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  * 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 
    174