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 const int kLargeHeapRefTableNElems = 1024;
24static const int  kFinalizableRefDefault = 128;
25
26void dvmHeapHeapTableFree(void *ptr)
27{
28    free(ptr);
29}
30
31#define heapRefTableIsFull(refs) \
32    dvmIsReferenceTableFull(refs)
33
34bool dvmHeapInitHeapRefTable(HeapRefTable *refs)
35{
36    memset(refs, 0, sizeof(*refs));
37    return dvmInitReferenceTable(refs, kFinalizableRefDefault, INT_MAX);
38}
39
40/* Frees the array inside the HeapRefTable, not the HeapRefTable itself.
41 */
42void dvmHeapFreeHeapRefTable(HeapRefTable *refs)
43{
44    dvmClearReferenceTable(refs);
45}
46
47/*
48 * Large, non-contiguous reference tables
49 */
50
51bool dvmHeapAddRefToLargeTable(LargeHeapRefTable **tableP, Object *ref)
52{
53    LargeHeapRefTable *table;
54
55    assert(tableP != NULL);
56    assert(ref != NULL);
57
58    /* Make sure that a table with a free slot is
59     * at the head of the list.
60     */
61    if (*tableP != NULL) {
62        table = *tableP;
63        LargeHeapRefTable *prevTable;
64
65        /* Find an empty slot for this reference.
66         */
67        prevTable = NULL;
68        while (table != NULL && heapRefTableIsFull(&table->refs)) {
69            prevTable = table;
70            table = table->next;
71        }
72        if (table != NULL) {
73            if (prevTable != NULL) {
74                /* Move the table to the head of the list.
75                 */
76                prevTable->next = table->next;
77                table->next = *tableP;
78                *tableP = table;
79            }
80            /* else it's already at the head. */
81
82            goto insert;
83        }
84        /* else all tables are already full;
85         * fall through to the alloc case.
86         */
87    }
88
89    /* Allocate a new table.
90     */
91    table = calloc(1, sizeof(LargeHeapRefTable));
92    if (table == NULL) {
93        LOGE_HEAP("Can't allocate a new large ref table\n");
94        return false;
95    }
96    if (!dvmInitReferenceTable(&table->refs,
97                               kLargeHeapRefTableNElems,
98                               INT_MAX)) {
99        LOGE_HEAP("Can't initialize a new large ref table\n");
100        dvmHeapHeapTableFree(table);
101        return false;
102    }
103
104    /* Stick it at the head.
105     */
106    table->next = *tableP;
107    *tableP = table;
108
109insert:
110    /* Insert the reference.
111     */
112    assert(table == *tableP);
113    assert(table != NULL);
114    assert(!heapRefTableIsFull(&table->refs));
115    *table->refs.nextEntry++ = ref;
116
117    return true;
118}
119
120bool dvmHeapAddTableToLargeTable(LargeHeapRefTable **tableP, HeapRefTable *refs)
121{
122    LargeHeapRefTable *table;
123
124    /* Allocate a node.
125     */
126    table = calloc(1, sizeof(LargeHeapRefTable));
127    if (table == NULL) {
128        LOGE_HEAP("Can't allocate a new large ref table\n");
129        return false;
130    }
131    table->refs = *refs;
132
133    /* Insert the table into the list.
134     */
135    table->next = *tableP;
136    *tableP = table;
137
138    return true;
139}
140
141/* Frees everything associated with the LargeHeapRefTable.
142 */
143void dvmHeapFreeLargeTable(LargeHeapRefTable *table)
144{
145    while (table != NULL) {
146        LargeHeapRefTable *next = table->next;
147        dvmHeapFreeHeapRefTable(&table->refs);
148        dvmHeapHeapTableFree(table);
149        table = next;
150    }
151}
152
153Object *dvmHeapGetNextObjectFromLargeTable(LargeHeapRefTable **pTable)
154{
155    LargeHeapRefTable *table;
156    Object *obj;
157
158    assert(pTable != NULL);
159
160    obj = NULL;
161    table = *pTable;
162    if (table != NULL) {
163        HeapRefTable *refs = &table->refs;
164
165        /* We should never have an empty table node in the list.
166         */
167        assert(dvmReferenceTableEntries(refs) != 0);
168
169        /* Remove and return the last entry in the list.
170         */
171        obj = *--refs->nextEntry;
172
173        /* If this was the last entry in the table node,
174         * free it and patch up the list.
175         */
176        if (refs->nextEntry == refs->table) {
177            *pTable = table->next;
178            dvmClearReferenceTable(refs);
179            dvmHeapHeapTableFree(table);
180        }
181    }
182
183    return obj;
184}
185
186void dvmHeapMarkLargeTableRefs(LargeHeapRefTable *table)
187{
188    while (table != NULL) {
189        Object **ref, **lastRef;
190
191        ref = table->refs.table;
192        lastRef = table->refs.nextEntry;
193        while (ref < lastRef) {
194            dvmMarkObjectNonNull(*ref++);
195        }
196        table = table->next;
197    }
198}
199