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