-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathtip_of_the_day_2.html
266 lines (236 loc) · 23.9 KB
/
tip_of_the_day_2.html
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
<!DOCTYPE html>
<html>
<head>
<title>Tip of the day #2: A safer arena allocator</title>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link type="application/atom+xml" href="/blog/feed.xml" rel="self">
<link rel="shortcut icon" type="image/ico" href="/blog/favicon.ico">
<link rel="stylesheet" type="text/css" href="main.css">
<link rel="stylesheet" href="https://unpkg.com/@highlightjs/[email protected]/styles/default.min.css">
<script src="highlight.min.js"></script>
<!-- From https://github.com/odin-lang/odin-lang.org/blob/6f48c2cfb094a42dffd34143884fa958bd9c0ba2/themes/odin/layouts/partials/head.html#L71 -->
<script src="x86asm.min.js"></script>
<script src="odin_syntax.js"></script>
<script type="module" src="search_index.js"></script>
<script type="module" src="search.js"></script>
</head>
<body>
<div id="banner">
<div id="name">
<img id="me" src="me.jpeg">
<span>Philippe Gaultier</span>
</div>
<input id="search" placeholder="🔎 Search" autocomplete=off>
<ul>
<li> <a href="/blog/body_of_work.html">Body of work</a> </li>
<li> <a href="/blog/articles-by-tag.html">Tags</a> </li>
<li> <a href="https://github.com/gaultier/resume/raw/master/Philippe_Gaultier_resume_en.pdf">
Resume
</a> </li>
<li> <a href="/blog/feed.xml">
<svg viewBox="0 0 24 24" fill="none" xmlns="http://www.w3.org/2000/svg">
<path fill-rule="evenodd" clip-rule="evenodd" d="M5.5 3.5C4.39543 3.5 3.5 4.39543 3.5 5.5V18.5C3.5 19.6046 4.39543 20.5 5.5 20.5H18.5C19.6046 20.5 20.5 19.6046 20.5 18.5V5.5C20.5 4.39543 19.6046 3.5 18.5 3.5H5.5ZM7 19C8.10457 19 9 18.1046 9 17C9 15.8954 8.10457 15 7 15C5.89543 15 5 15.8954 5 17C5 18.1046 5.89543 19 7 19ZM6.14863 10.5052C6.14863 10.0379 6.52746 9.65906 6.99478 9.65906C7.95949 9.65906 8.91476 9.84908 9.80603 10.2183C10.6973 10.5874 11.5071 11.1285 12.1893 11.8107C12.8715 12.4929 13.4126 13.3027 13.7817 14.194C14.1509 15.0852 14.3409 16.0405 14.3409 17.0052C14.3409 17.4725 13.9621 17.8514 13.4948 17.8514C13.0275 17.8514 12.6486 17.4725 12.6486 17.0052C12.6486 16.2627 12.5024 15.5275 12.2183 14.8416C11.9341 14.1556 11.5177 13.5324 10.9927 13.0073C10.4676 12.4823 9.84437 12.0659 9.15842 11.7817C8.47246 11.4976 7.73726 11.3514 6.99478 11.3514C6.52746 11.3514 6.14863 10.9725 6.14863 10.5052ZM7 5.15385C6.53268 5.15385 6.15385 5.53268 6.15385 6C6.15385 6.46732 6.53268 6.84615 7 6.84615C8.33342 6.84615 9.65379 7.10879 10.8857 7.61907C12.1176 8.12935 13.237 8.87728 14.1799 9.82015C15.1227 10.763 15.8707 11.8824 16.3809 13.1143C16.8912 14.3462 17.1538 15.6666 17.1538 17C17.1538 17.4673 17.5327 17.8462 18 17.8462C18.4673 17.8462 18.8462 17.4673 18.8462 17C18.8462 15.4443 18.5397 13.9039 17.9444 12.4667C17.3491 11.0294 16.4765 9.72352 15.3765 8.6235C14.2765 7.52349 12.9706 6.65091 11.5333 6.05558C10.0961 5.46026 8.55566 5.15385 7 5.15385Z" fill="#000000"/>
</svg>
</a> </li>
<li> <a href="https://www.linkedin.com/in/philippegaultier/">
<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" data-supported-dps="24x24" fill="currentColor" class="mercado-match" width="24" height="24" focusable="false">
<path d="M20.5 2h-17A1.5 1.5 0 002 3.5v17A1.5 1.5 0 003.5 22h17a1.5 1.5 0 001.5-1.5v-17A1.5 1.5 0 0020.5 2zM8 19H5v-9h3zM6.5 8.25A1.75 1.75 0 118.3 6.5a1.78 1.78 0 01-1.8 1.75zM19 19h-3v-4.74c0-1.42-.6-1.93-1.38-1.93A1.74 1.74 0 0013 14.19a.66.66 0 000 .14V19h-3v-9h2.9v1.3a3.11 3.11 0 012.7-1.4c1.55 0 3.36.86 3.36 3.66z"/>
</svg>
</a> </li>
<li> <a href="https://github.com/gaultier">
<svg height="32" aria-hidden="true" viewBox="0 0 24 24" version="1.1" width="32" data-view-component="true" class="octicon octicon-mark-github v-align-middle">
<path d="M12.5.75C6.146.75 1 5.896 1 12.25c0 5.089 3.292 9.387 7.863 10.91.575.101.79-.244.79-.546 0-.273-.014-1.178-.014-2.142-2.889.532-3.636-.704-3.866-1.35-.13-.331-.69-1.352-1.18-1.625-.402-.216-.977-.748-.014-.762.906-.014 1.553.834 1.769 1.179 1.035 1.74 2.688 1.25 3.349.948.1-.747.402-1.25.733-1.538-2.559-.287-5.232-1.279-5.232-5.678 0-1.25.445-2.285 1.178-3.09-.115-.288-.517-1.467.115-3.048 0 0 .963-.302 3.163 1.179.92-.259 1.897-.388 2.875-.388.977 0 1.955.13 2.875.388 2.2-1.495 3.162-1.179 3.162-1.179.633 1.581.23 2.76.115 3.048.733.805 1.179 1.825 1.179 3.09 0 4.413-2.688 5.39-5.247 5.678.417.36.776 1.05.776 2.128 0 1.538-.014 2.774-.014 3.162 0 .302.216.662.79.547C20.709 21.637 24 17.324 24 12.25 24 5.896 18.854.75 12.5.75Z"/>
</svg>
</a> </li>
<li> <a href="https://hachyderm.io/@pg">
<svg width="75" height="79" viewBox="0 0 75 79" fill="none" xmlns="http://www.w3.org/2000/svg">
<path d="M73.8393 17.4898C72.6973 9.00165 65.2994 2.31235 56.5296 1.01614C55.05 0.797115 49.4441 0 36.4582 0H36.3612C23.3717 0 20.585 0.797115 19.1054 1.01614C10.5798 2.27644 2.79399 8.28712 0.904997 16.8758C-0.00358524 21.1056 -0.100549 25.7949 0.0682394 30.0965C0.308852 36.2651 0.355538 42.423 0.91577 48.5665C1.30307 52.6474 1.97872 56.6957 2.93763 60.6812C4.73325 68.042 12.0019 74.1676 19.1233 76.6666C26.7478 79.2728 34.9474 79.7055 42.8039 77.9162C43.6682 77.7151 44.5217 77.4817 45.3645 77.216C47.275 76.6092 49.5123 75.9305 51.1571 74.7385C51.1797 74.7217 51.1982 74.7001 51.2112 74.6753C51.2243 74.6504 51.2316 74.6229 51.2325 74.5948V68.6416C51.2321 68.6154 51.2259 68.5896 51.2142 68.5661C51.2025 68.5426 51.1858 68.522 51.1651 68.5058C51.1444 68.4896 51.1204 68.4783 51.0948 68.4726C51.0692 68.4669 51.0426 68.467 51.0171 68.4729C45.9835 69.675 40.8254 70.2777 35.6502 70.2682C26.7439 70.2682 24.3486 66.042 23.6626 64.2826C23.1113 62.762 22.7612 61.1759 22.6212 59.5646C22.6197 59.5375 22.6247 59.5105 22.6357 59.4857C22.6466 59.4609 22.6633 59.4391 22.6843 59.422C22.7053 59.4048 22.73 59.3929 22.7565 59.3871C22.783 59.3813 22.8104 59.3818 22.8367 59.3886C27.7864 60.5826 32.8604 61.1853 37.9522 61.1839C39.1768 61.1839 40.3978 61.1839 41.6224 61.1516C46.7435 61.008 52.1411 60.7459 57.1796 59.7621C57.3053 59.7369 57.431 59.7154 57.5387 59.6831C65.4861 58.157 73.0493 53.3672 73.8178 41.2381C73.8465 40.7606 73.9184 36.2364 73.9184 35.7409C73.9219 34.0569 74.4606 23.7949 73.8393 17.4898Z" fill="url(#paint0_linear_549_34)"/>
<path d="M61.2484 27.0263V48.114H52.8916V27.6475C52.8916 23.3388 51.096 21.1413 47.4437 21.1413C43.4287 21.1413 41.4177 23.7409 41.4177 28.8755V40.0782H33.1111V28.8755C33.1111 23.7409 31.0965 21.1413 27.0815 21.1413C23.4507 21.1413 21.6371 23.3388 21.6371 27.6475V48.114H13.2839V27.0263C13.2839 22.7176 14.384 19.2946 16.5843 16.7572C18.8539 14.2258 21.8311 12.926 25.5264 12.926C29.8036 12.926 33.0357 14.5705 35.1905 17.8559L37.2698 21.346L39.3527 17.8559C41.5074 14.5705 44.7395 12.926 49.0095 12.926C52.7013 12.926 55.6784 14.2258 57.9553 16.7572C60.1531 19.2922 61.2508 22.7152 61.2484 27.0263Z" fill="white"/>
<defs>
<linearGradient id="paint0_linear_549_34" x1="37.0692" y1="0" x2="37.0692" y2="79" gradientUnits="userSpaceOnUse">
<stop stop-color="#6364FF"/>
<stop offset="1" stop-color="#563ACC"/>
</linearGradient>
</defs>
</svg>
</a> </li>
<li> <a href="https://bsky.app/profile/pgaultier.bsky.social">
<svg fill="none" viewBox="0 0 64 57" width="32" style="width: 32px; height: 28.5px;"><path fill="#0085ff" d="M13.873 3.805C21.21 9.332 29.103 20.537 32 26.55v15.882c0-.338-.13.044-.41.867-1.512 4.456-7.418 21.847-20.923 7.944-7.111-7.32-3.819-14.64 9.125-16.85-7.405 1.264-15.73-.825-18.014-9.015C1.12 23.022 0 8.51 0 6.55 0-3.268 8.579-.182 13.873 3.805ZM50.127 3.805C42.79 9.332 34.897 20.537 32 26.55v15.882c0-.338.13.044.41.867 1.512 4.456 7.418 21.847 20.923 7.944 7.111-7.32 3.819-14.64-9.125-16.85 7.405 1.264 15.73-.825 18.014-9.015C62.88 23.022 64 8.51 64 6.55c0-9.818-8.578-6.732-13.873-2.745Z"/></svg>
</a> </li>
</ul>
</div>
<div id="search-matches" hidden>
</div>
<div id="pseudo-body">
<div class="article-prelude">
<p><a href="/blog"> ⏴ Back to all articles</a></p>
<p class="publication-date">Published on 2024-10-29</p>
</div>
<div class="article-title">
<h1>Tip of the day #2: A safer arena allocator</h1>
<div class="tags"> <a href="/blog/articles-by-tag.html#c" class="tag">C</a> <a href="/blog/articles-by-tag.html#allocator" class="tag">Allocator</a> <a href="/blog/articles-by-tag.html#safety" class="tag">Safety</a> <a href="/blog/articles-by-tag.html#tip-of-the-day" class="tag">Tip of the day</a></div>
</div>
<strong>Table of contents</strong>
<ul>
<li>
<a href="#3570727127-the-standard-arena">The standard arena</a>
</li>
<li>
<a href="#366874779-the-bug">The bug</a>
</li>
<li>
<a href="#1807516660-the-solution">The solution</a>
</li>
<li>
<a href="#2175727336-variations">Variations</a>
<ul>
<li>
<a href="#3293170840-the-paranoid-approach">The paranoid approach</a>
</li>
<li>
<a href="#332247973-the-bucket-per-type-approach">The bucket per type approach</a>
</li>
</ul>
</li>
<li>
<a href="#3625827200-see-also">See also</a>
</li>
</ul>
<p><em>Discussions: <a href="https://old.reddit.com/r/programming/comments/1gfiif5/tip_of_the_day_2_a_safer_arena_allocator/">/r/programming</a>, <a href="https://old.reddit.com/r/cprogramming/comments/1gfiit0/tip_of_the_day_2_a_safer_arena_allocator/?">/r/cprogramming</a></em></p>
<p>The most transformative action you can do to dramatically improve your code in a programming language where you are in control of the memory is: to use arenas.</p>
<p>Much has been written about arenas (<a href="https://nullprogram.com/blog/2023/09/27/">1</a>, <a href="https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator">2</a>). In short, it means grouping multiple allocations with the same lifetime in one batch that gets allocated and deallocated only once.</p>
<p>Another way to look at it, is that the allocations are append only. They never get freed during their 'life'. The program is split into 'phases'. Typically, each phase has its own arena, and when it reaches its end, the whole arena gets nuked from space along with all entities allocated from it. It's a great way to simplify the code, make it faster, and escape from the 'web of pointers' hell.</p>
<h2 id="3570727127-the-standard-arena">
<a class="title" href="#3570727127-the-standard-arena">The standard arena</a>
<a class="hash-anchor" href="#3570727127-the-standard-arena" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>A typical arena looks like that:</p>
<pre><code class="language-c">#include <stdint.h>
#include <stdio.h>
#include <sys/mman.h>
#include <unistd.h>
typedef struct {
uint8_t *start;
uint8_t *end;
} Arena;
static Arena arena_make_from_virtual_mem(uint64_t size) {
uint8_t *alloc = mmap(nullptr, size, PROT_READ | PROT_WRITE,
MAP_ANON | MAP_PRIVATE, -1, 0);
return (Arena){.start = alloc, .end = alloc + size};
}
static void *
arena_alloc(Arena *a, uint64_t size, uint64_t align, uint64_t count) {
const uint64_t padding = (-(uint64_t)a->start & (align - 1));
const int64_t available = (int64_t)a->end - (int64_t)a->start - (int64_t)padding;
void *res = a->start + padding;
a->start += padding + count * size;
return memset(res, 0, count * size);
}
int main() {
Arena a = arena_make_from_virtual_mem(4096);
}
</code></pre>
<p>Very simple, just ask the OS to give us a region of virtual memory and off we go (on Windows, the system call is named differently but is equivalent).</p>
<h2 id="366874779-the-bug">
<a class="title" href="#366874779-the-bug">The bug</a>
<a class="hash-anchor" href="#366874779-the-bug" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>Now, since we use a system call directly, sanitizers and runtime checks from the libc allocator do not apply, since we bypass them completely. In a way, it is also a feature: it means that our program will behave exactly the same on all OSes, have the exact same memory layout, and use the exact same amount of memory. It does not depend on the libc or allocator.</p>
<p>So it turns out that I had a bug in my code: I allocated an array from the arena, and then accidentally wrote past the bounds of my array (so far, this sounds like a typical story from the C trenches).</p>
<p>Normally, this would likely (depending on a few factors, like where in the arena was this allocation located, how big was it, and by how many bytes did the write go past the bounds, etc) write past the memory page that the OS gave us, thus triggering a <code>SIGSEGV</code>.</p>
<p>However, in that instance, I got unlucky, because my code actually did something like that:</p>
<pre><code class="language-c">int main() {
Arena a = arena_make_from_virtual_mem(4096);
Arena b = arena_make_from_virtual_mem(4096);
// Simulate writing past the arena:
a.start + 5000 = 42;
}
</code></pre>
<p>And...the program did not crash. The symptoms were very weird: data was subtly wrong in another place of the program, thus making it very difficult to troubleshoot. That's basically the nightmare scenario for any engineer. A crash would be so much easier.</p>
<p>But why?</p>
<p>Well, we basically asked the OS to give us one page of virtual memory when creating the first arena. Right after, we asked for a second page. And most often than not, the OS gives us then a page right after the first page. So from the OS perspective, we allocated <code>2 * 4096 = 8192</code> bytes, and wrote in the middle, so all is good. We wanted to write into the first arena but instead wrote into the second one accidentally.</p>
<p>This behavior is however not consistent, running the programs many times will sometimes crash and sometimes not. It all depends if the memory pages for the different arenas are contiguous or not.</p>
<h2 id="1807516660-the-solution">
<a class="title" href="#1807516660-the-solution">The solution</a>
<a class="hash-anchor" href="#1807516660-the-solution" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p>So how do we fix it? What I did was defense in depth:</p>
<ul>
<li>Add asserts everywhere I could to check pre- and post-conditions. I believe that's how I discovered the bug in the first place, when one assert failed, even though it seemed impossible.</li>
<li>Replace all direct array and pointer accesses with macros that check bounds (like most modern programming languages)</li>
<li>Tweak how the arena is created to make it safer. That's our tip of the day, so let's see it.</li>
</ul>
<p>The idea is not new, most allocators do so in 'hardening' mode: when the arena is created, we place a 'guard page' right before and after the real allocation.</p>
<p>We mark these guard pages as neither readable nor writable, so any access will trigger a <code>SIGSEGV</code>, even though that's memory owned by our program.</p>
<p>That way, going slightly past the bounds of the real allocation in either direction, will result in a crash that's easy to diagnose.</p>
<p>Note that this is a trade-off:</p>
<ul>
<li>It will not catch all out-of-bounds accesses. We could get unlucky and accidentally hit the memory of another arena still. This is a protection that typically helps with off-by-one errors.</li>
<li>It's very lightweight: the OS only has to maintain an entry in a table, recording that the program owns the two additional pages (per arena). No actually physical memory will be dedicated for them. But, if there are millions of arenas, it could make a difference.</li>
<li>It's theoretically tunable: nothing prevents us from having larger guard 'regions'. If we are paranoid, we could make the guard region 64 Gib before and after the real allocation of 4096 bytes, if we wish. That's the power of virtual memory.</li>
<li>The granularity is still the page (typically 4096 bytes, something larger). We cannot easily prevent out-of-bounds accesses within a page.</li>
<li>The original implementation at the beginning of the article did not have to bother with the size of a page. But this implementation has to, which slightly complicates the logic (but not by much).</li>
</ul>
<p>So here it is:</p>
<pre><code class="language-c">static Arena arena_make_from_virtual_mem(uint64_t size) {
uint64_t page_size = (uint64_t)sysconf(_SC_PAGE_SIZE);
uint64_t alloc_real_size = round_up_multiple_of(size, page_size);
// Page guard before + after.
uint64_t mmap_size = alloc_real_size + 2 * page_size;
uint8_t *alloc = mmap(nullptr, mmap_size, PROT_READ | PROT_WRITE,
MAP_ANON | MAP_PRIVATE, -1, 0);
uint64_t page_guard_before = (uint64_t)alloc;
alloc += page_size;
uint64_t page_guard_after = (uint64_t)alloc + alloc_real_size;
mprotect((void *)page_guard_before, page_size, PROT_NONE);
mprotect((void *)page_guard_after, page_size, PROT_NONE);
return (Arena){.start = alloc, .end = alloc + size};
}
</code></pre>
<p>We get the page size with POSIX's <code>sysconf (3)</code>. Again, that's required because we will use the system call <code>mprotect</code> to change the permissions on parts of the memory, and <code>mprotect</code> expects a page-aligned memory range.</p>
<p>Since an allocation is at least one page, even if the user asked for an arena of size <code>1</code>, we first round the user allocation size up, to the next page size. E.g. for a page size of <code>4096</code>: <code>1 -> 4096</code>, <code>4095 -> 4096</code>, <code>4096 -> 4096</code>, <code>4097 -> 8192</code>.</p>
<p>Then, in one <code>mmap</code> call, we allocate all the memory we need including the two guard pages. For a brief moment, all the memory is readable and writable. The very next thing we do is mark the first page and last page as neither readable nor writable. We then return the arena, and the user is none the wiser.</p>
<p>Wouldn't it be simpler to issue 3 <code>mmap</code> calls with the right permissions from the get go? Well, yes, but there is no guarantee that the OS would give us a contiguous region of memory across these 3 calls. On Linux, we can give hints, but still there is no guarantee. Remember, our program is one of many running concurrently, and could get interrupted for some time between these <code>mmap</code> calls, the whole OS could go to sleep, etc. What we want is an atomic operation, thus, one <code>mmap</code> call.</p>
<p>Note, we can alternatively create the whole allocation as <code>PROT_NONE</code> and then mark the real (user-visible) allocation as <code>PROT_READ | PROT_WRITE</code>, that also works.</p>
<p>So that's it, a poor man Adress Sanitizer in a few lines of code.</p>
<h2 id="2175727336-variations">
<a class="title" href="#2175727336-variations">Variations</a>
<a class="hash-anchor" href="#2175727336-variations" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<h3 id="3293170840-the-paranoid-approach">
<a class="title" href="#3293170840-the-paranoid-approach">The paranoid approach</a>
<a class="hash-anchor" href="#3293170840-the-paranoid-approach" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h3>
<p>If we are really paranoid, we could change how the arena works, to make every allocation get a new, separate page from the OS. That means that creating the arena would do nothing, and allocating from the arena would do the real allocation. This approach is, to me, indistinguishable from a general purpose allocator a la <code>malloc</code> from libc, just one that's very naive, and probably much slower.</p>
<p>But, if there is a pesky out-of-bound bug pestering you, that could be worth trying.</p>
<h3 id="332247973-the-bucket-per-type-approach">
<a class="title" href="#332247973-the-bucket-per-type-approach">The bucket per type approach</a>
<a class="hash-anchor" href="#332247973-the-bucket-per-type-approach" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h3>
<p>On <a href="https://www.youtube.com/watch?v=t7EJTO0-reg">Apple platforms</a>, the libc allocator has a hardening mode that can be enabled at compile time. It stems from the realization that many security vulnerabilities rely on type confusion: The program thinks it is handling an entity of type <code>X</code>, but due to a logic bug, or the attacker meddling, or the allocator reusing freshly freed memory from another place in the program, it is actually of another type <code>Y</code>. This results in an entity being in an 'impossible' state which is great for an attacker. Also, reusing a previously allocated-then-freed object with a different type, without zero-initializing it, can leak secrets or information about the state of the program, to an attacker.</p>
<p>There's a whole class of attacks where the first step is to make the program allocate and free objects many times, of an attacker controlled size, so that the heap is in the right 'shape', with a high statistical chance. Meaning, a few targeted objects are next to each other in the heap, for the attack to occur.</p>
<p>So, the mitigation is to place all allocations of the same type in one bucket (supposedly, it's a separate memory region with guard pages before and after). When an object of type <code>X</code> is allocated, then freed, and then the program allocates an object of type <code>Y</code>, of roughly the same size, a typical allocator will reuse the memory of <code>X</code>. This Apple allocator would give memory from a separate bucket, from a completely different memory region.</p>
<p>What I don't know, is whether or not there are runtime checks as well, for example when casting one object from one type to another e.g. from <code>X</code> to <code>void*</code>, back to <code>X</code>, with <code>reinterpret_cast</code> in C++. It seems that this allocator would have the information needed at runtime to do so, which could be an interesting feature.</p>
<p>Now, having one bucket per type turns out to be too slow in reality, and consumes too much memory, according to Apple developers, so this allocator groups a handful a different types in one bucket. This is a typical trade-off between performance and security.</p>
<p>Still, this is an interesting approach, and could be implemented in our context by having one arena store all entities of one type, i.e. one arena is one bucket.</p>
<h2 id="3625827200-see-also">
<a class="title" href="#3625827200-see-also">See also</a>
<a class="hash-anchor" href="#3625827200-see-also" aria-hidden="true" onclick="navigator.clipboard.writeText(this.href);"></a>
</h2>
<p><em>Astute readers have also mentioned: using canaries in the available space in the arena to detect illegal accesses, putting the real data at the start or end of the page to catch out-of-bounds accesses respectively before and after the allocation, periodic checks for long-running applications, randomizing where the guard pages are placed relative to the allocation, running the tests a number of times to catch inconsistent behavior, and finally, teaching Address Sanitizer to be aware of our custom arena allocator so that it does these checks for us. That's super cool! See the linked discussions at the start.</em></p>
<p>I wrote in the past about adding memory profiling an arena allocator: <a href="/blog/roll_your_own_memory_profiling.html">Roll your own memory profiling: it's actually not hard</a>.</p>
<p><a href="/blog"> ⏴ Back to all articles</a></p>
<blockquote id="donate">
<p>If you enjoy what you're reading, you want to support me, and can afford it: <a href="https://paypal.me/philigaultier?country.x=DE&locale.x=en_US">Support me</a>. That allows me to write more cool articles!</p>
</blockquote>
<blockquote>
<p>
This blog is <a href="https://github.com/gaultier/blog">open-source</a>!
If you find a problem, please open a Github issue.
The content of this blog as well as the code snippets are under the <a href="https://en.wikipedia.org/wiki/BSD_licenses#3-clause_license_(%22BSD_License_2.0%22,_%22Revised_BSD_License%22,_%22New_BSD_License%22,_or_%22Modified_BSD_License%22)">BSD-3 License</a> which I also usually use for all my personal projects. It's basically free for every use but you have to mention me as the original author.
</p>
</blockquote>
</div>
</body>
</html>