qmalloc.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630
  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. /* Force it to allocate on 64 byte boundaries. I want to guarantee this happens as
  238. * I don't want to take alignment traps. */
  239. static void*
  240. qmalloc(usize nbytes)
  241. {
  242. return qmallocalign(nbytes, 64, 0, 0);
  243. }
  244. static void
  245. qfreeinternal(void* ap)
  246. {
  247. Qlist *qlist;
  248. Header *p, *q;
  249. uint nunits;
  250. if(ap == nil)
  251. return;
  252. qstats[QSfree]++;
  253. p = (Header*)ap - 1;
  254. if((nunits = p->s.size) == 0 || p->s.next != &checkval)
  255. panic("malloc: corrupt allocation arena\n");
  256. if(tailptr != nil && p+nunits == tailptr) {
  257. /* block before tail */
  258. tailptr = p;
  259. tailsize += nunits;
  260. qstats[QSfreetail]++;
  261. return;
  262. }
  263. if(nunits <= NQUICK) {
  264. qlist = &QLIST[nunits];
  265. QLOCK(&qlist->lk);
  266. p->s.next = qlist->first;
  267. qlist->first = p;
  268. QUNLOCK(&qlist->lk);
  269. qstats[QSfreequick]++;
  270. return;
  271. }
  272. if((q = rover) == nil) {
  273. q = &misclist;
  274. q->s.size = 0;
  275. q->s.next = q;
  276. }
  277. for(; !(p > q && p < q->s.next); q = q->s.next)
  278. if(q >= q->s.next && (p > q || p < q->s.next))
  279. break;
  280. if(p+p->s.size == q->s.next) {
  281. p->s.size += q->s.next->s.size;
  282. p->s.next = q->s.next->s.next;
  283. qstats[QSfreenext]++;
  284. } else
  285. p->s.next = q->s.next;
  286. if(q+q->s.size == p) {
  287. q->s.size += p->s.size;
  288. q->s.next = p->s.next;
  289. qstats[QSfreeprev]++;
  290. } else
  291. q->s.next = p;
  292. rover = q;
  293. }
  294. uint32_t
  295. msize(void* ap)
  296. {
  297. Header *p;
  298. uint nunits;
  299. if(ap == nil)
  300. return 0;
  301. p = (Header*)ap - 1;
  302. if((nunits = p->s.size) == 0 || p->s.next != &checkval)
  303. panic("malloc: corrupt allocation arena\n");
  304. return (nunits-1) * sizeof(Header);
  305. }
  306. static void
  307. mallocreadfmt(char* s, char* e)
  308. {
  309. char *p;
  310. Header *q;
  311. int i, n, t;
  312. Qlist *qlist;
  313. p = seprint(s, e,
  314. "%llu memory\n"
  315. "%d pagesize\n"
  316. "%llu kernel\n",
  317. (uint64_t)conf.npage*PGSZ,
  318. PGSZ,
  319. (uint64_t)conf.npage-conf.upages);
  320. t = 0;
  321. for(i = 0; i <= NQUICK; i++) {
  322. n = 0;
  323. qlist = &QLIST[i];
  324. QLOCK(&qlist->lk);
  325. for(q = qlist->first; q != nil; q = q->s.next){
  326. // if(q->s.size != i)
  327. // p = seprint(p, e, "q%d\t%#p\t%u\n",
  328. // i, q, q->s.size);
  329. n++;
  330. }
  331. QUNLOCK(&qlist->lk);
  332. // if(n != 0)
  333. // p = seprint(p, e, "q%d %d\n", i, n);
  334. t += n * i*sizeof(Header);
  335. }
  336. p = seprint(p, e, "quick: %u bytes total\n", t);
  337. MLOCK;
  338. if((q = rover) != nil){
  339. i = t = 0;
  340. do {
  341. t += q->s.size;
  342. i++;
  343. // p = seprint(p, e, "m%d\t%#p\n", q->s.size, q);
  344. } while((q = q->s.next) != rover);
  345. p = seprint(p, e, "rover: %d blocks %u bytes total\n",
  346. i, t*sizeof(Header));
  347. }
  348. p = seprint(p, e, "total allocated %lu, %u remaining\n",
  349. (tailptr-tailbase)*sizeof(Header), tailnunits*sizeof(Header));
  350. for(i = 0; i < nelem(qstats); i++){
  351. if(qstats[i] == 0)
  352. continue;
  353. p = seprint(p, e, "%s %u\n", qstatstr[i], qstats[i]);
  354. }
  355. MUNLOCK;
  356. }
  357. int32_t
  358. mallocreadsummary(Chan* c, void *a, int32_t n, int32_t offset)
  359. {
  360. char *alloc;
  361. alloc = malloc(16*READSTR);
  362. mallocreadfmt(alloc, alloc+16*READSTR);
  363. panic("mallocreadsummary"); //n = readstr(offset, a, n, alloc);
  364. free(alloc);
  365. return n;
  366. }
  367. void
  368. mallocsummary(void)
  369. {
  370. Header *q;
  371. int i, n, t;
  372. Qlist *qlist;
  373. t = 0;
  374. for(i = 0; i <= NQUICK; i++) {
  375. n = 0;
  376. qlist = &QLIST[i];
  377. QLOCK(&qlist->lk);
  378. for(q = qlist->first; q != nil; q = q->s.next){
  379. if(q->s.size != i)
  380. DBG("q%d\t%#p\t%u\n", i, q, q->s.size);
  381. n++;
  382. }
  383. QUNLOCK(&qlist->lk);
  384. t += n * i*sizeof(Header);
  385. }
  386. print("quick: %u bytes total\n", t);
  387. MLOCK;
  388. if((q = rover) != nil){
  389. i = t = 0;
  390. do {
  391. t += q->s.size;
  392. i++;
  393. } while((q = q->s.next) != rover);
  394. }
  395. MUNLOCK;
  396. if(i != 0){
  397. print("rover: %d blocks %u bytes total\n",
  398. i, t*sizeof(Header));
  399. }
  400. print("total allocated %lu, %u remaining\n",
  401. (tailptr-tailbase)*sizeof(Header), tailnunits*sizeof(Header));
  402. for(i = 0; i < nelem(qstats); i++){
  403. if(qstats[i] == 0)
  404. continue;
  405. print("%s %u\n", qstatstr[i], qstats[i]);
  406. }
  407. }
  408. void
  409. free(void* ap)
  410. {
  411. MLOCK;
  412. qfreeinternal(ap);
  413. MUNLOCK;
  414. }
  415. void*
  416. malloc(uint32_t size)
  417. {
  418. void* v;
  419. if((v = qmalloc(size)) != nil)
  420. memset(v, 0, size);
  421. return v;
  422. }
  423. void*
  424. mallocz(uint32_t size, int clr)
  425. {
  426. void *v;
  427. if((v = malloc(size)) != nil && clr)
  428. memset(v, 0, size);
  429. return v;
  430. }
  431. void*
  432. mallocalign(uint32_t nbytes, uint32_t align, int32_t offset, uint32_t span)
  433. {
  434. void *v;
  435. /*
  436. * Should this memset or should it be left to the caller?
  437. */
  438. if((v = qmallocalign(nbytes, align, offset, span)) != nil)
  439. memset(v, 0, nbytes);
  440. return v;
  441. }
  442. void*
  443. smalloc(uint32_t size)
  444. {
  445. Proc *up = externup();
  446. void *v;
  447. while((v = mallocz(size, 1)) == nil)
  448. tsleep(&up->sleep, return0, 0, 100);
  449. return v;
  450. }
  451. void*
  452. realloc(void* ap, uint32_t size)
  453. {
  454. void *v;
  455. Header *p;
  456. uint32_t osize;
  457. uint nunits, ounits;
  458. /*
  459. * Easy stuff:
  460. * free and return nil if size is 0
  461. * (implementation-defined behaviour);
  462. * behave like malloc if ap is nil;
  463. * check for arena corruption;
  464. * do nothing if units are the same.
  465. */
  466. if(size == 0){
  467. MLOCK;
  468. qfreeinternal(ap);
  469. MUNLOCK;
  470. return nil;
  471. }
  472. if(ap == nil)
  473. return qmalloc(size);
  474. p = (Header*)ap - 1;
  475. if((ounits = p->s.size) == 0 || p->s.next != &checkval)
  476. panic("realloc: corrupt allocation arena\n");
  477. if((nunits = NUNITS(size)) <= ounits)
  478. return ap;
  479. /*
  480. * Slightly harder:
  481. * if this allocation abuts the tail, try to just
  482. * adjust the tailptr.
  483. */
  484. MLOCK;
  485. if(tailptr != nil && p+ounits == tailptr){
  486. if(ounits > nunits){
  487. p->s.size = nunits;
  488. tailsize += ounits-nunits;
  489. MUNLOCK;
  490. return ap;
  491. }
  492. if(tailsize >= nunits-ounits){
  493. p->s.size = nunits;
  494. tailsize -= nunits-ounits;
  495. MUNLOCK;
  496. return ap;
  497. }
  498. }
  499. MUNLOCK;
  500. /*
  501. * Worth doing if it's a small reduction?
  502. * Do it anyway if <= NQUICK?
  503. if((ounits-nunits) < 2)
  504. return ap;
  505. */
  506. /*
  507. * Too hard (or can't be bothered):
  508. * allocate, copy and free.
  509. * What does the standard say for failure here?
  510. */
  511. if((v = qmalloc(size)) != nil){
  512. osize = (ounits-1)*sizeof(Header);
  513. if(size < osize)
  514. osize = size;
  515. memmove(v, ap, osize);
  516. MLOCK;
  517. qfreeinternal(ap);
  518. MUNLOCK;
  519. }
  520. return v;
  521. }
  522. void
  523. setmalloctag(void* v, uint32_t i)
  524. {
  525. }
  526. void
  527. mallocinit(void)
  528. {
  529. if(tailptr != nil)
  530. return;
  531. tailbase = UINT2PTR(sys->vmunused);
  532. tailptr = tailbase;
  533. tailnunits = NUNITS(sys->vmend - sys->vmunused);
  534. print("base %#p ptr %#p nunits %u\n", tailbase, tailptr, tailnunits);
  535. }
  536. static int
  537. morecore(uint nunits)
  538. {
  539. /*
  540. * First (simple) cut.
  541. * Pump it up when you don't really need it.
  542. * Pump it up until you can feel it.
  543. */
  544. if(nunits < NUNITS(128*KiB))
  545. nunits = NUNITS(128*KiB);
  546. if(nunits > tailnunits)
  547. nunits = tailnunits;
  548. tailnunits -= nunits;
  549. return nunits;
  550. }