r17525: This is a merge from the Google Summer of Code 2006 project by Martin Kühl

<mkhl@samba.org>.

Martin took over the work done last year by Jelmer, in last year's
SoC.  This was a substanital task, as the the ldb modules API changed
significantly during the past year, with the addition of async calls.

This changeset reimplements and enables the ldb_map ldb module and
adapts the example module and test case, both named samba3sam, to the
implementation.

The ldb_map module supports splitting an ldb database into two parts
(called the "local" and "remote" part) and storing the data in one of
them (the remote database) in a different format while the other acts
as a fallback.
This allows ldb to e.g. store to and load data from a remote LDAP
server and present it according to the Samba4 schema while still
allowing the LDAP to present and modify its data separately.

A complex example of this is the samba3sam module (by Jelmer
Vernooij), which maps data between the samba3 and samba4 schemas.

A simpler example is given by the entryUUID module (by Andrew
Bartlett), which handles some of the differences between AD and
OpenLDAP in operational attributes.  It principally maps objectGUID,
to and from entryUUID elements.  This is also an example of a module
that doesn't use the local backend as fallback storage.

This merge also splits the ldb_map.c file into smaller, more
manageable parts.
(This used to be commit af2bece4d343a9f787b2e3628848b266cec2b9f0)

11 files changed, 3380 insertions, 1302 deletions

diff --git a/source4/dsdb/samdb/ldb_modules/config.mk b/source4/dsdb/samdb/ldb_modules/config.mk
index 799d650ee7..6168a73d94 100644
--- a/source4/dsdb/samdb/ldb_modules/config.mk
+++ b/source4/dsdb/samdb/ldb_modules/config.mk
@@ -33,6 +33,18 @@ OBJ_FILES = \
 # End MODULE ldb_samldb
 ################################################
 
+################################################
+# Start MODULE ldb_entryUUID
+[MODULE::ldb_entryUUID]
+SUBSYSTEM = ldb
+INIT_FUNCTION = ldb_entryUUID_module_init
+ENABLE = YES
+OBJ_FILES = \
+		entryUUID.o
+#
+# End MODULE ldb_entryUUID
+################################################
+
 # ################################################
 # # Start MODULE ldb_proxy
 # [MODULE::ldb_proxy]
diff --git a/source4/dsdb/samdb/ldb_modules/entryUUID.c b/source4/dsdb/samdb/ldb_modules/entryUUID.c
new file mode 100644
index 0000000000..5f7efc1681
--- /dev/null
+++ b/source4/dsdb/samdb/ldb_modules/entryUUID.c
@@ -0,0 +1,182 @@
+/* 
+   ldb database module
+
+   LDAP semantics mapping module
+
+   Copyright (C) Jelmer Vernooij 2005
+   Copyright (C) Andrew Bartlett <abartlet@samba.org> 2006
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+/* 
+   This module relies on ldb_map to do all the real work, but performs
+   some of the trivial mappings between AD semantics and that provided
+   by OpenLDAP and similar servers.
+*/
+
+#include "includes.h"
+#include "ldb/include/ldb.h"
+#include "ldb/include/ldb_private.h"
+#include "ldb/include/ldb_errors.h"
+#include "ldb/modules/ldb_map.h"
+
+#include "librpc/gen_ndr/ndr_misc.h"
+#include "librpc/ndr/libndr.h"
+
+static struct ldb_val encode_guid(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+{
+	struct GUID guid;
+	NTSTATUS status = GUID_from_string((char *)val->data, &guid);
+	struct ldb_val out = data_blob(NULL, 0);
+
+	if (!NT_STATUS_IS_OK(status)) {
+		return out;
+	}
+	status = ndr_push_struct_blob(&out, ctx, &guid, 
+				      (ndr_push_flags_fn_t)ndr_push_GUID);
+	if (!NT_STATUS_IS_OK(status)) {
+		return out;
+	}
+
+	return out;
+}
+
+static struct ldb_val decode_guid(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+{
+	struct GUID *guid;
+	NTSTATUS status;
+	struct ldb_val out = data_blob(NULL, 0);
+	
+	guid = talloc(ctx, struct GUID);
+	if (guid == NULL) {
+		return out;
+	}
+	status = ndr_pull_struct_blob(val, guid, guid, 
+				      (ndr_pull_flags_fn_t)ndr_pull_GUID);
+	if (!NT_STATUS_IS_OK(status)) {
+		talloc_free(guid);
+		return out;
+	}
+	out = data_blob_string_const(GUID_string(ctx, guid));
+	talloc_free(guid);
+	return out;
+}
+
+/* The backend holds binary sids, so just copy them back */
+static struct ldb_val sid_copy(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+{
+	struct ldb_val out = data_blob(NULL, 0);
+	ldb_handler_copy(module->ldb, ctx, val, &out);
+
+	return out;
+}
+
+/* Ensure we always convert sids into binary, so the backend doesn't have to know about both forms */
+static struct ldb_val sid_always_binary(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+{
+	struct ldb_val out = data_blob(NULL, 0);
+	const struct ldb_attrib_handler *handler = ldb_attrib_handler(module->ldb, "objectSid");
+	
+	if (handler->canonicalise_fn(module->ldb, ctx, val, &out) != LDB_SUCCESS) {
+		return data_blob(NULL, 0);
+	}
+
+	return out;
+}
+
+const struct ldb_map_attribute entryUUID_attributes[] = 
+{
+	/* objectGUID */
+	{
+		.local_name = "objectGUID",
+		.type = MAP_CONVERT,
+		.u = {
+			.convert = {
+				.remote_name = "entryUUID", 
+				.convert_local = decode_guid,
+				.convert_remote = encode_guid,
+			},
+		},
+	},
+	/* objectSid */
+	{
+		.local_name = "objectSid",
+		.type = MAP_CONVERT,
+		.u = {
+			.convert = {
+				.remote_name = "objectSid", 
+				.convert_local = sid_always_binary,
+				.convert_remote = sid_copy,
+			},
+		},
+	},
+	{
+		.local_name = "whenCreated",
+		.type = MAP_RENAME,
+		.u = {
+			.rename = {
+				 .remote_name = "createTimestamp"
+			 }
+		}
+	},
+	{
+		.local_name = "whenChanged",
+		.type = MAP_RENAME,
+		.u = {
+			.rename = {
+				 .remote_name = "modifyTimestamp"
+			 }
+		}
+	},
+	{
+		.local_name = "*",
+		.type = MAP_KEEP,
+	},
+	{
+		.local_name = NULL,
+	}
+};
+
+/* the context init function */
+static int entryUUID_init(struct ldb_module *module)
+{
+        int ret;
+
+	ret = ldb_map_init(module, entryUUID_attributes, NULL, NULL);
+        if (ret != LDB_SUCCESS)
+                return ret;
+
+        return ldb_next_init(module);
+}
+
+static struct ldb_module_ops entryUUID_ops = {
+	.name		   = "entryUUID",
+	.init_context	   = entryUUID_init,
+};
+
+/* the init function */
+int ldb_entryUUID_module_init(void)
+{
+	struct ldb_module_ops ops = ldb_map_get_ops();
+	entryUUID_ops.add	= ops.add;
+	entryUUID_ops.modify	= ops.modify;
+	entryUUID_ops.del	= ops.del;
+	entryUUID_ops.rename	= ops.rename;
+	entryUUID_ops.search	= ops.search;
+	entryUUID_ops.wait	= ops.wait;
+
+	return ldb_register_module(&entryUUID_ops);
+}
diff --git a/source4/dsdb/samdb/ldb_modules/samba3sam.c b/source4/dsdb/samdb/ldb_modules/samba3sam.c
index 80cedb7b08..670d9ef0d8 100644
--- a/source4/dsdb/samdb/ldb_modules/samba3sam.c
+++ b/source4/dsdb/samdb/ldb_modules/samba3sam.c
@@ -5,11 +5,17 @@
 */
 
 #include "includes.h"
-#include "ldb/modules/ldb_map.h"
 #include "ldb/include/ldb.h"
 #include "ldb/include/ldb_private.h"
+#include "ldb/include/ldb_errors.h"
+#include "ldb/modules/ldb_map.h"
 #include "system/passwd.h"
 
+#include "librpc/gen_ndr/ndr_security.h"
+#include "librpc/ndr/libndr.h"
+#include "libcli/security/security.h"
+#include "libcli/security/proto.h"
+
 /* 
  * sambaSID -> member  (dn!)
  * sambaSIDList -> member (dn!) 
@@ -855,8 +861,33 @@ const struct ldb_map_attribute samba3_attributes[] =
 	}
 };
 
+/* the context init function */
+static int samba3sam_init(struct ldb_module *module)
+{
+        int ret;
+
+	ret = ldb_map_init(module, samba3_attributes, samba3_objectclasses, "samba3sam");
+        if (ret != LDB_SUCCESS)
+                return ret;
+
+        return ldb_next_init(module);
+}
+
+static struct ldb_module_ops samba3sam_ops = {
+	.name		   = "samba3sam",
+	.init_context	   = samba3sam_init,
+};
+
 /* the init function */
 int ldb_samba3sam_module_init(void)
 {
-	return ldb_map_init(ldb, samba3_attributes, samba3_objectclasses, "samba3sam");
+	struct ldb_module_ops ops = ldb_map_get_ops();
+	samba3sam_ops.add	= ops.add;
+	samba3sam_ops.modify	= ops.modify;
+	samba3sam_ops.del	= ops.del;
+	samba3sam_ops.rename	= ops.rename;
+	samba3sam_ops.search	= ops.search;
+	samba3sam_ops.wait	= ops.wait;
+
+	return ldb_register_module(&samba3sam_ops);
 }
diff --git a/source4/lib/ldb/config.mk b/source4/lib/ldb/config.mk
index 85a6cb6c67..7b6458dd63 100644
--- a/source4/lib/ldb/config.mk
+++ b/source4/lib/ldb/config.mk
@@ -81,13 +81,16 @@ PUBLIC_DEPENDENCIES = \
 # End MODULE ldb_ildap
 ################################################
 
-# ################################################
-# # Start MODULE ldb_map
-# [SUBSYSTEM::ldb_map]
-# PUBLIC_DEPENDENCIES = ldb
-# OBJ_FILES = modules/ldb_map.o
-# # End MODULE ldb_map
-# ################################################
+################################################
+# Start MODULE ldb_map
+[MODULE::ldb_map]
+SUBSYSTEM = ldb
+OBJ_FILES = \
+		modules/ldb_map_inbound.o \
+		modules/ldb_map_outbound.o \
+		modules/ldb_map.o
+# End MODULE ldb_map
+################################################
 
 ################################################
 # Start MODULE ldb_skel
diff --git a/source4/lib/ldb/modules/ldb_map.c b/source4/lib/ldb/modules/ldb_map.c
index 33d8fe0e4d..cdb9f5b4a9 100644
--- a/source4/lib/ldb/modules/ldb_map.c
+++ b/source4/lib/ldb/modules/ldb_map.c
@@ -1,1492 +1,1300 @@
-/* 
-   ldb database library - map backend
+/*
+   ldb database mapping module
 
    Copyright (C) Jelmer Vernooij 2005
+   Copyright (C) Martin Kuehl <mkhl@samba.org> 2006
 
-     ** NOTE! The following LGPL license applies to the ldb
-     ** library. This does NOT imply that all of Samba is released
-     ** under the LGPL
-   
-   This library is free software; you can redistribute it and/or
-   modify it under the terms of the GNU Lesser General Public
-   License as published by the Free Software Foundation; either
-   version 2 of the License, or (at your option) any later version.
+   * NOTICE: this module is NOT released under the GNU LGPL license as
+   * other ldb code. This module is release under the GNU GPL v2 or
+   * later license.
 
-   This library is distributed in the hope that it will be useful,
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   Lesser General Public License for more details.
-
-   You should have received a copy of the GNU Lesser General Public
-   License along with this library; if not, write to the Free Software
-   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
 
+/* 
+ *  Name: ldb
+ *
+ *  Component: ldb ldb_map module
+ *
+ *  Description: Map portions of data into a different format on a
+ *  remote partition.
+ *
+ *  Author: Jelmer Vernooij, Martin Kuehl
+ */
+
 #include "includes.h"
 #include "ldb/include/includes.h"
 
 #include "ldb/modules/ldb_map.h"
+#include "ldb/modules/ldb_map_private.h"
 
-/*
+/* Description of the provided ldb requests:
  - special attribute 'isMapped'
- - add/modify
- 	- split up ldb_message into fallback and mapped parts if is_mappable
- - search: 
- 	- search local one for not isMapped entries
-	- remove remote attributes from ldb_parse_tree
-	- search remote one
-	 - per record, search local one for additional data (by dn)
-	 - test if (full expression) is now true
- - delete
- 	- delete both
- - rename
- 	- rename locally and remotely
-*/
 
-static struct ldb_val map_convert_local_dn(struct ldb_module *map,
-					   TALLOC_CTX *ctx,
-					   const struct ldb_val *val);
-static struct ldb_val map_convert_remote_dn(struct ldb_module *map,
-					    TALLOC_CTX *ctx,
-					    const struct ldb_val *val);
-static struct ldb_val map_convert_local_objectclass(struct ldb_module *map,
-						    TALLOC_CTX *ctx,
-						    const struct ldb_val *val);
-static struct ldb_val map_convert_remote_objectclass(struct ldb_module *map,
-						     TALLOC_CTX *ctx,
-						     const struct ldb_val *val);
-
-static const struct ldb_map_attribute builtin_attribute_maps[] = {
-	{
-		.local_name = "dn",
-		.type = MAP_CONVERT,
-		.u = {
-			.convert = {
-				.remote_name = "dn",
-				.convert_local = map_convert_local_dn,
-				.convert_remote = map_convert_remote_dn,
-			},
-		},
-	},
-	{
-		.local_name = "objectclass",
-		.type = MAP_CONVERT,
-		.u = {
-			.convert = {
-				.remote_name = "objectclass",
-				.convert_local = map_convert_local_objectclass,
-				.convert_remote = map_convert_remote_objectclass,
-			},
-		},
-	},
-	{
-		.local_name = NULL,
-	}
-};
+ - search:
+     - if parse tree can be split
+         - search remote records w/ remote attrs and parse tree
+     - otherwise
+         - enumerate all remote records
+     - for each remote result
+         - map remote result to local message
+         - search local result
+         - is present
+             - merge local into remote result
+             - run callback on merged result
+         - otherwise
+             - run callback on remote result
+
+ - add:
+     - split message into local and remote part
+     - if local message is not empty
+         - add isMapped to local message
+         - add local message
+     - add remote message
+
+ - modify:
+     - split message into local and remote part
+     - if local message is not empty
+         - add isMapped to local message
+         - search for local record
+         - if present
+             - modify local record
+         - otherwise
+             - add local message
+     - modify remote record
+
+ - delete:
+     - search for local record
+     - if present
+         - delete local record
+     - delete remote record
+
+ - rename:
+     - search for local record
+     - if present
+         - rename local record
+         - modify local isMapped
+     - rename remote record
+*/
 
-static const struct ldb_map_objectclass *map_find_objectclass_remote(struct ldb_map_context *privdat, const char *name)
-{
-	int i;
-	for (i = 0; privdat->objectclass_maps[i].remote_name; i++) {
-		if (!ldb_attr_cmp(privdat->objectclass_maps[i].remote_name, name))
-			return &privdat->objectclass_maps[i];
-	}
 
-	return NULL;
-}
 
-struct map_private {
-	struct ldb_map_context context;
-};
+/* Private data structures
+ * ======================= */
 
-static struct ldb_map_context *map_get_privdat(struct ldb_module *module)
+/* Global private data */
+/* Extract mappings from private data. */
+const struct ldb_map_context *map_get_context(struct ldb_module *module)
 {
-	return &((struct map_private *)module->private_data)->context;
+	const struct map_private *data = talloc_get_type(module->private_data, struct map_private);
+	return &data->context;
 }
 
-/* Check whether the given attribute can fit into the specified 
- * message, obeying objectClass restrictions */
-static int map_msg_valid_attr(struct ldb_module *module, const struct ldb_message *msg, const char *attr)
+/* Create a generic request context. */
+static struct map_context *map_init_context(struct ldb_handle *h, struct ldb_request *req)
 {
-	struct ldb_map_context *map = module->private_data;
-	int i, j;
-	struct ldb_message_element *el = ldb_msg_find_element(msg, "objectClass");
+	struct map_context *ac;
 
-	if (el == NULL) {
-		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "Can't find objectClass");
-		return 0;
-	}
-
-	for (i = 0; i < el->num_values; i++) {
-		const struct ldb_map_objectclass *class = map_find_objectclass_remote(map, (char *)el->values[i].data);
-
-		if (!class) 
-			continue;
-		
-		for (j = 0; class->musts[j]; j++) {
-			if (!ldb_attr_cmp(class->musts[j], attr))
-				return 1;
-		}
-
-		for (j = 0; class->mays[j]; j++) {
-			if (!ldb_attr_cmp(class->mays[j], attr))
-				return 1;
-		}
+	ac = talloc_zero(h, struct map_context);
+	if (ac == NULL) {
+		map_oom(h->module);
+		return NULL;
 	}
 
-	return 0;
-} 
+	ac->module = h->module;
+	ac->orig_req = req;
 
+	return ac;
+}
 
-/* find an attribute by the local name */
-static const struct ldb_map_attribute *map_find_attr_local(struct ldb_map_context *privdat, const char *attr)
+/* Create a search request context. */
+struct map_search_context *map_init_search_context(struct map_context *ac, struct ldb_reply *ares)
 {
-	int i;
+	struct map_search_context *sc;
 
-	for (i = 0; privdat->attribute_maps[i].local_name; i++) {
-		if (!ldb_attr_cmp(privdat->attribute_maps[i].local_name, attr)) 
-			return &privdat->attribute_maps[i];
+	sc = talloc_zero(ac, struct map_search_context);
+	if (sc == NULL) {
+		map_oom(ac->module);
+		return NULL;
 	}
 
-	return NULL;
+	sc->ac = ac;
+	sc->local_res = NULL;
+	sc->remote_res = ares;
+
+	return sc;
 }
 
-/* Check if a given attribute can be created by doing mapping from a local attribute to a remote one */
-static int map_msg_can_map_attr(struct ldb_module *module, const struct ldb_message *msg, const char *attr_name)
+/* Create a request context and handle. */
+struct ldb_handle *map_init_handle(struct ldb_request *req, struct ldb_module *module)
 {
-	struct ldb_map_context *privdat = module->private_data;
-	int i,j;
+	struct map_context *ac;
+	struct ldb_handle *h;
 
-	for (i = 0; privdat->attribute_maps[i].local_name; i++) {
-		switch (privdat->attribute_maps[i].type) {
-		case MAP_IGNORE: /* No remote name at all */
-			continue;
-		case MAP_KEEP:
-			if (ldb_attr_cmp(attr_name, privdat->attribute_maps[i].local_name) == 0)
-				goto found;
-			break;
-		case MAP_RENAME:
-		case MAP_CONVERT:
-			if (ldb_attr_cmp(attr_name, privdat->attribute_maps[i].u.rename.remote_name) == 0)
-				goto found;
-			break;
-		case MAP_GENERATE:
-			for (j = 0; privdat->attribute_maps[i].u.generate.remote_names[j]; j++) {
-				if (ldb_attr_cmp(attr_name, privdat->attribute_maps[i].u.generate.remote_names[j]) == 0)
-					goto found;
-			}
-			break;
-		}
+	h = talloc_zero(req, struct ldb_handle);
+	if (h == NULL) {
+		map_oom(module);
+		return NULL;
 	}
 
-	return 0;
+	h->module = module;
+
+	ac = map_init_context(h, req);
+	if (ac == NULL) {
+		talloc_free(h);
+		return NULL;
+	}
 
-found:
+	h->private_data = (void *)ac;
 
-	if (ldb_msg_find_element(msg, privdat->attribute_maps[i].local_name))
-		return 1;
+	h->state = LDB_ASYNC_INIT;
+	h->status = LDB_SUCCESS;
 
-	return 0;
+	return h;
 }
 
 
+/* Dealing with DNs for different partitions
+ * ========================================= */
 
-/* find an attribute by the remote name */
-static const struct ldb_map_attribute *map_find_attr_remote(struct ldb_map_context *privdat, const char *attr)
+/* Check whether any data should be stored in the local partition. */
+BOOL map_check_local_db(struct ldb_module *module)
 {
-	int i;
+	const struct ldb_map_context *data = map_get_context(module);
 
-	for (i = 0; privdat->attribute_maps[i].local_name; i++) {
-		if (privdat->attribute_maps[i].type == MAP_IGNORE)
-			continue;
+	if (!data->remote_base_dn || !data->local_base_dn) {
+		return False;
+	}
 
-		if (privdat->attribute_maps[i].type == MAP_GENERATE)
-			continue;
+	return True;
+}
 
-		if (privdat->attribute_maps[i].type == MAP_KEEP &&
-			ldb_attr_cmp(privdat->attribute_maps[i].local_name, attr) == 0)
-			return &privdat->attribute_maps[i];
+/* WARK: verbatim copy from ldb_dn.c */
+static struct ldb_dn_component ldb_dn_copy_component(void *mem_ctx, struct ldb_dn_component *src)
+{
+	struct ldb_dn_component dst;
 
-		if ((privdat->attribute_maps[i].type == MAP_RENAME ||
-			privdat->attribute_maps[i].type == MAP_CONVERT) &&
-			ldb_attr_cmp(privdat->attribute_maps[i].u.rename.remote_name, attr) == 0) 
-			return &privdat->attribute_maps[i];
+	memset(&dst, 0, sizeof(dst));
 
+	if (src == NULL) {
+		return dst;
 	}
 
-	return NULL;
+	dst.value = ldb_val_dup(mem_ctx, &(src->value));
+	if (dst.value.data == NULL) {
+		return dst;
+	}
+
+	dst.name = talloc_strdup(mem_ctx, src->name);
+	if (dst.name == NULL) {
+		talloc_free(dst.value.data);
+	}
+
+	return dst;
 }
 
-static struct ldb_parse_tree *ldb_map_parse_tree(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_parse_tree *tree)
+/* Copy a DN but replace the old with the new base DN. */
+static struct ldb_dn *ldb_dn_rebase(void *mem_ctx, const struct ldb_dn *old, const struct ldb_dn *old_base, const struct ldb_dn *new_base)
 {
-	int i;
-	const struct ldb_map_attribute *attr;
-	struct ldb_parse_tree *new_tree;
-	enum ldb_map_attr_type map_type;
-	struct ldb_val value, newvalue;
-	struct ldb_map_context *privdat = map_get_privdat(module);
+	struct ldb_dn *new;
+	int i, offset;
 
-	if (tree == NULL)
-		return NULL;
-	
-
-	/* Find attr in question and:
-	 *  - if it has a convert_operator function, run that
-	 *  - otherwise, replace attr name with required[0] */
-
-	if (tree->operation == LDB_OP_AND || 
-		tree->operation == LDB_OP_OR) {
-		
-		new_tree = talloc_memdup(ctx, tree, sizeof(*tree));
-		new_tree->u.list.elements = talloc_array(new_tree, struct ldb_parse_tree *, tree->u.list.num_elements);
-		new_tree->u.list.num_elements = 0;
-		for (i = 0; i < tree->u.list.num_elements; i++) {
-			struct ldb_parse_tree *child = ldb_map_parse_tree(module, new_tree, tree->u.list.elements[i]);
-			
-			if (child) {
-				new_tree->u.list.elements[i] = child;
-				new_tree->u.list.num_elements++;
-			}
-		}
+	/* Perhaps we don't need to rebase at all? */
+	if (!old_base || !new_base) {
+		return ldb_dn_copy(mem_ctx, old);
+	}
 
-		return new_tree;
+	offset = old->comp_num - old_base->comp_num;
+	new = ldb_dn_copy_partial(mem_ctx, new_base, offset + new_base->comp_num);
+	for (i = 0; i < offset; i++) {
+		new->components[i] = ldb_dn_copy_component(new->components, &(old->components[i]));
 	}
-		
-	if (tree->operation == LDB_OP_NOT) {
-		struct ldb_parse_tree *child;
-		
-		new_tree = talloc_memdup(ctx, tree, sizeof(*tree));
-		child = ldb_map_parse_tree(module, new_tree, tree->u.isnot.child);
 
-		if (!child) {
-			talloc_free(new_tree);
-			return NULL;
+	return new;
+}
+
+/* Copy a DN with the base DN of the local partition. */
+static struct ldb_dn *ldb_dn_rebase_local(void *mem_ctx, const struct ldb_map_context *data, const struct ldb_dn *dn)
+{
+	return ldb_dn_rebase(mem_ctx, dn, data->remote_base_dn, data->local_base_dn);
+}
+
+/* Copy a DN with the base DN of the remote partition. */
+static struct ldb_dn *ldb_dn_rebase_remote(void *mem_ctx, const struct ldb_map_context *data, const struct ldb_dn *dn)
+{
+	return ldb_dn_rebase(mem_ctx, dn, data->local_base_dn, data->remote_base_dn);
+}
+
+/* Run a request and make sure it targets the remote partition. */
+/* TODO: free old DNs and messages? */
+int ldb_next_remote_request(struct ldb_module *module, struct ldb_request *request)
+{
+	const struct ldb_map_context *data = map_get_context(module);
+	struct ldb_message *msg;
+
+	switch (request->operation) {
+	case LDB_SEARCH:
+		if (request->op.search.base) {
+			request->op.search.base = ldb_dn_rebase_remote(request, data, request->op.search.base);
+		} else {
+			request->op.search.base = data->remote_base_dn;
+			/* TODO: adjust scope? */
 		}
+		break;
 
-		new_tree->u.isnot.child = child;
-		return new_tree;
-	}
+	case LDB_ADD:
+		msg = ldb_msg_copy_shallow(request, request->op.add.message);
+		msg->dn = ldb_dn_rebase_remote(msg, data, msg->dn);
+		request->op.add.message = msg;
+		break;
 
-	/* tree->operation is LDB_OP_EQUALITY, LDB_OP_SUBSTRING, LDB_OP_GREATER,
-	 * LDB_OP_LESS, LDB_OP_APPROX, LDB_OP_PRESENT or LDB_OP_EXTENDED
-	 *
-	 * (all have attr as the first element)
-	 */
+	case LDB_MODIFY:
+		msg = ldb_msg_copy_shallow(request, request->op.mod.message);
+		msg->dn = ldb_dn_rebase_remote(msg, data, msg->dn);
+		request->op.mod.message = msg;
+		break;
 
-	attr = map_find_attr_local(privdat, tree->u.equality.attr);
+	case LDB_DELETE:
+		request->op.del.dn = ldb_dn_rebase_remote(request, data, request->op.del.dn);
+		break;
 
-	if (!attr) {
-		ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Unable to find local attribute '%s', removing from parse tree\n", tree->u.equality.attr);
-		map_type = MAP_IGNORE;
-	} else {
-		map_type = attr->type;
-	}
+	case LDB_RENAME:
+		request->op.rename.olddn = ldb_dn_rebase_remote(request, data, request->op.rename.olddn);
+		request->op.rename.newdn = ldb_dn_rebase_remote(request, data, request->op.rename.newdn);
+		break;
 
-	if (attr && attr->convert_operator) {
-		/* Run convert_operator */
-		return attr->convert_operator(privdat, module, tree);
+	default:
+		ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+			  "Invalid remote request!\n");
+		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	if (map_type == MAP_IGNORE) {
-		ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Not mapping search on ignored attribute '%s'\n", tree->u.equality.attr);
-		return NULL;
-	}
+	return ldb_next_request(module, request);
+}
 
-	if (map_type == MAP_GENERATE) {
-		ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Can't do conversion for MAP_GENERATE in map_parse_tree without convert_operator for '%s'\n", tree->u.equality.attr);
-		return NULL;
-	}
 
-	if (tree->operation == LDB_OP_EQUALITY) {
-		value = tree->u.equality.value;
-	} else if (tree->operation == LDB_OP_LESS || tree->operation == LDB_OP_GREATER ||
-			   tree->operation == LDB_OP_APPROX) {
-		value = tree->u.comparison.value;
-	} else if (tree->operation == LDB_OP_EXTENDED) {
-		value = tree->u.extended.value;
-	}
-	
-	new_tree = talloc_memdup(ctx, tree, sizeof(*tree));
+/* Finding mappings for attributes and objectClasses
+ * ================================================= */
 
-	if (map_type == MAP_KEEP) {
-		new_tree->u.equality.attr = talloc_strdup(new_tree, tree->u.equality.attr);
-	} else { /* MAP_RENAME / MAP_CONVERT */
-		new_tree->u.equality.attr = talloc_strdup(new_tree, attr->u.rename.remote_name);
-	}
+/* Find an objectClass mapping by the local name. */
+static const struct ldb_map_objectclass *map_objectclass_find_local(const struct ldb_map_context *data, const char *name)
+{
+	int i;
 
-	if (new_tree->operation == LDB_OP_PRESENT) 
-		return new_tree;
-		
-	if (new_tree->operation == LDB_OP_SUBSTRING) {
-		new_tree->u.substring.chunks = NULL; /* FIXME! */
-		return new_tree;
+	for (i = 0; data->objectclass_maps && data->objectclass_maps[i].local_name; i++) {
+		if (ldb_attr_cmp(data->objectclass_maps[i].local_name, name) == 0) {
+			return &data->objectclass_maps[i];
+		}
 	}
 
-	if (map_type == MAP_CONVERT) {
-		if (!attr->u.convert.convert_local)
-			return NULL;
-		newvalue = attr->u.convert.convert_local(module, new_tree, &value);
-	} else {
-		newvalue = ldb_val_dup(new_tree, &value);
-	}
+	return NULL;
+}
 
-	if (new_tree->operation == LDB_OP_EQUALITY) {
-		new_tree->u.equality.value = newvalue;
-	} else if (new_tree->operation == LDB_OP_LESS || new_tree->operation == LDB_OP_GREATER ||
-			   new_tree->operation == LDB_OP_APPROX) {
-		new_tree->u.comparison.value = newvalue;
-	} else if (new_tree->operation == LDB_OP_EXTENDED) {
-		new_tree->u.extended.value = newvalue;
-		new_tree->u.extended.rule_id = talloc_strdup(new_tree, tree->u.extended.rule_id);
+/* Find an objectClass mapping by the remote name. */
+static const struct ldb_map_objectclass *map_objectclass_find_remote(const struct ldb_map_context *data, const char *name)
+{
+	int i;
+
+	for (i = 0; data->objectclass_maps && data->objectclass_maps[i].remote_name; i++) {
+		if (ldb_attr_cmp(data->objectclass_maps[i].remote_name, name) == 0) {
+			return &data->objectclass_maps[i];
+		}
 	}
-	
-	return new_tree;
+
+	return NULL;
 }
 
-/* Remote DN -> Local DN */
-static struct ldb_dn *map_remote_dn(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_dn *dn)
+/* Find an attribute mapping by the local name. */
+const struct ldb_map_attribute *map_attr_find_local(const struct ldb_map_context *data, const char *name)
 {
-	struct ldb_dn *newdn;
 	int i;
 
-	if (dn == NULL)
-		return NULL;
+	for (i = 0; data->attribute_maps[i].local_name; i++) {
+		if (ldb_attr_cmp(data->attribute_maps[i].local_name, name) == 0) {
+			return &data->attribute_maps[i];
+		}
+	}
+	for (i = 0; data->attribute_maps[i].local_name; i++) {
+		if (ldb_attr_cmp(data->attribute_maps[i].local_name, "*") == 0) {
+			return &data->attribute_maps[i];
+		}
+	}
 
-	newdn = talloc_memdup(ctx, dn, sizeof(*dn));
-	if (!newdn) 
-		return NULL;
+	return NULL;
+}
 
-	newdn->components = talloc_array(newdn, struct ldb_dn_component, newdn->comp_num); 
+/* Find an attribute mapping by the remote name. */
+const struct ldb_map_attribute *map_attr_find_remote(const struct ldb_map_context *data, const char *name)
+{
+	const struct ldb_map_attribute *wildcard = NULL;
+	int i, j;
 
-	if (!newdn->components)
-		return NULL;
+	for (i = 0; data->attribute_maps[i].local_name; i++) {
+		if (ldb_attr_cmp(data->attribute_maps[i].local_name, "*") == 0) {
+			wildcard = &data->attribute_maps[i];
+		}
 
-	/* For each rdn, map the attribute name and possibly the 
-	 * complete rdn */
-	
-	for (i = 0; i < dn->comp_num; i++) {
-		const struct ldb_map_attribute *attr = map_find_attr_remote(module->private_data, dn->components[i].name);
-		enum ldb_map_attr_type map_type;
-
-		/* Unknown attribute - leave this dn as is and hope the best... */
-		if (!attr) map_type = MAP_KEEP;
-		else map_type = attr->type;
-			
-		switch (map_type) { 
+		switch (data->attribute_maps[i].type) {
 		case MAP_IGNORE:
-		case MAP_GENERATE:
-			ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Local MAP_IGNORE or MAP_GENERATE attribute '%s' used in DN!", dn->components[i].name);
-			talloc_free(newdn);
-			return NULL;
+			break;
 
 		case MAP_KEEP:
-			newdn->components[i].name = talloc_strdup(newdn->components, dn->components[i].name);
-			newdn->components[i].value = ldb_val_dup(newdn->components, &dn->components[i].value);
+			if (ldb_attr_cmp(data->attribute_maps[i].local_name, name) == 0) {
+				return &data->attribute_maps[i];
+			}
 			break;
-			
+
+		case MAP_RENAME:
 		case MAP_CONVERT:
-			newdn->components[i].name = talloc_strdup(newdn->components, attr->local_name);
-			newdn->components[i].value = attr->u.convert.convert_remote(module, ctx, &dn->components[i].value);
+			if (ldb_attr_cmp(data->attribute_maps[i].u.rename.remote_name, name) == 0) {
+				return &data->attribute_maps[i];
+			}
 			break;
-			
-		case MAP_RENAME:
-			newdn->components[i].name = talloc_strdup(newdn->components, attr->local_name);
-			newdn->components[i].value = ldb_val_dup(newdn->components, &dn->components[i].value);
+
+		case MAP_GENERATE:
+			for (j = 0; data->attribute_maps[i].u.generate.remote_names[j]; j++) {
+				if (ldb_attr_cmp(data->attribute_maps[i].u.generate.remote_names[j], name) == 0) {
+					return &data->attribute_maps[i];
+				}
+			}
 			break;
 		}
 	}
-	return newdn;
-}
-
-/* Local DN -> Remote DN */
-static struct ldb_dn *map_local_dn(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_dn *dn)
-{	
-	struct ldb_dn *newdn;
-	int i;
-
-	if (dn == NULL)
-		return NULL;
 
-	newdn = talloc_memdup(ctx, dn, sizeof(*dn));
-	if (!newdn) 
-		return NULL;
-
-	newdn->components = talloc_array(newdn, struct ldb_dn_component, newdn->comp_num); 
+	/* We didn't find it, so return the wildcard record if one was configured */
+	return wildcard;
+}
 
-	if (!newdn->components)
-		return NULL;
 
-	/* For each rdn, map the attribute name and possibly the 
-	 * complete rdn using an equality convert_operator call */
-	
-	for (i = 0; i < dn->comp_num; i++) {
-		const struct ldb_map_attribute *attr = map_find_attr_local(module->private_data, dn->components[i].name);
-		enum ldb_map_attr_type map_type;
-
-		/* Unknown attribute - leave this dn as is and hope the best... */
-		if (!attr) map_type = MAP_KEEP; else map_type = attr->type;
-		
-		switch (map_type) 
-		{
-			case MAP_IGNORE: 
-			case MAP_GENERATE:
-			ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Local MAP_IGNORE/MAP_GENERATE attribute '%s' used in DN!", dn->components[i].name);
-			talloc_free(newdn);
-			return NULL;
+/* Mapping attributes
+ * ================== */
 
-			case MAP_CONVERT: 
-				newdn->components[i].name = talloc_strdup(newdn->components, attr->u.convert.remote_name);
-				if (attr->u.convert.convert_local == NULL) {
-					ldb_debug(module->ldb, LDB_DEBUG_ERROR, "convert_local not set for attribute '%s' used in DN!", dn->components[i].name);
-					talloc_free(newdn);
-					return NULL;
-				}
-				newdn->components[i].value = attr->u.convert.convert_local(module, newdn->components, &dn->components[i].value);
-			break;
-			
-			case MAP_RENAME:
-				newdn->components[i].name = talloc_strdup(newdn->components, attr->u.rename.remote_name);
-				newdn->components[i].value = ldb_val_dup(newdn->components, &dn->components[i].value);
-			break;
+/* Check whether an attribute will be mapped into the remote partition. */
+BOOL map_attr_check_remote(const struct ldb_map_context *data, const char *attr)
+{
+	const struct ldb_map_attribute *map = map_attr_find_local(data, attr);
 
-			case MAP_KEEP:
-				newdn->components[i].name = talloc_strdup(newdn->components, dn->components[i].name);
-				newdn->components[i].value = ldb_val_dup(newdn->components, &dn->components[i].value);
-			continue;
-		}
+	if (map == NULL) {
+		return False;
+	}
+	if (map->type == MAP_IGNORE) {
+		return False;
 	}
 
-	return newdn;
+	return True;
 }
 
-/* Loop over ldb_map_attribute array and add remote_names */
-static const char **ldb_map_attrs(struct ldb_module *module, const char *const attrs[])
+/* Map an attribute name into the remote partition. */
+const char *map_attr_map_local(void *mem_ctx, const struct ldb_map_attribute *map, const char *attr)
 {
-	int i;
-	const char **ret;
-	int ar_size = 0, last_element = 0;
-	struct ldb_map_context *privdat = map_get_privdat(module);
+	if (map == NULL) {
+		return talloc_strdup(mem_ctx, attr);
+	}
 
-	if (attrs == NULL) 
-		return NULL;
+	switch (map->type) {
+	case MAP_KEEP:
+		return talloc_strdup(mem_ctx, attr);
 
-	/* Start with good guess of number of elements */
-	for (i = 0; attrs[i]; i++);
-
-	ret = talloc_array(module, const char *, i);
-	ar_size = i;
-
-	for (i = 0; attrs[i]; i++) {
-		int j;
-		const struct ldb_map_attribute *attr = map_find_attr_local(privdat, attrs[i]);
-		enum ldb_map_attr_type map_type;
-
-		if (!attr) {
-			ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Local attribute '%s' does not have a definition!\n", attrs[i]);
-			map_type = MAP_IGNORE;
-		} else map_type = attr->type;
-
-		switch (map_type)
-		{ 
-			case MAP_IGNORE: break;
-			case MAP_KEEP: 
-				if (last_element >= ar_size) {
-					ret = talloc_realloc(module, ret, const char *, ar_size+1);
-					ar_size++;
-				}
-				ret[last_element] = attr->local_name;
-				last_element++;
-				break;
-
-			case MAP_RENAME:
-			case MAP_CONVERT:
-				if (last_element >= ar_size) {
-					ret = talloc_realloc(module, ret, const char *, ar_size+1);
-					ar_size++;
-				}
-				ret[last_element] = attr->u.rename.remote_name;
-				last_element++;
-				break;
-
-			case MAP_GENERATE:
-				/* Add remote_names[] for this attribute to the list of 
-				 * attributes to request from the remote server */
-				for (j = 0; attr->u.generate.remote_names[j]; j++) {
-					if (last_element >= ar_size) {
-						ret = talloc_realloc(module, ret, const char *, ar_size+1);
-						ar_size++;
-					}
-					ret[last_element] = attr->u.generate.remote_names[j];			
-					last_element++;
-				}
-				break;
-		} 
+	case MAP_RENAME:
+	case MAP_CONVERT:
+		return talloc_strdup(mem_ctx, map->u.rename.remote_name);
+
+	default:
+		return NULL;
 	}
-	
-	if (last_element >= ar_size) {
-		ret = talloc_realloc(module, ret, const char *, ar_size+1);
-		ar_size++;
+}
+
+/* Map an attribute name back into the local partition. */
+const char *map_attr_map_remote(void *mem_ctx, const struct ldb_map_attribute *map, const char *attr)
+{
+	if (map == NULL) {
+		return talloc_strdup(mem_ctx, attr);
 	}
 
-	ret[last_element] = NULL;
+	if (map->type == MAP_KEEP) {
+		return talloc_strdup(mem_ctx, attr);
+	}
 
-	return ret;
+	return talloc_strdup(mem_ctx, map->local_name);
 }
 
-static const char **available_local_attributes(struct ldb_module *module, const struct ldb_message *msg)
-{
-	struct ldb_map_context *privdat = map_get_privdat(module);
-	int i, j;
-	int count = 0;
-	const char **ret = talloc_array(module, const char *, 1);
-
-	ret[0] = NULL;
-
-	for (i = 0; privdat->attribute_maps[i].local_name; i++) {
-		BOOL avail = False;
-		const struct ldb_map_attribute *attr = &privdat->attribute_maps[i];
-
-		/* If all remote attributes for this attribute are present, add the 
-		 * local one to the list */
-		
-		switch (attr->type) {
-		case MAP_IGNORE: break;
-		case MAP_KEEP: 
-				avail = (ldb_msg_find_ldb_val(msg, attr->local_name) != NULL); 
-				break;
-				
-		case MAP_RENAME:
-		case MAP_CONVERT:
-				avail = (ldb_msg_find_ldb_val(msg, attr->u.rename.remote_name) != NULL);
-				break;
+/* Mapping ldb values
+ * ================== */
 
-		case MAP_GENERATE:
-				avail = True;
-				for (j = 0; attr->u.generate.remote_names[j]; j++) {
-					avail &= (BOOL)(ldb_msg_find_ldb_val(msg, attr->u.generate.remote_names[j]) != NULL);
-				}
-				break;
-		}
+/* Map an ldb value into the remote partition. */
+struct ldb_val ldb_val_map_local(struct ldb_module *module, void *mem_ctx, const struct ldb_map_attribute *map, struct ldb_val val)
+{
+	if (map && (map->type == MAP_CONVERT) && (map->u.convert.convert_local)) {
+		return map->u.convert.convert_local(module, mem_ctx, &val);
+	}
 
-		if (!avail)
-			continue;
+	return ldb_val_dup(mem_ctx, &val);
+}
 
-		ret = talloc_realloc(module, ret, const char *, count+2);
-		ret[count] = attr->local_name;
-		ret[count+1] = NULL;
-		count++;
+/* Map an ldb value back into the local partition. */
+struct ldb_val ldb_val_map_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_map_attribute *map, struct ldb_val val)
+{
+	if (map && (map->type == MAP_CONVERT) && (map->u.convert.convert_remote)) {
+		return map->u.convert.convert_remote(module, mem_ctx, &val);
 	}
 
-	return ret;
+	return ldb_val_dup(mem_ctx, &val);
 }
 
-/* Used for search */
-static struct ldb_message *ldb_map_message_incoming(struct ldb_module *module, const char * const*attrs, const struct ldb_message *mi)
+
+/* Mapping DNs
+ * =========== */
+
+/* Check whether a DN is below the local baseDN. */
+BOOL ldb_dn_check_local(struct ldb_module *module, const struct ldb_dn *dn)
 {
-	int i, j;
-	struct ldb_message *msg = talloc_zero(module, struct ldb_message);
-	struct ldb_message_element *elm, *oldelm;
-	struct ldb_map_context *privdat = map_get_privdat(module);
-	const char **newattrs = NULL;
+	const struct ldb_map_context *data = map_get_context(module);
 
-	msg->dn = map_remote_dn(module, module, mi->dn);
+	if (!data->local_base_dn) {
+		return True;
+	}
+
+	return ldb_dn_compare_base(module->ldb, data->local_base_dn, dn) == 0;
+}
 
-	/* Loop over attrs, find in ldb_map_attribute array and 
-	 * run generate() */
+/* Map a DN into the remote partition. */
+struct ldb_dn *ldb_dn_map_local(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn)
+{
+	const struct ldb_map_context *data = map_get_context(module);
+	struct ldb_dn *newdn;
+	struct ldb_dn_component *old, *new;
+	const struct ldb_map_attribute *map;
+	enum ldb_map_attr_type map_type;
+	int i;
 
-	if (attrs == NULL) {
-		/* Generate list of the local attributes that /can/ be generated
-		 * using the specific remote attributes */
+	if (dn == NULL) {
+		return NULL;
+	}
 
-		attrs = newattrs = available_local_attributes(module, mi);
+	newdn = ldb_dn_copy(mem_ctx, dn);
+	if (newdn == NULL) {
+		map_oom(module);
+		return NULL;
 	}
 
-	for (i = 0; attrs[i]; i++) {
-		const struct ldb_map_attribute *attr = map_find_attr_local(privdat, attrs[i]);
-		enum ldb_map_attr_type map_type;
+	/* For each RDN, map the component name and possibly the value */
+	for (i = 0; i < newdn->comp_num; i++) {
+		old = &dn->components[i];
+		new = &newdn->components[i];
+		map = map_attr_find_local(data, old->name);
 
-		if (!attr) {
-			ldb_debug(module->ldb, LDB_DEBUG_WARNING, "Unable to find local attribute '%s' when generating incoming message\n", attrs[i]);
-			map_type = MAP_IGNORE;
-		} else map_type = attr->type;
+		/* Unknown attribute - leave this RDN as is and hope the best... */
+		if (map == NULL) {
+			map_type = MAP_KEEP;
+		} else {
+			map_type = map->type;
+		}
 
 		switch (map_type) {
-			case MAP_IGNORE:break;
-			case MAP_RENAME:
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Renaming remote attribute %s to %s", attr->u.rename.remote_name, attr->local_name);
-				oldelm = ldb_msg_find_element(mi, attr->u.rename.remote_name);
-				if (!oldelm)
-					continue;
-
-				elm = talloc(msg, struct ldb_message_element);
-				elm->name = talloc_strdup(elm, attr->local_name);
-				elm->num_values = oldelm->num_values;
-				elm->values = talloc_array(elm, struct ldb_val, elm->num_values);
-				for (j = 0; j < oldelm->num_values; j++)
-					elm->values[j] = ldb_val_dup(elm, &oldelm->values[j]);
-
-				ldb_msg_add(msg, elm, oldelm->flags);
-				break;
-				
-			case MAP_CONVERT:
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Converting remote attribute %s to %s", attr->u.rename.remote_name, attr->local_name);
-				oldelm = ldb_msg_find_element(mi, attr->u.rename.remote_name);
-				if (!oldelm) 
-					continue;
-
-				elm = talloc(msg, struct ldb_message_element);
-				elm->name = talloc_strdup(elm, attr->local_name);
-				elm->num_values = oldelm->num_values;
-				elm->values = talloc_array(elm, struct ldb_val, elm->num_values);
-
-				for (j = 0; j < oldelm->num_values; j++)
-					elm->values[j] = attr->u.convert.convert_remote(module, elm, &oldelm->values[j]);
-
-				ldb_msg_add(msg, elm, oldelm->flags);
-				break;
-
-			case MAP_KEEP:
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Keeping remote attribute %s", attr->local_name);
-				oldelm = ldb_msg_find_element(mi, attr->local_name);
-				if (!oldelm) continue;
-				
-				elm = talloc(msg, struct ldb_message_element);
-
-				elm->num_values = oldelm->num_values;
-				elm->values = talloc_array(elm, struct ldb_val, elm->num_values);
-				for (j = 0; j < oldelm->num_values; j++)
-					elm->values[j] = ldb_val_dup(elm, &oldelm->values[j]);
-
-				elm->name = talloc_strdup(elm, oldelm->name);
-
-				ldb_msg_add(msg, elm, oldelm->flags);
-				break;
-
-			case MAP_GENERATE:
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Generating local attribute %s", attr->local_name);
-				if (!attr->u.generate.generate_local)
-					continue;
-
-				elm = attr->u.generate.generate_local(module, msg, attr->local_name, mi);
-				if (!elm) 
-					continue;
-
-				ldb_msg_add(msg, elm, elm->flags);
-				break;
-			default: 
-				ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Unknown attr->type for %s", attr->local_name);
-				break;
+		case MAP_IGNORE:
+		case MAP_GENERATE:
+			ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+				  "MAP_IGNORE/MAP_GENERATE attribute '%s' "
+				  "used in DN!\n", old->name);
+			goto failed;
+
+		case MAP_CONVERT:
+			if (map->u.convert.convert_local == NULL) {
+				ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+					  "'convert_local' not set for attribute '%s' "
+					  "used in DN!\n", old->name);
+				goto failed;
+			}
+			/* fall through */
+		case MAP_KEEP:
+		case MAP_RENAME:
+			new->name = discard_const_p(char, map_attr_map_local(newdn->components, map, old->name));
+			new->value = ldb_val_map_local(module, newdn->components, map, old->value);
+			break;
 		}
 	}
 
-	talloc_free(newattrs);
+	return newdn;
 
-	return msg;
+failed:
+	talloc_free(newdn);
+	return NULL;
 }
 
-/*
-  rename a record
-*/
-static int map_rename(struct ldb_module *module, struct ldb_request *req)
+/* Map a DN into the local partition. */
+struct ldb_dn *ldb_dn_map_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn)
 {
-	const struct ldb_dn *olddn = req->op.rename.olddn;
-	const struct ldb_dn *newdn = req->op.rename.newdn;
-	struct ldb_map_context *privdat = map_get_privdat(module);
-	struct ldb_dn *n_olddn, *n_newdn;
-	int ret;
+	const struct ldb_map_context *data = map_get_context(module);
+	struct ldb_dn *newdn;
+	struct ldb_dn_component *old, *new;
+	const struct ldb_map_attribute *map;
+	enum ldb_map_attr_type map_type;
+	int i;
 
-	n_olddn = map_local_dn(module, module, olddn);
-	n_newdn = map_local_dn(module, module, newdn);
+	if (dn == NULL) {
+		return NULL;
+	}
 
-	ret = ldb_rename(privdat->mapped_ldb, n_olddn, n_newdn);
-	if (ret != -1) {
-		ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Mapped record renamed");
-		ldb_next_request(module, req);
-	} else {
-		ret = ldb_next_request(module, req);
-	
-		if (ret != -1) {
-			ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Fallback record renamed");
-		}
+	newdn = ldb_dn_copy(mem_ctx, dn);
+	if (newdn == NULL) {
+		map_oom(module);
+		return NULL;
 	}
 
-	
-	talloc_free(n_olddn);
-	talloc_free(n_newdn);
-	
-	return ret;
-}
+	/* For each RDN, map the component name and possibly the value */
+	for (i = 0; i < newdn->comp_num; i++) {
+		old = &dn->components[i];
+		new = &newdn->components[i];
+		map = map_attr_find_remote(data, old->name);
 
-/*
-  delete a record
-*/
-static int map_delete(struct ldb_module *module, struct ldb_request *req)
-{
-	const struct ldb_dn *dn = req->op.del.dn;
-	struct ldb_map_context *privdat = map_get_privdat(module);
-	struct ldb_dn *newdn;
-	int ret;
+		/* Unknown attribute - leave this RDN as is and hope the best... */
+		if (map == NULL) {
+			map_type = MAP_KEEP;
+		} else {
+			map_type = map->type;
+		}
 
-	newdn = map_local_dn(module, module, dn);
+		switch (map_type) {
+		case MAP_IGNORE:
+		case MAP_GENERATE:
+			ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+				  "MAP_IGNORE/MAP_GENERATE attribute '%s' "
+				  "used in DN!\n", old->name);
+			goto failed;
 
-	ret = ldb_delete(privdat->mapped_ldb, newdn);
-	if (ret != -1) {
-		ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Mapped record deleted");
-	} else {
-		ret = ldb_next_request(module, req);
-		if (ret != -1) {
-			ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Fallback record deleted");
+		case MAP_CONVERT:
+			if (map->u.convert.convert_remote == NULL) {
+				ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+					  "'convert_remote' not set for attribute '%s' "
+					  "used in DN!\n", old->name);
+				goto failed;
+			}
+			/* fall through */
+		case MAP_KEEP:
+		case MAP_RENAME:
+			new->name = discard_const_p(char, map_attr_map_remote(newdn->components, map, old->name));
+			new->value = ldb_val_map_remote(module, newdn->components, map, old->value);
+			break;
 		}
 	}
 
-	req->op.del.dn = newdn;
-	ret = ldb_next_request(module, req);
-	req->op.del.dn = dn;
+	return newdn;
 
+failed:
 	talloc_free(newdn);
-
-	return ret;
+	return NULL;
 }
 
-/* search fallback database */
-static int map_search_fb(struct ldb_module *module, struct ldb_request *req)
+/* Map a DN and its base into the local partition. */
+/* TODO: This should not be required with GUIDs. */
+struct ldb_dn *ldb_dn_map_rebase_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn)
 {
-	struct ldb_parse_tree *tree = req->op.search.tree;
-	struct ldb_parse_tree t_and, t_not, t_present, *childs[2];
-	int ret;
-	char *ismapped;
+	const struct ldb_map_context *data = map_get_context(module);
+	struct ldb_dn *dn1, *dn2;
 
-	t_present.operation = LDB_OP_PRESENT;
-	ismapped = talloc_strdup(module, "isMapped");
-	t_present.u.present.attr = ismapped;
+	dn1 = ldb_dn_rebase_local(mem_ctx, data, dn);
+	dn2 = ldb_dn_map_remote(module, mem_ctx, dn1);
 
-	t_not.operation = LDB_OP_NOT;
-	t_not.u.isnot.child = &t_present;
+	talloc_free(dn1);
+	return dn2;
+}
 
-	childs[0] = &t_not;
-	childs[1] = tree;
-	t_and.operation = LDB_OP_AND;
-	t_and.u.list.num_elements = 2;
-	t_and.u.list.elements = childs;
 
-	req->op.search.tree = &t_and;
-	ret = ldb_next_request(module, req);
-	req->op.search.tree = tree;
+/* Converting DNs and objectClasses (as ldb values)
+ * ================================================ */
 
-	talloc_free(ismapped);
+/* Map a DN contained in an ldb value into the remote partition. */
+static struct ldb_val ldb_dn_convert_local(struct ldb_module *module, void *mem_ctx, const struct ldb_val *val)
+{
+	struct ldb_dn *dn, *newdn;
+	struct ldb_val newval;
 
-	return ret;
+	dn = ldb_dn_explode(mem_ctx, (char *)val->data);
+	newdn = ldb_dn_map_local(module, mem_ctx, dn);
+	talloc_free(dn);
+
+	newval.length = 0;
+	newval.data = (uint8_t *)ldb_dn_linearize(mem_ctx, newdn);
+	if (newval.data) {
+		newval.length = strlen((char *)newval.data);
+	}
+	talloc_free(newdn);
+
+	return newval;
 }
 
-/* Search in the database against which we are mapping */
-static int map_search_mp(struct ldb_module *module, struct ldb_request *req)
+/* Map a DN contained in an ldb value into the local partition. */
+static struct ldb_val ldb_dn_convert_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_val *val)
 {
-	const struct ldb_dn *base = req->op.search.base;
-	enum ldb_scope scope = req->op.search.scope;
-	struct ldb_parse_tree *tree = req->op.search.tree;
-	const char * const *attrs = req->op.search.attrs;
-	struct ldb_result *res;
-	struct ldb_request new_req;
-	struct ldb_parse_tree *new_tree;
-	struct ldb_dn *new_base;
-	struct ldb_result *newres;
-	const char **newattrs;
-	int mpret, ret;
-	struct ldb_map_context *privdat = map_get_privdat(module);
-	int i;
+	struct ldb_dn *dn, *newdn;
+	struct ldb_val newval;
 
-	/*- search mapped database */
-
-	new_tree = ldb_map_parse_tree(module, module, tree);
-	if (new_tree == NULL) {
-		/* All attributes used in the parse tree are 
-		 * local, apparently. Fall back to enumerating the complete remote 
-		 * database... Rather a slow search then no results. */
-		new_tree = talloc_zero(module, struct ldb_parse_tree);
-		new_tree->operation = LDB_OP_PRESENT;
-		new_tree->u.present.attr = talloc_strdup(new_tree, "dn");
-		return 0;
-	}
-		
-	newattrs = ldb_map_attrs(module, attrs); 
-	new_base = map_local_dn(module, module, base);
-
-	memset((char *)&(new_req), 0, sizeof(new_req));
-	new_req.operation = LDB_SEARCH;
-	new_req.op.search.base = new_base;
-	new_req.op.search.scope = scope;
-	new_req.op.search.tree = new_tree;
-	new_req.op.search.attrs = newattrs;
-
-	mpret = ldb_request(privdat->mapped_ldb, req);
-
-	newres = new_req.op.search.res;
-
-	talloc_free(new_base);
-	talloc_free(new_tree);
-	talloc_free(newattrs);
-
-	if (mpret != LDB_SUCCESS) {
-		ldb_set_errstring(module->ldb, ldb_errstring(privdat->mapped_ldb));
-		return mpret;
-	}
-
-	/*
-	 - per returned record, search fallback database for additional data (by dn)
-	 - test if (full expression) is now true
-	*/
-
-	res = talloc(module, struct ldb_result);
-	req->op.search.res = res;
-	res->msgs = talloc_array(module, struct ldb_message *, newres->count);
-	res->count = newres->count;
-
-	ret = 0;
-
-	for (i = 0; i < mpret; i++) {
-		struct ldb_request mergereq;
-		struct ldb_message *merged;
-		struct ldb_result *extrares = NULL;
-		int extraret;
-
-		/* Always get special DN's from the fallback database */
-		if (ldb_dn_is_special(newres->msgs[i]->dn))
-			continue;
-
-		merged = ldb_map_message_incoming(module, attrs, newres->msgs[i]);
-		
-		/* Merge with additional data from fallback database */
-		memset((char *)&(mergereq), 0, sizeof(mergereq)); /* zero off the request structure */
-		mergereq.operation = LDB_SEARCH;
-		mergereq.op.search.base = merged->dn;
-		mergereq.op.search.scope = LDB_SCOPE_BASE;
-		mergereq.op.search.tree = ldb_parse_tree(module, "");
-		mergereq.op.search.attrs = NULL;
-
-		extraret = ldb_next_request(module, &mergereq);
-
-		extrares = mergereq.op.search.res;
-
-		if (extraret == -1) {
-			ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Error searching for extra data!\n");
-		} else if (extraret > 1) {
-			ldb_debug(module->ldb, LDB_DEBUG_ERROR, "More than one result for extra data!\n");
-			talloc_free(newres);
-			return -1;
-		} else if (extraret == 0) {
-			ldb_debug(module->ldb, LDB_DEBUG_TRACE, "No extra data found for remote DN: %s", ldb_dn_linearize(merged, merged->dn));
-		}
-		
-		if (extraret == 1) {
-			int j;
-			ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Extra data found for remote DN: %s", ldb_dn_linearize(merged, merged->dn));
-			for (j = 0; j < extrares->msgs[0]->num_elements; j++) {
-				ldb_msg_add(merged, &(extrares->msgs[0]->elements[j]), extrares->msgs[0]->elements[j].flags);
-			}
-		}
-		
-		if (ldb_match_msg(module->ldb, merged, tree, base, scope) != 0) {
-			res->msgs[ret] = merged;
-			ret++;
-		} else {
-			ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Discarded merged message because it did not match");
-		}
-	}
+	dn = ldb_dn_explode(mem_ctx, (char *)val->data);
+	newdn = ldb_dn_map_remote(module, mem_ctx, dn);
+	talloc_free(dn);
 
-	talloc_free(newres);
+	newval.length = 0;
+	newval.data = (uint8_t *)ldb_dn_linearize(mem_ctx, newdn);
+	if (newval.data) {
+		newval.length = strlen((char *)newval.data);
+	}
+	talloc_free(newdn);
 
-	res->count = ret;
-	return LDB_SUCCESS;
+	return newval;
 }
 
-
-/*
-  search for matching records using a ldb_parse_tree
-*/
-static int map_search_bytree(struct ldb_module *module, struct ldb_request *req)
+/* Map an objectClass into the remote partition. */
+static struct ldb_val map_objectclass_convert_local(struct ldb_module *module, void *mem_ctx, const struct ldb_val *val)
 {
-	const struct ldb_dn *base = req->op.search.base;
-	struct ldb_result *fbres, *mpres, *res;
-	int i, ret;
+	const struct ldb_map_context *data = map_get_context(module);
+	const char *name = (char *)val->data;
+	const struct ldb_map_objectclass *map = map_objectclass_find_local(data, name);
+	struct ldb_val newval;
+
+	if (map) {
+		newval.data = (uint8_t*)talloc_strdup(mem_ctx, map->remote_name);
+		newval.length = strlen((char *)newval.data);
+		return newval;
+	}
 
-	ret = map_search_fb(module, req);
-	if (ret != LDB_SUCCESS)
-		return ret;
+	return ldb_val_dup(mem_ctx, val);
+}
 
-	/* special dn's are never mapped.. */
-	if (ldb_dn_is_special(base)) {
-		return ret;
+/* Generate a remote message with a mapped objectClass. */
+static void map_objectclass_generate_remote(struct ldb_module *module, const char *local_attr, const struct ldb_message *old, struct ldb_message *remote, struct ldb_message *local)
+{
+	struct ldb_message_element *el, *oc;
+	struct ldb_val val;
+	BOOL found_extensibleObject = False;
+	int i;
+
+	/* Find old local objectClass */
+	oc = ldb_msg_find_element(old, local_attr);
+	if (oc == NULL) {
+		return;
 	}
 
-	fbres = req->op.search.res;
+	/* Prepare new element */
+	el = talloc_zero(remote, struct ldb_message_element);
+	if (el == NULL) {
+		ldb_oom(module->ldb);
+		return;			/* TODO: fail? */
+	}
 
-	ret = map_search_mp(module, req);
-	if (ret != LDB_SUCCESS) {
-		return ret;
+	/* Copy local objectClass element, reverse space for an extra value */
+	el->num_values = oc->num_values + 1;
+	el->values = talloc_array(el, struct ldb_val, el->num_values);
+	if (el->values == NULL) {
+		talloc_free(el);
+		ldb_oom(module->ldb);
+		return;			/* TODO: fail? */
 	}
 
-	mpres = req->op.search.res;
+	/* Copy local element name "objectClass" */
+	el->name = talloc_strdup(el, local_attr);
 
-	/* Merge results */
-	res = talloc(module, struct ldb_result);
-	res->msgs = talloc_array(res, struct ldb_message *, fbres->count + mpres->count);
+	/* Convert all local objectClasses */
+	for (i = 0; i < el->num_values - 1; i++) {
+		el->values[i] = map_objectclass_convert_local(module, el->values, &oc->values[i]);
+		if (ldb_attr_cmp((char *)el->values[i].data, "extensibleObject") == 0) {
+			found_extensibleObject = True;
+		}
+	}
 
-	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Merging %d mapped and %d fallback messages", mpres->count, fbres->count);
+	if (!found_extensibleObject) {
+		val.data = (uint8_t *)talloc_strdup(el->values, "extensibleObject");
+		val.length = strlen((char *)val.data);
 
-	for (i = 0; i < fbres->count; i++) {
-		res->msgs[i] = talloc_steal(res->msgs, fbres->msgs[i]);
-	}
-	for (i = 0; i < mpres->count; i++) {
-		res->msgs[fbres->count + i] = talloc_steal(res->msgs, mpres->msgs[i]);
+		/* Append additional objectClass "extensibleObject" */
+		el->values[i] = val;
+	} else {
+		el->num_values--;
 	}
 
-	res->count = fbres->count + mpres->count;
-	return LDB_SUCCESS;
+	/* Add new objectClass to remote message */
+	ldb_msg_add(remote, el, 0);
 }
 
-static int msg_contains_objectclass(const struct ldb_message *msg, const char *name)
+/* Map an objectClass into the local partition. */
+static struct ldb_val map_objectclass_convert_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_val *val)
 {
-	struct ldb_message_element *el = ldb_msg_find_element(msg, "objectClass");
-	int i;
-	
-	for (i = 0; i < el->num_values; i++) {
-		if (ldb_attr_cmp((char *)el->values[i].data, name) == 0) {
-			return 1;
-		}
+	const struct ldb_map_context *data = map_get_context(module);
+	const char *name = (char *)val->data;
+	const struct ldb_map_objectclass *map = map_objectclass_find_remote(data, name);
+	struct ldb_val newval;
+
+	if (map) {
+		newval.data = (uint8_t*)talloc_strdup(mem_ctx, map->local_name);
+		newval.length = strlen((char *)newval.data);
+		return newval;
 	}
 
-	return 0;
+	return ldb_val_dup(mem_ctx, val);
 }
 
-/*
-  add a record
-*/
-static int map_add(struct ldb_module *module, struct ldb_request *req)
+/* Generate a local message with a mapped objectClass. */
+static struct ldb_message_element *map_objectclass_generate_local(struct ldb_module *module, void *mem_ctx, const char *remote_attr, const struct ldb_message *remote)
 {
-	const struct ldb_message *msg = req->op.add.message;
-	struct ldb_map_context *privdat = map_get_privdat(module);
-	struct ldb_message *fb, *mp;
-	struct ldb_message_element *ocs;
-	int ret;
+	struct ldb_message_element *el, *oc;
+	struct ldb_val val;
 	int i;
 
-	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "ldb_map_add");
-
-	if (ldb_dn_is_special(msg->dn)) {
-		ldb_debug(module->ldb, LDB_DEBUG_TRACE, "ldb_map_add: Added fallback record");
-		return ldb_next_request(module, req);
-	}
-
-	mp = talloc_zero(module, struct ldb_message);
-	mp->dn = map_local_dn(module, mp, msg->dn);
-
-	fb = talloc_zero(module, struct ldb_message);
-	fb->dn = talloc_reference(fb, msg->dn);
-
-	/* We add objectClass, so 'top' should be no problem */
-	ldb_msg_add_string(mp, "objectClass", "top");
-	
-	/* make a list of remote objectclasses that can be used 
-	 *   given the attributes that are available and add to 
-	 *   mp_msg */
-	for (i = 0; privdat->objectclass_maps[i].local_name; i++) {
-		int j, has_musts, has_baseclasses;
-		
-		/* Add this objectClass to the list if all musts are present */
-		for (j = 0; privdat->objectclass_maps[i].musts[j]; j++) {
-			if (!map_msg_can_map_attr(module, msg, privdat->objectclass_maps[i].musts[j])) {
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "map_add: Not adding objectClass %s because it is not possible to create remote attribute %s", privdat->objectclass_maps[i].local_name, privdat->objectclass_maps[i].musts[j]);
-				break;
-			}
-		}
+	/* Find old remote objectClass */
+	oc = ldb_msg_find_element(remote, remote_attr);
+	if (oc == NULL) {
+		return NULL;
+	}
 
-		has_musts = (privdat->objectclass_maps[i].musts[j] == NULL);
+	/* Prepare new element */
+	el = talloc_zero(mem_ctx, struct ldb_message_element);
+	if (el == NULL) {
+		ldb_oom(module->ldb);
+		return NULL;
+	}
 
-		/* Check if base classes are present as well */
-		for (j = 0; privdat->objectclass_maps[i].base_classes[j]; j++) {
-			if (!msg_contains_objectclass(mp, privdat->objectclass_maps[i].base_classes[j])) {
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "map_add: Not adding objectClass %s of missing base class %s", privdat->objectclass_maps[i].local_name, privdat->objectclass_maps[i].base_classes[j]);
-				break;
-			}
-		}
+	/* Copy remote objectClass element */
+	el->num_values = oc->num_values;
+	el->values = talloc_array(el, struct ldb_val, el->num_values);
+	if (el->values == NULL) {
+		talloc_free(el);
+		ldb_oom(module->ldb);
+		return NULL;
+	}
+
+	/* Copy remote element name "objectClass" */
+	el->name = talloc_strdup(el, remote_attr);
+
+	/* Convert all remote objectClasses */
+	for (i = 0; i < el->num_values; i++) {
+		el->values[i] = map_objectclass_convert_remote(module, el->values, &oc->values[i]);
+	}
+
+	val.data = (uint8_t *)talloc_strdup(el->values, "extensibleObject");
+	val.length = strlen((char *)val.data);
 
-		has_baseclasses = (privdat->objectclass_maps[i].base_classes[j] == NULL);
-		
-		/* Apparently, it contains all required elements */
-		if (has_musts && has_baseclasses) {
-			ldb_msg_add_string(mp, "objectClass", privdat->objectclass_maps[i].remote_name);	
-			ldb_debug(module->ldb, LDB_DEBUG_TRACE, "map_add: Adding objectClass %s", privdat->objectclass_maps[i].remote_name);
+	/* Remove last value if it was "extensibleObject" */
+	if (ldb_val_equal_exact(&val, &el->values[i-1])) {
+		el->num_values--;
+		el->values = talloc_realloc(el, el->values, struct ldb_val, el->num_values);
+		if (el->values == NULL) {
+			talloc_free(el);
+			ldb_oom(module->ldb);
+			return NULL;
 		}
 	}
 
-	ocs = ldb_msg_find_element(mp, "objectClass");
-	if (ocs->num_values == 1) { /* Only top */
-		ldb_debug(module->ldb, LDB_DEBUG_TRACE, "ldb_map_add: Added fallback record");
-		return ldb_next_request(module, req);
-	}
-	
-	/*
-	 * - try to map as much attributes as possible where allowed and add them to mp_msg
-	 * - add other attributes to fb_msg
-	 */
-	for (i = 0; i < msg->num_elements; i++) {
-		const struct ldb_map_attribute *attr;
-		struct ldb_message_element *elm = NULL;
-		int j, k;
-		int mapped = 0;
-
-		if (ldb_attr_cmp(msg->elements[i].name, "objectClass") == 0)
-			continue;
-
-		/* Loop over all attribute_maps with msg->elements[i].name as local_name */
-		for (k = 0; privdat->attribute_maps[k].local_name; k++) {
-			if (ldb_attr_cmp(msg->elements[i].name, privdat->attribute_maps[k].local_name) != 0)
-				continue;
-
-			attr = &privdat->attribute_maps[k];
-
-			/* Decide whether or not we need to map or fallback */
-			switch (attr->type) {
-			case MAP_GENERATE:
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Generating from %s", attr->local_name);
-				attr->u.generate.generate_remote(module, attr->local_name, msg, mp, fb);
-				mapped++;
-				continue;
-			case MAP_KEEP:
-				if (!map_msg_valid_attr(module, mp, attr->local_name))
-					continue;
-				break;
-			case MAP_IGNORE: continue; 
-			case MAP_CONVERT:
-			case MAP_RENAME: 
-				 if (!map_msg_valid_attr(module, mp, attr->u.rename.remote_name))
-					 continue;
-				 break;
-			}
+	return el;
+}
 
-			switch (attr->type) {
-			case MAP_KEEP:
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Keeping %s", attr->local_name);
-				elm = talloc(fb, struct ldb_message_element);
 
-				elm->num_values = msg->elements[i].num_values;
-				elm->values = talloc_array(elm, struct ldb_val, elm->num_values);
 
-				for (j = 0; j < elm->num_values; j++) {
-					elm->values[j] = ldb_val_dup(elm, &msg->elements[i].values[j]);
-				}
+/* Auxiliary request construction
+ * ============================== */
 
-				elm->name = talloc_strdup(elm, msg->elements[i].name);
-				break;
+/* Store the DN of a single search result in context. */
+static int map_search_self_callback(struct ldb_context *ldb, void *context, struct ldb_reply *ares)
+{
+	struct map_context *ac;
 
-			case MAP_RENAME:
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Renaming %s -> %s", attr->local_name, attr->u.rename.remote_name);
-				elm = talloc(mp, struct ldb_message_element);
+	if (context == NULL || ares == NULL) {
+		ldb_set_errstring(ldb, talloc_asprintf(ldb, "NULL Context or Result in callback"));
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
 
-				elm->name = talloc_strdup(elm, attr->u.rename.remote_name);
-				elm->num_values = msg->elements[i].num_values;
-				elm->values = talloc_array(elm, struct ldb_val, elm->num_values);
+	ac = talloc_get_type(context, struct map_context);
 
-				for (j = 0; j < elm->num_values; j++) {
-					elm->values[j] = ldb_val_dup(elm, &msg->elements[i].values[j]);
-				}
-				break;
+	/* We are interested only in the single reply */
+	if (ares->type != LDB_REPLY_ENTRY) {
+		talloc_free(ares);
+		return LDB_SUCCESS;
+	}
 
-			case MAP_CONVERT:
-				if (attr->u.convert.convert_local == NULL)
-					continue;
-				ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Converting %s -> %s", attr->local_name, attr->u.convert.remote_name);
-				elm = talloc(mp, struct ldb_message_element);
+	/* We have already found a remote DN */
+	if (ac->local_dn) {
+		ldb_set_errstring(ldb, talloc_asprintf(ldb, "Too many results to base search"));
+		talloc_free(ares);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
 
-				elm->name = talloc_strdup(elm, attr->u.rename.remote_name);
-				elm->num_values = msg->elements[i].num_values;
-				elm->values = talloc_array(elm, struct ldb_val, elm->num_values);
+	/* Store local DN */
+	ac->local_dn = ares->message->dn;
 
-				for (j = 0; j < elm->num_values; j++) {
-					elm->values[j] = attr->u.convert.convert_local(module, mp, &msg->elements[i].values[j]);
-				}
+	return LDB_SUCCESS;
+}
 
-				break;
-
-			case MAP_GENERATE:
-			case MAP_IGNORE:
-				ldb_debug(module->ldb, LDB_DEBUG_FATAL, "This line should never be reached");
-				continue;
-			} 
-			
-			ldb_msg_add(mp, elm, 0);
-			mapped++;
-		} 
-		
-		if (mapped == 0) {
-			ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Fallback storing %s", msg->elements[i].name);
-			elm = talloc(fb, struct ldb_message_element);
-
-			elm->num_values = msg->elements[i].num_values;
-			elm->values = talloc_reference(elm, msg->elements[i].values);
-			elm->name = talloc_strdup(elm, msg->elements[i].name);
-
-			ldb_msg_add(fb, elm, 0);
-		}
+/* Build a request to search a record by its DN. */
+struct ldb_request *map_search_base_req(struct map_context *ac, const struct ldb_dn *dn, const char * const *attrs, const struct ldb_parse_tree *tree, void *context, ldb_search_callback callback)
+{
+	struct ldb_request *req;
+
+	req = talloc_zero(ac, struct ldb_request);
+	if (req == NULL) {
+		map_oom(ac->module);
+		return NULL;
 	}
 
-	ret = ldb_add(privdat->mapped_ldb, mp);
-	if (ret == -1) {
-		ldb_debug(module->ldb, LDB_DEBUG_WARNING, "Adding mapped record failed: %s", ldb_errstring(privdat->mapped_ldb));
-		return -1;
+	req->operation = LDB_SEARCH;
+	req->op.search.base = dn;
+	req->op.search.scope = LDB_SCOPE_BASE;
+	req->op.search.attrs = attrs;
+
+	if (tree) {
+		req->op.search.tree = tree;
+	} else {
+		req->op.search.tree = ldb_parse_tree(req, NULL);
+		if (req->op.search.tree == NULL) {
+			talloc_free(req);
+			return NULL;
+		}
 	}
 
-	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "ldb_map_add: Added mapped record");
+	req->controls = NULL;
+	req->context = context;
+	req->callback = callback;
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, req);
 
-	ldb_msg_add_string(fb, "isMapped", "TRUE");
+	return req;
+}
 
-	req->op.add.message = fb;
-	ret = ldb_next_request(module, req);
-	req->op.add.message = msg;
-	if (ret == -1) {
-		ldb_debug(module->ldb, LDB_DEBUG_WARNING, "Adding fallback record failed: %s", ldb_errstring(module->ldb));
-		return -1;
+/* Build a request to search the local record by its DN. */
+struct ldb_request *map_search_self_req(struct map_context *ac, const struct ldb_dn *dn)
+{
+	/* attrs[] is returned from this function in
+	 * ac->search_req->op.search.attrs, so it must be static, as
+	 * otherwise the compiler can put it on the stack */
+	static const char * const attrs[] = { IS_MAPPED, NULL };
+	struct ldb_parse_tree *tree;
+
+	/* Limit search to records with 'IS_MAPPED' present */
+	/* TODO: `tree = ldb_parse_tree(ac, IS_MAPPED);' won't do. */
+	tree = talloc_zero(ac, struct ldb_parse_tree);
+	if (tree == NULL) {
+		map_oom(ac->module);
+		return NULL;
 	}
 
-	talloc_free(fb);
-	talloc_free(mp);
+	tree->operation = LDB_OP_PRESENT;
+	tree->u.present.attr = talloc_strdup(tree, IS_MAPPED);
 
-	return ret;
+	return map_search_base_req(ac, dn, attrs, tree, ac, map_search_self_callback);
 }
 
-
-/*
-  modify a record
-*/
-static int map_modify(struct ldb_module *module, struct ldb_request *req)
+/* Build a request to update the 'IS_MAPPED' attribute */
+struct ldb_request *map_build_fixup_req(struct map_context *ac, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
-	const struct ldb_message *msg = req->op.mod.message;
-	struct ldb_map_context *privdat = map_get_privdat(module);
-	struct ldb_message *fb, *mp;
-	struct ldb_message_element *elm;
-	int fb_ret, mp_ret;
-	int i,j;
-
-	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "ldb_map_modify");
-
-	if (ldb_dn_is_special(msg->dn))
-		return ldb_next_request(module, req);
-
-	fb = talloc_zero(module, struct ldb_message);
-	fb->dn = talloc_reference(fb, msg->dn);
-
-	mp = talloc_zero(module, struct ldb_message);
-	mp->dn = map_local_dn(module, mp, msg->dn);
-
-	/* Loop over mi and call generate_remote for each attribute */
-	for (i = 0; i < msg->num_elements; i++) {
-		const struct ldb_map_attribute *attr;
-		int k;
-		int mapped = 0;
-
-		if (ldb_attr_cmp(msg->elements[i].name, "isMapped") == 0)
-			continue;
-
-		for (k = 0; privdat->attribute_maps[k].local_name; k++) 
-		{
-			if (ldb_attr_cmp(privdat->attribute_maps[k].local_name, msg->elements[i].name) != 0)
-				continue;
-
-			attr = &privdat->attribute_maps[k];
-
-			switch (attr->type) {
-			case MAP_IGNORE: continue;
-			case MAP_RENAME:
-				 elm = talloc(mp, struct ldb_message_element);
-
-				 elm->name = talloc_strdup(elm, attr->u.rename.remote_name);
-				 elm->num_values = msg->elements[i].num_values;
-				 elm->values = talloc_array(elm, struct ldb_val, elm->num_values);
-				 for (j = 0; j < elm->num_values; j++) {
-					 elm->values[j] = msg->elements[i].values[j];
-				 }
-
-				 ldb_msg_add(mp, elm, msg->elements[i].flags);
-				 mapped++;
-				 continue;
-
-			case MAP_CONVERT:
-				 if (!attr->u.convert.convert_local)
-					 continue;
-				 elm = talloc(mp, struct ldb_message_element);
-
-				 elm->name = talloc_strdup(elm, attr->u.rename.remote_name);
-				 elm->num_values = msg->elements[i].num_values;
-				 elm->values = talloc_array(elm, struct ldb_val, elm->num_values);
-
-				 for (j = 0; j < elm->num_values; j++) {
-					 elm->values[j] = attr->u.convert.convert_local(module, mp, &msg->elements[i].values[j]);
-				 }
-
-				 ldb_msg_add(mp, elm, msg->elements[i].flags);
-				 mapped++;
-				 continue;
-
-			case MAP_KEEP:
-				 elm = talloc(mp, struct ldb_message_element);
-
-				 elm->num_values = msg->elements[i].num_values;
-				 elm->values = talloc_array(elm, struct ldb_val, elm->num_values);
-				 for (j = 0; j < elm->num_values; j++) {
-					 elm->values[j] = msg->elements[i].values[j];
-				 }
-
-				 elm->name = talloc_strdup(elm, msg->elements[i].name);
-
-				 ldb_msg_add(mp, elm, msg->elements[i].flags);	
-				 mapped++;
-				 continue;
-
-			case MAP_GENERATE:
-				 attr->u.generate.generate_remote(module, attr->local_name, msg, mp, fb);
-				 mapped++;
-				 continue;
-			} 
-		}
+	struct ldb_request *req;
+	struct ldb_message *msg;
+	const char *dn;
+
+	/* Prepare request */
+	req = talloc_zero(ac, struct ldb_request);
+	if (req == NULL) {
+		map_oom(ac->module);
+		return NULL;
+	}
 
-		if (mapped == 0) {/* Add to fallback message */
-			elm = talloc(fb, struct ldb_message_element);
+	/* Prepare message */
+	msg = ldb_msg_new(req);
+	if (msg == NULL) {
+		map_oom(ac->module);
+		goto failed;
+	}
 
-			elm->num_values = msg->elements[i].num_values;
-			elm->values = talloc_reference(elm, msg->elements[i].values);
-			elm->name = talloc_strdup(elm, msg->elements[i].name);
-			
-			ldb_msg_add(fb, elm, msg->elements[i].flags);	
-		}
+	/* Update local 'IS_MAPPED' to the new remote DN */
+	msg->dn = discard_const_p(struct ldb_dn, olddn);
+	dn = ldb_dn_linearize(msg, newdn);
+	if (dn == NULL) {
+		goto failed;
+	}
+	if (ldb_msg_add_empty(msg, IS_MAPPED, LDB_FLAG_MOD_REPLACE) != 0) {
+		goto failed;
+	}
+	if (ldb_msg_add_string(msg, IS_MAPPED, dn) != 0) {
+		goto failed;
 	}
 
-	if (fb->num_elements > 0) {
-		ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Modifying fallback record with %d elements", fb->num_elements);
-		req->op.mod.message = fb;
-		fb_ret = ldb_next_request(module, req);
-		if (fb_ret == -1) {
-			ldb_msg_add_string(fb, "isMapped", "TRUE");
-			req->operation = LDB_ADD;
-			req->op.add.message = fb;
-			fb_ret = ldb_next_request(module, req);
-			req->operation = LDB_MODIFY;
-		}
-		req->op.mod.message = msg;
-	} else fb_ret = 0;
-	talloc_free(fb);
+	req->operation = LDB_MODIFY;
+	req->op.mod.message = msg;
+	req->controls = NULL;
+	req->handle = NULL;
+	req->context = NULL;
+	req->callback = NULL;
 
-	if (mp->num_elements > 0) {
-		ldb_debug(module->ldb, LDB_DEBUG_TRACE, "Modifying mapped record with %d elements", mp->num_elements);
-		mp_ret = ldb_modify(privdat->mapped_ldb, mp);
-	} else mp_ret = 0;
-	talloc_free(mp);
+	return req;
 
-	return (mp_ret == -1 || fb_ret == -1)?-1:0;
+failed:
+	talloc_free(req);
+	return NULL;
 }
 
 
-static int map_request(struct ldb_module *module, struct ldb_request *req)
+/* Asynchronous call structure
+ * =========================== */
+
+/* Figure out which request is currently pending. */
+static struct ldb_request *map_get_req(struct map_context *ac)
 {
-	switch (req->operation) {
+	switch (ac->step) {
+	case MAP_SEARCH_SELF_MODIFY:
+	case MAP_SEARCH_SELF_DELETE:
+	case MAP_SEARCH_SELF_RENAME:
+		return ac->search_req;
+
+	case MAP_ADD_REMOTE:
+	case MAP_MODIFY_REMOTE:
+	case MAP_DELETE_REMOTE:
+	case MAP_RENAME_REMOTE:
+		return ac->remote_req;
+
+	case MAP_RENAME_FIXUP:
+		return ac->down_req;
+
+	case MAP_ADD_LOCAL:
+	case MAP_MODIFY_LOCAL:
+	case MAP_DELETE_LOCAL:
+	case MAP_RENAME_LOCAL:
+		return ac->local_req;
+
+	case MAP_SEARCH_REMOTE:
+		/* Can't happen */
+		break;
+	}
 
-	case LDB_SEARCH:
-		return map_search_bytree(module, req);
+	return NULL;		/* unreachable; silences a warning */
+}
 
-	case LDB_ADD:
-		return map_add(module, req);
+typedef int (*map_next_function)(struct ldb_handle *handle);
 
-	case LDB_MODIFY:
-		return map_modify(module, req);
+/* Figure out the next request to run. */
+static map_next_function map_get_next(struct map_context *ac)
+{
+	switch (ac->step) {
+	case MAP_SEARCH_REMOTE:
+		return NULL;
 
-	case LDB_DELETE:
-		return map_delete(module, req);
+	case MAP_ADD_LOCAL:
+		return map_add_do_remote;
+	case MAP_ADD_REMOTE:
+		return NULL;
 
-	case LDB_RENAME:
-		return map_rename(module, req);
+	case MAP_SEARCH_SELF_MODIFY:
+		return map_modify_do_local;
+	case MAP_MODIFY_LOCAL:
+		return map_modify_do_remote;
+	case MAP_MODIFY_REMOTE:
+		return NULL;
 
-	default:
-		return ldb_next_request(module, req);
+	case MAP_SEARCH_SELF_DELETE:
+		return map_delete_do_local;
+	case MAP_DELETE_LOCAL:
+		return map_delete_do_remote;
+	case MAP_DELETE_REMOTE:
+		return NULL;
 
+	case MAP_SEARCH_SELF_RENAME:
+		return map_rename_do_local;
+	case MAP_RENAME_LOCAL:
+		return map_rename_do_fixup;
+	case MAP_RENAME_FIXUP:
+		return map_rename_do_remote;
+	case MAP_RENAME_REMOTE:
+		return NULL;
 	}
-}
-
 
-static const struct ldb_module_ops map_ops = {
-	.name              = "map",
-	.request           = map_request
-};
+	return NULL;		/* unreachable; silences a warning */
+}
 
-static char *map_find_url(struct ldb_context *ldb, const char *name)
+/* Wait for the current pending request to finish and continue with the next. */
+static int map_wait_next(struct ldb_handle *handle)
 {
-	const char * const attrs[] = { "@MAP_URL" , NULL};
-	struct ldb_result *result = NULL;
-	struct ldb_dn *mods;
-	char *url;
+	struct map_context *ac;
+	struct ldb_request *req;
+	map_next_function next;
 	int ret;
 
-	mods = ldb_dn_string_compose(ldb, NULL, "@MAP=%s", name);
-	if (mods == NULL) {
-		ldb_debug(ldb, LDB_DEBUG_ERROR, "Can't construct DN");
-		return NULL;
+	if (handle == NULL || handle->private_data == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	ret = ldb_search(ldb, mods, LDB_SCOPE_BASE, "", attrs, &result);
-	talloc_free(mods);
-	if (ret != LDB_SUCCESS || result->count == 0) {
-		ldb_debug(ldb, LDB_DEBUG_ERROR, "Not enough results found looking for @MAP");
-		return NULL;
+	if (handle->state == LDB_ASYNC_DONE) {
+		return handle->status;
 	}
 
-	url = talloc_strdup(ldb, ldb_msg_find_string(result->msgs[0], "@MAP_URL", NULL));
+	handle->state = LDB_ASYNC_PENDING;
+	handle->status = LDB_SUCCESS;
 
-	talloc_free(result);
+	ac = talloc_get_type(handle->private_data, struct map_context);
 
-	return url;
-}
+	if (ac->step == MAP_SEARCH_REMOTE) {
+		int i;
+		for (i = 0; i < ac->num_searches; i++) {
+			req = ac->search_reqs[i];
+			ret = ldb_wait(req->handle, LDB_WAIT_NONE);
 
-/* the init function */
-struct ldb_module *ldb_map_init(struct ldb_context *ldb, const struct ldb_map_attribute *attrs, const struct ldb_map_objectclass *ocls, const char *name)
-{
-	int i, j;
-	struct ldb_module *ctx;
-	struct map_private *data;
-	char *url;
+			if (ret != LDB_SUCCESS) {
+				handle->status = ret;
+				goto done;
+			}
+			if (req->handle->status != LDB_SUCCESS) {
+				handle->status = req->handle->status;
+				goto done;
+			}
+			if (req->handle->state != LDB_ASYNC_DONE) {
+				return LDB_SUCCESS;
+			}
+		}
+	} else {
 
-	ctx = talloc(ldb, struct ldb_module);
-	if (!ctx)
-		return NULL;
+		req = map_get_req(ac);
 
-	data = talloc(ctx, struct map_private);
-	if (!data) {
-		talloc_free(ctx);
-		return NULL;
-	}
+		ret = ldb_wait(req->handle, LDB_WAIT_NONE);
 
-	data->context.mapped_ldb = ldb_init(data);
-	ldb_set_debug(data->context.mapped_ldb, ldb->debug_ops.debug, ldb->debug_ops.context);
-	url = map_find_url(ldb, name);
+		if (ret != LDB_SUCCESS) {
+			handle->status = ret;
+			goto done;
+		}
+		if (req->handle->status != LDB_SUCCESS) {
+			handle->status = req->handle->status;
+			goto done;
+		}
+		if (req->handle->state != LDB_ASYNC_DONE) {
+			return LDB_SUCCESS;
+		}
 
-	if (!url) {
-		ldb_debug(ldb, LDB_DEBUG_FATAL, "@MAP=%s not set!\n", name);
-		return NULL;
+		next = map_get_next(ac);
+		if (next) {
+			return next(handle);
+		}
 	}
 
-	if (ldb_connect(data->context.mapped_ldb, url, 0, NULL) != 0) {
-		ldb_debug(ldb, LDB_DEBUG_FATAL, "Unable to open mapped database for %s at '%s'\n", name, url);
-		return NULL;
-	}
+	ret = LDB_SUCCESS;
 
-	talloc_free(url);
+done:
+	handle->state = LDB_ASYNC_DONE;
+	return ret;
+}
 
-	/* Get list of attribute maps */
-	j = 0;
-	data->context.attribute_maps = NULL;
+/* Wait for all current pending requests to finish. */
+static int map_wait_all(struct ldb_handle *handle)
+{
+	int ret;
 
-	for (i = 0; attrs[i].local_name; i++) {
-		data->context.attribute_maps = talloc_realloc(data, data->context.attribute_maps, struct ldb_map_attribute, j+1);
-		data->context.attribute_maps[j] = attrs[i];
-		j++;
+	while (handle->state != LDB_ASYNC_DONE) {
+		ret = map_wait_next(handle);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
 	}
 
-	for (i = 0; builtin_attribute_maps[i].local_name; i++) {
-		data->context.attribute_maps = talloc_realloc(data, data->context.attribute_maps, struct ldb_map_attribute, j+1);
-		data->context.attribute_maps[j] = builtin_attribute_maps[i];
-		j++;
+	return handle->status;
+}
+
+/* Wait for pending requests to finish. */
+static int map_wait(struct ldb_handle *handle, enum ldb_wait_type type)
+{
+	if (type == LDB_WAIT_ALL) {
+		return map_wait_all(handle);
+	} else {
+		return map_wait_next(handle);
 	}
+}
 
-	data->context.attribute_maps = talloc_realloc(data, data->context.attribute_maps, struct ldb_map_attribute, j+1);
-	memset(&data->context.attribute_maps[j], 0, sizeof(struct ldb_map_attribute));
 
-	data->context.objectclass_maps = ocls;
-	ctx->private_data = data;
-	ctx->ldb = ldb;
-	ctx->prev = ctx->next = NULL;
-	ctx->ops = &map_ops;
+/* Module initialization
+ * ===================== */
 
-	return ctx;
-}
+/* Provided module operations */
+static const struct ldb_module_ops map_ops = {
+	.name		= "ldb_map",
+	.add		= map_add,
+	.modify		= map_modify,
+	.del		= map_delete,
+	.rename		= map_rename,
+	.search		= map_search,
+	.wait		= map_wait,
+};
+
+/* Builtin mappings for DNs and objectClasses */
+static const struct ldb_map_attribute builtin_attribute_maps[] = {
+	{
+		.local_name = "dn",
+		.type = MAP_CONVERT,
+		.u = {
+			.convert = {
+				 .remote_name = "dn",
+				 .convert_local = ldb_dn_convert_local,
+				 .convert_remote = ldb_dn_convert_remote,
+			 },
+		},
+	},
+	{
+		.local_name = "objectclass",
+		.type = MAP_GENERATE,
+		.u = {
+			.generate = {
+				 .remote_names = { "objectclass", NULL },
+				 .generate_local = map_objectclass_generate_local,
+				 .generate_remote = map_objectclass_generate_remote,
+			 },
+		},
+	},
+	{
+		.local_name = NULL,
+	}
+};
 
-static struct ldb_val map_convert_local_dn(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+/* Find the special 'MAP_DN_NAME' record and store local and remote
+ * base DNs in private data. */
+static int map_init_dns(struct ldb_module *module, struct ldb_map_context *data, const char *name)
 {
-	struct ldb_dn *dn, *newdn;
-	struct ldb_val *newval;
+	static const char * const attrs[] = { MAP_DN_FROM, MAP_DN_TO, NULL };
+	struct ldb_dn *dn;
+	struct ldb_message *msg;
+	struct ldb_result *res;
+	int ret;
 
-	dn = ldb_dn_explode(ctx, (char *)val->data);
+	if (!name) {
+		data->local_base_dn = NULL;
+		data->remote_base_dn = NULL;
+		return LDB_SUCCESS;
+	}
 
-	newdn = map_local_dn(module, ctx, dn);
+	dn = ldb_dn_string_compose(data, NULL, "%s=%s", MAP_DN_NAME, name);
+	if (dn == NULL) {
+		ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+			  "Failed to construct '%s' DN!\n", MAP_DN_NAME);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
 
+	ret = ldb_search(module->ldb, dn, LDB_SCOPE_BASE, NULL, attrs, &res);
 	talloc_free(dn);
-
-	newval = talloc(ctx, struct ldb_val);
-	newval->data = (uint8_t *)ldb_dn_linearize(ctx, newdn);
-	if (newval->data) {
-		newval->length = strlen((char *)newval->data);
-	} else {
-		newval->length = 0;
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+	if (res->count == 0) {
+		ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+			  "No results for '%s=%s'!\n", MAP_DN_NAME, name);
+		return LDB_ERR_CONSTRAINT_VIOLATION;
+	}
+	if (res->count > 1) {
+		ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+			  "Too many results for '%s=%s'!\n", MAP_DN_NAME, name);
+		return LDB_ERR_CONSTRAINT_VIOLATION;
 	}
 
-	talloc_free(newdn);
+	msg = res->msgs[0];
+	data->local_base_dn = ldb_msg_find_attr_as_dn(data, msg, MAP_DN_FROM);
+	data->remote_base_dn = ldb_msg_find_attr_as_dn(data, msg, MAP_DN_TO);
+	talloc_free(res);
 
-	return *newval;
+	return LDB_SUCCESS;
 }
 
-static struct ldb_val map_convert_remote_dn(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+/* Store attribute maps and objectClass maps in private data. */
+static int map_init_maps(struct ldb_module *module, struct ldb_map_context *data, const struct ldb_map_attribute *attrs, const struct ldb_map_objectclass *ocls)
 {
-	struct ldb_dn *dn, *newdn;
-	struct ldb_val *newval;
-
-	dn = ldb_dn_explode(ctx, (char *)val->data);
-
-	newdn = map_remote_dn(module, ctx, dn);
+	int i, j, last;
+	last = 0;
+
+	/* Count specified attribute maps */
+	for (i = 0; attrs[i].local_name; i++) /* noop */ ;
+	/* Count built-in attribute maps */
+	for (j = 0; builtin_attribute_maps[j].local_name; j++) /* noop */ ;
+
+	/* Store list of attribute maps */
+	data->attribute_maps = talloc_array(data, struct ldb_map_attribute, i+j+1);
+	if (data->attribute_maps == NULL) {
+		map_oom(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
 
-	talloc_free(dn);
+	/* Specified ones go first */
+	for (i = 0; attrs[i].local_name; i++) {
+		data->attribute_maps[last] = attrs[i];
+		last++;
+	}
 
-	newval = talloc(ctx, struct ldb_val);
-	newval->data = (uint8_t *)ldb_dn_linearize(ctx, newdn);
-	if (newval->data) {
-		newval->length = strlen((char *)newval->data);
-	} else {
-		newval->length = 0;
+	/* Built-in ones go last */
+	for (i = 0; builtin_attribute_maps[i].local_name; i++) {
+		data->attribute_maps[last] = builtin_attribute_maps[i];
+		last++;
 	}
 
-	talloc_free(newdn);
+	/* Ensure 'local_name == NULL' for the last entry */
+	memset(&data->attribute_maps[last], 0, sizeof(struct ldb_map_attribute));
 
-	return *newval;
+	/* Store list of objectClass maps */
+	data->objectclass_maps = ocls;
+
+	return LDB_SUCCESS;
 }
 
-static struct ldb_val map_convert_local_objectclass(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+/* Copy the list of provided module operations. */
+struct ldb_module_ops ldb_map_get_ops(void)
 {
-	int i;
-	struct ldb_map_context *map = module->private_data;
+	return map_ops;
+}
 
-	for (i = 0; map->objectclass_maps[i].local_name; i++) {
-		if (!strcmp(map->objectclass_maps[i].local_name, (char *)val->data)) {
-			struct ldb_val newval;
-			newval.data = (uint8_t*)talloc_strdup(ctx, map->objectclass_maps[i].remote_name);
-			newval.length = strlen((char *)newval.data);
+/* Initialize global private data. */
+int ldb_map_init(struct ldb_module *module, const struct ldb_map_attribute *attrs, const struct ldb_map_objectclass *ocls, const char *name)
+{
+	struct map_private *data;
+	int ret;
 
-			return ldb_val_dup(ctx, &newval);
-		}
+	/* Prepare private data */
+	data = talloc_zero(module, struct map_private);
+	if (data == NULL) {
+		map_oom(module);
+		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	return ldb_val_dup(ctx, val); 
-}
-
-static struct ldb_val map_convert_remote_objectclass(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
-{
-	int i;
-	struct ldb_map_context *map = module->private_data;
+	module->private_data = data;
 
-	for (i = 0; map->objectclass_maps[i].remote_name; i++) {
-		if (!strcmp(map->objectclass_maps[i].remote_name, (char *)val->data)) {
-			struct ldb_val newval;
-			newval.data = (uint8_t*)talloc_strdup(ctx, map->objectclass_maps[i].local_name);
-			newval.length = strlen((char *)newval.data);
+	/* Store local and remote baseDNs */
+	ret = map_init_dns(module, &(data->context), name);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(data);
+		return ret;
+	}
 
-			return ldb_val_dup(ctx, &newval);
-		}
+	/* Store list of attribute and objectClass maps */
+	ret = map_init_maps(module, &(data->context), attrs, ocls);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(data);
+		return ret;
 	}
 
-	return ldb_val_dup(ctx, val); 
+	return LDB_SUCCESS;
 }
 
+/* Usage note for initialization of this module:
+ *
+ * ldb_map is meant to be used from a different module that sets up
+ * the mappings and gets registered in ldb.
+ *
+ * 'ldb_map_init' initializes the private data of this module and
+ * stores the attribute and objectClass maps in there.	It also looks
+ * up the '@MAP' special DN so requests can be redirected to the
+ * remote partition.
+ *
+ * This function should be called from the 'init_context' op of the
+ * module using ldb_map.
+ *
+ * 'ldb_map_get_ops' returns a copy of ldb_maps module operations.
+ *
+ * It should be called from the initialize function of the using
+ * module, which should then override the 'init_context' op with a
+ * function making the appropriate calls to 'ldb_map_init'.
+ */
diff --git a/source4/lib/ldb/modules/ldb_map.h b/source4/lib/ldb/modules/ldb_map.h
index 36165a260b..f9e2086ee1 100644
--- a/source4/lib/ldb/modules/ldb_map.h
+++ b/source4/lib/ldb/modules/ldb_map.h
@@ -2,7 +2,8 @@
    ldb database library - map backend
 
    Copyright (C) Jelmer Vernooij 2005
-   	Development sponsored by the Google Summer of Code program
+   Copyright (C) Martin Kuehl <mkhl@samba.org> 2006
+	Development sponsored by the Google Summer of Code program
 
      ** NOTE! The following LGPL license applies to the ldb
      ** library. This does NOT imply that all of Samba is released
@@ -15,12 +16,12 @@
 
    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU
    Lesser General Public License for more details.
 
    You should have received a copy of the GNU Lesser General Public
    License along with this library; if not, write to the Free Software
-   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307	 USA
 */
 
 #ifndef __LDB_MAP_H__
@@ -39,10 +40,21 @@
  * while returning too many attributes in ldb_search() doesn't)
  */
 
+
+/* Name of the internal attribute pointing from the local to the
+ * remote part of a record */
+#define IS_MAPPED "isMapped"
+
+
 struct ldb_map_context;
 
-struct ldb_map_attribute 
-{
+/* convert a local ldb_val to a remote ldb_val */
+typedef struct ldb_val (*ldb_map_convert_func) (struct ldb_module *module, void *mem_ctx, const struct ldb_val *val);
+
+#define LDB_MAP_MAX_REMOTE_NAMES 10
+
+/* map from local to remote attribute */
+struct ldb_map_attribute {
 	const char *local_name; /* local name */
 
 	enum ldb_map_attr_type { 
@@ -55,8 +67,8 @@ struct ldb_map_attribute
 						multiple remote attributes. */
 	} type;
 	
-	/* if set, will be called for expressions that contain this attribute */
-	struct ldb_parse_tree *(*convert_operator) (struct ldb_map_context *, TALLOC_CTX *ctx, const struct ldb_parse_tree *);	
+	/* if set, will be called for search expressions that contain this attribute */
+	struct ldb_parse_tree *(*convert_operator)(const struct ldb_map_context *, TALLOC_CTX *ctx, const struct ldb_parse_tree *);
 
 	union { 
 		struct {
@@ -65,43 +77,46 @@ struct ldb_map_attribute
 		
 		struct {
 			const char *remote_name;
-			struct ldb_val (*convert_local) (struct ldb_module *, TALLOC_CTX *, const struct ldb_val *);
-			
+
+			/* Convert local to remote data */
+			ldb_map_convert_func convert_local;
+
+			/* Convert remote to local data */
 			/* an entry can have convert_remote set to NULL, as long as there as an entry with the same local_name 
 			 * that is non-NULL before it. */
-			struct ldb_val (*convert_remote) (struct ldb_module *, TALLOC_CTX *, const struct ldb_val *);
+			ldb_map_convert_func convert_remote;
 		} convert;
 	
 		struct {
 			/* Generate the local attribute from remote message */
-			struct ldb_message_element *(*generate_local) (
-					struct ldb_module *, 
-					TALLOC_CTX *ctx, 
-					const char *attr,
-					const struct ldb_message *remote);
+			struct ldb_message_element *(*generate_local)(struct ldb_module *, TALLOC_CTX *mem_ctx, const char *remote_attr, const struct ldb_message *remote);
 
 			/* Update remote message with information from local message */
-			void (*generate_remote) (
-					struct ldb_module *, 
-					const char *local_attr,
-					const struct ldb_message *local, 
-					struct ldb_message *remote_mp,
-					struct ldb_message *remote_fb);
+			void (*generate_remote)(struct ldb_module *, const char *local_attr, const struct ldb_message *old, struct ldb_message *remote, struct ldb_message *local);
 
 			/* Name(s) for this attribute on the remote server. This is an array since 
 			 * one local attribute's data can be split up into several attributes 
 			 * remotely */
-#define LDB_MAP_MAX_REMOTE_NAMES 10
 			const char *remote_names[LDB_MAP_MAX_REMOTE_NAMES];
+
+			/* Names of additional remote attributes
+			 * required for the generation.	 NULL
+			 * indicates that `local_attr' suffices. */
+			/*
+#define LDB_MAP_MAX_SELF_ATTRIBUTES 10
+			const char *self_attrs[LDB_MAP_MAX_SELF_ATTRIBUTES];
+			*/
 		} generate;
 	} u;
 };
 
-#define LDB_MAP_MAX_SUBCLASSES 	10
-#define LDB_MAP_MAX_MUSTS 		10
-#define LDB_MAP_MAX_MAYS 		50
-struct ldb_map_objectclass 
-{
+
+#define LDB_MAP_MAX_SUBCLASSES	10
+#define LDB_MAP_MAX_MUSTS		10
+#define LDB_MAP_MAX_MAYS		50
+
+/* map from local to remote objectClass */
+struct ldb_map_objectclass {
 	const char *local_name;
 	const char *remote_name;
 	const char *base_classes[LDB_MAP_MAX_SUBCLASSES];
@@ -109,12 +124,26 @@ struct ldb_map_objectclass
 	const char *mays[LDB_MAP_MAX_MAYS];
 };
 
-struct ldb_map_context
-{
+
+/* private context data */
+struct ldb_map_context {
 	struct ldb_map_attribute *attribute_maps;
 	/* NOTE: Always declare base classes first here */
 	const struct ldb_map_objectclass *objectclass_maps;
-	struct ldb_context *mapped_ldb;
+	/* struct ldb_context *mapped_ldb; */
+	const struct ldb_dn *local_base_dn;
+	const struct ldb_dn *remote_base_dn;
 };
 
+/* initialization function */
+int
+ldb_map_init(struct ldb_module *module,
+	     const struct ldb_map_attribute *attrs,
+	     const struct ldb_map_objectclass *ocls,
+	     const char *name);
+
+/* get copy of map_ops */
+struct ldb_module_ops
+ldb_map_get_ops(void);
+
 #endif /* __LDB_MAP_H__ */
diff --git a/source4/lib/ldb/modules/ldb_map_inbound.c b/source4/lib/ldb/modules/ldb_map_inbound.c
new file mode 100644
index 0000000000..b9119f341a
--- /dev/null
+++ b/source4/lib/ldb/modules/ldb_map_inbound.c
@@ -0,0 +1,724 @@
+/*
+   ldb database mapping module
+
+   Copyright (C) Jelmer Vernooij 2005
+   Copyright (C) Martin Kuehl <mkhl@samba.org> 2006
+
+   * NOTICE: this module is NOT released under the GNU LGPL license as
+   * other ldb code. This module is release under the GNU GPL v2 or
+   * later license.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#include "includes.h"
+#include "ldb/include/includes.h"
+
+#include "ldb/modules/ldb_map.h"
+#include "ldb/modules/ldb_map_private.h"
+
+
+/* Mapping message elements
+ * ======================== */
+
+/* Map a message element into the remote partition. */
+static struct ldb_message_element *ldb_msg_el_map_local(struct ldb_module *module, void *mem_ctx, const struct ldb_map_attribute *map, const struct ldb_message_element *old)
+{
+	struct ldb_message_element *el;
+	int i;
+
+	el = talloc_zero(mem_ctx, struct ldb_message_element);
+	if (el == NULL) {
+		map_oom(module);
+		return NULL;
+	}
+
+	el->num_values = old->num_values;
+	el->values = talloc_array(el, struct ldb_val, el->num_values);
+	if (el->values == NULL) {
+		talloc_free(el);
+		map_oom(module);
+		return NULL;
+	}
+
+	el->name = map_attr_map_local(el, map, old->name);
+
+	for (i = 0; i < el->num_values; i++) {
+		el->values[i] = ldb_val_map_local(module, el->values, map, old->values[i]);
+	}
+
+	return el;
+}
+
+/* Add a message element either to a local or to a remote message,
+ * depending on whether it goes into the local or remote partition. */
+static int ldb_msg_el_partition(struct ldb_module *module, struct ldb_message *local, struct ldb_message *remote, const struct ldb_message *msg, const char *attr_name, /* const char * const names[], */ const struct ldb_message_element *old)
+{
+	const struct ldb_map_context *data = map_get_context(module);
+	const struct ldb_map_attribute *map = map_attr_find_local(data, attr_name);
+	struct ldb_message_element *el;
+
+	/* Unknown attribute: ignore */
+	if (map == NULL) {
+		ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
+			  "Not mapping attribute '%s': no mapping found\n",
+			  old->name);
+		goto local;
+	}
+
+	switch (map->type) {
+	case MAP_IGNORE:
+		goto local;
+
+	case MAP_CONVERT:
+		if (map->u.convert.convert_local == NULL) {
+			ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
+				  "Not mapping attribute '%s': "
+				  "'convert_local' not set\n",
+				  map->local_name);
+			goto local;
+		}
+		/* fall through */
+	case MAP_KEEP:
+	case MAP_RENAME:
+		el = ldb_msg_el_map_local(module, remote, map, old);
+		break;
+
+	case MAP_GENERATE:
+		if (map->u.generate.generate_remote == NULL) {
+			ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
+				  "Not mapping attribute '%s': "
+				  "'generate_remote' not set\n",
+				  map->local_name);
+			goto local;
+		}
+
+		/* TODO: if this attr requires context:
+		 *	 make sure all context attrs are mappable (in 'names')
+		 *	 make sure all context attrs have already been mapped?
+		 *	 maybe postpone generation until they have been mapped?
+		 */
+
+		map->u.generate.generate_remote(module, map->local_name, msg, remote, local);
+		return 0;
+	}
+
+	if (el == NULL) {
+		return -1;
+	}
+
+	return ldb_msg_add(remote, el, old->flags);
+
+local:
+	el = talloc(local, struct ldb_message_element);
+	if (el == NULL) {
+		map_oom(module);
+		return -1;
+	}
+
+	*el = *old;			/* copy the old element */
+
+	return ldb_msg_add(local, el, old->flags);
+}
+
+/* Mapping messages
+ * ================ */
+
+/* Check whether a message will be (partially) mapped into the remote partition. */
+static BOOL ldb_msg_check_remote(struct ldb_module *module, const struct ldb_message *msg)
+{
+	const struct ldb_map_context *data = map_get_context(module);
+	BOOL ret;
+	int i;
+
+	for (i = 0; i < msg->num_elements; i++) {
+		ret = map_attr_check_remote(data, msg->elements[i].name);
+		if (ret) {
+			return ret;
+		}
+	}
+
+	return False;
+}
+
+/* Split message elements that stay in the local partition from those
+ * that are mapped into the remote partition. */
+static int ldb_msg_partition(struct ldb_module *module, struct ldb_message *local, struct ldb_message *remote, const struct ldb_message *msg)
+{
+	/* const char * const names[]; */
+	int i, ret;
+
+	for (i = 0; i < msg->num_elements; i++) {
+		/* Skip 'IS_MAPPED' */
+		if (ldb_attr_cmp(msg->elements[i].name, IS_MAPPED) == 0) {
+			ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
+				  "Skipping attribute '%s'\n",
+				  msg->elements[i].name);
+			continue;
+		}
+
+		ret = ldb_msg_el_partition(module, local, remote, msg, msg->elements[i].name, &msg->elements[i]);
+		if (ret) {
+			return ret;
+		}
+	}
+
+	return 0;
+}
+
+
+/* Inbound requests: add, modify, rename, delete
+ * ============================================= */
+
+/* Add the remote record. */
+int map_add_do_remote(struct ldb_handle *handle)
+{
+	struct map_context *ac;
+
+	ac = talloc_get_type(handle->private_data, struct map_context);
+
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, ac->remote_req);
+
+	ac->step = MAP_ADD_REMOTE;
+
+	handle->state = LDB_ASYNC_INIT;
+	handle->status = LDB_SUCCESS;
+
+	return ldb_next_remote_request(ac->module, ac->remote_req);
+}
+
+/* Add the local record. */
+int map_add_do_local(struct ldb_handle *handle)
+{
+	struct map_context *ac;
+
+	ac = talloc_get_type(handle->private_data, struct map_context);
+
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, ac->local_req);
+
+	ac->step = MAP_ADD_LOCAL;
+
+	handle->state = LDB_ASYNC_INIT;
+	handle->status = LDB_SUCCESS;
+
+	return ldb_next_request(ac->module, ac->local_req);
+}
+
+/* Add a record. */
+int map_add(struct ldb_module *module, struct ldb_request *req)
+{
+	const struct ldb_message *msg = req->op.add.message;
+	struct ldb_handle *h;
+	struct map_context *ac;
+	struct ldb_message *local, *remote;
+	const char *dn;
+
+	/* Do not manipulate our control entries */
+	if (ldb_dn_is_special(msg->dn)) {
+		return ldb_next_request(module, req);
+	}
+
+	/* No mapping requested (perhaps no DN mapping specified), skip to next module */
+	if (!ldb_dn_check_local(module, msg->dn)) {
+		return ldb_next_request(module, req);
+	}
+
+	/* No mapping needed, fail */
+	if (!ldb_msg_check_remote(module, msg)) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* Prepare context and handle */
+	h = map_init_handle(req, module);
+	if (h == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ac = talloc_get_type(h->private_data, struct map_context);
+
+	/* Prepare the local operation */
+	ac->local_req = talloc(ac, struct ldb_request);
+	if (ac->local_req == NULL) {
+		goto oom;
+	}
+
+	*(ac->local_req) = *req;	/* copy the request */
+
+	ac->local_req->context = NULL;
+	ac->local_req->callback = NULL;
+
+	/* Prepare the remote operation */
+	ac->remote_req = talloc(ac, struct ldb_request);
+	if (ac->remote_req == NULL) {
+		goto oom;
+	}
+
+	*(ac->remote_req) = *req;	/* copy the request */
+
+	ac->remote_req->context = NULL;
+	ac->remote_req->callback = NULL;
+
+	/* Prepare the local message */
+	local = ldb_msg_new(ac->local_req);
+	if (local == NULL) {
+		goto oom;
+	}
+	local->dn = msg->dn;
+
+	/* Prepare the remote message */
+	remote = ldb_msg_new(ac->remote_req);
+	if (remote == NULL) {
+		goto oom;
+	}
+	remote->dn = ldb_dn_map_local(ac->module, remote, msg->dn);
+
+	/* Split local from remote message */
+	ldb_msg_partition(module, local, remote, msg);
+	ac->local_req->op.add.message = local;
+	ac->remote_req->op.add.message = remote;
+
+	if ((local->num_elements == 0) || (!map_check_local_db(ac->module))) {
+		/* No local data or db, just run the remote request */
+		talloc_free(ac->local_req);
+		req->handle = h;	/* return our own handle to deal with this call */
+		return map_add_do_remote(h);
+	}
+
+	/* Store remote DN in 'IS_MAPPED' */
+	/* TODO: use GUIDs here instead */
+	dn = ldb_dn_linearize(local, remote->dn);
+	if (ldb_msg_add_string(local, IS_MAPPED, dn) != 0) {
+		goto failed;
+	}
+
+	req->handle = h;		/* return our own handle to deal with this call */
+	return map_add_do_local(h);
+
+oom:
+	map_oom(module);
+failed:
+	talloc_free(h);
+	return LDB_ERR_OPERATIONS_ERROR;
+}
+
+/* Modify the remote record. */
+int map_modify_do_remote(struct ldb_handle *handle)
+{
+	struct map_context *ac;
+
+	ac = talloc_get_type(handle->private_data, struct map_context);
+
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, ac->remote_req);
+
+	ac->step = MAP_MODIFY_REMOTE;
+
+	handle->state = LDB_ASYNC_INIT;
+	handle->status = LDB_SUCCESS;
+
+	return ldb_next_remote_request(ac->module, ac->remote_req);
+}
+
+/* Modify the local record. */
+int map_modify_do_local(struct ldb_handle *handle)
+{
+	struct map_context *ac;
+	struct ldb_message *msg;
+	char *dn;
+
+	ac = talloc_get_type(handle->private_data, struct map_context);
+
+	if (ac->local_dn == NULL) {
+		/* No local record present, add it instead */
+		msg = discard_const_p(struct ldb_message, ac->local_req->op.mod.message);
+
+		/* Add local 'IS_MAPPED' */
+		/* TODO: use GUIDs here instead */
+		dn = ldb_dn_linearize(msg, ac->remote_req->op.mod.message->dn);
+		if (ldb_msg_add_empty(msg, IS_MAPPED, LDB_FLAG_MOD_ADD) != 0) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		if (ldb_msg_add_string(msg, IS_MAPPED, dn) != 0) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		/* Turn request into 'add' */
+		ac->local_req->operation = LDB_ADD;
+		ac->local_req->op.add.message = msg;
+		/* TODO: Could I just leave msg in there?  I think so,
+		 *	 but it looks clearer this way. */
+	}
+
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, ac->local_req);
+
+	ac->step = MAP_MODIFY_LOCAL;
+
+	handle->state = LDB_ASYNC_INIT;
+	handle->status = LDB_SUCCESS;
+
+	return ldb_next_request(ac->module, ac->local_req);
+}
+
+/* Modify a record. */
+int map_modify(struct ldb_module *module, struct ldb_request *req)
+{
+	const struct ldb_message *msg = req->op.mod.message;
+	struct ldb_handle *h;
+	struct map_context *ac;
+	struct ldb_message *local, *remote;
+
+	/* Do not manipulate our control entries */
+	if (ldb_dn_is_special(msg->dn)) {
+		return ldb_next_request(module, req);
+	}
+
+	/* No mapping requested (perhaps no DN mapping specified), skip to next module */
+	if (!ldb_dn_check_local(module, msg->dn)) {
+		return ldb_next_request(module, req);
+	}
+
+	/* No mapping needed, skip to next module */
+	/* TODO: What if the remote part exists, the local doesn't,
+	 *	 and this request wants to modify local data and thus
+	 *	 add the local record? */
+	if (!ldb_msg_check_remote(module, msg)) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* Prepare context and handle */
+	h = map_init_handle(req, module);
+	if (h == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ac = talloc_get_type(h->private_data, struct map_context);
+
+	/* Prepare the local operation */
+	ac->local_req = talloc(ac, struct ldb_request);
+	if (ac->local_req == NULL) {
+		goto oom;
+	}
+
+	*(ac->local_req) = *req;	/* copy the request */
+
+	ac->local_req->context = NULL;
+	ac->local_req->callback = NULL;
+
+	/* Prepare the remote operation */
+	ac->remote_req = talloc(ac, struct ldb_request);
+	if (ac->remote_req == NULL) {
+		goto oom;
+	}
+
+	*(ac->remote_req) = *req;	/* copy the request */
+
+	ac->remote_req->context = NULL;
+	ac->remote_req->callback = NULL;
+
+	/* Prepare the local message */
+	local = ldb_msg_new(ac->local_req);
+	if (local == NULL) {
+		goto oom;
+	}
+	local->dn = msg->dn;
+
+	/* Prepare the remote message */
+	remote = ldb_msg_new(ac->remote_req);
+	if (remote == NULL) {
+		goto oom;
+	}
+	remote->dn = ldb_dn_map_local(ac->module, remote, msg->dn);
+
+	/* Split local from remote message */
+	ldb_msg_partition(module, local, remote, msg);
+	ac->local_req->op.mod.message = local;
+	ac->remote_req->op.mod.message = remote;
+
+	if ((local->num_elements == 0) || (!map_check_local_db(ac->module))) {
+		/* No local data or db, just run the remote request */
+		talloc_free(ac->local_req);
+		req->handle = h;	/* return our own handle to deal with this call */
+		return map_modify_do_remote(h);
+	}
+
+	/* prepare the search operation */
+	ac->search_req = map_search_self_req(ac, msg->dn);
+	if (ac->search_req == NULL) {
+		goto failed;
+	}
+
+	ac->step = MAP_SEARCH_SELF_MODIFY;
+
+	req->handle = h;		/* return our own handle to deal with this call */
+	return ldb_next_request(module, ac->search_req);
+
+oom:
+	map_oom(module);
+failed:
+	talloc_free(h);
+	return LDB_ERR_OPERATIONS_ERROR;
+}
+
+/* Delete the remote record. */
+int map_delete_do_remote(struct ldb_handle *handle)
+{
+	struct map_context *ac;
+
+	ac = talloc_get_type(handle->private_data, struct map_context);
+
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, ac->remote_req);
+
+	ac->step = MAP_DELETE_REMOTE;
+
+	handle->state = LDB_ASYNC_INIT;
+	handle->status = LDB_SUCCESS;
+
+	return ldb_next_remote_request(ac->module, ac->remote_req);
+}
+
+/* Delete the local record. */
+int map_delete_do_local(struct ldb_handle *handle)
+{
+	struct map_context *ac;
+
+	ac = talloc_get_type(handle->private_data, struct map_context);
+
+	/* No local record, continue remotely */
+	if (ac->local_dn == NULL) {
+		return map_delete_do_remote(handle);
+	}
+
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, ac->local_req);
+
+	ac->step = MAP_DELETE_LOCAL;
+
+	handle->state = LDB_ASYNC_INIT;
+	handle->status = LDB_SUCCESS;
+
+	return ldb_next_request(ac->module, ac->local_req);
+}
+
+/* Delete a record. */
+int map_delete(struct ldb_module *module, struct ldb_request *req)
+{
+	struct ldb_handle *h;
+	struct map_context *ac;
+
+	/* Do not manipulate our control entries */
+	if (ldb_dn_is_special(req->op.del.dn)) {
+		return ldb_next_request(module, req);
+	}
+
+	/* No mapping requested (perhaps no DN mapping specified), skip to next module */
+	if (!ldb_dn_check_local(module, req->op.del.dn)) {
+		return ldb_next_request(module, req);
+	}
+
+	/* Prepare context and handle */
+	h = map_init_handle(req, module);
+	if (h == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ac = talloc_get_type(h->private_data, struct map_context);
+
+	/* Prepare the local operation */
+	ac->local_req = talloc(ac, struct ldb_request);
+	if (ac->local_req == NULL) {
+		goto oom;
+	}
+
+	*(ac->local_req) = *req;	/* copy the request */
+	ac->local_req->op.del.dn = req->op.del.dn;
+
+	ac->local_req->context = NULL;
+	ac->local_req->callback = NULL;
+
+	/* Prepare the remote operation */
+	ac->remote_req = talloc(ac, struct ldb_request);
+	if (ac->remote_req == NULL) {
+		goto oom;
+	}
+
+	*(ac->remote_req) = *req;	/* copy the request */
+	ac->remote_req->op.del.dn = ldb_dn_map_local(module, ac->remote_req, req->op.del.dn);
+
+	/* No local db, just run the remote request */
+	if (!map_check_local_db(ac->module)) {
+		req->handle = h;	/* return our own handle to deal with this call */
+		return map_delete_do_remote(h);
+	}
+
+	ac->remote_req->context = NULL;
+	ac->remote_req->callback = NULL;
+
+	/* Prepare the search operation */
+	ac->search_req = map_search_self_req(ac, req->op.del.dn);
+	if (ac->search_req == NULL) {
+		goto failed;
+	}
+
+	req->handle = h;		/* return our own handle to deal with this call */
+
+	ac->step = MAP_SEARCH_SELF_DELETE;
+
+	return ldb_next_request(module, ac->search_req);
+
+oom:
+	map_oom(module);
+failed:
+	talloc_free(h);
+	return LDB_ERR_OPERATIONS_ERROR;
+}
+
+/* Rename the remote record. */
+int map_rename_do_remote(struct ldb_handle *handle)
+{
+	struct map_context *ac;
+
+	ac = talloc_get_type(handle->private_data, struct map_context);
+
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, ac->remote_req);
+
+	ac->step = MAP_RENAME_REMOTE;
+
+	handle->state = LDB_ASYNC_INIT;
+	handle->status = LDB_SUCCESS;
+
+	return ldb_next_remote_request(ac->module, ac->remote_req);
+}
+
+/* Update the local 'IS_MAPPED' attribute. */
+int map_rename_do_fixup(struct ldb_handle *handle)
+{
+	struct map_context *ac;
+
+	ac = talloc_get_type(handle->private_data, struct map_context);
+
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, ac->down_req);
+
+	ac->step = MAP_RENAME_FIXUP;
+
+	handle->state = LDB_ASYNC_INIT;
+	handle->status = LDB_SUCCESS;
+
+	return ldb_next_request(ac->module, ac->down_req);
+}
+
+/* Rename the local record. */
+int map_rename_do_local(struct ldb_handle *handle)
+{
+	struct map_context *ac;
+
+	ac = talloc_get_type(handle->private_data, struct map_context);
+
+	/* No local record, continue remotely */
+	if (ac->local_dn == NULL) {
+		return map_rename_do_remote(handle);
+	}
+
+	ldb_set_timeout_from_prev_req(ac->module->ldb, ac->orig_req, ac->local_req);
+
+	ac->step = MAP_RENAME_LOCAL;
+
+	handle->state = LDB_ASYNC_INIT;
+	handle->status = LDB_SUCCESS;
+
+	return ldb_next_request(ac->module, ac->local_req);
+}
+
+/* Rename a record. */
+int map_rename(struct ldb_module *module, struct ldb_request *req)
+{
+	struct ldb_handle *h;
+	struct map_context *ac;
+
+	/* Do not manipulate our control entries */
+	if (ldb_dn_is_special(req->op.rename.olddn)) {
+		return ldb_next_request(module, req);
+	}
+
+	/* No mapping requested (perhaps no DN mapping specified), skip to next module */
+	if ((!ldb_dn_check_local(module, req->op.rename.olddn)) &&
+	    (!ldb_dn_check_local(module, req->op.rename.newdn))) {
+		return ldb_next_request(module, req);
+	}
+
+	/* Rename into/out of the mapped partition requested, bail out */
+	if (!ldb_dn_check_local(module, req->op.rename.olddn) ||
+	    !ldb_dn_check_local(module, req->op.rename.newdn)) {
+		return LDB_ERR_AFFECTS_MULTIPLE_DSAS;
+	}
+
+	/* Prepare context and handle */
+	h = map_init_handle(req, module);
+	if (h == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ac = talloc_get_type(h->private_data, struct map_context);
+
+	/* Prepare the local operation */
+	ac->local_req = talloc(ac, struct ldb_request);
+	if (ac->local_req == NULL) {
+		goto oom;
+	}
+
+	*(ac->local_req) = *req;	/* copy the request */
+	ac->local_req->op.rename.olddn = req->op.rename.olddn;
+	ac->local_req->op.rename.newdn = req->op.rename.newdn;
+
+	ac->local_req->context = NULL;
+	ac->local_req->callback = NULL;
+
+	/* Prepare the remote operation */
+	ac->remote_req = talloc(ac, struct ldb_request);
+	if (ac->remote_req == NULL) {
+		goto oom;
+	}
+
+	*(ac->remote_req) = *req;	/* copy the request */
+	ac->remote_req->op.rename.olddn = ldb_dn_map_local(module, ac->remote_req, req->op.rename.olddn);
+	ac->remote_req->op.rename.newdn = ldb_dn_map_local(module, ac->remote_req, req->op.rename.newdn);
+
+	ac->remote_req->context = NULL;
+	ac->remote_req->callback = NULL;
+
+	/* No local db, just run the remote request */
+	if (!map_check_local_db(ac->module)) {
+		req->handle = h;	/* return our own handle to deal with this call */
+		return map_rename_do_remote(h);
+	}
+
+	/* Prepare the fixup operation */
+	/* TODO: use GUIDs here instead -- or skip it when GUIDs are used. */
+	ac->down_req = map_build_fixup_req(ac, req->op.rename.newdn, ac->remote_req->op.rename.newdn);
+	if (ac->down_req == NULL) {
+		goto failed;
+	}
+
+	/* Prepare the search operation */
+	ac->search_req = map_search_self_req(ac, req->op.rename.olddn);
+	if (ac->search_req == NULL) {
+		goto failed;
+	}
+
+	req->handle = h;		/* return our own handle to deal with this call */
+
+	ac->step = MAP_SEARCH_SELF_RENAME;
+
+	return ldb_next_request(module, ac->search_req);
+
+oom:
+	map_oom(module);
+failed:
+	talloc_free(h);
+	return LDB_ERR_OPERATIONS_ERROR;
+}
diff --git a/source4/lib/ldb/modules/ldb_map_outbound.c b/source4/lib/ldb/modules/ldb_map_outbound.c
new file mode 100644
index 0000000000..046c92bb99
--- /dev/null
+++ b/source4/lib/ldb/modules/ldb_map_outbound.c
@@ -0,0 +1,1134 @@
+/*
+   ldb database mapping module
+
+   Copyright (C) Jelmer Vernooij 2005
+   Copyright (C) Martin Kuehl <mkhl@samba.org> 2006
+
+   * NOTICE: this module is NOT released under the GNU LGPL license as
+   * other ldb code. This module is release under the GNU GPL v2 or
+   * later license.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#include "includes.h"
+#include "ldb/include/includes.h"
+
+#include "ldb/modules/ldb_map.h"
+#include "ldb/modules/ldb_map_private.h"
+
+
+/* Mapping attributes
+ * ================== */
+
+/* Select attributes that stay in the local partition. */
+static const char **map_attrs_select_local(struct ldb_module *module, void *mem_ctx, const char * const *attrs)
+{
+	const struct ldb_map_context *data = map_get_context(module);
+	const char **result;
+	int i, last;
+
+	if (attrs == NULL)
+		return NULL;
+
+	last = 0;
+	result = talloc_array(mem_ctx, const char *, 1);
+	if (result == NULL) {
+		goto failed;
+	}
+	result[0] = NULL;
+
+	for (i = 0; attrs[i]; i++) {
+		/* Wildcards and ignored attributes are kept locally */
+		if ((ldb_attr_cmp(attrs[i], "*") == 0) ||
+		    (!map_attr_check_remote(data, attrs[i]))) {
+			result = talloc_realloc(mem_ctx, result, const char *, last+2);
+			if (result == NULL) {
+				goto failed;
+			}
+
+			result[last] = talloc_strdup(result, attrs[i]);
+			result[last+1] = NULL;
+			last++;
+		}
+	}
+
+	return result;
+
+failed:
+	talloc_free(result);
+	map_oom(module);
+	return NULL;
+}
+
+/* Collect attributes that are mapped into the remote partition. */
+static const char **map_attrs_collect_remote(struct ldb_module *module, void *mem_ctx, const char * const *attrs)
+{
+	const struct ldb_map_context *data = map_get_context(module);
+	const char **result;
+	const struct ldb_map_attribute *map;
+	const char *name;
+	int i, j, last;
+
+	if (attrs == NULL)
+		return NULL;
+
+	last = 0;
+	result = talloc_array(mem_ctx, const char *, 1);
+	if (result == NULL) {
+		goto failed;
+	}
+	result[0] = NULL;
+
+	for (i = 0; attrs[i]; i++) {
+		/* Wildcards are kept remotely, too */
+		if (ldb_attr_cmp(attrs[i], "*") == 0) {
+			name = attrs[i];
+			goto named;
+		}
+
+		/* Add remote names of mapped attrs */
+		map = map_attr_find_local(data, attrs[i]);
+		if (map == NULL) {
+			continue;
+		}
+
+		switch (map->type) {
+		case MAP_IGNORE:
+			continue;
+
+		case MAP_KEEP:
+			name = attrs[i];
+			goto named;
+
+		case MAP_RENAME:
+		case MAP_CONVERT:
+			name = map->u.rename.remote_name;
+			goto named;
+
+		case MAP_GENERATE:
+			/* Add all remote names of "generate" attrs */
+			for (j = 0; map->u.generate.remote_names[j]; j++) {
+				result = talloc_realloc(mem_ctx, result, const char *, last+2);
+				if (result == NULL) {
+					goto failed;
+				}
+
+				result[last] = talloc_strdup(result, map->u.generate.remote_names[j]);
+				result[last+1] = NULL;
+				last++;
+			}
+			continue;
+		}
+
+	named:	/* We found a single remote name, add that */
+		result = talloc_realloc(mem_ctx, result, const char *, last+2);
+		if (result == NULL) {
+			goto failed;
+		}
+
+		result[last] = talloc_strdup(result, name);
+		result[last+1] = NULL;
+		last++;
+	}
+
+	return result;
+
+failed:
+	talloc_free(result);
+	map_oom(module);
+	return NULL;
+}
+
+/* Split attributes that stay in the local partition from those that
+ * are mapped into the remote partition. */
+static int map_attrs_partition(struct ldb_module *module, void *local_ctx, void *remote_ctx, const char ***local_attrs, const char ***remote_attrs, const char * const *attrs)
+{
+	*local_attrs = map_attrs_select_local(module, local_ctx, attrs);
+	*remote_attrs = map_attrs_collect_remote(module, remote_ctx, attrs);
+
+	return 0;
+}
+
+/* Merge two lists of attributes into a single one. */
+static int map_attrs_merge(struct ldb_module *module, void *mem_ctx, const char ***attrs, const char * const *more_attrs)
+{
+	int i, j, k;
+
+	for (i = 0; (*attrs)[i]; i++) /* noop */ ;
+	for (j = 0; more_attrs[j]; j++) /* noop */ ;
+
+	*attrs = talloc_realloc(mem_ctx, *attrs, const char *, i+j+1);
+	if (*attrs == NULL) {
+		map_oom(module);
+		return -1;
+	}
+
+	for (k = 0; k < j; k++) {
+		(*attrs)[i+k] = more_attrs[k];
+	}
+
+	(*attrs)[i+k] = NULL;
+
+	return 0;
+}
+
+/* Mapping ldb values
+ * ================== */
+
+/* Map an ldb value from a parse tree into the remote partition. */
+static struct ldb_val ldb_val_map_subtree(struct ldb_module *module, struct ldb_parse_tree *new, const struct ldb_map_attribute *map, const struct ldb_parse_tree *tree)
+{
+	struct ldb_val val;
+
+	/* Extract the old value */
+	switch (tree->operation) {
+	case LDB_OP_EQUALITY:
+		val = tree->u.equality.value;
+		break;
+	case LDB_OP_LESS:
+	case LDB_OP_GREATER:
+	case LDB_OP_APPROX:
+		val = tree->u.comparison.value;
+		break;
+	case LDB_OP_EXTENDED:
+		val = tree->u.extended.value;
+		break;
+	default:
+		val.length = 0;
+		val.data = NULL;
+		return ldb_val_dup(new, &val);
+	}
+
+	/* Convert to the new value */
+	return ldb_val_map_local(module, new, map, val);
+}
+
+/* Mapping message elements
+ * ======================== */
+
+/* Add an element to a message, overwriting any old identically named elements. */
+static int ldb_msg_replace(struct ldb_message *msg, const struct ldb_message_element *el)
+{
+	struct ldb_message_element *old;
+
+	old = ldb_msg_find_element(msg, el->name);
+
+	/* no local result, add as new element */
+	if (old == NULL) {
+		if (ldb_msg_add_empty(msg, el->name, 0) != 0) {
+			return -1;
+		}
+
+		old = ldb_msg_find_element(msg, el->name);
+		if (old == NULL) {
+			return -1;
+		}
+	}
+
+	*old = *el;			/* copy new element */
+
+	return 0;
+}
+
+/* Map a message element back into the local partition. */
+static struct ldb_message_element *ldb_msg_el_map_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_map_attribute *map, const struct ldb_message_element *old)
+{
+	struct ldb_message_element *el;
+	int i;
+
+	el = talloc_zero(mem_ctx, struct ldb_message_element);
+	if (el == NULL) {
+		map_oom(module);
+		return NULL;
+	}
+
+	el->num_values = old->num_values;
+	el->values = talloc_array(el, struct ldb_val, el->num_values);
+	if (el->values == NULL) {
+		talloc_free(el);
+		map_oom(module);
+		return NULL;
+	}
+
+	el->name = map_attr_map_remote(el, map, old->name);
+
+	for (i = 0; i < el->num_values; i++) {
+		el->values[i] = ldb_val_map_remote(module, el->values, map, old->values[i]);
+	}
+
+	return el;
+}
+
+/* Merge a remote message element into a local message. */
+static int ldb_msg_el_merge(struct ldb_module *module, struct ldb_message *local, struct ldb_message *remote, const char *attr_name, const struct ldb_message_element *old)
+{
+	const struct ldb_map_context *data = map_get_context(module);
+	const struct ldb_map_attribute *map = map_attr_find_remote(data, attr_name);
+	struct ldb_message_element *el;
+
+	/* Unknown attribute in remote message:
+	 * skip, attribute was probably auto-generated */
+	if (map == NULL) {
+		ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
+			  "Skipping attribute '%s': no mapping found\n",
+			  old->name);
+		return 0;
+	}
+
+	switch (map->type) {
+	case MAP_IGNORE:
+		return -1;
+
+	case MAP_CONVERT:
+		if (map->u.convert.convert_remote == NULL) {
+			ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+				  "Skipping attribute '%s': "
+				  "'convert_remote' not set\n",
+				  old->name);
+			return 0;
+		}
+		/* fall through */
+	case MAP_KEEP:
+	case MAP_RENAME:
+		el = ldb_msg_el_map_remote(module, local, map, old);
+		break;
+
+	case MAP_GENERATE:
+		if (map->u.generate.generate_local == NULL) {
+			ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
+				  "Skipping attribute '%s': "
+				  "'generate_local' not set\n",
+				  old->name);
+			return 0;
+		}
+
+		el = map->u.generate.generate_local(module, local, old->name, remote);
+		break;
+	}
+
+	if (el == NULL) {
+		return -1;
+	}
+
+	return ldb_msg_replace(local, el);
+}
+
+/* Mapping messages
+ * ================ */
+
+/* Merge two local messages into a single one. */
+static int ldb_msg_merge_local(struct ldb_module *module, struct ldb_message *msg1, struct ldb_message *msg2)
+{
+	int i, ret;
+
+	for (i = 0; i < msg2->num_elements; i++) {
+		ret = ldb_msg_replace(msg1, &msg2->elements[i]);
+		if (ret) {
+			return ret;
+		}
+	}
+
+	return 0;
+}
+
+/* Merge a local and a remote message into a single local one. */
+static int ldb_msg_merge_remote(struct ldb_module *module, struct ldb_message *local, struct ldb_message *remote)
+{
+	int i, ret;
+
+	/* Try to map each attribute back;
+	 * Add to local message is possible,
+	 * Overwrite old local attribute if necessary */
+	for (i = 0; i < remote->num_elements; i++) {
+		ret = ldb_msg_el_merge(module, local, remote, remote->elements[i].name, &remote->elements[i]);
+		if (ret) {
+			return ret;
+		}
+	}
+
+	return 0;
+}
+
+/* Mapping search results
+ * ====================== */
+
+/* Map a search result back into the local partition. */
+static int map_reply_remote(struct ldb_module *module, struct ldb_reply *ares)
+{
+	struct ldb_message *msg;
+	struct ldb_dn *dn;
+	int ret;
+
+	/* There is no result message, skip */
+	if (ares->type != LDB_REPLY_ENTRY) {
+		return 0;
+	}
+
+	/* Create a new result message */
+	msg = ldb_msg_new(ares);
+	if (msg == NULL) {
+		map_oom(module);
+		return -1;
+	}
+
+	/* Merge remote message into new message */
+	ret = ldb_msg_merge_remote(module, msg, ares->message);
+	if (ret) {
+		talloc_free(msg);
+		return ret;
+	}
+
+	/* Create corresponding local DN */
+	dn = ldb_dn_map_rebase_remote(module, msg, ares->message->dn);
+	if (dn == NULL) {
+		talloc_free(msg);
+		return -1;
+	}
+	msg->dn = dn;
+
+	/* Store new message with new DN as the result */
+	talloc_free(ares->message);
+	ares->message = msg;
+
+	return 0;
+}
+
+/* Mapping parse trees
+ * =================== */
+
+/* Check whether a parse tree can safely be split in two. */
+static BOOL ldb_parse_tree_check_splittable(const struct ldb_parse_tree *tree)
+{
+	const struct ldb_parse_tree *subtree = tree;
+	BOOL negate = False;
+
+	while (subtree) {
+		switch (subtree->operation) {
+		case LDB_OP_NOT:
+			negate = !negate;
+			subtree = subtree->u.isnot.child;
+			continue;
+
+		case LDB_OP_AND:
+			return !negate;	/* if negate: False */
+
+		case LDB_OP_OR:
+			return negate;	/* if negate: True */
+
+		default:
+			return True;	/* simple parse tree */
+		}
+	}
+
+	return True;			/* no parse tree */
+}
+
+/* Collect a list of attributes required to match a given parse tree. */
+static int ldb_parse_tree_collect_attrs(struct ldb_module *module, void *mem_ctx, const char ***attrs, const struct ldb_parse_tree *tree)
+{
+	const char **new_attrs;
+	int i, ret;
+
+	if (tree == NULL) {
+		return 0;
+	}
+
+	switch (tree->operation) {
+	case LDB_OP_OR:
+	case LDB_OP_AND:		/* attributes stored in list of subtrees */
+		for (i = 0; i < tree->u.list.num_elements; i++) {
+			ret = ldb_parse_tree_collect_attrs(module, mem_ctx, attrs, tree->u.list.elements[i]);
+			if (ret) {
+				return ret;
+			}
+		}
+		return 0;
+
+	case LDB_OP_NOT:		/* attributes stored in single subtree */
+		return ldb_parse_tree_collect_attrs(module, mem_ctx, attrs, tree->u.isnot.child);
+
+	default:			/* single attribute in tree */
+		new_attrs = ldb_attr_list_copy_add(mem_ctx, *attrs, tree->u.equality.attr);
+		talloc_free(*attrs);
+		*attrs = new_attrs;
+		return 0;
+	}
+
+	return -1;
+}
+
+static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
+
+/* Select a negated subtree that queries attributes in the local partition */
+static int map_subtree_select_local_not(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
+{
+	struct ldb_parse_tree *child;
+	int ret;
+
+	/* Prepare new tree */
+	*new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
+	if (*new == NULL) {
+		map_oom(module);
+		return -1;
+	}
+
+	/* Generate new subtree */
+	ret = map_subtree_select_local(module, *new, &child, tree->u.isnot.child);
+	if (ret) {
+		talloc_free(*new);
+		return ret;
+	}
+
+	/* Prune tree without subtree */
+	if (child == NULL) {
+		talloc_free(*new);
+		*new = NULL;
+		return 0;
+	}
+
+	(*new)->u.isnot.child = child;
+
+	return ret;
+}
+
+/* Select a list of subtrees that query attributes in the local partition */
+static int map_subtree_select_local_list(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
+{
+	int i, j, ret;
+
+	/* Prepare new tree */
+	*new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
+	if (*new == NULL) {
+		map_oom(module);
+		return -1;
+	}
+
+	/* Prepare list of subtrees */
+	(*new)->u.list.num_elements = 0;
+	(*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
+	if ((*new)->u.list.elements == NULL) {
+		map_oom(module);
+		talloc_free(*new);
+		return -1;
+	}
+
+	/* Generate new list of subtrees */
+	j = 0;
+	for (i = 0; i < tree->u.list.num_elements; i++) {
+		struct ldb_parse_tree *child;
+		ret = map_subtree_select_local(module, *new, &child, tree->u.list.elements[i]);
+		if (ret) {
+			talloc_free(*new);
+			return ret;
+		}
+
+		if (child) {
+			(*new)->u.list.elements[j] = child;
+			j++;
+		}
+	}
+
+	/* Prune tree without subtrees */
+	if (j == 0) {
+		talloc_free(*new);
+		*new = NULL;
+		return 0;
+	}
+
+	/* Fix subtree list size */
+	(*new)->u.list.num_elements = j;
+	(*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
+
+	return ret;
+}
+
+/* Select a simple subtree that queries attributes in the local partition */
+static int map_subtree_select_local_simple(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
+{
+	/* Prepare new tree */
+	*new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
+	if (*new == NULL) {
+		map_oom(module);
+		return -1;
+	}
+
+	return 0;
+}
+
+/* Select subtrees that query attributes in the local partition */
+static int map_subtree_select_local(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
+{
+	const struct ldb_map_context *data = map_get_context(module);
+
+	if (tree == NULL) {
+		return 0;
+	}
+
+	if (tree->operation == LDB_OP_NOT) {
+		return map_subtree_select_local_not(module, mem_ctx, new, tree);
+	}
+
+	if (tree->operation == LDB_OP_AND || tree->operation == LDB_OP_OR) {
+		return map_subtree_select_local_list(module, mem_ctx, new, tree);
+	}
+
+	if (map_attr_check_remote(data, tree->u.equality.attr)) {
+		*new = NULL;
+		return 0;
+	}
+
+	return map_subtree_select_local_simple(module, mem_ctx, new, tree);
+}
+
+static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree);
+
+/* Collect a negated subtree that queries attributes in the remote partition */
+static int map_subtree_collect_remote_not(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
+{
+	struct ldb_parse_tree *child;
+	int ret;
+
+	/* Prepare new tree */
+	*new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
+	if (*new == NULL) {
+		map_oom(module);
+		return -1;
+	}
+
+	/* Generate new subtree */
+	ret = map_subtree_collect_remote(module, *new, &child, tree->u.isnot.child);
+	if (ret) {
+		talloc_free(*new);
+		return ret;
+	}
+
+	/* Prune tree without subtree */
+	if (child == NULL) {
+		talloc_free(*new);
+		*new = NULL;
+		return 0;
+	}
+
+	(*new)->u.isnot.child = child;
+
+	return ret;
+}
+
+/* Collect a list of subtrees that query attributes in the remote partition */
+static int map_subtree_collect_remote_list(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
+{
+	int i, j, ret;
+
+	/* Prepare new tree */
+	*new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
+	if (*new == NULL) {
+		map_oom(module);
+		return -1;
+	}
+
+	/* Prepare list of subtrees */
+	(*new)->u.list.num_elements = 0;
+	(*new)->u.list.elements = talloc_array(*new, struct ldb_parse_tree *, tree->u.list.num_elements);
+	if ((*new)->u.list.elements == NULL) {
+		map_oom(module);
+		talloc_free(*new);
+		return -1;
+	}
+
+	/* Generate new list of subtrees */
+	j = 0;
+	for (i = 0; i < tree->u.list.num_elements; i++) {
+		struct ldb_parse_tree *child;
+		ret = map_subtree_collect_remote(module, *new, &child, tree->u.list.elements[i]);
+		if (ret) {
+			talloc_free(*new);
+			return ret;
+		}
+
+		if (child) {
+			(*new)->u.list.elements[j] = child;
+			j++;
+		}
+	}
+
+	/* Prune tree without subtrees */
+	if (j == 0) {
+		talloc_free(*new);
+		*new = NULL;
+		return 0;
+	}
+
+	/* Fix subtree list size */
+	(*new)->u.list.num_elements = j;
+	(*new)->u.list.elements = talloc_realloc(*new, (*new)->u.list.elements, struct ldb_parse_tree *, (*new)->u.list.num_elements);
+
+	return ret;
+}
+
+/* Collect a simple subtree that queries attributes in the remote partition */
+static int map_subtree_collect_remote_simple(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree, const struct ldb_map_attribute *map)
+{
+	const char *attr;
+	struct ldb_val val;
+
+	/* Prepare new tree */
+	*new = talloc_memdup(mem_ctx, tree, sizeof(struct ldb_parse_tree));
+	if (*new == NULL) {
+		map_oom(module);
+		return -1;
+	}
+
+	/* Map attribute and value */
+	attr = map_attr_map_local(*new, map, tree->u.equality.attr);
+	if (attr == NULL) {
+		talloc_free(*new);
+		*new = NULL;
+		return 0;
+	}
+	val = ldb_val_map_subtree(module, *new, map, tree);
+
+	/* Store attribute and value in new tree */
+	switch (tree->operation) {
+	case LDB_OP_PRESENT:
+		(*new)->u.present.attr = attr;
+		break;
+	case LDB_OP_SUBSTRING:
+		(*new)->u.substring.attr = attr;
+		(*new)->u.substring.chunks = NULL;	/* FIXME! */
+		break;
+	case LDB_OP_EQUALITY:
+		(*new)->u.equality.attr = attr;
+		(*new)->u.equality.value = val;
+		break;
+	case LDB_OP_LESS:
+	case LDB_OP_GREATER:
+	case LDB_OP_APPROX:
+		(*new)->u.comparison.attr = attr;
+		(*new)->u.comparison.value = val;
+		break;
+	case LDB_OP_EXTENDED:
+		(*new)->u.extended.attr = attr;
+		(*new)->u.extended.value = val;
+		(*new)->u.extended.rule_id = talloc_strdup(*new, tree->u.extended.rule_id);
+		break;
+	default:			/* unknown kind of simple subtree */
+		talloc_free(*new);
+		return -1;
+	}
+
+	return 0;
+}
+
+/* Collect subtrees that query attributes in the remote partition */
+static int map_subtree_collect_remote(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree)
+{
+	const struct ldb_map_context *data = map_get_context(module);
+	const struct ldb_map_attribute *map;
+
+	if (tree == NULL) {
+		return 0;
+	}
+
+	if (tree->operation == LDB_OP_NOT) {
+		return map_subtree_collect_remote_not(module, mem_ctx, new, tree);
+	}
+
+	if ((tree->operation == LDB_OP_AND) || (tree->operation == LDB_OP_OR)) {
+		return map_subtree_collect_remote_list(module, mem_ctx, new, tree);
+	}
+
+	if (!map_attr_check_remote(data, tree->u.equality.attr)) {
+		*new = NULL;
+		return 0;
+	}
+
+	map = map_attr_find_local(data, tree->u.equality.attr);
+	if (map->convert_operator) {
+		*new = map->convert_operator(data, mem_ctx, tree);
+		return 0;
+	}
+
+	if (map->type == MAP_GENERATE) {
+		ldb_debug(module->ldb, LDB_DEBUG_WARNING, "ldb_map: "
+			  "Skipping attribute '%s': "
+			  "'convert_operator' not set\n",
+			  tree->u.equality.attr);
+		*new = NULL;
+		return 0;
+	}
+
+	return map_subtree_collect_remote_simple(module, mem_ctx, new, tree, map);
+}
+
+/* Split subtrees that query attributes in the local partition from
+ * those that query the remote partition. */
+static int ldb_parse_tree_partition(struct ldb_module *module, void *local_ctx, void *remote_ctx, struct ldb_parse_tree **local_tree, struct ldb_parse_tree **remote_tree, const struct ldb_parse_tree *tree)
+{
+	int ret;
+
+	*local_tree = NULL;
+	*remote_tree = NULL;
+
+	/* No original tree */
+	if (tree == NULL) {
+		return 0;
+	}
+
+	/* Generate local tree */
+	ret = map_subtree_select_local(module, local_ctx, local_tree, tree);
+	if (ret) {
+		return ret;
+	}
+
+	/* Generate remote tree */
+	ret = map_subtree_collect_remote(module, remote_ctx, remote_tree, tree);
+	if (ret) {
+		talloc_free(*local_tree);
+		return ret;
+	}
+
+	return 0;
+}
+
+/* Collect a list of attributes required either explicitly from a
+ * given list or implicitly  from a given parse tree; split the
+ * collected list into local and remote parts. */
+static int map_attrs_collect_and_partition(struct ldb_module *module, void *local_ctx, void *remote_ctx, const char ***local_attrs, const char ***remote_attrs, const char * const *search_attrs, const struct ldb_parse_tree *tree)
+{
+	void *tmp_ctx;
+	const char **tree_attrs;
+	int ret;
+
+	/* Clear initial lists of partitioned attributes */
+	*local_attrs = NULL;
+	*remote_attrs = NULL;
+
+	/* There are no searched attributes, just stick to that */
+	if (search_attrs == NULL) {
+		return 0;
+	}
+
+	/* There is no tree, just partition the searched attributes */
+	if (tree == NULL) {
+		return map_attrs_partition(module, local_ctx, remote_ctx, local_attrs, remote_attrs, search_attrs);
+	}
+
+	/* Create context for temporary memory */
+	tmp_ctx = talloc_new(local_ctx);
+	if (tmp_ctx == NULL) {
+		goto oom;
+	}
+
+	/* Prepare list of attributes from tree */
+	tree_attrs = talloc_array(tmp_ctx, const char *, 1);
+	if (tree_attrs == NULL) {
+		talloc_free(tmp_ctx);
+		goto oom;
+	}
+	tree_attrs[0] = NULL;
+
+	/* Collect attributes from tree */
+	ret = ldb_parse_tree_collect_attrs(module, tmp_ctx, &tree_attrs, tree);
+	if (ret) {
+		goto done;
+	}
+
+	/* Merge attributes from search operation */
+	ret = map_attrs_merge(module, tmp_ctx, &tree_attrs, search_attrs);
+	if (ret) {
+		goto done;
+	}
+
+	/* Split local from remote attributes */
+	ret = map_attrs_partition(module, local_ctx, remote_ctx, local_attrs, remote_attrs, tree_attrs);
+
+done:
+	/* Free temporary memory */
+	talloc_free(tmp_ctx);
+	return ret;
+
+oom:
+	map_oom(module);
+	return -1;
+}
+
+
+/* Outbound requests: search
+ * ========================= */
+
+/* Pass a merged search result up the callback chain. */
+int map_up_callback(struct ldb_context *ldb, const struct ldb_request *req, struct ldb_reply *ares)
+{
+	int i;
+
+	/* No callback registered, stop */
+	if (req->callback == NULL) {
+		return LDB_SUCCESS;
+	}
+
+	/* Only records need special treatment */
+	if (ares->type != LDB_REPLY_ENTRY) {
+		return req->callback(ldb, req->context, ares);
+	}
+
+	/* Merged result doesn't match original query, skip */
+	if (!ldb_match_msg(ldb, ares->message, req->op.search.tree, req->op.search.base, req->op.search.scope)) {
+		ldb_debug(ldb, LDB_DEBUG_TRACE, "ldb_map: "
+			  "Skipping record '%s': "
+			  "doesn't match original search\n",
+			  ldb_dn_linearize(ldb, ares->message->dn));
+		return LDB_SUCCESS;
+	}
+
+	/* Limit result to requested attrs */
+	if ((req->op.search.attrs) && (!ldb_attr_in_list(req->op.search.attrs, "*"))) {
+		for (i = 0; i < ares->message->num_elements; i++) {
+			const struct ldb_message_element *el = &ares->message->elements[i];
+			if (!ldb_attr_in_list(req->op.search.attrs, el->name)) {
+				ldb_msg_remove_attr(ares->message, el->name);
+			}
+		}
+	}
+
+	return req->callback(ldb, req->context, ares);
+}
+
+/* Merge the remote and local parts of a search result. */
+int map_local_merge_callback(struct ldb_context *ldb, void *context, struct ldb_reply *ares)
+{
+	struct map_search_context *sc;
+	int ret;
+
+	if (context == NULL || ares == NULL) {
+		ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
+						       "NULL Context or Result in `map_local_merge_callback`"));
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	sc = talloc_get_type(context, struct map_search_context);
+
+	switch (ares->type) {
+	case LDB_REPLY_ENTRY:
+		/* We have already found a local record */
+		if (sc->local_res) {
+			ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
+							       "Too many results to base search for local entry"));
+			talloc_free(ares);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		/* Store local result */
+		sc->local_res = ares;
+
+		/* Merge remote into local message */
+		ret = ldb_msg_merge_local(sc->ac->module, ares->message, sc->remote_res->message);
+		if (ret) {
+			talloc_free(ares);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		return map_up_callback(ldb, sc->ac->orig_req, ares);
+
+	case LDB_REPLY_DONE:
+		/* No local record found, continue with remote record */
+		if (sc->local_res == NULL) {
+			return map_up_callback(ldb, sc->ac->orig_req, sc->remote_res);
+		}
+		return LDB_SUCCESS;
+
+	default:
+		ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
+						       "Unexpected result type in base search for local entry"));
+		talloc_free(ares);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+}
+
+/* Search the local part of a remote search result. */
+int map_remote_search_callback(struct ldb_context *ldb, void *context, struct ldb_reply *ares)
+{
+	struct map_context *ac;
+	struct map_search_context *sc;
+	struct ldb_request *req;
+	int ret;
+
+	if (context == NULL || ares == NULL) {
+		ldb_set_errstring(ldb, talloc_asprintf(ldb, "ldb_map: "
+						       "NULL Context or Result in `map_remote_search_callback`"));
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ac = talloc_get_type(context, struct map_context);
+
+	/* It's not a record, stop searching */
+	if (ares->type != LDB_REPLY_ENTRY) {
+		return map_up_callback(ldb, ac->orig_req, ares);
+	}
+
+	/* Map result record into a local message */
+	ret = map_reply_remote(ac->module, ares);
+	if (ret) {
+		talloc_free(ares);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* There is no local db, stop searching */
+	if (!map_check_local_db(ac->module)) {
+		return map_up_callback(ldb, ac->orig_req, ares);
+	}
+
+	/* Prepare local search context */
+	sc = map_init_search_context(ac, ares);
+	if (sc == NULL) {
+		talloc_free(ares);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* Prepare local search request */
+	/* TODO: use GUIDs here instead? */
+
+	ac->search_reqs = talloc_realloc(ac, ac->search_reqs, struct ldb_request *, ac->num_searches + 2);
+	if (ac->search_reqs == NULL) {
+		talloc_free(ares);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ac->search_reqs[ac->num_searches]
+		= req = map_search_base_req(ac, ares->message->dn, 
+					    NULL, NULL, sc, map_local_merge_callback);
+	if (req == NULL) {
+		talloc_free(sc);
+		talloc_free(ares);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ac->num_searches++;
+	ac->search_reqs[ac->num_searches] = NULL;
+
+	return ldb_next_request(ac->module, req);
+}
+
+/* Search a record. */
+int map_search(struct ldb_module *module, struct ldb_request *req)
+{
+	struct ldb_handle *h;
+	struct map_context *ac;
+	struct ldb_parse_tree *local_tree, *remote_tree;
+	const char **local_attrs, **remote_attrs;
+	int ret;
+
+	/* Do not manipulate our control entries */
+	if (ldb_dn_is_special(req->op.search.base))
+		return ldb_next_request(module, req);
+
+	/* No mapping requested, skip to next module */
+	if ((req->op.search.base) && (!ldb_dn_check_local(module, req->op.search.base))) {
+		return ldb_next_request(module, req);
+	}
+
+	/* TODO: How can we be sure about which partition we are
+	 *	 targetting when there is no search base? */
+
+	/* Prepare context and handle */
+	h = map_init_handle(req, module);
+	if (h == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ac = talloc_get_type(h->private_data, struct map_context);
+
+	ac->search_reqs = talloc_array(ac, struct ldb_request *, 2);
+	if (ac->search_reqs == NULL) {
+		talloc_free(h);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ac->num_searches = 1;
+	ac->search_reqs[1] = NULL;
+
+	/* Prepare the remote operation */
+	ac->search_reqs[0] = talloc(ac, struct ldb_request);
+	if (ac->search_reqs[0] == NULL) {
+		goto oom;
+	}
+
+	*(ac->search_reqs[0]) = *req;	/* copy the request */
+
+	ac->search_reqs[0]->handle = h;	/* return our own handle to deal with this call */
+
+	ac->search_reqs[0]->context = ac;
+	ac->search_reqs[0]->callback = map_remote_search_callback;
+
+	/* Split local from remote attrs */
+	ret = map_attrs_collect_and_partition(module, ac, ac->search_reqs[0], &local_attrs, &remote_attrs, req->op.search.attrs, req->op.search.tree);
+	if (ret) {
+		goto failed;
+	}
+
+	ac->local_attrs = local_attrs;
+	ac->search_reqs[0]->op.search.attrs = remote_attrs;
+
+	/* Split local from remote tree */
+	ret = ldb_parse_tree_partition(module, ac, ac->search_reqs[0], &local_tree, &remote_tree, req->op.search.tree);
+	if (ret) {
+		goto failed;
+	}
+
+	if (((local_tree == NULL) ^ (remote_tree == NULL)) &&
+	    (!ldb_parse_tree_check_splittable(req->op.search.tree))) {
+		/* The query can't safely be split, enumerate the remote partition */
+		local_tree = NULL;
+		remote_tree = NULL;
+	}
+
+	if (local_tree == NULL) {
+		/* Construct default local parse tree */
+		local_tree = talloc_zero(ac, struct ldb_parse_tree);
+		if (local_tree == NULL) {
+			map_oom(ac->module);
+			goto failed;
+		}
+
+		local_tree->operation = LDB_OP_PRESENT;
+		local_tree->u.present.attr = talloc_strdup(local_tree, IS_MAPPED);
+	}
+	if (remote_tree == NULL) {
+		/* Construct default remote parse tree */
+		remote_tree = ldb_parse_tree(ac->search_reqs[0], NULL);
+		if (remote_tree == NULL) {
+			goto failed;
+		}
+	}
+
+	ac->local_tree = local_tree;
+	ac->search_reqs[0]->op.search.tree = remote_tree;
+
+	ldb_set_timeout_from_prev_req(module->ldb, req, ac->search_reqs[0]);
+
+	h->state = LDB_ASYNC_INIT;
+	h->status = LDB_SUCCESS;
+
+	ac->step = MAP_SEARCH_REMOTE;
+
+	ret = ldb_next_remote_request(module, ac->search_reqs[0]);
+	if (ret == LDB_SUCCESS) {
+		req->handle = h;
+	}
+	return ret;
+
+oom:
+	map_oom(module);
+failed:
+	talloc_free(h);
+	return LDB_ERR_OPERATIONS_ERROR;
+}
diff --git a/source4/lib/ldb/modules/ldb_map_private.h b/source4/lib/ldb/modules/ldb_map_private.h
new file mode 100644
index 0000000000..1b21fcf558
--- /dev/null
+++ b/source4/lib/ldb/modules/ldb_map_private.h
@@ -0,0 +1,118 @@
+
+/* A handy macro to report Out of Memory conditions */
+#define map_oom(module) ldb_set_errstring(module->ldb, talloc_asprintf(module, "Out of Memory"));
+
+/* The type of search callback functions */
+typedef int (*ldb_search_callback)(struct ldb_context *, void *, struct ldb_reply *);
+
+/* The special DN from which the local and remote base DNs are fetched */
+#define MAP_DN_NAME	"@MAP"
+#define MAP_DN_FROM	"@FROM"
+#define MAP_DN_TO	"@TO"
+
+/* Private data structures
+ * ======================= */
+
+/* Global private data */
+struct map_private {
+	struct ldb_map_context context;
+};
+
+/* Context data for mapped requests */
+struct map_context {
+	enum map_step {
+		MAP_SEARCH_REMOTE,
+		MAP_ADD_REMOTE,
+		MAP_ADD_LOCAL,
+		MAP_SEARCH_SELF_MODIFY,
+		MAP_MODIFY_REMOTE,
+		MAP_MODIFY_LOCAL,
+		MAP_SEARCH_SELF_DELETE,
+		MAP_DELETE_REMOTE,
+		MAP_DELETE_LOCAL,
+		MAP_SEARCH_SELF_RENAME,
+		MAP_RENAME_REMOTE,
+		MAP_RENAME_FIXUP,
+		MAP_RENAME_LOCAL
+	} step;
+
+	struct ldb_module *module;
+
+	const struct ldb_dn *local_dn;
+	const struct ldb_parse_tree *local_tree;
+	const char * const *local_attrs;
+
+	struct ldb_request *orig_req;
+	struct ldb_request *local_req;
+	struct ldb_request *remote_req;
+	struct ldb_request *down_req;
+	struct ldb_request *search_req;
+
+	/* for search, we may have a lot of contexts */
+	int num_searches;
+	struct ldb_request **search_reqs;
+};
+
+/* Context data for mapped search requests */
+struct map_search_context {
+	struct map_context *ac;
+	struct ldb_reply *local_res;
+	struct ldb_reply *remote_res;
+};
+
+
+/* Common operations
+ * ================= */
+
+/* The following definitions come from lib/ldb/modules/ldb_map.c */
+const struct ldb_map_context *map_get_context(struct ldb_module *module);
+struct map_search_context *map_init_search_context(struct map_context *ac, struct ldb_reply *ares);
+struct ldb_handle *map_init_handle(struct ldb_request *req, struct ldb_module *module);
+
+int ldb_next_remote_request(struct ldb_module *module, struct ldb_request *request);
+
+BOOL map_check_local_db(struct ldb_module *module);
+BOOL map_attr_check_remote(const struct ldb_map_context *data, const char *attr);
+BOOL ldb_dn_check_local(struct ldb_module *module, const struct ldb_dn *dn);
+
+const struct ldb_map_attribute *map_attr_find_local(const struct ldb_map_context *data, const char *name);
+const struct ldb_map_attribute *map_attr_find_remote(const struct ldb_map_context *data, const char *name);
+
+const char *map_attr_map_local(void *mem_ctx, const struct ldb_map_attribute *map, const char *attr);
+const char *map_attr_map_remote(void *mem_ctx, const struct ldb_map_attribute *map, const char *attr);
+
+struct ldb_val ldb_val_map_local(struct ldb_module *module, void *mem_ctx, const struct ldb_map_attribute *map, struct ldb_val val);
+struct ldb_val ldb_val_map_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_map_attribute *map, struct ldb_val val);
+
+struct ldb_dn *ldb_dn_map_local(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn);
+struct ldb_dn *ldb_dn_map_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn);
+struct ldb_dn *ldb_dn_map_rebase_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn);
+
+struct ldb_request *map_search_base_req(struct map_context *ac, const struct ldb_dn *dn, const char * const *attrs, const struct ldb_parse_tree *tree, void *context, ldb_search_callback callback);
+struct ldb_request *map_search_self_req(struct map_context *ac, const struct ldb_dn *dn);
+struct ldb_request *map_build_fixup_req(struct map_context *ac, const struct ldb_dn *olddn, const struct ldb_dn *newdn);
+
+
+/* LDB Requests
+ * ============ */
+
+/* The following definitions come from lib/ldb/modules/ldb_map_inbound.c */
+int map_add_do_remote(struct ldb_handle *handle);
+int map_add_do_local(struct ldb_handle *handle);
+int map_add(struct ldb_module *module, struct ldb_request *req);
+
+int map_modify_do_remote(struct ldb_handle *handle);
+int map_modify_do_local(struct ldb_handle *handle);
+int map_modify(struct ldb_module *module, struct ldb_request *req);
+
+int map_delete_do_remote(struct ldb_handle *handle);
+int map_delete_do_local(struct ldb_handle *handle);
+int map_delete(struct ldb_module *module, struct ldb_request *req);
+
+int map_rename_do_remote(struct ldb_handle *handle);
+int map_rename_do_fixup(struct ldb_handle *handle);
+int map_rename_do_local(struct ldb_handle *handle);
+int map_rename(struct ldb_module *module, struct ldb_request *req);
+
+/* The following definitions come from lib/ldb/modules/ldb_map_outbound.c */
+int map_search(struct ldb_module *module, struct ldb_request *req);
diff --git a/testdata/samba3/samba3.ldif b/testdata/samba3/samba3.ldif
index 67c0ae1432..470f7ff246 100644
--- a/testdata/samba3/samba3.ldif
+++ b/testdata/samba3/samba3.ldif
@@ -1,19 +1,19 @@
-dn: sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: sambaDomainName=TESTS,${BASEDN}
 objectclass: sambaDomain
 objectclass: top
 sambaSID: S-1-5-21-4231626423-2410014848-2360679739
 sambaNextRid: 2000
 sambaDomainName: TESTS
 
-dn: ou=Users,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: ou=Users,sambaDomainName=TESTS,${BASEDN}
 objectClass: organizationalUnit
 ou: Users
 
-dn: ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: organizationalUnit
 ou: Groups
 
-dn: uid=nobody,ou=Users,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: uid=nobody,ou=Users,sambaDomainName=TESTS,${BASEDN}
 cn: nobody
 sn: nobody
 objectClass: inetOrgPerson
@@ -40,7 +40,7 @@ sambaAcctFlags: [NU         ]
 sambaSID: S-1-5-21-4231626423-2410014848-2360679739-2998
 loginShell: /bin/false
 
-dn: cn=Domain Admins,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Domain Admins,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 512
@@ -51,7 +51,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-512
 sambaGroupType: 2
 displayName: Domain Admins
 
-dn: cn=Domain Users,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Domain Users,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 513
@@ -61,7 +61,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-513
 sambaGroupType: 2
 displayName: Domain Users
 
-dn: cn=Domain Guests,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Domain Guests,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 514
@@ -71,7 +71,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-514
 sambaGroupType: 2
 displayName: Domain Guests
 
-dn: cn=Print Operators,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Print Operators,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 550
@@ -81,7 +81,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-550
 sambaGroupType: 2
 displayName: Print Operators
 
-dn: cn=Backup Operators,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Backup Operators,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 551
@@ -91,7 +91,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-551
 sambaGroupType: 2
 displayName: Backup Operators
 
-dn: cn=Replicator,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Replicator,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 552
@@ -101,7 +101,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-552
 sambaGroupType: 2
 displayName: Replicator
 
-dn: cn=Domain Computers,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Domain Computers,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 553
@@ -111,7 +111,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-553
 sambaGroupType: 2
 displayName: Domain Computers
 
-dn: cn=Administrators,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Administrators,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 544
@@ -121,7 +121,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-544
 sambaGroupType: 2
 displayName: Administrators
 
-dn: cn=Users,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Users,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 545
@@ -131,7 +131,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-545
 sambaGroupType: 2
 displayName: users
 
-dn: cn=Guests,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Guests,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 546
@@ -142,7 +142,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-546
 sambaGroupType: 2
 displayName: Guests
 
-dn: cn=Power Users,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Power Users,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 547
@@ -152,7 +152,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-547
 sambaGroupType: 2
 displayName: Power Users
 
-dn: cn=Account Operators,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Account Operators,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 548
@@ -162,7 +162,7 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-548
 sambaGroupType: 2
 displayName: Account Operators
 
-dn: cn=Server Operators,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: cn=Server Operators,ou=Groups,sambaDomainName=TESTS,${BASEDN}
 objectClass: posixGroup
 objectClass: sambaGroupMapping
 gidNumber: 549
@@ -172,11 +172,11 @@ sambaSID: S-1-5-21-4231626423-2410014848-2360679739-549
 sambaGroupType: 2
 displayName: Server Operators
 
-dn: ou=Computers,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: ou=Computers,sambaDomainName=TESTS,${BASEDN}
 objectClass: organizationalUnit
 ou: Computers
 
-dn: uid=Administrator,ou=Users,sambaDomainName=TESTS,dc=vernstok,dc=nl
+dn: uid=Administrator,ou=Users,sambaDomainName=TESTS,${BASEDN}
 cn: Administrator
 sn: Administrator
 objectClass: inetOrgPerson
diff --git a/testprogs/ejs/samba3sam b/testprogs/ejs/samba3sam
index e9a610eea5..0f6d1a82ab 100755
--- a/testprogs/ejs/samba3sam
+++ b/testprogs/ejs/samba3sam
@@ -8,75 +8,92 @@ libinclude("base.js");
 var mypath = substr(ARGV[0], 0, -strlen("samba3sam"));
 
 var sys = sys_init();
-var s3url;
+var s3url = "tdb://samba3.ldb";
+var s4url = "tdb://samba4.ldb";
 var s3 = ldb_init();
+var s4 = ldb_init();
+var msg;
 var ok;
 
-if (ARGV.length == 2) {
-	s3url = ARGV[1];
-	ok = s3.connect(s3url);
-	assert(ok);
-} else {
-	s3url = "tdb://samba3.ldb";
-	sys.unlink("samba3.ldb");
-	println("Adding samba3 LDIF...");
-	var s3 = ldb_init();
-	ok = s3.connect(s3url);
-	assert(ok);
-	var ldif = sys.file_load(mypath + "../../testdata/samba3/samba3.ldif");
-	assert(ldif != undefined);
-	ok = s3.add(ldif);
-	assert(ok);
-}
+var local = new Object();
+local.BASEDN = "dc=vernstok,dc=nl";
+var remote = new Object();
+remote.BASEDN = "CN=Samba3Sam," + local.BASEDN;
+
+var prt_ldif = sprintf("dn: @PARTITION
+partition: %s:%s
+partition: %s:%s", remote.BASEDN, s3url, local.BASEDN, s4url);
+
+var map_ldif = sprintf("dn: @MAP=samba3sam
+@FROM: %s
+@TO: %s", local.BASEDN, remote.BASEDN);
+
+var mod_ldif = "dn: @MODULES
+@LIST: rootdse,paged_results,server_sort,extended_dn,asq,samldb,objectclass,password_hash,operational,objectguid,rdn_name,samba3sam,partition";
+
+sys.unlink("samba3.ldb");
+ok = s3.connect(s3url);
+assert(ok);
+
+println("Initial samba3 LDIF...");
+var path = "../../testdata/samba3/samba3.ldif"
+var ldif = sys.file_load(mypath + path);
+ldif = substitute_var(ldif, remote);
+assert(ldif != undefined);
+ok = s3.add(ldif);
+assert(ok);
 
-println("Initial samba4 LDIF...");
-var s4 = ldb_init();
 sys.unlink("samba4.ldb");
 ok = s4.connect("tdb://samba4.ldb");
 assert(ok);
 
-var ldif = sys.file_load(mypath + "../../source/setup/provision_init.ldif");
+println("Initial samba4 LDIF...");
+var path = "../../source/setup/provision_init.ldif";
+var ldif = sys.file_load(mypath + path);
+ldif = substitute_var(ldif, local);
 assert(ldif != undefined);
 ok = s4.add(ldif);
 assert(ok);
 
-var ldif = sys.file_load(mypath + "../../source/setup/provision_templates.ldif");
-var subobj = new Object();
-subobj.BASEDN = "dc=vernstok,dc=nl";
-ldif = substitute_var(ldif, subobj);
+var path = "../../source/setup/provision_templates.ldif";
+var ldif = sys.file_load(mypath + path);
+ldif = substitute_var(ldif, local);
 assert(ldif != undefined);
 ok = s4.add(ldif);
 assert(ok);
 
+println("Registering partitions...");
+var ldif = substitute_var(prt_ldif, local);
+assert(ldif != undefined);
+ok = s4.add(ldif);
+assert(ok);
 
-
-ok = s4.add(sprintf("dn: @MAP=samba3sam
-@MAP_URL: %s", s3url));
+println("Registering mapping...");
+var ldif = substitute_var(map_ldif, local);
+assert(ldif != undefined);
+ok = s4.add(ldif);
 assert(ok);
 
-ok = s4.modify("
-dn: @MODULES
-replace: @LIST
-@LIST: samldb,timestamps,objectguid,rdn_name,samba3sam");
+println("Registering modules...");
+var ldif = substitute_var(mod_ldif, local);
+assert(ldif != undefined);
+ok = s4.add(ldif);
 assert(ok);
 
-println("Reconnecting to LDB database");
+println("Reconnecting to LDB database...");
 s4 = ldb_init();
-ok = s4.connect("tdb://samba4.ldb");
+ok = s4.connect(s4url);
 assert(ok);
 
-msg = s4.search("(ou=Users)");
-assert(msg.length == 1);
-
 println("Looking up by non-mapped attribute");
 msg = s4.search("(cn=Administrator)");
-assert(msg[0].cn == "Administrator");
 assert(msg.length == 1);
+assert(msg[0].cn == "Administrator");
 
 println("Looking up by mapped attribute");
 msg = s4.search("(name=Backup Operators)");
-assert(msg[0].name == "Backup Operators");
 assert(msg.length == 1);
+assert(msg[0].name == "Backup Operators");
 
 println("Looking up by old name of renamed attribute");
 msg = s4.search("(displayName=Backup Operators)");
@@ -88,8 +105,9 @@ assert(msg.length == 1);
 assert(msg[0].dn == "cn=Replicator,ou=Groups,sambaDomainName=TESTS,dc=vernstok,dc=nl");
 assert(msg[0].objectSid == "S-1-5-21-4231626423-2410014848-2360679739-552");
 
-println("Checking mapping of objectclass");
-var oc = msg[0].objectclass;
+println("Checking mapping of objectClass");
+var oc = msg[0].objectClass;
+assert(oc != undefined);
 for (var i in oc) {
 	assert(oc[i] == "posixGroup" || oc[i] == "group");
 }
@@ -104,8 +122,13 @@ showInAdvancedViewOnly: TRUE
 ");
 assert(ok);
 
-println("Checking for existance of record");
+println("Checking for existence of record (local)");
+/* TODO: This record must be searched in the local database, which is currently only supported for base searches
 msg = s4.search("(cn=Foo)", new Array('foo','blah','cn','showInAdvancedViewOnly'));
+TODO: Actually, this version should work as well but doesn't...
+msg = s4.search("(cn=Foo)", "dc=idealx,dc=org", s4.LDB_SCOPE_SUBTREE new Array('foo','blah','cn','showInAdvancedViewOnly'));
+*/
+msg = s4.search("", "cn=Foo,dc=idealx,dc=org", s4.LDB_SCOPE_BASE new Array('foo','blah','cn','showInAdvancedViewOnly'));
 assert(msg.length == 1);
 assert(msg[0].showInAdvancedViewOnly == "TRUE");
 assert(msg[0].foo == "bar");
@@ -121,10 +144,24 @@ cn: Niemand
 ");
 assert(ok);
 
-println("Checking for existance of record (mapped)");
-msg = s4.search("(unixName=bin)", new Array('unixName','cn','dn'));
+println("Checking for existence of record (remote)");
+msg = s4.search("(unixName=bin)", new Array('unixName','cn','dn', 'unicodePwd'));
 assert(msg.length == 1);
+assert(msg[0].cn == "Niemand"); 
+assert(msg[0].unicodePwd == "geheim");
+
+println("Checking for existence of record (local && remote)");
+msg = s4.search("(&(unixName=bin)(unicodePwd=geheim))", new Array('unixName','cn','dn', 'unicodePwd'));
+assert(msg.length == 1);                // TODO: should check with more records
+assert(msg[0].cn == "Niemand");
+assert(msg[0].unixName == "bin");
+assert(msg[0].unicodePwd == "geheim");
+
+println("Checking for existence of record (local || remote)");
+msg = s4.search("(|(unixName=bin)(unicodePwd=geheim))", new Array('unixName','cn','dn', 'unicodePwd'));
+assert(msg.length == 1);                // TODO: should check with more records
 assert(msg[0].cn == "Niemand");
+assert(msg[0].unixName == "bin" || msg[0].unicodePwd == "geheim");
 
 println("Checking for data in destination database");
 msg = s3.search("(cn=Niemand)");