#include <stdio.h>
#include <stdint.h> //uintptr_t
#include <unistd.h> //sbrk
//compile with: gcc -Wall -Wextra cc-c.c -o cc-c
//run with: ./cc-c
//K&R2 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 they make more pains with
//error checking.
//
//The 8.7 allocator again, with checks added -- every added line is
//marked "8-7". my_malloc refuses a request bigger than MAXBYTES.
//my_free refuses, with a message on stderr, a pointer that:
// - is NULL quietly ignored, as the standard says
// - lies outside the memory morecore ever got from sbrk
// - isn't aligned the way every my_malloc pointer is
// - has a size field running past the end of that memory, or 0
// - has no "in use" mark in its header: never given out by my_malloc,
// or freed already
//
//The mark is a new header field, magic. my_malloc writes USED into
//every block it hands out; my_free checks for it and writes FREED.
//On this machine magic costs nothing: the header had 4 bytes of
//padding after size, and magic fits in them -- still 16 bytes.
//
//None of this is proof. A wild pointer can land on bytes that happen
//to read USED; libc's own malloc also moves the break, so its blocks
//can sit inside the range morecore saw. The checks catch the common
//mistakes cheaply; tools like valgrind catch the rest, slowly.
//
//main:
// 1. the header with magic: still 16 bytes
// 2. normal use still works
// 3. malloc: an implausible size
// 4. free(NULL)
// 5. free of memory my_malloc never gave out: stack, static
// 6. free of a pointer one byte off
// 7. free of a pointer into the middle of a block
// 8. double free
// 9. a header overwritten by the caller (writing in front of a)
// 10. after all that, the free list is intact
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, in Header units
unsigned magic; //8-7: USED or FREED
} s;
Align x; //force alignment of blocks; never used
};
typedef union header Header;
#define USED 0xA110C8EDu //8-7: "allocated"
#define FREED 0xF4EEB10Cu //8-7: "free block"
#define MAXBYTES (16u * 1024 * 1024) //8-7: largest single request
static Header base; //empty list to get started
static Header *freep = NULL; //start of free list
static Header *heap_lo = NULL; //8-7: lowest address sbrk gave morecore
static Header *heap_hi = NULL; //8-7: just past the highest
static Header *morecore(unsigned);
void my_free(void *ap);
//my_malloc: general-purpose storage allocator
void *my_malloc(unsigned nbytes)
{
Header *p, *prevp;
unsigned nunits;
//8-7: refuse before computing nunits -- on a machine where size_t
//is unsigned, nbytes + sizeof(Header) - 1 wraps for the top values
//and a huge request becomes a 1-unit block
if (nbytes > MAXBYTES) {
fprintf(stderr, "my_malloc: %u bytes is more than %u\n",
nbytes, MAXBYTES);
return NULL;
}
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;
base.s.magic = FREED; //8-7
}
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;
}
p->s.magic = USED; //8-7
freep = prevp;
return (void *)(p+1);
}
if (p == freep) //wrapped around free list
if ((p = morecore(nunits)) == NULL)
return NULL; //none left
}
}
#define NALLOC 1024 //minimum #units to request
//morecore: ask system for more memory
static Header *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;
//8-7: widen the known range BEFORE my_free checks this chunk against it
if (heap_lo == NULL || up < heap_lo)
heap_lo = up;
if (up + nu > heap_hi)
heap_hi = up + nu;
up->s.magic = USED; //8-7: it is "allocated" until freed
my_free((void *)(up+1));
return freep;
}
//bad: 8-7 -- report a refused free
static void bad(void *ap, const char *why)
{
fprintf(stderr, "my_free: %p refused: %s\n", ap, why);
}
//my_free: put block ap in free list
void my_free(void *ap)
{
Header *bp, *p;
//IDIOM: free(NULL) does nothing -- so callers can free without
//testing first, e.g. at the end of a function that may have failed
if (ap == NULL) //8-7
return;
bp = (Header *)ap - 1; //point to block header
//8-7: the checks, cheapest first; each one makes the next safe to do
//IDIOM: check where a pointer points before reading through it --
//the range test comes before anything reads *bp
if (heap_lo == NULL || bp < heap_lo || bp >= heap_hi) {
bad(ap, "not in the heap");
return;
}
//IDIOM: (uintptr_t)p % n -- turn the pointer into a number to test
//its alignment; pointers themselves have no % operator
if ((uintptr_t)ap % _Alignof(Header) != 0) {
bad(ap, "misaligned");
return;
}
if (bp->s.magic == FREED) {
bad(ap, "already free");
return;
}
if (bp->s.magic != USED) {
bad(ap, "no USED mark -- not the start of a my_malloc block");
return;
}
//IDIOM: compare size against the room left, not bp + size against
//the end -- bp + a garbage size could overflow before the compare
if (bp->s.size == 0 || bp->s.size > (unsigned)(heap_hi - bp)) {
bad(ap, "size field runs past the heap");
return;
}
bp->s.magic = FREED;
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;
}
static void show(const char *label) //free list: blocks and units
{
Header *p;
int blocks = 0;
unsigned units = 0;
for (p = base.s.ptr; p != &base; p = p->s.ptr) {
blocks++;
units += p->s.size;
}
printf(" %-24s free list: %d block%s, %u units\n",
label, blocks, blocks == 1 ? "" : "s", units);
}
static char not_heap_static[64];
int main(void)
{
char *a, *b, *q;
char not_heap_stack[64];
int i;
printf("1. the header gained a field and didn't grow\n");
printf(" sizeof(Header) %zu: ptr 8 + size 4 + magic 4. it was 16 with\n"
" 4 bytes of padding; magic took them. (on a 32-bit machine:\n"
" ptr 4 + size 4 + magic 4 = 12, so there it costs a word)\n",
sizeof(Header));
fflush(stdout);
printf("\n2. normal use is unchanged\n");
a = my_malloc(64);
b = my_malloc(100);
show("a, b allocated");
printf(" magic behind a: 0x%X (USED)\n", ((Header *)a - 1)->s.magic);
my_free(b);
show("my_free(b)");
b = my_malloc(100);
show("b again");
//each refusal below prints a my_free/my_malloc line on stderr;
//fflush first so it lands in order with the printf lines
printf("\n3. my_malloc: refuse a size no one means\n");
fflush(stdout);
q = my_malloc(4000000000u);
printf(" my_malloc(4000000000) = %s\n", q == NULL ? "NULL" : "not NULL");
printf(" 16 MB is a choice, not a law; what matters is that the test\n"
" comes before the nunits arithmetic can wrap\n");
printf("\n4. my_free(NULL): nothing happens, no message\n");
fflush(stdout);
my_free(NULL);
show("after my_free(NULL)");
printf("\n5. memory that never came from my_malloc\n");
fflush(stdout);
my_free(not_heap_stack);
my_free(not_heap_static);
printf(" a local array (the stack, near the top of memory) and a\n"
" static one (data, below the heap): both fail the range test.\n"
" the book's free would read a \"size\" from in front of them\n");
printf("\n6. a pointer one byte off\n");
fflush(stdout);
my_free(a + 1);
printf(" every my_malloc pointer is a multiple of %zu; a + 1 can't be\n",
_Alignof(Header));
printf("\n7. a pointer into the middle of a block\n");
for (i = 0; i < 64; i++)
a[i] = 'x';
fflush(stdout);
my_free(a + 32);
printf(" a + 32 is in range and aligned; the 16 bytes in front of it\n"
" are a's data, \"xxxx...\", so magic reads 0x%X, not USED\n",
((Header *)(a + 32) - 1)->s.magic);
printf("\n8. double free\n");
my_free(b);
show("my_free(b)");
fflush(stdout);
my_free(b);
show("my_free(b) again");
printf(" the first free wrote FREED in b's header and merged b into\n"
" the big block; the second found FREED and stopped. the book's\n"
" free would link b in again, inside the big block: the same\n"
" memory on the list twice, to be handed out twice\n");
printf("\n9. the caller writes in front of its block\n");
((Header *)a - 1)->s.size = 1000000; //as if a[-8] .. a[-5] were overwritten
fflush(stdout);
my_free(a);
printf(" a's header still says USED, but its size is now 1000000\n"
" units, %ld more than the heap holds from a on\n",
1000000L - (long)(heap_hi - ((Header *)a - 1)));
((Header *)a - 1)->s.size = 5; //put it back: 64 bytes + header
printf("\n10. none of the refused frees touched the list\n");
my_free(a);
show("my_free(a), repaired");
a = my_malloc(64);
b = my_malloc(100);
my_free(a);
my_free(b);
show("alloc and free again");
printf(" one block, all %d units: the arena is whole\n", NALLOC);
return 0;
}
win@DESKTOP-MEIH88T:~/webdev-projects$ gcc -Wall -Wextra cc-c.c -o cc-c
win@DESKTOP-MEIH88T:~/webdev-projects$ ./cc-c
1. the header gained a field and didn't grow
sizeof(Header) 16: ptr 8 + size 4 + magic 4. it was 16 with
4 bytes of padding; magic took them. (on a 32-bit machine:
ptr 4 + size 4 + magic 4 = 12, so there it costs a word)
2. normal use is unchanged
a, b allocated free list: 1 block, 1011 units
magic behind a: 0xA110C8ED (USED)
my_free(b) free list: 1 block, 1019 units
b again free list: 1 block, 1011 units
3. my_malloc: refuse a size no one means
my_malloc: 4000000000 bytes is more than 16777216
my_malloc(4000000000) = NULL
16 MB is a choice, not a law; what matters is that the test
comes before the nunits arithmetic can wrap
4. my_free(NULL): nothing happens, no message
after my_free(NULL) free list: 1 block, 1011 units
5. memory that never came from my_malloc
my_free: 0x7ffe0d5c5960 refused: not in the heap
my_free: 0x5565f8af50a0 refused: not in the heap
a local array (the stack, near the top of memory) and a
static one (data, below the heap): both fail the range test.
the book's free would read a "size" from in front of them
6. a pointer one byte off
my_free: 0x55661fbe7fc1 refused: misaligned
every my_malloc pointer is a multiple of 8; a + 1 can't be
7. a pointer into the middle of a block
my_free: 0x55661fbe7fe0 refused: no USED mark -- not the start of a my_malloc block
a + 32 is in range and aligned; the 16 bytes in front of it
are a's data, "xxxx...", so magic reads 0x78787878, not USED
8. double free
my_free(b) free list: 1 block, 1019 units
my_free: 0x55661fbe7f40 refused: already free
my_free(b) again free list: 1 block, 1019 units
the first free wrote FREED in b's header and merged b into
the big block; the second found FREED and stopped. the book's
free would link b in again, inside the big block: the same
memory on the list twice, to be handed out twice
9. the caller writes in front of its block
my_free: 0x55661fbe7fc0 refused: size field runs past the heap
a's header still says USED, but its size is now 1000000
units, 999995 more than the heap holds from a on
10. none of the refused frees touched the list
my_free(a), repaired free list: 1 block, 1024 units
alloc and free again free list: 1 block, 1024 units
one block, all 1024 units: the arena is whole