Re: [PATCH] revision: reallocate TOPO_WALK object flags

[Jeff King <peff@peff.net>]

On Wed, Jun 24, 2020 at 03:05:38PM +0200, René Scharfe wrote:

> The bit fields in struct object have an unfortunate layout.  Here's what
> pahole reports on x86_64 GNU/Linux:
> 
> struct object {
> 	unsigned int               parsed:1;             /*     0: 0  4 */
> 	unsigned int               type:3;               /*     0: 1  4 */
> 
> 	/* XXX 28 bits hole, try to pack */
> 
> 	/* Force alignment to the next boundary: */
> 	unsigned int               :0;
> 
> 	unsigned int               flags:29;             /*     4: 0  4 */
> 
> 	/* XXX 3 bits hole, try to pack */
> 
> 	struct object_id           oid;                  /*     8    32 */
> 
> 	/* size: 40, cachelines: 1, members: 4 */
> 	/* sum members: 32 */
> 	/* sum bitfield members: 33 bits, bit holes: 2, sum bit holes: 31 bits */
> 	/* last cacheline: 40 bytes */
> };
> 
> Notice the 1+3+29=33 bits in bit fields and 28+3=31 bits in holes.

Good catch. The original FLAG_BITS was intended to pack with parsed and
type, and we should have caught this in review when it got bumped in
b45424181e (revision.c: generation-based topo-order algorithm,
2018-11-01).

The patch looks correct to me.

> There are holes inside the flags bit field as well -- while some object
> flags are used for more than one purpose, 22, 23 and 24 are still free.
> Use  23 and 24 instead of 27 and 28 for TOPO_WALK_EXPLORED and
> TOPO_WALK_INDEGREE.  This allows us to reduce FLAG_BITS by one so that
> all bitfields combined fit into a single 32-bit slot:
> 
> struct object {
> 	unsigned int               parsed:1;             /*     0: 0  4 */
> 	unsigned int               type:3;               /*     0: 1  4 */
> 	unsigned int               flags:28;             /*     0: 4  4 */
> 	struct object_id           oid;                  /*     4    32 */
> 
> 	/* size: 36, cachelines: 1, members: 4 */
> 	/* last cacheline: 36 bytes */
> };

With 20-byte hashes, this put us at 24 bytes, which is 8-byte aligned. I
had always assumed once we moved to 32-byte hashes that we'd be stuck
with a 40-byte "struct object" to keep 8-byte alignment on 64-bit
systems. But it seems that at least on x86_64 Linux, we're happy with
4-byte alignment. That's useful to know (I had wondered if we might be
able to put those extra bytes to a good use, but I guess not).

>  /*
>   * object flag allocation:
> - * revision.h:               0---------10         15                   25----28
> + * revision.h:               0---------10         15             23------26
>   * fetch-pack.c:             01
>   * negotiator/default.c:       2--5
>   * walker.c:                 0-2

Definitely not a new problem, but I think we should consider "rotating"
this table. The point of it is for two branches that get merged to cause
a conflict if they allocate the same bit to two uses. And we _might_ get
see such a conflict if the allocations are on adjacent lines, but we
wouldn't if they're far away. E.g., imagine one side does:

  -* revision.h    0---------10
  +* revision.h    0----------11
   * fetch-pack.c  01
   * foo.c           2
   * bar.c            3

and the other does:

   * revision.h    0---------10
   * fetch-pack.c  01
   * foo.c           2
   * bar.c            3
  +* uh-oh.c                  11

Now we have two possibly conflicting uses of bit 11 (a semantic
conflict), but no matching textual conflict.

Whereas if we wrote:

  * bit 0: revision.h, fetch-pack.c
  * bit 1: revision.h
  * bit 2: revision.h, foo.c
  * bit 3: revision.h, bar.c
  [etc...]

then we'd get a conflict on the "bit 11" line. It does mean that
unrelated modules get written on the same line, but that's the point.
They're only allowed to be on the same line after somebody determines
that they're mutually exclusive and won't stomp on each other.

-Peff