From yasuoka@openbsd.org Fri Nov 7 02:19:52 2014 Delivered-To: david@gwynne.id.au Received: by 10.152.87.225 with SMTP id bb1csp65627lab; Thu, 6 Nov 2014 08:19:53 -0800 (PST) X-Received: by 10.68.192.1 with SMTP id hc1mr5230158pbc.87.1415290792491; Thu, 06 Nov 2014 08:19:52 -0800 (PST) Return-Path: Received: from mail.2ndsoft.com (s247156.ppp.asahi-net.or.jp. [220.157.247.156]) by mx.google.com with ESMTP id px9si6272237pdb.159.2014.11.06.08.19.51 for ; Thu, 06 Nov 2014 08:19:52 -0800 (PST) Received-SPF: neutral (google.com: 220.157.247.156 is neither permitted nor denied by manual fallback record for domain of yasuoka@openbsd.org) client-ip=220.157.247.156; Authentication-Results: mx.google.com; spf=neutral (google.com: 220.157.247.156 is neither permitted nor denied by manual fallback record for domain of yasuoka@openbsd.org) smtp.mail=yasuoka@openbsd.org Received: from localhost (fe80::20c:29ff:fe63:1e7c [IPv6:fe80::20c:29ff:fe63:1e7c]); by mail.2ndsoft.com (OpenSMTPD) with ESMTP id ecccd1ee; Fri, 7 Nov 2014 01:19:49 +0900 (JST) Date: Fri, 07 Nov 2014 01:19:45 +0900 (JST) Message-Id: <20141107.011945.1299814570218524952.yasuoka@openbsd.org> To: david@gwynne.id.au Cc: tech@openbsd.org Subject: Re: use siphash for in_pcb hash key lookups From: YASUOKA Masahiko In-Reply-To: <20141104045049.GG265@animata.net> References: <20141104045049.GG265@animata.net> X-Mailer: Mew version 6.4 on Emacs 24.3 / Mule 6.0 (HANACHIRUSATO) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Status: RO Content-Length: 8325 Lines: 242 On Tue, 4 Nov 2014 14:50:49 +1000 David Gwynne wrote: > this uses siphash to protect the in_pcb hashes. this is pretty much > a textbook example of what siphash should be used for. > > tests? ok? Giving inpcb_hash() to LIST_* macros via INPCB*HASH() caused calling inpcb_hash() multiple times unintentionally. Fixed. Diff is as follows. Otherwise ok yasuoka. test yasuoka. Index: netinet/in_pcb.c =================================================================== RCS file: /cvs/src/sys/netinet/in_pcb.c,v retrieving revision 1.161 diff -u -p -r1.161 in_pcb.c --- netinet/in_pcb.c 28 Oct 2014 11:02:38 -0000 1.161 +++ netinet/in_pcb.c 6 Nov 2014 16:18:14 -0000 @@ -91,6 +91,7 @@ #include #include + #include #include @@ -121,17 +122,68 @@ int in_pcbresize (struct inpcbtable *, i #define INPCBHASH_LOADFACTOR(_x) (((_x) * 3) / 4) +struct inpcbhead *in_pcbhash(struct inpcbtable *, int, + const struct in_addr *, u_short, const struct in_addr *, u_short); +struct inpcbhead *in6_pcbhash(struct inpcbtable *, int, + const struct in6_addr *, u_short, const struct in6_addr *, u_short); +struct inpcbhead *in_pcblhash(struct inpcbtable *, int, u_short); + +struct inpcbhead * +in_pcbhash(struct inpcbtable *table, int rdom, + const struct in_addr *faddr, u_short fport, + const struct in_addr *laddr, u_short lport) +{ + SIPHASH_CTX ctx; + u_int32_t nrdom = htonl(rdom); + + SipHash24_Init(&ctx, &table->inpt_key); + SipHash24_Update(&ctx, &nrdom, sizeof(nrdom)); + SipHash24_Update(&ctx, faddr, sizeof(*faddr)); + SipHash24_Update(&ctx, &fport, sizeof(fport)); + SipHash24_Update(&ctx, laddr, sizeof(*laddr)); + SipHash24_Update(&ctx, &lport, sizeof(lport)); + + return (&table->inpt_hashtbl[SipHash24_End(&ctx) & table->inpt_hash]); +} + #define INPCBHASH(table, faddr, fport, laddr, lport, rdom) \ - &(table)->inpt_hashtbl[(ntohl((faddr)->s_addr) + \ - ntohs((fport)) + ntohs((lport)) + (rdom)) & (table->inpt_hash)] + in_pcbhash(table, rdom, faddr, fport, laddr, lport) + +struct inpcbhead * +in6_pcbhash(struct inpcbtable *table, int rdom, + const struct in6_addr *faddr, u_short fport, + const struct in6_addr *laddr, u_short lport) +{ + SIPHASH_CTX ctx; + u_int32_t nrdom = htonl(rdom); + + SipHash24_Init(&ctx, &table->inpt_key); + SipHash24_Update(&ctx, &nrdom, sizeof(nrdom)); + SipHash24_Update(&ctx, faddr, sizeof(*faddr)); + SipHash24_Update(&ctx, &fport, sizeof(fport)); + SipHash24_Update(&ctx, laddr, sizeof(*laddr)); + SipHash24_Update(&ctx, &lport, sizeof(lport)); + + return (&table->inpt_hashtbl[SipHash24_End(&ctx) & table->inpt_hash]); +} #define IN6PCBHASH(table, faddr, fport, laddr, lport, rdom) \ - &(table)->inpt_hashtbl[(ntohl((faddr)->s6_addr32[0] ^ \ - (faddr)->s6_addr32[3]) + ntohs((fport)) + ntohs((lport)) + (rdom)) & \ - (table->inpt_hash)] + in6_pcbhash(table, rdom, faddr, fport, laddr, lport) + +struct inpcbhead * +in_pcblhash(struct inpcbtable *table, int rdom, u_short lport) +{ + SIPHASH_CTX ctx; + u_int32_t nrdom = htonl(rdom); -#define INPCBLHASH(table, lport, rdom) \ - &(table)->inpt_lhashtbl[(ntohs((lport)) + (rdom)) & table->inpt_lhash] + SipHash24_Init(&ctx, &table->inpt_key); + SipHash24_Update(&ctx, &nrdom, sizeof(nrdom)); + SipHash24_Update(&ctx, &lport, sizeof(lport)); + + return (&table->inpt_lhashtbl[SipHash24_End(&ctx) & table->inpt_lhash]); +} + +#define INPCBLHASH(table, lport, rdom) in_pcblhash(table, rdom, lport) void in_pcbinit(struct inpcbtable *table, int hashsize) @@ -148,6 +200,7 @@ in_pcbinit(struct inpcbtable *table, int panic("in_pcbinit: hashinit failed for lport"); table->inpt_lastport = 0; table->inpt_count = 0; + arc4random_buf(&table->inpt_key, sizeof(table->inpt_key)); } /* @@ -176,6 +229,7 @@ in_pcballoc(struct socket *so, struct in { struct inpcb *inp; int s; + struct inpcbhead *head; splsoftassert(IPL_SOFTNET); @@ -199,11 +253,11 @@ in_pcballoc(struct socket *so, struct in table->inpt_count++ > INPCBHASH_LOADFACTOR(table->inpt_hash)) (void)in_pcbresize(table, (table->inpt_hash + 1) * 2); TAILQ_INSERT_HEAD(&table->inpt_queue, inp, inp_queue); - LIST_INSERT_HEAD(INPCBLHASH(table, inp->inp_lport, - inp->inp_rtableid), inp, inp_lhash); - LIST_INSERT_HEAD(INPCBHASH(table, &inp->inp_faddr, inp->inp_fport, - &inp->inp_laddr, inp->inp_lport, rtable_l2(inp->inp_rtableid)), - inp, inp_hash); + head = INPCBLHASH(table, inp->inp_lport, inp->inp_rtableid); + LIST_INSERT_HEAD(head, inp, inp_lhash); + head = INPCBHASH(table, &inp->inp_faddr, inp->inp_fport, + &inp->inp_laddr, inp->inp_lport, rtable_l2(inp->inp_rtableid)); + LIST_INSERT_HEAD(head, inp, inp_hash); splx(s); so->so_pcb = inp; inp->inp_hops = -1; @@ -659,9 +713,11 @@ in_pcblookup(struct inpcbtable *table, v u_int16_t fport = fport_arg, lport = lport_arg; struct in_addr faddr = *(struct in_addr *)faddrp; struct in_addr laddr = *(struct in_addr *)laddrp; + struct inpcbhead *head; rdomain = rtable_l2(rdomain); /* convert passed rtableid to rdomain */ - LIST_FOREACH(inp, INPCBLHASH(table, lport, rdomain), inp_lhash) { + head = INPCBLHASH(table, lport, rdomain); + LIST_FOREACH(inp, head, inp_lhash) { if (rtable_l2(inp->inp_rtableid) != rdomain) continue; if (inp->inp_lport != lport) @@ -870,25 +926,24 @@ in_pcbrehash(struct inpcb *inp) { struct inpcbtable *table = inp->inp_table; int s; + struct inpcbhead *head; s = splnet(); LIST_REMOVE(inp, inp_lhash); - LIST_INSERT_HEAD(INPCBLHASH(table, inp->inp_lport, inp->inp_rtableid), - inp, inp_lhash); + head = INPCBLHASH(table, inp->inp_lport, inp->inp_rtableid); + LIST_INSERT_HEAD(head, inp, inp_lhash); LIST_REMOVE(inp, inp_hash); #ifdef INET6 - if (inp->inp_flags & INP_IPV6) { - LIST_INSERT_HEAD(IN6PCBHASH(table, &inp->inp_faddr6, - inp->inp_fport, &inp->inp_laddr6, inp->inp_lport, - rtable_l2(inp->inp_rtableid)), inp, inp_hash); - } else { -#endif /* INET6 */ - LIST_INSERT_HEAD(INPCBHASH(table, &inp->inp_faddr, - inp->inp_fport, &inp->inp_laddr, inp->inp_lport, - rtable_l2(inp->inp_rtableid)), inp, inp_hash); -#ifdef INET6 - } -#endif /* INET6 */ + if (inp->inp_flags & INP_IPV6) + head = IN6PCBHASH(table, &inp->inp_faddr6, inp->inp_fport, + &inp->inp_laddr6, inp->inp_lport, + rtable_l2(inp->inp_rtableid)); + else +#endif /* INET6 */ + head = INPCBHASH(table, &inp->inp_faddr, inp->inp_fport, + &inp->inp_laddr, inp->inp_lport, + rtable_l2(inp->inp_rtableid)); + LIST_INSERT_HEAD(head, inp, inp_hash); splx(s); } @@ -915,6 +970,7 @@ in_pcbresize(struct inpcbtable *table, i table->inpt_lhashtbl = nlhashtbl; table->inpt_hash = nhash; table->inpt_lhash = nlhash; + arc4random_buf(&table->inpt_key, sizeof(table->inpt_key)); TAILQ_FOREACH_SAFE(inp0, &table->inpt_queue, inp_queue, inp1) { in_pcbrehash(inp0); Index: netinet/in_pcb.h =================================================================== RCS file: /cvs/src/sys/netinet/in_pcb.h,v retrieving revision 1.86 diff -u -p -r1.86 in_pcb.h --- netinet/in_pcb.h 12 Jul 2014 21:06:34 -0000 1.86 +++ netinet/in_pcb.h 6 Nov 2014 16:18:14 -0000 @@ -70,6 +70,8 @@ #include #include +#include + struct pf_state_key; union inpaddru { @@ -153,9 +155,12 @@ struct inpcb { int inp_divertfl; /* divert flags */ }; +LIST_HEAD(inpcbhead, inpcb); + struct inpcbtable { TAILQ_HEAD(inpthead, inpcb) inpt_queue; - LIST_HEAD(inpcbhead, inpcb) *inpt_hashtbl, *inpt_lhashtbl; + struct inpcbhead *inpt_hashtbl, *inpt_lhashtbl; + SIPHASH_KEY inpt_key; u_long inpt_hash, inpt_lhash; u_int16_t inpt_lastport; int inpt_count; Index: conf/files =================================================================== RCS file: /cvs/src/sys/conf/files,v retrieving revision 1.583 diff -u -p -r1.583 files --- conf/files 20 Oct 2014 00:38:50 -0000 1.583 +++ conf/files 6 Nov 2014 16:18:15 -0000 @@ -873,6 +873,7 @@ file crypto/hmac.c wlan | (softraid & file crypto/gmac.c (inet & ipsec) | crypto file crypto/key_wrap.c wlan file crypto/idgen.c inet6 | nfsclient | nfsserver +file crypto/siphash.c file netmpls/mpls_input.c mpls file netmpls/mpls_output.c mpls file netmpls/mpls_proto.c mpls