dmmlib/src/freelist/freelist_malloc.c

/*
 *   Copyright Institute of Communication and Computer Systems (ICCS) 
 *
 *   Licensed under the Apache License, Version 2.0 (the "License");
 *   you may not use this file except in compliance with the License.
 *   You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 *
 */

/**
 * @file   freelist_malloc.c
 * @author Ioannis Koutras
 * @date   September 2012
 * @brief  malloc() implementation for freelist-organised raw blocks
 */

#include "freelist/freelist.h"

#include "freelist/block_header_funcs.h"
#include "freelist/linked_lists/linked_lists.h"
#include "freelist/linked_lists/search_algorithms.h"

#if defined (SPLITTING_FIXED) || defined (SPLITTING_VARIABLE)
#include "freelist/split.h"
#endif /* SPLITTING_FIXED || SPLITTING_VARIABLE */

#include "trace.h"

#ifdef WITH_ALLOCATOR_STATS
#include "dmmlib/dmmlib.h"
#endif /* WITH_ALLOCATOR_STATS */

/**
 * Tries to find the best available free memory block
 *
 * @param size The requested size
 */
#if defined (BEST_FIT)
#define search_on_free(size) best_fit_on_freelist(raw_block, size)
#elif defined (GOOD_FIT)
#define search_on_free(size) good_fit_on_freelist(raw_block, size)
#elif defined (EXACT_FIT)
#define search_on_free(size) exact_fit_on_freelist(raw_block, size)
#elif defined (FIRST_FIT)
#define search_on_free(size) first_fit_on_freelist(raw_block, size)
#endif /* BEST_FIT */ 

size_t req_padding(size_t size);

/** Tries to align the input to 32, 64, 128, 256 or to a multiple of 4 if it is
 * larger.
 *
 * @param size The input number.
 */
size_t req_padding(size_t size) {
    size_t align;

    if(size <= 32)
        return 32;
    if(size <= 64)
        return 64;
    if(size <= 128)
        return 128;
    if(size <= 256)
        return 256;

    align = size % 4;
    if(align != 0) {
        size += 4 - align;
    }

    return size;
}

/** Tries to allocate memory from a specific free-list organized raw block.
 * @param raw_block The pointer of the freelist-organised raw block.
 * @param size      The requested size.
 * @retval          The address of the returned memory space.
 */
void * freelist_malloc(freelist_rb_t *raw_block, size_t size) {
    block_header_t *ptr;
    size_t allocation_size, previous_size, previous_size_availability;

    ptr = NULL;

    ptr = search_on_free(size);

    if(ptr != NULL) {
#ifdef REQUEST_SIZE_INFO
        set_requested_size(ptr, size);
#endif /* REQUEST_SIZE_INFO */

        /* Try to split */
#if defined (SPLITTING_FIXED) || defined (SPLITTING_VARIABLE)
        split(raw_block, ptr, size);
#endif /* (SPLITTING_FIXED) || (SPLITTING_VARIABLE) */

        mark_used(raw_block, ptr);
    } else {

        allocation_size = req_padding(size) + HEADER_SIZE;

        if(allocation_size <= raw_block->remaining_size) {
            if(raw_block->border_ptr == NULL) {
                previous_size_availability = 1; // Occupied and of 0 size
                ptr = (block_header_t *)((char *)raw_block +
                        sizeof(freelist_rb_t));
            } else {
                previous_size = get_size(raw_block->border_ptr);
                previous_size_availability =
                    get_size_availability(raw_block->border_ptr);
                ptr = (block_header_t *)((char *)raw_block->border_ptr +
                        HEADER_SIZE + previous_size);
            }

            // Update raw block metadata
            raw_block->remaining_size -= allocation_size;
            raw_block->border_ptr = ptr;

            // Update block metadata
            set_size_and_used(raw_block, ptr, req_padding(size));
            set_previous_size_availability(ptr, previous_size_availability);
#ifdef REQUEST_SIZE_INFO
            set_requested_size(ptr, size);
#endif /* REQUEST_SIZE_INFO */
        }
    }

    if(ptr != NULL) {

#ifdef WITH_ALLOCATOR_STATS
            systemallocator.dmm_stats.total_mem_allocated +=
                get_size(ptr) + HEADER_SIZE;
            systemallocator.dmm_stats.live_objects++;
            systemallocator.dmm_stats.num_malloc++;
            TRACE_1("dmmlib - global allocated memory: %zu bytes\n",
                    systemallocator.dmm_stats.total_mem_allocated);
#ifdef REQUEST_SIZE_INFO
            systemallocator.dmm_stats.total_mem_requested += size;
            TRACE_1("dmmlib - global requested memory: %zu bytes\n",
                    systemallocator.dmm_stats.total_mem_requested);
#endif /* REQUEST_SIZE_INFO */
#endif /* WITH_ALLOCATOR_STATS */

        return (void *)((char *)ptr + HEADER_SIZE);
    } else {
        return NULL;
    }
}