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 <stddef.h>
22
23 /*
24 * Prep string interning.
25 */
dvmStringInternStartup(void)26 bool dvmStringInternStartup(void)
27 {
28 dvmInitMutex(&gDvm.internLock);
29 gDvm.internedStrings = dvmHashTableCreate(256, NULL);
30 if (gDvm.internedStrings == NULL)
31 return false;
32 gDvm.literalStrings = dvmHashTableCreate(256, NULL);
33 if (gDvm.literalStrings == NULL)
34 return false;
35 return true;
36 }
37
38 /*
39 * Chuck the intern list.
40 *
41 * The contents of the list are StringObjects that live on the GC heap.
42 */
dvmStringInternShutdown(void)43 void dvmStringInternShutdown(void)
44 {
45 if (gDvm.internedStrings != NULL || gDvm.literalStrings != NULL) {
46 dvmDestroyMutex(&gDvm.internLock);
47 }
48 dvmHashTableFree(gDvm.internedStrings);
49 gDvm.internedStrings = NULL;
50 dvmHashTableFree(gDvm.literalStrings);
51 gDvm.literalStrings = NULL;
52 }
53
lookupInternedString(StringObject * strObj,bool isLiteral)54 static StringObject* lookupInternedString(StringObject* strObj, bool isLiteral)
55 {
56 StringObject* found;
57 u4 hash;
58
59 assert(strObj != NULL);
60 hash = dvmComputeStringHash(strObj);
61 dvmLockMutex(&gDvm.internLock);
62 if (isLiteral) {
63 /*
64 * Check the literal table for a match.
65 */
66 StringObject* literal = dvmHashTableLookup(gDvm.literalStrings,
67 hash, strObj,
68 dvmHashcmpStrings,
69 false);
70 if (literal != NULL) {
71 /*
72 * A match was found in the literal table, the easy case.
73 */
74 found = literal;
75 } else {
76 /*
77 * There is no match in the literal table, check the
78 * interned string table.
79 */
80 StringObject* interned = dvmHashTableLookup(gDvm.internedStrings,
81 hash, strObj,
82 dvmHashcmpStrings,
83 false);
84 if (interned != NULL) {
85 /*
86 * A match was found in the interned table. Move the
87 * matching string to the literal table.
88 */
89 dvmHashTableRemove(gDvm.internedStrings, hash, interned);
90 found = dvmHashTableLookup(gDvm.literalStrings,
91 hash, interned,
92 dvmHashcmpStrings,
93 true);
94 assert(found == interned);
95 } else {
96 /*
97 * No match in the literal table or the interned
98 * table. Insert into the literal table.
99 */
100 found = dvmHashTableLookup(gDvm.literalStrings,
101 hash, strObj,
102 dvmHashcmpStrings,
103 true);
104 assert(found == strObj);
105 }
106 }
107 } else {
108 /*
109 * Check the literal table for a match.
110 */
111 found = dvmHashTableLookup(gDvm.literalStrings,
112 hash, strObj,
113 dvmHashcmpStrings,
114 false);
115 if (found == NULL) {
116 /*
117 * No match was found in the literal table. Insert into
118 * the intern table.
119 */
120 found = dvmHashTableLookup(gDvm.internedStrings,
121 hash, strObj,
122 dvmHashcmpStrings,
123 true);
124 }
125 }
126 assert(found != NULL);
127 dvmUnlockMutex(&gDvm.internLock);
128 return found;
129 }
130
131 /*
132 * Find an entry in the interned string table.
133 *
134 * If the string doesn't already exist, the StringObject is added to
135 * the table. Otherwise, the existing entry is returned.
136 */
dvmLookupInternedString(StringObject * strObj)137 StringObject* dvmLookupInternedString(StringObject* strObj)
138 {
139 return lookupInternedString(strObj, false);
140 }
141
142 /*
143 * Same as dvmLookupInternedString(), but guarantees that the
144 * returned string is a literal.
145 */
dvmLookupImmortalInternedString(StringObject * strObj)146 StringObject* dvmLookupImmortalInternedString(StringObject* strObj)
147 {
148 return lookupInternedString(strObj, true);
149 }
150
151 /*
152 * Returns true if the object is a weak interned string. Any string
153 * interned by the user is weak.
154 */
dvmIsWeakInternedString(const StringObject * strObj)155 bool dvmIsWeakInternedString(const StringObject* strObj)
156 {
157 StringObject* found;
158 u4 hash;
159
160 assert(strObj != NULL);
161 if (gDvm.internedStrings == NULL) {
162 return false;
163 }
164 dvmLockMutex(&gDvm.internLock);
165 hash = dvmComputeStringHash(strObj);
166 found = dvmHashTableLookup(gDvm.internedStrings, hash, (void*)strObj,
167 dvmHashcmpStrings, false);
168 dvmUnlockMutex(&gDvm.internLock);
169 return found == strObj;
170 }
171
markStringObject(void * strObj,void * arg)172 static int markStringObject(void* strObj, void* arg)
173 {
174 UNUSED_PARAMETER(arg);
175 dvmMarkObjectNonNull(strObj);
176 return 0;
177 }
178
179 /*
180 * Blacken string references from the literal string table. The
181 * literal table is a root.
182 */
dvmGcScanInternedStrings()183 void dvmGcScanInternedStrings()
184 {
185 /* It's possible for a GC to happen before dvmStringInternStartup()
186 * is called.
187 */
188 if (gDvm.literalStrings != NULL) {
189 dvmHashForeach(gDvm.literalStrings, markStringObject, NULL);
190 }
191 }
192
193 /*
194 * Clear white references from the intern table.
195 */
dvmGcDetachDeadInternedStrings(int (* isUnmarkedObject)(void *))196 void dvmGcDetachDeadInternedStrings(int (*isUnmarkedObject)(void *))
197 {
198 /* It's possible for a GC to happen before dvmStringInternStartup()
199 * is called.
200 */
201 if (gDvm.internedStrings != NULL) {
202 dvmLockMutex(&gDvm.internLock);
203 dvmHashForeachRemove(gDvm.internedStrings, isUnmarkedObject);
204 dvmUnlockMutex(&gDvm.internLock);
205 }
206 }
207