{"id":1956,"date":"2016-01-30T00:31:03","date_gmt":"2016-01-30T08:31:03","guid":{"rendered":"https:\/\/www.privateinternetaccess.com\/blog\/?p=1956"},"modified":"2021-10-26T01:33:58","modified_gmt":"2021-10-26T08:33:58","slug":"linux-networking-stack-from-the-ground-up-part-4","status":"publish","type":"post","link":"https:\/\/www.privateinternetaccess.com\/blog\/linux-networking-stack-from-the-ground-up-part-4\/","title":{"rendered":"Linux networking stack from the ground up, part 4"},"content":{"rendered":"\n

part 1<\/a> | part 2<\/a> | part 3<\/a> | part 4<\/a> | part 5<\/a><\/p>\n\n\n\n

Overview<\/h2>\n\n\n\n

This post will pick up where part 3 left off beginning by describing Receive Packet Steering (RPS), what it is and how to configure it, followed by an examination of the network stack describing how packets are dealt with based on RPS settings, the packet backlog queue, the start of the IP protocol layer, and netfilter.<\/p>\n\n\n\n

Receive Packet Steering<\/h2>\n\n\n\n

We saw that device drivers register NAPI poll instances. Each NAPI poller instance is executed in the context of a kernel thread called a softirq of which there are one per CPU. The kernel thread for the CPU that the hardware interrupt handler runs on is woken up \/ scheduled to run in the hardware interrupt handler.<\/p>\n\n\n\n

Thus, a single CPU processes the hardware interrupt and polls from the networking layer to process the incoming data.<\/p>\n\n\n\n

Some NICs support multiple queues at the hardware level. This means that incoming packets can be DMA\u2019d to separate receive rings, each receive ring having its own hardware interrupt being delivered to indicate data is available. Each of these hardware interrupts would schedule NAPI poll instances to run on each of the associated CPUs.<\/p>\n\n\n\n

This allows multiple CPUs to process hardware interrupts and poll from the networking layer.<\/p>\n\n\n\n

Receive Packet Steering (RPS) is a software implementation of hardware enable multi-queue NICs. It allows multiple CPUs to process incoming packets even if the NIC only supports a single receive queue in hardware.<\/p>\n\n\n\n

RPS works by generating a hash for an incoming data to determine which CPU should process the data. The data is then enqueued to the per-CPU receive network backlog to be processed. An Inter-processor interrupt is delivered to the CPU owning the backlog. This helps to kick-start backlog processing by the remote CPU if it is not currently processing packets.<\/p>\n\n\n\n

netif_receive_skb<\/code> will either continue sending network data up the networking stack, or hand it over to RPS for processing on a different CPU.<\/p>\n\n\n\n

configure RPS<\/h3>\n\n\n\n

For RPS to work, it must be enabled in the kernel configuration (it is on Ubuntu for Linux kernel 3.13.0), and a bit mask describing which CPUs should process packets for a given interface and rx queue.<\/p>\n\n\n\n

The bit masks to modify are found in \/sys\/class\/net\/DEVICE_NAME\/queues\/QUEUE\/rps_cpus<\/code>.<\/p>\n\n\n\n

So, for eth0, and receive queue 0, you would modify: \/sys\/class\/net\/eth0\/queues\/rx-0\/rps_cpus<\/code> with a hexadecimal number indicating which CPUs should process packets from eth0\u2019s receive queue 0.<\/p>\n\n\n\n

Back to netif_receive_skb<\/code>.<\/p>\n\n\n\n

netif_receive_skb<\/code><\/h2>\n\n\n\n

As a reminder, netif_receive_skb<\/code> function is called from napi_skb_finish<\/code> in the softirq context from the NAPI poller registered by the device driver.<\/p>\n\n\n\n

netif_receive_skb<\/code> will either attempt to use RPS (as described above) or continue sending the data up the network stack.<\/p>\n\n\n\n

Let\u2019s first examine the second path: sending the data up the stack if RPS is disabled.<\/p>\n\n\n\n

netif_receive_skb<\/code> without RPS<\/h2>\n\n\n\n

netif_receive_skb<\/code> calls __netif_receive_skb<\/code> which does some bookkeeping prior to calling __netif_receive_skb_core<\/code> to move the data along up the network stack toward the protocol levels.<\/p>\n\n\n\n

__netif_receive_skb_core<\/code><\/h2>\n\n\n\n

This function passes the skb up to the protocol layer in this piece of code (net\/core\/dev.c:3628<\/a>):<\/p>\n\n\n\n

type = skb->protocol;                                                             \nlist_for_each_entry_rcu(ptype, &ptype_base[ntohs(type) & PTYPE_HASH_MASK], list) {               \n  if (ptype->type == type &&                                                \n     (ptype->dev == null_or_dev || ptype->dev == skb->dev || ptype->dev == orig_dev)) {                                           \n    if (pt_prev)\n      ret = deliver_skb(skb, pt_prev, orig_dev);\n    pt_prev = ptype;\n  }                                                                         \n}<\/pre>\n\n\n\n
We will examine precisely how this code delivers data to the protocol layer below, but first, let\u2019s see what happens when RPS is enabled.<\/p>\n\n\n\n
netif_receive_skb<\/code> with RPS<\/h2>\n\n\n\n
If RPS is enabled, netif_receive_skb<\/code> will compute which CPU\u2019s backlog it should queue the data. It does this by using the function get_rps_cpu<\/code> (defined at net\/core\/dev.c:2980<\/a>):<\/p>\n\n\n\n
int cpu = get_rps_cpu(skb->dev, skb, &rflow);                             \n\nif (cpu >= 0) {\n  ret = enqueue_to_backlog(skb, cpu, &rflow->last_qtail);           \n  rcu_read_unlock();                                                \n  return ret;                                                       \n}<\/pre>\n\n\n\n
enqueue_to_backlog<\/code><\/h2>\n\n\n\n
This function begins by getting a pointer to the remote CPU\u2019s softnet_data<\/code> structure which contains a pointer to a NAPI poller.<\/p>\n\n\n\n
Next, the queue length of the input_pkt_queue<\/code> of the remote CPU is checked:<\/p>\n\n\n\n
qlen = skb_queue_len(&sd->input_pkt_queue);\nif (qlen <= netdev_max_backlog && !skb_flow_limit(skb, qlen)) { if (skb_queue_len(&sd->input_pkt_queue)) {<\/pre>\n\n\n\n
It is first compared to the netdev_max_backlog<\/code>. If the queue length is larger than the backlog, the data is dropped and the drop is counted against the remote CPU.<\/p>\n\n\n\n
You can prevent drops by increasing the netdev_max_backlog<\/code>:<\/p>\n\n\n\n
sysctl -w net.core.netdev_max_backlog=3000<\/pre>\n\n\n\n
If the queue length isn\u2019t too large, the code next checks if the flow limit has been reached. By default, flow limits are disabled. In order to enable flow limits, you must specify a bitmap (similar to RPS\u2019 bitmap) in \/proc\/sys\/net\/core\/flow_limit_cpu_bitmap<\/code>.<\/p>\n\n\n\n
Once you enable flow limits per CPU, you can also adjust the size of the flow limit hash table by modifying the sysctl net.core.flow_limit_table_len<\/code>.<\/p>\n\n\n\n
You can read more about flow limits in the Documentation\/networking\/scaling.txt<\/a> file.<\/p>\n\n\n\n
Assuming that the flow limit has not been reached, enqueue_to_backlog<\/code> then checks if the backlog queue has data queued to it already.<\/p>\n\n\n\n
If so, the data is queued:<\/p>\n\n\n\n
if (skb_queue_len(&sd->input_pkt_queue)) {\nenqueue:\n  __skb_queue_tail(&sd->input_pkt_queue, skb);\n  input_queue_tail_incr_save(sd, qtail);\n  rps_unlock(sd);\n  local_irq_restore(flags);\n  return NET_RX_SUCCESS;\n}<\/pre>\n\n\n\n
If the queue is empty, first the NAPI poller for the backlog queue is started:<\/p>\n\n\n\n
\/* Schedule NAPI for backlog device                                       \n * We can use non atomic operation since we own the queue lock            \n *\/                                                                       \nif (!__test_and_set_bit(NAPI_STATE_SCHED, &sd->backlog.state)) {          \n  if (!rps_ipi_queued(sd))                                          \n    ____napi_schedule(sd, &sd->backlog);                      \n}                                                                         \ngoto enqueue;<\/pre>\n\n\n\n
The goto<\/code> at the bottom brings execution back up to the block of code above, queuing the data to the backlog.<\/p>\n\n\n\n
backlog queue NAPI poller<\/h2>\n\n\n\n
The per-CPU backlog queue plugs into NAPI the same way a device driver does. A poll function is provided that is used to process packets from the softirq context.<\/p>\n\n\n\n
This NAPI struct is provided during initialization of the networking system. From net_dev_init<\/code> in net\/core\/dev.c:6952<\/a>:<\/p>\n\n\n\n
sd->backlog.poll = process_backlog;\nsd->backlog.weight = weight_p;\nsd->backlog.gro_list = NULL;\nsd->backlog.gro_count = 0;<\/pre>\n\n\n\n
The backlog NAPI structure differs from the device driver NAPI structure in that the weight<\/code> parameter is adjustable. The drivers hardcode their values (most hardcode to 64, as seen in e1000e).<\/p>\n\n\n\n
To adjust the backlog\u2019s NAPI poller weight, modify \/proc\/sys\/net\/core\/dev_weight.<\/p>\n\n\n\n
The poll function for the backlog is called process_backlog<\/code> and, similar to e1000e\u2019s function e1000e_poll<\/code>, is called from the softirq context.<\/p>\n\n\n\n
process_backlog<\/code><\/h2>\n\n\n\n
The process_backlog<\/code> function (net\/core\/dev.c:4097<\/a>) is a loop which runs until its weight (specified in `\/proc\/sys\/net\/core\/dev_weight`) has been consumed or no more data remains on the backlog.<\/p>\n\n\n\n
Each piece of data on the backlog queue is removed from the backlog queue and passed on to __netif_receive_skb<\/code>. As explained earlier in the no RPS case, data passed to this function eventually reaches the protocol layers after some bookkeeping.<\/p>\n\n\n\n
Similarly to device driver NAPI implementations, the process_backlog<\/code> code disables its poller if the total weight will not be used. The poller is restarted with the call to ____napi_schedule<\/code> from enqueue_to_backlog<\/code> as described above.<\/p>\n\n\n\n
The function returns the amount of work done, which net_rx_action<\/code> (described above) will subtract from the budget (which is adjusted with the net.core.netdev_budget<\/code>, as described above).<\/p>\n\n\n\n
__netif_receive_skb_core<\/code> delivers data to protocol layers<\/h2>\n\n\n\n
The __netif_receive_skb_core<\/code> delivers data to protocol layers. It does this by obtaining the protocol field from the skb<\/code> and iterating across a list of deliver<\/code> functions registered for that protocol type.<\/p>\n\n\n\n
This happens in this piece of code (as seen above):<\/p>\n\n\n\n
type = skb->protocol;                                                             \nlist_for_each_entry_rcu(ptype, &ptype_base[ntohs(type) & PTYPE_HASH_MASK], list) {               \n  if (ptype->type == type &&\n       (ptype->dev == null_or_dev || ptype->dev == skb->dev || \n        ptype->dev == orig_dev)) {\n    if (pt_prev)\n      ret = deliver_skb(skb, pt_prev, orig_dev);\n    pt_prev = ptype;\n  }                                                                         \n}<\/pre>\n\n\n\n
The ptype_base<\/code> identifier is defined at net\/core\/dev.c:146<\/a>as a hash table of lists:<\/p>\n\n\n\n
struct list_head ptype_base[PTYPE_HASH_SIZE] __read_mostly;<\/pre>\n\n\n\n
Each protocol layer adds a struct packet_type<\/code> to a list at a given slot in the hash table.<\/p>\n\n\n\n
The slot in the hash table is computed by ptype_head<\/code>:<\/p>\n\n\n\n
static inline struct list_head *ptype_head(const struct packet_type *pt)\n{\n  if (pt->type == htons(ETH_P_ALL))\n    return &ptype_all;\n  else\n    return &ptype_base[ntohs(pt->type) & PTYPE_HASH_MASK];\n}<\/pre>\n\n\n\n
The protocol layers call dev_add_pack<\/code> to add themselves to the list.<\/p>\n\n\n\n
IP protocol layer<\/h2>\n\n\n\n
The IP protocol layer plugs itself into the ptype_base<\/code> hash table so that data will be delivered to it from the lower layers.<\/p>\n\n\n\n
This happens in the function inet_init<\/code> from net\/ipv4\/af_inet.c:1815<\/a><\/p>\n\n\n\n
dev_add_pack(&ip_packet_type);<\/pre>\n\n\n\n
This registers the IP packet type structure defined as:<\/p>\n\n\n\n
static struct packet_type ip_packet_type __read_mostly = {                                \n  .type = cpu_to_be16(ETH_P_IP),                                                    \n  .func = ip_rcv,\n};<\/pre>\n\n\n\n
__netif_receive_skb_core<\/code> calls deliver_skb<\/code> (as seen in the above section). This function (net\/core\/dev.c:1712<\/a>):<\/p>\n\n\n\n
static inline int deliver_skb(struct sk_buff *skb,                                        \n                              struct packet_type *pt_prev,                                \n                              struct net_device *orig_dev)                                \n{                                                                                         \n  if (unlikely(skb_orphan_frags(skb, GFP_ATOMIC)))\n    return -ENOMEM;\n  atomic_inc(&skb->users);\n  return pt_prev->func(skb, skb->dev, pt_prev, orig_dev);                           \n}<\/pre>\n\n\n\n
In the case of the IP protocol, the ip_rcv<\/code> function is called.<\/p>\n\n\n\n
ip_rcv<\/code><\/h2>\n\n\n\n
The ip_rcv<\/code> function is pretty straight-forward at a high level. There are several integrity checks to ensure the data is valid. Statistics counters that are bumped, as well.<\/p>\n\n\n\n
ip_rcv<\/code> ends by passing the packet to ip_rcv_finish<\/code> by way of netfilter. This is done so that any iptables rules that should be matched at the ip protocol layer can take a look at the packet before it continues on (net\/ipv4\/ip_input.c:453<\/a>):<\/p>\n\n\n\n
return NF_HOOK(NFPROTO_IPV4, NF_INET_PRE_ROUTING, skb, dev, NULL, ip_rcv_finish);<\/pre>\n\n\n\n
netfilter<\/h2>\n\n\n\n
The NF_HOOK_THRESH<\/code> function is simple enough. It calls down to nf_hook_thresh<\/code> and on success, calls okfn<\/code> which in our case is ip_rcv_finish<\/code> (include\/linux\/netfilter.h:175<\/a>):<\/p>\n\n\n\n
static inline int\nNF_HOOK_THRESH(uint8_t pf, unsigned int hook, struct sk_buff *skb,                        \n               struct net_device *in, struct net_device *out,                             \n               int (*okfn)(struct sk_buff *), int thresh)                                 \n{       \n        int ret = nf_hook_thresh(pf, hook, skb, in, out, okfn, thresh);                   \n        if (ret == 1) \n                ret = okfn(skb);                                                          \n        return ret;                                                                       \n}<\/pre>\n\n\n\n
The nf_hook_thresh<\/code> function continues down approaching iptables. It begins by determining if there are any netfilter hooks for the netfilter protocol family and netfilter chain passed in.<\/p>\n\n\n\n
In our example above, the protocol family is NFPROTO_IPV4<\/code> and chain type is NF_INET_PRE_ROUTING<\/code>:<\/p>\n\n\n\n
\/**\n *      nf_hook_thresh - call a netfilter hook\n *      \n *      Returns 1 if the hook has allowed the packet to pass.  The function\n *      okfn must be invoked by the caller in this case.  Any other return\n *      value indicates the packet has been consumed by the hook.\n *\/\nstatic inline int nf_hook_thresh(u_int8_t pf, unsigned int hook,\n                                 struct sk_buff *skb,\n                                 struct net_device *indev,\n                                 struct net_device *outdev,\n                                 int (*okfn)(struct sk_buff *), int thresh)\n{\n  if (nf_hooks_active(pf, hook))\n    return nf_hook_slow(pf, hook, skb, indev, outdev, okfn, thresh);\n  return 1;\n}<\/pre>\n\n\n\n
This function calls the nf_hooks_active<\/code> function which examines a table called nf_hooks_needed<\/code> (include\/linux\/netfilter.h:114<\/a>):<\/p>\n\n\n\n
static inline bool nf_hooks_active(u_int8_t pf, unsigned int hook)         \n{                                                                          \n  return !list_empty(&nf_hooks[pf][hook]);                           \n}<\/pre>\n\n\n\n
And if there is a hook present, nf_hook_slow<\/code> is called to go deeper into iptables.<\/p>\n\n\n\n
nf_hook_slow<\/code><\/h2>\n\n\n\n
nf_hook_slow<\/code> iterates through the list of hooks in the nf_hooks<\/code> table for the protocol type and chain type by calling nf_iterate<\/code> for each entry in the hook list.<\/p>\n\n\n\n
nf_iterate<\/code> in turn calls the hook function associated with an entry on the hook list and returns a \u201cverdict\u201d about the packet.<\/p>\n\n\n\n
iptables<\/code> \u2026 tables<\/h2>\n\n\n\n
iptables<\/code> registers hook functions for each of the packet matching tables: filter, nat, mangle, raw, and security.<\/p>\n\n\n\n
In our example, we\u2019re interested in NF_INET_PRE_ROUTING<\/code> chains which are found in the nat<\/code> table.<\/p>\n\n\n\n
Sure enough, the struct with the hook function pointer which is registered with netfilter is found in net\/ipv4\/netfilter\/iptable_nat.c:251<\/a>:<\/p>\n\n\n\n
static struct nf_hook_ops nf_nat_ipv4_ops[] __read_mostly = {\n  \/* Before packet filtering, change destination *\/\n  {\n    .hook           = nf_nat_ipv4_in,\n    .owner          = THIS_MODULE,\n    .pf             = NFPROTO_IPV4,\n    .hooknum        = NF_INET_PRE_ROUTING,\n    .priority       = NF_IP_PRI_NAT_DST,\n  },<\/pre>\n\n\n\n
which is registered in iptable_nat_init<\/code> (net\/ipv4\/netfilter\/iptable_nat.c:316<\/a>):<\/p>\n\n\n\n
err = nf_register_hooks(nf_nat_ipv4_ops, ARRAY_SIZE(nf_nat_ipv4_ops));\nif (err < 0)\n  goto err2;<\/pre>\n\n\n\n
In our example above from the IP protocol layer, packets will be passed down to the nf_nat_ipv4_in<\/code> to descend further into iptables via the nf_hook_slow<\/code> function described in the previous section.<\/p>\n\n\n\n
nf_nat_ipv4_in<\/code><\/h2>\n\n\n\n
nf_nat_ipv4_in<\/code> passes the packet on to nf_nat_ipv4_fn<\/code> which starts by obtaining the conntrack information for the packet:<\/p>\n\n\n\n
struct nf_conn *ct;\nenum ip_conntrack_info ctinfo;\n\n\/* slightly abbreviated code sample *\/\n\nct = nf_ct_get(skb, &ctinfo);<\/pre>\n\n\n\n
If the packet being examined is a packet for a new connection, the function nf_nat_rule_find<\/code> is called (net\/ipv4\/netfilter\/iptable_nat.c:117<\/a>):<\/p>\n\n\n\n
case IP_CT_NEW:\n  \/* Seen it before?  This can happen for loopback, retrans,\n   * or local packets.\n   *\/\n  if (!nf_nat_initialized(ct, maniptype)) {\n    unsigned int ret;\n\n    ret = nf_nat_rule_find(skb, ops->hooknum, in, out, ct);\n    if (ret != NF_ACCEPT)\n      return ret;<\/pre>\n\n\n\n
And, finally, nf_nat_rule_find<\/code> calls ipt_do_table<\/code> which enters the iptables subsystem. This is as far as we will go into the netfilter and iptables systems, as they are complex enough to warrant their own multi-page documents.<\/p>\n\n\n\n
The return value from the ipt_do_table<\/code> function will either:<\/p>\n\n\n\n