marCsweep/include/gc_malloc.h

#ifndef GC_MALLOC_H
#define GC_MALLOC_H

#include <stdint.h>
#include <stdio.h>
#include <unistd.h>

// Generally, inline functions are preferable to macros resembling functions.
// https://www.kernel.org/doc/html/v4.10/process/coding-style.html#data-structures

#define ALIGN 8 /* Number of bytes to which chunk size is aligned */
#define OVERHEAD 1 /* Number of 8-byte segments for chunk size & flags */
#define MAGIC 2 /* Number of 8-byte segments from top of chunk to fields */
#define MIN 3 /* Minimum number of 8-byte segments for data in a chunk */

/*
 * Metadata and user data for allocated memory
 *
 * footer: size of previous block or user data of previous block if allocated
 * size: size of chunk in bytes
 * merge: flag to identify when the chunk can be coalesced,
 *        possible values 0 (false, don't merge) or non-zero (true, do merge)
 * free: flag to identify when the chunk is free,
 *       possible values 0 (false, allocated) or non-zero (true, chunk is free)
 * next: pointer to next chunk in the free list
 * prev: pointer to previous chunk in the free list
 */
struct gc_chunk {
	uint64_t footer;
	uint32_t size;
	uint16_t merge; /* 1 = do merge, initialize to 0 */
	uint16_t free; /* 0 = allocated, initialize to 1 */
	struct gc_chunk *next;
	struct gc_chunk *prev;
};

// Gets a pointer to the next chunk
struct gc_chunk *find_next_chunk(struct gc_chunk *curr);

// Gets a pointer to the previous chunk, ensuring that current can be coalesced
struct gc_chunk *find_prev_chunk(struct gc_chunk *curr);

// Updates chunk footer information (remember that the current chunk's footer
// data is actually part of the next chunk)
void set_footer(struct gc_chunk *curr);

// Gets footer information for the current chunk - useful for debugging
uint64_t get_footer(struct gc_chunk *curr);

// Creates a new chunk with sentinel
struct gc_chunk *init_gc_chunk(void);

// Gets a pointer to a suitable chunk (first fit) from the free list, otherwise
// creates a new chunk and returns it's pointer
struct gc_chunk *find_free_chunk(size_t size);

// Coalesces chunks when merge flag is set
void merge_chunk(struct gc_chunk *curr);

// Performs allocations of SIZE bytes
void *gc_malloc(size_t size);

// Frees allocations for re-use
void gc_free(void *ptr);

// Completely de-allocates the heap (break glass in case of emergency)
void destroy_heap(struct gc_chunk *freelist);

#endif /* GC_MALLOC_H */