Exercise 8.07

Page 189

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 take more pains with error checking.

/* I found this SO answer very helpful in understanding some of the routines presented:
 * https://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book/36512105#36512105 */

#include <unistd.h>

typedef long Align;

union header {
	struct {
		union header *ptr;
		unsigned size;
	} s;
	Align _;
};

typedef union header Header;

static Header base;
static Header *freep = NULL;
static Header *knrmorecore(unsigned nu);

void *knrmalloc(unsigned nbytes)
{
	Header *currp, *prevp;
	Header *morecore(unsigned);
	unsigned nunits;

	/* I couldn't think of a reasonable way to determine a maximum number to check; as
     * far as I understand if the system has run out of memory the expectation is just
     * that sbrk (and therefore morecore and therefore malloc) will fail / return NULL.
     * I checked for some other solutions online and 10240 seems to be the number that a
     * few people used, though I can't seem to find where this number comes from. Maybe
     * at some point down the line I will come back to this and facepalm for not knowing
     * what that number represents, but at the moment I have no idea. */
	if (nbytes == 0) {
		return NULL;
	}

	nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;

	if ((prevp = freep) == NULL) {
		base.s.ptr = freep = prevp = &base;
		base.s.size = 0;
	}

	for (currp = prevp->s.ptr;; prevp = currp, currp = currp->s.ptr) {
		if (currp->s.size >= nunits) {
			if (currp->s.size == nunits) {
				prevp->s.ptr = currp->s.ptr;
			} else { /* allocate tail end */
				currp->s.size -= nunits;
				currp += currp->s.size;
				currp->s.size = nunits;
			}
			freep = prevp;
			return (void *)(currp + 1);
		}
		if (currp == freep) {
			if ((currp = knrmorecore(nunits)) == NULL) {
				return NULL;
			}
		}
	}
}

#define NALLOC 1024
void knrfree(void *ap);
static Header *knrmorecore(unsigned nu)
{
	char *cp;
	Header *up;

	if (nu < NALLOC) {
		nu = NALLOC;
	}
	cp = sbrk(nu * sizeof(Header));
	if (cp == (char *)-1) {
		return NULL;
	}
	up = (Header *)cp;
	up->s.size = nu;
	knrfree((void *)(up + 1));
	return freep;
}

void knrfree(void *ap)
{
	Header *insertp, *currp;

	if (ap == NULL) {
		return;
	}

	insertp = (Header *)ap - 1;

	if (insertp->s.size == 0) {
		return;
	}

	for (currp = freep; !(insertp > currp && insertp < currp->s.ptr);
	     currp = currp->s.ptr) {
		if (currp >= currp->s.ptr &&
		    (insertp > currp || insertp < currp->s.ptr)) {
			break;
		}
	}

	if (insertp + insertp->s.size == currp->s.ptr) { /* join to upper nbr */
		insertp->s.size += currp->s.ptr->s.size;
		insertp->s.ptr = currp->s.ptr->s.ptr;
	} else {
		insertp->s.ptr = currp->s.ptr;
	}

	if (currp + currp->s.size == insertp) {
		currp->s.size += insertp->s.size;
		currp->s.ptr = insertp->s.ptr;
	} else {
		currp->s.ptr = insertp;
	}
	freep = currp;
}

#include <string.h>
void *mycalloc(int n, size_t size)
{
	void *res = knrmalloc(n * size);
	if (res != NULL) {
		memset(res, 0, n * size);
	}
	return res;
}

#include <stdio.h>
#include <stdlib.h>
int main()
{
	char *str = (char *)knrmalloc(100 * sizeof(char));
	if (str == NULL) {
		puts("error: knrmalloc failed");
		exit(1);
	}

	strcpy(str, "hello, world!");
	puts(str);

	str = (char *)mycalloc(100, sizeof(char));
	if (str == NULL) {
		puts("error: mycalloc failed");
		exit(1);
	}

	strcpy(str, "hello, world!");
	puts(str);
}