lib/hashtable.c

   1 // SPDX-License-Identifier: LGPL-2.1+
   2 /*
   3  * This implementation is based on code from uClibc-0.9.30.3 but was
   4  * modified and extended for use within U-Boot.
   5  *
   6  * Copyright (C) 2010-2013 Wolfgang Denk <wd@denx.de>
   7  *
   8  * Original license header:
   9  *
  10  * Copyright (C) 1993, 1995, 1996, 1997, 2002 Free Software Foundation, Inc.
  11  * This file is part of the GNU C Library.
  12  * Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1993.
  13  */
  14
  15 #include <errno.h>
  16 #include <log.h>
  17 #include <malloc.h>
  18 #include <sort.h>
  19
  20 #ifdef USE_HOSTCC               /* HOST build */
  21 # include <string.h>
  22 # include <assert.h>
  23 # include <ctype.h>
  24
  25 # ifndef debug
  26 #  ifdef DEBUG
  27 #   define debug(fmt,args...)   printf(fmt ,##args)
  28 #  else
  29 #   define debug(fmt,args...)
  30 #  endif
  31 # endif
  32 #else                           /* U-Boot build */
  33 # include <common.h>
  34 # include <linux/string.h>
  35 # include <linux/ctype.h>
  36 #endif
  37
  38 #ifndef CONFIG_ENV_MIN_ENTRIES  /* minimum number of entries */
  39 #define CONFIG_ENV_MIN_ENTRIES 64
  40 #endif
  41 #ifndef CONFIG_ENV_MAX_ENTRIES  /* maximum number of entries */
  42 #define CONFIG_ENV_MAX_ENTRIES 512
  43 #endif
  44
  45 #define USED_FREE 0
  46 #define USED_DELETED -1
  47
  48 #include <env_callback.h>
  49 #include <env_flags.h>
  50 #include <search.h>
  51 #include <slre.h>
  52
  53 /*
  54  * [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986
  55  * [Knuth]            The Art of Computer Programming, part 3 (6.4)
  56  */
  57
  58 /*
  59  * The reentrant version has no static variables to maintain the state.
  60  * Instead the interface of all functions is extended to take an argument
  61  * which describes the current status.
  62  */
  63
  64 struct env_entry_node {
  65         int used;
  66         struct env_entry entry;
  67 };
  68
  69
  70 static void _hdelete(const char *key, struct hsearch_data *htab,
  71                      struct env_entry *ep, int idx);
  72
  73 /*
  74  * hcreate()
  75  */
  76
  77 /*
  78  * For the used double hash method the table size has to be a prime. To
  79  * correct the user given table size we need a prime test.  This trivial
  80  * algorithm is adequate because
  81  * a)  the code is (most probably) called a few times per program run and
  82  * b)  the number is small because the table must fit in the core
  83  * */
  84 static int isprime(unsigned int number)
  85 {
  86         /* no even number will be passed */
  87         unsigned int div = 3;
  88
  89         while (div * div < number && number % div != 0)
  90                 div += 2;
  91
  92         return number % div != 0;
  93 }
  94
  95 /*
  96  * Before using the hash table we must allocate memory for it.
  97  * Test for an existing table are done. We allocate one element
  98  * more as the found prime number says. This is done for more effective
  99  * indexing as explained in the comment for the hsearch function.
 100  * The contents of the table is zeroed, especially the field used
 101  * becomes zero.
 102  */
 103
 104 int hcreate_r(size_t nel, struct hsearch_data *htab)
 105 {
 106         /* Test for correct arguments.  */
 107         if (htab == NULL) {
 108                 __set_errno(EINVAL);
 109                 return 0;
 110         }
 111
 112         /* There is still another table active. Return with error. */
 113         if (htab->table != NULL) {
 114                 __set_errno(EINVAL);
 115                 return 0;
 116         }
 117
 118         /* Change nel to the first prime number not smaller as nel. */
 119         nel |= 1;               /* make odd */
 120         while (!isprime(nel))
 121                 nel += 2;
 122
 123         htab->size = nel;
 124         htab->filled = 0;
 125
 126         /* allocate memory and zero out */
 127         htab->table = (struct env_entry_node *)calloc(htab->size + 1,
 128                                                 sizeof(struct env_entry_node));
 129         if (htab->table == NULL) {
 130                 __set_errno(ENOMEM);
 131                 return 0;
 132         }
 133
 134         /* everything went alright */
 135         return 1;
 136 }
 137
 138
 139 /*
 140  * hdestroy()
 141  */
 142
 143 /*
 144  * After using the hash table it has to be destroyed. The used memory can
 145  * be freed and the local static variable can be marked as not used.
 146  */
 147
 148 void hdestroy_r(struct hsearch_data *htab)
 149 {
 150         int i;
 151
 152         /* Test for correct arguments.  */
 153         if (htab == NULL) {
 154                 __set_errno(EINVAL);
 155                 return;
 156         }
 157
 158         /* free used memory */
 159         for (i = 1; i <= htab->size; ++i) {
 160                 if (htab->table[i].used > 0) {
 161                         struct env_entry *ep = &htab->table[i].entry;
 162
 163                         free((void *)ep->key);
 164                         free(ep->data);
 165                 }
 166         }
 167         free(htab->table);
 168
 169         /* the sign for an existing table is an value != NULL in htable */
 170         htab->table = NULL;
 171 }
 172
 173 /*
 174  * hsearch()
 175  */
 176
 177 /*
 178  * This is the search function. It uses double hashing with open addressing.
 179  * The argument item.key has to be a pointer to an zero terminated, most
 180  * probably strings of chars. The function for generating a number of the
 181  * strings is simple but fast. It can be replaced by a more complex function
 182  * like ajw (see [Aho,Sethi,Ullman]) if the needs are shown.
 183  *
 184  * We use an trick to speed up the lookup. The table is created by hcreate
 185  * with one more element available. This enables us to use the index zero
 186  * special. This index will never be used because we store the first hash
 187  * index in the field used where zero means not used. Every other value
 188  * means used. The used field can be used as a first fast comparison for
 189  * equality of the stored and the parameter value. This helps to prevent
 190  * unnecessary expensive calls of strcmp.
 191  *
 192  * This implementation differs from the standard library version of
 193  * this function in a number of ways:
 194  *
 195  * - While the standard version does not make any assumptions about
 196  *   the type of the stored data objects at all, this implementation
 197  *   works with NUL terminated strings only.
 198  * - Instead of storing just pointers to the original objects, we
 199  *   create local copies so the caller does not need to care about the
 200  *   data any more.
 201  * - The standard implementation does not provide a way to update an
 202  *   existing entry.  This version will create a new entry or update an
 203  *   existing one when both "action == ENV_ENTER" and "item.data != NULL".
 204  * - Instead of returning 1 on success, we return the index into the
 205  *   internal hash table, which is also guaranteed to be positive.
 206  *   This allows us direct access to the found hash table slot for
 207  *   example for functions like hdelete().
 208  */
 209
 210 int hmatch_r(const char *match, int last_idx, struct env_entry **retval,
 211              struct hsearch_data *htab)
 212 {
 213         unsigned int idx;
 214         size_t key_len = strlen(match);
 215
 216         for (idx = last_idx + 1; idx < htab->size; ++idx) {
 217                 if (htab->table[idx].used <= 0)
 218                         continue;
 219                 if (!strncmp(match, htab->table[idx].entry.key, key_len)) {
 220                         *retval = &htab->table[idx].entry;
 221                         return idx;
 222                 }
 223         }
 224
 225         __set_errno(ESRCH);
 226         *retval = NULL;
 227         return 0;
 228 }
 229
 230 static int
 231 do_callback(const struct env_entry *e, const char *name, const char *value,
 232             enum env_op op, int flags)
 233 {
 234 #ifndef CONFIG_SPL_BUILD
 235         if (e->callback)
 236                 return e->callback(name, value, op, flags);
 237 #endif
 238         return 0;
 239 }
 240
 241 /*
 242  * Compare an existing entry with the desired key, and overwrite if the action
 243  * is ENV_ENTER.  This is simply a helper function for hsearch_r().
 244  */
 245 static inline int _compare_and_overwrite_entry(struct env_entry item,
 246                 enum env_action action, struct env_entry **retval,
 247                 struct hsearch_data *htab, int flag, unsigned int hval,
 248                 unsigned int idx)
 249 {
 250         if (htab->table[idx].used == hval
 251             && strcmp(item.key, htab->table[idx].entry.key) == 0) {
 252                 /* Overwrite existing value? */
 253                 if (action == ENV_ENTER && item.data) {
 254                         /* check for permission */
 255                         if (htab->change_ok != NULL && htab->change_ok(
 256                             &htab->table[idx].entry, item.data,
 257                             env_op_overwrite, flag)) {
 258                                 debug("change_ok() rejected setting variable "
 259                                         "%s, skipping it!\n", item.key);
 260                                 __set_errno(EPERM);
 261                                 *retval = NULL;
 262                                 return 0;
 263                         }
 264
 265                         /* If there is a callback, call it */
 266                         if (do_callback(&htab->table[idx].entry, item.key,
 267                                         item.data, env_op_overwrite, flag)) {
 268                                 debug("callback() rejected setting variable "
 269                                         "%s, skipping it!\n", item.key);
 270                                 __set_errno(EINVAL);
 271                                 *retval = NULL;
 272                                 return 0;
 273                         }
 274
 275                         free(htab->table[idx].entry.data);
 276                         htab->table[idx].entry.data = strdup(item.data);
 277                         if (!htab->table[idx].entry.data) {
 278                                 __set_errno(ENOMEM);
 279                                 *retval = NULL;
 280                                 return 0;
 281                         }
 282                 }
 283                 /* return found entry */
 284                 *retval = &htab->table[idx].entry;
 285                 return idx;
 286         }
 287         /* keep searching */
 288         return -1;
 289 }
 290
 291 int hsearch_r(struct env_entry item, enum env_action action,
 292               struct env_entry **retval, struct hsearch_data *htab, int flag)
 293 {
 294         unsigned int hval;
 295         unsigned int count;
 296         unsigned int len = strlen(item.key);
 297         unsigned int idx;
 298         unsigned int first_deleted = 0;
 299         int ret;
 300
 301         /* Compute an value for the given string. Perhaps use a better method. */
 302         hval = len;
 303         count = len;
 304         while (count-- > 0) {
 305                 hval <<= 4;
 306                 hval += item.key[count];
 307         }
 308
 309         /*
 310          * First hash function:
 311          * simply take the modul but prevent zero.
 312          */
 313         hval %= htab->size;
 314         if (hval == 0)
 315                 ++hval;
 316
 317         /* The first index tried. */
 318         idx = hval;
 319
 320         if (htab->table[idx].used) {
 321                 /*
 322                  * Further action might be required according to the
 323                  * action value.
 324                  */
 325                 unsigned hval2;
 326
 327                 if (htab->table[idx].used == USED_DELETED)
 328                         first_deleted = idx;
 329
 330                 ret = _compare_and_overwrite_entry(item, action, retval, htab,
 331                         flag, hval, idx);
 332                 if (ret != -1)
 333                         return ret;
 334
 335                 /*
 336                  * Second hash function:
 337                  * as suggested in [Knuth]
 338                  */
 339                 hval2 = 1 + hval % (htab->size - 2);
 340
 341                 do {
 342                         /*
 343                          * Because SIZE is prime this guarantees to
 344                          * step through all available indices.
 345                          */
 346                         if (idx <= hval2)
 347                                 idx = htab->size + idx - hval2;
 348                         else
 349                                 idx -= hval2;
 350
 351                         /*
 352                          * If we visited all entries leave the loop
 353                          * unsuccessfully.
 354                          */
 355                         if (idx == hval)
 356                                 break;
 357
 358                         if (htab->table[idx].used == USED_DELETED
 359                             && !first_deleted)
 360                                 first_deleted = idx;
 361
 362                         /* If entry is found use it. */
 363                         ret = _compare_and_overwrite_entry(item, action, retval,
 364                                 htab, flag, hval, idx);
 365                         if (ret != -1)
 366                                 return ret;
 367                 }
 368                 while (htab->table[idx].used != USED_FREE);
 369         }
 370
 371         /* An empty bucket has been found. */
 372         if (action == ENV_ENTER) {
 373                 /*
 374                  * If table is full and another entry should be
 375                  * entered return with error.
 376                  */
 377                 if (htab->filled == htab->size) {
 378                         __set_errno(ENOMEM);
 379                         *retval = NULL;
 380                         return 0;
 381                 }
 382
 383                 /*
 384                  * Create new entry;
 385                  * create copies of item.key and item.data
 386                  */
 387                 if (first_deleted)
 388                         idx = first_deleted;
 389
 390                 htab->table[idx].used = hval;
 391                 htab->table[idx].entry.key = strdup(item.key);
 392                 htab->table[idx].entry.data = strdup(item.data);
 393                 if (!htab->table[idx].entry.key ||
 394                     !htab->table[idx].entry.data) {
 395                         __set_errno(ENOMEM);
 396                         *retval = NULL;
 397                         return 0;
 398                 }
 399
 400                 ++htab->filled;
 401
 402                 /* This is a new entry, so look up a possible callback */
 403                 env_callback_init(&htab->table[idx].entry);
 404                 /* Also look for flags */
 405                 env_flags_init(&htab->table[idx].entry);
 406
 407                 /* check for permission */
 408                 if (htab->change_ok != NULL && htab->change_ok(
 409                     &htab->table[idx].entry, item.data, env_op_create, flag)) {
 410                         debug("change_ok() rejected setting variable "
 411                                 "%s, skipping it!\n", item.key);
 412                         _hdelete(item.key, htab, &htab->table[idx].entry, idx);
 413                         __set_errno(EPERM);
 414                         *retval = NULL;
 415                         return 0;
 416                 }
 417
 418                 /* If there is a callback, call it */
 419                 if (do_callback(&htab->table[idx].entry, item.key, item.data,
 420                                 env_op_create, flag)) {
 421                         debug("callback() rejected setting variable "
 422                                 "%s, skipping it!\n", item.key);
 423                         _hdelete(item.key, htab, &htab->table[idx].entry, idx);
 424                         __set_errno(EINVAL);
 425                         *retval = NULL;
 426                         return 0;
 427                 }
 428
 429                 /* return new entry */
 430                 *retval = &htab->table[idx].entry;
 431                 return 1;
 432         }
 433
 434         __set_errno(ESRCH);
 435         *retval = NULL;
 436         return 0;
 437 }
 438
 439
 440 /*
 441  * hdelete()
 442  */
 443
 444 /*
 445  * The standard implementation of hsearch(3) does not provide any way
 446  * to delete any entries from the hash table.  We extend the code to
 447  * do that.
 448  */
 449
 450 static void _hdelete(const char *key, struct hsearch_data *htab,
 451                      struct env_entry *ep, int idx)
 452 {
 453         /* free used entry */
 454         debug("hdelete: DELETING key \"%s\"\n", key);
 455         free((void *)ep->key);
 456         free(ep->data);
 457         ep->flags = 0;
 458         htab->table[idx].used = USED_DELETED;
 459
 460         --htab->filled;
 461 }
 462
 463 int hdelete_r(const char *key, struct hsearch_data *htab, int flag)
 464 {
 465         struct env_entry e, *ep;
 466         int idx;
 467
 468         debug("hdelete: DELETE key \"%s\"\n", key);
 469
 470         e.key = (char *)key;
 471
 472         idx = hsearch_r(e, ENV_FIND, &ep, htab, 0);
 473         if (idx == 0) {
 474                 __set_errno(ESRCH);
 475                 return -ENOENT; /* not found */
 476         }
 477
 478         /* Check for permission */
 479         if (htab->change_ok != NULL &&
 480             htab->change_ok(ep, NULL, env_op_delete, flag)) {
 481                 debug("change_ok() rejected deleting variable "
 482                         "%s, skipping it!\n", key);
 483                 __set_errno(EPERM);
 484                 return -EPERM;
 485         }
 486
 487         /* If there is a callback, call it */
 488         if (do_callback(&htab->table[idx].entry, key, NULL,
 489                         env_op_delete, flag)) {
 490                 debug("callback() rejected deleting variable "
 491                         "%s, skipping it!\n", key);
 492                 __set_errno(EINVAL);
 493                 return -EINVAL;
 494         }
 495
 496         _hdelete(key, htab, ep, idx);
 497
 498         return 0;
 499 }
 500
 501 #if !(defined(CONFIG_SPL_BUILD) && !defined(CONFIG_SPL_SAVEENV))
 502 /*
 503  * hexport()
 504  */
 505
 506 /*
 507  * Export the data stored in the hash table in linearized form.
 508  *
 509  * Entries are exported as "name=value" strings, separated by an
 510  * arbitrary (non-NUL, of course) separator character. This allows to
 511  * use this function both when formatting the U-Boot environment for
 512  * external storage (using '\0' as separator), but also when using it
 513  * for the "printenv" command to print all variables, simply by using
 514  * as '\n" as separator. This can also be used for new features like
 515  * exporting the environment data as text file, including the option
 516  * for later re-import.
 517  *
 518  * The entries in the result list will be sorted by ascending key
 519  * values.
 520  *
 521  * If the separator character is different from NUL, then any
 522  * separator characters and backslash characters in the values will
 523  * be escaped by a preceding backslash in output. This is needed for
 524  * example to enable multi-line values, especially when the output
 525  * shall later be parsed (for example, for re-import).
 526  *
 527  * There are several options how the result buffer is handled:
 528  *
 529  * *resp  size
 530  * -----------
 531  *  NULL    0   A string of sufficient length will be allocated.
 532  *  NULL   >0   A string of the size given will be
 533  *              allocated. An error will be returned if the size is
 534  *              not sufficient.  Any unused bytes in the string will
 535  *              be '\0'-padded.
 536  * !NULL    0   The user-supplied buffer will be used. No length
 537  *              checking will be performed, i. e. it is assumed that
 538  *              the buffer size will always be big enough. DANGEROUS.
 539  * !NULL   >0   The user-supplied buffer will be used. An error will
 540  *              be returned if the size is not sufficient.  Any unused
 541  *              bytes in the string will be '\0'-padded.
 542  */
 543
 544 static int cmpkey(const void *p1, const void *p2)
 545 {
 546         struct env_entry *e1 = *(struct env_entry **)p1;
 547         struct env_entry *e2 = *(struct env_entry **)p2;
 548
 549         return (strcmp(e1->key, e2->key));
 550 }
 551
 552 static int match_string(int flag, const char *str, const char *pat, void *priv)
 553 {
 554         switch (flag & H_MATCH_METHOD) {
 555         case H_MATCH_IDENT:
 556                 if (strcmp(str, pat) == 0)
 557                         return 1;
 558                 break;
 559         case H_MATCH_SUBSTR:
 560                 if (strstr(str, pat))
 561                         return 1;
 562                 break;
 563 #ifdef CONFIG_REGEX
 564         case H_MATCH_REGEX:
 565                 {
 566                         struct slre *slrep = (struct slre *)priv;
 567
 568                         if (slre_match(slrep, str, strlen(str), NULL))
 569                                 return 1;
 570                 }
 571                 break;
 572 #endif
 573         default:
 574                 printf("## ERROR: unsupported match method: 0x%02x\n",
 575                         flag & H_MATCH_METHOD);
 576                 break;
 577         }
 578         return 0;
 579 }
 580
 581 static int match_entry(struct env_entry *ep, int flag, int argc,
 582                        char *const argv[])
 583 {
 584         int arg;
 585         void *priv = NULL;
 586
 587         for (arg = 0; arg < argc; ++arg) {
 588 #ifdef CONFIG_REGEX
 589                 struct slre slre;
 590
 591                 if (slre_compile(&slre, argv[arg]) == 0) {
 592                         printf("Error compiling regex: %s\n", slre.err_str);
 593                         return 0;
 594                 }
 595
 596                 priv = (void *)&slre;
 597 #endif
 598                 if (flag & H_MATCH_KEY) {
 599                         if (match_string(flag, ep->key, argv[arg], priv))
 600                                 return 1;
 601                 }
 602                 if (flag & H_MATCH_DATA) {
 603                         if (match_string(flag, ep->data, argv[arg], priv))
 604                                 return 1;
 605                 }
 606         }
 607         return 0;
 608 }
 609
 610 ssize_t hexport_r(struct hsearch_data *htab, const char sep, int flag,
 611                  char **resp, size_t size,
 612                  int argc, char *const argv[])
 613 {
 614         struct env_entry *list[htab->size];
 615         char *res, *p;
 616         size_t totlen;
 617         int i, n;
 618
 619         /* Test for correct arguments.  */
 620         if ((resp == NULL) || (htab == NULL)) {
 621                 __set_errno(EINVAL);
 622                 return (-1);
 623         }
 624
 625         debug("EXPORT  table = %p, htab.size = %d, htab.filled = %d, size = %lu\n",
 626               htab, htab->size, htab->filled, (ulong)size);
 627         /*
 628          * Pass 1:
 629          * search used entries,
 630          * save addresses and compute total length
 631          */
 632         for (i = 1, n = 0, totlen = 0; i <= htab->size; ++i) {
 633
 634                 if (htab->table[i].used > 0) {
 635                         struct env_entry *ep = &htab->table[i].entry;
 636                         int found = match_entry(ep, flag, argc, argv);
 637
 638                         if ((argc > 0) && (found == 0))
 639                                 continue;
 640
 641                         if ((flag & H_HIDE_DOT) && ep->key[0] == '.')
 642                                 continue;
 643
 644                         list[n++] = ep;
 645
 646                         totlen += strlen(ep->key);
 647
 648                         if (sep == '\0') {
 649                                 totlen += strlen(ep->data);
 650                         } else {        /* check if escapes are needed */
 651                                 char *s = ep->data;
 652
 653                                 while (*s) {
 654                                         ++totlen;
 655                                         /* add room for needed escape chars */
 656                                         if ((*s == sep) || (*s == '\\'))
 657                                                 ++totlen;
 658                                         ++s;
 659                                 }
 660                         }
 661                         totlen += 2;    /* for '=' and 'sep' char */
 662                 }
 663         }
 664
 665 #ifdef DEBUG
 666         /* Pass 1a: print unsorted list */
 667         printf("Unsorted: n=%d\n", n);
 668         for (i = 0; i < n; ++i) {
 669                 printf("\t%3d: %p ==> %-10s => %s\n",
 670                        i, list[i], list[i]->key, list[i]->data);
 671         }
 672 #endif
 673
 674         /* Sort list by keys */
 675         qsort(list, n, sizeof(struct env_entry *), cmpkey);
 676
 677         /* Check if the user supplied buffer size is sufficient */
 678         if (size) {
 679                 if (size < totlen + 1) {        /* provided buffer too small */
 680                         printf("Env export buffer too small: %lu, but need %lu\n",
 681                                (ulong)size, (ulong)totlen + 1);
 682                         __set_errno(ENOMEM);
 683                         return (-1);
 684                 }
 685         } else {
 686                 size = totlen + 1;
 687         }
 688
 689         /* Check if the user provided a buffer */
 690         if (*resp) {
 691                 /* yes; clear it */
 692                 res = *resp;
 693                 memset(res, '\0', size);
 694         } else {
 695                 /* no, allocate and clear one */
 696                 *resp = res = calloc(1, size);
 697                 if (res == NULL) {
 698                         __set_errno(ENOMEM);
 699                         return (-1);
 700                 }
 701         }
 702         /*
 703          * Pass 2:
 704          * export sorted list of result data
 705          */
 706         for (i = 0, p = res; i < n; ++i) {
 707                 const char *s;
 708
 709                 s = list[i]->key;
 710                 while (*s)
 711                         *p++ = *s++;
 712                 *p++ = '=';
 713
 714                 s = list[i]->data;
 715
 716                 while (*s) {
 717                         if ((*s == sep) || (*s == '\\'))
 718                                 *p++ = '\\';    /* escape */
 719                         *p++ = *s++;
 720                 }
 721                 *p++ = sep;
 722         }
 723         *p = '\0';              /* terminate result */
 724
 725         return size;
 726 }
 727 #endif
 728
 729
 730 /*
 731  * himport()
 732  */
 733
 734 /*
 735  * Check whether variable 'name' is amongst vars[],
 736  * and remove all instances by setting the pointer to NULL
 737  */
 738 static int drop_var_from_set(const char *name, int nvars, char * vars[])
 739 {
 740         int i = 0;
 741         int res = 0;
 742
 743         /* No variables specified means process all of them */
 744         if (nvars == 0)
 745                 return 1;
 746
 747         for (i = 0; i < nvars; i++) {
 748                 if (vars[i] == NULL)
 749                         continue;
 750                 /* If we found it, delete all of them */
 751                 if (!strcmp(name, vars[i])) {
 752                         vars[i] = NULL;
 753                         res = 1;
 754                 }
 755         }
 756         if (!res)
 757                 debug("Skipping non-listed variable %s\n", name);
 758
 759         return res;
 760 }
 761
 762 /*
 763  * Import linearized data into hash table.
 764  *
 765  * This is the inverse function to hexport(): it takes a linear list
 766  * of "name=value" pairs and creates hash table entries from it.
 767  *
 768  * Entries without "value", i. e. consisting of only "name" or
 769  * "name=", will cause this entry to be deleted from the hash table.
 770  *
 771  * The "flag" argument can be used to control the behaviour: when the
 772  * H_NOCLEAR bit is set, then an existing hash table will kept, i. e.
 773  * new data will be added to an existing hash table; otherwise, if no
 774  * vars are passed, old data will be discarded and a new hash table
 775  * will be created. If vars are passed, passed vars that are not in
 776  * the linear list of "name=value" pairs will be removed from the
 777  * current hash table.
 778  *
 779  * The separator character for the "name=value" pairs can be selected,
 780  * so we both support importing from externally stored environment
 781  * data (separated by NUL characters) and from plain text files
 782  * (entries separated by newline characters).
 783  *
 784  * To allow for nicely formatted text input, leading white space
 785  * (sequences of SPACE and TAB chars) is ignored, and entries starting
 786  * (after removal of any leading white space) with a '#' character are
 787  * considered comments and ignored.
 788  *
 789  * [NOTE: this means that a variable name cannot start with a '#'
 790  * character.]
 791  *
 792  * When using a non-NUL separator character, backslash is used as
 793  * escape character in the value part, allowing for example for
 794  * multi-line values.
 795  *
 796  * In theory, arbitrary separator characters can be used, but only
 797  * '\0' and '\n' have really been tested.
 798  */
 799
 800 int himport_r(struct hsearch_data *htab,
 801                 const char *env, size_t size, const char sep, int flag,
 802                 int crlf_is_lf, int nvars, char * const vars[])
 803 {
 804         char *data, *sp, *dp, *name, *value;
 805         char *localvars[nvars];
 806         int i;
 807
 808         /* Test for correct arguments.  */
 809         if (htab == NULL) {
 810                 __set_errno(EINVAL);
 811                 return 0;
 812         }
 813
 814         /* we allocate new space to make sure we can write to the array */
 815         if ((data = malloc(size + 1)) == NULL) {
 816                 debug("himport_r: can't malloc %lu bytes\n", (ulong)size + 1);
 817                 __set_errno(ENOMEM);
 818                 return 0;
 819         }
 820         memcpy(data, env, size);
 821         data[size] = '\0';
 822         dp = data;
 823
 824         /* make a local copy of the list of variables */
 825         if (nvars)
 826                 memcpy(localvars, vars, sizeof(vars[0]) * nvars);
 827
 828 #if CONFIG_IS_ENABLED(ENV_APPEND)
 829         flag |= H_NOCLEAR;
 830 #endif
 831
 832         if ((flag & H_NOCLEAR) == 0 && !nvars) {
 833                 /* Destroy old hash table if one exists */
 834                 debug("Destroy Hash Table: %p table = %p\n", htab,
 835                        htab->table);
 836                 if (htab->table)
 837                         hdestroy_r(htab);
 838         }
 839
 840         /*
 841          * Create new hash table (if needed).  The computation of the hash
 842          * table size is based on heuristics: in a sample of some 70+
 843          * existing systems we found an average size of 39+ bytes per entry
 844          * in the environment (for the whole key=value pair). Assuming a
 845          * size of 8 per entry (= safety factor of ~5) should provide enough
 846          * safety margin for any existing environment definitions and still
 847          * allow for more than enough dynamic additions. Note that the
 848          * "size" argument is supposed to give the maximum environment size
 849          * (CONFIG_ENV_SIZE).  This heuristics will result in
 850          * unreasonably large numbers (and thus memory footprint) for
 851          * big flash environments (>8,000 entries for 64 KB
 852          * environment size), so we clip it to a reasonable value.
 853          * On the other hand we need to add some more entries for free
 854          * space when importing very small buffers. Both boundaries can
 855          * be overwritten in the board config file if needed.
 856          */
 857
 858         if (!htab->table) {
 859                 int nent = CONFIG_ENV_MIN_ENTRIES + size / 8;
 860
 861                 if (nent > CONFIG_ENV_MAX_ENTRIES)
 862                         nent = CONFIG_ENV_MAX_ENTRIES;
 863
 864                 debug("Create Hash Table: N=%d\n", nent);
 865
 866                 if (hcreate_r(nent, htab) == 0) {
 867                         free(data);
 868                         return 0;
 869                 }
 870         }
 871
 872         if (!size) {
 873                 free(data);
 874                 return 1;               /* everything OK */
 875         }
 876         if(crlf_is_lf) {
 877                 /* Remove Carriage Returns in front of Line Feeds */
 878                 unsigned ignored_crs = 0;
 879                 for(;dp < data + size && *dp; ++dp) {
 880                         if(*dp == '\r' &&
 881                            dp < data + size - 1 && *(dp+1) == '\n')
 882                                 ++ignored_crs;
 883                         else
 884                                 *(dp-ignored_crs) = *dp;
 885                 }
 886                 size -= ignored_crs;
 887                 dp = data;
 888         }
 889         /* Parse environment; allow for '\0' and 'sep' as separators */
 890         do {
 891                 struct env_entry e, *rv;
 892
 893                 /* skip leading white space */
 894                 while (isblank(*dp))
 895                         ++dp;
 896
 897                 /* skip comment lines */
 898                 if (*dp == '#') {
 899                         while (*dp && (*dp != sep))
 900                                 ++dp;
 901                         ++dp;
 902                         continue;
 903                 }
 904
 905                 /* parse name */
 906                 for (name = dp; *dp != '=' && *dp && *dp != sep; ++dp)
 907                         ;
 908
 909                 /* deal with "name" and "name=" entries (delete var) */
 910                 if (*dp == '\0' || *(dp + 1) == '\0' ||
 911                     *dp == sep || *(dp + 1) == sep) {
 912                         if (*dp == '=')
 913                                 *dp++ = '\0';
 914                         *dp++ = '\0';   /* terminate name */
 915
 916                         debug("DELETE CANDIDATE: \"%s\"\n", name);
 917                         if (!drop_var_from_set(name, nvars, localvars))
 918                                 continue;
 919
 920                         if (hdelete_r(name, htab, flag))
 921                                 debug("DELETE ERROR ##############################\n");
 922
 923                         continue;
 924                 }
 925                 *dp++ = '\0';   /* terminate name */
 926
 927                 /* parse value; deal with escapes */
 928                 for (value = sp = dp; *dp && (*dp != sep); ++dp) {
 929                         if ((*dp == '\\') && *(dp + 1))
 930                                 ++dp;
 931                         *sp++ = *dp;
 932                 }
 933                 *sp++ = '\0';   /* terminate value */
 934                 ++dp;
 935
 936                 if (*name == 0) {
 937                         debug("INSERT: unable to use an empty key\n");
 938                         __set_errno(EINVAL);
 939                         free(data);
 940                         return 0;
 941                 }
 942
 943                 /* Skip variables which are not supposed to be processed */
 944                 if (!drop_var_from_set(name, nvars, localvars))
 945                         continue;
 946
 947                 /* enter into hash table */
 948                 e.key = name;
 949                 e.data = value;
 950
 951                 hsearch_r(e, ENV_ENTER, &rv, htab, flag);
 952 #if !CONFIG_IS_ENABLED(ENV_WRITEABLE_LIST)
 953                 if (rv == NULL) {
 954                         printf("himport_r: can't insert \"%s=%s\" into hash table\n",
 955                                 name, value);
 956                 }
 957 #endif
 958
 959                 debug("INSERT: table %p, filled %d/%d rv %p ==> name=\"%s\" value=\"%s\"\n",
 960                         htab, htab->filled, htab->size,
 961                         rv, name, value);
 962         } while ((dp < data + size) && *dp);    /* size check needed for text */
 963                                                 /* without '\0' termination */
 964         debug("INSERT: free(data = %p)\n", data);
 965         free(data);
 966
 967         if (flag & H_NOCLEAR)
 968                 goto end;
 969
 970         /* process variables which were not considered */
 971         for (i = 0; i < nvars; i++) {
 972                 if (localvars[i] == NULL)
 973                         continue;
 974                 /*
 975                  * All variables which were not deleted from the variable list
 976                  * were not present in the imported env
 977                  * This could mean two things:
 978                  * a) if the variable was present in current env, we delete it
 979                  * b) if the variable was not present in current env, we notify
 980                  *    it might be a typo
 981                  */
 982                 if (hdelete_r(localvars[i], htab, flag))
 983                         printf("WARNING: '%s' neither in running nor in imported env!\n", localvars[i]);
 984                 else
 985                         printf("WARNING: '%s' not in imported env, deleting it!\n", localvars[i]);
 986         }
 987
 988 end:
 989         debug("INSERT: done\n");
 990         return 1;               /* everything OK */
 991 }
 992
 993 /*
 994  * hwalk_r()
 995  */
 996
 997 /*
 998  * Walk all of the entries in the hash, calling the callback for each one.
 999  * this allows some generic operation to be performed on each element.
1000  */
1001 int hwalk_r(struct hsearch_data *htab, int (*callback)(struct env_entry *entry))
1002 {
1003         int i;
1004         int retval;
1005
1006         for (i = 1; i <= htab->size; ++i) {
1007                 if (htab->table[i].used > 0) {
1008                         retval = callback(&htab->table[i].entry);
1009                         if (retval)
1010                                 return retval;
1011                 }
1012         }
1013
1014         return 0;
1015 }