[PATCH v5 0/5] pack-redundant: new algorithm to find min packs

[Jiang Xin <worldhello.net@gmail.com>]

> Sun Chao (my former colleague at Huawei) found a bug of
> git-pack-redundant.  If there are too many packs and many of them
> overlap
> each other, running `git pack-redundant --all` will exhaust all memories
> and the process will be killed by kernel.
> 
> There is a script in commit log of commit 2/3, which can be used to
> create a repository with lots of redundant packs. Running `git
> pack-redundant --all` in it can reproduce this issue.

SZEDER reported that t5233 won't pass for MacOS. See solution in patch
4/5.

Changes since reroll v4:

* Rewrite t5323, add more test cases.
* Add two new patches, one for refactor, and another changed sorting
  method and fixed t5323 for the new algorithm.

Range diff with sc/pack-redundant feature branch:

    1:  702267a888 < -:  ---------- t5323: test cases for git-pack-redundant
    -:  ---------- > 1:  40fea5d67f t5323: test cases for git-pack-redundant
    2:  c4b133d858 = 2:  50cd5a5b47 pack-redundant: new algorithm to find min packs
    -:  ---------- > 3:  6338c6fad4 pack-redundant: rename pack_list.all_objects
    -:  ---------- > 4:  734f4d8a8b pack-redundant: consistent sort method
    3:  2351d7e8b5 ! 5:  b7ccdea1ad pack-redundant: remove unused functions
        @@ -13,7 +13,7 @@
          --- a/builtin/pack-redundant.c
          +++ b/builtin/pack-redundant.c
         @@
        - 	struct llist *all_objects;
        + 	size_t all_objects_size;
          } *local_packs = NULL, *altodb_packs = NULL;
          
         -struct pll {
        @@ -105,7 +105,7 @@
         -	diff = llist_copy(list);
         -
         -	while (pl) {
        --		llist_sorted_difference_inplace(diff, pl->all_objects);
        +-		llist_sorted_difference_inplace(diff, pl->remaining_objects);
         -		if (diff->size == 0) { /* we're done */
         -			llist_free(diff);
         -			return 1;


Jiang Xin (3):
  t5323: test cases for git-pack-redundant
  pack-redundant: rename pack_list.all_objects
  pack-redundant: consistent sort method

Sun Chao (2):
  pack-redundant: new algorithm to find min packs
  pack-redundant: remove unused functions

 builtin/pack-redundant.c  | 221 +++++++++++++++-----------------------
 t/t5323-pack-redundant.sh | 157 +++++++++++++++++++++++++++
 2 files changed, 242 insertions(+), 136 deletions(-)
 create mode 100755 t/t5323-pack-redundant.sh


-- 
2.20.1.101.gc01fadde4e