source: soft/giet_vm/libs/malloc.c @ 241

Last change on this file since 241 was 239, checked in by joannou, 12 years ago

Changed NB_TASKS to NB_TASKS_MAX in malloc.c file
File size: 38.3 KB
RevLine 
[233]1
2#include "malloc.h"
3#include "malloc_private.h"
4#include "stdio.h"
5
[239]6heap_ll * _heap_head[NB_TASKS_MAX];
[233]7
[239]8unsigned int _heap_base[NB_TASKS_MAX];
9unsigned int _heap_length[NB_TASKS_MAX];
[233]10
[239]11int _first_malloc[NB_TASKS_MAX] = { 0 };
[233]12
13
14#if MALLOC_SELECTED == 1
15
16#elif MALLOC_SELECTED == 2
[239]17    heap_ll * _prev_next_last_allocted[NB_TASKS_MAX] = { 0 };
[233]18#else
19    #define MAX_SIZE_POW2_TAB 28
20    #define GET_TAB_INDEX(size) (size == 0x00000008) ? 0 :\
21                            (size <= 0x00000010) ? 1 :\
22                            (size <= 0x00000020) ? 2 :\
23                            (size <= 0x00000040) ? 3 :\
24                            (size <= 0x00000080) ? 4 :\
25                            (size <= 0x00000100) ? 5 :\
26                            (size <= 0x00000200) ? 6 :\
27                            (size <= 0x00000400) ? 7 :\
28                            (size <= 0x00000800) ? 8 :\
29                            (size <= 0x00001000) ? 9 :\
30                            (size <= 0x00002000) ? 10 :\
31                            (size <= 0x00004000) ? 11 :\
32                            (size <= 0x00008000) ? 12 :\
33                            (size <= 0x00010000) ? 13 :\
34                            (size <= 0x00020000) ? 14 :\
35                            (size <= 0x00040000) ? 15 :\
36                            (size <= 0x00080000) ? 16 :\
37                            (size <= 0x00100000) ? 17 :\
38                            (size <= 0x00200000) ? 18 :\
39                            (size <= 0x00400000) ? 19 :\
40                            (size <= 0x00800000) ? 20 :\
41                            (size <= 0x01000000) ? 21 :\
42                            (size <= 0x02000000) ? 22 :\
43                            (size <= 0x04000000) ? 23 :\
44                            (size <= 0x08000000) ? 24 :\
45                            (size <= 0x10000000) ? 25 :\
46                            (size <= 0x20000000) ? 26 :\
47                                                   27
48
[239]49    heap_ll * _pow2tab[NB_TASKS_MAX][MAX_SIZE_POW2_TAB] = {{ 0 }};
[233]50#endif
51
52/* Todo: meilleure gestion des printf
53//#if DEBUG_MALLOC == 1
54unsigned int debug_level = 2;
55#elif DEBUG_MALLOC == 0
56
57#define giet_printf(level, ...)                 \
58({                                           \
59if (debug_level < level) {              \
60giet_tty_printf(__VA_ARGS__);       \
61}                                       \
62})
63*/
64
65
66#if MALLOC_SELECTED == 1
67
68heap_ll *get_prev_fit_chunk(unsigned int size) {
69    int task_id = giet_global_task_id();
70    if (_heap_head[task_id] == 0x0) {
71        return ((heap_ll *) 0x01);
72    }
73    int found = 0;
74    heap_ll * ptr_to_chunk_list = _heap_head[task_id];
75    heap_ll * tmp = 0x0;
76    heap_ll * prev = 0x0;
77    heap_ll * prev_tmp = 0x0;
78    while (ptr_to_chunk_list != 0x0) {
79        if (size <= ptr_to_chunk_list->chunk_length) {
80            if (tmp == 0x0 || ptr_to_chunk_list->chunk_length > tmp->chunk_length) {
81                prev_tmp = prev;
82                tmp = ptr_to_chunk_list;
83                found = 1;
84            }
85        }
86        prev = ptr_to_chunk_list;
87        ptr_to_chunk_list = ptr_to_chunk_list->next;
88    }
89    if (found == 1) {
90        return prev_tmp; // case when prev_tmp == 0x0 is handled in the calling function
91    }
92    else {
93        return (heap_ll *) 0x1;
94    }
95}
96
97
98
99void * malloc(unsigned int size) {
100    int task_id = giet_global_task_id();
101
102#if DEBUG_MALLOC == 1
103    giet_tty_printf("############ MALLOC ############\n\n");
104#endif
105    if (size == 0) {
106#if DEBUG_MALLOC == 1
107        giet_tty_printf(" SIZE = 0 \n");
108#endif
109        return 0x0;
110    }
111
112    /****** First call to malloc ******/
113    if (_first_malloc[task_id] == 0) {
114        giet_heap_info(&_heap_base[task_id], &_heap_length[task_id]);
115
116        if (_heap_length[task_id] == 0) {
117            giet_tty_printf("*** Error: Malloc called in task %d while no heap was defined.\n", task_id);
118            return 0x0;
119        }
120        _heap_head[task_id] = (heap_ll *) _heap_base[task_id];
121        _heap_head[task_id]->chunk_length = _heap_length[task_id];
122        _heap_head[task_id]->next = 0x0;
123
124
125        _first_malloc[task_id] = 1;
126    }
127
128    /****** Size align ******/
129    int size_align = size;
130    if (size % 4 != 0) {
131        size_align = ((size / 4) + 1) * 4;
132    }
133
134
135#if DEBUG_MALLOC == 1
136    giet_tty_printf("Looking for size : %d\n", size_align + 4);
137#endif
138    /****** Get prev victim from the chunks list ******/
139    heap_ll *victim;
140    heap_ll *prev_victim;
141    //// WORST
142
143    if ((prev_victim = get_prev_fit_chunk(size_align + 4)) == (heap_ll *) 0x1) {
144        return 0x0;             // no chunk of this size avaiable, 0x1 : no suitable chunk found
145    }
146    else {
147        if (prev_victim != 0x0) {
148            // victim != HEAD
149            victim = prev_victim->next;
150        }
151        else {
152            victim = _heap_head[task_id];
153        }
154    }
155    /****** Get Victim Base ******/
156    unsigned int victim_vbase = (unsigned int) victim;  // overhead
157
158    /****** update the chunks list ******/
159    if (victim->chunk_length == size_align + 4) {
160        // if it is an exact match
161        if (prev_victim == 0x0) {
162            // if victim == head
163            _heap_head[task_id] = victim->next;
164        }
165        else {
166            prev_victim->next = victim->next;
167        }
168    } 
169    else {
170        // if its not an exact match then update chunk base and length
171        heap_ll * tmp_chunk = victim;
172        victim = (heap_ll *) (((unsigned int) victim) + (size_align + 4));
173#if DEBUG_MALLOC == 1
174        giet_tty_printf("NEXT CHUNK is at @ : 0x%x + 0x%x = 0x%x\n",
175                (unsigned int) tmp_chunk,
176                (unsigned int) ((size_align + 4) / 4),
177                (unsigned int) victim);
178#endif
179
180        victim->chunk_length = tmp_chunk->chunk_length - (size_align + 4);
181        victim->next = tmp_chunk->next;
182        if (prev_victim == 0x0) {
183            _heap_head[task_id] = victim;
184        }
185        else {
186            prev_victim->next = victim;
187        }
188    }
189
190    /****** Write Overhead ******/
191    *((unsigned int *) victim_vbase) = size_align;      // writing overhead on the first word
192#if DEBUG_MALLOC == 1
193    giet_tty_printf("BLOCK SUCCESSFULLY ALLOCATED at @ 0x%x user will write at @ 0x%x\n\n"\
194            ,(unsigned int)(victim_vbase),(unsigned int) (victim_vbase + 4));
195#endif
196    return (unsigned int *) (victim_vbase + 4);
197}
198
199
200
201/* this function tries to merge the block to free with chunks in the list if
202 * they are contiguous
203 * the block can be merged two times.
204 */
205void update_chunk_list(unsigned int block_base, unsigned int block_length) {
206    /* entire heap is allocated : create a new block of size block_length and give it to the head  */
207    int task_id = giet_global_task_id();
208    if (_heap_head[task_id] == 0x0) {
209        ((heap_ll *) block_base)->chunk_length = block_length;
210        ((heap_ll *) block_base)->next = 0x0;
211        _heap_head[task_id] = ((heap_ll *) block_base);
212#if DEBUG_MALLOC == 1
213        giet_tty_printf("****** NEW BLOCK ******\n"
214                "@ : %x\n"
215                "Length : %d o\n"
216                "***********************\n",
217                block_base,
218                (unsigned int) (((heap_ll *) block_base)->chunk_length));
219#endif
220        return;
221    }
222
223
224    /* Test for each Chunk in my list if the block can be merged with */
225    heap_ll *ptr_to_chunk_list = _heap_head[task_id]; // move through the list
226    heap_ll *prev = 0x0; // pointer on the previous visited chunk in the list
227    heap_ll *prev_block_base = 0x0; // pointer on the previous chunk of the chunk that contains the merged block in the list
228    unsigned int chunk_length;
229    int block_merged = 0; // =1 when the block has already been merged with a chunk in the list
230    while (ptr_to_chunk_list != 0x0) {
231        chunk_length = ptr_to_chunk_list->chunk_length;
232        /*  [.....|ptr|block|.....] */
233        if ((unsigned int) (ptr_to_chunk_list) + chunk_length == block_base) {
234#if DEBUG_MALLOC == 1
235            giet_tty_printf("****** BLOCK MERGED ******\n"
236                    "CHUNK : %x of size %d o\n"
237                    "merged with \n"
238                    "BLOCK : %x of size %d o\n"
239                    "***********************\n",
240                    (unsigned int) ptr_to_chunk_list,
241                    ptr_to_chunk_list->chunk_length, block_base,
242                    block_length);
243#endif
244
245            /* update the size */
246            ptr_to_chunk_list->chunk_length = chunk_length + block_length;
247
248            /* [.....|ptr|[block|old_ptr]|.....]
249             *  remove ptr from the list
250             *  update next pointer
251             *  update the previous chunk of block base to point to ptr
252             */
253            if (block_merged == 1) {
254                prev->next = ptr_to_chunk_list->next;
255                ptr_to_chunk_list->next = ((heap_ll *) block_base)->next;
256                if (prev_block_base != 0x0) {
257                    prev_block_base->next = ptr_to_chunk_list;
258                }
259                else {
260                    _heap_head[task_id] = ptr_to_chunk_list;
261                }
262            }
263            /****** for next turn ******/
264            block_base = (unsigned int) ptr_to_chunk_list;
265            block_length = ptr_to_chunk_list->chunk_length;
266#if DEBUG_MALLOC == 1
267            giet_tty_printf("****** NEW BLOCK ******\n"
268                    "@ : %x\n"
269                    "Length : %d o\n"
270                    "***********************\n",
271                    (unsigned int) ptr_to_chunk_list,
272                    (unsigned int) (ptr_to_chunk_list->chunk_length));
273#endif
274            prev_block_base = prev;
275            prev = ptr_to_chunk_list;
276            ptr_to_chunk_list = ptr_to_chunk_list->next;
277            block_merged = 1;
278            continue;
279
280        } // end [.....|ptr|block|.....]
281        /*  [......|block|ptr|.....] */
282        if (block_base + block_length == (unsigned int) ptr_to_chunk_list) {
283#if DEBUG_MALLOC == 1
284            giet_tty_printf("****** BLOCK MERGED ******\n"
285                    "BLOCK : %x of size %d o\n"
286                    "merged with \n"
287                    "CHUNK : %x of size %d o\n"
288                    "***********************\n",
289                    block_base, block_length,
290                    (unsigned int) ptr_to_chunk_list,
291                    ptr_to_chunk_list->chunk_length);
292#endif
293
294            /* update the size */
295            ((heap_ll *) block_base)->chunk_length = block_length + chunk_length;
296
297            /* [.....|block|ptr|......] */
298            if (block_merged == 0) {
299                /* update next pointer
300                 *  update the previous chunk of ptr to point to block_base
301                 */
302                ((heap_ll *) block_base)->next = ptr_to_chunk_list->next;
303                if (prev == 0x0) {
304                    _heap_head[task_id] = ((heap_ll *) block_base);
305                }
306                else {
307                    prev->next = ((heap_ll *) block_base);
308                }
309            }
310            /* [.....[old_ptr|block]|ptr|......] */
311            else {
312                /* remove ptr from the list */
313                prev->next = ptr_to_chunk_list->next;
314            }
315
316            ptr_to_chunk_list = ((heap_ll *) block_base);
317            block_length = ptr_to_chunk_list->chunk_length;
318#if DEBUG_MALLOC == 1
319            giet_tty_printf("****** NEW BLOCK ******\n"
320                    "@ : %x\n"
321                    "Length : %d o\n"
322                    "***********************\n",
323                    (unsigned int) ptr_to_chunk_list,
324                    (unsigned int) (ptr_to_chunk_list->chunk_length));
325#endif
326            prev_block_base = prev;
327            block_merged = 1;
328        } // end [......|block|ptr|.....]
329        prev = ptr_to_chunk_list;
330        ptr_to_chunk_list = ptr_to_chunk_list->next;
331    } // end while
332    if (block_merged == 1) {
333        return;
334    }
335    /* if the block cant be merge
336     *  create new block and add it to the end of the list
337     */
338    ((heap_ll *) block_base)->chunk_length = block_length;
339    ((heap_ll *) block_base)->next = 0x0;
340    prev->next = ((heap_ll *) block_base);
341#if DEBUG_MALLOC == 1
342    giet_tty_printf("****** NEW BLOCK ******\n"
343            "@ : %x\n"
344            "Length : %d o\n"
345            "***********************\n",
346            block_base,
347            (unsigned int) (((heap_ll *) block_base)->chunk_length));
348#endif
349    return;
350
351}
352
353
354static void print_all_heap(void) {
355    int task_id = giet_global_task_id();
356    heap_ll * ptr_to_chunk_list = _heap_head[task_id];
357    giet_tty_printf("################### PRINT ALL HEAP ######################\n");
358    while (ptr_to_chunk_list != 0x0) {
359        giet_tty_printf("CHUNK at @ : %x\n"
360                "OVERHEAD : %d\n"
361                "NEXT : %x\n\n",
362                (unsigned int) ptr_to_chunk_list,
363                ptr_to_chunk_list->chunk_length,
364                (unsigned int) ptr_to_chunk_list->next);
365        ptr_to_chunk_list = ptr_to_chunk_list->next;
366    }
367    giet_tty_printf("#########################################################\n");
368}
369
370
371/* Warning: the division doesn't seem to work well in the giet/soclib ? */
372static void frag(int turn) {
373    int task_id = giet_global_task_id();
374    int nb_blocks = 0;
375    int size = 0;
376    heap_ll * ptr_to_chunk;
377    ptr_to_chunk = _heap_head[task_id];
378    while(ptr_to_chunk != 0x0) {
379        size += ptr_to_chunk->chunk_length;
380        nb_blocks += 1;
381        ptr_to_chunk = ptr_to_chunk->next;
382    }
383    if (size != 0) {
384        giet_tty_printf("%.3f\t%d\n", size / ((double) nb_blocks), turn);
385    }
386}
387
388// End WORST_FIT
389#elif MALLOC_SELECTED == 2 // Next Fit
390
391heap_ll * get_prev_fit_chunk(unsigned int size) {
392    int task_id = giet_global_task_id();
393    if (_heap_head[task_id] == 0x0) {
394        return ((heap_ll *) 0x1);
395    }
396
397    heap_ll * ptr_to_chunk_list;
398    heap_ll * prev = 0x0;
399    heap_ll * tmp_turn = 0x0;
400
401    if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
402        ptr_to_chunk_list = _heap_head[task_id];
403    }
404    else
405    {
406        ptr_to_chunk_list = _prev_next_last_allocted[task_id]->next;
407    }
408
409    tmp_turn = (ptr_to_chunk_list == 0x0)?_heap_head[task_id]:ptr_to_chunk_list;
410    do {
411        if (ptr_to_chunk_list == 0x0) {
412            // simulate circular list
413            ptr_to_chunk_list = _heap_head[task_id];
414            if (ptr_to_chunk_list == tmp_turn) break;
415        }
416
417        if (size <= ptr_to_chunk_list->chunk_length) {
418            return prev;
419        }
420        prev = ptr_to_chunk_list;
421        ptr_to_chunk_list = ptr_to_chunk_list->next;
422    } while (ptr_to_chunk_list != tmp_turn);
423
424    return (heap_ll *) 0x1;
425}
426
427
428void * malloc(unsigned int size) {
429
430    int task_id = giet_global_task_id();
431#if DEBUG_MALLOC == 1
432    giet_tty_giet_tty_printf("############ MALLOC ############\n\n");
433#endif
434    if (size == 0) {
435#if DEBUG_MALLOC == 1
436        giet_tty_giet_tty_printf(" SIZE = 0 \n");
437#endif
438        return 0x0;
439    }
440
441    /****** First call to malloc ******/
442    if (_first_malloc[task_id] == 0) {
443        giet_heap_info(&_heap_base[task_id], &_heap_length[task_id]);
444
445        if (_heap_length[task_id] == 0) {
446            giet_tty_printf("*** Error: Malloc called in task %d while no heap was defined.\n", task_id);
447            return 0x0;
448        }
449
450        _heap_head[task_id] = (heap_ll *) _heap_base[task_id];
451        _heap_head[task_id]->chunk_length = _heap_length[task_id];
452        _heap_head[task_id]->next = 0x0;
453
454        _prev_next_last_allocted[task_id] = 0x0;
455
456        _first_malloc[task_id] = 1;
457    }
458
459    /****** Size align ******/
460    int size_align = size;
461    if (size % 4 != 0) {
462        size_align = ((size / 4) + 1) * 4;
463    }
464
465
466#if DEBUG_MALLOC == 1
467    giet_tty_giet_tty_printf("Looking for size : %d\n", size_align + 4);
468#endif
469    /****** Get prev victim from the chunks list ******/
470    heap_ll *victim;
471    heap_ll *prev_victim;
472
473    if ((prev_victim = get_prev_fit_chunk(size_align + 4)) == (heap_ll *) 0x1) {
474        return 0x0;             // no chunk of this size avaiable, 0x1 : no suitable chunk found
475    }
476    else {
477        if (prev_victim != 0x0) {
478            // victim != _next_last_allocted
479            if (prev_victim->next == 0x0) {
480                // victim == HEAD
481                victim = _heap_head[task_id];
482            }
483            else {
484                victim = prev_victim->next;
485            }
486        }
487        else
488        {
489            if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
490                victim =_heap_head[task_id];
491            }
492            else {
493                victim = _prev_next_last_allocted[task_id]->next;
494            }
495        }
496    }
497
498    /****** Get Victim Base ******/
499    unsigned int victim_vbase = (unsigned int) victim; // overhead
500
501    /****** update the chunks list ******/
502    if (victim->chunk_length - (size_align + 4) < 8) {
503        // if it is an exact match
504        size_align = size_align + (victim->chunk_length - (size_align + 4));
505
506        if (prev_victim == 0x0) {
507            // if victim == head
508            if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
509                _heap_head[task_id] = victim->next;
510            }
511            else {
512                _prev_next_last_allocted[task_id]->next = victim->next;
513            }
514            _prev_next_last_allocted[task_id] = victim->next;
515        }
516        else {
517            if (prev_victim->next == 0x0) {
518                _heap_head[task_id] = victim->next;
519            }
520            else {
521                prev_victim->next = victim->next;
522            }
523            _prev_next_last_allocted[task_id] = prev_victim;
524        }
525    } 
526    else {
527        // if its not an exact match then update chunk base and length
528        heap_ll * tmp_chunk = victim;
529        victim = (heap_ll *) (((unsigned int) victim) + (size_align + 4));
530#if DEBUG_MALLOC == 1
531        giet_tty_giet_tty_printf("NEXT CHUNK is at @ : 0x%x + 0x%x = 0x%x\n",
532                (unsigned int) tmp_chunk,
533                (unsigned int) ((size_align + 4) / 4),
534                (unsigned int) victim);
535#endif
536
537        victim->chunk_length = tmp_chunk->chunk_length - (size_align + 4);
538        victim->next = tmp_chunk->next;
539        if (prev_victim == 0x0) {
540            if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
541                _heap_head[task_id] = victim;
542            }
543            else {
544                _prev_next_last_allocted[task_id]->next = victim;
545            }
546            _prev_next_last_allocted[task_id] = victim->next;
547        }
548        else {
549            if (prev_victim->next == 0x0) {
550                _heap_head[task_id] = victim;
551            }
552            else {
553                prev_victim->next = victim;
554            }
555            _prev_next_last_allocted[task_id] = prev_victim;
556        }
557    }
558
559    /****** Write Overhead ******/
560    *((unsigned int *) victim_vbase) = size_align;      // writing overhead on the first word
561#if DEBUG_MALLOC == 1
562    giet_tty_giet_tty_printf("BLOCK SUCCESSFULLY ALLOCATED at @ 0x%x user will write at @ 0x%x\n\n"\
563            ,(unsigned int)(victim_vbase),(unsigned int )(victim_vbase + 4));
564#endif
565    return (unsigned int *) (victim_vbase + 4);
566}
567
568
569
570/* this function tries to merge the block to free with chunks in the list if they are contiguous
571 * the block can be merged two times.
572 */
573
574void update_chunk_list(unsigned int block_base, unsigned int block_length) {
575    int task_id = giet_global_task_id();
576    /* entire heap is allocated : create a new block of size block_length and give it to the head  */
577    if (_heap_head[task_id] == 0x0) {
578        ((heap_ll *) block_base)->chunk_length = block_length;
579        ((heap_ll *) block_base)->next = 0x0;
580        _heap_head[task_id] = ((heap_ll *) block_base);
581#if DEBUG_MALLOC == 1
582        giet_tty_giet_tty_printf("****** NEW BLOCK ******\n"
583                "@ : %x\n"
584                "Length : %d o\n"
585                "***********************\n",
586                block_base,
587                (unsigned int) (((heap_ll *) block_base)->chunk_length));
588#endif
589        return;
590    }
591
592    /* Test for each Chunk in my list if the block can be merged with */
593    heap_ll * ptr_to_chunk_list = _heap_head[task_id]; // move through the list
594    heap_ll * prev = 0x0; // pointer on the previous visited chunk in the list
595    heap_ll * prev_block_base = 0x0; // pointer on the previous chunk of the chunk that contains the merged block in the list
596    unsigned int chunk_length;
597    int block_merged = 0; // =1 when the block has already been merged with a chunk in the list
598    while (ptr_to_chunk_list != 0x0) {
599        chunk_length = ptr_to_chunk_list->chunk_length;
600        /*  [.....|ptr|block|.....] */
601        if ((unsigned int) (ptr_to_chunk_list) + chunk_length == block_base) {
602#if DEBUG_MALLOC == 1
603            giet_tty_giet_tty_printf("****** BLOCK MERGED ******\n"
604                    "CHUNK : %x of size %d o\n"
605                    "merged with \n"
606                    "BLOCK : %x of size %d o\n"
607                    "***********************\n",
608                    (unsigned int) ptr_to_chunk_list,
609                    ptr_to_chunk_list->chunk_length, block_base,
610                    block_length);
611#endif
612            if (_prev_next_last_allocted[task_id] == ptr_to_chunk_list) {
613                _prev_next_last_allocted[task_id] = ptr_to_chunk_list->next;
614            }
615
616            /* update the size */
617            ptr_to_chunk_list->chunk_length = chunk_length + block_length;
618
619            /* [.....|ptr|[block|old_ptr]|.....]
620             *  remove ptr from the list
621             *  update next pointer
622             *  update the previous chunk of block base to point to ptr
623             */
624            if (block_merged == 1) {
625                prev->next = ptr_to_chunk_list->next;
626                ptr_to_chunk_list->next = ((heap_ll *) block_base)->next;
627
628                if (prev_block_base != 0x0) {
629                    prev_block_base->next = ptr_to_chunk_list;
630                }
631                else {
632                    _heap_head[task_id] = ptr_to_chunk_list;
633                }
634            }
635            /****** for next turn ******/
636            block_base = (unsigned int) ptr_to_chunk_list;
637            block_length = ptr_to_chunk_list->chunk_length;
638#if DEBUG_MALLOC == 1
639            giet_tty_giet_tty_printf("****** NEW BLOCK ******\n"
640                    "@ : %x\n"
641                    "Length : %d o\n"
642                    "***********************\n",
643                    (unsigned int) ptr_to_chunk_list,
644                    (unsigned int) (ptr_to_chunk_list->chunk_length));
645#endif
646            prev_block_base = prev;
647            prev = ptr_to_chunk_list;
648            ptr_to_chunk_list = ptr_to_chunk_list->next;
649            block_merged = 1;
650            continue;
651
652        } // end [.....|ptr|block|.....]
653        /*  [......|block|ptr|.....] */
654        if (block_base + block_length == (unsigned int) ptr_to_chunk_list) {
655#if DEBUG_MALLOC == 1
656            giet_tty_giet_tty_printf("****** BLOCK MERGED ******\n"
657                    "BLOCK : %x of size %d o\n"
658                    "merged with \n"
659                    "CHUNK : %x of size %d o\n"
660                    "***********************\n",
661                    block_base, block_length,
662                    (unsigned int) ptr_to_chunk_list,
663                    ptr_to_chunk_list->chunk_length);
664#endif
665
666            if (_prev_next_last_allocted[task_id] == ptr_to_chunk_list) {
667                _prev_next_last_allocted[task_id] = ptr_to_chunk_list->next;
668            }
669
670            /* update the size */
671            ((heap_ll *) block_base)->chunk_length = block_length + chunk_length;
672
673            /* [.....|block|ptr|......] */
674            if (block_merged == 0) {
675                /* update next pointer
676                 *  update the previous chunk of ptr to point to block_base
677                 */
678                ((heap_ll *) block_base)->next = ptr_to_chunk_list->next;
679                if (prev == 0x0) {
680                    _heap_head[task_id] = ((heap_ll *) block_base);
681                }
682                else {
683                    prev->next = ((heap_ll *) block_base);
684                }
685            }
686            /* [.....[old_ptr|block]|ptr|......] */
687            else {
688                /* remove ptr from the list */
689                prev->next = ptr_to_chunk_list->next;
690                if (prev_block_base != 0x0) {
691                    prev_block_base->next = ((heap_ll *)block_base);
692                }
693                else {
694                    _heap_head[task_id] = ((heap_ll *)block_base);
695                }
696            }
697
698            ptr_to_chunk_list = ((heap_ll *) block_base);
699            block_length = ptr_to_chunk_list->chunk_length;
700#if DEBUG_MALLOC == 1
701            giet_tty_giet_tty_printf("****** NEW BLOCK ******\n"
702                    "@ : %x\n"
703                    "Length : %d o\n"
704                    "***********************\n",
705                    (unsigned int) ptr_to_chunk_list,
706                    (unsigned int) (ptr_to_chunk_list->chunk_length));
707#endif
708            prev_block_base = prev;
709            block_merged = 1;
710        } // end [......|block|ptr|.....]
711
712        prev = ptr_to_chunk_list;
713        ptr_to_chunk_list = ptr_to_chunk_list->next;
714    } // end while
715
716    if (block_merged == 1) {
717        return;
718    }
719
720    /* if the block cant be merge
721     *  create new block and add it to the end of the list
722     */
723    ((heap_ll *) block_base)->chunk_length = block_length;
724    ((heap_ll *) block_base)->next = 0x0;
725    prev->next = ((heap_ll *) block_base);
726
727#if DEBUG_MALLOC == 1
728    giet_tty_giet_tty_printf("****** NEW BLOCK ******\n"
729            "@ : %x\n"
730            "Length : %d o\n"
731            "***********************\n",
732            block_base,
733            (unsigned int) (((heap_ll *) block_base)->chunk_length));
734#endif
735    return;
736}
737
738
739void print_all_heap(void) {
740    int task_id = giet_global_task_id();
741    heap_ll * ptr_to_chunk_list = _heap_head[task_id];
742    giet_tty_printf("################### PRINT ALL HEAP ######################\n");
743    while (ptr_to_chunk_list != 0x0) {
744        giet_tty_printf("CHUNK at @ : %x\n"
745                "OVERHEAD : %d\n"
746                "NEXT : %x\n\n",
747                (unsigned int) ptr_to_chunk_list,
748                ptr_to_chunk_list->chunk_length,
749                (unsigned int) ptr_to_chunk_list->next);
750        ptr_to_chunk_list = ptr_to_chunk_list->next;
751    }
752    giet_tty_printf("#########################################################\n");
753}
754
755
756void frag(int turn) {
757    int task_id = giet_global_task_id();
758    int nb_blocks = 0;
759    int size = 0;
760    heap_ll * ptr_to_chunk;
761    ptr_to_chunk = _heap_head[task_id];
762    while (ptr_to_chunk != 0x0) {
763        size += ptr_to_chunk->chunk_length;
764        nb_blocks += 1;
765        ptr_to_chunk = ptr_to_chunk->next;
766    }
767    //   assert(size != 0 || nb_blocks == 0);
768    if (size != 0) {
769        giet_tty_printf("%.3f\t%d\n", size / ((double) nb_blocks), turn);
770    }
771}
772
773
774
775
776#else // Default case : New Fit
777
778
779int get_prev_fit_chunk(unsigned int size) {
780    int task_id = giet_global_task_id();
781    int index = GET_TAB_INDEX(size);
782    while (index != MAX_SIZE_POW2_TAB) {
783        if (_pow2tab[task_id][index] != 0x0) {
784            return index;
785        }
786        index++;
787    }
788    return -1;
789}
790
791
792
793void * malloc(unsigned int size) {
794    int task_id = giet_global_task_id();
795#if DEBUG_MALLOC == 1
796    giet_tty_printf("############ MALLOC ############\n\n");
797#endif
798    if(size == 0) {
799#if DEBUG_MALLOC == 1
800        giet_tty_printf(" SIZE = 0 \n");
801#endif
802        return 0x0;
803    }
804    if (size > 0x20000000) {
805#if DEBUG_MALLOC == 1
806        giet_tty_printf("ERROR max size = %d\n",0x20000000); 
807#endif
808        return 0x0;
809    }
810    if (size < 8) {
811        size = 8;
812    }
813
814    /****** First call to malloc ******/
815    if (_first_malloc[task_id] == 0) {
816        giet_heap_info(&_heap_base[task_id], &_heap_length[task_id]);
817
818        if (_heap_length[task_id] == 0) {
819            giet_tty_printf("*** Error: Malloc called in task %d while no heap was defined.\n", task_id);
820            return 0x0;
821        }
822
823        int index = GET_TAB_INDEX(_heap_length[task_id]);
824
825        _pow2tab[task_id][index] = (heap_ll *) _heap_base[task_id];
826        _pow2tab[task_id][index]->chunk_length = _heap_length[task_id];
827        _pow2tab[task_id][index]->next = 0x0;
828
829        *((unsigned int *) ((_heap_base[task_id] +_heap_length[task_id]) - 4))     = _heap_length[task_id];
830
831        _first_malloc[task_id] = 1;
832    }
833
834    /****** Size align ******/
835    int size_align = size;
836    if (size % 4 != 0) {
837        size_align = ((size / 4) + 1) * 4;
838    }
839
840#if DEBUG_MALLOC == 1
841    giet_tty_printf("Looking for size : %d %d = %d\n", size_align, 4,size_align+4);
842#endif
843
844
845    /****** Get tab index of the victim from the chunks list ******/
846    heap_ll * victim;
847    int index;
848    if ((index = get_prev_fit_chunk(size_align + 4)) == -1) {
849        return 0x0;
850    }
851    victim = _pow2tab[task_id][index];
852
853    /****** Get Victim Base ******/
854    unsigned int victim_vbase = (unsigned int) victim;  // overhead
855
856
857    /****** update the chunks list ******/
858    _pow2tab[task_id][index] = _pow2tab[task_id][index]->next;
859
860    if ((victim->chunk_length - (size_align + 4)) < 12) {
861        size_align = size_align + (victim->chunk_length - (size_align + 4)); 
862    } 
863    else {
864        // if its not an exact match then update chunk base and length
865        unsigned int new_size = victim->chunk_length - (size_align + 4); // get the new size;
866        unsigned int new_index = GET_TAB_INDEX(new_size);                 // get the new index;
867        heap_ll * new_chunk = (heap_ll *) (((unsigned int) victim) + (size_align + 4)); //update new_chunk @
868        new_chunk->chunk_length = new_size;                                // write new size
869        *((unsigned int *) ((unsigned int) new_chunk + new_size - 4)) = new_size;                                // on both side of the block
870        new_chunk->next = _pow2tab[task_id][new_index];                     // insert new_chunk @ the new index
871        _pow2tab[task_id][new_index] = new_chunk;
872
873#if DEBUG_MALLOC == 1
874        giet_tty_printf("NEXT CHUNK is at @ : 0x%x + 0x%x = 0x%x : @ of size over the block : %x\n",
875                (unsigned int) victim,
876                (unsigned int) ((size_align + 4) / 4),
877                (unsigned int) new_chunk,
878                ((unsigned int) new_chunk + new_chunk->chunk_length) - 4);
879#endif
880    }
881
882    /****** Write Overhead ******/
883    *((unsigned int *) victim_vbase) = size_align;      // writing overhead on the first word
884#if DEBUG_MALLOC == 1
885    giet_tty_printf("BLOCK SUCCESSFULLY ALLOCATED at @ 0x%x user will write at @ 0x%x\n\n",\
886            (unsigned int)(victim_vbase), (unsigned int ) (victim_vbase + 4));
887#endif
888
889    return (unsigned int *) (victim_vbase + 4);
890}
891
892
893
894/* this function tries to merge the block to free with chunks in the list if they are contiguous
895 * the block can be merged two times.
896 */
897void update_chunk_list(unsigned int block_base, unsigned int block_length) {
898    int task_id = giet_global_task_id();
899
900    int left_merging               = 0;
901    unsigned int left_block_size   = 0;
902    unsigned int left_block_index  = 0;
903    heap_ll * left_block_addr      = 0x0;
904
905    int right_merging              = 0;
906    unsigned int right_block_size  = 0; 
907    unsigned int right_block_index = 0;
908    heap_ll * right_block_addr     = 0x0;
909
910    if (block_base - 4 >= _heap_base[task_id]) {
911
912#if DEBUG_MALLOC == 1
913        giet_tty_printf("############# LEFT MERGE #############\n\n");
914#endif
915        left_block_size = *((unsigned int *) (block_base - 4));
916        left_block_index = GET_TAB_INDEX(left_block_size);
917        left_block_addr = (heap_ll *)(block_base - left_block_size);
918        left_merging = 1;
919    }
920
921    if ((block_base + block_length) <= (_heap_base[task_id] + _heap_length[task_id]) - 8) {
922#if DEBUG_MALLOC == 1
923        giet_tty_printf("############# RIGHT MERGE #############\n\n");
924#endif
925        right_block_size = ((heap_ll *)(block_base + block_length))->chunk_length;
926        right_block_index = GET_TAB_INDEX(right_block_size);
927        right_block_addr = (heap_ll *) (block_base + block_length);
928        right_merging = 1;
929    }
930
931#if DEBUG_MALLOC == 1
932    giet_tty_printf("############# END PREP MERGE #############\n\n");
933#endif
934
935    heap_ll * ptr_to_chunk = 0x0;
936    heap_ll * prev_ptr_to_chunk = 0x0;
937
938    heap_ll * ptr_to_chunk_right = 0x0;
939    heap_ll * prev_ptr_to_chunk_right = 0x0;
940
941    unsigned int new_size = block_length;
942    unsigned int new_index = 0;
943    int merged_left = 0;
944    heap_ll * new_addr = 0x0;
945
946
947
948    /* try to merge with left block */
949    if (left_merging == 1 &&
950            (unsigned int) left_block_addr >= _heap_base[task_id] &&
951            (unsigned int) left_block_addr <= block_base - 12) {
952        ptr_to_chunk = _pow2tab[task_id][left_block_index];
953        while (ptr_to_chunk != 0x0) {
954            if (ptr_to_chunk == left_block_addr && ptr_to_chunk->chunk_length == left_block_size) {
955                new_size = new_size + left_block_size;
956                if (prev_ptr_to_chunk == 0x0) {
957                    _pow2tab[task_id][left_block_index] = ptr_to_chunk->next;
958                }
959                else {
960                    prev_ptr_to_chunk->next = ptr_to_chunk->next;
961                }
962                merged_left = 1;
963                break;
964            }
965            else if (ptr_to_chunk == right_block_addr && ptr_to_chunk->chunk_length == right_block_size) {
966                ptr_to_chunk_right = ptr_to_chunk;
967                prev_ptr_to_chunk_right = prev_ptr_to_chunk;
968            }
969            prev_ptr_to_chunk = ptr_to_chunk;
970            ptr_to_chunk = ptr_to_chunk->next;
971        }
972    }
973
974    if (right_block_index != left_block_index) {
975        prev_ptr_to_chunk = 0x0;
976        ptr_to_chunk = _pow2tab[task_id][right_block_index];
977    }
978    else {
979        ptr_to_chunk = ptr_to_chunk_right;
980        prev_ptr_to_chunk = prev_ptr_to_chunk_right;
981    }
982
983    /* try to merge with right block */
984    if (right_merging == 1 &&
985            (unsigned int) right_block_addr >= block_base + block_length &&
986            (unsigned int) right_block_addr <= (_heap_base[task_id] + _heap_length[task_id]) - 12) {
987        while (ptr_to_chunk != 0x0) {
988            if (ptr_to_chunk == right_block_addr && ptr_to_chunk->chunk_length == right_block_size) {
989                new_size = new_size + right_block_size;
990                if (prev_ptr_to_chunk == 0x0) {
991                    _pow2tab[task_id][right_block_index] = ptr_to_chunk->next;
992                }
993                else {
994                    prev_ptr_to_chunk->next = ptr_to_chunk->next;
995                }
996                break;
997            }
998            prev_ptr_to_chunk = ptr_to_chunk;
999            ptr_to_chunk = ptr_to_chunk->next;
1000        }
1001    }
1002    new_index = GET_TAB_INDEX(new_size);
1003    if (merged_left == 1) {
1004        new_addr = (heap_ll *) (block_base - left_block_size);
1005    }
1006    else {
1007        new_addr = (heap_ll *) block_base;
1008    }
1009    new_addr->chunk_length = new_size;
1010    *((unsigned int *) ((unsigned int) new_addr + (new_addr->chunk_length - 4))) = new_size;
1011    new_addr->next = _pow2tab[task_id][new_index];
1012    _pow2tab[task_id][new_index] = new_addr;
1013
1014    return;
1015}
1016
1017
1018static void print_all_heap(void) {
1019    int task_id = giet_global_task_id();
1020    int i = 0;
1021    int nb_blocks = 0;
1022    heap_ll * ptr_to_chunk_list;
1023    giet_tty_printf("################### PRINT ALL HEAP ######################\n");
1024    while (i != MAX_SIZE_POW2_TAB) {
1025        ptr_to_chunk_list = _pow2tab[task_id][i];
1026
1027        if (ptr_to_chunk_list != 0x0) {
1028            giet_tty_printf("###################### %d ####################\n", i);
1029        }
1030        while (ptr_to_chunk_list != 0x0) {
1031            giet_tty_printf("CHUNK at @ : %x\n"
1032                    "OVERHEAD : %d\n"
1033                    "NEXT : %x\n\n",
1034                    (unsigned int) ptr_to_chunk_list,
1035                    ptr_to_chunk_list->chunk_length,
1036                    (unsigned int) ptr_to_chunk_list->next);
1037            ptr_to_chunk_list = ptr_to_chunk_list->next;
1038            nb_blocks++;
1039        }
1040        i++;
1041    }
1042    giet_tty_printf("####################### ##%d## ##########################\n", nb_blocks);
1043}
1044
1045
1046static void frag(int turn) {
1047    int task_id = giet_global_task_id();
1048    int i = 0;
1049    int nb_blocks = 0;
1050    int size = 0;
1051    heap_ll * ptr_to_chunk;
1052    while (i != MAX_SIZE_POW2_TAB) {
1053        ptr_to_chunk = _pow2tab[task_id][i];
1054        while (ptr_to_chunk != 0x0) {
1055            size += ptr_to_chunk->chunk_length;
1056            nb_blocks += 1;
1057            ptr_to_chunk = ptr_to_chunk->next;
1058        }
1059        i++;
1060    }
1061    if (size != 0) {
1062        giet_tty_printf("%.3f\t%d\n",size / ((double) nb_blocks), turn);
1063    }
1064}
1065
1066
1067
1068#endif // New Fit
1069
1070
1071void free(void * ptr) {
1072    int task_id = giet_global_task_id();
1073    unsigned int * to_free = ptr;
1074    unsigned int heapB = _heap_base[task_id];
1075    unsigned int heapL = _heap_length[task_id];
1076    unsigned int overhead;
1077    unsigned int block_base;
1078    unsigned int block_length;
1079
1080#if DEBUG_MALLOC == 1
1081    giet_tty_printf("############# FREE  #############\n\n");
1082#endif
1083    /****** CHECK PTR ******/
1084    if (to_free == 0x0) {
1085#if DEBUG_MALLOC == 1
1086        giet_tty_printf("free == 0x0\n");
1087#endif
1088        return;
1089    }
1090    // check alignement of ptr
1091    if (((unsigned int) to_free) % 4 != 0) {
1092#if DEBUG_MALLOC == 1
1093        giet_tty_printf("allignement of ptr  %x = %d\n", (unsigned int) to_free, (unsigned int) to_free % 4);
1094#endif
1095        return;
1096    }
1097    // check if the @ of ptr matches the range of the heap
1098    if (!((unsigned int) to_free >= heapB && (unsigned int) to_free < heapB + heapL)) {
1099#if DEBUG_MALLOC == 1
1100        giet_tty_printf("check if it matches the range of the heap\n");
1101#endif
1102        return;
1103    }
1104
1105    // get the 4 bytes before the ptr that contains the size of the block
1106    overhead = *(to_free - 1);
1107    // check alignement of overhead
1108    if (overhead % 4 != 0) {
1109#if DEBUG_MALLOC == 1
1110        giet_tty_printf("check alignement of overhead\n");
1111#endif
1112        return;
1113    }
1114    // check if (overhead + to_free) matches the range of the heap
1115    if ((((unsigned int) (to_free) + overhead) - 4) > heapB + heapL) {
1116#if DEBUG_MALLOC == 1
1117        giet_tty_printf ("check if (overhead + to_free) matches the range of the heap\n");
1118#endif
1119        return;
1120    }
1121
1122    block_base = (unsigned int) (to_free - 1);
1123    block_length = overhead + 4;
1124
1125#if DEBUG_MALLOC == 1
1126    giet_tty_printf("############# UPDATE CL :  FREE %x of size %d #############\n\n",block_base, block_length);
1127#endif
1128    update_chunk_list(block_base, block_length);
1129
1130#if DEBUG_MALLOC == 1
1131    giet_tty_printf("BLOCK SUCCESSFULLY FREED\n\n");
1132#endif
1133
1134    return;
1135}
1136
1137
1138
1139
1140
1141
1142// Local Variables:
1143// tab-width: 4
1144// c-basic-offset: 4
1145// c-file-offsets:((innamespace . 0)(inline-open . 0))
1146// indent-tabs-mode: nil
1147// End:
1148// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
1149
1150
1151
Note: See TracBrowser for help on using the repository browser.