[autobackport: sssd-2-9] sdap: eliminate O(N^2) loop in sdap_add_incomplete_groups()#8477
Conversation
![gemini-code-assist[bot]](https://avatars.githubusercontent.com/in/956858?s=60&v=4){kind=small}
There was a problem hiding this comment.
Code Review
The pull request successfully eliminates the sdap_add_incomplete_groups() by iterating directly over the LDAP attributes instead of matching names back to attributes. This provides a significant performance boost for users with many group memberships. However, the current implementation introduces a regression in domain detection for multi-domain environments (like AD Global Catalog) and a memory leak within the processing loop. These issues should be addressed to ensure correctness and maintain efficiency.
| ret = sysdb_search_group_by_name(tmp_ctx, subdomain, groupname, | ||
| NULL, &msg); | ||
| if (ret == EOK) { | ||
| continue; | ||
| } else if (ret == ENOENT) { | ||
| missing[mi] = talloc_strdup(missing, sysdb_groupnames[i]); | ||
| DEBUG(SSSDBG_TRACE_LIBS, "Group #%d [%s][%s] is not cached, " \ | ||
| "need to add a fake entry\n", | ||
| i, sysdb_groupnames[i], missing[mi]); | ||
| mi++; | ||
| continue; | ||
| } else if (ret != ENOENT) { | ||
| DEBUG(SSSDBG_CRIT_FAILURE, "search for group failed [%d]: %s\n", | ||
| ret, strerror(ret)); | ||
| DEBUG(SSSDBG_CRIT_FAILURE, | ||
| "search for group failed [%d]: %s\n", | ||
| ret, strerror(ret)); | ||
| goto done; | ||
| } |
There was a problem hiding this comment.
There is a memory leak in the loop. The msg structure returned by sysdb_search_group_by_name is allocated on tmp_ctx but is not freed when the group is already cached (the continue path) or after it is determined that the group is missing. In a scenario with 5,000 groups, this can lead to significant unnecessary memory accumulation during the function's execution.
ret = sysdb_search_group_by_name(tmp_ctx, subdomain, groupname,
NULL, &msg);
if (ret == EOK) {
talloc_zfree(msg);
continue;
} else if (ret != ENOENT) {
DEBUG(SSSDBG_CRIT_FAILURE,
"search for group failed [%d]: %s\n",
ret, strerror(ret));
goto done;
}
talloc_zfree(msg);
There was a problem hiding this comment.
This is valid.
Moreover, taking into account msg value isn't actually used - code only cares about sysdb_search_group_by_name() ret code - maybe it's worth introducing a new helper function in sysdb to check object presence, but to avoid mem allocations.
Nonetheless, since this is a backport PR, I'd prefer to do this a new, separate PR, rather than diverging original and backport PRs.
There was a problem hiding this comment.
maybe it's worth introducing a new helper function in sysdb to check object presence
I tried this - #8482 - and didn't see any meaningful perf improvements.
sumit-bose
left a comment
sumit-bose
left a comment
There was a problem hiding this comment.
Hi,
original and backport matches, ACK.
bye,
Sumit
alexey-tikhonov
added
no-backport
`sdap_add_incomplete_groups()` had two separate steps: first it iterated the group name list checking each against sysdb to build a 'missing' list, then for each missing group it scanned the entire 'ldap_groups' array calling to find matching LDAP attributes. This resulted in O(N^2) behavior when all groups were missing (i.e. empty cache). Replace this with a single O(N) loop that iterates 'ldap_groups' directly: check sysdb, and if missing create the incomplete entry immediately. The 'sysdb_groupnames' parameter is removed as it is not used anymore. This patch also has an interesting side effect: it also makes `sysdb_update_members()` executed in the `sdap_initgr_common_store()` after `sdap_add_incomplete_groups()` faster. Most probably this is because previosuly O(N^2) allocations of `groupname` (by `sdap_get_group_primary_name()`) trashed memory, purging ldb/tdb data from the cache. Implementation assisted-by: Claude Code (Opus 4.6) Reviewed-by: Justin Stephenson <[email protected]> Reviewed-by: Sumit Bose <[email protected]> (cherry picked from commit f91c7bb)
|
The pull request was accepted by @alexey-tikhonov with the following PR CI status: 🟢 CodeQL (success) There are unsuccessful or unfinished checks. Make sure that the failures are not related to this pull request before merging. |
7abb017 to
32aa87e
Compare
4 participants
This is an automatic backport of PR#8454 sdap: eliminate O(N^2) loop in
sdap_add_incomplete_groups()to branch sssd-2-9, created by @alexey-tikhonov.Please make sure this backport is correct.
Note
The commits were cherry-picked without conflicts.
You can push changes to this pull request
Original commits
f91c7bb - sdap: eliminate O(N^2) loop in
sdap_add_incomplete_groups()Backported commits
sdap_add_incomplete_groups()Original Pull Request Body
Those patch is based on a profiling of a following test case:
tu1is a member of 5k LDAP groups (RFC2307 case, no nested groups)time id [email protected] | tr ',' '\n' | wc -lis executedThis patch provides a x2 performance gain for described test case on a laptop. See commit message for details.