lib/object_idset.c

   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_hash.h"
  34 #include "got_lib_inflate.h"
  35 #include "got_lib_object.h"
  36 #include "got_lib_object_qid.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(GOT_OBJECT_IDSET_MIN_BUCKETS, sizeof(set->ids[0]));
  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, got_hash_digest_length(id->algo));
  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 }