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#include "Dalvik.h" 18#include "alloc/HeapTable.h" 19#include "alloc/HeapInternal.h" 20 21#include <limits.h> // for INT_MAX 22 23static void *heapTableRealloc(void *oldPtr, size_t newSize) 24{ 25 /* Don't just call realloc(), in case the native system 26 * doesn't malloc() on realloc(NULL). 27 */ 28 if (oldPtr != NULL) { 29 return realloc(oldPtr, newSize); 30 } else { 31 return malloc(newSize); 32 } 33} 34 35void dvmHeapHeapTableFree(void *ptr) 36{ 37 free(ptr); 38} 39 40#define heapRefTableIsFull(refs) \ 41 ({ \ 42 const HeapRefTable *HRTIF_refs = (refs); \ 43 dvmIsReferenceTableFull(refs); \ 44 }) 45 46bool dvmHeapInitHeapRefTable(HeapRefTable *refs, size_t nelems) 47{ 48 memset(refs, 0, sizeof(*refs)); 49 return dvmInitReferenceTable(refs, nelems, INT_MAX); 50} 51 52/* Frees the array inside the HeapRefTable, not the HeapRefTable itself. 53 */ 54void dvmHeapFreeHeapRefTable(HeapRefTable *refs) 55{ 56 dvmClearReferenceTable(refs); 57} 58 59/* 60 * Large, non-contiguous reference tables 61 */ 62 63#define kLargeHeapRefTableNElems 1024 64bool dvmHeapAddRefToLargeTable(LargeHeapRefTable **tableP, Object *ref) 65{ 66 LargeHeapRefTable *table; 67 68 assert(tableP != NULL); 69 assert(ref != NULL); 70 71 /* Make sure that a table with a free slot is 72 * at the head of the list. 73 */ 74 if (*tableP != NULL) { 75 table = *tableP; 76 LargeHeapRefTable *prevTable; 77 78 /* Find an empty slot for this reference. 79 */ 80 prevTable = NULL; 81 while (table != NULL && heapRefTableIsFull(&table->refs)) { 82 prevTable = table; 83 table = table->next; 84 } 85 if (table != NULL) { 86 if (prevTable != NULL) { 87 /* Move the table to the head of the list. 88 */ 89 prevTable->next = table->next; 90 table->next = *tableP; 91 *tableP = table; 92 } 93 /* else it's already at the head. */ 94 95 goto insert; 96 } 97 /* else all tables are already full; 98 * fall through to the alloc case. 99 */ 100 } 101 102 /* Allocate a new table. 103 */ 104 table = (LargeHeapRefTable *)heapTableRealloc(NULL, 105 sizeof(LargeHeapRefTable)); 106 if (table == NULL) { 107 LOGE_HEAP("Can't allocate a new large ref table\n"); 108 return false; 109 } 110 if (!dvmHeapInitHeapRefTable(&table->refs, kLargeHeapRefTableNElems)) { 111 LOGE_HEAP("Can't initialize a new large ref table\n"); 112 dvmHeapHeapTableFree(table); 113 return false; 114 } 115 116 /* Stick it at the head. 117 */ 118 table->next = *tableP; 119 *tableP = table; 120 121insert: 122 /* Insert the reference. 123 */ 124 assert(table == *tableP); 125 assert(table != NULL); 126 assert(!heapRefTableIsFull(&table->refs)); 127 *table->refs.nextEntry++ = ref; 128 129 return true; 130} 131 132bool dvmHeapAddTableToLargeTable(LargeHeapRefTable **tableP, HeapRefTable *refs) 133{ 134 LargeHeapRefTable *table; 135 136 /* Allocate a node. 137 */ 138 table = (LargeHeapRefTable *)heapTableRealloc(NULL, 139 sizeof(LargeHeapRefTable)); 140 if (table == NULL) { 141 LOGE_HEAP("Can't allocate a new large ref table\n"); 142 return false; 143 } 144 table->refs = *refs; 145 146 /* Insert the table into the list. 147 */ 148 table->next = *tableP; 149 *tableP = table; 150 151 return true; 152} 153 154/* Frees everything associated with the LargeHeapRefTable. 155 */ 156void dvmHeapFreeLargeTable(LargeHeapRefTable *table) 157{ 158 while (table != NULL) { 159 LargeHeapRefTable *next = table->next; 160 dvmHeapFreeHeapRefTable(&table->refs); 161 dvmHeapHeapTableFree(table); 162 table = next; 163 } 164} 165 166Object *dvmHeapGetNextObjectFromLargeTable(LargeHeapRefTable **pTable) 167{ 168 LargeHeapRefTable *table; 169 Object *obj; 170 171 assert(pTable != NULL); 172 173 obj = NULL; 174 table = *pTable; 175 if (table != NULL) { 176 GcHeap *gcHeap = gDvm.gcHeap; 177 HeapRefTable *refs = &table->refs; 178 179 /* We should never have an empty table node in the list. 180 */ 181 assert(dvmReferenceTableEntries(refs) != 0); 182 183 /* Remove and return the last entry in the list. 184 */ 185 obj = *--refs->nextEntry; 186 187 /* If this was the last entry in the table node, 188 * free it and patch up the list. 189 */ 190 if (refs->nextEntry == refs->table) { 191 *pTable = table->next; 192 dvmClearReferenceTable(refs); 193 dvmHeapHeapTableFree(table); 194 } 195 } 196 197 return obj; 198} 199 200void dvmHeapMarkLargeTableRefs(LargeHeapRefTable *table, bool stripLowBits) 201{ 202 while (table != NULL) { 203 Object **ref, **lastRef; 204 205 ref = table->refs.table; 206 lastRef = table->refs.nextEntry; 207 if (stripLowBits) { 208 /* This case is used for marking reference objects that 209 * are still waiting for the heap worker thread to get to 210 * them. The referents pointed to by the references are 211 * marked when a SCHEDULED_REFERENCE_MAGIC is encountered 212 * during scanning. 213 */ 214 while (ref < lastRef) { 215 dvmMarkObjectNonNull((Object *)((uintptr_t)*ref++ & ~3)); 216 } 217 } else { 218 while (ref < lastRef) { 219 dvmMarkObjectNonNull(*ref++); 220 } 221 } 222 table = table->next; 223 } 224} 225 226 227