slapi-nis: delay sending responses from compat tree after map search

When slapi-nis plugin responds on a search query, it holds read lock for
the internal structure called 'map cache'. The map cache lock can also be taken
for write when modification would be required like responding to DELETE, ADD, or
MODIFY operations.

As result of the lock semantics, write lock owner is blocked until all read lock
owners release their locks. This is generally not a problem but when readers sent
out LDAP query results, they call into SLAPI function that might take long time
to send out the data due to external reasons (network latencies, clients being
blocked, etc) and all this time map cache is locked for write operations.

When Kerberos KDC issues a TGT, it needs to modify few Kerberos-related attributes
in the principal's LDAP entry. These updates are generating MOD operations visible
by slapi-nis plugin which triggers re-scan of map cache to potentially replace
the affected entries. To perform potential replacement, slapi-nis has to take a write
lock and be blocked by outstanding readers.

Therefore, it is possible to encounter a situation where an LDAP client uses
SASL GSSAPI authentication and existing Kerberos ticket did expire in a course
of outstanding search request. According to LDAPv3 protocol specification, an
LDAP client must perform re-negotiation before reading any outstanding PDUs. It
would ask Kerberos KDC for a new (or renewed) TGT, that would cause MOD updates
for the primary tree which is tracked for changes by slapi-nis. These changes
would be blocked by a slapi-nis reader as the client cannot finish reading
outstanding PDUs yet.

To solve this problem, we avoid sending LDAP entries while keeping map cache
lock. Instead, we generate a linked list of copies of entries which will be
sent out. To allow sharing of entries between multiple parallel queries, we
hash the entry and reference the cached entry in the linked list with increased
reference count. Once entry is actually sent, its reference count decreased and
on reaching zero it is removed from the hash.

The entry in the hash table might become outdated. This is detected by comparing
both modifyTimestamp and entryUSN values of the entry to be sent and entry in the
hash table. If new version of the entry is different, hash table's entry reference
is replaced with a new copy. The old entry is not removed because it is still
referenced by some outstanding query processing. Thus, the hash table always
references the most recent version of an entry but there might be multiple copies
in possesion of the linked lists from the separate parallel queries.

An entry sharing via hash table can be disabled by setting
        slapi-entry-cache: 0
in the definition, cn=Schema Compatibility,cn=plugins,cn=config

Resolves: rhbz#1273587

https://bugzilla.redhat.com/show_bug.cgi?id=1273587

5 files changed, 212 insertions, 11 deletions

diff --git a/doc/sch-configuration.txt b/doc/sch-configuration.txt
index aa9ec41..cbc15e2 100644
--- a/doc/sch-configuration.txt
+++ b/doc/sch-configuration.txt
@@ -16,6 +16,13 @@ look like this:
   nsslapd-version: 0.0
   nsslapd-pluginvendor: redhat.com
   nsslapd-plugindescription: Schema Compatibility Plugin
+  slapi-entry-cache: 1
+
+The only optional attribute is 'slapi-entry-cache' (default to 1)
+controls whether the plugin should use an entry cache for outstanding
+query requests. The entry cache is an optimization technique to
+help reduce memory pressure during parallel requests. Specify 0 to disable
+an entry cache.
 
 Configuration for individual sets should be stored in entries directly
 beneath the plugin's entry.  These attributes are recognized:
diff --git a/src/back-sch.c b/src/back-sch.c
index dd6f92d..b2362d0 100644
--- a/src/back-sch.c
+++ b/src/back-sch.c
@@ -32,6 +32,7 @@
 
 #ifdef HAVE_DIRSRV_SLAPI_PLUGIN_H
 #include <nspr.h>
+#include <plhash.h>
 #include <nss.h>
 #include <dirsrv/slapi-plugin.h>
 #else
@@ -53,6 +54,9 @@
 #include "map.h"
 #include "back-sch.h"
 
+static void
+backend_entries_to_return_push(struct backend_search_cbdata *cbdata, Slapi_Entry *e);
+
 #define SCH_CONTAINER_CONFIGURATION_FILTER "(&(" SCH_CONTAINER_CONFIGURATION_GROUP_ATTR "=*)(" SCH_CONTAINER_CONFIGURATION_BASE_ATTR "=*)(" SCH_CONTAINER_CONFIGURATION_FILTER_ATTR "=*)(" SCH_CONTAINER_CONFIGURATION_RDN_ATTR "=*))"
 
 /* Read the name of the NIS master. A dummy function for the schema
@@ -996,7 +1000,7 @@ backend_search_entry_cb(const char *domain, const char *map, bool_t secure,
 			void *backend_data, void *cb_data)
 {
 	Slapi_DN *sdn;
-	Slapi_Entry *entry;
+	Slapi_Entry *entry = NULL; /* prevent to free an uninitialized entry */
 	Slapi_Attr *attr = NULL;
 	struct backend_search_cbdata *cbdata;
 	struct backend_entry_data *entry_data;
@@ -1052,8 +1056,7 @@ backend_search_entry_cb(const char *domain, const char *map, bool_t secure,
 			slapi_entry_delete_string(entry, "objectClass", "ipaOverrideTarget");
 		}
 #endif
-		slapi_send_ldap_search_entry(cbdata->pb, entry, NULL,
-					     cbdata->attrs, cbdata->attrsonly);
+		backend_entries_to_return_push(cbdata, entry);
 		cbdata->n_entries++;
 
 		if (entry != entry_data->e) {
@@ -1070,7 +1073,7 @@ backend_search_set_cb(const char *group, const char *set, bool_t flag,
 {
 	struct backend_search_cbdata *cbdata;
 	struct backend_set_data *set_data;
-	Slapi_Entry *set_entry;
+	Slapi_Entry *set_entry = NULL ; /* prevent to free an uninitialized entry */
 	int result, n_entries;
 	int n_entries_without_nsswitch;
 	const char *ndn;
@@ -1124,12 +1127,11 @@ backend_search_set_cb(const char *group, const char *set, bool_t flag,
 							 set_data->common.group, set_entry);
 			}
 #endif
-			slapi_send_ldap_search_entry(cbdata->pb, set_entry,
-						     NULL, cbdata->attrs,
-						     cbdata->attrsonly);
+			backend_entries_to_return_push(cbdata, set_entry);
 			cbdata->n_entries++;
 			break;
 		}
+
 		slapi_entry_free(set_entry);
 	}
 
@@ -1244,7 +1246,7 @@ backend_search_group_cb(const char *group, void *cb_data)
 {
 	struct backend_search_cbdata *cbdata;
 	Slapi_DN *group_dn;
-	Slapi_Entry *group_entry;
+	Slapi_Entry *group_entry = NULL; /* prevent to free an uninitialized entry */
 	int result, n_maps;
 
 	cbdata = cb_data;
@@ -1279,12 +1281,11 @@ backend_search_group_cb(const char *group, void *cb_data)
 				idview_process_overrides(cbdata, NULL, NULL, group, group_entry);
 			}
 #endif
-			slapi_send_ldap_search_entry(cbdata->pb, group_entry,
-						     NULL, cbdata->attrs,
-						     cbdata->attrsonly);
+			backend_entries_to_return_push(cbdata, group_entry);
 			cbdata->n_entries++;
 			break;
 		}
+
 		slapi_entry_free(group_entry);
 	}
 
@@ -1343,6 +1344,138 @@ backend_sch_scope_as_string(int scope)
 	return "";
 }
 
+/* The entries are pushed (added) at the end of the list
+ * so that they will be send in the head->tail order
+ */
+static void
+backend_entries_to_return_push(struct backend_search_cbdata *cbdata, Slapi_Entry *e)
+{
+	struct entries_to_send *e_to_send = NULL;
+	struct cached_entry *entry = NULL;
+	bool_t dont_cache = FALSE;
+	PLHashTable* ht = (PLHashTable*) cbdata->state->cached_entries;
+
+	if ((cbdata == NULL) || (e == NULL)) return;
+
+	e_to_send = (struct entries_to_send *) slapi_ch_calloc(1, sizeof(struct entries_to_send));
+
+	dont_cache = cbdata->state->use_entry_cache ? FALSE : TRUE;
+
+	if (!wrap_rwlock_wrlock(cbdata->state->cached_entries_lock)) {
+		entry = PL_HashTableLookup(ht, slapi_entry_get_ndn(e));
+		if (entry != NULL) {
+			/* There is an entry in the hash table but is it the same? */
+			char *e_modifyTimestamp = slapi_entry_attr_get_charptr(e, "modifyTimestamp");
+			char *entry_modifyTimestamp = slapi_entry_attr_get_charptr(entry->entry, "modifyTimestamp");
+			unsigned long e_usn = slapi_entry_attr_get_ulong(e, "entryUSN");
+			unsigned long entry_usn = slapi_entry_attr_get_ulong(entry->entry, "entryUSN");
+			int res = -1;
+
+			/* Our comparison strategy is following:
+			 * - compare modifyTimestamp values first,
+			 * - if they are the same (modifyTimestamp in slapi-nis is down to a second precision),
+			 *   compare entryUSN values if they exist
+			 * - default to not using the cached entry to be on safe side if both comparisons don't
+			 *   give us a definite answer */
+			if ((e_modifyTimestamp != NULL) && (entry_modifyTimestamp != NULL)) {
+				res = strncmp(e_modifyTimestamp, entry_modifyTimestamp, strlen(e_modifyTimestamp));
+			}
+
+			if ((res == 0) && ((e_usn != 0) && (entry_usn != 0))) {
+				res = e_usn != entry_usn ? 1 : 0;
+			}
+
+			if (res != 0) {
+				/* Cached entry is different, evict it from the hash table */
+				(void) PL_HashTableRemove(ht, slapi_entry_get_ndn(entry->entry));
+
+				/* We don't want to clear the entry because it is still in use by other thread.
+				 * Instead, we'll insert new entry into hash table, let the linked list in other
+				 * search to remove the entry itself, but mark it as non-cached. */
+				entry->not_cached = TRUE;
+				entry = NULL;
+			} else {
+				slapi_log_error(SLAPI_LOG_PLUGIN,
+					cbdata->state->plugin_desc->spd_id,
+					"referenced entry [%s], USNs: %ld vs %ld, [%s] vs [%s]\n",
+					slapi_entry_get_ndn(e), e_usn, entry_usn, e_modifyTimestamp, entry_modifyTimestamp);
+				/* It is the same entry, reference it for us */
+				(void) PR_AtomicIncrement(&entry->refcount);
+			}
+
+			if (e_modifyTimestamp != NULL)
+				slapi_ch_free_string(&e_modifyTimestamp);
+			if (entry_modifyTimestamp != NULL)
+				slapi_ch_free_string(&entry_modifyTimestamp);
+		}
+
+		if (entry == NULL) {
+			/* no cached entry for this DN */
+			entry = (struct cached_entry *) slapi_ch_calloc(1, sizeof(struct cached_entry));
+			entry->entry = slapi_entry_dup(e);
+			entry->not_cached = FALSE;
+			(void) PR_AtomicSet(&entry->refcount, 1);
+			if ((ht != NULL) && (entry->entry != NULL) && (!dont_cache)) {
+				(void) PL_HashTableAdd(ht, slapi_entry_get_ndn(entry->entry), entry);
+			}
+		}
+
+		wrap_rwlock_unlock(cbdata->state->cached_entries_lock);
+	}
+
+	e_to_send->entry = entry;
+	if (cbdata->entries_tail == NULL) {
+		/* First entry in that list */
+		cbdata->entries_tail = e_to_send;
+		cbdata->entries_head = e_to_send;
+	} else {
+		cbdata->entries_tail->next = e_to_send;
+		cbdata->entries_tail = e_to_send;
+	}
+}
+
+static void
+backend_send_mapped_entries(struct backend_search_cbdata *cbdata)
+{
+	struct entries_to_send *e_to_send, *next;
+	PLHashTable* ht = NULL;
+	int i = 0;
+	PRInt32 count;
+
+	if (cbdata == NULL) return;
+	ht = (PLHashTable*) cbdata->state->cached_entries;
+
+	/* iterate from head->tail sending the stored entries */
+	for (e_to_send = cbdata->entries_head, i = 0; e_to_send != NULL; i++) {
+		next = e_to_send->next;
+		if (e_to_send->entry->refcount > 0) {
+			slapi_send_ldap_search_entry(cbdata->pb, e_to_send->entry->entry, NULL,
+						     cbdata->attrs, cbdata->attrsonly);
+
+			/* Clean up entry only if there is no reference to it any more in any outstanding request */
+			wrap_rwlock_wrlock(cbdata->state->cached_entries_lock);
+			count = PR_AtomicDecrement(&e_to_send->entry->refcount);
+			if (count == 0) {
+				if (!e_to_send->entry->not_cached) {
+					(void) PL_HashTableRemove(ht, slapi_entry_get_ndn(e_to_send->entry->entry));
+				}
+				/* free this returned entry */
+				slapi_entry_free(e_to_send->entry->entry);
+				e_to_send->entry->entry = NULL;
+				slapi_ch_free((void **) &e_to_send->entry);
+				e_to_send->entry = NULL;
+			}
+			wrap_rwlock_unlock(cbdata->state->cached_entries_lock);
+		}
+
+		/* Otherwise only free list item */
+		slapi_ch_free((void **) &e_to_send);
+		e_to_send = next;
+	}
+	cbdata->entries_head = NULL;
+	cbdata->entries_tail = NULL;
+}
+
 static int
 backend_search_cb(Slapi_PBlock *pb)
 {
@@ -1443,6 +1576,8 @@ backend_search_cb(Slapi_PBlock *pb)
 				cbdata.state->plugin_desc->spd_id,
 				"unable to acquire read lock\n");
 	}
+	/* Return existing collected entries */
+	backend_send_mapped_entries(&cbdata);
 	wrap_dec_call_level();
 #ifdef USE_NSSWITCH
 	/* If during search of some sets we staged additional lookups, perform them. */
@@ -1525,6 +1660,8 @@ backend_search_cb(Slapi_PBlock *pb)
 		if (map_rdlock() == 0) {
 			map_data_foreach_domain(cbdata.state, backend_search_group_cb, &cbdata);
 			map_unlock();
+			/* Return newly acquired entries */
+			backend_send_mapped_entries(&cbdata);
 		} else {
 			slapi_log_error(SLAPI_LOG_PLUGIN,
 					cbdata.state->plugin_desc->spd_id,
diff --git a/src/back-sch.h b/src/back-sch.h
index 1aedf36..e8ec400 100644
--- a/src/back-sch.h
+++ b/src/back-sch.h
@@ -63,6 +63,24 @@ struct backend_staged_search {
 	Slapi_Entry **entries;
 };
 
+/* Entry to be send to clients is cached to allow multiple threads to re-use results.
+ */
+struct cached_entry {
+	Slapi_Entry *entry;
+	PRInt32 refcount;
+	bool_t not_cached;
+};
+
+/* list of entries to actually send, sorted as a linked list
+ * Entries are references to the ones stored in a cache
+ * Before sending them out one needs to refcount the entry
+ */
+struct entries_to_send {
+	struct entries_to_send *next;
+	struct entries_to_send *prev;
+	struct cached_entry *entry;
+};
+
 /* Intercept a search request, and if it belongs to one of our compatibility
  * trees, answer from our cache before letting the default database have a
  * crack at it. */
@@ -88,6 +106,8 @@ struct backend_search_cbdata {
 	int n_entries;
 	struct backend_staged_search *staged;
 	struct backend_staged_search *cur_staged;
+	struct entries_to_send *entries_head;
+	struct entries_to_send *entries_tail;
 };
 
 struct backend_search_filter_config {
diff --git a/src/plug-sch.c b/src/plug-sch.c
index 5a6e736..f132e6d 100644
--- a/src/plug-sch.c
+++ b/src/plug-sch.c
@@ -44,6 +44,7 @@
 
 #ifdef HAVE_DIRSRV_SLAPI_PLUGIN_H
 #include <nspr.h>
+#include <plhash.h>
 #include <nss.h>
 #include <dirsrv/slapi-plugin.h>
 #else
@@ -100,6 +101,7 @@ plugin_startup(Slapi_PBlock *pb)
 {
 	/* Populate the maps and data. */
 	struct plugin_state *state;
+	Slapi_Entry *plugin_entry = NULL;
 	slapi_pblock_get(pb, SLAPI_PLUGIN_PRIVATE, &state);
 	slapi_pblock_get(pb, SLAPI_TARGET_DN, &state->plugin_base);
 	slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
@@ -111,12 +113,35 @@ plugin_startup(Slapi_PBlock *pb)
 	backend_startup(pb, state);
 	state->pam_lock = wrap_new_rwlock();
 	backend_nss_init_context((struct nss_ops_ctx**) &state->nss_context);
+	if ((slapi_pblock_get(pb, SLAPI_PLUGIN_CONFIG_ENTRY, &plugin_entry) == 0) &&
+	    (plugin_entry != NULL)) {
+		state->use_entry_cache = backend_shr_get_vattr_boolean(state, plugin_entry,
+									"slapi-entry-cache",
+									1);
+	}
+	state->cached_entries_lock = wrap_new_rwlock();
+	wrap_rwlock_wrlock(state->cached_entries_lock);
+	state->cached_entries = PL_NewHashTable(0, PL_HashString, PL_CompareStrings, PL_CompareValues, 0, 0);
+	wrap_rwlock_unlock(state->cached_entries_lock);
 	/* Note that the plugin is ready to go. */
 	slapi_log_error(SLAPI_LOG_PLUGIN, plugin_description.spd_id,
 			"plugin startup completed\n");
 	return 0;
 }
 
+static PRIntn
+remove_cached_entries_cb(PLHashEntry *he, PRIntn i, void *arg)
+{
+	struct cached_entry *e = (struct cached_entry*) he->value;
+	if (e != NULL) {
+		if (e->entry != NULL) {
+			slapi_entry_free(e->entry);
+		}
+		slapi_ch_free((void **) &e);
+	}
+	return HT_ENUMERATE_REMOVE;
+}
+
 static int
 plugin_shutdown(Slapi_PBlock *pb)
 {
@@ -126,6 +151,15 @@ plugin_shutdown(Slapi_PBlock *pb)
 	wrap_free_rwlock(state->pam_lock);
 	state->pam_lock = NULL;
 	backend_nss_free_context((struct nss_ops_ctx**) &state->nss_context);
+	if (state->cached_entries != NULL) {
+		wrap_rwlock_wrlock(state->cached_entries_lock);
+		PL_HashTableEnumerateEntries(state->cached_entries, remove_cached_entries_cb, NULL);
+		PL_HashTableDestroy(state->cached_entries);
+		state->cached_entries = NULL;
+		wrap_rwlock_unlock(state->cached_entries_lock);
+		wrap_free_rwlock(state->cached_entries_lock);
+		state->cached_entries_lock = NULL;
+	}
 	state->plugin_base = NULL;
 	slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
 			"plugin shutdown completed\n");
diff --git a/src/plugin.h b/src/plugin.h
index 94ad747..429e291 100644
--- a/src/plugin.h
+++ b/src/plugin.h
@@ -47,6 +47,9 @@ struct plugin_state {
 	/* Schema compat-specific data. */
 	struct wrapped_rwlock *pam_lock;
 	void *nss_context;
+	int use_entry_cache;
+	void *cached_entries;
+	struct wrapped_rwlock *cached_entries_lock;
 };
 
 #endif