vm/AtomicCache.h

   1 /*
   2  * Copyright (C) 2008 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 /*
  17  * Mutex-free cache for key1+key2=value.
  18  */
  19 #ifndef _DALVIK_ATOMICCACHE
  20 #define _DALVIK_ATOMICCACHE
  21
  22 #ifdef __cplusplus
  23 extern "C" {
  24 #endif
  25
  26 /*
  27  * If set to "1", gather some stats on our caching success rate.
  28  */
  29 #define CALC_CACHE_STATS 0
  30
  31
  32 /*
  33  * One entry in the cache.  We store two keys (e.g. the classes that are
  34  * arguments to "instanceof") and one result (e.g. a boolean value).
  35  *
  36  * Must be exactly 16 bytes.
  37  */
  38 typedef struct AtomicCacheEntry {
  39     u4          key1;
  40     u4          key2;
  41     u4          value;
  42     volatile u4 version;    /* version and lock flag */
  43 } AtomicCacheEntry;
  44
  45 /*
  46  * One cache.
  47  *
  48  * Thought: we might be able to save a few cycles by storing the cache
  49  * struct and "entries" separately, avoiding an indirection.  (We already
  50  * handle "numEntries" separately in ATOMIC_CACHE_LOOKUP.)
  51  */
  52 typedef struct AtomicCache {
  53     AtomicCacheEntry*   entries;        /* array of entries */
  54     int         numEntries;             /* #of entries, must be power of 2 */
  55
  56     void*       entryAlloc;             /* memory allocated for entries */
  57
  58     /* cache stats; note we don't guarantee atomic increments for these */
  59     int         trivial;                /* cache access not required */
  60     int         fail;                   /* contention failure */
  61     int         hits;                   /* found entry in cache */
  62     int         misses;                 /* entry was for other keys */
  63     int         fills;                  /* entry was empty */
  64 } AtomicCache;
  65
  66 /*
  67  * Do a cache lookup.  We need to be able to read and write entries
  68  * atomically.  There are a couple of ways to do this:
  69  *  (1) Have a global lock.  A mutex is too heavy, so instead we would use
  70  *      an atomic flag.  If the flag is set, we could sit and spin,
  71  *      but if we're a high-priority thread that may cause a lockup.
  72  *      Better to just ignore the cache and do the full computation.
  73  *  (2) Have a "version" that gets incremented atomically when a write
  74  *      begins and again when it completes.  Compare the version before
  75  *      and after doing reads.  So long as we have memory barriers in the
  76  *      right place the compiler and CPU will do the right thing, allowing
  77  *      us to skip atomic ops in the common read case.  The table updates
  78  *      are expensive, requiring two writes with barriers.  We also need
  79  *      some sort of lock to ensure that nobody else tries to start an
  80  *      update while we're in the middle of one.
  81  *
  82  * We expect a 95+% hit rate for the things we use this for, so #2 is
  83  * much better than #1.
  84  *
  85  * _cache is an AtomicCache*
  86  * _cacheSize is _cache->cacheSize (can save a cycle avoiding the lookup)
  87  * _key1, _key2 are the keys
  88  *
  89  * Define a function ATOMIC_CACHE_CALC that returns a 32-bit value.  This
  90  * will be invoked when we need to compute the value.
  91  *
  92  * Returns the value.
  93  */
  94 #if CALC_CACHE_STATS > 0
  95 # define CACHE_XARG(_value) ,_value
  96 #else
  97 # define CACHE_XARG(_value)
  98 #endif
  99 #define ATOMIC_CACHE_LOOKUP(_cache, _cacheSize, _key1, _key2) ({            \
 100     AtomicCacheEntry* pEntry;                                               \
 101     int hash;                                                               \
 102     u4 firstVersion, secondVersion;                                         \
 103     u4 value;                                                               \
 104                                                                             \
 105     /* simple hash function */                                              \
 106     hash = (((u4)(_key1) >> 2) ^ (u4)(_key2)) & ((_cacheSize)-1);           \
 107     pEntry = (_cache)->entries + hash;                                      \
 108                                                                             \
 109     firstVersion = android_atomic_acquire_load((int32_t*)&pEntry->version); \
 110                                                                             \
 111     if (pEntry->key1 == (u4)(_key1) && pEntry->key2 == (u4)(_key2)) {       \
 112         /*                                                                  \
 113          * The fields match.  Get the value, then read the version a        \
 114          * second time to verify that we didn't catch a partial update.     \
 115          * We're also hosed if "firstVersion" was odd, indicating that      \
 116          * an update was in progress before we got here (unlikely).         \
 117          */                                                                 \
 118         value = android_atomic_acquire_load((int32_t*) &pEntry->value);     \
 119         secondVersion = pEntry->version;                                    \
 120                                                                             \
 121         if ((firstVersion & 0x01) != 0 || firstVersion != secondVersion) {  \
 122             /*                                                              \
 123              * We clashed with another thread.  Instead of sitting and      \
 124              * spinning, which might not complete if we're a high priority  \
 125              * thread, just do the regular computation.                     \
 126              */                                                             \
 127             if (CALC_CACHE_STATS)                                           \
 128                 (_cache)->fail++;                                           \
 129             value = (u4) ATOMIC_CACHE_CALC;                                 \
 130         } else {                                                            \
 131             /* all good */                                                  \
 132             if (CALC_CACHE_STATS)                                           \
 133                 (_cache)->hits++;                                           \
 134         }                                                                   \
 135     } else {                                                                \
 136         /*                                                                  \
 137          * Compute the result and update the cache.  We really want this    \
 138          * to happen in a different method -- it makes the ARM frame        \
 139          * setup for this method simpler, which gives us a ~10% speed       \
 140          * boost.                                                           \
 141          */                                                                 \
 142         value = (u4) ATOMIC_CACHE_CALC;                                     \
 143         dvmUpdateAtomicCache((u4) (_key1), (u4) (_key2), value, pEntry,     \
 144                     firstVersion CACHE_XARG(_cache) );                      \
 145     }                                                                       \
 146     value;                                                                  \
 147 })
 148
 149 /*
 150  * Allocate a cache.
 151  */
 152 AtomicCache* dvmAllocAtomicCache(int numEntries);
 153
 154 /*
 155  * Free a cache.
 156  */
 157 void dvmFreeAtomicCache(AtomicCache* cache);
 158
 159 /*
 160  * Update a cache entry.
 161  *
 162  * Making the last argument optional, instead of merely unused, saves us
 163  * a few percent in the ATOMIC_CACHE_LOOKUP time.
 164  */
 165 void dvmUpdateAtomicCache(u4 key1, u4 key2, u4 value, AtomicCacheEntry* pEntry,
 166     u4 firstVersion
 167 #if CALC_CACHE_STATS > 0
 168     , AtomicCache* pCache
 169 #endif
 170     );
 171
 172 /*
 173  * Debugging.
 174  */
 175 void dvmDumpAtomicCacheStats(const AtomicCache* pCache);
 176
 177 #ifdef __cplusplus
 178 }
 179 #endif
 180
 181 #endif /*_DALVIK_ATOMICCACHE*/