1 /*
2  * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 struct got_delta_cache_entry {
18 	off_t data_offset;
19 	uint8_t *delta_buf;
20 	size_t delta_len;
21 };
22 
23 #define GOT_DELTA_CACHE_SIZE	1024
24 
25 struct got_delta_cache {
26 	int nentries;
27 	struct got_delta_cache_entry deltas[GOT_DELTA_CACHE_SIZE];
28 };
29 
30 /* A pack file segment mapped with mmap(2). */
31 struct got_pack_mapping {
32 	TAILQ_ENTRY(got_pack_mapping) entry;
33 	int fd;
34 	uint8_t *addr;
35 	off_t offset;
36 	size_t len;
37 };
38 
39 #define GOT_PACK_MAX_OPEN_MAPPINGS	512
40 #define GOT_PACK_MAPPING_MIN_SIZE	8192
41 #define GOT_PACK_MAPPING_MAX_SIZE	(2048 * GOT_PACK_MAPPING_MIN_SIZE)
42 
43 /* An open pack file. */
44 struct got_pack {
45 	char *path_packfile;
46 	FILE *packfile;
47 	size_t filesize;
48 	int nmappings;
49 
50 	TAILQ_HEAD(, got_pack_mapping) mappings;
51 
52 	struct got_delta_cache delta_cache;
53 };
54 
55 const struct got_error *got_pack_close(struct got_pack *);
56 
57 /* See Documentation/technical/pack-format.txt in Git. */
58 
59 struct got_packidx_trailer {
60 	u_int8_t	packfile_sha1[SHA1_DIGEST_LENGTH];
61 	u_int8_t	packidx_sha1[SHA1_DIGEST_LENGTH];
62 } __attribute__((__packed__));
63 
64 /* Ignore pack index version 1 which is no longer written by Git. */
65 #define GOT_PACKIDX_VERSION 2
66 
67 struct got_packidx_v2_hdr {
68 	uint32_t	magic;		/* big endian */
69 #define GOT_PACKIDX_V2_MAGIC 0xff744f63	/* "\377t0c" */
70 	uint32_t	version;
71 
72 	/* 
73 	 * Each entry N in the fanout table contains the number of objects in
74 	 * the packfile whose SHA1 begins with a byte less than or equal to N.
75 	 * The last entry (index 255) contains the number of objects in the
76 	 * pack file whose first SHA1 byte is <= 0xff, and thus records the
77 	 * total number of objects in the pack file. All pointer variables
78 	 * below point to tables with a corresponding number of entries.
79 	 */
80 	uint32_t	fanout_table[0xff + 1];	/* values are big endian */
81 
82 	/* Sorted SHA1 checksums for each object in the pack file. */
83 	struct got_object_id *sorted_ids;
84 
85 	/* CRC32 of the packed representation of each object. */
86 	uint32_t	*crc32;
87 
88 	/* Offset into the pack file for each object. */
89 	uint32_t	*offsets;		/* values are big endian */
90 #define GOT_PACKIDX_OFFSET_VAL_MASK		0x7fffffff
91 #define GOT_PACKIDX_OFFSET_VAL_IS_LARGE_IDX	0x80000000
92 
93 	/* Large offsets table is empty for pack files < 2 GB. */
94 	uint64_t	*large_offsets;		/* values are big endian */
95 
96 	struct got_packidx_trailer trailer;
97 };
98 
99 struct got_packfile_hdr {
100 	uint32_t	signature;
101 #define GOT_PACKFILE_SIGNATURE	0x5041434b	/* 'P' 'A' 'C' 'K' */
102 	uint32_t	version;	/* big endian */
103 #define GOT_PACKFILE_VERSION 2
104 	uint32_t	nobjects;	/* big endian */
105 };
106 
107 struct got_packfile_obj_hdr {
108 	/* 
109 	 * The object size field uses a variable length encoding:
110 	 * size0...sizeN form a 4+7+7+...+7 bit integer, where size0 is the
111 	 * least significant part and sizeN is the most significant part.
112 	 * If the MSB of a size byte is set, an additional size byte follows.
113 	 * Of the 7 remaining bits of size0, the first 3 bits indicate the
114 	 * object's type, and the remaining 4 bits contribute to the size.
115 	 */
116 	uint8_t *size;		/* variable length */
117 #define GOT_PACK_OBJ_SIZE_MORE		0x80
118 #define GOT_PACK_OBJ_SIZE0_TYPE_MASK	0x70 /* See struct got_object->type */
119 #define GOT_PACK_OBJ_SIZE0_TYPE_MASK_SHIFT	4
120 #define GOT_PACK_OBJ_SIZE0_VAL_MASK	0x0f
121 #define GOT_PACK_OBJ_SIZE_VAL_MASK	0x7f
122 };
123 
124 /* If object is not a DELTA type. */
125 struct got_packfile_object_data {
126 	uint8_t *data;	/* compressed */
127 };
128 
129 /* If object is of type	GOT_OBJ_TYPE_REF_DELTA. */
130 struct got_packfile_object_data_ref_delta {
131 	uint8_t sha1[SHA1_DIGEST_LENGTH];
132 	uint8_t *delta_data;		/* compressed */
133 };
134 
135 /* If object is of type GOT_OBJ_TYPE_OFFSET_DELTA. */
136 struct got_packfile_object_data_offset_delta {
137 	/* 
138 	 * This offset is interpreted as a negative offset from
139 	 * the got_packfile_obj_hdr corresponding to this object.
140 	 * The size provided in the header specifies the amount
141 	 * of compressed delta data that follows.
142 	 *
143 	 * This field uses a variable length encoding of N bytes,
144 	 * where the MSB is always set except for the last byte.
145 	 * The value is encoded as a series of N 7 bit integers,
146 	 * which are concatenated, and if N > 1 the value 2^7 +
147 	 * 2^14 + ... + 2^(7 * (n-1)) is added to the result.
148 	 */
149 	uint8_t *offset;	/* variable length */
150 #define GOT_PACK_OBJ_DELTA_OFF_MORE		0x80
151 #define GOT_PACK_OBJ_DELTA_OFF_VAL_MASK		0x7f
152 	uint8_t *delta_data;		/* compressed */
153 };
154 
155 struct got_packfile_obj_data {
156 	union {
157 		struct got_packfile_object_data data;
158 		struct got_packfile_object_data_ref_delta ref_delta;
159 		struct got_packfile_object_data_offset_delta offset_delta;
160 	} __attribute__((__packed__));
161 } __attribute__((__packed__));
162 
163 const struct got_error *got_packidx_open(struct got_packidx_v2_hdr **,
164     const char *);
165 void got_packidx_close(struct got_packidx_v2_hdr *);
166 
167 const struct got_error *got_packfile_open_object(struct got_object **,
168     struct got_object_id *, struct got_repository *);
169 const struct got_error *got_packfile_extract_object(FILE **,
170     struct got_object *, struct got_repository *);
171 const struct got_error *got_packfile_extract_object_to_mem(uint8_t **, size_t *,
172     struct got_object *, struct got_repository *);