Home | History | Annotate | Download | only in vm 
      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 }
    183