From 967be9e750221ab2ab783f95df79bb26d290a45e Mon Sep 17 00:00:00 2001 From: Martial Simon Date: Mon, 15 Sep 2025 01:07:58 +0200 Subject: add: added projects --- malloc/alignment/alignment.c | 12 +++ malloc/alignment/alignment.h | 10 ++ malloc/beware_overflow/beware_overflow.c | 10 ++ malloc/beware_overflow/beware_overflow.h | 8 ++ malloc/beware_overflow/main.c | 21 ++++ malloc/block_allocator/allocator.c | 61 ++++++++++++ malloc/block_allocator/allocator.h | 25 +++++ malloc/block_allocator/main.c | 39 ++++++++ malloc/block_allocator/utils.c | 16 +++ malloc/block_allocator/utils.h | 16 +++ malloc/malloc/Makefile | 27 ++++++ malloc/malloc/src/helpers.c | 22 +++++ malloc/malloc/src/helpers.h | 14 +++ malloc/malloc/src/malloc.c | 23 +++++ malloc/malloc/src/utils.c | 158 ++++++++++++++++++++++++++++++ malloc/malloc/src/utils.h | 40 ++++++++ malloc/malloc/src/wrapper.c | 89 +++++++++++++++++ malloc/malloc/src/wrapper.h | 11 +++ malloc/malloc/tests/corruptionproof | Bin 0 -> 16632 bytes malloc/malloc/tests/memoryfootprint | Bin 0 -> 18064 bytes malloc/malloc/tests/speed | Bin 0 -> 17280 bytes malloc/malloc/tests/tests.sh | 3 + malloc/malloc/tests/unit.c | 161 +++++++++++++++++++++++++++++++ malloc/my_recycler/recycler.c | 62 ++++++++++++ malloc/my_recycler/recycler.h | 24 +++++ malloc/page_begin/main.c | 21 ++++ malloc/page_begin/page_begin.c | 10 ++ malloc/page_begin/page_begin.h | 8 ++ 28 files changed, 891 insertions(+) create mode 100644 malloc/alignment/alignment.c create mode 100644 malloc/alignment/alignment.h create mode 100644 malloc/beware_overflow/beware_overflow.c create mode 100644 malloc/beware_overflow/beware_overflow.h create mode 100644 malloc/beware_overflow/main.c create mode 100644 malloc/block_allocator/allocator.c create mode 100644 malloc/block_allocator/allocator.h create mode 100644 malloc/block_allocator/main.c create mode 100644 malloc/block_allocator/utils.c create mode 100644 malloc/block_allocator/utils.h create mode 100644 malloc/malloc/Makefile create mode 100644 malloc/malloc/src/helpers.c create mode 100644 malloc/malloc/src/helpers.h create mode 100644 malloc/malloc/src/malloc.c create mode 100644 malloc/malloc/src/utils.c create mode 100644 malloc/malloc/src/utils.h create mode 100644 malloc/malloc/src/wrapper.c create mode 100644 malloc/malloc/src/wrapper.h create mode 100755 malloc/malloc/tests/corruptionproof create mode 100755 malloc/malloc/tests/memoryfootprint create mode 100755 malloc/malloc/tests/speed create mode 100755 malloc/malloc/tests/tests.sh create mode 100644 malloc/malloc/tests/unit.c create mode 100644 malloc/my_recycler/recycler.c create mode 100644 malloc/my_recycler/recycler.h create mode 100644 malloc/page_begin/main.c create mode 100644 malloc/page_begin/page_begin.c create mode 100644 malloc/page_begin/page_begin.h (limited to 'malloc') diff --git a/malloc/alignment/alignment.c b/malloc/alignment/alignment.c new file mode 100644 index 0000000..99429c4 --- /dev/null +++ b/malloc/alignment/alignment.c @@ -0,0 +1,12 @@ +#include "alignment.h" + +size_t align(size_t size) +{ + size_t padding = size % sizeof(long double); + if (padding) + padding = sizeof(long double) - padding; + size_t res; + if (__builtin_uaddl_overflow(size, padding, &res)) + return 0; + return res; +} diff --git a/malloc/alignment/alignment.h b/malloc/alignment/alignment.h new file mode 100644 index 0000000..582ce8d --- /dev/null +++ b/malloc/alignment/alignment.h @@ -0,0 +1,10 @@ +#ifndef ALIGNMENT_H +#define ALIGNMENT_H + +#define _GNU_SOURCE + +#include + +size_t align(size_t size); + +#endif /* !ALIGNMENT_H */ diff --git a/malloc/beware_overflow/beware_overflow.c b/malloc/beware_overflow/beware_overflow.c new file mode 100644 index 0000000..4b2555c --- /dev/null +++ b/malloc/beware_overflow/beware_overflow.c @@ -0,0 +1,10 @@ +#include "beware_overflow.h" + +void *beware_overflow(void *ptr, size_t nmemb, size_t size) +{ + size_t res; + if (__builtin_umull_overflow(nmemb, size, &res)) + return NULL; + char *r = ptr; + return r + res; +} diff --git a/malloc/beware_overflow/beware_overflow.h b/malloc/beware_overflow/beware_overflow.h new file mode 100644 index 0000000..821e81e --- /dev/null +++ b/malloc/beware_overflow/beware_overflow.h @@ -0,0 +1,8 @@ +#ifndef BEWARE_OVERFLOW_H +#define BEWARE_OVERFLOW_H + +#include + +void *beware_overflow(void *ptr, size_t nmemb, size_t size); + +#endif /* BEWARE_OVERFLOW_H */ diff --git a/malloc/beware_overflow/main.c b/malloc/beware_overflow/main.c new file mode 100644 index 0000000..42fd689 --- /dev/null +++ b/malloc/beware_overflow/main.c @@ -0,0 +1,21 @@ +#include +#include + +#include "beware_overflow.h" + +void print_overflow(void *ptr, size_t nmemb, size_t size) +{ + void *begin = ptr; + void *res = beware_overflow(ptr, nmemb, size); + if (res) + printf("Pointer was incremented from %p to %p.\n", begin, res); + else + printf("Overflow detected between %ld and %ld.\n", nmemb, size); +} + +int main(void) +{ + print_overflow((void *)0x1000, 25, 6); + print_overflow((void *)0x40000, 12345678904, 12345678904); + return 0; +} diff --git a/malloc/block_allocator/allocator.c b/malloc/block_allocator/allocator.c new file mode 100644 index 0000000..0cf9af6 --- /dev/null +++ b/malloc/block_allocator/allocator.c @@ -0,0 +1,61 @@ +#include "allocator.h" + +#include +#include +#include + +size_t align(size_t size, size_t al) +{ + size_t padding = size % al; + if (padding) + padding = al - padding; + size_t res; + if (__builtin_uaddl_overflow(size, padding, &res)) + return 0; + return res; +} + +struct blk_allocator *blka_new(void) +{ + struct blk_allocator *new = malloc(sizeof(struct blk_allocator)); + new->meta = NULL; + return new; +} + +struct blk_meta *blka_alloc(struct blk_allocator *blka, size_t size) +{ + long page_size = sysconf(_SC_PAGESIZE); + size_t aligned_size = align(size + sizeof(struct blk_meta), page_size); + struct blk_meta *meta = mmap(NULL, aligned_size, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); + if (meta == MAP_FAILED) + return NULL; + meta->size = aligned_size - sizeof(struct blk_meta); + meta->next = blka->meta; + blka->meta = meta; + return meta; +} + +void blka_free(struct blk_meta *blk) +{ + munmap(blk, blk->size + sizeof(struct blk_meta)); +} + +void blka_pop(struct blk_allocator *blka) +{ + if (blka->meta == NULL) + return; + + struct blk_meta *meta = blka->meta; + blka->meta = blka->meta->next; + blka_free(meta); +} + +void blka_delete(struct blk_allocator *blka) +{ + while (blka->meta) + { + blka_pop(blka); + } + free(blka); +} diff --git a/malloc/block_allocator/allocator.h b/malloc/block_allocator/allocator.h new file mode 100644 index 0000000..98dd63e --- /dev/null +++ b/malloc/block_allocator/allocator.h @@ -0,0 +1,25 @@ +#ifndef ALLOCATOR_H +#define ALLOCATOR_H + +#include + +struct blk_meta +{ + struct blk_meta *next; + size_t size; + char data[]; +}; + +struct blk_allocator +{ + struct blk_meta *meta; +}; + +struct blk_allocator *blka_new(void); +void blka_delete(struct blk_allocator *blka); + +struct blk_meta *blka_alloc(struct blk_allocator *blka, size_t size); +void blka_free(struct blk_meta *blk); +void blka_pop(struct blk_allocator *blka); + +#endif /* !ALLOCATOR_H */ diff --git a/malloc/block_allocator/main.c b/malloc/block_allocator/main.c new file mode 100644 index 0000000..161185a --- /dev/null +++ b/malloc/block_allocator/main.c @@ -0,0 +1,39 @@ +#include + +#include "allocator.h" +#include "utils.h" + +int main(void) +{ + struct blk_allocator *ba = blka_new(); + + struct blk_meta *metas[6] = { NULL }; + char *messages[] = { "Hello world!\n", "You are doing ", "a great job ", + "if you see ", "this message ", "correctly.\n", + "But do not forget ", "to release ", "memory.\n" }; + + // Allocate metadatas + for (size_t i = 0; i < 3; ++i) + metas[i] = blka_alloc(ba, 2048); + for (size_t i = 3; i < 6; ++i) + metas[i] = blka_alloc(ba, 4096); + + // Write and read messages to metadatas + for (size_t i = 0; i < 6; ++i) + write_data(metas[i], messages[i], strlen(messages[i])); + for (size_t i = 0; i < 6; ++i) + read_data(metas[i]); + + // Overwrite metadatas, pop and read them + for (size_t i = 6; i < 9; ++i) + write_data(metas[i - 6], messages[i], strlen(messages[i])); + for (size_t i = 0; i < 3; ++i) + blka_pop(ba); + for (size_t i = 0; i < 3; ++i) + read_data(metas[i]); + + // Release memory + blka_delete(ba); + + return 0; +} diff --git a/malloc/block_allocator/utils.c b/malloc/block_allocator/utils.c new file mode 100644 index 0000000..d38dca0 --- /dev/null +++ b/malloc/block_allocator/utils.c @@ -0,0 +1,16 @@ +#include "utils.h" + +#include + +void read_data(struct blk_meta *meta) +{ + for (size_t i = 0; i < meta->size && meta->data[i] != '\0'; ++i) + putchar(meta->data[i]); +} + +void write_data(struct blk_meta *meta, char *data, size_t n) +{ + for (size_t i = 0; i < n; ++i) + meta->data[i] = data[i]; + meta->data[n] = '\0'; +} diff --git a/malloc/block_allocator/utils.h b/malloc/block_allocator/utils.h new file mode 100644 index 0000000..7573945 --- /dev/null +++ b/malloc/block_allocator/utils.h @@ -0,0 +1,16 @@ +#ifndef UTILS_H +#define UTILS_H + +#include "allocator.h" + +/* + * Print datas the `meta` block contains. + */ +void read_data(struct blk_meta *meta); + +/* + * Write `data` in the `meta` block. + */ +void write_data(struct blk_meta *meta, char *data, size_t n); + +#endif /* !UTILS_H */ diff --git a/malloc/malloc/Makefile b/malloc/malloc/Makefile new file mode 100644 index 0000000..0c73390 --- /dev/null +++ b/malloc/malloc/Makefile @@ -0,0 +1,27 @@ +CC = gcc +CPPFLAGS = -D_DEFAULT_SOURCE +CFLAGS = -Wall -Wextra -Werror -std=c99 -Wvla -Isrc +LDFLAGS = -shared +VPATH = src + +TARGET_LIB = libmalloc.so +OBJS = helpers.o utils.o wrapper.o malloc.o + +all: library + +library: $(TARGET_LIB) +$(TARGET_LIB): CFLAGS += -pedantic -fvisibility=hidden -fPIC +$(TARGET_LIB): LDFLAGS += -Wl,--no-undefined +$(TARGET_LIB): $(OBJS) + $(CC) $(LDFLAGS) -o $@ $^ + +debug: CFLAGS += -g +debug: clean $(TARGET_LIB) + +clean: + $(RM) $(TARGET_LIB) $(OBJS) + +check: + tests/tests.sh + +.PHONY: all $(TARGET_LIB) clean check diff --git a/malloc/malloc/src/helpers.c b/malloc/malloc/src/helpers.c new file mode 100644 index 0000000..93565e4 --- /dev/null +++ b/malloc/malloc/src/helpers.c @@ -0,0 +1,22 @@ +#include "helpers.h" + +void *get_data(struct header *h) +{ + void *tmp = h; + char *tmp1 = tmp; + return tmp1 + align(sizeof(struct header), sizeof(long double)); +} + +struct header *get_header(void *data) +{ + char *tmp = data; + void *tmp2 = tmp - align(sizeof(struct header), sizeof(long double)); + struct header *res = tmp2; + return res; +} + +void conditional_fuse(struct header *h, size_t size) +{ + if (split_chunk(h, size)) + fuse(h->next); +} diff --git a/malloc/malloc/src/helpers.h b/malloc/malloc/src/helpers.h new file mode 100644 index 0000000..8e6c010 --- /dev/null +++ b/malloc/malloc/src/helpers.h @@ -0,0 +1,14 @@ +#ifndef HELPERS_H +#define HELPERS_H + +#include + +#include "utils.h" + +void *get_data(struct header *h); + +struct header *get_header(void *data); + +void conditional_fuse(struct header *h, size_t size); + +#endif /* ! HELPERS_H */ diff --git a/malloc/malloc/src/malloc.c b/malloc/malloc/src/malloc.c new file mode 100644 index 0000000..d656569 --- /dev/null +++ b/malloc/malloc/src/malloc.c @@ -0,0 +1,23 @@ +#include + +#include "wrapper.h" + +__attribute__((visibility("default"))) void *malloc(size_t size) +{ + return my_malloc(size); +} + +__attribute__((visibility("default"))) void free(void *ptr) +{ + my_free(ptr); +} + +__attribute__((visibility("default"))) void *realloc(void *ptr, size_t size) +{ + return my_realloc(ptr, size); +} + +__attribute__((visibility("default"))) void *calloc(size_t nmemb, size_t size) +{ + return my_calloc(nmemb, size); +} diff --git a/malloc/malloc/src/utils.c b/malloc/malloc/src/utils.c new file mode 100644 index 0000000..f87285d --- /dev/null +++ b/malloc/malloc/src/utils.c @@ -0,0 +1,158 @@ +#include "utils.h" + +#include +#include + +struct page *first_page = NULL; + +size_t align(size_t size, size_t al) +{ + size_t padding = size % al; + if (padding) + padding = al - padding; + size_t res; + if (__builtin_uaddl_overflow(size, padding, &res)) + return 0; + return res; +} + +size_t next_pow(size_t n) +{ + n--; + n |= n >> 1; + n |= n >> 2; + n |= n >> 4; + n |= n >> 8; + n |= n >> 16; + n |= n >> 32; + n++; + n += (n == 0); + return n; +} + +int add_page(size_t size) +{ + size_t k = align(size + sizeof(struct header) + sizeof(struct page), + sysconf(_SC_PAGESIZE)); + struct page *new_page = mmap(NULL, k, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); + if (new_page == MAP_FAILED) + { + new_page = NULL; + return 0; + } + + new_page->next = first_page; + new_page->prev = NULL; + if (first_page) + first_page->prev = new_page; + new_page->size = k; + + void *tmp = new_page; + char *tmp2 = tmp; + void *tmp3 = tmp2 + align(sizeof(struct page), sizeof(long double)); + new_page->blocks = tmp3; + new_page->blocks->free = 1; + new_page->blocks->prev = NULL; + new_page->blocks->next = NULL; + new_page->blocks->size = + new_page->size - sizeof(struct page) - sizeof(struct header); + first_page = new_page; + return 1; +} + +int remove_page(struct page *p) +{ + if (p == NULL) + return 0; + + if (p->prev == NULL) + first_page = p->next; + else + p->prev->next = p->next; + + if (p->next != NULL) + p->next->prev = p->prev; + + return !munmap(p, p->size); +} + +struct page *get_pages(void) +{ + return first_page; +} + +struct header *find_free_header(struct page *p, size_t size) +{ + if (p->size - sizeof(struct header) - sizeof(struct page) < size) + return NULL; + struct header *h; + for (h = p->blocks; h && (!h->free || h->size < size); h = h->next) + { + continue; + } + if (!h) + return NULL; + return h; +} + +struct header *find_free(size_t size) +{ + struct page *p; + struct header *res; + for (p = first_page; p && !(res = find_free_header(p, size)); p = p->next) + { + continue; + } + if (!p) + return NULL; + return res; +} + +int split_chunk(struct header *h, size_t size) +{ + size_t aligned = align(size, sizeof(long double)); + if (h->size < aligned + sizeof(struct header) + sizeof(long double)) + { + return 0; + } + // un-free the chunk + h->free = 0; + // init next chunk + void *tmp = h; + char *tmp2 = tmp; + void *tmp3 = tmp2 + sizeof(struct header) + aligned; + struct header *new = tmp3; + new->next = h->next; + h->next = new; + new->prev = h; + new->free = 1; + new->size = + h->size - aligned - align(sizeof(struct header), sizeof(long double)); + h->size = aligned; + return 1; +} + +void fuse(struct header *h) +{ + if (h->next && h->next->free) + { + h->size += + h->next->size + align(sizeof(struct header), sizeof(long double)); + h->next = h->next->next; + } + if (h->prev && h->prev->free) + { + h->prev->size += + h->size + align(sizeof(struct header), sizeof(long double)); + h->prev->next = h->next; + } + if (!h->next && !h->prev) + { + void *tmp = h; + char *tmp2 = tmp; + void *tmp3 = tmp2 - align(sizeof(struct header), sizeof(long double)); + struct page *p = tmp3; + remove_page(p); + } +} diff --git a/malloc/malloc/src/utils.h b/malloc/malloc/src/utils.h new file mode 100644 index 0000000..c2badf3 --- /dev/null +++ b/malloc/malloc/src/utils.h @@ -0,0 +1,40 @@ +#ifndef UTILS_H +#define UTILS_H + +#include + +struct header +{ + struct header *next; + struct header *prev; + size_t size; + int free; // 1 if free, 0 otherwise +}; + +struct page +{ + struct page *next; + struct page *prev; + size_t size; // page size + struct header *blocks; +}; + +extern struct page *first_page; + +int add_page(size_t size); + +int remove_page(struct page *p); + +size_t align(size_t size, size_t alignment); + +size_t next_pow(size_t n); + +struct page *get_pages(void); + +struct header *find_free(size_t size); + +int split_chunk(struct header *h, size_t size); + +void fuse(struct header *h); + +#endif /* ! UTILS_H */ diff --git a/malloc/malloc/src/wrapper.c b/malloc/malloc/src/wrapper.c new file mode 100644 index 0000000..00d1072 --- /dev/null +++ b/malloc/malloc/src/wrapper.c @@ -0,0 +1,89 @@ +#include "wrapper.h" + +#include + +#include "helpers.h" + +void *my_malloc(size_t size) +{ + if (size == 0) + size++; + if (get_pages() == NULL && !add_page(size)) + return NULL; + struct header *h = find_free(size); + if (!h && !add_page(size)) + return NULL; + if (!h) + { + h = find_free(size); + } + split_chunk(h, size); + + void *t = h; + char *res = t; + return res + align(sizeof(struct header), sizeof(long double)); +} + +void my_free(void *ptr) +{ + if (ptr == NULL) + return; + char *tmp = ptr; + void *tmp2 = tmp - align(sizeof(struct header), sizeof(long double)); + struct header *h = tmp2; + h->free = 1; + fuse(h); +} + +void *my_calloc(size_t nmemb, size_t size) +{ + size_t res; + if (__builtin_umull_overflow(size, nmemb, &res)) + return NULL; + void *p = my_malloc(res); + if (p == NULL) + return NULL; + memset(p, 0, res); + return p; +} + +void *my_realloc(void *ptr, size_t size) +{ + if (ptr == NULL) + return my_malloc(size); + if (size == 0) + { + my_free(ptr); + return NULL; + } + struct header *h = get_header(ptr); + size_t s = h->size; + if (h->size > size) + { + conditional_fuse(h, size); + return ptr; + } + + h->free = 1; + fuse(h); + if (h->prev && h->prev->free) + h = h->prev; + if (h->size > size) + { + conditional_fuse(h, size); + void *data = get_data(h); + memmove(data, ptr, s); + + return data; + } + h = find_free(size); + if (!h && !add_page(size)) + return NULL; + if (!h) + { + h = find_free(size); + } + void *data = get_data(h); + memmove(data, ptr, s); + return data; +} diff --git a/malloc/malloc/src/wrapper.h b/malloc/malloc/src/wrapper.h new file mode 100644 index 0000000..76f7fb1 --- /dev/null +++ b/malloc/malloc/src/wrapper.h @@ -0,0 +1,11 @@ +#ifndef WRAPPER_H +#define WRAPPER_H + +#include "utils.h" + +void *my_malloc(size_t size); +void my_free(void *ptr); +void *my_calloc(size_t nmemb, size_t size); +void *my_realloc(void *ptr, size_t size); + +#endif /* ! WRAPPER_H */ diff --git a/malloc/malloc/tests/corruptionproof b/malloc/malloc/tests/corruptionproof new file mode 100755 index 0000000..26ebc81 Binary files /dev/null and b/malloc/malloc/tests/corruptionproof differ diff --git a/malloc/malloc/tests/memoryfootprint b/malloc/malloc/tests/memoryfootprint new file mode 100755 index 0000000..1718375 Binary files /dev/null and b/malloc/malloc/tests/memoryfootprint differ diff --git a/malloc/malloc/tests/speed b/malloc/malloc/tests/speed new file mode 100755 index 0000000..a1026c8 Binary files /dev/null and b/malloc/malloc/tests/speed differ diff --git a/malloc/malloc/tests/tests.sh b/malloc/malloc/tests/tests.sh new file mode 100755 index 0000000..7993b2e --- /dev/null +++ b/malloc/malloc/tests/tests.sh @@ -0,0 +1,3 @@ +#!/bin/sh + +echo aaaaa diff --git a/malloc/malloc/tests/unit.c b/malloc/malloc/tests/unit.c new file mode 100644 index 0000000..e30c2da --- /dev/null +++ b/malloc/malloc/tests/unit.c @@ -0,0 +1,161 @@ +#include +#include +#include + +#include "utils.h" +#include "wrapper.h" + +void print_header(struct header *h) +{ + if (!h) + return; + printf("------------- Header %p -----------\n", (void *)h); + printf("Free: %s\n", h->free ? "Yes" : "No"); + printf("Previous header: %p\n", (void *)h->prev); + printf("Next header: %p\n", (void *)h->next); + printf("Data size: %zu\n", h->size); + printf("??????????? Data ????????????\n"); + if (h->free) + { + printf("Unknown data\n"); + } + else + { + void *d = h; + char *data = d; + data += align(sizeof(struct header), sizeof(long double)); + printf("%s\n", data); + } +} + +void print_headers(struct header *h) +{ + if (!h) + return; + struct header *first = h; + while (first) + { + print_header(first); + first = first->next; + } +} + +void print_page(struct page *p) +{ + if (!p) + return; + printf("############## Page %p ##############\n", (void *)p); + printf("Previous page: %p\n", (void *)p->prev); + printf("Next page: %p\n", (void *)p->next); + printf("Page size: %zu\n", p->size); + print_headers(p->blocks); +} + +void print_pages(struct page *p) +{ + if (!p) + { + printf("No pages mapped\n"); + return; + } + printf("***************************************************************\n"); + struct page *first = p; + while (first) + { + print_page(first); + first = first->next; + } +} + +TestSuite(utils); + +Test(utils, next_pow1) +{ + size_t input = 1; + size_t expected = 1; + size_t actual = next_pow(input); + cr_expect(expected == actual, "Expected %zu, got %zu", expected, actual); +} + +Test(utils, next_pow3) +{ + size_t input = 3; + size_t expected = 4; + size_t actual = next_pow(input); + cr_expect(expected == actual, "Expected %zu, got %zu", expected, actual); +} + +Test(utils, next_pow720) +{ + size_t input = 720; + size_t expected = 1024; + size_t actual = next_pow(input); + cr_expect(expected == actual, "Expected %zu, got %zu", expected, actual); +} + +TestSuite(paging); + +Test(paging, pegging_one) +{ + int ret = add_page(5); + struct page *p = get_pages(); + cr_expect(ret, "add_page failed"); + ret = add_page(10000); + // cr_expect(ret, "add_page failed"); + ret = add_page(5000); + ret = add_page(42); + cr_expect(ret, "add_page failed"); + print_pages(get_pages()); + ret = remove_page(p); + cr_expect(ret, "remove_page failed"); + print_pages(get_pages()); + struct header *h = find_free(5000); + print_header(h); + h = find_free(100000); + cr_expect(h == NULL, "NULL expected, segfault incoming"); + h = find_free(42); + print_header(h); + print_pages(get_pages()); + printf(" / \\\n"); + printf(" / | \\\n"); + printf(" /__.__\\ SPLITTING\n"); + split_chunk(h, 25); + print_pages(get_pages()); + h->free = 1; + fuse(h); + print_pages(get_pages()); + while ((p = get_pages())) + remove_page(p); +} + +TestSuite(alloc); + +Test(alloc, malloc_simple) +{ + printf("//////////////////// Tests alloc ///////////////////\n"); + char *s = my_malloc(4); + s[0] = 'a'; + s[1] = 'c'; + s[2] = 'u'; + s[3] = '\0'; + printf("%s\n", s); + printf("Freeing...\n"); + print_pages(get_pages()); + printf("//////////////////// Fin tests alloc ///////////////////\n"); +} + +Test(alloc, malloc_stresstest) +{ + printf("\nSTRESSTEST \n"); + void *t = my_malloc(10000000); + cr_assert(t, "malloc returned NULL"); + my_free(t); + t = my_malloc(10000000); + void *r = my_malloc(4000000); + print_pages(get_pages()); + my_free(t); + print_pages(get_pages()); + my_free(r); + print_pages(get_pages()); + printf("\nEND STRESSTEST \n"); +} diff --git a/malloc/my_recycler/recycler.c b/malloc/my_recycler/recycler.c new file mode 100644 index 0000000..f2e7da5 --- /dev/null +++ b/malloc/my_recycler/recycler.c @@ -0,0 +1,62 @@ +#include "recycler.h" + +#include + +struct recycler *recycler_create(size_t block_size, size_t total_size) +{ + if (block_size % sizeof(size_t) || !block_size || !total_size + || total_size % block_size) + return NULL; + struct recycler *rec = malloc(sizeof(struct recycler)); + if (rec == NULL) + return NULL; + rec->block_size = block_size; + rec->capacity = total_size / block_size; + rec->chunk = malloc(total_size * sizeof(void *)); + if (rec->chunk == NULL) + { + free(rec); + return NULL; + } + rec->free = rec->chunk; + struct free_list *f = rec->free; + for (size_t i = 0; i < rec->capacity - 1; i++) + { + f->next = f + block_size; + f = f->next; + } + + f->next = NULL; + + return rec; +} + +void recycler_destroy(struct recycler *r) +{ + if (r == NULL) + return; + free(r->chunk); + free(r); +} + +void *recycler_allocate(struct recycler *r) +{ + if (r == NULL || r->free == NULL) + return NULL; + + void *res = r->free; + struct free_list *f = r->free; + r->free = f->next; + return res; +} + +void recycler_free(struct recycler *r, void *block) +{ + if (r == NULL || block == NULL) + return; + + struct free_list *old_head = r->free; + r->free = block; + struct free_list *b = block; + b->next = old_head; +} diff --git a/malloc/my_recycler/recycler.h b/malloc/my_recycler/recycler.h new file mode 100644 index 0000000..bff70ef --- /dev/null +++ b/malloc/my_recycler/recycler.h @@ -0,0 +1,24 @@ +#ifndef RECYCLER_H +#define RECYCLER_H + +#include + +struct recycler +{ + size_t block_size; + size_t capacity; // number of blocks in the chunk + void *chunk; // memory chunk containing all blocks + void *free; // address of the first free block of the free list +}; + +struct free_list +{ + struct free_list *next; // next free block +}; + +struct recycler *recycler_create(size_t block_size, size_t total_size); +void recycler_destroy(struct recycler *r); +void *recycler_allocate(struct recycler *r); +void recycler_free(struct recycler *r, void *block); + +#endif /* !RECYCLER_H */ diff --git a/malloc/page_begin/main.c b/malloc/page_begin/main.c new file mode 100644 index 0000000..8fc931e --- /dev/null +++ b/malloc/page_begin/main.c @@ -0,0 +1,21 @@ +#include + +#include "page_begin.h" + +static void display_result(void *ptr, size_t page_size, void *expected_result) +{ + void *res = page_begin(ptr, page_size); + + printf("ptr: %p\n", ptr); + printf("page_size: %lu\n", page_size); + printf("expected_result: %p\n", expected_result); + printf("result: %p\n", res); + + printf(expected_result == res ? "OK\n" : "KO\n"); +} + +int main(void) +{ + display_result((void *)0x1234ffea, 4096, (void *)0x1234f000); + display_result((void *)0x1234ffea, 256, (void *)0x1234ff00); +} diff --git a/malloc/page_begin/page_begin.c b/malloc/page_begin/page_begin.c new file mode 100644 index 0000000..ebb1842 --- /dev/null +++ b/malloc/page_begin/page_begin.c @@ -0,0 +1,10 @@ +#include "page_begin.h" + +void *page_begin(void *ptr, size_t page_size) +{ + char *a = ptr; + char *p = NULL; + size_t test = a - p; + void *res = (void *)(test & ~(page_size - 1)); + return res; +} diff --git a/malloc/page_begin/page_begin.h b/malloc/page_begin/page_begin.h new file mode 100644 index 0000000..ba467d5 --- /dev/null +++ b/malloc/page_begin/page_begin.h @@ -0,0 +1,8 @@ +#ifndef PAGE_BEGIN_H +#define PAGE_BEGIN_H + +#include + +void *page_begin(void *ptr, size_t page_size); + +#endif /* !PAGE_BEGIN_H */ -- cgit v1.2.3