Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 1 | #include "cache.h" |
| 2 | #include "object.h" |
| 3 | #include "pack.h" |
| 4 | #include "pack-objects.h" |
Nguyễn Thái Ngọc Duy | 43fa44f | 2018-04-14 17:35:05 +0200 | [diff] [blame] | 5 | #include "packfile.h" |
| 6 | #include "config.h" |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 7 | |
| 8 | static uint32_t locate_object_entry_hash(struct packing_data *pdata, |
| 9 | const unsigned char *sha1, |
| 10 | int *found) |
| 11 | { |
Karsten Blees | 039dc71 | 2014-07-03 00:20:20 +0200 | [diff] [blame] | 12 | uint32_t i, mask = (pdata->index_size - 1); |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 13 | |
Karsten Blees | 039dc71 | 2014-07-03 00:20:20 +0200 | [diff] [blame] | 14 | i = sha1hash(sha1) & mask; |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 15 | |
| 16 | while (pdata->index[i] > 0) { |
| 17 | uint32_t pos = pdata->index[i] - 1; |
| 18 | |
Jeff King | e3ff068 | 2018-08-28 17:22:44 -0400 | [diff] [blame] | 19 | if (hasheq(sha1, pdata->objects[pos].idx.oid.hash)) { |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 20 | *found = 1; |
| 21 | return i; |
| 22 | } |
| 23 | |
| 24 | i = (i + 1) & mask; |
| 25 | } |
| 26 | |
| 27 | *found = 0; |
| 28 | return i; |
| 29 | } |
| 30 | |
| 31 | static inline uint32_t closest_pow2(uint32_t v) |
| 32 | { |
| 33 | v = v - 1; |
| 34 | v |= v >> 1; |
| 35 | v |= v >> 2; |
| 36 | v |= v >> 4; |
| 37 | v |= v >> 8; |
| 38 | v |= v >> 16; |
| 39 | return v + 1; |
| 40 | } |
| 41 | |
| 42 | static void rehash_objects(struct packing_data *pdata) |
| 43 | { |
| 44 | uint32_t i; |
| 45 | struct object_entry *entry; |
| 46 | |
| 47 | pdata->index_size = closest_pow2(pdata->nr_objects * 3); |
| 48 | if (pdata->index_size < 1024) |
| 49 | pdata->index_size = 1024; |
| 50 | |
René Scharfe | fb79947 | 2014-06-01 13:07:21 +0200 | [diff] [blame] | 51 | free(pdata->index); |
| 52 | pdata->index = xcalloc(pdata->index_size, sizeof(*pdata->index)); |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 53 | |
| 54 | entry = pdata->objects; |
| 55 | |
| 56 | for (i = 0; i < pdata->nr_objects; i++) { |
| 57 | int found; |
brian m. carlson | e6a492b | 2017-05-06 22:10:11 +0000 | [diff] [blame] | 58 | uint32_t ix = locate_object_entry_hash(pdata, |
| 59 | entry->idx.oid.hash, |
| 60 | &found); |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 61 | |
| 62 | if (found) |
Johannes Schindelin | 033abf9 | 2018-05-02 11:38:39 +0200 | [diff] [blame] | 63 | BUG("Duplicate object in hash"); |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 64 | |
| 65 | pdata->index[ix] = i + 1; |
| 66 | entry++; |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | struct object_entry *packlist_find(struct packing_data *pdata, |
| 71 | const unsigned char *sha1, |
| 72 | uint32_t *index_pos) |
| 73 | { |
| 74 | uint32_t i; |
| 75 | int found; |
| 76 | |
| 77 | if (!pdata->index_size) |
| 78 | return NULL; |
| 79 | |
| 80 | i = locate_object_entry_hash(pdata, sha1, &found); |
| 81 | |
| 82 | if (index_pos) |
| 83 | *index_pos = i; |
| 84 | |
| 85 | if (!found) |
| 86 | return NULL; |
| 87 | |
| 88 | return &pdata->objects[pdata->index[i] - 1]; |
| 89 | } |
| 90 | |
Nguyễn Thái Ngọc Duy | 43fa44f | 2018-04-14 17:35:05 +0200 | [diff] [blame] | 91 | static void prepare_in_pack_by_idx(struct packing_data *pdata) |
| 92 | { |
| 93 | struct packed_git **mapping, *p; |
| 94 | int cnt = 0, nr = 1U << OE_IN_PACK_BITS; |
| 95 | |
| 96 | ALLOC_ARRAY(mapping, nr); |
| 97 | /* |
| 98 | * oe_in_pack() on an all-zero'd object_entry |
| 99 | * (i.e. in_pack_idx also zero) should return NULL. |
| 100 | */ |
| 101 | mapping[cnt++] = NULL; |
Nguyễn Thái Ngọc Duy | 7c14112 | 2018-11-10 06:49:08 +0100 | [diff] [blame] | 102 | for (p = get_all_packs(pdata->repo); p; p = p->next, cnt++) { |
Nguyễn Thái Ngọc Duy | 43fa44f | 2018-04-14 17:35:05 +0200 | [diff] [blame] | 103 | if (cnt == nr) { |
| 104 | free(mapping); |
| 105 | return; |
| 106 | } |
| 107 | p->index = cnt; |
| 108 | mapping[cnt] = p; |
| 109 | } |
| 110 | pdata->in_pack_by_idx = mapping; |
| 111 | } |
| 112 | |
| 113 | /* |
| 114 | * A new pack appears after prepare_in_pack_by_idx() has been |
| 115 | * run. This is likely a race. |
| 116 | * |
| 117 | * We could map this new pack to in_pack_by_idx[] array, but then we |
| 118 | * have to deal with full array anyway. And since it's hard to test |
| 119 | * this fall back code, just stay simple and fall back to using |
| 120 | * in_pack[] array. |
| 121 | */ |
| 122 | void oe_map_new_pack(struct packing_data *pack, |
| 123 | struct packed_git *p) |
| 124 | { |
| 125 | uint32_t i; |
| 126 | |
| 127 | REALLOC_ARRAY(pack->in_pack, pack->nr_alloc); |
| 128 | |
| 129 | for (i = 0; i < pack->nr_objects; i++) |
| 130 | pack->in_pack[i] = oe_in_pack(pack, pack->objects + i); |
| 131 | |
| 132 | FREE_AND_NULL(pack->in_pack_by_idx); |
| 133 | } |
| 134 | |
| 135 | /* assume pdata is already zero'd by caller */ |
Nguyễn Thái Ngọc Duy | 7c14112 | 2018-11-10 06:49:08 +0100 | [diff] [blame] | 136 | void prepare_packing_data(struct repository *r, struct packing_data *pdata) |
Nguyễn Thái Ngọc Duy | 43fa44f | 2018-04-14 17:35:05 +0200 | [diff] [blame] | 137 | { |
Nguyễn Thái Ngọc Duy | 7c14112 | 2018-11-10 06:49:08 +0100 | [diff] [blame] | 138 | pdata->repo = r; |
| 139 | |
Nguyễn Thái Ngọc Duy | 43fa44f | 2018-04-14 17:35:05 +0200 | [diff] [blame] | 140 | if (git_env_bool("GIT_TEST_FULL_IN_PACK_ARRAY", 0)) { |
| 141 | /* |
| 142 | * do not initialize in_pack_by_idx[] to force the |
| 143 | * slow path in oe_in_pack() |
| 144 | */ |
| 145 | } else { |
| 146 | prepare_in_pack_by_idx(pdata); |
| 147 | } |
Nguyễn Thái Ngọc Duy | ac77d0c | 2018-04-14 17:35:10 +0200 | [diff] [blame] | 148 | |
| 149 | pdata->oe_size_limit = git_env_ulong("GIT_TEST_OE_SIZE", |
| 150 | 1U << OE_SIZE_BITS); |
Nguyễn Thái Ngọc Duy | 9ac3f0e | 2018-07-22 10:04:21 +0200 | [diff] [blame] | 151 | pdata->oe_delta_size_limit = git_env_ulong("GIT_TEST_OE_DELTA_SIZE", |
| 152 | 1UL << OE_DELTA_SIZE_BITS); |
Patrick Hogg | edb673c | 2019-01-24 19:22:05 -0500 | [diff] [blame] | 153 | init_recursive_mutex(&pdata->odb_lock); |
Nguyễn Thái Ngọc Duy | 43fa44f | 2018-04-14 17:35:05 +0200 | [diff] [blame] | 154 | } |
| 155 | |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 156 | struct object_entry *packlist_alloc(struct packing_data *pdata, |
| 157 | const unsigned char *sha1, |
| 158 | uint32_t index_pos) |
| 159 | { |
| 160 | struct object_entry *new_entry; |
| 161 | |
| 162 | if (pdata->nr_objects >= pdata->nr_alloc) { |
| 163 | pdata->nr_alloc = (pdata->nr_alloc + 1024) * 3 / 2; |
René Scharfe | 2756ca4 | 2014-09-16 20:56:57 +0200 | [diff] [blame] | 164 | REALLOC_ARRAY(pdata->objects, pdata->nr_alloc); |
Nguyễn Thái Ngọc Duy | 43fa44f | 2018-04-14 17:35:05 +0200 | [diff] [blame] | 165 | |
| 166 | if (!pdata->in_pack_by_idx) |
| 167 | REALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc); |
Nguyễn Thái Ngọc Duy | 9ac3f0e | 2018-07-22 10:04:21 +0200 | [diff] [blame] | 168 | if (pdata->delta_size) |
| 169 | REALLOC_ARRAY(pdata->delta_size, pdata->nr_alloc); |
Christian Couder | 108f530 | 2018-08-16 08:13:12 +0200 | [diff] [blame] | 170 | |
| 171 | if (pdata->tree_depth) |
| 172 | REALLOC_ARRAY(pdata->tree_depth, pdata->nr_alloc); |
Christian Couder | fe0ac2f | 2018-08-16 08:13:13 +0200 | [diff] [blame] | 173 | |
| 174 | if (pdata->layer) |
| 175 | REALLOC_ARRAY(pdata->layer, pdata->nr_alloc); |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 176 | } |
| 177 | |
| 178 | new_entry = pdata->objects + pdata->nr_objects++; |
| 179 | |
| 180 | memset(new_entry, 0, sizeof(*new_entry)); |
brian m. carlson | e6a492b | 2017-05-06 22:10:11 +0000 | [diff] [blame] | 181 | hashcpy(new_entry->idx.oid.hash, sha1); |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 182 | |
| 183 | if (pdata->index_size * 3 <= pdata->nr_objects * 4) |
| 184 | rehash_objects(pdata); |
| 185 | else |
| 186 | pdata->index[index_pos] = pdata->nr_objects; |
| 187 | |
Nguyễn Thái Ngọc Duy | 43fa44f | 2018-04-14 17:35:05 +0200 | [diff] [blame] | 188 | if (pdata->in_pack) |
| 189 | pdata->in_pack[pdata->nr_objects - 1] = NULL; |
| 190 | |
Christian Couder | 108f530 | 2018-08-16 08:13:12 +0200 | [diff] [blame] | 191 | if (pdata->tree_depth) |
| 192 | pdata->tree_depth[pdata->nr_objects - 1] = 0; |
| 193 | |
Christian Couder | fe0ac2f | 2018-08-16 08:13:13 +0200 | [diff] [blame] | 194 | if (pdata->layer) |
| 195 | pdata->layer[pdata->nr_objects - 1] = 0; |
| 196 | |
Vicent Marti | 2834bc2 | 2013-10-24 14:01:06 -0400 | [diff] [blame] | 197 | return new_entry; |
| 198 | } |
Jeff King | 6a1e32d | 2018-08-21 15:07:05 -0400 | [diff] [blame] | 199 | |
| 200 | void oe_set_delta_ext(struct packing_data *pdata, |
| 201 | struct object_entry *delta, |
| 202 | const unsigned char *sha1) |
| 203 | { |
| 204 | struct object_entry *base; |
| 205 | |
| 206 | ALLOC_GROW(pdata->ext_bases, pdata->nr_ext + 1, pdata->alloc_ext); |
| 207 | base = &pdata->ext_bases[pdata->nr_ext++]; |
| 208 | memset(base, 0, sizeof(*base)); |
| 209 | hashcpy(base->idx.oid.hash, sha1); |
| 210 | |
| 211 | /* These flags mark that we are not part of the actual pack output. */ |
| 212 | base->preferred_base = 1; |
| 213 | base->filled = 1; |
| 214 | |
| 215 | delta->ext_base = 1; |
| 216 | delta->delta_idx = base - pdata->ext_bases + 1; |
| 217 | } |