Mon, 24 Dec 2012 11:46:38 -0800
Merge
coleenp@3865 | 1 | /* |
coleenp@3865 | 2 | * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. |
coleenp@3865 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
coleenp@3865 | 4 | * |
coleenp@3865 | 5 | * This code is free software; you can redistribute it and/or modify it |
coleenp@3865 | 6 | * under the terms of the GNU General Public License version 2 only, as |
coleenp@3865 | 7 | * published by the Free Software Foundation. |
coleenp@3865 | 8 | * |
coleenp@3865 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
coleenp@3865 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
coleenp@3865 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
coleenp@3865 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
coleenp@3865 | 13 | * accompanied this code). |
coleenp@3865 | 14 | * |
coleenp@3865 | 15 | * You should have received a copy of the GNU General Public License version |
coleenp@3865 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
coleenp@3865 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
coleenp@3865 | 18 | * |
coleenp@3865 | 19 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
coleenp@3865 | 20 | * or visit www.oracle.com if you need additional information or have any |
coleenp@3865 | 21 | * questions. |
coleenp@3865 | 22 | * |
coleenp@3865 | 23 | */ |
coleenp@3865 | 24 | |
coleenp@3865 | 25 | #include "precompiled.hpp" |
coleenp@3865 | 26 | #include "classfile/altHashing.hpp" |
coleenp@3865 | 27 | #include "classfile/symbolTable.hpp" |
coleenp@3865 | 28 | #include "classfile/systemDictionary.hpp" |
coleenp@3865 | 29 | #include "oops/markOop.hpp" |
coleenp@3865 | 30 | #include "runtime/thread.hpp" |
coleenp@3865 | 31 | |
coleenp@3865 | 32 | // Get the hash code of the classes mirror if it exists, otherwise just |
coleenp@3865 | 33 | // return a random number, which is one of the possible hash code used for |
coleenp@3865 | 34 | // objects. We don't want to call the synchronizer hash code to install |
coleenp@3865 | 35 | // this value because it may safepoint. |
coleenp@4037 | 36 | intptr_t object_hash(Klass* k) { |
coleenp@3865 | 37 | intptr_t hc = k->java_mirror()->mark()->hash(); |
coleenp@3865 | 38 | return hc != markOopDesc::no_hash ? hc : os::random(); |
coleenp@3865 | 39 | } |
coleenp@3865 | 40 | |
coleenp@3865 | 41 | // Seed value used for each alternative hash calculated. |
coleenp@3865 | 42 | jint AltHashing::compute_seed() { |
coleenp@3865 | 43 | jlong nanos = os::javaTimeNanos(); |
coleenp@3865 | 44 | jlong now = os::javaTimeMillis(); |
coleenp@3865 | 45 | jint SEED_MATERIAL[8] = { |
coleenp@3865 | 46 | (jint) object_hash(SystemDictionary::String_klass()), |
coleenp@3865 | 47 | (jint) object_hash(SystemDictionary::System_klass()), |
coleenp@3865 | 48 | (jint) os::random(), // current thread isn't a java thread |
coleenp@3865 | 49 | (jint) (((julong)nanos) >> 32), |
coleenp@3865 | 50 | (jint) nanos, |
coleenp@3865 | 51 | (jint) (((julong)now) >> 32), |
coleenp@3865 | 52 | (jint) now, |
coleenp@3865 | 53 | (jint) (os::javaTimeNanos() >> 2) |
coleenp@3865 | 54 | }; |
coleenp@3865 | 55 | |
coleenp@3865 | 56 | return murmur3_32(SEED_MATERIAL, 8); |
coleenp@3865 | 57 | } |
coleenp@3865 | 58 | |
coleenp@3865 | 59 | |
coleenp@3865 | 60 | // Murmur3 hashing for Symbol |
coleenp@3865 | 61 | jint AltHashing::murmur3_32(jint seed, const jbyte* data, int len) { |
coleenp@3865 | 62 | jint h1 = seed; |
coleenp@3865 | 63 | int count = len; |
coleenp@3865 | 64 | int offset = 0; |
coleenp@3865 | 65 | |
coleenp@3865 | 66 | // body |
coleenp@3865 | 67 | while (count >= 4) { |
coleenp@3865 | 68 | jint k1 = (data[offset] & 0x0FF) |
coleenp@3865 | 69 | | (data[offset + 1] & 0x0FF) << 8 |
coleenp@3865 | 70 | | (data[offset + 2] & 0x0FF) << 16 |
coleenp@3865 | 71 | | data[offset + 3] << 24; |
coleenp@3865 | 72 | |
coleenp@3865 | 73 | count -= 4; |
coleenp@3865 | 74 | offset += 4; |
coleenp@3865 | 75 | |
coleenp@3865 | 76 | k1 *= 0xcc9e2d51; |
coleenp@3865 | 77 | k1 = Integer_rotateLeft(k1, 15); |
coleenp@3865 | 78 | k1 *= 0x1b873593; |
coleenp@3865 | 79 | |
coleenp@3865 | 80 | h1 ^= k1; |
coleenp@3865 | 81 | h1 = Integer_rotateLeft(h1, 13); |
coleenp@3865 | 82 | h1 = h1 * 5 + 0xe6546b64; |
coleenp@3865 | 83 | } |
coleenp@3865 | 84 | |
coleenp@3865 | 85 | // tail |
coleenp@3865 | 86 | |
coleenp@3865 | 87 | if (count > 0) { |
coleenp@3865 | 88 | jint k1 = 0; |
coleenp@3865 | 89 | |
coleenp@3865 | 90 | switch (count) { |
coleenp@3865 | 91 | case 3: |
coleenp@3865 | 92 | k1 ^= (data[offset + 2] & 0xff) << 16; |
coleenp@3865 | 93 | // fall through |
coleenp@3865 | 94 | case 2: |
coleenp@3865 | 95 | k1 ^= (data[offset + 1] & 0xff) << 8; |
coleenp@3865 | 96 | // fall through |
coleenp@3865 | 97 | case 1: |
coleenp@3865 | 98 | k1 ^= (data[offset] & 0xff); |
coleenp@3865 | 99 | // fall through |
coleenp@3865 | 100 | default: |
coleenp@3865 | 101 | k1 *= 0xcc9e2d51; |
coleenp@3865 | 102 | k1 = Integer_rotateLeft(k1, 15); |
coleenp@3865 | 103 | k1 *= 0x1b873593; |
coleenp@3865 | 104 | h1 ^= k1; |
coleenp@3865 | 105 | } |
coleenp@3865 | 106 | } |
coleenp@3865 | 107 | |
coleenp@3865 | 108 | // finalization |
coleenp@3865 | 109 | h1 ^= len; |
coleenp@3865 | 110 | |
coleenp@3865 | 111 | // finalization mix force all bits of a hash block to avalanche |
coleenp@3865 | 112 | h1 ^= ((unsigned int)h1) >> 16; |
coleenp@3865 | 113 | h1 *= 0x85ebca6b; |
coleenp@3865 | 114 | h1 ^= ((unsigned int)h1) >> 13; |
coleenp@3865 | 115 | h1 *= 0xc2b2ae35; |
coleenp@3865 | 116 | h1 ^= ((unsigned int)h1) >> 16; |
coleenp@3865 | 117 | |
coleenp@3865 | 118 | return h1; |
coleenp@3865 | 119 | } |
coleenp@3865 | 120 | |
coleenp@3865 | 121 | // Murmur3 hashing for Strings |
coleenp@3865 | 122 | jint AltHashing::murmur3_32(jint seed, const jchar* data, int len) { |
coleenp@3865 | 123 | jint h1 = seed; |
coleenp@3865 | 124 | |
coleenp@3865 | 125 | int off = 0; |
coleenp@3865 | 126 | int count = len; |
coleenp@3865 | 127 | |
coleenp@3865 | 128 | // body |
coleenp@3865 | 129 | while (count >= 2) { |
coleenp@3865 | 130 | jchar d1 = data[off++] & 0xFFFF; |
coleenp@3865 | 131 | jchar d2 = data[off++]; |
coleenp@3865 | 132 | jint k1 = (d1 | d2 << 16); |
coleenp@3865 | 133 | |
coleenp@3865 | 134 | count -= 2; |
coleenp@3865 | 135 | |
coleenp@3865 | 136 | k1 *= 0xcc9e2d51; |
coleenp@3865 | 137 | k1 = Integer_rotateLeft(k1, 15); |
coleenp@3865 | 138 | k1 *= 0x1b873593; |
coleenp@3865 | 139 | |
coleenp@3865 | 140 | h1 ^= k1; |
coleenp@3865 | 141 | h1 = Integer_rotateLeft(h1, 13); |
coleenp@3865 | 142 | h1 = h1 * 5 + 0xe6546b64; |
coleenp@3865 | 143 | } |
coleenp@3865 | 144 | |
coleenp@3865 | 145 | // tail |
coleenp@3865 | 146 | |
coleenp@3865 | 147 | if (count > 0) { |
coleenp@3865 | 148 | int k1 = data[off]; |
coleenp@3865 | 149 | |
coleenp@3865 | 150 | k1 *= 0xcc9e2d51; |
coleenp@3865 | 151 | k1 = Integer_rotateLeft(k1, 15); |
coleenp@3865 | 152 | k1 *= 0x1b873593; |
coleenp@3865 | 153 | h1 ^= k1; |
coleenp@3865 | 154 | } |
coleenp@3865 | 155 | |
coleenp@3865 | 156 | // finalization |
coleenp@3865 | 157 | h1 ^= len * 2; // (Character.SIZE / Byte.SIZE); |
coleenp@3865 | 158 | |
coleenp@3865 | 159 | // finalization mix force all bits of a hash block to avalanche |
coleenp@3865 | 160 | h1 ^= ((unsigned int)h1) >> 16; |
coleenp@3865 | 161 | h1 *= 0x85ebca6b; |
coleenp@3865 | 162 | h1 ^= ((unsigned int)h1) >> 13; |
coleenp@3865 | 163 | h1 *= 0xc2b2ae35; |
coleenp@3865 | 164 | h1 ^= ((unsigned int)h1) >> 16; |
coleenp@3865 | 165 | |
coleenp@3865 | 166 | return h1; |
coleenp@3865 | 167 | } |
coleenp@3865 | 168 | |
coleenp@3865 | 169 | // Hash used for the seed. |
coleenp@3865 | 170 | jint AltHashing::murmur3_32(jint seed, const int* data, int len) { |
coleenp@3865 | 171 | jint h1 = seed; |
coleenp@3865 | 172 | |
coleenp@3865 | 173 | int off = 0; |
coleenp@3865 | 174 | int end = len; |
coleenp@3865 | 175 | |
coleenp@3865 | 176 | // body |
coleenp@3865 | 177 | while (off < end) { |
coleenp@3865 | 178 | jint k1 = data[off++]; |
coleenp@3865 | 179 | |
coleenp@3865 | 180 | k1 *= 0xcc9e2d51; |
coleenp@3865 | 181 | k1 = Integer_rotateLeft(k1, 15); |
coleenp@3865 | 182 | k1 *= 0x1b873593; |
coleenp@3865 | 183 | |
coleenp@3865 | 184 | h1 ^= k1; |
coleenp@3865 | 185 | h1 = Integer_rotateLeft(h1, 13); |
coleenp@3865 | 186 | h1 = h1 * 5 + 0xe6546b64; |
coleenp@3865 | 187 | } |
coleenp@3865 | 188 | |
coleenp@3865 | 189 | // tail (always empty, as body is always 32-bit chunks) |
coleenp@3865 | 190 | |
coleenp@3865 | 191 | // finalization |
coleenp@3865 | 192 | |
coleenp@3865 | 193 | h1 ^= len * 4; // (Integer.SIZE / Byte.SIZE); |
coleenp@3865 | 194 | |
coleenp@3865 | 195 | // finalization mix force all bits of a hash block to avalanche |
coleenp@3865 | 196 | h1 ^= ((juint)h1) >> 16; |
coleenp@3865 | 197 | h1 *= 0x85ebca6b; |
coleenp@3865 | 198 | h1 ^= ((juint)h1) >> 13; |
coleenp@3865 | 199 | h1 *= 0xc2b2ae35; |
coleenp@3865 | 200 | h1 ^= ((juint)h1) >> 16; |
coleenp@3865 | 201 | |
coleenp@3865 | 202 | return h1; |
coleenp@3865 | 203 | } |
coleenp@3865 | 204 | |
coleenp@3865 | 205 | jint AltHashing::murmur3_32(const int* data, int len) { |
coleenp@3865 | 206 | return murmur3_32(0, data, len); |
coleenp@3865 | 207 | } |
coleenp@3865 | 208 | |
coleenp@3865 | 209 | #ifndef PRODUCT |
coleenp@3865 | 210 | // Overloaded versions for internal test. |
coleenp@3865 | 211 | jint AltHashing::murmur3_32(const jbyte* data, int len) { |
coleenp@3865 | 212 | return murmur3_32(0, data, len); |
coleenp@3865 | 213 | } |
coleenp@3865 | 214 | |
coleenp@3865 | 215 | jint AltHashing::murmur3_32(const jchar* data, int len) { |
coleenp@3865 | 216 | return murmur3_32(0, data, len); |
coleenp@3865 | 217 | } |
coleenp@3865 | 218 | |
coleenp@3865 | 219 | // Internal test for alternate hashing. Translated from JDK version |
coleenp@3865 | 220 | // test/sun/misc/Hashing.java |
coleenp@3865 | 221 | static const jbyte ONE_BYTE[] = { (jbyte) 0x80}; |
coleenp@3865 | 222 | static const jbyte TWO_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81}; |
coleenp@3865 | 223 | static const jchar ONE_CHAR[] = { (jchar) 0x8180}; |
coleenp@3865 | 224 | static const jbyte THREE_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82}; |
coleenp@3865 | 225 | static const jbyte FOUR_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, (jbyte) 0x83}; |
coleenp@3865 | 226 | static const jchar TWO_CHAR[] = { (jchar) 0x8180, (jchar) 0x8382}; |
coleenp@3865 | 227 | static const jint ONE_INT[] = { 0x83828180}; |
coleenp@3865 | 228 | static const jbyte SIX_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, (jbyte) 0x83, (jbyte) 0x84, (jbyte) 0x85}; |
coleenp@3865 | 229 | static const jchar THREE_CHAR[] = { (jchar) 0x8180, (jchar) 0x8382, (jchar) 0x8584}; |
coleenp@3865 | 230 | static const jbyte EIGHT_BYTE[] = { |
coleenp@3865 | 231 | (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, |
coleenp@3865 | 232 | (jbyte) 0x83, (jbyte) 0x84, (jbyte) 0x85, |
coleenp@3865 | 233 | (jbyte) 0x86, (jbyte) 0x87}; |
coleenp@3865 | 234 | static const jchar FOUR_CHAR[] = { |
coleenp@3865 | 235 | (jchar) 0x8180, (jchar) 0x8382, |
coleenp@3865 | 236 | (jchar) 0x8584, (jchar) 0x8786}; |
coleenp@3865 | 237 | |
coleenp@3865 | 238 | static const jint TWO_INT[] = { 0x83828180, 0x87868584}; |
coleenp@3865 | 239 | |
coleenp@3865 | 240 | static const juint MURMUR3_32_X86_CHECK_VALUE = 0xB0F57EE3; |
coleenp@3865 | 241 | |
coleenp@3865 | 242 | void AltHashing::testMurmur3_32_ByteArray() { |
coleenp@3865 | 243 | // printf("testMurmur3_32_ByteArray\n"); |
coleenp@3865 | 244 | |
coleenp@3865 | 245 | jbyte* vector = new jbyte[256]; |
coleenp@3865 | 246 | jbyte* hashes = new jbyte[4 * 256]; |
coleenp@3865 | 247 | |
coleenp@3865 | 248 | for (int i = 0; i < 256; i++) { |
coleenp@3865 | 249 | vector[i] = (jbyte) i; |
coleenp@3865 | 250 | } |
coleenp@3865 | 251 | |
coleenp@3865 | 252 | // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255} |
coleenp@3865 | 253 | for (int i = 0; i < 256; i++) { |
coleenp@3865 | 254 | jint hash = murmur3_32(256 - i, vector, i); |
coleenp@3865 | 255 | hashes[i * 4] = (jbyte) hash; |
coleenp@3865 | 256 | hashes[i * 4 + 1] = (jbyte) (((juint)hash) >> 8); |
coleenp@3865 | 257 | hashes[i * 4 + 2] = (jbyte) (((juint)hash) >> 16); |
coleenp@3865 | 258 | hashes[i * 4 + 3] = (jbyte) (((juint)hash) >> 24); |
coleenp@3865 | 259 | } |
coleenp@3865 | 260 | |
coleenp@3865 | 261 | // hash to get const result. |
coleenp@3865 | 262 | juint final_hash = murmur3_32(hashes, 4*256); |
coleenp@3865 | 263 | |
coleenp@3865 | 264 | assert (MURMUR3_32_X86_CHECK_VALUE == final_hash, |
coleenp@3865 | 265 | err_msg( |
coleenp@3865 | 266 | "Calculated hash result not as expected. Expected %08X got %08X\n", |
coleenp@3865 | 267 | MURMUR3_32_X86_CHECK_VALUE, |
coleenp@3865 | 268 | final_hash)); |
coleenp@3865 | 269 | } |
coleenp@3865 | 270 | |
coleenp@3865 | 271 | void AltHashing::testEquivalentHashes() { |
coleenp@3865 | 272 | jint jbytes, jchars, ints; |
coleenp@3865 | 273 | |
coleenp@3865 | 274 | // printf("testEquivalentHashes\n"); |
coleenp@3865 | 275 | |
coleenp@3865 | 276 | jbytes = murmur3_32(TWO_BYTE, 2); |
coleenp@3865 | 277 | jchars = murmur3_32(ONE_CHAR, 1); |
coleenp@3865 | 278 | assert (jbytes == jchars, |
coleenp@3865 | 279 | err_msg("Hashes did not match. b:%08x != c:%08x\n", jbytes, jchars)); |
coleenp@3865 | 280 | |
coleenp@3865 | 281 | jbytes = murmur3_32(FOUR_BYTE, 4); |
coleenp@3865 | 282 | jchars = murmur3_32(TWO_CHAR, 2); |
coleenp@3865 | 283 | ints = murmur3_32(ONE_INT, 1); |
coleenp@3865 | 284 | assert ((jbytes == jchars) && (jbytes == ints), |
coleenp@3865 | 285 | err_msg("Hashes did not match. b:%08x != c:%08x != i:%08x\n", jbytes, jchars, ints)); |
coleenp@3865 | 286 | |
coleenp@3865 | 287 | jbytes = murmur3_32(SIX_BYTE, 6); |
coleenp@3865 | 288 | jchars = murmur3_32(THREE_CHAR, 3); |
coleenp@3865 | 289 | assert (jbytes == jchars, |
coleenp@3865 | 290 | err_msg("Hashes did not match. b:%08x != c:%08x\n", jbytes, jchars)); |
coleenp@3865 | 291 | |
coleenp@3865 | 292 | jbytes = murmur3_32(EIGHT_BYTE, 8); |
coleenp@3865 | 293 | jchars = murmur3_32(FOUR_CHAR, 4); |
coleenp@3865 | 294 | ints = murmur3_32(TWO_INT, 2); |
coleenp@3865 | 295 | assert ((jbytes == jchars) && (jbytes == ints), |
coleenp@3865 | 296 | err_msg("Hashes did not match. b:%08x != c:%08x != i:%08x\n", jbytes, jchars, ints)); |
coleenp@3865 | 297 | } |
coleenp@3865 | 298 | |
coleenp@3865 | 299 | // Returns true if the alternate hashcode is correct |
coleenp@3865 | 300 | void AltHashing::test_alt_hash() { |
coleenp@3865 | 301 | testMurmur3_32_ByteArray(); |
coleenp@3865 | 302 | testEquivalentHashes(); |
coleenp@3865 | 303 | } |
coleenp@3865 | 304 | #endif // PRODUCT |