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()
     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()
     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* lookupString(HashTable* table, u4 key, StringObject* value)
     55 {
     56     void* entry = dvmHashTableLookup(table, key, (void*)value,
     57                                      dvmHashcmpStrings, false);
     58     return (StringObject*)entry;
     59 }
     60 
     61 static StringObject* insertString(HashTable* table, u4 key, StringObject* value)
     62 {
     63     if (dvmIsNonMovingObject(value) == false) {
     64         value = (StringObject*)dvmCloneObject(value, ALLOC_NON_MOVING);
     65     }
     66     void* entry = dvmHashTableLookup(table, key, (void*)value,
     67                                      dvmHashcmpStrings, true);
     68     return (StringObject*)entry;
     69 }
     70 
     71 static StringObject* lookupInternedString(StringObject* strObj, bool isLiteral)
     72 {
     73     StringObject* found;
     74 
     75     assert(strObj != NULL);
     76     u4 key = dvmComputeStringHash(strObj);
     77     dvmLockMutex(&gDvm.internLock);
     78     if (isLiteral) {
     79         /*
     80          * Check the literal table for a match.
     81          */
     82         StringObject* literal = lookupString(gDvm.literalStrings, key, strObj);
     83         if (literal != NULL) {
     84             /*
     85              * A match was found in the literal table, the easy case.
     86              */
     87             found = literal;
     88         } else {
     89             /*
     90              * There is no match in the literal table, check the
     91              * interned string table.
     92              */
     93             StringObject* interned = lookupString(gDvm.internedStrings, key, strObj);
     94             if (interned != NULL) {
     95                 /*
     96                  * A match was found in the interned table.  Move the
     97                  * matching string to the literal table.
     98                  */
     99                 dvmHashTableRemove(gDvm.internedStrings, key, interned);
    100                 found = insertString(gDvm.literalStrings, key, interned);
    101                 assert(found == interned);
    102             } else {
    103                 /*
    104                  * No match in the literal table or the interned
    105                  * table.  Insert into the literal table.
    106                  */
    107                 found = insertString(gDvm.literalStrings, key, strObj);
    108                 assert(found == strObj);
    109             }
    110         }
    111     } else {
    112         /*
    113          * Check the literal table for a match.
    114          */
    115         found = lookupString(gDvm.literalStrings, key, strObj);
    116         if (found == NULL) {
    117             /*
    118              * No match was found in the literal table.  Insert into
    119              * the intern table if it does not already exist.
    120              */
    121             found = insertString(gDvm.internedStrings, key, strObj);
    122         }
    123     }
    124     assert(found != NULL);
    125     dvmUnlockMutex(&gDvm.internLock);
    126     return found;
    127 }
    128 
    129 /*
    130  * Find an entry in the interned string table.
    131  *
    132  * If the string doesn't already exist, the StringObject is added to
    133  * the table.  Otherwise, the existing entry is returned.
    134  */
    135 StringObject* dvmLookupInternedString(StringObject* strObj)
    136 {
    137     return lookupInternedString(strObj, false);
    138 }
    139 
    140 /*
    141  * Same as dvmLookupInternedString(), but guarantees that the
    142  * returned string is a literal.
    143  */
    144 StringObject* dvmLookupImmortalInternedString(StringObject* strObj)
    145 {
    146     return lookupInternedString(strObj, true);
    147 }
    148 
    149 /*
    150  * Returns true if the object is a weak interned string.  Any string
    151  * interned by the user is weak.
    152  */
    153 bool dvmIsWeakInternedString(StringObject* strObj)
    154 {
    155     assert(strObj != NULL);
    156     if (gDvm.internedStrings == NULL) {
    157         return false;
    158     }
    159     dvmLockMutex(&gDvm.internLock);
    160     u4 key = dvmComputeStringHash(strObj);
    161     StringObject* found = lookupString(gDvm.internedStrings, key, strObj);
    162     dvmUnlockMutex(&gDvm.internLock);
    163     return found == strObj;
    164 }
    165 
    166 /*
    167  * Clear white references from the intern table.
    168  */
    169 void dvmGcDetachDeadInternedStrings(int (*isUnmarkedObject)(void *))
    170 {
    171     /* It's possible for a GC to happen before dvmStringInternStartup()
    172      * is called.
    173      */
    174     if (gDvm.internedStrings != NULL) {
    175         dvmLockMutex(&gDvm.internLock);
    176         dvmHashForeachRemove(gDvm.internedStrings, isUnmarkedObject);
    177         dvmUnlockMutex(&gDvm.internLock);
    178     }
    179 }
    180