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_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(sizeof(set->ids[0]), GOT_OBJECT_IDSET_MIN_BUCKETS);
  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 }