fixed_lists_mem_t Class Reference

#include <mem_mgmt.h>

Classes
class	list_header_t
struct	slot_t

Public Member Functions
	fixed_lists_mem_t (size_t bufsize=8192 *10240, size_t incr=32, size_t max=16384)
	~fixed_lists_mem_t ()
rc_t	allocate (size_t length, slot_t &slot)
rc_t	free (slot_t slot)
rc_t	defrag ()

Private Member Functions
void	add_to_list (size_t block_size, char *address)
char *	remove_from_list (size_t block_size)
void	remove_from_list (list_header_t *p)
bool	is_list_empty (size_t block_size)

Private Attributes
const size_t	_incr
const size_t	_max
size_t	_bufsize
list_header_t **	_lists
char *	_buf
size_t	_first_non_empty
size_t	_last_non_empty
size_t	_alloc
size_t	_used

Detailed Description

Memory management algorithm as proposed in:

P. Larson: External sorting: run formation revisited IEEE Transactions on Knowledge and Data Engineering (Volume:15 , Issue: 4 )

Memory blocks have fixed lengths ranging from a minimum to a maximum size in fixed increments, for example from 32 to 8192 bytes. Free blocks are managed in linked lists, one for each block size. The metadata of each block, such as the prev/next pointers (valid only if free) and the block size, are stored within the block itself (see list_header_t).

Coalescence of free blocks is implemented by using boundary tags, as suggested in the paper. While it adds more complexity to the algorithm, we have found it essential to maintain a robust behavior in terms of usable space over time.

Author

: Caetano Sauer

Constructor & Destructor Documentation

fixed_lists_mem_t()

fixed_lists_mem_t::fixed_lists_mem_t	(	size_t	bufsize = 8192 * 10240,
		size_t	incr = 32,
		size_t	max = 16384
	)

Initialize the buffer with all blocks of the maximum size

~fixed_lists_mem_t()

fixed_lists_mem_t::~fixed_lists_mem_t

(

)

Member Function Documentation

add_to_list()

void fixed_lists_mem_t::add_to_list ( size_t  block_size, char *  address  )

private

Adds a new free block (located at 'address') to the list of blocks with 'block_size'.

allocate()

rc_t fixed_lists_mem_t::allocate	(	size_t	length,
		slot_t &	slot
	)

Allocate space for a record/object of size 'length'. The address and the actual block size are returned in 'slot'. If the slot is larger than the best fit (i.e., the smallest block size larger than 'length'), the block is split into one with size equal to the best fit, and the remaining part is readded to the lists as a smaller free block.

If there is no block available with the requested size, the method returns an invalid slot (containing a null pointer). The calles should then attempt to free more blocks before trying again.

defrag()

rc_t fixed_lists_mem_t::defrag

(

)

WARNING: This defrag method assumes that all blocks were freed beforehand (e.g. the overlying heap is empty)

free()

rc_t fixed_lists_mem_t::free

(

slot_t

slot

)

is_list_empty()

bool fixed_lists_mem_t::is_list_empty ( size_t  block_size )

inlineprivate

remove_from_list() [1/2]

char * fixed_lists_mem_t::remove_from_list ( size_t  block_size )

private

Removes a block of a given size from its linked list. Here we do not care which block is returned, since the method is invoked inside the allocation method. Thus, the list head is always removed, allowing allocation to happen in constant time.

remove_from_list() [2/2]

void fixed_lists_mem_t::remove_from_list ( list_header_t *  p )

private

Removes a free block from the middle of a linked lists. This version of the method is used by block coalescence, which transforms 2 or 3 free blocks into one of larger size. This requires removing the smaller blocks from their free lists using this method.

Member Data Documentation

_alloc

size_t fixed_lists_mem_t::_alloc

private

_buf

char* fixed_lists_mem_t::_buf

private

_bufsize

size_t fixed_lists_mem_t::_bufsize

private

_first_non_empty

size_t fixed_lists_mem_t::_first_non_empty

private

_incr

const size_t fixed_lists_mem_t::_incr

private

_last_non_empty

size_t fixed_lists_mem_t::_last_non_empty

private

_lists

list_header_t** fixed_lists_mem_t::_lists

private

_max

const size_t fixed_lists_mem_t::_max

private

_used

size_t fixed_lists_mem_t::_used

private

---

The documentation for this class was generated from the following files:

• src/sm/mem_mgmt.h
• src/sm/mem_mgmt.cpp