1 /*
2 * malloc
3 *
4 * Uses Quickfit (see SIGPLAN Notices October 1988)
5 * with allocator from Kernighan & Ritchie
6 *
7 * This is a placeholder.
8 */
9 #include "u.h"
10 #include "../port/lib.h"
11 #include "mem.h"
12 #include "dat.h"
13 #include "fns.h"
14
15 typedef double Align;
16 typedef union Header Header;
17 typedef struct Qlist Qlist;
18
19 union Header {
20 struct {
21 Header* next;
22 uint size;
23 } s;
24 Align al;
25 };
26
27 struct Qlist {
28 Lock lk;
29 Header* first;
30
31 uint nalloc;
32 };
33
34 enum {
35 Unitsz = sizeof(Header),
36 };
37
38 #define NUNITS(n) (HOWMANY(n, Unitsz) + 1)
39 #define NQUICK ((4096/Unitsz)+1)
40
41 static Qlist quicklist[NQUICK+1];
42 static Header misclist;
43 static Header *rover;
44 static unsigned tailsize;
45 static unsigned availnunits;
46 static Header *tailbase;
47 static Header *tailptr;
48 static Header checkval;
49 static int morecore(unsigned);
50
51 enum
52 {
53 QSmalign = 0,
54 QSmalignquick,
55 QSmalignrover,
56 QSmalignfront,
57 QSmalignback,
58 QSmaligntail,
59 QSmalignnottail,
60 QSmalloc,
61 QSmallocrover,
62 QSmalloctail,
63 QSfree,
64 QSfreetail,
65 QSfreequick,
66 QSfreenext,
67 QSfreeprev,
68 QSmax
69 };
70
71 static char* qstatstr[QSmax] = {
72 [QSmalign] "malign",
73 [QSmalignquick] "malignquick",
74 [QSmalignrover] "malignrover",
75 [QSmalignfront] "malignfront",
76 [QSmalignback] "malignback",
77 [QSmaligntail] "maligntail",
78 [QSmalignnottail] "malignnottail",
79 [QSmalloc] "malloc",
80 [QSmallocrover] "mallocrover",
81 [QSmalloctail] "malloctail",
82 [QSfree] "free",
83 [QSfreetail] "freetail",
84 [QSfreequick] "freequick",
85 [QSfreenext] "freenext",
86 [QSfreeprev] "freeprev",
87 };
88
89 static void* qmalloc(usize);
90 static void qfreeinternal(void*);
91 static int qstats[QSmax];
92
93 static Lock mainlock;
94
95 #define MLOCK ilock(&mainlock)
96 #define MUNLOCK iunlock(&mainlock)
97 #define QLOCK(l) ilock(l)
98 #define QUNLOCK(l) iunlock(l)
99
100 #define tailalloc(p, n) ((p)=tailptr, tailsize -= (n), tailptr+=(n),\
101 (p)->s.size=(n), (p)->s.next = &checkval)
102
103 #define ISPOWEROF2(x) (/*((x) != 0) && */!((x) & ((x)-1)))
104 #define ALIGNHDR(h, a) (Header*)((((uintptr)(h))+((a)-1)) & ~((a)-1))
105 #define ALIGNED(h, a) ((((uintptr)(h)) & (a-1)) == 0)
106
107 static void*
qmallocalign(usize nbytes,uintptr align,long offset,usize span)108 qmallocalign(usize nbytes, uintptr align, long offset, usize span)
109 {
110 Qlist *qlist;
111 uintptr aligned;
112 Header **pp, *p, *q, *r;
113 uint naligned, nunits, n;
114
115 if(nbytes == 0 || offset != 0 || span != 0)
116 return nil;
117
118 if(!ISPOWEROF2(align))
119 panic("qmallocalign");
120
121 if(align <= sizeof(Align))
122 return qmalloc(nbytes);
123
124 qstats[QSmalign]++;
125 nunits = NUNITS(nbytes);
126 if(nunits <= NQUICK){
127 /*
128 * Look for a conveniently aligned block
129 * on one of the quicklists.
130 */
131 qlist = &quicklist[nunits];
132 QLOCK(&qlist->lk);
133 pp = &qlist->first;
134 for(p = *pp; p != nil; p = p->s.next){
135 if(ALIGNED(p+1, align)){
136 *pp = p->s.next;
137 p->s.next = &checkval;
138 QUNLOCK(&qlist->lk);
139 qstats[QSmalignquick]++;
140 return p+1;
141 }
142 pp = &p->s.next;
143 }
144 QUNLOCK(&qlist->lk);
145 }
146
147 MLOCK;
148 if(nunits > tailsize) {
149 /* hard way */
150 if((q = rover) != nil){
151 do {
152 p = q->s.next;
153 if(p->s.size < nunits)
154 continue;
155 aligned = ALIGNED(p+1, align);
156 naligned = NUNITS(align)-1;
157 if(!aligned && p->s.size < nunits+naligned)
158 continue;
159
160 /*
161 * This block is big enough, remove it
162 * from the list.
163 */
164 q->s.next = p->s.next;
165 rover = q;
166 qstats[QSmalignrover]++;
167
168 /*
169 * Free any runt in front of the alignment.
170 */
171 if(!aligned){
172 r = p;
173 p = ALIGNHDR(p+1, align) - 1;
174 n = p - r;
175 p->s.size = r->s.size - n;
176
177 r->s.size = n;
178 r->s.next = &checkval;
179 qfreeinternal(r+1);
180 qstats[QSmalignfront]++;
181 }
182
183 /*
184 * Free any residue after the aligned block.
185 */
186 if(p->s.size > nunits){
187 r = p+nunits;
188 r->s.size = p->s.size - nunits;
189 r->s.next = &checkval;
190 qstats[QSmalignback]++;
191 qfreeinternal(r+1);
192
193 p->s.size = nunits;
194 }
195
196 p->s.next = &checkval;
197 MUNLOCK;
198 return p+1;
199 } while((q = p) != rover);
200 }
201 if((n = morecore(nunits)) == 0){
202 MUNLOCK;
203 return nil;
204 }
205 tailsize += n;
206 }
207
208 q = ALIGNHDR(tailptr+1, align);
209 if(q == tailptr+1){
210 tailalloc(p, nunits);
211 qstats[QSmaligntail]++;
212 }
213 else{
214 naligned = NUNITS(align)-1;
215 if(tailsize < nunits+naligned){
216 /*
217 * There are at least nunits,
218 * get enough for alignment.
219 */
220 if((n = morecore(naligned)) == 0){
221 MUNLOCK;
222 return nil;
223 }
224 tailsize += n;
225 }
226 /*
227 * Save the residue before the aligned allocation
228 * and free it after the tail pointer has been bumped
229 * for the main allocation.
230 */
231 n = q-tailptr - 1;
232 tailalloc(r, n);
233 tailalloc(p, nunits);
234 qstats[QSmalignnottail]++;
235 qfreeinternal(r+1);
236 }
237 MUNLOCK;
238
239 return p+1;
240 }
241
242 static void*
qmalloc(usize nbytes)243 qmalloc(usize nbytes)
244 {
245 Qlist *qlist;
246 Header *p, *q;
247 uint nunits, n;
248
249 ///* FIXME: (ignore for now)
250 if(nbytes == 0)
251 return nil;
252 //*/
253
254 qstats[QSmalloc]++;
255 nunits = NUNITS(nbytes);
256 if(nunits <= NQUICK){
257 qlist = &quicklist[nunits];
258 QLOCK(&qlist->lk);
259 if((p = qlist->first) != nil){
260 qlist->first = p->s.next;
261 qlist->nalloc++;
262 QUNLOCK(&qlist->lk);
263 p->s.next = &checkval;
264 return p+1;
265 }
266 QUNLOCK(&qlist->lk);
267 }
268
269 MLOCK;
270 if(nunits > tailsize) {
271 /* hard way */
272 if((q = rover) != nil){
273 do {
274 p = q->s.next;
275 if(p->s.size >= nunits) {
276 if(p->s.size > nunits) {
277 p->s.size -= nunits;
278 p += p->s.size;
279 p->s.size = nunits;
280 } else
281 q->s.next = p->s.next;
282 p->s.next = &checkval;
283 rover = q;
284 qstats[QSmallocrover]++;
285 MUNLOCK;
286 return p+1;
287 }
288 } while((q = p) != rover);
289 }
290 if((n = morecore(nunits)) == 0){
291 MUNLOCK;
292 return nil;
293 }
294 tailsize += n;
295 }
296 qstats[QSmalloctail]++;
297 tailalloc(p, nunits);
298 MUNLOCK;
299
300 return p+1;
301 }
302
303 static void
qfreeinternal(void * ap)304 qfreeinternal(void* ap)
305 {
306 Qlist *qlist;
307 Header *p, *q;
308 uint nunits;
309
310 if(ap == nil)
311 return;
312 qstats[QSfree]++;
313
314 p = (Header*)ap - 1;
315 if((nunits = p->s.size) == 0 || p->s.next != &checkval)
316 panic("malloc: corrupt allocation arena");
317 if(tailptr != nil && p+nunits == tailptr) {
318 /* block before tail */
319 tailptr = p;
320 tailsize += nunits;
321 qstats[QSfreetail]++;
322 return;
323 }
324 if(nunits <= NQUICK) {
325 qlist = &quicklist[nunits];
326 QLOCK(&qlist->lk);
327 p->s.next = qlist->first;
328 qlist->first = p;
329 QUNLOCK(&qlist->lk);
330 qstats[QSfreequick]++;
331 return;
332 }
333 if((q = rover) == nil) {
334 q = &misclist;
335 q->s.size = 0;
336 q->s.next = q;
337 }
338 for(; !(p > q && p < q->s.next); q = q->s.next)
339 if(q >= q->s.next && (p > q || p < q->s.next))
340 break;
341 if(p+p->s.size == q->s.next) {
342 p->s.size += q->s.next->s.size;
343 p->s.next = q->s.next->s.next;
344 qstats[QSfreenext]++;
345 } else
346 p->s.next = q->s.next;
347 if(q+q->s.size == p) {
348 q->s.size += p->s.size;
349 q->s.next = p->s.next;
350 qstats[QSfreeprev]++;
351 } else
352 q->s.next = p;
353 rover = q;
354 }
355
356 static void
mallocreadfmt(char * s,char * e)357 mallocreadfmt(char* s, char* e)
358 {
359 char *p;
360 Header *q;
361 int i, n, t;
362 Qlist *qlist;
363
364 p = s;
365 p = seprint(p, e, "%lud/%lud kernel malloc\n",
366 (tailptr-tailbase)*sizeof(Header),
367 (tailsize+availnunits + tailptr-tailbase)*sizeof(Header));
368 p = seprint(p, e, "0/0 kernel draw\n"); // keep scripts happy
369
370 t = 0;
371 for(i = 0; i <= NQUICK; i++) {
372 n = 0;
373 qlist = &quicklist[i];
374 QLOCK(&qlist->lk);
375 for(q = qlist->first; q != nil; q = q->s.next){
376 // if(q->s.size != i)
377 // p = seprint(p, e, "q%d\t%#p\t%ud\n",
378 // i, q, q->s.size);
379 n++;
380 }
381 QUNLOCK(&qlist->lk);
382
383 // if(n != 0)
384 // p = seprint(p, e, "q%d %d\n", i, n);
385 t += n * i*sizeof(Header);
386 }
387 p = seprint(p, e, "quick: %ud bytes total\n", t);
388
389 MLOCK;
390 if((q = rover) != nil){
391 i = t = 0;
392 do {
393 t += q->s.size;
394 i++;
395 // p = seprint(p, e, "m%d\t%#p\n", q->s.size, q);
396 } while((q = q->s.next) != rover);
397
398 p = seprint(p, e, "rover: %d blocks %ud bytes total\n",
399 i, t*sizeof(Header));
400 }
401
402 for(i = 0; i < nelem(qstats); i++){
403 if(qstats[i] == 0)
404 continue;
405 // p = seprint(p, e, "%s %ud\n", qstatstr[i], qstats[i]);
406 }
407 USED(p);
408 MUNLOCK;
409 }
410
411 long
mallocreadsummary(Chan *,void * a,long n,long offset)412 mallocreadsummary(Chan*, void *a, long n, long offset)
413 {
414 char *alloc;
415
416 alloc = malloc(16*READSTR);
417 if(waserror()){
418 free(alloc);
419 nexterror();
420 }
421 mallocreadfmt(alloc, alloc+16*READSTR);
422 n = readstr(offset, a, n, alloc);
423 poperror();
424 free(alloc);
425
426 return n;
427 }
428
429 void
mallocsummary(void)430 mallocsummary(void)
431 {
432 Header *q;
433 int i, n, t;
434 Qlist *qlist;
435
436 t = 0;
437 for(i = 0; i <= NQUICK; i++) {
438 n = 0;
439 qlist = &quicklist[i];
440 QLOCK(&qlist->lk);
441 for(q = qlist->first; q != nil; q = q->s.next){
442 if(q->s.size != i)
443 DBG("q%d\t%#p\t%ud\n", i, q, q->s.size);
444 n++;
445 }
446 QUNLOCK(&qlist->lk);
447
448 t += n * i*sizeof(Header);
449 }
450 print("quick: %ud bytes total\n", t);
451
452 MLOCK;
453 if((q = rover) != nil){
454 i = t = 0;
455 do {
456 t += q->s.size;
457 i++;
458 } while((q = q->s.next) != rover);
459 }
460 MUNLOCK;
461
462 if(i != 0){
463 print("rover: %d blocks %ud bytes total\n",
464 i, t*sizeof(Header));
465 }
466 print("total allocated %lud, %ud remaining\n",
467 (tailptr-tailbase)*sizeof(Header),
468 (tailsize+availnunits)*sizeof(Header));
469
470 for(i = 0; i < nelem(qstats); i++){
471 if(qstats[i] == 0)
472 continue;
473 print("%s %ud\n", qstatstr[i], qstats[i]);
474 }
475 }
476
477 void
free(void * ap)478 free(void* ap)
479 {
480 MLOCK;
481 qfreeinternal(ap);
482 MUNLOCK;
483 }
484
485 void*
malloc(ulong size)486 malloc(ulong size)
487 {
488 void* v;
489
490 if((v = qmalloc(size)) != nil)
491 memset(v, 0, size);
492
493 return v;
494 }
495
496 void*
mallocz(ulong size,int clr)497 mallocz(ulong size, int clr)
498 {
499 void *v;
500
501 if((v = qmalloc(size)) != nil && clr)
502 memset(v, 0, size);
503
504 return v;
505 }
506
507 void*
mallocalign(ulong nbytes,ulong align,long offset,ulong span)508 mallocalign(ulong nbytes, ulong align, long offset, ulong span)
509 {
510 void *v;
511
512 if(span != 0 && align <= span){
513 if(nbytes > span)
514 return nil;
515 align = span;
516 span = 0;
517 }
518
519 /*
520 * Should this memset or should it be left to the caller?
521 */
522 if((v = qmallocalign(nbytes, align, offset, span)) != nil)
523 memset(v, 0, nbytes);
524
525 return v;
526 }
527
528 void*
smalloc(ulong size)529 smalloc(ulong size)
530 {
531 void *v;
532
533 while((v = malloc(size)) == nil)
534 tsleep(&up->sleep, return0, 0, 100);
535 memset(v, 0, size);
536
537 return v;
538 }
539
540 void*
realloc(void * ap,ulong size)541 realloc(void* ap, ulong size)
542 {
543 void *v;
544 Header *p;
545 ulong osize;
546 uint nunits, ounits;
547 int delta;
548
549 /*
550 * Easy stuff:
551 * free and return nil if size is 0
552 * (implementation-defined behaviour);
553 * behave like malloc if ap is nil;
554 * check for arena corruption;
555 * do nothing if units are the same.
556 */
557 if(size == 0){
558 MLOCK;
559 qfreeinternal(ap);
560 MUNLOCK;
561
562 return nil;
563 }
564 if(ap == nil)
565 return qmalloc(size);
566
567 p = (Header*)ap - 1;
568 if((ounits = p->s.size) == 0 || p->s.next != &checkval)
569 panic("realloc: corrupt allocation arena");
570
571 if((nunits = NUNITS(size)) == ounits)
572 return ap;
573
574 /*
575 * Slightly harder:
576 * if this allocation abuts the tail, try to just
577 * adjust the tailptr.
578 */
579 MLOCK;
580 if(tailptr != nil && p+ounits == tailptr){
581 delta = nunits-ounits;
582 if(delta < 0 || tailsize >= delta){
583 p->s.size = nunits;
584 tailsize -= delta;
585 tailptr += delta;
586 MUNLOCK;
587 return ap;
588 }
589 }
590 MUNLOCK;
591
592 /*
593 * Worth doing if it's a small reduction?
594 * Do it anyway if <= NQUICK?
595 if((ounits-nunits) < 2)
596 return ap;
597 */
598
599 /*
600 * Too hard (or can't be bothered):
601 * allocate, copy and free.
602 * What does the standard say for failure here?
603 */
604 if((v = qmalloc(size)) != nil){
605 osize = (ounits-1)*sizeof(Header);
606 if(size < osize)
607 osize = size;
608 memmove(v, ap, osize);
609 MLOCK;
610 qfreeinternal(ap);
611 MUNLOCK;
612 }
613
614 return v;
615 }
616
617 void
setmalloctag(void *,ulong)618 setmalloctag(void*, ulong)
619 {
620 }
621
622 void
mallocinit(void)623 mallocinit(void)
624 {
625 if(tailptr != nil)
626 return;
627
628 tailbase = UINT2PTR(sys->vmunused);
629 tailptr = tailbase;
630 availnunits = HOWMANY(sys->vmend - sys->vmunused, Unitsz);
631 print("base %#p ptr %#p nunits %ud\n", tailbase, tailptr, availnunits);
632 }
633
634 static int
morecore(uint nunits)635 morecore(uint nunits)
636 {
637 /*
638 * First (simple) cut.
639 * Pump it up when you don't really need it.
640 * Pump it up until you can feel it.
641 */
642 if(nunits < NUNITS(128*KiB))
643 nunits = NUNITS(128*KiB);
644 if(nunits > availnunits)
645 nunits = availnunits;
646 availnunits -= nunits;
647
648 return nunits;
649 }
650