home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.lbl.gov / 2014.05.ftp.ee.lbl.gov.tar / ftp.ee.lbl.gov / email / vanj.93sep07.txt < prev    next >
Internet Message Format  |  1995-11-10  |  8KB
  1. Received: from rx7.ee.lbl.gov by uu2.psi.com (5.65b/4.0.071791-PSI/PSINet) via SMTP;
  2.     id AA12583 for popbbn; Wed, 8 Sep 93 01:29:46 -0400
  3. Received: by rx7.ee.lbl.gov for craig@aland.bbn.com (5.65/1.44r)
  4.     id AA05271; Tue, 7 Sep 93 22:30:15 -0700
  5. Message-Id: <9309080530.AA05271@rx7.ee.lbl.gov>
  6. To: Craig Partridge <craig@aland.bbn.com>
  7. Cc: David Clark <ddc@lcs.mit.edu>
  8. Subject: Re: query about TCP header on tcp-ip 
  9. In-Reply-To: Your message of Tue, 07 Sep 93 09:48:00 PDT.
  10. Date: Tue, 07 Sep 93 22:30:14 PDT
  11. From: Van Jacobson <van@ee.lbl.gov>
  12.  
  13. Craig,
  14.  
  15. As you probably remember from the "High Speed TCP" CNRI meeting,
  16. my kernel looks nothing at all like any version of BSD.  Mbufs
  17. no longer exist, for example, and `netipl' and all the protocol
  18. processing that used to be done at netipl interrupt level are
  19. gone.  TCP receive packet processing in the new kernel really is
  20. about 30 instructions on a RISC (33 on a sparc but three of
  21. those are compiler braindamage).  Attached is the C code & the
  22. associated sparc assembler.
  23.  
  24. A brief recap of the architecture:  Packets go in 'pbufs' which
  25. are, in general, the property of a particular device.  There is
  26. exactly one, contiguous, packet per pbuf (none of that mbuf
  27. chain stupidity).  On the packet input interrupt, the device
  28. driver upcalls through the protocol stack (no more of that queue
  29. packet on the netipl software interrupt bs).  The upcalls
  30. percolate up the stack until the packet is completely serviced
  31. (e.g., NFS requests that can be satisfied from in-memory data &
  32. data structures) or they reach a routine that knows the rest of
  33. the processing must be done in some process's context in which
  34. case the packet is laid on some appropriate queue and the
  35. process is unblocked.  In the case of TCP, the upcalls almost
  36. always go two levels: IP finds the datagram is for this host &
  37. it upcalls a TCP demuxer which hashes the ports + SYN to find a
  38. PCB, lays the packet on the tail of the PCB's queue and wakes up
  39. any process sleeping on the PCB.  The IP processing is about 25
  40. instructions & the demuxer is about 10.
  41.  
  42. As Dave noted, the two processing paths that need the most
  43. tuning are the data packet send & receive (since at most every
  44. other packet is acked, there will be at least twice as many data
  45. packets as ack packets).  In the new system, the receiving
  46. process calls 'tcp_usrrecv' (the protocol specific part of the
  47. 'recv' syscall) or is already blocked there waiting for new
  48. data.  So the following code is embedded in a loop at the start of
  49. tcp_usrrecv that spins taking packets off the pcb queue until
  50. there's no room for the next packet in the user buffer or the
  51. queue is empty.  The TCP protocol processing is done as we
  52. remove packets from the queue & copy their data to user space
  53. (and since we're in process context, it's possible to do a
  54. checksum-and-copy).
  55.  
  56. Throughout this code, 'tp' points to the pcb and 'ti' points to
  57. the tcp header of the first packet on the queue (the ip header was
  58. stripped as part of interrupt level ip processing).  The header info
  59. (excluding the ports which are implicit in the pcb) are sucked out
  60. of the packet into registers [this is to minimize cache thrashing and
  61. possibly to take advantage of 64 bit or longer loads].  Then the
  62. header checksum is computed (tp->ph_sum is the precomputed pseudo-header
  63. checksum + src & dst ports).
  64.  
  65. int tcp_usrrecv(struct uio* uio, struct socket* so)
  66. {
  67.     struct tcpcb *tp = (struct tcpcb *)so->so_pcb;
  68.     register struct pbuf* pb;
  69.  
  70.     while ((pb = tp->tp_inq) != 0) {
  71.         register int len = pb->len;
  72.         struct tcphdr *ti = (struct tcphdr *)pb->dat;
  73.  
  74.         u_long seq = ((u_long*)ti)[1];
  75.         u_long ack = ((u_long*)ti)[2];
  76.         u_long flg = ((u_long*)ti)[3];
  77.         u_long sum = ((u_long*)ti)[4];
  78.         u_long cksum = tp->ph_sum;
  79.  
  80.         /* NB - ocadd is an inline gcc assembler function */
  81.         cksum = ocadd(ocadd(ocadd(ocadd(cksum, seq), ack), flg), sum);
  82.  
  83. Next is the header prediction check which is probably the most
  84. opaque part of the code.  tp->pred_flags contains snd_wnd (the
  85. window we expect in incoming packets) in the bottom 16 bits and
  86. 0x4x10 in the top 16 bits.  The 'x' is normally 0 but will be
  87. set non-zero if header prediction shouldn't be done (e.g., if
  88. not in established state, if retransmitting, if hole in seq
  89. space, etc.).  So, the first term of the 'if' checks four
  90. different things simultaneously:
  91.  - that the window is what we expect
  92.  - that there are no tcp options
  93.  - that the packet has ACK set & doesn't have SYN, FIN, RST or URG set
  94.  - that the connection is in the right state
  95. and the 2nd term of the if checks that the packet is in sequence:
  96.  
  97. #define FMASK (((0xf000 | TH_SYN|TH_FIN|TH_RST|TH_URG|TH_ACK) << 16) | 0xffff)
  98.  
  99.         if ((flg & FMASK) == tp->pred_flags && seq == tp->rcv_nxt) {
  100.  
  101. The next few lines are pretty obvious -- we subtract the header
  102. length from the total length and if it's less than zero the packet
  103. was malformed, if it's zero we must have a pure ack packet & we
  104. do the ack stuff otherwise if the ack field didn't move we have
  105. a pure data packet which we copy to the user's buffer, checksumming
  106. as we go, then update the pcb state if everything checks:
  107.  
  108.                 len -= 20;
  109.                 if (len <= 0) {
  110.                         if (len < 0) {
  111.                                 /* packet malformed */
  112.                         } else {
  113.                                 /* do pure ack things */
  114.                         }
  115.                 } else if (ack == tp->snd_una) {
  116.                         cksum = in_uiomove((u_char*)ti + 20, len, uio, cksum);
  117.                         if (cksum != 0) {
  118.                                 /* packet or user buffer errors */
  119.                         }
  120.                         seq += len;
  121.                         tp->rcv_nxt = seq;
  122.                         if ((int)(seq - tp->rcv_acked) >= 0) {
  123.                                 /* send ack */
  124.                         } else {
  125.                                 /* free pbuf */
  126.                         }
  127.             continue;
  128.         }
  129.     }
  130.     /* header prediction failed -- take long path */
  131.     ...
  132.  
  133. That's it.  On the normal receive data path we execute 16 lines of
  134. C which turn into 33 instructions on a sparc (it would be 30 if I
  135. could trick gcc into generating double word loads for the header
  136. & my carefully aligned pcb fields).  I think you could get it down
  137. around 25 on a cray or big-endian alpha since the loads, checksum calc
  138. and most of the compares can be done on 64 bit quantities (e.g.,
  139. you can combine the seq & ack tests into one).
  140.  
  141. Attached is the sparc assembler for the above receive path.  Hope
  142. this explains Dave's '30 instruction' assertion.  Feel free to
  143. forward this to tcp-ip or anyone that might be interested.
  144.  
  145.  - Van
  146.  
  147.  ----------------
  148.     ld [%i0+4],%l3            ! load packet tcp header fields
  149.     ld [%i0+8],%l4
  150.     ld [%i0+12],%l2
  151.     ld [%i0+16],%l0
  152.  
  153.     ld [%i1+72],%o0            ! compute header checksum
  154.     addcc %l3,%o0,%o3
  155.     addxcc %l4,%o3,%o3
  156.     addxcc %l2,%o3,%o3
  157.     addxcc %l0,%o3,%o3
  158.  
  159.     sethi %hi(268369920),%o1    ! check if hdr. pred possible
  160.     andn %l2,%o1,%o1
  161.     ld [%i1+60],%o2
  162.     cmp %o1,%o2
  163.     bne L1
  164.     ld [%i1+68],%o0
  165.     cmp %l3,%o0
  166.     bne L1
  167.     addcc %i2,-20,%i2
  168.     bne,a L3
  169.     ld [%i1+36],%o0
  170.       ! packet error or ack processing
  171.       ...
  172. L3:
  173.     cmp %l4,%o0
  174.     bne L1
  175.     add %i0,20,%o0
  176.     mov %i2,%o1
  177.     call _in_uiomove,0
  178.     mov %i3,%o2
  179.     cmp %o0,0
  180.     be L6
  181.     add %l3,%i2,%l3
  182.       ! checksum error or user buffer error
  183.       ...
  184. L6:
  185.     ld [%i1+96],%o0
  186.     subcc %l3,%o0,%g0
  187.     bneg L7
  188.     st %l3,[%i1+68]
  189.       ! send ack
  190.       ...
  191.       br L8
  192. L7:
  193.       ! free pbuf
  194.       ...
  195. L8:    ! done with this packet - continue
  196.     ...
  197.  
  198. L1:    ! hdr pred. failed - do it the hard way
  199.