Context Navigation

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

Last change on this file since 238 was 233, checked in by meunier, 12 years ago
Added the malloc files, forgotten at the previous commit...
File size: 38.3 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: