scc

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

malloc.c (3129B)


      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 
     12 #define MAXADDR ((char *)-1)
     13 #define ERRADDR ((char *)-1)
     14 
     15 static Header base = { .h.next = &base };
     16 static 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;
     48 
     49 	if (!mem)
     50 		return;
     51 
     52 	hp = (Header *) mem - 1;
     53 	prev = _prevchunk(hp);
     54 
     55 	/* join to next */
     56 	if (hp + hp->h.size == prev->h.next) {
     57 		hp->h.size += prev->h.next->h.size;
     58 		hp->h.next = prev->h.next->h.next;
     59 	} else {
     60 		hp->h.next = prev->h.next;
     61 	}
     62 
     63 	/* join to previous */
     64 	if (prev + prev->h.size == hp) {
     65 		prev->h.size += hp->h.size;
     66 		prev->h.next = hp->h.next;
     67 	} else {
     68 		prev->h.next = hp;
     69 	}
     70 
     71 	freep = prev;
     72 }
     73 
     74 static void *
     75 sbrk(uintptr_t inc)
     76 {
     77 	char *new, *old;
     78 	static void *heap;
     79 
     80 	if (!heap)
     81 		heap = _getheap();
     82 
     83 	old = heap;
     84 	if (old >= MAXADDR - inc)
     85 		return ERRADDR;
     86 
     87 	new = old + inc;
     88 	if (_brk(new) < 0)
     89 		return ERRADDR;
     90 	heap = new;
     91 
     92 	return old;
     93 }
     94 
     95 static Header *
     96 morecore(size_t nunits)
     97 {
     98 	char *rawmem;
     99 	Header *hp;
    100 
    101 	if (nunits < NALLOC)
    102 		nunits = NALLOC;
    103 
    104 	rawmem = sbrk(nunits * sizeof(Header));
    105 	if (rawmem == ERRADDR)
    106 		return NULL;
    107 
    108 	hp = (Header*)rawmem;
    109 	hp->h.size = nunits;
    110 
    111 	/* integrate new memory into the list */
    112 	free(hp + 1);
    113 
    114 	return freep;
    115 }
    116 
    117 /*
    118  * Run over the list of free blocks trying to find a block
    119  * big enough for nbytes. If the block fit perfectly with
    120  * the required size then we only have to unlink
    121  * the block. Otherwise we have to split the block and
    122  * return the right part. If we run over the full list
    123  * without a fit then we have to require more memory
    124  *
    125  *              ______________________________________
    126  * ___________./______________________________________\_____
    127  * ...| in   |   |     | in  |  |.....| in   |  |    | |....
    128  * ...| use  |   |     | use |  |.....| use  |  |    | |....
    129  * ___|______|___|.____|_____|._|_____|______|._|.___|.|____
    130  *            \__/ \_________/ \_____________/ \/ \__/
    131  */
    132 void *
    133 malloc(size_t nbytes)
    134 {
    135 	Header *cur, *prev;
    136 	size_t nunits;
    137 
    138 	/* 1 unit for header plus enough units to fit nbytes */
    139 	nunits = (nbytes+sizeof(Header)-1) / sizeof(Header)+1;
    140 
    141 	for (prev = freep; ; prev = cur) {
    142 		cur = prev->h.next;
    143 		if (cur->h.size >= nunits) {
    144 			if (cur->h.size == nunits) {
    145 				prev->h.next = cur->h.next;
    146 			} else {
    147 				cur->h.size -= nunits;
    148 				cur += cur->h.size;
    149 				cur->h.size = nunits;
    150 			}
    151 			freep = prev;
    152 			return cur + 1;
    153 		}
    154 
    155 		if (cur == freep) {
    156 			if ((cur = morecore(nunits)) == NULL) {
    157 				errno = ENOMEM;
    158 				return NULL;
    159 			}
    160 		}
    161 	}
    162 }