[DTrace-devel] [PATCH 5/8] Add support for index() subroutine
eugene.loh at oracle.com
eugene.loh at oracle.com
Wed Sep 29 08:13:38 PDT 2021
From: Eugene Loh <eugene.loh at oracle.com>
Signed-off-by: Eugene Loh <eugene.loh at oracle.com>
---
bpf/Build | 1 +
bpf/index.S | 206 +++++++++++++++++++++++++++++++
libdtrace/dt_cg.c | 63 +++++++++-
libdtrace/dt_dlibs.c | 1 +
test/unittest/dif/index2arg.d | 1 -
test/unittest/dif/index3arg.d | 1 -
test/unittest/funcs/tst.index2.d | 48 +++++++
test/unittest/funcs/tst.index2.r | 23 ++++
8 files changed, 341 insertions(+), 3 deletions(-)
create mode 100644 bpf/index.S
create mode 100644 test/unittest/funcs/tst.index2.d
create mode 100644 test/unittest/funcs/tst.index2.r
diff --git a/bpf/Build b/bpf/Build
index 6e9ffa20..5f359293 100644
--- a/bpf/Build
+++ b/bpf/Build
@@ -25,6 +25,7 @@ bpf_dlib_SOURCES = \
agg_lqbin.c agg_qbin.c \
get_bvar.c \
get_tvar.c set_tvar.c \
+ index.S \
probe_error.c \
strchr.S \
strcmp.S \
diff --git a/bpf/index.S b/bpf/index.S
new file mode 100644
index 00000000..2ec9f133
--- /dev/null
+++ b/bpf/index.S
@@ -0,0 +1,206 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (c) 2021, Oracle and/or its affiliates. All rights reserved.
+ */
+
+#define DT_STRLEN_BYTES 2
+
+#define BPF_FUNC_probe_read 4
+#define BPF_FUNC_probe_read_str 45
+
+ .text
+/*
+ * For two buffers, return:
+ * 1 if the two buffers match in every bit
+ * 0 if the two buffers mismatch in any bit
+ * To help the BPF verifier, minimize branching by:
+ * - using a len whose exact value is known to the BPF verifier
+ * - operating on 64 bits at a time (len is a multiple of 8)
+ * - replacing conditional branching with arithmetic operations
+ * such as ^ | & etc.
+ *
+ * uint64_t dt_index_match(char *tmp1, char *tmp2, uint64_t len)
+ * {
+ * r0 = 0; // accumulate bits indicating mismatches
+ * r6 = 0; // loop counter
+ * L1:
+ * if (r6 >= len) goto L2;
+ *
+ * r4 = *((uint64_t*)&tmp1[r6]);
+ * r5 = *((uint64_t*)&tmp2[r6]);
+ * r0 |= (r4 ^ r5);
+ *
+ * r6 += 8;
+ * goto L1;
+ *
+ * L2:
+ * // value of r0
+ * // perfect match any mismatches
+ * // == 0 != 0
+ * r0 |= (r0 >> 32); // == 0 != 0
+ * r0 &= 0xffffffff; // == 0 > 0
+ * r0 -= 1; // < 0 >= 0
+ * r0 >>= 63; // == 1 == 0
+ *
+ * return r0;
+ * }
+ */
+ .align 4
+ .global dt_index_match
+dt_index_match:
+ mov %r0, 0
+ mov %r6, 0
+
+.L1:
+ jge %r6, %r3, .L2
+
+ mov %r4, %r1
+ add %r4, %r6
+ ldxdw %r4, [%r4+0]
+ mov %r5, %r2
+ add %r5, %r6
+ ldxdw %r5, [%r5+0]
+ xor %r4, %r5
+ or %r0, %r4
+
+ add %r6, 8
+ ja .L1
+
+.L2:
+ mov %r4, %r0
+ rsh %r4, 32
+ or %r0, %r4
+ and %r0, 0xffffffff
+ sub %r0, 1
+ rsh %r0, 63
+
+ exit
+
+/*
+ * int dt_index(const char *s, const char *t, int start, char *tmp1, char *tmp2)
+ * {
+ * uint64_t r0, tlen;
+ * uint64_t buflen;
+ *
+ * // ignore length prefix
+ * s += DT_STRLEN_BYTES;
+ * t += DT_STRLEN_BYTES;
+ *
+ * // determine actual start index
+ * if (start < 0) start = 0;
+ *
+ * // round buflen for dt_index_match()
+ * buflen = STRSZ rounded up to multiple of 8;
+ *
+ * // keep a copy of t in tmp2
+ * tlen = bpf_probe_read_str(tmp2, buflen, t);
+ *
+ * // determine maximum possible index value
+ * maxi = bpf_probe_read_str(tmp1, buflen, s);
+ * maxi -= tlen;
+ *
+ * // drop terminating NULL
+ * tlen--;
+ *
+ * // Fill end of tmp1 with contents from tmp2
+ * // to suppress spurious mismatches.
+ * bpf_probe_read(tmp1 + tlen, buflen - tlen, tmp2 + tlen);
+ *
+ * Lloop:
+ * // check loop
+ * if (start > maxi) return -1;
+ *
+ * // fill start of tmp1 with s, starting at the proposed index
+ * bpf_probe_read(tmp1, tlen, s + start);
+ *
+ * // keep looping if not a match
+ * r0 = dt_index_match(tmp1, tmp2, buflen);
+ * start++;
+ * if (r0 == 0) goto Lloop;
+ *
+ * start--;
+ * return start;
+ * }
+ *
+ * Some variables are kept in registers or spilled to the stack:
+ * r6 = start [%fp+-8] = s
+ * r7 = tmp1 [%fp+-16] = buflen
+ * r8 = tmp2 [%fp+-24] = maxi
+ * r9 = tlen
+ * but t is not needed once we have copied its contents to tmp2.
+ */
+ .align 4
+ .global dt_index
+dt_index:
+ add %r1, DT_STRLEN_BYTES /* s += DT_STRLEN_BYTES */
+ add %r2, DT_STRLEN_BYTES /* t += DT_STRLEN_BYTES */
+
+ jsge %r3, 0, 1
+ mov %r3, 0 /* if (start < 0) start = 0 */
+
+ lddw %r6, STRSZ
+ add %r6, 7
+ and %r6, -8
+ stxdw [%fp+-16], %r6 /* buflen = STRSZ rounded up to multiple of 8 */
+
+ stxdw [%fp+-8], %r1 /* stash copies of some variables */
+ mov %r6, %r3
+ mov %r7, %r4
+ mov %r8, %r5
+
+ mov %r3, %r2
+ ldxdw %r2, [%fp+-16]
+ mov %r1, %r8
+ call BPF_FUNC_probe_read_str /* tlen = bpf_probe_read_str(tmp2, buflen, t) */
+ jsle %r0, 0, .Lerror
+ mov %r9, %r0
+
+ mov %r1, %r7
+ ldxdw %r2, [%fp+-16]
+ ldxdw %r3, [%fp+-8]
+ call BPF_FUNC_probe_read_str /* maxi = bpf_probe_read_str(tmp1, buflen, s) */
+
+ sub %r0, %r9 /* maxi -= tlen */
+ jslt %r0, 0, .Lerror
+ stxdw [%fp+-24], %r0
+
+ sub %r9, 1 /* tlen-- */
+
+ mov %r1, %r7
+ add %r1, %r9
+ ldxdw %r2, [%fp+-16]
+ sub %r2, %r9
+ mov %r3, %r8
+ add %r3, %r9
+ call BPF_FUNC_probe_read /* bpf_probe_read(tmp1 + tlen, buflen - tlen, tmp2 + tlen) */
+
+.Lloop:
+ /* help the BPF verifier */
+ ldxdw %r0, [%fp+-16]
+ jge %r6, %r0, .Lerror /* if (start >= buflen) goto Lerror */
+
+ ldxdw %r0, [%fp+-24]
+ jgt %r6, %r0, .Lerror /* if (start > maxi) goto Lerror */
+
+ mov %r1, %r7
+ mov %r2, %r9
+ ldxdw %r3, [%fp+-8]
+ add %r3, %r6
+ call BPF_FUNC_probe_read /* bpf_probe_read(tmp1, tlen, s + start) */
+
+ mov %r1, %r7
+ mov %r2, %r8
+ ldxdw %r3, [%fp+-16]
+ call dt_index_match /* r0 = dt_index_match(tmp1, tmp2, buflen) */
+
+ add %r6, 1 /* start++ */
+ jeq %r0, 0, .Lloop /* if (r0 == 0) goto Lloop */
+
+ /* done */
+ sub %r6, 1 /* start-- */
+ mov %r0, %r6 /* return start */
+ exit
+
+.Lerror:
+ mov %r0, -1
+ exit
diff --git a/libdtrace/dt_cg.c b/libdtrace/dt_cg.c
index cb58f230..49403986 100644
--- a/libdtrace/dt_cg.c
+++ b/libdtrace/dt_cg.c
@@ -3170,6 +3170,67 @@ dt_cg_array_op(dt_node_t *dnp, dt_irlist_t *dlp, dt_regset_t *drp)
emit(dlp, BPF_ALU64_REG((dnp->dn_flags & DT_NF_SIGNED) ? BPF_ARSH : BPF_RSH, dnp->dn_reg, n));
}
+static void
+dt_cg_subr_index(dt_node_t *dnp, dt_irlist_t *dlp, dt_regset_t *drp)
+{
+ dt_node_t *s = dnp->dn_args;
+ dt_node_t *t = s->dn_list;
+ dt_node_t *start = t->dn_list;
+ dt_ident_t *idp = dt_dlib_get_func(yypcb->pcb_hdl, "dt_index");
+ uint64_t off1, off2;
+
+ assert(idp != NULL);
+
+ TRACE_REGSET(" subr-index:Begin");
+
+ dt_cg_node(s, dlp, drp);
+ dt_cg_check_notnull(dlp, drp, s->dn_reg);
+ dt_cg_node(t, dlp, drp);
+ dt_cg_check_notnull(dlp, drp, t->dn_reg);
+ if (start != NULL)
+ dt_cg_node(start, dlp, drp);
+
+ if (dt_regset_xalloc_args(drp) == -1)
+ longjmp(yypcb->pcb_jmpbuf, EDT_NOREG);
+ emit(dlp, BPF_MOV_REG(BPF_REG_1, s->dn_reg));
+ dt_regset_free(drp, s->dn_reg);
+ if (s->dn_tstring)
+ dt_cg_tstring_free(yypcb, s);
+ emit(dlp, BPF_MOV_REG(BPF_REG_2, t->dn_reg));
+ dt_regset_free(drp, t->dn_reg);
+ if (t->dn_tstring)
+ dt_cg_tstring_free(yypcb, t);
+ if (start) {
+ emit(dlp, BPF_MOV_REG(BPF_REG_3, start->dn_reg));
+ dt_regset_free(drp, start->dn_reg);
+ } else
+ emit(dlp, BPF_MOV_IMM(BPF_REG_3, 0));
+
+ off1 = dt_cg_tstring_xalloc(yypcb);
+ off2 = dt_cg_tstring_xalloc(yypcb);
+
+ emit(dlp, BPF_LOAD(BPF_DW, BPF_REG_4, BPF_REG_FP, DT_STK_DCTX));
+ emit(dlp, BPF_LOAD(BPF_DW, BPF_REG_4, BPF_REG_4, DCTX_MEM));
+ emit(dlp, BPF_MOV_REG(BPF_REG_5, BPF_REG_4));
+ emit(dlp, BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, off1));
+ emit(dlp, BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, off2));
+
+ dt_regset_xalloc(drp, BPF_REG_0);
+ emite(dlp, BPF_CALL_FUNC(idp->di_id), idp);
+ dt_regset_free_args(drp);
+
+ dt_cg_tstring_xfree(yypcb, off1);
+ dt_cg_tstring_xfree(yypcb, off2);
+
+ dnp->dn_reg = dt_regset_alloc(drp);
+ if (dnp->dn_reg == -1)
+ longjmp(yypcb->pcb_jmpbuf, EDT_NOREG);
+ emit(dlp, BPF_MOV_REG(dnp->dn_reg, BPF_REG_0));
+ dt_regset_free(drp, BPF_REG_0);
+
+ TRACE_REGSET(" subr-index:End ");
+}
+
static void
dt_cg_subr_speculation(dt_node_t *dnp, dt_irlist_t *dlp, dt_regset_t *drp)
{
@@ -3463,7 +3524,7 @@ static dt_cg_subr_f *_dt_cg_subr[DIF_SUBR_MAX + 1] = {
[DIF_SUBR_STRSTR] = NULL,
[DIF_SUBR_STRTOK] = NULL,
[DIF_SUBR_SUBSTR] = &dt_cg_subr_substr,
- [DIF_SUBR_INDEX] = NULL,
+ [DIF_SUBR_INDEX] = &dt_cg_subr_index,
[DIF_SUBR_RINDEX] = NULL,
[DIF_SUBR_HTONS] = &dt_cg_subr_htons,
[DIF_SUBR_HTONL] = &dt_cg_subr_htonl,
diff --git a/libdtrace/dt_dlibs.c b/libdtrace/dt_dlibs.c
index d9836f40..1fec0147 100644
--- a/libdtrace/dt_dlibs.c
+++ b/libdtrace/dt_dlibs.c
@@ -59,6 +59,7 @@ static const dt_ident_t dt_bpf_symbols[] = {
DT_BPF_SYMBOL(dt_get_string, DT_IDENT_SYMBOL),
DT_BPF_SYMBOL(dt_get_tvar, DT_IDENT_SYMBOL),
DT_BPF_SYMBOL(dt_set_tvar, DT_IDENT_SYMBOL),
+ DT_BPF_SYMBOL(dt_index, DT_IDENT_SYMBOL),
DT_BPF_SYMBOL(dt_strchr, DT_IDENT_SYMBOL),
DT_BPF_SYMBOL(dt_strcmp, DT_IDENT_SYMBOL),
DT_BPF_SYMBOL(dt_strjoin, DT_IDENT_SYMBOL),
diff --git a/test/unittest/dif/index2arg.d b/test/unittest/dif/index2arg.d
index 7d80538f..7eb8f15b 100644
--- a/test/unittest/dif/index2arg.d
+++ b/test/unittest/dif/index2arg.d
@@ -1,4 +1,3 @@
-/* @@xfail: dtv2 */
BEGIN
{
exit(index("BEGINNING", "G") == 2 ? 0 : 1);
diff --git a/test/unittest/dif/index3arg.d b/test/unittest/dif/index3arg.d
index d8c3db4f..886ba93e 100644
--- a/test/unittest/dif/index3arg.d
+++ b/test/unittest/dif/index3arg.d
@@ -1,4 +1,3 @@
-/* @@xfail: dtv2 */
BEGIN
{
exit(index("BEGINNING", "G", 3) == 8 ? 0 : 1);
diff --git a/test/unittest/funcs/tst.index2.d b/test/unittest/funcs/tst.index2.d
new file mode 100644
index 00000000..cf3cb92a
--- /dev/null
+++ b/test/unittest/funcs/tst.index2.d
@@ -0,0 +1,48 @@
+/*
+ * Oracle Linux DTrace.
+ * Copyright (c) 2021, 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.
+ */
+
+#pragma D option quiet
+
+/* cut string size back a little to ease pressure on BPF verifier */
+#pragma D option strsize=184
+
+BEGIN {
+ x = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789@#abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789@#";
+ y = "abcdefghijklmnopqrstuvwxyz";
+ printf(" 0 %3d\n", index(x, y));
+ printf(" 0 %3d\n", index(x, y, -1));
+ printf(" 0 %3d\n", index(x, y, 0));
+ printf(" 64 %3d\n", index(x, y, 1));
+ printf(" -1 %3d\n", index(x, y, 100));
+ printf(" -1 %3d\n", index(x, y, 200));
+
+ y = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789@#a";
+ printf(" 0 %3d\n", index(x, y, -1));
+ printf(" 0 %3d\n", index(x, y));
+ printf(" -1 %3d\n", index(x, y, 1));
+
+ x = "";
+ y = "klmnopqrstuvw";
+ printf(" -1 %3d\n", index(x, y));
+ printf(" 0 %3d\n", index(y, x));
+
+ x = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
+ y = "klmnopqrstuvw";
+ printf(" 10 %3d\n", index(x, y, -1));
+ printf(" 10 %3d\n", index(x, y));
+ printf(" 10 %3d\n", index(x, y, 10));
+ printf(" 36 %3d\n", index(x, y, 20));
+ printf(" 36 %3d\n", index(x, y, 30));
+ printf(" 62 %3d\n", index(x, y, 40));
+ printf(" 62 %3d\n", index(x, y, 50));
+ printf(" 62 %3d\n", index(x, y, 60));
+ printf(" 88 %3d\n", index(x, y, 70));
+ printf(" 88 %3d\n", index(x, y, 80));
+ printf("114 %3d\n", index(x, y, 90));
+
+ exit(0);
+}
diff --git a/test/unittest/funcs/tst.index2.r b/test/unittest/funcs/tst.index2.r
new file mode 100644
index 00000000..0372e9f5
--- /dev/null
+++ b/test/unittest/funcs/tst.index2.r
@@ -0,0 +1,23 @@
+ 0 0
+ 0 0
+ 0 0
+ 64 64
+ -1 -1
+ -1 -1
+ 0 0
+ 0 0
+ -1 -1
+ -1 -1
+ 0 0
+ 10 10
+ 10 10
+ 10 10
+ 36 36
+ 36 36
+ 62 62
+ 62 62
+ 62 62
+ 88 88
+ 88 88
+114 114
+
--
2.18.4
More information about the DTrace-devel
mailing list