Re: linux 2.6.16 routing problem
Mayuresh, On Fri, 14 Jul 2006, Mayuresh Chitale wrote: > > If anyone has solved similar problem or knows what causes this > problem, please let me know. > > Any suggestion is welcome. Configure a static arp entry for the tester on the unit under test. (Or configure the tester to respond to ARP queries.) --brian - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Daniel, On Wed, 14 Jun 2006, Daniel Phillips wrote: > > Speaking as a former member of a "grey market" binary module vendor that > came in from the cold I can assure you that the distinction between EXPORT > and EXPORT_GPL _is_ meaningful. That tainted flag makes it extremely > difficult to do deals with mainstream Linux companies and there is always > the fear that it will turn into a legal problem. The latter bit tends to > make venture capitalists nervous. > EXPORT_SYMBOL_GPL and the Tainted flag have nothing to do with each other. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Alan, On Wed, 14 Jun 2006, Alan Cox wrote: > It isn't "policy" its called copyright law. I know that I said I'd shut up, but I missed in TRIPS where it said that symbols must be EXPORT_SYMBOL_GPL... Could you point that out? (Just kidding.) > You don't seem to understand copyright law either. The GPL like all > copyright licenses deals with the right to make copies and to create and > control derivative works. It's not "defeated" by four lines of code. The 3 or 4 lines of code that I wrote as an original expression before the patch was submitted. > Is that a confession ;) No, just a declaration: the code in question was released under GPL Version 2. > Copyright is not about novelty, you have it confused with the > theoretical (not actual) role of patents. Wrong kind of intellectual > monopoly right. Yes, perhaps I should have said "original" instead of "novel". The patch is not "original" as it was predated by equivalent (machine translatable) original expressions. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Chase, On Wed, 14 Jun 2006, Chase Venters wrote: > > One point I remember coming up in the discussion was that the > EXPORT_SYMBOL()/EXPORT_SYMBOL_GPL() split was a compromise of sorts. > Interfaces that were needed to support users would reasonably be placed under > EXPORT_SYMBOL(). By contrast, EXPORT_SYMBOL_GPL() would indicate > functionality that would only seem to be used by derived works. It implies > that any code using it should probably be GPL as well. The difficulty with EXPORT_SYMBOL_GPL() as I see it that it reached farther than the GPL. GPL does not impact non-derived works, which can be licensed under any terms their authors see fit. Whereas, EXPORT_SYMBOL_GPL() requires a non-derived work to declare a GPL license to even use it. If you subscribe to the FSF view of derived work (just linking is a derivation) then I suppose you would support the EXPORT_SYMBOL_GPL(). IANAL, but I don't believe that TRIPS nor Berne Convention case law supports the FSF view. Linus' statements in the COPYING file take a different view: that simple use of a technical interface is not necessarily (in itself) derivation. Now, I understand the use of EXPORT_SYMBOL() vs. EXPORT_SYMBOL_GPL() to allow authors to differ on this idea. But, in the case in point, the function pointers can be accessed by merely including the appropriate header files. Changing a the wrapper access to them to EXPORT_SYMBOL_GPL() strikes me as similar to changing kmalloc() from EXPORT_SYMBOL() to EXPORT_SYMBOL_GPL(). Understand that all exported symbols, regardless of licensing or modversions or whatever, are available in the kernel boot image and can be linked to by any module at any time. That is, those that would abuse the concept of derivation will not be impeded by EXPORT_SYMBOL_GPL(). (Rip the symbol from the kernel image, write a thin GPL'ed module that aliases the symbol and the exports it again as EXPORT_SYMBOL() without module versioning, copy the lines of code into the proprietary module, reversing the order of arbitrary lines, etc.) In any case, all it serves to do is to punish honest non-derivative works not published compatible with the GPL. What I resist is the apparent attempt to change these symbols to _GPL as some matter of general policy in this case contrary to the author's original intentions as expressed in the original patch submission, and without the author of the interface being wrappered jumping up an screaming that his code was under strict FSF linking-is-derivation GPL (in which case we could have had a good discussion on whether Linux NET4 is actually a derivative work of BSD 4.4 Lite which was licensed under the "old" BSD license, incompatible with the GPL ;) As a general policy I would say make it EXPORT_SYMBOL() unless the author of the patch (derivation) or author of the original (derived) code dictates that it be EXPORT_SYMBOL_GPL(). Ok, I'll shut up now... ...really. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Chase, On Tue, 13 Jun 2006, Chase Venters wrote: > > > I don't think that it is fair to say that an unstable API/ABI, in of > > itself, provides an incentive to open an existing proprietary driver. > > Sure it does, depending on your perspective and what you're willing to > consider. The lack of a stable API/ABI means that if you don't want to have > to do work tracking the kernel, you should push to have your drivers merged. > More work must be done to track the kernel before they are merged, thus purposeless API changes, or unnecessary use of EXPORT_SYMBOL_GPL impedes merging Not all useful kernel modules will nor should be merged GPL or not. I think that a policy that intentionally makes it hard for proprietary modules to be developed defeats the purpose of ultimate opening and merging. It might end up causing something like iBCS, LinuxABI, SVR D3DK, or ODI to flourish obviating the principal goal. The interface currently under discussion is ultimately derived from the BSD socket-protocol interface, and IMHO should be EXPORT_SYMBOL instead of EXPORT_SYMBOL_GPL, if only because using _GPL serves no purpose here and can be defeated with 3 or 4 obvious (and probably existing) lines of code. I wrote similar wrappers for STREAMS TPI to Linux NET4 interface instead of using pointers directly quite a few years ago. I doubt I was the first. There is nothing really so novel here that it deserves _GPL. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Chase, On Tue, 13 Jun 2006, Chase Venters wrote: > > But I did ask for examples... Perhaps the license isn't a good example, but there are other RTP stacks that are non-GPL compatible. Also, if it includes SSL code for SRTP, SSL license happens to be non-GPL compatible. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Ben, On Tue, 13 Jun 2006, Ben Greear wrote: > > I got to the flame war late ... I think we're trying to have an honest open discussion here. I certainly don't mean to flame anyone and apologize if my remarks have been taken so. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Chase, On Tue, 13 Jun 2006, Chase Venters wrote: > > It depends on what you mean by "pure-BSD". If you're talking about the > 4-clause license with the advertising clause, then you are correct. Otherwise > (IANAL) but my understanding is that BSD code can even be relicensed GPL by a > third party contribution (though it is perhaps kind to ask for relicensing > permission anyway). Yes, and the long list of open source licenses listed on the FSF website as incompatible with the GPL. > Then would offering a 'stable API in disguise' not be a disaster and an > irritation to these people? If the kernel doesn't specify that an in-kernel > interface is stable, then there is no reason to expect it to be. It might not > change, but there won't be too much sympathy for out-of-tree users if it > does. The kernel comes with big warnings about the lack of a stable API for a > reason. In fact most core kernel facilities (spin lock, memory caches, character and block device interface, even core file system) have had a very stable API (way back to early 2.4 kernels). An in fact most of them are derived from some variant or precursor to UNIX. For example, memory caches are a Sun Solaris concept. It is the lack of an ABI that is most frustrating to these users. > > > Another thing to consider is that the first step for many organizations in > > opening a driver under GPL is to release a proprietary module that at least > > first works. > > If the driver is an old-tech Linux port, then it seems there isn't too much > stopping them from doing this today (aside from the fact that some people > think proprietary modules are murky anyway). In this case, we don't want a > stable API/ABI, because then we leave them with little incentive to open the > code. "old-tech"? No, these are high-tech drivers supported by commercial RTOS, from which Linux stands to benefit. And, by not allowing these organizations to take the first step (generate a workable Linux driver) such a policy provides them little incentive to ever move the driver to Linux, and cuts them off from opening it. I don't think that it is fair to say that an unstable API/ABI, in of itself, provides an incentive to open an existing proprietary driver. > We're not as perfect as I wish we were. But the lack of stable API (dead > horse) is something that is fairly well established and understood. I think > most people feel that the cost-benefit analysis, for Linux anyway, strongly > favors no stable API. Well, the lack of a stable ABI is well known. The API is largely stable (but not sacrosanctly so) for the major reason that changing it within a large code base is difficult and error prone at best. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Chase, On Tue, 13 Jun 2006, Chase Venters wrote: > I'm trying to imagine what kind of legitimate non-GPL modules might > use them. Example: in-kernel RTP implementation derived from AT&T rtp-lib implementation (non-GPL compatible license) utilizing this kernel interface for UDP socket access. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Daniel, On Tue, 13 Jun 2006, Daniel Phillips wrote: > > You probably meant "non-GPL-compatible non-proprietary". If so, then by > definition there are none. Well, being GPL compatible is not a requirement for an open source license. IANAL, but last I checked, pure-BSD is not compatible with GPL (it actually has to be dual-licensed BSD/GPL). - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Chase, On Tue, 13 Jun 2006, Chase Venters wrote: > > Look out for that word (stable). Judging from history (and sanity), > arguing /in favor of/ any kind of stable module API is asking for it. I was really just using Daniel's words. I am all too aware that kernel APIs are unstable. To some it is a serious failing of Linux (particularly those involved in porting kernel modules from branded UNIX or embedded RTOS). To those whatever stability that can be offered is a boon. To those, even worse is the lack of an ABI (even for a single kernel version). > > At least some of us feel like stable module APIs should be explicitly > discouraged, because we don't want to offer comfort for code > that refuses to live in the tree (since getting said code into the tree is > often a goal). And that would be fine if we were completely agnostic toward what was included in mainline, but we are not. A particular case in point that I deal with are STREAMS modules. STREAMS continues to be forbidden from the tree. Nevertheless, STREAMS has historically provided one of the most widespread mechanisms for providing value-added drivers to branded UNIX or embedded RTOS offerings. As a result, a large body of existing drivers are cut off from the tree regardless of their licensing terms. (Note that these is seldom a question of derivation for these drivers as they are fully functioning on other operating systems: branded UNIX or embedded RTOS.) > > I'm curious now too - can you name some non-GPL non-proprietary modules we > should be concerned about? I'd think most of the possible examples (not > sure what they are) would be better off dual-licensed (one license > being GPL) and in-kernel. Any open-source license not compatible with the GPL. One that comes to mind is OpenSolaris drivers. I'm sure that there are others because there are many license that qualify as open source licenses that are incompatible with the GPL. For example, pure BSD is incompatible with GPL. Another thing to consider is that the first step for many organizations in opening a driver under GPL is to release a proprietary module that at least first works. The second step is to jump through the hoops and over the hurdles necessary to open what has been to date proprietary code that may contain intellectual property issues across a number of organizations. In adopting a policy that hinders this process, we, instead, discourage opening of drivers and inclusion in mainline, rather than promoting it. Sorry for the rant. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Daniel, On Tue, 13 Jun 2006, Daniel Phillips wrote: > > This has the makings of a nice stable internal kernel api. Why do we want > to provide this nice stable internal api to proprietary modules? Why not? Not all non-GPL modules are proprietary. Do we lose something by making a nice stable api available to non-derived modules? - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [RFC/PATCH 1/2] in-kernel sockets API
Stephen, On Tue, 13 Jun 2006, Stephen Hemminger wrote: > > @@ -2176,3 +2279,13 @@ EXPORT_SYMBOL(sock_wake_async); > > EXPORT_SYMBOL(sockfd_lookup); > > EXPORT_SYMBOL(kernel_sendmsg); > > EXPORT_SYMBOL(kernel_recvmsg); > > +EXPORT_SYMBOL(kernel_bind); > > +EXPORT_SYMBOL(kernel_listen); > > +EXPORT_SYMBOL(kernel_accept); > > +EXPORT_SYMBOL(kernel_connect); > > +EXPORT_SYMBOL(kernel_getsockname); > > +EXPORT_SYMBOL(kernel_getpeername); > > +EXPORT_SYMBOL(kernel_getsockopt); > > +EXPORT_SYMBOL(kernel_setsockopt); > > +EXPORT_SYMBOL(kernel_sendpage); > > +EXPORT_SYMBOL(kernel_ioctl); > > Don't we want to restrict this to GPL code with EXPORT_SYMBOL_GPL? There are direct derivatives of the BSD/POSIX system call interface. The protocol function pointers within the socket structure are not GPL only. Why make this wrappered access to them GPL only? It will only encourange the reverse of what they were intended to do: be used instead of the protocol function pointers within the socket structure, that currently carry no such restriction. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Florian, On Fri, 02 Jun 2006, Florian Weimer wrote: > > I see them now. Hmm. Is there a theoretical explanation for them? Jenkins is an ad hoc function that is far from ideal. As you know, the ideal hash changes 1/2 the bits in the output value for each one bit change in the input value(s). Jenkins changes a few as 1/3 and performs less than ideal over even a small smaple of the input data set (Jenkins said he checked several billion of the trilions of changes). It should not be suprising that a general purpose ad hoc function (Jenkins) performs poorer than a specific purpose ad hoc function (XOR), for the very specific input data sets that the later was chosen to cover. Theoretically, XOR can be improved upon, but Jenkins doesn't do it. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Evgeniy, I agree, even with constant source IP, the hash still should have performed better (but didn't). Constant source IP and varying port is a realistic data set for a port proxy. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Evgeniy,
On Thu, 01 Jun 2006, Evgeniy Polyakov wrote:
I think the sun shines more in Moscow than in Edmonton, so it is not
so random. ;)
>
> Specially for you :)
Thank you for being so gracious and patient with me.
> It does not have artifacts, but it's dispersion is wider than XOR one.
> _Much_ wider, which tends to creation of some specially crafted source
> distribution which ends up in totally broken fairness.
> As usual folded and not folded versions behave exactly the same.
>
> > > With following ip/port selection algo:
> > > if (++sport == 0) {
> > > //saddr++;
> > > sport += 123;
> > > }
> > >
> > > I see yet another jenkins artefacts, but again different from previous
> > > two.
> >
> > Adding primes. Again, the arithmetic series of primes might auto-correlate
> > with the Jenkins function. Or it plain might not like gaps.
> >
>
> I want to confirm three things and one state:
> 1. Jenkins hash has some unacceptible artefacts in some source
> address/port distributions, no matter if it has some law embedded or it
> is (pseudo)-random set.
>
> If there are bugs, bugs exist.
True, artifacts appeared even in the basic arithmetic sequence of
primes. It is quite possible that a large set of natural sequences
might cause artifacts.
>
> 2. If it does not have artifacts it has unacceptible dispersion.
This is likely due to the relatively small sample sets; however, real
experienced data sets would be very small compared to the widest
possible set and might also contain structured gaps.
>
> 3. It is 3 times slower than XOR one (28 seconds for XOR for 2^29
> iterations vs. 101 seconds jhash nonfolded and 109 jhash folded on my AMD64
> 3500+ 2.2 Ghz desktop).
Yes, it is slower by inspection.
>
> 4. I believe it can be tuned or has some gaps inside refactoring logic,
> which can be fixed, but as is it can not be used for fair hash creation.
Yes, I now agree. And, for the purpose of dynamic hash sizing, high
dispersion is worse than artifacts.
For some realistic TCP data sets it appears that XOR is superior.
Thank you again for your efforts in resolving my doubts.
So what are your thoughts about my sequence number approach (for
connected sockets)?
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Evgeniy,
On Thu, 01 Jun 2006, Evgeniy Polyakov wrote:
For purely random numbers you could amplify thermal noise off an
open transitor junction (the audiofile's white noise generator)
and feed it into an analog to digital converter.
>
> I've run it with following source ip/port selection algo:
> if (++sport == 0) {
> saddr++;
> sport++;
> }
>
> Starting IP was 1.1.1.1 and sport was 1.
> Destination IP and port are the same 192.168.0.1:80
>
> Jenkins hash started to show different behaviour:
> it does not have previous artefacts, but instead it's dispersion is
> _much_ wider than in XOR case.
Aha! But perhaps this is too easy a data set. HTTP clients typically
dynamically allocate port numbers within a range and source address
are typically not less than a certain value. That is why I suggested
something like:
sport = 1;
saddr = 0x0a00; /* 10.0.0.0 */
...
if (++sport == 16000) {
sport = 1;
saddr++;
}
If this shows artifacts worse than XOR then more realistic gaps in the
input values will cause artifacts.
>
> With following ip/port selection algo:
> if (++sport == 0) {
> //saddr++;
> sport += 123;
> }
>
> I see yet another jenkins artefacts, but again different from previous
> two.
Adding primes. Again, the arithmetic series of primes might auto-correlate
with the Jenkins function. Or it plain might not like gaps.
>
> But each time both folded and not folded hashes behave exactly the same.
>
> > Can you show the same artifacts for jenkins_3word?
>
> What should be used as starting point there?
> If I use 0 it is the same as jhash_2words().
> If I use 123123 - artefacts are the same, just slighly shifted (I tested
> only the latest test above though).
>
> Looking into the code we can see that jhash_2words() is jhash_3words()
> with zero "C" value, so it will show the same nature.
Skip that then.
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Evgeniy, On Thu, 01 Jun 2006, Evgeniy Polyakov wrote: > On Thu, Jun 01, 2006 at 12:46:08AM -0600, Brian F. G. Bidulock ([EMAIL > PROTECTED]) wrote: > > > Since pseudo-randomness affects both folded and not folded hash > > > distribution, it can not end up in different results. > > > > Yes it would, so to rule out pseudo-random effects the pseudo- > > random number generator must be removed. > > > > > > > > You are right that having test with 2^48 values is really interesting, > > > but it will take ages on my test machine :) > > > > Try a usable subset; no pseudo-random number generator. > > I've run it for 2^30 - the same result: folded and not folded Jenkins > hash behave the same and still both results produce exactly the same > artifacts compared to XOR hash. But not without the pseudo-random number generation... ? > > Btw, XOR hash, as completely stateless, can be used to show how > Linux pseudo-random generator works for given subset - it's average of > distribution is very good. But its distribution might auto-correlate with the Jenkins function. The only way to be sure is to remove the pseudo-random number generator. Just try incrementing from, say, 10.0.0.0:1 up, resetting port number to 1 at 16000, and just incrementing the IP address when the port number wraps, instead of pseudo-random, through 2^30 loops for both. If the same artifacts emerge, I give in. Can you show the same artifacts for jenkins_3word? - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Evgeniy, On Thu, 01 Jun 2006, Evgeniy Polyakov wrote: > > Since pseudo-randomness affects both folded and not folded hash > distribution, it can not end up in different results. Yes it would, so to rule out pseudo-random effects the pseudo- random number generator must be removed. > > You are right that having test with 2^48 values is really interesting, > but it will take ages on my test machine :) Try a usable subset; no pseudo-random number generator. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
David, On Wed, 31 May 2006, David Miller wrote: > > Ok I believe you now :) > I'll believe it if he interates through a subset and gets the same results instead of using a pseudo-random number generator. I thought you said you were considering jenkins_3word(), not jenkins_2word()? - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Evgeniy, On Thu, 01 Jun 2006, Evgeniy Polyakov wrote: > > for (i=0; i saddr = num2ip(get_random_byte(), get_random_byte(), > get_random_byte(), get_random_byte()); > sport = get_random_word(); You still have a problem: you cannot use a pseudo-random number generator to generate the sample set as the pseudo-random number generator function itself can interact with the hash. Try iterating through all 2**48 values or at least a sizeable representative subset. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Evgeniy, On Wed, 31 May 2006, Evgeniy Polyakov wrote: > > > > Worse: he folded the jenkins algorith result with > > > > > > > >h ^= h >> 16; > > > >h ^= h >> 8; > > > > > > > > Destroying the coverage of the function. > > > > > > It was done to simulate socket code which uses the same folding. > > > Leaving 32bit space is just wrong, consider hash table size with that > > > index. > > Btw, that probably requires some clarification. > Since hash table size is definitely less than returned hash value, so > higher bits are removed, for that case above folding is done both in > XOR hash and my test case. > It is possible to just remove higher bits, but fairly ditributed parts > being xored produce still fairly distributed value. > > > >h ^= h >> 16; > > > >h ^= h >> 8; This does not remove high order bits in either function. Your comparison results are simply invalid with these two lines in place. --brian - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Evgeniy, On Wed, 31 May 2006, Evgeniy Polyakov wrote: > > 1. Netchannel. > http://tservice.net.ru/~s0mbre/old/?section=projects&item=netchannel This one refers to the erroneous result below. > > 2. Compared Jenkins hash with XOR hash used in TCP socket selection > code. > http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14 - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
Evgeniy, On Wed, 31 May 2006, Evgeniy Polyakov wrote: > 2. Compared Jenkins hash with XOR hash used in TCP socket selection code. > http://tservice.net.ru/~s0mbre/blog/2006/05/14#2006_05_14 Two problems with the comparison: Port numbers can be collected into a 32 bit register in network byte order directly from the TCP packet without taking two 16 bit values and shifting and or'ing them. Worse: he folded the jenkins algorith result with h ^= h >> 16; h ^= h >> 8; Destroying the coverage of the function. I, for one, am not suprised that artifacts appeared in the comparison as a result of this destruction of the coverage of the hashing function. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
David, On Wed, 31 May 2006, David Miller wrote: > > I don't know how practical this is. The 4GB sequence space > wraps very fast on 10 gigabit, so we'd be rehashing a bit > and 100 gigabit would make things worse whenever that shows > up. It works better for SCTP, because the vtags are constant. No rehashing is required there. But, also consider that rehashing is only required for senders sending at a high data rate. (http clients will likely never have to be rehashed.) These packets will typically be large and per-packet overheads will be overwhelmed by per-byte overheads. Also, the rehashing is orderly and simple, the entry is simply bumped to the next sequential hash slot and the socket hash structure can already be cached at the time the action is performed. Rehashing, although a bother, would take little time, and could simply be added as part of TCP's existing window calculations. > > It is, however, definitely an interesting idea. > > We also need the pure traditional hashes for net channels. I don't > see how we could use your scheme for net channels, because we are just > hashing in the interrupt handler of the network device driver in order > to get a queue to tack the packet onto, we're not interpreting the > sequence numbers and thus would not able to maintain the sequence > space based hashing state. Under SCTP I still have the traditional established hash for lookups of out of the blue packets and packets containing invalid verification tags. Really long lookups would invite DoS attacks on these. > > On a 3ghz cpu, the jenkins hash is essentially free. Even on slower > cpus, jhash_2words for example is just 20 cycles on a sparc64 chip. > It's ~40 integer instructions and they all pair up perfectly to > dual issue. We'd probably use jhash_3words() for TCP ipv4 which > would get us into the 30 cycle range. But you could throw away all 30 cycles, plus the stacking and unstacking of registers to get in and out of the algorithm. Some architectures might benefit more. Well, I thought you might find it interesting. Perhaps somebody reading this will experiment with it. For SCTP it is one of a number of techniques that allows OpenSS7 SCTP to drastically outperform lksctp. --brian - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
David, On Wed, 31 May 2006, David Miller wrote: > > For sure and there are plans afoot to move over to > dynamic table sizing and the Jenkins hash function. Just a suggestion, but I have an approach that stands to be faster than Jenkins deriving from the verification tag approach that I took for SCTP (OpenSS7 SCTP not lksctp). TCP uses a cryptographic hash function to select its initial sequence number (SCTP does the same for vtag). Last I checked it was taken from an MD4 swirled entropy pool and further combined with the local and remote IP addresses and port numbers. Each received segment contains a sequence number that is offset from the initial sequence number but is expected to appear within the current window. Most of the high order bits of an in-window sequence number are predicatable at any point in time and, due to cryptographic strength, are more efficient than Jenkins, ... and they are right there in the received packet. The approach would take the high order bits of the received sequence number and use them to index a separate sequence number keyed established hash (which could be dynamic). As the window changes, the socket would have to be removed and reinserted into this hash, but the repositioning would be infrequent. Out of window segments would fail to find a socket, but could fall back to the current established hash, or even the bind hash. A layer of caching could increase the hash lookup speed further for noisy senders. This would be faster than a Jenkins hash approach because it would not be necessary to calculate the hash function at all for in-window segments. Per packet overheads would decrease and better small packet performance would be experienced (i.e. your http server). It has better hash coverage because MD4 and other cryptographic algorithms used for initial sequence number selection have far better properties than Jenkins. What do you think? - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
David, On Wed, 31 May 2006, David Miller wrote: > > For sure and there are plans afoot to move over to > dynamic table sizing and the Jenkins hash function. Yes, that could be far more efficient. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: Question about tcp hash function tcp_hashfn()
David, On Wed, 31 May 2006, David Miller wrote: > From: "Brian F. G. Bidulock" <[EMAIL PROTECTED]> > Date: Tue, 30 May 2006 23:55:26 -0600 > > > For example, it goes to great pains to permute upper order bits in > > the local address, which for most connections will be a constant > > value. > > Consider an apache server hosting thousands of virtual > hosts. The local address will be different for every > such host. > If you mean named virtual hosts, no. They have the same addresses. If you mean actual hosts (with an IP address), perhaps in the low order bits (host number), but unlikely in the high order bits of the local address (network mask bits). Also, in such a case the local port number will be rather constant (80, etc); a condition also not exploited by the function. Also consider that the function simply folds the values rather than permuting bits across the key field by shifting by some other value than a multiple of 8 between XOR operations. This will result in a longer collision list because the entropy of the key value has not been sufficiently reduced. It might sound like I'm complaining, but I'm not. The function works for me. But from a purist point of view, the hash function is not as efficient as it could be and there is room for improvement. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
