LDAP: Handle very large Active Directory groups

Active Directory 2008R2 allows only 1500 group members to be
retrieved in a single lookup. However, when we hit such a
situation, we can take advantage of the ASQ lookups, which are not
similarly limited.

With this patch, we will add any members found by ASQ that were
not found by the initial lookup so we will end with a complete
group listing.

https://fedorahosted.org/sssd/ticket/783

5 files changed, 271 insertions, 45 deletions

diff --git a/src/providers/ldap/sdap.c b/src/providers/ldap/sdap.c
index e4d3aa9b..1bb513ae 100644
--- a/src/providers/ldap/sdap.c
+++ b/src/providers/ldap/sdap.c
@@ -24,6 +24,7 @@
 #include "confdb/confdb.h"
 #include "providers/ldap/ldap_common.h"
 #include "providers/ldap/sdap.h"
+#include "providers/ldap/sdap_range.h"
 
 /* =Retrieve-Options====================================================== */
 
@@ -108,6 +109,11 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
     const char *name;
     bool store;
     bool base64;
+    char *base_attr;
+    char *dn = NULL;
+    uint32_t range_offset;
+    TALLOC_CTX *tmp_ctx = talloc_new(NULL);
+    if (!tmp_ctx) return ENOMEM;
 
     lerrno = 0;
     ret = ldap_set_option(sh->ldap, LDAP_OPT_RESULT_CODE, &lerrno);
@@ -116,7 +122,7 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
                   sss_ldap_err2string(ret)));
     }
 
-    attrs = sysdb_new_attrs(memctx);
+    attrs = sysdb_new_attrs(tmp_ctx);
     if (!attrs) return ENOMEM;
 
     str = ldap_get_dn(sh->ldap, sm->msg);
@@ -125,18 +131,18 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
         DEBUG(1, ("ldap_get_dn failed: %d(%s)\n",
                   lerrno, sss_ldap_err2string(lerrno)));
         ret = EIO;
-        goto fail;
+        goto done;
     }
 
     DEBUG(9, ("OriginalDN: [%s].\n", str));
     ret = sysdb_attrs_add_string(attrs, SYSDB_ORIG_DN, str);
-    if (ret) goto fail;
+    if (ret) goto done;
     if (_dn) {
-        *_dn = talloc_strdup(memctx, str);
-        if (!*_dn) {
+        dn = talloc_strdup(tmp_ctx, str);
+        if (!dn) {
             ret = ENOMEM;
             ldap_memfree(str);
-            goto fail;
+            goto done;
         }
     }
     ldap_memfree(str);
@@ -146,7 +152,7 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
         if (!vals) {
             DEBUG(1, ("Unknown entry type, no objectClasses found!\n"));
             ret = EINVAL;
-            goto fail;
+            goto done;
         }
 
         for (i = 0; vals[i]; i++) {
@@ -162,7 +168,7 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
                       map[0].name));
             ldap_value_free_len(vals);
             ret = EINVAL;
-            goto fail;
+            goto done;
         }
         ldap_value_free_len(vals);
     }
@@ -174,17 +180,35 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
                   lerrno, sss_ldap_err2string(lerrno)));
         if (map) {
             ret = EINVAL;
-            goto fail;
+            goto done;
         }
     }
     while (str) {
         base64 = false;
+
+        ret = sdap_parse_range(tmp_ctx, str, &base_attr, &range_offset);
+        if (ret == EAGAIN) {
+            /* This attribute contained range values and needs more to
+             * be retrieved
+             */
+            /* TODO: return the set of attributes that need additional retrieval
+             * For now, we'll continue below and treat it as regular values.
+             */
+
+        } else if (ret != EOK) {
+            DEBUG(SSSDBG_MINOR_FAILURE,
+                  ("Could not determine if attribute [%s] was ranged\n",
+                   str));
+            goto done;
+        }
+
+
         if (map) {
             for (a = 1; a < attrs_num; a++) {
                 /* check if this attr is valid with the chosen schema */
                 if (!map[a].name) continue;
                 /* check if it is an attr we are interested in */
-                if (strcasecmp(str, map[a].name) == 0) break;
+                if (strcasecmp(base_attr, map[a].name) == 0) break;
             }
             /* interesting attr */
             if (a < attrs_num) {
@@ -198,16 +222,10 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
                 name = NULL;
             }
         } else {
-            name = str;
+            name = base_attr;
             store = true;
         }
 
-        if (strstr(str, ";range=") != NULL) {
-            DEBUG(1, ("Attribute [%s] has range sub-attribute "
-                      "which is currently not supported, skipping.\n", str));
-            store = false;
-        }
-
         if (store) {
             vals = ldap_get_values_len(sh->ldap, sm->msg, str);
             if (!vals) {
@@ -216,7 +234,7 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
                     DEBUG(1, ("LDAP Library error: %d(%s)",
                               lerrno, sss_ldap_err2string(lerrno)));
                     ret = EIO;
-                    goto fail;
+                    goto done;
                 }
 
                 DEBUG(5, ("Attribute [%s] has no values, skipping.\n", str));
@@ -225,7 +243,7 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
                 if (!vals[0]) {
                     DEBUG(1, ("Missing value after ldap_get_values() ??\n"));
                     ret = EINVAL;
-                    goto fail;
+                    goto done;
                 }
                 for (i = 0; vals[i]; i++) {
                     if (base64) {
@@ -233,7 +251,7 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
                                 (uint8_t *)vals[i]->bv_val, vals[i]->bv_len);
                         if (!v.data) {
                             ret = ENOMEM;
-                            goto fail;
+                            goto done;
                         }
                         v.length = strlen((const char *)v.data);
                     } else {
@@ -242,7 +260,7 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
                     }
 
                     ret = sysdb_attrs_add_val(attrs, name, &v);
-                    if (ret) goto fail;
+                    if (ret) goto done;
                 }
                 ldap_value_free_len(vals);
             }
@@ -252,21 +270,23 @@ int sdap_parse_entry(TALLOC_CTX *memctx,
         str = ldap_next_attribute(sh->ldap, sm->msg, ber);
     }
     ber_free(ber, 0);
+    ber = NULL;
 
     ldap_get_option(sh->ldap, LDAP_OPT_RESULT_CODE, &lerrno);
     if (lerrno) {
         DEBUG(1, ("LDAP Library error: %d(%s)",
                   lerrno, sss_ldap_err2string(lerrno)));
         ret = EIO;
-        goto fail;
+        goto done;
     }
 
-    *_attrs = attrs;
-    return EOK;
+    *_attrs = talloc_steal(memctx, attrs);
+    if (_dn) *_dn = talloc_steal(memctx, dn);
+    ret = EOK;
 
-fail:
+done:
     if (ber) ber_free(ber, 0);
-    talloc_free(attrs);
+    talloc_free(tmp_ctx);
     return ret;
 }
 
diff --git a/src/providers/ldap/sdap_async.c b/src/providers/ldap/sdap_async.c
index d505772c..a8a12c3d 100644
--- a/src/providers/ldap/sdap_async.c
+++ b/src/providers/ldap/sdap_async.c
@@ -1826,6 +1826,8 @@ static errno_t sdap_asq_search_parse_entry(struct sdap_handle *sh,
     struct sdap_attr_map *map;
     int num_attrs;
     struct sdap_deref_attrs **res;
+    char *tmp;
+    char *dn;
     TALLOC_CTX *tmp_ctx;
 
     tmp_ctx = talloc_new(NULL);
@@ -1848,6 +1850,20 @@ static errno_t sdap_asq_search_parse_entry(struct sdap_handle *sh,
         res[mi]->attrs = NULL;
     }
 
+
+    tmp = ldap_get_dn(sh->ldap, msg->msg);
+    if (!tmp) {
+        ret = EINVAL;
+        goto done;
+    }
+
+    dn = talloc_strdup(tmp_ctx, tmp);
+    ldap_memfree(tmp);
+    if (!dn) {
+        ret = ENOMEM;
+        goto done;
+    }
+
     /* Find all suitable maps in the list */
     vals = ldap_get_values_len(sh->ldap, msg->msg, "objectClass");
     for (mi =0; mi < state->num_maps; mi++) {
@@ -1857,12 +1873,20 @@ static errno_t sdap_asq_search_parse_entry(struct sdap_handle *sh,
             if (strncasecmp(state->maps[mi].map[0].name,
                             vals[i]->bv_val, vals[i]->bv_len) == 0) {
                 /* it's an entry of the right type */
+                DEBUG(SSSDBG_TRACE_INTERNAL,
+                      ("Matched objectclass [%s] on DN [%s], will use associated map\n",
+                       state->maps[mi].map[0].name, dn));
                 map = state->maps[mi].map;
                 num_attrs = state->maps[mi].num_attrs;
                 break;
             }
         }
-        if (!map) continue;
+        if (!map) {
+            DEBUG(SSSDBG_TRACE_INTERNAL,
+                  ("DN [%s] did not match the objectClass [%s]\n",
+                   dn, state->maps[mi].map[0].name));
+            continue;
+        }
 
         ret = sdap_parse_entry(res[mi], sh, msg,
                                map, num_attrs,
@@ -1871,7 +1895,6 @@ static errno_t sdap_asq_search_parse_entry(struct sdap_handle *sh,
             DEBUG(3, ("sdap_parse_entry failed [%d]: %s\n", ret, strerror(ret)));
             goto done;
         }
-
     }
     ldap_value_free_len(vals);
 
diff --git a/src/providers/ldap/sdap_async_groups.c b/src/providers/ldap/sdap_async_groups.c
index fb6a85e2..36152503 100644
--- a/src/providers/ldap/sdap_async_groups.c
+++ b/src/providers/ldap/sdap_async_groups.c
@@ -2977,19 +2977,47 @@ sdap_nested_group_process_deref_result(struct tevent_req *req)
     errno_t ret;
     struct sdap_deref_ctx *dctx = state->derefctx;
     const char *tmp_name;
+    size_t i;
 
     while (dctx->result_index < dctx->num_results) {
-        if (dctx->deref_result[dctx->result_index]->map == \
-            state->opts->user_map) {
+        /* Add to appropriate hash table */
+        ret = sysdb_attrs_get_string(
+                dctx->deref_result[dctx->result_index]->attrs,
+                SYSDB_ORIG_DN, &orig_dn);
+        if (ret != EOK) {
+            DEBUG(2, ("The entry has no originalDN\n"));
+            return ret;
+        }
 
-            /* Add to appropriate hash table */
-            ret = sysdb_attrs_get_string(
-                    dctx->deref_result[dctx->result_index]->attrs,
-                    SYSDB_ORIG_DN, &orig_dn);
-            if (ret != EOK) {
-                DEBUG(2, ("The entry has no originalDN\n"));
-                return ret;
+        /* Ensure that all members returned from the deref request are included
+         * in the member processing. Sometimes we will get more results back from
+         * deref/asq than we got from the initial lookup, as is the case with
+         * Active Directory and its range retrieval mechanism.
+         */
+        for (i = 0; i < state->members->num_values; i++) {
+            /* FIXME: This is inefficient for very large sets of groups */
+            if (strcasecmp((const char *)state->members->values[i].data,
+                           orig_dn) == 0) break;
+        }
+        if (i >= state->members->num_values) {
+            state->members->values = talloc_realloc(state,
+                                                    state->members->values,
+                                                    struct ldb_val,
+                                                    state->members->num_values + 1);
+            if (!state->members->values) {
+                return ENOMEM;
             }
+            state->members->values[state->members->num_values].data =
+                    (uint8_t *)talloc_strdup(state->members->values, orig_dn);
+            if (!state->members->values[state->members->num_values].data) {
+                return ENOMEM;
+            }
+            state->members->values[state->members->num_values].length = strlen(orig_dn);
+            state->members->num_values++;
+        }
+
+        if (dctx->deref_result[dctx->result_index]->map == \
+            state->opts->user_map) {
 
             /* check if the user is in search base */
             if (!sss_ldap_dn_in_search_bases(state, orig_dn,
@@ -3024,14 +3052,6 @@ sdap_nested_group_process_deref_result(struct tevent_req *req)
                 return EIO;
             }
 
-            ret = sysdb_attrs_get_string(
-                    dctx->deref_result[dctx->result_index]->attrs,
-                    SYSDB_ORIG_DN, &orig_dn);
-            if (ret != EOK) {
-                DEBUG(2, ("The entry has no originalDN\n"));
-                return ret;
-            }
-
             /* check if the group is in search base */
             if (!sss_ldap_dn_in_search_bases(state, orig_dn,
                                              state->opts->group_search_bases,
diff --git a/src/providers/ldap/sdap_range.c b/src/providers/ldap/sdap_range.c
new file mode 100644
index 00000000..295b6605
--- /dev/null
+++ b/src/providers/ldap/sdap_range.c
@@ -0,0 +1,130 @@
+/*
+    SSSD
+
+    Authors:
+        Stephen Gallagher <sgallagh@redhat.com>
+
+    Copyright (C) 2012 Red Hat
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 3 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "providers/ldap/sdap_range.h"
+#include "util/util.h"
+#include "util/strtonum.h"
+
+#define SDAP_RANGE_STRING "range="
+
+errno_t sdap_parse_range(TALLOC_CTX *mem_ctx,
+                         const char *attr_desc,
+                         char **base_attr,
+                         uint32_t *range_offset)
+{
+    errno_t ret;
+    TALLOC_CTX *tmp_ctx;
+    char *endptr;
+    char *end_range;
+    char *base;
+    size_t rangestringlen = sizeof(SDAP_RANGE_STRING) - 1;
+
+    *range_offset = 0;
+
+    tmp_ctx = talloc_new(NULL);
+    if (!tmp_ctx) return ENOMEM;
+
+    /* The base_attr is the portion before the semicolon (if it exists) */
+    endptr = strchr(attr_desc, ';');
+    if (endptr == NULL) {
+        /* Not a ranged attribute. Just copy the attribute desc */
+        *base_attr = talloc_strdup(mem_ctx, attr_desc);
+        if (!*base_attr) {
+            ret = ENOMEM;
+        } else {
+            ret = EOK;
+        }
+        DEBUG(SSSDBG_TRACE_INTERNAL,
+              ("No sub-attributes for [%s]\n", attr_desc));
+        goto done;
+    }
+
+    /* This is a complex attribute. First get the base attribute name */
+    base = talloc_strndup(tmp_ctx, attr_desc,
+                          endptr - attr_desc);
+    if (!base) {
+        ret = ENOMEM;
+        goto done;
+    }
+    DEBUG(SSSDBG_TRACE_LIBS,
+          ("Base attribute of [%s] is [%s]\n",
+           attr_desc, base));
+
+    /* Next, determine if this is a ranged attribute */
+    if (strncmp(endptr+1, SDAP_RANGE_STRING, rangestringlen) != 0) {
+        /* This is some other sub-attribute. We'll just return the whole
+         * thing in case it's dealt with elsewhere.
+         */
+        *base_attr = talloc_strdup(mem_ctx, attr_desc);
+        if (!*base_attr) {
+            ret = ENOMEM;
+        } else {
+            ret = EOK;
+        }
+        DEBUG(SSSDBG_TRACE_LIBS,
+              ("[%s] contains sub-attribute other than a range, returning whole\n",
+               attr_desc));
+        goto done;
+    }
+
+    /* Get the end of the range */
+    end_range = strchr(endptr + rangestringlen +1, '-');
+    if (!end_range) {
+        ret = EINVAL;
+        DEBUG(SSSDBG_MINOR_FAILURE,
+              ("Cannot find hyphen in [%s]\n",
+               endptr + rangestringlen +1));
+        goto done;
+    }
+    end_range++; /* advance past the hyphen */
+
+    if (*end_range == '*') {
+        /* this was the last iteration of range retrievals */
+        *base_attr = talloc_steal(mem_ctx, base);
+        *range_offset = 0;
+        DEBUG(SSSDBG_TRACE_LIBS,
+              ("[%s] contained the last set of values for this attribute\n",
+               attr_desc));
+        return EOK;
+    }
+
+    *range_offset = strtouint32(end_range, &endptr, 10);
+    if (*endptr != '\0') {
+        *range_offset = 0;
+        ret = errno;
+        DEBUG(SSSDBG_MINOR_FAILURE,
+              ("[%s] did not parse as an unsigned integer: [%s]\n",
+               end_range, strerror(ret)));
+        goto done;
+    }
+    (*range_offset)++;
+
+    *base_attr = talloc_steal(mem_ctx, base);
+    DEBUG(SSSDBG_TRACE_LIBS,
+          ("Parsed range values: [%s][%d]\n",
+           base, *range_offset));
+
+    ret = EAGAIN;
+done:
+    talloc_free(tmp_ctx);
+    return ret;
+}
diff --git a/src/providers/ldap/sdap_range.h b/src/providers/ldap/sdap_range.h
new file mode 100644
index 00000000..1dc3ba8f
--- /dev/null
+++ b/src/providers/ldap/sdap_range.h
@@ -0,0 +1,33 @@
+/*
+    SSSD
+
+    Authors:
+        Stephen Gallagher <sgallagh@redhat.com>
+
+    Copyright (C) 2012 Red Hat
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 3 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef SDAP_RANGE_H_
+#define SDAP_RANGE_H_
+
+#include "src/util/util.h"
+
+errno_t sdap_parse_range(TALLOC_CTX *mem_ctx,
+                         const char *attr_desc,
+                         char **base_attr,
+                         uint32_t *range_offset);
+
+#endif /* SDAP_RANGE_H_ */