[PATCH] selinux: Reduce memory use by avtab

This patch improves memory use by SELinux by both reducing the avtab node
size and reducing the number of avtab nodes.  The memory savings are
substantial, e.g.  on a 64-bit system after boot, James Morris reported the
following data for the targeted and strict policies:

            #objs  objsize   kernmem
Targeted:
  Before:  237888       40     9.1MB
  After:    19968       24     468KB

Strict:
  Before:  571680       40   21.81MB
  After:   221052       24    5.06MB

The improvement in memory use comes at a cost in the speed of security
server computations of access vectors, but these computations are only
required on AVC cache misses, and performance measurements by James Morris
using a number of benchmarks have shown that the change does not cause any
significant degradation.

Note that a rebuilt policy via an updated policy toolchain
(libsepol/checkpolicy) is required in order to gain the full benefits of
this patch, although some memory savings benefits are immediately applied
even to older policies (in particular, the reduction in avtab node size).
Sources for the updated toolchain are presently available from the
sourceforge CVS tree (http://sourceforge.net/cvs/?group_id=21266), and
tarballs are available from http://www.flux.utah.edu/~sds.

Signed-off-by: Stephen Smalley <sds@tycho.nsa.gov>
Signed-off-by: James Morris <jmorris@namei.org>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>

9 files changed, 400 insertions, 235 deletions

diff --git a/security/selinux/include/security.h b/security/selinux/include/security.h
index 71c0a19c9753..5f016c98056f 100644
--- a/security/selinux/include/security.h
+++ b/security/selinux/include/security.h
@@ -23,10 +23,11 @@
 #define POLICYDB_VERSION_NLCLASS        18
 #define POLICYDB_VERSION_VALIDATETRANS  19
 #define POLICYDB_VERSION_MLS            19
+#define POLICYDB_VERSION_AVTAB          20
 
 /* Range of policy versions we understand*/
 #define POLICYDB_VERSION_MIN   POLICYDB_VERSION_BASE
-#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_MLS
+#define POLICYDB_VERSION_MAX   POLICYDB_VERSION_AVTAB
 
 #ifdef CONFIG_SECURITY_SELINUX_BOOTPARAM
 extern int selinux_enabled;
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index f238c034c44e..2e71af67b5d8 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -58,6 +58,7 @@ static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_dat
 {
         int hvalue;
         struct avtab_node *prev, *cur, *newnode;
+        u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
         if (!h)
                 return -EINVAL;
@@ -69,7 +70,7 @@ static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_dat
                 if (key->source_type == cur->key.source_type &&
                     key->target_type == cur->key.target_type &&
                     key->target_class == cur->key.target_class &&
-                    (datum->specified & cur->datum.specified))
+                    (specified & cur->key.specified))
                         return -EEXIST;
                 if (key->source_type < cur->key.source_type)
                         break;
@@ -98,6 +99,7 @@ avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_da
 {
         int hvalue;
         struct avtab_node *prev, *cur, *newnode;
+        u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
         if (!h)
                 return NULL;
@@ -108,7 +110,7 @@ avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_da
                 if (key->source_type == cur->key.source_type &&
                     key->target_type == cur->key.target_type &&
                     key->target_class == cur->key.target_class &&
-                    (datum->specified & cur->datum.specified))
+                    (specified & cur->key.specified))
                         break;
                 if (key->source_type < cur->key.source_type)
                         break;
@@ -125,10 +127,11 @@ avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_da
         return newnode;
 }
 
-struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key, int specified)
+struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
 {
         int hvalue;
         struct avtab_node *cur;
+        u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
         if (!h)
                 return NULL;
@@ -138,7 +141,7 @@ struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key, int spe
                 if (key->source_type == cur->key.source_type &&
                     key->target_type == cur->key.target_type &&
                     key->target_class == cur->key.target_class &&
-                    (specified & cur->datum.specified))
+                    (specified & cur->key.specified))
                         return &cur->datum;
 
                 if (key->source_type < cur->key.source_type)
@@ -159,10 +162,11 @@ struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key, int spe
  * conjunction with avtab_search_next_node()
  */
 struct avtab_node*
-avtab_search_node(struct avtab *h, struct avtab_key *key, int specified)
+avtab_search_node(struct avtab *h, struct avtab_key *key)
 {
         int hvalue;
         struct avtab_node *cur;
+        u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
 
         if (!h)
                 return NULL;
@@ -172,7 +176,7 @@ avtab_search_node(struct avtab *h, struct avtab_key *key, int specified)
                 if (key->source_type == cur->key.source_type &&
                     key->target_type == cur->key.target_type &&
                     key->target_class == cur->key.target_class &&
-                    (specified & cur->datum.specified))
+                    (specified & cur->key.specified))
                         return cur;
 
                 if (key->source_type < cur->key.source_type)
@@ -196,11 +200,12 @@ avtab_search_node_next(struct avtab_node *node, int specified)
         if (!node)
                 return NULL;
 
+        specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
         for (cur = node->next; cur; cur = cur->next) {
                 if (node->key.source_type == cur->key.source_type &&
                     node->key.target_type == cur->key.target_type &&
                     node->key.target_class == cur->key.target_class &&
-                    (specified & cur->datum.specified))
+                    (specified & cur->key.specified))
                         return cur;
 
                 if (node->key.source_type < cur->key.source_type)
@@ -278,75 +283,126 @@ void avtab_hash_eval(struct avtab *h, char *tag)
                max_chain_len);
 }
 
-int avtab_read_item(void *fp, struct avtab_datum *avdatum, struct avtab_key *avkey)
+static uint16_t spec_order[] = {
+        AVTAB_ALLOWED,
+        AVTAB_AUDITDENY,
+        AVTAB_AUDITALLOW,
+        AVTAB_TRANSITION,
+        AVTAB_CHANGE,
+        AVTAB_MEMBER
+};
+
+int avtab_read_item(void *fp, u32 vers, struct avtab *a,
+                    int (*insertf)(struct avtab *a, struct avtab_key *k,
+                                   struct avtab_datum *d, void *p),
+                    void *p)
 {
-        u32 buf[7];
-        u32 items, items2;
-        int rc;
+        u16 buf16[4], enabled;
+        u32 buf32[7], items, items2, val;
+        struct avtab_key key;
+        struct avtab_datum datum;
+        int i, rc;
+
+        memset(&key, 0, sizeof(struct avt