1 /* 2 * Copyright (c) 2015, 2018, 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 34 public class CompactHashTable extends VMObject { 35 static { VM.registerVMInitializedObserver(new Observer() { public void update(Observable o, Object data) { initialize(VM.getVM().getTypeDataBase()); } })36 VM.registerVMInitializedObserver(new Observer() { 37 public void update(Observable o, Object data) { 38 initialize(VM.getVM().getTypeDataBase()); 39 } 40 }); 41 } 42 initialize(TypeDataBase db)43 private static synchronized void initialize(TypeDataBase db) throws WrongTypeException { 44 Type type = db.lookupType("SymbolCompactHashTable"); 45 baseAddressField = type.getAddressField("_base_address"); 46 bucketCountField = type.getCIntegerField("_bucket_count"); 47 entryCountField = type.getCIntegerField("_entry_count"); 48 bucketsField = type.getAddressField("_buckets"); 49 entriesField = type.getAddressField("_entries"); 50 uintSize = db.lookupType("u4").getSize(); 51 } 52 53 // Fields 54 private static CIntegerField bucketCountField; 55 private static CIntegerField entryCountField; 56 private static AddressField baseAddressField; 57 private static AddressField bucketsField; 58 private static AddressField entriesField; 59 private static long uintSize; 60 61 private static int BUCKET_OFFSET_MASK = 0x3FFFFFFF; 62 private static int BUCKET_TYPE_SHIFT = 30; 63 private static int VALUE_ONLY_BUCKET_TYPE = 1; 64 CompactHashTable(Address addr)65 public CompactHashTable(Address addr) { 66 super(addr); 67 } 68 bucketCount()69 private int bucketCount() { 70 return (int)bucketCountField.getValue(addr); 71 } 72 isValueOnlyBucket(int bucket_info)73 private boolean isValueOnlyBucket(int bucket_info) { 74 return (bucket_info >> BUCKET_TYPE_SHIFT) == VALUE_ONLY_BUCKET_TYPE; 75 } 76 bucketOffset(int bucket_info)77 private int bucketOffset(int bucket_info) { 78 return bucket_info & BUCKET_OFFSET_MASK; 79 } 80 probe(byte[] name, long hash)81 public Symbol probe(byte[] name, long hash) { 82 if (bucketCount() <= 0) { 83 // This CompactHashTable is not in use 84 return null; 85 } 86 87 long symOffset; 88 Symbol sym; 89 Address baseAddress = baseAddressField.getValue(addr); 90 Address bucket = bucketsField.getValue(addr); 91 long index = hash % bucketCount(); 92 int bucketInfo = (int)bucket.getCIntegerAt(index * uintSize, uintSize, true); 93 int bucketOffset = bucketOffset(bucketInfo); 94 int nextBucketInfo = (int)bucket.getCIntegerAt((index+1) * uintSize, uintSize, true); 95 int nextBucketOffset = bucketOffset(nextBucketInfo); 96 97 Address entry = entriesField.getValue(addr).addOffsetTo(bucketOffset * uintSize); 98 99 if (isValueOnlyBucket(bucketInfo)) { 100 symOffset = entry.getCIntegerAt(0, uintSize, true); 101 sym = Symbol.create(baseAddress.addOffsetTo(symOffset)); 102 if (sym.equals(name)) { 103 return sym; 104 } 105 } else { 106 Address entryMax = entriesField.getValue(addr).addOffsetTo(nextBucketOffset * uintSize); 107 while (entry.lessThan(entryMax)) { 108 long symHash = entry.getCIntegerAt(0, uintSize, true); 109 if (symHash == hash) { 110 symOffset = entry.getCIntegerAt(uintSize, uintSize, true); 111 Address symAddr = baseAddress.addOffsetTo(symOffset); 112 sym = Symbol.create(symAddr); 113 if (sym.equals(name)) { 114 return sym; 115 } 116 } 117 entry = entry.addOffsetTo(2 * uintSize); 118 } 119 } 120 return null; 121 } 122 123 public interface SymbolVisitor { visit(Symbol sym)124 public void visit(Symbol sym); 125 } 126 symbolsDo(SymbolVisitor visitor)127 public void symbolsDo(SymbolVisitor visitor) { 128 long symOffset; 129 Symbol sym; 130 Address baseAddress = baseAddressField.getValue(addr); 131 Address bucket = bucketsField.getValue(addr); 132 for (long index = 0; index < bucketCount(); index++) { 133 int bucketInfo = (int)bucket.getCIntegerAt(index * uintSize, uintSize, true); 134 int bucketOffset = bucketOffset(bucketInfo); 135 int nextBucketInfo = (int)bucket.getCIntegerAt((index+1) * uintSize, uintSize, true); 136 int nextBucketOffset = bucketOffset(nextBucketInfo); 137 138 Address entry = entriesField.getValue(addr).addOffsetTo(bucketOffset * uintSize); 139 140 if (isValueOnlyBucket(bucketInfo)) { 141 symOffset = entry.getCIntegerAt(0, uintSize, true); 142 sym = Symbol.create(baseAddress.addOffsetTo(symOffset)); 143 visitor.visit(sym); 144 } else { 145 Address entryMax = entriesField.getValue(addr).addOffsetTo(nextBucketOffset * uintSize); 146 while (entry.lessThan(entryMax)) { 147 symOffset = entry.getCIntegerAt(uintSize, uintSize, true); 148 Address symAddr = baseAddress.addOffsetTo(symOffset); 149 sym = Symbol.create(symAddr); 150 visitor.visit(sym); 151 entry = entry.addOffsetTo(2 * uintSize); 152 } 153 } 154 } 155 } 156 } 157 158