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