qmalloc.c 13 KB

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