1 /* 2 * Copyright (c) 2012, 2017, 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 #include "precompiled.hpp" 26 #include "classfile/altHashing.hpp" 27 #include "classfile/symbolTable.hpp" 28 #include "classfile/systemDictionary.hpp" 29 #include "oops/markOop.hpp" 30 #include "runtime/thread.hpp" 31 32 // Get the hash code of the classes mirror if it exists, otherwise just 33 // return a random number, which is one of the possible hash code used for 34 // objects. We don't want to call the synchronizer hash code to install 35 // this value because it may safepoint. 36 static intptr_t object_hash(Klass* k) { 37 intptr_t hc = k->java_mirror()->mark()->hash(); 38 return hc != markOopDesc::no_hash ? hc : os::random(); 39 } 40 41 // Seed value used for each alternative hash calculated. 42 juint AltHashing::compute_seed() { 43 jlong nanos = os::javaTimeNanos(); 44 jlong now = os::javaTimeMillis(); 45 int SEED_MATERIAL[8] = { 46 (int) object_hash(SystemDictionary::String_klass()), 47 (int) object_hash(SystemDictionary::System_klass()), 48 os::random(), // current thread isn't a java thread 49 (int) (((julong)nanos) >> 32), 50 (int) nanos, 51 (int) (((julong)now) >> 32), 52 (int) now, 53 (int) (os::javaTimeNanos() >> 2) 54 }; 55 56 return murmur3_32(SEED_MATERIAL, 8); 57 } 58 59 60 // Murmur3 hashing for Symbol 61 juint AltHashing::murmur3_32(juint seed, const jbyte* data, int len) { 62 juint h1 = seed; 63 int count = len; 64 int offset = 0; 65 66 // body 67 while (count >= 4) { 68 juint k1 = (data[offset] & 0x0FF) 69 | (data[offset + 1] & 0x0FF) << 8 70 | (data[offset + 2] & 0x0FF) << 16 71 | data[offset + 3] << 24; 72 73 count -= 4; 74 offset += 4; 75 76 k1 *= 0xcc9e2d51; 77 k1 = Integer_rotateLeft(k1, 15); 78 k1 *= 0x1b873593; 79 80 h1 ^= k1; 81 h1 = Integer_rotateLeft(h1, 13); 82 h1 = h1 * 5 + 0xe6546b64; 83 } 84 85 // tail 86 87 if (count > 0) { 88 juint k1 = 0; 89 90 switch (count) { 91 case 3: 92 k1 ^= (data[offset + 2] & 0xff) << 16; 93 // fall through 94 case 2: 95 k1 ^= (data[offset + 1] & 0xff) << 8; 96 // fall through 97 case 1: 98 k1 ^= (data[offset] & 0xff); 99 // fall through 100 default: 101 k1 *= 0xcc9e2d51; 102 k1 = Integer_rotateLeft(k1, 15); 103 k1 *= 0x1b873593; 104 h1 ^= k1; 105 } 106 } 107 108 // finalization 109 h1 ^= len; 110 111 // finalization mix force all bits of a hash block to avalanche 112 h1 ^= h1 >> 16; 113 h1 *= 0x85ebca6b; 114 h1 ^= h1 >> 13; 115 h1 *= 0xc2b2ae35; 116 h1 ^= h1 >> 16; 117 118 return h1; 119 } 120 121 // Murmur3 hashing for Strings 122 juint AltHashing::murmur3_32(juint seed, const jchar* data, int len) { 123 juint h1 = seed; 124 125 int off = 0; 126 int count = len; 127 128 // body 129 while (count >= 2) { 130 jchar d1 = data[off++] & 0xFFFF; 131 jchar d2 = data[off++]; 132 juint k1 = (d1 | d2 << 16); 133 134 count -= 2; 135 136 k1 *= 0xcc9e2d51; 137 k1 = Integer_rotateLeft(k1, 15); 138 k1 *= 0x1b873593; 139 140 h1 ^= k1; 141 h1 = Integer_rotateLeft(h1, 13); 142 h1 = h1 * 5 + 0xe6546b64; 143 } 144 145 // tail 146 147 if (count > 0) { 148 juint k1 = (juint)data[off]; 149 150 k1 *= 0xcc9e2d51; 151 k1 = Integer_rotateLeft(k1, 15); 152 k1 *= 0x1b873593; 153 h1 ^= k1; 154 } 155 156 // finalization 157 h1 ^= len * 2; // (Character.SIZE / Byte.SIZE); 158 159 // finalization mix force all bits of a hash block to avalanche 160 h1 ^= h1 >> 16; 161 h1 *= 0x85ebca6b; 162 h1 ^= h1 >> 13; 163 h1 *= 0xc2b2ae35; 164 h1 ^= h1 >> 16; 165 166 return h1; 167 } 168 169 // Hash used for the seed. 170 juint AltHashing::murmur3_32(juint seed, const int* data, int len) { 171 juint h1 = seed; 172 173 int off = 0; 174 int end = len; 175 176 // body 177 while (off < end) { 178 juint k1 = (juint)data[off++]; 179 180 k1 *= 0xcc9e2d51; 181 k1 = Integer_rotateLeft(k1, 15); 182 k1 *= 0x1b873593; 183 184 h1 ^= k1; 185 h1 = Integer_rotateLeft(h1, 13); 186 h1 = h1 * 5 + 0xe6546b64; 187 } 188 189 // tail (always empty, as body is always 32-bit chunks) 190 191 // finalization 192 193 h1 ^= len * 4; // (Integer.SIZE / Byte.SIZE); 194 195 // finalization mix force all bits of a hash block to avalanche 196 h1 ^= h1 >> 16; 197 h1 *= 0x85ebca6b; 198 h1 ^= h1 >> 13; 199 h1 *= 0xc2b2ae35; 200 h1 ^= h1 >> 16; 201 202 return h1; 203 } 204 205 juint AltHashing::murmur3_32(const int* data, int len) { 206 return murmur3_32(0, data, len); 207 }