kern
view src/klibc/malloc.c @ 28:bdd9bf70269d
implemented malloc
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Fri, 27 May 2011 12:05:38 +0300 |
| parents | |
| children | 3ed041d07ae1 |
line source
1 #include <stdlib.h>
2 #include "intr.h"
3 #include "vm.h"
4 #include "panic.h"
6 #define MAGIC 0xbaadbeef
8 struct mem_range {
9 uint32_t start;
10 size_t size;
11 struct mem_range *next;
12 };
14 struct alloc_desc {
15 size_t size;
16 uint32_t magic;
17 };
19 static void add_range(struct mem_range *rng);
20 static void coalesce(struct mem_range *low, struct mem_range *mid, struct mem_range *high);
21 static struct mem_range *alloc_node(void);
22 static void free_node(struct mem_range *node);
24 struct mem_range *free_list;
25 struct mem_range *node_pool;
28 void *malloc(size_t sz)
29 {
30 void *res = 0;
31 struct mem_range *node, *prev, dummy;
32 int intr_state;
33 struct alloc_desc *desc;
34 size_t alloc_size = sz + sizeof *desc;
36 if(!sz) {
37 return 0;
38 }
40 /* entering the critical section, do not disturb */
41 intr_state = get_intr_state();
42 disable_intr();
44 find_range:
45 prev = &dummy;
46 dummy.next = node = free_list;
47 while(node) {
48 /* find a node in the free_list with enough space ... */
49 if(node->size >= alloc_size) {
50 /* insert the allocation descriptor at the beginning */
51 desc = (void*)node->start;
52 desc->size = alloc_size;
53 desc->magic = MAGIC;
54 res = desc + 1; /* that's what we'll return to the user */
56 /* modify the node to reflect the new range after we
57 * grabbed a part at the beginning...
58 */
59 node->size -= alloc_size;
60 node->start += alloc_size;
62 /* if the range represented by this node now has zero size,
63 * remove and free the node (it goes into the node_pool)
64 */
65 if(!node->size) {
66 prev->next = node->next;
67 if(free_list == node) {
68 free_list = node->next;
69 }
70 free_node(node);
71 }
72 break;
73 }
74 prev = node;
75 node = node->next;
76 }
78 /* we didn't find a range big enough in the free_list. In that case
79 * we need to allocate some pages, add them to the free_list and try
80 * again.
81 */
82 if(!res) {
83 struct mem_range *range;
84 int pg, pgcount = (PGSIZE - 1 + alloc_size) / PGSIZE;
86 if((pg = pgalloc(pgcount, MEM_KERNEL)) == -1) {
87 set_intr_state(intr_state);
88 return 0;
89 }
91 range = alloc_node();
92 range->start = PAGE_TO_ADDR(pg);
93 range->size = pg * PGSIZE;
94 add_range(range);
95 goto find_range;
96 }
98 set_intr_state(intr_state);
99 return res;
100 }
102 void free(void *ptr)
103 {
104 int intr_state;
105 struct alloc_desc *desc;
106 struct mem_range *rng;
108 if(!ptr) return;
110 intr_state = get_intr_state();
111 disable_intr();
113 desc = (struct alloc_desc*)ptr - 1;
114 if(desc->magic != MAGIC) {
115 panic("free(%x) magic missmatch, invalid address.\n", (unsigned int)ptr);
116 }
118 rng = alloc_node();
119 rng->start = (uint32_t)desc;
120 rng->size = desc->size;
121 add_range(rng);
123 set_intr_state(intr_state);
124 }
126 static void add_range(struct mem_range *rng)
127 {
128 struct mem_range *node, *prev = 0;
130 if(!free_list || free_list->start > rng->start) {
131 rng->next = free_list;
132 free_list = rng;
134 } else {
135 node = free_list;
137 while(node) {
138 if(!node->next || node->next->start > rng->start) {
139 rng->next = node->next;
140 node->next = rng;
141 prev = node; /* needed by coalesce after the loop */
142 break;
143 }
145 prev = node;
146 node = node->next;
147 }
148 }
150 coalesce(prev, rng, rng->next);
151 }
153 static void coalesce(struct mem_range *low, struct mem_range *mid, struct mem_range *high)
154 {
155 if(high) {
156 if(mid->start + mid->size >= high->start) {
157 mid->size = high->size - mid->start;
158 mid->next = high->next;
159 free_node(high);
160 }
161 }
163 if(low) {
164 if(low->start + low->size >= mid->start) {
165 low->size = mid->size - low->start;
166 low->next = mid->next;
167 free_node(mid);
168 }
169 }
170 }
172 static struct mem_range *alloc_node(void)
173 {
174 struct mem_range *node;
176 /* no nodes available for reuse...
177 * grab a page, slice it into nodes, link them up and hang them in the pool
178 */
179 if(!node_pool) {
180 int i, num_nodes, pg;
181 struct mem_range *nodepage;
183 pg = pgalloc(1, MEM_KERNEL);
184 if(pg == -1) {
185 panic("failed to allocate page for the malloc node pool\n");
186 return 0; /* unreachable */
187 }
189 nodepage = (struct mem_range*)PAGE_TO_ADDR(pg);
190 num_nodes = PGSIZE / sizeof *nodepage;
192 for(i=1; i<num_nodes; i++) {
193 nodepage[i - 1].next = nodepage + i;
194 }
195 nodepage[i - 1].next = 0;
196 node_pool = nodepage;
197 }
199 node = node_pool;
200 node_pool = node->next;
201 node->next = 0;
202 return node;
203 }
205 static void free_node(struct mem_range *node)
206 {
207 node->next = node_pool;
208 node_pool = node;
209 }