| Main Archive Page > Month Archives > selinux archives |
Re: [patch] Tuning avtab to reduce memory usage
From: Stephen Smalley <sds_at_nospam>Date: Thu Jan 31 2008 - 21:00:50 GMT
To: Yuichi Nakamura <ynakam@hitachisoft.jp>
On Fri, 2007-08-24 at 11:55 +0900, Yuichi Nakamura wrote:
> On Thu, 23 Aug 2007 09:15:25 -0400
> Stephen Smalley wrote:
> > On Thu, 2007-08-23 at 09:57 +0900, Yuichi Nakamura wrote:
> > > Following is updated patch to 2.6.22.
> > >
> > > Signed-off-by: Yuichi Nakamura<ynakam@hitachisoft.jp>
> > > ---
> > > security/selinux/ss/avtab.c | 78 +++++++++++++++++++++++++++-----------
> > > security/selinux/ss/avtab.h | 16 +++++--
> > > security/selinux/ss/conditional.c | 4 +
> > > security/selinux/ss/policydb.c | 7 ---
> > > 4 files changed, 73 insertions(+), 32 deletions(-)
> > > diff -purN -X linux-2.6.22/Documentation/dontdiff linux-2.6.22.orig/security/selinux/ss/avtab.c linux-2.6.22/security/selinux/ss/avtab.c
> > > --- linux-2.6.22.orig/security/selinux/ss/avtab.c 2007-07-09 08:32:17.000000000 +0900
> > > +++ linux-2.6.22/security/selinux/ss/avtab.c 2007-08-23 09:30:03.000000000 +0900
> > > +int avtab_alloc(struct avtab *h, int nrules)
> >
> > nrules should be u32 too.
> Fixed.
>
> >
> > And you should likely test for the degenerate case (nrules == 0) and
> > bail on it.
> Checking nrules==0.
> And also checking !h->htable like below in avtab_search_node etc.
> - if (!h)
> + if (!h || !h->htable)
>
> Following is updated patch.
> From: Yuichi Nakamura <ynakam@hitachisoft.jp>
>
> 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>
> ---
> security/selinux/ss/avtab.c | 91 +++++++++++++++++++++++++++-----------
> security/selinux/ss/avtab.h | 16 ++++--
> security/selinux/ss/conditional.c | 4 +
> security/selinux/ss/policydb.c | 7 --
> 4 files changed, 82 insertions(+), 36 deletions(-)
Hi,
I'd like to apply the equivalent changes to libsepol, if you have no objection (note that libsepol is LGPL rather than GPL). A port of your patch to libsepol is below. This is to reduce memory usage by libsepol/libsemanage when reading in modules and policies. Is that ok with you? checkpolicy/test/dispol.c | 2 libsepol/include/sepol/policydb/avtab.h | 18 ++++--- libsepol/src/avtab.c | 80 ++++++++++++++++++++++++-------- libsepol/src/conditional.c | 4 + libsepol/src/policydb.c | 7 -- libsepol/src/write.c | 11 ++-- 6 files changed, 85 insertions(+), 37 deletions(-)
Index: libsepol/include/sepol/policydb/avtab.h
- libsepol/include/sepol/policydb/avtab.h (revision 2773) +++ libsepol/include/sepol/policydb/avtab.h (working copy) @@ -1,6 +1,11 @@
/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */
+/*
+ * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
+ * Tuned number of hash slots for avtab to reduce memory usage
+ */
+
/* Updated: Frank Mayer <mayerf@tresys.com> and Karl MacMillan <kmacmillan@tresys.com>
*
* 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: libsepol/src/conditional.c
- libsepol/src/conditional.c (revision 2773) +++ 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: libsepol/src/policydb.c
- libsepol/src/policydb.c (revision 2773) +++ libsepol/src/policydb.c (working copy) @@ -492,17 +492,14 @@
Index: libsepol/src/write.c
- libsepol/src/write.c (revision 2773) +++ 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: libsepol/src/avtab.c
- libsepol/src/avtab.c (revision 2773) +++ libsepol/src/avtab.c (working copy) @@ -1,6 +1,11 @@
/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */
+/*
+ * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
+ * Tuned number of hash slots for avtab to reduce memory usage
+ */
+
/* Updated: Frank Mayer <mayerf@tresys.com>
* and Karl MacMillan <kmacmillan@mentalrootkit.com>
*
@@ -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,
@@ -83,7 +88,7 @@
if (!h)
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 &&
@@ -123,7 +128,7 @@
if (!h)
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 &&
@@ -156,7 +161,7 @@
if (!h)
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 &&
@@ -191,7 +196,7 @@
if (!h)
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: checkpolicy/test/dispol.c
- checkpolicy/test/dispol.c (revision 2773) +++ checkpolicy/test/dispol.c (working copy) @@ -169,7 +169,7 @@ }