1// Copyright (c) 2008, Google Inc.
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8//     * Redistributions of source code must retain the above copyright
9// notice, this list of conditions and the following disclaimer.
10//     * Redistributions in binary form must reproduce the above
11// copyright notice, this list of conditions and the following disclaimer
12// in the documentation and/or other materials provided with the
13// distribution.
14//     * Neither the name of Google Inc. nor the names of its
15// contributors may be used to endorse or promote products derived from
16// this software without specific prior written permission.
17//
18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30// ---
31// Author: Sanjay Ghemawat <opensource@google.com>
32
33#include <config.h>
34#ifdef HAVE_INTTYPES_H
35#include <inttypes.h>                   // for PRIuPTR
36#endif
37#include <gperftools/malloc_extension.h>      // for MallocRange, etc
38#include "base/basictypes.h"
39#include "base/commandlineflags.h"
40#include "internal_logging.h"  // for ASSERT, TCMalloc_Printer, etc
41#include "page_heap_allocator.h"  // for PageHeapAllocator
42#include "static_vars.h"       // for Static
43#include "system-alloc.h"      // for TCMalloc_SystemAlloc, etc
44
45DEFINE_double(tcmalloc_release_rate,
46              EnvToDouble("TCMALLOC_RELEASE_RATE", 1.0),
47              "Rate at which we release unused memory to the system.  "
48              "Zero means we never release memory back to the system.  "
49              "Increase this flag to return memory faster; decrease it "
50              "to return memory slower.  Reasonable rates are in the "
51              "range [0,10]");
52
53namespace tcmalloc {
54
55PageHeap::PageHeap()
56    : pagemap_(MetaDataAlloc),
57      pagemap_cache_(0),
58      scavenge_counter_(0),
59      // Start scavenging at kMaxPages list
60      release_index_(kMaxPages) {
61  COMPILE_ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits), valuebits);
62  DLL_Init(&large_.normal);
63  DLL_Init(&large_.returned);
64  for (int i = 0; i < kMaxPages; i++) {
65    DLL_Init(&free_[i].normal);
66    DLL_Init(&free_[i].returned);
67  }
68}
69
70Span* PageHeap::SearchFreeAndLargeLists(Length n) {
71  ASSERT(Check());
72  ASSERT(n > 0);
73
74  // Find first size >= n that has a non-empty list
75  for (Length s = n; s < kMaxPages; s++) {
76    Span* ll = &free_[s].normal;
77    // If we're lucky, ll is non-empty, meaning it has a suitable span.
78    if (!DLL_IsEmpty(ll)) {
79      ASSERT(ll->next->location == Span::ON_NORMAL_FREELIST);
80      return Carve(ll->next, n);
81    }
82    // Alternatively, maybe there's a usable returned span.
83    ll = &free_[s].returned;
84    if (!DLL_IsEmpty(ll)) {
85      ASSERT(ll->next->location == Span::ON_RETURNED_FREELIST);
86      return Carve(ll->next, n);
87    }
88  }
89  // No luck in free lists, our last chance is in a larger class.
90  return AllocLarge(n);  // May be NULL
91}
92
93Span* PageHeap::New(Length n) {
94  ASSERT(Check());
95  ASSERT(n > 0);
96
97  Span* result = SearchFreeAndLargeLists(n);
98  if (result != NULL)
99    return result;
100
101  // Grow the heap and try again.
102  if (!GrowHeap(n)) {
103    ASSERT(Check());
104    return NULL;
105  }
106  return SearchFreeAndLargeLists(n);
107}
108
109Span* PageHeap::AllocLarge(Length n) {
110  // find the best span (closest to n in size).
111  // The following loops implements address-ordered best-fit.
112  Span *best = NULL;
113
114  // Search through normal list
115  for (Span* span = large_.normal.next;
116       span != &large_.normal;
117       span = span->next) {
118    if (span->length >= n) {
119      if ((best == NULL)
120          || (span->length < best->length)
121          || ((span->length == best->length) && (span->start < best->start))) {
122        best = span;
123        ASSERT(best->location == Span::ON_NORMAL_FREELIST);
124      }
125    }
126  }
127
128  // Search through released list in case it has a better fit
129  for (Span* span = large_.returned.next;
130       span != &large_.returned;
131       span = span->next) {
132    if (span->length >= n) {
133      if ((best == NULL)
134          || (span->length < best->length)
135          || ((span->length == best->length) && (span->start < best->start))) {
136        best = span;
137        ASSERT(best->location == Span::ON_RETURNED_FREELIST);
138      }
139    }
140  }
141
142  return best == NULL ? NULL : Carve(best, n);
143}
144
145Span* PageHeap::Split(Span* span, Length n) {
146  ASSERT(0 < n);
147  ASSERT(n < span->length);
148  ASSERT(span->location == Span::IN_USE);
149  ASSERT(span->sizeclass == 0);
150  Event(span, 'T', n);
151
152  const int extra = span->length - n;
153  Span* leftover = NewSpan(span->start + n, extra);
154  ASSERT(leftover->location == Span::IN_USE);
155  Event(leftover, 'U', extra);
156  RecordSpan(leftover);
157  pagemap_.set(span->start + n - 1, span); // Update map from pageid to span
158  span->length = n;
159
160  return leftover;
161}
162
163Span* PageHeap::Carve(Span* span, Length n) {
164  ASSERT(n > 0);
165  ASSERT(span->location != Span::IN_USE);
166  const int old_location = span->location;
167  RemoveFromFreeList(span);
168  span->location = Span::IN_USE;
169  Event(span, 'A', n);
170
171  const int extra = span->length - n;
172  ASSERT(extra >= 0);
173  if (extra > 0) {
174    Span* leftover = NewSpan(span->start + n, extra);
175    leftover->location = old_location;
176    Event(leftover, 'S', extra);
177    RecordSpan(leftover);
178    PrependToFreeList(leftover);  // Skip coalescing - no candidates possible
179    span->length = n;
180    pagemap_.set(span->start + n - 1, span);
181  }
182  ASSERT(Check());
183  return span;
184}
185
186void PageHeap::Delete(Span* span) {
187  ASSERT(Check());
188  ASSERT(span->location == Span::IN_USE);
189  ASSERT(span->length > 0);
190  ASSERT(GetDescriptor(span->start) == span);
191  ASSERT(GetDescriptor(span->start + span->length - 1) == span);
192  const Length n = span->length;
193  span->sizeclass = 0;
194  span->sample = 0;
195  span->location = Span::ON_NORMAL_FREELIST;
196  Event(span, 'D', span->length);
197  MergeIntoFreeList(span);  // Coalesces if possible
198  IncrementalScavenge(n);
199  ASSERT(Check());
200}
201
202void PageHeap::MergeIntoFreeList(Span* span) {
203  ASSERT(span->location != Span::IN_USE);
204
205  // Coalesce -- we guarantee that "p" != 0, so no bounds checking
206  // necessary.  We do not bother resetting the stale pagemap
207  // entries for the pieces we are merging together because we only
208  // care about the pagemap entries for the boundaries.
209  //
210  // Note that only similar spans are merged together.  For example,
211  // we do not coalesce "returned" spans with "normal" spans.
212  const PageID p = span->start;
213  const Length n = span->length;
214  Span* prev = GetDescriptor(p-1);
215  if (prev != NULL && prev->location == span->location) {
216    // Merge preceding span into this span
217    ASSERT(prev->start + prev->length == p);
218    const Length len = prev->length;
219    RemoveFromFreeList(prev);
220    DeleteSpan(prev);
221    span->start -= len;
222    span->length += len;
223    pagemap_.set(span->start, span);
224    Event(span, 'L', len);
225  }
226  Span* next = GetDescriptor(p+n);
227  if (next != NULL && next->location == span->location) {
228    // Merge next span into this span
229    ASSERT(next->start == p+n);
230    const Length len = next->length;
231    RemoveFromFreeList(next);
232    DeleteSpan(next);
233    span->length += len;
234    pagemap_.set(span->start + span->length - 1, span);
235    Event(span, 'R', len);
236  }
237
238  PrependToFreeList(span);
239}
240
241void PageHeap::PrependToFreeList(Span* span) {
242  ASSERT(span->location != Span::IN_USE);
243  SpanList* list = (span->length < kMaxPages) ? &free_[span->length] : &large_;
244  if (span->location == Span::ON_NORMAL_FREELIST) {
245    stats_.free_bytes += (span->length << kPageShift);
246    DLL_Prepend(&list->normal, span);
247  } else {
248    stats_.unmapped_bytes += (span->length << kPageShift);
249    DLL_Prepend(&list->returned, span);
250  }
251}
252
253void PageHeap::RemoveFromFreeList(Span* span) {
254  ASSERT(span->location != Span::IN_USE);
255  if (span->location == Span::ON_NORMAL_FREELIST) {
256    stats_.free_bytes -= (span->length << kPageShift);
257  } else {
258    stats_.unmapped_bytes -= (span->length << kPageShift);
259  }
260  DLL_Remove(span);
261}
262
263void PageHeap::IncrementalScavenge(Length n) {
264  // Fast path; not yet time to release memory
265  scavenge_counter_ -= n;
266  if (scavenge_counter_ >= 0) return;  // Not yet time to scavenge
267
268  const double rate = FLAGS_tcmalloc_release_rate;
269  if (rate <= 1e-6) {
270    // Tiny release rate means that releasing is disabled.
271    scavenge_counter_ = kDefaultReleaseDelay;
272    return;
273  }
274
275  Length released_pages = ReleaseAtLeastNPages(1);
276
277  if (released_pages == 0) {
278    // Nothing to scavenge, delay for a while.
279    scavenge_counter_ = kDefaultReleaseDelay;
280  } else {
281    // Compute how long to wait until we return memory.
282    // FLAGS_tcmalloc_release_rate==1 means wait for 1000 pages
283    // after releasing one page.
284    const double mult = 1000.0 / rate;
285    double wait = mult * static_cast<double>(released_pages);
286    if (wait > kMaxReleaseDelay) {
287      // Avoid overflow and bound to reasonable range.
288      wait = kMaxReleaseDelay;
289    }
290    scavenge_counter_ = static_cast<int64_t>(wait);
291  }
292}
293
294Length PageHeap::ReleaseLastNormalSpan(SpanList* slist) {
295  Span* s = slist->normal.prev;
296  ASSERT(s->location == Span::ON_NORMAL_FREELIST);
297  RemoveFromFreeList(s);
298  const Length n = s->length;
299  TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
300                         static_cast<size_t>(s->length << kPageShift));
301  s->location = Span::ON_RETURNED_FREELIST;
302  MergeIntoFreeList(s);  // Coalesces if possible.
303  return n;
304}
305
306Length PageHeap::ReleaseAtLeastNPages(Length num_pages) {
307  Length released_pages = 0;
308  Length prev_released_pages = -1;
309
310  // Round robin through the lists of free spans, releasing the last
311  // span in each list.  Stop after releasing at least num_pages.
312  while (released_pages < num_pages) {
313    if (released_pages == prev_released_pages) {
314      // Last iteration of while loop made no progress.
315      break;
316    }
317    prev_released_pages = released_pages;
318
319    for (int i = 0; i < kMaxPages+1 && released_pages < num_pages;
320         i++, release_index_++) {
321      if (release_index_ > kMaxPages) release_index_ = 0;
322      SpanList* slist = (release_index_ == kMaxPages) ?
323          &large_ : &free_[release_index_];
324      if (!DLL_IsEmpty(&slist->normal)) {
325        Length released_len = ReleaseLastNormalSpan(slist);
326        released_pages += released_len;
327      }
328    }
329  }
330  return released_pages;
331}
332
333void PageHeap::RegisterSizeClass(Span* span, size_t sc) {
334  // Associate span object with all interior pages as well
335  ASSERT(span->location == Span::IN_USE);
336  ASSERT(GetDescriptor(span->start) == span);
337  ASSERT(GetDescriptor(span->start+span->length-1) == span);
338  Event(span, 'C', sc);
339  span->sizeclass = sc;
340  for (Length i = 1; i < span->length-1; i++) {
341    pagemap_.set(span->start+i, span);
342  }
343}
344
345void PageHeap::GetSmallSpanStats(SmallSpanStats* result) {
346  for (int s = 0; s < kMaxPages; s++) {
347    result->normal_length[s] = DLL_Length(&free_[s].normal);
348    result->returned_length[s] = DLL_Length(&free_[s].returned);
349  }
350}
351
352void PageHeap::GetLargeSpanStats(LargeSpanStats* result) {
353  result->spans = 0;
354  result->normal_pages = 0;
355  result->returned_pages = 0;
356  for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) {
357    result->normal_pages += s->length;;
358    result->spans++;
359  }
360  for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) {
361    result->returned_pages += s->length;
362    result->spans++;
363  }
364}
365
366bool PageHeap::GetNextRange(PageID start, base::MallocRange* r) {
367  Span* span = reinterpret_cast<Span*>(pagemap_.Next(start));
368  if (span == NULL) {
369    return false;
370  }
371  r->address = span->start << kPageShift;
372  r->length = span->length << kPageShift;
373  r->fraction = 0;
374  switch (span->location) {
375    case Span::IN_USE:
376      r->type = base::MallocRange::INUSE;
377      r->fraction = 1;
378      if (span->sizeclass > 0) {
379        // Only some of the objects in this span may be in use.
380        const size_t osize = Static::sizemap()->class_to_size(span->sizeclass);
381        r->fraction = (1.0 * osize * span->refcount) / r->length;
382      }
383      break;
384    case Span::ON_NORMAL_FREELIST:
385      r->type = base::MallocRange::FREE;
386      break;
387    case Span::ON_RETURNED_FREELIST:
388      r->type = base::MallocRange::UNMAPPED;
389      break;
390    default:
391      r->type = base::MallocRange::UNKNOWN;
392      break;
393  }
394  return true;
395}
396
397static void RecordGrowth(size_t growth) {
398  StackTrace* t = Static::stacktrace_allocator()->New();
399  t->depth = GetStackTrace(t->stack, kMaxStackDepth-1, 3);
400  t->size = growth;
401  t->stack[kMaxStackDepth-1] = reinterpret_cast<void*>(Static::growth_stacks());
402  Static::set_growth_stacks(t);
403}
404
405bool PageHeap::GrowHeap(Length n) {
406  ASSERT(kMaxPages >= kMinSystemAlloc);
407  if (n > kMaxValidPages) return false;
408  Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc);
409  size_t actual_size;
410  void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
411  if (ptr == NULL) {
412    if (n < ask) {
413      // Try growing just "n" pages
414      ask = n;
415      ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
416    }
417    if (ptr == NULL) return false;
418  }
419  ask = actual_size >> kPageShift;
420  RecordGrowth(ask << kPageShift);
421
422  uint64_t old_system_bytes = stats_.system_bytes;
423  stats_.system_bytes += (ask << kPageShift);
424  const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
425  ASSERT(p > 0);
426
427  // If we have already a lot of pages allocated, just pre allocate a bunch of
428  // memory for the page map. This prevents fragmentation by pagemap metadata
429  // when a program keeps allocating and freeing large blocks.
430
431  if (old_system_bytes < kPageMapBigAllocationThreshold
432      && stats_.system_bytes >= kPageMapBigAllocationThreshold) {
433    pagemap_.PreallocateMoreMemory();
434  }
435
436  // Make sure pagemap_ has entries for all of the new pages.
437  // Plus ensure one before and one after so coalescing code
438  // does not need bounds-checking.
439  if (pagemap_.Ensure(p-1, ask+2)) {
440    // Pretend the new area is allocated and then Delete() it to cause
441    // any necessary coalescing to occur.
442    Span* span = NewSpan(p, ask);
443    RecordSpan(span);
444    Delete(span);
445    ASSERT(Check());
446    return true;
447  } else {
448    // We could not allocate memory within "pagemap_"
449    // TODO: Once we can return memory to the system, return the new span
450    return false;
451  }
452}
453
454bool PageHeap::Check() {
455  ASSERT(free_[0].normal.next == &free_[0].normal);
456  ASSERT(free_[0].returned.next == &free_[0].returned);
457  return true;
458}
459
460bool PageHeap::CheckExpensive() {
461  bool result = Check();
462  CheckList(&large_.normal, kMaxPages, 1000000000, Span::ON_NORMAL_FREELIST);
463  CheckList(&large_.returned, kMaxPages, 1000000000, Span::ON_RETURNED_FREELIST);
464  for (Length s = 1; s < kMaxPages; s++) {
465    CheckList(&free_[s].normal, s, s, Span::ON_NORMAL_FREELIST);
466    CheckList(&free_[s].returned, s, s, Span::ON_RETURNED_FREELIST);
467  }
468  return result;
469}
470
471bool PageHeap::CheckList(Span* list, Length min_pages, Length max_pages,
472                         int freelist) {
473  for (Span* s = list->next; s != list; s = s->next) {
474    CHECK_CONDITION(s->location == freelist);  // NORMAL or RETURNED
475    CHECK_CONDITION(s->length >= min_pages);
476    CHECK_CONDITION(s->length <= max_pages);
477    CHECK_CONDITION(GetDescriptor(s->start) == s);
478    CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s);
479  }
480  return true;
481}
482
483}  // namespace tcmalloc
484