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