diff options
author | Peter D'Hoye <peter.dhoye@gmail.com> | 2009-07-23 21:37:35 +0000 |
---|---|---|
committer | Peter D'Hoye <peter.dhoye@gmail.com> | 2009-07-23 21:37:35 +0000 |
commit | 840cd1069292e3f29d18e57f2274ec1e979f858b (patch) | |
tree | 0ee1d43fa3863de53c99432dc32001e625703d1c /apps/plugins/pdbox/dbestfit-3.3/bmalloc.c | |
parent | 0d9b7ec73e71188632a4fd584dfd745aeb7571b3 (diff) | |
download | rockbox-840cd1069292e3f29d18e57f2274ec1e979f858b.tar.gz rockbox-840cd1069292e3f29d18e57f2274ec1e979f858b.zip |
Another pdbox patch by Wincent Balin (FS #10416): switch to using TLSF as memory allocator. Probably the last patch I commit for him, next changes are for him :)
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@22017 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'apps/plugins/pdbox/dbestfit-3.3/bmalloc.c')
-rw-r--r-- | apps/plugins/pdbox/dbestfit-3.3/bmalloc.c | 371 |
1 files changed, 0 insertions, 371 deletions
diff --git a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c b/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c deleted file mode 100644 index f0ac7312a4..0000000000 --- a/apps/plugins/pdbox/dbestfit-3.3/bmalloc.c +++ /dev/null | |||
@@ -1,371 +0,0 @@ | |||
1 | /***************************************************************************** | ||
2 | * | ||
3 | * Big (best-fit) Memory Allocation | ||
4 | * | ||
5 | * Author: Daniel Stenberg | ||
6 | * Date: March 5, 1997 | ||
7 | * Version: 2.0 | ||
8 | * Email: Daniel.Stenberg@sth.frontec.se | ||
9 | * | ||
10 | * | ||
11 | * Read 'thoughts' for theories and details in implementation. | ||
12 | * | ||
13 | * Routines meant to replace the most low level functions of an Operting | ||
14 | * System | ||
15 | * | ||
16 | * v2.0 | ||
17 | * - Made all size-routines get moved out from this file. This way, the size | ||
18 | * functions can much more easily get replaced. | ||
19 | * - Improved how new memory blocks get added to the size-sorted list. When | ||
20 | * not adding new pools, there should never ever be any list traversing | ||
21 | * since all information is dynamically gathered. | ||
22 | * | ||
23 | ****************************************************************************/ | ||
24 | |||
25 | #include <stdio.h> | ||
26 | #include <stdlib.h> | ||
27 | |||
28 | #include "bysize.h" | ||
29 | |||
30 | #ifndef TRUE | ||
31 | #define TRUE 1 | ||
32 | #endif | ||
33 | #ifndef FALSE | ||
34 | #define FALSE 0 | ||
35 | #endif | ||
36 | |||
37 | /* #define DEBUG */ | ||
38 | |||
39 | #define BMEM_ALIGN 64 /* resolution */ | ||
40 | |||
41 | #define BMEMERR_TOOSMALL -1 | ||
42 | |||
43 | /* this struct will be stored in all CHUNKS and AREAS */ | ||
44 | struct BlockInfo { | ||
45 | struct BlockInfo *lower; /* previous block in memory (lower address) */ | ||
46 | struct BlockInfo *higher; /* next block in memory (higher address) */ | ||
47 | unsigned long info; /* 31 bits size: 1 bit free boolean */ | ||
48 | #define INFO_FREE 1 | ||
49 | #define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */ | ||
50 | |||
51 | /* FREE+SIZE Could be written to use ordinary bitfields if using a smart | ||
52 | (like gcc) compiler in a manner like: | ||
53 | int size:31; | ||
54 | int free:1; | ||
55 | |||
56 | The 'higher' pointer COULD be removed completely if the size is used as | ||
57 | an index to the higher one. This would then REQUIRE the entire memory | ||
58 | pool to be contiguous and it needs a 'terminating' "node" or an extra | ||
59 | flag that informs about the end of the list. | ||
60 | */ | ||
61 | }; | ||
62 | |||
63 | /* the BLOCK list should be sorted in a lower to higher address order */ | ||
64 | struct BlockInfo *blockHead=NULL; /* nothing from the start */ | ||
65 | |||
66 | void print_lists(void); | ||
67 | |||
68 | |||
69 | /*********************************************************************** | ||
70 | * | ||
71 | * remove_block() | ||
72 | * | ||
73 | * Remove the block from the address-sorted list. | ||
74 | * | ||
75 | ***********************************************************************/ | ||
76 | |||
77 | void remove_block(struct BlockInfo *block) | ||
78 | { | ||
79 | if(block->lower) | ||
80 | block->lower->higher = block->higher; | ||
81 | else | ||
82 | blockHead = block->higher; | ||
83 | if(block->higher) | ||
84 | block->higher->lower = block->lower; | ||
85 | } | ||
86 | |||
87 | /**************************************************************************** | ||
88 | * | ||
89 | * add_blocktolists() | ||
90 | * | ||
91 | * Adds the specified block at the specified place in the address-sorted | ||
92 | * list and at the appropriate place in the size-sorted. | ||
93 | * | ||
94 | ***************************************************************************/ | ||
95 | void add_blocktolists(struct BlockInfo *block, | ||
96 | struct BlockInfo *newblock, | ||
97 | size_t newsize) | ||
98 | { | ||
99 | struct BlockInfo *temp; /* temporary storage variable */ | ||
100 | if(block) { | ||
101 | /* `block' is now a lower address than 'newblock' */ | ||
102 | |||
103 | /* | ||
104 | * Check if the new CHUNK is wall-to-wall with the lower addressed | ||
105 | * one (if *that* is free) | ||
106 | */ | ||
107 | if(block->info&INFO_FREE) { | ||
108 | if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) { | ||
109 | /* yes sir, this is our lower address neighbour, enlarge that one | ||
110 | pick it out from the list and recursively add that chunk and | ||
111 | then we escape */ | ||
112 | |||
113 | /* remove from size-sorted list: */ | ||
114 | remove_chunksize((char*)block+sizeof(struct BlockInfo)); | ||
115 | |||
116 | block->info += newsize; /* newsize is an even number and thus the FREE | ||
117 | bit is untouched */ | ||
118 | |||
119 | remove_block(block); /* unlink the block address-wise */ | ||
120 | |||
121 | /* recursively check our lower friend(s) */ | ||
122 | add_blocktolists(block->lower, block, block->info&INFO_SIZE); | ||
123 | return; | ||
124 | } | ||
125 | } | ||
126 | |||
127 | temp = block->higher; | ||
128 | |||
129 | block->higher = newblock; | ||
130 | newblock->lower = block; | ||
131 | newblock->higher = temp; | ||
132 | if(newblock->higher) | ||
133 | newblock->higher->lower = newblock; | ||
134 | } | ||
135 | else { | ||
136 | /* this block should preceed the heading one */ | ||
137 | temp = blockHead; | ||
138 | |||
139 | /* check if this is our higher addressed neighbour */ | ||
140 | if((char *)newblock + newsize == (char *)temp) { | ||
141 | |||
142 | /* yes, we are wall-to-wall with the higher CHUNK */ | ||
143 | if(temp->info&INFO_FREE) { | ||
144 | /* and the neighbour is even free, remove that one and enlarge | ||
145 | ourselves, call add_pool() recursively and then escape */ | ||
146 | |||
147 | remove_block(temp); /* unlink 'temp' from list */ | ||
148 | |||
149 | /* remove from size-sorted list: */ | ||
150 | remove_chunksize((char*)temp+sizeof(struct BlockInfo) ); | ||
151 | |||
152 | /* add the upper block's size on ourselves */ | ||
153 | newsize += temp->info&INFO_SIZE; | ||
154 | |||
155 | /* add the new, bigger block */ | ||
156 | add_blocktolists(block, newblock, newsize); | ||
157 | return; | ||
158 | } | ||
159 | } | ||
160 | |||
161 | blockHead = newblock; | ||
162 | newblock->higher = temp; | ||
163 | newblock->lower = NULL; /* there is no lower one */ | ||
164 | if(newblock->higher) | ||
165 | newblock->higher->lower = newblock; | ||
166 | } | ||
167 | |||
168 | newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the | ||
169 | FREE bit */ | ||
170 | insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize); | ||
171 | } | ||
172 | |||
173 | /*********************************************************************** | ||
174 | * | ||
175 | * findblockbyaddr() | ||
176 | * | ||
177 | * Find the block that is just before the input block in memory. Returns NULL | ||
178 | * if none is. | ||
179 | * | ||
180 | ***********************************************************************/ | ||
181 | |||
182 | static struct BlockInfo *findblockbyaddr(struct BlockInfo *block) | ||
183 | { | ||
184 | struct BlockInfo *test = blockHead; | ||
185 | struct BlockInfo *lower = NULL; | ||
186 | |||
187 | while(test && (test < block)) { | ||
188 | lower = test; | ||
189 | test = test->higher; | ||
190 | } | ||
191 | return lower; | ||
192 | } | ||
193 | |||
194 | /*********************************************************************** | ||
195 | * | ||
196 | * add_pool() | ||
197 | * | ||
198 | * This function should be the absolutely first function to call. It sets up | ||
199 | * the memory bounds of the [first] CHUNK(s). It should be possible to call | ||
200 | * this function several times to add more CHUNKs to the pool of free | ||
201 | * memory. This allows the bmalloc system to deal with a non-contigous memory | ||
202 | * area. | ||
203 | * | ||
204 | * Returns non-zero if an error occured. The memory was not added then. | ||
205 | * | ||
206 | ***********************************************************************/ | ||
207 | |||
208 | int add_pool(void *start, | ||
209 | size_t size) | ||
210 | { | ||
211 | struct BlockInfo *newblock = (struct BlockInfo *)start; | ||
212 | struct BlockInfo *block; | ||
213 | |||
214 | if(size < BMEM_ALIGN) | ||
215 | return BMEMERR_TOOSMALL; | ||
216 | |||
217 | block = findblockbyaddr( newblock ); | ||
218 | /* `block' is now a lower address than 'newblock' or NULL */ | ||
219 | |||
220 | if(size&1) | ||
221 | size--; /* only add even sizes */ | ||
222 | |||
223 | add_blocktolists(block, newblock, size); | ||
224 | |||
225 | return 0; | ||
226 | } | ||
227 | |||
228 | |||
229 | #ifdef DEBUG | ||
230 | static void bmalloc_failed(size_t size) | ||
231 | { | ||
232 | printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size); | ||
233 | print_lists(); | ||
234 | } | ||
235 | #else | ||
236 | #define bmalloc_failed(x) | ||
237 | #endif | ||
238 | |||
239 | #ifdef DEBUG | ||
240 | void print_lists() | ||
241 | { | ||
242 | struct BlockInfo *block = blockHead; | ||
243 | #if 1 | ||
244 | printf("List of BLOCKS (in address order):\n"); | ||
245 | while(block) { | ||
246 | printf(" START %p END %p SIZE %ld FLAG %s\n", | ||
247 | (char *)block, | ||
248 | (char *)block+(block->info&INFO_SIZE), block->info&INFO_SIZE, | ||
249 | (block->info&INFO_FREE)?"free":"used"); | ||
250 | block = block->higher; | ||
251 | } | ||
252 | printf("End of BLOCKS:\n"); | ||
253 | #endif | ||
254 | print_sizes(); | ||
255 | } | ||
256 | #endif /* DEBUG */ | ||
257 | |||
258 | void *bmalloc(size_t size) | ||
259 | { | ||
260 | void *mem; | ||
261 | |||
262 | #ifdef DEBUG | ||
263 | { | ||
264 | static int count=0; | ||
265 | int realsize = size + sizeof(struct BlockInfo); | ||
266 | if(realsize%4096) | ||
267 | realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; | ||
268 | printf("%d bmalloc(%d) [%d]\n", count++, size, realsize); | ||
269 | } | ||
270 | #endif | ||
271 | |||
272 | size += sizeof(struct BlockInfo); /* add memory for our header */ | ||
273 | |||
274 | if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be | ||
275 | changed if the BLOCKSIZE is not 2^X ! */ | ||
276 | size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */ | ||
277 | |||
278 | /* get a CHUNK from the list with this size */ | ||
279 | mem = obtainbysize ( size ); | ||
280 | if(mem) { | ||
281 | /* the memory block we have got is the "best-fit" and it is already | ||
282 | un-linked from the free list */ | ||
283 | |||
284 | /* now do the math to get the proper block pointer */ | ||
285 | struct BlockInfo *block= (struct BlockInfo *) | ||
286 | ((char *)mem - sizeof(struct BlockInfo)); | ||
287 | |||
288 | block->info &= ~INFO_FREE; | ||
289 | /* not free anymore */ | ||
290 | |||
291 | if( size != (block->info&INFO_SIZE)) { | ||
292 | /* split this chunk into two pieces and return the one that fits us */ | ||
293 | size_t othersize = (block->info&INFO_SIZE) - size; | ||
294 | |||
295 | if(othersize > BMEM_ALIGN) { | ||
296 | /* prevent losing small pieces of memory due to weird alignments | ||
297 | of the memory pool */ | ||
298 | |||
299 | block->info = size; /* set new size (leave FREE bit cleared) */ | ||
300 | |||
301 | /* Add the new chunk to the lists: */ | ||
302 | add_blocktolists(block, | ||
303 | (struct BlockInfo *)((char *)block + size), | ||
304 | othersize ); | ||
305 | } | ||
306 | } | ||
307 | |||
308 | /* Return the memory our parent may use: */ | ||
309 | return (char *)block+sizeof(struct BlockInfo); | ||
310 | } | ||
311 | else { | ||
312 | bmalloc_failed(size); | ||
313 | return NULL; /* can't find any memory, fail hard */ | ||
314 | } | ||
315 | return NULL; | ||
316 | } | ||
317 | |||
318 | void bfree(void *ptr) | ||
319 | { | ||
320 | struct BlockInfo *block = (struct BlockInfo *) | ||
321 | ((char *)ptr - sizeof(struct BlockInfo)); | ||
322 | size_t size; | ||
323 | |||
324 | /* setup our initial higher and lower pointers */ | ||
325 | struct BlockInfo *lower = block->lower; | ||
326 | struct BlockInfo *higher = block->higher; | ||
327 | |||
328 | #ifdef DEBUG | ||
329 | static int freecount=0; | ||
330 | printf("%d bfree(%p)\n", freecount++, ptr); | ||
331 | #endif | ||
332 | |||
333 | /* bind together lower addressed FREE CHUNKS */ | ||
334 | if(lower && (lower->info&INFO_FREE) && | ||
335 | ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) { | ||
336 | size = block->info&INFO_SIZE; /* original size */ | ||
337 | |||
338 | /* remove from size-link: */ | ||
339 | remove_chunksize((char *)lower+sizeof(struct BlockInfo)); | ||
340 | |||
341 | remove_block(block); /* unlink from address list */ | ||
342 | block = lower; /* new base area pointer */ | ||
343 | block->info += size; /* append the new size (the FREE bit | ||
344 | will remain untouched) */ | ||
345 | |||
346 | lower = lower->lower; /* new lower pointer */ | ||
347 | } | ||
348 | /* bind together higher addressed FREE CHUNKS */ | ||
349 | if(higher && (higher->info&INFO_FREE) && | ||
350 | ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) { | ||
351 | /* append higher size, the FREE bit won't be affected */ | ||
352 | block->info += (higher->info&INFO_SIZE); | ||
353 | |||
354 | /* unlink from size list: */ | ||
355 | remove_chunksize((char *)higher+sizeof(struct BlockInfo)); | ||
356 | remove_block(higher); /* unlink from address list */ | ||
357 | higher = higher->higher; /* the new higher link */ | ||
358 | block->higher = higher; /* new higher link */ | ||
359 | } | ||
360 | block->info |= INFO_FREE; /* consider this FREE! */ | ||
361 | |||
362 | block->lower = lower; | ||
363 | block->higher = higher; | ||
364 | |||
365 | insert_bysize((char *)block+sizeof(struct BlockInfo), block->info&INFO_SIZE); | ||
366 | |||
367 | #ifdef DEBUG | ||
368 | print_lists(); | ||
369 | #endif | ||
370 | |||
371 | } | ||