Commit | Line | Data |
---|---|---|
3c206509 AP |
1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* | |
3 | * KMSAN initialization routines. | |
4 | * | |
5 | * Copyright (C) 2017-2021 Google LLC | |
6 | * Author: Alexander Potapenko <glider@google.com> | |
7 | * | |
8 | */ | |
9 | ||
10 | #include "kmsan.h" | |
11 | ||
12 | #include <asm/sections.h> | |
13 | #include <linux/mm.h> | |
14 | #include <linux/memblock.h> | |
15 | ||
16 | #include "../internal.h" | |
17 | ||
18 | #define NUM_FUTURE_RANGES 128 | |
19 | struct start_end_pair { | |
20 | u64 start, end; | |
21 | }; | |
22 | ||
23 | static struct start_end_pair start_end_pairs[NUM_FUTURE_RANGES] __initdata; | |
24 | static int future_index __initdata; | |
25 | ||
26 | /* | |
27 | * Record a range of memory for which the metadata pages will be created once | |
28 | * the page allocator becomes available. | |
29 | */ | |
30 | static void __init kmsan_record_future_shadow_range(void *start, void *end) | |
31 | { | |
32 | u64 nstart = (u64)start, nend = (u64)end, cstart, cend; | |
33 | bool merged = false; | |
34 | ||
35 | KMSAN_WARN_ON(future_index == NUM_FUTURE_RANGES); | |
36 | KMSAN_WARN_ON((nstart >= nend) || !nstart || !nend); | |
37 | nstart = ALIGN_DOWN(nstart, PAGE_SIZE); | |
38 | nend = ALIGN(nend, PAGE_SIZE); | |
39 | ||
40 | /* | |
41 | * Scan the existing ranges to see if any of them overlaps with | |
42 | * [start, end). In that case, merge the two ranges instead of | |
43 | * creating a new one. | |
44 | * The number of ranges is less than 20, so there is no need to organize | |
45 | * them into a more intelligent data structure. | |
46 | */ | |
47 | for (int i = 0; i < future_index; i++) { | |
48 | cstart = start_end_pairs[i].start; | |
49 | cend = start_end_pairs[i].end; | |
50 | if ((cstart < nstart && cend < nstart) || | |
51 | (cstart > nend && cend > nend)) | |
52 | /* ranges are disjoint - do not merge */ | |
53 | continue; | |
54 | start_end_pairs[i].start = min(nstart, cstart); | |
55 | start_end_pairs[i].end = max(nend, cend); | |
56 | merged = true; | |
57 | break; | |
58 | } | |
59 | if (merged) | |
60 | return; | |
61 | start_end_pairs[future_index].start = nstart; | |
62 | start_end_pairs[future_index].end = nend; | |
63 | future_index++; | |
64 | } | |
65 | ||
66 | /* | |
67 | * Initialize the shadow for existing mappings during kernel initialization. | |
68 | * These include kernel text/data sections, NODE_DATA and future ranges | |
69 | * registered while creating other data (e.g. percpu). | |
70 | * | |
71 | * Allocations via memblock can be only done before slab is initialized. | |
72 | */ | |
73 | void __init kmsan_init_shadow(void) | |
74 | { | |
75 | const size_t nd_size = roundup(sizeof(pg_data_t), PAGE_SIZE); | |
76 | phys_addr_t p_start, p_end; | |
77 | u64 loop; | |
78 | int nid; | |
79 | ||
80 | for_each_reserved_mem_range(loop, &p_start, &p_end) | |
81 | kmsan_record_future_shadow_range(phys_to_virt(p_start), | |
82 | phys_to_virt(p_end)); | |
83 | /* Allocate shadow for .data */ | |
84 | kmsan_record_future_shadow_range(_sdata, _edata); | |
85 | ||
86 | for_each_online_node(nid) | |
87 | kmsan_record_future_shadow_range( | |
88 | NODE_DATA(nid), (char *)NODE_DATA(nid) + nd_size); | |
89 | ||
90 | for (int i = 0; i < future_index; i++) | |
91 | kmsan_init_alloc_meta_for_range( | |
92 | (void *)start_end_pairs[i].start, | |
93 | (void *)start_end_pairs[i].end); | |
94 | } | |
95 | ||
96 | struct metadata_page_pair { | |
97 | struct page *shadow, *origin; | |
98 | }; | |
23baf831 | 99 | static struct metadata_page_pair held_back[MAX_ORDER + 1] __initdata; |
3c206509 AP |
100 | |
101 | /* | |
102 | * Eager metadata allocation. When the memblock allocator is freeing pages to | |
103 | * pagealloc, we use 2/3 of them as metadata for the remaining 1/3. | |
104 | * We store the pointers to the returned blocks of pages in held_back[] grouped | |
105 | * by their order: when kmsan_memblock_free_pages() is called for the first | |
106 | * time with a certain order, it is reserved as a shadow block, for the second | |
107 | * time - as an origin block. On the third time the incoming block receives its | |
108 | * shadow and origin ranges from the previously saved shadow and origin blocks, | |
109 | * after which held_back[order] can be used again. | |
110 | * | |
111 | * At the very end there may be leftover blocks in held_back[]. They are | |
112 | * collected later by kmsan_memblock_discard(). | |
113 | */ | |
114 | bool kmsan_memblock_free_pages(struct page *page, unsigned int order) | |
115 | { | |
116 | struct page *shadow, *origin; | |
117 | ||
118 | if (!held_back[order].shadow) { | |
119 | held_back[order].shadow = page; | |
120 | return false; | |
121 | } | |
122 | if (!held_back[order].origin) { | |
123 | held_back[order].origin = page; | |
124 | return false; | |
125 | } | |
126 | shadow = held_back[order].shadow; | |
127 | origin = held_back[order].origin; | |
128 | kmsan_setup_meta(page, shadow, origin, order); | |
129 | ||
130 | held_back[order].shadow = NULL; | |
131 | held_back[order].origin = NULL; | |
132 | return true; | |
133 | } | |
134 | ||
135 | #define MAX_BLOCKS 8 | |
136 | struct smallstack { | |
137 | struct page *items[MAX_BLOCKS]; | |
138 | int index; | |
139 | int order; | |
140 | }; | |
141 | ||
142 | static struct smallstack collect = { | |
143 | .index = 0, | |
144 | .order = MAX_ORDER, | |
145 | }; | |
146 | ||
147 | static void smallstack_push(struct smallstack *stack, struct page *pages) | |
148 | { | |
149 | KMSAN_WARN_ON(stack->index == MAX_BLOCKS); | |
150 | stack->items[stack->index] = pages; | |
151 | stack->index++; | |
152 | } | |
153 | #undef MAX_BLOCKS | |
154 | ||
155 | static struct page *smallstack_pop(struct smallstack *stack) | |
156 | { | |
157 | struct page *ret; | |
158 | ||
159 | KMSAN_WARN_ON(stack->index == 0); | |
160 | stack->index--; | |
161 | ret = stack->items[stack->index]; | |
162 | stack->items[stack->index] = NULL; | |
163 | return ret; | |
164 | } | |
165 | ||
166 | static void do_collection(void) | |
167 | { | |
168 | struct page *page, *shadow, *origin; | |
169 | ||
170 | while (collect.index >= 3) { | |
171 | page = smallstack_pop(&collect); | |
172 | shadow = smallstack_pop(&collect); | |
173 | origin = smallstack_pop(&collect); | |
174 | kmsan_setup_meta(page, shadow, origin, collect.order); | |
175 | __free_pages_core(page, collect.order); | |
176 | } | |
177 | } | |
178 | ||
179 | static void collect_split(void) | |
180 | { | |
181 | struct smallstack tmp = { | |
182 | .order = collect.order - 1, | |
183 | .index = 0, | |
184 | }; | |
185 | struct page *page; | |
186 | ||
187 | if (!collect.order) | |
188 | return; | |
189 | while (collect.index) { | |
190 | page = smallstack_pop(&collect); | |
191 | smallstack_push(&tmp, &page[0]); | |
192 | smallstack_push(&tmp, &page[1 << tmp.order]); | |
193 | } | |
194 | __memcpy(&collect, &tmp, sizeof(tmp)); | |
195 | } | |
196 | ||
197 | /* | |
198 | * Memblock is about to go away. Split the page blocks left over in held_back[] | |
199 | * and return 1/3 of that memory to the system. | |
200 | */ | |
201 | static void kmsan_memblock_discard(void) | |
202 | { | |
203 | /* | |
204 | * For each order=N: | |
205 | * - push held_back[N].shadow and .origin to @collect; | |
206 | * - while there are >= 3 elements in @collect, do garbage collection: | |
207 | * - pop 3 ranges from @collect; | |
208 | * - use two of them as shadow and origin for the third one; | |
209 | * - repeat; | |
210 | * - split each remaining element from @collect into 2 ranges of | |
211 | * order=N-1, | |
212 | * - repeat. | |
213 | */ | |
23baf831 KS |
214 | collect.order = MAX_ORDER; |
215 | for (int i = MAX_ORDER; i >= 0; i--) { | |
3c206509 AP |
216 | if (held_back[i].shadow) |
217 | smallstack_push(&collect, held_back[i].shadow); | |
218 | if (held_back[i].origin) | |
219 | smallstack_push(&collect, held_back[i].origin); | |
220 | held_back[i].shadow = NULL; | |
221 | held_back[i].origin = NULL; | |
222 | do_collection(); | |
223 | collect_split(); | |
224 | } | |
225 | } | |
226 | ||
227 | void __init kmsan_init_runtime(void) | |
228 | { | |
229 | /* Assuming current is init_task */ | |
230 | kmsan_internal_task_create(current); | |
231 | kmsan_memblock_discard(); | |
232 | pr_info("Starting KernelMemorySanitizer\n"); | |
233 | pr_info("ATTENTION: KMSAN is a debugging tool! Do not use it on production machines!\n"); | |
234 | kmsan_enabled = true; | |
235 | } |