1 /*
2  * Copyright (c) 2020 Ori Bernstein
3  * Copyright (c) 2021, 2022 Stefan Sperling <stsp@openbsd.org>
4  *
5  * Permission to use, copy, modify, and distribute this software for any
6  * purpose with or without fee is hereby granted, provided that the above
7  * copyright notice and this permission notice appear in all copies.
8  *
9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16  */
17 
18 #include <sys/types.h>
19 #include <sys/queue.h>
20 #include <sys/uio.h>
21 
22 #include <limits.h>
23 #include <stdio.h>
24 #include <stdint.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <time.h>
28 #include <imsg.h>
29 #include <inttypes.h>
30 #include <unistd.h>
31 
32 #include "got_error.h"
33 #include "got_cancel.h"
34 #include "got_object.h"
35 #include "got_reference.h"
36 #include "got_repository_admin.h"
37 #include "got_path.h"
38 
39 #include "got_lib_delta.h"
40 #include "got_lib_object.h"
41 #include "got_lib_object_cache.h"
42 #include "got_lib_object_idset.h"
43 #include "got_lib_ratelimit.h"
44 #include "got_lib_pack.h"
45 #include "got_lib_pack_create.h"
46 #include "got_lib_repository.h"
47 
48 static const struct got_error *
49 get_base_object_id(struct got_object_id *base_id, struct got_packidx *packidx,
50     off_t base_offset)
51 {
52 	const struct got_error *err;
53 	int idx;
54 
55 	err = got_packidx_get_offset_idx(&idx, packidx, base_offset);
56 	if (err)
57 		return err;
58 	if (idx == -1)
59 		return got_error(GOT_ERR_BAD_PACKIDX);
60 
61 	return got_packidx_get_object_id(base_id, packidx, idx);
62 }
63 
64 struct search_deltas_arg {
65 	struct got_pack_metavec *v;
66 	struct got_packidx *packidx;
67 	struct got_pack *pack;
68 	struct got_object_idset *idset;
69 	int ncolored, nfound, ntrees, ncommits;
70 	got_pack_progress_cb progress_cb;
71 	void *progress_arg;
72 	struct got_ratelimit *rl;
73 	got_cancel_cb cancel_cb;
74 	void *cancel_arg;
75 };
76 
77 static const struct got_error *
78 search_delta_for_object(struct got_object_id *id, void *data, void *arg)
79 {
80 	const struct got_error *err;
81 	struct search_deltas_arg *a = arg;
82 	int obj_idx;
83 	uint8_t *delta_buf = NULL;
84 	uint64_t base_size, result_size;
85 	size_t delta_size, delta_compressed_size;
86 	off_t delta_offset, delta_data_offset, base_offset;
87 	struct got_object_id base_id;
88 
89 	if (a->cancel_cb) {
90 		err = a->cancel_cb(a->cancel_arg);
91 		if (err)
92 			return err;
93 	}
94 
95 	obj_idx = got_packidx_get_object_idx(a->packidx, id);
96 	if (obj_idx == -1)
97 		return NULL; /* object not present in our pack file */
98 
99 	err = got_packfile_extract_raw_delta(&delta_buf, &delta_size,
100 	    &delta_compressed_size, &delta_offset, &delta_data_offset,
101 	    &base_offset, &base_id, &base_size, &result_size,
102 	    a->pack, a->packidx, obj_idx);
103 	if (err) {
104 		if (err->code == GOT_ERR_OBJ_TYPE)
105 			return NULL; /* object not stored as a delta */
106 		return err;
107 	}
108 
109 	/*
110 	 * If this is an offset delta we must determine the base
111 	 * object ID ourselves.
112 	 */
113 	if (base_offset != 0) {
114 		err = get_base_object_id(&base_id, a->packidx, base_offset);
115 		if (err)
116 			goto done;
117 	}
118 
119 	if (got_object_idset_contains(a->idset, &base_id)) {
120 		struct got_pack_meta *m, *base;
121 
122 		m = got_object_idset_get(a->idset, id);
123 		if (m == NULL) {
124 			err = got_error_msg(GOT_ERR_NO_OBJ,
125 			    "delta object not found");
126 			goto done;
127 		}
128 
129 		base = got_object_idset_get(a->idset, &base_id);
130 		if (m == NULL) {
131 			err = got_error_msg(GOT_ERR_NO_OBJ,
132 			    "delta base object not found");
133 			goto done;
134 		}
135 
136 		m->base_obj_id = got_object_id_dup(&base_id);
137 		if (m->base_obj_id == NULL) {
138 			err = got_error_from_errno("got_object_id_dup");
139 			goto done;
140 		}
141 
142 		m->prev = base;
143 		m->size = result_size;
144 		m->delta_len = delta_size;
145 		m->delta_compressed_len = delta_compressed_size;
146 		m->reused_delta_offset = delta_data_offset;
147 		m->delta_offset = 0;
148 
149 		err = got_pack_add_meta(m, a->v);
150 		if (err)
151 			goto done;
152 
153 		err = got_pack_report_progress(a->progress_cb, a->progress_arg,
154 		    a->rl, a->ncolored, a->nfound, a->ntrees, 0L, a->ncommits,
155 		    got_object_idset_num_elements(a->idset), a->v->nmeta, 0);
156 		if (err)
157 			goto done;
158 	}
159 done:
160 	free(delta_buf);
161 	return err;
162 }
163 
164 const struct got_error *
165 got_pack_search_deltas(struct got_packidx **packidx, struct got_pack **pack,
166     struct got_pack_metavec *v, struct got_object_idset *idset,
167     int ncolored, int nfound, int ntrees, int ncommits,
168     struct got_repository *repo,
169     got_pack_progress_cb progress_cb, void *progress_arg,
170     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
171 {
172 	const struct got_error *err = NULL;
173 	struct search_deltas_arg sda;
174 
175 	*packidx = NULL;
176 	*pack = NULL;
177 
178 	err = got_pack_find_pack_for_reuse(packidx, repo);
179 	if (err)
180 		return err;
181 
182 	if (*packidx == NULL)
183 		return NULL;
184 
185 	err = got_pack_cache_pack_for_packidx(pack, *packidx, repo);
186 	if (err)
187 		return err;
188 
189 	memset(&sda, 0, sizeof(sda));
190 	sda.v = v;
191 	sda.idset = idset;
192 	sda.pack = *pack;
193 	sda.packidx = *packidx;
194 	sda.ncolored = ncolored;
195 	sda.nfound = nfound;
196 	sda.ntrees = ntrees;
197 	sda.ncommits = ncommits;
198 	sda.progress_cb = progress_cb;
199 	sda.progress_arg = progress_arg;
200 	sda.rl = rl;
201 	sda.cancel_cb = cancel_cb;
202 	sda.cancel_arg = cancel_arg;
203 	return got_object_idset_for_each(idset, search_delta_for_object, &sda);
204 }
205 
206 const struct got_error *
207 got_pack_load_packed_object_ids(int *found_all_objects,
208     struct got_object_id **ours, int nours,
209     struct got_object_id **theirs, int ntheirs,
210     int want_meta, uint32_t seed, struct got_object_idset *idset,
211     struct got_object_idset *idset_exclude, int loose_obj_only,
212     struct got_repository *repo, struct got_packidx *packidx,
213     int *ncolored, int *nfound, int *ntrees,
214     got_pack_progress_cb progress_cb, void *progress_arg,
215     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
216 {
217 	/* We do not need this optimized traversal while using direct I/O. */
218 	*found_all_objects = 0;
219 	return NULL;
220 }
221 
222 const struct got_error *
223 got_pack_paint_commits(int *ncolored, struct got_object_id_queue *ids, int nids,
224     struct got_object_idset *keep, struct got_object_idset *drop,
225     struct got_object_idset *skip, struct got_repository *repo,
226     got_pack_progress_cb progress_cb, void *progress_arg,
227     struct got_ratelimit *rl, got_cancel_cb cancel_cb, void *cancel_arg)
228 {
229 	const struct got_error *err = NULL;
230 	struct got_commit_object *commit = NULL;
231 	struct got_packidx *packidx = NULL;
232 	struct got_pack *pack = NULL;
233 	const struct got_object_id_queue *parents;
234 	struct got_object_qid *qid = NULL;
235 	int nqueued = nids, nskip = 0;
236 
237 	while (!STAILQ_EMPTY(ids) && nskip != nqueued) {
238 		intptr_t color;
239 
240 		if (cancel_cb) {
241 			err = cancel_cb(cancel_arg);
242 			if (err)
243 				break;
244 		}
245 
246 		qid = STAILQ_FIRST(ids);
247 		STAILQ_REMOVE_HEAD(ids, entry);
248 		nqueued--;
249 		color = (intptr_t)qid->data;
250 		if (color == COLOR_SKIP)
251 			nskip--;
252 
253 		if (got_object_idset_contains(skip, &qid->id)) {
254 			got_object_qid_free(qid);
255 			qid = NULL;
256 			continue;
257 		}
258 		if (color == COLOR_KEEP &&
259 		    got_object_idset_contains(keep, &qid->id)) {
260 			got_object_qid_free(qid);
261 			qid = NULL;
262 			continue;
263 		}
264 		if (color == COLOR_DROP &&
265 		    got_object_idset_contains(drop, &qid->id)) {
266 			got_object_qid_free(qid);
267 			qid = NULL;
268 			continue;
269 		}
270 
271 		switch (color) {
272 		case COLOR_KEEP:
273 			if (got_object_idset_contains(drop, &qid->id)) {
274 				err = got_pack_paint_commit(qid, COLOR_SKIP);
275 				if (err)
276 					goto done;
277 			} else
278 				(*ncolored)++;
279 			err = got_object_idset_add(keep, &qid->id, NULL);
280 			if (err)
281 				goto done;
282 			break;
283 		case COLOR_DROP:
284 			if (got_object_idset_contains(keep, &qid->id)) {
285 				err = got_pack_paint_commit(qid, COLOR_SKIP);
286 				if (err)
287 					goto done;
288 			} else
289 				(*ncolored)++;
290 			err = got_object_idset_add(drop, &qid->id, NULL);
291 			if (err)
292 				goto done;
293 			break;
294 		case COLOR_SKIP:
295 			if (!got_object_idset_contains(skip, &qid->id)) {
296 				err = got_object_idset_add(skip, &qid->id,
297 				    NULL);
298 				if (err)
299 					goto done;
300 			}
301 			break;
302 		default:
303 			/* should not happen */
304 			err = got_error_fmt(GOT_ERR_NOT_IMPL,
305 			    "%s invalid commit color %"PRIdPTR, __func__,
306 			    color);
307 			goto done;
308 		}
309 
310 		err = got_pack_report_progress(progress_cb, progress_arg, rl,
311 		    *ncolored, 0, 0, 0L, 0, 0, 0, 0);
312 		if (err)
313 			break;
314 
315 		err = got_object_open_as_commit(&commit, repo, &qid->id);
316 		if (err)
317 			break;
318 
319 		parents = got_object_commit_get_parent_ids(commit);
320 		if (parents) {
321 			struct got_object_qid *pid;
322 			color = (intptr_t)qid->data;
323 			STAILQ_FOREACH(pid, parents, entry) {
324 				err = got_pack_queue_commit_id(ids, &pid->id,
325 				    color, repo);
326 				if (err)
327 					break;
328 				nqueued++;
329 				if (color == COLOR_SKIP)
330 					nskip++;
331 			}
332 		}
333 
334 		if (pack == NULL && (commit->flags & GOT_COMMIT_FLAG_PACKED)) {
335 			/*
336 			 * We now know that at least one pack file exists.
337 			 * Pin a suitable pack to ensure it remains cached
338 			 * while we are churning through commit history.
339 			 */
340 			if (packidx == NULL) {
341 				err = got_pack_find_pack_for_commit_painting(
342 				    &packidx, ids, nqueued, repo);
343 				if (err)
344 					goto done;
345 			}
346 			if (packidx != NULL) {
347 				err = got_pack_cache_pack_for_packidx(&pack,
348 				    packidx, repo);
349 				if (err)
350 					goto done;
351 				err = got_repo_pin_pack(repo, packidx, pack);
352 				if (err)
353 					goto done;
354 			}
355 		}
356 
357 		got_object_commit_close(commit);
358 		commit = NULL;
359 
360 		got_object_qid_free(qid);
361 		qid = NULL;
362 	}
363 done:
364 	if (commit)
365 		got_object_commit_close(commit);
366 	got_object_qid_free(qid);
367 	got_repo_unpin_pack(repo);
368 	return err;
369 }