Reallocation algorithm

What makes this library different to others is its ability for memory re-allocation. This section explains how it works and how it achieves best performances and less memory fragmentation vs others.

Sometimes application uses variable length of memory, especially when number of (as an example) elements in not fully known in advance. For the sake of this example, application anticipates 12 numbers (integers) but may (due to unknown reason in some cases) receive more than this. If application needs to hold all received numbers, it may be necessary to:

  • Option 1: Increase memory block size using reallocations

  • Option 2: Use very big (do we know how big?) array, allocated statically or dynamically, which would hold all numbers at any time possible

Note

LwMEM has been optimized to handle well option 1.

Application needs to define at least single region:

Memory region assignment
 1#include "lwmem/lwmem.h"
 2
 3/* Define one region used by lwmem */
 4static unsigned char region_mem[128];
 5
 6/*
 7 * \brief           Define regions for memory manager
 8 */
 9static
10lwmem_region_t regions[] = {
11    /* Set start address and size of each region */
12    { region_mem, sizeof(region_mem) },
13    { NULL, 0 }
14};
15
16/* Later in the initialization process */
17/* Assign regions for manager */
18lwmem_assignmem(regions);
19lwmem_debug_free();     /* This is debug function for sake of this example */

When executed on test machine, it prints:

Memory region assignment output
B = Free block; A = Address of free block; S = Free size
Allocation available bytes:  120 bytes

B  0: A: 0x013CB160, S:    0, next B: 0x013CB520; Start block
B  1: A: 0x013CB520, S:  120, next B: 0x013CB598
B  2: A: 0x013CB598, S:    0, next B: 0x00000000; End of region

Note

Please check How it works section for more information

After region has been defined, application tries to allocate memory for 12 integers.

First memory allocation
 1int* ints = lwmem_malloc(12 * sizeof(*ints));  /* Allocate memory for 12 integers */
 2
 3/* Check for successful allocation */
 4if (ints == NULL) {
 5    printf("Allocation failed!\r\n");
 6    return -1;
 7}
 8lwmem_debug_free();     /* This is debug function for sake of this example */
 9
10/* ints is a pointer to memory size for our integers */
11/* Do not forget to free it when not used anymore */
12lwmem_free_s(&ints);

When executed on test machine, it prints:

First memory allocation output
B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   64 bytes

B  0: A: 0x013CB160, S:    0, next B: 0x013CB558; Start block
B  1: A: 0x013CB558, S:   64, next B: 0x013CB598
B  2: A: 0x013CB598, S:    0, next B: 0x00000000; End of region

At first, manager had 120 bytes of available memory while after allocation of 48 bytes, it only left 64 bytes. Effectively 120 - 64 = 56 bytes have been used to allocate 48 bytes of memory.

Note

Every allocated block holds meta data. On test machine, sizeof(int) = 4 therefore 8 bytes are used for metadata as 56 - 12 * sizeof(int) = 8. Size of meta data header depends on CPU architecture and may be different between architectures

Application got necessary memory for 12 integers. How to proceed when application needs to extend size for one more integer?

Easiest would be to:

  1. Allocate new memory block with new size and check if allocation was successful

  2. Manually copy content from old block to new block

  3. Free old memory block

  4. Use new block for all future operations

Here is the code:

Custom reallocation
 1int* ints = lwmem_malloc(12 * sizeof(*ints));  /* Allocate memory for 12 integers */
 2
 3/* Check for successful allocation */
 4if (ints == NULL) {
 5    printf("Allocation failed ints!\r\n");
 6    return -1;
 7}
 8printf("ints allocated for 12 integers\r\n");
 9lwmem_debug_free();     /* This is debug function for sake of this example */
10
11/* Now allocate new one for new size */
12int* ints2 = lwmem_malloc(13 * sizeof(*ints)); /* Allocate memory for 13 integers */
13if (ints2 == NULL) {
14    printf("Allocation failed ints2!\r\n");
15    return -1;
16}
17
18printf("ints2 allocated for 13 integers\r\n");
19lwmem_debug_free();     /* This is debug function for sake of this example */
20
21/* Copy content of 12-integers to 13-integers long array */
22memcpy(ints2, ints, 12 * sizeof(12));
23
24/* Free first block */
25lwmem_free(ints);       /* Free memory */
26ints = ints2;           /* Use ints2 as new array now */
27ints2 = NULL;           /* Set it to NULL to prevent accessing same memory from different pointers */
28
29printf("old ints freed\r\n");
30lwmem_debug_free();     /* This is debug function for sake of this example */
31
32/* Do not forget to free it when not used anymore */
33lwmem_free_s(&ints);
34
35printf("ints and ints2 freed\r\n");
36lwmem_debug_free();     /* This is debug function for sake of this example */

When executed on test machine, it prints:

Custom reallocation output
ints allocated for 12 integers

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   64 bytes

B  0: A: 0x00B5B160, S:    0, next B: 0x00B5B558; Start block
B  1: A: 0x00B5B558, S:   64, next B: 0x00B5B598
B  2: A: 0x00B5B598, S:    0, next B: 0x00000000; End of region

ints2 allocated for 13 integers

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:    0 bytes

B  0: A: 0x00B5B160, S:    0, next B: 0x00B5B598; Start block
B  1: A: 0x00B5B598, S:    0, next B: 0x00000000; End of region

old ints freed

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   56 bytes

B  0: A: 0x00B5B160, S:    0, next B: 0x00B5B520; Start block
B  1: A: 0x00B5B520, S:   56, next B: 0x00B5B598
B  2: A: 0x00B5B598, S:    0, next B: 0x00000000; End of region

ints and ints2 freed

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:  120 bytes

B  0: A: 0x00B5B160, S:    0, next B: 0x00B5B520; Start block
B  1: A: 0x00B5B520, S:  120, next B: 0x00B5B598
B  2: A: 0x00B5B598, S:    0, next B: 0x00000000; End of region

Outcome of the debug messages:

  1. Memory was successfully allocated for 12 integers, it took 56 bytes

  2. Memory was successfully allocated for another 13 integers , it took 64 bytes

  3. There is no more free memory available

  4. First 12 integers array was successfully freed, manager has 56 bytes of free memory

  5. Second 13 integers block was successfully freed, manager has all 120 bytes available for new allocations

This was therefore successful custom reallocation from 12 to 13 integers. Next step is to verify what would happen when application wants to reallocate to 15 integers instead. When same code is executed (but with 15 instead of 12), it prints:

Custom reallocation for 15 integers
ints allocated for 12 integers

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   64 bytes

B  0: A: 0x00D2B160, S:    0, next B: 0x00D2B558; Start block
B  1: A: 0x00D2B558, S:   64, next B: 0x00D2B598
B  2: A: 0x00D2B598, S:    0, next B: 0x00000000; End of region

Allocation failed ints2!

Oooops! It is not anymore possible to allocate new block for new 15 integers as there was no available block with at least 15 * sizeof(int) + metadata_size bytes of free memory.

Note

With this reallocation approach, maximal size of application block is only 50% of region size. This is not the most effective memory manager!

Fortunately there is a solution. Every time application wants to resize existing block, manager tries to manipulate existing block and shrink or expand it.

Shrink existing block

Easiest reallocation algorithm is when application wants to decrease size of previously allocated memory. When this is the case, manager only needs to change the size of existing block to lower value.

Shrink existing block to smaller size
 1int* ints, *ints2;
 2
 3ints = lwmem_malloc(15 * sizeof(*ints));  /* Allocate memory for 15 integers */
 4if (ints == NULL) {
 5    printf("Allocation failed ints!\r\n");
 6    return -1;
 7}
 8printf("ints allocated for 15 integers\r\n");
 9lwmem_debug_free();     /* This is debug function for sake of this example */
10
11/* Now reallocte ints and write result to new variable */
12ints2 = lwmem_realloc(ints, 12 * sizeof(*ints));
13if (ints == NULL) {
14    printf("Allocation failed ints2!\r\n");
15    return -1;
16}
17printf("ints re-allocated for 12 integers\r\n");
18lwmem_debug_free();     /* This is debug function for sake of this example */
19
20/* ints is successfully reallocated and it is no longer valid pointer to read/write from/to */
21
22/* For the sake of example, let's test pointers */
23if (ints2 == ints) {
24	printf("New block reallocated to the same address as previous one\r\n");
25} else {
26	printf("New block reallocated to new address\r\n");
27}
28
29/* Free ints2 */
30lwmem_free_s(&ints2);
31/* ints is already freed by successful realloc function */
32ints = NULL;            /* It is enough to set it to NULL */
33
34lwmem_debug_free();     /* This is debug function for sake of this example */

When executed on test machine, it prints:

Shrink existing block to smaller size output
ints allocated for 15 integers

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   52 bytes

B  0: A: 0x00B6B160, S:    0, next B: 0x00B6B564; Start block
B  1: A: 0x00B6B564, S:   52, next B: 0x00B6B598
B  2: A: 0x00B6B598, S:    0, next B: 0x00000000; End of region

ints re-allocated for 12 integers

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   64 bytes

B  0: A: 0x00B6B160, S:    0, next B: 0x00B6B558; Start block
B  1: A: 0x00B6B558, S:   64, next B: 0x00B6B598
B  2: A: 0x00B6B598, S:    0, next B: 0x00000000; End of region

New block reallocated to the same address as previous one

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:  120 bytes

B  0: A: 0x00B6B160, S:    0, next B: 0x00B6B520; Start block
B  1: A: 0x00B6B520, S:  120, next B: 0x00B6B598
B  2: A: 0x00B6B598, S:    0, next B: 0x00000000; End of region

Outcome of our reallocation:

  • Memory was successfully allocated for 15 integers, it took 68 bytes; part A on image

  • Memory was successfully re-allocated to 12 integers, now it takes 56 bytes, part B on image

  • In both cases on image, final returned memory points to the same address

    • Manager does not need to copy data from existing memory to new address as it is the same memory used in both cases

  • Empty block start address has been modified and its size has been increased, part B on image

  • Reallocated block was successfully freed, manager has all 120 bytes for new allocations

Tip

This was a success now, much better.

It is not always possible to increase block size of next free block on linked list. Consider new example and dedicated image below.

Shrinking fragmented memory block

Shrinking fragmented memory block

Shrink fragmented memory block
 1void* ptr1, *ptr2, *ptr3, *ptr4, *ptrt;
 2
 3/* We are now at case A */
 4printf("State at case A\r\n");
 5lwmem_debug_free();     /* This is debug function for sake of this example */
 6
 7/* Each ptr points to its own block of allocated data */
 8/* Each block size is 24 bytes; 16 for user data and 8 for metadata */
 9ptr1 = lwmem_malloc(16);
10ptr2 = lwmem_malloc(16);
11ptr3 = lwmem_malloc(16);
12ptr4 = lwmem_malloc(16);
13
14/* We are now at case B */
15printf("State at case B\r\n");
16lwmem_debug_free();     /* This is debug function for sake of this example */
17
18/* Reallocate ptr1, decrease its size to 12 user bytes */
19/* Now we expect block size to be 20; 12 for user data and 8 for metadata */
20ptrt = lwmem_realloc(ptr1, 12);
21if (ptrt == NULL) {
22    ptr1 = ptrt;
23}
24
25printf("State after first realloc\r\n");
26lwmem_debug_free();     /* This is debug function for sake of this example */
27
28/* At this point we are still at case B */
29/* There was no modification of internal structure */
30/* Difference between existing and new size (16 - 12 = 4) is too small
31    to create new empty block, therefore block it is left unchanged */
32
33/* Reallocate again, now to new size of 4 bytes */
34/* Now we expect block size to be 16; 8 for user data and 8 for metadata */
35ptrt = lwmem_realloc(ptr1, 8);
36printf("State at case C\r\n");
37lwmem_debug_free();     /* This is debug function for sake of this example */
38
39/* We are now at case C */
40
41/* Now free all memories */

When executed on test machine, it prints:

Shrink fragmented memory block output
State at case A

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:  120 bytes

B  0: A: 0x00E7B160, S:    0, next B: 0x00E7B520; Start block
B  1: A: 0x00E7B520, S:  120, next B: 0x00E7B598
B  2: A: 0x00E7B598, S:    0, next B: 0x00000000; End of region

State at case B

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   24 bytes

B  0: A: 0x00E7B160, S:    0, next B: 0x00E7B580; Start block
B  1: A: 0x00E7B580, S:   24, next B: 0x00E7B598
B  2: A: 0x00E7B598, S:    0, next B: 0x00000000; End of region

State after first realloc

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   24 bytes

B  0: A: 0x00E7B160, S:    0, next B: 0x00E7B580; Start block
B  1: A: 0x00E7B580, S:   24, next B: 0x00E7B598
B  2: A: 0x00E7B598, S:    0, next B: 0x00000000; End of region

State at case C

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   32 bytes

B  0: A: 0x00E7B160, S:    0, next B: 0x00E7B530; Start block
B  1: A: 0x00E7B530, S:    8, next B: 0x00E7B580
B  2: A: 0x00E7B580, S:   24, next B: 0x00E7B598
B  3: A: 0x00E7B598, S:    0, next B: 0x00000000; End of region

Outcome of this example:

  • Size of all 4 blocks is 24 bytes; 16 for user data, 8 for metadata

  • Reallocating block first time from 16 to 12 user data bytes did not affect internal memory structure

    • It is not possible to create new empty block as it would be too small, only 4 bytes available, minimum is 8 bytes for meta data

    • It is not possible to enlarge next empty block due to current and next empty do not create contiguous block

    • Block is internally left unchanged

  • Reallocating block second time to 8 bytes was a success

    • Difference between old and new size is 8 bytes which is enough for new empty block

      • Its size is 8 bytes, effectively 0 for user data due to meta size

Shrink existing block - summary

When reallocating already allocated memory block, one of 3 cases will happen:

  • Case 1: When current block and next free block could create contigouos block of memory, current block is decreased (size parameter) and next free is enlarged by the size difference

  • Case 2: When difference between current size and new size is more or equal to minimal size for new empty block, new empty block is created with size current_size - new_size and added to list of free blocks

  • Case 3: When difference between current size and new size is less than minimal size for new empty block, block is left unchanged

Enlarge existing block

Now that you master procedure to shrink (or decrease) size of existing allocated memory block, it is time to understand how to enlarge it. Things here are more complicated, however, they are still easy to understand.

Manager covers 3 potential cases:

  • Case 1: Increase size of currently allocated block

  • Case 2: Merge previous empty block with existing one and shift data up

  • Case 3: Block before and after existing block together create contiguous block of memory

Free block after + allocated block create one big contiguous block

*Free block* after + *allocated block* create one big contiguous block

Free block after + allocated block create one big contiguous block

Enlarge existing block
 1void* ptr1, *ptr2;
 2
 3/* Allocate initial block */
 4ptr1 = lwmem_malloc(24);
 5
 6/* We assume allocation is successful */
 7
 8printf("State at case 1a\r\n");
 9lwmem_debug_free();     /* This is debug function for sake of this example */
10
11/* Now let's reallocate ptr1 */
12ptr2 = lwmem_realloc(ptr1, 32);
13
14printf("State at case 1b\r\n");
15lwmem_debug_free();     /* This is debug function for sake of this example */

When executed on test machine, it prints:

Enlarge existing block output
State at case 1a

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   88 bytes

B  0: A: 0x00CBB160, S:    0, next B: 0x00CBB540; Start block
B  1: A: 0x00CBB540, S:   88, next B: 0x00CBB598
B  2: A: 0x00CBB598, S:    0, next B: 0x00000000; End of region

State at case 1b

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   80 bytes

B  0: A: 0x00CBB160, S:    0, next B: 0x00CBB548; Start block
B  1: A: 0x00CBB548, S:   80, next B: 0x00CBB598
B  2: A: 0x00CBB598, S:    0, next B: 0x00000000; End of region

  • Allocation for first block of memory (24 user bytes) uses 32 bytes of data

  • Reallocation is successful, block has been extended to 40 bytes and next free block has been shrinked down to 80 bytes

Free block before + allocated block create one big contiguous block

*Free block* before + *allocated block* create one big contiguous block

Free block before + allocated block create one big contiguous block

Enlarge existing block
 1void* ptr1, *ptr2;
 2
 3/* Allocate initial blocks */
 4ptr2 = lwmem_malloc(80);
 5ptr1 = lwmem_malloc(24);
 6lwmem_free_s(&ptr2);    /* Free first block and mark it free */
 7
 8/* We assume allocation is successful */
 9
10printf("State at case 2a\r\n");
11lwmem_debug_free();     /* This is debug function for sake of this example */
12
13/* Now let's reallocate ptr1 */
14ptr2 = lwmem_realloc(ptr1, 32);
15
16printf("State at case 2b\r\n");
17lwmem_debug_free();     /* This is debug function for sake of this example */

When executed on test machine, it prints:

Enlarge existing block output
State at case 2a

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   88 bytes

B  0: A: 0x0135B160, S:    0, next B: 0x0135B520; Start block
B  1: A: 0x0135B520, S:   88, next B: 0x0135B598
B  2: A: 0x0135B598, S:    0, next B: 0x00000000; End of region

State at case 2b

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   80 bytes

B  0: A: 0x0135B160, S:    0, next B: 0x0135B548; Start block
B  1: A: 0x0135B548, S:   80, next B: 0x0135B598
B  2: A: 0x0135B598, S:    0, next B: 0x00000000; End of region

  • First application allocates big block (88 bytes), followed by smaller block (32 bytes)

  • Application then frees big block to mark it as free. This is effectively state 2a

  • During reallocation, manager did not find suitable block after current block, but it found suitable block before current block:

    • Empty block and allocated block are temporary merged to one big block (120 bytes)

    • Content of allocated block is shifted up to beginning of new big block

    • Big block is then splitted to required size, the rest is marked as free

  • This is effectively state 2b

Free block before + free block after + allocated block create one big contiguous block

When application makes many allocations and frees of memory, there is a high risk of memory fragmentations. Essentially small chunks of allocated memory prevent manager to allocate new, fresh, big block of memory.

When it comes to reallocating of existing block, it may happen that first free block after and current block create a contiguous block, but its combined size is not big enough. Same could happen with last block before + current block. However, it may be possible to combine free block before + current block + free block after current block together.

*Free block* before + *free block* after + *allocated block* create one big contiguous block

Free block before + free block after + allocated block create one big contiguous block

In this example manager has always 2 allocated blocks and application always wants to reallocate green block. Red block is acting as an obstacle to show different application use cases.

Note

Image shows 4 use cases. For each of them, case labeled with 3 is initial state.

Initial state 3 is generated using C code:

Initial state of blocks within memory
 1void* ptr1, *ptr2, *ptr3, *ptr4;
 2
 3/* Allocate 4 blocks */
 4ptr1 = lwmem_malloc(8);
 5ptr2 = lwmem_malloc(4);
 6ptr3 = lwmem_malloc(4);
 7ptr4 = lwmem_malloc(16);
 8/* Free first and third block */
 9lwmem_free_s(&ptr1);
10lwmem_free_s(&ptr3);
11
12/* We assume allocation is successful */
13
14printf("Initial state at case 3\r\n");
15lwmem_debug_free();     /* This is debug function for sake of this example */

When executed on test machine, it prints:

Initial state of blocks within memory output
Initial state at case 3

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   84 bytes

B  0: A: 0x013BB160, S:    0, next B: 0x013BB520; Start block
B  1: A: 0x013BB520, S:   16, next B: 0x013BB53C
B  2: A: 0x013BB53C, S:   12, next B: 0x013BB560
B  3: A: 0x013BB560, S:   56, next B: 0x013BB598
B  4: A: 0x013BB598, S:    0, next B: 0x00000000; End of region

Tip

Image shows (and log confirms) 3 free slots of 16, 12 and 56 bytes in size respectively.

  • Case 3a: Application tries to reallocate green block from 12 to 16 bytes

    • Reallocation is successful, there is a free block just after and green block is successfully enlarged

    • Block after is shrinked from 12 to 8 bytes

    • Code example (follows initial state code example)

    Enlarge of existing block for case 3A
    1/* Now reallocate ptr2 */
2ptr2 = lwmem_realloc(ptr2, 8);
3
4printf("New state at case 3a\r\n");
5lwmem_debug_free();     /* This is debug function for sake of this example */

    • When executed on test machine, it prints:

    Enlarge of existing block for case 3A output
    New state at case 3a

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   80 bytes

B  0: A: 0x0133B160, S:    0, next B: 0x0133B5C0; Start block
B  1: A: 0x0133B5C0, S:   16, next B: 0x0133B5E0
B  2: A: 0x0133B5E0, S:    8, next B: 0x0133B600
B  3: A: 0x0133B600, S:   56, next B: 0x0133B638
B  4: A: 0x0133B638, S:    0, next B: 0x00000000; End of region

  • Case 3b: Application tries to reallocate green block from 12 to 28 bytes

    • Block after green is not big enough to merge them to one block (12 + 12 < 28)

    • Block before green is big enough (16 + 12 >= 28)

    • Green block is merged with previous free block and content is shifted to the beginning of new block

    Enlarge of existing block for case 3B
    1/* Now reallocate ptr2 */
2ptr2 = lwmem_realloc(ptr2, 20);
3
4printf("New state at case 3b\r\n");
5lwmem_debug_free();     /* This is debug function for sake of this example */

    • When executed on test machine, it prints:

    Enlarge of existing block for case 3B output
    New state at case 3b

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   68 bytes

B  0: A: 0x0103B160, S:    0, next B: 0x0103B53C; Start block
B  1: A: 0x0103B53C, S:   12, next B: 0x0103B560
B  2: A: 0x0103B560, S:   56, next B: 0x0103B598
B  3: A: 0x0103B598, S:    0, next B: 0x00000000; End of region

  • Case 3c: Application tries to reallocate green block from 12 to 32 bytes

    • Block after green is not big enough to merge them to one block (12 + 12 < 32)

    • Block before green is also not big enough (12 + 16 < 32)

    • All three blocks together are big enough (16 + 12 + 12 >= 32)

    • All blocks are effectively merged together and there is a new temporary block with its size set to 40 bytes

    • Content of green block is shifted to the beginning of new block

    • New block is limited to 32 bytes, keeping 8 bytes marked as free at the end

    Enlarge of existing block for case 3C
    1/* Now reallocate ptr2 */
2ptr2 = lwmem_realloc(ptr2, 24);
3
4printf("New state at case 3c\r\n");
5lwmem_debug_free();     /* This is debug function for sake of this example */

    • When executed on test machine, it prints:

    Enlarge of existing block for case 3C output
    New state at case 3c

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   64 bytes

B  0: A: 0x011AB160, S:    0, next B: 0x011AB540; Start block
B  1: A: 0x011AB540, S:    8, next B: 0x011AB560
B  2: A: 0x011AB560, S:   56, next B: 0x011AB598
B  3: A: 0x011AB598, S:    0, next B: 0x00000000; End of region

  • Case 3d: Application tries to reallocate green block from 12 to 44 bytes

    • None of the methods (3a - 3c) are available as blocks are too small

    • Completely new block is created and content is copied to it

    • Existing block is marked as free. All 3 free blocks create big contiguous block, they are merged to one block with its size set to 40

    Enlarge of existing block for case 3D
    1/* Now reallocate ptr2 */
2ptr2 = lwmem_realloc(ptr2, 36);
3
4printf("New state at case 3d\r\n");
5lwmem_debug_free();     /* This is debug function for sake of this example */

    • When executed on test machine, it prints:

    Enlarge of existing block for case 3D output
    New state at case 3d

B = Free block; A = Address of free block; S = Free size
Allocation available bytes:   52 bytes

B  0: A: 0x002EB160, S:    0, next B: 0x002EB520; Start block
B  1: A: 0x002EB520, S:   40, next B: 0x002EB58C
B  2: A: 0x002EB58C, S:   12, next B: 0x002EB598
B  3: A: 0x002EB598, S:    0, next B: 0x00000000; End of region

Full test code with assert

Advanced debugging features have been added for development purposes. It is now possible to simulate different cases within single executable, by storing states to different memories.

Example has been implemented for WIN32 and relies on dynamic allocation using malloc standard C function for main block data preparation.

How it works:

  • Code prepares state 3 and saves memory to temporary memory for future restore

  • Code restores latest saved state (case 3) and executes case 3a

  • Code restores latest saved state (case 3) and executes case 3b

  • Code restores latest saved state (case 3) and executes case 3c

  • Code restores latest saved state (case 3) and executes case 3d

Initial state 3 is generated using C code:

Full test code with asserts
 1#define ASSERT(x)           do {        \
 2    if (!(x)) {                         \
 3        printf("Assert failed with condition (" # x ")\r\n");  \
 4    } else {\
 5        printf("Assert passed with condition (" # x ")\r\n");  \
 6    }\
 7} while (0) 
 8
 9/* For debug purposes */
10lwmem_region_t* regions_used;
11size_t regions_count = 1;       /* Use only 1 region for debug purposes of non-free areas */
12
13int
14main(void) {
15    uint8_t* ptr1, *ptr2, *ptr3, *ptr4;
16    uint8_t* rptr1, *rptr2, *rptr3, *rptr4;
17
18    /* Create regions for debug purpose */
19    if (!lwmem_debug_create_regions(&regions_used, regions_count, 128)) {
20        printf("Cannot allocate memory for regions for debug purpose!\r\n");
21        return -1;
22    }
23    lwmem_assignmem(regions_used);
24    printf("Manager is ready!\r\n");
25    lwmem_debug_print(1, 1);
26
27    /* Test case 1, allocate 3 blocks, each of different size */
28    /* We know that sizeof internal metadata block is 8 bytes on win32 */
29    printf("\r\n\r\nAllocating 4 pointers and freeing first and third..\r\n");
30    ptr1 = lwmem_malloc(8);
31    ptr2 = lwmem_malloc(4);
32    ptr3 = lwmem_malloc(4);
33    ptr4 = lwmem_malloc(16);
34    lwmem_free(ptr1);               /* Free but keep value for future comparison */
35    lwmem_free(ptr3);               /* Free but keep value for future comparison */
36    lwmem_debug_print(1, 1);
37    printf("Debug above is effectively state 3\r\n");
38    lwmem_debug_save_state();       /* Every restore operations rewinds here */
39
40    /* We always try to reallocate pointer ptr2 */
41
42    /* Create 3a case */
43    printf("\r\n------------------------------------------------------------------------\r\n");
44    lwmem_debug_restore_to_saved();
45    printf("State 3a\r\n");
46    rptr1 = lwmem_realloc(ptr2, 8);
47    lwmem_debug_print(1, 1);
48    ASSERT(rptr1 == ptr2);
49
50    /* Create 3b case */
51    printf("\r\n------------------------------------------------------------------------\r\n");
52    lwmem_debug_restore_to_saved();
53    printf("State 3b\r\n");
54    rptr2 = lwmem_realloc(ptr2, 20);
55    lwmem_debug_print(1, 1);
56    ASSERT(rptr2 == ptr2);
57
58    /* Create 3c case */
59    printf("\r\n------------------------------------------------------------------------\r\n");
60    lwmem_debug_restore_to_saved();
61    printf("State 3c\r\n");
62    rptr3 = lwmem_realloc(ptr2, 24);
63    lwmem_debug_print(1, 1);
64    ASSERT(rptr3 == ptr1);
65
66    /* Create 3d case */
67    printf("\r\n------------------------------------------------------------------------\r\n");
68    lwmem_debug_restore_to_saved();
69    printf("State 3d\r\n");
70    rptr4 = lwmem_realloc(ptr2, 36);
71    lwmem_debug_print(1, 1);
72    ASSERT(rptr4 != ptr1 && rptr4 != ptr2 && rptr4 != ptr3 && rptr4 != ptr4);
73
74    return 0;
75}

When executed on test machine, it prints:

Full test code with asserts output
Manager is ready!
|-------|----------|--------|------|------------------|----------------|
| Block | Address  | IsFree | Size | MaxUserAllocSize | Meta           |
|-------|----------|--------|------|------------------|----------------|
|     0 | 00179154 |      0 |    0 |                0 |Start block     |
|     1 | 0034A508 |      1 |  120 |              112 |Free block      |
|     2 | 0034A580 |      0 |    0 |                0 |End of region   |
|-------|----------|--------|------|------------------|----------------|


Allocating 4 pointers and freeing first and third..
|-------|----------|--------|------|------------------|----------------|
| Block | Address  | IsFree | Size | MaxUserAllocSize | Meta           |
|-------|----------|--------|------|------------------|----------------|
|     0 | 00179154 |      0 |    0 |                0 |Start block     |
|     1 | 0034A508 |      1 |   16 |                8 |Free block      |
|     2 | 0034A518 |      0 |   12 |                0 |Allocated block |
|     3 | 0034A524 |      1 |   12 |                4 |Free block      |
|     4 | 0034A530 |      0 |   24 |                0 |Allocated block |
|     5 | 0034A548 |      1 |   56 |               48 |Free block      |
|     6 | 0034A580 |      0 |    0 |                0 |End of region   |
|-------|----------|--------|------|------------------|----------------|
Debug above is effectively state 3
 -- > Current state saved!

------------------------------------------------------------------------
 -- > State restored to last saved!
State 3a
|-------|----------|--------|------|------------------|----------------|
| Block | Address  | IsFree | Size | MaxUserAllocSize | Meta           |
|-------|----------|--------|------|------------------|----------------|
|     0 | 00179154 |      0 |    0 |                0 |Start block     |
|     1 | 0034A508 |      1 |   16 |                8 |Free block      |
|     2 | 0034A518 |      0 |   16 |                0 |Allocated block |
|     3 | 0034A528 |      1 |    8 |                0 |Free block      |
|     4 | 0034A530 |      0 |   24 |                0 |Allocated block |
|     5 | 0034A548 |      1 |   56 |               48 |Free block      |
|     6 | 0034A580 |      0 |    0 |                0 |End of region   |
|-------|----------|--------|------|------------------|----------------|
Assert passed with condition (rptr1 == ptr2)

------------------------------------------------------------------------
 -- > State restored to last saved!
State 3b
|-------|----------|--------|------|------------------|----------------|
| Block | Address  | IsFree | Size | MaxUserAllocSize | Meta           |
|-------|----------|--------|------|------------------|----------------|
|     0 | 00179154 |      0 |    0 |                0 |Start block     |
|     1 | 0034A508 |      0 |   28 |                0 |Allocated block |
|     2 | 0034A524 |      1 |   12 |                4 |Free block      |
|     3 | 0034A530 |      0 |   24 |                0 |Allocated block |
|     4 | 0034A548 |      1 |   56 |               48 |Free block      |
|     5 | 0034A580 |      0 |    0 |                0 |End of region   |
|-------|----------|--------|------|------------------|----------------|
Assert failed with condition (rptr2 == ptr2)

------------------------------------------------------------------------
 -- > State restored to last saved!
State 3c
|-------|----------|--------|------|------------------|----------------|
| Block | Address  | IsFree | Size | MaxUserAllocSize | Meta           |
|-------|----------|--------|------|------------------|----------------|
|     0 | 00179154 |      0 |    0 |                0 |Start block     |
|     1 | 0034A508 |      0 |   32 |                0 |Allocated block |
|     2 | 0034A528 |      1 |    8 |                0 |Free block      |
|     3 | 0034A530 |      0 |   24 |                0 |Allocated block |
|     4 | 0034A548 |      1 |   56 |               48 |Free block      |
|     5 | 0034A580 |      0 |    0 |                0 |End of region   |
|-------|----------|--------|------|------------------|----------------|
Assert passed with condition (rptr3 == ptr1)

------------------------------------------------------------------------
 -- > State restored to last saved!
State 3d
|-------|----------|--------|------|------------------|----------------|
| Block | Address  | IsFree | Size | MaxUserAllocSize | Meta           |
|-------|----------|--------|------|------------------|----------------|
|     0 | 00179154 |      0 |    0 |                0 |Start block     |
|     1 | 0034A508 |      1 |   40 |               32 |Free block      |
|     2 | 0034A530 |      0 |   24 |                0 |Allocated block |
|     3 | 0034A548 |      0 |   44 |                0 |Allocated block |
|     4 | 0034A574 |      1 |   12 |                4 |Free block      |
|     5 | 0034A580 |      0 |    0 |                0 |End of region   |
|-------|----------|--------|------|------------------|----------------|
Assert passed with condition (rptr4 != ptr1 && rptr4 != ptr2 && rptr4 != ptr3 && rptr4 != ptr4)