<commit_before>/*
 * The "rubber" memory allocator.  It is a buffer for storing many
 * large objects.  Unlike heap memory, unused areas are given back to
 * the operating system.
 *
 * author: <NAME> <<EMAIL>>
 */

#include "rubber.h"

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

struct rubber_object {
    /**
     * The next object index or 0 for end of list.
     */
    unsigned next;

    /**
     * The previous object index.  Not used for the "free" list.
     */
    unsigned previous;

    /**
     * The offset of this object within the memory map.
     */
    size_t offset;

    /**
     * The size of this object.
     */
    size_t size;

#ifndef NDEBUG
    bool allocated;
#endif
};

struct rubber_table {
    /**
     * The allocated size of the table (maximum number of objects).
     */
    unsigned max_entries;

    /**
     * The index after the last initialized table entry.  We avoid
     * initializing all entries on startup, because this may make the
     * kernel allocate physical memory for table areas we don't need
     * (yet).
     */
    unsigned initialized_tail;

    /**
     * The index of the allocated object with the largest offset (the
     * "head" is always 0, which points to the table).  The linked
     * list is sorted by offset.
     */
    unsigned allocated_tail;

    /**
     * The index of the first free table entry.  The linked list
     * contains all free entries in no specific order.  This is 0 if
     * the table is full.
     */
    unsigned free_head;

    /**
     * The first entry (index 0) is the table itself.
     */
    struct rubber_object entries[1];
};

struct rubber {
    /**
     * The maximum size of the memory map.  This is the value passed
     * to rubber_new() and will never be changed.
     */
    size_t max_size;

    /**
     * The offset of the first free byte after the last allocation.
     * This is the amount of physical memory allocated by the kernel
     * for our memory map.
     */
    size_t brutto_size;

    /**
     * The sum of all allocation sizes.
     */
    size_t netto_size;

    /**
     * The table managing the allocations in the memory map.  At the
     * same time, this is the pointer to the memory map.
     */
    struct rubber_table *table;
};

gcc_const
static inline size_t
align_page_size(size_t size)
{
    return ((size - 1) | 0x3fffff) + 1;
}

gcc_const
static inline size_t
align_size(size_t size)
{
    return ((size - 1) | 0x1f) + 1;
}

/**
 * Calculate the size [in bytes] of a #rubber_table struct for the
 * given number of entries.
 */
gcc_const
static inline size_t
rubber_table_size(unsigned n)
{
    assert(n > 0);

    const struct rubber_table *dummy = NULL;
    return sizeof(*dummy) + sizeof(dummy->entries) * (n - 1);
}

/**
 * Calculate the capacity [in number of entries] of a #rubber_table
 * struct for the given size [in bytes].
 */
gcc_const
static inline unsigned
rubber_table_capacity(size_t size)
{
    const struct rubber_table *dummy = NULL;
    assert(size >= sizeof(*dummy));

    return (size - sizeof(*dummy)) / sizeof(dummy->entries) + 1;
}

static size_t
rubber_table_init(struct rubber_table *t, unsigned max_entries)
{
    assert(max_entries > 1);

    t->initialized_tail = 1;
    t->allocated_tail = 0;

    /* round to nearest "huge page", so the first real allocation
       starts at a "huge page" boundary */
    const size_t table_size = align_page_size(rubber_table_size(max_entries));

    t->entries[0] = (struct rubber_object){
        .next = 0,
        .offset = 0,
        .size = table_size,
    };

    t->max_entries = rubber_table_capacity(t->entries[0].size);

    t->free_head = 0;

#ifndef NDEBUG
    t->entries[0].allocated = true;
#endif

    return table_size;<commit_msg>rubber: rename _table_size() to _table_required_size()<commit_after>/*
 * The "rubber" memory allocator.  It is a buffer for storing many
 * large objects.  Unlike heap memory, unused areas are given back to
 * the operating system.
 *
 * author: <NAME> <<EMAIL>>
 */

#include "rubber.h"

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

struct rubber_object {
    /**
     * The next object index or 0 for end of list.
     */
    unsigned next;

    /**
     * The previous object index.  Not used for the "free" list.
     */
    unsigned previous;

    /**
     * The offset of this object within the memory map.
     */
    size_t offset;

    /**
     * The size of this object.
     */
    size_t size;

#ifndef NDEBUG
    bool allocated;
#endif
};

struct rubber_table {
    /**
     * The allocated size of the table (maximum number of objects).
     */
    unsigned max_entries;

    /**
     * The index after the last initialized table entry.  We avoid
     * initializing all entries on startup, because this may make the
     * kernel allocate physical memory for table areas we don't need
     * (yet).
     */
    unsigned initialized_tail;

    /**
     * The index of the allocated object with the largest offset (the
     * "head" is always 0, which points to the table).  The linked
     * list is sorted by offset.
     */
    unsigned allocated_tail;

    /**
     * The index of the first free table entry.  The linked list
     * contains all free entries in no specific order.  This is 0 if
     * the table is full.
     */
    unsigned free_head;

    /**
     * The first entry (index 0) is the table itself.
     */
    struct rubber_object entries[1];
};

struct rubber {
    /**
     * The maximum size of the memory map.  This is the value passed
     * to rubber_new() and will never be changed.
     */
    size_t max_size;

    /**
     * The offset of the first free byte after the last allocation.
     * This is the amount of physical memory allocated by the kernel
     * for our memory map.
     */
    size_t brutto_size;

    /**
     * The sum of all allocation sizes.
     */
    size_t netto_size;

    /**
     * The table managing the allocations in the memory map.  At the
     * same time, this is the pointer to the memory map.
     */
    struct rubber_table *table;
};

gcc_const
static inline size_t
align_page_size(size_t size)
{
    return ((size - 1) | 0x3fffff) + 1;
}

gcc_const
static inline size_t
align_size(size_t size)
{
    return ((size - 1) | 0x1f) + 1;
}

/**
 * Calculate the size [in bytes] of a #rubber_table struct for the
 * given number of entries.
 */
gcc_const
static inline size_t
rubber_table_required_size(unsigned n)
{
    assert(n > 0);

    const struct rubber_table *dummy = NULL;
    return sizeof(*dummy) + sizeof(dummy->entries) * (n - 1);
}

/**
 * Calculate the capacity [in number of entries] of a #rubber_table
 * struct for the given size [in bytes].
 */
gcc_const
static inline unsigned
rubber_table_capacity(size_t size)
{
    const struct rubber_table *dummy = NULL;
    assert(size >= sizeof(*dummy));

    return (size - sizeof(*dummy)) / sizeof(dummy->entries) + 1;
}

static size_t
rubber_table_init(struct rubber_table *t, unsigned max_entries)
{
    assert(max_entries > 1);

    t->initialized_tail = 1;
    t->allocated_tail = 0;

    /* round to nearest "huge page", so the first real allocation
       starts at a "huge page" boundary */
    const size_t table_size =
        align_page_size(rubber_table_required_size(max_entries));

    t->entries[0] = (struct rubber_object){
        .next = 0,
        .offset = 0,
        .size = table_size,
    };

    t->max_entries = rubber_table_capacity(t->entries[0].size);

    t->free_head = 0;

#ifndef NDEBUG
    t->entries[0].allocated = true;
#endif

    return table_size;
{'fraction_non_alphanumeric': 0.10040056854890812, 'fraction_numerical': 0.006460783046905285, 'mean_word_length': 2.5586206896551724, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5150309', 'n_tokens_mistral': 2470, 'n_tokens_neox': 2375, 'n_words': 873}