TABLE OF CONTENTS
- 1. mem_alloc/mem
- 1.1. mem/alloc_new_item
- 1.2. mem/array_inc_size
- 1.3. mem/array_init
- 1.4. mem/cell
- 1.5. mem/coalesce
- 1.6. mem/delete_item
- 1.7. mem/insert_item
- 1.8. mem/item_get_buddy
- 1.9. mem/mem_alloc
- 1.10. mem/mem_finalize
- 1.11. mem/mem_free
- 1.12. mem/mem_init
- 1.13. mem/split_item
- 1.14. mem/take_item
mem_alloc/mem [ Modules ]
NAME
mem - Generalized Fibonacci Memory Allocator
DESCRIPTION
A simple Fibonacci memory allocator. Uses blocks of size 8.
The sequence is 1, 2, 3, 4, 5, 7, 10, 14, 19, 26..., where
a(n) = a(n-1) + a(n-4).
Its functions are
* void mem_init() to initialize the allocator
* void *mem_alloc(unsigned int n) to initialize n bytes
* void mem_free(void *area) to free a previously allocated area
* void mem_finalize() to finalize the allocator
mem/alloc_new_item [ Functions ]
NAME
alloc_new_item - allocate a new item from the OS
SYNOPSIS
void *alloc_new_item(unsigned int n);
DESCRIPTION
The function alloc_new_item allocates a new item of n blocks. It also
allocates a fake empty buddy, so that it does not merge more than it
should. The fake right buddy is marked in use in order to stop the
merging of buddies.
The whole thing is prefixed by a pointer in order to make it a singly
linked list, mem_list, which is used to free all the elements
allocated from the OS.
The number passed in the n parameter is always a number belonging to
the generalized Fibonacci sequence.
RETURN VALUE
This function returns the address of new item allocated.
mem/array_inc_size [ Functions ]
NAME
array_set_size - increase the size of the array by one
SYNOPSIS
void array_inc_size(struct array *array, unsigned int new_size)
DESCRIPTION
The function array_inc_size increases the size of the array by 1.
Usually it only increases the size of the array->size variable, but
when the size reaches than the current capacity, a new array is
allocated, data is copied into it, and the old array is freed. Also a
new capacity is assigned. When a new size is set, it is made sure
that array->size is initialized. The array uses the functionality of
the allocator in order to allocate and free for the case when it needs
to copy itself into a new location.
RETURN VALUE
This function does not return anything.
mem/array_init [ Functions ]
NAME
array_init - initialize the array
SYNOPSIS
void array_init(struct array *array)
DESCRIPTION
This function is called during the initialization of the memory.
There is a limit of the minimum size that we allocate from the OS.
The initial array has to be at least this size. In the case of the
supported architectures this size is bigger than the minimal size that
can hold an array big enough so that it can be hold the array when the
array is freed. When the array needs to be resized, another space is
allocated and the array is copied there. The old area, that contained
the previous version of the array, is inserted into the array and can
be reused.
RETURN VALUE
This function does not return any value.
mem/cell [ Structures ]
[ Top ] [ mem ] [ Structures ]
NAME
struct cell - a cell of the array
DESCRIPTION
The items in the array are called cells, which have two fields: the
size and the pointer to the items. Each cell represents a free list
of the specified size. The cells are arranged in the order of the
generalized Fibonacci sequence. The items in one free list are all of
the same size.
mem/coalesce [ Functions ]
NAME
coalesce - merge buddies until an buddy in use is found.
DESCRIPTION
The coalesce function makes the opposite of splitting: it merges
buddies that are not in use, and stops when it finds a buddy which is
in use, which will happen sooner or later because the item at the top
had a fake right buddy which is marked in use.
SYNOPSIS
void coalesce(struct array *array, unsigned int);
RETURN VALUE
This function returns nothing.
mem/delete_item [ Functions ]
NAME
delete_item - delete an item from the free list at a specified index
SYNOPSIS
void delete_item(struct array *array, unsigned int i, void *item)
DESCRIPTION
The function delete_item deletes one item, which it finds by address,
from the free list specified by the index i in the array. It deletes
in two steps: first it finds the item, then it deletes it. The delete
operation is like a normal delete operation from a doubly linked list,
except that if it's the first item, then the entry in the array is
modified to point to the new head.
It is different from take_item, which removes any item from the free
list. The item deleted from the list can still be used (it is not
freed), and can be inserted back.
RETURN VALUE
Does not return anything
mem/insert_item [ Functions ]
NAME
insert_item - insert the item into the array
SYNOPSIS
void insert_item(struct array *array, unsigned int i, void *item)
DESCRIPTION
Inserts the item into the free list at i as the first element.
RETURN VALUE
This function returns nothing.
mem/item_get_buddy [ Functions ]
NAME
item_get_buddy - given an item, return its buddy
SYNOPSIS
void *item_get_buddy(struct array *array, void *item, unsigned int i,
unsigned int *ibuddy);
DESCRIPTION
Calculates the address of the buddy and returns it. It uses the fact
that the free list containing the size of the buddy is either 3 cells
to the left or 3 cells to the right, depending on whether the item is
is a left or the right buddy. Then, knowing the size, it's easy to
know the location of the buddy.
RETURN VALUE
The function retuens the address of the buddy. It also sets the
address pointed by ibuddy, which corresponds to the index in the array
where it would be inserted. That is, the index of the array that
gives the location of the free list of the same size as the buddy.
mem/mem_alloc [ Functions ]
NAME
mem_alloc - allocate an area block of a minumum number of bytes
SYNOPSIS
void *mem_alloc(unsigned int x)
DESCRIPTION
Allocates minimum x bytes.
First we check if the array contains an element that we can use in
order to hold x bytes.
If such element is found we remove it from
the array.
Otherwise we stretch the array if needed because the free lists in the
array have to follow the generalized Fibonacci sequence. So if we
need to allocate a very big item, we have to fill everything that
comes in between the end of the array and the place where the big item
will have to go. Then we can allocate the area from the OS. The rule
is to never allocate the same amount or less from the OS.
Once we have the item, we split it as much as needed. Then we set the
in_use bit of the item and return the area.
RETURN VALUE
An area of minimum x bytes.
mem/mem_finalize [ Functions ]
NAME
mem_finalize - return all memory used by the allocator to the OS
SYNOPSIS
void mem_finalize()
DESCRIPTION
The function mem_finalize is called by the user after having finished
using the memory allocator. This function goes through every item in
the mem_list and returns it to the Operating System by calling the
free function.
RETURN VALUE
Nothing is returned by this function.
mem/mem_free [ Functions ]
NAME
mem_free - put the item back into the free list
SYNOPSIS
void mem_free(void *area)
DESCRIPTION
Return the item after use to the free list. The first thing is to get
the item pointer from the address from the area. Using the header,
it's easy to find the size, and, having found the size, we have the
index which must match the size field of a free list in the array.
RETURN VALUE
Does not return anything.
mem/mem_init [ Functions ]
NAME
mem_init - initialize the memory
SYNOPSIS
void mem_init()
DESCRIPTION
This function needs to be called in order to use the memory allocator.
Its main duty is to initialize mem_list and the array. The global
variable mem_list contains a linked list of all of the memory chunks
that have been allocated by the Operating System, so that they can be
returned, not every OS guarantees that everything will be returned if
there are memory areas which are not freed.
RETURN VALUE
No value is returned.
mem/split_item [ Functions ]
NAME
split_item - split an item until of the requested size is created
SYNOPSIS
void* split_item(struct array *array, unsigned int i, void *item,
uintptr_t n)
DESCRIPTION
This function is given the number of blocks requested, an item, and
the index of the free list corresponding to its size in the array.
The purpose is to reduce the size of the item by splitting it into
two buddies and inserting one of them into the free list, until we
get an item as small as possible that can hold n blocks.
So, at each step we check if the item needs to be split. Then we
split it and determine if we want to use the left buddy or the right
buddy, and we continue the loop, which this time checks the buddy we
have chosen and so on. The buddy that is not used is inserted back
into the free list.
mem/take_item [ Functions ]
NAME
take_item - delete the first item from a free list and return it
SYNOPSIS
void *take_item(struct array *array, unsigned int i)
DESCRIPTION
Deletes the first item from the free list at index i in the array. It
should be checked before calling this function that there is at least
one item in the array cell, that is, array->data[i].items is not NULL.
RETURN VALUE
Returns the first item from the specified free list.