1#include "cache.h" 2#include "pack-revindex.h" 3 4/* 5 * Pack index for existing packs give us easy access to the offsets into 6 * corresponding pack file where each object's data starts, but the entries 7 * do not store the size of the compressed representation (uncompressed 8 * size is easily available by examining the pack entry header). It is 9 * also rather expensive to find the sha1 for an object given its offset. 10 * 11 * We build a hashtable of existing packs (pack_revindex), and keep reverse 12 * index here -- pack index file is sorted by object name mapping to offset; 13 * this pack_revindex[].revindex array is a list of offset/index_nr pairs 14 * ordered by offset, so if you know the offset of an object, next offset 15 * is where its packed representation ends and the index_nr can be used to 16 * get the object sha1 from the main index. 17 */ 18 19struct pack_revindex { 20 struct packed_git *p; 21 struct revindex_entry *revindex; 22}; 23 24static struct pack_revindex *pack_revindex; 25static int pack_revindex_hashsz; 26 27static int pack_revindex_ix(struct packed_git *p) 28{ 29 unsigned long ui = (unsigned long)p; 30 int i; 31 32 ui = ui ^ (ui >> 16); /* defeat structure alignment */ 33 i = (int)(ui % pack_revindex_hashsz); 34 while (pack_revindex[i].p) { 35 if (pack_revindex[i].p == p) 36 return i; 37 if (++i == pack_revindex_hashsz) 38 i = 0; 39 } 40 return -1 - i; 41} 42 43static void init_pack_revindex(void) 44{ 45 int num; 46 struct packed_git *p; 47 48 for (num = 0, p = packed_git; p; p = p->next) 49 num++; 50 if (!num) 51 return; 52 pack_revindex_hashsz = num * 11; 53 pack_revindex = xcalloc(sizeof(*pack_revindex), pack_revindex_hashsz); 54 for (p = packed_git; p; p = p->next) { 55 num = pack_revindex_ix(p); 56 num = - 1 - num; 57 pack_revindex[num].p = p; 58 } 59 /* revindex elements are lazily initialized */ 60} 61 62/* 63 * This is a least-significant-digit radix sort. 64 * 65 * It sorts each of the "n" items in "entries" by its offset field. The "max" 66 * parameter must be at least as large as the largest offset in the array, 67 * and lets us quit the sort early. 68 */ 69static void sort_revindex(struct revindex_entry *entries, unsigned n, off_t max) 70{ 71 /* 72 * We use a "digit" size of 16 bits. That keeps our memory 73 * usage reasonable, and we can generally (for a 4G or smaller 74 * packfile) quit after two rounds of radix-sorting. 75 */ 76#define DIGIT_SIZE (16) 77#define BUCKETS (1 << DIGIT_SIZE) 78 /* 79 * We want to know the bucket that a[i] will go into when we are using 80 * the digit that is N bits from the (least significant) end. 81 */ 82#define BUCKET_FOR(a, i, bits) (((a)[(i)].offset >> (bits)) & (BUCKETS-1)) 83 84 /* 85 * We need O(n) temporary storage. Rather than do an extra copy of the 86 * partial results into "entries", we sort back and forth between the 87 * real array and temporary storage. In each iteration of the loop, we 88 * keep track of them with alias pointers, always sorting from "from" 89 * to "to". 90 */ 91 struct revindex_entry *tmp = xmalloc(n * sizeof(*tmp)); 92 struct revindex_entry *from = entries, *to = tmp; 93 int bits; 94 unsigned *pos = xmalloc(BUCKETS * sizeof(*pos)); 95 96 /* 97 * If (max >> bits) is zero, then we know that the radix digit we are 98 * on (and any higher) will be zero for all entries, and our loop will 99 * be a no-op, as everybody lands in the same zero-th bucket. 100 */ 101 for (bits = 0; max >> bits; bits += DIGIT_SIZE) { 102 struct revindex_entry *swap; 103 unsigned i; 104 105 memset(pos, 0, BUCKETS * sizeof(*pos)); 106 107 /* 108 * We want pos[i] to store the index of the last element that 109 * will go in bucket "i" (actually one past the last element). 110 * To do this, we first count the items that will go in each 111 * bucket, which gives us a relative offset from the last 112 * bucket. We can then cumulatively add the index from the 113 * previous bucket to get the true index. 114 */ 115 for (i = 0; i < n; i++) 116 pos[BUCKET_FOR(from, i, bits)]++; 117 for (i = 1; i < BUCKETS; i++) 118 pos[i] += pos[i-1]; 119 120 /* 121 * Now we can drop the elements into their correct buckets (in 122 * our temporary array). We iterate the pos counter backwards 123 * to avoid using an extra index to count up. And since we are 124 * going backwards there, we must also go backwards through the 125 * array itself, to keep the sort stable. 126 * 127 * Note that we use an unsigned iterator to make sure we can 128 * handle 2^32-1 objects, even on a 32-bit system. But this 129 * means we cannot use the more obvious "i >= 0" loop condition 130 * for counting backwards, and must instead check for 131 * wrap-around with UINT_MAX. 132 */ 133 for (i = n - 1; i != UINT_MAX; i--) 134 to[--pos[BUCKET_FOR(from, i, bits)]] = from[i]; 135 136 /* 137 * Now "to" contains the most sorted list, so we swap "from" and 138 * "to" for the next iteration. 139 */ 140 swap = from; 141 from = to; 142 to = swap; 143 } 144 145 /* 146 * If we ended with our data in the original array, great. If not, 147 * we have to move it back from the temporary storage. 148 */ 149 if (from != entries) 150 memcpy(entries, tmp, n * sizeof(*entries)); 151 free(tmp); 152 free(pos); 153 154#undef BUCKET_FOR 155#undef BUCKETS 156#undef DIGIT_SIZE 157} 158 159/* 160 * Ordered list of offsets of objects in the pack. 161 */ 162static void create_pack_revindex(struct pack_revindex *rix) 163{ 164 struct packed_git *p = rix->p; 165 unsigned num_ent = p->num_objects; 166 unsigned i; 167 const char *index = p->index_data; 168 169 rix->revindex = xmalloc(sizeof(*rix->revindex) * (num_ent + 1)); 170 index += 4 * 256; 171 172 if (p->index_version > 1) { 173 const uint32_t *off_32 = 174 (uint32_t *)(index + 8 + p->num_objects * (20 + 4)); 175 const uint32_t *off_64 = off_32 + p->num_objects; 176 for (i = 0; i < num_ent; i++) { 177 uint32_t off = ntohl(*off_32++); 178 if (!(off & 0x80000000)) { 179 rix->revindex[i].offset = off; 180 } else { 181 rix->revindex[i].offset = 182 ((uint64_t)ntohl(*off_64++)) << 32; 183 rix->revindex[i].offset |= 184 ntohl(*off_64++); 185 } 186 rix->revindex[i].nr = i; 187 } 188 } else { 189 for (i = 0; i < num_ent; i++) { 190 uint32_t hl = *((uint32_t *)(index + 24 * i)); 191 rix->revindex[i].offset = ntohl(hl); 192 rix->revindex[i].nr = i; 193 } 194 } 195 196 /* This knows the pack format -- the 20-byte trailer 197 * follows immediately after the last object data. 198 */ 199 rix->revindex[num_ent].offset = p->pack_size - 20; 200 rix->revindex[num_ent].nr = -1; 201 sort_revindex(rix->revindex, num_ent, p->pack_size); 202} 203 204struct revindex_entry *find_pack_revindex(struct packed_git *p, off_t ofs) 205{ 206 int num; 207 unsigned lo, hi; 208 struct pack_revindex *rix; 209 struct revindex_entry *revindex; 210 211 if (!pack_revindex_hashsz) 212 init_pack_revindex(); 213 num = pack_revindex_ix(p); 214 if (num < 0) 215 die("internal error: pack revindex fubar"); 216 217 rix = &pack_revindex[num]; 218 if (!rix->revindex) 219 create_pack_revindex(rix); 220 revindex = rix->revindex; 221 222 lo = 0; 223 hi = p->num_objects + 1; 224 do { 225 unsigned mi = lo + (hi - lo) / 2; 226 if (revindex[mi].offset == ofs) { 227 return revindex + mi; 228 } else if (ofs < revindex[mi].offset) 229 hi = mi; 230 else 231 lo = mi + 1; 232 } while (lo < hi); 233 error("bad offset for revindex"); 234 return NULL; 235} 236 237void discard_revindex(void) 238{ 239 if (pack_revindex_hashsz) { 240 int i; 241 for (i = 0; i < pack_revindex_hashsz; i++) 242 free(pack_revindex[i].revindex); 243 free(pack_revindex); 244 pack_revindex_hashsz = 0; 245 } 246}