[DTrace-devel] [PATCH] Signed divide and mod are broken
Kris Van Hees
kris.van.hees at oracle.com
Fri Aug 21 23:22:07 PDT 2020
On Fri, Aug 21, 2020 at 05:50:18PM -0400, eugene.loh at oracle.com wrote:
> From: Eugene Loh <eugene.loh at oracle.com>
>
> Consider
> trace(-2700 / 1000);
> trace(-2700 % 1000);
>
> versus
> x = -2700;
> y = 1000;
> trace(x / y);
> trace(x % y);
>
> The first correctly gives -2 and -700, while the second incorrectly
> gives -1700 and -1700.
>
> The problem is that we pass obsolete DIF_OP_SDIV and DIF_OP_SREM op
> codes, whose numeric values translate to BPF_ADD operations. There
> are no signed DIV or MOD operations in BPF.
>
> Fix by handling the signs ourselves. Also, clean up tests so that
> such a problem would be discovered.
Nice catch. See below for an improvement in the implementation...
> Orabug: 31783034
> Signed-off-by: Eugene Loh <eugene.loh at oracle.com>
> ---
> libdtrace/dt_cg.c | 67 +++++++++++++++++++++++----
> test/unittest/arithmetic/tst.basics.d | 4 +-
> test/unittest/arithmetic/tst.basics.r | 8 ++++
> test/unittest/arithmetic/tst.moddiv.d | 26 +++++++++++
> test/unittest/arithmetic/tst.moddiv.r | 1 +
> 5 files changed, 94 insertions(+), 12 deletions(-)
> create mode 100644 test/unittest/arithmetic/tst.basics.r
> create mode 100644 test/unittest/arithmetic/tst.moddiv.d
> create mode 100644 test/unittest/arithmetic/tst.moddiv.r
>
> diff --git a/libdtrace/dt_cg.c b/libdtrace/dt_cg.c
> index d5532c55..896243a9 100644
> --- a/libdtrace/dt_cg.c
> +++ b/libdtrace/dt_cg.c
> @@ -1606,6 +1606,7 @@ dt_cg_arithmetic_op(dt_node_t *dnp, dt_irlist_t *dlp, dt_regset_t *drp,
>
> int lp_is_ptr = dt_node_is_pointer(dnp->dn_left);
> int rp_is_ptr = dt_node_is_pointer(dnp->dn_right);
> + int lsignreg, rsignreg, signflag;
>
> struct bpf_insn instr;
>
> @@ -1622,9 +1623,61 @@ dt_cg_arithmetic_op(dt_node_t *dnp, dt_irlist_t *dlp, dt_regset_t *drp,
> if (is_ptr_op && lp_is_ptr)
> dt_cg_ptrsize(dnp, dlp, drp, BPF_MUL, dnp->dn_right->dn_reg);
>
> - instr = BPF_ALU64_REG(op, dnp->dn_left->dn_reg, dnp->dn_right->dn_reg);
> + /* BPF_DIV and BPF_MOD are only for unsigned arguments */
> + signflag = (op == BPF_MOD || op == BPF_DIV) &&
> + (dnp->dn_flags & DT_NF_SIGNED);
> + if (signflag) {
> + /* allocate registers to hold the signs of the arguments */
> + lsignreg = dt_regset_alloc(drp);
> + rsignreg = dt_regset_alloc(drp);
> + if (lsignreg == -1 || rsignreg == -1)
> + longjmp(yypcb->pcb_jmpbuf, EDT_NOREG);
> +
> + /*
> + * Determine the signs of the arguments as follows:
> + * sign = arg; // copy the arg
> + * sign >>= 63; // sign-extended, arithmetic shift
> + * sign |= 1; // convert [0|-1] to [1|-1]
> + */
> + instr = BPF_MOV_REG(lsignreg, dnp->dn_left->dn_reg);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> + instr = BPF_MOV_REG(rsignreg, dnp->dn_right->dn_reg);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> + instr = BPF_ALU64_IMM(BPF_ARSH, lsignreg, 64 - 1);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> + instr = BPF_ALU64_IMM(BPF_ARSH, rsignreg, 64 - 1);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> + instr = BPF_ALU64_IMM(BPF_OR, lsignreg, 1);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> + instr = BPF_ALU64_IMM(BPF_OR, rsignreg, 1);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> +
> + /* multiply arguments by their signs to make them positive */
> + instr = BPF_ALU64_REG(BPF_MUL, dnp->dn_left->dn_reg, lsignreg);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> + instr = BPF_ALU64_REG(BPF_MUL, dnp->dn_right->dn_reg, rsignreg);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> + }
>
> + instr = BPF_ALU64_REG(op, dnp->dn_left->dn_reg, dnp->dn_right->dn_reg);
> dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> +
> + if (signflag) {
> + /* apply the signs to the result */
> + instr = BPF_ALU64_REG(BPF_MUL, dnp->dn_left->dn_reg, lsignreg);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> + instr = BPF_ALU64_REG(BPF_MUL, dnp->dn_left->dn_reg, rsignreg);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> +
> + /* restore the sign of the right-hand argument */
> + instr = BPF_ALU64_REG(BPF_MUL, dnp->dn_right->dn_reg, rsignreg);
> + dt_irlist_append(dlp, dt_cg_node_alloc(DT_LBL_NONE, instr));
> +
> + /* free the sign registers */
> + dt_regset_free(drp, rsignreg);
> + dt_regset_free(drp, lsignreg);
> + }
> +
First of all, there is no need to restore the sign on the RHS operand because
that register is going to be thrown away anyway (LHS is replaced with the
result, RHS is thrown away).
The code you provide is elegant but requires signed DIV and MOD to always
execute 12 instructions. By making use of conditional branch instructions
you can reduce this to 4 instructions in the best case scenario (both operands
are positive) and 6 instructions in the worst case scenario (operands have
different signs). The implementation is as follows (in BPF code):
a > 0 a > 0 a < 0 a < 0
b > 0 b < 0 b > 0 b < 0
0001 jslt %r1,0,L3 1 1 1 1
0002 jslt %r2,0,L1 2 2
0003 ja L4 3
L1: 0004 neg %r2 3
L2: 0005 div %r1,%r2 4 4
0006 neg %r1 5 5
0007 ja L5 6 6
L3: 0008 neg %r1 2 2
0009 jsge %r2,0,L2 3 3
0010 neg %r2 4
L4: 0011 div %r1,%r2 4 5
L5: 0012 nop
The nop instruction will be removed when the assembler processes all the
generated instructions. It only appears here because you need to insert it
so that the L5 label can be placed on it.
The 4 columsn on the right show the instruction flow (and count) for the four
different cases. The fact that BPF provides conditional branches for signed
operands is a saving grace here.
The other benefit of doing it this way is also that no additional registers
are needed.
> dt_regset_free(drp, dnp->dn_right->dn_reg);
> dnp->dn_reg = dnp->dn_left->dn_reg;
>
> @@ -2380,14 +2433,12 @@ dt_cg_node(dt_node_t *dnp, dt_irlist_t *dlp, dt_regset_t *drp)
> break;
>
> case DT_TOK_DIV_EQ:
> - dt_cg_arithmetic_op(dnp, dlp, drp,
> - (dnp->dn_flags & DT_NF_SIGNED) ? DIF_OP_SDIV : BPF_DIV);
> + dt_cg_arithmetic_op(dnp, dlp, drp, BPF_DIV);
> dt_cg_asgn_op(dnp, dlp, drp);
> break;
>
> case DT_TOK_MOD_EQ:
> - dt_cg_arithmetic_op(dnp, dlp, drp,
> - (dnp->dn_flags & DT_NF_SIGNED) ? DIF_OP_SREM : BPF_MOD);
> + dt_cg_arithmetic_op(dnp, dlp, drp, BPF_MOD);
> dt_cg_asgn_op(dnp, dlp, drp);
> break;
>
> @@ -2495,13 +2546,11 @@ dt_cg_node(dt_node_t *dnp, dt_irlist_t *dlp, dt_regset_t *drp)
> break;
>
> case DT_TOK_DIV:
> - dt_cg_arithmetic_op(dnp, dlp, drp,
> - (dnp->dn_flags & DT_NF_SIGNED) ? DIF_OP_SDIV : BPF_DIV);
> + dt_cg_arithmetic_op(dnp, dlp, drp, BPF_DIV);
> break;
>
> case DT_TOK_MOD:
> - dt_cg_arithmetic_op(dnp, dlp, drp,
> - (dnp->dn_flags & DT_NF_SIGNED) ? DIF_OP_SREM : BPF_MOD);
> + dt_cg_arithmetic_op(dnp, dlp, drp, BPF_MOD);
> break;
>
> case DT_TOK_LNEG:
> diff --git a/test/unittest/arithmetic/tst.basics.d b/test/unittest/arithmetic/tst.basics.d
> index dceadf48..300a0079 100644
> --- a/test/unittest/arithmetic/tst.basics.d
> +++ b/test/unittest/arithmetic/tst.basics.d
> @@ -5,13 +5,11 @@
> * http://oss.oracle.com/licenses/upl.
> */
>
> -/* @@note: wild negative numbers, tst.basics.d.out does not exist: validate */
> -
> /*
> * ASSERTION:
> * Simple Arithmetic expressions.
> * Call simple expressions and make sure test succeeds.
> - * Match expected output in tst.basics.d.out
> + * Match expected output in tst.basics.r
> *
> * SECTION: Types, Operators, and Expressions/Arithmetic Operators
> *
> diff --git a/test/unittest/arithmetic/tst.basics.r b/test/unittest/arithmetic/tst.basics.r
> new file mode 100644
> index 00000000..d3b6af81
> --- /dev/null
> +++ b/test/unittest/arithmetic/tst.basics.r
> @@ -0,0 +1,8 @@
> +The value of i is 6
> +The value of i is 18
> +The value of i is 72
> +The value of i is 25920
> +The value of i is 935761216
> +The value of i is -91738734
> +The value of i is -91738729
> +
> diff --git a/test/unittest/arithmetic/tst.moddiv.d b/test/unittest/arithmetic/tst.moddiv.d
> new file mode 100644
> index 00000000..d80ec003
> --- /dev/null
> +++ b/test/unittest/arithmetic/tst.moddiv.d
> @@ -0,0 +1,26 @@
> +/*
> + * Oracle Linux DTrace.
> + * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
> + * Licensed under the Universal Permissive License v 1.0 as shown at
> + * http://oss.oracle.com/licenses/upl.
> + */
> +
> +/*
> + * ASSERTION:
> + * Simple mod and div expressions should work correctly,
> + * even for signed operations.
> + *
> + * SECTION: Types, Operators, and Expressions/Arithmetic Operators
> + *
> + */
> +
> +#pragma D option quiet
> +
> +BEGIN {
> + x = 19; y = 5;
> + trace(( x) / ( y)); trace (( x) % ( y));
> + trace(( x) / (-y)); trace (( x) % (-y));
> + trace((-x) / ( y)); trace ((-x) % ( y));
> + trace((-x) / (-y)); trace ((-x) % (-y));
> + exit(0)
> +}
> diff --git a/test/unittest/arithmetic/tst.moddiv.r b/test/unittest/arithmetic/tst.moddiv.r
> new file mode 100644
> index 00000000..3fc9bc14
> --- /dev/null
> +++ b/test/unittest/arithmetic/tst.moddiv.r
> @@ -0,0 +1 @@
> +34-3-4-3-434
> --
> 2.18.4
>
>
> _______________________________________________
> DTrace-devel mailing list
> DTrace-devel at oss.oracle.com
> https://oss.oracle.com/mailman/listinfo/dtrace-devel
More information about the DTrace-devel
mailing list