VirtualBox

Changeset 1857 in kBuild for trunk


Ignore:
Timestamp:
Oct 13, 2008 3:58:07 AM (16 years ago)
Author:
bird
Message:

kmk: improved the hashing of file table entries by making the strcache cache their hash values along with the string length.

Location:
trunk/src/kmk
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/kmk/file.c

    r1851 r1857  
    4141/* Hash table of files the makefile knows how to make.  */
    4242
     43#ifndef KMK
    4344static unsigned long
    4445file_hash_1 (const void *key)
    … …  
    5657file_hash_cmp (const void *x, const void *y)
    5758{
    58 #ifdef KMK
    59  /* since the names live in the strcache, there is a raging likelylood
    60     that we'll match on the string pointer.  Which is wee bit faster...  */
    61  struct file const *xf = ((struct file const *) x);
    62  struct file const *yf = ((struct file const *) y);
     59  return_ISTRING_COMPARE (((struct file const *) x)->hname,
     60                          ((struct file const *) y)->hname);
     61}
     62#else  /* KMK */
     63
     64static unsigned long
     65file_hash_1 (const void *key)
     66{
     67  struct file const *f = (struct file const *)key;
     68
     69  /* If it's cached, get the hash from the strcache. */
     70  if (f->name != (const char *)f)
     71    return strcache_get_hash1 (f->hname);
     72
     73  return_ISTRING_HASH_1 (f->hname);
     74}
     75
     76static unsigned long
     77file_hash_2 (const void *key)
     78{
     79  struct file const *f = (struct file const *)key;
     80
     81  /* If it's cached, get the hash from the strcache. */
     82  if (f->name != (const char *)f)
     83    return strcache_get_hash2 (f->hname);
     84
     85  return_ISTRING_HASH_2 (f->hname);
     86}
     87
     88static int
     89file_hash_cmp (const void *x, const void *y)
     90{
     91  struct file const *xf = ((struct file const *) x);
     92  struct file const *yf = ((struct file const *) y);
     93
     94  /* The file name strings all live in the strcache. However,
     95     lookup_file may or may not have a string from the cache. It indicates
     96     that it's responsible for the lookup by setting file::name to point
     97     to the file structure itself. So, when file::name points elsewhere
     98     we can omit the string compare, while when it isn't we can only
     99     check if they match that way. */
     100
    63101  if (xf->hname == yf->hname)
    64102    return 0;
     103  if (   xf->name != (const char *)xf
     104      && yf->name != (const char *)yf)
     105    return 1;
     106
    65107  return_ISTRING_COMPARE (xf->hname, yf->hname);
    66 #else
    67   return_ISTRING_COMPARE (((struct file const *) x)->hname,
    68                           ((struct file const *) y)->hname);
    69 #endif
    70 }
     108}
     109
     110#endif /* KMK */
    71111
    72112#ifndef FILE_BUCKETS
    … …  
    83123*/
    84124
     125#ifndef KMK
    85126struct file *
    86127lookup_file (const char *name)
     128#else  /* KMK */
     129MY_INLINE struct file *
     130lookup_file_common (const char *name, int cached)
     131#endif /* KMK */
    87132{
    88133  struct file *f;
    … …  
    132177#endif
    133178
     179#ifdef KMK
     180  /* uncached lookup indicator hack. */
     181  file_key.name = !cached ? (const char *)&file_key : NULL;
     182#endif
    134183  file_key.hname = name;
    135184  f = hash_find_item (&files, &file_key);
    … …  
    141190  return f;
    142191}
     192
     193#ifdef KMK
     194/* Given a name, return the struct file * for that name,
     195  or nil if there is none. */
     196
     197struct file *
     198lookup_file (const char *name)
     199{
     200  return lookup_file_common (name, 0 /* cached */);
     201}
     202
     203/* Given a name in the strcache, return the struct file * for that name,
     204  or nil if there is none. */
     205struct file *
     206lookup_file_cached (const char *name)
     207{
     208  assert (strcache_iscached (name));
     209  return lookup_file_common (name, 1 /* cached */);
     210}
     211#endif /* KMK */
     212
    143213
    144214/* Look up a file record for file NAME and return it.
    … …  
    222292  struct file *deleted_file;
    223293  struct file *f;
     294
     295#ifdef KMK
     296  assert (strcache_iscached (to_hname));
     297  assert (strcache_iscached (from_file->hname));
     298  file_key.name = NULL; /* cached lookup indicator hack. */
     299#endif
    224300
    225301  /* If it's already that name, we're done.  */

  • trunk/src/kmk/filedef.h

    r1701 r1857  
    107107                                   by the explicit multi target rule. */
    108108#endif
    109 #ifdef CONFIG_WITH_2ND_TARGET_EXPANSION   
    110     unsigned int need_2nd_target_expansion:1; /* Nonzero if this file needs 
     109#ifdef CONFIG_WITH_2ND_TARGET_EXPANSION
     110    unsigned int need_2nd_target_expansion:1; /* Nonzero if this file needs
    111111                                  second expansion of its name. Whether it
    112112                                  can receive this is decided at parse time,
    … …  
    122122
    123123struct file *lookup_file (const char *name);
     124#ifdef KMK
     125struct file *lookup_file_cached (const char *name);
     126#endif
    124127struct file *enter_file (const char *name);
    125128struct dep *parse_prereqs (char *prereqs);

  • trunk/src/kmk/make.h

    r1854 r1857  
    511511#endif
    512512#ifdef CONFIG_WITH_VALUE_LENGTH
     513struct strcache_pref
     514{
     515    unsigned long hash1;
     516    unsigned long hash2;
     517    unsigned int len;
     518};
     519
     520int strcache_check_sanity (const char *str);
     521unsigned long strcache_get_hash2_fallback (const char *str);
     522
    513523MY_INLINE unsigned int strcache_get_len (const char *str)
    514524{
    515   unsigned int len = ((unsigned int *)str)[-1];
    516   MY_ASSERT_MSG (strcache_iscached (str), ("\n"));
    517   MY_ASSERT_MSG (strlen (str) == len, ("\n"));
     525  struct strcache_pref const *prefix = (struct strcache_pref const *)str - 1;
     526  unsigned int len = prefix->len;
     527  MY_ASSERT_MSG (strcache_check_sanity (str) == 0, ("!\n"));
    518528  return len;
    519529}
     530
     531MY_INLINE unsigned int strcache_get_hash1 (const char *str)
     532{
     533  struct strcache_pref const *prefix = (struct strcache_pref const *)str - 1;
     534  unsigned long hash1 = prefix->hash1;
     535  MY_ASSERT_MSG (strcache_check_sanity (str) == 0, ("!\n"));
     536  return hash1;
     537}
     538
     539MY_INLINE unsigned long strcache_get_hash2 (const char *str)
     540{
     541  struct strcache_pref const *prefix = (struct strcache_pref const *)str - 1;
     542  unsigned long hash2 = prefix->hash2;
     543  MY_ASSERT_MSG (strcache_check_sanity (str) == 0, ("!\n"));
     544  if (!hash2)
     545    return strcache_get_hash2_fallback (str);
     546  return hash2;
     547}
     548
    520549#endif
    521550

  • trunk/src/kmk/read.c

    r1853 r1857  
    418418  deps->next = read_makefiles;
    419419  read_makefiles = deps;
     420#ifndef KMK
    420421  deps->file = lookup_file (filename);
     422#else
     423  deps->file = lookup_file_cached (filename);
     424#endif
    421425  if (deps->file == 0)
    422426    deps->file = enter_file (filename);
    … …  
    23022306             new entry if the file is a double-colon, which we don't want in
    23032307             this situation.  */
     2308#ifndef KMK
    23042309          f = lookup_file (name);
    23052310          if (!f)
    23062311            f = enter_file (strcache_add (name));
     2312#else  /* KMK */
     2313           /* XXX: this is probably already a cached string. */
     2314          fname = strcache_add (name);
     2315          f = lookup_file_cached (fname);
     2316          if (!f)
     2317            f = enter_file (fname);
     2318#endif
    23072319          else if (f->double_colon)
    23082320            f = f->double_colon;
    … …  
    26452657        {
    26462658          /* Double-colon.  Make a new record even if there already is one.  */
     2659#ifndef KMK
    26472660          f = lookup_file (name);
     2661#else  /* KMK - the name is already in the cache, don't waste time.  */
     2662          f = lookup_file_cached (name);
     2663#endif
    26482664
    26492665          /* Check for both : and :: rules.  Check is_target so
    … …  
    26522668            fatal (flocp,
    26532669                   _("target file `%s' has both : and :: entries"), f->name);
     2670#ifndef KMK
    26542671          f = enter_file (strcache_add (name));
     2672#else  /* KMK - the name is already in the cache, don't waste time.  */
     2673          f = enter_file (name);
     2674#endif
    26552675          /* If there was an existing entry and it was a double-colon entry,
    26562676             enter_file will have returned a new one, making it the prev

  • trunk/src/kmk/remake.c

    r1110 r1857  
    386386  if (file->multi_head != NULL && file->multi_head != file)
    387387    {
    388       DBS (DB_VERBOSE, (_("Considering target file `%s' -> multi head `%s'.\n"), 
     388      DBS (DB_VERBOSE, (_("Considering target file `%s' -> multi head `%s'.\n"),
    389389                          file->name, file->multi_head->name));
    390390      file = file->multi_head;
    … …  
    505505
    506506  /* Update all non-intermediate files we depend on, if necessary,
    507      and see whether any of them is more recent than this file. 
     507     and see whether any of them is more recent than this file.
    508508     For explicit multitarget rules we must iterate all the output
    509509     files to get the correct picture. */
    … …  
    523523          int maybe_make;
    524524          int dontcare = 0;
    525    
     525
    526526          check_renamed (d->file);
    527    
     527
    528528          mtime = file_mtime (d->file);
    529529          check_renamed (d->file);
    530    
     530
    531531          if (is_updating (d->file))
    532532            {
    … …  
    561561              continue;
    562562            }
    563    
     563
    564564#ifdef CONFIG_WITH_EXPLICIT_MULTITARGET
    565565          d->file->parent = f2;
    … …  
    568568#endif
    569569          maybe_make = must_make;
    570    
     570
    571571          /* Inherit dontcare flag from our parent. */
    572572          if (rebuilding_makefiles)
    … …  
    575575              d->file->dontcare = file->dontcare;
    576576            }
    577    
    578    
     577
     578
    579579          dep_status |= check_dep (d->file, depth, this_mtime, &maybe_make);
    580    
     580
    581581          /* Restore original dontcare flag. */
    582582          if (rebuilding_makefiles)
    583583            d->file->dontcare = dontcare;
    584    
     584
    585585          if (! d->ignore_mtime)
    586586            must_make = maybe_make;
    587    
     587
    588588          check_renamed (d->file);
    589    
     589
    590590          {
    591591            register struct file *f = d->file;
    … …  
    600600            while (f != 0);
    601601          }
    602    
     602
    603603          if (dep_status != 0 && !keep_going_flag)
    604604            break;
    605    
     605
    606606          if (!running)
    607607            /* The prereq is considered changed if the timestamp has changed while
    … …  
    609609            d->changed = ((file_mtime (d->file) != mtime)
    610610                          || (mtime == NONEXISTENT_MTIME));
    611    
     611
    612612          lastd = d;
    613613          d = d->next;
    … …  
    633633            {
    634634              int dontcare = 0;
    635    
     635
    636636              FILE_TIMESTAMP mtime = file_mtime (d->file);
    637637              check_renamed (d->file);
    … …  
    641641              d->file->parent = file;
    642642#endif
    643    
     643
    644644              /* Inherit dontcare flag from our parent. */
    645645              if (rebuilding_makefiles)
    … …  
    648648                  d->file->dontcare = file->dontcare;
    649649                }
    650    
    651    
     650
     651
    652652              dep_status |= update_file (d->file, depth);
    653    
     653
    654654              /* Restore original dontcare flag. */
    655655              if (rebuilding_makefiles)
    656656                d->file->dontcare = dontcare;
    657    
     657
    658658              check_renamed (d->file);
    659                  
     659
    660660              {
    661661                register struct file *f = d->file;
    … …  
    670670                while (f != 0);
    671671              }
    672    
     672
    673673              if (dep_status != 0 && !keep_going_flag)
    674674                break;
    675    
     675
    676676              if (!running)
    677677#ifdef CONFIG_WITH_EXPLICIT_MULTITARGET
    … …  
    741741#endif
    742742        check_renamed (d->file);
    743  
     743
    744744        if (! d->ignore_mtime)
    745745          {
    … …  
    753753              must_make = 1;
    754754#endif
    755  
     755
    756756            /* Set DEPS_CHANGED if this dep actually changed.  */
    757757            deps_changed |= d->changed;
    758758          }
    759  
     759
    760760        /* Set D->changed if either this dep actually changed,
    761761           or its dependent, FILE, is older or does not exist.  */
    762762        d->changed |= noexist || d_mtime > this_mtime;
    763  
     763
    764764        if (!noexist && ISDB (DB_BASIC|DB_VERBOSE))
    765765          {
    766766            const char *fmt = 0;
    767  
     767
    768768            if (d->ignore_mtime)
    769769              {
    … …  
    783783            else if (ISDB (DB_VERBOSE))
    784784              fmt = _("Prerequisite `%s' is older than target `%s'.\n");
    785  
     785
    786786            if (fmt)
    787787              {

  • trunk/src/kmk/strcache.c

    r1854 r1857  
    6161}
    6262
     63#ifndef CONFIG_WITH_VALUE_LENGTH
    6364static const char *
    6465add_string(const char *str, int len)
    … …  
    6768  struct strcache *sp;
    6869  const char *res;
    69 #ifdef CONFIG_WITH_VALUE_LENGTH
    70   int str_len = len;
    71   char *tmp;
    72 
    73   /* Add space a length prefix and the terminator and assure
    74      (somewhat) natural alignment. */
    75   len += sizeof(unsigned int) + 1;
    76   len = (len + sizeof(void *) - 1) & ~(sizeof(void *) - 1);
    77   --len;
    78 #endif
    7970
    8071  /* If the string we want is too large to fit into a single buffer, then
    … …  
    9889
    9990  /* Add the string to the best cache.  */
    100 #ifndef CONFIG_WITH_VALUE_LENGTH
    10191  res = best->end;
    10292  memcpy (best->end, str, len);
    … …  
    10595  best->bytesfree -= len + 1;
    10696  ++best->count;
     97  return res;
     98}
     99
    107100#else  /* CONFIG_WITH_VALUE_LENGTH */
    108   tmp = best->end;
    109   best->end += len + 1;
    110   assert(!((size_t)tmp & (sizeof(void *) - 1)));
    111 
    112   *(unsigned int *)tmp = str_len; /* length prefix */
    113   tmp += sizeof(unsigned int);
    114 
    115   res = tmp;
    116   memcpy (tmp, str, str_len);
    117   tmp += str_len;
    118   *(tmp++) = '\0';
    119 
    120   best->bytesfree -= len + 1;
     101
     102static const char *
     103add_string(const char *str, struct strcache_pref *prefix)
     104{
     105  struct strcache *best = NULL;
     106  struct strcache *sp;
     107  struct strcache_pref *real_prefix;
     108  int len;
     109  const char *res;
     110  char *dst;
     111
     112  /* Calc the entry length; the prefix data + the string + alignment. */
     113  len = sizeof(struct strcache_pref) + prefix->len + 1;
     114  len = (len + sizeof(void *) - 1) & ~(sizeof(void *) - 1);
     115
     116  /* If the string we want is too large to fit into a single buffer, then
     117     we're screwed; nothing will ever fit!  Change the maximum size of the
     118     cache to be big enough.  */
     119  if (len > bufsize)
     120    bufsize = len * 2;
     121
     122  /* First, find a cache with enough free space.  We always look through all
     123     the blocks and choose the one with the best fit (the one that leaves the
     124     least amount of space free).  */
     125  for (sp = strcache; sp != NULL; sp = sp->next)
     126    if (sp->bytesfree >= len && (!best || best->bytesfree > sp->bytesfree))
     127      best = sp;
     128
     129  /* If nothing is big enough, make a new cache.  */
     130  if (!best)
     131    best = new_cache();
     132
     133  assert (best->bytesfree >= len);
     134
     135  /* Add the string to the best cache.  */
     136  real_prefix = (struct strcache_pref *)best->end;
     137  *real_prefix = *prefix;
     138
     139  res = dst = (char *)(real_prefix + 1);
     140  assert(!((size_t)res & (sizeof(void *) - 1)));
     141  memcpy (dst, str, prefix->len);
     142  dst += prefix->len;
     143  *(dst++) = '\0';
     144
     145  best->end += len;
     146  best->bytesfree -= len;
    121147  ++best->count;
    122148
    123   assert (tmp <= best->end);
    124   assert (!((size_t)res & (sizeof(void *) - 1)));
    125 #endif /* CONFIG_WITH_VALUE_LENGTH */
    126149  return res;
    127150}
    128151
    129 
    130 /* Hash table of strings in the cache.  */
    131 
    132 #ifdef CONFIG_WITH_VALUE_LENGTH
    133152/* Hackish globals for passing data to the hash functions.
    134153   There isn't really any other way without running the
    135154   risk of breaking rehashing. */
    136155static const char *lookup_string;
    137 static unsigned int lookup_string_len;
    138 # ifdef CONFIG_WITH_INCLUDEDEP
    139 static unsigned long lookup_string_hash1;
    140 static unsigned long lookup_string_hash2;
    141 # endif /* CONFIG_WITH_INCLUDEDEP */
     156static struct strcache_pref *lookup_prefix;
     157
    142158#endif /* CONFIG_WITH_VALUE_LENGTH */
     159
     160
     161/* Hash table of strings in the cache.  */
    143162
    144163static unsigned long
    145164str_hash_1 (const void *key)
    146165{
    147 #ifdef CONFIG_WITH_INCLUDEDEP
    148   if ((const char *) key == lookup_string && lookup_string_hash1)
    149     return lookup_string_hash1;
     166#ifdef CONFIG_WITH_VALUE_LENGTH
     167  if (MY_PREDICT_TRUE ((const char *) key == lookup_string))
     168    return lookup_prefix->hash1;
    150169#endif
    151170  return_ISTRING_HASH_1 ((const char *) key);
    … …  
    155174str_hash_2 (const void *key)
    156175{
    157 #ifdef CONFIG_WITH_INCLUDEDEP
    158   if ((const char *) key == lookup_string && lookup_string_hash2)
    159     return lookup_string_hash2;
     176#ifdef CONFIG_WITH_VALUE_LENGTH
     177  if (MY_PREDICT_TRUE ((const char *) key == lookup_string))
     178    {
     179      if (lookup_prefix->hash2)
     180        {
     181          unsigned long hash2 = 0;
     182          ISTRING_HASH_2 ((const char *)key, hash2);
     183          lookup_prefix->hash2 = hash2;
     184        }
     185      return lookup_prefix->hash2;
     186    }
    160187#endif
    161188  return_ISTRING_HASH_2 ((const char *) key);
    … …  
    172199     kBuild scenario.  */
    173200
    174   if ((const char *) x == lookup_string)
    175     {
    176       assert (lookup_string_len == strlen ((const char *)x));
    177       if (strcache_get_len ((const char *)y) != lookup_string_len)
     201  if (MY_PREDICT_TRUE ((const char *) x == lookup_string))
     202    {
     203      assert (lookup_prefix->len == strlen ((const char *)x));
     204      if (strcache_get_len ((const char *)y) != lookup_prefix->len)
    178205        return -1;
    179206    }
    … …  
    185212static unsigned long total_adds = 0;
    186213
     214#ifndef CONFIG_WITH_VALUE_LENGTH
    187215static const char *
    188216add_hash (const char *str, int len)
    189217{
    190218  /* Look up the string in the hash.  If it's there, return it.  */
    191 #ifndef CONFIG_WITH_VALUE_LENGTH
    192219  char *const *slot = (char *const *) hash_find_slot (&strings, str);
    193220  const char *key = *slot;
    194 #else  /* CONFIG_WITH_VALUE_LENGTH */
    195   char *const *slot;
    196   const char *key;
    197 
    198   lookup_string = str;
    199   lookup_string_len = len;
    200   slot = (char *const *) hash_find_slot (&strings, str);
    201   key = *slot;
    202 #endif /* CONFIG_WITH_VALUE_LENGTH */
    203221
    204222  /* Count the total number of adds we performed.  */
    … …  
    213231  return key;
    214232}
     233
     234#else  /* CONFIG_WITH_VALUE_LENGTH */
     235
     236static const char *
     237add_hash (const char *str, int len, unsigned long hash1, unsigned long hash2)
     238{
     239  char *const *slot;
     240  const char *key;
     241  struct strcache_pref prefix;
     242
     243  /* Look up the string in the hash.  If it's there, return it.  */
     244  prefix.len = len;
     245  prefix.hash2 = hash2;
     246  if (!hash1 && !hash2)
     247    ISTRING_HASH_1 (str, hash1);
     248  prefix.hash1 = hash1;
     249
     250  lookup_string = str;
     251  lookup_prefix = &prefix;
     252
     253  slot = (char *const *) hash_find_slot (&strings, str);
     254  key = *slot;
     255
     256  /* Count the total number of adds we performed.  */
     257  ++total_adds;
     258
     259  if (!HASH_VACANT (key))
     260    return key;
     261
     262  /* Not there yet so add it to a buffer, then into the hash table.  */
     263  key = add_string (str,  &prefix);
     264  hash_insert_at (&strings, key, slot);
     265  return key;
     266}
     267
     268/* Verifies that a string cache entry didn't change and that the
     269   prefix is still valid. */
     270int
     271strcache_check_sanity (const char *str)
     272{
     273  struct strcache_pref const *prefix = (struct strcache_pref const *)str - 1;
     274  unsigned long hash;
     275
     276  if (strlen (str) != prefix->len)
     277    {
     278      MY_ASSERT_MSG (0, ("len: %u != %u - '%s'\n", (unsigned int)strlen (str),
     279                         prefix->len, str));
     280      return -1;
     281    }
     282
     283  hash = 0;
     284  ISTRING_HASH_1 (str, hash);
     285  if (hash != prefix->hash1)
     286    {
     287      MY_ASSERT_MSG (0, ("hash1: %lx != %lx - '%s'\n", hash, prefix->hash1, str));
     288      return -1;
     289    }
     290
     291  if (prefix->hash2)
     292    {
     293      hash = 0;
     294      ISTRING_HASH_2 (str, hash);
     295      if (hash != prefix->hash2)
     296        {
     297          MY_ASSERT_MSG (0, ("hash2: %lx != %lx - '%s'\n", hash, prefix->hash2, str));
     298          return -1;
     299        }
     300    }
     301
     302  return 0;
     303}
     304
     305/* Fallback for when the hash2 value isn't present. */
     306unsigned long
     307strcache_get_hash2_fallback (const char *str)
     308{
     309  struct strcache_pref *prefix = (struct strcache_pref *)str - 1;
     310  unsigned long hash2 = 0;
     311
     312  ISTRING_HASH_2 (str, hash2);
     313  prefix->hash2 = hash2;
     314
     315  return hash2;
     316}
     317
     318#endif /* CONFIG_WITH_VALUE_LENGTH */
    215319
    216320/* Returns true if the string is in the cache; false if not.  */
    … …  
    233337strcache_add (const char *str)
    234338{
     339#ifndef CONFIG_WITH_VALUE_LENGTH
    235340  return add_hash (str, strlen (str));
     341#else
     342  /* XXX: calc the hash1 while determining the string length. */
     343  return add_hash (str, strlen (str), 0, 0);
     344#endif
    236345}
    237346
    … …  
    249358    }
    250359
     360#ifndef CONFIG_WITH_VALUE_LENGTH
    251361  return add_hash (str, len);
     362#else
     363  /* XXX: eliminate the alloca mess using the prefixing? */
     364  return add_hash (str, len, 0, 0);
     365#endif
    252366}
    253367
    … …  
    260374                        unsigned long hash2)
    261375{
    262   const char *retstr;
    263 
    264   assert (hash1 == str_hash_1 (str));
    265   assert (hash2 == str_hash_2 (str));
    266 
    267   lookup_string_hash1 = hash1;
    268   lookup_string_hash2 = hash2;
    269 
    270   retstr = add_hash (str, len);
    271 
    272   lookup_string_hash1 = 0;
    273   lookup_string_hash2 = 0;
    274 
    275   return retstr;
     376  return add_hash (str, len, hash1, hash2);
    276377}
    277378
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