vm/Intern.c

   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  */
  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  */
  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  */
  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
  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  */
 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  */
 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  */
 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
 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  */
 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 }