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
| ||
|
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
Powered by blists - more mailing lists