{"thread":{"id":"2409","subject":"[PATCH 0/4] Add git-pack-intersect","startedAt":"2005-11-09T01:20:59Z","lastAt":"2005-11-10T00:15:17Z","messageCount":10,"participants":["Lukas Sandström","Petr Baudis","Andreas Ericsson","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"11368","messageId":"43714EFB.5070705@etek.chalmers.se","threadId":"2409","inReplyTo":null,"subject":"[PATCH 0/4] Add git-pack-intersect","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-09T01:20:59Z","receivedAt":"2005-11-09T01:20:59Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"This patch series adds git-pack-intersect. It finds redundant packs\nby calculating the union of all objects present in .git/objects/pack\nand then computing the smallest set of packs which contain all the\nobjects in this union.\n\nIt is quite fast, if I may say so myself. On my AMD3200+ it manages\nto minimize a linux-2.6 repository with 9 pack files totaling 430MB\nin ~0.7 seconds. The remaining packfiles total 102MB, which is a nice\nreduction.\n\ngit-fsck-objects reports no errors after pruning, but the algorithm is \nnot proven correct so backups might be in order before this gets more\ntesting.\n\n/Lukas\n"},{"id":"11369","messageId":"43714F60.6030508@etek.chalmers.se","threadId":"2409","inReplyTo":"43714EFB.5070705@etek.chalmers.se","subject":"[PATCH 1/4] Add git-pack-intersect","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-09T01:22:40Z","receivedAt":"2005-11-09T01:22:40Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Add git-pack-intersect\n\nThis patch adds the program git-pack-intersect. It is\nused to find redundant packs in git repositories.\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\n\n Makefile         |    2 \n pack-intersect.c |  577 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n sha1_file.c      |    3 \n 3 files changed, 581 insertions(+), 1 deletions(-)\n create mode 100644 pack-intersect.c\n\napplies-to: bb7dd65e1d945edbe0137a761ebc388c7394067a\ncb2f9b435d8101fd29454b77fb5047b7edf847dc\ndiff --git a/Makefile b/Makefile\nindex b202be1..4c646c9 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -122,7 +122,7 @@ PROGRAMS = \\\n \tgit-unpack-objects$X git-update-index$X git-update-server-info$X \\\n \tgit-upload-pack$X git-verify-pack$X git-write-tree$X \\\n \tgit-update-ref$X git-symbolic-ref$X git-check-ref-format$X \\\n-\tgit-name-rev$X $(SIMPLE_PROGRAMS)\n+\tgit-name-rev$X git-pack-intersect$X $(SIMPLE_PROGRAMS)\n \n # Backward compatibility -- to be removed after 1.0\n PROGRAMS += git-ssh-pull$X git-ssh-push$X\ndiff --git a/pack-intersect.c b/pack-intersect.c\nnew file mode 100644\nindex 0000000..2267478\n--- /dev/null\n+++ b/pack-intersect.c\n@@ -0,0 +1,577 @@\n+/*\n+*\n+* Copyright 2005, Lukas Sandstrom <lukass@etek.chalmers.se>\n+*\n+* This file is licensed under the GPL v2.\n+*\n+*/\n+\n+#include \"cache.h\"\n+\n+static const char pack_intersect_usage[] =\n+\"git-pack-intersect [ -v ]  < -a | <.pack filename> ...>\";\n+\n+int all = 0, verbose = 0;\n+\n+struct llist_item {\n+\tstruct llist_item *next;\n+\tchar *sha1;\n+};\n+struct llist {\n+\tstruct llist_item *front;\n+\tstruct llist_item *back;\n+\tsize_t size;\n+} *all_objects;\n+\n+struct pack_list {\n+\tstruct pack_list *next;\n+\tstruct packed_git *pack;\n+\tstruct llist *unique_objects;\n+\tstruct llist *all_objects;\n+} *pack_list;\n+\n+struct pll {\n+\tstruct pll *next;\n+\tstruct pack_list *pl;\n+};\n+\n+inline void llist_free(struct llist *list)\n+{\n+\twhile((list->back = list->front)) {\n+\t\tlist->front = list->front->next;\n+\t\tfree(list->back);\n+\t}\n+\tfree(list);\n+}\n+\n+inline void llist_init(struct llist **list)\n+{\n+\t*list = xmalloc(sizeof(struct llist));\n+\t(*list)->front = (*list)->back = NULL;\n+\t(*list)->size = 0;\n+}\n+\n+struct llist * llist_copy(struct llist *list)\n+{\n+\tstruct llist *ret;\n+\tstruct llist_item *new, *old, *prev;\n+\t\n+\tllist_init(&ret);\n+\n+\tif ((ret->size = list->size) == 0)\n+\t\treturn ret;\n+\n+\tnew = ret->front = xmalloc(sizeof(struct llist_item));\n+\tnew->sha1 = list->front->sha1;\n+\n+\told = list->front->next;\n+\twhile (old) {\n+\t\tprev = new;\n+\t\tnew = xmalloc(sizeof(struct llist_item));\n+\t\tprev->next = new;\n+\t\tnew->sha1 = old->sha1;\n+\t\told = old->next;\n+\t}\n+\tnew->next = NULL;\n+\tret->back = new;\n+\t\n+\treturn ret;\n+}\n+\n+inline struct llist_item * llist_insert(struct llist *list,\n+\t\t\t\t\tstruct llist_item *after, char *sha1)\n+{\n+\tstruct llist_item *new = xmalloc(sizeof(struct llist_item));\n+\tnew->sha1 = sha1;\n+\tnew->next = NULL;\n+\n+\tif (after != NULL) {\n+\t\tnew->next = after->next;\n+\t\tafter->next = new;\n+\t\tif (after == list->back)\n+\t\t\tlist->back = new;\n+\t} else {/* insert in front */\n+\t\tif (list->size == 0)\n+\t\t\tlist->back = new;\n+\t\telse\n+\t\t\tnew->next = list->front;\n+\t\tlist->front = new;\n+\t}\n+\tlist->size++;\n+\treturn new;\n+}\n+\n+inline struct llist_item * llist_insert_back(struct llist *list, char *sha1)\n+{\n+\treturn llist_insert(list, list->back, sha1);\n+}\n+\n+inline struct llist_item * llist_insert_sorted_unique(struct llist *list,\n+\t\t\t\t\tchar *sha1, struct llist_item *hint)\n+{\n+\tstruct llist_item *prev = NULL, *l;\n+\n+\tl = (hint == NULL) ? list->front : hint;\n+\twhile (l) {\n+\t\tint cmp = memcmp(l->sha1, sha1, 20);\n+\t\tif (cmp > 0) { /* we insert before this entry */\n+\t\t\treturn llist_insert(list, prev, sha1);\n+\t\t}\n+\t\tif(!cmp) { /* already exists */\n+\t\t\treturn l;\n+\t\t}\n+\t\tprev = l;\n+\t\tl = l->next;\n+\t}\n+\t/* insert at the end */\n+\treturn llist_insert_back(list, sha1);\n+}\n+\n+/* computes A\\B */\n+struct llist * llist_sorted_difference(struct llist_item *A,\n+\t\t\t\t       struct llist_item *B)\n+{\n+\tstruct llist *ret;\n+\tllist_init(&ret);\n+\n+\twhile (A != NULL && B != NULL) {\n+\t\tint cmp = memcmp(A->sha1, B->sha1, 20);\n+\t\tif (!cmp) {\n+\t\t\tA = A->next;\n+\t\t\tB = B->next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif(cmp > 0) { /* we'll never find this B */\n+\t\t\tB = B->next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\t/* A has the object, B doesn't */\n+\t\tllist_insert_back(ret, A->sha1);\n+\t\tA = A->next;\n+\t}\n+\twhile (A != NULL) {\n+\t\tllist_insert_back(ret, A->sha1);\n+\t\tA = A->next;\n+\t}\n+\treturn ret;\n+}\n+\n+/* returns a pointer to an item in front of sha1 */\n+inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1,\n+\t\t\t\t\t       struct llist_item *hint)\n+{\n+\tstruct llist_item *prev, *l;\n+\n+redo_from_start:\n+\tl = (hint == NULL) ? list->front : hint;\n+\tprev = NULL;\n+\twhile (l) {\n+\t\tint cmp = memcmp(l->sha1, sha1, 20);\n+\t\tif (cmp > 0) /* not in list, since sorted */\n+\t\t\treturn prev;\n+\t\tif(!cmp) { /* found */\n+\t\t\tif (prev == NULL) {\n+\t\t\t\tif (hint != NULL && hint != list->front) {\n+\t\t\t\t\t/* we don't know the previous element */\n+\t\t\t\t\thint = NULL;\n+\t\t\t\t\tgoto redo_from_start;\n+\t\t\t\t}\n+\t\t\t\tlist->front = l->next;\n+\t\t\t} else\n+\t\t\t\tprev->next = l->next;\n+\t\t\tif (l == list->back)\n+\t\t\t\tlist->back = prev;\n+\t\t\tfree(l);\n+\t\t\tlist->size--;\n+\t\t\treturn prev;\n+\t\t}\n+\t\tprev = l;\n+\t\tl = l->next;\n+\t}\n+\treturn prev;\n+}\n+\n+inline struct pack_list * pack_list_insert(struct pack_list **pl,\n+\t\t\t\t\t   struct pack_list *entry)\n+{\n+\tstruct pack_list *p = xmalloc(sizeof(struct pack_list));\n+\tmemcpy(p, entry, sizeof(struct pack_list));\n+\tp->next = *pl;\n+\t*pl = p;\n+\treturn p;\n+}\n+\n+struct pack_list * pack_list_difference(struct pack_list *A,\n+\t\t\t\t\tstruct pack_list *B)\n+{\n+\tstruct pack_list *ret, *pl;\n+\n+\tif (A == NULL)\n+\t\treturn NULL;\n+\n+\tpl = B;\n+\twhile (pl != NULL) {\n+\t\tif (A->pack == pl->pack)\n+\t\t\treturn pack_list_difference(A->next, B);\n+\t\tpl = pl->next;\n+\t}\n+\tret = xmalloc(sizeof(struct pack_list));\n+\tmemcpy(ret, A, sizeof(struct pack_list));\n+\tret->next = pack_list_difference(A->next, B);\n+\treturn ret;\n+}\n+\n+void cmp_two_packs(struct pack_list *p1, struct pack_list *p2)\n+{\n+\tint p1_off, p2_off;\n+\tvoid *p1_base, *p2_base;\n+\tstruct llist_item *p1_hint = NULL, *p2_hint = NULL;\n+\t\n+\tp1_off = p2_off = 256 * 4 + 4;\n+\tp1_base = (void *)p1->pack->index_base;\n+\tp2_base = (void *)p2->pack->index_base;\n+\n+\twhile (p1_off <= p1->pack->index_size - 3 * 20 &&\n+\t       p2_off <= p2->pack->index_size - 3 * 20)\n+\t{\n+\t\tint cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);\n+\t\t/* cmp ~ p1 - p2 */\n+\t\tif (cmp == 0) {\n+\t\t\tp1_hint = llist_sorted_remove(p1->unique_objects,\n+\t\t\t\t\tp1_base + p1_off, p1_hint);\n+\t\t\tp2_hint = llist_sorted_remove(p2->unique_objects,\n+\t\t\t\t\tp1_base + p1_off, p2_hint);\n+\t\t\tp1_off+=24;\n+\t\t\tp2_off+=24;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (cmp < 0) { /* p1 has the object, p2 doesn't */\n+\t\t\tp1_off+=24;\n+\t\t} else { /* p2 has the object, p1 doesn't */\n+\t\t\tp2_off+=24;\n+\t\t}\n+\t}\n+}\n+\n+/* all the permutations have to be free()d at the same time,\n+ * since they refer to each other\n+ */\n+struct pll * get_all_permutations(struct pack_list *list)\n+{\n+\tstruct pll *subset, *pll, *new_pll = NULL; /*silence warning*/\n+\n+\tif (list == NULL)\n+\t\treturn NULL;\n+\n+\tif (list->next == NULL) {\n+\t\tnew_pll = xmalloc(sizeof(struct pll));\n+\t\tnew_pll->next = NULL;\n+\t\tnew_pll->pl = list;\n+\t\treturn new_pll;\n+\t}\n+\n+\tpll = subset = get_all_permutations(list->next);\n+\twhile (pll) {\n+\t\tnew_pll = xmalloc(sizeof(struct pll));\n+\t\tnew_pll->next = pll->next;\n+\t\tpll->next = new_pll;\n+\n+\t\tnew_pll->pl = xmalloc(sizeof(struct pack_list));\n+\t\tmemcpy(new_pll->pl, list, sizeof(struct pack_list));\n+\t\tnew_pll->pl->next = pll->pl;\n+\n+\t\tpll = new_pll->next;\n+\t}\n+\t/* add ourself to the end */\n+\tnew_pll->next = xmalloc(sizeof(struct pll));\n+\tnew_pll->next->pl = xmalloc(sizeof(struct pack_list));\n+\tnew_pll->next->next = NULL;\n+\tmemcpy(new_pll->next->pl, list, sizeof(struct pack_list));\n+\tnew_pll->next->pl->next = NULL;\n+\n+\treturn subset;\n+}\n+\n+int is_superset(struct pack_list *pl, struct llist *list)\n+{\n+\tstruct llist *diff, *old;\n+\n+\tdiff = llist_copy(list);\n+\n+\twhile (pl) {\n+\t\told = diff;\n+\t\tdiff = llist_sorted_difference(diff->front,\n+\t\t\t\t\t       pl->all_objects->front);\n+\t\tllist_free(old);\n+\t\tif (diff->size == 0) { /* we're done */\n+\t\t\tllist_free(diff);\n+\t\t\treturn 1;\n+\t\t}\n+\t\tpl = pl->next;\n+\t}\n+\tllist_free(diff);\n+\treturn 0;\n+}\n+\n+size_t sizeof_union(struct packed_git *p1, struct packed_git *p2)\n+{\n+\tsize_t ret = 0;\n+\tint p1_off, p2_off;\n+\tvoid *p1_base, *p2_base;\n+\n+\tp1_off = p2_off = 256 * 4 + 4;\n+\tp1_base = (void *)p1->index_base;\n+\tp2_base = (void *)p2->index_base;\n+\n+\twhile (p1_off <= p1->index_size - 3 * 20 &&\n+\t       p2_off <= p2->index_size - 3 * 20)\n+\t{\n+\t\tint cmp = memcmp(p1_base + p1_off, p2_base + p2_off, 20);\n+\t\t/* cmp ~ p1 - p2 */\n+\t\tif (cmp == 0) {\n+\t\t\tret++;\n+\t\t\tp1_off+=24;\n+\t\t\tp2_off+=24;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (cmp < 0) { /* p1 has the object, p2 doesn't */\n+\t\t\tp1_off+=24;\n+\t\t} else { /* p2 has the object, p1 doesn't */\n+\t\t\tp2_off+=24;\n+\t\t}\n+\t}\n+\treturn ret;\n+}\n+\n+/* another O(n^2) function ... */\n+size_t get_pack_redundancy(struct pack_list *pl)\n+{\n+\tstruct pack_list *subset;\n+\tsize_t ret = 0;\n+\twhile ((subset = pl->next)) {\n+\t\twhile(subset) {\n+\t\t\tret += sizeof_union(pl->pack, subset->pack);\n+\t\t\tsubset = subset->next;\n+\t\t}\n+\t\tpl = pl->next;\n+\t}\n+\treturn ret;\n+}\n+\n+inline size_t pack_set_bytecount(struct pack_list *pl)\n+{\n+\tsize_t ret = 0;\n+\twhile (pl) {\n+\t\tret += pl->pack->pack_size;\n+\t\tret += pl->pack->index_size;\n+\t\tpl = pl->next;\n+\t}\n+\treturn ret;\n+}\n+\n+void minimize(struct pack_list **min)\n+{\n+\tstruct pack_list *pl, *unique = NULL,\n+\t\t*non_unique = NULL, *min_perm = NULL;\n+\tstruct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;\n+\tstruct llist *missing, *old;\n+\tsize_t min_perm_size = (size_t)-1, perm_size;\n+\n+\tpl = pack_list;\n+\twhile (pl) {\n+\t\tif(pl->unique_objects->size)\n+\t\t\tpack_list_insert(&unique, pl);\n+\t\telse\n+\t\t\tpack_list_insert(&non_unique, pl);\n+\t\tpl = pl->next;\n+\t}\n+\t/* find out which objects are missing from the set of unique packs */\n+\tmissing = llist_copy(all_objects);\n+\tpl = unique;\n+\twhile (pl) {\n+\t\told = missing;\n+\t\tmissing = llist_sorted_difference(missing->front,\n+\t\t\t\t\t\t  pl->all_objects->front);\n+\t\tllist_free(old);\n+\t\tpl = pl->next;\n+\t}\n+\n+\tif (missing->size == 0) {\n+\t\t*min = unique;\n+\t\treturn;\n+\t}\n+\n+\t/* find the permutations which contain all missing objects */\n+\tperm_all = perm = get_all_permutations(non_unique);\n+\twhile (perm) {\n+\t\tif (is_superset(perm->pl, missing)) {\n+\t\t\tnew_perm = xmalloc(sizeof(struct pll));\n+\t\t\tnew_perm->pl = perm->pl;\n+\t\t\tnew_perm->next = perm_ok;\n+\t\t\tperm_ok = new_perm;\n+\t\t}\n+\t\tperm = perm->next;\n+\t}\n+\t\n+\tif (perm_ok == NULL)\n+\t\tdie(\"Internal error: No complete sets found!\\n\");\n+\n+\t/* find the permutation with the smallest size */\n+\tperm = perm_ok;\n+\twhile (perm) {\n+\t\tperm_size = pack_set_bytecount(perm->pl);\n+\t\tif (min_perm_size > perm_size) {\n+\t\t\tmin_perm_size = perm_size;\n+\t\t\tmin_perm = perm->pl;\n+\t\t}\n+\t\tperm = perm->next;\n+\t}\n+\t*min = min_perm;\n+\t/* add the unique packs to the list */\n+\tpl = unique;\n+\twhile(pl) {\n+\t\tpack_list_insert(min, pl);\n+\t\tpl = pl->next;\n+\t}\n+}\n+\n+void load_all_objects()\n+{\n+\tstruct pack_list *pl = pack_list;\n+\tstruct llist_item *hint, *l;\n+\tint i;\n+\n+\tllist_init(&all_objects);\n+\n+\twhile (pl) {\n+\t\ti = 0;\n+\t\thint = NULL;\n+\t\tl = pl->all_objects->front;\n+\t\twhile (l) {\n+\t\t\thint = llist_insert_sorted_unique(all_objects,\n+\t\t\t\t\t\t\t  l->sha1, hint);\n+\t\t\tl = l->next;\n+\t\t}\n+\t\tpl = pl->next;\n+\t}\n+}\n+\n+/* this scales like O(n^2) */\n+void cmp_packs()\n+{\n+\tstruct pack_list *subset, *curr = pack_list;\n+\n+\twhile ((subset = curr)) {\n+\t\twhile((subset = subset->next))\n+\t\t\tcmp_two_packs(curr, subset);\n+\t\tcurr = curr->next;\n+\t}\n+}\n+\n+struct pack_list * add_pack(struct packed_git *p)\n+{\n+\tstruct pack_list l;\n+\tsize_t off;\n+\tvoid *base;\n+\n+\tl.pack = p;\n+\tllist_init(&l.all_objects);\n+\n+\toff = 256 * 4 + 4;\n+\tbase = (void *)p->index_base;\n+\twhile (off <= p->index_size - 3 * 20) {\n+\t\tllist_insert_back(l.all_objects, base + off);\n+\t\toff+=24;\n+\t}\n+\t/* this list will be pruned in cmp_two_packs later */\n+\tl.unique_objects = llist_copy(l.all_objects);\n+\treturn pack_list_insert(&pack_list, &l);\n+}\n+\n+struct pack_list * add_pack_file(char *filename)\n+{\n+\tstruct packed_git *p = packed_git;\n+\n+\tif (strlen(filename) < 40)\n+\t\tdie(\"Bad pack filename: %s\\n\", filename);\n+\n+\twhile (p) {\n+\t\tif (strstr(p->pack_name, filename))\n+\t\t\t/* this will silently ignore packs in alt-odb */\n+\t\t\treturn add_pack(p);\n+\t\tp = p->next;\n+\t}\n+\tdie(\"Filename %s not found in packed_git\\n\", filename);\n+}\n+\n+void load_all()\n+{\n+\tstruct packed_git *p = packed_git;\n+\n+\twhile (p) {\n+\t\tif (p->pack_local) /* ignore alt-odb for now */\n+\t\t\tadd_pack(p);\n+\t\tp = p->next;\n+\t}\n+}\n+\n+int main(int argc, char **argv)\n+{\n+\tint i;\n+\tstruct pack_list *min, *red, *pl;\n+\n+\tfor (i = 1; i < argc; i++) {\n+\t\tconst char *arg = argv[i];\n+\t\tif(!strcmp(arg, \"--\"))\n+\t\t\tbreak;\n+\t\tif(!strcmp(arg, \"-a\")) {\n+\t\t\tall = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif(!strcmp(arg, \"-v\")) {\n+\t\t\tverbose = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif(*arg == '-')\n+\t\t\tusage(pack_intersect_usage);\n+\t\telse\n+\t\t\tbreak;\n+\t}\n+\n+\tprepare_packed_git();\n+\n+\tif(all)\n+\t\tload_all();\n+\telse\n+\t\twhile (*(argv + i) != NULL)\n+\t\t\tadd_pack_file(*(argv + i++));\n+\n+\tif (pack_list == NULL)\n+\t\tdie(\"Zero packs found!\\n\");\n+\n+\tcmp_packs();\n+\n+\tload_all_objects();\n+\n+\tminimize(&min);\n+\tif (verbose) {\n+\t\tfprintf(stderr, \"The smallest (bytewise) set of packs is:\\n\");\n+\t\tpl = min;\n+\t\twhile (pl) {\n+\t\t\tfprintf(stderr, \"\\t%s\\n\", pl->pack->pack_name);\n+\t\t\tpl = pl->next;\n+\t\t}\n+\t\tfprintf(stderr, \"containing %ld duplicate objects \"\n+\t\t\t\t\"with a total size of %ldkb.\\n\",\n+\t\t\tget_pack_redundancy(min), pack_set_bytecount(min)/1024);\n+\t\tfprintf(stderr, \"Redundant packs (with indexes):\\n\");\n+\t}\n+\tpl = red = pack_list_difference(pack_list, min);\n+\twhile (pl) {\n+\t\tprintf(\"%s\\n%s\\n\",\n+\t\t       sha1_pack_index_name(pl->pack->sha1), pl->pack->pack_name);\n+\t\tpl = pl->next;\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 946a353..cd814d7 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -424,6 +424,7 @@ struct packed_git *add_packed_git(char *\n \tstruct packed_git *p;\n \tunsigned long idx_size;\n \tvoid *idx_map;\n+\tchar sha1[20];\n \n \tif (check_packed_git_idx(path, &idx_size, &idx_map))\n \t\treturn NULL;\n@@ -447,6 +448,8 @@ struct packed_git *add_packed_git(char *\n \tp->pack_last_used = 0;\n \tp->pack_use_cnt = 0;\n \tp->pack_local = local;\n+\tif (!get_sha1_hex(path + path_len - 40 - 4, sha1))\n+\t\tmemcpy(p->sha1, sha1, 20);\n \treturn p;\n }\n \n---\n0.99.9.GIT\n"},{"id":"11371","messageId":"43714FAB.2050501@etek.chalmers.se","threadId":"2409","inReplyTo":"43714EFB.5070705@etek.chalmers.se","subject":"[PATCH 2/4] Add documentation for git-pack-intersect","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-09T01:23:55Z","receivedAt":"2005-11-09T01:23:55Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Add documentation for git-pack-intersect\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\n\n Documentation/git-pack-intersect.txt |   47 ++++++++++++++++++++++++++++++++++\n 1 files changed, 47 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/git-pack-intersect.txt\n\napplies-to: 2746df1385345537edc41746b191c67ee98eea20\na1b6ab6c15c3b782478a524a7fd7791ba92960e6\ndiff --git a/Documentation/git-pack-intersect.txt b/Documentation/git-pack-intersect.txt\nnew file mode 100644\nindex 0000000..a73d9e3\n--- /dev/null\n+++ b/Documentation/git-pack-intersect.txt\n@@ -0,0 +1,47 @@\n+git-pack-intersect(1)\n+=====================\n+\n+NAME\n+----\n+git-pack-intersect - Program used to find redundant pack files.\n+\n+\n+SYNOPSIS\n+--------\n+'git-pack-intersect [ -v ] < -a | .pack filename ... >'\n+\n+DESCRIPTION\n+-----------\n+This program computes which packs in your repository\n+are redundant. The output is suitable for piping to\n+'xargs rm' if you are in the root of the repository.\n+\n+OPTIONS\n+-------\n+\n+-v::\n+\tVerbose. Outputs some statistics to stderr.\n+\tHas a small performance penalty.\n+\n+-a::\n+\tAll. Processes all the local packs. Any filenames on\n+\tthe commandline are ignored.\n+\n+Author\n+------\n+Written by Lukas Sandström <lukass@etek.chalmers.se>\n+\n+Documentation\n+--------------\n+Documentation by Lukas Sandström <lukass@etek.chalmers.se>\n+\n+See-Also\n+--------\n+gitlink:git-pack-objects[1]\n+gitlink:git-repack[1]\n+gitlink:git-prune-packed[1]\n+\n+GIT\n+---\n+Part of the gitlink:git[7] suite\n+\n---\n0.99.9.GIT\n"},{"id":"11372","messageId":"43714FE3.8020101@etek.chalmers.se","threadId":"2409","inReplyTo":"43714EFB.5070705@etek.chalmers.se","subject":"[PATCH 3/4] Add git-pack-intersect to .gitignore","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-09T01:24:51Z","receivedAt":"2005-11-09T01:24:51Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Add git-pack-intersect to .gitignore\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\n\n .gitignore |    1 +\n 1 files changed, 1 insertions(+), 0 deletions(-)\n\napplies-to: f4f7accfd9ee93f528c85bae514334fbc7a70be7\n7b8da40e79aa09b43ba4590c6bf8169ed85e4871\ndiff --git a/.gitignore b/.gitignore\nindex 716c340..6ff2530 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -60,6 +60,7 @@ git-mktag\n git-name-rev\n git-mv\n git-octopus\n+git-pack-intersect\n git-pack-objects\n git-parse-remote\n git-patch-id\n---\n0.99.9.GIT\n"},{"id":"11373","messageId":"4371501C.6000204@etek.chalmers.se","threadId":"2409","inReplyTo":"43714EFB.5070705@etek.chalmers.se","subject":"[PATCH 4/4] Make git-repack use git-pack-intersect","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-09T01:25:48Z","receivedAt":"2005-11-09T01:25:48Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Make git-repack use git-pack-intersect.\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\n\n git-repack.sh |   30 ++++++++++++------------------\n 1 files changed, 12 insertions(+), 18 deletions(-)\n\napplies-to: 73e05dab832dd7320a5128fbf97e693f23ffb949\n2cbd6ade19a768eca47f6f7313f6831226ee58b7\ndiff --git a/git-repack.sh b/git-repack.sh\nindex d341966..3f28300 100755\n--- a/git-repack.sh\n+++ b/git-repack.sh\n@@ -32,10 +32,6 @@ case \",$all_into_one,\" in\n \trev_list=\n \trev_parse='--all'\n \tpack_objects=\n-\t# This part is a stop-gap until we have proper pack redundancy\n-\t# checker.\n-\texisting=`cd \"$PACKDIR\" && \\\n-\t    find . -type f \\( -name '*.pack' -o -name '*.idx' \\) -print`\n \t;;\n esac\n if [ \"$local\" ]; then\n@@ -46,6 +42,14 @@ name=$(git-rev-list --objects $rev_list \n \texit 1\n if [ -z \"$name\" ]; then\n \techo Nothing new to pack.\n+\tif test \"$remove_redandant\" = t ; then\n+\t\techo \"Removing redundant packs.\"\n+\t\tsync\n+\t\tredundant=$(git-pack-intersect -a)\n+\t\tif test \"$redundant\" != \"\" ; then\n+\t\t\techo $redundant | xargs rm\n+\t\tfi\n+\tfi\n \texit 0\n fi\n echo \"Pack pack-$name created.\"\n@@ -58,20 +62,10 @@ exit\n \n if test \"$remove_redandant\" = t\n then\n-\t# We know $existing are all redandant only when\n-\t# all-into-one is used.\n-\tif test \"$all_into_one\" != '' && test \"$existing\" != ''\n-\tthen\n-\t\tsync\n-\t\t( cd \"$PACKDIR\" &&\n-\t\t  for e in $existing\n-\t\t  do\n-\t\t\tcase \"$e\" in\n-\t\t\t./pack-$name.pack | ./pack-$name.idx) ;;\n-\t\t\t*)\trm -f $e ;;\n-\t\t\tesac\n-\t\t  done\n-\t\t)\n+\tsync\n+\tredundant=$(git-pack-intersect -a)\n+\tif test \"$redundant\" != \"\" ; then\n+\t\techo $redundant | xargs rm\n \tfi\n fi\n \n---\n0.99.9.GIT\n"},{"id":"11385","messageId":"20051109111917.GB30496@pasky.or.cz","threadId":"2409","inReplyTo":"43714EFB.5070705@etek.chalmers.se","subject":"Re: [PATCH 0/4] Add git-pack-intersect","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2005-11-09T11:19:17Z","receivedAt":"2005-11-09T11:19:17Z","isPatch":true,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Dear diary, on Wed, Nov 09, 2005 at 02:20:59AM CET, I got a letter\nwhere Lukas Sandström <lukass@etek.chalmers.se> said that...\n> This patch series adds git-pack-intersect. It finds redundant packs\n> by calculating the union of all objects present in .git/objects/pack\n> and then computing the smallest set of packs which contain all the\n> objects in this union.\n\nSounds nice, except the name - it does something else than what the name\nsays, so perhaps something like 'git-pack-redundant' would be more\nappropriate.\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nVI has two modes: the one in which it beeps and the one in which\nit doesn't.\n"},{"id":"11388","messageId":"4371E472.4030902@op5.se","threadId":"2409","inReplyTo":"20051109111917.GB30496@pasky.or.cz","subject":"Re: [PATCH 0/4] Add git-pack-intersect","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2005-11-09T11:58:42Z","receivedAt":"2005-11-09T11:58:42Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Petr Baudis wrote:\n> Dear diary, on Wed, Nov 09, 2005 at 02:20:59AM CET, I got a letter\n> where Lukas Sandström <lukass@etek.chalmers.se> said that...\n> \n>>This patch series adds git-pack-intersect. It finds redundant packs\n>>by calculating the union of all objects present in .git/objects/pack\n>>and then computing the smallest set of packs which contain all the\n>>objects in this union.\n> \n> \n> Sounds nice, except the name - it does something else than what the name\n> says, so perhaps something like 'git-pack-redundant' would be more\n> appropriate.\n> \n\nIt would be better if it was in git-prune or a default action for \ngit-repack. I can't imagine a scenario where keeping redundant packfiles \nis useful.\n\n-- \nAndreas Ericsson                   andreas.ericsson@op5.se\nOP5 AB                             www.op5.se\nTel: +46 8-230225                  Fax: +46 8-230231\n"},{"id":"11427","messageId":"4372833D.3010706@etek.chalmers.se","threadId":"2409","inReplyTo":"20051109111917.GB30496@pasky.or.cz","subject":"[PATCH] Rename git-pack-intersect to git-pack-redundant","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-09T23:16:13Z","receivedAt":"2005-11-09T23:16:13Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Petr Baudis wrote:\n> Dear diary, on Wed, Nov 09, 2005 at 02:20:59AM CET, I got a letter\n> where Lukas Sandström <lukass@etek.chalmers.se> said that...\n> \n>>This patch series adds git-pack-intersect. It finds redundant packs\n>>by calculating the union of all objects present in .git/objects/pack\n>>and then computing the smallest set of packs which contain all the\n>>objects in this union.\n> \n> \n> Sounds nice, except the name - it does something else than what the name\n> says, so perhaps something like 'git-pack-redundant' would be more\n> appropriate.\n> \n\nYes, it would. git-pack-intersect is a working name from before\nI knew what the program would actually do. In the beginning\nit just computed the intersection of two pack-files...\n\n/Lukas Sandström\n\n-- >8 -- cut here -- >8 --\nSubject: [PATCH] Rename git-pack-intersect to git-pack-redundant\n\nThis patch renames git-pack-intersect to git-pack-redundant\nas suggested by Petr Baudis. The new name reflects what the\nprogram does, rather than how it does it.\n\nAlso fix a small argument parsing bug.\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\n\n .gitignore                           |    2 +-\n Documentation/git-pack-redundant.txt |    6 +++---\n Makefile                             |    2 +-\n git-repack.sh                        |    4 ++--\n pack-redundant.c                     |   10 ++++++----\n 5 files changed, 13 insertions(+), 11 deletions(-)\n rename Documentation/{git-pack-intersect.txt => git-pack-redundant.txt} (86%)\n rename pack-intersect.c => pack-redundant.c (98%)\n\napplies-to: 85a2ca124a0579c98df5e6d9158a7ee358aeefef\n4db829aa0d1811ccf3505aca232045d7970aec5d\ndiff --git a/.gitignore b/.gitignore\nindex 6ff2530..1d1aa57 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -60,7 +60,7 @@ git-mktag\n git-name-rev\n git-mv\n git-octopus\n-git-pack-intersect\n+git-pack-redundant\n git-pack-objects\n git-parse-remote\n git-patch-id\ndiff --git a/Documentation/git-pack-intersect.txt b/Documentation/git-pack-redundant.txt\nsimilarity index 86%\nrename from Documentation/git-pack-intersect.txt\nrename to Documentation/git-pack-redundant.txt\nindex a73d9e3..3829616 100644\n--- a/Documentation/git-pack-intersect.txt\n+++ b/Documentation/git-pack-redundant.txt\n@@ -1,14 +1,14 @@\n-git-pack-intersect(1)\n+git-pack-redundant(1)\n =====================\n \n NAME\n ----\n-git-pack-intersect - Program used to find redundant pack files.\n+git-pack-redundant - Program used to find redundant pack files.\n \n \n SYNOPSIS\n --------\n-'git-pack-intersect [ -v ] < -a | .pack filename ... >'\n+'git-pack-redundant [ -v ] < -a | .pack filename ... >'\n \n DESCRIPTION\n -----------\ndiff --git a/Makefile b/Makefile\nindex 4c646c9..b4dca5f 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -122,7 +122,7 @@ PROGRAMS = \\\n \tgit-unpack-objects$X git-update-index$X git-update-server-info$X \\\n \tgit-upload-pack$X git-verify-pack$X git-write-tree$X \\\n \tgit-update-ref$X git-symbolic-ref$X git-check-ref-format$X \\\n-\tgit-name-rev$X git-pack-intersect$X $(SIMPLE_PROGRAMS)\n+\tgit-name-rev$X git-pack-redundant$X $(SIMPLE_PROGRAMS)\n \n # Backward compatibility -- to be removed after 1.0\n PROGRAMS += git-ssh-pull$X git-ssh-push$X\ndiff --git a/git-repack.sh b/git-repack.sh\nindex 3f28300..4ce0022 100755\n--- a/git-repack.sh\n+++ b/git-repack.sh\n@@ -45,7 +45,7 @@ if [ -z \"$name\" ]; then\n \tif test \"$remove_redandant\" = t ; then\n \t\techo \"Removing redundant packs.\"\n \t\tsync\n-\t\tredundant=$(git-pack-intersect -a)\n+\t\tredundant=$(git-pack-redundant -a)\n \t\tif test \"$redundant\" != \"\" ; then\n \t\t\techo $redundant | xargs rm\n \t\tfi\n@@ -63,7 +63,7 @@ exit\n if test \"$remove_redandant\" = t\n then\n \tsync\n-\tredundant=$(git-pack-intersect -a)\n+\tredundant=$(git-pack-redundant -a)\n \tif test \"$redundant\" != \"\" ; then\n \t\techo $redundant | xargs rm\n \tfi\ndiff --git a/pack-intersect.c b/pack-redundant.c\nsimilarity index 98%\nrename from pack-intersect.c\nrename to pack-redundant.c\nindex 2267478..db3dcde 100644\n--- a/pack-intersect.c\n+++ b/pack-redundant.c\n@@ -8,8 +8,8 @@\n \n #include \"cache.h\"\n \n-static const char pack_intersect_usage[] =\n-\"git-pack-intersect [ -v ]  < -a | <.pack filename> ...>\";\n+static const char pack_redundant_usage[] =\n+\"git-pack-redundant [ -v ]  < -a | <.pack filename> ...>\";\n \n int all = 0, verbose = 0;\n \n@@ -522,8 +522,10 @@ int main(int argc, char **argv)\n \n \tfor (i = 1; i < argc; i++) {\n \t\tconst char *arg = argv[i];\n-\t\tif(!strcmp(arg, \"--\"))\n+\t\tif(!strcmp(arg, \"--\")) {\n+\t\t\ti++;\n \t\t\tbreak;\n+\t\t}\n \t\tif(!strcmp(arg, \"-a\")) {\n \t\t\tall = 1;\n \t\t\tcontinue;\n@@ -533,7 +535,7 @@ int main(int argc, char **argv)\n \t\t\tcontinue;\n \t\t}\n \t\tif(*arg == '-')\n-\t\t\tusage(pack_intersect_usage);\n+\t\t\tusage(pack_redundant_usage);\n \t\telse\n \t\t\tbreak;\n \t}\n---\n0.99.9.GIT\n"},{"id":"11428","messageId":"43728523.1040209@etek.chalmers.se","threadId":"2409","inReplyTo":"4371E472.4030902@op5.se","subject":"Re: [PATCH 0/4] Add git-pack-intersect","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-09T23:24:19Z","receivedAt":"2005-11-09T23:24:19Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Andreas Ericsson wrote:\n> It would be better if it was in git-prune or a default action for\n> git-repack. I can't imagine a scenario where keeping redundant packfiles\n> is useful.\n> \n\nPerhaps if git-daemon ever does caching of packfiles, removing the smaller\npackfiles might not be optimal.\n\nIntegrating it with git-prune sounds like a good idea though, I'll look \nin to it.\n\n/Lukas \n"},{"id":"11443","messageId":"7vy83x73ze.fsf@assigned-by-dhcp.cox.net","threadId":"2409","inReplyTo":"43728523.1040209@etek.chalmers.se","subject":"Re: [PATCH 0/4] Add git-pack-intersect","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-11-10T00:15:17Z","receivedAt":"2005-11-10T00:15:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lukas Sandström <lukass@etek.chalmers.se> writes:\n\n> Perhaps if git-daemon ever does caching of packfiles, removing the smaller\n> packfiles might not be optimal.\n\nAh, that reminds me of something.\n\nI did not advertise it too much, but you can put a prepackaged\npacks in $GIT_DIR/pack-cache/ and it is used when upload-pack\nnotices it is creating that exact pack.\n\nThis is useless for ordinary repository, but can be useful for\nhistorical repositories whose heads/tags never change (e.g. the\nLinux kernel repository resurrected from bkcvs).  There you\ncould:\n\n\t$ git repack -a -d\n\t$ ln $GIT_DIR/objects/pack/pack-* $GIT_DIR/pack-cache/.\n\nand a clone request would feed the pack, without regenerating\nthe pack data from scratch.  upload-pack still reads, sorts and\ncomputes SHA1 hash of the list of objects to find the pack name,\nbut that is a fairly quick operation, compared to the rest of\nthe pack generation process.\n"}]}