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