What is a packet checksum?Gigabit Ethernet frame-formatSome lowest-level detailsThe FCS fieldThe CRCERRS registerAnother (simpler) checksumSlide 7The idea of ‘complements’Set TheoryArithmeticTwo’s complementOne’s complementNine’s complements‘end-around-carry’NIC uses ‘one’s complement’Intel’s cpu uses ‘little endian’Checksum using CIn-class demonstration #1Checksum ‘offloading’Using ‘nicecho.c’Slide 21The ‘Legacy’ Transmit-DescriptorSlide 23Further driver modifications…Slide 25What is a packet checksum?Here we investigate the NIC’s capabilities for computing and detecting errors using checksumsGigabit Ethernet frame-formatPreambleDestination AddressStart-Of-Frame DelimiterSource AddressType/LenthDataFrame Check SequenceCarrier ExtensionFrame is extended to occupy a slot-time of 512 bytesSome lowest-level details•The frame’s Preamble consists of 7 bytes of an alternating bit-pattern of 1’s and 0’s•The Start-of-Frame Delimiter is a one-byte bit-pattern which continues the alternation of 1’s and 0’s until the final bit is reached (which ‘breaks’ the pattern-of-alternation)10101010 10101010 10101010 10101010 10101010 10101010 10101010 10101011In hexadecimal notation: 0xAA 0xAA 0xAA 0xAA 0xAA 0xAA 0xAA 0xABThe 64-bit Preamble and SFDThe Start-of-Frame DelimiterThe FCS field•The Frame Check Sequence is a four-byte integer, usually computed by the hardware according to a sophisticated mathematical error-detection scheme known as Cyclic-Redundancy Check (CRC):The CRC is calculated by performing a modulo 2 division of the data by a generator polynomial and recording the remainder after division CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1The CRCERRS register•Our Intel Pro1000 ethernet controller has a statistical counter register (the first one, at offset 0x4000 in the memory-mapped I/O- space) which counts any received frames which arrived with a CRC-error indicated •Our ‘nic2.c’ was programmed to ‘strip’ the 4-byte FCS field from all received frames, by setting the SECRC-bit in register RCTLAnother (simpler) checksumBase-address (64-bits)statusPacket-lengthPacket-checksumVLANtagerrors16 bytesThe device-driver initializes this ‘base-address’ field with the physical address of a packet-buffer The network controller will ‘write-back’ the values for these fields when it has transferred a received packet’s data into the packet-bufferThe Pro1000’s ‘legacy-format’ Receive-DescriptorWhat is this ‘packet checksum’?•According to the Intel documentation, the packet checksum is “the unadjusted 16-bit ones complement of the packet” (page 24)•Now what exactly does that mean?•And why did Intel’s hardware designers believe that device-driver software would need this value to be available for every ethernet packet that the NIC receives?The idea of ‘complements’•Whenever a whole object gets divided into two parts, those pieces often referred to as complements•Example: complementary angles in a right-triangle ABC ABC + BAC = 90°Set Theory BAVenn Diagram Within the ‘universe’ represented here by the box, the orange set B is the complement of the green set A.Arithmetic•Among the digits in our ‘base ten’ system:–the values 1 and 9 are complements–the values 2 and 8 are complements–the values 3 and 7 are complements–the values 4 and 6 are complements•Complements are useful when performing subtractions in modular arithmetic: 4 - 6 (mod 10) = 4 + 4 (mod 10)Two’s complement•Digital computers use modular arithmetic in the ‘base two’ number system •Two 8-bit numbers are ‘complements’ if their sum equals 28 (= 256):00000001 is the twos-complement of 1111111100000010 is the twos-complement of 1111111000000011 is the twos-complement of 11111101•As a consequence, subtractions can be done with the same circuits as additionsOne’s complement•But for some purposes there is a different kind of ‘complement’ that results in better arithmetical properties – it’s known as the ‘diminished radix’ complement•For the case of radix ten, it’s called ‘nine’s complement’, and for the case of radix two it’s called ‘one’s complement’Nine’s complements•A pair of 3-digit numbers x and y in the radix ten number system would be called nine’s complements if x+y = 103-1 = 999–Thus 321 and 678 are nines-complements •A pair of 3-digit numbers x and y in the radix two number system would be called one’s complements if x+y = 23-1 = 111–Thus 110 and 001 are ones-complements‘end-around-carry’•When you want to add two binary numbers using the one’s complement system, you can do it by first performing ordinary binary addition, and then adding in the carry-bit: 10101010 (8-bit number) + 11110000 (8-bit number) --------------------- 1 10011010 (9-bits in the normal total) + 1 (apply ‘end-around carry’) ---------------------10011011 (8-bits in the ones-complement total)NIC uses ‘one’s complement’•For network programming nowadays it is common practice for ‘one’s complement’ to be used when computing checksums•It is also common practice for multi-byte integers to be ‘sent out over the wire’ in so called ‘big-endian’ byte-order (i.e., the most significant byte goes out ahead of the bytes having lesser significance)Intel’s cpu uses ‘little endian’•Whenever our x86 processor ‘stores’ a multi-byte value into a series of cells in memory, it puts the least significant byte first (i.e., at the earliest memory address), followed by the remaining bytes having greater significance)0x3456AX = 0x56buf:0x34 mov %ax, bufChecksum using C{unsigned char *cp = phys_to_virt( rxring[ rxhead ].base_address );unsigned int nbytes = rxring[ rxhead ].packet_length;unsigned int nwords = ( nbytes / 2 );unsigned short *wp = (unsigned short*)cp;unsigned int i, checksum = 0;if ( nbytes & 1 ) { cp[ nbytes ] = 0; ++nwords; } // pad odd length packetfor ( i = 0; i < nwords; i++ ) checksum += wp[ i ]; // two’s complement sumchecksum += (checksum >> 16); // do ‘end-around carries’checksum = htons( checksum ) // -- adjustment #1: swap the byteschecksum = ~checksum; // -- adjustment #2: and flip the bitschecksum &= 0xFFFF; // mask to lowest 16-bits// Let’s compare our checksum-calculation with the
View Full Document
Unlocking...