vm/AtomicCache.cpp

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