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