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