servers/vm/slaballoc.c

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