From patchwork Mon Sep 11 14:56:59 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Potapenko X-Patchwork-Id: 13379413 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 717E6EE57DF for ; Mon, 11 Sep 2023 14:57:15 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CDB736B02A9; Mon, 11 Sep 2023 10:57:14 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C64976B02AA; Mon, 11 Sep 2023 10:57:14 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id B05ED6B02AB; Mon, 11 Sep 2023 10:57:14 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0013.hostedemail.com [216.40.44.13]) by kanga.kvack.org (Postfix) with ESMTP id A17136B02A9 for ; Mon, 11 Sep 2023 10:57:14 -0400 (EDT) Received: from smtpin09.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 668A6A0A54 for ; Mon, 11 Sep 2023 14:57:14 +0000 (UTC) X-FDA: 81224619588.09.C558244 Received: from mail-yw1-f202.google.com (mail-yw1-f202.google.com [209.85.128.202]) by imf26.hostedemail.com (Postfix) with ESMTP id 94C8914001E for ; Mon, 11 Sep 2023 14:57:12 +0000 (UTC) Authentication-Results: imf26.hostedemail.com; dkim=pass header.d=google.com header.s=20221208 header.b=gGQRqaYK; spf=pass (imf26.hostedemail.com: domain of 3xyr_ZAYKCEgqvsno1qyyqvo.mywvsx47-wwu5kmu.y1q@flex--glider.bounces.google.com designates 209.85.128.202 as permitted sender) smtp.mailfrom=3xyr_ZAYKCEgqvsno1qyyqvo.mywvsx47-wwu5kmu.y1q@flex--glider.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1694444232; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding:in-reply-to: references:dkim-signature; bh=6iMPMRaHZZkPt2h2lba04yggcsYBY9dzA07C/TArg4s=; b=lnOztKpcIDa0yS4tb96pqcaekqGEvwhw33+wMXD5HL/DnS3H2TsjAmHv6Bru2sJKXQFLRZ YW3YPUzi/gEAB9Ei4uoiXxjxwQIvmLyF83ULgYQGyTgBPprZjhAQKJgAoknihRk+WVS/1X f3Q68GrTRsxnMppaIuhWf28MbQ5ZqX4= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1694444232; a=rsa-sha256; cv=none; b=0KiD1A5IvKQAB3d5qrmGeRg+82CIL8FU9eQ0n9UZwFpEazSuhIxQ0oK/MJoDkKfuxIdx0r RnX+seHfDzzLwCGSnPujzdRuIA2/C3gRtFjkohF/a+mHTb6sklzGaZFxWdFrCtGC2pUNb9 UjOgrLTZeWFzThflBoO0g4xaEbeAcTs= ARC-Authentication-Results: i=1; imf26.hostedemail.com; dkim=pass header.d=google.com header.s=20221208 header.b=gGQRqaYK; spf=pass (imf26.hostedemail.com: domain of 3xyr_ZAYKCEgqvsno1qyyqvo.mywvsx47-wwu5kmu.y1q@flex--glider.bounces.google.com designates 209.85.128.202 as permitted sender) smtp.mailfrom=3xyr_ZAYKCEgqvsno1qyyqvo.mywvsx47-wwu5kmu.y1q@flex--glider.bounces.google.com; dmarc=pass (policy=reject) header.from=google.com Received: by mail-yw1-f202.google.com with SMTP id 00721157ae682-59b6083fa00so30376937b3.0 for ; Mon, 11 Sep 2023 07:57:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1694444231; x=1695049031; darn=kvack.org; h=cc:to:from:subject:message-id:mime-version:date:from:to:cc:subject :date:message-id:reply-to; bh=6iMPMRaHZZkPt2h2lba04yggcsYBY9dzA07C/TArg4s=; b=gGQRqaYKr2pa+AgHbvzMYNMh8mqdPqkQy/oN9hMNmrTGmsD4KS0cYXJjN64azQ9r9m nbYyMV7Y20Cwr27rgrZsRbeYwb0zV8K+Qk2ydGV7neonglviMrDR7YucpOijvZILh5gK e1REU3+tFpVLTOhZWsdVo89SdwIaTnBdvtV+AP+Fk85o4jzFZBk8wvEZYWgLiWSM64zV mo/027DFTPU+s292AyArOZc5iuH5I5O4mtMrnvi+Yer+SAkf8Swgr5tBbJbya+O9sjGQ DsresuO32J+7kesZwAApBPfisbc8PBkdkbvsVXYA2DRSYjrPG9yb9I1na4Qb9Rfy6ntt g1GQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1694444231; x=1695049031; h=cc:to:from:subject:message-id:mime-version:date:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=6iMPMRaHZZkPt2h2lba04yggcsYBY9dzA07C/TArg4s=; b=HaMymYuAq86XKIuwiY5cStSiNKClvEnzEvAVI2F2Swi2UFDHFeUYkL/6/xO241UGWE PsPxrgk88QDKVqdb87+u/JTr8XFx1lHN2YaGWIafwKECuOf5fF6yvLacB+EyO/oY4bGJ 9wDfpk9vu07L8/1QW10EgEgz5nmO1STVZ4r0HrV6Ws4eatouD2zg+6h4XsbBIF9vsRG6 l3/Lj5f4XKzGhB5atltlPN2yvn84BMKjKCxfj/hd2TE3uBbHVPXslBYfVQTLcByTB5to Ok+c+SOOl9W6TX5F2k/P2yCVhuyPSHoaoUeEBlOcTzfYiAMvL716VPF+mPzEq1wEjqB/ HWlw== X-Gm-Message-State: AOJu0YxN4K4qq0lGrxapaOsqxtLxwIKJF8EOeVk39vvazihGy0zSJc17 cG9K2wTshe5uXKNRj2dlUm7cxNwuj6g= X-Google-Smtp-Source: AGHT+IEE/n86D7W4BtYVWvhxMGGLZDAbWRkUH6Etb6BUe2tQGb6wjCu5rOgyHRKUX+nMOOSbojbh9HnT304= X-Received: from glider.muc.corp.google.com ([2a00:79e0:9c:201:62e7:6658:cb4:b858]) (user=glider job=sendgmr) by 2002:a81:b706:0:b0:58c:74ec:339b with SMTP id v6-20020a81b706000000b0058c74ec339bmr231210ywh.1.1694444231601; Mon, 11 Sep 2023 07:57:11 -0700 (PDT) Date: Mon, 11 Sep 2023 16:56:59 +0200 Mime-Version: 1.0 X-Mailer: git-send-email 2.42.0.283.g2d96d420d3-goog Message-ID: <20230911145702.2663753-1-glider@google.com> Subject: [PATCH v2 1/4] kmsan: simplify kmsan_internal_memmove_metadata() From: Alexander Potapenko To: glider@google.com, dvyukov@google.com, elver@google.com, akpm@linux-foundation.org, linux-mm@kvack.org Cc: linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com X-Rspamd-Queue-Id: 94C8914001E X-Rspam-User: X-Stat-Signature: x1mh6zmrfgnuj81g1wzisrsmntkq1er7 X-Rspamd-Server: rspam03 X-HE-Tag: 1694444232-669734 X-HE-Meta: U2FsdGVkX1+BDTXckqljSPqPxhCpJWz78ZfQeiNLeby2MZKSCKcfxtCCYWtcF5O8gno+0GVnKu4YKyQN1CUUE3zEanNfJ3FkD1GooPmBMgRgc0A7RSZKQ/kRCxF9vwbjzdFnHg42tLOyxvRNHXet/RUhp2vujRE4amKM+6MJi9JR0/T9+nk37tuZ992fmSn6PS9usu+Quu7pwpc3i9ecNs2h5896BKEz9hC1EsQk9HaW/z+hlMaexCihx6t4aRQIfGBBFiJO0aHz3KzULMFeSKZplVnB7yD36PkSMrxKHd4WfA21shPAweoZunLlqpFntKMsEdBPxC7PCY+AtsGJObvb4NcsU37JZWS4CUHnseUbEvD2/hDfCfTchHWCFYIz8gZnMrsb+X+85VrKCvcQe378SEKoQSqh48cyZYzCFJd0MBQo+7jYrAk8414jKtjwOI6LZl38Ms8O3yrkmOEZLVwalnoDeeJcMXKimN01DyQFBg8bihrYM6R+NB5JliOaUoAOTBuqlqhtgDD7YK7hdL4Sv55pIuig6zIzS3jRFt5HlFprmJlRByDmbiuucSFJpP9aswY0r7hOhiA+J+OmDCNJgP8nU6rQiFrD1vt9ZIvtdOrKOyoAU5o9NNBGdQB7fNXF2LE+VrUGr4b+8ulsHnsW2r8B02VnJww/IVpYSbrqW6ZjO4rkVtU9glcIOxie+VbP2DvSddweG81kFRooDbnNDUZ2HK5hO6jEKKWcEuzKWKfqSIUyx94ewPzWr+viEXByDZqZa7+/jqVA8khkAmp1xDL+1wuGN1OCGfy+yxcqyMD2Ogs0S924bJUY6pqyxLdwBRBs1+HpnRnVVQYcmNjFEgBXmL7AmEfkayvrKFxkOP5qSe8pS8bJjqdS+79ntPdXKCz3WFSDrEa8AwTOJQpkynEM96M38ZIbRKM6/HaiYklRYa8f/f3/yfdtoWstISzjvbbHvVfnF2QNi00 syZI++xT zYbJuRV4Drc9eIOXfXXMiIpaaJxBjhO6a4ZgNsTSnHwuLfugZwHctVfVwJiqRfT5mEUifBGZGzqS3K0Ai7/J/7RBsOBsH/tXXf7DQ6W66L1kN7aciCD4EGELImqqG0KMg14Hh0Wi4ZmAwWpiuHb9XE8Tw/oZQsZu+uADX3U/glOzWjmFYDFDGMhBC3nxDydcJwA6c7/C6P35v83zxBrKbrOD//AHv5VNavuiOfkO1Zv3kjY14h5pLpbTKJXKnSr3AbSGp+0nirdiBsUWX4zEWrsVadD1FxSrbFqxOVW9irS5sENpjyDTbLHFQMMqdshIpVZyyUugN0HdwYm+owvW2TcJ8V14UO9BvfSOMLnCDh4tD/QsPp6tpE5ydJ9R3017L1tW74t1UpO6TyAYd9o17oXO/40Eh6oJhs4sik6q7br7zBrIsQkbDghtu8oUidgRT/8QYuFsf20OptglRTjinPS1Q8adQAlMacvY5+s4asi1TXG2nYUPD56fxyREG7c+ZWsVEVRpDFWEDgRbX3PXdkwt1/KWuQwz+HstIKhZf6PaFVWxAWgQEmZZJ4LnztiEciOuubSvGu/e2lUnZ1pUw6r/bXZCQYMxoJ1DUCwAjFg2MyzUiG34UXRZer+ueoXuMURouKP+tkm+4msy9eipSZiKR4g== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: kmsan_internal_memmove_metadata() is the function that implements copying metadata every time memcpy()/memmove() is called. Because shadow memory stores 1 byte per each byte of kernel memory, copying the shadow is trivial and can be done by a single memmove() call. Origins, on the other hand, are stored as 4-byte values corresponding to every aligned 4 bytes of kernel memory. Therefore, if either the source or the destination of kmsan_internal_memmove_metadata() is unaligned, the number of origin slots corresponding to the source or destination may differ: 1) memcpy(0xffff888080a00000, 0xffff888080900000, 4) copies 1 origin slot into 1 origin slot: src (0xffff888080900000): xxxx src origins: o111 dst (0xffff888080a00000): xxxx dst origins: o111 2) memcpy(0xffff888080a00001, 0xffff888080900000, 4) copies 1 origin slot into 2 origin slots: src (0xffff888080900000): xxxx src origins: o111 dst (0xffff888080a00000): .xxx x... dst origins: o111 o111 3) memcpy(0xffff888080a00000, 0xffff888080900001, 4) copies 2 origin slots into 1 origin slot: src (0xffff888080900000): .xxx x... src origins: o111 o222 dst (0xffff888080a00000): xxxx dst origins: o111 (or o222) Previously, kmsan_internal_memmove_metadata() tried to solve this problem by copying min(src_slots, dst_slots) as is and cloning the missing slot on one of the ends, if needed. This was error-prone even in the simple cases where 4 bytes were copied, and did not account for situations where the total number of nonzero origin slots could have increased by more than one after copying: memcpy(0xffff888080a00000, 0xffff888080900002, 8) src (0xffff888080900002): ..xx .... xx.. src origins: o111 0000 o222 dst (0xffff888080a00000): xx.. ..xx o111 0000 (or 0000 o222) The new implementation simply copies the shadow byte by byte, and updates the corresponding origin slot, if the shadow byte is nonzero. This approach can handle complex cases with mixed initialized and uninitialized bytes. Similarly to KMSAN inline instrumentation, latter writes to bytes sharing the same origin slots take precedence. Signed-off-by: Alexander Potapenko Fixes: f80be4571b19 ("kmsan: add KMSAN runtime core") Acked-by: Marco Elver --- mm/kmsan/core.c | 127 ++++++++++++------------------------------------ 1 file changed, 31 insertions(+), 96 deletions(-) diff --git a/mm/kmsan/core.c b/mm/kmsan/core.c index 3adb4c1d3b193..c19f47af04241 100644 --- a/mm/kmsan/core.c +++ b/mm/kmsan/core.c @@ -83,131 +83,66 @@ depot_stack_handle_t kmsan_save_stack_with_flags(gfp_t flags, /* Copy the metadata following the memmove() behavior. */ void kmsan_internal_memmove_metadata(void *dst, void *src, size_t n) { + depot_stack_handle_t prev_old_origin = 0, prev_new_origin = 0; + int i, iter, step, src_off, dst_off, oiter_src, oiter_dst; depot_stack_handle_t old_origin = 0, new_origin = 0; - int src_slots, dst_slots, i, iter, step, skip_bits; depot_stack_handle_t *origin_src, *origin_dst; - void *shadow_src, *shadow_dst; - u32 *align_shadow_src, shadow; + u8 *shadow_src, *shadow_dst; + u32 *align_shadow_dst; bool backwards; shadow_dst = kmsan_get_metadata(dst, KMSAN_META_SHADOW); if (!shadow_dst) return; KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(dst, n)); + align_shadow_dst = + (u32 *)ALIGN_DOWN((u64)shadow_dst, KMSAN_ORIGIN_SIZE); shadow_src = kmsan_get_metadata(src, KMSAN_META_SHADOW); if (!shadow_src) { - /* - * @src is untracked: zero out destination shadow, ignore the - * origins, we're done. - */ - __memset(shadow_dst, 0, n); + /* @src is untracked: mark @dst as initialized. */ + kmsan_internal_unpoison_memory(dst, n, /*checked*/ false); return; } KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(src, n)); - __memmove(shadow_dst, shadow_src, n); - origin_dst = kmsan_get_metadata(dst, KMSAN_META_ORIGIN); origin_src = kmsan_get_metadata(src, KMSAN_META_ORIGIN); KMSAN_WARN_ON(!origin_dst || !origin_src); - src_slots = (ALIGN((u64)src + n, KMSAN_ORIGIN_SIZE) - - ALIGN_DOWN((u64)src, KMSAN_ORIGIN_SIZE)) / - KMSAN_ORIGIN_SIZE; - dst_slots = (ALIGN((u64)dst + n, KMSAN_ORIGIN_SIZE) - - ALIGN_DOWN((u64)dst, KMSAN_ORIGIN_SIZE)) / - KMSAN_ORIGIN_SIZE; - KMSAN_WARN_ON((src_slots < 1) || (dst_slots < 1)); - KMSAN_WARN_ON((src_slots - dst_slots > 1) || - (dst_slots - src_slots < -1)); backwards = dst > src; - i = backwards ? min(src_slots, dst_slots) - 1 : 0; - iter = backwards ? -1 : 1; - - align_shadow_src = - (u32 *)ALIGN_DOWN((u64)shadow_src, KMSAN_ORIGIN_SIZE); - for (step = 0; step < min(src_slots, dst_slots); step++, i += iter) { - KMSAN_WARN_ON(i < 0); - shadow = align_shadow_src[i]; - if (i == 0) { - /* - * If @src isn't aligned on KMSAN_ORIGIN_SIZE, don't - * look at the first @src % KMSAN_ORIGIN_SIZE bytes - * of the first shadow slot. - */ - skip_bits = ((u64)src % KMSAN_ORIGIN_SIZE) * 8; - shadow = (shadow >> skip_bits) << skip_bits; + step = backwards ? -1 : 1; + iter = backwards ? n - 1 : 0; + src_off = (u64)src % KMSAN_ORIGIN_SIZE; + dst_off = (u64)dst % KMSAN_ORIGIN_SIZE; + + /* Copy shadow bytes one by one, updating the origins if necessary. */ + for (i = 0; i < n; i++, iter += step) { + oiter_src = (iter + src_off) / KMSAN_ORIGIN_SIZE; + oiter_dst = (iter + dst_off) / KMSAN_ORIGIN_SIZE; + if (!shadow_src[iter]) { + shadow_dst[iter] = 0; + if (!align_shadow_dst[oiter_dst]) + origin_dst[oiter_dst] = 0; + continue; } - if (i == src_slots - 1) { - /* - * If @src + n isn't aligned on - * KMSAN_ORIGIN_SIZE, don't look at the last - * (@src + n) % KMSAN_ORIGIN_SIZE bytes of the - * last shadow slot. - */ - skip_bits = (((u64)src + n) % KMSAN_ORIGIN_SIZE) * 8; - shadow = (shadow << skip_bits) >> skip_bits; - } - /* - * Overwrite the origin only if the corresponding - * shadow is nonempty. - */ - if (origin_src[i] && (origin_src[i] != old_origin) && shadow) { - old_origin = origin_src[i]; - new_origin = kmsan_internal_chain_origin(old_origin); + shadow_dst[iter] = shadow_src[iter]; + old_origin = origin_src[oiter_src]; + if (old_origin == prev_old_origin) + new_origin = prev_new_origin; + else { /* * kmsan_internal_chain_origin() may return * NULL, but we don't want to lose the previous * origin value. */ + new_origin = kmsan_internal_chain_origin(old_origin); if (!new_origin) new_origin = old_origin; } - if (shadow) - origin_dst[i] = new_origin; - else - origin_dst[i] = 0; - } - /* - * If dst_slots is greater than src_slots (i.e. - * dst_slots == src_slots + 1), there is an extra origin slot at the - * beginning or end of the destination buffer, for which we take the - * origin from the previous slot. - * This is only done if the part of the source shadow corresponding to - * slot is non-zero. - * - * E.g. if we copy 8 aligned bytes that are marked as uninitialized - * and have origins o111 and o222, to an unaligned buffer with offset 1, - * these two origins are copied to three origin slots, so one of then - * needs to be duplicated, depending on the copy direction (@backwards) - * - * src shadow: |uuuu|uuuu|....| - * src origin: |o111|o222|....| - * - * backwards = 0: - * dst shadow: |.uuu|uuuu|u...| - * dst origin: |....|o111|o222| - fill the empty slot with o111 - * backwards = 1: - * dst shadow: |.uuu|uuuu|u...| - * dst origin: |o111|o222|....| - fill the empty slot with o222 - */ - if (src_slots < dst_slots) { - if (backwards) { - shadow = align_shadow_src[src_slots - 1]; - skip_bits = (((u64)dst + n) % KMSAN_ORIGIN_SIZE) * 8; - shadow = (shadow << skip_bits) >> skip_bits; - if (shadow) - /* src_slots > 0, therefore dst_slots is at least 2 */ - origin_dst[dst_slots - 1] = - origin_dst[dst_slots - 2]; - } else { - shadow = align_shadow_src[0]; - skip_bits = ((u64)dst % KMSAN_ORIGIN_SIZE) * 8; - shadow = (shadow >> skip_bits) << skip_bits; - if (shadow) - origin_dst[0] = origin_dst[1]; - } + origin_dst[oiter_dst] = new_origin; + prev_new_origin = new_origin; + prev_old_origin = old_origin; } }