Rev 1682 | Rev 1966 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
759 | palkovsky | 1 | /* |
2 | * Copyright (C) 2006 Ondrej Palkovsky |
||
3 | * All rights reserved. |
||
4 | * |
||
5 | * Redistribution and use in source and binary forms, with or without |
||
6 | * modification, are permitted provided that the following conditions |
||
7 | * are met: |
||
8 | * |
||
9 | * - Redistributions of source code must retain the above copyright |
||
10 | * notice, this list of conditions and the following disclaimer. |
||
11 | * - Redistributions in binary form must reproduce the above copyright |
||
12 | * notice, this list of conditions and the following disclaimer in the |
||
13 | * documentation and/or other materials provided with the distribution. |
||
14 | * - The name of the author may not be used to endorse or promote products |
||
15 | * derived from this software without specific prior written permission. |
||
16 | * |
||
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
||
18 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
||
19 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
||
20 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
||
21 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
||
22 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
||
23 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
||
24 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
||
25 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
||
26 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
||
27 | */ |
||
28 | |||
1702 | cejka | 29 | /** @addtogroup genericmm |
30 | * @{ |
||
31 | */ |
||
32 | |||
1248 | jermar | 33 | /** |
1702 | cejka | 34 | * @file |
1248 | jermar | 35 | * @brief Slab allocator. |
769 | palkovsky | 36 | * |
1248 | jermar | 37 | * The slab allocator is closely modelled after OpenSolaris slab allocator. |
38 | * @see http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/ |
||
39 | * |
||
769 | palkovsky | 40 | * with the following exceptions: |
1248 | jermar | 41 | * @li empty slabs are deallocated immediately |
769 | palkovsky | 42 | * (in Linux they are kept in linked list, in Solaris ???) |
1248 | jermar | 43 | * @li empty magazines are deallocated when not needed |
769 | palkovsky | 44 | * (in Solaris they are held in linked list in slab cache) |
45 | * |
||
1248 | jermar | 46 | * Following features are not currently supported but would be easy to do: |
47 | * @li cache coloring |
||
48 | * @li dynamic magazine growing (different magazine sizes are already |
||
1144 | jermar | 49 | * supported, but we would need to adjust allocation strategy) |
769 | palkovsky | 50 | * |
1248 | jermar | 51 | * The slab allocator supports per-CPU caches ('magazines') to facilitate |
769 | palkovsky | 52 | * good SMP scaling. |
53 | * |
||
54 | * When a new object is being allocated, it is first checked, if it is |
||
1554 | jermar | 55 | * available in a CPU-bound magazine. If it is not found there, it is |
56 | * allocated from a CPU-shared slab - if a partially full one is found, |
||
57 | * it is used, otherwise a new one is allocated. |
||
769 | palkovsky | 58 | * |
1554 | jermar | 59 | * When an object is being deallocated, it is put to a CPU-bound magazine. |
60 | * If there is no such magazine, a new one is allocated (if this fails, |
||
1248 | jermar | 61 | * the object is deallocated into slab). If the magazine is full, it is |
1554 | jermar | 62 | * put into cpu-shared list of magazines and a new one is allocated. |
769 | palkovsky | 63 | * |
1554 | jermar | 64 | * The CPU-bound magazine is actually a pair of magazines in order to avoid |
769 | palkovsky | 65 | * thrashing when somebody is allocating/deallocating 1 item at the magazine |
66 | * size boundary. LIFO order is enforced, which should avoid fragmentation |
||
67 | * as much as possible. |
||
68 | * |
||
1554 | jermar | 69 | * Every cache contains list of full slabs and list of partially full slabs. |
1248 | jermar | 70 | * Empty slabs are immediately freed (thrashing will be avoided because |
769 | palkovsky | 71 | * of magazines). |
72 | * |
||
1248 | jermar | 73 | * The slab information structure is kept inside the data area, if possible. |
769 | palkovsky | 74 | * The cache can be marked that it should not use magazines. This is used |
1248 | jermar | 75 | * only for slab related caches to avoid deadlocks and infinite recursion |
76 | * (the slab allocator uses itself for allocating all it's control structures). |
||
769 | palkovsky | 77 | * |
1554 | jermar | 78 | * The slab allocator allocates a lot of space and does not free it. When |
79 | * the frame allocator fails to allocate a frame, it calls slab_reclaim(). |
||
769 | palkovsky | 80 | * It tries 'light reclaim' first, then brutal reclaim. The light reclaim |
81 | * releases slabs from cpu-shared magazine-list, until at least 1 slab |
||
82 | * is deallocated in each cache (this algorithm should probably change). |
||
83 | * The brutal reclaim removes all cached objects, even from CPU-bound |
||
84 | * magazines. |
||
85 | * |
||
1248 | jermar | 86 | * TODO:@n |
87 | * For better CPU-scaling the magazine allocation strategy should |
||
775 | palkovsky | 88 | * be extended. Currently, if the cache does not have magazine, it asks |
89 | * for non-cpu cached magazine cache to provide one. It might be feasible |
||
90 | * to add cpu-cached magazine cache (which would allocate it's magazines |
||
91 | * from non-cpu-cached mag. cache). This would provide a nice per-cpu |
||
92 | * buffer. The other possibility is to use the per-cache |
||
93 | * 'empty-magazine-list', which decreases competing for 1 per-system |
||
94 | * magazine cache. |
||
95 | * |
||
1248 | jermar | 96 | * @li it might be good to add granularity of locks even to slab level, |
97 | * we could then try_spinlock over all partial slabs and thus improve |
||
98 | * scalability even on slab level |
||
769 | palkovsky | 99 | */ |
100 | |||
759 | palkovsky | 101 | #include <synch/spinlock.h> |
102 | #include <mm/slab.h> |
||
788 | jermar | 103 | #include <adt/list.h> |
759 | palkovsky | 104 | #include <memstr.h> |
105 | #include <align.h> |
||
762 | palkovsky | 106 | #include <mm/frame.h> |
759 | palkovsky | 107 | #include <config.h> |
108 | #include <print.h> |
||
109 | #include <arch.h> |
||
110 | #include <panic.h> |
||
762 | palkovsky | 111 | #include <debug.h> |
771 | palkovsky | 112 | #include <bitops.h> |
759 | palkovsky | 113 | |
114 | SPINLOCK_INITIALIZE(slab_cache_lock); |
||
769 | palkovsky | 115 | static LIST_INITIALIZE(slab_cache_list); |
759 | palkovsky | 116 | |
769 | palkovsky | 117 | /** Magazine cache */ |
118 | static slab_cache_t mag_cache; |
||
119 | /** Cache for cache descriptors */ |
||
120 | static slab_cache_t slab_cache_cache; |
||
121 | /** Cache for external slab descriptors |
||
122 | * This time we want per-cpu cache, so do not make it static |
||
1248 | jermar | 123 | * - using slab for internal slab structures will not deadlock, |
769 | palkovsky | 124 | * as all slab structures are 'small' - control structures of |
125 | * their caches do not require further allocation |
||
126 | */ |
||
127 | static slab_cache_t *slab_extern_cache; |
||
771 | palkovsky | 128 | /** Caches for malloc */ |
129 | static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1]; |
||
130 | char *malloc_names[] = { |
||
791 | palkovsky | 131 | "malloc-16","malloc-32","malloc-64","malloc-128", |
771 | palkovsky | 132 | "malloc-256","malloc-512","malloc-1K","malloc-2K", |
133 | "malloc-4K","malloc-8K","malloc-16K","malloc-32K", |
||
1428 | palkovsky | 134 | "malloc-64K","malloc-128K","malloc-256K" |
771 | palkovsky | 135 | }; |
762 | palkovsky | 136 | |
769 | palkovsky | 137 | /** Slab descriptor */ |
762 | palkovsky | 138 | typedef struct { |
139 | slab_cache_t *cache; /**< Pointer to parent cache */ |
||
140 | link_t link; /* List of full/partial slabs */ |
||
141 | void *start; /**< Start address of first available item */ |
||
142 | count_t available; /**< Count of available items in this slab */ |
||
143 | index_t nextavail; /**< The index of next available item */ |
||
144 | }slab_t; |
||
145 | |||
791 | palkovsky | 146 | #ifdef CONFIG_DEBUG |
147 | static int _slab_initialized = 0; |
||
148 | #endif |
||
149 | |||
759 | palkovsky | 150 | /**************************************/ |
1248 | jermar | 151 | /* Slab allocation functions */ |
759 | palkovsky | 152 | |
762 | palkovsky | 153 | /** |
154 | * Allocate frames for slab space and initialize |
||
155 | * |
||
156 | */ |
||
157 | static slab_t * slab_space_alloc(slab_cache_t *cache, int flags) |
||
158 | { |
||
159 | void *data; |
||
160 | slab_t *slab; |
||
161 | size_t fsize; |
||
162 | int i; |
||
163 | int status; |
||
814 | palkovsky | 164 | pfn_t pfn; |
165 | int zone=0; |
||
166 | |||
167 | pfn = frame_alloc_rc_zone(cache->order, FRAME_KA | flags, &status, &zone); |
||
168 | data = (void *) PA2KA(PFN2ADDR(pfn)); |
||
764 | palkovsky | 169 | if (status != FRAME_OK) { |
762 | palkovsky | 170 | return NULL; |
764 | palkovsky | 171 | } |
768 | palkovsky | 172 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) { |
769 | palkovsky | 173 | slab = slab_alloc(slab_extern_cache, flags); |
762 | palkovsky | 174 | if (!slab) { |
814 | palkovsky | 175 | frame_free(ADDR2PFN(KA2PA(data))); |
762 | palkovsky | 176 | return NULL; |
177 | } |
||
178 | } else { |
||
179 | fsize = (PAGE_SIZE << cache->order); |
||
180 | slab = data + fsize - sizeof(*slab); |
||
181 | } |
||
1288 | jermar | 182 | |
762 | palkovsky | 183 | /* Fill in slab structures */ |
814 | palkovsky | 184 | for (i=0; i < (1 << cache->order); i++) |
185 | frame_set_parent(pfn+i, slab, zone); |
||
762 | palkovsky | 186 | |
187 | slab->start = data; |
||
188 | slab->available = cache->objects; |
||
189 | slab->nextavail = 0; |
||
767 | palkovsky | 190 | slab->cache = cache; |
762 | palkovsky | 191 | |
192 | for (i=0; i<cache->objects;i++) |
||
193 | *((int *) (slab->start + i*cache->size)) = i+1; |
||
764 | palkovsky | 194 | |
195 | atomic_inc(&cache->allocated_slabs); |
||
762 | palkovsky | 196 | return slab; |
197 | } |
||
198 | |||
759 | palkovsky | 199 | /** |
1248 | jermar | 200 | * Deallocate space associated with slab |
762 | palkovsky | 201 | * |
202 | * @return number of freed frames |
||
203 | */ |
||
204 | static count_t slab_space_free(slab_cache_t *cache, slab_t *slab) |
||
205 | { |
||
814 | palkovsky | 206 | frame_free(ADDR2PFN(KA2PA(slab->start))); |
768 | palkovsky | 207 | if (! (cache->flags & SLAB_CACHE_SLINSIDE)) |
769 | palkovsky | 208 | slab_free(slab_extern_cache, slab); |
764 | palkovsky | 209 | |
210 | atomic_dec(&cache->allocated_slabs); |
||
211 | |||
762 | palkovsky | 212 | return 1 << cache->order; |
213 | } |
||
214 | |||
215 | /** Map object to slab structure */ |
||
216 | static slab_t * obj2slab(void *obj) |
||
217 | { |
||
814 | palkovsky | 218 | return (slab_t *)frame_get_parent(ADDR2PFN(KA2PA(obj)), 0); |
762 | palkovsky | 219 | } |
220 | |||
221 | /**************************************/ |
||
1248 | jermar | 222 | /* Slab functions */ |
762 | palkovsky | 223 | |
224 | |||
225 | /** |
||
759 | palkovsky | 226 | * Return object to slab and call a destructor |
227 | * |
||
762 | palkovsky | 228 | * @param slab If the caller knows directly slab of the object, otherwise NULL |
229 | * |
||
759 | palkovsky | 230 | * @return Number of freed pages |
231 | */ |
||
762 | palkovsky | 232 | static count_t slab_obj_destroy(slab_cache_t *cache, void *obj, |
233 | slab_t *slab) |
||
759 | palkovsky | 234 | { |
787 | palkovsky | 235 | int freed = 0; |
236 | |||
762 | palkovsky | 237 | if (!slab) |
238 | slab = obj2slab(obj); |
||
239 | |||
767 | palkovsky | 240 | ASSERT(slab->cache == cache); |
241 | |||
787 | palkovsky | 242 | if (cache->destructor) |
243 | freed = cache->destructor(obj); |
||
244 | |||
776 | palkovsky | 245 | spinlock_lock(&cache->slablock); |
789 | palkovsky | 246 | ASSERT(slab->available < cache->objects); |
776 | palkovsky | 247 | |
762 | palkovsky | 248 | *((int *)obj) = slab->nextavail; |
249 | slab->nextavail = (obj - slab->start)/cache->size; |
||
250 | slab->available++; |
||
251 | |||
252 | /* Move it to correct list */ |
||
253 | if (slab->available == cache->objects) { |
||
254 | /* Free associated memory */ |
||
255 | list_remove(&slab->link); |
||
782 | palkovsky | 256 | spinlock_unlock(&cache->slablock); |
257 | |||
787 | palkovsky | 258 | return freed + slab_space_free(cache, slab); |
782 | palkovsky | 259 | |
780 | palkovsky | 260 | } else if (slab->available == 1) { |
261 | /* It was in full, move to partial */ |
||
262 | list_remove(&slab->link); |
||
263 | list_prepend(&slab->link, &cache->partial_slabs); |
||
762 | palkovsky | 264 | } |
783 | palkovsky | 265 | spinlock_unlock(&cache->slablock); |
787 | palkovsky | 266 | return freed; |
759 | palkovsky | 267 | } |
268 | |||
269 | /** |
||
270 | * Take new object from slab or create new if needed |
||
271 | * |
||
272 | * @return Object address or null |
||
273 | */ |
||
274 | static void * slab_obj_create(slab_cache_t *cache, int flags) |
||
275 | { |
||
762 | palkovsky | 276 | slab_t *slab; |
277 | void *obj; |
||
278 | |||
776 | palkovsky | 279 | spinlock_lock(&cache->slablock); |
280 | |||
762 | palkovsky | 281 | if (list_empty(&cache->partial_slabs)) { |
282 | /* Allow recursion and reclaiming |
||
1248 | jermar | 283 | * - this should work, as the slab control structures |
1288 | jermar | 284 | * are small and do not need to allocate with anything |
285 | * other than frame_alloc when they are allocating, |
||
762 | palkovsky | 286 | * that's why we should get recursion at most 1-level deep |
287 | */ |
||
776 | palkovsky | 288 | spinlock_unlock(&cache->slablock); |
762 | palkovsky | 289 | slab = slab_space_alloc(cache, flags); |
780 | palkovsky | 290 | if (!slab) |
291 | return NULL; |
||
776 | palkovsky | 292 | spinlock_lock(&cache->slablock); |
762 | palkovsky | 293 | } else { |
294 | slab = list_get_instance(cache->partial_slabs.next, |
||
295 | slab_t, |
||
296 | link); |
||
297 | list_remove(&slab->link); |
||
298 | } |
||
299 | obj = slab->start + slab->nextavail * cache->size; |
||
300 | slab->nextavail = *((int *)obj); |
||
301 | slab->available--; |
||
787 | palkovsky | 302 | |
762 | palkovsky | 303 | if (! slab->available) |
764 | palkovsky | 304 | list_prepend(&slab->link, &cache->full_slabs); |
762 | palkovsky | 305 | else |
764 | palkovsky | 306 | list_prepend(&slab->link, &cache->partial_slabs); |
776 | palkovsky | 307 | |
308 | spinlock_unlock(&cache->slablock); |
||
787 | palkovsky | 309 | |
310 | if (cache->constructor && cache->constructor(obj, flags)) { |
||
311 | /* Bad, bad, construction failed */ |
||
312 | slab_obj_destroy(cache, obj, slab); |
||
313 | return NULL; |
||
314 | } |
||
762 | palkovsky | 315 | return obj; |
759 | palkovsky | 316 | } |
317 | |||
318 | /**************************************/ |
||
319 | /* CPU-Cache slab functions */ |
||
320 | |||
321 | /** |
||
781 | palkovsky | 322 | * Finds a full magazine in cache, takes it from list |
323 | * and returns it |
||
324 | * |
||
325 | * @param first If true, return first, else last mag |
||
326 | */ |
||
327 | static slab_magazine_t * get_mag_from_cache(slab_cache_t *cache, |
||
328 | int first) |
||
329 | { |
||
330 | slab_magazine_t *mag = NULL; |
||
331 | link_t *cur; |
||
332 | |||
333 | spinlock_lock(&cache->maglock); |
||
334 | if (!list_empty(&cache->magazines)) { |
||
335 | if (first) |
||
336 | cur = cache->magazines.next; |
||
337 | else |
||
338 | cur = cache->magazines.prev; |
||
339 | mag = list_get_instance(cur, slab_magazine_t, link); |
||
340 | list_remove(&mag->link); |
||
341 | atomic_dec(&cache->magazine_counter); |
||
342 | } |
||
343 | spinlock_unlock(&cache->maglock); |
||
344 | return mag; |
||
345 | } |
||
346 | |||
347 | /** Prepend magazine to magazine list in cache */ |
||
348 | static void put_mag_to_cache(slab_cache_t *cache, slab_magazine_t *mag) |
||
349 | { |
||
350 | spinlock_lock(&cache->maglock); |
||
351 | |||
352 | list_prepend(&mag->link, &cache->magazines); |
||
353 | atomic_inc(&cache->magazine_counter); |
||
354 | |||
355 | spinlock_unlock(&cache->maglock); |
||
356 | } |
||
357 | |||
358 | /** |
||
759 | palkovsky | 359 | * Free all objects in magazine and free memory associated with magazine |
360 | * |
||
361 | * @return Number of freed pages |
||
362 | */ |
||
363 | static count_t magazine_destroy(slab_cache_t *cache, |
||
364 | slab_magazine_t *mag) |
||
365 | { |
||
366 | int i; |
||
367 | count_t frames = 0; |
||
368 | |||
767 | palkovsky | 369 | for (i=0;i < mag->busy; i++) { |
762 | palkovsky | 370 | frames += slab_obj_destroy(cache, mag->objs[i], NULL); |
767 | palkovsky | 371 | atomic_dec(&cache->cached_objs); |
372 | } |
||
759 | palkovsky | 373 | |
374 | slab_free(&mag_cache, mag); |
||
375 | |||
376 | return frames; |
||
377 | } |
||
378 | |||
379 | /** |
||
769 | palkovsky | 380 | * Find full magazine, set it as current and return it |
381 | * |
||
382 | * Assume cpu_magazine lock is held |
||
383 | */ |
||
384 | static slab_magazine_t * get_full_current_mag(slab_cache_t *cache) |
||
385 | { |
||
386 | slab_magazine_t *cmag, *lastmag, *newmag; |
||
387 | |||
388 | cmag = cache->mag_cache[CPU->id].current; |
||
389 | lastmag = cache->mag_cache[CPU->id].last; |
||
390 | if (cmag) { /* First try local CPU magazines */ |
||
391 | if (cmag->busy) |
||
392 | return cmag; |
||
393 | |||
394 | if (lastmag && lastmag->busy) { |
||
395 | cache->mag_cache[CPU->id].current = lastmag; |
||
396 | cache->mag_cache[CPU->id].last = cmag; |
||
397 | return lastmag; |
||
398 | } |
||
399 | } |
||
400 | /* Local magazines are empty, import one from magazine list */ |
||
781 | palkovsky | 401 | newmag = get_mag_from_cache(cache, 1); |
402 | if (!newmag) |
||
769 | palkovsky | 403 | return NULL; |
404 | |||
405 | if (lastmag) |
||
781 | palkovsky | 406 | magazine_destroy(cache, lastmag); |
407 | |||
769 | palkovsky | 408 | cache->mag_cache[CPU->id].last = cmag; |
409 | cache->mag_cache[CPU->id].current = newmag; |
||
410 | return newmag; |
||
411 | } |
||
412 | |||
413 | /** |
||
759 | palkovsky | 414 | * Try to find object in CPU-cache magazines |
415 | * |
||
416 | * @return Pointer to object or NULL if not available |
||
417 | */ |
||
418 | static void * magazine_obj_get(slab_cache_t *cache) |
||
419 | { |
||
420 | slab_magazine_t *mag; |
||
767 | palkovsky | 421 | void *obj; |
759 | palkovsky | 422 | |
772 | palkovsky | 423 | if (!CPU) |
424 | return NULL; |
||
425 | |||
759 | palkovsky | 426 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
427 | |||
769 | palkovsky | 428 | mag = get_full_current_mag(cache); |
429 | if (!mag) { |
||
430 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
||
431 | return NULL; |
||
759 | palkovsky | 432 | } |
767 | palkovsky | 433 | obj = mag->objs[--mag->busy]; |
759 | palkovsky | 434 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
767 | palkovsky | 435 | atomic_dec(&cache->cached_objs); |
436 | |||
437 | return obj; |
||
759 | palkovsky | 438 | } |
439 | |||
440 | /** |
||
768 | palkovsky | 441 | * Assure that the current magazine is empty, return pointer to it, or NULL if |
769 | palkovsky | 442 | * no empty magazine is available and cannot be allocated |
759 | palkovsky | 443 | * |
773 | palkovsky | 444 | * Assume mag_cache[CPU->id].lock is held |
445 | * |
||
759 | palkovsky | 446 | * We have 2 magazines bound to processor. |
447 | * First try the current. |
||
448 | * If full, try the last. |
||
449 | * If full, put to magazines list. |
||
450 | * allocate new, exchange last & current |
||
451 | * |
||
768 | palkovsky | 452 | */ |
453 | static slab_magazine_t * make_empty_current_mag(slab_cache_t *cache) |
||
454 | { |
||
455 | slab_magazine_t *cmag,*lastmag,*newmag; |
||
456 | |||
457 | cmag = cache->mag_cache[CPU->id].current; |
||
458 | lastmag = cache->mag_cache[CPU->id].last; |
||
459 | |||
460 | if (cmag) { |
||
461 | if (cmag->busy < cmag->size) |
||
462 | return cmag; |
||
463 | if (lastmag && lastmag->busy < lastmag->size) { |
||
464 | cache->mag_cache[CPU->id].last = cmag; |
||
465 | cache->mag_cache[CPU->id].current = lastmag; |
||
466 | return lastmag; |
||
467 | } |
||
468 | } |
||
469 | /* current | last are full | nonexistent, allocate new */ |
||
470 | /* We do not want to sleep just because of caching */ |
||
471 | /* Especially we do not want reclaiming to start, as |
||
472 | * this would deadlock */ |
||
473 | newmag = slab_alloc(&mag_cache, FRAME_ATOMIC | FRAME_NO_RECLAIM); |
||
474 | if (!newmag) |
||
475 | return NULL; |
||
476 | newmag->size = SLAB_MAG_SIZE; |
||
477 | newmag->busy = 0; |
||
478 | |||
479 | /* Flush last to magazine list */ |
||
781 | palkovsky | 480 | if (lastmag) |
481 | put_mag_to_cache(cache, lastmag); |
||
482 | |||
768 | palkovsky | 483 | /* Move current as last, save new as current */ |
484 | cache->mag_cache[CPU->id].last = cmag; |
||
485 | cache->mag_cache[CPU->id].current = newmag; |
||
486 | |||
487 | return newmag; |
||
488 | } |
||
489 | |||
490 | /** |
||
491 | * Put object into CPU-cache magazine |
||
492 | * |
||
759 | palkovsky | 493 | * @return 0 - success, -1 - could not get memory |
494 | */ |
||
495 | static int magazine_obj_put(slab_cache_t *cache, void *obj) |
||
496 | { |
||
497 | slab_magazine_t *mag; |
||
498 | |||
772 | palkovsky | 499 | if (!CPU) |
500 | return -1; |
||
501 | |||
759 | palkovsky | 502 | spinlock_lock(&cache->mag_cache[CPU->id].lock); |
768 | palkovsky | 503 | |
504 | mag = make_empty_current_mag(cache); |
||
769 | palkovsky | 505 | if (!mag) { |
506 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
||
507 | return -1; |
||
508 | } |
||
759 | palkovsky | 509 | |
510 | mag->objs[mag->busy++] = obj; |
||
511 | |||
512 | spinlock_unlock(&cache->mag_cache[CPU->id].lock); |
||
767 | palkovsky | 513 | atomic_inc(&cache->cached_objs); |
759 | palkovsky | 514 | return 0; |
515 | } |
||
516 | |||
517 | |||
518 | /**************************************/ |
||
1248 | jermar | 519 | /* Slab cache functions */ |
759 | palkovsky | 520 | |
762 | palkovsky | 521 | /** Return number of objects that fit in certain cache size */ |
522 | static int comp_objects(slab_cache_t *cache) |
||
523 | { |
||
524 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
||
525 | return ((PAGE_SIZE << cache->order) - sizeof(slab_t)) / cache->size; |
||
526 | else |
||
527 | return (PAGE_SIZE << cache->order) / cache->size; |
||
528 | } |
||
529 | |||
530 | /** Return wasted space in slab */ |
||
531 | static int badness(slab_cache_t *cache) |
||
532 | { |
||
533 | int objects; |
||
534 | int ssize; |
||
535 | |||
536 | objects = comp_objects(cache); |
||
537 | ssize = PAGE_SIZE << cache->order; |
||
538 | if (cache->flags & SLAB_CACHE_SLINSIDE) |
||
539 | ssize -= sizeof(slab_t); |
||
540 | return ssize - objects*cache->size; |
||
541 | } |
||
542 | |||
789 | palkovsky | 543 | /** |
544 | * Initialize mag_cache structure in slab cache |
||
545 | */ |
||
546 | static void make_magcache(slab_cache_t *cache) |
||
547 | { |
||
548 | int i; |
||
791 | palkovsky | 549 | |
550 | ASSERT(_slab_initialized >= 2); |
||
789 | palkovsky | 551 | |
822 | palkovsky | 552 | cache->mag_cache = malloc(sizeof(slab_mag_cache_t)*config.cpu_count,0); |
789 | palkovsky | 553 | for (i=0; i < config.cpu_count; i++) { |
554 | memsetb((__address)&cache->mag_cache[i], |
||
555 | sizeof(cache->mag_cache[i]), 0); |
||
556 | spinlock_initialize(&cache->mag_cache[i].lock, |
||
557 | "slab_maglock_cpu"); |
||
558 | } |
||
559 | } |
||
560 | |||
759 | palkovsky | 561 | /** Initialize allocated memory as a slab cache */ |
562 | static void |
||
563 | _slab_cache_create(slab_cache_t *cache, |
||
564 | char *name, |
||
565 | size_t size, |
||
566 | size_t align, |
||
567 | int (*constructor)(void *obj, int kmflag), |
||
787 | palkovsky | 568 | int (*destructor)(void *obj), |
759 | palkovsky | 569 | int flags) |
570 | { |
||
771 | palkovsky | 571 | int pages; |
783 | palkovsky | 572 | ipl_t ipl; |
759 | palkovsky | 573 | |
574 | memsetb((__address)cache, sizeof(*cache), 0); |
||
575 | cache->name = name; |
||
576 | |||
766 | palkovsky | 577 | if (align < sizeof(__native)) |
578 | align = sizeof(__native); |
||
579 | size = ALIGN_UP(size, align); |
||
580 | |||
762 | palkovsky | 581 | cache->size = size; |
759 | palkovsky | 582 | |
583 | cache->constructor = constructor; |
||
584 | cache->destructor = destructor; |
||
585 | cache->flags = flags; |
||
586 | |||
587 | list_initialize(&cache->full_slabs); |
||
588 | list_initialize(&cache->partial_slabs); |
||
589 | list_initialize(&cache->magazines); |
||
776 | palkovsky | 590 | spinlock_initialize(&cache->slablock, "slab_lock"); |
591 | spinlock_initialize(&cache->maglock, "slab_maglock"); |
||
789 | palkovsky | 592 | if (! (cache->flags & SLAB_CACHE_NOMAGAZINE)) |
593 | make_magcache(cache); |
||
759 | palkovsky | 594 | |
595 | /* Compute slab sizes, object counts in slabs etc. */ |
||
596 | if (cache->size < SLAB_INSIDE_SIZE) |
||
597 | cache->flags |= SLAB_CACHE_SLINSIDE; |
||
598 | |||
762 | palkovsky | 599 | /* Minimum slab order */ |
1682 | palkovsky | 600 | pages = SIZE2FRAMES(cache->size); |
1677 | palkovsky | 601 | /* We need the 2^order >= pages */ |
602 | if (pages == 1) |
||
603 | cache->order = 0; |
||
604 | else |
||
605 | cache->order = fnzb(pages-1)+1; |
||
766 | palkovsky | 606 | |
762 | palkovsky | 607 | while (badness(cache) > SLAB_MAX_BADNESS(cache)) { |
608 | cache->order += 1; |
||
609 | } |
||
610 | cache->objects = comp_objects(cache); |
||
766 | palkovsky | 611 | /* If info fits in, put it inside */ |
612 | if (badness(cache) > sizeof(slab_t)) |
||
613 | cache->flags |= SLAB_CACHE_SLINSIDE; |
||
762 | palkovsky | 614 | |
783 | palkovsky | 615 | /* Add cache to cache list */ |
616 | ipl = interrupts_disable(); |
||
759 | palkovsky | 617 | spinlock_lock(&slab_cache_lock); |
618 | |||
619 | list_append(&cache->link, &slab_cache_list); |
||
620 | |||
621 | spinlock_unlock(&slab_cache_lock); |
||
783 | palkovsky | 622 | interrupts_restore(ipl); |
759 | palkovsky | 623 | } |
624 | |||
625 | /** Create slab cache */ |
||
626 | slab_cache_t * slab_cache_create(char *name, |
||
627 | size_t size, |
||
628 | size_t align, |
||
629 | int (*constructor)(void *obj, int kmflag), |
||
787 | palkovsky | 630 | int (*destructor)(void *obj), |
759 | palkovsky | 631 | int flags) |
632 | { |
||
633 | slab_cache_t *cache; |
||
634 | |||
769 | palkovsky | 635 | cache = slab_alloc(&slab_cache_cache, 0); |
759 | palkovsky | 636 | _slab_cache_create(cache, name, size, align, constructor, destructor, |
637 | flags); |
||
638 | return cache; |
||
639 | } |
||
640 | |||
641 | /** |
||
642 | * Reclaim space occupied by objects that are already free |
||
643 | * |
||
644 | * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing |
||
645 | * @return Number of freed pages |
||
646 | */ |
||
647 | static count_t _slab_reclaim(slab_cache_t *cache, int flags) |
||
648 | { |
||
649 | int i; |
||
650 | slab_magazine_t *mag; |
||
651 | count_t frames = 0; |
||
781 | palkovsky | 652 | int magcount; |
759 | palkovsky | 653 | |
654 | if (cache->flags & SLAB_CACHE_NOMAGAZINE) |
||
655 | return 0; /* Nothing to do */ |
||
781 | palkovsky | 656 | |
657 | /* We count up to original magazine count to avoid |
||
658 | * endless loop |
||
659 | */ |
||
660 | magcount = atomic_get(&cache->magazine_counter); |
||
661 | while (magcount-- && (mag=get_mag_from_cache(cache,0))) { |
||
662 | frames += magazine_destroy(cache,mag); |
||
663 | if (!(flags & SLAB_RECLAIM_ALL) && frames) |
||
664 | break; |
||
769 | palkovsky | 665 | } |
759 | palkovsky | 666 | |
667 | if (flags & SLAB_RECLAIM_ALL) { |
||
781 | palkovsky | 668 | /* Free cpu-bound magazines */ |
759 | palkovsky | 669 | /* Destroy CPU magazines */ |
670 | for (i=0; i<config.cpu_count; i++) { |
||
781 | palkovsky | 671 | spinlock_lock(&cache->mag_cache[i].lock); |
672 | |||
759 | palkovsky | 673 | mag = cache->mag_cache[i].current; |
674 | if (mag) |
||
675 | frames += magazine_destroy(cache, mag); |
||
676 | cache->mag_cache[i].current = NULL; |
||
677 | |||
678 | mag = cache->mag_cache[i].last; |
||
679 | if (mag) |
||
680 | frames += magazine_destroy(cache, mag); |
||
681 | cache->mag_cache[i].last = NULL; |
||
781 | palkovsky | 682 | |
683 | spinlock_unlock(&cache->mag_cache[i].lock); |
||
759 | palkovsky | 684 | } |
685 | } |
||
767 | palkovsky | 686 | |
759 | palkovsky | 687 | return frames; |
688 | } |
||
689 | |||
690 | /** Check that there are no slabs and remove cache from system */ |
||
691 | void slab_cache_destroy(slab_cache_t *cache) |
||
692 | { |
||
781 | palkovsky | 693 | ipl_t ipl; |
694 | |||
695 | /* First remove cache from link, so that we don't need |
||
696 | * to disable interrupts later |
||
697 | */ |
||
698 | |||
699 | ipl = interrupts_disable(); |
||
700 | spinlock_lock(&slab_cache_lock); |
||
701 | |||
702 | list_remove(&cache->link); |
||
703 | |||
704 | spinlock_unlock(&slab_cache_lock); |
||
705 | interrupts_restore(ipl); |
||
706 | |||
759 | palkovsky | 707 | /* Do not lock anything, we assume the software is correct and |
708 | * does not touch the cache when it decides to destroy it */ |
||
709 | |||
710 | /* Destroy all magazines */ |
||
711 | _slab_reclaim(cache, SLAB_RECLAIM_ALL); |
||
712 | |||
713 | /* All slabs must be empty */ |
||
714 | if (!list_empty(&cache->full_slabs) \ |
||
715 | || !list_empty(&cache->partial_slabs)) |
||
716 | panic("Destroying cache that is not empty."); |
||
717 | |||
789 | palkovsky | 718 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE)) |
822 | palkovsky | 719 | free(cache->mag_cache); |
769 | palkovsky | 720 | slab_free(&slab_cache_cache, cache); |
759 | palkovsky | 721 | } |
722 | |||
723 | /** Allocate new object from cache - if no flags given, always returns |
||
724 | memory */ |
||
725 | void * slab_alloc(slab_cache_t *cache, int flags) |
||
726 | { |
||
727 | ipl_t ipl; |
||
728 | void *result = NULL; |
||
773 | palkovsky | 729 | |
759 | palkovsky | 730 | /* Disable interrupts to avoid deadlocks with interrupt handlers */ |
731 | ipl = interrupts_disable(); |
||
771 | palkovsky | 732 | |
814 | palkovsky | 733 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE)) { |
759 | palkovsky | 734 | result = magazine_obj_get(cache); |
814 | palkovsky | 735 | } |
776 | palkovsky | 736 | if (!result) |
759 | palkovsky | 737 | result = slab_obj_create(cache, flags); |
738 | |||
769 | palkovsky | 739 | interrupts_restore(ipl); |
740 | |||
764 | palkovsky | 741 | if (result) |
742 | atomic_inc(&cache->allocated_objs); |
||
743 | |||
759 | palkovsky | 744 | return result; |
745 | } |
||
746 | |||
771 | palkovsky | 747 | /** Return object to cache, use slab if known */ |
748 | static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab) |
||
759 | palkovsky | 749 | { |
750 | ipl_t ipl; |
||
751 | |||
752 | ipl = interrupts_disable(); |
||
753 | |||
762 | palkovsky | 754 | if ((cache->flags & SLAB_CACHE_NOMAGAZINE) \ |
755 | || magazine_obj_put(cache, obj)) { |
||
776 | palkovsky | 756 | |
771 | palkovsky | 757 | slab_obj_destroy(cache, obj, slab); |
776 | palkovsky | 758 | |
759 | palkovsky | 759 | } |
769 | palkovsky | 760 | interrupts_restore(ipl); |
764 | palkovsky | 761 | atomic_dec(&cache->allocated_objs); |
759 | palkovsky | 762 | } |
763 | |||
771 | palkovsky | 764 | /** Return slab object to cache */ |
765 | void slab_free(slab_cache_t *cache, void *obj) |
||
766 | { |
||
767 | _slab_free(cache,obj,NULL); |
||
768 | } |
||
769 | |||
759 | palkovsky | 770 | /* Go through all caches and reclaim what is possible */ |
771 | count_t slab_reclaim(int flags) |
||
772 | { |
||
773 | slab_cache_t *cache; |
||
774 | link_t *cur; |
||
775 | count_t frames = 0; |
||
776 | |||
777 | spinlock_lock(&slab_cache_lock); |
||
778 | |||
776 | palkovsky | 779 | /* TODO: Add assert, that interrupts are disabled, otherwise |
780 | * memory allocation from interrupts can deadlock. |
||
781 | */ |
||
782 | |||
759 | palkovsky | 783 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
784 | cache = list_get_instance(cur, slab_cache_t, link); |
||
785 | frames += _slab_reclaim(cache, flags); |
||
786 | } |
||
787 | |||
788 | spinlock_unlock(&slab_cache_lock); |
||
789 | |||
790 | return frames; |
||
791 | } |
||
792 | |||
793 | |||
794 | /* Print list of slabs */ |
||
795 | void slab_print_list(void) |
||
796 | { |
||
797 | slab_cache_t *cache; |
||
798 | link_t *cur; |
||
783 | palkovsky | 799 | ipl_t ipl; |
800 | |||
801 | ipl = interrupts_disable(); |
||
759 | palkovsky | 802 | spinlock_lock(&slab_cache_lock); |
1248 | jermar | 803 | printf("slab name\t Osize\t Pages\t Obj/pg\t Slabs\t Cached\tAllocobjs\tCtl\n"); |
759 | palkovsky | 804 | for (cur = slab_cache_list.next;cur!=&slab_cache_list; cur=cur->next) { |
805 | cache = list_get_instance(cur, slab_cache_t, link); |
||
1224 | cejka | 806 | printf("%s\t%7zd\t%7zd\t%7zd\t%7zd\t%7zd\t%7zd\t\t%s\n", cache->name, cache->size, |
766 | palkovsky | 807 | (1 << cache->order), cache->objects, |
767 | palkovsky | 808 | atomic_get(&cache->allocated_slabs), |
809 | atomic_get(&cache->cached_objs), |
||
766 | palkovsky | 810 | atomic_get(&cache->allocated_objs), |
811 | cache->flags & SLAB_CACHE_SLINSIDE ? "In" : "Out"); |
||
759 | palkovsky | 812 | } |
813 | spinlock_unlock(&slab_cache_lock); |
||
783 | palkovsky | 814 | interrupts_restore(ipl); |
759 | palkovsky | 815 | } |
816 | |||
817 | void slab_cache_init(void) |
||
818 | { |
||
771 | palkovsky | 819 | int i, size; |
820 | |||
759 | palkovsky | 821 | /* Initialize magazine cache */ |
822 | _slab_cache_create(&mag_cache, |
||
823 | "slab_magazine", |
||
824 | sizeof(slab_magazine_t)+SLAB_MAG_SIZE*sizeof(void*), |
||
825 | sizeof(__address), |
||
826 | NULL, NULL, |
||
769 | palkovsky | 827 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
828 | /* Initialize slab_cache cache */ |
||
829 | _slab_cache_create(&slab_cache_cache, |
||
830 | "slab_cache", |
||
789 | palkovsky | 831 | sizeof(slab_cache_cache), |
769 | palkovsky | 832 | sizeof(__address), |
833 | NULL, NULL, |
||
834 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE); |
||
835 | /* Initialize external slab cache */ |
||
836 | slab_extern_cache = slab_cache_create("slab_extern", |
||
837 | sizeof(slab_t), |
||
838 | 0, NULL, NULL, |
||
789 | palkovsky | 839 | SLAB_CACHE_SLINSIDE | SLAB_CACHE_MAGDEFERRED); |
759 | palkovsky | 840 | |
841 | /* Initialize structures for malloc */ |
||
771 | palkovsky | 842 | for (i=0, size=(1<<SLAB_MIN_MALLOC_W); |
843 | i < (SLAB_MAX_MALLOC_W-SLAB_MIN_MALLOC_W+1); |
||
844 | i++, size <<= 1) { |
||
845 | malloc_caches[i] = slab_cache_create(malloc_names[i], |
||
846 | size, 0, |
||
789 | palkovsky | 847 | NULL,NULL, SLAB_CACHE_MAGDEFERRED); |
771 | palkovsky | 848 | } |
778 | palkovsky | 849 | #ifdef CONFIG_DEBUG |
850 | _slab_initialized = 1; |
||
851 | #endif |
||
759 | palkovsky | 852 | } |
771 | palkovsky | 853 | |
789 | palkovsky | 854 | /** Enable cpu_cache |
855 | * |
||
856 | * Kernel calls this function, when it knows the real number of |
||
857 | * processors. |
||
858 | * Allocate slab for cpucache and enable it on all existing |
||
859 | * slabs that are SLAB_CACHE_MAGDEFERRED |
||
860 | */ |
||
861 | void slab_enable_cpucache(void) |
||
862 | { |
||
863 | link_t *cur; |
||
864 | slab_cache_t *s; |
||
865 | |||
791 | palkovsky | 866 | #ifdef CONFIG_DEBUG |
867 | _slab_initialized = 2; |
||
868 | #endif |
||
869 | |||
789 | palkovsky | 870 | spinlock_lock(&slab_cache_lock); |
871 | |||
872 | for (cur=slab_cache_list.next; cur != &slab_cache_list;cur=cur->next){ |
||
873 | s = list_get_instance(cur, slab_cache_t, link); |
||
874 | if ((s->flags & SLAB_CACHE_MAGDEFERRED) != SLAB_CACHE_MAGDEFERRED) |
||
875 | continue; |
||
876 | make_magcache(s); |
||
877 | s->flags &= ~SLAB_CACHE_MAGDEFERRED; |
||
878 | } |
||
879 | |||
880 | spinlock_unlock(&slab_cache_lock); |
||
881 | } |
||
882 | |||
771 | palkovsky | 883 | /**************************************/ |
884 | /* kalloc/kfree functions */ |
||
822 | palkovsky | 885 | void * malloc(unsigned int size, int flags) |
771 | palkovsky | 886 | { |
887 | int idx; |
||
778 | palkovsky | 888 | |
889 | ASSERT(_slab_initialized); |
||
1288 | jermar | 890 | ASSERT(size && size <= (1 << SLAB_MAX_MALLOC_W)); |
771 | palkovsky | 891 | |
892 | if (size < (1 << SLAB_MIN_MALLOC_W)) |
||
893 | size = (1 << SLAB_MIN_MALLOC_W); |
||
894 | |||
895 | idx = fnzb(size-1) - SLAB_MIN_MALLOC_W + 1; |
||
896 | |||
897 | return slab_alloc(malloc_caches[idx], flags); |
||
898 | } |
||
899 | |||
822 | palkovsky | 900 | void free(void *obj) |
771 | palkovsky | 901 | { |
781 | palkovsky | 902 | slab_t *slab; |
903 | |||
904 | if (!obj) return; |
||
905 | |||
906 | slab = obj2slab(obj); |
||
771 | palkovsky | 907 | _slab_free(slab->cache, obj, slab); |
908 | } |
||
1702 | cejka | 909 | |
910 | /** @} |
||
911 | */ |
||
912 |