[DTrace-devel] [PATCH v3 06/19] alloca: add alloca() itself

[Nick Alcock]

On 30 Mar 2022, Kris Van Hees uttered the following:

> On Thu, Mar 24, 2022 at 06:24:32PM +0000, Nick Alcock via DTrace-devel wrote:
>> We add a new scratchsize option (default value 256, just like in days of
>> old), and a new scratchmem dctx pointer.  This is allocated twice as
>> much space as we asked for, because the verifier can only use the values
>> of variables to adjust its bounds in very limited conditions: so we
>> leave enough space to write the full size of scratch space to the last
>> byte of scratch space without overflow.  (Runtime checks will prohibit
>> such things, but the verifier doesn't know about those.)
>
> I would get rid of everything in the paragraph above except for the first
> sentence.  The rest is not needed.
>
>> The top of currently-allocated scratch space is indicated with two
>> values in the machine state: DMST_SCRATCH_TOP, the current top of
>> scratch space, used for bounds-checking lookups, and DMST_SCRATCH_NEXT,
>> which is an 8-byte-aligned DMST_SCRATCH_TOP, and is where the next
>> allocation comes from.  (Thus we ensure that all allocations are aligned
>> adequately for all D basic types, without losing bounds checking of the
>> most recently alloca()ed value.)
>
> Why not simply have DMST_SCRATCH_TOP be 8-byte-aligned and thereby avoid
> needing DMST_SCRATCH_NEXT?  It is perfectly valid to over-allocate by a few
> bytes to ensure that the next allocation will always be properly aligned.

This lets us spot (and fault on) even one-byte overruns in the extremely
common case that the thing you're modifying is the last thing you
alloca()ed. Maybe we don't care about that? If we don't care, I'll
switch over to save the dmst space.

> Yes, it would mean that after you allocate 13 bytes, you are able to access
> 16 bytes, but that is fine.

Oh, OK. I tend to err on the side of spotting overflows, particularly in
cases where they are dead easy to spot and quite likely to happen (like
this case), but I suppose this is doing no worse than malloc() anyway!
and it does save mst space.

Adjusted.

>                              You just want to ensure that the scratchsize
> option value is also rounded up to the next 8-byte-boundary.  When that is

Why? No other size options do adjustments like that, even those for
which v1 required not only alignment but power-of-two values. If you
specify a non-aligned value you waste a bit of space at the end, but
that's space we'd have to waste *anyway*, even if the requested size was
larger.

There's no need to do it to ensure that we can store arbitrary stuff in
the last part of the scratch space -- we can do that *anyway* because we
allocate twice the requested size.

> needed, you could emit a message saying that scratchsize got increased to the
> new value but perhaps that is not really necessary because it is just a small
> adjustment and I highly doubt anyone would count on it being exact (except when

It's not exact in v1 anyway, so nobody can be depending on that.

>> Both values are reset to 0 before each clause is invoked.
>> 
>> alloca itself is fairly pedestrian given all that.  The size check is
>> fairly trivial: the only fiddly bit is the alignment (thanks to Kris Van
>> Hees for that).
>
> This becomes easier with the change mentioned above.  Not that is was
> difficult before.

I don't see how this bit changes at all. The fiddly bit is turning an
unaligned value into an aligned one, and we'd need to do that anyway
since the value in question is the *argument to alloca()*, and we're
surely not requiring that users only pass in multiples of 8 bytes to
alloca()!

>> Overly large allocations are unconditionally refused via a compile-time
>> error, before even generating any code, preventing the verifier from
>> concluding that too-large allocations can't succeed and therefore
>> the success branch in the alloca size check is unreachable code.
>
> No need to mention the part about the verifier.  That is subject to change
> anyway and might spark wondering minds (like mine) why that even matter since
> you would instead then do a size check in the generated code and avoid any
> verifier issues that way.

That might work now actually -- that code was added long before the
bounds checkers reached their current state. I can try tearing out the
oversize check if you prefer :)

>                            So I would just simply avoid that thought process.
> It is valid in its own right to do this at compile time anyway.

True enough!

>> +	/*
>> +	 * The size for this is twice what it needs to be, to allow us to bcopy
>
> s/bcopy/copy/
>
> since this would also affect copy-by-value of large structs etc...

True! When I wrote this I forgot that case.

>> +static void
>> +dt_cg_subr_alloca(dt_node_t *dnp, dt_irlist_t *dlp, dt_regset_t *drp)
>> +{
>> +	dt_node_t	*size = dnp->dn_args;
>> +	uint_t		lbl_ok = dt_irlist_label(dlp);
>> +	uint_t		lbl_err = dt_irlist_label(dlp);
>> +	int		opt_scratchsize = yypcb->pcb_hdl->dt_options[DTRACEOPT_SCRATCHSIZE];
>> +	int		mst, scratchbot, top, next;
>
> Get rid of 'top' and just use 'next' per comments above.  Seems contradictory
> but I think it makes more sense to work with a 'next' variable that will be
> used as ((*_TOP + size = 7) & -8) since that is really what you are needing.
> The old top value is in dnp->dn_reg.

Agreed.

>> +
>> +	TRACE_REGSET("    subr-alloca:Begin");
>> +
>> +	dt_cg_node(size, dlp, drp);
>> +
>> +	/*
>> +	 * Compile-error out if the size is too large even absent other
>> +	 * allocations.  (This prevents us generating code for which the
>> +	 * verifier will fail due to one branch of the conditional below being
>> +	 * determined to be unreachable.)
>> +	 */
>> +	if (size->dn_kind == DT_NODE_INT && size->dn_value > opt_scratchsize)
>> +		dnerror(dnp, D_ALLOCA_SIZE,
>> +			"alloca(%lu) size larger than scratchsize %lu\n",
>> +			(unsigned long) size->dn_value,
>> +			(unsigned long) opt_scratchsize);
>> +
>> +	if (((dnp->dn_reg = dt_regset_alloc(drp)) == -1) ||
>> +	    ((mst = dt_regset_alloc(drp)) == -1) ||
>> +	    ((scratchbot = dt_regset_alloc(drp)) == -1) ||
>> +	    ((top = dt_regset_alloc(drp)) == -1) ||
>> +	    ((next = dt_regset_alloc(drp)) == -1))
>> +		longjmp(yypcb->pcb_jmpbuf, EDT_NOREG);
>> +
>> +	/*
>> +	 *     %mst = DT_STK_DCTX->mst;		// lddw %mst, [%fp + DCTX_FP(DCTX_MST)]
>> +	 *     %scratchbot = DCTX_SCRATCHMEM;	// lddw %scratchbot, [%fp + DT_STK_DCTX]
>> +	 *					// add %scratchbot, DCTX_SCRATCHMEM
>> +	 *     %dn_reg = DMST_SCRATCH_NEXT;	// lddw %dn_reg, [%mst + DMST_SCRATCH_NEXT]
>> +	 *     %top = %dn_reg + size;		// mov %top, %dn_reg
>> +	 *     					// add %top, %size
>> +	 *     %next = %top + 7 & -8;		// mov %next, %top
>> +	 *					// add %next, 7
>> +	 *					// and %next, -8
>> +	 *     if (%top > opt_scratchsize) ||	// jgt %top, opt_scratchsize, lbl_ok
>> +	 *	   (%scratchbot > opt_scratchsize) // jgt %scratchbot, opt_scratchsize, lbl_err
>> +	 *	   goto lbl_err;
>> +	 *     goto lbl_ok;
>> +	 * lbl_err:
>> +	 *     probe_error(DTRACEFLT_NOSCRATCH);
>> +	 *
>> +	 * lbl_ok:
>> +	 *     DMST_SCRATCH_TOP = %top;		// stdw [%mst + DMST_SCRATCH_TOP], %top
>> +	 *     DMST_SCRATCH_NEXT = %next;	// stdw [%mst + DMST_SCRATCH_NEXT], %next
>> +	 *     %dn_reg += %scratchbot		// add %dn_reg, %scratchbot
>> +	 *     (result: %dn_reg)
>> +	 *
>> +	 */
>
> This comment block does not match the code.

Honestly I'm wondering if I even want to keep it. It's hard to maintain
and doesn't add much in clarity at all.

>> +	/*
>> +	 * Set the maximum scratch space permitted.
>> +	 */
>> +	dtp->dt_options[DTRACEOPT_SCRATCHSIZE] = _dtrace_scratchsize;
>
> Round up to 8-byte boundary.

No other option values are ever so rounded. Why is this one special?

-- 
NULL && (void)