[SSSD] [PATCH] When ldap_group_nesting_level was reached, the LDAP provider, tried to link group members with groups outside nesting, limit.

Michal Zidek mzidek at redhat.com
Tue Aug 7 17:08:17 UTC 2012


On 08/07/2012 04:11 PM, Simo Sorce wrote:
> On Tue, 2012-08-07 at 15:40 +0200, Michal Zidek wrote:
>> On 08/06/2012 08:57 PM, Simo Sorce wrote:
>>> The major question I have is that this new code introduces O(N^2)
>>> behavior, if there are more then a handful of groups it will be quite
>>> costly. Can we find a way that is not so expensive ?
>> I think this is not a big problem. If I understand the code correctly,
>> the inner cycle only iterates through potential direct parent groups (we
>> add group member to them later) and it is unlikely to be a big number in
>> real scenarios (Or am I wrong? Is it common that a group has so many
>> direct parents that it would be expensive?).
> On what data do you base your assertion about probability, not saying
> you are wrong, but is it a gut feeling or do you have actual data ?
>

It is just my feeling. Database with many groups where each has few 
DIRECT parents sounds OK, but
many groups with many direct parents sound like a mess to me. But maybe 
I am wrong, I tested it only
on a very small test database. If you have a large test database with 
complex group hierarchy, you could
test how much time sssd_be spends in this loops.

Another thing to consider is that this process only takes place when the 
information about group
memberships can not be retrieved from local cache.

> You may want to add a talloc_free(add); before the continue; but you 
> could get even more gains if you instead of freeing the add array at 
> each loop always just realloc it if grp_count is > than the previous 
> grp_count. Allocations tend to be expensive and here you can spare a 
> lot of allocation given you always leave the array in consistent state 
> by adding the terminating NULL.

Good idea, I rewrote it using the talloc_realloc. Updated patch attached.

Thanks
Michal
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-When-ldap_group_nesting_level-was-reached-the-LDAP-p.patch
Type: text/x-patch
Size: 3038 bytes
Desc: not available
URL: <https://lists.fedorahosted.org/pipermail/sssd-devel/attachments/20120807/de0d5637/attachment.bin>


More information about the sssd-devel mailing list