[patch] libsepol: tune avtab to reduce memory usage
Stephen Smalley <
sds@...>
2008-02-01 13:58:56 GMT
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@...>
---
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)
<at> <at> -1,6 +1,11 <at> <at>
/* Author : Stephen Smalley, <sds@...> */
+/*
+ * Updated: Yuichi Nakamura <ynakam@...>
+ * Tuned number of hash slots for avtab to reduce memory usage
+ */
+
/* Updated: Frank Mayer <mayerf@...> and Karl MacMillan <kmacmillan@...>
*
* Added conditional policy language extensions
<at> <at> -75,10 +80,12 <at> <at>
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);
<at> <at> -110,12 +117,11 <at> <at>
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)
<at> <at> -829,6 +829,10 <at> <at>
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)
<at> <at> -492,17 +492,14 <at> <at>
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)
<at> <at> -2137,6 +2137,16 <at> <at>
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;
<at> <at> -2548,6 +2558,11 <at> <at>
{
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);
<at> <at> -2676,6 +2691,11 <at> <at>
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)
<at> <at> -229,9 +229,9 <at> <at>
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;
}
<at> <at> -239,7 +239,8 <at> <at>
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;
<at> <at> -269,7 +270,7 <at> <at>
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. */
<at> <at> -290,7 +291,7 <at> <at>
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)
<at> <at> -1,6 +1,11 <at> <at>
/* Author : Stephen Smalley, <sds@...> */
+/*
+ * Updated: Yuichi Nakamura <ynakam@...>
+ * Tuned number of hash slots for avtab to reduce memory usage
+ */
+
/* Updated: Frank Mayer <mayerf@...>
* and Karl MacMillan <kmacmillan@...>
*
<at> <at> -44,11 +49,11 <at> <at>
#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,
<at> <at> -80,10 +85,10 <at> <at>
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 &&
<at> <at> -121,9 +126,9 <at> <at>
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 &&
<at> <at> -153,10 +158,10 <at> <at>
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 &&
<at> <at> -188,10 +193,10 <at> <at>
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 &&
<at> <at> -242,13 +247,13 <at> <at>
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;
<at> <at> -259,19 +264,22 <at> <at>
}
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);
<at> <at> -285,25 +293,50 <at> <at>
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++;
<at> <at> -320,7 +353,7 <at> <at>
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. */
<at> <at> -471,6 +504,13 <at> <at>
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)
<at> <at> -169,7 +169,7 <at> <at>
}
/* 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);
}
--
--
Stephen Smalley
National Security Agency
RSS Feed