Memory Allocation and Deallocation

This exercise must be done in the C programming language under Linux (make sure it runs on Ubuntu 16.04 64-bit).

----------------------------------------------

mymalloc.c:

/* Memory allocation example */

#include "mymalloc.h" #include #include #include #include #include #include

/* base address of heap */ void * base = NULL;

/* Searching for a free segment */ static t_header find_header(t_header *last, size_t size) { t_header b = base; /* start from heap base address */ /* first fit algorithm */ while (b && !(b->free && b->size >= size)) { *last = b; /* save address of last visited segment */ b = b->next; } /* if success, return segment address else NULL */ return (b); }

/* Extending the heap */ static t_header extend_heap(t_header last , size_t s) { void * sb; t_header b; /* ptr to header being created */ b = sbrk(0); /* get current address of break */ /* increment the break */ sb = sbrk(header_SIZE + s); /* the following verification is in accordance with Linux man pages */ if (sb == (void *) -1) { /* failure! */ return (NULL); } /* success! */ b->size = s; b->next = NULL; b->prev = last; b->ptr = (char *)b + header_SIZE; if (last) { last ->next = b; } b->free = 0; return (b); }

/* header splitting */ void split_header(t_header b, size_t s) { t_header new; /* ptr to header being created */ new = (t_header)( (char *)b->ptr + s ); /* addr of new header */ new->size = b->size - s - header_SIZE ; /* size of new header */ new->next = b->next; new->prev = b; new->free = 1; /* In the following, "header_SIZE" is in bytes. Using the type * cast "(char *)", the "void *" pointer "p" is converted to a * character pointer. Hence, the pointer subtraction is done in * the byte unit. The result is converted as a "t_header" pointer. */ new->ptr = (char *)new + header_SIZE; /* addr of available mem in new header */ b->size = s; /* update size of old header */ b->next = new; if (new->next) { new->next->prev = new; } }

/* Memory allocation function * size = number of bytes * returns pointer to allocated memory, * NULL in case of failure */ void * mymalloc(size_t size) { t_header b, last; size_t s; s = ALIGN(size); /* alignment of size */ /* not first time */ if (base) { /* find a header */ last = base; b = find_header(&last, s); if (b) { /* can split? */ if ((b->size - s) >= (header_SIZE + 8)) { split_header(b, s); } b->free = 0; } else { /* no fitting header, extend the heap */ b = extend_heap(last, s); if (!b) return (NULL); } /* first time */ } else { b = extend_heap(NULL, s); if (!b) return (NULL); /* set base address of heap */ base = b; } return (b->ptr); }

/* free function */ void myfree(void *p) { fprintf(stdout, "myfree not implemented "); }

---------------------------------------------------------------------

mymalloc.h?

#ifndef MYALLOC_H #define MYALLOC_H

#include

/* header structure */ struct s_header { size_t size; /* in bytes */ int free; /* 1=available; 0=not available */ struct s_header *next; /* ptr to next header */ struct s_header *prev; /* ptr to previous header */ void * ptr; /* addr of data part, after header */ }; typedef struct s_header * t_header;

/* segment must begin at an address on a multiple of alignment size, Linux requires 8-byte alignment */ #define ALIGNMENT 8 // must be a power of 2 #define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~(ALIGNMENT-1))

/* header size */ # define header_SIZE (ALIGN(sizeof(struct s_header)))

/* malloc function */ void * mymalloc(size_t size );

/* free function */ void myfree(void *p);

#endif

-----------------------------------------------------------

tester.c:

/* Memory allocation tester program */ #include #include #include #include #include #include "mymalloc.h"

void main(int argc, char *argv[]) { int sizes[] = { 1024, 2048, 4096 }; int N = 3; int i; void * p[N];

fprintf(stdout, " "); fprintf(stdout, "Initial program break: %10p ", sbrk(0)); fprintf(stdout, "*** First test *** "); for (i = 0; i fprintf(stderr, "Allocating %d bytes ", sizes[i]); p[i] = mymalloc(sizes[i]); if (p[i]==NULL) { fprintf(stderr, "mymalloc failed! "); exit(EXIT_FAILURE); } fprintf(stdout, "After allocation, program break is: %10p ", sbrk(0)); } for (i = N-1; i >=0; i--) { fprintf(stderr, "Address being freed: %10p ", p[i]); myfree(p[i]); fprintf(stdout, "After freeing, program break is: %10p ", sbrk(0)); }

fprintf(stdout, "*** 2nd test *** "); fprintf(stdout, "Testing freeing invalid address "); myfree(NULL); fprintf(stdout, "Program break is: %10p ", sbrk(0));

fprintf(stdout, "*** 3rdt test *** "); for (i = 0; i fprintf(stderr, "Allocating %d bytes ", sizes[i]); p[i] = mymalloc(sizes[i]); if (p[i]==NULL) { fprintf(stderr, "mymalloc failed! "); exit(EXIT_FAILURE); } fprintf(stdout, "After allocation, program break is: %10p ", sbrk(0)); } for (i = 0; i fprintf(stderr, "Address being freed: %10p ", p[i]); myfree(p[i]); fprintf(stdout, "After freeing, program break is: %10p ", sbrk(0)); }

fprintf(stdout, "*** 4th test *** "); fprintf(stdout, "Final program break is: %10p ", sbrk(0));

return; }

-----------------------------------------------

Makefile:

all: mymalloc.o tester.o cc -o tester mymalloc.o tester.o mymalloc.o: mymalloc.c mymalloc.h cc -c mymalloc.c tester.o: tester.c cc -c tester.c clean: rm -f *.o *~ core *~ tester

Extend the memory allocation example with a segment deallocation function, in- cluding a fusion function that merges headers of adjacent segments. The deallocation function must have the signature: void myfree(void *p) The pointer must be verified using the field "voidpt the header You may reuse and adapt code returned by Google, but give credit to and cite your SourceS Test your software with the provided tester program (tester.c) Here is a sample execution: $ ./tester Initial program break: 0xaea000 First test Allocating 1024 bytes After allocation, program break is:0xaea428 Allocating 2048 bytes After allocation, program break is Allocating 4096 bytes After allocation, program break is: Address being freed 0xaeac78 After freeing, program break is 0xaeac50 Address being freed 0xaea450 After freeing, program break is: Oxaea428 Address being freed: 0xaea028 After freeing, program break is 0xaea000 Oxaeac50 0xaebc78 2nd test Testing freeing invalid address Program break is Oxaea000 3rdt test* Allocating 1024 bytes After allocation, program break is: Allocating 2048 bytes After allocation, program break is: Allocating 4096 bytes After allocation, program break is Address being freed 0xaea028 After freeing, program break is 0xaebc78 Address being freed Oxaea45 After freeing, program break i Oxaebc78 Address being freed: Oxaeac78 After freeing, program break is 0xaea000 *4th test Final program break is: Oxaea428 Oxaeac50 Oxaebc78 0xaea000