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_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 }