{"id":4854,"date":"2020-06-03T21:24:44","date_gmt":"2020-06-04T00:24:44","guid":{"rendered":"https:\/\/blog.clusterweb.com.br\/?p=4854"},"modified":"2020-06-03T21:31:25","modified_gmt":"2020-06-04T00:31:25","slug":"how-tcp-backlog-works-in-linux","status":"publish","type":"post","link":"https:\/\/blog.clusterweb.com.br\/?p=4854","title":{"rendered":"How TCP backlog works in Linux"},"content":{"rendered":"

When an application puts a socket into LISTEN state using the\u00a0listen<\/code><\/a>\u00a0syscall, it needs to specify a backlog for that socket. The backlog is usually described as the limit for the queue of incoming connections.<\/p>\n

\"TCP<\/p>\n

<\/p>\n

Because of the 3-way handshake used by TCP, an incoming connection goes through an intermediate state SYN RECEIVED before it reaches the ESTABLISHED state and can be returned by the\u00a0accept<\/code><\/a>\u00a0syscall to the application (see the part of the\u00a0TCP state diagram<\/a>\u00a0reproduced above). This means that a TCP\/IP stack has two options to implement the backlog queue for a socket in LISTEN state:<\/p>\n

    \n
  1. The implementation uses a single queue, the size of which is determined by the\u00a0backlog<\/code>\u00a0argument of the\u00a0listen<\/code>\u00a0syscall. When a SYN packet is received, it sends back a SYN\/ACK packet and adds the connection to the queue. When the corresponding ACK is received, the connection changes its state to ESTABLISHED and becomes eligible for handover to the application. This means that the queue can contain connections in two different state: SYN RECEIVED and ESTABLISHED. Only connections in the latter state can be returned to the application by the\u00a0accept<\/code>\u00a0syscall.<\/li>\n
  2. The implementation uses two queues, a SYN queue (or incomplete connection queue) and an accept queue (or complete connection queue). Connections in state SYN RECEIVED are added to the SYN queue and later moved to the accept queue when their state changes to ESTABLISHED, i.e. when the ACK packet in the 3-way handshake is received. As the name implies, the\u00a0accept<\/code>\u00a0call is then implemented simply to consume connections from the accept queue. In this case, the\u00a0backlog<\/code>\u00a0argument of the\u00a0listen<\/code>\u00a0syscall determines the size of the accept queue.<\/li>\n<\/ol>\n

    Historically, BSD derived TCP implementations use the first approach. That choice implies that when the maximum backlog is reached, the system will no longer send back SYN\/ACK packets in response to SYN packets. Usually the TCP implementation will simply drop the SYN packet (instead of responding with a RST packet) so that the client will retry. This is what is described in section 14.5,\u00a0listen<\/code>\u00a0Backlog Queue<\/em>\u00a0in W. Richard Stevens\u2019 classic textbook\u00a0TCP\/IP Illustrated, Volume 3<\/em>.<\/p>\n

    Note that Stevens actually explains that the BSD implementation does use two separate queues, but they behave as a single queue with a fixed maximum size determined by (but not necessary exactly equal to) the\u00a0backlog<\/code>\u00a0argument, i.e. BSD logically behaves as described in option 1:<\/p>\n

    The queue limit applies to the sum of [\u2026] the number of entries on the incomplete connection queue [\u2026] and [\u2026] the number of entries on the completed connection queue [\u2026].<\/p><\/blockquote>\n

    On Linux, things are different, as mentioned in the\u00a0man page<\/a>\u00a0of the\u00a0listen<\/code>\u00a0syscall:<\/p>\n

    The behavior of the\u00a0backlog<\/code>\u00a0argument on TCP sockets changed with Linux 2.2. Now it specifies the queue length for\u00a0completely<\/em>\u00a0established sockets waiting to be accepted, instead of the number of incomplete connection requests. The maximum length of the queue for incomplete sockets can be set using\u00a0\/proc\/sys\/net\/ipv4\/tcp_max_syn_backlog<\/code>.<\/p><\/blockquote>\n

    This means that current Linux versions use the second option with two distinct queues: a SYN queue with a size specified by a system wide setting and an accept queue with a size specified by the application.<\/p>\n

    The interesting question is now how such an implementation behaves if the accept queue is full and a connection needs to be moved from the SYN queue to the accept queue, i.e. when the ACK packet of the 3-way handshake is received. This case is handled by the\u00a0tcp_check_req<\/code>\u00a0function in\u00a0net\/ipv4\/tcp_minisocks.c<\/code>. The relevant code reads:<\/p>\n

    \n
    \n
            child =<\/span> inet_csk(<\/span><\/span>sk)<\/span>-<\/span>><\/span>icsk_af_ops-<\/span>><\/span>syn_recv_sock(<\/span><\/span>sk,<\/span> skb,<\/span> req,<\/span> NULL)<\/span>;<\/span>\r\n        if<\/span> (<\/span>child ==<\/span> NULL)<\/span>\r\n                goto<\/span> listen_overflow;<\/span>\r\n<\/code><\/pre>\n<\/div>\n<\/div>\n
    For IPv4, the first line of code will actually call\u00a0tcp_v4_syn_recv_sock<\/code>\u00a0in\u00a0net\/ipv4\/tcp_ipv4.c<\/code>, which contains the following code:<\/p>\n
    \n
    \n
            if<\/span> (<\/span>sk_acceptq_is_full(<\/span><\/span>sk)<\/span>)<\/span>\r\n                goto<\/span> exit_overflow;<\/span>\r\n<\/code><\/pre>\n<\/div>\n<\/div>\n
    We see here the check for the accept queue. The code after the\u00a0exit_overflow<\/code>\u00a0label will perform some cleanup, update the\u00a0ListenOverflows<\/code>\u00a0and\u00a0ListenDrops<\/code>\u00a0statistics in\u00a0\/proc\/net\/netstat<\/code>\u00a0and then return\u00a0NULL<\/code>. This will trigger the execution of the\u00a0listen_overflow<\/code>\u00a0code in\u00a0tcp_check_req<\/code>:<\/p>\n
    \n
    \n
    listen_overflow:<\/span>\r\n        if<\/span> (<\/span>!<\/span>sysctl_tcp_abort_on_overflow)<\/span> {<\/span>\r\n                inet_rsk(<\/span><\/span>req)<\/span>-<\/span>><\/span>acked =<\/span> 1<\/span>;<\/span>\r\n                return<\/span> NULL;<\/span>\r\n        }<\/span>\r\n<\/code><\/pre>\n<\/div>\n<\/div>\n
    This means that unless\u00a0\/proc\/sys\/net\/ipv4\/tcp_abort_on_overflow<\/code>\u00a0is set to 1 (in which case the code right after the code shown above will send a RST packet), the implementation basically does\u2026 nothing!<\/p>\n
    To summarize, if the TCP implementation in Linux receives the ACK packet of the 3-way handshake and the accept queue is full, it will basically ignore that packet. At first, this sounds strange, but remember that there is a timer associated with the SYN RECEIVED state: if the ACK packet is not received (or if it is ignored, as in the case considered here), then the TCP implementation will resend the SYN\/ACK packet (with a certain number of retries specified by\u00a0\/proc\/sys\/net\/ipv4\/tcp_synack_retries<\/code>\u00a0and using an\u00a0exponential backoff<\/a>\u00a0algorithm).<\/p>\n
    This can be seen in the following packet trace for a client attempting to connect (and send data) to a socket that has reached its maximum backlog:<\/p>\n
    \n
    \n
      0.000  127.0.0.1 -> 127.0.0.1  TCP 74 53302 > 9999 [SYN] Seq=0 Len=0\r\n  0.000  127.0.0.1 -> 127.0.0.1  TCP 74 9999 > 53302 [SYN, ACK] Seq=0 Ack=1 Len=0\r\n  0.000  127.0.0.1 -> 127.0.0.1  TCP 66 53302 > 9999 [ACK] Seq=1 Ack=1 Len=0\r\n  0.000  127.0.0.1 -> 127.0.0.1  TCP 71 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n  0.207  127.0.0.1 -> 127.0.0.1  TCP 71 [TCP Retransmission] 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n  0.623  127.0.0.1 -> 127.0.0.1  TCP 71 [TCP Retransmission] 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n  1.199  127.0.0.1 -> 127.0.0.1  TCP 74 9999 > 53302 [SYN, ACK] Seq=0 Ack=1 Len=0\r\n  1.199  127.0.0.1 -> 127.0.0.1  TCP 66 [TCP Dup ACK 6#1] 53302 > 9999 [ACK] Seq=6 Ack=1 Len=0\r\n  1.455  127.0.0.1 -> 127.0.0.1  TCP 71 [TCP Retransmission] 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n  3.123  127.0.0.1 -> 127.0.0.1  TCP 71 [TCP Retransmission] 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n  3.399  127.0.0.1 -> 127.0.0.1  TCP 74 9999 > 53302 [SYN, ACK] Seq=0 Ack=1 Len=0\r\n  3.399  127.0.0.1 -> 127.0.0.1  TCP 66 [TCP Dup ACK 10#1] 53302 > 9999 [ACK] Seq=6 Ack=1 Len=0\r\n  6.459  127.0.0.1 -> 127.0.0.1  TCP 71 [TCP Retransmission] 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n  7.599  127.0.0.1 -> 127.0.0.1  TCP 74 9999 > 53302 [SYN, ACK] Seq=0 Ack=1 Len=0\r\n  7.599  127.0.0.1 -> 127.0.0.1  TCP 66 [TCP Dup ACK 13#1] 53302 > 9999 [ACK] Seq=6 Ack=1 Len=0\r\n 13.131  127.0.0.1 -> 127.0.0.1  TCP 71 [TCP Retransmission] 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n 15.599  127.0.0.1 -> 127.0.0.1  TCP 74 9999 > 53302 [SYN, ACK] Seq=0 Ack=1 Len=0\r\n 15.599  127.0.0.1 -> 127.0.0.1  TCP 66 [TCP Dup ACK 16#1] 53302 > 9999 [ACK] Seq=6 Ack=1 Len=0\r\n 26.491  127.0.0.1 -> 127.0.0.1  TCP 71 [TCP Retransmission] 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n 31.599  127.0.0.1 -> 127.0.0.1  TCP 74 9999 > 53302 [SYN, ACK] Seq=0 Ack=1 Len=0\r\n 31.599  127.0.0.1 -> 127.0.0.1  TCP 66 [TCP Dup ACK 19#1] 53302 > 9999 [ACK] Seq=6 Ack=1 Len=0\r\n 53.179  127.0.0.1 -> 127.0.0.1  TCP 71 [TCP Retransmission] 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n106.491  127.0.0.1 -> 127.0.0.1  TCP 71 [TCP Retransmission] 53302 > 9999 [PSH, ACK] Seq=1 Ack=1 Len=5\r\n106.491  127.0.0.1 -> 127.0.0.1  TCP 54 9999 > 53302 [RST] Seq=1 Len=0\r\n<\/code><\/pre>\n<\/div>\n<\/div>\n
    Since the TCP implementation on the client side gets multiple SYN\/ACK packets, it will assume that the ACK packet was lost and resend it (see the lines with\u00a0TCP Dup ACK<\/code>\u00a0in the above trace). If the application on the server side reduces the backlog (i.e. consumes an entry from the accept queue) before the maximum number of SYN\/ACK retries has been reached, then the TCP implementation will eventually process one of the duplicate ACKs, transition the state of the connection from SYN RECEIVED to ESTABLISHED and add it to the accept queue. Otherwise, the client will eventually get a RST packet (as in the sample shown above).<\/p>\n
    The packet trace also shows another interesting aspect of this behavior. From the point of view of the client, the connection will be in state ESTABLISHED after reception of the first SYN\/ACK. If it sends data (without waiting for data from the server first), then that data will be retransmitted as well. Fortunately\u00a0TCP slow-start<\/a>\u00a0should limit the number of segments sent during this phase.<\/p>\n
    On the other hand, if the client first waits for data from the server and the server never reduces the backlog, then the end result is that on the client side, the connection is in state ESTABLISHED, while on the server side, the connection is considered CLOSED. This means that we end up with a\u00a0half-open connection<\/a>!<\/p>\n
    There is one other aspect that we didn\u2019t discuss yet. The quote from the\u00a0listen<\/code>\u00a0man page suggests that every SYN packet would result in the addition of a connection to the SYN queue (unless that queue is full). That is not exactly how things work. The reason is the following code in the\u00a0tcp_v4_conn_request<\/code>\u00a0function (which does the processing of SYN packets) in\u00a0net\/ipv4\/tcp_ipv4.c<\/code>:<\/p>\n
    \n
    \n
            \/* Accept backlog is full. If we have already queued enough\r\n         * of warm entries in syn queue, drop request. It is better than\r\n         * clogging syn queue with openreqs with exponentially increasing\r\n         * timeout.\r\n         *\/<\/span>\r\n        if<\/span> (<\/span>sk_acceptq_is_full(<\/span><\/span>sk)<\/span> &&<\/span> inet_csk_reqsk_queue_young(<\/span><\/span>sk)<\/span> ><\/span> 1<\/span>)<\/span> {<\/span>\r\n                NET_INC_STATS_BH(<\/span><\/span>sock_net(<\/span><\/span>sk)<\/span>,<\/span> LINUX_MIB_LISTENOVERFLOWS)<\/span>;<\/span>\r\n                goto<\/span> drop;<\/span>\r\n        }<\/span>\r\n<\/code><\/pre>\n<\/div>\n<\/div>\n
    What this means is that if the accept queue is full, then the kernel will impose a limit on the rate at which SYN packets are accepted. If too many SYN packets are received, some of them will be dropped. In this case, it is up to the client to retry sending the SYN packet and we end up with the same behavior as in BSD derived implementations.<\/p>\n
    To conclude, let\u2019s try to see why the design choice made by Linux would be superior to the traditional BSD implementation. Stevens makes the following interesting point:<\/p>\n
    The backlog can be reached if the completed connection queue fills (i.e., the server process or the server host is so busy that the process cannot call\u00a0accept<\/code>\u00a0fast enough to take the completed entries off the queue) or if the incomplete connection queue fills. The latter is the problem that HTTP servers face, when the round-trip time between the client and server is long, compared to the arrival rate of new connection requests, because a new SYN occupies an entry on this queue for one round-trip time. [\u2026]<\/p>\n
    The completed connection queue is almost always empty because when an entry is placed on this queue, the server\u2019s call to\u00a0accept<\/code>\u00a0returns, and the server takes the completed connection off the queue.<\/p><\/blockquote>\n
    The solution suggested by Stevens is simply to increase the backlog. The problem with this is that it assumes that an application is expected to tune the backlog not only taking into account how it intents to process newly established incoming connections, but also in function of traffic characteristics such as the round-trip time. The implementation in Linux effectively separates these two concerns: the application is only responsible for tuning the backlog such that it can call\u00a0accept<\/code>\u00a0fast enough to avoid filling the accept queue); a system administrator can then tune\u00a0\/proc\/sys\/net\/ipv4\/tcp_max_syn_backlog<\/code>\u00a0based on traffic characteristics.<\/p>\n","protected":false},"excerpt":{"rendered":"
    When an application puts a socket into LISTEN state using the\u00a0listen\u00a0syscall, it needs to specify a backlog for that socket. The backlog is usually described as the limit for the queue of incoming connections.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[1082,1,730,830,42,51,495,68,548],"tags":[1471,920,1065,14,21,1472],"class_list":["post-4854","post","type-post","status-publish","format-standard","hentry","category-centos-7-rhel-7","category-viazap","category-clusterweb","category-debian","category-leitura-recomendada","category-linux-linuxrs","category-profissional-de-ti","category-redes-2","category-ubuntu-2","tag-backlog","tag-how","tag-in","tag-linux","tag-tcp","tag-works"],"_links":{"self":[{"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/posts\/4854","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4854"}],"version-history":[{"count":5,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/posts\/4854\/revisions"}],"predecessor-version":[{"id":4859,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/posts\/4854\/revisions\/4859"}],"wp:attachment":[{"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4854"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4854"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4854"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}