Computing the Internet Checksum (RFC1071)

시작하기전에

주어진 checksum 영역에 대한 합을 16bits로 산출하는데 overflow 되는 값은 1의 보수로 합하는 구현을 의미합니다.

[https]RFC1071[] 에서 제시하는 checksum 알고리즘은 IP, UDP, TCP protocol 에서 packet의 오류정정 확인을 위한 용도로 사용됩니다. (IP 뿐만 아니라 Transport layer 에서 많은 protocol 이 같은 알고리즘을 사용합니다.)

만약 이 글을 읽고 계시는 분이 IP RAW packet을 다루게 된다면 [https]RFC1071[] 에서 제시하는 비교적 단순한 checksum 을 구현하거나 이해해야 할겁니다.

구현에 있어서 Byte order에 대한 이해와 고려가 필요합니다.

소스

  • RFC1071 에서 C언어로의 구현 예시
    {
               /* Compute Internet Checksum for "count" bytes
                *         beginning at location "addr".
                */
           register long sum = 0;
    
            while( count > 1 )  {
               /*  This is the inner loop */
                   sum += * (unsigned short) addr++;
                   count -= 2;
           }
    
               /*  Add left-over byte, if any */
           if( count > 0 )
                   sum += * (unsigned char *) addr;
    
               /*  Fold 32-bit sum to 16 bits */
           while (sum>>16)
               sum = (sum & 0xffff) + (sum >> 16);
    
           checksum = ~sum;
       }
    


  • 필자가 수정하여 제시하는 예제소스
    unsigned int hwport_rfc1071_checksum(const void *s_data, size_t s_size)
    { /* hwport_internet_checksum (RFC1071) */
        register uint32_t s_result = (uint32_t)0u;
    
        while(s_size > ((size_t)1u)) {
            s_result += (uint32_t)(*((const uint16_t *)s_data));
            s_data = ((const uint16_t *)s_data) + ((size_t)1u);
            s_size -= (size_t)2u;
        }
    
        if(s_size > ((size_t)0u)) {
            s_result += (uint32_t)(*((const uint8_t *)s_data));
        }
    
        /*  Fold 32-bit sum to 16 bits */
        s_result = (s_result >> 16) + (s_result & ((uint32_t)0xffffu));
        s_result += s_result >> 16;
    
        return((unsigned int)((~s_result) & ((uint32_t)0xffffu)));
    }
    


  • 가장 성능 좋은 구현 예제는 Linux kernel 에서 csum_partial() 함수와 csum_fold() 함수입니다.

Checksum (IP, TCP, UDP, ICMP, ...)의 업데이트가 필요한 경우

  • TTL 감소
    • ip_forward 에서 ip_decrease_ttl 함수를 통해서 checksum의 update 구현으로 처리
  • 패킷 난도질(mangling 및 Transform 그리고 NAT 포함)
    • NAT 에 의해서 IP header의 출발지, 목적지 등이 변경될 때 필요
    • XFRM 등의 Transform module(IPSec VPN 등) 에 의해서 변화직전에 반영할 때
  • IP옵션의 수정시
    • 옵션의 변경이 발생하면 재계산 필요
  • 단편화
    • 단편화 되면 서로 다른 Header를 갖고 이에 따른 각각의 체크섬이 재계산 되어야 합니다.

수신된 프레임이 하드웨어에서 계산된 L4 checksum이 무효화 되는 일상적인 경우

  • 입력 L2 프레임이 최소 프레임 크기를 맞추려고 padding을 포함하고, NIC가 checksum을 계산할 때 padding을 뺄 수 있을 만큼 똑똑하지 못한 경우 (=> 이 경우 ip_rcv함수는 항상 checksum을 무효화 하게 됩니다. bridge에서 이와 비슷한 상황)
  • 입력 IP 단편이 이전에 받은 단편과 겹쳐지는 경우
  • 입력 IP 패킷이 IPSec protocol 처리에 관여되는 경우
  • NAT되어 checksum이 재계산 되어야 하거나 IP계층에서 비슷한 개입이 발생하는 경우
  • Linux kernel의 ip_nat_fn 함수를 참고

리눅스 커널(Linux kernel) 에서의 checksum 관점 정리

리눅스의 경우 unsigned long으로 합만 하는 과정인 nofold(또는 partial과 일부 의미 비슷)과 이를 최종 상위 값을 16bit로 합산하는 fold 과정을 나누어 처리함으로써 매번할 필요는 없는 1의 보수 합을 fold로 분리하여 다루게 됩니다. (이를 구현한 대표적인 함수는 ip_fast_csum 이 있으며 그 밖에도 많은 함수가 나뉘어 있음)

  • 대부분의 아키텍쳐에서 어셈블리로 구현된 함수 : "static inline unsigned short ip_fast_csum(unsigned char *iph, unsigned int ihl);"
    • 호출전에 iph의 checksum 을 0으로 초기화 후에 사용해야 합니다.
    • 포워딩이나 수신단계에서는 반환값 0이 반환되어 checksum이 맞다는 것을 확인하도록 사용한다는 점에 흥미로운 사용법이 존재합니다.
  • 결국 매번 fold 하는 작업을 줄임으로써 성능에 이점을 얻으려는 아이디어에서 만들어진 것이 nofold와 fold를 분리한다는 것!
  • skb->ip_summed 는 IP checksum만의 이야기가 아니고 L4 checksum과 관계적임
    • 무언가 checksum 갱신이 될만한 사항은 이 값이 그에 맞는 값으로 상태값을 가져야 합니다.
      • CHECKSUM_NONE 또는 CHECKSUM_COMPLETE
        • 수신 패킷 (인입시 장치로부터 설정되는 skb->ip_summed)
          • skb->csum 값이 유효하지 않음을 의미
            • 장치가 하드웨어 checksum을 지원하지 못하는 경우
            • 충돌이 있는 프레임인 경우 (이 경우 하드웨어는 패킷을 버리지 않고 수신처리부에서 이를 확인하여 검증하고 유무를 판단하는게 의도)
        • 송출 패킷 (TX 시에 skb->ip_summed)
          • checksum을 완료했으므로 장치에서 checksum을 더 할게 없음을 표현
      • CHECKSUM_UNNECESSARY
        • 송출/수신 패킷 (인입시 장치로부터 설정되거나 TX시에 skb->ip_summed)
          • NIC는 L4헤더의 체크섬과 의사헤더의 체크섬(선택적)을 계산하고 검증함. 더이상의 L4 checksum 검증 할 필요 없는 만큼 신뢰되는 패킷임을 의미
          • 오류가능성이 매우 낮은 경우 설정됨
          • 보통은 loopback 인 경우 구간신뢰가 가능하기 때문에 설정됨
      • CHECKSUM_PARTIAL
        • 송출 패킷 (TX 시에 skb->ip_summed)
          • 특정 부분까지 checksum을 수행하였으나 fold되지도 않았고 모든 부분에 대한 checksum이 수행되지 않은 상태 (보통 L4 payload checksum이 미완료인 상태)
          • 송출 직전까지는 checksum이 더 계산되어 완료되어야 하는 상태 !
      • CHECKSUM_HW (장치 드라이버에서 내부적으로 사용)
        • 수신 패킷 (인입시 장치로부터 설정되는 skb->ip_summed)
          • NIC는 L4 헤더와 payload 에 대한 checksum을 수행하였고 skb->csum 필드에 복사하였음을 의미
          • 수신부에서는 이를 의사헤더와 함께 체크하여 검증하기만 하면 됨
        • 송출 패킷 (TX 시에 skb->ip_summed)
          • protocol 의 의사헤더의 checksum을 해당 Header에 저장 후 나머지에 대한 checksum을 장치에서 수행하도록 함
  • 장치가 checksum을 처리할 수 있는지에 따른 통제를 위한 플래그 net_device->features
    • NETIF_F_NO_CSUM
      • 장치가 매우 신뢰되므로 L4 checksum이 필요하지 않은 경우 (보통 lookback 장치들)
    • NETIF_F_IP_CSUM
      • 장치가 하드웨어에서 L4 checksum을 계산 가능하지만 TCP, UDP만 해당
    • NETIF_F_HW_CSUM
      • 장치가 어떠한 protocol 에 대해서도 L4 checksum을 계산 가능
  • 리눅스에서 checksum을 담당하는 기본 주요 함수 요약 (실제로는 더 많이 있음)
    • ip_compute_csum
      • checksum을 수행하는 일반 목적의 함수
    • ip_fast_csum
      • IP Header와 길이(ip header의 ip length 필드 값 그대로)를 입력으로 받아 ip checksum을 계산하여 반환
      • ip_compute_csum의 IP header를 위한 최적화된 변형인 함수
    • ip_send_check
      • 송출되는 IP packet의 checksum을 계산
      • iph->check를 0으로 초기화 하고 ip_fast_csum을 호출하는 wrapper 함수
    • ip_decrease_ttl
      • TTL을 감소시키고 갱신된 변화값만큼만 checksum을 갱신하는 함수 (checksum을 전체 계산하는 것이 아닌 TTL 1감소하는 것에 대한 update만 수행)
      • ip_forward 에서 TTL 감소 및 checksum 갱신하는 목적으로 사용
    • skb_checksum
      • skb에 특화된 일반 함수
    • csum_fold
      • 32bits 값의 최상위 16bits를 하위 16bits에 반영하는 과정(이를 fold한다고 함)을 처리
    • csum_partial_XXX
      • fold하지 않은 checksum 값을 계산 (결국 최종에는 fold 해야 유효한 checksum이 완성된다고 보면 됨)
    • csum_block_add
      • checksum을 증가하는 방향으로 계산 (추가되는 block에 대한 checksum을 계산하여 이전 결과에 합산)
    • csum_block_sub
      • checksum을 빼는 방향으로 계산 (checksum된 결과에서 제거되는 block에 대한 checksum을 계산하여 뺌)
    • skb_checksum_help
      • 인입 패킷에서는 L4 하드웨어 checksum을 검증하기 위해서 사용
      • 인출 패킷에서는 L4 checksum을 계산
        • skb->ip_summed 가 CHECKSUM_PARTIAL 상태인 경우 skb->ip_summed 가 CHECKSUM_NONE이 되도록 checksum 남은 부분을 완료처리하게 됩니다.
    • csum_tcpudp_magic
      • TCP와 UDP의 의사헤더를 가상으로 만들어 checksum을 수행
      • 보통은 csum_partial로 계산된 의사헤더를 제외한 부분의 checksum 결과를 먼저 얻고 이 값과 csum_tcpudp_magic에 의해서 계산된 의사헤더 checksum을 더하는 과정을 하게 됨




/*
[ FrontPage | PrintView | RawView | RSS ]

Copyright ⓒ MINZKN.COM
All Rights Reserved.

MINZKN
*/