Kernel Connection Multiplexor

KCM의 NxM 구조

Kernel Connection Multiplexor(KCM)는 일반 응용 프로토콜을 위해 TCP 위에 메시지 기반 인터페이스를 제공하는 메커니즘입니다. 애플리케이션은 datagram 소켓 API로 응용 프로토콜 메시지를 효율적으로 송수신하면서 실제 전송에는 TCP 연결을 사용할 수 있습니다.

커널의 NxM multiplexor는 여러 KCM 소켓과 여러 TCP 소켓을 연결합니다. 각 TCP 소켓에는 KCM 전용 상태를 담는 Psock이 하나씩 배치되고, multiplexor가 위쪽 KCM 소켓과 아래쪽 Psock/TCP 연결 사이에서 메시지를 조향합니다.

.. SPDX-License-Identifier: GPL-2.0

=============================
Kernel Connection Multiplexor
=============================

Kernel Connection Multiplexor (KCM) is a mechanism that provides a message based
interface over TCP for generic application protocols. With KCM an application
can efficiently send and receive application protocol messages over TCP using
datagram sockets.

KCM implements an NxM multiplexor in the kernel as diagrammed below::

    +------------+   +------------+   +------------+   +------------+
    | KCM socket |   | KCM socket |   | KCM socket |   | KCM socket |
    +------------+   +------------+   +------------+   +------------+
        |                 |               |                |
        +-----------+     |               |     +----------+
                    |     |               |     |
                +----------------------------------+
                |           Multiplexor            |
                +----------------------------------+
                    |   |           |           |  |
        +---------+   |           |           |  ------------+
        |             |           |           |              |
    +----------+  +----------+  +----------+  +----------+ +----------+
    |  Psock   |  |  Psock   |  |  Psock   |  |  Psock   | |  Psock   |
    +----------+  +----------+  +----------+  +----------+ +----------+
        |              |           |            |             |
    +----------+  +----------+  +----------+  +----------+ +----------+
    | TCP sock |  | TCP sock |  | TCP sock |  | TCP sock | | TCP sock |
    +----------+  +----------+  +----------+  +----------+ +----------+

KCM 소켓, multiplexor와 Psock

KCM 소켓은 multiplexor의 사용자 인터페이스입니다. 한 multiplexor에 묶인 모든 KCM 소켓은 기능적으로 동등하므로 사용자 공간 thread끼리 별도 동기화를 하지 않아도 서로 다른 소켓에서 I/O를 병렬로 수행할 수 있습니다.

송신 경로에서는 KCM 소켓에 기록한 메시지 전체를 적절한 TCP 소켓에 원자적으로 보냅니다. 수신 경로에서는 각 TCP 소켓의 Psock이 스트림 조각으로부터 완전한 메시지를 조립하고, multiplexor가 완성된 메시지를 KCM 소켓으로 보냅니다.

TCP 소켓을 multiplexor에 연결하면 소켓마다 Psock 구조체가 할당됩니다. Psock은 수신 메시지 조립 상태와 해당 연결에만 필요한 KCM 정보를 보관합니다. 한 multiplexor에 붙는 TCP 연결은 모두 같은 목적지로 향한다고 가정하며, 송신 시 여러 연결을 부하 분산에 사용할 수 있습니다. KCM은 `SOCK_DGRAM`과 `SOCK_SEQPACKET`을 지원하고 `sendmmsg`·`recvmmsg`를 포함한 일반 send/recv 호출을 사용합니다.

KCM sockets
===========

The KCM sockets provide the user interface to the multiplexor. All the KCM sockets
bound to a multiplexor are considered to have equivalent function, and I/O
operations in different sockets may be done in parallel without the need for
synchronization between threads in userspace.

Multiplexor
===========

The multiplexor provides the message steering. In the transmit path, messages
written on a KCM socket are sent atomically on an appropriate TCP socket.
Similarly, in the receive path, messages are constructed on each TCP socket
(Psock) and complete messages are steered to a KCM socket.

TCP sockets & Psocks
====================

TCP sockets may be bound to a KCM multiplexor. A Psock structure is allocated
for each bound TCP socket, this structure holds the state for constructing
messages on receive as well as other connection specific information for KCM.

Connected mode semantics
========================

Each multiplexor assumes that all attached TCP connections are to the same
destination and can use the different connections for load balancing when
transmitting. The normal send and recv calls (include sendmmsg and recvmmsg)
can be used to send and receive messages from the KCM socket.

Socket types
============

KCM supports SOCK_DGRAM and SOCK_SEQPACKET socket types.

BPF 메시지 경계와 TCP 소켓 관리

TCP는 byte stream이므로 응용 프로토콜 헤더를 해석해 메시지 경계를 찾아야 합니다. TCP 소켓을 KCM multiplexor에 연결할 때 BPF 프로그램을 함께 지정합니다. 새 메시지 수신이 시작되면 이 프로그램에 지금까지 받은 바이트가 든 `skbuff`가 전달되고, 프로그램은 헤더를 해석해 전체 메시지 길이를 반환합니다. KCM은 그 길이만큼 조립한 뒤 하나의 메시지로 전달합니다.

연결된 TCP 소켓의 `POLLIN`과 `POLLOUT`은 multiplexor가 처리합니다. 연결 해제나 다른 상태 오류가 생기면 TCP 소켓에 오류를 게시해 `POLLERR`를 일으키고 KCM은 그 소켓 사용을 중단합니다. 애플리케이션은 오류 통지를 받으면 소켓을 KCM에서 분리하고 닫은 뒤 필요하면 새 연결을 만들어야 합니다.

최대 수신 메시지 크기는 연결된 TCP 소켓의 receive buffer 크기 `SO_RCVBUF`입니다. BPF가 보고한 길이가 이 한도를 넘으면 TCP 소켓에 `EMSGSIZE`가 게시되며 BPF 자체도 별도 최대값을 검사할 수 있습니다. 메시지 조립 제한 시간은 TCP 소켓의 `SO_RCVTIMEO`를 사용하고, 완성 전에 만료되면 `ETIMEDOUT`이 게시됩니다.

Message delineation
-------------------

Messages are sent over a TCP stream with some application protocol message
format that typically includes a header which frames the messages. The length
of a received message can be deduced from the application protocol header
(often just a simple length field).

A TCP stream must be parsed to determine message boundaries. Berkeley Packet
Filter (BPF) is used for this. When attaching a TCP socket to a multiplexor a
BPF program must be specified. The program is called at the start of receiving
a new message and is given an skbuff that contains the bytes received so far.
It parses the message header and returns the length of the message. Given this
information, KCM will construct the message of the stated length and deliver it
to a KCM socket.

TCP socket management
---------------------

When a TCP socket is attached to a KCM multiplexor data ready (POLLIN) and
write space available (POLLOUT) events are handled by the multiplexor. If there
is a state change (disconnection) or other error on a TCP socket, an error is
posted on the TCP socket so that a POLLERR event happens and KCM discontinues
using the socket. When the application gets the error notification for a
TCP socket, it should unattach the socket from KCM and then handle the error
condition (the typical response is to close the socket and create a new
connection if necessary).

KCM limits the maximum receive message size to be the size of the receive
socket buffer on the attached TCP socket (the socket buffer size can be set by
SO_RCVBUF). If the length of a new message reported by the BPF program is
greater than this limit a corresponding error (EMSGSIZE) is posted on the TCP
socket. The BPF program may also enforce a maximum messages size and report an
error when it is exceeded.

A timeout may be set for assembling messages on a receive socket. The timeout
value is taken from the receive timeout of the attached TCP socket (this is set
by SO_RCVTIMEO). If the timer expires before assembly is complete an error
(ETIMEDOUT) is posted on the socket.

multiplexor 생성과 KCM 소켓 복제

새 multiplexor와 첫 KCM 소켓은 `socket(AF_KCM, type, protocol)`로 만듭니다. `type`은 `SOCK_DGRAM` 또는 `SOCK_SEQPACKET`, `protocol`은 `KCMPROTO_CONNECTED`입니다.

같은 multiplexor에 추가 KCM 소켓을 만들려면 기존 KCM 소켓에 `SIOCKCMCLONE` ioctl을 호출합니다. `struct kcm_clone`을 0으로 초기화해 전달하고 호출이 성공하면 `info.fd`에서 새 KCM 소켓 파일 디스크립터를 얻습니다.

User interface
==============

Creating a multiplexor
----------------------

A new multiplexor and initial KCM socket is created by a socket call::

  socket(AF_KCM, type, protocol)

- type is either SOCK_DGRAM or SOCK_SEQPACKET
- protocol is KCMPROTO_CONNECTED

Cloning KCM sockets
-------------------

After the first KCM socket is created using the socket call as described
above, additional sockets for the multiplexor can be created by cloning
a KCM socket. This is accomplished by an ioctl on a KCM socket::

  /* From linux/kcm.h */
  struct kcm_clone {
        int fd;
  };

  struct kcm_clone info;

  memset(&info, 0, sizeof(info));

  err = ioctl(kcmfd, SIOCKCMCLONE, &info);

  if (!err)
    newkcmfd = info.fd;

transport 소켓 연결과 분리

TCP transport 소켓 연결은 multiplexor의 KCM 소켓에 `SIOCKCMATTACH` ioctl을 호출해 수행합니다. `struct kcm_attach`의 `fd`에는 연결할 TCP 소켓 파일 디스크립터를, `bpf_fd`에는 컴파일해 커널에 적재한 BPF 프로그램 파일 디스크립터를 넣습니다.

transport 소켓을 떼려면 `struct kcm_unattach`의 `fd`에 분리할 연결의 파일 디스크립터를 넣고 `SIOCKCMUNATTACH` ioctl을 호출합니다. 연결 오류를 처리할 때에도 먼저 이 절차로 KCM에서 분리한 뒤 소켓을 닫습니다.

Attach transport sockets
------------------------

Attaching of transport sockets to a multiplexor is performed by calling an
ioctl on a KCM socket for the multiplexor. e.g.::

  /* From linux/kcm.h */
  struct kcm_attach {
        int fd;
        int bpf_fd;
  };

  struct kcm_attach info;

  memset(&info, 0, sizeof(info));

  info.fd = tcpfd;
  info.bpf_fd = bpf_prog_fd;

  ioctl(kcmfd, SIOCKCMATTACH, &info);

The kcm_attach structure contains:

  - fd: file descriptor for TCP socket being attached
  - bpf_prog_fd: file descriptor for compiled BPF program downloaded

Unattach transport sockets
--------------------------

Unattaching a transport socket from a multiplexor is straightforward. An
"unattach" ioctl is done with the kcm_unattach structure as the argument::

  /* From linux/kcm.h */
  struct kcm_unattach {
        int fd;
  };

  struct kcm_unattach info;

  memset(&info, 0, sizeof(info));

  info.fd = cfd;

  ioctl(fd, SIOCKCMUNATTACH, &info);

수신 중지와 BPF 프로그램 예제

`SOL_KCM` 레벨의 `KCM_RECV_DISABLE` socket option으로 특정 KCM 소켓의 수신을 끄거나 다시 켤 수 있습니다. 수신을 끄면 그 소켓 receive buffer에 대기하던 메시지는 다른 KCM 소켓으로 이동합니다. 요청 하나를 오래 처리하느라 당분간 새 메시지를 받을 수 없는 worker thread에 유용합니다.

메시지 경계를 찾는 BPF 프로그램은 LLVM BPF backend로 컴파일할 수 있습니다. Thrift 예제는 `socket_kcm` section의 프로그램에서 `skb` 시작 위치의 32비트 길이를 읽고 헤더 4바이트를 더한 값을 반환해 전체 메시지 길이를 KCM에 알려 줍니다. 프로그램 라이선스는 GPL로 선언합니다.

Disabling receive on KCM socket
-------------------------------

A setsockopt is used to disable or enable receiving on a KCM socket.
When receive is disabled, any pending messages in the socket's
receive buffer are moved to other sockets. This feature is useful
if an application thread knows that it will be doing a lot of
work on a request and won't be able to service new messages for a
while. Example use::

  int val = 1;

  setsockopt(kcmfd, SOL_KCM, KCM_RECV_DISABLE, &val, sizeof(val))

BPF programs for message delineation
------------------------------------

BPF programs can be compiled using the BPF LLVM backend. For example,
the BPF program for parsing Thrift is::

  #include "bpf.h" /* for __sk_buff */
  #include "bpf_helpers.h" /* for load_word intrinsic */

  SEC("socket_kcm")
  int bpf_prog1(struct __sk_buff *skb)
  {
       return load_word(skb, 0) + 4;
  }

  char _license[] SEC("license") = "GPL";

응용 구성과 메시지 배치

KCM은 메시지 기반 응용 프로토콜을 가속합니다. 커널이 메시지 단위의 원자적 송수신을 보장하므로 애플리케이션이 TCP stream을 직접 메시지에 대응시키는 부담이 줄어듭니다. 메시지가 커널 안의 steering과 scheduling 작업 단위가 되어 다중 thread 프로그램의 네트워킹 모델도 단순해집니다.

Nx1 구성은 같은 TCP 연결에 여러 KCM 소켓 handle을 제공해 copyin/copyout 같은 I/O 작업을 병렬화합니다. 처리 thread마다 KCM 소켓을 열어 epoll에 넣을 수 있으며, 같은 port의 여러 listener에 `SO_REUSEPORT`를 쓰는 방식과 비슷합니다. MxN 구성은 같은 목적지에 여러 TCP 연결을 만들고 단순 부하 분산에 사용합니다.

메시지마다 소켓이나 연결을 바꾸는 완벽한 분산은 affinity 형성을 막아 오히려 느릴 수 있으므로 메시지 묶음 단위 분산이 유리할 수 있습니다. 송신 배치는 한 번의 `sendmmsg`에 여러 메시지를 넣거나, 마지막을 제외한 `sendmsg`에 `MSG_BATCH`를 지정하거나, 여러 메시지를 합친 super message를 한 번에 보내는 세 방법이 있습니다. 수신에서는 각 TCP ready callback 동안 같은 KCM 소켓에 메시지를 모으고 다음 callback마다 대상 소켓을 바꾸므로 별도 설정이 필요 없습니다.

Use in applications
===================

KCM accelerates application layer protocols. Specifically, it allows
applications to use a message based interface for sending and receiving
messages. The kernel provides necessary assurances that messages are sent
and received atomically. This relieves much of the burden applications have
in mapping a message based protocol onto the TCP stream. KCM also make
application layer messages a unit of work in the kernel for the purposes of
steering and scheduling, which in turn allows a simpler networking model in
multithreaded applications.

Configurations
--------------

In an Nx1 configuration, KCM logically provides multiple socket handles
to the same TCP connection. This allows parallelism between in I/O
operations on the TCP socket (for instance copyin and copyout of data is
parallelized). In an application, a KCM socket can be opened for each
processing thread and inserted into the epoll (similar to how SO_REUSEPORT
is used to allow multiple listener sockets on the same port).

In a MxN configuration, multiple connections are established to the
same destination. These are used for simple load balancing.

Message batching
----------------

The primary purpose of KCM is load balancing between KCM sockets and hence
threads in a nominal use case. Perfect load balancing, that is steering
each received message to a different KCM socket or steering each sent
message to a different TCP socket, can negatively impact performance
since this doesn't allow for affinities to be established. Balancing
based on groups, or batches of messages, can be beneficial for performance.

On transmit, there are three ways an application can batch (pipeline)
messages on a KCM socket.

  1) Send multiple messages in a single sendmmsg.
  2) Send a group of messages each with a sendmsg call, where all messages
     except the last have MSG_BATCH in the flags of sendmsg call.
  3) Create "super message" composed of multiple messages and send this
     with a single sendmsg.

On receive, the KCM module attempts to queue messages received on the
same KCM socket during each TCP ready callback. The targeted KCM socket
changes at each receive ready callback on the KCM socket. The application
does not need to configure this.

오류 처리와 TCP 연결 감시

애플리케이션에는 TCP 연결 오류를 감시하는 thread가 있어야 합니다. 일반적으로 multiplexor에 붙인 모든 TCP 소켓을 `POLLERR` 관심 항목으로 epoll에 등록합니다. 연결 오류가 생기면 KCM이 TCP 소켓에 `EPIPE`를 설정해 감시 thread를 깨웁니다.

오류는 메시지를 받는 도중에도 발생할 수 있으므로 오류가 게시된 TCP stream은 복구할 수 없다고 가정합니다. 애플리케이션은 해당 소켓을 KCM에서 분리한 뒤 닫습니다. KCM 메시지와 실제 송수신에 사용된 TCP 소켓을 직접 대응시키는 방법은 TCP 소켓이 하나뿐인 경우를 제외하면 없습니다. 다만 애플리케이션은 각 TCP 파일 디스크립터를 계속 보유하므로 재전송 횟수 같은 소켓 통계를 읽어 연결 문제를 탐지할 수 있습니다.

Error handling
--------------

An application should include a thread to monitor errors raised on
the TCP connection. Normally, this will be done by placing each
TCP socket attached to a KCM multiplexor in epoll set for POLLERR
event. If an error occurs on an attached TCP socket, KCM sets an EPIPE
on the socket thus waking up the application thread. When the application
sees the error (which may just be a disconnect) it should unattach the
socket from KCM and then close it. It is assumed that once an error is
posted on the TCP socket the data stream is unrecoverable (i.e. an error
may have occurred in the middle of receiving a message).

TCP connection monitoring
-------------------------

In KCM there is no means to correlate a message to the TCP socket that
was used to send or receive the message (except in the case there is
only one attached TCP socket). However, the application does retain
an open file descriptor to the socket so it will be able to get statistics
from the socket which can be used in detecting issues (such as high
retransmissions on the socket).