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 * String interning.
18 */
19#include "Dalvik.h"
20
21#include <stdlib.h>
22
23#define INTERN_STRING_IMMORTAL_BIT (1<<0)
24#define SET_IMMORTAL_BIT(strObj) \
25            ((uintptr_t)(strObj) | INTERN_STRING_IMMORTAL_BIT)
26#define STRIP_IMMORTAL_BIT(strObj) \
27            ((uintptr_t)(strObj) & ~INTERN_STRING_IMMORTAL_BIT)
28#define IS_IMMORTAL(strObj) \
29            ((uintptr_t)(strObj) & INTERN_STRING_IMMORTAL_BIT)
30
31
32/*
33 * Prep string interning.
34 */
35bool dvmStringInternStartup(void)
36{
37    gDvm.internedStrings = dvmHashTableCreate(256, NULL);
38    if (gDvm.internedStrings == NULL)
39        return false;
40
41    return true;
42}
43
44/*
45 * Chuck the intern list.
46 *
47 * The contents of the list are StringObjects that live on the GC heap.
48 */
49void dvmStringInternShutdown(void)
50{
51    dvmHashTableFree(gDvm.internedStrings);
52    gDvm.internedStrings = NULL;
53}
54
55
56/*
57 * Compare two string objects that may have INTERN_STRING_IMMORTAL_BIT
58 * set in their pointer values.
59 */
60static int hashcmpImmortalStrings(const void* vstrObj1, const void* vstrObj2)
61{
62    return dvmHashcmpStrings((const void*) STRIP_IMMORTAL_BIT(vstrObj1),
63                             (const void*) STRIP_IMMORTAL_BIT(vstrObj2));
64}
65
66static StringObject* lookupInternedString(StringObject* strObj, bool immortal)
67{
68    StringObject* found;
69    u4 hash;
70
71    assert(strObj != NULL);
72    hash = dvmComputeStringHash(strObj);
73
74    if (false) {
75        char* debugStr = dvmCreateCstrFromString(strObj);
76        LOGV("+++ dvmLookupInternedString searching for '%s'\n", debugStr);
77        free(debugStr);
78    }
79
80    if (immortal) {
81        strObj = (StringObject*) SET_IMMORTAL_BIT(strObj);
82    }
83
84    dvmHashTableLock(gDvm.internedStrings);
85
86    found = (StringObject*) dvmHashTableLookup(gDvm.internedStrings,
87                                hash, strObj, hashcmpImmortalStrings, true);
88    if (immortal && !IS_IMMORTAL(found)) {
89        /* Make this entry immortal.  We have to use the existing object
90         * because, as an interned string, it's not allowed to change.
91         *
92         * There's no way to get a pointer to the actual hash table entry,
93         * so the only way to modify the existing entry is to remove,
94         * modify, and re-add it.
95         */
96        dvmHashTableRemove(gDvm.internedStrings, hash, found);
97        found = (StringObject*) SET_IMMORTAL_BIT(found);
98        found = (StringObject*) dvmHashTableLookup(gDvm.internedStrings,
99                                    hash, found, hashcmpImmortalStrings, true);
100        assert(IS_IMMORTAL(found));
101    }
102
103    dvmHashTableUnlock(gDvm.internedStrings);
104
105    //if (found == strObj)
106    //    LOGVV("+++  added string\n");
107    return (StringObject*) STRIP_IMMORTAL_BIT(found);
108}
109
110/*
111 * Find an entry in the interned string list.
112 *
113 * If the string doesn't already exist, the StringObject is added to
114 * the list.  Otherwise, the existing entry is returned.
115 */
116StringObject* dvmLookupInternedString(StringObject* strObj)
117{
118    return lookupInternedString(strObj, false);
119}
120
121/*
122 * Same as dvmLookupInternedString(), but guarantees that the
123 * returned string is immortal.
124 */
125StringObject* dvmLookupImmortalInternedString(StringObject* strObj)
126{
127    return lookupInternedString(strObj, true);
128}
129
130/*
131 * Mark all immortal interned string objects so that they don't
132 * get collected by the GC.  Non-immortal strings may or may not
133 * get marked by other references.
134 */
135static int markStringObject(void* strObj, void* arg)
136{
137    UNUSED_PARAMETER(arg);
138
139    if (IS_IMMORTAL(strObj)) {
140        dvmMarkObjectNonNull((Object*) STRIP_IMMORTAL_BIT(strObj));
141    }
142    return 0;
143}
144
145void dvmGcScanInternedStrings()
146{
147    /* It's possible for a GC to happen before dvmStringInternStartup()
148     * is called.
149     */
150    if (gDvm.internedStrings != NULL) {
151        dvmHashTableLock(gDvm.internedStrings);
152        dvmHashForeach(gDvm.internedStrings, markStringObject, NULL);
153        dvmHashTableUnlock(gDvm.internedStrings);
154    }
155}
156
157/*
158 * Called by the GC after all reachable objects have been
159 * marked.  isUnmarkedObject is a function suitable for passing
160 * to dvmHashForeachRemove();  it must strip the low bits from
161 * its pointer argument to deal with the immortal bit, though.
162 */
163void dvmGcDetachDeadInternedStrings(int (*isUnmarkedObject)(void *))
164{
165    /* It's possible for a GC to happen before dvmStringInternStartup()
166     * is called.
167     */
168    if (gDvm.internedStrings != NULL) {
169        dvmHashTableLock(gDvm.internedStrings);
170        dvmHashForeachRemove(gDvm.internedStrings, isUnmarkedObject);
171        dvmHashTableUnlock(gDvm.internedStrings);
172    }
173}
174