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