From mboxrd@z Thu Jan 1 00:00:00 1970 Message-ID: <47A3483D.8090705@tresys.com> Date: Fri, 01 Feb 2008 11:26:37 -0500 From: Joshua Brindle MIME-Version: 1.0 To: Stephen Smalley CC: selinux@tycho.nsa.gov, Yuichi Nakamura , "Todd C. Miller" Subject: Re: [patch] libsepol: tune avtab to reduce memory usage References: <1201874336.4568.142.camel@moss-spartans.epoch.ncsc.mil> <47A33D70.7010704@manicmethod.com> In-Reply-To: <47A33D70.7010704@manicmethod.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Sender: owner-selinux@tycho.nsa.gov List-Id: selinux@tycho.nsa.gov Joshua Brindle wrote: > 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 >> >> > > Looks good to me > > Acked-By: Joshua Brindle FYI: with these 3 recent patches (this one, free base immediately and expand consume) it looks like the rss of semodule has gone from 329912 kB to 208560 kB with a full refpolicy on my machine (x86-64). > >> --- >> >> 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, */ >> >> +/* >> + * Updated: Yuichi Nakamura >> + * Tuned number of hash slots for avtab to reduce memory usage >> + */ >> + >> /* Updated: Frank Mayer and Karl MacMillan >> >> * >> * 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, */ >> >> +/* >> + * Updated: Yuichi Nakamura >> + * Tuned number of hash slots for avtab to reduce memory usage >> + */ >> + >> /* Updated: Frank Mayer >> * and Karl MacMillan >> * >> @@ -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@tycho.nsa.gov > with > the words "unsubscribe selinux" without quotes as the message. > -- This message was distributed to subscribers of the selinux mailing list. If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with the words "unsubscribe selinux" without quotes as the message.