Rev 229 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
141 | trimarchi | 1 | /* |
2 | * Doubly indexed dynamic memory allocator (DIDMA) |
||
3 | * Version 0.61 |
||
4 | * |
||
5 | * Written by Miguel Masmano Tello <mmasmano@disca.upv.es> |
||
6 | * Copyright (C) Dec, 2002 OCERA Consortium |
||
7 | * Release under the terms of the GNU General Public License Version 2 |
||
8 | * shark porting Trimarchi Michael |
||
9 | */ |
||
10 | |||
11 | #include <kernel/func.h> |
||
12 | #include "didma.h" |
||
13 | #include "queuem.h" |
||
14 | #include "i386/bitops.h" |
||
15 | #include "i386/bits.h" |
||
16 | |||
17 | #ifndef NULL |
||
18 | #define NULL ((void *) 0) |
||
19 | #endif // #ifndef NULL |
||
20 | |||
21 | |||
22 | #define INIT_THREAD_MUTEX() |
||
23 | #define THREAD_LOCK() kern_cli() |
||
24 | #define THREAD_UNLOCK() kern_sti() |
||
25 | |||
26 | // u8, u16, u32 are only defined in kernel headers |
||
27 | |||
28 | #define u8 char |
||
29 | #define u16 unsigned short int |
||
30 | #define u32 unsigned int |
||
31 | |||
32 | #define MAX_SL_LOG2_INDEX 5 // Real value is 2**MAX_SL_INDEX |
||
33 | |||
34 | #define MAX_SL_INDEX (1 << MAX_SL_LOG2_INDEX) |
||
35 | |||
36 | #define F_OK 0 |
||
37 | #define F_ERROR -1 |
||
38 | |||
39 | #define MIN_LOG2_SIZE 5 // 32 bytes |
||
40 | #define MAX_LOG2_SIZE MAX_FL_INDEX |
||
41 | #define MIN_SIZE (1 << MIN_LOG2_SIZE) |
||
42 | #define MAX_SIZE (1 << MAX_LOG2_SIZE) |
||
43 | |||
44 | #define DIDMA__set_bit(num, mem) mem |= (1 << num) |
||
45 | #define DIDMA__clear_bit(num, mem) mem &= ~(1 << num) |
||
46 | |||
47 | /* |
||
48 | * First, all necessary TADs are defined |
||
49 | */ |
||
50 | |||
51 | |||
52 | /* |
||
53 | * the follow TAD will be a double level indexed array, the most important |
||
54 | * thing is that the time is limited, it is because this dynamic memory manger |
||
55 | * is designed to run with real time programs. |
||
56 | * |
||
57 | * First level Second level |
||
58 | * it is indexed it is indexed by 2**n+(2**n/m*index_number) |
||
59 | * by power of 2 |
||
60 | * 0 1 m-1 m |
||
61 | * ----> NULL --> NULL ----> NUL |
||
62 | * | | | |
||
63 | * ------- ---------------------...--------------------- |
||
64 | * 2**n | n | -----> |2**n+(2**n/m*0)|...| |...|2**n+(2**n/m*m)| |
||
65 | * |-----| ---------------------...--------------------- |
||
66 | * 2**n-1| n-1 | -----> .... | |
||
67 | * |-----| --->NULL |
||
68 | * ..... |
||
69 | */ |
||
70 | |||
71 | /* DON'T TOUCH THESE MACROS */ |
||
72 | #define MAGIC_NUMBER 0xA5A5 |
||
73 | #define MAGIC_NUMBER_NONE 0x0000 |
||
74 | #define BLOCK_FREE 0 |
||
75 | #define BLOCK_USED 1 |
||
76 | |||
77 | |||
78 | struct free_ptr_struct { |
||
79 | struct block_header_struct *prev; |
||
80 | struct block_header_struct *next; |
||
81 | /* |
||
82 | * first_l_index and second_l_index are used to store |
||
83 | * mapping_function results, that's how we get some extra |
||
84 | * nanoseconds |
||
85 | */ |
||
86 | u8 first_l_index; |
||
87 | u8 second_l_index; |
||
88 | }; |
||
89 | |||
90 | typedef struct block_header_struct { |
||
91 | /* magic_number is the id of the block */ |
||
92 | u16 magic_number; |
||
93 | /* size of the block */ |
||
94 | size_t size; |
||
95 | /* state of the block can be free or used */ |
||
96 | u8 state; |
||
97 | |||
98 | struct block_header_struct *prev; |
||
99 | struct block_header_struct *next; |
||
100 | |||
101 | union { |
||
102 | struct free_ptr_struct free_ptr; |
||
103 | u8 buffer[sizeof(struct free_ptr_struct)]; |
||
104 | } ptr; |
||
105 | } block_header_t; |
||
106 | |||
107 | /* first level index array */ |
||
108 | typedef struct fl_array_struct { |
||
109 | /* ptr is pointer to next level */ |
||
110 | block_header_t **sl_array; |
||
111 | /* n_blocks is the number of the blocks which they are pointed by sl_array */ |
||
112 | u32 bitmapSL; |
||
113 | } fl_array_t; |
||
114 | |||
115 | /* |
||
116 | * fl_array will be our first level array. |
||
117 | */ |
||
118 | |||
119 | static fl_array_t *fl_array;// [MAX_FL_INDEX - MIN_LOG2_SIZE]; |
||
120 | u32 bitmapFL; |
||
121 | /* |
||
122 | * first_bh will be our first memory block allocated by MALLOC function |
||
123 | */ |
||
124 | static block_header_t *first_bh, *free_block; |
||
125 | |||
126 | static int all_ok = 0; |
||
127 | |||
128 | /* |
||
129 | * header_overhead has size of blocks_header - 2 * ptr to next free block |
||
130 | */ |
||
131 | static int header_overhead = 0, total_size = 0; |
||
132 | |||
133 | /* |
||
134 | * log2size () returns cell of log2 (len) |
||
135 | * it does a search between MIN_SIZE and MAX_SIZE values |
||
136 | */ |
||
137 | static int log2size(size_t size, size_t *new_size) |
||
138 | { |
||
139 | int i; |
||
140 | |||
141 | if (size <= 0) { |
||
142 | PRINT_MSG ("ERROR: Chunk length must be > 0\n"); |
||
143 | return F_ERROR; |
||
144 | } |
||
145 | |||
146 | |||
147 | // MIN_SIZE and MAX_SIZE must be defined |
||
148 | |||
149 | if (size <= MIN_SIZE){ |
||
150 | *new_size = MIN_SIZE; |
||
151 | return MIN_LOG2_SIZE; |
||
152 | } |
||
153 | |||
154 | for (i = MIN_LOG2_SIZE; |
||
155 | (i <= MAX_LOG2_SIZE) && (size > (*new_size = (1 << i))) ; i++); |
||
156 | |||
157 | if (i > MAX_LOG2_SIZE) { |
||
158 | PRINT_MSG ("ERROR: Maximum chunk size exceeded\n"); |
||
159 | return F_ERROR; |
||
160 | } |
||
161 | |||
162 | return i; |
||
163 | } |
||
164 | |||
165 | /* |
||
166 | * caculate_reserve () returns the size that has to be reservate for |
||
167 | * avoid fragmentation |
||
168 | */ |
||
169 | |||
170 | #define MAX(a, b) (a>b)?a:b |
||
171 | |||
172 | /* |
||
173 | May be calculate_reserve can be improved |
||
174 | */ |
||
175 | |||
176 | static inline int calculate_reserve (int size){ |
||
177 | // int internal_frag, dummy; |
||
178 | |||
179 | // header_overhead = (int) first_bh -> ptr.buffer - (int) first_bh; |
||
180 | |||
181 | //internal_frag = (1 << log2size(size, &dummy)) / MAX_SL_INDEX; |
||
182 | |||
183 | //dummy = MAX((header_overhead * size / MAX_SL_INDEX) + internal_frag, size); |
||
184 | |||
185 | return size;//(size + dummy); |
||
186 | |||
187 | } |
||
188 | |||
189 | /* |
||
190 | * mapping_function () returns first and second level index |
||
191 | * |
||
192 | * first level index function is: |
||
193 | * fl = log2 (size) |
||
194 | * |
||
195 | * and second level index function is: |
||
196 | * sl = (size - 2**(log2size (size))) / (log2 (size) - log2 (MAX_SL_INDEX)) |
||
197 | * |
||
198 | */ |
||
199 | static int mapping_function (size_t size, int *fl, int *sl){ |
||
200 | int aux; |
||
201 | int new_len; |
||
202 | |||
203 | // first level = log2 (size) |
||
379 | giacomo | 204 | *fl = log2size (size, (size_t *)&new_len); |
141 | trimarchi | 205 | |
206 | if (new_len == size) { |
||
207 | // if 2**fl == size, second level must be 0 |
||
208 | *sl = 0; |
||
209 | } else { |
||
210 | -- *fl; |
||
211 | aux = *fl - MAX_SL_LOG2_INDEX; |
||
212 | *sl = (int)((size - (new_len >> 1)) >> aux); |
||
213 | } |
||
214 | |||
215 | *fl -= MIN_LOG2_SIZE; |
||
216 | return F_OK; |
||
217 | } |
||
218 | |||
219 | /* |
||
220 | * init_TAD () initialize the structure fl_array to NULL |
||
221 | * and free_block with the initial blocks pointed by ptr |
||
222 | * |
||
223 | * its cost is O (n x m) |
||
224 | */ |
||
225 | static int init_TAD (size_t size, u8 *ptr){ |
||
226 | int n, aux, dummy; |
||
227 | if (!(size > 0)) { |
||
228 | PRINT_MSG ("ERROR: size must be > 0\n"); |
||
229 | return F_ERROR; |
||
230 | } |
||
231 | if (MAX_SL_INDEX > MIN_SIZE) { |
||
232 | PRINT_MSG ("ERROR: MAX_SL_INDEX must be < MIN_SIZE\n"); |
||
233 | return F_ERROR; |
||
234 | } |
||
235 | |||
236 | total_size = size; |
||
237 | |||
379 | giacomo | 238 | MAX_FL_INDEX = log2size(size, (size_t *)&dummy); |
141 | trimarchi | 239 | |
240 | if (MAX_FL_INDEX < 0) return -1; |
||
241 | fl_array = (fl_array_t *) SYSTEM_MALLOC ((MAX_FL_INDEX - MIN_LOG2_SIZE) |
||
242 | * sizeof(fl_array_t)); |
||
243 | if (fl_array == NULL) return -1; |
||
244 | _init_malloc_ (20); |
||
245 | for (n = 0; n < MAX_FL_INDEX - MIN_LOG2_SIZE; n++) { |
||
246 | fl_array [n].bitmapSL = 0; |
||
247 | aux = (1 << (n + MIN_LOG2_SIZE)); |
||
248 | fl_array[n].sl_array = NULL; |
||
249 | } |
||
250 | bitmapFL = 0; |
||
251 | |||
252 | header_overhead = (int) first_bh -> ptr.buffer - (int) first_bh; |
||
253 | first_bh = (block_header_t *) ptr; |
||
254 | |||
255 | first_bh -> magic_number = MAGIC_NUMBER; |
||
256 | first_bh -> size = size - header_overhead; |
||
257 | first_bh -> state = BLOCK_FREE; |
||
258 | first_bh -> prev = NULL; |
||
259 | first_bh -> next = NULL; |
||
260 | first_bh -> ptr.free_ptr.prev = NULL; |
||
261 | first_bh -> ptr.free_ptr.next = NULL; |
||
262 | |||
263 | free_block = first_bh; |
||
264 | //mapping_function (first_bh->size,&n, &m); |
||
265 | //fl_array[n].sl_array[m].ptr= first_bh; |
||
266 | //DIDMA__set_bit (m, fl_array[n].bitmapSL); |
||
267 | //DIDMA__set_bit (n, bitmapFL); |
||
268 | all_ok = 1; |
||
269 | return F_OK; |
||
270 | } |
||
271 | |||
272 | /* |
||
273 | * destroy_TAD return a pointer to the initial block |
||
274 | */ |
||
275 | static void *destroy_TAD (void){ |
||
276 | all_ok = 0; |
||
277 | _destroy_malloc_(); |
||
278 | return (void *) first_bh; |
||
279 | } |
||
280 | |||
281 | /* |
||
282 | * insert_TAD merge a free block pointed by ptr |
||
283 | * with its buddies and then |
||
284 | * insert it into fl_array |
||
285 | * |
||
286 | * The cost of this operation is |
||
287 | * always O (K) = (1) |
||
288 | */ |
||
289 | static int insert_TAD (u8 *ptr){ |
||
290 | int fl, sl; |
||
291 | block_header_t *bh = NULL, *bh2; |
||
292 | int for_free_block = 0; |
||
293 | |||
294 | if (!all_ok) return F_ERROR; |
||
295 | |||
296 | bh = (block_header_t *) (ptr - header_overhead); |
||
297 | if (bh -> magic_number != MAGIC_NUMBER) |
||
298 | return F_ERROR; |
||
299 | |||
300 | THREAD_LOCK(); |
||
301 | /* |
||
302 | * now bh is a free block |
||
303 | */ |
||
304 | bh -> state = BLOCK_FREE; |
||
305 | bh -> ptr.free_ptr.prev = NULL; |
||
306 | bh -> ptr.free_ptr.next = NULL; |
||
307 | |||
308 | /* |
||
309 | * first bh will be merge with its free buddies and |
||
310 | * then it will be inserted with the free blocks |
||
311 | */ |
||
312 | /* |
||
313 | * it is used to know if bh have to be inserted into free_block or |
||
314 | * into fl_array |
||
315 | */ |
||
316 | if (bh -> next == NULL) for_free_block = 1; |
||
317 | |||
318 | /* is it free the follow block? */ |
||
319 | if (bh -> next != NULL) { |
||
320 | bh2 = bh -> next; |
||
321 | |||
322 | if (bh2 -> magic_number == MAGIC_NUMBER && |
||
323 | bh2 -> state == BLOCK_FREE) { |
||
324 | /* we are lucky, we can merge bh with the next block */ |
||
325 | |||
326 | if (bh2 == free_block) for_free_block = 1; |
||
327 | bh2 -> magic_number = MAGIC_NUMBER_NONE; |
||
328 | if (bh2 -> next != NULL) |
||
329 | bh2 -> next -> prev = bh; |
||
330 | if (!for_free_block) { |
||
331 | if (bh2 -> ptr.free_ptr.next != NULL) |
||
332 | bh2 -> ptr.free_ptr.next -> ptr.free_ptr.prev = |
||
333 | bh2 -> ptr.free_ptr.prev; |
||
334 | |||
335 | if (bh2 -> ptr.free_ptr.prev != NULL) |
||
336 | bh2 -> ptr.free_ptr.prev -> ptr.free_ptr.next = |
||
337 | bh2 -> ptr.free_ptr.next; |
||
338 | //mapping_function (bh2 -> size, &fl, &sl); |
||
339 | fl = bh2 -> ptr.free_ptr.first_l_index; |
||
340 | sl = bh2 -> ptr.free_ptr.second_l_index; |
||
341 | /* bh2 must be erased from fl_array */ |
||
342 | if (fl_array [fl].sl_array [sl] == bh2) |
||
343 | fl_array [fl].sl_array [sl] = bh2 -> ptr.free_ptr.next; |
||
344 | |||
345 | //fl_array [fl].n_blocks --; |
||
346 | if (fl_array [fl].sl_array [sl] == NULL){ |
||
347 | //fl_array[fl].bitmapSL &= ~(1 << sl); |
||
348 | DIDMA__clear_bit (sl, fl_array[fl].bitmapSL); |
||
349 | if (!fl_array[fl].bitmapSL) { |
||
350 | _free_ ((void *) fl_array [fl].sl_array); |
||
351 | DIDMA__clear_bit (fl, bitmapFL); |
||
352 | } |
||
353 | } |
||
354 | } |
||
355 | bh -> size += bh2 -> size + header_overhead; |
||
356 | bh -> next = bh2 -> next; |
||
357 | } |
||
358 | } |
||
359 | |||
360 | /* is it free the previous block? */ |
||
361 | if (bh -> prev != NULL) { |
||
362 | bh2 = bh -> prev; |
||
363 | if (bh2 -> magic_number == MAGIC_NUMBER && |
||
364 | bh2 -> state == BLOCK_FREE) { |
||
365 | bh -> magic_number = MAGIC_NUMBER_NONE; |
||
366 | |||
367 | if (bh -> next != NULL) |
||
368 | bh -> next -> prev = bh2; |
||
369 | |||
370 | if (bh2 -> ptr.free_ptr.next != NULL) |
||
371 | bh2 -> ptr.free_ptr.next -> ptr.free_ptr.prev = |
||
372 | bh2 -> ptr.free_ptr.prev; |
||
373 | |||
374 | if (bh2 -> ptr.free_ptr.prev != NULL) |
||
375 | bh2 -> ptr.free_ptr.prev -> ptr.free_ptr.next = |
||
376 | bh2 -> ptr.free_ptr.next; |
||
377 | |||
378 | //mapping_function (bh2 -> size, &fl, &sl); |
||
379 | |||
380 | fl = bh2 -> ptr.free_ptr.first_l_index; |
||
381 | sl = bh2 -> ptr.free_ptr.second_l_index; |
||
382 | if (fl_array [fl].sl_array [sl] == bh2) |
||
383 | fl_array [fl].sl_array [sl] = bh2 -> ptr.free_ptr.next; |
||
384 | |||
385 | if (fl_array[fl].sl_array[sl] == NULL){ |
||
386 | //fl_array[fl].bitmapSL &= ~(1 << sl); |
||
387 | DIDMA__clear_bit (sl, fl_array[fl].bitmapSL); |
||
388 | if (!fl_array[fl].bitmapSL) { |
||
389 | _free_ ((void *) fl_array [fl].sl_array); |
||
390 | DIDMA__clear_bit (fl, bitmapFL); |
||
391 | } |
||
392 | } |
||
393 | |||
394 | bh2 -> size += bh -> size + header_overhead; |
||
395 | bh2 -> next = bh -> next; |
||
396 | bh = bh2; |
||
397 | |||
398 | } |
||
399 | } |
||
400 | |||
401 | /* |
||
402 | * and then we merge the free block with the initial memory |
||
403 | */ |
||
404 | if (for_free_block) { |
||
405 | free_block = bh; |
||
406 | bh -> ptr.free_ptr.next = NULL; |
||
407 | bh -> ptr.free_ptr.prev = NULL; |
||
408 | } else { |
||
409 | /* |
||
410 | * or we insert the free block in the TAD |
||
411 | */ |
||
412 | mapping_function (bh -> size, &fl, &sl); |
||
413 | if (fl_array[fl].bitmapSL == 0) |
||
414 | fl_array[fl].sl_array = (block_header_t **) _malloc_ (); |
||
415 | if (fl_array[fl].sl_array == NULL) { |
||
416 | PRINT_MSG("CRITICAL ERROR: there isn't enought memory for free\n"); |
||
229 | giacomo | 417 | THREAD_UNLOCK(); |
418 | return F_ERROR; |
||
141 | trimarchi | 419 | } |
420 | bh -> ptr.free_ptr.first_l_index = fl; |
||
421 | bh -> ptr.free_ptr.second_l_index = sl; |
||
422 | bh -> ptr.free_ptr.next = fl_array [fl].sl_array [sl]; |
||
423 | bh -> ptr.free_ptr.prev = NULL; |
||
424 | if (fl_array [fl].sl_array [sl] != NULL) |
||
425 | fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = bh; |
||
426 | fl_array [fl].sl_array [sl] = bh; |
||
427 | |||
428 | DIDMA__set_bit (sl, fl_array[fl].bitmapSL); |
||
429 | DIDMA__set_bit (fl, bitmapFL); |
||
430 | |||
431 | } |
||
432 | |||
433 | THREAD_UNLOCK(); |
||
434 | return F_OK; |
||
435 | } |
||
436 | |||
437 | /* |
||
438 | * search_TAD searchs a free block of size 'size' |
||
439 | * then this block will be splitted in two new blocks, |
||
440 | * one of these new blocks will be given to the user and the |
||
441 | * other will be inserted into a free blocks structure |
||
442 | * |
||
443 | * The cost of this operation is |
||
444 | * best case: (K) = (1) |
||
445 | * worst case: (MAX_FL_LOG2_INDEX - MIN_FL_LOG2_INDEX + MAX_SL_INDEX + K) |
||
446 | * = (1) |
||
447 | * where K is an integer constant |
||
448 | */ |
||
449 | |||
450 | static u8 *search_TAD (size_t size) { |
||
451 | int for_free_block = 0; |
||
452 | int fl, sl, n; |
||
453 | int found; |
||
454 | block_header_t *bh = NULL, *bh2; |
||
455 | |||
456 | if (!(size > 0) || size >= MAX_SIZE || !all_ok) return NULL; |
||
457 | THREAD_LOCK(); |
||
458 | |||
459 | if (size <= MIN_SIZE) { |
||
460 | size = MIN_SIZE; |
||
461 | fl = 0; |
||
462 | sl = 0; |
||
463 | } else { |
||
464 | mapping_function (size, &fl, &sl); |
||
465 | |||
466 | if (++sl == MAX_SL_INDEX) { |
||
467 | fl ++; |
||
468 | sl = 0; |
||
469 | } |
||
470 | /* |
||
471 | * This is the reason of the internal fragmentation |
||
472 | * The block given is greater that the size demanded |
||
473 | */ |
||
474 | size = (1 << (fl + MIN_LOG2_SIZE)); |
||
475 | size = size + ((size >> MAX_SL_LOG2_INDEX) * sl); |
||
476 | } |
||
477 | |||
478 | /* the size given can be bigger than the size demanded */ |
||
479 | found = 0; |
||
480 | |||
481 | // we take the first free block from fl_array or a buddy of him |
||
482 | |||
483 | sl = fl_array[fl].bitmapSL & ((~0) << sl); |
||
484 | if (sl != 0) { |
||
485 | sl = DIDMA_fls(sl); |
||
486 | bh = fl_array [fl].sl_array [sl]; |
||
487 | fl_array [fl].sl_array [sl] = bh -> ptr.free_ptr.next; |
||
488 | if (fl_array [fl].sl_array [sl] != NULL) |
||
489 | fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = NULL; |
||
490 | else { |
||
491 | DIDMA__clear_bit (sl, fl_array[fl].bitmapSL); |
||
492 | if (!fl_array[fl].bitmapSL) { |
||
493 | DIDMA__clear_bit (fl, bitmapFL); |
||
494 | _free_ ((void *) fl_array [fl].sl_array); |
||
495 | } |
||
496 | } |
||
497 | found = 1; |
||
498 | goto out; |
||
499 | } |
||
500 | /* |
||
501 | * if fl_array is empty we will take a free block |
||
502 | * from free_block pointer |
||
503 | */ |
||
504 | |||
505 | if (free_block != NULL && free_block -> size >= size) { |
||
506 | bh = free_block; |
||
507 | free_block = NULL; |
||
508 | for_free_block = 1; |
||
509 | found = 1; |
||
510 | goto out; |
||
511 | } |
||
512 | |||
513 | /* |
||
514 | * A free block is searched |
||
515 | * |
||
516 | * Using a bitmap |
||
517 | */ |
||
518 | |||
519 | fl = DIDMA_fls(bitmapFL & ((~0) << (fl + 1))); |
||
520 | |||
521 | if (fl > 0) { |
||
522 | sl = DIDMA_fls(fl_array[fl].bitmapSL); |
||
523 | bh = fl_array [fl].sl_array [sl]; |
||
524 | fl_array [fl].sl_array [sl] = bh -> ptr.free_ptr.next; |
||
525 | if (fl_array [fl].sl_array [sl] != NULL){ |
||
526 | fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = NULL; |
||
527 | } else { |
||
528 | DIDMA__clear_bit (sl, fl_array[fl].bitmapSL); |
||
529 | if (!fl_array[fl].bitmapSL) { |
||
530 | _free_ ((void *) fl_array[fl].sl_array); |
||
531 | DIDMA__clear_bit (fl, bitmapFL); |
||
532 | } |
||
533 | } |
||
534 | found = 1; |
||
535 | goto out; |
||
536 | } |
||
537 | |||
538 | out: |
||
539 | |||
540 | /* |
||
541 | * HUGGGG, NOT ENOUGHT MEMORY |
||
542 | * I think that we have done all that we have been able |
||
543 | */ |
||
544 | if (!found) { |
||
545 | PRINT_MSG ("ERROR: Memory pool exhausted!!!\n"); |
||
546 | THREAD_UNLOCK(); |
||
547 | return NULL; |
||
548 | } |
||
549 | |||
550 | /* |
||
551 | * we can say: YESSSSSSSSSSS, we have enought memory!!!! |
||
552 | */ |
||
553 | bh -> state = BLOCK_USED; |
||
554 | |||
555 | /* can bh be splitted? */ |
||
556 | n = (int)(bh -> size - size - header_overhead); |
||
557 | if (n >= (int) MIN_SIZE) { |
||
558 | |||
559 | /* |
||
560 | * Yes, bh will be splitted |
||
561 | */ |
||
562 | |||
563 | bh2 = (block_header_t *) ((u8 *)(bh -> ptr.buffer) + size); |
||
564 | bh2 -> magic_number = MAGIC_NUMBER; |
||
565 | bh2 -> state = BLOCK_FREE; |
||
566 | bh2 -> size = n; |
||
567 | if (bh -> next != NULL) |
||
568 | bh -> next -> prev = bh2; |
||
569 | bh2 -> next = bh -> next; |
||
570 | bh -> next = bh2; |
||
571 | bh2 -> prev = bh; |
||
572 | bh -> size = size; |
||
573 | |||
574 | if (!for_free_block) { |
||
575 | mapping_function (bh2 -> size, &fl, &sl); |
||
576 | if (fl_array[fl].bitmapSL == 0) |
||
577 | fl_array[fl].sl_array = (block_header_t **) _malloc_ (); |
||
578 | if (fl_array[fl].sl_array == NULL) { |
||
579 | PRINT_MSG("CRITICAL ERROR: there isn't enought memory for free\n"); |
||
580 | return NULL; |
||
581 | } |
||
582 | bh2 -> ptr.free_ptr.first_l_index = fl; |
||
583 | bh2 -> ptr.free_ptr.second_l_index = sl; |
||
584 | bh2 -> ptr.free_ptr.prev = NULL; |
||
585 | bh2 -> ptr.free_ptr.next = fl_array [fl].sl_array [sl]; |
||
586 | |||
587 | if (fl_array [fl].sl_array [sl] != NULL) |
||
588 | fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = bh2; |
||
589 | fl_array [fl].sl_array [sl] = bh2; |
||
590 | DIDMA__set_bit (sl, fl_array[fl].bitmapSL); |
||
591 | DIDMA__set_bit (fl, bitmapFL); |
||
592 | |||
593 | //fl_array [fl].n_blocks ++; |
||
594 | } else |
||
595 | free_block = bh2; |
||
596 | } |
||
597 | THREAD_UNLOCK(); |
||
598 | return (u8 *) bh -> ptr.buffer; |
||
599 | } |
||
600 | |||
601 | |||
602 | int init_memory_pool (int max_size){ |
||
603 | |||
604 | u8 *buffer; |
||
605 | int real_max_size = 0; |
||
606 | |||
607 | if (max_size < 0) return -1; |
||
608 | |||
609 | |||
610 | //buffer = (u8 *) SYSTEM_MALLOC (real_max_size * sizeof (u8)); |
||
611 | real_max_size = calculate_reserve(max_size); |
||
612 | buffer = (u8 *) SYSTEM_MALLOC (real_max_size * sizeof (u8)); |
||
613 | if (buffer == NULL) return F_ERROR; |
||
614 | return init_TAD (real_max_size, buffer); |
||
615 | } |
||
616 | |||
617 | void destroy_memory_pool(void){ |
||
618 | |||
619 | SYSTEM_FREE (destroy_TAD ()); |
||
620 | } |
||
621 | |||
622 | /* see 'man malloc' */ |
||
623 | void *rt_malloc (size_t size){ |
||
624 | return (void *) search_TAD (size); |
||
625 | } |
||
626 | |||
627 | /* see 'man free' */ |
||
628 | void rt_free (void *ptr){ |
||
629 | if (ptr != NULL) insert_TAD ((u8 *) ptr); |
||
630 | } |
||
631 | |||
632 | /* see 'man calloc' */ |
||
633 | void *rt_calloc (size_t nelem, size_t elem_size) |
||
634 | { |
||
635 | void *p; |
||
636 | |||
637 | if (!all_ok || nelem <= 0 || elem_size <= 0) return NULL; |
||
638 | |||
639 | if ((p = rt_malloc (nelem * elem_size)) == NULL) |
||
640 | return NULL; |
||
641 | |||
642 | memset (p, 0, nelem * elem_size); |
||
643 | |||
644 | return p; |
||
645 | } |
||
646 | |||
647 | /* |
||
648 | * see man realloc |
||
649 | * be careful, realloc () is an expensive operation because |
||
650 | * it uses malloc () and free () |
||
651 | */ |
||
652 | void *rt_realloc (void *p, size_t new_len) |
||
653 | { |
||
654 | u8 *aux; |
||
655 | void *addr; |
||
656 | int old_len, min; |
||
657 | block_header_t *b; |
||
658 | |||
659 | if (!all_ok) return NULL; |
||
660 | |||
661 | if (p == NULL) |
||
662 | return rt_malloc (new_len); |
||
663 | else if (new_len == 0) { |
||
664 | rt_free(p); |
||
665 | return NULL; |
||
666 | } else { |
||
667 | /* |
||
668 | * Now we try to achieve old size because |
||
669 | * then we need it to copy all data in the new allocated |
||
670 | * memory |
||
671 | */ |
||
672 | aux = (u8 *) p; |
||
673 | aux -= header_overhead; |
||
674 | b = (block_header_t *) aux; |
||
675 | if (b -> magic_number == MAGIC_NUMBER) { |
||
676 | old_len = b -> size; |
||
677 | } else { |
||
678 | PRINT_MSG ("CRITICAL ERROR: block corrupted\n"); |
||
679 | return NULL; |
||
680 | } |
||
681 | |||
682 | addr = rt_malloc (new_len); |
||
683 | |||
684 | if (addr == NULL) return NULL; |
||
685 | |||
686 | min = (old_len > new_len)? new_len : old_len; |
||
687 | memcpy (addr, p, min); |
||
688 | rt_free (p); |
||
689 | |||
690 | return addr; |
||
691 | } |
||
692 | } |
||
693 | |||
694 | #ifdef __DEBUG__ |
||
695 | |||
696 | /* |
||
697 | * dump_mem () is a simple operation, |
||
698 | * it only does a dumped of memory |
||
699 | */ |
||
700 | |||
701 | void dump_mem (void){ |
||
702 | u8 *aux; |
||
703 | int n; |
||
704 | |||
705 | if (!all_ok) return; |
||
706 | |||
707 | aux = (u8 *) first_bh; |
||
708 | |||
709 | for (n = 0; n < total_size; n++) { |
||
710 | PRINT_DBG_H (aux [n]); |
||
711 | PRINT_DBG_C (" "); |
||
712 | } |
||
713 | PRINT_DBG_C ("\n"); |
||
714 | } |
||
715 | |||
716 | /* |
||
717 | * I haven't anything to say about print_block () |
||
718 | */ |
||
719 | static void print_block (block_header_t *b){ |
||
720 | if (b == NULL) return; |
||
721 | PRINT_DBG_C (">>>> MNum 0x"); |
||
722 | PRINT_DBG_H (b -> magic_number); |
||
723 | PRINT_DBG_C (" Address 0x"); |
||
724 | //PRINT_DBG_H (b); |
||
725 | if (b -> state == BLOCK_FREE) |
||
726 | PRINT_DBG_C (" State FREE"); |
||
727 | else |
||
728 | PRINT_DBG_C (" State USED"); |
||
729 | PRINT_DBG_C (" Size "); |
||
730 | PRINT_DBG_D (b -> size); |
||
731 | PRINT_DBG_C ("\n---- Prev 0x"); |
||
732 | //PRINT_DBG_H (b -> prev); |
||
733 | PRINT_DBG_C (" Next 0x"); |
||
734 | //PRINT_DBG_H (b -> next); |
||
735 | if (b -> state == BLOCK_FREE){ |
||
736 | PRINT_DBG_C ("\n---- Prev Free 0x"); |
||
737 | //PRINT_DBG_H (b -> ptr.free_ptr.prev); |
||
738 | PRINT_DBG_C (" Next Free 0x"); |
||
739 | //PRINT_DBG_H (b -> ptr.free_ptr.next); |
||
740 | } |
||
741 | PRINT_DBG_C ("\n"); |
||
742 | } |
||
743 | |||
744 | /* |
||
745 | * structure_context () show the content of all blocks |
||
746 | */ |
||
747 | void structure_context (void) { |
||
748 | block_header_t *b; |
||
749 | |||
750 | if (!all_ok) return; |
||
751 | |||
752 | b = first_bh; |
||
753 | PRINT_DBG_C ("\nALL BLOCKS\n"); |
||
754 | while (b != NULL) { |
||
755 | print_block (b); |
||
756 | b = b -> next; |
||
757 | } |
||
758 | |||
759 | } |
||
760 | |||
761 | /* |
||
762 | * global_state () returns overhead, free and used space |
||
763 | */ |
||
764 | void global_state (int *free, int *used, int *overhead){ |
||
765 | block_header_t *b; |
||
766 | |||
767 | *free = 0; |
||
768 | *used = 0; |
||
769 | *overhead = 0; |
||
770 | if (!all_ok) return; |
||
771 | b = first_bh; |
||
772 | while (b != NULL) { |
||
773 | if (b -> state == BLOCK_USED) { |
||
774 | *used += b -> size; |
||
775 | } else { |
||
776 | *free += b -> size; |
||
777 | } |
||
778 | b = b -> next; |
||
779 | *overhead += header_overhead; |
||
780 | } |
||
781 | |||
782 | } |
||
783 | |||
784 | /* |
||
785 | * free_blocks_context () show the content |
||
786 | * of free blocks |
||
787 | */ |
||
788 | void free_blocks_context (void){ |
||
789 | int i, j; |
||
790 | block_header_t *b; |
||
791 | |||
792 | if (!all_ok) return; |
||
793 | |||
794 | PRINT_DBG_C ("\nFREE BLOCKS\n"); |
||
795 | PRINT_DBG_C ("MAIN BLOCK\n"); |
||
796 | print_block (free_block); |
||
797 | PRINT_DBG_C ("FRAGMENTED BLOCKS\n"); |
||
798 | for (i = MAX_FL_INDEX - 1 - MIN_LOG2_SIZE; i >= 0; i--) { |
||
799 | if (fl_array [i].bitmapSL > 0) |
||
800 | for (j = MAX_SL_INDEX - 1; j >= 0; j--) { |
||
801 | if (fl_array [i].sl_array[j] != NULL) { |
||
802 | b = fl_array [i].sl_array [j]; |
||
803 | PRINT_DBG_C ("["); |
||
804 | PRINT_DBG_D (i); |
||
805 | PRINT_DBG_C ("] "); |
||
806 | PRINT_DBG_D (1 << (i + MIN_LOG2_SIZE)); |
||
807 | PRINT_DBG_C (" bytes -> Free blocks: 0x"); |
||
808 | PRINT_DBG_H (fl_array [i].bitmapSL); |
||
809 | PRINT_DBG_C ("\n"); |
||
810 | |||
811 | while (b != NULL) { |
||
812 | PRINT_DBG_C (">>>> "); |
||
813 | PRINT_DBG_D ((1 << (i + MIN_LOG2_SIZE)) + |
||
814 | (1<< (i + MIN_LOG2_SIZE)) / MAX_SL_INDEX * j); |
||
815 | PRINT_DBG_C (" bytes\n"); |
||
816 | print_block (b); |
||
817 | b = b -> ptr.free_ptr.next; |
||
818 | } |
||
819 | } |
||
820 | } |
||
821 | } |
||
822 | } |
||
823 | |||
824 | /* |
||
825 | * check_mem () checks memory searching |
||
826 | * errors and incoherences |
||
827 | * return : |
||
828 | * 0 if there isn't any error |
||
829 | * or |
||
830 | * -1 in other case |
||
831 | */ |
||
832 | int check_mem (void){ |
||
833 | block_header_t *b, *b2; |
||
834 | int i, j, num_blocks; |
||
835 | |||
836 | if (!all_ok) return F_ERROR; |
||
837 | |||
838 | b = first_bh; |
||
839 | num_blocks = 0; |
||
840 | for (i = MAX_FL_INDEX - 1 - MIN_LOG2_SIZE; i >= 0; i--) { |
||
841 | if (fl_array [i].bitmapSL < 0) return F_ERROR; |
||
842 | for (j = MAX_SL_INDEX - 1; j >= 0; j--) { |
||
843 | b2 = fl_array [i].sl_array[j]; |
||
844 | while (b2 != NULL) { |
||
845 | b2 = b2 -> ptr.free_ptr.next; |
||
846 | num_blocks ++; |
||
847 | } |
||
848 | } |
||
849 | if (num_blocks != fl_array [i].bitmapSL) return F_ERROR; |
||
850 | num_blocks = 0; |
||
851 | } |
||
852 | |||
853 | while (b != NULL) { |
||
854 | if (b -> magic_number != MAGIC_NUMBER || |
||
855 | b -> size > MAX_SIZE || b -> size < MIN_SIZE) |
||
856 | return F_ERROR; |
||
857 | |||
858 | if (b -> next != NULL) |
||
859 | if (b -> next < first_bh || b -> next > |
||
860 | (block_header_t *) ((u8 *) (first_bh) + MAX_SIZE)) |
||
861 | return F_ERROR; |
||
862 | |||
863 | if (b -> prev != NULL) |
||
864 | if (b -> prev < first_bh || b -> prev > |
||
865 | (block_header_t *) ((u8 *) (first_bh) + MAX_SIZE) ) |
||
866 | return F_ERROR; |
||
867 | |||
868 | if (b -> state != BLOCK_FREE && b -> state != BLOCK_USED) return F_ERROR; |
||
869 | if (b -> state == BLOCK_FREE) { |
||
870 | if (b -> ptr.free_ptr.next != NULL) |
||
871 | if (b -> ptr.free_ptr.next < first_bh || |
||
872 | b -> ptr.free_ptr.next > |
||
873 | (block_header_t *) ((u8 *) (first_bh) + MAX_SIZE)) |
||
874 | return F_ERROR; |
||
875 | |||
876 | if (b -> ptr.free_ptr.prev != NULL) |
||
877 | if (b -> ptr.free_ptr.prev < first_bh || |
||
878 | b -> ptr.free_ptr.prev > |
||
879 | (block_header_t *) ((u8 *) (first_bh) + MAX_SIZE) ) |
||
880 | return F_ERROR; |
||
881 | } |
||
882 | |||
883 | b = b -> next; |
||
884 | |||
885 | } |
||
886 | return F_OK; |
||
887 | } |
||
888 | #endif // #ifdef __DEBUG__ |