scc

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

malloc.c (3150B)


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