1 /* 2 * Copyright 2010 Marek Olk <maraeo (at) gmail.com> 3 * Copyright 2016 Advanced Micro Devices, Inc. 4 * 5 * Permission is hereby granted, free of charge, to any person obtaining a 6 * copy of this software and associated documentation files (the "Software"), 7 * to deal in the Software without restriction, including without limitation 8 * on the rights to use, copy, modify, merge, publish, distribute, sub 9 * license, and/or sell copies of the Software, and to permit persons to whom 10 * the Software is furnished to do so, subject to the following conditions: 11 * 12 * The above copyright notice and this permission notice (including the next 13 * paragraph) shall be included in all copies or substantial portions of the 14 * Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 19 * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM, 20 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 21 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 22 * USE OR OTHER DEALINGS IN THE SOFTWARE. */ 23 24 #include "slab.h" 25 #include "macros.h" 26 #include "u_atomic.h" 27 #include <stdint.h> 28 #include <stdbool.h> 29 #include <string.h> 30 31 #define ALIGN(value, align) (((value) + (align) - 1) & ~((align) - 1)) 32 33 #define SLAB_MAGIC_ALLOCATED 0xcafe4321 34 #define SLAB_MAGIC_FREE 0x7ee01234 35 36 #ifdef DEBUG 37 #define SET_MAGIC(element, value) (element)->magic = (value) 38 #define CHECK_MAGIC(element, value) assert((element)->magic == (value)) 39 #else 40 #define SET_MAGIC(element, value) 41 #define CHECK_MAGIC(element, value) 42 #endif 43 44 /* One array element within a big buffer. */ 45 struct slab_element_header { 46 /* The next element in the free or migrated list. */ 47 struct slab_element_header *next; 48 49 /* This is either 50 * - a pointer to the child pool to which this element belongs, or 51 * - a pointer to the orphaned page of the element, with the least 52 * significant bit set to 1. 53 */ 54 intptr_t owner; 55 56 #ifdef DEBUG 57 intptr_t magic; 58 #endif 59 }; 60 61 /* The page is an array of allocations in one block. */ 62 struct slab_page_header { 63 union { 64 /* Next page in the same child pool. */ 65 struct slab_page_header *next; 66 67 /* Number of remaining, non-freed elements (for orphaned pages). */ 68 unsigned num_remaining; 69 } u; 70 /* Memory after the last member is dedicated to the page itself. 71 * The allocated size is always larger than this structure. 72 */ 73 }; 74 75 76 static struct slab_element_header * 77 slab_get_element(struct slab_parent_pool *parent, 78 struct slab_page_header *page, unsigned index) 79 { 80 return (struct slab_element_header*) 81 ((uint8_t*)&page[1] + (parent->element_size * index)); 82 } 83 84 /* The given object/element belongs to an orphaned page (i.e. the owning child 85 * pool has been destroyed). Mark the element as freed and free the whole page 86 * when no elements are left in it. 87 */ 88 static void 89 slab_free_orphaned(struct slab_element_header *elt) 90 { 91 struct slab_page_header *page; 92 93 assert(elt->owner & 1); 94 95 page = (struct slab_page_header *)(elt->owner & ~(intptr_t)1); 96 if (!p_atomic_dec_return(&page->u.num_remaining)) 97 free(page); 98 } 99 100 /** 101 * Create a parent pool for the allocation of same-sized objects. 102 * 103 * \param item_size Size of one object. 104 * \param num_items Number of objects to allocate at once. 105 */ 106 void 107 slab_create_parent(struct slab_parent_pool *parent, 108 unsigned item_size, 109 unsigned num_items) 110 { 111 mtx_init(&parent->mutex, mtx_plain); 112 parent->element_size = ALIGN(sizeof(struct slab_element_header) + item_size, 113 sizeof(intptr_t)); 114 parent->num_elements = num_items; 115 } 116 117 void 118 slab_destroy_parent(struct slab_parent_pool *parent) 119 { 120 mtx_destroy(&parent->mutex); 121 } 122 123 /** 124 * Create a child pool linked to the given parent. 125 */ 126 void slab_create_child(struct slab_child_pool *pool, 127 struct slab_parent_pool *parent) 128 { 129 pool->parent = parent; 130 pool->pages = NULL; 131 pool->free = NULL; 132 pool->migrated = NULL; 133 } 134 135 /** 136 * Destroy the child pool. 137 * 138 * Pages associated to the pool will be orphaned. They are eventually freed 139 * when all objects in them are freed. 140 */ 141 void slab_destroy_child(struct slab_child_pool *pool) 142 { 143 if (!pool->parent) 144 return; /* the slab probably wasn't even created */ 145 146 mtx_lock(&pool->parent->mutex); 147 148 while (pool->pages) { 149 struct slab_page_header *page = pool->pages; 150 pool->pages = page->u.next; 151 p_atomic_set(&page->u.num_remaining, pool->parent->num_elements); 152 153 for (unsigned i = 0; i < pool->parent->num_elements; ++i) { 154 struct slab_element_header *elt = slab_get_element(pool->parent, page, i); 155 p_atomic_set(&elt->owner, (intptr_t)page | 1); 156 } 157 } 158 159 while (pool->migrated) { 160 struct slab_element_header *elt = pool->migrated; 161 pool->migrated = elt->next; 162 slab_free_orphaned(elt); 163 } 164 165 mtx_unlock(&pool->parent->mutex); 166 167 while (pool->free) { 168 struct slab_element_header *elt = pool->free; 169 pool->free = elt->next; 170 slab_free_orphaned(elt); 171 } 172 173 /* Guard against use-after-free. */ 174 pool->parent = NULL; 175 } 176 177 static bool 178 slab_add_new_page(struct slab_child_pool *pool) 179 { 180 struct slab_page_header *page = malloc(sizeof(struct slab_page_header) + 181 pool->parent->num_elements * pool->parent->element_size); 182 183 if (!page) 184 return false; 185 186 for (unsigned i = 0; i < pool->parent->num_elements; ++i) { 187 struct slab_element_header *elt = slab_get_element(pool->parent, page, i); 188 elt->owner = (intptr_t)pool; 189 assert(!(elt->owner & 1)); 190 191 elt->next = pool->free; 192 pool->free = elt; 193 SET_MAGIC(elt, SLAB_MAGIC_FREE); 194 } 195 196 page->u.next = pool->pages; 197 pool->pages = page; 198 199 return true; 200 } 201 202 /** 203 * Allocate an object from the child pool. Single-threaded (i.e. the caller 204 * must ensure that no operation happens on the same child pool in another 205 * thread). 206 */ 207 void * 208 slab_alloc(struct slab_child_pool *pool) 209 { 210 struct slab_element_header *elt; 211 212 if (!pool->free) { 213 /* First, collect elements that belong to us but were freed from a 214 * different child pool. 215 */ 216 mtx_lock(&pool->parent->mutex); 217 pool->free = pool->migrated; 218 pool->migrated = NULL; 219 mtx_unlock(&pool->parent->mutex); 220 221 /* Now allocate a new page. */ 222 if (!pool->free && !slab_add_new_page(pool)) 223 return NULL; 224 } 225 226 elt = pool->free; 227 pool->free = elt->next; 228 229 CHECK_MAGIC(elt, SLAB_MAGIC_FREE); 230 SET_MAGIC(elt, SLAB_MAGIC_ALLOCATED); 231 232 return &elt[1]; 233 } 234 235 /** 236 * Free an object allocated from the slab. Single-threaded (i.e. the caller 237 * must ensure that no operation happens on the same child pool in another 238 * thread). 239 * 240 * Freeing an object in a different child pool from the one where it was 241 * allocated is allowed, as long the pool belong to the same parent. No 242 * additional locking is required in this case. 243 */ 244 void slab_free(struct slab_child_pool *pool, void *ptr) 245 { 246 struct slab_element_header *elt = ((struct slab_element_header*)ptr - 1); 247 intptr_t owner_int; 248 249 CHECK_MAGIC(elt, SLAB_MAGIC_ALLOCATED); 250 SET_MAGIC(elt, SLAB_MAGIC_FREE); 251 252 if (p_atomic_read(&elt->owner) == (intptr_t)pool) { 253 /* This is the simple case: The caller guarantees that we can safely 254 * access the free list. 255 */ 256 elt->next = pool->free; 257 pool->free = elt; 258 return; 259 } 260 261 /* The slow case: migration or an orphaned page. */ 262 mtx_lock(&pool->parent->mutex); 263 264 /* Note: we _must_ re-read elt->owner here because the owning child pool 265 * may have been destroyed by another thread in the meantime. 266 */ 267 owner_int = p_atomic_read(&elt->owner); 268 269 if (!(owner_int & 1)) { 270 struct slab_child_pool *owner = (struct slab_child_pool *)owner_int; 271 elt->next = owner->migrated; 272 owner->migrated = elt; 273 mtx_unlock(&pool->parent->mutex); 274 } else { 275 mtx_unlock(&pool->parent->mutex); 276 277 slab_free_orphaned(elt); 278 } 279 } 280 281 /** 282 * Allocate an object from the slab. Single-threaded (no mutex). 283 */ 284 void * 285 slab_alloc_st(struct slab_mempool *pool) 286 { 287 return slab_alloc(&pool->child); 288 } 289 290 /** 291 * Free an object allocated from the slab. Single-threaded (no mutex). 292 */ 293 void 294 slab_free_st(struct slab_mempool *pool, void *ptr) 295 { 296 slab_free(&pool->child, ptr); 297 } 298 299 void 300 slab_destroy(struct slab_mempool *pool) 301 { 302 slab_destroy_child(&pool->child); 303 slab_destroy_parent(&pool->parent); 304 } 305 306 /** 307 * Create an allocator for same-sized objects. 308 * 309 * \param item_size Size of one object. 310 * \param num_items Number of objects to allocate at once. 311 */ 312 void 313 slab_create(struct slab_mempool *pool, 314 unsigned item_size, 315 unsigned num_items) 316 { 317 slab_create_parent(&pool->parent, item_size, num_items); 318 slab_create_child(&pool->child, &pool->parent); 319 } 320
