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 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 *===========================================================================*/ 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 *===========================================================================*/ 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 *===========================================================================*/ 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 *===========================================================================*/ 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 *===========================================================================*/ 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 *===========================================================================*/ 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 *===========================================================================*/ 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 *===========================================================================*/ 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 *===========================================================================*/ 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