dmmlib/src/freelist/coalesce.c

/*
 *   Copyright 2011 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.
 *
 */

#include "dmm_config.h"

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

#include "freelist/coalesce.h"
#include "freelist/block_header_funcs.h"
#include "freelist/ordering_policy.h"

void coalesce(freelist_rb_t *raw_block, block_header_t *ptr) {
    size_t max_coal_size;
    size_t size;
    size_t current_next_size;
    size_t previous_current_size;
    size_t three_blocks_size;
    block_header_t *previous_block, *next_block;

#ifdef COALESCING_FIXED
    max_coal_size = MAX_COALESCE_SIZE;
#endif /* COALESCING_FIXED */
#ifdef COALESCING_VARIABLE
    max_coal_size = (size_t) systemallocator.dmm_knobs.max_coalesce_size;
#endif /* COALESCING_VARIABLE */

    size = get_size(ptr);

    previous_block = get_dlprevious(ptr);
    next_block = get_dlnext(raw_block, ptr);

    /* Find out the sizes of all possible combinations */

    /* Current + Next */
    if(next_block != NULL && is_free(next_block) == true) {
        current_next_size = size + get_size(next_block) + HEADER_SIZE;
    } else {
        current_next_size = (size_t) -1; /* SIZE_MAX */
    }

    /* Previous + Current */
    if(is_previous_free(ptr) == true) {
        previous_current_size = size + get_previous_size(ptr) + HEADER_SIZE;
    } else {
        previous_current_size = (size_t) -1; /* SIZE_MAX */
    }

    /* Previous + Current + Next */
    if(is_previous_free(ptr) == true && next_block != NULL &&
            is_free(next_block) == true) {
        three_blocks_size = get_previous_size(ptr) + size +
            get_size(next_block) + 2 * HEADER_SIZE;
    } else {
        three_blocks_size = (size_t) -1; /* SIZE_MAX */
    }

    /* Check if Previous + Current + Next is ok */
    if(three_blocks_size <= max_coal_size) {
        /* Remove the next block from the free list */
        REMOVE_FSLLIST(raw_block, next_block);
        /* Update border pointer if the next block was the border pointer */
        if(raw_block->border_ptr == next_block) {
            raw_block->border_ptr = previous_block;
        }
        /* Reset the previous block size */
        set_size_and_free(raw_block, previous_block, three_blocks_size);
        return;
    }

    /* Check if Previous + Current is ok */
    if(previous_current_size <= max_coal_size) {
        /* Update border pointer if the current block was the border pointer */
        if(raw_block->border_ptr == ptr) {
            raw_block->border_ptr = previous_block;
        }
        /* Reset the previous block size */
        set_size_and_free(raw_block, previous_block, previous_current_size);
        return;
    }
 
    /* Check if Current + Next is ok */
    if(current_next_size <= max_coal_size) {
        REMOVE_FSLLIST(raw_block, next_block);
        if(raw_block->border_ptr == next_block) {
            raw_block->border_ptr = ptr;
        }
        set_size_and_free(raw_block, ptr, current_next_size);
        ADD_BLOCK(ptr);
        return;
    }

    /* If everything fails, just mark the block free and add it to the free
     * list
     */
    mark_free(raw_block, ptr);
    ADD_BLOCK(ptr);
    return;
}