Review Of The IP Checksum Function

published: 2022-12-14 [nandalism home] (dark light)

Internet Checksum

There is a field in the network on-the-wire struct icmphdr called uint16_t checksum. It must be filled with a checksum for the packet to be considered valid. The checksum algorithm is, of course, specified in RFC 1071 (which I first read after writing this...). I had a look at the implementations for various ping utilities on Linux/BSD, and make the following observations:

They all use misaligned 16-bit reads (this is bad)
Most have an endianness dependency which is not required, a portable version can be written without referring to endianness.

Misaligned Reads

When reading any word larger than a byte from memory the read may have to be aligned i.e. the address may have to be a multiple of 2 for 16-bit word, multiple of 4 for 32-bit word etc. (the same applies for writes). If the read is not on an aligned address it will fail on some architectures, and have performance penalties on others. In general misaligned access is illegal, and we are not writing code for a single platform.

The solution is to use memcpy() to read a byte stream into a memory word. The memcpy will be optimized away by the compiler in the case where a misaligned read would be allowed and cheaper.

Endianness

The perceived problem comes about when we have a number of bytes in the stream not a multiple of the word size (2 for u16). So there is a case when we have 1 byte left over. Where to put it, the reasoning goes, the top byte or the bottom byte, of the u16. The (erroneous) conclusion: it depends on the endianness.

Note: This is not about the endianness of the byte stream being checksum'd. It doesn't have one as far as inet_cksum() is concerned. This is evident in that half the code doesn't care about endianness and the other half does.

If we think about this another way. We didn't care about endianness in the loop. What would we have liked? It would be nice if there were one more zero byte after the last byte. Then we would have a multiple of the word size (u16) and no problem. Can we engineer this situation post-hoc? Copy the entire block and add a zero? No need, we have processed the entire block already we only need to make a byte buf[2] and put the last byte in the first slot and a zero in the second. Now we do a (proper memcpy) read from that buffer as if it had been part of the stream all along. Ate Viola problem solved, no endianness flag required. We have code that is portable across architectures.

My Version

Downloaded source from my simple ping.c.

There is one more problem which all have. They all under type-specify the sum accumulator (sometimes int, sometimes the better unsigned). The algorithm implicitly assumes an unsigned 32-bit accumulator (we see this from the comments and code in the originals).

I have made this explicit with uint32_t sum = 0.

The OpenBSD version allows the sum to be initialized with an incoming u16 checksum value instead of zero, which allows chaining of checksums. I had written mine before looking at the OpenBSD version.

static uint16_t
inet_cksum(void const* ptr, unsigned sz){
  uint8_t const* p = ptr;
  uint32_t sum = 0;
  uint16_t u16;
  for(;sz>=2; sz-=2,p+=2){
    memcpy(&u16, p, sizeof(u16));
    sum += u16;
  }
  if(1==sz){
    memcpy(&u16, (uint8_t[]){*p, 0}, sizeof(u16));
    sum += u16;
  }
  sum = (sum >> 16) + (sum & 0xffff);
  sum += (sum >> 16);
  return (uint16_t)~sum;
}

In fact the OpenBSD version, does not contain an endianness check and they have made a clever observation which I missed. Writing the extra byte into the first byte of a (pre-zeroed) u16 is equivalent to copying the a 2 byte array [extra,0] onto the u16. I vacillate between which I like best. Their code is more idiomatic, my memcpy is more uniform with the code in the loop. At any rate, they get points for avoiding the endianness dependency and are the only version of the 3 to do so.

memcpy(&u16, (uint8_t[]){*p, 0}, sizeof(u16));
=>
u16=0;
*(uint8_t*)&u16 = *p;

The BusyBox Version

Downloaded sources from busybox.net.

uint16_t FAST_FUNC
inet_cksum(const void *ptr, int nleft)
{
  const uint16_t *addr = ptr;

  /*
   * Our algorithm is simple, using a 32 bit accumulator,
   * we add sequential 16 bit words to it, and at the end, fold
   * back all the carry bits from the top 16 bits into the lower
   * 16 bits.
   */
  unsigned sum = 0;
  while (nleft > 1) {
    sum += *addr++;
    nleft -= 2;
  }

  /* Mop up an odd byte, if necessary */
  if (nleft == 1) {
    if (BB_LITTLE_ENDIAN)
      sum += *(uint8_t*)addr;
    else
      sum += *(uint8_t*)addr << 8;
  }

  /* Add back carry outs from top 16 bits to low 16 bits */
  sum = (sum >> 16) + (sum & 0xffff);     /* add hi 16 to low 16 */
  sum += (sum >> 16);                     /* add carry */

  return (uint16_t)~sum;
}

The Linux iputils Version

Downloaded sources from github.com.

#if BYTE_ORDER == LITTLE_ENDIAN
# define ODDBYTE(v) (v)
#elif BYTE_ORDER == BIG_ENDIAN
# define ODDBYTE(v) ((unsigned short)(v) << 8)
#else
# define ODDBYTE(v) htons((unsigned short)(v) << 8)
#endif

static unsigned short
in_cksum(const unsigned short *addr, int len, unsigned short csum)
{
  int nleft = len;
  const unsigned short *w = addr;
  unsigned short answer;
  int sum = csum;

  /*
   *  Our algorithm is simple, using a 32 bit accumulator (sum),
   *  we add sequential 16 bit words to it, and at the end, fold
   *  back all the carry bits from the top 16 bits into the lower
   *  16 bits.
   */
  while (nleft > 1) {
    sum += *w++;
    nleft -= 2;
  }

  /* mop up an odd byte, if necessary */
  if (nleft == 1)
    sum += ODDBYTE(*(unsigned char *)w); /* le16toh() may be unavailable on old systems */

  /*
   * add back carry outs from top 16 bits to low 16 bits
   */
  sum = (sum >> 16) + (sum & 0xffff); /* add hi 16 to low 16 */
  sum += (sum >> 16);     /* add carry */
  answer = ~sum;        /* truncate to 16 bits */
  return (answer);
}

The OpenBSD ping Version

Downloaded sources from openbsd ping.c.

int
in_cksum(u_short *addr, int len)
{
        int nleft = len;
        u_short *w = addr;
        int sum = 0;
        u_short answer = 0;

        /*
         * Our algorithm is simple, using a 32 bit accumulator (sum), we add
         * sequential 16 bit words to it, and at the end, fold back all the
         * carry bits from the top 16 bits into the lower 16 bits.
         */
        while (nleft > 1) {
                sum += *w++;
                nleft -= 2;
        }

        /* mop up an odd byte, if necessary */
        if (nleft == 1) {
                *(u_char *)(&answer) = *(u_char *)w ;
                sum += answer;
        }

        /* add back carry outs from top 16 bits to low 16 bits */
        sum = (sum >> 16) + (sum & 0xffff);     /* add hi 16 to low 16 */
        sum += (sum >> 16);                     /* add carry */
        answer = ~sum;                          /* truncate to 16 bits */
        return(answer);
}