xalloc.c 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260
  1. #include "u.h"
  2. #include "../port/lib.h"
  3. #include "mem.h"
  4. #include "dat.h"
  5. #include "fns.h"
  6. enum
  7. {
  8. Chunk = 64*1024,
  9. Nhole = 128,
  10. Magichole = 0x484F4C45, /* HOLE */
  11. };
  12. typedef struct Hole Hole;
  13. typedef struct Xalloc Xalloc;
  14. typedef struct Xhdr Xhdr;
  15. struct Hole
  16. {
  17. ulong addr;
  18. ulong size;
  19. ulong top;
  20. Hole* link;
  21. };
  22. struct Xhdr
  23. {
  24. ulong size;
  25. ulong magix;
  26. char data[];
  27. };
  28. struct Xalloc
  29. {
  30. Lock;
  31. Hole hole[Nhole];
  32. Hole* flist;
  33. Hole* table;
  34. };
  35. static Xalloc xlists;
  36. void
  37. xinit(void)
  38. {
  39. int i, n, upages, kpages;
  40. ulong maxpages;
  41. Confmem *m;
  42. Pallocmem *pm;
  43. Hole *h, *eh;
  44. eh = &xlists.hole[Nhole-1];
  45. for(h = xlists.hole; h < eh; h++)
  46. h->link = h+1;
  47. xlists.flist = xlists.hole;
  48. upages = conf.upages;
  49. kpages = conf.npage - upages;
  50. pm = palloc.mem;
  51. for(i=0; i<nelem(conf.mem); i++){
  52. m = &conf.mem[i];
  53. n = m->npage;
  54. if(n > kpages)
  55. n = kpages;
  56. /* don't try to use non-KADDR-able memory for kernel */
  57. maxpages = cankaddr(m->base)/BY2PG;
  58. if(n > maxpages)
  59. n = maxpages;
  60. /* first give to kernel */
  61. if(n > 0){
  62. m->kbase = (ulong)KADDR(m->base);
  63. m->klimit = (ulong)KADDR(m->base+n*BY2PG);
  64. xhole(m->base, n*BY2PG);
  65. kpages -= n;
  66. }
  67. /* if anything left over, give to user */
  68. if(n < m->npage){
  69. if(pm >= palloc.mem+nelem(palloc.mem)){
  70. print("xinit: losing %lud pages\n", m->npage-n);
  71. continue;
  72. }
  73. pm->base = m->base+n*BY2PG;
  74. pm->npage = m->npage - n;
  75. pm++;
  76. }
  77. }
  78. xsummary();
  79. }
  80. void*
  81. xspanalloc(ulong size, int align, ulong span)
  82. {
  83. ulong a, v, t;
  84. a = (ulong)xalloc(size+align+span);
  85. if(a == 0)
  86. panic("xspanalloc: %lud %d %lux\n", size, align, span);
  87. if(span > 2) {
  88. v = (a + span) & ~(span-1);
  89. t = v - a;
  90. if(t > 0)
  91. xhole(PADDR(a), t);
  92. t = a + span - v;
  93. if(t > 0)
  94. xhole(PADDR(v+size+align), t);
  95. }
  96. else
  97. v = a;
  98. if(align > 1)
  99. v = (v + align) & ~(align-1);
  100. return (void*)v;
  101. }
  102. void*
  103. xallocz(ulong size, int zero)
  104. {
  105. Xhdr *p;
  106. Hole *h, **l;
  107. size += BY2V + offsetof(Xhdr, data[0]);
  108. size &= ~(BY2V-1);
  109. ilock(&xlists);
  110. l = &xlists.table;
  111. for(h = *l; h; h = h->link) {
  112. if(h->size >= size) {
  113. p = (Xhdr*)KADDR(h->addr);
  114. h->addr += size;
  115. h->size -= size;
  116. if(h->size == 0) {
  117. *l = h->link;
  118. h->link = xlists.flist;
  119. xlists.flist = h;
  120. }
  121. iunlock(&xlists);
  122. if(zero)
  123. memset(p->data, 0, size);
  124. p->magix = Magichole;
  125. p->size = size;
  126. return p->data;
  127. }
  128. l = &h->link;
  129. }
  130. iunlock(&xlists);
  131. return nil;
  132. }
  133. void*
  134. xalloc(ulong size)
  135. {
  136. return xallocz(size, 1);
  137. }
  138. void
  139. xfree(void *p)
  140. {
  141. Xhdr *x;
  142. x = (Xhdr*)((ulong)p - offsetof(Xhdr, data[0]));
  143. if(x->magix != Magichole) {
  144. xsummary();
  145. panic("xfree(%#p) %#ux != %#lux", p, Magichole, x->magix);
  146. }
  147. xhole(PADDR((uintptr)x), x->size);
  148. }
  149. int
  150. xmerge(void *vp, void *vq)
  151. {
  152. Xhdr *p, *q;
  153. p = (Xhdr*)(((ulong)vp - offsetof(Xhdr, data[0])));
  154. q = (Xhdr*)(((ulong)vq - offsetof(Xhdr, data[0])));
  155. if(p->magix != Magichole || q->magix != Magichole) {
  156. xsummary();
  157. panic("xmerge(%#p, %#p) bad magic %#lux, %#lux\n",
  158. vp, vq, p->magix, q->magix);
  159. }
  160. if((uchar*)p+p->size == (uchar*)q) {
  161. p->size += q->size;
  162. return 1;
  163. }
  164. return 0;
  165. }
  166. void
  167. xhole(ulong addr, ulong size)
  168. {
  169. ulong top;
  170. Hole *h, *c, **l;
  171. if(size == 0)
  172. return;
  173. top = addr + size;
  174. ilock(&xlists);
  175. l = &xlists.table;
  176. for(h = *l; h; h = h->link) {
  177. if(h->top == addr) {
  178. h->size += size;
  179. h->top = h->addr+h->size;
  180. c = h->link;
  181. if(c && h->top == c->addr) {
  182. h->top += c->size;
  183. h->size += c->size;
  184. h->link = c->link;
  185. c->link = xlists.flist;
  186. xlists.flist = c;
  187. }
  188. iunlock(&xlists);
  189. return;
  190. }
  191. if(h->addr > addr)
  192. break;
  193. l = &h->link;
  194. }
  195. if(h && top == h->addr) {
  196. h->addr -= size;
  197. h->size += size;
  198. iunlock(&xlists);
  199. return;
  200. }
  201. if(xlists.flist == nil) {
  202. iunlock(&xlists);
  203. print("xfree: no free holes, leaked %lud bytes\n", size);
  204. return;
  205. }
  206. h = xlists.flist;
  207. xlists.flist = h->link;
  208. h->addr = addr;
  209. h->top = top;
  210. h->size = size;
  211. h->link = *l;
  212. *l = h;
  213. iunlock(&xlists);
  214. }
  215. void
  216. xsummary(void)
  217. {
  218. int i;
  219. Hole *h;
  220. i = 0;
  221. for(h = xlists.flist; h; h = h->link)
  222. i++;
  223. print("%d holes free\n", i);
  224. i = 0;
  225. for(h = xlists.table; h; h = h->link) {
  226. print("%.8lux %.8lux %lud\n", h->addr, h->top, h->size);
  227. i += h->size;
  228. }
  229. print("%d bytes free\n", i);
  230. }