Re: Encode UTF-8 optimizations
[email protected] (Karl Williamson) Sat, 20 Aug 2016 19:10:40 -0600
| Newsgroups | perl.unicode |
|---|---|
| Message-ID | <[email protected]> |
--------------6F0358D95FA98F99E47C732E Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit Top posting. Attached is my alternative patch. It effectively uses a different algorithm to avoid decoding the input into code points, and to copy all spans of valid input at once, instead of character at a time. And it uses only currently available functions. Any of these that are missing or buggy in previous perls can and will be dealt with by the Devel::PPPort mechanism. On 08/19/2016 02:42 AM, [email protected] wrote: > On Thursday 18 August 2016 23:06:27 Karl Williamson wrote: >> On 08/12/2016 09:31 AM, [email protected] wrote: >>> On Thursday 11 August 2016 17:41:23 Karl Williamson wrote: >>>> On 07/09/2016 05:12 PM, [email protected] wrote: >>>>> Hi! As we know utf8::encode() does not provide correct UTF-8 encoding >>>>> and Encode::encode("UTF-8", ...) should be used instead. Also opening >>>>> file should be done by :encoding(UTF-8) layer instead :utf8. >>>>> >>>>> But UTF-8 strict implementation in Encode module is horrible slow when >>>>> comparing to utf8::encode(). It is implemented in Encode.xs file and for >>>>> benchmarking can be this XS implementation called directly by: >>>>> >>>>> use Encode; >>>>> my $output = Encode::utf8::encode_xs({strict_utf8 => 1}, $input) >>>>> >>>>> (without overhead of Encode module...) >>>>> >>>>> Here are my results on 160 bytes long input string: >>>>> >>>>> Encode::utf8::encode_xs({strict_utf8 => 1}, ...): 8 wallclock secs ( 8.56 usr + >>> 0.00 sys = 8.56 CPU) @ 467289.72/s (n=4000000) >>>>> Encode::utf8::encode_xs({strict_utf8 => 0}, ...): 1 wallclock secs ( 1.66 usr + >>> 0.00 sys = 1.66 CPU) @ 2409638.55/s (n=4000000) >>>>> utf8::encode: 1 wallclock secs ( 0.39 usr + 0.00 sys = 0.39 CPU) @ >>> 10256410.26/s (n=4000000) >>>>> >>>>> I found two bottle necks (slow sv_catpv* and utf8n_to_uvuni functions) >>>>> and did some optimizations. Final results are: >>>>> >>>>> Encode::utf8::encode_xs({strict_utf8 => 1}, ...): 2 wallclock secs ( 3.27 usr + >>> 0.00 sys = 3.27 CPU) @ 1223241.59/s (n=4000000) >>>>> Encode::utf8::encode_xs({strict_utf8 => 0}, ...): 1 wallclock secs ( 1.68 usr + >>> 0.00 sys = 1.68 CPU) @ 2380952.38/s (n=4000000) >>>>> utf8::encode: 1 wallclock secs ( 0.40 usr + 0.00 sys = 0.40 CPU) @ >>> 10000000.00/s (n=4000000) >>>>> >>>>> Patches are on github at pull request: >>>>> https://github.com/dankogai/p5-encode/pull/56 >>>>> >>>>> I would like if somebody review my patches and tell if this is the >>>>> right way for optimizations... >>>>> >>>> >>>> I'm sorry that this slipped off my radar until I saw it in the new Encode >>>> release >>>> >>>> There are a couple of things I see wrong with your patch. >>>> >>>> 1) It does not catch the malformation of an overlong sequence. This is a >>>> serious malformation which has been used for attacks. Basically, after you >>>> get the result, you need to check that it is the expected length for that >>>> result. For example, \xC2\x80 will have an input length of 2, and evaluates >>>> to \x00, whose expected length is 1, and so the input is overlong. In >>>> modern perls, you can just do an OFFUNISKIP(uv) and compare that with the >>>> passed-in length. This can be rewritten for perls back to 5.8 using >>>> UNI_SKIP and UNI_TO_NATIVE >>> >>> I do not see where can be a problem. At least I think my patches should >>> be compatible with previous implementation of Encode.xs... >>> >>> First UTF8_IS_INVARIANT is checked and one character processed. >>> >>> Otherwise UTF8_IS_START is checked and UTF8SKIP is used to get length of >>> sequence. And then len-1 characters are checked if they pass test for >>> UTF8_IS_CONTINUATION. >>> >>> If there are less characters then following does not >>> UTF8_IS_CONTINUATION and error is reported. If there are more, then next >>> iteration of loop starts and it fail on both UTF8_IS_CONTINUATION and >>> UTF8_IS_START. >>> >>> Can you describe in details what do you think it wrong and how to do >>> that attack? >> >> This discussion has been active at >> https://github.com/dankogai/p5-encode/issues/64 >> >> For the curious out there, please refer to that discussion. My bottom line >> is that I have come to believe the security risks are too high to have >> modules do their own security checking for UTF-8 correctness. >>> >>>> 2) It does not work on EBCDIC platforms. The NATIVE_TO_UTF() call is a good >>>> start, but the result uv needs to be transformed back to native, using >>>> UNI_TO_NATIVE(uv). >>> >>> uv is used just to check if it is valid Unicode code point. Real value >>> is used only for error/warn message. Previous implementation used >>> utf8n_to_uvuni which convert return value with NATIVE_TO_UNI. >> >> As I said on that other thread, if this is really true, then it's faster to >> use a boolean function to verify the inputs. > > Value of uv is used only in warn/error message. > >> Also, performance should not >> be a consideration for errors or warnings. One can check validity fast; and >> then spend the time getting the message right in the rare cases where a >> message is generated. > > Yes, fully I agree. > >>>> 3) The assumptions the subroutine runs under need to be documented for >>>> future maintainers and code readers. For example, it assumes that there is >>>> enough space in the input to hold all the bytes. >>> >>> Function process_utf8 does not assume that. It calls SvGROW to increase >>> buffer size when needed. >> >> You misunderstand what I meant here. The bottom line is your patch adds a >> significant amount of code without any comments in a risky area. The name >> of the function does not indicate that its value is to be thrown away, and >> even after looking at the code that calls it some more, it's not obvious to >> me that the value isn't kept. All subtleties in code should be commented in >> that code. To do otherwise is a disservice to future maintainers. I >> personally will never push to blead someone's commit that I think unfairly >> burdens future maintainers. One of the subtleties of this function is that >> it doesn't check that it is not running off the end of the buffer. It >> relies on the caller to do that check, but someone coming along might see >> that function and think from its name that it's more general purpose than it >> actually is. Someone looking at its name and return value would likely >> think it generates a valid code point from UTF-8 input. > > It is intended to do not add another non-needed checks as it again slow > down function performance. Checks are done before on another place and > that function is designed to be used only in Encode's process_utf8. > > So rather write comments/description about that function. But on the > other hand, I dislike comments which just write what is function doing > in case that comments are longer then function code itself. Then it is > easier to read function code itself and so whole comment is useless... > >>>> Other than that, it looks ok to me. But, to be sure, I think you should run >>>> it on the tests included in the core t/op/utf8decode.t which came from an >>>> internet repository of edge cases. >> >> I later realized that under non-strict calls, this can overflow, and there >> is some code in your amendments to this patch that check that. I have not >> looked those over. > > Yes, check for overlong and overflow is there... > >> But again, I don't think Encode should undertake its own security checking. >> I'm willing to work with you to get something in core that adequately meets >> Encode's needs. > > Ok. We can discuss about it. First I see there big problems: > > 1) Encode module is for Perl 5.8+. In 5.8+ perl's versions will never be > your (new) functions, so Encode module needs to have at least copy of > them. And this does not solve problem which you want to prevent :-( > > 2) Functions must be defined and declared in some header file. So C > compiler can inline and optimize them in Encode module. Calling such > hot function via shared library must be avoided. > > 3) Such function needs to be designed in way that it do only what is > needed in case for Encode module. On the other hand I do not think it > is good idea to create special function just for Encode module living > in core perl... But maybe general-useful function can be designed. > >>> How to use and run that test with Encode? >> >> It looks like you figured that out for the most part in your amended >> patches. > > Yes, meanwhile you wrote reply, I figured out about those problems and > also copied those tests :-) Anyway, test for EBCDIC are missing in core. > --------------6F0358D95FA98F99E47C732E Content-Type: text/x-diff; name="0001-Speed-up-Encode-UTF-8-validation-checking.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename*0="0001-Speed-up-Encode-UTF-8-validation-checking.patch" From 1dada0ad113474081ad9590d9d154c2981c71909 Mon Sep 17 00:00:00 2001 From: Karl Williamson <[email protected]> Date: Sat, 20 Aug 2016 15:16:06 -0600 Subject: [PATCH] Speed up Encode UTF-8 validation checking This replaces the current scheme for checking UTF-8 validity by one in which normal processing doesn't require having to decode the UTF-8 into code points. The copying of characters individually from the input to the output is changed to be a single operation for each entire span of valid input at once. Thus in the normal case, what ends up happening is a tight loop to check the validity, and then a memmove of the entire input to the output, then return. If an error is found, it copies all the valid input before the error, then handles the character in error, then positions to the next input position and repeats. It uses the functionality available from the Perl 5 core to to look at just the bytes that comprise the UTF-8 to make the determination, converting to code points only those that are defective some how in order to display them in warnings and error messages. (The core macro it calls,isUTF8_CHAR(), currently does convert extremely large code points as well, only those well above any legal Unicode ones, and hence extremely unlikely to be encountered in practice.) Thus, this does not need to know about the intricacies of UTF-8 malformations, relying on the core to handle this. Not all the core facilities used are in the public API. That was true of the implementation this replaces as well. I'm confident enough in all the ones it does use to put them in the API. I have not looked at previous Perl versions to see how this would work on them. That will have to be tested and ppport used to overcome this. That should be done anyway to make sure we've got less buggy Unicode handling code available to older modules. --- cpan/Encode/Encode.xs | 109 ++++++++++++++++++++++++++++++-------------------- 1 file changed, 65 insertions(+), 44 deletions(-) diff --git a/cpan/Encode/Encode.xs b/cpan/Encode/Encode.xs index 222f39b..5ba9b1d 100644 --- a/cpan/Encode/Encode.xs +++ b/cpan/Encode/Encode.xs @@ -318,6 +318,37 @@ strict_utf8(pTHX_ SV* sv) return SvTRUE(*svp); } +static bool +is_strict_utf8_string_loc(const U8* const s, STRLEN const len, const U8 **ep) +{ + /* Returns a boolean giving whether or not the input string from 's' to + * ('s' + 'len' - 1) is well-formed UTF-8 that is entirely Unicode code + * points that aren't surrogates nor non-character code points. *ep is set + * to point to 1 byte beyond the end of the final valid input character */ + + const U8* const send = s + len; + const U8* x = s; + + while (x < send) { + const STRLEN char_len = isUTF8_CHAR(x, send); + + if ( UNLIKELY(! char_len) + || ( UNLIKELY(isUTF8_POSSIBLY_PROBLEMATIC(*x)) + && ( UNLIKELY(UTF8_IS_SURROGATE(x, send)) + || UNLIKELY(UTF8_IS_SUPER(x, send)) + || UNLIKELY(UTF8_IS_NONCHAR(x, send))))) + { + *ep = x; + return FALSE; + } + + x += char_len; + } + + *ep = x; + return TRUE; +} + static U8* process_utf8(pTHX_ SV* dst, U8* s, U8* e, SV *check_sv, bool encode, bool strict, bool stop_at_partial) @@ -346,59 +377,49 @@ process_utf8(pTHX_ SV* dst, U8* s, U8* e, SV *check_sv, d = (U8 *) SvGROW(dst, dlen); while (s < e) { - if (UTF8_IS_INVARIANT(*s)) { - *d++ = *s++; - continue; + const U8* e_or_where_failed; + + bool valid = (strict) + ? is_strict_utf8_string_loc(s, e - s, &e_or_where_failed) + : is_utf8_string_loc (s, e - s, &e_or_where_failed); + STRLEN len = e_or_where_failed - s; + + Move(s, d, len, U8); + d += len; + s = (U8 *) e_or_where_failed; + + if (LIKELY(valid)) { + break; } - if (UTF8_IS_START(*s)) { - U8 skip = UTF8SKIP(s); - if ((s + skip) > e) { - if (stop_at_partial || (check & ENCODE_STOP_AT_PARTIAL)) { - const U8 *p = s + 1; - for (; p < e; p++) { - if (!UTF8_IS_CONTINUATION(*p)) - goto malformed_byte; - } - break; - } - - goto malformed_byte; + if ( (stop_at_partial || (check & ENCODE_STOP_AT_PARTIAL)) + && s + UTF8SKIP(s) >= e) + { + const U8* x; + + if (UNLIKELY(! UTF8_IS_START(*s))) { + goto malformed; } - uv = utf8n_to_uvuni(s, e - s, &ulen, - UTF8_CHECK_ONLY | (strict ? UTF8_ALLOW_STRICT : - UTF8_ALLOW_NONSTRICT) - ); -#if 1 /* perl-5.8.6 and older do not check UTF8_ALLOW_LONG */ - if (strict && uv > PERL_UNICODE_MAX) - ulen = (STRLEN) -1; -#endif - if (ulen == (STRLEN) -1) { - if (strict) { - uv = utf8n_to_uvuni(s, e - s, &ulen, - UTF8_CHECK_ONLY | UTF8_ALLOW_NONSTRICT); - if (ulen == (STRLEN) -1) - goto malformed_byte; + for (x = s + 1; x < e; x++) { + if (UNLIKELY (! UTF8_IS_CONTINUATION(*x))) goto malformed; - } - goto malformed_byte; } - - /* Whole char is good */ - memcpy(d, s, skip); - d += skip; - s += skip; - continue; + break; } - /* If we get here there is something wrong with alleged UTF-8 */ - malformed_byte: - uv = (UV)*s; - ulen = 1; + malformed: + + if (! isUTF8_CHAR(s, e)) { + uv = (UV)*s; + ulen = 1; + } + else { + uv = utf8n_to_uvchr(s, e - s, &ulen, + UTF8_CHECK_ONLY | UTF8_ALLOW_NONSTRICT); + } - malformed: if (check & ENCODE_DIE_ON_ERR){ if (encode) Perl_croak(aTHX_ ERR_ENCODE_NOMAP, uv, "utf8"); @@ -414,7 +435,7 @@ process_utf8(pTHX_ SV* dst, U8* s, U8* e, SV *check_sv, ERR_DECODE_NOMAP, "utf8", uv); } if (check & ENCODE_RETURN_ON_ERR) { - break; + break; } if (check & (ENCODE_PERLQQ|ENCODE_HTMLCREF|ENCODE_XMLCREF)){ SV* subchar = -- 2.5.0 --------------6F0358D95FA98F99E47C732E--