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 */ 16deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Mutex-free cache. Each entry has two 32-bit keys, one 32-bit value, 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and a 32-bit version. 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#include "Dalvik.h" 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#include <stdlib.h> 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * I think modern C mandates that the results of a boolean expression are 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 0 or 1. If not, or we suddenly turn into C++ and bool != int, use this. 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define BOOL_TO_INT(x) (x) 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project//#define BOOL_TO_INT(x) ((x) ? 1 : 0) 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define CPU_CACHE_WIDTH 32 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define CPU_CACHE_WIDTH_1 (CPU_CACHE_WIDTH-1) 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#define ATOMIC_LOCK_FLAG (1 << 31) 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Allocate cache. 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source ProjectAtomicCache* dvmAllocAtomicCache(int numEntries) 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project AtomicCache* newCache; 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newCache = (AtomicCache*) calloc(1, sizeof(AtomicCache)); 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newCache == NULL) 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return NULL; 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newCache->numEntries = numEntries; 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newCache->entryAlloc = calloc(1, 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project sizeof(AtomicCacheEntry) * numEntries + CPU_CACHE_WIDTH); 52f61171f4800799fa604850e39e6ae88368fe1ee4You Kim if (newCache->entryAlloc == NULL) { 53f61171f4800799fa604850e39e6ae88368fe1ee4You Kim free(newCache); 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return NULL; 55f61171f4800799fa604850e39e6ae88368fe1ee4You Kim } 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adjust storage to align on a 32-byte boundary. Each entry is 16 bytes 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * wide. This ensures that each cache entry sits on a single CPU cache 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * line. 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert(sizeof(AtomicCacheEntry) == 16); 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newCache->entries = (AtomicCacheEntry*) 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (((int) newCache->entryAlloc + CPU_CACHE_WIDTH_1) & ~CPU_CACHE_WIDTH_1); 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newCache; 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Free cache. 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmFreeAtomicCache(AtomicCache* cache) 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (cache != NULL) { 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(cache->entryAlloc); 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project free(cache); 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Update a cache entry. 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * In the event of a collision with another thread, the update may be skipped. 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We only need "pCache" for stats. 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmUpdateAtomicCache(u4 key1, u4 key2, u4 value, AtomicCacheEntry* pEntry, 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project u4 firstVersion 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#if CALC_CACHE_STATS > 0 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project , AtomicCache* pCache 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#endif 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ) 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 96deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * The fields don't match, so we want to update them. There is a risk 97deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * that another thread is also trying to update them, so we grab an 98deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * ownership flag to lock out other threads. 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * If the lock flag was already set in "firstVersion", somebody else 101deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * was in mid-update, and we don't want to continue here. (This means 102deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * that using "firstVersion" as the "before" argument to the CAS would 103deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * succeed when it shouldn't and vice-versa -- we could also just pass 104deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * in (firstVersion & ~ATOMIC_LOCK_FLAG) as the first argument.) 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 106deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * NOTE: we don't deal with the situation where we overflow the version 107deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * counter and trample the ATOMIC_LOCK_FLAG (at 2^31). Probably not 108deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * a real concern. 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if ((firstVersion & ATOMIC_LOCK_FLAG) != 0 || 1116e10b9aaa72425a4825a25f0043533d0c6fdbba4Andy McFadden android_atomic_release_cas( 1126e10b9aaa72425a4825a25f0043533d0c6fdbba4Andy McFadden firstVersion, firstVersion | ATOMIC_LOCK_FLAG, 1136e10b9aaa72425a4825a25f0043533d0c6fdbba4Andy McFadden (volatile s4*) &pEntry->version) != 0) 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project { 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * We couldn't get the write lock. Return without updating the table. 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#if CALC_CACHE_STATS > 0 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pCache->fail++; 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#endif 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* must be even-valued on entry */ 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assert((firstVersion & 0x01) == 0); 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#if CALC_CACHE_STATS > 0 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* for stats, assume a key value of zero indicates an empty entry */ 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pEntry->key1 == 0) 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pCache->fills++; 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project else 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pCache->misses++; 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project#endif 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 135deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden /* 136deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * We have the write lock, but somebody could be reading this entry 137deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * while we work. We use memory barriers to ensure that the state 138deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden * is always consistent when the version number is even. 139deeeeb264fc6f4ab7f5cb6e01b9dd76f487ff914Andy McFadden */ 140fc3d31683a0120ba005f45f98dcbe1001064dafbAndy McFadden u4 newVersion = (firstVersion | ATOMIC_LOCK_FLAG) + 1; 141fc3d31683a0120ba005f45f98dcbe1001064dafbAndy McFadden assert((newVersion & 0x01) == 1); 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 143fc3d31683a0120ba005f45f98dcbe1001064dafbAndy McFadden pEntry->version = newVersion; 144fc3d31683a0120ba005f45f98dcbe1001064dafbAndy McFadden 145fc3d31683a0120ba005f45f98dcbe1001064dafbAndy McFadden android_atomic_release_store(key1, (int32_t*) &pEntry->key1); 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry->key2 = key2; 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pEntry->value = value; 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 149fc3d31683a0120ba005f45f98dcbe1001064dafbAndy McFadden newVersion++; 150fc3d31683a0120ba005f45f98dcbe1001064dafbAndy McFadden android_atomic_release_store(newVersion, (int32_t*) &pEntry->version); 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Clear the lock flag. Nobody else should have been able to modify 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * pEntry->version, so if this fails the world is broken. 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 156fc3d31683a0120ba005f45f98dcbe1001064dafbAndy McFadden assert(newVersion == ((firstVersion + 2) | ATOMIC_LOCK_FLAG)); 1576e10b9aaa72425a4825a25f0043533d0c6fdbba4Andy McFadden if (android_atomic_release_cas( 158fc3d31683a0120ba005f45f98dcbe1001064dafbAndy McFadden newVersion, newVersion & ~ATOMIC_LOCK_FLAG, 1596e10b9aaa72425a4825a25f0043533d0c6fdbba4Andy McFadden (volatile s4*) &pEntry->version) != 0) 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project { 161c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block //ALOGE("unable to reset the instanceof cache ownership"); 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmAbort(); 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Dump the "instanceof" cache stats. 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectvoid dvmDumpAtomicCacheStats(const AtomicCache* pCache) 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project{ 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pCache == NULL) 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project dvmFprintf(stdout, 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "Cache stats: trv=%d fai=%d hit=%d mis=%d fil=%d %d%% (size=%d)\n", 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pCache->trivial, pCache->fail, pCache->hits, 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pCache->misses, pCache->fills, 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (pCache->hits == 0) ? 0 : 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pCache->hits * 100 / 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project (pCache->fail + pCache->hits + pCache->misses + pCache->fills), 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project pCache->numEntries); 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 183