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_inflate.h"
36 #include "got_lib_object.h"
37 #include "got_lib_object_qid.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->sha1, sizeof(id->sha1));
100 }
101 
102 static const struct got_error *
103 idset_resize(struct got_object_idset *set, size_t nbuckets)
104 {
105 	struct got_object_id_queue *ids;
106 	size_t i;
107 
108 	ids = calloc(nbuckets, sizeof(ids[0]));
109 	if (ids == NULL) {
110 		if (errno != ENOMEM)
111 			return got_error_from_errno("calloc");
112 		/* Proceed with our current amount of hash buckets. */
113 		set->flags |= GOT_OBJECT_IDSET_F_NOMEM;
114 		return NULL;
115 	}
116 
117 	for (i = 0; i < nbuckets; i++)
118 		STAILQ_INIT(&ids[i]);
119 
120 	arc4random_buf(&set->key, sizeof(set->key));
121 
122 	for (i = 0; i < set->nbuckets; i++) {
123 		while (!STAILQ_EMPTY(&set->ids[i])) {
124 			struct got_object_qid *qid;
125 			uint64_t idx;
126 			qid = STAILQ_FIRST(&set->ids[i]);
127 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
128 			idx = idset_hash(set, &qid->id) % nbuckets;
129 			STAILQ_INSERT_HEAD(&ids[idx], qid, entry);
130 		}
131 	}
132 
133 	free(set->ids);
134 	set->ids = ids;
135 	set->nbuckets = nbuckets;
136 	return NULL;
137 }
138 
139 static const struct got_error *
140 idset_grow(struct got_object_idset *set)
141 {
142 	size_t nbuckets;
143 
144 	if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)
145 		return NULL;
146 
147 	if (set->nbuckets >= UINT_MAX / 2)
148 		nbuckets = UINT_MAX;
149 	else
150 		nbuckets = set->nbuckets * 2;
151 
152 	return idset_resize(set, nbuckets);
153 }
154 
155 const struct got_error *
156 got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
157     void *data)
158 {
159 	const struct got_error *err;
160 	struct got_object_qid *qid;
161 	uint64_t idx;
162 	struct got_object_id_queue *head;
163 
164 	/* This function may resize the set. */
165 	if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)
166 		return got_error_msg(GOT_ERR_NOT_IMPL,
167 		    "cannot add elements to idset during traversal");
168 
169 	if (set->totelem == UINT_MAX)
170 		return got_error(GOT_ERR_NO_SPACE);
171 
172 	err = got_object_qid_alloc_partial(&qid);
173 	if (err)
174 		return err;
175 	memcpy(&qid->id, id, sizeof(qid->id));
176 	qid->data = data;
177 
178 	idx = idset_hash(set, id) % set->nbuckets;
179 	head = &set->ids[idx];
180 	STAILQ_INSERT_HEAD(head, qid, entry);
181 	set->totelem++;
182 
183 	if (set->nbuckets < set->totelem)
184 		err = idset_grow(set);
185 
186 	return err;
187 }
188 
189 static struct got_object_qid *
190 find_element(struct got_object_idset *set, struct got_object_id *id)
191 {
192 	uint64_t idx = idset_hash(set, id) % set->nbuckets;
193 	struct got_object_id_queue *head = &set->ids[idx];
194 	struct got_object_qid *qid;
195 
196 	STAILQ_FOREACH(qid, head, entry) {
197 		if (got_object_id_cmp(&qid->id, id) == 0)
198 			return qid;
199 	}
200 
201 	return NULL;
202 }
203 
204 void *
205 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
206 {
207 	struct got_object_qid *qid = find_element(set, id);
208 	return qid ? qid->data : NULL;
209 }
210 
211 const struct got_error *
212 got_object_idset_remove(void **data, struct got_object_idset *set,
213     struct got_object_id *id)
214 {
215 	uint64_t idx;
216 	struct got_object_id_queue *head;
217 	struct got_object_qid *qid;
218 
219 	if (data)
220 		*data = NULL;
221 
222 	if (set->totelem == 0)
223 		return got_error(GOT_ERR_NO_OBJ);
224 
225 	if (id == NULL) {
226 		/* Remove a "random" element. */
227 		for (idx = 0; idx < set->nbuckets; idx++) {
228 			head = &set->ids[idx];
229 			qid = STAILQ_FIRST(head);
230 			if (qid)
231 				break;
232 		}
233 	} else {
234 		idx = idset_hash(set, id) % set->nbuckets;
235 		head = &set->ids[idx];
236 		STAILQ_FOREACH(qid, head, entry) {
237 			if (got_object_id_cmp(&qid->id, id) == 0)
238 				break;
239 		}
240 		if (qid == NULL)
241 			return got_error_no_obj(id);
242 	}
243 
244 	if (data)
245 		*data = qid->data;
246 	STAILQ_REMOVE(head, qid, got_object_qid, entry);
247 	got_object_qid_free(qid);
248 	set->totelem--;
249 
250 	return NULL;
251 }
252 
253 int
254 got_object_idset_contains(struct got_object_idset *set,
255     struct got_object_id *id)
256 {
257 	struct got_object_qid *qid = find_element(set, id);
258 	return qid ? 1 : 0;
259 }
260 
261 const struct got_error *
262 got_object_idset_for_each(struct got_object_idset *set,
263     const struct got_error *(*cb)(struct got_object_id *, void *, void *),
264     void *arg)
265 {
266 	const struct got_error *err = NULL;
267 	struct got_object_id_queue *head;
268 	struct got_object_qid *qid, *tmp;
269 	size_t i;
270 
271 	set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;
272 	for (i = 0; i < set->nbuckets; i++) {
273 		head = &set->ids[i];
274 		STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {
275 			err = (*cb)(&qid->id, qid->data, arg);
276 			if (err)
277 				goto done;
278 		}
279 	}
280 done:
281 	set->flags &= ~GOT_OBJECT_IDSET_F_TRAVERSAL;
282 	return err;
283 }
284 
285 int
286 got_object_idset_num_elements(struct got_object_idset *set)
287 {
288 	return set->totelem;
289 }