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