OLD | NEW |
1 // Copyright (c) 2008, Google Inc. | 1 // Copyright (c) 2008, Google Inc. |
2 // All rights reserved. | 2 // All rights reserved. |
3 // | 3 // |
4 // Redistribution and use in source and binary forms, with or without | 4 // Redistribution and use in source and binary forms, with or without |
5 // modification, are permitted provided that the following conditions are | 5 // modification, are permitted provided that the following conditions are |
6 // met: | 6 // met: |
7 // | 7 // |
8 // * Redistributions of source code must retain the above copyright | 8 // * Redistributions of source code must retain the above copyright |
9 // notice, this list of conditions and the following disclaimer. | 9 // notice, this list of conditions and the following disclaimer. |
10 // * Redistributions in binary form must reproduce the above | 10 // * Redistributions in binary form must reproduce the above |
(...skipping 13 matching lines...) Expand all Loading... |
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 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. | 28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
29 | 29 |
30 // --- | 30 // --- |
31 // Author: Sanjay Ghemawat <opensource@google.com> | 31 // Author: Sanjay Ghemawat <opensource@google.com> |
32 | 32 |
33 #include <config.h> | 33 #include <config.h> |
34 #include "page_heap.h" | 34 #ifdef HAVE_INTTYPES_H |
35 | 35 #include <inttypes.h> // for PRIuPTR |
36 #include "static_vars.h" | 36 #endif |
37 #include "system-alloc.h" | 37 #include <google/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 |
38 | 44 |
39 DEFINE_double(tcmalloc_release_rate, | 45 DEFINE_double(tcmalloc_release_rate, |
40 EnvToDouble("TCMALLOC_RELEASE_RATE", 1.0), | 46 EnvToDouble("TCMALLOC_RELEASE_RATE", 1.0), |
41 "Rate at which we release unused memory to the system. " | 47 "Rate at which we release unused memory to the system. " |
42 "Zero means we never release memory back to the system. " | 48 "Zero means we never release memory back to the system. " |
43 "Increase this flag to return memory faster; decrease it " | 49 "Increase this flag to return memory faster; decrease it " |
44 "to return memory slower. Reasonable rates are in the " | 50 "to return memory slower. Reasonable rates are in the " |
45 "range [0,10]"); | 51 "range [0,10]"); |
46 | 52 |
47 namespace tcmalloc { | 53 namespace tcmalloc { |
48 | 54 |
49 PageHeap::PageHeap() | 55 PageHeap::PageHeap() |
50 : pagemap_(MetaDataAlloc), | 56 : pagemap_(MetaDataAlloc), |
51 pagemap_cache_(0), | 57 pagemap_cache_(0), |
52 scavenge_counter_(0), | 58 scavenge_counter_(0), |
53 // Start scavenging at kMaxPages list | 59 // Start scavenging at kMaxPages list |
54 release_index_(kMaxPages) { | 60 release_index_(kMaxPages) { |
55 COMPILE_ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits), valuebits); | 61 COMPILE_ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits), valuebits); |
56 DLL_Init(&large_.normal); | 62 DLL_Init(&large_.normal); |
57 DLL_Init(&large_.returned); | 63 DLL_Init(&large_.returned); |
58 for (int i = 0; i < kMaxPages; i++) { | 64 for (int i = 0; i < kMaxPages; i++) { |
59 DLL_Init(&free_[i].normal); | 65 DLL_Init(&free_[i].normal); |
60 DLL_Init(&free_[i].returned); | 66 DLL_Init(&free_[i].returned); |
61 } | 67 } |
62 } | 68 } |
63 | 69 |
64 Span* PageHeap::New(Length n) { | 70 Span* PageHeap::SearchFreeAndLargeLists(Length n) { |
65 ASSERT(Check()); | 71 ASSERT(Check()); |
66 ASSERT(n > 0); | 72 ASSERT(n > 0); |
67 | 73 |
68 // Find first size >= n that has a non-empty list | 74 // Find first size >= n that has a non-empty list |
69 for (Length s = n; s < kMaxPages; s++) { | 75 for (Length s = n; s < kMaxPages; s++) { |
70 Span* ll = &free_[s].normal; | 76 Span* ll = &free_[s].normal; |
71 // If we're lucky, ll is non-empty, meaning it has a suitable span. | 77 // If we're lucky, ll is non-empty, meaning it has a suitable span. |
72 if (!DLL_IsEmpty(ll)) { | 78 if (!DLL_IsEmpty(ll)) { |
73 ASSERT(ll->next->location == Span::ON_NORMAL_FREELIST); | 79 ASSERT(ll->next->location == Span::ON_NORMAL_FREELIST); |
74 return Carve(ll->next, n); | 80 return Carve(ll->next, n); |
75 } | 81 } |
76 // Alternatively, maybe there's a usable returned span. | 82 // Alternatively, maybe there's a usable returned span. |
77 ll = &free_[s].returned; | 83 ll = &free_[s].returned; |
78 if (!DLL_IsEmpty(ll)) { | 84 if (!DLL_IsEmpty(ll)) { |
79 ASSERT(ll->next->location == Span::ON_RETURNED_FREELIST); | 85 ASSERT(ll->next->location == Span::ON_RETURNED_FREELIST); |
80 return Carve(ll->next, n); | 86 return Carve(ll->next, n); |
81 } | 87 } |
82 // Still no luck, so keep looking in larger classes. | |
83 } | 88 } |
| 89 // No luck in free lists, our last chance is in a larger class. |
| 90 return AllocLarge(n); // May be NULL |
| 91 } |
84 | 92 |
85 Span* result = AllocLarge(n); | 93 Span* PageHeap::New(Length n) { |
86 if (result != NULL) return result; | 94 ASSERT(Check()); |
| 95 ASSERT(n > 0); |
87 | 96 |
88 // Grow the heap and try again | 97 Span* result = SearchFreeAndLargeLists(n); |
| 98 if (result != NULL) |
| 99 return result; |
| 100 |
| 101 // Grow the heap and try again. |
89 if (!GrowHeap(n)) { | 102 if (!GrowHeap(n)) { |
90 ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes); | 103 ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes); |
91 ASSERT(Check()); | 104 ASSERT(Check()); |
92 return NULL; | 105 return NULL; |
93 } | 106 } |
94 | 107 return SearchFreeAndLargeLists(n); |
95 return AllocLarge(n); | |
96 } | 108 } |
97 | 109 |
98 Span* PageHeap::AllocLarge(Length n) { | 110 Span* PageHeap::AllocLarge(Length n) { |
99 // find the best span (closest to n in size). | 111 // find the best span (closest to n in size). |
100 // The following loops implements address-ordered best-fit. | 112 // The following loops implements address-ordered best-fit. |
101 Span *best = NULL; | 113 Span *best = NULL; |
102 | 114 |
103 // Search through normal list | 115 // Search through normal list |
104 for (Span* span = large_.normal.next; | 116 for (Span* span = large_.normal.next; |
105 span != &large_.normal; | 117 span != &large_.normal; |
(...skipping 278 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
384 ASSERT(span->location == Span::IN_USE); | 396 ASSERT(span->location == Span::IN_USE); |
385 ASSERT(GetDescriptor(span->start) == span); | 397 ASSERT(GetDescriptor(span->start) == span); |
386 ASSERT(GetDescriptor(span->start+span->length-1) == span); | 398 ASSERT(GetDescriptor(span->start+span->length-1) == span); |
387 Event(span, 'C', sc); | 399 Event(span, 'C', sc); |
388 span->sizeclass = sc; | 400 span->sizeclass = sc; |
389 for (Length i = 1; i < span->length-1; i++) { | 401 for (Length i = 1; i < span->length-1; i++) { |
390 pagemap_.set(span->start+i, span); | 402 pagemap_.set(span->start+i, span); |
391 } | 403 } |
392 } | 404 } |
393 | 405 |
394 static double MB(uint64_t bytes) { | 406 static double MiB(uint64_t bytes) { |
395 return bytes / 1048576.0; | 407 return bytes / 1048576.0; |
396 } | 408 } |
397 | 409 |
398 static double PagesToMB(uint64_t pages) { | 410 static double PagesToMiB(uint64_t pages) { |
399 return (pages << kPageShift) / 1048576.0; | 411 return (pages << kPageShift) / 1048576.0; |
400 } | 412 } |
401 | 413 |
| 414 void PageHeap::GetClassSizes(int64 class_sizes_normal[kMaxPages], |
| 415 int64 class_sizes_returned[kMaxPages], |
| 416 int64* normal_pages_in_spans, |
| 417 int64* returned_pages_in_spans) { |
| 418 |
| 419 for (int s = 0; s < kMaxPages; s++) { |
| 420 if (class_sizes_normal != NULL) { |
| 421 class_sizes_normal[s] = DLL_Length(&free_[s].normal); |
| 422 } |
| 423 if (class_sizes_returned != NULL) { |
| 424 class_sizes_returned[s] = DLL_Length(&free_[s].returned); |
| 425 } |
| 426 } |
| 427 |
| 428 if (normal_pages_in_spans != NULL) { |
| 429 *normal_pages_in_spans = 0; |
| 430 for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) { |
| 431 *normal_pages_in_spans += s->length;; |
| 432 } |
| 433 } |
| 434 |
| 435 if (returned_pages_in_spans != NULL) { |
| 436 *returned_pages_in_spans = 0; |
| 437 for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) { |
| 438 *returned_pages_in_spans += s->length; |
| 439 } |
| 440 } |
| 441 } |
| 442 |
402 void PageHeap::Dump(TCMalloc_Printer* out) { | 443 void PageHeap::Dump(TCMalloc_Printer* out) { |
403 int nonempty_sizes = 0; | 444 int nonempty_sizes = 0; |
404 for (int s = 0; s < kMaxPages; s++) { | 445 for (int s = 0; s < kMaxPages; s++) { |
405 if (!DLL_IsEmpty(&free_[s].normal) || !DLL_IsEmpty(&free_[s].returned)) { | 446 if (!DLL_IsEmpty(&free_[s].normal) || !DLL_IsEmpty(&free_[s].returned)) { |
406 nonempty_sizes++; | 447 nonempty_sizes++; |
407 } | 448 } |
408 } | 449 } |
409 out->printf("------------------------------------------------\n"); | 450 out->printf("------------------------------------------------\n"); |
410 out->printf("PageHeap: %d sizes; %6.1f MB free; %6.1f MB unmapped\n", | 451 out->printf("PageHeap: %d sizes; %6.1f MiB free; %6.1f MiB unmapped\n", |
411 nonempty_sizes, MB(stats_.free_bytes), MB(stats_.unmapped_bytes)); | 452 nonempty_sizes, MiB(stats_.free_bytes), |
| 453 MiB(stats_.unmapped_bytes)); |
412 out->printf("------------------------------------------------\n"); | 454 out->printf("------------------------------------------------\n"); |
413 uint64_t total_normal = 0; | 455 uint64_t total_normal = 0; |
414 uint64_t total_returned = 0; | 456 uint64_t total_returned = 0; |
415 for (int s = 0; s < kMaxPages; s++) { | 457 for (int s = 0; s < kMaxPages; s++) { |
416 const int n_length = DLL_Length(&free_[s].normal); | 458 const int n_length = DLL_Length(&free_[s].normal); |
417 const int r_length = DLL_Length(&free_[s].returned); | 459 const int r_length = DLL_Length(&free_[s].returned); |
418 if (n_length + r_length > 0) { | 460 if (n_length + r_length > 0) { |
419 uint64_t n_pages = s * n_length; | 461 uint64_t n_pages = s * n_length; |
420 uint64_t r_pages = s * r_length; | 462 uint64_t r_pages = s * r_length; |
421 total_normal += n_pages; | 463 total_normal += n_pages; |
422 total_returned += r_pages; | 464 total_returned += r_pages; |
423 out->printf("%6u pages * %6u spans ~ %6.1f MB; %6.1f MB cum" | 465 out->printf("%6u pages * %6u spans ~ %6.1f MiB; %6.1f MiB cum" |
424 "; unmapped: %6.1f MB; %6.1f MB cum\n", | 466 "; unmapped: %6.1f MiB; %6.1f MiB cum\n", |
425 s, | 467 s, |
426 (n_length + r_length), | 468 (n_length + r_length), |
427 PagesToMB(n_pages + r_pages), | 469 PagesToMiB(n_pages + r_pages), |
428 PagesToMB(total_normal + total_returned), | 470 PagesToMiB(total_normal + total_returned), |
429 PagesToMB(r_pages), | 471 PagesToMiB(r_pages), |
430 PagesToMB(total_returned)); | 472 PagesToMiB(total_returned)); |
431 } | 473 } |
432 } | 474 } |
433 | 475 |
434 uint64_t n_pages = 0; | 476 uint64_t n_pages = 0; |
435 uint64_t r_pages = 0; | 477 uint64_t r_pages = 0; |
436 int n_spans = 0; | 478 int n_spans = 0; |
437 int r_spans = 0; | 479 int r_spans = 0; |
438 out->printf("Normal large spans:\n"); | 480 out->printf("Normal large spans:\n"); |
439 for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) { | 481 for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) { |
440 out->printf(" [ %6" PRIuPTR " pages ] %6.1f MB\n", | 482 out->printf(" [ %6" PRIuPTR " pages ] %6.1f MiB\n", |
441 s->length, PagesToMB(s->length)); | 483 s->length, PagesToMiB(s->length)); |
442 n_pages += s->length; | 484 n_pages += s->length; |
443 n_spans++; | 485 n_spans++; |
444 } | 486 } |
445 out->printf("Unmapped large spans:\n"); | 487 out->printf("Unmapped large spans:\n"); |
446 for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) { | 488 for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) { |
447 out->printf(" [ %6" PRIuPTR " pages ] %6.1f MB\n", | 489 out->printf(" [ %6" PRIuPTR " pages ] %6.1f MiB\n", |
448 s->length, PagesToMB(s->length)); | 490 s->length, PagesToMiB(s->length)); |
449 r_pages += s->length; | 491 r_pages += s->length; |
450 r_spans++; | 492 r_spans++; |
451 } | 493 } |
452 total_normal += n_pages; | 494 total_normal += n_pages; |
453 total_returned += r_pages; | 495 total_returned += r_pages; |
454 out->printf(">255 large * %6u spans ~ %6.1f MB; %6.1f MB cum" | 496 out->printf(">255 large * %6u spans ~ %6.1f MiB; %6.1f MiB cum" |
455 "; unmapped: %6.1f MB; %6.1f MB cum\n", | 497 "; unmapped: %6.1f MiB; %6.1f MiB cum\n", |
456 (n_spans + r_spans), | 498 (n_spans + r_spans), |
457 PagesToMB(n_pages + r_pages), | 499 PagesToMiB(n_pages + r_pages), |
458 PagesToMB(total_normal + total_returned), | 500 PagesToMiB(total_normal + total_returned), |
459 PagesToMB(r_pages), | 501 PagesToMiB(r_pages), |
460 PagesToMB(total_returned)); | 502 PagesToMiB(total_returned)); |
461 } | 503 } |
462 | 504 |
463 bool PageHeap::GetNextRange(PageID start, base::MallocRange* r) { | 505 bool PageHeap::GetNextRange(PageID start, base::MallocRange* r) { |
464 Span* span = reinterpret_cast<Span*>(pagemap_.Next(start)); | 506 Span* span = reinterpret_cast<Span*>(pagemap_.Next(start)); |
465 if (span == NULL) { | 507 if (span == NULL) { |
466 return false; | 508 return false; |
467 } | 509 } |
468 r->address = span->start << kPageShift; | 510 r->address = span->start << kPageShift; |
469 r->length = span->length << kPageShift; | 511 r->length = span->length << kPageShift; |
470 r->fraction = 0; | 512 r->fraction = 0; |
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
573 CHECK_CONDITION(s->location == freelist); // NORMAL or RETURNED | 615 CHECK_CONDITION(s->location == freelist); // NORMAL or RETURNED |
574 CHECK_CONDITION(s->length >= min_pages); | 616 CHECK_CONDITION(s->length >= min_pages); |
575 CHECK_CONDITION(s->length <= max_pages); | 617 CHECK_CONDITION(s->length <= max_pages); |
576 CHECK_CONDITION(GetDescriptor(s->start) == s); | 618 CHECK_CONDITION(GetDescriptor(s->start) == s); |
577 CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s); | 619 CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s); |
578 } | 620 } |
579 return true; | 621 return true; |
580 } | 622 } |
581 | 623 |
582 } // namespace tcmalloc | 624 } // namespace tcmalloc |
OLD | NEW |