0,0 → 1,887 |
/* |
* Doubly indexed dynamic memory allocator (DIDMA) |
* Version 0.61 |
* |
* Written by Miguel Masmano Tello <mmasmano@disca.upv.es> |
* Copyright (C) Dec, 2002 OCERA Consortium |
* Release under the terms of the GNU General Public License Version 2 |
* shark porting Trimarchi Michael |
*/ |
|
#include <kernel/func.h> |
#include "didma.h" |
#include "queuem.h" |
#include "i386/bitops.h" |
#include "i386/bits.h" |
|
#ifndef NULL |
#define NULL ((void *) 0) |
#endif // #ifndef NULL |
|
|
#define INIT_THREAD_MUTEX() |
#define THREAD_LOCK() kern_cli() |
#define THREAD_UNLOCK() kern_sti() |
|
// u8, u16, u32 are only defined in kernel headers |
|
#define u8 char |
#define u16 unsigned short int |
#define u32 unsigned int |
|
#define MAX_SL_LOG2_INDEX 5 // Real value is 2**MAX_SL_INDEX |
|
#define MAX_SL_INDEX (1 << MAX_SL_LOG2_INDEX) |
|
#define F_OK 0 |
#define F_ERROR -1 |
|
#define MIN_LOG2_SIZE 5 // 32 bytes |
#define MAX_LOG2_SIZE MAX_FL_INDEX |
#define MIN_SIZE (1 << MIN_LOG2_SIZE) |
#define MAX_SIZE (1 << MAX_LOG2_SIZE) |
|
#define DIDMA__set_bit(num, mem) mem |= (1 << num) |
#define DIDMA__clear_bit(num, mem) mem &= ~(1 << num) |
|
/* |
* First, all necessary TADs are defined |
*/ |
|
|
/* |
* the follow TAD will be a double level indexed array, the most important |
* thing is that the time is limited, it is because this dynamic memory manger |
* is designed to run with real time programs. |
* |
* First level Second level |
* it is indexed it is indexed by 2**n+(2**n/m*index_number) |
* by power of 2 |
* 0 1 m-1 m |
* ----> NULL --> NULL ----> NUL |
* | | | |
* ------- ---------------------...--------------------- |
* 2**n | n | -----> |2**n+(2**n/m*0)|...| |...|2**n+(2**n/m*m)| |
* |-----| ---------------------...--------------------- |
* 2**n-1| n-1 | -----> .... | |
* |-----| --->NULL |
* ..... |
*/ |
|
/* DON'T TOUCH THESE MACROS */ |
#define MAGIC_NUMBER 0xA5A5 |
#define MAGIC_NUMBER_NONE 0x0000 |
#define BLOCK_FREE 0 |
#define BLOCK_USED 1 |
|
|
struct free_ptr_struct { |
struct block_header_struct *prev; |
struct block_header_struct *next; |
/* |
* first_l_index and second_l_index are used to store |
* mapping_function results, that's how we get some extra |
* nanoseconds |
*/ |
u8 first_l_index; |
u8 second_l_index; |
}; |
|
typedef struct block_header_struct { |
/* magic_number is the id of the block */ |
u16 magic_number; |
/* size of the block */ |
size_t size; |
/* state of the block can be free or used */ |
u8 state; |
|
struct block_header_struct *prev; |
struct block_header_struct *next; |
|
union { |
struct free_ptr_struct free_ptr; |
u8 buffer[sizeof(struct free_ptr_struct)]; |
} ptr; |
} block_header_t; |
|
/* first level index array */ |
typedef struct fl_array_struct { |
/* ptr is pointer to next level */ |
block_header_t **sl_array; |
/* n_blocks is the number of the blocks which they are pointed by sl_array */ |
u32 bitmapSL; |
} fl_array_t; |
|
/* |
* fl_array will be our first level array. |
*/ |
|
static fl_array_t *fl_array;// [MAX_FL_INDEX - MIN_LOG2_SIZE]; |
u32 bitmapFL; |
/* |
* first_bh will be our first memory block allocated by MALLOC function |
*/ |
static block_header_t *first_bh, *free_block; |
|
static int all_ok = 0; |
|
/* |
* header_overhead has size of blocks_header - 2 * ptr to next free block |
*/ |
static int header_overhead = 0, total_size = 0; |
|
/* |
* log2size () returns cell of log2 (len) |
* it does a search between MIN_SIZE and MAX_SIZE values |
*/ |
static int log2size(size_t size, size_t *new_size) |
{ |
int i; |
|
if (size <= 0) { |
PRINT_MSG ("ERROR: Chunk length must be > 0\n"); |
return F_ERROR; |
} |
|
|
// MIN_SIZE and MAX_SIZE must be defined |
|
if (size <= MIN_SIZE){ |
*new_size = MIN_SIZE; |
return MIN_LOG2_SIZE; |
} |
|
for (i = MIN_LOG2_SIZE; |
(i <= MAX_LOG2_SIZE) && (size > (*new_size = (1 << i))) ; i++); |
|
if (i > MAX_LOG2_SIZE) { |
PRINT_MSG ("ERROR: Maximum chunk size exceeded\n"); |
return F_ERROR; |
} |
|
return i; |
} |
|
/* |
* caculate_reserve () returns the size that has to be reservate for |
* avoid fragmentation |
*/ |
|
#define MAX(a, b) (a>b)?a:b |
|
/* |
May be calculate_reserve can be improved |
*/ |
|
static inline int calculate_reserve (int size){ |
// int internal_frag, dummy; |
|
// header_overhead = (int) first_bh -> ptr.buffer - (int) first_bh; |
|
//internal_frag = (1 << log2size(size, &dummy)) / MAX_SL_INDEX; |
|
//dummy = MAX((header_overhead * size / MAX_SL_INDEX) + internal_frag, size); |
|
return size;//(size + dummy); |
|
} |
|
/* |
* mapping_function () returns first and second level index |
* |
* first level index function is: |
* fl = log2 (size) |
* |
* and second level index function is: |
* sl = (size - 2**(log2size (size))) / (log2 (size) - log2 (MAX_SL_INDEX)) |
* |
*/ |
static int mapping_function (size_t size, int *fl, int *sl){ |
int aux; |
int new_len; |
|
// first level = log2 (size) |
*fl = log2size (size, &new_len); |
|
if (new_len == size) { |
// if 2**fl == size, second level must be 0 |
*sl = 0; |
} else { |
-- *fl; |
aux = *fl - MAX_SL_LOG2_INDEX; |
*sl = (int)((size - (new_len >> 1)) >> aux); |
} |
|
*fl -= MIN_LOG2_SIZE; |
return F_OK; |
} |
|
/* |
* init_TAD () initialize the structure fl_array to NULL |
* and free_block with the initial blocks pointed by ptr |
* |
* its cost is O (n x m) |
*/ |
static int init_TAD (size_t size, u8 *ptr){ |
int n, aux, dummy; |
if (!(size > 0)) { |
PRINT_MSG ("ERROR: size must be > 0\n"); |
return F_ERROR; |
} |
if (MAX_SL_INDEX > MIN_SIZE) { |
PRINT_MSG ("ERROR: MAX_SL_INDEX must be < MIN_SIZE\n"); |
return F_ERROR; |
} |
|
total_size = size; |
|
MAX_FL_INDEX = log2size(size, &dummy); |
|
if (MAX_FL_INDEX < 0) return -1; |
fl_array = (fl_array_t *) SYSTEM_MALLOC ((MAX_FL_INDEX - MIN_LOG2_SIZE) |
* sizeof(fl_array_t)); |
if (fl_array == NULL) return -1; |
_init_malloc_ (20); |
for (n = 0; n < MAX_FL_INDEX - MIN_LOG2_SIZE; n++) { |
fl_array [n].bitmapSL = 0; |
aux = (1 << (n + MIN_LOG2_SIZE)); |
fl_array[n].sl_array = NULL; |
} |
bitmapFL = 0; |
|
header_overhead = (int) first_bh -> ptr.buffer - (int) first_bh; |
first_bh = (block_header_t *) ptr; |
|
first_bh -> magic_number = MAGIC_NUMBER; |
first_bh -> size = size - header_overhead; |
first_bh -> state = BLOCK_FREE; |
first_bh -> prev = NULL; |
first_bh -> next = NULL; |
first_bh -> ptr.free_ptr.prev = NULL; |
first_bh -> ptr.free_ptr.next = NULL; |
|
free_block = first_bh; |
//mapping_function (first_bh->size,&n, &m); |
//fl_array[n].sl_array[m].ptr= first_bh; |
//DIDMA__set_bit (m, fl_array[n].bitmapSL); |
//DIDMA__set_bit (n, bitmapFL); |
all_ok = 1; |
return F_OK; |
} |
|
/* |
* destroy_TAD return a pointer to the initial block |
*/ |
static void *destroy_TAD (void){ |
all_ok = 0; |
_destroy_malloc_(); |
return (void *) first_bh; |
} |
|
/* |
* insert_TAD merge a free block pointed by ptr |
* with its buddies and then |
* insert it into fl_array |
* |
* The cost of this operation is |
* always O (K) = (1) |
*/ |
static int insert_TAD (u8 *ptr){ |
int fl, sl; |
block_header_t *bh = NULL, *bh2; |
int for_free_block = 0; |
|
if (!all_ok) return F_ERROR; |
|
bh = (block_header_t *) (ptr - header_overhead); |
if (bh -> magic_number != MAGIC_NUMBER) |
return F_ERROR; |
|
THREAD_LOCK(); |
/* |
* now bh is a free block |
*/ |
bh -> state = BLOCK_FREE; |
bh -> ptr.free_ptr.prev = NULL; |
bh -> ptr.free_ptr.next = NULL; |
|
/* |
* first bh will be merge with its free buddies and |
* then it will be inserted with the free blocks |
*/ |
/* |
* it is used to know if bh have to be inserted into free_block or |
* into fl_array |
*/ |
if (bh -> next == NULL) for_free_block = 1; |
|
/* is it free the follow block? */ |
if (bh -> next != NULL) { |
bh2 = bh -> next; |
|
if (bh2 -> magic_number == MAGIC_NUMBER && |
bh2 -> state == BLOCK_FREE) { |
/* we are lucky, we can merge bh with the next block */ |
|
if (bh2 == free_block) for_free_block = 1; |
bh2 -> magic_number = MAGIC_NUMBER_NONE; |
if (bh2 -> next != NULL) |
bh2 -> next -> prev = bh; |
if (!for_free_block) { |
if (bh2 -> ptr.free_ptr.next != NULL) |
bh2 -> ptr.free_ptr.next -> ptr.free_ptr.prev = |
bh2 -> ptr.free_ptr.prev; |
|
if (bh2 -> ptr.free_ptr.prev != NULL) |
bh2 -> ptr.free_ptr.prev -> ptr.free_ptr.next = |
bh2 -> ptr.free_ptr.next; |
//mapping_function (bh2 -> size, &fl, &sl); |
fl = bh2 -> ptr.free_ptr.first_l_index; |
sl = bh2 -> ptr.free_ptr.second_l_index; |
/* bh2 must be erased from fl_array */ |
if (fl_array [fl].sl_array [sl] == bh2) |
fl_array [fl].sl_array [sl] = bh2 -> ptr.free_ptr.next; |
|
//fl_array [fl].n_blocks --; |
if (fl_array [fl].sl_array [sl] == NULL){ |
//fl_array[fl].bitmapSL &= ~(1 << sl); |
DIDMA__clear_bit (sl, fl_array[fl].bitmapSL); |
if (!fl_array[fl].bitmapSL) { |
_free_ ((void *) fl_array [fl].sl_array); |
DIDMA__clear_bit (fl, bitmapFL); |
} |
} |
} |
bh -> size += bh2 -> size + header_overhead; |
bh -> next = bh2 -> next; |
} |
} |
|
/* is it free the previous block? */ |
if (bh -> prev != NULL) { |
bh2 = bh -> prev; |
if (bh2 -> magic_number == MAGIC_NUMBER && |
bh2 -> state == BLOCK_FREE) { |
bh -> magic_number = MAGIC_NUMBER_NONE; |
|
if (bh -> next != NULL) |
bh -> next -> prev = bh2; |
|
if (bh2 -> ptr.free_ptr.next != NULL) |
bh2 -> ptr.free_ptr.next -> ptr.free_ptr.prev = |
bh2 -> ptr.free_ptr.prev; |
|
if (bh2 -> ptr.free_ptr.prev != NULL) |
bh2 -> ptr.free_ptr.prev -> ptr.free_ptr.next = |
bh2 -> ptr.free_ptr.next; |
|
//mapping_function (bh2 -> size, &fl, &sl); |
|
fl = bh2 -> ptr.free_ptr.first_l_index; |
sl = bh2 -> ptr.free_ptr.second_l_index; |
if (fl_array [fl].sl_array [sl] == bh2) |
fl_array [fl].sl_array [sl] = bh2 -> ptr.free_ptr.next; |
|
if (fl_array[fl].sl_array[sl] == NULL){ |
//fl_array[fl].bitmapSL &= ~(1 << sl); |
DIDMA__clear_bit (sl, fl_array[fl].bitmapSL); |
if (!fl_array[fl].bitmapSL) { |
_free_ ((void *) fl_array [fl].sl_array); |
DIDMA__clear_bit (fl, bitmapFL); |
} |
} |
|
bh2 -> size += bh -> size + header_overhead; |
bh2 -> next = bh -> next; |
bh = bh2; |
|
} |
} |
|
/* |
* and then we merge the free block with the initial memory |
*/ |
if (for_free_block) { |
free_block = bh; |
bh -> ptr.free_ptr.next = NULL; |
bh -> ptr.free_ptr.prev = NULL; |
} else { |
/* |
* or we insert the free block in the TAD |
*/ |
mapping_function (bh -> size, &fl, &sl); |
if (fl_array[fl].bitmapSL == 0) |
fl_array[fl].sl_array = (block_header_t **) _malloc_ (); |
if (fl_array[fl].sl_array == NULL) { |
PRINT_MSG("CRITICAL ERROR: there isn't enought memory for free\n"); |
return F_ERROR; |
} |
bh -> ptr.free_ptr.first_l_index = fl; |
bh -> ptr.free_ptr.second_l_index = sl; |
bh -> ptr.free_ptr.next = fl_array [fl].sl_array [sl]; |
bh -> ptr.free_ptr.prev = NULL; |
if (fl_array [fl].sl_array [sl] != NULL) |
fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = bh; |
fl_array [fl].sl_array [sl] = bh; |
|
DIDMA__set_bit (sl, fl_array[fl].bitmapSL); |
DIDMA__set_bit (fl, bitmapFL); |
|
} |
|
THREAD_UNLOCK(); |
return F_OK; |
} |
|
/* |
* search_TAD searchs a free block of size 'size' |
* then this block will be splitted in two new blocks, |
* one of these new blocks will be given to the user and the |
* other will be inserted into a free blocks structure |
* |
* The cost of this operation is |
* best case: (K) = (1) |
* worst case: (MAX_FL_LOG2_INDEX - MIN_FL_LOG2_INDEX + MAX_SL_INDEX + K) |
* = (1) |
* where K is an integer constant |
*/ |
|
static u8 *search_TAD (size_t size) { |
int for_free_block = 0; |
int fl, sl, n; |
int found; |
block_header_t *bh = NULL, *bh2; |
|
if (!(size > 0) || size >= MAX_SIZE || !all_ok) return NULL; |
THREAD_LOCK(); |
|
if (size <= MIN_SIZE) { |
size = MIN_SIZE; |
fl = 0; |
sl = 0; |
} else { |
mapping_function (size, &fl, &sl); |
|
if (++sl == MAX_SL_INDEX) { |
fl ++; |
sl = 0; |
} |
/* |
* This is the reason of the internal fragmentation |
* The block given is greater that the size demanded |
*/ |
size = (1 << (fl + MIN_LOG2_SIZE)); |
size = size + ((size >> MAX_SL_LOG2_INDEX) * sl); |
} |
|
/* the size given can be bigger than the size demanded */ |
found = 0; |
|
// we take the first free block from fl_array or a buddy of him |
|
sl = fl_array[fl].bitmapSL & ((~0) << sl); |
if (sl != 0) { |
sl = DIDMA_fls(sl); |
bh = fl_array [fl].sl_array [sl]; |
fl_array [fl].sl_array [sl] = bh -> ptr.free_ptr.next; |
if (fl_array [fl].sl_array [sl] != NULL) |
fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = NULL; |
else { |
DIDMA__clear_bit (sl, fl_array[fl].bitmapSL); |
if (!fl_array[fl].bitmapSL) { |
DIDMA__clear_bit (fl, bitmapFL); |
_free_ ((void *) fl_array [fl].sl_array); |
} |
} |
found = 1; |
goto out; |
} |
/* |
* if fl_array is empty we will take a free block |
* from free_block pointer |
*/ |
|
if (free_block != NULL && free_block -> size >= size) { |
bh = free_block; |
free_block = NULL; |
for_free_block = 1; |
found = 1; |
goto out; |
} |
|
/* |
* A free block is searched |
* |
* Using a bitmap |
*/ |
|
fl = DIDMA_fls(bitmapFL & ((~0) << (fl + 1))); |
|
if (fl > 0) { |
sl = DIDMA_fls(fl_array[fl].bitmapSL); |
bh = fl_array [fl].sl_array [sl]; |
fl_array [fl].sl_array [sl] = bh -> ptr.free_ptr.next; |
if (fl_array [fl].sl_array [sl] != NULL){ |
fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = NULL; |
} else { |
DIDMA__clear_bit (sl, fl_array[fl].bitmapSL); |
if (!fl_array[fl].bitmapSL) { |
_free_ ((void *) fl_array[fl].sl_array); |
DIDMA__clear_bit (fl, bitmapFL); |
} |
} |
found = 1; |
goto out; |
} |
|
out: |
|
/* |
* HUGGGG, NOT ENOUGHT MEMORY |
* I think that we have done all that we have been able |
*/ |
if (!found) { |
PRINT_MSG ("ERROR: Memory pool exhausted!!!\n"); |
THREAD_UNLOCK(); |
return NULL; |
} |
|
/* |
* we can say: YESSSSSSSSSSS, we have enought memory!!!! |
*/ |
bh -> state = BLOCK_USED; |
|
/* can bh be splitted? */ |
n = (int)(bh -> size - size - header_overhead); |
if (n >= (int) MIN_SIZE) { |
|
/* |
* Yes, bh will be splitted |
*/ |
|
bh2 = (block_header_t *) ((u8 *)(bh -> ptr.buffer) + size); |
bh2 -> magic_number = MAGIC_NUMBER; |
bh2 -> state = BLOCK_FREE; |
bh2 -> size = n; |
if (bh -> next != NULL) |
bh -> next -> prev = bh2; |
bh2 -> next = bh -> next; |
bh -> next = bh2; |
bh2 -> prev = bh; |
bh -> size = size; |
|
if (!for_free_block) { |
mapping_function (bh2 -> size, &fl, &sl); |
if (fl_array[fl].bitmapSL == 0) |
fl_array[fl].sl_array = (block_header_t **) _malloc_ (); |
if (fl_array[fl].sl_array == NULL) { |
PRINT_MSG("CRITICAL ERROR: there isn't enought memory for free\n"); |
return NULL; |
} |
bh2 -> ptr.free_ptr.first_l_index = fl; |
bh2 -> ptr.free_ptr.second_l_index = sl; |
bh2 -> ptr.free_ptr.prev = NULL; |
bh2 -> ptr.free_ptr.next = fl_array [fl].sl_array [sl]; |
|
if (fl_array [fl].sl_array [sl] != NULL) |
fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = bh2; |
fl_array [fl].sl_array [sl] = bh2; |
DIDMA__set_bit (sl, fl_array[fl].bitmapSL); |
DIDMA__set_bit (fl, bitmapFL); |
|
//fl_array [fl].n_blocks ++; |
} else |
free_block = bh2; |
} |
THREAD_UNLOCK(); |
return (u8 *) bh -> ptr.buffer; |
} |
|
|
int init_memory_pool (int max_size){ |
|
u8 *buffer; |
int real_max_size = 0; |
|
if (max_size < 0) return -1; |
|
|
//buffer = (u8 *) SYSTEM_MALLOC (real_max_size * sizeof (u8)); |
real_max_size = calculate_reserve(max_size); |
buffer = (u8 *) SYSTEM_MALLOC (real_max_size * sizeof (u8)); |
if (buffer == NULL) return F_ERROR; |
return init_TAD (real_max_size, buffer); |
} |
|
void destroy_memory_pool(void){ |
|
SYSTEM_FREE (destroy_TAD ()); |
} |
|
/* see 'man malloc' */ |
void *rt_malloc (size_t size){ |
return (void *) search_TAD (size); |
} |
|
/* see 'man free' */ |
void rt_free (void *ptr){ |
if (ptr != NULL) insert_TAD ((u8 *) ptr); |
} |
|
/* see 'man calloc' */ |
void *rt_calloc (size_t nelem, size_t elem_size) |
{ |
void *p; |
|
if (!all_ok || nelem <= 0 || elem_size <= 0) return NULL; |
|
if ((p = rt_malloc (nelem * elem_size)) == NULL) |
return NULL; |
|
memset (p, 0, nelem * elem_size); |
|
return p; |
} |
|
/* |
* see man realloc |
* be careful, realloc () is an expensive operation because |
* it uses malloc () and free () |
*/ |
void *rt_realloc (void *p, size_t new_len) |
{ |
u8 *aux; |
void *addr; |
int old_len, min; |
block_header_t *b; |
|
if (!all_ok) return NULL; |
|
if (p == NULL) |
return rt_malloc (new_len); |
else if (new_len == 0) { |
rt_free(p); |
return NULL; |
} else { |
/* |
* Now we try to achieve old size because |
* then we need it to copy all data in the new allocated |
* memory |
*/ |
aux = (u8 *) p; |
aux -= header_overhead; |
b = (block_header_t *) aux; |
if (b -> magic_number == MAGIC_NUMBER) { |
old_len = b -> size; |
} else { |
PRINT_MSG ("CRITICAL ERROR: block corrupted\n"); |
return NULL; |
} |
|
addr = rt_malloc (new_len); |
|
if (addr == NULL) return NULL; |
|
min = (old_len > new_len)? new_len : old_len; |
memcpy (addr, p, min); |
rt_free (p); |
|
return addr; |
} |
} |
|
#ifdef __DEBUG__ |
|
/* |
* dump_mem () is a simple operation, |
* it only does a dumped of memory |
*/ |
|
void dump_mem (void){ |
u8 *aux; |
int n; |
|
if (!all_ok) return; |
|
aux = (u8 *) first_bh; |
|
for (n = 0; n < total_size; n++) { |
PRINT_DBG_H (aux [n]); |
PRINT_DBG_C (" "); |
} |
PRINT_DBG_C ("\n"); |
} |
|
/* |
* I haven't anything to say about print_block () |
*/ |
static void print_block (block_header_t *b){ |
if (b == NULL) return; |
PRINT_DBG_C (">>>> MNum 0x"); |
PRINT_DBG_H (b -> magic_number); |
PRINT_DBG_C (" Address 0x"); |
//PRINT_DBG_H (b); |
if (b -> state == BLOCK_FREE) |
PRINT_DBG_C (" State FREE"); |
else |
PRINT_DBG_C (" State USED"); |
PRINT_DBG_C (" Size "); |
PRINT_DBG_D (b -> size); |
PRINT_DBG_C ("\n---- Prev 0x"); |
//PRINT_DBG_H (b -> prev); |
PRINT_DBG_C (" Next 0x"); |
//PRINT_DBG_H (b -> next); |
if (b -> state == BLOCK_FREE){ |
PRINT_DBG_C ("\n---- Prev Free 0x"); |
//PRINT_DBG_H (b -> ptr.free_ptr.prev); |
PRINT_DBG_C (" Next Free 0x"); |
//PRINT_DBG_H (b -> ptr.free_ptr.next); |
} |
PRINT_DBG_C ("\n"); |
} |
|
/* |
* structure_context () show the content of all blocks |
*/ |
void structure_context (void) { |
block_header_t *b; |
|
if (!all_ok) return; |
|
b = first_bh; |
PRINT_DBG_C ("\nALL BLOCKS\n"); |
while (b != NULL) { |
print_block (b); |
b = b -> next; |
} |
|
} |
|
/* |
* global_state () returns overhead, free and used space |
*/ |
void global_state (int *free, int *used, int *overhead){ |
block_header_t *b; |
|
*free = 0; |
*used = 0; |
*overhead = 0; |
if (!all_ok) return; |
b = first_bh; |
while (b != NULL) { |
if (b -> state == BLOCK_USED) { |
*used += b -> size; |
} else { |
*free += b -> size; |
} |
b = b -> next; |
*overhead += header_overhead; |
} |
|
} |
|
/* |
* free_blocks_context () show the content |
* of free blocks |
*/ |
void free_blocks_context (void){ |
int i, j; |
block_header_t *b; |
|
if (!all_ok) return; |
|
PRINT_DBG_C ("\nFREE BLOCKS\n"); |
PRINT_DBG_C ("MAIN BLOCK\n"); |
print_block (free_block); |
PRINT_DBG_C ("FRAGMENTED BLOCKS\n"); |
for (i = MAX_FL_INDEX - 1 - MIN_LOG2_SIZE; i >= 0; i--) { |
if (fl_array [i].bitmapSL > 0) |
for (j = MAX_SL_INDEX - 1; j >= 0; j--) { |
if (fl_array [i].sl_array[j] != NULL) { |
b = fl_array [i].sl_array [j]; |
PRINT_DBG_C ("["); |
PRINT_DBG_D (i); |
PRINT_DBG_C ("] "); |
PRINT_DBG_D (1 << (i + MIN_LOG2_SIZE)); |
PRINT_DBG_C (" bytes -> Free blocks: 0x"); |
PRINT_DBG_H (fl_array [i].bitmapSL); |
PRINT_DBG_C ("\n"); |
|
while (b != NULL) { |
PRINT_DBG_C (">>>> "); |
PRINT_DBG_D ((1 << (i + MIN_LOG2_SIZE)) + |
(1<< (i + MIN_LOG2_SIZE)) / MAX_SL_INDEX * j); |
PRINT_DBG_C (" bytes\n"); |
print_block (b); |
b = b -> ptr.free_ptr.next; |
} |
} |
} |
} |
} |
|
/* |
* check_mem () checks memory searching |
* errors and incoherences |
* return : |
* 0 if there isn't any error |
* or |
* -1 in other case |
*/ |
int check_mem (void){ |
block_header_t *b, *b2; |
int i, j, num_blocks; |
|
if (!all_ok) return F_ERROR; |
|
b = first_bh; |
num_blocks = 0; |
for (i = MAX_FL_INDEX - 1 - MIN_LOG2_SIZE; i >= 0; i--) { |
if (fl_array [i].bitmapSL < 0) return F_ERROR; |
for (j = MAX_SL_INDEX - 1; j >= 0; j--) { |
b2 = fl_array [i].sl_array[j]; |
while (b2 != NULL) { |
b2 = b2 -> ptr.free_ptr.next; |
num_blocks ++; |
} |
} |
if (num_blocks != fl_array [i].bitmapSL) return F_ERROR; |
num_blocks = 0; |
} |
|
while (b != NULL) { |
if (b -> magic_number != MAGIC_NUMBER || |
b -> size > MAX_SIZE || b -> size < MIN_SIZE) |
return F_ERROR; |
|
if (b -> next != NULL) |
if (b -> next < first_bh || b -> next > |
(block_header_t *) ((u8 *) (first_bh) + MAX_SIZE)) |
return F_ERROR; |
|
if (b -> prev != NULL) |
if (b -> prev < first_bh || b -> prev > |
(block_header_t *) ((u8 *) (first_bh) + MAX_SIZE) ) |
return F_ERROR; |
|
if (b -> state != BLOCK_FREE && b -> state != BLOCK_USED) return F_ERROR; |
if (b -> state == BLOCK_FREE) { |
if (b -> ptr.free_ptr.next != NULL) |
if (b -> ptr.free_ptr.next < first_bh || |
b -> ptr.free_ptr.next > |
(block_header_t *) ((u8 *) (first_bh) + MAX_SIZE)) |
return F_ERROR; |
|
if (b -> ptr.free_ptr.prev != NULL) |
if (b -> ptr.free_ptr.prev < first_bh || |
b -> ptr.free_ptr.prev > |
(block_header_t *) ((u8 *) (first_bh) + MAX_SIZE) ) |
return F_ERROR; |
} |
|
b = b -> next; |
|
} |
return F_OK; |
} |
#endif // #ifdef __DEBUG__ |