Re: [PATCH 10/13]: net: Implement simple sw TX hashing.

[Eric Dumazet <dada1@cosmosbay.com>]

David Miller a écrit :
> From: Herbert Xu <herbert@gondor.apana.org.au>
> Date: Mon, 14 Jul 2008 19:33:02 +0800
> 
>> Eric Dumazet <dada1@cosmosbay.com> wrote:
>>>> +     return hash % dev->real_num_tx_queues;
>>> simple but expensive... but could be changed to use reciprocal_divide() if necessary...
>> For the common cases it should be a power of 2 too.
> 
> Unfortunately it is not enforcable for it to be a power of 2
> and I fear it will in fact not be very often for several
> chips that will use this stuff.
> 
> BTW, how can reciprocal_divide() be used to compute a modulus?  Are
> you going to do the reciprocal divide, re-multiply, then subtract?
> :-)
> 

reciprocal divide is the name of the following
tranformation of a divide to one multiply.

f1(X) = X / N;  
->g1(X) ((u64)X * R) >> 32;

So you are right I was wrong to name the following 
transformation a reciprocal divide.

f2(X) = X % N ;
->g2(X) = ((u64)X * N) >> 32;

But g2() is quite similar to g1() :)

f2() & g2() functions are different of course, but should give 
same hash spreading if X has an uniform distribution in 32bits space.

simple_tx_hash() in its current form may not have this property, thats hard
to say.

For example, hash_dst() in net/netfilter/xt_hashlimit.c is using the following code :

static u_int32_t
hash_dst(const struct xt_hashlimit_htable *ht, const struct dsthash_dst *dst)
{
        u_int32_t hash = jhash2((const u32 *)dst,
                                sizeof(*dst)/sizeof(u32),
                                ht->rnd);
        /*
         * Instead of returning hash % ht->cfg.size (implying a divide)
         * we return the high 32 bits of the (hash * ht->cfg.size) that will
         * give results between [0 and cfg.size-1] and same hash distribution,
         * but using a multiply, less expensive than a divide
         */
        return ((u64)hash * ht->cfg.size) >> 32;
}