Mercurial > hg > truffle
annotate src/share/vm/classfile/altHashing.cpp @ 7985:ab826603e572
8007475: Memory stomp with UseMallocOnly
Summary: Fix off-by-one error
Reviewed-by: coleenp, hseigel
author | simonis |
---|---|
date | Mon, 04 Feb 2013 13:14:12 -0500 |
parents | da91efe96a93 |
children | 6f817ce50129 |
rev | line source |
---|---|
6162 | 1 /* |
2 * Copyright (c) 2012, 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. | |
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6162
diff
changeset
|
36 intptr_t object_hash(Klass* k) { |
6162 | 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 jint AltHashing::compute_seed() { | |
43 jlong nanos = os::javaTimeNanos(); | |
44 jlong now = os::javaTimeMillis(); | |
45 jint SEED_MATERIAL[8] = { | |
46 (jint) object_hash(SystemDictionary::String_klass()), | |
47 (jint) object_hash(SystemDictionary::System_klass()), | |
48 (jint) os::random(), // current thread isn't a java thread | |
49 (jint) (((julong)nanos) >> 32), | |
50 (jint) nanos, | |
51 (jint) (((julong)now) >> 32), | |
52 (jint) now, | |
53 (jint) (os::javaTimeNanos() >> 2) | |
54 }; | |
55 | |
56 return murmur3_32(SEED_MATERIAL, 8); | |
57 } | |
58 | |
59 | |
60 // Murmur3 hashing for Symbol | |
61 jint AltHashing::murmur3_32(jint seed, const jbyte* data, int len) { | |
62 jint h1 = seed; | |
63 int count = len; | |
64 int offset = 0; | |
65 | |
66 // body | |
67 while (count >= 4) { | |
68 jint 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 jint 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 ^= ((unsigned int)h1) >> 16; | |
113 h1 *= 0x85ebca6b; | |
114 h1 ^= ((unsigned int)h1) >> 13; | |
115 h1 *= 0xc2b2ae35; | |
116 h1 ^= ((unsigned int)h1) >> 16; | |
117 | |
118 return h1; | |
119 } | |
120 | |
121 // Murmur3 hashing for Strings | |
122 jint AltHashing::murmur3_32(jint seed, const jchar* data, int len) { | |
123 jint 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 jint 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 int k1 = 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 ^= ((unsigned int)h1) >> 16; | |
161 h1 *= 0x85ebca6b; | |
162 h1 ^= ((unsigned int)h1) >> 13; | |
163 h1 *= 0xc2b2ae35; | |
164 h1 ^= ((unsigned int)h1) >> 16; | |
165 | |
166 return h1; | |
167 } | |
168 | |
169 // Hash used for the seed. | |
170 jint AltHashing::murmur3_32(jint seed, const int* data, int len) { | |
171 jint h1 = seed; | |
172 | |
173 int off = 0; | |
174 int end = len; | |
175 | |
176 // body | |
177 while (off < end) { | |
178 jint k1 = 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 ^= ((juint)h1) >> 16; | |
197 h1 *= 0x85ebca6b; | |
198 h1 ^= ((juint)h1) >> 13; | |
199 h1 *= 0xc2b2ae35; | |
200 h1 ^= ((juint)h1) >> 16; | |
201 | |
202 return h1; | |
203 } | |
204 | |
205 jint AltHashing::murmur3_32(const int* data, int len) { | |
206 return murmur3_32(0, data, len); | |
207 } | |
208 | |
209 #ifndef PRODUCT | |
210 // Overloaded versions for internal test. | |
211 jint AltHashing::murmur3_32(const jbyte* data, int len) { | |
212 return murmur3_32(0, data, len); | |
213 } | |
214 | |
215 jint AltHashing::murmur3_32(const jchar* data, int len) { | |
216 return murmur3_32(0, data, len); | |
217 } | |
218 | |
219 // Internal test for alternate hashing. Translated from JDK version | |
220 // test/sun/misc/Hashing.java | |
221 static const jbyte ONE_BYTE[] = { (jbyte) 0x80}; | |
222 static const jbyte TWO_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81}; | |
223 static const jchar ONE_CHAR[] = { (jchar) 0x8180}; | |
224 static const jbyte THREE_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82}; | |
225 static const jbyte FOUR_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, (jbyte) 0x83}; | |
226 static const jchar TWO_CHAR[] = { (jchar) 0x8180, (jchar) 0x8382}; | |
227 static const jint ONE_INT[] = { 0x83828180}; | |
228 static const jbyte SIX_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, (jbyte) 0x83, (jbyte) 0x84, (jbyte) 0x85}; | |
229 static const jchar THREE_CHAR[] = { (jchar) 0x8180, (jchar) 0x8382, (jchar) 0x8584}; | |
230 static const jbyte EIGHT_BYTE[] = { | |
231 (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, | |
232 (jbyte) 0x83, (jbyte) 0x84, (jbyte) 0x85, | |
233 (jbyte) 0x86, (jbyte) 0x87}; | |
234 static const jchar FOUR_CHAR[] = { | |
235 (jchar) 0x8180, (jchar) 0x8382, | |
236 (jchar) 0x8584, (jchar) 0x8786}; | |
237 | |
238 static const jint TWO_INT[] = { 0x83828180, 0x87868584}; | |
239 | |
240 static const juint MURMUR3_32_X86_CHECK_VALUE = 0xB0F57EE3; | |
241 | |
242 void AltHashing::testMurmur3_32_ByteArray() { | |
243 // printf("testMurmur3_32_ByteArray\n"); | |
244 | |
245 jbyte* vector = new jbyte[256]; | |
246 jbyte* hashes = new jbyte[4 * 256]; | |
247 | |
248 for (int i = 0; i < 256; i++) { | |
249 vector[i] = (jbyte) i; | |
250 } | |
251 | |
252 // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255} | |
253 for (int i = 0; i < 256; i++) { | |
254 jint hash = murmur3_32(256 - i, vector, i); | |
255 hashes[i * 4] = (jbyte) hash; | |
256 hashes[i * 4 + 1] = (jbyte) (((juint)hash) >> 8); | |
257 hashes[i * 4 + 2] = (jbyte) (((juint)hash) >> 16); | |
258 hashes[i * 4 + 3] = (jbyte) (((juint)hash) >> 24); | |
259 } | |
260 | |
261 // hash to get const result. | |
262 juint final_hash = murmur3_32(hashes, 4*256); | |
263 | |
264 assert (MURMUR3_32_X86_CHECK_VALUE == final_hash, | |
265 err_msg( | |
266 "Calculated hash result not as expected. Expected %08X got %08X\n", | |
267 MURMUR3_32_X86_CHECK_VALUE, | |
268 final_hash)); | |
269 } | |
270 | |
271 void AltHashing::testEquivalentHashes() { | |
272 jint jbytes, jchars, ints; | |
273 | |
274 // printf("testEquivalentHashes\n"); | |
275 | |
276 jbytes = murmur3_32(TWO_BYTE, 2); | |
277 jchars = murmur3_32(ONE_CHAR, 1); | |
278 assert (jbytes == jchars, | |
279 err_msg("Hashes did not match. b:%08x != c:%08x\n", jbytes, jchars)); | |
280 | |
281 jbytes = murmur3_32(FOUR_BYTE, 4); | |
282 jchars = murmur3_32(TWO_CHAR, 2); | |
283 ints = murmur3_32(ONE_INT, 1); | |
284 assert ((jbytes == jchars) && (jbytes == ints), | |
285 err_msg("Hashes did not match. b:%08x != c:%08x != i:%08x\n", jbytes, jchars, ints)); | |
286 | |
287 jbytes = murmur3_32(SIX_BYTE, 6); | |
288 jchars = murmur3_32(THREE_CHAR, 3); | |
289 assert (jbytes == jchars, | |
290 err_msg("Hashes did not match. b:%08x != c:%08x\n", jbytes, jchars)); | |
291 | |
292 jbytes = murmur3_32(EIGHT_BYTE, 8); | |
293 jchars = murmur3_32(FOUR_CHAR, 4); | |
294 ints = murmur3_32(TWO_INT, 2); | |
295 assert ((jbytes == jchars) && (jbytes == ints), | |
296 err_msg("Hashes did not match. b:%08x != c:%08x != i:%08x\n", jbytes, jchars, ints)); | |
297 } | |
298 | |
299 // Returns true if the alternate hashcode is correct | |
300 void AltHashing::test_alt_hash() { | |
301 testMurmur3_32_ByteArray(); | |
302 testEquivalentHashes(); | |
303 } | |
304 #endif // PRODUCT |