source: soft/giet_vm/giet_libs/malloc.c @ 343

Last change on this file since 343 was 325, checked in by alain, 10 years ago

heu...

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