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