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