vm/IndirectRefTable.c - platform/dalvik - Gitiles

 /*
  * 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 != kIndirectKindInvalid);

     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);
     free(pRef->slotData);
     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] = (Object*)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;
 }

 /*
  * Dump the contents of a IndirectRefTable to the log.
  */
 void dvmDumpIndirectRefTable(const IndirectRefTable* pRef, const char* descr)
 {
     dvmDumpReferenceTableContents(pRef->table, dvmIndirectRefTableEntries(pRef),
         descr);
 }
	/*
	* 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 != kIndirectKindInvalid);

	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);
	free(pRef->slotData);
	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] = (Object*)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;
	}

	/*
	* Dump the contents of a IndirectRefTable to the log.
	*/
	void dvmDumpIndirectRefTable(const IndirectRefTable* pRef, const char* descr)
	{
	dvmDumpReferenceTableContents(pRef->table, dvmIndirectRefTableEntries(pRef),
	descr);
	}