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        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 */
70void 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 */
86void 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        //ALOGE("unable to reset the instanceof cache ownership");
160        dvmAbort();
161    }
162}
163
164
165/*
166 * Dump the "instanceof" cache stats.
167 */
168void 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