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)
 329                         first_deleted = idx;
 330
 331                 ret = _compare_and_overwrite_entry(item, action, retval, htab,
 332                         flag, hval, idx);
 333                 if (ret != -1)
 334                         return ret;
 335
 336                 /*
 337                  * Second hash function:
 338                  * as suggested in [Knuth]
 339                  */
 340                 hval2 = 1 + hval % (htab->size - 2);
 341
 342                 do {
 343                         /*
 344                          * Because SIZE is prime this guarantees to
 345                          * step through all available indices.
 346                          */
 347                         if (idx <= hval2)
 348                                 idx = htab->size + idx - hval2;
 349                         else
 350                                 idx -= hval2;
 351
 352                         /*
 353                          * If we visited all entries leave the loop
 354                          * unsuccessfully.
 355                          */
 356                         if (idx == hval)
 357                                 break;
 358
 359                         if (htab->table[idx].used == USED_DELETED
 360                             && !first_deleted)
 361                                 first_deleted = idx;
 362
 363                         /* If entry is found use it. */
 364                         ret = _compare_and_overwrite_entry(item, action, retval,
 365                                 htab, flag, hval, idx);
 366                         if (ret != -1)
 367                                 return ret;
 368                 }
 369                 while (htab->table[idx].used != USED_FREE);
 370         }
 371
 372         /* An empty bucket has been found. */
 373         if (action == ENV_ENTER) {
 374                 /*
 375                  * If table is full and another entry should be
 376                  * entered return with error.
 377                  */
 378                 if (htab->filled == htab->size) {
 379                         __set_errno(ENOMEM);
 380                         *retval = NULL;
 381                         return 0;
 382                 }
 383
 384                 /*
 385                  * Create new entry;
 386                  * create copies of item.key and item.data
 387                  */
 388                 if (first_deleted)
 389                         idx = first_deleted;
 390
 391                 htab->table[idx].used = hval;
 392                 htab->table[idx].entry.key = strdup(item.key);
 393                 htab->table[idx].entry.data = strdup(item.data);
 394                 if (!htab->table[idx].entry.key ||
 395                     !htab->table[idx].entry.data) {
 396                         __set_errno(ENOMEM);
 397                         *retval = NULL;
 398                         return 0;
 399                 }
 400
 401                 ++htab->filled;
 402
 403                 /* This is a new entry, so look up a possible callback */
 404                 env_callback_init(&htab->table[idx].entry);
 405                 /* Also look for flags */
 406                 env_flags_init(&htab->table[idx].entry);
 407
 408                 /* check for permission */
 409                 if (htab->change_ok != NULL && htab->change_ok(
 410                     &htab->table[idx].entry, item.data, env_op_create, flag)) {
 411                         debug("change_ok() rejected setting variable "
 412                                 "%s, skipping it!\n", item.key);
 413                         _hdelete(item.key, htab, &htab->table[idx].entry, idx);
 414                         __set_errno(EPERM);
 415                         *retval = NULL;
 416                         return 0;
 417                 }
 418
 419                 /* If there is a callback, call it */
 420                 if (do_callback(&htab->table[idx].entry, item.key, item.data,
 421                                 env_op_create, flag)) {
 422                         debug("callback() rejected setting variable "
 423                                 "%s, skipping it!\n", item.key);
 424                         _hdelete(item.key, htab, &htab->table[idx].entry, idx);
 425                         __set_errno(EINVAL);
 426                         *retval = NULL;
 427                         return 0;
 428                 }
 429
 430                 /* return new entry */
 431                 *retval = &htab->table[idx].entry;
 432                 return 1;
 433         }
 434
 435         __set_errno(ESRCH);
 436         *retval = NULL;
 437         return 0;
 438 }
 439
 440
 441 /*
 442  * hdelete()
 443  */
 444
 445 /*
 446  * The standard implementation of hsearch(3) does not provide any way
 447  * to delete any entries from the hash table.  We extend the code to
 448  * do that.
 449  */
 450
 451 static void _hdelete(const char *key, struct hsearch_data *htab,
 452                      struct env_entry *ep, int idx)
 453 {
 454         /* free used entry */
 455         debug("hdelete: DELETING key \"%s\"\n", key);
 456         free((void *)ep->key);
 457         free(ep->data);
 458         ep->flags = 0;
 459         htab->table[idx].used = USED_DELETED;
 460
 461         --htab->filled;
 462 }
 463
 464 int hdelete_r(const char *key, struct hsearch_data *htab, int flag)
 465 {
 466         struct env_entry e, *ep;
 467         int idx;
 468
 469         debug("hdelete: DELETE key \"%s\"\n", key);
 470
 471         e.key = (char *)key;
 472
 473         idx = hsearch_r(e, ENV_FIND, &ep, htab, 0);
 474         if (idx == 0) {
 475                 __set_errno(ESRCH);
 476                 return 0;       /* not found */
 477         }
 478
 479         /* Check for permission */
 480         if (htab->change_ok != NULL &&
 481             htab->change_ok(ep, NULL, env_op_delete, flag)) {
 482                 debug("change_ok() rejected deleting variable "
 483                         "%s, skipping it!\n", key);
 484                 __set_errno(EPERM);
 485                 return 0;
 486         }
 487
 488         /* If there is a callback, call it */
 489         if (do_callback(&htab->table[idx].entry, key, NULL,
 490                         env_op_delete, flag)) {
 491                 debug("callback() rejected deleting variable "
 492                         "%s, skipping it!\n", key);
 493                 __set_errno(EINVAL);
 494                 return 0;
 495         }
 496
 497         _hdelete(key, htab, ep, idx);
 498
 499         return 1;
 500 }
 501
 502 #if !(defined(CONFIG_SPL_BUILD) && !defined(CONFIG_SPL_SAVEENV))
 503 /*
 504  * hexport()
 505  */
 506
 507 /*
 508  * Export the data stored in the hash table in linearized form.
 509  *
 510  * Entries are exported as "name=value" strings, separated by an
 511  * arbitrary (non-NUL, of course) separator character. This allows to
 512  * use this function both when formatting the U-Boot environment for
 513  * external storage (using '\0' as separator), but also when using it
 514  * for the "printenv" command to print all variables, simply by using
 515  * as '\n" as separator. This can also be used for new features like
 516  * exporting the environment data as text file, including the option
 517  * for later re-import.
 518  *
 519  * The entries in the result list will be sorted by ascending key
 520  * values.
 521  *
 522  * If the separator character is different from NUL, then any
 523  * separator characters and backslash characters in the values will
 524  * be escaped by a preceding backslash in output. This is needed for
 525  * example to enable multi-line values, especially when the output
 526  * shall later be parsed (for example, for re-import).
 527  *
 528  * There are several options how the result buffer is handled:
 529  *
 530  * *resp  size
 531  * -----------
 532  *  NULL    0   A string of sufficient length will be allocated.
 533  *  NULL   >0   A string of the size given will be
 534  *              allocated. An error will be returned if the size is
 535  *              not sufficient.  Any unused bytes in the string will
 536  *              be '\0'-padded.
 537  * !NULL    0   The user-supplied buffer will be used. No length
 538  *              checking will be performed, i. e. it is assumed that
 539  *              the buffer size will always be big enough. DANGEROUS.
 540  * !NULL   >0   The user-supplied buffer will be used. An error will
 541  *              be returned if the size is not sufficient.  Any unused
 542  *              bytes in the string will be '\0'-padded.
 543  */
 544
 545 static int cmpkey(const void *p1, const void *p2)
 546 {
 547         struct env_entry *e1 = *(struct env_entry **)p1;
 548         struct env_entry *e2 = *(struct env_entry **)p2;
 549
 550         return (strcmp(e1->key, e2->key));
 551 }
 552
 553 static int match_string(int flag, const char *str, const char *pat, void *priv)
 554 {
 555         switch (flag & H_MATCH_METHOD) {
 556         case H_MATCH_IDENT:
 557                 if (strcmp(str, pat) == 0)
 558                         return 1;
 559                 break;
 560         case H_MATCH_SUBSTR:
 561                 if (strstr(str, pat))
 562                         return 1;
 563                 break;
 564 #ifdef CONFIG_REGEX
 565         case H_MATCH_REGEX:
 566                 {
 567                         struct slre *slrep = (struct slre *)priv;
 568
 569                         if (slre_match(slrep, str, strlen(str), NULL))
 570                                 return 1;
 571                 }
 572                 break;
 573 #endif
 574         default:
 575                 printf("## ERROR: unsupported match method: 0x%02x\n",
 576                         flag & H_MATCH_METHOD);
 577                 break;
 578         }
 579         return 0;
 580 }
 581
 582 static int match_entry(struct env_entry *ep, int flag, int argc,
 583                        char *const argv[])
 584 {
 585         int arg;
 586         void *priv = NULL;
 587
 588         for (arg = 0; arg < argc; ++arg) {
 589 #ifdef CONFIG_REGEX
 590                 struct slre slre;
 591
 592                 if (slre_compile(&slre, argv[arg]) == 0) {
 593                         printf("Error compiling regex: %s\n", slre.err_str);
 594                         return 0;
 595                 }
 596
 597                 priv = (void *)&slre;
 598 #endif
 599                 if (flag & H_MATCH_KEY) {
 600                         if (match_string(flag, ep->key, argv[arg], priv))
 601                                 return 1;
 602                 }
 603                 if (flag & H_MATCH_DATA) {
 604                         if (match_string(flag, ep->data, argv[arg], priv))
 605                                 return 1;
 606                 }
 607         }
 608         return 0;
 609 }
 610
 611 ssize_t hexport_r(struct hsearch_data *htab, const char sep, int flag,
 612                  char **resp, size_t size,
 613                  int argc, char *const argv[])
 614 {
 615         struct env_entry *list[htab->size];
 616         char *res, *p;
 617         size_t totlen;
 618         int i, n;
 619
 620         /* Test for correct arguments.  */
 621         if ((resp == NULL) || (htab == NULL)) {
 622                 __set_errno(EINVAL);
 623                 return (-1);
 624         }
 625
 626         debug("EXPORT  table = %p, htab.size = %d, htab.filled = %d, size = %lu\n",
 627               htab, htab->size, htab->filled, (ulong)size);
 628         /*
 629          * Pass 1:
 630          * search used entries,
 631          * save addresses and compute total length
 632          */
 633         for (i = 1, n = 0, totlen = 0; i <= htab->size; ++i) {
 634
 635                 if (htab->table[i].used > 0) {
 636                         struct env_entry *ep = &htab->table[i].entry;
 637                         int found = match_entry(ep, flag, argc, argv);
 638
 639                         if ((argc > 0) && (found == 0))
 640                                 continue;
 641
 642                         if ((flag & H_HIDE_DOT) && ep->key[0] == '.')
 643                                 continue;
 644
 645                         list[n++] = ep;
 646
 647                         totlen += strlen(ep->key);
 648
 649                         if (sep == '\0') {
 650                                 totlen += strlen(ep->data);
 651                         } else {        /* check if escapes are needed */
 652                                 char *s = ep->data;
 653
 654                                 while (*s) {
 655                                         ++totlen;
 656                                         /* add room for needed escape chars */
 657                                         if ((*s == sep) || (*s == '\\'))
 658                                                 ++totlen;
 659                                         ++s;
 660                                 }
 661                         }
 662                         totlen += 2;    /* for '=' and 'sep' char */
 663                 }
 664         }
 665
 666 #ifdef DEBUG
 667         /* Pass 1a: print unsorted list */
 668         printf("Unsorted: n=%d\n", n);
 669         for (i = 0; i < n; ++i) {
 670                 printf("\t%3d: %p ==> %-10s => %s\n",
 671                        i, list[i], list[i]->key, list[i]->data);
 672         }
 673 #endif
 674
 675         /* Sort list by keys */
 676         qsort(list, n, sizeof(struct env_entry *), cmpkey);
 677
 678         /* Check if the user supplied buffer size is sufficient */
 679         if (size) {
 680                 if (size < totlen + 1) {        /* provided buffer too small */
 681                         printf("Env export buffer too small: %lu, but need %lu\n",
 682                                (ulong)size, (ulong)totlen + 1);
 683                         __set_errno(ENOMEM);
 684                         return (-1);
 685                 }
 686         } else {
 687                 size = totlen + 1;
 688         }
 689
 690         /* Check if the user provided a buffer */
 691         if (*resp) {
 692                 /* yes; clear it */
 693                 res = *resp;
 694                 memset(res, '\0', size);
 695         } else {
 696                 /* no, allocate and clear one */
 697                 *resp = res = calloc(1, size);
 698                 if (res == NULL) {
 699                         __set_errno(ENOMEM);
 700                         return (-1);
 701                 }
 702         }
 703         /*
 704          * Pass 2:
 705          * export sorted list of result data
 706          */
 707         for (i = 0, p = res; i < n; ++i) {
 708                 const char *s;
 709
 710                 s = list[i]->key;
 711                 while (*s)
 712                         *p++ = *s++;
 713                 *p++ = '=';
 714
 715                 s = list[i]->data;
 716
 717                 while (*s) {
 718                         if ((*s == sep) || (*s == '\\'))
 719                                 *p++ = '\\';    /* escape */
 720                         *p++ = *s++;
 721                 }
 722                 *p++ = sep;
 723         }
 724         *p = '\0';              /* terminate result */
 725
 726         return size;
 727 }
 728 #endif
 729
 730
 731 /*
 732  * himport()
 733  */
 734
 735 /*
 736  * Check whether variable 'name' is amongst vars[],
 737  * and remove all instances by setting the pointer to NULL
 738  */
 739 static int drop_var_from_set(const char *name, int nvars, char * vars[])
 740 {
 741         int i = 0;
 742         int res = 0;
 743
 744         /* No variables specified means process all of them */
 745         if (nvars == 0)
 746                 return 1;
 747
 748         for (i = 0; i < nvars; i++) {
 749                 if (vars[i] == NULL)
 750                         continue;
 751                 /* If we found it, delete all of them */
 752                 if (!strcmp(name, vars[i])) {
 753                         vars[i] = NULL;
 754                         res = 1;
 755                 }
 756         }
 757         if (!res)
 758                 debug("Skipping non-listed variable %s\n", name);
 759
 760         return res;
 761 }
 762
 763 /*
 764  * Import linearized data into hash table.
 765  *
 766  * This is the inverse function to hexport(): it takes a linear list
 767  * of "name=value" pairs and creates hash table entries from it.
 768  *
 769  * Entries without "value", i. e. consisting of only "name" or
 770  * "name=", will cause this entry to be deleted from the hash table.
 771  *
 772  * The "flag" argument can be used to control the behaviour: when the
 773  * H_NOCLEAR bit is set, then an existing hash table will kept, i. e.
 774  * new data will be added to an existing hash table; otherwise, if no
 775  * vars are passed, old data will be discarded and a new hash table
 776  * will be created. If vars are passed, passed vars that are not in
 777  * the linear list of "name=value" pairs will be removed from the
 778  * current hash table.
 779  *
 780  * The separator character for the "name=value" pairs can be selected,
 781  * so we both support importing from externally stored environment
 782  * data (separated by NUL characters) and from plain text files
 783  * (entries separated by newline characters).
 784  *
 785  * To allow for nicely formatted text input, leading white space
 786  * (sequences of SPACE and TAB chars) is ignored, and entries starting
 787  * (after removal of any leading white space) with a '#' character are
 788  * considered comments and ignored.
 789  *
 790  * [NOTE: this means that a variable name cannot start with a '#'
 791  * character.]
 792  *
 793  * When using a non-NUL separator character, backslash is used as
 794  * escape character in the value part, allowing for example for
 795  * multi-line values.
 796  *
 797  * In theory, arbitrary separator characters can be used, but only
 798  * '\0' and '\n' have really been tested.
 799  */
 800
 801 int himport_r(struct hsearch_data *htab,
 802                 const char *env, size_t size, const char sep, int flag,
 803                 int crlf_is_lf, int nvars, char * const vars[])
 804 {
 805         char *data, *sp, *dp, *name, *value;
 806         char *localvars[nvars];
 807         int i;
 808
 809         /* Test for correct arguments.  */
 810         if (htab == NULL) {
 811                 __set_errno(EINVAL);
 812                 return 0;
 813         }
 814
 815         /* we allocate new space to make sure we can write to the array */
 816         if ((data = malloc(size + 1)) == NULL) {
 817                 debug("himport_r: can't malloc %lu bytes\n", (ulong)size + 1);
 818                 __set_errno(ENOMEM);
 819                 return 0;
 820         }
 821         memcpy(data, env, size);
 822         data[size] = '\0';
 823         dp = data;
 824
 825         /* make a local copy of the list of variables */
 826         if (nvars)
 827                 memcpy(localvars, vars, sizeof(vars[0]) * nvars);
 828
 829         if ((flag & H_NOCLEAR) == 0 && !nvars) {
 830                 /* Destroy old hash table if one exists */
 831                 debug("Destroy Hash Table: %p table = %p\n", htab,
 832                        htab->table);
 833                 if (htab->table)
 834                         hdestroy_r(htab);
 835         }
 836
 837         /*
 838          * Create new hash table (if needed).  The computation of the hash
 839          * table size is based on heuristics: in a sample of some 70+
 840          * existing systems we found an average size of 39+ bytes per entry
 841          * in the environment (for the whole key=value pair). Assuming a
 842          * size of 8 per entry (= safety factor of ~5) should provide enough
 843          * safety margin for any existing environment definitions and still
 844          * allow for more than enough dynamic additions. Note that the
 845          * "size" argument is supposed to give the maximum environment size
 846          * (CONFIG_ENV_SIZE).  This heuristics will result in
 847          * unreasonably large numbers (and thus memory footprint) for
 848          * big flash environments (>8,000 entries for 64 KB
 849          * environment size), so we clip it to a reasonable value.
 850          * On the other hand we need to add some more entries for free
 851          * space when importing very small buffers. Both boundaries can
 852          * be overwritten in the board config file if needed.
 853          */
 854
 855         if (!htab->table) {
 856                 int nent = CONFIG_ENV_MIN_ENTRIES + size / 8;
 857
 858                 if (nent > CONFIG_ENV_MAX_ENTRIES)
 859                         nent = CONFIG_ENV_MAX_ENTRIES;
 860
 861                 debug("Create Hash Table: N=%d\n", nent);
 862
 863                 if (hcreate_r(nent, htab) == 0) {
 864                         free(data);
 865                         return 0;
 866                 }
 867         }
 868
 869         if (!size) {
 870                 free(data);
 871                 return 1;               /* everything OK */
 872         }
 873         if(crlf_is_lf) {
 874                 /* Remove Carriage Returns in front of Line Feeds */
 875                 unsigned ignored_crs = 0;
 876                 for(;dp < data + size && *dp; ++dp) {
 877                         if(*dp == '\r' &&
 878                            dp < data + size - 1 && *(dp+1) == '\n')
 879                                 ++ignored_crs;
 880                         else
 881                                 *(dp-ignored_crs) = *dp;
 882                 }
 883                 size -= ignored_crs;
 884                 dp = data;
 885         }
 886         /* Parse environment; allow for '\0' and 'sep' as separators */
 887         do {
 888                 struct env_entry e, *rv;
 889
 890                 /* skip leading white space */
 891                 while (isblank(*dp))
 892                         ++dp;
 893
 894                 /* skip comment lines */
 895                 if (*dp == '#') {
 896                         while (*dp && (*dp != sep))
 897                                 ++dp;
 898                         ++dp;
 899                         continue;
 900                 }
 901
 902                 /* parse name */
 903                 for (name = dp; *dp != '=' && *dp && *dp != sep; ++dp)
 904                         ;
 905
 906                 /* deal with "name" and "name=" entries (delete var) */
 907                 if (*dp == '\0' || *(dp + 1) == '\0' ||
 908                     *dp == sep || *(dp + 1) == sep) {
 909                         if (*dp == '=')
 910                                 *dp++ = '\0';
 911                         *dp++ = '\0';   /* terminate name */
 912
 913                         debug("DELETE CANDIDATE: \"%s\"\n", name);
 914                         if (!drop_var_from_set(name, nvars, localvars))
 915                                 continue;
 916
 917                         if (hdelete_r(name, htab, flag) == 0)
 918                                 debug("DELETE ERROR ##############################\n");
 919
 920                         continue;
 921                 }
 922                 *dp++ = '\0';   /* terminate name */
 923
 924                 /* parse value; deal with escapes */
 925                 for (value = sp = dp; *dp && (*dp != sep); ++dp) {
 926                         if ((*dp == '\\') && *(dp + 1))
 927                                 ++dp;
 928                         *sp++ = *dp;
 929                 }
 930                 *sp++ = '\0';   /* terminate value */
 931                 ++dp;
 932
 933                 if (*name == 0) {
 934                         debug("INSERT: unable to use an empty key\n");
 935                         __set_errno(EINVAL);
 936                         free(data);
 937                         return 0;
 938                 }
 939
 940                 /* Skip variables which are not supposed to be processed */
 941                 if (!drop_var_from_set(name, nvars, localvars))
 942                         continue;
 943
 944                 /* enter into hash table */
 945                 e.key = name;
 946                 e.data = value;
 947
 948                 hsearch_r(e, ENV_ENTER, &rv, htab, flag);
 949                 if (rv == NULL)
 950                         printf("himport_r: can't insert \"%s=%s\" into hash table\n",
 951                                 name, value);
 952
 953                 debug("INSERT: table %p, filled %d/%d rv %p ==> name=\"%s\" value=\"%s\"\n",
 954                         htab, htab->filled, htab->size,
 955                         rv, name, value);
 956         } while ((dp < data + size) && *dp);    /* size check needed for text */
 957                                                 /* without '\0' termination */
 958         debug("INSERT: free(data = %p)\n", data);
 959         free(data);
 960
 961         if (flag & H_NOCLEAR)
 962                 goto end;
 963
 964         /* process variables which were not considered */
 965         for (i = 0; i < nvars; i++) {
 966                 if (localvars[i] == NULL)
 967                         continue;
 968                 /*
 969                  * All variables which were not deleted from the variable list
 970                  * were not present in the imported env
 971                  * This could mean two things:
 972                  * a) if the variable was present in current env, we delete it
 973                  * b) if the variable was not present in current env, we notify
 974                  *    it might be a typo
 975                  */
 976                 if (hdelete_r(localvars[i], htab, flag) == 0)
 977                         printf("WARNING: '%s' neither in running nor in imported env!\n", localvars[i]);
 978                 else
 979                         printf("WARNING: '%s' not in imported env, deleting it!\n", localvars[i]);
 980         }
 981
 982 end:
 983         debug("INSERT: done\n");
 984         return 1;               /* everything OK */
 985 }
 986
 987 /*
 988  * hwalk_r()
 989  */
 990
 991 /*
 992  * Walk all of the entries in the hash, calling the callback for each one.
 993  * this allows some generic operation to be performed on each element.
 994  */
 995 int hwalk_r(struct hsearch_data *htab, int (*callback)(struct env_entry *entry))
 996 {
 997         int i;
 998         int retval;
 999
1000         for (i = 1; i <= htab->size; ++i) {
1001                 if (htab->table[i].used > 0) {
1002                         retval = callback(&htab->table[i].entry);
1003                         if (retval)
1004                                 return retval;
1005                 }
1006         }
1007
1008         return 0;
1009 }