Re: [patch] libsepol: tune avtab to reduce memory usage

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 

Joshua Brindle wrote:

Stephen Smalley wrote:

Port of Yuichi Nakamura's tune avtab to reduce memory usage patch
from the kernel avtab to libsepol.

This patch decides the number of hash slots dynamically based on the
number of rules.  It also avoids allocating the avtab altogether when
reading policy modules, as they don't need it.

Signed-off-by:  Stephen Smalley <sds@xxxxxxxxxxxxx>



Looks good to me

Acked-By: Joshua Brindle <method@xxxxxxxxxxxxxxx>
FYI: with these 3 recent patches (this one, free base immediately and expand consume) it looks like the rss of semodule has gone from 329912 kB to 208560 kB with a full refpolicy on my machine (x86-64). 




---
checkpolicy/test/dispol.c | 2 libsepol/include/sepol/policydb/avtab.h | 18 ++++-- libsepol/src/avtab.c | 88 +++++++++++++++++++++++--------- 
 libsepol/src/conditional.c              |    4 +
 libsepol/src/expand.c                   |   20 +++++++
 libsepol/src/policydb.c                 |    7 --
 libsepol/src/write.c                    |   11 ++--
 7 files changed, 109 insertions(+), 41 deletions(-)

Index: trunk/libsepol/include/sepol/policydb/avtab.h
===================================================================
--- trunk/libsepol/include/sepol/policydb/avtab.h    (revision 2774)
+++ trunk/libsepol/include/sepol/policydb/avtab.h    (working copy)
@@ -1,6 +1,11 @@
/* Author : Stephen Smalley, <sds@xxxxxxxxxxxxxx> */ +/* 
+ * Updated: Yuichi Nakamura <ynakam@xxxxxxxxxxxxxx>
+ *     Tuned number of hash slots for avtab to reduce memory usage
+ */
+
/* Updated: Frank Mayer <mayerf@xxxxxxxxxx> and Karl MacMillan <kmacmillan@xxxxxxxxxx> 
  *
  *     Added conditional policy language extensions
@@ -75,10 +80,12 @@
 typedef struct avtab {
     avtab_ptr_t *htable;
     uint32_t nel;        /* number of elements */
+    uint32_t nslot;         /* number of hash slots */
+    uint16_t mask;          /* mask to compute hash func */
 } avtab_t;
extern int avtab_init(avtab_t *); 
-
+extern int avtab_alloc(avtab_t *, uint32_t);
extern int avtab_insert(avtab_t * h, avtab_key_t * k, avtab_datum_t * d); extern avtab_datum_t *avtab_search(avtab_t * h, avtab_key_t * k); 
@@ -110,12 +117,11 @@
extern avtab_ptr_t avtab_search_node_next(avtab_ptr_t node, int specified); -#define AVTAB_HASH_BITS 15 
-#define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
-#define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
+#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
-#define AVTAB_SIZE AVTAB_HASH_BUCKETS 
-
 #endif                /* _AVTAB_H_ */
/* FLASK */ 
Index: trunk/libsepol/src/conditional.c
===================================================================
--- trunk/libsepol/src/conditional.c    (revision 2774)
+++ trunk/libsepol/src/conditional.c    (working copy)
@@ -829,6 +829,10 @@
len = le32_to_cpu(buf[0]); + rc = avtab_alloc(&p->te_cond_avtab, p->te_avtab.nel); 
+    if (rc)
+        goto err;
+
     for (i = 0; i < len; i++) {
         node = malloc(sizeof(cond_node_t));
         if (!node)
Index: trunk/libsepol/src/policydb.c
===================================================================
--- trunk/libsepol/src/policydb.c    (revision 2774)
+++ trunk/libsepol/src/policydb.c    (working copy)
@@ -492,17 +492,14 @@
rc = roles_init(p); 
     if (rc)
-        goto out_free_avtab;
+        goto out_free_symtab;
rc = cond_policydb_init(p); 
     if (rc)
-        goto out_free_avtab;
+        goto out_free_symtab;
       out:
     return rc;
- out_free_avtab: 
-    avtab_destroy(&p->te_avtab);
-
       out_free_symtab:
     for (i = 0; i < SYM_NUM; i++) {
         hashtab_destroy(p->symtab[i].table);
Index: trunk/libsepol/src/expand.c
===================================================================
--- trunk/libsepol/src/expand.c    (revision 2774)
+++ trunk/libsepol/src/expand.c    (working copy)
@@ -2137,6 +2137,16 @@
     avrule_block_t *curblock;
     int retval = -1;
+ if (avtab_alloc(&state->out->te_avtab, MAX_AVTAB_SIZE)) { 
+        ERR(state->handle, "Out of Memory!");
+        return -1;
+    }
+
+    if (avtab_alloc(&state->out->te_cond_avtab, MAX_AVTAB_SIZE)) {
+        ERR(state->handle, "Out of Memory!");
+        return -1;
+    }
+
     for (curblock = state->base->global; curblock != NULL;
          curblock = curblock->next) {
         avrule_decl_t *decl = curblock->enabled;
@@ -2548,6 +2558,11 @@
 {
     struct expand_avtab_data data;
+ if (avtab_alloc(expa, MAX_AVTAB_SIZE)) { 
+        ERR(NULL, "Out of memory!");
+        return -1;
+    }
+
     data.expa = expa;
     data.p = p;
     return avtab_map(a, expand_avtab_node, &data);
@@ -2676,6 +2691,11 @@
     avtab_ptr_t node;
     int rc;
+ if (avtab_alloc(expa, MAX_AVTAB_SIZE)) { 
+        ERR(NULL, "Out of memory!");
+        return -1;
+    }
+
     *newl = NULL;
     for (cur = l; cur; cur = cur->next) {
         node = cur->node;
Index: trunk/libsepol/src/write.c
===================================================================
--- trunk/libsepol/src/write.c    (revision 2774)
+++ trunk/libsepol/src/write.c    (working copy)
@@ -229,9 +229,9 @@
static inline void avtab_reset_merged(avtab_t * a) 
 {
-    int i;
+    unsigned int i;
     avtab_ptr_t cur;
-    for (i = 0; i < AVTAB_SIZE; i++) {
+    for (i = 0; i < a->nslot; i++) {
         for (cur = a->htable[i]; cur; cur = cur->next)
             cur->merged = 0;
     }
@@ -239,7 +239,8 @@
static int avtab_write(struct policydb *p, avtab_t * a, struct policy_file *fp) 
 {
-    int i, rc;
+    unsigned int i;
+    int rc;
     avtab_t expa;
     avtab_ptr_t cur;
     uint32_t nel;
@@ -269,7 +270,7 @@
             return POLICYDB_ERROR;
     }
- for (i = 0; i < AVTAB_SIZE; i++) { 
+    for (i = 0; i < a->nslot; i++) {
         for (cur = a->htable[i]; cur; cur = cur->next) {
             /* If old format, compute final nel.
                If new format, write out the items. */
@@ -290,7 +291,7 @@
             goto out;
         }
         avtab_reset_merged(a);
-        for (i = 0; i < AVTAB_SIZE; i++) {
+        for (i = 0; i < a->nslot; i++) {
             for (cur = a->htable[i]; cur; cur = cur->next) {
                 if (avtab_write_item(p, cur, fp, 1, 1, NULL)) {
                     rc = -1;
Index: trunk/libsepol/src/avtab.c
===================================================================
--- trunk/libsepol/src/avtab.c    (revision 2774)
+++ trunk/libsepol/src/avtab.c    (working copy)
@@ -1,6 +1,11 @@
/* Author : Stephen Smalley, <sds@xxxxxxxxxxxxxx> */ +/* 
+ * Updated: Yuichi Nakamura <ynakam@xxxxxxxxxxxxxx>
+ *     Tuned number of hash slots for avtab to reduce memory usage
+ */
+
 /* Updated: Frank Mayer <mayerf@xxxxxxxxxx>
  *          and Karl MacMillan <kmacmillan@xxxxxxxxxxxxxxxxx>
  *
@@ -44,11 +49,11 @@
 #include "debug.h"
 #include "private.h"
-#define AVTAB_HASH(keyp) \ 
-((keyp->target_class + \
- (keyp->target_type << 2) + \
- (keyp->source_type << 9)) & \
- AVTAB_HASH_MASK)
+static inline int avtab_hash(struct avtab_key *keyp, uint16_t mask)
+{
+    return ((keyp->target_class + (keyp->target_type << 2) +
+         (keyp->source_type << 9)) & mask);
+}
static avtab_ptr_t avtab_insert_node(avtab_t * h, int hvalue, avtab_ptr_t prev, avtab_key_t * key, 
@@ -80,10 +85,10 @@
     uint16_t specified =
         key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
- if (!h) 
+    if (!h || !h->htable)
         return SEPOL_ENOMEM;
- hvalue = AVTAB_HASH(key); 
+    hvalue = avtab_hash(key, h->mask);
     for (prev = NULL, cur = h->htable[hvalue];
          cur; prev = cur, cur = cur->next) {
         if (key->source_type == cur->key.source_type &&
@@ -121,9 +126,9 @@
     uint16_t specified =
         key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
- if (!h) 
+    if (!h || !h->htable)
         return NULL;
-    hvalue = AVTAB_HASH(key);
+    hvalue = avtab_hash(key, h->mask);
     for (prev = NULL, cur = h->htable[hvalue];
          cur; prev = cur, cur = cur->next) {
         if (key->source_type == cur->key.source_type &&
@@ -153,10 +158,10 @@
     uint16_t specified =
         key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
- if (!h) 
+    if (!h || !h->htable)
         return NULL;
- hvalue = AVTAB_HASH(key); 
+    hvalue = avtab_hash(key, h->mask);
     for (cur = h->htable[hvalue]; cur; cur = cur->next) {
         if (key->source_type == cur->key.source_type &&
             key->target_type == cur->key.target_type &&
@@ -188,10 +193,10 @@
     uint16_t specified =
         key->specified & ~(AVTAB_ENABLED | AVTAB_ENABLED_OLD);
- if (!h) 
+    if (!h || !h->htable)
         return NULL;
- hvalue = AVTAB_HASH(key); 
+    hvalue = avtab_hash(key, h->mask);
     for (cur = h->htable[hvalue]; cur; cur = cur->next) {
         if (key->source_type == cur->key.source_type &&
             key->target_type == cur->key.target_type &&
@@ -242,13 +247,13 @@
void avtab_destroy(avtab_t * h) 
 {
-    int i;
+    unsigned int i;
     avtab_ptr_t cur, temp;
if (!h || !h->htable) 
         return;
- for (i = 0; i < AVTAB_SIZE; i++) { 
+    for (i = 0; i < h->nslot; i++) {
         cur = h->htable[i];
         while (cur != NULL) {
             temp = cur;
@@ -259,19 +264,22 @@
     }
     free(h->htable);
     h->htable = NULL;
+    h->nslot = 0;
+    h->mask = 0;
 }
int avtab_map(avtab_t * h, 
           int (*apply) (avtab_key_t * k,
                 avtab_datum_t * d, void *args), void *args)
 {
-    int i, ret;
+    unsigned int i;
+    int ret;
     avtab_ptr_t cur;
if (!h) 
         return 0;
- for (i = 0; i < AVTAB_SIZE; i++) { 
+    for (i = 0; i < h->nslot; i++) {
         cur = h->htable[i];
         while (cur != NULL) {
             ret = apply(&cur->key, &cur->datum, args);
@@ -285,25 +293,50 @@
int avtab_init(avtab_t * h) 
 {
-    int i;
+    h->htable = NULL;
+    h->nel = 0;
+    return 0;
+}
- h->htable = malloc(sizeof(avtab_ptr_t) * AVTAB_SIZE); 
+int avtab_alloc(avtab_t *h, uint32_t nrules)
+{
+    uint16_t mask = 0;
+    uint32_t shift = 0;
+    uint32_t work = nrules;
+    uint32_t nslot = 0;
+
+    if (nrules == 0)
+        goto out;
+
+    while (work) {
+        work  = work >> 1;
+        shift++;
+    }
+    if (shift > 2)
+        shift = shift - 2;
+    nslot = 1 << shift;
+    if (nslot > MAX_AVTAB_SIZE)
+        nslot = MAX_AVTAB_SIZE;
+    mask = nslot - 1;
+
+    h->htable = calloc(nslot, sizeof(avtab_ptr_t));
     if (!h->htable)
         return -1;
-    for (i = 0; i < AVTAB_SIZE; i++)
-        h->htable[i] = (avtab_ptr_t) NULL;
+out:
     h->nel = 0;
+    h->nslot = nslot;
+    h->mask = mask;
     return 0;
 }
void avtab_hash_eval(avtab_t * h, char *tag) 
 {
-    int i, chain_len, slots_used, max_chain_len;
+    unsigned int i, chain_len, slots_used, max_chain_len;
     avtab_ptr_t cur;
slots_used = 0; 
     max_chain_len = 0;
-    for (i = 0; i < AVTAB_SIZE; i++) {
+    for (i = 0; i < h->nslot; i++) {
         cur = h->htable[i];
         if (cur) {
             slots_used++;
@@ -320,7 +353,7 @@
printf ("%s: %d entries and %d/%d buckets used, longest chain length %d\n", 
-         tag, h->nel, slots_used, AVTAB_SIZE, max_chain_len);
+         tag, h->nel, slots_used, h->nslot, max_chain_len);
 }
/* Ordering of datums in the original avtab format in the policy file. */ 
@@ -471,6 +504,13 @@
         ERR(fp->handle, "table is empty");
         goto bad;
     }
+
+    rc = avtab_alloc(a, nel);
+    if (rc) {
+        ERR(fp->handle, "out of memory");
+        goto bad;
+    }
+
     for (i = 0; i < nel; i++) {
         rc = avtab_read_item(fp, vers, a, avtab_insertf, NULL);
         if (rc) {
Index: trunk/checkpolicy/test/dispol.c
===================================================================
--- trunk/checkpolicy/test/dispol.c    (revision 2774)
+++ trunk/checkpolicy/test/dispol.c    (working copy)
@@ -169,7 +169,7 @@
     }
/* hmm...should have used avtab_map. */ 
-    for (i = 0; i < AVTAB_SIZE; i++) {
+    for (i = 0; i < expa.nslot; i++) {
         for (cur = expa.htable[i]; cur; cur = cur->next) {
             render_av_rule(&cur->key, &cur->datum, what, p, fp);
         }





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





--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@xxxxxxxxxxxxx with
the words "unsubscribe selinux" without quotes as the message.
[Index of Archives]     [Selinux Refpolicy]     [Linux SGX]     [Fedora Users]     [Fedora Desktop]     [Yosemite Photos]     [Yosemite Camping]     [Yosemite Campsites]     [KDE Users]     [Gnome Users]

  Powered by Linux