commit d2ed6f4dbec88868b42ec90ae6707e25a7dba95b
parent 82b49fd168f0c3c91518f68a37c9e3fd8216f049
Author: Chris Bracken <chris@bracken.jp>
Date: Sat, 22 Oct 2022 00:16:04 -0700
Extract malloc/free to memory.h
This also renames the .cc files to .c files since these no longer
include C++ code.
Diffstat:
5 files changed, 185 insertions(+), 175 deletions(-)
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
@@ -1,4 +1,4 @@
-add_definitions(-std=c++17)
+add_definitions(-std=c17)
set(CXX_FLAGS
"-Wall"
@@ -13,6 +13,7 @@ set(CXX_TEST_FLAGS
)
add_executable(main
- main.cc
+ main.c
+ memory.c
)
target_compile_options(main PRIVATE ${CXX_FLAGS})
diff --git a/src/main.c b/src/main.c
@@ -0,0 +1,21 @@
+#include <stdio.h>
+
+#include "memory.h"
+
+int main(int argc, char** argv) {
+ print_brk();
+ print_alloc_list();
+ printf("\n");
+
+ void *p = malloc(20);
+ printf("*** malloced a block\n");
+ print_block(p);
+ print_brk();
+ print_alloc_list();
+ printf("\n");
+
+ free(p);
+ printf("*** freed a block\n");
+ print_brk();
+ print_alloc_list();
+}
diff --git a/src/main.cc b/src/main.cc
@@ -1,173 +0,0 @@
-#include <pthread.h>
-#include <stdio.h>
-#include <unistd.h>
-
-struct header_t {
- size_t size;
- struct header_t *next;
- unsigned char is_free;
-};
-
-struct header_t *get_free_block(size_t size);
-void *malloc(size_t size);
-void print_brk();
-void print_header(struct header_t *header);
-void print_block(void *p);
-void print_alloc_list();
-
-static struct header_t *head, *tail;
-static pthread_mutex_t global_malloc_lock;
-
-////////////////////////////////////////////////////////////////////////
-// Implementation.
-
-/**
- * Return the first free block of at least the specified size, or nullptr if no
- * such block exists.
- */
-struct header_t *get_free_block(size_t size) {
- struct header_t *curr = head;
- while (curr) {
- if (curr->is_free && curr->size >= size)
- return curr;
- curr = curr->next;
- }
- return nullptr;
-}
-
-/**
- * Allocate a block of memory of a specific size on the heap.
- */
-void *malloc(size_t size) {
- size_t total_size;
- void *block;
- struct header_t *header;
-
- if (!size)
- return nullptr;
-
- // Check for free previously-allocated block of the right size.
- pthread_mutex_lock(&global_malloc_lock);
- header = get_free_block(size);
- if (header) {
- header->is_free = 0;
- pthread_mutex_unlock(&global_malloc_lock);
- return (void*)(header + 1);
- }
-
- // If none, allocate a new block.
- total_size = sizeof(struct header_t) + size;
- block = sbrk((int)total_size);
- if (block == (void*)(-1)) {
- pthread_mutex_unlock(&global_malloc_lock);
- return nullptr;
- }
-
- header = (struct header_t*)block;
- header->size = size;
- header->is_free = 0;
- header->next = nullptr;
- if (!head)
- head = header;
- if (tail)
- tail->next = header;
- tail = header;
- pthread_mutex_unlock(&global_malloc_lock);
- return (void*)(header + 1);
-}
-
-/**
- * Frees the specified block.
- */
-void free(void *block) {
- if (!block)
- return;
-
- pthread_mutex_lock(&global_malloc_lock);
-
- // Get block header.
- struct header_t *header = (struct header_t*)block - 1;
-
- void *program_break = sbrk(0);
- if ((char*)block + header->size == program_break) {
- // If we're the last allocated block before brk, decrement it.
- if (head == tail) {
- head = tail = nullptr;
- } else {
- for (struct header_t *p = head; p != nullptr; p = p->next) {
- if (p->next == tail) {
- p->next = nullptr;
- tail = p;
- }
- }
- }
- size_t total_size = sizeof(struct header_t) + header->size;
- sbrk(-(int)total_size);
- pthread_mutex_unlock(&global_malloc_lock);
- return;
- } else {
- // Otherwise, mark the block as free.
- header->is_free = 1;
- }
-
- pthread_mutex_unlock(&global_malloc_lock);
-}
-
-/**
- * Compute and report brk.
- */
-void print_brk() {
- void *p = sbrk(0);
- if (p == (void*)(-1))
- fprintf(stderr, "sbrk() failed\n");
- printf("brk: %p\n", p);
-}
-
-void print_header(struct header_t *header) {
- printf("hdr: %p\n", header);
- if (!header) {
- return;
- }
- printf("size: %#zx\n", header->size);
- printf("free: %s\n", header->is_free ? "true" : "false");
-}
-
-/**
- * Print the header for a block.
- */
-void print_block(void *block) {
- printf("addr: %p\n", block);
- if (!block)
- return;
- struct header_t *h = (struct header_t*)(block) - 1;
- print_header(h);
-}
-
-/**
- * Print the alloc list.
- */
-void print_alloc_list() {
- printf("== head\n");
- print_header(head);
- printf("== tail\n");
- print_header(tail);
-}
-
-int main(int argc, char** argv) {
- print_brk();
- printf("Header size is: %#zx\n", sizeof(struct header_t));
- print_alloc_list();
- printf("\n");
-
- void *p = malloc(20);
- printf("*** malloced a block\n");
- print_block(p);
- print_brk();
- print_alloc_list();
- printf("\n");
-
- free(p);
- printf("*** freed a block\n");
- print_brk();
- print_alloc_list();
-}
diff --git a/src/memory.c b/src/memory.c
@@ -0,0 +1,140 @@
+#include "memory.h"
+
+#include <pthread.h>
+#include <stdio.h>
+#include <unistd.h>
+
+// An allocation header block.
+//
+// Allocation header blocks sit immediately before the allocated pointer in
+// memory and form a linked list staring at |head| and ending at |tail|.
+struct header_t {
+ size_t size;
+ struct header_t *next;
+ unsigned char is_free;
+};
+
+static struct header_t *head, *tail;
+static pthread_mutex_t global_malloc_lock;
+
+// Returns the first free block of at least the specified size, or null if
+// no such block exists.
+static struct header_t *get_free_block(size_t size);
+
+// Print header struct debug dump.
+void print_header(struct header_t *header);
+
+static struct header_t *get_free_block(size_t size) {
+ struct header_t *curr = head;
+ while (curr) {
+ if (curr->is_free && curr->size >= size)
+ return curr;
+ curr = curr->next;
+ }
+ return NULL;
+}
+
+void *malloc(size_t size) {
+ size_t total_size;
+ void *block;
+ struct header_t *header;
+
+ if (!size)
+ return NULL;
+
+ // Check for free previously-allocated block of the right size.
+ pthread_mutex_lock(&global_malloc_lock);
+ header = get_free_block(size);
+ if (header) {
+ header->is_free = 0;
+ pthread_mutex_unlock(&global_malloc_lock);
+ return (void*)(header + 1);
+ }
+
+ // If none, allocate a new block.
+ total_size = sizeof(struct header_t) + size;
+ block = sbrk((int)total_size);
+ if (block == (void*)-1) {
+ pthread_mutex_unlock(&global_malloc_lock);
+ return NULL;
+ }
+
+ header = (struct header_t*)block;
+ header->size = size;
+ header->is_free = 0;
+ header->next = NULL;
+ if (!head)
+ head = header;
+ if (tail)
+ tail->next = header;
+ tail = header;
+ pthread_mutex_unlock(&global_malloc_lock);
+ return (void*)(header + 1);
+}
+
+void free(void *block) {
+ if (!block)
+ return;
+
+ pthread_mutex_lock(&global_malloc_lock);
+
+ // Get block header.
+ struct header_t *header = (struct header_t*)block - 1;
+
+ void *program_break = sbrk(0);
+ if ((char*)block + header->size == program_break) {
+ // If we're the last allocated block before brk, decrement it.
+ if (head == tail) {
+ head = tail = NULL;
+ } else {
+ for (struct header_t *p = head; p != NULL; p = p->next) {
+ if (p->next == tail) {
+ p->next = NULL;
+ tail = p;
+ }
+ }
+ }
+ size_t total_size = sizeof(struct header_t) + header->size;
+ sbrk(-(int)total_size);
+ pthread_mutex_unlock(&global_malloc_lock);
+ return;
+ } else {
+ // Otherwise, mark the block as free.
+ header->is_free = 1;
+ }
+
+ pthread_mutex_unlock(&global_malloc_lock);
+}
+
+void print_brk() {
+ void *p = sbrk(0);
+ if (p == (void*)(-1))
+ fprintf(stderr, "sbrk() failed\n");
+ printf("brk: %p\n", p);
+}
+
+void print_header(struct header_t *header) {
+ printf("hdr: %p\n", header);
+ printf("sizeof(hdr): %#zx\n", sizeof(struct header_t));
+ if (!header) {
+ return;
+ }
+ printf("size: %#zx\n", header->size);
+ printf("free: %s\n", header->is_free ? "true" : "false");
+}
+
+void print_block(void *block) {
+ printf("addr: %p\n", block);
+ if (!block)
+ return;
+ struct header_t *h = (struct header_t*)(block) - 1;
+ print_header(h);
+}
+
+void print_alloc_list() {
+ printf("== head\n");
+ print_header(head);
+ printf("== tail\n");
+ print_header(tail);
+}
+
diff --git a/src/memory.h b/src/memory.h
@@ -0,0 +1,21 @@
+#ifndef MEMORY_H_
+#define MEMORY_H_
+
+#include <unistd.h>
+
+// Allocate a block of memory of a specific size on the heap.
+void *malloc(size_t size);
+
+// Frees the specified block.
+void free(void *block);
+
+// Compute and write the program break to stdout.
+void print_brk();
+
+// Write debug info for a block to stdout.
+void print_block(void *p);
+
+// Write debug info for the allocations list to stdout.
+void print_alloc_list();
+
+#endif // MEMORY_H_
