VirtualBox

Changeset 1895 in kBuild


Ignore:
Timestamp:
Oct 21, 2008 12:48:25 AM (16 years ago)
Author:
bird
Message:

kmk: strcache cleanup.

Location:
trunk/src/kmk
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/kmk/incdep.c

    r1875 r1895  
    769769{
    770770  if (!entry->user)
    771     entry->user = (void *)strcache_add_prehashed ((const char *)(entry + 1),
    772                                                   entry->length,
    773                                                   entry->hash1,
    774                                                   entry->hash2);
     771    entry->user = (void *)strcache2_add_hashed (&file_strcache,
     772                                                (const char *)(entry + 1),
     773                                                entry->length,
     774                                                entry->hash1,
     775                                                entry->hash2);
    775776  return (const char *)entry->user;
    776777}

  • trunk/src/kmk/make.h

    r1893 r1895  
    593593const char *strcache_add_len (const char *str, int len);
    594594int strcache_setbufsize (int size);
    595 # ifdef CONFIG_WITH_INCLUDEDEP
    596 const char *strcache_add_prehashed (const char *str, int len,
    597                                     unsigned long hash1, unsigned long hash2);
    598 void strcache_prehash_str (const char *str, unsigned int len, unsigned long *hash1p,
    599                            unsigned long *hash2p);
    600 #endif
    601 #ifdef CONFIG_WITH_VALUE_LENGTH
    602 struct strcache_pref
    603 {
    604     unsigned long hash1;
    605     unsigned long hash2;
    606     unsigned int len;
    607 };
    608 
    609 int strcache_check_sanity (const char *str);
    610 unsigned long strcache_get_hash2_fallback (const char *str);
    611 
    612 MY_INLINE unsigned int strcache_get_len (const char *str)
    613 {
    614   struct strcache_pref const *prefix = (struct strcache_pref const *)str - 1;
    615   unsigned int len = prefix->len;
    616   MY_ASSERT_MSG (strcache_check_sanity (str) == 0, ("!\n"));
    617   return len;
    618 }
    619 
    620 /* FIXME: make a 2nd version of this which uses the unique string address, it
    621    is more efficient than the string hash we calculate on most systems. */
    622 MY_INLINE unsigned int strcache_get_hash1 (const char *str)
    623 {
    624   struct strcache_pref const *prefix = (struct strcache_pref const *)str - 1;
    625   unsigned long hash1 = prefix->hash1;
    626   MY_ASSERT_MSG (strcache_check_sanity (str) == 0, ("!\n"));
    627   return hash1;
    628 }
    629 
    630 MY_INLINE unsigned long strcache_get_hash2 (const char *str)
    631 {
    632   struct strcache_pref const *prefix = (struct strcache_pref const *)str - 1;
    633   unsigned long hash2 = prefix->hash2;
    634   MY_ASSERT_MSG (strcache_check_sanity (str) == 0, ("!\n"));
    635   if (!hash2)
    636     return strcache_get_hash2_fallback (str);
    637   return hash2;
    638 }
    639 
    640 # endif /* CONFIG_WITH_VALUE_LENGTH*/
    641 
    642595#else  /* CONFIG_WITH_STRCACHE2 */
    643596
    … …  
    648601# define strcache_add(str)          strcache2_add_file(&file_strcache, str, strlen (str))
    649602# define strcache_add_len(str, len) strcache2_add_file(&file_strcache, str, len)
    650 # ifdef CONFIG_WITH_INCLUDEDEP
    651 #  define strcache_add_prehashed(str, len, hash1, hash2) \
    652     strcache2_add_hashed(&file_strcache, str, len, hash1, hash2)
    653 #  ifdef HAVE_CASE_INSENSITIVE_FS
    654 #   define strcache_prehash_str(str, length, hash1p, hash2p) \
    655      do { *(hash1p) = strcache2_hash_istr (str, length, (hash2p)); } while (0)
    656 #  else
    657 #   define strcache_prehash_str(str, length, hash1p, hash2p) \
    658      do { *(hash1p) = strcache2_hash_str (str, length, (hash2p)); } while (0)
    659 #  endif
    660 # endif /* CONFIG_WITH_INCLUDEDEP */
    661 # ifdef CONFIG_WITH_VALUE_LENGTH
    662 #  define strcache_get_len(str)     strcache2_get_len(&file_strcache, str)
    663 #  define strcache_get_hash1(str)   strcache2_get_hash1(&file_strcache, str)
    664 #  define strcache_get_hash2(str)   strcache2_get_hash2(&file_strcache, str)
    665 # endif /* CONFIG_WITH_VALUE_LENGTH */
     603# define strcache_get_len(str)      strcache2_get_len(&file_strcache, str)
     604# define strcache_get_hash1(str)    strcache2_get_hash1(&file_strcache, str)
     605# define strcache_get_hash2(str)    strcache2_get_hash2(&file_strcache, str)
    666606
    667607#endif /* CONFIG_WITH_STRCACHE2 */

  • trunk/src/kmk/strcache.c

    r1870 r1895  
    2121
    2222#include "hash.h"
    23 
    2423
    2524/* The size (in bytes) of each cache buffer.
    … …  
    6362}
    6463
    65 #ifndef CONFIG_WITH_VALUE_LENGTH
    6664static const char *
    6765add_string(const char *str, int len)
    … …  
    9795  best->bytesfree -= len + 1;
    9896  ++best->count;
     97
    9998  return res;
    10099}
    101 
    102 #else  /* CONFIG_WITH_VALUE_LENGTH */
    103 
    104 static const char *
    105 add_string(const char *str, struct strcache_pref *prefix)
    106 {
    107   struct strcache *best = NULL;
    108   struct strcache *sp;
    109   struct strcache_pref *real_prefix;
    110   int len;
    111   const char *res;
    112   char *dst;
    113 
    114   /* Calc the entry length; the prefix data + the string + alignment. */
    115   len = sizeof(struct strcache_pref) + prefix->len + 1;
    116   len = (len + sizeof(void *) - 1) & ~(sizeof(void *) - 1);
    117 
    118   /* If the string we want is too large to fit into a single buffer, then
    119      we're screwed; nothing will ever fit!  Change the maximum size of the
    120      cache to be big enough.  */
    121   if (len > bufsize)
    122     bufsize = len * 2;
    123 
    124   /* First, find a cache with enough free space.  We always look through all
    125      the blocks and choose the one with the best fit (the one that leaves the
    126      least amount of space free).  */
    127   for (sp = strcache; sp != NULL; sp = sp->next)
    128     if (sp->bytesfree >= len && (!best || best->bytesfree > sp->bytesfree))
    129       best = sp;
    130 
    131   /* If nothing is big enough, make a new cache.  */
    132   if (!best)
    133     best = new_cache();
    134 
    135   assert (best->bytesfree >= len);
    136 
    137   /* Add the string to the best cache.  */
    138   real_prefix = (struct strcache_pref *)best->end;
    139   *real_prefix = *prefix;
    140 
    141   res = dst = (char *)(real_prefix + 1);
    142   assert(!((size_t)res & (sizeof(void *) - 1)));
    143   memcpy (dst, str, prefix->len);
    144   dst += prefix->len;
    145   *(dst++) = '\0';
    146 
    147   best->end += len;
    148   best->bytesfree -= len;
    149   ++best->count;
    150 
    151   return res;
    152 }
    153 
    154 /* Hackish globals for passing data to the hash functions.
    155    There isn't really any other way without running the
    156    risk of breaking rehashing. */
    157 static const char *lookup_string;
    158 static struct strcache_pref *lookup_prefix;
    159 
    160 #endif /* CONFIG_WITH_VALUE_LENGTH */
    161100
    162101
    … …  
    166105str_hash_1 (const void *key)
    167106{
    168 #if 0
    169 #ifdef CONFIG_WITH_VALUE_LENGTH
    170   if (MY_PREDICT_TRUE ((const char *) key == lookup_string))
    171     return lookup_prefix->hash1;
    172 #endif
    173 #endif
    174107  return_ISTRING_HASH_1 ((const char *) key);
    175108}
    … …  
    178111str_hash_2 (const void *key)
    179112{
    180 #ifdef CONFIG_WITH_VALUE_LENGTH
    181   if (MY_PREDICT_TRUE ((const char *) key == lookup_string))
    182     {
    183       if (lookup_prefix->hash2)
    184         {
    185           unsigned long hash2 = 0;
    186           ISTRING_HASH_2 ((const char *)key, hash2);
    187           lookup_prefix->hash2 = hash2;
    188         }
    189       return lookup_prefix->hash2;
    190     }
    191 #endif
    192113  return_ISTRING_HASH_2 ((const char *) key);
    193114}
    … …  
    196117str_hash_cmp (const void *x, const void *y)
    197118{
    198 #ifdef CONFIG_WITH_VALUE_LENGTH
    199   /* Use the string length to avoid some unncessary comparing.
    200      X is either the add_hash input (during hash_find_slot)
    201      or a cache entry (during rare hash_insert_at calls).
    202      This catches 520253 out of 1341947 calls in the typical
    203      kBuild scenario.  */
    204 
    205   if (MY_PREDICT_TRUE ((const char *) x == lookup_string))
    206     {
    207       assert (lookup_prefix->len == strlen ((const char *)x));
    208       if (strcache_get_len ((const char *)y) != lookup_prefix->len)
    209         return -1;
    210     }
    211 #endif
    212119  return_ISTRING_COMPARE ((const char *) x, (const char *) y);
    213120}
    … …  
    216123static unsigned long total_adds = 0;
    217124
    218 #ifndef CONFIG_WITH_VALUE_LENGTH
    219125static const char *
    220126add_hash (const char *str, int len)
    … …  
    235141  return key;
    236142}
    237 
    238 #else  /* CONFIG_WITH_VALUE_LENGTH */
    239 
    240 static const char *
    241 add_hash (const char *str, int len, unsigned long hash1, unsigned long hash2)
    242 {
    243   void const **slot;
    244   const char *key;
    245   struct strcache_pref prefix;
    246 
    247   /* Look up the string in the hash.  If it's there, return it.  */
    248   prefix.len = len;
    249   prefix.hash2 = hash2;
    250   if (!hash1 && !hash2)
    251     ISTRING_HASH_1 (str, hash1);
    252   prefix.hash1 = hash1;
    253 
    254   lookup_string = str;
    255   lookup_prefix = &prefix;
    256 
    257   slot = hash_find_slot_prehashed (&strings, str, prefix.hash1, prefix.hash2);
    258   key = *(const char **)slot;
    259 
    260   /* Count the total number of adds we performed.  */
    261   ++total_adds;
    262 
    263   if (!HASH_VACANT (key))
    264     return key;
    265 
    266   /* Not there yet so add it to a buffer, then into the hash table.  */
    267   key = add_string (str,  &prefix);
    268   hash_insert_at (&strings, key, slot);
    269   return key;
    270 }
    271 
    272 /* Verifies that a string cache entry didn't change and that the
    273    prefix is still valid. */
    274 int
    275 strcache_check_sanity (const char *str)
    276 {
    277   struct strcache_pref const *prefix = (struct strcache_pref const *)str - 1;
    278   unsigned long hash;
    279 
    280   if (strlen (str) != prefix->len)
    281     {
    282       MY_ASSERT_MSG (0, ("len: %u != %u - '%s'\n", (unsigned int)strlen (str),
    283                          prefix->len, str));
    284       return -1;
    285     }
    286 
    287   hash = 0;
    288   ISTRING_HASH_1 (str, hash);
    289   if (hash != prefix->hash1)
    290     {
    291       MY_ASSERT_MSG (0, ("hash1: %lx != %lx - '%s'\n", hash, prefix->hash1, str));
    292       return -1;
    293     }
    294 
    295   if (prefix->hash2)
    296     {
    297       hash = 0;
    298       ISTRING_HASH_2 (str, hash);
    299       if (hash != prefix->hash2)
    300         {
    301           MY_ASSERT_MSG (0, ("hash2: %lx != %lx - '%s'\n", hash, prefix->hash2, str));
    302           return -1;
    303         }
    304     }
    305 
    306   return 0;
    307 }
    308 
    309 /* Fallback for when the hash2 value isn't present. */
    310 unsigned long
    311 strcache_get_hash2_fallback (const char *str)
    312 {
    313   struct strcache_pref *prefix = (struct strcache_pref *)str - 1;
    314   unsigned long hash2 = 0;
    315 
    316   ISTRING_HASH_2 (str, hash2);
    317   prefix->hash2 = hash2;
    318 
    319   return hash2;
    320 }
    321 
    322 #endif /* CONFIG_WITH_VALUE_LENGTH */
    323143
    324144/* Returns true if the string is in the cache; false if not.  */
    … …  
    341161strcache_add (const char *str)
    342162{
    343 #ifndef CONFIG_WITH_VALUE_LENGTH
    344163  return add_hash (str, strlen (str));
    345 #else
    346   /* XXX: calc the hash1 while determining the string length. */
    347   return add_hash (str, strlen (str), 0, 0);
    348 #endif
    349164}
    350165
    … …  
    362177    }
    363178
    364 #ifndef CONFIG_WITH_VALUE_LENGTH
    365179  return add_hash (str, len);
    366 #else
    367   /* XXX: eliminate the alloca mess using the prefixing? */
    368   return add_hash (str, len, 0, 0);
    369 #endif
    370 }
    371 
    372 #ifdef CONFIG_WITH_INCLUDEDEP
    373 
    374 /* A special variant used by the includedep worker threads, it off loads
    375    the main thread when it adds the strings to the cache later. */
    376 const char *
    377 strcache_add_prehashed (const char *str, int len, unsigned long hash1,
    378                         unsigned long hash2)
    379 {
    380   return add_hash (str, len, hash1, hash2);
    381 }
    382 
    383 /* Performs the prehashing for use with strcache_add_prehashed(). */
    384 void
    385 strcache_prehash_str (const char *str, unsigned int len, unsigned long *hash1p,
    386                       unsigned long *hash2p)
    387 {
    388   (void)len;
    389   *hash1p = str_hash_1 (str);
    390   *hash2p = str_hash_2 (str);
    391 }
    392 
    393 #endif /* CONFIG_WITH_INCLUDEDEP */
     180}
    394181
    395182int
    … …  
    404191strcache_init (void)
    405192{
    406 #ifdef KMK
    407   hash_init (&strings, 65535, str_hash_1, str_hash_2, str_hash_cmp);
    408 #else
    409193  hash_init (&strings, 8000, str_hash_1, str_hash_2, str_hash_cmp);
    410 #endif
    411194}
    412195
    … …  
    491274}
    492275
    493 
    494276#endif /* CONFIG_WITH_STRCACHE2 */
     277
Note: See TracChangeset for help on using the changeset viewer.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette