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