Re: [PATCH v2 2/4] string-list: replace negative index encoding with "exact_match" parameter

[Collin Funk <collin.funk1@gmail.com>]

Junio C Hamano <gitster@pobox.com> writes:

> Jeff King <peff@peff.net> writes:
>
>> I agree that size_t is much more than one needs for counting most
>> things. But the problem is that "int" is much too small, if you are
>> worried about malicious input causing integer overflows that could cause
>> memory access errors.
>
> Well, a malicious input can cause overflow/wraparound size_t while
> parsing, so I do not think that is really an argument.
>
> The code need to be protected against such overflows either way.

Apologies for jumping into this thread so long after it happened, but I
wanted to voice my agreement with Junio here and mention another
consideration.

In GNU Coreutils and Gnulib we often use 'idx_t', which is a typedef to
the standard signed type 'ptrdiff_t', when we refer to allocation of
objects or indexes.

The rational is written in the header file where it is defined [1].
However, I want to highlight one part that I find most useful:

     * Security: Signed types can be checked for overflow via
       '-fsanitize=undefined', but unsigned types cannot.

On common platforms, you will never need to allocate more memory than
PTRDIFF_MAX anyways:

    $ numfmt --to=iec-i `echo $(((1 << 63) - 1))`
    8.0Ei

I think that addresses Jeff's point that 'int' is too small, which I
agree with.

In C23 it is also easy to do wraparound arithmetic on signed integers if
you want to. Here is an example:

    $ cat main.c 
    #include <stdio.h>
    #include <inttypes.h>
    #include <stddef.h>
    #include <stdckdint.h>
    int
    main (void)
    {
      ptrdiff_t value = PTRDIFF_MAX;
      if (! ckd_add (&value, value, 1))
        printf ("No overflow\n");
      else
        {
          /* Or handle overflow.  */
          printf ("%td\n", value);
          printf ("%td\n", PTRDIFF_MIN);
        }
      return 0;
    }
    $ gcc -std=gnu23 main.c 
    $ ./a.out 
    -9223372036854775808
    -9223372036854775808

Paul Eggert wrote some macros to implement these on old compilers which
is very helpful [2] [3]. They only assume that signed integers are two's
complement without padding bits (I would hope that git doesn't have to
support anything else...).

Collin

[1] https://github.com/coreutils/gnulib/blob/master/lib/idx.h
[2] https://github.com/coreutils/gnulib/blob/master/lib/intprops.h
[3] https://github.com/coreutils/gnulib/blob/master/lib/stdckdint.in.h