/*
 * Two Levels Segregate Fit memory allocator (TLSF)
 * Version 1.3
 *
 * Written by Miguel Masmano Tello <mmasmano@disca.upv.es>
 *
 * Thanks to Ismael Ripoll for his suggestions and reviews
 *
 * Copyright (C) April 2004 UPVLC, OCERA Consortium
 * 
 * This code is released using a dual license strategy: GPL/LGPL
 * You can choose the license that better fits your requirements.
 *
 * Released under the terms of the GNU General Public License Version 2.0
 * Released under the terms of the GNU Lesser General Public License Version 2.1
 *
 */

#include "TLSF_nondep.h"
#include "TLSF_struct_functions.h"

/*
 * see man free
 *
 * free () is only guaranteed  to work if ptr is the address
 * of a block allocated by rt_malloc() (and not yet freed).
 */

void
FREE_FUNCTION_EX (void *ptr, char *block_ptr)
{
    THREAD_LOCK_FNC_HEAD
    __s32 aux_size, fl, sl, new_size;
    block_header_t *bh, *bh2, *bh3;

    TLSF_t *ptr_TLSF;

    ptr_TLSF = (TLSF_t *) block_ptr;

#ifdef SANITY_CHECK
    checking_structure (ptr_TLSF, "Entering free");
    check_range_ptr (block_ptr, "malloc 1");
#endif

    if (!ptr_TLSF || ptr_TLSF->magic_number != MAGIC_NUMBER) {
	PRINT_MSG ("free() error: TLSF structure is not initialized\n");
	PRINT_MSG ("Hint: Execute init_memory_pool() before calling free()");
	return;
    }

    bh = (block_header_t *) ((__u8 *) ptr -
			     TLSF_WORDS2BYTES (beg_header_overhead));

    THREAD_LOCK ();
    /* now bh is a free block */

    SET_FREE_BLOCK (bh);
    bh->ptr.free_ptr.prev = NULL;
    bh->ptr.free_ptr.next = NULL;

    /*
     * first of all, we will try to merge bh with the
     * physically contiguos free block and
     * after we will inserte bh into TLSF structure
     */

    /* Now we will try if we can merge bh with the next phys. contiguos block */
    if (!IS_LAST_BLOCK (bh)) {
	/* is it the next block free? */
	/* The next block is easy to found */

	bh2 = (block_header_t *) (bh->ptr.buffer +
				  TLSF_WORDS2BYTES (GET_BLOCK_SIZE (bh)));

#ifdef SANITY_CHECK
	check_range_bh (bh2, "free 1");
	check_mn (bh2, "free 1");
#endif


	if (!IS_USED_BLOCK (bh2)) {
	    /* we are lucky, we can merge bh with the following one */

	    remove_block (bh2, ptr_TLSF);

	    bh->size += bh2->size + beg_header_overhead;

	    if (!IS_LAST_BLOCK (bh2)) {
		bh3 = (block_header_t *) (bh2->ptr.buffer +
					  TLSF_WORDS2BYTES
					  (GET_BLOCK_SIZE (bh2)));
		bh3->prev_phys_block = bh;
	    }
	}
    }

    /* is it free the previous physical block? */
    if (bh->prev_phys_block) {	// This block is not the first block

	bh2 = bh->prev_phys_block;
#ifdef SANITY_CHECK
	check_range_bh (bh2, "free 2");
	check_mn (bh2, "free 2");
#endif
	if (!IS_USED_BLOCK (bh2)) {

	    remove_block (bh2, ptr_TLSF);

	    bh2->size += bh->size + beg_header_overhead;

	    bh = bh2;

	    if (!IS_LAST_BLOCK (bh)) {
		bh3 = (block_header_t *) (bh->ptr.buffer +
					  TLSF_WORDS2BYTES
					  (GET_BLOCK_SIZE (bh)));
		bh3->prev_phys_block = bh;

#ifdef SANITY_CHECK
		check_range_bh (bh3, "free 3");
		check_mn (bh3, "free 3");
#endif
	    }
	}
    }

    /*
     * and now we can merge the free block with the initial memory
     */
    aux_size = GET_BLOCK_SIZE (bh);

    if (aux_size < ptr_TLSF->TLSF_max_struct_size) {
	mapping_function (aux_size, &fl, &sl, &new_size, ptr_TLSF);
#ifdef SANITY_CHECK
	check_fl_sl (fl, sl, ptr_TLSF, "free 1");
#endif
    } else {
	fl = ptr_TLSF->max_fl_index - 1;
	sl = ptr_TLSF->max_sl_index - 1;
    }

    fl -= MIN_LOG2_SIZE;

#ifdef SANITY_CHECK
    check_fl_sl_2 (fl, sl, ptr_TLSF, "free 2");
#endif

    init_and_insert_block (ptr_TLSF, bh, fl, sl);

    THREAD_UNLOCK ();

#ifdef SANITY_CHECK
    checking_structure (ptr_TLSF, "Leaving free");
#endif
}