Re: [WISH] Store also tag dereferences in packed-refs

Linus Torvalds [off-list ref] writes:

So the optimizations that _can_ be done are:

 - add dereference info to .git/packed-refs

   This would allow us to simply not do the expensive object lookup for 
   every single tag. We'd still have to do it for non-packed objects, of 
   course, but the cost here tends to be that over time you might have 
   hundreds of tags, and even if each tag only takes 0.02s to look up, 
   you're going to be slow.

 - avoid the references for "heads/" (which we know are supposed to be 
   commits, and cannot be tags) and when not specifying "-d". This won't 
   help your case very much, though. If you want "-d", you want it, and 
   the _big_ number of refs tends to be in tags, not branches, anyway.

 - using a filesystem wih nicer locality behaviour for directory entries 
   and inodes. This can cut down costs of cold-cache case by a factor of 
   two, but right now there are no good filesystems that do this (but see 
   for example "spadfs" that Mikulas Patocka announced a few weeks ago on 
   linux-kernel - it would seem to have the possibility of being better in 
   this area. I looked at the code and it looked like it could become 
   very reasonable, but I've not actually _tested_ it, soo...)

Anyway, I think that if we really want to make "git show-refs" go fast 
when things are cold in the cache, and with lots ot tags and "-d" (which 
is a reasonable case to optimize for: it's probably exactly what we end up 
doing both for gitweb _and_ for "git-send-pack"), we'd need to expand the 
packed-refs file with the deref cache.

Junio?

Yes; the "for discussion only" WIP patch from yesterday was
about the first point and half of the second point.

One downside about storing the peeled refs in .git/packed-refs
is that the code in the wild does not have safety guard against
them, so the version of show-ref from v1.4.4 recently released
will list tags/v2.6.19^{} as if it is a true tag and worse yet
it might even show tags/v2.6.19^{}^{} under -d option after the
repository's refs are packed in the new format.

But I think we can avoid that problem by using a format slightly
different from the WIP patch.  We can for example use two spaces
between SHA-1 and the name for them.  refs.c::parse_ref_line()
in existing code will say "oh, this line is nonsense" and skip
them, while the updated code can say "ok, this is a peeled ref",
since it has a seemingly incomplete "check for valid refname"
there that only checks "isspace(*line)".

Did you do this "if (isspace(*line)) return NULL" to have
extensibility later, I wonder...

On Sun, 19 Nov 2006, Jakub Narebski wrote:

So the only reason against this format (IMHO more reasonable, more readable
and more readable, and even easy extendable to the whole chain of derefs)
is code in the wild? 

By the way, do we copy packed refs literaly when fetching or cloning?

The packed refs format is _purely_ a local format. So in that sense, we 
can change it any way we want, and nobody really cares.

HOWEVER, even on a local machine, we generally want to be able to upgrade 
and downgrade git versions without having to worry about things like this, 
and having to convert one format to another. So using a format that "just 
works" with any version of git that understands packed refs is _wildly_ 
more preferable over changing the format.

Btw, the simplest and best format is probably to make the new extension 
look something like

	8ba130df4b67fa40878ccf80d54615132d24bc68 refs/tags/v2.6.17
	^427abfa28afedffadfca9dd8b067eb6d36bac53f
	d882e0c80e6e3c60640492b83395e6fbbae04276 refs/tags/v2.6.17-rc1
	^6246b6128bbe34d0752f119cf7c5111c85fe481d

which is basically almost as dense as having a space on the same line, and 
will also trigger the old "that's not a valid line, just ignore it" 
reaction from older versions.

So the parsing rules for that would simply be:

 - if you see a line that starts with a "^<sha1>", then that is the 
   "unpeeling" of the previous packed entry (which in turn might have been 
   an unpeeling itself)

So if you were to have tags pointing to tags, you migt have

	<sha1> refs/tags/tagname
	^<sha1-unpeeled>
	^<sha1-unpeeled-of-unpeeled>
	...
	<sha1> refs/tags/othertag

In addition, we'd need a line at the top of the file that says "this has 
unpeeled information", because otherwise we have no way to distinguish 
between the case of "no actual tag objects" and "old-fashioned ref-pack 
file without any unpeeling info" - since they'd look identical.

So I'd suggest adding - at the very top of the ref-pack file - a line line

	# Ref-pack version 2

which will be ignored by the current ref-pack reader (again, because it's 
not a valid ref line), but we can use it in the future to specify further 
extensions if we want to.

Now somebody would just need to implement that ;)

Linus Torvalds [off-list ref] writes:

So I'd suggest adding - at the very top of the ref-pack file - a line line

	# Ref-pack version 2

which will be ignored by the current ref-pack reader (again, because it's 
not a valid ref line), but we can use it in the future to specify further 
extensions if we want to.

Now somebody would just need to implement that ;)

For this particular one, there is no need for version 2.

My current wip does:

	SHA-1 SP name LF
	SHA-1 SP SP name^{} LF

the latter of which is ignored by code in the wild and the new
code can take advantage of (and fall back the usual deref_tag
when it is not available).

I need to rebase it on top of a minor update to refs.c before
pushing it out.

Linus Torvalds wrote:

On Sun, 19 Nov 2006, Junio C Hamano wrote:

quoted

Did you do this "if (isspace(*line)) return NULL" to have
extensibility later, I wonder...

No, but I try to have a policy of not accepting anything that is even 
slightly questionable, so it was unintentional in the details but a result 
of a higher-level principle..

Of course, even when I wrote it I _also_ knew that I should check 
everything else too (not just the first character), but I was lazy. That 
would have been even better - then we could have made the thing be 
something like

      <sha1><space><name>[<space><sha1-of-deref>]*

instead.

So the only reason against this format (IMHO more reasonable, more readable
and more readable, and even easy extendable to the whole chain of derefs)
is code in the wild? 

By the way, do we copy packed refs literaly when fetching or cloning?
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

On Sun, 19 Nov 2006, Junio C Hamano wrote:

Did you do this "if (isspace(*line)) return NULL" to have
extensibility later, I wonder...

No, but I try to have a policy of not accepting anything that is even 
slightly questionable, so it was unintentional in the details but a result 
of a higher-level principle..

Of course, even when I wrote it I _also_ knew that I should check 
everything else too (not just the first character), but I was lazy. That 
would have been even better - then we could have made the thing be 
something like

	<sha1><space><name>[<space><sha1-of-deref>]*

instead.

Junio C Hamano wrote:

Linus Torvalds [off-list ref] writes:

quoted

So I'd suggest adding - at the very top of the ref-pack file - a line line

     # Ref-pack version 2

which will be ignored by the current ref-pack reader (again, because it's 
not a valid ref line), but we can use it in the future to specify further 
extensions if we want to.

Now somebody would just need to implement that ;)

For this particular one, there is no need for version 2.

Actually, I think it is both true and untrue. True, because we need some
indicator that we trust packed-refs file to provide tag dereferences to
distinguish between the case when there are no tag objects at all, so there
are no tag dereferences in packed-refs, and the situation where we use
packed-refs generated by older git, and there are no tag dereferences in
packed-refs because git didn't saved it.

Untrue, because it is not enough. In the case[*1*] when packed-refs was
created with tag dereferences, then some "heavyweight" tags were added
by older version of git (adding references doesn't rewrite packed-refs
if I understand correctly), then we use new git again and trust that there
are no derefs...

[*1*] For example when git repository is on the network filesystem, but
programs are installed locally, and perhaps computers in the network are
heterogenic (perhaps even different architectures: PC vs. Sun and/or
different operating systems: Linux vs. FreeBSD vs. Solaris vs.
Windows+Cygwin) and have different versions of git installed (perhaps
one of them is "your" machine, where you have admin rights, and you have
newest git installed there). Or for example using git repository on USB
stick, again on different computers with different version of git installed.
 
---------------------------------------------------------------------

To summarize, we have the following proposals of the packed-refs format
extension


The unusable Linux Torvalds proposal (unusable because of requiring
newer packed-refs work with older git, for example in the case [*1*]
or the case of git downgrade):

lt>    <sha1><space><name>[<space><sha1-of-deref>]*


Linus Torvalds "Now somebody would just need to implement that ;)"
proposal:

lt>    <sha1> refs/tags/tagname
lt>    ^<sha1-unpeeled>
lt>    ^<sha1-unpeeled-of-unpeeled>
lt>    ...
lt>    <sha1> refs/tags/othertag


Junio C Hamano proposal _with code_ (proposal with code usually wins).
Less elegant IMVHO, but perhaps better.

jc> My current wip does:
jc> 
jc>     SHA-1 SP name LF
jc>     SHA-1 SP SP name^{} LF
jc> 
jc> the latter of which is ignored by code in the wild and the new
jc> code can take advantage of (and fall back the usual deref_tag
jc> when it is not available).

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

On Sun, 19 Nov 2006, Junio C Hamano wrote:

Linus Torvalds [off-list ref] writes:

quoted

So I'd suggest adding - at the very top of the ref-pack file - a line line

	# Ref-pack version 2

which will be ignored by the current ref-pack reader (again, because it's 
not a valid ref line), but we can use it in the future to specify further 
extensions if we want to.

Now somebody would just need to implement that ;)

For this particular one, there is no need for version 2.

I don't think you understand.

My current wip does:

	SHA-1 SP name LF
	SHA-1 SP SP name^{} LF

I think that's ugly and redundant (if "name" is ever different from the 
lien above it, that would be a bug), but that's not the real problem.

The real problem is (go back to the mail that you answered, and snipped 
the explanation from) this:

 - you have a thousand tags

 - NONE of them are "tag objects".

 - as a result your ref-pack file doesn't have a _single_ of the ^{} lines

Think about it. How do you know whether you should look up the tag objects 
for "-d" or not?

The answer is: you don't. You can't tell a "version 1" and "version 2" 
file apart. It might be an old "version 1" file that simply doesn't _have_ 
dereference information. Or it might be a "version 2" file that _does_ 
have dereference information, but nothing to dereference.

So you either have to:

 - look up each object again to see if it's a tag that should be 
   dereferenced

OR:

 - add a "# ref-pack version 2" flag at the top of the file.

So it's not about "parsing" the new file structure. I realize that parsing 
it is trivial. It's simply about knowing whether the new information 
_could_ be there or not.

And once you have that flag, your _future_ extensions can add their own 
version, which is an added bonus. But that means that "version 2" parsing 
should _also_ ignore lines that it cannot match, so you'd better have an 
escape from the new format. I personally think that using

	^<sha1><lf>

instead of "<sha1><space><space><name>^{}<lf>" is better partly for that 
reason: it's not only denser, it is "stricter" in the sense that there's 
less room for some future extended version that could be mistaken for a 
"version 2 unpeeling" line. 

(But you can do the same thing with your version too. You should:
 - check that there is just _one_ extra space
 - verify that the name matches the previous one
 - verify that it ends exactly with "^{}", so that any future extension 
   could add their own flags at the end.)

But regardless of which format chosen, you need the flag of "this format 
is in use", exactly because the extended unpeeling information might not 
_exist_.

Oh, and regardless of which format chosen, you'd need to verify that the 
unpeeled object in the pack wasn't overridden, of course. 

		Linus

quoted

For this particular one, there is no need for version 2.

Actually, I think it is both true and untrue. True, because we need some
indicator that we trust packed-refs file to provide tag dereferences to
distinguish between the case when there are no tag objects at all, so there
are no tag dereferences in packed-refs, and the situation where we use
packed-refs generated by older git, and there are no tag dereferences in
packed-refs because git didn't saved it.

We should be able to handle the ambiguous/malformed lines correctly
and gracefully _always_, without 'trust' a version number to avoid to
be prone to attacks with a malicious malformed file.

Anyway document versioning it's a common and savy practice.