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