selftests/bpf: Test packet range of pointers sharing an idgrafted

Add tests where two packet pointers share an id and tightening one
pointer's umax from its var_off would put it less than their constant
distance from the other's umax: with an index & 0x38 capped at 50, the
base pointer keeps umax 50, so the pointer 8 bytes further on must keep
umax 58, even though its known bits allow at most 56.

These refused a valid program or accepted an out-of-bounds access before
the fix:

- check the advanced copy, load through the base: valid, was refused;
- check the base, load the byte at base + 1 through a copy advanced by
  8: was accepted;
- check base + 4, load 4 bytes at base + 2 through base + 8: reads two
  bytes past the checked range, was accepted;
- the same as the second with data_meta pointers checked against data:
  was accepted.

These pass with and without the fix and cover nearby paths:

- subtract an unknown scalar from a checked pointer and load below it
  (the range is kept across a new id);
- reach a load through two paths whose checks cover 8 and 7 bytes after
  the loaded pointer; the second path must not be pruned by the first;
- spill a copy of a pointer, check the pointer, fill the copy and load
  one byte past the checked range: the load is refused, and the copy
  has the range of the check.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://lore.kernel.org/bpf/20261001145255.855630-2-alexei.starovoitov@gmail.com
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

1 files changed, 121 insertions, 0 deletions

diff --git a/scripts/kconfig/util.c b/scripts/kconfig/util.c
new file mode 100644
index 000000000..0809aa061
--- /dev/null
+++ b/scripts/kconfig/util.c
@@ -0,0 +1,121 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (C) 2002-2005 Roman Zippel <zippel@linux-m68k.org>
+ * Copyright (C) 2002-2005 Sam Ravnborg <sam@ravnborg.org>
+ */
+
+#include <stdarg.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <hash.h>
+#include <hashtable.h>
+#include <xalloc.h>
+#include "lkc.h"
+
+/* hash table of all parsed Kconfig files */
+static HASHTABLE_DEFINE(file_hashtable, 1U << 11);
+
+struct file {
+	struct hlist_node node;
+	struct {
+		const char *name;
+		int lineno;
+	} parent;
+	char name[];
+};
+
+static void die_duplicated_include(struct file *file,
+				   const char *parent, int lineno)
+{
+	fprintf(stderr,
+		"%s:%d: error: repeated inclusion of %s\n"
+		"%s:%d: note: location of first inclusion of %s\n",
+		parent, lineno, file->name,
+		file->parent.name, file->parent.lineno, file->name);
+	exit(1);
+}
+
+/* file already present in list? If not add it */
+const char *file_lookup(const char *name,
+			const char *parent_name, int parent_lineno)
+{
+	const char *parent = NULL;
+	struct file *file;
+	size_t len;
+	int hash = hash_str(name);
+
+	if (parent_name)
+		parent = file_lookup(parent_name, NULL, 0);
+
+	hash_for_each_possible(file_hashtable, file, node, hash)
+		if (!strcmp(name, file->name)) {
+			if (!parent_name)
+				return file->name;
+			die_duplicated_include(file, parent, parent_lineno);
+		}
+
+	len = strlen(name);
+	file = xmalloc(sizeof(*file) + len + 1);
+	memset(file, 0, sizeof(*file));
+	memcpy(file->name, name, len);
+	file->name[len] = '\0';
+	file->parent.name = parent;
+	file->parent.lineno = parent_lineno;
+
+	hash_add(file_hashtable, &file->node, hash);
+
+	str_printf(&autoconf_cmd, "\t%s \\\n", name);
+
+	return file->name;
+}
+
+/* Allocate initial growable string */
+struct gstr str_new(void)
+{
+	struct gstr gs;
+	gs.s = xmalloc(sizeof(char) * 64);
+	gs.len = 64;
+	gs.max_width = 0;
+	strcpy(gs.s, "\0");
+	return gs;
+}
+
+/* Free storage for growable string */
+void str_free(struct gstr *gs)
+{
+	free(gs->s);
+	gs->s = NULL;
+	gs->len = 0;
+}
+
+/* Append to growable string */
+void str_append(struct gstr *gs, const char *s)
+{
+	size_t l;
+	if (s) {
+		l = strlen(gs->s) + strlen(s) + 1;
+		if (l > gs->len) {
+			gs->s = xrealloc(gs->s, l);
+			gs->len = l;
+		}
+		strcat(gs->s, s);
+	}
+}
+
+/* Append printf formatted string to growable string */
+void str_printf(struct gstr *gs, const char *fmt, ...)
+{
+	va_list ap;
+	char s[10000]; /* big enough... */
+	va_start(ap, fmt);
+	vsnprintf(s, sizeof(s), fmt, ap);
+	str_append(gs, s);
+	va_end(ap);
+}
+
+/* Retrieve value of growable string */
+char *str_get(const struct gstr *gs)
+{
+	return gs->s;
+}