palacios/src/palacios/vmm_hashtable.c

   1 /*
   2   Copyright (c) 2002, 2004, Christopher Clark
   3   All rights reserved.
   4
   5   Redistribution and use in source and binary forms, with or without
   6   modification, are permitted provided that the following conditions
   7   are met:
   8
   9   * Redistributions of source code must retain the above copyright
  10     notice, this list of conditions and the following disclaimer.
  11
  12   * Redistributions in binary form must reproduce the above copyright
  13     notice, this list of conditions and the following disclaimer in the
  14     documentation and/or other materials provided with the distribution.
  15
  16   * Neither the name of the original author; nor the names of any contributors
  17     may be used to endorse or promote products derived from this software
  18     without specific prior written permission.
  19
  20
  21   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  25   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  26   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  27   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  28   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  29   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  30   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  31   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32 */
  33
  34 /* Modifications made by Jack Lange <jarusl@cs.northwestern.edu> */
  35
  36
  37
  38 #include <palacios/vmm.h>
  39 #include <palacios/vmm_hashtable.h>
  40 #include <palacios/vmm_string.h>
  41
  42
  43
  44
  45
  46 struct hash_entry {
  47   addr_t key;
  48   addr_t value;
  49   uint_t hash;
  50   struct hash_entry * next;
  51 };
  52
  53 struct hashtable {
  54     uint_t table_length;
  55     struct hash_entry ** table;
  56     uint_t entry_count;
  57     uint_t load_limit;
  58     uint_t prime_index;
  59     uint_t (*hash_fn) (addr_t key);
  60     int (*eq_fn) (addr_t key1, addr_t key2);
  61 };
  62
  63
  64
  65 /* HASH FUNCTIONS */
  66
  67
  68
  69 uint_t do_hash(struct hashtable * htable, addr_t key) {
  70   /* Aim to protect against poor hash functions by adding logic here
  71    * - logic taken from java 1.4 hashtable source */
  72   uint_t i = htable->hash_fn(key);
  73   i += ~(i << 9);
  74   i ^=  ((i >> 14) | (i << 18)); /* >>> */
  75   i +=  (i << 4);
  76   i ^=  ((i >> 10) | (i << 22)); /* >>> */
  77
  78   return i;
  79 }
  80
  81
  82 /* HASH AN UNSIGNED LONG */
  83 /* LINUX UNSIGHED LONG HASH FUNCTION */
  84 #ifdef __V3_32BIT__
  85 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  86 #define GOLDEN_RATIO_PRIME 0x9e370001UL
  87 #define BITS_PER_LONG 32
  88 #elif  defined(__V3_64BIT__)
  89 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  90 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
  91 #define BITS_PER_LONG 64
  92 #else
  93 #error Define GOLDEN_RATIO_PRIME for your wordsize.
  94 #endif
  95
  96 ulong_t hash_long(ulong_t val, uint_t bits) {
  97   ulong_t hash = val;
  98
  99 #ifdef __V3_64BIT__
 100   /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
 101   ulong_t n = hash;
 102   n <<= 18;
 103   hash -= n;
 104   n <<= 33;
 105   hash -= n;
 106   n <<= 3;
 107   hash += n;
 108   n <<= 3;
 109   hash -= n;
 110   n <<= 4;
 111   hash += n;
 112   n <<= 2;
 113   hash += n;
 114 #else
 115   /* On some cpus multiply is faster, on others gcc will do shifts */
 116   hash *= GOLDEN_RATIO_PRIME;
 117 #endif
 118
 119   /* High bits are more random, so use them. */
 120   return hash >> (BITS_PER_LONG - bits);
 121 }
 122
 123 /* HASH GENERIC MEMORY BUFFER */
 124 /* ELF HEADER HASH FUNCTION */
 125 ulong_t hash_buffer(uchar_t * msg, uint_t length) {
 126   ulong_t hash = 0;
 127   ulong_t temp = 0;
 128   uint_t i;
 129
 130   for (i = 0; i < length; i++) {
 131     hash = (hash << 4) + *(msg + i) + i;
 132     if ((temp = (hash & 0xF0000000))) {
 133       hash ^= (temp >> 24);
 134     }
 135     hash &= ~temp;
 136   }
 137   return hash;
 138 }
 139
 140
 141
 142 /*****************************************************************************/
 143 /* indexFor */
 144 static inline uint_t indexFor(uint_t table_length, uint_t hash_value) {
 145   return (hash_value % table_length);
 146 };
 147
 148 /* Only works if table_length == 2^N */
 149 /*
 150   static inline uint_t indexFor(uint_t table_length, uint_t hashvalue)
 151   {
 152   return (hashvalue & (table_length - 1u));
 153   }
 154 */
 155
 156 /*****************************************************************************/
 157 #define freekey(X) V3_Free(X)
 158 /*define freekey(X) ; */
 159
 160
 161 static void * tmp_realloc(void * old_ptr, uint_t old_size, uint_t new_size) {
 162   void * new_buf = V3_Malloc(new_size);
 163
 164   if (new_buf == NULL) {
 165     return NULL;
 166   }
 167
 168   memcpy(new_buf, old_ptr, old_size);
 169   V3_Free(old_ptr);
 170
 171   return new_buf;
 172 }
 173
 174
 175 /*
 176 Credit for primes table: Aaron Krowne
 177  http://br.endernet.org/~akrowne/
 178  http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
 179 */
 180 static const uint_t primes[] = {
 181   53, 97, 193, 389,
 182   769, 1543, 3079, 6151,
 183   12289, 24593, 49157, 98317,
 184   196613, 393241, 786433, 1572869,
 185   3145739, 6291469, 12582917, 25165843,
 186   50331653, 100663319, 201326611, 402653189,
 187   805306457, 1610612741 };
 188
 189
 190 const uint_t prime_table_length = sizeof(primes) / sizeof(primes[0]);
 191
 192 const float max_load_factor = 0.65;
 193
 194 /*****************************************************************************/
 195 struct hashtable * create_hashtable(uint_t min_size,
 196                                     uint_t (*hash_fn) (addr_t),
 197                                     int (*eq_fn) (addr_t, addr_t)) {
 198     struct hashtable * htable;
 199     uint_t prime_index;
 200     uint_t size = primes[0];
 201
 202     /* Check requested hashtable isn't too large */
 203     if (min_size > (1u << 30)) {
 204       return NULL;
 205     }
 206
 207     /* Enforce size as prime */
 208     for (prime_index = 0; prime_index < prime_table_length; prime_index++) {
 209         if (primes[prime_index] > min_size) {
 210           size = primes[prime_index];
 211           break;
 212         }
 213     }
 214
 215     htable = (struct hashtable *)V3_Malloc(sizeof(struct hashtable));
 216
 217     if (htable == NULL) {
 218       return NULL; /*oom*/
 219     }
 220
 221     htable->table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * size);
 222
 223     if (htable->table == NULL) {
 224       V3_Free(htable);
 225       return NULL;  /*oom*/
 226     }
 227
 228
 229     memset(htable->table, 0, size * sizeof(struct hash_entry *));
 230
 231     htable->table_length  = size;
 232     htable->prime_index   = prime_index;
 233     htable->entry_count   = 0;
 234     htable->hash_fn       = hash_fn;
 235     htable->eq_fn         = eq_fn;
 236     htable->load_limit    = (uint_t) v3_ceil((double)(size * max_load_factor));
 237
 238     return htable;
 239 }
 240
 241
 242
 243 /*****************************************************************************/
 244 static int hashtable_expand(struct hashtable * htable) {
 245     /* Double the size of the table to accomodate more entries */
 246     struct hash_entry ** new_table;
 247     struct hash_entry * tmp_entry;
 248     struct hash_entry ** entry_ptr;
 249     uint_t new_size;
 250     uint_t i;
 251     uint_t index;
 252
 253     /* Check we're not hitting max capacity */
 254     if (htable->prime_index == (prime_table_length - 1)) {
 255       return 0;
 256     }
 257
 258     new_size = primes[++(htable->prime_index)];
 259
 260     new_table = (struct hash_entry **)V3_Malloc(sizeof(struct hash_entry*) * new_size);
 261
 262     if (new_table != NULL) {
 263         memset(new_table, 0, new_size * sizeof(struct hash_entry *));
 264         /* This algorithm is not 'stable'. ie. it reverses the list
 265          * when it transfers entries between the tables */
 266
 267         for (i = 0; i < htable->table_length; i++) {
 268
 269           while ((tmp_entry = htable->table[i]) != NULL) {
 270             htable->table[i] = tmp_entry->next;
 271
 272             index = indexFor(new_size, tmp_entry->hash);
 273
 274             tmp_entry->next = new_table[index];
 275
 276             new_table[index] = tmp_entry;
 277           }
 278         }
 279
 280         V3_Free(htable->table);
 281
 282         htable->table = new_table;
 283     } else {
 284       /* Plan B: realloc instead */
 285
 286       //new_table = (struct hash_entry **)realloc(htable->table, new_size * sizeof(struct hash_entry *));
 287       new_table = (struct hash_entry **)tmp_realloc(htable->table, primes[htable->prime_index - 1],
 288                                                new_size * sizeof(struct hash_entry *));
 289
 290       if (new_table == NULL) {
 291         (htable->prime_index)--;
 292         return 0;
 293       }
 294
 295       htable->table = new_table;
 296
 297       memset(new_table[htable->table_length], 0, new_size - htable->table_length);
 298
 299       for (i = 0; i < htable->table_length; i++) {
 300
 301         for (entry_ptr = &(new_table[i]), tmp_entry = *entry_ptr;
 302              tmp_entry != NULL;
 303              tmp_entry = *entry_ptr) {
 304
 305           index = indexFor(new_size, tmp_entry->hash);
 306
 307           if (i == index) {
 308             entry_ptr = &(tmp_entry->next);
 309           } else {
 310             *entry_ptr = tmp_entry->next;
 311             tmp_entry->next = new_table[index];
 312             new_table[index] = tmp_entry;
 313           }
 314         }
 315       }
 316     }
 317
 318     htable->table_length = new_size;
 319
 320     htable->load_limit   = (uint_t) v3_ceil(new_size * max_load_factor);
 321
 322     return -1;
 323 }
 324
 325 /*****************************************************************************/
 326 uint_t hashtable_count(struct hashtable * htable) {
 327     return htable->entry_count;
 328 }
 329
 330 /*****************************************************************************/
 331 int hashtable_insert(struct hashtable * htable, addr_t key, addr_t value) {
 332     /* This method allows duplicate keys - but they shouldn't be used */
 333     uint_t index;
 334     struct hash_entry * new_entry;
 335
 336     if (++(htable->entry_count) > htable->load_limit) {
 337       /* Ignore the return value. If expand fails, we should
 338        * still try cramming just this value into the existing table
 339        * -- we may not have memory for a larger table, but one more
 340        * element may be ok. Next time we insert, we'll try expanding again.*/
 341       hashtable_expand(htable);
 342     }
 343
 344
 345     new_entry = (struct hash_entry *)V3_Malloc(sizeof(struct hash_entry));
 346
 347     if (new_entry == NULL) {
 348       (htable->entry_count)--;
 349       return 0; /*oom*/
 350     }
 351
 352     new_entry->hash = do_hash(htable, key);
 353
 354     index = indexFor(htable->table_length, new_entry->hash);
 355
 356     new_entry->key = key;
 357     new_entry->value = value;
 358
 359     new_entry->next = htable->table[index];
 360
 361     htable->table[index] = new_entry;
 362
 363     return -1;
 364 }
 365
 366
 367
 368 int hashtable_change(struct hashtable * htable, addr_t key, addr_t value, int free_value) {
 369     struct hash_entry * tmp_entry;
 370     uint_t hash_value;
 371     uint_t index;
 372
 373     hash_value = do_hash(htable, key);
 374
 375     index = indexFor(htable->table_length, hash_value);
 376
 377     tmp_entry = htable->table[index];
 378
 379     while (tmp_entry != NULL) {
 380         /* Check hash value to short circuit heavier comparison */
 381         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 382
 383           if (free_value) {
 384             V3_Free((void *)(tmp_entry->value));
 385           }
 386
 387           tmp_entry->value = value;
 388           return -1;
 389         }
 390         tmp_entry = tmp_entry->next;
 391     }
 392     return 0;
 393 }
 394
 395
 396
 397 int hashtable_inc(struct hashtable * htable, addr_t key, addr_t value) {
 398     struct hash_entry * tmp_entry;
 399     uint_t hash_value;
 400     uint_t index;
 401
 402     hash_value = do_hash(htable, key);
 403
 404     index = indexFor(htable->table_length, hash_value);
 405
 406     tmp_entry = htable->table[index];
 407
 408     while (tmp_entry != NULL) {
 409         /* Check hash value to short circuit heavier comparison */
 410         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 411
 412           tmp_entry->value += value;
 413           return -1;
 414         }
 415         tmp_entry = tmp_entry->next;
 416     }
 417     return 0;
 418 }
 419
 420
 421 int hashtable_dec(struct hashtable * htable, addr_t key, addr_t value) {
 422     struct hash_entry * tmp_entry;
 423     uint_t hash_value;
 424     uint_t index;
 425
 426     hash_value = do_hash(htable, key);
 427
 428     index = indexFor(htable->table_length, hash_value);
 429
 430     tmp_entry = htable->table[index];
 431
 432     while (tmp_entry != NULL) {
 433         /* Check hash value to short circuit heavier comparison */
 434         if ((hash_value == tmp_entry->hash) && (htable->eq_fn(key, tmp_entry->key))) {
 435
 436           tmp_entry->value -= value;
 437           return -1;
 438         }
 439         tmp_entry = tmp_entry->next;
 440     }
 441     return 0;
 442 }
 443
 444
 445
 446
 447 /*****************************************************************************/
 448 /* returns value associated with key */
 449 addr_t hashtable_search(struct hashtable * htable, addr_t key) {
 450   struct hash_entry * cursor;
 451   uint_t hash_value;
 452   uint_t index;
 453
 454   hash_value = do_hash(htable, key);
 455
 456   index = indexFor(htable->table_length, hash_value);
 457
 458   cursor = htable->table[index];
 459
 460   while (cursor != NULL) {
 461     /* Check hash value to short circuit heavier comparison */
 462     if ((hash_value == cursor->hash) &&
 463         (htable->eq_fn(key, cursor->key))) {
 464       return cursor->value;
 465     }
 466
 467     cursor = cursor->next;
 468   }
 469
 470   return (addr_t)NULL;
 471 }
 472
 473 /*****************************************************************************/
 474 /* returns value associated with key */
 475 addr_t hashtable_remove(struct hashtable * htable, addr_t key, int free_key) {
 476   /* TODO: consider compacting the table when the load factor drops enough,
 477    *       or provide a 'compact' method. */
 478
 479   struct hash_entry * cursor;
 480   struct hash_entry ** entry_ptr;
 481   addr_t value;
 482   uint_t hash_value;
 483   uint_t index;
 484
 485   hash_value = do_hash(htable, key);
 486
 487   index = indexFor(htable->table_length, hash_value);
 488
 489   entry_ptr = &(htable->table[index]);
 490   cursor = *entry_ptr;
 491
 492   while (cursor != NULL) {
 493     /* Check hash value to short circuit heavier comparison */
 494     if ((hash_value == cursor->hash) &&
 495         (htable->eq_fn(key, cursor->key))) {
 496
 497       *entry_ptr = cursor->next;
 498       htable->entry_count--;
 499       value = cursor->value;
 500
 501       if (free_key) {
 502         freekey((void *)(cursor->key));
 503       }
 504       V3_Free(cursor);
 505
 506       return value;
 507     }
 508
 509     entry_ptr = &(cursor->next);
 510     cursor = cursor->next;
 511   }
 512   return (addr_t)NULL;
 513 }
 514
 515 /*****************************************************************************/
 516 /* destroy */
 517 void hashtable_destroy(struct hashtable * htable, int free_values, int free_keys) {
 518   uint_t i;
 519   struct hash_entry * cursor;;
 520   struct hash_entry **table = htable->table;
 521
 522   if (free_values) {
 523     for (i = 0; i < htable->table_length; i++) {
 524       cursor = table[i];
 525
 526       while (cursor != NULL) {
 527         struct hash_entry * tmp;
 528
 529         tmp = cursor;
 530         cursor = cursor->next;
 531
 532         if (free_keys) {
 533           freekey((void *)(tmp->key));
 534         }
 535         V3_Free((void *)(tmp->value));
 536         V3_Free(tmp);
 537       }
 538     }
 539   } else {
 540     for (i = 0; i < htable->table_length; i++) {
 541       cursor = table[i];
 542
 543       while (cursor != NULL) {
 544         struct hash_entry * tmp;
 545
 546         tmp = cursor;
 547         cursor = cursor->next;
 548
 549         if (free_keys) {
 550           freekey((void *)(tmp->key));
 551         }
 552         V3_Free(tmp);
 553       }
 554     }
 555   }
 556
 557   V3_Free(htable->table);
 558   V3_Free(htable);
 559 }
 560
 561
 562
 563
 564 /* HASH TABLE ITERATORS */
 565
 566
 567
 568 struct hashtable_iter * create_hashtable_iterator(struct hashtable * htable) {
 569   uint_t i;
 570   uint_t table_length;
 571
 572   struct hashtable_iter * iter = (struct hashtable_iter *)V3_Malloc(sizeof(struct hashtable_iter));
 573
 574   if (iter == NULL) {
 575     return NULL;
 576   }
 577
 578   iter->htable = htable;
 579   iter->entry = NULL;
 580   iter->parent = NULL;
 581   table_length = htable->table_length;
 582   iter->index = table_length;
 583
 584   if (htable->entry_count == 0) {
 585     return iter;
 586   }
 587
 588   for (i = 0; i < table_length; i++) {
 589     if (htable->table[i] != NULL) {
 590       iter->entry = htable->table[i];
 591       iter->index = i;
 592       break;
 593     }
 594   }
 595
 596   return iter;
 597 }
 598
 599
 600 addr_t hashtable_get_iter_key(struct hashtable_iter * iter) {
 601   return iter->entry->key;
 602 }
 603
 604 addr_t hashtable_get_iter_value(struct hashtable_iter * iter) {
 605   return iter->entry->value;
 606 }
 607
 608
 609 /* advance - advance the iterator to the next element
 610  *           returns zero if advanced to end of table */
 611 int hashtable_iterator_advance(struct hashtable_iter * iter) {
 612   uint_t j;
 613   uint_t table_length;
 614   struct hash_entry ** table;
 615   struct hash_entry * next;
 616
 617   if (iter->entry == NULL) {
 618     return 0; /* stupidity check */
 619   }
 620
 621
 622   next = iter->entry->next;
 623
 624   if (next != NULL) {
 625     iter->parent = iter->entry;
 626     iter->entry = next;
 627     return -1;
 628   }
 629
 630   table_length = iter->htable->table_length;
 631   iter->parent = NULL;
 632
 633   if (table_length <= (j = ++(iter->index))) {
 634     iter->entry = NULL;
 635     return 0;
 636   }
 637
 638   table = iter->htable->table;
 639
 640   while ((next = table[j]) == NULL) {
 641     if (++j >= table_length) {
 642       iter->index = table_length;
 643       iter->entry = NULL;
 644       return 0;
 645     }
 646   }
 647
 648   iter->index = j;
 649   iter->entry = next;
 650
 651   return -1;
 652 }
 653
 654
 655 /* remove - remove the entry at the current iterator position
 656  *          and advance the iterator, if there is a successive
 657  *          element.
 658  *          If you want the value, read it before you remove:
 659  *          beware memory leaks if you don't.
 660  *          Returns zero if end of iteration. */
 661 int hashtable_iterator_remove(struct hashtable_iter * iter, int free_key) {
 662   struct hash_entry * remember_entry;
 663   struct hash_entry * remember_parent;
 664   int ret;
 665
 666   /* Do the removal */
 667   if ((iter->parent) == NULL) {
 668     /* element is head of a chain */
 669     iter->htable->table[iter->index] = iter->entry->next;
 670   } else {
 671     /* element is mid-chain */
 672     iter->parent->next = iter->entry->next;
 673   }
 674
 675
 676   /* itr->e is now outside the hashtable */
 677   remember_entry = iter->entry;
 678   iter->htable->entry_count--;
 679   if (free_key) {
 680     freekey((void *)(remember_entry->key));
 681   }
 682
 683   /* Advance the iterator, correcting the parent */
 684   remember_parent = iter->parent;
 685   ret = hashtable_iterator_advance(iter);
 686
 687   if (iter->parent == remember_entry) {
 688     iter->parent = remember_parent;
 689   }
 690
 691   V3_Free(remember_entry);
 692   return ret;
 693 }
 694
 695
 696 /* returns zero if not found */
 697 int hashtable_iterator_search(struct hashtable_iter * iter,
 698                               struct hashtable * htable, addr_t key) {
 699   struct hash_entry * entry;
 700   struct hash_entry * parent;
 701   uint_t hash_value;
 702   uint_t index;
 703
 704   hash_value = do_hash(htable, key);
 705   index = indexFor(htable->table_length, hash_value);
 706
 707   entry = htable->table[index];
 708   parent = NULL;
 709
 710   while (entry != NULL) {
 711     /* Check hash value to short circuit heavier comparison */
 712     if ((hash_value == entry->hash) &&
 713         (htable->eq_fn(key, entry->key))) {
 714       iter->index = index;
 715       iter->entry = entry;
 716       iter->parent = parent;
 717       iter->htable = htable;
 718       return -1;
 719     }
 720     parent = entry;
 721     entry = entry->next;
 722   }
 723   return 0;
 724 }
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740 /*
 741  * Copyright (c) 2002, Christopher Clark
 742  * All rights reserved.
 743  *
 744  * Redistribution and use in source and binary forms, with or without
 745  * modification, are permitted provided that the following conditions
 746  * are met:
 747  *
 748  * * Redistributions of source code must retain the above copyright
 749  * notice, this list of conditions and the following disclaimer.
 750  *
 751  * * Redistributions in binary form must reproduce the above copyright
 752  * notice, this list of conditions and the following disclaimer in the
 753  * documentation and/or other materials provided with the distribution.
 754  *
 755  * * Neither the name of the original author; nor the names of any contributors
 756  * may be used to endorse or promote products derived from this software
 757  * without specific prior written permission.
 758  *
 759  *
 760  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 761  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 762  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 763  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 764  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 765  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 766  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 767  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 768  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 769  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 770  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 771 */