sys/kern/kern_objcache.c

   1 /*
   2  * Copyright (c) 2005 Jeffrey M. Hsu.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Jeffrey M. Hsu.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of The DragonFly Project nor the names of its
  16  *    contributors may be used to endorse or promote products derived
  17  *    from this software without specific, prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  22  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  23  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  24  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  25  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  27  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  * $DragonFly: src/sys/kern/kern_objcache.c,v 1.23 2008/10/26 04:29:19 sephe Exp $
  33  */
  34
  35 #include <sys/param.h>
  36 #include <sys/kernel.h>
  37 #include <sys/systm.h>
  38 #include <sys/callout.h>
  39 #include <sys/globaldata.h>
  40 #include <sys/malloc.h>
  41 #include <sys/queue.h>
  42 #include <sys/objcache.h>
  43 #include <sys/spinlock.h>
  44 #include <sys/thread.h>
  45 #include <sys/thread2.h>
  46 #include <sys/spinlock2.h>
  47
  48 static MALLOC_DEFINE(M_OBJCACHE, "objcache", "Object Cache");
  49 static MALLOC_DEFINE(M_OBJMAG, "objcache magazine", "Object Cache Magazine");
  50
  51 #define INITIAL_MAG_CAPACITY    64
  52
  53 struct magazine {
  54         int                      rounds;
  55         int                      capacity;
  56         SLIST_ENTRY(magazine)    nextmagazine;
  57         void                    *objects[];
  58 };
  59
  60 SLIST_HEAD(magazinelist, magazine);
  61
  62 /*
  63  * per-cluster cache of magazines
  64  *
  65  * All fields in this structure are protected by the spinlock.
  66  */
  67 struct magazinedepot {
  68         /*
  69          * The per-cpu object caches only exchanges completely full or
  70          * completely empty magazines with the depot layer, so only have
  71          * to cache these two types of magazines.
  72          */
  73         struct magazinelist     fullmagazines;
  74         struct magazinelist     emptymagazines;
  75         int                     magcapacity;
  76
  77         /* protect this structure */
  78         struct spinlock         spin;
  79
  80         /* magazines not yet allocated towards limit */
  81         int                     unallocated_objects;
  82
  83         /* infrequently used fields */
  84         int                     waiting;        /* waiting for another cpu to
  85                                                  * return a full magazine to
  86                                                  * the depot */
  87         int                     contested;      /* depot contention count */
  88 };
  89
  90 /*
  91  * per-cpu object cache
  92  * All fields in this structure are protected by crit_enter().
  93  */
  94 struct percpu_objcache {
  95         struct magazine *loaded_magazine;       /* active magazine */
  96         struct magazine *previous_magazine;     /* backup magazine */
  97
  98         /* statistics */
  99         int             gets_cumulative;        /* total calls to get */
 100         int             gets_null;              /* objcache_get returned NULL */
 101         int             puts_cumulative;        /* total calls to put */
 102         int             puts_othercluster;      /* returned to other cluster */
 103
 104         /* infrequently used fields */
 105         int             waiting;        /* waiting for a thread on this cpu to
 106                                          * return an obj to the per-cpu cache */
 107 };
 108
 109 /* only until we have NUMA cluster topology information XXX */
 110 #define MAXCLUSTERS 1
 111 #define myclusterid 0
 112 #define CLUSTER_OF(obj) 0
 113
 114 /*
 115  * Two-level object cache consisting of NUMA cluster-level depots of
 116  * fully loaded or completely empty magazines and cpu-level caches of
 117  * individual objects.
 118  */
 119 struct objcache {
 120         char                    *name;
 121
 122         /* object constructor and destructor from blank storage */
 123         objcache_ctor_fn        *ctor;
 124         objcache_dtor_fn        *dtor;
 125         void                    *privdata;
 126
 127         /* interface to underlying allocator */
 128         objcache_alloc_fn       *alloc;
 129         objcache_free_fn        *free;
 130         void                    *allocator_args;
 131
 132         LIST_ENTRY(objcache)    oc_next;
 133         int                     exhausted;      /* oops */
 134
 135         /* NUMA-cluster level caches */
 136         struct magazinedepot    depot[MAXCLUSTERS];
 137
 138         struct percpu_objcache  cache_percpu[];         /* per-cpu caches */
 139 };
 140
 141 static struct spinlock objcachelist_spin;
 142 static LIST_HEAD(objcachelist, objcache) allobjcaches;
 143
 144 static struct magazine *
 145 mag_alloc(int capacity)
 146 {
 147         struct magazine *mag;
 148
 149         mag = kmalloc(__offsetof(struct magazine, objects[capacity]),
 150                         M_OBJMAG, M_INTWAIT | M_ZERO);
 151         mag->capacity = capacity;
 152         mag->rounds = 0;
 153         return (mag);
 154 }
 155
 156 /*
 157  * Utility routine for objects that don't require any de-construction.
 158  */
 159
 160 static void
 161 null_dtor(void *obj, void *privdata)
 162 {
 163         /* do nothing */
 164 }
 165
 166 static boolean_t
 167 null_ctor(void *obj, void *privdata, int ocflags)
 168 {
 169         return TRUE;
 170 }
 171
 172 /*
 173  * Create an object cache.
 174  */
 175 struct objcache *
 176 objcache_create(const char *name, int *cluster_limit0, int mag_capacity,
 177                 objcache_ctor_fn *ctor, objcache_dtor_fn *dtor, void *privdata,
 178                 objcache_alloc_fn *alloc, objcache_free_fn *free,
 179                 void *allocator_args)
 180 {
 181         struct objcache *oc;
 182         struct magazinedepot *depot;
 183         int cpuid;
 184         int need;
 185         int factor;
 186         int nmagdepot;
 187         int i;
 188         int cluster_limit;
 189
 190         if (cluster_limit0 == NULL)
 191                 cluster_limit = 0;
 192         else
 193                 cluster_limit = *cluster_limit0;
 194
 195         /* allocate object cache structure */
 196         oc = kmalloc(__offsetof(struct objcache, cache_percpu[ncpus]),
 197                     M_OBJCACHE, M_WAITOK | M_ZERO);
 198         oc->name = kstrdup(name, M_TEMP);
 199         oc->ctor = ctor ? ctor : null_ctor;
 200         oc->dtor = dtor ? dtor : null_dtor;
 201         oc->privdata = privdata;
 202         oc->free = free;
 203         oc->allocator_args = allocator_args;
 204
 205         /* initialize depots */
 206         depot = &oc->depot[0];
 207
 208         spin_init(&depot->spin);
 209         SLIST_INIT(&depot->fullmagazines);
 210         SLIST_INIT(&depot->emptymagazines);
 211
 212         if (mag_capacity == 0)
 213                 mag_capacity = INITIAL_MAG_CAPACITY;
 214
 215         /*
 216          * The cluster_limit must be sufficient to have three magazines per
 217          * cpu.  If we have a lot of cpus the mag_capacity might just be
 218          * too big, reduce it if necessary.
 219          *
 220          * Each cpu can hold up to two magazines, with the remainder in the
 221          * depot.  If many objects are allocated fewer magazines are
 222          * available.  We have to make sure that each cpu has access to
 223          * free objects until the object cache hits 75% of its limit.
 224          */
 225         if (cluster_limit == 0) {
 226                 depot->unallocated_objects = -1;
 227         } else {
 228                 factor = 8;
 229                 need = mag_capacity * ncpus * factor;
 230                 if (cluster_limit < need && mag_capacity > 16) {
 231                         kprintf("objcache(%s): too small for ncpus"
 232                                 ", adjusting mag_capacity %d->",
 233                                 name, mag_capacity);
 234                         while (need > cluster_limit && mag_capacity > 16) {
 235                                 mag_capacity >>= 1;
 236                                 need = mag_capacity * ncpus * factor;
 237                         }
 238                         kprintf("%d\n", mag_capacity);
 239                 }
 240                 if (cluster_limit < need) {
 241                         kprintf("objcache(%s): too small for ncpus"
 242                                 ", adjusting cluster_limit %d->%d\n",
 243                                 name, cluster_limit, need);
 244                         cluster_limit = need;
 245                 }
 246                 depot->unallocated_objects = cluster_limit;
 247         }
 248         depot->magcapacity = mag_capacity;
 249         oc->alloc = alloc;
 250
 251         /* initialize per-cpu caches */
 252         for (cpuid = 0; cpuid < ncpus; cpuid++) {
 253                 struct percpu_objcache *cache_percpu = &oc->cache_percpu[cpuid];
 254
 255                 cache_percpu->loaded_magazine = mag_alloc(mag_capacity);
 256                 cache_percpu->previous_magazine = mag_alloc(mag_capacity);
 257         }
 258
 259         /* compute initial number of empty magazines in depot */
 260         nmagdepot = 0;
 261         if (cluster_limit > 0) {
 262                 /* max number of magazines in depot */
 263                 nmagdepot = (cluster_limit - ncpus * 2 * mag_capacity) /
 264                                 mag_capacity;
 265
 266                 /* retain at most 50% of the limit */
 267                 nmagdepot /= 2;
 268         }
 269         /* bound result to acceptable range */
 270         if (nmagdepot < 2)
 271                 nmagdepot = 2;
 272         if (nmagdepot > 1000)
 273                 nmagdepot = 1000;
 274
 275         /* put empty magazines in depot */
 276         for (i = 0; i < nmagdepot; i++) {
 277                 struct magazine *mag = mag_alloc(mag_capacity);
 278                 SLIST_INSERT_HEAD(&depot->emptymagazines, mag, nextmagazine);
 279         }
 280
 281         spin_lock(&objcachelist_spin);
 282         LIST_INSERT_HEAD(&allobjcaches, oc, oc_next);
 283         spin_unlock(&objcachelist_spin);
 284
 285         if (cluster_limit0 != NULL)
 286                 *cluster_limit0 = cluster_limit;
 287         return (oc);
 288 }
 289
 290 struct objcache *
 291 objcache_create_simple(malloc_type_t mtype, size_t objsize)
 292 {
 293         struct objcache_malloc_args *margs;
 294         struct objcache *oc;
 295
 296         margs = kmalloc(sizeof(*margs), M_OBJCACHE, M_WAITOK|M_ZERO);
 297         margs->objsize = objsize;
 298         margs->mtype = mtype;
 299         oc = objcache_create(mtype->ks_shortdesc, NULL, 0,
 300                              NULL, NULL, NULL,
 301                              objcache_malloc_alloc, objcache_malloc_free,
 302                              margs);
 303         return (oc);
 304 }
 305
 306 struct objcache *
 307 objcache_create_mbacked(malloc_type_t mtype, size_t objsize,
 308                         int *cluster_limit, int mag_capacity,
 309                         objcache_ctor_fn *ctor, objcache_dtor_fn *dtor,
 310                         void *privdata)
 311 {
 312         struct objcache_malloc_args *margs;
 313         struct objcache *oc;
 314
 315         margs = kmalloc(sizeof(*margs), M_OBJCACHE, M_WAITOK|M_ZERO);
 316         margs->objsize = objsize;
 317         margs->mtype = mtype;
 318         oc = objcache_create(mtype->ks_shortdesc,
 319                              cluster_limit, mag_capacity,
 320                              ctor, dtor, privdata,
 321                              objcache_malloc_alloc, objcache_malloc_free,
 322                              margs);
 323         return(oc);
 324 }
 325
 326
 327 #define MAGAZINE_EMPTY(mag)     (mag->rounds == 0)
 328 #define MAGAZINE_NOTEMPTY(mag)  (mag->rounds != 0)
 329 #define MAGAZINE_FULL(mag)      (mag->rounds == mag->capacity)
 330
 331 #define swap(x, y)      ({ struct magazine *t = x; x = y; y = t; })
 332
 333 /*
 334  * Get an object from the object cache.
 335  *
 336  * WARNING!  ocflags are only used when we have to go to the underlying
 337  * allocator, so we cannot depend on flags such as M_ZERO.
 338  */
 339 void *
 340 objcache_get(struct objcache *oc, int ocflags)
 341 {
 342         struct percpu_objcache *cpucache = &oc->cache_percpu[mycpuid];
 343         struct magazine *loadedmag;
 344         struct magazine *emptymag;
 345         void *obj;
 346         struct magazinedepot *depot;
 347
 348         KKASSERT((ocflags & M_ZERO) == 0);
 349         crit_enter();
 350         ++cpucache->gets_cumulative;
 351
 352 retry:
 353         /*
 354          * Loaded magazine has an object.  This is the hot path.
 355          * It is lock-free and uses a critical section to block
 356          * out interrupt handlers on the same processor.
 357          */
 358         loadedmag = cpucache->loaded_magazine;
 359         if (MAGAZINE_NOTEMPTY(loadedmag)) {
 360                 obj = loadedmag->objects[--loadedmag->rounds];
 361                 crit_exit();
 362                 return (obj);
 363         }
 364
 365         /* Previous magazine has an object. */
 366         if (MAGAZINE_NOTEMPTY(cpucache->previous_magazine)) {
 367                 swap(cpucache->loaded_magazine, cpucache->previous_magazine);
 368                 loadedmag = cpucache->loaded_magazine;
 369                 obj = loadedmag->objects[--loadedmag->rounds];
 370                 crit_exit();
 371                 return (obj);
 372         }
 373
 374         /*
 375          * Both magazines empty.  Get a full magazine from the depot and
 376          * move one of the empty ones to the depot.
 377          *
 378          * Obtain the depot spinlock.
 379          *
 380          * NOTE: Beyond this point, M_* flags are handled via oc->alloc()
 381          */
 382         depot = &oc->depot[myclusterid];
 383         spin_lock(&depot->spin);
 384
 385         /*
 386          * Recheck the cpucache after obtaining the depot spinlock.  This
 387          * shouldn't be necessary now but don't take any chances.
 388          */
 389         if (MAGAZINE_NOTEMPTY(cpucache->loaded_magazine) ||
 390             MAGAZINE_NOTEMPTY(cpucache->previous_magazine)
 391         ) {
 392                 spin_unlock(&depot->spin);
 393                 goto retry;
 394         }
 395
 396         /* Check if depot has a full magazine. */
 397         if (!SLIST_EMPTY(&depot->fullmagazines)) {
 398                 emptymag = cpucache->previous_magazine;
 399                 cpucache->previous_magazine = cpucache->loaded_magazine;
 400                 cpucache->loaded_magazine = SLIST_FIRST(&depot->fullmagazines);
 401                 SLIST_REMOVE_HEAD(&depot->fullmagazines, nextmagazine);
 402
 403                 /*
 404                  * Return emptymag to the depot.
 405                  */
 406                 KKASSERT(MAGAZINE_EMPTY(emptymag));
 407                 SLIST_INSERT_HEAD(&depot->emptymagazines,
 408                                   emptymag, nextmagazine);
 409                 spin_unlock(&depot->spin);
 410                 goto retry;
 411         }
 412
 413         /*
 414          * The depot does not have any non-empty magazines.  If we have
 415          * not hit our object limit we can allocate a new object using
 416          * the back-end allocator.
 417          *
 418          * note: unallocated_objects can be initialized to -1, which has
 419          * the effect of removing any allocation limits.
 420          */
 421         if (depot->unallocated_objects) {
 422                 --depot->unallocated_objects;
 423                 spin_unlock(&depot->spin);
 424                 crit_exit();
 425
 426                 obj = oc->alloc(oc->allocator_args, ocflags);
 427                 if (obj) {
 428                         if (oc->ctor(obj, oc->privdata, ocflags))
 429                                 return (obj);
 430                         oc->free(obj, oc->allocator_args);
 431                         obj = NULL;
 432                 }
 433                 if (obj == NULL) {
 434                         spin_lock(&depot->spin);
 435                         ++depot->unallocated_objects;
 436                         spin_unlock(&depot->spin);
 437                         if (depot->waiting)
 438                                 wakeup(depot);
 439
 440                         crit_enter();
 441                         /*
 442                          * makes debugging easier when gets_cumulative does
 443                          * not include gets_null.
 444                          */
 445                         ++cpucache->gets_null;
 446                         --cpucache->gets_cumulative;
 447                         crit_exit();
 448                 }
 449                 return(obj);
 450         }
 451         if (oc->exhausted == 0) {
 452                 kprintf("Warning, objcache(%s): Exhausted!\n", oc->name);
 453                 oc->exhausted = 1;
 454         }
 455
 456         /*
 457          * Otherwise block if allowed to.
 458          */
 459         if ((ocflags & (M_WAITOK|M_NULLOK)) == M_WAITOK) {
 460                 ++cpucache->waiting;
 461                 ++depot->waiting;
 462                 ssleep(depot, &depot->spin, 0, "objcache_get", 0);
 463                 --cpucache->waiting;
 464                 --depot->waiting;
 465                 spin_unlock(&depot->spin);
 466                 goto retry;
 467         }
 468
 469         /*
 470          * Otherwise fail
 471          */
 472         ++cpucache->gets_null;
 473         --cpucache->gets_cumulative;
 474         crit_exit();
 475         spin_unlock(&depot->spin);
 476         return (NULL);
 477 }
 478
 479 /*
 480  * Wrapper for malloc allocation routines.
 481  */
 482 void *
 483 objcache_malloc_alloc(void *allocator_args, int ocflags)
 484 {
 485         struct objcache_malloc_args *alloc_args = allocator_args;
 486
 487         return (kmalloc(alloc_args->objsize, alloc_args->mtype,
 488                        ocflags & OC_MFLAGS));
 489 }
 490
 491 void
 492 objcache_malloc_free(void *obj, void *allocator_args)
 493 {
 494         struct objcache_malloc_args *alloc_args = allocator_args;
 495
 496         kfree(obj, alloc_args->mtype);
 497 }
 498
 499 /*
 500  * Wrapper for allocation policies that pre-allocate at initialization time
 501  * and don't do run-time allocation.
 502  */
 503 void *
 504 objcache_nop_alloc(void *allocator_args, int ocflags)
 505 {
 506         return (NULL);
 507 }
 508
 509 void
 510 objcache_nop_free(void *obj, void *allocator_args)
 511 {
 512 }
 513
 514 /*
 515  * Return an object to the object cache.
 516  */
 517 void
 518 objcache_put(struct objcache *oc, void *obj)
 519 {
 520         struct percpu_objcache *cpucache = &oc->cache_percpu[mycpuid];
 521         struct magazine *loadedmag;
 522         struct magazinedepot *depot;
 523
 524         crit_enter();
 525         ++cpucache->puts_cumulative;
 526
 527         if (CLUSTER_OF(obj) != myclusterid) {
 528 #ifdef notyet
 529                 /* use lazy IPI to send object to owning cluster XXX todo */
 530                 ++cpucache->puts_othercluster;
 531                 crit_exit();
 532                 return;
 533 #endif
 534         }
 535
 536 retry:
 537         /*
 538          * Free slot available in loaded magazine.  This is the hot path.
 539          * It is lock-free and uses a critical section to block out interrupt
 540          * handlers on the same processor.
 541          */
 542         loadedmag = cpucache->loaded_magazine;
 543         if (!MAGAZINE_FULL(loadedmag)) {
 544                 loadedmag->objects[loadedmag->rounds++] = obj;
 545                 if (cpucache->waiting)
 546                         wakeup_mycpu(&oc->depot[myclusterid]);
 547                 crit_exit();
 548                 return;
 549         }
 550
 551         /*
 552          * Current magazine full, but previous magazine has room.  XXX
 553          */
 554         if (!MAGAZINE_FULL(cpucache->previous_magazine)) {
 555                 swap(cpucache->loaded_magazine, cpucache->previous_magazine);
 556                 loadedmag = cpucache->loaded_magazine;
 557                 loadedmag->objects[loadedmag->rounds++] = obj;
 558                 if (cpucache->waiting)
 559                         wakeup_mycpu(&oc->depot[myclusterid]);
 560                 crit_exit();
 561                 return;
 562         }
 563
 564         /*
 565          * Both magazines full.  Get an empty magazine from the depot and
 566          * move a full loaded magazine to the depot.  Even though the
 567          * magazine may wind up with space available after we block on
 568          * the spinlock, we still cycle it through to avoid the non-optimal
 569          * corner-case.
 570          *
 571          * Obtain the depot spinlock.
 572          */
 573         depot = &oc->depot[myclusterid];
 574         spin_lock(&depot->spin);
 575
 576         /*
 577          * If an empty magazine is available in the depot, cycle it
 578          * through and retry.
 579          */
 580         if (!SLIST_EMPTY(&depot->emptymagazines)) {
 581                 loadedmag = cpucache->previous_magazine;
 582                 cpucache->previous_magazine = cpucache->loaded_magazine;
 583                 cpucache->loaded_magazine = SLIST_FIRST(&depot->emptymagazines);
 584                 SLIST_REMOVE_HEAD(&depot->emptymagazines, nextmagazine);
 585
 586                 /*
 587                  * Return loadedmag to the depot.  Due to blocking it may
 588                  * not be entirely full and could even be empty.
 589                  */
 590                 if (MAGAZINE_EMPTY(loadedmag)) {
 591                         SLIST_INSERT_HEAD(&depot->emptymagazines,
 592                                           loadedmag, nextmagazine);
 593                         spin_unlock(&depot->spin);
 594                 } else {
 595                         SLIST_INSERT_HEAD(&depot->fullmagazines,
 596                                           loadedmag, nextmagazine);
 597                         spin_unlock(&depot->spin);
 598                         if (depot->waiting)
 599                                 wakeup(depot);
 600                 }
 601                 goto retry;
 602         }
 603
 604         /*
 605          * An empty mag is not available.  This is a corner case which can
 606          * occur due to cpus holding partially full magazines.  Do not try
 607          * to allocate a mag, just free the object.
 608          */
 609         ++depot->unallocated_objects;
 610         spin_unlock(&depot->spin);
 611         if (depot->waiting)
 612                 wakeup(depot);
 613         crit_exit();
 614         oc->dtor(obj, oc->privdata);
 615         oc->free(obj, oc->allocator_args);
 616 }
 617
 618 /*
 619  * The object is being put back into the cache, but the caller has
 620  * indicated that the object is not in any shape to be reused and should
 621  * be dtor'd immediately.
 622  */
 623 void
 624 objcache_dtor(struct objcache *oc, void *obj)
 625 {
 626         struct magazinedepot *depot;
 627
 628         depot = &oc->depot[myclusterid];
 629         spin_lock(&depot->spin);
 630         ++depot->unallocated_objects;
 631         spin_unlock(&depot->spin);
 632         if (depot->waiting)
 633                 wakeup(depot);
 634         oc->dtor(obj, oc->privdata);
 635         oc->free(obj, oc->allocator_args);
 636 }
 637
 638 /*
 639  * Deallocate all objects in a magazine and free the magazine if requested.
 640  * When freeit is TRUE the magazine must already be disassociated from the
 641  * depot.
 642  *
 643  * Must be called with a critical section held when called with a per-cpu
 644  * magazine.  The magazine may be indirectly modified during the loop.
 645  *
 646  * If the magazine moves during a dtor the operation is aborted.  This is
 647  * only allowed when freeit is FALSE.
 648  *
 649  * The number of objects freed is returned.
 650  */
 651 static int
 652 mag_purge(struct objcache *oc, struct magazine **magp, int freeit)
 653 {
 654         struct magazine *mag = *magp;
 655         int count;
 656         void *obj;
 657
 658         count = 0;
 659         while (mag->rounds) {
 660                 obj = mag->objects[--mag->rounds];
 661                 oc->dtor(obj, oc->privdata);            /* MAY BLOCK */
 662                 oc->free(obj, oc->allocator_args);      /* MAY BLOCK */
 663                 ++count;
 664
 665                 /*
 666                  * Cycle for interrupts.
 667                  */
 668                 if ((count & 15) == 0) {
 669                         crit_exit();
 670                         crit_enter();
 671                 }
 672
 673                 /*
 674                  * mag may have become invalid either due to dtor/free
 675                  * blocking or interrupt cycling, do not derefernce it
 676                  * until we check.
 677                  */
 678                 if (*magp != mag) {
 679                         kprintf("mag_purge: mag ripped out\n");
 680                         break;
 681                 }
 682         }
 683         if (freeit) {
 684                 KKASSERT(*magp == mag);
 685                 *magp = NULL;
 686                 kfree(mag, M_OBJMAG);
 687         }
 688         return(count);
 689 }
 690
 691 /*
 692  * Disassociate zero or more magazines from a magazine list associated with
 693  * the depot, update the depot, and move the magazines to a temporary
 694  * list.
 695  *
 696  * The caller must check the depot for waiters and wake it up, typically
 697  * after disposing of the magazines this function loads onto the temporary
 698  * list.
 699  */
 700 static void
 701 maglist_disassociate(struct magazinedepot *depot, struct magazinelist *maglist,
 702                      struct magazinelist *tmplist, boolean_t purgeall)
 703 {
 704         struct magazine *mag;
 705
 706         while ((mag = SLIST_FIRST(maglist)) != NULL) {
 707                 SLIST_REMOVE_HEAD(maglist, nextmagazine);
 708                 SLIST_INSERT_HEAD(tmplist, mag, nextmagazine);
 709                 depot->unallocated_objects += mag->rounds;
 710         }
 711 }
 712
 713 /*
 714  * Deallocate all magazines and their contents from the passed temporary
 715  * list.  The magazines have already been accounted for by their depots.
 716  *
 717  * The total number of rounds freed is returned.  This number is typically
 718  * only used to determine whether a wakeup on the depot is needed or not.
 719  */
 720 static int
 721 maglist_purge(struct objcache *oc, struct magazinelist *maglist)
 722 {
 723         struct magazine *mag;
 724         int count = 0;
 725
 726         /*
 727          * can't use SLIST_FOREACH because blocking releases the depot
 728          * spinlock
 729          */
 730         crit_enter();
 731         while ((mag = SLIST_FIRST(maglist)) != NULL) {
 732                 SLIST_REMOVE_HEAD(maglist, nextmagazine);
 733                 count += mag_purge(oc, &mag, TRUE);
 734         }
 735         crit_exit();
 736         return(count);
 737 }
 738
 739 /*
 740  * De-allocates all magazines on the full and empty magazine lists.
 741  *
 742  * Because this routine is called with a spinlock held, the magazines
 743  * can only be disassociated and moved to a temporary list, not freed.
 744  *
 745  * The caller is responsible for freeing the magazines.
 746  */
 747 static void
 748 depot_disassociate(struct magazinedepot *depot, struct magazinelist *tmplist)
 749 {
 750         maglist_disassociate(depot, &depot->fullmagazines, tmplist, TRUE);
 751         maglist_disassociate(depot, &depot->emptymagazines, tmplist, TRUE);
 752 }
 753
 754 #ifdef notneeded
 755 void
 756 objcache_reclaim(struct objcache *oc)
 757 {
 758         struct percpu_objcache *cache_percpu = &oc->cache_percpu[myclusterid];
 759         struct magazinedepot *depot = &oc->depot[myclusterid];
 760         struct magazinelist tmplist;
 761         int count;
 762
 763         SLIST_INIT(&tmplist);
 764         crit_enter();
 765         count = mag_purge(oc, &cache_percpu->loaded_magazine, FALSE);
 766         count += mag_purge(oc, &cache_percpu->previous_magazine, FALSE);
 767         crit_exit();
 768
 769         spin_lock(&depot->spin);
 770         depot->unallocated_objects += count;
 771         depot_disassociate(depot, &tmplist);
 772         spin_unlock(&depot->spin);
 773         count += maglist_purge(oc, &tmplist);
 774         if (count && depot->waiting)
 775                 wakeup(depot);
 776 }
 777 #endif
 778
 779 /*
 780  * Try to free up some memory.  Return as soon as some free memory is found.
 781  * For each object cache on the reclaim list, first try the current per-cpu
 782  * cache, then the full magazine depot.
 783  */
 784 boolean_t
 785 objcache_reclaimlist(struct objcache *oclist[], int nlist, int ocflags)
 786 {
 787         struct objcache *oc;
 788         struct percpu_objcache *cpucache;
 789         struct magazinedepot *depot;
 790         struct magazinelist tmplist;
 791         int i, count;
 792
 793         kprintf("objcache_reclaimlist\n");
 794
 795         SLIST_INIT(&tmplist);
 796
 797         for (i = 0; i < nlist; i++) {
 798                 oc = oclist[i];
 799                 cpucache = &oc->cache_percpu[mycpuid];
 800                 depot = &oc->depot[myclusterid];
 801
 802                 crit_enter();
 803                 count = mag_purge(oc, &cpucache->loaded_magazine, FALSE);
 804                 if (count == 0)
 805                         count += mag_purge(oc, &cpucache->previous_magazine, FALSE);
 806                 crit_exit();
 807                 if (count > 0) {
 808                         spin_lock(&depot->spin);
 809                         depot->unallocated_objects += count;
 810                         spin_unlock(&depot->spin);
 811                         if (depot->waiting)
 812                                 wakeup(depot);
 813                         return (TRUE);
 814                 }
 815                 spin_lock(&depot->spin);
 816                 maglist_disassociate(depot, &depot->fullmagazines,
 817                                      &tmplist, FALSE);
 818                 spin_unlock(&depot->spin);
 819                 count = maglist_purge(oc, &tmplist);
 820                 if (count > 0) {
 821                         if (depot->waiting)
 822                                 wakeup(depot);
 823                         return (TRUE);
 824                 }
 825         }
 826         return (FALSE);
 827 }
 828
 829 /*
 830  * Destroy an object cache.  Must have no existing references.
 831  */
 832 void
 833 objcache_destroy(struct objcache *oc)
 834 {
 835         struct percpu_objcache *cache_percpu;
 836         struct magazinedepot *depot;
 837         int clusterid, cpuid;
 838         struct magazinelist tmplist;
 839
 840         spin_lock(&objcachelist_spin);
 841         LIST_REMOVE(oc, oc_next);
 842         spin_unlock(&objcachelist_spin);
 843
 844         SLIST_INIT(&tmplist);
 845         for (clusterid = 0; clusterid < MAXCLUSTERS; clusterid++) {
 846                 depot = &oc->depot[clusterid];
 847                 spin_lock(&depot->spin);
 848                 depot_disassociate(depot, &tmplist);
 849                 spin_unlock(&depot->spin);
 850         }
 851         maglist_purge(oc, &tmplist);
 852
 853         for (cpuid = 0; cpuid < ncpus; cpuid++) {
 854                 cache_percpu = &oc->cache_percpu[cpuid];
 855
 856                 crit_enter();
 857                 mag_purge(oc, &cache_percpu->loaded_magazine, TRUE);
 858                 mag_purge(oc, &cache_percpu->previous_magazine, TRUE);
 859                 crit_exit();
 860                 cache_percpu->loaded_magazine = NULL;
 861                 cache_percpu->previous_magazine = NULL;
 862                 /* don't bother adjusting depot->unallocated_objects */
 863         }
 864
 865         kfree(oc->name, M_TEMP);
 866         kfree(oc, M_OBJCACHE);
 867 }
 868
 869 #if 0
 870 /*
 871  * Populate the per-cluster depot with elements from a linear block
 872  * of memory.  Must be called for individually for each cluster.
 873  * Populated depots should not be destroyed.
 874  */
 875 void
 876 objcache_populate_linear(struct objcache *oc, void *base, int nelts, int size)
 877 {
 878         char *p = base;
 879         char *end = (char *)base + (nelts * size);
 880         struct magazinedepot *depot = &oc->depot[myclusterid];
 881         struct magazine *emptymag = mag_alloc(depot->magcapcity);
 882
 883         while (p < end) {
 884                 emptymag->objects[emptymag->rounds++] = p;
 885                 if (MAGAZINE_FULL(emptymag)) {
 886                         spin_lock_wr(&depot->spin);
 887                         SLIST_INSERT_HEAD(&depot->fullmagazines, emptymag,
 888                                           nextmagazine);
 889                         depot->unallocated_objects += emptymag->rounds;
 890                         spin_unlock_wr(&depot->spin);
 891                         if (depot->waiting)
 892                                 wakeup(depot);
 893                         emptymag = mag_alloc(depot->magcapacity);
 894                 }
 895                 p += size;
 896         }
 897         if (MAGAZINE_EMPTY(emptymag)) {
 898                 crit_enter();
 899                 mag_purge(oc, &emptymag, TRUE);
 900                 crit_exit();
 901         } else {
 902                 spin_lock_wr(&depot->spin);
 903                 SLIST_INSERT_HEAD(&depot->fullmagazines, emptymag,
 904                                   nextmagazine);
 905                 depot->unallocated_objects += emptymag->rounds;
 906                 spin_unlock_wr(&depot->spin);
 907                 if (depot->waiting)
 908                         wakeup(depot);
 909                 emptymag = mag_alloc(depot->magcapacity);
 910         }
 911 }
 912 #endif
 913
 914 #if 0
 915 /*
 916  * Check depot contention once a minute.
 917  * 2 contested locks per second allowed.
 918  */
 919 static int objcache_rebalance_period;
 920 static const int objcache_contention_rate = 120;
 921 static struct callout objcache_callout;
 922
 923 #define MAXMAGSIZE 512
 924
 925 /*
 926  * Check depot contention and increase magazine size if necessary.
 927  */
 928 static void
 929 objcache_timer(void *dummy)
 930 {
 931         struct objcache *oc;
 932         struct magazinedepot *depot;
 933         struct magazinelist tmplist;
 934
 935         XXX we need to detect when an objcache is destroyed out from under
 936             us XXX
 937
 938         SLIST_INIT(&tmplist);
 939
 940         spin_lock_wr(&objcachelist_spin);
 941         LIST_FOREACH(oc, &allobjcaches, oc_next) {
 942                 depot = &oc->depot[myclusterid];
 943                 if (depot->magcapacity < MAXMAGSIZE) {
 944                         if (depot->contested > objcache_contention_rate) {
 945                                 spin_lock_wr(&depot->spin);
 946                                 depot_disassociate(depot, &tmplist);
 947                                 depot->magcapacity *= 2;
 948                                 spin_unlock_wr(&depot->spin);
 949                                 kprintf("objcache_timer: increasing cache %s"
 950                                        " magsize to %d, contested %d times\n",
 951                                     oc->name, depot->magcapacity,
 952                                     depot->contested);
 953                         }
 954                         depot->contested = 0;
 955                 }
 956                 spin_unlock_wr(&objcachelist_spin);
 957                 if (maglist_purge(oc, &tmplist) > 0 && depot->waiting)
 958                         wakeup(depot);
 959                 spin_lock_wr(&objcachelist_spin);
 960         }
 961         spin_unlock_wr(&objcachelist_spin);
 962
 963         callout_reset(&objcache_callout, objcache_rebalance_period,
 964                       objcache_timer, NULL);
 965 }
 966
 967 #endif
 968
 969 static void
 970 objcache_init(void)
 971 {
 972         spin_init(&objcachelist_spin);
 973 #if 0
 974         callout_init(&objcache_callout);
 975         objcache_rebalance_period = 60 * hz;
 976         callout_reset(&objcache_callout, objcache_rebalance_period,
 977                       objcache_timer, NULL);
 978 #endif
 979 }
 980 SYSINIT(objcache, SI_BOOT2_OBJCACHE, SI_ORDER_FIRST, objcache_init, 0);