lib/ecoli_keyval.c

   1 /*
   2  * Copyright (c) 2016, Olivier MATZ <zer0@droids-corp.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the University of California, Berkeley nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <sys/types.h>
  29 #include <sys/stat.h>
  30 #include <sys/queue.h>
  31 #include <stdlib.h>
  32 #include <stdint.h>
  33 #include <unistd.h>
  34 #include <assert.h>
  35 #include <errno.h>
  36 #include <fcntl.h>
  37
  38 #include <ecoli_init.h>
  39 #include <ecoli_malloc.h>
  40 #include <ecoli_log.h>
  41 #include <ecoli_test.h>
  42 #include <ecoli_murmurhash.h>
  43 #include <ecoli_keyval.h>
  44
  45 #define FACTOR 3
  46
  47 EC_LOG_TYPE_REGISTER(keyval);
  48
  49 static uint32_t ec_keyval_seed;
  50
  51 struct ec_keyval_elt {
  52         char *key;
  53         void *val;
  54         uint32_t hash;
  55         ec_keyval_elt_free_t free;
  56         unsigned int refcount;
  57 };
  58
  59 struct ec_keyval_elt_ref {
  60         LIST_ENTRY(ec_keyval_elt_ref) next;
  61         struct ec_keyval_elt *elt;
  62 };
  63
  64 LIST_HEAD(ec_keyval_elt_ref_list, ec_keyval_elt_ref);
  65
  66 struct ec_keyval {
  67         size_t len;
  68         size_t table_size;
  69         struct ec_keyval_elt_ref_list *table;
  70 };
  71
  72 struct ec_keyval *ec_keyval(void)
  73 {
  74         struct ec_keyval *keyval;
  75
  76         keyval = ec_calloc(1, sizeof(*keyval));
  77         if (keyval == NULL)
  78                 return NULL;
  79
  80         return keyval;
  81 }
  82
  83 static struct ec_keyval_elt_ref *
  84 ec_keyval_lookup(const struct ec_keyval *keyval, const char *key)
  85 {
  86         struct ec_keyval_elt_ref *ref;
  87         uint32_t h, mask = keyval->table_size - 1;
  88
  89         if (keyval == NULL || key == NULL) {
  90                 errno = EINVAL;
  91                 return NULL;
  92         }
  93         if (keyval->table_size == 0) {
  94                 errno = ENOENT;
  95                 return NULL;
  96         }
  97
  98         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
  99         LIST_FOREACH(ref, &keyval->table[h & mask], next) {
 100                 if (strcmp(ref->elt->key, key) == 0) {
 101                         errno = 0;
 102                         return ref;
 103                 }
 104         }
 105
 106         errno = ENOENT;
 107         return NULL;
 108 }
 109
 110 static void ec_keyval_elt_ref_free(struct ec_keyval_elt_ref *ref)
 111 {
 112         struct ec_keyval_elt *elt;
 113
 114         if (ref == NULL)
 115                 return;
 116
 117         elt = ref->elt;
 118         if (elt != NULL && --elt->refcount == 0) {
 119                 ec_free(elt->key);
 120                 if (elt->free != NULL)
 121                         elt->free(elt->val);
 122                 ec_free(elt);
 123         }
 124         ec_free(ref);
 125 }
 126
 127 bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
 128 {
 129         return !!ec_keyval_lookup(keyval, key);
 130 }
 131
 132 void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
 133 {
 134         struct ec_keyval_elt_ref *ref;
 135
 136         ref = ec_keyval_lookup(keyval, key);
 137         if (ref == NULL)
 138                 return NULL;
 139
 140         return ref->elt->val;
 141 }
 142
 143 int ec_keyval_del(struct ec_keyval *keyval, const char *key)
 144 {
 145         struct ec_keyval_elt_ref *ref;
 146
 147         ref = ec_keyval_lookup(keyval, key);
 148         if (ref == NULL)
 149                 return -1;
 150
 151         /* we could resize table here */
 152
 153         LIST_REMOVE(ref, next);
 154         ec_keyval_elt_ref_free(ref);
 155         keyval->len--;
 156
 157         return 0;
 158 }
 159
 160 static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
 161 {
 162         struct ec_keyval_elt_ref_list *new_table;
 163         struct ec_keyval_elt_ref *ref;
 164         size_t i;
 165
 166         if (new_size == 0 || (new_size & (new_size - 1))) {
 167                 errno = EINVAL;
 168                 return -1;
 169         }
 170
 171         new_table = ec_calloc(new_size, sizeof(*keyval->table));
 172         if (new_table == NULL)
 173                 return -1;
 174
 175         for (i = 0; i < keyval->table_size; i++) {
 176                 while (!LIST_EMPTY(&keyval->table[i])) {
 177                         ref = LIST_FIRST(&keyval->table[i]);
 178                         LIST_REMOVE(ref, next);
 179                         LIST_INSERT_HEAD(
 180                                 &new_table[ref->elt->hash & (new_size - 1)],
 181                                 ref, next);
 182                 }
 183         }
 184
 185         ec_free(keyval->table);
 186         keyval->table = new_table;
 187         keyval->table_size = new_size;
 188
 189         return 0;
 190 }
 191
 192 static int
 193 __ec_keyval_set(struct ec_keyval *keyval, struct ec_keyval_elt_ref *ref)
 194 {
 195         size_t new_size;
 196         uint32_t mask;
 197         int ret;
 198
 199         /* remove previous entry if any */
 200         ec_keyval_del(keyval, ref->elt->key);
 201
 202         if (keyval->len >= keyval->table_size) {
 203                 if (keyval->table_size != 0)
 204                         new_size =  keyval->table_size << FACTOR;
 205                 else
 206                         new_size =  1 << FACTOR;
 207                 ret = ec_keyval_table_resize(keyval, new_size);
 208                 if (ret < 0)
 209                         return ret;
 210         }
 211
 212         mask = keyval->table_size - 1;
 213         LIST_INSERT_HEAD(&keyval->table[ref->elt->hash & mask], ref, next);
 214         keyval->len++;
 215
 216         return 0;
 217 }
 218
 219 int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
 220         ec_keyval_elt_free_t free_cb)
 221 {
 222         struct ec_keyval_elt *elt = NULL;
 223         struct ec_keyval_elt_ref *ref = NULL;
 224         uint32_t h;
 225
 226         if (keyval == NULL || key == NULL) {
 227                 errno = EINVAL;
 228                 return -1;
 229         }
 230
 231         ref = ec_calloc(1, sizeof(*ref));
 232         if (ref == NULL)
 233                 goto fail;
 234
 235         elt = ec_calloc(1, sizeof(*elt));
 236         if (elt == NULL)
 237                 goto fail;
 238
 239         ref->elt = elt;
 240         elt->refcount = 1;
 241         elt->val = val;
 242         val = NULL;
 243         elt->free = free_cb;
 244         elt->key = ec_strdup(key);
 245         if (elt->key == NULL)
 246                 goto fail;
 247         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
 248         elt->hash = h;
 249
 250         if (__ec_keyval_set(keyval, ref) < 0)
 251                 goto fail;
 252
 253         return 0;
 254
 255 fail:
 256         if (free_cb != NULL && val != NULL)
 257                 free_cb(val);
 258         ec_keyval_elt_ref_free(ref);
 259         return -1;
 260 }
 261
 262 void ec_keyval_free(struct ec_keyval *keyval)
 263 {
 264         struct ec_keyval_elt_ref *ref;
 265         size_t i;
 266
 267         if (keyval == NULL)
 268                 return;
 269
 270         for (i = 0; i < keyval->table_size; i++) {
 271                 while (!LIST_EMPTY(&keyval->table[i])) {
 272                         ref = LIST_FIRST(&keyval->table[i]);
 273                         LIST_REMOVE(ref, next);
 274                         ec_keyval_elt_ref_free(ref);
 275                 }
 276         }
 277         ec_free(keyval->table);
 278         ec_free(keyval);
 279 }
 280
 281 size_t ec_keyval_len(const struct ec_keyval *keyval)
 282 {
 283         return keyval->len;
 284 }
 285
 286 void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
 287 {
 288         struct ec_keyval_elt_ref *ref;
 289         size_t i;
 290
 291         if (keyval == NULL) {
 292                 fprintf(out, "empty keyval\n");
 293                 return;
 294         }
 295
 296         fprintf(out, "keyval:\n");
 297         for (i = 0; i < keyval->table_size; i++) {
 298                 LIST_FOREACH(ref, &keyval->table[i], next) {
 299                         fprintf(out, "  %s: %p\n",
 300                                 ref->elt->key, ref->elt->val);
 301                 }
 302         }
 303 }
 304
 305 struct ec_keyval *ec_keyval_dup(const struct ec_keyval *keyval)
 306 {
 307         struct ec_keyval *dup = NULL;
 308         struct ec_keyval_elt_ref *ref, *dup_ref = NULL;
 309         size_t i;
 310
 311         dup = ec_keyval();
 312         if (dup == NULL)
 313                 return NULL;
 314
 315         for (i = 0; i < keyval->table_size; i++) {
 316                 LIST_FOREACH(ref, &keyval->table[i], next) {
 317                         dup_ref = ec_calloc(1, sizeof(*ref));
 318                         if (dup_ref == NULL)
 319                                 goto fail;
 320                         dup_ref->elt = ref->elt;
 321                         ref->elt->refcount++;
 322
 323                         if (__ec_keyval_set(dup, dup_ref) < 0)
 324                                 goto fail;
 325                 }
 326         }
 327
 328         return dup;
 329
 330 fail:
 331         ec_keyval_elt_ref_free(dup_ref);
 332         ec_keyval_free(dup);
 333         return NULL;
 334 }
 335
 336 static int ec_keyval_init_func(void)
 337 {
 338         int fd;
 339         ssize_t ret;
 340
 341         fd = open("/dev/urandom", 0);
 342         if (fd == -1) {
 343                 fprintf(stderr, "failed to open /dev/urandom\n");
 344                 return -1;
 345         }
 346         ret = read(fd, &ec_keyval_seed, sizeof(ec_keyval_seed));
 347         if (ret != sizeof(ec_keyval_seed)) {
 348                 fprintf(stderr, "failed to read /dev/urandom\n");
 349                 return -1;
 350         }
 351         close(fd);
 352         return 0;
 353 }
 354
 355 static struct ec_init ec_keyval_init = {
 356         .init = ec_keyval_init_func,
 357         .priority = 50,
 358 };
 359
 360 EC_INIT_REGISTER(ec_keyval_init);
 361
 362 /* LCOV_EXCL_START */
 363 static int ec_keyval_testcase(void)
 364 {
 365         struct ec_keyval *keyval, *dup;
 366         char *val;
 367         size_t i;
 368         int ret, testres = 0;
 369
 370         keyval = ec_keyval();
 371         if (keyval == NULL) {
 372                 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
 373                 return -1;
 374         }
 375
 376         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0, "bad keyval len");
 377         ret = ec_keyval_set(keyval, "key1", "val1", NULL);
 378         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 379         ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
 380         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 381         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2, "bad keyval len");
 382
 383         val = ec_keyval_get(keyval, "key1");
 384         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val1"),
 385                                 "invalid keyval value");
 386         val = ec_keyval_get(keyval, "key2");
 387         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val2"),
 388                                 "invalid keyval value");
 389         val = ec_keyval_get(keyval, "key3");
 390         testres |= EC_TEST_CHECK(val == NULL, "key3 should be NULL");
 391
 392         ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
 393         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 394         ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
 395                         ec_free_func);
 396         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 397         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2,
 398                                 "bad keyval len");
 399
 400         val = ec_keyval_get(keyval, "key1");
 401         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val1"),
 402                 "invalid keyval value");
 403         val = ec_keyval_get(keyval, "key2");
 404         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val2"),
 405                 "invalid keyval value");
 406         testres |= EC_TEST_CHECK(ec_keyval_has_key(keyval, "key1"),
 407                 "key1 should be in keyval");
 408
 409         ret = ec_keyval_del(keyval, "key1");
 410         testres |= EC_TEST_CHECK(ret == 0, "cannot del key");
 411         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 1,
 412                 "invalid keyval len");
 413
 414         ec_keyval_dump(stdout, NULL);
 415         ec_keyval_dump(stdout, keyval);
 416
 417         for (i = 0; i < 100; i++) {
 418                 char key[8];
 419                 snprintf(key, sizeof(key), "k%zd", i);
 420                 ret = ec_keyval_set(keyval, key, "val", NULL);
 421                 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 422         }
 423         dup = ec_keyval_dup(keyval);
 424         testres |= EC_TEST_CHECK(dup != NULL, "cannot duplicate keyval");
 425         if (dup != NULL) {
 426                 for (i = 0; i < 100; i++) {
 427                         char key[8];
 428                         snprintf(key, sizeof(key), "k%zd", i);
 429                         val = ec_keyval_get(dup, key);
 430                         testres |= EC_TEST_CHECK(
 431                                 val != NULL && !strcmp(val, "val"),
 432                                 "invalid keyval value");
 433                 }
 434                 ec_keyval_free(dup);
 435                 dup = NULL;
 436         }
 437
 438         /* einval */
 439         ret = ec_keyval_set(keyval, NULL, "val1", NULL);
 440         testres |= EC_TEST_CHECK(ret == -1, "should not be able to set key");
 441         val = ec_keyval_get(keyval, NULL);
 442         testres |= EC_TEST_CHECK(val == NULL, "get(NULL) should no success");
 443
 444         ec_keyval_free(keyval);
 445
 446         return testres;
 447 }
 448 /* LCOV_EXCL_STOP */
 449
 450 static struct ec_test ec_keyval_test = {
 451         .name = "keyval",
 452         .test = ec_keyval_testcase,
 453 };
 454
 455 EC_TEST_REGISTER(ec_keyval_test);