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 preferred_base:1;/* 105 * we do not pack this, but is available 106 * to be used as the base object to delta 107 * objects against. 108 */ 109unsigned tagged:1;/* near the very tip of refs */ 110unsigned filled:1;/* assigned write-order */ 111unsigned dfs_state:OE_DFS_STATE_BITS; 112unsigned char in_pack_header_size; 113unsigned depth:OE_DEPTH_BITS; 114 115/* 116 * pahole results on 64-bit linux (gcc and clang) 117 * 118 * size: 80, bit_padding: 20 bits, holes: 8 bits 119 * 120 * and on 32-bit (gcc) 121 * 122 * size: 76, bit_padding: 20 bits, holes: 8 bits 123 */ 124}; 125 126struct packing_data { 127struct object_entry *objects; 128uint32_t nr_objects, nr_alloc; 129 130int32_t*index; 131uint32_t index_size; 132 133unsigned int*in_pack_pos; 134 135/* 136 * Only one of these can be non-NULL and they have different 137 * sizes. if in_pack_by_idx is allocated, oe_in_pack() returns 138 * the pack of an object using in_pack_idx field. If not, 139 * in_pack[] array is used the same way as in_pack_pos[] 140 */ 141struct packed_git **in_pack_by_idx; 142struct packed_git **in_pack; 143 144uintmax_t oe_size_limit; 145 146/* delta islands */ 147unsigned int*tree_depth; 148unsigned char*layer; 149}; 150 151voidprepare_packing_data(struct packing_data *pdata); 152struct object_entry *packlist_alloc(struct packing_data *pdata, 153const unsigned char*sha1, 154uint32_t index_pos); 155 156struct object_entry *packlist_find(struct packing_data *pdata, 157const unsigned char*sha1, 158uint32_t*index_pos); 159 160staticinlineuint32_tpack_name_hash(const char*name) 161{ 162uint32_t c, hash =0; 163 164if(!name) 165return0; 166 167/* 168 * This effectively just creates a sortable number from the 169 * last sixteen non-whitespace characters. Last characters 170 * count "most", so things that end in ".c" sort together. 171 */ 172while((c = *name++) !=0) { 173if(isspace(c)) 174continue; 175 hash = (hash >>2) + (c <<24); 176} 177return hash; 178} 179 180staticinlineenum object_type oe_type(const struct object_entry *e) 181{ 182return e->type_valid ? e->type_ : OBJ_BAD; 183} 184 185staticinlinevoidoe_set_type(struct object_entry *e, 186enum object_type type) 187{ 188if(type >= OBJ_ANY) 189BUG("OBJ_ANY cannot be set in pack-objects code"); 190 191 e->type_valid = type >= OBJ_NONE; 192 e->type_ = (unsigned)type; 193} 194 195staticinlineunsigned intoe_in_pack_pos(const struct packing_data *pack, 196const struct object_entry *e) 197{ 198return pack->in_pack_pos[e - pack->objects]; 199} 200 201staticinlinevoidoe_set_in_pack_pos(const struct packing_data *pack, 202const struct object_entry *e, 203unsigned int pos) 204{ 205 pack->in_pack_pos[e - pack->objects] = pos; 206} 207 208staticinlinestruct packed_git *oe_in_pack(const struct packing_data *pack, 209const struct object_entry *e) 210{ 211if(pack->in_pack_by_idx) 212return pack->in_pack_by_idx[e->in_pack_idx]; 213else 214return pack->in_pack[e - pack->objects]; 215} 216 217voidoe_map_new_pack(struct packing_data *pack, 218struct packed_git *p); 219staticinlinevoidoe_set_in_pack(struct packing_data *pack, 220struct object_entry *e, 221struct packed_git *p) 222{ 223if(!p->index) 224oe_map_new_pack(pack, p); 225if(pack->in_pack_by_idx) 226 e->in_pack_idx = p->index; 227else 228 pack->in_pack[e - pack->objects] = p; 229} 230 231staticinlinestruct object_entry *oe_delta( 232const struct packing_data *pack, 233const struct object_entry *e) 234{ 235if(e->delta_idx) 236return&pack->objects[e->delta_idx -1]; 237return NULL; 238} 239 240staticinlinevoidoe_set_delta(struct packing_data *pack, 241struct object_entry *e, 242struct object_entry *delta) 243{ 244if(delta) 245 e->delta_idx = (delta - pack->objects) +1; 246else 247 e->delta_idx =0; 248} 249 250staticinlinestruct object_entry *oe_delta_child( 251const struct packing_data *pack, 252const struct object_entry *e) 253{ 254if(e->delta_child_idx) 255return&pack->objects[e->delta_child_idx -1]; 256return NULL; 257} 258 259staticinlinevoidoe_set_delta_child(struct packing_data *pack, 260struct object_entry *e, 261struct object_entry *delta) 262{ 263if(delta) 264 e->delta_child_idx = (delta - pack->objects) +1; 265else 266 e->delta_child_idx =0; 267} 268 269staticinlinestruct object_entry *oe_delta_sibling( 270const struct packing_data *pack, 271const struct object_entry *e) 272{ 273if(e->delta_sibling_idx) 274return&pack->objects[e->delta_sibling_idx -1]; 275return NULL; 276} 277 278staticinlinevoidoe_set_delta_sibling(struct packing_data *pack, 279struct object_entry *e, 280struct object_entry *delta) 281{ 282if(delta) 283 e->delta_sibling_idx = (delta - pack->objects) +1; 284else 285 e->delta_sibling_idx =0; 286} 287 288unsigned longoe_get_size_slow(struct packing_data *pack, 289const struct object_entry *e); 290staticinlineunsigned longoe_size(struct packing_data *pack, 291const struct object_entry *e) 292{ 293if(e->size_valid) 294return e->size_; 295 296returnoe_get_size_slow(pack, e); 297} 298 299staticinlineintoe_size_less_than(struct packing_data *pack, 300const struct object_entry *lhs, 301unsigned long rhs) 302{ 303if(lhs->size_valid) 304return lhs->size_ < rhs; 305if(rhs < pack->oe_size_limit)/* rhs < 2^x <= lhs ? */ 306return0; 307returnoe_get_size_slow(pack, lhs) < rhs; 308} 309 310staticinlineintoe_size_greater_than(struct packing_data *pack, 311const struct object_entry *lhs, 312unsigned long rhs) 313{ 314if(lhs->size_valid) 315return lhs->size_ > rhs; 316if(rhs < pack->oe_size_limit)/* rhs < 2^x <= lhs ? */ 317return1; 318returnoe_get_size_slow(pack, lhs) > rhs; 319} 320 321staticinlinevoidoe_set_size(struct packing_data *pack, 322struct object_entry *e, 323unsigned long size) 324{ 325if(size < pack->oe_size_limit) { 326 e->size_ = size; 327 e->size_valid =1; 328}else{ 329 e->size_valid =0; 330if(oe_get_size_slow(pack, e) != size) 331BUG("'size' is supposed to be the object size!"); 332} 333} 334 335staticinlineunsigned longoe_delta_size(struct packing_data *pack, 336const struct object_entry *e) 337{ 338if(e->delta_size_valid) 339return e->delta_size_; 340returnoe_size(pack, e); 341} 342 343staticinlinevoidoe_set_delta_size(struct packing_data *pack, 344struct object_entry *e, 345unsigned long size) 346{ 347 e->delta_size_ = size; 348 e->delta_size_valid = e->delta_size_ == size; 349if(!e->delta_size_valid && size !=oe_size(pack, e)) 350BUG("this can only happen in check_object() " 351"where delta size is the same as entry size"); 352} 353 354staticinlineunsigned intoe_tree_depth(struct packing_data *pack, 355struct object_entry *e) 356{ 357if(!pack->tree_depth) 358return0; 359return pack->tree_depth[e - pack->objects]; 360} 361 362staticinlinevoidoe_set_tree_depth(struct packing_data *pack, 363struct object_entry *e, 364unsigned int tree_depth) 365{ 366if(!pack->tree_depth) 367ALLOC_ARRAY(pack->tree_depth, pack->nr_alloc); 368 pack->tree_depth[e - pack->objects] = tree_depth; 369} 370 371staticinlineunsigned charoe_layer(struct packing_data *pack, 372struct object_entry *e) 373{ 374if(!pack->layer) 375return0; 376return pack->layer[e - pack->objects]; 377} 378 379staticinlinevoidoe_set_layer(struct packing_data *pack, 380struct object_entry *e, 381unsigned char layer) 382{ 383if(!pack->layer) 384ALLOC_ARRAY(pack->layer, pack->nr_alloc); 385 pack->layer[e - pack->objects] = layer; 386} 387 388#endif