close Warning: Can't use blame annotator: 
No changeset 2 in the repository

source: svn/newcon3bcm2_21bu/BSEAV/lib/utils/bpool.c @ 46

Last change on this file since 46 was 46, checked in by megakiss, 11 years ago

459Mhz로 OTC 주파수 변경
  • Property svn:executable set to *
File size: 8.6 KB
RevLine 
1/***************************************************************************
2 *     Copyright (c) 2007-2008, Broadcom Corporation
3 *     All Rights Reserved
4 *     Confidential Property of Broadcom Corporation
5 *
6 *  THIS SOFTWARE MAY ONLY BE USED SUBJECT TO AN EXECUTED SOFTWARE LICENSE
7 *  AGREEMENT  BETWEEN THE USER AND BROADCOM.  YOU HAVE NO RIGHT TO USE OR
8 *  EXPLOIT THIS MATERIAL EXCEPT SUBJECT TO THE TERMS OF SUCH AN AGREEMENT.
9 *
10 * $brcm_Workfile: bpool.c $
11 * $brcm_Revision: 6 $
12 * $brcm_Date: 6/12/08 3:07p $
13 *
14 * Module Description:
15 *
16 * Pool alloc library
17 *
18 * Revision History:
19 *
20 * $brcm_Log: /BSEAV/lib/utils/bpool.c $
21 *
22 * 6   6/12/08 3:07p vsilyaev
23 * PR 43607: Renamed alloc and free to bmem_alloc and bmem_free
24 *
25 * 5   4/17/07 2:01p vsilyaev
26 * PR 29921: Demoted debug message
27 *
28 * 4   3/27/07 7:24p vsilyaev
29 * PR 29125: Relaxed test to pool alloc
30 *
31 * 3   2/15/07 3:12p vsilyaev
32 * PR 25701: Added code to handle parsing during resource starvation
33 *
34 * 2   2/14/07 5:45p vsilyaev
35 * PR 25701: Added code to dump content/status of allocator
36 *
37 * 1   2/5/07 5:29p vsilyaev
38 * PR 25701:Portions of stackable parsing framework
39 *
40 *
41 *******************************************************************************/
42#include "bstd.h"
43#include "bkni.h"
44#include "bpool.h"
45#include "blst_selist.h"
46
47BDBG_MODULE(bpool);
48
49#define BDBG_MSG_TRACE(x)  /* BDBG_MSG(x) */
50
51BDBG_OBJECT_ID(bpool_t);
52
53struct bpool {
54        struct balloc_iface alloc_iface; /* must be a first member */
55        uint16_t last_free;
56        uint16_t nfree_elem;
57        uint16_t elem_size;
58        uint16_t nelem;
59        uint32_t *bitmap; /* pointer to bitmap */
60        BLST_SE_ENTRY(bpool);
61        balloc_iface_t alloc;
62        BDBG_OBJECT(bpool_t)
63        /*
64         allocated objects start here
65        */
66        /*
67         object bitmap start here, and bitmap points here as well
68        */
69};
70#define B_POOL_BITS_IN_MAP      32
71
72static unsigned 
73b_pool_first_zero(uint32_t word)
74{
75        unsigned i;
76        for(i=0;i<B_POOL_BITS_IN_MAP;i++) {
77                if (!(word&(1<<i))) {
78                        return i;
79                }
80        }
81        BDBG_ASSERT(0);
82        return 0;
83}
84
85void *
86bpool_alloc(bpool_t pool, size_t size)
87{
88        uint16_t i;
89        BSTD_UNUSED(size);
90
91        BDBG_OBJECT_ASSERT(pool, bpool_t);
92        BDBG_ASSERT(size<=pool->elem_size);
93
94        do {
95                for(;pool->nfree_elem>0;) {
96                        for(i=pool->last_free;i<(pool->nelem/B_POOL_BITS_IN_MAP);i++) {
97                                if(pool->bitmap[i]!=(~0u)) {
98                                        unsigned bit;
99
100                                        pool->last_free = i;
101                                        bit = b_pool_first_zero(pool->bitmap[i]);
102                                        pool->bitmap[i] |= (1<<bit);
103                                        BDBG_ASSERT(pool->nfree_elem>0);
104                                        pool->nfree_elem--;
105                                        BDBG_MSG_TRACE(("bpool_alloc: %#lx %#lx offset %u [%x:%u]", (unsigned long)pool, (unsigned long)((uint8_t *)pool + sizeof(*pool) + pool->elem_size*(i*B_POOL_BITS_IN_MAP + bit)), i, (unsigned)pool->bitmap[i], bit));
106                                        return (void *)((uint8_t *)pool + sizeof(*pool) + pool->elem_size*(i*B_POOL_BITS_IN_MAP + bit));
107                                }
108                        }
109                        if(pool->last_free==0) {
110                                break; /* there is no empty space left */
111                        }
112                        pool->last_free=0; /* rescan entire bitmap */
113                }
114                BDBG_MSG(("bpool_alloc:%#lx exhausted", (unsigned long)pool));
115        } while(NULL!=(pool=BLST_SE_NEXT(pool)));
116        return NULL;
117}
118
119static bool
120b_pool_test_one(bpool_t pool, void *ptr)
121{
122        if ((uint8_t *)ptr >= (uint8_t *)pool + sizeof(*pool) && (uint8_t *)ptr <= (uint8_t *)pool->bitmap - pool->elem_size) {
123                return true;
124        } else {
125                return false;
126        }
127}
128
129bool
130bpool_test_block(bpool_t pool, void *ptr)
131{
132        BDBG_OBJECT_ASSERT(pool, bpool_t);
133        do {
134                BDBG_OBJECT_ASSERT(pool, bpool_t);
135                if(b_pool_test_one(pool, ptr)) {
136                        return true;
137                }
138        } while(NULL!=(pool=BLST_SE_NEXT(pool)));
139        return false;
140}
141
142void
143bpool_join(bpool_t parent, bpool_t child)
144{
145        BDBG_OBJECT_ASSERT(parent, bpool_t);
146        BDBG_OBJECT_ASSERT(child, bpool_t);
147        BDBG_ASSERT(parent->elem_size == child->elem_size);
148        BDBG_ASSERT(parent != child);
149
150        BLST_SE_INSERT_AFTER(parent, child);
151        return;
152}
153
154bool
155bpool_is_empty(bpool_t pool)
156{
157        BDBG_OBJECT_ASSERT(pool, bpool_t);
158        /* this function doesn't query child pools */
159        return pool->nfree_elem == pool->nelem;
160}
161
162bpool_t
163bpool_last_child(bpool_t pool)
164{
165        BDBG_OBJECT_ASSERT(pool, bpool_t);
166        /* adjust to the child right the way */
167        while(NULL!=(pool=BLST_SE_NEXT(pool))) {
168                if (BLST_SE_NEXT(pool)==NULL) {
169                        return pool;
170                }
171        }
172        return NULL;
173}
174
175void 
176bpool_detach(bpool_t parent, bpool_t child)
177{
178        bpool_t pool;
179
180        BDBG_OBJECT_ASSERT(parent, bpool_t);
181        BDBG_OBJECT_ASSERT(child, bpool_t);
182        BDBG_ASSERT(parent->elem_size == child->elem_size);
183        BDBG_ASSERT(parent != child);
184        BDBG_ASSERT(bpool_is_empty(child)); /* can't delete busy child */
185
186        pool = parent;
187        do {
188                if(child==BLST_SE_NEXT(pool)) {
189                        BLST_SE_REMOVE_BEFORE(pool, child);
190                        return;
191                }
192        } while(NULL!=(pool=BLST_SE_NEXT(pool)));
193        BDBG_ASSERT(0); /* child doesn't belong to a parent */
194        return;
195}
196
197void 
198bpool_free(bpool_t pool, void *ptr)
199{
200        unsigned offset;
201        unsigned bit;
202
203        BDBG_OBJECT_ASSERT(pool, bpool_t);
204        BDBG_ASSERT(ptr);
205        BDBG_ASSERT(bpool_test_block(pool, ptr));
206        do {
207                if (!b_pool_test_one(pool,ptr)) {
208                        continue; /* try next pool */
209                }
210                offset = (uint8_t *)ptr - ((uint8_t *)pool + sizeof(*pool));
211                BDBG_ASSERT((offset % pool->elem_size) == 0);
212                offset = offset/pool->elem_size;
213                bit = offset % B_POOL_BITS_IN_MAP;
214                offset = offset/B_POOL_BITS_IN_MAP;
215                BDBG_MSG_TRACE(("bpool_free: %#lx %#lx offset %u [%#x:%u]", (unsigned long)pool, (unsigned long)ptr, offset, (unsigned)pool->bitmap[offset], bit));
216                BDBG_ASSERT(pool->bitmap[offset] & (1<<bit)); /* block shall have been allocated */
217                pool->bitmap[offset] &= ~((1<<bit)); /* clear alloc bit */
218                BDBG_ASSERT(pool->nfree_elem<pool->nelem);
219                pool->nfree_elem++;
220                return;
221        } while(NULL!=(pool=BLST_SE_NEXT(pool)));
222        BDBG_ASSERT(0); /* block wasn't allocated */
223        return;
224}
225
226static void *
227b_pool_alloc(balloc_iface_t alloc, size_t size)
228{
229        return bpool_alloc((bpool_t)alloc, size);
230}
231
232static void
233b_pool_free(balloc_iface_t alloc, void *ptr)
234{
235        bpool_free((bpool_t)alloc, ptr);
236}
237
238bpool_t
239bpool_create(balloc_iface_t alloc, size_t nelem, size_t elem_size)
240{
241        bpool_t pool;
242        size_t map_size;
243
244        BDBG_ASSERT(nelem);
245        BDBG_ASSERT(elem_size);
246        BDBG_ASSERT(alloc);
247        BDBG_ASSERT(nelem<65536);
248        BDBG_ASSERT(elem_size<65536);
249
250        BDBG_CASSERT(sizeof(uint32_t)==(B_POOL_BITS_IN_MAP/8));
251        nelem = (nelem+(B_POOL_BITS_IN_MAP-1))&(~(B_POOL_BITS_IN_MAP-1));
252        map_size = nelem/B_POOL_BITS_IN_MAP;
253
254        pool = alloc->bmem_alloc(alloc, nelem*elem_size + sizeof(*pool) + map_size*sizeof(uint32_t));
255        BDBG_MSG(("bpool_create: %#lx overhead %u allocated %u (bytes)", (unsigned long)pool, sizeof(*pool), nelem*elem_size + sizeof(*pool) + map_size*sizeof(uint32_t)));
256        if (!pool) {
257                BDBG_ERR(("alloc failed (%u bytes)", nelem*elem_size + sizeof(*pool) + map_size*sizeof(uint32_t)));
258                return NULL;
259        }
260        BDBG_OBJECT_INIT(pool, bpool_t);
261        pool->alloc_iface.bmem_alloc = b_pool_alloc;
262        pool->alloc_iface.bmem_free = b_pool_free;
263        pool->alloc = alloc;
264        BLST_SE_INIT(pool);
265        pool->bitmap = (uint32_t *)((uint8_t *)pool + sizeof(*pool) + nelem*elem_size);
266        pool->nelem = nelem;
267        pool->elem_size = elem_size;
268        pool->last_free = 0;
269        pool->nfree_elem = nelem;
270        BKNI_Memset(pool->bitmap, 0, map_size*sizeof(uint32_t)); /* mark all as free */
271        return pool;
272}
273
274void
275bpool_destroy(bpool_t pool)
276{
277        balloc_iface_t alloc;
278        bpool_t next;
279
280        BDBG_MSG_TRACE(("bpool_destroy: >%#lx", pool));
281        BDBG_OBJECT_ASSERT(pool, bpool_t);
282        do {
283                BDBG_MSG_TRACE(("bpool_destroy: +%#lx", pool));
284                BDBG_OBJECT_ASSERT(pool, bpool_t);
285                alloc = pool->alloc;
286                next = BLST_SE_NEXT(pool);
287                BDBG_OBJECT_DESTROY(pool, bpool_t);
288                alloc->bmem_free(alloc, pool);
289                BDBG_MSG_TRACE(("bpool_destroy: -%#lx", pool));
290                pool=next;
291        } while(pool);
292        BDBG_MSG_TRACE(("bpool_destroy: <%#lx", pool));
293        return;
294}
295
296
297balloc_iface_t
298bpool_alloc_iface(bpool_t pool)
299{
300        BDBG_OBJECT_ASSERT(pool, bpool_t);
301        return &pool->alloc_iface;
302}
303
304void
305bpool_get_status(bpool_t pool, bpool_status *status)
306{
307        BDBG_OBJECT_ASSERT(pool, bpool_t);
308        BDBG_ASSERT(status);
309
310        status->pools = 0;
311        status->free = 0;
312        status->allocated = 0;
313        for(;pool;pool=BLST_SE_NEXT(pool)) {
314                BDBG_OBJECT_ASSERT(pool, bpool_t);
315                status->pools ++;
316                status->free += pool->nfree_elem;
317                status->allocated += pool->nelem - pool->nfree_elem;
318        }
319}
320
321void
322bpool_dump(bpool_t pool)
323{
324        uint16_t i,bit;
325        BDBG_OBJECT_ASSERT(pool, bpool_t);
326
327        for(;pool;pool=BLST_SE_NEXT(pool)) {
328                BDBG_WRN(("bpool_dump: pool %#lx free:%u allocated:%u", (unsigned long)pool, pool->nfree_elem, pool->nelem-pool->nfree_elem));
329                for(i=0;i<(pool->nelem/B_POOL_BITS_IN_MAP);i++) {
330                        if(pool->bitmap[i]) {
331                                for(bit=0;bit<B_POOL_BITS_IN_MAP;bit++) {
332                                        if(pool->bitmap[i]&(1<<bit)) {
333                                                BDBG_WRN(("bpool_dump: %#lx %#lx offset %u [%#x:%u]", (unsigned long)pool, (unsigned long)((uint8_t *)pool + sizeof(*pool) + pool->elem_size*(i*B_POOL_BITS_IN_MAP + bit)), i, (unsigned)pool->bitmap[i], bit));
334                                        }
335                                }
336                        }
337                }
338        }
339}
340
Note: See TracBrowser for help on using the repository browser.