Exercise 8-8: Free any block with bfree

Write a routine bfree(p,n) that will free any arbitrary block p of n characters into the free list maintained by malloc and free. By using bfree, a user can add a static or external array to the free list at any time.

Here bfree adds to the list kept by kr_malloc and kr_free; p need not be aligned, and a block too small to hold a header and some space is ignored. Use it in a program with a static array arena of 10,000 characters, whose input lines are commands. bfree off n calls bfree(arena + off, n). malloc n calls kr_malloc(n) and prints arena if the block is inside arena, heap if it isn't, or NULL. free frees the block from the latest malloc.

The book's storage allocator from Section 8.7, renamed kr_malloc, kr_free and kr_morecore so it works beside the C library's own malloc and free, which printf and the rest of the library use. sbrk is declared here because strict ISO C headers leave it out.

#include <stddef.h>   /* size_t, NULL */
#include <stdint.h>   /* intptr_t */

void *sbrk(intptr_t increment);

typedef long Align;   /* for alignment to long boundary */

union header {        /* block header */
    struct {
        union header *ptr; /* next block if on free list */
        unsigned size;     /* size of this block */
    } s;
    Align x;          /* force alignment of blocks */
};

typedef union header Header;

static Header base;           /* empty list to get started */
static Header *freep = NULL;  /* start of free list */

static Header *kr_morecore(unsigned);
void kr_free(void *);

/* kr_malloc:  general-purpose storage allocator */
void *kr_malloc(size_t nbytes)
{
    Header *p, *prevp;
    unsigned nunits;

    nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
    if ((prevp = freep) == NULL) {   /* no free list yet */
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {   /* big enough */
            if (p->s.size == nunits)     /* exactly */
                prevp->s.ptr = p->s.ptr;
            else {               /* allocate tail end */
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p+1);
        }
        if (p == freep)  /* wrapped around free list */
            if ((p = kr_morecore(nunits)) == NULL)
                return NULL;    /* none left */
    }
}

#define NALLOC  1024   /* minimum #units to request */

/* kr_morecore:  ask system for more memory */
static Header *kr_morecore(unsigned nu)
{
    char *cp;
    Header *up;

    if (nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) -1)   /* no space at all */
        return NULL;
    up = (Header *) cp;
    up->s.size = nu;
    kr_free((void *)(up+1));
    return freep;
}

/* kr_free:  put block ap in free list */
void kr_free(void *ap)
{
    Header *bp, *p;

    bp = (Header *)ap - 1;    /* point to block header */
    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;  /* freed block at start or end of arena */

    if (bp + bp->s.size == p->s.ptr) {    /* join to upper nbr */
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    } else
        bp->s.ptr = p->s.ptr;
    if (p + p->s.size == bp) {            /* join to lower nbr */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;
    freep = p;
}