From: Jeff King <hidden> Date: 2016-06-15 23:02:38
At GitHub we've occasionally run across repos getting corrupted by trees
and blobs near the tip going missing. We do a lot of "test merges"
between branches and HEAD (this is what feeds the "OK to merge" button
on the web interface), and the objects are almost always related to
these merges. The objects are removed by prune, which doesn't realize
that they are part of an ongoing operation. Prune uses the filesystem
mtime to determine this, but we are not very thorough in making sure
that is kept up to date.
This series tries to fix that with two techniques:
1. When we try to write an object to disk, we optimize out the write
if we already have the object. Instead, we should still update the
mtime of the object in this case.
2. Treat objects reachable from "recent" objects as recent themselves.
When we check that we have an object, we do not check whether we
have all of the objects it can reach. If you have some new objects
that refer to some old objects (e.g., you create and delete a tree
on day 1, and then create a new tree referring to the blob on day
2), then prune may delete the old object but not the new (in this
case, we delete the blob but not the tree).
Any subsequent use of the new object will check that we have it
(e.g., commit-tree makes sure we have the tree we feed it), but not
other objects it can reach. This can lead to referencing a
half-formed part of the graph.
Note that this does not make prune race-free. For example, you could
check for and update the mtime of an object just as prune is deleting
it, and think that it is written when it is not. Fixing that would
require some atomic mechanism for prune to check the mtime and delete.
But I do think this series cuts us down to "real" race conditions, with
millisecond-ish timing. The problems we're fixing here are much worse
than that. The distance between an object being written and being
referred may operate on human timescales (e.g., writing a commit
message). Or the time distance between two objects that refer to each
other may be days or weeks; a prune where one falls in the "recent"
boundary and another does not can be disastrous.
There's quite a lot of patches here, but most of them are preparatory
cleanups. The meat is in patches 13, 15, and 16.
[01/16]: foreach_alt_odb: propagate return value from callback
[02/16]: isxdigit: cast input to unsigned char
[03/16]: object_array: factor out slopbuf-freeing logic
[04/16]: object_array: add a "clear" function
[05/16]: clean up name allocation in prepare_revision_walk
[06/16]: reachable: clear pending array after walking it
[07/16]: t5304: use test_path_is_* instead of "test -f"
[08/16]: t5304: use helper to report failure of "test foo = bar"
[09/16]: prune: factor out loose-object directory traversal
[10/16]: count-objects: do not use xsize_t when counting object size
[11/16]: count-objects: use for_each_loose_file_in_objdir
[12/16]: sha1_file: add for_each iterators for loose and packed objects
[13/16]: prune: keep objects reachable from recent objects
[14/16]: pack-objects: refactor unpack-unreachable expiration check
[15/16]: pack-objects: match prune logic for discarding objects
[16/16]: write_sha1_file: freshen existing objects
Note that these aren't yet running on GitHub servers. I know that they
fix real potential problems (see the new t6501 for examples), but I
don't know for sure if they will catch the problems we have seen. The
frequency of these issues is relatively rare, so even once deployed, we
won't know for sure until a few weeks or months have passed.
-Peff
From: Jeff King <hidden> Date: 2016-06-15 23:02:38
We check the return value of the callback and stop iterating
if it is non-zero. However, we do not make the non-zero
return value available to the caller, so they have no way of
knowing whether the operation succeeded or not (technically
they can keep their own error flag in the callback data, but
that is unlike our other for_each functions).
Signed-off-by: Jeff King <redacted>
---
cache.h | 2 +-
sha1_file.c | 12 ++++++++----
2 files changed, 9 insertions(+), 5 deletions(-)
From: Jeff King <hidden> Date: 2016-06-15 23:02:38
Otherwise, callers must do so or risk triggering
-Wchar-subscript (and rightfully so; a signed char might
cause us to use a bogus negative index into the
hexval_table).
While we are dropping the now-unnecessary casts from the
caller in urlmatch.c, we can get rid of similar casts in
actually parsing the hex by using the hexval() helper, which
implicitly casts to unsigned (but note that we cannot
implement isxdigit in terms of hexval(), as it also casts
its return value to unsigned).
Signed-off-by: Jeff King <redacted>
---
git-compat-util.h | 2 +-
urlmatch.c | 8 ++++----
2 files changed, 5 insertions(+), 5 deletions(-)
From: Jeff King <hidden> Date: 2016-06-15 23:02:38
This is not a lot of code, but it's a logical construct that
should not need to be repeated (and we are about to add a
third repetition).
Signed-off-by: Jeff King <redacted>
---
object.c | 12 ++++++++----
1 file changed, 8 insertions(+), 4 deletions(-)
From: Jeff King <hidden> Date: 2016-06-15 23:02:38
There's currently no easy way to free the memory associated
with an object_array (and in most cases, we simply leak the
memory in a rev_info's pending array). Let's provide a
helper to make this easier to handle.
We can make use of it in list-objects.c, which does the same
thing by hand (but fails to free the "name" field of each
entry, potentially leaking memory).
Signed-off-by: Jeff King <redacted>
---
list-objects.c | 7 +------
object.c | 10 ++++++++++
object.h | 6 ++++++
3 files changed, 17 insertions(+), 6 deletions(-)
From: Jeff King <hidden> Date: 2016-06-15 23:02:38
When we enter prepare_revision_walk, we have zero or more
entries in our "pending" array. We disconnect that array
from the rev_info, and then process each entry:
1. If the entry is a commit and the --source option is in
effect, we keep a pointer to the object name.
2. Otherwise, we re-add the item to the pending list with
a blank name.
We then throw away the old array by freeing the array
itself, but do not touch the "name" field of each entry. For
any items of type (2), we leak the memory associated with
the name. This commit fixes that by calling object_array_clear,
which handles the cleanup for us.
That breaks (1), though, because it depends on the memory
pointed to by the name to last forever. We can solve that by
making a copy of the name. This is slightly less efficient,
but it shouldn't matter in practice, as we do it only for
the tip commits of the traversal.
Signed-off-by: Jeff King <redacted>
---
revision.c | 14 +++++++-------
1 file changed, 7 insertions(+), 7 deletions(-)
@@ -2672,10 +2673,9 @@ int prepare_revision_walk(struct rev_info *revs)next=commit_list_append(commit,next);}}-e++;}if(!revs->leak_pending)-free(list);+object_array_clear(&old_pending);/* Signal whether we need per-parent treesame decoration */if(revs->simplify_merges||
From: Jeff King <hidden> Date: 2016-06-15 23:02:38
We add a number of objects to our "pending" array, and then
process it with a combination of get_revision and walking
the pending array ourselves (to catch any non-commits). The
commits in the pending array are cleaned up automatically by
prepare_revision_walk, but we essentially leak any other
objects (they are technically still reachable from rev_info,
but no callers ever look at them or bother to clean them
up).
This is not a huge deal in practice, as the number of
non-commits tends to be small. However, a future patch will
broaden this considerably. Let's call object_array_clear to
free the memory.
Signed-off-by: Jeff King <redacted>
---
reachable.c | 2 ++
1 file changed, 2 insertions(+)
From: Jeff King <hidden> Date: 2016-06-15 23:02:38
This is slightly more robust (checking "! test -f" would not
notice a directory of the same name, though that is not
likely to happen here). It also makes debugging easier, as
the test script will output a message on failure.
Signed-off-by: Jeff King <redacted>
---
This patch is totally optional. I did it while debugging t5304 (strange
how badly prune works when you accidentally invert the mtime check!)
and figured it might be worth keeping as a cleanup.
t/t5304-prune.sh | 46 +++++++++++++++++++++++-----------------------
1 file changed, 23 insertions(+), 23 deletions(-)
@@ -110,7 +110,7 @@ test_expect_success 'prune: do not prune detached HEAD with no reflog' 'gitcommit--allow-empty-m"detached commit"&&# verify that there is no reflogs# (should be removed and disabled by previous test)-test!-e.git/logs&&+test_path_is_missing.git/logs&&gitprune-n>prune_actual&&:>prune_expected&&test_cmpprune_actualprune_expected
@@ -210,10 +210,10 @@ test_expect_success 'gc: prune old objects after local clone' '(cdaclone&&test1=$(gitcount-objects|sed"s/ .*//")&&-test-f$BLOB_FILE&&+test_path_is_file$BLOB_FILE&&gitgc--prune&&test0=$(gitcount-objects|sed"s/ .*//")&&-!test-f$BLOB_FILE+test_path_is_missing$BLOB_FILE)'
From: Jeff King <hidden> Date: 2016-06-15 23:02:39
For small outputs, we sometimes use:
test "$(some_cmd)" = "something we expect"
instead of a full test_cmp. The downside of this is that
when it fails, there is no output at all from the script.
Let's introduce a small helper to make tests easier to
debug.
Signed-off-by: Jeff King <redacted>
---
This is in the same boat as the last commit; we can drop it without
hurting the rest of the series.
Is test_eq too cutesy or obfuscated? I have often wanted it when
debugging other tests, too. Our usual technique is to do:
echo whatever >expect &&
do_something >actual &&
test_cmp expect actual
That's a bit verbose. We could hide it behind something like test_eq,
too, but it introduces several extra new processes. And I know people on
some fork-challenged platforms are very sensitive to the number of
spawned processes in the test suite.
t/t5304-prune.sh | 16 ++++++++--------
t/test-lib-functions.sh | 11 +++++++++++
2 files changed, 19 insertions(+), 8 deletions(-)
@@ -634,6 +634,17 @@ test_cmp_bin() {cmp"$@"}+# This is the same as 'test "$1" $3 "$2"' except that it+# will output a useful message to stderr on failure. If+# $3 is omitted, defaults to "=".+test_eq(){+if!test"$1""${3:-=}""$2"+then+echo>&2"test_eq failed: $1${3:-=}$2"+false+fi+}+# Check if the file expected to be empty is indeed empty, and barfs# otherwise.
From: Jeff King <hidden> Date: 2016-06-15 23:02:39
Prune has to walk $GIT_DIR/objects/?? in order to find the
set of loose objects to prune. Other parts of the code
(e.g., count-objects) want to do the same. Let's factor it
out into a reusable for_each-style function.
Note that this is not quite a straight code movement. There
are two differences:
1. The original code iterated from 0 to 256, trying to
opendir("$GIT_DIR/%02x"). The new code just does a
readdir() on the object directory, and descends into
any matching directories. This is faster on
already-pruned repositories, and should not ever be
slower (nobody ever creates other files in the object
directory).
2. The original code had strange behavior when it found a
file of the form "[0-9a-f]{2}/.{38}" that did _not_
contain all hex digits. It executed a "break" from the
loop, meaning that we stopped pruning in that directory
(but still pruned other directories!). This was
probably a bug; we do not want to process the file as
an object, but we should keep going otherwise.
Signed-off-by: Jeff King <redacted>
---
I admit the speedup in (1) almost certainly doesn't matter. It is real,
and I found out about it while writing a different program that was
basically "count-objects" across a large number of repositories. However
for a single repo it's probably not big enough to matter (calling
count-objects in a loop while get dominated by the startup costs). The
end result is a little more obvious IMHO, but that's subjective.
builtin/prune.c | 87 ++++++++++++++++------------------------------------
cache.h | 31 +++++++++++++++++++
sha1_file.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 152 insertions(+), 61 deletions(-)
@@ -31,11 +31,23 @@ static int prune_tmp_file(const char *fullpath)return0;}-staticintprune_object(constchar*fullpath,constunsignedchar*sha1)+staticintprune_object(constunsignedchar*sha1,constchar*fullpath,+void*data){structstatst;-if(lstat(fullpath,&st))-returnerror("Could not stat '%s'",fullpath);++/*+*Doweknowaboutthisobject?+*Itmusthavebeenreachable+*/+if(lookup_object(sha1))+return0;++if(lstat(fullpath,&st)){+/* report errors, but do not stop pruning */+error("Could not stat '%s'",fullpath);+return0;+}if(st.st_mtime>expire)return0;if(show_only||verbose){
@@ -3218,3 +3218,98 @@ void assert_sha1_type(const unsigned char *sha1, enum object_type expect)die("%s is not a valid '%s' object",sha1_to_hex(sha1),typename(expect));}++staticintopendir_error(constchar*path)+{+if(errno==ENOENT)+return0;+returnerror("unable to open %s: %s",path,strerror(errno));+}++staticintfor_each_file_in_obj_subdir(structstrbuf*path,+constchar*prefix,+each_loose_object_fnobj_cb,+each_loose_cruft_fncruft_cb,+each_loose_subdir_fnsubdir_cb,+void*data)+{+size_tbaselen=path->len;+DIR*dir=opendir(path->buf);+structdirent*de;+intr=0;++if(!dir)+returnopendir_error(path->buf);++while((de=readdir(dir))){+if(is_dot_or_dotdot(de->d_name))+continue;++strbuf_setlen(path,baselen);+strbuf_addf(path,"/%s",de->d_name);++if(strlen(de->d_name)==38){+charhex[41];+unsignedcharsha1[20];++memcpy(hex,prefix,2);+memcpy(hex+2,de->d_name,38);+hex[40]=0;+if(!get_sha1_hex(hex,sha1)){+if(obj_cb){+r=obj_cb(sha1,path->buf,data);+if(r)+break;+}+continue;+}+}++if(cruft_cb){+r=cruft_cb(de->d_name,path->buf,data);+if(r)+break;+}+}+if(!r&&subdir_cb)+r=subdir_cb(de->d_name,path->buf,data);+closedir(dir);+returnr;+}++intfor_each_loose_file_in_objdir(constchar*path,+each_loose_object_fnobj_cb,+each_loose_cruft_fncruft_cb,+each_loose_subdir_fnsubdir_cb,+void*data)+{+structstrbufbuf=STRBUF_INIT;+size_tbaselen;+DIR*dir=opendir(path);+structdirent*de;+intr=0;++if(!dir)+returnopendir_error(path);++strbuf_addstr(&buf,path);+baselen=buf.len;++while((de=readdir(dir))){+if(!isxdigit(de->d_name[0])||+!isxdigit(de->d_name[1])||+de->d_name[2])+continue;++strbuf_addf(&buf,"/%s",de->d_name);+r=for_each_file_in_obj_subdir(&buf,de->d_name,obj_cb,+cruft_cb,subdir_cb,data);+strbuf_setlen(&buf,baselen);+if(r)+break;+}++closedir(dir);+strbuf_release(&buf);+returnr;+}
From: Jeff King <hidden> Date: 2016-06-15 23:02:39
The point of xsize_t is to safely cast an off_t into a size_t
(because we are about to mmap). But in count-objects, we are
summing the sizes in an off_t. Using xsize_t means that
count-objects could fail on a 32-bit system with a 4G
object (not likely, as other parts of git would fail, but
we should at least be correct here).
Signed-off-by: Jeff King <redacted>
---
I think the on_disk_bytes is a little weird here, too. We count actual
disk-usage blocks for loose objects here, which makes sense. But we do
_not_ do so for packfiles, or for "garbage" files. Which seems kind of
inconsistent.
I kind of doubt anybody cares too much either way, though.
builtin/count-objects.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
From: Jeff King <hidden> Date: 2016-06-15 23:02:39
This drops our line count considerably, and should make
things more readable by keeping the counting logic separate
from the traversal.
Signed-off-by: Jeff King <redacted>
---
builtin/count-objects.c | 101 ++++++++++++++----------------------------------
1 file changed, 30 insertions(+), 71 deletions(-)
From: Jeff King <hidden> Date: 2016-06-15 23:02:39
We typically iterate over the reachable objects in a
repository by starting at the tips and walking the graph.
There's no easy way to iterate over all of the objects,
including unreachable ones. Let's provide a way of doing so.
Signed-off-by: Jeff King <redacted>
---
cache.h | 11 +++++++++++
sha1_file.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 73 insertions(+)
@@ -3313,3 +3313,65 @@ int for_each_loose_file_in_objdir(const char *path,strbuf_release(&buf);returnr;}++structloose_alt_odb_data{+each_loose_object_fn*cb;+void*data;+};++staticintloose_from_alt_odb(structalternate_object_database*alt,+void*vdata)+{+structloose_alt_odb_data*data=vdata;+returnfor_each_loose_file_in_objdir(alt->base,+data->cb,NULL,NULL,+data->data);+}++intfor_each_loose_object(each_loose_object_fncb,void*data)+{+structloose_alt_odb_dataalt;+intr;++r=for_each_loose_file_in_objdir(get_object_directory(),+cb,NULL,NULL,data);+if(r)+returnr;++alt.cb=cb;+alt.data=data;+returnforeach_alt_odb(loose_from_alt_odb,&alt);+}++intfor_each_object_in_pack(structpacked_git*p,each_packed_object_fncb,void*data)+{+uint32_ti;+intr=0;++for(i=0;i<p->num_objects;i++){+constunsignedchar*sha1=nth_packed_object_sha1(p,i);++if(!sha1)+returnerror("unable to get sha1 of object %u in %s",+i,p->pack_name);++r=cb(sha1,p,i,data);+if(r)+break;+}+returnr;+}++intfor_each_packed_object(each_packed_object_fncb,void*data)+{+structpacked_git*p;+intr=0;++prepare_packed_git();+for(p=packed_git;p;p=p->next){+r=for_each_object_in_pack(p,cb,data);+if(r)+break;+}+return0;+}
From: Jeff King <hidden> Date: 2016-06-15 23:02:39
Our current strategy with prune is that an object falls into
one of three categories:
1. Reachable (from ref tips, reflogs, index, etc).
2. Not reachable, but recent (based on the --expire time
and the file's mtime).
3. Not reachable and not recent.
We keep objects from (1) and (2), but prune objects in (3).
The point of (2) is that these objects may be part of an
in-progress operation that has not yet updated any refs.
However, it is not always the case that objects for an
in-progress operation will have a recent mtime. For example,
the object database may have an old copy of a blob (from an
abandoned operation, a branch that was deleted, etc). If we
create a new tree that points to it, a simultaneous prune
will leave our tree, but delete the blob. Referencing that
tree with a commit will then work (we check that the tree is
in the object database, but not that all of its referred
objects are), as will mentioning the commit in a ref. But
the resulting repo is corrupt; we are missing the blob
reachable from a ref.
One way to solve this is to be more thorough when
referencing a sha1: make sure that not only do we have that
sha1, but that we have the objects it refers to, and so
forth recursively. The problem is that this is very
expensive. Creating a parent link would require traversing
the entire object graph down to the roots.
Instead, this patch pushes the extra work onto prune, which
runs less frequently (and has to look at the whole object
graph anyway). It creates a new category of objects: objects
which are not recent, but which are reachable from a recent
object. We do not prune these objects, just like the
reachable and recent ones.
This lets us avoid the recursive check above, because if we
have an object, even if it is unreachable, we should have
its referent:
- if we are creating new objects, then we cannot create
the parent object without having the child
- and if we are pruning objects, will not prune the child
if we are keeping the parent
The big exception would be if one were to write the object
in a way that avoided referential integrity (e.g., using
hash-object). But if you are in the habit of doing that, you
deserve what you get.
Naively, the simplest way to implement this would be to add
all recent objects as tips to the reachability traversal.
However, this does not perform well. In a recently-packed
repository, all reachable objects will also be recent, and
therefore we have to consider each object twice (both as a
tip, and when we reach it in the traversal). I tested this,
and it added about 10s to a 30s prune on linux.git. This
patch instead performs the normal reachability traversal
first, then follows up with a second traversal for recent
objects, skipping any that have already been marked.
Signed-off-by: Jeff King <redacted>
---
I put the mark-recent code into mark_reachable_objects here,
but it does not technically have to be there. It reuses the
same rev_info object (which is convenient), but the SEEN
flags from the first traversal are marked on the global
commit objects themselves. So we could break it out into a
separate function.
However, we'd have to refactor the progress reporting; the
numbers are kept internally to mark_reachable, and we would
want to continue them for the second traversal (though I
suppose you could start a second progress meter with
"Checking recent objects" or something if you wanted).
builtin/prune.c | 2 +-
builtin/reflog.c | 2 +-
reachable.c | 111 +++++++++++++++++++++++++++++++++++++++++++++
reachable.h | 3 +-
t/t6501-freshen-objects.sh | 88 +++++++++++++++++++++++++++++++++++
5 files changed, 203 insertions(+), 3 deletions(-)
create mode 100755 t/t6501-freshen-objects.sh
@@ -212,7 +212,109 @@ static void add_cache_refs(struct rev_info *revs)add_cache_tree(active_cache_tree,revs);}+structrecent_data{+structrev_info*revs;+unsignedlongtimestamp;+};++staticvoidadd_recent_object(constunsignedchar*sha1,+unsignedlongmtime,+structrecent_data*data)+{+structobject*obj;+enumobject_typetype;++if(mtime<=data->timestamp)+return;++/*+*Wedonotwanttocallparse_objecthere,because+*inflatingblobsandtreescouldbeveryexpensive.+*However,wedoneedtoknowthecorrecttypefor+*laterprocessing,andtherevisionmachineryexpects+*commitsandtagstohavebeenparsed.+*/+type=sha1_object_info(sha1,NULL);+if(type<0)+die("unable to get object info for %s",sha1_to_hex(sha1));++switch(type){+caseOBJ_TAG:+caseOBJ_COMMIT:+obj=parse_object_or_die(sha1,NULL);+break;+caseOBJ_TREE:+obj=(structobject*)lookup_tree(sha1);+break;+caseOBJ_BLOB:+obj=(structobject*)lookup_blob(sha1);+break;+default:+die("unknown object type for %s: %s",+sha1_to_hex(sha1),typename(type));+}++if(!obj)+die("unable to lookup %s",sha1_to_hex(sha1));++add_pending_object(data->revs,obj,"");+}++staticintadd_recent_loose(constunsignedchar*sha1,+constchar*path,void*data)+{+structstatst;+structobject*obj=lookup_object(sha1);++if(obj&&obj->flags&SEEN)+return0;++if(stat(path,&st)<0){+/*+*It'sOKifanobjectwentawayduringouriteration;this+*couldbeduetoasimultaneousrepack.Butanythingelse+*weshouldabort,sincewemightthenfailtomarkobjects+*whichshouldnotbepruned.+*/+if(errno==ENOENT)+return0;+returnerror("unable to stat %s: %s",+sha1_to_hex(sha1),strerror(errno));+}++add_recent_object(sha1,st.st_mtime,data);+return0;+}++staticintadd_recent_packed(constunsignedchar*sha1,+structpacked_git*p,uint32_tpos,+void*data)+{+structobject*obj=lookup_object(sha1);++if(obj&&obj->flags&SEEN)+return0;+add_recent_object(sha1,p->mtime,data);+return0;+}++staticintadd_unseen_recent_objects_to_traversal(structrev_info*revs,+unsignedlongtimestamp)+{+structrecent_datadata;+intr;++data.revs=revs;+data.timestamp=timestamp;++r=for_each_loose_object(add_recent_loose,&data);+if(r)+returnr;+returnfor_each_packed_object(add_recent_packed,&data);+}+voidmark_reachable_objects(structrev_info*revs,intmark_reflog,+unsignedlongmark_recent,structprogress*progress){structconnectivity_progresscp;
@@ -248,5 +350,14 @@ void mark_reachable_objects(struct rev_info *revs, int mark_reflog,if(prepare_revision_walk(revs))die("revision walk setup failed");walk_commit_list(revs,&cp);++if(mark_recent){+if(add_unseen_recent_objects_to_traversal(revs,mark_recent))+die("unable to mark recent objects");+if(prepare_revision_walk(revs))+die("revision walk setup failed");+walk_commit_list(revs,&cp);+}+display_progress(cp.progress,cp.count);}
@@ -0,0 +1,88 @@+#!/bin/sh+#+# This test covers the handling of objects which might have old+# mtimes in the filesystem (because they were used previously)+# and are just now becoming referenced again.+#+# We're going to do two things that are a little bit "fake" to+# help make our simulation easier:+#+# 1. We'll turn off reflogs. You can still run into+# problems with reflogs on, but your objects+# don't get pruned until both the reflog expiration+# has passed on their references, _and_ they are out+# of prune's expiration period. Dropping reflogs+# means we only have to deal with one variable in our tests,+# but the results generalize.+#+# 2. We'll use a temporary index file to create our+# works-in-progress. Most workflows would mention+# referenced objects in the index, which prune takes+# into account. However, many operations don't. For+# example, a partial commit with "git commit foo"+# will use a temporary index. Or they may not need+# an index at all (e.g., creating a new commit+# to refer to an existing tree).++test_description='check pruning of dependent objects'+../test-lib.sh++# We care about reachability, so we do not want to use+# the normal test_commit, which creates extra tags.+add(){+echo"$1">"$1"&&+gitadd"$1"+}+commit(){+test_tick&&+add"$1"&&+gitcommit-m"$1"+}++test_expect_success'disable reflogs''+gitconfigcore.logallrefupdatesfalse&&+rm-rf.git/logs+'++test_expect_success'setup basic history''+commitbase+'++test_expect_success'create and abandon some objects''+gitcheckout-bexperiment&&+commitabandon&&+gitcheckoutmaster&&+gitbranch-Dexperiment+'++test_expect_success'simulate time passing''+find.git/objects-typef|+xargstest-chmtime-v-86400+'++test_expect_success'start writing new commit with old blob''+tree=$(+GIT_INDEX_FILE=index.tmp&&+exportGIT_INDEX_FILE&&+gitread-treeHEAD&&+addunrelated&&+addabandon&&+gitwrite-tree+)+'++test_expect_success'simultaneous gc''+gitgc--prune=12.hours.ago+'++test_expect_success'finish writing out commit''+commit=$(echofoo|gitcommit-tree-pHEAD$tree)&&+gitupdate-refHEAD$commit+'++# "abandon" blob should have been rescued by reference from new tree+test_expect_success'repository passes fsck''+gitfsck+'++test_done
From: Jeff King <hidden> Date: 2016-06-15 23:02:39
When we are loosening unreachable packed objects, we do not
bother to process objects that would simply be pruned
immediately anyway. The "would be pruned" check is a simple
comparison, but is about to get more complicated. Let's pull
it out into a separate function.
Note that this is slightly less efficient than the original,
which avoided even opening old packs, since no object in
them could pass the current check, which cares only about
the pack mtime. But the new rules will depend on the exact
object, so we need to perform the check even for old packs.
Note also that we fix a minor buglet when the pack mtime is
exactly the same as the expiration time. The prune code
considers that worth pruning, whereas our check here
considered it worth keeping. This wasn't a big deal. Besides
being unlikely to happen, the result was simply that the
object was loosened and then pruned, missing the
optimization. Still, we can easily fix it while we are here.
Signed-off-by: Jeff King <redacted>
---
builtin/pack-objects.c | 17 ++++++++++++-----
1 file changed, 12 insertions(+), 5 deletions(-)
From: Jeff King <hidden> Date: 2016-06-15 23:02:39
A recent commit taught git-prune to keep non-recent objects
that are reachable from recent ones. However, pack-objects,
when loosening unreachable objects, tries to optimize out
the write in the case that the object will be immediately
pruned. It now gets this wrong, since its rule does not
reflect the new prune code (and this can be seen by running
t6501 with a strategically placed repack).
Let's teach pack-objects similar logic.
Signed-off-by: Jeff King <redacted>
---
The test changes look big because of the indentation. View with "-w" for
a sane diff.
builtin/pack-objects.c | 38 +++++++++++++++++++
reachable.c | 4 +-
reachable.h | 2 +
t/t6501-freshen-objects.sh | 93 +++++++++++++++++++++++++++-------------------
4 files changed, 97 insertions(+), 40 deletions(-)
@@ -39,50 +39,67 @@ commit () {gitcommit-m"$1"}-test_expect_success'disable reflogs''-gitconfigcore.logallrefupdatesfalse&&-rm-rf.git/logs-'+maybe_repack(){+iftest-n"$repack";then+gitrepack-ad+fi+}++forrepackin''true;do+title=${repack:+repack}+title=${title:-loose}++test_expect_success"make repo completely empty ($title)"'+rm-rf.git&&+gitinit+'++test_expect_success"disable reflogs ($title)"'+gitconfigcore.logallrefupdatesfalse&&+rm-rf.git/logs+'-test_expect_success'setup basic history''-commitbase-'+test_expect_success"setup basic history ($title)"'+commitbase+'-test_expect_success'create and abandon some objects''-gitcheckout-bexperiment&&-commitabandon&&-gitcheckoutmaster&&-gitbranch-Dexperiment-'+test_expect_success"create and abandon some objects ($title)"'+gitcheckout-bexperiment&&+commitabandon&&+maybe_repack&&+gitcheckoutmaster&&+gitbranch-Dexperiment+'-test_expect_success'simulate time passing''-find.git/objects-typef|-xargstest-chmtime-v-86400-'+test_expect_success"simulate time passing ($title)"'+find.git/objects-typef|+xargstest-chmtime-v-86400+'-test_expect_success'start writing new commit with old blob''-tree=$(-GIT_INDEX_FILE=index.tmp&&-exportGIT_INDEX_FILE&&-gitread-treeHEAD&&-addunrelated&&-addabandon&&-gitwrite-tree-)-'+test_expect_success"start writing new commit with old blob ($title)"'+tree=$(+GIT_INDEX_FILE=index.tmp&&+exportGIT_INDEX_FILE&&+gitread-treeHEAD&&+addunrelated&&+addabandon&&+gitwrite-tree+)+'-test_expect_success'simultaneous gc''-gitgc--prune=12.hours.ago-'+test_expect_success"simultaneous gc ($title)"'+gitgc--prune=12.hours.ago+'-test_expect_success'finish writing out commit''-commit=$(echofoo|gitcommit-tree-pHEAD$tree)&&-gitupdate-refHEAD$commit-'+test_expect_success"finish writing out commit ($title)"'+commit=$(echofoo|gitcommit-tree-pHEAD$tree)&&+gitupdate-refHEAD$commit+'-# "abandon" blob should have been rescued by reference from new tree-test_expect_success'repository passes fsck''-gitfsck-'+# "abandon" blob should have been rescued by reference from new tree+test_expect_success"repository passes fsck ($title)"'+gitfsck+'+done test_done
From: Jeff King <hidden> Date: 2016-06-15 23:02:39
When we try to write a loose object file, we first check
whether that object already exists. If so, we skip the
write as an optimization. However, this can interfere with
prune's strategy of using mtimes to mark files in progress.
For example, if a branch contains a particular tree object
and is deleted, that tree object may become unreachable, and
have an old mtime. If a new operation then tries to write
the same tree, this ends up as a noop; we notice we
already have the object and do nothing. A prune running
simultaneously with this operation will see the object as
old, and may delete it.
We can solve this by "freshening" objects that we avoid
writing by updating their mtime. The algorithm for doing so
is essentially the same as that of has_sha1_file. Therefore
we provide a new (static) interface "check_and_freshen",
which finds and optionally freshens the object. It's trivial
to implement freshening and simple checking by tweaking a
single parameter.
Signed-off-by: Jeff King <redacted>
---
sha1_file.c | 51 +++++++++++++++++++++++++++++++++++++++-------
t/t6501-freshen-objects.sh | 27 ++++++++++++++++++++++++
2 files changed, 71 insertions(+), 7 deletions(-)
@@ -100,6 +100,33 @@ for repack in '' true; dotest_expect_success"repository passes fsck ($title)"'gitfsck'++test_expect_success"abandon objects again ($title)"'+gitreset--hardHEAD^&&+find.git/objects-typef|+xargstest-chmtime-v-86400+'++test_expect_success"start writing new commit with same tree ($title)"'+tree=$(+GIT_INDEX_FILE=index.tmp&&+exportGIT_INDEX_FILE&&+gitread-treeHEAD&&+addabandon&&+addunrelated&&+gitwrite-tree+)+'++test_expect_success"simultaneous gc ($title)"'+gitgc--prune=12.hours.ago+'++# tree should have been refreshed by write-tree+test_expect_success"finish writing out commit ($title)"'+commit=$(echofoo|gitcommit-tree-pHEAD$tree)&&+gitupdate-refHEAD$commit+'done test_done
From: René Scharfe <hidden> Date: 2016-06-15 23:02:39
Am 03.10.2014 um 22:21 schrieb Jeff King:
quoted hunk
We check the return value of the callback and stop iterating
if it is non-zero. However, we do not make the non-zero
return value available to the caller, so they have no way of
knowing whether the operation succeeded or not (technically
they can keep their own error flag in the callback data, but
that is unlike our other for_each functions).
Signed-off-by: Jeff King <redacted>
---
cache.h | 2 +-
sha1_file.c | 12 ++++++++----
2 files changed, 9 insertions(+), 5 deletions(-)
From: René Scharfe <hidden> Date: 2016-06-15 23:02:39
Am 03.10.2014 um 22:32 schrieb Jeff King:
quoted hunk
We typically iterate over the reachable objects in a
repository by starting at the tips and walking the graph.
There's no easy way to iterate over all of the objects,
including unreachable ones. Let's provide a way of doing so.
Signed-off-by: Jeff King <redacted>
---
cache.h | 11 +++++++++++
sha1_file.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 73 insertions(+)
From: René Scharfe <hidden> Date: 2016-06-15 23:02:39
Am 03.10.2014 um 22:41 schrieb Jeff King:
quoted hunk
When we try to write a loose object file, we first check
whether that object already exists. If so, we skip the
write as an optimization. However, this can interfere with
prune's strategy of using mtimes to mark files in progress.
For example, if a branch contains a particular tree object
and is deleted, that tree object may become unreachable, and
have an old mtime. If a new operation then tries to write
the same tree, this ends up as a noop; we notice we
already have the object and do nothing. A prune running
simultaneously with this operation will see the object as
old, and may delete it.
We can solve this by "freshening" objects that we avoid
writing by updating their mtime. The algorithm for doing so
is essentially the same as that of has_sha1_file. Therefore
we provide a new (static) interface "check_and_freshen",
which finds and optionally freshens the object. It's trivial
to implement freshening and simple checking by tweaking a
single parameter.
Signed-off-by: Jeff King <redacted>
---
sha1_file.c | 51 +++++++++++++++++++++++++++++++++++++++-------
t/t6501-freshen-objects.sh | 27 ++++++++++++++++++++++++
2 files changed, 71 insertions(+), 7 deletions(-)
Returns 1 if a pack entry is found and freshen_file() fails, and 0 if no
entry is found or freshen_file() succeeds.
It should be "&& !freshen(...)" instead, no?
Or better, let freshen_file() return 1 on success as the other functions
here.
quoted hunk
+
int write_sha1_file(const void *buf, unsigned long len, const char *type, unsigned char *returnsha1)
{
unsigned char sha1[20];
@@ -2961,7 +2998,7 @@ int write_sha1_file(const void *buf, unsigned long len, const char *type, unsign write_sha1_file_prepare(buf, len, type, sha1, hdr, &hdrlen); if (returnsha1) hashcpy(returnsha1, sha1);- if (has_sha1_file(sha1))+ if (freshen_loose_object(sha1) || freshen_packed_object(sha1)) return 0; return write_loose_object(sha1, hdr, hdrlen, buf, len, 0); }
@@ -100,6 +100,33 @@ for repack in '' true; dotest_expect_success"repository passes fsck ($title)"'gitfsck'++test_expect_success"abandon objects again ($title)"'+gitreset--hardHEAD^&&+find.git/objects-typef|+xargstest-chmtime-v-86400+'++test_expect_success"start writing new commit with same tree ($title)"'+tree=$(+GIT_INDEX_FILE=index.tmp&&+exportGIT_INDEX_FILE&&+gitread-treeHEAD&&+addabandon&&+addunrelated&&+gitwrite-tree+)+'++test_expect_success"simultaneous gc ($title)"'+gitgc--prune=12.hours.ago+'++# tree should have been refreshed by write-tree+test_expect_success"finish writing out commit ($title)"'+commit=$(echofoo|gitcommit-tree-pHEAD$tree)&&+gitupdate-refHEAD$commit+'donetest_done
From: Ramsay Jones <hidden> Date: 2016-06-15 23:02:39
On 05/10/14 09:15, René Scharfe wrote:
Am 03.10.2014 um 22:32 schrieb Jeff King:
quoted
We typically iterate over the reachable objects in a
repository by starting at the tips and walking the graph.
There's no easy way to iterate over all of the objects,
including unreachable ones. Let's provide a way of doing so.
Signed-off-by: Jeff King <redacted>
---
cache.h | 11 +++++++++++
sha1_file.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 73 insertions(+)
@@ -3313,3 +3313,65 @@ int for_each_loose_file_in_objdir(const char *path,strbuf_release(&buf);returnr;}++structloose_alt_odb_data{+each_loose_object_fn*cb;+void*data;+};++staticintloose_from_alt_odb(structalternate_object_database*alt,+void*vdata)+{+structloose_alt_odb_data*data=vdata;+returnfor_each_loose_file_in_objdir(alt->base,+data->cb,NULL,NULL,+data->data);+}++intfor_each_loose_object(each_loose_object_fncb,void*data)+{+structloose_alt_odb_dataalt;+intr;++r=for_each_loose_file_in_objdir(get_object_directory(),+cb,NULL,NULL,data);+if(r)+returnr;++alt.cb=cb;+alt.data=data;+returnforeach_alt_odb(loose_from_alt_odb,&alt);+}++intfor_each_object_in_pack(structpacked_git*p,each_packed_object_fncb,void*data)
Should this one be declared static? It seems to be used only in sha1_file.c.
Heh, I was just about to make the same observation myself (with included patch).
I could imagine this function being useful elsewhere, but until it gains some
more external callers I think it should remain static (so it doesn't cause a
sparse warning), rather than add an extern declaration to cache.h (which would
also suppress sparse).
ATB,
Ramsay Jones
quoted
+{
+ uint32_t i;
+ int r = 0;
+
+ for (i = 0; i < p->num_objects; i++) {
+ const unsigned char *sha1 = nth_packed_object_sha1(p, i);
+
+ if (!sha1)
+ return error("unable to get sha1 of object %u in %s",
+ i, p->pack_name);
+
+ r = cb(sha1, p, i, data);
+ if (r)
+ break;
+ }
+ return r;
+}
+
+int for_each_packed_object(each_packed_object_fn cb, void *data)
+{
+ struct packed_git *p;
+ int r = 0;
+
+ prepare_packed_git();
+ for (p = packed_git; p; p = p->next) {
+ r = for_each_object_in_pack(p, cb, data);
+ if (r)
+ break;
+ }
+ return 0;
+}
Perhaps return r instead here?
René
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
.
From: Michael Haggerty <hidden> Date: 2016-06-15 23:02:39
On 10/03/2014 10:22 PM, Jeff King wrote:
quoted hunk
This is not a lot of code, but it's a logical construct that
should not need to be repeated (and we are about to add a
third repetition).
Signed-off-by: Jeff King <redacted>
---
object.c | 12 ++++++++----
1 file changed, 8 insertions(+), 4 deletions(-)
From: Michael Haggerty <hidden> Date: 2016-06-15 23:02:39
On 10/03/2014 10:27 PM, Jeff King wrote:
For small outputs, we sometimes use:
test "$(some_cmd)" = "something we expect"
instead of a full test_cmp. The downside of this is that
when it fails, there is no output at all from the script.
Let's introduce a small helper to make tests easier to
debug.
Signed-off-by: Jeff King <redacted>
---
This is in the same boat as the last commit; we can drop it without
hurting the rest of the series.
Is test_eq too cutesy or obfuscated? I have often wanted it when
debugging other tests, too. Our usual technique is to do:
echo whatever >expect &&
do_something >actual &&
test_cmp expect actual
That's a bit verbose. We could hide it behind something like test_eq,
too, but it introduces several extra new processes. And I know people on
some fork-challenged platforms are very sensitive to the number of
spawned processes in the test suite.
I don't like the three-argument version of test_eq. Wouldn't using a
comparison operator other than "=" would be very confusing, given that
"eq" is in the name of the function? It also doesn't look like you use
this feature.
If you want to write a helper that allows arbitrary comparator
operators, then I think it would be more readable to put the comparison
operator in the middle, like
test_test foo = bar
And in fact once you've done that, couldn't we just make this a generic
wrapper for any `test` command?
test_test () {
if ! test "$@"
then
echo >&2 "test failed: $*"
false
fi
}
Feel free to bikeshed the function name.
An alternative direction to go would be to specialize the function for
equality testing and delegate to test_cmp to get better output for
failures, but optimized to avoid excess process creation in the happy path:
test_eq () {
if test "$1" != "$2"
then
printf "%s" "$1" >expect &&
printf "%s" "$2" >actual &&
test_cmp expect actual
fi
}
(but using properly-created temporary file names).
Finally, if we want a function intended mainly for checking program
output (like the test_eql function suggested by Junio), it might be
simpler to use if it accepts the function output on its stdin:
test_output () {
echo "$1" >expect &&
cat >actual &&
test_cmp expect actual
}
...
do_something | test_output whatever
This would make it easier to generate the input using an arbitrary shell
pipeline.
From: Michael Haggerty <hidden> Date: 2016-06-15 23:02:39
On 10/03/2014 10:29 PM, Jeff King wrote:
Prune has to walk $GIT_DIR/objects/?? in order to find the
set of loose objects to prune. Other parts of the code
(e.g., count-objects) want to do the same. Let's factor it
out into a reusable for_each-style function.
Note that this is not quite a straight code movement. There
are two differences:
1. The original code iterated from 0 to 256, trying to
opendir("$GIT_DIR/%02x"). The new code just does a
readdir() on the object directory, and descends into
any matching directories. This is faster on
already-pruned repositories, and should not ever be
slower (nobody ever creates other files in the object
directory).
This would change the order that the objects are processed. I doubt that
matters to anybody, but it's probably worth mentioning in the commit
message.
quoted hunk
2. The original code had strange behavior when it found a
file of the form "[0-9a-f]{2}/.{38}" that did _not_
contain all hex digits. It executed a "break" from the
loop, meaning that we stopped pruning in that directory
(but still pruned other directories!). This was
probably a bug; we do not want to process the file as
an object, but we should keep going otherwise.
Signed-off-by: Jeff King <redacted>
---
I admit the speedup in (1) almost certainly doesn't matter. It is real,
and I found out about it while writing a different program that was
basically "count-objects" across a large number of repositories. However
for a single repo it's probably not big enough to matter (calling
count-objects in a loop while get dominated by the startup costs). The
end result is a little more obvious IMHO, but that's subjective.
builtin/prune.c | 87 ++++++++++++++++------------------------------------
cache.h | 31 +++++++++++++++++++
sha1_file.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 152 insertions(+), 61 deletions(-)
[...]
@@ -3218,3 +3218,98 @@ void assert_sha1_type(const unsigned char *sha1, enum object_type expect)die("%s is not a valid '%s' object",sha1_to_hex(sha1),typename(expect));}++staticintopendir_error(constchar*path)+{+if(errno==ENOENT)+return0;+returnerror("unable to open %s: %s",path,strerror(errno));+}++staticintfor_each_file_in_obj_subdir(structstrbuf*path,+constchar*prefix,+each_loose_object_fnobj_cb,+each_loose_cruft_fncruft_cb,+each_loose_subdir_fnsubdir_cb,+void*data)+{+size_tbaselen=path->len;+DIR*dir=opendir(path->buf);+structdirent*de;+intr=0;++if(!dir)+returnopendir_error(path->buf);
OK, so if there is a non-directory named $GIT_DIR/objects/33, then we
emit an "unable to open" error rather than treating it as cruft. I think
this is reasonable.
+
+ while ((de = readdir(dir))) {
+ if (is_dot_or_dotdot(de->d_name))
+ continue;
+
+ strbuf_setlen(path, baselen);
+ strbuf_addf(path, "/%s", de->d_name);
+
+ if (strlen(de->d_name) == 38) {
+ char hex[41];
+ unsigned char sha1[20];
+
+ memcpy(hex, prefix, 2);
+ memcpy(hex + 2, de->d_name, 38);
+ hex[40] = 0;
+ if (!get_sha1_hex(hex, sha1)) {
+ if (obj_cb) {
+ r = obj_cb(sha1, path->buf, data);
+ if (r)
+ break;
+ }
+ continue;
+ }
+ }
+
+ if (cruft_cb) {
+ r = cruft_cb(de->d_name, path->buf, data);
So, files *and* directories at the $GIT_DIR/objects/XX/ level are
reported as cruft (as opposed to, say, descending into the directories
and reporting any files found deeper in the hierarchy). This seems fine,
too.
+ if (r)
+ break;
+ }
+ }
+ if (!r && subdir_cb)
+ r = subdir_cb(de->d_name, path->buf, data);
By my reading, path->buf still contains the name of the last file in the
directory at this point. I assume you want to pass it the original
"baselen"-length path here.
+ closedir(dir);
+ return r;
...and anyway, it would be more polite to restore the path strbuf to its
original length before returning.
So other files or directories at the $GIT_DIR/objects/ level are just
ignored; they are not considered cruft. This is worth clarifying in the
docstring.
From: Michael Haggerty <hidden> Date: 2016-06-15 23:02:39
On 10/03/2014 10:39 PM, Jeff King wrote:
[...]
Instead, this patch pushes the extra work onto prune, which
runs less frequently (and has to look at the whole object
graph anyway). It creates a new category of objects: objects
which are not recent, but which are reachable from a recent
object. We do not prune these objects, just like the
reachable and recent ones.
This lets us avoid the recursive check above, because if we
have an object, even if it is unreachable, we should have
its referent:
- if we are creating new objects, then we cannot create
the parent object without having the child
- and if we are pruning objects, will not prune the child
if we are keeping the parent
The big exception would be if one were to write the object
in a way that avoided referential integrity (e.g., using
hash-object). But if you are in the habit of doing that, you
deserve what you get.
Naively, the simplest way to implement this would be to add
all recent objects as tips to the reachability traversal.
However, this does not perform well. In a recently-packed
repository, all reachable objects will also be recent, and
therefore we have to consider each object twice (both as a
tip, and when we reach it in the traversal). I tested this,
and it added about 10s to a 30s prune on linux.git. This
patch instead performs the normal reachability traversal
first, then follows up with a second traversal for recent
objects, skipping any that have already been marked.
I haven't read all of the old code, but if I understand correctly this
is your new algorithm:
1. Walk from all references etc., marking reachable objects.
2. Iterate over *all* objects, in no particular order, skipping the
objects that are already known to be reachable. Use any unreachable
object that has a recent mtime as a tip for a second traversal that
marks all of its references as "to-keep".
3. Iterate over any objects that are not marked "to-keep". (I assume
that this iteration is in no particular order.) For each object:
* [Presumably] verify that its mtime is still "old"
* If so, prune the object
I see some problems with this.
* The one that you mentioned in your cover letter, namely that prune's
final mtime check is not atomic with the object deletion. I agree
that this race is so much shorter than the others that we can accept
a solution that doesn't eliminate it, so let's forget about this one.
* If the final mtime check fails, then the object is recognized as new
and not pruned. But does that prevent its referents from being pruned?
* When this situation is encountered, you would have to start another
object traversal starting at the "renewed" object to mark its
referents "to-keep". I don't see that you do this. Another, much
less attractive alternative would be to abort the prune operation
if this situation arises. But even if you do one of these...
* ...assuming the iteration in step 3 is in no defined order, a
referent might *already* have been pruned before you notice the
"renewed" object.
So although your changes are a big improvement, it seems to me that they
still leave a race with a window approximately as long as the time it
takes to scan and prune the unreachable objects.
I think that the only way to get rid of that race is to delete objects
in parent-to-child order; in other words, *only prune an object after
all objects that refer to it have been pruned*. This could be done by
maintaining reference counts of the to-be-pruned objects and only
deleting an object once its reference count is zero.
The next point that I'm confused by is what happens when a new object or
reference is created while prune is running, and the new object or
reference refers to old objects. I think when we discussed this
privately I claimed that the following freshenings would not be
necessary, but now I think that they are (sorry about that!).
Let's take the simpler case first. Suppose I run the following command
between steps 1 and 3:
git update-ref refs/heads/newbranch $COMMIT
, where $COMMIT is a previously-unreachable object. This doesn't affect
the mtime of $COMMIT, does it? So how does prune know that it shouldn't
delete $COMMIT?
-> So ISTM that updating a reference (or any other traversal starting
point, like the index) must freshen the mtime of any object newly
referred to.
A more complicated case: suppose I create a new $COMMIT referring to an
old $TREE during step 2, *after* prune has scanned the directory that
now contains $COMMIT. (I.e., the scan in step 2 never notices $COMMIT.)
Then I create a new reference pointing at $COMMIT. (I.e., the scan in
step 1 never noticed that the reference exists.) None of this affects
the mtime of $TREE, does it? So how does prune know that it mustn't
prune $TREE?
-> It seems to me that the creation of $COMMIT has to freshen the mtime
of $TREE, so that the final mtime check in step 3 realizes that it
shouldn't prune $TREE. Or to generalize, whenever a new object is
created which refers to existing objects, the direct referents of the
new object have to have their mtimes freshened. However, when an attempt
to write a new object accidentally coincides with an object that already
exists, *that* object needs to be freshened but *its* referents do *not*.
I hope I understood that all correctly...
Michael
--
Michael Haggerty
mhagger@alum.mit.edu
From: Jeff King <hidden> Date: 2016-06-15 23:02:40
On Tue, Oct 07, 2014 at 06:29:00PM +0200, Michael Haggerty wrote:
I haven't read all of the old code, but if I understand correctly this
is your new algorithm:
1. Walk from all references etc., marking reachable objects.
2. Iterate over *all* objects, in no particular order, skipping the
objects that are already known to be reachable. Use any unreachable
object that has a recent mtime as a tip for a second traversal that
marks all of its references as "to-keep".
3. Iterate over any objects that are not marked "to-keep". (I assume
that this iteration is in no particular order.) For each object:
* [Presumably] verify that its mtime is still "old"
* If so, prune the object
Yes, that's more or less accurate. The iteration is in readdir() order
on the filesystem.
We do verify that the mtime is still "old" in the final iteration, but
that is mostly because the existing check was left in. In theory any
recent objects would have been caught in step 2 and marked as "to-keep"
already. Anything we find in step 3 would have to have been racily
created or freshened.
I see some problems with this.
* The one that you mentioned in your cover letter, namely that prune's
final mtime check is not atomic with the object deletion. I agree
that this race is so much shorter than the others that we can accept
a solution that doesn't eliminate it, so let's forget about this one.
Right, I don't see an easy way around this.
* If the final mtime check fails, then the object is recognized as new
and not pruned. But does that prevent its referents from being pruned?
* When this situation is encountered, you would have to start another
object traversal starting at the "renewed" object to mark its
referents "to-keep". I don't see that you do this. Another, much
less attractive alternative would be to abort the prune operation
if this situation arises. But even if you do one of these...
* ...assuming the iteration in step 3 is in no defined order, a
referent might *already* have been pruned before you notice the
"renewed" object.
So although your changes are a big improvement, it seems to me that they
still leave a race with a window approximately as long as the time it
takes to scan and prune the unreachable objects.
Correct. There is a delay between marking objects and deleting them.
This goes for both the existing reachability checks and the new "recent
reachability" check.
As noted above, if we see a fresh object in the final check, then we
know that it was newly freshened (or created). We could then do an
additional traversal with it as the tip, to get a slightly more accurate
view of the world.
The obvious problem as you note is that we may already have deleted its
referents. But let's leave that aside for a moment.
But even if we fix that problem, I don't think traversing again can
eliminate the race. Another process may be freshening or creating
objects after we have processed them (or their containing directories).
So you can catch _some_ cases by re-traversing, but there will always be
cases where we delete an object that has just now become recent (or
reachable, for that matter, if somebody updates the refs).
The obvious solution is to have some atomic view of the object and ref
namespace (i.e., a global write lock that says "I'm pruning, nobody
write"). But that sucks for obvious reasons. I feel like there must be
some more clever solution, but it eludes me. Surely this is something
database people solved 30 years ago. :)
I think that the only way to get rid of that race is to delete objects
in parent-to-child order; in other words, *only prune an object after
all objects that refer to it have been pruned*. This could be done by
maintaining reference counts of the to-be-pruned objects and only
deleting an object once its reference count is zero.
Yes, if you are going to traverse again, you would want to delete in
parent-child order. I'm not convinced that traversing again is worth it;
it's trying to shorten the window, but it can't eliminate it. And my
goal here was never to eliminate the race. It was to keep races to
"simultaneous reference and prune is a problem", and not "ongoing
unbounded operations and simultaneous prune are a problem". And I do not
claim to eliminate the possibility of referents going missing; only to
try to close some obvious and easy holes where it happens.
Let's take the simpler case first. Suppose I run the following command
between steps 1 and 3:
git update-ref refs/heads/newbranch $COMMIT
, where $COMMIT is a previously-unreachable object. This doesn't affect
the mtime of $COMMIT, does it? So how does prune know that it shouldn't
delete $COMMIT?
-> So ISTM that updating a reference (or any other traversal starting
point, like the index) must freshen the mtime of any object newly
referred to.
_If_ the deletion of the object and the checking of its mtime were
atomic, that would be useful to do. But it's not. Before my patch, you
have one way of "saving" the object (and its referents): making it
reachable from a ref. After my patch, you have the additional option of
updating its mtime.
But why bother with the mtime? You can just make it reachable by
updating the ref. Both are racy, but we cannot help that, so one is as
good as the other.
A more complicated case: suppose I create a new $COMMIT referring to an
old $TREE during step 2, *after* prune has scanned the directory that
now contains $COMMIT. (I.e., the scan in step 2 never notices $COMMIT.)
Then I create a new reference pointing at $COMMIT. (I.e., the scan in
step 1 never noticed that the reference exists.) None of this affects
the mtime of $TREE, does it? So how does prune know that it mustn't
prune $TREE?
It doesn't, and you are screwed. :)
You could freshen the referents here, but you are still racy. Just as
you might miss the creation of $COMMIT, you might miss the freshening of
$TREE and delete it.
Making the mtimes race-free requires an atomic check-timestamp-and-delete.
And without that, I'm not sure that shortening the race from 50 system
calls to 3 system calls is worth the additional complexity. If we had
such an atomic operation, even on only a subset of systems, it might
be worth it. But I do not know of any filesystem or system call that can
do so.
I hope I understood that all correctly...
I think your analysis is all correct. The open question is whether it's
worth trying to shrink the last bits of raciness or not (or even whether
there is a clever way of eliminating them that I haven't considered).
-Peff
From: Jeff King <hidden> Date: 2016-06-15 23:02:40
On Tue, Oct 07, 2014 at 04:07:52PM +0200, Michael Haggerty wrote:
On 10/03/2014 10:29 PM, Jeff King wrote:
quoted
Prune has to walk $GIT_DIR/objects/?? in order to find the
set of loose objects to prune. Other parts of the code
(e.g., count-objects) want to do the same. Let's factor it
out into a reusable for_each-style function.
Note that this is not quite a straight code movement. There
are two differences:
1. The original code iterated from 0 to 256, trying to
opendir("$GIT_DIR/%02x"). The new code just does a
readdir() on the object directory, and descends into
any matching directories. This is faster on
already-pruned repositories, and should not ever be
slower (nobody ever creates other files in the object
directory).
This would change the order that the objects are processed. I doubt that
matters to anybody, but it's probably worth mentioning in the commit
message.
Yeah, I don't think it matters, but I'll mention it.
quoted
+ if (!dir)
+ return opendir_error(path->buf);
OK, so if there is a non-directory named $GIT_DIR/objects/33, then we
emit an "unable to open" error rather than treating it as cruft. I think
this is reasonable.
Correct. The original "prune" silently ignored this case, but I think
it makes sense to complain about oddities. We must treat ENOENT
as a noop, even though the value comes from readdir() and therefore
should exist. A simultaneous prune might have deleted it (hopefully
nobody is insane enough to run two prunes at once, but ignoring
directories that went away seems like the only sane behavior to me).
quoted
+ if (cruft_cb) {
+ r = cruft_cb(de->d_name, path->buf, data);
So, files *and* directories at the $GIT_DIR/objects/XX/ level are
reported as cruft (as opposed to, say, descending into the directories
and reporting any files found deeper in the hierarchy). This seems fine,
too.
Yes, this matches the original prune behavior (and anyway, this is the
object database; anything that is not a loose object is cruft).
quoted
+ if (r)
+ break;
+ }
+ }
+ if (!r && subdir_cb)
+ r = subdir_cb(de->d_name, path->buf, data);
By my reading, path->buf still contains the name of the last file in the
directory at this point. I assume you want to pass it the original
"baselen"-length path here.
Ack, good catch. This was originally in the outer for_each_loose_file
loop, but I thought it was more clear to handle it in the subdir
function. Not only is path->buf wrong here, but de->d_name is totally
bogus here.
Will fix in the re-roll.
[...]
So other files or directories at the $GIT_DIR/objects/ level are just
ignored; they are not considered cruft. This is worth clarifying in the
docstring.
I tried to clarify that by indicating that we iterated only over the
"loose-object parts of the object directory". I guess that needs a more
clear definition.
-Peff
Would it be a little safer to set ent->name to NULL or to
object_array_slopbuf after freeing the memory, to prevent accidents?
I considered that, but what about the other parts of object_array_entry?
Should we NULL the object context pointers, too?
The intent of this function is freeing memory, not clearing it for sane
reuse. I think I'd be more in favor of a comment clarifying that. It is
a static function used only internally by the object-array code.
-Peff
Would it be a little safer to set ent->name to NULL or to
object_array_slopbuf after freeing the memory, to prevent accidents?
I considered that, but what about the other parts of object_array_entry?
Should we NULL the object context pointers, too?
The intent of this function is freeing memory, not clearing it for sane
reuse. I think I'd be more in favor of a comment clarifying that. It is
a static function used only internally by the object-array code.
I guess the name reminded me of strbuf_release(), which returns the
strbuf to its newly-initialized state (contrary to what api-strbuf.txt
says, I just noticed). You're right that your function does no such
thing, so it is self-consistent for it not to set ent->name to NULL.
But maybe its name could be chosen better? Let's see if there is a
consensus naming policy for functions that free resources. I grepped for
short functions calling free() and visually inspected a bunch of them.
Functions *_release():
* strbuf_release(), range_set_release(), and diff_ranges_release()
completely reinitialize their arguments
* window_release() appears not to
Functions *_clear() and clear_*():
* All *_clear() functions that I looked at (e.g., argv_array_clear(),
clear_image(), credential_clear(), clear_exclude_list(),
signature_check_clear(), and clear_prio_queue()) completely reinitialize
their arguments
Functions *_free() and free_*():
* Almost all of these free their arguments plus anything that their
arguments point at.
* Confusingly, free_ref_list() and free_pathspec() don't free their
arguments, but rather only the things that their arguments points at.
(Perhaps they should be renamed.)
So while three out of four *_release() functions completely reinitialize
their arguments, there is one that doesn't. And I couldn't find enough
other functions that just free referenced memory without reinitializing
their whole argument to establish a naming pattern. So I guess your
function name is OK too.
So forget I said anything :-)
Michael
--
Michael Haggerty
mhagger@alum.mit.edu
From: Jeff King <hidden> Date: 2016-06-15 23:02:40
On Wed, Oct 08, 2014 at 10:40:03AM +0200, Michael Haggerty wrote:
quoted
The intent of this function is freeing memory, not clearing it for sane
reuse. I think I'd be more in favor of a comment clarifying that. It is
a static function used only internally by the object-array code.
I guess the name reminded me of strbuf_release(), which returns the
strbuf to its newly-initialized state (contrary to what api-strbuf.txt
says, I just noticed). You're right that your function does no such
thing, so it is self-consistent for it not to set ent->name to NULL.
Yeah, I had the same thought while writing it (and ended up with the
same analysis you do below).
Functions *_clear() and clear_*():
I think these ones very clearly are about reinitializing to empty (and
it looks like we follow that rule, which is good).
If we were designing it now, I think strbuf_release() should probably be
called strbuf_clear(). Or maybe that would be too confusing, as it might
imply it is the same thing as strbuf_reset(). Yeesh. Naming is hard.
Functions *_free() and free_*():
* Almost all of these free their arguments plus anything that their
arguments point at.
Yes, that's the rule I think we try to follow.
* Confusingly, free_ref_list() and free_pathspec() don't free their
arguments, but rather only the things that their arguments points at.
(Perhaps they should be renamed.)
Yeah, I would almost say free_pathspec should be called clear_pathspec.
Except it _only_ NULLs the array. It leaves "nr" set, which means that
anybody looking at it will still dereference a bogus pointer (but at
least it's NULL and not freed memory!).
The free_ref_list() function is on my todo list to get rid of as part of
the for-each-ref/branch/tag merger I'd like to do. But somehow that
keeps slipping further down my todo list rather than actually getting
finished. :(
So while three out of four *_release() functions completely reinitialize
their arguments, there is one that doesn't. And I couldn't find enough
other functions that just free referenced memory without reinitializing
their whole argument to establish a naming pattern. So I guess your
function name is OK too.
I'm open to suggestions for totally new names for this concept (free
associated memory, do not reinitialize, but do not free the passed
pointer). But in the absence of one, I think release() is the least-bad.
-Peff
From: Michael Haggerty <hidden> Date: 2016-06-15 23:02:40
On 10/08/2014 09:19 AM, Jeff King wrote:
On Tue, Oct 07, 2014 at 06:29:00PM +0200, Michael Haggerty wrote:
quoted
I haven't read all of the old code, but if I understand correctly this
is your new algorithm:
1. Walk from all references etc., marking reachable objects.
2. Iterate over *all* objects, in no particular order, skipping the
objects that are already known to be reachable. Use any unreachable
object that has a recent mtime as a tip for a second traversal that
marks all of its references as "to-keep".
3. Iterate over any objects that are not marked "to-keep". (I assume
that this iteration is in no particular order.) For each object:
* [Presumably] verify that its mtime is still "old"
* If so, prune the object
Yes, that's more or less accurate. The iteration is in readdir() order
on the filesystem.
We do verify that the mtime is still "old" in the final iteration, but
that is mostly because the existing check was left in. In theory any
recent objects would have been caught in step 2 and marked as "to-keep"
already. Anything we find in step 3 would have to have been racily
created or freshened.
I *like* the mtime check in step 3 and think it should be kept.
quoted
I see some problems with this.
* The one that you mentioned in your cover letter, namely that prune's
final mtime check is not atomic with the object deletion. I agree
that this race is so much shorter than the others that we can accept
a solution that doesn't eliminate it, so let's forget about this one.
Right, I don't see an easy way around this.
I had an idea to mostly get around it; see below.
quoted
* If the final mtime check fails, then the object is recognized as new
and not pruned. But does that prevent its referents from being pruned?
* When this situation is encountered, you would have to start another
object traversal starting at the "renewed" object to mark its
referents "to-keep". I don't see that you do this. Another, much
less attractive alternative would be to abort the prune operation
if this situation arises. But even if you do one of these...
* ...assuming the iteration in step 3 is in no defined order, a
referent might *already* have been pruned before you notice the
"renewed" object.
So although your changes are a big improvement, it seems to me that they
still leave a race with a window approximately as long as the time it
takes to scan and prune the unreachable objects.
Correct. There is a delay between marking objects and deleting them.
This goes for both the existing reachability checks and the new "recent
reachability" check.
As noted above, if we see a fresh object in the final check, then we
know that it was newly freshened (or created). We could then do an
additional traversal with it as the tip, to get a slightly more accurate
view of the world.
The obvious problem as you note is that we may already have deleted its
referents. But let's leave that aside for a moment.
But even if we fix that problem, I don't think traversing again can
eliminate the race. Another process may be freshening or creating
objects after we have processed them (or their containing directories).
...then you would traverse again when you discovered an object freshened
by *that* process.
Please note that these would not be full traversals; you would only have
to traverse starting at the newly freshened object(s), and the traversal
could stop when it hit objects that are already known to be "to-keep".
So they should be quick. (But the length of the residual race wouldn't
depend on their being quick.)
So you can catch _some_ cases by re-traversing, but there will always be
cases where we delete an object that has just now become recent (or
reachable, for that matter, if somebody updates the refs).
The obvious solution is to have some atomic view of the object and ref
namespace (i.e., a global write lock that says "I'm pruning, nobody
write"). But that sucks for obvious reasons. I feel like there must be
some more clever solution, but it eludes me. Surely this is something
database people solved 30 years ago. :)
quoted
I think that the only way to get rid of that race is to delete objects
in parent-to-child order; in other words, *only prune an object after
all objects that refer to it have been pruned*. This could be done by
maintaining reference counts of the to-be-pruned objects and only
deleting an object once its reference count is zero.
Yes, if you are going to traverse again, you would want to delete in
parent-child order. I'm not convinced that traversing again is worth it;
it's trying to shorten the window, but it can't eliminate it. And my
goal here was never to eliminate the race. It was to keep races to
"simultaneous reference and prune is a problem", and not "ongoing
unbounded operations and simultaneous prune are a problem". And I do not
claim to eliminate the possibility of referents going missing; only to
try to close some obvious and easy holes where it happens.
quoted
Let's take the simpler case first. Suppose I run the following command
between steps 1 and 3:
git update-ref refs/heads/newbranch $COMMIT
, where $COMMIT is a previously-unreachable object. This doesn't affect
the mtime of $COMMIT, does it? So how does prune know that it shouldn't
delete $COMMIT?
-> So ISTM that updating a reference (or any other traversal starting
point, like the index) must freshen the mtime of any object newly
referred to.
_If_ the deletion of the object and the checking of its mtime were
atomic, that would be useful to do. But it's not. Before my patch, you
have one way of "saving" the object (and its referents): making it
reachable from a ref. After my patch, you have the additional option of
updating its mtime.
But why bother with the mtime? You can just make it reachable by
updating the ref. Both are racy, but we cannot help that, so one is as
good as the other.
Yes, but the race between the time prune starts reading the references
and the time that it scans all objects to find the ones that were not
marked reachable can be quite long--many seconds for a big repo. During
this whole time, if somebody creates a new reference that refers to a
previously-unreachable object, then prune will corrupt the repository.
On the other hand, if creating a new reference freshens the referent,
then the only race window is the one between prune's final check of the
object's mtime and its deletion of the file, which is only the time for
two consecutive system calls.
This is an enormous difference, and one is definitely not as good as the
other unless perfection is considered the only metric of success.
quoted
A more complicated case: suppose I create a new $COMMIT referring to an
old $TREE during step 2, *after* prune has scanned the directory that
now contains $COMMIT. (I.e., the scan in step 2 never notices $COMMIT.)
Then I create a new reference pointing at $COMMIT. (I.e., the scan in
step 1 never noticed that the reference exists.) None of this affects
the mtime of $TREE, does it? So how does prune know that it mustn't
prune $TREE?
It doesn't, and you are screwed. :)
You could freshen the referents here, but you are still racy. Just as
you might miss the creation of $COMMIT, you might miss the freshening of
$TREE and delete it.
But again, the race window for missing the freshening of $TREE would
only be the time of two consecutive system calls.
Making the mtimes race-free requires an atomic check-timestamp-and-delete.
And without that, I'm not sure that shortening the race from 50 system
calls to 3 system calls is worth the additional complexity. If we had
such an atomic operation, even on only a subset of systems, it might
be worth it. But I do not know of any filesystem or system call that can
do so.
It it were only 50 consecutive system calls, that would be one thing.
But can't the full object traversal take many seconds on a large repo?
That still seems like a pretty big race to me.
I think I found a way to make the final check-timestamp-and-delete safe,
albeit leaving open the possibility that the object is briefly moved to
a different filename. I don't think it's *necessary*, but I think it's
*possible*:
Any process that wants to create a new reference to an existing object
freshens the corresponding file as follows:
1. Write the file (if necessary)
2. Update the file's mtime.
* If the mtime update succeeds, your object is safe against being
pruned (though it might be renamed for a moment; see below)
* If the mtime update fails, treat it as if the object had never
been there (e.g., report an error or write a new copy of the
object). This is the same situation as if the object had been
pruned just before you sought it.
Prune, when it is pretty sure that it wants to delete a file in step 3,
does the following:
1. Check mtime to make sure the file is still stale (this is not
strictly necessary, but prevents an object that has been freshened
since the traversal in step 2 from being temporarily renamed).
2. Rename the file to "<filename>.to-be-deleted" (or, possibly, using
the filename "<filename>.lock" would have good side-effects).
3. Check the mtime again to make sure the file is still stale.
* If yes, then delete the object permanently
* If no, then rename it back to its original name
4. If either of the staleness checks failed, then do an object
traversal to mark this object and any of its (direct or indirect)
referents "to-keep".
I think that this procedure, along with a change to deleting objects in
referrer-then-referent order, would guarantee that prune can never
permanently delete any object that is still be in use, though it might
move such a file to a different filename for a moment.
I'm not sure that this scheme would work on Windows (I seem to recall
that renaming a file on Windows changes its mtime). But nobody in their
right mind would run a Git server on a Windows computer anyway...
Also, to be really super anal about things, there should be a procedure
to reinstate any "<filename>.to-be-deleted" files if the program dies or
if the computer crashes during the final, FINAL mtime check. But that is
almost certainly overkill.
quoted
I hope I understood that all correctly...
I think your analysis is all correct. The open question is whether it's
worth trying to shrink the last bits of raciness or not (or even whether
there is a clever way of eliminating them that I haven't considered).
To be clear, I think your changes are a big improvement, and my ideas
here should not be seen as blockers to your patch series getting
accepted. But I think your changes still leave races that are big enough
that they will be observed on busy Git servers.
Michael
--
Michael Haggerty
mhagger@alum.mit.edu