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 */
uffs_PoolInit(uffs_Pool * pool,void * mem,u32 mem_size,u32 buf_size,u32 num_bufs)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 */
uffs_PoolVerify(uffs_Pool * pool,void * p)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 */
uffs_PoolRelease(uffs_Pool * pool)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 */
uffs_PoolGet(uffs_Pool * pool)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 */
uffs_PoolGetLocked(uffs_Pool * pool)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 */
uffs_PoolPut(uffs_Pool * pool,void * p)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 */
uffs_PoolPutLocked(uffs_Pool * pool,void * p)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 */
uffs_PoolGetBufByIndex(uffs_Pool * pool,u32 index)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 */
uffs_PoolGetIndex(uffs_Pool * pool,void * p)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 */
uffs_PoolCheckFreeList(uffs_Pool * pool,void * p)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 */
FindNextAllocatedInSmallPool(uffs_Pool * pool,void * from)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 */
uffs_PoolFindNextAllocated(uffs_Pool * pool,void * from)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 */
uffs_PoolGetFreeCount(uffs_Pool * pool)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 */
uffs_PoolPutAll(uffs_Pool * pool)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