239 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * KMSAN initialization routines.4 *5 * Copyright (C) 2017-2021 Google LLC6 * 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 12819struct start_end_pair {20 u64 start, end;21};22 23static struct start_end_pair start_end_pairs[NUM_FUTURE_RANGES] __initdata;24static int future_index __initdata;25 26/*27 * Record a range of memory for which the metadata pages will be created once28 * the page allocator becomes available.29 */30static 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) ||37 /* Virtual address 0 is valid on s390. */38 (!IS_ENABLED(CONFIG_S390) && !nstart) ||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 any of them overlaps with45 * [start, end). In that case, merge the two ranges instead of46 * creating a new one.47 * The number of ranges is less than 20, so there is no need to organize48 * them into a more intelligent data structure.49 */50 for (int i = 0; i < future_index; i++) {51 cstart = start_end_pairs[i].start;52 cend = start_end_pairs[i].end;53 if ((cstart < nstart && cend < nstart) ||54 (cstart > nend && cend > nend))55 /* ranges are disjoint - do not merge */56 continue;57 start_end_pairs[i].start = min(nstart, cstart);58 start_end_pairs[i].end = max(nend, cend);59 merged = true;60 break;61 }62 if (merged)63 return;64 start_end_pairs[future_index].start = nstart;65 start_end_pairs[future_index].end = nend;66 future_index++;67}68 69/*70 * Initialize the shadow for existing mappings during kernel initialization.71 * These include kernel text/data sections, NODE_DATA and future ranges72 * registered while creating other data (e.g. percpu).73 *74 * Allocations via memblock can be only done before slab is initialized.75 */76void __init kmsan_init_shadow(void)77{78 const size_t nd_size = sizeof(pg_data_t);79 phys_addr_t p_start, p_end;80 u64 loop;81 int nid;82 83 for_each_reserved_mem_range(loop, &p_start, &p_end)84 kmsan_record_future_shadow_range(phys_to_virt(p_start),85 phys_to_virt(p_end));86 /* Allocate shadow for .data */87 kmsan_record_future_shadow_range(_sdata, _edata);88 89 for_each_online_node(nid)90 kmsan_record_future_shadow_range(91 NODE_DATA(nid), (char *)NODE_DATA(nid) + nd_size);92 93 for (int i = 0; i < future_index; i++)94 kmsan_init_alloc_meta_for_range(95 (void *)start_end_pairs[i].start,96 (void *)start_end_pairs[i].end);97}98 99struct metadata_page_pair {100 struct page *shadow, *origin;101};102static struct metadata_page_pair held_back[NR_PAGE_ORDERS] __initdata;103 104/*105 * Eager metadata allocation. When the memblock allocator is freeing pages to106 * pagealloc, we use 2/3 of them as metadata for the remaining 1/3.107 * We store the pointers to the returned blocks of pages in held_back[] grouped108 * by their order: when kmsan_memblock_free_pages() is called for the first109 * time with a certain order, it is reserved as a shadow block, for the second110 * time - as an origin block. On the third time the incoming block receives its111 * shadow and origin ranges from the previously saved shadow and origin blocks,112 * after which held_back[order] can be used again.113 *114 * At the very end there may be leftover blocks in held_back[]. They are115 * collected later by kmsan_memblock_discard().116 */117bool kmsan_memblock_free_pages(struct page *page, unsigned int order)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, order);132 133 held_back[order].shadow = NULL;134 held_back[order].origin = NULL;135 return true;136}137 138#define MAX_BLOCKS 8139struct smallstack {140 struct page *items[MAX_BLOCKS];141 int index;142 int order;143};144 145static struct smallstack collect = {146 .index = 0,147 .order = MAX_PAGE_ORDER,148};149 150static void smallstack_push(struct smallstack *stack, struct page *pages)151{152 KMSAN_WARN_ON(stack->index == MAX_BLOCKS);153 stack->items[stack->index] = pages;154 stack->index++;155}156#undef MAX_BLOCKS157 158static struct page *smallstack_pop(struct smallstack *stack)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 169static 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(&collect);176 origin = smallstack_pop(&collect);177 kmsan_setup_meta(page, shadow, origin, collect.order);178 __free_pages_core(page, collect.order, MEMINIT_EARLY);179 }180}181 182static 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 << tmp.order]);196 }197 __memcpy(&collect, &tmp, sizeof(tmp));198}199 200/*201 * Memblock is about to go away. Split the page blocks left over in held_back[]202 * and return 1/3 of that memory to the system.203 */204static void kmsan_memblock_discard(void)205{206 /*207 * For each order=N:208 * - push held_back[N].shadow and .origin to @collect;209 * - while there are >= 3 elements in @collect, do garbage collection:210 * - pop 3 ranges from @collect;211 * - use two of them as shadow and origin for the third one;212 * - repeat;213 * - split each remaining element from @collect into 2 ranges of214 * 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(&collect, held_back[i].shadow);221 if (held_back[i].origin)222 smallstack_push(&collect, held_back[i].origin);223 held_back[i].shadow = NULL;224 held_back[i].origin = NULL;225 do_collection();226 collect_split();227 }228}229 230void __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 KernelMemorySanitizer\n");236 pr_info("ATTENTION: KMSAN is a debugging tool! Do not use it on production machines!\n");237 kmsan_enabled = true;238}239