aboutsummaryrefslogtreecommitdiff
path: root/security/selinux/ss/avtab.c
diff options
context:
space:
mode:
authorYuichi Nakamura <ynakam@hitachisoft.jp>2007-08-24 11:55:11 +0900
committerJames Morris <jmorris@namei.org>2007-10-17 08:59:30 +1000
commit3232c110b56bd01c5f0fdfd16b4d695f2e05b0a9 (patch)
treeb369f8dc55e9d27bbd0b8b4b6843c0736d61b005 /security/selinux/ss/avtab.c
parent821f3eff7cdb9d6c7076effabd46c96c322daed1 (diff)
SELinux: tune avtab to reduce memory usage
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> Acked-by: Stephen Smalley <sds@tycho.nsa.gov> Signed-off-by: James Morris <jmorris@namei.org>
Diffstat (limited to 'security/selinux/ss/avtab.c')
-rw-r--r--security/selinux/ss/avtab.c91
1 files changed, 65 insertions, 26 deletions
diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
index 85705eb289e..7551af1f789 100644
--- a/security/selinux/ss/avtab.c
+++ b/security/selinux/ss/avtab.c
@@ -12,24 +12,25 @@
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, version 2.
+ *
+ * Updated: Yuichi Nakamura <ynakam@hitachisoft.jp>
+ * Tuned number of hash slots for avtab to reduce memory usage
*/
#include <linux/kernel.h>
#include <linux/slab.h>
-#include <linux/vmalloc.h>
#include <linux/errno.h>
-
#include "avtab.h"
#include "policydb.h"
-#define AVTAB_HASH(keyp) \
-((keyp->target_class + \
- (keyp->target_type << 2) + \
- (keyp->source_type << 9)) & \
- AVTAB_HASH_MASK)
-
static struct kmem_cache *avtab_node_cachep;
+static inline int avtab_hash(struct avtab_key *keyp, u16 mask)
+{
+ return ((keyp->target_class + (keyp->target_type << 2) +
+ (keyp->source_type << 9)) & mask);
+}
+
static struct avtab_node*
avtab_insert_node(struct avtab *h, int hvalue,
struct avtab_node * prev, struct avtab_node * cur,
@@ -59,10 +60,10 @@ static int avtab_insert(struct avtab *h, struct avtab_key *key, struct avtab_dat
struct avtab_node *prev, *cur, *newnode;
u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
- if (!h)
+ if (!h || !h->htable)
return -EINVAL;
- hvalue = AVTAB_HASH(key);
+ hvalue = avtab_hash(key, h->mask);
for (prev = NULL, cur = h->htable[hvalue];
cur;
prev = cur, cur = cur->next) {
@@ -100,9 +101,9 @@ avtab_insert_nonunique(struct avtab * h, struct avtab_key * key, struct avtab_da
struct avtab_node *prev, *cur, *newnode;
u16 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) {
@@ -132,10 +133,10 @@ struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *key)
struct avtab_node *cur;
u16 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 &&
@@ -167,10 +168,10 @@ avtab_search_node(struct avtab *h, struct avtab_key *key)
struct avtab_node *cur;
u16 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 &&
@@ -228,7 +229,7 @@ void avtab_destroy(struct avtab *h)
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;
@@ -237,32 +238,63 @@ void avtab_destroy(struct avtab *h)
}
h->htable[i] = NULL;
}
- vfree(h->htable);
+ kfree(h->htable);
h->htable = NULL;
+ h->nslot = 0;
+ h->mask = 0;
}
-
int avtab_init(struct avtab *h)
{
- int i;
+ h->htable = NULL;
+ h->nel = 0;
+ return 0;
+}
+
+int avtab_alloc(struct avtab *h, u32 nrules)
+{
+ u16 mask = 0;
+ u32 shift = 0;
+ u32 work = nrules;
+ u32 nslot = 0;
+
+ if (nrules == 0)
+ goto avtab_alloc_out;
- h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
+ 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 = kcalloc(nslot, sizeof(*(h->htable)), GFP_KERNEL);
if (!h->htable)
return -ENOMEM;
- for (i = 0; i < AVTAB_SIZE; i++)
- h->htable[i] = NULL;
+
+ avtab_alloc_out:
h->nel = 0;
+ h->nslot = nslot;
+ h->mask = mask;
+ printk(KERN_DEBUG "SELinux:%d avtab hash slots allocated."
+ "Num of rules:%d\n", h->nslot, nrules);
return 0;
}
void avtab_hash_eval(struct avtab *h, char *tag)
{
int i, chain_len, slots_used, max_chain_len;
+ unsigned long long chain2_len_sum;
struct avtab_node *cur;
slots_used = 0;
max_chain_len = 0;
- for (i = 0; i < AVTAB_SIZE; i++) {
+ chain2_len_sum = 0;
+ for (i = 0; i < h->nslot; i++) {
cur = h->htable[i];
if (cur) {
slots_used++;
@@ -274,12 +306,14 @@ void avtab_hash_eval(struct avtab *h, char *tag)
if (chain_len > max_chain_len)
max_chain_len = chain_len;
+ chain2_len_sum += chain_len * chain_len;
}
}
printk(KERN_DEBUG "%s: %d entries and %d/%d buckets used, longest "
- "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
- max_chain_len);
+ "chain length %d sum of chain length^2 %Lu\n",
+ tag, h->nel, slots_used, h->nslot, max_chain_len,
+ chain2_len_sum);
}
static uint16_t spec_order[] = {
@@ -419,6 +453,11 @@ int avtab_read(struct avtab *a, void *fp, u32 vers)
rc = -EINVAL;
goto bad;
}
+
+ rc = avtab_alloc(a, nel);
+ if (rc)
+ goto bad;
+
for (i = 0; i < nel; i++) {
rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL);
if (rc) {