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 reallocationsOption
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:
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:
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
.
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:
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:
Allocate new memory block with new size and check if allocation was successful
Manually copy content from old block to new block
Free old memory block
Use new block for all future operations
Here is the code:
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:
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:
Memory was successfully allocated for
12
integers, it took56
bytesMemory was successfully allocated for another
13
integers , it took64
bytesThere is no more free memory available
First
12
integers array was successfully freed, manager has56
bytes of free memorySecond
13
integers block was successfully freed, manager has all120
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:
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.
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:
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 took68
bytes; partA
on imageMemory was successfully re-allocated to
12
integers, now it takes56
bytes, partB
on imageIn 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 imageReallocated 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
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:
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 is24
bytes;16
for user data,8
for metadataReallocating block first time from
16
to12
user data bytes did not affect internal memory structureIt is not possible to create new empty block as it would be too small, only
4
bytes available, minimum is8
bytes for meta dataIt 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 successDifference between old and new size is
8
bytes which is enough for new empty blockIts size is
8
bytes, effectively0
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 differenceCase
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 sizecurrent_size - new_size
and added to list of free blocksCase
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 blockCase
2
: Merge previous empty block with existing one and shift data upCase
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
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:
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) uses32
bytes of dataReallocation is successful, block has been extended to
40
bytes and next free block has been shrinked down to80
bytes
Free block before + allocated block create one big contiguous block
Free block before + allocated block create one big contiguous 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:
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
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:
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 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 from12
to16
bytesReallocation is successful, there is a free block just after and green block is successfully enlarged
Block after is shrinked from
12
to8
bytesCode example (follows initial state code example)
Enlarge of existing block for case 3A1/* 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 outputNew 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 from12
to28
bytesBlock 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 3B1/* 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 outputNew 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 from12
to32
bytesBlock 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
bytesContent of green block is shifted to the beginning of new block
New block is limited to
32
bytes, keeping8
bytes marked as free at the end
Enlarge of existing block for case 3C1/* 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 outputNew 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 from12
to44
bytesNone of the methods (
3a - 3c
) are available as blocks are too smallCompletely 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 to40
Enlarge of existing block for case 3D1/* 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 outputNew 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 case3a
Code restores latest saved state (case
3
) and executes case3b
Code restores latest saved state (case
3
) and executes case3c
Code restores latest saved state (case
3
) and executes case3d
Initial state 3
is generated using C code:
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(®ions_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:
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)