[Tarantool-patches] [PATCH v2 2/2] base64: Improve decoder performance

[Sergey Nikiforov]

Hi.

On 17.12.2020 2:22, Vladislav Shpilevoy wrote:
> Hi! Thanks for the patch!
> 
> On 15.12.2020 15:22, Sergey Nikiforov wrote:
>> Unnecessary checks were removed from internal loops.
>> Benchmark shows that performance is now ~1.15 times higher
>> (release build, Intel Core I7-9700K, only one thread).
>> ---
>>
>> Branch: https://github.com/tarantool/tarantool/tree/void234/gh-3069-fix-base64-memory-overrun-v2
>>
>>   third_party/base64.c | 36 +++++++++++++++++++++++++-----------
>>   1 file changed, 25 insertions(+), 11 deletions(-)
>>
>> diff --git a/third_party/base64.c b/third_party/base64.c
>> index 3350a98ff..f4fbbf477 100644
>> --- a/third_party/base64.c
>> +++ b/third_party/base64.c
>> @@ -257,7 +257,7 @@ base64_decode_block(const char *in_base64, int in_len,
>>   		{
>>   	case step_a:
>>   			do {
>> -				if (in_pos == in_end || out_pos >= out_end)
>> +				if (in_pos >= in_end)
> 
> This test now crashes:
> 
> ====================
> --- a/test/unit/base64.c
> +++ b/test/unit/base64.c
> @@ -7,7 +7,7 @@ static void
>   base64_test(const char *str, int options, const char *no_symbols,
>   	    int no_symbols_len)
>   {
> -	plan(3 + no_symbols_len);
> +	plan(4 + no_symbols_len);
>   
>   	int len = strlen(str);
>   	int base64_buflen = base64_bufsize(len + 1, options);
> @@ -34,6 +34,11 @@ base64_test(const char *str, int options, const char *no_symbols,
>   	free(base64_buf);
>   	free(strbuf);
>   
> +	const char *in = "sIIpHw==";
> +	int in_len = strlen(in);
> +	rc = base64_decode(in, in_len, NULL, 0);
> +	is(rc, 0, "no space in out buffer");
> +
>   	check_plan();
>   }
> ====================
> 
> It didn't crash while the checks were in place.

I knew about this "problem" even before first patch version. Glad 
someone noticed. More on that below.

> I would suggest to
> add this test to the previous commit. Because technically it is
> also 'buffer overrun'. And it will crash 3069 bug even without ASAN.

I do not think this is a good idea.

Both old code and your proposed change (below) behave like this: if 
output buffer size if 0, stop everything and return zero. No input chars 
are decoded even when this is possible (no "stored" bits in state - aka 
"step_a" - and only one valid input char with 6 new bits). My 
"optimized" code already handles such situation properly. And this is 
"free" (no extra if's).

It is of course possible to process "zero output buffer size" situation 
properly but it would require additional "if" in base64_decode_block() 
beginning and some logic - and in every case except "step_a with no more 
than one useful input char" would cause some input characters to be lost 
anyway. Existing API for base64_decode() completely ignores situation 
when output buffer is too small (it is easy to calculate worst-case 
output buffer size) - not-yet-processed input data is ignored in such 
case. No reasonable programmer would use "0" as output buffer size. Such 
requirement is even DOCUMENTED in base64.h.

What would you say?

> For this patch you may want to add a zero length in the beginning.
> Also we can keep the number of 'if's unchanged like this:
> 
> ====================
> --- a/third_party/base64.c
> +++ b/third_party/base64.c
> @@ -256,6 +256,12 @@ base64_decode_block(const char *in_base64, int in_len,
>   		while (1)
>   		{
>   	case step_a:
> +			if (out_pos >= out_end)
> +			{
> +				state->step = step_a;
> +				state->result = curr_byte;
> +				return out_pos - out_bin;
> +			}
>   			do {
>   				if (in_pos >= in_end)
>   				{
> @@ -316,12 +322,7 @@ base64_decode_block(const char *in_base64, int in_len,
>   			} while (fragment < 0);
>   			curr_byte |= (fragment & 0x03f);
>   			*out_pos = curr_byte;
> -			if (++out_pos >= out_end)
> -			{
> -				state->step = step_a;
> -				state->result = curr_byte;
> -				return out_pos - out_bin;
> -			}
> +			++out_pos;
>   		}
>   	}
>   	/* control should not reach here */
> ====================
> 
> Will that work?

Yes, but it would lose data when (out_len == 0), (state->step == step_a) 
and there is one useful char in input buffer. Not that it matter in real 
life.