AtomicCache.cpp revision f61171f4800799fa604850e39e6ae88368fe1ee4 
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 */
40AtomicCache* 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 */
72void 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 */
88void 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 */
170void 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