From mboxrd@z Thu Jan 1 00:00:00 1970 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 8C909EE7FF4 for ; Mon, 11 Sep 2023 11:44:04 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id E24526B027F; Mon, 11 Sep 2023 07:44:03 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id DD35F6B0280; Mon, 11 Sep 2023 07:44:03 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C9D2A6B0281; Mon, 11 Sep 2023 07:44:03 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id B8A226B027F for ; Mon, 11 Sep 2023 07:44:03 -0400 (EDT) Received: from smtpin30.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay03.hostedemail.com (Postfix) with ESMTP id 928E0A09B7 for ; Mon, 11 Sep 2023 11:44:03 +0000 (UTC) X-FDA: 81224132766.30.AA47ABD Received: from mail-wm1-f52.google.com (mail-wm1-f52.google.com [209.85.128.52]) by imf15.hostedemail.com (Postfix) with ESMTP id CAECFA0037 for ; Mon, 11 Sep 2023 11:44:01 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=google.com header.s=20221208 header.b=giLLPGqW; spf=pass (imf15.hostedemail.com: domain of elver@google.com designates 209.85.128.52 as permitted sender) smtp.mailfrom=elver@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=1694432641; 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:in-reply-to:references:references:dkim-signature; bh=FdxNots/ZdhIISnEaFRRuK2rgiRRh92V2Io2TUdmEu4=; b=EiFOQoDhp4Pm4bgmS0RwsY9pzrfffz3YzqeYSD9iBx7vVANiaAycns+Ko0IpJKyailbDvC ZCROSgBv0nf9oxneeyKOgW3Vv+DC1GxNnC55doTr70gXMkztHpcNn4AW0Dg7QxWNF2W31a r7t3K7KFwbBRLc92g8JTd10cGXQw8Pk= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1694432641; a=rsa-sha256; cv=none; b=AM/sy44dBU72/959RcX9DmRrx5X7C/RP+alInykzxJJkDo5kcfX0JPC/iKchrHa1C7SBpX qZsL4MMxMJtccZYS2TojI0FoCkHslLfqM8qtpO+iehiUVRg6rae4lS5bKgEij6sumrbfu/ t5LF1iuwaBJhk2Antj0L6g7xRzC5mlg= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=google.com header.s=20221208 header.b=giLLPGqW; spf=pass (imf15.hostedemail.com: domain of elver@google.com designates 209.85.128.52 as permitted sender) smtp.mailfrom=elver@google.com; dmarc=pass (policy=reject) header.from=google.com Received: by mail-wm1-f52.google.com with SMTP id 5b1f17b1804b1-401da71b83cso49297295e9.2 for ; Mon, 11 Sep 2023 04:44:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20221208; t=1694432640; x=1695037440; darn=kvack.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=FdxNots/ZdhIISnEaFRRuK2rgiRRh92V2Io2TUdmEu4=; b=giLLPGqWjXDcN+C/uxcGMGxQRplgtMZa6GG5n1wIJov4XVtEIqbV4rQ0hfnkGY9WXN Lny4+e+Q/+XWAQKbMgEoTU3ZznGOg47Wk9Lqt0L9VpcD+plTScKB610M9eMp5nwN3NuW U5lL0Q3AS1tVKEyGo1LTQ8toMKj7EEzQw7o9m2/UP8lYzwvHLMyJgDg5n1g7Cz+doyng 6zg7jjp9vbh8vg6pEIODfibI/+3pph/ylM0c23GGA0RQk/s7cihSzzToFAtH/IZNGKf9 hk/+JaJsmJbdA4+fLJF+VCjuUqiIs8b/zVfrNWJfNh/9KhWEPc8fkcVinUefqsgyfWqF ShYg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1694432640; x=1695037440; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=FdxNots/ZdhIISnEaFRRuK2rgiRRh92V2Io2TUdmEu4=; b=i1PVAt+/uzayOPmcTGUtWkxnVIxsXrQZN/FDOPEO+w6AA+loenqI2O9+OTeOF70sPd FQmWVFi2y56Yh1c7oYNr6og6uNU5/WRGwV5vroeNDhUvJCf7zqkRvxjxF/XRsLRU1G/h zomCJSL0+PXzqnbXt4DL4Da9ppierqTbkV7YsDh9vevTYG2azuJyxSL7ddgBBI7jQGqI l/A7m25FZcBP4Dxt3mM08S/qIvmpq3uFUgRARsnfYrX6KYHpUXPe0oI0mr1eaG5aFPYQ h5h5wEIsVVXROMGn3JxYPqyyOvxdI0dYflzYDfWcYlDsoCToGsoZCqScDDPHJeBNlGkE Iugw== X-Gm-Message-State: AOJu0YyEXlYXD9nP5H/1uakpjg662w956uJHEl6ta7pkiTGRCIc+QFlx 9UyDlS7rioR1OYifNkB3/LzmPb1okSnc5hh10VKeHA== X-Google-Smtp-Source: AGHT+IGODvX6beJZ5zvdfH+VxLt6+uAABmMvCiPydjYPQlmKzfiXP8yxNJSdULc9CFhOjcKGcex8m7OJN69MT8ZxIhM= X-Received: by 2002:a7b:c389:0:b0:401:d947:c8a9 with SMTP id s9-20020a7bc389000000b00401d947c8a9mr7855842wmj.19.1694432640069; Mon, 11 Sep 2023 04:44:00 -0700 (PDT) MIME-Version: 1.0 References: <20230907130642.245222-1-glider@google.com> In-Reply-To: <20230907130642.245222-1-glider@google.com> From: Marco Elver Date: Mon, 11 Sep 2023 13:43:23 +0200 Message-ID: Subject: Re: [PATCH 1/2] kmsan: simplify kmsan_internal_memmove_metadata() To: Alexander Potapenko Cc: dvyukov@google.com, akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, kasan-dev@googlegroups.com Content-Type: text/plain; charset="UTF-8" X-Stat-Signature: kqmksrqx3cpgzjmqdy89epuy4pcan1gb X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: CAECFA0037 X-Rspam-User: X-HE-Tag: 1694432641-403494 X-HE-Meta: U2FsdGVkX19qiaiJQ3iZqGsAwAA478aLq8bLq9AmylhHma0ndf6r6gboea1j5FYn4VIeeTfuDv+kw9SB7hW7XfVtLusNRoxBK4X6lvwELawxHgR4M2B3ZMDH/fWolq6iqGSHzcpFlzubH5pn8Dsj9u9n4qrzJBq4w8MYqTckZSTMTINqTDTQQGXdylIOKfFI93K3lXxFPo8iE3Id7XEapWlHThUeEh3G/tzzZZwZcsOe2Fp6vxeYvybxM3tcJht5Ap/vqw82v6+TTu/kX7YR3rnTdcuwtBXJZPYZJi5oMgAgtV3jbkUdVWdvVhfqOZ98fLI68TZ985NbH56Xi2xZmohTrAT2LQ7ZiLE082i3GPjmBOdW9j4+q1DU0J9wcfXusbJhOE9KsihqQjFYWPD7FHbIfxS8BpHfhh7hpyuPBwo6GlozCGJVMyuw3idEvhd8y45iKeoFBbdc8rMGb3vDUScv4HacKJG9H66BZIRdtcJcAhzUhr8iNZ5b3ZuHbXr9HrwZjen6VdzAOZ7TBOcJfQjYQnWlcMnOrYi9kjZFpBhGcBZbqhx7cE7KLXorMBldRGFBkkx1Ikv4QhK45ieraTWcK39DKozvduHlHqOa3ZGI0mxrUZ6nRRtcMivarWTQDsQ3UYo2w9iPqT97Hwq0OQdHG8D5EtGrohNxxz1dJievD9gfRwxJWcAvtJfHDqqAfHaUoM1KebR7W6sPud3EgQkBJowfUF6wvPYXyAJoe+80pmeuEzqqtwJ9PaWw3InZI7U514CRqoE/PlaVQiQHU6Qp+9LtDaJR4uXu3taKaD4Gmw1NHI3NoPgtvo5ooU7c5hvM733fjUAiiKH/cr5p6D+EPzTQDg80tkPChdF7ufcfDH2MfuTVX+Z/OAEIlUHCwq1wpUu+HZEaUsFOZXGN/OQf5u+cCgr98etN2ZAdYZ9Hj+22mQLmsrZU8snkdjm6gHDZuyYfg6lU6PJS6VP J4HxVex7 DONHbPQ/+jxmAeM01vzczSbDepQumHkK/dDkCuF2apNFV6/8TM4FA056KqA3WtCpkOcqnjbDvr46OMu6fPjp4Fxth4TsE78NnNAEUSWs/P7ixHZ08jUaLxaakzQGd4hiFU8tQW7FeYi0RE7NIDxMoti5k6xeBJoL9DhxmDr5FE1Pjr/M3C4SrVZbxwOS23aOMBeFeFtco7ighA/yQDngb/KTME55W23ExJT8Fenm64I43KDC1O32ze2xZrY4qG9LHjKe8ihDFnoyD8Bm7O3BpCxmLMJnWLXmCE9GLOC+UcdDMt9U= 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: On Thu, 7 Sept 2023 at 15:06, Alexander Potapenko wrote: > > 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 I think this needs a Fixes tag. Also, is this corner case exercised by one of the KMSAN KUnit test cases? Otherwise, 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; > } > } > > -- > 2.42.0.283.g2d96d420d3-goog >