vm/AtomicCache.c

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