Mercurial > hg > graal-compiler
changeset 2320:41d4973cf100
6942326: x86 code in string_indexof() could read beyond reserved heap space
Summary: copy small (<8) strings on stack if str+16 crosses a page boundary and load from stack into XMM. Back up pointer when loading string's tail.
Reviewed-by: never
author | kvn |
---|---|
date | Sat, 26 Feb 2011 12:10:54 -0800 |
parents | 8190d4b75e09 |
children | 1b4e6a5d98e0 |
files | src/cpu/x86/vm/assembler_x86.cpp src/cpu/x86/vm/assembler_x86.hpp src/cpu/x86/vm/x86_32.ad src/cpu/x86/vm/x86_64.ad src/share/vm/opto/library_call.cpp src/share/vm/opto/memnode.cpp test/compiler/6942326/Test.java |
diffstat | 7 files changed, 955 insertions(+), 114 deletions(-) [+] |
line wrap: on
line diff
--- a/src/cpu/x86/vm/assembler_x86.cpp Thu Feb 24 14:49:34 2011 -0800 +++ b/src/cpu/x86/vm/assembler_x86.cpp Sat Feb 26 12:10:54 2011 -0800 @@ -1601,6 +1601,17 @@ emit_byte(0xC0 | encode); } +void Assembler::movdl(XMMRegister dst, Address src) { + NOT_LP64(assert(VM_Version::supports_sse2(), "")); + InstructionMark im(this); + emit_byte(0x66); + prefix(src, dst); + emit_byte(0x0F); + emit_byte(0x6E); + emit_operand(dst, src); +} + + void Assembler::movdqa(XMMRegister dst, Address src) { NOT_LP64(assert(VM_Version::supports_sse2(), "")); InstructionMark im(this); @@ -2412,7 +2423,10 @@ } void Assembler::psrlq(XMMRegister dst, int shift) { - // HMM Table D-1 says sse2 or mmx + // Shift 64 bit value logically right by specified number of bits. + // HMM Table D-1 says sse2 or mmx. + // Do not confuse it with psrldq SSE2 instruction which + // shifts 128 bit value in xmm register by number of bytes. NOT_LP64(assert(VM_Version::supports_sse(), "")); int encode = prefixq_and_encode(xmm2->encoding(), dst->encoding()); @@ -2423,6 +2437,18 @@ emit_byte(shift); } +void Assembler::psrldq(XMMRegister dst, int shift) { + // Shift 128 bit value in xmm register by number of bytes. + NOT_LP64(assert(VM_Version::supports_sse2(), "")); + + int encode = prefixq_and_encode(xmm3->encoding(), dst->encoding()); + emit_byte(0x66); + emit_byte(0x0F); + emit_byte(0x73); + emit_byte(0xC0 | encode); + emit_byte(shift); +} + void Assembler::ptest(XMMRegister dst, Address src) { assert(VM_Version::supports_sse4_1(), ""); @@ -8567,101 +8593,418 @@ } #endif // _LP64 -// IndexOf substring. -void MacroAssembler::string_indexof(Register str1, Register str2, - Register cnt1, Register cnt2, Register result, - XMMRegister vec, Register tmp) { +// IndexOf for constant substrings with size >= 8 chars +// which don't need to be loaded through stack. +void MacroAssembler::string_indexofC8(Register str1, Register str2, + Register cnt1, Register cnt2, + int int_cnt2, Register result, + XMMRegister vec, Register tmp) { assert(UseSSE42Intrinsics, "SSE4.2 is required"); - Label RELOAD_SUBSTR, PREP_FOR_SCAN, SCAN_TO_SUBSTR, - SCAN_SUBSTR, RET_NOT_FOUND, CLEANUP; - - push(str1); // string addr - push(str2); // substr addr - push(cnt2); // substr count - jmpb(PREP_FOR_SCAN); - - // Substr count saved at sp - // Substr saved at sp+1*wordSize - // String saved at sp+2*wordSize - - // Reload substr for rescan - bind(RELOAD_SUBSTR); - movl(cnt2, Address(rsp, 0)); - movptr(str2, Address(rsp, wordSize)); - // We came here after the beginninig of the substring was - // matched but the rest of it was not so we need to search - // again. Start from the next element after the previous match. - subptr(str1, result); // Restore counter - shrl(str1, 1); - addl(cnt1, str1); - decrementl(cnt1); - lea(str1, Address(result, 2)); // Reload string - - // Load substr - bind(PREP_FOR_SCAN); - movdqu(vec, Address(str2, 0)); - addl(cnt1, 8); // prime the loop - subptr(str1, 16); - - // Scan string for substr in 16-byte vectors - bind(SCAN_TO_SUBSTR); - subl(cnt1, 8); - addptr(str1, 16); - - // pcmpestri + // This method uses pcmpestri inxtruction with bound registers // inputs: // xmm - substring // rax - substring length (elements count) - // mem - scaned string + // mem - scanned string + // rdx - string length (elements count) + // 0xd - mode: 1100 (substring search) + 01 (unsigned shorts) + // outputs: + // rcx - matched index in string + assert(cnt1 == rdx && cnt2 == rax && tmp == rcx, "pcmpestri"); + + Label RELOAD_SUBSTR, SCAN_TO_SUBSTR, SCAN_SUBSTR, + RET_FOUND, RET_NOT_FOUND, EXIT, FOUND_SUBSTR, + MATCH_SUBSTR_HEAD, RELOAD_STR, FOUND_CANDIDATE; + + // Note, inline_string_indexOf() generates checks: + // if (substr.count > string.count) return -1; + // if (substr.count == 0) return 0; + assert(int_cnt2 >= 8, "this code isused only for cnt2 >= 8 chars"); + + // Load substring. + movdqu(vec, Address(str2, 0)); + movl(cnt2, int_cnt2); + movptr(result, str1); // string addr + + if (int_cnt2 > 8) { + jmpb(SCAN_TO_SUBSTR); + + // Reload substr for rescan, this code + // is executed only for large substrings (> 8 chars) + bind(RELOAD_SUBSTR); + movdqu(vec, Address(str2, 0)); + negptr(cnt2); // Jumped here with negative cnt2, convert to positive + + bind(RELOAD_STR); + // We came here after the beginning of the substring was + // matched but the rest of it was not so we need to search + // again. Start from the next element after the previous match. + + // cnt2 is number of substring reminding elements and + // cnt1 is number of string reminding elements when cmp failed. + // Restored cnt1 = cnt1 - cnt2 + int_cnt2 + subl(cnt1, cnt2); + addl(cnt1, int_cnt2); + movl(cnt2, int_cnt2); // Now restore cnt2 + + decrementl(cnt1); // Shift to next element + cmpl(cnt1, cnt2); + jccb(Assembler::negative, RET_NOT_FOUND); // Left less then substring + + addptr(result, 2); + + } // (int_cnt2 > 8) + + // Scan string for start of substr in 16-byte vectors + bind(SCAN_TO_SUBSTR); + pcmpestri(vec, Address(result, 0), 0x0d); + jccb(Assembler::below, FOUND_CANDIDATE); // CF == 1 + subl(cnt1, 8); + jccb(Assembler::lessEqual, RET_NOT_FOUND); // Scanned full string + cmpl(cnt1, cnt2); + jccb(Assembler::negative, RET_NOT_FOUND); // Left less then substring + addptr(result, 16); + jmpb(SCAN_TO_SUBSTR); + + // Found a potential substr + bind(FOUND_CANDIDATE); + // Matched whole vector if first element matched (tmp(rcx) == 0). + if (int_cnt2 == 8) { + jccb(Assembler::overflow, RET_FOUND); // OF == 1 + } else { // int_cnt2 > 8 + jccb(Assembler::overflow, FOUND_SUBSTR); + } + // After pcmpestri tmp(rcx) contains matched element index + // Compute start addr of substr + lea(result, Address(result, tmp, Address::times_2)); + + // Make sure string is still long enough + subl(cnt1, tmp); + cmpl(cnt1, cnt2); + if (int_cnt2 == 8) { + jccb(Assembler::greaterEqual, SCAN_TO_SUBSTR); + } else { // int_cnt2 > 8 + jccb(Assembler::greaterEqual, MATCH_SUBSTR_HEAD); + } + // Left less then substring. + + bind(RET_NOT_FOUND); + movl(result, -1); + jmpb(EXIT); + + if (int_cnt2 > 8) { + // This code is optimized for the case when whole substring + // is matched if its head is matched. + bind(MATCH_SUBSTR_HEAD); + pcmpestri(vec, Address(result, 0), 0x0d); + // Reload only string if does not match + jccb(Assembler::noOverflow, RELOAD_STR); // OF == 0 + + Label CONT_SCAN_SUBSTR; + // Compare the rest of substring (> 8 chars). + bind(FOUND_SUBSTR); + // First 8 chars are already matched. + negptr(cnt2); + addptr(cnt2, 8); + + bind(SCAN_SUBSTR); + subl(cnt1, 8); + cmpl(cnt2, -8); // Do not read beyond substring + jccb(Assembler::lessEqual, CONT_SCAN_SUBSTR); + // Back-up strings to avoid reading beyond substring: + // cnt1 = cnt1 - cnt2 + 8 + addl(cnt1, cnt2); // cnt2 is negative + addl(cnt1, 8); + movl(cnt2, 8); negptr(cnt2); + bind(CONT_SCAN_SUBSTR); + if (int_cnt2 < (int)G) { + movdqu(vec, Address(str2, cnt2, Address::times_2, int_cnt2*2)); + pcmpestri(vec, Address(result, cnt2, Address::times_2, int_cnt2*2), 0x0d); + } else { + // calculate index in register to avoid integer overflow (int_cnt2*2) + movl(tmp, int_cnt2); + addptr(tmp, cnt2); + movdqu(vec, Address(str2, tmp, Address::times_2, 0)); + pcmpestri(vec, Address(result, tmp, Address::times_2, 0), 0x0d); + } + // Need to reload strings pointers if not matched whole vector + jccb(Assembler::noOverflow, RELOAD_SUBSTR); // OF == 0 + addptr(cnt2, 8); + jccb(Assembler::negative, SCAN_SUBSTR); + // Fall through if found full substring + + } // (int_cnt2 > 8) + + bind(RET_FOUND); + // Found result if we matched full small substring. + // Compute substr offset + subptr(result, str1); + shrl(result, 1); // index + bind(EXIT); + +} // string_indexofC8 + +// Small strings are loaded through stack if they cross page boundary. +void MacroAssembler::string_indexof(Register str1, Register str2, + Register cnt1, Register cnt2, + int int_cnt2, Register result, + XMMRegister vec, Register tmp) { + assert(UseSSE42Intrinsics, "SSE4.2 is required"); + // + // int_cnt2 is length of small (< 8 chars) constant substring + // or (-1) for non constant substring in which case its length + // is in cnt2 register. + // + // Note, inline_string_indexOf() generates checks: + // if (substr.count > string.count) return -1; + // if (substr.count == 0) return 0; + // + assert(int_cnt2 == -1 || (0 < int_cnt2 && int_cnt2 < 8), "should be != 0"); + + // This method uses pcmpestri inxtruction with bound registers + // inputs: + // xmm - substring + // rax - substring length (elements count) + // mem - scanned string // rdx - string length (elements count) // 0xd - mode: 1100 (substring search) + 01 (unsigned shorts) // outputs: // rcx - matched index in string assert(cnt1 == rdx && cnt2 == rax && tmp == rcx, "pcmpestri"); - pcmpestri(vec, Address(str1, 0), 0x0d); - jcc(Assembler::above, SCAN_TO_SUBSTR); // CF == 0 && ZF == 0 - jccb(Assembler::aboveEqual, RET_NOT_FOUND); // CF == 0 - - // Fallthrough: found a potential substr + Label RELOAD_SUBSTR, SCAN_TO_SUBSTR, SCAN_SUBSTR, ADJUST_STR, + RET_FOUND, RET_NOT_FOUND, CLEANUP, FOUND_SUBSTR, + FOUND_CANDIDATE; + + { //======================================================== + // We don't know where these strings are located + // and we can't read beyond them. Load them through stack. + Label BIG_STRINGS, CHECK_STR, COPY_SUBSTR, COPY_STR; + + movptr(tmp, rsp); // save old SP + + if (int_cnt2 > 0) { // small (< 8 chars) constant substring + if (int_cnt2 == 1) { // One char + load_unsigned_short(result, Address(str2, 0)); + movdl(vec, result); // move 32 bits + } else if (int_cnt2 == 2) { // Two chars + movdl(vec, Address(str2, 0)); // move 32 bits + } else if (int_cnt2 == 4) { // Four chars + movq(vec, Address(str2, 0)); // move 64 bits + } else { // cnt2 = { 3, 5, 6, 7 } + // Array header size is 12 bytes in 32-bit VM + // + 6 bytes for 3 chars == 18 bytes, + // enough space to load vec and shift. + assert(HeapWordSize*typeArrayKlass::header_size() >= 12,"sanity"); + movdqu(vec, Address(str2, (int_cnt2*2)-16)); + psrldq(vec, 16-(int_cnt2*2)); + } + } else { // not constant substring + cmpl(cnt2, 8); + jccb(Assembler::aboveEqual, BIG_STRINGS); // Both strings are big enough + + // We can read beyond string if srt+16 does not cross page boundary + // since heaps are aligned and mapped by pages. + assert(os::vm_page_size() < (int)G, "default page should be small"); + movl(result, str2); // We need only low 32 bits + andl(result, (os::vm_page_size()-1)); + cmpl(result, (os::vm_page_size()-16)); + jccb(Assembler::belowEqual, CHECK_STR); + + // Move small strings to stack to allow load 16 bytes into vec. + subptr(rsp, 16); + int stk_offset = wordSize-2; + push(cnt2); + + bind(COPY_SUBSTR); + load_unsigned_short(result, Address(str2, cnt2, Address::times_2, -2)); + movw(Address(rsp, cnt2, Address::times_2, stk_offset), result); + decrement(cnt2); + jccb(Assembler::notZero, COPY_SUBSTR); + + pop(cnt2); + movptr(str2, rsp); // New substring address + } // non constant + + bind(CHECK_STR); + cmpl(cnt1, 8); + jccb(Assembler::aboveEqual, BIG_STRINGS); + + // Check cross page boundary. + movl(result, str1); // We need only low 32 bits + andl(result, (os::vm_page_size()-1)); + cmpl(result, (os::vm_page_size()-16)); + jccb(Assembler::belowEqual, BIG_STRINGS); + + subptr(rsp, 16); + int stk_offset = -2; + if (int_cnt2 < 0) { // not constant + push(cnt2); + stk_offset += wordSize; + } + movl(cnt2, cnt1); + + bind(COPY_STR); + load_unsigned_short(result, Address(str1, cnt2, Address::times_2, -2)); + movw(Address(rsp, cnt2, Address::times_2, stk_offset), result); + decrement(cnt2); + jccb(Assembler::notZero, COPY_STR); + + if (int_cnt2 < 0) { // not constant + pop(cnt2); + } + movptr(str1, rsp); // New string address + + bind(BIG_STRINGS); + // Load substring. + if (int_cnt2 < 0) { // -1 + movdqu(vec, Address(str2, 0)); + push(cnt2); // substr count + push(str2); // substr addr + push(str1); // string addr + } else { + // Small (< 8 chars) constant substrings are loaded already. + movl(cnt2, int_cnt2); + } + push(tmp); // original SP + + } // Finished loading + + //======================================================== + // Start search + // + + movptr(result, str1); // string addr + + if (int_cnt2 < 0) { // Only for non constant substring + jmpb(SCAN_TO_SUBSTR); + + // SP saved at sp+0 + // String saved at sp+1*wordSize + // Substr saved at sp+2*wordSize + // Substr count saved at sp+3*wordSize + + // Reload substr for rescan, this code + // is executed only for large substrings (> 8 chars) + bind(RELOAD_SUBSTR); + movptr(str2, Address(rsp, 2*wordSize)); + movl(cnt2, Address(rsp, 3*wordSize)); + movdqu(vec, Address(str2, 0)); + // We came here after the beginning of the substring was + // matched but the rest of it was not so we need to search + // again. Start from the next element after the previous match. + subptr(str1, result); // Restore counter + shrl(str1, 1); + addl(cnt1, str1); + decrementl(cnt1); // Shift to next element + cmpl(cnt1, cnt2); + jccb(Assembler::negative, RET_NOT_FOUND); // Left less then substring + + addptr(result, 2); + } // non constant + + // Scan string for start of substr in 16-byte vectors + bind(SCAN_TO_SUBSTR); + assert(cnt1 == rdx && cnt2 == rax && tmp == rcx, "pcmpestri"); + pcmpestri(vec, Address(result, 0), 0x0d); + jccb(Assembler::below, FOUND_CANDIDATE); // CF == 1 + subl(cnt1, 8); + jccb(Assembler::lessEqual, RET_NOT_FOUND); // Scanned full string + cmpl(cnt1, cnt2); + jccb(Assembler::negative, RET_NOT_FOUND); // Left less then substring + addptr(result, 16); + + bind(ADJUST_STR); + cmpl(cnt1, 8); // Do not read beyond string + jccb(Assembler::greaterEqual, SCAN_TO_SUBSTR); + // Back-up string to avoid reading beyond string. + lea(result, Address(result, cnt1, Address::times_2, -16)); + movl(cnt1, 8); + jmpb(SCAN_TO_SUBSTR); + + // Found a potential substr + bind(FOUND_CANDIDATE); + // After pcmpestri tmp(rcx) contains matched element index // Make sure string is still long enough subl(cnt1, tmp); cmpl(cnt1, cnt2); - jccb(Assembler::negative, RET_NOT_FOUND); - // Compute start addr of substr - lea(str1, Address(str1, tmp, Address::times_2)); - movptr(result, str1); // save - - // Compare potential substr - addl(cnt1, 8); // prime the loop - addl(cnt2, 8); - subptr(str1, 16); - subptr(str2, 16); - - // Scan 16-byte vectors of string and substr - bind(SCAN_SUBSTR); - subl(cnt1, 8); - subl(cnt2, 8); - addptr(str1, 16); - addptr(str2, 16); - movdqu(vec, Address(str2, 0)); - pcmpestri(vec, Address(str1, 0), 0x0d); - jcc(Assembler::noOverflow, RELOAD_SUBSTR); // OF == 0 - jcc(Assembler::positive, SCAN_SUBSTR); // SF == 0 - - // Compute substr offset - subptr(result, Address(rsp, 2*wordSize)); - shrl(result, 1); // index - jmpb(CLEANUP); + jccb(Assembler::greaterEqual, FOUND_SUBSTR); + // Left less then substring. bind(RET_NOT_FOUND); movl(result, -1); + jmpb(CLEANUP); + + bind(FOUND_SUBSTR); + // Compute start addr of substr + lea(result, Address(result, tmp, Address::times_2)); + + if (int_cnt2 > 0) { // Constant substring + // Repeat search for small substring (< 8 chars) + // from new point without reloading substring. + // Have to check that we don't read beyond string. + cmpl(tmp, 8-int_cnt2); + jccb(Assembler::greater, ADJUST_STR); + // Fall through if matched whole substring. + } else { // non constant + assert(int_cnt2 == -1, "should be != 0"); + + addl(tmp, cnt2); + // Found result if we matched whole substring. + cmpl(tmp, 8); + jccb(Assembler::lessEqual, RET_FOUND); + + // Repeat search for small substring (<= 8 chars) + // from new point 'str1' without reloading substring. + cmpl(cnt2, 8); + // Have to check that we don't read beyond string. + jccb(Assembler::lessEqual, ADJUST_STR); + + Label CHECK_NEXT, CONT_SCAN_SUBSTR, RET_FOUND_LONG; + // Compare the rest of substring (> 8 chars). + movptr(str1, result); + + cmpl(tmp, cnt2); + // First 8 chars are already matched. + jccb(Assembler::equal, CHECK_NEXT); + + bind(SCAN_SUBSTR); + pcmpestri(vec, Address(str1, 0), 0x0d); + // Need to reload strings pointers if not matched whole vector + jcc(Assembler::noOverflow, RELOAD_SUBSTR); // OF == 0 + + bind(CHECK_NEXT); + subl(cnt2, 8); + jccb(Assembler::lessEqual, RET_FOUND_LONG); // Found full substring + addptr(str1, 16); + addptr(str2, 16); + subl(cnt1, 8); + cmpl(cnt2, 8); // Do not read beyond substring + jccb(Assembler::greaterEqual, CONT_SCAN_SUBSTR); + // Back-up strings to avoid reading beyond substring. + lea(str2, Address(str2, cnt2, Address::times_2, -16)); + lea(str1, Address(str1, cnt2, Address::times_2, -16)); + subl(cnt1, cnt2); + movl(cnt2, 8); + addl(cnt1, 8); + bind(CONT_SCAN_SUBSTR); + movdqu(vec, Address(str2, 0)); + jmpb(SCAN_SUBSTR); + + bind(RET_FOUND_LONG); + movptr(str1, Address(rsp, wordSize)); + } // non constant + + bind(RET_FOUND); + // Compute substr offset + subptr(result, str1); + shrl(result, 1); // index bind(CLEANUP); - addptr(rsp, 3*wordSize); -} + pop(rsp); // restore SP + +} // string_indexof // Compare strings. void MacroAssembler::string_compare(Register str1, Register str2,
--- a/src/cpu/x86/vm/assembler_x86.hpp Thu Feb 24 14:49:34 2011 -0800 +++ b/src/cpu/x86/vm/assembler_x86.hpp Sat Feb 26 12:10:54 2011 -0800 @@ -1121,6 +1121,7 @@ void movdl(XMMRegister dst, Register src); void movdl(Register dst, XMMRegister src); + void movdl(XMMRegister dst, Address src); // Move Double Quadword void movdq(XMMRegister dst, Register src); @@ -1288,9 +1289,12 @@ void pshuflw(XMMRegister dst, XMMRegister src, int mode); void pshuflw(XMMRegister dst, Address src, int mode); - // Shift Right Logical Quadword Immediate + // Shift Right by bits Logical Quadword Immediate void psrlq(XMMRegister dst, int shift); + // Shift Right by bytes Logical DoubleQuadword Immediate + void psrldq(XMMRegister dst, int shift); + // Logical Compare Double Quadword void ptest(XMMRegister dst, XMMRegister src); void ptest(XMMRegister dst, Address src); @@ -2290,10 +2294,22 @@ void movl2ptr(Register dst, Register src) { LP64_ONLY(movslq(dst, src)) NOT_LP64(if (dst != src) movl(dst, src)); } // IndexOf strings. + // Small strings are loaded through stack if they cross page boundary. void string_indexof(Register str1, Register str2, - Register cnt1, Register cnt2, Register result, + Register cnt1, Register cnt2, + int int_cnt2, Register result, XMMRegister vec, Register tmp); + // IndexOf for constant substrings with size >= 8 elements + // which don't need to be loaded through stack. + void string_indexofC8(Register str1, Register str2, + Register cnt1, Register cnt2, + int int_cnt2, Register result, + XMMRegister vec, Register tmp); + + // Smallest code: we don't need to load through stack, + // check string tail. + // Compare strings. void string_compare(Register str1, Register str2, Register cnt1, Register cnt2, Register result,
--- a/src/cpu/x86/vm/x86_32.ad Thu Feb 24 14:49:34 2011 -0800 +++ b/src/cpu/x86/vm/x86_32.ad Sat Feb 26 12:10:54 2011 -0800 @@ -1,5 +1,5 @@ // -// Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. +// Copyright (c) 1997, 2011, Oracle and/or its affiliates. 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 @@ -12658,17 +12658,46 @@ ins_pipe( pipe_slow ); %} +// fast search of substring with known size. +instruct string_indexof_con(eDIRegP str1, eDXRegI cnt1, eSIRegP str2, immI int_cnt2, + eBXRegI result, regXD vec, eAXRegI cnt2, eCXRegI tmp, eFlagsReg cr) %{ + predicate(UseSSE42Intrinsics); + match(Set result (StrIndexOf (Binary str1 cnt1) (Binary str2 int_cnt2))); + effect(TEMP vec, USE_KILL str1, USE_KILL str2, USE_KILL cnt1, KILL cnt2, KILL tmp, KILL cr); + + format %{ "String IndexOf $str1,$cnt1,$str2,$int_cnt2 -> $result // KILL $vec, $cnt1, $cnt2, $tmp" %} + ins_encode %{ + int icnt2 = (int)$int_cnt2$$constant; + if (icnt2 >= 8) { + // IndexOf for constant substrings with size >= 8 elements + // which don't need to be loaded through stack. + __ string_indexofC8($str1$$Register, $str2$$Register, + $cnt1$$Register, $cnt2$$Register, + icnt2, $result$$Register, + $vec$$XMMRegister, $tmp$$Register); + } else { + // Small strings are loaded through stack if they cross page boundary. + __ string_indexof($str1$$Register, $str2$$Register, + $cnt1$$Register, $cnt2$$Register, + icnt2, $result$$Register, + $vec$$XMMRegister, $tmp$$Register); + } + %} + ins_pipe( pipe_slow ); +%} + instruct string_indexof(eDIRegP str1, eDXRegI cnt1, eSIRegP str2, eAXRegI cnt2, - eBXRegI result, regXD tmp1, eCXRegI tmp2, eFlagsReg cr) %{ + eBXRegI result, regXD vec, eCXRegI tmp, eFlagsReg cr) %{ predicate(UseSSE42Intrinsics); match(Set result (StrIndexOf (Binary str1 cnt1) (Binary str2 cnt2))); - effect(TEMP tmp1, USE_KILL str1, USE_KILL str2, USE_KILL cnt1, USE_KILL cnt2, KILL tmp2, KILL cr); - - format %{ "String IndexOf $str1,$cnt1,$str2,$cnt2 -> $result // KILL $tmp2, $tmp1" %} + effect(TEMP vec, USE_KILL str1, USE_KILL str2, USE_KILL cnt1, USE_KILL cnt2, KILL tmp, KILL cr); + + format %{ "String IndexOf $str1,$cnt1,$str2,$cnt2 -> $result // KILL all" %} ins_encode %{ __ string_indexof($str1$$Register, $str2$$Register, - $cnt1$$Register, $cnt2$$Register, $result$$Register, - $tmp1$$XMMRegister, $tmp2$$Register); + $cnt1$$Register, $cnt2$$Register, + (-1), $result$$Register, + $vec$$XMMRegister, $tmp$$Register); %} ins_pipe( pipe_slow ); %}
--- a/src/cpu/x86/vm/x86_64.ad Thu Feb 24 14:49:34 2011 -0800 +++ b/src/cpu/x86/vm/x86_64.ad Sat Feb 26 12:10:54 2011 -0800 @@ -1,5 +1,5 @@ // -// Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved. +// Copyright (c) 2003, 2011, Oracle and/or its affiliates. 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 @@ -11598,18 +11598,48 @@ ins_pipe( pipe_slow ); %} +// fast search of substring with known size. +instruct string_indexof_con(rdi_RegP str1, rdx_RegI cnt1, rsi_RegP str2, immI int_cnt2, + rbx_RegI result, regD vec, rax_RegI cnt2, rcx_RegI tmp, rFlagsReg cr) +%{ + predicate(UseSSE42Intrinsics); + match(Set result (StrIndexOf (Binary str1 cnt1) (Binary str2 int_cnt2))); + effect(TEMP vec, USE_KILL str1, USE_KILL str2, USE_KILL cnt1, KILL cnt2, KILL tmp, KILL cr); + + format %{ "String IndexOf $str1,$cnt1,$str2,$int_cnt2 -> $result // KILL $vec, $cnt1, $cnt2, $tmp" %} + ins_encode %{ + int icnt2 = (int)$int_cnt2$$constant; + if (icnt2 >= 8) { + // IndexOf for constant substrings with size >= 8 elements + // which don't need to be loaded through stack. + __ string_indexofC8($str1$$Register, $str2$$Register, + $cnt1$$Register, $cnt2$$Register, + icnt2, $result$$Register, + $vec$$XMMRegister, $tmp$$Register); + } else { + // Small strings are loaded through stack if they cross page boundary. + __ string_indexof($str1$$Register, $str2$$Register, + $cnt1$$Register, $cnt2$$Register, + icnt2, $result$$Register, + $vec$$XMMRegister, $tmp$$Register); + } + %} + ins_pipe( pipe_slow ); +%} + instruct string_indexof(rdi_RegP str1, rdx_RegI cnt1, rsi_RegP str2, rax_RegI cnt2, - rbx_RegI result, regD tmp1, rcx_RegI tmp2, rFlagsReg cr) + rbx_RegI result, regD vec, rcx_RegI tmp, rFlagsReg cr) %{ predicate(UseSSE42Intrinsics); match(Set result (StrIndexOf (Binary str1 cnt1) (Binary str2 cnt2))); - effect(TEMP tmp1, USE_KILL str1, USE_KILL str2, USE_KILL cnt1, USE_KILL cnt2, KILL tmp2, KILL cr); - - format %{ "String IndexOf $str1,$cnt1,$str2,$cnt2 -> $result // KILL $tmp1, $tmp2" %} + effect(TEMP vec, USE_KILL str1, USE_KILL str2, USE_KILL cnt1, USE_KILL cnt2, KILL tmp, KILL cr); + + format %{ "String IndexOf $str1,$cnt1,$str2,$cnt2 -> $result // KILL all" %} ins_encode %{ __ string_indexof($str1$$Register, $str2$$Register, - $cnt1$$Register, $cnt2$$Register, $result$$Register, - $tmp1$$XMMRegister, $tmp2$$Register); + $cnt1$$Register, $cnt2$$Register, + (-1), $result$$Register, + $vec$$XMMRegister, $tmp$$Register); %} ins_pipe( pipe_slow ); %}
--- a/src/share/vm/opto/library_call.cpp Thu Feb 24 14:49:34 2011 -0800 +++ b/src/share/vm/opto/library_call.cpp Sat Feb 26 12:10:54 2011 -0800 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1999, 2010, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1999, 2011, Oracle and/or its affiliates. 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 @@ -1193,7 +1193,7 @@ Node* result; // Disable the use of pcmpestri until it can be guaranteed that // the load doesn't cross into the uncommited space. - if (false && Matcher::has_match_rule(Op_StrIndexOf) && + if (Matcher::has_match_rule(Op_StrIndexOf) && UseSSE42Intrinsics) { // Generate SSE4.2 version of indexOf // We currently only have match rules that use SSE4.2 @@ -1211,14 +1211,14 @@ return true; } + ciInstanceKlass* str_klass = env()->String_klass(); + const TypeOopPtr* string_type = TypeOopPtr::make_from_klass(str_klass); + // Make the merge point - RegionNode* result_rgn = new (C, 3) RegionNode(3); - Node* result_phi = new (C, 3) PhiNode(result_rgn, TypeInt::INT); + RegionNode* result_rgn = new (C, 4) RegionNode(4); + Node* result_phi = new (C, 4) PhiNode(result_rgn, TypeInt::INT); Node* no_ctrl = NULL; - ciInstanceKlass* klass = env()->String_klass(); - const TypeOopPtr* string_type = TypeOopPtr::make_from_klass(klass); - // Get counts for string and substr Node* source_cnta = basic_plus_adr(receiver, receiver, count_offset); Node* source_cnt = make_load(no_ctrl, source_cnta, TypeInt::INT, T_INT, string_type->add_offset(count_offset)); @@ -1236,6 +1236,17 @@ } if (!stopped()) { + // Check for substr count == 0 + cmp = _gvn.transform( new(C, 3) CmpINode(substr_cnt, intcon(0)) ); + bol = _gvn.transform( new(C, 2) BoolNode(cmp, BoolTest::eq) ); + Node* if_zero = generate_slow_guard(bol, NULL); + if (if_zero != NULL) { + result_phi->init_req(3, intcon(0)); + result_rgn->init_req(3, if_zero); + } + } + + if (!stopped()) { result = make_string_method_node(Op_StrIndexOf, receiver, source_cnt, argument, substr_cnt); result_phi->init_req(1, result); result_rgn->init_req(1, control()); @@ -1244,8 +1255,8 @@ record_for_igvn(result_rgn); result = _gvn.transform(result_phi); - } else { //Use LibraryCallKit::string_indexOf - // don't intrinsify is argument isn't a constant string. + } else { // Use LibraryCallKit::string_indexOf + // don't intrinsify if argument isn't a constant string. if (!argument->is_Con()) { return false; } @@ -1281,7 +1292,7 @@ // No null check on the argument is needed since it's a constant String oop. _sp -= 2; if (stopped()) { - return true; + return true; } // The null string as a pattern always returns 0 (match at beginning of string)
--- a/src/share/vm/opto/memnode.cpp Thu Feb 24 14:49:34 2011 -0800 +++ b/src/share/vm/opto/memnode.cpp Sat Feb 26 12:10:54 2011 -0800 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1997, 2011, Oracle and/or its affiliates. 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 @@ -1559,21 +1559,24 @@ phase->C->has_unsafe_access(), "Field accesses must be precise" ); // For oop loads, we expect the _type to be precise - if (OptimizeStringConcat && klass == phase->C->env()->String_klass() && + if (klass == phase->C->env()->String_klass() && adr->is_AddP() && off != Type::OffsetBot) { - // For constant Strings treat the fields as compile time constants. + // For constant Strings treat the final fields as compile time constants. Node* base = adr->in(AddPNode::Base); const TypeOopPtr* t = phase->type(base)->isa_oopptr(); if (t != NULL && t->singleton()) { - ciObject* string = t->const_oop(); - ciConstant constant = string->as_instance()->field_value_by_offset(off); - if (constant.basic_type() == T_INT) { - return TypeInt::make(constant.as_int()); - } else if (constant.basic_type() == T_ARRAY) { - if (adr->bottom_type()->is_ptr_to_narrowoop()) { - return TypeNarrowOop::make_from_constant(constant.as_object()); - } else { - return TypeOopPtr::make_from_constant(constant.as_object()); + ciField* field = phase->C->env()->String_klass()->get_field_by_offset(off, false); + if (field != NULL && field->is_final()) { + ciObject* string = t->const_oop(); + ciConstant constant = string->as_instance()->field_value(field); + if (constant.basic_type() == T_INT) { + return TypeInt::make(constant.as_int()); + } else if (constant.basic_type() == T_ARRAY) { + if (adr->bottom_type()->is_ptr_to_narrowoop()) { + return TypeNarrowOop::make_from_constant(constant.as_object()); + } else { + return TypeOopPtr::make_from_constant(constant.as_object()); + } } } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/compiler/6942326/Test.java Sat Feb 26 12:10:54 2011 -0800 @@ -0,0 +1,409 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. 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 + * @bug 6942326 + * @summary x86 code in string_indexof() could read beyond reserved heap space + * + * @run main/othervm/timeout=300 -Xmx32m -Xbatch -XX:+IgnoreUnrecognizedVMOptions -XX:CompileCommand=exclude,Test,main -XX:CompileCommand=exclude,Test,test_varsub_indexof -XX:CompileCommand=exclude,Test,test_varstr_indexof -XX:CompileCommand=exclude,Test,test_missub_indexof -XX:CompileCommand=exclude,Test,test_consub_indexof -XX:CompileCommand=exclude,Test,test_conmis_indexof -XX:CompileCommand=exclude,Test,test_subcon Test + * + */ + +public class Test { + + static String[] strings = new String[1024]; + private static final int ITERATIONS = 100000; + + public static void main(String[] args) { + + long start_total = System.currentTimeMillis(); + + // search variable size substring in string (33 chars). + String a = " 1111111111111xx1111111111111xx11y"; // +1 to execute a.substring(1) first + String b = "1111111111111xx1111111111111xx11y"; + test_varsub_indexof(a, b); + + // search variable size substring in string (32 chars). + a = " 1111111111111xx1111111111111xx1y"; + b = "1111111111111xx1111111111111xx1y"; + test_varsub_indexof(a, b); + + // search variable size substring in string (17 chars). + a = " 1111111111111xx1y"; + b = "1111111111111xx1y"; + test_varsub_indexof(a, b); + + // search variable size substring in string (16 chars). + a = " 111111111111xx1y"; + b = "111111111111xx1y"; + test_varsub_indexof(a, b); + + // search variable size substring in string (8 chars). + a = " 1111xx1y"; + b = "1111xx1y"; + test_varsub_indexof(a, b); + + // search variable size substring in string (7 chars). + a = " 111xx1y"; + b = "111xx1y"; + test_varsub_indexof(a, b); + + + + // search substring (17 chars) in variable size string. + a = "1111111111111xx1x"; + b = " 1111111111111xx1111111111111xx1x"; // +1 to execute b.substring(1) first + test_varstr_indexof(a, b); + + // search substring (16 chars) in variable size string. + a = "111111111111xx1x"; + b = " 1111111111111xx1111111111111xx1x"; + test_varstr_indexof(a, b); + + // search substring (9 chars) in variable size string. + a = "11111xx1x"; + b = " 1111111111111xx1111111111111xx1x"; + test_varstr_indexof(a, b); + + // search substring (8 chars) in variable size string. + a = "1111xx1x"; + b = " 1111111111111xx1111111111111xx1x"; + test_varstr_indexof(a, b); + + // search substring (4 chars) in variable size string. + a = "xx1x"; + b = " 1111111111111xx1111111111111xx1x"; + test_varstr_indexof(a, b); + + // search substring (3 chars) in variable size string. + a = "x1x"; + b = " 1111111111111xx1111111111111xx1x"; + test_varstr_indexof(a, b); + + // search substring (2 chars) in variable size string. + a = "1y"; + b = " 1111111111111xx1111111111111xx1y"; + test_varstr_indexof(a, b); + + + + // search non matching variable size substring in string (33 chars). + a = " 1111111111111xx1111111111111xx11z"; // +1 to execute a.substring(1) first + b = "1111111111111xx1111111111111xx11y"; + test_missub_indexof(a, b); + + // search non matching variable size substring in string (32 chars). + a = " 1111111111111xx1111111111111xx1z"; + b = "1111111111111xx1111111111111xx1y"; + test_missub_indexof(a, b); + + // search non matching variable size substring in string (17 chars). + a = " 1111111111111xx1z"; + b = "1111111111111xx1y"; + test_missub_indexof(a, b); + + // search non matching variable size substring in string (16 chars). + a = " 111111111111xx1z"; + b = "111111111111xx1y"; + test_missub_indexof(a, b); + + // search non matching variable size substring in string (8 chars). + a = " 1111xx1z"; + b = "1111xx1y"; + test_missub_indexof(a, b); + + // search non matching variable size substring in string (7 chars). + a = " 111xx1z"; + b = "111xx1y"; + test_missub_indexof(a, b); + + + + // Testing constant substring search in variable size string. + + // search constant substring (17 chars). + b = " 1111111111111xx1111111111111xx1x"; // +1 to execute b.substring(1) first + TestCon tc = new TestCon17(); + test_consub_indexof(tc, b); + + // search constant substring (16 chars). + b = " 1111111111111xx1111111111111xx1x"; + tc = new TestCon16(); + test_consub_indexof(tc, b); + + // search constant substring (9 chars). + b = " 1111111111111xx1111111111111xx1x"; + tc = new TestCon9(); + test_consub_indexof(tc, b); + + // search constant substring (8 chars). + b = " 1111111111111xx1111111111111xx1x"; + tc = new TestCon8(); + test_consub_indexof(tc, b); + + // search constant substring (4 chars). + b = " 1111111111111xx1111111111111xx1x"; + tc = new TestCon4(); + test_consub_indexof(tc, b); + + // search constant substring (3 chars). + b = " 1111111111111xx1111111111111xx1x"; + tc = new TestCon3(); + test_consub_indexof(tc, b); + + // search constant substring (2 chars). + b = " 1111111111111xx1111111111111xx1y"; + tc = new TestCon2(); + test_consub_indexof(tc, b); + + // search constant substring (1 chars). + b = " 1111111111111xx1111111111111xx1y"; + tc = new TestCon1(); + test_consub_indexof(tc, b); + + + // search non matching constant substring (17 chars). + b = " 1111111111111xx1111111111111xx1z"; // +1 to execute b.substring(1) first + tc = new TestCon17(); + test_conmis_indexof(tc, b); + + // search non matching constant substring (16 chars). + b = " 1111111111111xx1111111111111xx1z"; + tc = new TestCon16(); + test_conmis_indexof(tc, b); + + // search non matching constant substring (9 chars). + b = " 1111111111111xx1111111111111xx1z"; + tc = new TestCon9(); + test_conmis_indexof(tc, b); + + // search non matching constant substring (8 chars). + b = " 1111111111111xx1111111111111xx1z"; + tc = new TestCon8(); + test_conmis_indexof(tc, b); + + // search non matching constant substring (4 chars). + b = " 1111111111111xx1111111111111xx1z"; + tc = new TestCon4(); + test_conmis_indexof(tc, b); + + // search non matching constant substring (3 chars). + b = " 1111111111111xx1111111111111xx1z"; + tc = new TestCon3(); + test_conmis_indexof(tc, b); + + // search non matching constant substring (2 chars). + b = " 1111111111111xx1111111111111xx1z"; + tc = new TestCon2(); + test_conmis_indexof(tc, b); + + // search non matching constant substring (1 chars). + b = " 1111111111111xx1111111111111xx1z"; + tc = new TestCon1(); + test_conmis_indexof(tc, b); + + long end_total = System.currentTimeMillis(); + System.out.println("End run time: " + (end_total - start_total)); + + } + + public static long test_init(String a, String b) { + for (int i = 0; i < 512; i++) { + strings[i * 2] = new String(b.toCharArray()); + strings[i * 2 + 1] = new String(a.toCharArray()); + } + System.out.print(a.length() + " " + b.length() + " "); + return System.currentTimeMillis(); + } + + public static void test_end(String a, String b, int v, int expected, long start) { + long end = System.currentTimeMillis(); + int res = (v/ITERATIONS); + System.out.print(" " + res); + System.out.println(" time:" + (end - start)); + if (res != expected) { + System.out.println("wrong indexOf result: " + res + ", expected " + expected); + System.out.println("\"" + b + "\".indexOf(\"" + a + "\")"); + System.exit(97); + } + } + + public static int test_subvar() { + int s = 0; + int v = 0; + for (int i = 0; i < ITERATIONS; i++) { + v += strings[s].indexOf(strings[s + 1]); + s += 2; + if (s >= strings.length) s = 0; + } + return v; + } + + public static void test_varsub_indexof(String a, String b) { + System.out.println("Start search variable size substring in string (" + b.length() + " chars)"); + long start_it = System.currentTimeMillis(); + int limit = 1; // last a.length() == 1 + while (a.length() > limit) { + a = a.substring(1); + long start = test_init(a, b); + int v = test_subvar(); + test_end(a, b, v, (b.length() - a.length()), start); + } + long end_it = System.currentTimeMillis(); + System.out.println("End search variable size substring in string (" + b.length() + " chars), time: " + (end_it - start_it)); + } + + public static void test_varstr_indexof(String a, String b) { + System.out.println("Start search substring (" + a.length() + " chars) in variable size string"); + long start_it = System.currentTimeMillis(); + int limit = a.length(); + while (b.length() > limit) { + b = b.substring(1); + long start = test_init(a, b); + int v = test_subvar(); + test_end(a, b, v, (b.length() - a.length()), start); + } + long end_it = System.currentTimeMillis(); + System.out.println("End search substring (" + a.length() + " chars) in variable size string, time: " + (end_it - start_it)); + } + + public static void test_missub_indexof(String a, String b) { + System.out.println("Start search non matching variable size substring in string (" + b.length() + " chars)"); + long start_it = System.currentTimeMillis(); + int limit = 1; // last a.length() == 1 + while (a.length() > limit) { + a = a.substring(1); + long start = test_init(a, b); + int v = test_subvar(); + test_end(a, b, v, (-1), start); + } + long end_it = System.currentTimeMillis(); + System.out.println("End search non matching variable size substring in string (" + b.length() + " chars), time: " + (end_it - start_it)); + } + + + + public static void test_consub_indexof(TestCon tc, String b) { + System.out.println("Start search constant substring (" + tc.constr().length() + " chars)"); + long start_it = System.currentTimeMillis(); + int limit = tc.constr().length(); + while (b.length() > limit) { + b = b.substring(1); + long start = test_init(tc.constr(), b); + int v = test_subcon(tc); + test_end(tc.constr(), b, v, (b.length() - tc.constr().length()), start); + } + long end_it = System.currentTimeMillis(); + System.out.println("End search constant substring (" + tc.constr().length() + " chars), time: " + (end_it - start_it)); + } + + public static void test_conmis_indexof(TestCon tc, String b) { + System.out.println("Start search non matching constant substring (" + tc.constr().length() + " chars)"); + long start_it = System.currentTimeMillis(); + int limit = tc.constr().length(); + while (b.length() > limit) { + b = b.substring(1); + long start = test_init(tc.constr(), b); + int v = test_subcon(tc); + test_end(tc.constr(), b, v, (-1), start); + } + long end_it = System.currentTimeMillis(); + System.out.println("End search non matching constant substring (" + tc.constr().length() + " chars), time: " + (end_it - start_it)); + } + + public static int test_subcon(TestCon tc) { + int s = 0; + int v = 0; + for (int i = 0; i < ITERATIONS; i++) { + v += tc.indexOf(strings[s]); + s += 2; + if (s >= strings.length) s = 0; + } + return v; + } + + private interface TestCon { + public String constr(); + public int indexOf(String str); + } + + // search constant substring (17 chars). + private final static class TestCon17 implements TestCon { + private static final String constr = "1111111111111xx1x"; + public String constr() { return constr; } + public int indexOf(String str) { return str.indexOf(constr); } + } + + // search constant substring (16 chars). + private final static class TestCon16 implements TestCon { + private static final String constr = "111111111111xx1x"; + public String constr() { return constr; } + public int indexOf(String str) { return str.indexOf(constr); } + } + + // search constant substring (9 chars). + private final static class TestCon9 implements TestCon { + private static final String constr = "11111xx1x"; + public String constr() { return constr; } + public int indexOf(String str) { return str.indexOf(constr); } + } + + // search constant substring (8 chars). + private final static class TestCon8 implements TestCon { + private static final String constr = "1111xx1x"; + public String constr() { return constr; } + public int indexOf(String str) { return str.indexOf(constr); } + } + + // search constant substring (4 chars). + private final static class TestCon4 implements TestCon { + private static final String constr = "xx1x"; + public String constr() { return constr; } + public int indexOf(String str) { return str.indexOf(constr); } + } + + // search constant substring (3 chars). + private final static class TestCon3 implements TestCon { + private static final String constr = "x1x"; + public String constr() { return constr; } + public int indexOf(String str) { return str.indexOf(constr); } + } + + // search constant substring (2 chars). + private final static class TestCon2 implements TestCon { + private static final String constr = "1y"; + public String constr() { return constr; } + public int indexOf(String str) { return str.indexOf(constr); } + } + + + // search constant substring (1 chars). + private final static class TestCon1 implements TestCon { + private static final String constr = "y"; + public String constr() { return constr; } + public int indexOf(String str) { return str.indexOf(constr); } + } +} +