blob: d51463ec33ca53cfb4f5e3372e5884337be4f66b (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
[Doc] Box64 Memory Allocator (for review and feedback)
This document describes the memory management design in Box64 (`custommem.c`).
The goal is to verify the correctness and gather feedback for improvements.
Below is the current draft:
### High-Level Overview
The memory allocator operates similarly to a segregated free list by maintaining an array of **blocks**.
In this context, a "**block**" refers to one of three types of fixed-size memory mappings:
- 512 KB blocks for general use
- 128 KB blocks for fixed 128-byte slices
- 2 MB blocks for dynarec (dynamic recompilation)
Within each block, smaller pieces — called **subblocks** — are carved out.
**Subblocks** are the actual allocation units returned to the caller.
There are two types of free subblock tracking implementations:
- `BTYPE_LIST`: Managed using an implicit free list, with `blockmark_t` headers placed before each payload.
The end of a block is indicated by a special subblock where `next.x32 == 0`.
- `BTYPE_MAP`: Subblocks are tracked using a `bitmap` at the end of the block.
Each block is tracked by a `blocklist_s` structure — metadata for each mapped region:
```c
typedef struct blocklist_s {
void* block; // Base address of the mapped region
size_t maxfree; // Largest contiguous free space (in bytes) available
size_t size; // Total size of the region (including bitmap if present)
void* first; // Pointer to bitmap (`BTYPE_MAP`) or to the first free subblock (`BTYPE_LIST`)
uint32_t lowest; // Hint index for next allocation scan (bitmap only)
uint8_t type; // Either `BTYPE_LIST` or `BTYPE_MAP`
} blocklist_t;
```
In `BTYPE_LIST`, subblocks are linked implicitly via the offset field (offs) in `blockmark_s`:
```c
typedef struct blockmark_s {
mark_t prev; // Marker for the previous subblock
mark_t next; // Marker for the next subblock
uint8_t mark[]; // Flexible array member; payload starts here
} blockmark_t;
```
Where `mark_t` represents the distance between two subblock headers:
```c
typedef union mark_s {
struct {
unsigned int offs : 31; // Byte offset to the next or previous header
unsigned int fill : 1; // Allocation flag (0 = free, 1 = allocated)
};
uint32_t x32;
} mark_t;
```
A set of macros is provided to help navigate between subblocks inside a block.
These macros rely on the offs fields inside the `mark_t` structures:
```c
#define NEXT_BLOCK(b) ((blockmark_t*)((uintptr_t)(b) + (b)->next.offs))
// Get the pointer to the next subblock.
#define PREV_BLOCK(b) ((blockmark_t*)((uintptr_t)(b) - (b)->prev.offs))
// Get the pointer to the previous subblock.
#define LAST_BLOCK(b, s) ((blockmark_t*)((uintptr_t)(b) + (s)) - sizeof(blockmark_t))
// Get the pointer to the subblock at the end of the block with size 's'.
#define SIZE_BLOCK(b) (((ssize_t)(b).offs) - sizeof(blockmark_t))
// Get the usable payload size of a subblock (excluding the size of its own header).
```
|