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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <487C487C.5030403@cosmosbay.com>
Date:	Tue, 15 Jul 2008 08:49:32 +0200
From:	Eric Dumazet <dada1@...mosbay.com>
To:	David Miller <davem@...emloft.net>
Cc:	herbert@...dor.apana.org.au, netdev@...r.kernel.org
Subject: Re: [PATCH 10/13]: net: Implement simple sw TX hashing.

David Miller a écrit :
> From: Herbert Xu <herbert@...dor.apana.org.au>
> Date: Mon, 14 Jul 2008 19:33:02 +0800
> 
>> Eric Dumazet <dada1@...mosbay.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;
}

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html