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
37namespace 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.
41static 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
55int 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
77int 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
99void 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.
191static uint64_t metadata_system_bytes_ = 0;
192void* 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
200uint64_t metadata_system_bytes() { return metadata_system_bytes_; }
201
202}  // namespace tcmalloc
203