13c206509SAlexander Potapenko // SPDX-License-Identifier: GPL-2.0
23c206509SAlexander Potapenko /*
33c206509SAlexander Potapenko * KMSAN initialization routines.
43c206509SAlexander Potapenko *
53c206509SAlexander Potapenko * Copyright (C) 2017-2021 Google LLC
63c206509SAlexander Potapenko * Author: Alexander Potapenko <glider@google.com>
73c206509SAlexander Potapenko *
83c206509SAlexander Potapenko */
93c206509SAlexander Potapenko
103c206509SAlexander Potapenko #include "kmsan.h"
113c206509SAlexander Potapenko
123c206509SAlexander Potapenko #include <asm/sections.h>
133c206509SAlexander Potapenko #include <linux/mm.h>
143c206509SAlexander Potapenko #include <linux/memblock.h>
153c206509SAlexander Potapenko
163c206509SAlexander Potapenko #include "../internal.h"
173c206509SAlexander Potapenko
183c206509SAlexander Potapenko #define NUM_FUTURE_RANGES 128
193c206509SAlexander Potapenko struct start_end_pair {
203c206509SAlexander Potapenko u64 start, end;
213c206509SAlexander Potapenko };
223c206509SAlexander Potapenko
233c206509SAlexander Potapenko static struct start_end_pair start_end_pairs[NUM_FUTURE_RANGES] __initdata;
243c206509SAlexander Potapenko static int future_index __initdata;
253c206509SAlexander Potapenko
263c206509SAlexander Potapenko /*
273c206509SAlexander Potapenko * Record a range of memory for which the metadata pages will be created once
283c206509SAlexander Potapenko * the page allocator becomes available.
293c206509SAlexander Potapenko */
kmsan_record_future_shadow_range(void * start,void * end)303c206509SAlexander Potapenko static void __init kmsan_record_future_shadow_range(void *start, void *end)
313c206509SAlexander Potapenko {
323c206509SAlexander Potapenko u64 nstart = (u64)start, nend = (u64)end, cstart, cend;
333c206509SAlexander Potapenko bool merged = false;
343c206509SAlexander Potapenko
353c206509SAlexander Potapenko KMSAN_WARN_ON(future_index == NUM_FUTURE_RANGES);
363c206509SAlexander Potapenko KMSAN_WARN_ON((nstart >= nend) || !nstart || !nend);
373c206509SAlexander Potapenko nstart = ALIGN_DOWN(nstart, PAGE_SIZE);
383c206509SAlexander Potapenko nend = ALIGN(nend, PAGE_SIZE);
393c206509SAlexander Potapenko
403c206509SAlexander Potapenko /*
413c206509SAlexander Potapenko * Scan the existing ranges to see if any of them overlaps with
423c206509SAlexander Potapenko * [start, end). In that case, merge the two ranges instead of
433c206509SAlexander Potapenko * creating a new one.
443c206509SAlexander Potapenko * The number of ranges is less than 20, so there is no need to organize
453c206509SAlexander Potapenko * them into a more intelligent data structure.
463c206509SAlexander Potapenko */
473c206509SAlexander Potapenko for (int i = 0; i < future_index; i++) {
483c206509SAlexander Potapenko cstart = start_end_pairs[i].start;
493c206509SAlexander Potapenko cend = start_end_pairs[i].end;
503c206509SAlexander Potapenko if ((cstart < nstart && cend < nstart) ||
513c206509SAlexander Potapenko (cstart > nend && cend > nend))
523c206509SAlexander Potapenko /* ranges are disjoint - do not merge */
533c206509SAlexander Potapenko continue;
543c206509SAlexander Potapenko start_end_pairs[i].start = min(nstart, cstart);
553c206509SAlexander Potapenko start_end_pairs[i].end = max(nend, cend);
563c206509SAlexander Potapenko merged = true;
573c206509SAlexander Potapenko break;
583c206509SAlexander Potapenko }
593c206509SAlexander Potapenko if (merged)
603c206509SAlexander Potapenko return;
613c206509SAlexander Potapenko start_end_pairs[future_index].start = nstart;
623c206509SAlexander Potapenko start_end_pairs[future_index].end = nend;
633c206509SAlexander Potapenko future_index++;
643c206509SAlexander Potapenko }
653c206509SAlexander Potapenko
663c206509SAlexander Potapenko /*
673c206509SAlexander Potapenko * Initialize the shadow for existing mappings during kernel initialization.
683c206509SAlexander Potapenko * These include kernel text/data sections, NODE_DATA and future ranges
693c206509SAlexander Potapenko * registered while creating other data (e.g. percpu).
703c206509SAlexander Potapenko *
713c206509SAlexander Potapenko * Allocations via memblock can be only done before slab is initialized.
723c206509SAlexander Potapenko */
kmsan_init_shadow(void)733c206509SAlexander Potapenko void __init kmsan_init_shadow(void)
743c206509SAlexander Potapenko {
753c206509SAlexander Potapenko const size_t nd_size = roundup(sizeof(pg_data_t), PAGE_SIZE);
763c206509SAlexander Potapenko phys_addr_t p_start, p_end;
773c206509SAlexander Potapenko u64 loop;
783c206509SAlexander Potapenko int nid;
793c206509SAlexander Potapenko
803c206509SAlexander Potapenko for_each_reserved_mem_range(loop, &p_start, &p_end)
813c206509SAlexander Potapenko kmsan_record_future_shadow_range(phys_to_virt(p_start),
823c206509SAlexander Potapenko phys_to_virt(p_end));
833c206509SAlexander Potapenko /* Allocate shadow for .data */
843c206509SAlexander Potapenko kmsan_record_future_shadow_range(_sdata, _edata);
853c206509SAlexander Potapenko
863c206509SAlexander Potapenko for_each_online_node(nid)
873c206509SAlexander Potapenko kmsan_record_future_shadow_range(
883c206509SAlexander Potapenko NODE_DATA(nid), (char *)NODE_DATA(nid) + nd_size);
893c206509SAlexander Potapenko
903c206509SAlexander Potapenko for (int i = 0; i < future_index; i++)
913c206509SAlexander Potapenko kmsan_init_alloc_meta_for_range(
923c206509SAlexander Potapenko (void *)start_end_pairs[i].start,
933c206509SAlexander Potapenko (void *)start_end_pairs[i].end);
943c206509SAlexander Potapenko }
953c206509SAlexander Potapenko
963c206509SAlexander Potapenko struct metadata_page_pair {
973c206509SAlexander Potapenko struct page *shadow, *origin;
983c206509SAlexander Potapenko };
99fd377218SKirill A. Shutemov static struct metadata_page_pair held_back[NR_PAGE_ORDERS] __initdata;
1003c206509SAlexander Potapenko
1013c206509SAlexander Potapenko /*
1023c206509SAlexander Potapenko * Eager metadata allocation. When the memblock allocator is freeing pages to
1033c206509SAlexander Potapenko * pagealloc, we use 2/3 of them as metadata for the remaining 1/3.
1043c206509SAlexander Potapenko * We store the pointers to the returned blocks of pages in held_back[] grouped
1053c206509SAlexander Potapenko * by their order: when kmsan_memblock_free_pages() is called for the first
1063c206509SAlexander Potapenko * time with a certain order, it is reserved as a shadow block, for the second
1073c206509SAlexander Potapenko * time - as an origin block. On the third time the incoming block receives its
1083c206509SAlexander Potapenko * shadow and origin ranges from the previously saved shadow and origin blocks,
1093c206509SAlexander Potapenko * after which held_back[order] can be used again.
1103c206509SAlexander Potapenko *
1113c206509SAlexander Potapenko * At the very end there may be leftover blocks in held_back[]. They are
1123c206509SAlexander Potapenko * collected later by kmsan_memblock_discard().
1133c206509SAlexander Potapenko */
kmsan_memblock_free_pages(struct page * page,unsigned int order)1143c206509SAlexander Potapenko bool kmsan_memblock_free_pages(struct page *page, unsigned int order)
1153c206509SAlexander Potapenko {
1163c206509SAlexander Potapenko struct page *shadow, *origin;
1173c206509SAlexander Potapenko
1183c206509SAlexander Potapenko if (!held_back[order].shadow) {
1193c206509SAlexander Potapenko held_back[order].shadow = page;
1203c206509SAlexander Potapenko return false;
1213c206509SAlexander Potapenko }
1223c206509SAlexander Potapenko if (!held_back[order].origin) {
1233c206509SAlexander Potapenko held_back[order].origin = page;
1243c206509SAlexander Potapenko return false;
1253c206509SAlexander Potapenko }
1263c206509SAlexander Potapenko shadow = held_back[order].shadow;
1273c206509SAlexander Potapenko origin = held_back[order].origin;
1283c206509SAlexander Potapenko kmsan_setup_meta(page, shadow, origin, order);
1293c206509SAlexander Potapenko
1303c206509SAlexander Potapenko held_back[order].shadow = NULL;
1313c206509SAlexander Potapenko held_back[order].origin = NULL;
1323c206509SAlexander Potapenko return true;
1333c206509SAlexander Potapenko }
1343c206509SAlexander Potapenko
1353c206509SAlexander Potapenko #define MAX_BLOCKS 8
1363c206509SAlexander Potapenko struct smallstack {
1373c206509SAlexander Potapenko struct page *items[MAX_BLOCKS];
1383c206509SAlexander Potapenko int index;
1393c206509SAlexander Potapenko int order;
1403c206509SAlexander Potapenko };
1413c206509SAlexander Potapenko
1423c206509SAlexander Potapenko static struct smallstack collect = {
1433c206509SAlexander Potapenko .index = 0,
144*5e0a760bSKirill A. Shutemov .order = MAX_PAGE_ORDER,
1453c206509SAlexander Potapenko };
1463c206509SAlexander Potapenko
smallstack_push(struct smallstack * stack,struct page * pages)1473c206509SAlexander Potapenko static void smallstack_push(struct smallstack *stack, struct page *pages)
1483c206509SAlexander Potapenko {
1493c206509SAlexander Potapenko KMSAN_WARN_ON(stack->index == MAX_BLOCKS);
1503c206509SAlexander Potapenko stack->items[stack->index] = pages;
1513c206509SAlexander Potapenko stack->index++;
1523c206509SAlexander Potapenko }
1533c206509SAlexander Potapenko #undef MAX_BLOCKS
1543c206509SAlexander Potapenko
smallstack_pop(struct smallstack * stack)1553c206509SAlexander Potapenko static struct page *smallstack_pop(struct smallstack *stack)
1563c206509SAlexander Potapenko {
1573c206509SAlexander Potapenko struct page *ret;
1583c206509SAlexander Potapenko
1593c206509SAlexander Potapenko KMSAN_WARN_ON(stack->index == 0);
1603c206509SAlexander Potapenko stack->index--;
1613c206509SAlexander Potapenko ret = stack->items[stack->index];
1623c206509SAlexander Potapenko stack->items[stack->index] = NULL;
1633c206509SAlexander Potapenko return ret;
1643c206509SAlexander Potapenko }
1653c206509SAlexander Potapenko
do_collection(void)1663c206509SAlexander Potapenko static void do_collection(void)
1673c206509SAlexander Potapenko {
1683c206509SAlexander Potapenko struct page *page, *shadow, *origin;
1693c206509SAlexander Potapenko
1703c206509SAlexander Potapenko while (collect.index >= 3) {
1713c206509SAlexander Potapenko page = smallstack_pop(&collect);
1723c206509SAlexander Potapenko shadow = smallstack_pop(&collect);
1733c206509SAlexander Potapenko origin = smallstack_pop(&collect);
1743c206509SAlexander Potapenko kmsan_setup_meta(page, shadow, origin, collect.order);
1753c206509SAlexander Potapenko __free_pages_core(page, collect.order);
1763c206509SAlexander Potapenko }
1773c206509SAlexander Potapenko }
1783c206509SAlexander Potapenko
collect_split(void)1793c206509SAlexander Potapenko static void collect_split(void)
1803c206509SAlexander Potapenko {
1813c206509SAlexander Potapenko struct smallstack tmp = {
1823c206509SAlexander Potapenko .order = collect.order - 1,
1833c206509SAlexander Potapenko .index = 0,
1843c206509SAlexander Potapenko };
1853c206509SAlexander Potapenko struct page *page;
1863c206509SAlexander Potapenko
1873c206509SAlexander Potapenko if (!collect.order)
1883c206509SAlexander Potapenko return;
1893c206509SAlexander Potapenko while (collect.index) {
1903c206509SAlexander Potapenko page = smallstack_pop(&collect);
1913c206509SAlexander Potapenko smallstack_push(&tmp, &page[0]);
1923c206509SAlexander Potapenko smallstack_push(&tmp, &page[1 << tmp.order]);
1933c206509SAlexander Potapenko }
1943c206509SAlexander Potapenko __memcpy(&collect, &tmp, sizeof(tmp));
1953c206509SAlexander Potapenko }
1963c206509SAlexander Potapenko
1973c206509SAlexander Potapenko /*
1983c206509SAlexander Potapenko * Memblock is about to go away. Split the page blocks left over in held_back[]
1993c206509SAlexander Potapenko * and return 1/3 of that memory to the system.
2003c206509SAlexander Potapenko */
kmsan_memblock_discard(void)2013c206509SAlexander Potapenko static void kmsan_memblock_discard(void)
2023c206509SAlexander Potapenko {
2033c206509SAlexander Potapenko /*
2043c206509SAlexander Potapenko * For each order=N:
2053c206509SAlexander Potapenko * - push held_back[N].shadow and .origin to @collect;
2063c206509SAlexander Potapenko * - while there are >= 3 elements in @collect, do garbage collection:
2073c206509SAlexander Potapenko * - pop 3 ranges from @collect;
2083c206509SAlexander Potapenko * - use two of them as shadow and origin for the third one;
2093c206509SAlexander Potapenko * - repeat;
2103c206509SAlexander Potapenko * - split each remaining element from @collect into 2 ranges of
2113c206509SAlexander Potapenko * order=N-1,
2123c206509SAlexander Potapenko * - repeat.
2133c206509SAlexander Potapenko */
214*5e0a760bSKirill A. Shutemov collect.order = MAX_PAGE_ORDER;
215*5e0a760bSKirill A. Shutemov for (int i = MAX_PAGE_ORDER; i >= 0; i--) {
2163c206509SAlexander Potapenko if (held_back[i].shadow)
2173c206509SAlexander Potapenko smallstack_push(&collect, held_back[i].shadow);
2183c206509SAlexander Potapenko if (held_back[i].origin)
2193c206509SAlexander Potapenko smallstack_push(&collect, held_back[i].origin);
2203c206509SAlexander Potapenko held_back[i].shadow = NULL;
2213c206509SAlexander Potapenko held_back[i].origin = NULL;
2223c206509SAlexander Potapenko do_collection();
2233c206509SAlexander Potapenko collect_split();
2243c206509SAlexander Potapenko }
2253c206509SAlexander Potapenko }
2263c206509SAlexander Potapenko
kmsan_init_runtime(void)2273c206509SAlexander Potapenko void __init kmsan_init_runtime(void)
2283c206509SAlexander Potapenko {
2293c206509SAlexander Potapenko /* Assuming current is init_task */
2303c206509SAlexander Potapenko kmsan_internal_task_create(current);
2313c206509SAlexander Potapenko kmsan_memblock_discard();
2323c206509SAlexander Potapenko pr_info("Starting KernelMemorySanitizer\n");
2333c206509SAlexander Potapenko pr_info("ATTENTION: KMSAN is a debugging tool! Do not use it on production machines!\n");
2343c206509SAlexander Potapenko kmsan_enabled = true;
2353c206509SAlexander Potapenko }
236