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  */