[DTrace-devel] [PATCH v3 00/19] alloca and bcopy, and improved null-pointer checking
Nick Alcock
nick.alcock at oracle.com
Thu Mar 24 18:24:26 UTC 2022
This pile of commits implements alloca and bcopy, and a few bugfixes and
feature additions I found necessary along the way.
Changes since v2:
- support passing alloca'ed pointers to subrs and actions as parameters
- fix strlen() lower bounds (needed for strlen)
- fix bounds-checked pointer's lower bounds (which could end up
erroneously negative when sized checks were done)
- delete a bunch of unnecessary fault checks
- a couple of tiny consistency improvements in the changes to
dt_xcook_ident
- (even) more tests
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.
There is also a helper dt_cg_check_alloca_string_bounds to bounds-check
strings iff they are alloca'ed: this is largely used by the
implementation of subrs taking strings.
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 (except that you can't do it with strings yet because
there is as yet no way to record null-pointer-ness in a string variable).
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 record null pointers in variables as a new constant
DT_CG_ALLOCA_NULLPTR, which is way too big to be valid for any actual
allocation, then spot it at load time: in order to diagnose pointers near
NULL as NULL (like native programs do), we implement this by checking for
NULL and near-NULL pointers and then adding DT_CG_ALLOCA_NULLPTR to whatever
the pointer value is if it's found to be NULL, and subtracting it again on
load: so you can even do this and it works:
char *foo = NULL;
BEGIN
{
bar = &foo[10];
}
BEGIN
/ bar == &foo[10] /
{
trace("yes, this should work\n");
}
(and we have a test for something similar).
We check for "near-null" pointers wherever we would have checked for null
pointers: in the scratch checkers and in dt_cg_check_notnull. In order to
make the verifier happier, dtg_cg_check_notnull explicitly checks for
0-valued null pointers as well, because the verifier understands this where
it does not understand what a near-null pointer might imply. We define
"near-null" as "within scratchmem of 0, in either direction", allowing us to
detect uses of null pointers instead of alloca variables in any point of any
structure or array which might fit inside allocaable space in the first
place.
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 ternary conditional operator now correctly handles NULL strings
(or will be able to, when we can store them)
- 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
- the testsuite runner now emits diffs even if the input looks like
binary data (could be split into a separate series)
- we no longer throw away CTF errors when setting task offsets
(could be split into a separate series)
- we fix the bounds on the return value of dt_strlen() to prevent
the verifier seeing the lower bound as -1, causing possible verifier
failures later on iff it decides it needs a non-negative value
The set of failures when running make check with this series, for me,
ignoring things like aggs timeouts and the name-lookups failure that have
been present for years:
test/unittest/funcs/strtok/tst.strtok2.d: FAIL: erroneous exitcode (1).
test/unittest/funcs/strtok/tst.strtok_long.d: FAIL: erroneous exitcode (1).
test/unittest/operators/tst.str_comparison-basic.d: FAIL: erroneous exitcode (1).
test/unittest/speculation/tst.SingleCPU.d: FAIL: timed out.
I'll look at tst.SingleCPU.d next (it seems to be a timeout,
probably not particularly related to this series, but it helps to be sure).
The other three are all string null-assignment stuff.
Nick Alcock (19):
alloca: track alloca()ed allocations
cg: add dt_cg_trace
cg: fault improvements
memcpy: bounds-check
alloca: new bad-size fault
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
bpf: don't throw away CTF errors when setting task offsets
cg: support casts of pointers to integers
strings: handle null strings in the ternary conditional op
strings: improve bounds on strlen return value
alloca: allow passing alloca pointers to actions and subrs
Makeoptions | 3 +-
bpf/Build | 3 +-
bpf/strlen.c | 2 +-
bpf/trace_ptr.c | 23 +
include/bpf-lib.h | 15 +
include/dtrace/faults_defines.h | 1 +
include/dtrace/options_defines.h | 3 +-
libdtrace/dt_bpf.c | 25 +-
libdtrace/dt_cg.c | 913 +++++++++++++++++-
libdtrace/dt_dctx.h | 26 +-
libdtrace/dt_dlibs.c | 1 +
libdtrace/dt_error.c | 1 +
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 | 226 ++++-
libdtrace/dt_parser.h | 5 +-
libdtrace/dt_pcb.h | 1 +
runtest.sh | 2 +-
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 +
.../alloca/err.alloca-load-before-bottom.r | 3 +
.../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 | 29 +
.../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 +
test/unittest/funcs/alloca/tst.alloca-funcs.d | 125 +++
.../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 +
.../unittest/funcs/alloca/tst.string-alloca.d | 24 +
.../unittest/funcs/alloca/tst.string-alloca.r | 1 +
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 +
.../{err.badbcopy5.d => err.badbcopy8.d} | 13 +-
test/unittest/funcs/err.badbcopy8.r | 3 +
test/unittest/funcs/tst.bcopy.d | 10 +-
test/unittest/inline/tst.InlineKinds.d | 7 +
...CA_INCOMPAT.alloca-postinc-instantiation.d | 21 +
...CA_INCOMPAT.alloca-postinc-instantiation.r | 2 +
.../tst.alloca-postinc-instantiation.d | 46 +
108 files changed, 2583 insertions(+), 109 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-before-bottom.r
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 100644 test/unittest/funcs/alloca/tst.alloca-funcs.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.string-alloca.d
create mode 100644 test/unittest/funcs/alloca/tst.string-alloca.r
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
copy test/unittest/funcs/{err.badbcopy5.d => err.badbcopy8.d} (63%)
create mode 100644 test/unittest/funcs/err.badbcopy8.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.1.261.g8402f930ba.dirty
More information about the DTrace-devel
mailing list