URL: https://github.com/SSSD/sssd/pull/5937
Author: alexey-tikhonov
Title: #5937: [WIP] Another attempt to resolve #5134
Action: opened
PR body:
"""
There are two ideas:
- get rid of re-alloc for every new member added: instead reserve space with a
margin and shrink later.
- don't add every new member to the list immediately: instead keep new members
in a temporarily hash table. This will allow to avoid cross strcmp() at least
among new members - hopefully, hash table should be much faster.
2nd patch actually makes 1st patch obsolete, but I will keep it a while to
measure impact.
This is "WIP" as I didn't conduct perf measurements yet.
"""
To pull the PR as Git branch:
git remote add ghsssd https://github.com/SSSD/sssd
git fetch ghsssd pull/5937/head:pr5937
git checkout pr5937
From 1557e7f31216919c6f7170d6d503927827e95280 Mon Sep 17 00:00:00 2001
From: Alexey Tikhonov <atikh...@redhat.com>
Date: Tue, 28 Dec 2021 23:04:45 +0100
Subject: [PATCH 1/3] SDAP: sdap_nested_group_deref_direct_process(): avoid
realloc for every new member.
Single realloc + shrink are much cheaper.
---
src/providers/ldap/sdap_async_nested_groups.c | 24 ++++++++++++-------
1 file changed, 16 insertions(+), 8 deletions(-)
diff --git a/src/providers/ldap/sdap_async_nested_groups.c b/src/providers/ldap/sdap_async_nested_groups.c
index 2570a00bbd..577353569c 100644
--- a/src/providers/ldap/sdap_async_nested_groups.c
+++ b/src/providers/ldap/sdap_async_nested_groups.c
@@ -2334,6 +2334,15 @@ sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
goto done;
}
+ /* The same with new members: make an assumpation all entries are new
+ and shrink memory later. */
+ members->values = talloc_realloc(members, members->values, struct ldb_val,
+ members->num_values + num_entries);
+ if (members->values == NULL) {
+ ret = ENOMEM;
+ goto done;
+ }
+
PROBE(SDAP_NESTED_GROUP_DEREF_PROCESS_PRE);
for (i = 0; i < num_entries; i++) {
ret = sysdb_attrs_get_string(entries[i]->attrs,
@@ -2362,14 +2371,6 @@ sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
/* Append newly found member to member list.
* Changes in state->members will propagate into sysdb_attrs of
* the group. */
- state->members->values = talloc_realloc(members, members->values,
- struct ldb_val,
- members->num_values + 1);
- if (members->values == NULL) {
- ret = ENOMEM;
- goto done;
- }
-
members->values[members->num_values].data =
(uint8_t *)talloc_strdup(members->values, orig_dn);
if (members->values[members->num_values].data == NULL) {
@@ -2452,6 +2453,13 @@ sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
talloc_zfree(state->nested_groups);
}
+ members->values = talloc_realloc(members, members->values, struct ldb_val,
+ members->num_values);
+ if (members->values == NULL) {
+ ret = ENOMEM;
+ goto done;
+ }
+
ret = EOK;
done:
From 9cf6a1c868de1b91a2f6f038cbb88cde303f0ce2 Mon Sep 17 00:00:00 2001
From: Alexey Tikhonov <atikh...@redhat.com>
Date: Wed, 29 Dec 2021 21:04:26 +0100
Subject: [PATCH 2/3] SDAP: sdap_nested_group_deref_direct_process(): don't add
all new members to the list immediately to avoid cross strcasecmp() amongst
them.
Resolves: https://github.com/SSSD/sssd/issues/5134
---
src/providers/ldap/sdap_async_nested_groups.c | 89 ++++++++++++++-----
1 file changed, 66 insertions(+), 23 deletions(-)
diff --git a/src/providers/ldap/sdap_async_nested_groups.c b/src/providers/ldap/sdap_async_nested_groups.c
index 577353569c..4c89542b12 100644
--- a/src/providers/ldap/sdap_async_nested_groups.c
+++ b/src/providers/ldap/sdap_async_nested_groups.c
@@ -2293,6 +2293,49 @@ sdap_nested_group_deref_send(TALLOC_CTX *mem_ctx,
return req;
}
+static errno_t
+expand_members_list(struct ldb_message_element *members, hash_table_t *addon)
+{
+ struct hash_iter_context_t *iter;
+ hash_entry_t *entry;
+ const char *dn;
+ unsigned long num_new_members = hash_count(addon);
+
+ if (num_new_members == 0) {
+ return EOK;
+ }
+
+ members->values = talloc_realloc(members, members->values, struct ldb_val,
+ members->num_values + num_new_members);
+ if (members->values == NULL) {
+ return ENOMEM;
+ }
+
+ iter = new_hash_iter_context(addon);
+ if (iter == NULL) {
+ return ENOMEM;
+ }
+
+ while ((entry = iter->next(iter)) != NULL) {
+ if (entry->key.type != HASH_KEY_CONST_STRING) {
+ DEBUG(SSSDBG_MINOR_FAILURE,
+ "Unexpected key type = %d\n", entry->key.type);
+ continue;
+ }
+ dn = entry->key.c_str;
+ members->values[members->num_values].data =
+ (uint8_t *)talloc_strdup(members->values, dn);
+ if (members->values[members->num_values].data == NULL) {
+ return ENOMEM;
+ }
+ members->values[members->num_values].length = strlen(dn);
+ members->num_values++;
+ }
+ talloc_free(iter);
+
+ return EOK;
+}
+
static errno_t
sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
{
@@ -2306,6 +2349,9 @@ sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
size_t num_entries = 0;
size_t i, j;
bool member_found;
+ hash_table_t *new_members; /* will be used as a set */
+ hash_key_t key;
+ hash_value_t value;
errno_t ret;
req = tevent_req_callback_data(subreq, struct tevent_req);
@@ -2319,6 +2365,14 @@ sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
goto done;
}
+ ret = sss_hash_create(state, 0, &new_members);
+ if (ret != EOK) {
+ DEBUG(SSSDBG_CRIT_FAILURE, "Unable to create hash table [%d]: %s\n",
+ ret, strerror(ret));
+ new_members = NULL;
+ goto done;
+ }
+
DEBUG(SSSDBG_TRACE_INTERNAL, "Received %zu dereference results, "
"about to process them\n", num_entries);
@@ -2334,15 +2388,6 @@ sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
goto done;
}
- /* The same with new members: make an assumpation all entries are new
- and shrink memory later. */
- members->values = talloc_realloc(members, members->values, struct ldb_val,
- members->num_values + num_entries);
- if (members->values == NULL) {
- ret = ENOMEM;
- goto done;
- }
-
PROBE(SDAP_NESTED_GROUP_DEREF_PROCESS_PRE);
for (i = 0; i < num_entries; i++) {
ret = sysdb_attrs_get_string(entries[i]->attrs,
@@ -2359,7 +2404,6 @@ sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
*/
member_found = false;
for (j = 0; j < members->num_values; j++) {
- /* FIXME: This is inefficient for very large sets of groups */
member_dn = (const char *)members->values[j].data;
if (strcasecmp(orig_dn, member_dn) == 0) {
member_found = true;
@@ -2368,18 +2412,17 @@ sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
}
if (!member_found) {
- /* Append newly found member to member list.
+ /* Store newly found member to append to member list later.
* Changes in state->members will propagate into sysdb_attrs of
* the group. */
- members->values[members->num_values].data =
- (uint8_t *)talloc_strdup(members->values, orig_dn);
- if (members->values[members->num_values].data == NULL) {
- ret = ENOMEM;
- goto done;
+ key.type = HASH_KEY_CONST_STRING;
+ key.c_str = orig_dn;
+ value.type = HASH_VALUE_UNDEF;
+ ret = hash_enter(new_members, &key, &value);
+ if (ret != HASH_SUCCESS) {
+ DEBUG(SSSDBG_CRIT_FAILURE,
+ "Failed to add '%s' to member list\n", orig_dn);
}
-
- members->values[members->num_values].length = strlen(orig_dn);
- members->num_values++;
}
if (entries[i]->map == opts->user_map) {
@@ -2453,16 +2496,16 @@ sdap_nested_group_deref_direct_process(struct tevent_req *subreq)
talloc_zfree(state->nested_groups);
}
- members->values = talloc_realloc(members, members->values, struct ldb_val,
- members->num_values);
- if (members->values == NULL) {
- ret = ENOMEM;
+ ret = expand_members_list(members, new_members);
+ if (ret != EOK) {
+ DEBUG(SSSDBG_CRIT_FAILURE, "expand_members_list() failed: %d\n", ret);
goto done;
}
ret = EOK;
done:
+ hash_destroy(new_members);
return ret;
}
From a0d2a0bbc1003402c36a58e831da3de3e24927f5 Mon Sep 17 00:00:00 2001
From: Alexey Tikhonov <atikh...@redhat.com>
Date: Wed, 29 Dec 2021 21:21:33 +0100
Subject: [PATCH 3/3] SDAP: sdap_nested_group_hash_insert(): don't create key
copy - hash_enter() takes care of this.
---
src/providers/ldap/sdap_async_nested_groups.c | 8 +-------
1 file changed, 1 insertion(+), 7 deletions(-)
diff --git a/src/providers/ldap/sdap_async_nested_groups.c b/src/providers/ldap/sdap_async_nested_groups.c
index 4c89542b12..16e1658991 100644
--- a/src/providers/ldap/sdap_async_nested_groups.c
+++ b/src/providers/ldap/sdap_async_nested_groups.c
@@ -209,13 +209,9 @@ static errno_t sdap_nested_group_hash_insert(hash_table_t *table,
entry_key, table_name);
key.type = HASH_KEY_STRING;
- key.str = talloc_strdup(NULL, entry_key);
- if (key.str == NULL) {
- return ENOMEM;
- }
+ key.c_str = discard_const(entry_key); /* hash_enter() will make a copy */
if (overwrite == false && hash_has_key(table, &key)) {
- talloc_free(key.str);
return EEXIST;
}
@@ -224,11 +220,9 @@ static errno_t sdap_nested_group_hash_insert(hash_table_t *table,
hret = hash_enter(table, &key, &value);
if (hret != HASH_SUCCESS) {
- talloc_free(key.str);
return EIO;
}
- talloc_steal(table, key.str);
talloc_steal(table, value.ptr);
return EOK;
_______________________________________________
sssd-devel mailing list -- sssd-devel@lists.fedorahosted.org
To unsubscribe send an email to sssd-devel-le...@lists.fedorahosted.org
Fedora Code of Conduct:
https://docs.fedoraproject.org/en-US/project/code-of-conduct/
List Guidelines: https://fedoraproject.org/wiki/Mailing_list_guidelines
List Archives:
https://lists.fedorahosted.org/archives/list/sssd-devel@lists.fedorahosted.org
Do not reply to spam on the list, report it:
https://pagure.io/fedora-infrastructure
