From ae45e1a3832fbb6c96707687e42f0b4aaab52c9b Mon Sep 17 00:00:00 2001 From: Yu Watanabe Date: Tue, 29 Dec 2020 23:50:54 +0900 Subject: [PATCH] resolve: slightly optimize dns_answer_add() Previously, dns_answer_add() was O(n^2). With this change dns_packet_extract() becomes ~15 times faster for some extremal case. Before: ``` $ time ./fuzz-dns-packet ~/downloads/clusterfuzz-testcase-minimized-fuzz-dns-packet-5631106733047808 /home/watanabe/downloads/clusterfuzz-testcase-minimized-fuzz-dns-packet-5631106733047808... ok real 0m15.453s user 0m15.430s sys 0m0.007s ``` After: ``` $ time ./fuzz-dns-packet ~/downloads/clusterfuzz-testcase-minimized-fuzz-dns-packet-5631106733047808 /home/watanabe/downloads/clusterfuzz-testcase-minimized-fuzz-dns-packet-5631106733047808... ok real 0m0.831s user 0m0.824s sys 0m0.006s ``` Hopefully fixes oss-fuzz#19227. https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=19227 --- src/resolve/resolved-dns-answer.c | 89 ++++++++++++++++------- src/resolve/resolved-dns-answer.h | 2 + src/resolve/resolved-dns-rr.c | 2 +- src/resolve/resolved-dns-rr.h | 1 + test/fuzz/fuzz-dns-packet/oss-fuzz-19227 | Bin 0 -> 30586 bytes 5 files changed, 67 insertions(+), 27 deletions(-) create mode 100644 test/fuzz/fuzz-dns-packet/oss-fuzz-19227 diff --git a/src/resolve/resolved-dns-answer.c b/src/resolve/resolved-dns-answer.c index 5b762a82e81..f5e50fcd844 100644 --- a/src/resolve/resolved-dns-answer.c +++ b/src/resolve/resolved-dns-answer.c @@ -8,18 +8,53 @@ #include "resolved-dns-dnssec.h" #include "string-util.h" +static void dns_answer_item_hash_func(const DnsAnswerItem *a, struct siphash *state) { + assert(a); + assert(state); + + siphash24_compress(&a->ifindex, sizeof(a->ifindex), state); + + dns_resource_record_hash_func(a->rr, state); +} + +static int dns_answer_item_compare_func(const DnsAnswerItem *a, const DnsAnswerItem *b) { + int r; + + assert(a); + assert(b); + + r = CMP(a->ifindex, b->ifindex); + if (r != 0) + return r; + + return dns_resource_record_compare_func(a->rr, b->rr); +} + +DEFINE_PRIVATE_HASH_OPS(dns_answer_item_hash_ops, DnsAnswerItem, dns_answer_item_hash_func, dns_answer_item_compare_func); + DnsAnswer *dns_answer_new(size_t n) { + _cleanup_set_free_ Set *s = NULL; DnsAnswer *a; if (n > UINT16_MAX) /* We can only place 64K RRs in an answer at max */ n = UINT16_MAX; + s = set_new(&dns_answer_item_hash_ops); + if (!s) + return NULL; + + /* Higher multipliers give slightly higher efficiency through hash collisions, but the gains + * quickly drop off after 2. */ + if (set_reserve(s, n * 2) < 0) + return NULL; + a = malloc0(offsetof(DnsAnswer, items) + sizeof(DnsAnswerItem) * n); if (!a) return NULL; a->n_ref = 1; a->n_allocated = n; + a->set_items = TAKE_PTR(s); return a; } @@ -30,6 +65,8 @@ static void dns_answer_flush(DnsAnswer *a) { if (!a) return; + a->set_items = set_free(a->set_items); + DNS_ANSWER_FOREACH(rr, a) dns_resource_record_unref(rr); @@ -46,6 +83,8 @@ static DnsAnswer *dns_answer_free(DnsAnswer *a) { DEFINE_TRIVIAL_REF_UNREF_FUNC(DnsAnswer, dns_answer, dns_answer_free); static int dns_answer_add_raw(DnsAnswer *a, DnsResourceRecord *rr, int ifindex, DnsAnswerFlags flags) { + int r; + assert(rr); if (!a) @@ -54,12 +93,21 @@ static int dns_answer_add_raw(DnsAnswer *a, DnsResourceRecord *rr, int ifindex, if (a->n_rrs >= a->n_allocated) return -ENOSPC; - a->items[a->n_rrs++] = (DnsAnswerItem) { - .rr = dns_resource_record_ref(rr), + a->items[a->n_rrs] = (DnsAnswerItem) { + .rr = rr, .ifindex = ifindex, .flags = flags, }; + r = set_put(a->set_items, &a->items[a->n_rrs]); + if (r < 0) + return r; + if (r == 0) + return -EEXIST; + + dns_resource_record_ref(rr); + a->n_rrs++; + return 1; } @@ -78,8 +126,7 @@ static int dns_answer_add_raw_all(DnsAnswer *a, DnsAnswer *source) { } int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr, int ifindex, DnsAnswerFlags flags) { - size_t i; - int r; + DnsAnswerItem tmp, *exist; assert(rr); @@ -88,36 +135,26 @@ int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr, int ifindex, DnsAnswerFl if (a->n_ref > 1) return -EBUSY; - for (i = 0; i < a->n_rrs; i++) { - if (a->items[i].ifindex != ifindex) - continue; - - r = dns_resource_key_equal(a->items[i].rr->key, rr->key); - if (r < 0) - return r; - if (r == 0) - continue; + tmp = (DnsAnswerItem) { + .rr = rr, + .ifindex = ifindex, + }; + exist = set_get(a->set_items, &tmp); + if (exist) { /* There's already an RR of the same RRset in place! Let's see if the TTLs more or less * match. We don't really care if they match precisely, but we do care whether one is 0 and * the other is not. See RFC 2181, Section 5.2. */ - if ((rr->ttl == 0) != (a->items[i].rr->ttl == 0)) + if ((rr->ttl == 0) != (exist->rr->ttl == 0)) return -EINVAL; - r = dns_resource_record_payload_equal(a->items[i].rr, rr); - if (r < 0) - return r; - if (r == 0) - continue; - - /* Entry already exists, keep the entry with the higher RR. */ - if (rr->ttl > a->items[i].rr->ttl) { - dns_resource_record_ref(rr); - dns_resource_record_unref(a->items[i].rr); - a->items[i].rr = rr; + /* Entry already exists, keep the entry with the higher TTL. */ + if (rr->ttl > exist->rr->ttl) { + dns_resource_record_unref(exist->rr); + exist->rr = dns_resource_record_ref(rr); } - a->items[i].flags |= flags; + exist->flags |= flags; return 0; } diff --git a/src/resolve/resolved-dns-answer.h b/src/resolve/resolved-dns-answer.h index fd94c516de9..d73525cedd2 100644 --- a/src/resolve/resolved-dns-answer.h +++ b/src/resolve/resolved-dns-answer.h @@ -6,6 +6,7 @@ typedef struct DnsAnswerItem DnsAnswerItem; #include "macro.h" #include "resolved-dns-rr.h" +#include "set.h" /* A simple array of resource records. We keep track of the * originating ifindex for each RR where that makes sense, so that we @@ -30,6 +31,7 @@ struct DnsAnswerItem { struct DnsAnswer { unsigned n_ref; + Set *set_items; /* Used by dns_answer_add() for optimization. */ size_t n_rrs, n_allocated; DnsAnswerItem items[0]; }; diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c index c848da3ccb9..19e075479f7 100644 --- a/src/resolve/resolved-dns-rr.c +++ b/src/resolve/resolved-dns-rr.c @@ -1479,7 +1479,7 @@ void dns_resource_record_hash_func(const DnsResourceRecord *rr, struct siphash * } } -static int dns_resource_record_compare_func(const DnsResourceRecord *x, const DnsResourceRecord *y) { +int dns_resource_record_compare_func(const DnsResourceRecord *x, const DnsResourceRecord *y) { int r; r = dns_resource_key_compare_func(x->key, y->key); diff --git a/src/resolve/resolved-dns-rr.h b/src/resolve/resolved-dns-rr.h index 59b3a70179c..aa17d6d391b 100644 --- a/src/resolve/resolved-dns-rr.h +++ b/src/resolve/resolved-dns-rr.h @@ -330,6 +330,7 @@ DnsTxtItem *dns_txt_item_copy(DnsTxtItem *i); int dns_txt_item_new_empty(DnsTxtItem **ret); void dns_resource_record_hash_func(const DnsResourceRecord *i, struct siphash *state); +int dns_resource_record_compare_func(const DnsResourceRecord *x, const DnsResourceRecord *y); extern const struct hash_ops dns_resource_key_hash_ops; extern const struct hash_ops dns_resource_record_hash_ops; diff --git a/test/fuzz/fuzz-dns-packet/oss-fuzz-19227 b/test/fuzz/fuzz-dns-packet/oss-fuzz-19227 new file mode 100644 index 0000000000000000000000000000000000000000..62828e7446a07cfe8e449629be937afb636ac920 GIT binary patch literal 30586 zc-rlqTZ|;vS%6Q?&R)E`!Q;fN@AevB$$HCmZguMH+IZ(01mb}QFv0?*x-PpT&&~|f zv$ofuWEDun10aYMf)bE|rMyK#T!bG8V)Njq2;`Rtq}Wzoko_1?VjD-^=KoK1_w;mE z|NpLUTH9Ol&P-Q*ed=8P`>AdpJsN#@hq|xV>-}>gA|XD|`{>K;PV})kZukhder+l~ zo>O&AW3P$nwW+u^RafV+zjx`03|tu4V6 z`F6f`zT0sWv$3{T726wI1XH@I(8_i^!JNsrI;-oaE2^FKs;Ii%eCs^PJfpL$E)s(2 zu5NB^oZD`_mzZss?W((7)Fz+4rm*aKA(6T9mSSw~Yb%S2Vlt_##1@KTmhFn0uVqa! zD@ComR2_=RmCv9{8OfC0IL}f|GN-HcZJUtu(-)v^lBu>j)z-N##gwkr3*N6#%;~kf z+$gJpV$SB>Zc#f$GawkN`5MKnZ)}~-*UR%1v$fH!)}P#XYMi;{=Aj%)Sg*pB^DZMG zRr^{lFQrQr0a;mVop(BEPC%&gsVe6)ML>lzOI5zKVkxN17t*ZArJ*`r=e6r}3ZtjB zlr-v^c1)=}b-T@Tow!phdg-P@sA$uy=P0yjQs=WW%}B_(`T0~DLqYjcQ7lxZprP7< zDY8jTLR(dtrI{{iXo^iAg{B(gQK*u6N864{DX7lRt!-D95EX#V%K6-BDGQ2PPD)jkounu!YNbfx4Jnn+DGFqHYju4s?{q0@x(ywr zz=&2wr&N-><8&)JO4Yej(p6rk6a^-7ZPn;Pld~E$!$R0M5gpxj>yE=o zz(5|1N_4zzJ0*cF%6z`)#GB{Rq(fng#Zqasmv!n0tdpp;lO)dIYV>Y%b_CB^G2G`SA!w@u$$=Jm=hJM(Wh*Nc!8I|bD@#@8)Vvfq1WC*JvayLK+pEF&g8G9!=}_wtf}D7}s?#E) z<^_V(bKMwhk1Ml$Du;TJ#7=`gn%GH_lh(&BiB%eVnoA8d=VBQfhVyYMW80$MyE*8d zR>Azx9GDBdwT?4}0}Exr78pl!U=?*3u_8H@#5PznjzbV2uvI*#!5}m90s{q;=AlV? z9Ll7zR5*q7yy)1(5=Nq!acCSah>J{__Een4PQ@xoNe)`lAX6}fhT&42J{Nnse_-N4 z5)AxD%d-OzBpSpo<2Z1VFp!j%dvJUPgay0|EvMk9V6d=mhUPr18r&CpDLKx=EW0>M z8BX~)Q$SDWFxDkPsZkDNsoHm{x~bq^&5fTuACnrJ3}TLDwiZaDr`- z%_uiWCS0l~eD58%@A#v|)N~e-1!;<%NLdgRUqYjr1|gI+!60g;MKJ!b zDCjFZ1A4qM*jcG~(4mQy%&pT{fqBZ3I5P}rkc3-vYYl!8Z_ke!CdPtDIG9cv#15vh zQ7v|R90a>9(R{NlqT92w#lnw)Dx^x8jv46z0n?z05Q zxP;|SGX^x6^?A(dXfR1pT_M(x84EV6Xc$mpDh7d&VuV6Tm>!Qwprz+gp{g2ek})X& zg33VXBvZ|R(3S}y0@ETabda4mrNvBvVFrr}3SpQDhlK$#12$u(2fCN^gGw6opngDs zvCtd{x&?BpG(F)VxRVYfD50lE>!5+c3bY#tmeEfnYxbO`qu&jkwY&;-bqFnKrVF?En=2k60Aw4o@u zGNaWM5a^@9tckug=&5V8h8YZcIOr#+g3dS)GmQj8TpDbYA9T^ussO7DYLH=CLJI}7 zmijP{OdnIwQ|zE?siEx#Rj|vj zU=mz{f-sKmBkCaND-50)HGm)!%CbQmm=j3h(F4 zAX$MN11IyX$;uK%u6B!!_-x)aWm0ttg51oV&Wc#oSSy~a zhz`l77=W566&3|7Nn#j@Srs@4?RgT@8*uWPA;A!#{R1`U?w(;KSSC77nKoq-vP1|m zykkg-5j3_rnT?E*I#_gQnr$=W4H&MaDMNa+{b0FTs-L?_^b$5ipBXbt;FUdeQ(>&i zkf9QzvBJXL-G?L@=QLwUk2RK*l@N$grNl5Ri!DoHEhuZN1dWj@EIL*&EKg$K2L3AL zNeHvRp*v>mkZYh{!@4qe_q35@_?0kZSR+haRmPGUWfO}d3<-J!aVx|q#< zTsTRFCDGc*wg7uKX+w^L_0)u!C5YhEF&I1=2Zq$RpMa5R!t@jJBuoS#gLTZf!eJFHkRW5*25;EtcPjJ{*-71jw9*)!G#?Qtj)OT*pWgq;%HG)q|$MJ|*s zX%bWNEEG(*SqceLXx1~U>0~GfK*-I_l2aiG3wZ%UW??r8Cd+A-#99&RCL^CNSXqn* zIGYS4qy|`SP|SR0jqygC%#3J|b7!!i3~A8EweNh5l9L|rt~ zxOcBvG!)=))h`Eao(QnaYGLJ12lZ@;R3}l7H*YJiO`y00SjlCV0C(uq5H)G81DM)_ zxyN@TEEbX*KXjf!P1v!)I!D5_>Vp49%bRkOg)Ss(YM6#cacHhB37SB`=_qtOoD5(JU_wYH zGtHrBEie~ri8sd3B$#N04wacKhtaSNp@jE5YE-E9rqd_uPx@#`ZK36q5kgF^Fw(Vc z0oNFs1_4YjW3>>)rx=sAuww$nDm&K3IMGIr3ibkRykit53#nKW(=hXz*(N3j{W6+G zEoQ>4d-D^hS53fgn8^xTN}+}bsR@l@2#?xg+X9s_)L_vT;}4Z^sBKE3o;SrFVlAw;nX zTfSj&8Ps78hglD#Ni>R~i|Pl<%&GLt1`sB)ktWR^woK{%WO;CSnRG?iVR=tc;d~Cnu5+VlsXW zRW$8C6_L=U8pE3Ki~xEeMxlHYgIUF*x*x8gUz7B(Fz3`J1o?{bYnU?NL;m=v0ux$b z8icI|k)>xKJbRFZhnl3MWguv?3bkm(2q6~GP@BA=2`HU1jC5CHgWfYHMlpjQf78fk$_0w|2Bv~k@IH%w= zm87*G>n{O5i0Gy-Z20;D{B#g*)#e?YOzZ_7y=&)lCzZ(-Ok8`J=c%f5MX*NB+l8dF zvY^dMowPi0Gs4=1+UH3}#<_Kcm!>3GCzE+?^g=zat+r;eGBLu=r=8TeV#OC)t(d%~ z#@2t@czIqgqzis!X`Wz*AMK69=QgXFVuv3a^gc<;Nmn<*;%9$i{FG#s=1G-Ek}b7K zOXU_^DotKamWW1JSg?ip#ZoS1orQYE6;!*!&&S3^-BG49z1?Ov(KHzh)<`C+8M|3b zHkIxxre#>wSUdd4g^~;#tT+0ww&#Z?S#;%zYg3C!7N34Yt+QOac>l1!gzuqQ6_Re$ z;I;>uCt05cZ`$%u-x#YJpMySKT9yq@kDx*4<^f9&XdzA5rC?Yrfcd7nVwrX^_fuh) z5li4KtFT&vAw$N4v#n6-!Vrd$2MixW`W_yWqgf2!&_1F4&$w|KOerQNGi{AqVn<=cA`rN6-G5XxJO0{;6$o z1W)x34gaEDZ`j*3v#WcDzWs;IAD3~<+54K`|1D18fKUD~yb8nr;p`K8;5>di>9kAH zDKYKRTSB~xcj4bx_%P_=w1+{fkK)6i(P5Z@hh7wKU4O3-pZYg=_15*`264UorF+$X ze)FF1{o`-F_{~@T^8V=$gYJI-8rVNP;_&l9`1e3_V)kM9@%aAzH-#7Y`%)x&hsEs0 zpF0Xdaq%!Tdtdl@-Nj!Na&PbaAAI#IuWvo~^`ESZZ{YVKMxT^NMz8R(Nz>QSNtY1q z5ug93H^3jv3@%+iaS2?)wZ|q05_D|7Z-IOHg+X^k!yy(Mz+p_Nm#E1AYXRqThq4zsR#E z26X7o2ns#y$&n7cx2X`~cG0}=d+_f-{DqP3!>qgm-JhKiy=dm86C>TfcYIP3(eFMx ze>f#V9=!CX|Gzo3BykX~l1N6G^3hsA9b8e zLGcS9a!2rTbNAgSGPBM7n&naA6W8;y@-=lGztp<9ezNsC?gtX@$8RZ4iR<{qpb2#y z6H($iB>dyw^q0K*QsQ63NwCo)?bp@TMwht%>1uoOt1|o7lfgIT5%1s3x3T<>l^ z8s6Xa#mHm8*+2*X_igke;#jYDst1D=4E;B1GM9+zpCQCXX{sK>$W^`h& zc=&F4AcCTveX9nc7K8Qi7!I