src/third_party/tcmalloc/vendor/src/common.cc

   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 #include "common.h"
  35 #include "system-alloc.h"
  36
  37 namespace tcmalloc {
  38
  39 // Note: the following only works for "n"s that fit in 32-bits, but
  40 // that is fine since we only use it for small sizes.
  41 static inline int LgFloor(size_t n) {
  42   int log = 0;
  43   for (int i = 4; i >= 0; --i) {
  44     int shift = (1 << i);
  45     size_t x = n >> shift;
  46     if (x != 0) {
  47       n = x;
  48       log += shift;
  49     }
  50   }
  51   ASSERT(n == 1);
  52   return log;
  53 }
  54
  55 int AlignmentForSize(size_t size) {
  56   int alignment = kAlignment;
  57   if (size > kMaxSize) {
  58     // Cap alignment at kPageSize for large sizes.
  59     alignment = kPageSize;
  60   } else if (size >= 128) {
  61     // Space wasted due to alignment is at most 1/8, i.e., 12.5%.
  62     alignment = (1 << LgFloor(size)) / 8;
  63   } else if (size >= 16) {
  64     // We need an alignment of at least 16 bytes to satisfy
  65     // requirements for some SSE types.
  66     alignment = 16;
  67   }
  68   // Maximum alignment allowed is page size alignment.
  69   if (alignment > kPageSize) {
  70     alignment = kPageSize;
  71   }
  72   CHECK_CONDITION(size < 16 || alignment >= 16);
  73   CHECK_CONDITION((alignment & (alignment - 1)) == 0);
  74   return alignment;
  75 }
  76
  77 int SizeMap::NumMoveSize(size_t size) {
  78   if (size == 0) return 0;
  79   // Use approx 64k transfers between thread and central caches.
  80   int num = static_cast<int>(64.0 * 1024.0 / size);
  81   if (num < 2) num = 2;
  82
  83   // Avoid bringing too many objects into small object free lists.
  84   // If this value is too large:
  85   // - We waste memory with extra objects sitting in the thread caches.
  86   // - The central freelist holds its lock for too long while
  87   //   building a linked list of objects, slowing down the allocations
  88   //   of other threads.
  89   // If this value is too small:
  90   // - We go to the central freelist too often and we have to acquire
  91   //   its lock each time.
  92   // This value strikes a balance between the constraints above.
  93   if (num > 32) num = 32;
  94
  95   return num;
  96 }
  97
  98 // Initialize the mapping arrays
  99 void SizeMap::Init() {
 100   // Do some sanity checking on add_amount[]/shift_amount[]/class_array[]
 101   if (ClassIndex(0) < 0) {
 102     Log(kCrash, __FILE__, __LINE__,
 103         "Invalid class index for size 0", ClassIndex(0));
 104   }
 105   if (ClassIndex(kMaxSize) >= sizeof(class_array_)) {
 106     Log(kCrash, __FILE__, __LINE__,
 107         "Invalid class index for kMaxSize", ClassIndex(kMaxSize));
 108   }
 109
 110   // Compute the size classes we want to use
 111   int sc = 1;   // Next size class to assign
 112   int alignment = kAlignment;
 113   CHECK_CONDITION(kAlignment <= 16);
 114   for (size_t size = kAlignment; size <= kMaxSize; size += alignment) {
 115     alignment = AlignmentForSize(size);
 116     CHECK_CONDITION((size % alignment) == 0);
 117
 118     int blocks_to_move = NumMoveSize(size) / 4;
 119     size_t psize = 0;
 120     do {
 121       psize += kPageSize;
 122       // Allocate enough pages so leftover is less than 1/8 of total.
 123       // This bounds wasted space to at most 12.5%.
 124       while ((psize % size) > (psize >> 3)) {
 125         psize += kPageSize;
 126       }
 127       // Continue to add pages until there are at least as many objects in
 128       // the span as are needed when moving objects from the central
 129       // freelists and spans to the thread caches.
 130     } while ((psize / size) < (blocks_to_move));
 131     const size_t my_pages = psize >> kPageShift;
 132
 133     if (sc > 1 && my_pages == class_to_pages_[sc-1]) {
 134       // See if we can merge this into the previous class without
 135       // increasing the fragmentation of the previous class.
 136       const size_t my_objects = (my_pages << kPageShift) / size;
 137       const size_t prev_objects = (class_to_pages_[sc-1] << kPageShift)
 138                                   / class_to_size_[sc-1];
 139       if (my_objects == prev_objects) {
 140         // Adjust last class to include this size
 141         class_to_size_[sc-1] = size;
 142         continue;
 143       }
 144     }
 145
 146     // Add new class
 147     class_to_pages_[sc] = my_pages;
 148     class_to_size_[sc] = size;
 149     sc++;
 150   }
 151   if (sc != kNumClasses) {
 152     Log(kCrash, __FILE__, __LINE__,
 153         "wrong number of size classes: (found vs. expected )", sc, kNumClasses);
 154   }
 155
 156   // Initialize the mapping arrays
 157   int next_size = 0;
 158   for (int c = 1; c < kNumClasses; c++) {
 159     const int max_size_in_class = class_to_size_[c];
 160     for (int s = next_size; s <= max_size_in_class; s += kAlignment) {
 161       class_array_[ClassIndex(s)] = c;
 162     }
 163     next_size = max_size_in_class + kAlignment;
 164   }
 165
 166   // Double-check sizes just to be safe
 167   for (size_t size = 0; size <= kMaxSize; size++) {
 168     const int sc = SizeClass(size);
 169     if (sc <= 0 || sc >= kNumClasses) {
 170       Log(kCrash, __FILE__, __LINE__,
 171           "Bad size class (class, size)", sc, size);
 172     }
 173     if (sc > 1 && size <= class_to_size_[sc-1]) {
 174       Log(kCrash, __FILE__, __LINE__,
 175           "Allocating unnecessarily large class (class, size)", sc, size);
 176     }
 177     const size_t s = class_to_size_[sc];
 178     if (size > s || s == 0) {
 179       Log(kCrash, __FILE__, __LINE__,
 180           "Bad (class, size, requested)", sc, s, size);
 181     }
 182   }
 183
 184   // Initialize the num_objects_to_move array.
 185   for (size_t cl = 1; cl  < kNumClasses; ++cl) {
 186     num_objects_to_move_[cl] = NumMoveSize(ByteSizeForClass(cl));
 187   }
 188 }
 189
 190 // Metadata allocator -- keeps stats about how many bytes allocated.
 191 static uint64_t metadata_system_bytes_ = 0;
 192 void* MetaDataAlloc(size_t bytes) {
 193   void* result = TCMalloc_SystemAlloc(bytes, NULL);
 194   if (result != NULL) {
 195     metadata_system_bytes_ += bytes;
 196   }
 197   return result;
 198 }
 199
 200 uint64_t metadata_system_bytes() { return metadata_system_bytes_; }
 201
 202 }  // namespace tcmalloc