From owner-freebsd-hackers Sat Mar 1 08:27:18 1997 Return-Path: Received: (from root@localhost) by freefall.freebsd.org (8.8.5/8.8.5) id IAA15368 for hackers-outgoing; Sat, 1 Mar 1997 08:27:18 -0800 (PST) Received: from root.com (implode.root.com [198.145.90.17]) by freefall.freebsd.org (8.8.5/8.8.5) with ESMTP id IAA15363 for ; Sat, 1 Mar 1997 08:27:15 -0800 (PST) Received: from localhost (localhost [127.0.0.1]) by root.com (8.8.5/8.6.5) with SMTP id IAA05199 for ; Sat, 1 Mar 1997 08:28:29 -0800 (PST) Message-Id: <199703011628.IAA05199@root.com> X-Authentication-Warning: implode.root.com: localhost [127.0.0.1] didn't use HELO protocol To: hackers@freebsd.org Subject: Re: overview of socket hashing changes, plus new patch From: David Greenman Reply-To: dg@root.com Date: Sat, 01 Mar 1997 08:28:29 -0800 Sender: owner-hackers@freebsd.org X-Loop: FreeBSD.org Precedence: bulk ------- Forwarded Message To: "David S. Miller" cc: netdev@roxanne.nuclecu.unam.mx Subject: Re: overview of socket hashing changes, plus new patch In-reply-to: Your message of "Fri, 28 Feb 1997 21:26:57 EST." <199703010226.VAA08431@jenolan.caipgeneral> From: David Greenman Reply-To: dg@root.com - -------- A couple of comments: > FreeBSD - Single hash for entire TCP socket > space. Listening sockets pollute > the established connections. I didn't see a significant amount of overhead due to this when I implemented the PCB hashing in FreeBSD. Almost all of the overhead was in the per-packet linear list searches...so creating a seperate hash list for listening/wildcard PCBs didn't seem worth it at the time. > Hash > function involves a mod instruction > because the table size is a prime. > (Some minutae, I have approximately 50 or so samples from some > of the largest ftp and web servers that I know about (some > of these samples have 5,000 or more connections), listing > the socket connections during high load. A comparison of the > current bound hash function under Linux and the one > under FreeBSD shows them to distribute about the same, if not > better for Linux (in particular Linux is better on machines > which run many clients as well as large single port servers) > the prime size of the hash does not seem to help FreeBSD and > they eat the multi-cycle modulo instrucion on top of it all, > so stupid) My analysis showed that an add or shift+add didn't provide adequate distribution. I actually went to a lot of trouble to write the prime number based hashing code because of this. If you've found a good way to get similarly good distribution, I'm certainly interested. > 2) Timers: > > FreeBSD - Every 500ms, and every 200ms, the > _ENTIRE_ TCP socket list is walked, > yes in it's entirety. How the fuck > does this scale? It doesn't, and it's one of the biggest problems with the code. It is, however, a second order problem (7/second compared to 1000's/second in the first order linear list search per packet case). I plan to re-visit this eventually, but it's not been very high priority. - -DG David Greenman Core-team/Principal Architect, The FreeBSD Project ------- End of Forwarded Message