Typesafer git hash patch

Typesafer git hash patch

[Linus Torvalds]

So because of the whole SHA1 discussion, I started looking at what it
would involve to turn

    unsigned char *sha1

style arguments (and various structure members) in the git source into

   typedef struct { ... } hash_t;

   hash_t *hash;

The answer is that it's pretty painful - more so than I expected (I
looked at it _looong_ ago and decided it was painful - and it has
become more painful as git has grown).

But once I got started I just continued through the slog.

Having the hashes be more encapsulated does seem to make things better
in many ways. What I did was to also just unify the notion of "hash_t"
and "struct object_id", so the two are entirely interchangeable. That
actually can clean up some code, because right now we have duplicate
interfaces for some things that take an oid pointer and others take a
"const unsigned char *sha1", and that duplication essentially can go
away. I didn't do any of that, I tried to keep it as as brute-force
stupid conversion.

I saw that somebody is actually looking at doing this "well" - by
doing it in many smaller steps. I tried. I gave up. The "unsigned char
*sha1" model is so ingrained that doing it incrementally just seemed
like a lot of pain. But it might be the right approach.

It might particularly be the right approach considering the size of the patch:

 216 files changed, 4174 insertions(+), 4080 deletions(-)

which is pretty nasty. The good news is that my patch passes all the
tests, and while it's big it's mostly very very mindless, and a lot of
it looks like cleanups, and the lines are generally shorter, eg

-               const unsigned char *mb = result->item->object.oid.hash;
-               if (!hashcmp(mb, current_bad_oid->hash)) {

turns into

+               const hash_t *mb = &result->item->object.oid;
+               if (!hashcmp(mb, current_bad_oid)) {

but I ended up also renaming a lot of common "sha1" as "hash", which
adds to the noise in that patch.

NOTE! It doesn't actually _fix_ the SHA1-centricity in any way, but it
makes it a bit more obvious where the bigger problems are. Not that
anybody would be surprised by what they are, but as part of writing
the patch it did kind of pinpoint most of them, and about 30 of those
new lines are added

 /* FIXME! Hardcoded hash sizes */
 /* FIXME! Lots of fixed-size hashes */
 /* FIXME! Fixed 20-byte hash usage */

with the rest of the added lines being a few helper functions and
splitting cache.h up a bit.

And as part of the type safety, I do think I may have found a bug:

show_one_mergetag():

                strbuf_addf(&verify_message, "tag %s names a non-parent %s\n",
                                    tag->tag, tag->tagged->oid.hash);

note how it prints out the "non-parent %s", but that's a SHA1 hash
that hasn't been converted to hex. Hmm?

Anyway, is anybody interested?  I warn you - it really is one big
patch on top of 2.12.

                   Linus

PS. Just for fun, I tried to look what it does when you then merge pu
or next.. You do get a fair number of merge conflicts because there's
just a lot of changes all around, but they look manageable. So merging
something like that would be painful, but it appears to not entirely
break other development.

Re: Typesafer git hash patch

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 3410 bytes --]

On Tue, Feb 28, 2017 at 11:53:28AM -0800, Junio C Hamano wrote:
> Linus Torvalds <torvalds@linux-foundation.org> writes:
> 
> > That
> > actually can clean up some code, because right now we have duplicate
> > interfaces for some things that take an oid pointer and others take a
> > "const unsigned char *sha1", and that duplication essentially can go
> > away.
> 
> ... I understand that this is an eventual goal of "struct object_id"
> effort.

Yes, it is.

> > ..., and the lines are generally shorter, eg
> >
> > -               const unsigned char *mb = result->item->object.oid.hash;
> > -               if (!hashcmp(mb, current_bad_oid->hash)) {
> >
> > turns into
> >
> > +               const hash_t *mb = &result->item->object.oid;
> > +               if (!hashcmp(mb, current_bad_oid)) {
> 
> Hmph.  I somehow thought the longer term directio for the above code
> would be to turn it into
> 
> 		if (!oidcmp(&result->item->object.oid, &current_bad_oid))
> 
> instead.

It is.  The duplication is temporary.  We've actually removed some of
the original SHA-1 functions in favor of the object_id versions.

> Having said all that, I do not offhand see a huge benefit of the
> current layout that has one layer between the hash (i.e. oid.hash)
> and the object name (i.e. oid) over "there is no need for oid.hash;
> oid is just a hash", which you seem to be doing.
> 
> Except for cases where we need to be prepared to see two or more
> kinds of object names (in which case struct object_id would have an
> enum that tells you if oid.hash is SHA-1 or SHA-3-256), that is.  Of
> course we can encode that in hash_t itself (e.g. multihash).

Right, this is indeed a benefit.

The bigger issue is the assumptions in the code base that assume a given
hash size.  These assumptions are in a bunch of places, so pretty much
any time you see a number, you end up having to question what it means.
We have a 64 that means 40 (SHA-1 hex) plus 24 other values, for
example.

I've sent various series because I think that's the way that the Git
development community has most welcomed my contributions.  I have
another 69 patches in two series (which are as of yet untested).  I can
probably have almost all of the transition actually complete in another
couple weeks (because I have a day job which does not involve working on
Git).

I've hesitated to send additional patches to the list when my existing
changes haven't even hit next yet, since they're received little actual
testing.

I'm unsure if sending one enormous patch is actually going to be
welcome; I feel Junio and most of the regulars are probably not going to
be very excited about the idea, mostly because the reviewing task is
enormous, and the risk for breakage is also pretty high.  We want to
move away from SHA-1 as quickly as possible, yes, but we don't want Git
to become unusably buggy.

I guess what I'm saying is that I'm fine if we want to have a more
aggressive timeline, and I can probably make that happen, at least if we
can wait a few weeks.  If Junio and the other regulars are comfortable
merging one omnibus patch to get it moving even more quickly, I won't
stand in the way.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 868 bytes --]

Re: Typesafer git hash patch

[Linus Torvalds]

On Tue, Feb 28, 2017 at 11:53 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Linus Torvalds <torvalds@linux-foundation.org> writes:
>>
>> Having the hashes be more encapsulated does seem to make things better
>> in many ways. What I did was to also just unify the notion of "hash_t"
>> and "struct object_id", so the two are entirely interchangeable.
>
> Sorry, but at this point in your description, you completely lost
> me.  I thought "struct object_id" was what you call "hash_t" in the
> above.

So what happened was that I started out just encapsulating

   unsigned char sha1[20];

as a

   hash_t hash;

and that made sense in a lot of situations. I always thought that code that used

    struct object_id oid;

is just too ugly to live, so I'm not actually all that big of a fan of
the oid approach.

But the two approaches really are pretty much equivalent logically,
even if they don't look the same.

So I wanted to unify things: "One type to bring them all and in the
darkness bind them".

So I just basically made this:

    typedef struct object_id {
            unsigned char hash[GIT_HASH_SIZE];
    } hash_t;

to create one single data structure that doesn't make my eyes bleed.
That "struct object_id" still exists, but I don't generally have to
look at it when doing the conversion, and any current users "just
work".

>> turns into
>>
>> +               const hash_t *mb = &result->item->object.oid;
>> +               if (!hashcmp(mb, current_bad_oid)) {
>
> Hmph.  I somehow thought the longer term directio for the above code
> would be to turn it into
>
>                 if (!oidcmp(&result->item->object.oid, &current_bad_oid))

Well, you can actually do it with my patch, since I left "oidcmp()"
alone and it's just an alias for "hashcmp()" in my tree.

Except I think "oid" is an odious name, and really confusing and not
at all descriptive.

Using a three-letter acronym when we have a four-letter actual word to
say it feels stupid and wrong to me.

So what my conversion does is basically say that the name is *hash*.
So instead of using "oidcmp", you use "hashcmp":

        if (!hashcmp(&result->item->object.oid, &current_bad_oid))

and functions take a "hash_t *" argument rather than a "struct
object_id *" argument, and when there was any kind of confusion and
mixing of use, I converted to "hash_t".

Both oid and "unsigned char *" users got converted.

In other words, what I was aiming for was getting rid - entirely - of
the "two different types", and I disliked both "oid" and "unsigned
char []", so neither replaces the other.

> Having said all that, I do not offhand see a huge benefit of the
> current layout that has one layer between the hash (i.e. oid.hash)
> and the object name (i.e. oid) over "there is no need for oid.hash;
> oid is just a hash", which you seem to be doing.

Yes exactly.

>> And as part of the type safety, I do think I may have found a bug:
>>
>> show_one_mergetag():
>>
>>                 strbuf_addf(&verify_message, "tag %s names a non-parent %s\n",
>>                                     tag->tag, tag->tagged->oid.hash);
>>
>> note how it prints out the "non-parent %s", but that's a SHA1 hash
>> that hasn't been converted to hex. Hmm?
>
> Yup.  That needs fixing, obviously.

I suspect nobody has ever hit that case - I tried to google for "names
a non-parent" and "tag" and "git" and the only thing that I found was
hits to git source.

So I was actually fairly impressed that the only thing I found was one
totally insignificant bug in a printout.

I did find a lot of cases where we really do mix a buffer of memory
("unsigned char *") with the hash. Not unsurprisingly, most of them
were in pack-file handling and in the tree parsing.

And some thing do the reverse, and really walk a hash name byte by
byte. Things like "find_pack_entry_one()" really does walk the bytes
of the hash.

With the conversion in place, those painful things are a bit more
obvious. So there's a couple of places where I just did a hard
conversion from a "unsigned char *" to a hash_t, but they are now
obvious casts and there's only 17 of them:

  [torvalds@i7 git]$ git grep '(hash_t \*)'
  builtin/index-pack.c:           hashcpy(ref_hash, (hash_t *) fill(20));
  builtin/pack-redundant.c:               hash_t *h1 = (hash_t
*)(p1_base + p1_off);
  builtin/pack-redundant.c:               hash_t *h2 = (hash_t
*)(p2_base + p2_off);
  builtin/pack-redundant.c:               hash_t *h1 = (hash_t
*)(p1_base + p1_off);
  builtin/pack-redundant.c:               hash_t *h2 = (hash_t
*)(p2_base + p2_off);
  builtin/pack-redundant.c:               hash_t *h = (hash_t *)(base + off);
  dir.c:  hashcpy(&ud->exclude_sha1, (hash_t *)rd->data);
  fast-import.c:          hashcpy(&e->versions[0].hash, (hash_t *)c);
  fast-import.c:          hashcpy(&e->versions[1].hash, (hash_t *)c);
  match-trees.c:  hashcpy((hash_t *)rewrite_here, rewrite_with);
  sha1-lookup.c:                      lo, mi, hi, sha1_to_hex((hash_t *)key));
  sha1_file.c:    return (hash_t *)(base + idx * GIT_SHA1_RAWSZ);
  sha1_file.c:            return (hash_t *)base;
  sha1_file.c:            return (hash_t *) (index + 24 * n + 4);
  sha1_file.c:            return (hash_t *) (index + 20 * n);
  sha1_file.c:            int cmp = hashcmp((hash_t *)(index + mi *
stride), (hash_t *)sha1);
  split-index.c:  hashcpy(&si->base_sha1, (hash_t *)data);

and there are basically an equal number of cases where I do the
reverse (by doing hash->hash to get the byte array data of the hash).

So the patch doesn't *fix* anything, but it does, I think, make it
easier to see the problems.

And the *bulk* of the code doesn't look inside the hashes at all.

                     Linus

Re: Typesafer git hash patch

[Jeff King]

On Mon, Feb 27, 2017 at 10:59:15PM -0800, Linus Torvalds wrote:

> I saw that somebody is actually looking at doing this "well" - by
> doing it in many smaller steps. I tried. I gave up. The "unsigned char
> *sha1" model is so ingrained that doing it incrementally just seemed
> like a lot of pain. But it might be the right approach.

That somebody is brian carlson, cc'd.

> which is pretty nasty. The good news is that my patch passes all the
> tests, and while it's big it's mostly very very mindless, and a lot of
> it looks like cleanups, and the lines are generally shorter, eg
> 
> -               const unsigned char *mb = result->item->object.oid.hash;
> -               if (!hashcmp(mb, current_bad_oid->hash)) {
> 
> turns into
> 
> +               const hash_t *mb = &result->item->object.oid;
> +               if (!hashcmp(mb, current_bad_oid)) {
> 
> but I ended up also renaming a lot of common "sha1" as "hash", which
> adds to the noise in that patch.

I think the preimage there is worse than it ought to be because it's
mid-transition. "struct object" has an object_id, but the rest of the
function hasn't been converted yet. So ultimately it should be:

  const struct object_id *mb = &result->item->object.oid;
  if (!oidcmp(mb, current_bad_oid))

It looks like you stuck your "hash_t" inside "struct object_id", which I
think is redundant. They're both trying to solve the same problem.

> NOTE! It doesn't actually _fix_ the SHA1-centricity in any way, but it
> makes it a bit more obvious where the bigger problems are. Not that
> anybody would be surprised by what they are, but as part of writing
> the patch it did kind of pinpoint most of them, and about 30 of those
> new lines are added
> 
>  /* FIXME! Hardcoded hash sizes */
>  /* FIXME! Lots of fixed-size hashes */
>  /* FIXME! Fixed 20-byte hash usage */

Yeah, a lot of brian's patches have been focused around the fixing the
related size assumptions. We've got GIT_SHA1_HEXSZ which doesn't solve
the problem, but at least makes it easy to find. And a big improvement
in the most recent series is a parse_oid() function that lets you parse
object-ids left-to-right without knowing the size up front. So things
like:

  if (len > 82 &&
      !get_sha1_hex(buf, sha1_a) &&
      get_sha1_hex(buf + 41, sha1_b))

becomes more like:

  if (parse_oid(p, oid_a, &p) && *p++ == ' ' &&
      parse_oid(p, oid_b, &p) && *p++ == '\n')

Still, if you've done more conversion, it's probably worth showing it
publicly. It might not end up used, but it may serve as a reference
later.

> And as part of the type safety, I do think I may have found a bug:
> 
> show_one_mergetag():
> 
>                 strbuf_addf(&verify_message, "tag %s names a non-parent %s\n",
>                                     tag->tag, tag->tagged->oid.hash);
> 
> note how it prints out the "non-parent %s", but that's a SHA1 hash
> that hasn't been converted to hex. Hmm?

Yeah, that's definitely a bug. I'm surprised that -Wformat doesn't
complain, but I guess we'd need -Wformat-signedness (which triggers
quite a lot of warnings related to "int"). It's especially bad for "%x",
which is implicitly unsigned.

-Peff

Re: Typesafer git hash patch

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 1165 bytes --]

On Tue, Feb 28, 2017 at 03:26:34PM -0500, Jeff King wrote:
> Yeah, a lot of brian's patches have been focused around the fixing the
> related size assumptions. We've got GIT_SHA1_HEXSZ which doesn't solve
> the problem, but at least makes it easy to find. And a big improvement
> in the most recent series is a parse_oid() function that lets you parse
> object-ids left-to-right without knowing the size up front. So things
> like:
> 
>   if (len > 82 &&
>       !get_sha1_hex(buf, sha1_a) &&
>       get_sha1_hex(buf + 41, sha1_b))
> 
> becomes more like:
> 
>   if (parse_oid(p, oid_a, &p) && *p++ == ' ' &&
>       parse_oid(p, oid_b, &p) && *p++ == '\n')

What I could do instead of using GIT_SHA1_HEXSZ is use GIT_MAX_HEXSZ for
things that are about allocating enough memory and create a global (or
function) for things that only care about what the current hash size is.
That might be a desirable approach.  If other people agree, I can make a
patch to do that.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 868 bytes --]

Re: Typesafer git hash patch

[Jeff King]

On Tue, Feb 28, 2017 at 08:33:13PM +0000, brian m. carlson wrote:

> On Tue, Feb 28, 2017 at 03:26:34PM -0500, Jeff King wrote:
> > Yeah, a lot of brian's patches have been focused around the fixing the
> > related size assumptions. We've got GIT_SHA1_HEXSZ which doesn't solve
> > the problem, but at least makes it easy to find. And a big improvement
> > in the most recent series is a parse_oid() function that lets you parse
> > object-ids left-to-right without knowing the size up front. So things
> > like:
> > 
> >   if (len > 82 &&
> >       !get_sha1_hex(buf, sha1_a) &&
> >       get_sha1_hex(buf + 41, sha1_b))
> > 
> > becomes more like:
> > 
> >   if (parse_oid(p, oid_a, &p) && *p++ == ' ' &&
> >       parse_oid(p, oid_b, &p) && *p++ == '\n')
> 
> What I could do instead of using GIT_SHA1_HEXSZ is use GIT_MAX_HEXSZ for
> things that are about allocating enough memory and create a global (or
> function) for things that only care about what the current hash size is.
> That might be a desirable approach.  If other people agree, I can make a
> patch to do that.

I was going to say "don't worry about it, and focus on converting to
constants at all for now". But I guess while you are doing that, it does
not hurt to split the MAX_HEXSZ cases out. It will save work in sorting
them later.

-Peff

Re: Typesafer git hash patch

[Linus Torvalds]

On Tue, Feb 28, 2017 at 12:19 PM, brian m. carlson
<sandals@crustytoothpaste.net> wrote:
>
> The bigger issue is the assumptions in the code base that assume a given
> hash size.

Absolutely. And I think those are going to be the "real" patches.

I actually saw your status report about

  "After another 27 commits, I've got it down from 1244 to 1119."

when I had just started, and I applauded the approach, but the numbers
made me go "ugh, that sounds painful".

What I actually wanted to do was to write a coccinelle script to
automate it, but it wasn't entirely obvious, and I started out just
doing it with "sed" and hand-fixing, and it got tedious byt then I had
done X% and just kept going.

I think an automated script that also guarantees that no code
generation could possibly change would have been lovely. We do that
over the kernel occasionally, where those kinds of patches that are
four thousand insertions/deletions in size are called "last Tuesday".

So my approach was really just brute-force and stupid, I admit it. I'm
not proud of the patch either.

It might be one of those "bandaid removal moments" - get it over and
done with and just rip that thing off ;)

So the patch is

 216 files changed, 4174 insertions(+), 4080 deletions(-)

and about 27k lines and 950kB total size.

The list limits are apparently much lower than that, but I'll happily
send it to people in private.

               Linus

Re: Typesafer git hash patch

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 2268 bytes --]

On Tue, Feb 28, 2017 at 12:25:20PM -0800, Linus Torvalds wrote:
> On Tue, Feb 28, 2017 at 11:53 AM, Junio C Hamano <gitster@pobox.com> wrote:
> > Sorry, but at this point in your description, you completely lost
> > me.  I thought "struct object_id" was what you call "hash_t" in the
> > above.
> 
> So what happened was that I started out just encapsulating
> 
>    unsigned char sha1[20];
> 
> as a
> 
>    hash_t hash;
> 
> and that made sense in a lot of situations. I always thought that code that used
> 
>     struct object_id oid;
> 
> is just too ugly to live, so I'm not actually all that big of a fan of
> the oid approach.

There was some discussion on the list about the best name to use, and
object_id seemed like the most popular decision.  I don't care if we add
a typedef for it and prefer that typedef, but the existing code avoided
typedefs in favor of explicit struct definitions.

I'm certainly not opposed to having less to type, because “object_id” is
awkward to type, but I've generally tried to defer to existing uses in
the codebase and what list regulars are comfortable with.

The only problem with using hash_t is that it's then not obvious as we
transition (assuming we don't take an omnibus patch) what is converted
and what isn't.

> But the two approaches really are pretty much equivalent logically,
> even if they don't look the same.

Yeah, I think they are.

> So I wanted to unify things: "One type to bring them all and in the
> darkness bind them".
> 
> So I just basically made this:
> 
>     typedef struct object_id {
>             unsigned char hash[GIT_HASH_SIZE];
>     } hash_t;
> 
> to create one single data structure that doesn't make my eyes bleed.
> That "struct object_id" still exists, but I don't generally have to
> look at it when doing the conversion, and any current users "just
> work".

There is nothing that prevents us from doing a nice global
search-and-replace in the future if we think the status quo is bad.
That's something that could be automated with Coccinelle.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 868 bytes --]