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
>From 058ebcd0f1ee7a68c14188ab000758199cb2c1ac Mon Sep 17 00:00:00 2001
From: Michal Zidek <mzi...@redhat.com>
Date: Mon, 6 Aug 2012 19:42:08 +0200
Subject: [PATCH] When ldap_group_nesting_level was reached, the LDAP provider
tried to link group members with groups outside nesting
limit.
https://fedorahosted.org/sssd/ticket/1194
---
src/providers/ldap/sdap_async_initgroups.c | 46 +++++++++++++++++++++++++++++-
1 file changed, 45 insertions(+), 1 deletion(-)
diff --git a/src/providers/ldap/sdap_async_initgroups.c b/src/providers/ldap/sdap_async_initgroups.c
index 8a837bc..2cda9c2 100644
--- a/src/providers/ldap/sdap_async_initgroups.c
+++ b/src/providers/ldap/sdap_async_initgroups.c
@@ -1781,7 +1781,14 @@ save_rfc2307bis_group_memberships(struct sdap_initgr_rfc2307bis_state *state)
TALLOC_CTX *tmp_ctx;
struct rfc2307bis_group_memberships_state *membership_state;
struct membership_diff *iter;
+ struct membership_diff *iter_start;
+ struct membership_diff *iter_tmp;
bool in_transaction = false;
+ int num_added;
+ int i;
+ int grp_count;
+ int grp_count_old = 0;
+ char **add = NULL;
tmp_ctx = talloc_new(NULL);
if (!tmp_ctx) return ENOMEM;
@@ -1813,10 +1820,47 @@ save_rfc2307bis_group_memberships(struct sdap_initgr_rfc2307bis_state *state)
}
in_transaction = true;
+ iter_tmp = membership_state->memberships;
+ iter_start = membership_state->memberships;
+
DLIST_FOR_EACH(iter, membership_state->memberships) {
+ /* Create a copy of iter->add array but do not include groups outside
+ * nesting limit. This array must be NULL terminated.
+ */
+ for (grp_count = 0; iter->add[grp_count]; grp_count++);
+ if (grp_count > grp_count_old) {
+ add = talloc_realloc(tmp_ctx, add, char*, grp_count + 1);
+ if (add == NULL) {
+ ret = ENOMEM;
+ goto done;
+ }
+ }
+
+ num_added = 0;
+ for (i = 0; i < grp_count; i++) {
+ DLIST_FOR_EACH(iter_tmp, iter_start) {
+ if (!strcmp(iter_tmp->name,iter->add[i])) {
+ add[num_added] = iter->add[i];
+ num_added++;
+ break;
+ }
+ }
+ }
+
+ /* Swap old and new group counter. */
+ grp_count ^= grp_count_old;
+ grp_count_old ^= grp_count;
+ grp_count ^= grp_count_old;
+
+ if (num_added == 0) {
+ /* Nothing to add. Skip. */
+ continue;
+ } else {
+ add[num_added] = NULL;
+ }
ret = sysdb_update_members(state->sysdb, iter->name,
SYSDB_MEMBER_GROUP,
- (const char *const *) iter->add,
+ (const char *const *) add,
(const char *const *) iter->del);
if (ret != EOK) {
DEBUG(3, ("Failed to update memberships\n"));
--
1.7.11.2
_______________________________________________
sssd-devel mailing list
sssd-devel@lists.fedorahosted.org
https://lists.fedorahosted.org/mailman/listinfo/sssd-devel
