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 */
dvmStringInternStartup(void)35 bool 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 */
dvmStringInternShutdown(void)49 void 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 */
hashcmpImmortalStrings(const void * vstrObj1,const void * vstrObj2)60 static 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
lookupInternedString(StringObject * strObj,bool immortal)66 static 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 */
dvmLookupInternedString(StringObject * strObj)116 StringObject* 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 */
dvmLookupImmortalInternedString(StringObject * strObj)125 StringObject* 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 */
markStringObject(void * strObj,void * arg)135 static 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
dvmGcScanInternedStrings()145 void 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 */
dvmGcDetachDeadInternedStrings(int (* isUnmarkedObject)(void *))163 void 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