A Sense of Doubt blog post #1633 - Memory Management - a program written in the C language

A Sense of Doubt blog post #1633 - Memory Management - a program written in the C language

Hi there reader,

New feature. Posting my code to my blog to show off both coding skills and my ability to write documentation for code.

In fact, to get all the samples up in time, I may have to post extra posts rather than one a day. I will also have posts for collected code samples and collected writing samples.

I chose this program as my first sample because it's my favorite. As the documentation explains, I wrote a memory management program in the C programming language.

One caveat with this sample: the code is OVER-DOCUMENTED. The documentation here is as much for me as part of my study, to understand all the functions and concepts even years later (as my memory is faulty and C can be somewhat cryptic) as well as helping a user or a future coder who must maintain this code to understand it.

I am considering trimming some of the extra comments that may not be needed or moving them around so that the code is more readable.

For now, this is what I am sharing as it's the original state of the program.

For readers, good news, I managed to preserve the original text editor's state of the code with everything color-identified. The documentation comments are in green. Commands are in blue. Basic code is in black.

For now, this is what it is. And it runs (with the edits for "includes" as noted. Try it.)


// WHAT: ASSIGNMENT TWO - MY MALLOC, CALLOC, REALLOC, AND FREE

// MORE WHAT: a program written in the C programming language
// WHERE: For CS2240 - Trenary

// WHO: Chris Tower and Spider Friends

// WHEN: It is now Monday March, 2 2015 but I have been working on this for weeks.

// HOW: A mix of super soldier serum, mutant x genes, and single malt scotch.

// WHAT THIS PROGRAM DOES: Using system call sbreak, this program replicates versions of the standard library functions malloc, calloc, realloc, and free. Ultimately, using an mreplace program, these functions substitute for the standrad library functions and perform via a series of tester programs. Mine passed! :-)

//DESIGN NOTES AS OF 1503.02 SUBMISSION: Right now, after many hours and weeks of labor, this thing successfully performs all functions but is not as efficient as it could be. Time permitting, I would add a function to split big blocks and fuse together smaller blocks. Originally, I wanted to do a bin system to sort blocks by size, but this is too ambitious at this stage with a third assignment (SHELL) to work on.

// ****************** INCLUDES **********************

//Many includes. All needed? Possibly.

// Includes use "<" and ">" around dot h files but here in html land these disappear, so an edit will be needed to run the program as I substituted "" for the brackets.

#include "stdio.h"
#include "unistd.h"
#include  "sys/types.h"
#include "stdlib.h" // For use of "atoi" and calloc etc.
#include  "fcntl.h"
#include  "sys/stat.h"
#include  "errno.h"
#include  "string.h"
#include  "assert.h"
#include  "apue.h" // except this one uses quotes apparently
// compile program with "error.c"

//******************* Meta Data Header Struct ***********

// Structure for meta-data (header) information added to start of each memory block for record keeping. Size as a type of size_t holds size of block, an int for a boolean flag holds a 0 (zero) when block is free and a 1 (one) when block is used. Two pointers *next and *prev hold pointers to start of next block and previous block. A one element char data [1] array provides a pointer to the end of the metadata header or rather the start of the data block to be used, iE the allocated memory space, but this char is not calculated as part of the size of the meta-data header.

// The struct is type defined to be referred to as simply "meta."

typedef struct _meta {

size_t        size;

int           frflag;

struct _meta         *next;

struct _meta         *prev;

char data [1];

} meta;

// ************************* Variables *******************

// Best to initialize meta head pointer (the pointer to the start of the meta data header at the start of the block to NULL as first time through it is NULL (no allocated blocks yet; no written meta data).

// HEADPTR serves as a pointer of type meta (my struct) to give me a ptr to the first block in the linked list. Could also be global or base pointer.

meta *headptr = NULL;

//********* DEFINES **********************************

/* This is the header size in bytes. */

# define META_SIZE 32

//Explanation of META_SIZE: *  two 8 byte structs, one 8 byte size_t (unsigned long) and a 4 byte int ...not including char data [1]; However, PLEASE NOTE, Meta Size should be 24. If I arranged the variables differently, I could get away with 24. With this ordering of variables, C pads out all the elements to the longest type, which is 8 bytes. I had many alignment problems until I reset META_SIZE this way. And I am leaving it this way because it works, though at some point I may do the science to check the other arranegement, which I believe has to do with moving the int for the free flag (frflag).

// When changing this for the tester, change void *my_free(void*); to void free(void*); so lose the star before the free because the library function does not return a void *free(void*).

//***** MODULE DECLARATIONS**********************

void *my_malloc(size_t);

void *my_free(void*);

void *my_calloc(size_t, size_t);

void *my_realloc(void*, size_t);

int main (int argc, char* argv[])

{

// The following statements, all of MAIN, run tests on malloc, free, calloc, and realloc using strings, which are copied into the memory space allocated. PLEASE NOTE USE OF STRNCOPY, needs to keep the NULL at the end of the string, so each size of the string given to strncopy is 1 more than the length of the string. For instance, "did it work" is 12 characters in length including spaces but 13 is passed to strncopy so that it grabs the NULL at the end of the string.

//Simply, malloc 32, copy 13 character string into space (12+NULL) and write out string. If this works, I have a successful Malloc at least the first time through the list.

char *string = my_malloc(32);

strncpy(string, "did it work?", 13);

printf("\n The string is = %s\n", string);

//Let's try malloc again with a bigger string. NOTE: need to use a different variable for the string.

char *nextstring = my_malloc(55);

strncpy(nextstring, "it worked again.", 17);

printf("\n The string is = %s\n", nextstring);

//Now, I will perform magic and free the previously allocated block of 55 into which I wrote nextstring. I will pass nextstring to free and free it. I will than malloc 12 into that block, which is 55 as in the above. I should see 55 again in my tester print statement as this is the blocksize.

my_free(nextstring);

char *xtstring = my_malloc(12);

strncpy(xtstring, "bork", 5);

printf("\n The string is = %s\n", xtstring);

//REalloc next. Take the xtstring used above and send it to realloc and ask for another 20 bytes. Then when I test I send in a 21 length string (though the block is much bigger).

xtstring = my_realloc(xtstring, 20);

strncpy(xtstring, "Did the realloc work", 21);

printf("\n The string is = %s\n", xtstring);

// Just another malloc test. I originally had four of them before I added the other functions.

char *tstring = my_malloc(20);

strncpy(tstring, "fourth test!", 13);

printf("\n The string is = %s\n", tstring);

//Lastly, testing calloc, which takes number of elements and blocksize. Elements is just one, for a char, then size is the previous block in tstring, which is 20. Calloc then writes zeroes in that space, so my print tester should have nothing after the equals sign, which it does.

tstring = my_calloc(1, 20);

printf("\n The calloc string is = %s\n", tstring);

} // end bracket of main

void *my_malloc(size_t Blocksize)

{

meta *ptr; // Setting up a ptr to type meta (the struc) in my malloc for use in the malloc process.

if (headptr == NULL) // Checks headptr, if it's NULL then this is the first use of malloc and so I can go ahead and malloc the first block in the list, which is a different process than adding a block to the end of the list or writing into a free block found while examining the list.

{

headptr = sbrk(0); //sbrk(0) gives me a pointer to the current position on the heap, which here is the start of the memory area, which is what I want in a headptr, a pointer to the beginning of the linked list.

ptr = sbrk (META_SIZE + Blocksize); // here's the sbrk of the memory for malloc

if (ptr == (void *) -1) //*Error check on the system call, sbrk fails/

{

return (NULL );

}

// Now, I write all the fields in the meat data header using the meta *ptr I created above. Size is Blocksize. This is the value passed in from main. Frflag is the boolean marking free (0) or used (1), and so I mark used here. Then the next and previous ptrs are empty as this is the first memory block created.

ptr -> size = Blocksize;

ptr -> frflag = 1;

ptr -> next = NULL;

ptr -> prev = NULL;

} // end bracket for if statement checking headptr for FIRST TIME THROUGH

else          // ELSE if not first time through then do the following instead.

{

// *select pointer is created here simply to step through blocks from meta data header to header, so headptr is selected to start at the beginning of the linked list. *temp is created to store each select as I iterate through the list to ensure I examine the last block of memory. I had trouble with this in my initial design because my while loop checked for next pointer being NULL, which it will be with the last item in the list. But in that design, the while bailed out before ite checked that memory block, which is bad. So I switched to a do-while loop, which doesn't check test to exit the loop until after iterating.

meta *select = headptr;

meta *temp;

do {

if (select -> size > Blocksize && select -> frflag == 0) 

// Yay!! Free block found because frflag is zero. Also, checking for size being big enough. Did not yet bother with equals to or greater than.

{

      

select -> frflag = 1; // Since I found a free block, I am using it, so I set the flag to used. I do this in my SELECT ptr as this is the struc I am using as I iterate.

// Printer test statement. Here I print the pointer address, as in the memory location of the beginning of the entire block of memory. Then I print the position of the beginning of the data area allocated, after the meta data header. I use that char data[1] that I created for this position. Then just for fun, I print the blocksize.

fprintf(stderr, "pointer address %lu\t data start %lu\t size %d\n", (unsigned long int)select, (unsigned long int)select -> data, (int)select -> size);

return select -> data; // Returns a pointer to start of the data block for use (after the meta-data header). Again, this is that char data[1].

} // end bracket of if checking size & for checking free flag

temp = select; // Store select in temp to ensure I look at all blocks in the list.

select = select -> next; // iterate, move select to the next block of data

} while (select != NULL); // end bracket for while loop

// The while loop iterates until the select is empty, which is will be after I have checked all blocks to find free ones. If I find no free blocks, then I have to sbrk a new one at the end of the list, which is what the next statements do. If the program finds a free block, it returns with the pointer so it exits the while loop thta way and does not get here.

temp -> next = sbrk(0); // Use sbrk(0) to get current heap position and put that in the next field of the temp struc.

//sbrk some memory just like before with meta size added for header data. I use ptr here as before because this the generic reusable ptr for allocating and filling the header with data.

ptr = sbrk (META_SIZE + Blocksize);

if (ptr == (void *) -1) //*Error check on the system call, sbrk fails/

{

return (NULL );

}

// Fill data fields as before though this time I put temp into previous because I was saving that value gained from sbrk(0). Adding to the end of the list, so next is NULL.

ptr -> size = Blocksize;

ptr -> frflag = 1;

ptr -> next = NULL;

ptr -> prev = temp;

} // end bracket of else not first time statement

// Tester as before.

fprintf(stderr, "pointer address %lu\t data start %lu\t size %d\n", (unsigned long int)ptr, (unsigned long int)ptr -> data, (int)ptr -> size);

return ptr -> data; // Returns a pointer to start of the data block for use (after the meta-data header).

} // end bracket of my_malloc

void *my_free(void *ptr)

{

// Though complicated looking, this next statement simply backs up the pointer by the size of the meta data; however, it uses complicated casting of the ptr into a char * and that plus the subtraction all into a meta * and all that in a meta *p. Then I access just p (that meta *p) to switch the free flag to zero for free. That's it for FREE!

meta *p = (meta *)((char *)ptr - META_SIZE);

p -> frflag = 0;

} // end bracket for free module

void *my_calloc(size_t Elements, size_t Blocksize)

{

//Calloc receives number of Elements, I pas just one char, and the blocksize to then write zeroes. Size is modied with multiplication of these two values and passed to malloc, which returns a ptr to the memory. Then I use  memset to write zeroes of that size to that space starting at ptr and then return the ptr to the calling function, which is main.

  size_t size = Elements * Blocksize;

  void *ptr = my_malloc(size);

  memset(ptr, 0, size);

  return ptr;

} // end bracket for calloc module

void *my_realloc(void *ptr, size_t Blocksize)

{

if (!ptr){

return my_malloc(Blocksize);

// pointer is NULL (no pointer); there's no memory to realloc, so just malloc.

}

//This next statement is the same as the one in free to move the pointer back by the meta data size.

meta *p = (meta *)((char *)ptr - META_SIZE);

//Here I did do a greater or equals for reallocing.

if (p -> size >= Blocksize)

{

       //print tester as before but note use of p here as that's the current pointer I am working with.

       fprintf(stderr, "pointer address %lu\t data start %lu\t size %d\n", (unsigned long int)p, (unsigned long int)p -> data, (int)p -> size);

       return ptr;

       // Enough space exists, so return the pointer.

}

//Otherwise, if not enough space, then I need to realloc. Malloc new space and then free old space. then copy old data to new space.

void *new_ptr; // Need a new ptr for this work.

new_ptr = my_malloc(Blocksize); //Do the malloc.

if (!new_ptr) //If there is no newptr then error.

{

return NULL;  // need to set errono on failure.

}

// copy the memory new ptr is the new space or destination, ptr is the old space and it gets freed next, then use p, which is set all the way at the top of the function with the meta *p to set the new size of the realloced space.

memcpy(new_ptr, ptr, p -> size);

free(ptr);

return new_ptr; // returns the new ptr for the new space.

}

// END of the CODE for "memmanage.c"


+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

- Bloggery committed by chris tower - 1908.10 - 10:10

- Days ago = 1498 days ago

- New note - On 1807.06, I ceased daily transmission of my Hey Mom feature after three years of daily conversations. I plan to continue Hey Mom posts at least twice per week but will continue to post the days since ("Days Ago") count on my blog each day. The blog entry numbering in the title has changed to reflect total Sense of Doubt posts since I began the blog on 0705.04, which include Hey Mom posts, Daily Bowie posts, and Sense of Doubt posts. Hey Mom posts will still be numbered sequentially. New Hey Mom posts will use the same format as all the other Hey Mom posts; all other posts will feature this format seen here.