{"thread":{"id":"10915","subject":"[RFC] Alternates and broken repos: A pack and prune scheme to avoid them","startedAt":"2007-11-18T11:25:52Z","lastAt":"2007-11-29T20:59:55Z","messageCount":14,"participants":["Johannes Sixt","Junio C Hamano","Johannes Schindelin","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"60230","messageId":"200711181225.52288.johannes.sixt@telecom.at","threadId":"10915","inReplyTo":null,"subject":"[RFC] Alternates and broken repos: A pack and prune scheme to avoid them","fromName":"Johannes Sixt","fromEmail":"johannes.sixt@telecom.at","sentAt":"2007-11-18T11:25:52Z","receivedAt":"2007-11-18T11:25:52Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"As you know, repo.or.cz uses alternates in order to reduce the space that the \nrepositories of forked projects require.\n\nRecently, it happened that a fork (4msysgit.git) became broken because it was \nusing an object that was pruned away from the repository that it was \nborrowing from (mingw.git). This happened even though 4msysgit did not use \nthe branch of mingw.git that was rebased and whose objects were pruned. The \nreason is that a merge in 4msysgit.git resulted in a blob that was also in \nthe rebased branch.\n\nTo avoid such situations I propose to introduce \"attic\" packs. They contain \nobjects that are unreachable by the local set of refs. Otherwise they are \nused like regular packs.\n\ngit-repack produces \"attic\" packs like this:\n\n- Places objects of the local object store that are unreachable in an \"attic\" \npack.\n- Copies objects that are reachable but borrowed from an alternate and are \nonly in the alternates' \"attic\" packs into the local regular pack.\n\ngit-prune removes \"attic\" packs.\n\nThen the strategy of garbage collection can be arranged in the following way:\n\n- Repack by starting at the \"most complete\" repo and work towards the \"most \nborrowing\" ones. During this phase \"attic\" packs are created. Borrowing repos \nget a chance to salvage objects before the alternates prune them away.\n\n- Prune by starting at the \"most borrowing\" repo and work towards the \"most \ncomplete\" ones. During this phase the \"attic\" packs are cleaned up.\n\nWhat do you think? Is this a way for a solution?\n\n-- Hannes\n"},{"id":"60243","messageId":"7v3av3wg7h.fsf@gitster.siamese.dyndns.org","threadId":"10915","inReplyTo":"200711181225.52288.johannes.sixt@telecom.at","subject":"Re: [RFC] Alternates and broken repos: A pack and prune scheme to avoid them","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-18T18:39:46Z","receivedAt":"2007-11-18T18:39:46Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt writes:\n\n> Then the strategy of garbage collection can be arranged in the following way:\n>\n> - Repack by starting at the \"most complete\" repo and work towards the \"most \n> borrowing\" ones. During this phase \"attic\" packs are created. Borrowing repos \n> get a chance to salvage objects before the alternates prune them away.\n>\n> - Prune by starting at the \"most borrowing\" repo and work towards the \"most \n> complete\" ones. During this phase the \"attic\" packs are cleaned up.\n>\n> What do you think? Is this a way for a solution?\n\nI would imagine that would work as long as it can be controlled\nwhen all the involved repositories are repacked and pruned, such\nas on repo.or.cz case (but on the other hand it is not really\ncontrolled well there and that is the reason you wrote the\nmessage X-<).\n"},{"id":"60250","messageId":"200711182101.53936.johannes.sixt@telecom.at","threadId":"10915","inReplyTo":"7v3av3wg7h.fsf@gitster.siamese.dyndns.org","subject":"Re: [RFC] Alternates and broken repos: A pack and prune scheme to avoid them","fromName":"Johannes Sixt","fromEmail":"johannes.sixt@telecom.at","sentAt":"2007-11-18T20:01:53Z","receivedAt":"2007-11-18T20:01:53Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"On Sunday 18 November 2007 19:39, Junio C Hamano wrote:\n> Johannes Sixt writes:\n> > Then the strategy of garbage collection can be arranged in the following\n> > way:\n> >\n> > - Repack by starting at the \"most complete\" repo and work towards the\n> > \"most borrowing\" ones. During this phase \"attic\" packs are created.\n> > Borrowing repos get a chance to salvage objects before the alternates\n> > prune them away.\n> >\n> > - Prune by starting at the \"most borrowing\" repo and work towards the\n> > \"most complete\" ones. During this phase the \"attic\" packs are cleaned up.\n> >\n> > What do you think? Is this a way for a solution?\n>\n> I would imagine that would work as long as it can be controlled\n> when all the involved repositories are repacked and pruned, such\n> as on repo.or.cz case (but on the other hand it is not really\n> controlled well there and that is the reason you wrote the\n> message X-<).\n\nWell, I think in many situations pack and prune can be controlled. To be \nprecise, if alternates are used pack and prune *must* be controlled. \nCurrently, the control is very simple: \"don't prune\" (and I don't recall ATM \nwhat you must not do when you repack).\n\nAnyway, judging from the responses so far it seems that people can live \nwith \"don't prune\" (or not using alternates) ;-) Repositories getting broken \nthis way isn't exactly my itch, either, so... I spelled out a possible \nsolution if someone wants to pick up the topic.\n\n-- Hannes\n"},{"id":"60251","messageId":"7v7ikfuxfk.fsf@gitster.siamese.dyndns.org","threadId":"10915","inReplyTo":"200711182101.53936.johannes.sixt@telecom.at","subject":"Re: [RFC] Alternates and broken repos: A pack and prune scheme to avoid them","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-18T20:10:39Z","receivedAt":"2007-11-18T20:10:39Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt writes:\n\n> On Sunday 18 November 2007 19:39, Junio C Hamano wrote:\n> ...\n>> I would imagine that would work as long as it can be controlled\n>> when all the involved repositories are repacked and pruned, such\n>> as on repo.or.cz case (but on the other hand it is not really\n>> controlled well there and that is the reason you wrote the\n>> message X-<).\n>\n> Well, I think in many situations pack and prune can be controlled. To be \n> precise, if alternates are used pack and prune *must* be controlled.\n> Currently, the control is very simple: \"don't prune\" (and I don't recall ATM \n> what you must not do when you repack).\n>\n> Anyway, judging from the responses so far it seems that people can live \n> with \"don't prune\" (or not using alternates) ;-)\n\nBecause my point was not \"don't prune is good enough\", I think\nyou are judging from too small number of responses (in fact,\nzero).\n\nMy point was that even the existing setup that is well known to\nthe public (i.e. repo.or.cz) does not seem to be controlled, and\nadding a nicer mechanism (e.g. I do not think there currently is\na canned way to prepare a pack that contains only unreachable\nobjects --- you need to script it anew) for a better control may\nnot help the situation much, unless it is actually used.\n"},{"id":"61360","messageId":"Pine.LNX.4.64.0711290340470.27959@racer.site","threadId":"10915","inReplyTo":"7v7ikfuxfk.fsf@gitster.siamese.dyndns.org","subject":"[PATCH/RFC] Teach repack to optionally retain otherwise lost objects","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-11-29T03:41:42Z","receivedAt":"2007-11-29T03:41:42Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"\nWhen specifying --attic=, the objects that would be lost when\ncalling repack with -d will be put into a packfile (or multiple\npackfiles), using the file name prefix .\n\nSigned-off-by: Johannes Schindelin \n---\n\n\tThis implements the idea of Hannes.\n\n\tThe plan for repo.or.cz is now to invoke repack with\n\t\"--attic=attic\" and copied attic-*.{idx,pack} to all the forks'\n\tobject stores, then delete the original attic-*{.idx,pack}.\n\n\tThe beauty of that approach is that the order in which the\n\trepositories are repacked is no longer important.\n\n\tThis patch is marked RFC since there is a severe bottleneck\n\there: the new pack's index is sorted and made unique and every\n\tSHA-1 displayed twice, then the old pack's index is sorted and\n\tmade unique. Then the combined result is sorted and only the\n\tnow-unique SHA-1s are actually packed.\n\n\t(The sort is not necessary if there is only _one_ pack.\n\tHowever, we cannot guarantee that.)\n\n\tOf course, this is quick 'n dirty, and the price to be paid\n\tis a substantial performance hit: in my tests, linux-2.6.git\n\tneeded half a second to show its pack's index, but that\n\tsed 's/^.* //' | sort | uniq | sed p mantra needs 19 seconds.\n\n\tThe obvious thing is to exploit the fact that the pack indices\n\tare already sorted:\n\n\tI started patch git-show-index so it takes an argument\n\t--missing-objects, followed by the new pack index file names,\n\tfollowed by --, followed be the old pack index file names.\n\n\tThen it would traverse all of them simultaneously, outputting\n\tonly the SHA-1s of objects that are in an old pack, but not\n\tin any of the new packs.\n\n\tTwo issues: there might be a whole lot of pack files (Pasky\n\ttold me today that in one instance there were 416 pack files!)\n\tand that might well exceed the maximum number of open files.\n\n\tSecond issue: there are two different pack index formats, and\n\tthe code is not easily refactored AFAICT.\n\n\tProbably a better method would be not to read the files\n\tsimultaneously, but fill a \"struct decorate *\" with objects\n\t(which can be faked, as we do not really need to parse them)\n\tof the new packs, and then only use decorate_lookup() to determine\n\tfor all old packs' objects if they are present in the new ones.\n\n\tThe latter approach would allow for a relatively easy refactoring\n\tof show-index.c; just provide a callback for each entry.\n\n\tHowever, I am way too tired today to do it.\n\n\tBesides, a completely different idea just struck me: before\n\trepacking, .git/objects/pack/* could be _hard linked_ to the\n\tforkee's object stores. Then nothing in git-repack's code\n\tneeds to be changed.\n\n\tOh, well. I just wasted 1.5 hours.\n\n Documentation/git-repack.txt | 4 +++\n git-repack.sh | 40 +++++++++++++++++++++++++++++++++----\n t/t5303-repack-attic.sh | 44 ++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 83 insertions(+), 5 deletions(-)\n create mode 100644 t/t5303-repack-attic.sh\n\ndiff --git a/Documentation/git-repack.txt b/Documentation/git-repack.txt\nindex 12e2079..ec2c2bf 100644\n--- a/Documentation/git-repack.txt\n+++ b/Documentation/git-repack.txt\n@@ -84,6 +84,10 @@ OPTIONS\n \tIf specified, multiple packfiles may be created.\n \tThe default is unlimited.\n \n+--attic=::\n+\tPut all objects that would/will be lost when running with `-d`\n+\tinto its own packfile(s), with file name prefix ``.\n+\n \n Configuration\n -------------\ndiff --git a/git-repack.sh b/git-repack.sh\nindex e18eb3f..f83d6f0 100755\n--- a/git-repack.sh\n+++ b/git-repack.sh\n@@ -18,12 +18,13 @@ window= size of the window used for delta compression\n window-memory= same as the above, but limit memory size instead of entries count\n depth= limits the maximum delta depth\n max-pack-size= maximum size of each packfile\n+attic= pack no-longer-packed used objects into an \"attic\" pack\n \"\n SUBDIRECTORY_OK='Yes'\n . git-sh-setup\n \n no_update_info= all_into_one= remove_redundant= keep_unreachable=\n-local= quiet= no_reuse= extra=\n+local= quiet= no_reuse= extra= attic=\n while test $# != 0\n do\n \tcase \"$1\" in\n@@ -37,6 +38,8 @@ do\n \t-l)\tlocal=--local ;;\n \t--max-pack-size|--window|--window-memory|--depth)\n \t\textra=\"$extra $1=$2\"; shift ;;\n+\t--attic)\n+\t\tattic=\"$2\"; shift ;;\n \t--) shift; break;;\n \t*)\tusage ;;\n \tesac\n@@ -119,6 +122,36 @@ for name in $names ; do\n \trm -f \"$PACKDIR/old-pack-$name.pack\" \"$PACKDIR/old-pack-$name.idx\"\n done\n \n+new_existing=\n+for e in $existing\n+do\n+\tcase \"$ fullbases \" in\n+\t*\" $e \"*) ;;\n+\t*)\n+\t\tnew_existing=\"$new_existing $e\"\n+\t\t;;\n+\tesac\n+done\n+existing=\"$new_existing\"\n+\n+if test ! -z \"$attic\"\n+then\n+\t# Find the objects which were in the existing packs, but are no\n+\t# longer in the new ones.\n+\t#\n+\t# This could be much more efficient.\n+\t(for name in $names\n+\t do\n+\t\tgit show-index < $PACKDIR/pack-$name.idx\n+\t done | sed 's/^.* //' | sort | uniq | sed p &&\n+\t for e in $existing\n+\t do\n+\t\tgit show-index < \"$PACKDIR/$e.idx\"\n+\t done | sed 's/^.* //' | sort | uniq) | sort | uniq -u |\n+\tgit pack-objects --non-empty \"$attic\" ||\n+\t\tdie \"Could not create attic '$attic'.\"\n+fi\n+\n if test \"$remove_redundant\" = t\n then\n \t# We know $existing are all redundant.\n@@ -128,10 +161,7 @@ then\n \t\t( cd \"$PACKDIR\" &&\n \t\t for e in $existing\n \t\t do\n-\t\t\tcase \" $fullbases \" in\n-\t\t\t*\" $e \"*) ;;\n-\t\t\t*)\trm -f \"$e.pack\" \"$e.idx\" \"$e.keep\" ;;\n-\t\t\tesac\n+\t\t\trm -f \"$e.pack\" \"$e.idx\" \"$e.keep\"\n \t\t done\n \t\t)\n \tfi\ndiff --git a/t/t5303-repack-attic.sh b/t/t5303-repack-attic.sh\nnew file mode 100644\nindex 0000000..9777748\n--- /dev/null\n+++ b/t/t5303-repack-attic.sh\n@@ -0,0 +1,44 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2007 Johannes E. Schindelin\n+#\n+\n+test_description='repack with an attic pack'\n+. ./test-lib.sh\n+\n+test_expect_success 'setup' '\n+\n+\techo \"Ten weary, footsore wanderers,\" > file &&\n+\tgit add file &&\n+\ttest_tick &&\n+\tgit commit -m initial &&\n+\techo \"all in a woeful plight,\" >> file &&\n+\ttest_tick &&\n+\tgit commit -m second file &&\n+\techo \"sought shelter in a wayside-inn\" >> file &&\n+\ttest_tick &&\n+\tgit commit -m third file &&\n+\techo \"one dark and lonely night.\" >> file &&\n+\ttest_tick &&\n+\tgit commit -m fourth file &&\n+\techo \">>Nine rooms, no more<<, the landlord said,\" >> file &&\n+\ttest_tick && git commit -m fifth file &&\n+\tgit repack -a -d &&\n+\t! ls .git/objects/??/*\n+\n+'\n+\n+test_expect_success 'create attic pack' '\n+\n+\tLAST_VERSION=$(git rev-parse --verify HEAD:file) &&\n+\tgit reset --hard HEAD^ &&\n+\trm .git/logs/HEAD .git/logs/refs/heads/master &&\n+\tgit cat-file blob $LAST_VERSION &&\n+\tgit repack --attic=attic -a -d &&\n+\t! git cat-file blob $LAST_VERSION &&\n+\ttest -f attic-*.idx &&\n+\tcat attic-*.idx | git show-index | grep $LAST_VERSION\n+\n+'\n+\n+test_done\n-- \n1.5.3.6.2066.g09421\n"},{"id":"61367","messageId":"7vaboxy3va.fsf@gitster.siamese.dyndns.org","threadId":"10915","inReplyTo":"Pine.LNX.4.64.0711290340470.27959@racer.site","subject":"Re: [PATCH/RFC] Teach repack to optionally retain otherwise lost objects","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-11-29T06:15:05Z","receivedAt":"2007-11-29T06:15:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n> \tBesides, a completely different idea just struck me: before\n> \trepacking, .git/objects/pack/* could be _hard linked_ to the\n> \tforkee's object stores. Then nothing in git-repack's code\n> \tneeds to be changed.\n>\n> \tOh, well. I just wasted 1.5 hours.\n\nYour 1.5 hours was spent wisely to come up with that idea ;-).\n\nTo make sure I understand your idea correctly, the procedure to repack a\nrepository in a fork-friendly way is:\n\n (1) find the project directly forked from you;\n\n (2) hardlink all packs under your object store to their object store;\n\n (3) repack -a -l and prune.\n\nI think that would work as long as you do the above as a unit and handle\none repository at a time. Otherwise I think you risk losing necessary\nobjects when hierarchical forks are involved. E.g. if you have a\nproject X that has a fork Y which in turn has fork Z.\n\n\t* Step 1 is run for X, Y and Z.\n * Step 2 is run for Y and Z.\n * Step 3 is run for Z.\n\nAt this point, Z is still borrowing objects from Y and X through Y, and\nit will not keep objects it is borrowing from X through Y. Then if the\nprocedure is intermixed like this, a bad thing happens.\n\n\t* Step 2 is run for X.\n\t* Step 3 is run for Y.\n\t* Step 3 is run for X.\n\nStep 3 for Y would lose objects Y was borrowing from X that were not\nused by Y itself. At this point, Z is still usable as the objects it is\nborrowing from X though Y have not been pruned from X. But Step 3 for X\nwill lose them, rendering Z unusable.\n"},{"id":"61389","messageId":"Pine.LNX.4.64.0711291146090.27959@racer.site","threadId":"10915","inReplyTo":"7vaboxy3va.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH/RFC] Teach repack to optionally retain otherwise lost objects","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-11-29T11:57:26Z","receivedAt":"2007-11-29T11:57:26Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 28 Nov 2007, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n> \n> > \tBesides, a completely different idea just struck me: before\n> > \trepacking, .git/objects/pack/* could be _hard linked_ to the\n> > \tforkee's object stores. Then nothing in git-repack's code\n> > \tneeds to be changed.\n> >\n> > \tOh, well. I just wasted 1.5 hours.\n> \n> Your 1.5 hours was spent wisely to come up with that idea ;-).\n\nThanks ;-)\n\n> To make sure I understand your idea correctly, the procedure to repack a \n> repository in a fork-friendly way is:\n> \n> (1) find the project directly forked from you;\n> \n> (2) hardlink all packs under your object store to their object store;\n> \n> (3) repack -a -l and prune.\n\nYep.\n\n> I think that would work as long as you do the above as a unit and handle\n> one repository at a time.\n\nExactly. See\n\nhttp://repo.or.cz/w/repo.git?a=commitdiff;h=fba501deabd349afbe3b8bf89f385889889e04ac\n\nfor a tired proposal.\n\nNote that \"prune\" is not (yet) an option, since it could possibly destroy \nobjects which are needed in an ongoing push operation.\n\nHowever, we could do exactly the same as with reflogs: introduce a grace \nperiod (with loose objects, we can use the ctime...)\n\n> Otherwise I think you risk losing necessary objects when hierarchical \n> forks are involved. E.g. if you have a project X that has a fork Y \n> which in turn has fork Z.\n\nWell, in theory you could also iterate over all projects and hard link the \npacks/objects of their alternates, and _then_ iterate and repack. But it \nis simpler and more obvious in the case of repo.or.cz to do all in one \niteration, because we can order the repository names easily so that \nforkees come first, _and_ we have an easy way to find out what are the \nforks of a project.\n\nCiao,\nDscho\n"},{"id":"61398","messageId":"Pine.LNX.4.64.0711291419350.27959@racer.site","threadId":"10915","inReplyTo":"Pine.LNX.4.64.0711291146090.27959@racer.site","subject":"[PATCH] Add \"--expire