Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0
2 : /*
3 : * KASAN quarantine.
4 : *
5 : * Author: Alexander Potapenko <glider@google.com>
6 : * Copyright (C) 2016 Google, Inc.
7 : *
8 : * Based on code by Dmitry Chernenkov.
9 : */
10 :
11 : #include <linux/gfp.h>
12 : #include <linux/hash.h>
13 : #include <linux/kernel.h>
14 : #include <linux/mm.h>
15 : #include <linux/percpu.h>
16 : #include <linux/printk.h>
17 : #include <linux/shrinker.h>
18 : #include <linux/slab.h>
19 : #include <linux/srcu.h>
20 : #include <linux/string.h>
21 : #include <linux/types.h>
22 : #include <linux/cpuhotplug.h>
23 :
24 : #include "../slab.h"
25 : #include "kasan.h"
26 :
27 : /* Data structure and operations for quarantine queues. */
28 :
29 : /*
30 : * Each queue is a signle-linked list, which also stores the total size of
31 : * objects inside of it.
32 : */
33 : struct qlist_head {
34 : struct qlist_node *head;
35 : struct qlist_node *tail;
36 : size_t bytes;
37 : bool offline;
38 : };
39 :
40 : #define QLIST_INIT { NULL, NULL, 0 }
41 :
42 1278852 : static bool qlist_empty(struct qlist_head *q)
43 : {
44 1278852 : return !q->head;
45 : }
46 :
47 3296 : static void qlist_init(struct qlist_head *q)
48 : {
49 3296 : q->head = q->tail = NULL;
50 3296 : q->bytes = 0;
51 814 : }
52 :
53 1273018 : static void qlist_put(struct qlist_head *q, struct qlist_node *qlink,
54 : size_t size)
55 : {
56 1273018 : if (unlikely(qlist_empty(q)))
57 838 : q->head = qlink;
58 : else
59 1272180 : q->tail->next = qlink;
60 1273018 : q->tail = qlink;
61 1273018 : qlink->next = NULL;
62 1273018 : q->bytes += size;
63 0 : }
64 :
65 2482 : static void qlist_move_all(struct qlist_head *from, struct qlist_head *to)
66 : {
67 2482 : if (unlikely(qlist_empty(from)))
68 : return;
69 :
70 2482 : if (qlist_empty(to)) {
71 2482 : *to = *from;
72 2482 : qlist_init(from);
73 2482 : return;
74 : }
75 :
76 0 : to->tail->next = from->head;
77 0 : to->tail = from->tail;
78 0 : to->bytes += from->bytes;
79 :
80 0 : qlist_init(from);
81 : }
82 :
83 : #define QUARANTINE_PERCPU_SIZE (1 << 20)
84 : #define QUARANTINE_BATCHES \
85 : (1024 > 4 * CONFIG_NR_CPUS ? 1024 : 4 * CONFIG_NR_CPUS)
86 :
87 : /*
88 : * The object quarantine consists of per-cpu queues and a global queue,
89 : * guarded by quarantine_lock.
90 : */
91 : static DEFINE_PER_CPU(struct qlist_head, cpu_quarantine);
92 :
93 : /* Round-robin FIFO array of batches. */
94 : static struct qlist_head global_quarantine[QUARANTINE_BATCHES];
95 : static int quarantine_head;
96 : static int quarantine_tail;
97 : /* Total size of all objects in global_quarantine across all batches. */
98 : static unsigned long quarantine_size;
99 : static DEFINE_RAW_SPINLOCK(quarantine_lock);
100 : DEFINE_STATIC_SRCU(remove_cache_srcu);
101 :
102 : /* Maximum size of the global queue. */
103 : static unsigned long quarantine_max_size;
104 :
105 : /*
106 : * Target size of a batch in global_quarantine.
107 : * Usually equal to QUARANTINE_PERCPU_SIZE unless we have too much RAM.
108 : */
109 : static unsigned long quarantine_batch_size;
110 :
111 : /*
112 : * The fraction of physical memory the quarantine is allowed to occupy.
113 : * Quarantine doesn't support memory shrinker with SLAB allocator, so we keep
114 : * the ratio low to avoid OOM.
115 : */
116 : #define QUARANTINE_FRACTION 32
117 :
118 1223649 : static struct kmem_cache *qlink_to_cache(struct qlist_node *qlink)
119 : {
120 1223649 : return virt_to_head_page(qlink)->slab_cache;
121 : }
122 :
123 1223671 : static void *qlink_to_object(struct qlist_node *qlink, struct kmem_cache *cache)
124 : {
125 1223671 : struct kasan_free_meta *free_info =
126 1223671 : container_of(qlink, struct kasan_free_meta,
127 : quarantine_link);
128 :
129 1223671 : return ((void *)free_info) - cache->kasan_info.free_meta_offset;
130 : }
131 :
132 1223671 : static void qlink_free(struct qlist_node *qlink, struct kmem_cache *cache)
133 : {
134 1223671 : void *object = qlink_to_object(qlink, cache);
135 1223671 : unsigned long flags;
136 :
137 1223671 : if (IS_ENABLED(CONFIG_SLAB))
138 1223671 : local_irq_save(flags);
139 :
140 : /*
141 : * As the object now gets freed from the quaratine, assume that its
142 : * free track is no longer valid.
143 : */
144 1223671 : *(u8 *)kasan_mem_to_shadow(object) = KASAN_KMALLOC_FREE;
145 :
146 1223671 : ___cache_free(cache, object, _THIS_IP_);
147 :
148 1223642 : if (IS_ENABLED(CONFIG_SLAB))
149 1223642 : local_irq_restore(flags);
150 1223642 : }
151 :
152 870 : static void qlist_free_all(struct qlist_head *q, struct kmem_cache *cache)
153 : {
154 870 : struct qlist_node *qlink;
155 :
156 870 : if (unlikely(qlist_empty(q)))
157 : return;
158 :
159 : qlink = q->head;
160 1224456 : while (qlink) {
161 2447283 : struct kmem_cache *obj_cache =
162 2447290 : cache ? cache : qlink_to_cache(qlink);
163 1223641 : struct qlist_node *next = qlink->next;
164 :
165 1223641 : qlink_free(qlink, obj_cache);
166 1223641 : qlink = next;
167 : }
168 814 : qlist_init(q);
169 : }
170 :
171 1273956 : bool kasan_quarantine_put(struct kmem_cache *cache, void *object)
172 : {
173 1273956 : unsigned long flags;
174 1273956 : struct qlist_head *q;
175 1273956 : struct qlist_head temp = QLIST_INIT;
176 1273956 : struct kasan_free_meta *meta = kasan_get_free_meta(cache, object);
177 :
178 : /*
179 : * If there's no metadata for this object, don't put it into
180 : * quarantine.
181 : */
182 1273415 : if (!meta)
183 : return false;
184 :
185 : /*
186 : * Note: irq must be disabled until after we move the batch to the
187 : * global quarantine. Otherwise kasan_quarantine_remove_cache() can
188 : * miss some objects belonging to the cache if they are in our local
189 : * temp list. kasan_quarantine_remove_cache() executes on_each_cpu()
190 : * at the beginning which ensures that it either sees the objects in
191 : * per-cpu lists or in the global quarantine.
192 : */
193 2547340 : local_irq_save(flags);
194 :
195 1272882 : q = this_cpu_ptr(&cpu_quarantine);
196 1273018 : if (q->offline) {
197 0 : local_irq_restore(flags);
198 0 : return false;
199 : }
200 1273018 : qlist_put(q, &meta->quarantine_link, cache->size);
201 1273018 : if (unlikely(q->bytes > QUARANTINE_PERCPU_SIZE)) {
202 834 : qlist_move_all(q, &temp);
203 :
204 834 : raw_spin_lock(&quarantine_lock);
205 834 : WRITE_ONCE(quarantine_size, quarantine_size + temp.bytes);
206 834 : qlist_move_all(&temp, &global_quarantine[quarantine_tail]);
207 834 : if (global_quarantine[quarantine_tail].bytes >=
208 834 : READ_ONCE(quarantine_batch_size)) {
209 834 : int new_tail;
210 :
211 834 : new_tail = quarantine_tail + 1;
212 834 : if (new_tail == QUARANTINE_BATCHES)
213 0 : new_tail = 0;
214 834 : if (new_tail != quarantine_head)
215 834 : quarantine_tail = new_tail;
216 : }
217 834 : raw_spin_unlock(&quarantine_lock);
218 : }
219 :
220 1273018 : local_irq_restore(flags);
221 :
222 : return true;
223 : }
224 :
225 1383343 : void kasan_quarantine_reduce(void)
226 : {
227 1383343 : size_t total_size, new_quarantine_size, percpu_quarantines;
228 1383343 : unsigned long flags;
229 1383343 : int srcu_idx;
230 1383343 : struct qlist_head to_free = QLIST_INIT;
231 :
232 1383343 : if (likely(READ_ONCE(quarantine_size) <=
233 : READ_ONCE(quarantine_max_size)))
234 1382475 : return;
235 :
236 : /*
237 : * srcu critical section ensures that kasan_quarantine_remove_cache()
238 : * will not miss objects belonging to the cache while they are in our
239 : * local to_free list. srcu is chosen because (1) it gives us private
240 : * grace period domain that does not interfere with anything else,
241 : * and (2) it allows synchronize_srcu() to return without waiting
242 : * if there are no pending read critical sections (which is the
243 : * expected case).
244 : */
245 868 : srcu_idx = srcu_read_lock(&remove_cache_srcu);
246 869 : raw_spin_lock_irqsave(&quarantine_lock, flags);
247 :
248 : /*
249 : * Update quarantine size in case of hotplug. Allocate a fraction of
250 : * the installed memory to quarantine minus per-cpu queue limits.
251 : */
252 870 : total_size = (totalram_pages() << PAGE_SHIFT) /
253 : QUARANTINE_FRACTION;
254 870 : percpu_quarantines = QUARANTINE_PERCPU_SIZE * num_online_cpus();
255 1740 : new_quarantine_size = (total_size < percpu_quarantines) ?
256 870 : 0 : total_size - percpu_quarantines;
257 870 : WRITE_ONCE(quarantine_max_size, new_quarantine_size);
258 : /* Aim at consuming at most 1/2 of slots in quarantine. */
259 870 : WRITE_ONCE(quarantine_batch_size, max((size_t)QUARANTINE_PERCPU_SIZE,
260 : 2 * total_size / QUARANTINE_BATCHES));
261 :
262 870 : if (likely(quarantine_size > quarantine_max_size)) {
263 814 : qlist_move_all(&global_quarantine[quarantine_head], &to_free);
264 814 : WRITE_ONCE(quarantine_size, quarantine_size - to_free.bytes);
265 814 : quarantine_head++;
266 814 : if (quarantine_head == QUARANTINE_BATCHES)
267 0 : quarantine_head = 0;
268 : }
269 :
270 870 : raw_spin_unlock_irqrestore(&quarantine_lock, flags);
271 :
272 870 : qlist_free_all(&to_free, NULL);
273 870 : srcu_read_unlock(&remove_cache_srcu, srcu_idx);
274 : }
275 :
276 0 : static void qlist_move_cache(struct qlist_head *from,
277 : struct qlist_head *to,
278 : struct kmem_cache *cache)
279 : {
280 0 : struct qlist_node *curr;
281 :
282 0 : if (unlikely(qlist_empty(from)))
283 : return;
284 :
285 0 : curr = from->head;
286 0 : qlist_init(from);
287 0 : while (curr) {
288 0 : struct qlist_node *next = curr->next;
289 0 : struct kmem_cache *obj_cache = qlink_to_cache(curr);
290 :
291 0 : if (obj_cache == cache)
292 0 : qlist_put(to, curr, obj_cache->size);
293 : else
294 0 : qlist_put(from, curr, obj_cache->size);
295 :
296 : curr = next;
297 : }
298 : }
299 :
300 0 : static void per_cpu_remove_cache(void *arg)
301 : {
302 0 : struct kmem_cache *cache = arg;
303 0 : struct qlist_head to_free = QLIST_INIT;
304 0 : struct qlist_head *q;
305 :
306 0 : q = this_cpu_ptr(&cpu_quarantine);
307 0 : qlist_move_cache(q, &to_free, cache);
308 0 : qlist_free_all(&to_free, cache);
309 0 : }
310 :
311 : /* Free all quarantined objects belonging to cache. */
312 0 : void kasan_quarantine_remove_cache(struct kmem_cache *cache)
313 : {
314 0 : unsigned long flags, i;
315 0 : struct qlist_head to_free = QLIST_INIT;
316 :
317 : /*
318 : * Must be careful to not miss any objects that are being moved from
319 : * per-cpu list to the global quarantine in kasan_quarantine_put(),
320 : * nor objects being freed in kasan_quarantine_reduce(). on_each_cpu()
321 : * achieves the first goal, while synchronize_srcu() achieves the
322 : * second.
323 : */
324 0 : on_each_cpu(per_cpu_remove_cache, cache, 1);
325 :
326 0 : raw_spin_lock_irqsave(&quarantine_lock, flags);
327 0 : for (i = 0; i < QUARANTINE_BATCHES; i++) {
328 0 : if (qlist_empty(&global_quarantine[i]))
329 0 : continue;
330 0 : qlist_move_cache(&global_quarantine[i], &to_free, cache);
331 : /* Scanning whole quarantine can take a while. */
332 0 : raw_spin_unlock_irqrestore(&quarantine_lock, flags);
333 0 : cond_resched();
334 0 : raw_spin_lock_irqsave(&quarantine_lock, flags);
335 : }
336 0 : raw_spin_unlock_irqrestore(&quarantine_lock, flags);
337 :
338 0 : qlist_free_all(&to_free, cache);
339 :
340 0 : synchronize_srcu(&remove_cache_srcu);
341 0 : }
342 :
343 4 : static int kasan_cpu_online(unsigned int cpu)
344 : {
345 4 : this_cpu_ptr(&cpu_quarantine)->offline = false;
346 4 : return 0;
347 : }
348 :
349 0 : static int kasan_cpu_offline(unsigned int cpu)
350 : {
351 0 : struct qlist_head *q;
352 :
353 0 : q = this_cpu_ptr(&cpu_quarantine);
354 : /* Ensure the ordering between the writing to q->offline and
355 : * qlist_free_all. Otherwise, cpu_quarantine may be corrupted
356 : * by interrupt.
357 : */
358 0 : WRITE_ONCE(q->offline, true);
359 0 : barrier();
360 0 : qlist_free_all(q, NULL);
361 0 : return 0;
362 : }
363 :
364 1 : static int __init kasan_cpu_quarantine_init(void)
365 : {
366 1 : int ret = 0;
367 :
368 1 : ret = cpuhp_setup_state(CPUHP_AP_ONLINE_DYN, "mm/kasan:online",
369 : kasan_cpu_online, kasan_cpu_offline);
370 1 : if (ret < 0)
371 0 : pr_err("kasan cpu quarantine register failed [%d]\n", ret);
372 1 : return ret;
373 : }
374 : late_initcall(kasan_cpu_quarantine_init);
|
