1 /* 2 * Copyright (c) 2015, 2020, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 package sun.jvm.hotspot.utilities; 26 27 import java.util.*; 28 import sun.jvm.hotspot.debugger.*; 29 import sun.jvm.hotspot.oops.*; 30 import sun.jvm.hotspot.types.*; 31 import sun.jvm.hotspot.runtime.*; 32 import sun.jvm.hotspot.utilities.*; 33 import sun.jvm.hotspot.utilities.Observable; 34 import sun.jvm.hotspot.utilities.Observer; 35 36 public class CompactHashTable extends VMObject { 37 static { VM.registerVMInitializedObserver(new Observer() { public void update(Observable o, Object data) { initialize(VM.getVM().getTypeDataBase()); } })38 VM.registerVMInitializedObserver(new Observer() { 39 public void update(Observable o, Object data) { 40 initialize(VM.getVM().getTypeDataBase()); 41 } 42 }); 43 } 44 initialize(TypeDataBase db)45 private static synchronized void initialize(TypeDataBase db) throws WrongTypeException { 46 Type type = db.lookupType("SymbolCompactHashTable"); 47 baseAddressField = type.getAddressField("_base_address"); 48 bucketCountField = type.getCIntegerField("_bucket_count"); 49 entryCountField = type.getCIntegerField("_entry_count"); 50 bucketsField = type.getAddressField("_buckets"); 51 entriesField = type.getAddressField("_entries"); 52 uintSize = db.lookupType("u4").getSize(); 53 } 54 55 // Fields 56 private static CIntegerField bucketCountField; 57 private static CIntegerField entryCountField; 58 private static AddressField baseAddressField; 59 private static AddressField bucketsField; 60 private static AddressField entriesField; 61 private static long uintSize; 62 63 private static int BUCKET_OFFSET_MASK = 0x3FFFFFFF; 64 private static int BUCKET_TYPE_SHIFT = 30; 65 private static int VALUE_ONLY_BUCKET_TYPE = 1; 66 CompactHashTable(Address addr)67 public CompactHashTable(Address addr) { 68 super(addr); 69 } 70 bucketCount()71 private int bucketCount() { 72 return (int)bucketCountField.getValue(addr); 73 } 74 isValueOnlyBucket(int bucket_info)75 private boolean isValueOnlyBucket(int bucket_info) { 76 return (bucket_info >> BUCKET_TYPE_SHIFT) == VALUE_ONLY_BUCKET_TYPE; 77 } 78 bucketOffset(int bucket_info)79 private int bucketOffset(int bucket_info) { 80 return bucket_info & BUCKET_OFFSET_MASK; 81 } 82 probe(byte[] name, long hash)83 public Symbol probe(byte[] name, long hash) { 84 if (bucketCount() <= 0) { 85 // This CompactHashTable is not in use 86 return null; 87 } 88 89 long symOffset; 90 Symbol sym; 91 Address baseAddress = baseAddressField.getValue(addr); 92 Address bucket = bucketsField.getValue(addr); 93 long index = hash % bucketCount(); 94 int bucketInfo = (int)bucket.getCIntegerAt(index * uintSize, uintSize, true); 95 int bucketOffset = bucketOffset(bucketInfo); 96 int nextBucketInfo = (int)bucket.getCIntegerAt((index+1) * uintSize, uintSize, true); 97 int nextBucketOffset = bucketOffset(nextBucketInfo); 98 99 Address entry = entriesField.getValue(addr).addOffsetTo(bucketOffset * uintSize); 100 101 if (isValueOnlyBucket(bucketInfo)) { 102 symOffset = entry.getCIntegerAt(0, uintSize, true); 103 sym = Symbol.create(baseAddress.addOffsetTo(symOffset)); 104 if (sym.equals(name)) { 105 return sym; 106 } 107 } else { 108 Address entryMax = entriesField.getValue(addr).addOffsetTo(nextBucketOffset * uintSize); 109 while (entry.lessThan(entryMax)) { 110 long symHash = entry.getCIntegerAt(0, uintSize, true); 111 if (symHash == hash) { 112 symOffset = entry.getCIntegerAt(uintSize, uintSize, true); 113 Address symAddr = baseAddress.addOffsetTo(symOffset); 114 sym = Symbol.create(symAddr); 115 if (sym.equals(name)) { 116 return sym; 117 } 118 } 119 entry = entry.addOffsetTo(2 * uintSize); 120 } 121 } 122 return null; 123 } 124 125 public interface SymbolVisitor { visit(Symbol sym)126 public void visit(Symbol sym); 127 } 128 symbolsDo(SymbolVisitor visitor)129 public void symbolsDo(SymbolVisitor visitor) { 130 long symOffset; 131 Symbol sym; 132 Address baseAddress = baseAddressField.getValue(addr); 133 Address bucket = bucketsField.getValue(addr); 134 for (long index = 0; index < bucketCount(); index++) { 135 int bucketInfo = (int)bucket.getCIntegerAt(index * uintSize, uintSize, true); 136 int bucketOffset = bucketOffset(bucketInfo); 137 int nextBucketInfo = (int)bucket.getCIntegerAt((index+1) * uintSize, uintSize, true); 138 int nextBucketOffset = bucketOffset(nextBucketInfo); 139 140 Address entry = entriesField.getValue(addr).addOffsetTo(bucketOffset * uintSize); 141 142 if (isValueOnlyBucket(bucketInfo)) { 143 symOffset = entry.getCIntegerAt(0, uintSize, true); 144 sym = Symbol.create(baseAddress.addOffsetTo(symOffset)); 145 visitor.visit(sym); 146 } else { 147 Address entryMax = entriesField.getValue(addr).addOffsetTo(nextBucketOffset * uintSize); 148 while (entry.lessThan(entryMax)) { 149 symOffset = entry.getCIntegerAt(uintSize, uintSize, true); 150 Address symAddr = baseAddress.addOffsetTo(symOffset); 151 sym = Symbol.create(symAddr); 152 visitor.visit(sym); 153 entry = entry.addOffsetTo(2 * uintSize); 154 } 155 } 156 } 157 } 158 } 159 160