c734406cafb6a6f46b60b7a922d67ee33da9a4c2
[dragonfly.git] / 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(&objcachelist_spin);
284         LIST_INSERT_HEAD(&allobjcaches, oc, oc_next);
285         spin_unlock(&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(&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(&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(&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(&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(&depot->spin);
439                         ++depot->unallocated_objects;
440                         spin_unlock(&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(&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(&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(&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(&depot->spin);
602                 } else {
603                         SLIST_INSERT_HEAD(&depot->fullmagazines,
604                                           loadedmag, nextmagazine);
605                         spin_unlock(&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(&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(&depot->spin);
638         ++depot->unallocated_objects;
639         spin_unlock(&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(&depot->spin);
762         depot->unallocated_objects += count;
763         depot_disassociate(depot, &tmplist);
764         spin_unlock(&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(&depot->spin);
799                         depot->unallocated_objects += count;
800                         spin_unlock(&depot->spin);
801                         if (depot->waiting)
802                                 wakeup(depot);
803                         return (TRUE);
804                 }
805                 spin_lock(&depot->spin);
806                 maglist_disassociate(depot, &depot->fullmagazines,
807                                      &tmplist, FALSE);
808                 spin_unlock(&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(&objcachelist_spin);
831         LIST_REMOVE(oc, oc_next);
832         spin_unlock(&objcachelist_spin);
833
834         SLIST_INIT(&tmplist);
835         for (clusterid = 0; clusterid < MAXCLUSTERS; clusterid++) {
836                 depot = &oc->depot[clusterid];
837                 spin_lock(&depot->spin);
838                 depot_disassociate(depot, &tmplist);
839                 spin_unlock(&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);