avtab dense hash table

[Pavel Roschin <roshin@scriptumplus.ru>]

Hello, I have some questions about hash tables in SELinux. As I see, all AV
rules are stored inside hash tables: I found them in kernel source and in
libsepol source. All types, domains, classes and so on also stored inside hash
tables.

Regarding source code of libsepol I see that all hash tables are fixed-size:
maximum avtab size is 2^13 - 8192 buckets. But in RHEL seinfo shows that there
are 250000+ allow rules and 170000+ dontaudit rules. Shouldn't that be a huge
performance kick?

In Linux kernel, avtab has size 2^11 - 2048 buckets for 256000+ av rules. Huge
hash table will be transformed into lists and linear search that should be slow
as hell, shouldn't?

>From kernel source:

#define MAX_AVTAB_HASH_BITS 11
#define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
#define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)

What is the reason of such dense hash maps?

--
Best regards,
Pavel Roschin


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.