mm/kmsan/core.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * KMSAN runtime library.
   4  *
   5  * Copyright (C) 2017-2022 Google LLC
   6  * Author: Alexander Potapenko <glider@google.com>
   7  *
   8  */
   9
  10 #include <asm/page.h>
  11 #include <linux/compiler.h>
  12 #include <linux/export.h>
  13 #include <linux/highmem.h>
  14 #include <linux/interrupt.h>
  15 #include <linux/kernel.h>
  16 #include <linux/kmsan_types.h>
  17 #include <linux/memory.h>
  18 #include <linux/mm.h>
  19 #include <linux/mm_types.h>
  20 #include <linux/mmzone.h>
  21 #include <linux/percpu-defs.h>
  22 #include <linux/preempt.h>
  23 #include <linux/slab.h>
  24 #include <linux/stackdepot.h>
  25 #include <linux/stacktrace.h>
  26 #include <linux/types.h>
  27 #include <linux/vmalloc.h>
  28
  29 #include "../slab.h"
  30 #include "kmsan.h"
  31
  32 bool kmsan_enabled __read_mostly;
  33
  34 /*
  35  * Per-CPU KMSAN context to be used in interrupts, where current->kmsan is
  36  * unavaliable.
  37  */
  38 DEFINE_PER_CPU(struct kmsan_ctx, kmsan_percpu_ctx);
  39
  40 void kmsan_internal_task_create(struct task_struct *task)
  41 {
  42         struct kmsan_ctx *ctx = &task->kmsan_ctx;
  43         struct thread_info *info = current_thread_info();
  44
  45         __memset(ctx, 0, sizeof(*ctx));
  46         ctx->allow_reporting = true;
  47         kmsan_internal_unpoison_memory(info, sizeof(*info), false);
  48 }
  49
  50 void kmsan_internal_poison_memory(void *address, size_t size, gfp_t flags,
  51                                   unsigned int poison_flags)
  52 {
  53         u32 extra_bits =
  54                 kmsan_extra_bits(/*depth*/ 0, poison_flags & KMSAN_POISON_FREE);
  55         bool checked = poison_flags & KMSAN_POISON_CHECK;
  56         depot_stack_handle_t handle;
  57
  58         handle = kmsan_save_stack_with_flags(flags, extra_bits);
  59         kmsan_internal_set_shadow_origin(address, size, -1, handle, checked);
  60 }
  61
  62 void kmsan_internal_unpoison_memory(void *address, size_t size, bool checked)
  63 {
  64         kmsan_internal_set_shadow_origin(address, size, 0, 0, checked);
  65 }
  66
  67 depot_stack_handle_t kmsan_save_stack_with_flags(gfp_t flags,
  68                                                  unsigned int extra)
  69 {
  70         unsigned long entries[KMSAN_STACK_DEPTH];
  71         unsigned int nr_entries;
  72         depot_stack_handle_t handle;
  73
  74         nr_entries = stack_trace_save(entries, KMSAN_STACK_DEPTH, 0);
  75
  76         /* Don't sleep. */
  77         flags &= ~__GFP_DIRECT_RECLAIM;
  78
  79         handle = __stack_depot_save(entries, nr_entries, flags, true);
  80         return stack_depot_set_extra_bits(handle, extra);
  81 }
  82
  83 /* Copy the metadata following the memmove() behavior. */
  84 void kmsan_internal_memmove_metadata(void *dst, void *src, size_t n)
  85 {
  86         depot_stack_handle_t old_origin = 0, new_origin = 0;
  87         int src_slots, dst_slots, i, iter, step, skip_bits;
  88         depot_stack_handle_t *origin_src, *origin_dst;
  89         void *shadow_src, *shadow_dst;
  90         u32 *align_shadow_src, shadow;
  91         bool backwards;
  92
  93         shadow_dst = kmsan_get_metadata(dst, KMSAN_META_SHADOW);
  94         if (!shadow_dst)
  95                 return;
  96         KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(dst, n));
  97
  98         shadow_src = kmsan_get_metadata(src, KMSAN_META_SHADOW);
  99         if (!shadow_src) {
 100                 /*
 101                  * @src is untracked: zero out destination shadow, ignore the
 102                  * origins, we're done.
 103                  */
 104                 __memset(shadow_dst, 0, n);
 105                 return;
 106         }
 107         KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(src, n));
 108
 109         __memmove(shadow_dst, shadow_src, n);
 110
 111         origin_dst = kmsan_get_metadata(dst, KMSAN_META_ORIGIN);
 112         origin_src = kmsan_get_metadata(src, KMSAN_META_ORIGIN);
 113         KMSAN_WARN_ON(!origin_dst || !origin_src);
 114         src_slots = (ALIGN((u64)src + n, KMSAN_ORIGIN_SIZE) -
 115                      ALIGN_DOWN((u64)src, KMSAN_ORIGIN_SIZE)) /
 116                     KMSAN_ORIGIN_SIZE;
 117         dst_slots = (ALIGN((u64)dst + n, KMSAN_ORIGIN_SIZE) -
 118                      ALIGN_DOWN((u64)dst, KMSAN_ORIGIN_SIZE)) /
 119                     KMSAN_ORIGIN_SIZE;
 120         KMSAN_WARN_ON((src_slots < 1) || (dst_slots < 1));
 121         KMSAN_WARN_ON((src_slots - dst_slots > 1) ||
 122                       (dst_slots - src_slots < -1));
 123
 124         backwards = dst > src;
 125         i = backwards ? min(src_slots, dst_slots) - 1 : 0;
 126         iter = backwards ? -1 : 1;
 127
 128         align_shadow_src =
 129                 (u32 *)ALIGN_DOWN((u64)shadow_src, KMSAN_ORIGIN_SIZE);
 130         for (step = 0; step < min(src_slots, dst_slots); step++, i += iter) {
 131                 KMSAN_WARN_ON(i < 0);
 132                 shadow = align_shadow_src[i];
 133                 if (i == 0) {
 134                         /*
 135                          * If @src isn't aligned on KMSAN_ORIGIN_SIZE, don't
 136                          * look at the first @src % KMSAN_ORIGIN_SIZE bytes
 137                          * of the first shadow slot.
 138                          */
 139                         skip_bits = ((u64)src % KMSAN_ORIGIN_SIZE) * 8;
 140                         shadow = (shadow >> skip_bits) << skip_bits;
 141                 }
 142                 if (i == src_slots - 1) {
 143                         /*
 144                          * If @src + n isn't aligned on
 145                          * KMSAN_ORIGIN_SIZE, don't look at the last
 146                          * (@src + n) % KMSAN_ORIGIN_SIZE bytes of the
 147                          * last shadow slot.
 148                          */
 149                         skip_bits = (((u64)src + n) % KMSAN_ORIGIN_SIZE) * 8;
 150                         shadow = (shadow << skip_bits) >> skip_bits;
 151                 }
 152                 /*
 153                  * Overwrite the origin only if the corresponding
 154                  * shadow is nonempty.
 155                  */
 156                 if (origin_src[i] && (origin_src[i] != old_origin) && shadow) {
 157                         old_origin = origin_src[i];
 158                         new_origin = kmsan_internal_chain_origin(old_origin);
 159                         /*
 160                          * kmsan_internal_chain_origin() may return
 161                          * NULL, but we don't want to lose the previous
 162                          * origin value.
 163                          */
 164                         if (!new_origin)
 165                                 new_origin = old_origin;
 166                 }
 167                 if (shadow)
 168                         origin_dst[i] = new_origin;
 169                 else
 170                         origin_dst[i] = 0;
 171         }
 172         /*
 173          * If dst_slots is greater than src_slots (i.e.
 174          * dst_slots == src_slots + 1), there is an extra origin slot at the
 175          * beginning or end of the destination buffer, for which we take the
 176          * origin from the previous slot.
 177          * This is only done if the part of the source shadow corresponding to
 178          * slot is non-zero.
 179          *
 180          * E.g. if we copy 8 aligned bytes that are marked as uninitialized
 181          * and have origins o111 and o222, to an unaligned buffer with offset 1,
 182          * these two origins are copied to three origin slots, so one of then
 183          * needs to be duplicated, depending on the copy direction (@backwards)
 184          *
 185          *   src shadow: |uuuu|uuuu|....|
 186          *   src origin: |o111|o222|....|
 187          *
 188          * backwards = 0:
 189          *   dst shadow: |.uuu|uuuu|u...|
 190          *   dst origin: |....|o111|o222| - fill the empty slot with o111
 191          * backwards = 1:
 192          *   dst shadow: |.uuu|uuuu|u...|
 193          *   dst origin: |o111|o222|....| - fill the empty slot with o222
 194          */
 195         if (src_slots < dst_slots) {
 196                 if (backwards) {
 197                         shadow = align_shadow_src[src_slots - 1];
 198                         skip_bits = (((u64)dst + n) % KMSAN_ORIGIN_SIZE) * 8;
 199                         shadow = (shadow << skip_bits) >> skip_bits;
 200                         if (shadow)
 201                                 /* src_slots > 0, therefore dst_slots is at least 2 */
 202                                 origin_dst[dst_slots - 1] =
 203                                         origin_dst[dst_slots - 2];
 204                 } else {
 205                         shadow = align_shadow_src[0];
 206                         skip_bits = ((u64)dst % KMSAN_ORIGIN_SIZE) * 8;
 207                         shadow = (shadow >> skip_bits) << skip_bits;
 208                         if (shadow)
 209                                 origin_dst[0] = origin_dst[1];
 210                 }
 211         }
 212 }
 213
 214 depot_stack_handle_t kmsan_internal_chain_origin(depot_stack_handle_t id)
 215 {
 216         unsigned long entries[3];
 217         u32 extra_bits;
 218         int depth;
 219         bool uaf;
 220         depot_stack_handle_t handle;
 221
 222         if (!id)
 223                 return id;
 224         /*
 225          * Make sure we have enough spare bits in @id to hold the UAF bit and
 226          * the chain depth.
 227          */
 228         BUILD_BUG_ON(
 229                 (1 << STACK_DEPOT_EXTRA_BITS) <= (KMSAN_MAX_ORIGIN_DEPTH << 1));
 230
 231         extra_bits = stack_depot_get_extra_bits(id);
 232         depth = kmsan_depth_from_eb(extra_bits);
 233         uaf = kmsan_uaf_from_eb(extra_bits);
 234
 235         /*
 236          * Stop chaining origins once the depth reached KMSAN_MAX_ORIGIN_DEPTH.
 237          * This mostly happens in the case structures with uninitialized padding
 238          * are copied around many times. Origin chains for such structures are
 239          * usually periodic, and it does not make sense to fully store them.
 240          */
 241         if (depth == KMSAN_MAX_ORIGIN_DEPTH)
 242                 return id;
 243
 244         depth++;
 245         extra_bits = kmsan_extra_bits(depth, uaf);
 246
 247         entries[0] = KMSAN_CHAIN_MAGIC_ORIGIN;
 248         entries[1] = kmsan_save_stack_with_flags(GFP_ATOMIC, 0);
 249         entries[2] = id;
 250         /*
 251          * @entries is a local var in non-instrumented code, so KMSAN does not
 252          * know it is initialized. Explicitly unpoison it to avoid false
 253          * positives when __stack_depot_save() passes it to instrumented code.
 254          */
 255         kmsan_internal_unpoison_memory(entries, sizeof(entries), false);
 256         handle = __stack_depot_save(entries, ARRAY_SIZE(entries), GFP_ATOMIC,
 257                                     true);
 258         return stack_depot_set_extra_bits(handle, extra_bits);
 259 }
 260
 261 void kmsan_internal_set_shadow_origin(void *addr, size_t size, int b,
 262                                       u32 origin, bool checked)
 263 {
 264         u64 address = (u64)addr;
 265         void *shadow_start;
 266         u32 *origin_start;
 267         size_t pad = 0;
 268
 269         KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size));
 270         shadow_start = kmsan_get_metadata(addr, KMSAN_META_SHADOW);
 271         if (!shadow_start) {
 272                 /*
 273                  * kmsan_metadata_is_contiguous() is true, so either all shadow
 274                  * and origin pages are NULL, or all are non-NULL.
 275                  */
 276                 if (checked) {
 277                         pr_err("%s: not memsetting %ld bytes starting at %px, because the shadow is NULL\n",
 278                                __func__, size, addr);
 279                         KMSAN_WARN_ON(true);
 280                 }
 281                 return;
 282         }
 283         __memset(shadow_start, b, size);
 284
 285         if (!IS_ALIGNED(address, KMSAN_ORIGIN_SIZE)) {
 286                 pad = address % KMSAN_ORIGIN_SIZE;
 287                 address -= pad;
 288                 size += pad;
 289         }
 290         size = ALIGN(size, KMSAN_ORIGIN_SIZE);
 291         origin_start =
 292                 (u32 *)kmsan_get_metadata((void *)address, KMSAN_META_ORIGIN);
 293
 294         for (int i = 0; i < size / KMSAN_ORIGIN_SIZE; i++)
 295                 origin_start[i] = origin;
 296 }
 297
 298 struct page *kmsan_vmalloc_to_page_or_null(void *vaddr)
 299 {
 300         struct page *page;
 301
 302         if (!kmsan_internal_is_vmalloc_addr(vaddr) &&
 303             !kmsan_internal_is_module_addr(vaddr))
 304                 return NULL;
 305         page = vmalloc_to_page(vaddr);
 306         if (pfn_valid(page_to_pfn(page)))
 307                 return page;
 308         else
 309                 return NULL;
 310 }
 311
 312 void kmsan_internal_check_memory(void *addr, size_t size, const void *user_addr,
 313                                  int reason)
 314 {
 315         depot_stack_handle_t cur_origin = 0, new_origin = 0;
 316         unsigned long addr64 = (unsigned long)addr;
 317         depot_stack_handle_t *origin = NULL;
 318         unsigned char *shadow = NULL;
 319         int cur_off_start = -1;
 320         int chunk_size;
 321         size_t pos = 0;
 322
 323         if (!size)
 324                 return;
 325         KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size));
 326         while (pos < size) {
 327                 chunk_size = min(size - pos,
 328                                  PAGE_SIZE - ((addr64 + pos) % PAGE_SIZE));
 329                 shadow = kmsan_get_metadata((void *)(addr64 + pos),
 330                                             KMSAN_META_SHADOW);
 331                 if (!shadow) {
 332                         /*
 333                          * This page is untracked. If there were uninitialized
 334                          * bytes before, report them.
 335                          */
 336                         if (cur_origin) {
 337                                 kmsan_enter_runtime();
 338                                 kmsan_report(cur_origin, addr, size,
 339                                              cur_off_start, pos - 1, user_addr,
 340                                              reason);
 341                                 kmsan_leave_runtime();
 342                         }
 343                         cur_origin = 0;
 344                         cur_off_start = -1;
 345                         pos += chunk_size;
 346                         continue;
 347                 }
 348                 for (int i = 0; i < chunk_size; i++) {
 349                         if (!shadow[i]) {
 350                                 /*
 351                                  * This byte is unpoisoned. If there were
 352                                  * poisoned bytes before, report them.
 353                                  */
 354                                 if (cur_origin) {
 355                                         kmsan_enter_runtime();
 356                                         kmsan_report(cur_origin, addr, size,
 357                                                      cur_off_start, pos + i - 1,
 358                                                      user_addr, reason);
 359                                         kmsan_leave_runtime();
 360                                 }
 361                                 cur_origin = 0;
 362                                 cur_off_start = -1;
 363                                 continue;
 364                         }
 365                         origin = kmsan_get_metadata((void *)(addr64 + pos + i),
 366                                                     KMSAN_META_ORIGIN);
 367                         KMSAN_WARN_ON(!origin);
 368                         new_origin = *origin;
 369                         /*
 370                          * Encountered new origin - report the previous
 371                          * uninitialized range.
 372                          */
 373                         if (cur_origin != new_origin) {
 374                                 if (cur_origin) {
 375                                         kmsan_enter_runtime();
 376                                         kmsan_report(cur_origin, addr, size,
 377                                                      cur_off_start, pos + i - 1,
 378                                                      user_addr, reason);
 379                                         kmsan_leave_runtime();
 380                                 }
 381                                 cur_origin = new_origin;
 382                                 cur_off_start = pos + i;
 383                         }
 384                 }
 385                 pos += chunk_size;
 386         }
 387         KMSAN_WARN_ON(pos != size);
 388         if (cur_origin) {
 389                 kmsan_enter_runtime();
 390                 kmsan_report(cur_origin, addr, size, cur_off_start, pos - 1,
 391                              user_addr, reason);
 392                 kmsan_leave_runtime();
 393         }
 394 }
 395
 396 bool kmsan_metadata_is_contiguous(void *addr, size_t size)
 397 {
 398         char *cur_shadow = NULL, *next_shadow = NULL, *cur_origin = NULL,
 399              *next_origin = NULL;
 400         u64 cur_addr = (u64)addr, next_addr = cur_addr + PAGE_SIZE;
 401         depot_stack_handle_t *origin_p;
 402         bool all_untracked = false;
 403
 404         if (!size)
 405                 return true;
 406
 407         /* The whole range belongs to the same page. */
 408         if (ALIGN_DOWN(cur_addr + size - 1, PAGE_SIZE) ==
 409             ALIGN_DOWN(cur_addr, PAGE_SIZE))
 410                 return true;
 411
 412         cur_shadow = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ false);
 413         if (!cur_shadow)
 414                 all_untracked = true;
 415         cur_origin = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ true);
 416         if (all_untracked && cur_origin)
 417                 goto report;
 418
 419         for (; next_addr < (u64)addr + size;
 420              cur_addr = next_addr, cur_shadow = next_shadow,
 421              cur_origin = next_origin, next_addr += PAGE_SIZE) {
 422                 next_shadow = kmsan_get_metadata((void *)next_addr, false);
 423                 next_origin = kmsan_get_metadata((void *)next_addr, true);
 424                 if (all_untracked) {
 425                         if (next_shadow || next_origin)
 426                                 goto report;
 427                         if (!next_shadow && !next_origin)
 428                                 continue;
 429                 }
 430                 if (((u64)cur_shadow == ((u64)next_shadow - PAGE_SIZE)) &&
 431                     ((u64)cur_origin == ((u64)next_origin - PAGE_SIZE)))
 432                         continue;
 433                 goto report;
 434         }
 435         return true;
 436
 437 report:
 438         pr_err("%s: attempting to access two shadow page ranges.\n", __func__);
 439         pr_err("Access of size %ld at %px.\n", size, addr);
 440         pr_err("Addresses belonging to different ranges: %px and %px\n",
 441                (void *)cur_addr, (void *)next_addr);
 442         pr_err("page[0].shadow: %px, page[1].shadow: %px\n", cur_shadow,
 443                next_shadow);
 444         pr_err("page[0].origin: %px, page[1].origin: %px\n", cur_origin,
 445                next_origin);
 446         origin_p = kmsan_get_metadata(addr, KMSAN_META_ORIGIN);
 447         if (origin_p) {
 448                 pr_err("Origin: %08x\n", *origin_p);
 449                 kmsan_print_origin(*origin_p);
 450         } else {
 451                 pr_err("Origin: unavailable\n");
 452         }
 453         return false;
 454 }