[DTrace-devel] [PATCH 00/14] alloca and bcopy
Nick Alcock
nick.alcock at oracle.com
Wed Mar 2 13:44:53 UTC 2022
This pile of commits implements alloca and bcopy, and a few bugfixes and
feature additions I found necessary along the way.
In brief, alloca works in three phases, all combining to allow us to
store and retrieve data in a new percpu scratchmem array. (The result
should be usable for cross-clause allocations too in future, though the
array would need to be non-per-CPU and there might be a few locking
considerations.)
1) mark all pointers emitted from alloca(), all variables such values
are stored in, and all values retrieved from those variables with
special parser/ident flags
2) use these flags to identify alloca values flowing into variables and
reduce them to offsets from the scratchmem base; also use them to
identify alloca values flowing *out* of such variables, and raise
them back to pointers into the scratchmem base again; bounds-check
them appropriately to prevent verifier failures (making sure the
pointer lies within the scratchmem bounds: the resulting pointer is
still not useful for accesses but can get as far as dereferencing
without triggering verifier failures)
2) at deref time, bounds-check them again, taking the size of the access
into account: this allows for any intermediate pointer arithmetic,
including that emitted automatically by the compiler for array
accesses.
All of these involve bounds checkers. There are three.
One, dt_cg_check_bounds, is a low-level function that checks if a
pointer or offset lies within some bounds or other (defined by a base
pointer), and hands you back a bounds-checked pointer (or raises a
fault). It's a bit fiddly: in particular, we need to allocate twice the
length for scratchmem that we are actually allowed to access, since the
verifier cannot be told that an access at the very end of scratchmem
might not be max-length (we check that at runtime but the verifier
insists on constants in bounds checks, and the actual length being
accessed is often a variable value). This is only a few hundred bytes
per CPU so is probably not a problem.
The other two are a pair: dt_cg_check_scratch_bounds wraps
dt_cg_check_bounds and specifically checks whether things are in range
of the scratchmem; the other, dt_cg_check_outscratch_bounds, checks
specifically whether a reg is *not* in the scratch bounds. Both also
raise exceptions if you pass them null pointers.
The alloca-tainting stuff above has some slightly unfortunate
implications, since alloca status attaches to identifiers, not to
specific uses of them. You cannot reuse the same variable to store both
alloca pointers and other sorts of pointer in a single D program (not
clause!). You *can* have ternary conditionals whose branches are
sometimes alloca and sometimes not, but you can't assign the result of
such ternaries to variables at all.
This does *not* apply to null pointers: you can assign NULL to pointers
that previously held allocaed pointers, and stick alloca pointers back
on them, freely. But that's not a get-out clause: you still can't do
this:
foo = 42;
foo = NULL;
foo = alloca(10);
Getting null pointers working was a bit weird. They're pointers from
BPF's perspective as soon as they're assigned, but if we write them to a
variable and read them back out again they become not pointers any more,
and you can't turn them back into something looking just like the
original NULL, since there's no BPF map there: also, we can't store them
as 0, since 0 means "offset of 0 from scratch base", which is not a null
pointer. So instead we have a new 1-byte "array" named "null"; we store
null pointers assigned to alloca'ed variables as a new constant
DT_CG_ALLOCA_NULLPTR, which is way too big to be valid for any actual
allocation, then spot it on load and convert it to a pointer to the
"null" array. Since this is a map_value, the verifier doesn't complain
if you do things with it, so we can get it as far as the bounds
checkers. The only one that cares about it is
dt_cg_check_outscratch_bounds, which defines both sorts of null pointer
as being BADADDR-invalid even though they are also outside the scratch
space :)
Thus we avoid doing actual null pointer derefs, which would cause
verifier failures rather than a nice error.
One downside of this approach, though -- as with null pointer checking
elsewhere, we must consider values *near* the null pointer map to be
null pointers (due to array offsets, structure fields etc). For us,
"near" is "within scratchmem length". This means that there are some
structures allocated near the null pointer array that are not bcopyable
from because they are "null pointers"! I might fix this by expanding
the null pointer array to be at least scratchmem * 2 in length, and
make the null pointer constant sit in the middle of it: does that seem
sensible?
The non-alloca-related parts of this:
- dt_cg_trace, a debugging=yes-only facility for emitting debug output
on the trace_pipe: must be used with care because e.g. emitting trace
while some regs are allocated but uninitialized might cause verifier
failures. And obviously you can't use it to *spot* verifier failures!
It's still damn useful though.
- memcpy now has error-checking rather than a FIXME asking for it
- the testsuite runner now emits diffs even if the input looks like
binary data
- the fault-emitting machinery in dt_cg can now emit an illegal value
found in a register, and avoids using the regset machinery because
that can try to spill to the stack, which can cause verifier
failures if some regs are still uninitialized -- which is quite
likely in a fault situation
Nick Alcock (14):
alloca: track alloca()ed allocations
cg: add dt_cg_trace
cg: fault improvements
memcpy: bounds-check
alloca: new faults
alloca: add alloca() itself
cg: comment typo fix
alloca: load and store
alloca: deref
alloca: bcopy
tests: always check expected results as text, not binary
alloca: fix verifier failure checking the bounds of scalars
alloca: support null pointers
alloca, tests: add test/unittest/funcs/err.badbcopy*.d expected
results
Makeoptions | 3 +-
bpf/Build | 3 +-
bpf/trace_ptr.c | 23 +
include/dtrace/faults_defines.h | 2 +
include/dtrace/options_defines.h | 3 +-
libdtrace/dt_bpf.c | 23 +
libdtrace/dt_cg.c | 782 +++++++++++++++++-
libdtrace/dt_dctx.h | 28 +-
libdtrace/dt_dlibs.c | 5 +
libdtrace/dt_error.c | 2 +
libdtrace/dt_errtags.h | 2 +
libdtrace/dt_handle.c | 1 +
libdtrace/dt_ident.c | 18 +-
libdtrace/dt_ident.h | 2 +
libdtrace/dt_open.c | 10 +-
libdtrace/dt_options.c | 1 +
libdtrace/dt_parser.c | 225 ++++-
libdtrace/dt_parser.h | 5 +-
libdtrace/dt_pcb.h | 1 +
runtest.sh | 2 +-
test/unittest/codegen/tst.stack_layout.r | 22 +-
test/unittest/dif/alloca.d | 3 +-
.../alloca/err.D_ALLOCA_INCOMPAT.ternary.d | 26 +
.../alloca/err.D_ALLOCA_INCOMPAT.ternary.r | 2 +
...rr.D_ALLOCA_INCOMPAT.var-clash-non-first.d | 28 +
...rr.D_ALLOCA_INCOMPAT.var-clash-non-first.r | 2 +
.../alloca/err.D_ALLOCA_INCOMPAT.var-clash.d | 30 +
.../alloca/err.D_ALLOCA_INCOMPAT.var-clash.r | 2 +
.../alloca/err.alloca-bcopy-before-beyond.d | 27 +
.../alloca/err.alloca-bcopy-before-beyond.r | 3 +
.../alloca/err.alloca-bcopy-before-bottom.d | 27 +
.../alloca/err.alloca-bcopy-before-bottom.r | 3 +
.../alloca/err.alloca-bcopy-beyond-top.d | 27 +
.../alloca/err.alloca-bcopy-beyond-top.r | 3 +
.../alloca/err.alloca-bcopy-crossing-bottom.d | 27 +
.../alloca/err.alloca-bcopy-crossing-bottom.r | 3 +
.../alloca/err.alloca-bcopy-crossing-top.d | 27 +
.../alloca/err.alloca-bcopy-crossing-top.r | 3 +
.../alloca/err.alloca-crossing-clauses.d | 31 +
.../alloca/err.alloca-crossing-clauses.r | 3 +
.../alloca/err.alloca-load-before-bottom.d | 26 +
.../funcs/alloca/err.alloca-load-beyond-top.d | 28 +
.../funcs/alloca/err.alloca-load-beyond-top.r | 3 +
.../alloca/err.alloca-load-crossing-bottom.d | 25 +
.../alloca/err.alloca-load-crossing-bottom.r | 3 +
.../alloca/err.alloca-load-crossing-top.d | 25 +
.../alloca/err.alloca-load-crossing-top.r | 3 +
.../alloca/err.alloca-null-deref-lvalue.d | 27 +
.../alloca/err.alloca-null-deref-lvalue.r | 3 +
.../funcs/alloca/err.alloca-null-deref.d | 27 +
.../funcs/alloca/err.alloca-null-deref.r | 3 +
.../err.alloca-scratch-exceeding-bcopy.d | 37 +
.../err.alloca-scratch-exceeding-bcopy.r | 3 +
.../alloca/err.alloca-store-before-bottom.d | 26 +
.../alloca/err.alloca-store-before-bottom.r | 3 +
.../alloca/err.alloca-store-beyond-top.d | 28 +
.../alloca/err.alloca-store-beyond-top.r | 3 +
.../alloca/err.alloca-store-crossing-bottom.d | 26 +
.../alloca/err.alloca-store-crossing-bottom.r | 3 +
.../alloca/err.alloca-store-crossing-top.d | 25 +
.../alloca/err.alloca-store-crossing-top.r | 3 +
....alloca-store-load-aliasing-arith-bottom.d | 28 +
....alloca-store-load-aliasing-arith-bottom.r | 3 +
.../funcs/alloca/tst.alloca-alignment.d | 34 +
.../funcs/alloca/tst.alloca-bcopy-top.d | 28 +
.../funcs/alloca/tst.alloca-bcopy-top.r | 2 +
.../alloca/tst.alloca-crossing-clauses.d | 33 +
.../funcs/alloca/tst.alloca-overtainting.sh | 35 +
.../alloca/tst.alloca-scratch-filling-bcopy.d | 31 +
.../tst.alloca-store-load-aliasing-arith.d | 29 +
.../alloca/tst.alloca-store-load-bottom.d | 27 +
.../alloca/tst.alloca-store-load-idx-1.d | 27 +
.../funcs/alloca/tst.alloca-store-load-top.d | 27 +
.../alloca/tst.alloca0-after-alloca-load.d | 28 +
.../funcs/alloca/tst.alloca0-after-alloca.d | 26 +
test/unittest/funcs/alloca/tst.alloca0-load.d | 27 +
.../funcs/alloca/tst.alloca0-values.sh | 34 +
test/unittest/funcs/alloca/tst.alloca0.d | 25 +
test/unittest/funcs/alloca/tst.ternary.d | 27 +
.../funcs/err.D_ALLOCA_SIZE.big_alloca.d | 24 +
.../funcs/err.D_ALLOCA_SIZE.big_alloca.r | 2 +
test/unittest/funcs/err.badalloca.d | 2 +-
test/unittest/funcs/err.badalloca2.d | 3 +-
test/unittest/funcs/err.badalloca2.r | 6 +-
test/unittest/funcs/err.badbcopy.r | 3 +
test/unittest/funcs/err.badbcopy1.r | 3 +
test/unittest/funcs/err.badbcopy2.r | 3 +
test/unittest/funcs/err.badbcopy3.r | 3 +
test/unittest/funcs/err.badbcopy4.d | 1 -
test/unittest/funcs/err.badbcopy4.r | 2 +-
test/unittest/funcs/err.badbcopy5.d | 1 -
test/unittest/funcs/err.badbcopy5.r | 2 +-
test/unittest/funcs/err.badbcopy6.d | 1 -
test/unittest/funcs/err.badbcopy6.r | 2 +-
.../{err.badalloca.d => err.badbcopy7.d} | 12 +-
test/unittest/funcs/err.badbcopy7.r | 3 +
test/unittest/funcs/tst.bcopy.d | 10 +-
...CA_INCOMPAT.alloca-postinc-instantiation.d | 21 +
...CA_INCOMPAT.alloca-postinc-instantiation.r | 2 +
.../tst.alloca-postinc-instantiation.d | 46 ++
100 files changed, 2308 insertions(+), 85 deletions(-)
create mode 100644 bpf/trace_ptr.c
create mode 100644 test/unittest/funcs/alloca/err.D_ALLOCA_INCOMPAT.ternary.d
create mode 100644 test/unittest/funcs/alloca/err.D_ALLOCA_INCOMPAT.ternary.r
create mode 100644 test/unittest/funcs/alloca/err.D_ALLOCA_INCOMPAT.var-clash-non-first.d
create mode 100644 test/unittest/funcs/alloca/err.D_ALLOCA_INCOMPAT.var-clash-non-first.r
create mode 100644 test/unittest/funcs/alloca/err.D_ALLOCA_INCOMPAT.var-clash.d
create mode 100644 test/unittest/funcs/alloca/err.D_ALLOCA_INCOMPAT.var-clash.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-before-beyond.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-before-beyond.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-before-bottom.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-before-bottom.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-beyond-top.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-beyond-top.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-crossing-bottom.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-crossing-bottom.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-crossing-top.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-bcopy-crossing-top.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-crossing-clauses.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-crossing-clauses.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-load-before-bottom.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-load-beyond-top.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-load-beyond-top.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-load-crossing-bottom.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-load-crossing-bottom.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-load-crossing-top.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-load-crossing-top.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-null-deref-lvalue.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-null-deref-lvalue.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-null-deref.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-null-deref.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-scratch-exceeding-bcopy.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-scratch-exceeding-bcopy.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-before-bottom.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-before-bottom.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-beyond-top.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-beyond-top.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-crossing-bottom.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-crossing-bottom.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-crossing-top.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-crossing-top.r
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-load-aliasing-arith-bottom.d
create mode 100644 test/unittest/funcs/alloca/err.alloca-store-load-aliasing-arith-bottom.r
create mode 100644 test/unittest/funcs/alloca/tst.alloca-alignment.d
create mode 100644 test/unittest/funcs/alloca/tst.alloca-bcopy-top.d
create mode 100644 test/unittest/funcs/alloca/tst.alloca-bcopy-top.r
create mode 100644 test/unittest/funcs/alloca/tst.alloca-crossing-clauses.d
create mode 100755 test/unittest/funcs/alloca/tst.alloca-overtainting.sh
create mode 100644 test/unittest/funcs/alloca/tst.alloca-scratch-filling-bcopy.d
create mode 100644 test/unittest/funcs/alloca/tst.alloca-store-load-aliasing-arith.d
create mode 100644 test/unittest/funcs/alloca/tst.alloca-store-load-bottom.d
create mode 100644 test/unittest/funcs/alloca/tst.alloca-store-load-idx-1.d
create mode 100644 test/unittest/funcs/alloca/tst.alloca-store-load-top.d
create mode 100644 test/unittest/funcs/alloca/tst.alloca0-after-alloca-load.d
create mode 100644 test/unittest/funcs/alloca/tst.alloca0-after-alloca.d
create mode 100644 test/unittest/funcs/alloca/tst.alloca0-load.d
create mode 100755 test/unittest/funcs/alloca/tst.alloca0-values.sh
create mode 100644 test/unittest/funcs/alloca/tst.alloca0.d
create mode 100644 test/unittest/funcs/alloca/tst.ternary.d
create mode 100644 test/unittest/funcs/err.D_ALLOCA_SIZE.big_alloca.d
create mode 100644 test/unittest/funcs/err.D_ALLOCA_SIZE.big_alloca.r
create mode 100644 test/unittest/funcs/err.badbcopy.r
create mode 100644 test/unittest/funcs/err.badbcopy1.r
create mode 100644 test/unittest/funcs/err.badbcopy2.r
create mode 100644 test/unittest/funcs/err.badbcopy3.r
copy test/unittest/funcs/{err.badalloca.d => err.badbcopy7.d} (64%)
create mode 100644 test/unittest/funcs/err.badbcopy7.r
create mode 100644 test/unittest/predicates/err.D_ALLOCA_INCOMPAT.alloca-postinc-instantiation.d
create mode 100644 test/unittest/predicates/err.D_ALLOCA_INCOMPAT.alloca-postinc-instantiation.r
create mode 100644 test/unittest/predicates/tst.alloca-postinc-instantiation.d
--
2.35.0.260.gb82b153193.dirty
More information about the DTrace-devel
mailing list