kern
view src/klibc/malloc.c @ 80:4db99a52863e
fixed the "endianess" of the text messages in the ATA identify info block. this
is the first time I've seen wrong byteorder in ascii text, the ATA committee
should be commended.
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Tue, 06 Dec 2011 13:35:39 +0200 |
| parents | bdd9bf70269d |
| children |
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 = pgcount * 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 }