minix/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/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