[DTrace-devel] [PATCH] Avoid "::" in inet_ntoa6 output if no zero-words are collapsed

[Kris Van Hees]

Thanks for finding this flaw in the inet_ntoa6 implementation.  And showing
that the testcase was not covering all possibilities that are to be handled.

The solution you provide is unfortunately quite expensive due to the use of
a branch in a part of the code that is already being evaluated quite a few
times over by the verifier.  With my (expanded) test case of 11 inet-ntoa6
invocations, the original code (with the bug) took 132827 insns while your
patch increases that to 156281 insns.

Looking a bit more at the code, it is clear that this only happens when the
lookup table has the 0x70 value (as you point out) and in that case the
expected output is simply a list of 8 words separated by :, so it is actually
more efficient to just add a branch right after the table lookup, and generate
the output as 7 words with ':' appended, and then the final word.

Doing that with a simple loop for each word + ':' entry, and then adding the
output of the final word results in the BPF verifier evaluating only 137689
insns.

So that is merely an increase of 4862 insns (442 per inet_ntoa6 invocation)
as opposed to 23454 insns (2132 per invocation).

I'll post my patch shortly.

Again, thank you for pointing me at this problem.  And this again show just how
painful it can be to avoid extensive BPF verifier insn counts.

On Fri, Sep 01, 2023 at 01:04:21AM -0400, eugene.loh--- via DTrace-devel wrote:
> From: Eugene Loh <eugene.loh at oracle.com>
> 
> The case of no zero-words to collapse is the most common case in the
> lookup table!  (Entry 0x70 accounts for over 20% of the entries.)
> 
> Signed-off-by: Eugene Loh <eugene.loh at oracle.com>
> ---
>  bpf/inet_ntoa6.S                              |  9 +++++++++
>  .../funcs/inet_ntoa6/tst.inet_ntoa6.d         | 20 +++++++++++++++++++
>  .../funcs/inet_ntoa6/tst.inet_ntoa6.r         |  1 +
>  .../inet_ntoa6/tst.inet_ntoa6.strsize_40.r    |  2 +-
>  4 files changed, 31 insertions(+), 1 deletion(-)
> 
> diff --git a/bpf/inet_ntoa6.S b/bpf/inet_ntoa6.S
> index a4f56da8..7e4e284f 100644
> --- a/bpf/inet_ntoa6.S
> +++ b/bpf/inet_ntoa6.S
> @@ -286,6 +286,15 @@ dt_inet_ntoa6:
>  	add	%r1, %r0		/* #(words used) */
>  	jgt	%r1, 8, .Ldone
>  
> +	/*
> +	 * Special case:  if there are no collapsed zero-words, then the
> +	 * "::" should not appear.  Back the output up 1 byte, so that
> +	 * the two ':' will overwrite one another.
> +	 */
> +	jne	%r0, 0, .Lnorm
> +	add	%r9, -1
> +.Lnorm:
> +
>  	/*
>  	 * Calculate the number of words left to output, and advance the input
>  	 * pointer to the start of the remaining words.
> diff --git a/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.d b/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.d
> index 1f316afb..8eea1346 100644
> --- a/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.d
> +++ b/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.d
> @@ -14,6 +14,7 @@ struct in6_addr *ip6d;
>  struct in6_addr *ip6e;
>  struct in6_addr *ip6f;
>  struct in6_addr *ip6g;
> +struct in6_addr *ip6h;
>  
>  BEGIN
>  {
> @@ -24,6 +25,7 @@ BEGIN
>  	this->buf6e = alloca(sizeof(struct in6_addr));
>  	this->buf6f = alloca(sizeof(struct in6_addr));
>  	this->buf6g = alloca(sizeof(struct in6_addr));
> +	this->buf6h = alloca(sizeof(struct in6_addr));
>  	ip6a = this->buf6a;
>  	ip6b = this->buf6b;
>  	ip6c = this->buf6c;
> @@ -31,6 +33,7 @@ BEGIN
>  	ip6e = this->buf6e;
>  	ip6f = this->buf6f;
>  	ip6g = this->buf6g;
> +	ip6h = this->buf6h;
>  
>  	ip6a->in6_u.u6_addr8[0] = 0xfe;
>  	ip6a->in6_u.u6_addr8[1] = 0x80;
> @@ -61,6 +64,22 @@ BEGIN
>  	ip6g->in6_u.u6_addr8[11] = 0xfe;
>  	ip6g->in6_u.u6_addr8[12] = 0x7f;
>  	ip6g->in6_u.u6_addr8[15] = 0x01;
> +	ip6h->in6_u.u6_addr8[0] = 0xff;
> +	ip6h->in6_u.u6_addr8[1] = 0xff;
> +	ip6h->in6_u.u6_addr8[2] = 0xff;
> +	ip6h->in6_u.u6_addr8[3] = 0xff;
> +	ip6h->in6_u.u6_addr8[4] = 0xff;
> +	ip6h->in6_u.u6_addr8[5] = 0xff;
> +	ip6h->in6_u.u6_addr8[6] = 0xff;
> +	ip6h->in6_u.u6_addr8[7] = 0xff;
> +	ip6h->in6_u.u6_addr8[8] = 0xff;
> +	ip6h->in6_u.u6_addr8[9] = 0xff;
> +	ip6h->in6_u.u6_addr8[10] = 0xff;
> +	ip6h->in6_u.u6_addr8[11] = 0xff;
> +	ip6h->in6_u.u6_addr8[12] = 0xff;
> +	ip6h->in6_u.u6_addr8[13] = 0xff;
> +	ip6h->in6_u.u6_addr8[14] = 0xff;
> +	ip6h->in6_u.u6_addr8[15] = 0xff;
>  
>  	printf("%s\n", inet_ntoa6(ip6a));
>  	printf("%s\n", inet_ntoa6(ip6b));
> @@ -69,6 +88,7 @@ BEGIN
>  	printf("%s\n", inet_ntoa6(ip6e));
>  	printf("%s\n", inet_ntoa6(ip6f));
>  	printf("%s\n", inet_ntoa6(ip6g));
> +	printf("%s\n", inet_ntoa6(ip6h));
>  
>  	exit(0);
>  }
> diff --git a/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.r b/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.r
> index d87c1f61..c3cebd6d 100644
> --- a/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.r
> +++ b/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.r
> @@ -5,4 +5,5 @@ fe80::214:4fff:fe0b:76c8
>  127.0.0.1
>  127.0.0.1
>  ::fffe:7f00:1
> +ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff
>  
> diff --git a/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.strsize_40.r b/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.strsize_40.r
> index 3320cd34..cef7a61a 100644
> --- a/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.strsize_40.r
> +++ b/test/unittest/funcs/inet_ntoa6/tst.inet_ntoa6.strsize_40.r
> @@ -1,4 +1,4 @@
> -fe80:7060:5040:3080:3214:4fff:fe0b::76c8
> +fe80:7060:5040:3080:3214:4fff:fe0b:76c8
>  1080::808:c:417a
>  ::1
>  ::
> -- 
> 2.18.4
> 
> 
> _______________________________________________
> DTrace-devel mailing list
> DTrace-devel at oss.oracle.com
> https://oss.oracle.com/mailman/listinfo/dtrace-devel