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 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
51 n = x; | 51 n = x; |
52 log += shift; | 52 log += shift; |
53 } | 53 } |
54 } | 54 } |
55 ASSERT(n == 1); | 55 ASSERT(n == 1); |
56 return log; | 56 return log; |
57 } | 57 } |
58 | 58 |
59 int AlignmentForSize(size_t size) { | 59 int AlignmentForSize(size_t size) { |
60 int alignment = kAlignment; | 60 int alignment = kAlignment; |
61 if (size > kMaxSize) { | 61 if (size >= 2048) { |
62 // Cap alignment at kPageSize for large sizes. | 62 // Cap alignment at 256 for large sizes. |
63 alignment = kPageSize; | 63 alignment = 256; |
64 } else if (size >= 128) { | 64 } else if (size >= 128) { |
65 // Space wasted due to alignment is at most 1/8, i.e., 12.5%. | 65 // Space wasted due to alignment is at most 1/8, i.e., 12.5%. |
66 alignment = (1 << LgFloor(size)) / 8; | 66 alignment = (1 << LgFloor(size)) / 8; |
67 } else if (size >= 16) { | 67 } else if (size >= 16) { |
68 // We need an alignment of at least 16 bytes to satisfy | 68 // We need an alignment of at least 16 bytes to satisfy |
69 // requirements for some SSE types. | 69 // requirements for some SSE types. |
70 alignment = 16; | 70 alignment = 16; |
71 } | 71 } |
72 // Maximum alignment allowed is page size alignment. | |
73 if (alignment > kPageSize) { | |
74 alignment = kPageSize; | |
75 } | |
76 CHECK_CONDITION(size < 16 || alignment >= 16); | 72 CHECK_CONDITION(size < 16 || alignment >= 16); |
77 CHECK_CONDITION((alignment & (alignment - 1)) == 0); | 73 CHECK_CONDITION((alignment & (alignment - 1)) == 0); |
78 return alignment; | 74 return alignment; |
79 } | 75 } |
80 | 76 |
81 int SizeMap::NumMoveSize(size_t size) { | 77 int SizeMap::NumMoveSize(size_t size) { |
82 if (size == 0) return 0; | 78 if (size == 0) return 0; |
83 // Use approx 64k transfers between thread and central caches. | 79 // Use approx 64k transfers between thread and central caches. |
84 int num = static_cast<int>(64.0 * 1024.0 / size); | 80 int num = static_cast<int>(64.0 * 1024.0 / size); |
85 if (num < 2) num = 2; | 81 if (num < 2) num = 2; |
(...skipping 10 matching lines...) Expand all Loading... |
96 // This value strikes a balance between the constraints above. | 92 // This value strikes a balance between the constraints above. |
97 if (num > 32) num = 32; | 93 if (num > 32) num = 32; |
98 | 94 |
99 return num; | 95 return num; |
100 } | 96 } |
101 | 97 |
102 // Initialize the mapping arrays | 98 // Initialize the mapping arrays |
103 void SizeMap::Init() { | 99 void SizeMap::Init() { |
104 // Do some sanity checking on add_amount[]/shift_amount[]/class_array[] | 100 // Do some sanity checking on add_amount[]/shift_amount[]/class_array[] |
105 if (ClassIndex(0) < 0) { | 101 if (ClassIndex(0) < 0) { |
106 Log(kCrash, __FILE__, __LINE__, | 102 CRASH("Invalid class index %d for size 0\n", ClassIndex(0)); |
107 "Invalid class index for size 0", ClassIndex(0)); | |
108 } | 103 } |
109 if (ClassIndex(kMaxSize) >= sizeof(class_array_)) { | 104 if (ClassIndex(kMaxSize) >= sizeof(class_array_)) { |
110 Log(kCrash, __FILE__, __LINE__, | 105 CRASH("Invalid class index %d for kMaxSize\n", ClassIndex(kMaxSize)); |
111 "Invalid class index for kMaxSize", ClassIndex(kMaxSize)); | |
112 } | 106 } |
113 | 107 |
114 // Compute the size classes we want to use | 108 // Compute the size classes we want to use |
115 int sc = 1; // Next size class to assign | 109 int sc = 1; // Next size class to assign |
116 int alignment = kAlignment; | 110 int alignment = kAlignment; |
117 CHECK_CONDITION(kAlignment <= 16); | 111 CHECK_CONDITION(kAlignment <= 16); |
| 112 int last_lg = -1; |
118 for (size_t size = kMinClassSize; size <= kMaxSize; size += alignment) { | 113 for (size_t size = kMinClassSize; size <= kMaxSize; size += alignment) { |
119 alignment = AlignmentForSize(size); | 114 int lg = LgFloor(size); |
| 115 if (lg > last_lg) { |
| 116 // Increase alignment every so often to reduce number of size classes. |
| 117 alignment = AlignmentForSize(size); |
| 118 last_lg = lg; |
| 119 } |
120 CHECK_CONDITION((size % alignment) == 0); | 120 CHECK_CONDITION((size % alignment) == 0); |
121 | 121 |
122 int blocks_to_move = NumMoveSize(size) / 4; | 122 // Allocate enough pages so leftover is less than 1/8 of total. |
123 size_t psize = 0; | 123 // This bounds wasted space to at most 12.5%. |
124 do { | 124 size_t psize = kPageSize; |
| 125 while ((psize % size) > (psize >> 3)) { |
125 psize += kPageSize; | 126 psize += kPageSize; |
126 // Allocate enough pages so leftover is less than 1/8 of total. | 127 } |
127 // This bounds wasted space to at most 12.5%. | |
128 while ((psize % size) > (psize >> 3)) { | |
129 psize += kPageSize; | |
130 } | |
131 // Continue to add pages until there are at least as many objects in | |
132 // the span as are needed when moving objects from the central | |
133 // freelists and spans to the thread caches. | |
134 } while ((psize / size) < (blocks_to_move)); | |
135 const size_t my_pages = psize >> kPageShift; | 128 const size_t my_pages = psize >> kPageShift; |
136 | 129 |
137 if (sc > 1 && my_pages == class_to_pages_[sc-1]) { | 130 if (sc > 1 && my_pages == class_to_pages_[sc-1]) { |
138 // See if we can merge this into the previous class without | 131 // See if we can merge this into the previous class without |
139 // increasing the fragmentation of the previous class. | 132 // increasing the fragmentation of the previous class. |
140 const size_t my_objects = (my_pages << kPageShift) / size; | 133 const size_t my_objects = (my_pages << kPageShift) / size; |
141 const size_t prev_objects = (class_to_pages_[sc-1] << kPageShift) | 134 const size_t prev_objects = (class_to_pages_[sc-1] << kPageShift) |
142 / class_to_size_[sc-1]; | 135 / class_to_size_[sc-1]; |
143 if (my_objects == prev_objects) { | 136 if (my_objects == prev_objects) { |
144 // Adjust last class to include this size | 137 // Adjust last class to include this size |
145 class_to_size_[sc-1] = size; | 138 class_to_size_[sc-1] = size; |
146 continue; | 139 continue; |
147 } | 140 } |
148 } | 141 } |
149 | 142 |
150 // Add new class | 143 // Add new class |
151 class_to_pages_[sc] = my_pages; | 144 class_to_pages_[sc] = my_pages; |
152 class_to_size_[sc] = size; | 145 class_to_size_[sc] = size; |
153 sc++; | 146 sc++; |
154 } | 147 } |
155 if (sc != kNumClasses) { | 148 if (sc != kNumClasses) { |
156 Log(kCrash, __FILE__, __LINE__, | 149 CRASH("wrong number of size classes: found %d instead of %d\n", |
157 "wrong number of size classes: (found vs. expected )", sc, kNumClasses); | 150 sc, int(kNumClasses)); |
158 } | 151 } |
159 | 152 |
160 // Initialize the mapping arrays | 153 // Initialize the mapping arrays |
161 int next_size = 0; | 154 int next_size = 0; |
162 for (int c = 1; c < kNumClasses; c++) { | 155 for (int c = 1; c < kNumClasses; c++) { |
163 const int max_size_in_class = class_to_size_[c]; | 156 const int max_size_in_class = class_to_size_[c]; |
164 for (int s = next_size; s <= max_size_in_class; s += kAlignment) { | 157 for (int s = next_size; s <= max_size_in_class; s += kAlignment) { |
165 class_array_[ClassIndex(s)] = c; | 158 class_array_[ClassIndex(s)] = c; |
166 } | 159 } |
167 next_size = max_size_in_class + kAlignment; | 160 next_size = max_size_in_class + kAlignment; |
168 } | 161 } |
169 | 162 |
170 // Double-check sizes just to be safe | 163 // Double-check sizes just to be safe |
171 for (size_t size = 0; size <= kMaxSize; size++) { | 164 for (size_t size = 0; size <= kMaxSize; size++) { |
172 const int sc = SizeClass(size); | 165 const int sc = SizeClass(size); |
173 if (sc <= 0 || sc >= kNumClasses) { | 166 if (sc <= 0 || sc >= kNumClasses) { |
174 Log(kCrash, __FILE__, __LINE__, | 167 CRASH("Bad size class %d for %" PRIuS "\n", sc, size); |
175 "Bad size class (class, size)", sc, size); | |
176 } | 168 } |
177 if (sc > 1 && size <= class_to_size_[sc-1]) { | 169 if (sc > 1 && size <= class_to_size_[sc-1]) { |
178 Log(kCrash, __FILE__, __LINE__, | 170 CRASH("Allocating unnecessarily large class %d for %" PRIuS |
179 "Allocating unnecessarily large class (class, size)", sc, size); | 171 "\n", sc, size); |
180 } | 172 } |
181 const size_t s = class_to_size_[sc]; | 173 const size_t s = class_to_size_[sc]; |
182 if (size > s || s == 0) { | 174 if (size > s) { |
183 Log(kCrash, __FILE__, __LINE__, | 175 CRASH("Bad size %" PRIuS " for %" PRIuS " (sc = %d)\n", s, size, sc); |
184 "Bad (class, size, requested)", sc, s, size); | 176 } |
| 177 if (s == 0) { |
| 178 CRASH("Bad size %" PRIuS " for %" PRIuS " (sc = %d)\n", s, size, sc); |
185 } | 179 } |
186 } | 180 } |
187 | 181 |
188 // Initialize the num_objects_to_move array. | 182 // Initialize the num_objects_to_move array. |
189 for (size_t cl = 1; cl < kNumClasses; ++cl) { | 183 for (size_t cl = 1; cl < kNumClasses; ++cl) { |
190 num_objects_to_move_[cl] = NumMoveSize(ByteSizeForClass(cl)); | 184 num_objects_to_move_[cl] = NumMoveSize(ByteSizeForClass(cl)); |
191 } | 185 } |
192 } | 186 } |
193 | 187 |
| 188 void SizeMap::Dump(TCMalloc_Printer* out) { |
| 189 // Dump class sizes and maximum external wastage per size class |
| 190 for (size_t cl = 1; cl < kNumClasses; ++cl) { |
| 191 const int alloc_size = class_to_pages_[cl] << kPageShift; |
| 192 const int alloc_objs = alloc_size / class_to_size_[cl]; |
| 193 const int min_used = (class_to_size_[cl-1] + 1) * alloc_objs; |
| 194 const int max_waste = alloc_size - min_used; |
| 195 out->printf("SC %3d [ %8d .. %8d ] from %8d ; %2.0f%% maxwaste\n", |
| 196 int(cl), |
| 197 int(class_to_size_[cl-1] + 1), |
| 198 int(class_to_size_[cl]), |
| 199 int(class_to_pages_[cl] << kPageShift), |
| 200 max_waste * 100.0 / alloc_size |
| 201 ); |
| 202 } |
| 203 } |
| 204 |
194 // Metadata allocator -- keeps stats about how many bytes allocated. | 205 // Metadata allocator -- keeps stats about how many bytes allocated. |
195 static uint64_t metadata_system_bytes_ = 0; | 206 static uint64_t metadata_system_bytes_ = 0; |
196 void* MetaDataAlloc(size_t bytes) { | 207 void* MetaDataAlloc(size_t bytes) { |
197 static size_t pagesize; | 208 static size_t pagesize; |
198 #ifdef HAVE_GETPAGESIZE | 209 #ifdef HAVE_GETPAGESIZE |
199 if (pagesize == 0) | 210 if (pagesize == 0) |
200 pagesize = getpagesize(); | 211 pagesize = getpagesize(); |
201 #endif | 212 #endif |
202 | 213 |
203 void* result = TCMalloc_SystemAlloc(bytes, NULL, pagesize); | 214 void* result = TCMalloc_SystemAlloc(bytes, NULL, pagesize); |
204 if (result != NULL) { | 215 if (result != NULL) { |
205 metadata_system_bytes_ += bytes; | 216 metadata_system_bytes_ += bytes; |
206 } | 217 } |
207 return result; | 218 return result; |
208 } | 219 } |
209 | 220 |
210 uint64_t metadata_system_bytes() { return metadata_system_bytes_; } | 221 uint64_t metadata_system_bytes() { return metadata_system_bytes_; } |
211 | 222 |
212 void increment_metadata_system_bytes(size_t bytes) { | 223 void increment_metadata_system_bytes(size_t bytes) { |
213 metadata_system_bytes_ += bytes; | 224 metadata_system_bytes_ += bytes; |
214 } | 225 } |
215 | 226 |
216 } // namespace tcmalloc | 227 } // namespace tcmalloc |
OLD | NEW |