From patchwork Thu Jan 30 11:23:40 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dimitar Kanaliev X-Patchwork-Id: 13954499 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-wm1-f50.google.com (mail-wm1-f50.google.com [209.85.128.50]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B6E3B1BC065 for ; Thu, 30 Jan 2025 11:24:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738236246; cv=none; b=aiYYe7IXmVwVvMA4iRUGYVh3C3S0LI/NogtteHP+gHEkB6y9ApfDOXyECo2J9bubHDWNfYnOi7NWdkvY8RvaM/j7/FHq6AjyNRgNN87DZbTzHdFb+5o6pzJyl5RvhR/Tl3P1P/EfgoGPrqo7vjHIrzLvvvbtz62HhjwFg3T5M8M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738236246; c=relaxed/simple; bh=v1oPdERKX3fbXbdEsOpMgyO+3sLyesWUqzTiIeqAIyY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=MaRpiFFZ9WUTbQMnMzYdV8BEomfBZ1qxN0p3tBa+v7p/98/wq0hq3fAgAauENZVgf6H8oS+d+Tf51yNjyXPnhUrjVNKMXqXSolFE5rx0W13yrtRu9gk3v7AyI2vtlGgCuKyO31wdEgKFDP7o9SH8p4ecbIJib/R5qJ3QJmh1Jco= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=siteground.com; spf=pass smtp.mailfrom=siteground.com; dkim=pass (1024-bit key) header.d=siteground.com header.i=@siteground.com header.b=sGYylEUv; arc=none smtp.client-ip=209.85.128.50 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=siteground.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=siteground.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=siteground.com header.i=@siteground.com header.b="sGYylEUv" Received: by mail-wm1-f50.google.com with SMTP id 5b1f17b1804b1-4363ae65100so7255765e9.0 for ; Thu, 30 Jan 2025 03:24:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=siteground.com; s=google; t=1738236243; x=1738841043; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Xvg6MyU1DU2MCtc9Jk4pLxd20Kiayavou3Y5ZSj56Kg=; b=sGYylEUvkqmW0spHPirxF5OUU0dGWZg1DpMJ0/VwU0BYb2fm6GUg9X/5RbqcYIhg5z iDK7Se1f282eeYLEtLB3ea9s+GWkt7q6XWm+MFY3/APn7ke3m3puhLmGKF5fmHQXjzY3 kETRwIMl651b6ZV6CSy4/tJamJWhEsd3Zs33M= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1738236243; x=1738841043; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Xvg6MyU1DU2MCtc9Jk4pLxd20Kiayavou3Y5ZSj56Kg=; b=p6qPUMX/SJM/tIU24+OMIkrypijqZZJ812hW2d9p8XxrMbU8LHFF/YKrA8jt3m89Yr 8SDRNXCrEN8fnCc3ZBaLSVc1CPiWwwzsl05Rmw++75w3vNjy59kpaYCYxIXVNiKS9frV mQPqDlmdB8rxqyKHmOaVguNcDHrsyxWsw0CunH9xhhy+Y4vc+tz5fEDKHWyFRmuhNBc+ 3HSmQ0J6EYfR2OYawtyoXJF0fu7LYLDrsUQKEkC4O/aH1GTnmw1cetPfEaqKkb0IRQk+ yv2xPU1a9JO0nRBML+83bedkeA2kpejnUzol/QCs8Iyw5+gaKOHOlHkx/lUiMDXqlWZu gVbQ== X-Gm-Message-State: AOJu0YxmQ4Ix+Zel9olzr4xpQo25aRaRumHBNwpH59J49gZa5MlqcDVm eVoceb0KBe25HD2cQ2+VxRhcAS3imqYjTyoSyAZkdNa4ZKxPQ7+V7OUm20KkIjfLJfDVxH4CH2s KoCQ= X-Gm-Gg: ASbGncsSw42wFGmKFAAgmXUy9UTawjEb24iLeIOW1lJkaNdSR6jPfxu0uAzL2wH3/gD Pfmh8mCfnOhtm6rXp6Lkfnf7fIeVboch6zGak9f7QXqpjK9pQbYufjxB+nprQ5VurQs4poafYRv ibDxYec7dEwSFtm3DbSYpbVbhcSDigudFjGR6IuAAMKyaM6j1I/Ohqc/frG4GPJjt3Swgx8Y4rE WKAad1kXI7aC23/tgRrINQlSY8DY3Z38WFMhz7i4RIkaPHMGeO5bq9bvTkZMsTGd+UU0mwYJP95 aZomuXn7o+4pYeK4thvu4VO1HqMHckjmvodNDnjS6CW+15eeQdQhLR0= X-Google-Smtp-Source: AGHT+IH03vq/sOIQasPFzmDWm0epxUB+btdz1xpllkROHoDfroHf9sITDYKmZ9/688dg6qn1Q8axiQ== X-Received: by 2002:a05:6000:18ac:b0:38a:88f8:aadd with SMTP id ffacd0b85a97d-38c520a64b7mr6637706f8f.53.1738236242911; Thu, 30 Jan 2025 03:24:02 -0800 (PST) Received: from localhost.localdomain ([85.196.187.226]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-38c5c1b51e1sm1678981f8f.77.2025.01.30.03.24.01 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 30 Jan 2025 03:24:02 -0800 (PST) From: Dimitar Kanaliev To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Daniel Borkmann , John Fastabend , Andrii Nakryiko , Martin KaFai Lau , Eduard Zingerman , Song Liu , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , Mykola Lysenko , Yonghong Song , Shung-Hsi Yu , Dimitar Kanaliev Subject: [PATCH v0 1/3] bpf: Introduce tnum_scast as a tnum native sign extension helper Date: Thu, 30 Jan 2025 13:23:40 +0200 Message-Id: <20250130112342.69843-2-dimitar.kanaliev@siteground.com> X-Mailer: git-send-email 2.39.3 (Apple Git-146) In-Reply-To: <20250130112342.69843-1-dimitar.kanaliev@siteground.com> References: <20250130112342.69843-1-dimitar.kanaliev@siteground.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net This patch introduces a new helper function - tnum_scast(), which sign-extends a tnum from a smaller integer size to the full 64-bit bpf register range. This is achieved by: Given a tnum (v, m) and target size S bytes: 1) Mask value/mask to S bytes: val = v & mask, msk = m & mask 2) If sign bit (bit S*8-1) is unknown (msk has bit set): - Extended bits become unknown (mask |= ~value_mask) - Sign possibilities constrain value (if sign could be 1, upper bits must allow both 0s and 1s) 3) If sign bit is known: - Upper bits follow sign extension of val - Mask upper bits then follow sign extension of msk a) When the sign bit is known: Assume a tnum with value = 0xFF, mask = 0x00, size = 1, which corresponds to an 8-bit subregister of value 0xFF. We extract the sign bit position, compute the value mask, apply it to the lower bits and check the sign bit at said position. s = size * 8 - 1 // 1 * 8 - 1 = 7. value_mask = (1ULL << (s + 1)) - 1; // (1 << (7 + 1)) - 1 = 0xFF new_value = a.value & value_mask; // 0xFF & 0xFF = 0xFF new_mask = a.mask & value_mask; // 0x00 & 0xFF = 0x00 sign_bit_unknown = (0x00 >> 7) & 1 = 0; // sign bit is known sign_bit_value = (0xFF >> 7) & 1 = 1; // with value 1 Because the sign bit is known to be 1, we sign-extend with 1s above bit 7, so all upper bits [63,8] become 1, new_value in 64 bits is 0xFFFFFFFFFFFFFFFF and new_mask for those bits is 0 (since we know for sure they are all 1). So after the tnum_scast call and the sign extension, the tnum is (0xFFFFFFFFFFFFFFFF, 0x0000000000000000), which corresponds to the 64-bit value -1. b) When the sign bit is unknown: Assume a tnum wih value = 0x7F, mask = 0x80, size = 1. In this case the lower 8 bits [6,0] are known to be 0x7F or b(0111 1111). Bit 7 is unknown (mask = 0x80), so it could be 0 or 1. This means the subregister could be 0x7F (+127) or 0xFF (-1), or otherwise anythnig that differs in bit 7. Following the same operations as the previous example, we get s = 7 and value_mask = 0xFF. Then: new_value = a.value & value_mask; // 0x7F & 0xFF = 0x7F new_mask = a.mask & value_mask; // 0x80 & 0xFF = 0x80 sign_bit_unknown = (0x80 >> 7) & 1 = 1; // bit 7 is unknown // sign bit is unkown, so we treat upper bits [63,8] as unknown new_mask |= ~value_mask; This leads to a new tnum with value=0x7F, mask=0xFFFFFFFFFFFFFF80 The lower 8 bits can be 0x7F or 0xFF, and the higher 56 bits are fully unknown. In 64-bit form, this tnum can represent anything from: 0x000000000000007F (+127) if the sign bit is 0 and all higher bits are 0, up to 0xFFFFFFFFFFFFFFFF (-1) if the sign bit and all higher bits are 1. Signed-off-by: Dimitar Kanaliev --- include/linux/tnum.h | 3 +++ kernel/bpf/tnum.c | 29 +++++++++++++++++++++++++++++ 2 files changed, 32 insertions(+) diff --git a/include/linux/tnum.h b/include/linux/tnum.h index 3c13240077b8..6933db04c9ee 100644 --- a/include/linux/tnum.h +++ b/include/linux/tnum.h @@ -55,6 +55,9 @@ struct tnum tnum_intersect(struct tnum a, struct tnum b); /* Return @a with all but the lowest @size bytes cleared */ struct tnum tnum_cast(struct tnum a, u8 size); +/* Return @a sign-extended from @size bytes */ +struct tnum tnum_scast(struct tnum a, u8 size); + /* Returns true if @a is a known constant */ static inline bool tnum_is_const(struct tnum a) { diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c index 9dbc31b25e3d..cb29dbc793d4 100644 --- a/kernel/bpf/tnum.c +++ b/kernel/bpf/tnum.c @@ -157,6 +157,35 @@ struct tnum tnum_cast(struct tnum a, u8 size) return a; } +struct tnum tnum_scast(struct tnum a, u8 size) +{ + u64 s = size * 8 - 1; + u64 sign_mask; + u64 value_mask; + u64 new_value, new_mask; + u64 sign_bit_unknown, sign_bit_value; + u64 mask; + + if (size >= 8) { + return a; + } + + sign_mask = 1ULL << s; + value_mask = (1ULL << (s + 1)) - 1; + + new_value = a.value & value_mask; + new_mask = a.mask & value_mask; + + sign_bit_unknown = (a.mask >> s) & 1; + sign_bit_value = (a.value >> s) & 1; + + mask = ~value_mask; + new_mask |= mask & (0 - sign_bit_unknown); + new_value |= mask & (0 - ((sign_bit_unknown ^ 1) & sign_bit_value)); + + return TNUM(new_value, new_mask); +} + bool tnum_is_aligned(struct tnum a, u64 size) { if (!size) From patchwork Thu Jan 30 11:23:41 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dimitar Kanaliev X-Patchwork-Id: 13954500 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-wm1-f41.google.com (mail-wm1-f41.google.com [209.85.128.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 09D8F1B6D0F for ; Thu, 30 Jan 2025 11:24:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.41 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738236247; cv=none; b=jU3yT2UKm86cpIIApOFoJlqE4fcqiPEWKk602zdkgxGLbbH4Wkn72rG+VLKbUesxBG2jpj/IilX2iYQNjoPXB2KX38ppMEq++IjUAKWfwavI3zpIdDVsXO+CfLijLvSWoQt46Feuq7FQWuUsnS0OL+Z8yTUQ7uDCMbKsmexDFJM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738236247; c=relaxed/simple; bh=ir14bMQFsNYp32aOA6f0D6ULmpCPLRrhToUomfBUGXU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=aamrZj4kzVwiZm0n/++G2Gk1j0Qlm3h+Cmx1wGhNPzQB7A4UobH3h8HMLR0UAq5LvLgvKvhTS4m5EyXrTa7XHqdf+m+g5n+ZcrlLLQ162j+MQZ+6LvEibliqk5qIqMwke+f6Jm2Ga5SwuoTr6J4kM4DBBk/nijggylsfGEqTS+k= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=siteground.com; spf=pass smtp.mailfrom=siteground.com; dkim=pass (1024-bit key) header.d=siteground.com header.i=@siteground.com header.b=dzqaP9+h; arc=none smtp.client-ip=209.85.128.41 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=siteground.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=siteground.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=siteground.com header.i=@siteground.com header.b="dzqaP9+h" Received: by mail-wm1-f41.google.com with SMTP id 5b1f17b1804b1-43626213fffso11621835e9.1 for ; Thu, 30 Jan 2025 03:24:05 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=siteground.com; s=google; t=1738236244; x=1738841044; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=io1jYVOEhBj2nb/i6PNa0znOjf7UI5FGujFQE4rV18s=; b=dzqaP9+hdA1lbdJKLVNEo3uGSU7+WFsaCxl/I5OFBRglnzXk23VPefs+EaO/LJYnrF poBJfzBOwoEXSOcJ1Ikh6TAJt2ATuMPQl4GwNxooPP15VO1BqtPwSatJicLNs0rjdBI+ WdtmIkLAThdqme4C0YFxyzOYJWQ2lxgKaD2Bw= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1738236244; x=1738841044; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=io1jYVOEhBj2nb/i6PNa0znOjf7UI5FGujFQE4rV18s=; b=UbsaBxa5NjIKW5ddBKLdVZoHqwGlgmCsn29q3qH3X6GlSrA9dUFauwyZcbhB9qkQzl evdeFz9R07PoZoUyWO+8b7pl4Br4lR6aHIgpg1WEOk6p1yLvNED5iib4cjjP05gua70y u4NS374TTW3TlxH3F7fM+1BnJ4Sr0KnvGjROkNwQl2MQOiZfWm0Y8cRRKJ1LVhRBJ/QJ ID0nIhyx2IYdAuaxGyc831k0bu5elhUbUeTmJzehqp6PVYdvWPMONc9vqJx/id9enaWC YxCEfrlJsAoAIuD7NRxvBVUabpCGnknlOmW17nGbiRauRl6NyJs0eta62JuSSZCndCMc AarQ== X-Gm-Message-State: AOJu0YxM4mOqHN9eymiNTtuiChbinKaG0v3r++q0gXQc28OSpZgmcZ4I T8i2aVdTDh0hWu6AdKwUIx0swbbhbSTEuWFnSi9cTEGsl2hqRQLyBlGnhHnH+Yi7VfuKwXNWJ6L Noh0= X-Gm-Gg: ASbGnctbw33sYmR7tzA6CBcSxAVatdQHgnUyLRrwklBoh7jPIAE1lx9IT1zCG4VqEhI yMDZ033uU4VPR2MADgEwK8rRlmC7IKDJpePM6Zvs0a+kDFXrzmqMfTT5Ejx85F3l6xq72w4C+hL xmnEQbx+KUc1MPwL0eAingTd/qD9gPWL6nnbuBfOqOEcn0RIAl3qT8SImV+gB7KSAtdBeIYHa5u sy+4TLAFeIDpK1giVz0JyflQIvs0Tey3HVz2eW4Rx47O4JyYuETF/DVTcZTNYdAKrEMQroprXkj KlJ3c3Othspgt/2l3EmNKai8ZxuJkh96kX3OD54VV5oNKlSLX9XfIPA= X-Google-Smtp-Source: AGHT+IHA0i+sMu6BzcszTqP8lGj75Bic4aD8JZOvjRjSwo+iF6c/Uloni+KAfZ6f8naAmSB7ScGclg== X-Received: by 2002:a5d:6d0d:0:b0:38a:6183:77b9 with SMTP id ffacd0b85a97d-38c5a95722cmr2586107f8f.6.1738236244292; Thu, 30 Jan 2025 03:24:04 -0800 (PST) Received: from localhost.localdomain ([85.196.187.226]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-38c5c1b51e1sm1678981f8f.77.2025.01.30.03.24.03 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 30 Jan 2025 03:24:03 -0800 (PST) From: Dimitar Kanaliev To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Daniel Borkmann , John Fastabend , Andrii Nakryiko , Martin KaFai Lau , Eduard Zingerman , Song Liu , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , Mykola Lysenko , Yonghong Song , Shung-Hsi Yu , Dimitar Kanaliev Subject: [PATCH v0 2/3] bpf: verifier: Simplify register sign extension with tnum_scast Date: Thu, 30 Jan 2025 13:23:41 +0200 Message-Id: <20250130112342.69843-3-dimitar.kanaliev@siteground.com> X-Mailer: git-send-email 2.39.3 (Apple Git-146) In-Reply-To: <20250130112342.69843-1-dimitar.kanaliev@siteground.com> References: <20250130112342.69843-1-dimitar.kanaliev@siteground.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net This patch refactors the verifier's sign-extension logic for narrow register values to use the new tnum_scast helper. The general idea is to replace manual range checks in coerce_reg_to_size_sx and coerce_subreg_to_size_sx by deriving smin/smax and umin/umax boundaries directly from the tnum via tnum_scast. In the original code,some coercion cases with unknown sign bits triggered a fallback to worst-case [S64_MIN, S64_MAX] ranges. With these changes, we can now track bitwise uncertainty more precisely, allowing for arbitratry bounds like `[-129, 126]` when upper bits are partially known. An example for such cases would be: For an 8-bit register with var_off = (value=0x7F, mask=0x80) i.e known lower 7 bits, unknown sign bit, the original code would default to [S64_MIN, S64_MAX] for the smin, smax ranges, while the tnum_scast implementation will bind smin = -1, smax = 127, while still tracking uncertainty in the upper 56 bits. Signed-off-by: Dimitar Kanaliev --- kernel/bpf/verifier.c | 124 +++++++++++++----------------------------- 1 file changed, 39 insertions(+), 85 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 9971c03adfd5..a98dba42abc0 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -6661,61 +6661,35 @@ static void set_sext64_default_val(struct bpf_reg_state *reg, int size) static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) { - s64 init_s64_max, init_s64_min, s64_max, s64_min, u64_cval; - u64 top_smax_value, top_smin_value; - u64 num_bits = size * 8; + u64 s = size * 8 - 1; + u64 sign_mask = 1ULL << s; + s64 smin_value, smax_value; + u64 umax_value; - if (tnum_is_const(reg->var_off)) { - u64_cval = reg->var_off.value; - if (size == 1) - reg->var_off = tnum_const((s8)u64_cval); - else if (size == 2) - reg->var_off = tnum_const((s16)u64_cval); - else - /* size == 4 */ - reg->var_off = tnum_const((s32)u64_cval); - - u64_cval = reg->var_off.value; - reg->smax_value = reg->smin_value = u64_cval; - reg->umax_value = reg->umin_value = u64_cval; - reg->s32_max_value = reg->s32_min_value = u64_cval; - reg->u32_max_value = reg->u32_min_value = u64_cval; + if (size >= 8) return; - } - top_smax_value = ((u64)reg->smax_value >> num_bits) << num_bits; - top_smin_value = ((u64)reg->smin_value >> num_bits) << num_bits; + reg->var_off = tnum_scast(reg->var_off, size); - if (top_smax_value != top_smin_value) - goto out; - - /* find the s64_min and s64_min after sign extension */ - if (size == 1) { - init_s64_max = (s8)reg->smax_value; - init_s64_min = (s8)reg->smin_value; - } else if (size == 2) { - init_s64_max = (s16)reg->smax_value; - init_s64_min = (s16)reg->smin_value; + if (reg->var_off.mask & sign_mask) { + smin_value = -(1LL << s); + smax_value = (1LL << s) - 1; } else { - init_s64_max = (s32)reg->smax_value; - init_s64_min = (s32)reg->smin_value; + smin_value = (s64)(reg->var_off.value); + smax_value = (s64)(reg->var_off.value | reg->var_off.mask); } - s64_max = max(init_s64_max, init_s64_min); - s64_min = min(init_s64_max, init_s64_min); + reg->smin_value = smin_value; + reg->smax_value = smax_value; - /* both of s64_max/s64_min positive or negative */ - if ((s64_max >= 0) == (s64_min >= 0)) { - reg->s32_min_value = reg->smin_value = s64_min; - reg->s32_max_value = reg->smax_value = s64_max; - reg->u32_min_value = reg->umin_value = s64_min; - reg->u32_max_value = reg->umax_value = s64_max; - reg->var_off = tnum_range(s64_min, s64_max); - return; - } + reg->umin_value = reg->var_off.value; + umax_value = reg->var_off.value | reg->var_off.mask; + reg->umax_value = umax_value; -out: - set_sext64_default_val(reg, size); + reg->s32_min_value = (s32)smin_value; + reg->s32_max_value = (s32)smax_value; + reg->u32_min_value = (u32)reg->umin_value; + reg->u32_max_value = (u32)umax_value; } static void set_sext32_default_val(struct bpf_reg_state *reg, int size) @@ -6735,52 +6709,32 @@ static void set_sext32_default_val(struct bpf_reg_state *reg, int size) static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size) { - s32 init_s32_max, init_s32_min, s32_max, s32_min, u32_val; - u32 top_smax_value, top_smin_value; - u32 num_bits = size * 8; + u32 s = size * 8 - 1; + u32 sign_mask = 1U << s; + s32 smin_value, smax_value; + u32 umax_value; - if (tnum_is_const(reg->var_off)) { - u32_val = reg->var_off.value; - if (size == 1) - reg->var_off = tnum_const((s8)u32_val); - else - reg->var_off = tnum_const((s16)u32_val); - - u32_val = reg->var_off.value; - reg->s32_min_value = reg->s32_max_value = u32_val; - reg->u32_min_value = reg->u32_max_value = u32_val; + if (size >= 4) return; - } - - top_smax_value = ((u32)reg->s32_max_value >> num_bits) << num_bits; - top_smin_value = ((u32)reg->s32_min_value >> num_bits) << num_bits; - if (top_smax_value != top_smin_value) - goto out; + reg->var_off = tnum_scast(reg->var_off, size); - /* find the s32_min and s32_min after sign extension */ - if (size == 1) { - init_s32_max = (s8)reg->s32_max_value; - init_s32_min = (s8)reg->s32_min_value; + if (reg->var_off.mask & sign_mask) { + smin_value = -(1 << s); + smax_value = (1 << s) - 1; } else { - /* size == 2 */ - init_s32_max = (s16)reg->s32_max_value; - init_s32_min = (s16)reg->s32_min_value; - } - s32_max = max(init_s32_max, init_s32_min); - s32_min = min(init_s32_max, init_s32_min); - - if ((s32_min >= 0) == (s32_max >= 0)) { - reg->s32_min_value = s32_min; - reg->s32_max_value = s32_max; - reg->u32_min_value = (u32)s32_min; - reg->u32_max_value = (u32)s32_max; - reg->var_off = tnum_subreg(tnum_range(s32_min, s32_max)); - return; + smin_value = (s32)(reg->var_off.value); + smax_value = (s32)(reg->var_off.value | reg->var_off.mask); } -out: - set_sext32_default_val(reg, size); + reg->s32_min_value = smin_value; + reg->s32_max_value = smax_value; + + reg->u32_min_value = reg->var_off.value; + umax_value = reg->var_off.value | reg->var_off.mask; + reg->u32_max_value = umax_value; + + reg->var_off = tnum_subreg(reg->var_off); } static bool bpf_map_is_rdonly(const struct bpf_map *map) From patchwork Thu Jan 30 11:23:42 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dimitar Kanaliev X-Patchwork-Id: 13954501 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-wr1-f49.google.com (mail-wr1-f49.google.com [209.85.221.49]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4ED9F1C1F07 for ; Thu, 30 Jan 2025 11:24:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738236249; cv=none; b=ic4sP+rWTb5qNJ5WtTX45kpmeJ99z4/rQYFR1G/66B29E5JotHIvV+bWfsHCeVUgK/W+JKRvRGLO+NCv3Z9sg4DBs5TMsC6P5gzvd4xcpWACr0Vp2LNNJzA5Hv/Qvv6bEwF7ijh46qdNA0bZZhHmGTvOuvQsfAmM4fBwG3g89Lk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738236249; c=relaxed/simple; bh=V745EBPtWfO/KlVgeT/flSnTLJNcnFiunDgLtlkuRng=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=unxJ8QnolsZPKRf+xjLHCdAr9CMSrh5xsLDhPU0DnbYXuPfpCrVWiNxWt7y3Ol6kxZPkLmJTksi3DXPV750vcQrY79LD6AK6vs2VNsGWaXJ9g9DAjxprIfhBF0R08aBHS+58H6csRB0bCJhAn1KPUPZn+fUXTs++MPoRP1BFeG4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=siteground.com; spf=pass smtp.mailfrom=siteground.com; dkim=pass (1024-bit key) header.d=siteground.com header.i=@siteground.com header.b=wc1nIB3J; arc=none smtp.client-ip=209.85.221.49 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=siteground.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=siteground.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=siteground.com header.i=@siteground.com header.b="wc1nIB3J" Received: by mail-wr1-f49.google.com with SMTP id ffacd0b85a97d-385e27c75f4so563679f8f.2 for ; Thu, 30 Jan 2025 03:24:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=siteground.com; s=google; t=1738236245; x=1738841045; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=LYWhsyq+R/1EI1JInTggJWtmiRl2dMfBFoFdGnxFB5w=; b=wc1nIB3JMyPE5chLqcxm9fbYKd9vVDI/vbhJ5CIwAZ2oqGJr8lj/iqEf2Km5YR/AEJ kbpUuavIEFnaujhR/b4eX7Tchy+2BevA+VuPfdGlfvppn+SRgOeFGEzGcwhCvRV4kz3R c6P1BGZbyWatT8O4n2CKSYjUemRx0MJJpcdmQ= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1738236245; x=1738841045; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=LYWhsyq+R/1EI1JInTggJWtmiRl2dMfBFoFdGnxFB5w=; b=M6BTRBmPOq8+tGYUfY2Q54bac78xbR9DTgzZ0sN/rxUiobOs6eFq1/8CimVu2qUk4l St4h88YReg/Pq3omd3JM5yDZmg4tio/C7eoswHGETJTUKulQbI+3cX0Zp5p1rP1FYc7x 2/mCUn4wBH5QYlpE7djq7alE0s7R+y3MlqLCYNcCGnx+mYAUBOKT1bcuHMYfAD0d4cIK wi1pqg3tmjfANII81DdiXHaUkMyLba1aV6uOqIhTbIxPcpRlHc6lBDL4I1Zdq4RGlKeg lHjmRYzE8xqY90/JO+JvpI0EkupNtfCUPudUrH9sL7jJj9782aEJW2d9VPY3KyaGclnB Dcsw== X-Gm-Message-State: AOJu0YwauAQFcZfqIN4pG/DXt7jRsUOPvDk6e6CPbfwqT00L6p/XydVE 7s2UsmefxwrazV3SVYCevsm8EB0VBMfb6aG7JKbY3vWj+uw7zTAqZs7IaGIs6uSzwiaMot3kN29 8+T4= X-Gm-Gg: ASbGncupE2ngeHkna/9GJ7SQbit/3xZ/wZ1a5HZd1/cAbqBo0mI0met0k16TaJ/gpK4 ioe/GiIOsOGM7kt2oQrTWOWwIkd99xRaEhEtQj0WIVZeyx4b1XhQmLiEY3FrEfckDtw0oRQVkMf 1WGRFuT+/SKPN0qED7pPaQjxRWOpcYQE7+Ne3iLNyaOsmpfCIu8xIYU+f3sn8uXkWsGOMSenJwq BwITMAIymlAoimOxku4d9Q6CwRVHk8w/qVfuT9rzmVSFf1CLwP9adpuOnhno8XS8GHFpeUbvWjb VGAqNFs90HXKkzdOdBxlBmrqWNMCdGETns+w8rACkYN9Nk9g1vsvlVU= X-Google-Smtp-Source: AGHT+IE6E9y1qbeZwqYyFKuJAaMuNalusb+mJc8UfE0nLv4MdMrq+YCk19kqDOzVpa6EWB0eP2nfQA== X-Received: by 2002:a05:6000:18a9:b0:385:df6d:6fc7 with SMTP id ffacd0b85a97d-38c51b5efb4mr6535840f8f.25.1738236245551; Thu, 30 Jan 2025 03:24:05 -0800 (PST) Received: from localhost.localdomain ([85.196.187.226]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-38c5c1b51e1sm1678981f8f.77.2025.01.30.03.24.04 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 30 Jan 2025 03:24:05 -0800 (PST) From: Dimitar Kanaliev To: bpf@vger.kernel.org Cc: Alexei Starovoitov , Daniel Borkmann , John Fastabend , Andrii Nakryiko , Martin KaFai Lau , Eduard Zingerman , Song Liu , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , Mykola Lysenko , Yonghong Song , Shung-Hsi Yu , Dimitar Kanaliev Subject: [PATCH v0 3/3] selftests/bpf: Extend tests with more coverage for sign extension Date: Thu, 30 Jan 2025 13:23:42 +0200 Message-Id: <20250130112342.69843-4-dimitar.kanaliev@siteground.com> X-Mailer: git-send-email 2.39.3 (Apple Git-146) In-Reply-To: <20250130112342.69843-1-dimitar.kanaliev@siteground.com> References: <20250130112342.69843-1-dimitar.kanaliev@siteground.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net This commit adds a few more tests related to tnum_scast that explicitly check cases with known / unknown sign bit, as well as values that cross zero (going from negative to positive). Signed-off-by: Dimitar Kanaliev --- .../selftests/bpf/progs/verifier_movsx.c | 73 +++++++++++++++++++ 1 file changed, 73 insertions(+) diff --git a/tools/testing/selftests/bpf/progs/verifier_movsx.c b/tools/testing/selftests/bpf/progs/verifier_movsx.c index 994bbc346d25..20abeec09dee 100644 --- a/tools/testing/selftests/bpf/progs/verifier_movsx.c +++ b/tools/testing/selftests/bpf/progs/verifier_movsx.c @@ -327,6 +327,79 @@ label_%=: \ : __clobber_all); } +SEC("socket") +__description("MOV64SX, S8, unknown value") +__success __success_unpriv __retval(1) +__naked void mov64sx_s8_unknown(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r1 &= 0xFF; \ + r1 = (s8)r1; \ + if r1 s>= -128 goto l0_%=; \ + r0 = 0; \ + exit; \ +l0_%=: \ + if r1 s<= 127 goto l1_%=; \ + r0 = 0; \ + exit; \ +l1_%=: \ + r0 = 1; \ + exit; \ +" : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") + __description("MOV64SX, S8, sign bit unknown") + __success __success_unpriv __retval(1) +__naked void mov64sx_s8_sign_unknown(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r1 &= 0x7F; \ + r1 |= 0x80; \ + r1 = (s8)r1; \ + if r1 s>= -128 goto l0_%=; \ + r0 = 0; \ + exit; \ +l0_%=: \ + if r1 s<= 127 goto l1_%=; \ + r0 = 0; \ + exit; \ +l1_%=: \ + r0 = 1; \ + exit; \ + " : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + +SEC("socket") + __description("MOV64SX, S8, value crossing zero") + __success __success_unpriv __retval(1) +__naked void mov64sx_s8_cross_zero(void) +{ + asm volatile (" \ + call %[bpf_get_prandom_u32]; \ + r1 = r0; \ + r1 &= 0xFF; \ + r1 = (s8)r1; \ + if r1 s> -10 goto l0_%=; \ + if r1 s< 10 goto l0_%=; \ + r0 = 0; \ + exit; \ +l0_%=: \ + r0 = 1; \ + exit; \ + " : + : __imm(bpf_get_prandom_u32) + : __clobber_all); +} + #else SEC("socket")