#include <stdio.h>
#include <limits.h> //UINT_MAX
#include <unistd.h> //sbrk
//compile with: gcc -Wall -Wextra cc-c.c -o cc-c
//run with: ./cc-c
//K&R2 Exercise 8-6. The standard library function calloc(n,size)
//returns a pointer to n objects of size size, with the storage
//initialized to zero. Write calloc, by calling malloc or by modifying it.
//
//By calling malloc: my_calloc = check n*size, my_malloc(n*size), then
//zero those bytes. The allocator underneath is the 8.7 block's, as
//the book has it (minus that block's "not the book's" extras).
//
//Two things calloc does that malloc(n*size) alone doesn't:
// - zeroing. malloc hands back whatever the last owner left there.
// - the multiply is checked. n*size can wrap past the top of unsigned
// and come out small; malloc would then happily return a tiny block
// for a huge request, and the caller would write far past its end.
// The real calloc returns NULL instead; so does this one.
//
//Modifying malloc instead would mean a second copy of the whole search
//loop with a clearing step before each return -- calling it is the
//"reuse, don't repeat" idiom morecore already uses with free.
//
//main:
// 1. fresh memory from sbrk is already zero -- so it proves nothing
// 2. reused memory is dirty: my_malloc returns it as is
// 3. my_calloc on the same block: zeroed
// 4. typed use: n ints, all 0
// 5. the overflow check
// 6. my_calloc(0, size)
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
} s;
Align x; //force alignment of blocks; never used
};
typedef union header Header;
static Header base; //empty list to get started
static Header *freep = NULL; //start of free list
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;
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 = morecore(nunits)) == NULL)
return NULL; //none left
}
}
//my_calloc: n objects of size size, all bytes zero; NULL on overflow
void *my_calloc(size_t n, size_t size)
{
char *p, *q;
unsigned nbytes;
//IDIOM: overflow check by division -- n*size > MAX is the test we
//want, but computing n*size is exactly what overflows; size > MAX/n
//asks the same question without multiplying. n != 0 guards the /
if (n != 0 && size > UINT_MAX / n)
return NULL;
nbytes = n * size;
//IDIOM: assign inside the test -- get the block and check it at once
if ((p = my_malloc(nbytes)) == NULL)
return NULL;
//IDIOM: walk a char pointer to an end pointer -- a byte at a time,
//whatever the objects' type; memset(p, 0, nbytes) does the same
for (q = p; q < p + nbytes; q++)
*q = 0;
return p;
}
#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;
my_free((void *)(up+1));
return freep;
}
//my_free: put block ap in free list
void my_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;
}
static int nonzero(void *ap, unsigned nbytes) //how many bytes are not 0
{
unsigned char *p = ap;
int count = 0;
while (nbytes-- > 0)
if (*p++ != 0)
count++;
return count;
}
int main(void)
{
char *a, *b, *c;
int *v;
void *z1, *z2;
size_t n, size, i;
printf("1. fresh memory: the first my_malloc gets a new sbrk chunk\n");
a = my_malloc(64);
printf(" a = my_malloc(64): nonzero bytes %d of 64\n", nonzero(a, 64));
printf(" the kernel zeroes every page it gives a process (or one\n"
" program could read another's leftovers) -- so fresh memory\n"
" can't show whether calloc clears anything. reused memory can\n");
printf("\n2. dirty memory: fill a, free it, ask for the same size again\n");
for (i = 0; i < 64; i++)
a[i] = (char) 0xAB;
my_free(a);
b = my_malloc(64);
printf(" b = my_malloc(64): b %s a, nonzero bytes %d of 64, b[0] 0x%02X\n",
b == a ? "==" : "!=", nonzero(b, 64), (unsigned char) b[0]);
printf(" free merged a back into the chunk; the next 64 bytes were\n"
" carved off the same tail -- same address, a's 0xAB still in\n"
" it. malloc promises space, not contents\n");
printf("\n3. the same again, through my_calloc\n");
my_free(b);
c = my_calloc(16, 4);
printf(" c = my_calloc(16, 4): c %s a, nonzero bytes %d of 64\n",
c == a ? "==" : "!=", nonzero(c, 64));
printf(" 16*4 = 64 bytes: same request, same block, now clean\n");
my_free(c);
printf("\n4. typed use: calloc's two arguments read as \"10 ints\"\n");
//IDIOM: n, sizeof *v -- size from the pointer, not the type name,
//so the call stays right if v's type changes
v = my_calloc(10, sizeof *v);
printf(" v = my_calloc(10, sizeof *v):");
for (i = 0; i < 10; i++)
printf(" %d", v[i]);
printf("\n all bits zero is 0 for every integer type. the standard\n"
" doesn't promise it is 0.0 or a null pointer too -- it is on\n"
" every machine you'll meet, but = 0 / = NULL is the portable way\n");
my_free(v);
printf("\n5. the overflow check\n");
n = 65536;
size = 65537;
printf(" n %zu * size %zu = %zu; UINT_MAX is %u\n",
n, size, n * size, UINT_MAX);
printf(" squeezed into my_malloc's unsigned: %u bytes -- 64 KB for\n"
" a 4 GB request; filling n objects would run 4 GB past its end\n",
(unsigned)(n * size));
printf(" my_calloc(65536, 65537) = %s\n",
my_calloc(n, size) == NULL ? "NULL" : "not NULL");
printf(" size > UINT_MAX / n: 65537 > %u, so it stops before multiplying\n",
UINT_MAX / 65536);
printf("\n6. my_calloc(0, 8) twice: zero bytes still costs a header\n");
z1 = my_calloc(0, 8);
z2 = my_calloc(0, 8);
printf(" z1 %s NULL, z2 %s NULL, z1 %s z2\n",
z1 == NULL ? "==" : "!=", z2 == NULL ? "==" : "!=",
z1 == z2 ? "==" : "!=");
printf(" n == 0 skips the division (no / 0), the loop runs 0 times,\n"
" and my_malloc(0) gives a real, distinct pointer\n");
return 0;
}
win@DESKTOP-MEIH88T:~/webdev-projects$ gcc -Wall -Wextra cc-c.c -o cc-c
win@DESKTOP-MEIH88T:~/webdev-projects$ ./cc-c
1. fresh memory: the first my_malloc gets a new sbrk chunk
a = my_malloc(64): nonzero bytes 0 of 64
the kernel zeroes every page it gives a process (or one
program could read another's leftovers) -- so fresh memory
can't show whether calloc clears anything. reused memory can
2. dirty memory: fill a, free it, ask for the same size again
b = my_malloc(64): b == a, nonzero bytes 64 of 64, b[0] 0xAB
free merged a back into the chunk; the next 64 bytes were
carved off the same tail -- same address, a's 0xAB still in
it. malloc promises space, not contents
3. the same again, through my_calloc
c = my_calloc(16, 4): c == a, nonzero bytes 0 of 64
16*4 = 64 bytes: same request, same block, now clean
4. typed use: calloc's two arguments read as "10 ints"
v = my_calloc(10, sizeof *v): 0 0 0 0 0 0 0 0 0 0
all bits zero is 0 for every integer type. the standard
doesn't promise it is 0.0 or a null pointer too -- it is on
every machine you'll meet, but = 0 / = NULL is the portable way
5. the overflow check
n 65536 * size 65537 = 4295032832; UINT_MAX is 4294967295
squeezed into my_malloc's unsigned: 65536 bytes -- 64 KB for
a 4 GB request; filling n objects would run 4 GB past its end
my_calloc(65536, 65537) = NULL
size > UINT_MAX / n: 65537 > 65535, so it stops before multiplying
6. my_calloc(0, 8) twice: zero bytes still costs a header
z1 != NULL, z2 != NULL, z1 != z2
n == 0 skips the division (no / 0), the loop runs 0 times,
and my_malloc(0) gives a real, distinct pointer