1 /*
2 * malloc.c
3 *
4 * Very simple linked-list based malloc()/free().
5 */
6
7 #include <stdlib.h>
8 #include <string.h>
9 #include "malloc.h"
10
11 struct free_arena_header __malloc_head = {
12 {
13 ARENA_TYPE_HEAD,
14 0,
15 &__malloc_head,
16 &__malloc_head,
17 },
18 &__malloc_head,
19 &__malloc_head
20 };
21
22 extern void *__mem_end; /* In argv.c */
23
__init_memory_arena(void)24 void __init_memory_arena(void)
25 {
26 extern char __heap_end[];
27 struct free_arena_header *fp;
28
29 fp = (struct free_arena_header *)__mem_end;
30 fp->a.type = ARENA_TYPE_FREE;
31 fp->a.size = __heap_end - (char *)__mem_end;
32
33 /* Insert into chains */
34 fp->a.next = fp->a.prev = &__malloc_head;
35 fp->next_free = fp->prev_free = &__malloc_head;
36 __malloc_head.a.next = __malloc_head.a.prev = fp;
37 __malloc_head.next_free = __malloc_head.prev_free = fp;
38 }
39
__malloc_from_block(struct free_arena_header * fp,size_t size)40 static void *__malloc_from_block(struct free_arena_header *fp, size_t size)
41 {
42 size_t fsize;
43 struct free_arena_header *nfp, *na;
44
45 fsize = fp->a.size;
46
47 /* We need the 2* to account for the larger requirements of a free block */
48 if (fsize >= size + 2 * sizeof(struct arena_header)) {
49 /* Bigger block than required -- split block */
50 nfp = (struct free_arena_header *)((char *)fp + size);
51 na = fp->a.next;
52
53 nfp->a.type = ARENA_TYPE_FREE;
54 nfp->a.size = fsize - size;
55 fp->a.type = ARENA_TYPE_USED;
56 fp->a.size = size;
57
58 /* Insert into all-block chain */
59 nfp->a.prev = fp;
60 nfp->a.next = na;
61 na->a.prev = nfp;
62 fp->a.next = nfp;
63
64 /* Replace current block on free chain */
65 nfp->next_free = fp->next_free;
66 nfp->prev_free = fp->prev_free;
67 fp->next_free->prev_free = nfp;
68 fp->prev_free->next_free = nfp;
69 } else {
70 /* Allocate the whole block */
71 fp->a.type = ARENA_TYPE_USED;
72
73 /* Remove from free chain */
74 fp->next_free->prev_free = fp->prev_free;
75 fp->prev_free->next_free = fp->next_free;
76 }
77
78 return (void *)(&fp->a + 1);
79 }
80
malloc(size_t size)81 void *malloc(size_t size)
82 {
83 struct free_arena_header *fp;
84
85 if (size == 0)
86 return NULL;
87
88 /* Add the obligatory arena header, and round up */
89 size = (size + 2 * sizeof(struct arena_header) - 1) & ~ARENA_SIZE_MASK;
90
91 for (fp = __malloc_head.next_free; fp->a.type != ARENA_TYPE_HEAD;
92 fp = fp->next_free) {
93 if (fp->a.size >= size) {
94 /* Found fit -- allocate out of this block */
95 return __malloc_from_block(fp, size);
96 }
97 }
98
99 /* Nothing found... need to request a block from the kernel */
100 return NULL; /* No kernel to get stuff from */
101 }
102
calloc(size_t nmemb,size_t size)103 void *calloc(size_t nmemb, size_t size)
104 {
105 void *p;
106 size *= nmemb;
107 p = malloc(size);
108 if (p)
109 memset(p, 0, size);
110 return p;
111 }
112