1
2 #define _SYSTEM 1
3
4 #include <minix/callnr.h>
5 #include <minix/com.h>
6 #include <minix/config.h>
7 #include <minix/const.h>
8 #include <minix/ds.h>
9 #include <minix/endpoint.h>
10 #include <minix/minlib.h>
11 #include <minix/type.h>
12 #include <minix/ipc.h>
13 #include <minix/sysutil.h>
14 #include <minix/syslib.h>
15 #include <minix/bitmap.h>
16 #include <minix/debug.h>
17
18 #include <assert.h>
19 #include <errno.h>
20 #include <string.h>
21
22 #include <sys/param.h>
23
24 #include "glo.h"
25 #include "proto.h"
26 #include "util.h"
27 #include "sanitycheck.h"
28
29 #define SLABSIZES 200
30
31 #define ITEMSPERPAGE(bytes) (int)(DATABYTES / (bytes))
32
33 #define ELBITS (sizeof(element_t)*8)
34 #define BITPAT(b) (1UL << ((b) % ELBITS))
35 #define BITEL(f, b) (f)->sdh.usebits[(b)/ELBITS]
36
37
38 #define OFF(f, b) assert(!GETBIT(f, b))
39 #define ON(f, b) assert(GETBIT(f, b))
40
41 #if MEMPROTECT
42 #define SLABDATAWRITABLE(data, wr) do { \
43 assert(data->sdh.writable == WRITABLE_NONE); \
44 assert(wr != WRITABLE_NONE); \
45 vm_pagelock(data, 0); \
46 data->sdh.writable = wr; \
47 } while(0)
48
49 #define SLABDATAUNWRITABLE(data) do { \
50 assert(data->sdh.writable != WRITABLE_NONE); \
51 data->sdh.writable = WRITABLE_NONE; \
52 vm_pagelock(data, 1); \
53 } while(0)
54
55 #define SLABDATAUSE(data, code) do { \
56 SLABDATAWRITABLE(data, WRITABLE_HEADER); \
57 code \
58 SLABDATAUNWRITABLE(data); \
59 } while(0)
60
61 #else
62
63 #define SLABDATAWRITABLE(data, wr)
64 #define SLABDATAUNWRITABLE(data)
65 #define SLABDATAUSE(data, code) do { code } while(0)
66
67 #endif
68
69 #define GETBIT(f, b) (BITEL(f,b) & BITPAT(b))
70 #define SETBIT(f, b) {OFF(f,b); SLABDATAUSE(f, BITEL(f,b)|= BITPAT(b); (f)->sdh.nused++;); }
71 #define CLEARBIT(f, b) {ON(f, b); SLABDATAUSE(f, BITEL(f,b)&=~BITPAT(b); (f)->sdh.nused--; (f)->sdh.freeguess = (b);); }
72
73 #define OBJALIGN 8
74
75 #define MINSIZE 8
76 #define MAXSIZE (SLABSIZES-1+MINSIZE)
77 #define USEELEMENTS (1+(VM_PAGE_SIZE/MINSIZE/8))
78
79 static int pages = 0;
80
81 typedef u8_t element_t;
82 #define BITS_FULL (~(element_t)0)
83 typedef element_t elements_t[USEELEMENTS];
84
85 /* This file is too low-level to have global SANITYCHECKs everywhere,
86 * as the (other) data structures are often necessarily in an
87 * inconsistent state during a slaballoc() / slabfree(). So only do
88 * our own sanity checks here, with SLABSANITYCHECK.
89 */
90
91
92 /* Special writable values. */
93 #define WRITABLE_NONE -2
94 #define WRITABLE_HEADER -1
95
96 struct sdh {
97 #if SANITYCHECKS
98 u32_t magic1;
99 #endif
100 int freeguess;
101 struct slabdata *next, *prev;
102 elements_t usebits;
103 phys_bytes phys;
104 #if SANITYCHECKS
105 int writable; /* data item number or WRITABLE_* */
106 u32_t magic2;
107 #endif
108 u16_t nused; /* Number of data items used in this slab. */
109 };
110
111 #define DATABYTES (VM_PAGE_SIZE-sizeof(struct sdh))
112
113 #define MAGIC1 0x1f5b842f
114 #define MAGIC2 0x8bb5a420
115 #define JUNK 0xdeadbeef
116 #define NOJUNK 0xc0ffee
117
118 struct slabdata {
119 u8_t data[DATABYTES];
120 struct sdh sdh;
121 };
122
123 static struct slabheader {
124 struct slabdata *list_head;
125 } slabs[SLABSIZES];
126
127 static int objstats(void *, int, struct slabheader **, struct slabdata
128 **, int *);
129
130 #define GETSLAB(b, s) { \
131 int _gsi; \
132 assert((b) >= MINSIZE); \
133 _gsi = (b) - MINSIZE; \
134 assert((_gsi) < SLABSIZES); \
135 assert((_gsi) >= 0); \
136 s = &slabs[_gsi]; \
137 }
138
139 /* move slabdata nw to slabheader sl under list number l. */
140 #define ADDHEAD(nw, sl) { \
141 SLABDATAUSE(nw, \
142 (nw)->sdh.next = sl->list_head; \
143 (nw)->sdh.prev = NULL;); \
144 sl->list_head = nw; \
145 if((nw)->sdh.next) { \
146 SLABDATAUSE((nw)->sdh.next, \
147 (nw)->sdh.next->sdh.prev = (nw);); \
148 } \
149 }
150
151 #define UNLINKNODE(node) { \
152 struct slabdata *next, *prev; \
153 prev = (node)->sdh.prev; \
154 next = (node)->sdh.next; \
155 if(prev) { SLABDATAUSE(prev, prev->sdh.next = next;); } \
156 if(next) { SLABDATAUSE(next, next->sdh.prev = prev;); } \
157 }
158
newslabdata(void)159 static struct slabdata *newslabdata(void)
160 {
161 struct slabdata *n;
162 phys_bytes p;
163
164 assert(sizeof(*n) == VM_PAGE_SIZE);
165
166 if(!(n = vm_allocpage(&p, VMP_SLAB))) {
167 printf("newslabdata: vm_allocpage failed\n");
168 return NULL;
169 }
170 memset(n->sdh.usebits, 0, sizeof(n->sdh.usebits));
171 pages++;
172
173 n->sdh.phys = p;
174 #if SANITYCHECKS
175 n->sdh.magic1 = MAGIC1;
176 n->sdh.magic2 = MAGIC2;
177 #endif
178 n->sdh.nused = 0;
179 n->sdh.freeguess = 0;
180
181 #if SANITYCHECKS
182 n->sdh.writable = WRITABLE_HEADER;
183 SLABDATAUNWRITABLE(n);
184 #endif
185
186 return n;
187 }
188
189 #if SANITYCHECKS
190
191 /*===========================================================================*
192 * checklist *
193 *===========================================================================*/
checklist(const char * file,int line,struct slabheader * s,int bytes)194 static int checklist(const char *file, int line,
195 struct slabheader *s, int bytes)
196 {
197 struct slabdata *n = s->list_head;
198 int ch = 0;
199
200 while(n) {
201 int count = 0, i;
202 #if SANITYCHECKS
203 MYASSERT(n->sdh.magic1 == MAGIC1);
204 MYASSERT(n->sdh.magic2 == MAGIC2);
205 #endif
206 MYASSERT(usedpages_add(n->sdh.phys, VM_PAGE_SIZE) == OK);
207 if(n->sdh.prev)
208 MYASSERT(n->sdh.prev->sdh.next == n);
209 else
210 MYASSERT(s->list_head == n);
211 if(n->sdh.next) MYASSERT(n->sdh.next->sdh.prev == n);
212 for(i = 0; i < USEELEMENTS*8; i++)
213 if(i >= ITEMSPERPAGE(bytes))
214 MYASSERT(!GETBIT(n, i));
215 else
216 if(GETBIT(n,i))
217 count++;
218 MYASSERT(count == n->sdh.nused);
219 ch += count;
220 n = n->sdh.next;
221 }
222
223 return ch;
224 }
225
226 /*===========================================================================*
227 * void slab_sanitycheck *
228 *===========================================================================*/
slab_sanitycheck(const char * file,int line)229 void slab_sanitycheck(const char *file, int line)
230 {
231 int s;
232 for(s = 0; s < SLABSIZES; s++) {
233 checklist(file, line, &slabs[s], s + MINSIZE);
234 }
235 }
236
237 /*===========================================================================*
238 * int slabsane *
239 *===========================================================================*/
slabsane_f(const char * file,int line,void * mem,int bytes)240 int slabsane_f(const char *file, int line, void *mem, int bytes)
241 {
242 struct slabheader *s;
243 struct slabdata *f;
244 int i;
245
246 bytes = roundup(bytes, OBJALIGN);
247
248 return (objstats(mem, bytes, &s, &f, &i) == OK);
249 }
250 #endif
251
252 #if SANITYCHECKS
253 static int nojunkwarning = 0;
254 #endif
255
256 /*===========================================================================*
257 * void *slaballoc *
258 *===========================================================================*/
slaballoc(int bytes)259 void *slaballoc(int bytes)
260 {
261 int i;
262 int count = 0;
263 struct slabheader *s;
264 struct slabdata *newslab;
265 char *ret;
266
267 bytes = roundup(bytes, OBJALIGN);
268
269 SLABSANITYCHECK(SCL_FUNCTIONS);
270
271 /* Retrieve entry in slabs[]. */
272 GETSLAB(bytes, s);
273 assert(s);
274
275 if(!(newslab = s->list_head)) {
276 /* Make sure there is something on the freelist. */
277 newslab = newslabdata();
278 if(!newslab) return NULL;
279 ADDHEAD(newslab, s);
280 assert(newslab->sdh.nused == 0);
281 } else assert(newslab->sdh.nused > 0);
282 assert(newslab->sdh.nused < ITEMSPERPAGE(bytes));
283
284 SLABSANITYCHECK(SCL_DETAIL);
285
286 #if SANITYCHECKS
287 assert(newslab->sdh.magic1 == MAGIC1);
288 assert(newslab->sdh.magic2 == MAGIC2);
289 #endif
290
291 for(i = newslab->sdh.freeguess;
292 count < ITEMSPERPAGE(bytes); count++, i++) {
293 i = i % ITEMSPERPAGE(bytes);
294
295 if(!GETBIT(newslab, i))
296 break;
297 }
298
299 SLABSANITYCHECK(SCL_FUNCTIONS);
300
301 assert(count < ITEMSPERPAGE(bytes));
302 assert(i >= 0 && i < ITEMSPERPAGE(bytes));
303
304 SETBIT(newslab, i);
305 if(newslab->sdh.nused == ITEMSPERPAGE(bytes)) {
306 UNLINKNODE(newslab);
307 s->list_head = newslab->sdh.next;
308 }
309
310 ret = ((char *) newslab) + i*bytes;
311
312 #if SANITYCHECKS
313 #if MEMPROTECT
314 nojunkwarning++;
315 slabunlock(ret, bytes);
316 nojunkwarning--;
317 assert(!nojunkwarning);
318 #endif
319 *(u32_t *) ret = NOJUNK;
320 #if MEMPROTECT
321 slablock(ret, bytes);
322 #endif
323 #endif
324
325 SLABDATAUSE(newslab, newslab->sdh.freeguess = i+1;);
326
327 #if SANITYCHECKS
328 if(bytes >= SLABSIZES+MINSIZE) {
329 printf("slaballoc: odd, bytes %d?\n", bytes);
330 }
331
332 if(!slabsane_f(__FILE__, __LINE__, ret, bytes))
333 panic("slaballoc: slabsane failed");
334 #endif
335
336 assert(!((vir_bytes) ret % OBJALIGN));
337
338 return ret;
339 }
340
341 /*===========================================================================*
342 * int objstats *
343 *===========================================================================*/
objstats(void * mem,int bytes,struct slabheader ** sp,struct slabdata ** fp,int * ip)344 static inline int objstats(void *mem, int bytes,
345 struct slabheader **sp, struct slabdata **fp, int *ip)
346 {
347 #if SANITYCHECKS
348 #define OBJSTATSCHECK(cond) \
349 if(!(cond)) { \
350 printf("VM: objstats: %s failed for ptr %p, %d bytes\n", \
351 #cond, mem, bytes); \
352 return EINVAL; \
353 }
354 #else
355 #define OBJSTATSCHECK(cond)
356 #endif
357
358 struct slabheader *s;
359 struct slabdata *f;
360 int i;
361
362 assert(!(bytes % OBJALIGN));
363
364 OBJSTATSCHECK((char *) mem >= (char *) VM_PAGE_SIZE);
365
366 #if SANITYCHECKS
367 if(*(u32_t *) mem == JUNK && !nojunkwarning) {
368 util_stacktrace();
369 printf("VM: WARNING: JUNK seen in slab object, likely freed\n");
370 }
371 #endif
372 /* Retrieve entry in slabs[]. */
373 GETSLAB(bytes, s);
374
375 /* Round address down to VM_PAGE_SIZE boundary to get header. */
376 f = (struct slabdata *) ((char *) mem - (vir_bytes) mem % VM_PAGE_SIZE);
377
378 #if SANITYCHECKS
379 OBJSTATSCHECK(f->sdh.magic1 == MAGIC1);
380 OBJSTATSCHECK(f->sdh.magic2 == MAGIC2);
381 #endif
382
383 /* Make sure it's in range. */
384 OBJSTATSCHECK((char *) mem >= (char *) f->data);
385 OBJSTATSCHECK((char *) mem < (char *) f->data + sizeof(f->data));
386
387 /* Get position. */
388 i = (char *) mem - (char *) f->data;
389 OBJSTATSCHECK(!(i % bytes));
390 i = i / bytes;
391
392 /* Make sure it is marked as allocated. */
393 OBJSTATSCHECK(GETBIT(f, i));
394
395 /* return values */
396 *ip = i;
397 *fp = f;
398 *sp = s;
399
400 return OK;
401 }
402
403 /*===========================================================================*
404 * void *slabfree *
405 *===========================================================================*/
slabfree(void * mem,int bytes)406 void slabfree(void *mem, int bytes)
407 {
408 int i;
409 struct slabheader *s;
410 struct slabdata *f;
411
412 bytes = roundup(bytes, OBJALIGN);
413
414 SLABSANITYCHECK(SCL_FUNCTIONS);
415
416 if(objstats(mem, bytes, &s, &f, &i) != OK) {
417 panic("slabfree objstats failed");
418 }
419
420 #if SANITYCHECKS
421 if(*(u32_t *) mem == JUNK) {
422 printf("VM: WARNING: likely double free, JUNK seen\n");
423 }
424 #endif
425
426 #if SANITYCHECKS
427 #if MEMPROTECT
428 slabunlock(mem, bytes);
429 #endif
430 #if JUNKFREE
431 memset(mem, 0xa6, bytes);
432 #endif
433 *(u32_t *) mem = JUNK;
434 nojunkwarning++;
435 #if MEMPROTECT
436 slablock(mem, bytes);
437 #endif
438 nojunkwarning--;
439 assert(!nojunkwarning);
440 #endif
441
442 /* Free this data. */
443 CLEARBIT(f, i);
444
445 /* Check if this slab changes lists. */
446 if(f->sdh.nused == 0) {
447 UNLINKNODE(f);
448 if(f == s->list_head) s->list_head = f->sdh.next;
449 vm_freepages((vir_bytes) f, 1);
450 SLABSANITYCHECK(SCL_DETAIL);
451 } else if(f->sdh.nused == ITEMSPERPAGE(bytes)-1) {
452 ADDHEAD(f, s);
453 }
454
455 SLABSANITYCHECK(SCL_FUNCTIONS);
456
457 return;
458 }
459
460 #if MEMPROTECT
461 /*===========================================================================*
462 * void *slablock *
463 *===========================================================================*/
slablock(void * mem,int bytes)464 void slablock(void *mem, int bytes)
465 {
466 int i;
467 struct slabheader *s;
468 struct slabdata *f;
469
470 bytes = roundup(bytes, OBJALIGN);
471
472 if(objstats(mem, bytes, &s, &f, &i) != OK)
473 panic("slablock objstats failed");
474
475 SLABDATAUNWRITABLE(f);
476
477 return;
478 }
479
480 /*===========================================================================*
481 * void *slabunlock *
482 *===========================================================================*/
slabunlock(void * mem,int bytes)483 void slabunlock(void *mem, int bytes)
484 {
485 int i;
486 struct slabheader *s;
487 struct slabdata *f;
488
489 bytes = roundup(bytes, OBJALIGN);
490
491 if(objstats(mem, bytes, &s, &f, &i) != OK)
492 panic("slabunlock objstats failed");
493
494 SLABDATAWRITABLE(f, i);
495
496 return;
497 }
498 #endif
499
500 #if SANITYCHECKS
501 /*===========================================================================*
502 * void slabstats *
503 *===========================================================================*/
slabstats(void)504 void slabstats(void)
505 {
506 int s, totalbytes = 0;
507 static int n;
508 n++;
509 if(n%1000) return;
510 for(s = 0; s < SLABSIZES; s++) {
511 int b, t;
512 b = s + MINSIZE;
513 t = checklist(__FILE__, __LINE__, &slabs[s], b);
514
515 if(t > 0) {
516 int bytes = t * b;
517 printf("VMSTATS: %2d slabs: %d (%dkB)\n", b, t, bytes/1024);
518 totalbytes += bytes;
519 }
520 }
521
522 if(pages > 0) {
523 printf("VMSTATS: %dK net used in slab objects in %d pages (%dkB): %d%% utilization\n",
524 totalbytes/1024, pages, pages*VM_PAGE_SIZE/1024,
525 100 * totalbytes / (pages*VM_PAGE_SIZE));
526 }
527 }
528 #endif
529