SELinux: tune avtab to reduce memory usage

This patch reduces memory usage of SELinux by tuning avtab. Number of hash
slots in avtab was 32768. Unused slots used memory when number of rules is
fewer. This patch decides number of hash slots dynamically based on number
of rules. (chain length)^2 is also printed out in avtab_hash_eval to see
standard deviation of avtab hash table.

Signed-off-by: Yuichi Nakamura<ynakam@hitachisoft.jp>
Acked-by:  Stephen Smalley <sds@tycho.nsa.gov>
Signed-off-by: James Morris <jmorris@namei.org>

1 files changed, 11 insertions, 5 deletions

diff --git a/security/selinux/ss/avtab.h b/security/selinux/ss/avtab.h
index 0a90d939af93..d8edf8ca56d1 100644
--- a/security/selinux/ss/avtab.h
+++ b/security/selinux/ss/avtab.h
@@ -16,6 +16,9 @@
  *      This program is free software; you can redistribute it and/or modify
  *      it under the terms of the GNU General Public License as published by
  *      the Free Software Foundation, version 2.
+ *
+ * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
+ *      Tuned number of hash slots for avtab to reduce memory usage
  */
 #ifndef _SS_AVTAB_H_
 #define _SS_AVTAB_H_
@@ -50,9 +53,13 @@ struct avtab_node {
 struct avtab {
         struct avtab_node **htable;
         u32 nel;        /* number of elements */
+        u32 nslot;      /* number of hash slots */
+        u16 mask;       /* mask to compute hash func */
+
 };
 
 int avtab_init(struct avtab *);
+int avtab_alloc(struct avtab *, u32);
 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *k);
 void avtab_destroy(struct avtab *h);
 void avtab_hash_eval(struct avtab *h, char *tag);
@@ -74,11 +81,10 @@ struct avtab_node *avtab_search_node_next(struct avtab_node *node, int specified
 void avtab_cache_init(void);
 void avtab_cache_destroy(void);
 
-#define AVTAB_HASH_BITS 15
-#define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
-#define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
-
-#define AVTAB_SIZE AVTAB_HASH_BUCKETS
+#define MAX_AVTAB_HASH_BITS 13
+#define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
+#define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
+#define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
 
 #endif  /* _SS_AVTAB_H_ */