changeset 55024:82fd8793ba5e

8218966: AArch64: String.compareTo() can read memory after string Reviewed-by: dsamersoff
author dpochepk
date Wed, 22 May 2019 20:39:04 +0300
parents cbc557f166f2
children 4cc9109caffd
files src/hotspot/cpu/aarch64/stubGenerator_aarch64.cpp test/hotspot/jtreg/compiler/intrinsics/string/TestStringCompareToDifferentLength.java test/hotspot/jtreg/compiler/intrinsics/string/TestStringCompareToSameLength.java
diffstat 3 files changed, 260 insertions(+), 46 deletions(-) [+]
line wrap: on
line diff
--- a/src/hotspot/cpu/aarch64/stubGenerator_aarch64.cpp	Wed May 22 20:12:19 2019 +0300
+++ b/src/hotspot/cpu/aarch64/stubGenerator_aarch64.cpp	Wed May 22 20:39:04 2019 +0300
@@ -4035,14 +4035,14 @@
         : "compare_long_string_different_encoding UL");
     address entry = __ pc();
     Label SMALL_LOOP, TAIL, TAIL_LOAD_16, LOAD_LAST, DIFF1, DIFF2,
-        DONE, CALCULATE_DIFFERENCE, LARGE_LOOP_PREFETCH, SMALL_LOOP_ENTER,
+        DONE, CALCULATE_DIFFERENCE, LARGE_LOOP_PREFETCH, NO_PREFETCH,
         LARGE_LOOP_PREFETCH_REPEAT1, LARGE_LOOP_PREFETCH_REPEAT2;
     Register result = r0, str1 = r1, cnt1 = r2, str2 = r3, cnt2 = r4,
         tmp1 = r10, tmp2 = r11, tmp3 = r12, tmp4 = r14;
     FloatRegister vtmpZ = v0, vtmp = v1, vtmp3 = v2;
     RegSet spilled_regs = RegSet::of(tmp3, tmp4);
 
-    int prefetchLoopExitCondition = MAX(32, SoftwarePrefetchHintDistance/2);
+    int prefetchLoopExitCondition = MAX(64, SoftwarePrefetchHintDistance/2);
 
     __ eor(vtmpZ, __ T16B, vtmpZ, vtmpZ);
     // cnt2 == amount of characters left to compare
@@ -4069,7 +4069,7 @@
 
     if (SoftwarePrefetchHintDistance >= 0) {
       __ subs(rscratch2, cnt2, prefetchLoopExitCondition);
-      __ br(__ LT, SMALL_LOOP);
+      __ br(__ LT, NO_PREFETCH);
       __ bind(LARGE_LOOP_PREFETCH);
         __ prfm(Address(tmp2, SoftwarePrefetchHintDistance));
         __ mov(tmp4, 2);
@@ -4089,51 +4089,20 @@
           __ br(__ GE, LARGE_LOOP_PREFETCH);
     }
     __ cbz(cnt2, LOAD_LAST); // no characters left except last load
+    __ bind(NO_PREFETCH);
     __ subs(cnt2, cnt2, 16);
     __ br(__ LT, TAIL);
-    __ b(SMALL_LOOP_ENTER);
     __ bind(SMALL_LOOP); // smaller loop
       __ subs(cnt2, cnt2, 16);
-    __ bind(SMALL_LOOP_ENTER);
       compare_string_16_x_LU(tmpL, tmpU, DIFF1, DIFF2);
       __ br(__ GE, SMALL_LOOP);
-      __ cbz(cnt2, LOAD_LAST);
-    __ bind(TAIL); // 1..15 characters left
-      __ subs(zr, cnt2, -8);
-      __ br(__ GT, TAIL_LOAD_16);
-      __ ldrd(vtmp, Address(tmp2));
-      __ zip1(vtmp3, __ T8B, vtmp, vtmpZ);
-
-      __ ldr(tmpU, Address(__ post(cnt1, 8)));
-      __ fmovd(tmpL, vtmp3);
-      __ eor(rscratch2, tmp3, tmpL);
-      __ cbnz(rscratch2, DIFF2);
-      __ umov(tmpL, vtmp3, __ D, 1);
-      __ eor(rscratch2, tmpU, tmpL);
-      __ cbnz(rscratch2, DIFF1);
-      __ b(LOAD_LAST);
-    __ bind(TAIL_LOAD_16);
-      __ ldrq(vtmp, Address(tmp2));
-      __ ldr(tmpU, Address(__ post(cnt1, 8)));
-      __ zip1(vtmp3, __ T16B, vtmp, vtmpZ);
-      __ zip2(vtmp, __ T16B, vtmp, vtmpZ);
-      __ fmovd(tmpL, vtmp3);
-      __ eor(rscratch2, tmp3, tmpL);
-      __ cbnz(rscratch2, DIFF2);
-
-      __ ldr(tmp3, Address(__ post(cnt1, 8)));
-      __ umov(tmpL, vtmp3, __ D, 1);
-      __ eor(rscratch2, tmpU, tmpL);
-      __ cbnz(rscratch2, DIFF1);
-
-      __ ldr(tmpU, Address(__ post(cnt1, 8)));
-      __ fmovd(tmpL, vtmp);
-      __ eor(rscratch2, tmp3, tmpL);
-      __ cbnz(rscratch2, DIFF2);
-
-      __ umov(tmpL, vtmp, __ D, 1);
-      __ eor(rscratch2, tmpU, tmpL);
-      __ cbnz(rscratch2, DIFF1);
+      __ cmn(cnt2, (u1)16);
+      __ br(__ EQ, LOAD_LAST);
+    __ bind(TAIL); // 1..15 characters left until last load (last 4 characters)
+      __ add(cnt1, cnt1, cnt2, __ LSL, 1); // Address of 8 bytes before last 4 characters in UTF-16 string
+      __ add(tmp2, tmp2, cnt2); // Address of 16 bytes before last 4 characters in Latin1 string
+      __ ldr(tmp3, Address(cnt1, -8));
+      compare_string_16_x_LU(tmpL, tmpU, DIFF1, DIFF2); // last 16 characters before last load
       __ b(LOAD_LAST);
     __ bind(DIFF2);
       __ mov(tmpU, tmp3);
@@ -4141,10 +4110,12 @@
       __ pop(spilled_regs, sp);
       __ b(CALCULATE_DIFFERENCE);
     __ bind(LOAD_LAST);
+      // Last 4 UTF-16 characters are already pre-loaded into tmp3 by compare_string_16_x_LU.
+      // No need to load it again
+      __ mov(tmpU, tmp3);
       __ pop(spilled_regs, sp);
 
       __ ldrs(vtmp, Address(strL));
-      __ ldr(tmpU, Address(strU));
       __ zip1(vtmp, __ T8B, vtmp, vtmpZ);
       __ fmovd(tmpL, vtmp);
 
@@ -4206,10 +4177,10 @@
         compare_string_16_bytes_same(DIFF, DIFF2);
         __ br(__ GT, LARGE_LOOP_PREFETCH);
         __ cbz(cnt2, LAST_CHECK_AND_LENGTH_DIFF); // no more chars left?
-        // less than 16 bytes left?
-        __ subs(cnt2, cnt2, isLL ? 16 : 8);
-        __ br(__ LT, TAIL);
     }
+    // less than 16 bytes left?
+    __ subs(cnt2, cnt2, isLL ? 16 : 8);
+    __ br(__ LT, TAIL);
     __ bind(SMALL_LOOP);
       compare_string_16_bytes_same(DIFF, DIFF2);
       __ subs(cnt2, cnt2, isLL ? 16 : 8);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/jtreg/compiler/intrinsics/string/TestStringCompareToDifferentLength.java	Wed May 22 20:39:04 2019 +0300
@@ -0,0 +1,101 @@
+/*
+ * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2019, BELLSOFT. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @requires os.arch=="aarch64"
+ * @summary String::compareTo implementation uses different algorithms for
+ *          different string length. This test creates string with specified
+ *          size and longer string, which is same at beginning.
+ *          Expecting length delta to be returned. Test class takes 2
+ *          parameters: <string length>, <maximum string length delta>
+ *          Input parameters for this test are set according to Aarch64
+ *          String::compareTo intrinsic implementation specifics. Aarch64
+ *          implementation has 1, 4, 8 -characters loops for length < 72 and
+ *          16, 32, 64 -characters loops for length >= 72. Code is also affected
+ *          by SoftwarePrefetchHintDistance vm flag value.
+ * @run main/othervm -XX:SoftwarePrefetchHintDistance=192 compiler.intrinsics.string.TestStringCompareToDifferentLength 4 2 5 10 13 17 20 25 71 72 73 88 90 192 193 208 209
+ * @run main/othervm -XX:SoftwarePrefetchHintDistance=16 compiler.intrinsics.string.TestStringCompareToDifferentLength 4 2 5 10 13 17 20 25 71 72 73 88 90
+ * @run main/othervm -XX:SoftwarePrefetchHintDistance=-1 compiler.intrinsics.string.TestStringCompareToDifferentLength 4 2 5 10 13 17 20 25 71 72 73 88 90
+ */
+
+package compiler.intrinsics.string;
+
+public class TestStringCompareToDifferentLength {
+    private final int size;
+
+    public static void main(String args[]) {
+        if (args.length > 1) {
+            int maxLengthDelta = Integer.parseInt(args[0]);
+            for (int i = 1; i < args.length; i++) {
+                int  size = Integer.parseInt(args[i]);
+                TestStringCompareToDifferentLength test
+                        = new TestStringCompareToDifferentLength(size);
+                for (int delta = 1; delta <= maxLengthDelta; delta++) {
+                    test.testCompareTo(delta);
+                }
+            }
+        } else {
+            System.out.println("Usage: $testClass $maxLengthDelta $testLength [$testLength2 [$testLength3 [...]]]");
+        }
+    }
+
+    private TestStringCompareToDifferentLength(int size) {
+        this.size = size;
+    }
+
+    private void testCompareTo(int delta) {
+        char strsrc[] = new char[size + delta];
+        // generate ASCII string
+        for (int i = 0; i < size + delta; i++) {
+            strsrc[i] = (char) ('a' + (i % 26));
+        }
+
+        String longLatin1 = new String(strsrc);
+        String shortLatin1 = longLatin1.substring(0, size);
+
+        String longUTF16LastChar = longLatin1.substring(0, longLatin1.length() - 1) + '\uBEEF';
+        String longUTF16FirstChar = '\uBEEF' + longLatin1.substring(1, longLatin1.length());
+        String shortUTF16FirstChar = longUTF16FirstChar.substring(0, size);
+
+        for (int i = 0; i < 10000; i++) {
+            checkCase(longLatin1, shortLatin1, delta, "LL"); // Latin1-Latin1.
+            checkCase(longUTF16LastChar, shortLatin1, delta, "UL"); // Latin1-UTF-16 case.
+            checkCase(longUTF16FirstChar, shortUTF16FirstChar, delta, "UU"); // UTF-16-UTF-16 case
+        }
+    }
+
+    private void checkCase(String str2, String str1, int expected, String caseName) {
+        int result = str2.compareTo(str1);
+        int reversedResult = str1.compareTo(str2);
+        if (expected != result || result != -reversedResult) {
+            throw new AssertionError(String.format("%s CASE FAILED: size = %d, "
+                    + "expected = %d, but got result = %d, "
+                    + "reversedResult = %d for string1 = '%s', string2 = '%s'",
+                    caseName, size, expected, result,
+                    reversedResult, str1, str2));
+        }
+    }
+}
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/hotspot/jtreg/compiler/intrinsics/string/TestStringCompareToSameLength.java	Wed May 22 20:39:04 2019 +0300
@@ -0,0 +1,142 @@
+/*
+ * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2019, BELLSOFT. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @requires os.arch=="aarch64"
+ * @summary String::compareTo implementation uses different algorithms for
+ *          different string length. This test creates various strings of
+ *          specified size, which are different at all possible index values and
+ *          compares them. Expecting separately calculated result to be returned.
+ *          String size is specified via commandline. Various size values can
+ *          be specified during intrinsic development in order to test cases
+ *          specific for new or modified intrinsic implementation. Aarch64
+ *          implementation has 1, 4, 8 -characters loops for length < 72 and
+ *          16, 32, 64 -characters loops for string length >= 72. Code is also
+ *          affected by SoftwarePrefetchHintDistance flag value.
+ *          Test class can also accept "-fullmode" parameter
+ *          with maxLength paramter after it. Then it will iterate through all
+ *          string length values up to maxLength parameter (inclusive). It takes
+ *          a lot of time but is useful for development.
+ * @run main/othervm -XX:SoftwarePrefetchHintDistance=192 compiler.intrinsics.string.TestStringCompareToSameLength 2 5 10 13 17 20 25 71 72 73 88 90 192 193 208 209
+ * @run main/othervm -XX:SoftwarePrefetchHintDistance=16 compiler.intrinsics.string.TestStringCompareToSameLength 2 5 10 13 17 20 25 71 72 73 88 90
+ * @run main/othervm -XX:SoftwarePrefetchHintDistance=-1 compiler.intrinsics.string.TestStringCompareToSameLength 2 5 10 13 17 20 25 71 72 73 88 90
+ */
+
+package compiler.intrinsics.string;
+
+public class TestStringCompareToSameLength {
+    private final int size;
+
+    public static void main(String args[]) {
+        if (args.length == 0) {
+            throw new IllegalArgumentException("Usage: $testClass $testLength1"
+                    + " [$testLength2 [...]] | -fullmode $maxLength");
+        }
+        if (args.length == 2 && "-fullmode".equals(args[0])) {
+            int maxLength = Integer.parseInt(args[1]);
+            for (int length = 1; length <= maxLength; length++) {
+                TestStringCompareToSameLength test = new TestStringCompareToSameLength(length);
+                for (int mismatchIdx = 0; mismatchIdx <= length; mismatchIdx++) {
+                    test.testCompareTo(mismatchIdx);
+                }
+            }
+        } else {
+            for (String arg : args) {
+                int size = Integer.parseInt(arg);
+                TestStringCompareToSameLength test = new TestStringCompareToSameLength(size);
+                for (int mismatchIdx = 0; mismatchIdx <= size; mismatchIdx++) {
+                    test.testCompareTo(mismatchIdx);
+                }
+            }
+        }
+    }
+
+    private TestStringCompareToSameLength(int size) {
+        this.size = size;
+    }
+
+    private void testCompareTo(int mismatchIdx) {
+        // Create Latin1 strings: latin1, latin2, which are different at index.
+        // Case of index == size is a case of equal strings
+        char latinSrc[] = new char[size];
+        // generate ASCII string
+        for (int i = 0; i < size; i++) {
+            latinSrc[i] = (char) ('a' + (i % 26));
+        }
+        String latinStr1 = new String(latinSrc);
+        if (mismatchIdx != size) latinSrc[mismatchIdx] = (char) ('a' - 1);
+        String latinStr2 = new String(latinSrc);
+
+        // Create 3 utf strings: utfStr1, utfStr2: same as latinStr1, but has UTF-16 character
+        // utfStr1 and utfStr2 are different at requested index and character value is greater
+        // than same index character in latinStr1.
+        // utfStr3 is different at requested index and character value is less than same
+        // index character in latinStr1. Will be a Latin1-encoded string in case difference
+        // is requested at last character. This case not applicable and is skipped below.
+        char cArray[] = latinStr1.toCharArray();
+        cArray[cArray.length - 1] = '\uBEEF'; // at least last character is UTF-16
+        if (mismatchIdx != size) cArray[mismatchIdx] = '\u1234';
+        String utfStr1 = new String(cArray);
+        if (mismatchIdx != size) cArray[mismatchIdx] = '\u5678';
+        String utfStr2 = new String(cArray);
+        if (mismatchIdx != size) cArray[mismatchIdx] = (char) ('a' - 2); // less than Latin1 index position
+        // utfStr3 will be Latin1 if last character differ. Will skip this case
+        String utfStr3 = new String(cArray);
+
+        for (int i = 0; i < 10000; i++) {
+            checkCase(mismatchIdx, latinStr1, latinStr2, "LL"); // compare Latin1 with Latin1
+
+            checkCase(mismatchIdx, utfStr1, utfStr2, "UU"); // compare UTF-16 vs UTF-16
+
+            if (size != mismatchIdx) { // UTF-16 and Latin1 strings can't be equal. Then skip this case
+                // compare UTF16 string, which is expected to be > than Latin1
+                checkCase(mismatchIdx, latinStr1, utfStr1, "U(large)L");
+                if (mismatchIdx != size - 1) {
+                    // compare UTF16 string, which is expected to be < than Latin1
+                    checkCase(mismatchIdx,  latinStr1, utfStr3, "U(small)L");
+                }
+            }
+        }
+    }
+
+    private void checkCase(int mismatchIdx, String str1, String str2, String caseName) {
+        int expected;
+        if (mismatchIdx != size) {
+            expected = str1.charAt(mismatchIdx) - str2.charAt(mismatchIdx);
+        } else {
+            expected = str1.length() - str2.length();
+        }
+        int result = str1.compareTo(str2);
+        int reversedResult = str2.compareTo(str1);
+        if (expected != result || result != -reversedResult) {
+            throw new AssertionError(String.format("%s CASE FAILED: size = %d, "
+                    + "mismatchIdx = %d, expected = %d, but got result = %d, "
+                    + "reversedResult = %d for string1 = '%s', string2 = '%s'",
+                    caseName, size, mismatchIdx, expected, result,
+                    reversedResult, str1, str2));
+        }
+    }
+}
+