Exercise 8-7 (Error checking - malloc, calloc, free)

Chapter_8     Exercise_8-6 Exercise_8-8





Exercise 8-7     K&R, p. 189


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




Note:  See also malloc and Exercise_8-6.




CONTENTS:     malloc2.c     calloc2.c




malloc2.c     K&R, p. 186-189         download


#include <stdio.h> // for printf(), fprintf(), stderr, NULL
#include <string.h> // for strcpy()
#include <limits.h> // for ULONG_MAX
#include <sys/sysinfo.h> // for sysconf(), get_avphys_pages()
#include <unistd.h> // for sbrk(), _SC_PAGESIZE
// unistd.h includes stdlib.h, which contains malloc(), free()

//#define _XOPEN_SOURCE_EXTENDED 1 // for sbrk()

#define MAXLEN 100 // max length

#define min(A,B) (((A) < (B)) ? (A) : (B))

typedef long Align; // for alignment to 'long' boundaries

union header // block header:
{
struct
{
union header *ptr; // next block on free list
unsigned size; // size of this block
} s;
Align x; // force alignment pf blocks
};

typedef union header Header;

static Header base; // empty list to get started
static Header *freep = NULL; // start of free list

long unsigned maxmem(); // max memory that can be allocated

// general-purpose storage allocator
void * MAlloc(long unsigned nbytes);
void Free (void *); // put block in free list

int main()
{
char *s = (char *) MAlloc(10);
if (s == NULL)
{
fprintf(stderr, "Could not allocate space\n");
return 1; // end program, signalling error
}
strcpy(s, "Hello!");
printf("%s\n", s);

Free(s);

s = (char *) MAlloc(MAXLEN);
if (s == NULL)
{
fprintf(stderr, "Could not allocate space\n");
return 1; // end program, signalling error
}
strcpy(s, "Hello, world!");
printf("%s\n", s);

Free(s);

return 0;
}

long unsigned maxmem() // max memory that can be allocated
{ // avm - available memory
long unsigned avm = get_avphys_pages() * sysconf(_SC_PAGESIZE);
long unsigned min = min(avm, ULONG_MAX);
// printf("maxmem: %lu bytes\n", min-sizeof(Header));
return min-sizeof(Header);
}

Header * MoreCore(long unsigned);

// general-purpose storage allocator
void * MAlloc(long unsigned nbytes)
{ // nbytes >= 0
if (nbytes == 0)
{return NULL;} // malloc(0) is legal
// else
if (nbytes > maxmem())
{
fprintf(stderr, "MAlloc(): not enough memory available\n");
return NULL;
}

Header *p, *prevp;
long unsigned nunits;
// no of Header units to cover nbytes plus header (at least 1)
nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;

if ((prevp = freep) == NULL) // no free list yet
{ // base is the first node in the circular linked list
base.s.ptr = freep = prevp = &base;
base.s.size = 0; // no space allocated yet
}

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;} // p removed from free list
else // allocate tail end
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp; // next search begins with freep
return (void *)(p+1); // after header
}
if (p == freep) // wrapped around free list
{
if ((p = MoreCore(nunits)) == NULL)
{return NULL;} // none left
// else p->s.ptr has the newly allocated space
}
// here prevp = p, p = p->s.ptr
}
}

#define NALLOC 1024 // minimum no of units to request

// ask system for more memory
Header * MoreCore(long unsigned nu) // no of units
{
if (nu * sizeof(Header) > maxmem())
{
fprintf(stderr, "MoreCore(): not enough memory available\n");
return NULL;
}

void *vp;
Header *up;

if (nu < NALLOC) // allocate at least NALLOC units
{nu = NALLOC;}

vp = sbrk(nu * sizeof(Header)); // allocate space

if (vp == (void *) -1) // no space at all
{return NULL;}

up = (Header *) vp;
up->s.size = nu; // size includes header
// add newly allocated space to the free list:
Free((void *)(up+1)); // +1 - after header

return freep; // freep->s.ptr has the allocated space
}

void Free (void *ap) // put block ap in free list
{ // we assume ap was allocated with MAlloc()
if (ap == NULL) // free(NULL) does nothing
{return;} // like free() from stdlib.h

Header *bp, *p;

bp = (Header *)ap - 1; // point to block header

if (bp->s.size == 0)
{return;} // nothing to free
if (bp->s.size * sizeof(Header) > maxmem())
{
fprintf(stderr, "Free(): too much memory");
return;
}

if (freep == NULL) // MAlloc() has not been called yet
{ // base is the first node in the circular linked list
base.s.ptr = freep = &base;
base.s.size = 0; // no space allocated yet
}

for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
{ // p >= p->s.ptr at the end of list
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
{break;} // freed block at start or end of arena
}
// here bp > p and/or bp < p->s.ptr, p < p->s.ptr or p >= p->s.ptr
if (bp + bp->s.size == p->s.ptr) // join to upper neighbor
{
bp->s.size += p->s.ptr->s.size; // add size of p, including header
bp->s.ptr = p->s.ptr->s.ptr; // add bp, remove p->s.ptr
}
else {bp->s.ptr = p->s.ptr;} // add bp in between p and p->s.ptr
// bp can join both neighbors, one, or none
if (p + p->s.size == bp) // join to lower neighbor
{
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr; // absorb bp into the list
}
else {p->s.ptr = bp;} // bp is in between p and p->s.ptr

freep = p;
}

/*
gcc malloc2.c -o malloc2
./malloc2
Hello!
Hello, world!
*/





Note:  See also GitHub-kr_(8.7), clc-wiki-kr_(8.7), and Check_free_RAM on StackOverflow.









calloc2.c     K&R, p. 186-189         download


#include <stdio.h> // for printf(), fprintf(), stderr, NULL
#include <string.h> // for memset()
#include <stdlib.h> // for srand(), rand()
// stdlib.h declares malloc(), calloc(), free()
#include <limits.h> // for ULONG_MAX
#include <time.h> // for time_t, time()
#include <sys/sysinfo.h> // for sysconf(), get_avphys_pages()
#include <unistd.h> // for sbrk(), _SC_PAGESIZE

//#define _XOPEN_SOURCE_EXTENDED 1 // for sbrk()

#define SIZE 100 // array size

#define min(A,B) (((A) < (B)) ? (A) : (B))

typedef long Align; // for alignment to 'long' boundaries

union header // block header:
{
struct
{
union header *ptr; // next block on free list
unsigned size; // size of this block
} s;
Align x; // force alignment pf blocks
};

typedef union header Header;

static Header base; // empty list to get started
static Header *freep = NULL; // start of free list

long unsigned maxmem(); // max memory that can be allocated

// allocate space for an array:
void * CAlloc(long unsigned nunits, long unsigned size);
// general-purpose storage allocator:
void * MAlloc(long unsigned nbytes);
void Free (void *); // put block in free list

int main()
{
int i;
int *p = (int *) CAlloc(10, sizeof(int));

if (p == NULL)
{
fprintf(stderr, "Could not allocate space\n");
return 1; // end program, signalling error
}

time_t t;

srand((unsigned) time(&t)); // seed rand()

for (i = 0; i < 10; i++)
{p[i] = rand() % 50;}

for (i = 0; i < 9; i++)
{printf("%d, ", p[i]);}
printf("%d\n\n", p[i]);

Free(p);

p = (int *) CAlloc(SIZE, sizeof(int));

if (p == NULL)
{
fprintf(stderr, "Could not allocate space\n");
return 1; // end program, signalling error
}

for (i = 0; i < SIZE; i++)
{p[i] = rand() % SIZE;}

for (i = 0; i < SIZE; i++)
{printf("%d%s", p[i], (i % 10 == 9) ? "\n" : ", ");}

Free(p);

return 0;
}

long unsigned maxmem() // max memory that can be allocated
{ // avm - available memory
long unsigned avm = get_avphys_pages() * sysconf(_SC_PAGESIZE);
long unsigned min = min(avm, ULONG_MAX);
// printf("maxmem: %lu bytes\n", min-sizeof(Header));
return min-sizeof(Header);
}

// allocate space for an array:
void * CAlloc(long unsigned nunits, long unsigned size)
{
long unsigned nbytes = nunits * size;

if (nbytes == 0) // nbytes >= 0
{return NULL;} // calloc(0,0) is legal
// else
if (nbytes > maxmem())
{
fprintf(stderr, "CAlloc(): not enough memory available\n");
return NULL;
}

void *p = MAlloc(nbytes);

if (p == NULL)
{return NULL;} // return p
// else
memset(p, 0, nbytes); // initialize to 0

return p;
}

Header * MoreCore(long unsigned);

// general-purpose storage allocator
void * MAlloc(long unsigned nbytes)
{ // nbytes >= 0
if (nbytes == 0)
{return NULL;} // malloc(0) is legal
// else
if (nbytes > maxmem())
{
fprintf(stderr, "MAlloc(): not enough memory available\n");
return NULL;
}

Header *p, *prevp;
long unsigned nunits;
// no of Header units to cover nbytes plus header (at least 1)
nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;

if ((prevp = freep) == NULL) // no free list yet
{ // base is the first node in the circular linked list
base.s.ptr = freep = prevp = &base;
base.s.size = 0; // no space allocated yet
}

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;} // p removed from free list
else // allocate tail end
{
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp; // next search begins with freep
return (void *)(p+1); // after header
}
if (p == freep) // wrapped around free list
{
if ((p = MoreCore(nunits)) == NULL)
{return NULL;} // none left
// else p->s.ptr has the newly allocated space
}
// here prevp = p, p = p->s.ptr
}
}

#define NALLOC 1024 // minimum no of units to request

// ask system for more memory
Header * MoreCore(long unsigned nu) // no of units
{
if (nu * sizeof(Header) > maxmem())
{
fprintf(stderr, "MoreCore(): not enough memory available\n");
return NULL;
}

void *vp;
Header *up;

if (nu < NALLOC) // allocate at least NALLOC units
{nu = NALLOC;}

vp = sbrk(nu * sizeof(Header)); // allocate space

if (vp == (void *) -1) // no space at all
{return NULL;}

up = (Header *) vp;
up->s.size = nu; // size includes header
// add newly allocated space to the free list:
Free((void *)(up+1)); // +1 - after header

return freep;
}

void Free (void *ap) // put block ap in free list
{ // we assume ap was allocated with MAlloc()
if (ap == NULL) // free(NULL) does nothing
{return;} // like free() from stdlib.h

Header *bp, *p;

bp = (Header *)ap - 1; // point to block header

if (bp->s.size == 0)
{return;} // nothing to free
if (bp->s.size * sizeof(Header) > maxmem())
{
fprintf(stderr, "Free(): too much memory");
return;
}

if (freep == NULL) // MAlloc() has not been called yet
{ // base is the first node in the circular linked list
base.s.ptr = freep = &base;
base.s.size = 0; // no space allocated yet
}

for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
{ // p >= p->s.ptr at the end of list
if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
{break;} // freed block at start or end of arena
}
// here bp > p && bp < p->s.ptr, p < p->s.ptr or p >= p->s.ptr
if (bp + bp->s.size == p->s.ptr) // join to upper neighbor
{
bp->s.size += p->s.ptr->s.size; // add size of p, including header
bp->s.ptr = p->s.ptr->s.ptr; // add bp, remove p->s.ptr
}
else {bp->s.ptr = p->s.ptr;} // add bp in between p and p->s.ptr
// bp can join both neighbors, one, or none
if (p + p->s.size == bp) // join to lower neighbor
{
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr; // absorb bp into the list
}
else {p->s.ptr = bp;} // bp is in between p and p->s.ptr

freep = p;
}

/*
gcc calloc2.c -o calloc2
./calloc2
40, 38, 39, 42, 48, 5, 25, 46, 16, 35

24, 97, 92, 69, 14, 91, 5, 22, 21, 35
80, 67, 69, 46, 74, 54, 73, 15, 94, 76
63, 35, 66, 5, 79, 64, 60, 54, 63, 26
39, 39, 76, 32, 9, 90, 75, 14, 64, 48
1, 97, 15, 70, 43, 90, 76, 68, 57, 22
44, 21, 9, 62, 26, 88, 27, 38, 43, 42
17, 34, 81, 45, 66, 90, 87, 93, 56, 51
41, 57, 48, 57, 79, 43, 99, 55, 12, 56
30, 8, 29, 39, 71, 7, 28, 50, 98, 71
92, 15, 5, 25, 60, 24, 16, 47, 17, 24
*/







Chapter_8     Exercise_8-6 BACK_TO_TOP Exercise_8-8



Comments

Post a Comment

Popular posts from this blog

Contents

Programming_Languages_blog     C_Prog_blogs Chapter_1     Advanced_Linux_Prog     C_in_C++ NAVIGATION     CHAPTERS     CONTENTS     EXERCISES     INDEX     ABOUT     CONTACT Chapter_1  (Introduction) Hello     Exercise_1-1     Exercise_1-2     quotes     Temperature_Programs     Truncate     Exercise_1-3     Exercise_1-4     for()_variant     Exercise_1-5     #define_directive     copy     Exercise_1-6     Exercise_1-7     copyEOF     count     Exercise_1-8     Exercise_1-9 ...
Read more

Blogger Page Margins in Contempo

NAVIGATION     CHAPTERS     CONTENTS     EXERCISES     INDEX     ABOUT     CONTACT Navigate Blogger left panel   →   Theme   →   CUSTOMIZE drop-down menu   →   Edit HTML CONTENTS:     Left_Margin     Right_Margin     Page_Content_Fills_the_Screen Left Margin No Left Margin .centered-bottom,.centered-top-container,.centered-top-placeholder{ padding:0 0px } Original CSS .centered-bottom,.centered-top-container,.centered-top-placeholder{ padding:0 16px } Right Margin No Right Margin (No Vertical Ads on blog) .vertical-ad-container { float: right; margin-right: 0px; width: 0px; } .page_body.has-vertical-ads .centered .centered-bottom { display: inline-block; width: calc(100% - 0px); } Original CSS .vertical-ad-contain...
Read more