src/ecoli_keyval.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
   3  */
   4
   5 #include <sys/types.h>
   6 #include <sys/stat.h>
   7 #include <sys/queue.h>
   8 #include <stdlib.h>
   9 #include <stdint.h>
  10 #include <unistd.h>
  11 #include <assert.h>
  12 #include <errno.h>
  13 #include <fcntl.h>
  14
  15 #include <ecoli_init.h>
  16 #include <ecoli_malloc.h>
  17 #include <ecoli_log.h>
  18 #include <ecoli_test.h>
  19 #include <ecoli_murmurhash.h>
  20 #include <ecoli_keyval.h>
  21
  22 #define FACTOR 3
  23
  24 EC_LOG_TYPE_REGISTER(keyval);
  25
  26 static uint32_t ec_keyval_seed;
  27
  28 struct ec_keyval_elt {
  29         char *key;
  30         void *val;
  31         uint32_t hash;
  32         ec_keyval_elt_free_t free;
  33         unsigned int refcount;
  34 };
  35
  36 struct ec_keyval_elt_ref {
  37         TAILQ_ENTRY(ec_keyval_elt_ref) next;
  38         TAILQ_ENTRY(ec_keyval_elt_ref) hnext;
  39         struct ec_keyval_elt *elt;
  40 };
  41
  42 TAILQ_HEAD(ec_keyval_elt_ref_list, ec_keyval_elt_ref);
  43
  44 struct ec_keyval {
  45         size_t len;
  46         size_t table_size;
  47         struct ec_keyval_elt_ref_list list;
  48         struct ec_keyval_elt_ref_list *table;
  49 };
  50
  51 struct ec_keyval *ec_keyval(void)
  52 {
  53         struct ec_keyval *keyval;
  54
  55         keyval = ec_calloc(1, sizeof(*keyval));
  56         if (keyval == NULL)
  57                 return NULL;
  58         TAILQ_INIT(&keyval->list);
  59
  60         return keyval;
  61 }
  62
  63 static struct ec_keyval_elt_ref *
  64 ec_keyval_lookup(const struct ec_keyval *keyval, const char *key)
  65 {
  66         struct ec_keyval_elt_ref *ref;
  67         uint32_t h, mask = keyval->table_size - 1;
  68
  69         if (keyval == NULL || key == NULL) {
  70                 errno = EINVAL;
  71                 return NULL;
  72         }
  73         if (keyval->table_size == 0) {
  74                 errno = ENOENT;
  75                 return NULL;
  76         }
  77
  78         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
  79         TAILQ_FOREACH(ref, &keyval->table[h & mask], hnext) {
  80                 if (strcmp(ref->elt->key, key) == 0)
  81                         return ref;
  82         }
  83
  84         errno = ENOENT;
  85         return NULL;
  86 }
  87
  88 static void ec_keyval_elt_ref_free(struct ec_keyval_elt_ref *ref)
  89 {
  90         struct ec_keyval_elt *elt;
  91
  92         if (ref == NULL)
  93                 return;
  94
  95         elt = ref->elt;
  96         if (elt != NULL && --elt->refcount == 0) {
  97                 ec_free(elt->key);
  98                 if (elt->free != NULL)
  99                         elt->free(elt->val);
 100                 ec_free(elt);
 101         }
 102         ec_free(ref);
 103 }
 104
 105 bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
 106 {
 107         return !!ec_keyval_lookup(keyval, key);
 108 }
 109
 110 void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
 111 {
 112         struct ec_keyval_elt_ref *ref;
 113
 114         ref = ec_keyval_lookup(keyval, key);
 115         if (ref == NULL)
 116                 return NULL;
 117
 118         return ref->elt->val;
 119 }
 120
 121 int ec_keyval_del(struct ec_keyval *keyval, const char *key)
 122 {
 123         struct ec_keyval_elt_ref *ref;
 124         size_t idx;
 125
 126         ref = ec_keyval_lookup(keyval, key);
 127         if (ref == NULL)
 128                 return -1;
 129
 130         /* we could resize table here */
 131
 132         TAILQ_REMOVE(&keyval->list, ref, next);
 133         idx = ref->elt->hash & (keyval->table_size - 1);
 134         TAILQ_REMOVE(&keyval->table[idx], ref, hnext);
 135         ec_keyval_elt_ref_free(ref);
 136         keyval->len--;
 137
 138         return 0;
 139 }
 140
 141 static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
 142 {
 143         struct ec_keyval_elt_ref_list *new_table;
 144         struct ec_keyval_elt_ref *ref;
 145         size_t i;
 146
 147         if (new_size == 0 || (new_size & (new_size - 1))) {
 148                 errno = EINVAL;
 149                 return -1;
 150         }
 151
 152         new_table = ec_calloc(new_size, sizeof(*keyval->table));
 153         if (new_table == NULL)
 154                 return -1;
 155         for (i = 0; i < new_size; i++)
 156                 TAILQ_INIT(&new_table[i]);
 157
 158         TAILQ_FOREACH(ref, &keyval->list, next) {
 159                 i = ref->elt->hash & (keyval->table_size - 1);
 160                 TAILQ_REMOVE(&keyval->table[i], ref, hnext);
 161                 i = ref->elt->hash & (new_size - 1);
 162                 TAILQ_INSERT_TAIL(&new_table[i], ref, hnext);
 163         }
 164
 165         ec_free(keyval->table);
 166         keyval->table = new_table;
 167         keyval->table_size = new_size;
 168
 169         return 0;
 170 }
 171
 172 static int
 173 __ec_keyval_set(struct ec_keyval *keyval, struct ec_keyval_elt_ref *ref)
 174 {
 175         size_t new_size;
 176         uint32_t mask;
 177         int ret;
 178
 179         /* remove previous entry if any */
 180         ec_keyval_del(keyval, ref->elt->key);
 181
 182         if (keyval->len >= keyval->table_size) {
 183                 if (keyval->table_size != 0)
 184                         new_size =  keyval->table_size << FACTOR;
 185                 else
 186                         new_size =  1 << FACTOR;
 187                 ret = ec_keyval_table_resize(keyval, new_size);
 188                 if (ret < 0)
 189                         return ret;
 190         }
 191
 192         mask = keyval->table_size - 1;
 193         TAILQ_INSERT_TAIL(&keyval->table[ref->elt->hash & mask], ref, hnext);
 194         TAILQ_INSERT_TAIL(&keyval->list, ref, next);
 195         keyval->len++;
 196
 197         return 0;
 198 }
 199
 200 int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
 201         ec_keyval_elt_free_t free_cb)
 202 {
 203         struct ec_keyval_elt *elt = NULL;
 204         struct ec_keyval_elt_ref *ref = NULL;
 205         uint32_t h;
 206
 207         if (keyval == NULL || key == NULL) {
 208                 errno = EINVAL;
 209                 return -1;
 210         }
 211
 212         ref = ec_calloc(1, sizeof(*ref));
 213         if (ref == NULL)
 214                 goto fail;
 215
 216         elt = ec_calloc(1, sizeof(*elt));
 217         if (elt == NULL)
 218                 goto fail;
 219
 220         ref->elt = elt;
 221         elt->refcount = 1;
 222         elt->val = val;
 223         val = NULL;
 224         elt->free = free_cb;
 225         elt->key = ec_strdup(key);
 226         if (elt->key == NULL)
 227                 goto fail;
 228         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
 229         elt->hash = h;
 230
 231         if (__ec_keyval_set(keyval, ref) < 0)
 232                 goto fail;
 233
 234         return 0;
 235
 236 fail:
 237         if (free_cb != NULL && val != NULL)
 238                 free_cb(val);
 239         ec_keyval_elt_ref_free(ref);
 240         return -1;
 241 }
 242
 243 void ec_keyval_free(struct ec_keyval *keyval)
 244 {
 245         struct ec_keyval_elt_ref *ref;
 246         size_t idx;
 247
 248         if (keyval == NULL)
 249                 return;
 250
 251         while (!TAILQ_EMPTY(&keyval->list)) {
 252                 ref = TAILQ_FIRST(&keyval->list);
 253                 TAILQ_REMOVE(&keyval->list, ref, next);
 254                 idx = ref->elt->hash & (keyval->table_size - 1);
 255                 TAILQ_REMOVE(&keyval->table[idx], ref, hnext);
 256                 ec_keyval_elt_ref_free(ref);
 257         }
 258         ec_free(keyval->table);
 259         ec_free(keyval);
 260 }
 261
 262 size_t ec_keyval_len(const struct ec_keyval *keyval)
 263 {
 264         return keyval->len;
 265 }
 266
 267 struct ec_keyval_elt_ref *
 268 ec_keyval_iter(const struct ec_keyval *keyval)
 269 {
 270         if (keyval == NULL)
 271                 return NULL;
 272
 273         return TAILQ_FIRST(&keyval->list);
 274 }
 275
 276 struct ec_keyval_elt_ref *
 277 ec_keyval_iter_next(struct ec_keyval_elt_ref *iter)
 278 {
 279         if (iter == NULL)
 280                 return NULL;
 281
 282         return TAILQ_NEXT(iter, next);
 283 }
 284
 285 const char *
 286 ec_keyval_iter_get_key(const struct ec_keyval_elt_ref *iter)
 287 {
 288         if (iter == NULL)
 289                 return NULL;
 290
 291         return iter->elt->key;
 292 }
 293
 294 void *
 295 ec_keyval_iter_get_val(const struct ec_keyval_elt_ref *iter)
 296 {
 297         if (iter == NULL)
 298                 return NULL;
 299
 300         return iter->elt->val;
 301 }
 302
 303 void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
 304 {
 305         struct ec_keyval_elt_ref *iter;
 306
 307         if (keyval == NULL) {
 308                 fprintf(out, "empty keyval\n");
 309                 return;
 310         }
 311
 312         fprintf(out, "keyval:\n");
 313         for (iter = ec_keyval_iter(keyval);
 314              iter != NULL;
 315              iter = ec_keyval_iter_next(iter)) {
 316                 fprintf(out, "  %s: %p\n",
 317                         ec_keyval_iter_get_key(iter),
 318                         ec_keyval_iter_get_val(iter));
 319         }
 320 }
 321
 322 struct ec_keyval *ec_keyval_dup(const struct ec_keyval *keyval)
 323 {
 324         struct ec_keyval *dup = NULL;
 325         struct ec_keyval_elt_ref *ref, *dup_ref = NULL;
 326
 327         dup = ec_keyval();
 328         if (dup == NULL)
 329                 return NULL;
 330
 331         TAILQ_FOREACH(ref, &keyval->list, next) {
 332                 dup_ref = ec_calloc(1, sizeof(*ref));
 333                 if (dup_ref == NULL)
 334                         goto fail;
 335                 dup_ref->elt = ref->elt;
 336                 ref->elt->refcount++;
 337
 338                 if (__ec_keyval_set(dup, dup_ref) < 0)
 339                         goto fail;
 340         }
 341
 342         return dup;
 343
 344 fail:
 345         ec_keyval_elt_ref_free(dup_ref);
 346         ec_keyval_free(dup);
 347         return NULL;
 348 }
 349
 350 static int ec_keyval_init_func(void)
 351 {
 352         int fd;
 353         ssize_t ret;
 354
 355         return 0;//XXX for test reproduceability
 356
 357         fd = open("/dev/urandom", 0);
 358         if (fd == -1) {
 359                 fprintf(stderr, "failed to open /dev/urandom\n");
 360                 return -1;
 361         }
 362         ret = read(fd, &ec_keyval_seed, sizeof(ec_keyval_seed));
 363         if (ret != sizeof(ec_keyval_seed)) {
 364                 fprintf(stderr, "failed to read /dev/urandom\n");
 365                 return -1;
 366         }
 367         close(fd);
 368         return 0;
 369 }
 370
 371 static struct ec_init ec_keyval_init = {
 372         .init = ec_keyval_init_func,
 373         .priority = 50,
 374 };
 375
 376 EC_INIT_REGISTER(ec_keyval_init);
 377
 378 /* LCOV_EXCL_START */
 379 static int ec_keyval_testcase(void)
 380 {
 381         struct ec_keyval *keyval, *dup;
 382         struct ec_keyval_elt_ref *iter;
 383         char *val;
 384         size_t i, count;
 385         int ret, testres = 0;
 386         FILE *f = NULL;
 387         char *buf = NULL;
 388         size_t buflen = 0;
 389
 390         keyval = ec_keyval();
 391         if (keyval == NULL) {
 392                 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
 393                 return -1;
 394         }
 395
 396         count = 0;
 397         for (iter = ec_keyval_iter(keyval);
 398              iter != NULL;
 399              iter = ec_keyval_iter_next(iter)) {
 400                 count++;
 401         }
 402         testres |= EC_TEST_CHECK(count == 0, "invalid count in iterator");
 403
 404         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0, "bad keyval len");
 405         ret = ec_keyval_set(keyval, "key1", "val1", NULL);
 406         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 407         ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
 408         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 409         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2, "bad keyval len");
 410
 411         val = ec_keyval_get(keyval, "key1");
 412         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val1"),
 413                                 "invalid keyval value");
 414         val = ec_keyval_get(keyval, "key2");
 415         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val2"),
 416                                 "invalid keyval value");
 417         val = ec_keyval_get(keyval, "key3");
 418         testres |= EC_TEST_CHECK(val == NULL, "key3 should be NULL");
 419
 420         ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
 421         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 422         ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
 423                         ec_free_func);
 424         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 425         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2,
 426                                 "bad keyval len");
 427
 428         val = ec_keyval_get(keyval, "key1");
 429         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val1"),
 430                 "invalid keyval value");
 431         val = ec_keyval_get(keyval, "key2");
 432         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val2"),
 433                 "invalid keyval value");
 434         testres |= EC_TEST_CHECK(ec_keyval_has_key(keyval, "key1"),
 435                 "key1 should be in keyval");
 436
 437         f = open_memstream(&buf, &buflen);
 438         if (f == NULL)
 439                 goto fail;
 440         ec_keyval_dump(f, NULL);
 441         fclose(f);
 442         f = NULL;
 443         free(buf);
 444         buf = NULL;
 445
 446         f = open_memstream(&buf, &buflen);
 447         if (f == NULL)
 448                 goto fail;
 449         ec_keyval_dump(f, keyval);
 450         fclose(f);
 451         f = NULL;
 452         free(buf);
 453         buf = NULL;
 454
 455         ret = ec_keyval_del(keyval, "key1");
 456         testres |= EC_TEST_CHECK(ret == 0, "cannot del key1");
 457         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 1,
 458                 "invalid keyval len");
 459         ret = ec_keyval_del(keyval, "key2");
 460         testres |= EC_TEST_CHECK(ret == 0, "cannot del key2");
 461         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0,
 462                 "invalid keyval len");
 463
 464         for (i = 0; i < 100; i++) {
 465                 char key[8];
 466                 snprintf(key, sizeof(key), "k%zd", i);
 467                 ret = ec_keyval_set(keyval, key, "val", NULL);
 468                 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 469         }
 470         dup = ec_keyval_dup(keyval);
 471         testres |= EC_TEST_CHECK(dup != NULL, "cannot duplicate keyval");
 472         if (dup != NULL) {
 473                 for (i = 0; i < 100; i++) {
 474                         char key[8];
 475                         snprintf(key, sizeof(key), "k%zd", i);
 476                         val = ec_keyval_get(dup, key);
 477                         testres |= EC_TEST_CHECK(
 478                                 val != NULL && !strcmp(val, "val"),
 479                                 "invalid keyval value");
 480                 }
 481                 ec_keyval_free(dup);
 482                 dup = NULL;
 483         }
 484
 485         count = 0;
 486         for (iter = ec_keyval_iter(keyval);
 487              iter != NULL;
 488              iter = ec_keyval_iter_next(iter)) {
 489                 count++;
 490         }
 491         testres |= EC_TEST_CHECK(count == 100, "invalid count in iterator");
 492
 493         /* einval */
 494         ret = ec_keyval_set(keyval, NULL, "val1", NULL);
 495         testres |= EC_TEST_CHECK(ret == -1, "should not be able to set key");
 496         val = ec_keyval_get(keyval, NULL);
 497         testres |= EC_TEST_CHECK(val == NULL, "get(NULL) should no success");
 498
 499         ec_keyval_free(keyval);
 500
 501         return testres;
 502
 503 fail:
 504         ec_keyval_free(keyval);
 505         if (f)
 506                 fclose(f);
 507         free(buf);
 508         return -1;
 509 }
 510 /* LCOV_EXCL_STOP */
 511
 512 static struct ec_test ec_keyval_test = {
 513         .name = "keyval",
 514         .test = ec_keyval_testcase,
 515 };
 516
 517 EC_TEST_REGISTER(ec_keyval_test);