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
|
# Releasing vmem, reloaded
_2026 August_
Here's a cool strategy I came up with that's a huge improvement over
the naive one with the array sort explained here:
* [Releasing virtual memory](260817-release.html)
At least, it doesn't require extra memory allocation, so it would be
safe to use whenever. All it needs is a statically allocated array,
like in the `.data` or `.bss` section of the executable.
As above, I will describe the algo in terms of a single size class;
just loop over the size classes and apply it to as many as needed
until enough memory is released to the kernel.
* Allocate a single static array of a relatively small even number,
like 16, 32, or 64. Every two elements are a FROM and a TO index.
* Initialize them all to some NULL/INVALID index value. (Need this
every time the algo runs, since it may be dirty from last run.)
* Initialize a counter UNHANDLED to 0.
* Now iterate through all free-list entries (the chunk head indexes
and indexes of each chunk) and do as follows for each INDEX:
For each FROM / TO pair in the static array, do one of these:
* Check if FROM is NULL; if so, write INDEX into FROM and TO.
(Registers a new span of memory into the static array.)
* Check if INDEX equals FROM - 1; if so, write INDEX into FROM.
(Expands this span of memory backwards.)
* Check if INDEX equals TO + 1; if so, write INDEX into TO.
(Expands this span of memory forwards.)
* Otherwise, increment UNHANDLED. (Found an index belonging to a
span of memory we can't handle right now; static array is full.)
Note: When I write INDEX - 1 and INDEX + 1 I mean "the index that
would belong to the previous / next slot of this size class" which
typically means subtracting or adding some multiple of 8 to the
index value, depending on slot size.
* After we're done with the free-list iteration, we now have pairs of
from-to indexes representing free spans of memory. There may be
some that actually connect to each other (one "to" happens to be
equal to another "from") so we could run a normalization loop over
the array... Which may be most easily achieved by just sorting it.
* In any case we've found N vacancies in a single iteration through
the free-list... Except it could actually just be a single one,
because the array immediately filled up with dispersed indexes
within a single span, which we didn't know would eventually all
connect to each other! Crap.
Well, this is why I write down these notes; clarifying some idea
often reveals a flaw in it. Anyhow, moving on for now.
* If UNHANDLED is a reasonably large number, we may decide to go for
another loop through the free-list.
OK, a small improvement immediately occurs to me:
* Keep the array permanently sorted by shifting around entries when
new ones are added. (It's small; that's fine to do. Just don't
literally call sort every time; use a smart algo that keeps empty
slots in the array etc., like a kind of streaming sort with upper
size bound. No idea if "streaming sort" is a thing. Now it is?
Another way to view this is... Just a B-Tree of height 1?)
* This will have a chance of revealing connected spans as we go, so
they can be concatenated on-the-run and a from/to pair slot in the
array freed up.
Choosing a sufficiently large static array could actually make this
quite effective, but 16 or 32 probably won't cut it. It all depends
on the user's memory allocation and freeing patterns, but using an
array of length 1024 or a small multiple thereof may work well.
Ultimately, it's better than nothing. The size of the array sets a
lower bound on the length of the span we will find in the pessimal
case: `N * slot_size`. For N = 1024, and the smallest size class,
which is 128 bytes, that's still... 128 KiB. OK, maybe that's not
very much, but it's the *absolute worst* case.
(Later addition: Nope, it's even worse, because we may end up having
to skip lots of indexes, when the array is full, that would have at
some point revealed that it's one big span. The real worst-case is
something much worse I think, but it doesn't matter anymore because
read on...)
Another improvement comes to mind, along with a flaw in the original
plan:
First of all, the static array must be large enough to hold at least
every element of a free-list node including the head of the chunk.
And that twice, since each index is stored as FROM and TO initially.
Given 16-element chunks, that means the array must be at least 34
indexes long. The reason is simple: I didn't consider at what point
entries / chunks would be pruned from the free-list. If every index
of a chunk is inserted into our array, OK, detach the chunk, but if
there's even one index that remains unhandled, what do we do with it?
The chunk header has to stay in the free-list, the other indexes get
"liberated" from it, and the one index we couldn't handle remains.
That's pretty ugly.
But lo and behold: What if we reuse the memory of the free slots??
Even with the smallest size class of 128, that's space for 32 more
index values.
We could build a B-tree of free slots, out of the free slots!
I'm getting tired, so I think I'll leave it here.
To be continued...
|
