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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
# Releasing virtual memory
_2026 August_
Allocators often face the issue of not being able to release virtual
memory back to the operating system.
Here I describe a strategy through which Zisp's "Meta Allocator" as
I've decided to name it can solve this.
The strategy may be applicable to more general-purpose allocators as
well; I've not thought much about it and don't currently care. I'll
simply describe this strategy in terms of how it applies to the Zisp
Meta Allocator.
## Recap of the relevant parts of Meta Alloc
For each of the 16 size classes supported, there's a 16 GiB slab, a
global (shared) free-list, and a watermark beyond which the slab's
memory has not yet been touched.
Above the watermark hasn't been paged in by the kernel anyway, since
it's never been touched. But the entire region below the watermark
has physical RAM or swap space backing it.
We need to find vacant spans of memory under the watermark, and tell
the OS that we don't need them by calling `madvise(DONTNEED)` so the
kernel can reclaim the backing physical memory.
Let's focus on a single size class; the strategy I'll describe can
then be applied iteratively to each one. I'll be speaking of one
global free-list from now on; what's meant is the global free-list
belonging to the specific size class we're operating on.
## The problem
As many allocations and deallocations happen in chaotic order, the
memory of a slab becomes filled with free-list entries all over the
place, which hold metadata and thus aren't even truly unused.
(Note on terminology: A slot is the size-class sized piece of memory
the allocator returns to the user; the slot index is the position of
the slot within the slab it belongs to, like a compressed pointer.)
Although Meta Alloc puts entire inline arrays of free slot indexes
into the nodes of the free-list, meaning that many freed slots are
actually completely empty (not as in zero bytes but as in devoid of
meaningful data; they just hold whatever bytes were put in by the
application before freeing the slot) it's nevertheless not easy to
find long spans of such free slot indexes, since the slots may be
freed in any order.
For example, you may look into the head node of the global free-list
and find it to contain the indexes 13, 129, 73, 5, 36, ... which is
pretty useless because we don't want to call `madvise()` in a loop;
that would be very inefficient. And even that extremely simplistic
strategy would only work for size classes 4K and up.
No, we need a way to actually find long spans of unneeded memory.
## The process
It's quite simple, really:
* Allocate a reasonably large array, perhaps simply with `mmap()` or
using a slot from one of our own huge size classes; doesn't matter.
* Optionally, call the function that flushes thread-local reserves,
which is normally meant for thread shutdown but it can be called
whenever you want because it doesn't destroy anything.
* Iterate through the global free-list, putting all indexes into our
big array. (Including indexes of the nodes themselves.) Sort it
in-place. Reset the global free-list.
* Now iterate through the sorted array, identifying contiguous index
sequences, which represent uninterrupted spans of unneeded memory.
* If the sequence represents a span of memory large enough to be worth
freeing back to the OS, transform it into a vacancy-list entry, and
call `madvise(DONTNEED)` on the sub-span starting at the next page
boundary, going up to the last page boundary within the span.
* If the sequence is interrupted before a worthy size is reached, put
the indexes back into the global free-list.
## What the fuck is a vacancy-list entry
That's simple, too:
It's just like the free-list, but instead of each node containing a
bunch of freed slot indexes and the index of the next node, the nodes
of the vacancy-list instead just contain the size of the vacancy, and
a pointer to the next vacancy-list entry.
Remember, the vacancy-list entries represent large spans of memory,
since they were created from contiguous free slot indexes. So you
just need to record the size, and have a pointer to the next; the
entire rest is a huge chunk of (now) completely unused memory.
It's like a free-list for arbitrarily size holes in vmem.
## How do I reuse the vacancies?
A simplistic strategy --too simplistic-- would be to use the start of
the vacancy as the new "low watermark" of a thread, setting the "high
watermark" to the end of the vacancy, thus reserving the entire thing
for a thread.
(Threads have a low and high watermark to represent reserved regions
of memory within a slab, so they don't need to update the global slab
watermark too often, which requires an atomic operation.)
(This would happen when a thread doesn't have any entries in its free
slot cache, no reserved memory from the slab, and the global free-list
is also empty. Better to leave the vacancy vacant for as long as we
don't absolutely need it, since using it means page faults.)
The reason this is too simplistic is that the vacancy may be way too
large to make sense to reserve for a single thread.
Instead, the thread can set its low and high watermark to a sub-span
of the vacancy, and update it accordingly. Unless it's small enough
to make sense to reserve entirely, in which case its used up and
popped from the global vacancy-list.
## That's all
That's it. That's the entire strategy.
It requires a large amount of temporary memory and an in-place sort;
performance won't exactly be great, so this operation should only be
performed upon explicit request. Also, the need for extra temporary
memory means this is *not* intended for when memory is tight!
For example, if an application using our Meta Alloc has an intensely
memory hungry initialization process, but is then expected to run for
hours or days with lower memory requirements, or if there's certain
highly memory intensive subroutines that are only rarely performed,
then the application code could explicitly request this vmem release
operation after the memory intense section.
I'm not actually planning to implement this yet, but it's good to
document the idea for the future.
Oh, actually, this could mostly happen in parallel in a background
thread: The nodes of the global free-list could be popped one by one
through atomic ops without the need for an entire mutex-guarded code
section, and the vacancy-list entries later pushed one by one. So,
the time required may be mostly a non-issue. Still, the issue with
extra memory use remains.
## So what if memory is tight?
OK, there's an even simpler little strategy that doesn't require any
extra temporary memory:
Iterate through the free-list of a size class that's at least page
sized (4K), and for each index that represents a completely unused
slot (i.e., the indexes that are inlined within the free-list node)
call `madvise(DONTNEED)` directly on the memory of the slot.
This only works for sufficiently large size classes, but needs no
sorting of indexes in extra memory. How the execution time would
compare depends on how costly `madvise()` is, and how many indexes
you'd be sorting; I've no idea.
This could save us from OOM in a pinch. It should probably not be
automated, except maybe for some humongous size classes.
|
