1 /*
2 * Copyright (C) 2009 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 * Indirect reference table management.
19 */
20 #include "Dalvik.h"
21
abortMaybe()22 static void abortMaybe() {
23 // If CheckJNI is on, it'll give a more detailed error before aborting.
24 // Otherwise, we want to abort rather than hand back a bad reference.
25 if (!gDvmJni.useCheckJni) {
26 dvmAbort();
27 }
28 }
29
init(size_t initialCount,size_t maxCount,IndirectRefKind desiredKind)30 bool IndirectRefTable::init(size_t initialCount,
31 size_t maxCount, IndirectRefKind desiredKind)
32 {
33 assert(initialCount > 0);
34 assert(initialCount <= maxCount);
35 assert(desiredKind != kIndirectKindInvalid);
36
37 table_ = (Object**) malloc(initialCount * sizeof(Object*));
38 if (table_ == NULL) {
39 return false;
40 }
41 #ifndef NDEBUG
42 memset(table_, 0xd1, initialCount * sizeof(Object*));
43 #endif
44
45 slot_data_ = (IndirectRefSlot*) calloc(initialCount, sizeof(IndirectRefSlot));
46 if (slot_data_ == NULL) {
47 return false;
48 }
49
50 segmentState.all = IRT_FIRST_SEGMENT;
51 alloc_entries_ = initialCount;
52 max_entries_ = maxCount;
53 kind_ = desiredKind;
54
55 return true;
56 }
57
58 /*
59 * Clears out the contents of a IndirectRefTable, freeing allocated storage.
60 */
destroy()61 void IndirectRefTable::destroy()
62 {
63 free(table_);
64 free(slot_data_);
65 table_ = NULL;
66 slot_data_ = NULL;
67 alloc_entries_ = max_entries_ = -1;
68 }
69
70 /*
71 * Make sure that the entry at "idx" is correctly paired with "iref".
72 */
checkEntry(const char * what,IndirectRef iref,int idx) const73 bool IndirectRefTable::checkEntry(const char* what, IndirectRef iref, int idx) const
74 {
75 Object* obj = table_[idx];
76 IndirectRef checkRef = toIndirectRef(obj, idx);
77 if (checkRef != iref) {
78 LOGE("JNI ERROR (app bug): attempt to %s stale %s reference %p (should be %p)",
79 what, indirectRefKindToString(kind_), iref, checkRef);
80 abortMaybe();
81 return false;
82 }
83 return true;
84 }
85
add(u4 cookie,Object * obj)86 IndirectRef IndirectRefTable::add(u4 cookie, Object* obj)
87 {
88 IRTSegmentState prevState;
89 prevState.all = cookie;
90 size_t topIndex = segmentState.parts.topIndex;
91
92 assert(obj != NULL);
93 assert(dvmIsHeapAddress(obj));
94 assert(table_ != NULL);
95 assert(alloc_entries_ <= max_entries_);
96 assert(segmentState.parts.numHoles >= prevState.parts.numHoles);
97
98 if (topIndex == alloc_entries_) {
99 /* reached end of allocated space; did we hit buffer max? */
100 if (topIndex == max_entries_) {
101 LOGE("JNI ERROR (app bug): %s reference table overflow (max=%d)",
102 indirectRefKindToString(kind_), max_entries_);
103 dump(indirectRefKindToString(kind_));
104 dvmAbort();
105 }
106
107 size_t newSize = alloc_entries_ * 2;
108 if (newSize > max_entries_) {
109 newSize = max_entries_;
110 }
111 assert(newSize > alloc_entries_);
112
113 table_ = (Object**) realloc(table_, newSize * sizeof(Object*));
114 slot_data_ = (IndirectRefSlot*) realloc(slot_data_, newSize * sizeof(IndirectRefSlot));
115 if (table_ == NULL || slot_data_ == NULL) {
116 LOGE("JNI ERROR (app bug): unable to expand %s reference table (from %d to %d, max=%d)",
117 indirectRefKindToString(kind_),
118 alloc_entries_, newSize, max_entries_);
119 dump(indirectRefKindToString(kind_));
120 dvmAbort();
121 }
122
123 // Clear the newly-allocated slot_data_ elements.
124 memset(slot_data_ + alloc_entries_, 0, (newSize - alloc_entries_) * sizeof(IndirectRefSlot));
125
126 alloc_entries_ = newSize;
127 }
128
129 /*
130 * We know there's enough room in the table. Now we just need to find
131 * the right spot. If there's a hole, find it and fill it; otherwise,
132 * add to the end of the list.
133 */
134 IndirectRef result;
135 int numHoles = segmentState.parts.numHoles - prevState.parts.numHoles;
136 if (numHoles > 0) {
137 assert(topIndex > 1);
138 /* find the first hole; likely to be near the end of the list */
139 Object** pScan = &table_[topIndex - 1];
140 assert(*pScan != NULL);
141 while (*--pScan != NULL) {
142 assert(pScan >= table_ + prevState.parts.topIndex);
143 }
144 updateSlotAdd(obj, pScan - table_);
145 result = toIndirectRef(obj, pScan - table_);
146 *pScan = obj;
147 segmentState.parts.numHoles--;
148 } else {
149 /* add to the end */
150 updateSlotAdd(obj, topIndex);
151 result = toIndirectRef(obj, topIndex);
152 table_[topIndex++] = obj;
153 segmentState.parts.topIndex = topIndex;
154 }
155
156 assert(result != NULL);
157 return result;
158 }
159
160 /*
161 * Verify that the indirect table lookup is valid.
162 *
163 * Returns "false" if something looks bad.
164 */
getChecked(IndirectRef iref) const165 bool IndirectRefTable::getChecked(IndirectRef iref) const
166 {
167 if (iref == NULL) {
168 LOGW("Attempt to look up NULL %s reference", indirectRefKindToString(kind_));
169 return false;
170 }
171 if (indirectRefKind(iref) == kIndirectKindInvalid) {
172 LOGE("JNI ERROR (app bug): invalid %s reference %p",
173 indirectRefKindToString(kind_), iref);
174 abortMaybe();
175 return false;
176 }
177
178 int topIndex = segmentState.parts.topIndex;
179 int idx = extractIndex(iref);
180 if (idx >= topIndex) {
181 /* bad -- stale reference? */
182 LOGE("JNI ERROR (app bug): accessed stale %s reference %p (index %d in a table of size %d)",
183 indirectRefKindToString(kind_), iref, idx, topIndex);
184 abortMaybe();
185 return false;
186 }
187
188 if (table_[idx] == NULL) {
189 LOGI("JNI ERROR (app bug): accessed deleted %s reference %p",
190 indirectRefKindToString(kind_), iref);
191 abortMaybe();
192 return false;
193 }
194
195 if (!checkEntry("use", iref, idx)) {
196 return false;
197 }
198
199 return true;
200 }
201
linearScan(IndirectRef iref,int bottomIndex,int topIndex,Object ** table)202 static int linearScan(IndirectRef iref, int bottomIndex, int topIndex, Object** table) {
203 for (int i = bottomIndex; i < topIndex; ++i) {
204 if (table[i] == reinterpret_cast<Object*>(iref)) {
205 return i;
206 }
207 }
208 return -1;
209 }
210
contains(IndirectRef iref) const211 bool IndirectRefTable::contains(IndirectRef iref) const {
212 return linearScan(iref, 0, segmentState.parts.topIndex, table_) != -1;
213 }
214
215 /*
216 * Remove "obj" from "pRef". We extract the table offset bits from "iref"
217 * and zap the corresponding entry, leaving a hole if it's not at the top.
218 *
219 * If the entry is not between the current top index and the bottom index
220 * specified by the cookie, we don't remove anything. This is the behavior
221 * required by JNI's DeleteLocalRef function.
222 *
223 * Note this is NOT called when a local frame is popped. This is only used
224 * for explicit single removals.
225 *
226 * Returns "false" if nothing was removed.
227 */
remove(u4 cookie,IndirectRef iref)228 bool IndirectRefTable::remove(u4 cookie, IndirectRef iref)
229 {
230 IRTSegmentState prevState;
231 prevState.all = cookie;
232 int topIndex = segmentState.parts.topIndex;
233 int bottomIndex = prevState.parts.topIndex;
234
235 assert(table_ != NULL);
236 assert(alloc_entries_ <= max_entries_);
237 assert(segmentState.parts.numHoles >= prevState.parts.numHoles);
238
239 int idx = extractIndex(iref);
240 bool workAroundAppJniBugs = false;
241
242 if (indirectRefKind(iref) == kIndirectKindInvalid && gDvmJni.workAroundAppJniBugs) {
243 idx = linearScan(iref, bottomIndex, topIndex, table_);
244 workAroundAppJniBugs = true;
245 if (idx == -1) {
246 LOGW("trying to work around app JNI bugs, but didn't find %p in table!", iref);
247 return false;
248 }
249 }
250
251 if (idx < bottomIndex) {
252 /* wrong segment */
253 LOGV("Attempt to remove index outside index area (%d vs %d-%d)",
254 idx, bottomIndex, topIndex);
255 return false;
256 }
257 if (idx >= topIndex) {
258 /* bad -- stale reference? */
259 LOGD("Attempt to remove invalid index %d (bottom=%d top=%d)",
260 idx, bottomIndex, topIndex);
261 return false;
262 }
263
264 if (idx == topIndex-1) {
265 // Top-most entry. Scan up and consume holes.
266
267 if (workAroundAppJniBugs == false && !checkEntry("remove", iref, idx)) {
268 return false;
269 }
270
271 table_[idx] = NULL;
272 int numHoles = segmentState.parts.numHoles - prevState.parts.numHoles;
273 if (numHoles != 0) {
274 while (--topIndex > bottomIndex && numHoles != 0) {
275 LOGV("+++ checking for hole at %d (cookie=0x%08x) val=%p",
276 topIndex-1, cookie, table_[topIndex-1]);
277 if (table_[topIndex-1] != NULL) {
278 break;
279 }
280 LOGV("+++ ate hole at %d", topIndex-1);
281 numHoles--;
282 }
283 segmentState.parts.numHoles = numHoles + prevState.parts.numHoles;
284 segmentState.parts.topIndex = topIndex;
285 } else {
286 segmentState.parts.topIndex = topIndex-1;
287 LOGV("+++ ate last entry %d", topIndex-1);
288 }
289 } else {
290 /*
291 * Not the top-most entry. This creates a hole. We NULL out the
292 * entry to prevent somebody from deleting it twice and screwing up
293 * the hole count.
294 */
295 if (table_[idx] == NULL) {
296 LOGV("--- WEIRD: removing null entry %d", idx);
297 return false;
298 }
299 if (workAroundAppJniBugs == false && !checkEntry("remove", iref, idx)) {
300 return false;
301 }
302
303 table_[idx] = NULL;
304 segmentState.parts.numHoles++;
305 LOGV("+++ left hole at %d, holes=%d", idx, segmentState.parts.numHoles);
306 }
307
308 return true;
309 }
310
indirectRefKindToString(IndirectRefKind kind)311 const char* indirectRefKindToString(IndirectRefKind kind)
312 {
313 switch (kind) {
314 case kIndirectKindInvalid: return "invalid";
315 case kIndirectKindLocal: return "local";
316 case kIndirectKindGlobal: return "global";
317 case kIndirectKindWeakGlobal: return "weak global";
318 default: return "UNKNOWN";
319 }
320 }
321
dump(const char * descr) const322 void IndirectRefTable::dump(const char* descr) const
323 {
324 dvmDumpReferenceTableContents(table_, capacity(), descr);
325 }
326