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