pack-redundant: rename pack_list.all_objects
[gitweb.git] / builtin / pack-objects.c
index f434e1fb0c1ff29e801a2a3b3fc2e67d0f86d217..24bba8147fc96ec2b124aa659c981af08e7a688d 100644 (file)
@@ -24,6 +24,7 @@
 #include "streaming.h"
 #include "thread-utils.h"
 #include "pack-bitmap.h"
+#include "delta-islands.h"
 #include "reachable.h"
 #include "sha1-array.h"
 #include "argv-array.h"
@@ -62,6 +63,7 @@ static struct packing_data to_pack;
 static struct pack_idx_entry **written_list;
 static uint32_t nr_result, nr_written, nr_seen;
 static struct bitmap_index *bitmap_git;
+static uint32_t write_layer;
 
 static int non_empty;
 static int reuse_delta = 1, reuse_object = 1;
@@ -97,6 +99,8 @@ static uint16_t write_bitmap_options;
 
 static int exclude_promisor_objects;
 
+static int use_delta_islands;
+
 static unsigned long delta_cache_size = 0;
 static unsigned long max_delta_cache_size = DEFAULT_DELTA_CACHE_SIZE;
 static unsigned long cache_max_small_delta_size = 1000;
@@ -616,7 +620,7 @@ static inline void add_to_write_order(struct object_entry **wo,
                               unsigned int *endp,
                               struct object_entry *e)
 {
-       if (e->filled)
+       if (e->filled || oe_layer(&to_pack, e) != write_layer)
                return;
        wo[(*endp)++] = e;
        e->filled = 1;
@@ -676,48 +680,15 @@ static void add_family_to_write_order(struct object_entry **wo,
        add_descendants_to_write_order(wo, endp, root);
 }
 
-static struct object_entry **compute_write_order(void)
+static void compute_layer_order(struct object_entry **wo, unsigned int *wo_end)
 {
-       unsigned int i, wo_end, last_untagged;
-
-       struct object_entry **wo;
+       unsigned int i, last_untagged;
        struct object_entry *objects = to_pack.objects;
 
        for (i = 0; i < to_pack.nr_objects; i++) {
-               objects[i].tagged = 0;
-               objects[i].filled = 0;
-               SET_DELTA_CHILD(&objects[i], NULL);
-               SET_DELTA_SIBLING(&objects[i], NULL);
-       }
-
-       /*
-        * Fully connect delta_child/delta_sibling network.
-        * Make sure delta_sibling is sorted in the original
-        * recency order.
-        */
-       for (i = to_pack.nr_objects; i > 0;) {
-               struct object_entry *e = &objects[--i];
-               if (!DELTA(e))
-                       continue;
-               /* Mark me as the first child */
-               e->delta_sibling_idx = DELTA(e)->delta_child_idx;
-               SET_DELTA_CHILD(DELTA(e), e);
-       }
-
-       /*
-        * Mark objects that are at the tip of tags.
-        */
-       for_each_tag_ref(mark_tagged, NULL);
-
-       /*
-        * Give the objects in the original recency order until
-        * we see a tagged tip.
-        */
-       ALLOC_ARRAY(wo, to_pack.nr_objects);
-       for (i = wo_end = 0; i < to_pack.nr_objects; i++) {
                if (objects[i].tagged)
                        break;
-               add_to_write_order(wo, &wo_end, &objects[i]);
+               add_to_write_order(wo, wo_end, &objects[i]);
        }
        last_untagged = i;
 
@@ -726,7 +697,7 @@ static struct object_entry **compute_write_order(void)
         */
        for (; i < to_pack.nr_objects; i++) {
                if (objects[i].tagged)
-                       add_to_write_order(wo, &wo_end, &objects[i]);
+                       add_to_write_order(wo, wo_end, &objects[i]);
        }
 
        /*
@@ -736,7 +707,7 @@ static struct object_entry **compute_write_order(void)
                if (oe_type(&objects[i]) != OBJ_COMMIT &&
                    oe_type(&objects[i]) != OBJ_TAG)
                        continue;
-               add_to_write_order(wo, &wo_end, &objects[i]);
+               add_to_write_order(wo, wo_end, &objects[i]);
        }
 
        /*
@@ -745,16 +716,60 @@ static struct object_entry **compute_write_order(void)
        for (i = last_untagged; i < to_pack.nr_objects; i++) {
                if (oe_type(&objects[i]) != OBJ_TREE)
                        continue;
-               add_to_write_order(wo, &wo_end, &objects[i]);
+               add_to_write_order(wo, wo_end, &objects[i]);
        }
 
        /*
         * Finally all the rest in really tight order
         */
        for (i = last_untagged; i < to_pack.nr_objects; i++) {
-               if (!objects[i].filled)
-                       add_family_to_write_order(wo, &wo_end, &objects[i]);
+               if (!objects[i].filled && oe_layer(&to_pack, &objects[i]) == write_layer)
+                       add_family_to_write_order(wo, wo_end, &objects[i]);
        }
+}
+
+static struct object_entry **compute_write_order(void)
+{
+       uint32_t max_layers = 1;
+       unsigned int i, wo_end;
+
+       struct object_entry **wo;
+       struct object_entry *objects = to_pack.objects;
+
+       for (i = 0; i < to_pack.nr_objects; i++) {
+               objects[i].tagged = 0;
+               objects[i].filled = 0;
+               SET_DELTA_CHILD(&objects[i], NULL);
+               SET_DELTA_SIBLING(&objects[i], NULL);
+       }
+
+       /*
+        * Fully connect delta_child/delta_sibling network.
+        * Make sure delta_sibling is sorted in the original
+        * recency order.
+        */
+       for (i = to_pack.nr_objects; i > 0;) {
+               struct object_entry *e = &objects[--i];
+               if (!DELTA(e))
+                       continue;
+               /* Mark me as the first child */
+               e->delta_sibling_idx = DELTA(e)->delta_child_idx;
+               SET_DELTA_CHILD(DELTA(e), e);
+       }
+
+       /*
+        * Mark objects that are at the tip of tags.
+        */
+       for_each_tag_ref(mark_tagged, NULL);
+
+       if (use_delta_islands)
+               max_layers = compute_pack_layers(&to_pack);
+
+       ALLOC_ARRAY(wo, to_pack.nr_objects);
+       wo_end = 0;
+
+       for (; write_layer < max_layers; ++write_layer)
+               compute_layer_order(wo, &wo_end);
 
        if (wo_end != to_pack.nr_objects)
                die(_("ordered %u objects, expected %"PRIu32),
@@ -955,8 +970,7 @@ static int no_try_delta(const char *path)
 
        if (!check)
                check = attr_check_initl("delta", NULL);
-       if (git_check_attr(&the_index, path, check))
-               return 0;
+       git_check_attr(&the_index, path, check);
        if (ATTR_FALSE(check->items[0].value))
                return 1;
        return 0;
@@ -1233,7 +1247,7 @@ static struct pbase_tree_cache *pbase_tree_get(const struct object_id *oid)
         */
        for (neigh = 0; neigh < 8; neigh++) {
                ent = pbase_tree_cache[my_ix];
-               if (ent && !oidcmp(&ent->oid, oid)) {
+               if (ent && oideq(&ent->oid, oid)) {
                        ent->ref++;
                        return ent;
                }
@@ -1415,7 +1429,7 @@ static void add_preferred_base(struct object_id *oid)
                return;
 
        for (it = pbase_tree; it; it = it->next) {
-               if (!oidcmp(&it->pcache.oid, &tree_oid)) {
+               if (oideq(&it->pcache.oid, &tree_oid)) {
                        free(data);
                        return;
                }
@@ -1455,6 +1469,57 @@ static void cleanup_preferred_base(void)
        done_pbase_paths_num = done_pbase_paths_alloc = 0;
 }
 
+/*
+ * Return 1 iff the object specified by "delta" can be sent
+ * literally as a delta against the base in "base_sha1". If
+ * so, then *base_out will point to the entry in our packing
+ * list, or NULL if we must use the external-base list.
+ *
+ * Depth value does not matter - find_deltas() will
+ * never consider reused delta as the base object to
+ * deltify other objects against, in order to avoid
+ * circular deltas.
+ */
+static int can_reuse_delta(const unsigned char *base_sha1,
+                          struct object_entry *delta,
+                          struct object_entry **base_out)
+{
+       struct object_entry *base;
+
+       if (!base_sha1)
+               return 0;
+
+       /*
+        * First see if we're already sending the base (or it's explicitly in
+        * our "excluded" list).
+        */
+       base = packlist_find(&to_pack, base_sha1, NULL);
+       if (base) {
+               if (!in_same_island(&delta->idx.oid, &base->idx.oid))
+                       return 0;
+               *base_out = base;
+               return 1;
+       }
+
+       /*
+        * Otherwise, reachability bitmaps may tell us if the receiver has it,
+        * even if it was buried too deep in history to make it into the
+        * packing list.
+        */
+       if (thin && bitmap_has_sha1_in_uninteresting(bitmap_git, base_sha1)) {
+               if (use_delta_islands) {
+                       struct object_id base_oid;
+                       hashcpy(base_oid.hash, base_sha1);
+                       if (!in_same_island(&delta->idx.oid, &base_oid))
+                               return 0;
+               }
+               *base_out = NULL;
+               return 1;
+       }
+
+       return 0;
+}
+
 static void check_object(struct object_entry *entry)
 {
        unsigned long canonical_size;
@@ -1541,21 +1606,7 @@ static void check_object(struct object_entry *entry)
                        break;
                }
 
-               if (base_ref && (
-                   (base_entry = packlist_find(&to_pack, base_ref, NULL)) ||
-                   (thin &&
-                    bitmap_has_sha1_in_uninteresting(bitmap_git, base_ref)))) {
-                       /*
-                        * If base_ref was set above that means we wish to
-                        * reuse delta data, and either we found that object in
-                        * the list of objects we want to pack, or it's one we
-                        * know the receiver has.
-                        *
-                        * Depth value does not matter - find_deltas() will
-                        * never consider reused delta as the base object to
-                        * deltify other objects against, in order to avoid
-                        * circular deltas.
-                        */
+               if (can_reuse_delta(base_ref, entry, &base_entry)) {
                        oe_set_type(entry, entry->in_pack_type);
                        SET_SIZE(entry, in_pack_size); /* delta size */
                        SET_DELTA_SIZE(entry, in_pack_size);
@@ -1867,6 +1918,11 @@ static int type_size_sort(const void *_a, const void *_b)
                return -1;
        if (a->preferred_base < b->preferred_base)
                return 1;
+       if (use_delta_islands) {
+               int island_cmp = island_delta_cmp(&a->idx.oid, &b->idx.oid);
+               if (island_cmp)
+                       return island_cmp;
+       }
        if (a_size > b_size)
                return -1;
        if (a_size < b_size)
@@ -1897,8 +1953,6 @@ static int delta_cacheable(unsigned long src_size, unsigned long trg_size,
        return 0;
 }
 
-#ifndef NO_PTHREADS
-
 /* Protect access to object database */
 static pthread_mutex_t read_mutex;
 #define read_lock()            pthread_mutex_lock(&read_mutex)
@@ -1923,16 +1977,6 @@ static pthread_mutex_t progress_mutex;
  * ahead in the list because they can be stolen and would need
  * progress_mutex for protection.
  */
-#else
-
-#define read_lock()            (void)0
-#define read_unlock()          (void)0
-#define cache_lock()           (void)0
-#define cache_unlock()         (void)0
-#define progress_lock()                (void)0
-#define progress_unlock()      (void)0
-
-#endif
 
 /*
  * Return the size of the object without doing any delta
@@ -2027,6 +2071,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
        if (trg_size < src_size / 32)
                return 0;
 
+       if (!in_same_island(&trg->entry->idx.oid, &src->entry->idx.oid))
+               return 0;
+
        /* Load data if not already done */
        if (!trg->data) {
                read_lock();
@@ -2036,9 +2083,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
                        die(_("object %s cannot be read"),
                            oid_to_hex(&trg_entry->idx.oid));
                if (sz != trg_size)
-                       die(_("object %s inconsistent object length (%lu vs %lu)"),
-                           oid_to_hex(&trg_entry->idx.oid), sz,
-                           trg_size);
+                       die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
+                           oid_to_hex(&trg_entry->idx.oid), (uintmax_t)sz,
+                           (uintmax_t)trg_size);
                *mem_usage += sz;
        }
        if (!src->data) {
@@ -2063,9 +2110,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,
                            oid_to_hex(&src_entry->idx.oid));
                }
                if (sz != src_size)
-                       die(_("object %s inconsistent object length (%lu vs %lu)"),
-                           oid_to_hex(&src_entry->idx.oid), sz,
-                           src_size);
+                       die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
+                           oid_to_hex(&src_entry->idx.oid), (uintmax_t)sz,
+                           (uintmax_t)src_size);
                *mem_usage += sz;
        }
        if (!src->index) {
@@ -2288,8 +2335,6 @@ static void find_deltas(struct object_entry **list, unsigned *list_size,
        free(array);
 }
 
-#ifndef NO_PTHREADS
-
 static void try_to_free_from_threads(size_t size)
 {
        read_lock();
@@ -2340,7 +2385,6 @@ static void init_threaded_search(void)
        pthread_mutex_init(&cache_mutex, NULL);
        pthread_mutex_init(&progress_mutex, NULL);
        pthread_cond_init(&progress_cond, NULL);
-       pthread_mutex_init(&to_pack.lock, NULL);
        old_try_to_free_routine = set_try_to_free_routine(try_to_free_from_threads);
 }
 
@@ -2519,10 +2563,6 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,
        free(p);
 }
 
-#else
-#define ll_find_deltas(l, s, w, d, p)  find_deltas(l, &s, w, d, p)
-#endif
-
 static void add_tag_chain(const struct object_id *oid)
 {
        struct tag *tag;
@@ -2569,6 +2609,9 @@ static void prepare_pack(int window, int depth)
        uint32_t i, nr_deltas;
        unsigned n;
 
+       if (use_delta_islands)
+               resolve_tree_islands(the_repository, progress, &to_pack);
+
        get_object_details();
 
        /*
@@ -2672,12 +2715,10 @@ static int git_pack_config(const char *k, const char *v, void *cb)
                if (delta_search_threads < 0)
                        die(_("invalid number of threads specified (%d)"),
                            delta_search_threads);
-#ifdef NO_PTHREADS
-               if (delta_search_threads != 1) {
+               if (!HAVE_THREADS && delta_search_threads != 1) {
                        warning(_("no threads support, ignoring %s"), k);
                        delta_search_threads = 0;
                }
-#endif
                return 0;
        }
        if (!strcmp(k, "pack.indexversion")) {
@@ -2732,6 +2773,9 @@ static void show_commit(struct commit *commit, void *data)
 
        if (write_bitmap_index)
                index_commit_for_bitmap(commit);
+
+       if (use_delta_islands)
+               propagate_island_marks(commit);
 }
 
 static void show_object(struct object *obj, const char *name, void *data)
@@ -2739,6 +2783,21 @@ static void show_object(struct object *obj, const char *name, void *data)
        add_preferred_base_object(name);
        add_object_entry(&obj->oid, obj->type, name, 0);
        obj->flags |= OBJECT_ADDED;
+
+       if (use_delta_islands) {
+               const char *p;
+               unsigned depth;
+               struct object_entry *ent;
+
+               /* the empty string is a root tree, which is depth 0 */
+               depth = *name ? 1 : 0;
+               for (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))
+                       depth++;
+
+               ent = packlist_find(&to_pack, obj->oid.hash, NULL);
+               if (ent && depth > oe_tree_depth(&to_pack, ent))
+                       oe_set_tree_depth(&to_pack, ent, depth);
+       }
 }
 
 static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)
@@ -3027,14 +3086,19 @@ static void get_object_list(int ac, const char **av)
        struct rev_info revs;
        char line[1000];
        int flags = 0;
+       int save_warning;
 
-       init_revisions(&revs, NULL);
+       repo_init_revisions(the_repository, &revs, NULL);
        save_commit_buffer = 0;
+       revs.allow_exclude_promisor_objects_opt = 1;
        setup_revisions(ac, av, &revs, NULL);
 
        /* make sure shallows are read */
        is_repository_shallow(the_repository);
 
+       save_warning = warn_on_object_refname_ambiguity;
+       warn_on_object_refname_ambiguity = 0;
+
        while (fgets(line, sizeof(line), stdin) != NULL) {
                int len = strlen(line);
                if (len && line[len - 1] == '\n')
@@ -3061,9 +3125,14 @@ static void get_object_list(int ac, const char **av)
                        die(_("bad revision '%s'"), line);
        }
 
+       warn_on_object_refname_ambiguity = save_warning;
+
        if (use_bitmap_index && !get_object_list_from_bitmap(&revs))
                return;
 
+       if (use_delta_islands)
+               load_delta_islands(the_repository);
+
        if (prepare_revision_walk(&revs))
                die(_("revision walk setup failed"));
        mark_edges_uninteresting(&revs, show_edge);
@@ -3126,6 +3195,9 @@ static int option_parse_index_version(const struct option *opt,
 {
        char *c;
        const char *val = arg;
+
+       BUG_ON_OPT_NEG(unset);
+
        pack_idx_opts.version = strtoul(val, &c, 10);
        if (pack_idx_opts.version > 2)
                die(_("unsupported index version %s"), val);
@@ -3172,7 +3244,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
                         N_("similar to --all-progress when progress meter is shown")),
                { OPTION_CALLBACK, 0, "index-version", NULL, N_("<version>[,<offset>]"),
                  N_("write the pack index file in the specified idx format version"),
-                 0, option_parse_index_version },
+                 PARSE_OPT_NONEG, option_parse_index_version },
                OPT_MAGNITUDE(0, "max-pack-size", &pack_size_limit,
                              N_("maximum size of each output pack file")),
                OPT_BOOL(0, "local", &local,
@@ -3242,6 +3314,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
                  option_parse_missing_action },
                OPT_BOOL(0, "exclude-promisor-objects", &exclude_promisor_objects,
                         N_("do not pack objects in promisor packfiles")),
+               OPT_BOOL(0, "delta-islands", &use_delta_islands,
+                        N_("respect islands during delta compression")),
                OPT_END(),
        };
 
@@ -3319,10 +3393,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
        if (!delta_search_threads)      /* --threads=0 means autodetect */
                delta_search_threads = online_cpus();
 
-#ifdef NO_PTHREADS
-       if (delta_search_threads != 1)
+       if (!HAVE_THREADS && delta_search_threads != 1)
                warning(_("no threads support, ignoring --threads"));
-#endif
        if (!pack_to_stdout && !pack_size_limit)
                pack_size_limit = pack_size_limit_cfg;
        if (pack_to_stdout && pack_size_limit)
@@ -3368,6 +3440,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
        if (pack_to_stdout || !rev_list_all)
                write_bitmap_index = 0;
 
+       if (use_delta_islands)
+               argv_array_push(&rp, "--topo-order");
+
        if (progress && all_progress_implied)
                progress = 2;
 
@@ -3395,7 +3470,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
                }
        }
 
-       prepare_packing_data(&to_pack);
+       prepare_packing_data(the_repository, &to_pack);
 
        if (progress)
                progress_state = start_progress(_("Enumerating objects"), 0);