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

Last change on this file since 313 was 258, checked in by alain, 11 years ago

This is a major release, including a deep restructuration of code.
The main evolutions are

  • use of the Tsar preloader to load the GIET boot-loader from disk
  • introduction of a FAT32 file system library,
  • use of this fat32 library by the boot-loader to load the map.bin data structure, and the various .elf files
  • reorganisation of drivers (one file per peripheral).
  • introduction of drivers for new peripherals: vci_chbuf_dma and vci_multi_ahci.
  • introduction of a new physical memory allocator in the boot code.

This release has been tested on the tsar_generic_iob architecture,
for the two following mappings: 4c_1p_iob_four.xml and 4c_1p_iob_sort.xml

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