Merge branch 'master' of git.fedorahosted.org:/git/slapi-nis

12 files changed, 532 insertions, 252 deletions

diff --git a/configure.ac b/configure.ac
index 13f7f6f..d5f3de0 100644
--- a/configure.ac
+++ b/configure.ac
@@ -113,7 +113,7 @@ AC_DEFINE(DEFAULT_MAX_DGRAM_SIZE,YPMAXRECORD,[Define to the default maximum data
 AC_DEFINE(DEFAULT_MAX_VALUE_SIZE,(256 * 1024),[Define to the default maximum map entry key and value size.])
 AC_DEFINE(DEFAULT_TARGET_REPLY_SIZE,(4 * 1024),[Define to the default target size for a connected reply fragment.])
 
-baseattr=base
+baseattr=nis-base
 AC_DEFINE_UNQUOTED(MAP_CONFIGURATION_BASE_ATTR,"$baseattr",
 		   [Define to name of the attribute which lists the containers for entries for a given map.])
 filterattr=nis-filter
@@ -131,6 +131,9 @@ AC_DEFINE_UNQUOTED(MAP_CONFIGURATION_DOMAIN_ATTR,"$domainattr",
 mapattr=nis-map
 AC_DEFINE_UNQUOTED(MAP_CONFIGURATION_MAP_ATTR,"$mapattr",
 		   [Define to name of the map configuration attribute which holds the name of the map.])
+disallowedcharsattr=nis-disallowed-chars
+AC_DEFINE_UNQUOTED(MAP_CONFIGURATION_DISALLOWED_CHARS_ATTR,"$disallowedcharsattr",
+		   [Define to the list of characters which should not be allowed in attribute values which are being considered.])
 secureattr=nis-secure
 AC_DEFINE_UNQUOTED(MAP_CONFIGURATION_SECURE_ATTR,"$secureattr",
 		   [Define to name of the map configuration attribute which determines whether or not the map is treated a 'secure' map.])
diff --git a/doc/configuration.txt b/doc/configuration.txt
index 08376b0..63c33fc 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -82,11 +82,17 @@ beneath the plugin's entry.  These attributes are recognized:
  * nis-key-format
    A format specifier which the plugin will use to convert the contents
    of the directory server entry into the corresponding key in the NIS
-   map.
+   map.  If this attribute has more than one value, the resulting NIS
+   map will include each resulting key with the same corresponding
+   value.
  * nis-value-format
    A format specifier which the plugin will use to convert the contents
    of the directory server entry into the corresponding value in the NIS
    map.
+ * nis-disallowed-chars
+   A list of characters which, if found in an attribute value, will
+   cause that attribute value to be ignored when evaluating keys and
+   values.
 
 The nis-filter, nis-key-format, and nis-value-format all have default
 settings which vary based on the name of the NIS map, but they can be
@@ -101,5 +107,6 @@ overridden.  An example map definition might look like this:
   nis-filter: (&(mail=*)(uid=*))
   nis-key-format: %{uid}
   nis-value-format: %{uid}:%{mail}
+  nis-disallowed-chars: :
   nis-secure: no
 
diff --git a/doc/design.txt b/doc/design.txt
index c4a98bd..92abf49 100644
--- a/doc/design.txt
+++ b/doc/design.txt
@@ -191,7 +191,7 @@ given domain (or domains) with the given map name (or names), and then
 performs a subtree search under the specified base (or bases, if there's
 more than one "nis-base" value) for entries which match the provided
 filter.  Each entry found is then "added" to the map, using the format
-specifier stored in "nis-key-format" to construct the key for the entry
+specifiers stored in "nis-key-format" to construct the keys for the entry
 in the map, with the corresponding value in the map being constructed
 using the format specifier given as the "nis-value-format".  The map is
 marked as a "secure" map according to the "nis-secure" attribute, if
diff --git a/src/backend.c b/src/backend.c
index 393cc9d..a40241a 100644
--- a/src/backend.c
+++ b/src/backend.c
@@ -55,7 +55,10 @@
 /* The data we ask the map cache to keep, for us, for each map. */
 struct backend_map_data {
 	struct plugin_state *state;
-	char *domain, *map, **bases, *entry_filter, *key_format, *value_format;
+	char *domain, *map, **bases, *entry_filter, **key_formats;
+	char *value_format;
+	int n_key_formats;
+	char *disallowed_chars;
 	char **ref_attrs;
 	struct format_inref_attr **inref_attrs;
 };
@@ -120,6 +123,14 @@ backend_read_master_name(struct plugin_state *state, char **master)
 	slapi_entry_free(config);
 	return (*master != NULL) ? 0 : -1;
 }
+static void
+backend_free_strlist(char **strlist)
+{
+	int i;
+	if (strlist) {
+		free(strlist);
+	}
+}
 static char **
 backend_dup_strlist(char **strlist)
 {
@@ -139,7 +150,7 @@ backend_dup_strlist(char **strlist)
 	}
 	/* Allocate space for the array of pointers (with NULL terminator) and
 	 * then the string data. */
-	ret = malloc((i + 1) * sizeof(char *) + l);
+	ret = malloc(((i + 1) * sizeof(char *)) + l);
 	if (ret != NULL) {
 		/* Figure out where the string data will start. */
 		s = (char *) &ret[i + 1];
@@ -165,10 +176,11 @@ backend_free_map_data_contents(void *data)
 		free(map_data->domain);
 		free(map_data->map);
 		free(map_data->bases);
+		free(map_data->disallowed_chars);
 		format_free_attr_list(map_data->ref_attrs);
 		format_free_inref_attrs(map_data->inref_attrs);
 		free(map_data->entry_filter);
-		free(map_data->key_format);
+		backend_free_strlist(map_data->key_formats);
 		free(map_data->value_format);
 	}
 }
@@ -191,6 +203,8 @@ backend_copy_cb_data(const struct backend_map_data *data)
 	ret->domain = strdup(data->domain);
 	ret->map = strdup(data->map);
 	ret->bases = backend_dup_strlist(data->bases);
+	ret->disallowed_chars = data->disallowed_chars ?
+				strdup(data->disallowed_chars) : NULL;
 	ret->ref_attrs = data->ref_attrs ?
 			 format_dup_attr_list(data->ref_attrs) :
 			 NULL;
@@ -198,13 +212,15 @@ backend_copy_cb_data(const struct backend_map_data *data)
 			   format_dup_inref_attrs(data->inref_attrs) :
 			   NULL;
 	ret->entry_filter = strdup(data->entry_filter);
-	ret->key_format = strdup(data->key_format);
+	ret->key_formats = backend_dup_strlist(data->key_formats);
+	ret->n_key_formats = data->n_key_formats;
 	ret->value_format = strdup(data->value_format);
 	if ((ret->domain == NULL) ||
 	    (ret->map == NULL) ||
 	    (ret->bases == NULL) ||
+	    (ret->disallowed_chars == NULL) ||
 	    (ret->entry_filter == NULL) ||
-	    (ret->key_format == NULL) ||
+	    (ret->key_formats == NULL) ||
 	    (ret->value_format == NULL)) {
 		backend_free_map_data(ret);
 		return NULL;
@@ -218,29 +234,43 @@ static int
 backend_map_config_entry_add_one_cb(Slapi_Entry *e, void *callback_data)
 {
 	struct backend_map_data *data;
-	char *key, *value, *ndn;
+	char **keys, *value, *ndn;
 	int i, j;
 	data = callback_data;
-	/* Pull out the key and value for the entry. */
-	key = format_get_data(data->state, NULL, e, data->domain, data->map,
-			      data->key_format,
-			      &data->ref_attrs, &data->inref_attrs);
+	/* Pull out the keys and value for the entry. */
+	keys = malloc((data->n_key_formats + 1) * sizeof(char *));
+	if (keys != NULL) {
+		for (i = 0; i < data->n_key_formats; i++) {
+			keys[i] = format_get_data(data->state, NULL, e,
+						  data->domain, data->map,
+						  data->key_formats[i],
+						  data->disallowed_chars,
+						  &data->ref_attrs,
+						  &data->inref_attrs);
+		}
+		keys[i] = NULL;
+	} else {
+		return 0;
+	}
 	value = format_get_data(data->state, NULL, e, data->domain, data->map,
-			        data->value_format,
+			        data->value_format, data->disallowed_chars,
 			        &data->ref_attrs, &data->inref_attrs);
 	/* Pull out the NDN of this entry. */
 	ndn = slapi_entry_get_ndn(e);
 	/* If we actually generated a value, then set it, otherwise clear it in
 	 * case there was one set before. */
-	if ((key != NULL) && (value != NULL)) {
-		slapi_log_error(SLAPI_LOG_PLUGIN,
-				data->state->plugin_desc->spd_id,
-				"setting domain/map/key/value "
-				"\"%s\"/\"%s\"/\"%s\"(\"%s\")=\"%s\"\n",
-				data->domain, data->map,
-				key, ndn, value);
+	if ((keys != NULL) && (value != NULL)) {
+		for (i = 0; i < data->n_key_formats; i++) {
+			slapi_log_error(SLAPI_LOG_PLUGIN,
+					data->state->plugin_desc->spd_id,
+					"setting domain/map/key/value "
+					"\"%s\"/\"%s\"/\"%s\"(\"%s\")=\"%s\"\n",
+					data->domain, data->map,
+					keys[i], ndn, value);
+		}
 		map_data_set_entry(data->state, data->domain, data->map, ndn,
-				   -1, key,
+				   data->n_key_formats,
+				   NULL, keys,
 				   -1, value);
 	} else {
 		slapi_log_error(SLAPI_LOG_PLUGIN,
@@ -253,7 +283,10 @@ backend_map_config_entry_add_one_cb(Slapi_Entry *e, void *callback_data)
 					ndn);
 	}
 	format_free_data(value);
-	format_free_data(key);
+	for (i = 0; i < data->n_key_formats; i++) {
+		format_free_data(keys[i]);
+	}
+	free(keys);
 	return 0;
 }
 
@@ -372,18 +405,21 @@ backend_map_config_read_config(struct plugin_state *state, Slapi_Entry *e,
 			       const char *domain, const char *map,
 			       bool_t *secure, struct backend_map_data *ret)
 {
-	const char *default_filter, *default_key_format, *default_value_format;
-	char **bases, *entry_filter, *key_format, *value_format, *actual_attr;
-	char **ref_attrs;
+	const char *default_filter, **default_key_formats;
+	const char *default_value_format, *default_disallowed_chars;
+	char **bases, *entry_filter, **key_formats, *value_format, *actual_attr;
+	char **ref_attrs, *disallowed_chars;
 	struct format_inref_attr **inref_attrs;
-	char **use_bases, *use_entry_filter, *use_key_format, *use_value_format;
+	char **use_bases, *use_entry_filter, **use_key_formats;
+	char *use_value_format, *use_disallowed_chars;
 	const char *cvalue;
-	int i, disposition, buffer_flags, count;
+	int i, j, disposition, buffer_flags, count;
 	Slapi_ValueSet *values;
 	Slapi_Value *value;
 	/* Read the hard-coded defaults for a map with this name. */
 	defaults_get_map_config(map, secure, &default_filter,
-				&default_key_format, &default_value_format);
+				&default_key_formats, &default_value_format,
+				&default_disallowed_chars);
 	/* Read the values from the configuration entry. */
 	bases = NULL;
 	if (slapi_vattr_values_get(e, MAP_CONFIGURATION_BASE_ATTR, &values,
@@ -392,13 +428,14 @@ backend_map_config_read_config(struct plugin_state *state, Slapi_Entry *e,
 		count = slapi_valueset_count(values);
 		bases = malloc(sizeof(char *) * (count + 1));
 		if (bases != NULL) {
-			for (i = slapi_valueset_first_value(values, &value);
-			     i != -1;
-			     i = slapi_valueset_next_value(values, i, &value)) {
+			i = 0;
+			for (j = slapi_valueset_first_value(values, &value);
+			     j != -1;
+			     j = slapi_valueset_next_value(values, j, &value)) {
 				cvalue = slapi_value_get_string(value);
-				bases[i] = strdup(cvalue);
+				bases[i++] = strdup(cvalue);
 			}
-			bases[count] = NULL;
+			bases[i] = NULL;
 		}
 		slapi_vattr_values_free(&values, &actual_attr, buffer_flags);
 	}
@@ -413,16 +450,24 @@ backend_map_config_read_config(struct plugin_state *state, Slapi_Entry *e,
 		}
 		slapi_vattr_values_free(&values, &actual_attr, buffer_flags);
 	}
-	key_format = NULL;
+	key_formats = NULL;
 	if (slapi_vattr_values_get(e, MAP_CONFIGURATION_KEY_ATTR, &values,
 				   &disposition, &actual_attr,
 				   0, &buffer_flags) == 0) {
-		i = slapi_valueset_first_value(values, &value);
-		if (i != -1) {
-			cvalue = slapi_value_get_string(value);
-			key_format = strdup(cvalue);
+		key_formats = malloc((slapi_valueset_count(values) + 1) *
+				     (sizeof (char *)));
+		if (key_formats != NULL) {
+			i = 0;
+			for (j = slapi_valueset_first_value(values, &value);
+			     j != -1;
+			     j = slapi_valueset_next_value(values, j, &value)) {
+				cvalue = slapi_value_get_string(value);
+				key_formats[i++] = strdup(cvalue);
+			}
+			key_formats[i] = NULL;
+			slapi_vattr_values_free(&values, &actual_attr,
+						buffer_flags);
 		}
-		slapi_vattr_values_free(&values, &actual_attr, buffer_flags);
 	}
 	value_format = NULL;
 	if (slapi_vattr_values_get(e, MAP_CONFIGURATION_VALUE_ATTR, &values,
@@ -435,6 +480,17 @@ backend_map_config_read_config(struct plugin_state *state, Slapi_Entry *e,
 		}
 		slapi_vattr_values_free(&values, &actual_attr, buffer_flags);
 	}
+	disallowed_chars = NULL;
+	if (slapi_vattr_values_get(e, MAP_CONFIGURATION_DISALLOWED_CHARS_ATTR,
+				   &values, &disposition, &actual_attr,
+				   0, &buffer_flags) == 0) {
+		i = slapi_valueset_first_value(values, &value);
+		if (i != -1) {
+			cvalue = slapi_value_get_string(value);
+			disallowed_chars = strdup(cvalue);
+		}
+		slapi_vattr_values_free(&values, &actual_attr, buffer_flags);
+	}
 	*secure = FALSE;
 	if (slapi_vattr_values_get(e, MAP_CONFIGURATION_SECURE_ATTR, &values,
 				   &disposition, &actual_attr,
@@ -461,41 +517,49 @@ backend_map_config_read_config(struct plugin_state *state, Slapi_Entry *e,
 						     entry_filter :
 						     default_filter,
 						     domain, map);
-	use_key_format = key_format ?
-			 strdup(key_format) :
-			 strdup(default_key_format);
+	use_key_formats = key_formats ?
+			  backend_dup_strlist(key_formats) :
+			  backend_dup_strlist((char **) default_key_formats);
 	use_value_format = value_format ?
 			   strdup(value_format) :
 			   strdup(default_value_format);
 	use_bases = backend_dup_strlist(bases);
+	use_disallowed_chars = disallowed_chars ?
+			       disallowed_chars :
+			       (default_disallowed_chars ?
+			        strdup(default_disallowed_chars) :
+				NULL);
 	/* Free the values we read from the entry. */
 	free(value_format);
-	free(key_format);
+	backend_free_strlist(key_formats);
 	free(entry_filter);
-	if (bases) {
-		for (i = 0; bases[i] != NULL; i++) {
-			free(bases[i]);
-		}
-		free(bases);
-	}
+	backend_free_strlist(bases);
 	/* Populate the returned structure. */
 	ret->state = state;
 	ret->domain = strdup(domain);
 	ret->map = strdup(map);
 	ret->bases = use_bases;
+	ret->disallowed_chars = use_disallowed_chars;
 	ret->entry_filter = use_entry_filter;
-	ret->key_format = use_key_format;
+	ret->key_formats = use_key_formats;
 	ret->value_format = use_value_format;
 	ret->ref_attrs = NULL;
 	ret->inref_attrs = NULL;
-	slapi_log_error(SLAPI_LOG_PLUGIN,
-			state->plugin_desc->spd_id,
-			"initializing map %s in %s (3): "
-			"filter \"%s\", "
-			"key \"%s\", "
-			"value \"%s\"\n",
-			map, domain,
-			use_entry_filter, use_key_format, use_value_format);
+	ret->n_key_formats = 0;
+	for (i = 0;
+	     (use_key_formats != NULL) && (use_key_formats[i] != NULL);
+	     i++) {
+		slapi_log_error(SLAPI_LOG_PLUGIN,
+				state->plugin_desc->spd_id,
+				"initializing map %s in %s (3): "
+				"filter \"%s\", "
+				"key \"%s\", "
+				"value \"%s\"\n",
+				map, domain,
+				use_entry_filter,
+				use_key_formats[i], use_value_format);
+		ret->n_key_formats++;
+	}
 }
 
 /* Given a directory server entry which represents a map's configuration, set
@@ -513,13 +577,21 @@ backend_map_config_entry_add_one(struct plugin_state *state, Slapi_Entry *e,
 	secure = FALSE;
 	backend_map_config_read_config(state, e, domain, map, &secure,
 				       &cb_data);
+	map_cb_data = backend_copy_cb_data(&cb_data);
+	backend_free_map_data_contents(&cb_data);
+	if (map_cb_data == NULL) {
+		slapi_log_error(SLAPI_LOG_PLUGIN,
+				state->plugin_desc->spd_id,
+				"incomplete map definition %s in %s (2)\n",
+				map, domain);
+		slapi_pblock_destroy(pb);
+		return 0;
+	}
 	slapi_log_error(SLAPI_LOG_PLUGIN,
 			state->plugin_desc->spd_id,
 			"initializing map %s in %s, secure=%s (2)\n",
 			map, domain, secure ? "yes" : "no");
-	map_cb_data = backend_copy_cb_data(&cb_data);
-	backend_free_map_data_contents(&cb_data);
-	map_data_set_map(state, domain, map, secure,
+	map_data_set_map(state, domain, map, map_cb_data->n_key_formats, secure,
 			 map_cb_data, &backend_free_map_data);
 	map_data_clear_map(state, domain, map);
 	/* Search under each base in turn, adding the matching directory
@@ -803,12 +875,7 @@ void
 backend_free_map_config(char **bases, char *entry_filter)
 {
 	int i;
-	if (bases != NULL) {
-		for (i = 0; bases[i] != NULL; i++) {
-			free(bases[i]);
-		}
-	}
-	free(bases);
+	backend_free_strlist(bases);
 	free(entry_filter);
 }
 
@@ -908,7 +975,8 @@ backend_get_map_config(struct plugin_state *state,
 	cbdata.bases = NULL;
 	cbdata.state = state;
 	map_secure = FALSE;
-	defaults_get_map_config(map, &map_secure, &default_filter, NULL, NULL);
+	defaults_get_map_config(map, &map_secure, &default_filter,
+				NULL, NULL, NULL);
 	cbdata.entry_filter = strdup(default_filter);
 	slapi_search_internal_callback_pb(pb, &cbdata,
 					  NULL,
diff --git a/src/defaults.c b/src/defaults.c
index fe2474d..9ecd1f8 100644
--- a/src/defaults.c
+++ b/src/defaults.c
@@ -33,45 +33,53 @@
 #define DEFAULT_KEY_FORMAT "%{cn}"
 #define DEFAULT_VALUE_FORMAT "%{nisMapEntry}"
 #define DEFAULT_MAP_SECURE FALSE
+static const char *default_key_formats[] = {DEFAULT_KEY_FORMAT, NULL};
 
 static struct configuration {
 	char *map;
 	enum { config_exact, config_glob } config_match;
 	bool_t secure;
-	char *filter, *key_format, *value_format;
+	char *filter, *key_formats[3], *value_format, *disallowed_chars;
 } config[] = {
 	{"passwd.byname", config_exact, FALSE,
 	 "(objectClass=posixAccount)",
-	 "%{uid}",
-	 "%{uid}:%regsub(\"userPassword\",\"^\\\\{CRYPT\\\\}(..*)\",\"%1\",\"*\"):%{uidNumber}:%{gidNumber}:%{cn!:}:%{homeDirectory:-/}:%{loginShell!:}"},
+	 {"%{uid}", NULL, NULL},
+	 "%{uid}:%regsub(\"userPassword\",\"^\\\\{CRYPT\\\\}(..*)\",\"%1\",\"*\"):%{uidNumber}:%{gidNumber}:%{gecos:-%{cn}}:%{homeDirectory:-/}:%{loginShell}",
+	 ":"},
 	{"passwd.byuid", config_exact, FALSE,
 	 "(objectClass=posixAccount)",
-	 "%{uidNumber}",
-	 "%{uid}:%regsub(\"userPassword\",\"^\\\\{CRYPT\\\\}(..*)\",\"%1\",\"*\"):%{uidNumber}:%{gidNumber}:%{cn!:}:%{homeDirectory:-/}:%{loginShell!:}"},
+	 {"%{uidNumber}", NULL, NULL},
+	 "%{uid}:%regsub(\"userPassword\",\"^\\\\{CRYPT\\\\}(..*)\",\"%1\",\"*\"):%{uidNumber}:%{gidNumber}:%{gecos:-%{cn}}:%{homeDirectory:-/}:%{loginShell}",
+	 ":"},
 	{"group.byname", config_exact, FALSE,
 	 "(objectClass=posixGroup)",
-	 "%{cn}",
-	 "%{cn}:%regsub(\"userPassword\",\"^\\\\{CRYPT\\\\}(..*)\",\"%1\",\"*\"):%{gidNumber}:%merge(\",\",\"%list(\\\",\\\",\\\"memberUid\\\")\",\"%deref(\\\",\\\",\\\"member\\\",\\\"uid\\\")\",\"%deref(\\\",\\\",\\\"uniqueMember\\\",\\\"uid\\\")\",\"%referred(\\\",\\\",\\\"passwd.byname\\\",\\\"memberOf\\\",\\\"uid\\\")\")"},
+	 {"%{cn}", NULL, NULL},
+	 "%{cn}:%regsub(\"userPassword\",\"^\\\\{CRYPT\\\\}(..*)\",\"%1\",\"*\"):%{gidNumber}:%merge(\",\",\"%list(\\\",\\\",\\\"memberUid\\\")\",\"%deref(\\\",\\\",\\\"member\\\",\\\"uid\\\")\",\"%deref(\\\",\\\",\\\"uniqueMember\\\",\\\"uid\\\")\",\"%referred(\\\",\\\",\\\"passwd.byname\\\",\\\"memberOf\\\",\\\"uid\\\")\")",
+	 ":,"},
 	{"group.bygid", config_exact, FALSE,
 	 "(objectClass=posixGroup)",
-	 "%{gidNumber}",
-	 "%{cn}:%regsub(\"userPassword\",\"^\\\\{CRYPT\\\\}(..*)\",\"%1\",\"*\"):%{gidNumber}:%merge(\",\",\"%list(\\\",\\\",\\\"memberUid\\\")\",\"%deref(\\\",\\\",\\\"member\\\",\\\"uid\\\")\",\"%deref(\\\",\\\",\\\"uniqueMember\\\",\\\"uid\\\")\",\"%referred(\\\",\\\",\\\"passwd.byuid\\\",\\\"memberOf\\\",\\\"uid\\\")\")"},
+	 {"%{gidNumber}", NULL, NULL},
+	 "%{cn}:%regsub(\"userPassword\",\"^\\\\{CRYPT\\\\}(..*)\",\"%1\",\"*\"):%{gidNumber}:%merge(\",\",\"%list(\\\",\\\",\\\"memberUid\\\")\",\"%deref(\\\",\\\",\\\"member\\\",\\\"uid\\\")\",\"%deref(\\\",\\\",\\\"uniqueMember\\\",\\\"uid\\\")\",\"%referred(\\\",\\\",\\\"passwd.byuid\\\",\\\"memberOf\\\",\\\"uid\\\")\")",
+	 ":,"},
 	{"netgroup", config_exact, FALSE,
 	 "(objectClass=nisNetgroup)",
-	 "%{cn}",
-	 "%list(\" \",\"nisNetgroupTriple\",\"memberNisNetgroup\")"},
+	 {"%{cn}", NULL, NULL},
+	 "%list(\" \",\"nisNetgroupTriple\",\"memberNisNetgroup\")",
+	 NULL},
 	{"auto.*", config_glob, FALSE,
 	 "(objectClass=automount)",
-	 "%{automountKey}",
-	 "%{automountInformation}"},
+	 {"%{automountKey}", NULL, NULL},
+	 "%{automountInformation}",
+	 NULL},
 };
 
 void
 defaults_get_map_config(const char *mapname,
 			bool_t *secure,
 			const char **filter,
-			const char **key_format,
-			const char **value_format)
+			const char ***key_formats,
+			const char **value_format,
+			const char **disallowed_chars)
 {
 	unsigned int i;
 	if (filter) {
@@ -80,8 +88,8 @@ defaults_get_map_config(const char *mapname,
 	if (secure) {
 		*secure = DEFAULT_MAP_SECURE;
 	}
-	if (key_format) {
-		*key_format = DEFAULT_KEY_FORMAT;
+	if (key_formats) {
+		*key_formats = default_key_formats;
 	}
 	if (value_format) {
 		*value_format = DEFAULT_VALUE_FORMAT;
@@ -96,12 +104,15 @@ defaults_get_map_config(const char *mapname,
 				if (filter) {
 					*filter = config[i].filter;
 				}
-				if (key_format) {
-					*key_format = config[i].key_format;
+				if (key_formats) {
+					*key_formats = (const char **) config[i].key_formats;
 				}
 				if (value_format) {
 					*value_format = config[i].value_format;
 				}
+				if (disallowed_chars) {
+					*disallowed_chars = config[i].disallowed_chars;
+				}
 			}
 			break;
 		case config_glob:
@@ -113,12 +124,15 @@ defaults_get_map_config(const char *mapname,
 				if (filter) {
 					*filter = config[i].filter;
 				}
-				if (key_format) {
-					*key_format = config[i].key_format;
+				if (key_formats) {
+					*key_formats = (const char **) config[i].key_formats;
 				}
 				if (value_format) {
 					*value_format = config[i].value_format;
 				}
+				if (disallowed_chars) {
+					*disallowed_chars = config[i].disallowed_chars;
+				}
 			}
 			break;
 		}
diff --git a/src/defaults.h b/src/defaults.h
index 486b9e5..7b93398 100644
--- a/src/defaults.h
+++ b/src/defaults.h
@@ -24,6 +24,7 @@
 void defaults_get_map_config(const char *mapname,
 			     bool_t *secure,
 			     const char **filter,
-			     const char **key_format,
-			     const char **value_format);
+			     const char ***key_formats,
+			     const char **value_format,
+			     const char **disallowed_chars);
 #endif
diff --git a/src/dummymap.c b/src/dummymap.c
index ffb4ef7..f99ea6d 100644
--- a/src/dummymap.c
+++ b/src/dummymap.c
@@ -219,13 +219,16 @@ map_match(struct plugin_state *state,
 bool_t
 map_match_id(struct plugin_state *state,
 	     const char *domain, const char *map, bool_t *secure,
-	     const char *in_id,
+	     const char *in_id, unsigned int in_index,
 	     unsigned int *key_len, char **key,
 	     unsigned int *value_len, char **value,
 	     const char **id)
 {
 	struct entry *entries;
 	int i;
+	if (in_index != 0) {
+		return FALSE;
+	}
 	if ((entries = map_find_entries(domain, map)) == NULL) {
 		return FALSE;
 	}
@@ -251,7 +254,7 @@ map_first(struct plugin_state *state,
 	  const char *domain, const char *map, bool_t *secure,
 	  unsigned int *first_key_len, char **first_key,
 	  unsigned int *first_value_len, char **first_value,
-	  const char **first_id)
+	  const char **first_id, int *first_id_index)
 {
 	struct entry *entries;
 	if ((entries = map_find_entries(domain, map)) == NULL) {
@@ -266,6 +269,7 @@ map_first(struct plugin_state *state,
 	*first_value = entries[0].value;
 	*first_value_len = strlen(entries[0].value);
 	*first_id = entries[0].id;
+	*first_id_index = 0;
 	return TRUE;
 }
 
@@ -274,8 +278,7 @@ map_next(struct plugin_state *state,
 	 const char *domain, const char *map, bool_t *secure,
 	 unsigned int prev_len, const char *prev,
 	 unsigned int *next_key_len, char **next_key,
-	 unsigned int *next_value_len, char **next_value,
-	 const char **next_id)
+	 unsigned int *next_value_len, char **next_value)
 {
 	struct entry *entries;
 	int i;
@@ -299,17 +302,16 @@ map_next(struct plugin_state *state,
 	*next_key_len = strlen(entries[i + 1].key);
 	*next_value = entries[i + 1].value;
 	*next_value_len = strlen(entries[i + 1].value);
-	*next_id = entries[i + 1].id;
 	return TRUE;
 }
 
 bool_t
 map_next_id(struct plugin_state *state,
 	    const char *domain, const char *map, bool_t *secure,
-	    const char *prev_id,
+	    const char *prev_id, int prev_id_index,
 	    unsigned int *next_key_len, char **next_key,
 	    unsigned int *next_value_len, char **next_value,
-	    const char **next_id)
+	    const char **next_id, int *next_id_index)
 {
 	struct entry *entries;
 	int i;
@@ -333,5 +335,6 @@ map_next_id(struct plugin_state *state,
 	*next_value = entries[i + 1].value;
 	*next_value_len = strlen(entries[i + 1].value);
 	*next_id = entries[i + 1].id;
+	*next_id_index = 0;
 	return TRUE;
 }
diff --git a/src/format.c b/src/format.c
index 49020fc..27f0364 100644
--- a/src/format.c
+++ b/src/format.c
@@ -50,7 +50,8 @@
 #define MAX_BUFFER_SIZE     0x100000
 static int format_expand(struct plugin_state *state,
 			 Slapi_PBlock *pb, Slapi_Entry *e,
-			 const char *domain, const char *map, const char *fmt,
+			 const char *domain, const char *map,
+			 const char *fmt, const char *disallowed,
 			 char *outbuf, int outbuf_len,
 			 char ***ref_attrs,
 			 struct format_inref_attr ***inref_attrs,
@@ -285,7 +286,8 @@ format_parse_args(struct plugin_state *state, const char *args,
 static int
 format_echo(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	    const char *domain, const char *map,
-	    const char *args, char *outbuf, int outbuf_len,
+	    const char *args, const char *disallowed,
+	    char *outbuf, int outbuf_len,
 	    char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	int ret, i, argc, len;
@@ -325,7 +327,8 @@ format_echo(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 static int
 format_list(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	    const char *domain, const char *map,
-	    const char *args, char *outbuf, int outbuf_len,
+	    const char *args, const char *disallowed,
+	    char *outbuf, int outbuf_len,
 	    char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	int ret, i, j, len, slen, count, argc;
@@ -404,7 +407,8 @@ format_list(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 static int
 format_deref(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	     const char *domain, const char *map,
-	     const char *args, char *outbuf, int outbuf_len,
+	     const char *args, const char *disallowed,
+	     char *outbuf, int outbuf_len,
 	     char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	int i, j, len, slen, ret, count, argc;
@@ -629,7 +633,8 @@ format_referred_entry_cb(Slapi_Entry *e, void *callback_data)
 static int
 format_referred(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	        const char *domain, const char *map,
-		const char *args, char *outbuf, int outbuf_len,
+		const char *args, const char *disallowed,
+		char *outbuf, int outbuf_len,
 	        char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	int i, j, len, slen, ret, count, argc;
@@ -757,7 +762,8 @@ format_referred(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 static int
 format_merge(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	     const char *domain, const char *map,
-	     const char *args, char *outbuf, int outbuf_len,
+	     const char *args, const char *disallowed,
+	     char *outbuf, int outbuf_len,
 	     char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	int ret, i, argc, len, slen, count;
@@ -779,7 +785,8 @@ format_merge(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 		/* Expand this argument. */
 		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
 				"merge: expanding ->%s<-\n", argv[i]);
-		len = format_expand(state, pb, e, domain, map, argv[i],
+		len = format_expand(state, pb, e, domain, map,
+				    argv[i], disallowed,
 				    outbuf + ret + (count ? slen : 0),
 				    outbuf_len - (ret + (count ? slen : 0)),
 				    ref_attrs, inref_attrs, FALSE);
@@ -885,6 +892,7 @@ format_match_generic(struct plugin_state *state,
 		     Slapi_PBlock *pb, Slapi_Entry *e,
 		     const char *domain, const char *map,
 		     const char *args, int min_args, int default_arg,
+		     const char *disallowed,
 		     char *outbuf, int outbuf_len,
 		     char ***ref_attrs,
 		     struct format_inref_attr ***inref_attrs,
@@ -1035,10 +1043,12 @@ static int
 format_match(struct plugin_state *state,
 	     Slapi_PBlock *pb, Slapi_Entry *e,
 	     const char *domain, const char *map,
-	     const char *args, char *outbuf, int outbuf_len,
+	     const char *args, const char *disallowed,
+	     char *outbuf, int outbuf_len,
 	     char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	return format_match_generic(state, pb, e, domain, map, args, 2, 2,
+				    disallowed,
 				    outbuf, outbuf_len, ref_attrs, inref_attrs,
 				    "format_match", format_match_cb);
 }
@@ -1062,10 +1072,12 @@ static int
 format_regmatch(struct plugin_state *state,
 	        Slapi_PBlock *pb, Slapi_Entry *e,
 		const char *domain, const char *map,
-	        const char *args, char *outbuf, int outbuf_len,
+	        const char *args, const char *disallowed,
+		char *outbuf, int outbuf_len,
 		char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	return format_match_generic(state, pb, e, domain, map, args, 2, 2,
+				    disallowed,
 				    outbuf, outbuf_len, ref_attrs, inref_attrs,
 				    "format_regmatch", format_regmatch_cb);
 }
@@ -1182,10 +1194,12 @@ static int
 format_regsub(struct plugin_state *state,
 	      Slapi_PBlock *pb, Slapi_Entry *e,
 	      const char *domain, const char *map,
-	      const char *args, char *outbuf, int outbuf_len,
+	      const char *args, const char *disallowed,
+	      char *outbuf, int outbuf_len,
 	      char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	return format_match_generic(state, pb, e, domain, map, args, 3, 3,
+				    disallowed,
 				    outbuf, outbuf_len, ref_attrs, inref_attrs,
 				    "format_regsub", format_regsub_cb);
 }
@@ -1200,7 +1214,7 @@ format_lookup_fn(const char *fnname)
 		int (*fct_ptr)(struct plugin_state *state,
 			       Slapi_PBlock *pb, Slapi_Entry *e,
 			       const char *domain, const char *map,
-			       const char *args,
+			       const char *args, const char *disallowed,
 			       char *outbuf, int outbuf_len,
 			       char ***ref_attrs,
 			       struct format_inref_attr ***inref_attrs);
@@ -1229,12 +1243,12 @@ format_lookup_fn(const char *fnname)
  * than one, fail. */
 static char *
 format_single(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
-	      const char *attr)
+	      const char *attr, const char *disallowed)
 {
 	Slapi_ValueSet *value_set;
 	Slapi_Value *value;
 	char *ret, *actual_attr;
-	const char *cret;
+	const char *cret, *d;
 	int count, disposition, buffer_flags;
 	if (slapi_vattr_values_get(e, (char *) attr, &value_set,
 				   &disposition, &actual_attr,
@@ -1247,7 +1261,17 @@ format_single(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 		if (slapi_valueset_first_value(value_set, &value) == 0) {
 			cret = slapi_value_get_string(value);
 			if (cret != NULL) {
-				ret = strdup(cret);
+				if ((disallowed != NULL) &&
+				    ((d = strpbrk(cret, disallowed)) != NULL)) {
+					slapi_log_error(SLAPI_LOG_PLUGIN,
+							state->plugin_desc->spd_id,
+							"value for \"%s\" "
+							"contains disallowed "
+							"character %c\n",
+							attr, *d);
+				} else {
+					ret = strdup(cret);
+				}
 			}
 		}
 	} else {
@@ -1493,7 +1517,8 @@ static int
 format_expand_simple(struct plugin_state *state,
 		     Slapi_PBlock *pb, Slapi_Entry *e,
 		     const char *domain, const char *map,
-		     const char *fmt, char *outbuf, int outbuf_len,
+		     const char *fmt, const char *disallowed,
+		     char *outbuf, int outbuf_len,
 		     char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	char *shortstart, *longstart, *shortend, *longend;
@@ -1588,14 +1613,14 @@ format_expand_simple(struct plugin_state *state,
 		}
 	}
 	/* Retrieve the value. */
-	tmp = format_single(state, pb, e, attribute);
+	tmp = format_single(state, pb, e, attribute, disallowed);
 	if (tmp == NULL) {
 		/* The attribute is undefined, or we're treating it as if it
 		 * is. */
 		if (default_value != NULL) {
 			/* Supply the default value, expanding it if needed. */
 			i = format_expand(state, pb, e,
-					  domain, map, default_value,
+					  domain, map, default_value, NULL,
 					  outbuf, outbuf_len,
 					  ref_attrs, inref_attrs, FALSE);
 			free(expr);
@@ -1611,7 +1636,7 @@ format_expand_simple(struct plugin_state *state,
 		if (alternate_value != NULL) {
 			/* Supply the alternate value. */
 			i = format_expand(state, pb, e,
-					  domain, map, alternate_value,
+					  domain, map, alternate_value, NULL,
 					  outbuf, outbuf_len,
 					  ref_attrs, inref_attrs, FALSE);
 			free(tmp);
@@ -1649,7 +1674,8 @@ format_expand_simple(struct plugin_state *state,
  * evaluate it, otherwise return it. */
 static int
 format_expand(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
-	      const char *domain, const char *map, const char *fmt,
+	      const char *domain, const char *map,
+	      const char *fmt, const char *disallowed,
 	      char *outbuf, int outbuf_len,
 	      char ***ref_attrs, struct format_inref_attr ***inref_attrs,
 	      bool_t is_simple_expression)
@@ -1665,7 +1691,8 @@ format_expand(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	size_t spn;
 	int (*formatfn)(struct plugin_state *state,
 		        Slapi_PBlock *pb, Slapi_Entry *e,
-			const char *domain, const char *map, const char *args,
+			const char *domain, const char *map,
+			const char *args, const char *disallowed,
 		        char *outbuf, int outbuf_len,
 			char ***ref_attrs,
 			struct format_inref_attr ***inref_attrs);
@@ -1731,6 +1758,7 @@ format_expand(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 									domain,
 									map,
 									tmp,
+									disallowed,
 									expr + j,
 									exp_size - j,
 									ref_attrs,
@@ -1838,7 +1866,8 @@ format_expand(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 				}
 				/* Call the "function". */
 				exp_used = (*formatfn)(state, pb, e,
-						       domain, map, tmp,
+						       domain, map,
+						       tmp, disallowed,
 						       expr + j, exp_size - j,
 						       ref_attrs, inref_attrs);
 				free(tmp);
@@ -1883,7 +1912,8 @@ format_expand(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 
 	if (is_simple_expression) {
 		exp_used = format_expand_simple(state, pb, e, domain, map,
-						expr, outbuf, outbuf_len,
+						expr, disallowed,
+						outbuf, outbuf_len,
 						ref_attrs, inref_attrs);
 		if (exp_used < 0) {
 			free(expr);
@@ -1907,7 +1937,7 @@ format_expand(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 static char *
 format_format(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 	      const char *domain, const char *map,
-	      const char *fmt,
+	      const char *fmt, const char *disallowed,
 	      char ***ref_attrs, struct format_inref_attr ***inref_attrs)
 {
 	char *buf, *tmp, *ret, *spd_id;
@@ -1928,8 +1958,8 @@ format_format(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 			return NULL;
 		}
 
-		i = format_expand(state, pb, e, domain, map, fmt, buf, buflen,
-				  ref_attrs, inref_attrs, FALSE);
+		i = format_expand(state, pb, e, domain, map, fmt, disallowed,
+				  buf, buflen, ref_attrs, inref_attrs, FALSE);
 		if ((i >= 0) && (i < buflen)) {
 			buf[i] = '\0';
 			ret = strdup(buf);
@@ -1975,7 +2005,7 @@ format_format(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 char *
 format_get_data(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 		const char *domain, const char *map,
-		const char *fmt,
+		const char *fmt, const char *disallowed,
 		char ***ref_attrs,
 		struct format_inref_attr ***inref_attrs)
 {
@@ -1990,7 +2020,7 @@ format_get_data(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
 		local_pb = NULL;
 	}
 
-	ret = format_format(state, pb, e, domain, map, fmt,
+	ret = format_format(state, pb, e, domain, map, fmt, disallowed,
 			    ref_attrs, inref_attrs);
 
 	/* If we supplied a PBlock, clean it up. */
diff --git a/src/format.h b/src/format.h
index 7bc4775..5728ff2 100644
--- a/src/format.h
+++ b/src/format.h
@@ -39,7 +39,7 @@ void format_free_data(char *data);
 char *format_get_data(struct plugin_state *state,
 		      struct slapi_pblock *pb, struct slapi_entry *e,
 		      const char *domain, const char *map,
-		      const char *fmt,
+		      const char *fmt, const char *disallowed_chars,
 		      char ***ref_attrs,
 		      struct format_inref_attr ***inref_attrs);
 
diff --git a/src/map.c b/src/map.c
index 0e2c190..f8ed3c7 100644
--- a/src/map.c
+++ b/src/map.c
@@ -64,14 +64,18 @@ struct {
 				/* The name of the backend entry for this
 				 * entry. */
 				char *id;
-				/* Key and value. */
-				char *key;
-				unsigned int key_len;
+				/* Keys and value. */
+				unsigned int n_keys;
+				char **keys;
+				unsigned int *key_len;
 				char *value;
 				unsigned int value_len;
+				/* Key index for comparison.  Used by the
+				 * key_trees. */
+				int key_index;
 			} *entries;
 			/* Search trees to speed up searches for entries. */
-			void *key_tree;
+			void **key_trees;
 			void *id_tree;
 			/* Callback data supplied by the map writer. */
 			void *backend_data;
@@ -105,23 +109,33 @@ t_compare_entry_by_id(const void *p1, const void *p2)
 	return strcmp(e1->id, e2->id);
 }
 static int
-t_compare_entry_by_key(const void *p1, const void *p2)
+t_compare_entry_by_nth_key(const void *p1, const void *p2)
 {
 	const struct map_entry *e1, *e2;
 	unsigned int key_len;
-	int eq;
+	int eq, i;
 	e1 = p1;
 	e2 = p2;
-	if (e1->key_len == e2->key_len) {
-		return memcmp(e1->key, e2->key, e1->key_len);
+	/* Figure out which key index to use for comparison by pulling it out
+	 * of the template (whichever one that is) -- real entries have
+	 * key_index set to -1. */
+	if (e1->key_index >= 0) {
+		i = e1->key_index;
 	} else {
-		key_len = (e1->key_len < e2->key_len) ?
-			   e1->key_len : e2->key_len;
-		eq = memcmp(e1->key, e2->key, key_len);
+		i = e2->key_index;
+	}
+	/* Same length -> straight comparison. */
+	if (e1->key_len[i] == e2->key_len[i]) {
+		return memcmp(e1->keys[i], e2->keys[i], e1->key_len[i]);
+	} else {
+		/* Compare the common length. */
+		key_len = (e1->key_len[i] < e2->key_len[i]) ?
+			   e1->key_len[i] : e2->key_len[i];
+		eq = memcmp(e1->keys[i], e2->keys[i], key_len);
 		if (eq != 0) {
 			return eq;
 		} else {
-			return (e1->key_len < e2->key_len) ? -1 : 1;
+			return (e1->key_len[i] < e2->key_len[i]) ? -1 : 1;
 		}
 	}
 }
@@ -166,13 +180,21 @@ map_data_find_map_entry(struct plugin_state *state,
 {
 	struct map_entry **entry, entry_template;
 	void **p;
-	if (map == NULL) {
+	unsigned int i;
+	if ((map == NULL) || (map->entries == NULL)) {
 		return NULL;
 	}
-	entry_template.key = (char *) key;
-	entry_template.key_len = key_len;
-	entry = tfind(&entry_template, &map->key_tree, t_compare_entry_by_key);
-	return entry ? *entry : NULL;
+	for (i = 0; i < map->entries->n_keys; i++) {
+		entry_template.keys = ((char **) &key) - i;
+		entry_template.key_len = (&key_len) - i;
+		entry_template.key_index = i;
+		entry = tfind(&entry_template, &map->key_trees[i],
+			      t_compare_entry_by_nth_key);
+		if (entry != NULL) {
+			return *entry;
+		}
+	}
+	return NULL;
 }
 
 static struct map_entry *
@@ -209,10 +231,12 @@ map_data_foreach_entry(struct plugin_state *state,
 				    bool_t secure,
 				    const char *key, unsigned int key_len,
 				    const char *value, unsigned int value_len,
-				    const char *id, void *cbdata),
+				    const char *id, int key_index,
+				    void *cbdata),
 		       void *cbdata)
 {
 	int i, j;
+	unsigned int k;
 	struct domain *domain;
 	struct map *map;
 	struct map_entry *entry;
@@ -226,14 +250,18 @@ map_data_foreach_entry(struct plugin_state *state,
 				if (all ||
 				    ((id != NULL) &&
 				     (strcmp(id, entry->id) == 0))) {
-					if (!(*fn)(domain->name, map->name,
-						   map->secure,
-						   entry->key,
-						   entry->key_len,
-						   entry->value,
-						   entry->value_len,
-						   entry->id, cbdata)) {
-						return FALSE;
+					for (k = 0; k < entry->n_keys; k++) {
+						if (!(*fn)(domain->name,
+							   map->name,
+							   map->secure,
+							   entry->keys[k],
+							   entry->key_len[k],
+							   entry->value,
+							   entry->value_len,
+							   entry->id, k,
+							   cbdata)) {
+							return FALSE;
+						}
 					}
 				}
 			}
@@ -251,7 +279,8 @@ map_data_foreach_entry_id(struct plugin_state *state, const char *id,
 				       unsigned int key_len,
 				       const char *value,
 				       unsigned int value_len,
-				       const char *id, void *cbdata),
+				       const char *id, int key_index,
+				       void *cbdata),
 			  void *cbdata)
 {
 	return map_data_foreach_entry(state, FALSE, id, fn, cbdata);
@@ -391,7 +420,7 @@ bool_t
 map_match_id(struct plugin_state *state,
 	     const char *domain_name, const char *map_name,
 	     bool_t *secure,
-	     const char *in_id,
+	     const char *in_id, unsigned int in_key_index,
 	     unsigned int *key_len, char **key,
 	     unsigned int *value_len, char **value,
 	     const char **id)
@@ -406,9 +435,15 @@ map_match_id(struct plugin_state *state,
 	if (entry == NULL) {
 		return FALSE;
 	}
+	if (entry->n_keys < 1) {
+		return FALSE;
+	}
+	if (in_key_index >= entry->n_keys) {
+		return FALSE;
+	}
 	*secure = map->secure;
-	*key_len = entry->key_len;
-	*key = entry->key;
+	*key_len = entry->key_len[in_key_index];
+	*key = entry->keys[in_key_index];
 	*value_len = entry->value_len;
 	*value = entry->value;
 	*id = entry->id;
@@ -423,7 +458,7 @@ map_first(struct plugin_state *state,
 	  bool_t *secure,
 	  unsigned int *first_key_len, char **first_key,
 	  unsigned int *first_value_len, char **first_value,
-	  const char **first_id)
+	  const char **first_id, int *first_key_index)
 {
 	struct map *map;
 	struct map_entry *entry;
@@ -436,11 +471,12 @@ map_first(struct plugin_state *state,
 		return FALSE;
 	}
 	*secure = map->secure;
-	*first_key_len = entry->key_len;
-	*first_key = entry->key;
+	*first_key_len = entry->key_len[0];
+	*first_key = entry->keys[0];
 	*first_value_len = entry->value_len;
 	*first_value = entry->value;
 	*first_id = entry->id;
+	*first_key_index = 0;
 	return TRUE;
 }
 
@@ -452,51 +488,80 @@ map_next(struct plugin_state *state,
 	 const char *domain_name, const char *map_name, bool_t *secure,
 	 unsigned int prev_len, const char *prev,
 	 unsigned int *next_key_len, char **next_key,
-	 unsigned int *next_value_len, char **next_value,
-	 const char **next_id)
+	 unsigned int *next_value_len, char **next_value)
 {
 	struct map *map;
 	struct map_entry *entry;
+	unsigned int i;
 	map = map_data_find_map(state, domain_name, map_name);
 	if (map == NULL) {
 		return FALSE;
 	}
 	entry = map_data_find_map_entry(state, map, prev_len, prev);
-	if ((entry == NULL) || (entry->next == NULL)) {
+	if (entry == NULL) {
 		return FALSE;
 	}
 	*secure = map->secure;
-	*next_key_len = entry->next->key_len;
-	*next_key = entry->next->key;
-	*next_value_len = entry->next->value_len;
-	*next_value = entry->next->value;
-	*next_id = entry->next->id;
+	for (i = 0; i < entry->n_keys; i++) {
+		if ((prev_len == entry->key_len[i]) &&
+		    (memcmp(prev, entry->keys[i], prev_len) == 0)) {
+			break;
+		}
+	}
+	if (i + 1 < entry->n_keys) {
+		*next_key_len = entry->key_len[i + 1];
+		*next_key = entry->keys[i + 1];
+		*next_value_len = entry->value_len;
+		*next_value = entry->value;
+	} else {
+		if (entry->next == NULL) {
+			return FALSE;
+		}
+		*next_key_len = entry->next->key_len[0];
+		*next_key = entry->next->keys[0];
+		*next_value_len = entry->next->value_len;
+		*next_value = entry->next->value;
+	}
 	return TRUE;
 }
 bool_t
 map_next_id(struct plugin_state *state,
 	    const char *domain_name, const char *map_name, bool_t *secure,
-	    const char *prev_id,
+	    const char *prev_id, int prev_key_index,
 	    unsigned int *next_key_len, char **next_key,
 	    unsigned int *next_value_len, char **next_value,
-	    const char **next_id)
+	    const char **next_id, int *next_key_index)
 {
 	struct map *map;
 	struct map_entry *entry;
+	unsigned int key_index;
 	map = map_data_find_map(state, domain_name, map_name);
 	if (map == NULL) {
 		return FALSE;
 	}
 	entry = map_data_find_map_entry_id(state, map, prev_id);
-	if ((entry == NULL) || (entry->next == NULL)) {
+	if (entry == NULL) {
 		return FALSE;
 	}
 	*secure = map->secure;
-	*next_key_len = entry->next->key_len;
-	*next_key = entry->next->key;
-	*next_value_len = entry->next->value_len;
-	*next_value = entry->next->value;
-	*next_id = entry->next->id;
+	if (prev_key_index + 1 < (int) entry->n_keys) {
+		*next_key_len = entry->key_len[prev_key_index + 1];
+		*next_key = entry->keys[prev_key_index + 1];
+		*next_value_len = entry->value_len;
+		*next_value = entry->value;
+		*next_id = entry->id;
+		*next_key_index = prev_key_index + 1;
+	} else {
+		if (entry->next == NULL) {
+			return FALSE;
+		}
+		*next_key_len = entry->next->key_len[0];
+		*next_key = entry->next->keys[0];
+		*next_value_len = entry->next->value_len;
+		*next_value = entry->next->value;
+		*next_id = entry->next->id;
+		*next_key_index = 0;
+	}
 	return TRUE;
 }
 
@@ -518,21 +583,31 @@ static void
 map_data_clear_map_map(struct plugin_state *state, struct map *map)
 {
 	struct map_entry *entry, *next;
+	unsigned int i;
 	/* Clear the entries list. */
 	if (map != NULL) {
 		for (entry = map->entries; entry != NULL; entry = next) {
+			/* Remove every key for this entry from the applicable
+			 * key trees, and then the ID tree. */
+			for (i = 0; i < entry->n_keys; i++) {
+				entry->key_index = i;
+				tdelete(entry, &map->key_trees[i],
+					t_compare_entry_by_nth_key);
+				entry->key_index = -1;
+			}
 			tdelete(entry, &map->id_tree, t_compare_entry_by_id);
-			tdelete(entry, &map->key_tree, t_compare_entry_by_key);
 			next = entry->next;
 			free(entry->id);
 			entry->key_len = 0;
-			free(entry->key);
+			for (i = 0; i < entry->n_keys; i++) {
+				free(entry->keys[i]);
+			}
+			free(entry->keys);
 			entry->value_len = 0;
 			free(entry->value);
 			free(entry);
 		}
 		map->entries = NULL;
-		map->key_tree = NULL;
 		map->id_tree = NULL;
 	}
 }
@@ -610,6 +685,7 @@ void
 map_data_set_map(struct plugin_state *state,
 		 const char *domain_name,
 		 const char *map_name,
+		 unsigned int n_keys,
 		 bool_t secure,
 		 void *backend_data,
 		 void (*free_backend_data)(void *backend_data))
@@ -666,13 +742,18 @@ map_data_set_map(struct plugin_state *state,
 			map = &maps[domain->n_maps];
 			memset(map, 0, sizeof(*map));
 			map->name = strdup(map_name);
+			map->key_trees = malloc(n_keys * sizeof(void *));
 			map->secure = secure;
 			map->backend_data = backend_data;
 			map->free_backend_data = free_backend_data;
-			if (map->name != NULL) {
+			map->last_changed = time(NULL);
+			if ((map->name != NULL) && (map->key_trees != NULL)) {
 				/* Copy in existing data. */
 				memcpy(maps, domain->maps,
 				       sizeof(*map) * domain->n_maps);
+				/* Clear the key tree set. */
+				memset(map->key_trees, 0,
+				       n_keys * sizeof(void *));
 				/* Switcheroo. */
 				free(domain->maps);
 				domain->maps = maps;
@@ -692,6 +773,7 @@ map_data_set_map(struct plugin_state *state,
 		}
 		map->backend_data = backend_data;
 		map->free_backend_data = free_backend_data;
+		map->last_changed = time(NULL);
 	}
 }
 
@@ -702,6 +784,7 @@ map_data_unset_map_entry(struct plugin_state *state,
 			 struct map_entry *entry)
 {
 	struct map_entry *prev, *next;
+	unsigned int i;
 	if ((map != NULL) && (entry != NULL)) {
 		prev = entry->prev;
 		next = entry->next;
@@ -714,31 +797,27 @@ map_data_unset_map_entry(struct plugin_state *state,
 		if (map->entries == entry) {
 			map->entries = next;
 		}
-		tdelete(entry, &map->key_tree, t_compare_entry_by_key);
+		/* Remove every key for this entry from the applicable key
+		 * trees, and then the ID tree. */
+		for (i = 0; i < entry->n_keys; i++) {
+			entry->key_index = i;
+			tdelete(entry, &map->key_trees[i],
+				t_compare_entry_by_nth_key);
+			entry->key_index = -1;
+		}
 		tdelete(entry, &map->id_tree, t_compare_entry_by_id);
 		free(entry->id);
-		free(entry->key);
+		/* Free the keys list. */
+		for (i = 0; i < entry->n_keys; i++) {
+			free(entry->keys[i]);
+		}
+		free(entry->keys);
+		/* The value and the key itself. */
 		free(entry->value);
 		free(entry);
 	}
 }
 
-/* Remove the entry from the map which matches the passed-in key. */
-void
-map_data_unset_entry_key(struct plugin_state *state,
-			 const char *domain_name,
-			 const char *map_name,
-			 unsigned int key_len,
-			 const char *key)
-{
-	struct map *map;
-	struct map_entry *entry;
-	map = map_data_find_map(state, domain_name, map_name);
-	entry = map_data_find_map_entry(state, map, key_len, key);
-	map_data_unset_map_entry(state, map, entry);
-	map->last_changed = time(NULL);
-}
-
 /* Remove the entry from the map which matches the passed-in ID. */
 void
 map_data_unset_entry_id(struct plugin_state *state,
@@ -760,17 +839,16 @@ map_data_set_entry(struct plugin_state *state,
 		   const char *domain_name,
 		   const char *map_name,
 		   const char *id,
-		   unsigned int key_len,
-		   char *key,
+		   unsigned int n_keys,
+		   unsigned int *key_lens,
+		   char **keys,
 		   unsigned int value_len,
 		   char *value)
 {
 	struct map *map;
 	struct map_entry *entry;
+	unsigned int i, key_len;
 	map = map_data_find_map(state, domain_name, map_name);
-	if (key_len == (unsigned int) -1) {
-		key_len = strlen(key);
-	}
 	if (value_len == (unsigned int) -1) {
 		value_len = strlen(value);
 	}
@@ -778,26 +856,81 @@ map_data_set_entry(struct plugin_state *state,
 		entry = map_data_find_map_entry_id(state, map, id);
 		if (entry != NULL) {
 			/* There's already an entry with this ID, so let's
-			 * replace its key and value. */
-			tdelete(entry, &map->key_tree, t_compare_entry_by_key);
+			 * replace its keys and value. */
+			for (i = 0; i < entry->n_keys; i++) {
+				entry->key_index = i;
+				tdelete(entry, &map->key_trees[i],
+					t_compare_entry_by_nth_key);
+				entry->key_index = -1;
+			}
 			tdelete(entry, &map->id_tree, t_compare_entry_by_id);
-			free(entry->key);
-			entry->key = xmemdup(key, key_len);
-			entry->key_len = key_len;
+			/* Free the keys. */
+			for (i = 0; i < entry->n_keys; i++) {
+				free(entry->keys[i]);
+			}
+			free(entry->keys);
+			/* Create a new keys list. */
+			entry->keys = malloc((n_keys + 1) * sizeof(char *));
+			if (entry->keys != NULL) {
+				for (i = 0; i < n_keys; i++) {
+					if (key_lens != NULL) {
+						key_len = key_lens[i];
+					} else {
+						key_len = -1;
+					}
+					if (key_len == (unsigned int) -1) {
+						key_len = strlen(keys[i]);
+					}
+					entry->keys[i] = xmemdup(keys[i],
+								 key_len);
+					entry->key_len[i] = key_len;
+				}
+				entry->keys[i] = NULL;
+			}
+			entry->n_keys = n_keys;
+			/* Replace the value and ID. */
 			free(entry->value);
+			free(entry->id);
 			entry->value = xmemdup(value, value_len);
 			entry->value_len = value_len;
-			free(entry->id);
 			entry->id = strdup(id);
-			tsearch(entry, &map->key_tree, t_compare_entry_by_key);
+			/* Add the ID to the tree and all of the keys to their
+			 * trees. */
 			tsearch(entry, &map->id_tree, t_compare_entry_by_id);
+			for (i = 0; i < n_keys; i++) {
+				entry->key_index = i;
+				tsearch(entry, &map->key_trees[i],
+					t_compare_entry_by_nth_key);
+				entry->key_index = -1;
+			}
 		} else {
 			/* There's no entry with this ID, so create one. */
 			entry = malloc(sizeof(*entry));
 			if (entry != NULL) {
 				memset(entry, 0, sizeof(*entry));
-				entry->key = xmemdup(key, key_len);
-				entry->key_len = key_len;
+				entry->keys = malloc((n_keys + 1) *
+						     sizeof(char *));
+				entry->key_len = malloc(n_keys * sizeof(int));
+				if ((entry->keys != NULL) &&
+				    (entry->key_len != NULL)) {
+					for (i = 0; i < n_keys; i++) {
+						if (key_lens != NULL) {
+							key_len = key_lens[i];
+						} else {
+							key_len = -1;
+						}
+						if (key_len == (unsigned int) -1) {
+							key_len =
+								strlen(keys[i]);
+						}
+						entry->keys[i] = xmemdup(keys[i],
+									 key_len);
+						entry->key_len[i] = key_len;
+					}
+					entry->keys[i] = NULL;
+				}
+				entry->n_keys = n_keys;
+				entry->key_index = -1;
 				entry->value = xmemdup(value, value_len);
 				entry->value_len = value_len;
 				entry->id = strdup(id);
@@ -806,8 +939,12 @@ map_data_set_entry(struct plugin_state *state,
 					map->entries->prev = entry;
 				}
 				map->entries = entry;
-				tsearch(entry, &map->key_tree,
-					t_compare_entry_by_key);
+				for (i = 0; i < entry->n_keys; i++) {
+					entry->key_index = i;
+					tsearch(entry, &map->key_trees[i],
+						t_compare_entry_by_nth_key);
+					entry->key_index = -1;
+				}
 				tsearch(entry, &map->id_tree,
 					t_compare_entry_by_id);
 			} else {
diff --git a/src/map.h b/src/map.h
index e0ae03f..30db7bc 100644
--- a/src/map.h
+++ b/src/map.h
@@ -41,7 +41,7 @@ bool_t map_match(struct plugin_state *state,
 		 unsigned int *value_len, char **value, const char **id);
 bool_t map_match_id(struct plugin_state *state,
 		    const char *domain, const char *map, bool_t *secure,
-		    const char *id_in,
+		    const char *id_in, unsigned int id_index,
 		    unsigned int *key_len, char **key,
 		    unsigned int *value_len, char **value,
 		    const char **id);
@@ -49,19 +49,18 @@ bool_t map_first(struct plugin_state *state,
 		 const char *domain, const char *map, bool_t *secure,
 		 unsigned int *first_key_len, char **first_key,
 		 unsigned int *first_value_len, char **first_value,
-		 const char **id);
+		 const char **first_id, int *first_key_index);
 bool_t map_next(struct plugin_state *state,
 		const char *domain, const char *map, bool_t *secure,
 		unsigned int prev_len, const char *prev,
 		unsigned int *next_key_len, char **next_key,
-		unsigned int *next_value_len, char **next_value,
-		const char **next_id);
+		unsigned int *next_value_len, char **next_value);
 bool_t map_next_id(struct plugin_state *state,
 		   const char *domain, const char *map, bool_t *secure,
-		   const char *prev_id,
+		   const char *prev_id, int prev_index,
 		   unsigned int *next_key_len, char **next_key,
 		   unsigned int *next_value_len, char **next_value,
-		   const char **next_id);
+		   const char **next_id, int *next_key_index);
 bool_t map_order(struct plugin_state *state,
 		 const char *domain, const char *map, bool_t *map_secure,
 		 unsigned int *order);
@@ -72,18 +71,16 @@ void map_data_unset_map(struct plugin_state *state,
 			const char *domain_name, const char *map_name);
 void map_data_set_map(struct plugin_state *state,
 		      const char *domain_name, const char *map_name,
-		      bool_t secure,
+		      unsigned int n_keys, bool_t secure,
 		      void *backend_data, void (*free_backend_data)(void *p));
-void map_data_unset_entry_key(struct plugin_state *state,
-			      const char *domain_name, const char *map_name,
-			      unsigned int key_len, const char *key);
 void map_data_unset_entry_id(struct plugin_state *state,
 			     const char *domain_name, const char *map_name,
 			     const char *id);
 void map_data_set_entry(struct plugin_state *state,
 			const char *domain_name, const char *map_name,
 			const char *id,
-			unsigned int key_len, char *key,
+			unsigned int n_keys,
+			unsigned int *key_len, char **keys,
 			unsigned int value_len, char *value);
 bool_t map_data_check_entry(struct plugin_state *state,
 			    const char *domain_name, const char *map_name,
@@ -96,7 +93,8 @@ bool_t map_data_foreach_entry_id(struct plugin_state *state, const char *id,
 					      unsigned int key_len,
 					      const char *value,
 					      unsigned int value_len,
-					      const char *id, void *cbdata),
+					      const char *id, int key_index,
+					      void *cbdata),
 				 void *cbdata);
 bool_t map_data_foreach_map(struct plugin_state *state, const char *domain_name,
 			    bool_t (*fn)(const char *domain,
diff --git a/src/nis.c b/src/nis.c
index 4ae38b2..961b3e5 100644
--- a/src/nis.c
+++ b/src/nis.c
@@ -143,6 +143,7 @@ nis_first(struct plugin_state *state,
 	struct ypreq_nokey req_nokey;
 	bool_t map_supported, map_secure;
 	const char *entry_id;
+	int entry_key_index;
 
 	memset(&req_nokey, 0, sizeof(req_nokey));
 	memset(reply_key_val, 0, sizeof(*reply_key_val));
@@ -154,7 +155,7 @@ nis_first(struct plugin_state *state,
 			      &reply_key_val->keydat.keydat_val,
 			      &reply_key_val->valdat.valdat_len,
 			      &reply_key_val->valdat.valdat_val,
-			      &entry_id) &&
+			      &entry_id, &entry_key_index) &&
 		    (map_secure ? client_secure : TRUE)) {
 			reply_key_val->status = YP_TRUE;
 			slapi_log_error(SLAPI_LOG_PLUGIN,
@@ -199,17 +200,16 @@ nis_next(struct plugin_state *state,
 			     &reply_key_val->keydat.keydat_len,
 			     &reply_key_val->keydat.keydat_val,
 			     &reply_key_val->valdat.valdat_len,
-			     &reply_key_val->valdat.valdat_val,
-			     &entry_id) &&
+			     &reply_key_val->valdat.valdat_val) &&
 		    (map_secure ? client_secure : TRUE)) {
 			reply_key_val->status = YP_TRUE;
 			slapi_log_error(SLAPI_LOG_PLUGIN,
 					state->plugin_desc->spd_id,
-					"next(%.*s/%s/%s) -> %d\n",
-					req_key.keydat.keydat_len,
-					req_key.keydat.keydat_val,
+					"next(%s/%s/%.*s) -> %d\n",
 					req_key.domain,
 					req_key.map,
+					req_key.keydat.keydat_len,
+					req_key.keydat.keydat_val,
 					reply_key_val->status);
 		} else {
 			if (map_match(state, req_key.domain, req_key.map,
@@ -228,11 +228,11 @@ nis_next(struct plugin_state *state,
 			}
 			slapi_log_error(SLAPI_LOG_PLUGIN,
 					state->plugin_desc->spd_id,
-					"next(%.*s/%s/%s) -> no more!\n",
-					req_key.keydat.keydat_len,
-					req_key.keydat.keydat_val,
+					"next(%s/%s/%.*s) -> no more!\n",
 					req_key.domain,
-					req_key.map);
+					req_key.map,
+					req_key.keydat.keydat_len,
+					req_key.keydat.keydat_val);
 		}
 		(*reply_fn)(state, cdata, reply, reply_xdrs);
 		map_unlock();
@@ -404,6 +404,7 @@ struct nis_all_cookie {
 		cookie_end2,
 	} state;
 	unsigned int id_length;
+	int key_index;
 	char id[1];
 };
 static void
@@ -412,7 +413,8 @@ nis_all_free_cookie(struct nis_all_cookie *cookie)
 	free(cookie);
 }
 static struct nis_all_cookie *
-nis_all_make_cookie(enum nis_all_cookie_state state, const char *id)
+nis_all_make_cookie(enum nis_all_cookie_state state,
+		    const char *id, int key_index)
 {
 	struct nis_all_cookie *cookie;
 	int length;
@@ -420,6 +422,9 @@ nis_all_make_cookie(enum nis_all_cookie_state state, const char *id)
 	cookie = malloc(sizeof(*cookie) + length + 1);
 	if (cookie != NULL) {
 		cookie->state = state;
+		memset(cookie->id, '\0', sizeof(cookie->id));
+		cookie->id_length = 0;
+		cookie->key_index = 0;
 		switch (cookie->state) {
 		case cookie_bad:
 		case cookie_first:
@@ -430,6 +435,7 @@ nis_all_make_cookie(enum nis_all_cookie_state state, const char *id)
 		case cookie_this:
 		case cookie_next:
 			cookie->id_length = length;
+			cookie->key_index = key_index;
 			if (length > 0) {
 				memcpy(&cookie->id, id, cookie->id_length);
 				cookie->id[length] = '\0';
@@ -458,6 +464,7 @@ nis_all(struct plugin_state *state,
 	enum nis_all_cookie_state next_state;
 	bool_t map_supported, map_secure, stop;
 	const char *entry_id;
+	int entry_key_index;
 
 	memset(&req_nokey, 0, sizeof(req_nokey));
 	reply_key = &reply_all->ypresp_all_u.val.keydat;
@@ -468,11 +475,12 @@ nis_all(struct plugin_state *state,
 			if (*continuation_cookie != NULL) {
 				cookie = *continuation_cookie;
 			} else {
-				cookie = nis_all_make_cookie(cookie_bad, NULL);
+				cookie = nis_all_make_cookie(cookie_bad,
+							     NULL, 0);
 			}
 			*continuation_cookie = NULL;
 		} else {
-			cookie = nis_all_make_cookie(cookie_bad, NULL);
+			cookie = nis_all_make_cookie(cookie_bad, NULL, 0);
 		}
 		/* Check if we even support the map. */
 		map_rdlock();
@@ -526,7 +534,8 @@ nis_all(struct plugin_state *state,
 						  &reply_key->keydat_val,
 						  &reply_val->valdat_len,
 						  &reply_val->valdat_val,
-						  &entry_id) &&
+						  &entry_id,
+						  &entry_key_index) &&
 					(map_secure ? client_secure : TRUE);
 				if (found) {
 					/* Next time grab the entry after this
@@ -564,12 +573,13 @@ nis_all(struct plugin_state *state,
 					 * entry or send end0 or end1,
 					 * whichever is appropriate. */
 					cookie = nis_all_make_cookie(next_state,
-								     entry_id);
+								     entry_id,
+								     entry_key_index);
 				} else {
 					/* Leave a note to try sending the
 					 * first entry again. */
 					cookie = nis_all_make_cookie(cookie_first,
-								     NULL);
+								     NULL, 0);
 					stop = TRUE;
 				}
 				break;
@@ -582,11 +592,13 @@ nis_all(struct plugin_state *state,
 						    req_nokey.map,
 						    &map_secure,
 						    cookie->id,
+						    cookie->key_index,
 						    &reply_key->keydat_len,
 						    &reply_key->keydat_val,
 						    &reply_val->valdat_len,
 						    &reply_val->valdat_val,
-						    &entry_id) &&
+						    &entry_id,
+						    &entry_key_index) &&
 					(map_secure ? client_secure : TRUE);
 				if (found) {
 					slapi_log_error(SLAPI_LOG_PLUGIN,
@@ -625,13 +637,15 @@ nis_all(struct plugin_state *state,
 					 * appropriate. */
 					nis_all_free_cookie(cookie);
 					cookie = nis_all_make_cookie(next_state,
-								     entry_id);
+								     entry_id,
+								     entry_key_index);
 				} else {
 					/* Leave a note to retry sending this
 					 * entry the next time. */
 					nis_all_free_cookie(cookie);
 					cookie = nis_all_make_cookie(cookie_this,
-								     entry_id);
+								     entry_id,
+								     entry_key_index);
 					stop = TRUE;
 				}
 				break;
@@ -644,22 +658,25 @@ nis_all(struct plugin_state *state,
 						     req_nokey.map,
 						     &map_secure,
 						     cookie->id,
+						     cookie->key_index,
 						     &reply_key->keydat_len,
 						     &reply_key->keydat_val,
 						     &reply_val->valdat_len,
 						     &reply_val->valdat_val,
 						     &entry_id) &&
 					(map_secure ? client_secure : TRUE);
+				entry_key_index = cookie->key_index;
 				if (found) {
 					/* Next time grab the entry after this
 					 * one. */
 					slapi_log_error(SLAPI_LOG_PLUGIN,
 							state->plugin_desc->spd_id,
-							"all(%s/%s) \"%s\" "
+							"all(%s/%s) \"%s\":%d "
 							"(retry)\n",
 							req_nokey.domain,
 							req_nokey.map,
-							cookie->id);
+							cookie->id,
+							cookie->key_index);
 					skip = FALSE;
 					reply_all->more = TRUE;
 					reply_all->ypresp_all_u.val.status = YP_TRUE;
@@ -669,11 +686,12 @@ nis_all(struct plugin_state *state,
 					 * state. */
 					slapi_log_error(SLAPI_LOG_PLUGIN,
 							state->plugin_desc->spd_id,
-							"all(%s/%s) \"%s\" "
+							"all(%s/%s) \"%s\":%d "
 							"(disappeared?)\n",
 							req_nokey.domain,
 							req_nokey.map,
-							cookie->id);
+							cookie->id,
+							cookie->key_index);
 					skip = TRUE;
 					next_state = cookie_end1;
 				}
@@ -692,7 +710,8 @@ nis_all(struct plugin_state *state,
 				 * stuck. */
 				nis_all_free_cookie(cookie);
 				cookie = nis_all_make_cookie(next_state,
-							     entry_id);
+							     entry_id,
+							     entry_key_index);
 				break;
 			case cookie_end0:
 				/* Send the end-of-map message as the first
@@ -713,7 +732,7 @@ nis_all(struct plugin_state *state,
 					/* Leave a note to finish the reply. */
 					nis_all_free_cookie(cookie);
 					cookie = nis_all_make_cookie(cookie_end2,
-								     NULL);
+								     NULL, 0);
 				} else {
 					/* Leave the note alone, so that we'll
 					 * have to try again. */
@@ -740,7 +759,7 @@ nis_all(struct plugin_state *state,
 					/* Leave a note to finish the reply. */
 					nis_all_free_cookie(cookie);
 					cookie = nis_all_make_cookie(cookie_end2,
-								     NULL);
+								     NULL, 0);
 				} else {
 					/* Leave the note alone, so that we'll
 					 * have to try again. */