home *** CD-ROM | disk | FTP | other *** search
/ ftp.ee.lbl.gov / 2014.05.ftp.ee.lbl.gov.tar / ftp.ee.lbl.gov / email / vanj.88jul20.txt < prev    next >
Internet Message Format  |  1995-11-10  |  16KB

  1. From: van@HELIOS.EE.LBL.GOV (Van Jacobson)
  2. Newsgroups: comp.protocols.tcp-ip
  3. Subject: some interim notes on the bsd network speedups
  4. Message-ID: <8807200426.AA01221@helios.ee.lbl.gov>
  5. Date: 20 Jul 88 04:26:17 GMT
  6.  
  7. I told the potential beta-tests for our new 4bsd network code
  8. that I hoped to have a version of the code out by the end of
  9. July.  (BTW, we've got all the beta testers we can handle --
  10. please don't apply.)  It looks like that's going to turn into
  11. the end of August, in part because of SIGCOMM and in part
  12. because Sun puts sending source to academic customers on the
  13. bottom of its priority list.  I thought I'd flame about the
  14. latter and give a bit of a status report on the new code.
  15.  
  16. I've been trying to put together a beta distribution for the
  17. "header prediction" bsd network code.  This effort has been
  18. stymied because it's impossible to get current source from Sun.
  19. The code involves major changes to the 4.3bsd kernel.  The only
  20. local machines I can use to develop new kernels are Suns --
  21. everything else is either multi-user or has pathetic ethernet
  22. hardware.  But the only Sun kernel source I've got is the doubly
  23. obsolete Sun OS 3.5/4.2 BSD.  It would be a massive waste of
  24. time to upgrade this system to 4.3 BSD just so I can develop
  25. the next BSD -- Bill Nowicki did the upgrade a year ago and
  26. binaries of the new system (totally worthless to me) are
  27. shipping as Sun OS 4.0.  [I'm not the only one suffering this
  28. problem -- I understand Craig Partridge's multicast work is
  29. suffering because he can't get 4.3-compatible Sun source.  I
  30. think he gave up & decided to do all his development on 4.3bsd
  31. Vaxen.  And I think I heard Chuck Hedrick say 4.0 has all the
  32. rlogin, URG and nameserver bugs that we fondly remember fixing
  33. in 3.x.  And he has to get source before the academic year
  34. starts or they won't be able to switch until a semester break.
  35. And Mike Karels is saying "I told you so" and suggesting I buy
  36. some CCIs.  Pity that Sun can't figure out that it's in their
  37. best interest to do TIMELY source distribution to the academic
  38. and research community -- their software development base gets
  39. expanded a few hundred-fold for the cost of making tapes.]
  40.  
  41. Anyway, now that I've vented my spleen, there are some interim
  42. results to talk about.  While waiting for either useful source
  43. or a better hardware platform to show up, I've been cleaning up
  44. my original mods and backing out changes one and two at a time
  45. to gauge their individual effect.  Because network performance
  46. seems to rest on getting a lot of things happening in parallel,
  47. this leave-one-out testing doesn't give simple good/bad answers
  48. (I had one test case that went like
  49.  
  50.     Basic system:    600 KB/s
  51.     add feature A:    520 KB/s
  52.     drop A, add B:    530 KB/s
  53.     add both A & B:    700 KB/s
  54.  
  55. Obviously, any statement of the form "feature A/B is good/bad"
  56. is bogus.)  But, in spite of the ambiguity, some of the network
  57. design folklore I've heard seems to be clearly wrong.
  58.  
  59. In the process of cleaning things up, they slowed down.  Task-
  60. to-task data throughput using TCP between two Sun 3/60s dropped
  61. from 1 MB/s (about 8.6 Mb/s on the wire) to 890 KB/s (about 7.6
  62. Mb/s on the wire).  I know where the 11% was lost (an
  63. interaction between "sosend" and the fact that an AMD LANCE chip
  64. requires at least 100 bytes in the first chunk of data if you
  65. ask it to chain -- massive braindamage on AMD's part) and how to
  66. get it back (re-do the way user data gets handed to the
  67. transport protocol) but need to talk with Mike Karels about the
  68. "right" way to do this.
  69.  
  70. Still, 890 KB/s represents a non-trivial improvement over the
  71. stock Sun/4bsd system:  Under identical test conditions (same
  72. socket & user buffer sizes, same MSS and MTU, same machines),
  73. the best tcp throughput I could get with an out-the-box Sun OS
  74. 3.5 was 380 KB/s.  I wish I could say "make these two simple
  75. changes and your throughput will double" but I can't.  There
  76. were lots and lots of fiddley little changes, none made a huge
  77. difference and they all seemed to be necessary.
  78.  
  79. The biggest single effect was a change to sosend (the routine
  80. between the user "write" syscall and tcp_output).  Its loop
  81. looked something like:
  82.  
  83.     while there is user data & space in the socket buffer
  84.     copy from user space to socket
  85.     call the protocol "send" routine
  86.  
  87. After hooking a scope to our ethernet cable & looking at the
  88. packet spacings, I changed this to
  89.  
  90.     while there is user data & space in the socket buffer
  91.     copy up to 1K (one cluster's worth) from user space to socket
  92.     call the protocol "send" routine
  93.  
  94. and the throughput jumped from 380 to 456 KB/s (+20%).  There's
  95. one school of thought that says the first loop was better
  96. because it minimized the "boundary crossings", the fixed costs
  97. of routine calls and context changes.  This same school is
  98. always lobbying for "bigger":  bigger packets, bigger windows,
  99. bigger buffers, for essentially the same reason: the bigger
  100. chunks are, the fewer boundary crossings you pay for.  The
  101. correct school, mine :-), says there's always a fixed cost and a
  102. variable cost (e.g., the cost of maintaining tcp state and
  103. tacking a tcp packet header on the front of some data is
  104. independent of the amount of data; the cost of filling in the
  105. checksum field in that header scales linearly with the amount of
  106. data).  If the size is large enough to make the fixed cost small
  107. compared to the variable cost, making things bigger LOWERS
  108. throughput because you throw away opportunities for parallelism.
  109. Looking at the ethernet, I saw a burst of packets, a long dead
  110. time, another burst of packets, ... .  It was clear that while
  111. we were copying 4 KB from the user, the processor in the LANCE
  112. chip and tcp_input on the destination machine were mostly
  113. sitting idle.
  114.  
  115. To get good network performance, where there are guaranteed to
  116. be many processors that could be doing things in parallel, you
  117. want the "units of work" (loop sizes, packet sizes, etc.) to be
  118. the SMALLEST values that amortise the fixed cost.  In Berkeley
  119. Unix, the fixed costs of protocol processing are pretty low and
  120. sizes of 1 - 2 KB on a 68020 are as large as you'd want to get.
  121. (This is easy to determine.  Just do a throughput vs. size test
  122. and look for the knee in the graph.  Best performance is just to
  123. the right of the knee.)  And, obviously, on a faster machine
  124. you'd probably want to do things in even smaller units (if the
  125. overhead stays the same -- Crays are fast but hardware
  126. strangeness drives the fixed costs way up.  Just remember that
  127. if it takes large packets and large buffers to get good
  128. performance on a fast machine, that's because it's broken, not
  129. because it's fast.)
  130.  
  131. Another big effect (difficult to quantify because several
  132. changes had to be made at once) was to remove lots of
  133. more-or-less hidden data copies from the protocol processing.
  134. It's a truism that you never copy data in network code.  Just
  135. lay the data down in a buffer & pass around pointers to
  136. appropriate places in that buffer.  But there are lots of places
  137. where you need to get from a pointer into the buffer back to a
  138. pointer to the buffer itself (e.g., you've got a pointer to the
  139. packet's IP header, there's a header checksum error, and you
  140. want to free the buffer holding the packet).  The routine "dtom"
  141. converts a data pointer back to a buffer pointer but it only
  142. works for small things that fit in a single mbuf (the basic
  143. storage allocation unit in the bsd network code).  Incoming
  144. packets are never in an mbuf; they're in a "cluster" which the
  145. mbuf points to.  There's no way to go from a pointer into a
  146. cluster to a pointer to the mbuf.  So, anywhere you might need
  147. to do a dtom (anywhere there's a detectable error), there had to
  148. be a call to "m_pullup" to make sure the dtom would work.
  149. (M_pullup works by allocating a fresh mbuf, copying a bunch of
  150. data from the cluster to this mbuf, then chaining the original
  151. cluster behind the new mbuf.)
  152.  
  153. So, we were doing a bunch of copying to expedite error handling.
  154. But errors usually don't happen (if you're worried about
  155. performance, first you make sure there are very, very few
  156. errors), so we were doing a bunch of copying for nothing.  But,
  157. if you're sufficiently insomniac, in about a week you can track
  158. down all the pullup's associated with all the dtom's and change
  159. things to avoid both.  This requires massive recoding of both
  160. the TCP and IP re-assembly code.  But it was worth it:  TCP
  161. throughput climbed from around 600 KB/s to 750 KB/s and IP
  162. forwarding just screamed:  A 3/60 forwarding packets at the 9
  163. Mb/s effective ethernet bandwidth used less than 50% of the CPU.
  164.  
  165. [BTW, in general I didn't find anything wrong with the BSD
  166. mbuf/cluster model.  In fact, I tried some other models (e.g.,
  167. do everything in packet sized chunks) and they were slower.
  168. There are many cases where knowing that you can grab an mbuf and
  169. chain it onto a chunk of data really simplifies the protocol
  170. code (simplicity == speed).  And the level of indirection and
  171. fast, reference counted allocation of clusters can really be a
  172. win on data transfers (a la kudp_fastsend in Sun OS).  The
  173. biggest problem I saw, other than the m_pullup's, was that
  174. clusters are too small:  They need to be at least big enough for
  175. an ethernet packet (2K) and making them page sized (8K on a Sun)
  176. doesn't hurt and would let you do some quick page swap tricks in
  177. the user-system data copies (I didn't do any of these tricks in
  178. the fast TCP.  I did use 2KB clusters to optimize things for the
  179. ethernet drivers).]
  180.  
  181. An interesting result of the m_pullup removals was the death of
  182. another piece of folklore.  I'd always heard that the limiting
  183. CPU was the receiver.  Wrong.  After the pullup changes, the
  184. sender would be maxed out at 100% CPU utilization while the
  185. receiver loafed along at 65-70% utilization (utilizations
  186. measured with a microprocessor analyzer; I don't trust the
  187. system's stats).  In hindsight, this seems reasonable.  At the
  188. receiver, a packet comes in, wanders up to the tcp layer, gets
  189. stuck in the socket buffer and an ack is generated (i.e., the
  190. processing terminates with tcp_input at the socket buffer).  At
  191. the sender, the ack comes in, wanders up to the tcp layer, frees
  192. some space, then the higher level socket process has to be woken
  193. up to fill that space (i.e., the processing terminates with
  194. sosend, at the user socket layer).  The way Unix works, this
  195. forces a boundary crossing between the bottom half (interrupt
  196. service) and top half (process context) of the kernel.  On a
  197. Sun, and most of the other Unix boxes I know of, this is an
  198. expensive crossing.  [Of course, the user process on the
  199. receiver side has to eventually wake up and empty the socket
  200. buffer but it gets to do that asynchronously and the dynamics
  201. tend to arrange themselves so it processes several packets on
  202. each wakeup, minimizing the boundary crossings.]
  203.  
  204. Talking about the bottom half of the kernel reminds me of
  205. another major effect.  There seemed to be a "sound barrier" at
  206. 550 KB/s.  No matter what I did, the performance stuck at 550
  207. KB/s.  Finally, I noticed that Sun's LANCE ethernet driver,
  208. if_le.c, would only queue one packet to the LANCE at a time.
  209. Picture what this means:  (1) driver hands packet to LANCE, (2)
  210. LANCE puts packet on wire, (3) end of packet, LANCE interrupts
  211. processor, (4) interrupt dispatched to driver, (5) go back to
  212. (1).  The time involved in (4) is non-trivial, more than 150us,
  213. and represents a lot of idle time for the LANCE and the wire.
  214. So, I rewrote the driver to queue an arbitrary number of packets
  215. to the LANCE, the sound barrier disappeared, and other changes
  216. started making the throughput climb (it's not clear whether this
  217. change had any effect on throughput or just allowed other
  218. changes to have an effect).
  219.  
  220. [Shortly after making the if_le change, I learned why Sun might
  221. have written the driver the silly way they did:  Before the
  222. change, the 6 back-to-back IP fragments of an NFS write would
  223. each be separated by the 150us interrupt service time.  After
  224. the change, they were really back-to-back, separated by only the
  225. 9.6us minimum ethernet spacing (and, no, Sun does NOT violate
  226. the ethernet spec in any way, shape or form.  After my last
  227. message on this stuff, Apollo & DEC people kept telling me Sun
  228. was out of spec.  I've been watching packets on our ethernet for
  229. so long, I'm starting to learn the middle name of every bit.
  230. Sun bits look like DEC bits and Sun, or rather, the LANCE in the
  231. 3/50 & 3/60, completely complys with the timings in the blue
  232. book.)  Anyway, the brain-dead Intel 82586 ethernet chip Sun
  233. puts in all its 3/180, 3/280 and Sun-4 file servers can't hack
  234. back-to-back, minimum spacing packets.  Every now and again it
  235. drops some of the frags and wanders off to never-never land
  236. ("iebark reset").  Diskless workstations don't work well when
  237. they can't write to their file server and, until I hit on the
  238. idea of inserting "DELAY" macros in kudp_fastsend, it looked
  239. like I could have a fast TCP or a functional workstation but not
  240. both.]
  241.  
  242. Probably 30% of the performance improvements came from fixing
  243. things in the Sun kernel.  I mean like, really, guys:  If the
  244. current task doesn't change, and it doesn't 80% of the time
  245. swtch is called, there's no need to do a full context save and
  246. restore.  Adding the two lines
  247.  
  248.     cmpl    _masterprocp,a0
  249.     jeq     6f              ⁿ restore of current proc is easy
  250.  
  251. just before the call to "resume" in sun3/vax.s:swtch got me a
  252. quick 70 KB/s performance increase but felt more like a bug fix
  253. than progress.  And a kernel hacker that does 16-bit "movw"s and
  254. "addw"s on a 68020, or writes 2 instruction dbra loops designed
  255. to put a 68010 in loop mode, should be shot.  The alu takes the
  256. same 3 clocks for a 2 byte add or a 4 byte add so things will
  257. finish a lot quicker if you give it 4 bytes at a time.  And
  258. every branch stalls the pipe, so unrolling that loop to cut down
  259. on branches is a BIG win.
  260.  
  261. Anyway, I recoded the checksum routine, ocsum.s (now oc_cksum.s
  262. because I found the old calling sequence wasn't the best way to
  263. do things) and its caller, in_cksum.c, and got the checksumming
  264. time down from 490us/KB to 130us/KB.  Unrolling the move loop in
  265. copyin/copyout (the routines that move data user to kernel and
  266. kernel to user), got them down from 200us/KB to 140us/KB.  (BTW,
  267. if you combine the move with the checksum, which I did in the
  268. kludged up, fast code that ran 1 MB/s on a 15MHz 3/50, it costs
  269. 200us/KB, not the 300us/KB you'd expect from adding the move
  270. and sum times.  Pipelined processors are strange and wonderful
  271. beasts.)
  272.  
  273. From these times, you can work out most of the budgets and
  274. processing details:  I was using 1408 data byte packets (don't
  275. ask why 1408).  It takes 193us to copy a packet's worth of data
  276. and 184us to checksum the packet and its 40 byte header.  From
  277. the logic analyzer, the LANCE uses 300us of bus and memory
  278. bandwidth reading or writing the packet (I don't understand why,
  279. it should only take half this).   So, the variable costs are
  280. around 700us per packet.  When you add the 18 byte ethernet
  281. header and 12 byte interpacket gap, to run at 10 Mb/s I'd have
  282. to supply a new packet every 1200us.  I.e., there's a budget of
  283. 500us for all the fixed costs (protocol processing, interrupt
  284. dispatch, device setup, etc.).  This is do-able (I've done it,
  285. but not very cleanly) but what I'm getting today is a packet
  286. every 1500us.  I.e., 800us per packet fixed costs.  When I look
  287. with our analyzer, 30% of this is TCP, IP, ARP and ethernet
  288. protocol processing (this was 45% before the "header prediction"
  289. tcp mods), 15% is stalls (idle time that I don't currently
  290. understand but should be able to eventually get rid of) and 55%
  291. is device setup, interrupt service and task handling.  I.e.,
  292. protocol processing is negligible (240us per packet on this
  293. processor and this isn't a fast processor in today's terms).  To
  294. make the network go faster, it seems we just need to fix the
  295. operating system parts we've always needed to fix:  I/O service,
  296. interrupts, task switching and scheduling.  Gee, what a surprise.
  297.  
  298.  - Van
  299.  
  300.  
  301.