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

[Joshua Brindle <method@xxxxxxxxxxxxxxx>]

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>

> ---
>
>  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.