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 } __cachealign;
  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 } __cachealign;
 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_limit, int nom_cache,
 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 nmagdepot;
 185         int mag_capacity;
 186         int i;
 187
 188         /*
 189          * Allocate object cache structure
 190          */
 191         oc = kmalloc_cachealign(
 192             __offsetof(struct objcache, cache_percpu[ncpus]),
 193             M_OBJCACHE, M_WAITOK | M_ZERO);
 194         oc->name = kstrdup(name, M_TEMP);
 195         oc->ctor = ctor ? ctor : null_ctor;
 196         oc->dtor = dtor ? dtor : null_dtor;
 197         oc->privdata = privdata;
 198         oc->alloc = alloc;
 199         oc->free = free;
 200         oc->allocator_args = allocator_args;
 201
 202         /*
 203          * Initialize depot list(s).
 204          */
 205         depot = &oc->depot[0];
 206
 207         spin_init(&depot->spin);
 208         SLIST_INIT(&depot->fullmagazines);
 209         SLIST_INIT(&depot->emptymagazines);
 210
 211         /*
 212          * Figure out the nominal number of free objects to cache and
 213          * the magazine capacity.  By default we want to cache up to
 214          * half the cluster_limit.  If there is no cluster_limit then
 215          * we want to cache up to 128 objects.
 216          */
 217         if (nom_cache == 0)
 218                 nom_cache = cluster_limit / 2;
 219         if (cluster_limit && nom_cache > cluster_limit)
 220                 nom_cache = cluster_limit;
 221         if (nom_cache == 0)
 222                 nom_cache = INITIAL_MAG_CAPACITY * 2;
 223
 224         /*
 225          * Magazine capacity for 2 active magazines per cpu plus 2
 226          * magazines in the depot.  Minimum capacity is 4 objects.
 227          */
 228         mag_capacity = nom_cache / (ncpus + 1) / 2 + 1;
 229         if (mag_capacity > 128)
 230                 mag_capacity = 128;
 231         if (mag_capacity < 4)
 232                 mag_capacity = 4;
 233         depot->magcapacity = mag_capacity;
 234
 235         /*
 236          * The cluster_limit must be sufficient to have two magazines per
 237          * cpu plus at least two magazines in the depot.  However, because
 238          * partial magazines can stay on the cpus what we really need here
 239          * is to specify the number of extra magazines we allocate for the
 240          * depot.
 241          */
 242         if (cluster_limit == 0) {
 243                 depot->unallocated_objects = -1;
 244         } else {
 245                 depot->unallocated_objects = ncpus * mag_capacity * 2 +
 246                                              cluster_limit;
 247         }
 248
 249         /*
 250          * Initialize per-cpu caches
 251          */
 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         /*
 260          * Compute how many empty magazines to place in the depot.  This
 261          * determines the retained cache size and is based on nom_cache.
 262          *
 263          * The actual cache size is larger because there are two magazines
 264          * for each cpu as well but those can be in any fill state so we
 265          * just can't count them.
 266          *
 267          * There is a minimum of two magazines in the depot.
 268          */
 269         nmagdepot = nom_cache / mag_capacity + 1;
 270         if (nmagdepot < 2)
 271                 nmagdepot = 2;
 272         if (bootverbose) {
 273                 kprintf("ndepotmags=%-3d x mag_cap=%-3d for %s\n",
 274                         nmagdepot, mag_capacity, name);
 275         }
 276
 277         /*
 278          * Put empty magazines in depot
 279          */
 280         for (i = 0; i < nmagdepot; i++) {
 281                 struct magazine *mag = mag_alloc(mag_capacity);
 282                 SLIST_INSERT_HEAD(&depot->emptymagazines, mag, nextmagazine);
 283         }
 284
 285         spin_lock(&objcachelist_spin);
 286         LIST_INSERT_HEAD(&allobjcaches, oc, oc_next);
 287         spin_unlock(&objcachelist_spin);
 288
 289         return (oc);
 290 }
 291
 292 struct objcache *
 293 objcache_create_simple(malloc_type_t mtype, size_t objsize)
 294 {
 295         struct objcache_malloc_args *margs;
 296         struct objcache *oc;
 297
 298         margs = kmalloc(sizeof(*margs), M_OBJCACHE, M_WAITOK|M_ZERO);
 299         margs->objsize = objsize;
 300         margs->mtype = mtype;
 301         oc = objcache_create(mtype->ks_shortdesc, 0, 0,
 302                              NULL, NULL, NULL,
 303                              objcache_malloc_alloc, objcache_malloc_free,
 304                              margs);
 305         return (oc);
 306 }
 307
 308 struct objcache *
 309 objcache_create_mbacked(malloc_type_t mtype, size_t objsize,
 310                         int cluster_limit, int nom_cache,
 311                         objcache_ctor_fn *ctor, objcache_dtor_fn *dtor,
 312                         void *privdata)
 313 {
 314         struct objcache_malloc_args *margs;
 315         struct objcache *oc;
 316
 317         margs = kmalloc(sizeof(*margs), M_OBJCACHE, M_WAITOK|M_ZERO);
 318         margs->objsize = objsize;
 319         margs->mtype = mtype;
 320         oc = objcache_create(mtype->ks_shortdesc,
 321                              cluster_limit, nom_cache,
 322                              ctor, dtor, privdata,
 323                              objcache_malloc_alloc, objcache_malloc_free,
 324                              margs);
 325         return(oc);
 326 }
 327
 328
 329 #define MAGAZINE_EMPTY(mag)     (mag->rounds == 0)
 330 #define MAGAZINE_NOTEMPTY(mag)  (mag->rounds != 0)
 331 #define MAGAZINE_FULL(mag)      (mag->rounds == mag->capacity)
 332
 333 #define swap(x, y)      ({ struct magazine *t = x; x = y; y = t; })
 334
 335 /*
 336  * Get an object from the object cache.
 337  *
 338  * WARNING!  ocflags are only used when we have to go to the underlying
 339  * allocator, so we cannot depend on flags such as M_ZERO.
 340  */
 341 void *
 342 objcache_get(struct objcache *oc, int ocflags)
 343 {
 344         struct percpu_objcache *cpucache = &oc->cache_percpu[mycpuid];
 345         struct magazine *loadedmag;
 346         struct magazine *emptymag;
 347         void *obj;
 348         struct magazinedepot *depot;
 349
 350         KKASSERT((ocflags & M_ZERO) == 0);
 351         crit_enter();
 352         ++cpucache->gets_cumulative;
 353
 354 retry:
 355         /*
 356          * Loaded magazine has an object.  This is the hot path.
 357          * It is lock-free and uses a critical section to block
 358          * out interrupt handlers on the same processor.
 359          */
 360         loadedmag = cpucache->loaded_magazine;
 361         if (MAGAZINE_NOTEMPTY(loadedmag)) {
 362                 obj = loadedmag->objects[--loadedmag->rounds];
 363                 crit_exit();
 364                 return (obj);
 365         }
 366
 367         /* Previous magazine has an object. */
 368         if (MAGAZINE_NOTEMPTY(cpucache->previous_magazine)) {
 369                 swap(cpucache->loaded_magazine, cpucache->previous_magazine);
 370                 loadedmag = cpucache->loaded_magazine;
 371                 obj = loadedmag->objects[--loadedmag->rounds];
 372                 crit_exit();
 373                 return (obj);
 374         }
 375
 376         /*
 377          * Both magazines empty.  Get a full magazine from the depot and
 378          * move one of the empty ones to the depot.
 379          *
 380          * Obtain the depot spinlock.
 381          *
 382          * NOTE: Beyond this point, M_* flags are handled via oc->alloc()
 383          */
 384         depot = &oc->depot[myclusterid];
 385         spin_lock(&depot->spin);
 386
 387         /*
 388          * Recheck the cpucache after obtaining the depot spinlock.  This
 389          * shouldn't be necessary now but don't take any chances.
 390          */
 391         if (MAGAZINE_NOTEMPTY(cpucache->loaded_magazine) ||
 392             MAGAZINE_NOTEMPTY(cpucache->previous_magazine)
 393         ) {
 394                 spin_unlock(&depot->spin);
 395                 goto retry;
 396         }
 397
 398         /* Check if depot has a full magazine. */
 399         if (!SLIST_EMPTY(&depot->fullmagazines)) {
 400                 emptymag = cpucache->previous_magazine;
 401                 cpucache->previous_magazine = cpucache->loaded_magazine;
 402                 cpucache->loaded_magazine = SLIST_FIRST(&depot->fullmagazines);
 403                 SLIST_REMOVE_HEAD(&depot->fullmagazines, nextmagazine);
 404
 405                 /*
 406                  * Return emptymag to the depot.
 407                  */
 408                 KKASSERT(MAGAZINE_EMPTY(emptymag));
 409                 SLIST_INSERT_HEAD(&depot->emptymagazines,
 410                                   emptymag, nextmagazine);
 411                 spin_unlock(&depot->spin);
 412                 goto retry;
 413         }
 414
 415         /*
 416          * The depot does not have any non-empty magazines.  If we have
 417          * not hit our object limit we can allocate a new object using
 418          * the back-end allocator.
 419          *
 420          * note: unallocated_objects can be initialized to -1, which has
 421          * the effect of removing any allocation limits.
 422          */
 423         if (depot->unallocated_objects) {
 424                 --depot->unallocated_objects;
 425                 spin_unlock(&depot->spin);
 426                 crit_exit();
 427
 428                 obj = oc->alloc(oc->allocator_args, ocflags);
 429                 if (obj) {
 430                         if (oc->ctor(obj, oc->privdata, ocflags))
 431                                 return (obj);
 432                         oc->free(obj, oc->allocator_args);
 433                         obj = NULL;
 434                 }
 435                 if (obj == NULL) {
 436                         spin_lock(&depot->spin);
 437                         ++depot->unallocated_objects;
 438                         spin_unlock(&depot->spin);
 439                         if (depot->waiting)
 440                                 wakeup(depot);
 441
 442                         crit_enter();
 443                         /*
 444                          * makes debugging easier when gets_cumulative does
 445                          * not include gets_null.
 446                          */
 447                         ++cpucache->gets_null;
 448                         --cpucache->gets_cumulative;
 449                         crit_exit();
 450                 }
 451                 return(obj);
 452         }
 453         if (oc->exhausted == 0) {
 454                 kprintf("Warning, objcache(%s): Exhausted!\n", oc->name);
 455                 oc->exhausted = 1;
 456         }
 457
 458         /*
 459          * Otherwise block if allowed to.
 460          */
 461         if ((ocflags & (M_WAITOK|M_NULLOK)) == M_WAITOK) {
 462                 ++cpucache->waiting;
 463                 ++depot->waiting;
 464                 ssleep(depot, &depot->spin, 0, "objcache_get", 0);
 465                 --cpucache->waiting;
 466                 --depot->waiting;
 467                 spin_unlock(&depot->spin);
 468                 goto retry;
 469         }
 470
 471         /*
 472          * Otherwise fail
 473          */
 474         ++cpucache->gets_null;
 475         --cpucache->gets_cumulative;
 476         crit_exit();
 477         spin_unlock(&depot->spin);
 478         return (NULL);
 479 }
 480
 481 /*
 482  * Wrapper for malloc allocation routines.
 483  */
 484 void *
 485 objcache_malloc_alloc(void *allocator_args, int ocflags)
 486 {
 487         struct objcache_malloc_args *alloc_args = allocator_args;
 488
 489         return (kmalloc(alloc_args->objsize, alloc_args->mtype,
 490                        ocflags & OC_MFLAGS));
 491 }
 492
 493 void
 494 objcache_malloc_free(void *obj, void *allocator_args)
 495 {
 496         struct objcache_malloc_args *alloc_args = allocator_args;
 497
 498         kfree(obj, alloc_args->mtype);
 499 }
 500
 501 /*
 502  * Wrapper for allocation policies that pre-allocate at initialization time
 503  * and don't do run-time allocation.
 504  */
 505 void *
 506 objcache_nop_alloc(void *allocator_args, int ocflags)
 507 {
 508         return (NULL);
 509 }
 510
 511 void
 512 objcache_nop_free(void *obj, void *allocator_args)
 513 {
 514 }
 515
 516 /*
 517  * Return an object to the object cache.
 518  */
 519 void
 520 objcache_put(struct objcache *oc, void *obj)
 521 {
 522         struct percpu_objcache *cpucache = &oc->cache_percpu[mycpuid];
 523         struct magazine *loadedmag;
 524         struct magazinedepot *depot;
 525
 526         crit_enter();
 527         ++cpucache->puts_cumulative;
 528
 529         if (CLUSTER_OF(obj) != myclusterid) {
 530 #ifdef notyet
 531                 /* use lazy IPI to send object to owning cluster XXX todo */
 532                 ++cpucache->puts_othercluster;
 533                 crit_exit();
 534                 return;
 535 #endif
 536         }
 537
 538 retry:
 539         /*
 540          * Free slot available in loaded magazine.  This is the hot path.
 541          * It is lock-free and uses a critical section to block out interrupt
 542          * handlers on the same processor.
 543          */
 544         loadedmag = cpucache->loaded_magazine;
 545         if (!MAGAZINE_FULL(loadedmag)) {
 546                 loadedmag->objects[loadedmag->rounds++] = obj;
 547                 if (cpucache->waiting)
 548                         wakeup_mycpu(&oc->depot[myclusterid]);
 549                 crit_exit();
 550                 return;
 551         }
 552
 553         /*
 554          * Current magazine full, but previous magazine has room.  XXX
 555          */
 556         if (!MAGAZINE_FULL(cpucache->previous_magazine)) {
 557                 swap(cpucache->loaded_magazine, cpucache->previous_magazine);
 558                 loadedmag = cpucache->loaded_magazine;
 559                 loadedmag->objects[loadedmag->rounds++] = obj;
 560                 if (cpucache->waiting)
 561                         wakeup_mycpu(&oc->depot[myclusterid]);
 562                 crit_exit();
 563                 return;
 564         }
 565
 566         /*
 567          * Both magazines full.  Get an empty magazine from the depot and
 568          * move a full loaded magazine to the depot.  Even though the
 569          * magazine may wind up with space available after we block on
 570          * the spinlock, we still cycle it through to avoid the non-optimal
 571          * corner-case.
 572          *
 573          * Obtain the depot spinlock.
 574          */
 575         depot = &oc->depot[myclusterid];
 576         spin_lock(&depot->spin);
 577
 578         /*
 579          * If an empty magazine is available in the depot, cycle it
 580          * through and retry.
 581          */
 582         if (!SLIST_EMPTY(&depot->emptymagazines)) {
 583                 loadedmag = cpucache->previous_magazine;
 584                 cpucache->previous_magazine = cpucache->loaded_magazine;
 585                 cpucache->loaded_magazine = SLIST_FIRST(&depot->emptymagazines);
 586                 SLIST_REMOVE_HEAD(&depot->emptymagazines, nextmagazine);
 587
 588                 /*
 589                  * Return loadedmag to the depot.  Due to blocking it may
 590                  * not be entirely full and could even be empty.
 591                  */
 592                 if (MAGAZINE_EMPTY(loadedmag)) {
 593                         SLIST_INSERT_HEAD(&depot->emptymagazines,
 594                                           loadedmag, nextmagazine);
 595                         spin_unlock(&depot->spin);
 596                 } else {
 597                         SLIST_INSERT_HEAD(&depot->fullmagazines,
 598                                           loadedmag, nextmagazine);
 599                         spin_unlock(&depot->spin);
 600                         if (depot->waiting)
 601                                 wakeup(depot);
 602                 }
 603                 goto retry;
 604         }
 605
 606         /*
 607          * An empty mag is not available.  This is a corner case which can
 608          * occur due to cpus holding partially full magazines.  Do not try
 609          * to allocate a mag, just free the object.
 610          */
 611         ++depot->unallocated_objects;
 612         spin_unlock(&depot->spin);
 613         if (depot->waiting)
 614                 wakeup(depot);
 615         crit_exit();
 616         oc->dtor(obj, oc->privdata);
 617         oc->free(obj, oc->allocator_args);
 618 }
 619
 620 /*
 621  * The object is being put back into the cache, but the caller has
 622  * indicated that the object is not in any shape to be reused and should
 623  * be dtor'd immediately.
 624  */
 625 void
 626 objcache_dtor(struct objcache *oc, void *obj)
 627 {
 628         struct magazinedepot *depot;
 629
 630         depot = &oc->depot[myclusterid];
 631         spin_lock(&depot->spin);
 632         ++depot->unallocated_objects;
 633         spin_unlock(&depot->spin);
 634         if (depot->waiting)
 635                 wakeup(depot);
 636         oc->dtor(obj, oc->privdata);
 637         oc->free(obj, oc->allocator_args);
 638 }
 639
 640 /*
 641  * Deallocate all objects in a magazine and free the magazine if requested.
 642  * When freeit is TRUE the magazine must already be disassociated from the
 643  * depot.
 644  *
 645  * Must be called with a critical section held when called with a per-cpu
 646  * magazine.  The magazine may be indirectly modified during the loop.
 647  *
 648  * If the magazine moves during a dtor the operation is aborted.  This is
 649  * only allowed when freeit is FALSE.
 650  *
 651  * The number of objects freed is returned.
 652  */
 653 static int
 654 mag_purge(struct objcache *oc, struct magazine **magp, int freeit)
 655 {
 656         struct magazine *mag = *magp;
 657         int count;
 658         void *obj;
 659
 660         count = 0;
 661         while (mag->rounds) {
 662                 obj = mag->objects[--mag->rounds];
 663                 oc->dtor(obj, oc->privdata);            /* MAY BLOCK */
 664                 oc->free(obj, oc->allocator_args);      /* MAY BLOCK */
 665                 ++count;
 666
 667                 /*
 668                  * Cycle for interrupts.
 669                  */
 670                 if ((count & 15) == 0) {
 671                         crit_exit();
 672                         crit_enter();
 673                 }
 674
 675                 /*
 676                  * mag may have become invalid either due to dtor/free
 677                  * blocking or interrupt cycling, do not derefernce it
 678                  * until we check.
 679                  */
 680                 if (*magp != mag) {
 681                         kprintf("mag_purge: mag ripped out\n");
 682                         break;
 683                 }
 684         }
 685         if (freeit) {
 686                 KKASSERT(*magp == mag);
 687                 *magp = NULL;
 688                 kfree(mag, M_OBJMAG);
 689         }
 690         return(count);
 691 }
 692
 693 /*
 694  * Disassociate zero or more magazines from a magazine list associated with
 695  * the depot, update the depot, and move the magazines to a temporary
 696  * list.
 697  *
 698  * The caller must check the depot for waiters and wake it up, typically
 699  * after disposing of the magazines this function loads onto the temporary
 700  * list.
 701  */
 702 static void
 703 maglist_disassociate(struct magazinedepot *depot, struct magazinelist *maglist,
 704                      struct magazinelist *tmplist, boolean_t purgeall)
 705 {
 706         struct magazine *mag;
 707
 708         while ((mag = SLIST_FIRST(maglist)) != NULL) {
 709                 SLIST_REMOVE_HEAD(maglist, nextmagazine);
 710                 SLIST_INSERT_HEAD(tmplist, mag, nextmagazine);
 711                 depot->unallocated_objects += mag->rounds;
 712         }
 713 }
 714
 715 /*
 716  * Deallocate all magazines and their contents from the passed temporary
 717  * list.  The magazines have already been accounted for by their depots.
 718  *
 719  * The total number of rounds freed is returned.  This number is typically
 720  * only used to determine whether a wakeup on the depot is needed or not.
 721  */
 722 static int
 723 maglist_purge(struct objcache *oc, struct magazinelist *maglist)
 724 {
 725         struct magazine *mag;
 726         int count = 0;
 727
 728         /*
 729          * can't use SLIST_FOREACH because blocking releases the depot
 730          * spinlock
 731          */
 732         crit_enter();
 733         while ((mag = SLIST_FIRST(maglist)) != NULL) {
 734                 SLIST_REMOVE_HEAD(maglist, nextmagazine);
 735                 count += mag_purge(oc, &mag, TRUE);
 736         }
 737         crit_exit();
 738         return(count);
 739 }
 740
 741 /*
 742  * De-allocates all magazines on the full and empty magazine lists.
 743  *
 744  * Because this routine is called with a spinlock held, the magazines
 745  * can only be disassociated and moved to a temporary list, not freed.
 746  *
 747  * The caller is responsible for freeing the magazines.
 748  */
 749 static void
 750 depot_disassociate(struct magazinedepot *depot, struct magazinelist *tmplist)
 751 {
 752         maglist_disassociate(depot, &depot->fullmagazines, tmplist, TRUE);
 753         maglist_disassociate(depot, &depot->emptymagazines, tmplist, TRUE);
 754 }
 755
 756 #ifdef notneeded
 757 void
 758 objcache_reclaim(struct objcache *oc)
 759 {
 760         struct percpu_objcache *cache_percpu = &oc->cache_percpu[myclusterid];
 761         struct magazinedepot *depot = &oc->depot[myclusterid];
 762         struct magazinelist tmplist;
 763         int count;
 764
 765         SLIST_INIT(&tmplist);
 766         crit_enter();
 767         count = mag_purge(oc, &cache_percpu->loaded_magazine, FALSE);
 768         count += mag_purge(oc, &cache_percpu->previous_magazine, FALSE);
 769         crit_exit();
 770
 771         spin_lock(&depot->spin);
 772         depot->unallocated_objects += count;
 773         depot_disassociate(depot, &tmplist);
 774         spin_unlock(&depot->spin);
 775         count += maglist_purge(oc, &tmplist);
 776         if (count && depot->waiting)
 777                 wakeup(depot);
 778 }
 779 #endif
 780
 781 /*
 782  * Try to free up some memory.  Return as soon as some free memory is found.
 783  * For each object cache on the reclaim list, first try the current per-cpu
 784  * cache, then the full magazine depot.
 785  */
 786 boolean_t
 787 objcache_reclaimlist(struct objcache *oclist[], int nlist, int ocflags)
 788 {
 789         struct objcache *oc;
 790         struct percpu_objcache *cpucache;
 791         struct magazinedepot *depot;
 792         struct magazinelist tmplist;
 793         int i, count;
 794
 795         kprintf("objcache_reclaimlist\n");
 796
 797         SLIST_INIT(&tmplist);
 798
 799         for (i = 0; i < nlist; i++) {
 800                 oc = oclist[i];
 801                 cpucache = &oc->cache_percpu[mycpuid];
 802                 depot = &oc->depot[myclusterid];
 803
 804                 crit_enter();
 805                 count = mag_purge(oc, &cpucache->loaded_magazine, FALSE);
 806                 if (count == 0)
 807                         count += mag_purge(oc, &cpucache->previous_magazine, FALSE);
 808                 crit_exit();
 809                 if (count > 0) {
 810                         spin_lock(&depot->spin);
 811                         depot->unallocated_objects += count;
 812                         spin_unlock(&depot->spin);
 813                         if (depot->waiting)
 814                                 wakeup(depot);
 815                         return (TRUE);
 816                 }
 817                 spin_lock(&depot->spin);
 818                 maglist_disassociate(depot, &depot->fullmagazines,
 819                                      &tmplist, FALSE);
 820                 spin_unlock(&depot->spin);
 821                 count = maglist_purge(oc, &tmplist);
 822                 if (count > 0) {
 823                         if (depot->waiting)
 824                                 wakeup(depot);
 825                         return (TRUE);
 826                 }
 827         }
 828         return (FALSE);
 829 }
 830
 831 /*
 832  * Destroy an object cache.  Must have no existing references.
 833  */
 834 void
 835 objcache_destroy(struct objcache *oc)
 836 {
 837         struct percpu_objcache *cache_percpu;
 838         struct magazinedepot *depot;
 839         int clusterid, cpuid;
 840         struct magazinelist tmplist;
 841
 842         spin_lock(&objcachelist_spin);
 843         LIST_REMOVE(oc, oc_next);
 844         spin_unlock(&objcachelist_spin);
 845
 846         SLIST_INIT(&tmplist);
 847         for (clusterid = 0; clusterid < MAXCLUSTERS; clusterid++) {
 848                 depot = &oc->depot[clusterid];
 849                 spin_lock(&depot->spin);
 850                 depot_disassociate(depot, &tmplist);
 851                 spin_unlock(&depot->spin);
 852         }
 853         maglist_purge(oc, &tmplist);
 854
 855         for (cpuid = 0; cpuid < ncpus; cpuid++) {
 856                 cache_percpu = &oc->cache_percpu[cpuid];
 857
 858                 crit_enter();
 859                 mag_purge(oc, &cache_percpu->loaded_magazine, TRUE);
 860                 mag_purge(oc, &cache_percpu->previous_magazine, TRUE);
 861                 crit_exit();
 862                 cache_percpu->loaded_magazine = NULL;
 863                 cache_percpu->previous_magazine = NULL;
 864                 /* don't bother adjusting depot->unallocated_objects */
 865         }
 866
 867         kfree(oc->name, M_TEMP);
 868         kfree(oc, M_OBJCACHE);
 869 }
 870
 871 #if 0
 872 /*
 873  * Populate the per-cluster depot with elements from a linear block
 874  * of memory.  Must be called for individually for each cluster.
 875  * Populated depots should not be destroyed.
 876  */
 877 void
 878 objcache_populate_linear(struct objcache *oc, void *base, int nelts, int size)
 879 {
 880         char *p = base;
 881         char *end = (char *)base + (nelts * size);
 882         struct magazinedepot *depot = &oc->depot[myclusterid];
 883         struct magazine *emptymag = mag_alloc(depot->magcapcity);
 884
 885         while (p < end) {
 886                 emptymag->objects[emptymag->rounds++] = p;
 887                 if (MAGAZINE_FULL(emptymag)) {
 888                         spin_lock_wr(&depot->spin);
 889                         SLIST_INSERT_HEAD(&depot->fullmagazines, emptymag,
 890                                           nextmagazine);
 891                         depot->unallocated_objects += emptymag->rounds;
 892                         spin_unlock_wr(&depot->spin);
 893                         if (depot->waiting)
 894                                 wakeup(depot);
 895                         emptymag = mag_alloc(depot->magcapacity);
 896                 }
 897                 p += size;
 898         }
 899         if (MAGAZINE_EMPTY(emptymag)) {
 900                 crit_enter();
 901                 mag_purge(oc, &emptymag, TRUE);
 902                 crit_exit();
 903         } else {
 904                 spin_lock_wr(&depot->spin);
 905                 SLIST_INSERT_HEAD(&depot->fullmagazines, emptymag,
 906                                   nextmagazine);
 907                 depot->unallocated_objects += emptymag->rounds;
 908                 spin_unlock_wr(&depot->spin);
 909                 if (depot->waiting)
 910                         wakeup(depot);
 911                 emptymag = mag_alloc(depot->magcapacity);
 912         }
 913 }
 914 #endif
 915
 916 #if 0
 917 /*
 918  * Check depot contention once a minute.
 919  * 2 contested locks per second allowed.
 920  */
 921 static int objcache_rebalance_period;
 922 static const int objcache_contention_rate = 120;
 923 static struct callout objcache_callout;
 924
 925 #define MAXMAGSIZE 512
 926
 927 /*
 928  * Check depot contention and increase magazine size if necessary.
 929  */
 930 static void
 931 objcache_timer(void *dummy)
 932 {
 933         struct objcache *oc;
 934         struct magazinedepot *depot;
 935         struct magazinelist tmplist;
 936
 937         XXX we need to detect when an objcache is destroyed out from under
 938             us XXX
 939
 940         SLIST_INIT(&tmplist);
 941
 942         spin_lock_wr(&objcachelist_spin);
 943         LIST_FOREACH(oc, &allobjcaches, oc_next) {
 944                 depot = &oc->depot[myclusterid];
 945                 if (depot->magcapacity < MAXMAGSIZE) {
 946                         if (depot->contested > objcache_contention_rate) {
 947                                 spin_lock_wr(&depot->spin);
 948                                 depot_disassociate(depot, &tmplist);
 949                                 depot->magcapacity *= 2;
 950                                 spin_unlock_wr(&depot->spin);
 951                                 kprintf("objcache_timer: increasing cache %s"
 952                                        " magsize to %d, contested %d times\n",
 953                                     oc->name, depot->magcapacity,
 954                                     depot->contested);
 955                         }
 956                         depot->contested = 0;
 957                 }
 958                 spin_unlock_wr(&objcachelist_spin);
 959                 if (maglist_purge(oc, &tmplist) > 0 && depot->waiting)
 960                         wakeup(depot);
 961                 spin_lock_wr(&objcachelist_spin);
 962         }
 963         spin_unlock_wr(&objcachelist_spin);
 964
 965         callout_reset(&objcache_callout, objcache_rebalance_period,
 966                       objcache_timer, NULL);
 967 }
 968
 969 #endif
 970
 971 static void
 972 objcache_init(void)
 973 {
 974         spin_init(&objcachelist_spin);
 975 #if 0
 976         callout_init_mp(&objcache_callout);
 977         objcache_rebalance_period = 60 * hz;
 978         callout_reset(&objcache_callout, objcache_rebalance_period,
 979                       objcache_timer, NULL);
 980 #endif
 981 }
 982 SYSINIT(objcache, SI_BOOT2_OBJCACHE, SI_ORDER_FIRST, objcache_init, 0);