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