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, 113 insertions, 0 deletions

diff --git a/scripts/bloat-o-meter b/scripts/bloat-o-meter
new file mode 100755
index 000000000..5868a8b11
--- /dev/null
+++ b/scripts/bloat-o-meter
@@ -0,0 +1,113 @@
+#!/usr/bin/env python3
+#
+# Copyright 2004 Matt Mackall <mpm@selenic.com>
+#
+# inspired by perl Bloat-O-Meter (c) 1997 by Andi Kleen
+#
+# This software may be used and distributed according to the terms
+# of the GNU General Public License, incorporated herein by reference.
+
+import sys, os, re, argparse
+from signal import signal, SIGPIPE, SIG_DFL
+
+signal(SIGPIPE, SIG_DFL)
+
+parser = argparse.ArgumentParser(description="Simple script used to compare the symbol sizes of 2 object files")
+group = parser.add_mutually_exclusive_group()
+group.add_argument('-c', help='categorize output based on symbol type', action='store_true')
+group.add_argument('-d', help='Show delta of Data Section', action='store_true')
+group.add_argument('-t', help='Show delta of text Section', action='store_true')
+parser.add_argument('-p', dest='prefix', help='Arch prefix for the tool being used. Useful in cross build scenarios')
+parser.add_argument('file_old', help='First file to compare')
+parser.add_argument('file_new', help='Second file to compare')
+
+args = parser.parse_args()
+
+re_NUMBER = re.compile(r'\.[0-9]+')
+
+def getsizes(file, format):
+    sym = {}
+    nm = "nm"
+    if args.prefix:
+        nm = "{}nm".format(args.prefix)
+
+    with os.popen("{} --size-sort {}".format(nm, file)) as f:
+        for line in f:
+            if line.startswith("\n") or ":" in line:
+                continue
+            size, type, name = line.split()
+            if type in format:
+                # strip generated symbols
+                if name.startswith("__mod_"): continue
+                if name.startswith("__se_sys"): continue
+                if name.startswith("__se_compat_sys"): continue
+                if name.startswith("__addressable_"): continue
+                if name.startswith("__noinstr_text_start"): continue
+                if name.startswith("_sdata"): continue
+                if name == "linux_banner": continue
+                if name == "vermagic": continue
+                # statics and some other optimizations adds random .NUMBER
+                name = re_NUMBER.sub('', name)
+                sym[name] = sym.get(name, 0) + int(size, 16)
+    return sym
+
+def calc(oldfile, newfile, format):
+    old = getsizes(oldfile, format)
+    new = getsizes(newfile, format)
+    grow, shrink, add, remove, up, down = 0, 0, 0, 0, 0, 0
+    delta, common = [], {}
+    otot, ntot = 0, 0
+
+    for a in old:
+        if a in new:
+            common[a] = 1
+
+    for name in old:
+        otot += old[name]
+        if name not in common:
+            remove += 1
+            down += old[name]
+            delta.append((-old[name], name))
+
+    for name in new:
+        ntot += new[name]
+        if name not in common:
+            add += 1
+            up += new[name]
+            delta.append((new[name], name))
+
+    for name in common:
+        d = new.get(name, 0) - old.get(name, 0)
+        if d>0: grow, up = grow+1, up+d
+        if d<0: shrink, down = shrink+1, down-d
+        delta.append((d, name))
+
+    delta.sort(reverse=True)
+    return grow, shrink, add, remove, up, down, delta, old, new, otot, ntot
+
+def print_result(symboltype, symbolformat):
+    grow, shrink, add, remove, up, down, delta, old, new, otot, ntot = \
+    calc(args.file_old, args.file_new, symbolformat)
+
+    print("add/remove: %s/%s grow/shrink: %s/%s up/down: %s/%s (%s)" % \
+          (add, remove, grow, shrink, up, -down, up-down))
+    print("%-40s %7s %7s %+7s" % (symboltype, "old", "new", "delta"))
+    for d, n in delta:
+        if d: print("%-40s %7s %7s %+7d" % (n, old.get(n,"-"), new.get(n,"-"), d))
+
+    if otot:
+        percent = (ntot - otot) * 100.0 / otot
+    else:
+        percent = 0
+    print("Total: Before=%d, After=%d, chg %+.2f%%" % (otot, ntot, percent))
+
+if args.c:
+    print_result("Function", "tTwW")
+    print_result("Data", "dDbBvV")
+    print_result("RO Data", "rR")
+elif args.d:
+    print_result("Data", "dDbBrRvV")
+elif args.t:
+    print_result("Function", "tTwW")
+else:
+    print_result("Function", "tTdDbBrRvVwW")