#include "examples_common.h"

Classes
struct	malloc_example_opts_st_
struct	memblock_obj_st_
struct	malloc_example_input_st_
struct	memblock_ctx_st_
Typedefs
typedef enum malloc_pattern_e_	malloc_pattern_e
typedef struct malloc_example_opts_st_	malloc_example_opts_st
typedef struct memblock_obj_st_	memblock_obj_st
typedef struct malloc_example_input_st_	malloc_example_input_st
typedef struct memblock_ctx_st_	memblock_ctx_st
typedef enum malloc_example_key_e_	malloc_example_key_e
Enumerations
enum	malloc_pattern_e_ { MALLOC_PATTERN_E_LINEAR, MALLOC_PATTERN_E_UNIFORM, MALLOC_PATTERN_E_MAX }
enum	malloc_example_key_e_ { MALLOC_EXAMPLE_KEY_E_ADDR, MALLOC_EXAMPLE_KEY_E_SIZE, MALLOC_EXAMPLE_KEY_E_MAX }
Functions
static void	print_usage (bool do_exit, int32_t exit_val)
static void	print_opts (malloc_example_opts_st *opts)
static void	parse_command_line (int argc, char *argv, malloc_example_opts_st opts)
static int32_t	memblock_cmp_by_addr (const void item1, const void item2, void *context)
static int32_t	memblock_cmp_by_size (const void item1, const void item2, void *context)
static mkavl_rc_e	free_memblock (void item, void context)
static void	display_memory (mkavl_tree_handle tree_h, void *start_addr, size_t bytes)
static bool	generate_memblock (memblock_obj_st *obj, void start_addr, size_t byte_cnt)
static void *	my_malloc (mkavl_tree_handle tree_h, size_t size)
static void	my_free (mkavl_tree_handle tree_h, void *ptr)
static void	run_malloc_example (malloc_example_input_st *input)
int	main (int argc, char *argv[])
Variables
static const size_t	malloc_sizes [] = { 4, 8, 512, 4096 }
static const uint32_t	default_malloc_cnt = 100
static uint32_t	default_memory_size
static const uint32_t	default_run_cnt = 1
static const uint8_t	default_verbosity = 0
static void *	base_addr = (void *) 0x1234ABCD
static size_t	max_memory_size
static mkavl_compare_fn	cmp_fn_array []

Detailed Description

Author:: Matt Miller <matt@matthewjmiller.net>

LICENSE

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.

DESCRIPTION

This is a basic example of how the mkavl library can be used for memory management. The free and allocated memory blocks are maintained in a single mvavl DB. The DB is indexed by the starting address of the memory block as one key and the other key consists of the allocation status (i.e., free or allocated), block size, and starting address.

On a malloc() call, we look up the free block with the size greater than or equal to the requested size. This is a O(lg N) best-fit algorithm. On a free() call, we change the state of the freed block from allocated to free. We then check whether the adjacent memory blocks are also free and, if so, consolidate the blocks into one.

The example run will:

Allocate 100 pointers
Free up to half of them.
Re-allocate the ones just freed.
Free all the pointers.

At each step, we print out a graphical display of the curent memory state. The step where up to half are freed is done by chosing points uniformly at random by default. A command line option allows you to instead free the first half of the pointers deterministically.

Of course, this is just an example so we use malloc to generate the AVL items placed in the tree. In reality, a more complicated scheme would be implemented to grab memory for the purpose so malloc isn't being called to implement malloc.

    Example of using mkavl for an memory allocation

    Usage:
    -s <seed>
       The starting seed for the RNG (default=seeded by time()).
    -b <memory size in bytes>
       The number of bytes in memory (default=409600).
    -n <number of allocations>
       The max number of allocations at any one time (default=100).
    -r <runs>
       The number of runs to do (default=1).
    -l
       Free/re-allocate linearly (default=uniform distribution).
    -v <verbosity level>
       A higher number gives more output (default=0).
    -h
       Display this help message.

Definition in file malloc_example.c.

Typedef Documentation

typedef struct malloc_example_input_st_ malloc_example_input_st

The input structure to pass test parameters to functions.

typedef enum malloc_example_key_e_ malloc_example_key_e

The values for the key ordering.

typedef struct malloc_example_opts_st_ malloc_example_opts_st

State for the current test execution.

typedef enum malloc_pattern_e_ malloc_pattern_e

Patterns for how memory gets freed and re-allocated.

typedef struct memblock_ctx_st_ memblock_ctx_st

The context associated with the memblock AVLs.

typedef struct memblock_obj_st_ memblock_obj_st

The data for a free/allocated memory block.

Enumeration Type Documentation

enum malloc_example_key_e_

The values for the key ordering.

Enumerator:

MALLOC_EXAMPLE_KEY_E_ADDR	Ordered by address
MALLOC_EXAMPLE_KEY_E_SIZE	Ordered by allocation status + size + address
MALLOC_EXAMPLE_KEY_E_MAX	Max value for boundary testing

Definition at line 372 of file malloc_example.c.

enum malloc_pattern_e_

Patterns for how memory gets freed and re-allocated.

Enumerator:

MALLOC_PATTERN_E_LINEAR	Free and re-allocate the first N memory locations
MALLOC_PATTERN_E_UNIFORM	Free and re-allocated the memory in locations chosen from a uniform distribution.
MALLOC_PATTERN_E_MAX	Max value for boundary checking

Definition at line 93 of file malloc_example.c.

Function Documentation

static void display_memory	(	mkavl_tree_handle	tree_h,
		void *	start_addr,
		size_t	bytes
	)		`[static]`

Display memory in the given range.

Parameters:

tree_h	The memory block trees.
start_addr	The start address of the range.
bytes	The number of bytes to display.

Definition at line 418 of file malloc_example.c.

static mkavl_rc_e free_memblock	(	void *	item,
		void *	context
	)		`[static]`

Callback to free the given memory block object.

Parameters:

item	The pointer to the object.
context	Context for the tree.

Returns:: The return code

Definition at line 399 of file malloc_example.c.

static bool generate_memblock	(	memblock_obj_st **	obj,
		void *	start_addr,
		size_t	byte_cnt
	)		`[static]`

Allocate and fill in the data for a memory block object. By default, the object is set to not allocated.

Obviously in a real implementation, malloc() wouldn't be used to implement malloc. You'd need to slice up the memory available yourself.

Parameters:

obj	A pointer to fill in with the newly allocated object.
start_addr	The start address for the block.
byte_cnt	The byte count for the block.

Returns:: true if the creation was successful.

Definition at line 471 of file malloc_example.c.

int main	(	int	argc,
		char *	argv[]
	)

Main function to test objects.

Definition at line 739 of file malloc_example.c.

static int32_t memblock_cmp_by_addr	(	const void *	item1,
		const void *	item2,
		void *	context
	)		`[static]`

Compare memory blocks by address.

Parameters:

item1	Item to compare
item2	Item to compare
context	Context for the tree

Returns:: Comparison result

Definition at line 309 of file malloc_example.c.

static int32_t memblock_cmp_by_size	(	const void *	item1,
		const void *	item2,
		void *	context
	)		`[static]`

Compare memory blocks by allocated status, size, and address.

Parameters:

item1	Item to compare
item2	Item to compare
context	Context for the tree

Returns:: Comparison result

Definition at line 336 of file malloc_example.c.

static void my_free	(	mkavl_tree_handle	tree_h,
		void *	ptr
	)		`[static]`

Mark the memory as unallocated and merge with adjacent unallocated blocks.

Parameters:

tree_h	The tree of memory blocks.
ptr	The pointer to free.

Definition at line 571 of file malloc_example.c.

static void* my_malloc	(	mkavl_tree_handle	tree_h,
		size_t	size
	)		`[static]`

This is a best-fit version that will find the first unallocated memory block large enough to hold the request.

Parameters:

tree_h	The tree of memory blocks.
size	The size of memory to allocate.

Returns:: A pointer to the memory of NULL if the allocation failed.

Definition at line 504 of file malloc_example.c.

static void parse_command_line	(	int	argc,
		char **	argv,
		malloc_example_opts_st *	opts
	)		`[static]`

Store the command line options into a local structure.

Parameters:

argc	The number of options
argv	The string for the options.
opts	The local structure in which to store the parsed info.

Definition at line 219 of file malloc_example.c.

static void print_opts ( malloc_example_opts_st * opts ) [static]

Utility function to output the value of the options.

Parameters:

opts	The options to output.

Definition at line 198 of file malloc_example.c.

static void print_usage	(	bool	do_exit,
		int32_t	exit_val
	)		`[static]`

Display the program's help screen and exit as needed.

Parameters:

do_exit	Whether to exit after the output.
exit_val	If exiting the value with which to exit.

Definition at line 163 of file malloc_example.c.

static void run_malloc_example ( malloc_example_input_st * input ) [static]

Run a single instance of an example.

Parameters:

input The input parameters for the run.

Definition at line 646 of file malloc_example.c.

Variable Documentation

void* base_addr = (void *) 0x1234ABCD [static]

The address to use as the base of the memory

Definition at line 86 of file malloc_example.c.

mkavl_compare_fn cmp_fn_array[] [static]

Initial value:

 { 
    memblock_cmp_by_addr, 
    memblock_cmp_by_size 
}

The comparison functions to use

Definition at line 382 of file malloc_example.c.

const uint32_t default_malloc_cnt = 100 [static]

The default number of items to allocated at any one time

Definition at line 77 of file malloc_example.c.

uint32_t default_memory_size [static]

The default memory size

Definition at line 79 of file malloc_example.c.

const uint32_t default_run_cnt = 1 [static]

The default number of test runs

Definition at line 81 of file malloc_example.c.

const uint8_t default_verbosity = 0 [static]

The default verbosity level of messages displayed

Definition at line 83 of file malloc_example.c.

const size_t malloc_sizes[] = { 4, 8, 512, 4096 } [static]

List of sizes for memory allocations

Definition at line 74 of file malloc_example.c.

size_t max_memory_size [static]

Maximum size of the memory

Definition at line 88 of file malloc_example.c.

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

LICENSE

DESCRIPTION

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation