2 * Copyright (C) 2008 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 * Mutex-free cache for key1+key2=value.
19 #ifndef DALVIK_ATOMICCACHE_H_
20 #define DALVIK_ATOMICCACHE_H_
23 * If set to "1", gather some stats on our caching success rate.
25 #define CALC_CACHE_STATS 0
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).
32 * Must be exactly 16 bytes.
34 struct AtomicCacheEntry {
38 volatile u4 version; /* version and lock flag */
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.)
49 AtomicCacheEntry* entries; /* array of entries */
50 int numEntries; /* #of entries, must be power of 2 */
52 void* entryAlloc; /* memory allocated for entries */
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 */
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.
78 * We expect a 95+% hit rate for the things we use this for, so #2 is
79 * much better than #1.
81 * _cache is an AtomicCache*
82 * _cacheSize is _cache->cacheSize (can save a cycle avoiding the lookup)
83 * _key1, _key2 are the keys
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.
90 #if CALC_CACHE_STATS > 0
91 # define CACHE_XARG(_value) ,_value
93 # define CACHE_XARG(_value)
95 #define ATOMIC_CACHE_LOOKUP(_cache, _cacheSize, _key1, _key2) ({ \
96 AtomicCacheEntry* pEntry; \
98 u4 firstVersion, secondVersion; \
101 /* simple hash function */ \
102 hash = (((u4)(_key1) >> 2) ^ (u4)(_key2)) & ((_cacheSize)-1); \
103 pEntry = (_cache)->entries + hash; \
105 firstVersion = android_atomic_acquire_load((int32_t*)&pEntry->version); \
107 if (pEntry->key1 == (u4)(_key1) && pEntry->key2 == (u4)(_key2)) { \
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). \
114 value = android_atomic_acquire_load((int32_t*) &pEntry->value); \
115 secondVersion = pEntry->version; \
117 if ((firstVersion & 0x01) != 0 || firstVersion != secondVersion) { \
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. \
123 if (CALC_CACHE_STATS) \
125 value = (u4) ATOMIC_CACHE_CALC; \
128 if (CALC_CACHE_STATS) \
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 \
138 value = (u4) ATOMIC_CACHE_CALC; \
139 if (value == 0 && ATOMIC_CACHE_NULL_ALLOWED) { \
140 dvmUpdateAtomicCache((u4) (_key1), (u4) (_key2), value, pEntry, \
141 firstVersion CACHE_XARG(_cache) ); \
150 AtomicCache* dvmAllocAtomicCache(int numEntries);
155 void dvmFreeAtomicCache(AtomicCache* cache);
158 * Update a cache entry.
160 * Making the last argument optional, instead of merely unused, saves us
161 * a few percent in the ATOMIC_CACHE_LOOKUP time.
163 void dvmUpdateAtomicCache(u4 key1, u4 key2, u4 value, AtomicCacheEntry* pEntry,
165 #if CALC_CACHE_STATS > 0
166 , AtomicCache* pCache
173 void dvmDumpAtomicCacheStats(const AtomicCache* pCache);
175 #endif // DALVIK_ATOMICCACHE_H_