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
|
# Releasing vmem, again
_2026 August_
Finding contiguous spans of freed memory is difficult when all you
have is a free-list in arbitrary order.
It's especially difficult if you don't want to allocate auxiliary
memory, which is crucial if you're trying to free memory to the OS
because it's signaling memory pressure or declining an allocation.
Here's a method that sacrifices CPU time, in exchange for locating
unused spans of memory from a free-list without extra allocation.
## Locking
Meta Alloc uses a lock-free Treiber stack for the free-list, which
only works when threads contend for the top node of the linked list,
trying to push and pop in parallel.
Any subroutine that wants to walk through the whole list will need
some other strategy for synchronization. Here are some choices:
1. Some way to communicate to the relevant portions of `alloc()` and
`free()` that the free-list is locked. Not sure how to best do
this in a way that doesn't defeat the purpose of the lock-free
strategy, but there are ways.
2. Atomically swap out the entire free-list (replace head with NULL
through a CAS) and swap it back in when we're done. This would
mean that threads simply go on to allocate fresh memory, while
we're busy releasing memory. Probably not great.
3. Atomically swap out the entire free-list, but also use some global
flag that says "fresh allocations banned." The benefit of this is
that you don't *have* to set that flag; you can decide that based
on whether memory pressure is really that severe. This way, the
free-list pruning can be done without stalling allocations when
there's no such dire pressure.
I think I like the third. It means that, when fresh alloc is banned,
threads will stall after they've found the free-list to be empty, but
can just check it again once they continue. Pseudo-code:
if (check_free_list()) |ptr|
return ptr;
if (fresh_alloc_banned()) // Reads atomic flag
sleep_until_unbanned(); // Could just be a 10 ms sleep loop.
if (check_vacancy_list()) |ptr|
return ptr;
return alloc_fresh_memory();
And if the ban isn't put in place, threads don't stall at all, which
seems ideal. The fact that they'll bump the slab watermark when it
isn't truly needed is benign; we just end up with some holes in our
slab, recorded in the vacancy-list, so they'll be reused if needed.
## The obvious
Before doing anything more complicated:
For each size class greater than or equal to page size, use the above
strategy to hide the free-list, go through it and `madvise(DONTNEED)`
every non-chunk-head slot, then put the free-list back in place.
For example, if the 64 KiB size class uses free-list chunk nodes that
carry 4 extra slot indexes, it means 4 out of every 5 slots can be
released back to the OS.
Oh, actually, chunk heads never use more than the first 128 bytes of
the slot. (Subject to change by tweaking constants, but it'll surely
never reach 4 KiB.) So, we can also safely release every non-first
page of every chunk head slot. Taking the 64 KiB size class as an
example again, where each slot is 16 pages (assuming 4 KiB), we can
release `4*16+15` out of `5*16` pages. That's 79/80, or 98.75% of
memory held by the free-list, that we can release.
I think the worst-case is the 4 KiB size class, and even there, the
free-list chunks store 8 other slots, so we release 8 out of every 9
pages back to the OS. That's ~88.89% which isn't too bad. The next
is the 8 KiB class where it comes out to 17/18 i.e. ~94.44%.
## The tedious
The challenge is size classes under 4 KiB. Or if we want something
better than ~88% release efficiency for 4 KiB / better than ~94% for
the 8 KiB size class. (Beyond that, it seems stupid to worry about,
as we surpass 95% release efficiency.)
So let's see what we can do if individual slots are under a page,
meaning we have to find contiguous sequences of them across the
free-list to be able to consolidate and release them.
The consolidation in question could happen in two ways:
* Transform the free-list such that contiguous slots are, as much as
possible, not used as chunk heads, so the pages of memory they make
up can be released. This works, for example, if we have four 1 KiB
slots that form a contiguous span of memory, i.e. a page, so we can
release that page and make sure to store these four indexes within
some chunk header, not using any of them as a header that needs to
hold data.
* Just turn the contiguous spans of memory we find into vacancy-list
entries instead.
The second option is simpler and simply better. I don't know why I
even bothered to write out the other option.
The only question, then, is how to identify such contiguous slots in
the free-list, which carries indexes in arbitrary order.
At this point I have to admit that the following is probably way too
much complication for a small benefit, and this is partly just a fun
mental exercise.
[TBC]
|
