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