1 // SPDX-License-Identifier: GPL-2.0 1
2 /*
3 * KMSAN initialization routines.
4 *
5 * Copyright (C) 2017-2021 Google LLC
6 * Author: Alexander Potapenko <glider@google.
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[N
24 static int future_index __initdata;
25
26 /*
27 * Record a range of memory for which the meta
28 * the page allocator becomes available.
29 */
30 static void __init kmsan_record_future_shadow_
31 {
32 u64 nstart = (u64)start, nend = (u64)e
33 bool merged = false;
34
35 KMSAN_WARN_ON(future_index == NUM_FUTU
36 KMSAN_WARN_ON((nstart >= nend) ||
37 /* Virtual address 0 is
38 (!IS_ENABLED(CONFIG_S390
39 !nend);
40 nstart = ALIGN_DOWN(nstart, PAGE_SIZE)
41 nend = ALIGN(nend, PAGE_SIZE);
42
43 /*
44 * Scan the existing ranges to see if
45 * [start, end). In that case, merge t
46 * creating a new one.
47 * The number of ranges is less than 2
48 * them into a more intelligent data s
49 */
50 for (int i = 0; i < future_index; i++)
51 cstart = start_end_pairs[i].st
52 cend = start_end_pairs[i].end;
53 if ((cstart < nstart && cend <
54 (cstart > nend && cend > n
55 /* ranges are disjoint
56 continue;
57 start_end_pairs[i].start = min
58 start_end_pairs[i].end = max(n
59 merged = true;
60 break;
61 }
62 if (merged)
63 return;
64 start_end_pairs[future_index].start =
65 start_end_pairs[future_index].end = ne
66 future_index++;
67 }
68
69 /*
70 * Initialize the shadow for existing mappings
71 * These include kernel text/data sections, NO
72 * registered while creating other data (e.g.
73 *
74 * Allocations via memblock can be only done b
75 */
76 void __init kmsan_init_shadow(void)
77 {
78 const size_t nd_size = sizeof(pg_data_
79 phys_addr_t p_start, p_end;
80 u64 loop;
81 int nid;
82
83 for_each_reserved_mem_range(loop, &p_s
84 kmsan_record_future_shadow_ran
85
86 /* Allocate shadow for .data */
87 kmsan_record_future_shadow_range(_sdat
88
89 for_each_online_node(nid)
90 kmsan_record_future_shadow_ran
91 NODE_DATA(nid), (char
92
93 for (int i = 0; i < future_index; i++)
94 kmsan_init_alloc_meta_for_rang
95 (void *)start_end_pair
96 (void *)start_end_pair
97 }
98
99 struct metadata_page_pair {
100 struct page *shadow, *origin;
101 };
102 static struct metadata_page_pair held_back[NR_
103
104 /*
105 * Eager metadata allocation. When the membloc
106 * pagealloc, we use 2/3 of them as metadata f
107 * We store the pointers to the returned block
108 * by their order: when kmsan_memblock_free_pa
109 * time with a certain order, it is reserved a
110 * time - as an origin block. On the third tim
111 * shadow and origin ranges from the previousl
112 * after which held_back[order] can be used ag
113 *
114 * At the very end there may be leftover block
115 * collected later by kmsan_memblock_discard()
116 */
117 bool kmsan_memblock_free_pages(struct page *pa
118 {
119 struct page *shadow, *origin;
120
121 if (!held_back[order].shadow) {
122 held_back[order].shadow = page
123 return false;
124 }
125 if (!held_back[order].origin) {
126 held_back[order].origin = page
127 return false;
128 }
129 shadow = held_back[order].shadow;
130 origin = held_back[order].origin;
131 kmsan_setup_meta(page, shadow, origin,
132
133 held_back[order].shadow = NULL;
134 held_back[order].origin = NULL;
135 return true;
136 }
137
138 #define MAX_BLOCKS 8
139 struct smallstack {
140 struct page *items[MAX_BLOCKS];
141 int index;
142 int order;
143 };
144
145 static struct smallstack collect = {
146 .index = 0,
147 .order = MAX_PAGE_ORDER,
148 };
149
150 static void smallstack_push(struct smallstack
151 {
152 KMSAN_WARN_ON(stack->index == MAX_BLOC
153 stack->items[stack->index] = pages;
154 stack->index++;
155 }
156 #undef MAX_BLOCKS
157
158 static struct page *smallstack_pop(struct smal
159 {
160 struct page *ret;
161
162 KMSAN_WARN_ON(stack->index == 0);
163 stack->index--;
164 ret = stack->items[stack->index];
165 stack->items[stack->index] = NULL;
166 return ret;
167 }
168
169 static void do_collection(void)
170 {
171 struct page *page, *shadow, *origin;
172
173 while (collect.index >= 3) {
174 page = smallstack_pop(&collect
175 shadow = smallstack_pop(&colle
176 origin = smallstack_pop(&colle
177 kmsan_setup_meta(page, shadow,
178 __free_pages_core(page, collec
179 }
180 }
181
182 static void collect_split(void)
183 {
184 struct smallstack tmp = {
185 .order = collect.order - 1,
186 .index = 0,
187 };
188 struct page *page;
189
190 if (!collect.order)
191 return;
192 while (collect.index) {
193 page = smallstack_pop(&collect
194 smallstack_push(&tmp, &page[0]
195 smallstack_push(&tmp, &page[1
196 }
197 __memcpy(&collect, &tmp, sizeof(tmp));
198 }
199
200 /*
201 * Memblock is about to go away. Split the pag
202 * and return 1/3 of that memory to the system
203 */
204 static void kmsan_memblock_discard(void)
205 {
206 /*
207 * For each order=N:
208 * - push held_back[N].shadow and .or
209 * - while there are >= 3 elements in
210 * - pop 3 ranges from @collect;
211 * - use two of them as shadow and
212 * - repeat;
213 * - split each remaining element fro
214 * order=N-1,
215 * - repeat.
216 */
217 collect.order = MAX_PAGE_ORDER;
218 for (int i = MAX_PAGE_ORDER; i >= 0; i
219 if (held_back[i].shadow)
220 smallstack_push(&colle
221 if (held_back[i].origin)
222 smallstack_push(&colle
223 held_back[i].shadow = NULL;
224 held_back[i].origin = NULL;
225 do_collection();
226 collect_split();
227 }
228 }
229
230 void __init kmsan_init_runtime(void)
231 {
232 /* Assuming current is init_task */
233 kmsan_internal_task_create(current);
234 kmsan_memblock_discard();
235 pr_info("Starting KernelMemorySanitize
236 pr_info("ATTENTION: KMSAN is a debuggi
237 kmsan_enabled = true;
238 }
239
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.