Re: [PATCH 1/5] add SWAP macro

From: Jeff King <peff@peff.net>
Date: Apr 30, 2017, 03:11 UTC
Message-ID: <20170430031154.qurrbdb3wqrdxd37@sigill.intra.peff.net>
In-Reply-To: <11699799-6bdf-484d-5a1c-8e8fa7981594@web.de>

On Sat, Apr 29, 2017 at 08:16:17PM +0200, René Scharfe wrote:

Show 10 quoted lines

> > I dunno. I could go either way. Or we could leave it as-is, and let
> > valgrind find the problem. That has zero run-time cost, but of course
> > nobody bothers to run valgrind outside of the test suite, so the inputs
> > are not usually very exotic.
> 
> It would be  problematic on platforms where memcpy has to erase the
> destination before writing new values (I don't know any example).
> 
> We could use two temporary buffers.  The object code is the same with
> GCC around 5 and Clang 3.2 or higher -- at least for prio-queue.c.

Hmm, yeah, that's an easy solution that covers the overlap case, too. If the generated code is the same, that seems like it might not be bad (I am a little sad how complex this simple swap operation is getting, though).

Show 9 quoted lines

> > Yes, the overlap case is probably an actual bug. Detecting it is a bit
> > harder, but definitely possible. I hate to pay the run-time cost for it,
> > but I wonder if a compiler could optimize it out.
> 
> How is it possible to arrive at such a situation?  We'd need two objects
> of the same size (we check that in SWAP) and one of them would start
> inside of the other one, i.e. the pointer difference between them would
> be a fraction of 1.  So the type system would have to be tricked into
> it, right?

Yeah, I guess it would be pretty odd. I was thinking of swapping a struct and one of its components, but that fail the size equality check. And anyway that would be a silly thing to do in the first place, so it's probably not worth thinking too much about.

> It may be my laziness speaking, but do we really need such a check?  If
> someone constructs interleaving objects then they'd need to implement
> the necessary checks themselves IMHO.

Yeah, I think we can live without it. I was mostly trying to think through whether there were worse cases than the one we saw. But you've convinced me that there probably aren't.

Show 15 quoted lines

> > > The line in question is this one:
> > > 
> > > 	for (i = 0; i <= (j = (queue->nr - 1) - i); i++)
> > > 
> > > Assignment in the middle?  Hmm.  Why not do it like this?
> > > 
> > > 	for (i = 0, j = queue->nr - 1; i < j; i++, j--)
> > > 
> > > Looks less complicated to me.
> > 
> > Yes, see my other reply. :)
> 
> Ah, so that's where I stole it from. ;)  Perhaps my source amnesia was
> in part caused by confusion about your reasoning there: The code does A,
> B would be better, so let's do C.  Wait, what? :)

My reasoning was that there's a bug, and the patch does the minimal fix. I don't mind making a readability improvement on top, but the two are orthogonal. I.e., you could still write:

  for (i = 0, j = queue->nr - 1; i <= j; i++, j--)

which is more readable but still buggy. :)

-Peff