1 /*
   2  * Copyright (c) 2015, 2016, 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 {
  36     VM.registerVMInitializedObserver(new Observer() {
  37       public void update(Observable o, Object data) {
  38         initialize(VM.getVM().getTypeDataBase());
  39       }
  40     });
  41   }
  42 
  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 
  65   public CompactHashTable(Address addr) {
  66     super(addr);
  67   }
  68 
  69   private int bucketCount() {
  70     return (int)bucketCountField.getValue(addr);
  71   }
  72 
  73   private boolean isValueOnlyBucket(int bucket_info) {
  74     return (bucket_info >> BUCKET_TYPE_SHIFT) == VALUE_ONLY_BUCKET_TYPE;
  75   }
  76 
  77   private int bucketOffset(int bucket_info) {
  78     return bucket_info & BUCKET_OFFSET_MASK;
  79   }
  80 
  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 }