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 <stddef.h>
     22 
     23 /*
     24  * Prep string interning.
     25  */
     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  */
     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 
     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  */
    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  */
    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  */
    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 
    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  */
    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  */
    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