Exercise 8-7: malloc and free with error checking

malloc accepts a size request without checking its plausibility; free believes that the block it is asked to free contains a valid size field. Improve these routines so they make more pains with error checking.

Make kr_malloc return NULL for a request of 0 bytes or more than 1,000,000. Make kr_free ignore NULL, and print kr_free: bad pointer on a line of its own and do nothing else for a pointer it didn't return, one inside a block rather than at its start, or one already freed.

Use them in a program whose input lines are commands. malloc n calls kr_malloc(n), fills the block with zeros, and prints its number (0 for the first malloc command, 1 for the next, and so on) or NULL. free i frees block i; free i +k frees the address k bytes into block i; and free static frees the address of a static array.

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;
}