1 /*
2  * Copyright (c) 2022 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 #include <sys/queue.h>
18 
19 #include <stdlib.h>
20 #include <stdint.h>
21 #include <string.h>
22 #include <sha1.h>
23 #include <sha2.h>
24 #include <stdio.h>
25 #include <zlib.h>
26 #include <limits.h>
27 #include <time.h>
28 #include <errno.h>
29 #include <siphash.h>
30 
31 #include "got_object.h"
32 #include "got_error.h"
33 
34 #include "got_lib_delta.h"
35 #include "got_lib_hash.h"
36 #include "got_lib_inflate.h"
37 #include "got_lib_object.h"
38 #include "got_lib_object_idset.h"
39 #include "got_lib_object_parse.h"
40 
41 #define GOT_OBJECT_IDSET_MIN_BUCKETS	64
42 
43 struct got_object_idset {
44 	struct got_object_id_queue *ids;
45 	size_t nbuckets;
46 	unsigned int totelem;
47 	unsigned int flags;
48 #define GOT_OBJECT_IDSET_F_TRAVERSAL	0x01
49 #define GOT_OBJECT_IDSET_F_NOMEM	0x02
50 	SIPHASH_KEY key;
51 };
52 
53 struct got_object_idset *
54 got_object_idset_alloc(void)
55 {
56 	struct got_object_idset *set;
57 	int i;
58 
59 	set = malloc(sizeof(*set));
60 	if (set == NULL)
61 		return NULL;
62 
63 	set->ids = calloc(sizeof(set->ids[0]), GOT_OBJECT_IDSET_MIN_BUCKETS);
64 	if (set->ids == NULL) {
65 		free(set);
66 		return NULL;
67 	}
68 	for (i = 0; i < GOT_OBJECT_IDSET_MIN_BUCKETS; i++)
69 		STAILQ_INIT(&set->ids[i]);
70 
71 	set->totelem = 0;
72 	set->nbuckets = GOT_OBJECT_IDSET_MIN_BUCKETS;
73 	set->flags = 0;
74 	arc4random_buf(&set->key, sizeof(set->key));
75 	return set;
76 }
77 
78 void
79 got_object_idset_free(struct got_object_idset *set)
80 {
81 	size_t i;
82 	struct got_object_qid *qid;
83 
84 	for (i = 0; i < set->nbuckets; i++) {
85 		while (!STAILQ_EMPTY(&set->ids[i])) {
86 			qid = STAILQ_FIRST(&set->ids[i]);
87 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
88 			got_object_qid_free(qid);
89 		}
90 	}
91 	/* User data should be freed by caller. */
92 	free(set->ids);
93 	free(set);
94 }
95 
96 static uint64_t
97 idset_hash(struct got_object_idset *set, struct got_object_id *id)
98 {
99 	return SipHash24(&set->key, id->hash,
100 	    got_hash_digest_length(id->algo));
101 }
102 
103 static const struct got_error *
104 idset_resize(struct got_object_idset *set, size_t nbuckets)
105 {
106 	struct got_object_id_queue *ids;
107 	size_t i;
108 
109 	ids = calloc(nbuckets, sizeof(ids[0]));
110 	if (ids == NULL) {
111 		if (errno != ENOMEM)
112 			return got_error_from_errno("calloc");
113 		/* Proceed with our current amount of hash buckets. */
114 		set->flags |= GOT_OBJECT_IDSET_F_NOMEM;
115 		return NULL;
116 	}
117 
118 	for (i = 0; i < nbuckets; i++)
119 		STAILQ_INIT(&ids[i]);
120 
121 	arc4random_buf(&set->key, sizeof(set->key));
122 
123 	for (i = 0; i < set->nbuckets; i++) {
124 		while (!STAILQ_EMPTY(&set->ids[i])) {
125 			struct got_object_qid *qid;
126 			uint64_t idx;
127 			qid = STAILQ_FIRST(&set->ids[i]);
128 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
129 			idx = idset_hash(set, &qid->id) % nbuckets;
130 			STAILQ_INSERT_HEAD(&ids[idx], qid, entry);
131 		}
132 	}
133 
134 	free(set->ids);
135 	set->ids = ids;
136 	set->nbuckets = nbuckets;
137 	return NULL;
138 }
139 
140 static const struct got_error *
141 idset_grow(struct got_object_idset *set)
142 {
143 	size_t nbuckets;
144 
145 	if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)
146 		return NULL;
147 
148 	if (set->nbuckets >= UINT_MAX / 2)
149 		nbuckets = UINT_MAX;
150 	else
151 		nbuckets = set->nbuckets * 2;
152 
153 	return idset_resize(set, nbuckets);
154 }
155 
156 const struct got_error *
157 got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
158     void *data)
159 {
160 	const struct got_error *err;
161 	struct got_object_qid *qid;
162 	uint64_t idx;
163 	struct got_object_id_queue *head;
164 
165 	/* This function may resize the set. */
166 	if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)
167 		return got_error_msg(GOT_ERR_NOT_IMPL,
168 		    "cannot add elements to idset during traversal");
169 
170 	if (set->totelem == UINT_MAX)
171 		return got_error(GOT_ERR_NO_SPACE);
172 
173 	err = got_object_qid_alloc_partial(&qid);
174 	if (err)
175 		return err;
176 	memcpy(&qid->id, id, sizeof(qid->id));
177 	qid->data = data;
178 
179 	idx = idset_hash(set, id) % set->nbuckets;
180 	head = &set->ids[idx];
181 	STAILQ_INSERT_HEAD(head, qid, entry);
182 	set->totelem++;
183 
184 	if (set->nbuckets < set->totelem)
185 		err = idset_grow(set);
186 
187 	return err;
188 }
189 
190 static struct got_object_qid *
191 find_element(struct got_object_idset *set, struct got_object_id *id)
192 {
193 	uint64_t idx = idset_hash(set, id) % set->nbuckets;
194 	struct got_object_id_queue *head = &set->ids[idx];
195 	struct got_object_qid *qid;
196 
197 	STAILQ_FOREACH(qid, head, entry) {
198 		if (got_object_id_cmp(&qid->id, id) == 0)
199 			return qid;
200 	}
201 
202 	return NULL;
203 }
204 
205 void *
206 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
207 {
208 	struct got_object_qid *qid = find_element(set, id);
209 	return qid ? qid->data : NULL;
210 }
211 
212 const struct got_error *
213 got_object_idset_remove(void **data, struct got_object_idset *set,
214     struct got_object_id *id)
215 {
216 	uint64_t idx;
217 	struct got_object_id_queue *head;
218 	struct got_object_qid *qid;
219 
220 	if (data)
221 		*data = NULL;
222 
223 	if (set->totelem == 0)
224 		return got_error(GOT_ERR_NO_OBJ);
225 
226 	if (id == NULL) {
227 		/* Remove a "random" element. */
228 		for (idx = 0; idx < set->nbuckets; idx++) {
229 			head = &set->ids[idx];
230 			qid = STAILQ_FIRST(head);
231 			if (qid)
232 				break;
233 		}
234 	} else {
235 		idx = idset_hash(set, id) % set->nbuckets;
236 		head = &set->ids[idx];
237 		STAILQ_FOREACH(qid, head, entry) {
238 			if (got_object_id_cmp(&qid->id, id) == 0)
239 				break;
240 		}
241 		if (qid == NULL)
242 			return got_error_no_obj(id);
243 	}
244 
245 	if (data)
246 		*data = qid->data;
247 	STAILQ_REMOVE(head, qid, got_object_qid, entry);
248 	got_object_qid_free(qid);
249 	set->totelem--;
250 
251 	return NULL;
252 }
253 
254 int
255 got_object_idset_contains(struct got_object_idset *set,
256     struct got_object_id *id)
257 {
258 	struct got_object_qid *qid = find_element(set, id);
259 	return qid ? 1 : 0;
260 }
261 
262 const struct got_error *
263 got_object_idset_for_each(struct got_object_idset *set,
264     const struct got_error *(*cb)(struct got_object_id *, void *, void *),
265     void *arg)
266 {
267 	const struct got_error *err = NULL;
268 	struct got_object_id_queue *head;
269 	struct got_object_qid *qid, *tmp;
270 	size_t i;
271 
272 	set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;
273 	for (i = 0; i < set->nbuckets; i++) {
274 		head = &set->ids[i];
275 		STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {
276 			err = (*cb)(&qid->id, qid->data, arg);
277 			if (err)
278 				goto done;
279 		}
280 	}
281 done:
282 	set->flags &= ~GOT_OBJECT_IDSET_F_TRAVERSAL;
283 	return err;
284 }
285 
286 int
287 got_object_idset_num_elements(struct got_object_idset *set)
288 {
289 	return set->totelem;
290 }