{"id":1178,"date":"2021-12-29T23:56:21","date_gmt":"2021-12-29T15:56:21","guid":{"rendered":"https:\/\/blog.cauchyschwarz.com\/?p=1178"},"modified":"2021-12-29T23:56:26","modified_gmt":"2021-12-29T15:56:26","slug":"%e5%86%85%e6%a0%b8%e4%b8%ad%e7%9a%84tcp-hash-table","status":"publish","type":"post","link":"https:\/\/blog.cauchyschwarz.com\/?p=1178","title":{"rendered":"\u5185\u6838\u4e2d\u7684tcp hash table"},"content":{"rendered":"\n<p id=\"%E5%86%85%E6%A0%B8%E4%B8%AD%E7%9A%84tcp-hash-table\">\u5728net\/ipv4\/tcp_ipv4.c\u4e2d\u5b9a\u4e49\u4e86\u4e00\u4e2a<code>struct inet_hashinfo tcp_hashinfo<\/code>\uff0c\u7528\u4e8e\u8bb0\u5f55\u6240\u6709\u7684TCP socket\u3002<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 ez-toc-wrap-right counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fc488cbe311\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69fc488cbe311\" checked aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=1178\/#inet_hashinfo\" >inet_hashinfo<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=1178\/#ehash\" >ehash<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=1178\/#1%E6%AF%8F%E4%B8%AAbucket%E7%9A%84%E5%AE%9A%E4%B9%89\" >1.\u6bcf\u4e2abucket\u7684\u5b9a\u4e49<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=1178\/#2hash%E7%AE%97%E6%B3%95\" >2.hash\u7b97\u6cd5<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=1178\/#3ehash%E7%9A%84%E5%88%9D%E5%A7%8B%E5%8C%96\" >3.ehash\u7684\u521d\u59cb\u5316<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=1178\/#4ehash%E7%9A%84%E4%BF%AE%E6%94%B9\" >4.ehash\u7684\u4fee\u6539<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=1178\/#a%E5%90%91ehash%E4%B8%AD%E6%8F%92%E5%85%A5socket%EF%BC%9B\" >a.\u5411ehash\u4e2d\u63d2\u5165socket\uff1b<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/blog.cauchyschwarz.com\/?p=1178\/#b%E4%BB%8Eehash%E4%B8%AD%E5%88%A0%E9%99%A4socket%EF%BC%9B\" >b.\u4eceehash\u4e2d\u5220\u9664socket\uff1b<\/a><\/li><\/ul><\/li><\/ul><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h1 class=\"wp-block-heading\" id=\"inethashinfo\"><span class=\"ez-toc-section\" id=\"inet_hashinfo\"><\/span>inet_hashinfo<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"c\" class=\"language-c\">struct inet_hashinfo {\n\t<em>\/* This is for sockets with full identity only.  Sockets here will\n\t * always be without wildcards and will have the following invariant:\n\t *\n\t *          TCP_ESTABLISHED &lt;= sk-&gt;sk_state &lt; TCP_CLOSE\n\t *\n\t *\/<\/em>\n\tstruct inet_ehash_bucket\t*ehash;\n\tspinlock_t\t\t\t*ehash_locks;\n\tunsigned int\t\t\tehash_mask;\n\tunsigned int\t\t\tehash_locks_mask;\n\n\t<em>\/* Ok, let's try this, I give up, we do need a local binding\n\t * TCP hash as well as the others for fast bind\/connect.\n\t *\/<\/em>\n\tstruct kmem_cache\t\t*bind_bucket_cachep;\n\tstruct inet_bind_hashbucket\t*bhash;\n\tunsigned int\t\t\tbhash_size;\n\n\t<em>\/* The 2nd listener table hashed by local port and address *\/<\/em>\n\tunsigned int\t\t\tlhash2_mask;\n\tstruct inet_listen_hashbucket\t*lhash2;\n\n\t<em>\/* All the above members are written once at bootup and\n\t * never written again _or_ are predominantly read-access.\n\t *\n\t * Now align to a new cache line as all the following members\n\t * might be often dirty.\n\t *\/<\/em>\n\t<em>\/* All sockets in TCP_LISTEN state will be in listening_hash.\n\t * This is the only table where wildcard'd TCP sockets can\n\t * exist.  listening_hash is only hashed by local port number.\n\t * If lhash2 is initialized, the same socket will also be hashed\n\t * to lhash2 by port and address.\n\t *\/<\/em>\n\tstruct inet_listen_hashbucket\tlistening_hash[INET_LHTABLE_SIZE]\n\t\t\t\t\t____cacheline_aligned_in_smp;\n};\n<\/code><\/pre>\n\n\n\n<p>\u4eceinet_hashinfo\u7684\u5b9a\u4e49\u53ef\u4ee5\u770b\u51fa\uff0c\u8fd9\u4e2ahash table\u662f\u5206\u4e3a\u4e09\u90e8\u5206\u7684\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>\u7528\u4e8e\u8bb0\u5f55\u5df2\u7ecf\u5efa\u7acb\u8fde\u63a5\u7684TCP\u8fde\u63a5\u7684socket\u7684hash table&nbsp;<strong>ehash<\/strong><\/li><li>\u5904\u4e8elisten\u72b6\u6001\u7684TCP socket\u7684hash table&nbsp;<strong>listening_hash<\/strong><br><strong>listening_hash<\/strong>\u53ea\u7528\u76d1\u542c\u7aef\u53e3\u6765hash\uff1b<\/li><li>\u6839\u636e\u76d1\u542c\u7aef\u53e3\u548c\u5730\u5740\u6765hash\u7684\uff0c\u7528\u4e8e\u8bb0\u5f55listen\u72b6\u6001socket\u7684<strong>lhash2<\/strong>\uff1b<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"ehash\"><span class=\"ez-toc-section\" id=\"ehash\"><\/span>ehash<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1%E6%AF%8F%E4%B8%AAbucket%E7%9A%84%E5%AE%9A%E4%B9%89\"><span class=\"ez-toc-section\" id=\"1%E6%AF%8F%E4%B8%AAbucket%E7%9A%84%E5%AE%9A%E4%B9%89\"><\/span>1.\u6bcf\u4e2abucket\u7684\u5b9a\u4e49<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>\u5bf9\u4e8e\u5df2\u7ecf\u5b8c\u5168\u5efa\u7acb\u8fde\u63a5\u7684TCP socket\uff0cehash\u7684\u6bcf\u4e2a<strong>inet_ehash_bucket<\/strong>\u7684\u5b9a\u4e49\u662f\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">struct inet_ehash_bucket {\n\tstruct hlist_nulls_head chain;\n};\n<\/code><\/pre>\n\n\n\n<p>\u7ee7\u7eed\u770b\u6bcf\u4e2abucket\u91cc\u7684\u94fe\u8868\u7684\u5b9a\u4e49\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">struct hlist_nulls_head {\n\tstruct hlist_nulls_node *first;\n};\n<\/code><\/pre>\n\n\n\n<p>\u7ee7\u7eed\u770b\u94fe\u8868\u7684\u6bcf\u4e2a\u8282\u70b9\u7684\u5b9a\u4e49\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">struct hlist_nulls_node {\n\tstruct hlist_nulls_node *next, **pprev;\n};\n<\/code><\/pre>\n\n\n\n<p>\u5c31\u662f\u4e00\u4e2a\u666e\u901a\u7684\u94fe\u8868\u8282\u70b9\u5b9a\u4e49\uff0c\u4f46\u662f\u8fd9\u4e2a\u547d\u540d\u91cc\u5e26\u4e86\u4e00\u4e2a<em>nulls<\/em>\uff0c\u56e0\u4e3a\u94fe\u8868\u7684\u672b\u5c3e\u4e0d\u662f\u4e00\u4e2aNULL\u6307\u9488\uff0c\u800c\u662f\u6240\u8c13\u7684<code>null marker<\/code>\uff1a\u5982\u679cnext\u6307\u9488\u7684\u503c\u7684\u6700\u540e\u4e00\u4f4d\u662f1\uff0c\u90a3\u4e48\u8fd9\u5c31\u4e0d\u662f\u4e00\u4e2a\u6709\u6548\u7684\u94fe\u8868\u8282\u70b9\u6307\u9488\uff0c\u800c\u662f\u4e00\u4e2a\u7279\u6b8a\u7684null marker\uff0c\u5c06\u8fd9\u4e2a\u503c\u53f3\u79fb\u4e00\u4f4d\u6709\u4ed6\u7528\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2hash%E7%AE%97%E6%B3%95\"><span class=\"ez-toc-section\" id=\"2hash%E7%AE%97%E6%B3%95\"><\/span>2.hash\u7b97\u6cd5<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>\u5c31\u662f\u6839\u636ehash\u8868\u91cc\u8bbe\u7f6e\u7684ehash_mask\u548c\u7ed9\u5b9a\u7684hash\u503c\u76f8\u4e0e\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">static inline struct inet_ehash_bucket *inet_ehash_bucket(\n\tstruct inet_hashinfo *hashinfo,\n\tunsigned int hash)\n{\n\treturn &amp;hashinfo-&gt;ehash[hash &amp; hashinfo-&gt;ehash_mask];\n}\n<\/code><\/pre>\n\n\n\n<p>\u8fd9\u4e2a\u4f20\u5165\u7684hash\u503c\u7684\u7b97\u6cd5\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">static u32 inet_ehashfn(const struct net *net, const __be32 laddr,\n\t\t\tconst __u16 lport, const __be32 faddr,\n\t\t\tconst __be16 fport)\n{\n\tstatic u32 inet_ehash_secret __read_mostly;\n\n\tnet_get_random_once(&amp;inet_ehash_secret, sizeof(inet_ehash_secret));\n\n\treturn __inet_ehashfn(laddr, lport, faddr, fport,\n\t\t\t      inet_ehash_secret + net_hash_mix(net));\n}\n<\/code><\/pre>\n\n\n\n<p>\u8fd9\u4e2ainet_ehash_secret\u662f\u4e00\u6b21\u6027\u521d\u59cb\u5316\u7684\u968f\u673a\u6570\u3002net_hash_mix(net)\u5219\u662f\u628anet namespace\u8fd9\u4e2a\u56e0\u7d20\u4e5f\u52a0\u8fdb\u53bb\uff0c\u6700\u7ec8\u5b9e\u9645\u4e0a\u4f7f\u7528\u7684hash\u51fd\u6570\u662f\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">static inline unsigned int __inet_ehashfn(const __be32 laddr,\n\t\t\t\t\t  const __u16 lport,\n\t\t\t\t\t  const __be32 faddr,\n\t\t\t\t\t  const __be16 fport,\n\t\t\t\t\t  u32 initval)\n{\n\treturn jhash_3words((__force __u32) laddr,\n\t\t\t    (__force __u32) faddr,\n\t\t\t    ((__u32) lport) &lt;&lt; 16 | (__force __u32)fport,\n\t\t\t    initval);\n}\n<\/code><\/pre>\n\n\n\n<p>\u5177\u4f53\u7684hash\u7b97\u6cd5\u5c31\u4e0d\u7ee7\u7eed\u770b\u4e86\uff0c\u603b\u4e4b\u5c31\u662f\u6839\u636eTCP\u8fde\u63a5\u7684\u56db\u5143\u7956\uff0cinet_ehash_secret\uff0cnet namespace\u8fd93\u79cd\u56e0\u7d20\u7b97\u51fa\u7684\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3ehash%E7%9A%84%E5%88%9D%E5%A7%8B%E5%8C%96\"><span class=\"ez-toc-section\" id=\"3ehash%E7%9A%84%E5%88%9D%E5%A7%8B%E5%8C%96\"><\/span>3.ehash\u7684\u521d\u59cb\u5316<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>\u5728tcp.c\u7684<code>tcp_init<\/code>\u51fd\u6570\u91cc\u4f1a\u521d\u59cb\u5316\u6574\u4e2atcp_hashinfo\u8868\uff0c\u5176\u4e2d<code>alloc_large_system_hash<\/code>\u7528\u4e8e\u521d\u59cb\u5316ehash\u548cbhash\u3002\u53ef\u4ee5\u4ece<code>alloc_large_system_hash<\/code>\u7684\u5b9e\u73b0\u4e2d\u770b\u51fa<code>ehash_mask<\/code>\u4e4b\u7c7b\u7684\u53d8\u91cf\u65e2\u662fmask\uff0c\u53c8\u662fhash\u8868\u7684\u5bb9\u91cf\uff0c\u53ea\u4e0d\u8fc7\u8fd9\u4e2a\u5bb9\u91cf\u6b63\u597d\u662f2\u7684\u5e42\uff0c\u65b9\u4fbfhash\u7528\u4e0e\u7684\u65b9\u5f0f\u53d6\u4f59\u6570\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4ehash%E7%9A%84%E4%BF%AE%E6%94%B9\"><span class=\"ez-toc-section\" id=\"4ehash%E7%9A%84%E4%BF%AE%E6%94%B9\"><\/span>4.ehash\u7684\u4fee\u6539<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"a%E5%90%91ehash%E4%B8%AD%E6%8F%92%E5%85%A5socket\"><span class=\"ez-toc-section\" id=\"a%E5%90%91ehash%E4%B8%AD%E6%8F%92%E5%85%A5socket%EF%BC%9B\"><\/span>a.\u5411ehash\u4e2d\u63d2\u5165socket\uff1b<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<p>\u6839\u636e\u4eceehash\u4e2d\u5220\u9664socket\u7684\u51fd\u6570\uff0c\u5012\u7740\u5f80\u56de\u627e\uff0c\u53d1\u73b0\u662f<code>tcp_conn_request<\/code>\u51fd\u6570\u5728\u5f80hash\u8868\u91cc\u63d2\u5165socket\uff0c\u4e0d\u8fc7\u8fd9\u65f6\u5019\u63d2\u5165\u7684\u662f<code>struct request_sock *<\/code>\uff0c\u5728\u5b8c\u6210\u4e09\u6b21\u63e1\u624b\u4e4b\u540e\uff0c\u518d\u5728<code>tcp_v4_syn_recv_sock<\/code>\u51fd\u6570\u4e2d\u63d2\u5165\u65b0\u7684<code>struct sock *<\/code>\uff0c\u5e76\u79fb\u9664\u4e4b\u524d\u63d2\u5165\u7684<code>struct request_sock *<\/code>\u3002<\/p>\n\n\n\n<h4 class=\"wp-block-heading\" id=\"b%E4%BB%8Eehash%E4%B8%AD%E5%88%A0%E9%99%A4socket\"><span class=\"ez-toc-section\" id=\"b%E4%BB%8Eehash%E4%B8%AD%E5%88%A0%E9%99%A4socket%EF%BC%9B\"><\/span>b.\u4eceehash\u4e2d\u5220\u9664socket\uff1b<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<ul class=\"wp-block-list\"><li><code>reqsk_queue_unlink<\/code>\u4e2d\u5220\u9664<code>struct request_sock *<\/code>\uff0c\u5e76\u4e14\u6e05\u9664\u8fd9\u4e2a<code>request_sock<\/code>\u76f8\u5e94\u7684timer\uff1b<\/li><li><code>inet_unhash<\/code>\u4e2d\u5220\u9664\uff0c<code>inet_hash<\/code>\u4e0d\u4ec5\u5220\u9664ehash\u4e2d\u7684socket,\u4e5f\u53ef\u4ee5\u5220\u9664listen\u8868\u4e2d\u7684socket\uff0c\u4f46\u662f<code>inet_unhash<\/code>\u5220\u9664\u65f6\u4e0d\u4f1a\u5220\u9664\u76f8\u5e94\u7684timer\uff1b<\/li><li><code>inet_twsk_hashdance<\/code>\u4e2d\u5220\u9664\uff1b<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u5728net\/ipv4\/tcp_ipv4.c\u4e2d\u5b9a\u4e49\u4e86\u4e00\u4e2astruct inet_hashinfo tcp_hashinfo\uff0c\u7528\u4e8e\u8bb0\u5f55\u6240\u6709\u7684TCP socket\u3002 inet_hashinfo \u4eceinet_h&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[37,100],"class_list":["post-1178","post","type-post","status-publish","format-standard","hentry","category-10","tag-kernel","tag-tcp"],"_links":{"self":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/1178","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1178"}],"version-history":[{"count":1,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/1178\/revisions"}],"predecessor-version":[{"id":1179,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/1178\/revisions\/1179"}],"wp:attachment":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1178"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}