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