1#ifndef PACK_OBJECTS_H 2#define PACK_OBJECTS_H 3 4#include"object-store.h" 5#include"thread-utils.h" 6 7#define OE_DFS_STATE_BITS 2 8#define OE_DEPTH_BITS 12 9#define OE_IN_PACK_BITS 10 10#define OE_Z_DELTA_BITS 20 11/* 12 * Note that oe_set_size() becomes expensive when the given size is 13 * above this limit. Don't lower it too much. 14 */ 15#define OE_SIZE_BITS 31 16#define OE_DELTA_SIZE_BITS 23 17 18/* 19 * State flags for depth-first search used for analyzing delta cycles. 20 * 21 * The depth is measured in delta-links to the base (so if A is a delta 22 * against B, then A has a depth of 1, and B a depth of 0). 23 */ 24enum dfs_state { 25 DFS_NONE =0, 26 DFS_ACTIVE, 27 DFS_DONE, 28 DFS_NUM_STATES 29}; 30 31/* 32 * The size of struct nearly determines pack-objects's memory 33 * consumption. This struct is packed tight for that reason. When you 34 * add or reorder something in this struct, think a bit about this. 35 * 36 * basic object info 37 * ----------------- 38 * idx.oid is filled up before delta searching starts. idx.crc32 is 39 * only valid after the object is written out and will be used for 40 * generating the index. idx.offset will be both gradually set and 41 * used in writing phase (base objects get offset first, then deltas 42 * refer to them) 43 * 44 * "size" is the uncompressed object size. Compressed size of the raw 45 * data for an object in a pack is not stored anywhere but is computed 46 * and made available when reverse .idx is made. Note that when a 47 * delta is reused, "size" is the uncompressed _delta_ size, not the 48 * canonical one after the delta has been applied. 49 * 50 * "hash" contains a path name hash which is used for sorting the 51 * delta list and also during delta searching. Once prepare_pack() 52 * returns it's no longer needed. 53 * 54 * source pack info 55 * ---------------- 56 * The (in_pack, in_pack_offset) tuple contains the location of the 57 * object in the source pack. in_pack_header_size allows quickly 58 * skipping the header and going straight to the zlib stream. 59 * 60 * "type" and "in_pack_type" both describe object type. in_pack_type 61 * may contain a delta type, while type is always the canonical type. 62 * 63 * deltas 64 * ------ 65 * Delta links (delta, delta_child and delta_sibling) are created to 66 * reflect that delta graph from the source pack then updated or added 67 * during delta searching phase when we find better deltas. 68 * 69 * delta_child and delta_sibling are last needed in 70 * compute_write_order(). "delta" and "delta_size" must remain valid 71 * at object writing phase in case the delta is not cached. 72 * 73 * If a delta is cached in memory and is compressed, delta_data points 74 * to the data and z_delta_size contains the compressed size. If it's 75 * uncompressed [1], z_delta_size must be zero. delta_size is always 76 * the uncompressed size and must be valid even if the delta is not 77 * cached. 78 * 79 * [1] during try_delta phase we don't bother with compressing because 80 * the delta could be quickly replaced with a better one. 81 */ 82struct object_entry { 83struct pack_idx_entry idx; 84void*delta_data;/* cached delta (uncompressed) */ 85 off_t in_pack_offset; 86uint32_t hash;/* name hint hash */ 87unsigned size_:OE_SIZE_BITS; 88unsigned size_valid:1; 89uint32_t delta_idx;/* delta base object */ 90uint32_t delta_child_idx;/* deltified objects who bases me */ 91uint32_t delta_sibling_idx;/* other deltified objects who 92 * uses the same base as me 93 */ 94unsigned delta_size_:OE_DELTA_SIZE_BITS;/* delta data size (uncompressed) */ 95unsigned delta_size_valid:1; 96unsigned char in_pack_header_size; 97unsigned in_pack_idx:OE_IN_PACK_BITS;/* already in pack */ 98unsigned z_delta_size:OE_Z_DELTA_BITS; 99unsigned type_valid:1; 100unsigned no_try_delta:1; 101unsigned type_:TYPE_BITS; 102unsigned in_pack_type:TYPE_BITS;/* could be delta */ 103unsigned preferred_base:1;/* 104 * we do not pack this, but is available 105 * to be used as the base object to delta 106 * objects against. 107 */ 108unsigned tagged:1;/* near the very tip of refs */ 109unsigned filled:1;/* assigned write-order */ 110unsigned dfs_state:OE_DFS_STATE_BITS; 111unsigned depth:OE_DEPTH_BITS; 112 113/* 114 * pahole results on 64-bit linux (gcc and clang) 115 * 116 * size: 80, bit_padding: 9 bits 117 * 118 * and on 32-bit (gcc) 119 * 120 * size: 76, bit_padding: 9 bits 121 */ 122}; 123 124struct packing_data { 125struct object_entry *objects; 126uint32_t nr_objects, nr_alloc; 127 128int32_t*index; 129uint32_t index_size; 130 131unsigned int*in_pack_pos; 132unsigned long*delta_size; 133 134/* 135 * Only one of these can be non-NULL and they have different 136 * sizes. if in_pack_by_idx is allocated, oe_in_pack() returns 137 * the pack of an object using in_pack_idx field. If not, 138 * in_pack[] array is used the same way as in_pack_pos[] 139 */ 140struct packed_git **in_pack_by_idx; 141struct packed_git **in_pack; 142 143#ifndef NO_PTHREADS 144 pthread_mutex_t lock; 145#endif 146 147uintmax_t oe_size_limit; 148uintmax_t oe_delta_size_limit; 149}; 150 151voidprepare_packing_data(struct packing_data *pdata); 152 153staticinlinevoidpacking_data_lock(struct packing_data *pdata) 154{ 155#ifndef NO_PTHREADS 156pthread_mutex_lock(&pdata->lock); 157#endif 158} 159staticinlinevoidpacking_data_unlock(struct packing_data *pdata) 160{ 161#ifndef NO_PTHREADS 162pthread_mutex_unlock(&pdata->lock); 163#endif 164} 165 166struct object_entry *packlist_alloc(struct packing_data *pdata, 167const unsigned char*sha1, 168uint32_t index_pos); 169 170struct object_entry *packlist_find(struct packing_data *pdata, 171const unsigned char*sha1, 172uint32_t*index_pos); 173 174staticinlineuint32_tpack_name_hash(const char*name) 175{ 176uint32_t c, hash =0; 177 178if(!name) 179return0; 180 181/* 182 * This effectively just creates a sortable number from the 183 * last sixteen non-whitespace characters. Last characters 184 * count "most", so things that end in ".c" sort together. 185 */ 186while((c = *name++) !=0) { 187if(isspace(c)) 188continue; 189 hash = (hash >>2) + (c <<24); 190} 191return hash; 192} 193 194staticinlineenum object_type oe_type(const struct object_entry *e) 195{ 196return e->type_valid ? e->type_ : OBJ_BAD; 197} 198 199staticinlinevoidoe_set_type(struct object_entry *e, 200enum object_type type) 201{ 202if(type >= OBJ_ANY) 203BUG("OBJ_ANY cannot be set in pack-objects code"); 204 205 e->type_valid = type >= OBJ_NONE; 206 e->type_ = (unsigned)type; 207} 208 209staticinlineunsigned intoe_in_pack_pos(const struct packing_data *pack, 210const struct object_entry *e) 211{ 212return pack->in_pack_pos[e - pack->objects]; 213} 214 215staticinlinevoidoe_set_in_pack_pos(const struct packing_data *pack, 216const struct object_entry *e, 217unsigned int pos) 218{ 219 pack->in_pack_pos[e - pack->objects] = pos; 220} 221 222staticinlinestruct packed_git *oe_in_pack(const struct packing_data *pack, 223const struct object_entry *e) 224{ 225if(pack->in_pack_by_idx) 226return pack->in_pack_by_idx[e->in_pack_idx]; 227else 228return pack->in_pack[e - pack->objects]; 229} 230 231voidoe_map_new_pack(struct packing_data *pack, 232struct packed_git *p); 233staticinlinevoidoe_set_in_pack(struct packing_data *pack, 234struct object_entry *e, 235struct packed_git *p) 236{ 237if(!p->index) 238oe_map_new_pack(pack, p); 239if(pack->in_pack_by_idx) 240 e->in_pack_idx = p->index; 241else 242 pack->in_pack[e - pack->objects] = p; 243} 244 245staticinlinestruct object_entry *oe_delta( 246const struct packing_data *pack, 247const struct object_entry *e) 248{ 249if(e->delta_idx) 250return&pack->objects[e->delta_idx -1]; 251return NULL; 252} 253 254staticinlinevoidoe_set_delta(struct packing_data *pack, 255struct object_entry *e, 256struct object_entry *delta) 257{ 258if(delta) 259 e->delta_idx = (delta - pack->objects) +1; 260else 261 e->delta_idx =0; 262} 263 264staticinlinestruct object_entry *oe_delta_child( 265const struct packing_data *pack, 266const struct object_entry *e) 267{ 268if(e->delta_child_idx) 269return&pack->objects[e->delta_child_idx -1]; 270return NULL; 271} 272 273staticinlinevoidoe_set_delta_child(struct packing_data *pack, 274struct object_entry *e, 275struct object_entry *delta) 276{ 277if(delta) 278 e->delta_child_idx = (delta - pack->objects) +1; 279else 280 e->delta_child_idx =0; 281} 282 283staticinlinestruct object_entry *oe_delta_sibling( 284const struct packing_data *pack, 285const struct object_entry *e) 286{ 287if(e->delta_sibling_idx) 288return&pack->objects[e->delta_sibling_idx -1]; 289return NULL; 290} 291 292staticinlinevoidoe_set_delta_sibling(struct packing_data *pack, 293struct object_entry *e, 294struct object_entry *delta) 295{ 296if(delta) 297 e->delta_sibling_idx = (delta - pack->objects) +1; 298else 299 e->delta_sibling_idx =0; 300} 301 302unsigned longoe_get_size_slow(struct packing_data *pack, 303const struct object_entry *e); 304staticinlineunsigned longoe_size(struct packing_data *pack, 305const struct object_entry *e) 306{ 307if(e->size_valid) 308return e->size_; 309 310returnoe_get_size_slow(pack, e); 311} 312 313staticinlineintoe_size_less_than(struct packing_data *pack, 314const struct object_entry *lhs, 315unsigned long rhs) 316{ 317if(lhs->size_valid) 318return lhs->size_ < rhs; 319if(rhs < pack->oe_size_limit)/* rhs < 2^x <= lhs ? */ 320return0; 321returnoe_get_size_slow(pack, lhs) < rhs; 322} 323 324staticinlineintoe_size_greater_than(struct packing_data *pack, 325const struct object_entry *lhs, 326unsigned long rhs) 327{ 328if(lhs->size_valid) 329return lhs->size_ > rhs; 330if(rhs < pack->oe_size_limit)/* rhs < 2^x <= lhs ? */ 331return1; 332returnoe_get_size_slow(pack, lhs) > rhs; 333} 334 335staticinlinevoidoe_set_size(struct packing_data *pack, 336struct object_entry *e, 337unsigned long size) 338{ 339if(size < pack->oe_size_limit) { 340 e->size_ = size; 341 e->size_valid =1; 342}else{ 343 e->size_valid =0; 344if(oe_get_size_slow(pack, e) != size) 345BUG("'size' is supposed to be the object size!"); 346} 347} 348 349staticinlineunsigned longoe_delta_size(struct packing_data *pack, 350const struct object_entry *e) 351{ 352if(e->delta_size_valid) 353return e->delta_size_; 354 355/* 356 * pack->detla_size[] can't be NULL because oe_set_delta_size() 357 * must have been called when a new delta is saved with 358 * oe_set_delta(). 359 * If oe_delta() returns NULL (i.e. default state, which means 360 * delta_size_valid is also false), then the caller must never 361 * call oe_delta_size(). 362 */ 363return pack->delta_size[e - pack->objects]; 364} 365 366staticinlinevoidoe_set_delta_size(struct packing_data *pack, 367struct object_entry *e, 368unsigned long size) 369{ 370if(size < pack->oe_delta_size_limit) { 371 e->delta_size_ = size; 372 e->delta_size_valid =1; 373}else{ 374packing_data_lock(pack); 375if(!pack->delta_size) 376ALLOC_ARRAY(pack->delta_size, pack->nr_alloc); 377packing_data_unlock(pack); 378 379 pack->delta_size[e - pack->objects] = size; 380 e->delta_size_valid =0; 381} 382} 383 384#endif