xalloc.c 4.0 KB

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