1 /*
   2  * Copyright (c) 2014, 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  * Common code for string deduplication tests
  26  */
  27 
  28 import java.lang.management.*;
  29 import java.lang.reflect.*;
  30 import java.security.*;
  31 import java.util.*;
  32 import com.oracle.java.testlibrary.*;
  33 import sun.misc.*;
  34 
  35 class TestStringDeduplicationTools {
  36     private static final String YoungGC = "YoungGC";
  37     private static final String FullGC  = "FullGC";
  38 
  39     private static final int Xmn = 50;  // MB
  40     private static final int Xms = 100; // MB
  41     private static final int Xmx = 100; // MB
  42     private static final int MB = 1024 * 1024;
  43     private static final int StringLength = 50;
  44 
  45     private static Field valueField;
  46     private static Unsafe unsafe;
  47     private static byte[] dummy;
  48 
  49     static {
  50         try {
  51             Field field = Unsafe.class.getDeclaredField("theUnsafe");
  52             field.setAccessible(true);
  53             unsafe = (Unsafe)field.get(null);
  54 
  55             valueField = String.class.getDeclaredField("value");
  56             valueField.setAccessible(true);
  57         } catch (Exception e) {
  58             throw new RuntimeException(e);
  59         }
  60     }
  61 
  62     private static Object getValue(String string) {
  63         try {
  64             return valueField.get(string);
  65         } catch (Exception e) {
  66             throw new RuntimeException(e);
  67         }
  68     }
  69 
  70     private static void doFullGc(int numberOfTimes) {
  71         for (int i = 0; i < numberOfTimes; i++) {
  72             System.out.println("Begin: Full GC " + (i + 1) + "/" + numberOfTimes);
  73             System.gc();
  74             System.out.println("End: Full GC " + (i + 1) + "/" + numberOfTimes);
  75         }
  76     }
  77 
  78     private static void doYoungGc(int numberOfTimes) {
  79         // Provoke at least numberOfTimes young GCs
  80         final int objectSize = 128;
  81         final int maxObjectInYoung = (Xmn * MB) / objectSize;
  82         for (int i = 0; i < numberOfTimes; i++) {
  83             System.out.println("Begin: Young GC " + (i + 1) + "/" + numberOfTimes);
  84             for (int j = 0; j < maxObjectInYoung + 1; j++) {
  85                 dummy = new byte[objectSize];
  86             }
  87             System.out.println("End: Young GC " + (i + 1) + "/" + numberOfTimes);
  88         }
  89     }
  90 
  91     private static void forceDeduplication(int ageThreshold, String gcType) {
  92         // Force deduplication to happen by either causing a FullGC or a YoungGC.
  93         // We do several collections to also provoke a situation where the the
  94         // deduplication thread needs to yield while processing the queue. This
  95         // also tests that the references in the deduplication queue are adjusted
  96         // accordingly.
  97         if (gcType.equals(FullGC)) {
  98             doFullGc(3);
  99         } else {
 100             doYoungGc(ageThreshold + 3);
 101         }
 102     }
 103 
 104     private static String generateString(int id) {
 105         StringBuilder builder = new StringBuilder(StringLength);
 106 
 107         builder.append("DeduplicationTestString:" + id + ":");
 108 
 109         while (builder.length() < StringLength) {
 110             builder.append('X');
 111         }
 112 
 113         return builder.toString();
 114     }
 115 
 116     private static ArrayList<String> createStrings(int total, int unique) {
 117         System.out.println("Creating strings: total=" + total + ", unique=" + unique);
 118         if (total % unique != 0) {
 119             throw new RuntimeException("Total must be divisible by unique");
 120         }
 121 
 122         ArrayList<String> list = new ArrayList<String>(total);
 123         for (int j = 0; j < total / unique; j++) {
 124             for (int i = 0; i < unique; i++) {
 125                 list.add(generateString(i));
 126             }
 127         }
 128 
 129         return list;
 130     }
 131 
 132     /**
 133      * Verifies that the given list contains expected number of unique strings.
 134      * It's possible that deduplication hasn't completed yet, so the method
 135      * will perform several attempts to check with a little pause between.
 136      * The method throws RuntimeException to signal that verification failed.
 137      *
 138      * @param list strings to check
 139      * @param uniqueExpected expected number of unique strings
 140      * @throws RuntimeException if check fails
 141      */
 142     private static void verifyStrings(ArrayList<String> list, int uniqueExpected) {
 143         boolean passed = false;
 144         for (int attempts = 0; attempts < 10; attempts++) {
 145             // Check number of deduplicated strings
 146             ArrayList<Object> unique = new ArrayList<Object>(uniqueExpected);
 147             for (String string: list) {
 148                 Object value = getValue(string);
 149                 boolean uniqueValue = true;
 150                 for (Object obj: unique) {
 151                     if (obj == value) {
 152                         uniqueValue = false;
 153                         break;
 154                     }
 155                 }
 156 
 157                 if (uniqueValue) {
 158                     unique.add(value);
 159                 }
 160             }
 161 
 162             System.out.println("Verifying strings: total=" + list.size() +
 163                                ", uniqueFound=" + unique.size() +
 164                                ", uniqueExpected=" + uniqueExpected);
 165 
 166             if (unique.size() == uniqueExpected) {
 167                 System.out.println("Deduplication completed (as fast as " + attempts + " iterations)");
 168                 passed = true;
 169                 break;
 170             } else {
 171                 System.out.println("Deduplication not completed, waiting...");
 172                 // Give the deduplication thread time to complete
 173                 try {
 174                     Thread.sleep(1000);
 175                 } catch (Exception e) {
 176                     throw new RuntimeException(e);
 177                 }
 178             }
 179         }
 180         if (!passed) {
 181             throw new RuntimeException("String verification failed");
 182         }
 183     }
 184 
 185     private static OutputAnalyzer runTest(String... extraArgs) throws Exception {
 186         String[] defaultArgs = new String[] {
 187             "-Xmn" + Xmn + "m",
 188             "-Xms" + Xms + "m",
 189             "-Xmx" + Xmx + "m",
 190             "-XX:+UseG1GC",
 191             "-XX:+UnlockDiagnosticVMOptions",
 192             "-XX:+VerifyAfterGC" // Always verify after GC
 193         };
 194 
 195         ArrayList<String> args = new ArrayList<String>();
 196         args.addAll(Arrays.asList(defaultArgs));
 197         args.addAll(Arrays.asList(extraArgs));
 198 
 199         ProcessBuilder pb = ProcessTools.createJavaProcessBuilder(args.toArray(new String[args.size()]));
 200         OutputAnalyzer output = new OutputAnalyzer(pb.start());
 201         System.err.println(output.getStderr());
 202         System.out.println(output.getStdout());
 203         return output;
 204     }
 205 
 206     private static class DeduplicationTest {
 207         public static void main(String[] args) {
 208             System.out.println("Begin: DeduplicationTest");
 209 
 210             final int numberOfStrings = Integer.parseUnsignedInt(args[0]);
 211             final int numberOfUniqueStrings = Integer.parseUnsignedInt(args[1]);
 212             final int ageThreshold = Integer.parseUnsignedInt(args[2]);
 213             final String gcType = args[3];
 214 
 215             ArrayList<String> list = createStrings(numberOfStrings, numberOfUniqueStrings);
 216             forceDeduplication(ageThreshold, gcType);
 217             verifyStrings(list, numberOfUniqueStrings);
 218 
 219             System.out.println("End: DeduplicationTest");
 220         }
 221 
 222         public static OutputAnalyzer run(int numberOfStrings, int ageThreshold, String gcType, String... extraArgs) throws Exception {
 223             String[] defaultArgs = new String[] {
 224                 "-XX:+UseStringDeduplication",
 225                 "-XX:StringDeduplicationAgeThreshold=" + ageThreshold,
 226                 DeduplicationTest.class.getName(),
 227                 "" + numberOfStrings,
 228                 "" + numberOfStrings / 2,
 229                 "" + ageThreshold,
 230                 gcType
 231             };
 232 
 233             ArrayList<String> args = new ArrayList<String>();
 234             args.addAll(Arrays.asList(extraArgs));
 235             args.addAll(Arrays.asList(defaultArgs));
 236 
 237             return runTest(args.toArray(new String[args.size()]));
 238         }
 239     }
 240 
 241     private static class InternedTest {
 242         public static void main(String[] args) {
 243             // This test verifies that interned strings are always
 244             // deduplicated when being interned, and never after
 245             // being interned.
 246 
 247             System.out.println("Begin: InternedTest");
 248 
 249             final int ageThreshold = Integer.parseUnsignedInt(args[0]);
 250             final String baseString = "DeduplicationTestString:" + InternedTest.class.getName();
 251 
 252             // Create duplicate of baseString
 253             StringBuilder sb1 = new StringBuilder(baseString);
 254             String dupString1 = sb1.toString();
 255             if (getValue(dupString1) == getValue(baseString)) {
 256                 throw new RuntimeException("Values should not match");
 257             }
 258 
 259             // Force baseString to be inspected for deduplication
 260             // and be inserted into the deduplication hashtable.
 261             forceDeduplication(ageThreshold, FullGC);
 262 
 263             // Wait for deduplication to occur
 264             for (int attempts = 0; attempts < 10; attempts++) {
 265                 if (getValue(dupString1) == getValue(baseString)) {
 266                     break;
 267                 }
 268                 System.out.println("Waiting...");
 269                 try {
 270                     Thread.sleep(1000);
 271                 } catch (Exception e) {
 272                     throw new RuntimeException(e);
 273                 }
 274             }
 275             if (getValue(dupString1) != getValue(baseString)) {
 276                 throw new RuntimeException("Deduplication has not occurred");
 277             }
 278 
 279             // Create a new duplicate of baseString
 280             StringBuilder sb2 = new StringBuilder(baseString);
 281             String dupString2 = sb2.toString();
 282             if (getValue(dupString2) == getValue(baseString)) {
 283                 throw new RuntimeException("Values should not match");
 284             }
 285 
 286             // Intern the new duplicate
 287             Object beforeInternedValue = getValue(dupString2);
 288             String internedString = dupString2.intern();
 289             if (internedString != dupString2) {
 290                 throw new RuntimeException("String should match");
 291             }
 292             if (getValue(internedString) != getValue(baseString)) {
 293                 throw new RuntimeException("Values should match");
 294             }
 295 
 296             // Check original value of interned string, to make sure
 297             // deduplication happened on the interned string and not
 298             // on the base string
 299             if (beforeInternedValue == getValue(baseString)) {
 300                 throw new RuntimeException("Values should not match");
 301             }
 302 
 303             System.out.println("End: InternedTest");
 304         }
 305 
 306         public static OutputAnalyzer run() throws Exception {
 307             return runTest("-XX:+PrintGC",
 308                            "-XX:+PrintGCDetails",
 309                            "-XX:+UseStringDeduplication",
 310                            "-XX:+PrintStringDeduplicationStatistics",
 311                            "-XX:StringDeduplicationAgeThreshold=" + DefaultAgeThreshold,
 312                            InternedTest.class.getName(),
 313                            "" + DefaultAgeThreshold);
 314         }
 315     }
 316 
 317     /*
 318      * Tests
 319      */
 320 
 321     private static final int LargeNumberOfStrings = 10000;
 322     private static final int SmallNumberOfStrings = 10;
 323 
 324     private static final int MaxAgeThreshold      = 31;
 325     private static final int DefaultAgeThreshold  = 3;
 326     private static final int MinAgeThreshold      = 1;
 327 
 328     private static final int TooLowAgeThreshold   = MinAgeThreshold - 1;
 329     private static final int TooHighAgeThreshold  = MaxAgeThreshold + 1;
 330 
 331     public static void testYoungGC() throws Exception {
 332         // Do young GC to age strings to provoke deduplication
 333         OutputAnalyzer output = DeduplicationTest.run(LargeNumberOfStrings,
 334                                                       DefaultAgeThreshold,
 335                                                       YoungGC,
 336                                                       "-XX:+PrintGC",
 337                                                       "-XX:+PrintStringDeduplicationStatistics");
 338         output.shouldNotContain("Full GC");
 339         output.shouldContain("GC pause (G1 Evacuation Pause) (young)");
 340         output.shouldContain("GC concurrent-string-deduplication");
 341         output.shouldContain("Deduplicated:");
 342         output.shouldHaveExitValue(0);
 343     }
 344 
 345     public static void testFullGC() throws Exception {
 346         // Do full GC to age strings to provoke deduplication
 347         OutputAnalyzer output = DeduplicationTest.run(LargeNumberOfStrings,
 348                                                       DefaultAgeThreshold,
 349                                                       FullGC,
 350                                                       "-XX:+PrintGC",
 351                                                       "-XX:+PrintStringDeduplicationStatistics");
 352         output.shouldNotContain("GC pause (G1 Evacuation Pause) (young)");
 353         output.shouldContain("Full GC");
 354         output.shouldContain("GC concurrent-string-deduplication");
 355         output.shouldContain("Deduplicated:");
 356         output.shouldHaveExitValue(0);
 357     }
 358 
 359     public static void testTableResize() throws Exception {
 360         // Test with StringDeduplicationResizeALot
 361         OutputAnalyzer output = DeduplicationTest.run(LargeNumberOfStrings,
 362                                                       DefaultAgeThreshold,
 363                                                       YoungGC,
 364                                                       "-XX:+PrintGC",
 365                                                       "-XX:+PrintStringDeduplicationStatistics",
 366                                                       "-XX:+StringDeduplicationResizeALot");
 367         output.shouldContain("GC concurrent-string-deduplication");
 368         output.shouldContain("Deduplicated:");
 369         output.shouldNotContain("Resize Count: 0");
 370         output.shouldHaveExitValue(0);
 371     }
 372 
 373     public static void testTableRehash() throws Exception {
 374         // Test with StringDeduplicationRehashALot
 375         OutputAnalyzer output = DeduplicationTest.run(LargeNumberOfStrings,
 376                                                       DefaultAgeThreshold,
 377                                                       YoungGC,
 378                                                       "-XX:+PrintGC",
 379                                                       "-XX:+PrintStringDeduplicationStatistics",
 380                                                       "-XX:+StringDeduplicationRehashALot");
 381         output.shouldContain("GC concurrent-string-deduplication");
 382         output.shouldContain("Deduplicated:");
 383         output.shouldNotContain("Rehash Count: 0");
 384         output.shouldNotContain("Hash Seed: 0x0");
 385         output.shouldHaveExitValue(0);
 386     }
 387 
 388     public static void testAgeThreshold() throws Exception {
 389         OutputAnalyzer output;
 390 
 391         // Test with max age theshold
 392         output = DeduplicationTest.run(SmallNumberOfStrings,
 393                                        MaxAgeThreshold,
 394                                        YoungGC,
 395                                        "-XX:+PrintGC",
 396                                        "-XX:+PrintStringDeduplicationStatistics");
 397         output.shouldContain("GC concurrent-string-deduplication");
 398         output.shouldContain("Deduplicated:");
 399         output.shouldHaveExitValue(0);
 400 
 401         // Test with min age theshold
 402         output = DeduplicationTest.run(SmallNumberOfStrings,
 403                                        MinAgeThreshold,
 404                                        YoungGC,
 405                                        "-XX:+PrintGC",
 406                                        "-XX:+PrintStringDeduplicationStatistics");
 407         output.shouldContain("GC concurrent-string-deduplication");
 408         output.shouldContain("Deduplicated:");
 409         output.shouldHaveExitValue(0);
 410 
 411         // Test with too low age threshold
 412         output = DeduplicationTest.run(SmallNumberOfStrings,
 413                                        TooLowAgeThreshold,
 414                                        YoungGC);
 415         output.shouldContain("StringDeduplicationAgeThreshold of " + TooLowAgeThreshold +
 416                              " is invalid; must be between " + MinAgeThreshold + " and " + MaxAgeThreshold);
 417         output.shouldHaveExitValue(1);
 418 
 419         // Test with too high age threshold
 420         output = DeduplicationTest.run(SmallNumberOfStrings,
 421                                        TooHighAgeThreshold,
 422                                        YoungGC);
 423         output.shouldContain("StringDeduplicationAgeThreshold of " + TooHighAgeThreshold +
 424                              " is invalid; must be between " + MinAgeThreshold + " and " + MaxAgeThreshold);
 425         output.shouldHaveExitValue(1);
 426     }
 427 
 428     public static void testPrintOptions() throws Exception {
 429         OutputAnalyzer output;
 430 
 431         // Test without PrintGC and without PrintStringDeduplicationStatistics
 432         output = DeduplicationTest.run(SmallNumberOfStrings,
 433                                        DefaultAgeThreshold,
 434                                        YoungGC);
 435         output.shouldNotContain("GC concurrent-string-deduplication");
 436         output.shouldNotContain("Deduplicated:");
 437         output.shouldHaveExitValue(0);
 438 
 439         // Test with PrintGC but without PrintStringDeduplicationStatistics
 440         output = DeduplicationTest.run(SmallNumberOfStrings,
 441                                        DefaultAgeThreshold,
 442                                        YoungGC,
 443                                        "-XX:+PrintGC");
 444         output.shouldContain("GC concurrent-string-deduplication");
 445         output.shouldNotContain("Deduplicated:");
 446         output.shouldHaveExitValue(0);
 447     }
 448 
 449     public static void testInterned() throws Exception {
 450         // Test that interned strings are deduplicated before being interned
 451         OutputAnalyzer output = InternedTest.run();
 452         output.shouldHaveExitValue(0);
 453     }
 454 }