scc

  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
 16static Header base = { .h.next = &base };
 17Header *_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 */
 24void *
 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 */
 45void
 46free(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
 76static void *
 77sbrk(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
 97static Header *
 98morecore(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 */
134void *
135malloc(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}