r9391: Convert all the code to use struct ldb_dn to ohandle ldap like distinguished names

Provide more functions to handle DNs in this form
(This used to be commit 692e35b7797e39533dd2a1c4b63d9da30f1eb5ba)

56 files changed, 1477 insertions, 864 deletions

diff --git a/source4/auth/auth_sam.c b/source4/auth/auth_sam.c
index 555b2a25ac..008a7f3a84 100644
--- a/source4/auth/auth_sam.c
+++ b/source4/auth/auth_sam.c
@@ -217,7 +217,7 @@ static NTSTATUS authsam_search_account(TALLOC_CTX *mem_ctx, struct ldb_context *
 	int ret;
 	int ret_domain;
 
-	const char *domain_dn = NULL;
+	const struct ldb_dn *domain_dn = NULL;
 
 	const char *attrs[] = {"unicodePwd", "lmPwdHash", "ntPwdHash",
 			       "userAccountControl",
@@ -265,7 +265,7 @@ static NTSTATUS authsam_search_account(TALLOC_CTX *mem_ctx, struct ldb_context *
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 
-		domain_dn = samdb_result_string(msgs_domain[0], "nCName", NULL);
+		domain_dn = samdb_result_dn(mem_ctx, msgs_domain[0], "nCName", NULL);
 	}
 
 	/* pull the user attributes */
@@ -316,7 +316,7 @@ static NTSTATUS authsam_search_account(TALLOC_CTX *mem_ctx, struct ldb_context *
 		}
 
 		ret_domain = gendb_search(sam_ctx, mem_ctx, NULL, &msgs_domain, domain_attrs,
-					  "(nCName=%s)", msgs_tmp[0]->dn);
+					  "(nCName=%s)", ldb_dn_linearize(msgs_tmp, msgs_tmp[0]->dn));
 
 		if (ret_domain == -1) {
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
@@ -324,13 +324,13 @@ static NTSTATUS authsam_search_account(TALLOC_CTX *mem_ctx, struct ldb_context *
 		
 		if (ret_domain == 0) {
 			DEBUG(3,("check_sam_security: Couldn't find domain [%s] in passdb file.\n",
-				 msgs_tmp[0]->dn));
+				 ldb_dn_linearize(msgs_tmp, msgs_tmp[0]->dn)));
 			return NT_STATUS_NO_SUCH_USER;
 		}
 		
 		if (ret_domain > 1) {
 			DEBUG(0,("Found %d records matching domain [%s]\n", 
-				 ret_domain, msgs_tmp[0]->dn));
+				 ret_domain, ldb_dn_linearize(msgs_tmp, msgs_tmp[0]->dn)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 
@@ -356,7 +356,7 @@ static NTSTATUS authsam_authenticate(struct auth_context *auth_context,
 	NTTIME last_set_time;
 	struct samr_Password *lm_pwd, *nt_pwd;
 	NTSTATUS nt_status;
-	const char *domain_dn = samdb_result_string(msgs_domain[0], "nCName", "");
+	struct ldb_dn *domain_dn = samdb_result_dn(mem_ctx, msgs_domain[0], "nCName", ldb_dn_new(mem_ctx));
 
 	acct_flags = samdb_result_acct_flags(msgs[0], "userAccountControl");
 	
@@ -407,7 +407,8 @@ static NTSTATUS authsam_make_server_info(TALLOC_CTX *mem_ctx, struct ldb_context
 	struct dom_sid **groupSIDs = NULL;
 	struct dom_sid *account_sid;
 	struct dom_sid *primary_group_sid;
-	const char *str, *ncname;
+	const char *str;
+	struct ldb_dn *ncname;
 	int i;
 	uint_t rid;
 	TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
@@ -415,7 +416,7 @@ static NTSTATUS authsam_make_server_info(TALLOC_CTX *mem_ctx, struct ldb_context
 	group_ret = gendb_search(sam_ctx,
 				 tmp_ctx, NULL, &group_msgs, group_attrs,
 				 "(&(member=%s)(sAMAccountType=*))", 
-				 msgs[0]->dn);
+				 ldb_dn_linearize(tmp_ctx, msgs[0]->dn));
 	if (group_ret == -1) {
 		talloc_free(tmp_ctx);
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
@@ -490,7 +491,7 @@ static NTSTATUS authsam_make_server_info(TALLOC_CTX *mem_ctx, struct ldb_context
 	server_info->acct_expiry = samdb_result_nttime(msgs[0], "accountExpires", 0);
 	server_info->last_password_change = samdb_result_nttime(msgs[0], "pwdLastSet", 0);
 
-	ncname = samdb_result_string(msgs_domain[0], "nCName", "");
+	ncname = samdb_result_dn(mem_ctx, msgs_domain[0], "nCName", ldb_dn_new(mem_ctx));
 
 	server_info->allow_password_change = samdb_result_allow_password_change(sam_ctx, mem_ctx, 
 							ncname, msgs[0], "pwdLastSet");
diff --git a/source4/auth/gensec/schannel_state.c b/source4/auth/gensec/schannel_state.c
index 0c5ce09637..4864221ade 100644
--- a/source4/auth/gensec/schannel_state.c
+++ b/source4/auth/gensec/schannel_state.c
@@ -100,16 +100,15 @@ NTSTATUS schannel_store_session_key(TALLOC_CTX *mem_ctx,
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	msg = ldb_msg_new(mem_ctx);
+	msg = ldb_msg_new(ldb);
 	if (msg == NULL) {
 		talloc_free(ldb);
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	msg->dn = talloc_asprintf(msg, "computerName=%s", creds->computer_name);
+	msg->dn = ldb_dn_build_child(msg, "computerName", creds->computer_name, NULL);
 	if (msg->dn == NULL) {
 		talloc_free(ldb);
-		talloc_free(msg);
 		return NT_STATUS_NO_MEMORY;
 	}
 
@@ -134,13 +133,11 @@ NTSTATUS schannel_store_session_key(TALLOC_CTX *mem_ctx,
 
 	if (ret != 0) {
 		DEBUG(0,("Unable to add %s to session key db - %s\n", 
-			 msg->dn, ldb_errstring(ldb)));
+			 ldb_dn_linearize(msg, msg->dn), ldb_errstring(ldb)));
 		talloc_free(ldb);
-		talloc_free(msg);
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
-	talloc_free(msg);
 	talloc_free(ldb);
 
 	return NT_STATUS_OK;
diff --git a/source4/cldap_server/netlogon.c b/source4/cldap_server/netlogon.c
index a39ad64a8e..bfecc3576f 100644
--- a/source4/cldap_server/netlogon.c
+++ b/source4/cldap_server/netlogon.c
@@ -81,9 +81,10 @@ static NTSTATUS cldapd_netlogon_fill(struct cldapd_server *cldapd,
 	/* try and find the domain */
 	ret = gendb_search(cldapd->samctx, mem_ctx, NULL, &ref_res, ref_attrs, 
 			   "(&(objectClass=crossRef)(ncName=%s))", 
-			   dom_res[0]->dn);
+			   ldb_dn_linearize(mem_ctx, dom_res[0]->dn));
 	if (ret != 1) {
-		DEBUG(2,("Unable to find referece to '%s' in sam\n", dom_res[0]->dn));
+		DEBUG(2,("Unable to find referece to '%s' in sam\n",
+			 ldb_dn_linearize(mem_ctx, dom_res[0]->dn)));
 		return NT_STATUS_NO_SUCH_DOMAIN;
 	}
 
diff --git a/source4/dsdb/samdb/ldb_modules/objectguid.c b/source4/dsdb/samdb/ldb_modules/objectguid.c
index 873c89cf28..dc4576a8f9 100644
--- a/source4/dsdb/samdb/ldb_modules/objectguid.c
+++ b/source4/dsdb/samdb/ldb_modules/objectguid.c
@@ -42,7 +42,7 @@ struct private_data {
 	const char *error_string;
 };
 
-static int objectguid_search(struct ldb_module *module, const char *base,
+static int objectguid_search(struct ldb_module *module, const struct ldb_dn *base,
 				  enum ldb_scope scope, const char *expression,
 				  const char * const *attrs, struct ldb_message ***res)
 {
@@ -50,7 +50,7 @@ static int objectguid_search(struct ldb_module *module, const char *base,
 	return ldb_next_search(module, base, scope, expression, attrs, res);
 }
 
-static int objectguid_search_bytree(struct ldb_module *module, const char *base,
+static int objectguid_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 				    enum ldb_scope scope, struct ldb_parse_tree *tree,
 				    const char * const *attrs, struct ldb_message ***res)
 {
@@ -83,7 +83,7 @@ static int objectguid_add_record(struct ldb_module *module, const struct ldb_mes
 
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "objectguid_add_record\n");
 
-	if (msg->dn[0] == '@') { /* do not manipulate our control entries */
+	if (ldb_dn_is_special(msg->dn)) { /* do not manipulate our control entries */
 		return ldb_next_add_record(module, msg);
 	}
 
@@ -131,13 +131,13 @@ static int objectguid_modify_record(struct ldb_module *module, const struct ldb_
 	return ldb_next_modify_record(module, msg);
 }
 
-static int objectguid_delete_record(struct ldb_module *module, const char *dn)
+static int objectguid_delete_record(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "objectguid_delete_record\n");
 	return ldb_next_delete_record(module, dn);
 }
 
-static int objectguid_rename_record(struct ldb_module *module, const char *olddn, const char *newdn)
+static int objectguid_rename_record(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "objectguid_rename_record\n");
 	return ldb_next_rename_record(module, olddn, newdn);
diff --git a/source4/dsdb/samdb/ldb_modules/samldb.c b/source4/dsdb/samdb/ldb_modules/samldb.c
index 88c1ab5804..ed7c135efa 100644
--- a/source4/dsdb/samdb/ldb_modules/samldb.c
+++ b/source4/dsdb/samdb/ldb_modules/samldb.c
@@ -44,7 +44,7 @@ struct private_data {
 	const char *error_string;
 };
 
-static int samldb_search(struct ldb_module *module, const char *base,
+static int samldb_search(struct ldb_module *module, const struct ldb_dn *base,
 				  enum ldb_scope scope, const char *expression,
 				  const char * const *attrs, struct ldb_message ***res)
 {
@@ -52,7 +52,7 @@ static int samldb_search(struct ldb_module *module, const char *base,
 	return ldb_next_search(module, base, scope, expression, attrs, res);
 }
 
-static int samldb_search_bytree(struct ldb_module *module, const char *base,
+static int samldb_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 				enum ldb_scope scope, struct ldb_parse_tree *tree,
 				const char * const *attrs, struct ldb_message ***res)
 {
@@ -65,7 +65,7 @@ static int samldb_search_bytree(struct ldb_module *module, const char *base,
   return 0 on failure, the id on success
 */
 static int samldb_allocate_next_rid(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
-				   const char *dn, uint32_t *id)
+				   const struct ldb_dn *dn, uint32_t *id)
 {
 	const char * const attrs[2] = { "nextRid", NULL };
 	struct ldb_message **res = NULL;
@@ -82,7 +82,7 @@ static int samldb_allocate_next_rid(struct ldb_context *ldb, TALLOC_CTX *mem_ctx
 	}
 	str = ldb_msg_find_string(res[0], "nextRid", NULL);
 	if (str == NULL) {
-		ldb_debug(ldb, LDB_DEBUG_FATAL, "attribute nextRid not found in %s\n", dn);
+		ldb_debug(ldb, LDB_DEBUG_FATAL, "attribute nextRid not found in %s\n", ldb_dn_linearize(res, dn));
 		talloc_free(res);
 		return -1;
 	}
@@ -99,7 +99,7 @@ static int samldb_allocate_next_rid(struct ldb_context *ldb, TALLOC_CTX *mem_ctx
 	/* we do a delete and add as a single operation. That prevents
 	   a race */
 	ZERO_STRUCT(msg);
-	msg.dn = talloc_strdup(mem_ctx, dn);
+	msg.dn = ldb_dn_copy(mem_ctx, dn);
 	if (!msg.dn) {
 		return -1;
 	}
@@ -141,29 +141,35 @@ static int samldb_allocate_next_rid(struct ldb_context *ldb, TALLOC_CTX *mem_ctx
 	return 0;
 }
 
-static char *samldb_search_domain(struct ldb_module *module, TALLOC_CTX *mem_ctx, const char *dn)
+static struct ldb_dn *samldb_search_domain(struct ldb_module *module, TALLOC_CTX *mem_ctx, const struct ldb_dn *dn)
 {
-	const char *sdn;
+	TALLOC_CTX *local_ctx;
+	struct ldb_dn *sdn;
 	struct ldb_message **res = NULL;
 	int ret = 0;
 
-	sdn = dn;
-	while ((sdn = strchr(sdn, ',')) != NULL) {
-
-		sdn++;
+	local_ctx = talloc_named(mem_ctx, 0, "samldb_search_domain memory conext");
+	if (local_ctx == NULL) return NULL;
 
+	sdn = ldb_dn_copy(local_ctx, dn);
+	do {
 		ret = ldb_search(module->ldb, sdn, LDB_SCOPE_BASE, "objectClass=domain", NULL, &res);
 		talloc_free(res);
 
 		if (ret == 1)
 			break;
-	}
+
+	} while ((sdn = ldb_dn_get_parent(local_ctx, sdn)));
 
 	if (ret != 1) {
+		talloc_free(local_ctx);
 		return NULL;
 	}
 
-	return talloc_strdup(mem_ctx, sdn);
+	talloc_steal(mem_ctx, sdn);
+	talloc_free(local_ctx);
+
+	return sdn;
 }
 
 /* search the domain related to the provided dn
@@ -171,11 +177,11 @@ static char *samldb_search_domain(struct ldb_module *module, TALLOC_CTX *mem_ctx
    return the new sid string
 */
 static struct dom_sid *samldb_get_new_sid(struct ldb_module *module, 
-					  TALLOC_CTX *mem_ctx, const char *obj_dn)
+					  TALLOC_CTX *mem_ctx, const struct ldb_dn *obj_dn)
 {
 	const char * const attrs[2] = { "objectSid", NULL };
 	struct ldb_message **res = NULL;
-	const char *dom_dn;
+	const struct ldb_dn *dom_dn;
 	uint32_t rid;
 	int ret, tries = 10;
 	struct dom_sid *dom_sid, *obj_sid;
@@ -190,7 +196,7 @@ static struct dom_sid *samldb_get_new_sid(struct ldb_module *module,
 	
 	dom_dn = samldb_search_domain(module, mem_ctx, obj_dn);
 	if (dom_dn == NULL) {
-		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "Invalid dn (%s) not child of a domain object!\n", obj_dn);
+		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "Invalid dn (%s) not child of a domain object!\n", ldb_dn_linearize(mem_ctx, obj_dn));
 		return NULL;
 	}
 
@@ -221,7 +227,7 @@ static struct dom_sid *samldb_get_new_sid(struct ldb_module *module,
 		}
 	}
 	if (ret != 0) {
-		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "Failed to increment nextRid of %s\n", dom_dn);
+		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "Failed to increment nextRid of %s\n", ldb_dn_linearize(mem_ctx, dom_dn));
 		talloc_free(res);
 		return NULL;
 	}
@@ -243,22 +249,6 @@ static char *samldb_generate_samAccountName(const void *mem_ctx) {
 	return name;
 }
 
-static BOOL samldb_get_rdn(void *mem_ctx, const char *dn, struct ldb_dn_component **rdn)
-{
-	struct ldb_dn *dn_exploded = ldb_dn_explode(mem_ctx, dn);
-
-	if (!dn_exploded) {
-		return False;
-	}
-	
-	if (dn_exploded->comp_num < 1) {
-		return False;
-	}
-	
-	*rdn = &dn_exploded->components[0];
-	return True;
-}
-
 /* if value is not null also check for attribute to have exactly that value */
 static struct ldb_message_element *samldb_find_attribute(const struct ldb_message *msg, const char *name, const char *value)
 {
@@ -390,8 +380,8 @@ static struct ldb_message *samldb_fill_group_object(struct ldb_module *module, c
 		return NULL;
 	}
 
-	if ( ! samldb_get_rdn(msg2, msg2->dn, &rdn)) {
-		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "samldb_fill_group_object: Bad DN (%s)!\n", msg2->dn);
+	if ((rdn = ldb_dn_get_rdn(msg2, msg2->dn)) == NULL) {
+		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "samldb_fill_group_object: Bad DN (%s)!\n", ldb_dn_linearize(msg2, msg2->dn));
 		return NULL;
 	}
 	if (strcasecmp(rdn->name, "cn") != 0) {
@@ -454,7 +444,7 @@ static struct ldb_message *samldb_fill_user_or_computer_object(struct ldb_module
 		}
 	}
 
-	if ( ! samldb_get_rdn(msg2, msg2->dn, &rdn)) {
+	if ((rdn = ldb_dn_get_rdn(msg2, msg2->dn)) == NULL) {
 		return NULL;
 	}
 	if (strcasecmp(rdn->name, "cn") != 0) {
@@ -510,13 +500,15 @@ static struct ldb_message *samldb_fill_foreignSecurityPrincipal_object(struct ld
 		return NULL;
 	}
 
+	talloc_steal(msg, msg2);
+
 	if (samldb_copy_template(module, msg2, "(&(CN=TemplateForeignSecurityPrincipal)(objectclass=foreignSecurityPrincipalTemplate))") != 0) {
 		ldb_debug(module->ldb, LDB_DEBUG_WARNING, "samldb_fill_foreignSecurityPrincipal_object: Error copying template!\n");
 		return NULL;
 	}
 
-	if ( ! samldb_get_rdn(msg2, msg2->dn, &rdn)) {
-		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "samldb_fill_foreignSecurityPrincipal_object: Bad DN (%s)!\n", msg2->dn);
+	if ((rdn = ldb_dn_get_rdn(msg2, msg2->dn)) == NULL) {
+		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "samldb_fill_foreignSecurityPrincipal_object: Bad DN (%s)!\n", ldb_dn_linearize(msg2, msg2->dn));
 		return NULL;
 	}
 	if (strcasecmp(rdn->name, "cn") != 0) {
@@ -538,8 +530,6 @@ static struct ldb_message *samldb_fill_foreignSecurityPrincipal_object(struct ld
 		talloc_free(sid);
 	}
 
-	talloc_steal(msg, msg2);
-
 	return msg2;
 }
 
@@ -551,7 +541,7 @@ static int samldb_add_record(struct ldb_module *module, const struct ldb_message
 
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "samldb_add_record\n");
 
-	if (msg->dn[0] == '@') { /* do not manipulate our control entries */
+	if (strcmp(msg->dn->components[0].name, "@SPEACIAL") == 0) { /* do not manipulate our control entries */
 		return ldb_next_add_record(module, msg);
 	}
 
@@ -584,13 +574,13 @@ static int samldb_modify_record(struct ldb_module *module, const struct ldb_mess
 	return ldb_next_modify_record(module, msg);
 }
 
-static int samldb_delete_record(struct ldb_module *module, const char *dn)
+static int samldb_delete_record(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "samldb_delete_record\n");
 	return ldb_next_delete_record(module, dn);
 }
 
-static int samldb_rename_record(struct ldb_module *module, const char *olddn, const char *newdn)
+static int samldb_rename_record(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "samldb_rename_record\n");
 	return ldb_next_rename_record(module, olddn, newdn);
diff --git a/source4/dsdb/samdb/samdb.c b/source4/dsdb/samdb/samdb.c
index 3a160615ff..9cb9a93446 100644
--- a/source4/dsdb/samdb/samdb.c
+++ b/source4/dsdb/samdb/samdb.c
@@ -43,7 +43,7 @@ struct ldb_context *samdb_connect(TALLOC_CTX *mem_ctx)
 */
 int samdb_search_domain(struct ldb_context *sam_ldb,
 			TALLOC_CTX *mem_ctx, 
-			const char *basedn,
+			const struct ldb_dn *basedn,
 			struct ldb_message ***res,
 			const char * const *attrs,
 			const struct dom_sid *domain_sid,
@@ -84,7 +84,7 @@ int samdb_search_domain(struct ldb_context *sam_ldb,
 */
 const char *samdb_search_string_v(struct ldb_context *sam_ldb,
 				  TALLOC_CTX *mem_ctx,
-				  const char *basedn,
+				  const struct ldb_dn *basedn,
 				  const char *attr_name,
 				  const char *format, va_list ap) _PRINTF_ATTRIBUTE(5,0)
 {
@@ -113,7 +113,7 @@ const char *samdb_search_string_v(struct ldb_context *sam_ldb,
 */
 const char *samdb_search_string(struct ldb_context *sam_ldb,
 				TALLOC_CTX *mem_ctx,
-				const char *basedn,
+				const struct ldb_dn *basedn,
 				const char *attr_name,
 				const char *format, ...) _PRINTF_ATTRIBUTE(5,6)
 {
@@ -132,7 +132,7 @@ const char *samdb_search_string(struct ldb_context *sam_ldb,
 */
 struct dom_sid *samdb_search_dom_sid(struct ldb_context *sam_ldb,
 				     TALLOC_CTX *mem_ctx,
-				     const char *basedn,
+				     const struct ldb_dn *basedn,
 				     const char *attr_name,
 				     const char *format, ...) _PRINTF_ATTRIBUTE(5,6)
 {
@@ -165,7 +165,7 @@ struct dom_sid *samdb_search_dom_sid(struct ldb_context *sam_ldb,
 */
 int samdb_search_count(struct ldb_context *sam_ldb,
 		       TALLOC_CTX *mem_ctx,
-		       const char *basedn,
+		       const struct ldb_dn *basedn,
 		       const char *format, ...) _PRINTF_ATTRIBUTE(4,5)
 {
 	va_list ap;
@@ -187,7 +187,7 @@ int samdb_search_count(struct ldb_context *sam_ldb,
 uint_t samdb_search_uint(struct ldb_context *sam_ldb,
 			 TALLOC_CTX *mem_ctx,
 			 uint_t default_value,
-			 const char *basedn,
+			 const struct ldb_dn *basedn,
 			 const char *attr_name,
 			 const char *format, ...) _PRINTF_ATTRIBUTE(6,7)
 {
@@ -215,7 +215,7 @@ uint_t samdb_search_uint(struct ldb_context *sam_ldb,
 int64_t samdb_search_int64(struct ldb_context *sam_ldb,
 			   TALLOC_CTX *mem_ctx,
 			   int64_t default_value,
-			   const char *basedn,
+			   const struct ldb_dn *basedn,
 			   const char *attr_name,
 			   const char *format, ...) _PRINTF_ATTRIBUTE(6,7)
 {
@@ -243,7 +243,7 @@ int64_t samdb_search_int64(struct ldb_context *sam_ldb,
 */
 int samdb_search_string_multiple(struct ldb_context *sam_ldb,
 				 TALLOC_CTX *mem_ctx,
-				 const char *basedn,
+				 const struct ldb_dn *basedn,
 				 const char ***strs,
 				 const char *attr_name,
 				 const char *format, ...) _PRINTF_ATTRIBUTE(6,7)
@@ -312,6 +312,14 @@ const char *samdb_result_string(struct ldb_message *msg, const char *attr,
 	return ldb_msg_find_string(msg, attr, default_value);
 }
 
+struct ldb_dn *samdb_result_dn(TALLOC_CTX *mem_ctx, struct ldb_message *msg,
+			       const char *attr, struct ldb_dn *default_value)
+{
+	const char *string = samdb_result_string(msg, attr, NULL);
+	if (string == NULL) return default_value;
+	return ldb_dn_explode(mem_ctx, string);
+}
+
 /*
   pull a rid from a objectSid in a result set. 
 */
@@ -421,7 +429,7 @@ uint64_t samdb_result_uint64(struct ldb_message *msg, const char *attr, uint64_t
 */
 NTTIME samdb_result_allow_password_change(struct ldb_context *sam_ldb, 
 					  TALLOC_CTX *mem_ctx, 
-					  const char *domain_dn, 
+					  const struct ldb_dn *domain_dn, 
 					  struct ldb_message *msg, 
 					  const char *attr)
 {
@@ -433,7 +441,7 @@ NTTIME samdb_result_allow_password_change(struct ldb_context *sam_ldb,
 	}
 
 	minPwdAge = samdb_search_int64(sam_ldb, mem_ctx, 0,
-				       domain_dn, "minPwdAge", "dn=%s", domain_dn);
+				       domain_dn, "minPwdAge", "dn=%s", ldb_dn_linearize(mem_ctx, domain_dn));
 
 	/* yes, this is a -= not a += as minPwdAge is stored as the negative
 	   of the number of 100-nano-seconds */
@@ -448,7 +456,7 @@ NTTIME samdb_result_allow_password_change(struct ldb_context *sam_ldb,
 */
 NTTIME samdb_result_force_password_change(struct ldb_context *sam_ldb, 
 					  TALLOC_CTX *mem_ctx, 
-					  const char *domain_dn, 
+					  const struct ldb_dn *domain_dn, 
 					  struct ldb_message *msg, 
 					  const char *attr)
 {
@@ -460,7 +468,7 @@ NTTIME samdb_result_force_password_change(struct ldb_context *sam_ldb,
 	}
 
 	maxPwdAge = samdb_search_int64(sam_ldb, mem_ctx, 0, domain_dn, 
-				       "maxPwdAge", "dn=%s", domain_dn);
+				       "maxPwdAge", "dn=%s", ldb_dn_linearize(mem_ctx, domain_dn));
 	if (maxPwdAge == 0) {
 		return 0;
 	} else {
@@ -899,7 +907,7 @@ int samdb_add(struct ldb_context *sam_ldb, TALLOC_CTX *mem_ctx, struct ldb_messa
 /*
   delete a record
 */
-int samdb_delete(struct ldb_context *sam_ldb, TALLOC_CTX *mem_ctx, const char *dn)
+int samdb_delete(struct ldb_context *sam_ldb, TALLOC_CTX *mem_ctx, const struct ldb_dn *dn)
 {
 	return ldb_delete(sam_ldb, dn);
 }
diff --git a/source4/include/structs.h b/source4/include/structs.h
index 26c6b9a622..bcecd5c096 100644
--- a/source4/include/structs.h
+++ b/source4/include/structs.h
@@ -197,6 +197,7 @@ struct test_join_ads_dc;
 struct netr_LMSessionKey;
 
 struct ldb_val;
+struct ldb_dn;
 struct ldb_message;
 struct ldb_context;
 struct ldb_parse_tree;
diff --git a/source4/kdc/hdb-ldb.c b/source4/kdc/hdb-ldb.c
index 0aa18423a0..78084f2e89 100644
--- a/source4/kdc/hdb-ldb.c
+++ b/source4/kdc/hdb-ldb.c
@@ -447,7 +447,7 @@ static krb5_error_code LDB_lookup_principal(krb5_context context, struct ldb_con
 					    TALLOC_CTX *mem_ctx,
 					    krb5_const_principal principal,
 					    enum hdb_ldb_ent_type ent_type,
-					    const char *realm_dn,
+					    const struct ldb_dn *realm_dn,
 					    struct ldb_message ***pmsg)
 {
 	krb5_error_code ret;
@@ -460,6 +460,8 @@ static krb5_error_code LDB_lookup_principal(krb5_context context, struct ldb_con
 	char *princ_str_talloc;
 	char *short_princ;
 
+	char *realm_dn_str;
+
 	struct ldb_message **msg = NULL;
 
 	/* Structure assignment, so we don't mess with the source parameter */
@@ -520,18 +522,20 @@ static krb5_error_code LDB_lookup_principal(krb5_context context, struct ldb_con
 	count = ldb_search(ldb_ctx, realm_dn, LDB_SCOPE_SUBTREE, filter, 
 			   princ_attrs, &msg);
 
+	realm_dn_str = ldb_dn_linearize(mem_ctx, realm_dn);
+
 	if (count < 1) {
 		krb5_warnx(context, "ldb_search: basedn: '%s' filter: '%s' failed: %d", 
-			   realm_dn, filter, count);
+			   realm_dn_str, filter, count);
 		krb5_set_error_string(context, "ldb_search: basedn: '%s' filter: '%s' failed: %d", 
-				      realm_dn, filter, count);
+				      realm_dn_str, filter, count);
 		return HDB_ERR_NOENTRY;
 	} else if (count > 1) {
 		talloc_free(msg);
 		krb5_warnx(context, "ldb_search: basedn: '%s' filter: '%s' more than 1 entry: %d", 
-			   realm_dn, filter, count);
+			   realm_dn_str, filter, count);
 		krb5_set_error_string(context, "ldb_search: basedn: '%s' filter: '%s' more than 1 entry: %d", 
-				      realm_dn, filter, count);
+				      realm_dn_str, filter, count);
 		return HDB_ERR_NOENTRY;
 	}
 	*pmsg = talloc_steal(mem_ctx, msg);
@@ -544,7 +548,8 @@ static krb5_error_code LDB_lookup_realm(krb5_context context, struct ldb_context
 					struct ldb_message ***pmsg)
 {
 	int count;
-	const char *realm_dn;
+	struct ldb_dn *realm_dn;
+	const char *realm_dn_str;
 	char *cross_ref_filter;
 	struct ldb_message **cross_ref_msg;
 	struct ldb_message **msg;
@@ -585,7 +590,8 @@ static krb5_error_code LDB_lookup_realm(krb5_context context, struct ldb_context
 		return HDB_ERR_NOENTRY;
 	}
 
-	realm_dn = ldb_msg_find_string(cross_ref_msg[0], "nCName", NULL);
+	realm_dn_str = ldb_msg_find_string(cross_ref_msg[0], "nCName", NULL);
+	realm_dn = ldb_dn_explode(mem_ctx, realm_dn_str);
 
 	count = ldb_search(ldb_ctx, realm_dn, LDB_SCOPE_BASE, "(objectClass=domain)",
 			   realm_attrs, &msg);
@@ -596,12 +602,12 @@ static krb5_error_code LDB_lookup_realm(krb5_context context, struct ldb_context
 	}
 
 	if (count < 1) {
-		krb5_warnx(context, "ldb_search: dn: %s not found: %d", realm_dn, count);
-		krb5_set_error_string(context, "ldb_search: dn: %s not found: %d", realm_dn, count);
+		krb5_warnx(context, "ldb_search: dn: %s not found: %d", realm_dn_str, count);
+		krb5_set_error_string(context, "ldb_search: dn: %s not found: %d", realm_dn_str, count);
 		return HDB_ERR_NOENTRY;
 	} else if (count > 1) {
-		krb5_warnx(context, "ldb_search: dn: '%s' more than 1 entry: %d", realm_dn, count);
-		krb5_set_error_string(context, "ldb_search: dn: %s more than 1 entry: %d", realm_dn, count);
+		krb5_warnx(context, "ldb_search: dn: '%s' more than 1 entry: %d", realm_dn_str, count);
+		krb5_set_error_string(context, "ldb_search: dn: %s more than 1 entry: %d", realm_dn_str, count);
 		return HDB_ERR_NOENTRY;
 	}
 
@@ -610,7 +616,7 @@ static krb5_error_code LDB_lookup_realm(krb5_context context, struct ldb_context
 
 static krb5_error_code LDB_lookup_spn_alias(krb5_context context, struct ldb_context *ldb_ctx, 
 					    TALLOC_CTX *mem_ctx,
-					    const char *realm_dn,
+					    const struct ldb_dn *realm_dn,
 					    const char *alias_from,
 					    char **alias_to)
 {
@@ -618,9 +624,11 @@ static krb5_error_code LDB_lookup_spn_alias(krb5_context context, struct ldb_con
 	int count;
 	struct ldb_message **msg;
 	struct ldb_message_element *spnmappings;
-	char *service_dn = talloc_asprintf(mem_ctx, 
-					   "CN=Directory Service,CN=Windows NT,CN=Services,CN=Configuration,%s", 
-					   realm_dn);
+	struct ldb_dn *service_dn = ldb_dn_compose_string_dn(mem_ctx,
+						"CN=Directory Service,CN=Windows NT"
+						",CN=Services,CN=Configuration", 
+						realm_dn);
+	char *service_dn_str = ldb_dn_linearize(mem_ctx, service_dn);
 	const char *directory_attrs[] = {
 		"sPNMappings", 
 		NULL
@@ -631,19 +639,19 @@ static krb5_error_code LDB_lookup_spn_alias(krb5_context context, struct ldb_con
 	talloc_steal(mem_ctx, msg);
 
 	if (count < 1) {
-		krb5_warnx(context, "ldb_search: dn: %s not found: %d", service_dn, count);
-		krb5_set_error_string(context, "ldb_search: dn: %s not found: %d", service_dn, count);
+		krb5_warnx(context, "ldb_search: dn: %s not found: %d", service_dn_str, count);
+		krb5_set_error_string(context, "ldb_search: dn: %s not found: %d", service_dn_str, count);
 		return HDB_ERR_NOENTRY;
 	} else if (count > 1) {
-		krb5_warnx(context, "ldb_search: dn: %s found %d times!", service_dn, count);
-		krb5_set_error_string(context, "ldb_search: dn: %s found %d times!", service_dn, count);
+		krb5_warnx(context, "ldb_search: dn: %s found %d times!", service_dn_str, count);
+		krb5_set_error_string(context, "ldb_search: dn: %s found %d times!", service_dn_str, count);
 		return HDB_ERR_NOENTRY;
 	}
 	
 	spnmappings = ldb_msg_find_element(msg[0], "sPNMappings");
 	if (!spnmappings || spnmappings->num_values == 0) {
-		krb5_warnx(context, "ldb_search: dn: %s no sPNMappings attribute", service_dn);
-		krb5_set_error_string(context, "ldb_search: dn: %s no sPNMappings attribute", service_dn);
+		krb5_warnx(context, "ldb_search: dn: %s no sPNMappings attribute", service_dn_str);
+		krb5_set_error_string(context, "ldb_search: dn: %s no sPNMappings attribute", service_dn_str);
 		return HDB_ERR_NOENTRY;
 	}
 
@@ -652,8 +660,8 @@ static krb5_error_code LDB_lookup_spn_alias(krb5_context context, struct ldb_con
 		mapping = talloc_strdup(mem_ctx, 
 					(const char *)spnmappings->values[i].data);
 		if (!mapping) {
-			krb5_warnx(context, "LDB_lookup_spn_alias: ldb_search: dn: %s did not have an sPNMapping", service_dn);
-			krb5_set_error_string(context, "LDB_lookup_spn_alias: ldb_search: dn: %s did not have an sPNMapping", service_dn);
+			krb5_warnx(context, "LDB_lookup_spn_alias: ldb_search: dn: %s did not have an sPNMapping", service_dn_str);
+			krb5_set_error_string(context, "LDB_lookup_spn_alias: ldb_search: dn: %s did not have an sPNMapping", service_dn_str);
 			return HDB_ERR_NOENTRY;
 		}
 		
@@ -662,9 +670,9 @@ static krb5_error_code LDB_lookup_spn_alias(krb5_context context, struct ldb_con
 		p = strchr(mapping, '=');
 		if (!p) {
 			krb5_warnx(context, "ldb_search: dn: %s sPNMapping malformed: %s", 
-				   service_dn, mapping);
+				   service_dn_str, mapping);
 			krb5_set_error_string(context, "ldb_search: dn: %s sPNMapping malformed: %s", 
-					      service_dn, mapping);
+					      service_dn_str, mapping);
 			return HDB_ERR_NOENTRY;
 		}
 		p[0] = '\0';
@@ -729,7 +737,7 @@ static krb5_error_code LDB_fetch(krb5_context context, HDB *db, unsigned flags,
 	krb5_error_code ret;
 
 	const char *realm;
-	const char *realm_dn;
+	const struct ldb_dn *realm_dn;
 	TALLOC_CTX *mem_ctx = talloc_named(NULL, 0, "LDB_fetch context");
 
 	if (!mem_ctx) {
@@ -927,7 +935,7 @@ static krb5_error_code LDB_firstkey(krb5_context context, HDB *db, unsigned flag
 	struct ldb_context *ldb_ctx = (struct ldb_context *)db->hdb_db;
 	struct hdb_ldb_seq *priv = (struct hdb_ldb_seq *)db->hdb_openp;
 	char *realm;
-	char *realm_dn = NULL;
+	struct ldb_dn *realm_dn = NULL;
 	struct ldb_message **msgs = NULL;
 	struct ldb_message **realm_msgs = NULL;
 	krb5_error_code ret;
diff --git a/source4/ldap_server/config.mk b/source4/ldap_server/config.mk
index 2d99de8081..3d39b397bd 100644
--- a/source4/ldap_server/config.mk
+++ b/source4/ldap_server/config.mk
@@ -8,7 +8,6 @@ INIT_OBJ_FILES = \
 		ldap_server/ldap_backend.o \
 		ldap_server/ldap_bind.o \
 		ldap_server/ldap_rootdse.o \
-		ldap_server/ldap_parse.o \
 		ldap_server/ldap_simple_ldb.o \
 		ldap_server/ldap_hacked_ldb.o
 REQUIRED_SUBSYSTEMS = \
diff --git a/source4/ldap_server/ldap_hacked_ldb.c b/source4/ldap_server/ldap_hacked_ldb.c
index 6ff97eb1d0..24e2163e48 100644
--- a/source4/ldap_server/ldap_hacked_ldb.c
+++ b/source4/ldap_server/ldap_hacked_ldb.c
@@ -24,7 +24,6 @@
 #include "includes.h"
 #include "dynconfig.h"
 #include "ldap_server/ldap_server.h"
-#include "ldap_parse.h"
 #include "lib/ldb/include/ldb.h"
 #include "librpc/gen_ndr/ndr_security.h"
 #include "librpc/gen_ndr/ndr_misc.h"
@@ -131,12 +130,12 @@ DEBUG(0, (__location__": convert_values(ncname): nc dn = '%s'\n", nc_filter));
 
 		
 		/* first the NC stuff */
-		count = ldb_search(samdb, "", LDB_SCOPE_BASE, nc_filter, s_attrs, &res);
+		count = ldb_search(samdb, NULL, LDB_SCOPE_BASE, nc_filter, s_attrs, &res);
 		if (count != 1) {
 			DEBUG(0, (__location__": convert_values(ncname): nc_count: %d \n", count));
 			return NT_STATUS_FOOBAR;
 		}
-DEBUG(0, (__location__": convert_values(ncname): nc_res '%s'\n", res[0]->dn));
+DEBUG(0, (__location__": convert_values(ncname): nc_res '%s'\n", ldb_dn_linearize(mem_ctx, res[0]->dn)));
 		nc_guid_str = samdb_result_string(res[0], "objectGUID", NULL);
 
 		status = GUID_from_string(nc_guid_str, &nc_guid);
@@ -159,7 +158,7 @@ DEBUG(0, (__location__": convert_values(ncname): dn='%s'\n",*dn));
 
 		dom_filter = talloc_asprintf(mem_ctx, "(dn=%s)", dom_dn);
 DEBUG(0, (__location__": convert_values(ncname): dom dn = '%s'\n", dom_filter));
-		count = ldb_search(samdb, "", LDB_SCOPE_BASE, dom_filter, s_attrs, &res);
+		count = ldb_search(samdb, NULL, LDB_SCOPE_BASE, dom_filter, s_attrs, &res);
 		if (count != 1) {
 			DEBUG(0, (__location__": convert_values(ncname): dom_count: %d \n", count));
 			return NT_STATUS_OK;
@@ -292,18 +291,12 @@ static NTSTATUS hacked_Search(struct ldapsrv_partition *partition, struct ldapsr
 	int count, j, y, i;
 	const char **attrs = NULL;
 	enum ldb_scope scope = LDB_SCOPE_DEFAULT;
-	struct ldap_dn *basedn;
-	const char *basedn_str;
+	struct ldb_dn *basedn;
 
 	local_ctx = talloc_named(call, 0, "hacked_Search local memory context");
 	NT_STATUS_HAVE_NO_MEMORY(local_ctx);
 
-	basedn = ldap_parse_dn(local_ctx, r->basedn);
-	if (!basedn) {
-		basedn_str = r->basedn;
-	} else {
-		basedn_str = basedn->dn;
-	}
+	basedn = ldb_dn_explode(local_ctx, r->basedn);
 
 	switch (r->scope) {
 		case LDAP_SEARCH_SCOPE_BASE:
@@ -330,9 +323,9 @@ static NTSTATUS hacked_Search(struct ldapsrv_partition *partition, struct ldapsr
 		}
 		attrs[j] = NULL;
 	}
-DEBUG(0,("hacked basedn: %s\n", basedn_str));
+DEBUG(0,("hacked basedn: %s\n", ldb_dn_linearize(local_ctx, basedn)));
 DEBUGADD(0,("hacked filter: %s\n", ldb_filter_from_tree(r, r->tree)));
-	count = ldb_search_bytree(samdb, basedn_str, scope, r->tree, attrs, &res);
+	count = ldb_search_bytree(samdb, basedn, scope, r->tree, attrs, &res);
 	talloc_steal(samdb, res);
 
 	if (count < 1) {
@@ -345,7 +338,7 @@ DEBUGADD(0,("hacked filter: %s\n", ldb_filter_from_tree(r, r->tree)));
 		NT_STATUS_HAVE_NO_MEMORY(ent_r);
 
 		ent = &ent_r->msg->r.SearchResultEntry;
-		ent->dn = talloc_steal(ent_r, res[0]->dn);
+		ent->dn = ldb_dn_linearize(ent_r, res[0]->dn);
 		DEBUG(0,("hacked result [0] dn: %s\n", ent->dn));
 		ent->num_attributes = 0;
 		ent->attributes = NULL;
@@ -390,7 +383,7 @@ queue_reply:
 			NT_STATUS_HAVE_NO_MEMORY(ent_r);
 
 			ent = &ent_r->msg->r.SearchResultEntry;
-			ent->dn = talloc_steal(ent_r, res[i]->dn);
+			ent->dn = ldb_dn_linearize(ent_r, res[i]->dn);
 			DEBUG(0,("hacked result [%d] dn: %s\n", i, ent->dn));
 			ent->num_attributes = 0;
 			ent->attributes = NULL;
@@ -606,7 +599,7 @@ static NTSTATUS hldb_Add(struct ldapsrv_partition *partition, struct ldapsrv_cal
 				     struct ldap_AddRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *dn;
+	struct ldb_dn *dn;
 	struct ldap_Result *add_result;
 	struct ldapsrv_reply *add_reply;
 	int ldb_ret;
@@ -622,15 +615,14 @@ static NTSTATUS hldb_Add(struct ldapsrv_partition *partition, struct ldapsrv_cal
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	dn = ldap_parse_dn(local_ctx, r->dn);
-	VALID_DN_SYNTAX(dn,1);
-
-	DEBUG(10, ("hldb_add: dn: [%s]\n", dn->dn));
-
 	msg = talloc(local_ctx, struct ldb_message);
 	NT_STATUS_HAVE_NO_MEMORY(msg);
 
-	msg->dn = dn->dn;
+	msg->dn = ldb_dn_explode(local_ctx, r->dn);
+	VALID_DN_SYNTAX(dn, 1);
+
+	DEBUG(10, ("hldb_add: dn: [%s]\n", ldb_dn_linearize(local_ctx, dn)));
+
 	msg->private_data = NULL;
 	msg->num_elements = 0;
 	msg->elements = NULL;
@@ -679,7 +671,7 @@ reply:
 	if (result == LDAP_SUCCESS) {
 		ldb_ret = ldb_add(samdb, msg);
 		if (ldb_ret == 0) {
-			DEBUG(0,("hldb_Add: added: '%s'\n", msg->dn));
+			DEBUG(0,("hldb_Add: added: '%s'\n", ldb_dn_linearize(msg, msg->dn)));
 			result = LDAP_SUCCESS;
 			errstr = NULL;
 		} else {
@@ -707,7 +699,7 @@ static NTSTATUS hldb_Del(struct ldapsrv_partition *partition, struct ldapsrv_cal
 				     struct ldap_DelRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *dn;
+	struct ldb_dn *dn;
 	struct ldap_Result *del_result;
 	struct ldapsrv_reply *del_reply;
 	int ldb_ret;
@@ -721,17 +713,17 @@ static NTSTATUS hldb_Del(struct ldapsrv_partition *partition, struct ldapsrv_cal
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	dn = ldap_parse_dn(local_ctx, r->dn);
+	dn = ldb_dn_explode(local_ctx, r->dn);
 	VALID_DN_SYNTAX(dn,1);
 
-	DEBUG(10, ("hldb_Del: dn: [%s]\n", dn->dn));
+	DEBUG(10, ("hldb_Del: dn: [%s]\n", ldb_dn_linearize(local_ctx, dn)));
 
 reply:
 	del_reply = ldapsrv_init_reply(call, LDAP_TAG_DelResponse);
 	NT_STATUS_HAVE_NO_MEMORY(del_reply);
 
 	if (result == LDAP_SUCCESS) {
-		ldb_ret = ldb_delete(samdb, dn->dn);
+		ldb_ret = ldb_delete(samdb, dn);
 		if (ldb_ret == 0) {
 			result = LDAP_SUCCESS;
 			errstr = NULL;
@@ -760,7 +752,7 @@ static NTSTATUS hldb_Modify(struct ldapsrv_partition *partition, struct ldapsrv_
 				     struct ldap_ModifyRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *dn;
+	struct ldb_dn *dn;
 	struct ldap_Result *modify_result;
 	struct ldapsrv_reply *modify_reply;
 	int ldb_ret;
@@ -776,15 +768,14 @@ static NTSTATUS hldb_Modify(struct ldapsrv_partition *partition, struct ldapsrv_
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	dn = ldap_parse_dn(local_ctx, r->dn);
-	VALID_DN_SYNTAX(dn,1);
-
-	DEBUG(10, ("hldb_modify: dn: [%s]\n", dn->dn));
-
 	msg = talloc(local_ctx, struct ldb_message);
 	NT_STATUS_HAVE_NO_MEMORY(msg);
 
-	msg->dn = dn->dn;
+	msg->dn = ldb_dn_explode(local_ctx, r->dn);
+	VALID_DN_SYNTAX(dn,1);
+
+	DEBUG(10, ("hldb_modify: dn: [%s]\n", ldb_dn_linearize(local_ctx, dn)));
+
 	msg->private_data = NULL;
 	msg->num_elements = 0;
 	msg->elements = NULL;
@@ -856,7 +847,7 @@ reply:
 			if (strcmp("Type or value exists", errstr) ==0){
 				result = LDAP_ATTRIBUTE_OR_VALUE_EXISTS;
 			}
-			DEBUG(0,("failed to modify: %s - %u - %s\n", msg->dn, result, errstr));
+			DEBUG(0,("failed to modify: %s - %u - %s\n", ldb_dn_linearize(local_ctx, msg->dn), result, errstr));
 		}
 	}
 
@@ -876,7 +867,7 @@ static NTSTATUS hldb_Compare(struct ldapsrv_partition *partition, struct ldapsrv
 				     struct ldap_CompareRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *dn;
+	struct ldb_dn *dn;
 	struct ldap_Result *compare;
 	struct ldapsrv_reply *compare_r;
 	int result = LDAP_SUCCESS;
@@ -893,10 +884,10 @@ static NTSTATUS hldb_Compare(struct ldapsrv_partition *partition, struct ldapsrv
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	dn = ldap_parse_dn(local_ctx, r->dn);
+	dn = ldb_dn_explode(local_ctx, r->dn);
 	VALID_DN_SYNTAX(dn,1);
 
-	DEBUG(10, ("hldb_Compare: dn: [%s]\n", dn->dn));
+	DEBUG(10, ("hldb_Compare: dn: [%s]\n", ldb_dn_linearize(local_ctx, dn)));
 	filter = talloc_asprintf(local_ctx, "(%s=%*s)", r->attribute, 
 				 (int)r->value.length, r->value.data);
 	NT_STATUS_HAVE_NO_MEMORY(filter);
@@ -910,7 +901,7 @@ reply:
 	NT_STATUS_HAVE_NO_MEMORY(compare_r);
 
 	if (result == LDAP_SUCCESS) {
-		count = ldb_search(samdb, dn->dn, LDB_SCOPE_BASE, filter, attrs, &res);
+		count = ldb_search(samdb, dn, LDB_SCOPE_BASE, filter, attrs, &res);
 		talloc_steal(samdb, res);
 		if (count == 1) {
 			DEBUG(10,("hldb_Compare: matched\n"));
@@ -946,15 +937,15 @@ reply:
 static NTSTATUS hldb_ModifyDN(struct ldapsrv_partition *partition, struct ldapsrv_call *call, struct ldap_ModifyDNRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *olddn, *newrdn, *newsuperior;
+	struct ldb_dn *olddn, *newrdn, *newsuperior;
 	struct ldap_Result *modifydn;
 	struct ldapsrv_reply *modifydn_r;
 	int ldb_ret;
 	struct ldb_context *samdb;
 	const char *errstr = NULL;
 	int result = LDAP_SUCCESS;
-	const char *newdn = NULL;
-	char *parentdn = NULL;
+	const struct ldb_dn *newdn = NULL;
+	struct ldb_dn *parentdn = NULL;
 
 	local_ctx = talloc_named(call, 0, "hldb_ModifyDN local memory context");
 	NT_STATUS_HAVE_NO_MEMORY(local_ctx);
@@ -962,14 +953,14 @@ static NTSTATUS hldb_ModifyDN(struct ldapsrv_partition *partition, struct ldapsr
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	olddn = ldap_parse_dn(local_ctx, r->dn);
+	olddn = ldb_dn_explode(local_ctx, r->dn);
 	VALID_DN_SYNTAX(olddn,2);
 
-	newrdn = ldap_parse_dn(local_ctx, r->newrdn);
+	newrdn = ldb_dn_explode(local_ctx, r->newrdn);
 	VALID_DN_SYNTAX(newrdn,1);
 
-	DEBUG(10, ("hldb_ModifyDN: olddn: [%s]\n", olddn->dn));
-	DEBUG(10, ("hldb_ModifyDN: newrdn: [%s]\n", newrdn->dn));
+	DEBUG(10, ("hldb_ModifyDN: olddn: [%s]\n", ldb_dn_linearize(local_ctx, olddn)));
+	DEBUG(10, ("hldb_ModifyDN: newrdn: [%s]\n", ldb_dn_linearize(local_ctx, newrdn)));
 
 	/* we can't handle the rename if we should not remove the old dn */
 	if (!r->deleteolddn) {
@@ -985,30 +976,22 @@ static NTSTATUS hldb_ModifyDN(struct ldapsrv_partition *partition, struct ldapsr
 	}
 
 	if (r->newsuperior) {
-		newsuperior = ldap_parse_dn(local_ctx, r->newsuperior);
+		newsuperior = ldb_dn_explode(local_ctx, r->newsuperior);
 		VALID_DN_SYNTAX(newsuperior,0);
-		DEBUG(10, ("hldb_ModifyDN: newsuperior: [%s]\n", newsuperior->dn));
+		DEBUG(10, ("hldb_ModifyDN: newsuperior: [%s]\n", ldb_dn_linearize(local_ctx, newsuperior)));
 		
 		if (newsuperior->comp_num < 1) {
 			result = LDAP_AFFECTS_MULTIPLE_DSAS;
 			errstr = "Error new Superior DN invalid";
 			goto reply;
 		}
-		parentdn = newsuperior->dn;
+		parentdn = newsuperior;
 	}
 
 	if (!parentdn) {
-		int i;
-		parentdn = talloc_strdup(local_ctx, olddn->components[1]->component);
-		NT_STATUS_HAVE_NO_MEMORY(parentdn);
-		for(i=2; i < olddn->comp_num; i++) {
-			char *old = parentdn;
-			parentdn = talloc_asprintf(local_ctx, "%s,%s", old, olddn->components[i]->component);
-			NT_STATUS_HAVE_NO_MEMORY(parentdn);
-			talloc_free(old);
-		}
+		parentdn = ldb_dn_get_parent(local_ctx, olddn);
 	}
-	newdn = talloc_asprintf(local_ctx, "%s,%s", newrdn->dn, parentdn);
+	newdn = ldb_dn_make_child(local_ctx, ldb_dn_get_rdn(local_ctx, newrdn), parentdn);
 	NT_STATUS_HAVE_NO_MEMORY(newdn);
 
 reply:
@@ -1016,7 +999,7 @@ reply:
 	NT_STATUS_HAVE_NO_MEMORY(modifydn_r);
 
 	if (result == LDAP_SUCCESS) {
-		ldb_ret = ldb_rename(samdb, olddn->dn, newdn);
+		ldb_ret = ldb_rename(samdb, olddn, newdn);
 		if (ldb_ret == 0) {
 			result = LDAP_SUCCESS;
 			errstr = NULL;
diff --git a/source4/ldap_server/ldap_simple_ldb.c b/source4/ldap_server/ldap_simple_ldb.c
index 7a8f664898..fbeec2f3ca 100644
--- a/source4/ldap_server/ldap_simple_ldb.c
+++ b/source4/ldap_server/ldap_simple_ldb.c
@@ -21,7 +21,6 @@
 
 #include "includes.h"
 #include "ldap_server/ldap_server.h"
-#include "ldap_parse.h"
 #include "lib/ldb/include/ldb.h"
 #include "db_wrap.h"
 
@@ -39,7 +38,7 @@ static NTSTATUS sldb_Search(struct ldapsrv_partition *partition, struct ldapsrv_
 				     struct ldap_SearchRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *basedn;
+	struct ldb_dn *basedn;
 	struct ldap_Result *done;
 	struct ldap_SearchResEntry *ent;
 	struct ldapsrv_reply *ent_r, *done_r;
@@ -58,17 +57,17 @@ static NTSTATUS sldb_Search(struct ldapsrv_partition *partition, struct ldapsrv_
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	basedn = ldap_parse_dn(local_ctx, r->basedn);
-	VALID_DN_SYNTAX(basedn,0);
+	basedn = ldb_dn_explode(local_ctx, r->basedn);
+	VALID_DN_SYNTAX(basedn, 0);
 
-	DEBUG(10, ("sldb_Search: basedn: [%s]\n", basedn->dn));
+	DEBUG(10, ("sldb_Search: basedn: [%s]\n", r->basedn));
 	DEBUG(10, ("sldb_Search: filter: [%s]\n", ldb_filter_from_tree(call, r->tree)));
 
 	switch (r->scope) {
 		case LDAP_SEARCH_SCOPE_BASE:
 			DEBUG(10,("sldb_Search: scope: [BASE]\n"));
 			scope = LDB_SCOPE_BASE;
-			success_limit = 1;
+			success_limit = 0;
 			break;
 		case LDAP_SEARCH_SCOPE_SINGLE:
 			DEBUG(10,("sldb_Search: scope: [ONE]\n"));
@@ -94,9 +93,9 @@ static NTSTATUS sldb_Search(struct ldapsrv_partition *partition, struct ldapsrv_
 	}
 
 	DEBUG(5,("ldb_search_bytree dn=%s filter=%s\n", 
-		 basedn->dn, ldb_filter_from_tree(call, r->tree)));
+		 r->basedn, ldb_filter_from_tree(call, r->tree)));
 
-	count = ldb_search_bytree(samdb, basedn->dn, scope, r->tree, attrs, &res);
+	count = ldb_search_bytree(samdb, basedn, scope, r->tree, attrs, &res);
 	talloc_steal(samdb, res);
 
 	for (i=0; i < count; i++) {
@@ -104,7 +103,7 @@ static NTSTATUS sldb_Search(struct ldapsrv_partition *partition, struct ldapsrv_
 		NT_STATUS_HAVE_NO_MEMORY(ent_r);
 
 		ent = &ent_r->msg->r.SearchResultEntry;
-		ent->dn = talloc_steal(ent_r, res[i]->dn);
+		ent->dn = ldb_dn_linearize(ent_r, res[i]->dn);
 		ent->num_attributes = 0;
 		ent->attributes = NULL;
 		if (res[i]->num_elements == 0) {
@@ -170,7 +169,7 @@ static NTSTATUS sldb_Add(struct ldapsrv_partition *partition, struct ldapsrv_cal
 				     struct ldap_AddRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *dn;
+	struct ldb_dn *dn;
 	struct ldap_Result *add_result;
 	struct ldapsrv_reply *add_reply;
 	int ldb_ret;
@@ -186,15 +185,15 @@ static NTSTATUS sldb_Add(struct ldapsrv_partition *partition, struct ldapsrv_cal
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	dn = ldap_parse_dn(local_ctx, r->dn);
+	dn = ldb_dn_explode(local_ctx, r->dn);
 	VALID_DN_SYNTAX(dn,1);
 
-	DEBUG(10, ("sldb_add: dn: [%s]\n", dn->dn));
+	DEBUG(10, ("sldb_add: dn: [%s]\n", r->dn));
 
 	msg = talloc(local_ctx, struct ldb_message);
 	NT_STATUS_HAVE_NO_MEMORY(msg);
 
-	msg->dn = dn->dn;
+	msg->dn = dn;
 	msg->private_data = NULL;
 	msg->num_elements = 0;
 	msg->elements = NULL;
@@ -270,7 +269,7 @@ static NTSTATUS sldb_Del(struct ldapsrv_partition *partition, struct ldapsrv_cal
 				     struct ldap_DelRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *dn;
+	struct ldb_dn *dn;
 	struct ldap_Result *del_result;
 	struct ldapsrv_reply *del_reply;
 	int ldb_ret;
@@ -284,17 +283,17 @@ static NTSTATUS sldb_Del(struct ldapsrv_partition *partition, struct ldapsrv_cal
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	dn = ldap_parse_dn(local_ctx, r->dn);
+	dn = ldb_dn_explode(local_ctx, r->dn);
 	VALID_DN_SYNTAX(dn,1);
 
-	DEBUG(10, ("sldb_Del: dn: [%s]\n", dn->dn));
+	DEBUG(10, ("sldb_Del: dn: [%s]\n", r->dn));
 
 reply:
 	del_reply = ldapsrv_init_reply(call, LDAP_TAG_DelResponse);
 	NT_STATUS_HAVE_NO_MEMORY(del_reply);
 
 	if (result == LDAP_SUCCESS) {
-		ldb_ret = ldb_delete(samdb, dn->dn);
+		ldb_ret = ldb_delete(samdb, dn);
 		if (ldb_ret == 0) {
 			result = LDAP_SUCCESS;
 			errstr = NULL;
@@ -323,7 +322,7 @@ static NTSTATUS sldb_Modify(struct ldapsrv_partition *partition, struct ldapsrv_
 				     struct ldap_ModifyRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *dn;
+	struct ldb_dn *dn;
 	struct ldap_Result *modify_result;
 	struct ldapsrv_reply *modify_reply;
 	int ldb_ret;
@@ -339,15 +338,15 @@ static NTSTATUS sldb_Modify(struct ldapsrv_partition *partition, struct ldapsrv_
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	dn = ldap_parse_dn(local_ctx, r->dn);
-	VALID_DN_SYNTAX(dn,1);
+	dn = ldb_dn_explode(local_ctx, r->dn);
+	VALID_DN_SYNTAX(dn, 1);
 
-	DEBUG(10, ("sldb_modify: dn: [%s]\n", dn->dn));
+	DEBUG(10, ("sldb_modify: dn: [%s]\n", r->dn));
 
 	msg = talloc(local_ctx, struct ldb_message);
 	NT_STATUS_HAVE_NO_MEMORY(msg);
 
-	msg->dn = dn->dn;
+	msg->dn = dn;
 	msg->private_data = NULL;
 	msg->num_elements = 0;
 	msg->elements = NULL;
@@ -434,7 +433,7 @@ static NTSTATUS sldb_Compare(struct ldapsrv_partition *partition, struct ldapsrv
 				     struct ldap_CompareRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *dn;
+	struct ldb_dn *dn;
 	struct ldap_Result *compare;
 	struct ldapsrv_reply *compare_r;
 	int result = LDAP_SUCCESS;
@@ -451,10 +450,10 @@ static NTSTATUS sldb_Compare(struct ldapsrv_partition *partition, struct ldapsrv
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	dn = ldap_parse_dn(local_ctx, r->dn);
-	VALID_DN_SYNTAX(dn,1);
+	dn = ldb_dn_explode(local_ctx, r->dn);
+	VALID_DN_SYNTAX(dn, 1);
 
-	DEBUG(10, ("sldb_Compare: dn: [%s]\n", dn->dn));
+	DEBUG(10, ("sldb_Compare: dn: [%s]\n", r->dn));
 	filter = talloc_asprintf(local_ctx, "(%s=%*s)", r->attribute, 
 				 (int)r->value.length, r->value.data);
 	NT_STATUS_HAVE_NO_MEMORY(filter);
@@ -468,7 +467,7 @@ reply:
 	NT_STATUS_HAVE_NO_MEMORY(compare_r);
 
 	if (result == LDAP_SUCCESS) {
-		count = ldb_search(samdb, dn->dn, LDB_SCOPE_BASE, filter, attrs, &res);
+		count = ldb_search(samdb, dn, LDB_SCOPE_BASE, filter, attrs, &res);
 		talloc_steal(samdb, res);
 		if (count == 1) {
 			DEBUG(10,("sldb_Compare: matched\n"));
@@ -504,15 +503,14 @@ reply:
 static NTSTATUS sldb_ModifyDN(struct ldapsrv_partition *partition, struct ldapsrv_call *call, struct ldap_ModifyDNRequest *r)
 {
 	void *local_ctx;
-	struct ldap_dn *olddn, *newrdn, *newsuperior;
+	struct ldb_dn *olddn, *newdn, *newrdn;
+	struct ldb_dn *parentdn = NULL;
 	struct ldap_Result *modifydn;
 	struct ldapsrv_reply *modifydn_r;
 	int ldb_ret;
 	struct ldb_context *samdb;
 	const char *errstr = NULL;
 	int result = LDAP_SUCCESS;
-	const char *newdn = NULL;
-	char *parentdn = NULL;
 
 	local_ctx = talloc_named(call, 0, "sldb_ModifyDN local memory context");
 	NT_STATUS_HAVE_NO_MEMORY(local_ctx);
@@ -520,14 +518,14 @@ static NTSTATUS sldb_ModifyDN(struct ldapsrv_partition *partition, struct ldapsr
 	samdb = ldapsrv_sam_connect(call);
 	NT_STATUS_HAVE_NO_MEMORY(samdb);
 
-	olddn = ldap_parse_dn(local_ctx, r->dn);
-	VALID_DN_SYNTAX(olddn,2);
+	olddn = ldb_dn_explode(local_ctx, r->dn);
+	VALID_DN_SYNTAX(olddn, 2);
 
-	newrdn = ldap_parse_dn(local_ctx, r->newrdn);
-	VALID_DN_SYNTAX(newrdn,1);
+	newrdn = ldb_dn_explode(local_ctx, r->newrdn);
+	VALID_DN_SYNTAX(newrdn, 1);
 
-	DEBUG(10, ("sldb_ModifyDN: olddn: [%s]\n", olddn->dn));
-	DEBUG(10, ("sldb_ModifyDN: newrdn: [%s]\n", newrdn->dn));
+	DEBUG(10, ("sldb_ModifyDN: olddn: [%s]\n", r->dn));
+	DEBUG(10, ("sldb_ModifyDN: newrdn: [%s]\n", r->newrdn));
 
 	/* we can't handle the rename if we should not remove the old dn */
 	if (!r->deleteolddn) {
@@ -543,30 +541,23 @@ static NTSTATUS sldb_ModifyDN(struct ldapsrv_partition *partition, struct ldapsr
 	}
 
 	if (r->newsuperior) {
-		newsuperior = ldap_parse_dn(local_ctx, r->newsuperior);
-		VALID_DN_SYNTAX(newsuperior,0);
-		DEBUG(10, ("sldb_ModifyDN: newsuperior: [%s]\n", newsuperior->dn));
+		parentdn = ldb_dn_explode(local_ctx, r->newsuperior);
+		VALID_DN_SYNTAX(parentdn, 0);
+		DEBUG(10, ("sldb_ModifyDN: newsuperior: [%s]\n", r->newsuperior));
 		
-		if (newsuperior->comp_num < 1) {
+		if (parentdn->comp_num < 1) {
 			result = LDAP_AFFECTS_MULTIPLE_DSAS;
 			errstr = "Error new Superior DN invalid";
 			goto reply;
 		}
-		parentdn = newsuperior->dn;
 	}
 
 	if (!parentdn) {
-		int i;
-		parentdn = talloc_strdup(local_ctx, olddn->components[1]->component);
+		parentdn = ldb_dn_get_parent(local_ctx, olddn);
 		NT_STATUS_HAVE_NO_MEMORY(parentdn);
-		for(i=2; i < olddn->comp_num; i++) {
-			char *old = parentdn;
-			parentdn = talloc_asprintf(local_ctx, "%s,%s", old, olddn->components[i]->component);
-			NT_STATUS_HAVE_NO_MEMORY(parentdn);
-			talloc_free(old);
-		}
 	}
-	newdn = talloc_asprintf(local_ctx, "%s,%s", newrdn->dn, parentdn);
+
+	newdn = ldb_dn_make_child(local_ctx, ldb_dn_get_rdn(local_ctx, newrdn), parentdn);
 	NT_STATUS_HAVE_NO_MEMORY(newdn);
 
 reply:
@@ -574,7 +565,7 @@ reply:
 	NT_STATUS_HAVE_NO_MEMORY(modifydn_r);
 
 	if (result == LDAP_SUCCESS) {
-		ldb_ret = ldb_rename(samdb, olddn->dn, newdn);
+		ldb_ret = ldb_rename(samdb, olddn, newdn);
 		if (ldb_ret == 0) {
 			result = LDAP_SUCCESS;
 			errstr = NULL;
diff --git a/source4/lib/gendb.c b/source4/lib/gendb.c
index 4bf76a7f64..a5fe7c3bce 100644
--- a/source4/lib/gendb.c
+++ b/source4/lib/gendb.c
@@ -29,7 +29,7 @@
 */
 int gendb_search_v(struct ldb_context *ldb, 
 		   TALLOC_CTX *mem_ctx,
-		   const char *basedn,
+		   const struct ldb_dn *basedn,
 		   struct ldb_message ***res,
 		   const char * const *attrs,
 		   const char *format, 
@@ -55,7 +55,8 @@ int gendb_search_v(struct ldb_context *ldb,
 	if (*res) talloc_steal(mem_ctx, *res);
 
 	DEBUG(4,("gendb_search_v: %s %s -> %d  (%s)\n", 
-		 basedn?basedn:"NULL", expr?expr:"NULL", count,
+		 basedn?ldb_dn_linearize(mem_ctx,basedn):"NULL",
+		 expr?expr:"NULL", count,
 		 count==-1?ldb_errstring(ldb):"OK"));
 
 	free(expr);
@@ -68,7 +69,7 @@ int gendb_search_v(struct ldb_context *ldb,
 */
 int gendb_search(struct ldb_context *ldb,
 		 TALLOC_CTX *mem_ctx, 
-		 const char *basedn,
+		 const struct ldb_dn *basedn,
 		 struct ldb_message ***res,
 		 const char * const *attrs,
 		 const char *format, ...) _PRINTF_ATTRIBUTE(6,7)
@@ -85,11 +86,11 @@ int gendb_search(struct ldb_context *ldb,
 
 int gendb_search_dn(struct ldb_context *ldb,
 		 TALLOC_CTX *mem_ctx, 
-		 const char *dn,
+		 const struct ldb_dn *dn,
 		 struct ldb_message ***res,
 		 const char * const *attrs)
 {
-	return gendb_search(ldb, mem_ctx, dn, res, attrs, "dn=%s", dn);
+	return gendb_search(ldb, mem_ctx, dn, res, attrs, "dn=%s", ldb_dn_linearize(mem_ctx, dn));
 }
 
 /*
diff --git a/source4/lib/ldb/common/ldb.c b/source4/lib/ldb/common/ldb.c
index 3a2eb13297..25e7bee66b 100644
--- a/source4/lib/ldb/common/ldb.c
+++ b/source4/lib/ldb/common/ldb.c
@@ -114,7 +114,7 @@ int ldb_connect(struct ldb_context *ldb, const char *url, unsigned int flags, co
 
 */
 int ldb_search(struct ldb_context *ldb, 
-	       const char *base,
+	       const struct ldb_dn *base,
 	       enum ldb_scope scope,
 	       const char *expression,
 	       const char * const *attrs, struct ldb_message ***res)
@@ -131,7 +131,7 @@ int ldb_search(struct ldb_context *ldb,
 
 */
 int ldb_search_bytree(struct ldb_context *ldb, 
-		      const char *base,
+		      const struct ldb_dn *base,
 		      enum ldb_scope scope,
 		      struct ldb_parse_tree *tree,
 		      const char * const *attrs, struct ldb_message ***res)
@@ -162,7 +162,7 @@ int ldb_modify(struct ldb_context *ldb,
 /*
   delete a record from the database
 */
-int ldb_delete(struct ldb_context *ldb, const char *dn)
+int ldb_delete(struct ldb_context *ldb, const struct ldb_dn *dn)
 {
 	return ldb->modules->ops->delete_record(ldb->modules, dn);
 }
@@ -170,7 +170,7 @@ int ldb_delete(struct ldb_context *ldb, const char *dn)
 /*
   rename a record in the database
 */
-int ldb_rename(struct ldb_context *ldb, const char *olddn, const char *newdn)
+int ldb_rename(struct ldb_context *ldb, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
 	return ldb->modules->ops->rename_record(ldb->modules, olddn, newdn);
 }
diff --git a/source4/lib/ldb/common/ldb_dn.c b/source4/lib/ldb/common/ldb_dn.c
index d13238cc17..dae79fd9e1 100644
--- a/source4/lib/ldb/common/ldb_dn.c
+++ b/source4/lib/ldb/common/ldb_dn.c
@@ -41,8 +41,26 @@
 
 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
 
+#define LDB_SPECIAL "@SPECIAL"
+
+BOOL ldb_dn_is_special(const struct ldb_dn *dn)
+{
+	if (dn == NULL || dn->comp_num != 1) return 0;
+
+	return ! strcmp(dn->components[0].name, LDB_SPECIAL);
+}
+
+BOOL ldb_dn_check_special(const struct ldb_dn *dn, const char *check)
+{
+	if (dn == NULL || dn->comp_num != 1) return 0;
+
+	return ! strcmp(dn->components[0].value.data, check);
+}
+
 static int ldb_dn_is_valid_attribute_name(const char *name)
 {
+	if (name == NULL) return 0;
+
 	while (*name) {
 		if (! isascii(*name)) {
 			return 0;
@@ -165,6 +183,8 @@ static int get_quotes_position(const char *source, int *quote_start, int *quote_
 {
 	const char *p;
 
+	if (source == NULL || quote_start == NULL || quote_end == NULL) return -1;
+
 	p = source;
 
 	/* check if there are quotes surrounding the value */
@@ -197,6 +217,8 @@ static char *seek_to_separator(char *string, const char *separators)
 	char *p;
 	int ret, qs, qe;
 
+	if (string == NULL || separators == NULL) return NULL;
+
 	p = strchr(string, '=');
 	LDB_DN_NULL_FAILED(p);
 
@@ -254,6 +276,11 @@ static struct ldb_dn_component ldb_dn_explode_component(void *mem_ctx, char *raw
 	char *p;
 	int ret, qs, qe;
 
+	if (raw_component == NULL) {
+		dc.name = NULL;
+		return dc;
+	}
+
 	/* find attribute type/value separator */
 	p = strchr(raw_component, '=');
 	LDB_DN_NULL_FAILED(p);
@@ -300,14 +327,10 @@ failed:
 	return dc;
 }
 
-struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn)
+struct ldb_dn *ldb_dn_new(void *mem_ctx)
 {
-	struct ldb_dn *edn; /* the exploded dn */
-	char *pdn, *p;
+	struct ldb_dn *edn;
 
-	pdn = NULL;
-
-	/* Allocate a structure to hold the exploded DN */
 	edn = talloc(mem_ctx, struct ldb_dn);
 	LDB_DN_NULL_FAILED(edn);
 
@@ -315,12 +338,33 @@ struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn)
 	edn->comp_num = 0;
 	edn->components = NULL;
 
+	return edn;
+
+failed:
+	return NULL;
+}
+
+struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn)
+{
+	struct ldb_dn *edn; /* the exploded dn */
+	char *pdn, *p;
+
+	if (dn == NULL) return NULL;
+
+	/* Allocate a structure to hold the exploded DN */
+	edn = ldb_dn_new(mem_ctx);
+
+	/* Empty DNs */
+	if (dn[0] == '\0') {
+		return edn;
+	}
+
 	/* Special DNs case */
 	if (dn[0] == '@') {
 		edn->comp_num = 1;
 		edn->components = talloc(edn, struct ldb_dn_component);
 		if (edn->components == NULL) goto failed;
-		edn->components[0].name = talloc_strdup(edn->components, "@SPECIAL");
+		edn->components[0].name = talloc_strdup(edn->components, LDB_SPECIAL);
 		if (edn->components[0].name == NULL) goto failed;
 		edn->components[0].value.data = talloc_strdup(edn->components, dn);
 		if (edn->components[0].value.data== NULL) goto failed;
@@ -376,8 +420,10 @@ char *ldb_dn_linearize(void *mem_ctx, const struct ldb_dn *edn)
 	char *dn, *value;
 	int i;
 
+	if (edn == NULL) return NULL;
+
 	/* Special DNs */
-	if ((edn->comp_num == 1) && strcmp("@SPECIAL", edn->components[0].name) == 0) {
+	if (ldb_dn_is_special(edn)) {
 		dn = talloc_strdup(mem_ctx, edn->components[0].value.data);
 		return dn;
 	}
@@ -419,6 +465,10 @@ int ldb_dn_compare_base(struct ldb_context *ldb,
 		return (dn->comp_num - base->comp_num);
 	}
 
+	if (base == NULL || base->comp_num == 0) return 0;
+	if (dn == NULL || dn->comp_num == 0) return -1;
+	if (base->comp_num > dn->comp_num) return -1;
+
 	/* if the number of components doesn't match they differ */
 	n0 = base->comp_num - 1;
 	n1 = dn->comp_num - 1;
@@ -450,6 +500,8 @@ int ldb_dn_compare(struct ldb_context *ldb,
 		   const struct ldb_dn *edn0,
 		   const struct ldb_dn *edn1)
 {
+	if (edn0 == NULL || edn1 == NULL) return edn1 - edn0;
+
 	if (edn0->comp_num != edn1->comp_num)
 		return (edn1->comp_num - edn0->comp_num);
 
@@ -462,6 +514,8 @@ int ldb_dn_cmp(struct ldb_context *ldb, const char *dn0, const char *dn1)
 	struct ldb_dn *edn1;
 	int ret;
 
+	if (dn0 == NULL || dn1 == NULL) return dn1 - dn0;
+
 	edn0 = ldb_dn_explode_casefold(ldb, dn0);
 	if (edn0 == NULL) return 0;
 
@@ -488,7 +542,9 @@ struct ldb_dn *ldb_dn_casefold(struct ldb_context *ldb, const struct ldb_dn *edn
 	struct ldb_dn *cedn;
 	int i;
 
-	cedn = talloc(ldb, struct ldb_dn);
+	if (edn == NULL) return NULL;
+
+	cedn = ldb_dn_new(ldb);
 	LDB_DN_NULL_FAILED(cedn);
 
 	cedn->comp_num = edn->comp_num;
@@ -521,6 +577,8 @@ struct ldb_dn *ldb_dn_explode_casefold(struct ldb_context *ldb, const char *dn)
 {
 	struct ldb_dn *edn, *cdn;
 
+	if (dn == NULL) return NULL;
+
 	edn = ldb_dn_explode(ldb, dn);
 	if (edn == NULL) return NULL;
 
@@ -529,3 +587,235 @@ struct ldb_dn *ldb_dn_explode_casefold(struct ldb_context *ldb, const char *dn)
 	talloc_free(edn);
 	return cdn;
 }
+
+char *ldb_dn_linearize_casefold(struct ldb_context *ldb, const struct ldb_dn *edn)
+{
+	struct ldb_dn *cdn;
+	char *dn;
+
+	if (edn == NULL) return NULL;
+
+	/* Special DNs */
+	if (ldb_dn_is_special(edn)) {
+		dn = talloc_strdup(ldb, edn->components[0].value.data);
+		return dn;
+	}
+
+	cdn = ldb_dn_casefold(ldb, edn);
+	if (cdn == NULL) return NULL;
+
+	dn = ldb_dn_linearize(ldb, cdn);
+	if (dn == NULL) {
+		talloc_free(cdn);
+		return NULL;
+	}
+
+	talloc_free(cdn);
+	return dn;
+}
+
+static struct ldb_dn_component ldb_dn_copy_component(void *mem_ctx, struct ldb_dn_component *src)
+{
+	struct ldb_dn_component dst;
+	
+	dst.name = NULL;
+
+	if (src == NULL) {
+		return dst;
+	}
+
+	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;
+}
+
+/* copy specified number of elements of a dn into a new one
+   element are copied from top level up to the unique rdn
+   num_el may be greater then dn->comp_num (see ldb_dn_make_child)
+*/
+struct ldb_dn *ldb_dn_copy_partial(void *mem_ctx, const struct ldb_dn *dn, int num_el)
+{
+	struct ldb_dn *new;
+	int i, n, e;
+
+	if (dn == NULL) return NULL;
+	if (num_el <= 0) return NULL;
+
+	new = ldb_dn_new(mem_ctx);
+	LDB_DN_NULL_FAILED(new);
+
+	new->comp_num = num_el;
+	n = new->comp_num - 1;
+	new->components = talloc_array(new, struct ldb_dn_component, new->comp_num);
+
+	if (dn->comp_num == 0) return new;
+	e = dn->comp_num - 1;
+
+	for (i = 0; i < new->comp_num; i++) {
+		new->components[n - i] = ldb_dn_copy_component(new->components,
+								&(dn->components[e - i]));
+		if ((e - i) == 0) {
+			return new;
+		}
+	}
+
+	return new;
+
+failed:
+	talloc_free(new);
+	return NULL;
+}
+
+struct ldb_dn *ldb_dn_copy(void *mem_ctx, const struct ldb_dn *dn)
+{
+	if (dn == NULL) return NULL;
+	return ldb_dn_copy_partial(mem_ctx, dn, dn->comp_num);
+}
+
+struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, const struct ldb_dn *dn)
+{
+	if (dn == NULL) return NULL;
+	return ldb_dn_copy_partial(mem_ctx, dn, dn->comp_num - 1);
+}
+
+struct ldb_dn_component *ldb_dn_build_component(void *mem_ctx, const char *attr,
+							       const char *val)
+{
+	struct ldb_dn_component *dc;
+
+	if (attr == NULL || val == NULL) return NULL;
+
+	dc = talloc(mem_ctx, struct ldb_dn_component);
+	if (dc == NULL) return NULL;
+
+	dc->name = talloc_strdup(dc, attr);
+	if (dc->name ==  NULL) {
+		talloc_free(dc);
+		return NULL;
+	}
+
+	dc->value.data = talloc_strdup(dc, val);
+	if (dc->value.data ==  NULL) {
+		talloc_free(dc);
+		return NULL;
+	}
+
+	dc->value.length = strlen(val);
+
+	return dc;
+}
+
+struct ldb_dn *ldb_dn_build_child(void *mem_ctx, const char *attr,
+						 const char * value,
+						 const struct ldb_dn *base)
+{
+	struct ldb_dn *new;
+	if (! ldb_dn_is_valid_attribute_name(attr)) return NULL;
+	if (value == NULL || value == '\0') return NULL; 
+
+	if (base != NULL) {
+		new = ldb_dn_copy_partial(mem_ctx, base, base->comp_num + 1);
+		LDB_DN_NULL_FAILED(new);
+	} else {
+		new = ldb_dn_new(mem_ctx);
+		LDB_DN_NULL_FAILED(new);
+
+		new->comp_num = 1;
+		new->components = talloc_array(new, struct ldb_dn_component, new->comp_num);
+	}
+
+	new->components[0].name = talloc_strdup(new->components, attr);
+	LDB_DN_NULL_FAILED(new->components[0].name);
+
+	new->components[0].value.data = talloc_strdup(new->components, value);
+	LDB_DN_NULL_FAILED(new->components[0].value.data);
+	new->components[0].value.length = strlen(new->components[0].value.data);
+
+	return new;
+
+failed:
+	talloc_free(new);
+	return NULL;
+
+}
+
+struct ldb_dn *ldb_dn_make_child(void *mem_ctx, const struct ldb_dn_component *component,
+						const struct ldb_dn *base)
+{
+	if (component == NULL) return NULL;
+
+	return ldb_dn_build_child(mem_ctx, component->name, component->value.data, base);
+}
+
+struct ldb_dn *ldb_dn_compose(void *mem_ctx, const struct ldb_dn *dn1, const struct ldb_dn *dn2)
+{
+	int i;
+	struct ldb_dn *new;
+
+	if (dn2 == NULL && dn1 == NULL) {
+		return NULL;
+	}
+
+	if (dn2 == NULL) {
+		new = ldb_dn_new(mem_ctx);
+		LDB_DN_NULL_FAILED(new);
+
+		new->comp_num = dn1->comp_num;
+		new->components = talloc_array(new, struct ldb_dn_component, new->comp_num);
+	} else {
+		new = ldb_dn_copy_partial(mem_ctx, dn2, dn2->comp_num + dn1?dn1->comp_num:0);
+	}
+
+	if (dn1 == NULL) {
+		return new;
+	}
+
+	for (i = 0; i < dn1->comp_num; i++) {
+		new->components[i] = ldb_dn_copy_component(new->components,
+								&(dn1->components[i]));
+	}
+
+	return new;
+
+failed:
+	talloc_free(new);
+	return NULL;
+}
+
+struct ldb_dn *ldb_dn_compose_string_dn(void *mem_ctx, const char *dn1, const struct ldb_dn *dn2)
+{
+	if (dn1 == NULL) return NULL;
+
+	return ldb_dn_compose(mem_ctx, ldb_dn_explode(mem_ctx, dn1), dn2);
+}
+
+struct ldb_dn_component *ldb_dn_get_rdn(void *mem_ctx, const struct ldb_dn *dn)
+{
+	struct ldb_dn_component *rdn;
+
+	if (dn == NULL) return NULL;
+
+	if (dn->comp_num < 1) {
+		return NULL;
+	}
+
+	rdn = talloc(mem_ctx, struct ldb_dn_component);
+	if (rdn == NULL) return NULL;
+
+	*rdn = ldb_dn_copy_component(mem_ctx, &dn->components[0]);
+	if (rdn->name == NULL) {
+		talloc_free(rdn);
+		return NULL;
+	}
+
+	return rdn;
+}
+
diff --git a/source4/lib/ldb/common/ldb_ldif.c b/source4/lib/ldb/common/ldb_ldif.c
index 463bae483b..6359c9a014 100644
--- a/source4/lib/ldb/common/ldb_ldif.c
+++ b/source4/lib/ldb/common/ldb_ldif.c
@@ -275,7 +275,7 @@ int ldb_ldif_write(struct ldb_context *ldb,
 
 	msg = ldif->msg;
 
-	ret = fprintf_fn(private_data, "dn: %s\n", msg->dn);
+	ret = fprintf_fn(private_data, "dn: %s\n", ldb_dn_linearize(msg->dn, msg->dn));
 	CHECK_RET;
 
 	if (ldif->changetype != LDB_CHANGETYPE_NONE) {
@@ -587,7 +587,7 @@ struct ldb_ldif *ldb_ldif_read(struct ldb_context *ldb,
 		goto failed;
 	}
 
-	msg->dn = value.data;
+	msg->dn = ldb_dn_explode(msg, value.data);
 
 	while (next_attr(ldif, &s, &attr, &value) == 0) {
 		const struct ldb_attrib_handler *h;		
diff --git a/source4/lib/ldb/common/ldb_match.c b/source4/lib/ldb/common/ldb_match.c
index b6f5f5a18d..1269d99a0f 100644
--- a/source4/lib/ldb/common/ldb_match.c
+++ b/source4/lib/ldb/common/ldb_match.c
@@ -42,27 +42,16 @@
   check if the scope matches in a search result
 */
 static int ldb_match_scope(struct ldb_context *ldb,
-			   const char *base_str,
-			   const char *dn_str,
+			   const struct ldb_dn *base,
+			   const struct ldb_dn *dn,
 			   enum ldb_scope scope)
 {
-	struct ldb_dn *base;
-	struct ldb_dn *dn;
 	int ret = 0;
 
-	if (base_str == NULL) {
+	if (base == NULL || dn == NULL) {
 		return 1;
 	}
 
-	base = ldb_dn_explode_casefold(ldb, base_str);
-	if (base == NULL) return 0;
-
-	dn = ldb_dn_explode_casefold(ldb, dn_str);
-	if (dn == NULL) {
-		talloc_free(base);
-		return 0;
-	}
-
 	switch (scope) {
 	case LDB_SCOPE_BASE:
 		if (ldb_dn_compare(ldb, base, dn) == 0) {
@@ -86,8 +75,6 @@ static int ldb_match_scope(struct ldb_context *ldb,
 		break;
 	}
 
-	talloc_free(base);
-	talloc_free(dn);
 	return ret;
 }
 
@@ -98,7 +85,6 @@ static int ldb_match_scope(struct ldb_context *ldb,
 static int ldb_match_present(struct ldb_context *ldb, 
 			    struct ldb_message *msg,
 			    struct ldb_parse_tree *tree,
-			    const char *base,
 			    enum ldb_scope scope)
 {
 
@@ -116,7 +102,6 @@ static int ldb_match_present(struct ldb_context *ldb,
 static int ldb_match_comparison(struct ldb_context *ldb, 
 				struct ldb_message *msg,
 				struct ldb_parse_tree *tree,
-				const char *base,
 				enum ldb_scope scope,
 				enum ldb_parse_op comp_op)
 {
@@ -158,29 +143,23 @@ static int ldb_match_comparison(struct ldb_context *ldb,
 static int ldb_match_equality(struct ldb_context *ldb, 
 			      struct ldb_message *msg,
 			      struct ldb_parse_tree *tree,
-			      const char *base,
 			      enum ldb_scope scope)
 {
 	unsigned int i;
 	struct ldb_message_element *el;
 	const struct ldb_attrib_handler *h;
-	struct ldb_dn *msgdn, *valuedn;
+	struct ldb_dn *valuedn;
 	int ret;
 
 	if (ldb_attr_cmp(tree->u.equality.attr, "dn") == 0) {
 
-		msgdn = ldb_dn_explode_casefold(ldb, msg->dn);
-		if (msgdn == NULL) return 0;
-
 		valuedn = ldb_dn_explode_casefold(ldb, tree->u.equality.value.data);
 		if (valuedn == NULL) {
-			talloc_free(msgdn);
 			return 0;
 		}
 
-		ret = ldb_dn_compare(ldb, msgdn, valuedn);
+		ret = ldb_dn_compare(ldb, msg->dn, valuedn);
 
-		talloc_free(msgdn);
 		talloc_free(valuedn);
 
 		if (ret == 0) return 1;
@@ -277,7 +256,6 @@ failed:
 static int ldb_match_substring(struct ldb_context *ldb, 
 			       struct ldb_message *msg,
 			       struct ldb_parse_tree *tree,
-			       const char *base,
 			       enum ldb_scope scope)
 {
 	unsigned int i;
@@ -327,7 +305,6 @@ static int ldb_comparator_or(struct ldb_val *v1, struct ldb_val *v2)
 static int ldb_match_extended(struct ldb_context *ldb, 
 			      struct ldb_message *msg,
 			      struct ldb_parse_tree *tree,
-			      const char *base,
 			      enum ldb_scope scope)
 {
 	int i;
@@ -391,7 +368,6 @@ static int ldb_match_extended(struct ldb_context *ldb,
 static int ldb_match_message(struct ldb_context *ldb, 
 			     struct ldb_message *msg,
 			     struct ldb_parse_tree *tree,
-			     const char *base,
 			     enum ldb_scope scope)
 {
 	unsigned int i;
@@ -400,43 +376,41 @@ static int ldb_match_message(struct ldb_context *ldb,
 	switch (tree->operation) {
 	case LDB_OP_AND:
 		for (i=0;i<tree->u.list.num_elements;i++) {
-			v = ldb_match_message(ldb, msg, tree->u.list.elements[i],
-					       base, scope);
+			v = ldb_match_message(ldb, msg, tree->u.list.elements[i], scope);
 			if (!v) return 0;
 		}
 		return 1;
 
 	case LDB_OP_OR:
 		for (i=0;i<tree->u.list.num_elements;i++) {
-			v = ldb_match_message(ldb, msg, tree->u.list.elements[i],
-					      base, scope);
+			v = ldb_match_message(ldb, msg, tree->u.list.elements[i], scope);
 			if (v) return 1;
 		}
 		return 0;
 
 	case LDB_OP_NOT:
-		return ! ldb_match_message(ldb, msg, tree->u.isnot.child, base, scope);
+		return ! ldb_match_message(ldb, msg, tree->u.isnot.child, scope);
 
 	case LDB_OP_EQUALITY:
-		return ldb_match_equality(ldb, msg, tree, base, scope);
+		return ldb_match_equality(ldb, msg, tree, scope);
 
 	case LDB_OP_SUBSTRING:
-		return ldb_match_substring(ldb, msg, tree, base, scope);
+		return ldb_match_substring(ldb, msg, tree, scope);
 
 	case LDB_OP_GREATER:
-		return ldb_match_comparison(ldb, msg, tree, base, scope, LDB_OP_GREATER);
+		return ldb_match_comparison(ldb, msg, tree, scope, LDB_OP_GREATER);
 
 	case LDB_OP_LESS:
-		return ldb_match_comparison(ldb, msg, tree, base, scope, LDB_OP_LESS);
+		return ldb_match_comparison(ldb, msg, tree, scope, LDB_OP_LESS);
 
 	case LDB_OP_PRESENT:
-		return ldb_match_present(ldb, msg, tree, base, scope);
+		return ldb_match_present(ldb, msg, tree, scope);
 
 	case LDB_OP_APPROX:
-		return ldb_match_comparison(ldb, msg, tree, base, scope, LDB_OP_APPROX);
+		return ldb_match_comparison(ldb, msg, tree, scope, LDB_OP_APPROX);
 
 	case LDB_OP_EXTENDED:
-		return ldb_match_extended(ldb, msg, tree, base, scope);
+		return ldb_match_extended(ldb, msg, tree, scope);
 
 	}
 
@@ -446,12 +420,12 @@ static int ldb_match_message(struct ldb_context *ldb,
 int ldb_match_msg(struct ldb_context *ldb,
 		  struct ldb_message *msg,
 		  struct ldb_parse_tree *tree,
-		  const char *base,
+		  const struct ldb_dn *base,
 		  enum ldb_scope scope)
 {
 	if ( ! ldb_match_scope(ldb, base, msg->dn, scope) ) {
 		return 0;
 	}
 
-	return ldb_match_message(ldb, msg, tree, base, scope);
+	return ldb_match_message(ldb, msg, tree, scope);
 }
diff --git a/source4/lib/ldb/common/ldb_modules.c b/source4/lib/ldb/common/ldb_modules.c
index dcc384ffad..ab743d1b49 100644
--- a/source4/lib/ldb/common/ldb_modules.c
+++ b/source4/lib/ldb/common/ldb_modules.c
@@ -139,8 +139,15 @@ int ldb_load_modules(struct ldb_context *ldb, const char *options[])
 		int ret;
 		const char * const attrs[] = { "@LIST" , NULL};
 		struct ldb_message **msg = NULL;
+		struct ldb_dn *mods;
 
-		ret = ldb_search(ldb, "@MODULES", LDB_SCOPE_BASE, "", attrs, &msg);
+		mods = ldb_dn_explode(ldb, "@MODULES");
+		if (mods == NULL) {
+			return -1;
+		}
+
+		ret = ldb_search(ldb, mods, LDB_SCOPE_BASE, "", attrs, &msg);
+		talloc_free(mods);
 		if (ret == 0 || (ret == 1 && msg[0]->num_elements == 0)) {
 			ldb_debug(ldb, LDB_DEBUG_TRACE, "no modules required by the db\n");
 		} else {
@@ -233,7 +240,7 @@ int ldb_load_modules(struct ldb_context *ldb, const char *options[])
 */
 
 int ldb_next_search(struct ldb_module *module, 
-		    const char *base,
+		    const struct ldb_dn *base,
 		    enum ldb_scope scope,
 		    const char *expression,
 		    const char * const *attrs, struct ldb_message ***res)
@@ -245,7 +252,7 @@ int ldb_next_search(struct ldb_module *module,
 }
 
 int ldb_next_search_bytree(struct ldb_module *module, 
-			   const char *base,
+			   const struct ldb_dn *base,
 			   enum ldb_scope scope,
 			   struct ldb_parse_tree *tree,
 			   const char * const *attrs, struct ldb_message ***res)
@@ -272,7 +279,7 @@ int ldb_next_modify_record(struct ldb_module *module, const struct ldb_message *
 	return module->next->ops->modify_record(module->next, message);
 }
 
-int ldb_next_delete_record(struct ldb_module *module, const char *dn)
+int ldb_next_delete_record(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	if (!module->next) {
 		return -1;
@@ -280,7 +287,7 @@ int ldb_next_delete_record(struct ldb_module *module, const char *dn)
 	return module->next->ops->delete_record(module->next, dn);
 }
 
-int ldb_next_rename_record(struct ldb_module *module, const char *olddn, const char *newdn)
+int ldb_next_rename_record(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
 	if (!module->next) {
 		return -1;
diff --git a/source4/lib/ldb/common/ldb_msg.c b/source4/lib/ldb/common/ldb_msg.c
index 295c74c90d..197c42ddb5 100644
--- a/source4/lib/ldb/common/ldb_msg.c
+++ b/source4/lib/ldb/common/ldb_msg.c
@@ -344,7 +344,6 @@ const char *ldb_msg_find_string(const struct ldb_message *msg,
 	return v->data;
 }
 
-
 /*
   sort the elements of a message by name
 */
@@ -354,32 +353,23 @@ void ldb_msg_sort_elements(struct ldb_message *msg)
 	      (comparison_fn_t)ldb_msg_element_compare_name);
 }
 
-
-/*
-  free a message created using ldb_msg_copy
-*/
-void ldb_msg_free(struct ldb_context *ldb, struct ldb_message *msg)
-{
-	talloc_free(msg);
-}
-
 /*
   copy a message, allocating new memory for all parts
 */
-struct ldb_message *ldb_msg_copy(struct ldb_context *ldb, 
+struct ldb_message *ldb_msg_copy(TALLOC_CTX *mem_ctx, 
 				 const struct ldb_message *msg)
 {
 	struct ldb_message *msg2;
 	int i, j;
 
-	msg2 = talloc(ldb, struct ldb_message);
+	msg2 = talloc(mem_ctx, struct ldb_message);
 	if (msg2 == NULL) return NULL;
 
 	msg2->elements = NULL;
 	msg2->num_elements = 0;
 	msg2->private_data = NULL;
 
-	msg2->dn = talloc_strdup(msg2, msg->dn);
+	msg2->dn = ldb_dn_copy(msg2, msg->dn);
 	if (msg2->dn == NULL) goto failed;
 
 	msg2->elements = talloc_array(msg2, struct ldb_message_element, msg->num_elements);
@@ -396,12 +386,11 @@ struct ldb_message *ldb_msg_copy(struct ldb_context *ldb,
 		if (el2->name == NULL) goto failed;
 		el2->values = talloc_array(msg2->elements, struct ldb_val, el1->num_values);
 		for (j=0;j<el1->num_values;j++) {
-			el2->values[j] = ldb_val_dup(ldb, &el1->values[j]);
+			el2->values[j] = ldb_val_dup(el2->values, &el1->values[j]);
 			if (el2->values[j].data == NULL &&
 			    el1->values[j].length != 0) {
 				goto failed;
 			}
-			el2->values[j].data = talloc_steal(el2->values, el2->values[j].data);
 			el2->num_values++;
 		}
 
diff --git a/source4/lib/ldb/include/ldb.h b/source4/lib/ldb/include/ldb.h
index fdf5dc8d91..13c9b72e6d 100644
--- a/source4/lib/ldb/include/ldb.h
+++ b/source4/lib/ldb/include/ldb.h
@@ -64,6 +64,16 @@ struct ldb_val {
 };
 #endif
 
+/* internal ldb exploded dn structures */
+struct ldb_dn_component {
+	char *name;
+	struct ldb_val value;
+};
+struct ldb_dn {
+	int comp_num;
+	struct ldb_dn_component *components;
+};
+
 /* these flags are used in ldd_message_element.flags fields. The
    LDA_FLAGS_MOD_* flags are used in ldap_modify() calls to specify
    whether attributes are being added, deleted or modified */
@@ -95,7 +105,7 @@ struct ldb_message_element {
   number of elements. 
 */
 struct ldb_message {
-	char *dn;
+	struct ldb_dn *dn;
 	unsigned int num_elements;
 	struct ldb_message_element *elements;
 	void *private_data; /* private to the backend */
@@ -259,7 +269,7 @@ int ldb_connect(struct ldb_context *ldb, const char *url, unsigned int flags, co
   use talloc_free to free the ldb_message returned
 */
 int ldb_search(struct ldb_context *ldb, 
-	       const char *base,
+	       const const struct ldb_dn *base,
 	       enum ldb_scope scope,
 	       const char *expression,
 	       const char * const *attrs, struct ldb_message ***res);
@@ -268,7 +278,7 @@ int ldb_search(struct ldb_context *ldb,
   like ldb_search() but takes a parse tree
 */
 int ldb_search_bytree(struct ldb_context *ldb, 
-		      const char *base,
+		      const struct ldb_dn *base,
 		      enum ldb_scope scope,
 		      struct ldb_parse_tree *tree,
 		      const char * const *attrs, struct ldb_message ***res);
@@ -289,7 +299,7 @@ int ldb_modify(struct ldb_context *ldb,
 /*
   rename a record in the database
 */
-int ldb_rename(struct ldb_context *ldb, const char *olddn, const char *newdn);
+int ldb_rename(struct ldb_context *ldb, const struct ldb_dn *olddn, const struct ldb_dn *newdn);
 
 /*
   create a named lock
@@ -304,7 +314,7 @@ int ldb_unlock(struct ldb_context *ldb, const char *lockname);
 /*
   delete a record from the database
 */
-int ldb_delete(struct ldb_context *ldb, const char *dn);
+int ldb_delete(struct ldb_context *ldb, const struct ldb_dn *dn);
 
 
 /*
@@ -337,19 +347,38 @@ int ldb_attrib_add_handlers(struct ldb_context *ldb,
 			    const struct ldb_attrib_handler *handlers, 
 			    unsigned num_handlers);
 
+/* The following definitions come from lib/ldb/common/ldb_dn.c  */
+BOOL ldb_dn_is_special(const struct ldb_dn *dn);
+BOOL ldb_dn_check_special(const struct ldb_dn *dn, const char *check);
+char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value);
+struct ldb_dn *ldb_dn_new(void *mem_ctx);
+struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn);
+char *ldb_dn_linearize(void *mem_ctx, const struct ldb_dn *edn);
+char *ldb_dn_linearize_casefold(struct ldb_context *ldb, const struct ldb_dn *edn);
+int ldb_dn_compare_base(struct ldb_context *ldb, const struct ldb_dn *base, const struct ldb_dn *dn);
+int ldb_dn_compare(struct ldb_context *ldb, const struct ldb_dn *edn0, const struct ldb_dn *edn1);
+struct ldb_dn *ldb_dn_casefold(struct ldb_context *ldb, const struct ldb_dn *edn);
+struct ldb_dn *ldb_dn_explode_casefold(struct ldb_context *ldb, const char *dn);
+struct ldb_dn *ldb_dn_copy_partial(void *mem_ctx, const struct ldb_dn *dn, int num_el);
+struct ldb_dn *ldb_dn_copy(void *mem_ctx, const struct ldb_dn *dn);
+struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, const struct ldb_dn *dn);
+struct ldb_dn_component *ldb_dn_build_component(void *mem_ctx, const char *attr,
+							       const char *val);
+struct ldb_dn *ldb_dn_build_child(void *mem_ctx, const char *attr,
+						 const char * value,
+						 const struct ldb_dn *base);
+struct ldb_dn *ldb_dn_make_child(void *mem_ctx,
+				 const struct ldb_dn_component *component,
+				 const struct ldb_dn *base);
+struct ldb_dn *ldb_dn_compose(void *mem_ctx, const struct ldb_dn *dn1, const struct ldb_dn *dn2);
+struct ldb_dn *ldb_dn_compose_string_dn(void *mem_ctx, const char *dn1, const struct ldb_dn *dn2);
+struct ldb_dn_component *ldb_dn_get_rdn(void *mem_ctx, const struct ldb_dn *dn);
 
 /* useful functions for ldb_message structure manipulation */
-
 int ldb_dn_cmp(struct ldb_context *ldb, const char *dn1, const char *dn2);
 int ldb_attr_cmp(const char *dn1, const char *dn2);
 char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value);
 
-/* case-fold a DN */
-char *ldb_dn_fold(void * mem_ctx,
-                  const char * dn,
-                  void * user_data,
-                  int (* case_fold_attr_fn)(void * user_data, char * attr));
-
 /* create an empty message */
 struct ldb_message *ldb_msg_new(void *mem_ctx);
 
@@ -411,9 +440,7 @@ const char *ldb_msg_find_string(const struct ldb_message *msg,
 
 void ldb_msg_sort_elements(struct ldb_message *msg);
 
-void ldb_msg_free(struct ldb_context *ldb, struct ldb_message *msg);
-
-struct ldb_message *ldb_msg_copy(struct ldb_context *ldb, 
+struct ldb_message *ldb_msg_copy(void *mem_ctx, 
 				 const struct ldb_message *msg);
 
 struct ldb_message *ldb_msg_canonicalize(struct ldb_context *ldb, 
diff --git a/source4/lib/ldb/include/ldb_private.h b/source4/lib/ldb/include/ldb_private.h
index 43e6a3ecba..f5b50f5fc0 100644
--- a/source4/lib/ldb/include/ldb_private.h
+++ b/source4/lib/ldb/include/ldb_private.h
@@ -56,14 +56,14 @@ struct ldb_module {
 */
 struct ldb_module_ops {
 	const char *name;
-	int (*search)(struct ldb_module *, const char *, enum ldb_scope,
+	int (*search)(struct ldb_module *, const struct ldb_dn *, enum ldb_scope,
 		      const char *, const char * const [], struct ldb_message ***);
-	int (*search_bytree)(struct ldb_module *, const char *, enum ldb_scope,
+	int (*search_bytree)(struct ldb_module *, const struct ldb_dn *, enum ldb_scope,
 			     struct ldb_parse_tree *, const char * const [], struct ldb_message ***);
 	int (*add_record)(struct ldb_module *, const struct ldb_message *);
 	int (*modify_record)(struct ldb_module *, const struct ldb_message *);
-	int (*delete_record)(struct ldb_module *, const char *);
-	int (*rename_record)(struct ldb_module *, const char *, const char *);
+	int (*delete_record)(struct ldb_module *, const struct ldb_dn *);
+	int (*rename_record)(struct ldb_module *, const struct ldb_dn *, const struct ldb_dn *);
 	int (*named_lock)(struct ldb_module *, const char *);
 	int (*named_unlock)(struct ldb_module *, const char *);
 	const char * (*errstring)(struct ldb_module *);
@@ -106,16 +106,6 @@ struct ldb_context {
 	struct ldb_schema schema;
 };
 
-/* internal ldb exploded dn structures */
-struct ldb_dn_component {
-	char *name;
-	struct ldb_val value;
-};
-struct ldb_dn {
-	int comp_num;
-	struct ldb_dn_component *components;
-};
-
 /* the modules init function */
 typedef struct ldb_module *(*ldb_module_init_function)(struct ldb_context *ldb, const char *options[]);
 
@@ -132,19 +122,19 @@ typedef struct ldb_module *(*ldb_module_init_function)(struct ldb_context *ldb,
 
 int ldb_load_modules(struct ldb_context *ldb, const char *options[]);
 int ldb_next_search(struct ldb_module *module, 
-	       const char *base,
+	       const struct ldb_dn *base,
 	       enum ldb_scope scope,
 	       const char *expression,
 	       const char * const *attrs, struct ldb_message ***res);
 int ldb_next_search_bytree(struct ldb_module *module, 
-			   const char *base,
+			   const struct ldb_dn *base,
 			   enum ldb_scope scope,
 			   struct ldb_parse_tree *tree,
 			   const char * const *attrs, struct ldb_message ***res);
 int ldb_next_add_record(struct ldb_module *module, const struct ldb_message *message);
 int ldb_next_modify_record(struct ldb_module *module, const struct ldb_message *message);
-int ldb_next_delete_record(struct ldb_module *module, const char *dn);
-int ldb_next_rename_record(struct ldb_module *module, const char *olddn, const char *newdn);
+int ldb_next_delete_record(struct ldb_module *module, const struct ldb_dn *dn);
+int ldb_next_rename_record(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn);
 int ldb_next_named_lock(struct ldb_module *module, const char *lockname);
 int ldb_next_named_unlock(struct ldb_module *module, const char *lockname);
 const char *ldb_next_errstring(struct ldb_module *module);
@@ -174,10 +164,10 @@ struct ldb_module *schema_module_init(struct ldb_context *ldb, const char *optio
 struct ldb_module *rdn_name_module_init(struct ldb_context *ldb, const char *options[]);
 
 
-int ldb_match_msg(struct ldb_context *ldb, 
+int ldb_match_msg(struct ldb_context *ldb,
 		  struct ldb_message *msg,
 		  struct ldb_parse_tree *tree,
-		  const char *base,
+		  const struct ldb_dn *base,
 		  enum ldb_scope scope);
 
 void ldb_remove_attrib_handler(struct ldb_context *ldb, const char *attrib);
@@ -188,15 +178,6 @@ int ldb_set_attrib_handlers(struct ldb_context *ldb,
 			    unsigned num_handlers);
 int ldb_setup_wellknown_attributes(struct ldb_context *ldb);
 
-
-/* The following definitions come from lib/ldb/common/ldb_dn.c  */
-struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn);
-char *ldb_dn_linearize(void *mem_ctx, const struct ldb_dn *edn);
-int ldb_dn_compare_base(struct ldb_context *ldb, const struct ldb_dn *base, const struct ldb_dn *dn);
-int ldb_dn_compare(struct ldb_context *ldb, const struct ldb_dn *edn0, const struct ldb_dn *edn1);
-struct ldb_dn *ldb_dn_casefold(struct ldb_context *ldb, const struct ldb_dn *edn);
-struct ldb_dn *ldb_dn_explode_casefold(struct ldb_context *ldb, const char *dn);
-
 /* The following definitions come from lib/ldb/common/ldb_attributes.c  */
 const char **ldb_subclass_list(struct ldb_context *ldb, const char *class);
 void ldb_subclass_remove(struct ldb_context *ldb, const char *class);
diff --git a/source4/lib/ldb/ldb_ildap/ldb_ildap.c b/source4/lib/ldb/ldb_ildap/ldb_ildap.c
index b51139aa6f..bb89fc910e 100644
--- a/source4/lib/ldb/ldb_ildap/ldb_ildap.c
+++ b/source4/lib/ldb/ldb_ildap/ldb_ildap.c
@@ -45,57 +45,77 @@ struct ildb_private {
 /*
   rename a record
 */
-static int ildb_rename(struct ldb_module *module, const char *olddn, const char *newdn)
+static int ildb_rename(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
+	TALLOC_CTX *local_ctx;
 	struct ildb_private *ildb = module->private_data;
 	int ret = 0;
-	char *newrdn, *p;
-	const char *parentdn = "";
+	char *old_dn;
+	char *newrdn, *parentdn;
 
 	/* ignore ltdb specials */
-	if (olddn[0] == '@' ||newdn[0] == '@') {
+	if (ldb_dn_is_special(olddn) || ldb_dn_is_special(newdn)) {
 		return 0;
 	}
 
-	newrdn = talloc_strdup(ildb, newdn);
-	if (!newrdn) {
+	local_ctx = talloc_named(ildb, 0, "ildb_rename local context");
+	if (local_ctx == NULL) {
 		return -1;
 	}
 
-	p = strchr(newrdn, ',');
-	if (p) {
-		*p++ = '\0';
-		parentdn = p;
+	old_dn = ldb_dn_linearize(local_ctx, olddn);
+	if (old_dn == NULL) {
+		goto failed;
+	}
+
+	newrdn = talloc_asprintf(local_ctx, "%s=%s",
+					    newdn->components[0].name,
+					    ldb_dn_escape_value(ildb, newdn->components[0].value));
+	if (newrdn == NULL) {
+		goto failed;
+	}
+
+	parentdn = ldb_dn_linearize(local_ctx, ldb_dn_get_parent(ildb, newdn));
+	if (parentdn == NULL) {
+		goto failed;
 	}
 
-	ildb->last_rc = ildap_rename(ildb->ldap, olddn, newrdn, parentdn, True);
+	ildb->last_rc = ildap_rename(ildb->ldap, old_dn, newrdn, parentdn, True);
 	if (!NT_STATUS_IS_OK(ildb->last_rc)) {
 		ret = -1;
 	}
 
-	talloc_free(newrdn);
-
+	talloc_free(local_ctx);
 	return ret;
+
+failed:
+	talloc_free(local_ctx);
+	return -1;
 }
 
 /*
   delete a record
 */
-static int ildb_delete(struct ldb_module *module, const char *dn)
+static int ildb_delete(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	struct ildb_private *ildb = module->private_data;
+	char *del_dn;
 	int ret = 0;
 
 	/* ignore ltdb specials */
-	if (dn[0] == '@') {
+	if (ldb_dn_is_special(dn)) {
 		return 0;
 	}
 	
-	ildb->last_rc = ildap_delete(ildb->ldap, dn);
+	del_dn = ldb_dn_linearize(ildb, dn);
+
+	ildb->last_rc = ildap_delete(ildb->ldap, del_dn);
 	if (!NT_STATUS_IS_OK(ildb->last_rc)) {
 		ret = -1;
 	}
 
+	talloc_free(del_dn);
+
 	return ret;
 }
 
@@ -105,13 +125,14 @@ static void ildb_rootdse(struct ldb_module *module);
 /*
   search for matching records
 */
-static int ildb_search(struct ldb_module *module, const char *base,
+static int ildb_search(struct ldb_module *module, const struct ldb_dn *base,
 		       enum ldb_scope scope, const char *expression,
 		       const char * const *attrs, struct ldb_message ***res)
 {
 	struct ildb_private *ildb = module->private_data;
 	int count, i;
 	struct ldap_message **ldapres, *msg;
+	char *search_base;
 
 	if (scope == LDB_SCOPE_DEFAULT) {
 		scope = LDB_SCOPE_SUBTREE;
@@ -122,19 +143,26 @@ static int ildb_search(struct ldb_module *module, const char *base,
 			ildb_rootdse(module);
 		}
 		if (ildb->rootDSE != NULL) {
-			base = ldb_msg_find_string(ildb->rootDSE, 
-						   "defaultNamingContext", "");
+			search_base = talloc_strdup(ildb,
+						ldb_msg_find_string(ildb->rootDSE, 
+								"defaultNamingContext", ""));
 		} else {
-			base = "";
+			search_base = talloc_strdup(ildb, "");
 		}
+	} else {
+		search_base = ldb_dn_linearize(ildb, base);
+	}
+	if (search_base == NULL) {
+		return -1;
 	}
 
 	if (expression == NULL || expression[0] == '\0') {
 		expression = "objectClass=*";
 	}
 
-	ildb->last_rc = ildap_search(ildb->ldap, base, scope, expression, attrs, 
+	ildb->last_rc = ildap_search(ildb->ldap, search_base, scope, expression, attrs, 
 				     0, &ldapres);
+	talloc_free(search_base);
 	if (!NT_STATUS_IS_OK(ildb->last_rc)) {
 		return -1;
 	}
@@ -166,7 +194,10 @@ static int ildb_search(struct ldb_module *module, const char *base,
 		}
 		(*res)[i+1] = NULL;
 
-		(*res)[i]->dn = talloc_steal((*res)[i], search->dn);
+		(*res)[i]->dn = ldb_dn_explode((*res)[i], search->dn);
+		if ((*res)[i]->dn == NULL) {
+			goto failed;
+		}
 		(*res)[i]->num_elements = search->num_attributes;
 		(*res)[i]->elements = talloc_steal((*res)[i], search->attributes);
 		(*res)[i]->private_data = NULL;
@@ -185,7 +216,7 @@ failed:
 /*
   search for matching records using a ldb_parse_tree
 */
-static int ildb_search_bytree(struct ldb_module *module, const char *base,
+static int ildb_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 			      enum ldb_scope scope, struct ldb_parse_tree *tree,
 			      const char * const *attrs, struct ldb_message ***res)
 {
@@ -264,16 +295,26 @@ static int ildb_add(struct ldb_module *module, const struct ldb_message *msg)
 	struct ldb_context *ldb = module->ldb;
 	struct ildb_private *ildb = module->private_data;
 	struct ldap_mod **mods;
+	char *dn;
 	int ret = 0;
 
 	/* ignore ltdb specials */
-	if (msg->dn[0] == '@') {
+	if (ldb_dn_is_special(msg->dn)) {
 		return 0;
 	}
 
 	mods = ildb_msg_to_mods(ldb, msg, 0);
+	if (mods == NULL) {
+		return -1;
+	}
 
-	ildb->last_rc = ildap_add(ildb->ldap, msg->dn, mods);
+	dn = ldb_dn_linearize(mods, msg->dn);
+	if (dn == NULL) {
+		talloc_free(mods);
+		return -1;
+	}
+
+	ildb->last_rc = ildap_add(ildb->ldap, dn, mods);
 	if (!NT_STATUS_IS_OK(ildb->last_rc)) {
 		ret = -1;
 	}
@@ -292,16 +333,26 @@ static int ildb_modify(struct ldb_module *module, const struct ldb_message *msg)
 	struct ldb_context *ldb = module->ldb;
 	struct ildb_private *ildb = module->private_data;
 	struct ldap_mod **mods;
+	char *dn;
 	int ret = 0;
 
 	/* ignore ltdb specials */
-	if (msg->dn[0] == '@') {
+	if (ldb_dn_is_special(msg->dn)) {
 		return 0;
 	}
 
 	mods = ildb_msg_to_mods(ldb, msg, 1);
+	if (mods == NULL) {
+		return -1;
+	}
+
+	dn = ldb_dn_linearize(mods, msg->dn);
+	if (dn == NULL) {
+		talloc_free(mods);
+		return -1;
+	}
 
-	ildb->last_rc = ildap_modify(ildb->ldap, msg->dn, mods);
+	ildb->last_rc = ildap_modify(ildb->ldap, dn, mods);
 	if (!NT_STATUS_IS_OK(ildb->last_rc)) {
 		ret = -1;
 	}
@@ -372,12 +423,14 @@ static void ildb_rootdse(struct ldb_module *module)
 {
 	struct ildb_private *ildb = module->private_data;
 	struct ldb_message **res = NULL;
+	struct ldb_dn *empty_dn = ldb_dn_new(ildb);
 	int ret;
-	ret = ildb_search(module, "", LDB_SCOPE_BASE, "dn=dc=rootDSE", NULL, &res);
+	ret = ildb_search(module, empty_dn, LDB_SCOPE_BASE, "dn=dc=rootDSE", NULL, &res);
 	if (ret == 1) {
 		ildb->rootDSE = talloc_steal(ildb, res[0]);
 	}
-	talloc_free(res);
+	if (ret != -1) talloc_free(res);
+	talloc_free(empty_dn);
 }
 
 
diff --git a/source4/lib/ldb/ldb_ldap/ldb_ldap.c b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
index d7f589e2e5..2da4f1af8e 100644
--- a/source4/lib/ldb/ldb_ldap/ldb_ldap.c
+++ b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
@@ -40,57 +40,77 @@
 /*
   rename a record
 */
-static int lldb_rename(struct ldb_module *module, const char *olddn, const char *newdn)
+static int lldb_rename(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
+	TALLOC_CTX *local_ctx;
 	struct lldb_private *lldb = module->private_data;
 	int ret = 0;
-	char *newrdn, *p;
+	char *old_dn;
+	char *newrdn;
 	const char *parentdn = "";
 
 	/* ignore ltdb specials */
-	if (olddn[0] == '@' ||newdn[0] == '@') {
+	if (ldb_dn_is_special(olddn) || ldb_dn_is_special(newdn)) {
 		return 0;
 	}
 
-	newrdn = talloc_strdup(lldb, newdn);
-	if (!newrdn) {
+	local_ctx = talloc_named(lldb, 0, "lldb_rename local context");
+	if (local_ctx == NULL) {
 		return -1;
 	}
 
-	p = strchr(newrdn, ',');
-	if (p) {
-		*p++ = '\0';
-		parentdn = p;
+	old_dn = ldb_dn_linearize(local_ctx, olddn);
+	if (old_dn == NULL) {
+		goto failed;
+	}
+
+	newrdn = talloc_asprintf(lldb, "%s=%s",
+				      newdn->components[0].name,
+				      ldb_dn_escape_value(lldb, newdn->components[0].value));
+	if (!newrdn) {
+		goto failed;
+	}
+
+	parentdn = ldb_dn_linearize(lldb, ldb_dn_get_parent(lldb, newdn));
+	if (!parentdn) {
+		goto failed;
 	}
 
-	lldb->last_rc = ldap_rename_s(lldb->ldap, olddn, newrdn, parentdn, 1, NULL, NULL);
+	lldb->last_rc = ldap_rename_s(lldb->ldap, old_dn, newrdn, parentdn, 1, NULL, NULL);
 	if (lldb->last_rc != LDAP_SUCCESS) {
 		ret = -1;
 	}
 
-	talloc_free(newrdn);
-
+	talloc_free(local_ctx);
 	return ret;
+
+failed:
+	talloc_free(local_ctx);
+	return -1;
 }
 
 /*
   delete a record
 */
-static int lldb_delete(struct ldb_module *module, const char *dn)
+static int lldb_delete(struct ldb_module *module, const struct ldb_dn *edn)
 {
 	struct lldb_private *lldb = module->private_data;
+	char *dn;
 	int ret = 0;
 
 	/* ignore ltdb specials */
-	if (dn[0] == '@') {
+	if (ldb_dn_is_special(edn)) {
 		return 0;
 	}
-	
+
+	dn = ldb_dn_linearize(lldb, edn);
+
 	lldb->last_rc = ldap_delete_s(lldb->ldap, dn);
 	if (lldb->last_rc != LDAP_SUCCESS) {
 		ret = -1;
 	}
 
+	talloc_free(dn);
 	return ret;
 }
 
@@ -152,27 +172,33 @@ static int lldb_add_msg_attr(struct ldb_context *ldb,
 /*
   search for matching records
 */
-static int lldb_search(struct ldb_module *module, const char *base,
+static int lldb_search(struct ldb_module *module, const struct ldb_dn *base,
 		       enum ldb_scope scope, const char *expression,
 		       const char * const *attrs, struct ldb_message ***res)
 {
 	struct ldb_context *ldb = module->ldb;
 	struct lldb_private *lldb = module->private_data;
 	int count, msg_count;
+	char *search_base;
 	LDAPMessage *ldapres, *msg;
 
+	search_base = ldb_dn_linearize(ldb, base);
 	if (base == NULL) {
-		base = "";
+		search_base = talloc_strdup(ldb, "");
+	}
+	if (search_base == NULL) {
+		return -1;
 	}
 
 	if (expression == NULL || expression[0] == '\0') {
 		expression = "objectClass=*";
 	}
 
-	lldb->last_rc = ldap_search_s(lldb->ldap, base, (int)scope, 
+	lldb->last_rc = ldap_search_s(lldb->ldap, search_base, (int)scope, 
 				      expression, 
 				      discard_const_p(char *, attrs), 
 				      0, &ldapres);
+	talloc_free(search_base);
 	if (lldb->last_rc != LDAP_SUCCESS) {
 		return -1;
 	}
@@ -218,7 +244,7 @@ static int lldb_search(struct ldb_module *module, const char *base,
 			goto failed;
 		}
 
-		(*res)[msg_count]->dn = talloc_strdup((*res)[msg_count], dn);
+		(*res)[msg_count]->dn = ldb_dn_explode((*res)[msg_count], dn);
 		ldap_memfree(dn);
 		if (!(*res)[msg_count]->dn) {
 			goto failed;
@@ -261,7 +287,7 @@ failed:
 /*
   search for matching records using a ldb_parse_tree
 */
-static int lldb_search_bytree(struct ldb_module *module, const char *base,
+static int lldb_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 			      enum ldb_scope scope, struct ldb_parse_tree *tree,
 			      const char * const *attrs, struct ldb_message ***res)
 {
@@ -357,16 +383,26 @@ static int lldb_add(struct ldb_module *module, const struct ldb_message *msg)
 	struct ldb_context *ldb = module->ldb;
 	struct lldb_private *lldb = module->private_data;
 	LDAPMod **mods;
+	char *dn;
 	int ret = 0;
 
 	/* ignore ltdb specials */
-	if (msg->dn[0] == '@') {
+	if (ldb_dn_is_special(msg->dn)) {
 		return 0;
 	}
 
 	mods = lldb_msg_to_mods(ldb, msg, 0);
+	if (mods == NULL) {
+		return -1;
+	}
 
-	lldb->last_rc = ldap_add_s(lldb->ldap, msg->dn, mods);
+	dn = ldb_dn_linearize(mods, msg->dn);
+	if (dn == NULL) {
+		talloc_free(mods);
+		return -1;
+	}
+
+	lldb->last_rc = ldap_add_s(lldb->ldap, dn, mods);
 	if (lldb->last_rc != LDAP_SUCCESS) {
 		ret = -1;
 	}
@@ -385,16 +421,26 @@ static int lldb_modify(struct ldb_module *module, const struct ldb_message *msg)
 	struct ldb_context *ldb = module->ldb;
 	struct lldb_private *lldb = module->private_data;
 	LDAPMod **mods;
+	char *dn;
 	int ret = 0;
 
 	/* ignore ltdb specials */
-	if (msg->dn[0] == '@') {
+	if (ldb_dn_is_special(msg->dn)) {
 		return 0;
 	}
 
 	mods = lldb_msg_to_mods(ldb, msg, 1);
+	if (mods == NULL) {
+		return -1;
+	}
+
+	dn = ldb_dn_linearize(mods, msg->dn);
+	if (dn == NULL) {
+		talloc_free(mods);
+		return -1;
+	}
 
-	lldb->last_rc = ldap_modify_s(lldb->ldap, msg->dn, mods);
+	lldb->last_rc = ldap_modify_s(lldb->ldap, dn, mods);
 	if (lldb->last_rc != LDAP_SUCCESS) {
 		ret = -1;
 	}
diff --git a/source4/lib/ldb/ldb_tdb/ldb_cache.c b/source4/lib/ldb/ldb_tdb/ldb_cache.c
index be76f7085b..5e40b8fd3f 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_cache.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_cache.c
@@ -115,11 +115,17 @@ static int ltdb_attributes_load(struct ldb_module *module)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	struct ldb_message *msg = ltdb->cache->attributes;
+	struct ldb_dn *dn;
 	int i;
 
-	if (ltdb_search_dn1(module, LTDB_ATTRIBUTES, msg) == -1) {
+	dn = ldb_dn_explode(module->ldb, LTDB_ATTRIBUTES);
+	if (dn == NULL) goto failed;
+
+	if (ltdb_search_dn1(module, dn, msg) == -1) {
+		talloc_free(dn);
 		goto failed;
 	}
+	talloc_free(dn);
 	/* mapping these flags onto ldap 'syntaxes' isn't strictly correct,
 	   but its close enough for now */
 	for (i=0;i<msg->num_elements;i++) {
@@ -176,11 +182,17 @@ static int ltdb_subclasses_load(struct ldb_module *module)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	struct ldb_message *msg = ltdb->cache->subclasses;
+	struct ldb_dn *dn;
 	int i, j;
 
-	if (ltdb_search_dn1(module, LTDB_SUBCLASSES, msg) == -1) {
+	dn = ldb_dn_explode(module->ldb, LTDB_SUBCLASSES);
+	if (dn == NULL) goto failed;
+
+	if (ltdb_search_dn1(module, dn, msg) == -1) {
+		talloc_free(dn);
 		goto failed;
 	}
+	talloc_free(dn);
 
 	for (i=0;i<msg->num_elements;i++) {
 		struct ldb_message_element *el = &msg->elements[i];
@@ -245,7 +257,7 @@ static int ltdb_baseinfo_init(struct ldb_module *module)
 
 	msg->num_elements = 1;
 	msg->elements = &el;
-	msg->dn = talloc_strdup(msg, LTDB_BASEINFO);
+	msg->dn = ldb_dn_explode(msg, LTDB_BASEINFO);
 	if (!msg->dn) {
 		goto failed;
 	}
@@ -303,6 +315,8 @@ int ltdb_cache_reload(struct ldb_module *module)
 int ltdb_cache_load(struct ldb_module *module)
 {
 	struct ltdb_private *ltdb = module->private_data;
+	struct ldb_dn *baseinfo_dn = NULL;
+	struct ldb_dn *indexlist_dn = NULL;
 	double seq;
 
 	if (ltdb->cache == NULL) {
@@ -321,8 +335,11 @@ int ltdb_cache_load(struct ldb_module *module)
 	talloc_free(ltdb->cache->baseinfo);
 	ltdb->cache->baseinfo = talloc(ltdb->cache, struct ldb_message);
 	if (ltdb->cache->baseinfo == NULL) goto failed;
-	
-	if (ltdb_search_dn1(module, LTDB_BASEINFO, ltdb->cache->baseinfo) == -1) {
+
+	baseinfo_dn = ldb_dn_explode(module->ldb, LTDB_BASEINFO);
+	if (baseinfo_dn == NULL) goto failed;
+
+	if (ltdb_search_dn1(module, baseinfo_dn, ltdb->cache->baseinfo) == -1) {
 		goto failed;
 	}
 	
@@ -331,7 +348,7 @@ int ltdb_cache_load(struct ldb_module *module)
 		if (ltdb_baseinfo_init(module) != 0) {
 			goto failed;
 		}
-		if (ltdb_search_dn1(module, LTDB_BASEINFO, ltdb->cache->baseinfo) != 1) {
+		if (ltdb_search_dn1(module, baseinfo_dn, ltdb->cache->baseinfo) != 1) {
 			goto failed;
 		}
 	}
@@ -362,7 +379,10 @@ int ltdb_cache_load(struct ldb_module *module)
 		goto failed;
 	}
 	    
-	if (ltdb_search_dn1(module, LTDB_INDEXLIST, ltdb->cache->indexlist) == -1) {
+	indexlist_dn = ldb_dn_explode(module->ldb, LTDB_INDEXLIST);
+	if (indexlist_dn == NULL) goto failed;
+
+	if (ltdb_search_dn1(module, indexlist_dn, ltdb->cache->indexlist) == -1) {
 		goto failed;
 	}
 
@@ -374,9 +394,13 @@ int ltdb_cache_load(struct ldb_module *module)
 	}
 
 done:
+	talloc_free(baseinfo_dn);
+	talloc_free(indexlist_dn);
 	return 0;
 
 failed:
+	talloc_free(baseinfo_dn);
+	talloc_free(indexlist_dn);
 	return -1;
 }
 
@@ -407,8 +431,18 @@ int ltdb_increase_sequence_number(struct ldb_module *module)
 
 	msg->num_elements = 1;
 	msg->elements = &el;
-	msg->dn = talloc_strdup(msg, LTDB_BASEINFO);
+	msg->dn = ldb_dn_explode(msg, LTDB_BASEINFO);
+	if (msg->dn == NULL) {
+		talloc_free(msg);
+		errno = ENOMEM;
+		return -1;
+	}
 	el.name = talloc_strdup(msg, LTDB_SEQUENCE_NUMBER);
+	if (el.name == NULL) {
+		talloc_free(msg);
+		errno = ENOMEM;
+		return -1;
+	}
 	el.values = &val;
 	el.num_values = 1;
 	el.flags = LDB_FLAG_MOD_REPLACE;
diff --git a/source4/lib/ldb/ldb_tdb/ldb_index.c b/source4/lib/ldb/ldb_tdb/ldb_index.c
index 2fb6c34227..f78d840206 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_index.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_index.c
@@ -97,10 +97,11 @@ struct dn_list {
   return the dn key to be used for an index
   caller frees
 */
-static char *ldb_dn_key(struct ldb_context *ldb,
+static struct ldb_dn *ldb_dn_key(struct ldb_context *ldb,
 			const char *attr, const struct ldb_val *value)
 {
-	char *ret = NULL;
+	struct ldb_dn *ret;
+	char *dn;
 	struct ldb_val v;
 	const struct ldb_attrib_handler *h;
 	char *attr_folded;
@@ -121,16 +122,17 @@ static char *ldb_dn_key(struct ldb_context *ldb,
 	if (ldb_should_b64_encode(&v)) {
 		char *vstr = ldb_base64_encode(ldb, v.data, v.length);
 		if (!vstr) return NULL;
-		ret = talloc_asprintf(ldb, "%s:%s::%s", LTDB_INDEX, attr_folded, vstr);
+		dn = talloc_asprintf(ldb, "%s:%s::%s", LTDB_INDEX, attr_folded, vstr);
 		talloc_free(vstr);
 		if (v.data != value->data) {
 			talloc_free(v.data);
 		}
 		talloc_free(attr_folded);
-		return ret;
+		if (dn == NULL) return NULL;
+		goto done;
 	}
 
-	ret = talloc_asprintf(ldb, "%s:%s:%.*s", 
+	dn = talloc_asprintf(ldb, "%s:%s:%.*s", 
 			      LTDB_INDEX, attr_folded, (int)v.length, (char *)v.data);
 
 	if (v.data != value->data) {
@@ -138,6 +140,9 @@ static char *ldb_dn_key(struct ldb_context *ldb,
 	}
 	talloc_free(attr_folded);
 
+done:
+	ret = ldb_dn_explode(ldb, dn);
+	talloc_free(dn);
 	return ret;
 }
 
@@ -180,7 +185,7 @@ static int ltdb_index_dn_simple(struct ldb_module *module,
 				struct dn_list *list)
 {
 	struct ldb_context *ldb = module->ldb;
-	char *dn = NULL;
+	struct ldb_dn *dn;
 	int ret;
 	unsigned int i, j;
 	struct ldb_message *msg;
@@ -605,7 +610,7 @@ static int ltdb_index_dn(struct ldb_module *module,
   extracting just the given attributes
 */
 static int ldb_index_filter(struct ldb_module *module, struct ldb_parse_tree *tree,
-			    const char *base,
+			    const struct ldb_dn *base,
 			    enum ldb_scope scope,
 			    const struct dn_list *dn_list, 
 			    const char * const attrs[], struct ldb_message ***res)
@@ -613,8 +618,9 @@ static int ldb_index_filter(struct ldb_module *module, struct ldb_parse_tree *tr
 	unsigned int i;
 	int count = 0;
 
-	for (i=0;i<dn_list->count;i++) {
+	for (i = 0; i < dn_list->count; i++) {
 		struct ldb_message *msg;
+		struct ldb_dn *dn;
 		int ret;
 
 		msg = talloc(module, struct ldb_message);
@@ -622,7 +628,14 @@ static int ldb_index_filter(struct ldb_module *module, struct ldb_parse_tree *tr
 			return -1;
 		}
 
-		ret = ltdb_search_dn1(module, dn_list->dn[i], msg);
+		dn = ldb_dn_explode(msg, dn_list->dn[i]);
+		if (dn == NULL) {
+			talloc_free(msg);
+			return -1;
+		}
+
+		ret = ltdb_search_dn1(module, dn, msg);
+		talloc_free(dn);
 		if (ret == 0) {
 			/* the record has disappeared? yes, this can happen */
 			talloc_free(msg);
@@ -654,7 +667,7 @@ static int ldb_index_filter(struct ldb_module *module, struct ldb_parse_tree *tr
   case the caller should call ltdb_search_full() 
 */
 int ltdb_search_indexed(struct ldb_module *module, 
-			const char *base,
+			const struct ldb_dn *base,
 			enum ldb_scope scope,
 			struct ldb_parse_tree *tree,
 			const char * const attrs[], struct ldb_message ***res)
@@ -766,33 +779,32 @@ static int ltdb_index_add1(struct ldb_module *module, char *dn,
 {
 	struct ldb_context *ldb = module->ldb;
 	struct ldb_message *msg;
-	char *dn_key;
+	struct ldb_dn *dn_key;
 	int ret;
 	unsigned int i;
 
-	dn_key = ldb_dn_key(ldb, el->name, &el->values[v_idx]);
-	if (!dn_key) {
+	msg = talloc(module, struct ldb_message);
+	if (msg == NULL) {
+		errno = ENOMEM;
 		return -1;
 	}
 
-	msg = talloc(dn_key, struct ldb_message);
-	if (msg == NULL) {
+	dn_key = ldb_dn_key(ldb, el->name, &el->values[v_idx]);
+	if (!dn_key) {
+		talloc_free(msg);
+		errno = ENOMEM;
 		return -1;
 	}
+	talloc_steal(msg, dn_key);
 
 	ret = ltdb_search_dn1(module, dn_key, msg);
 	if (ret == -1) {
-		talloc_free(dn_key);
+		talloc_free(msg);
 		return -1;
 	}
 
 	if (ret == 0) {
-		msg->dn = talloc_strdup(msg, dn_key);
-		if (!msg->dn) {
-			talloc_free(dn_key);
-			errno = ENOMEM;
-			return -1;
-		}
+		msg->dn = dn_key;
 		msg->num_elements = 0;
 		msg->elements = NULL;
 	}
@@ -813,22 +825,19 @@ static int ltdb_index_add1(struct ldb_module *module, char *dn,
 		ret = ltdb_store(module, msg, TDB_REPLACE);
 	}
 
-	talloc_free(dn_key);
+	talloc_free(msg);
 
 	return ret;
 }
 
-/*
-  add the index entries for a new record
-  return -1 on failure
-*/
-int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg)
+static int ltdb_index_add0(struct ldb_module *module, char *dn,
+			   struct ldb_message_element *elements, int num_el)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	int ret;
 	unsigned int i, j;
 
-	if (msg->dn[0] == '@') {
+	if (dn[0] == '@') {
 		return 0;
 	}
 
@@ -837,15 +846,16 @@ int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg)
 		return 0;
 	}
 
-	for (i=0;i<msg->num_elements;i++) {
-		ret = ldb_msg_find_idx(ltdb->cache->indexlist, msg->elements[i].name, 
+	for (i = 0; i < num_el; i++) {
+		ret = ldb_msg_find_idx(ltdb->cache->indexlist, elements[i].name, 
 				       NULL, LTDB_IDXATTR);
 		if (ret == -1) {
 			continue;
 		}
-		for (j=0;j<msg->elements[i].num_values;j++) {
-			ret = ltdb_index_add1(module, msg->dn, &msg->elements[i], j);
+		for (j = 0; j < elements[i].num_values; j++) {
+			ret = ltdb_index_add1(module, dn, &elements[i], j);
 			if (ret == -1) {
+				talloc_free(dn);
 				return -1;
 			}
 		}
@@ -854,6 +864,28 @@ int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg)
 	return 0;
 }
 
+/*
+  add the index entries for a new record
+  return -1 on failure
+*/
+int ltdb_index_add(struct ldb_module *module, const struct ldb_message *msg)
+{
+	struct ltdb_private *ltdb = module->private_data;
+	char *dn;
+	int ret;
+
+	dn = ldb_dn_linearize(ltdb, msg->dn);
+	if (dn == NULL) {
+		return -1;
+	}
+
+	ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
+
+	talloc_free(dn);
+
+	return ret;
+}
+
 
 /*
   delete an index entry for one message element
@@ -863,7 +895,7 @@ int ltdb_index_del_value(struct ldb_module *module, const char *dn,
 {
 	struct ldb_context *ldb = module->ldb;
 	struct ldb_message *msg;
-	char *dn_key;
+	struct ldb_dn *dn_key;
 	int ret, i;
 	unsigned int j;
 
@@ -897,7 +929,9 @@ int ltdb_index_del_value(struct ldb_module *module, const char *dn,
 
 	i = ldb_msg_find_idx(msg, dn, &j, LTDB_IDX);
 	if (i == -1) {
-		ldb_debug(ldb, LDB_DEBUG_ERROR, "ERROR: dn %s not found in %s\n", dn, dn_key);
+		ldb_debug(ldb, LDB_DEBUG_ERROR,
+				"ERROR: dn %s not found in %s\n", dn,
+				ldb_dn_linearize(dn_key, dn_key));
 		/* it ain't there. hmmm */
 		talloc_free(dn_key);
 		return 0;
@@ -930,32 +964,40 @@ int ltdb_index_del(struct ldb_module *module, const struct ldb_message *msg)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	int ret;
+	char *dn;
 	unsigned int i, j;
 
-	if (msg->dn[0] == '@') {
+	if (ldb_dn_is_special(msg->dn)) {
 		return 0;
 	}
 
+	dn = ldb_dn_linearize(ltdb, msg->dn);
+	if (dn == NULL) {
+		return -1;
+	}
+
 	/* find the list of indexed fields */	
 	if (ltdb->cache->indexlist->num_elements == 0) {
 		/* no indexed fields */
 		return 0;
 	}
 
-	for (i=0;i<msg->num_elements;i++) {
+	for (i = 0; i < msg->num_elements; i++) {
 		ret = ldb_msg_find_idx(ltdb->cache->indexlist, msg->elements[i].name, 
 				       NULL, LTDB_IDXATTR);
 		if (ret == -1) {
 			continue;
 		}
-		for (j=0;j<msg->elements[i].num_values;j++) {
-			ret = ltdb_index_del_value(module, msg->dn, &msg->elements[i], j);
+		for (j = 0; j < msg->elements[i].num_values; j++) {
+			ret = ltdb_index_del_value(module, dn, &msg->elements[i], j);
 			if (ret == -1) {
+				talloc_free(dn);
 				return -1;
 			}
 		}
 	}
 
+	talloc_free(dn);
 	return 0;
 }
 
@@ -979,6 +1021,7 @@ static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *
 {
 	struct ldb_module *module = state;
 	struct ldb_message *msg;
+	char *dn = NULL;
 	int ret;
 	TDB_DATA key2;
 
@@ -1003,7 +1046,9 @@ static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *
 	key2 = ltdb_key(module, msg->dn);
 	if (key2.dptr == NULL) {
 		/* probably a corrupt record ... darn */
-		ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Invalid DN in re_index: %s\n", msg->dn);
+		ldb_debug(module->ldb, LDB_DEBUG_ERROR, "Invalid DN in re_index: %s\n",
+							ldb_dn_linearize(msg, msg->dn));
+		talloc_free(msg);
 		return 0;
 	}
 	if (strcmp(key2.dptr, key.dptr) != 0) {
@@ -1012,11 +1057,13 @@ static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *
 	}
 	talloc_free(key2.dptr);
 
-	if (!msg->dn) {
-		msg->dn = key.dptr+3;
+	if (msg->dn == NULL) {
+		dn = key.dptr + 3;
+	} else {
+		dn = ldb_dn_linearize(msg->dn, msg->dn);
 	}
 
-	ret = ltdb_index_add(module, msg);
+	ret = ltdb_index_add0(module, dn, msg->elements, msg->num_elements);
 
 	talloc_free(msg);
 
diff --git a/source4/lib/ldb/ldb_tdb/ldb_pack.c b/source4/lib/ldb/ldb_tdb/ldb_pack.c
index 4433e16cb2..332dbf03df 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_pack.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_pack.c
@@ -74,9 +74,16 @@ int ltdb_pack_data(struct ldb_module *module,
 	struct ldb_context *ldb = module->ldb;
 	unsigned int i, j, real_elements=0;
 	size_t size;
+	char *dn;
 	char *p;
 	size_t len;
 
+	dn = ldb_dn_linearize(ldb, message->dn);
+	if (dn == NULL) {
+		errno = ENOMEM;
+		return -1;
+	}
+
 	for (i=0;i<message->num_elements;i++) {
 		if (message->elements[i].num_values != 0) {
 			real_elements++;
@@ -86,7 +93,7 @@ int ltdb_pack_data(struct ldb_module *module,
 	/* work out how big it needs to be */
 	size = 8;
 
-	size += 1 + strlen(message->dn);
+	size += 1 + strlen(dn);
 
 	for (i=0;i<message->num_elements;i++) {
 		if (message->elements[i].num_values == 0) {
@@ -101,6 +108,7 @@ int ltdb_pack_data(struct ldb_module *module,
 	/* allocate it */
 	data->dptr = talloc_array(ldb, char, size);
 	if (!data->dptr) {
+		talloc_free(dn);
 		errno = ENOMEM;
 		return -1;
 	}
@@ -113,8 +121,8 @@ int ltdb_pack_data(struct ldb_module *module,
 
 	/* the dn needs to be packed so we can be case preserving
 	   while hashing on a case folded dn */
-	len = strlen(message->dn);
-	memcpy(p, message->dn, len+1);
+	len = strlen(dn);
+	memcpy(p, dn, len+1);
 	p += len + 1;
 	
 	for (i=0;i<message->num_elements;i++) {
@@ -135,6 +143,7 @@ int ltdb_pack_data(struct ldb_module *module,
 		}
 	}
 
+	talloc_free(dn);
 	return 0;
 }
 
@@ -179,7 +188,11 @@ int ltdb_unpack_data(struct ldb_module *module,
 			errno = EIO;
 			goto failed;
 		}
-		message->dn = p;
+		message->dn = ldb_dn_explode(message, p);
+		if (message->dn == NULL) {
+			errno = ENOMEM;
+			goto failed;
+		}
 		remaining -= len + 1;
 		p += len + 1;
 		break;
diff --git a/source4/lib/ldb/ldb_tdb/ldb_search.c b/source4/lib/ldb/ldb_tdb/ldb_search.c
index 922d24b6eb..160affd4e7 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_search.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_search.c
@@ -94,7 +94,7 @@ static int msg_add_all_elements(struct ldb_module *module, struct ldb_message *r
 	for (i=0;i<msg->num_elements;i++) {
 		const struct ldb_attrib_handler *h;
 		h = ldb_attrib_handler(ldb, msg->elements[i].name);
-		if ((msg->dn[0] != '@') && (h->flags & LDB_ATTR_FLAG_HIDDEN)) {
+		if (ldb_dn_is_special(msg->dn) && (h->flags & LDB_ATTR_FLAG_HIDDEN)) {
 			continue;
 		}
 		if (msg_add_element(ldb, ret, &msg->elements[i]) != 0) {
@@ -122,7 +122,7 @@ static struct ldb_message *ltdb_pull_attrs(struct ldb_module *module,
 		return NULL;
 	}
 
-	ret->dn = talloc_strdup(ret, msg->dn);
+	ret->dn = ldb_dn_copy(ret, msg->dn);
 	if (!ret->dn) {
 		talloc_free(ret);
 		return NULL;
@@ -163,8 +163,8 @@ static struct ldb_message *ltdb_pull_attrs(struct ldb_module *module,
 			}
 			el2.num_values = 1;
 			el2.values = &val;
-			val.data = ret->dn;
-			val.length = strlen(ret->dn);
+			val.data = ldb_dn_linearize(ret, ret->dn);
+			val.length = strlen(val.data);
 
 			if (msg_add_element(ldb, ret, &el2) != 0) {
 				talloc_free(ret);
@@ -194,7 +194,7 @@ static struct ldb_message *ltdb_pull_attrs(struct ldb_module *module,
 
   return 1 on success, 0 on record-not-found and -1 on error
 */
-int ltdb_search_dn1(struct ldb_module *module, const char *dn, struct ldb_message *msg)
+int ltdb_search_dn1(struct ldb_module *module, const struct ldb_dn *dn, struct ldb_message *msg)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	int ret;
@@ -231,7 +231,7 @@ int ltdb_search_dn1(struct ldb_module *module, const char *dn, struct ldb_messag
 	}
 
 	if (!msg->dn) {
-		msg->dn = talloc_strdup(tdb_data2.dptr, dn);
+		msg->dn = ldb_dn_copy(tdb_data2.dptr, dn);
 	}
 	if (!msg->dn) {
 		talloc_free(tdb_data2.dptr);
@@ -245,7 +245,7 @@ int ltdb_search_dn1(struct ldb_module *module, const char *dn, struct ldb_messag
 /*
   search the database for a single simple dn
 */
-static int ltdb_search_dn(struct ldb_module *module, const char *dn,
+static int ltdb_search_dn(struct ldb_module *module, const struct ldb_dn *dn,
 			  const char * const attrs[], struct ldb_message ***res)
 {
 	struct ldb_context *ldb = module->ldb;
@@ -347,7 +347,7 @@ int ltdb_add_attr_results(struct ldb_module *module, struct ldb_message *msg,
 struct ltdb_search_info {
 	struct ldb_module *module;
 	struct ldb_parse_tree *tree;
-	const char *base;
+	const struct ldb_dn *base;
 	enum ldb_scope scope;
 	const char * const *attrs;
 	struct ldb_message **msgs;
@@ -384,7 +384,11 @@ static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, voi
 	}
 
 	if (!msg->dn) {
-		msg->dn = key.dptr + 3;
+		msg->dn = ldb_dn_explode(msg, key.dptr + 3);
+		if (msg->dn == NULL) {
+			talloc_free(msg);
+			return -1;
+		}
 	}
 
 	/* see if it matches the given expression */
@@ -411,7 +415,7 @@ static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, voi
   this is the "full search" non-indexed variant
 */
 static int ltdb_search_full(struct ldb_module *module, 
-			    const char *base,
+			    const struct ldb_dn *base,
 			    enum ldb_scope scope,
 			    struct ldb_parse_tree *tree,
 			    const char * const attrs[], struct ldb_message ***res)
@@ -454,7 +458,7 @@ static int ltdb_search_full(struct ldb_module *module,
   search the database with a LDAP-like expression.
   choses a search method
 */
-int ltdb_search_bytree(struct ldb_module *module, const char *base,
+int ltdb_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 		       enum ldb_scope scope, struct ldb_parse_tree *tree,
 		       const char * const attrs[], struct ldb_message ***res)
 {
@@ -466,7 +470,14 @@ int ltdb_search_bytree(struct ldb_module *module, const char *base,
 	if (tree->operation == LDB_OP_EQUALITY &&
 	    (ldb_attr_cmp(tree->u.equality.attr, "dn") == 0 ||
 	     ldb_attr_cmp(tree->u.equality.attr, "distinguishedName") == 0)) {
-		return ltdb_search_dn(module, tree->u.equality.value.data, attrs, res);
+		struct ldb_dn *dn;
+		dn = ldb_dn_explode(module->ldb, tree->u.equality.value.data);
+		if (dn == NULL) {
+			return -1;
+		}
+		ret = ltdb_search_dn(module, dn, attrs, res);
+		talloc_free(dn);
+		return ret;
 	}
 
 	if (ltdb_lock_read(module) != 0) {
@@ -497,7 +508,7 @@ int ltdb_search_bytree(struct ldb_module *module, const char *base,
   search the database with a LDAP-like expression.
   choses a search method
 */
-int ltdb_search(struct ldb_module *module, const char *base,
+int ltdb_search(struct ldb_module *module, const struct ldb_dn *base,
 		enum ldb_scope scope, const char *expression,
 		const char * const attrs[], struct ldb_message ***res)
 {
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.c b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
index 40cfe97c29..61d0f9b64a 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_tdb.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
@@ -50,14 +50,12 @@
   note that the key for a record can depend on whether the 
   dn refers to a case sensitive index record or not
 */
-struct TDB_DATA ltdb_key(struct ldb_module *module, const char *dn)
+struct TDB_DATA ltdb_key(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	struct ldb_context *ldb = module->ldb;
 	TDB_DATA key;
 	char *key_str = NULL;
 	char *dn_folded = NULL;
-	struct ldb_dn *edn = NULL;
-	struct ldb_dn *cedn = NULL;
 
 	/*
 	  most DNs are case insensitive. The exception is index DNs for
@@ -70,26 +68,14 @@ struct TDB_DATA ltdb_key(struct ldb_module *module, const char *dn)
 	  2) if the dn starts with @ then leave it alone - the indexing code handles
 	     the rest
 	*/
-	if (*dn == '@') {
-		dn_folded = talloc_strdup(ldb, dn);
-	} else {
-		edn = ldb_dn_explode(ldb, dn);
-		if (!edn)
-			goto failed;
-
-		cedn = ldb_dn_casefold(ldb, edn);
-		if (!cedn)
-			goto failed;
-
-                dn_folded = ldb_dn_linearize(ldb, cedn);
-		if (!dn_folded)
-			goto failed;
 
-		talloc_free(edn);
-		talloc_free(cedn);
+	dn_folded = ldb_dn_linearize_casefold(ldb, dn);
+	if (!dn_folded) {
+		goto failed;
 	}
 
 	key_str = talloc_asprintf(ldb, "DN=%s", dn_folded);
+
 	talloc_free(dn_folded);
 
 	if (!key_str) {
@@ -102,8 +88,6 @@ struct TDB_DATA ltdb_key(struct ldb_module *module, const char *dn)
 	return key;
 
 failed:
-	talloc_free(edn);
-	talloc_free(cedn);
 	errno = ENOMEM;
 	key.dptr = NULL;
 	key.dsize = 0;
@@ -116,7 +100,8 @@ failed:
 static int ltdb_lock(struct ldb_module *module, const char *lockname)
 {
 	struct ltdb_private *ltdb = module->private_data;
-	char *lock_dn;
+	struct ldb_dn *lock_dn;
+	char *ldn;
 	TDB_DATA key;
 	int ret;
 
@@ -124,10 +109,17 @@ static int ltdb_lock(struct ldb_module *module, const char *lockname)
 		return -1;
 	}
 
-	lock_dn = talloc_asprintf(module->ldb, "%s_%s", LDBLOCK, lockname);	
+	ldn = talloc_asprintf(module->ldb, "%s_%s", LDBLOCK, lockname);	
+	if (ldn == NULL) {
+		return -1;
+	}
+
+	lock_dn = ldb_dn_explode(module->ldb, ldn);
 	if (lock_dn == NULL) {
+		talloc_free(ldn);
 		return -1;
 	}
+	talloc_free(ldn);
 
 	key = ltdb_key(module, lock_dn);
 	if (!key.dptr) {
@@ -149,17 +141,25 @@ static int ltdb_lock(struct ldb_module *module, const char *lockname)
 static int ltdb_unlock(struct ldb_module *module, const char *lockname)
 {
 	struct ltdb_private *ltdb = module->private_data;
-	char *lock_dn;
+	struct ldb_dn *lock_dn;
+	char *ldn;
 	TDB_DATA key;
 
 	if (lockname == NULL) {
 		return -1;
 	}
 
-	lock_dn = talloc_asprintf(module->ldb, "%s_%s", LDBLOCK, lockname);	
+	ldn = talloc_asprintf(module->ldb, "%s_%s", LDBLOCK, lockname);	
+	if (ldn == NULL) {
+		return -1;
+	}
+
+	lock_dn = ldb_dn_explode(module->ldb, ldn);
 	if (lock_dn == NULL) {
+		talloc_free(ldn);
 		return -1;
 	}
+	talloc_free(ldn);
 
 	key = ltdb_key(module, lock_dn);
 	if (!key.dptr) {
@@ -183,11 +183,21 @@ int ltdb_lock_read(struct ldb_module *module)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	TDB_DATA key;
+	struct ldb_dn *lock_dn;
 	int ret;
-	key = ltdb_key(module, LDBLOCK);
+
+	lock_dn = ldb_dn_explode(module, LDBLOCK);
+	if (lock_dn == NULL) {
+		return -1;
+	}
+
+	key = ltdb_key(module, lock_dn);
 	if (!key.dptr) {
+		talloc_free(lock_dn);
 		return -1;
 	}
+	talloc_free(lock_dn);
+
 	ret = tdb_chainlock_read(ltdb->tdb, key);
 	talloc_free(key.dptr);
 	return ret;
@@ -199,11 +209,21 @@ int ltdb_lock_read(struct ldb_module *module)
 int ltdb_unlock_read(struct ldb_module *module)
 {
 	struct ltdb_private *ltdb = module->private_data;
+	struct ldb_dn *lock_dn;
 	TDB_DATA key;
-	key = ltdb_key(module, LDBLOCK);
+
+	lock_dn = ldb_dn_explode(module, LDBLOCK);
+	if (lock_dn == NULL) {
+		return -1;
+	}
+
+	key = ltdb_key(module, lock_dn);
 	if (!key.dptr) {
+		talloc_free(lock_dn);
 		return -1;
 	}
+	talloc_free(lock_dn);
+
 	tdb_chainunlock_read(ltdb->tdb, key);
 	talloc_free(key.dptr);
 	return 0;
@@ -217,8 +237,9 @@ int ltdb_check_special_dn(struct ldb_module *module, const struct ldb_message *m
 {
 	struct ltdb_private *ltdb = module->private_data;
 	int i, j;
-
-	if (strcmp(msg->dn, LTDB_ATTRIBUTES) != 0) {
+ 
+	if (! ldb_dn_is_special(msg->dn) ||
+	    ! ldb_dn_check_special(msg->dn, LTDB_ATTRIBUTES)) {
 		return 0;
 	}
 
@@ -241,17 +262,19 @@ int ltdb_check_special_dn(struct ldb_module *module, const struct ldb_message *m
   we've made a modification to a dn - possibly reindex and 
   update sequence number
 */
-static int ltdb_modified(struct ldb_module *module, const char *dn)
+static int ltdb_modified(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	int ret = 0;
 
-	if (strcmp(dn, LTDB_INDEXLIST) == 0 ||
-	    strcmp(dn, LTDB_ATTRIBUTES) == 0) {
+	if (ldb_dn_is_special(dn) &&
+	    (ldb_dn_check_special(dn, LTDB_INDEXLIST) ||
+	     ldb_dn_check_special(dn, LTDB_ATTRIBUTES)) ) {
 		ret = ltdb_reindex(module);
 	}
 
 	if (ret == 0 &&
-	    strcmp(dn, LTDB_BASEINFO) != 0) {
+	    !(ldb_dn_is_special(dn) &&
+	      ldb_dn_check_special(dn, LTDB_BASEINFO)) ) {
 		ret = ltdb_increase_sequence_number(module);
 	}
 
@@ -335,7 +358,7 @@ static int ltdb_add(struct ldb_module *module, const struct ldb_message *msg)
   delete a record from the database, not updating indexes (used for deleting
   index records)
 */
-int ltdb_delete_noindex(struct ldb_module *module, const char *dn)
+int ltdb_delete_noindex(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	TDB_DATA tdb_key;
@@ -355,7 +378,7 @@ int ltdb_delete_noindex(struct ldb_module *module, const char *dn)
 /*
   delete a record from the database
 */
-static int ltdb_delete(struct ldb_module *module, const char *dn)
+static int ltdb_delete(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	int ret;
@@ -477,12 +500,18 @@ static int msg_delete_attribute(struct ldb_module *module,
 				struct ldb_context *ldb,
 				struct ldb_message *msg, const char *name)
 {
+	char *dn;
 	unsigned int i, j;
 
+	dn = ldb_dn_linearize(ldb, msg->dn);
+	if (dn == NULL) {
+		return -1;
+	}
+
 	for (i=0;i<msg->num_elements;i++) {
 		if (ldb_attr_cmp(msg->elements[i].name, name) == 0) {
 			for (j=0;j<msg->elements[i].num_values;j++) {
-				ltdb_index_del_value(module, msg->dn, &msg->elements[i], j);
+				ltdb_index_del_value(module, dn, &msg->elements[i], j);
 			}
 			talloc_free(msg->elements[i].values);
 			if (msg->num_elements > (i+1)) {
@@ -499,6 +528,7 @@ static int msg_delete_attribute(struct ldb_module *module,
 		}
 	}
 
+	talloc_free(dn);
 	return 0;
 }
 
@@ -593,6 +623,7 @@ int ltdb_modify_internal(struct ldb_module *module, const struct ldb_message *ms
 		struct ldb_message_element *el = &msg->elements[i];
 		struct ldb_message_element *el2;
 		struct ldb_val *vals;
+		char *dn;
 
 		switch (msg->elements[i].flags & LDB_FLAG_MOD_MASK) {
 
@@ -650,6 +681,10 @@ int ltdb_modify_internal(struct ldb_module *module, const struct ldb_message *ms
 			break;
 
 		case LDB_FLAG_MOD_DELETE:
+
+			dn = ldb_dn_linearize(msg2, msg->dn);
+			if (dn == NULL) goto failed;
+
 			/* we could be being asked to delete all
 			   values or just some values */
 			if (msg->elements[i].num_values == 0) {
@@ -668,7 +703,7 @@ int ltdb_modify_internal(struct ldb_module *module, const struct ldb_message *ms
 					ltdb->last_err_string = "No such attribute";
 					goto failed;
 				}
-				if (ltdb_index_del_value(module, msg->dn, &msg->elements[i], j) != 0) {
+				if (ltdb_index_del_value(module, dn, &msg->elements[i], j) != 0) {
 					goto failed;
 				}
 			}
@@ -730,7 +765,7 @@ static int ltdb_modify(struct ldb_module *module, const struct ldb_message *msg)
 /*
   rename a record
 */
-static int ltdb_rename(struct ldb_module *module, const char *olddn, const char *newdn)
+static int ltdb_rename(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	int ret;
@@ -761,7 +796,7 @@ static int ltdb_rename(struct ldb_module *module, const char *olddn, const char
 		goto failed;
 	}
 
-	msg->dn = talloc_strdup(msg, newdn);
+	msg->dn = ldb_dn_copy(msg, newdn);
 	if (!msg->dn) {
 		goto failed;
 	}
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.h b/source4/lib/ldb/ldb_tdb/ldb_tdb.h
index 9ee3bfb70f..f08601832c 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_tdb.h
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.h
@@ -57,7 +57,7 @@ int ltdb_check_at_attributes_values(const struct ldb_val *value);
 struct ldb_parse_tree;
 
 int ltdb_search_indexed(struct ldb_module *module, 
-			const char *base,
+			const struct ldb_dn *base,
 			enum ldb_scope scope,
 			struct ldb_parse_tree *tree,
 			const char * const attrs[], struct ldb_message ***res);
@@ -81,23 +81,23 @@ int ltdb_unpack_data(struct ldb_module *module,
 int ltdb_has_wildcard(struct ldb_module *module, const char *attr_name, 
 		      const struct ldb_val *val);
 void ltdb_search_dn1_free(struct ldb_module *module, struct ldb_message *msg);
-int ltdb_search_dn1(struct ldb_module *module, const char *dn, struct ldb_message *msg);
+int ltdb_search_dn1(struct ldb_module *module, const struct ldb_dn *dn, struct ldb_message *msg);
 int ltdb_add_attr_results(struct ldb_module *module, struct ldb_message *msg,
 			  const char * const attrs[], 
 			  int *count, 
 			  struct ldb_message ***res);
-int ltdb_search(struct ldb_module *module, const char *base,
+int ltdb_search(struct ldb_module *module, const struct ldb_dn *base,
 		enum ldb_scope scope, const char *expression,
 		const char * const attrs[], struct ldb_message ***res);
-int ltdb_search_bytree(struct ldb_module *module, const char *base,
+int ltdb_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 		       enum ldb_scope scope, struct ldb_parse_tree *tree,
 		       const char * const attrs[], struct ldb_message ***res);
 
 
 /* The following definitions come from lib/ldb/ldb_tdb/ldb_tdb.c  */
-struct TDB_DATA ltdb_key(struct ldb_module *module, const char *dn);
+struct TDB_DATA ltdb_key(struct ldb_module *module, const struct ldb_dn *dn);
 int ltdb_store(struct ldb_module *module, const struct ldb_message *msg, int flgs);
-int ltdb_delete_noindex(struct ldb_module *module, const char *dn);
+int ltdb_delete_noindex(struct ldb_module *module, const struct ldb_dn *dn);
 int ltdb_modify_internal(struct ldb_module *module, const struct ldb_message *msg);
 int ltdb_lock_read(struct ldb_module *module);
 int ltdb_unlock_read(struct ldb_module *module);
diff --git a/source4/lib/ldb/modules/rdn_name.c b/source4/lib/ldb/modules/rdn_name.c
index 89cc49eb3e..d59205c6e4 100644
--- a/source4/lib/ldb/modules/rdn_name.c
+++ b/source4/lib/ldb/modules/rdn_name.c
@@ -41,7 +41,7 @@ struct private_data {
 	const char *error_string;
 };
 
-static int rdn_name_search(struct ldb_module *module, const char *base,
+static int rdn_name_search(struct ldb_module *module, const struct ldb_dn *base,
 				  enum ldb_scope scope, const char *expression,
 				  const char * const *attrs, struct ldb_message ***res)
 {
@@ -49,7 +49,7 @@ static int rdn_name_search(struct ldb_module *module, const char *base,
 	return ldb_next_search(module, base, scope, expression, attrs, res);
 }
 
-static int rdn_name_search_bytree(struct ldb_module *module, const char *base,
+static int rdn_name_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 				    enum ldb_scope scope, struct ldb_parse_tree *tree,
 				    const char * const *attrs, struct ldb_message ***res)
 {
@@ -70,21 +70,6 @@ static struct ldb_message_element *rdn_name_find_attribute(const struct ldb_mess
 	return NULL;
 }
 
-static struct ldb_dn_component *get_rdn(void *mem_ctx, const char *dn)
-{
-	struct ldb_dn *dn_exploded = ldb_dn_explode(mem_ctx, dn);
-
-	if (!dn_exploded) {
-		return NULL;
-	}
-	
-	if (dn_exploded->comp_num < 1) {
-		return NULL;
-	}
-	
-	return  &dn_exploded->components[0];
-}
-
 /* add_record: add crateTimestamp/modifyTimestamp attributes */
 static int rdn_name_add_record(struct ldb_module *module, const struct ldb_message *msg)
 {
@@ -97,7 +82,8 @@ static int rdn_name_add_record(struct ldb_module *module, const struct ldb_messa
 
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "rdn_name_add_record\n");
 
-	if (msg->dn[0] == '@') { /* do not manipulate our control entries */
+	/* do not manipulate our control entries */
+	if (ldb_dn_is_special(msg->dn)) {
 		return ldb_next_add_record(module, msg);
 	}
 
@@ -119,12 +105,14 @@ static int rdn_name_add_record(struct ldb_module *module, const struct ldb_messa
 		msg2->elements[i] = msg->elements[i];
 	}
 
-	rdn = get_rdn(msg2, msg2->dn);
+	rdn = ldb_dn_get_rdn(msg2, msg2->dn);
 	if (!rdn) {
+		talloc_free(msg2);
 		return -1;
 	}
 	
 	if (ldb_msg_add_value(module->ldb, msg2, "name", &rdn->value) != 0) {
+		talloc_free(msg2);
 		return -1;
 	}
 
@@ -132,6 +120,7 @@ static int rdn_name_add_record(struct ldb_module *module, const struct ldb_messa
 
 	if (!attribute) {
 		if (ldb_msg_add_value(module->ldb, msg2, rdn->name, &rdn->value) != 0) {
+			talloc_free(msg2);
 			return -1;
 		}
 	} else {
@@ -145,8 +134,9 @@ static int rdn_name_add_record(struct ldb_module *module, const struct ldb_messa
 			}
 		}
 		if (i == attribute->num_values) {
-			data->error_string = talloc_asprintf(data, "RDN mismatch on %s: %s", msg2->dn, rdn->name);
+			data->error_string = talloc_asprintf(data, "RDN mismatch on %s: %s", ldb_dn_linearize(msg2, msg2->dn), rdn->name);
 			ldb_debug(module->ldb, LDB_DEBUG_FATAL, "%s\n", data->error_string);
+			talloc_free(msg2);
 			return -1;
 		}
 	}
@@ -167,6 +157,11 @@ static int rdn_name_modify_record(struct ldb_module *module, const struct ldb_me
 
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "rdn_name_modify_record\n");
 
+	/* do not manipulate our control entries */
+	if (ldb_dn_is_special(msg->dn)) {
+		return ldb_next_add_record(module, msg);
+	}
+
 	/* Perhaps someone above us knows better */
 	if ((attribute = rdn_name_find_attribute(msg, "name")) != NULL ) {
 		return ldb_next_add_record(module, msg);
@@ -185,17 +180,20 @@ static int rdn_name_modify_record(struct ldb_module *module, const struct ldb_me
 		msg2->elements[i] = msg->elements[i];
 	}
 	
-	rdn = get_rdn(msg2, msg2->dn);
+	rdn = ldb_dn_get_rdn(msg2, msg2->dn);
 	if (!rdn) {
+		talloc_free(msg2);
 		return -1;
 	}
 	
 	if (ldb_msg_add_value(module->ldb, msg2, "name", &rdn->value) != 0) {
+		talloc_free(msg2);
 		return -1;
 	}
 
 	attribute = rdn_name_find_attribute(msg2, "name");
 	if (!attribute) {
+		talloc_free(msg2);
 		return -1;
 	}
 
@@ -207,13 +205,13 @@ static int rdn_name_modify_record(struct ldb_module *module, const struct ldb_me
 	return ret;
 }
 
-static int rdn_name_delete_record(struct ldb_module *module, const char *dn)
+static int rdn_name_delete_record(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "rdn_name_delete_record\n");
 	return ldb_next_delete_record(module, dn);
 }
 
-static int rdn_name_rename_record(struct ldb_module *module, const char *olddn, const char *newdn)
+static int rdn_name_rename_record(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "rdn_name_rename_record\n");
 	return ldb_next_rename_record(module, olddn, newdn);
diff --git a/source4/lib/ldb/modules/schema.c b/source4/lib/ldb/modules/schema.c
index e11c8b4e4e..baf038de0c 100644
--- a/source4/lib/ldb/modules/schema.c
+++ b/source4/lib/ldb/modules/schema.c
@@ -1,7 +1,7 @@
 /* 
    ldb database library
 
-   Copyright (C) Simo Sorce  2004
+   Copyright (C) Simo Sorce  2004-2005
 
      ** NOTE! The following LGPL license applies to the ldb
      ** library. This does NOT imply that all of Samba is released
@@ -72,28 +72,6 @@ struct schema_structures {
 	struct schema_attribute_list optional_attrs;
 };
 
-/* This function embedds the knowledge of aliased names.
-   Currently it handles only dn vs distinguishedNAme as a special case as AD
-   only have this special alias case, in future we should read the schema
-   to find out which names have an alias and check for them */
-static int schema_attr_cmp(const char *attr1, const char *attr2)
-{
-	int ret;
-
-	ret = ldb_attr_cmp(attr1, attr2);
-	if (ret != 0) {
-		if ((ldb_attr_cmp("dn", attr1) == 0) &&
-		    (ldb_attr_cmp("distinguishedName", attr2) == 0)) {
-			return 0;
-		}
-		if ((ldb_attr_cmp("dn", attr2) == 0) &&
-		    (ldb_attr_cmp("distinguishedName", attr1) == 0)) {
-			return 0;
-		}
-	}
-	return ret;
-}
-
 static struct schema_attribute *schema_find_attribute(struct schema_attribute_list *list, const char *attr_name)
 {
 	unsigned int i;
@@ -110,7 +88,7 @@ static struct schema_attribute *schema_find_attribute(struct schema_attribute_li
    objectclasses go in the objectclasses structure */
 static int get_msg_attributes(struct schema_structures *ss, const struct ldb_message *msg, int flag_mask)
 {
-	int i, j, k, l;
+	int i, j, anum, cnum;
 
 	ss->entry_attrs.attr = talloc_realloc(ss, ss->entry_attrs.attr,
 					      struct schema_attribute,
@@ -119,9 +97,9 @@ static int get_msg_attributes(struct schema_structures *ss, const struct ldb_mes
 		return -1;
 	}
 
-	for (i = 0, j = ss->entry_attrs.num; i < msg->num_elements; i++) {
+	for (i = 0, anum = ss->entry_attrs.num; i < msg->num_elements; i++) {
 
-		if (schema_attr_cmp(msg->elements[i].name, "objectclass") == 0) {
+		if (ldb_attr_cmp(msg->elements[i].name, "objectclass") == 0) {
 
 			ss->objectclasses.attr = talloc_realloc(ss, ss->objectclasses.attr,
 								struct schema_attribute,
@@ -130,34 +108,33 @@ static int get_msg_attributes(struct schema_structures *ss, const struct ldb_mes
 				return -1;
 			}
 
-			for (k = 0, l = ss->objectclasses.num; k < msg->elements[i].num_values; k++) {
-				ss->objectclasses.attr[l].name = msg->elements[i].values[k].data;
-				ss->objectclasses.attr[l].flags = msg->elements[i].flags & flag_mask;
-				l++;
+			for (j = 0, cnum = ss->objectclasses.num; j < msg->elements[i].num_values; j++) {
+				ss->objectclasses.attr[cnum+j].name = msg->elements[i].values[j].data;
+				ss->objectclasses.attr[cnum+j].flags = msg->elements[i].flags & flag_mask;
 			}
 			ss->objectclasses.num += msg->elements[i].num_values;
 		}
 
-		ss->entry_attrs.attr[j].flags = msg->elements[i].flags & flag_mask;
-		ss->entry_attrs.attr[j].name = talloc_reference(ss->entry_attrs.attr,
+		/* TODO: Check for proper attribute Syntax ! */
+
+		ss->entry_attrs.attr[anum+i].flags = msg->elements[i].flags & flag_mask;
+		ss->entry_attrs.attr[anum+i].name = talloc_reference(ss->entry_attrs.attr,
 							    msg->elements[i].name);
-		if (ss->entry_attrs.attr[j].name == NULL) {
+		if (ss->entry_attrs.attr[anum+i].name == NULL) {
 			return -1;
 		}
-		j++;
 	}
 	ss->entry_attrs.num += msg->num_elements;
 
 	return 0;
 }
 
-static int get_entry_attributes(struct ldb_context *ldb, const char *dn, struct schema_structures *ss)
+static int get_entry_attributes(struct ldb_context *ldb, const struct ldb_dn *dn, struct schema_structures *ss)
 {
-	char *filter = talloc_asprintf(ss, "dn=%s", dn);
 	struct ldb_message **srch;
 	int ret;
 
-	ret = ldb_search(ldb, NULL, LDB_SCOPE_SUBTREE, filter, NULL, &srch);
+	ret = ldb_search(ldb, dn, LDB_SCOPE_BASE, NULL, NULL, &srch);
 	if (ret != 1) {
 		return ret;
 	}
@@ -190,7 +167,7 @@ static int add_attribute_uniq(void *mem_ctx, struct schema_attribute_list *list,
 		for (c = 0; c < list->num; c++) {
 			len = strlen(list->attr[c].name);
 			if (len == el->values[i].length) {
-				if (schema_attr_cmp(list->attr[c].name, el->values[i].data) == 0) {
+				if (ldb_attr_cmp(list->attr[c].name, el->values[i].data) == 0) {
 					found = 1;
 					break;
 				}
@@ -254,11 +231,15 @@ static int get_attr_list_recursive(struct ldb_module *module, struct schema_stru
 
 			is_aux = 0;
 			is_class = 0;
-			if (schema_attr_cmp((*srch)->elements[j].name, "systemAuxiliaryclass") == 0) {
+			if (ldb_attr_cmp((*srch)->elements[j].name, "systemAuxiliaryclass") == 0) {
 				is_aux = SCHEMA_FLAG_AUXILIARY;
 				is_class = 1;
 			}
-			if (schema_attr_cmp((*srch)->elements[j].name, "subClassOf") == 0) {
+			if (ldb_attr_cmp((*srch)->elements[j].name, "auxiliaryClass") == 0) {
+				is_aux = SCHEMA_FLAG_AUXILIARY;
+				is_class = 1;
+			}
+			if (ldb_attr_cmp((*srch)->elements[j].name, "subClassOf") == 0) {
 				is_class = 1;
 			}
 
@@ -271,8 +252,8 @@ static int get_attr_list_recursive(struct ldb_module *module, struct schema_stru
 				}
 			} else {
 
-				if (schema_attr_cmp((*srch)->elements[j].name, "mustContain") == 0 ||
-					schema_attr_cmp((*srch)->elements[j].name, "SystemMustContain") == 0) {
+				if (ldb_attr_cmp((*srch)->elements[j].name, "mustContain") == 0 ||
+					ldb_attr_cmp((*srch)->elements[j].name, "SystemMustContain") == 0) {
 					if (add_attribute_uniq(schema_struct,
 								&schema_struct->required_attrs,
 								SCHEMA_FLAG_RESET,
@@ -281,8 +262,8 @@ static int get_attr_list_recursive(struct ldb_module *module, struct schema_stru
 					}
 				}
 
-				if (schema_attr_cmp((*srch)->elements[j].name, "mayContain") == 0 ||
-				    schema_attr_cmp((*srch)->elements[j].name, "SystemMayContain") == 0) {
+				if (ldb_attr_cmp((*srch)->elements[j].name, "mayContain") == 0 ||
+				    ldb_attr_cmp((*srch)->elements[j].name, "SystemMayContain") == 0) {
 
 					if (add_attribute_uniq(schema_struct,
 								&schema_struct->optional_attrs,
@@ -299,14 +280,14 @@ static int get_attr_list_recursive(struct ldb_module *module, struct schema_stru
 }
 
 /* search */
-static int schema_search(struct ldb_module *module, const char *base,
+static int schema_search(struct ldb_module *module, const struct ldb_dn *base,
 		       enum ldb_scope scope, const char *expression,
 		       const char * const *attrs, struct ldb_message ***res)
 {
 	return ldb_next_search(module, base, scope, expression, attrs, res); 
 }
 
-static int schema_search_bytree(struct ldb_module *module, const char *base,
+static int schema_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 				enum ldb_scope scope, struct ldb_parse_tree *tree,
 				const char * const *attrs, struct ldb_message ***res)
 {
@@ -329,10 +310,13 @@ static int schema_add_record(struct ldb_module *module, const struct ldb_message
 		Free all structures and commit the change
 	*/
 
-	if (msg->dn[0] == '@') { /* do not check on our control entries */
+	/* do not check on our control entries */
+	if (ldb_dn_is_special(msg->dn)) {
 		return ldb_next_add_record(module, msg);
 	}
 
+	/* TODO: check parent exists */
+
 	entry_structs = talloc_zero(module, struct schema_structures);
 	if (!entry_structs) {
 		return -1;
@@ -414,8 +398,9 @@ static int schema_modify_record(struct ldb_module *module, const struct ldb_mess
 		Free all structures and commit the change.
 	*/
 
-	if (msg->dn[0] == '@') { /* do not check on our control entries */
-		return ldb_next_modify_record(module, msg);
+	/* do not check on our control entries */
+	if (ldb_dn_is_special(msg->dn)) {
+		return ldb_next_add_record(module, msg);
 	}
 
 	/* allocate object structs */
@@ -504,14 +489,14 @@ static int schema_modify_record(struct ldb_module *module, const struct ldb_mess
 }
 
 /* delete_record */
-static int schema_delete_record(struct ldb_module *module, const char *dn)
+static int schema_delete_record(struct ldb_module *module, const struct ldb_dn *dn)
 {
 /*	struct private_data *data = (struct private_data *)module->private_data; */
 	return ldb_next_delete_record(module, dn);
 }
 
 /* rename_record */
-static int schema_rename_record(struct ldb_module *module, const char *olddn, const char *newdn)
+static int schema_rename_record(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
 	return ldb_next_rename_record(module, olddn, newdn);
 }
diff --git a/source4/lib/ldb/modules/skel.c b/source4/lib/ldb/modules/skel.c
index 1221ac70f1..57c89a6a65 100644
--- a/source4/lib/ldb/modules/skel.c
+++ b/source4/lib/ldb/modules/skel.c
@@ -42,7 +42,7 @@ struct private_data {
 };
 
 /* search */
-static int skel_search(struct ldb_module *module, const char *base,
+static int skel_search(struct ldb_module *module, const struct ldb_dn *base,
 		       enum ldb_scope scope, const char *expression,
 		       const char * const *attrs, struct ldb_message ***res)
 {
@@ -62,13 +62,13 @@ static int skel_modify_record(struct ldb_module *module, const struct ldb_messag
 }
 
 /* delete_record */
-static int skel_delete_record(struct ldb_module *module, const char *dn)
+static int skel_delete_record(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	return ldb_next_delete_record(module, dn);
 }
 
 /* rename_record */
-static int skel_rename_record(struct ldb_module *module, const char *olddn, const char *newdn)
+static int skel_rename_record(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
 	return ldb_next_rename_record(module, olddn, newdn);
 }
diff --git a/source4/lib/ldb/modules/timestamps.c b/source4/lib/ldb/modules/timestamps.c
index b067d8e8d6..4819e0466b 100644
--- a/source4/lib/ldb/modules/timestamps.c
+++ b/source4/lib/ldb/modules/timestamps.c
@@ -41,7 +41,7 @@ struct private_data {
 	const char *error_string;
 };
 
-static int timestamps_search(struct ldb_module *module, const char *base,
+static int timestamps_search(struct ldb_module *module, const struct ldb_dn *base,
 				  enum ldb_scope scope, const char *expression,
 				  const char * const *attrs, struct ldb_message ***res)
 {
@@ -49,7 +49,7 @@ static int timestamps_search(struct ldb_module *module, const char *base,
 	return ldb_next_search(module, base, scope, expression, attrs, res);
 }
 
-static int timestamps_search_bytree(struct ldb_module *module, const char *base,
+static int timestamps_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 				    enum ldb_scope scope, struct ldb_parse_tree *tree,
 				    const char * const *attrs, struct ldb_message ***res)
 {
@@ -101,7 +101,8 @@ static int timestamps_add_record(struct ldb_module *module, const struct ldb_mes
 
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "timestamps_add_record\n");
 
-	if (msg->dn[0] == '@') { /* do not manipulate our control entries */
+	/* do not manipulate our control entries */
+	if (ldb_dn_is_special(msg->dn)) {
 		return ldb_next_add_record(module, msg);
 	}
 
@@ -159,8 +160,9 @@ static int timestamps_modify_record(struct ldb_module *module, const struct ldb_
 
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "timestamps_modify_record\n");
 
-	if (msg->dn[0] == '@') { /* do not manipulate our control entries */
-		return ldb_next_modify_record(module, msg);
+	/* do not manipulate our control entries */
+	if (ldb_dn_is_special(msg->dn)) {
+		return ldb_next_add_record(module, msg);
 	}
 
 	timeval = time(NULL);
@@ -201,13 +203,13 @@ static int timestamps_modify_record(struct ldb_module *module, const struct ldb_
 	return ret;
 }
 
-static int timestamps_delete_record(struct ldb_module *module, const char *dn)
+static int timestamps_delete_record(struct ldb_module *module, const struct ldb_dn *dn)
 {
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "timestamps_delete_record\n");
 	return ldb_next_delete_record(module, dn);
 }
 
-static int timestamps_rename_record(struct ldb_module *module, const char *olddn, const char *newdn)
+static int timestamps_rename_record(struct ldb_module *module, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
 {
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "timestamps_rename_record\n");
 	return ldb_next_rename_record(module, olddn, newdn);
diff --git a/source4/lib/ldb/tools/cmdline.c b/source4/lib/ldb/tools/cmdline.c
index 48dc8ddd47..7657301f35 100644
--- a/source4/lib/ldb/tools/cmdline.c
+++ b/source4/lib/ldb/tools/cmdline.c
@@ -57,6 +57,8 @@ struct ldb_cmdline *ldb_cmdline_process(struct ldb_context *ldb, int argc, const
 		{ "all", 'a',    POPT_ARG_NONE, &options.all_records, 0, "dn=*", NULL },
 		{ "sorted", 'S', POPT_ARG_NONE, &options.sorted, 0, "sort attributes", NULL },
 		{ "sasl-mechanism", 0, POPT_ARG_STRING, &options.sasl_mechanism, 0, "choose SASL mechanism", "MECHANISM" },
+		{ "input", 'I', POPT_ARG_STRING, &options.input, 0, "Input File", "Input" },
+		{ "output", 'O', POPT_ARG_STRING, &options.output, 0, "Output File", "Output" },
 		{ NULL,    'o', POPT_ARG_STRING, NULL, 'o', "ldb_connect option", "OPTION" },
 #ifdef _SAMBA_BUILD_
 		POPT_COMMON_SAMBA
@@ -149,16 +151,18 @@ struct ldb_cmdline *ldb_cmdline_process(struct ldb_context *ldb, int argc, const
 	*ret = options;
 
 	/* all utils need some option */
-	if (ret->url == NULL) {
-		fprintf(stderr, "You must supply a url with -H or with $LDB_URL\n");
-		if (usage) usage();
-		goto failed;
-	}
+	if (ldb) {
+		if (ret->url == NULL) {
+			fprintf(stderr, "You must supply a url with -H or with $LDB_URL\n");
+			if (usage) usage();
+			goto failed;
+		}
 
-	if (ldb_connect(ldb, ret->url, 0, ret->options) != 0) {
-		fprintf(stderr, "Failed to connect to %s - %s\n", 
-			ret->url, ldb_errstring(ldb));
-		goto failed;
+		if (ldb_connect(ldb, ret->url, 0, ret->options) != 0) {
+			fprintf(stderr, "Failed to connect to %s - %s\n", 
+				ret->url, ldb_errstring(ldb));
+			goto failed;
+		}
 	}
 
 	return ret;
diff --git a/source4/lib/ldb/tools/cmdline.h b/source4/lib/ldb/tools/cmdline.h
index 8e479c5538..daf9c06f42 100644
--- a/source4/lib/ldb/tools/cmdline.h
+++ b/source4/lib/ldb/tools/cmdline.h
@@ -40,6 +40,8 @@ struct ldb_cmdline {
 	int num_records;
 	int num_searches;
 	const char *sasl_mechanism;
+	const char *input;
+	const char *output;
 };
 
 struct ldb_cmdline *ldb_cmdline_process(struct ldb_context *ldb, int argc, const char **argv,
diff --git a/source4/lib/ldb/tools/ldbadd.c b/source4/lib/ldb/tools/ldbadd.c
index 5be3b7fc75..de6da0eb5b 100644
--- a/source4/lib/ldb/tools/ldbadd.c
+++ b/source4/lib/ldb/tools/ldbadd.c
@@ -76,7 +76,7 @@ static int process_file(struct ldb_context *ldb, FILE *f)
 		ret = ldb_add(ldb, ldif->msg);
 		if (ret != 0) {
 			fprintf(stderr, "ERR: \"%s\" on DN %s\n", 
-				ldb_errstring(ldb), ldif->msg->dn);
+				ldb_errstring(ldb), ldb_dn_linearize(ldb, ldif->msg->dn));
 			failures++;
 		} else {
 			count++;
diff --git a/source4/lib/ldb/tools/ldbdel.c b/source4/lib/ldb/tools/ldbdel.c
index fdb1f7ef3b..6082931e22 100644
--- a/source4/lib/ldb/tools/ldbdel.c
+++ b/source4/lib/ldb/tools/ldbdel.c
@@ -41,7 +41,7 @@
 #include "system/filesys.h"
 #endif
 
-static int ldb_delete_recursive(struct ldb_context *ldb, const char *dn)
+static int ldb_delete_recursive(struct ldb_context *ldb, const struct ldb_dn *dn)
 {
 	int ret, i, total=0;
 	const char *attrs[] = { "dn", NULL };
@@ -94,7 +94,13 @@ static void usage(void)
 	}
 
 	for (i=0;i<options->argc;i++) {
-		const char *dn = options->argv[i];
+		const struct ldb_dn *dn;
+
+		dn = ldb_dn_explode(ldb, options->argv[i]);
+		if (dn == NULL) {
+			printf("Invalid DN format\n");
+			exit(1);
+		}
 		if (options->recursive) {
 			ret = ldb_delete_recursive(ldb, dn);
 		} else {
@@ -104,7 +110,9 @@ static void usage(void)
 			}
 		}
 		if (ret != 0) {
-			printf("delete of '%s' failed - %s\n", dn, ldb_errstring(ldb));
+			printf("delete of '%s' failed - %s\n",
+				ldb_dn_linearize(ldb, dn),
+				ldb_errstring(ldb));
 		}
 	}
 
diff --git a/source4/lib/ldb/tools/ldbedit.c b/source4/lib/ldb/tools/ldbedit.c
index 1613f4ddc5..a850562a7d 100644
--- a/source4/lib/ldb/tools/ldbedit.c
+++ b/source4/lib/ldb/tools/ldbedit.c
@@ -83,7 +83,7 @@ static int modify_record(struct ldb_context *ldb,
 
 	if (ldb_modify(ldb, mod) != 0) {
 		fprintf(stderr, "failed to modify %s - %s\n", 
-			msg1->dn, ldb_errstring(ldb));
+			ldb_dn_linearize(ldb, msg1->dn), ldb_errstring(ldb));
 		return -1;
 	}
 
@@ -96,11 +96,11 @@ static int modify_record(struct ldb_context *ldb,
 static struct ldb_message *msg_find(struct ldb_context *ldb,
 				    struct ldb_message **msgs,
 				    int count,
-				    const char *dn)
+				    const struct ldb_dn *dn)
 {
 	int i;
 	for (i=0;i<count;i++) {
-		if (ldb_dn_cmp(ldb, dn, msgs[i]->dn) == 0) {
+		if (ldb_dn_compare(ldb, dn, msgs[i]->dn) == 0) {
 			return msgs[i];
 		}
 	}
@@ -128,7 +128,8 @@ static int merge_edits(struct ldb_context *ldb,
 			}
 			if (ldb_add(ldb, msgs2[i]) != 0) {
 				fprintf(stderr, "failed to add %s - %s\n",
-					msgs2[i]->dn, ldb_errstring(ldb));
+					ldb_dn_linearize(ldb, msgs2[i]->dn),
+					ldb_errstring(ldb));
 				return -1;
 			}
 			adds++;
@@ -148,7 +149,8 @@ static int merge_edits(struct ldb_context *ldb,
 			}
 			if (ldb_delete(ldb, msgs1[i]->dn) != 0) {
 				fprintf(stderr, "failed to delete %s - %s\n",
-					msgs1[i]->dn, ldb_errstring(ldb));
+					ldb_dn_linearize(ldb, msgs1[i]->dn),
+					ldb_errstring(ldb));
 				return -1;
 			}
 			deletes++;
@@ -279,6 +281,7 @@ static void usage(void)
 {
 	struct ldb_context *ldb;
 	struct ldb_message **msgs;
+	struct ldb_dn *basedn = NULL;
 	int ret;
 	const char *expression = "(|(objectclass=*)(dn=*))";
 	const char * const * attrs = NULL;
@@ -299,7 +302,15 @@ static void usage(void)
 		attrs = (const char * const *)(options->argv);
 	}
 
-	ret = ldb_search(ldb, options->basedn, options->scope, expression, attrs, &msgs);
+	if (options->basedn != NULL) {
+		basedn = ldb_dn_explode(ldb, options->basedn);
+		if (basedn == NULL) {
+			printf("Invalid Base DN format\n");
+			exit(1);
+		}
+	}
+
+	ret = ldb_search(ldb, basedn, options->scope, expression, attrs, &msgs);
 	if (ret == -1) {
 		printf("search failed - %s\n", ldb_errstring(ldb));
 		exit(1);
diff --git a/source4/lib/ldb/tools/ldbmodify.c b/source4/lib/ldb/tools/ldbmodify.c
index 901a4c9628..4c78e485b5 100644
--- a/source4/lib/ldb/tools/ldbmodify.c
+++ b/source4/lib/ldb/tools/ldbmodify.c
@@ -78,7 +78,7 @@ static int process_file(struct ldb_context *ldb, FILE *f)
 		}
 		if (ret != 0) {
 			fprintf(stderr, "ERR: \"%s\" on DN %s\n", 
-				ldb_errstring(ldb), ldif->msg->dn);
+				ldb_errstring(ldb), ldb_dn_linearize(ldb, ldif->msg->dn));
 			failures++;
 		} else {
 			count++;
diff --git a/source4/lib/ldb/tools/ldbrename.c b/source4/lib/ldb/tools/ldbrename.c
index c74516869e..4b3b27c130 100644
--- a/source4/lib/ldb/tools/ldbrename.c
+++ b/source4/lib/ldb/tools/ldbrename.c
@@ -61,7 +61,7 @@ static void usage(void)
 	struct ldb_context *ldb;
 	int ret;
 	struct ldb_cmdline *options;
-	const char *dn1, *dn2;
+	const struct ldb_dn *dn1, *dn2;
 
 	ldb = ldb_init(NULL);
 
@@ -71,15 +71,15 @@ static void usage(void)
 		usage();
 	}
 
-	dn1 = options->argv[0];
-	dn2 = options->argv[1];
+	dn1 = ldb_dn_explode(ldb, options->argv[0]);
+	dn2 = ldb_dn_explode(ldb, options->argv[1]);
 
 	ret = ldb_rename(ldb, dn1, dn2);
 	if (ret == 0) {
 		printf("Renamed 1 record\n");
 	} else  {
 		printf("rename of '%s' to '%s' failed - %s\n", 
-			dn1, dn2, ldb_errstring(ldb));
+			options->argv[0], options->argv[1], ldb_errstring(ldb));
 	}
 
 	talloc_free(ldb);
diff --git a/source4/lib/ldb/tools/ldbsearch.c b/source4/lib/ldb/tools/ldbsearch.c
index 5604436980..4499bc9359 100644
--- a/source4/lib/ldb/tools/ldbsearch.c
+++ b/source4/lib/ldb/tools/ldbsearch.c
@@ -60,11 +60,11 @@ struct ldb_context *ldbsearch_ldb;
 static int do_compare_msg(struct ldb_message **el1,
 			  struct ldb_message **el2)
 {
-	return ldb_dn_cmp(ldbsearch_ldb, (*el1)->dn, (*el2)->dn);
+	return ldb_dn_compare(ldbsearch_ldb, (*el1)->dn, (*el2)->dn);
 }
 
 static int do_search(struct ldb_context *ldb,
-		     const char *basedn,
+		     const struct ldb_dn *basedn,
 		     int scope,
                      int sort_attribs,
 		     const char *expression,
@@ -120,6 +120,7 @@ static int do_search(struct ldb_context *ldb,
  int main(int argc, const char **argv)
 {
 	struct ldb_context *ldb;
+	struct ldb_dn *basedn = NULL;
 	const char * const * attrs = NULL;
 	struct ldb_cmdline *options;
 	int ret = -1;
@@ -142,16 +143,24 @@ static int do_search(struct ldb_context *ldb,
 		attrs = (const char * const *)(options->argv);
 	}
 
+	if (options->basedn != NULL) {
+		basedn = ldb_dn_explode(ldb, options->basedn);
+		if (basedn == NULL) {
+			fprintf(stderr, "Invalid Base DN format\n");
+			exit(1);
+		}
+	}
+
 	if (options->interactive) {
 		char line[1024];
 		while (fgets(line, sizeof(line), stdin)) {
-			if (do_search(ldb, options->basedn, 
+			if (do_search(ldb, basedn, 
 				      options->scope, options->sorted, line, attrs) == -1) {
 				ret = -1;
 			}
 		}
 	} else {
-		ret = do_search(ldb, options->basedn, options->scope, options->sorted, 
+		ret = do_search(ldb, basedn, options->scope, options->sorted, 
 				expression, attrs);
 	}
 
diff --git a/source4/lib/ldb/tools/ldbtest.c b/source4/lib/ldb/tools/ldbtest.c
index aff1eaadda..a2e824dcdb 100644
--- a/source4/lib/ldb/tools/ldbtest.c
+++ b/source4/lib/ldb/tools/ldbtest.c
@@ -58,7 +58,7 @@ static double _end_timer(void)
 }
 
 static void add_records(struct ldb_context *ldb,
-			const char *basedn,
+			const struct ldb_dn *basedn,
 			int count)
 {
 	struct ldb_message msg;
@@ -77,7 +77,7 @@ static void add_records(struct ldb_context *ldb,
 
 		asprintf(&name, "Test%d", i);
 
-		msg.dn = talloc_asprintf(tmp_ctx, "cn=%s,%s", name, basedn);
+		msg.dn = ldb_dn_build_child(tmp_ctx, "cn", name, basedn);
 		msg.num_elements = 6;
 		msg.elements = el;
 
@@ -145,7 +145,7 @@ static void add_records(struct ldb_context *ldb,
 }
 
 static void modify_records(struct ldb_context *ldb,
-			   const char *basedn,
+			   const struct ldb_dn *basedn,
 			   int count)
 {
 	struct ldb_message msg;
@@ -158,7 +158,7 @@ static void modify_records(struct ldb_context *ldb,
 		TALLOC_CTX *tmp_ctx = talloc_new(ldb);
 		
 		name = talloc_asprintf(tmp_ctx, "Test%d", i);
-		msg.dn = talloc_asprintf(tmp_ctx, "cn=%s,%s", name, basedn);
+		msg.dn = ldb_dn_build_child(tmp_ctx, "cn", name, basedn);
 
 		msg.num_elements = 3;
 		msg.elements = el;
@@ -197,29 +197,30 @@ static void modify_records(struct ldb_context *ldb,
 
 
 static void delete_records(struct ldb_context *ldb,
-			   const char *basedn,
+			   const struct ldb_dn *basedn,
 			   int count)
 {
 	int i;
 
 	for (i=0;i<count;i++) {
-		char *dn;
-		asprintf(&dn, "cn=Test%d,%s", i, basedn);
+		struct ldb_dn *dn;
+		char *name = talloc_asprintf(ldb, "Test%d", i);
+		dn = ldb_dn_build_child(name, "cn", name, basedn);
 
 		printf("Deleting uid Test%d\r", i);
 		fflush(stdout);
 
 		if (ldb_delete(ldb, dn) != 0) {
-			printf("Delete of %s failed - %s\n", dn, ldb_errstring(ldb));
+			printf("Delete of %s failed - %s\n", ldb_dn_linearize(ldb, dn), ldb_errstring(ldb));
 			exit(1);
 		}
-		free(dn);
+		talloc_free(name);
 	}
 
 	printf("\n");
 }
 
-static void search_uid(struct ldb_context *ldb, int nrecords, int nsearches)
+static void search_uid(struct ldb_context *ldb, struct ldb_dn *basedn, int nrecords, int nsearches)
 {
 	int i;
 
@@ -230,7 +231,7 @@ static void search_uid(struct ldb_context *ldb, int nrecords, int nsearches)
 		int ret;
 
 		asprintf(&expr, "(uid=TEST%d)", uid);
-		ret = ldb_search(ldb, options->basedn, LDB_SCOPE_SUBTREE, expr, NULL, &res);
+		ret = ldb_search(ldb, basedn, LDB_SCOPE_SUBTREE, expr, NULL, &res);
 
 		if (uid < nrecords && ret != 1) {
 			printf("Failed to find %s - %s\n", expr, ldb_errstring(ldb));
@@ -257,19 +258,23 @@ static void search_uid(struct ldb_context *ldb, int nrecords, int nsearches)
 
 static void start_test(struct ldb_context *ldb, int nrecords, int nsearches)
 {
+	struct ldb_dn *basedn;
+
+	basedn = ldb_dn_explode(ldb, options->basedn);
+
 	printf("Adding %d records\n", nrecords);
-	add_records(ldb, options->basedn, nrecords);
+	add_records(ldb, basedn, nrecords);
 
 	printf("Starting search on uid\n");
 	_start_timer();
-	search_uid(ldb, nrecords, nsearches);
+	search_uid(ldb, basedn, nrecords, nsearches);
 	printf("uid search took %.2f seconds\n", _end_timer());
 
 	printf("Modifying records\n");
-	modify_records(ldb, options->basedn, nrecords);
+	modify_records(ldb, basedn, nrecords);
 
 	printf("Deleting records\n");
-	delete_records(ldb, options->basedn, nrecords);
+	delete_records(ldb, basedn, nrecords);
 }
 
 
@@ -290,31 +295,37 @@ static void start_test_index(struct ldb_context **ldb)
 {
 	struct ldb_message *msg;
 	struct ldb_message **res;
+	struct ldb_dn *indexlist;
+	struct ldb_dn *basedn;
 	int ret;
 
 	printf("Starting index test\n");
 
-	ldb_delete(*ldb, "@INDEXLIST");
+	indexlist = ldb_dn_explode(NULL, "@INDEXLIST");
+
+	ldb_delete(*ldb, indexlist);
 
 	msg = ldb_msg_new(NULL);
 
-	msg->dn = strdup("@INDEXLIST");
+	msg->dn = indexlist;
 	ldb_msg_add_string(*ldb, msg, "@IDXATTR", strdup("uid"));
 
 	if (ldb_add(*ldb, msg) != 0) {
-		printf("Add of %s failed - %s\n", msg->dn, ldb_errstring(*ldb));
+		printf("Add of %s failed - %s\n", ldb_dn_linearize(*ldb, msg->dn), ldb_errstring(*ldb));
 		exit(1);
 	}
 
+	basedn = ldb_dn_explode(NULL, options->basedn);
+
 	memset(msg, 0, sizeof(*msg));
-	asprintf(&msg->dn, "cn=%s,%s", "test", options->basedn);
+	msg->dn = ldb_dn_build_child(msg, "cn", "test", basedn);
 	ldb_msg_add_string(*ldb, msg, "cn", strdup("test"));
 	ldb_msg_add_string(*ldb, msg, "sn", strdup("test"));
 	ldb_msg_add_string(*ldb, msg, "uid", strdup("test"));
 	ldb_msg_add_string(*ldb, msg, "objectClass", strdup("OpenLDAPperson"));
 
 	if (ldb_add(*ldb, msg) != 0) {
-		printf("Add of %s failed - %s\n", msg->dn, ldb_errstring(*ldb));
+		printf("Add of %s failed - %s\n", ldb_dn_linearize(*ldb, msg->dn), ldb_errstring(*ldb));
 		exit(1);
 	}
 
@@ -331,14 +342,14 @@ static void start_test_index(struct ldb_context **ldb)
 		exit(1);
 	}
 
-	ret = ldb_search(*ldb, options->basedn, LDB_SCOPE_SUBTREE, "uid=test", NULL, &res);
+	ret = ldb_search(*ldb, basedn, LDB_SCOPE_SUBTREE, "uid=test", NULL, &res);
 	if (ret != 1) {
 		printf("Should have found 1 record - found %d\n", ret);
 		exit(1);
 	}
 
 	if (ldb_delete(*ldb, msg->dn) != 0 ||
-	    ldb_delete(*ldb, "@INDEXLIST") != 0) {
+	    ldb_delete(*ldb, indexlist) != 0) {
 		printf("cleanup failed - %s\n", ldb_errstring(*ldb));
 		exit(1);
 	}
diff --git a/source4/lib/registry/reg_backend_ldb.c b/source4/lib/registry/reg_backend_ldb.c
index 3c50258d02..404dab4dc1 100644
--- a/source4/lib/registry/reg_backend_ldb.c
+++ b/source4/lib/registry/reg_backend_ldb.c
@@ -25,7 +25,7 @@
 
 struct ldb_key_data 
 {
-	const char *dn;
+	const struct ldb_dn *dn;
 	struct ldb_message **subkeys, **values;
 	int subkey_count, value_count;
 };
@@ -113,39 +113,34 @@ static int reg_close_ldb_key (void *data)
 	return 0;
 }
 
-static char *reg_path_to_ldb(TALLOC_CTX *mem_ctx, struct registry_key *from, const char *path, const char *add)
+static struct ldb_dn *reg_path_to_ldb(TALLOC_CTX *mem_ctx, struct registry_key *from, const char *path, const char *add)
 {
-	char *ret = talloc_strdup(mem_ctx, "");
+	TALLOC_CTX *local_ctx;
+	struct ldb_dn *ret = ldb_dn_new(mem_ctx);
 	char *mypath = talloc_strdup(mem_ctx, path);
 	char *begin;
 	struct ldb_key_data *kd = from->backend_data;
 
-	if(add) 
-		ret = talloc_asprintf_append(ret, "%s", add);
+	local_ctx = talloc_named(mem_ctx, 0, "reg_path_to_ldb context");
+
+	if (add) 
+		ret = ldb_dn_compose(local_ctx, ret, ldb_dn_explode(mem_ctx, add));
 
 	while(mypath) {
 		char *keyname;
-		struct ldb_val val;
-		char *key;
 
 		begin = strrchr(mypath, '\\');
 
 		if (begin) keyname = begin + 1;
 		else keyname = mypath;
 
-		val.data = keyname;
-		val.length = strlen(keyname);
-		
-		key = ldb_dn_escape_value(mem_ctx, val);
-		if (key == NULL) {
-			return NULL;
-		}
+		if(strlen(keyname)) {
+			struct ldb_dn *base;
 
-		if (strlen(key))
-			ret = talloc_asprintf_append(ret, "key=%s,", key);
+			base = ldb_dn_build_child(local_ctx, "key", keyname, NULL);
+			ret = ldb_dn_compose(local_ctx, ret, base);
+		}
 
-		talloc_free(key);
-			
 		if(begin) {
 			*begin = '\0';
 		} else {
@@ -153,7 +148,7 @@ static char *reg_path_to_ldb(TALLOC_CTX *mem_ctx, struct registry_key *from, con
 		}
 	}
 
-	ret = talloc_asprintf_append(ret, "%s", kd->dn);
+	ret = ldb_dn_compose(local_ctx, ret, kd->dn);
 
 	return ret;
 }
@@ -170,7 +165,7 @@ static WERROR ldb_get_subkey_by_id(TALLOC_CTX *mem_ctx, struct registry_key *k,
 		kd->subkey_count = ldb_search(c, kd->dn, LDB_SCOPE_ONELEVEL, "(key=*)", NULL, &kd->subkeys);
 
 		if(kd->subkey_count < 0) {
-			DEBUG(0, ("Error getting subkeys for '%s': %s\n", kd->dn, ldb_errstring(c)));
+			DEBUG(0, ("Error getting subkeys for '%s': %s\n", ldb_dn_linearize(mem_ctx, kd->dn), ldb_errstring(c)));
 			return WERR_FOOBAR;
 		}
 	} 
@@ -185,7 +180,7 @@ static WERROR ldb_get_subkey_by_id(TALLOC_CTX *mem_ctx, struct registry_key *k,
 	(*subkey)->backend_data = newkd = talloc_zero(*subkey, struct ldb_key_data);
 	(*subkey)->last_mod = 0; /* TODO: we need to add this to the
 				    ldb backend properly */
-	newkd->dn = talloc_strdup(mem_ctx, kd->subkeys[idx]->dn);
+	newkd->dn = ldb_dn_copy(mem_ctx, kd->subkeys[idx]->dn);
 
 	return WERR_OK;
 }
@@ -200,7 +195,7 @@ static WERROR ldb_get_value_by_id(TALLOC_CTX *mem_ctx, struct registry_key *k, i
 		kd->value_count = ldb_search(c, kd->dn, LDB_SCOPE_ONELEVEL, "(value=*)", NULL,&kd->values);
 
 		if(kd->value_count < 0) {
-			DEBUG(0, ("Error getting values for '%s': %s\n", kd->dn, ldb_errstring(c)));
+			DEBUG(0, ("Error getting values for '%s': %s\n", ldb_dn_linearize(mem_ctx, kd->dn), ldb_errstring(c)));
 			return WERR_FOOBAR;
 		}
 	}
@@ -218,18 +213,18 @@ static WERROR ldb_open_key(TALLOC_CTX *mem_ctx, struct registry_key *h, const ch
 {
 	struct ldb_context *c = h->hive->backend_data;
 	struct ldb_message **msg;
-	char *ldap_path;
+	struct ldb_dn *ldap_path;
 	int ret;
 	struct ldb_key_data *newkd;
 
 	ldap_path = reg_path_to_ldb(mem_ctx, h, name, NULL);
 
-	ret = ldb_search(c, ldap_path, LDB_SCOPE_BASE, "(key=*)", NULL,&msg);
+	ret = ldb_search(c, ldap_path, LDB_SCOPE_BASE, "(key=*)", NULL, &msg);
 
 	if(ret == 0) {
 		return WERR_BADFILE;
 	} else if(ret < 0) {
-		DEBUG(0, ("Error opening key '%s': %s\n", ldap_path, ldb_errstring(c)));
+		DEBUG(0, ("Error opening key '%s': %s\n", ldb_dn_linearize(ldap_path, ldap_path), ldb_errstring(c)));
 		return WERR_FOOBAR;
 	}
 
@@ -237,7 +232,7 @@ static WERROR ldb_open_key(TALLOC_CTX *mem_ctx, struct registry_key *h, const ch
 	talloc_set_destructor(*key, reg_close_ldb_key);
 	(*key)->name = talloc_strdup(mem_ctx, strrchr(name, '\\')?strchr(name, '\\'):name);
 	(*key)->backend_data = newkd = talloc_zero(*key, struct ldb_key_data);
-	newkd->dn = talloc_strdup(mem_ctx, msg[0]->dn); 
+	newkd->dn = ldb_dn_copy(mem_ctx, msg[0]->dn); 
 
 	talloc_free(msg);
 
@@ -265,7 +260,7 @@ static WERROR ldb_open_hive(struct registry_hive *hive, struct registry_key **k)
 	talloc_set_destructor (hive, ldb_free_hive);
 	(*k)->name = talloc_strdup(*k, "");
 	(*k)->backend_data = kd = talloc_zero(*k, struct ldb_key_data);
-	kd->dn = talloc_strdup(*k, "hive=NONE");
+	kd->dn = ldb_dn_explode(*k, "hive=NONE");
 	
 
 	return WERR_OK;
@@ -303,11 +298,12 @@ static WERROR ldb_del_key (struct registry_key *key, const char *child)
 {
 	int ret;
 	struct ldb_key_data *kd = key->backend_data;
-	char *childdn = talloc_asprintf(NULL, "key=%s,%s", child, kd->dn);
+	TALLOC_CTX *local_ctx = talloc_named(NULL, 0, "ldb_del_key mem ctx");
+	struct ldb_dn *childdn = ldb_dn_build_child(local_ctx, "key", child, kd->dn);
 
 	ret = ldb_delete(key->hive->backend_data, childdn);
 
-	talloc_free(childdn);
+	talloc_free(local_ctx);
 
 	if (ret < 0) {
 		DEBUG(1, ("ldb_del_key: %s\n", ldb_errstring(key->hive->backend_data)));
@@ -321,11 +317,12 @@ static WERROR ldb_del_value (struct registry_key *key, const char *child)
 {
 	int ret;
 	struct ldb_key_data *kd = key->backend_data;
-	char *childdn = talloc_asprintf(NULL, "value=%s,%s", child, kd->dn);
+	TALLOC_CTX *local_ctx = talloc_named(NULL, 0, "ldb_del_value mem ctx");
+	struct ldb_dn *childdn = ldb_dn_build_child(local_ctx, "value", child, kd->dn);
 
 	ret = ldb_delete(key->hive->backend_data, childdn);
 
-	talloc_free(childdn);
+	talloc_free(local_ctx);
 
 	if (ret < 0) {
 		DEBUG(1, ("ldb_del_value: %s\n", ldb_errstring(key->hive->backend_data)));
@@ -345,7 +342,7 @@ static WERROR ldb_set_value (struct registry_key *parent, const char *name, uint
 
 	msg = reg_ldb_pack_value(ctx, mem_ctx, name, type, data, len);
 
-	msg->dn = talloc_asprintf(mem_ctx, "value=%s,%s", name, kd->dn);
+	msg->dn = ldb_dn_build_child(msg, "value", name, kd->dn);
 
 	ret = ldb_add(ctx, msg);
 	if (ret < 0) {
diff --git a/source4/libnet/libnet_join.c b/source4/libnet/libnet_join.c
index b72577fa84..cef74492b8 100644
--- a/source4/libnet/libnet_join.c
+++ b/source4/libnet/libnet_join.c
@@ -91,7 +91,7 @@ NTSTATUS libnet_JoinDomain(struct libnet_context *ctx, TALLOC_CTX *mem_ctx, stru
 	struct dom_sid *domain_sid;
 	const char *domain_name;
 	const char *realm = NULL; /* Also flag for remote being AD */
-	const char *account_dn;
+	const struct ldb_dn *account_dn;
 
 	char *remote_ldb_url;
 	struct ldb_message **msgs, *msg;
@@ -561,8 +561,13 @@ NTSTATUS libnet_JoinDomain(struct libnet_context *ctx, TALLOC_CTX *mem_ctx, stru
 		return NT_STATUS_UNSUCCESSFUL;
 	}
 
-	account_dn = r_crack_names.out.ctr.ctr1->array[0].result_name;
-
+	account_dn = ldb_dn_explode(mem_ctx, r_crack_names.out.ctr.ctr1->array[0].result_name);
+	if (account_dn == NULL) {
+		r->out.error_string
+			= talloc_asprintf(mem_ctx, "Invalid account dn: %s",
+					  r_crack_names.out.ctr.ctr1->array[0].result_name);
+		return NT_STATUS_UNSUCCESSFUL;
+	}
 
 	/* Now we know the user's DN, open with LDAP, read and modify a few things */
 
@@ -581,8 +586,8 @@ NTSTATUS libnet_JoinDomain(struct libnet_context *ctx, TALLOC_CTX *mem_ctx, stru
 	if (ldb_ret != 1) {
 		r->out.error_string
 			= talloc_asprintf(mem_ctx,
-					  "ldb_search for %s failed - %s\n", 
-					  account_dn, 
+					  "ldb_search for %s failed - %s\n",
+					  ldb_dn_linearize(mem_ctx, account_dn),
 					  ldb_errstring(remote_ldb));
 		return NT_STATUS_UNSUCCESSFUL;
 	}
@@ -615,7 +620,7 @@ NTSTATUS libnet_JoinDomain(struct libnet_context *ctx, TALLOC_CTX *mem_ctx, stru
 			r->out.error_string
 				= talloc_asprintf(mem_ctx, 
 						  "Failed to replace entries on %s\n", 
-						  msg->dn);
+						  ldb_dn_linearize(mem_ctx, msg->dn));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	}
@@ -635,7 +640,7 @@ static NTSTATUS libnet_Join_primary_domain(struct libnet_context *ctx,
 
 	struct ldb_context *ldb;
 	struct libnet_JoinDomain r2;
-	const char *base_dn = "cn=Primary Domains";
+	const struct ldb_dn *base_dn = ldb_dn_explode(mem_ctx, "cn=Primary Domains");
 	const struct ldb_val *prior_secret;
 	const struct ldb_val *prior_modified_time;
 	struct ldb_message **msgs, *msg;
@@ -679,13 +684,12 @@ static NTSTATUS libnet_Join_primary_domain(struct libnet_context *ctx,
 
 	/* search for the secret record */
 	ret = gendb_search(ldb,
-			   mem_ctx, base_dn, &msgs, attrs,
+			   mem_ctx, base_dn,
+			   &msgs, attrs,
 			   "(|" SECRETS_PRIMARY_DOMAIN_FILTER "(realm=%s))",
 			   r2.out.domain_name, r2.out.realm);
 
-	msg->dn = talloc_asprintf(mem_ctx, "flatname=%s,%s", 
-				  r2.out.domain_name,
-				  base_dn);
+	msg->dn = ldb_dn_build_child(mem_ctx, "flatname", r2.out.domain_name, base_dn);
 	
 	samdb_msg_add_string(ldb, mem_ctx, msg, "flatname", r2.out.domain_name);
 	if (r2.out.realm) {
@@ -739,7 +743,7 @@ static NTSTATUS libnet_Join_primary_domain(struct libnet_context *ctx,
 		r->out.error_string
 			= talloc_asprintf(mem_ctx, 
 					  "Failed to create secret record %s\n", 
-					  msg->dn);
+					  ldb_dn_linearize(ldb, msg->dn));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 	return NT_STATUS_OK;
diff --git a/source4/libnet/libnet_samsync_ldb.c b/source4/libnet/libnet_samsync_ldb.c
index 691f621dfe..4ec7c60715 100644
--- a/source4/libnet/libnet_samsync_ldb.c
+++ b/source4/libnet/libnet_samsync_ldb.c
@@ -46,7 +46,7 @@ struct samsync_ldb_trusted_domain {
 struct samsync_ldb_state {
 	struct dom_sid *dom_sid[3];
 	struct ldb_context *sam_ldb;
-	char *base_dn[3];
+	struct ldb_dn *base_dn[3];
 	struct samsync_ldb_secret *secrets;
 	struct samsync_ldb_trusted_domain *trusted_domains;
 };
@@ -54,14 +54,15 @@ struct samsync_ldb_state {
 static NTSTATUS samsync_ldb_add_foreignSecurityPrincipal(TALLOC_CTX *mem_ctx,
 							 struct samsync_ldb_state *state,
 							 struct dom_sid *sid,
-							 char **fsp_dn)
+							 struct ldb_dn **fsp_dn)
 {
 	const char *sidstr = dom_sid_string(mem_ctx, sid);
 	/* We assume that ForeignSecurityPrincipals are under the BASEDN of the main domain */
-	const char *basedn = samdb_search_string(state->sam_ldb, mem_ctx, state->base_dn[SAM_DATABASE_DOMAIN],
-						 "dn",
-						 "(&(objectClass=container)"
-						 "(cn=ForeignSecurityPrincipals))");
+	struct ldb_dn *basedn = ldb_dn_explode(mem_ctx,
+						samdb_search_string(state->sam_ldb, mem_ctx,
+									state->base_dn[SAM_DATABASE_DOMAIN],
+									"dn", "(&(objectClass=container)"
+										"(cn=ForeignSecurityPrincipals))"));
 	struct ldb_message *msg;
 	int ret;
 
@@ -81,7 +82,7 @@ static NTSTATUS samsync_ldb_add_foreignSecurityPrincipal(TALLOC_CTX *mem_ctx,
 	}
 
 	/* add core elements to the ldb_message for the alias */
-	msg->dn = talloc_asprintf(mem_ctx, "CN=%s,%s", sidstr, basedn);
+	msg->dn = ldb_dn_build_child(mem_ctx, "CN", sidstr, basedn);
 	if (msg->dn == NULL)
 		return NT_STATUS_NO_MEMORY;
 	
@@ -95,7 +96,9 @@ static NTSTATUS samsync_ldb_add_foreignSecurityPrincipal(TALLOC_CTX *mem_ctx,
 	ret = samdb_add(state->sam_ldb, mem_ctx, msg);
 	if (ret != 0) {
 		DEBUG(0,("Failed to create foreignSecurityPrincipal "
-			 "record %s: %s\n", msg->dn, ldb_errstring(state->sam_ldb)));
+			 "record %s: %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn),
+			 ldb_errstring(state->sam_ldb)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 	return NT_STATUS_OK;
@@ -134,8 +137,8 @@ static NTSTATUS samsync_ldb_handle_domain(TALLOC_CTX *mem_ctx,
 		state->dom_sid[database]
 			= talloc_steal(state, 
 				       samdb_search_dom_sid(state->sam_ldb, state,
-							    state->base_dn[database], "objectSid", 
-							    "dn=%s", state->base_dn[database]));
+							    state->base_dn[database], "objectSid", "dn=%s",
+							    ldb_dn_linearize(mem_ctx, state->base_dn[database])));
 	} else if (database == SAM_DATABASE_BUILTIN) {
 			/* work out the builtin_dn - useful for so many calls its worth
 			   fetching here */
@@ -220,8 +223,8 @@ static NTSTATUS samsync_ldb_handle_user(TALLOC_CTX *mem_ctx,
 	}
 
 	/* search for the user, by rid */
-	ret = gendb_search(state->sam_ldb, mem_ctx, state->base_dn[database], &msgs, attrs,
-			   "(&(objectClass=user)(objectSid=%s))", 
+	ret = gendb_search(state->sam_ldb, mem_ctx, state->base_dn[database],
+			   &msgs, attrs, "(&(objectClass=user)(objectSid=%s))", 
 			   ldap_encode_ndr_dom_sid(mem_ctx, dom_sid_add_rid(mem_ctx, state->dom_sid[database], rid))); 
 
 	if (ret == -1) {
@@ -334,21 +337,26 @@ static NTSTATUS samsync_ldb_handle_user(TALLOC_CTX *mem_ctx,
 	if (add) {
 		samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, 
 				     "objectClass", obj_class);
-		msg->dn = talloc_asprintf(mem_ctx, "CN=%s,CN=%s,%s",
-					  cn_name, container, state->base_dn[database]);
+		msg->dn = ldb_dn_build_child(mem_ctx,
+					     "CN", cn_name,
+					     ldb_dn_build_child(mem_ctx,
+								"CN", container,
+								state->base_dn[database]));
 		if (!msg->dn) {
 			return NT_STATUS_NO_MEMORY;		
 		}
 
 		ret = samdb_add(state->sam_ldb, mem_ctx, msg);
 		if (ret != 0) {
-			DEBUG(0,("Failed to create user record %s\n", msg->dn));
+			DEBUG(0,("Failed to create user record %s\n",
+				 ldb_dn_linearize(mem_ctx, msg->dn)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	} else {
 		ret = samdb_replace(state->sam_ldb, mem_ctx, msg);
 		if (ret != 0) {
-			DEBUG(0,("Failed to modify user record %s\n", msg->dn));
+			DEBUG(0,("Failed to modify user record %s\n",
+				 ldb_dn_linearize(mem_ctx, msg->dn)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	}
@@ -368,8 +376,8 @@ static NTSTATUS samsync_ldb_delete_user(TALLOC_CTX *mem_ctx,
 	const char *attrs[] = { NULL };
 
 	/* search for the user, by rid */
-	ret = gendb_search(state->sam_ldb, mem_ctx, state->base_dn[database], &msgs, attrs,
-			   "(&(objectClass=user)(objectSid=%s))", 
+	ret = gendb_search(state->sam_ldb, mem_ctx, state->base_dn[database],
+			   &msgs, attrs, "(&(objectClass=user)(objectSid=%s))", 
 			   ldap_encode_ndr_dom_sid(mem_ctx, dom_sid_add_rid(mem_ctx, state->dom_sid[database], rid))); 
 
 	if (ret == -1) {
@@ -388,7 +396,9 @@ static NTSTATUS samsync_ldb_delete_user(TALLOC_CTX *mem_ctx,
 
 	ret = samdb_delete(state->sam_ldb, mem_ctx, msgs[0]->dn);
 	if (ret != 0) {
-		DEBUG(0,("Failed to delete user record %s: %s\n", msgs[0]->dn, ldb_errstring(state->sam_ldb)));
+		DEBUG(0,("Failed to delete user record %s: %s\n",
+			 ldb_dn_linearize(mem_ctx, msgs[0]->dn),
+			 ldb_errstring(state->sam_ldb)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -467,21 +477,28 @@ static NTSTATUS samsync_ldb_handle_group(TALLOC_CTX *mem_ctx,
 	if (add) {
 		samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, 
 				     "objectClass", obj_class);
-		msg->dn = talloc_asprintf(mem_ctx, "CN=%s,CN=%s,%s",
-					  cn_name, container, state->base_dn[database]);
+		msg->dn = ldb_dn_build_child(mem_ctx,
+					     "CN", cn_name,
+					     ldb_dn_build_child(mem_ctx,
+								"CN", container,
+								state->base_dn[database]));
 		if (!msg->dn) {
 			return NT_STATUS_NO_MEMORY;		
 		}
 
 		ret = samdb_add(state->sam_ldb, mem_ctx, msg);
 		if (ret != 0) {
-			DEBUG(0,("Failed to create group record %s: %s\n", msg->dn, ldb_errstring(state->sam_ldb)));
+			DEBUG(0,("Failed to create group record %s: %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn),
+			 ldb_errstring(state->sam_ldb)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	} else {
 		ret = samdb_replace(state->sam_ldb, mem_ctx, msg);
 		if (ret != 0) {
-			DEBUG(0,("Failed to modify group record %s: %s\n", msg->dn, ldb_errstring(state->sam_ldb)));
+			DEBUG(0,("Failed to modify group record %s: %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn),
+			 ldb_errstring(state->sam_ldb)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	}
@@ -521,7 +538,9 @@ static NTSTATUS samsync_ldb_delete_group(TALLOC_CTX *mem_ctx,
 	
 	ret = samdb_delete(state->sam_ldb, mem_ctx, msgs[0]->dn);
 	if (ret != 0) {
-		DEBUG(0,("Failed to delete group record %s: %s\n", msgs[0]->dn, ldb_errstring(state->sam_ldb)));
+		DEBUG(0,("Failed to delete group record %s: %s\n",
+			 ldb_dn_linearize(mem_ctx, msgs[0]->dn),
+			 ldb_errstring(state->sam_ldb)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -584,7 +603,7 @@ static NTSTATUS samsync_ldb_handle_group_member(TALLOC_CTX *mem_ctx,
 		} else if (ret > 1) {
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		} else {
-			samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, "member", msgs[0]->dn);
+			samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, "member", ldb_dn_linearize(mem_ctx, msgs[0]->dn));
 		}
 	
 		talloc_free(msgs);
@@ -592,7 +611,9 @@ static NTSTATUS samsync_ldb_handle_group_member(TALLOC_CTX *mem_ctx,
 
 	ret = samdb_replace(state->sam_ldb, mem_ctx, msg);
 	if (ret != 0) {
-		DEBUG(0,("Failed to modify group record %s: %s\n", msg->dn, ldb_errstring(state->sam_ldb)));
+		DEBUG(0,("Failed to modify group record %s: %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn),
+			 ldb_errstring(state->sam_ldb)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -673,21 +694,28 @@ static NTSTATUS samsync_ldb_handle_alias(TALLOC_CTX *mem_ctx,
 	if (add) {
 		samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, 
 				     "objectClass", obj_class);
-		msg->dn = talloc_asprintf(mem_ctx, "CN=%s,CN=%s,%s",
-					  cn_name, container, state->base_dn[database]);
+		msg->dn = ldb_dn_build_child(mem_ctx,
+					     "CN", cn_name,
+					     ldb_dn_build_child(mem_ctx,
+								"CN", container,
+								state->base_dn[database]));
 		if (!msg->dn) {
 			return NT_STATUS_NO_MEMORY;		
 		}
 
 		ret = samdb_add(state->sam_ldb, mem_ctx, msg);
 		if (ret != 0) {
-			DEBUG(0,("Failed to create alias record %s: %s\n", msg->dn, ldb_errstring(state->sam_ldb)));
+			DEBUG(0,("Failed to create alias record %s: %s\n",
+				 ldb_dn_linearize(mem_ctx, msg->dn),
+				 ldb_errstring(state->sam_ldb)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	} else {
 		ret = samdb_replace(state->sam_ldb, mem_ctx, msg);
 		if (ret != 0) {
-			DEBUG(0,("Failed to modify alias record %s: %s\n", msg->dn, ldb_errstring(state->sam_ldb)));
+			DEBUG(0,("Failed to modify alias record %s: %s\n",
+				 ldb_dn_linearize(mem_ctx, msg->dn),
+				 ldb_errstring(state->sam_ldb)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	}
@@ -722,7 +750,9 @@ static NTSTATUS samsync_ldb_delete_alias(TALLOC_CTX *mem_ctx,
 
 	ret = samdb_delete(state->sam_ldb, mem_ctx, msgs[0]->dn);
 	if (ret != 0) {
-		DEBUG(0,("Failed to delete alias record %s: %s\n", msgs[0]->dn, ldb_errstring(state->sam_ldb)));
+		DEBUG(0,("Failed to delete alias record %s: %s\n",
+			 ldb_dn_linearize(mem_ctx, msgs[0]->dn),
+			 ldb_errstring(state->sam_ldb)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -772,7 +802,7 @@ static NTSTATUS samsync_ldb_handle_alias_member(TALLOC_CTX *mem_ctx,
 	talloc_free(msgs);
 
 	for (i=0; i<alias_member->sids.num_sids; i++) {
-		char *alias_member_dn;
+		struct ldb_dn *alias_member_dn;
 		/* search for members, in the top basedn (normal users are builtin aliases) */
 		ret = gendb_search(state->sam_ldb, mem_ctx, state->base_dn[SAM_DATABASE_DOMAIN], &msgs, attrs,
 				   "(objectSid=%s)", 
@@ -794,14 +824,16 @@ static NTSTATUS samsync_ldb_handle_alias_member(TALLOC_CTX *mem_ctx,
 		} else {
 			alias_member_dn = msgs[0]->dn;
 		}
-		samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, "member", alias_member_dn);
+		samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, "member", ldb_dn_linearize(mem_ctx, alias_member_dn));
 	
 		talloc_free(msgs);
 	}
 
 	ret = samdb_replace(state->sam_ldb, mem_ctx, msg);
 	if (ret != 0) {
-		DEBUG(0,("Failed to modify group record %s: %s\n", msg->dn, ldb_errstring(state->sam_ldb)));
+		DEBUG(0,("Failed to modify group record %s: %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn),
+			 ldb_errstring(state->sam_ldb)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -819,7 +851,7 @@ static NTSTATUS samsync_ldb_handle_account(TALLOC_CTX *mem_ctx,
 
 	struct ldb_message *msg;
 	struct ldb_message **msgs;
-	char *privilage_dn;
+	struct ldb_dn *privilege_dn;
 	int ret;
 	const char *attrs[] = { NULL };
 	int i;
@@ -840,8 +872,8 @@ static NTSTATUS samsync_ldb_handle_account(TALLOC_CTX *mem_ctx,
 		NTSTATUS nt_status;
 		nt_status = samsync_ldb_add_foreignSecurityPrincipal(mem_ctx, state,
 								     sid,
-								     &privilage_dn);
-		privilage_dn = talloc_steal(msg, privilage_dn);
+								     &privilege_dn);
+		privilege_dn = talloc_steal(msg, privilege_dn);
 		if (!NT_STATUS_IS_OK(nt_status)) {
 			return nt_status;
 		}
@@ -850,19 +882,20 @@ static NTSTATUS samsync_ldb_handle_account(TALLOC_CTX *mem_ctx,
 			  dom_sid_string(mem_ctx, sid)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	} else {
-		privilage_dn = talloc_steal(msg, msgs[0]->dn);
+		privilege_dn = talloc_steal(msg, msgs[0]->dn);
 	}
 
-	msg->dn = privilage_dn;
+	msg->dn = privilege_dn;
 
 	for (i=0; i< account->privilege_entries; i++) {
-		samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, "privilage",
+		samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, "privilege",
 				     account->privilege_name[i].string);
 	}
 
 	ret = samdb_replace(state->sam_ldb, mem_ctx, msg);
 	if (ret != 0) {
-		DEBUG(0,("Failed to modify privilage record %s\n", msg->dn));
+		DEBUG(0,("Failed to modify privilege record %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -910,7 +943,8 @@ static NTSTATUS samsync_ldb_delete_account(TALLOC_CTX *mem_ctx,
 
 	ret = samdb_replace(state->sam_ldb, mem_ctx, msg);
 	if (ret != 0) {
-		DEBUG(0,("Failed to modify privilage record %s\n", msg->dn));
+		DEBUG(0,("Failed to modify privilege record %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
diff --git a/source4/nbt_server/dgram/netlogon.c b/source4/nbt_server/dgram/netlogon.c
index b484ca4a77..ab2f1cc579 100644
--- a/source4/nbt_server/dgram/netlogon.c
+++ b/source4/nbt_server/dgram/netlogon.c
@@ -125,10 +125,11 @@ static void nbtd_netlogon_getdc2(struct dgram_mailslot_handler *dgmslot,
 
 	/* try and find the domain */
 	ret = gendb_search_dn(samctx, samctx, 
-			      samdb_result_string(ref_res[0], "ncName", NULL), 
+			      samdb_result_dn(samctx, ref_res[0], "ncName", NULL), 
 			      &dom_res, dom_attrs);
 	if (ret != 1) {
-		DEBUG(2,("Unable to find domain from reference '%s' in sam\n", ref_res[0]->dn));
+		DEBUG(2,("Unable to find domain from reference '%s' in sam\n",
+			 ldb_dn_linearize(samctx, ref_res[0]->dn)));
 		return;
 	}
 
diff --git a/source4/nbt_server/wins/winsdb.c b/source4/nbt_server/wins/winsdb.c
index c46c4c571e..a83c60c3e7 100644
--- a/source4/nbt_server/wins/winsdb.c
+++ b/source4/nbt_server/wins/winsdb.c
@@ -37,7 +37,7 @@ static BOOL winsdb_save_version(struct wins_server *winssrv)
 	struct ldb_message *msg = ldb_msg_new(winssrv);
 	if (msg == NULL) goto failed;
 
-	msg->dn = talloc_strdup(msg, "CN=VERSION");
+	msg->dn = ldb_dn_explode(msg, "CN=VERSION");
 	if (msg->dn == NULL) goto failed;
 
 	ret |= ldb_msg_add_fmt(ldb, msg, "minVersion", "%llu", winssrv->min_version);
@@ -184,7 +184,7 @@ static struct ldb_message *winsdb_message(struct wins_server *winssrv,
 	struct ldb_message *msg = ldb_msg_new(mem_ctx);
 	if (msg == NULL) goto failed;
 
-	msg->dn = winsdb_dn(msg, rec->name);
+	msg->dn = ldb_dn_explode(msg, winsdb_dn(msg, rec->name));
 	if (msg->dn == NULL) goto failed;
 	ret |= ldb_msg_add_fmt(ldb, msg, "objectClass", "wins");
 	ret |= ldb_msg_add_fmt(ldb, msg, "active", "%u", rec->state);
@@ -272,11 +272,11 @@ uint8_t winsdb_delete(struct wins_server *winssrv, struct winsdb_record *rec)
 	struct ldb_context *ldb = winssrv->wins_db;
 	TALLOC_CTX *tmp_ctx = talloc_new(winssrv);
 	int ret;
-	const char *dn;
+	const struct ldb_dn *dn;
 
 	winsdb_remove_version(winssrv, rec->version);
 
-	dn = winsdb_dn(tmp_ctx, rec->name);
+	dn = ldb_dn_explode(tmp_ctx, winsdb_dn(tmp_ctx, rec->name));
 	if (dn == NULL) goto failed;
 
 	ret = ldb_delete(ldb, dn);
diff --git a/source4/ntptr/simple_ldb/ntptr_simple_ldb.c b/source4/ntptr/simple_ldb/ntptr_simple_ldb.c
index bd3443e199..c0ae2e078d 100644
--- a/source4/ntptr/simple_ldb/ntptr_simple_ldb.c
+++ b/source4/ntptr/simple_ldb/ntptr_simple_ldb.c
@@ -45,14 +45,14 @@ static struct ldb_context *sptr_db_connect(TALLOC_CTX *mem_ctx)
 
 static int sptr_db_search(struct ldb_context *ldb,
 			  TALLOC_CTX *mem_ctx,
-			  const char *basedn,
+			  const struct ldb_dn *basedn,
 			  struct ldb_message ***res,
 			  const char * const *attrs,
 			  const char *format, ...) PRINTF_ATTRIBUTE(6,7);
 
 static int sptr_db_search(struct ldb_context *ldb,
 			  TALLOC_CTX *mem_ctx,
-			  const char *basedn,
+			  const struct ldb_dn *basedn,
 			  struct ldb_message ***res,
 			  const char * const *attrs,
 			  const char *format, ...)
@@ -222,8 +222,9 @@ static WERROR sptr_EnumPrintServerForms(struct ntptr_GenericHandle *server, TALL
 	int i;
 	union spoolss_FormInfo *info;
 
-	count = sptr_db_search(sptr_db, mem_ctx, "CN=Forms,CN=PrintServer", &msgs, NULL,
-			       "(&(objectClass=form))");
+	count = sptr_db_search(sptr_db, mem_ctx,
+				ldb_dn_explode(mem_ctx, "CN=Forms,CN=PrintServer"),
+				&msgs, NULL, "(&(objectClass=form))");
 
 	if (count == 0) return WERR_OK;
 	if (count < 0) return WERR_GENERAL_FAILURE;
@@ -276,8 +277,9 @@ static WERROR sptr_AddPrintServerForm(struct ntptr_GenericHandle *server, TALLOC
 		if (!r->in.info.info1) {
 			return WERR_FOOBAR;
 		}
-		count = sptr_db_search(sptr_db, mem_ctx, "CN=Forms,CN=PrintServer", &msgs, attrs,
-				       "(&(form-name=%s)(objectClass=form))",
+		count = sptr_db_search(sptr_db, mem_ctx,
+				       ldb_dn_explode(mem_ctx, "CN=Forms,CN=PrintServer"),
+				       &msgs, attrs, "(&(form-name=%s)(objectClass=form))",
 				       r->in.info.info1->form_name);
 
 		if (count == 1) return WERR_FOOBAR;
@@ -292,8 +294,9 @@ static WERROR sptr_AddPrintServerForm(struct ntptr_GenericHandle *server, TALLOC
 		W_ERROR_HAVE_NO_MEMORY(msg);
 
 		/* add core elements to the ldb_message for the Form */
-		msg->dn = talloc_asprintf(msg, "form-name=%s,CN=Forms,CN=PrintServer",
-						r->in.info.info1->form_name);
+		msg->dn = ldb_dn_build_child(msg,
+					     "form-name", r->in.info.info1->form_name,
+					     ldb_dn_explode(msg, "CN=Forms,CN=PrintServer"));
 		SET_STRING(sptr_db, msg, "objectClass", "form");
 
 		SET_UINT(sptr_db, msg, "flags", r->in.info.info1->flags);
@@ -341,8 +344,9 @@ static WERROR sptr_SetPrintServerForm(struct ntptr_GenericHandle *server, TALLOC
 			return WERR_FOOBAR;
 		}
 
-		count = sptr_db_search(sptr_db, mem_ctx, "CN=Forms,CN=PrintServer", &msgs, attrs,
-				       "(&(form-name=%s)(objectClass=form))",
+		count = sptr_db_search(sptr_db, mem_ctx,
+				       ldb_dn_explode(mem_ctx, "CN=Forms,CN=PrintServer"),
+				       &msgs, attrs, "(&(form-name=%s)(objectClass=form))",
 				       r->in.info.info1->form_name);
 
 		if (count == 0) return WERR_FOOBAR;
@@ -403,8 +407,9 @@ static WERROR sptr_DeletePrintServerForm(struct ntptr_GenericHandle *server, TAL
 		return WERR_FOOBAR;
 	}
 
-	count = sptr_db_search(sptr_db, mem_ctx, "CN=Forms,CN=PrintServer", &msgs, attrs,
-			       "(&(form-name=%s)(objectclass=form))",
+	count = sptr_db_search(sptr_db, mem_ctx,
+			       ldb_dn_explode(mem_ctx, "CN=Forms,CN=PrintServer"),
+			       &msgs, attrs, "(&(form-name=%s)(objectclass=form))",
 			       r->in.form_name);
 
 	if (count == 0) return WERR_FOOBAR;
@@ -695,7 +700,7 @@ static WERROR sptr_GetPrinterForm(struct ntptr_GenericHandle *printer, TALLOC_CT
 {
 	struct ldb_context *sptr_db = talloc_get_type(printer->ntptr->private_data, struct ldb_context);
 	struct ldb_message **msgs;
-	const char *base_dn;
+	const struct ldb_dn *base_dn;
 	int count;
 	union spoolss_FormInfo *info;
 
@@ -705,7 +710,11 @@ static WERROR sptr_GetPrinterForm(struct ntptr_GenericHandle *printer, TALLOC_CT
 	 * }
 	 */
 
-	base_dn = talloc_asprintf(mem_ctx, "CN=Forms,CN=%s,CN=Printers", printer->object_name);
+	base_dn = ldb_dn_compose_string_dn(mem_ctx,
+					   "CN=Forms",
+					   ldb_dn_build_child(mem_ctx,
+							      "CN", printer->object_name,
+							      ldb_dn_explode(mem_ctx, "CN=Printers")));
 	W_ERROR_HAVE_NO_MEMORY(base_dn);
 
 	count = sptr_db_search(sptr_db, mem_ctx, base_dn, &msgs, NULL,
diff --git a/source4/rpc_server/drsuapi/drsuapi_cracknames.c b/source4/rpc_server/drsuapi/drsuapi_cracknames.c
index e9b78b184b..b6a9105be5 100644
--- a/source4/rpc_server/drsuapi/drsuapi_cracknames.c
+++ b/source4/rpc_server/drsuapi/drsuapi_cracknames.c
@@ -36,7 +36,7 @@ static WERROR DsCrackNameOneName(struct drsuapi_bind_state *b_state, TALLOC_CTX
 	const char *domain_filter = NULL;
 	const char * const *domain_attrs;
 	struct ldb_message **domain_res = NULL;
-	const char *result_basedn = NULL;
+	const struct ldb_dn *result_basedn = NULL;
 	const char *result_filter = NULL;
 	const char * const *result_attrs;
 	struct ldb_message **result_res = NULL;
@@ -166,7 +166,7 @@ static WERROR DsCrackNameOneName(struct drsuapi_bind_state *b_state, TALLOC_CTX
 	info1->status		= DRSUAPI_DS_NAME_STATUS_DOMAIN_ONLY;
 
 	if (result_filter) {
-		result_basedn = samdb_result_string(domain_res[0], "ncName", NULL);
+		result_basedn = samdb_result_dn(mem_ctx, domain_res[0], "ncName", NULL);
 
 		ret = gendb_search(b_state->sam_ctx, mem_ctx, result_basedn, &result_res,
 					result_attrs, "%s", result_filter);
@@ -189,7 +189,7 @@ static WERROR DsCrackNameOneName(struct drsuapi_bind_state *b_state, TALLOC_CTX
 	/* here we can use result_res[0] and domain_res[0] */
 	switch (format_desired) {
 		case DRSUAPI_DS_NAME_FORMAT_FQDN_1779: {
-			info1->result_name	= result_res[0]->dn;
+			info1->result_name	= ldb_dn_linearize(mem_ctx, result_res[0]->dn);
 			WERR_TALLOC_CHECK(info1->result_name);
 
 			info1->status		= DRSUAPI_DS_NAME_STATUS_OK;
diff --git a/source4/rpc_server/lsa/dcesrv_lsa.c b/source4/rpc_server/lsa/dcesrv_lsa.c
index fef1c91c6f..9ee0d6faec 100644
--- a/source4/rpc_server/lsa/dcesrv_lsa.c
+++ b/source4/rpc_server/lsa/dcesrv_lsa.c
@@ -49,9 +49,9 @@ struct lsa_policy_state {
 	struct ldb_context *sam_ldb;
 	struct sidmap_context *sidmap;
 	uint32_t access_mask;
-	const char *domain_dn;
-	const char *builtin_dn;
-	const char *system_dn;
+	const struct ldb_dn *domain_dn;
+	const struct ldb_dn *builtin_dn;
+	const struct ldb_dn *system_dn;
 	const char *domain_name;
 	struct dom_sid *domain_sid;
 	struct dom_sid *builtin_sid;
@@ -65,7 +65,7 @@ struct lsa_account_state {
 	struct lsa_policy_state *policy;
 	uint32_t access_mask;
 	struct dom_sid *account_sid;
-	const char *account_dn;
+	const struct ldb_dn *account_dn;
 };
 
 
@@ -75,7 +75,7 @@ struct lsa_account_state {
 struct lsa_secret_state {
 	struct lsa_policy_state *policy;
 	uint32_t access_mask;
-	const char *secret_dn;
+	const struct ldb_dn *secret_dn;
 	struct ldb_context *sam_ldb;
 	BOOL global;
 };
@@ -86,7 +86,7 @@ struct lsa_secret_state {
 struct lsa_trusted_domain_state {
 	struct lsa_policy_state *policy;
 	uint32_t access_mask;
-	const char *trusted_domain_dn;
+	const struct ldb_dn *trusted_domain_dn;
 };
 
 /* 
@@ -254,14 +254,14 @@ static NTSTATUS lsa_get_policy_state(struct dcesrv_call_state *dce_call, TALLOC_
 
 	/* work out the domain_dn - useful for so many calls its worth
 	   fetching here */
-	state->domain_dn = talloc_steal(state, samdb_result_string(msgs_domain[0], "nCName", NULL));
+	state->domain_dn = samdb_result_dn(state, msgs_domain[0], "nCName", NULL);
 	if (!state->domain_dn) {
 		return NT_STATUS_NO_SUCH_DOMAIN;		
 	}
 
 	/* work out the builtin_dn - useful for so many calls its worth
 	   fetching here */
-	state->builtin_dn = talloc_steal(state, 
+	state->builtin_dn = ldb_dn_explode(state, 
 					 samdb_search_string(state->sam_ldb, mem_ctx, NULL,
 							     "dn", "objectClass=builtinDomain"));
 	if (!state->builtin_dn) {
@@ -270,7 +270,7 @@ static NTSTATUS lsa_get_policy_state(struct dcesrv_call_state *dce_call, TALLOC_
 
 	/* work out the system_dn - useful for so many calls its worth
 	   fetching here */
-	state->system_dn = talloc_steal(state, 
+	state->system_dn = ldb_dn_explode(state, 
 					samdb_search_string(state->sam_ldb, mem_ctx, state->domain_dn,
 							    "dn", "(&(objectClass=container)(cn=System))"));
 	if (!state->system_dn) {
@@ -279,8 +279,8 @@ static NTSTATUS lsa_get_policy_state(struct dcesrv_call_state *dce_call, TALLOC_
 
 	state->domain_sid = talloc_steal(state, 
 					 samdb_search_dom_sid(state->sam_ldb, state,
-							      state->domain_dn, "objectSid", 
-							      "dn=%s", state->domain_dn));
+							      state->domain_dn, "objectSid", "dn=%s",
+							      ldb_dn_linearize(mem_ctx, state->domain_dn)));
 	if (!state->domain_sid) {
 		return NT_STATUS_NO_SUCH_DOMAIN;		
 	}
@@ -598,12 +598,14 @@ static NTSTATUS lsa_CreateTrustedDomain(struct dcesrv_call_state *dce_call, TALL
 	}
 	
 	if (ret < 0 || ret > 1) {
-		DEBUG(0,("Found %d records matching DN %s\n", ret, policy_state->system_dn));
+		DEBUG(0,("Found %d records matching DN %s\n", ret,
+			 ldb_dn_linearize(mem_ctx, policy_state->system_dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 	
-	msg->dn = talloc_asprintf(mem_ctx, "cn=%s,%s", r->in.info->name.string, 
-				  policy_state->system_dn);
+	msg->dn = ldb_dn_build_child(mem_ctx, "cn",
+				     r->in.info->name.string, 
+				     policy_state->system_dn);
 	if (!msg->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -627,7 +629,8 @@ static NTSTATUS lsa_CreateTrustedDomain(struct dcesrv_call_state *dce_call, TALL
 	/* create the trusted_domain */
 	ret = samdb_add(trusted_domain_state->policy->sam_ldb, mem_ctx, msg);
 	if (ret != 0) {
-		DEBUG(0,("Failed to create trusted_domain record %s\n", msg->dn));
+		DEBUG(0,("Failed to create trusted_domain record %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -690,7 +693,8 @@ static NTSTATUS lsa_OpenTrustedDomain(struct dcesrv_call_state *dce_call, TALLOC
 	}
 	
 	if (ret != 1) {
-		DEBUG(0,("Found %d records matching DN %s\n", ret, policy_state->system_dn));
+		DEBUG(0,("Found %d records matching DN %s\n", ret,
+			 ldb_dn_linearize(mem_ctx, policy_state->system_dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -755,7 +759,8 @@ static NTSTATUS lsa_OpenTrustedDomainByName(struct dcesrv_call_state *dce_call,
 	}
 	
 	if (ret != 1) {
-		DEBUG(0,("Found %d records matching DN %s\n", ret, policy_state->system_dn));
+		DEBUG(0,("Found %d records matching DN %s\n", ret,
+			 ldb_dn_linearize(mem_ctx, policy_state->system_dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -1300,11 +1305,12 @@ static NTSTATUS lsa_OpenAccount(struct dcesrv_call_state *dce_call, TALLOC_CTX *
 	
 	/* check it really exists */
 	astate->account_dn = 
-		samdb_search_string(state->sam_ldb, astate,
-				    NULL, "dn", 
-				    "(&(objectSid=%s)(objectClass=group))", 
-				    ldap_encode_ndr_dom_sid(mem_ctx,
-							    astate->account_sid));
+		ldb_dn_explode(mem_ctx,
+				samdb_search_string(state->sam_ldb, astate,
+						    NULL, "dn", 
+						    "(&(objectSid=%s)(objectClass=group))", 
+						    ldap_encode_ndr_dom_sid(mem_ctx,
+									    astate->account_sid)));
 	if (astate->account_dn == NULL) {
 		talloc_free(astate);
 		return NT_STATUS_NO_SUCH_USER;
@@ -1466,7 +1472,7 @@ static NTSTATUS lsa_AddRemoveAccountRights(struct dcesrv_call_state *dce_call,
 		return NT_STATUS_NO_SUCH_USER;
 	}
 
-	msg->dn = talloc_strdup(mem_ctx, dn);
+	msg->dn = ldb_dn_explode(mem_ctx, dn);
 	if (msg->dn == NULL) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -1732,11 +1738,12 @@ static NTSTATUS lsa_CreateSecret(struct dcesrv_call_state *dce_call, TALLOC_CTX
 		}
 		
 		if (ret < 0 || ret > 1) {
-			DEBUG(0,("Found %d records matching DN %s\n", ret, policy_state->system_dn));
+			DEBUG(0,("Found %d records matching DN %s\n", ret,
+				 ldb_dn_linearize(mem_ctx, policy_state->system_dn)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 
-		msg->dn = talloc_asprintf(mem_ctx, "cn=%s,%s", name2, policy_state->system_dn);
+		msg->dn = ldb_dn_build_child(mem_ctx, "cn", name2, policy_state->system_dn);
 		if (!name2 || !msg->dn) {
 			return NT_STATUS_NO_MEMORY;
 		}
@@ -1753,20 +1760,24 @@ static NTSTATUS lsa_CreateSecret(struct dcesrv_call_state *dce_call, TALLOC_CTX
 
 		secret_state->sam_ldb = talloc_reference(secret_state, secrets_db_connect(mem_ctx));
 		/* search for the secret record */
-		ret = gendb_search(secret_state->sam_ldb,
-				   mem_ctx, "cn=LSA Secrets", &msgs, attrs,
-				   "(&(cn=%s)(objectclass=secret))", 
-				   name);
+		ret = gendb_search(secret_state->sam_ldb, mem_ctx,
+				   ldb_dn_explode(mem_ctx, "cn=LSA Secrets"),
+				   &msgs, attrs,
+				   "(&(cn=%s)(objectclass=secret))", name);
 		if (ret > 0) {
 			return NT_STATUS_OBJECT_NAME_COLLISION;
 		}
 		
 		if (ret < 0 || ret > 1) {
-			DEBUG(0,("Found %d records matching DN %s\n", ret, policy_state->system_dn));
+			DEBUG(0,("Found %d records matching DN %s\n", ret,
+				 ldb_dn_linearize(mem_ctx, policy_state->system_dn)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 
-		msg->dn = talloc_asprintf(mem_ctx, "cn=%s,cn=LSA Secrets", name);
+		msg->dn = ldb_dn_build_child(mem_ctx,
+					     "cn", name,
+					     ldb_dn_build_child(mem_ctx,
+								"cn", "LSA Secrets", NULL));
 		samdb_msg_add_string(secret_state->sam_ldb, mem_ctx, msg, "cn", name);
 	} 
 
@@ -1785,7 +1796,8 @@ static NTSTATUS lsa_CreateSecret(struct dcesrv_call_state *dce_call, TALLOC_CTX
 	/* create the secret */
 	ret = samdb_add(secret_state->sam_ldb, mem_ctx, msg);
 	if (ret != 0) {
-		DEBUG(0,("Failed to create secret record %s\n", msg->dn));
+		DEBUG(0,("Failed to create secret record %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -1858,7 +1870,8 @@ static NTSTATUS lsa_OpenSecret(struct dcesrv_call_state *dce_call, TALLOC_CTX *m
 		}
 		
 		if (ret != 1) {
-			DEBUG(0,("Found %d records matching DN %s\n", ret, policy_state->system_dn));
+			DEBUG(0,("Found %d records matching DN %s\n", ret,
+				 ldb_dn_linearize(mem_ctx, policy_state->system_dn)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	
@@ -1872,16 +1885,17 @@ static NTSTATUS lsa_OpenSecret(struct dcesrv_call_state *dce_call, TALLOC_CTX *m
 		}
 
 		/* search for the secret record */
-		ret = gendb_search(secret_state->sam_ldb,
-				   mem_ctx, "cn=LSA Secrets", &msgs, attrs,
-				   "(&(cn=%s)(objectclass=secret))", 
-				   name);
+		ret = gendb_search(secret_state->sam_ldb, mem_ctx,
+				   ldb_dn_explode(mem_ctx, "cn=LSA Secrets"),
+				   &msgs, attrs,
+				   "(&(cn=%s)(objectclass=secret))", name);
 		if (ret == 0) {
 			return NT_STATUS_OBJECT_NAME_NOT_FOUND;
 		}
 		
 		if (ret != 1) {
-			DEBUG(0,("Found %d records matching DN %s\n", ret, policy_state->system_dn));
+			DEBUG(0,("Found %d records matching DN %s\n", ret,
+				 ldb_dn_linearize(mem_ctx, policy_state->system_dn)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	} 
@@ -2032,7 +2046,8 @@ static NTSTATUS lsa_SetSecret(struct dcesrv_call_state *dce_call, TALLOC_CTX *me
 			}
 			
 			if (ret != 1) {
-				DEBUG(0,("Found %d records matching dn=%s\n", ret, secret_state->secret_dn));
+				DEBUG(0,("Found %d records matching dn=%s\n", ret,
+					 ldb_dn_linearize(mem_ctx, secret_state->secret_dn)));
 				return NT_STATUS_INTERNAL_DB_CORRUPTION;
 			}
 
diff --git a/source4/rpc_server/netlogon/dcerpc_netlogon.c b/source4/rpc_server/netlogon/dcerpc_netlogon.c
index aad66ad314..cea645cd02 100644
--- a/source4/rpc_server/netlogon/dcerpc_netlogon.c
+++ b/source4/rpc_server/netlogon/dcerpc_netlogon.c
@@ -956,7 +956,7 @@ static NTSTATUS netr_LogonGetDomainInfo(struct dcesrv_call_state *dce_call, TALL
 	ret = gendb_search(sam_ctx, mem_ctx, NULL, 
 			   &ref_res, ref_attrs, 
 			   "(&(objectClass=crossRef)(ncName=%s))", 
-			   res1[0]->dn);
+			   ldb_dn_linearize(mem_ctx, res1[0]->dn));
 	if (ret != 1) {
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
@@ -1261,7 +1261,8 @@ static WERROR netr_DsrEnumerateDomainTrusts(struct dcesrv_call_state *dce_call,
 		return WERR_GENERAL_FAILURE;
 	}
 
-	ret = gendb_search(sam_ctx, mem_ctx, NULL, &dom_res, dom_attrs, "(&(objectClass=domainDNS)(dnsDomain=%s))", lp_realm());
+	ret = gendb_search(sam_ctx, mem_ctx, NULL, &dom_res, dom_attrs,
+			   "(&(objectClass=domainDNS)(dnsDomain=%s))", lp_realm());
 	if (ret == -1) {
 		return WERR_GENERAL_FAILURE;		
 	}
@@ -1270,7 +1271,9 @@ static WERROR netr_DsrEnumerateDomainTrusts(struct dcesrv_call_state *dce_call,
 		return WERR_GENERAL_FAILURE;
 	}
 
-	ret = gendb_search(sam_ctx, mem_ctx, NULL, &ref_res, ref_attrs, "(&(objectClass=crossRef)(ncName=%s))", dom_res[0]->dn);
+	ret = gendb_search(sam_ctx, mem_ctx, NULL, &ref_res, ref_attrs,
+			   "(&(objectClass=crossRef)(ncName=%s))",
+			   ldb_dn_linearize(mem_ctx, dom_res[0]->dn));
 	if (ret == -1) {
 		return WERR_GENERAL_FAILURE;
 	}
diff --git a/source4/rpc_server/samr/dcesrv_samr.c b/source4/rpc_server/samr/dcesrv_samr.c
index 1e47199d20..81db2b386b 100644
--- a/source4/rpc_server/samr/dcesrv_samr.c
+++ b/source4/rpc_server/samr/dcesrv_samr.c
@@ -191,7 +191,8 @@ static NTSTATUS samr_LookupDomain(struct dcesrv_call_state *dce_call, TALLOC_CTX
 		}
 		
 		ret = gendb_search_dn(c_state->sam_ctx, mem_ctx, 
-				      samdb_result_string(ref_msgs[0], "ncName", NULL), 
+				      samdb_result_dn(mem_ctx,
+					ref_msgs[0], "ncName", NULL), 
 				      &dom_msgs, dom_attrs);
 	}
 
@@ -274,7 +275,7 @@ static NTSTATUS samr_EnumDomains(struct dcesrv_call_state *dce_call, TALLOC_CTX
 		ret = gendb_search(c_state->sam_ctx, mem_ctx, NULL, 
 				   &ref_msgs, ref_attrs, 
 				   "(&(objectClass=crossRef)(ncName=%s))", 
-				   dom_msgs[i]->dn);
+				   ldb_dn_linearize(mem_ctx, dom_msgs[i]->dn));
 		if (ret == 1) {
 			array->entries[i].name.string = samdb_result_string(ref_msgs[0], "nETBIOSName", NULL);
 		} else {
@@ -339,7 +340,7 @@ static NTSTATUS samr_OpenDomain(struct dcesrv_call_state *dce_call, TALLOC_CTX *
 		ret = gendb_search(c_state->sam_ctx,
 				   mem_ctx, NULL, &ref_msgs, ref_attrs,
 				   "(&(&(nETBIOSName=*)(objectclass=crossRef))(ncName=%s))", 
-				   dom_msgs[0]->dn);
+				   ldb_dn_linearize(mem_ctx, dom_msgs[0]->dn));
 		if (ret != 1) {
 			return NT_STATUS_NO_SUCH_DOMAIN;
 		}
@@ -359,7 +360,7 @@ static NTSTATUS samr_OpenDomain(struct dcesrv_call_state *dce_call, TALLOC_CTX *
 	d_state->sam_ctx = c_state->sam_ctx;
 	d_state->domain_sid = dom_sid_dup(d_state, r->in.sid);
 	d_state->domain_name = talloc_strdup(d_state, domain_name);
-	d_state->domain_dn = talloc_strdup(d_state, dom_msgs[0]->dn);
+	d_state->domain_dn = ldb_dn_copy(d_state, dom_msgs[0]->dn);
 	if (!d_state->domain_sid || !d_state->domain_name || !d_state->domain_dn) {
 		talloc_free(d_state);
 		return NT_STATUS_NO_MEMORY;		
@@ -553,8 +554,11 @@ static NTSTATUS samr_CreateDomainGroup(struct dcesrv_call_state *dce_call, TALLO
 	}
 
 	/* add core elements to the ldb_message for the user */
-	msg->dn = talloc_asprintf(mem_ctx, "CN=%s,CN=Users,%s", groupname,
-				  d_state->domain_dn);
+	msg->dn = ldb_dn_build_child(mem_ctx,
+				     "CN", groupname,
+				     ldb_dn_build_child(mem_ctx,
+							"CN", "Users",
+							d_state->domain_dn));
 	if (!msg->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -564,7 +568,8 @@ static NTSTATUS samr_CreateDomainGroup(struct dcesrv_call_state *dce_call, TALLO
 	/* create the group */
 	ret = samdb_add(d_state->sam_ctx, mem_ctx, msg);
 	if (ret != 0) {
-		DEBUG(0,("Failed to create group record %s\n", msg->dn));
+		DEBUG(0,("Failed to create group record %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -579,7 +584,8 @@ static NTSTATUS samr_CreateDomainGroup(struct dcesrv_call_state *dce_call, TALLO
 
 	/* retrieve the sid for the group just created */
 	sid = samdb_search_dom_sid(d_state->sam_ctx, a_state,
-				   msg->dn, "objectSid", "dn=%s", msg->dn);
+				   msg->dn, "objectSid", "dn=%s",
+				   ldb_dn_linearize(mem_ctx, msg->dn));
 	if (sid == NULL) {
 		return NT_STATUS_UNSUCCESSFUL;
 	}
@@ -789,7 +795,7 @@ static NTSTATUS samr_CreateUser2(struct dcesrv_call_state *dce_call, TALLOC_CTX
 	}
 
 	/* add core elements to the ldb_message for the user */
-	msg->dn = talloc_asprintf(mem_ctx, "CN=%s,CN=%s,%s", cn_name, container, d_state->domain_dn);
+	msg->dn = ldb_dn_build_child(mem_ctx, "CN", cn_name, ldb_dn_build_child(mem_ctx, "CN", container, d_state->domain_dn));
 	if (!msg->dn) {
 		return NT_STATUS_NO_MEMORY;		
 	}
@@ -798,7 +804,8 @@ static NTSTATUS samr_CreateUser2(struct dcesrv_call_state *dce_call, TALLOC_CTX
 	/* create the user */
 	ret = samdb_add(d_state->sam_ctx, mem_ctx, msg);
 	if (ret != 0) {
-		DEBUG(0,("Failed to create user record %s\n", msg->dn));
+		DEBUG(0,("Failed to create user record %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -813,7 +820,7 @@ static NTSTATUS samr_CreateUser2(struct dcesrv_call_state *dce_call, TALLOC_CTX
 
 	/* retrieve the sid for the user just created */
 	sid = samdb_search_dom_sid(d_state->sam_ctx, a_state,
-				   msg->dn, "objectSid", "dn=%s", msg->dn);
+				   msg->dn, "objectSid", "dn=%s", ldb_dn_linearize(mem_ctx, msg->dn));
 	if (sid == NULL) {
 		return NT_STATUS_UNSUCCESSFUL;
 	}
@@ -984,8 +991,11 @@ static NTSTATUS samr_CreateDomAlias(struct dcesrv_call_state *dce_call, TALLOC_C
 	}
 
 	/* add core elements to the ldb_message for the alias */
-	msg->dn = talloc_asprintf(mem_ctx, "CN=%s,CN=Users,%s", alias_name,
-				 d_state->domain_dn);
+	msg->dn = ldb_dn_build_child(mem_ctx,
+				     "CN", alias_name,
+				     ldb_dn_build_child(mem_ctx,
+							"CN", "Users",
+							d_state->domain_dn));
 	if (!msg->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -997,7 +1007,8 @@ static NTSTATUS samr_CreateDomAlias(struct dcesrv_call_state *dce_call, TALLOC_C
 	/* create the alias */
 	ret = samdb_add(d_state->sam_ctx, mem_ctx, msg);
 	if (ret != 0) {
-		DEBUG(0,("Failed to create alias record %s\n", msg->dn));
+		DEBUG(0,("Failed to create alias record %s\n",
+			 ldb_dn_linearize(mem_ctx, msg->dn)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 
@@ -1013,7 +1024,8 @@ static NTSTATUS samr_CreateDomAlias(struct dcesrv_call_state *dce_call, TALLOC_C
 
 	/* retrieve the sid for the alias just created */
 	sid = samdb_search_dom_sid(d_state->sam_ctx, a_state,
-				   msg->dn, "objectSid", "dn=%s", msg->dn);
+				   msg->dn, "objectSid", "dn=%s",
+				   ldb_dn_linearize(mem_ctx, msg->dn));
 
 	a_state->account_name = talloc_strdup(a_state, alias_name);
 	if (!a_state->account_name) {
@@ -1580,7 +1592,7 @@ static NTSTATUS samr_SetGroupInfo(struct dcesrv_call_state *dce_call, TALLOC_CTX
 		return NT_STATUS_NO_MEMORY;
 	}	
 
-	msg->dn = talloc_strdup(mem_ctx, a_state->account_dn);
+	msg->dn = ldb_dn_copy(mem_ctx, a_state->account_dn);
 	if (!msg->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -1813,7 +1825,7 @@ static NTSTATUS samr_QueryGroupMember(struct dcesrv_call_state *dce_call, TALLOC
 			struct ldb_message **res2;
 			const char * const attrs2[2] = { "objectSid", NULL };
 			ret = gendb_search_dn(a_state->sam_ctx, mem_ctx,
-					   (char *)el->values[i].data,
+					   ldb_dn_explode(mem_ctx, el->values[i].data),
 					   &res2, attrs2);
 			if (ret != 1)
 				return NT_STATUS_INTERNAL_DB_CORRUPTION;
@@ -2001,7 +2013,7 @@ static NTSTATUS samr_SetAliasInfo(struct dcesrv_call_state *dce_call, TALLOC_CTX
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	msg->dn = talloc_strdup(mem_ctx, a_state->account_dn);
+	msg->dn = ldb_dn_copy(mem_ctx, a_state->account_dn);
 	if (!msg->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -2069,7 +2081,7 @@ static NTSTATUS samr_AddAliasMember(struct dcesrv_call_state *dce_call, TALLOC_C
 	struct ldb_message *mod;
 	struct ldb_message **msgs;
 	const char * const attrs[2] = { "dn", NULL };
-	const char *memberdn = NULL;
+	struct ldb_dn *memberdn = NULL;
 	int ret;
 
 	DCESRV_PULL_HANDLE(h, r->in.alias_handle, SAMR_HANDLE_ALIAS);
@@ -2082,14 +2094,15 @@ static NTSTATUS samr_AddAliasMember(struct dcesrv_call_state *dce_call, TALLOC_C
 			   ldap_encode_ndr_dom_sid(mem_ctx, r->in.sid));
 
 	if (ret == 1) {
-		memberdn = ldb_msg_find_string(msgs[0], "dn", NULL);
+		memberdn = ldb_dn_explode(mem_ctx, ldb_msg_find_string(msgs[0], "dn", NULL));
 	} else 	if (ret > 1) {
 		DEBUG(0,("Found %d records matching sid %s\n", 
 			 ret, dom_sid_string(mem_ctx, r->in.sid)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	} else if (ret == 0) {
 		struct ldb_message *msg;
-		const char *basedn, *sidstr;
+		struct ldb_dn *basedn;
+		const char *sidstr;
 
 		sidstr = dom_sid_string(mem_ctx, r->in.sid);
 		NT_STATUS_HAVE_NO_MEMORY(sidstr);
@@ -2110,10 +2123,11 @@ static NTSTATUS samr_AddAliasMember(struct dcesrv_call_state *dce_call, TALLOC_C
 		 * cn=For...,cn=Builtin,dc={BASEDN}.  -- vl
 		 */
 
-		basedn = samdb_search_string(d_state->sam_ctx, mem_ctx, NULL,
-					     "dn",
-					     "(&(objectClass=container)"
-					     "(cn=ForeignSecurityPrincipals))");
+		basedn = ldb_dn_explode(mem_ctx,
+					samdb_search_string(d_state->sam_ctx,
+							    mem_ctx, NULL, "dn",
+							    "(&(objectClass=container)"
+							    "(cn=ForeignSecurityPrincipals))"));
 
 		if (basedn == NULL) {
 			DEBUG(0, ("Failed to find DN for "
@@ -2122,7 +2136,7 @@ static NTSTATUS samr_AddAliasMember(struct dcesrv_call_state *dce_call, TALLOC_C
 		}
 
 		/* add core elements to the ldb_message for the alias */
-		msg->dn = talloc_asprintf(mem_ctx, "CN=%s,%s", sidstr, basedn);
+		msg->dn = ldb_dn_build_child(mem_ctx, "CN", sidstr, basedn);
 		if (msg->dn == NULL)
 			return NT_STATUS_NO_MEMORY;
 
@@ -2136,7 +2150,7 @@ static NTSTATUS samr_AddAliasMember(struct dcesrv_call_state *dce_call, TALLOC_C
 		ret = samdb_add(d_state->sam_ctx, mem_ctx, msg);
 		if (ret != 0) {
 			DEBUG(0,("Failed to create foreignSecurityPrincipal "
-				 "record %s\n", msg->dn));
+				 "record %s\n", ldb_dn_linearize(mem_ctx, msg->dn)));
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 	} else {
@@ -2156,7 +2170,7 @@ static NTSTATUS samr_AddAliasMember(struct dcesrv_call_state *dce_call, TALLOC_C
 	mod->dn = talloc_reference(mem_ctx, a_state->account_dn);
 
 	if (samdb_msg_add_addval(d_state->sam_ctx, mem_ctx, mod, "member",
-				 memberdn) != 0)
+				 ldb_dn_linearize(mem_ctx, memberdn)) != 0)
 		return NT_STATUS_UNSUCCESSFUL;
 
 	if (samdb_modify(a_state->sam_ctx, mem_ctx, mod) != 0)
@@ -2252,7 +2266,7 @@ static NTSTATUS samr_GetMembersInAlias(struct dcesrv_call_state *dce_call, TALLO
 			struct ldb_message **msgs2;
 			const char * const attrs2[2] = { "objectSid", NULL };
 			ret = gendb_search_dn(a_state->sam_ctx, mem_ctx,
-					   (char *)el->values[i].data,
+					   ldb_dn_explode(mem_ctx, el->values[i].data),
 					   &msgs2, attrs2);
 			if (ret != 1)
 				return NT_STATUS_INTERNAL_DB_CORRUPTION;
@@ -2821,7 +2835,7 @@ static NTSTATUS samr_GetGroupsForUser(struct dcesrv_call_state *dce_call, TALLOC
 	count = samdb_search_domain(a_state->sam_ctx, mem_ctx, NULL, &res,
 				    attrs, d_state->domain_sid,
 				    "(&(member=%s)(grouptype=%s)(objectclass=group))",
-				    a_state->account_dn,
+				    ldb_dn_linearize(mem_ctx, a_state->account_dn),
 				    ldb_hexstr(mem_ctx,
 					       GTYPE_SECURITY_GLOBAL_GROUP));
 	if (count < 0)
@@ -3113,11 +3127,11 @@ static NTSTATUS samr_GetUserPwInfo(struct dcesrv_call_state *dce_call, TALLOC_CT
 	r->out.info.min_password_length = samdb_search_uint(a_state->sam_ctx, mem_ctx, 0,
 							    a_state->domain_state->domain_dn, "minPwdLength", 
 							    "dn=%s", 
-							    a_state->domain_state->domain_dn);
+							    ldb_dn_linearize(mem_ctx, a_state->domain_state->domain_dn));
 	r->out.info.password_properties = samdb_search_uint(a_state->sam_ctx, mem_ctx, 0,
 							    a_state->account_dn, 
-							    "pwdProperties", 
-							    "dn=%s", a_state->account_dn);
+							    "pwdProperties", "dn=%s",
+							    ldb_dn_linearize(mem_ctx, a_state->account_dn));
 	return NT_STATUS_OK;
 }
 
@@ -3170,9 +3184,7 @@ static NTSTATUS samr_RemoveMemberFromForeignDomain(struct dcesrv_call_state *dce
 			return NT_STATUS_NO_MEMORY;
 		}
 
-		mod->dn = talloc_reference(mod,
-					   samdb_result_string(res[i], "dn",
-							       NULL));
+		mod->dn = samdb_result_dn(mod, res[i], "dn", NULL);
 		if (mod->dn == NULL) {
 			talloc_free(mod);
 			continue;
diff --git a/source4/rpc_server/samr/dcesrv_samr.h b/source4/rpc_server/samr/dcesrv_samr.h
index 51e0869eef..8e53fa7a10 100644
--- a/source4/rpc_server/samr/dcesrv_samr.h
+++ b/source4/rpc_server/samr/dcesrv_samr.h
@@ -49,7 +49,7 @@ struct samr_domain_state {
 	uint32_t access_mask;
 	struct dom_sid *domain_sid;
 	const char *domain_name;
-	const char *domain_dn;
+	const struct ldb_dn *domain_dn;
 };
 
 /*
@@ -61,5 +61,5 @@ struct samr_account_state {
 	uint32_t access_mask;
 	struct dom_sid *account_sid;
 	const char *account_name;
-	const char *account_dn;
+	const struct ldb_dn *account_dn;
 };
diff --git a/source4/rpc_server/samr/samr_password.c b/source4/rpc_server/samr/samr_password.c
index 48abc7cfde..c862763101 100644
--- a/source4/rpc_server/samr/samr_password.c
+++ b/source4/rpc_server/samr/samr_password.c
@@ -108,7 +108,7 @@ NTSTATUS samr_ChangePasswordUser(struct dcesrv_call_state *dce_call, TALLOC_CTX
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	msg->dn = talloc_strdup(msg, a_state->account_dn);
+	msg->dn = ldb_dn_copy(msg, a_state->account_dn);
 	if (!msg->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -143,7 +143,7 @@ NTSTATUS samr_OemChangePasswordUser2(struct dcesrv_call_state *dce_call, TALLOC_
 	uint32_t new_pass_len;
 	struct samr_CryptPassword *pwbuf = r->in.password;
 	void *sam_ctx;
-	const char *user_dn, *domain_dn;
+	const struct ldb_dn *user_dn, *domain_dn;
 	int ret;
 	struct ldb_message **res, *mod;
 	const char * const attrs[] = { "objectSid", "lmPwdHash", "unicodePwd", NULL };
@@ -210,9 +210,10 @@ NTSTATUS samr_OemChangePasswordUser2(struct dcesrv_call_state *dce_call, TALLOC_
 		return NT_STATUS_NO_SUCH_USER;
 	}
 
-	domain_dn = samdb_search_string(sam_ctx, mem_ctx, NULL, "dn",
-					"(objectSid=%s)", 
-					ldap_encode_ndr_dom_sid(mem_ctx, domain_sid));
+	domain_dn = ldb_dn_explode(mem_ctx,
+				   samdb_search_string(sam_ctx, mem_ctx, NULL, "dn",
+							"(objectSid=%s)", 
+							ldap_encode_ndr_dom_sid(mem_ctx, domain_sid)));
 	if (!domain_dn) {
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
@@ -222,7 +223,7 @@ NTSTATUS samr_OemChangePasswordUser2(struct dcesrv_call_state *dce_call, TALLOC_
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	mod->dn = talloc_strdup(mod, user_dn);
+	mod->dn = ldb_dn_copy(mod, user_dn);
 	if (!mod->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -261,7 +262,7 @@ NTSTATUS samr_ChangePasswordUser3(struct dcesrv_call_state *dce_call,
 	char new_pass[512];
 	uint32_t new_pass_len;
 	void *sam_ctx = NULL;
-	const char *user_dn, *domain_dn = NULL;
+	const struct ldb_dn *user_dn, *domain_dn = NULL;
 	int ret;
 	struct ldb_message **res, *mod;
 	const char * const attrs[] = { "objectSid", "ntPwdHash", "lmPwdHash", "unicodePwd", NULL };
@@ -360,9 +361,10 @@ NTSTATUS samr_ChangePasswordUser3(struct dcesrv_call_state *dce_call,
 		goto failed;
 	}
 
-	domain_dn = samdb_search_string(sam_ctx, mem_ctx, NULL, "dn",
-					"(objectSid=%s)", 
-					ldap_encode_ndr_dom_sid(mem_ctx, domain_sid));
+	domain_dn = ldb_dn_explode(mem_ctx,
+				   samdb_search_string(sam_ctx, mem_ctx, NULL, "dn",
+							"(objectSid=%s)", 
+							ldap_encode_ndr_dom_sid(mem_ctx, domain_sid)));
 	if (!domain_dn) {
 		status = NT_STATUS_INTERNAL_DB_CORRUPTION;
 		goto failed;
@@ -373,7 +375,7 @@ NTSTATUS samr_ChangePasswordUser3(struct dcesrv_call_state *dce_call,
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	mod->dn = talloc_strdup(mod, user_dn);
+	mod->dn = ldb_dn_copy(mod, user_dn);
 	if (!mod->dn) {
 		status = NT_STATUS_NO_MEMORY;
 		goto failed;
@@ -485,7 +487,8 @@ static BOOL samdb_password_complexity_ok(const char *pass)
   changes (as is needed by some of the set user info levels)
 */
 NTSTATUS samdb_set_password(void *ctx, TALLOC_CTX *mem_ctx,
-			    const char *user_dn, const char *domain_dn,
+			    const struct ldb_dn *user_dn,
+			    const struct ldb_dn *domain_dn,
 			    struct ldb_message *mod,
 			    const char *new_pass,
 			    struct samr_Password *lmNewHash, 
@@ -743,7 +746,7 @@ NTSTATUS samdb_set_password(void *ctx, TALLOC_CTX *mem_ctx,
 */
 NTSTATUS samr_set_password(struct dcesrv_call_state *dce_call,
 			   void *sam_ctx,
-			   const char *account_dn, const char *domain_dn,
+			   const struct ldb_dn *account_dn, const struct ldb_dn *domain_dn,
 			   TALLOC_CTX *mem_ctx,
 			   struct ldb_message *msg, 
 			   struct samr_CryptPassword *pwbuf)
@@ -785,7 +788,7 @@ NTSTATUS samr_set_password(struct dcesrv_call_state *dce_call,
 */
 NTSTATUS samr_set_password_ex(struct dcesrv_call_state *dce_call,
 			      void *sam_ctx,
-			      const char *account_dn, const char *domain_dn,
+			      const struct ldb_dn *account_dn, const struct ldb_dn *domain_dn,
 			      TALLOC_CTX *mem_ctx,
 			      struct ldb_message *msg, 
 			      struct samr_CryptPasswordEx *pwbuf)
diff --git a/source4/scripting/ejs/mprutil.c b/source4/scripting/ejs/mprutil.c
index 700185f07e..8f1e5f71c8 100644
--- a/source4/scripting/ejs/mprutil.c
+++ b/source4/scripting/ejs/mprutil.c
@@ -161,7 +161,7 @@ static struct MprVar mprLdbMessage(struct ldb_context *ldb, struct ldb_message *
 	const char *multivalued[] = { "objectClass", "memberOf", "privilege", 
 					    "member", NULL };
 
-	var = mprObject(msg->dn);
+	var = mprObject(ldb_dn_linearize(msg, msg->dn));
 
 	for (i=0;i<msg->num_elements;i++) {
 		struct ldb_message_element *el = &msg->elements[i];
@@ -196,7 +196,7 @@ static struct MprVar mprLdbMessage(struct ldb_context *ldb, struct ldb_message *
 
 	/* add the dn if it is not already specified */
 	if (mprGetProperty(&var, "dn", 0) == 0) {
-		mprSetVar(&var, "dn", mprString(msg->dn));
+		mprSetVar(&var, "dn", mprString(ldb_dn_linearize(msg, msg->dn)));
 	}
 	
 	return var;		
diff --git a/source4/scripting/ejs/smbcalls_ldb.c b/source4/scripting/ejs/smbcalls_ldb.c
index 50ba6fce68..7d268d09f6 100644
--- a/source4/scripting/ejs/smbcalls_ldb.c
+++ b/source4/scripting/ejs/smbcalls_ldb.c
@@ -51,7 +51,8 @@ static int ejs_ldbSearch(MprVarHandle eid, int argc, struct MprVar **argv)
 {
 	const char **attrs = NULL;
 	const char *expression;
-	const char *basedn = NULL;
+	const char *base = NULL;
+	struct ldb_dn *basedn = NULL;
 	int scope = LDB_SCOPE_DEFAULT;
 	TALLOC_CTX *tmp_ctx = talloc_new(mprMemCtx());
 	struct ldb_context *ldb;
@@ -79,9 +80,16 @@ static int ejs_ldbSearch(MprVarHandle eid, int argc, struct MprVar **argv)
 		goto failed;
 	}
 	if (argc > 1) {
-		basedn = mprToString(argv[1]);
+		base = mprToString(argv[1]);
 		/* a null basedn is valid */
 	}
+	if (base != NULL) {
+		basedn = ldb_dn_explode(tmp_ctx, base);
+		if (basedn == NULL) {
+			ejsSetErrorMsg(eid, "ldb.search malformed base dn");
+			goto failed;
+		}
+	}
 	if (argc > 2) {
 		scope = mprToInt(argv[2]);
 		switch (scope) {
@@ -160,7 +168,7 @@ static int ejs_ldbAddModify(MprVarHandle eid, int argc, struct MprVar **argv,
 */
 static int ejs_ldbDelete(MprVarHandle eid, int argc, struct MprVar **argv)
 {
-	const char *dn;
+	struct ldb_dn *dn;
 	struct ldb_context *ldb;
 	int ret;
 
@@ -169,14 +177,21 @@ static int ejs_ldbDelete(MprVarHandle eid, int argc, struct MprVar **argv)
 		return -1;
 	}
 
-	dn = mprToString(argv[0]);
-
 	ldb = ejs_get_ldb_context(eid);
 	if (ldb == NULL) {
 		return -1;
 	}
+
+	dn = ldb_dn_explode(ldb, mprToString(argv[0]));
+	if (dn == NULL) {
+		ejsSetErrorMsg(eid, "ldb.delete malformed dn");
+		return -1;
+	}
+
 	ret = ldb_delete(ldb, dn);
 
+	talloc_free(dn);
+
 	mpr_Return(eid, mprCreateBoolVar(ret == 0));
 	return 0;
 }
@@ -188,7 +203,7 @@ static int ejs_ldbDelete(MprVarHandle eid, int argc, struct MprVar **argv)
 */
 static int ejs_ldbRename(MprVarHandle eid, int argc, struct MprVar **argv)
 {
-	const char *dn1, *dn2;
+	struct ldb_dn *dn1, *dn2;
 	struct ldb_context *ldb;
 	int ret;
 
@@ -197,20 +212,23 @@ static int ejs_ldbRename(MprVarHandle eid, int argc, struct MprVar **argv)
 		return -1;
 	}
 
-	dn1 = mprToString(argv[0]);
-	dn2 = mprToString(argv[1]);
-	if (dn1 == NULL || dn2 == NULL) {
-		ejsSetErrorMsg(eid, "ldb.rename invalid arguments");
+	ldb = ejs_get_ldb_context(eid);
+	if (ldb == NULL) {
 		return -1;
 	}
 
-	ldb = ejs_get_ldb_context(eid);
-	if (ldb == NULL) {
+	dn1 = ldb_dn_explode(ldb, mprToString(argv[0]));
+	dn2 = ldb_dn_explode(ldb, mprToString(argv[1]));
+	if (dn1 == NULL || dn2 == NULL) {
+		ejsSetErrorMsg(eid, "ldb.rename invalid or malformed arguments");
 		return -1;
 	}
 
 	ret = ldb_rename(ldb, dn1, dn2);
 
+	talloc_free(dn1);
+	talloc_free(dn2);
+
 	mpr_Return(eid, mprCreateBoolVar(ret == 0));
 	return 0;
 }
diff --git a/source4/torture/rpc/samsync.c b/source4/torture/rpc/samsync.c
index 988f94d904..b15ee98200 100644
--- a/source4/torture/rpc/samsync.c
+++ b/source4/torture/rpc/samsync.c
@@ -1025,13 +1025,13 @@ static BOOL samsync_handle_account(TALLOC_CTX *mem_ctx, struct samsync_state *sa
 	}
 
 	if ((account->privilege_entries && !e.out.privs)) {
-		printf("Account %s has privilages in SamSync, but not LSA\n",
+		printf("Account %s has privileges in SamSync, but not LSA\n",
 		       dom_sid_string(mem_ctx, dom_sid));
 		return False;
 	}
 
 	if (!account->privilege_entries && e.out.privs && e.out.privs->count) {
-		printf("Account %s has privilages in LSA, but not SamSync\n",
+		printf("Account %s has privileges in LSA, but not SamSync\n",
 		       dom_sid_string(mem_ctx, dom_sid));
 		return False;
 	}