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