1 #include "u.h"
2 #include "../port/lib.h"
3 #include "mem.h"
4 #include "dat.h"
5 #include "fns.h"
6
7 #define datoff ((ulong)((Xhdr*)0)->data)
8
9 enum
10 {
11 Chunk = 64*1024,
12 Nhole = 128,
13 Magichole = 0xDeadBabe,
14 };
15
16 typedef struct Hole Hole;
17 typedef struct Xalloc Xalloc;
18 typedef struct Xhdr Xhdr;
19
20 struct Hole
21 {
22 ulong addr;
23 ulong size;
24 ulong top;
25 Hole* link;
26 };
27
28 struct Xhdr
29 {
30 ulong size;
31 ulong magix;
32 char data[1];
33 };
34
35 struct Xalloc
36 {
37 Lock;
38 Hole hole[Nhole];
39 Hole* flist;
40 Hole* table;
41 };
42
43 static Xalloc xlists;
44
45 static void
ixprt()46 ixprt()
47 {
48 xsummary();
49 ixsummary();
50 }
51
52 void
xinit(void)53 xinit(void)
54 {
55 Hole *h, *eh;
56
57 eh = &xlists.hole[Nhole-1];
58 for(h = xlists.hole; h < eh; h++)
59 h->link = h+1;
60
61 xlists.flist = xlists.hole;
62
63 if(conf.npage1)
64 xhole(conf.base1, conf.npage1*BY2PG);
65 conf.npage1 = conf.base1+(conf.npage1*BY2PG);
66
67 if(conf.npage0)
68 xhole(conf.base0, conf.npage0*BY2PG);
69 conf.npage0 = conf.base0+(conf.npage0*BY2PG);
70
71 /* Save the bounds of kernel alloc memory for kernel mmu mapping */
72 conf.base0 = (ulong)KADDR(conf.base0);
73 conf.base1 = (ulong)KADDR(conf.base1);
74 conf.npage0 = (ulong)KADDR(conf.npage0);
75 conf.npage1 = (ulong)KADDR(conf.npage1);
76
77 debugkey('x', "xalloc/ialloc", ixprt, 0);
78 }
79
80 void*
xspanalloc(ulong size,int align,ulong span)81 xspanalloc(ulong size, int align, ulong span)
82 {
83 ulong a, v, t;
84
85 a = (ulong)xalloc(size+align+span);
86 if(a == 0)
87 panic("xspanalloc: %lud %d %lux\n", size, align, span);
88
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
101 if(align > 1)
102 v = (v + align) & ~(align-1);
103
104 return (void*)v;
105 }
106
107 void*
xallocz(ulong size,int zero)108 xallocz(ulong size, int zero)
109 {
110 Xhdr *p;
111 Hole *h, **l;
112
113 size += BY2V + sizeof(Xhdr);
114 size &= ~(BY2V-1);
115
116 ilock(&xlists);
117 l = &xlists.table;
118 for(h = *l; h; h = h->link) {
119 if(h->size >= size) {
120 p = (Xhdr*)h->addr;
121 h->addr += size;
122 h->size -= size;
123 if(h->size == 0) {
124 *l = h->link;
125 h->link = xlists.flist;
126 xlists.flist = h;
127 }
128 iunlock(&xlists);
129 p = KADDR(p);
130 p->magix = Magichole;
131 p->size = size;
132 if(zero)
133 memset(p->data, 0, size);
134 return p->data;
135 }
136 l = &h->link;
137 }
138 iunlock(&xlists);
139 return nil;
140 }
141
142 void*
xalloc(ulong size)143 xalloc(ulong size)
144 {
145 return xallocz(size, 1);
146 }
147
148 void
xfree(void * p)149 xfree(void *p)
150 {
151 Xhdr *x;
152
153 x = (Xhdr*)((ulong)p - datoff);
154 if(x->magix != Magichole) {
155 xsummary();
156 panic("xfree(0x%lux) 0x%lux!=0x%lux", p, (ulong)Magichole, x->magix);
157 }
158 xhole(PADDR(x), x->size);
159 }
160
161 int
xmerge(void * vp,void * vq)162 xmerge(void *vp, void *vq)
163 {
164 Xhdr *p, *q;
165
166 p = (Xhdr*)(((ulong)vp - offsetof(Xhdr, data[0])));
167 q = (Xhdr*)(((ulong)vq - offsetof(Xhdr, data[0])));
168 if(p->magix != Magichole || q->magix != Magichole) {
169 xsummary();
170 panic("xmerge(%#p, %#p) bad magic %#lux, %#lux\n",
171 vp, vq, p->magix, q->magix);
172 }
173 if((uchar*)p+p->size == (uchar*)q) {
174 p->size += q->size;
175 return 1;
176 }
177 return 0;
178 }
179
180 void
xhole(ulong addr,ulong size)181 xhole(ulong addr, ulong size)
182 {
183 ulong top;
184 Hole *h, *c, **l;
185
186 if(size == 0)
187 return;
188
189 top = addr + size;
190 ilock(&xlists);
191 l = &xlists.table;
192 for(h = *l; h; h = h->link) {
193 if(h->top == addr) {
194 h->size += size;
195 h->top = h->addr+h->size;
196 c = h->link;
197 if(c && h->top == c->addr) {
198 h->top += c->size;
199 h->size += c->size;
200 h->link = c->link;
201 c->link = xlists.flist;
202 xlists.flist = c;
203 }
204 iunlock(&xlists);
205 return;
206 }
207 if(h->addr > addr)
208 break;
209 l = &h->link;
210 }
211 if(h && top == h->addr) {
212 h->addr -= size;
213 h->size += size;
214 iunlock(&xlists);
215 return;
216 }
217
218 if(xlists.flist == nil) {
219 iunlock(&xlists);
220 print("xfree: no free holes, leaked %lud bytes\n", size);
221 return;
222 }
223
224 h = xlists.flist;
225 xlists.flist = h->link;
226 h->addr = addr;
227 h->top = top;
228 h->size = size;
229 h->link = *l;
230 *l = h;
231 iunlock(&xlists);
232 }
233
234 void
xsummary(void)235 xsummary(void)
236 {
237 int i;
238 Hole *h;
239
240 i = 0;
241 for(h = xlists.flist; h; h = h->link)
242 i++;
243
244 print("%d holes free\n", i);
245 i = 0;
246 for(h = xlists.table; h; h = h->link) {
247 print("%.8lux %.8lux %lud\n", h->addr, h->top, h->size);
248 i += h->size;
249 }
250 print("%d bytes free\n", i);
251 }
252