malloc.c - scc - simple c99 compiler
(HTM) git clone git://git.simple-cc.org/scc
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) Submodules
(DIR) README
(DIR) LICENSE
---
malloc.c (3228B)
---
1 #include <errno.h>
2 #include <stdint.h>
3 #include <stdlib.h>
4 #include <string.h>
5
6 #include "malloc.h"
7 #include "../syscall.h"
8 #include "../libc.h"
9
10 #undef malloc
11 #undef free
12
13 #define MAXADDR ((char *)-1)
14 #define ERRADDR ((char *)-1)
15
16 static Header base = { .h.next = &base };
17 Header *_freep = &base;
18
19 /*
20 * Run over the free list looking for the nearest previous
21 * block. There are two possible results: end of the list
22 * or an intermediary block.
23 */
24 void *
25 _prevchunk(Header *hp)
26 {
27 Header *p;
28
29 for (p = _freep; ;p = p->h.next) {
30 /* hp between p and p->h.next? */
31 if (p < hp && hp < p->h.next)
32 break;
33
34 /* p before hp and hp at the end of list? */
35 if (p->h.next <= p && (hp < p->h.next || hp > p))
36 break;
37 }
38 return p;
39 }
40
41 /*
42 * Get the previous block and try to merge
43 * with next and previous blocks
44 */
45 void
46 free(void *mem)
47 {
48 Header *hp, *prev, *next;
49
50 if (!mem)
51 return;
52
53 hp = (Header *) mem - 1;
54 prev = _prevchunk(hp);
55 next = prev->h.next;
56
57 /* join to next */
58 if (hp + hp->h.size == next) {
59 hp->h.size += next->h.size;
60 hp->h.next = next->h.next;
61 } else {
62 hp->h.next = next;
63 }
64
65 /* join to previous */
66 if (prev + prev->h.size == hp) {
67 prev->h.size += hp->h.size;
68 prev->h.next = hp->h.next;
69 } else {
70 prev->h.next = hp;
71 }
72
73 _freep = prev;
74 }
75
76 static void *
77 sbrk(uintptr_t inc)
78 {
79 char *new, *old;
80 static void *heap;
81
82 if (!heap)
83 heap = _getheap();
84
85 old = heap;
86 if (old >= MAXADDR - inc)
87 return ERRADDR;
88
89 new = old + inc;
90 if (_brk(new) < 0)
91 return ERRADDR;
92 heap = new;
93
94 return old;
95 }
96
97 static Header *
98 morecore(size_t nunits)
99 {
100 void *rawmem;
101 Header *hp;
102
103 if (nunits < NALLOC)
104 nunits = NALLOC;
105
106 rawmem = sbrk(nunits * sizeof(Header));
107 if (rawmem == ERRADDR)
108 return NULL;
109
110 hp = (Header *) rawmem;
111 hp->h.size = nunits;
112
113 /* integrate new memory into the list */
114 free(hp + 1);
115
116 return _freep;
117 }
118
119 /*
120 * Run over the list of free blocks trying to find a block
121 * big enough for nbytes. If the block fits perfectly with
122 * the required size then we only have to unlink
123 * the block. Otherwise we have to split the block and
124 * return the right part. If we run over the full list
125 * without a fit then we have to acquire more memory
126 *
127 * ______________________________________
128 * ___________./______________________________________\_____
129 * ...| in | | | in | |.....| in | | | |....
130 * ...| use | | | use | |.....| use | | | |....
131 * ___|______|___|.____|_____|._|_____|______|._|.___|.|____
132 * \__/ \_________/ \_____________/ \/ \__/
133 */
134 void *
135 malloc(size_t nbytes)
136 {
137 Header *cur, *prev;
138 size_t nunits;
139
140 if (nbytes > SIZE_MAX - sizeof(Header)-1) {
141 errno = ENOMEM;
142 return NULL;
143 }
144
145 /* 1 unit for header plus enough units to fit nbytes */
146 nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
147
148 for (prev = _freep; ; prev = cur) {
149 cur = prev->h.next;
150 if (cur->h.size >= nunits) {
151 if (cur->h.size == nunits) {
152 prev->h.next = cur->h.next;
153 } else {
154 cur->h.size -= nunits;
155 cur += cur->h.size;
156 cur->h.size = nunits;
157 }
158
159 cur->h.next = NULL;
160 _freep = prev;
161
162 return cur + 1;
163 }
164
165 if (cur == _freep) {
166 if ((cur = morecore(nunits)) == NULL)
167 return NULL;
168 }
169 }
170 }