Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value

[Stephen Smalley <sds@tycho.nsa.gov>]

On 2/14/20 12:38 PM, Stephen Smalley wrote:
> On 2/13/20 8:39 AM, Ondrej Mosnacek wrote:
>> According to profiling of semodule -BN, ebitmap_cardinality() is called
>> quite often and contributes a lot to the total runtime. Cache its result
>> in the ebitmap struct to reduce this overhead. The cached value is
>> invalidated on most modifying operations, but ebitmap_cardinality() is
>> usually called once the ebitmap doesn't change any more.
>>
>> After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
>> decreased from ~14.6s to ~12.4s (2.2s saved).
>>
>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> 
> This seems fine but I was wondering how many of the callers of 
> ebitmap_cardinality() actually need anything more than ebitmap_length()?

Regardless,

Acked-by: Stephen Smalley <sds@tycho.nsa.gov>

> 
>> ---
>>
>> v2: corrected time values in commit message
>>
>>   libsepol/include/sepol/policydb/ebitmap.h |  1 +
>>   libsepol/src/ebitmap.c                    | 10 ++++++++++
>>   2 files changed, 11 insertions(+)
>>
>> diff --git a/libsepol/include/sepol/policydb/ebitmap.h 
>> b/libsepol/include/sepol/policydb/ebitmap.h
>> index e62df01c..53fafdaa 100644
>> --- a/libsepol/include/sepol/policydb/ebitmap.h
>> +++ b/libsepol/include/sepol/policydb/ebitmap.h
>> @@ -37,6 +37,7 @@ typedef struct ebitmap_node {
>>   typedef struct ebitmap {
>>       ebitmap_node_t *node;    /* first node in the bitmap */
>>       uint32_t highbit;    /* highest position in the total bitmap */
>> +    unsigned int cardinality;    /* cached value of cardinality */
>>   } ebitmap_t;
>>   #define ebitmap_length(e) ((e)->highbit)
>> diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
>> index 6c9951b7..d23444ce 100644
>> --- a/libsepol/src/ebitmap.c
>> +++ b/libsepol/src/ebitmap.c
>> @@ -67,6 +67,7 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * 
>> e1)
>>       ebitmap_destroy(dst);
>>       dst->node = tmp.node;
>>       dst->highbit = tmp.highbit;
>> +    dst->cardinality = 0;
>>       return 0;
>>   }
>> @@ -128,9 +129,14 @@ int ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, 
>> ebitmap_t *e2, unsigned int ma
>>   unsigned int ebitmap_cardinality(ebitmap_t *e1)
>>   {
>>       unsigned int i, count = 0;
>> +
>> +    if (e1->cardinality || e1->highbit == 0)
>> +        return e1->cardinality;
>> +
>>       for (i=ebitmap_startbit(e1); i < ebitmap_length(e1); i++)
>>           if (ebitmap_get_bit(e1, i))
>>               count++;
>> +    e1->cardinality = count;
>>       return count;
>>   }
>> @@ -194,6 +200,7 @@ int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * 
>> src)
>>       }
>>       dst->highbit = src->highbit;
>> +    dst->cardinality = src->cardinality;
>>       return 0;
>>   }
>> @@ -309,6 +316,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int 
>> bit, int value)
>>                       free(n);
>>                   }
>>               }
>> +            e->cardinality = 0; /* invalidate cached cardinality */
>>               return 0;
>>           }
>>           prev = n;
>> @@ -339,6 +347,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int 
>> bit, int value)
>>           e->node = new;
>>       }
>> +    e->cardinality = 0; /* invalidate cached cardinality */
>>       return 0;
>>   }
>> @@ -358,6 +367,7 @@ void ebitmap_destroy(ebitmap_t * e)
>>       e->highbit = 0;
>>       e->node = 0;
>> +    e->cardinality = 0;
>>       return;
>>   }
>>
>