[4e147a6] | 1 | /*
|
---|
[df4ed85] | 2 | * Copyright (c) 2006 Ondrej Palkovsky
|
---|
[4e147a6] | 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 |
|
---|
[cc73a8a1] | 29 | /** @addtogroup genericmm
|
---|
[b45c443] | 30 | * @{
|
---|
| 31 | */
|
---|
| 32 |
|
---|
[9179d0a] | 33 | /**
|
---|
[b45c443] | 34 | * @file
|
---|
[da1bafb] | 35 | * @brief Slab allocator.
|
---|
[9179d0a] | 36 | *
|
---|
| 37 | * The slab allocator is closely modelled after OpenSolaris slab allocator.
|
---|
| 38 | * @see http://www.usenix.org/events/usenix01/full_papers/bonwick/bonwick_html/
|
---|
[fb10289b] | 39 | *
|
---|
| 40 | * with the following exceptions:
|
---|
[9179d0a] | 41 | * @li empty slabs are deallocated immediately
|
---|
[fb10289b] | 42 | * (in Linux they are kept in linked list, in Solaris ???)
|
---|
[9179d0a] | 43 | * @li empty magazines are deallocated when not needed
|
---|
[fb10289b] | 44 | * (in Solaris they are held in linked list in slab cache)
|
---|
| 45 | *
|
---|
[9179d0a] | 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
|
---|
[5b04fc7] | 49 | * supported, but we would need to adjust allocation strategy)
|
---|
[fb10289b] | 50 | *
|
---|
[9179d0a] | 51 | * The slab allocator supports per-CPU caches ('magazines') to facilitate
|
---|
[da1bafb] | 52 | * good SMP scaling.
|
---|
[fb10289b] | 53 | *
|
---|
| 54 | * When a new object is being allocated, it is first checked, if it is
|
---|
[7669bcf] | 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.
|
---|
[fb10289b] | 58 | *
|
---|
[7669bcf] | 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,
|
---|
[9179d0a] | 61 | * the object is deallocated into slab). If the magazine is full, it is
|
---|
[7669bcf] | 62 | * put into cpu-shared list of magazines and a new one is allocated.
|
---|
[fb10289b] | 63 | *
|
---|
[7669bcf] | 64 | * The CPU-bound magazine is actually a pair of magazines in order to avoid
|
---|
[fb10289b] | 65 | * thrashing when somebody is allocating/deallocating 1 item at the magazine
|
---|
| 66 | * size boundary. LIFO order is enforced, which should avoid fragmentation
|
---|
[da1bafb] | 67 | * as much as possible.
|
---|
| 68 | *
|
---|
[7669bcf] | 69 | * Every cache contains list of full slabs and list of partially full slabs.
|
---|
[9179d0a] | 70 | * Empty slabs are immediately freed (thrashing will be avoided because
|
---|
[da1bafb] | 71 | * of magazines).
|
---|
[fb10289b] | 72 | *
|
---|
[9179d0a] | 73 | * The slab information structure is kept inside the data area, if possible.
|
---|
[fb10289b] | 74 | * The cache can be marked that it should not use magazines. This is used
|
---|
[9179d0a] | 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).
|
---|
[fb10289b] | 77 | *
|
---|
[7669bcf] | 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().
|
---|
[fb10289b] | 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 | *
|
---|
[cc73a8a1] | 86 | * @todo
|
---|
[9179d0a] | 87 | * For better CPU-scaling the magazine allocation strategy should
|
---|
[10e16a7] | 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 | *
|
---|
[cc73a8a1] | 96 | * @todo
|
---|
[da1bafb] | 97 | * It might be good to add granularity of locks even to slab level,
|
---|
[cc73a8a1] | 98 | * we could then try_spinlock over all partial slabs and thus improve
|
---|
[da1bafb] | 99 | * scalability even on slab level.
|
---|
| 100 | *
|
---|
[fb10289b] | 101 | */
|
---|
| 102 |
|
---|
[63e27ef] | 103 | #include <assert.h>
|
---|
[4e147a6] | 104 | #include <synch/spinlock.h>
|
---|
| 105 | #include <mm/slab.h>
|
---|
[5c9a08b] | 106 | #include <adt/list.h>
|
---|
[44a7ee5] | 107 | #include <mem.h>
|
---|
[4e147a6] | 108 | #include <align.h>
|
---|
[a294ad0] | 109 | #include <mm/frame.h>
|
---|
[4e147a6] | 110 | #include <config.h>
|
---|
| 111 | #include <print.h>
|
---|
| 112 | #include <arch.h>
|
---|
| 113 | #include <panic.h>
|
---|
[c352c2e] | 114 | #include <bitops.h>
|
---|
[ce8aed1] | 115 | #include <macros.h>
|
---|
[1066041] | 116 | #include <cpu.h>
|
---|
[4e147a6] | 117 |
|
---|
[da1bafb] | 118 | IRQ_SPINLOCK_STATIC_INITIALIZE(slab_cache_lock);
|
---|
[fb10289b] | 119 | static LIST_INITIALIZE(slab_cache_list);
|
---|
| 120 |
|
---|
| 121 | /** Magazine cache */
|
---|
| 122 | static slab_cache_t mag_cache;
|
---|
[da1bafb] | 123 |
|
---|
[fb10289b] | 124 | /** Cache for cache descriptors */
|
---|
| 125 | static slab_cache_t slab_cache_cache;
|
---|
[da1bafb] | 126 |
|
---|
[fb10289b] | 127 | /** Cache for external slab descriptors
|
---|
| 128 | * This time we want per-cpu cache, so do not make it static
|
---|
[9179d0a] | 129 | * - using slab for internal slab structures will not deadlock,
|
---|
[fb10289b] | 130 | * as all slab structures are 'small' - control structures of
|
---|
| 131 | * their caches do not require further allocation
|
---|
| 132 | */
|
---|
| 133 | static slab_cache_t *slab_extern_cache;
|
---|
[da1bafb] | 134 |
|
---|
[c352c2e] | 135 | /** Caches for malloc */
|
---|
[ce8aed1] | 136 | static slab_cache_t *malloc_caches[SLAB_MAX_MALLOC_W - SLAB_MIN_MALLOC_W + 1];
|
---|
[da1bafb] | 137 |
|
---|
[a000878c] | 138 | static const char *malloc_names[] = {
|
---|
[ce8aed1] | 139 | "malloc-16",
|
---|
| 140 | "malloc-32",
|
---|
| 141 | "malloc-64",
|
---|
| 142 | "malloc-128",
|
---|
| 143 | "malloc-256",
|
---|
| 144 | "malloc-512",
|
---|
| 145 | "malloc-1K",
|
---|
| 146 | "malloc-2K",
|
---|
| 147 | "malloc-4K",
|
---|
| 148 | "malloc-8K",
|
---|
| 149 | "malloc-16K",
|
---|
| 150 | "malloc-32K",
|
---|
| 151 | "malloc-64K",
|
---|
| 152 | "malloc-128K",
|
---|
[c3ebc47] | 153 | "malloc-256K",
|
---|
| 154 | "malloc-512K",
|
---|
| 155 | "malloc-1M",
|
---|
| 156 | "malloc-2M",
|
---|
| 157 | "malloc-4M"
|
---|
[c352c2e] | 158 | };
|
---|
[a294ad0] | 159 |
|
---|
[fb10289b] | 160 | /** Slab descriptor */
|
---|
[a294ad0] | 161 | typedef struct {
|
---|
[da1bafb] | 162 | slab_cache_t *cache; /**< Pointer to parent cache. */
|
---|
| 163 | link_t link; /**< List of full/partial slabs. */
|
---|
| 164 | void *start; /**< Start address of first available item. */
|
---|
| 165 | size_t available; /**< Count of available items in this slab. */
|
---|
| 166 | size_t nextavail; /**< The index of next available item. */
|
---|
[ce8aed1] | 167 | } slab_t;
|
---|
[a294ad0] | 168 |
|
---|
[214f5bb] | 169 | #ifdef CONFIG_DEBUG
|
---|
[da1bafb] | 170 | static unsigned int _slab_initialized = 0;
|
---|
[214f5bb] | 171 | #endif
|
---|
| 172 |
|
---|
[a294ad0] | 173 | /**************************************/
|
---|
[9179d0a] | 174 | /* Slab allocation functions */
|
---|
[da1bafb] | 175 | /**************************************/
|
---|
[a294ad0] | 176 |
|
---|
[da1bafb] | 177 | /** Allocate frames for slab space and initialize
|
---|
[a294ad0] | 178 | *
|
---|
| 179 | */
|
---|
[7a0359b] | 180 | NO_TRACE static slab_t *slab_space_alloc(slab_cache_t *cache,
|
---|
| 181 | unsigned int flags)
|
---|
[a294ad0] | 182 | {
|
---|
[98000fb] | 183 | size_t zone = 0;
|
---|
[085d973] | 184 |
|
---|
[cd3b380] | 185 | uintptr_t data_phys =
|
---|
| 186 | frame_alloc_generic(cache->frames, flags, 0, &zone);
|
---|
| 187 | if (!data_phys)
|
---|
[a294ad0] | 188 | return NULL;
|
---|
[da1bafb] | 189 |
|
---|
[cd3b380] | 190 | void *data = (void *) PA2KA(data_phys);
|
---|
| 191 |
|
---|
[da1bafb] | 192 | slab_t *slab;
|
---|
| 193 | size_t fsize;
|
---|
| 194 |
|
---|
[46c1234] | 195 | if (!(cache->flags & SLAB_CACHE_SLINSIDE)) {
|
---|
[fb10289b] | 196 | slab = slab_alloc(slab_extern_cache, flags);
|
---|
[a294ad0] | 197 | if (!slab) {
|
---|
[5df1963] | 198 | frame_free(KA2PA(data), cache->frames);
|
---|
[a294ad0] | 199 | return NULL;
|
---|
| 200 | }
|
---|
| 201 | } else {
|
---|
[b0c2075] | 202 | fsize = FRAMES2SIZE(cache->frames);
|
---|
[a294ad0] | 203 | slab = data + fsize - sizeof(*slab);
|
---|
| 204 | }
|
---|
[e3c762cd] | 205 |
|
---|
[a294ad0] | 206 | /* Fill in slab structures */
|
---|
[da1bafb] | 207 | size_t i;
|
---|
[b0c2075] | 208 | for (i = 0; i < cache->frames; i++)
|
---|
[6c441cf8] | 209 | frame_set_parent(ADDR2PFN(KA2PA(data)) + i, slab, zone);
|
---|
[da1bafb] | 210 |
|
---|
[a294ad0] | 211 | slab->start = data;
|
---|
| 212 | slab->available = cache->objects;
|
---|
| 213 | slab->nextavail = 0;
|
---|
[4a5b2b0e] | 214 | slab->cache = cache;
|
---|
[da1bafb] | 215 |
|
---|
[6c441cf8] | 216 | for (i = 0; i < cache->objects; i++)
|
---|
[da1bafb] | 217 | *((size_t *) (slab->start + i * cache->size)) = i + 1;
|
---|
| 218 |
|
---|
[bc504ef2] | 219 | atomic_inc(&cache->allocated_slabs);
|
---|
[a294ad0] | 220 | return slab;
|
---|
| 221 | }
|
---|
| 222 |
|
---|
[da1bafb] | 223 | /** Deallocate space associated with slab
|
---|
[a294ad0] | 224 | *
|
---|
| 225 | * @return number of freed frames
|
---|
[da1bafb] | 226 | *
|
---|
[a294ad0] | 227 | */
|
---|
[7a0359b] | 228 | NO_TRACE static size_t slab_space_free(slab_cache_t *cache, slab_t *slab)
|
---|
[a294ad0] | 229 | {
|
---|
[5df1963] | 230 | frame_free(KA2PA(slab->start), slab->cache->frames);
|
---|
[da1bafb] | 231 | if (!(cache->flags & SLAB_CACHE_SLINSIDE))
|
---|
[fb10289b] | 232 | slab_free(slab_extern_cache, slab);
|
---|
[da1bafb] | 233 |
|
---|
[bc504ef2] | 234 | atomic_dec(&cache->allocated_slabs);
|
---|
| 235 |
|
---|
[b0c2075] | 236 | return cache->frames;
|
---|
[a294ad0] | 237 | }
|
---|
| 238 |
|
---|
| 239 | /** Map object to slab structure */
|
---|
[7a0359b] | 240 | NO_TRACE static slab_t *obj2slab(void *obj)
|
---|
[a294ad0] | 241 | {
|
---|
[ce8aed1] | 242 | return (slab_t *) frame_get_parent(ADDR2PFN(KA2PA(obj)), 0);
|
---|
[a294ad0] | 243 | }
|
---|
| 244 |
|
---|
[da1bafb] | 245 | /******************/
|
---|
[9179d0a] | 246 | /* Slab functions */
|
---|
[da1bafb] | 247 | /******************/
|
---|
[4e147a6] | 248 |
|
---|
[da1bafb] | 249 | /** Return object to slab and call a destructor
|
---|
[4e147a6] | 250 | *
|
---|
[a294ad0] | 251 | * @param slab If the caller knows directly slab of the object, otherwise NULL
|
---|
| 252 | *
|
---|
[4e147a6] | 253 | * @return Number of freed pages
|
---|
[da1bafb] | 254 | *
|
---|
[4e147a6] | 255 | */
|
---|
[7a0359b] | 256 | NO_TRACE static size_t slab_obj_destroy(slab_cache_t *cache, void *obj,
|
---|
| 257 | slab_t *slab)
|
---|
[4e147a6] | 258 | {
|
---|
[a294ad0] | 259 | if (!slab)
|
---|
| 260 | slab = obj2slab(obj);
|
---|
[da1bafb] | 261 |
|
---|
[63e27ef] | 262 | assert(slab->cache == cache);
|
---|
[da1bafb] | 263 |
|
---|
| 264 | size_t freed = 0;
|
---|
| 265 |
|
---|
[266294a9] | 266 | if (cache->destructor)
|
---|
| 267 | freed = cache->destructor(obj);
|
---|
| 268 |
|
---|
[ddb56be] | 269 | irq_spinlock_lock(&cache->slablock, true);
|
---|
[63e27ef] | 270 | assert(slab->available < cache->objects);
|
---|
[da1bafb] | 271 |
|
---|
| 272 | *((size_t *) obj) = slab->nextavail;
|
---|
[46c1234] | 273 | slab->nextavail = (obj - slab->start) / cache->size;
|
---|
[a294ad0] | 274 | slab->available++;
|
---|
[da1bafb] | 275 |
|
---|
[a294ad0] | 276 | /* Move it to correct list */
|
---|
| 277 | if (slab->available == cache->objects) {
|
---|
| 278 | /* Free associated memory */
|
---|
| 279 | list_remove(&slab->link);
|
---|
[ddb56be] | 280 | irq_spinlock_unlock(&cache->slablock, true);
|
---|
[da1bafb] | 281 |
|
---|
[266294a9] | 282 | return freed + slab_space_free(cache, slab);
|
---|
[e72b0a3] | 283 | } else if (slab->available == 1) {
|
---|
| 284 | /* It was in full, move to partial */
|
---|
| 285 | list_remove(&slab->link);
|
---|
| 286 | list_prepend(&slab->link, &cache->partial_slabs);
|
---|
[a294ad0] | 287 | }
|
---|
[da1bafb] | 288 |
|
---|
[ddb56be] | 289 | irq_spinlock_unlock(&cache->slablock, true);
|
---|
[266294a9] | 290 | return freed;
|
---|
[a294ad0] | 291 | }
|
---|
[4e147a6] | 292 |
|
---|
[da1bafb] | 293 | /** Take new object from slab or create new if needed
|
---|
[4e147a6] | 294 | *
|
---|
| 295 | * @return Object address or null
|
---|
[da1bafb] | 296 | *
|
---|
[4e147a6] | 297 | */
|
---|
[7a0359b] | 298 | NO_TRACE static void *slab_obj_create(slab_cache_t *cache, unsigned int flags)
|
---|
[4e147a6] | 299 | {
|
---|
[ddb56be] | 300 | irq_spinlock_lock(&cache->slablock, true);
|
---|
[da1bafb] | 301 |
|
---|
| 302 | slab_t *slab;
|
---|
| 303 |
|
---|
[a294ad0] | 304 | if (list_empty(&cache->partial_slabs)) {
|
---|
[da1bafb] | 305 | /*
|
---|
| 306 | * Allow recursion and reclaiming
|
---|
[9179d0a] | 307 | * - this should work, as the slab control structures
|
---|
[e3c762cd] | 308 | * are small and do not need to allocate with anything
|
---|
| 309 | * other than frame_alloc when they are allocating,
|
---|
[a294ad0] | 310 | * that's why we should get recursion at most 1-level deep
|
---|
[da1bafb] | 311 | *
|
---|
[a294ad0] | 312 | */
|
---|
[ddb56be] | 313 | irq_spinlock_unlock(&cache->slablock, true);
|
---|
[a294ad0] | 314 | slab = slab_space_alloc(cache, flags);
|
---|
[428aabf] | 315 | if (!slab)
|
---|
[e72b0a3] | 316 | return NULL;
|
---|
[da1bafb] | 317 |
|
---|
[ddb56be] | 318 | irq_spinlock_lock(&cache->slablock, true);
|
---|
[a294ad0] | 319 | } else {
|
---|
[55b77d9] | 320 | slab = list_get_instance(list_first(&cache->partial_slabs),
|
---|
| 321 | slab_t, link);
|
---|
[a294ad0] | 322 | list_remove(&slab->link);
|
---|
| 323 | }
|
---|
[da1bafb] | 324 |
|
---|
| 325 | void *obj = slab->start + slab->nextavail * cache->size;
|
---|
| 326 | slab->nextavail = *((size_t *) obj);
|
---|
[a294ad0] | 327 | slab->available--;
|
---|
[da1bafb] | 328 |
|
---|
[f3272e98] | 329 | if (!slab->available)
|
---|
[bc504ef2] | 330 | list_prepend(&slab->link, &cache->full_slabs);
|
---|
[a294ad0] | 331 | else
|
---|
[bc504ef2] | 332 | list_prepend(&slab->link, &cache->partial_slabs);
|
---|
[da1bafb] | 333 |
|
---|
[ddb56be] | 334 | irq_spinlock_unlock(&cache->slablock, true);
|
---|
[da1bafb] | 335 |
|
---|
| 336 | if ((cache->constructor) && (cache->constructor(obj, flags))) {
|
---|
[266294a9] | 337 | /* Bad, bad, construction failed */
|
---|
| 338 | slab_obj_destroy(cache, obj, slab);
|
---|
| 339 | return NULL;
|
---|
| 340 | }
|
---|
[da1bafb] | 341 |
|
---|
[a294ad0] | 342 | return obj;
|
---|
[4e147a6] | 343 | }
|
---|
| 344 |
|
---|
[da1bafb] | 345 | /****************************/
|
---|
[4e147a6] | 346 | /* CPU-Cache slab functions */
|
---|
[da1bafb] | 347 | /****************************/
|
---|
[4e147a6] | 348 |
|
---|
[da1bafb] | 349 | /** Find a full magazine in cache, take it from list and return it
|
---|
| 350 | *
|
---|
| 351 | * @param first If true, return first, else last mag.
|
---|
[5158549] | 352 | *
|
---|
| 353 | */
|
---|
[7a0359b] | 354 | NO_TRACE static slab_magazine_t *get_mag_from_cache(slab_cache_t *cache,
|
---|
| 355 | bool first)
|
---|
[5158549] | 356 | {
|
---|
| 357 | slab_magazine_t *mag = NULL;
|
---|
| 358 | link_t *cur;
|
---|
[da1bafb] | 359 |
|
---|
[4d194be] | 360 | irq_spinlock_lock(&cache->maglock, true);
|
---|
[5158549] | 361 | if (!list_empty(&cache->magazines)) {
|
---|
| 362 | if (first)
|
---|
[55b77d9] | 363 | cur = list_first(&cache->magazines);
|
---|
[5158549] | 364 | else
|
---|
[55b77d9] | 365 | cur = list_last(&cache->magazines);
|
---|
[da1bafb] | 366 |
|
---|
[5158549] | 367 | mag = list_get_instance(cur, slab_magazine_t, link);
|
---|
| 368 | list_remove(&mag->link);
|
---|
| 369 | atomic_dec(&cache->magazine_counter);
|
---|
| 370 | }
|
---|
[4d194be] | 371 | irq_spinlock_unlock(&cache->maglock, true);
|
---|
[25ebfbd] | 372 |
|
---|
[5158549] | 373 | return mag;
|
---|
| 374 | }
|
---|
| 375 |
|
---|
[da1bafb] | 376 | /** Prepend magazine to magazine list in cache
|
---|
| 377 | *
|
---|
| 378 | */
|
---|
[7a0359b] | 379 | NO_TRACE static void put_mag_to_cache(slab_cache_t *cache,
|
---|
| 380 | slab_magazine_t *mag)
|
---|
[5158549] | 381 | {
|
---|
[4d194be] | 382 | irq_spinlock_lock(&cache->maglock, true);
|
---|
[da1bafb] | 383 |
|
---|
[5158549] | 384 | list_prepend(&mag->link, &cache->magazines);
|
---|
| 385 | atomic_inc(&cache->magazine_counter);
|
---|
| 386 |
|
---|
[4d194be] | 387 | irq_spinlock_unlock(&cache->maglock, true);
|
---|
[5158549] | 388 | }
|
---|
| 389 |
|
---|
[da1bafb] | 390 | /** Free all objects in magazine and free memory associated with magazine
|
---|
[4e147a6] | 391 | *
|
---|
| 392 | * @return Number of freed pages
|
---|
[da1bafb] | 393 | *
|
---|
[4e147a6] | 394 | */
|
---|
[7a0359b] | 395 | NO_TRACE static size_t magazine_destroy(slab_cache_t *cache,
|
---|
| 396 | slab_magazine_t *mag)
|
---|
[4e147a6] | 397 | {
|
---|
[da1bafb] | 398 | size_t i;
|
---|
[98000fb] | 399 | size_t frames = 0;
|
---|
[da1bafb] | 400 |
|
---|
[6c441cf8] | 401 | for (i = 0; i < mag->busy; i++) {
|
---|
[a294ad0] | 402 | frames += slab_obj_destroy(cache, mag->objs[i], NULL);
|
---|
[4a5b2b0e] | 403 | atomic_dec(&cache->cached_objs);
|
---|
| 404 | }
|
---|
[4e147a6] | 405 |
|
---|
| 406 | slab_free(&mag_cache, mag);
|
---|
[da1bafb] | 407 |
|
---|
[4e147a6] | 408 | return frames;
|
---|
| 409 | }
|
---|
| 410 |
|
---|
[da1bafb] | 411 | /** Find full magazine, set it as current and return it
|
---|
| 412 | *
|
---|
[fb10289b] | 413 | */
|
---|
[7a0359b] | 414 | NO_TRACE static slab_magazine_t *get_full_current_mag(slab_cache_t *cache)
|
---|
[fb10289b] | 415 | {
|
---|
[da1bafb] | 416 | slab_magazine_t *cmag = cache->mag_cache[CPU->id].current;
|
---|
| 417 | slab_magazine_t *lastmag = cache->mag_cache[CPU->id].last;
|
---|
[7a0359b] | 418 |
|
---|
[63e27ef] | 419 | assert(irq_spinlock_locked(&cache->mag_cache[CPU->id].lock));
|
---|
[da1bafb] | 420 |
|
---|
[fb10289b] | 421 | if (cmag) { /* First try local CPU magazines */
|
---|
| 422 | if (cmag->busy)
|
---|
| 423 | return cmag;
|
---|
[da1bafb] | 424 |
|
---|
| 425 | if ((lastmag) && (lastmag->busy)) {
|
---|
[fb10289b] | 426 | cache->mag_cache[CPU->id].current = lastmag;
|
---|
| 427 | cache->mag_cache[CPU->id].last = cmag;
|
---|
| 428 | return lastmag;
|
---|
| 429 | }
|
---|
| 430 | }
|
---|
[da1bafb] | 431 |
|
---|
[fb10289b] | 432 | /* Local magazines are empty, import one from magazine list */
|
---|
[da1bafb] | 433 | slab_magazine_t *newmag = get_mag_from_cache(cache, 1);
|
---|
[5158549] | 434 | if (!newmag)
|
---|
[fb10289b] | 435 | return NULL;
|
---|
[da1bafb] | 436 |
|
---|
[fb10289b] | 437 | if (lastmag)
|
---|
[5158549] | 438 | magazine_destroy(cache, lastmag);
|
---|
[da1bafb] | 439 |
|
---|
[fb10289b] | 440 | cache->mag_cache[CPU->id].last = cmag;
|
---|
| 441 | cache->mag_cache[CPU->id].current = newmag;
|
---|
[da1bafb] | 442 |
|
---|
[fb10289b] | 443 | return newmag;
|
---|
| 444 | }
|
---|
| 445 |
|
---|
[da1bafb] | 446 | /** Try to find object in CPU-cache magazines
|
---|
[4e147a6] | 447 | *
|
---|
| 448 | * @return Pointer to object or NULL if not available
|
---|
[da1bafb] | 449 | *
|
---|
[4e147a6] | 450 | */
|
---|
[7a0359b] | 451 | NO_TRACE static void *magazine_obj_get(slab_cache_t *cache)
|
---|
[4e147a6] | 452 | {
|
---|
[81e52f2a] | 453 | if (!CPU)
|
---|
| 454 | return NULL;
|
---|
[da1bafb] | 455 |
|
---|
[25ebfbd] | 456 | irq_spinlock_lock(&cache->mag_cache[CPU->id].lock, true);
|
---|
[da1bafb] | 457 |
|
---|
| 458 | slab_magazine_t *mag = get_full_current_mag(cache);
|
---|
[fb10289b] | 459 | if (!mag) {
|
---|
[25ebfbd] | 460 | irq_spinlock_unlock(&cache->mag_cache[CPU->id].lock, true);
|
---|
[fb10289b] | 461 | return NULL;
|
---|
[4e147a6] | 462 | }
|
---|
[da1bafb] | 463 |
|
---|
| 464 | void *obj = mag->objs[--mag->busy];
|
---|
[25ebfbd] | 465 | irq_spinlock_unlock(&cache->mag_cache[CPU->id].lock, true);
|
---|
[da1bafb] | 466 |
|
---|
[4a5b2b0e] | 467 | atomic_dec(&cache->cached_objs);
|
---|
| 468 |
|
---|
| 469 | return obj;
|
---|
[4e147a6] | 470 | }
|
---|
| 471 |
|
---|
[da1bafb] | 472 | /** Assure that the current magazine is empty, return pointer to it,
|
---|
| 473 | * or NULL if no empty magazine is available and cannot be allocated
|
---|
[4e147a6] | 474 | *
|
---|
[da1bafb] | 475 | * We have 2 magazines bound to processor.
|
---|
| 476 | * First try the current.
|
---|
| 477 | * If full, try the last.
|
---|
| 478 | * If full, put to magazines list.
|
---|
[4e147a6] | 479 | *
|
---|
[086a600] | 480 | */
|
---|
[7a0359b] | 481 | NO_TRACE static slab_magazine_t *make_empty_current_mag(slab_cache_t *cache)
|
---|
[086a600] | 482 | {
|
---|
[da1bafb] | 483 | slab_magazine_t *cmag = cache->mag_cache[CPU->id].current;
|
---|
| 484 | slab_magazine_t *lastmag = cache->mag_cache[CPU->id].last;
|
---|
| 485 |
|
---|
[63e27ef] | 486 | assert(irq_spinlock_locked(&cache->mag_cache[CPU->id].lock));
|
---|
[7a0359b] | 487 |
|
---|
[086a600] | 488 | if (cmag) {
|
---|
| 489 | if (cmag->busy < cmag->size)
|
---|
| 490 | return cmag;
|
---|
[da1bafb] | 491 |
|
---|
| 492 | if ((lastmag) && (lastmag->busy < lastmag->size)) {
|
---|
[086a600] | 493 | cache->mag_cache[CPU->id].last = cmag;
|
---|
| 494 | cache->mag_cache[CPU->id].current = lastmag;
|
---|
| 495 | return lastmag;
|
---|
| 496 | }
|
---|
| 497 | }
|
---|
[da1bafb] | 498 |
|
---|
[086a600] | 499 | /* current | last are full | nonexistent, allocate new */
|
---|
[da1bafb] | 500 |
|
---|
| 501 | /*
|
---|
| 502 | * We do not want to sleep just because of caching,
|
---|
| 503 | * especially we do not want reclaiming to start, as
|
---|
| 504 | * this would deadlock.
|
---|
| 505 | *
|
---|
| 506 | */
|
---|
| 507 | slab_magazine_t *newmag = slab_alloc(&mag_cache,
|
---|
| 508 | FRAME_ATOMIC | FRAME_NO_RECLAIM);
|
---|
[086a600] | 509 | if (!newmag)
|
---|
| 510 | return NULL;
|
---|
[da1bafb] | 511 |
|
---|
[086a600] | 512 | newmag->size = SLAB_MAG_SIZE;
|
---|
| 513 | newmag->busy = 0;
|
---|
[da1bafb] | 514 |
|
---|
[086a600] | 515 | /* Flush last to magazine list */
|
---|
[5158549] | 516 | if (lastmag)
|
---|
| 517 | put_mag_to_cache(cache, lastmag);
|
---|
[da1bafb] | 518 |
|
---|
[086a600] | 519 | /* Move current as last, save new as current */
|
---|
[da1bafb] | 520 | cache->mag_cache[CPU->id].last = cmag;
|
---|
| 521 | cache->mag_cache[CPU->id].current = newmag;
|
---|
| 522 |
|
---|
[086a600] | 523 | return newmag;
|
---|
| 524 | }
|
---|
| 525 |
|
---|
[da1bafb] | 526 | /** Put object into CPU-cache magazine
|
---|
| 527 | *
|
---|
| 528 | * @return 0 on success, -1 on no memory
|
---|
[086a600] | 529 | *
|
---|
[4e147a6] | 530 | */
|
---|
[7a0359b] | 531 | NO_TRACE static int magazine_obj_put(slab_cache_t *cache, void *obj)
|
---|
[4e147a6] | 532 | {
|
---|
[81e52f2a] | 533 | if (!CPU)
|
---|
| 534 | return -1;
|
---|
[da1bafb] | 535 |
|
---|
[25ebfbd] | 536 | irq_spinlock_lock(&cache->mag_cache[CPU->id].lock, true);
|
---|
[da1bafb] | 537 |
|
---|
| 538 | slab_magazine_t *mag = make_empty_current_mag(cache);
|
---|
[fb10289b] | 539 | if (!mag) {
|
---|
[25ebfbd] | 540 | irq_spinlock_unlock(&cache->mag_cache[CPU->id].lock, true);
|
---|
[fb10289b] | 541 | return -1;
|
---|
| 542 | }
|
---|
[4e147a6] | 543 |
|
---|
| 544 | mag->objs[mag->busy++] = obj;
|
---|
[da1bafb] | 545 |
|
---|
[25ebfbd] | 546 | irq_spinlock_unlock(&cache->mag_cache[CPU->id].lock, true);
|
---|
[da1bafb] | 547 |
|
---|
[4a5b2b0e] | 548 | atomic_inc(&cache->cached_objs);
|
---|
[da1bafb] | 549 |
|
---|
[4e147a6] | 550 | return 0;
|
---|
| 551 | }
|
---|
| 552 |
|
---|
[da1bafb] | 553 | /************************/
|
---|
[9179d0a] | 554 | /* Slab cache functions */
|
---|
[da1bafb] | 555 | /************************/
|
---|
[a294ad0] | 556 |
|
---|
[da1bafb] | 557 | /** Return number of objects that fit in certain cache size
|
---|
| 558 | *
|
---|
| 559 | */
|
---|
[7a0359b] | 560 | NO_TRACE static size_t comp_objects(slab_cache_t *cache)
|
---|
[a294ad0] | 561 | {
|
---|
| 562 | if (cache->flags & SLAB_CACHE_SLINSIDE)
|
---|
[b0c2075] | 563 | return (FRAMES2SIZE(cache->frames) - sizeof(slab_t)) /
|
---|
| 564 | cache->size;
|
---|
[da1bafb] | 565 | else
|
---|
[b0c2075] | 566 | return FRAMES2SIZE(cache->frames) / cache->size;
|
---|
[a294ad0] | 567 | }
|
---|
| 568 |
|
---|
[da1bafb] | 569 | /** Return wasted space in slab
|
---|
| 570 | *
|
---|
| 571 | */
|
---|
[7a0359b] | 572 | NO_TRACE static size_t badness(slab_cache_t *cache)
|
---|
[a294ad0] | 573 | {
|
---|
[da1bafb] | 574 | size_t objects = comp_objects(cache);
|
---|
[b0c2075] | 575 | size_t ssize = FRAMES2SIZE(cache->frames);
|
---|
[da1bafb] | 576 |
|
---|
[a294ad0] | 577 | if (cache->flags & SLAB_CACHE_SLINSIDE)
|
---|
| 578 | ssize -= sizeof(slab_t);
|
---|
[da1bafb] | 579 |
|
---|
[6c441cf8] | 580 | return ssize - objects * cache->size;
|
---|
[a294ad0] | 581 | }
|
---|
[4e147a6] | 582 |
|
---|
[da1bafb] | 583 | /** Initialize mag_cache structure in slab cache
|
---|
| 584 | *
|
---|
[8e1ea655] | 585 | */
|
---|
[7a0359b] | 586 | NO_TRACE static bool make_magcache(slab_cache_t *cache)
|
---|
[8e1ea655] | 587 | {
|
---|
[63e27ef] | 588 | assert(_slab_initialized >= 2);
|
---|
[da1bafb] | 589 |
|
---|
[46c1234] | 590 | cache->mag_cache = malloc(sizeof(slab_mag_cache_t) * config.cpu_count,
|
---|
[55821eea] | 591 | FRAME_ATOMIC);
|
---|
| 592 | if (!cache->mag_cache)
|
---|
| 593 | return false;
|
---|
[da1bafb] | 594 |
|
---|
| 595 | size_t i;
|
---|
[6c441cf8] | 596 | for (i = 0; i < config.cpu_count; i++) {
|
---|
[e32e092] | 597 | memsetb(&cache->mag_cache[i], sizeof(cache->mag_cache[i]), 0);
|
---|
[25ebfbd] | 598 | irq_spinlock_initialize(&cache->mag_cache[i].lock,
|
---|
[da1bafb] | 599 | "slab.cache.mag_cache[].lock");
|
---|
[8e1ea655] | 600 | }
|
---|
[da1bafb] | 601 |
|
---|
[55821eea] | 602 | return true;
|
---|
[8e1ea655] | 603 | }
|
---|
| 604 |
|
---|
[da1bafb] | 605 | /** Initialize allocated memory as a slab cache
|
---|
| 606 | *
|
---|
| 607 | */
|
---|
[7a0359b] | 608 | NO_TRACE static void _slab_cache_create(slab_cache_t *cache, const char *name,
|
---|
[da1bafb] | 609 | size_t size, size_t align, int (*constructor)(void *obj,
|
---|
| 610 | unsigned int kmflag), size_t (*destructor)(void *obj), unsigned int flags)
|
---|
[4e147a6] | 611 | {
|
---|
[63e27ef] | 612 | assert(size > 0);
|
---|
[7ec3c56] | 613 |
|
---|
[e32e092] | 614 | memsetb(cache, sizeof(*cache), 0);
|
---|
[4e147a6] | 615 | cache->name = name;
|
---|
[da1bafb] | 616 |
|
---|
[96b02eb9] | 617 | if (align < sizeof(sysarg_t))
|
---|
| 618 | align = sizeof(sysarg_t);
|
---|
[da1bafb] | 619 |
|
---|
[14e5d88] | 620 | size = ALIGN_UP(size, align);
|
---|
[da1bafb] | 621 |
|
---|
[a294ad0] | 622 | cache->size = size;
|
---|
[4e147a6] | 623 | cache->constructor = constructor;
|
---|
| 624 | cache->destructor = destructor;
|
---|
| 625 | cache->flags = flags;
|
---|
[da1bafb] | 626 |
|
---|
[4e147a6] | 627 | list_initialize(&cache->full_slabs);
|
---|
| 628 | list_initialize(&cache->partial_slabs);
|
---|
| 629 | list_initialize(&cache->magazines);
|
---|
[da1bafb] | 630 |
|
---|
[ddb56be] | 631 | irq_spinlock_initialize(&cache->slablock, "slab.cache.slablock");
|
---|
[4d194be] | 632 | irq_spinlock_initialize(&cache->maglock, "slab.cache.maglock");
|
---|
[da1bafb] | 633 |
|
---|
[46c1234] | 634 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE))
|
---|
[55821eea] | 635 | (void) make_magcache(cache);
|
---|
[da1bafb] | 636 |
|
---|
[4e147a6] | 637 | /* Compute slab sizes, object counts in slabs etc. */
|
---|
| 638 | if (cache->size < SLAB_INSIDE_SIZE)
|
---|
| 639 | cache->flags |= SLAB_CACHE_SLINSIDE;
|
---|
[da1bafb] | 640 |
|
---|
[b0c2075] | 641 | /* Minimum slab frames */
|
---|
| 642 | cache->frames = SIZE2FRAMES(cache->size);
|
---|
[da1bafb] | 643 |
|
---|
| 644 | while (badness(cache) > SLAB_MAX_BADNESS(cache))
|
---|
[b0c2075] | 645 | cache->frames <<= 1;
|
---|
[da1bafb] | 646 |
|
---|
[a294ad0] | 647 | cache->objects = comp_objects(cache);
|
---|
[da1bafb] | 648 |
|
---|
[14e5d88] | 649 | /* If info fits in, put it inside */
|
---|
| 650 | if (badness(cache) > sizeof(slab_t))
|
---|
| 651 | cache->flags |= SLAB_CACHE_SLINSIDE;
|
---|
[da1bafb] | 652 |
|
---|
[248fc1a] | 653 | /* Add cache to cache list */
|
---|
[da1bafb] | 654 | irq_spinlock_lock(&slab_cache_lock, true);
|
---|
[4e147a6] | 655 | list_append(&cache->link, &slab_cache_list);
|
---|
[da1bafb] | 656 | irq_spinlock_unlock(&slab_cache_lock, true);
|
---|
[4e147a6] | 657 | }
|
---|
| 658 |
|
---|
[da1bafb] | 659 | /** Create slab cache
|
---|
| 660 | *
|
---|
| 661 | */
|
---|
[a000878c] | 662 | slab_cache_t *slab_cache_create(const char *name, size_t size, size_t align,
|
---|
[da1bafb] | 663 | int (*constructor)(void *obj, unsigned int kmflag),
|
---|
| 664 | size_t (*destructor)(void *obj), unsigned int flags)
|
---|
[4e147a6] | 665 | {
|
---|
[da1bafb] | 666 | slab_cache_t *cache = slab_alloc(&slab_cache_cache, 0);
|
---|
[4e147a6] | 667 | _slab_cache_create(cache, name, size, align, constructor, destructor,
|
---|
[46c1234] | 668 | flags);
|
---|
[da1bafb] | 669 |
|
---|
[4e147a6] | 670 | return cache;
|
---|
| 671 | }
|
---|
| 672 |
|
---|
[da1bafb] | 673 | /** Reclaim space occupied by objects that are already free
|
---|
[4e147a6] | 674 | *
|
---|
| 675 | * @param flags If contains SLAB_RECLAIM_ALL, do aggressive freeing
|
---|
[da1bafb] | 676 | *
|
---|
[4e147a6] | 677 | * @return Number of freed pages
|
---|
[da1bafb] | 678 | *
|
---|
[4e147a6] | 679 | */
|
---|
[7a0359b] | 680 | NO_TRACE static size_t _slab_reclaim(slab_cache_t *cache, unsigned int flags)
|
---|
[4e147a6] | 681 | {
|
---|
| 682 | if (cache->flags & SLAB_CACHE_NOMAGAZINE)
|
---|
| 683 | return 0; /* Nothing to do */
|
---|
[da1bafb] | 684 |
|
---|
| 685 | /*
|
---|
| 686 | * We count up to original magazine count to avoid
|
---|
| 687 | * endless loop
|
---|
[5158549] | 688 | */
|
---|
[da1bafb] | 689 | atomic_count_t magcount = atomic_get(&cache->magazine_counter);
|
---|
| 690 |
|
---|
| 691 | slab_magazine_t *mag;
|
---|
| 692 | size_t frames = 0;
|
---|
| 693 |
|
---|
| 694 | while ((magcount--) && (mag = get_mag_from_cache(cache, 0))) {
|
---|
| 695 | frames += magazine_destroy(cache, mag);
|
---|
| 696 | if ((!(flags & SLAB_RECLAIM_ALL)) && (frames))
|
---|
[5158549] | 697 | break;
|
---|
[fb10289b] | 698 | }
|
---|
[4e147a6] | 699 |
|
---|
| 700 | if (flags & SLAB_RECLAIM_ALL) {
|
---|
[5158549] | 701 | /* Free cpu-bound magazines */
|
---|
[4e147a6] | 702 | /* Destroy CPU magazines */
|
---|
[da1bafb] | 703 | size_t i;
|
---|
[6c441cf8] | 704 | for (i = 0; i < config.cpu_count; i++) {
|
---|
[25ebfbd] | 705 | irq_spinlock_lock(&cache->mag_cache[i].lock, true);
|
---|
[da1bafb] | 706 |
|
---|
[4e147a6] | 707 | mag = cache->mag_cache[i].current;
|
---|
| 708 | if (mag)
|
---|
| 709 | frames += magazine_destroy(cache, mag);
|
---|
| 710 | cache->mag_cache[i].current = NULL;
|
---|
| 711 |
|
---|
| 712 | mag = cache->mag_cache[i].last;
|
---|
| 713 | if (mag)
|
---|
| 714 | frames += magazine_destroy(cache, mag);
|
---|
| 715 | cache->mag_cache[i].last = NULL;
|
---|
[da1bafb] | 716 |
|
---|
[25ebfbd] | 717 | irq_spinlock_unlock(&cache->mag_cache[i].lock, true);
|
---|
[5158549] | 718 | }
|
---|
[428aabf] | 719 | }
|
---|
[da1bafb] | 720 |
|
---|
[4e147a6] | 721 | return frames;
|
---|
| 722 | }
|
---|
| 723 |
|
---|
[da1bafb] | 724 | /** Check that there are no slabs and remove cache from system
|
---|
| 725 | *
|
---|
| 726 | */
|
---|
[4e147a6] | 727 | void slab_cache_destroy(slab_cache_t *cache)
|
---|
| 728 | {
|
---|
[da1bafb] | 729 | /*
|
---|
| 730 | * First remove cache from link, so that we don't need
|
---|
[5158549] | 731 | * to disable interrupts later
|
---|
[da1bafb] | 732 | *
|
---|
[5158549] | 733 | */
|
---|
[da1bafb] | 734 | irq_spinlock_lock(&slab_cache_lock, true);
|
---|
[5158549] | 735 | list_remove(&cache->link);
|
---|
[da1bafb] | 736 | irq_spinlock_unlock(&slab_cache_lock, true);
|
---|
| 737 |
|
---|
| 738 | /*
|
---|
| 739 | * Do not lock anything, we assume the software is correct and
|
---|
| 740 | * does not touch the cache when it decides to destroy it
|
---|
| 741 | *
|
---|
| 742 | */
|
---|
[4e147a6] | 743 |
|
---|
| 744 | /* Destroy all magazines */
|
---|
| 745 | _slab_reclaim(cache, SLAB_RECLAIM_ALL);
|
---|
[da1bafb] | 746 |
|
---|
[4e147a6] | 747 | /* All slabs must be empty */
|
---|
[da1bafb] | 748 | if ((!list_empty(&cache->full_slabs)) ||
|
---|
| 749 | (!list_empty(&cache->partial_slabs)))
|
---|
[4e147a6] | 750 | panic("Destroying cache that is not empty.");
|
---|
[da1bafb] | 751 |
|
---|
[8e1ea655] | 752 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE))
|
---|
[bb68433] | 753 | free(cache->mag_cache);
|
---|
[da1bafb] | 754 |
|
---|
[fb10289b] | 755 | slab_free(&slab_cache_cache, cache);
|
---|
[4e147a6] | 756 | }
|
---|
| 757 |
|
---|
[da1bafb] | 758 | /** Allocate new object from cache - if no flags given, always returns memory
|
---|
| 759 | *
|
---|
| 760 | */
|
---|
| 761 | void *slab_alloc(slab_cache_t *cache, unsigned int flags)
|
---|
[4e147a6] | 762 | {
|
---|
[da1bafb] | 763 | /* Disable interrupts to avoid deadlocks with interrupt handlers */
|
---|
| 764 | ipl_t ipl = interrupts_disable();
|
---|
| 765 |
|
---|
[4e147a6] | 766 | void *result = NULL;
|
---|
[c5613b72] | 767 |
|
---|
[da1bafb] | 768 | if (!(cache->flags & SLAB_CACHE_NOMAGAZINE))
|
---|
[4e147a6] | 769 | result = magazine_obj_get(cache);
|
---|
[da1bafb] | 770 |
|
---|
[428aabf] | 771 | if (!result)
|
---|
[4e147a6] | 772 | result = slab_obj_create(cache, flags);
|
---|
[da1bafb] | 773 |
|
---|
[4e147a6] | 774 | interrupts_restore(ipl);
|
---|
[da1bafb] | 775 |
|
---|
[fb10289b] | 776 | if (result)
|
---|
| 777 | atomic_inc(&cache->allocated_objs);
|
---|
[da1bafb] | 778 |
|
---|
[4e147a6] | 779 | return result;
|
---|
| 780 | }
|
---|
| 781 |
|
---|
[da1bafb] | 782 | /** Return object to cache, use slab if known
|
---|
| 783 | *
|
---|
| 784 | */
|
---|
[7a0359b] | 785 | NO_TRACE static void _slab_free(slab_cache_t *cache, void *obj, slab_t *slab)
|
---|
[4e147a6] | 786 | {
|
---|
[da1bafb] | 787 | ipl_t ipl = interrupts_disable();
|
---|
| 788 |
|
---|
[46c1234] | 789 | if ((cache->flags & SLAB_CACHE_NOMAGAZINE) ||
|
---|
[da1bafb] | 790 | (magazine_obj_put(cache, obj)))
|
---|
[c352c2e] | 791 | slab_obj_destroy(cache, obj, slab);
|
---|
[da1bafb] | 792 |
|
---|
[4e147a6] | 793 | interrupts_restore(ipl);
|
---|
[fb10289b] | 794 | atomic_dec(&cache->allocated_objs);
|
---|
[4e147a6] | 795 | }
|
---|
| 796 |
|
---|
[da1bafb] | 797 | /** Return slab object to cache
|
---|
| 798 | *
|
---|
| 799 | */
|
---|
[c352c2e] | 800 | void slab_free(slab_cache_t *cache, void *obj)
|
---|
| 801 | {
|
---|
[ce8aed1] | 802 | _slab_free(cache, obj, NULL);
|
---|
[c352c2e] | 803 | }
|
---|
| 804 |
|
---|
[ab6f2507] | 805 | /** Go through all caches and reclaim what is possible */
|
---|
[da1bafb] | 806 | size_t slab_reclaim(unsigned int flags)
|
---|
[4e147a6] | 807 | {
|
---|
[ab6f2507] | 808 | irq_spinlock_lock(&slab_cache_lock, true);
|
---|
[da1bafb] | 809 |
|
---|
[98000fb] | 810 | size_t frames = 0;
|
---|
[feeac0d] | 811 | list_foreach(slab_cache_list, link, slab_cache_t, cache) {
|
---|
[4e147a6] | 812 | frames += _slab_reclaim(cache, flags);
|
---|
| 813 | }
|
---|
[da1bafb] | 814 |
|
---|
[ab6f2507] | 815 | irq_spinlock_unlock(&slab_cache_lock, true);
|
---|
[da1bafb] | 816 |
|
---|
[4e147a6] | 817 | return frames;
|
---|
| 818 | }
|
---|
| 819 |
|
---|
[da1bafb] | 820 | /* Print list of slabs
|
---|
| 821 | *
|
---|
| 822 | */
|
---|
[4e147a6] | 823 | void slab_print_list(void)
|
---|
| 824 | {
|
---|
[ccb426c] | 825 | printf("[slab name ] [size ] [pages ] [obj/pg] [slabs ]"
|
---|
| 826 | " [cached] [alloc ] [ctl]\n");
|
---|
[da1bafb] | 827 |
|
---|
| 828 | size_t skip = 0;
|
---|
[599d6f5] | 829 | while (true) {
|
---|
| 830 | /*
|
---|
| 831 | * We must not hold the slab_cache_lock spinlock when printing
|
---|
| 832 | * the statistics. Otherwise we can easily deadlock if the print
|
---|
| 833 | * needs to allocate memory.
|
---|
| 834 | *
|
---|
| 835 | * Therefore, we walk through the slab cache list, skipping some
|
---|
| 836 | * amount of already processed caches during each iteration and
|
---|
| 837 | * gathering statistics about the first unprocessed cache. For
|
---|
| 838 | * the sake of printing the statistics, we realese the
|
---|
| 839 | * slab_cache_lock and reacquire it afterwards. Then the walk
|
---|
| 840 | * starts again.
|
---|
| 841 | *
|
---|
| 842 | * This limits both the efficiency and also accuracy of the
|
---|
| 843 | * obtained statistics. The efficiency is decreased because the
|
---|
| 844 | * time complexity of the algorithm is quadratic instead of
|
---|
| 845 | * linear. The accuracy is impacted because we drop the lock
|
---|
| 846 | * after processing one cache. If there is someone else
|
---|
| 847 | * manipulating the cache list, we might omit an arbitrary
|
---|
| 848 | * number of caches or process one cache multiple times.
|
---|
| 849 | * However, we don't bleed for this algorithm for it is only
|
---|
| 850 | * statistics.
|
---|
| 851 | */
|
---|
[da1bafb] | 852 |
|
---|
| 853 | irq_spinlock_lock(&slab_cache_lock, true);
|
---|
| 854 |
|
---|
| 855 | link_t *cur;
|
---|
| 856 | size_t i;
|
---|
[55b77d9] | 857 | for (i = 0, cur = slab_cache_list.head.next;
|
---|
| 858 | (i < skip) && (cur != &slab_cache_list.head);
|
---|
[da1bafb] | 859 | i++, cur = cur->next);
|
---|
| 860 |
|
---|
[55b77d9] | 861 | if (cur == &slab_cache_list.head) {
|
---|
[da1bafb] | 862 | irq_spinlock_unlock(&slab_cache_lock, true);
|
---|
[599d6f5] | 863 | break;
|
---|
| 864 | }
|
---|
[da1bafb] | 865 |
|
---|
[599d6f5] | 866 | skip++;
|
---|
[da1bafb] | 867 |
|
---|
| 868 | slab_cache_t *cache = list_get_instance(cur, slab_cache_t, link);
|
---|
| 869 |
|
---|
[a000878c] | 870 | const char *name = cache->name;
|
---|
[b0c2075] | 871 | size_t frames = cache->frames;
|
---|
[599d6f5] | 872 | size_t size = cache->size;
|
---|
[da1bafb] | 873 | size_t objects = cache->objects;
|
---|
[599d6f5] | 874 | long allocated_slabs = atomic_get(&cache->allocated_slabs);
|
---|
| 875 | long cached_objs = atomic_get(&cache->cached_objs);
|
---|
| 876 | long allocated_objs = atomic_get(&cache->allocated_objs);
|
---|
[da1bafb] | 877 | unsigned int flags = cache->flags;
|
---|
[599d6f5] | 878 |
|
---|
[da1bafb] | 879 | irq_spinlock_unlock(&slab_cache_lock, true);
|
---|
[6536a4a9] | 880 |
|
---|
[b0c2075] | 881 | printf("%-18s %8zu %8zu %8zu %8ld %8ld %8ld %-5s\n",
|
---|
| 882 | name, size, frames, objects, allocated_slabs,
|
---|
[599d6f5] | 883 | cached_objs, allocated_objs,
|
---|
| 884 | flags & SLAB_CACHE_SLINSIDE ? "in" : "out");
|
---|
[4e147a6] | 885 | }
|
---|
| 886 | }
|
---|
| 887 |
|
---|
| 888 | void slab_cache_init(void)
|
---|
| 889 | {
|
---|
| 890 | /* Initialize magazine cache */
|
---|
[f97f1e51] | 891 | _slab_cache_create(&mag_cache, "slab_magazine_t",
|
---|
[7ec3c56] | 892 | sizeof(slab_magazine_t) + SLAB_MAG_SIZE * sizeof(void *),
|
---|
[46c1234] | 893 | sizeof(uintptr_t), NULL, NULL, SLAB_CACHE_NOMAGAZINE |
|
---|
| 894 | SLAB_CACHE_SLINSIDE);
|
---|
[da1bafb] | 895 |
|
---|
[fb10289b] | 896 | /* Initialize slab_cache cache */
|
---|
[f97f1e51] | 897 | _slab_cache_create(&slab_cache_cache, "slab_cache_cache",
|
---|
[46c1234] | 898 | sizeof(slab_cache_cache), sizeof(uintptr_t), NULL, NULL,
|
---|
| 899 | SLAB_CACHE_NOMAGAZINE | SLAB_CACHE_SLINSIDE);
|
---|
[da1bafb] | 900 |
|
---|
[fb10289b] | 901 | /* Initialize external slab cache */
|
---|
[f97f1e51] | 902 | slab_extern_cache = slab_cache_create("slab_t", sizeof(slab_t), 0,
|
---|
[46c1234] | 903 | NULL, NULL, SLAB_CACHE_SLINSIDE | SLAB_CACHE_MAGDEFERRED);
|
---|
[da1bafb] | 904 |
|
---|
[4e147a6] | 905 | /* Initialize structures for malloc */
|
---|
[da1bafb] | 906 | size_t i;
|
---|
| 907 | size_t size;
|
---|
| 908 |
|
---|
[46c1234] | 909 | for (i = 0, size = (1 << SLAB_MIN_MALLOC_W);
|
---|
| 910 | i < (SLAB_MAX_MALLOC_W - SLAB_MIN_MALLOC_W + 1);
|
---|
| 911 | i++, size <<= 1) {
|
---|
| 912 | malloc_caches[i] = slab_cache_create(malloc_names[i], size, 0,
|
---|
| 913 | NULL, NULL, SLAB_CACHE_MAGDEFERRED);
|
---|
[c352c2e] | 914 | }
|
---|
[da1bafb] | 915 |
|
---|
[a000878c] | 916 | #ifdef CONFIG_DEBUG
|
---|
[04225a7] | 917 | _slab_initialized = 1;
|
---|
| 918 | #endif
|
---|
[c352c2e] | 919 | }
|
---|
| 920 |
|
---|
[8e1ea655] | 921 | /** Enable cpu_cache
|
---|
| 922 | *
|
---|
| 923 | * Kernel calls this function, when it knows the real number of
|
---|
[da1bafb] | 924 | * processors. Allocate slab for cpucache and enable it on all
|
---|
| 925 | * existing slabs that are SLAB_CACHE_MAGDEFERRED
|
---|
| 926 | *
|
---|
[8e1ea655] | 927 | */
|
---|
| 928 | void slab_enable_cpucache(void)
|
---|
| 929 | {
|
---|
[214f5bb] | 930 | #ifdef CONFIG_DEBUG
|
---|
| 931 | _slab_initialized = 2;
|
---|
| 932 | #endif
|
---|
[8e1ea655] | 933 |
|
---|
[da1bafb] | 934 | irq_spinlock_lock(&slab_cache_lock, false);
|
---|
| 935 |
|
---|
[feeac0d] | 936 | list_foreach(slab_cache_list, link, slab_cache_t, slab) {
|
---|
[da1bafb] | 937 | if ((slab->flags & SLAB_CACHE_MAGDEFERRED) !=
|
---|
[46c1234] | 938 | SLAB_CACHE_MAGDEFERRED)
|
---|
[8e1ea655] | 939 | continue;
|
---|
[da1bafb] | 940 |
|
---|
| 941 | (void) make_magcache(slab);
|
---|
| 942 | slab->flags &= ~SLAB_CACHE_MAGDEFERRED;
|
---|
[8e1ea655] | 943 | }
|
---|
[da1bafb] | 944 |
|
---|
| 945 | irq_spinlock_unlock(&slab_cache_lock, false);
|
---|
[8e1ea655] | 946 | }
|
---|
| 947 |
|
---|
[da1bafb] | 948 | void *malloc(size_t size, unsigned int flags)
|
---|
[c352c2e] | 949 | {
|
---|
[63e27ef] | 950 | assert(_slab_initialized);
|
---|
| 951 | assert(size <= (1 << SLAB_MAX_MALLOC_W));
|
---|
[c352c2e] | 952 |
|
---|
| 953 | if (size < (1 << SLAB_MIN_MALLOC_W))
|
---|
| 954 | size = (1 << SLAB_MIN_MALLOC_W);
|
---|
[da1bafb] | 955 |
|
---|
| 956 | uint8_t idx = fnzb(size - 1) - SLAB_MIN_MALLOC_W + 1;
|
---|
| 957 |
|
---|
[c352c2e] | 958 | return slab_alloc(malloc_caches[idx], flags);
|
---|
| 959 | }
|
---|
| 960 |
|
---|
[da1bafb] | 961 | void *realloc(void *ptr, size_t size, unsigned int flags)
|
---|
[c352c2e] | 962 | {
|
---|
[63e27ef] | 963 | assert(_slab_initialized);
|
---|
| 964 | assert(size <= (1 << SLAB_MAX_MALLOC_W));
|
---|
[ce8aed1] | 965 |
|
---|
| 966 | void *new_ptr;
|
---|
| 967 |
|
---|
| 968 | if (size > 0) {
|
---|
| 969 | if (size < (1 << SLAB_MIN_MALLOC_W))
|
---|
| 970 | size = (1 << SLAB_MIN_MALLOC_W);
|
---|
[da1bafb] | 971 | uint8_t idx = fnzb(size - 1) - SLAB_MIN_MALLOC_W + 1;
|
---|
[ce8aed1] | 972 |
|
---|
| 973 | new_ptr = slab_alloc(malloc_caches[idx], flags);
|
---|
| 974 | } else
|
---|
| 975 | new_ptr = NULL;
|
---|
| 976 |
|
---|
| 977 | if ((new_ptr != NULL) && (ptr != NULL)) {
|
---|
| 978 | slab_t *slab = obj2slab(ptr);
|
---|
| 979 | memcpy(new_ptr, ptr, min(size, slab->cache->size));
|
---|
| 980 | }
|
---|
| 981 |
|
---|
| 982 | if (ptr != NULL)
|
---|
| 983 | free(ptr);
|
---|
| 984 |
|
---|
| 985 | return new_ptr;
|
---|
| 986 | }
|
---|
[5158549] | 987 |
|
---|
[ce8aed1] | 988 | void free(void *ptr)
|
---|
| 989 | {
|
---|
| 990 | if (!ptr)
|
---|
[f3272e98] | 991 | return;
|
---|
[da1bafb] | 992 |
|
---|
[ce8aed1] | 993 | slab_t *slab = obj2slab(ptr);
|
---|
| 994 | _slab_free(slab->cache, ptr, slab);
|
---|
[4e147a6] | 995 | }
|
---|
[b45c443] | 996 |
|
---|
[cc73a8a1] | 997 | /** @}
|
---|
[b45c443] | 998 | */
|
---|