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