1 /*
  2  * Copyright (c) 2018, Red Hat, Inc. All rights reserved.
  3  * Copyright (c) 2022, 2024, 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 import org.testng.annotations.DataProvider;
 26 import org.testng.annotations.Test;
 27 
 28 import java.lang.invoke.MethodHandle;
 29 import java.lang.invoke.MethodHandles;
 30 import java.lang.invoke.MethodType;
 31 import java.lang.invoke.VarHandle;
 32 import java.util.AbstractMap;
 33 import java.util.AbstractSet;
 34 import java.util.ArrayList;
 35 import java.util.Arrays;
 36 import java.util.HashMap;
 37 import java.util.HashSet;
 38 import java.util.Iterator;
 39 import java.util.LinkedHashMap;
 40 import java.util.LinkedHashSet;
 41 import java.util.List;
 42 import java.util.Map;
 43 import java.util.Set;
 44 import java.util.WeakHashMap;
 45 import java.util.function.Consumer;
 46 import java.util.function.IntFunction;
 47 import java.util.function.Supplier;
 48 
 49 import static org.testng.Assert.assertEquals;
 50 import static org.testng.Assert.assertNull;
 51 import static org.testng.Assert.assertThrows;
 52 
 53 /*
 54  * @test
 55  * @bug 8186958 8210280 8281631 8285386 8284780
 56  * @modules java.base/java.util:open
 57  * @summary White box tests for HashMap-related internals around table sizing
 58  * @comment skip running this test on 32 bit VM
 59  * @requires vm.bits == "64"
 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 
 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 
 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 
 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 
103     int capacity(Map<?, ?> map) {
104         return table(map).length;
105     }
106 
107     // creates a map with size mappings
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
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         cases.addAll(genFakePopulatedCapacityCases(25165824,  33554432));
315         cases.addAll(genFakePopulatedCapacityCases(25165825,  67108864));
316         cases.addAll(genFakePopulatedCapacityCases(50331648,  67108864));
317         cases.addAll(genFakePopulatedCapacityCases(50331649, 134217728));
318 
319         return cases.iterator();
320     }
321 
322     @Test(dataProvider = "populatedCapacity")
323     public void populatedCapacity(String label, // unused, included for diagnostics
324                                   int size,     // unused, included for diagnostics
325                                   int expectedCapacity,
326                                   Supplier<Map<String, String>> s,
327                                   Consumer<Map<String, String>> c) {
328         Map<String, String> map = s.get();
329         c.accept(map);
330         assertEquals(capacity(map), expectedCapacity);
331     }
332 
333     /*
334      * tests for requested size (static factory methods)
335      */
336 
337     // helper method for one requested size case, to provide target types for lambda
338     Object[] rsc(String label,
339                  int size,
340                  int expectedCapacity,
341                  Supplier<Capacitiable> supplier) {
342         return new Object[]{label, size, expectedCapacity, supplier};
343     }
344 
345     List<Object[]> genRequestedSizeCases(int size, int cap) {
346         return Arrays.asList(
347                 rsc("rshm", size, cap, () -> new MapCapacitiable(HashMap.newHashMap(size))),
348                 rsc("rslm", size, cap, () -> new MapCapacitiable(LinkedHashMap.newLinkedHashMap(size))),
349                 rsc("rswm", size, cap, () -> new MapCapacitiable(WeakHashMap.newWeakHashMap(size))),
350                 rsc("rshs", size, cap, () -> new SetCapacitiable(HashSet.newHashSet(size))),
351                 rsc("rsls", size, cap, () -> new SetCapacitiable(LinkedHashSet.newLinkedHashSet(size)))
352         );
353     }
354 
355     @DataProvider(name = "requestedSize")
356     public Iterator<Object[]> requestedSizeCases() {
357         ArrayList<Object[]> cases = new ArrayList<>();
358         cases.addAll(genRequestedSizeCases(12,  16));
359         cases.addAll(genRequestedSizeCases(13,  32));
360         cases.addAll(genRequestedSizeCases(24,  32));
361         cases.addAll(genRequestedSizeCases(25,  64));
362         cases.addAll(genRequestedSizeCases(48,  64));
363         cases.addAll(genRequestedSizeCases(49, 128));
364 
365         // numbers in this range are truncated by a float computation with 0.75f
366         // but can get an exact result with a double computation with 0.75d
367         cases.addAll(genRequestedSizeCases(25165824,  33554432));
368         cases.addAll(genRequestedSizeCases(25165825,  67108864));
369         cases.addAll(genRequestedSizeCases(50331648,  67108864));
370         cases.addAll(genRequestedSizeCases(50331649, 134217728));
371 
372         return cases.iterator();
373     }
374 
375     @Test(dataProvider = "requestedSize")
376     public void requestedSize(String label,  // unused, included for diagnostics
377                               int size,      // unused, included for diagnostics
378                               int expectedCapacity,
379                               Supplier<Capacitiable> s) {
380         Capacitiable capacitiable = s.get();
381         capacitiable.init();
382         assertEquals(capacitiable.capacity(), expectedCapacity);
383     }
384 
385     interface Capacitiable {
386 
387         void init();
388 
389         int capacity();
390 
391     }
392 
393     class MapCapacitiable implements Capacitiable {
394 
395         private final Map<String, String> content;
396 
397         public MapCapacitiable(Map<String, String> content) {
398             this.content = content;
399         }
400 
401         @Override
402         public void init() {
403             content.put("", "");
404         }
405 
406         @Override
407         public int capacity() {
408             return table(content).length;
409         }
410     }
411 
412     class SetCapacitiable implements Capacitiable {
413 
414         private final Set<String> content;
415 
416         public SetCapacitiable(Set<String> content) {
417             this.content = content;
418         }
419 
420         @Override
421         public void init() {
422             content.add("");
423         }
424 
425         @Override
426         public int capacity() {
427             HashMap<?, ?> hashMap = (HashMap<?, ?>) HS_MAP.get(content);
428             return table(hashMap).length;
429         }
430     }
431 
432     @DataProvider(name = "negativeNumMappings")
433     public Iterator<Object[]> negativeNumMappings() {
434         final List<Object[]> methods = new ArrayList<>();
435         methods.add(new Object[] {(IntFunction<?>) HashMap::newHashMap, "HashMap::newHashMap"});
436         methods.add(new Object[] {(IntFunction<?>) LinkedHashMap::newLinkedHashMap,
437                 "LinkedHashMap::newLinkedHashMap"});
438         methods.add(new Object[] {(IntFunction<?>) WeakHashMap::newWeakHashMap,
439                 "WeakHashMap::newWeakHashMap"});
440         methods.add(new Object[] {(IntFunction<?>) HashSet::newHashSet, "HashSet::newHashSet"});
441         methods.add(new Object[] {(IntFunction<?>) LinkedHashSet::newLinkedHashSet,
442                 "LinkedHashSet::newLinkedHashSet"});
443         return methods.iterator();
444     }
445 
446     /**
447      * Tests that the APIs that take {@code numMappings} or {@code numElements} as a parameter for
448      * creating the collection instance (for example: {@link HashMap#newHashMap(int)}), throw
449      * an {@code IllegalArgumentException} when a negative value is passed to them
450      */
451     @Test(dataProvider = "negativeNumMappings")
452     public void testNegativeNumMappings(final IntFunction<?> method, final String methodName) {
453         assertThrows(IllegalArgumentException.class, () -> method.apply(-1));
454     }
455 }