Efficient Memory Allocation in C

Code Files

Core Files

#include <stdio.h>
#include <stdlib.h>
#include "mymalloc.h"

#define MEMLENGTH 4096

static union {
    char bytes[MEMLENGTH];
    double not_used; 
} heap;

typedef struct header {
        int size; // size of the chunk 
        int is_allocated; // if 0 empty if 1 full
} header; 

static int initialized = 0;
static header *head = NULL;
void leak_report();

void allocation(){
    if(!initialized){
        head = (header*) heap.bytes;
        head -> size = MEMLENGTH - sizeof(header);  
        head -> is_allocated = 0;  
        initialized = 1;   
        atexit(leak_report);
    }
}

void * mymalloc(size_t size, char *file, int line){
    allocation();
    header *current = head;
    if((size % 8) != 0){
        size = size + (8 - (size % 8));
    }
    while ((char*)current < heap.bytes + MEMLENGTH) {
        if((current -> is_allocated) == 0 && current -> size >= size){
            int old_size = current->size;
            current -> size = size;
            current -> is_allocated = 1;
            header *temp = current; 
            if((old_size) > (size + sizeof(header))){
                header *next = (header *) ((char *)current + sizeof(header) + size);
                next -> size = old_size - size - sizeof(header);
                next -> is_allocated = 0;
            }
            return (void*) ((char*)temp + sizeof(header));
        }
        current = (header *)((char *)current + (sizeof(header)) + current -> size);
    }
    fprintf(stderr, "malloc: Unable to allocate %zu bytes (%s:%d)\n", size, file, line);
    return NULL;
}

void myfree(void *ptr, char *file, int line){
    allocation();
    if(!ptr){ return; }
    if ((char*)ptr < (heap.bytes + sizeof(header)) || (char*)ptr >= (heap.bytes + MEMLENGTH)) {
        fprintf(stderr, "free: Inappropriate pointer (%s:%d)\n", file, line);
        exit(2);
    }
    header *r = head;
    int is_in = 0;
    while((char*)r < heap.bytes + MEMLENGTH){
        if ((char*)r + sizeof(header) == (char*)ptr){
            is_in = 1;
            break;
        }
        r = (header *)((char*)r + sizeof(header) + r -> size);
    }
    if(!is_in){
        fprintf(stderr, "free: Inappropriate pointer (%s:%d)\n", file, line);
        exit(2);
    }
    header *chunk = (header *)((char *) ptr - sizeof(header));
    if (chunk -> is_allocated == 0) {
        fprintf(stderr, "free: Inappropriate pointer (%s:%d)\n", file, line);
        exit(2);
    }
    chunk -> is_allocated = 0;
    header *c = (header*) heap.bytes; 
    header *p = NULL;
    while((char*)c < (char*)chunk){
        p = c;
        c = (header *)((char *)p + sizeof(header) + p -> size );
    }
    if(p != NULL && p->is_allocated == 0){            
        p ->size += chunk -> size + sizeof(header);      
        chunk = p;        
    }
    header *next = (header *) ((char *)(chunk) + sizeof(header) + chunk -> size);
    while ((char*)next < heap.bytes + MEMLENGTH - sizeof(header) && next->is_allocated == 0) {
        if (((char *)next >= heap.bytes + MEMLENGTH)){ break; }
        chunk -> size += sizeof(header) + next -> size;
        next = (header *) ((char *)(chunk) + sizeof(header) + chunk -> size);
    }
}

void leak_report(){
    header *h = head;
    int memory = 0;
    int chunks = 0;
    while((char*)h < heap.bytes + MEMLENGTH){
        if(h -> is_allocated == 1){
            memory += h -> size;
            chunks += 1;
        }
        h = (header *)((char *)h + sizeof(header) + h -> size );
    }
    if(chunks > 0){
        fprintf(stderr, "mymalloc: %d bytes leaked in %d objects\n", memory, chunks);
    }
}

#ifndef _MYMALLOC_H
#define _MYMALLOC_H

#define malloc(X) mymalloc(X, __FILE__, __LINE__)
#define free(X) myfree(X, __FILE__, __LINE__)

void * mymalloc(size_t size, char *file, int line);
void   myfree(void *ptr, char *file, int line);

#endif

all: memgrind memtest Test1 Test2 Test3 Test4_1 Test4_2 Test4_3 Test5
memgrind: memgrind.o mymalloc.o
	gcc memgrind.o mymalloc.o -o memgrind
memtest: memtest.o mymalloc.o
	gcc memtest.o mymalloc.o -o memtest
Test1: Test1.o mymalloc.o
	gcc Test1.o mymalloc.o -o Test1
Test2: Test2.o mymalloc.o
	gcc Test2.o mymalloc.o -o Test2
Test3: Test3.o mymalloc.o
	gcc Test3.o mymalloc.o -o Test3
Test4_1: Test4_1.o mymalloc.o
	gcc Test4_1.o mymalloc.o -o Test4_1
Test4_2: Test4_2.o mymalloc.o
	gcc Test4_2.o mymalloc.o -o Test4_2
Test4_3: Test4_3.o mymalloc.o
	gcc Test4_3.o mymalloc.o -o Test4_3
Test5: Test5.o mymalloc.o
	gcc Test5.o mymalloc.o -o Test5
mymalloc.o: mymalloc.c mymalloc.h
	gcc -c mymalloc.c
memgrind.o: memgrind.c mymalloc.h
	gcc -c memgrind.c
memtest.o: memtest.c mymalloc.h
	gcc -c memtest.c
Test1.o: Test1.c mymalloc.h
	gcc -c Test1.c
Test2.o: Test2.c mymalloc.h
	gcc -c Test2.c
Test3.o: Test3.c mymalloc.h
	gcc -c Test3.c
Test4_1.o: Test4_1.c mymalloc.h
	gcc -c Test4_1.c
Test4_2.o: Test4_2.c mymalloc.h
	gcc -c Test4_2.c
Test4_3.o: Test4_3.c mymalloc.h
	gcc -c Test4_3.c
Test5.o: Test5.c mymalloc.h
	gcc -c Test5.c
clean:
	rm -f *.o mymalloc memgrind memtest Test1 Test2 Test3 Test4_1 Test4_2 Test4_3 Test5

Test Files

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mymalloc.h"
int main(){
    char *a = malloc(500);
    memset(a, 'A', 500);
    char *b = malloc(500);
    memset(b, 'B', 500);
    char *c = malloc(500);
    memset(c, 'C', 500);
    int overlap = 0;
    for(int i = 0; i < 500; i++){
        if(a[i] != 'A' || b[i] != 'B' || c[i] != 'C'){
            overlap = 1;
            break;
        }
    }
    if(overlap == 1){
        printf("Overlap Detected\n");
    }else {
        printf("No Overlap Detected\n");
    }
    free(a);
    free(b);
    free(c);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mymalloc.h"
int main(){
    char *p = malloc(4000);
    free(p);
    char *p2 = malloc(2000);
    free(p2);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mymalloc.h"
int main(){
    char *a1 = malloc(1000);
    char *a2 = malloc(1000);
    char *a3 = malloc(1000);
    char *a4 = malloc(1000);
    free(a1);
    free(a2);
    char *a5 = malloc(2000);
    free(a5);
    free(a3);
    free(a4);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mymalloc.h"
int main(){
    char *a = malloc(1000);
    int x;
    free(&x);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mymalloc.h"
int main(){
    int *a1 = malloc(sizeof(int) * 2);
    free(a1 + 1);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mymalloc.h"
int main(){
    char *a2 = malloc(1000);
    char *q = a2;
    free(a2);
    free(q);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mymalloc.h"
int main(){
    char *a1 = malloc(500);
    char *a2 = malloc(1500);
    free(a1);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include "mymalloc.h"
typedef struct Node { int value; struct Node *next; } Node;
typedef struct Tree { int value; struct Tree *right; struct Tree *left; } Tree;
void freeTree(Tree *root){
    if(!root){ return; }
    freeTree(root -> left);
    freeTree(root -> right);
    free(root);
}
int main(){
    struct timeval start, end;
    long seconds, useconds;
    gettimeofday(&start, NULL);
    for(int t = 0; t < 50; t++){
        for(int i = 0; i < 120; i++){
            char *a = malloc(1);
            if(a == NULL){ fprintf(stderr, "Memory allocation failed"); continue; }
            free(a);
        }
    }
    gettimeofday(&end, NULL);
    seconds = end.tv_sec  - start.tv_sec;
    useconds = end.tv_usec - start.tv_usec;
    double time = (seconds * 1000000.0 + useconds) / 1000000.0;
    double avg_time = time/50;
    printf("The average time for first workload is %1.8f seconds.\n", avg_time);
    gettimeofday(&start, NULL);
    for(int t = 0; t < 50; t++){
        char *p[120];
        for(int i = 0; i < 120; i++){
            p[i] = malloc(1);
            if(p[i] == NULL){ fprintf(stderr, "Memory allocation failed"); continue; }            
        }
        for(int i = 0; i < 120; i++){ free(p[i]); }
    }
    gettimeofday(&end, NULL);
    seconds = end.tv_sec  - start.tv_sec;
    useconds = end.tv_usec - start.tv_usec;
    double time2 = (seconds * 1000000.0 + useconds) / 1000000.0;
    double avg_time2 = time2 / 50;
    printf("The average time for second workload is %1.8f seconds.\n", avg_time2);
    gettimeofday(&start, NULL);
    for(int t = 0; t < 50; t++){
        char *q[120];
        int alreay_free[120] = {0};
        int up = 3, low = 0;
        for(int i = 0; i < 120; i++){
            q[i] = malloc(1);
            if(i == up){ 
                for(int j = low; j < i; j++){
                    int random = (rand() % (up - 0 + 1)) + 0;
                    if(alreay_free[random] == 0){ free(q[random]); alreay_free[random] = 1; }
                }
                int random2 = (rand() % (4 - 1 + 1)) + 1;
                low = up; 
                up += random2;
            }
        }
        for(int i = 0; i < 120; i++){
            if(alreay_free[i] == 0){ free(q[i]); }
        }
    }
    gettimeofday(&end, NULL);
    seconds = end.tv_sec  - start.tv_sec;
    useconds = end.tv_usec - start.tv_usec;
    double time3 = (seconds * 1000000.0 + useconds) / 1000000.0;
    double avg_time3 = time3 / 50;
    printf("The average time for third workload is %1.8f seconds.\n", avg_time3);
    gettimeofday(&start, NULL);
    for(int j = 0; j < 50; j++){
        Node *head = NULL;
        for (int i = 0; i < 100; i++) {
            Node* node = (Node*)malloc(sizeof(Node));
            node -> value = 10;
            node -> next = head;
            head = node;
        }
        while(head != NULL){
            Node *next = head -> next;
            free(head);
            head = next;
        }
    }
    gettimeofday(&end, NULL);
    seconds = end.tv_sec  - start.tv_sec;
    useconds = end.tv_usec - start.tv_usec;
    double time4 = (seconds * 1000000.0 + useconds) / 1000000.0;
    double avg_time4 = time4/50;
    printf("The average time for fourth workload is %1.8f seconds.\n", avg_time4);
    gettimeofday(&start, NULL);
    for(int j = 0; j < 50; j++){
        Tree* nodes[100];
        for(int i = 0; i < 100; i++){
            nodes[i] = malloc(sizeof(Tree));
            nodes[i]  -> value = i;
            nodes[i] -> left = NULL;
            nodes[i] -> right = NULL;
        }
        for(int i = 0; i < 100; i++){
            int left = (i * 2) + 1;
            int right = (i * 2) + 2;
            if(left < 100){ nodes[i]  -> left = nodes[left]; }
            if(right < 100){ nodes[i]  -> right = nodes[right]; }
        }
        freeTree(nodes[0]);
    }
    gettimeofday(&end, NULL);
    seconds = end.tv_sec  - start.tv_sec;
    useconds = end.tv_usec - start.tv_usec;
    double time5 = (seconds * 1000000.0 + useconds) / 1000000.0;
    double avg_time5 = time5/50;
    printf("The average time for fifth workload is %1.8f seconds.\n", avg_time5);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#ifndef REALMALLOC
#include "mymalloc.h"
#endif
#ifndef LEAK
#define LEAK 0
#endif
#define MEMSIZE 4096
#define HEADERSIZE 8
#define OBJECTS 64
#define OBJSIZE (MEMSIZE / OBJECTS - HEADERSIZE)
int main(int argc, char **argv)
{
	char *obj[OBJECTS];
	int i, j, errors = 0;
	for (i = 0; i < OBJECTS; i++) {
		obj[i] = malloc(OBJSIZE);
		if (obj[i] == NULL) {
		    printf("Unable to allocate object %d\n", i);
		    exit(1);
		}
	}
	for (i = 0; i < OBJECTS; i++) {
		memset(obj[i], i, OBJSIZE);
	}
	for (i = 0; i < OBJECTS; i++) {
		for (j = 0; j < OBJSIZE; j++) {
			if (obj[i][j] != i) {
				errors++;
				printf("Object %d byte %d incorrect: %d\n", i, j, obj[i][j]);
			}
		}
	}
	if (!LEAK) {
	    for (i = 0; i < OBJECTS; i++) {
		    free(obj[i]);
	    }
	}
	printf("%d incorrect bytes\n", errors);
	return EXIT_SUCCESS;
}

Efficient Memory Allocation in C

Project Overview

Real-World Application & Use Cases

Project Implementation in Brief

Comprehensive Testing & Stress Analysis

Correctness & Edge Cases:

Performance & Stress Testing:

Code Files

Core Files

Test Files

How to Compile & Run