blob: cee84a892340b3a44fa71a763689952f02701b57 [file] [log] [blame]
/*
* Copyright (C) 2008 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*
* Mutex-free cache. Each entry has two 32-bit keys, one 32-bit value,
* and a 32-bit version.
*/
#include "Dalvik.h"
#include <stdlib.h>
/*
* I think modern C mandates that the results of a boolean expression are
* 0 or 1. If not, or we suddenly turn into C++ and bool != int, use this.
*/
#define BOOL_TO_INT(x) (x)
//#define BOOL_TO_INT(x) ((x) ? 1 : 0)
#define CPU_CACHE_WIDTH 32
#define CPU_CACHE_WIDTH_1 (CPU_CACHE_WIDTH-1)
#define ATOMIC_LOCK_FLAG (1 << 31)
/*
* Allocate cache.
*/
AtomicCache* dvmAllocAtomicCache(int numEntries)
{
AtomicCache* newCache;
newCache = (AtomicCache*) calloc(1, sizeof(AtomicCache));
if (newCache == NULL)
return NULL;
newCache->numEntries = numEntries;
newCache->entryAlloc = calloc(1,
sizeof(AtomicCacheEntry) * numEntries + CPU_CACHE_WIDTH);
if (newCache->entryAlloc == NULL)
return NULL;
/*
* Adjust storage to align on a 32-byte boundary. Each entry is 16 bytes
* wide. This ensures that each cache entry sits on a single CPU cache
* line.
*/
assert(sizeof(AtomicCacheEntry) == 16);
newCache->entries = (AtomicCacheEntry*)
(((int) newCache->entryAlloc + CPU_CACHE_WIDTH_1) & ~CPU_CACHE_WIDTH_1);
return newCache;
}
/*
* Free cache.
*/
void dvmFreeAtomicCache(AtomicCache* cache)
{
if (cache != NULL) {
free(cache->entryAlloc);
free(cache);
}
}
/*
* Update a cache entry.
*
* In the event of a collision with another thread, the update may be skipped.
*
* We only need "pCache" for stats.
*/
void dvmUpdateAtomicCache(u4 key1, u4 key2, u4 value, AtomicCacheEntry* pEntry,
u4 firstVersion
#if CALC_CACHE_STATS > 0
, AtomicCache* pCache
#endif
)
{
/*
* The fields don't match, so we need to update them. There is a
* risk that another thread is also trying to update them, so we
* grab an ownership flag to lock out other threads.
*
* If the lock flag was already set in "firstVersion", somebody else
* was in mid-update. (This means that using "firstVersion" as the
* "before" argument to the CAS would succeed when it shouldn't and
* vice-versa -- we could also just pass in
* (firstVersion & ~ATOMIC_LOCK_FLAG) as the first argument.)
*
* NOTE: we don't really deal with the situation where we overflow
* the version counter (at 2^31). Probably not a real concern.
*/
if ((firstVersion & ATOMIC_LOCK_FLAG) != 0 ||
!ATOMIC_CMP_SWAP((volatile s4*) &pEntry->version,
firstVersion, firstVersion | ATOMIC_LOCK_FLAG))
{
/*
* We couldn't get the write lock. Return without updating the table.
*/
#if CALC_CACHE_STATS > 0
pCache->fail++;
#endif
return;
}
/* must be even-valued on entry */
assert((firstVersion & 0x01) == 0);
#if CALC_CACHE_STATS > 0
/* for stats, assume a key value of zero indicates an empty entry */
if (pEntry->key1 == 0)
pCache->fills++;
else
pCache->misses++;
#endif
/* volatile incr */
pEntry->version++;
MEM_BARRIER();
pEntry->key1 = key1;
pEntry->key2 = key2;
pEntry->value = value;
/* volatile incr */
pEntry->version++;
MEM_BARRIER();
/*
* Clear the lock flag. Nobody else should have been able to modify
* pEntry->version, so if this fails the world is broken.
*/
firstVersion += 2;
if (!ATOMIC_CMP_SWAP((volatile s4*) &pEntry->version,
firstVersion | ATOMIC_LOCK_FLAG, firstVersion))
{
//LOGE("unable to reset the instanceof cache ownership\n");
dvmAbort();
}
}
/*
* Dump the "instanceof" cache stats.
*/
void dvmDumpAtomicCacheStats(const AtomicCache* pCache)
{
if (pCache == NULL)
return;
dvmFprintf(stdout,
"Cache stats: trv=%d fai=%d hit=%d mis=%d fil=%d %d%% (size=%d)\n",
pCache->trivial, pCache->fail, pCache->hits,
pCache->misses, pCache->fills,
(pCache->hits == 0) ? 0 :
pCache->hits * 100 /
(pCache->fail + pCache->hits + pCache->misses + pCache->fills),
pCache->numEntries);
}