1 /* 2 * Copyright (c) 2018, Red Hat, Inc. All rights reserved. 3 * Copyright (c) 2022, Oracle and/or its affiliates. All rights reserved. 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25 package test.java.util.HashMap; 26 27 import org.testng.annotations.DataProvider; 28 import org.testng.annotations.Test; 29 30 import java.lang.invoke.MethodHandle; 31 import java.lang.invoke.MethodHandles; 32 import java.lang.invoke.MethodType; 33 import java.lang.invoke.VarHandle; 34 import java.util.AbstractMap; 35 import java.util.AbstractSet; 36 import java.util.ArrayList; 37 import java.util.Arrays; 38 import java.util.HashMap; 39 import java.util.HashSet; 40 import java.util.Iterator; 41 import java.util.LinkedHashMap; 42 import java.util.LinkedHashSet; 43 import java.util.List; 44 import java.util.Map; 45 import java.util.Set; 46 import java.util.WeakHashMap; 47 import java.util.function.Consumer; 48 import java.util.function.IntFunction; 49 import java.util.function.Supplier; 50 51 import static org.testng.Assert.assertEquals; 52 import static org.testng.Assert.assertNull; 53 import static org.testng.Assert.assertThrows; 54 55 /* 56 * @test 57 * @bug 8186958 8210280 8281631 8285386 8284780 58 * @modules java.base/java.util:open 59 * @summary White box tests for HashMap-related internals around table sizing 60 * @run testng/othervm -Xmx2g WhiteBoxResizeTest 61 */ 62 public class WhiteBoxResizeTest { 63 64 final MethodHandle TABLE_SIZE_FOR; 65 final VarHandle HM_TABLE; 66 final VarHandle WHM_TABLE; 67 final VarHandle HS_MAP; 68 WhiteBoxResizeTest()69 public WhiteBoxResizeTest() throws ReflectiveOperationException { 70 MethodHandles.Lookup hmlookup = MethodHandles.privateLookupIn(HashMap.class, MethodHandles.lookup()); 71 TABLE_SIZE_FOR = hmlookup.findStatic( 72 HashMap.class, "tableSizeFor", MethodType.methodType(int.class, int.class)); 73 HM_TABLE = hmlookup.unreflectVarHandle(HashMap.class.getDeclaredField("table")); 74 75 MethodHandles.Lookup whmlookup = MethodHandles.privateLookupIn(WeakHashMap.class, MethodHandles.lookup()); 76 WHM_TABLE = whmlookup.unreflectVarHandle(WeakHashMap.class.getDeclaredField("table")); 77 78 MethodHandles.Lookup hslookup = MethodHandles.privateLookupIn(HashSet.class, MethodHandles.lookup()); 79 HS_MAP = hslookup.unreflectVarHandle(HashSet.class.getDeclaredField("map")); 80 } 81 82 /* 83 * utility methods 84 */ 85 tableSizeFor(int n)86 int tableSizeFor(int n) { 87 try { 88 return (int) TABLE_SIZE_FOR.invoke(n); 89 } catch (Throwable t) { 90 throw new AssertionError(t); 91 } 92 } 93 table(Map<?, ?> map)94 Object[] table(Map<?, ?> map) { 95 try { 96 VarHandle vh = map instanceof WeakHashMap ? WHM_TABLE : HM_TABLE; 97 return (Object[]) vh.get(map); 98 } catch (Throwable t) { 99 throw new AssertionError(t); 100 } 101 } 102 capacity(Map<?, ?> map)103 int capacity(Map<?, ?> map) { 104 return table(map).length; 105 } 106 107 // creates a map with size mappings makeMap(int size)108 Map<String, String> makeMap(int size) { 109 Map<String, String> map = new HashMap<>(); 110 putN(map, size); 111 return map; 112 } 113 114 // creates a "fake" map: size() returns the given size, but 115 // the entrySet iterator returns only one entry fakeMap(int size)116 Map<String, String> fakeMap(int size) { 117 return new AbstractMap<>() { 118 public Set<Map.Entry<String, String>> entrySet() { 119 return new AbstractSet<Map.Entry<String, String>>() { 120 public int size() { 121 return size; 122 } 123 124 public Iterator<Map.Entry<String, String>> iterator() { 125 return Set.of(Map.entry("1", "1")).iterator(); 126 } 127 }; 128 } 129 }; 130 } 131 132 void putN(Map<String, String> map, int n) { 133 for (int i = 0; i < n; i++) { 134 String string = Integer.toString(i); 135 map.put(string, string); 136 } 137 } 138 139 /* 140 * tests of tableSizeFor 141 */ 142 143 @DataProvider(name = "tableSizeFor") 144 public Object[][] tableSizeForCases() { 145 final int MAX = 1 << 30; 146 return new Object[][] { 147 // tableSizeFor(arg), expected 148 { 0, 1 }, 149 { 1, 1 }, 150 { 2, 2 }, 151 { 3, 4 }, 152 { 4, 4 }, 153 { 5, 8 }, 154 { 15, 16 }, 155 { 16, 16 }, 156 { 17, 32 }, 157 { MAX-1, MAX }, 158 { MAX, MAX }, 159 { MAX+1, MAX }, 160 { Integer.MAX_VALUE, MAX } 161 }; 162 } 163 164 @Test(dataProvider = "tableSizeFor") 165 public void tableSizeFor(int arg, int expected) { 166 assertEquals(tableSizeFor(arg), expected); 167 } 168 169 /* 170 * tests for lazy table allocation 171 */ 172 173 @DataProvider(name = "lazy") 174 public Object[][] lazyTableAllocationCases() { 175 return new Object[][]{ 176 {new HashMap<>()}, 177 // { new WeakHashMap<>() }, // WHM doesn't allocate lazily 178 {new LinkedHashMap<>()} 179 }; 180 } 181 182 @Test(dataProvider = "lazy") 183 public void lazyTableAllocation(Map<?, ?> map) { 184 assertNull(table(map)); 185 } 186 187 /* 188 * tests for default capacity (no-arg constructor) 189 */ 190 191 @DataProvider(name = "defaultCapacity") 192 public Object[][] defaultCapacityCases() { 193 return new Supplier<?>[][]{ 194 {() -> new HashMap<>()}, 195 {() -> new LinkedHashMap<>()}, 196 {() -> new WeakHashMap<>()} 197 }; 198 } 199 200 @Test(dataProvider = "defaultCapacity") 201 public void defaultCapacity(Supplier<Map<String, String>> s) { 202 Map<String, String> map = s.get(); 203 map.put("", ""); 204 assertEquals(capacity(map), 16); 205 } 206 207 /* 208 * tests for requested capacity (int and int+float constructors) 209 */ 210 211 @DataProvider(name = "requestedCapacity") 212 public Iterator<Object[]> requestedCapacityCases() { 213 ArrayList<Object[]> cases = new ArrayList<>(); 214 for (int i = 2; i < 64; i++) { 215 int cap = i; 216 cases.add(new Object[]{"rhm1", cap, (Supplier<Map<String, String>>) () -> new HashMap<>(cap)}); 217 cases.add(new Object[]{"rhm2", cap, (Supplier<Map<String, String>>) () -> new HashMap<>(cap, 0.75f)}); 218 cases.add(new Object[]{"rlm1", cap, (Supplier<Map<String, String>>) () -> new LinkedHashMap<>(cap)}); 219 cases.add(new Object[]{"rlm2", cap, (Supplier<Map<String, String>>) () -> new LinkedHashMap<>(cap, 0.75f)}); 220 cases.add(new Object[]{"rwm1", cap, (Supplier<Map<String, String>>) () -> new WeakHashMap<>(cap)}); 221 cases.add(new Object[]{"rwm2", cap, (Supplier<Map<String, String>>) () -> new WeakHashMap<>(cap, 0.75f)}); 222 } 223 return cases.iterator(); 224 } 225 226 @Test(dataProvider = "requestedCapacity") 227 public void requestedCapacity(String label, int cap, Supplier<Map<String, String>> s) { 228 Map<String, String> map = s.get(); 229 map.put("", ""); 230 assertEquals(capacity(map), tableSizeFor(cap)); 231 } 232 233 /* 234 * Tests for capacity after map is populated with a given number N of mappings. 235 * Maps are populated using a copy constructor on a map with N mappings, 236 * other constructors followed by N put() calls, and other constructors followed 237 * by putAll() on a map with N mappings. 238 * 239 * String labels encode the test case for ease of diagnosis if one of the test cases fails. 240 * For example, "plm2pn" is "populated LinkedHashMap, 2-arg constructor, followed by putN". 241 */ 242 243 // helper method for one populated capacity case, to provide target types for lambdas 244 Object[] pcc(String label, 245 int size, 246 int expectedCapacity, 247 Supplier<Map<String, String>> supplier, 248 Consumer<Map<String, String>> consumer) { 249 return new Object[]{label, size, expectedCapacity, supplier, consumer}; 250 } 251 252 List<Object[]> genPopulatedCapacityCases(int size, int cap) { 253 return Arrays.asList( 254 pcc("phmcpy", size, cap, () -> new HashMap<>(makeMap(size)), map -> { }), 255 pcc("phm0pn", size, cap, () -> new HashMap<>(), map -> { putN(map, size); }), 256 pcc("phm1pn", size, cap, () -> new HashMap<>(cap), map -> { putN(map, size); }), 257 pcc("phm2pn", size, cap, () -> new HashMap<>(cap, 0.75f), map -> { putN(map, size); }), 258 pcc("phm0pa", size, cap, () -> new HashMap<>(), map -> { map.putAll(makeMap(size)); }), 259 pcc("phm1pa", size, cap, () -> new HashMap<>(cap), map -> { map.putAll(makeMap(size)); }), 260 pcc("phm2pa", size, cap, () -> new HashMap<>(cap, 0.75f), map -> { map.putAll(makeMap(size)); }), 261 262 pcc("plmcpy", size, cap, () -> new LinkedHashMap<>(makeMap(size)), map -> { }), 263 pcc("plm0pn", size, cap, () -> new LinkedHashMap<>(), map -> { putN(map, size); }), 264 pcc("plm1pn", size, cap, () -> new LinkedHashMap<>(cap), map -> { putN(map, size); }), 265 pcc("plm2pn", size, cap, () -> new LinkedHashMap<>(cap, 0.75f), map -> { putN(map, size); }), 266 pcc("plm0pa", size, cap, () -> new LinkedHashMap<>(), map -> { map.putAll(makeMap(size)); }), 267 pcc("plm1pa", size, cap, () -> new LinkedHashMap<>(cap), map -> { map.putAll(makeMap(size)); }), 268 pcc("plm2pa", size, cap, () -> new LinkedHashMap<>(cap, 0.75f), map -> { map.putAll(makeMap(size)); }), 269 270 pcc("pwmcpy", size, cap, () -> new WeakHashMap<>(makeMap(size)), map -> { }), 271 pcc("pwm0pn", size, cap, () -> new WeakHashMap<>(), map -> { putN(map, size); }), 272 pcc("pwm1pn", size, cap, () -> new WeakHashMap<>(cap), map -> { putN(map, size); }), 273 pcc("pwm2pn", size, cap, () -> new WeakHashMap<>(cap, 0.75f), map -> { putN(map, size); }), 274 pcc("pwm0pa", size, cap, () -> new WeakHashMap<>(), map -> { map.putAll(makeMap(size)); }), 275 pcc("pwm1pa", size, cap, () -> new WeakHashMap<>(cap), map -> { map.putAll(makeMap(size)); }), 276 pcc("pwm2pa", size, cap, () -> new WeakHashMap<>(cap, 0.75f), map -> { map.putAll(makeMap(size)); }) 277 ); 278 } 279 280 List<Object[]> genFakePopulatedCapacityCases(int size, int cap) { 281 return Arrays.asList( 282 pcc("fhmcpy", size, cap, () -> new HashMap<>(fakeMap(size)), map -> { }), 283 pcc("fhm0pa", size, cap, () -> new HashMap<>(), map -> { map.putAll(fakeMap(size)); }), 284 pcc("fhm1pa", size, cap, () -> new HashMap<>(cap), map -> { map.putAll(fakeMap(size)); }), 285 pcc("fhm2pa", size, cap, () -> new HashMap<>(cap, 0.75f), map -> { map.putAll(fakeMap(size)); }), 286 287 pcc("flmcpy", size, cap, () -> new LinkedHashMap<>(fakeMap(size)), map -> { }), 288 pcc("flm0pa", size, cap, () -> new LinkedHashMap<>(), map -> { map.putAll(fakeMap(size)); }), 289 pcc("flm1pa", size, cap, () -> new LinkedHashMap<>(cap), map -> { map.putAll(fakeMap(size)); }), 290 pcc("flm2pa", size, cap, () -> new LinkedHashMap<>(cap, 0.75f), map -> { map.putAll(fakeMap(size)); }), 291 292 pcc("fwmcpy", size, cap, () -> new WeakHashMap<>(fakeMap(size)), map -> { }), 293 // pcc("fwm0pa", size, cap, () -> new WeakHashMap<>(), map -> { map.putAll(fakeMap(size)); }), // see note 294 pcc("fwm1pa", size, cap, () -> new WeakHashMap<>(cap), map -> { map.putAll(fakeMap(size)); }), 295 pcc("fwm2pa", size, cap, () -> new WeakHashMap<>(cap, 0.75f), map -> { map.putAll(fakeMap(size)); }) 296 ); 297 298 // Test case "fwm0pa" is commented out because WeakHashMap uses a different allocation 299 // policy from the other map implementations: it deliberately under-allocates in this case. 300 } 301 302 @DataProvider(name = "populatedCapacity") 303 public Iterator<Object[]> populatedCapacityCases() { 304 ArrayList<Object[]> cases = new ArrayList<>(); 305 cases.addAll(genPopulatedCapacityCases(12, 16)); 306 cases.addAll(genPopulatedCapacityCases(13, 32)); 307 cases.addAll(genPopulatedCapacityCases(24, 32)); 308 cases.addAll(genPopulatedCapacityCases(25, 64)); 309 cases.addAll(genPopulatedCapacityCases(48, 64)); 310 cases.addAll(genPopulatedCapacityCases(49, 128)); 311 312 // numbers in this range are truncated by a float computation with 0.75f 313 // but can get an exact result with a double computation with 0.75d 314 // Android-removed: cause OOM. 315 // cases.addAll(genFakePopulatedCapacityCases(25165824, 33554432)); 316 // cases.addAll(genFakePopulatedCapacityCases(25165825, 67108864)); 317 // cases.addAll(genFakePopulatedCapacityCases(50331648, 67108864)); 318 // cases.addAll(genFakePopulatedCapacityCases(50331649, 134217728)); 319 320 return cases.iterator(); 321 } 322 323 @Test(dataProvider = "populatedCapacity") 324 public void populatedCapacity(String label, // unused, included for diagnostics 325 int size, // unused, included for diagnostics 326 int expectedCapacity, 327 Supplier<Map<String, String>> s, 328 Consumer<Map<String, String>> c) { 329 Map<String, String> map = s.get(); 330 c.accept(map); 331 assertEquals(capacity(map), expectedCapacity); 332 } 333 334 /* 335 * tests for requested size (static factory methods) 336 */ 337 338 // helper method for one requested size case, to provide target types for lambda 339 Object[] rsc(String label, 340 int size, 341 int expectedCapacity, 342 Supplier<Capacitiable> supplier) { 343 return new Object[]{label, size, expectedCapacity, supplier}; 344 } 345 346 List<Object[]> genRequestedSizeCases(int size, int cap) { 347 return Arrays.asList( 348 rsc("rshm", size, cap, () -> new MapCapacitiable(HashMap.newHashMap(size))), 349 rsc("rslm", size, cap, () -> new MapCapacitiable(LinkedHashMap.newLinkedHashMap(size))), 350 rsc("rswm", size, cap, () -> new MapCapacitiable(WeakHashMap.newWeakHashMap(size))), 351 rsc("rshs", size, cap, () -> new SetCapacitiable(HashSet.newHashSet(size))), 352 rsc("rsls", size, cap, () -> new SetCapacitiable(LinkedHashSet.newLinkedHashSet(size))) 353 ); 354 } 355 356 @DataProvider(name = "requestedSize") 357 public Iterator<Object[]> requestedSizeCases() { 358 ArrayList<Object[]> cases = new ArrayList<>(); 359 cases.addAll(genRequestedSizeCases(12, 16)); 360 cases.addAll(genRequestedSizeCases(13, 32)); 361 cases.addAll(genRequestedSizeCases(24, 32)); 362 cases.addAll(genRequestedSizeCases(25, 64)); 363 cases.addAll(genRequestedSizeCases(48, 64)); 364 cases.addAll(genRequestedSizeCases(49, 128)); 365 366 // numbers in this range are truncated by a float computation with 0.75f 367 // but can get an exact result with a double computation with 0.75d 368 // Android-removed: cause OOM. 369 // cases.addAll(genRequestedSizeCases(25165824, 33554432)); 370 // cases.addAll(genRequestedSizeCases(25165825, 67108864)); 371 // cases.addAll(genRequestedSizeCases(50331648, 67108864)); 372 // cases.addAll(genRequestedSizeCases(50331649, 134217728)); 373 374 return cases.iterator(); 375 } 376 377 @Test(dataProvider = "requestedSize") 378 public void requestedSize(String label, // unused, included for diagnostics 379 int size, // unused, included for diagnostics 380 int expectedCapacity, 381 Supplier<Capacitiable> s) { 382 Capacitiable capacitiable = s.get(); 383 capacitiable.init(); 384 assertEquals(capacitiable.capacity(), expectedCapacity); 385 } 386 387 interface Capacitiable { 388 389 void init(); 390 391 int capacity(); 392 393 } 394 395 class MapCapacitiable implements Capacitiable { 396 397 private final Map<String, String> content; 398 399 public MapCapacitiable(Map<String, String> content) { 400 this.content = content; 401 } 402 403 @Override 404 public void init() { 405 content.put("", ""); 406 } 407 408 @Override 409 public int capacity() { 410 return table(content).length; 411 } 412 } 413 414 class SetCapacitiable implements Capacitiable { 415 416 private final Set<String> content; 417 418 public SetCapacitiable(Set<String> content) { 419 this.content = content; 420 } 421 422 @Override 423 public void init() { 424 content.add(""); 425 } 426 427 @Override 428 public int capacity() { 429 HashMap<?, ?> hashMap = (HashMap<?, ?>) HS_MAP.get(content); 430 return table(hashMap).length; 431 } 432 } 433 434 @DataProvider(name = "negativeNumMappings") 435 public Iterator<Object[]> negativeNumMappings() { 436 final List<Object[]> methods = new ArrayList<>(); 437 methods.add(new Object[] {(IntFunction<?>) HashMap::newHashMap, "HashMap::newHashMap"}); 438 methods.add(new Object[] {(IntFunction<?>) LinkedHashMap::newLinkedHashMap, 439 "LinkedHashMap::newLinkedHashMap"}); 440 methods.add(new Object[] {(IntFunction<?>) WeakHashMap::newWeakHashMap, 441 "WeakHashMap::newWeakHashMap"}); 442 methods.add(new Object[] {(IntFunction<?>) HashSet::newHashSet, "HashSet::newHashSet"}); 443 methods.add(new Object[] {(IntFunction<?>) LinkedHashSet::newLinkedHashSet, 444 "LinkedHashSet::newLinkedHashSet"}); 445 return methods.iterator(); 446 } 447 448 /** 449 * Tests that the APIs that take {@code numMappings} or {@code numElements} as a parameter for 450 * creating the collection instance (for example: {@link HashMap#newHashMap(int)}), throw 451 * an {@code IllegalArgumentException} when a negative value is passed to them 452 */ 453 @Test(dataProvider = "negativeNumMappings") 454 public void testNegativeNumMappings(final IntFunction<?> method, final String methodName) { 455 assertThrows(IllegalArgumentException.class, () -> method.apply(-1)); 456 } 457 } 458