Re: [devel] rust-1:1.50.0-alt1: Sisyphus/x86_64 test rebuild failed

Re: [devel] rust-1:1.50.0-alt1: Sisyphus/x86_64 test rebuild failed

[Alexey Gladkov]

On Sat, May 01, 2021 at 06:44:31AM +0000, ALT beekeeper wrote:
> Package: rust-1:1.50.0-alt1
> Status: Sisyphus/x86_64 test rebuild failed
> URL: http://git.altlinux.org/beehive/logs/Sisyphus/x86_64/archive/2021/0501/error/rust-1:1.50.0-alt1
> Cannot build this package.
> Please investigate.
> Excerpt from build log:
> 
> Verifying ELF objects in /usr/src/tmp/rust-buildroot (arch=normal,fhs=normal,lfs=relaxed,lint=relaxed,rpath=normal,stack=normal,textrel=normal,unresolved=normal)
> section [39] '.symtab': symbol 13269 (_ZN3std9panicking11panic_count17LOCAL_PANIC_COUNT7__getit5__KEY17h12fb9976e0c26702E.llvm.13708256337585169031) does not fit completely in referenced section [21] '.tbss'
> verify-elf: WARNING: ./usr/bin/rustfmt: eu-elflint failed
> section [39] '.symtab': symbol 27618 (_ZN12thread_local9thread_id9THREAD_ID7__getit5__KEY17h8994e316e1ec1334E) does not fit completely in referenced section [21] '.tbss'
> verify-elf: WARNING: ./usr/bin/rls: eu-elflint failed
> section [39] '.symtab': symbol 11114 (_ZN3std10sys_common11thread_info11THREAD_INFO7__getit5__KEY17h392c4b1514584758E) does not fit completely in referenced section [21] '.tbss'
> section [39] '.symtab': symbol 22918 (_ZN3std9panicking11panic_count17LOCAL_PANIC_COUNT7__getit5__KEY17h12fb9976e0c26702E.llvm.13708256337585169031): st_value out of bounds of referenced section [21] '.tbss'
> verify-elf: WARNING: ./usr/bin/cargo: eu-elflint failed
> section [38] '.symtab': symbol 53164 (_ZN4rand4rngs6thread14THREAD_RNG_KEY7__getit5__KEY17hd4b0b80e7f6fdcbfE) does not fit completely in referenced section [19] '.tbss'
> section [38] '.symtab': symbol 53305 (_ZN84_$LT$parking_lot..remutex..RawThreadId$u20$as$u20$lock_api..remutex..GetThreadId$GT$17nonzero_thread_id3KEY7__getit5__KEY17hd7cc1cd89b18e04cE): st_value out of bounds of referenced section [19] '.tbss'
> verify-elf: WARNING: ./usr/lib64/librustc_driver-ba5ce6e8a56408f3.so: eu-elflint failed
> verify-elf: WARNING: ./usr/lib64/rustlib/x86_64-unknown-linux-gnu/bin/rust-llvm-dwp: RPATH entry found: $ORIGIN/../lib64
> Executing(%check): /bin/sh -e /usr/src/tmp/rpm-tmp.21386
> + umask 022
> + /bin/mkdir -p /usr/src/RPM/BUILD
> + cd /usr/src/RPM/BUILD
> + cd rustc-src
> + . ./env.sh
> ++ export RUST_BACKTRACE=1
> ++ RUST_BACKTRACE=1
> ++ export 'RUSTFLAGS=-Clink-arg=-Wl,-z,relro,-z,now -Clink-args=-fPIC -Copt-level=2'
> ++ RUSTFLAGS='-Clink-arg=-Wl,-z,relro,-z,now -Clink-args=-fPIC -Copt-level=2'
> ++ export LIBGIT2_SYS_USE_PKG_CONFIG=1
> ++ LIBGIT2_SYS_USE_PKG_CONFIG=1
> ++ export LIBSSH2_SYS_USE_PKG_CONFIG=1
> ++ LIBSSH2_SYS_USE_PKG_CONFIG=1
> ++ export DESTDIR=/usr/src/tmp/rust-buildroot
> ++ DESTDIR=/usr/src/tmp/rust-buildroot
> + find /usr/src/tmp/rust-buildroot//usr/lib64 -name 'librustc_driver-*.so' -execdir objdump -p '{}' +
> + grep -qs 'NEEDED.*LLVM'
> + exit 0
> Processing files: rust-1.50.0-alt1
> Executing(%doc): /bin/sh -e /usr/src/tmp/rpm-tmp.21386
> + umask 022
> + /bin/mkdir -p /usr/src/RPM/BUILD
> + cd /usr/src/RPM/BUILD
> + cd rustc-src
> + DOCDIR=/usr/src/tmp/rust-buildroot/usr/share/doc/rust-1.50.0
> + export DOCDIR
> + rm -rf /usr/src/tmp/rust-buildroot/usr/share/doc/rust-1.50.0
> + /bin/mkdir -p /usr/src/tmp/rust-buildroot/usr/share/doc/rust-1.50.0
> + cp -prL COPYRIGHT LICENSE-APACHE LICENSE-MIT README.md /usr/src/tmp/rust-buildroot/usr/share/doc/rust-1.50.0
> + chmod -R go-w /usr/src/tmp/rust-buildroot/usr/share/doc/rust-1.50.0
> + chmod -R a+rX /usr/src/tmp/rust-buildroot/usr/share/doc/rust-1.50.0
> + exit 0
> Finding Provides (using /usr/lib/rpm/find-provides)
> Executing: /bin/sh -e /usr/src/tmp/rpm-tmp.9cq6Tq
> find-provides: running scripts (alternatives,debuginfo,lib,pam,perl,pkgconfig,python,shell)
> lib.prov: /usr/src/tmp/rust-buildroot/usr/lib64/libchalk_derive-37534ae34f5fcae8.so: 16215 symbols, 24 bpp
> warning: hash collision: _ZN4core3mem12align_of_val17h6279c5833cd5522cE _ZN4core3ptr13drop_in_place17h2590dfd213db08ffE
> warning: hash collision: _ZN4core3ptr6unique15Unique$LT$T$GT$4cast17h90cf5cd4c3f13b51E _ZN68_$LT$std..thread..local..AccessError$u20$as$u20$core..fmt..Debug$GT$3fmt17h6b7ba1bbf0f00c45E
> warning: hash collision: _ZN4core4iter8adapters4take13Take$LT$I$GT$3new17h75045b18f9916eb2E _ZN4core6option15Option$LT$T$GT$7or_else17heeff00a141867c99E
> warning: hash collision: _ZN11miniz_oxide7deflate4core33create_comp_flags_from_zip_params17h0b416523e01bbf6aE _ZN4core3ptr4read17h2a39e57cc70183caE
> warning: hash collision: _ZN105_$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$core..cmp..PartialEq$LT$alloc..vec..Vec$LT$U$C$A$GT$$GT$$GT$2eq17h1e8949a6b6a3e0fbE _ZN3syn3lit10LitByteStr4span17he839fdc0c0941bf8E
> warning: hash collision: _ZN4core6result19Result$LT$T$C$E$GT$14unwrap_or_else17hc412d5ee4070274cE _ZN75_$LT$alloc..vec..IntoIter$LT$T$C$A$GT$$u20$as$u20$core..ops..drop..Drop$GT$4drop17h4a7021959e78d02dE
> warning: hash collision: _ZN3std3sys4unix3ext3net9ancillary10SocketCred3new17h00c0281be9f19464E _ZN4core3ptr6unique15Unique$LT$T$GT$13new_unchecked17h3c5a1e8401980360E
> warning: hash collision: _ZN54_$LT$$LP$T10$C$T11$RP$$u20$as$u20$core..fmt..Debug$GT$3fmt17h34a8dd22db59980aE _ZN84_$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$alloc..vec..SpecExtend$LT$T$C$I$GT$$GT$11spec_extend17h60ca674df9219823E
> warning: hash collision: _ZN3syn3gen6helper5visit13tokens_helper17h0cfe94e695e97ff8E _ZN42_$LT$$RF$T$u20$as$u20$core..fmt..Debug$GT$3fmt17h648870c773ee854fE
> warning: hash collision: _ZN3syn5parse11ParseBuffer4peek17hf9a11eea8c9a3d3fE _ZN4core5slice5index74_$LT$impl$u20$core..ops..index..Index$LT$I$GT$$u20$for$u20$$u5b$T$u5d$$GT$5index17h5a12cf41c79d168fE
> warning: hash collision: _ZN3syn3gen5visit5Visit15visit_pat_slice17hbf44f3125c810c39E _ZN66_$LT$core..option..Option$LT$T$GT$$u20$as$u20$core..fmt..Debug$GT$3fmt17h818541d64f1ddcfdE
> warning: hash collision: _ZN4core3ptr13drop_in_place17he21b3c2d21e2e2c1E _ZN4core4iter6traits12double_ended19DoubleEndedIterator15advance_back_by17hefd6f0c285c16047E
> lib.prov: /usr/src/tmp/rust-buildroot/usr/lib64/librustc_driver-ba5ce6e8a56408f3.so: 13929 symbols, 24 bpp
> warning: hash collision: _ZN17rustc_codegen_ssa4back4link13link_natively8CALLSITE17heec9512fe75df10eE _ZN97_$LT$regex_syntax..hir..translate..TranslatorI$u20$as$u20$regex_syntax..ast..visitor..Visitor$GT$25visit_class_set_item_post17h97a3e0991800014aE
> warning: hash collision: _ZN13rustc_feature6active15ACTIVE_FEATURES1f17h34debe6b549fb15fE _ZN76_$LT$rustc_session..code_stats..DataTypeKind$u20$as$u20$core..fmt..Debug$GT$3fmt17h013f6c8f87f7737eE
> warning: hash collision: _ZN104_$LT$rustc_typeck..check..dropck..SimpleEqRelation$u20$as$u20$rustc_middle..ty..relate..TypeRelation$GT$13a_is_expected17h8ee3fd4747d45e42E _ZN108_$LT$rustc_mir..borrow_check..region_infer..graphviz..SccConstraints$u20$as$u20$rustc_graphviz..Labeller$GT$8graph_id17hef23cbc093aa88aeE
> warning: hash collision: _ZN71_$LT$rustc_metadata..creader..CrateDump$u20$as$u20$core..fmt..Debug$GT$3fmt17hce7600da19895b3bE _ZN86_$LT$thread_local..thread_id..THREAD_ID_MANAGER$u20$as$u20$core..ops..deref..Deref$GT$5deref17h51faeeda00480bb8E
> warning: hash collision: _ZN17annotate_snippets9formatter102_$LT$impl$u20$core..fmt..Display$u20$for$u20$annotate_snippets..display_list..structs..DisplayList$GT$3fmt17hfa5cbc856fe773bfE _ZN65_$LT$proc_macro..TokenTree$u20$as$u20$alloc..string..ToString$GT$9to_string17he4dc53f357b73ee4E
> warning: hash collision: _ZN10serde_json5value10partial_eq90_$LT$impl$u20$core..cmp..PartialEq$LT$f32$GT$$u20$for$u20$$RF$serde_json..value..Value$GT$2eq17hb90215bdb914c35bE _ZN57_$LT$u8$u20$as$u20$regex_syntax..hir..interval..Bound$GT$9max_value17hf6bf45ce420cf4d5E
> warning: hash collision: _ZN12rustc_middle2ty16structural_impls93_$LT$impl$u20$rustc_middle..ty..context..Lift$u20$for$u20$rustc_middle..ty..sty..TraitRef$GT$11lift_to_tcx17hc362434ae4a62dedE _ZN15rustc_interface4util11release_str17hb40b3ed76d1863caE
> warning: hash collision: _ZN6chrono6format4scan16nanosecond_fixed17hc1b446c1a99ec3adE _ZN94_$LT$rustc_expand..expand..InvocationCollector$u20$as$u20$rustc_ast..mut_visit..MutVisitor$GT$15filter_map_expr17h7d3c99cea8ed722fE
> warning: hash collision: _ZN178_$LT$fn$LP$$RF$mut$u20$dyn$u20$core..fmt..Write$RP$$u20$.$GT$$u20$core..result..Result$LT$$LP$$RP$$C$core..fmt..Error$GT$$u20$as$u20$tracing_subscriber..fmt..time..FormatTime$GT$11format_time17h0a16a3def99b7388E _ZN21rustc_trait_selection6traits39type_known_to_meet_bound_modulo_regions17h325760c739108ce9E
> lib.prov: /usr/src/tmp/rust-buildroot/usr/lib64/librustc_macros-699d933d47f5ae2e.so: 16215 symbols, 24 bpp
> warning: hash collision: _ZN4core3mem12align_of_val17h6279c5833cd5522cE _ZN4core3ptr13drop_in_place17h2590dfd213db08ffE
> warning: hash collision: _ZN4core3ptr6unique15Unique$LT$T$GT$4cast17h90cf5cd4c3f13b51E _ZN68_$LT$std..thread..local..AccessError$u20$as$u20$core..fmt..Debug$GT$3fmt17h6b7ba1bbf0f00c45E
> warning: hash collision: _ZN4core4iter8adapters4take13Take$LT$I$GT$3new17h75045b18f9916eb2E _ZN4core6option15Option$LT$T$GT$7or_else17heeff00a141867c99E
> warning: hash collision: _ZN11miniz_oxide7deflate4core33create_comp_flags_from_zip_params17h0b416523e01bbf6aE _ZN4core3ptr4read17h2a39e57cc70183caE
> warning: hash collision: _ZN105_$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$core..cmp..PartialEq$LT$alloc..vec..Vec$LT$U$C$A$GT$$GT$$GT$2eq17h1e8949a6b6a3e0fbE _ZN3syn3lit10LitByteStr4span17he839fdc0c0941bf8E
> warning: hash collision: _ZN4core6result19Result$LT$T$C$E$GT$14unwrap_or_else17hc412d5ee4070274cE _ZN75_$LT$alloc..vec..IntoIter$LT$T$C$A$GT$$u20$as$u20$core..ops..drop..Drop$GT$4drop17h4a7021959e78d02dE
> warning: hash collision: _ZN3std3sys4unix3ext3net9ancillary10SocketCred3new17h00c0281be9f19464E _ZN4core3ptr6unique15Unique$LT$T$GT$13new_unchecked17h3c5a1e8401980360E
> warning: hash collision: _ZN54_$LT$$LP$T10$C$T11$RP$$u20$as$u20$core..fmt..Debug$GT$3fmt17h34a8dd22db59980aE _ZN84_$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$alloc..vec..SpecExtend$LT$T$C$I$GT$$GT$11spec_extend17h60ca674df9219823E
> warning: hash collision: _ZN3syn3gen6helper5visit13tokens_helper17h0cfe94e695e97ff8E _ZN42_$LT$$RF$T$u20$as$u20$core..fmt..Debug$GT$3fmt17h648870c773ee854fE
> warning: hash collision: _ZN3syn5parse11ParseBuffer4peek17hf9a11eea8c9a3d3fE _ZN4core5slice5index74_$LT$impl$u20$core..ops..index..Index$LT$I$GT$$u20$for$u20$$u5b$T$u5d$$GT$5index17h5a12cf41c79d168fE
> warning: hash collision: _ZN3syn3gen5visit5Visit15visit_pat_slice17hbf44f3125c810c39E _ZN66_$LT$core..option..Option$LT$T$GT$$u20$as$u20$core..fmt..Debug$GT$3fmt17h818541d64f1ddcfdE
> warning: hash collision: _ZN4core3ptr13drop_in_place17he21b3c2d21e2e2c1E _ZN4core4iter6traits12double_ended19DoubleEndedIterator15advance_back_by17hefd6f0c285c16047E
> lib.prov: /usr/src/tmp/rust-buildroot/usr/lib64/libserde_derive-58c063dc739a6f06.so: 13021 symbols, 24 bpp
> warning: hash collision: _ZN4core3mem12align_of_val17h6279c5833cd5522cE _ZN4core3ptr13drop_in_place17h2590dfd213db08ffE
> warning: hash collision: _ZN4core3ptr6unique15Unique$LT$T$GT$4cast17h90cf5cd4c3f13b51E _ZN68_$LT$std..thread..local..AccessError$u20$as$u20$core..fmt..Debug$GT$3fmt17h6b7ba1bbf0f00c45E
> warning: hash collision: _ZN11miniz_oxide7deflate4core33create_comp_flags_from_zip_params17h0b416523e01bbf6aE _ZN4core3ptr4read17h2a39e57cc70183caE
> warning: hash collision: _ZN105_$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$core..cmp..PartialEq$LT$alloc..vec..Vec$LT$U$C$A$GT$$GT$$GT$2eq17h1e8949a6b6a3e0fbE _ZN3syn3lit10LitByteStr4span17he839fdc0c0941bf8E
> warning: hash collision: _ZN54_$LT$$LP$T10$C$T11$RP$$u20$as$u20$core..fmt..Debug$GT$3fmt17h34a8dd22db59980aE _ZN84_$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$alloc..vec..SpecExtend$LT$T$C$I$GT$$GT$11spec_extend17h60ca674df9219823E
> warning: hash collision: _ZN3syn5parse11ParseBuffer4peek17hf9a11eea8c9a3d3fE _ZN4core5slice5index74_$LT$impl$u20$core..ops..index..Index$LT$I$GT$$u20$for$u20$$u5b$T$u5d$$GT$5index17h5a12cf41c79d168fE
> warning: hash collision: _ZN4core3ptr13drop_in_place17he21b3c2d21e2e2c1E _ZN4core4iter6traits12double_ended19DoubleEndedIterator15advance_back_by17hefd6f0c285c16047E
> lib.prov: /usr/src/tmp/rust-buildroot/usr/lib64/libstd-bff2707de9e49df8.so: 2670 symbols, 22 bpp
> lib.prov: /usr/src/tmp/rust-buildroot/usr/lib64/libtest-e36e0033748a1619.so: 134 symbols, 18 bpp
> lib.prov: /usr/src/tmp/rust-buildroot/usr/lib64/libtracing_attributes-5e6a34c3e0958c16.so: 13021 symbols, 24 bpp
> warning: hash collision: _ZN4core3mem12align_of_val17h6279c5833cd5522cE _ZN4core3ptr13drop_in_place17h2590dfd213db08ffE
> warning: hash collision: _ZN4core3ptr6unique15Unique$LT$T$GT$4cast17h90cf5cd4c3f13b51E _ZN68_$LT$std..thread..local..AccessError$u20$as$u20$core..fmt..Debug$GT$3fmt17h6b7ba1bbf0f00c45E
> warning: hash collision: _ZN11miniz_oxide7deflate4core33create_comp_flags_from_zip_params17h0b416523e01bbf6aE _ZN4core3ptr4read17h2a39e57cc70183caE
> warning: hash collision: _ZN105_$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$core..cmp..PartialEq$LT$alloc..vec..Vec$LT$U$C$A$GT$$GT$$GT$2eq17h1e8949a6b6a3e0fbE _ZN3syn3lit10LitByteStr4span17he839fdc0c0941bf8E
> warning: hash collision: _ZN54_$LT$$LP$T10$C$T11$RP$$u20$as$u20$core..fmt..Debug$GT$3fmt17h34a8dd22db59980aE _ZN84_$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$alloc..vec..SpecExtend$LT$T$C$I$GT$$GT$11spec_extend17h60ca674df9219823E
> warning: hash collision: _ZN3syn5parse11ParseBuffer4peek17hf9a11eea8c9a3d3fE _ZN4core5slice5index74_$LT$impl$u20$core..ops..index..Index$LT$I$GT$$u20$for$u20$$u5b$T$u5d$$GT$5index17h5a12cf41c79d168fE
> warning: hash collision: _ZN4core3ptr13drop_in_place17he21b3c2d21e2e2c1E _ZN4core4iter6traits12double_ended19DoubleEndedIterator15advance_back_by17hefd6f0c285c16047E

Меня немного настораживает такое обилие предупреждений о коллизии. Как бы
не было беды, когда кто-то решит собрать модули rust отдельно.

-- 
Rgrds, legion

Re: [devel] hash collision in rpm

[Anton Farygin]

On 01.05.2021 12:04, Alexey Gladkov wrote:
> On Sat, May 01, 2021 at 06:44:31AM +0000, ALT beekeeper wrote:
>> Package: rust-1:1.50.0-alt1
>> Status: Sisyphus/x86_64 test rebuild failed
<skip>
>> warning: hash collision: _ZN54_$LT$$LP$T10$C$T11$RP$$u20$as$u20$core..fmt..Debug$GT$3fmt17h34a8dd22db59980aE _ZN84_$LT$alloc..vec..Vec$LT$T$C$A$GT$$u20$as$u20$alloc..vec..SpecExtend$LT$T$C$I$GT$$GT$11spec_extend17h60ca674df9219823E
>> warning: hash collision: _ZN3syn5parse11ParseBuffer4peek17hf9a11eea8c9a3d3fE _ZN4core5slice5index74_$LT$impl$u20$core..ops..index..Index$LT$I$GT$$u20$for$u20$$u5b$T$u5d$$GT$5index17h5a12cf41c79d168fE
>> warning: hash collision: _ZN4core3ptr13drop_in_place17he21b3c2d21e2e2c1E _ZN4core4iter6traits12double_ended19DoubleEndedIterator15advance_back_by17hefd6f0c285c16047E
> Меня немного настораживает такое обилие предупреждений о коллизии. Как бы
> не было беды, когда кто-то решит собрать модули rust отдельно.
>
Я тоже с таким же столкнулся в новом пакете с библиотеками для C++:

warning: hash collision: _ZN23IGESData_IGESReaderData12AddStartLineEPKc 
_ZNK14IGESSolid_Loop4EdgeEi

и там такого довольно много.

Re: [devel] hash collision in rpm

[Alexey Gladkov]

On Tue, May 04, 2021 at 01:32:59PM +0300, Anton Farygin wrote:
> On 01.05.2021 12:04, Alexey Gladkov wrote:
> > On Sat, May 01, 2021 at 06:44:31AM +0000, ALT beekeeper wrote:
> > > Package: rust-1:1.50.0-alt1
> > > Status: Sisyphus/x86_64 test rebuild failed
> <skip>
> > Меня немного настораживает такое обилие предупреждений о коллизии. Как бы
> > не было беды, когда кто-то решит собрать модули rust отдельно.
> > 
> Я тоже с таким же столкнулся в новом пакете с библиотеками для C++:
> 
> warning: hash collision: _ZN23IGESData_IGESReaderData12AddStartLineEPKc
> _ZNK14IGESSolid_Loop4EdgeEi
> 
> и там такого довольно много.

Я обсудил это с Димой и он объяснил мне, что это не признак ошибки.
Вот тут в suggest_bpp.c есть комментарий:

http://git.altlinux.org/gears/r/..git?p=rpm-build.git;a=commitdiff;h=0ea2deff

Если мы выбираем bpp таким образом, чтобы вероятность коллизии была
1/1024, то в больших библиотеках (у rust там 16215 symbols) ожидаются
коллизии, это нормально.

-- 
Rgrds, legion

Re: [devel] hash collision in rpm

[Alexey Tourbin]

On Tue, May 4, 2021 at 1:45 PM Alexey Gladkov <legion@altlinux.ru> wrote:
> On Tue, May 04, 2021 at 01:32:59PM +0300, Anton Farygin wrote:
> > On 01.05.2021 12:04, Alexey Gladkov wrote:
> > > On Sat, May 01, 2021 at 06:44:31AM +0000, ALT beekeeper wrote:
> > > > Package: rust-1:1.50.0-alt1
> > > > Status: Sisyphus/x86_64 test rebuild failed
> > <skip>
> > > Меня немного настораживает такое обилие предупреждений о коллизии. Как бы
> > > не было беды, когда кто-то решит собрать модули rust отдельно.
> > >
> > Я тоже с таким же столкнулся в новом пакете с библиотеками для C++:
> >
> > warning: hash collision: _ZN23IGESData_IGESReaderData12AddStartLineEPKc
> > _ZNK14IGESSolid_Loop4EdgeEi
> >
> > и там такого довольно много.
>
> Я обсудил это с Димой и он объяснил мне, что это не признак ошибки.
> Вот тут в suggest_bpp.c есть комментарий:
>
> http://git.altlinux.org/gears/r/..git?p=rpm-build.git;a=commitdiff;h=0ea2deff
>
> Если мы выбираем bpp таким образом, чтобы вероятность коллизии была
> 1/1024, то в больших библиотеках (у rust там 16215 symbols) ожидаются
> коллизии, это нормально.

The number of birthday collisions among n-bit hashes is small only if
we hash up to about sqrt(2^n) items. If we want to keep the number of
birthday collisions under control, then bpp=10+log2(n) is simply a bad
formula. A better one is bpp=max(10,log2(n))+log2(n). I.e. for
n=16215, as per your example, it should be 14+14 rather than 10+14.

Now, there is a subtle argument why you shouldn't go 14+14, and why
10+14 is indeed "normal". One view is that we should try to keep the
number of birthday collisions small *per a provided version*.  But
this view is naive. Consider what happens when we have one big shared
library and we split it into two smaller libraries. It seems that
smaller libraries can use smaller bpp, e.g. 13+13 each instead of
14+14 combined. Indeed the number of expected collisions E[X] per each
library is the same. But now we've got two libraries, and the combined
expectation is linear! From the perspective of a client, one OR the
other library is now twice as likely to exhibit a collision, simply
because there are two of them!

You could achieve the same effect - doubling E[X] - without splitting
a big library into two smaller libraries. Just use the big library
with bpp=13 instead of 14. :-)

So the right view must be under the invariant "it doesn't matter how
the symbols are spread among libraries". That's why "probability per
symbol" makes sense, and "restricting birthday collisions" does not.

Re: [devel] hash collision in rpm

[Alexey Tourbin]

On Tue, May 4, 2021 at 3:50 PM Alexey Tourbin <alexey.tourbin@gmail.com> wrote:
> On Tue, May 4, 2021 at 1:45 PM Alexey Gladkov <legion@altlinux.ru> wrote:
> > Если мы выбираем bpp таким образом, чтобы вероятность коллизии была
> > 1/1024, то в больших библиотеках (у rust там 16215 symbols) ожидаются
> > коллизии, это нормально.
>
> The number of birthday collisions among n-bit hashes is small only if
> we hash up to about sqrt(2^n) items. If we want to keep the number of
> birthday collisions under control, then bpp=10+log2(n) is simply a bad
> formula. A better one is bpp=max(10,log2(n))+log2(n). I.e. for
> n=16215, as per your example, it should be 14+14 rather than 10+14.
>
> Now, there is a subtle argument why you shouldn't go 14+14, and why
> 10+14 is indeed "normal". One view is that we should try to keep the
> number of birthday collisions small *per a provided version*.  But
> this view is naive. Consider what happens when we have one big shared
> library and we split it into two smaller libraries. It seems that
> smaller libraries can use smaller bpp, e.g. 13+13 each instead of
> 14+14 combined. Indeed the number of expected collisions E[X] per each
> library is the same. But now we've got two libraries, and the combined
> expectation is linear! From the perspective of a client, one OR the
> other library is now twice as likely to exhibit a collision, simply
> because there are two of them!

> So the right view must be under the invariant "it doesn't matter how
> the symbols are spread among libraries". That's why "probability per
> symbol" makes sense, and "restricting birthday collisions" does not.

Let's check that the invariant holds with bpp=10+log2(n). Again, we
split a long set-version with bpp=10+14 into two shorter set-versions
with bpp=10+13 (the number of symbols being 2^14 resp. 2^13). The
number of hash values over the hash space, which is how we define the
false positive rate, is the same: 2^14/2^24=2^13/2^23=2^-10.

A related notion is the average distance between two neighbour hash
values (when we "drop" hash values into the interval [0,2^bpp)). The
distance is approximately 2^-10 in both cases. It defines the optimal
parameter m for Golomb-Rice code. Roughly speaking, with
bpp=10+log2(n), the optimal m is 10. With optimal m, the length of
Golomb-Rice code is approximately m+2 bits per integer. So the
combined length of the two shorter versions must be about the same as
the length of the long version.

Finally we need to check the birthday collision rate. With bpp-bit
hash values, n of them, the expected number of birthday collisions is
(to a good approximation)

E[X]=n^2 / 2^(bpp+1)
(refer to Cormen et al., Introduction to Algorithms (3rd ed.), p. 133.)

Let E_0 be the expected number of collisions for a long version. For a
shorter version with (bbp-1)-bit hash values, n/2 of them, we have

E_1 = (n/2)^2 / (2^(bpp-1+1) = 1/2 E_0

So the expected number of collisions for short versions is smaller,
but we have two of them. By the linearity of expectation, the birthday
collision rate is the same. (This generally shows that it is pointless
to split a long set-version into a few shorter ones, under any classes
of equivalence on symbols such as ELF ABI tags. Counterintuitively,
you can't fight birthday collisions by partitioning, unless you also
increase the output length. So doing separate set-versions for
libfoo.so.0(FOO_1.0) and libfoo.so.0(FOO_1.1) is not necessarily a
good idea, we can just as well hash sym@FOO_1.0 and sym@FOO_1.1 and
package them into a single version.)

* * *

By the way, there's a clever way to detect collisions at a higher
level, even though low-level collisions are unavoidable, subject to
implacable math. We can take advantage of the fact that the build
system synchronizes package builds across a few architectures.
Currently, if a missing symbol goes undetected due to a hash
collision, it does so on all architectures simultaneously. To change
that, we need to hash symbols differently, depending on the target
architecture (we can pass seed=hash(arch) to the hash function, or use
different initialization vectors IV=hash(arch)).  The desired outcome
is that when a missing symbol goes undetected, it does so, with an
overwhelming probability, on only one target.  Roughly speaking, if
the probability of an undetected missing symbol is 10^-3 on a single
target, it must be 10^-6 on two targets, 10^-9 on thee targets, etc.

Re: [devel] hash collision in rpm

[Dmitry V. Levin]

On Wed, May 05, 2021 at 08:40:27AM +0300, Alexey Tourbin wrote:
[...]
> By the way, there's a clever way to detect collisions at a higher
> level, even though low-level collisions are unavoidable, subject to
> implacable math. We can take advantage of the fact that the build
> system synchronizes package builds across a few architectures.
> Currently, if a missing symbol goes undetected due to a hash
> collision, it does so on all architectures simultaneously. To change
> that, we need to hash symbols differently, depending on the target
> architecture (we can pass seed=hash(arch) to the hash function, or use
> different initialization vectors IV=hash(arch)).  The desired outcome
> is that when a missing symbol goes undetected, it does so, with an
> overwhelming probability, on only one target.  Roughly speaking, if
> the probability of an undetected missing symbol is 10^-3 on a single
> target, it must be 10^-6 on two targets, 10^-9 on thee targets, etc.

This looks very promising indeed.  I suppose the gain would justify
the necessary rebuilding of all packages with set-versions in their
arch-specific dependencies.


-- 
ldv

Re: [devel] hash collision in rpm

[Vladimir D. Seleznev]

On Wed, May 05, 2021 at 08:40:27AM +0300, Alexey Tourbin wrote:
> [skip]
> 
> So the expected number of collisions for short versions is smaller,
> but we have two of them. By the linearity of expectation, the birthday
> collision rate is the same. (This generally shows that it is pointless
> to split a long set-version into a few shorter ones, under any classes
> of equivalence on symbols such as ELF ABI tags. Counterintuitively,
> you can't fight birthday collisions by partitioning, unless you also
> increase the output length. So doing separate set-versions for
> libfoo.so.0(FOO_1.0) and libfoo.so.0(FOO_1.1) is not necessarily a
> good idea, we can just as well hash sym@FOO_1.0 and sym@FOO_1.1 and
> package them into a single version.)

Unfortunately, the symbol resolution is very flexible (some treat it as
an advantage), so the dynamic linker can resolve sym@FOO_1.0 as sym and
vice versa. That makes almost no point to hash symbols with their
versions.

-- 
   WBR,
   Vladimir D. Seleznev