From 1f200adfa7c1a87ca8af43c4eb5f471379899d26 Mon Sep 17 00:00:00 2001 From: Zachary Turner Date: Fri, 6 Jul 2018 02:33:58 +0000 Subject: [PATCH] [PDB] Sort globals symbols by name in GSI hash buckets. It seems like the debugger first computes a symbol's bucket, and then does a binary search of entries in the bucket using the symbol's name in order to find it. If the bucket entries are not in sorted order, this obviously won't work. After this patch a couple of simple test cases show that we generate an exactly identical GSI hash stream, which is very nice. llvm-svn: 336405 --- .../COFF/Inputs/globals-dia-vfunc-collision.obj | Bin 0 -> 8794 bytes .../COFF/Inputs/globals-dia-vfunc-collision2.obj | Bin 0 -> 3660 bytes lld/test/COFF/Inputs/globals-dia-vfunc-simple.obj | Bin 0 -> 4575 bytes lld/test/COFF/pdb-globals-dia-vfunc-collision.test | 42 +++++++++++++++++++++ .../COFF/pdb-globals-dia-vfunc-collision2.test | 25 ++++++++++++ lld/test/COFF/pdb-globals-dia-vfunc-simple.test | 26 +++++++++++++ llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp | 24 +++++++++--- 7 files changed, 112 insertions(+), 5 deletions(-) create mode 100644 lld/test/COFF/Inputs/globals-dia-vfunc-collision.obj create mode 100644 lld/test/COFF/Inputs/globals-dia-vfunc-collision2.obj create mode 100644 lld/test/COFF/Inputs/globals-dia-vfunc-simple.obj create mode 100644 lld/test/COFF/pdb-globals-dia-vfunc-collision.test create mode 100644 lld/test/COFF/pdb-globals-dia-vfunc-collision2.test create mode 100644 lld/test/COFF/pdb-globals-dia-vfunc-simple.test diff --git a/lld/test/COFF/Inputs/globals-dia-vfunc-collision.obj b/lld/test/COFF/Inputs/globals-dia-vfunc-collision.obj new file mode 100644 index 0000000000000000000000000000000000000000..3191c3ea2b285b12fac87d2fc88b637a0239ffd0 GIT binary patch literal 8794 zcmb`MeP~tZ9mk)Oo0prLn|Kr7Q){p5ZJTLwy;^Is(3(Wzdb@_{mg^dwSo5Z)jcJ-h zmsz%DC~abtb!?2WH_9lZ>!2+wgAO`T?3inz*kZvyWF4$*j>%9fV+>*Yet*B`oO{lF zF?Zkt=bYd3JD>AA&-Zyh_YOV3(fo7Emao3L(wJwBrsUM{^pv%EIf~1)1=NM2PP-oe6i~cx#?g)hAI%RGq-&0;C=}BL;LPB znC|-9bJQ^dCfcwtmj-jO1TMB1b%TTHb~-MB8M0%^;|h$Un;b)&;E-e-aeNfu;$WIf z;CjIHmB3AdIbH(yGMG0?;4XlLBTzToO`f~S?@oB`1l-+o zXVS;s={v_2k^{Efti_qbqTICM%nnm-w&TpAmYe-JuNKQGcTD-uQK(~A+gQ$2dY-4b z^UO4*=g!(P%Fs^FXXuNt@bUEA1-!HETqEM#E3ww#{IFP9>lt@I;^K)O;D{TSU=__+ zH}GiFITo;09}s?PVg8RmJbvSX{IN6pJ-SJ0Tb{!4kDZBnd`m9BBYle7FO!~&Cergb z<{VVcu5(;tJ1p!tj&aJcHzD*E>vq?&TLP|aEfDV zJ2LoL!3bGGVnt~jR)NN0RcjnJl4IiQySIJ5YiCcU=drErqay=@ho+La1l-Sz4vqC6 z8lL10*3oqw>v6Q0hwE9A3kDloNqy|BNQ0yOV+Z0#h9@RRo*9d`CR52&T%Y>^?yfbD z+S!<_?v2&Lyk_Tf`a_%6Ji-@3qC~w_u$|%a2*HRCv3vF)BUUlN^n`^%C@#@nTUmaX`oIMAsjSn%t32K%secn8uJ}BFmJqOts3)d z&-cFP`_S`!0!!mvu~r0gifZe{HMh<9z2K&$G1oGg_V$c4NELjJnL0RzlqOtQC=(P;OKha;}E2z|)e`@Axg_ zrey&QT^mvl6_XLiBPwH&%8-6TubbSsejO|qb#U~m4q6eza&aE6F}tl5F)Y1uY$}MI2Kd~E!CkMbtrec_OO!&Sd5vVjt5h%3+t#Y(jIPH ze|yy69n`_OR&~%)9o%NA4qB>1IqFcZR2?gWIyR+JcUA}c4s~#)P#v^X$13r$U(r$> z%29`Mu8u-uob#5O?#k-uZEx=t5sTo<8RNv23>O~bZcKk$V3`#S+;OM|S~|wph>v5O zmX2}dMv+&})lg`RM?tx1RX{_R+oy`ikSzjMw(QyvcLU+-#`Wt6!Oym6!l627X0mjigS!URK}&V46CZWZQXR@shjOLrSRK^i&Q*6z z2V0OjHsVknv{Xk*eAGcpbtp$2%9X0)o}dnQ?YLt)Dp4ZpXvLvAXsM2e#77;pREKiZ zp&WHYOj&Fkfub0(b;fDnn47}E(OPH1F|pCt9poE~vy8XOV9O@#(;L@Un+j}uX84#d zWlXZ8YiFjj6W_O7qjv5r%=HS_3y$R|M_iVp66Ij9MpG^Cr=R-fh={dx8#f1abn>Oj9J!%tt5DsT;(td5PQLbU%s+p#)Rxs1EZ zC=TvdsF880kv7Xt+ttZDI|q}ib2oHWV~MPTzkcar6SMbamJ%K63*(tCtHtGrc6oZ0 z<2>uu5!-~C>upTcoNW`9pSx9-pAF1%axN>>9(AT{8U0IeWXz504L0v@lYq~bE8w$j z74TV2?z;=s5#LRJBaUACZsu86Zap!k=d&>bK3{n}jw2Rz49W64J+DmTI6|_6REu@b zvBNWtF{G2(k&Wa6*deMb1q)E2|dS&x%iO2UxBa%Bn>+ zS%l?`tgKpOA1uOh)>Bq3vTfq?|C_;;JLDY2nd`*n*G`?J2PN?RfX&emQn%dG@d3v7 zZwzZJ$Y>q zeDl)T7Veicv1CkDd6AdH8;o3)7nyYxa@f0B=EO@~k8wk(N$ZaDc5ZF3*9Iep^CEMG z&PHBwGWq9fFEaZJQ*~Zs8Btz6vo@;pBFo5kSO%7P`0-62VfJS@q#x-8>p^arWrTW> zk3ap}#z1 zWSQpz^<1ZsegCM*eC)&#!|h}I#@F~ffSK5){V-ga_ zEwefP%SqekeawA6qGEDZnmWNQ4V`yf4NFW)~fvPR2jBGz~6#YgA~GO`+a%x|{WF0t+9i?bHb zXb)$c|0GWT&9;}1;rCaNvF+t!ngh%?T0U4~+sntu+Uu2vjBPI;BdfB<{A}&s*KK?G znDv2oZD0EO6Slp4410UF%w%kP`IrrPjBPI;BYOa^JdC65C0{Feo(aEgW5k_?)xphS zC%#g4ZtLnw_w9xQyTG6WTfm?Ld&i)IG4KTwj1h1!M!>-sen&?Nh4>N*(aAz|q;M~r Td$JWbH*f94jVD`ihvxqPRGN2K6-vTKsMNkg)Y z0bhbGrlBoX5Pd5}d@23}e5z7JNkKu8QYeTIf>5;&dFjtXpTzIG_s;IjW?ORL&YXMh zH|L&n?m1^}?t^B@eAaRN`>4on(UdOc=Zl8ts|{n=7P*8$3SlIr|3o^MEoPOZ{P^5p zJc%QjAJQYUv)=r1?*-!Kg9;-6SJCHG+V>Q2Ut-@IW^W7gWE}QY_|X9Q?-lkv4!2qj zHxslk4t-K162~AhE>7HW(z%)ZXmKvDgm`2yQU>G6BpR1=EU$?;xdbkU~on>%*q;S(g`{-{RN}i=65M2V!sTSv(75+N$>bN`W#67BptMK<6 z?8(%MT*Dyog?&ALOL4gX`9mx&)DiV$+;w1F6PuF0Dsef0n7ID9(BCS!abSw;z@VLjg5nCG|+BZk3va2}C}+J(ve5QDvo@rhg8|EPb|k@&9e)0MWrr{DW;OymLN zv_N{>hi7L-hYN+d$&u3&h1~Ge#MH^`uKB%f!wf)rbb6Yw97Y-=CgX;S%6V|4n0%-i zSn;*tV)9K%_FGAIt0cPvPV2jCxG3A5@`d(So)LZVXrqdxnhmtK52ypEgUpiR_(VCt z1ZZSLRDc=ZB&CKtos7|DBSU)2P7KB~rcQ%gRA^H~$qpMXsv@Cr1%)Bb^WhLAyDIXG zJ=3Fjz=y8Z7xp~K4c)Zsv>PfGJ-vQE_yzr7y=gzlMTK^4P_ko&iwdpRxM{>z^exE;QqbmB#e?<;AcJ>kaTC)(17FM-+~=v z=pOe8<2&v{zQ*vi*pnY_m3p-o<;+)7#Ju;2-Bb^gYcWqWZvs-UtIU86o{Txz)ygPq zyU-g#_}wew-VtP~XIG1al`rcl@kXiL!VcAdK}TsT`%X1m8zr=b@wAr&a zDAV@R$TmI%J5x^xMFLuTGLoyd^c2j7Q|>@{kJA&tZmT_(nrfD zFH-_Nz8fd2+qS&^o`1FNc34?P-1B^Z!jgo{ubFjU)_nGzZ?}el3TjsIx4Z~-FaC16 zwxn6x!85AV+_*+_?HbMeN82UMj~2)OVL#KPf2F93HJa54mZCwM>$GOyeVMVcS-d5E zZ1|d9G;d-M4d3mVe^T4ZnDsyFRwI<~Ov^WCm1`F7&gB06;`$Z7gBX=r);UNSyF)*o zz(q<$)u)Ho4coe4Fs;}Bdfmjwhhd8-W4_A18#111%pjK00Tl-Jkeat|zfB43@!c+Y zb~?_?t;IJMP0an6O##g1mN%D;%|1P<9@MwgbFg{&u(8>PQI!(FXq#2%#8)Isov8z^ mlg+_F#~kYI>T-`9qX3;DAnD9t{WYvRT9(E6h5!7Khx`eq<_lKb9y=YIFx z^LNjCFY`&W>^gMh^cyuIheT6iKD#(?c-~&ch?j~CV30~MVlsFxkr|sGQ)^Qf;xe<@iTQ=B-6qNP24iIsjz}Vt z9lvxw{ z9k+_oC8KNw#G^dyEE49r~)ZnRoNvrkr4yKo@raht?JhOg!4iA*Y_V)I@);-)m)PJ<6GdDRtF*TpSZJYRF zE;Btgm7U`R_ua(Ui?K%zN2%k!m_n41=kW-d$c;^(k1b?p=O!;s$2tNRVo_f!pgpol1<=BE-drvO5CF1 z^8TEHWM9A^ooh^h8jARHd_OuvQCGM^H`EI4N`Ws{x8E1`N&3QbqkSP47TU%$UL|J? z7nT`t8b_}*&YqEzkR$`Xu#PM><$YnPb#|(PqboI-31o$fG(KcpDe%SW_WMGfzA#VP z7jj{tZESW`@{ZxOFB(T*G|u{R0+K|)7aKcF$!F$DQgtD!fkzI zPfnt%d)V-)6yB?0WNUD9chNN}sa!w?=&jALltf(YRgG26QmJg=GtZ(Tb8i;6P8wV( zQ_owQ(Z&j?0FTfr`(Rv2$Y4ux4@q(R_Dh-a@Bg%?S}AX0-^FK{IzhCVd(dX`w8?Kj zpPB2R{go)AYRIFF^-^o*X+L8{`*#?bw!bh|w1d5vcCa28FZT6f@v4)OCd%tDY$R%p z%*M^GFJ>>-Q{IT7EI}P`J!Q0=cGExq`-;8LRoz%~>~QQKw2?%qC3ZxO)tv5&d91B_ z;@L?wR&&I{1W&I$>kz4vsFwG|UXjTyp(`a*CW{*#i{C;m9Ee@Fa(Km5GX8C2)t@(W++ z4=z83Z?!z;>w%gE4EaHvmF|BpeF^y*$xjv F!GFQu=o0_{ literal 0 HcmV?d00001 diff --git a/lld/test/COFF/pdb-globals-dia-vfunc-collision.test b/lld/test/COFF/pdb-globals-dia-vfunc-collision.test new file mode 100644 index 0000000..b19ff34 --- /dev/null +++ b/lld/test/COFF/pdb-globals-dia-vfunc-collision.test @@ -0,0 +1,42 @@ +REQUIRES: diasdk + +Input object file reconstruction: + +; // main.cpp +; struct S { +; // Function names are chosen specifically to generate hash collisions in the +; // GSI hash table. +; virtual int A307() { return 102; } +; virtual int A400() { return 12; } +; virtual int A206() { return 201; } +; virtual int A105() { return 300; } +; }; +; +; struct T : public S { +; int A105() override { return 300; } +; int A307() override { return 102; } +; int A206() override { return 201; } +; int A400() override { return 12; } +; }; +; +; int main(int argc, char **argv) { +; T s; +; return s.A105() + s.A206() + s.A307() + s.A400(); +; } + +clang-cl /Z7 /GS- /GR- /c main.cpp /Foglobals-dia-vfunc-collision.obj + +RUN: lld-link /debug /nodefaultlib /entry:main /out:%t.exe %S/Inputs/globals-dia-vfunc-collision.obj +RUN: llvm-pdbutil pretty -classes %t.pdb | FileCheck %s + +CHECK: struct T +CHECK: func [0x000010c0+ 0 - 0x000010dd-29 | sizeof= 29] (FPO) virtual int __cdecl A105() +CHECK: func [0x00001100+ 0 - 0x0000111b-27 | sizeof= 27] (FPO) virtual int __cdecl A307() +CHECK: func [0x000010e0+ 0 - 0x000010fd-29 | sizeof= 29] (FPO) virtual int __cdecl A206() +CHECK: func [0x00001120+ 0 - 0x0000113b-27 | sizeof= 27] (FPO) virtual int __cdecl A400() + +CHECK: struct S +CHECK: func [0x00001160+ 0 - 0x0000116c-12 | sizeof= 12] (FPO) virtual int __cdecl A307() +CHECK: func [0x00001170+ 0 - 0x0000117c-12 | sizeof= 12] (FPO) virtual int __cdecl A400() +CHECK: func [0x00001180+ 0 - 0x0000118c-12 | sizeof= 12] (FPO) virtual int __cdecl A206() +CHECK: func [0x00001190+ 0 - 0x0000119c-12 | sizeof= 12] (FPO) virtual int __cdecl A105() diff --git a/lld/test/COFF/pdb-globals-dia-vfunc-collision2.test b/lld/test/COFF/pdb-globals-dia-vfunc-collision2.test new file mode 100644 index 0000000..0d5da46 --- /dev/null +++ b/lld/test/COFF/pdb-globals-dia-vfunc-collision2.test @@ -0,0 +1,25 @@ +REQUIRES: diasdk + +Input object file reconstruction: + +; // main.cpp +; struct S { +; // Function names are chosen specifically to generate hash collisions in the +; // GSI hash table. +; virtual int A132() { return 102; } +; virtual int A1001() { return 300; } +; }; +; +; int main(int argc, char **argv) { +; S s; +; return s.A132(); +; } + +clang-cl /Z7 /GS- /GR- /c main.cpp /Foglobals-dia-vfunc-collision2.obj + +RUN: lld-link /debug /nodefaultlib /entry:main /out:%t.exe %S/Inputs/globals-dia-vfunc-collision2.obj +RUN: llvm-pdbutil pretty -classes %t.pdb | FileCheck %s + +CHECK: struct S +CHECK: func [0x00001060+ 0 - 0x0000106c-12 | sizeof= 12] (FPO) virtual int __cdecl A132() +CHECK: func [0x00001070+ 0 - 0x0000107c-12 | sizeof= 12] (FPO) virtual int __cdecl A1001() diff --git a/lld/test/COFF/pdb-globals-dia-vfunc-simple.test b/lld/test/COFF/pdb-globals-dia-vfunc-simple.test new file mode 100644 index 0000000..6273c39 --- /dev/null +++ b/lld/test/COFF/pdb-globals-dia-vfunc-simple.test @@ -0,0 +1,26 @@ +REQUIRES: diasdk + +Input object file reconstruction: + +; // main.cpp +; struct Base { +; virtual int V2() { return 42; } +; }; +; +; struct Derived : public Base { +; int V2() override { return 42; } +; }; +; +; int main() +; { +; Derived D; +; return D.V2(); +; } + +clang-cl /Z7 /GS- /GR- /c main.cpp /Foglobals-dia-vfunc-simple.obj + +RUN: lld-link /debug /nodefaultlib /entry:main /out:%t.exe %S/Inputs/globals-dia-vfunc-simple.obj +RUN: llvm-pdbutil pretty -classes %t.pdb | FileCheck %s + +CHECK: func [0x00001070+ 0 - 0x0000107c-12 | sizeof= 12] (FPO) virtual int __cdecl V2() +CHECK: func [0x000010a0+ 0 - 0x000010ac-12 | sizeof= 12] (FPO) virtual int __cdecl V2() diff --git a/llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp b/llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp index 63d63c1..eaea24a 100644 --- a/llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp +++ b/llvm/lib/DebugInfo/PDB/Native/GSIStreamBuilder.cpp @@ -83,7 +83,8 @@ Error GSIHashStreamBuilder::commit(BinaryStreamWriter &Writer) { } void GSIHashStreamBuilder::finalizeBuckets(uint32_t RecordZeroOffset) { - std::array, IPHR_HASH + 1> TmpBuckets; + std::array>, IPHR_HASH + 1> + TmpBuckets; uint32_t SymOffset = RecordZeroOffset; for (const CVSymbol &Sym : Records) { PSHashRecord HR; @@ -94,8 +95,7 @@ void GSIHashStreamBuilder::finalizeBuckets(uint32_t RecordZeroOffset) { // Hash the name to figure out which bucket this goes into. StringRef Name = getSymbolName(Sym); size_t BucketIdx = hashStringV1(Name) % IPHR_HASH; - TmpBuckets[BucketIdx].push_back(HR); // FIXME: Does order matter? - + TmpBuckets[BucketIdx].push_back(std::make_pair(Name, HR)); SymOffset += Sym.length(); } @@ -117,8 +117,22 @@ void GSIHashStreamBuilder::finalizeBuckets(uint32_t RecordZeroOffset) { ulittle32_t ChainStartOff = ulittle32_t(HashRecords.size() * SizeOfHROffsetCalc); HashBuckets.push_back(ChainStartOff); - for (const auto &HR : Bucket) - HashRecords.push_back(HR); + + // Sort each bucket by memcmp of the symbol's name. + std::sort(Bucket.begin(), Bucket.end(), + [](const std::pair &Left, + const std::pair &Right) { + size_t LS = Left.first.size(); + size_t RS = Right.first.size(); + if (LS < RS) + return true; + if (LS > RS) + return false; + return Left.first < Right.first; + }); + + for (const auto &Entry : Bucket) + HashRecords.push_back(Entry.second); } } -- 2.7.4