/* $Header$ */ /* replace undef by define */ #define ALIGN_EIGHT_BYTES /* Use 8-byte alignment. */ #define DEBUG /* check assertions */ #undef SLOWDEBUG /* some extra test loops (requires DEBUG) */ #ifndef DEBUG #define NDEBUG #endif #include #include #include #include #include "malloc-debug.h" static int no_debug = -1; #define CHECK_DBG(statement) \ if (no_debug <= 0) { \ if (no_debug < 0) no_debug = getenv("MALLOC_DEBUG") ? 0 : 1; \ if (no_debug == 0) { statement; } \ } #if _EM_WSIZE == _EM_PSIZE #define ptrint int #else #define ptrint long #endif #if _EM_PSIZE == 2 #define BRKSIZE 1024 #else #define BRKSIZE 4096 #endif #ifdef ALIGN_EIGHT_BYTES #define PTRSIZE 8 #else #define PTRSIZE ((int) sizeof(void *)) #endif /** * "Align(x,a)" est la plus petite adresse au dessus de "x" alignee avec "a" * (typiquement PTRSIZE). * (Rq : si "a" n'est pas une puissance de 2, ca fait n'importe quoi...) */ #define Align(x,a) (((x) + (a - 1)) & ~(a - 1)) /** * "NextSlot(p)" nous donne l'adresse des donnees du bloc (libre ou occupe) * suivant. * * Plus precisemment, dans "NextSlot(p)" : * - "p" est l'adresse du debut des donnees d'un bloc, * - "p-PTRSIZE" est l'adresse de la case memoire juste avant la zone de * donnees. Cette case contient l'adresse des donnees du bloc suivant, * C'est donc un "void **". * On obtient donc la valeur du pointeur vers les donnees du bloc suivant "p". */ #define NextSlot(p) (* (void **) ((p) - PTRSIZE)) /** * "NextFree(p)" nous donne l'adresse des donnees du bloc libre suivant. Cette * macro n'a des sens que si "p" est lui meme un bloc libre. * * Plus precisemment, dans "NextFree(p)", "p" est l'adresse du debut des * donnees d'un bloc libre. Ce bloc commence donc par un pointeur vers les * donnees du bloc libre suivant. On obtient donc la valeur de ce pointeur. */ #define NextFree(p) (* (void **) (p)) /* * A short explanation of the data structure and algorithms. * An area returned by malloc() is called a slot. Each slot * contains the number of bytes requested, but preceeded by * an extra pointer to the next the slot in memory. * '_bottom' and '_top' point to the first/last slot. * More memory is asked for using brk() and appended to top. * The list of free slots is maintained to keep malloc() fast. * '_empty' points the the first free slot. Free slots are * linked together by a pointer at the start of the * user visable part, so just after the next-slot pointer. * Free slots are merged together by free(). * * Since modern processors prefer 8-byte alignment, we now pretend * our pointers are 8 bytes wide. */ /** * "_sbrk()" et "_brk()" sont les versions Minix de "brk()" et "sbrk()". De * cette maniere, meme si on redefinit "brk()" et "sbrk()", "malloc()" * continue de fonctionner normalement. */ extern void *_sbrk(int); extern int _brk(void *); /** * Les variables globales pour le premier et dernier slot, ainsi que le * premier slot libre. * Remarque : "_top" est toujours un bloc "vide" qui sert seulement a marquer * la fin de la memoire. On ne peut pas s'en servir pour allouer de la * memoire... */ static void *_bottom, *_top, *_empty; /** * Fonction qui appelle "brk" pour augmenter la taille du tas quand cela est * necessaire. */ static int grow(size_t len) /** "len" contient le nombre d'octets a rajouter au tas */ { register char *p; /** rappel : "_top" est le dernier slot, son pointeur vers le slot suivant * est donc NULL. */ assert(NextSlot((char *)_top) == 0); /** Est-il possible d'allouer la taille demandee ? * Si "_top+len < _top", c'est qu'on a un depassement de capacite : on ne * peut de toute facon pas adresser les adresses correspondantes. * C'est pareil s'il y a un depassement de capacite en prenant l'alignement * en compte. * "p" prend comme valeur "_top+len" (plus alignement). */ /* FIXME : pourquoi faire le premier test ? */ if ((char *) _top + len < (char *) _top || (p = (char *)Align((ptrint)_top + len, BRKSIZE)) < (char *) _top ) { errno = ENOMEM; return(0); } /** appel a "brk()" pour augmenter la taille du tas */ if (_brk(p) != 0) return(0); /** On agrandit le dernier slot (vide) en mettant NextSlot a la valeur du * nouveau dernier bloc (vide). */ NextSlot((char *)_top) = p; /** "p" devient lui meme le dernier slot : il n'a pas de NextSlot. */ NextSlot(p) = 0; /** Il faut inserer le bloc ajoute dans la liste des blocs libres. * La fonction "free" fait entre autre ceci. (Elle passe egalement le bloc * de occupe a libre, mais comme celui ci est deja libre, cette etape ne * sert a rien dans ce cas precis...) */ free(_top); _top = p; return 1; } /** La fonction "malloc" */ void * malloc(const size_t size) { register char *prev, *p, *next, *new; unsigned ntries; if (size == 0) return NULL; CHECK_DBG(return _dbg_malloc(size)); for (ntries = 0; ntries < 2; ntries++) { unsigned len = Align(size, PTRSIZE) + PTRSIZE; if (len < 2 * PTRSIZE) { errno = ENOMEM; return NULL; } if (_bottom == 0) { if ((p = _sbrk(2 * PTRSIZE)) == (char *) -1) return NULL; p = (char *) Align((ptrint)p, PTRSIZE); p += PTRSIZE; _top = _bottom = p; NextSlot(p) = 0; } #ifdef SLOWDEBUG for (p = _bottom; (next = NextSlot(p)) != 0; p = next) assert(next > p); assert(p == _top); #endif for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p)) { next = NextSlot(p); new = p + len; /* easily overflows!! */ if (new > next || new <= p) continue; /* too small */ if (new + PTRSIZE < next) { /* too big, so split */ /* + PTRSIZE avoids tiny slots on free list */ NextSlot(new) = next; NextSlot(p) = new; NextFree(new) = NextFree(p); NextFree(p) = new; } if (prev) NextFree(prev) = NextFree(p); else _empty = NextFree(p); return p; } if (grow(len) == 0) break; } assert(ntries != 2); return NULL; } /** non commentee... */ void * realloc(void *oldp, size_t size) { register char *prev, *p, *next, *new; char *old = oldp; register size_t len, n; if (old == 0) return malloc(size); if (size == 0) { free(old); return NULL; } CHECK_DBG(return _dbg_realloc(oldp, size)); len = Align(size, PTRSIZE) + PTRSIZE; next = NextSlot(old); n = (int)(next - old); /* old length */ /* * extend old if there is any free space just behind it */ for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p)) { if (p > next) break; if (p == next) { /* 'next' is a free slot: merge */ NextSlot(old) = NextSlot(p); if (prev) NextFree(prev) = NextFree(p); else _empty = NextFree(p); next = NextSlot(old); break; } } new = old + len; /* * Can we use the old, possibly extended slot? */ if (new <= next && new >= old) { /* it does fit */ if (new + PTRSIZE < next) { /* too big, so split */ /* + PTRSIZE avoids tiny slots on free list */ NextSlot(new) = next; NextSlot(old) = new; free(new); } return old; } if ((new = malloc(size)) == NULL) /* it didn't fit */ return NULL; memcpy(new, old, n); /* n < size */ free(old); return new; } /** Cette fonction va transformer un bloc occupe en bloc libre, et inserer le * bloc libre dans la liste chainee des blocs libre (en fusionnant des blocs * libres si besoin). */ void free(void *ptr) /* "ptr" est le pointeur vers le bloc de donnees que l'utilisateur souhaite * desallouer. */ { register char *prev, *next; char *p = ptr; if (p == 0) return; CHECK_DBG(_dbg_free(ptr); return); #ifdef SLOWDEBUG { int found; char *curr; /* block must be in block list */ assert(_bottom); found = 0; for (curr = _bottom; (next = NextSlot(curr)) != 0; curr = next) { assert(next > curr); if (curr == p) found = 1; } if (curr == p) found = 1; assert(found); /* block must not be in free list */ if (_empty) { found = 0; for (curr = _empty; (next = NextFree(curr)) != 0; curr = next) { assert(next > curr); if (curr == p) found = 1; } if (curr == p) found = 1; assert(!found); } } #endif /** La condition n'est (probablement) pas satisfaite si on ne pointe pas sur * un bloc valide. Elle n'est pas non plus satisfaite pour le dernier bloc * ("_top") qui n'est jamais utilise comme bloc de donnees. */ assert((char *) NextSlot(p) > p); /** on parcourt la liste des blocs libres pour se placer juste apres le bloc * libre precedent "p" */ for (prev = 0, next = _empty; next != 0; prev = next, next = NextFree(next)) if (p < next) break; /** on insere "p" dans la liste */ NextFree(p) = next; /** avec un cas particulier lorsque c'est le premier bloc. */ if (prev) NextFree(prev) = p; else _empty = p; /** fusion des blocs libres lorsque c'est necessaire */ if (next) { assert((char *) NextSlot(p) <= next); /** fusion de "p" avec le bloc suivant */ if (NextSlot(p) == next) { /* merge p and next */ NextSlot(p) = NextSlot(next); NextFree(p) = NextFree(next); } } if (prev) { assert((char *) NextSlot(prev) <= p); /** fusion de "p" avec le bloc precedent */ if (NextSlot(prev) == p) { /* merge prev and p */ NextSlot(prev) = NextSlot(p); NextFree(prev) = NextFree(p); } } }