1 void OutOfMemoryPanic();
2
3 void *SysAllocRaw(size_t size, size_t reqsize);
4 void SysFreeRaw(void *ptr, size_t size);
5
6 const char *asString(int i);
7 const char *asString(void *ptr);
8
9 struct Heap;
10
11 // This is used internally by U++ to manage large (64KB) and huge (up to 256MB) blocks
12
13 struct BlkPrefix { // this part is at the start of Blk allocated block, client must not touch it
14 word prev_size;
15 word size;
16 bool free;
17 bool last;
18 Heap *heap; // we need this for 4KB pages and large blocks, NULL for Huge blocks
19 #ifdef CPU_32
20 dword filler;
21 #endif
22
SetSizeBlkPrefix23 void SetSize(word sz) { size = sz; }
SetPrevSizeBlkPrefix24 void SetPrevSize(word sz) { prev_size = sz; }
SetFreeBlkPrefix25 void SetFree(bool b) { free = b; }
SetLastBlkPrefix26 void SetLast(bool b) { last = b; }
27
GetSizeBlkPrefix28 word GetSize() { return size; }
GetPrevSizeBlkPrefix29 word GetPrevSize() { return prev_size; }
IsFirstBlkPrefix30 bool IsFirst() { return GetPrevSize() == 0; }
IsFreeBlkPrefix31 bool IsFree() { return free; }
IsLastBlkPrefix32 bool IsLast() { return last; }
33
GetPrevHeaderBlkPrefix34 BlkPrefix *GetPrevHeader(int BlkSize) { return (BlkPrefix *)((byte *)this - BlkSize * GetPrevSize()); }
GetNextHeaderBlkPrefix35 BlkPrefix *GetNextHeader(int BlkSize) { return (BlkPrefix *)((byte *)this + BlkSize * GetSize()); }
36 };
37
38 template <int BlkSize>
39 struct BlkHeader_ : BlkPrefix { // free block record
40 BlkHeader_ *prev; // linked list of free blocks
41 BlkHeader_ *next; // linked list of free blocks
42
GetPrevHeaderBlkHeader_43 BlkHeader_ *GetPrevHeader() { return (BlkHeader_ *)BlkPrefix::GetPrevHeader(BlkSize); }
GetNextHeaderBlkHeader_44 BlkHeader_ *GetNextHeader() { return (BlkHeader_ *)BlkPrefix::GetNextHeader(BlkSize); }
45
SetNextPrevSzBlkHeader_46 void SetNextPrevSz() { if(!IsLast()) GetNextHeader()->SetPrevSize(GetSize()); }
47
UnlinkFreeBlkHeader_48 void UnlinkFree() { Dbl_Unlink(this); }
49 };
50
51 template <typename Detail, int BlkSize>
52 struct BlkHeap : Detail {
53 typedef BlkHeader_<BlkSize> BlkHeader;
54 typedef Detail D;
55
56 bool JoinNext(BlkHeader *h, word needs_count = 0);
57 void Split(BlkHeader *h, word wcount, bool fill = false);
58 void AddChunk(BlkHeader *h, int count);
59 void *MakeAlloc(BlkHeader *h, word wcount);
60 BlkHeader *Free(BlkHeader *h); // returns final joined block
61 bool TryRealloc(void *ptr, size_t count, size_t& n);
62 void BlkCheck(void *page, int size, bool check_heap = false);
63
64 static void Assert(bool b);
65 #ifdef HEAPDBG
66 static void DbgFreeFill(void *ptr, size_t size);
67 static void DbgFreeCheck(void *ptr, size_t size);
68 static void FillFree(BlkHeader *h);
69 static void CheckFree(BlkHeader *h);
70 #else
DbgFreeFillBlkHeap71 static void DbgFreeFill(void *ptr, size_t size) {}
DbgFreeCheckBlkHeap72 static void DbgFreeCheck(void *ptr, size_t size) {}
FillFreeBlkHeap73 static void FillFree(BlkHeader *h) {}
CheckFreeBlkHeap74 static void CheckFree(BlkHeader *h) {}
75 #endif
76 };
77
78 template <typename Detail, int BlkSize>
Assert(bool b)79 void BlkHeap<Detail, BlkSize>::Assert(bool b)
80 {
81 if(!b)
82 Panic("Heap is corrupted!");
83 }
84
85 #ifdef HEAPDBG
86
87 template <typename Detail, int BlkSize>
DbgFreeFill(void * p,size_t size)88 void BlkHeap<Detail, BlkSize>::DbgFreeFill(void *p, size_t size)
89 {
90 size_t count = size >> 2;
91 dword *ptr = (dword *)p;
92 while(count--)
93 *ptr++ = 0x65657246;
94 }
95
96 template <typename Detail, int BlkSize>
DbgFreeCheck(void * p,size_t size)97 void BlkHeap<Detail, BlkSize>::DbgFreeCheck(void *p, size_t size)
98 {
99 size_t count = size >> 2;
100 dword *ptr = (dword *)p;
101 while(count--)
102 if(*ptr++ != 0x65657246)
103 Panic("Writes to freed blocks detected");
104 }
105
106 template <typename Detail, int BlkSize>
FillFree(BlkHeader * h)107 void BlkHeap<Detail, BlkSize>::FillFree(BlkHeader *h)
108 {
109 if(BlkSize == 4096) // it is too slow to check huge blocks
110 return;
111 DbgFreeFill(h + 1, h->GetSize() * BlkSize - sizeof(BlkHeader));
112 }
113
114 template <typename Detail, int BlkSize>
CheckFree(BlkHeader * h)115 void BlkHeap<Detail, BlkSize>::CheckFree(BlkHeader *h)
116 {
117 if(BlkSize == 4096) // it is too slow to check huge blocks
118 return;
119 DbgFreeCheck(h + 1, h->GetSize() * BlkSize - sizeof(BlkHeader));
120 }
121
122 #endif
123
124 template <typename Detail, int BlkSize>
BlkCheck(void * page,int page_size,bool check_heap)125 void BlkHeap<Detail, BlkSize>::BlkCheck(void *page, int page_size, bool check_heap)
126 {
127 #define CLOG(x) // LOG(x)
128 CLOG("=== " << asString(page_size) << " " << AsString(page));
129 BlkPrefix *h = (BlkPrefix *)page;
130 int size = 0;
131 int psize = 0;
132 Assert(h->IsFirst());
133 for(;;) {
134 size += h->GetSize();
135 CLOG("h: " << AsString(h) << ", GetSize: " << asString(h->GetSize())
136 << ", size: " << asString(size) << ", islast: " << asString(h->IsLast()));
137 Assert(h->GetSize());
138 Assert(h->GetPrevSize() == psize);
139 Assert(!check_heap || h->IsFree() || h->heap);
140 if(h->IsFree())
141 CheckFree((BlkHeader *)h);
142 psize = h->GetSize();
143 if(h->IsLast() && size == page_size)
144 return;
145 Assert(size < page_size);
146 h = h->GetNextHeader(BlkSize);
147 }
148 #undef CLOG
149 }
150
151 template <typename Detail, int BlkSize>
152 force_inline
JoinNext(BlkHeader * h,word needs_count)153 bool BlkHeap<Detail, BlkSize>::JoinNext(BlkHeader *h, word needs_count)
154 { // try to join with next header if it is free, does not link it to free
155 if(h->IsLast())
156 return false;
157 BlkHeader *nh = h->GetNextHeader();
158 if(!nh->IsFree() || h->GetSize() + nh->GetSize() < needs_count)
159 return false;
160 CheckFree(nh);
161 h->SetLast(nh->IsLast());
162 nh->UnlinkFree();
163 word nsz = h->GetSize() + nh->GetSize();
164 h->SetSize(nsz);
165 h->SetNextPrevSz();
166 return true;
167 }
168
169 template <typename Detail, int BlkSize>
170 force_inline
Split(BlkHeader * h,word wcount,bool fill)171 void BlkHeap<Detail, BlkSize>::Split(BlkHeader *h, word wcount, bool fill)
172 { // splits the block if bigger, links new block to free
173 ASSERT(BlkSize != 4096 || ((dword)(uintptr_t)h & 4095) == 0);
174 BlkHeader *h2 = (BlkHeader *)((byte *)h + BlkSize * (int)wcount);
175 word nsz = h->GetSize() - wcount;
176 if(nsz == 0) // nothing to split
177 return;
178
179 h2->SetFree(true);
180 h2->SetLast(h->IsLast());
181 h2->SetSize(nsz);
182 h2->SetPrevSize(wcount);
183 h2->SetNextPrevSz();
184 D::LinkFree(h2);
185 if(fill)
186 FillFree(h2);
187
188 h->SetSize(wcount);
189 h->SetLast(false);
190 }
191
192 template <typename Detail, int BlkSize>
AddChunk(BlkHeader * h,int count)193 void BlkHeap<Detail, BlkSize>::AddChunk(BlkHeader *h, int count)
194 {
195 h->SetSize(count);
196 h->SetPrevSize(0); // is first
197 h->SetLast(true);
198 h->SetFree(true);
199 D::LinkFree(h);
200 FillFree(h);
201 }
202
203 template <typename Detail, int BlkSize>
204 force_inline
MakeAlloc(BlkHeader * h,word wcount)205 void *BlkHeap<Detail, BlkSize>::MakeAlloc(BlkHeader *h, word wcount)
206 {
207 h->UnlinkFree();
208 h->SetFree(false);
209 Split(h, wcount);
210 CheckFree(h);
211 return h;
212 }
213
214 template <typename Detail, int BlkSize>
TryRealloc(void * ptr,size_t count,size_t & n)215 bool BlkHeap<Detail, BlkSize>::TryRealloc(void *ptr, size_t count, size_t& n)
216 {
217 ASSERT(count);
218
219 BlkHeader *h = (BlkHeader *)ptr;
220 if(h->size == 0)
221 return false;
222
223 word sz = h->GetSize();
224 if(sz != count) {
225 if(!JoinNext(h, (word)count) && count > sz)
226 return false;
227 Split(h, (word)count, true);
228 n = n - sz + count;
229 }
230 return true;
231 }
232
233 template <typename Detail, int BlkSize>
234 force_inline
Free(BlkHeader * h)235 typename BlkHeap<Detail, BlkSize>::BlkHeader *BlkHeap<Detail, BlkSize>::Free(BlkHeader *h)
236 {
237 ASSERT(BlkSize != 4096 || ((dword)(uintptr_t)h & 4095) == 0);
238 JoinNext(h);
239 if(!h->IsFirst()) { // try to join with previous header if it is free
240 BlkHeader *ph = h->GetPrevHeader();
241 if(ph->IsFree()) {
242 ph->UnlinkFree(); // remove because size will change, might end in another bucket then
243 word nsz = ph->GetSize() + h->GetSize();
244 ph->SetSize(nsz);
245 ph->SetLast(h->IsLast());
246 ph->SetNextPrevSz();
247 h = ph;
248 }
249 }
250 h->SetFree(true);
251 D::LinkFree(h); // was not joined with previous header
252 FillFree(h);
253 return h;
254 }
255
256 struct HugeHeapDetail {
257 static BlkHeader_<4096> freelist[20][1];
258
CvHugeHeapDetail259 static int Cv(int n) { return n < 16 ? 0 : SignificantBits(n - 16) + 1; }
LinkFreeHugeHeapDetail260 static void LinkFree(BlkHeader_<4096> *h) { Dbl_LinkAfter(h, freelist[Cv(h->GetSize())]); }
NewFreeSizeHugeHeapDetail261 static void NewFreeSize(BlkHeader_<4096> *h) {}
262 };
263
264 struct Heap : BlkHeap<HugeHeapDetail, 4096> {
265 enum {
266 LUNIT = 256, // granularity of large blocks (size always a multiple of this)
267 LPAGE = 255, // number of LUNITs in large page (need to fix freelist and lclass if changing)
268 LOFFSET = 64, // offset from 64KB start to the first block header
269
270 NKLASS = 23, // number of small size classes
271
272 REMOTE_OUT_SZ = 2000, // maximum size of remote frees to be buffered to flush at once
273 };
274
275 // allocator options:
276 static word HPAGE; // size of master page, in 4KB units
277 static int max_free_hpages; // maximum free master pages kept in reserve (if more, they are returned to the system)
278 static int max_free_lpages; // maximum free large pages kept in reserve (if more, they are returned to huge system)
279 static int max_free_spages; // maximum free small pages kept in reserve (but HugeAlloc also converts them)
280 static word sys_block_limit; // > this (in 4KB) blocks are managed directly by system
281
282 void *HugeAlloc(size_t count); // count in 4KB, client needs to not touch HugePrefix
283 int HugeFree(void *ptr);
284 bool HugeTryRealloc(void *ptr, size_t count);
285
KszHeap286 static int Ksz(int k) { // small block size classes
287 static int sz[] = {
288 // 0 1 2 3 4 5 6 7 8 9 10 11
289 32, 64, 96, 128, 160, 192, 224, 256, 288, 320, 352, 384,
290 448, 576, 672, 800, 992, 8, 16, 24, 40, 48, 56
291 // 12 13 14 15 16 17 18 19 20 21 22
292 // 8 - 56 sizes are only available with TinyAlloc
293 };
294 static_assert(__countof(sz) == 23, "NKLASS mismatch");
295 return sz[k];
296 }
297
298 struct FreeLink {
299 FreeLink *next;
300 };
301
302 struct Page : BlkPrefix { // small block Page
303 byte klass; // size class
304 word active; // number of used (active) blocks in this page
305 FreeLink *freelist; // single linked list of free blocks in Page
306 Page *next; // Pages are in work/full/empty lists
307 Page *prev;
308
LinkSelfHeap::Page309 void LinkSelf() { Dbl_Self(this); }
UnlinkHeap::Page310 void Unlink() { Dbl_Unlink(this); }
LinkHeap::Page311 void Link(Page *lnk) { Dbl_LinkAfter(this, lnk); }
312
313 void Format(int k);
314
BeginHeap::Page315 byte *Begin() { return (byte *)this + sizeof(Page); }
EndHeap::Page316 byte *End() { return (byte *)this + 4096; }
CountHeap::Page317 int Count() { return (int)(uintptr_t)(End() - Begin()) / Ksz(klass); }
318 };
319
320 struct LargeHeapDetail {
321 BlkHeader_<LUNIT> freelist[25][1];
322 void LinkFree(BlkHeader_<LUNIT> *h);
323 };
324
325 struct LargeHeap : BlkHeap<LargeHeapDetail, LUNIT> {};
326
327 typedef LargeHeap::BlkHeader LBlkHeader;
328
329 struct DLink : BlkPrefix { // Large Page header / big block header
330 DLink *next;
331 DLink *prev;
332 size_t size; // only used for big header
333 #ifdef CPU_64
334 dword filler[6]; // sizeof need to be 64 because of alignment
335 #else
336 dword filler[9];
337 #endif
338
LinkSelfHeap::DLink339 void LinkSelf() { Dbl_Self(this); }
UnlinkHeap::DLink340 void Unlink() { Dbl_Unlink(this); }
LinkHeap::DLink341 void Link(DLink *lnk) { Dbl_LinkAfter(this, lnk); }
342
GetFirstHeap::DLink343 LargeHeap::BlkHeader *GetFirst() { return (LargeHeap::BlkHeader *)((byte *)this + LOFFSET); } // pointer to data area
344 };
345
346 static int lclass[];
347 static int free_lclass[LPAGE + 1];
348 static int alloc_lclass[LPAGE + 1];
349
350 static_assert(sizeof(BlkPrefix) == 16, "Wrong sizeof(BlkPrefix)");
351 static_assert(sizeof(DLink) == 64, "Wrong sizeof(DLink)");
352
353 static StaticMutex mutex;
354
355 Page work[NKLASS][1]; // circular list of pages that contain some empty blocks
356 Page full[NKLASS][1]; // circular list of pages that contain NO empty blocks
357 Page *empty[NKLASS]; // last fully freed page per klass (hot reserve) / shared global list of empty pages in aux
358 FreeLink *cache[NKLASS]; // hot frontend cache of small blocks
359 int cachen[NKLASS]; // counter of small blocks that are allowed to be stored in cache
360
361 bool initialized;
362
363 LargeHeap lheap;
364 DLink large[1]; // all large 64KB chunks that belong to this heap
365 int free_lpages; // empty large pages (in reserve)
366
367 void *out[REMOTE_OUT_SZ / 8 + 1];
368 void **out_ptr;
369 int out_size;
370
371 byte filler1[64]; // make sure the next variable is in distinct cacheline
372
373 FreeLink *small_remote_list; // list of remotely freed small blocks for lazy reclamation
374 FreeLink *large_remote_list; // list of remotely freed large blocks for lazy reclamation
375
376 struct HugePage { // to store the list of all huge pages in permanent storage
377 void *page;
378 HugePage *next;
379 };
380
381 static HugePage *huge_pages;
382
383 static DLink big[1]; // List of all big blocks
384 static Heap aux; // Single global auxiliary heap to store orphans and global list of free pages
385
386 static size_t huge_4KB_count; // total number of 4KB pages in small/large/huge blocks
387 static int free_4KB; // number of empty 4KB pages (linked in aux.empty)
388 static size_t big_size; // blocks >~64KB
389 static size_t big_count;
390 static size_t sys_size; // blocks allocated directly from system (included in big too)
391 static size_t sys_count;
392 static size_t huge_chunks; // 32MB master pages
393 static size_t huge_4KB_count_max; // peak huge memory allocated
394 static HugePage *free_huge_pages; // list of records of freed hpages (to be reused)
395 static int free_hpages; // empty huge pages (in reserve)
396
397 #ifdef HEAPDBG
398 static void DbgFreeFillK(void *ptr, int k);
399 static void *DbgFreeCheckK(void *p, int k);
400 #else
DbgFreeFillKHeap401 static void DbgFreeFillK(void *ptr, int k) {}
DbgFreeCheckKHeap402 static void *DbgFreeCheckK(void *p, int k) { return p; }
403 #endif
404
405 #ifdef flagHEAPSTAT
406 static void Stat(size_t sz);
407 #else
StatHeap408 static void Stat(size_t sz) {}
409 #endif
410
411 void Init();
412
413 static int CheckFree(FreeLink *l, int k);
414 void Check();
415 static void DblCheck(Page *p);
416 static void AssertLeaks(bool b);
417
IsSmallHeap418 static bool IsSmall(void *ptr) { return (((dword)(uintptr_t)ptr) & 16) == 0; }
GetPageHeap419 static Page *GetPage(void *ptr) { return (Page *)((uintptr_t)ptr & ~(uintptr_t)4095); }
420
421 Page *WorkPage(int k);
422 void *AllocK(int k);
423 void FreeK(void *ptr, Page *page, int k);
424 void *Allok(int k);
425 void Free(void *ptr, Page *page, int k);
426 void Free(void *ptr, int k);
427 void Free4KB(int k, Page *page);
428
429 static bool FreeSmallEmpty(int size4KB, int count = INT_MAX);
430
431 void LInit();
432 void *TryLAlloc(int i0, word wcount);
433 void *LAlloc(size_t& size);
434 void FreeLargePage(DLink *l);
435 void LFree(void *ptr);
436 bool LTryRealloc(void *ptr, size_t& newsize);
437 size_t LGetBlockSize(void *ptr);
438
439 void Make(MemoryProfile& f);
440 void DumpLarge();
441 void DumpHuge();
442
443 static void Shrink();
444
445 void SmallFreeDirect(void *ptr);
446
447 void RemoteFlushRaw();
448 void RemoteFlush();
449 void RemoteFree(void *ptr, int size);
450 void SmallFreeRemoteRaw(FreeLink *list);
SmallFreeRemoteRawHeap451 void SmallFreeRemoteRaw() { SmallFreeRemoteRaw(small_remote_list); small_remote_list = NULL; }
452 void SmallFreeRemote();
453 void LargeFreeRemoteRaw(FreeLink *list);
LargeFreeRemoteRawHeap454 void LargeFreeRemoteRaw() { LargeFreeRemoteRaw(large_remote_list); large_remote_list = NULL; }
455 void LargeFreeRemote();
456 void FreeRemoteRaw();
457 static void MoveLargeTo(DLink *ml, Heap *to_heap);
458 void MoveLargeTo(Heap *to_heap);
459
460 void Shutdown();
461 static void AuxFinalCheck();
462
463 void *AllocSz(size_t& sz);
464 void Free(void *ptr);
465 size_t GetBlockSize(void *ptr);
466 void *Alloc32();
467 void Free32(void *ptr);
468 void *Alloc48();
469 void Free48(void *ptr);
470
471 bool TryRealloc(void *ptr, size_t& newsize);
472 };
473
474 force_inline
RemoteFlushRaw()475 void Heap::RemoteFlushRaw()
476 { // transfer all buffered freed remote blocks to target heaps, no locking
477 if(!initialized)
478 Init();
479 for(void **o = out; o < out_ptr; o++) {
480 FreeLink *f = (FreeLink *)*o;
481 Heap *heap = GetPage(f)->heap;
482 f->next = heap->small_remote_list;
483 heap->small_remote_list = f;
484 }
485 out_ptr = out;
486 out_size = 0;
487 }
488
489 force_inline
RemoteFree(void * ptr,int size)490 void Heap::RemoteFree(void *ptr, int size)
491 { // buffer freed remote block until REMOTE_OUT_SZ is reached
492 if(!initialized)
493 Init();
494 ASSERT(out_ptr <= out + REMOTE_OUT_SZ / 8 + 1);
495 *out_ptr++ = ptr;
496 out_size += size;
497 if(out_size >= REMOTE_OUT_SZ) {
498 Mutex::Lock __(mutex);
499 RemoteFlushRaw();
500 }
501 }
502
503 force_inline
SmallFreeRemoteRaw(FreeLink * list)504 void Heap::SmallFreeRemoteRaw(FreeLink *list)
505 {
506 while(list) {
507 FreeLink *f = list;
508 list = list->next;
509 SmallFreeDirect(f);
510 }
511 }
512
513 force_inline
SmallFreeRemote()514 void Heap::SmallFreeRemote()
515 {
516 while(small_remote_list) { // avoid mutex if likely nothing to free
517 FreeLink *list;
518 { // only pick values in mutex, resolve later
519 Mutex::Lock __(mutex);
520 list = small_remote_list;
521 small_remote_list = NULL;
522 }
523 SmallFreeRemoteRaw(list);
524 }
525 }
526
527 force_inline
LargeFreeRemoteRaw(FreeLink * list)528 void Heap::LargeFreeRemoteRaw(FreeLink *list)
529 {
530 while(list) {
531 FreeLink *f = list;
532 list = list->next;
533 LFree(f);
534 }
535 }
536
537 force_inline
LargeFreeRemote()538 void Heap::LargeFreeRemote()
539 {
540 while(large_remote_list) { // avoid mutex if likely nothing to free
541 FreeLink *list;
542 { // only pick values in mutex, resolve later
543 Mutex::Lock __(mutex);
544 list = large_remote_list;
545 large_remote_list = NULL;
546 }
547 LargeFreeRemoteRaw(list);
548 }
549 }
550