File: page_heap.h

package info (click to toggle)
google-perftools 2.7-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 7,284 kB
  • sloc: cpp: 27,869; ansic: 9,534; sh: 4,799; perl: 4,116; makefile: 1,101; asm: 128
file content (358 lines) | stat: -rw-r--r-- 13,271 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
// -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*-
// Copyright (c) 2008, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// ---
// Author: Sanjay Ghemawat <opensource@google.com>

#ifndef TCMALLOC_PAGE_HEAP_H_
#define TCMALLOC_PAGE_HEAP_H_

#include <config.h>
#include <stddef.h>                     // for size_t
#ifdef HAVE_STDINT_H
#include <stdint.h>                     // for uint64_t, int64_t, uint16_t
#endif
#include <gperftools/malloc_extension.h>
#include "base/basictypes.h"
#include "common.h"
#include "packed-cache-inl.h"
#include "pagemap.h"
#include "span.h"

// We need to dllexport PageHeap just for the unittest.  MSVC complains
// that we don't dllexport the PageHeap members, but we don't need to
// test those, so I just suppress this warning.
#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable:4251)
#endif

// This #ifdef should almost never be set.  Set NO_TCMALLOC_SAMPLES if
// you're porting to a system where you really can't get a stacktrace.
// Because we control the definition of GetStackTrace, all clients of
// GetStackTrace should #include us rather than stacktrace.h.
#ifdef NO_TCMALLOC_SAMPLES
  // We use #define so code compiles even if you #include stacktrace.h somehow.
# define GetStackTrace(stack, depth, skip)  (0)
#else
# include <gperftools/stacktrace.h>
#endif

namespace base {
struct MallocRange;
}

namespace tcmalloc {

// -------------------------------------------------------------------------
// Map from page-id to per-page data
// -------------------------------------------------------------------------

// We use PageMap2<> for 32-bit and PageMap3<> for 64-bit machines.
// We also use a simple one-level cache for hot PageID-to-sizeclass mappings,
// because sometimes the sizeclass is all the information we need.

// Selector class -- general selector uses 3-level map
template <int BITS> class MapSelector {
 public:
  typedef TCMalloc_PageMap3<BITS-kPageShift> Type;
};

#ifndef TCMALLOC_SMALL_BUT_SLOW
// x86-64 and arm64 are using 48 bits of address space. So we can use
// just two level map, but since initial ram consumption of this mode
// is a bit on the higher side, we opt-out of it in
// TCMALLOC_SMALL_BUT_SLOW mode.
template <> class MapSelector<48> {
 public:
  typedef TCMalloc_PageMap2<48-kPageShift> Type;
};

#endif // TCMALLOC_SMALL_BUT_SLOW

// A two-level map for 32-bit machines
template <> class MapSelector<32> {
 public:
  typedef TCMalloc_PageMap2<32-kPageShift> Type;
};

// -------------------------------------------------------------------------
// Page-level allocator
//  * Eager coalescing
//
// Heap for page-level allocation.  We allow allocating and freeing a
// contiguous runs of pages (called a "span").
// -------------------------------------------------------------------------

class PERFTOOLS_DLL_DECL PageHeap {
 public:
  PageHeap();

  // Allocate a run of "n" pages.  Returns zero if out of memory.
  // Caller should not pass "n == 0" -- instead, n should have
  // been rounded up already.
  Span* New(Length n);

  // Delete the span "[p, p+n-1]".
  // REQUIRES: span was returned by earlier call to New() and
  //           has not yet been deleted.
  void Delete(Span* span);

  // Mark an allocated span as being used for small objects of the
  // specified size-class.
  // REQUIRES: span was returned by an earlier call to New()
  //           and has not yet been deleted.
  void RegisterSizeClass(Span* span, uint32 sc);

  // Split an allocated span into two spans: one of length "n" pages
  // followed by another span of length "span->length - n" pages.
  // Modifies "*span" to point to the first span of length "n" pages.
  // Returns a pointer to the second span.
  //
  // REQUIRES: "0 < n < span->length"
  // REQUIRES: span->location == IN_USE
  // REQUIRES: span->sizeclass == 0
  Span* Split(Span* span, Length n);

  // Return the descriptor for the specified page.  Returns NULL if
  // this PageID was not allocated previously.
  inline ATTRIBUTE_ALWAYS_INLINE
  Span* GetDescriptor(PageID p) const {
    return reinterpret_cast<Span*>(pagemap_.get(p));
  }

  // If this page heap is managing a range with starting page # >= start,
  // store info about the range in *r and return true.  Else return false.
  bool GetNextRange(PageID start, base::MallocRange* r);

  // Page heap statistics
  struct Stats {
    Stats() : system_bytes(0), free_bytes(0), unmapped_bytes(0), committed_bytes(0),
        scavenge_count(0), commit_count(0), total_commit_bytes(0),
        decommit_count(0), total_decommit_bytes(0),
        reserve_count(0), total_reserve_bytes(0) {}
    uint64_t system_bytes;    // Total bytes allocated from system
    uint64_t free_bytes;      // Total bytes on normal freelists
    uint64_t unmapped_bytes;  // Total bytes on returned freelists
    uint64_t committed_bytes;  // Bytes committed, always <= system_bytes_.

    uint64_t scavenge_count;   // Number of times scavagened flush pages

    uint64_t commit_count;          // Number of virtual memory commits
    uint64_t total_commit_bytes;    // Bytes committed in lifetime of process
    uint64_t decommit_count;        // Number of virtual memory decommits
    uint64_t total_decommit_bytes;  // Bytes decommitted in lifetime of process

    uint64_t reserve_count;         // Number of virtual memory reserves
    uint64_t total_reserve_bytes;   // Bytes reserved in lifetime of process
  };
  inline Stats stats() const { return stats_; }

  struct SmallSpanStats {
    // For each free list of small spans, the length (in spans) of the
    // normal and returned free lists for that size.
    //
    // NOTE: index 'i' accounts the number of spans of length 'i + 1'.
    int64 normal_length[kMaxPages];
    int64 returned_length[kMaxPages];
  };
  void GetSmallSpanStats(SmallSpanStats* result);

  // Stats for free large spans (i.e., spans with more than kMaxPages pages).
  struct LargeSpanStats {
    int64 spans;           // Number of such spans
    int64 normal_pages;    // Combined page length of normal large spans
    int64 returned_pages;  // Combined page length of unmapped spans
  };
  void GetLargeSpanStats(LargeSpanStats* result);

  bool Check();
  // Like Check() but does some more comprehensive checking.
  bool CheckExpensive();
  bool CheckList(Span* list, Length min_pages, Length max_pages,
                 int freelist);  // ON_NORMAL_FREELIST or ON_RETURNED_FREELIST
  bool CheckSet(SpanSet *s, Length min_pages, int freelist);

  // Try to release at least num_pages for reuse by the OS.  Returns
  // the actual number of pages released, which may be less than
  // num_pages if there weren't enough pages to release. The result
  // may also be larger than num_pages since page_heap might decide to
  // release one large range instead of fragmenting it into two
  // smaller released and unreleased ranges.
  Length ReleaseAtLeastNPages(Length num_pages);

  // Reads and writes to pagemap_cache_ do not require locking.
  bool TryGetSizeClass(PageID p, uint32* out) const {
    return pagemap_cache_.TryGet(p, out);
  }
  void SetCachedSizeClass(PageID p, uint32 cl) {
    ASSERT(cl != 0);
    pagemap_cache_.Put(p, cl);
  }
  void InvalidateCachedSizeClass(PageID p) { pagemap_cache_.Invalidate(p); }
  uint32 GetSizeClassOrZero(PageID p) const {
    uint32 cached_value;
    if (!TryGetSizeClass(p, &cached_value)) {
      cached_value = 0;
    }
    return cached_value;
  }

  bool GetAggressiveDecommit(void) {return aggressive_decommit_;}
  void SetAggressiveDecommit(bool aggressive_decommit) {
    aggressive_decommit_ = aggressive_decommit;
  }

 private:
  // Allocates a big block of memory for the pagemap once we reach more than
  // 128MB
  static const size_t kPageMapBigAllocationThreshold = 128 << 20;

  // Minimum number of pages to fetch from system at a time.  Must be
  // significantly bigger than kBlockSize to amortize system-call
  // overhead, and also to reduce external fragementation.  Also, we
  // should keep this value big because various incarnations of Linux
  // have small limits on the number of mmap() regions per
  // address-space.
  // REQUIRED: kMinSystemAlloc <= kMaxPages;
  static const int kMinSystemAlloc = kMaxPages;

  // Never delay scavenging for more than the following number of
  // deallocated pages.  With 4K pages, this comes to 4GB of
  // deallocation.
  static const int kMaxReleaseDelay = 1 << 20;

  // If there is nothing to release, wait for so many pages before
  // scavenging again.  With 4K pages, this comes to 1GB of memory.
  static const int kDefaultReleaseDelay = 1 << 18;

  // Pick the appropriate map and cache types based on pointer size
  typedef MapSelector<kAddressBits>::Type PageMap;
  typedef PackedCache<kAddressBits - kPageShift> PageMapCache;
  mutable PageMapCache pagemap_cache_;
  PageMap pagemap_;

  // We segregate spans of a given size into two circular linked
  // lists: one for normal spans, and one for spans whose memory
  // has been returned to the system.
  struct SpanList {
    Span        normal;
    Span        returned;
  };

  // Sets of spans with length > kMaxPages.
  //
  // Rather than using a linked list, we use sets here for efficient
  // best-fit search.
  SpanSet large_normal_;
  SpanSet large_returned_;

  // Array mapping from span length to a doubly linked list of free spans
  //
  // NOTE: index 'i' stores spans of length 'i + 1'.
  SpanList free_[kMaxPages];

  // Statistics on system, free, and unmapped bytes
  Stats stats_;

  Span* SearchFreeAndLargeLists(Length n);

  bool GrowHeap(Length n);

  // REQUIRES: span->length >= n
  // REQUIRES: span->location != IN_USE
  // Remove span from its free list, and move any leftover part of
  // span into appropriate free lists.  Also update "span" to have
  // length exactly "n" and mark it as non-free so it can be returned
  // to the client.  After all that, decrease free_pages_ by n and
  // return span.
  Span* Carve(Span* span, Length n);

  void RecordSpan(Span* span) {
    pagemap_.set(span->start, span);
    if (span->length > 1) {
      pagemap_.set(span->start + span->length - 1, span);
    }
  }

  // Allocate a large span of length == n.  If successful, returns a
  // span of exactly the specified length.  Else, returns NULL.
  Span* AllocLarge(Length n);

  // Coalesce span with neighboring spans if possible, prepend to
  // appropriate free list, and adjust stats.
  void MergeIntoFreeList(Span* span);

  // Commit the span.
  void CommitSpan(Span* span);

  // Decommit the span.
  bool DecommitSpan(Span* span);

  // Prepends span to appropriate free list, and adjusts stats.
  void PrependToFreeList(Span* span);

  // Removes span from its free list, and adjust stats.
  void RemoveFromFreeList(Span* span);

  // Incrementally release some memory to the system.
  // IncrementalScavenge(n) is called whenever n pages are freed.
  void IncrementalScavenge(Length n);

  // Attempts to decommit 's' and move it to the returned freelist.
  //
  // Returns the length of the Span or zero if release failed.
  //
  // REQUIRES: 's' must be on the NORMAL freelist.
  Length ReleaseSpan(Span *s);

  // Checks if we are allowed to take more memory from the system.
  // If limit is reached and allowRelease is true, tries to release
  // some unused spans.
  bool EnsureLimit(Length n, bool allowRelease = true);

  Span* CheckAndHandlePreMerge(Span *span, Span *other);

  // Number of pages to deallocate before doing more scavenging
  int64_t scavenge_counter_;

  // Index of last free list where we released memory to the OS.
  int release_index_;

  bool aggressive_decommit_;
};

}  // namespace tcmalloc

#ifdef _MSC_VER
#pragma warning(pop)
#endif

#endif  // TCMALLOC_PAGE_HEAP_H_