1 #include "Core.h"
2
3 #define LTIMING(x) // RTIMING(x)
4 #define LHITCOUNT(x) // RHITCOUNT(x)
5 #define LLOG(x) // LOG((void *)this << ' ' << x)
6
7 namespace Upp {
8
9 #ifdef UPP_HEAP
10
11 #include "HeapImp.h"
12
13 int Heap::lclass[] = { 0, 4, 5, 6, 7, 8, 9, 11, 13, 15, 18, 22, 27, 33, 40, 49, 60, 73, 89, 109, 134, 164, 201, 225, 255 };
14 int Heap::free_lclass[LPAGE + 1]; // free block size -> lclass, size is >= class sz
15 int Heap::alloc_lclass[LPAGE + 1]; // allocation size -> lclass, size <= class sz
16
17
LinkFree(BlkHeader_<LUNIT> * h)18 void Heap::LargeHeapDetail::LinkFree(BlkHeader_<LUNIT> *h)
19 {
20 Dbl_LinkAfter(h, freelist[free_lclass[h->GetSize()]]);
21 }
22
LInit()23 void Heap::LInit()
24 {
25 ASSERT(__countof(lheap.freelist) == __countof(lclass));
26 ONCELOCK {
27 int ai = 0;
28 int fi = 0;
29 for(int i = 0; i <= 255; i++) {
30 if(i > lclass[ai])
31 ai++;
32 if(i >= lclass[fi + 1])
33 fi++;
34 alloc_lclass[i] = ai;
35 free_lclass[i] = fi;
36 }
37 }
38 for(int i = 0; i <= __countof(lheap.freelist); i++)
39 Dbl_Self(lheap.freelist[i]);
40 big->LinkSelf();
41 }
42
TryLAlloc(int i0,word wcount)43 void *Heap::TryLAlloc(int i0, word wcount)
44 {
45 LTIMING("TryLAlloc");
46 for(int i = i0; i < __countof(lheap.freelist); i++) {
47 LBlkHeader *l = lheap.freelist[i];
48 LBlkHeader *h = l->next;
49 if(h != l) {
50 ASSERT(h->GetSize() >= wcount);
51 if(h->GetSize() == LPAGE && this != &aux) {
52 free_lpages--;
53 ASSERT(free_lpages >= 0);
54 }
55 lheap.MakeAlloc(h, wcount);
56 h->heap = this;
57 return (BlkPrefix *)h + 1;
58 }
59 LHITCOUNT("TryLAlloc 2");
60 }
61 return NULL;
62 }
63
64 #ifdef LSTAT
65 int stat[65536];
66
67 EXITBLOCK {
68 int cnt = 0;
69 for(int i = 0; i < 65536; i++) {
70 cnt += stat[i];
71 if(stat[i])
72 RLOG(i * 256 << ": " << stat[i] << " / " << cnt);
73 }
74 }
75 #endif
76
77 void *Heap::LAlloc(size_t& size)
78 {
79 if(!initialized)
80 Init();
81
82 if(size > LUNIT * LPAGE - sizeof(BlkPrefix)) { // big block allocation
83 LTIMING("Big alloc");
84 Mutex::Lock __(mutex);
85 size_t count = (size + sizeof(DLink) + sizeof(BlkPrefix) + 4095) >> 12;
86 DLink *d = (DLink *)HugeAlloc(count);
87 d->Link(big);
88 d->size = size = (count << 12) - sizeof(DLink) - sizeof(BlkPrefix);
89 BlkPrefix *h = (BlkPrefix *)(d + 1);
90 h->heap = NULL; // mark this as huge block
91 big_size += size;
92 big_count++;
93 LLOG("Big alloc " << size << ": " << h + 1);
94 return h + 1;
95 }
96
97 word wcount = word((size + sizeof(BlkPrefix) + LUNIT - 1) >> 8);
98
99 #ifdef LSTAT
100 stat[wcount]++;
101 #endif
102
103 LTIMING("LAlloc");
104
105 size = ((int)wcount * LUNIT) - sizeof(BlkPrefix);
106 int i0 = alloc_lclass[wcount];
107
108 if(large_remote_list) // there might be blocks of this heap freed in other threads
109 LargeFreeRemote(); // free them first
110
111 void *ptr = TryLAlloc(i0, wcount);
112 if(ptr)
113 return ptr;
114
115 Mutex::Lock __(mutex);
116 aux.LargeFreeRemoteRaw();
117 ptr = aux.TryLAlloc(i0, wcount);
118 if(ptr) { // found in aux, we need to move large page from aux to this heap
119 LLOG("Found in aux");
120 BlkPrefix *h = (BlkPrefix *)ptr - 1;
121 while(!h->IsFirst()) // find the start of large page to get page header
122 h = h->GetPrevHeader(LUNIT);
123 MoveLargeTo((DLink *)((byte *)h - LOFFSET), this);
124 return ptr;
125 }
126
127 LTIMING("Large More");
128 DLink *ml = (DLink *)HugeAlloc(((LPAGE + 1) * LUNIT) / 4096);
129 ml->Link(large);
130 LBlkHeader *h = ml->GetFirst();
131 lheap.AddChunk(h, LPAGE);
132 lheap.MakeAlloc(h, wcount);
133 h->heap = this;
134 return (BlkPrefix *)h + 1;
135 }
136
FreeLargePage(DLink * l)137 void Heap::FreeLargePage(DLink *l)
138 {
139 LLOG("Moving empty large " << (void *)l << " to global storage, lcount " << lcount);
140 l->Unlink();
141 Mutex::Lock __(mutex);
142 HugeFree(l);
143 }
144
LFree(void * ptr)145 void Heap::LFree(void *ptr)
146 {
147 BlkPrefix *h = (BlkPrefix *)ptr - 1;
148
149 if(h->heap == this) {
150 LTIMING("Large Free");
151 LBlkHeader *fh = lheap.Free((LBlkHeader *)h);
152 if(fh->GetSize() == LPAGE) {
153 if(free_lpages >= max_free_lpages || this == &aux) {
154 LTIMING("FreeLargePage");
155 fh->UnlinkFree();
156 FreeLargePage((DLink *)((byte *)fh - LOFFSET));
157 }
158 else
159 free_lpages++;
160 }
161 return;
162 }
163
164 Mutex::Lock __(mutex);
165 if(h->heap == NULL) { // this is big block
166 LTIMING("Big Free");
167 DLink *d = (DLink *)h - 1;
168 big_size -= d->size;
169 big_count--;
170 d->Unlink();
171 LLOG("Big free " << (void *) ptr << " size " << h->size);
172 HugeFree(d);
173 return;
174 }
175
176 LTIMING("Remote Free");
177 // this is remote heap
178 FreeLink *f = (FreeLink *)ptr;
179 f->next = h->heap->large_remote_list;
180 h->heap->large_remote_list = f;
181 }
182
TryRealloc(void * ptr,size_t & newsize)183 bool Heap::TryRealloc(void *ptr, size_t& newsize)
184 {
185 LTIMING("TryRealloc");
186 ASSERT(ptr);
187
188 #ifdef _DEBUG
189 if(IsSmall(ptr))
190 return false;
191 #endif
192
193 BlkPrefix *h = (BlkPrefix *)ptr - 1;
194
195 if(h->heap == this) {
196 if(newsize > LUNIT * LPAGE - sizeof(BlkPrefix))
197 return false;
198 word wcount = word(((newsize ? newsize : 1) + sizeof(BlkPrefix) + LUNIT - 1) >> 8);
199 size_t dummy = 0;
200 if(wcount == h->GetSize() || lheap.TryRealloc(h, wcount, dummy)) {
201 newsize = ((int)wcount * LUNIT) - sizeof(BlkPrefix);
202 LHITCOUNT("Large realloc true");
203 return true;
204 }
205 }
206
207 Mutex::Lock __(mutex);
208 if(h->heap == NULL) { // this is big block
209 LTIMING("Big realloc");
210
211 DLink *d = (DLink *)h - 1;
212
213 size_t count = (newsize + sizeof(DLink) + sizeof(BlkPrefix) + 4095) >> 12;
214
215 if(HugeTryRealloc(d, count)) {
216 big_size -= d->size;
217 d->size = newsize = (count << 12) - sizeof(DLink) - sizeof(BlkPrefix);
218 big_size += d->size;
219 return true;
220 }
221 }
222
223 return false;
224 }
225
LGetBlockSize(void * ptr)226 size_t Heap::LGetBlockSize(void *ptr) {
227 LBlkHeader *h = (LBlkHeader *)ptr - 1;
228
229 if(h->heap == NULL) { // huge block
230 Mutex::Lock __(mutex);
231 DLink *h = (DLink *)ptr - 1;
232 return h->size;
233 }
234
235 return h->GetSize();
236 }
237
238 #endif
239
240 }
241