1 /* 2 This file is part of UFFS, the Ultra-low-cost Flash File System. 3 4 Copyright (C) 2005-2009 Ricky Zheng <[email protected]> 5 6 UFFS is free software; you can redistribute it and/or modify it under 7 the GNU Library General Public License as published by the Free Software 8 Foundation; either version 2 of the License, or (at your option) any 9 later version. 10 11 UFFS is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 or GNU Library General Public License, as applicable, for more details. 15 16 You should have received a copy of the GNU General Public License 17 and GNU Library General Public License along with UFFS; if not, write 18 to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 19 Boston, MA 02110-1301, USA. 20 21 As a special exception, if other files instantiate templates or use 22 macros or inline functions from this file, or you compile this file 23 and link it with other works to produce a work based on this file, 24 this file does not by itself cause the resulting work to be covered 25 by the GNU General Public License. However the source code for this 26 file must still be made available in accordance with section (3) of 27 the GNU General Public License v2. 28 29 This exception does not invalidate any other reasons why a work based 30 on this file might be covered by the GNU General Public License. 31 */ 32 33 /** 34 * \file uffs_pool.c 35 * \brief Fast fixed size memory pool management. 36 * \author Ricky Zheng, Simon Kallweit 37 */ 38 39 #include "uffs_config.h" 40 #include "uffs/uffs_types.h" 41 #include "uffs/uffs_os.h" 42 #include "uffs/uffs_public.h" 43 #include "uffs/uffs_pool.h" 44 45 /* 46 47 usage: 48 49 #define BUF_SIZE 32 50 #define NUM_BUFS 1024 51 52 static int pool_mem[NUM_BUFS * BUF_SIZE / sizeof(int)]; 53 static uffs_Pool pool; 54 55 uffs_PoolInit(&pool, pool_mem, sizeof(pool_mem), BUF_SIZE, NUM_BUFS); 56 57 void * p; 58 p = uffs_PoolGet(&pool); 59 ... 60 uffs_PoolPut(p, &pool); 61 62 notice: 63 64 uffs_PoolInit will assert when NUM_BUFS is not at least 1, or BUF_SIZE is 65 not aligned to the platforms pointer size. 66 67 */ 68 69 70 /** 71 * \brief Initializes the memory pool. 72 * \param[in] pool memory pool 73 * \param[in] mem pool memory 74 * \param[in] mem_size size of pool memory 75 * \param[in] buf_size size of a single buffer 76 * \param[in] num_bufs number of buffers 77 * \return Returns U_SUCC if successful. 78 */ 79 URET uffs_PoolInit(uffs_Pool *pool, 80 void *mem, u32 mem_size, u32 buf_size, u32 num_bufs) 81 { 82 unsigned int i; 83 uffs_PoolEntry *e1, *e2; 84 85 if (!uffs_Assert(pool != NULL, "pool missing") || 86 !uffs_Assert(mem != NULL, "pool memory missing") || 87 !uffs_Assert(num_bufs > 0, "not enough buffers") || 88 !uffs_Assert(buf_size % sizeof(void *) == 0, 89 "buffer size not aligned to pointer size") || 90 !uffs_Assert(mem_size == num_bufs * buf_size, 91 "pool memory size is wrong")) 92 { 93 return U_FAIL; 94 } 95 96 pool->mem = (u8 *)mem; 97 pool->buf_size = buf_size; 98 pool->num_bufs = num_bufs; 99 100 uffs_SemCreate(&pool->sem); 101 uffs_SemWait(pool->sem); 102 103 // Initialize the free_list 104 e1 = e2 = pool->free_list = (uffs_PoolEntry *) pool->mem; 105 for (i = 1; i < pool->num_bufs; i++) { 106 e2 = (uffs_PoolEntry *) (pool->mem + i * pool->buf_size); 107 e1->next = e2; 108 e1 = e2; 109 } 110 e2->next = NULL; 111 112 uffs_SemSignal(pool->sem); 113 114 return U_SUCC; 115 } 116 117 /** 118 * \brief verify pointer validity aganist memory pool 119 * \return U_TRUE if valid, U_FALSE if invalid. 120 */ 121 UBOOL uffs_PoolVerify(uffs_Pool *pool, void *p) 122 { 123 return p && 124 (u8 *)p >= pool->mem && 125 (u8 *)p < pool->mem + (pool->buf_size * pool->num_bufs) && 126 (((u8 *)p - pool->mem) % pool->buf_size) == 0 ? U_TRUE : U_FALSE; 127 } 128 129 /** 130 * \brief Releases the memory pool. 131 * \param[in] pool memory pool 132 * \return Returns U_SUCC if successful. 133 */ 134 URET uffs_PoolRelease(uffs_Pool *pool) 135 { 136 if (!uffs_Assert(pool != NULL, "pool missing")) 137 return U_FAIL; 138 139 uffs_SemDelete(&pool->sem); 140 141 return U_SUCC; 142 } 143 144 /** 145 * \brief Get a buffer from the memory pool. 146 * \param[in] pool memory pool 147 * \return Returns a pointer to the buffer or NULL if none is available. 148 */ 149 void *uffs_PoolGet(uffs_Pool *pool) 150 { 151 uffs_PoolEntry *e; 152 153 if (!uffs_Assert(pool != NULL, "pool missing")) 154 return NULL; 155 156 e = pool->free_list; 157 if (e) 158 pool->free_list = e->next; 159 160 return e; 161 } 162 163 /** 164 * \brief Get a buffer from the memory pool. 165 * This version is locked and should be used when multiple threads access the 166 * same memory pool. 167 * \param[in] pool memory pool 168 * \return Returns a pointer to the buffer or NULL if none is available. 169 */ 170 void *uffs_PoolGetLocked(uffs_Pool *pool) 171 { 172 uffs_PoolEntry *e; 173 174 if (!uffs_Assert(pool != NULL, "pool missing")) 175 return NULL; 176 177 uffs_SemWait(pool->sem); 178 e = pool->free_list; 179 if (e) 180 pool->free_list = e->next; 181 uffs_SemSignal(pool->sem); 182 183 return e; 184 } 185 186 /** 187 * \brief Puts a buffer back to the memory pool. 188 * \param[in] pool memory pool 189 * \param[in] p buffer to put back 190 * \return Returns 0 if successful. 191 */ 192 int uffs_PoolPut(uffs_Pool *pool, void *p) 193 { 194 uffs_PoolEntry *e = (uffs_PoolEntry *)p; 195 196 if (!uffs_Assert(pool != NULL, "pool missing")) 197 return -1; 198 199 if (e) { 200 e->next = pool->free_list; 201 pool->free_list = e; 202 return 0; 203 } 204 205 return -1; 206 } 207 208 /** 209 * \brief Puts a buffer back to the memory pool. 210 * This version is locked and should be used when multiple threads access the 211 * same memory pool. 212 * \param[in] pool memory pool 213 * \param[in] p buffer to put back 214 * \return Returns 0 if successful. 215 */ 216 int uffs_PoolPutLocked(uffs_Pool *pool, void *p) 217 { 218 uffs_PoolEntry *e = (uffs_PoolEntry *)p; 219 220 if (!uffs_Assert(pool != NULL, "pool missing")) 221 return -1; 222 223 if (e) { 224 uffs_SemWait(pool->sem); 225 e->next = pool->free_list; 226 pool->free_list = e; 227 uffs_SemSignal(pool->sem); 228 return 0; 229 } 230 231 return -1; 232 } 233 234 /** 235 * \brief Gets a buffer by index (offset). 236 * This method returns a buffer from the memory pool by index. 237 * \param[in] pool memory pool 238 * \param[in] index index 239 * \return Returns a pointer to the buffer. 240 */ 241 void *uffs_PoolGetBufByIndex(uffs_Pool *pool, u32 index) 242 { 243 if (!uffs_Assert(pool != NULL, "pool missing") || 244 !uffs_Assert(index < pool->num_bufs, 245 "index(%d) out of range(max %d)", index, pool->num_bufs)) 246 { 247 return NULL; 248 } 249 250 return (u8 *) pool->mem + index * pool->buf_size; 251 } 252 253 /** 254 * \brief Gets the index (offset) of a buffer. 255 * This method returns the index of a buffer from the memory pool. 256 * \param[in] pool memory pool 257 * \param[in] p buffer to get index from 258 * \return Returns the index of the buffer. 259 */ 260 u32 uffs_PoolGetIndex(uffs_Pool *pool, void *p) 261 { 262 if (!uffs_Assert(pool != NULL, "pool missing") || 263 !uffs_Assert(p >= (void *) pool->mem && 264 p < (void *) (pool->mem + pool->num_bufs * pool->buf_size), 265 "pointer out of range")) 266 { 267 uffs_Panic(); 268 } 269 270 return ((u8 *) p - pool->mem) / pool->buf_size; 271 } 272 273 /** 274 * \brief Check given buffer in free list 275 * \return U_TRUE if it's in free list, U_FALSE if not. 276 */ 277 UBOOL uffs_PoolCheckFreeList(uffs_Pool *pool, void *p) 278 { 279 uffs_PoolEntry *e; 280 for (e = pool->free_list; e; e = e->next) { 281 if ((void *)e == p) 282 return U_TRUE; 283 } 284 return U_FALSE; 285 } 286 287 /** 288 * \brief this is more efficient version for small nodes number memory pool (< 32) 289 */ 290 static void * FindNextAllocatedInSmallPool(uffs_Pool *pool, void *from) 291 { 292 u32 map = 0; 293 uffs_PoolEntry *e; 294 u32 i; 295 296 for (e = pool->free_list; e; e = e->next) 297 map |= (1 << uffs_PoolGetIndex(pool, e)); 298 299 for (i = uffs_PoolGetIndex(pool, from); 300 (map & (1 << i)) && i < 32 && i < pool->num_bufs; 301 i++); 302 303 return i < 32 && i < pool->num_bufs ? 304 uffs_PoolGetBufByIndex(pool, i) : NULL; 305 } 306 307 308 /** 309 * \brief Find next allocated memory block 310 * 311 * \param[in] pool memory pool 312 * \param[in] from search start address, if NULL, from pool->mem 313 * 314 * \return next allocated memory block, NULL if not found. 315 * 316 * \note This is NOT efficient, don't do it on a pool with large free nodes ! 317 */ 318 void * uffs_PoolFindNextAllocated(uffs_Pool *pool, void *from) 319 { 320 uffs_PoolEntry *e = NULL; 321 u8 *p = (u8 *)from; 322 323 if (p == NULL) 324 p = pool->mem; 325 else 326 p += pool->buf_size; 327 328 if (pool->num_bufs < 32) 329 return FindNextAllocatedInSmallPool(pool, p); 330 331 // work through the free list, stop if not in free list, 332 // otherwise move to next entry and search free list again. 333 334 if (pool->free_list) { 335 while (uffs_PoolVerify(pool, p)) { 336 e = pool->free_list; 337 while (e) { 338 if (p == (u8 *)e) { 339 p += pool->buf_size; // in free list, move to next entry 340 break; 341 } 342 e = e->next; 343 } 344 if (e == NULL) // not in free_list, gotcha 345 break; 346 } 347 } 348 349 return uffs_PoolVerify(pool, p) ? p : NULL ; 350 } 351 352 /** 353 * \brief get free memory block count 354 */ 355 int uffs_PoolGetFreeCount(uffs_Pool *pool) 356 { 357 int count = 0; 358 uffs_PoolEntry *e; 359 360 e = pool->free_list; 361 while (e) { 362 count++; 363 e = e->next; 364 } 365 366 return count; 367 } 368 369 /** 370 * \brief put all memory block back, return how many memory blocks were put back 371 */ 372 int uffs_PoolPutAll(uffs_Pool *pool) 373 { 374 void *p = NULL; 375 int count = 0; 376 377 do { 378 p = uffs_PoolFindNextAllocated(pool, p); 379 if (p) { 380 uffs_PoolPut(pool, p); 381 count++; 382 } 383 } while (p); 384 385 return count; 386 } 387