Custom Memory Management Library (Course: UNC, FCEFyN, Operative Systems I, Laboratory 3) application. Makes use of the library recurrently, for benchmarking purposes.

cmml_app.c

/**
 * @file cmml_app.c
 * @brief Main program file.
 */

#include "memory.h"

//! \brief Amount of allocated blocks per test.
#define NUM_OPERATIONS 10000
//! \brief Max amount of block data (in bytes), per block.
#define MAX_B_DATA_SIZE 128
//! \brief RNG system fixed seed; the variant is to use `time(NULL)`.
#define XORSHIFT_SEED 3370684199
//! \brief Free blocks every next amount of allocated blocks.
#define BLOCKS_FREE_EVERY 3

/* PROTOTYPES */
//! \brief Seed setting for an implementation of XorShift PRNG.
void xorshift_srand(unsigned int seed);
//! \brief Own implementation of XorShift PRNG.
unsigned int xorshift_rand(void);
//! \brief Test & benchmark for the FIRST_FIT allocation policy.
void run_first_fit_policy_batch(void);
//! \brief Test & benchmark for the BEST_FIT allocation policy.
void run_best_fit_policy_batch(void);
//! \brief Test & benchmark for the WORST_FIT allocation policy.
void run_worst_fit_policy_batch(void);
//! \brief Helper function for benchmarking a policy.
void benchmark_policy(int policy);
//! \brief Reports the result of benchmarking certain policy.
void report_result(int policy, double fragmentation_perc);
//! \brief Helper function to calculate fragmentation (0~1 * 100 = x%).
double calculate_fragmentation(void);
//! \brief Cleans the heap. The lone arg shall be an array to pointers pointing to allocated data.
void destroy_memory(void** allocated_data);

/* Global vars */
static unsigned int xor_state; // Seed

/* Helper functions definition */
void xorshift_srand(unsigned int seed) {
    xor_state = seed;
}

unsigned int xorshift_rand(void) {
    xor_state ^= xor_state << 13;
    xor_state ^= xor_state >> 17;
    xor_state ^= xor_state << 5;
    return xor_state;
}

void run_first_fit_policy_batch(void) {
    set_method(FIRST_FIT);
    benchmark_policy(FIRST_FIT);
}

void run_best_fit_policy_batch(void) {
    set_method(BEST_FIT);
    benchmark_policy(BEST_FIT);
}

void run_worst_fit_policy_batch(void) {
    set_method(WORST_FIT);
    benchmark_policy(WORST_FIT);
}

void benchmark_policy(int policy) {
    // 0-initialize the elements to allocate pointers to data claimed
    void* allocated_data[NUM_OPERATIONS] = {0};
    // Perform random allocations and deallocations
    for (int i = LOWEST_ARR_INDEX; i < NUM_OPERATIONS; i++)
    {
        // Data claimed is random
        size_t size = xorshift_rand() % MAX_B_DATA_SIZE + 1;
        // malloc() should return a ptr to the data claimed (not to the block which has that data as part of it)
        allocated_data[i] = malloc(size);
        if (allocated_data[i] == NULL)
        {
            wstderr("ERROR: malloc() returned NULL on one of its call, aborting this test.\n");
            return;
        }
        // Free one block every 3 of them
        if (((i % BLOCKS_FREE_EVERY) == 0) && (allocated_data[i / BLOCKS_FREE_EVERY]))
        {
            free(allocated_data[i / BLOCKS_FREE_EVERY]);
            // Freed memory can no longer be used
            allocated_data[i / BLOCKS_FREE_EVERY] = NULL;
        }
    }
    // Report the result & clean the heap
    report_result(policy, calculate_fragmentation());
    destroy_memory(allocated_data);
}

void report_result(int policy, double fragmentation_perc)
{
    static unsigned int ff_calls = 0, bf_calls = 0, wf_calls = 0;
    // fr: fragmentation rate
    static double ff_fr = 0.0, bf_fr = 0.0, wf_fr = 0.0;
    // Re-calculate rates and report the findings
    switch (policy)
    {
    case FIRST_FIT:
        ff_fr = ((ff_calls * ff_fr) + fragmentation_perc)/(ff_calls + 1);
        ff_calls++;
        printf("f %u p %f\n", ff_calls, ff_fr);
        break;
    case BEST_FIT:
        bf_fr = ((bf_calls * bf_fr) + fragmentation_perc)/(bf_calls + 1);
        bf_calls++;
        printf("b %u p %f\n", bf_calls, bf_fr);
        break;
    default:
        // WORST_FIT
        wf_fr = ((wf_calls * wf_fr) + fragmentation_perc)/(wf_calls + 1);
        wf_calls++;
        printf("w %u p %f\n", wf_calls, wf_fr);
    }
    fflush(stdout);
}

double calculate_fragmentation(void)
{
    size_t total_free = 0;
    size_t largest_free_block = 0;
    // Iterate over each mem block of the heap
    for (t_block block = get_heap_base(); block != NULL; block = block->next)
    {
        // Check good allocation
        if ((block->ptr == block->data) && block->free)
        {
            total_free += block->size;
            if (block->size > largest_free_block)
            {
                largest_free_block = block->size;
            }
        }
    }
    if (total_free == 0)
    {
        return 0.0;
    }
    // The smaller are the pieces of free memory, the more fragmentation there is
    return (1.0 - ((double)largest_free_block / (double)total_free)) * 100.0;
}

void destroy_memory(void** allocated_data)
{
    for (int i = LOWEST_ARR_INDEX; i < NUM_OPERATIONS; i++)
    {
        if (allocated_data[i] != NULL)
        {
            free(allocated_data[i]);
            // Once freed, that memory can't be accessed
            allocated_data[i] = NULL;
        }
    }
}

//! \brief Main function for testing.
int main(int argc, char* argv[])
{
    (void)argc;
    (void)argv;

    // Seed the RNG
    xorshift_srand(XORSHIFT_SEED);

    // Loop benchmarking different policies, randomly
    while (1)
    {
        switch (xorshift_rand() % 3)
        {
        case 0:
            run_first_fit_policy_batch();
            break;
        case 1:
            run_best_fit_policy_batch();
            break;
        default:
            // case 2
            run_worst_fit_policy_batch();
        }
        // sleep a bit
        sleep(1);
    }

    return 0;
}