debugalloc.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683
  1. #include "u.h"
  2. #include "../port/lib.h"
  3. #include "mem.h"
  4. #include "pool.h"
  5. #include "dat.h"
  6. #include "fns.h"
  7. #include "error.h"
  8. #define left u.s.bhl
  9. #define right u.s.bhr
  10. #define fwd u.s.bhf
  11. #define prev u.s.bhv
  12. #define parent u.s.bhp
  13. typedef struct Bhdr Bhdr;
  14. struct Bhdr {
  15. ulong magic;
  16. ulong size;
  17. };
  18. enum {
  19. NOT_MAGIC = 0xdeadfa11,
  20. };
  21. struct Pool
  22. {
  23. char* name;
  24. ulong maxsize;
  25. int quanta;
  26. int chunk;
  27. ulong cursize;
  28. ulong arenasize;
  29. ulong hw;
  30. Lock l;
  31. Bhdr* root;
  32. Bhdr* chain;
  33. int nalloc;
  34. int nfree;
  35. int nbrk;
  36. int lastfree;
  37. void (*move)(void*, void*);
  38. };
  39. struct
  40. {
  41. int n;
  42. Pool pool[MAXPOOL];
  43. Lock l;
  44. } table = {
  45. 2,
  46. {
  47. { "Main", 4*1024*1024, 31, 128*1024 },
  48. { "Image", 16*1024*1024, 31, 2*1024*1024 },
  49. }
  50. };
  51. Pool* mainmem = &table.pool[0];
  52. Pool* imagmem = &table.pool[1];
  53. int poolcompact(Pool*);
  54. Bhdr*
  55. poolchain(Pool *p)
  56. {
  57. return p->chain;
  58. }
  59. void
  60. pooldel(Pool *p, Bhdr *t)
  61. {
  62. Bhdr *s, *f, *rp, *q;
  63. if(t->parent == nil && p->root != t) {
  64. t->prev->fwd = t->fwd;
  65. t->fwd->prev = t->prev;
  66. return;
  67. }
  68. if(t->fwd != t) {
  69. f = t->fwd;
  70. s = t->parent;
  71. f->parent = s;
  72. if(s == nil)
  73. p->root = f;
  74. else {
  75. if(s->left == t)
  76. s->left = f;
  77. else
  78. s->right = f;
  79. }
  80. rp = t->left;
  81. f->left = rp;
  82. if(rp != nil)
  83. rp->parent = f;
  84. rp = t->right;
  85. f->right = rp;
  86. if(rp != nil)
  87. rp->parent = f;
  88. t->prev->fwd = t->fwd;
  89. t->fwd->prev = t->prev;
  90. return;
  91. }
  92. if(t->left == nil)
  93. rp = t->right;
  94. else {
  95. if(t->right == nil)
  96. rp = t->left;
  97. else {
  98. f = t;
  99. rp = t->right;
  100. s = rp->left;
  101. while(s != nil) {
  102. f = rp;
  103. rp = s;
  104. s = rp->left;
  105. }
  106. if(f != t) {
  107. s = rp->right;
  108. f->left = s;
  109. if(s != nil)
  110. s->parent = f;
  111. s = t->right;
  112. rp->right = s;
  113. if(s != nil)
  114. s->parent = rp;
  115. }
  116. s = t->left;
  117. rp->left = s;
  118. s->parent = rp;
  119. }
  120. }
  121. q = t->parent;
  122. if(q == nil)
  123. p->root = rp;
  124. else {
  125. if(t == q->left)
  126. q->left = rp;
  127. else
  128. q->right = rp;
  129. }
  130. if(rp != nil)
  131. rp->parent = q;
  132. }
  133. void
  134. pooladd(Pool *p, Bhdr *q)
  135. {
  136. int size;
  137. Bhdr *tp, *t;
  138. q->magic = MAGIC_F;
  139. q->left = nil;
  140. q->right = nil;
  141. q->parent = nil;
  142. q->fwd = q;
  143. q->prev = q;
  144. t = p->root;
  145. if(t == nil) {
  146. p->root = q;
  147. return;
  148. }
  149. size = q->size;
  150. tp = nil;
  151. while(t != nil) {
  152. if(size == t->size) {
  153. q->fwd = t->fwd;
  154. q->fwd->prev = q;
  155. q->prev = t;
  156. t->fwd = q;
  157. return;
  158. }
  159. tp = t;
  160. if(size < t->size)
  161. t = t->left;
  162. else
  163. t = t->right;
  164. }
  165. q->parent = tp;
  166. if(size < tp->size)
  167. tp->left = q;
  168. else
  169. tp->right = q;
  170. }
  171. void*
  172. poolalloc(Pool *p, int size)
  173. {
  174. Bhdr *q, *t;
  175. int alloc, ldr, ns, frag;
  176. if(size < 0 || size >= 1024*1024*1024) /* for sanity and to avoid overflow */
  177. return nil;
  178. size = (size + BHDRSIZE + p->quanta) & ~(p->quanta);
  179. ilock(&p->l);
  180. p->nalloc++;
  181. t = p->root;
  182. q = nil;
  183. while(t) {
  184. if(t->size == size) {
  185. pooldel(p, t);
  186. t->magic = MAGIC_A;
  187. p->cursize += t->size;
  188. if(p->cursize > p->hw)
  189. p->hw = p->cursize;
  190. iunlock(&p->l);
  191. return B2D(t);
  192. }
  193. if(size < t->size) {
  194. q = t;
  195. t = t->left;
  196. }
  197. else
  198. t = t->right;
  199. }
  200. if(q != nil) {
  201. pooldel(p, q);
  202. q->magic = MAGIC_A;
  203. frag = q->size - size;
  204. if(frag < (size>>2)) {
  205. p->cursize += q->size;
  206. if(p->cursize > p->hw)
  207. p->hw = p->cursize;
  208. iunlock(&p->l);
  209. return B2D(q);
  210. }
  211. /* Split */
  212. ns = q->size - size;
  213. q->size = size;
  214. B2T(q)->hdr = q;
  215. t = B2NB(q);
  216. t->size = ns;
  217. B2T(t)->hdr = t;
  218. pooladd(p, t);
  219. p->cursize += q->size;
  220. if(p->cursize > p->hw)
  221. p->hw = p->cursize;
  222. iunlock(&p->l);
  223. return B2D(q);
  224. }
  225. ns = p->chunk;
  226. if(size > ns)
  227. ns = size;
  228. ldr = p->quanta+1;
  229. alloc = ns+ldr+sizeof(t->magic);
  230. p->arenasize += alloc;
  231. if(p->arenasize > p->maxsize) {
  232. p->arenasize -= alloc;
  233. if(poolcompact(p)) {
  234. iunlock(&p->l);
  235. return poolalloc(p, size);
  236. }
  237. iunlock(&p->l);
  238. print("%s arena too large: size %d cursize %lud arenasize %lud maxsize %lud\n",
  239. p->name, size, p->cursize, p->arenasize, p->maxsize);
  240. return nil;
  241. }
  242. p->nbrk++;
  243. t = xalloc(alloc);
  244. if(t == nil) {
  245. iunlock(&p->l);
  246. return nil;
  247. }
  248. t->magic = MAGIC_E; /* Make a leader */
  249. t->size = ldr;
  250. t->csize = ns+ldr;
  251. t->clink = p->chain;
  252. p->chain = t;
  253. B2T(t)->hdr = t;
  254. t = B2NB(t);
  255. t->magic = MAGIC_A; /* Make the block we are going to return */
  256. t->size = size;
  257. B2T(t)->hdr = t;
  258. q = t;
  259. ns -= size; /* Free the rest */
  260. if(ns > 0) {
  261. q = B2NB(t);
  262. q->size = ns;
  263. B2T(q)->hdr = q;
  264. pooladd(p, q);
  265. }
  266. B2NB(q)->magic = MAGIC_E; /* Mark the end of the chunk */
  267. p->cursize += t->size;
  268. if(p->cursize > p->hw)
  269. p->hw = p->cursize;
  270. iunlock(&p->l);
  271. return B2D(t);
  272. }
  273. void
  274. poolfree(Pool *p, void *v)
  275. {
  276. Bhdr *b, *c;
  277. D2B(b, v);
  278. ilock(&p->l);
  279. p->nfree++;
  280. p->cursize -= b->size;
  281. c = B2NB(b);
  282. if(c->magic == MAGIC_F) { /* Join forward */
  283. pooldel(p, c);
  284. c->magic = 0;
  285. b->size += c->size;
  286. B2T(b)->hdr = b;
  287. }
  288. c = B2PT(b)->hdr;
  289. if(c->magic == MAGIC_F) { /* Join backward */
  290. pooldel(p, c);
  291. b->magic = 0;
  292. c->size += b->size;
  293. b = c;
  294. B2T(b)->hdr = b;
  295. }
  296. pooladd(p, b);
  297. iunlock(&p->l);
  298. }
  299. int
  300. poolread(char *va, int count, ulong offset)
  301. {
  302. Pool *p;
  303. int n, i, signed_off;
  304. n = 0;
  305. signed_off = offset;
  306. for(i = 0; i < table.n; i++) {
  307. p = &table.pool[i];
  308. n += snprint(va+n, count-n, "%11lud %11lud %11lud %11d %11d %11d %s\n",
  309. p->cursize,
  310. p->maxsize,
  311. p->hw,
  312. p->nalloc,
  313. p->nfree,
  314. p->nbrk,
  315. p->name);
  316. if(signed_off > 0) {
  317. signed_off -= n;
  318. if(signed_off < 0) {
  319. memmove(va, va+n+signed_off, -signed_off);
  320. n = -signed_off;
  321. }
  322. else
  323. n = 0;
  324. }
  325. }
  326. return n;
  327. }
  328. Lock pcxlock;
  329. struct {
  330. ulong n;
  331. ulong pc;
  332. } pcx[1024];
  333. static void
  334. remember(ulong pc, void *v)
  335. {
  336. Bhdr *b;
  337. int i;
  338. if(v == nil)
  339. return;
  340. D2B(b, v);
  341. if((b->size>>5) != 2)
  342. return;
  343. ilock(&pcxlock);
  344. B2T(b)->pad = 0;
  345. for(i = 0; i < 1024; i++)
  346. if(pcx[i].pc == pc || pcx[i].pc == 0){
  347. pcx[i].pc = pc;
  348. pcx[i].n++;
  349. B2T(b)->pad = i;
  350. break;
  351. }
  352. iunlock(&pcxlock);
  353. }
  354. static void
  355. forget(void *v)
  356. {
  357. Bhdr *b;
  358. if(v == nil)
  359. return;
  360. D2B(b, v);
  361. if((b->size>>5) != 2)
  362. return;
  363. ilock(&pcxlock);
  364. pcx[B2T(b)->pad].n--;
  365. iunlock(&pcxlock);
  366. }
  367. void*
  368. malloc(ulong size)
  369. {
  370. void *v;
  371. v = poolalloc(mainmem, size);
  372. remember(getcallerpc(&size), v);
  373. if(v != nil)
  374. memset(v, 0, size);
  375. return v;
  376. }
  377. void*
  378. smalloc(ulong size)
  379. {
  380. void *v;
  381. for(;;) {
  382. v = poolalloc(mainmem, size);
  383. remember(getcallerpc(&size), v);
  384. if(v != nil)
  385. break;
  386. tsleep(&up->sleep, return0, 0, 100);
  387. }
  388. memset(v, 0, size);
  389. return v;
  390. }
  391. void*
  392. mallocz(ulong size, int clr)
  393. {
  394. void *v;
  395. v = poolalloc(mainmem, size);
  396. remember(getcallerpc(&size), v);
  397. if(clr && v != nil)
  398. memset(v, 0, size);
  399. return v;
  400. }
  401. void
  402. free(void *v)
  403. {
  404. Bhdr *b;
  405. if(v != nil) {
  406. forget(v);
  407. D2B(b, v);
  408. poolfree(mainmem, v);
  409. }
  410. }
  411. void*
  412. realloc(void *v, ulong size)
  413. {
  414. Bhdr *b;
  415. void *nv;
  416. int osize;
  417. if(v == nil)
  418. return malloc(size);
  419. D2B(b, v);
  420. osize = b->size - BHDRSIZE;
  421. if(osize >= size)
  422. return v;
  423. nv = poolalloc(mainmem, size);
  424. remember(getcallerpc(&v), nv);
  425. if(nv != nil) {
  426. memmove(nv, v, osize);
  427. free(v);
  428. }
  429. return nv;
  430. }
  431. int
  432. msize(void *v)
  433. {
  434. Bhdr *b;
  435. D2B(b, v);
  436. return b->size - BHDRSIZE;
  437. }
  438. void*
  439. calloc(ulong n, ulong szelem)
  440. {
  441. return malloc(n*szelem);
  442. }
  443. /*
  444. void
  445. pooldump(Bhdr *b, int d, int c)
  446. {
  447. Bhdr *t;
  448. if(b == nil)
  449. return;
  450. print("%.8lux %.8lux %.8lux %c %4d %d (f %.8lux p %.8lux)\n",
  451. b, b->left, b->right, c, d, b->size, b->fwd, b->prev);
  452. d++;
  453. for(t = b->fwd; t != b; t = t->fwd)
  454. print("\t%.8lux %.8lux %.8lux\n", t, t->prev, t->fwd);
  455. pooldump(b->left, d, 'l');
  456. pooldump(b->right, d, 'r');
  457. }
  458. void
  459. poolshow(void)
  460. {
  461. int i;
  462. for(i = 0; i < table.n; i++) {
  463. print("Arena: %s root=%.8lux\n", table.pool[i].name, table.pool[i].root);
  464. pooldump(table.pool[i].root, 0, 'R');
  465. }
  466. }
  467. */
  468. void
  469. poolsummary(void)
  470. {
  471. int i;
  472. for(i = 0; i < table.n; i++)
  473. print("Arena: %s cursize=%lud; maxsize=%lud\n",
  474. table.pool[i].name,
  475. table.pool[i].cursize,
  476. table.pool[i].maxsize);
  477. }
  478. /*
  479. void
  480. pooldump(Pool *p)
  481. {
  482. Bhdr *b, *base, *limit, *ptr;
  483. b = p->chain;
  484. if(b == nil)
  485. return;
  486. base = b;
  487. ptr = b;
  488. limit = B2LIMIT(b);
  489. while(base != nil) {
  490. print("\tbase #%.8lux ptr #%.8lux", base, ptr);
  491. if(ptr->magic == MAGIC_A)
  492. print("\tA%.5d\n", ptr->size);
  493. else if(ptr->magic == MAGIC_E)
  494. print("\tE\tL#%.8lux\tS#%.8lux\n", ptr->clink, ptr->csize);
  495. else
  496. print("\tF%.5d\tL#%.8lux\tR#%.8lux\tF#%.8lux\tP#%.8lux\tT#%.8lux\n",
  497. ptr->size, ptr->left, ptr->right, ptr->fwd, ptr->prev, ptr->parent);
  498. ptr = B2NB(ptr);
  499. if(ptr >= limit) {
  500. print("link to #%.8lux\n", base->clink);
  501. base = base->clink;
  502. if(base == nil)
  503. break;
  504. ptr = base;
  505. limit = B2LIMIT(base);
  506. }
  507. }
  508. return;
  509. }
  510. */
  511. void
  512. poolsetcompact(Pool *p, void (*move)(void*, void*))
  513. {
  514. p->move = move;
  515. }
  516. void
  517. poolsetparam(char *name, ulong maxsize, int quanta, int chunk)
  518. {
  519. Pool *p;
  520. int i;
  521. for(i=0; i<table.n; i++){
  522. p = &table.pool[i];
  523. if(strcmp(name, p->name) == 0){
  524. if(maxsize)
  525. p->maxsize = maxsize;
  526. if(quanta)
  527. p->quanta = quanta;
  528. if(chunk)
  529. p->chunk = chunk;
  530. return;
  531. }
  532. }
  533. }
  534. int
  535. poolcompact(Pool *pool)
  536. {
  537. Bhdr *base, *limit, *ptr, *end, *next;
  538. int compacted, recov, nb;
  539. if(pool->move == nil || pool->lastfree == pool->nfree)
  540. return 0;
  541. pool->lastfree = pool->nfree;
  542. base = pool->chain;
  543. ptr = B2NB(base); /* First Block in arena has clink */
  544. limit = B2LIMIT(base);
  545. compacted = 0;
  546. pool->root = nil;
  547. end = ptr;
  548. recov = 0;
  549. while(base != nil) {
  550. next = B2NB(ptr);
  551. if(ptr->magic == MAGIC_A) {
  552. if(ptr != end) {
  553. memmove(end, ptr, ptr->size);
  554. pool->move(B2D(ptr), B2D(end));
  555. recov = (uchar*)ptr - (uchar*)end;
  556. compacted = 1;
  557. }
  558. end = B2NB(end);
  559. }
  560. if(next >= limit) {
  561. nb = (uchar*)limit - (uchar*)end;
  562. //print("recovered %d bytes\n", recov);
  563. //print("%d bytes at end\n", nb);
  564. USED(recov);
  565. if(nb > 0){
  566. if(nb < pool->quanta+1)
  567. panic("poolcompact: leftover too small\n");
  568. end->size = nb;
  569. pooladd(pool, end);
  570. }
  571. base = base->clink;
  572. if(base == nil)
  573. break;
  574. ptr = B2NB(base);
  575. end = ptr; /* could do better by copying between chains */
  576. limit = B2LIMIT(base);
  577. recov = 0;
  578. } else
  579. ptr = next;
  580. }
  581. return compacted;
  582. }
  583. int
  584. recur(Bhdr *t)
  585. {
  586. if(t == 0)
  587. return 1;
  588. if(((ulong)t) < 0x80000000)
  589. return 0;
  590. if(((ulong)t) > 0x90000000)
  591. return 0;
  592. return recur(t->right) && recur(t->left);
  593. }