2 cbc287dc 2022-04-19 stsp * Copyright (c) 2022 Stefan Sperling <stsp@openbsd.org>
4 54be8251 2018-06-04 stsp * Permission to use, copy, modify, and distribute this software for any
5 54be8251 2018-06-04 stsp * purpose with or without fee is hereby granted, provided that the above
6 54be8251 2018-06-04 stsp * copyright notice and this permission notice appear in all copies.
8 54be8251 2018-06-04 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 54be8251 2018-06-04 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 54be8251 2018-06-04 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 54be8251 2018-06-04 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 54be8251 2018-06-04 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 54be8251 2018-06-04 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 54be8251 2018-06-04 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 54be8251 2018-06-04 stsp #include <sys/queue.h>
19 54be8251 2018-06-04 stsp #include <stdlib.h>
20 cbc287dc 2022-04-19 stsp #include <stdint.h>
21 54be8251 2018-06-04 stsp #include <string.h>
22 54be8251 2018-06-04 stsp #include <sha1.h>
23 5822e79e 2023-02-23 op #include <sha2.h>
24 54be8251 2018-06-04 stsp #include <stdio.h>
25 54be8251 2018-06-04 stsp #include <zlib.h>
26 c6f420bf 2018-06-04 stsp #include <limits.h>
27 788c352e 2018-06-16 stsp #include <time.h>
28 cbc287dc 2022-04-19 stsp #include <errno.h>
29 cbc287dc 2022-04-19 stsp #include <siphash.h>
31 54be8251 2018-06-04 stsp #include "got_object.h"
32 54be8251 2018-06-04 stsp #include "got_error.h"
34 54be8251 2018-06-04 stsp #include "got_lib_delta.h"
35 63581804 2018-07-09 stsp #include "got_lib_inflate.h"
36 54be8251 2018-06-04 stsp #include "got_lib_object.h"
37 2f43cd69 2023-04-14 stsp #include "got_lib_object_qid.h"
38 54be8251 2018-06-04 stsp #include "got_lib_object_idset.h"
39 cbc287dc 2022-04-19 stsp #include "got_lib_object_parse.h"
41 cbc287dc 2022-04-19 stsp #define GOT_OBJECT_IDSET_MIN_BUCKETS 64
43 54be8251 2018-06-04 stsp struct got_object_idset {
44 cbc287dc 2022-04-19 stsp struct got_object_id_queue *ids;
45 cbc287dc 2022-04-19 stsp size_t nbuckets;
46 cbc287dc 2022-04-19 stsp unsigned int totelem;
47 cbc287dc 2022-04-19 stsp unsigned int flags;
48 cbc287dc 2022-04-19 stsp #define GOT_OBJECT_IDSET_F_TRAVERSAL 0x01
49 cbc287dc 2022-04-19 stsp #define GOT_OBJECT_IDSET_F_NOMEM 0x02
50 cbc287dc 2022-04-19 stsp SIPHASH_KEY key;
53 54be8251 2018-06-04 stsp struct got_object_idset *
54 60f2eee1 2018-07-08 stsp got_object_idset_alloc(void)
56 54be8251 2018-06-04 stsp struct got_object_idset *set;
59 984e8a45 2018-11-05 stsp set = malloc(sizeof(*set));
60 54be8251 2018-06-04 stsp if (set == NULL)
61 54be8251 2018-06-04 stsp return NULL;
63 cbc287dc 2022-04-19 stsp set->ids = calloc(sizeof(set->ids[0]), GOT_OBJECT_IDSET_MIN_BUCKETS);
64 cbc287dc 2022-04-19 stsp if (set->ids == NULL) {
66 cbc287dc 2022-04-19 stsp return NULL;
68 cbc287dc 2022-04-19 stsp for (i = 0; i < GOT_OBJECT_IDSET_MIN_BUCKETS; i++)
69 cbc287dc 2022-04-19 stsp STAILQ_INIT(&set->ids[i]);
71 cbc287dc 2022-04-19 stsp set->totelem = 0;
72 cbc287dc 2022-04-19 stsp set->nbuckets = GOT_OBJECT_IDSET_MIN_BUCKETS;
73 cbc287dc 2022-04-19 stsp set->flags = 0;
74 cbc287dc 2022-04-19 stsp arc4random_buf(&set->key, sizeof(set->key));
79 54be8251 2018-06-04 stsp got_object_idset_free(struct got_object_idset *set)
82 cbc287dc 2022-04-19 stsp struct got_object_qid *qid;
84 cbc287dc 2022-04-19 stsp for (i = 0; i < set->nbuckets; i++) {
85 cbc287dc 2022-04-19 stsp while (!STAILQ_EMPTY(&set->ids[i])) {
86 cbc287dc 2022-04-19 stsp qid = STAILQ_FIRST(&set->ids[i]);
87 cbc287dc 2022-04-19 stsp STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
88 cbc287dc 2022-04-19 stsp got_object_qid_free(qid);
91 cbc287dc 2022-04-19 stsp /* User data should be freed by caller. */
92 cbc287dc 2022-04-19 stsp free(set->ids);
96 cbc287dc 2022-04-19 stsp static uint64_t
97 cbc287dc 2022-04-19 stsp idset_hash(struct got_object_idset *set, struct got_object_id *id)
99 cbc287dc 2022-04-19 stsp return SipHash24(&set->key, id->sha1, sizeof(id->sha1));
102 cbc287dc 2022-04-19 stsp static const struct got_error *
103 cbc287dc 2022-04-19 stsp idset_resize(struct got_object_idset *set, size_t nbuckets)
105 cbc287dc 2022-04-19 stsp struct got_object_id_queue *ids;
108 cbc287dc 2022-04-19 stsp ids = calloc(nbuckets, sizeof(ids[0]));
109 cbc287dc 2022-04-19 stsp if (ids == NULL) {
110 cbc287dc 2022-04-19 stsp if (errno != ENOMEM)
111 cbc287dc 2022-04-19 stsp return got_error_from_errno("calloc");
112 cbc287dc 2022-04-19 stsp /* Proceed with our current amount of hash buckets. */
113 cbc287dc 2022-04-19 stsp set->flags |= GOT_OBJECT_IDSET_F_NOMEM;
114 cbc287dc 2022-04-19 stsp return NULL;
117 cbc287dc 2022-04-19 stsp for (i = 0; i < nbuckets; i++)
118 cbc287dc 2022-04-19 stsp STAILQ_INIT(&ids[i]);
120 cbc287dc 2022-04-19 stsp arc4random_buf(&set->key, sizeof(set->key));
122 cbc287dc 2022-04-19 stsp for (i = 0; i < set->nbuckets; i++) {
123 cbc287dc 2022-04-19 stsp while (!STAILQ_EMPTY(&set->ids[i])) {
124 cbc287dc 2022-04-19 stsp struct got_object_qid *qid;
125 cbc287dc 2022-04-19 stsp uint64_t idx;
126 cbc287dc 2022-04-19 stsp qid = STAILQ_FIRST(&set->ids[i]);
127 cbc287dc 2022-04-19 stsp STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);
128 d7b5a0e8 2022-04-20 stsp idx = idset_hash(set, &qid->id) % nbuckets;
129 cbc287dc 2022-04-19 stsp STAILQ_INSERT_HEAD(&ids[idx], qid, entry);
133 cbc287dc 2022-04-19 stsp free(set->ids);
134 cbc287dc 2022-04-19 stsp set->ids = ids;
135 cbc287dc 2022-04-19 stsp set->nbuckets = nbuckets;
136 b36429ab 2018-11-05 stsp return NULL;
139 cbc287dc 2022-04-19 stsp static const struct got_error *
140 cbc287dc 2022-04-19 stsp idset_grow(struct got_object_idset *set)
142 cbc287dc 2022-04-19 stsp size_t nbuckets;
144 cbc287dc 2022-04-19 stsp if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)
145 cbc287dc 2022-04-19 stsp return NULL;
147 cbc287dc 2022-04-19 stsp if (set->nbuckets >= UINT_MAX / 2)
148 cbc287dc 2022-04-19 stsp nbuckets = UINT_MAX;
150 cbc287dc 2022-04-19 stsp nbuckets = set->nbuckets * 2;
152 cbc287dc 2022-04-19 stsp return idset_resize(set, nbuckets);
155 cbc287dc 2022-04-19 stsp const struct got_error *
156 cbc287dc 2022-04-19 stsp got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,
157 cbc287dc 2022-04-19 stsp void *data)
159 cbc287dc 2022-04-19 stsp const struct got_error *err;
160 cbc287dc 2022-04-19 stsp struct got_object_qid *qid;
161 cbc287dc 2022-04-19 stsp uint64_t idx;
162 cbc287dc 2022-04-19 stsp struct got_object_id_queue *head;
164 cbc287dc 2022-04-19 stsp /* This function may resize the set. */
165 cbc287dc 2022-04-19 stsp if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)
166 cbc287dc 2022-04-19 stsp return got_error_msg(GOT_ERR_NOT_IMPL,
167 cbc287dc 2022-04-19 stsp "cannot add elements to idset during traversal");
169 cbc287dc 2022-04-19 stsp if (set->totelem == UINT_MAX)
170 cbc287dc 2022-04-19 stsp return got_error(GOT_ERR_NO_SPACE);
172 cbc287dc 2022-04-19 stsp err = got_object_qid_alloc_partial(&qid);
174 cbc287dc 2022-04-19 stsp return err;
175 d7b5a0e8 2022-04-20 stsp memcpy(&qid->id, id, sizeof(qid->id));
176 cbc287dc 2022-04-19 stsp qid->data = data;
178 cbc287dc 2022-04-19 stsp idx = idset_hash(set, id) % set->nbuckets;
179 cbc287dc 2022-04-19 stsp head = &set->ids[idx];
180 cbc287dc 2022-04-19 stsp STAILQ_INSERT_HEAD(head, qid, entry);
181 cbc287dc 2022-04-19 stsp set->totelem++;
183 cbc287dc 2022-04-19 stsp if (set->nbuckets < set->totelem)
184 cbc287dc 2022-04-19 stsp err = idset_grow(set);
186 cbc287dc 2022-04-19 stsp return err;
189 cbc287dc 2022-04-19 stsp static struct got_object_qid *
190 cbc287dc 2022-04-19 stsp find_element(struct got_object_idset *set, struct got_object_id *id)
192 cbc287dc 2022-04-19 stsp uint64_t idx = idset_hash(set, id) % set->nbuckets;
193 cbc287dc 2022-04-19 stsp struct got_object_id_queue *head = &set->ids[idx];
194 cbc287dc 2022-04-19 stsp struct got_object_qid *qid;
196 cbc287dc 2022-04-19 stsp STAILQ_FOREACH(qid, head, entry) {
197 d7b5a0e8 2022-04-20 stsp if (got_object_id_cmp(&qid->id, id) == 0)
198 cbc287dc 2022-04-19 stsp return qid;
201 cbc287dc 2022-04-19 stsp return NULL;
205 984e8a45 2018-11-05 stsp got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
207 cbc287dc 2022-04-19 stsp struct got_object_qid *qid = find_element(set, id);
208 cbc287dc 2022-04-19 stsp return qid ? qid->data : NULL;
211 54be8251 2018-06-04 stsp const struct got_error *
212 e7c810ea 2018-06-22 stsp got_object_idset_remove(void **data, struct got_object_idset *set,
213 54be8251 2018-06-04 stsp struct got_object_id *id)
215 cbc287dc 2022-04-19 stsp uint64_t idx;
216 cbc287dc 2022-04-19 stsp struct got_object_id_queue *head;
217 cbc287dc 2022-04-19 stsp struct got_object_qid *qid;
220 441e144c 2018-06-22 stsp *data = NULL;
222 984e8a45 2018-11-05 stsp if (set->totelem == 0)
223 c6f420bf 2018-06-04 stsp return got_error(GOT_ERR_NO_OBJ);
225 0ae61b79 2022-03-21 stsp if (id == NULL) {
226 cbc287dc 2022-04-19 stsp /* Remove a "random" element. */
227 cbc287dc 2022-04-19 stsp for (idx = 0; idx < set->nbuckets; idx++) {
228 cbc287dc 2022-04-19 stsp head = &set->ids[idx];
229 cbc287dc 2022-04-19 stsp qid = STAILQ_FIRST(head);
234 cbc287dc 2022-04-19 stsp idx = idset_hash(set, id) % set->nbuckets;
235 cbc287dc 2022-04-19 stsp head = &set->ids[idx];
236 cbc287dc 2022-04-19 stsp STAILQ_FOREACH(qid, head, entry) {
237 d7b5a0e8 2022-04-20 stsp if (got_object_id_cmp(&qid->id, id) == 0)
240 cbc287dc 2022-04-19 stsp if (qid == NULL)
241 0ae61b79 2022-03-21 stsp return got_error_no_obj(id);
245 cbc287dc 2022-04-19 stsp *data = qid->data;
246 cbc287dc 2022-04-19 stsp STAILQ_REMOVE(head, qid, got_object_qid, entry);
247 cbc287dc 2022-04-19 stsp got_object_qid_free(qid);
248 984e8a45 2018-11-05 stsp set->totelem--;
250 984e8a45 2018-11-05 stsp return NULL;
254 54be8251 2018-06-04 stsp got_object_idset_contains(struct got_object_idset *set,
255 54be8251 2018-06-04 stsp struct got_object_id *id)
257 cbc287dc 2022-04-19 stsp struct got_object_qid *qid = find_element(set, id);
258 cbc287dc 2022-04-19 stsp return qid ? 1 : 0;
261 cb103d04 2018-11-07 stsp const struct got_error *
262 cb103d04 2018-11-07 stsp got_object_idset_for_each(struct got_object_idset *set,
263 cb103d04 2018-11-07 stsp const struct got_error *(*cb)(struct got_object_id *, void *, void *),
266 cbc287dc 2022-04-19 stsp const struct got_error *err = NULL;
267 cbc287dc 2022-04-19 stsp struct got_object_id_queue *head;
268 cbc287dc 2022-04-19 stsp struct got_object_qid *qid, *tmp;
271 cbc287dc 2022-04-19 stsp set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;
272 cbc287dc 2022-04-19 stsp for (i = 0; i < set->nbuckets; i++) {
273 cbc287dc 2022-04-19 stsp head = &set->ids[i];
274 cbc287dc 2022-04-19 stsp STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {
275 d7b5a0e8 2022-04-20 stsp err = (*cb)(&qid->id, qid->data, arg);
281 cbc287dc 2022-04-19 stsp set->flags &= ~GOT_OBJECT_IDSET_F_TRAVERSAL;
282 cbc287dc 2022-04-19 stsp return err;
286 c6f420bf 2018-06-04 stsp got_object_idset_num_elements(struct got_object_idset *set)
288 2bd394ff 2018-06-22 stsp return set->totelem;