Merge branch 'js/anonymise-push-url-in-errors'
[git] / pack-bitmap.c
1 #include "cache.h"
2 #include "commit.h"
3 #include "tag.h"
4 #include "diff.h"
5 #include "revision.h"
6 #include "progress.h"
7 #include "list-objects.h"
8 #include "pack.h"
9 #include "pack-bitmap.h"
10 #include "pack-revindex.h"
11 #include "pack-objects.h"
12 #include "packfile.h"
13 #include "repository.h"
14 #include "object-store.h"
15 #include "list-objects-filter-options.h"
16
17 /*
18  * An entry on the bitmap index, representing the bitmap for a given
19  * commit.
20  */
21 struct stored_bitmap {
22         struct object_id oid;
23         struct ewah_bitmap *root;
24         struct stored_bitmap *xor;
25         int flags;
26 };
27
28 /*
29  * The active bitmap index for a repository. By design, repositories only have
30  * a single bitmap index available (the index for the biggest packfile in
31  * the repository), since bitmap indexes need full closure.
32  *
33  * If there is more than one bitmap index available (e.g. because of alternates),
34  * the active bitmap index is the largest one.
35  */
36 struct bitmap_index {
37         /* Packfile to which this bitmap index belongs to */
38         struct packed_git *pack;
39
40         /*
41          * Mark the first `reuse_objects` in the packfile as reused:
42          * they will be sent as-is without using them for repacking
43          * calculations
44          */
45         uint32_t reuse_objects;
46
47         /* mmapped buffer of the whole bitmap index */
48         unsigned char *map;
49         size_t map_size; /* size of the mmaped buffer */
50         size_t map_pos; /* current position when loading the index */
51
52         /*
53          * Type indexes.
54          *
55          * Each bitmap marks which objects in the packfile  are of the given
56          * type. This provides type information when yielding the objects from
57          * the packfile during a walk, which allows for better delta bases.
58          */
59         struct ewah_bitmap *commits;
60         struct ewah_bitmap *trees;
61         struct ewah_bitmap *blobs;
62         struct ewah_bitmap *tags;
63
64         /* Map from object ID -> `stored_bitmap` for all the bitmapped commits */
65         kh_oid_map_t *bitmaps;
66
67         /* Number of bitmapped commits */
68         uint32_t entry_count;
69
70         /* If not NULL, this is a name-hash cache pointing into map. */
71         uint32_t *hashes;
72
73         /*
74          * Extended index.
75          *
76          * When trying to perform bitmap operations with objects that are not
77          * packed in `pack`, these objects are added to this "fake index" and
78          * are assumed to appear at the end of the packfile for all operations
79          */
80         struct eindex {
81                 struct object **objects;
82                 uint32_t *hashes;
83                 uint32_t count, alloc;
84                 kh_oid_pos_t *positions;
85         } ext_index;
86
87         /* Bitmap result of the last performed walk */
88         struct bitmap *result;
89
90         /* "have" bitmap from the last performed walk */
91         struct bitmap *haves;
92
93         /* Version of the bitmap index */
94         unsigned int version;
95 };
96
97 static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
98 {
99         struct ewah_bitmap *parent;
100         struct ewah_bitmap *composed;
101
102         if (st->xor == NULL)
103                 return st->root;
104
105         composed = ewah_pool_new();
106         parent = lookup_stored_bitmap(st->xor);
107         ewah_xor(st->root, parent, composed);
108
109         ewah_pool_free(st->root);
110         st->root = composed;
111         st->xor = NULL;
112
113         return composed;
114 }
115
116 /*
117  * Read a bitmap from the current read position on the mmaped
118  * index, and increase the read position accordingly
119  */
120 static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)
121 {
122         struct ewah_bitmap *b = ewah_pool_new();
123
124         ssize_t bitmap_size = ewah_read_mmap(b,
125                 index->map + index->map_pos,
126                 index->map_size - index->map_pos);
127
128         if (bitmap_size < 0) {
129                 error("Failed to load bitmap index (corrupted?)");
130                 ewah_pool_free(b);
131                 return NULL;
132         }
133
134         index->map_pos += bitmap_size;
135         return b;
136 }
137
138 static int load_bitmap_header(struct bitmap_index *index)
139 {
140         struct bitmap_disk_header *header = (void *)index->map;
141
142         if (index->map_size < sizeof(*header) + the_hash_algo->rawsz)
143                 return error("Corrupted bitmap index (missing header data)");
144
145         if (memcmp(header->magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE)) != 0)
146                 return error("Corrupted bitmap index file (wrong header)");
147
148         index->version = ntohs(header->version);
149         if (index->version != 1)
150                 return error("Unsupported version for bitmap index file (%d)", index->version);
151
152         /* Parse known bitmap format options */
153         {
154                 uint32_t flags = ntohs(header->options);
155
156                 if ((flags & BITMAP_OPT_FULL_DAG) == 0)
157                         return error("Unsupported options for bitmap index file "
158                                 "(Git requires BITMAP_OPT_FULL_DAG)");
159
160                 if (flags & BITMAP_OPT_HASH_CACHE) {
161                         unsigned char *end = index->map + index->map_size - the_hash_algo->rawsz;
162                         index->hashes = ((uint32_t *)end) - index->pack->num_objects;
163                 }
164         }
165
166         index->entry_count = ntohl(header->entry_count);
167         index->map_pos += sizeof(*header) - GIT_MAX_RAWSZ + the_hash_algo->rawsz;
168         return 0;
169 }
170
171 static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
172                                           struct ewah_bitmap *root,
173                                           const struct object_id *oid,
174                                           struct stored_bitmap *xor_with,
175                                           int flags)
176 {
177         struct stored_bitmap *stored;
178         khiter_t hash_pos;
179         int ret;
180
181         stored = xmalloc(sizeof(struct stored_bitmap));
182         stored->root = root;
183         stored->xor = xor_with;
184         stored->flags = flags;
185         oidcpy(&stored->oid, oid);
186
187         hash_pos = kh_put_oid_map(index->bitmaps, stored->oid, &ret);
188
189         /* a 0 return code means the insertion succeeded with no changes,
190          * because the SHA1 already existed on the map. this is bad, there
191          * shouldn't be duplicated commits in the index */
192         if (ret == 0) {
193                 error("Duplicate entry in bitmap index: %s", oid_to_hex(oid));
194                 return NULL;
195         }
196
197         kh_value(index->bitmaps, hash_pos) = stored;
198         return stored;
199 }
200
201 static inline uint32_t read_be32(const unsigned char *buffer, size_t *pos)
202 {
203         uint32_t result = get_be32(buffer + *pos);
204         (*pos) += sizeof(result);
205         return result;
206 }
207
208 static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)
209 {
210         return buffer[(*pos)++];
211 }
212
213 #define MAX_XOR_OFFSET 160
214
215 static int load_bitmap_entries_v1(struct bitmap_index *index)
216 {
217         uint32_t i;
218         struct stored_bitmap *recent_bitmaps[MAX_XOR_OFFSET] = { NULL };
219
220         for (i = 0; i < index->entry_count; ++i) {
221                 int xor_offset, flags;
222                 struct ewah_bitmap *bitmap = NULL;
223                 struct stored_bitmap *xor_bitmap = NULL;
224                 uint32_t commit_idx_pos;
225                 struct object_id oid;
226
227                 commit_idx_pos = read_be32(index->map, &index->map_pos);
228                 xor_offset = read_u8(index->map, &index->map_pos);
229                 flags = read_u8(index->map, &index->map_pos);
230
231                 nth_packed_object_id(&oid, index->pack, commit_idx_pos);
232
233                 bitmap = read_bitmap_1(index);
234                 if (!bitmap)
235                         return -1;
236
237                 if (xor_offset > MAX_XOR_OFFSET || xor_offset > i)
238                         return error("Corrupted bitmap pack index");
239
240                 if (xor_offset > 0) {
241                         xor_bitmap = recent_bitmaps[(i - xor_offset) % MAX_XOR_OFFSET];
242
243                         if (xor_bitmap == NULL)
244                                 return error("Invalid XOR offset in bitmap pack index");
245                 }
246
247                 recent_bitmaps[i % MAX_XOR_OFFSET] = store_bitmap(
248                         index, bitmap, &oid, xor_bitmap, flags);
249         }
250
251         return 0;
252 }
253
254 static char *pack_bitmap_filename(struct packed_git *p)
255 {
256         size_t len;
257
258         if (!strip_suffix(p->pack_name, ".pack", &len))
259                 BUG("pack_name does not end in .pack");
260         return xstrfmt("%.*s.bitmap", (int)len, p->pack_name);
261 }
262
263 static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git *packfile)
264 {
265         int fd;
266         struct stat st;
267         char *idx_name;
268
269         if (open_pack_index(packfile))
270                 return -1;
271
272         idx_name = pack_bitmap_filename(packfile);
273         fd = git_open(idx_name);
274         free(idx_name);
275
276         if (fd < 0)
277                 return -1;
278
279         if (fstat(fd, &st)) {
280                 close(fd);
281                 return -1;
282         }
283
284         if (bitmap_git->pack) {
285                 warning("ignoring extra bitmap file: %s", packfile->pack_name);
286                 close(fd);
287                 return -1;
288         }
289
290         bitmap_git->pack = packfile;
291         bitmap_git->map_size = xsize_t(st.st_size);
292         bitmap_git->map = xmmap(NULL, bitmap_git->map_size, PROT_READ, MAP_PRIVATE, fd, 0);
293         bitmap_git->map_pos = 0;
294         close(fd);
295
296         if (load_bitmap_header(bitmap_git) < 0) {
297                 munmap(bitmap_git->map, bitmap_git->map_size);
298                 bitmap_git->map = NULL;
299                 bitmap_git->map_size = 0;
300                 return -1;
301         }
302
303         return 0;
304 }
305
306 static int load_pack_bitmap(struct bitmap_index *bitmap_git)
307 {
308         assert(bitmap_git->map);
309
310         bitmap_git->bitmaps = kh_init_oid_map();
311         bitmap_git->ext_index.positions = kh_init_oid_pos();
312         if (load_pack_revindex(bitmap_git->pack))
313                 goto failed;
314
315         if (!(bitmap_git->commits = read_bitmap_1(bitmap_git)) ||
316                 !(bitmap_git->trees = read_bitmap_1(bitmap_git)) ||
317                 !(bitmap_git->blobs = read_bitmap_1(bitmap_git)) ||
318                 !(bitmap_git->tags = read_bitmap_1(bitmap_git)))
319                 goto failed;
320
321         if (load_bitmap_entries_v1(bitmap_git) < 0)
322                 goto failed;
323
324         return 0;
325
326 failed:
327         munmap(bitmap_git->map, bitmap_git->map_size);
328         bitmap_git->map = NULL;
329         bitmap_git->map_size = 0;
330
331         kh_destroy_oid_map(bitmap_git->bitmaps);
332         bitmap_git->bitmaps = NULL;
333
334         kh_destroy_oid_pos(bitmap_git->ext_index.positions);
335         bitmap_git->ext_index.positions = NULL;
336
337         return -1;
338 }
339
340 static int open_pack_bitmap(struct repository *r,
341                             struct bitmap_index *bitmap_git)
342 {
343         struct packed_git *p;
344         int ret = -1;
345
346         assert(!bitmap_git->map);
347
348         for (p = get_all_packs(r); p; p = p->next) {
349                 if (open_pack_bitmap_1(bitmap_git, p) == 0)
350                         ret = 0;
351         }
352
353         return ret;
354 }
355
356 struct bitmap_index *prepare_bitmap_git(struct repository *r)
357 {
358         struct bitmap_index *bitmap_git = xcalloc(1, sizeof(*bitmap_git));
359
360         if (!open_pack_bitmap(r, bitmap_git) && !load_pack_bitmap(bitmap_git))
361                 return bitmap_git;
362
363         free_bitmap_index(bitmap_git);
364         return NULL;
365 }
366
367 struct include_data {
368         struct bitmap_index *bitmap_git;
369         struct bitmap *base;
370         struct bitmap *seen;
371 };
372
373 static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
374                                            const struct object_id *oid)
375 {
376         kh_oid_pos_t *positions = bitmap_git->ext_index.positions;
377         khiter_t pos = kh_get_oid_pos(positions, *oid);
378
379         if (pos < kh_end(positions)) {
380                 int bitmap_pos = kh_value(positions, pos);
381                 return bitmap_pos + bitmap_git->pack->num_objects;
382         }
383
384         return -1;
385 }
386
387 static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
388                                            const struct object_id *oid)
389 {
390         off_t offset = find_pack_entry_one(oid->hash, bitmap_git->pack);
391         if (!offset)
392                 return -1;
393
394         return find_revindex_position(bitmap_git->pack, offset);
395 }
396
397 static int bitmap_position(struct bitmap_index *bitmap_git,
398                            const struct object_id *oid)
399 {
400         int pos = bitmap_position_packfile(bitmap_git, oid);
401         return (pos >= 0) ? pos : bitmap_position_extended(bitmap_git, oid);
402 }
403
404 static int ext_index_add_object(struct bitmap_index *bitmap_git,
405                                 struct object *object, const char *name)
406 {
407         struct eindex *eindex = &bitmap_git->ext_index;
408
409         khiter_t hash_pos;
410         int hash_ret;
411         int bitmap_pos;
412
413         hash_pos = kh_put_oid_pos(eindex->positions, object->oid, &hash_ret);
414         if (hash_ret > 0) {
415                 if (eindex->count >= eindex->alloc) {
416                         eindex->alloc = (eindex->alloc + 16) * 3 / 2;
417                         REALLOC_ARRAY(eindex->objects, eindex->alloc);
418                         REALLOC_ARRAY(eindex->hashes, eindex->alloc);
419                 }
420
421                 bitmap_pos = eindex->count;
422                 eindex->objects[eindex->count] = object;
423                 eindex->hashes[eindex->count] = pack_name_hash(name);
424                 kh_value(eindex->positions, hash_pos) = bitmap_pos;
425                 eindex->count++;
426         } else {
427                 bitmap_pos = kh_value(eindex->positions, hash_pos);
428         }
429
430         return bitmap_pos + bitmap_git->pack->num_objects;
431 }
432
433 struct bitmap_show_data {
434         struct bitmap_index *bitmap_git;
435         struct bitmap *base;
436 };
437
438 static void show_object(struct object *object, const char *name, void *data_)
439 {
440         struct bitmap_show_data *data = data_;
441         int bitmap_pos;
442
443         bitmap_pos = bitmap_position(data->bitmap_git, &object->oid);
444
445         if (bitmap_pos < 0)
446                 bitmap_pos = ext_index_add_object(data->bitmap_git, object,
447                                                   name);
448
449         bitmap_set(data->base, bitmap_pos);
450 }
451
452 static void show_commit(struct commit *commit, void *data)
453 {
454 }
455
456 static int add_to_include_set(struct bitmap_index *bitmap_git,
457                               struct include_data *data,
458                               const struct object_id *oid,
459                               int bitmap_pos)
460 {
461         khiter_t hash_pos;
462
463         if (data->seen && bitmap_get(data->seen, bitmap_pos))
464                 return 0;
465
466         if (bitmap_get(data->base, bitmap_pos))
467                 return 0;
468
469         hash_pos = kh_get_oid_map(bitmap_git->bitmaps, *oid);
470         if (hash_pos < kh_end(bitmap_git->bitmaps)) {
471                 struct stored_bitmap *st = kh_value(bitmap_git->bitmaps, hash_pos);
472                 bitmap_or_ewah(data->base, lookup_stored_bitmap(st));
473                 return 0;
474         }
475
476         bitmap_set(data->base, bitmap_pos);
477         return 1;
478 }
479
480 static int should_include(struct commit *commit, void *_data)
481 {
482         struct include_data *data = _data;
483         int bitmap_pos;
484
485         bitmap_pos = bitmap_position(data->bitmap_git, &commit->object.oid);
486         if (bitmap_pos < 0)
487                 bitmap_pos = ext_index_add_object(data->bitmap_git,
488                                                   (struct object *)commit,
489                                                   NULL);
490
491         if (!add_to_include_set(data->bitmap_git, data, &commit->object.oid,
492                                 bitmap_pos)) {
493                 struct commit_list *parent = commit->parents;
494
495                 while (parent) {
496                         parent->item->object.flags |= SEEN;
497                         parent = parent->next;
498                 }
499
500                 return 0;
501         }
502
503         return 1;
504 }
505
506 static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
507                                    struct rev_info *revs,
508                                    struct object_list *roots,
509                                    struct bitmap *seen)
510 {
511         struct bitmap *base = NULL;
512         int needs_walk = 0;
513
514         struct object_list *not_mapped = NULL;
515
516         /*
517          * Go through all the roots for the walk. The ones that have bitmaps
518          * on the bitmap index will be `or`ed together to form an initial
519          * global reachability analysis.
520          *
521          * The ones without bitmaps in the index will be stored in the
522          * `not_mapped_list` for further processing.
523          */
524         while (roots) {
525                 struct object *object = roots->item;
526                 roots = roots->next;
527
528                 if (object->type == OBJ_COMMIT) {
529                         khiter_t pos = kh_get_oid_map(bitmap_git->bitmaps, object->oid);
530
531                         if (pos < kh_end(bitmap_git->bitmaps)) {
532                                 struct stored_bitmap *st = kh_value(bitmap_git->bitmaps, pos);
533                                 struct ewah_bitmap *or_with = lookup_stored_bitmap(st);
534
535                                 if (base == NULL)
536                                         base = ewah_to_bitmap(or_with);
537                                 else
538                                         bitmap_or_ewah(base, or_with);
539
540                                 object->flags |= SEEN;
541                                 continue;
542                         }
543                 }
544
545                 object_list_insert(object, &not_mapped);
546         }
547
548         /*
549          * Best case scenario: We found bitmaps for all the roots,
550          * so the resulting `or` bitmap has the full reachability analysis
551          */
552         if (not_mapped == NULL)
553                 return base;
554
555         roots = not_mapped;
556
557         /*
558          * Let's iterate through all the roots that don't have bitmaps to
559          * check if we can determine them to be reachable from the existing
560          * global bitmap.
561          *
562          * If we cannot find them in the existing global bitmap, we'll need
563          * to push them to an actual walk and run it until we can confirm
564          * they are reachable
565          */
566         while (roots) {
567                 struct object *object = roots->item;
568                 int pos;
569
570                 roots = roots->next;
571                 pos = bitmap_position(bitmap_git, &object->oid);
572
573                 if (pos < 0 || base == NULL || !bitmap_get(base, pos)) {
574                         object->flags &= ~UNINTERESTING;
575                         add_pending_object(revs, object, "");
576                         needs_walk = 1;
577                 } else {
578                         object->flags |= SEEN;
579                 }
580         }
581
582         if (needs_walk) {
583                 struct include_data incdata;
584                 struct bitmap_show_data show_data;
585
586                 if (base == NULL)
587                         base = bitmap_new();
588
589                 incdata.bitmap_git = bitmap_git;
590                 incdata.base = base;
591                 incdata.seen = seen;
592
593                 revs->include_check = should_include;
594                 revs->include_check_data = &incdata;
595
596                 if (prepare_revision_walk(revs))
597                         die("revision walk setup failed");
598
599                 show_data.bitmap_git = bitmap_git;
600                 show_data.base = base;
601
602                 traverse_commit_list(revs, show_commit, show_object,
603                                      &show_data);
604         }
605
606         return base;
607 }
608
609 static void show_extended_objects(struct bitmap_index *bitmap_git,
610                                   struct rev_info *revs,
611                                   show_reachable_fn show_reach)
612 {
613         struct bitmap *objects = bitmap_git->result;
614         struct eindex *eindex = &bitmap_git->ext_index;
615         uint32_t i;
616
617         for (i = 0; i < eindex->count; ++i) {
618                 struct object *obj;
619
620                 if (!bitmap_get(objects, bitmap_git->pack->num_objects + i))
621                         continue;
622
623                 obj = eindex->objects[i];
624                 if ((obj->type == OBJ_BLOB && !revs->blob_objects) ||
625                     (obj->type == OBJ_TREE && !revs->tree_objects) ||
626                     (obj->type == OBJ_TAG && !revs->tag_objects))
627                         continue;
628
629                 show_reach(&obj->oid, obj->type, 0, eindex->hashes[i], NULL, 0);
630         }
631 }
632
633 static void init_type_iterator(struct ewah_iterator *it,
634                                struct bitmap_index *bitmap_git,
635                                enum object_type type)
636 {
637         switch (type) {
638         case OBJ_COMMIT:
639                 ewah_iterator_init(it, bitmap_git->commits);
640                 break;
641
642         case OBJ_TREE:
643                 ewah_iterator_init(it, bitmap_git->trees);
644                 break;
645
646         case OBJ_BLOB:
647                 ewah_iterator_init(it, bitmap_git->blobs);
648                 break;
649
650         case OBJ_TAG:
651                 ewah_iterator_init(it, bitmap_git->tags);
652                 break;
653
654         default:
655                 BUG("object type %d not stored by bitmap type index", type);
656                 break;
657         }
658 }
659
660 static void show_objects_for_type(
661         struct bitmap_index *bitmap_git,
662         enum object_type object_type,
663         show_reachable_fn show_reach)
664 {
665         size_t i = 0;
666         uint32_t offset;
667
668         struct ewah_iterator it;
669         eword_t filter;
670
671         struct bitmap *objects = bitmap_git->result;
672
673         init_type_iterator(&it, bitmap_git, object_type);
674
675         for (i = 0; i < objects->word_alloc &&
676                         ewah_iterator_next(&filter, &it); i++) {
677                 eword_t word = objects->words[i] & filter;
678                 size_t pos = (i * BITS_IN_EWORD);
679
680                 if (!word)
681                         continue;
682
683                 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
684                         struct object_id oid;
685                         struct revindex_entry *entry;
686                         uint32_t hash = 0;
687
688                         if ((word >> offset) == 0)
689                                 break;
690
691                         offset += ewah_bit_ctz64(word >> offset);
692
693                         entry = &bitmap_git->pack->revindex[pos + offset];
694                         nth_packed_object_id(&oid, bitmap_git->pack, entry->nr);
695
696                         if (bitmap_git->hashes)
697                                 hash = get_be32(bitmap_git->hashes + entry->nr);
698
699                         show_reach(&oid, object_type, 0, hash, bitmap_git->pack, entry->offset);
700                 }
701         }
702 }
703
704 static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
705                              struct object_list *roots)
706 {
707         while (roots) {
708                 struct object *object = roots->item;
709                 roots = roots->next;
710
711                 if (find_pack_entry_one(object->oid.hash, bitmap_git->pack) > 0)
712                         return 1;
713         }
714
715         return 0;
716 }
717
718 static struct bitmap *find_tip_blobs(struct bitmap_index *bitmap_git,
719                                      struct object_list *tip_objects)
720 {
721         struct bitmap *result = bitmap_new();
722         struct object_list *p;
723
724         for (p = tip_objects; p; p = p->next) {
725                 int pos;
726
727                 if (p->item->type != OBJ_BLOB)
728                         continue;
729
730                 pos = bitmap_position(bitmap_git, &p->item->oid);
731                 if (pos < 0)
732                         continue;
733
734                 bitmap_set(result, pos);
735         }
736
737         return result;
738 }
739
740 static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,
741                                     struct object_list *tip_objects,
742                                     struct bitmap *to_filter)
743 {
744         struct eindex *eindex = &bitmap_git->ext_index;
745         struct bitmap *tips;
746         struct ewah_iterator it;
747         eword_t mask;
748         uint32_t i;
749
750         /*
751          * The non-bitmap version of this filter never removes
752          * blobs which the other side specifically asked for,
753          * so we must match that behavior.
754          */
755         tips = find_tip_blobs(bitmap_git, tip_objects);
756
757         /*
758          * We can use the blob type-bitmap to work in whole words
759          * for the objects that are actually in the bitmapped packfile.
760          */
761         for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);
762              i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);
763              i++) {
764                 if (i < tips->word_alloc)
765                         mask &= ~tips->words[i];
766                 to_filter->words[i] &= ~mask;
767         }
768
769         /*
770          * Clear any blobs that weren't in the packfile (and so would not have
771          * been caught by the loop above. We'll have to check them
772          * individually.
773          */
774         for (i = 0; i < eindex->count; i++) {
775                 uint32_t pos = i + bitmap_git->pack->num_objects;
776                 if (eindex->objects[i]->type == OBJ_BLOB &&
777                     bitmap_get(to_filter, pos) &&
778                     !bitmap_get(tips, pos))
779                         bitmap_unset(to_filter, pos);
780         }
781
782         bitmap_free(tips);
783 }
784
785 static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,
786                                      uint32_t pos)
787 {
788         struct packed_git *pack = bitmap_git->pack;
789         unsigned long size;
790         struct object_info oi = OBJECT_INFO_INIT;
791
792         oi.sizep = &size;
793
794         if (pos < pack->num_objects) {
795                 struct revindex_entry *entry = &pack->revindex[pos];
796                 if (packed_object_info(the_repository, pack,
797                                        entry->offset, &oi) < 0) {
798                         struct object_id oid;
799                         nth_packed_object_id(&oid, pack, entry->nr);
800                         die(_("unable to get size of %s"), oid_to_hex(&oid));
801                 }
802         } else {
803                 struct eindex *eindex = &bitmap_git->ext_index;
804                 struct object *obj = eindex->objects[pos - pack->num_objects];
805                 if (oid_object_info_extended(the_repository, &obj->oid, &oi, 0) < 0)
806                         die(_("unable to get size of %s"), oid_to_hex(&obj->oid));
807         }
808
809         return size;
810 }
811
812 static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,
813                                      struct object_list *tip_objects,
814                                      struct bitmap *to_filter,
815                                      unsigned long limit)
816 {
817         struct eindex *eindex = &bitmap_git->ext_index;
818         struct bitmap *tips;
819         struct ewah_iterator it;
820         eword_t mask;
821         uint32_t i;
822
823         tips = find_tip_blobs(bitmap_git, tip_objects);
824
825         for (i = 0, init_type_iterator(&it, bitmap_git, OBJ_BLOB);
826              i < to_filter->word_alloc && ewah_iterator_next(&mask, &it);
827              i++) {
828                 eword_t word = to_filter->words[i] & mask;
829                 unsigned offset;
830
831                 for (offset = 0; offset < BITS_IN_EWORD; offset++) {
832                         uint32_t pos;
833
834                         if ((word >> offset) == 0)
835                                 break;
836                         offset += ewah_bit_ctz64(word >> offset);
837                         pos = i * BITS_IN_EWORD + offset;
838
839                         if (!bitmap_get(tips, pos) &&
840                             get_size_by_pos(bitmap_git, pos) >= limit)
841                                 bitmap_unset(to_filter, pos);
842                 }
843         }
844
845         for (i = 0; i < eindex->count; i++) {
846                 uint32_t pos = i + bitmap_git->pack->num_objects;
847                 if (eindex->objects[i]->type == OBJ_BLOB &&
848                     bitmap_get(to_filter, pos) &&
849                     !bitmap_get(tips, pos) &&
850                     get_size_by_pos(bitmap_git, pos) >= limit)
851                         bitmap_unset(to_filter, pos);
852         }
853
854         bitmap_free(tips);
855 }
856
857 static int filter_bitmap(struct bitmap_index *bitmap_git,
858                          struct object_list *tip_objects,
859                          struct bitmap *to_filter,
860                          struct list_objects_filter_options *filter)
861 {
862         if (!filter || filter->choice == LOFC_DISABLED)
863                 return 0;
864
865         if (filter->choice == LOFC_BLOB_NONE) {
866                 if (bitmap_git)
867                         filter_bitmap_blob_none(bitmap_git, tip_objects,
868                                                 to_filter);
869                 return 0;
870         }
871
872         if (filter->choice == LOFC_BLOB_LIMIT) {
873                 if (bitmap_git)
874                         filter_bitmap_blob_limit(bitmap_git, tip_objects,
875                                                  to_filter,
876                                                  filter->blob_limit_value);
877                 return 0;
878         }
879
880         /* filter choice not handled */
881         return -1;
882 }
883
884 static int can_filter_bitmap(struct list_objects_filter_options *filter)
885 {
886         return !filter_bitmap(NULL, NULL, NULL, filter);
887 }
888
889 struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
890                                          struct list_objects_filter_options *filter)
891 {
892         unsigned int i;
893
894         struct object_list *wants = NULL;
895         struct object_list *haves = NULL;
896
897         struct bitmap *wants_bitmap = NULL;
898         struct bitmap *haves_bitmap = NULL;
899
900         struct bitmap_index *bitmap_git;
901
902         /*
903          * We can't do pathspec limiting with bitmaps, because we don't know
904          * which commits are associated with which object changes (let alone
905          * even which objects are associated with which paths).
906          */
907         if (revs->prune)
908                 return NULL;
909
910         if (!can_filter_bitmap(filter))
911                 return NULL;
912
913         /* try to open a bitmapped pack, but don't parse it yet
914          * because we may not need to use it */
915         bitmap_git = xcalloc(1, sizeof(*bitmap_git));
916         if (open_pack_bitmap(revs->repo, bitmap_git) < 0)
917                 goto cleanup;
918
919         for (i = 0; i < revs->pending.nr; ++i) {
920                 struct object *object = revs->pending.objects[i].item;
921
922                 if (object->type == OBJ_NONE)
923                         parse_object_or_die(&object->oid, NULL);
924
925                 while (object->type == OBJ_TAG) {
926                         struct tag *tag = (struct tag *) object;
927
928                         if (object->flags & UNINTERESTING)
929                                 object_list_insert(object, &haves);
930                         else
931                                 object_list_insert(object, &wants);
932
933                         object = parse_object_or_die(get_tagged_oid(tag), NULL);
934                 }
935
936                 if (object->flags & UNINTERESTING)
937                         object_list_insert(object, &haves);
938                 else
939                         object_list_insert(object, &wants);
940         }
941
942         /*
943          * if we have a HAVES list, but none of those haves is contained
944          * in the packfile that has a bitmap, we don't have anything to
945          * optimize here
946          */
947         if (haves && !in_bitmapped_pack(bitmap_git, haves))
948                 goto cleanup;
949
950         /* if we don't want anything, we're done here */
951         if (!wants)
952                 goto cleanup;
953
954         /*
955          * now we're going to use bitmaps, so load the actual bitmap entries
956          * from disk. this is the point of no return; after this the rev_list
957          * becomes invalidated and we must perform the revwalk through bitmaps
958          */
959         if (load_pack_bitmap(bitmap_git) < 0)
960                 goto cleanup;
961
962         object_array_clear(&revs->pending);
963
964         if (haves) {
965                 revs->ignore_missing_links = 1;
966                 haves_bitmap = find_objects(bitmap_git, revs, haves, NULL);
967                 reset_revision_walk();
968                 revs->ignore_missing_links = 0;
969
970                 if (haves_bitmap == NULL)
971                         BUG("failed to perform bitmap walk");
972         }
973
974         wants_bitmap = find_objects(bitmap_git, revs, wants, haves_bitmap);
975
976         if (!wants_bitmap)
977                 BUG("failed to perform bitmap walk");
978
979         if (haves_bitmap)
980                 bitmap_and_not(wants_bitmap, haves_bitmap);
981
982         filter_bitmap(bitmap_git, wants, wants_bitmap, filter);
983
984         bitmap_git->result = wants_bitmap;
985         bitmap_git->haves = haves_bitmap;
986
987         object_list_free(&wants);
988         object_list_free(&haves);
989
990         return bitmap_git;
991
992 cleanup:
993         free_bitmap_index(bitmap_git);
994         object_list_free(&wants);
995         object_list_free(&haves);
996         return NULL;
997 }
998
999 static void try_partial_reuse(struct bitmap_index *bitmap_git,
1000                               size_t pos,
1001                               struct bitmap *reuse,
1002                               struct pack_window **w_curs)
1003 {
1004         struct revindex_entry *revidx;
1005         off_t offset;
1006         enum object_type type;
1007         unsigned long size;
1008
1009         if (pos >= bitmap_git->pack->num_objects)
1010                 return; /* not actually in the pack */
1011
1012         revidx = &bitmap_git->pack->revindex[pos];
1013         offset = revidx->offset;
1014         type = unpack_object_header(bitmap_git->pack, w_curs, &offset, &size);
1015         if (type < 0)
1016                 return; /* broken packfile, punt */
1017
1018         if (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {
1019                 off_t base_offset;
1020                 int base_pos;
1021
1022                 /*
1023                  * Find the position of the base object so we can look it up
1024                  * in our bitmaps. If we can't come up with an offset, or if
1025                  * that offset is not in the revidx, the pack is corrupt.
1026                  * There's nothing we can do, so just punt on this object,
1027                  * and the normal slow path will complain about it in
1028                  * more detail.
1029                  */
1030                 base_offset = get_delta_base(bitmap_git->pack, w_curs,
1031                                              &offset, type, revidx->offset);
1032                 if (!base_offset)
1033                         return;
1034                 base_pos = find_revindex_position(bitmap_git->pack, base_offset);
1035                 if (base_pos < 0)
1036                         return;
1037
1038                 /*
1039                  * We assume delta dependencies always point backwards. This
1040                  * lets us do a single pass, and is basically always true
1041                  * due to the way OFS_DELTAs work. You would not typically
1042                  * find REF_DELTA in a bitmapped pack, since we only bitmap
1043                  * packs we write fresh, and OFS_DELTA is the default). But
1044                  * let's double check to make sure the pack wasn't written with
1045                  * odd parameters.
1046                  */
1047                 if (base_pos >= pos)
1048                         return;
1049
1050                 /*
1051                  * And finally, if we're not sending the base as part of our
1052                  * reuse chunk, then don't send this object either. The base
1053                  * would come after us, along with other objects not
1054                  * necessarily in the pack, which means we'd need to convert
1055                  * to REF_DELTA on the fly. Better to just let the normal
1056                  * object_entry code path handle it.
1057                  */
1058                 if (!bitmap_get(reuse, base_pos))
1059                         return;
1060         }
1061
1062         /*
1063          * If we got here, then the object is OK to reuse. Mark it.
1064          */
1065         bitmap_set(reuse, pos);
1066 }
1067
1068 int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
1069                                        struct packed_git **packfile_out,
1070                                        uint32_t *entries,
1071                                        struct bitmap **reuse_out)
1072 {
1073         struct bitmap *result = bitmap_git->result;
1074         struct bitmap *reuse;
1075         struct pack_window *w_curs = NULL;
1076         size_t i = 0;
1077         uint32_t offset;
1078
1079         assert(result);
1080
1081         while (i < result->word_alloc && result->words[i] == (eword_t)~0)
1082                 i++;
1083
1084         /* Don't mark objects not in the packfile */
1085         if (i > bitmap_git->pack->num_objects / BITS_IN_EWORD)
1086                 i = bitmap_git->pack->num_objects / BITS_IN_EWORD;
1087
1088         reuse = bitmap_word_alloc(i);
1089         memset(reuse->words, 0xFF, i * sizeof(eword_t));
1090
1091         for (; i < result->word_alloc; ++i) {
1092                 eword_t word = result->words[i];
1093                 size_t pos = (i * BITS_IN_EWORD);
1094
1095                 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1096                         if ((word >> offset) == 0)
1097                                 break;
1098
1099                         offset += ewah_bit_ctz64(word >> offset);
1100                         try_partial_reuse(bitmap_git, pos + offset, reuse, &w_curs);
1101                 }
1102         }
1103
1104         unuse_pack(&w_curs);
1105
1106         *entries = bitmap_popcount(reuse);
1107         if (!*entries) {
1108                 bitmap_free(reuse);
1109                 return -1;
1110         }
1111
1112         /*
1113          * Drop any reused objects from the result, since they will not
1114          * need to be handled separately.
1115          */
1116         bitmap_and_not(result, reuse);
1117         *packfile_out = bitmap_git->pack;
1118         *reuse_out = reuse;
1119         return 0;
1120 }
1121
1122 int bitmap_walk_contains(struct bitmap_index *bitmap_git,
1123                          struct bitmap *bitmap, const struct object_id *oid)
1124 {
1125         int idx;
1126
1127         if (!bitmap)
1128                 return 0;
1129
1130         idx = bitmap_position(bitmap_git, oid);
1131         return idx >= 0 && bitmap_get(bitmap, idx);
1132 }
1133
1134 void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,
1135                                  struct rev_info *revs,
1136                                  show_reachable_fn show_reachable)
1137 {
1138         assert(bitmap_git->result);
1139
1140         show_objects_for_type(bitmap_git, OBJ_COMMIT, show_reachable);
1141         if (revs->tree_objects)
1142                 show_objects_for_type(bitmap_git, OBJ_TREE, show_reachable);
1143         if (revs->blob_objects)
1144                 show_objects_for_type(bitmap_git, OBJ_BLOB, show_reachable);
1145         if (revs->tag_objects)
1146                 show_objects_for_type(bitmap_git, OBJ_TAG, show_reachable);
1147
1148         show_extended_objects(bitmap_git, revs, show_reachable);
1149 }
1150
1151 static uint32_t count_object_type(struct bitmap_index *bitmap_git,
1152                                   enum object_type type)
1153 {
1154         struct bitmap *objects = bitmap_git->result;
1155         struct eindex *eindex = &bitmap_git->ext_index;
1156
1157         uint32_t i = 0, count = 0;
1158         struct ewah_iterator it;
1159         eword_t filter;
1160
1161         init_type_iterator(&it, bitmap_git, type);
1162
1163         while (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {
1164                 eword_t word = objects->words[i++] & filter;
1165                 count += ewah_bit_popcount64(word);
1166         }
1167
1168         for (i = 0; i < eindex->count; ++i) {
1169                 if (eindex->objects[i]->type == type &&
1170                         bitmap_get(objects, bitmap_git->pack->num_objects + i))
1171                         count++;
1172         }
1173
1174         return count;
1175 }
1176
1177 void count_bitmap_commit_list(struct bitmap_index *bitmap_git,
1178                               uint32_t *commits, uint32_t *trees,
1179                               uint32_t *blobs, uint32_t *tags)
1180 {
1181         assert(bitmap_git->result);
1182
1183         if (commits)
1184                 *commits = count_object_type(bitmap_git, OBJ_COMMIT);
1185
1186         if (trees)
1187                 *trees = count_object_type(bitmap_git, OBJ_TREE);
1188
1189         if (blobs)
1190                 *blobs = count_object_type(bitmap_git, OBJ_BLOB);
1191
1192         if (tags)
1193                 *tags = count_object_type(bitmap_git, OBJ_TAG);
1194 }
1195
1196 struct bitmap_test_data {
1197         struct bitmap_index *bitmap_git;
1198         struct bitmap *base;
1199         struct progress *prg;
1200         size_t seen;
1201 };
1202
1203 static void test_show_object(struct object *object, const char *name,
1204                              void *data)
1205 {
1206         struct bitmap_test_data *tdata = data;
1207         int bitmap_pos;
1208
1209         bitmap_pos = bitmap_position(tdata->bitmap_git, &object->oid);
1210         if (bitmap_pos < 0)
1211                 die("Object not in bitmap: %s\n", oid_to_hex(&object->oid));
1212
1213         bitmap_set(tdata->base, bitmap_pos);
1214         display_progress(tdata->prg, ++tdata->seen);
1215 }
1216
1217 static void test_show_commit(struct commit *commit, void *data)
1218 {
1219         struct bitmap_test_data *tdata = data;
1220         int bitmap_pos;
1221
1222         bitmap_pos = bitmap_position(tdata->bitmap_git,
1223                                      &commit->object.oid);
1224         if (bitmap_pos < 0)
1225                 die("Object not in bitmap: %s\n", oid_to_hex(&commit->object.oid));
1226
1227         bitmap_set(tdata->base, bitmap_pos);
1228         display_progress(tdata->prg, ++tdata->seen);
1229 }
1230
1231 void test_bitmap_walk(struct rev_info *revs)
1232 {
1233         struct object *root;
1234         struct bitmap *result = NULL;
1235         khiter_t pos;
1236         size_t result_popcnt;
1237         struct bitmap_test_data tdata;
1238         struct bitmap_index *bitmap_git;
1239
1240         if (!(bitmap_git = prepare_bitmap_git(revs->repo)))
1241                 die("failed to load bitmap indexes");
1242
1243         if (revs->pending.nr != 1)
1244                 die("you must specify exactly one commit to test");
1245
1246         fprintf(stderr, "Bitmap v%d test (%d entries loaded)\n",
1247                 bitmap_git->version, bitmap_git->entry_count);
1248
1249         root = revs->pending.objects[0].item;
1250         pos = kh_get_oid_map(bitmap_git->bitmaps, root->oid);
1251
1252         if (pos < kh_end(bitmap_git->bitmaps)) {
1253                 struct stored_bitmap *st = kh_value(bitmap_git->bitmaps, pos);
1254                 struct ewah_bitmap *bm = lookup_stored_bitmap(st);
1255
1256                 fprintf(stderr, "Found bitmap for %s. %d bits / %08x checksum\n",
1257                         oid_to_hex(&root->oid), (int)bm->bit_size, ewah_checksum(bm));
1258
1259                 result = ewah_to_bitmap(bm);
1260         }
1261
1262         if (result == NULL)
1263                 die("Commit %s doesn't have an indexed bitmap", oid_to_hex(&root->oid));
1264
1265         revs->tag_objects = 1;
1266         revs->tree_objects = 1;
1267         revs->blob_objects = 1;
1268
1269         result_popcnt = bitmap_popcount(result);
1270
1271         if (prepare_revision_walk(revs))
1272                 die("revision walk setup failed");
1273
1274         tdata.bitmap_git = bitmap_git;
1275         tdata.base = bitmap_new();
1276         tdata.prg = start_progress("Verifying bitmap entries", result_popcnt);
1277         tdata.seen = 0;
1278
1279         traverse_commit_list(revs, &test_show_commit, &test_show_object, &tdata);
1280
1281         stop_progress(&tdata.prg);
1282
1283         if (bitmap_equals(result, tdata.base))
1284                 fprintf(stderr, "OK!\n");
1285         else
1286                 fprintf(stderr, "Mismatch!\n");
1287
1288         free_bitmap_index(bitmap_git);
1289 }
1290
1291 static int rebuild_bitmap(uint32_t *reposition,
1292                           struct ewah_bitmap *source,
1293                           struct bitmap *dest)
1294 {
1295         uint32_t pos = 0;
1296         struct ewah_iterator it;
1297         eword_t word;
1298
1299         ewah_iterator_init(&it, source);
1300
1301         while (ewah_iterator_next(&word, &it)) {
1302                 uint32_t offset, bit_pos;
1303
1304                 for (offset = 0; offset < BITS_IN_EWORD; ++offset) {
1305                         if ((word >> offset) == 0)
1306                                 break;
1307
1308                         offset += ewah_bit_ctz64(word >> offset);
1309
1310                         bit_pos = reposition[pos + offset];
1311                         if (bit_pos > 0)
1312                                 bitmap_set(dest, bit_pos - 1);
1313                         else /* can't reuse, we don't have the object */
1314                                 return -1;
1315                 }
1316
1317                 pos += BITS_IN_EWORD;
1318         }
1319         return 0;
1320 }
1321
1322 int rebuild_existing_bitmaps(struct bitmap_index *bitmap_git,
1323                              struct packing_data *mapping,
1324                              kh_oid_map_t *reused_bitmaps,
1325                              int show_progress)
1326 {
1327         uint32_t i, num_objects;
1328         uint32_t *reposition;
1329         struct bitmap *rebuild;
1330         struct stored_bitmap *stored;
1331         struct progress *progress = NULL;
1332
1333         khiter_t hash_pos;
1334         int hash_ret;
1335
1336         num_objects = bitmap_git->pack->num_objects;
1337         reposition = xcalloc(num_objects, sizeof(uint32_t));
1338
1339         for (i = 0; i < num_objects; ++i) {
1340                 struct object_id oid;
1341                 struct revindex_entry *entry;
1342                 struct object_entry *oe;
1343
1344                 entry = &bitmap_git->pack->revindex[i];
1345                 nth_packed_object_id(&oid, bitmap_git->pack, entry->nr);
1346                 oe = packlist_find(mapping, &oid);
1347
1348                 if (oe)
1349                         reposition[i] = oe_in_pack_pos(mapping, oe) + 1;
1350         }
1351
1352         rebuild = bitmap_new();
1353         i = 0;
1354
1355         if (show_progress)
1356                 progress = start_progress("Reusing bitmaps", 0);
1357
1358         kh_foreach_value(bitmap_git->bitmaps, stored, {
1359                 if (stored->flags & BITMAP_FLAG_REUSE) {
1360                         if (!rebuild_bitmap(reposition,
1361                                             lookup_stored_bitmap(stored),
1362                                             rebuild)) {
1363                                 hash_pos = kh_put_oid_map(reused_bitmaps,
1364                                                           stored->oid,
1365                                                           &hash_ret);
1366                                 kh_value(reused_bitmaps, hash_pos) =
1367                                         bitmap_to_ewah(rebuild);
1368                         }
1369                         bitmap_reset(rebuild);
1370                         display_progress(progress, ++i);
1371                 }
1372         });
1373
1374         stop_progress(&progress);
1375
1376         free(reposition);
1377         bitmap_free(rebuild);
1378         return 0;
1379 }
1380
1381 void free_bitmap_index(struct bitmap_index *b)
1382 {
1383         if (!b)
1384                 return;
1385
1386         if (b->map)
1387                 munmap(b->map, b->map_size);
1388         ewah_pool_free(b->commits);
1389         ewah_pool_free(b->trees);
1390         ewah_pool_free(b->blobs);
1391         ewah_pool_free(b->tags);
1392         kh_destroy_oid_map(b->bitmaps);
1393         free(b->ext_index.objects);
1394         free(b->ext_index.hashes);
1395         bitmap_free(b->result);
1396         bitmap_free(b->haves);
1397         free(b);
1398 }
1399
1400 int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,
1401                                     const struct object_id *oid)
1402 {
1403         return bitmap_git &&
1404                 bitmap_walk_contains(bitmap_git, bitmap_git->haves, oid);
1405 }