Classes | Typedefs | Enumerations | Functions | Variables
examples/malloc_example.c File Reference
#include "examples_common.h"

Go to the source code of this file.


struct  malloc_example_opts_st_
struct  memblock_obj_st_
struct  malloc_example_input_st_
struct  memblock_ctx_st_


typedef enum malloc_pattern_e_ malloc_pattern_e
typedef struct
typedef struct memblock_obj_st_ memblock_obj_st
typedef struct
typedef struct memblock_ctx_st_ memblock_ctx_st
typedef enum malloc_example_key_e_ malloc_example_key_e




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[])


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

Matt Miller <>


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 <>.


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:

  1. Allocate 100 pointers
  2. Free up to half of them.
  3. Re-allocate the ones just freed.
  4. 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

    -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).
       Free/re-allocate linearly (default=uniform distribution).
    -v <verbosity level>
       A higher number gives more output (default=0).
       Display this help message.

Definition in file malloc_example.c.

Typedef Documentation

The input structure to pass test parameters to functions.

The values for the key ordering.

State for the current test execution.

Patterns for how memory gets freed and re-allocated.

The context associated with the memblock AVLs.

The data for a free/allocated memory block.

Enumeration Type Documentation

The values for the key ordering.


Ordered by address


Ordered by allocation status + size + address


Max value for boundary testing

Definition at line 372 of file malloc_example.c.

Patterns for how memory gets freed and re-allocated.


Free and re-allocate the first N memory locations


Free and re-allocated the memory in locations chosen from a uniform distribution.


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.

tree_hThe memory block trees.
start_addrThe start address of the range.
bytesThe 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.

itemThe pointer to the object.
contextContext for the tree.
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.

objA pointer to fill in with the newly allocated object.
start_addrThe start address for the block.
byte_cntThe byte count for the block.
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.

item1Item to compare
item2Item to compare
contextContext for the tree
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.

item1Item to compare
item2Item to compare
contextContext for the tree
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.

tree_hThe tree of memory blocks.
ptrThe 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.

tree_hThe tree of memory blocks.
sizeThe size of memory to allocate.
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.

argcThe number of options
argvThe string for the options.
optsThe 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.

optsThe 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.

do_exitWhether to exit after the output.
exit_valIf 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.

inputThe 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.

Initial value:

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.

 All Classes Files Functions Variables Typedefs Enumerations Enumerator Defines