Add Toeplitz hash function to map packet's CPU

Matthew Dillon dillon at
Wed Mar 11 09:52:37 PDT 2009

:Hi all,
:After making two NICs multiple receive queue working, I now propose to
:add Toeplitz hash function to map packet's CPU.  It is mainly use to
:support "receive side scaling"
:( in
:forwarding path is even CPU localized).  If the packet is non-fragment
:TCP, the hash is calculated based on laddr,faddr,lport,fport, else the
:hash is calculated using laddr,faddr.
:There are two things we need to overcome:
:1) The result of hash function is non-commutative in the M$ paper,
:i.e. faddr,laddr,fport,lport and laddr,faddr,lport,fport gives
:different result.
:Thanks to corecode's suggestion, as long as 0xabcd is replicated to
:form the key, the result of the hash function _is_ commutative.
:2) It is computational heavy
:Thanks to corecode again, we could cache a pre-calculated result
:table, so we actually only need to index a array and OR the results.
:A simple implementation is at:
:I used it to verify that hardware gives the correct result :)
:The whole thing is not implemented yet, but if you don't think its bad
:idea, I will move on to implement it.  Note, it is not intended to
:replace the current packet hash function.
:Best Regards,

    Yes, I agree, we definitely need to make this an end-to-end capable
    feature, similar to propogating hardware checksum state.  My suggestion
    is that we add appropriate flags and a hash field in the mbuf header.

    I don't understand the 0xabcd replication comment w/ regards to making
    both directions of the connection produce the same hash value, but I
    agree that would be desirable.  Does it avoid having to recalculate
    a hardware-supplied hash code?

					Matthew Dillon 
					<dillon at>

More information about the Kernel mailing list