Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

[Jeff King <peff@peff.net>]

On Tue, Nov 17, 2020 at 06:16:05PM -0800, Jonathan Nieder wrote:

> Since this came up in [1], I took a glance at this.
> 
> I also think it looks reasonable, though it's possible to do better if
> we're willing to (1) cast between pointers to function with different
> signatures, which is portable in practice but I don't believe the C
> standard speaks to and (2) conditionally make use of gcc extensions,
> for typechecking.

The C standard definitely is not OK with calling a function through a
wrong declaration or cast. I won't find chapter and verse, but here's a
practical example:

-- >8 --
#include <stdio.h>
#include <stdint.h>

void foo(uint32_t a, uint32_t b)
{
	printf("got a = %u\n", a);
	printf("got b = %u\n", b);
}

typedef void (*almost_foo)(uint64_t, uint64_t);

int main(void)
{
	almost_foo bar = (almost_foo)foo;

	printf("real call:\n");
	foo(1, 2);
	printf("via cast:\n");
	bar(3, 4);
	return 0;
}
-- >8 --

The caller thinks it's passing uint64_t integers, but the function
thinks it's getting uint32_t integers. The output will depend on your
calling conventions. If I compile it on my 64-bit Linux machine, it
produces what you'd expect:

  $ gcc foo.c
  $ ./a.out
  real call:
  got a = 1
  got b = 2
  via cast:
  got a = 3
  got b = 4

That's because we're using the System V AMD64 ABI convention, which
passes the first six parameters via registers. And even after that, each
parameter on the stack uses 8 bytes (even if it's smaller), so the two
representations are equivalent.

But if I compile it in 32-bit mode, it doesn't work:

  $ gcc -m32 foo.c
  $ ./a.out
  real call:
  got a = 1
  got b = 2
  via cast:
  got a = 3
  got b = 0

That's because it's using the cdecl convention, which puts everything on
the stack, and which uses a minimum of 4 bytes per parameter. So each
64-bit value results in two 32-bit pushes onto the stack (of 0, and 3).

Now in practice you're probably fine as long as the number and sizes of
the parameters are the same between the function definition and what the
caller casts to. And so if we're talking about casting individual
parameters between a void parameter and another pointer, that would
usually be fine (in practice; the standard only says that void can store
the type of anything, so it _could_ be larger than some other pointers.
I don't know of any modern systems where this is true, though).

Which is all a roundabout way of saying that yes, I think this kind of
cast is probably OK in practice.

I _think_ the ccan type-checking macro you pointed to would catch this
sufficiently on systems with typeof() that it would also protect systems
with different calling conventions. But I admit it's pretty dense.

So I dunno. The nice thing is that this puts the ugliness all inside of
QSORT(), which becomes magically type-safe. But it involves importing a
lot of tricky bits under the hood.

The downside of René's patch is that it hides the declaration of the
comparison function (and the typesafe wrapper) inside a macro. But the
resulting code is (IMHO) pretty easy to comprehend.

-Peff