| 1 | #include "git-compat-util.h" |
| 2 | #include "object.h" |
| 3 | #include "pack.h" |
| 4 | #include "pack-objects.h" |
| 5 | #include "packfile.h" |
| 6 | #include "parse.h" |
| 7 | #include "repository.h" |
| 8 | |
| 9 | static uint32_t locate_object_entry_hash(struct packing_data *pdata, |
| 10 | const struct object_id *oid, |
| 11 | int *found) |
| 12 | { |
| 13 | uint32_t i, mask = (pdata->index_size - 1); |
| 14 | |
| 15 | i = oidhash(oid) & mask; |
| 16 | |
| 17 | while (pdata->index[i] > 0) { |
| 18 | uint32_t pos = pdata->index[i] - 1; |
| 19 | |
| 20 | if (oideq(oid, &pdata->objects[pos].idx.oid)) { |
| 21 | *found = 1; |
| 22 | return i; |
| 23 | } |
| 24 | |
| 25 | i = (i + 1) & mask; |
| 26 | } |
| 27 | |
| 28 | *found = 0; |
| 29 | return i; |
| 30 | } |
| 31 | |
| 32 | static inline uint32_t closest_pow2(uint32_t v) |
| 33 | { |
| 34 | v = v - 1; |
| 35 | v |= v >> 1; |
| 36 | v |= v >> 2; |
| 37 | v |= v >> 4; |
| 38 | v |= v >> 8; |
| 39 | v |= v >> 16; |
| 40 | return v + 1; |
| 41 | } |
| 42 | |
| 43 | static void rehash_objects(struct packing_data *pdata) |
| 44 | { |
| 45 | uint32_t i; |
| 46 | struct object_entry *entry; |
| 47 | |
| 48 | pdata->index_size = closest_pow2(pdata->nr_objects * 3); |
| 49 | if (pdata->index_size < 1024) |
| 50 | pdata->index_size = 1024; |
| 51 | |
| 52 | free(pdata->index); |
| 53 | CALLOC_ARRAY(pdata->index, pdata->index_size); |
| 54 | |
| 55 | entry = pdata->objects; |
| 56 | |
| 57 | for (i = 0; i < pdata->nr_objects; i++) { |
| 58 | int found; |
| 59 | uint32_t ix = locate_object_entry_hash(pdata, |
| 60 | &entry->idx.oid, |
| 61 | &found); |
| 62 | |
| 63 | if (found) |
| 64 | BUG("Duplicate object in hash"); |
| 65 | |
| 66 | pdata->index[ix] = i + 1; |
| 67 | entry++; |
| 68 | } |
| 69 | } |
| 70 | |
| 71 | struct object_entry *packlist_find(struct packing_data *pdata, |
| 72 | const struct object_id *oid) |
| 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, oid, &found); |
| 81 | |
| 82 | if (!found) |
| 83 | return NULL; |
| 84 | |
| 85 | return &pdata->objects[pdata->index[i] - 1]; |
| 86 | } |
| 87 | |
| 88 | static void prepare_in_pack_by_idx(struct packing_data *pdata) |
| 89 | { |
| 90 | struct packed_git **mapping, *p; |
| 91 | int cnt = 0, nr = 1U << OE_IN_PACK_BITS; |
| 92 | |
| 93 | ALLOC_ARRAY(mapping, nr); |
| 94 | /* |
| 95 | * oe_in_pack() on an all-zero'd object_entry |
| 96 | * (i.e. in_pack_idx also zero) should return NULL. |
| 97 | */ |
| 98 | mapping[cnt++] = NULL; |
| 99 | repo_for_each_pack(pdata->repo, p) { |
| 100 | if (cnt == nr) { |
| 101 | free(mapping); |
| 102 | return; |
| 103 | } |
| 104 | p->index = cnt; |
| 105 | mapping[cnt++] = p; |
| 106 | } |
| 107 | pdata->in_pack_by_idx = mapping; |
| 108 | } |
| 109 | |
| 110 | /* |
| 111 | * A new pack appears after prepare_in_pack_by_idx() has been |
| 112 | * run. This is likely a race. |
| 113 | * |
| 114 | * We could map this new pack to in_pack_by_idx[] array, but then we |
| 115 | * have to deal with full array anyway. And since it's hard to test |
| 116 | * this fall back code, just stay simple and fall back to using |
| 117 | * in_pack[] array. |
| 118 | */ |
| 119 | void oe_map_new_pack(struct packing_data *pack) |
| 120 | { |
| 121 | uint32_t i; |
| 122 | |
| 123 | if (pack->in_pack) |
| 124 | BUG("packing_data has already been converted to pack array"); |
| 125 | |
| 126 | ALLOC_ARRAY(pack->in_pack, pack->nr_alloc); |
| 127 | |
| 128 | for (i = 0; i < pack->nr_objects; i++) |
| 129 | pack->in_pack[i] = oe_in_pack(pack, pack->objects + i); |
| 130 | |
| 131 | FREE_AND_NULL(pack->in_pack_by_idx); |
| 132 | } |
| 133 | |
| 134 | /* assume pdata is already zero'd by caller */ |
| 135 | void prepare_packing_data(struct repository *r, struct packing_data *pdata) |
| 136 | { |
| 137 | pdata->repo = r; |
| 138 | |
| 139 | if (git_env_bool("GIT_TEST_FULL_IN_PACK_ARRAY", 0)) { |
| 140 | /* |
| 141 | * do not initialize in_pack_by_idx[] to force the |
| 142 | * slow path in oe_in_pack() |
| 143 | */ |
| 144 | } else { |
| 145 | prepare_in_pack_by_idx(pdata); |
| 146 | } |
| 147 | |
| 148 | pdata->oe_size_limit = git_env_ulong("GIT_TEST_OE_SIZE", |
| 149 | 1U << OE_SIZE_BITS); |
| 150 | pdata->oe_delta_size_limit = git_env_ulong("GIT_TEST_OE_DELTA_SIZE", |
| 151 | 1UL << OE_DELTA_SIZE_BITS); |
| 152 | init_recursive_mutex(&pdata->odb_lock); |
| 153 | } |
| 154 | |
| 155 | void clear_packing_data(struct packing_data *pdata) |
| 156 | { |
| 157 | if (!pdata) |
| 158 | return; |
| 159 | |
| 160 | free(pdata->cruft_mtime); |
| 161 | free(pdata->in_pack); |
| 162 | free(pdata->in_pack_by_idx); |
| 163 | free(pdata->in_pack_pos); |
| 164 | free(pdata->index); |
| 165 | free(pdata->layer); |
| 166 | free(pdata->objects); |
| 167 | free(pdata->tree_depth); |
| 168 | } |
| 169 | |
| 170 | struct object_entry *packlist_alloc(struct packing_data *pdata, |
| 171 | const struct object_id *oid) |
| 172 | { |
| 173 | struct object_entry *new_entry; |
| 174 | |
| 175 | if (pdata->nr_objects >= pdata->nr_alloc) { |
| 176 | pdata->nr_alloc = (pdata->nr_alloc + 1024) * 3 / 2; |
| 177 | REALLOC_ARRAY(pdata->objects, pdata->nr_alloc); |
| 178 | |
| 179 | if (!pdata->in_pack_by_idx) |
| 180 | REALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc); |
| 181 | if (pdata->delta_size) |
| 182 | REALLOC_ARRAY(pdata->delta_size, pdata->nr_alloc); |
| 183 | |
| 184 | if (pdata->tree_depth) |
| 185 | REALLOC_ARRAY(pdata->tree_depth, pdata->nr_alloc); |
| 186 | |
| 187 | if (pdata->layer) |
| 188 | REALLOC_ARRAY(pdata->layer, pdata->nr_alloc); |
| 189 | |
| 190 | if (pdata->cruft_mtime) |
| 191 | REALLOC_ARRAY(pdata->cruft_mtime, pdata->nr_alloc); |
| 192 | } |
| 193 | |
| 194 | new_entry = pdata->objects + pdata->nr_objects++; |
| 195 | |
| 196 | memset(new_entry, 0, sizeof(*new_entry)); |
| 197 | oidcpy(&new_entry->idx.oid, oid); |
| 198 | |
| 199 | if (pdata->index_size * 3 <= pdata->nr_objects * 4) |
| 200 | rehash_objects(pdata); |
| 201 | else { |
| 202 | int found; |
| 203 | uint32_t pos = locate_object_entry_hash(pdata, |
| 204 | &new_entry->idx.oid, |
| 205 | &found); |
| 206 | if (found) |
| 207 | BUG("duplicate object inserted into hash"); |
| 208 | pdata->index[pos] = pdata->nr_objects; |
| 209 | } |
| 210 | |
| 211 | if (pdata->in_pack) |
| 212 | pdata->in_pack[pdata->nr_objects - 1] = NULL; |
| 213 | |
| 214 | if (pdata->tree_depth) |
| 215 | pdata->tree_depth[pdata->nr_objects - 1] = 0; |
| 216 | |
| 217 | if (pdata->layer) |
| 218 | pdata->layer[pdata->nr_objects - 1] = 0; |
| 219 | |
| 220 | if (pdata->cruft_mtime) |
| 221 | pdata->cruft_mtime[pdata->nr_objects - 1] = 0; |
| 222 | |
| 223 | return new_entry; |
| 224 | } |
| 225 | |
| 226 | void oe_set_delta_ext(struct packing_data *pdata, |
| 227 | struct object_entry *delta, |
| 228 | const struct object_id *oid) |
| 229 | { |
| 230 | struct object_entry *base; |
| 231 | |
| 232 | ALLOC_GROW(pdata->ext_bases, pdata->nr_ext + 1, pdata->alloc_ext); |
| 233 | base = &pdata->ext_bases[pdata->nr_ext++]; |
| 234 | memset(base, 0, sizeof(*base)); |
| 235 | oidcpy(&base->idx.oid, oid); |
| 236 | |
| 237 | /* These flags mark that we are not part of the actual pack output. */ |
| 238 | base->preferred_base = 1; |
| 239 | base->filled = 1; |
| 240 | |
| 241 | delta->ext_base = 1; |
| 242 | delta->delta_idx = base - pdata->ext_bases + 1; |
| 243 | } |