The Android Open Source Project | f6c3871 | 2009-03-03 19:28:47 -0800 | [diff] [blame] | 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 | /* |
| 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 | typedef struct AtomicCacheEntry { |
| 35 | u4 key1; |
| 36 | u4 key2; |
| 37 | u4 value; |
| 38 | volatile u4 version; /* version and lock flag */ |
| 39 | } AtomicCacheEntry; |
| 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 | typedef 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 | } AtomicCache; |
| 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 |
Andy McFadden | deeeeb2 | 2010-06-16 08:32:04 -0700 | [diff] [blame] | 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. |
The Android Open Source Project | f6c3871 | 2009-03-03 19:28:47 -0800 | [diff] [blame] | 69 | * (2) Have a "version" that gets incremented atomically when a write |
| 70 | * begins and again when it completes. Compare the version before |
Andy McFadden | deeeeb2 | 2010-06-16 08:32:04 -0700 | [diff] [blame] | 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 |
The Android Open Source Project | f6c3871 | 2009-03-03 19:28:47 -0800 | [diff] [blame] | 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; \ |
Andy McFadden | fc3d316 | 2010-08-05 14:34:26 -0700 | [diff] [blame] | 98 | u4 firstVersion, secondVersion; \ |
The Android Open Source Project | f6c3871 | 2009-03-03 19:28:47 -0800 | [diff] [blame] | 99 | u4 value; \ |
| 100 | \ |
| 101 | /* simple hash function */ \ |
| 102 | hash = (((u4)(_key1) >> 2) ^ (u4)(_key2)) & ((_cacheSize)-1); \ |
| 103 | pEntry = (_cache)->entries + hash; \ |
| 104 | \ |
Andy McFadden | fc3d316 | 2010-08-05 14:34:26 -0700 | [diff] [blame] | 105 | firstVersion = android_atomic_acquire_load((int32_t*)&pEntry->version); \ |
The Android Open Source Project | f6c3871 | 2009-03-03 19:28:47 -0800 | [diff] [blame] | 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 \ |
Andy McFadden | fc3d316 | 2010-08-05 14:34:26 -0700 | [diff] [blame] | 112 | * an update was in progress before we got here (unlikely). \ |
The Android Open Source Project | f6c3871 | 2009-03-03 19:28:47 -0800 | [diff] [blame] | 113 | */ \ |
Andy McFadden | fc3d316 | 2010-08-05 14:34:26 -0700 | [diff] [blame] | 114 | value = android_atomic_acquire_load((int32_t*) &pEntry->value); \ |
| 115 | secondVersion = pEntry->version; \ |
The Android Open Source Project | f6c3871 | 2009-03-03 19:28:47 -0800 | [diff] [blame] | 116 | \ |
Andy McFadden | fc3d316 | 2010-08-05 14:34:26 -0700 | [diff] [blame] | 117 | if ((firstVersion & 0x01) != 0 || firstVersion != secondVersion) { \ |
The Android Open Source Project | f6c3871 | 2009-03-03 19:28:47 -0800 | [diff] [blame] | 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*/ |