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 */
34struct 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 */
48struct 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 */
148AtomicCache* dvmAllocAtomicCache(int numEntries);
149
150/*
151 * Free a cache.
152 */
153void 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 */
161void 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 */
171void dvmDumpAtomicCacheStats(const AtomicCache* pCache);
172
173#endif  // DALVIK_ATOMICCACHE_H_
174