source: svn/newcon3bcm2_21bu/BSEAV/lib/utils/barena.c

Last change on this file was 76, checked in by megakiss, 10 years ago

1W 대기전력을 만족시키기 위하여 POWEROFF시 튜너를 Standby 상태로 함
  • Property svn:executable set to *
File size: 10.0 KB
Line 
1/***************************************************************************
2 *     copyright (c) 2007, 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: bdemux_pes.c $
11 * $brcm_revision: 1 $
12 * $brcm_date: 10/16/06 11:35a $
13 *
14 * module description:
15 *
16 * Arena alloc library
17 *
18 * revision history:
19 *
20 * $brcm_log: /bseav/lib/utils/bdemux_pes.c $
21 *
22 *
23 *******************************************************************************/
24#include "bstd.h"
25#include "barena.h"
26#include "blst_selist.h"
27#include "blst_queue.h"
28BDBG_MODULE(barena);
29
30#define BDBG_MSG_TRACE(x) /* BDBG_MSG(x)  */
31
32BDBG_OBJECT_ID(barena_t);
33
34typedef struct b_arena_block {
35        BLST_Q_ENTRY(b_arena_block) link;
36        uint16_t size; /* size in  sizeof(unsigned) units of entire block (include headers)  */
37        uint16_t tag; /* this is offset in to the arean, only used to verify validity of block */
38        /* user data located here */
39} b_arena_block;
40
41struct barena {
42        struct balloc_iface alloc_iface; /* must be a first member */
43        BLST_SE_ENTRY(barena);
44        unsigned free_head; /* number of free bytes in the head of arena */
45        unsigned free_tail; /* number of free bytes in the tail of arena */
46    BLST_Q_HEAD(b_arena_head, b_arena_block) blocks;
47        unsigned size; /* size of arena, without header */
48        balloc_iface_t alloc;
49        BDBG_OBJECT(barena_t)
50        /*
51          memory pool located here
52        */
53};
54
55#define B_ARENA_MAX_ALLOC       ((0xFFFF)*sizeof(unsigned))
56#define B_ARENA_ROUND(size) (((size)+(sizeof(unsigned)-1))&~(sizeof(unsigned)-1))
57
58#define B_BLOCK_TAG(arena, block) ((uint16_t)((uint8_t *)(block) - (uint8_t *)(arena))/sizeof(unsigned))
59
60void *
61barena_alloc(barena_t arena, size_t size)
62{
63        BDBG_MSG_TRACE(("barena_alloc: >%#lx %u", (unsigned long)arena, (unsigned)size));
64        BDBG_OBJECT_ASSERT(arena, barena_t);
65        size = B_ARENA_ROUND(size);
66        BDBG_CASSERT(B_ARENA_MAX_ALLOC>sizeof(b_arena_block));
67        if (size >= B_ARENA_MAX_ALLOC-sizeof(b_arena_block)) { 
68                goto err_size;
69        }
70        size += sizeof(b_arena_block);
71        BDBG_MSG_TRACE(("barena_alloc: %#lx head %u tail %u", (unsigned long)arena, arena->free_head, arena->free_tail));
72        do {
73                b_arena_block *block;
74                BDBG_OBJECT_ASSERT(arena, barena_t);
75                if (arena->free_head >= size) {
76                        /* allocate entry from the head */
77                        block = (b_arena_block*)((uint8_t *)arena+sizeof(*arena)+ (arena->free_head - size));
78                        BDBG_MSG_TRACE(("barena_alloc: %#lx head block %#lx", (unsigned long)arena, (unsigned long)block));
79                        arena->free_head -= size;
80                        BLST_Q_INSERT_HEAD(&arena->blocks, block, link); /* this would keep blocks sorted by their address */
81                        block->size = size/sizeof(unsigned);
82                        block->tag = B_BLOCK_TAG(arena, block);
83                } else if (arena->free_tail >= size) {
84                        block = (b_arena_block*)((uint8_t *)arena+sizeof(*arena)+ (arena->size - arena->free_tail));
85                        BDBG_MSG_TRACE(("barena_alloc: %#lx tail block %#lx", (unsigned long)arena, (unsigned long)block));
86                        arena->free_tail -= size;
87                        BLST_Q_INSERT_TAIL(&arena->blocks, block, link); /* this would keep blocks sorted by their address */
88                        block->size = size/sizeof(unsigned);
89                        block->tag = ((uint8_t *)block - (uint8_t *)arena)/sizeof(unsigned);
90                } else {
91                        continue;
92                }
93                BDBG_MSG_TRACE(("barena_alloc: <%#lx %#lx", (unsigned long)arena, (unsigned long)block+sizeof(*block)));
94                return (uint8_t *)block+sizeof(*block);
95        } while(NULL!=(arena=BLST_SE_NEXT(arena)));
96
97        return NULL;
98err_size:
99        BDBG_WRN(("barena_alloc: requested size %u exceeds limit %u", size, B_ARENA_MAX_ALLOC - sizeof(b_arena_block)));
100        /* too large block */
101        return NULL;
102}
103
104static bool
105b_arena_test_one(barena_t arena, void *ptr)
106{
107        if ((uint8_t *)ptr >= (uint8_t *)arena + sizeof(*arena) && (uint8_t *)arena <= (uint8_t *)arena + (sizeof(*arena) - sizeof(b_arena_block)) + arena->size) {
108                return true;
109        } else {
110                return false;
111        }
112}
113
114bool
115barena_test_block(barena_t arena, void *ptr)
116{
117        BDBG_OBJECT_ASSERT(arena, barena_t);
118        do {
119                BDBG_OBJECT_ASSERT(arena, barena_t);
120                if(b_arena_test_one(arena, ptr)) {
121                        return true;
122                }
123        } while(NULL!=(arena=BLST_SE_NEXT(arena)));
124        return false;
125}
126
127void
128barena_free(barena_t arena, void *ptr)
129{
130        unsigned new_size;
131        BDBG_OBJECT_ASSERT(arena, barena_t);
132        BDBG_MSG_TRACE(("barena_free: >%#lx %#lx", (unsigned long)arena, (unsigned long)ptr));
133        BDBG_ASSERT(barena_test_block(arena, ptr));
134        do {
135                b_arena_block *block;
136                b_arena_block *next_block;
137                unsigned arena_size; 
138                if(!b_arena_test_one(arena, ptr)) {
139                        continue; /* try next arena */
140                }
141                block = (b_arena_block *)(((uint8_t *)ptr) - sizeof(*block));
142                /* test if block belongs to us */
143                BDBG_ASSERT(block->tag = B_BLOCK_TAG(arena, block));
144                BDBG_MSG_TRACE(("barena_free: %#lx block %#lx(%u) first:%#lx  last:%#lx prev:%#lx next:%#lx", (unsigned long)arena, (unsigned long)block, block->size, (unsigned long)BLST_Q_FIRST(&arena->blocks), (unsigned long)BLST_Q_LAST(&arena->blocks), (unsigned long)BLST_Q_PREV(block,link), (unsigned long)BLST_Q_NEXT(block,link)));
145                BDBG_ASSERT(BLST_Q_PREV(block,link)==NULL || b_arena_test_one(arena, BLST_Q_PREV(block,link)));
146                BDBG_ASSERT(BLST_Q_PREV(block,link)!=NULL || BLST_Q_FIRST(&arena->blocks)==block);
147                BDBG_ASSERT(BLST_Q_NEXT(block,link)==NULL || b_arena_test_one(arena, BLST_Q_NEXT(block,link)));
148                BDBG_ASSERT(BLST_Q_NEXT(block,link)!=NULL || BLST_Q_LAST(&arena->blocks)==block);
149                block->tag = 0; /* clear tag */
150                arena_size = arena->size;
151                if(block==BLST_Q_LAST(&arena->blocks)) {
152                        next_block = BLST_Q_PREV(block, link);
153                        if(next_block) {
154                                new_size = ((uint8_t *)arena + arena_size + sizeof(*arena))- ((uint8_t*)next_block + next_block->size*sizeof(unsigned));
155                                BDBG_ASSERT(new_size >= arena->free_tail+block->size*sizeof(unsigned));
156                                arena->free_tail = new_size;
157                        } else {
158                                arena->free_head = 0;
159                                arena->free_tail = arena_size;
160                        }
161                } else if(block==BLST_Q_FIRST(&arena->blocks)) {
162                        next_block = BLST_Q_NEXT(block, link);
163                        if(next_block) {
164                                new_size = ((uint8_t*)next_block) - ((uint8_t *)arena + sizeof(*arena)); 
165                                BDBG_ASSERT(new_size >= arena->free_head+block->size*sizeof(unsigned));
166                                arena->free_head = new_size;
167                        } else {
168                                arena->free_head = 0;
169                                arena->free_tail = arena_size;
170                        }
171                }
172                BDBG_ASSERT(arena->free_head + arena->free_tail <= arena->size);
173#if 0
174                if (arena->free_head+arena->free_tail == arena->size) {
175                        arena->free_head = 0;
176                        arena->free_tail = arena->size;
177                }
178#endif
179                BLST_Q_REMOVE(&arena->blocks, block, link);
180                BDBG_MSG_TRACE(("barena_free: %#lx head %u tail %u", (unsigned long)arena, arena->free_head, arena->free_tail));
181                BDBG_MSG_TRACE(("barena_free: <%#lx", (unsigned long)arena));
182                return;
183        } while(NULL!=(arena=BLST_SE_NEXT(arena)));
184        BDBG_MSG_TRACE(("barena_free: <%#lx %#lx", (unsigned long)arena, (unsigned long)ptr));
185        BDBG_ASSERT(0);
186        return;
187}
188
189static void *
190b_arena_alloc(balloc_iface_t alloc, size_t size)
191{
192        return barena_alloc((barena_t)alloc, size);
193}
194
195static void
196b_arena_free(balloc_iface_t alloc, void *ptr)
197{
198        barena_free((barena_t)alloc, ptr);
199}
200
201barena_t
202barena_create(balloc_iface_t alloc, size_t arena_size)
203{
204        barena_t arena;
205        BDBG_ASSERT(alloc);
206
207        arena_size = B_ARENA_ROUND(arena_size);
208        arena = alloc->bmem_alloc(alloc, sizeof(*arena)+arena_size);
209        BDBG_MSG(("barena_create: %#lx overhead %u allocated %u (bytes)", (unsigned long)arena, sizeof(b_arena_block), arena_size + sizeof(*arena)));
210        if (!arena) {
211                BDBG_ERR(("alloc failed (%u bytes)", arena_size + sizeof(*arena)));
212                return NULL;
213        }
214        BDBG_OBJECT_INIT(arena, barena_t);
215        arena->alloc = alloc;
216        BLST_SE_INIT(arena);
217        arena->free_head = 0;
218        arena->free_tail = arena_size;
219        arena->size = arena_size;
220        BLST_Q_INIT(&arena->blocks);
221        arena->alloc_iface.bmem_alloc = b_arena_alloc;
222        arena->alloc_iface.bmem_free = b_arena_free;
223        return arena;
224}
225
226void
227barena_destroy(barena_t arena)
228{
229        balloc_iface_t alloc;
230        barena_t next;
231        BDBG_MSG_TRACE(("barena_destroy: >%#lx", arena));
232
233        BDBG_OBJECT_ASSERT(arena, barena_t);
234        do {
235                BDBG_OBJECT_ASSERT(arena, barena_t);
236                alloc = arena->alloc;
237                next = BLST_SE_NEXT(arena);
238                BDBG_OBJECT_DESTROY(arena, barena_t);
239                BDBG_MSG_TRACE(("barena_destroy: %#lx", arena));
240                alloc->bmem_free(alloc, arena);
241                arena = next;
242        } while(arena);
243        BDBG_MSG_TRACE(("barena_destroy: <%#lx", arena));
244        return;
245}
246
247balloc_iface_t
248barena_alloc_iface(barena_t arena)
249{
250        BDBG_OBJECT_ASSERT(arena, barena_t);
251        return &arena->alloc_iface;
252}
253
254void
255barena_join(barena_t parent, barena_t child)
256{
257        BDBG_OBJECT_ASSERT(parent, barena_t);
258        BDBG_OBJECT_ASSERT(child, barena_t);
259        BDBG_ASSERT(parent != child);
260
261        BLST_SE_INSERT_AFTER(parent, child);
262        return;
263}
264
265bool
266barena_is_empty(barena_t arena)
267{
268        BDBG_OBJECT_ASSERT(arena, barena_t);
269        /* this function doesn't query child pools */
270        return BLST_Q_FIRST(&arena->blocks)==NULL;
271}
272
273barena_t
274barena_last_child(barena_t arena)
275{
276        BDBG_OBJECT_ASSERT(arena, barena_t);
277        /* adjust to the child right the way */
278        while(NULL!=(arena=BLST_SE_NEXT(arena))) {
279                if (BLST_SE_NEXT(arena)==NULL) {
280                        return arena;
281                }
282        }
283        return NULL;
284}
285
286void 
287barena_detach(barena_t parent, barena_t child)
288{
289        barena_t arena;
290
291        BDBG_OBJECT_ASSERT(parent, barena_t);
292        BDBG_OBJECT_ASSERT(child, barena_t);
293        BDBG_ASSERT(parent != child);
294        BDBG_ASSERT(barena_is_empty(child)); /* can't delete busy child */
295
296        arena = parent;
297        do {
298                if(child==BLST_SE_NEXT(arena)) {
299                        BLST_SE_REMOVE_BEFORE(arena, child);
300                        return;
301                }
302        } while(NULL!=(arena=BLST_SE_NEXT(arena)));
303        BDBG_ASSERT(0); /* child doesn't belong to a parent */
304        return;
305}
306
307void 
308barena_dump(barena_t arena)
309{
310        b_arena_block *block;
311        size_t total;
312        BDBG_OBJECT_ASSERT(arena, barena_t);
313        for(total=0,block=BLST_Q_FIRST(&arena->blocks);block;block=BLST_Q_NEXT(block,link)) {
314                total += sizeof(unsigned)*(unsigned)block->size;
315                BDBG_WRN(("barena_dump: %#lx %#lx:%u", (unsigned long)arena, (unsigned long)block, sizeof(unsigned)*(unsigned)block->size));
316        }
317        BDBG_WRN(("barena_dump: %#lx size:%u head:%u tail:%u overhead:%u", (unsigned long)arena, arena->size, arena->free_head, arena->free_tail, arena->size-total));
318        return;
319}
Note: See TracBrowser for help on using the repository browser.