From 06988a01833c5f669f83b16b35f0b3f70c36f807 Mon Sep 17 00:00:00 2001 From: zlg Date: Sun, 23 Jan 2022 21:20:25 -0800 Subject: Solve Exercise 8-7: malloc & free, improved There wasn't much to check for, but I checked for what I could think of. --- ch8/8-07_malloc-improved.c | 179 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 179 insertions(+) create mode 100644 ch8/8-07_malloc-improved.c (limited to 'ch8') diff --git a/ch8/8-07_malloc-improved.c b/ch8/8-07_malloc-improved.c new file mode 100644 index 0000000..48e835b --- /dev/null +++ b/ch8/8-07_malloc-improved.c @@ -0,0 +1,179 @@ +#include +#include +#include +#include + +/* The C Programming Language: 2nd Edition + * + * Exercise 8-7: `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 that they take more pains with + * error checking. + * + * Notes: There isn't much to check for, since a lot of boundary checking is + * already done. The primary things to watch out for in functions that accept + * pointers is the existence of a NULL pointer, which has undefined behavior + * when dereferenced or otherwise worked with. We also check for the size value + * of a header not exceeding the system's integer limits. Fairly simple error + * checking, but it works. + */ + +typedef long Align; + +union header { + struct { + union header *ptr; + unsigned size; + } s; + /* unused, just for alignment */ + Align x; +} hdr; + +typedef union header Header; + +static Header base; +static Header *freep = NULL; +static Header *zmorecore(unsigned); +void *zmalloc(unsigned); +void zfree(void *); + +void *zmalloc(unsigned nbytes) { + if (nbytes == 0 || nbytes > (UINT_MAX - sizeof (Header))) { + /* cannot ask for zero memory */ + errno = EINVAL; + return NULL; + } + printf("Requesting %d bytes.\n", nbytes); + Header *p, *prevp; + unsigned nunits; + /* Set the number to something more sane */ + nunits = (nbytes + sizeof (Header)); + /* is the K&R wrong here...? */ + /* nunits = (nbytes + sizeof (Header) - 1) / sizeof (Header) + 1; */ + printf("%d units need allocated.\n", nunits); + + if ((prevp = freep) == NULL) { + base.s.ptr = freep = prevp = &base; + base.s.size = 0; + } + for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) { + /* larger than requested units */ + if (p->s.size >= nunits) { + if (p->s.size == nunits) { + prevp->s.ptr = p->s.ptr; + } else { + p->s.size -= nunits; + p += p->s.size; + p->s.size = nunits; + } + freep = prevp; + return (void *)(p+1); + } + if (p == freep) { + if ((p = zmorecore(nunits)) == NULL) { + errno = ENOMEM; + return NULL; + } + } + } +} + +#define NALLOC 1024 + +static Header *zmorecore(unsigned nu) { + char *cp, *sbrk(int); + Header *up; + if (nu < NALLOC) { + nu = NALLOC; + } + cp = sbrk(nu * sizeof (Header)); + if (errno == ENOMEM) { + return NULL; + } + up = (Header *) cp; + up->s.size = nu; + zfree((void *)(up+1)); + return freep; +} + +void zfree(void *ap) { + if (ap == NULL) { + printf("Cannot free null pointer.\n"); + errno = EINVAL; + return; + } + Header *bp, *p; + bp = (Header *)ap - 1; + if (bp->s.size == 0) { + printf("Cannot free block of size 0.\n"); + errno = EINVAL; + return; + } + 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; + } + } + if (bp + bp->s.size == p->s.ptr && bp->s.size < (UINT_MAX - p->s.ptr->s.size)) { + 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 && p->s.size < (UINT_MAX - bp->s.size)) { + p->s.size += bp->s.size; + p->s.ptr = bp->s.ptr; + } else { + p->s.ptr = bp; + } + freep = p; +} + +void * zcalloc(int count, unsigned size) { + char *p; + int i; + p = zmalloc(count * size); + if (p != NULL) { + for (i = 0; i < (count * size); i++) { + p[i] = '\0'; + } + return p; + } else { + return (int *)(-1); + } +} + +int main(int argc, char *argv[]) { + char *foo = "Hello world."; + char *baz = zcalloc(strlen(foo) + 1, sizeof (char)); + strncpy(baz, foo, strlen(foo)+1); + printf("%s\n", baz); + printf("baz is %d long\n", strlen(baz)); + printf("\nHEADER INFO:\n"); + Header *i; + int c = 1; + for (i = freep; ; i = i->s.ptr, c++) { + if (c > 1 && i == &base || + i->s.ptr == i) { + break; + } + printf("Header %d:\n", c); + printf("Address: %p\n", i); + printf("Size: %d\n", i->s.size); + printf("Next: %p\n", i->s.ptr); + printf("Data:\n%s\n", i+i->s.size+1); + } + printf("baz's address is %p\n", baz); + zfree(baz); + printf("\nLet's try allocating zero.\n"); + char *beep = zcalloc(0, sizeof (char)); + if (beep = (char *)(-1)) { + printf("Nope.\n"); + } + printf("\nLet's try allocating UINT_MAX + 1.\n"); + char *borp = zcalloc(UINT_MAX + 1, sizeof (char)); + if (borp = (char *)(-1)) { + printf("Nope.\n"); + } + return 0; +} -- cgit v1.2.3-54-g00ecf