LDAP: Use the IPA provider interface to resolve external group members

Resolves:
    https://fedorahosted.org/sssd/ticket/2522

Currently the approach is not optimized for performance, because each
external member is resolved in a full transaction to make sure even ID
views and similar information is processed.

In future, we should implement https://fedorahosted.org/sssd/ticket/2943
we will again be able to process all the data in a single transaction.

Reviewed-by: Sumit Bose <sbose@redhat.com>

3 files changed, 654 insertions, 28 deletions

diff --git a/src/providers/ldap/sdap_async_groups.c b/src/providers/ldap/sdap_async_groups.c
index 75bfa413d..3ccf7deb5 100644
--- a/src/providers/ldap/sdap_async_groups.c
+++ b/src/providers/ldap/sdap_async_groups.c
@@ -1758,6 +1758,7 @@ struct sdap_get_groups_state {
     struct sysdb_attrs **groups;
     size_t count;
     size_t check_count;
+    hash_table_t *missing_external;
 
     hash_table_t *user_hash;
     hash_table_t *group_hash;
@@ -2333,6 +2334,8 @@ int sdap_get_groups_recv(struct tevent_req *req,
     return EOK;
 }
 
+static void sdap_nested_ext_done(struct tevent_req *subreq);
+
 static void sdap_nested_done(struct tevent_req *subreq)
 {
     errno_t ret, tret;
@@ -2348,7 +2351,8 @@ static void sdap_nested_done(struct tevent_req *subreq)
                                             struct sdap_get_groups_state);
 
     ret = sdap_nested_group_recv(state, subreq, &user_count, &users,
-                                 &group_count, &groups);
+                                 &group_count, &groups,
+                                 &state->missing_external);
     talloc_zfree(subreq);
     if (ret != EOK) {
         DEBUG(SSSDBG_CRIT_FAILURE, "Nested group processing failed: [%d][%s]\n",
@@ -2387,8 +2391,25 @@ static void sdap_nested_done(struct tevent_req *subreq)
     }
     in_transaction = false;
 
-    /* Processing complete */
-    tevent_req_done(req);
+    if (hash_count(state->missing_external) == 0) {
+        /* No external members. Processing complete */
+        DEBUG(SSSDBG_TRACE_INTERNAL, "No external members, done");
+        tevent_req_done(req);
+        return;
+    }
+
+    /* At the moment, we need to save the direct groups & members in one
+     * transaction and then query the others in a separate requests
+     */
+    subreq = sdap_nested_group_lookup_external_send(state, state->ev,
+                                                    state->dom,
+                                                    state->opts->ext_ctx,
+                                                    state->missing_external);
+    if (subreq == NULL) {
+        ret = ENOMEM;
+        goto fail;
+    }
+    tevent_req_set_callback(subreq, sdap_nested_ext_done, req);
     return;
 
 fail:
@@ -2401,6 +2422,28 @@ fail:
     tevent_req_error(req, ret);
 }
 
+static void sdap_nested_ext_done(struct tevent_req *subreq)
+{
+    errno_t ret;
+    struct tevent_req *req = tevent_req_callback_data(subreq,
+                                                      struct tevent_req);
+    struct sdap_get_groups_state *state = tevent_req_data(req,
+                                            struct sdap_get_groups_state);
+
+    ret = sdap_nested_group_lookup_external_recv(state, subreq);
+    talloc_free(subreq);
+    if (ret != EOK) {
+        DEBUG(SSSDBG_OP_FAILURE,
+              "Cannot resolve external members [%d]: %s\n",
+              ret, sss_strerror(ret));
+        tevent_req_error(req, ret);
+        return;
+    }
+
+    tevent_req_done(req);
+    return;
+}
+
 static errno_t sdap_nested_group_populate_users(TALLOC_CTX *mem_ctx,
                                                 struct sysdb_ctx *sysdb,
                                                 struct sss_domain_info *domain,
diff --git a/src/providers/ldap/sdap_async_nested_groups.c b/src/providers/ldap/sdap_async_nested_groups.c
index 9d7152252..f0d04fa09 100644
--- a/src/providers/ldap/sdap_async_nested_groups.c
+++ b/src/providers/ldap/sdap_async_nested_groups.c
@@ -56,6 +56,13 @@ struct sdap_nested_group_member {
     const char *group_filter;
 };
 
+const size_t external_members_chunk = 16;
+
+struct sdap_external_missing_member {
+    const char **parent_group_dns;
+    size_t parent_dn_idx;
+};
+
 struct sdap_nested_group_ctx {
     struct sss_domain_info *domain;
     struct sdap_options *opts;
@@ -64,6 +71,7 @@ struct sdap_nested_group_ctx {
     struct sdap_handle *sh;
     hash_table_t *users;
     hash_table_t *groups;
+    hash_table_t *missing_external;
     bool try_deref;
     int deref_treshold;
     int max_nesting_level;
@@ -184,37 +192,32 @@ done:
     return ret;
 }
 
-static errno_t sdap_nested_group_hash_entry(hash_table_t *table,
-                                            struct sysdb_attrs *entry,
-                                            const char *table_name)
+static errno_t sdap_nested_group_hash_insert(hash_table_t *table,
+                                             const char *entry_key,
+                                             void *entry_value,
+                                             bool overwrite,
+                                             const char *table_name)
 {
     hash_key_t key;
     hash_value_t value;
-    const char *name = NULL;
-    errno_t ret;
     int hret;
 
-    ret = sysdb_attrs_get_string(entry, SYSDB_ORIG_DN, &name);
-    if (ret != EOK) {
-        return ret;
-    }
-
     DEBUG(SSSDBG_TRACE_ALL, "Inserting [%s] into hash table [%s]\n",
-                             name, table_name);
+                             entry_key, table_name);
 
     key.type = HASH_KEY_STRING;
-    key.str = talloc_strdup(NULL, name);
+    key.str = talloc_strdup(NULL, entry_key);
     if (key.str == NULL) {
         return ENOMEM;
     }
 
-    if (hash_has_key(table, &key)) {
+    if (overwrite == false && hash_has_key(table, &key)) {
         talloc_free(key.str);
         return EEXIST;
     }
 
     value.type = HASH_VALUE_PTR;
-    value.ptr = entry;
+    value.ptr = entry_value;
 
     hret = hash_enter(table, &key, &value);
     if (hret != HASH_SUCCESS) {
@@ -228,6 +231,21 @@ static errno_t sdap_nested_group_hash_entry(hash_table_t *table,
     return EOK;
 }
 
+static errno_t sdap_nested_group_hash_entry(hash_table_t *table,
+                                            struct sysdb_attrs *entry,
+                                            const char *table_name)
+{
+    const char *name = NULL;
+    errno_t ret;
+
+    ret = sysdb_attrs_get_string(entry, SYSDB_ORIG_DN, &name);
+    if (ret != EOK) {
+        return ret;
+    }
+
+    return sdap_nested_group_hash_insert(table, name, entry, false, table_name);
+}
+
 static errno_t
 sdap_nested_group_hash_user(struct sdap_nested_group_ctx *group_ctx,
                             struct sysdb_attrs *user)
@@ -297,6 +315,76 @@ sdap_nested_group_hash_group(struct sdap_nested_group_ctx *group_ctx,
     return sdap_nested_group_hash_entry(group_ctx->groups, group, "groups");
 }
 
+static errno_t sdap_nested_group_external_add(hash_table_t *table,
+                                              const char *ext_member,
+                                              const char *parent_group_dn)
+{
+    hash_key_t key;
+    hash_value_t value;
+    int hret;
+    int ret;
+    struct sdap_external_missing_member *ext_mem;
+
+    key.type = HASH_KEY_STRING;
+    key.str = discard_const(ext_member);
+
+    DEBUG(SSSDBG_TRACE_ALL,
+          "Inserting external member [%s] into external members hash table\n",
+          ext_member);
+
+    hret = hash_lookup(table, &key, &value);
+    switch (hret) {
+    case HASH_ERROR_KEY_NOT_FOUND:
+        ext_mem = talloc_zero(table, struct sdap_external_missing_member);
+        if (ext_mem == NULL) {
+            return ENOMEM;
+        }
+        ext_mem->parent_group_dns = talloc_zero_array(ext_mem,
+                                                      const char *,
+                                                      external_members_chunk);
+        if (ext_mem->parent_group_dns == NULL) {
+            talloc_free(ext_mem);
+            return ENOMEM;
+        }
+
+        ret = sdap_nested_group_hash_insert(table, ext_member, ext_mem,
+                                            true, "missing external users");
+        if (ret != EOK) {
+            return ret;
+        }
+        break;
+
+    case HASH_SUCCESS:
+        ext_mem = talloc_get_type(value.ptr,
+                                  struct sdap_external_missing_member);
+        if (ext_mem->parent_dn_idx == \
+                talloc_array_length(ext_mem->parent_group_dns)) {
+            ext_mem->parent_group_dns = talloc_realloc(ext_mem,
+                                                ext_mem->parent_group_dns,
+                                                const char *,
+                                                ext_mem->parent_dn_idx + \
+                                                    external_members_chunk);
+            if (ext_mem->parent_group_dns == NULL) {
+                talloc_free(ext_mem);
+                return ENOMEM;
+            }
+        }
+        break;
+    default:
+        return EIO;
+    }
+
+    ext_mem->parent_group_dns[ext_mem->parent_dn_idx] = \
+                                        talloc_strdup(ext_mem->parent_group_dns,
+                                                      parent_group_dn);
+    if (ext_mem->parent_group_dns[ext_mem->parent_dn_idx] == NULL) {
+        return ENOMEM;
+    }
+    ext_mem->parent_dn_idx++;
+
+    return EOK;
+}
+
 static errno_t sdap_nested_group_sysdb_search(struct sss_domain_info *domain,
                                               const char *filter,
                                               bool user)
@@ -478,6 +566,13 @@ sdap_nested_group_split_members(TALLOC_CTX *mem_ctx,
     errno_t ret;
     int i;
 
+    if (members == NULL) {
+        *_missing = NULL;
+        *_num_missing = 0;
+        *_num_groups = 0;
+        return EOK;
+    }
+
     tmp_ctx = talloc_new(NULL);
     if (tmp_ctx == NULL) {
         DEBUG(SSSDBG_CRIT_FAILURE, "talloc_new() failed\n");
@@ -619,6 +714,65 @@ done:
     return ret;
 }
 
+static errno_t
+sdap_nested_group_add_ext_members(TALLOC_CTX *mem_ctx,
+                                  struct sdap_nested_group_ctx *group_ctx,
+                                  struct sysdb_attrs *group,
+                                  struct ldb_message_element *ext_members)
+{
+    errno_t ret;
+    const char *ext_member_attr;
+    const char *orig_dn;
+
+    if (ext_members == NULL) {
+        return EOK;
+    }
+
+    ret = sysdb_attrs_get_string(group, SYSDB_ORIG_DN, &orig_dn);
+    if (ret != EOK) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "A group with no originalDN!?!\n");
+        return ret;
+    }
+
+    for (size_t i = 0; i < ext_members->num_values; i++) {
+        ext_member_attr = (const char *) ext_members->values[i].data;
+
+        ret = sdap_nested_group_external_add(group_ctx->missing_external,
+                                             ext_member_attr,
+                                             orig_dn);
+        if (ret != EOK) {
+            DEBUG(SSSDBG_CRIT_FAILURE,
+                    "Cannot add %s into external members [%d]: %s\n",
+                    ext_member_attr, ret, sss_strerror(ret));
+            return ret;
+        }
+    }
+
+    return EOK;
+}
+
+static struct ldb_message_element *
+sdap_nested_group_ext_members(struct sdap_options *opts,
+                              struct sysdb_attrs *group)
+{
+    errno_t ret;
+    struct ldb_message_element *ext_members = NULL;
+
+    if (opts->ext_ctx == NULL) {
+        return NULL;
+    }
+
+    ret = sysdb_attrs_get_el_ext(group,
+                 opts->group_map[SDAP_AT_GROUP_EXT_MEMBER].sys_name,
+                 false, &ext_members);
+    if (ret != EOK && ret != ENOENT) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "Unable to retrieve external member list "
+                                   "[%d]: %s\n", ret, sss_strerror(ret));
+    }
+
+    return ext_members;
+}
+
 
 struct sdap_nested_group_state {
     struct sdap_nested_group_ctx *group_ctx;
@@ -667,6 +821,14 @@ sdap_nested_group_send(TALLOC_CTX *mem_ctx,
         goto immediately;
     }
 
+    ret = sss_hash_create(state->group_ctx, 32,
+                          &state->group_ctx->missing_external);
+    if (ret != EOK) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "Unable to create hash table [%d]: %s\n",
+                                    ret, strerror(ret));
+        goto immediately;
+    }
+
     state->group_ctx->try_deref = true;
     state->group_ctx->deref_treshold = dp_opt_get_int(opts->basic,
                                                       SDAP_DEREF_THRESHOLD);
@@ -760,7 +922,8 @@ errno_t sdap_nested_group_recv(TALLOC_CTX *mem_ctx,
                                unsigned long *_num_users,
                                struct sysdb_attrs ***_users,
                                unsigned long *_num_groups,
-                               struct sysdb_attrs ***_groups)
+                               struct sysdb_attrs ***_groups,
+                               hash_table_t **_missing_external)
 {
     struct sdap_nested_group_state *state = NULL;
     struct sysdb_attrs **users = NULL;
@@ -807,6 +970,11 @@ errno_t sdap_nested_group_recv(TALLOC_CTX *mem_ctx,
         *_groups = talloc_steal(mem_ctx, groups);
     }
 
+    if (_missing_external) {
+        *_missing_external = talloc_steal(mem_ctx,
+                                          state->group_ctx->missing_external);
+    }
+
     return EOK;
 }
 
@@ -816,6 +984,7 @@ struct sdap_nested_group_process_state {
     struct sdap_nested_group_member *missing;
     int num_missing_total;
     int num_missing_groups;
+    struct ldb_message_element *ext_members;
     int nesting_level;
     char *group_dn;
     bool deref;
@@ -866,13 +1035,16 @@ sdap_nested_group_process_send(TALLOC_CTX *mem_ctx,
 
     DEBUG(SSSDBG_TRACE_INTERNAL, "About to process group [%s]\n", orig_dn);
 
-    /* get member list */
+    /* get member list, both direct and external */
+    state->ext_members = sdap_nested_group_ext_members(state->group_ctx->opts,
+                                                       group);
+
     ret = sysdb_attrs_get_el_ext(group, group_map[SDAP_AT_GROUP_MEMBER].sys_name,
                                  false, &members);
-    if (ret == ENOENT) {
-        ret = EOK; /* no members */
+    if (ret == ENOENT && state->ext_members == NULL) {
+        ret = EOK; /* no members, direct or external */
         goto immediately;
-    } else if (ret != EOK) {
+    } else if (ret != EOK && ret != ENOENT) {
         DEBUG(SSSDBG_CRIT_FAILURE, "Unable to retrieve member list "
                                     "[%d]: %s\n", ret, strerror(ret));
         goto immediately;
@@ -890,14 +1062,31 @@ sdap_nested_group_process_send(TALLOC_CTX *mem_ctx,
         goto immediately;
     }
 
-    DEBUG(SSSDBG_TRACE_INTERNAL, "Looking up %d/%d members of group [%s]\n",
-          state->num_missing_total, members->num_values, orig_dn);
+    ret = sdap_nested_group_add_ext_members(state,
+                                            state->group_ctx,
+                                            group,
+                                            state->ext_members);
+    if (ret != EOK) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "Unable to split external member list "
+                                    "[%d]: %s\n", ret, sss_strerror(ret));
+        goto immediately;
+    }
 
-    if (state->num_missing_total == 0) {
+    if (state->num_missing_total == 0
+            && hash_count(state->group_ctx->missing_external) == 0) {
         ret = EOK; /* we're done */
         goto immediately;
     }
 
+    /* If there are only indirect members of the group, it's still safe to
+     * proceed and let the direct lookup code just fall through.
+     */
+
+    DEBUG(SSSDBG_TRACE_INTERNAL, "Looking up %d/%d members of group [%s]\n",
+                                 state->num_missing_total,
+                                 members ? members->num_values : 0,
+                                 orig_dn);
+
     /* process members */
     if (group_ctx->try_deref
             && state->num_missing_total > group_ctx->deref_treshold) {
@@ -2268,3 +2457,385 @@ static errno_t sdap_nested_group_deref_recv(struct tevent_req *req)
 
     return EOK;
 }
+
+struct sdap_ext_member {
+    struct sdap_external_missing_member *missing_mem;
+    const char *ext_member_attr;
+
+    enum sysdb_member_type member_type;
+    struct sss_domain_info *dom;
+    struct sysdb_attrs *attrs;
+};
+
+struct sdap_nested_group_lookup_external_state {
+    struct tevent_context *ev;
+    struct sdap_ext_member_ctx *ext_ctx;
+    struct sss_domain_info *group_dom;
+    hash_table_t *missing_external;
+
+    hash_entry_t *entries;
+    unsigned long n_entries;
+    unsigned long eniter;
+
+    struct sdap_ext_member *ext_members;
+
+    ext_member_send_fn_t ext_member_resolve_send;
+    ext_member_recv_fn_t ext_member_resolve_recv;
+};
+
+static errno_t
+sdap_nested_group_lookup_external_step(struct tevent_req *req);
+static void
+sdap_nested_group_lookup_external_done(struct tevent_req *subreq);
+static errno_t
+sdap_nested_group_lookup_external_link(struct tevent_req *req);
+static errno_t
+sdap_nested_group_lookup_external_link_member(
+                        struct sdap_nested_group_lookup_external_state *state,
+                        struct sdap_ext_member *member);
+static errno_t
+sdap_nested_group_memberof_dn_by_original_dn(
+                            TALLOC_CTX *mem_ctx,
+                            struct sss_domain_info *group_dom,
+                            const char *original_dn,
+                            const char ***_parents);
+
+struct tevent_req *
+sdap_nested_group_lookup_external_send(TALLOC_CTX *mem_ctx,
+                                       struct tevent_context *ev,
+                                       struct sss_domain_info *group_dom,
+                                       struct sdap_ext_member_ctx *ext_ctx,
+                                       hash_table_t *missing_external)
+{
+    struct sdap_nested_group_lookup_external_state *state = NULL;
+    struct tevent_req *req = NULL;
+    errno_t ret;
+
+    req = tevent_req_create(mem_ctx, &state,
+                            struct sdap_nested_group_lookup_external_state);
+    if (req == NULL) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "tevent_req_create() failed\n");
+        return NULL;
+    }
+
+    state->ev = ev;
+    state->group_dom = group_dom;
+    state->ext_ctx = ext_ctx;
+    state->missing_external = missing_external;
+
+    if (state->ext_ctx->ext_member_resolve_send == NULL
+            || state->ext_ctx->ext_member_resolve_recv == NULL) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "Wrong private context\n");
+        ret = EINVAL;
+        goto immediately;
+    }
+
+    ret = hash_entries(state->missing_external,
+                       &state->n_entries, &state->entries);
+    if (ret != HASH_SUCCESS) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "hash_entries returned %d\n", ret);
+        ret = EIO;
+        goto immediately;
+    }
+    state->eniter = 0;
+
+    state->ext_members = talloc_zero_array(state,
+                                           struct sdap_ext_member,
+                                           state->n_entries);
+    if (state->ext_members == NULL) {
+        ret = ENOMEM;
+        goto immediately;
+    }
+
+    ret = sdap_nested_group_lookup_external_step(req);
+    if (ret != EAGAIN) {
+        goto immediately;
+    }
+
+    return req;
+
+immediately:
+    if (ret == EOK) {
+        tevent_req_done(req);
+    } else {
+        tevent_req_error(req, ret);
+    }
+    tevent_req_post(req, ev);
+    return req;
+}
+
+static errno_t
+sdap_nested_group_lookup_external_step(struct tevent_req *req)
+{
+    struct tevent_req *subreq = NULL;
+    struct sdap_nested_group_lookup_external_state *state = NULL;
+    state = tevent_req_data(req,
+                            struct sdap_nested_group_lookup_external_state);
+
+    subreq = state->ext_ctx->ext_member_resolve_send(state,
+                                        state->ev,
+                                        state->entries[state->eniter].key.str,
+                                        state->ext_ctx->pvt);
+    if (subreq == NULL) {
+        return ENOMEM;
+    }
+    DEBUG(SSSDBG_TRACE_FUNC, "Refreshing member %lu/%lu\n",
+                             state->eniter, state->n_entries);
+    tevent_req_set_callback(subreq,
+                            sdap_nested_group_lookup_external_done,
+                            req);
+
+    return EAGAIN;
+}
+
+static void
+sdap_nested_group_lookup_external_done(struct tevent_req *subreq)
+{
+    errno_t ret;
+    struct tevent_req *req = NULL;
+    struct sdap_nested_group_lookup_external_state *state = NULL;
+    enum sysdb_member_type member_type;
+    struct sysdb_attrs *member;
+    struct sss_domain_info *member_dom;
+
+    req = tevent_req_callback_data(subreq, struct tevent_req);
+    state = tevent_req_data(req,
+                            struct sdap_nested_group_lookup_external_state);
+
+    ret = state->ext_ctx->ext_member_resolve_recv(state, subreq,
+                                                  &member_type,
+                                                  &member_dom,
+                                                  &member);
+    talloc_free(subreq);
+    if (ret == EOK) {
+        DEBUG(SSSDBG_TRACE_FUNC, "Refreshing member %lu\n", state->eniter);
+        state->ext_members[state->eniter].missing_mem = \
+                                    state->entries[state->eniter].value.ptr;
+        state->ext_members[state->eniter].dom = member_dom;
+
+        state->ext_members[state->eniter].ext_member_attr = \
+                        talloc_steal(state->ext_members,
+                                     state->entries[state->eniter].key.str);
+        state->ext_members[state->eniter].member_type = member_type;
+        state->ext_members[state->eniter].attrs = \
+                            talloc_steal(state->ext_members, member);
+    }
+
+    state->eniter++;
+    if (state->eniter >= state->n_entries) {
+        DEBUG(SSSDBG_TRACE_FUNC, "All external members processed\n");
+        ret = sdap_nested_group_lookup_external_link(req);
+        if (ret != EOK) {
+            tevent_req_error(req, ret);
+            return;
+        }
+        tevent_req_done(req);
+        return;
+    }
+
+    ret = sdap_nested_group_lookup_external_step(req);
+    if (ret != EOK && ret != EAGAIN) {
+        tevent_req_error(req, ret);
+        return;
+    }
+
+    return;
+}
+
+static errno_t
+sdap_nested_group_lookup_external_link(struct tevent_req *req)
+{
+    errno_t ret, tret;
+    bool in_transaction = false;
+    struct sdap_nested_group_lookup_external_state *state = NULL;
+    state = tevent_req_data(req,
+                            struct sdap_nested_group_lookup_external_state);
+
+    ret = sysdb_transaction_start(state->group_dom->sysdb);
+    if (ret != EOK) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "Failed to start transaction\n");
+        goto fail;
+    }
+    in_transaction = true;
+
+
+    for (size_t i = 0; i < state->eniter; i++) {
+        if (state->ext_members[i].attrs == NULL) {
+            DEBUG(SSSDBG_MINOR_FAILURE, "The member %s could not be resolved\n",
+                                        state->ext_members[i].ext_member_attr);
+            continue;
+        }
+
+        ret = sdap_nested_group_lookup_external_link_member(state,
+                                                    &state->ext_members[i]);
+        if (ret != EOK) {
+            goto fail;
+        }
+    }
+
+    ret = sysdb_transaction_commit(state->group_dom->sysdb);
+    if (ret != EOK) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "Failed to commit transaction\n");
+        goto fail;
+    }
+    in_transaction = false;
+
+    return EOK;
+
+fail:
+    if (in_transaction) {
+        tret = sysdb_transaction_cancel(state->group_dom->sysdb);
+        if (tret != EOK) {
+            DEBUG(SSSDBG_CRIT_FAILURE, "Failed to cancel transaction\n");
+        }
+    }
+    return EFAULT;
+}
+
+static errno_t
+sdap_nested_group_lookup_external_link_member(
+                        struct sdap_nested_group_lookup_external_state *state,
+                        struct sdap_ext_member *member)
+{
+    const char *name;
+    int ret;
+    const char **parents = NULL;
+    size_t i;
+    TALLOC_CTX *tmp_ctx;
+    const char *orig_dn;
+
+    tmp_ctx = talloc_new(state);
+    if (tmp_ctx == NULL) {
+        return ENOMEM;
+    }
+
+    ret = sysdb_attrs_get_string(member->attrs, SYSDB_NAME, &name);
+    if (ret != EOK) {
+        DEBUG(SSSDBG_CRIT_FAILURE, "No name for a user\n");
+        goto done;
+    }
+
+    /* This only works because the groups were saved in a previous
+     * transaction */
+    for (i=0; i < member->missing_mem->parent_dn_idx; i++) {
+        orig_dn = member->missing_mem->parent_group_dns[i];
+        DEBUG(SSSDBG_TRACE_INTERNAL,
+              "Linking external members %s from domain %s to parents of %s\n",
+              name, member->dom->name, orig_dn);
+        ret = sdap_nested_group_memberof_dn_by_original_dn(tmp_ctx,
+                                                           state->group_dom,
+                                                           orig_dn,
+                                                           &parents);
+        if (ret != EOK) {
+            DEBUG(SSSDBG_MINOR_FAILURE,
+                  "Cannot find parents of %s\n", orig_dn);
+            continue;
+        }
+
+        /* We don't have to remove the members here, since all members attributes
+         * are always written anew
+         */
+        ret = sysdb_update_members_dn(member->dom, name, member->member_type,
+                                      parents, NULL);
+        if (ret != EOK) {
+            DEBUG(SSSDBG_CRIT_FAILURE, "Cannot link %s@%s to its parents\n",
+                                       name, member->dom->name);
+            goto done;
+        }
+
+    }
+
+    ret = EOK;
+done:
+    talloc_free(tmp_ctx);
+    return ret;
+}
+
+static errno_t
+sdap_nested_group_memberof_dn_by_original_dn(
+                            TALLOC_CTX *mem_ctx,
+                            struct sss_domain_info *group_dom,
+                            const char *original_dn,
+                            const char ***_parents)
+{
+    errno_t ret;
+    char *sanitized_dn;
+    char *filter;
+    const char *attrs[] = { SYSDB_NAME,
+                            SYSDB_MEMBEROF,
+                            NULL };
+    struct ldb_message **msgs = NULL;
+    size_t count;
+    TALLOC_CTX *tmp_ctx;
+    struct ldb_message_element *memberof;
+    const char **parents;
+
+    tmp_ctx = talloc_new(mem_ctx);
+    if (tmp_ctx == NULL) {
+        return ENOMEM;
+    }
+
+    ret = sss_filter_sanitize(tmp_ctx, original_dn, &sanitized_dn);
+    if (ret != EOK) {
+        DEBUG(SSSDBG_CRIT_FAILURE,
+                "Cannot sanitize originalDN [%s]\n", original_dn);
+        goto done;
+    }
+
+    filter = talloc_asprintf(tmp_ctx, "(%s=%s)", SYSDB_ORIG_DN, sanitized_dn);
+    if (filter == NULL) {
+        goto done;
+    }
+
+    ret = sysdb_search_groups(tmp_ctx, group_dom, filter, attrs,
+                              &count, &msgs);
+    if (ret != EOK) {
+        goto done;
+    }
+
+    if (count != 1) {
+        DEBUG(SSSDBG_OP_FAILURE,
+              "More than one entry found by originalDN?\n");
+        goto done;
+    }
+
+    memberof = ldb_msg_find_element(msgs[0], SYSDB_MEMBEROF);
+    if (memberof == NULL || memberof->num_values == 0) {
+        DEBUG(SSSDBG_MINOR_FAILURE,
+              "The external group is not a member of any groups\n");
+        ret = ENOENT;
+        goto done;
+    }
+
+    parents = talloc_zero_array(tmp_ctx,
+                                const char *,
+                                memberof->num_values + 1);
+    if (parents == NULL) {
+        ret = ENOMEM;
+        goto done;
+    }
+
+    for (size_t i = 0; i < memberof->num_values; i++) {
+        parents[i] = talloc_strdup(parents,
+                                   (const char *) memberof->values[i].data);
+        if (parents[i] == NULL) {
+            ret = ENOMEM;
+            goto done;
+        }
+    }
+
+    *_parents = talloc_steal(mem_ctx, parents);
+    ret = EOK;
+done:
+    talloc_free(tmp_ctx);
+    return ret;
+}
+
+errno_t
+sdap_nested_group_lookup_external_recv(TALLOC_CTX *mem_ctx,
+                                       struct tevent_req *req)
+{
+    TEVENT_REQ_RETURN_ON_ERROR(req);
+
+    return EOK;
+}
diff --git a/src/providers/ldap/sdap_async_private.h b/src/providers/ldap/sdap_async_private.h
index db542eaf8..9cde6f5df 100644
--- a/src/providers/ldap/sdap_async_private.h
+++ b/src/providers/ldap/sdap_async_private.h
@@ -130,8 +130,20 @@ errno_t sdap_nested_group_recv(TALLOC_CTX *mem_ctx,
                                unsigned long *_num_users,
                                struct sysdb_attrs ***_users,
                                unsigned long *_num_groups,
-                               struct sysdb_attrs ***_groups);
-
+                               struct sysdb_attrs ***_groups,
+                               hash_table_t **missing_external);
+
+struct tevent_req *
+sdap_nested_group_lookup_external_send(TALLOC_CTX *mem_ctx,
+                                       struct tevent_context *ev,
+                                       struct sss_domain_info *group_dom,
+                                       struct sdap_ext_member_ctx *ext_ctx,
+                                       hash_table_t *missing_external);
+errno_t
+sdap_nested_group_lookup_external_recv(TALLOC_CTX *mem_ctx,
+                                       struct tevent_req *req);
+
+/* from sdap_async_initgroups.c */
 errno_t sdap_add_incomplete_groups(struct sysdb_ctx *sysdb,
                                    struct sss_domain_info *domain,
                                    struct sdap_options *opts,
@@ -139,7 +151,7 @@ errno_t sdap_add_incomplete_groups(struct sysdb_ctx *sysdb,
                                    struct sysdb_attrs **ldap_groups,
                                    int ldap_groups_count);
 
-/* from sdap_async_nested_groups.c */
+/* from sdap_ad_groups.c */
 errno_t sdap_check_ad_group_type(struct sss_domain_info *dom,
                                  struct sdap_options *opts,
                                  struct sysdb_attrs *group_attrs,