Menu
▾
▴
[Selinux-commits] SF.net SVN: selinux: [2777] trunk
|
From: <ssm...@us...> - 2008-02-04 15:59:48
|
Revision: 2777
http://selinux.svn.sourceforge.net/selinux/?rev=2777&view=rev
Author: ssmalley
Date: 2008-02-04 07:24:49 -0800 (Mon, 04 Feb 2008)
Log Message:
-----------
Author: Stephen Smalley
Email: sd...@ty...
Subject: libsepol: tune avtab to reduce memory usage
Date: Fri, 01 Feb 2008 08:58:56 -0500
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 <sd...@ty...>
Acked-By: Joshua Brindle <me...@ma...>
Modified Paths:
--------------
trunk/checkpolicy/test/dispol.c
trunk/libsepol/include/sepol/policydb/avtab.h
trunk/libsepol/src/avtab.c
trunk/libsepol/src/conditional.c
trunk/libsepol/src/expand.c
trunk/libsepol/src/policydb.c
trunk/libsepol/src/write.c
Modified: trunk/checkpolicy/test/dispol.c
===================================================================
--- trunk/checkpolicy/test/dispol.c 2008-02-02 15:40:55 UTC (rev 2776)
+++ trunk/checkpolicy/test/dispol.c 2008-02-04 15:24:49 UTC (rev 2777)
@@ -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);
}
Modified: trunk/libsepol/include/sepol/policydb/avtab.h
===================================================================
--- trunk/libsepol/include/sepol/policydb/avtab.h 2008-02-02 15:40:55 UTC (rev 2776)
+++ trunk/libsepol/include/sepol/policydb/avtab.h 2008-02-04 15:24:49 UTC (rev 2777)
@@ -1,6 +1,11 @@
/* Author : Stephen Smalley, <sd...@ep...> */
+/*
+ * Updated: Yuichi Nakamura <yn...@hi...>
+ * Tuned number of hash slots for avtab to reduce memory usage
+ */
+
/* Updated: Frank Mayer <ma...@tr...> and Karl MacMillan <kma...@tr...>
*
* 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 */
Modified: trunk/libsepol/src/avtab.c
===================================================================
--- trunk/libsepol/src/avtab.c 2008-02-02 15:40:55 UTC (rev 2776)
+++ trunk/libsepol/src/avtab.c 2008-02-04 15:24:49 UTC (rev 2777)
@@ -1,6 +1,11 @@
/* Author : Stephen Smalley, <sd...@ep...> */
+/*
+ * Updated: Yuichi Nakamura <yn...@hi...>
+ * Tuned number of hash slots for avtab to reduce memory usage
+ */
+
/* Updated: Frank Mayer <ma...@tr...>
* and Karl MacMillan <kma...@me...>
*
@@ -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) {
Modified: trunk/libsepol/src/conditional.c
===================================================================
--- trunk/libsepol/src/conditional.c 2008-02-02 15:40:55 UTC (rev 2776)
+++ trunk/libsepol/src/conditional.c 2008-02-04 15:24:49 UTC (rev 2777)
@@ -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)
Modified: trunk/libsepol/src/expand.c
===================================================================
--- trunk/libsepol/src/expand.c 2008-02-02 15:40:55 UTC (rev 2776)
+++ trunk/libsepol/src/expand.c 2008-02-04 15:24:49 UTC (rev 2777)
@@ -2138,6 +2138,16 @@
avrule_block_t *prevblock;
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;
+ }
+
while (curblock) {
avrule_decl_t *decl = curblock->enabled;
avrule_t *cur_avrule;
@@ -2560,6 +2570,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);
@@ -2688,6 +2703,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;
Modified: trunk/libsepol/src/policydb.c
===================================================================
--- trunk/libsepol/src/policydb.c 2008-02-02 15:40:55 UTC (rev 2776)
+++ trunk/libsepol/src/policydb.c 2008-02-04 15:24:49 UTC (rev 2777)
@@ -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);
Modified: trunk/libsepol/src/write.c
===================================================================
--- trunk/libsepol/src/write.c 2008-02-02 15:40:55 UTC (rev 2776)
+++ trunk/libsepol/src/write.c 2008-02-04 15:24:49 UTC (rev 2777)
@@ -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;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
