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 struct slabdata { 120 u8_t data[DATABYTES]; 121 struct sdh sdh; 122 }; 123 124 static struct slabheader { 125 struct slabdata *list_head; 126 } slabs[SLABSIZES]; 127 128 static int objstats(void *, int, struct slabheader **, struct slabdata 129 **, int *); 130 131 #define GETSLAB(b, s) { \ 132 int _gsi; \ 133 assert((b) >= MINSIZE); \ 134 _gsi = (b) - MINSIZE; \ 135 assert((_gsi) < SLABSIZES); \ 136 assert((_gsi) >= 0); \ 137 s = &slabs[_gsi]; \ 138 } 139 140 /* move slabdata nw to slabheader sl under list number l. */ 141 #define ADDHEAD(nw, sl) { \ 142 SLABDATAUSE(nw, \ 143 (nw)->sdh.next = sl->list_head; \ 144 (nw)->sdh.prev = NULL;); \ 145 sl->list_head = nw; \ 146 if((nw)->sdh.next) { \ 147 SLABDATAUSE((nw)->sdh.next, \ 148 (nw)->sdh.next->sdh.prev = (nw);); \ 149 } \ 150 } 151 152 #define UNLINKNODE(node) { \ 153 struct slabdata *next, *prev; \ 154 prev = (node)->sdh.prev; \ 155 next = (node)->sdh.next; \ 156 if(prev) { SLABDATAUSE(prev, prev->sdh.next = next;); } \ 157 if(next) { SLABDATAUSE(next, next->sdh.prev = prev;); } \ 158 } 159 160 static struct slabdata *newslabdata(void) 161 { 162 struct slabdata *n; 163 phys_bytes p; 164 165 assert(sizeof(*n) == VM_PAGE_SIZE); 166 167 if(!(n = vm_allocpage(&p, VMP_SLAB))) { 168 printf("newslabdata: vm_allocpage failed\n"); 169 return NULL; 170 } 171 memset(n->sdh.usebits, 0, sizeof(n->sdh.usebits)); 172 pages++; 173 174 n->sdh.phys = p; 175 #if SANITYCHECKS 176 n->sdh.magic1 = MAGIC1; 177 n->sdh.magic2 = MAGIC2; 178 #endif 179 n->sdh.nused = 0; 180 n->sdh.freeguess = 0; 181 182 #if SANITYCHECKS 183 n->sdh.writable = WRITABLE_HEADER; 184 SLABDATAUNWRITABLE(n); 185 #endif 186 187 return n; 188 } 189 190 #if SANITYCHECKS 191 192 /*===========================================================================* 193 * checklist * 194 *===========================================================================*/ 195 static int checklist(const char *file, int line, 196 struct slabheader *s, int bytes) 197 { 198 struct slabdata *n = s->list_head; 199 int ch = 0; 200 201 while(n) { 202 int count = 0, i; 203 #if SANITYCHECKS 204 MYASSERT(n->sdh.magic1 == MAGIC1); 205 MYASSERT(n->sdh.magic2 == MAGIC2); 206 #endif 207 MYASSERT(usedpages_add(n->sdh.phys, VM_PAGE_SIZE) == OK); 208 if(n->sdh.prev) 209 MYASSERT(n->sdh.prev->sdh.next == n); 210 else 211 MYASSERT(s->list_head == n); 212 if(n->sdh.next) MYASSERT(n->sdh.next->sdh.prev == n); 213 for(i = 0; i < USEELEMENTS*8; i++) 214 if(i >= ITEMSPERPAGE(bytes)) 215 MYASSERT(!GETBIT(n, i)); 216 else 217 if(GETBIT(n,i)) 218 count++; 219 MYASSERT(count == n->sdh.nused); 220 ch += count; 221 n = n->sdh.next; 222 } 223 224 return ch; 225 } 226 227 /*===========================================================================* 228 * void slab_sanitycheck * 229 *===========================================================================*/ 230 void slab_sanitycheck(const char *file, int line) 231 { 232 int s; 233 for(s = 0; s < SLABSIZES; s++) { 234 checklist(file, line, &slabs[s], s + MINSIZE); 235 } 236 } 237 238 /*===========================================================================* 239 * int slabsane * 240 *===========================================================================*/ 241 int slabsane_f(const char *file, int line, void *mem, int bytes) 242 { 243 struct slabheader *s; 244 struct slabdata *f; 245 int i; 246 247 bytes = roundup(bytes, OBJALIGN); 248 249 return (objstats(mem, bytes, &s, &f, &i) == OK); 250 } 251 #endif 252 253 #if SANITYCHECKS 254 static int nojunkwarning = 0; 255 #endif 256 257 /*===========================================================================* 258 * void *slaballoc * 259 *===========================================================================*/ 260 void *slaballoc(int bytes) 261 { 262 int i; 263 int count = 0; 264 struct slabheader *s; 265 struct slabdata *newslab; 266 char *ret; 267 268 bytes = roundup(bytes, OBJALIGN); 269 270 SLABSANITYCHECK(SCL_FUNCTIONS); 271 272 /* Retrieve entry in slabs[]. */ 273 GETSLAB(bytes, s); 274 assert(s); 275 276 if(!(newslab = s->list_head)) { 277 /* Make sure there is something on the freelist. */ 278 newslab = newslabdata(); 279 if(!newslab) return NULL; 280 ADDHEAD(newslab, s); 281 assert(newslab->sdh.nused == 0); 282 } else assert(newslab->sdh.nused > 0); 283 assert(newslab->sdh.nused < ITEMSPERPAGE(bytes)); 284 285 SLABSANITYCHECK(SCL_DETAIL); 286 287 #if SANITYCHECKS 288 assert(newslab->sdh.magic1 == MAGIC1); 289 assert(newslab->sdh.magic2 == MAGIC2); 290 #endif 291 292 for(i = newslab->sdh.freeguess; 293 count < ITEMSPERPAGE(bytes); count++, i++) { 294 i = i % ITEMSPERPAGE(bytes); 295 296 if(!GETBIT(newslab, i)) 297 break; 298 } 299 300 SLABSANITYCHECK(SCL_FUNCTIONS); 301 302 assert(count < ITEMSPERPAGE(bytes)); 303 assert(i >= 0 && i < ITEMSPERPAGE(bytes)); 304 305 SETBIT(newslab, i); 306 if(newslab->sdh.nused == ITEMSPERPAGE(bytes)) { 307 UNLINKNODE(newslab); 308 s->list_head = newslab->sdh.next; 309 } 310 311 ret = ((char *) newslab) + i*bytes; 312 313 #if SANITYCHECKS 314 #if MEMPROTECT 315 nojunkwarning++; 316 slabunlock(ret, bytes); 317 nojunkwarning--; 318 assert(!nojunkwarning); 319 #endif 320 *(u32_t *) ret = NOJUNK; 321 #if MEMPROTECT 322 slablock(ret, bytes); 323 #endif 324 #endif 325 326 SLABDATAUSE(newslab, newslab->sdh.freeguess = i+1;); 327 328 #if SANITYCHECKS 329 if(bytes >= SLABSIZES+MINSIZE) { 330 printf("slaballoc: odd, bytes %d?\n", bytes); 331 } 332 333 if(!slabsane_f(__FILE__, __LINE__, ret, bytes)) 334 panic("slaballoc: slabsane failed"); 335 #endif 336 337 assert(!((vir_bytes) ret % OBJALIGN)); 338 339 return ret; 340 } 341 342 /*===========================================================================* 343 * int objstats * 344 *===========================================================================*/ 345 static inline int objstats(void *mem, int bytes, 346 struct slabheader **sp, struct slabdata **fp, int *ip) 347 { 348 #if SANITYCHECKS 349 #define OBJSTATSCHECK(cond) \ 350 if(!(cond)) { \ 351 printf("VM: objstats: %s failed for ptr %p, %d bytes\n", \ 352 #cond, mem, bytes); \ 353 return EINVAL; \ 354 } 355 #else 356 #define OBJSTATSCHECK(cond) 357 #endif 358 359 struct slabheader *s; 360 struct slabdata *f; 361 int i; 362 363 assert(!(bytes % OBJALIGN)); 364 365 OBJSTATSCHECK((char *) mem >= (char *) VM_PAGE_SIZE); 366 367 #if SANITYCHECKS 368 if(*(u32_t *) mem == JUNK && !nojunkwarning) { 369 util_stacktrace(); 370 printf("VM: WARNING: JUNK seen in slab object, likely freed\n"); 371 } 372 #endif 373 /* Retrieve entry in slabs[]. */ 374 GETSLAB(bytes, s); 375 376 /* Round address down to VM_PAGE_SIZE boundary to get header. */ 377 f = (struct slabdata *) ((char *) mem - (vir_bytes) mem % VM_PAGE_SIZE); 378 379 #if SANITYCHECKS 380 OBJSTATSCHECK(f->sdh.magic1 == MAGIC1); 381 OBJSTATSCHECK(f->sdh.magic2 == MAGIC2); 382 #endif 383 384 /* Make sure it's in range. */ 385 OBJSTATSCHECK((char *) mem >= (char *) f->data); 386 OBJSTATSCHECK((char *) mem < (char *) f->data + sizeof(f->data)); 387 388 /* Get position. */ 389 i = (char *) mem - (char *) f->data; 390 OBJSTATSCHECK(!(i % bytes)); 391 i = i / bytes; 392 393 /* Make sure it is marked as allocated. */ 394 OBJSTATSCHECK(GETBIT(f, i)); 395 396 /* return values */ 397 *ip = i; 398 *fp = f; 399 *sp = s; 400 401 return OK; 402 } 403 404 /*===========================================================================* 405 * void *slabfree * 406 *===========================================================================*/ 407 void slabfree(void *mem, int bytes) 408 { 409 int i; 410 struct slabheader *s; 411 struct slabdata *f; 412 413 bytes = roundup(bytes, OBJALIGN); 414 415 SLABSANITYCHECK(SCL_FUNCTIONS); 416 417 if(objstats(mem, bytes, &s, &f, &i) != OK) { 418 panic("slabfree objstats failed"); 419 } 420 421 #if SANITYCHECKS 422 if(*(u32_t *) mem == JUNK) { 423 printf("VM: WARNING: likely double free, JUNK seen\n"); 424 } 425 #endif 426 427 #if SANITYCHECKS 428 #if MEMPROTECT 429 slabunlock(mem, bytes); 430 #endif 431 #if JUNKFREE 432 memset(mem, 0xa6, bytes); 433 #endif 434 *(u32_t *) mem = JUNK; 435 nojunkwarning++; 436 #if MEMPROTECT 437 slablock(mem, bytes); 438 #endif 439 nojunkwarning--; 440 assert(!nojunkwarning); 441 #endif 442 443 /* Free this data. */ 444 CLEARBIT(f, i); 445 446 /* Check if this slab changes lists. */ 447 if(f->sdh.nused == 0) { 448 UNLINKNODE(f); 449 if(f == s->list_head) s->list_head = f->sdh.next; 450 vm_freepages((vir_bytes) f, 1); 451 SLABSANITYCHECK(SCL_DETAIL); 452 } else if(f->sdh.nused == ITEMSPERPAGE(bytes)-1) { 453 ADDHEAD(f, s); 454 } 455 456 SLABSANITYCHECK(SCL_FUNCTIONS); 457 458 return; 459 } 460 461 #if MEMPROTECT 462 /*===========================================================================* 463 * void *slablock * 464 *===========================================================================*/ 465 void slablock(void *mem, int bytes) 466 { 467 int i; 468 struct slabheader *s; 469 struct slabdata *f; 470 471 bytes = roundup(bytes, OBJALIGN); 472 473 if(objstats(mem, bytes, &s, &f, &i) != OK) 474 panic("slablock objstats failed"); 475 476 SLABDATAUNWRITABLE(f); 477 478 return; 479 } 480 481 /*===========================================================================* 482 * void *slabunlock * 483 *===========================================================================*/ 484 void slabunlock(void *mem, int bytes) 485 { 486 int i; 487 struct slabheader *s; 488 struct slabdata *f; 489 490 bytes = roundup(bytes, OBJALIGN); 491 492 if(objstats(mem, bytes, &s, &f, &i) != OK) 493 panic("slabunlock objstats failed"); 494 495 SLABDATAWRITABLE(f, i); 496 497 return; 498 } 499 #endif 500 501 #if SANITYCHECKS 502 /*===========================================================================* 503 * void slabstats * 504 *===========================================================================*/ 505 void slabstats(void) 506 { 507 int s, totalbytes = 0; 508 static int n; 509 n++; 510 if(n%1000) return; 511 for(s = 0; s < SLABSIZES; s++) { 512 int b, t; 513 b = s + MINSIZE; 514 t = checklist(__FILE__, __LINE__, &slabs[s], b); 515 516 if(t > 0) { 517 int bytes = t * b; 518 printf("VMSTATS: %2d slabs: %d (%dkB)\n", b, t, bytes/1024); 519 totalbytes += bytes; 520 } 521 } 522 523 if(pages > 0) { 524 printf("VMSTATS: %dK net used in slab objects in %d pages (%dkB): %d%% utilization\n", 525 totalbytes/1024, pages, pages*VM_PAGE_SIZE/1024, 526 100 * totalbytes / (pages*VM_PAGE_SIZE)); 527 } 528 } 529 #endif 530