1ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák/* 2ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * Copyright 2010 Marek Olšák <maraeo@gmail.com> 3ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * 4ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * Permission is hereby granted, free of charge, to any person obtaining a 5ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * copy of this software and associated documentation files (the "Software"), 6ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * to deal in the Software without restriction, including without limitation 7ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * on the rights to use, copy, modify, merge, publish, distribute, sub 8ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * license, and/or sell copies of the Software, and to permit persons to whom 9ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * the Software is furnished to do so, subject to the following conditions: 10ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * 11ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * The above copyright notice and this permission notice (including the next 12ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * paragraph) shall be included in all copies or substantial portions of the 13ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * Software. 14ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * 15ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 18ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM, 19ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 20ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 21ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * USE OR OTHER DEALINGS IN THE SOFTWARE. */ 22ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 2380f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák#include "util/u_slab.h" 24ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 25ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák#include "util/u_math.h" 26ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák#include "util/u_memory.h" 27ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák#include "util/u_simple_list.h" 28ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 29ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák#include <stdio.h> 30ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 3180f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák#define UTIL_SLAB_MAGIC 0xcafe4321 32ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 33ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák/* The block is either allocated memory or free space. */ 3480f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákstruct util_slab_block { 35ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák /* The header. */ 36ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák /* The first next free block. */ 3780f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák struct util_slab_block *next_free; 38ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 39ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák intptr_t magic; 40ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 41ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák /* Memory after the last member is dedicated to the block itself. 42ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák * The allocated size is always larger than this structure. */ 43ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák}; 44ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 4580f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákstatic struct util_slab_block * 4680f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákutil_slab_get_block(struct util_slab_mempool *pool, 4780f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák struct util_slab_page *page, unsigned index) 48ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák{ 4980f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák return (struct util_slab_block*) 5080f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák ((uint8_t*)page + sizeof(struct util_slab_page) + 51fd03dd203f19301520d16de58552cc2fec5e6115Marek Olšák (pool->block_size * index)); 52ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák} 53ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 5480f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákstatic void util_slab_add_new_page(struct util_slab_mempool *pool) 55ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák{ 5680f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák struct util_slab_page *page; 5780f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák struct util_slab_block *block; 58ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák int i; 59ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 60ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák page = MALLOC(pool->page_size); 61ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák insert_at_tail(&pool->list, page); 62ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 63ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák /* Mark all blocks as free. */ 64ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák for (i = 0; i < pool->num_blocks-1; i++) { 6580f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák block = util_slab_get_block(pool, page, i); 6680f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák block->next_free = util_slab_get_block(pool, page, i+1); 6780f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák block->magic = UTIL_SLAB_MAGIC; 68ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák } 69ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 7080f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák block = util_slab_get_block(pool, page, pool->num_blocks-1); 71ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák block->next_free = pool->first_free; 7280f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák block->magic = UTIL_SLAB_MAGIC; 7380f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák pool->first_free = util_slab_get_block(pool, page, 0); 74ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pool->num_pages++; 75ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 76ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák#if 0 77ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák fprintf(stderr, "New page! Num of pages: %i\n", pool->num_pages); 78ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák#endif 79ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák} 80ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 8180f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákstatic void *util_slab_alloc_st(struct util_slab_mempool *pool) 82ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák{ 8380f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák struct util_slab_block *block; 84ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 85ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák if (!pool->first_free) 8680f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák util_slab_add_new_page(pool); 87ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 88ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák block = pool->first_free; 8980f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák assert(block->magic == UTIL_SLAB_MAGIC); 90ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pool->first_free = block->next_free; 91ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 9280f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák return (uint8_t*)block + sizeof(struct util_slab_block); 93ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák} 94ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 9580f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákstatic void util_slab_free_st(struct util_slab_mempool *pool, void *ptr) 96ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák{ 9780f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák struct util_slab_block *block = 9880f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák (struct util_slab_block*) 9980f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák ((uint8_t*)ptr - sizeof(struct util_slab_block)); 100ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 10180f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák assert(block->magic == UTIL_SLAB_MAGIC); 102ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák block->next_free = pool->first_free; 103ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pool->first_free = block; 104ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák} 105ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 10680f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákstatic void *util_slab_alloc_mt(struct util_slab_mempool *pool) 107ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák{ 108ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák void *mem; 109ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 110ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pipe_mutex_lock(pool->mutex); 11180f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák mem = util_slab_alloc_st(pool); 112ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pipe_mutex_unlock(pool->mutex); 113ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák return mem; 114ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák} 115ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 11680f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákstatic void util_slab_free_mt(struct util_slab_mempool *pool, void *ptr) 117ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák{ 118ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pipe_mutex_lock(pool->mutex); 11980f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák util_slab_free_st(pool, ptr); 120ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pipe_mutex_unlock(pool->mutex); 121ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák} 122ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 12380f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákvoid util_slab_set_thread_safety(struct util_slab_mempool *pool, 12480f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák enum util_slab_threading threading) 125ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák{ 126ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pool->threading = threading; 127ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 128ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák if (threading) { 12980f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák pool->alloc = util_slab_alloc_mt; 13080f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák pool->free = util_slab_free_mt; 131ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák } else { 13280f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák pool->alloc = util_slab_alloc_st; 13380f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák pool->free = util_slab_free_st; 134ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák } 135ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák} 136ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 13780f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákvoid util_slab_create(struct util_slab_mempool *pool, 13880f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák unsigned item_size, 13980f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák unsigned num_blocks, 14080f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák enum util_slab_threading threading) 141ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák{ 142ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák item_size = align(item_size, sizeof(intptr_t)); 143ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 144ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pool->num_pages = 0; 145ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pool->num_blocks = num_blocks; 14680f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák pool->block_size = sizeof(struct util_slab_block) + item_size; 147ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pool->block_size = align(pool->block_size, sizeof(intptr_t)); 14880f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák pool->page_size = sizeof(struct util_slab_page) + 149ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák num_blocks * pool->block_size; 150ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák pool->first_free = NULL; 151ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 152ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák make_empty_list(&pool->list); 153ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 154d26fb6916931f10e029429ecbf46e86484e7e956Marek Olšák pipe_mutex_init(pool->mutex); 155d26fb6916931f10e029429ecbf46e86484e7e956Marek Olšák 15680f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák util_slab_set_thread_safety(pool, threading); 157ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák} 158ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 15980f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšákvoid util_slab_destroy(struct util_slab_mempool *pool) 160ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák{ 16180f24c1575688e9cd4a5a811137f43b7e0a661bbMarek Olšák struct util_slab_page *page, *temp; 162ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 16399d5c1a13b97b9133a166c00c9fba1bec5f4bd9eMarek Olšák if (pool->list.next) { 16499d5c1a13b97b9133a166c00c9fba1bec5f4bd9eMarek Olšák foreach_s(page, temp, &pool->list) { 16599d5c1a13b97b9133a166c00c9fba1bec5f4bd9eMarek Olšák remove_from_list(page); 16699d5c1a13b97b9133a166c00c9fba1bec5f4bd9eMarek Olšák FREE(page); 16799d5c1a13b97b9133a166c00c9fba1bec5f4bd9eMarek Olšák } 168ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák } 169ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák 170a3a42e46965221b8f8249f0f1076fc3544b68d0eMarek Olšák pipe_mutex_destroy(pool->mutex); 171ad44b775e30b2740d25bb8330c9e8879f1ec5533Marek Olšák} 172