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