/*
* Copyright (C) 2009 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*
* Indirect reference table management.
*/
#include "Dalvik.h"
/*
* Initialize an IndirectRefTable structure.
*/
bool dvmInitIndirectRefTable(IndirectRefTable* pRef, int initialCount,
int maxCount, IndirectRefKind kind)
{
assert(initialCount > 0);
assert(initialCount <= maxCount);
assert(kind == kIndirectKindLocal || kind == kIndirectKindGlobal);
pRef->table = (Object**) malloc(initialCount * sizeof(Object*));
if (pRef->table == NULL)
return false;
#ifndef NDEBUG
memset(pRef->table, 0xd1, initialCount * sizeof(Object*));
#endif
pRef->slotData =
(IndirectRefSlot*) calloc(maxCount, sizeof(IndirectRefSlot));
if (pRef->slotData == NULL)
return false;
pRef->segmentState.all = IRT_FIRST_SEGMENT;
pRef->allocEntries = initialCount;
pRef->maxEntries = maxCount;
pRef->kind = kind;
return true;
}
/*
* Clears out the contents of a IndirectRefTable, freeing allocated storage.
*/
void dvmClearIndirectRefTable(IndirectRefTable* pRef)
{
free(pRef->table);
pRef->table = NULL;
pRef->allocEntries = pRef->maxEntries = -1;
}
/*
* Remove one or more segments from the top. The table entry identified
* by "cookie" becomes the new top-most entry.
*
* Returns false if "cookie" is invalid or the table has only one segment.
*/
bool dvmPopIndirectRefTableSegmentCheck(IndirectRefTable* pRef, u4 cookie)
{
IRTSegmentState sst;
/*
* The new value for "top" must be <= the current value. Otherwise
* this would represent an expansion of the table.
*/
sst.all = cookie;
if (sst.parts.topIndex > pRef->segmentState.parts.topIndex) {
LOGE("Attempt to expand table with segment pop (%d to %d)\n",
pRef->segmentState.parts.topIndex, sst.parts.topIndex);
return false;
}
if (sst.parts.numHoles >= sst.parts.topIndex) {
LOGE("Absurd numHoles in cookie (%d bi=%d)\n",
sst.parts.numHoles, sst.parts.topIndex);
return false;
}
LOGV("IRT %p[%d]: pop, top=%d holes=%d\n",
pRef, pRef->kind, sst.parts.topIndex, sst.parts.numHoles);
return true;
}
/*
* Make sure that the entry at "idx" is correctly paired with "iref".
*/
static bool checkEntry(IndirectRefTable* pRef, IndirectRef iref, int idx)
{
Object* obj = pRef->table[idx];
IndirectRef checkRef = dvmObjectToIndirectRef(pRef, obj, idx, pRef->kind);
if (checkRef != iref) {
LOGW("IRT %p[%d]: iref mismatch (req=%p vs cur=%p)\n",
pRef, pRef->kind, iref, checkRef);
return false;
}
return true;
}
/*
* Update extended debug info when an entry is added.
*
* We advance the serial number, invalidating any outstanding references to
* this slot.
*/
static inline void updateSlotAdd(IndirectRefTable* pRef, Object* obj, int slot)
{
if (pRef->slotData != NULL) {
IndirectRefSlot* pSlot = &pRef->slotData[slot];
pSlot->serial++;
//LOGI("+++ add [%d] slot %d (%p->%p), serial=%d\n",
// pRef->kind, slot, obj, iref, pSlot->serial);
pSlot->previous[pSlot->serial % kIRTPrevCount] = obj;
}
}
/*
* Update extended debug info when an entry is removed.
*/
static inline void updateSlotRemove(IndirectRefTable* pRef, int slot)
{
if (pRef->slotData != NULL) {
//IndirectRefSlot* pSlot = &pRef->slotData[slot];
//LOGI("+++ remove [%d] slot %d, serial now %d\n",
// pRef->kind, slot, pSlot->serial);
}
}
/*
* Add "obj" to "pRef".
*/
IndirectRef dvmAddToIndirectRefTable(IndirectRefTable* pRef, u4 cookie,
Object* obj)
{
IRTSegmentState prevState;
prevState.all = cookie;
int topIndex = pRef->segmentState.parts.topIndex;
assert(obj != NULL);
assert(dvmIsValidObject(obj));
assert(pRef->table != NULL);
assert(pRef->allocEntries <= pRef->maxEntries);
assert(pRef->segmentState.parts.numHoles >= prevState.parts.numHoles);
if (topIndex == pRef->allocEntries) {
/* reached end of allocated space; did we hit buffer max? */
if (topIndex == pRef->maxEntries) {
LOGW("IndirectRefTable overflow (max=%d)\n", pRef->maxEntries);
return NULL;
}
Object** newTable;
int newSize;
newSize = pRef->allocEntries * 2;
if (newSize > pRef->maxEntries)
newSize = pRef->maxEntries;
assert(newSize > pRef->allocEntries);
newTable = (Object**) realloc(pRef->table, newSize * sizeof(Object*));
if (newTable == NULL) {
LOGE("Unable to expand iref table (from %d to %d, max=%d)\n",
pRef->allocEntries, newSize, pRef->maxEntries);
return false;
}
LOGI("Growing ireftab %p from %d to %d (max=%d)\n",
pRef, pRef->allocEntries, newSize, pRef->maxEntries);
/* update entries; adjust "nextEntry" in case memory moved */
pRef->table = newTable;
pRef->allocEntries = newSize;
}
IndirectRef result;
/*
* We know there's enough room in the table. Now we just need to find
* the right spot. If there's a hole, find it and fill it; otherwise,
* add to the end of the list.
*/
int numHoles = pRef->segmentState.parts.numHoles - prevState.parts.numHoles;
if (numHoles > 0) {
assert(topIndex > 1);
/* find the first hole; likely to be near the end of the list */
Object** pScan = &pRef->table[topIndex - 1];
assert(*pScan != NULL);
while (*--pScan != NULL) {
assert(pScan >= pRef->table + prevState.parts.topIndex);
}
updateSlotAdd(pRef, obj, pScan - pRef->table);
result = dvmObjectToIndirectRef(pRef, obj, pScan - pRef->table,
pRef->kind);
*pScan = obj;
pRef->segmentState.parts.numHoles--;
} else {
/* add to the end */
updateSlotAdd(pRef, obj, topIndex);
result = dvmObjectToIndirectRef(pRef, obj, topIndex, pRef->kind);
pRef->table[topIndex++] = obj;
pRef->segmentState.parts.topIndex = topIndex;
}
assert(result != NULL);
return result;
}
/*
* Verify that the indirect table lookup is valid.
*
* Returns "false" if something looks bad.
*/
bool dvmGetFromIndirectRefTableCheck(IndirectRefTable* pRef, IndirectRef iref)
{
if (dvmGetIndirectRefType(iref) == kIndirectKindInvalid) {
LOGW("Invalid indirect reference 0x%08x\n", (u4) iref);
return false;
}
int topIndex = pRef->segmentState.parts.topIndex;
int idx = dvmIndirectRefToIndex(iref);
if (iref == NULL) {
LOGI("--- lookup on NULL iref\n");
return false;
}
if (idx >= topIndex) {
/* bad -- stale reference? */
LOGI("Attempt to access invalid index %d (top=%d)\n",
idx, topIndex);
return false;
}
Object* obj = pRef->table[idx];
if (obj == NULL) {
LOGI("Attempt to read from hole, iref=%p\n", iref);
return false;
}
if (!checkEntry(pRef, iref, idx))
return false;
return true;
}
/*
* Remove "obj" from "pRef". We extract the table offset bits from "iref"
* and zap the corresponding entry, leaving a hole if it's not at the top.
*
* If the entry is not between the current top index and the bottom index
* specified by the cookie, we don't remove anything. This is the behavior
* required by JNI's DeleteLocalRef function.
*
* Note this is NOT called when a local frame is popped. This is only used
* for explict single removals.
*
* Returns "false" if nothing was removed.
*/
bool dvmRemoveFromIndirectRefTable(IndirectRefTable* pRef, u4 cookie,
IndirectRef iref)
{
IRTSegmentState prevState;
prevState.all = cookie;
int topIndex = pRef->segmentState.parts.topIndex;
int bottomIndex = prevState.parts.topIndex;
assert(pRef->table != NULL);
assert(pRef->allocEntries <= pRef->maxEntries);
assert(pRef->segmentState.parts.numHoles >= prevState.parts.numHoles);
int idx = dvmIndirectRefToIndex(iref);
if (idx < bottomIndex) {
/* wrong segment */
LOGV("Attempt to remove index outside index area (%d vs %d-%d)\n",
idx, bottomIndex, topIndex);
return false;
}
if (idx >= topIndex) {
/* bad -- stale reference? */
LOGI("Attempt to remove invalid index %d (bottom=%d top=%d)\n",
idx, bottomIndex, topIndex);
return false;
}
if (idx == topIndex-1) {
/*
* Top-most entry. Scan up and consume holes. No need to NULL
* out the entry, since the test vs. topIndex will catch it.
*/
if (!checkEntry(pRef, iref, idx))
return false;
updateSlotRemove(pRef, idx);
#ifndef NDEBUG
pRef->table[idx] = (IndirectRef) 0xd3d3d3d3;
#endif
int numHoles =
pRef->segmentState.parts.numHoles - prevState.parts.numHoles;
if (numHoles != 0) {
while (--topIndex > bottomIndex && numHoles != 0) {
LOGV("+++ checking for hole at %d (cookie=0x%08x) val=%p\n",
topIndex-1, cookie, pRef->table[topIndex-1]);
if (pRef->table[topIndex-1] != NULL)
break;
LOGV("+++ ate hole at %d\n", topIndex-1);
numHoles--;
}
pRef->segmentState.parts.numHoles =
numHoles + prevState.parts.numHoles;
pRef->segmentState.parts.topIndex = topIndex;
} else {
pRef->segmentState.parts.topIndex = topIndex-1;
LOGV("+++ ate last entry %d\n", topIndex-1);
}
} else {
/*
* Not the top-most entry. This creates a hole. We NULL out the
* entry to prevent somebody from deleting it twice and screwing up
* the hole count.
*/
if (pRef->table[idx] == NULL) {
LOGV("--- WEIRD: removing null entry %d\n", idx);
return false;
}
if (!checkEntry(pRef, iref, idx))
return false;
updateSlotRemove(pRef, idx);
pRef->table[idx] = NULL;
pRef->segmentState.parts.numHoles++;
LOGV("+++ left hole at %d, holes=%d\n",
idx, pRef->segmentState.parts.numHoles);
}
return true;
}
/*
* This is a qsort() callback. We sort Object* by class, allocation size,
* and then by the Object* itself.
*/
static int compareObject(const void* vobj1, const void* vobj2)
{
Object* obj1 = *((Object**) vobj1);
Object* obj2 = *((Object**) vobj2);
/* ensure null references appear at the end */
if (obj1 == NULL) {
if (obj2 == NULL) {
return 0;
} else {
return 1;
}
} else if (obj2 == NULL) {
return -1;
}
if (obj1->clazz != obj2->clazz) {
return (u1*)obj1->clazz - (u1*)obj2->clazz;
} else {
int size1 = dvmObjectSizeInHeap(obj1);
int size2 = dvmObjectSizeInHeap(obj2);
if (size1 != size2) {
return size1 - size2;
} else {
return (u1*)obj1 - (u1*)obj2;
}
}
}
/*
* Log an object with some additional info.
*
* Pass in the number of additional elements that are identical to or
* equivalent to the original.
*/
static void logObject(Object* obj, int size, int identical, int equiv)
{
if (obj == NULL) {
LOGW(" NULL reference (count=%d)\n", equiv);
return;
}
if (identical + equiv != 0) {
LOGW("%5d of %s %dB (%d unique)\n", identical + equiv +1,
obj->clazz->descriptor, size, equiv +1);
} else {
LOGW("%5d of %s %dB\n", identical + equiv +1,
obj->clazz->descriptor, size);
}
}
/*
* Dump the contents of a IndirectRefTable to the log.
*/
void dvmDumpIndirectRefTable(const IndirectRefTable* pRef, const char* descr)
{
const int kLast = 10;
int count = dvmIndirectRefTableEntries(pRef);
Object** refs;
int i;
if (count == 0) {
LOGW("Reference table has no entries\n");
return;
}
assert(count > 0);
/*
* Dump the most recent N entries. If there are holes, we will show
* fewer than N.
*/
LOGW("Last %d entries in %s reference table:\n", kLast, descr);
refs = pRef->table; // use unsorted list
int size;
int start = count - kLast;
if (start < 0)
start = 0;
for (i = start; i < count; i++) {
if (refs[i] == NULL)
continue;
size = dvmObjectSizeInHeap(refs[i]);
Object* ref = refs[i];
if (ref->clazz == gDvm.classJavaLangClass) {
ClassObject* clazz = (ClassObject*) ref;
LOGW("%5d: %p cls=%s '%s' (%d bytes)\n", i, ref,
(refs[i] == NULL) ? "-" : ref->clazz->descriptor,
clazz->descriptor, size);
} else {
LOGW("%5d: %p cls=%s (%d bytes)\n", i, ref,
(refs[i] == NULL) ? "-" : ref->clazz->descriptor, size);
}
}
/*
* Make a copy of the table, and sort it.
*
* The NULL "holes" wind up at the end, so we can strip them off easily.
*/
Object** tableCopy = (Object**)malloc(sizeof(Object*) * count);
memcpy(tableCopy, pRef->table, sizeof(Object*) * count);
qsort(tableCopy, count, sizeof(Object*), compareObject);
refs = tableCopy; // use sorted list
if (false) {
int q;
for (q = 0; q < count; q++)
LOGI("%d %p\n", q, refs[q]);
}
int holes = 0;
while (refs[count-1] == NULL) {
count--;
holes++;
}
/*
* Dump uniquified table summary. While we're at it, generate a
* cumulative total amount of pinned memory based on the unique entries.
*/
LOGW("%s reference table summary (%d entries / %d holes):\n",
descr, count, holes);
int equiv, identical, total;
total = equiv = identical = 0;
for (i = 1; i < count; i++) {
size = dvmObjectSizeInHeap(refs[i-1]);
if (refs[i] == refs[i-1]) {
/* same reference, added more than once */
identical++;
} else if (refs[i]->clazz == refs[i-1]->clazz &&
(int) dvmObjectSizeInHeap(refs[i]) == size)
{
/* same class / size, different object */
total += size;
equiv++;
} else {
/* different class */
total += size;
logObject(refs[i-1], size, identical, equiv);
equiv = identical = 0;
}
}
/* handle the last entry (everything above outputs refs[i-1]) */
size = (refs[count-1] == NULL) ? 0 : dvmObjectSizeInHeap(refs[count-1]);
total += size;
logObject(refs[count-1], size, identical, equiv);
LOGW("Memory held directly by native code is %d bytes\n", total);
free(tableCopy);
}