1 // SPDX-License-Identifier: BSD-2-Clause 2 /* 3 * Copyright (c) 2014, STMicroelectronics International N.V. 4 * Copyright (c) 2018, Linaro Limited 5 */ 6 7 8 #include <assert.h> 9 #include <compiler.h> 10 #include <malloc.h> 11 #include <mempool.h> 12 #include <util.h> 13 14 #if defined(__KERNEL__) 15 #include <kernel/mutex.h> 16 #include <kernel/panic.h> 17 #include <kernel/thread.h> 18 #include <kernel/refcount.h> 19 #endif 20 21 /* 22 * Allocation of temporary memory buffers which are used in a stack like 23 * fashion. One exmaple is when a Big Number is needed for a temporary 24 * variable in a Big Number computation: Big Number operations (add,...), 25 * crypto algorithms (rsa, ecc,,...). 26 * 27 * The allocation algorithm takes memory buffers from a pool, 28 * characterized by (cf. struct mempool): 29 * - the total size (in bytes) of the pool 30 * - the offset of the last item allocated in the pool (struct 31 * mempool_item). This offset is -1 is nothing is allocated yet. 32 * 33 * Each item consists of (struct mempool_item) 34 * - the size of the item 35 * - the offsets, in the pool, of the previous and next items 36 * 37 * The allocation allocates an item for a given size. 38 * The allocation is performed in the pool after the last 39 * allocated items. This means: 40 * - the heap is never used. 41 * - there is no assumption on the size of the allocated memory buffers. Only 42 * the size of the pool will limit the allocation. 43 * - a constant time allocation and free as there is no list scan 44 * - but a potentially fragmented memory as the allocation does not take into 45 * account "holes" in the pool (allocation is performed after the last 46 * allocated variable). Indeed, this interface is supposed to be used 47 * with stack like allocations to avoid this issue. This means that 48 * allocated items: 49 * - should have a short life cycle 50 * - if an item A is allocated before another item B, then A should be 51 * released after B. 52 * So the potential fragmentation is mitigated. 53 */ 54 55 #define POOL_ALIGN __alignof__(long) 56 57 struct mempool { 58 size_t size; /* size of the memory pool, in bytes */ 59 ssize_t last_offset; /* offset to the last one */ 60 vaddr_t data; 61 #ifdef CFG_MEMPOOL_REPORT_LAST_OFFSET 62 ssize_t max_last_offset; 63 #endif 64 #if defined(__KERNEL__) 65 void (*release_mem)(void *ptr, size_t size); 66 struct mutex mu; 67 struct condvar cv; 68 struct refcount refc; 69 int owner; 70 #endif 71 }; 72 73 static void get_pool(struct mempool *pool __maybe_unused) 74 { 75 #if defined(__KERNEL__) 76 if (refcount_inc(&pool->refc)) { 77 if (pool->owner == thread_get_id()) 78 return; 79 refcount_dec(&pool->refc); 80 } 81 82 mutex_lock(&pool->mu); 83 84 /* Wait until the pool is available */ 85 while (pool->owner != THREAD_ID_INVALID) 86 condvar_wait(&pool->cv, &pool->mu); 87 88 pool->owner = thread_get_id(); 89 refcount_set(&pool->refc, 1); 90 91 mutex_unlock(&pool->mu); 92 #endif 93 } 94 95 static void put_pool(struct mempool *pool __maybe_unused) 96 { 97 #if defined(__KERNEL__) 98 assert(pool->owner == thread_get_id()); 99 100 if (refcount_dec(&pool->refc)) { 101 mutex_lock(&pool->mu); 102 103 pool->owner = THREAD_ID_INVALID; 104 condvar_signal(&pool->cv); 105 106 /* As the refcount is 0 there should be no items left */ 107 if (pool->last_offset >= 0) 108 panic(); 109 if (pool->release_mem) 110 pool->release_mem((void *)pool->data, pool->size); 111 112 mutex_unlock(&pool->mu); 113 } 114 #endif 115 } 116 117 struct mempool * 118 mempool_alloc_pool(void *data, size_t size, 119 void (*release_mem)(void *ptr, size_t size) __maybe_unused) 120 { 121 struct mempool *pool = calloc(1, sizeof(*pool)); 122 123 COMPILE_TIME_ASSERT(POOL_ALIGN >= __alignof__(struct mempool_item)); 124 assert(!((vaddr_t)data & (POOL_ALIGN - 1))); 125 126 if (pool) { 127 pool->size = size; 128 pool->data = (vaddr_t)data; 129 pool->last_offset = -1; 130 #if defined(__KERNEL__) 131 pool->release_mem = release_mem; 132 mutex_init(&pool->mu); 133 condvar_init(&pool->cv); 134 pool->owner = THREAD_ID_INVALID; 135 #endif 136 } 137 138 return pool; 139 } 140 141 void *mempool_alloc(struct mempool *pool, size_t size) 142 { 143 size_t offset; 144 struct mempool_item *new_item; 145 struct mempool_item *last_item = NULL; 146 147 get_pool(pool); 148 149 if (pool->last_offset < 0) { 150 offset = 0; 151 } else { 152 last_item = (struct mempool_item *)(pool->data + 153 pool->last_offset); 154 offset = pool->last_offset + last_item->size; 155 156 offset = ROUNDUP(offset, POOL_ALIGN); 157 if (offset > pool->size) 158 goto error; 159 } 160 161 size = sizeof(struct mempool_item) + size; 162 size = ROUNDUP(size, POOL_ALIGN); 163 if (offset + size > pool->size) 164 goto error; 165 166 new_item = (struct mempool_item *)(pool->data + offset); 167 new_item->size = size; 168 new_item->prev_item_offset = pool->last_offset; 169 if (last_item) 170 last_item->next_item_offset = offset; 171 new_item->next_item_offset = -1; 172 pool->last_offset = offset; 173 #ifdef CFG_MEMPOOL_REPORT_LAST_OFFSET 174 if (pool->last_offset > pool->max_last_offset) { 175 pool->max_last_offset = pool->last_offset; 176 DMSG("Max memory usage increased to %zu", 177 (size_t)pool->max_last_offset); 178 } 179 #endif 180 181 return new_item + 1; 182 183 error: 184 EMSG("Failed to allocate %zu bytes, please tune the pool size", size); 185 put_pool(pool); 186 return NULL; 187 } 188 189 void mempool_free(struct mempool *pool, void *ptr) 190 { 191 struct mempool_item *item; 192 struct mempool_item *prev_item; 193 struct mempool_item *next_item; 194 ssize_t last_offset = -1; 195 196 if (!ptr) 197 return; 198 199 item = (struct mempool_item *)((vaddr_t)ptr - 200 sizeof(struct mempool_item)); 201 if (item->prev_item_offset >= 0) { 202 prev_item = (struct mempool_item *)(pool->data + 203 item->prev_item_offset); 204 prev_item->next_item_offset = item->next_item_offset; 205 last_offset = item->prev_item_offset; 206 } 207 208 if (item->next_item_offset >= 0) { 209 next_item = (struct mempool_item *)(pool->data + 210 item->next_item_offset); 211 next_item->prev_item_offset = item->prev_item_offset; 212 last_offset = pool->last_offset; 213 } 214 215 pool->last_offset = last_offset; 216 put_pool(pool); 217 } 218