[PATCH] When ldap_group_nesting_level was reached, the LDAP provider, tried to link group members with groups outside nesting, limit.
Now, the groups outside nesting limit are skipped. The patch is attached.
https://fedorahosted.org/sssd/ticket/1194
Michal
On Mon, 2012-08-06 at 20:29 +0200, Michal Zidek wrote:
Now, the groups outside nesting limit are skipped. The patch is attached.
Mnior nitpicks and one important question inline.
From b16c02579bb94d0058cde0f890167cccb47b3899 Mon Sep 17 00:00:00 2001 From: Michal Zidek mzidek@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 | 35 +++++++++++++++++++++++++++++- 1 file changed, 34 insertions(+), 1 deletion(-)
diff --git a/src/providers/ldap/sdap_async_initgroups.c b/src/providers/ldap/sdap_async_initgroups.c index 8a837bc..1cc278d 100644 --- a/src/providers/ldap/sdap_async_initgroups.c +++ b/src/providers/ldap/sdap_async_initgroups.c @@ -1781,7 +1781,13 @@ 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 added;
please use num_added, it will immediately convey this is a counter, as it is it sounds like a boolean but it not.
int i;
int grp_count;
char **add;
tmp_ctx = talloc_new(NULL); if (!tmp_ctx) return ENOMEM;
@@ -1813,15 +1819,42 @@ 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 groupsoutside
* nesting limit. This array must be NULL terminated. */for (grp_count = 0; iter->add[grp_count]; ++grp_count);
In general please use the x++ form not ++x, we use the former everywhere else.
add = talloc_zero_array(tmp_ctx, char*, grp_count + 1);if (add == NULL) {ret = ENOMEM;goto done;}
Zeroing the array is just a waste here, whe you are finished assigning assign all members then just add a NULL for the last one. memset are relatively cheap with optimizations but still no reason to abuse of them when not needed.
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[added] = iter->add[i];++added;break;}}}if (add[0] == NULL) {/* Nothing to add. Skip. */continue;}
This becomes: if (num_added == 0) { continue; } else { add[num_added] = NULL; }
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 ?
Simo.
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?).
I corrected the nitpicks, new patch is attached.
Thanks Michal
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 ?
I corrected the nitpicks, new patch is attached.
Nitpick-wise looks ok.
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.
Also given you have to count it may make sense to pass down the interfaces the number of elements to avoid busy loops just for counting, but I haven't looked at the interface, so if it is a lot of work, please ignore this suggestion for now (feel free to file a ticket if you want).
Simo.
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
On Tue, 2012-08-07 at 19:08 +0200, Michal Zidek wrote:
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.
My motto here would be "Get it right first". If we find out later that it's causing a bottleneck, we'll optimize it later. We don't have any real-world data suggesting that O(n^2) is too slow for this particular operation.
On Tue, 2012-08-07 at 13:15 -0400, Stephen Gallagher wrote:
On Tue, 2012-08-07 at 19:08 +0200, Michal Zidek wrote:
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.
My motto here would be "Get it right first". If we find out later that it's causing a bottleneck, we'll optimize it later. We don't have any real-world data suggesting that O(n^2) is too slow for this particular operation.
Ok, makes sense, and ack to the last incarnation of the patch.
Good work Michal.
Simo.
On 08/07/2012 07:35 PM, Simo Sorce wrote:
On Tue, 2012-08-07 at 13:15 -0400, Stephen Gallagher wrote:
On Tue, 2012-08-07 at 19:08 +0200, Michal Zidek wrote:
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.
My motto here would be "Get it right first". If we find out later that it's causing a bottleneck, we'll optimize it later. We don't have any real-world data suggesting that O(n^2) is too slow for this particular operation.
Ok, makes sense, and ack to the last incarnation of the patch.
Good work Michal.
Simo.
i was instructed to test it, successfull, ack
On Fri, Aug 10, 2012 at 02:00:09PM +0200, Ondrej Kos wrote:
On 08/07/2012 07:35 PM, Simo Sorce wrote:
On Tue, 2012-08-07 at 13:15 -0400, Stephen Gallagher wrote:
On Tue, 2012-08-07 at 19:08 +0200, Michal Zidek wrote:
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.
My motto here would be "Get it right first". If we find out later that it's causing a bottleneck, we'll optimize it later. We don't have any real-world data suggesting that O(n^2) is too slow for this particular operation.
Ok, makes sense, and ack to the last incarnation of the patch.
Good work Michal.
Simo.
i was instructed to test it, successfull, ack
Pushed to master.
Great work finding your way around the nested initgroups code, Michal.
sssd-devel@lists.fedorahosted.org
-
Jakub Hrozek -
Michal Židek -
Ondrej Kos -
Simo Sorce -
Stephen Gallagher