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