NO... dsdb-extended: use a cache of dsdb_attributes for the current request

The logic is that for a given search it's often the same given search of
attributes in the same order that is used, so we use a small cache
instead of doing a binary search in the attributes_by_ldapname of the
schema. It helps to reduce the time spent doing strcasecmp.

NO: if we use a cache then it should be global and hidden inside of
dsdb_attribute_by_lDAPDisplayName() in order to speed of all modules.

diff --git a/source4/dsdb/samdb/ldb_modules/extended_dn_out.c b/source4/dsdb/samdb/ldb_modules/extended_dn_out.c
index b1eacf59eb8d98485828b8ff6fb928f83218d886..06686f9438e74149cb5d8a7a4c65ddc4f78344aa 100644 (file)
--- a/source4/dsdb/samdb/ldb_modules/extended_dn_out.c
+++ b/source4/dsdb/samdb/ldb_modules/extended_dn_out.c
@@ -337,6 +337,14 @@ static int handle_dereference_fds(struct ldb_dn *dn,
        return LDB_SUCCESS;
 }
 
+struct attributes_cache {
+       struct dsdb_attribute **data;
+       unsigned int used;
+       unsigned int size;
+       unsigned int initial_size;
+       unsigned int last_idx;
+};
+
 /* search */
 struct extended_search_context {
        struct ldb_module *module;
@@ -346,8 +354,93 @@ struct extended_search_context {
        bool remove_guid;
        bool remove_sid;
        int extended_type;
+       struct attributes_cache *attr_cache;
 };
 
+static void add_attribute_to_cache(struct attributes_cache *cache,
+                                  const struct dsdb_attribute *attr)
+{
+       if (cache->size == 0) {
+               return;
+       }
+
+       if (cache->size == cache->used) {
+               cache->size += 2;
+               /*
+                * The cache is initialy allocated to match the number of
+                * attribute in the first message.
+                * When attribute list is homogeneous because it's either
+                * the same class of object or a limited set of attributes on
+                * different object then we will have a positive effect, if
+                * we need to grow too much the cache we are most probably
+                * starting to store attributes that are not homogeneous.
+                * In this case as the array is not sorted the linear search
+                * will be less efficient than just the lookup in the
+                * schema using the binary search. So we'd better start ignoring
+                * the cache.
+                */
+               if (cache->size >= (2 * cache->initial_size)) {
+                       cache->used = 0;
+                       cache->size = 0;
+                       talloc_free(cache->data);
+                       return;
+               }
+
+               cache->data = talloc_realloc(cache, cache->data,
+                                            struct dsdb_attribute *,
+                                            cache->size);
+               if (!cache->data) {
+                       cache->used = 0;
+                       cache->size = 0;
+                       return;
+               }
+       }
+       cache->data[cache->used] = discard_const(attr);
+       cache->used++;
+}
+
+static const struct dsdb_attribute* find_attr_in_cache(struct attributes_cache *cache,
+                                                      const char* name)
+{
+       int i = 0;
+       int idx = cache->last_idx;
+
+       if (cache->used == 0) {
+               return NULL;
+       }
+       /* because we do last_idx = i +1 and i can be cache_used - 1 */
+       if (idx == cache->used) {
+               idx = 0;
+       }
+
+       /*
+        * Take advantage that most of the time attributes will be asked
+        * in the same order, again and again so starting for the last position
+        * should reduce the number of iteration to search for the next result
+        */
+       for (i = idx; i < cache->used; i++) {
+               if (ldb_attr_cmp(cache->data[i]->lDAPDisplayName, name) == 0) {
+                       cache->last_idx = i + 1;
+                       return cache->data[i];
+               }
+       }
+
+       for (i = 0; i < idx; i++) {
+               if (ldb_attr_cmp(cache->data[i]->lDAPDisplayName, name) == 0) {
+                       cache->last_idx = i + 1;
+                       return cache->data[i];
+               }
+       }
+#if 0
+       for (i = 0; i < cache->used; i++) {
+               if (ldb_attr_cmp(cache->data[i]->lDAPDisplayName, name) == 0) {
+                       cache->last_idx = i + 1;
+                       return cache->data[i];
+               }
+       }
+#endif
+       return NULL;
+}
 
 /*
    fix one-way links to have the right string DN, to cope with
@@ -507,9 +600,28 @@ static int extended_callback(struct ldb_request *req, struct ldb_reply *ares,
                bool make_extended_dn;
                const struct dsdb_attribute *attribute;
 
-               attribute = dsdb_attribute_by_lDAPDisplayName(ac->schema, msg->elements[i].name);
+               /*
+                * We create a small cache for the lifetime of the response
+                * so that instead of doing a search in 1000+ attributes for
+                * every entries, it will be done for all but the first time
+                * an attribute is seen in a small cache of ~20/30 entries
+                */
+               if (ac->attr_cache->initial_size == 0) {
+                       ac->attr_cache->data = talloc_zero_array(ac->attr_cache,
+                                                                struct dsdb_attribute *,
+                                                                msg->num_elements);
+                       ac->attr_cache->size = msg->num_elements;
+                       ac->attr_cache->initial_size = msg->num_elements;
+               }
+               attribute = find_attr_in_cache(ac->attr_cache,
+                                              msg->elements[i].name);
                if (!attribute) {
-                       continue;
+                       attribute = dsdb_attribute_by_lDAPDisplayName(ac->schema, msg->elements[i].name);
+                       if (!attribute) {
+                               continue;
+                       }
+                       add_attribute_to_cache(ac->attr_cache,
+                                              attribute);
                }
 
                if (p->normalise) {
@@ -743,6 +855,10 @@ static int extended_dn_out_search(struct ldb_module *module, struct ldb_request
 
        ac->module = module;
        ac->schema = dsdb_get_schema(ldb, ac);
+       ac->attr_cache = talloc_zero(ac, struct attributes_cache);
+       if (ac->attr_cache == NULL) {
+               return ldb_oom(ldb);
+       }
        ac->req = req;
        ac->inject = false;
        ac->remove_guid = false;