Home | History | Annotate | Download | only in vm 
      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 }
    174