[SSSD] [PATCH] Speed up NSS enumeration code

Sumit Bose sbose at redhat.com
Fri Aug 28 10:03:24 UTC 2009


On Thu, Aug 27, 2009 at 01:58:15PM -0400, Simo Sorce wrote:
> This patch should make the enumeration code ~ O(log n) instead of O(n)
> 
> On my system it brought enumeration down from 12s to 4s with the same
> data set.
> 

Although I haven't measured it I see a speed-up, too.

I have only one issue with sort_members. Can you rename it to something
like distribute_members_to_groups or scatter_members_to_groups? I think
sort_members is very misleading here.

bye,
Sumit

> Simo.
> 
> -- 
> Simo Sorce * Red Hat, Inc * New York

> >From ab7ab19462ca5ccbb3efcb283648eb699f756f43 Mon Sep 17 00:00:00 2001
> From: Simo Sorce <ssorce at redhat.com>
> Date: Thu, 27 Aug 2009 13:52:54 -0400
> Subject: [PATCH] Speed-up enumerations.
> 
> This patch reduces the time needed to enumerate groups of a midsized
> domain from 12 seconds to 4.4
> Optimizes enumerations by doing only 2 ldb searches and some ordering
> instead of a number of searches proportional to the number of groups
> ---
>  server/db/sysdb.h        |    6 ++-
>  server/db/sysdb_search.c |  163 +++++++++++++++++++++++++++++++++++++++++++++-
>  2 files changed, 167 insertions(+), 2 deletions(-)
> 
> diff --git a/server/db/sysdb.h b/server/db/sysdb.h
> index 2f01ea6..3d75f50 100644
> --- a/server/db/sysdb.h
> +++ b/server/db/sysdb.h
> @@ -119,8 +119,12 @@
>                            SYSDB_LAST_UPDATE, \
>                            "objectClass", \
>                            NULL}
> +#define SYSDB_GRENT_ATTRS {SYSDB_NAME, SYSDB_UIDNUM, SYSDB_MEMBEROF, \
> +                           SYSDB_LAST_UPDATE, \
> +                           "objectClass", \
> +                           NULL}
>  
> -#define SYSDB_INITGR_ATTR "memberof"
> +#define SYSDB_INITGR_ATTR SYSDB_MEMBEROF
>  #define SYSDB_INITGR_ATTRS {SYSDB_GIDNUM, SYSDB_LAST_UPDATE, \
>                              "objectClass", \
>                              NULL}
> diff --git a/server/db/sysdb_search.c b/server/db/sysdb_search.c
> index a3fdb16..3837f45 100644
> --- a/server/db/sysdb_search.c
> +++ b/server/db/sysdb_search.c
> @@ -35,6 +35,7 @@ struct sysdb_search_ctx {
>  
>      struct sss_domain_info *domain;
>  
> +    bool enumeration;
>      const char *expression;
>  
>      sysdb_callback_t callback;
> @@ -297,6 +298,8 @@ int sysdb_enumpwent(TALLOC_CTX *mem_ctx,
>          return ENOMEM;
>      }
>  
> +    sctx->enumeration = true;
> +
>      if (expression)
>          sctx->expression = expression;
>      else
> @@ -384,6 +387,158 @@ static void get_members(struct sysdb_search_ctx *sctx)
>      }
>  }
>  
> +static void sort_members(struct sysdb_search_ctx *sctx);
> +static void enum_members(struct sysdb_search_ctx *sctx)
> +{
> +    static const char *attrs[] = SYSDB_GRENT_ATTRS;
> +    struct ldb_request *req;
> +    struct ldb_dn *dn;
> +    int ret;
> +
> +    /* search for all users that have memberof set */
> +    sctx->expression = talloc_asprintf(sctx, SYSDB_GRNA2_FILTER, "*");
> +    if (!sctx->expression) {
> +        return request_ldberror(sctx, LDB_ERR_OPERATIONS_ERROR);
> +    }
> +
> +    dn = ldb_dn_new_fmt(sctx, sctx->ctx->ldb,
> +                        SYSDB_TMPL_USER_BASE, sctx->domain->name);
> +    if (!dn) {
> +        return request_ldberror(sctx, LDB_ERR_OPERATIONS_ERROR);
> +    }
> +
> +    sctx->gen_aux_fn = sort_members;
> +
> +    ret = ldb_build_search_req(&req, sctx->ctx->ldb, sctx,
> +                               dn, LDB_SCOPE_SUBTREE,
> +                               sctx->expression, attrs, NULL,
> +                               sctx, get_gen_callback,
> +                               NULL);
> +    if (ret != LDB_SUCCESS) {
> +        return request_ldberror(sctx, ret);
> +    }
> +
> +    ret = ldb_request(sctx->ctx->ldb, req);
> +    if (ret != LDB_SUCCESS) {
> +        return request_ldberror(sctx, ret);
> +    }
> +}
> +
> +static void sort_members(struct sysdb_search_ctx *sctx)
> +{
> +    struct get_mem_ctx *gmctx;
> +    struct ldb_message **users;
> +    size_t num_users;
> +    size_t res_idx, grp_idx, i;
> +    const char *grp_dn;
> +
> +    gmctx = sctx->gmctx;
> +
> +    /* we have groups in gmctx->grps, and users in res->msgs
> +     * now we need to create a new set where we have each group
> +     * followed by pointers to its users */
> +    users = sctx->res->msgs;
> +    num_users = sctx->res->count;
> +
> +    /* allocate initial storage all in one go */
> +    sctx->res->count = gmctx->num_grps + num_users;
> +    sctx->res->msgs = talloc_array(sctx->res, struct ldb_message *,
> +                                   sctx->res->count + 1);
> +    if (!sctx->res->msgs) {
> +        return request_ldberror(sctx, LDB_ERR_OPERATIONS_ERROR);
> +    }
> +
> +    res_idx = 0;
> +    for (grp_idx = 0; grp_idx < gmctx->num_grps; grp_idx++) {
> +
> +        /* store the group first */
> +
> +        if (res_idx == sctx->res->count) {
> +            sctx->res->count += 10; /* allocate 10 at a time */
> +            sctx->res->msgs = talloc_realloc(sctx->res, sctx->res->msgs,
> +                                             struct ldb_message *,
> +                                             sctx->res->count + 1);
> +            if (!sctx->res->msgs) {
> +                return request_ldberror(sctx, LDB_ERR_OPERATIONS_ERROR);
> +            }
> +        }
> +
> +        sctx->res->msgs[res_idx] = gmctx->grps[grp_idx];
> +        res_idx++;
> +
> +        grp_dn = ldb_dn_get_linearized(gmctx->grps[grp_idx]->dn);
> +
> +        /* now search for the members */
> +        for (i = 0; i < num_users; i++) {
> +            struct ldb_message_element *el;
> +            struct ldb_val *val;
> +            int j;
> +
> +            el = ldb_msg_find_element(users[i], SYSDB_MEMBEROF);
> +            for (j = 0; j < el->num_values; j++) {
> +                val = &(el->values[j]);
> +                /* HACK: dn comparisons should be made with ldb_dn_compare() but
> +                 * that function requires slow conversions and memory
> +                 * allocations. ATM all DNs we use internally should be safe to
> +                 * compare directly in a case-insensitive manner */
> +                if (strncasecmp(grp_dn, (char *)val->data, val->length) != 0) {
> +                    continue;
> +                }
> +
> +                /* ok users belong to this group */
> +                if (res_idx == sctx->res->count) {
> +                    sctx->res->count += 10; /* allocate 10 at a time */
> +                    sctx->res->msgs = talloc_realloc(sctx->res,
> +                                                     sctx->res->msgs,
> +                                                     struct ldb_message *,
> +                                                     sctx->res->count + 1);
> +                    if (!sctx->res->msgs) {
> +                        return request_ldberror(sctx,
> +                                                LDB_ERR_OPERATIONS_ERROR);
> +                    }
> +                }
> +
> +                sctx->res->msgs[res_idx] = users[i];
> +                res_idx++;
> +
> +                /* now remove value so that we do not parse it again, and
> +                 * completely remove the user if it has no more values */
> +                if (el->num_values == 1) {
> +
> +                    /* make sure to remove memberof as we messed it up */
> +                    ldb_msg_remove_element(users[i], el);
> +
> +                    /* remove user from list by swapping it out and replacing
> +                     * it with the last on the list and shortening the list */
> +                    num_users--;
> +                    if (i == num_users) {
> +                        users[i] = NULL;
> +                    } else {
> +                        users[i] = users[num_users];
> +                        users[num_users] = NULL;
> +                        /* need to rewind or this user won't be checked */
> +                        i--;
> +                    }
> +
> +                } else {
> +                    /* still more values, just swap out this one */
> +                    el->num_values--;
> +                    if (j != el->num_values) {
> +                        /* swap last in */
> +                        el->values[j] = el->values[el->num_values];
> +                    }
> +                }
> +            }
> +        }
> +    }
> +
> +    /* count may be larger as we allocate in chuncks of 10,
> +     * make sure we report back the real size */
> +    sctx->res->count = res_idx;
> +
> +    return request_done(sctx);
> +}
> +
>  static int mpg_convert(struct ldb_message *msg)
>  {
>      struct ldb_message_element *el;
> @@ -495,7 +650,11 @@ static int get_grp_callback(struct ldb_request *req,
>              res->count = 0;
>  
>              /* now get members */
> -            get_members(sctx);
> +            if (sctx->enumeration) {
> +                enum_members(sctx);
> +            } else {
> +                get_members(sctx);
> +            }
>              return LDB_SUCCESS;
>          }
>  
> @@ -648,6 +807,8 @@ int sysdb_enumgrent(TALLOC_CTX *mem_ctx,
>          return ENOMEM;
>      }
>  
> +    sctx->enumeration = true;
> +
>      if (domain->mpg) {
>          sctx->expression = SYSDB_GRENT_MPG_FILTER;
>      } else {
> -- 
> 1.6.2.5
> 

> _______________________________________________
> sssd-devel mailing list
> sssd-devel at lists.fedorahosted.org
> https://fedorahosted.org/mailman/listinfo/sssd-devel




More information about the sssd-devel mailing list