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