| /* |
| * Copyright 2010 Marek Olšák <maraeo@gmail.com> |
| * Copyright 2016 Advanced Micro Devices, Inc. |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * on the rights to use, copy, modify, merge, publish, distribute, sub |
| * license, and/or sell copies of the Software, and to permit persons to whom |
| * the Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice (including the next |
| * paragraph) shall be included in all copies or substantial portions of the |
| * Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL |
| * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM, |
| * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR |
| * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE |
| * USE OR OTHER DEALINGS IN THE SOFTWARE. */ |
| |
| #include "slab.h" |
| #include "macros.h" |
| #include "u_atomic.h" |
| #include <stdint.h> |
| #include <stdbool.h> |
| #include <string.h> |
| |
| #define ALIGN(value, align) (((value) + (align) - 1) & ~((align) - 1)) |
| |
| #define SLAB_MAGIC_ALLOCATED 0xcafe4321 |
| #define SLAB_MAGIC_FREE 0x7ee01234 |
| |
| #ifdef DEBUG |
| #define SET_MAGIC(element, value) (element)->magic = (value) |
| #define CHECK_MAGIC(element, value) assert((element)->magic == (value)) |
| #else |
| #define SET_MAGIC(element, value) |
| #define CHECK_MAGIC(element, value) |
| #endif |
| |
| /* One array element within a big buffer. */ |
| struct slab_element_header { |
| /* The next element in the free or migrated list. */ |
| struct slab_element_header *next; |
| |
| /* This is either |
| * - a pointer to the child pool to which this element belongs, or |
| * - a pointer to the orphaned page of the element, with the least |
| * significant bit set to 1. |
| */ |
| intptr_t owner; |
| |
| #ifdef DEBUG |
| intptr_t magic; |
| #endif |
| }; |
| |
| /* The page is an array of allocations in one block. */ |
| struct slab_page_header { |
| union { |
| /* Next page in the same child pool. */ |
| struct slab_page_header *next; |
| |
| /* Number of remaining, non-freed elements (for orphaned pages). */ |
| unsigned num_remaining; |
| } u; |
| /* Memory after the last member is dedicated to the page itself. |
| * The allocated size is always larger than this structure. |
| */ |
| }; |
| |
| |
| static struct slab_element_header * |
| slab_get_element(struct slab_parent_pool *parent, |
| struct slab_page_header *page, unsigned index) |
| { |
| return (struct slab_element_header*) |
| ((uint8_t*)&page[1] + (parent->element_size * index)); |
| } |
| |
| /* The given object/element belongs to an orphaned page (i.e. the owning child |
| * pool has been destroyed). Mark the element as freed and free the whole page |
| * when no elements are left in it. |
| */ |
| static void |
| slab_free_orphaned(struct slab_element_header *elt) |
| { |
| struct slab_page_header *page; |
| |
| assert(elt->owner & 1); |
| |
| page = (struct slab_page_header *)(elt->owner & ~(intptr_t)1); |
| if (!p_atomic_dec_return(&page->u.num_remaining)) |
| free(page); |
| } |
| |
| /** |
| * Create a parent pool for the allocation of same-sized objects. |
| * |
| * \param item_size Size of one object. |
| * \param num_items Number of objects to allocate at once. |
| */ |
| void |
| slab_create_parent(struct slab_parent_pool *parent, |
| unsigned item_size, |
| unsigned num_items) |
| { |
| mtx_init(&parent->mutex, mtx_plain); |
| parent->element_size = ALIGN(sizeof(struct slab_element_header) + item_size, |
| sizeof(intptr_t)); |
| parent->num_elements = num_items; |
| } |
| |
| void |
| slab_destroy_parent(struct slab_parent_pool *parent) |
| { |
| mtx_destroy(&parent->mutex); |
| } |
| |
| /** |
| * Create a child pool linked to the given parent. |
| */ |
| void slab_create_child(struct slab_child_pool *pool, |
| struct slab_parent_pool *parent) |
| { |
| pool->parent = parent; |
| pool->pages = NULL; |
| pool->free = NULL; |
| pool->migrated = NULL; |
| } |
| |
| /** |
| * Destroy the child pool. |
| * |
| * Pages associated to the pool will be orphaned. They are eventually freed |
| * when all objects in them are freed. |
| */ |
| void slab_destroy_child(struct slab_child_pool *pool) |
| { |
| mtx_lock(&pool->parent->mutex); |
| |
| while (pool->pages) { |
| struct slab_page_header *page = pool->pages; |
| pool->pages = page->u.next; |
| p_atomic_set(&page->u.num_remaining, pool->parent->num_elements); |
| |
| for (unsigned i = 0; i < pool->parent->num_elements; ++i) { |
| struct slab_element_header *elt = slab_get_element(pool->parent, page, i); |
| p_atomic_set(&elt->owner, (intptr_t)page | 1); |
| } |
| } |
| |
| while (pool->migrated) { |
| struct slab_element_header *elt = pool->migrated; |
| pool->migrated = elt->next; |
| slab_free_orphaned(elt); |
| } |
| |
| mtx_unlock(&pool->parent->mutex); |
| |
| while (pool->free) { |
| struct slab_element_header *elt = pool->free; |
| pool->free = elt->next; |
| slab_free_orphaned(elt); |
| } |
| |
| /* Guard against use-after-free. */ |
| pool->parent = NULL; |
| } |
| |
| static bool |
| slab_add_new_page(struct slab_child_pool *pool) |
| { |
| struct slab_page_header *page = malloc(sizeof(struct slab_page_header) + |
| pool->parent->num_elements * pool->parent->element_size); |
| |
| if (!page) |
| return false; |
| |
| for (unsigned i = 0; i < pool->parent->num_elements; ++i) { |
| struct slab_element_header *elt = slab_get_element(pool->parent, page, i); |
| elt->owner = (intptr_t)pool; |
| assert(!(elt->owner & 1)); |
| |
| elt->next = pool->free; |
| pool->free = elt; |
| SET_MAGIC(elt, SLAB_MAGIC_FREE); |
| } |
| |
| page->u.next = pool->pages; |
| pool->pages = page; |
| |
| return true; |
| } |
| |
| /** |
| * Allocate an object from the child pool. Single-threaded (i.e. the caller |
| * must ensure that no operation happens on the same child pool in another |
| * thread). |
| */ |
| void * |
| slab_alloc(struct slab_child_pool *pool) |
| { |
| struct slab_element_header *elt; |
| |
| if (!pool->free) { |
| /* First, collect elements that belong to us but were freed from a |
| * different child pool. |
| */ |
| mtx_lock(&pool->parent->mutex); |
| pool->free = pool->migrated; |
| pool->migrated = NULL; |
| mtx_unlock(&pool->parent->mutex); |
| |
| /* Now allocate a new page. */ |
| if (!pool->free && !slab_add_new_page(pool)) |
| return NULL; |
| } |
| |
| elt = pool->free; |
| pool->free = elt->next; |
| |
| CHECK_MAGIC(elt, SLAB_MAGIC_FREE); |
| SET_MAGIC(elt, SLAB_MAGIC_ALLOCATED); |
| |
| return &elt[1]; |
| } |
| |
| /** |
| * Free an object allocated from the slab. Single-threaded (i.e. the caller |
| * must ensure that no operation happens on the same child pool in another |
| * thread). |
| * |
| * Freeing an object in a different child pool from the one where it was |
| * allocated is allowed, as long the pool belong to the same parent. No |
| * additional locking is required in this case. |
| */ |
| void slab_free(struct slab_child_pool *pool, void *ptr) |
| { |
| struct slab_element_header *elt = ((struct slab_element_header*)ptr - 1); |
| intptr_t owner_int; |
| |
| CHECK_MAGIC(elt, SLAB_MAGIC_ALLOCATED); |
| SET_MAGIC(elt, SLAB_MAGIC_FREE); |
| |
| if (p_atomic_read(&elt->owner) == (intptr_t)pool) { |
| /* This is the simple case: The caller guarantees that we can safely |
| * access the free list. |
| */ |
| elt->next = pool->free; |
| pool->free = elt; |
| return; |
| } |
| |
| /* The slow case: migration or an orphaned page. */ |
| mtx_lock(&pool->parent->mutex); |
| |
| /* Note: we _must_ re-read elt->owner here because the owning child pool |
| * may have been destroyed by another thread in the meantime. |
| */ |
| owner_int = p_atomic_read(&elt->owner); |
| |
| if (!(owner_int & 1)) { |
| struct slab_child_pool *owner = (struct slab_child_pool *)owner_int; |
| elt->next = owner->migrated; |
| owner->migrated = elt; |
| mtx_unlock(&pool->parent->mutex); |
| } else { |
| mtx_unlock(&pool->parent->mutex); |
| |
| slab_free_orphaned(elt); |
| } |
| } |
| |
| /** |
| * Allocate an object from the slab. Single-threaded (no mutex). |
| */ |
| void * |
| slab_alloc_st(struct slab_mempool *pool) |
| { |
| return slab_alloc(&pool->child); |
| } |
| |
| /** |
| * Free an object allocated from the slab. Single-threaded (no mutex). |
| */ |
| void |
| slab_free_st(struct slab_mempool *pool, void *ptr) |
| { |
| slab_free(&pool->child, ptr); |
| } |
| |
| void |
| slab_destroy(struct slab_mempool *pool) |
| { |
| slab_destroy_child(&pool->child); |
| slab_destroy_parent(&pool->parent); |
| } |
| |
| /** |
| * Create an allocator for same-sized objects. |
| * |
| * \param item_size Size of one object. |
| * \param num_items Number of objects to allocate at once. |
| */ |
| void |
| slab_create(struct slab_mempool *pool, |
| unsigned item_size, |
| unsigned num_items) |
| { |
| slab_create_parent(&pool->parent, item_size, num_items); |
| slab_create_child(&pool->child, &pool->parent); |
| } |