Defaults for rte_hash

Defaults for rte_hash

[Matthew Hall]

Hello,

I was looking at the code which inits rte_hash objects in examples/l3fwd. It's 
using approx. 1M to 4M hash 'entries' depending on 32-bit vs 64-bit, but it's 
setting the 'bucket_entries' to just 4.

Normally I'm used to using somewhat deeper hash buckets than that... it seems 
like having a zillion little tiny hash buckets would cause more TLB pressure 
and memory overhead... or does 4 get shifted / exponentiated into 2**4 ?

The documentation in http://dpdk.org/doc/api/structrte__hash__parameters.html 
and http://dpdk.org/doc/api/rte__hash_8h.html isn't that clear... is there a 
better place to look for this?

In my case I'm looking to create a table of 4M or 8M entries, containing 
tables of security threat IPs / domains, to be detected in the traffic. So it 
would be good to have some understanding how not to waste a ton of memory on a 
table this huge without making it run super slow either.

Did anybody have some experience with how to get this right?

Another thing... the LPM table uses 16-bit Hop IDs. But I would probably have 
more than 64K CIDR blocks of badness on the Internet available to me for 
analysis. How would I cope with this, besides just letting some attackers 
escape unnoticed? ;)

Have we got some kind of structure which allows a greater number of CIDRs even 
if it's not quite as fast?

Thanks,
Matthew.

Re: Defaults for rte_hash

[Richardson, Bruce]

> -----Original Message-----
> From: dev [mailto:dev-bounces-VfR2kkLFssw@public.gmane.org] On Behalf Of Matthew Hall
> Sent: Tuesday, September 09, 2014 11:32 AM
> To: dev-VfR2kkLFssw@public.gmane.org
> Subject: [dpdk-dev] Defaults for rte_hash
> 
> Hello,
> 
> I was looking at the code which inits rte_hash objects in examples/l3fwd. It's
> using approx. 1M to 4M hash 'entries' depending on 32-bit vs 64-bit, but it's
> setting the 'bucket_entries' to just 4.
> 
> Normally I'm used to using somewhat deeper hash buckets than that... it seems
> like having a zillion little tiny hash buckets would cause more TLB pressure
> and memory overhead... or does 4 get shifted / exponentiated into 2**4 ?
> 
> The documentation in
> http://dpdk.org/doc/api/structrte__hash__parameters.html
> and http://dpdk.org/doc/api/rte__hash_8h.html isn't that clear... is there a
> better place to look for this?
> 
> In my case I'm looking to create a table of 4M or 8M entries, containing
> tables of security threat IPs / domains, to be detected in the traffic. So it
> would be good to have some understanding how not to waste a ton of memory
> on a
> table this huge without making it run super slow either.
> 
> Did anybody have some experience with how to get this right?

It might be worth looking too at the hash table structures in the librte_table directory for packet framework. These should give better scalability across millions of flows than the existing rte_hash implementation. [We're looking here to provide in the future a similar, more scalable, hash table implementation with an API like that of rte_hash, but that is still under development here at the moment.]

> 
> Another thing... the LPM table uses 16-bit Hop IDs. But I would probably have
> more than 64K CIDR blocks of badness on the Internet available to me for
> analysis. How would I cope with this, besides just letting some attackers
> escape unnoticed? ;)

Actually, I think the next hop field in the lpm implementation is only 8-bits, not 16 :-). Each lpm entry is only 16-bits in total.

> 
> Have we got some kind of structure which allows a greater number of CIDRs
> even
> if it's not quite as fast?
> 
> Thanks,
> Matthew.

Re: Defaults for rte_hash

[De Lara Guarch, Pablo]

> -----Original Message-----
> From: dev [mailto:dev-bounces-VfR2kkLFssw@public.gmane.org] On Behalf Of Richardson, Bruce
> Sent: Tuesday, September 09, 2014 11:45 AM
> To: Matthew Hall; dev-VfR2kkLFssw@public.gmane.org
> Subject: Re: [dpdk-dev] Defaults for rte_hash
> 
> > -----Original Message-----
> > From: dev [mailto:dev-bounces-VfR2kkLFssw@public.gmane.org] On Behalf Of Matthew Hall
> > Sent: Tuesday, September 09, 2014 11:32 AM
> > To: dev-VfR2kkLFssw@public.gmane.org
> > Subject: [dpdk-dev] Defaults for rte_hash
> >
> > Hello,
> >
> > I was looking at the code which inits rte_hash objects in examples/l3fwd.
> It's
> > using approx. 1M to 4M hash 'entries' depending on 32-bit vs 64-bit, but it's
> > setting the 'bucket_entries' to just 4.
> >
> > Normally I'm used to using somewhat deeper hash buckets than that... it
> seems
> > like having a zillion little tiny hash buckets would cause more TLB pressure
> > and memory overhead... or does 4 get shifted / exponentiated into 2**4 ?
> >

That 4 is not shifted, so it is actually 4 entries/bucket. Actually, the maximum number of entries you can use is 16, as bucket will be as big as a cache line.
However, regardless the number of entries, memory size will remain the same, but using 4 entries/bucket, with 16-byte key, all keys stored for a bucket will fit in a cache line, 
so performance looks to be better in this case (although a non-optimal hash function could lead not to be able to store all keys, as chances to fill a bucket are higher).
Anyway, for this example, 4 entries/bucket looks a good number to me.

> > The documentation in
> > http://dpdk.org/doc/api/structrte__hash__parameters.html
> > and http://dpdk.org/doc/api/rte__hash_8h.html isn't that clear... is there a
> > better place to look for this?
> >
> > In my case I'm looking to create a table of 4M or 8M entries, containing
> > tables of security threat IPs / domains, to be detected in the traffic. So it
> > would be good to have some understanding how not to waste a ton of
> memory
> > on a
> > table this huge without making it run super slow either.
> >
> > Did anybody have some experience with how to get this right?
> 
> It might be worth looking too at the hash table structures in the librte_table
> directory for packet framework. These should give better scalability across
> millions of flows than the existing rte_hash implementation. [We're looking
> here to provide in the future a similar, more scalable, hash table
> implementation with an API like that of rte_hash, but that is still under
> development here at the moment.]
> 
> >
> > Another thing... the LPM table uses 16-bit Hop IDs. But I would probably
> have
> > more than 64K CIDR blocks of badness on the Internet available to me for
> > analysis. How would I cope with this, besides just letting some attackers
> > escape unnoticed? ;)
> 
> Actually, I think the next hop field in the lpm implementation is only 8-bits,
> not 16 :-). Each lpm entry is only 16-bits in total.
> 
> >
> > Have we got some kind of structure which allows a greater number of
> CIDRs
> > even
> > if it's not quite as fast?
> >
> > Thanks,
> > Matthew.

Re: Defaults for rte_hash

[Matthew Hall]

On Tue, Sep 09, 2014 at 11:42:40AM +0000, De Lara Guarch, Pablo wrote:
> That 4 is not shifted, so it is actually 4 entries/bucket. Actually, the 
> maximum number of entries you can use is 16, as bucket will be as big as a 
> cache line. However, regardless the number of entries, memory size will 
> remain the same, but using 4 entries/bucket, with 16-byte key, all keys 
> stored for a bucket will fit in a cache line, so performance looks to be 
> better in this case (although a non-optimal hash function could lead not to 
> be able to store all keys, as chances to fill a bucket are higher). Anyway, 
> for this example, 4 entries/bucket looks a good number to me.

So, a general purpose hash usually has some kind of conflict resolution when a 
bucket is full rather than just tossing out entries. It could be open 
addressing, chaining, secondary hashing, etc.

If I'm putting security indicators into a bucket and the buckets just toss 
stuff out without warning that's a security problem. Same thing could be true 
for firewall tables.

Also, if we're assuming a 16-byte key, what happens when I want to do matching 
against www.badness.com or www.this-is-a-really-long-malware-domain.net ?

Did anybody have a performant general purpose hash table for DPDK that doesn't 
have problems with bigger keys or depth issues in a bucket?

Matthew.