A Map of the Networking Code in Linux Kernel 2.4.20

 

 A Map of the Networking Code in Linux Kernel 2.4.20
 Miguel Rio
 
  Начиная с версии 2.4.2 был впервые применен механизм NAPI - 
  New Application Programming Interface.
 В этой статье будут также описаны sub-IP layer(Ethernet protocol),IP layer, 
 а также протоколы TCP и UDP.
 Толчком к написанию этой статьи послужили эксперименты в гигабитной сети , 
 в которых были обнаружены некоторые потери отдельных пакетов .
 В ядре 2.4.2 реализован вариант ТСР , известный под названием NewReno, 
 основанный на RFC 2581 [2], RFCs 2018 [8] , 2883 [9]. 
  Следующий рисунок в графической форме показывает сетевой код ядра .
 Он располагается в net/ipv4 , net/core , net/sched. 
 Хидеры лежат в include/linux и include/net.
 

 
  Следующий рисунок показывает , как входящий пакет проходит через ядро .

  Можно выделить 4 области с различным кодом для входящих пакетов - 
     железо
     драйвер
     kernel protocol stack 
     kernel/application interface
  
  В ядре можно выделить 2 основных структуры - одна контролирует коннект 
  и называется "sock", вторая контролирует входящие-выходящие пакеты 
  и называется "sk_buff". Следует также отметить
 другую структуру - tcp_opt, которая входит в "sock".
 sk_buff описана в include/linux/skbuff.h. 
 Изменение поля в пакете осуществляется путем изменения
 полей именно этой структуры . 
 Это происходит путем вызова функций , параметром которой является
 структура sk_buff.
 	struct sk_buff {
 		/* These two members must be first. */
 		struct sk_buff *next; /* Next buffer in list */
 		struct sk_buff *prev; /* Previous buffer in list*/
 		struct sk_buff_head *list; /* List we are on */
 		struct sock *sk; /* Socket we are owned by */
 		struct timeval stamp; /* Time we arrived */
 		struct net_device *dev; /* Device we arrived on/are leaving by */
 Первые 2 указателя этой структуры указывают на соседние структуры в очереди .
 Указатель sk указывает на сокет , в котором хранится пакет . 
 Транспортная секция представлена юнионами :
 	union
 	{
 	struct tcphdr *th;
 	struct udphdr *uh;
 	struct icmphdr *icmph;
 	struct igmphdr *igmph;
 	struct iphdr *ipiph;
 	struct spxhdr *spxh;
 	unsigned char *raw;
 	} h;
 	
 	union
 	{
 	struct iphdr *iph;
 	struct ipv6hdr *ipv6h;
 	struct arphdr *arph;
 	struct ipxhdr *ipxh;
 	unsigned char *raw;
 	} nh;
 
 	union
 	{
 	struct ethhdr *ethernet;
 	unsigned char *raw;
 	} mac;
 	struct dst_entry *dst;
 
 
 Такая информация о пакете , как длина , контрольная сумма , 
 тип пакета и т.д. хранится в структуре :
 	char cb[48];
 	unsigned int len; /* Length of actual data */
 	unsigned int data_len;
 	unsigned int csum; /* Checksum */
 	unsigned char __unused, /* Dead field, may be reused */
 	                cloned, /* head may be cloned (check refcnt to be sure) */
                         pkt_type, /* Packet class */
        	                ip_summed; /* Driver fed us an IP checksum */
                       __u32 priority; /* Packet queueing priority */
 	atomic_t users; /* User count - see datagram.c,tcp.c */
 	unsigned short protocol; /* Packet protocol from driver */
 	unsigned short security; /* Security level of packet */
 	unsigned int truesize; /* Buffer size */
 	unsigned char *head; /* Head of buffer */
 	unsigned char *data; /* Data head pointer */
 	unsigned char *tail; /* Tail pointer */
 	unsigned char *end; /* End pointer */
 
  Структура sock создается каждый раз при создании сокета .
 	struct sock {
 	/* Socket demultiplex comparisons on incoming packets. */
 		__u32 daddr; /* Foreign IPv4 address */
 		__u32 rcv_saddr; /* Bound local IPv4 address */
 		__u16 dport; /* Destination port */
 		unsigned short num; /* Local port */
 		int bound_dev_if; /* Bound device index if != 0 */
 Информация,специфичная для протокола:
 	union {
 		struct ipv6_pinfo af_inet6;
 	} net_pinfo;
 
 	union {
 		struct tcp_opt af_tcp;
 		struct raw_opt tp_raw4;
 		struct raw6_opt tp_raw;
 		struct spx_opt af_spx;
 	} tp_pinfo;
 В отличие от более простых протоколов ip и udp , 
 протокол tcp включает дополнительные поля ,
 которые хранятся в структуре tcp_opt
 	struct tcp_opt {
 int tcp_header_len; /* Bytes of tcp header to send */
 __u32 rcv_nxt; /* What we want to receive next */
 __u32 snd_nxt; /* Next sequence we send */
 __u32 snd_una; /* First byte we want an ack for */
 __u32 snd_sml; /* Last byte of the most recently transmitted* small packet */
 __u32 rcv_tstamp; /* timestamp of last received ACK (for keepalives) */
 __u32 lsndtime; /* timestamp of last sent data packet* (for restart window) */
 /* Delayed ACK control data */
 struct {
         __u8 pending; /* ACK is pending */
         __u8 quick; /* Scheduled number of quick acks */
         __u8 pingpong; /* The session is interactive */
         __u8 blocked; /* Delayed ACK was blocked by socket lock */
         __u32 ato; /* Predicted tick of soft clock */
         unsigned long timeout; /* Currently scheduled timeout */
         __u32 lrcvtime; /* timestamp of last received data packet */
         __u16 last_seg_size; /* Size of last incoming segment */
         __u16 rcv_mss; /* MSS used for delayed ACK decisions */
 		} ack;
 		/* Data for direct copy to user */
 		struct {
 			struct sk_buff_head prequeue;
 			struct task_struct *task;
 			struct iovec *iov;
 			int memory;
 			int len;
 		} ucopy;
         __u32 snd_wl1; /* Sequence for window update */
         __u32 snd_wnd; /* The window we expect to receive */
         __u32 max_window; /* Maximal window ever seen from peer */
         __u32 pmtu_cookie; /* Last pmtu seen by socket */
         __u16 mss_cache; /* Cached effective mss, not including SACKS */
         __u16 mss_clamp; /* Maximal mss, negotiated at connection setup */
         __u16 ext_header_len; /* Network protocol overhead (IP/IPv6 options) */
         __u8 ca_state; /* State of fast-retransmit machine */
         __u8 retransmits; /* Number of unrecovered RTO timeouts */
         __u8 reordering; /* Packet reordering metric */
         __u8 queue_shrunk; /* Write queue has been shrunk recently */
         __u8 defer_accept; /* User waits for some data after accept() */
         /* RTT measurement */
         __u8 backoff; /* backoff */
         __u32 srtt; /* smothed round trip time << 3 */
         __u32 mdev; /* medium deviation */
         __u32 mdev_max; /* maximal mdev for the last rtt period */
         __u32 rttvar; /* smoothed mdev_max */
         __u32 rtt_seq; /* sequence number to update rttvar */
         __u32 rto; /* retransmit timeout */
         __u32 packets_out; /* Packets which are "in flight" */
         __u32 left_out; /* Packets which leaved network */
         __u32 retrans_out; /* Retransmitted packets out */
         __u32 snd_ssthresh; /* Slow start size threshold */
         __u32 snd_cwnd; /* Sending congestion window */
         __u16 snd_cwnd_cnt; /* Linear increase counter */
         __u16 snd_cwnd_clamp; /* Do not allow snd_cwnd to grow above this */
         __u32 snd_cwnd_used;
         __u32 snd_cwnd_stamp;
         /* Two commonly used timers in both sender and receiver paths. */
         unsigned long timeout;
         struct timer_list retransmit_timer; /* Resend (no ack) */
         struct timer_list delack_timer; /* Ack delay */
         struct sk_buff_head out_of_order_queue; /* Out of order segments */
         struct tcp_func *af_specific; 
         struct sk_buff *send_head; /* Front of stuff to transmit */
         struct page *sndmsg_page; /* Cached page for sendmsg */
         u32 sndmsg_off; /* Cached offset for sendmsg */
         __u32 rcv_wnd; /* Current receiver window */
         __u32 rcv_wup; /* rcv_nxt on last window update sent */
         __u32 write_seq; /* Tail(+1) of data held in tcp send buffer */
         __u32 pushed_seq; /* Last pushed seq, required to talk to windows */
         __u32 copied_seq; /* Head of yet unread data */
         /* Options received (usually on last packet, some only on SYN packets) */
         char tstamp_ok, /* TIMESTAMP seen on SYN packet */
         wscale_ok, /* Wscale seen on SYN packet */
         sack_ok; /* SACK seen on SYN packet */
         char saw_tstamp; /* Saw TIMESTAMP on last packet */
         __u8 snd_wscale; /* Window scaling received from sender */
         __u8 rcv_wscale; /* Window scaling to send to receiver */
         __u8 nonagle; /* Disable Nagle algorithm? */
         __u8 keepalive_probes; /* num of allowed keep alive probes */
         /* PAWS/RTTM data */
         __u32 rcv_tsval; /* Time stamp value */
         __u32 rcv_tsecr; /* Time stamp echo reply */
         __u32 ts_recent; /* Time stamp to echo next */
         long ts_recent_stamp; /* Time we stored ts_recent (for aging) */
         /* SACKs data */
         __u16 user_mss; /* mss requested by user in ioctl */
         __u8 dsack; /* D-SACK is scheduled */
         __u8 eff_sacks; /* Size of SACK array to send with next packet */
         struct tcp_sack_block duplicate_sack[1]; /* D-SACK block */
         struct tcp_sack_block selective_acks[4]; /* The SACKs themselves */
         __u32 window_clamp; /* Maximal window to advertise */
         __u32 rcv_ssthresh; /* Current window clamp */
         __u8 probes_out; /* unanswered 0 window probes */
         __u8 num_sacks; /* Number of SACK blocks */
         __u16 advmss; /* Advertised MSS */
         __u8 syn_retries; /* num of allowed syn retries */
         __u8 ecn_flags; /* ECN status bits. */
         __u16 prior_ssthresh; /* ssthresh saved at recovery start */
         __u32 lost_out; /* Lost packets */
         __u32 sacked_out; /* SACK'd packets */
         __u32 fackets_out; /* FACK'd packets */
         __u32 high_seq; /* snd_nxt at onset of congestion */
         __u32 retrans_stamp; 
         /* Timestamp of the last retransmit,	
          also used in SYN-SENT to remember * stamp of the first SYN */
         __u32 undo_marker; /* tracking retrans started here */
         int undo_retrans; /* number of undoable retransmissions */
         __u32 urg_seq; /* Seq of received urgent pointer */
         __u16 urg_data; /* Saved octet of OOB data and control flags */
         __u8 pending; /* Scheduled timer event */
         __u8 urg_mode; /* In urgent mode */
         __u32 snd_up; /* Urgent pointer */
 };       
 Сетевая пакетная модель включает в себя 7 уровней .
 Рассмотрим первые два , относящиеся к железу и NIC-драйверу , 
 на примере входящих пакетов .
 Пакетный дескриптор создается в net/core/skbuff.c , в функции alloc_skb().
 Закрывается он в случае получения ACK функцией kfree_skb()
 Некоторые пакеты создаются с помощью skb_clone() (transmitter side).
  Основные файлы , отвечающие за прием пакетов :
 	 include/linux/netdevice.h
 	 net/core/skbuff.c
 	 net/core/dev.c
 	 net/dev/core.c
 	 arch/i386/irq.c
 	 drivers/net/net_init.c
 	 net/sched/sch_generic.c
 NIC драйвер использует DMA-доступ к памяти .
 На следующем рисунке показано прохождение входящего пакета .
 

  Когда пакет попадает в NIC , ему выделяется kernel-память через DMA, 
  и он становится в очередь пакетов . 
 Максимальный размер пакета определяется параметром ядра , 
 который называется maxMTU.
 Сначала в interrupt handler создает пакетный дескриптор - sk_buff. 
 После чего указатель на нее помещается в очередь rx_ring . 
 Затем вызывается системное прерывание и вызывается Interrupt Service Routine (ISR).
 Затем interrupt handler вызывает netif_rx_schedule() , 
 и указатель на пакет помещается в очередь , которая называется poll_list.
 Затем шедулятором в основном цикле do_softirq() будет вызван softirq , 
 и receive interruptions будут задисэйблены .
 Когда срабатывает softirq, он вызывает net_rx_action() в следующем порядке :
 	HI_SOFTIRQ,
 	NET_TX_SOFTIRQ, 
         NET_RX_SOFTIRQ 
 	TASKLET_SOFTIRQ.
 Преимущество этой схемы в том , что ограничивается т.н. interruption rate , 
 нет необходимости в кэшировании пакетов . В старых API , 
 если очередь переполнялась , пакет просто удалялся ,
 в NAPI же переполнение пулла исключено , 
 причем это возможно на аппаратном уровне .
 
 
 Packet Transmission
  IP-пакеты строятся с помощью arp_constructor(). В каждом пакете есть поле dst.
 

  При передаче IP пакетов происходит следующее : 
   1. вызывается dev_queue_xmit() , при этом пакет ставится в очередь , 
      которая называется qdisc. после чего управление передается в  qdisc_restart()
   2. вызывается hard_start_xmit() , который входит в код драйвера . 
      Дескриптор пакета помещается в  tx_ring , и драйвер говорит NIC-у , 
      что есть пакет , который можно послать.
   3. NIC говорит CPU , что пакет был отослан , после чего CPU ложит 
      отправленный пакет в очередь , которая называется completion_queue , 
      и в дальнейшем будет вызван шедулятор , освобождающий
      память от лишней структуры skbuff.
 С помощью команды ifconfig можно изменить длину  output packet queue , 
 используя параметр txqueuelen , или с помощью команды tc :
 	qdisc add dev eth0 root pfifo limit 100
 Получить статистику по qdisc:
 	tc -s -d qdisc show dev eth0
 Последние модели NIC позволяют генерировать прерывание для каждого 
 входящего и выходящего пакета .
 Прерывание может быть сгенерировано по определенному тайм-ауту .
 Это возможно благодаря механизму , который называется interrupt coalescence. 
 Он уменьшает время , отводимое процессором на обработку прерываний .
 
 
Network layer
  Этот слой из 7-уровневой сетевой модели гарантирует т.н. to-end connectivity 
  в интернете .
 В его основе лежит протокол IP . 
 Линукс может выступать в качестве роутера , здесь мы имеем дело
 с т.н. packet forwarding. Основной код :
 	 ip_input.c - processing of the packets arriving at the host
 	 ip_output.c - processing of the packets leaving the host
 	 ip_forward.c - processing of the packets being routed by the host
 	 ip_fragment.c - IP packet fragmentation
 	 ip_options.c - IP options
 	 ipmr.c - IP multicast
 	 ipip.c - IP over IP
 Следующий рисунок показывает путь IP-пакета.
 

  Пакет,приходящий из сети,показан слева,пакет уходящий показан 
 справа на рисунке.
 Порядок функций при поступлении пакета :
 	net_rx_action()
 	ip_rcv() 
 	netfilter
 	ip_rcv_finish()
         ip_local_delivery() - если пакет для данного хоста
 На выходе :
 	ip_finish_output()
 	dev_queue_transmit()
         qdisc_run()
         * Если хост сконфигурирован как роутер , переменная ip_forward должна 
         быть отличной от нуля .
         ip_route_input() - вычисление dst
 ip_rcv_finished() - вставляет вычисленный пункт назначения dst в структуру sk_buff.
 	ip_forward() - отправка
 
  ARP (Address Resolution Protocol) определен в RFC 826 и конвертирует адрес .
 Когда возникает необходиость в посылке пакета в локальную сеть , 
 нужно сконвертировать IP-адрес в 
 MAC-адрес и результат сохранить в структуре skb . 
 Если пункт назначения находится за пределами 
 локальной сети , то пакет посылается на роутер , 
 где уже принимается решение о дальнейшем пути .
 
 Internet Control Message Protocol (ICMP) играет важную роль в интернете .
 При получении icmp-пакета , порядок вызова функций :
 	net_rx_action()
 	to icmp_rcv()
 	icmp_send().
 
 
TCP
  ТСР-протокол обладает несколькими особенностями , 
  в том числе он реализует надежный канал передачи данных
 за счет перепосылки неполученных пакетов .
  Основные файлы :
 	 tcp_input.c  
 	 tcp_output.c 
 	 tcp.c       - General TCP code. 
 	 tcp_ipv4.c  - IPv4 TCP specific code.
 	 tcp_timer.c - Timer management.
 	 tcp.h       - Definition of TCP constants.
 Следующий рисунок показывает путь входящих tcp-пакетов
 

 Следующий рисунок показывает путь выходящих tcp-пакетов