scc

simple c99 compiler
git clone git://git.simple-cc.org/scc
Log | Files | Refs | Submodules | README | LICENSE

malloc.c (3200B)


      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 fit 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 require 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 }