title	tags
Ft_Ping ReadMe	C Networking Unix

This project has been created as part of the 42 curriculum by pjarnac.

---

Ft_Ping

Project Description

This project aims to introduce us to raw networking with the implementation of a ping command with the ICMP protocol, part of the IP protocol. I've decided to try to handle all the ping flags from inetutils.

Dev Environment

For all my projects i use DevContainers, they usually work with docker to create OS agnostic, isolated, and reproducible environments. For ease of use i use DevPod to manage my devcontainers, for this project i use a Debian machine with the clang compiler with the C standard GNU23.

What is ICMP protocol

We all know some of the IP protocol, IP addresses like 192.168.0.1 are specified and come from the IP RFC. IP is at layer 3 of the OSI model, the networking layer. It also includes some protocols at the same level encapsulated in IP packets, like ICMP (Internet Control Message Protocol). It's a protocol used in an IP packet data section, used to "debugging" ip, it have some utilities to gather information, send error messages about ip communications, and indications about success of an operation.

What interest us the most in the ICMP Protocol is the echo requests and echo responses, when we send an echo request to a router, it should respond us with an echo responses. This is what we use to know if an ip is joignable. An ICMP packet is formed like this:

Type: 8 bits
Code: 8 bits
Checksum: 16 bits
Content: 32 bits
Data: 0-576 bytes (more dicussion about the size later)

Type is used to specify the ICMP message type, like echo request, echo response, etc... Code is in case the Type have a subset of messages, we do not use it in our case so likely 0. Content is Type specific and contains additional information. Checksum is used to verify the integrity of a message and is computed by making the sum of all the 2 bytes words of the icmp_pack starting with Type and returning the 1's complement of the sum.

Raw Sockets

Since we do not work Transport Layer protocol, like UDP and TCP that work on top of IP, we work directly with IP at the Network Layer, so we need to build the packet manually and use Raw Sockets, since Stream Socket are used with TCP and Datagram Socket with UDP.

Implementation Choices

Parsing

For the program entry and CLI parsing i use the gnu argp library, it's in my opinion the best library to parse with ease and have a result like every programs, it provides help pages, arguments, and options with or without values.

You provides different s options using a list of struct argp_option:

{
// option name, used for long option, ex: --count
.name = "count",
// option used to identify it, if it's a printable can be also used as: -c
.key = 'c',
// if the option should receive a value, set the name of the value in help messages
.arg = "NUMBER",
// option flags, never find uses of one
.flags = 0,
// for documentation purpose on help messages
.doc = "stop after sending NUMBER packets"
}

Polling

While we are pinging we are only using one socket, but we need to have polling to handle packet drops and when the ping interval is shorter than the RTT. We need to be able to continue the program and not block on the recv_from when a packet is dropped. So we need to know when the socket have received a packet and is able to be read. I have chosen to use epoll instead of poll and select, both are old and not optimized io multiplexing solutions and in my opinion harder to use and less scalable.

Optimizations and cool things

Packet structure

When we work with manually build packet we can use protocol headers that gives us C structures for protocols packets, for icmp we should use <netinet/ip_icmp.h> :

struct icmphdr
{
  uint8_t type;		/* message type */
  uint8_t code;		/* type sub-code */
  uint16_t checksum;
  union
  {
    struct
    {
      uint16_t	id;
      uint16_t	sequence;
    } echo;			/* echo datagram */
    uint32_t	gateway;	/* gateway address */
    struct
    {
      uint16_t	__glibc_reserved;
      uint16_t	mtu;
    } frag;			/* path mtu discovery */
  } un;
};

This scary structure actually contains the packet definition i gave upper. Just that for content we have an union that will adapt to our message type, for exemple for echo requests and responses we use the 2 bytes of content to track the ping id and sequence.

On top of this i have built my own structure for ease of use with sockets, when we work with sockets we need to send raw array data, but when we also need to work with the icmp structure we have to cast. When we send a echo request we have give to send to: icmp_header + data. But when we receive, we have: ip_header + icmp_header + data. So again another structure, to simplify things i use an unions to handle all case in one type, inspired by the icmp structure:c

typedef union
{
	struct
	{
		struct ip	   ip_hdr;
		struct icmphdr hdr;
		uint8_t		   data[];
	} res;
	struct
	{
		struct icmphdr hdr;
		uint8_t		   data[];
	};
	uint8_t raw[0];
} icmp_packet;

This structure use a flexible array member at the end so all the supplement size given to malloc will go on raw, and we can interpret the response with the ip packet at the beginning.

Checksum Computing Optimization

Parallel Summation

Based on the Checksum Calculation RFC i've implemented a parallel summation optimization, instead of summing 2 bytes values i use the CPU word size, for exemple on 64bit machines i sum 8 bytes values, reducing the number of sum to make by 4, and it's also faster because we use the CPU optimal size. Since sum are associatives we do not have to add them in order and can add them as 4 2bytes values at a time, we will just need to re arrange them on a 2 byte value at the end. This optimization has been able to shorten the computation time by 7, for 1000 bytes: 500ns vs 3500ns.

Incremental Update

Since in our ping program the data section and the ICMP header except on field are constant, it's a HUGE waste of time to compute the whole checksum each packet, instead we can compute the only field that change, the sequence_id field and add the difference of the old value with the new value to the checksum. Hence only computing 2 octect each packet instead of all the packet.

Loop Unwind

Loop unwind is a popular choice to optimize loops, it's also valable for the checksum calculation, in my opinion it's not a worth optimization for a lot of reason:

• Code Readability: Unwinding loop duplicate lines of code, making the code hard to understand for someone that want to contribute to the code without knowing it's an unwinding.

• Locality Reference: One of the most costly operations on computers is fetching from the RAM, to reduce this CPU have extremely fast caches, to be concise, it's better to have the code most use code next to each other in memory so they can be transferred to the CPU cache, by unwinding loops we make the code lines farther from each other in the memory. Although on older CPU with small caches it may be worth.

• Compiler Is Better Than Us: Compiler will do the unwinding if necessary for us, no need to make the code unreadable, it's the job of the compiler.