Still Very very slow inside CollationBuilder::addRelation when we have Hangul

General

Other Data

General

Other Data

Description

downstream bug https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=62639

stacktrace

#13 0x811856 in registerNode icu/icu4c/source/common/stringtriebuilder.cpp:328:29

#14 0x811856 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:254:12

#15 0x813b04 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:297:33

#16 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#17 0x813f77 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:306:29

#18 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#19 0x810f06 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:229:24

#20 0x813b04 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:297:33

#21 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#22 0x810f06 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:229:24

#23 0x813b04 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:297:33

#24 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#25 0x810f06 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:229:24

#26 0x813b04 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:297:33

#27 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#28 0x813f77 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:306:29

#29 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#30 0x813f77 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:306:29

#31 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#32 0x810f06 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:229:24

#33 0x813f77 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:306:29

#34 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#35 0x810f06 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:229:24

#36 0x813f77 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:306:29

#37 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#38 0x813b04 in icu_74::StringTrieBuilder::makeBranchSubNode(int, int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:297:33

#39 0x8112a1 in icu_74::StringTrieBuilder::makeNode(int, int, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:244:23

#40 0x810414 in icu_74::StringTrieBuilder::build(UStringTrieBuildOption, int, UErrorCode&) icu/icu4c/source/common/stringtriebuilder.cpp:74:20

#41 0x6d0765 in icu_74::UCharsTrieBuilder::buildUChars(UStringTrieBuildOption, UErrorCode&) icu/icu4c/source/common/ucharstriebuilder.cpp:223:24

#42 0x6d1187 in icu_74::UCharsTrieBuilder::buildUnicodeString(UStringTrieBuildOption, icu_74::UnicodeString&, UErrorCode&) icu/icu4c/source/common/ucharstriebuilder.cpp:164:5

#43 0x59410e in icu_74::CollationDataBuilder::addContextTrie(unsigned int, icu_74::UCharsTrieBuilder&, UErrorCode&) icu/icu4c/source/i18n/collationdatabuilder.cpp:1617:32

#44 0x58602c in icu_74::CollationDataBuilder::buildContext(icu_74::ConditionalCE32*, UErrorCode&) icu/icu4c/source/i18n/collationdatabuilder.cpp:1579:29

#45 0x5843b9 in icu_74::DataBuilderCollationIterator::getCE32FromBuilderData(unsigned int, UErrorCode&) icu/icu4c/source/i18n/collationdatabuilder.cpp:284:39

#46 0x5a9f65 in icu_74::CollationIterator::appendCEsFromCE32(icu_74::CollationData const*, int, unsigned int, signed char, UErrorCode&) icu/icu4c/source/i18n/collationiterator.cpp:293:20

#47 0x58357f in icu_74::DataBuilderCollationIterator::fetchCEs(icu_74::UnicodeString const&, int, long*, int) icu/icu4c/source/i18n/collationdatabuilder.cpp:207:9

#48 0x5948a6 in icu_74::CollationDataBuilder::getCEs(icu_74::UnicodeString const&, int, long*, int) icu/icu4c/source/i18n/collationdatabuilder.cpp:1678:22

#49 0x595002 in icu_74::CollationDataBuilder::getCEs(icu_74::UnicodeString const&, icu_74::UnicodeString const&, long*, int) icu/icu4c/source/i18n/collationdatabuilder.cpp:1665:16

#50 0x57b34d in addIfDifferent icu/icu4c/source/i18n/collationbuilder.cpp:1356:41

#51 0x57b34d in icu_74::CollationBuilder::addOnlyClosure(icu_74::UnicodeString const&, icu_74::UnicodeString const&, long const*, int, unsigned int, UErrorCode&) icu/icu4c/source/i18n/collationbuilder.cpp:1131:20

#52 0x57a69f in icu_74::CollationBuilder::addWithClosure(icu_74::UnicodeString const&, icu_74::UnicodeString const&, long const*, int, unsigned int, UErrorCode&) icu/icu4c/source/i18n/collationbuilder.cpp:1111:12

#53 0x57797e in icu_74::CollationBuilder::addRelation(int, icu_74::UnicodeString const&, icu_74::UnicodeString const&, icu_74::UnicodeString const&, char const*&, UErrorCode&) icu/icu4c/source/i18n/collationbuilder.cpp:756:9

#54 0x5c3fb5 in icu_74::CollationRuleParser::parseRelationStrings(int, int, UErrorCode&) icu/icu4c/source/i18n/collationruleparser.cpp:284:11

#55 0x5bb68b in icu_74::CollationRuleParser::parseRuleChain(UErrorCode&) icu/icu4c/source/i18n/collationruleparser.cpp:163:13

#56 0x5badd7 in icu_74::CollationRuleParser::parse(icu_74::UnicodeString const&, UErrorCode&) icu/icu4c/source/i18n/collationruleparser.cpp:102:13

#57 0x5ba9af in icu_74::CollationRuleParser::parse(icu_74::UnicodeString const&, icu_74::CollationSettings&, UParseError*, UErrorCode&) icu/icu4c/source/i18n/collationruleparser.cpp:85:5

#58 0x56e239 in icu_74::CollationBuilder::parseAndBuild(icu_74::UnicodeString const&, unsigned char const*, icu_74::CollationRuleParser::Importer*, UParseError*, UErrorCode&) icu/icu4c/source/i18n/collationbuilder.cpp:258:12

#59 0x56d3f1 in icu_74::RuleBasedCollator::internalBuildTailoring(icu_74::UnicodeString const&, int, UColAttributeValue, UParseError*, icu_74::UnicodeString*, UErrorCode&) icu/icu4c/source/i18n/collationbuilder.cpp:170:48

#60 0x56d109 in icu_74::RuleBasedCollator::RuleBasedCollator(icu_74::UnicodeString const&, UErrorCode&) icu/icu4c/source/i18n/collationbuilder.cpp:103:5

#61 0x56ca78 in LLVMFuzzerTestOneInput icu/icu4c/source/test/fuzzer/collator_rulebased_fuzzer.cpp:23:11

#62 0x43e193 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) /src/llvm-project/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:611:15

#63 0x4298f2 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) /src/llvm-project/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:324:6

#64 0x42f19c in fuzzer::FuzzerDriver(int*, char**, int ()(unsigned char const*, unsigned long)) /src/llvm-project/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:860:9

#65 0x4586d2 in main /src/llvm-project/compiler-rt/lib/fuzzer/FuzzerMain.cpp:20:10

#66 0x7b01a3dfd082 in __libc_start_main /build/glibc-SzIz7B/glibc-2.31/csu/libc-start.c:308:16

#67 0x41fabd in _start

Linked work items

clones

ICU-22517

Very very slow inside CollationBuilder::addRelation when we have Hangul

Activity

Show:

Frank Yung-Fong Tang

October 13, 2023 at 11:29 PM

Since the issue is accepted by ICU TC for 74-1 in https://unicode-org.atlassian.net/browse/ICU-22517, I mark this left over also as accepted.

Frank Yung-Fong Tang

October 13, 2023 at 8:56 PM

fix in https://github.com/unicode-org/icu/pull/2672

Frank Yung-Fong Tang

October 13, 2023 at 8:52 PM

This is a clone of https://unicode-org.atlassian.net/browse/ICU-22517 because the limit we set in https://github.com/unicode-org/icu/pull/2629 is still causing the timeout but it is too late to land it in 74.1. Therefore I clone this out for 75.1 to land a change of the limit

Resize issue view side panel

Fixed

Details

Assignee

Frank Yung-Fong Tang

Reporter

Frank Yung-Fong Tang

Components

collation

Labels

Priority

assess

Time Needed

Hours

Fix versions

75.1

Created October 13, 2023 at 8:50 PM

Updated May 1, 2025 at 3:53 PM

Resolved October 25, 2023 at 12:22 AM