Re: [RFCv2] security: smack: add a hash table to quickensmk_find_entry()

[Tomasz Stanislawski]

Hi Casey,
Thank you for your review.
Please refer to comments below.

On 06/12/2013 07:11 AM, Casey Schaufler wrote:
> On 6/11/2013 5:55 AM, Tomasz Stanislawski wrote:
>> This patch adds a hash table to quicken searching of a smack label by its name.
>>
>> Basically, the patch improves performance of SMACK initialization.  Parsing of
>> rules involves translation from a string to a smack_known (aka label) entity
>> which is done in smk_find_entry().
> 
> There is one place where this is done, and that is in smk_import_entry().
> 
> There is another place where labels are looked up, and that is in
> smack_from_secattr(). Can you apply this enhancement there, too?
> 

The overmentioned function contains following check:

                        if (memcmp(sap->attr.mls.cat,
                                 skp->smk_netlabel.attr.mls.cat,
                                 SMK_CIPSOLEN) != 0)
                                 continue;

What does it mean?
I expect that there was a reason not to use smk_find_entry()
in smack_from_secattr().

Do you want me to introduce a new hash table for searching
skp->smk_netlabel.attr.mls.cat using up to SMK_CIPSOLEN character
to produce a hash?

If it is true then this change is rather orthogonal to the current patch
and it can go to a separate patch.

Moreover, smack_from_secid() may need some hashing improvement.

>>
>> The current implementation of the function iterates over a global list of
>> smack_known resulting in O(N) complexity for smk_find_entry().  The total
>> complexity of SMACK initialization becomes O(rules * labels).  Therefore it
>> scales quadratically with a complexity of a system.
>>
>> Applying the patch reduced the complexity of smk_find_entry() to O(1) as long
>> as number of label is in hundreds. If the number of labels is increased please
>> update SMACK_HASH_SLOTS constant defined in security/smack/smack.h. Introducing
>> the configuration of this constant with Kconfig or cmdline might be a good
>> idea.
>>
>> The size of the hash table was adjusted experimentally.  The rule set used by
>> TIZEN contains circa 17K rules for 500 labels.  The table above contains
>> results of SMACK initialization using 'time smackctl apply' bash command.
>> The 'Ref' is a kernel without this patch applied. The consecutive values
>> refers to value of SMACK_HASH_SLOTS.  Every measurement was repeated three
>> times to reduce noise.
>>
>>      |  Ref  |   1   |   2   |   4   |   8   |   16  |   32  |   64  |  128  |  256  |  512
>> --------------------------------------------------------------------------------------------
>> Run1 | 1.156 | 1.096 | 0.883 | 0.764 | 0.692 | 0.667 | 0.649 | 0.633 | 0.634 | 0.629 | 0.620
>> Run2 | 1.156 | 1.111 | 0.885 | 0.764 | 0.694 | 0.661 | 0.649 | 0.651 | 0.634 | 0.638 | 0.623
>> Run3 | 1.160 | 1.107 | 0.886 | 0.764 | 0.694 | 0.671 | 0.661 | 0.638 | 0.631 | 0.624 | 0.638
>> AVG  | 1.157 | 1.105 | 0.885 | 0.764 | 0.693 | 0.666 | 0.653 | 0.641 | 0.633 | 0.630 | 0.627
> 
>                  4%      20%     14%     9%      4%      2%      2%      1%      <1%
> 
> 
> You get 4% by going to the hlist. The improvement is trivial after 16 slots.
> If you have 500 labels and 128 slots that's an average of 4 labels per slot.
> That's an awfully big hash table for so few labels and so little performance
> gain over what you get with 16 slots. Plus, 500 labels is a huge number of
> labels. Most Smack systems should be using far fewer than that. 
> 

Ok. 16 slots might be considered as 'good-enough'.

However, the cost of a single slot is a hash table is only 4 bytes (on ARM).
For example, using 64 slots instead of 16 costs only 4 * (64 - 16) = 196 bytes.
It is a very small value in comparison to other structures used in SMACK.
For example, sizeof(struct smack_rule) == 20. Notice that 32 bytes are consumed
due to kmalloc alignment policy (refer to include/linux/kmalloc_sizes.h).
So the cost is equal to the cost of 6 additional rules.

The performance gain is 4% (for 64 slots compared to 16 slots).
The gain (expressed in percents) will be larger if IO issues in smackctl get resolved.
The additional memory cost for TIZEN case (not including smack_known and other objects) is:
196 / (17k rules * 32 bytes/rule) * 100% = 0.03%

I think that 4% speed for 0.03% memory is a very good trade-off.
Especially as it makes system more resistant if a number of labels somehow
get increased.

Anyway, if you consider 16 to be the best value then 16 is the best value.

Are there any other issues to be fixed in the patch?
Do you think that commit log is a good place for measurement results.
Maybe cover-letter would be a better place?

Regards,
Tomasz Stanislawski

>>
>> Surprisingly, a single hlist is slightly faster than a double-linked list.
>> The speed-up saturates near 64 slots.  Therefore I chose value 128 to provide
>> some margin if more labels were used.
>> It looks that IO becomes a new bottleneck.
>>
>> Signed-off-by: Tomasz Stanislawski <t.stanislaws@xxxxxxxxxxx>
>> ---
>>  security/smack/smack.h        |    5 +++++
>>  security/smack/smack_access.c |   30 +++++++++++++++++++++++++++---
>>  security/smack/smack_lsm.c    |   12 ++++++------
>>  3 files changed, 38 insertions(+), 9 deletions(-)
>>

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/