Thoughts on memory usage reduction

[DrXiao]

When submitting the pull request (#203 ), I used my beaglebone black (running Debian OS) to build shecc targeting armv7.

However, I found that the current memory usage is too high to build the stage 2 compiler on my beaglebone black.

debian@BeagleBone:~/shecc$ make
env printf "ARCH=arm" > .session.mk
Target machine code switch to arm
Warning: missing packages: dot jq
Warning: Please check package installation
  CC+LD out/inliner
  GEN   out/libc.inc
  CC    out/src/main.o
  LD    out/shecc
  SHECC out/shecc-stage1.elf
  SHECC out/shecc-stage2.elf
[ 1830.930466] Out of memory: Killed process 1995 (shecc-stage1.el) total-vm:1875560kB, anon-rss:429492kB, file-rss:148kB, shmem-rss:0kB, UID:1000 pgtables:1832kB oom_score_adj:0
make: *** [Makefile:115: out/shecc-stage2.elf] Killed

It would be better to reduce the memory usage so that the build process can complete even on low-memory ARM machines.

[jserv]

The original Implementation is very simplistic, primarily using mmap for every allocation.

• Maintains a global __alloc_head and __alloc_tail list of all allocated chunks (used for __free_all).
• Maintains a separate __freelist_head for freed chunks, using a best-fit search.
  free marks chunks as freed but does not return memory to the OS (except via __free_all).
• No coalescing of adjacent free blocks.

Let's consider a hybrid approach:

• Small/medium allocations (below MMAP_THRESHOLD) are handled by an internal heap manager.
• Large allocations (at or above MMAP_THRESHOLD) are directly mmaped and munmaped.
• Internal Heap: Manages contiguous memory blocks obtained from mmaping pages, effectively acting as a sub-allocator.
• First-Fit Allocation: Iterates the free list to find the first suitable block.
• Block Splitting: If a free block is larger than needed, it's split, returning the remainder to the free list.
• Coalescing: Adjacent free blocks are merged during free to reduce external fragmentation.
• Refined Metadata: next_free and prev_free pointers for free list management are stored within the user data area of free chunks, reducing the fixed overhead for allocated chunks.

Proof-of-concept (PoC) implementation is shown below. It does not munmap memory from the internal heap unless it was a large direct 'mmap' allocation. Smaller heap blocks are reused within the process until process termination, at which point the operating system reclaims all remaining process memory.

/* Linux mmap flags/prot definitions. */
#define PROT_READ 0x1
#define PROT_WRITE 0x2
#define MAP_PRIVATE 0x2
#define MAP_ANONYMOUS 0x20

#ifndef PAGESIZE
#define PAGESIZE 4096
#endif

/* Minimum alignment for all memory allocations.
 * 8 bytes ensures alignment for pointers and 64-bit types (if used, e.g., long
 * long) on 32-bit systems. Must be a power of 2.
 */
#define MIN_ALIGNMENT 8

/* Helper to align a value up to the nearest multiple of 'align'. */
#define ALIGN_UP(val, align) (((val) + (align) - 1) & ~((align) - 1))

/* Flag stored in the lowest bit of 'size_and_flags' within the chunk header. */
#define CHUNK_FREED_MASK 1 /* LSB: 1 if chunk is free, 0 if allocated */

/* Acts as the metadata at the start of each memory block. */
typedef struct chunk {
    /* 'size_and_flags' stores the total size of this chunk (including its
     * header, data, and potential footer) AND the CHUNK_FREED_MASK flag.
     */
    size_t size_and_flags;
} chunk_t;

/* This structure defines the nodes used for the doubly linked free list.
 * It is overlaid on the user data area of a 'chunk_t' when that chunk is free.
 */
typedef struct free_list_node {
    struct free_list_node *next_free;
    struct free_list_node *prev_free;
} free_list_node_t;

/* Calculate the actual size of the chunk header (aligned).
 * This is the minimum overhead added to user's requested size.
 */
#define CHUNK_HEADER_SIZE ALIGN_UP(sizeof(chunk_t), MIN_ALIGNMENT)

/* Minimum size a chunk can be to be placed on the free list.
 * It must accommodate:
 * 1. Its own 'chunk_t' header ('size_and_flags').
 * 2. The 'free_list_node_t' (for 'next_free' and 'prev_free' pointers) when
 *    free.
 * 3. A footer ('size_t') which is a copy of the header's size.
 */
#define MIN_CHUNK_SIZE                                                      \
    ALIGN_UP(CHUNK_HEADER_SIZE + sizeof(free_list_node_t) + sizeof(size_t), \
             MIN_ALIGNMENT)

/* Get the raw size of the chunk (masking out the CHUNK_FREED_MASK flag). */
#define GET_CHUNK_RAW_SIZE(chunk_ptr) \
    ((chunk_ptr)->size_and_flags & ~CHUNK_FREED_MASK)

/* Convert a 'chunk_t' pointer (to the header) to the user's data pointer. */
#define CHUNK_TO_USER_DATA(chunk_ptr) \
    ((void *) ((char *) (chunk_ptr) + CHUNK_HEADER_SIZE))

/* Convert a user data pointer back to its 'chunk_t' header pointer. */
#define USER_DATA_TO_CHUNK(ptr) \
    ((chunk_t *) ((char *) (ptr) - CHUNK_HEADER_SIZE))

/* Get a pointer to the next physically adjacent chunk in memory. */
#define NEXT_MEM_CHUNK(chunk_ptr) \
    ((chunk_t *) ((char *) (chunk_ptr) + GET_CHUNK_RAW_SIZE(chunk_ptr)))

/* Check if a chunk is marked as free. */
#define IS_CHUNK_FREED(chunk_ptr) \
    (((chunk_ptr)->size_and_flags & CHUNK_FREED_MASK) != 0)
/* Mark a chunk as free. */
#define SET_CHUNK_FREED(chunk_ptr) \
    ((chunk_ptr)->size_and_flags |= CHUNK_FREED_MASK)
/* Mark a chunk as allocated. */
#define CLEAR_CHUNK_FREED(chunk_ptr) \
    ((chunk_ptr)->size_and_flags &= ~CHUNK_FREED_MASK)

/* Set the boundary tag (footer) for a free chunk.
 * The footer is a copy of its header's 'size_and_flags'.
 * This is critical for 'free' to determine the size of adjacent blocks during
 * coalescing.
 */
#define SET_FOOTER(chunk_ptr, size_val)                                 \
    (*((size_t *) ((char *) (chunk_ptr) + size_val - sizeof(size_t))) = \
         (size_t) size_val)

/* Global free list sentinel node.
 * This is a static (not allocated via mmap) dummy node that simplifies
 * operations on the doubly linked free list. It only holds the pointers.
 */
free_list_node_t __freelist_head = {
    .next_free = &__freelist_head,
    .prev_free = &__freelist_head,
};

/* Threshold for deciding when to use direct 'mmap' for large allocations.
 * Allocations larger than or equal to this threshold will bypass the internal
 * heap and be handled directly by 'mmap' and 'munmap'.
 */
#define MMAP_THRESHOLD (PAGESIZE * 8) /* TODO: check */

free_list_node_t *get_free_node(chunk_t *chunk)
{
    return (free_list_node_t *) ((char *) chunk + CHUNK_HEADER_SIZE);
}

/* Adds a chunk to the head of the free list (LIFO - Last In, First Out).
 * LIFO often results in good cache locality for recently freed memory.
 */
void add_to_freelist(chunk_t *chunk)
{
    free_list_node_t *node = get_free_node(chunk);
    node->next_free = __freelist_head.next_free;
    node->prev_free = &__freelist_head;
    __freelist_head.next_free->prev_free = node;
    __freelist_head.next_free = node;
    SET_CHUNK_FREED(chunk);
    /* Must set footer when adding to free list */
    SET_FOOTER(chunk, GET_CHUNK_RAW_SIZE(chunk));
}

/* Removes a chunk from the free list. */
void remove_from_freelist(chunk_t *chunk)
{
    free_list_node_t *node = get_free_node(chunk);
    node->prev_free->next_free = node->next_free;
    node->next_free->prev_free = node->prev_free;
    CLEAR_CHUNK_FREED(chunk);
}

/* 'malloc' implementation. */
void *malloc(size_t size)
{
    if (!size)
        return NULL;

    /* Calculate required total chunk size including metadata and alignment.
     * CHUNK_HEADER_SIZE is added for the chunk's metadata.
     * The result is aligned up to MIN_ALIGNMENT.
     */
    size_t total_chunk_size = ALIGN_UP(size + CHUNK_HEADER_SIZE, MIN_ALIGNMENT);

    /* Ensure the chunk is at least MIN_CHUNK_SIZE to be a valid free chunk
     * if it's ever split or freed.
     */
    if (total_chunk_size < MIN_CHUNK_SIZE)
        total_chunk_size = MIN_CHUNK_SIZE;

    /* Loop to find or acquire memory. */
    while (1) {
        /* Handle large allocations directly via 'mmap'.
         * If the requested size is large enough, bypass the internal heap and
         * allocate directly from the OS using 'mmap'.
         */
        if (total_chunk_size >= MMAP_THRESHOLD) {
            /* Round up to page size for 'mmap' to avoid internal fragmentation
             * within the mmap'd region and ensure page-aligned memory.
             */
            size_t mmap_len = ALIGN_UP(total_chunk_size, PAGESIZE);
            chunk_t *mmaped_chunk = (chunk_t *) __syscall(
                SYS_MMAP, NULL, mmap_len, PROT_READ | PROT_WRITE,
                MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
            if ((long) mmaped_chunk == -1)
                return NULL;

            /* For directly mmap'd chunks, store only the raw size in
             * 'size_and_flags'. They are not part of the internal free list
             * management.
             */
            mmaped_chunk->size_and_flags = mmap_len;
            return CHUNK_TO_USER_DATA(mmaped_chunk);
        }

        /* Search for a suitable chunk in the internal free list (first-fit).
         * Iterate through the free list to find the first chunk that can
         * satisfy the request.
         */
        free_list_node_t *current_node = __freelist_head.next_free;
        while (current_node != &__freelist_head) {
            chunk_t *current_chunk =
                (chunk_t *) ((char *) current_node - CHUNK_HEADER_SIZE);
            size_t current_chunk_raw_size = GET_CHUNK_RAW_SIZE(current_chunk);

            if (current_chunk_raw_size >= total_chunk_size) {
                /* Found a suitable chunk. */
                remove_from_freelist(current_chunk);

                /* Check if we can split the chunk to avoid internal
                 * fragmentation. If the remaining size after allocation is
                 * large enough to form another valid free chunk
                 * (MIN_CHUNK_SIZE), then split it.
                 */
                size_t remaining_size =
                    current_chunk_raw_size - total_chunk_size;
                if (remaining_size >= MIN_CHUNK_SIZE) {
                    /* Split the chunk: 'current_chunk' becomes the allocated
                     * part. 'remainder_chunk' becomes the new free part.
                     */
                    chunk_t *remainder_chunk =
                        (chunk_t *) ((char *) current_chunk + total_chunk_size);
                    remainder_chunk->size_and_flags =
                        remaining_size; /* Store raw size for the remainder. */
                    add_to_freelist(remainder_chunk);

                    /* Update the allocated chunk's size. */
                    current_chunk->size_and_flags = total_chunk_size;
                } else {
                    /* No split, take the whole chunk. */
                    /* 'current_chunk->size_and_flags' already contains
                     * 'current_chunk_raw_size' with CHUNK_FREED_MASK cleared
                     * by 'remove_from_freelist'. So, no further change needed
                     * to 'current_chunk->size_and_flags' here.
                     */
                }
                return CHUNK_TO_USER_DATA(
                    current_chunk); /* Return the user data pointer. */
            }
            current_node = current_node->next_free;
        }

        /* No suitable chunk found in the free list, expand heap.
         * Allocate a new page (or more) from the OS and add it as a new large
         * free chunk to the freelist. This allows the internal heap to grow
         * dynamically.
         */
        size_t extend_size =
            ALIGN_UP(total_chunk_size > PAGESIZE ? total_chunk_size : PAGESIZE,
                     PAGESIZE);

        chunk_t *new_heap_chunk = (chunk_t *) __syscall(
            SYS_MMAP, NULL, extend_size, PROT_READ | PROT_WRITE,
            MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        if ((long) new_heap_chunk == -1)
            return NULL; /* 'mmap' failed, cannot allocate memory. */

        /* Store raw size for the new chunk. */
        new_heap_chunk->size_and_flags = extend_size;
        /* Add the new large free chunk to the list. */
        add_to_freelist(new_heap_chunk);
    }
}

/* 'free' implementation. */
void free(void *ptr)
{
    if (!ptr)
        return; /* Freeing a NULL pointer is a no-op. */

    chunk_t *chunk = USER_DATA_TO_CHUNK(ptr);
    size_t chunk_raw_size = GET_CHUNK_RAW_SIZE(chunk);

    /* Check for direct 'mmap'd chunks (large allocations).
     * If the chunk's raw size is >= MMAP_THRESHOLD and its start address is
     * page-aligned, it is likely a block directly allocated via 'mmap'. In this
     * case, 'munmap' it directly. This heuristic is simple and generally
     * effective for distinguishing from internal heap chunks.
     */
    if (chunk_raw_size >= MMAP_THRESHOLD && (uintptr_t) chunk % PAGESIZE == 0) {
        __syscall(SYS_MUNMAP, chunk, chunk_raw_size);
        return;
    }

    /* Double free check. */
    /* Abort if the chunk is already marked as free, indicating a double-free
     * attempt. */
    if (IS_CHUNK_FREED(chunk)) {
        abort(); /* Terminate the program. */
    }

    /* Coalescing logic (only with the next physically adjacent chunk).
     * First, mark the current chunk as free and set its footer.
     */
    SET_CHUNK_FREED(chunk);
    SET_FOOTER(chunk, chunk_raw_size);

    chunk_t *next_mc = NEXT_MEM_CHUNK(chunk);
    /* Coalesce with 'next_mc' if it's also free. */
    /* This relies on 'next_mc' being a valid chunk in the same contiguous
     * memory region. */
    if (IS_CHUNK_FREED(next_mc)) {     /* If next chunk is free. */
        remove_from_freelist(next_mc); /* Remove 'next_mc' from the freelist. */
        /* Extend the current chunk's size to include 'next_mc's size.
         * Preserve the CHUNK_FREED_MASK during this size update.
         */
        chunk->size_and_flags =
            (chunk_raw_size + GET_CHUNK_RAW_SIZE(next_mc)) | CHUNK_FREED_MASK;
        /* Update the footer for the new combined chunk. */
        SET_FOOTER(chunk, GET_CHUNK_RAW_SIZE(chunk));
    }

    /* Add the (potentially coalesced) chunk back to the free list. */
    add_to_freelist(chunk);
}

/* 'calloc' implementation. */
void *calloc(size_t n, size_t size)
{
    /* Check for overflow before multiplication to prevent vulnerabilities. */
    if (!n || !size)
        return NULL;
    size_t total_size;

    /* Manual overflow check for 'n * size'.
     * If 'size' is not zero and 'n' exceeds 'SIZE_MAX / size', an overflow
     * would occur.
     */
    if (size != 0 && n > (size_t) -1 / size)
        return NULL; /* Overflow occurred. */
    total_size = n * size;

    void *p = malloc(total_size);
    if (p)
        memset(p, 0, total_size); /* Zero-initialize the allocated memory. */
    return p;
}

[jserv]

@DrXiao, you can adapt the above PoC implementation and see if it works on Beaglebone hardware (without swap).

[DrXiao]

The improvement is still a work in progress because I have encountered a troublesome problem.

After enhancing the malloc/free routines, the bootstrap process fails with an unknown-cause segfault when building the stage 2 compiler.