pack-objects.h

   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  */
  24 enum 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  */
  82 struct object_entry {
  83         struct pack_idx_entry idx;
  84         void *delta_data;       /* cached delta (uncompressed) */
  85         off_t in_pack_offset;
  86         uint32_t hash;                  /* name hint hash */
  87         unsigned size_:OE_SIZE_BITS;
  88         unsigned size_valid:1;
  89         uint32_t delta_idx;     /* delta base object */
  90         uint32_t delta_child_idx; /* deltified objects who bases me */
  91         uint32_t delta_sibling_idx; /* other deltified objects who
  92                                      * uses the same base as me
  93                                      */
  94         unsigned delta_size_:OE_DELTA_SIZE_BITS; /* delta data size (uncompressed) */
  95         unsigned delta_size_valid:1;
  96         unsigned char in_pack_header_size;
  97         unsigned in_pack_idx:OE_IN_PACK_BITS;   /* already in pack */
  98         unsigned z_delta_size:OE_Z_DELTA_BITS;
  99         unsigned type_valid:1;
 100         unsigned no_try_delta:1;
 101         unsigned type_:TYPE_BITS;
 102         unsigned in_pack_type:TYPE_BITS; /* could be delta */
 103         unsigned 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                                     */
 108         unsigned tagged:1; /* near the very tip of refs */
 109         unsigned filled:1; /* assigned write-order */
 110         unsigned dfs_state:OE_DFS_STATE_BITS;
 111         unsigned 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
 124 struct packing_data {
 125         struct object_entry *objects;
 126         uint32_t nr_objects, nr_alloc;
 127
 128         int32_t *index;
 129         uint32_t index_size;
 130
 131         unsigned int *in_pack_pos;
 132         unsigned 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          */
 140         struct packed_git **in_pack_by_idx;
 141         struct packed_git **in_pack;
 142
 143 #ifndef NO_PTHREADS
 144         pthread_mutex_t lock;
 145 #endif
 146
 147         uintmax_t oe_size_limit;
 148         uintmax_t oe_delta_size_limit;
 149 };
 150
 151 void prepare_packing_data(struct packing_data *pdata);
 152
 153 static inline void packing_data_lock(struct packing_data *pdata)
 154 {
 155 #ifndef NO_PTHREADS
 156         pthread_mutex_lock(&pdata->lock);
 157 #endif
 158 }
 159 static inline void packing_data_unlock(struct packing_data *pdata)
 160 {
 161 #ifndef NO_PTHREADS
 162         pthread_mutex_unlock(&pdata->lock);
 163 #endif
 164 }
 165
 166 struct object_entry *packlist_alloc(struct packing_data *pdata,
 167                                     const unsigned char *sha1,
 168                                     uint32_t index_pos);
 169
 170 struct object_entry *packlist_find(struct packing_data *pdata,
 171                                    const unsigned char *sha1,
 172                                    uint32_t *index_pos);
 173
 174 static inline uint32_t pack_name_hash(const char *name)
 175 {
 176         uint32_t c, hash = 0;
 177
 178         if (!name)
 179                 return 0;
 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          */
 186         while ((c = *name++) != 0) {
 187                 if (isspace(c))
 188                         continue;
 189                 hash = (hash >> 2) + (c << 24);
 190         }
 191         return hash;
 192 }
 193
 194 static inline enum object_type oe_type(const struct object_entry *e)
 195 {
 196         return e->type_valid ? e->type_ : OBJ_BAD;
 197 }
 198
 199 static inline void oe_set_type(struct object_entry *e,
 200                                enum object_type type)
 201 {
 202         if (type >= OBJ_ANY)
 203                 BUG("OBJ_ANY cannot be set in pack-objects code");
 204
 205         e->type_valid = type >= OBJ_NONE;
 206         e->type_ = (unsigned)type;
 207 }
 208
 209 static inline unsigned int oe_in_pack_pos(const struct packing_data *pack,
 210                                           const struct object_entry *e)
 211 {
 212         return pack->in_pack_pos[e - pack->objects];
 213 }
 214
 215 static inline void oe_set_in_pack_pos(const struct packing_data *pack,
 216                                       const struct object_entry *e,
 217                                       unsigned int pos)
 218 {
 219         pack->in_pack_pos[e - pack->objects] = pos;
 220 }
 221
 222 static inline struct packed_git *oe_in_pack(const struct packing_data *pack,
 223                                             const struct object_entry *e)
 224 {
 225         if (pack->in_pack_by_idx)
 226                 return pack->in_pack_by_idx[e->in_pack_idx];
 227         else
 228                 return pack->in_pack[e - pack->objects];
 229 }
 230
 231 void oe_map_new_pack(struct packing_data *pack,
 232                      struct packed_git *p);
 233 static inline void oe_set_in_pack(struct packing_data *pack,
 234                                   struct object_entry *e,
 235                                   struct packed_git *p)
 236 {
 237         if (!p->index)
 238                 oe_map_new_pack(pack, p);
 239         if (pack->in_pack_by_idx)
 240                 e->in_pack_idx = p->index;
 241         else
 242                 pack->in_pack[e - pack->objects] = p;
 243 }
 244
 245 static inline struct object_entry *oe_delta(
 246                 const struct packing_data *pack,
 247                 const struct object_entry *e)
 248 {
 249         if (e->delta_idx)
 250                 return &pack->objects[e->delta_idx - 1];
 251         return NULL;
 252 }
 253
 254 static inline void oe_set_delta(struct packing_data *pack,
 255                                 struct object_entry *e,
 256                                 struct object_entry *delta)
 257 {
 258         if (delta)
 259                 e->delta_idx = (delta - pack->objects) + 1;
 260         else
 261                 e->delta_idx = 0;
 262 }
 263
 264 static inline struct object_entry *oe_delta_child(
 265                 const struct packing_data *pack,
 266                 const struct object_entry *e)
 267 {
 268         if (e->delta_child_idx)
 269                 return &pack->objects[e->delta_child_idx - 1];
 270         return NULL;
 271 }
 272
 273 static inline void oe_set_delta_child(struct packing_data *pack,
 274                                       struct object_entry *e,
 275                                       struct object_entry *delta)
 276 {
 277         if (delta)
 278                 e->delta_child_idx = (delta - pack->objects) + 1;
 279         else
 280                 e->delta_child_idx = 0;
 281 }
 282
 283 static inline struct object_entry *oe_delta_sibling(
 284                 const struct packing_data *pack,
 285                 const struct object_entry *e)
 286 {
 287         if (e->delta_sibling_idx)
 288                 return &pack->objects[e->delta_sibling_idx - 1];
 289         return NULL;
 290 }
 291
 292 static inline void oe_set_delta_sibling(struct packing_data *pack,
 293                                         struct object_entry *e,
 294                                         struct object_entry *delta)
 295 {
 296         if (delta)
 297                 e->delta_sibling_idx = (delta - pack->objects) + 1;
 298         else
 299                 e->delta_sibling_idx = 0;
 300 }
 301
 302 unsigned long oe_get_size_slow(struct packing_data *pack,
 303                                const struct object_entry *e);
 304 static inline unsigned long oe_size(struct packing_data *pack,
 305                                     const struct object_entry *e)
 306 {
 307         if (e->size_valid)
 308                 return e->size_;
 309
 310         return oe_get_size_slow(pack, e);
 311 }
 312
 313 static inline int oe_size_less_than(struct packing_data *pack,
 314                                     const struct object_entry *lhs,
 315                                     unsigned long rhs)
 316 {
 317         if (lhs->size_valid)
 318                 return lhs->size_ < rhs;
 319         if (rhs < pack->oe_size_limit) /* rhs < 2^x <= lhs ? */
 320                 return 0;
 321         return oe_get_size_slow(pack, lhs) < rhs;
 322 }
 323
 324 static inline int oe_size_greater_than(struct packing_data *pack,
 325                                        const struct object_entry *lhs,
 326                                        unsigned long rhs)
 327 {
 328         if (lhs->size_valid)
 329                 return lhs->size_ > rhs;
 330         if (rhs < pack->oe_size_limit) /* rhs < 2^x <= lhs ? */
 331                 return 1;
 332         return oe_get_size_slow(pack, lhs) > rhs;
 333 }
 334
 335 static inline void oe_set_size(struct packing_data *pack,
 336                                struct object_entry *e,
 337                                unsigned long size)
 338 {
 339         if (size < pack->oe_size_limit) {
 340                 e->size_ = size;
 341                 e->size_valid = 1;
 342         } else {
 343                 e->size_valid = 0;
 344                 if (oe_get_size_slow(pack, e) != size)
 345                         BUG("'size' is supposed to be the object size!");
 346         }
 347 }
 348
 349 static inline unsigned long oe_delta_size(struct packing_data *pack,
 350                                           const struct object_entry *e)
 351 {
 352         if (e->delta_size_valid)
 353                 return 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          */
 363         return pack->delta_size[e - pack->objects];
 364 }
 365
 366 static inline void oe_set_delta_size(struct packing_data *pack,
 367                                      struct object_entry *e,
 368                                      unsigned long size)
 369 {
 370         if (size < pack->oe_delta_size_limit) {
 371                 e->delta_size_ = size;
 372                 e->delta_size_valid = 1;
 373         } else {
 374                 packing_data_lock(pack);
 375                 if (!pack->delta_size)
 376                         ALLOC_ARRAY(pack->delta_size, pack->nr_alloc);
 377                 packing_data_unlock(pack);
 378
 379                 pack->delta_size[e - pack->objects] = size;
 380                 e->delta_size_valid = 0;
 381         }
 382 }
 383
 384 #endif