r19831: Big ldb_dn optimization and interfaces enhancement patch

This patch changes a lot of the code in ldb_dn.c, and also
removes and add a number of manipulation functions around.

The aim is to avoid validating a dn if not necessary as the
validation code is necessarily slow. This is mainly to speed up
internal operations where input is not user generated and so we
can assume the DNs need no validation. The code is designed to
keep the data as a string if possible.

The code is not yet 100% perfect, but pass all the tests so far.
A memleak is certainly present, I'll work on that next.

Simo.
(This used to be commit a580c871d3784602a9cce32d33419e63c8236e63)

80 files changed, 1550 insertions, 1118 deletions

diff --git a/source4/auth/auth_sam.c b/source4/auth/auth_sam.c
index 8bfcab1eaf..08ba75e4f6 100644
--- a/source4/auth/auth_sam.c
+++ b/source4/auth/auth_sam.c
@@ -47,12 +47,12 @@ static NTSTATUS authsam_search_account(TALLOC_CTX *mem_ctx, struct ldb_context *
 	struct ldb_message **msgs_tmp;
 	struct ldb_message **msgs;
 	struct ldb_message **msgs_domain_ref;
-	const struct ldb_dn *partitions_basedn = samdb_partitions_dn(sam_ctx, mem_ctx);
+	struct ldb_dn *partitions_basedn = samdb_partitions_dn(sam_ctx, mem_ctx);
 
 	int ret;
 	int ret_domain;
 
-	const struct ldb_dn *domain_dn = NULL;
+	struct ldb_dn *domain_dn = NULL;
 
 	if (domain_name) {
 		char *escaped_domain = ldb_binary_encode_string(mem_ctx, domain_name);
@@ -76,7 +76,7 @@ static NTSTATUS authsam_search_account(TALLOC_CTX *mem_ctx, struct ldb_context *
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 
-		domain_dn = samdb_result_dn(mem_ctx, msgs_domain_ref[0], "nCName", NULL);
+		domain_dn = samdb_result_dn(sam_ctx, mem_ctx, msgs_domain_ref[0], "nCName", NULL);
 	}
 
 	/* pull the user attributes */
diff --git a/source4/auth/credentials/credentials_files.c b/source4/auth/credentials/credentials_files.c
index ecd89d2259..1cbc9d9c15 100644
--- a/source4/auth/credentials/credentials_files.c
+++ b/source4/auth/credentials/credentials_files.c
@@ -220,7 +220,7 @@ NTSTATUS cli_credentials_set_secrets(struct cli_credentials *cred,
 
 	/* search for the secret record */
 	ldb_ret = gendb_search(ldb,
-			       mem_ctx, ldb_dn_explode(mem_ctx, base), 
+			       mem_ctx, ldb_dn_new(mem_ctx, ldb, base), 
 			       &msgs, attrs,
 			       "%s", filter);
 	if (ldb_ret == 0) {
diff --git a/source4/auth/gensec/schannel_state.c b/source4/auth/gensec/schannel_state.c
index 3c9ff64147..7ba35abd19 100644
--- a/source4/auth/gensec/schannel_state.c
+++ b/source4/auth/gensec/schannel_state.c
@@ -93,8 +93,8 @@ NTSTATUS schannel_store_session_key_ldb(TALLOC_CTX *mem_ctx,
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	msg->dn = ldb_dn_build_child(msg, "computerName", creds->computer_name, NULL);
-	if (msg->dn == NULL) {
+	msg->dn = ldb_dn_new_fmt(msg, ldb, "computerName=%s", creds->computer_name);
+	if ( ! msg->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
 
diff --git a/source4/auth/sam.c b/source4/auth/sam.c
index c7f0a74ac9..34ce34540a 100644
--- a/source4/auth/sam.c
+++ b/source4/auth/sam.c
@@ -89,7 +89,7 @@ _PUBLIC_ NTSTATUS authsam_account_ok(TALLOC_CTX *mem_ctx,
 	NTTIME must_change_time;
 	NTTIME last_set_time;
 
-	struct ldb_dn *domain_dn = samdb_result_dn(mem_ctx, msg_domain_ref, "nCName", ldb_dn_new(mem_ctx));
+	struct ldb_dn *domain_dn = samdb_result_dn(sam_ctx, mem_ctx, msg_domain_ref, "nCName", ldb_dn_new(mem_ctx, sam_ctx, NULL));
 
 	NTTIME now;
 	DEBUG(4,("authsam_account_ok: Checking SMB password for user %s\n", name_for_logs));
@@ -287,7 +287,7 @@ _PUBLIC_ NTSTATUS authsam_make_server_info(TALLOC_CTX *mem_ctx, struct ldb_conte
 	server_info->acct_expiry = samdb_result_nttime(msg, "accountExpires", 0);
 	server_info->last_password_change = samdb_result_nttime(msg, "pwdLastSet", 0);
 
-	ncname = samdb_result_dn(mem_ctx, msg_domain_ref, "nCName", NULL);
+	ncname = samdb_result_dn(sam_ctx, mem_ctx, msg_domain_ref, "nCName", NULL);
 	if (!ncname) {
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
@@ -322,7 +322,7 @@ _PUBLIC_ NTSTATUS sam_get_results_principal(struct ldb_context *sam_ctx,
 	NTSTATUS nt_status;
 	TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
 	int ret;
-	const struct ldb_dn *partitions_basedn = samdb_partitions_dn(sam_ctx, mem_ctx);
+	struct ldb_dn *partitions_basedn = samdb_partitions_dn(sam_ctx, mem_ctx);
 
 	if (!tmp_ctx) {
 		return NT_STATUS_NO_MEMORY;
diff --git a/source4/cldap_server/netlogon.c b/source4/cldap_server/netlogon.c
index fd00c43cda..6de505659f 100644
--- a/source4/cldap_server/netlogon.c
+++ b/source4/cldap_server/netlogon.c
@@ -62,7 +62,7 @@ static NTSTATUS cldapd_netlogon_fill(struct cldapd_server *cldapd,
 	const char *server_site;
 	const char *client_site;
 	const char *pdc_ip;
-	const struct ldb_dn *partitions_basedn;
+	struct ldb_dn *partitions_basedn;
 
 	partitions_basedn = samdb_partitions_dn(cldapd->samctx, mem_ctx);
 
@@ -79,7 +79,7 @@ static NTSTATUS cldapd_netlogon_fill(struct cldapd_server *cldapd,
 				   "(&(&(objectClass=crossRef)(dnsRoot=%s))(nETBIOSName=*))", 
 				   domain);
 		if (count == 1) {
-			dom_dn = samdb_result_dn(mem_ctx, ref_res[0], "ncName", NULL);
+			dom_dn = samdb_result_dn(cldapd->samctx, mem_ctx, ref_res[0], "ncName", NULL);
 			if (!dom_dn) {
 				return NT_STATUS_NO_SUCH_DOMAIN;
 			}
diff --git a/source4/cldap_server/rootdse.c b/source4/cldap_server/rootdse.c
index 966b90889c..0690e8769a 100644
--- a/source4/cldap_server/rootdse.c
+++ b/source4/cldap_server/rootdse.c
@@ -51,7 +51,7 @@ static void cldapd_rootdse_fill(struct cldapd_server *cldapd,
 	int ret = 0;
 	int ldb_ret = -1;
 
-	basedn = ldb_dn_explode(mem_ctx, "");
+	basedn = ldb_dn_new(mem_ctx, cldapd->samctx, NULL);
 	if (basedn == NULL) goto nomem;
 	scope = LDB_SCOPE_BASE;
 
diff --git a/source4/dsdb/samdb/cracknames.c b/source4/dsdb/samdb/cracknames.c
index eb051a0fb2..16aa616983 100644
--- a/source4/dsdb/samdb/cracknames.c
+++ b/source4/dsdb/samdb/cracknames.c
@@ -38,12 +38,12 @@
 static WERROR DsCrackNameOneFilter(struct ldb_context *sam_ctx, TALLOC_CTX *mem_ctx,
 				   struct smb_krb5_context *smb_krb5_context,
 				   uint32_t format_flags, uint32_t format_offered, uint32_t format_desired,
-				   const struct ldb_dn *name_dn, const char *name, 
+				   struct ldb_dn *name_dn, const char *name, 
 				   const char *domain_filter, const char *result_filter, 
 				   struct drsuapi_DsNameInfo1 *info1);
 static WERROR DsCrackNameOneSyntactical(TALLOC_CTX *mem_ctx,
 					uint32_t format_offered, uint32_t format_desired,
-					const struct ldb_dn *name_dn, const char *name, 
+					struct ldb_dn *name_dn, const char *name, 
 					struct drsuapi_DsNameInfo1 *info1);
 
 static enum drsuapi_DsNameStatus LDB_lookup_spn_alias(krb5_context context, struct ldb_context *ldb_ctx, 
@@ -69,10 +69,14 @@ static enum drsuapi_DsNameStatus LDB_lookup_spn_alias(krb5_context context, stru
 		return DRSUAPI_DS_NAME_STATUS_RESOLVE_ERROR;
 	}
 
-	service_dn = ldb_dn_string_compose(tmp_ctx, samdb_base_dn(ldb_ctx),
-					   "CN=Directory Service,CN=Windows NT"
-					   ",CN=Services,CN=Configuration");
+	service_dn = ldb_dn_new(tmp_ctx, ldb_ctx, "CN=Directory Service,CN=Windows NT,CN=Services,CN=Configuration");
+	if ( ! ldb_dn_add_base(service_dn, samdb_base_dn(ldb_ctx))) {
+		return DRSUAPI_DS_NAME_STATUS_RESOLVE_ERROR;
+	}
 	service_dn_str = ldb_dn_linearize(tmp_ctx, service_dn);
+	if ( ! service_dn_str) {
+		return DRSUAPI_DS_NAME_STATUS_RESOLVE_ERROR;
+	}
 
 	ret = ldb_search(ldb_ctx, service_dn, LDB_SCOPE_BASE, "(objectClass=nTDSService)",
 			 directory_attrs, &res);
@@ -358,9 +362,9 @@ WERROR DsCrackNameOneName(struct ldb_context *sam_ctx, TALLOC_CTX *mem_ctx,
 
 		/* A LDAP DN as a string */
 	case DRSUAPI_DS_NAME_FORMAT_FQDN_1779: {
-		name_dn = ldb_dn_explode(mem_ctx, name);
 		domain_filter = NULL;
-		if (!name_dn) {
+		name_dn = ldb_dn_new(mem_ctx, sam_ctx, name);
+		if (! ldb_dn_validate(name_dn)) {
 			info1->status = DRSUAPI_DS_NAME_STATUS_NOT_FOUND;
 			return WERR_OK;
 		}
@@ -534,7 +538,7 @@ WERROR DsCrackNameOneName(struct ldb_context *sam_ctx, TALLOC_CTX *mem_ctx,
 
 static WERROR DsCrackNameOneSyntactical(TALLOC_CTX *mem_ctx,
 					uint32_t format_offered, uint32_t format_desired,
-					const struct ldb_dn *name_dn, const char *name, 
+					struct ldb_dn *name_dn, const char *name, 
 					struct drsuapi_DsNameInfo1 *info1)
 {
 	char *cracked;
@@ -573,7 +577,7 @@ static WERROR DsCrackNameOneSyntactical(TALLOC_CTX *mem_ctx,
 static WERROR DsCrackNameOneFilter(struct ldb_context *sam_ctx, TALLOC_CTX *mem_ctx,
 				   struct smb_krb5_context *smb_krb5_context,
 				   uint32_t format_flags, uint32_t format_offered, uint32_t format_desired,
-				   const struct ldb_dn *name_dn, const char *name, 
+				   struct ldb_dn *name_dn, const char *name, 
 				   const char *domain_filter, const char *result_filter, 
 				   struct drsuapi_DsNameInfo1 *info1)
 {
@@ -582,8 +586,8 @@ static WERROR DsCrackNameOneFilter(struct ldb_context *sam_ctx, TALLOC_CTX *mem_
 	const char * const *domain_attrs;
 	const char * const *result_attrs;
 	struct ldb_message **result_res = NULL;
-	const struct ldb_dn *result_basedn;
-	const struct ldb_dn *partitions_basedn = samdb_partitions_dn(sam_ctx, mem_ctx);
+	struct ldb_dn *result_basedn;
+	struct ldb_dn *partitions_basedn = samdb_partitions_dn(sam_ctx, mem_ctx);
 
 	const char * const _domain_attrs_1779[] = { "ncName", "dnsRoot", NULL};
 	const char * const _result_attrs_null[] = { NULL };
@@ -655,7 +659,7 @@ static WERROR DsCrackNameOneFilter(struct ldb_context *sam_ctx, TALLOC_CTX *mem_
 	info1->status		= DRSUAPI_DS_NAME_STATUS_DOMAIN_ONLY;
 
 	if (result_filter) {
-		result_basedn = samdb_result_dn(mem_ctx, domain_res[0], "ncName", NULL);
+		result_basedn = samdb_result_dn(sam_ctx, mem_ctx, domain_res[0], "ncName", NULL);
 		
 		ldb_ret = gendb_search(sam_ctx, mem_ctx, result_basedn, &result_res,
 				       result_attrs, "%s", result_filter);
@@ -663,7 +667,7 @@ static WERROR DsCrackNameOneFilter(struct ldb_context *sam_ctx, TALLOC_CTX *mem_
 		ldb_ret = gendb_search_dn(sam_ctx, mem_ctx, name_dn, &result_res,
 					  result_attrs);
 	} else {
-		name_dn = samdb_result_dn(mem_ctx, domain_res[0], "ncName", NULL);
+		name_dn = samdb_result_dn(sam_ctx, mem_ctx, domain_res[0], "ncName", NULL);
 		ldb_ret = gendb_search_dn(sam_ctx, mem_ctx, name_dn, &result_res,
 					  result_attrs);
 	}
@@ -830,7 +834,7 @@ NTSTATUS crack_user_principal_name(struct ldb_context *sam_ctx,
 		return NT_STATUS_UNSUCCESSFUL;
 	}
 	
-	*user_dn = ldb_dn_explode(mem_ctx, info1.result_name);
+	*user_dn = ldb_dn_new(mem_ctx, sam_ctx, info1.result_name);
 	
 	if (domain_dn) {
 		werr = DsCrackNameOneName(sam_ctx, mem_ctx, 0,
@@ -854,7 +858,7 @@ NTSTATUS crack_user_principal_name(struct ldb_context *sam_ctx,
 			return NT_STATUS_UNSUCCESSFUL;
 		}
 		
-		*domain_dn = ldb_dn_explode(mem_ctx, info1.result_name);
+		*domain_dn = ldb_dn_new(mem_ctx, sam_ctx, info1.result_name);
 	}
 
 	return NT_STATUS_OK;
@@ -893,7 +897,7 @@ NTSTATUS crack_service_principal_name(struct ldb_context *sam_ctx,
 		return NT_STATUS_UNSUCCESSFUL;
 	}
 	
-	*user_dn = ldb_dn_explode(mem_ctx, info1.result_name);
+	*user_dn = ldb_dn_new(mem_ctx, sam_ctx, info1.result_name);
 	
 	if (domain_dn) {
 		werr = DsCrackNameOneName(sam_ctx, mem_ctx, 0,
@@ -917,7 +921,7 @@ NTSTATUS crack_service_principal_name(struct ldb_context *sam_ctx,
 			return NT_STATUS_UNSUCCESSFUL;
 		}
 		
-		*domain_dn = ldb_dn_explode(mem_ctx, info1.result_name);
+		*domain_dn = ldb_dn_new(mem_ctx, sam_ctx, info1.result_name);
 	}
 
 	return NT_STATUS_OK;
diff --git a/source4/dsdb/samdb/ldb_modules/entryUUID.c b/source4/dsdb/samdb/ldb_modules/entryUUID.c
index 38f366dfa2..2bc97f2040 100644
--- a/source4/dsdb/samdb/ldb_modules/entryUUID.c
+++ b/source4/dsdb/samdb/ldb_modules/entryUUID.c
@@ -112,7 +112,7 @@ static struct ldb_val objectCategory_always_dn(struct ldb_module *module, TALLOC
 	struct entryUUID_private *entryUUID_private;
 	struct ldb_result *list;
 
-	if (ldb_dn_explode(ctx, (const char *)val->data)) {
+	if (ldb_dn_validate(ldb_dn_new(ctx, module->ldb, (const char *)val->data))) {
 		return *val;
 	}
 	map_private = talloc_get_type(module->private_data, struct map_private);
@@ -415,7 +415,7 @@ static struct ldb_dn *find_schema_dn(struct ldb_context *ldb, TALLOC_CTX *mem_ct
 {
 	const char *rootdse_attrs[] = {"schemaNamingContext", NULL};
 	struct ldb_dn *schema_dn;
-	struct ldb_dn *basedn = ldb_dn_explode(mem_ctx, "");
+	struct ldb_dn *basedn = ldb_dn_new(mem_ctx, ldb, NULL);
 	struct ldb_result *rootdse_res;
 	int ldb_ret;
 	if (!basedn) {
@@ -436,7 +436,7 @@ static struct ldb_dn *find_schema_dn(struct ldb_context *ldb, TALLOC_CTX *mem_ct
 	}
 	
 	/* Locate schema */
-	schema_dn = ldb_msg_find_attr_as_dn(mem_ctx, rootdse_res->msgs[0], "schemaNamingContext");
+	schema_dn = ldb_msg_find_attr_as_dn(ldb, mem_ctx, rootdse_res->msgs[0], "schemaNamingContext");
 	if (!schema_dn) {
 		return NULL;
 	}
@@ -490,8 +490,8 @@ static int get_remote_rootdse(struct ldb_context *ldb, void *context,
 			if (!entryUUID_private->base_dns) {
 				return LDB_ERR_OPERATIONS_ERROR;
 			}
-			entryUUID_private->base_dns[i] = ldb_dn_explode(entryUUID_private->base_dns, (const char *)el->values[i].data);
-			if (!entryUUID_private->base_dns[i]) {
+			entryUUID_private->base_dns[i] = ldb_dn_new(entryUUID_private->base_dns, ldb, (const char *)el->values[i].data);
+			if ( ! ldb_dn_validate(entryUUID_private->base_dns[i])) {
 				return LDB_ERR_OPERATIONS_ERROR;
 			}
 		}
@@ -517,7 +517,7 @@ static int find_base_dns(struct ldb_module *module,
 	}
 
 	req->operation = LDB_SEARCH;
-	req->op.search.base = ldb_dn_new(req);
+	req->op.search.base = ldb_dn_new(req, module->ldb, NULL);
 	req->op.search.scope = LDB_SCOPE_BASE;
 
 	req->op.search.tree = ldb_parse_tree(req, "objectClass=*");
diff --git a/source4/dsdb/samdb/ldb_modules/extended_dn.c b/source4/dsdb/samdb/ldb_modules/extended_dn.c
index 64600fff8b..012ac74514 100644
--- a/source4/dsdb/samdb/ldb_modules/extended_dn.c
+++ b/source4/dsdb/samdb/ldb_modules/extended_dn.c
@@ -97,6 +97,7 @@ static BOOL add_attrs(void *mem_ctx, char ***attrs, const char *attr)
 }
 
 static BOOL inject_extended_dn(struct ldb_message *msg,
+				struct ldb_context *ldb,
 				int type,
 				BOOL remove_guid,
 				BOOL remove_sid)
@@ -152,8 +153,8 @@ static BOOL inject_extended_dn(struct ldb_message *msg,
 	if (!new_dn)
 		return False;
 
-	msg->dn = ldb_dn_explode_or_special(msg, new_dn);
-	if (!msg->dn)
+	msg->dn = ldb_dn_new(msg, ldb, new_dn);
+	if (! ldb_dn_validate(msg->dn))
 		return False;
 
 	val = ldb_msg_find_ldb_val(msg, "distinguishedName");
@@ -193,7 +194,7 @@ static int extended_callback(struct ldb_context *ldb, void *context, struct ldb_
 	if (ares->type == LDB_REPLY_ENTRY) {
 		/* for each record returned post-process to add any derived
 		   attributes that have been asked for */
-		if (!inject_extended_dn(ares->message, ac->extended_type, ac->remove_guid, ac->remove_sid)) {
+		if (!inject_extended_dn(ares->message, ldb, ac->extended_type, ac->remove_guid, ac->remove_sid)) {
 			goto error;
 		}
 	}
diff --git a/source4/dsdb/samdb/ldb_modules/kludge_acl.c b/source4/dsdb/samdb/ldb_modules/kludge_acl.c
index 088f2657cc..176cfbf3a5 100644
--- a/source4/dsdb/samdb/ldb_modules/kludge_acl.c
+++ b/source4/dsdb/samdb/ldb_modules/kludge_acl.c
@@ -231,7 +231,7 @@ static int kludge_acl_init(struct ldb_module *module)
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	ret = ldb_search(module->ldb, ldb_dn_explode(mem_ctx, "@KLUDGEACL"),
+	ret = ldb_search(module->ldb, ldb_dn_new(mem_ctx, module->ldb, "@KLUDGEACL"),
 			 LDB_SCOPE_BASE,
 			 NULL, attrs,
 			 &res);
diff --git a/source4/dsdb/samdb/ldb_modules/local_password.c b/source4/dsdb/samdb/ldb_modules/local_password.c
index b5cff0272d..57323d859f 100644
--- a/source4/dsdb/samdb/ldb_modules/local_password.c
+++ b/source4/dsdb/samdb/ldb_modules/local_password.c
@@ -140,8 +140,7 @@ static int local_password_add(struct ldb_module *module, struct ldb_request *req
 	}
 
 	/* If the caller is manipulating the local passwords directly, let them pass */
-	if (ldb_dn_compare_base(module->ldb, 
-				ldb_dn_explode(req, LOCAL_BASE),
+	if (ldb_dn_compare_base(ldb_dn_new(req, module->ldb, LOCAL_BASE),
 				req->op.add.message->dn) == 0) {
 		return ldb_next_request(module, req);
 	}
@@ -225,9 +224,8 @@ static int local_password_add(struct ldb_module *module, struct ldb_request *req
 	/* Find the objectGUID to use as the key */
 	objectGUID = samdb_result_guid(ac->orig_req->op.add.message, "objectGUID");
 	
-	local_message->dn = ldb_dn_string_compose(local_message,
-						  ldb_dn_explode(local_message, LOCAL_BASE),
-						  PASSWORD_GUID_ATTR "=%s", GUID_string(local_message, &objectGUID));
+	local_message->dn = ldb_dn_new(local_message, module->ldb, LOCAL_BASE);
+	ldb_dn_add_child_fmt(local_message->dn, PASSWORD_GUID_ATTR "=%s", GUID_string(local_message, &objectGUID));
 
 	ac->local_req->op.add.message = local_message;
 
@@ -276,8 +274,7 @@ static int local_password_modify(struct ldb_module *module, struct ldb_request *
 	}
 
 	/* If the caller is manipulating the local passwords directly, let them pass */
-	if (ldb_dn_compare_base(module->ldb, 
-				ldb_dn_explode(req, LOCAL_BASE),
+	if (ldb_dn_compare_base(ldb_dn_new(req, module->ldb, LOCAL_BASE),
 				req->op.mod.message->dn) == 0) {
 		return ldb_next_request(module, req);
 	}
@@ -447,9 +444,8 @@ static int local_password_mod_local(struct ldb_handle *h) {
 	
 	objectGUID = samdb_result_guid(ac->search_res->message, "objectGUID");
 
-	ac->local_message->dn = ldb_dn_string_compose(ac,
-						      ldb_dn_explode(ac, LOCAL_BASE),
-						      PASSWORD_GUID_ATTR "=%s", GUID_string(ac, &objectGUID));
+	ac->local_message->dn = ldb_dn_new(ac, ac->module->ldb, LOCAL_BASE);
+	ldb_dn_add_child_fmt(ac->local_message->dn, PASSWORD_GUID_ATTR "=%s", GUID_string(ac, &objectGUID));
 
 	h->state = LDB_ASYNC_INIT;
 	h->status = LDB_SUCCESS;
@@ -591,10 +587,8 @@ static int lpdb_remote_search_callback(struct ldb_context *ldb, void *context, s
 		local_context->remote_res = ares;
 		local_context->local_res = NULL;
 
-		req->op.search.base = ldb_dn_string_compose(ac,
-							    ldb_dn_explode(ac, LOCAL_BASE),
-							    PASSWORD_GUID_ATTR "=%s", GUID_string(ac, &objectGUID));
-		if (!req->op.search.base) {
+		req->op.search.base = ldb_dn_new(ac, ac->module->ldb, LOCAL_BASE);
+		if ( ! ldb_dn_add_child_fmt(req->op.search.base, PASSWORD_GUID_ATTR "=%s", GUID_string(ac, &objectGUID))) {
 			return LDB_ERR_OPERATIONS_ERROR;
 		}
 		req->operation = LDB_SEARCH;
@@ -642,8 +636,7 @@ static int local_password_search(struct ldb_module *module, struct ldb_request *
 	}
 
 	/* If the caller is searching for the local passwords directly, let them pass */
-	if (ldb_dn_compare_base(module->ldb, 
-				ldb_dn_explode(req, LOCAL_BASE),
+	if (ldb_dn_compare_base(ldb_dn_new(req, module->ldb, LOCAL_BASE),
 				req->op.search.base) == 0) {
 		return ldb_next_request(module, req);
 	}
diff --git a/source4/dsdb/samdb/ldb_modules/partition.c b/source4/dsdb/samdb/ldb_modules/partition.c
index d678364b6e..625c846bdc 100644
--- a/source4/dsdb/samdb/ldb_modules/partition.c
+++ b/source4/dsdb/samdb/ldb_modules/partition.c
@@ -100,7 +100,7 @@ struct ldb_module *make_module_for_next_request(TALLOC_CTX *mem_ctx,
 	return current;
 }
 
-struct ldb_module *find_backend(struct ldb_module *module, struct ldb_request *req, const struct ldb_dn *dn)
+struct ldb_module *find_backend(struct ldb_module *module, struct ldb_request *req, struct ldb_dn *dn)
 {
 	int i;
 	struct partition_private_data *data = talloc_get_type(module->private_data, 
@@ -109,8 +109,7 @@ struct ldb_module *find_backend(struct ldb_module *module, struct ldb_request *r
 	/* Figure out which partition it is under */
 	/* Skip the lot if 'data' isn't here yet (initialistion) */
 	for (i=0; data && data->partitions && data->partitions[i]; i++) {
-		if (ldb_dn_compare_base(module->ldb, 
-					data->partitions[i]->dn, 
+		if (ldb_dn_compare_base(data->partitions[i]->dn, 
 					dn) == 0) {
 			return make_module_for_next_request(req, module->ldb, data->partitions[i]->module);
 		}
@@ -210,8 +209,7 @@ static int partition_send_request(struct partition_context *ac, struct ldb_modul
 		/* If the search is for 'more' than this partition,
 		 * then change the basedn, so a remote LDAP server
 		 * doesn't object */
-		if (ldb_dn_compare_base(ac->module->ldb, 
-					partition_base_dn, req->op.search.base) != 0) {
+		if (ldb_dn_compare_base(partition_base_dn, req->op.search.base) != 0) {
 			req->op.search.base = partition_base_dn;
 		}
 		req->callback = partition_search_callback;
@@ -253,7 +251,7 @@ static int partition_send_all(struct ldb_module *module,
 
 /* Figure out which backend a request needs to be aimed at.  Some
  * requests must be replicated to all backends */
-static int partition_replicate(struct ldb_module *module, struct ldb_request *req, const struct ldb_dn *dn) 
+static int partition_replicate(struct ldb_module *module, struct ldb_request *req, struct ldb_dn *dn) 
 {
 	int i;
 	struct ldb_module *backend;
@@ -262,8 +260,7 @@ static int partition_replicate(struct ldb_module *module, struct ldb_request *re
 	
 	/* Is this a special DN, we need to replicate to every backend? */
 	for (i=0; data->replicate && data->replicate[i]; i++) {
-		if (ldb_dn_compare(module->ldb, 
-				   data->replicate[i], 
+		if (ldb_dn_compare(data->replicate[i], 
 				   dn) == 0) {
 			struct ldb_handle *h;
 			struct partition_context *ac;
@@ -316,13 +313,12 @@ static int partition_search(struct ldb_module *module, struct ldb_request *req)
 		ac = talloc_get_type(h->private_data, struct partition_context);
 		
 		/* Search from the base DN */
-		if (!req->op.search.base || (ldb_dn_get_comp_num(req->op.search.base) == 0)) {
+		if (!req->op.search.base || ldb_dn_is_null(req->op.search.base)) {
 			return partition_send_all(module, ac, req);
 		}
 		for (i=0; data && data->partitions && data->partitions[i]; i++) {
 			/* Find all partitions under the search base */
-			if (ldb_dn_compare_base(module->ldb, 
-						req->op.search.base,
+			if (ldb_dn_compare_base(req->op.search.base,
 						data->partitions[i]->dn) == 0) {
 				ret = partition_send_request(ac, data->partitions[i]->module, data->partitions[i]->dn);
 				if (ret != LDB_SUCCESS) {
@@ -577,13 +573,12 @@ static int partition_sequence_number(struct ldb_module *module, struct ldb_reque
 static int sort_compare(void *void1,
 			void *void2, void *opaque)
 {
-	struct ldb_context *ldb = talloc_get_type(opaque, struct ldb_context);
 	struct partition **pp1 = void1;
 	struct partition **pp2 = void2;
 	struct partition *partition1 = talloc_get_type(*pp1, struct partition);
 	struct partition *partition2 = talloc_get_type(*pp2, struct partition);
 
-	return ldb_dn_compare(ldb, partition1->dn, partition2->dn);
+	return ldb_dn_compare(partition1->dn, partition2->dn);
 }
 
 static int partition_init(struct ldb_module *module)
@@ -608,7 +603,7 @@ static int partition_init(struct ldb_module *module)
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	ret = ldb_search(module->ldb, ldb_dn_explode(mem_ctx, "@PARTITION"),
+	ret = ldb_search(module->ldb, ldb_dn_new(mem_ctx, module->ldb, "@PARTITION"),
 			 LDB_SCOPE_BASE,
 			 NULL, attrs,
 			 &res);
@@ -665,7 +660,7 @@ static int partition_init(struct ldb_module *module)
 			return LDB_ERR_OPERATIONS_ERROR;
 		}
 
-		data->partitions[i]->dn = ldb_dn_explode(data->partitions[i], base);
+		data->partitions[i]->dn = ldb_dn_new(data->partitions[i], module->ldb, base);
 		if (!data->partitions[i]->dn) {
 			ldb_asprintf_errstring(module->ldb, 
 						"partition_init: invalid DN in partition record: %s", base);
@@ -718,8 +713,8 @@ static int partition_init(struct ldb_module *module)
 		}
 		
 		for (i=0; i < replicate_attributes->num_values; i++) {
-			data->replicate[i] = ldb_dn_explode(data->replicate, (const char *)replicate_attributes->values[i].data);
-			if (!data->replicate[i]) {
+			data->replicate[i] = ldb_dn_new(data->replicate, module->ldb, (const char *)replicate_attributes->values[i].data);
+			if (!ldb_dn_validate(data->replicate[i])) {
 				ldb_asprintf_errstring(module->ldb, 
 							"partition_init: "
 							"invalid DN in partition replicate record: %s", 
@@ -765,14 +760,14 @@ static int partition_init(struct ldb_module *module)
 			modules = ldb_modules_list_from_string(module->ldb, mem_ctx,
 							       p);
 			
-			base_dn = ldb_dn_explode(mem_ctx, base);
-			if (!base_dn) {
+			base_dn = ldb_dn_new(mem_ctx, module->ldb, base);
+			if (!ldb_dn_validate(base_dn)) {
 				talloc_free(mem_ctx);
 				return LDB_ERR_OPERATIONS_ERROR;
 			}
 			
 			for (partition_idx = 0; data->partitions[partition_idx]; partition_idx++) {
-				if (ldb_dn_compare(module->ldb, data->partitions[partition_idx]->dn, 
+				if (ldb_dn_compare(data->partitions[partition_idx]->dn, 
 						   base_dn) == 0) {
 					partition = data->partitions[partition_idx];
 					break;
diff --git a/source4/dsdb/samdb/ldb_modules/password_hash.c b/source4/dsdb/samdb/ldb_modules/password_hash.c
index 1b35ec3e8c..b25beb7a8f 100644
--- a/source4/dsdb/samdb/ldb_modules/password_hash.c
+++ b/source4/dsdb/samdb/ldb_modules/password_hash.c
@@ -588,8 +588,7 @@ static int password_hash_add(struct ldb_module *module, struct ldb_request *req)
 	}
 
 	/* If the caller is manipulating the local passwords directly, let them pass */
-	if (ldb_dn_compare_base(module->ldb, 
-				ldb_dn_explode(req, LOCAL_BASE),
+	if (ldb_dn_compare_base(ldb_dn_new(req, module->ldb, LOCAL_BASE),
 				req->op.add.message->dn) == 0) {
 		return ldb_next_request(module, req);
 	}
@@ -783,8 +782,7 @@ static int password_hash_modify(struct ldb_module *module, struct ldb_request *r
 	}
 	
 	/* If the caller is manipulating the local passwords directly, let them pass */
-	if (ldb_dn_compare_base(module->ldb, 
-				ldb_dn_explode(req, LOCAL_BASE),
+	if (ldb_dn_compare_base(ldb_dn_new(req, module->ldb, LOCAL_BASE),
 				req->op.mod.message->dn) == 0) {
 		return ldb_next_request(module, req);
 	}
diff --git a/source4/dsdb/samdb/ldb_modules/proxy.c b/source4/dsdb/samdb/ldb_modules/proxy.c
index d2628f5d1d..41fe8b68c9 100644
--- a/source4/dsdb/samdb/ldb_modules/proxy.c
+++ b/source4/dsdb/samdb/ldb_modules/proxy.c
@@ -70,7 +70,7 @@ static int load_proxy_info(struct ldb_module *module)
 		return 0;
 	}
 
-	dn = ldb_dn_explode(proxy, "@PROXYINFO");
+	dn = ldb_dn_new(proxy, module->ldb, "@PROXYINFO");
 	if (dn == NULL) {
 		goto failed;
 	}
@@ -94,13 +94,13 @@ static int load_proxy_info(struct ldb_module *module)
 		goto failed;
 	}
 
-	proxy->olddn = ldb_dn_explode(proxy, olddn);
+	proxy->olddn = ldb_dn_new(proxy, module->ldb, olddn);
 	if (proxy->olddn == NULL) {
 		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "Failed to explode olddn '%s'\n", olddn);
 		goto failed;
 	}
 	
-	proxy->newdn = ldb_dn_explode(proxy, newdn);
+	proxy->newdn = ldb_dn_new(proxy, module->ldb, newdn);
 	if (proxy->newdn == NULL) {
 		ldb_debug(module->ldb, LDB_DEBUG_FATAL, "Failed to explode newdn '%s'\n", newdn);
 		goto failed;
@@ -226,9 +226,8 @@ static void proxy_convert_record(struct ldb_module *module, struct ldb_message *
 	
 	/* fix the message DN */
 	if (ldb_dn_compare_base(module->ldb, proxy->olddn, msg->dn) == 0) {
-		struct ldb_dn *newdn = ldb_dn_copy(msg, msg->dn);
-		newdn->comp_num -= proxy->olddn->comp_num;
-		msg->dn = ldb_dn_compose(msg, newdn, proxy->newdn);
+		ldb_dn_remove_base_components(msg->dn, ldb_dn_get_comp_num(proxy->olddn));
+		ldb_dn_add_base(msg->dn, proxy->newdn);
 	}
 
 	/* fix any attributes */
@@ -282,8 +281,8 @@ static int proxy_search_bytree(struct ldb_module *module, struct ldb_request *re
 		talloc_free(newreq);
 		goto failed;
 	}
-	base->comp_num -= proxy->newdn->comp_num;
-	base = ldb_dn_compose(proxy, newreq->op.search.base, proxy->olddn);
+	ldb_dn_remove_base_components(base, ldb_dn_get_comp_num(proxy->newdn));
+	ldb_dn_add_base(base, proxy->olddn);
 
 	ldb_debug(module->ldb, LDB_DEBUG_FATAL, "proxying: '%s' with dn '%s' \n", 
 		  ldb_filter_from_tree(proxy, newreq->op.search.tree), ldb_dn_linearize(proxy, newreq->op.search.base));
diff --git a/source4/dsdb/samdb/ldb_modules/rootdse.c b/source4/dsdb/samdb/ldb_modules/rootdse.c
index 371031be26..e073c8f89b 100644
--- a/source4/dsdb/samdb/ldb_modules/rootdse.c
+++ b/source4/dsdb/samdb/ldb_modules/rootdse.c
@@ -53,7 +53,7 @@ static int rootdse_add_dynamic(struct ldb_module *module, struct ldb_message *ms
 	struct private_data *priv = talloc_get_type(module->private_data, struct private_data);
 	char **server_sasl;
 
-	msg->dn = ldb_dn_explode(msg, "");
+	msg->dn = ldb_dn_new(msg, module->ldb, NULL);
 
 	/* don't return the distinduishedName, cn and name attributes */
 	ldb_msg_remove_attr(msg, "distinguishedName");
@@ -182,7 +182,7 @@ static int rootdse_search(struct ldb_module *module, struct ldb_request *req)
 
 	/* see if its for the rootDSE */
 	if (req->op.search.scope != LDB_SCOPE_BASE ||
-	    (req->op.search.base && ldb_dn_get_comp_num(req->op.search.base) != 0)) {
+	    ( ! ldb_dn_is_null(req->op.search.base))) {
 		return ldb_next_request(module, req);
 	}
 
@@ -203,7 +203,7 @@ static int rootdse_search(struct ldb_module *module, struct ldb_request *req)
 
 	down_req->operation = req->operation;
 	/* in our db we store the rootDSE with a DN of cn=rootDSE */
-	down_req->op.search.base = ldb_dn_explode(down_req, "cn=rootDSE");
+	down_req->op.search.base = ldb_dn_new(down_req, module->ldb, "cn=rootDSE");
 	down_req->op.search.scope = LDB_SCOPE_BASE;
 	down_req->op.search.tree = ldb_parse_tree(down_req, NULL);
 	if (down_req->op.search.base == NULL || down_req->op.search.tree == NULL) {
diff --git a/source4/dsdb/samdb/ldb_modules/samldb.c b/source4/dsdb/samdb/ldb_modules/samldb.c
index 3ce5cc1b5c..667b0d5ca8 100644
--- a/source4/dsdb/samdb/ldb_modules/samldb.c
+++ b/source4/dsdb/samdb/ldb_modules/samldb.c
@@ -62,7 +62,7 @@ static BOOL samldb_msg_add_sid(struct ldb_module *module, struct ldb_message *ms
   return 0 on failure, the id on success
 */
 static int samldb_set_next_rid(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
-			       const struct ldb_dn *dn, uint32_t old_id, uint32_t new_id)
+			       struct ldb_dn *dn, uint32_t old_id, uint32_t new_id)
 {
 	struct ldb_message msg;
 	int ret;
@@ -119,7 +119,7 @@ static int samldb_set_next_rid(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
   return 0 on failure, the id on success
 */
 static int samldb_find_next_rid(struct ldb_module *module, TALLOC_CTX *mem_ctx,
-				const struct ldb_dn *dn, uint32_t *old_rid)
+				struct ldb_dn *dn, uint32_t *old_rid)
 {
 	const char * const attrs[2] = { "nextRid", NULL };
 	struct ldb_result *res = NULL;
@@ -150,7 +150,7 @@ static int samldb_find_next_rid(struct ldb_module *module, TALLOC_CTX *mem_ctx,
 }
 
 static int samldb_allocate_next_rid(struct ldb_module *module, TALLOC_CTX *mem_ctx,
-				    const struct ldb_dn *dn, const struct dom_sid *dom_sid, 
+				    struct ldb_dn *dn, const struct dom_sid *dom_sid, 
 				    struct dom_sid **new_sid)
 {
 	struct dom_sid *obj_sid;
@@ -185,7 +185,7 @@ static int samldb_allocate_next_rid(struct ldb_module *module, TALLOC_CTX *mem_c
 }
 
 /* Find a domain object in the parents of a particular DN.  */
-static struct ldb_dn *samldb_search_domain(struct ldb_module *module, TALLOC_CTX *mem_ctx, const struct ldb_dn *dn)
+static struct ldb_dn *samldb_search_domain(struct ldb_module *module, TALLOC_CTX *mem_ctx, struct ldb_dn *dn)
 {
 	TALLOC_CTX *local_ctx;
 	struct ldb_dn *sdn;
@@ -224,12 +224,12 @@ static struct ldb_dn *samldb_search_domain(struct ldb_module *module, TALLOC_CTX
    return the new sid string
 */
 static int samldb_get_new_sid(struct ldb_module *module, 
-			      TALLOC_CTX *mem_ctx, const struct ldb_dn *obj_dn,
+			      TALLOC_CTX *mem_ctx, struct ldb_dn *obj_dn,
 			      struct dom_sid **sid)
 {
 	const char * const attrs[2] = { "objectSid", NULL };
 	struct ldb_result *res = NULL;
-	const struct ldb_dn *dom_dn;
+	struct ldb_dn *dom_dn;
 	int ret;
 	struct dom_sid *dom_sid;
 
diff --git a/source4/dsdb/samdb/ldb_modules/schema.c b/source4/dsdb/samdb/ldb_modules/schema.c
index fe275ce841..f7bbb7b2c5 100644
--- a/source4/dsdb/samdb/ldb_modules/schema.c
+++ b/source4/dsdb/samdb/ldb_modules/schema.c
@@ -946,7 +946,7 @@ static int schema_check_attributes_syntax(struct schema_context *sctx)
 		if (attr == NULL) {
 			return LDB_ERR_NO_SUCH_ATTRIBUTE;
 		}
-		ret = schema_validate(&msg->elements[i], attr->syntax, attr->single, attr->min, attr->max);
+		ret = schema_validate(sctx->module->ldb, &msg->elements[i], attr->syntax, attr->single, attr->min, attr->max);
 		if (ret != LDB_SUCCESS) {
 			return ret;
 		}
@@ -1187,7 +1187,7 @@ static int schema_init(struct ldb_module *module)
 
 	/* find the schema partition */
 	ret = ldb_search(module->ldb,
-			 ldb_dn_new(module),
+			 ldb_dn_new(module, module->ldb, NULL),
 			 LDB_SCOPE_BASE,
 			 "(objectClass=*)",
 			 schema_attrs,
@@ -1200,7 +1200,7 @@ static int schema_init(struct ldb_module *module)
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	data->schema_dn = ldb_msg_find_attr_as_dn(data, res->msgs[0], "schemaNamingContext");
+	data->schema_dn = ldb_msg_find_attr_as_dn(module->ldb, data, res->msgs[0], "schemaNamingContext");
 	if (data->schema_dn == NULL) {
 		/* FIXME: return a clear error string */
 		talloc_free(data);
diff --git a/source4/dsdb/samdb/ldb_modules/schema_syntax.c b/source4/dsdb/samdb/ldb_modules/schema_syntax.c
index f23c2d156d..f394c75047 100644
--- a/source4/dsdb/samdb/ldb_modules/schema_syntax.c
+++ b/source4/dsdb/samdb/ldb_modules/schema_syntax.c
@@ -137,7 +137,7 @@ int map_schema_syntax(uint32_t om_syntax, const char *attr_syntax, const struct
 	return ret;
 }
 
-static int schema_validate_boolean(struct ldb_val *val, int min, int max)
+static int schema_validate_boolean(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 
 	if ((strncmp("TRUE", (const char *)val->data, val->length) != 0) &&
@@ -148,7 +148,7 @@ static int schema_validate_boolean(struct ldb_val *val, int min, int max)
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_integer(struct ldb_val *val, int min, int max)
+static int schema_validate_integer(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	int value;
 	char *endptr;
@@ -163,19 +163,19 @@ static int schema_validate_integer(struct ldb_val *val, int min, int max)
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_binary_blob(struct ldb_val *val, int min, int max)
+static int schema_validate_binary_blob(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* is there anythign we should check in a binary blob ? */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_sid(struct ldb_val *val, int min, int max)
+static int schema_validate_sid(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: validate binary form of objectSid */
 	return LDB_SUCCESS;	
 }
 
-static int schema_validate_oid(struct ldb_val *val, int min, int max)
+static int schema_validate_oid(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	if (strspn((const char *)val->data, "0123456789.") != val->length)
 		return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX;
@@ -183,7 +183,7 @@ static int schema_validate_oid(struct ldb_val *val, int min, int max)
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_numeric_string(struct ldb_val *val, int min, int max)
+static int schema_validate_numeric_string(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	if (strspn((const char *)val->data, "0123456789") != val->length)
 		return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX;
@@ -191,80 +191,76 @@ static int schema_validate_numeric_string(struct ldb_val *val, int min, int max)
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_printable_string(struct ldb_val *val, int min, int max)
+static int schema_validate_printable_string(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: find out what constitutes the printable character set */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_teletext_string(struct ldb_val *val, int min, int max)
+static int schema_validate_teletext_string(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: find out what constitutes the teletext character set */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_ia5_string(struct ldb_val *val, int min, int max)
+static int schema_validate_ia5_string(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: find out what constitutes the IA5 character set */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_utc_time(struct ldb_val *val, int min, int max)
+static int schema_validate_utc_time(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: validate syntax of UTC Time string */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_generalized_time(struct ldb_val *val, int min, int max)
+static int schema_validate_generalized_time(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: validate syntax of Generalized Time string */
 	return LDB_SUCCESS;
 }
 
 /* NOTE: not a single attribute has this syntax in the basic w2k3 schema */
-static int schema_validate_sensitive_string(struct ldb_val *val, int min, int max)
+static int schema_validate_sensitive_string(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: find out what constitutes a "case sensitive string" */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_unicode_string(struct ldb_val *val, int min, int max)
+static int schema_validate_unicode_string(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: validate utf8 string */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_large_integer(struct ldb_val *val, int min, int max)
+static int schema_validate_large_integer(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: validate large integer/interval */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_object_sd(struct ldb_val *val, int min, int max)
+static int schema_validate_object_sd(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: validate object Security Descriptor */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_dn(struct ldb_val *val, int min, int max)
+static int schema_validate_dn(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
-	TALLOC_CTX *memctx;
 	struct ldb_dn *dn;
 	int ret = LDB_SUCCESS;
 
-	memctx = talloc_new(NULL);
-	if (!memctx) return LDB_ERR_OPERATIONS_ERROR;
-
-	dn = ldb_dn_explode(memctx, (const char *)val->data);
-	if (!dn) {
+	dn = ldb_dn_new(ldb, ldb, (const char *)val->data);
+	if ( ! ldb_dn_validate(dn)) {
 		ret = LDB_ERR_INVALID_ATTRIBUTE_SYNTAX;
 	}
 
-	talloc_free(memctx);
+	talloc_free(dn);
 	return ret;
 }
 
-static int schema_validate_binary_plus_dn(struct ldb_val *val, int min, int max)
+static int schema_validate_binary_plus_dn(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	int ret = LDB_ERR_INVALID_ATTRIBUTE_SYNTAX;
 	TALLOC_CTX *memctx;
@@ -319,8 +315,8 @@ static int schema_validate_binary_plus_dn(struct ldb_val *val, int min, int max)
 
 	str = p + 1;
 
-	dn = ldb_dn_explode(memctx, str);
-	if (dn) {
+	dn = ldb_dn_new(memctx, ldb, str);
+	if (ldb_dn_validate(dn)) {
 		ret = LDB_SUCCESS;
 	}
 
@@ -329,26 +325,26 @@ done:
 	return ret;
 }
 
-static int schema_validate_x400_or_name(struct ldb_val *val, int min, int max)
+static int schema_validate_x400_or_name(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: find out what is the syntax of an X400 OR NAME */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_presentation_address(struct ldb_val *val, int min, int max)
+static int schema_validate_presentation_address(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: find out what is the syntax of a presentation address */
 	return LDB_SUCCESS;
 }
 
-static int schema_validate_x400_access_point(struct ldb_val *val, int min, int max)
+static int schema_validate_x400_access_point(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	/* TODO: find out what is the syntax of an X400 Access Point */
 	return LDB_SUCCESS;
 }
 
 /* NOTE: seem there isn't a single attribute defined like this in the base w2k3 schema */
-static int schema_validate_string_plus_dn(struct ldb_val *val, int min, int max)
+static int schema_validate_string_plus_dn(struct ldb_context *ldb, struct ldb_val *val, int min, int max)
 {
 	int ret = LDB_ERR_INVALID_ATTRIBUTE_SYNTAX;
 	TALLOC_CTX *memctx;
@@ -403,8 +399,8 @@ static int schema_validate_string_plus_dn(struct ldb_val *val, int min, int max)
 
 	str = p + 1;
 
-	dn = ldb_dn_explode(memctx, str);
-	if (dn) {
+	dn = ldb_dn_new(memctx, ldb, str);
+	if (ldb_dn_validate(dn)) {
 		ret = LDB_SUCCESS;
 	}
 
@@ -415,7 +411,7 @@ done:
 
 struct schema_syntax_validator {
 	enum schema_internal_syntax type;
-	int (*validate)(struct ldb_val *, int, int);
+	int (*validate)(struct ldb_context *ldb, struct ldb_val *, int, int);
 };
 
 struct schema_syntax_validator schema_syntax_validators[] = {
@@ -445,7 +441,8 @@ struct schema_syntax_validator schema_syntax_validators[] = {
 	{ -1, NULL }
 };
 
-int schema_validate(struct ldb_message_element *el,
+int schema_validate(struct ldb_context *ldb,
+		    struct ldb_message_element *el,
 		    enum schema_internal_syntax type,
 		    bool single, int min, int max)
 {
@@ -466,7 +463,7 @@ int schema_validate(struct ldb_message_element *el,
 	v = &schema_syntax_validators[i];
 	
 	for (i = 0; i < el->num_values; i++) {
-		ret = v->validate(&el->values[i], min, max);
+		ret = v->validate(ldb, &el->values[i], min, max);
 	}
 
 	return LDB_SUCCESS;
diff --git a/source4/dsdb/samdb/ldb_modules/schema_syntax.h b/source4/dsdb/samdb/ldb_modules/schema_syntax.h
index 453f79a3c2..39a5603cae 100644
--- a/source4/dsdb/samdb/ldb_modules/schema_syntax.h
+++ b/source4/dsdb/samdb/ldb_modules/schema_syntax.h
@@ -67,7 +67,8 @@ int map_schema_syntax(uint32_t om_syntax,
 		      const struct ldb_val *om_class,
 		      enum schema_internal_syntax *syntax);
 
-int schema_validate(struct ldb_message_element *el,
+int schema_validate(struct ldb_context *ldb,
+		    struct ldb_message_element *el,
 		    enum schema_internal_syntax type,
 		    bool single, int min, int max);
 
diff --git a/source4/dsdb/samdb/samdb.c b/source4/dsdb/samdb/samdb.c
index f9ef3bc907..4439335ca5 100644
--- a/source4/dsdb/samdb/samdb.c
+++ b/source4/dsdb/samdb/samdb.c
@@ -59,7 +59,7 @@ struct ldb_context *samdb_connect(TALLOC_CTX *mem_ctx,
 */
 int samdb_search_domain(struct ldb_context *sam_ldb,
 			TALLOC_CTX *mem_ctx, 
-			const struct ldb_dn *basedn,
+			struct ldb_dn *basedn,
 			struct ldb_message ***res,
 			const char * const *attrs,
 			const struct dom_sid *domain_sid,
@@ -100,7 +100,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 struct ldb_dn *basedn,
+				  struct ldb_dn *basedn,
 				  const char *attr_name,
 				  const char *format, va_list ap) _PRINTF_ATTRIBUTE(5,0)
 {
@@ -129,7 +129,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 struct ldb_dn *basedn,
+				struct ldb_dn *basedn,
 				const char *attr_name,
 				const char *format, ...) _PRINTF_ATTRIBUTE(5,6)
 {
@@ -145,7 +145,7 @@ const char *samdb_search_string(struct ldb_context *sam_ldb,
 
 struct ldb_dn *samdb_search_dn(struct ldb_context *sam_ldb,
 			       TALLOC_CTX *mem_ctx,
-			       const struct ldb_dn *basedn,
+			       struct ldb_dn *basedn,
 			       const char *format, ...) _PRINTF_ATTRIBUTE(4,5)
 {
 	va_list ap;
@@ -170,7 +170,7 @@ struct ldb_dn *samdb_search_dn(struct ldb_context *sam_ldb,
 */
 struct dom_sid *samdb_search_dom_sid(struct ldb_context *sam_ldb,
 				     TALLOC_CTX *mem_ctx,
-				     const struct ldb_dn *basedn,
+				     struct ldb_dn *basedn,
 				     const char *attr_name,
 				     const char *format, ...) _PRINTF_ATTRIBUTE(5,6)
 {
@@ -203,7 +203,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 struct ldb_dn *basedn,
+		       struct ldb_dn *basedn,
 		       const char *format, ...) _PRINTF_ATTRIBUTE(4,5)
 {
 	va_list ap;
@@ -225,7 +225,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 struct ldb_dn *basedn,
+			 struct ldb_dn *basedn,
 			 const char *attr_name,
 			 const char *format, ...) _PRINTF_ATTRIBUTE(6,7)
 {
@@ -253,7 +253,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 struct ldb_dn *basedn,
+			   struct ldb_dn *basedn,
 			   const char *attr_name,
 			   const char *format, ...) _PRINTF_ATTRIBUTE(6,7)
 {
@@ -281,7 +281,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 struct ldb_dn *basedn,
+				 struct ldb_dn *basedn,
 				 const char ***strs,
 				 const char *attr_name,
 				 const char *format, ...) _PRINTF_ATTRIBUTE(6,7)
@@ -350,12 +350,18 @@ const char *samdb_result_string(const struct ldb_message *msg, const char *attr,
 	return ldb_msg_find_attr_as_string(msg, attr, default_value);
 }
 
-struct ldb_dn *samdb_result_dn(TALLOC_CTX *mem_ctx, const struct ldb_message *msg,
+struct ldb_dn *samdb_result_dn(struct ldb_context *ldb, TALLOC_CTX *mem_ctx, const struct ldb_message *msg,
 			       const char *attr, struct ldb_dn *default_value)
 {
+	struct ldb_dn *res_dn;
 	const char *string = samdb_result_string(msg, attr, NULL);
 	if (string == NULL) return default_value;
-	return ldb_dn_explode(mem_ctx, string);
+	res_dn = ldb_dn_new(mem_ctx, ldb, string);
+	if ( ! ldb_dn_validate(res_dn)) {
+		talloc_free(res_dn);
+		return NULL;
+	}
+	return res_dn;
 }
 
 /*
@@ -467,7 +473,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 struct ldb_dn *domain_dn, 
+					  struct ldb_dn *domain_dn, 
 					  struct ldb_message *msg, 
 					  const char *attr)
 {
@@ -493,7 +499,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 struct ldb_dn *domain_dn, 
+					  struct ldb_dn *domain_dn, 
 					  struct ldb_message *msg)
 {
 	uint64_t attr_time = samdb_result_uint64(msg, "pwdLastSet", 0);
@@ -679,7 +685,7 @@ int samdb_copy_template(struct ldb_context *ldb,
 	struct ldb_result *res;
 	struct ldb_message *t;
 	int ret, i, j;
-	struct ldb_dn *basedn = ldb_dn_explode(ldb, "cn=Templates");
+	struct ldb_dn *basedn = ldb_dn_new(ldb, ldb, "cn=Templates");
 
 	*errstring = NULL;	
 
@@ -982,7 +988,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 struct ldb_dn *dn)
+int samdb_delete(struct ldb_context *sam_ldb, TALLOC_CTX *mem_ctx, struct ldb_dn *dn)
 {
 	return ldb_delete(sam_ldb, dn);
 }
@@ -1023,19 +1029,23 @@ struct security_descriptor *samdb_default_security_descriptor(TALLOC_CTX *mem_ct
 	return sd;
 }
 
-const struct ldb_dn *samdb_base_dn(struct ldb_context *sam_ctx) 
+struct ldb_dn *samdb_base_dn(struct ldb_context *sam_ctx) 
 {
 	return ldb_get_default_basedn(sam_ctx);
 }
 
 
-const struct ldb_dn *samdb_partitions_dn(struct ldb_context *sam_ctx,
-				   TALLOC_CTX *mem_ctx)
+struct ldb_dn *samdb_partitions_dn(struct ldb_context *sam_ctx, TALLOC_CTX *mem_ctx)
 {
-	return ldb_dn_string_compose(mem_ctx, samdb_base_dn(sam_ctx), 
-				     "CN=Partitions,CN=Configuration");
-}
+	struct ldb_dn *new_dn;
 
+	new_dn = ldb_dn_copy(mem_ctx, samdb_base_dn(sam_ctx));
+	if ( ! ldb_dn_add_child_fmt(new_dn, "CN=Partitions,CN=Configuration")) {
+		talloc_free(new_dn);
+		return NULL;
+	}
+	return new_dn;
+}
 
 /*
   work out the domain sid for the current open ldb
@@ -1061,7 +1071,7 @@ const struct dom_sid *samdb_domain_sid(struct ldb_context *ldb)
 		goto failed;
 	}
 
-	basedn = ldb_dn_explode(tmp_ctx, "");
+	basedn = ldb_dn_new(tmp_ctx, ldb, NULL);
 	if (basedn == NULL) {
 		goto failed;
 	}
@@ -1078,8 +1088,8 @@ const struct dom_sid *samdb_domain_sid(struct ldb_context *ldb)
 		goto failed;
 	}
 
-	basedn = ldb_dn_explode(tmp_ctx, basedn_s);
-	if (basedn == NULL) {
+	basedn = ldb_dn_new(tmp_ctx, ldb, basedn_s);
+	if ( ! ldb_dn_validate(basedn)) {
 		goto failed;
 	}
 
@@ -1129,8 +1139,8 @@ static BOOL samdb_password_complexity_ok(const char *pass)
   The caller should probably have a transaction wrapping this
 */
 _PUBLIC_ NTSTATUS samdb_set_password(struct ldb_context *ctx, TALLOC_CTX *mem_ctx,
-			    const struct ldb_dn *user_dn,
-			    const struct ldb_dn *domain_dn,
+			    struct ldb_dn *user_dn,
+			    struct ldb_dn *domain_dn,
 			    struct ldb_message *mod,
 			    const char *new_pass,
 			    struct samr_Password *lmNewHash, 
@@ -1542,8 +1552,8 @@ NTSTATUS samdb_create_foreign_security_principal(struct ldb_context *sam_ctx, TA
 	}
 	
 	/* add core elements to the ldb_message for the alias */
-	msg->dn = ldb_dn_build_child(mem_ctx, "CN", sidstr, basedn);
-	if (msg->dn == NULL)
+	msg->dn = ldb_dn_copy(mem_ctx, basedn);
+	if ( ! ldb_dn_add_child_fmt(msg->dn, "CN=%s", sidstr))
 		return NT_STATUS_NO_MEMORY;
 	
 	samdb_msg_add_string(sam_ctx, mem_ctx, msg,
diff --git a/source4/kdc/hdb-ldb.c b/source4/kdc/hdb-ldb.c
index 00c89f9c0a..fd6ebfbe1b 100644
--- a/source4/kdc/hdb-ldb.c
+++ b/source4/kdc/hdb-ldb.c
@@ -212,7 +212,11 @@ static krb5_error_code LDB_message2entry(krb5_context context, HDB *db,
 	krb5_boolean is_computer = FALSE;
 	const char *dnsdomain = ldb_msg_find_attr_as_string(realm_ref_msg, "dnsRoot", NULL);
 	char *realm = strupper_talloc(mem_ctx, dnsdomain);
-	struct ldb_dn *domain_dn = samdb_result_dn(mem_ctx, realm_ref_msg, "nCName", ldb_dn_new(mem_ctx));
+	struct ldb_dn *domain_dn = samdb_result_dn((struct ldb_context *)db->hdb_db,
+							mem_ctx,
+							realm_ref_msg,
+							"nCName",
+							ldb_dn_new(mem_ctx, (struct ldb_context *)db->hdb_db, NULL));
 
 	struct hdb_ldb_private *private;
 	NTTIME acct_expiry;
@@ -449,7 +453,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 struct ldb_dn *realm_dn,
+					    struct ldb_dn *realm_dn,
 					    struct ldb_message ***pmsg)
 {
 	krb5_error_code ret;
@@ -523,7 +527,7 @@ static krb5_error_code LDB_lookup_realm(krb5_context context, struct ldb_context
  	int ret;
 	char *cross_ref_filter;
 	struct ldb_result *cross_ref_res;
-	const struct ldb_dn *partitions_basedn = samdb_partitions_dn(ldb_ctx, mem_ctx);
+	struct ldb_dn *partitions_basedn = samdb_partitions_dn(ldb_ctx, mem_ctx);
 
 	cross_ref_filter = talloc_asprintf(mem_ctx, 
 					   "(&(&(|(&(dnsRoot=%s)(nETBIOSName=*))(nETBIOSName=%s))(objectclass=crossRef))(ncName=*))",
@@ -630,7 +634,7 @@ static krb5_error_code LDB_fetch_krbtgt(krb5_context context, HDB *db,
 	krb5_error_code ret;
 	struct ldb_message **msg = NULL;
 	struct ldb_message **realm_ref_msg = NULL;
-	const struct ldb_dn *realm_dn;
+	struct ldb_dn *realm_dn;
 
 	if (principal->name.name_string.len != 2
 	    || (strcmp(principal->name.name_string.val[0], KRB5_TGS_NAME) != 0)) {
@@ -642,13 +646,13 @@ static krb5_error_code LDB_fetch_krbtgt(krb5_context context, HDB *db,
 	if ((LDB_lookup_realm(context, (struct ldb_context *)db->hdb_db,
 			      mem_ctx, principal->name.name_string.val[1], &realm_ref_msg) == 0)) {
 		/* us */		
-		realm_dn = samdb_result_dn(mem_ctx, realm_ref_msg[0], "nCName", NULL);
+		realm_dn = samdb_result_dn((struct ldb_context *)db->hdb_db, mem_ctx, realm_ref_msg[0], "nCName", NULL);
 	} else {
 		/* we should lookup trusted domains */
 		return HDB_ERR_NOENTRY;
 	}
 
-	realm_dn = samdb_result_dn(mem_ctx, realm_ref_msg[0], "nCName", NULL);
+	realm_dn = samdb_result_dn((struct ldb_context *)db->hdb_db, mem_ctx, realm_ref_msg[0], "nCName", NULL);
 	
 	ret = LDB_lookup_principal(context, (struct ldb_context *)db->hdb_db, 
 				   mem_ctx, 
@@ -679,7 +683,7 @@ static krb5_error_code LDB_fetch_server(krb5_context context, HDB *db,
 	const char *realm;
 	struct ldb_message **msg = NULL;
 	struct ldb_message **realm_ref_msg = NULL;
-	const struct ldb_dn *partitions_basedn = samdb_partitions_dn(db->hdb_db, mem_ctx);
+	struct ldb_dn *partitions_basedn = samdb_partitions_dn(db->hdb_db, mem_ctx);
 	if (principal->name.name_string.len >= 2) {
 		/* 'normal server' case */
 		int ldb_ret;
@@ -722,7 +726,7 @@ static krb5_error_code LDB_fetch_server(krb5_context context, HDB *db,
 		}
 		
 	} else {
-		const struct ldb_dn *realm_dn;
+		struct ldb_dn *realm_dn;
 		/* server as client principal case, but we must not lookup userPrincipalNames */
 
 		realm = krb5_principal_get_realm(context, principal);
@@ -733,7 +737,7 @@ static krb5_error_code LDB_fetch_server(krb5_context context, HDB *db,
 			return HDB_ERR_NOENTRY;
 		}
 		
-		realm_dn = samdb_result_dn(mem_ctx, realm_ref_msg[0], "nCName", NULL);
+		realm_dn = samdb_result_dn((struct ldb_context *)db->hdb_db, mem_ctx, realm_ref_msg[0], "nCName", NULL);
 		
 		ret = LDB_lookup_principal(context, (struct ldb_context *)db->hdb_db, 
 					   mem_ctx, 
@@ -898,7 +902,7 @@ static krb5_error_code LDB_firstkey(krb5_context context, HDB *db, unsigned flag
 		return HDB_ERR_NOENTRY;
 	}
 
-	realm_dn = samdb_result_dn(mem_ctx, realm_ref_msgs[0], "nCName", NULL);
+	realm_dn = samdb_result_dn((struct ldb_context *)db->hdb_db, mem_ctx, realm_ref_msgs[0], "nCName", NULL);
 
 	priv->realm_ref_msgs = talloc_steal(priv, realm_ref_msgs);
 
diff --git a/source4/ldap_server/ldap_backend.c b/source4/ldap_server/ldap_backend.c
index 1a2206b831..de99280ded 100644
--- a/source4/ldap_server/ldap_backend.c
+++ b/source4/ldap_server/ldap_backend.c
@@ -31,6 +31,10 @@
 #define VALID_DN_SYNTAX(dn,i) do {\
 	if (!(dn)) {\
 		return NT_STATUS_NO_MEMORY;\
+	} else if ( ! ldb_dn_validate(dn)) {\
+		result = LDAP_INVALID_DN_SYNTAX;\
+		errstr = "Invalid DN format";\
+		goto reply;\
 	} else if (ldb_dn_get_comp_num(dn) < (i)) {\
 		result = LDAP_INVALID_DN_SYNTAX;\
 		errstr = "Invalid DN (" #i " components needed for '" #dn "')";\
@@ -169,7 +173,7 @@ static NTSTATUS ldapsrv_SearchRequest(struct ldapsrv_call *call)
 	local_ctx = talloc_new(call);
 	NT_STATUS_HAVE_NO_MEMORY(local_ctx);
 
-	basedn = ldb_dn_explode(local_ctx, req->basedn);
+	basedn = ldb_dn_new(local_ctx, samdb, req->basedn);
 	VALID_DN_SYNTAX(basedn, 0);
 
 	DEBUG(10, ("SearchRequest: basedn: [%s]\n", req->basedn));
@@ -327,7 +331,7 @@ static NTSTATUS ldapsrv_ModifyRequest(struct ldapsrv_call *call)
 	local_ctx = talloc_named(call, 0, "ModifyRequest local memory context");
 	NT_STATUS_HAVE_NO_MEMORY(local_ctx);
 
-	dn = ldb_dn_explode(local_ctx, req->dn);
+	dn = ldb_dn_new(local_ctx, samdb, req->dn);
 	VALID_DN_SYNTAX(dn, 1);
 
 	DEBUG(10, ("ModifyRequest: dn: [%s]\n", req->dn));
@@ -431,7 +435,7 @@ static NTSTATUS ldapsrv_AddRequest(struct ldapsrv_call *call)
 	local_ctx = talloc_named(call, 0, "AddRequest local memory context");
 	NT_STATUS_HAVE_NO_MEMORY(local_ctx);
 
-	dn = ldb_dn_explode(local_ctx, req->dn);
+	dn = ldb_dn_new(local_ctx, samdb, req->dn);
 	VALID_DN_SYNTAX(dn,1);
 
 	DEBUG(10, ("AddRequest: dn: [%s]\n", req->dn));
@@ -522,7 +526,7 @@ static NTSTATUS ldapsrv_DelRequest(struct ldapsrv_call *call)
 	local_ctx = talloc_named(call, 0, "DelRequest local memory context");
 	NT_STATUS_HAVE_NO_MEMORY(local_ctx);
 
-	dn = ldb_dn_explode(local_ctx, req->dn);
+	dn = ldb_dn_new(local_ctx, samdb, req->dn);
 	VALID_DN_SYNTAX(dn,1);
 
 	DEBUG(10, ("DelRequest: dn: [%s]\n", req->dn));
@@ -568,10 +572,10 @@ static NTSTATUS ldapsrv_ModifyDNRequest(struct ldapsrv_call *call)
 	local_ctx = talloc_named(call, 0, "ModifyDNRequest local memory context");
 	NT_STATUS_HAVE_NO_MEMORY(local_ctx);
 
-	olddn = ldb_dn_explode(local_ctx, req->dn);
+	olddn = ldb_dn_new(local_ctx, samdb, req->dn);
 	VALID_DN_SYNTAX(olddn, 2);
 
-	newrdn = ldb_dn_explode(local_ctx, req->newrdn);
+	newrdn = ldb_dn_new(local_ctx, samdb, req->newrdn);
 	VALID_DN_SYNTAX(newrdn, 1);
 
 	DEBUG(10, ("ModifyDNRequest: olddn: [%s]\n", req->dn));
@@ -584,14 +588,8 @@ static NTSTATUS ldapsrv_ModifyDNRequest(struct ldapsrv_call *call)
 		goto reply;
 	}
 
-	if (ldb_dn_get_comp_num(newrdn) > 1) {
-		result = LDAP_NAMING_VIOLATION;
-		errstr = "Error new RDN invalid";
-		goto reply;
-	}
-
 	if (req->newsuperior) {
-		parentdn = ldb_dn_explode(local_ctx, req->newsuperior);
+		parentdn = ldb_dn_new(local_ctx, samdb, req->newsuperior);
 		VALID_DN_SYNTAX(parentdn, 0);
 		DEBUG(10, ("ModifyDNRequest: newsuperior: [%s]\n", req->newsuperior));
 		
@@ -607,11 +605,13 @@ static NTSTATUS ldapsrv_ModifyDNRequest(struct ldapsrv_call *call)
 		NT_STATUS_HAVE_NO_MEMORY(parentdn);
 	}
 
-	newdn = ldb_dn_build_child(local_ctx,
-				   ldb_dn_get_rdn_name(newrdn),
-				   (char *)ldb_dn_get_rdn_val(newrdn)->data,
-				   parentdn);
-	NT_STATUS_HAVE_NO_MEMORY(newdn);
+	if ( ! ldb_dn_add_child_fmt(parentdn,
+				"%s=%s",
+				ldb_dn_get_rdn_name(newrdn),
+				(char *)ldb_dn_get_rdn_val(newrdn)->data)) {
+		result = LDAP_OTHER;
+		goto reply;
+	}
 
 reply:
 	modifydn_r = ldapsrv_init_reply(call, LDAP_TAG_ModifyDNResponse);
@@ -655,7 +655,7 @@ static NTSTATUS ldapsrv_CompareRequest(struct ldapsrv_call *call)
 	local_ctx = talloc_named(call, 0, "CompareRequest local_memory_context");
 	NT_STATUS_HAVE_NO_MEMORY(local_ctx);
 
-	dn = ldb_dn_explode(local_ctx, req->dn);
+	dn = ldb_dn_new(local_ctx, samdb, req->dn);
 	VALID_DN_SYNTAX(dn, 1);
 
 	DEBUG(10, ("CompareRequest: dn: [%s]\n", req->dn));
diff --git a/source4/ldap_server/ldap_server.c b/source4/ldap_server/ldap_server.c
index 29555b14e1..82fc1d9660 100644
--- a/source4/ldap_server/ldap_server.c
+++ b/source4/ldap_server/ldap_server.c
@@ -239,8 +239,8 @@ static int ldapsrv_load_limits(struct ldapsrv_connection *conn)
 		return -1;
 	}
 
-	basedn = ldb_dn_new(tmp_ctx);
-	if (basedn == NULL) {
+	basedn = ldb_dn_new(tmp_ctx, conn->ldb, NULL);
+	if ( ! ldb_dn_validate(basedn)) {
 		goto failed;
 	}
 
@@ -250,12 +250,13 @@ static int ldapsrv_load_limits(struct ldapsrv_connection *conn)
 		goto failed;
 	}
 
-	conf_dn = ldb_msg_find_attr_as_dn(tmp_ctx, res->msgs[0], "configurationNamingContext");
+	conf_dn = ldb_msg_find_attr_as_dn(conn->ldb, tmp_ctx, res->msgs[0], "configurationNamingContext");
 	if (conf_dn == NULL) {
 		goto failed;
 	}
 
-	policy_dn = ldb_dn_string_compose(tmp_ctx, conf_dn, "CN=Default Query Policy,CN=Query-Policies,CN=Directory Service,CN=Windows NT,CN=Services");
+	policy_dn = ldb_dn_copy(tmp_ctx, conf_dn);
+	ldb_dn_add_child_fmt(policy_dn, "CN=Default Query Policy,CN=Query-Policies,CN=Directory Service,CN=Windows NT,CN=Services");
 	if (policy_dn == NULL) {
 		goto failed;
 	}
diff --git a/source4/lib/gendb.c b/source4/lib/gendb.c
index faaca3877e..035ef01a8f 100644
--- a/source4/lib/gendb.c
+++ b/source4/lib/gendb.c
@@ -30,7 +30,7 @@
 */
 int gendb_search_v(struct ldb_context *ldb, 
 		   TALLOC_CTX *mem_ctx,
-		   const struct ldb_dn *basedn,
+		   struct ldb_dn *basedn,
 		   struct ldb_message ***msgs,
 		   const char * const *attrs,
 		   const char *format, 
@@ -79,7 +79,7 @@ int gendb_search_v(struct ldb_context *ldb,
 */
 int gendb_search(struct ldb_context *ldb,
 		 TALLOC_CTX *mem_ctx, 
-		 const struct ldb_dn *basedn,
+		 struct ldb_dn *basedn,
 		 struct ldb_message ***res,
 		 const char * const *attrs,
 		 const char *format, ...) _PRINTF_ATTRIBUTE(6,7)
@@ -100,7 +100,7 @@ int gendb_search(struct ldb_context *ldb,
 
 int gendb_search_dn(struct ldb_context *ldb,
 		 TALLOC_CTX *mem_ctx, 
-		 const struct ldb_dn *dn,
+		 struct ldb_dn *dn,
 		 struct ldb_message ***res,
 		 const char * const *attrs)
 {
diff --git a/source4/lib/ldb/common/attrib_handlers.c b/source4/lib/ldb/common/attrib_handlers.c
index cb1dfa105f..372793a103 100644
--- a/source4/lib/ldb/common/attrib_handlers.c
+++ b/source4/lib/ldb/common/attrib_handlers.c
@@ -234,8 +234,8 @@ static int ldb_canonicalise_dn(struct ldb_context *ldb, void *mem_ctx,
 	out->length = 0;
 	out->data = NULL;
 
-	dn = ldb_dn_explode_casefold(ldb, mem_ctx, (char *)in->data);
-	if (dn == NULL) {
+	dn = ldb_dn_new(ldb, mem_ctx, (char *)in->data);
+	if ( ! ldb_dn_validate(dn)) {
 		return -1;
 	}
 
@@ -262,16 +262,16 @@ static int ldb_comparison_dn(struct ldb_context *ldb, void *mem_ctx,
 	struct ldb_dn *dn1 = NULL, *dn2 = NULL;
 	int ret;
 
-	dn1 = ldb_dn_explode_casefold(ldb, mem_ctx, (char *)v1->data);
-	if (dn1 == NULL) return -1;
+	dn1 = ldb_dn_new(ldb, mem_ctx, (char *)v1->data);
+	if ( ! ldb_dn_validate(dn1)) return -1;
 
-	dn2 = ldb_dn_explode_casefold(ldb, mem_ctx, (char *)v2->data);
-	if (dn2 == NULL) {
+	dn2 = ldb_dn_new(ldb, mem_ctx, (char *)v2->data);
+	if ( ! ldb_dn_validate(dn2)) {
 		talloc_free(dn1);
 		return -1;
 	} 
 
-	ret = ldb_dn_compare(ldb, dn1, dn2);
+	ret = ldb_dn_compare(dn1, dn2);
 
 	talloc_free(dn1);
 	talloc_free(dn2);
diff --git a/source4/lib/ldb/common/ldb.c b/source4/lib/ldb/common/ldb.c
index 9e0ee6ebca..c05f8313f1 100644
--- a/source4/lib/ldb/common/ldb.c
+++ b/source4/lib/ldb/common/ldb.c
@@ -153,7 +153,7 @@ int ldb_connect_backend(struct ldb_context *ldb, const char *url, const char *op
   pet hates about ldapsearch, which is that you have to get a long,
   complex basedn right to make any use of it.
 */
-static const struct ldb_dn *ldb_set_default_basedn(struct ldb_context *ldb)
+static struct ldb_dn *ldb_set_default_basedn(struct ldb_context *ldb)
 {
 	TALLOC_CTX *tmp_ctx;
 	int ret;
@@ -167,11 +167,11 @@ static const struct ldb_dn *ldb_set_default_basedn(struct ldb_context *ldb)
 	}
 
 	tmp_ctx = talloc_new(ldb);
-	ret = ldb_search(ldb, ldb_dn_new(tmp_ctx), LDB_SCOPE_BASE, 
+	ret = ldb_search(ldb, ldb_dn_new(tmp_ctx, ldb, NULL), LDB_SCOPE_BASE, 
 			 "(objectClass=*)", attrs, &res);
 	if (ret == LDB_SUCCESS) {
 		if (res->count == 1) {
-			basedn = ldb_msg_find_attr_as_dn(ldb, res->msgs[0], "defaultNamingContext");
+			basedn = ldb_msg_find_attr_as_dn(ldb, ldb, res->msgs[0], "defaultNamingContext");
 			ldb_set_opaque(ldb, "default_baseDN", basedn);
 		}
 		talloc_free(res);
@@ -181,9 +181,9 @@ static const struct ldb_dn *ldb_set_default_basedn(struct ldb_context *ldb)
 	return basedn;
 }
 
-const struct ldb_dn *ldb_get_default_basedn(struct ldb_context *ldb)
+struct ldb_dn *ldb_get_default_basedn(struct ldb_context *ldb)
 {
-	return (const struct ldb_dn *)ldb_get_opaque(ldb, "default_baseDN");
+	return (struct ldb_dn *)ldb_get_opaque(ldb, "default_baseDN");
 }
 
 /* 
@@ -582,7 +582,7 @@ error:
 int ldb_build_search_req(struct ldb_request **ret_req,
 			struct ldb_context *ldb,
 			void *mem_ctx,
-			const struct ldb_dn *base,
+			struct ldb_dn *base,
 	       		enum ldb_scope scope,
 			const char *expression,
 			const char * const *attrs,
@@ -602,7 +602,7 @@ int ldb_build_search_req(struct ldb_request **ret_req,
 
 	req->operation = LDB_SEARCH;
 	if (base == NULL) {
-		req->op.search.base = ldb_dn_new(req);
+		req->op.search.base = ldb_dn_new(req, ldb, NULL);
 	} else {
 		req->op.search.base = base;
 	}
@@ -685,7 +685,7 @@ int ldb_build_mod_req(struct ldb_request **ret_req,
 int ldb_build_del_req(struct ldb_request **ret_req,
 			struct ldb_context *ldb,
 			void *mem_ctx,
-			const struct ldb_dn *dn,
+			struct ldb_dn *dn,
 			struct ldb_control **controls,
 			void *context,
 			ldb_request_callback_t callback)
@@ -714,8 +714,8 @@ int ldb_build_del_req(struct ldb_request **ret_req,
 int ldb_build_rename_req(struct ldb_request **ret_req,
 			struct ldb_context *ldb,
 			void *mem_ctx,
-			const struct ldb_dn *olddn,
-			const struct ldb_dn *newdn,
+			struct ldb_dn *olddn,
+			struct ldb_dn *newdn,
 			struct ldb_control **controls,
 			void *context,
 			ldb_request_callback_t callback)
@@ -747,7 +747,7 @@ int ldb_build_rename_req(struct ldb_request **ret_req,
   defaultNamingContext from the rootDSE if available.
 */
 int ldb_search(struct ldb_context *ldb, 
-	       const struct ldb_dn *base,
+	       struct ldb_dn *base,
 	       enum ldb_scope scope,
 	       const char *expression,
 	       const char * const *attrs, 
@@ -861,7 +861,7 @@ int ldb_modify(struct ldb_context *ldb,
 /*
   delete a record from the database
 */
-int ldb_delete(struct ldb_context *ldb, const struct ldb_dn *dn)
+int ldb_delete(struct ldb_context *ldb, struct ldb_dn *dn)
 {
 	struct ldb_request *req;
 	int ret;
@@ -886,7 +886,7 @@ int ldb_delete(struct ldb_context *ldb, const struct ldb_dn *dn)
 /*
   rename a record in the database
 */
-int ldb_rename(struct ldb_context *ldb, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
+int ldb_rename(struct ldb_context *ldb, struct ldb_dn *olddn, struct ldb_dn *newdn)
 {
 	struct ldb_request *req;
 	int ret;
diff --git a/source4/lib/ldb/common/ldb_dn.c b/source4/lib/ldb/common/ldb_dn.c
index 48f471bf6f..0a10ed6f2e 100644
--- a/source4/lib/ldb/common/ldb_dn.c
+++ b/source4/lib/ldb/common/ldb_dn.c
@@ -25,64 +25,138 @@
 /*
  *  Name: ldb
  *
- *  Component: ldb dn explode and utility functions
+ *  Component: ldb dn creation and manipulation utility functions
  *
  *  Description: - explode a dn into it's own basic elements
- *                 and put them in a structure
+ *                 and put them in a structure (only if necessary)
  *               - manipulate ldb_dn structures
  *
  *  Author: Simo Sorce
  */
 
 #include "includes.h"
+#include <ctype.h>
 #include "ldb/include/includes.h"
 
 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
 
-#define LDB_SPECIAL "@SPECIAL"
+#define LDB_FREE(x) do { talloc_free(x); x = NULL; } while(0)
 
 /**
    internal ldb exploded dn structures
 */
 struct ldb_dn_component {
-	char *name;  
+
+	char *name;
 	struct ldb_val value;
+
+	char *cf_name;
+	struct ldb_val cf_value;
 };
 
 struct ldb_dn {
-	int comp_num;
+
+	struct ldb_context *ldb;
+
+	/* Special DNs are always linearized */
+	bool special;
+	bool invalid;
+
+	bool valid_lin;
+	bool valid_comp;
+	bool valid_case;
+
+	char *linearized;
+	char *casefold;
+
+	unsigned int comp_num;
 	struct ldb_dn_component *components;
+
 };
 
-int ldb_dn_is_special(const struct ldb_dn *dn)
+/* strdn may be NULL */
+struct ldb_dn *ldb_dn_new(void *mem_ctx, struct ldb_context *ldb, const char *strdn)
 {
-	if (dn == NULL || dn->comp_num != 1) return 0;
+	struct ldb_dn *dn;
 
-	return ! strcmp(dn->components[0].name, LDB_SPECIAL);
-}
+	if ( (! mem_ctx) || (! ldb)) return NULL;
 
-int ldb_dn_check_special(const struct ldb_dn *dn, const char *check)
-{
-	if (dn == NULL || dn->comp_num != 1) return 0;
+	dn = talloc_zero(mem_ctx, struct ldb_dn);
+	LDB_DN_NULL_FAILED(dn);
+
+	dn->ldb = ldb;
+
+	if (strdn) {
+		if (strdn[0] == '@') {
+			dn->special = true;
+		}
+		if (strncasecmp(strdn, "<GUID=", 6) == 0) {
+			/* this is special DN returned when the
+			 * exploded_dn control is used */
+			dn->special = true;
+			/* FIXME: add a GUID string to ldb_dn structure */
+		}
+		dn->linearized = talloc_strdup(dn, strdn);
+	} else {
+		dn->linearized = talloc_strdup(dn, "");
+	}
+	LDB_DN_NULL_FAILED(dn->linearized);
+
+	dn->valid_lin = true;
+
+	return dn;
 
-	return ! strcmp((char *)dn->components[0].value.data, check);
+failed:
+	talloc_free(dn);
+	return NULL;
 }
 
-char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
+struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx, struct ldb_context *ldb, const char *new_fmt, ...)
 {
-	const char *p, *s, *src;
-	char *d, *dst;
-	int len;
+	struct ldb_dn *dn;
+	char *strdn;
+	va_list ap;
 
-	if (!value.length)
-		return NULL;
+	if ( (! mem_ctx) || (! ldb)) return NULL;
+
+	dn = talloc_zero(mem_ctx, struct ldb_dn);
+	LDB_DN_NULL_FAILED(dn);
 
-	p = s = src = (const char *)value.data;
-	len = value.length;
+	dn->ldb = ldb;
 
-	/* allocate destination string, it will be at most 3 times the source */
-	dst = d = talloc_array(mem_ctx, char, len * 3 + 1);
-	LDB_DN_NULL_FAILED(dst);
+	va_start(ap, new_fmt);
+	strdn = talloc_vasprintf(dn, new_fmt, ap);
+	va_end(ap);
+	LDB_DN_NULL_FAILED(strdn);
+
+	if (strdn[0] == '@') {
+		dn->special = true;
+	}
+	if (strncasecmp(strdn, "<GUID=", 6) == 0) {
+		/* this is special DN returned when the
+		 * exploded_dn control is used */
+		dn->special = true;
+		/* FIXME: add a GUID string to ldb_dn structure */
+	}
+	dn->linearized = strdn;
+
+	dn->valid_lin = true;
+
+	return dn;
+
+failed:
+	talloc_free(dn);
+	return NULL;
+}
+
+static int ldb_dn_escape_internal(char *dst, const char *src, int len)
+{
+	const char *p, *s;
+	char *d;
+	int l;
+
+	p = s = src;
+	d = dst;
 
 	while (p - src < len) {
 
@@ -99,404 +173,500 @@ char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
 			*d++ = *p++;
 		} else { /* we have a zero byte in the string */
 			strncpy(d, "\00", 3); /* escape the zero */
-			d = d + 3;
+			d += 3;
 			p++; /* skip the zero */
 		}
 		s = p; /* move forward */
 	}
 
 	/* copy the last part (with zero) and return */
-	memcpy(d, s, &src[len] - s + 1);
+	l = len - (s - src);
+	memcpy(d, s, l + 1);
 
-	return dst;
-
-failed:
-	talloc_free(dst);
-	return NULL;
-}
+	/* return the length of the resulting string */
+	return (l + (d - dst));
+} 
 
-static struct ldb_val ldb_dn_unescape_value(void *mem_ctx, const char *src)
+char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
 {
-	struct ldb_val value;
-	unsigned x;
-	char *p, *dst = NULL, *end;
-
-	memset(&value, 0, sizeof(value));
-
-	LDB_DN_NULL_FAILED(src);
-
-	dst = p = (char *)talloc_memdup(mem_ctx, src, strlen(src) + 1);
-	LDB_DN_NULL_FAILED(dst);
-
-	end = &dst[strlen(dst)];
-
-	while (*p) {
-		p += strcspn(p, ",=\n+<>#;\\\"");
-
-		if (*p == '\\') {
-			if (strchr(",=\n+<>#;\\\"", p[1])) {
-				memmove(p, p + 1, end - (p + 1) + 1);
-				end--;
-				p++;
-				continue;
-			}
+	char *dst;
 
-			if (sscanf(p + 1, "%02x", &x) == 1) {
-				*p = (unsigned char)x;
-				memmove(p + 1, p + 3, end - (p + 3) + 1);
-				end -= 2;
-				p++;
-				continue;
-			}
-		}
+	if (!value.length)
+		return NULL;
 
-		/* a string with not escaped specials is invalid (tested) */
-		if (*p != '\0') {
-			goto failed;
-		}
+	/* allocate destination string, it will be at most 3 times the source */
+	dst = talloc_array(mem_ctx, char, value.length * 3 + 1);
+	if ( ! dst) {
+		talloc_free(dst);
+		return NULL;
 	}
 
-	value.length = end - dst;
-	value.data = (uint8_t *)dst;
-	return value;
+	ldb_dn_escape_internal(dst, (const char *)value.data, value.length);
 
-failed:
-	talloc_free(dst);
-	return value;
+	return dst;
 }
 
-/* check if the string contains quotes
- * skips leading and trailing spaces
- * - returns 0 if no quotes found
- * - returns 1 if quotes are found and put their position
- *   in *quote_start and *quote_end parameters
- * - return -1 if there are open quotes
- */
-
-static int get_quotes_position(const char *source, int *quote_start, int *quote_end)
+/*
+  explode a DN string into a ldb_dn structure
+  based on RFC4514 except that we don't support multiple valued RDNs
+*/
+static bool ldb_dn_explode(struct ldb_dn *dn)
 {
-	const char *p;
-
-	if (source == NULL || quote_start == NULL || quote_end == NULL) return -1;
-
-	p = source;
-
-	/* check if there are quotes surrounding the value */
-	p += strspn(p, " \n"); /* skip white spaces */
+	char *p, *data, *d, *dt, *t;
+	bool trim = false;
+	bool in_attr = false;
+	bool in_value = false;
+	bool in_quote = false;
+	bool is_oid = false;
+	bool escape = false;
+	unsigned x;
+	int l;
 
-	if (*p == '\"') {
-		*quote_start = p - source;
+	if ( ! dn || dn->invalid) return false;
 
-		p++;
-		while (*p != '\"') {
-			p = strchr(p, '\"');
-			LDB_DN_NULL_FAILED(p);
+	if (dn->valid_comp) {
+		return true;
+	}
 
-			if (*(p - 1) == '\\')
-				p++;
-		}
+	if ( ! dn->valid_lin) {
+		return false;
+	}
 
-		*quote_end = p - source;
-		return 1;
+	/* Empty DNs */
+	if (dn->linearized[0] == '\0') {
+		dn->valid_comp = true;
+		return true;
 	}
 
-	return 0;
+	/* Special DNs case */
+	if (dn->special) {
+		return true;
+	}
 
-failed:
-	return -1;
-}
+	/* in the common case we have 3 or more components */
+	/* make sure all components are zeroed, other functions depend on this */
+	dn->components = talloc_zero_array(dn, struct ldb_dn_component, 3);
+	if ( ! dn->components) {
+		return false;
+	}
+	dn->comp_num = 0;
 
-static char *seek_to_separator(char *string, const char *separators)
-{
-	char *p, *q;
-	int ret, qs, qe, escaped;
+	/* Components data space is allocated here once */
+	data = talloc_array(dn->components, char, strlen(dn->linearized) + 1);
 
-	if (string == NULL || separators == NULL) return NULL;
+	p = dn->linearized;
+	in_attr = true;
+	trim = true;
+	t = NULL;
+	d = dt = data;
 
-	p = strchr(string, '=');
-	LDB_DN_NULL_FAILED(p);
+	while (*p) {
 
-	p++;
+		if (in_attr) {
+			if (trim) {
+				if (*p == ' ') {
+					p++;
+					continue;
+				}
+
+				/* first char */
+				trim = false;
+
+				if (isdigit(*p)) {
+					is_oid = true;
+				} else
+				if ( ! isalpha(*p)) {
+					/* not a digit nor an alpha, invalid attribute name */
+					dn->invalid = true;
+					goto failed;
+				}
+				
+				*d++ = *p++;
+				continue;
+			}
 
-	/* check if there are quotes surrounding the value */
+			if (*p == ' ') {
+				p++;
+				/* valid only if we are at the end */
+				trim = true;
+				continue;
+			}
 
-	ret = get_quotes_position(p, &qs, &qe);
-	if (ret == -1)
-		return NULL;
+			if (trim && (*p != '=')) {
+				/* spaces/tabs are not allowed in attribute names */
+				dn->invalid = true;
+				goto failed;
+			}
 
-	if (ret == 1) { /* quotes found */
+			if (*p == '=') {
+				/* attribute terminated */
+				in_attr = false;
+				in_value = true;
+				trim = true;
+				l = 0;
 
-		p += qe; /* positioning after quotes */
-		p += strspn(p, " \n"); /* skip white spaces after the quote */
+				*d++ = '\0';
+				dn->components[dn->comp_num].name = dt;
+				dt = d;
 
-		if (strcspn(p, separators) != 0) /* if there are characters between quotes */
-			return NULL;	    /* and separators, the dn is invalid */
+				p++;
+				continue;
+			}
 
-		return p; /* return on the separator */
-	}
+			if (is_oid && ( ! (isdigit(*p) || (*p == '.')))) {
+				/* not a digit nor a dot, invalid attribute oid */
+				dn->invalid = true;
+				goto failed;
+			} else
+			if ( ! (isalpha(*p) || isdigit(*p) || (*p == '-'))) {
+				/* not ALPHA, DIGIT or HYPHEN */
+				dn->invalid = true;
+				goto failed;
+			}
 
-	/* no quotes found seek to separators */
-	q = p;
-	do {
-		escaped = 0;
-		ret = strcspn(q, separators);
-		
-		if (q[ret - 1] == '\\') {
-			escaped = 1;
-			q = q + ret + 1;
+			*d++ = *p++;
+			continue;
 		}
-	} while (escaped);
-
-	if (ret == 0 && p == q) /* no separators ?! bail out */
-		return NULL;
 
-	return q + ret;
+		if (in_value) {
+			if (in_quote) {
+				if (*p == '\"') {
+					if (p[-1] != '\\') {
+						p++;
+						in_quote = false;
+						continue;
+					}
+				}
+				*d++ = *p++;
+				l++;
+				continue;
+			}
 
-failed:
-	return NULL;
-}
+			if (trim) {
+				if (*p == ' ') {
+					p++;
+					continue;
+				}
 
-static char *ldb_dn_trim_string(char *string, const char *edge)
-{
-	char *s, *p;
+				/* first char */
+				trim = false;
 
-	/* seek out edge from start of string */
-	s = string + strspn(string, edge);
+				if (*p == '\"') {
+					in_quote = true;
+					p++;
+					continue;
+				}
+			}
 
-	/* backwards skip from end of string */
-	p = &s[strlen(s) - 1];
-	while (p > s && strchr(edge, *p)) {
-		*p = '\0';
-		p--;
-	}
+			switch (*p) {
 
-	return s;
-}
+			/* TODO: support ber encoded values
+			case '#':
+			*/
 
-/* we choosed to not support multpile valued components */
-static struct ldb_dn_component ldb_dn_explode_component(void *mem_ctx, char *raw_component)
-{
-	struct ldb_dn_component dc;
-	char *p;
-	int ret, qs, qe;
+			case ',':
+				if (escape) {
+					*d++ = *p++;
+					l++;
+					escape = false;
+					continue;
+				}
+				/* ok found value terminator */
 
-	memset(&dc, 0, sizeof(dc));
+				if ( t ) {
+					/* trim back */
+					d -= (p - t);
+					l -= (p - t);
+				}
 
-	if (raw_component == NULL) {
-		return dc;
-	}
+				in_attr = true;
+				in_value = false;
+				trim = true;
 
-	/* find attribute type/value separator */
-	p = strchr(raw_component, '=');
-	LDB_DN_NULL_FAILED(p);
+				p++;
+				*d++ = '\0';
+				dn->components[dn->comp_num].value.data = (uint8_t *)dt;
+				dn->components[dn->comp_num].value.length = l;
+				dt = d;
+
+				dn->comp_num++;
+				if (dn->comp_num > 2) {
+					dn->components = talloc_realloc(dn,
+									dn->components,
+									struct ldb_dn_component,
+									dn->comp_num + 1);
+					if ( ! dn->components) {
+						/* ouch ! */
+						goto failed;
+					}
+					/* make sure all components are zeroed, other functions depend on this */
+					memset(&dn->components[dn->comp_num], '\0', sizeof(struct ldb_dn_component));
+				}
 
-	*p++ = '\0'; /* terminate name and point to value */
+				continue;
 
-	/* copy and trim name in the component */
-	dc.name = talloc_strdup(mem_ctx, ldb_dn_trim_string(raw_component, " \n"));
-	if (!dc.name)
-		return dc;
+			case '=':
+			case '\n':
+			case '+':
+			case '<':
+			case '>':
+			case '#':
+			case ';':
+			case '\"':
+				/* a string with not escaped specials is invalid (tested) */
+				if ( ! escape) {
+					dn->invalid = true;
+					goto failed;
+				}
+				escape = false;
+
+				*d++ = *p++;
+				l++;
+
+				if ( t ) t = NULL;
+				break;
+
+			case '\\':
+				if ( ! escape) {
+					escape = true;
+					p++;
+					continue;
+				}
+				escape = false;
+
+				*d++ = *p++;
+				l++;
+
+				if ( t ) t = NULL;
+				break;
+
+			default:
+				if (escape) {
+	 				if (sscanf(p, "%02x", &x) != 1) {
+						/* invalid escaping sequence */
+						dn->invalid = true;
+						goto failed;
+					}
+					escape = false;
+
+					p += 2;
+					*d++ = (unsigned char)x;
+					l++;
+
+					if ( t ) t = NULL;
+					break;
+				}
+
+				if (*p == ' ') { 
+					if ( ! t) t = p;
+				} else {
+					if ( t ) t = NULL;
+				}
+
+				*d++ = *p++;
+				l++;
+				
+				break;
+			}
 
-	if (! ldb_valid_attr_name(dc.name)) {
-		goto failed;
+		}
 	}
 
-	ret = get_quotes_position(p, &qs, &qe);
-
-	switch (ret) {
-	case 0: /* no quotes trim the string */
-		p = ldb_dn_trim_string(p, " \n");
-		dc.value = ldb_dn_unescape_value(mem_ctx, p);
-		break;
-
-	case 1: /* quotes found get the unquoted string */
-		p[qe] = '\0';
-		p = p + qs + 1;
-		dc.value.length = strlen(p);
-		dc.value.data = (uint8_t *)talloc_memdup(mem_ctx, p,
-							 dc.value.length + 1);
-		break;
-
-	default: /* mismatched quotes ot other error, bail out */
+	if (in_attr || in_quote) {
+		/* invalid dn */
+		dn->invalid = true;
 		goto failed;
 	}
 
-	if (dc.value.length == 0) {
-		goto failed;
+	/* save last element */
+	if ( t ) {
+		/* trim back */
+		d -= (p - t);
+		l -= (p - t);
 	}
 
-	return dc;
+	*d++ = '\0';
+	dn->components[dn->comp_num].value.data = (uint8_t *)dt;
+	dn->components[dn->comp_num].value.length = l;
+
+	dn->comp_num++;
+
+	dn->valid_comp = true;
+	return true;
 
 failed:
-	talloc_free(dc.name);
-	dc.name = NULL;
-	return dc;
+	talloc_free(dn->components);
+	return false;
 }
 
-struct ldb_dn *ldb_dn_new(void *mem_ctx)
+bool ldb_dn_validate(struct ldb_dn *dn)
 {
-	struct ldb_dn *edn;
-
-	edn = talloc(mem_ctx, struct ldb_dn);
-	LDB_DN_NULL_FAILED(edn);
-
-	/* Initially there are no components */
-	edn->comp_num = 0;
-	edn->components = NULL;
-
-	return edn;
-
-failed:
-	return NULL;
+	return ldb_dn_explode(dn);
 }
 
-/*
-  explode a DN string into a ldb_dn structure
-*/
-struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn)
+const char *ldb_dn_get_linearized(struct ldb_dn *dn)
 {
-	struct ldb_dn *edn; /* the exploded dn */
-	char *pdn, *p;
+	int i, len;
+	char *d, *n;
+
+	if ( ! dn || ( dn->invalid)) return NULL;
 
-	if (dn == NULL) return NULL;
+	if (dn->valid_lin) return dn->linearized;
 
-	/* Allocate a structure to hold the exploded DN */
-	edn = ldb_dn_new(mem_ctx);
-	if (edn == NULL) {
+	if ( ! dn->valid_comp) {
+		dn->invalid = true;
 		return NULL;
 	}
 
-	pdn = NULL;
-
-	/* Empty DNs */
-	if (dn[0] == '\0') {
-		return edn;
+	if (dn->comp_num == 0) {
+		dn->linearized = talloc_strdup(dn, "");
+		if ( ! dn->linearized) return NULL;
+		dn->valid_lin = true;
+		return dn->linearized;
 	}
 
-	/* 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, LDB_SPECIAL);
-		if (edn->components[0].name == NULL) goto failed;
-		edn->components[0].value.data = (uint8_t *)talloc_strdup(edn->components, dn);
-		if (edn->components[0].value.data== NULL) goto failed;
-		edn->components[0].value.length = strlen(dn);
-		return edn;
+	/* calculate maximum possible length of DN */
+	for (len = 0, i = 0; i < dn->comp_num; i++) {
+		len += strlen(dn->components[i].name); /* name len */
+		len += (dn->components[i].value.length * 3); /* max escaped data len */
+		len += 2; /* '=' and ',' */
 	}
+	dn->linearized = talloc_array(dn, char, len);
+	if ( ! dn->linearized) return NULL;
 
-	pdn = p = talloc_strdup(edn, dn);
-	LDB_DN_NULL_FAILED(pdn);
+	d = dn->linearized;
 
-	/* get the components */
-	do {
-		char *t;
+	for (i = 0; i < dn->comp_num; i++) {
 
-		/* terminate the current component and return pointer to the next one */
-		t = seek_to_separator(p, ",;");
-		LDB_DN_NULL_FAILED(t);
+		/* copy the name */
+		n = dn->components[i].name;
+		while (*n) *d++ = *n++;
 
-		if (*t) { /* here there is a separator */
-			*t = '\0'; /*terminate */
-			t++; /* a separtor means another component follows */
-		}
-
-		/* allocate space to hold the dn component */
-		edn->components = talloc_realloc(edn, edn->components,
-						 struct ldb_dn_component,
-						 edn->comp_num + 1);
-		if (edn->components == NULL)
-			goto failed;
+		*d++ = '=';
 
-		/* store the exploded component in the main structure */
-		edn->components[edn->comp_num] = ldb_dn_explode_component(edn, p);
-		LDB_DN_NULL_FAILED(edn->components[edn->comp_num].name);
+		/* and the value */
+		d += ldb_dn_escape_internal( d,
+				(char *)dn->components[i].value.data,
+				dn->components[i].value.length);
+		*d++ = ',';
+	}
 
-		edn->comp_num++;
+	*(--d) = '\0';
 
-		/* jump to the next component if any */
-		p = t;
+	dn->valid_lin = true;
 
-	} while(*p);
+	/* don't waste more memory than necessary */
+	dn->linearized = talloc_realloc(dn, dn->linearized, char, (d - dn->linearized + 1));
 
-	talloc_free(pdn);
-	return edn;
+	return dn->linearized;
+}
 
-failed:
-	talloc_free(pdn);
-	talloc_free(edn);
-	return NULL;
+char *ldb_dn_linearize(void *mem_ctx, struct ldb_dn *dn)
+{
+	return talloc_strdup(mem_ctx, ldb_dn_get_linearized(dn));
 }
 
-struct ldb_dn *ldb_dn_explode_or_special(void *mem_ctx, const char *dn)
+/*
+  casefold a dn. We need to casefold the attribute names, and canonicalize 
+  attribute values of case insensitive attributes.
+*/
+
+static bool ldb_dn_casefold_internal(struct ldb_dn *dn)
 {
-	struct ldb_dn *edn; /* the exploded dn */
+	int i, ret;
 
-	if (dn == NULL) return NULL;
+	if ( ! dn || dn->invalid) return false;
 
-	if (strncasecmp(dn, "<GUID=", 6) == 0) {
-		/* this is special DN returned when the
-		 * exploded_dn control is used
-		 */
+	if (dn->valid_case) return true;
+
+	if (( ! dn->valid_comp) && ( ! ldb_dn_explode(dn))) {
+		return false;
+	}
 
-		/* Allocate a structure to hold the exploded DN */
-		edn = ldb_dn_new(mem_ctx);
+	for (i = 0; i < dn->comp_num; i++) {
+		struct ldb_dn_component dc;
+		const struct ldb_attrib_handler *h;
 
-		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, LDB_SPECIAL);
-		if (edn->components[0].name == NULL) goto failed;
-		edn->components[0].value.data = (uint8_t *)talloc_strdup(edn->components, dn);
-		if (edn->components[0].value.data== NULL) goto failed;
-		edn->components[0].value.length = strlen(dn);
-		return edn;
+		memset(&dc, 0, sizeof(dc));
+		dn->components[i].cf_name = ldb_attr_casefold(dn->components, dn->components[i].name);
+		if (!dn->components[i].cf_name) {
+			return false;
+		}
 
+		h = ldb_attrib_handler(dn->ldb, dn->components[i].cf_name);
+		ret = h->canonicalise_fn(dn->ldb, dn->components,
+					 &(dn->components[i].value),
+					 &(dn->components[i].cf_value));
+		if (ret != 0) {
+			return false;
+		}
 	}
-	
-	return ldb_dn_explode(mem_ctx, dn);
 
-failed:
-	talloc_free(edn);
-	return NULL;
+	return true;
 }
 
-char *ldb_dn_linearize(void *mem_ctx, const struct ldb_dn *edn)
+const char *ldb_dn_get_casefold(struct ldb_dn *dn)
 {
-	char *dn, *value;
-	int i;
-
-	if (edn == NULL) return NULL;
+	int i, len;
+	char *d, *n;
 
-	/* Special DNs */
-	if (ldb_dn_is_special(edn)) {
-		dn = talloc_strdup(mem_ctx, (char *)edn->components[0].value.data);
-		return dn;
+	if ( ! ldb_dn_casefold_internal(dn)) {
+		return NULL;
 	}
 
-	dn = talloc_strdup(mem_ctx, "");
-	LDB_DN_NULL_FAILED(dn);
-
-	for (i = 0; i < edn->comp_num; i++) {
-		value = ldb_dn_escape_value(dn, edn->components[i].value);
-		LDB_DN_NULL_FAILED(value);
+	if (dn->casefold) return dn->casefold;
 
-		if (i == 0) {
-			dn = talloc_asprintf_append(dn, "%s=%s", edn->components[i].name, value);
+	if (dn->comp_num == 0) {
+		if (dn->special) {
+			len = strlen(dn->linearized);
+			dn->casefold = talloc_array(dn, char, len * 3 + 1);
+			if ( ! dn->casefold) return NULL;
+			ldb_dn_escape_internal(dn->casefold, dn->linearized, len);
+			/* don't waste more memory than necessary */
+			dn->casefold = talloc_realloc(dn, dn->casefold, char, strlen(dn->casefold) + 1);
 		} else {
-			dn = talloc_asprintf_append(dn, ",%s=%s", edn->components[i].name, value);
+			dn->casefold = talloc_strdup(dn, "");
+			if ( ! dn->casefold) return NULL;
 		}
-		LDB_DN_NULL_FAILED(dn);
+		dn->valid_case = true;
+		return dn->casefold;
+	}
 
-		talloc_free(value);
+	/* calculate maximum possible length of DN */
+	for (len = 0, i = 0; i < dn->comp_num; i++) {
+		len += strlen(dn->components[i].cf_name); /* name len */
+		len += (dn->components[i].cf_value.length * 3); /* max escaped data len */
+		len += 2; /* '=' and ',' */
 	}
+	dn->casefold = talloc_array(dn, char, len);
+	if ( ! dn->casefold) return NULL;
 
-	return dn;
+	d = dn->casefold;
 
-failed:
-	talloc_free(dn);
-	return NULL;
+	for (i = 0; i < dn->comp_num; i++) {
+
+		/* copy the name */
+		n = dn->components[i].cf_name;
+		while (*n) *d++ = *n++;
+
+		*d++ = '=';
+
+		/* and the value */
+		d += ldb_dn_escape_internal( d,
+				(char *)dn->components[i].cf_value.data,
+				dn->components[i].cf_value.length);
+		*d++ = ',';
+	}
+	*(--d) = '\0';
+
+	dn->valid_case = true;
+
+	return dn->casefold;
+}
+
+char *ldb_dn_casefold(void *mem_ctx, struct ldb_dn *dn)
+{
+	return talloc_strdup(mem_ctx, ldb_dn_get_casefold(dn));
 }
 
 /* Determine if dn is below base, in the ldap tree.  Used for
@@ -504,42 +674,65 @@ failed:
  * 0 if they match, otherwise non-zero
  */
 
-int ldb_dn_compare_base(struct ldb_context *ldb,
-			const struct ldb_dn *base,
-			const struct ldb_dn *dn)
+int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
 {
 	int ret;
-	int n0, n1;
+	int n_base, n_dn;
+
+	if ( ! base || base->invalid) return 1;
+	if ( ! dn || dn->invalid) return -1;
+
+	if (( ! base->valid_case) || ( ! dn->valid_case)) {
+		if (base->valid_lin && dn->valid_lin) {
+			/* try with a normal compare first, if we are lucky
+			 * we will avoid exploding and casfolding */
+			int dif;
+			dif = strlen(dn->linearized) - strlen(base->linearized);
+			if (dif < 0) return dif;
+			if (strcmp(base->linearized, &dn->linearized[dif]) == 0) return 0;
+		}
 
-	if (base == NULL || base->comp_num == 0) return 0;
-	if (dn == NULL || dn->comp_num == 0) return -1;
+		if ( ! ldb_dn_casefold_internal(base)) {
+			return 1;
+		}
 
-	/* if the base has more componts than the dn, then they differ */
+		if ( ! ldb_dn_casefold_internal(dn)) {
+			return -1;
+		}
+
+	}
+
+	/* if base has more components,
+	 * they don't have the same base */
 	if (base->comp_num > dn->comp_num) {
 		return (dn->comp_num - base->comp_num);
 	}
 
-	n0 = base->comp_num - 1;
-	n1 = dn->comp_num - 1;
-	while (n0 >= 0 && n1 >= 0) {
-		const struct ldb_attrib_handler *h;
-
-		/* compare names (attribute names are guaranteed to be ASCII only) */
-		ret = ldb_attr_cmp(base->components[n0].name,
-				   dn->components[n1].name);
-		if (ret) {
-			return ret;
+	if (dn->comp_num == 0) {
+		if (dn->special && base->special) {
+			return strcmp(base->linearized, dn->linearized);
+		} else {
+			return 0;
 		}
+	}
+
+	n_base = base->comp_num - 1;
+	n_dn = dn->comp_num - 1;
 
-		/* names match, compare values */
-		h = ldb_attrib_handler(ldb, base->components[n0].name);
-		ret = h->comparison_fn(ldb, ldb, &(base->components[n0].value),
-						  &(dn->components[n1].value));
-		if (ret) {
-			return ret;
+	while (n_base >= 0) {
+		/* compare attr names */
+		ret = strcmp(base->components[n_base].cf_name, dn->components[n_dn].cf_name);
+		if (ret != 0) return ret;
+
+		/* compare attr.cf_value. */ 
+		if (base->components[n_base].cf_value.length != dn->components[n_dn].cf_value.length) {
+			return base->components[n_base].cf_value.length - dn->components[n_dn].cf_value.length;
 		}
-		n1--;
-		n0--;
+		ret = strcmp((char *)base->components[n_base].cf_value.data, (char *)dn->components[n_dn].cf_value.data);
+		if (ret != 0) return ret;
+
+		n_base--;
+		n_dn--;
 	}
 
 	return 0;
@@ -550,350 +743,433 @@ int ldb_dn_compare_base(struct ldb_context *ldb,
    If they match, then return 0
  */
 
-int ldb_dn_compare(struct ldb_context *ldb,
-		   const struct ldb_dn *edn0,
-		   const struct ldb_dn *edn1)
+int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
 {
-	if (edn0 == NULL || edn1 == NULL) return edn1 - edn0;
+	int i, ret;
 
-	if (edn0->comp_num != edn1->comp_num)
-		return (edn1->comp_num - edn0->comp_num);
+	if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) return -1;
 
-	return ldb_dn_compare_base(ldb, edn0, edn1);
+	if (( ! dn0->valid_case) || ( ! dn1->valid_case)) {
+		if (dn0->valid_lin && dn1->valid_lin) {
+			/* try with a normal compare first, if we are lucky
+			 * we will avoid exploding and casfolding */
+			if (strcmp(dn0->linearized, dn1->linearized) == 0) return 0;
+		}
+
+		if ( ! ldb_dn_casefold_internal(dn0)) {
+			return 1;
+		}
+
+		if ( ! ldb_dn_casefold_internal(dn1)) {
+			return -1;
+		}
+
+	}
+
+	if (dn0->comp_num != dn1->comp_num) {
+		return (dn1->comp_num - dn0->comp_num);
+	}
+
+	if (dn0->comp_num == 0) {
+		if (dn0->special && dn1->special) {
+			return strcmp(dn0->linearized, dn1->linearized);
+		} else {
+			return 0;
+		}
+	}
+
+	for (i = 0; i < dn0->comp_num; i++) {
+		/* compare attr names */
+		ret = strcmp(dn0->components[i].cf_name, dn1->components[i].cf_name);
+		if (ret != 0) return ret;
+
+		/* compare attr.cf_value. */ 
+		if (dn0->components[i].cf_value.length != dn1->components[i].cf_value.length) {
+			return dn0->components[i].cf_value.length - dn1->components[i].cf_value.length;
+		}
+		ret = strcmp((char *)dn0->components[i].cf_value.data, (char *)dn1->components[i].cf_value.data);
+		if (ret != 0) return ret;
+	}
+
+	return 0;
 }
 
-int ldb_dn_cmp(struct ldb_context *ldb, const char *dn0, const char *dn1)
+static struct ldb_dn_component ldb_dn_copy_component(void *mem_ctx, struct ldb_dn_component *src)
 {
-	struct ldb_dn *edn0;
-	struct ldb_dn *edn1;
-	int ret;
+	struct ldb_dn_component dst;
+
+	memset(&dst, 0, sizeof(dst));
 
-	if (dn0 == NULL || dn1 == NULL) return dn1 - dn0;
+	if (src == NULL) {
+		return dst;
+	}
 
-	edn0 = ldb_dn_explode_casefold(ldb, ldb, dn0);
-	if (edn0 == NULL) return 1;
+	dst.value = ldb_val_dup(mem_ctx, &(src->value));
+	if (dst.value.data == NULL) {
+		return dst;
+	}
 
-	edn1 = ldb_dn_explode_casefold(ldb, ldb, dn1);
-	if (edn1 == NULL) {
-		talloc_free(edn0);
-		return -1;
+	dst.name = talloc_strdup(mem_ctx, src->name);
+	if (dst.name == NULL) {
+		LDB_FREE(dst.value.data);
 	}
 
-	ret = ldb_dn_compare(ldb, edn0, edn1);
+	if (src->cf_value.data) {
+		dst.cf_value = ldb_val_dup(mem_ctx, &(src->cf_value));
+		if (dst.cf_value.data == NULL) {
+			LDB_FREE(dst.value.data);
+			LDB_FREE(dst.name);
+			return dst;
+		}
 
-	talloc_free(edn0);
-	talloc_free(edn1);
+		dst.cf_name = talloc_strdup(mem_ctx, src->cf_name);
+		if (dst.cf_name == NULL) {
+			LDB_FREE(dst.cf_name);
+			LDB_FREE(dst.value.data);
+			LDB_FREE(dst.name);
+			return dst;
+		}
+	} else {
+		dst.cf_value.data = NULL;
+		dst.cf_name = NULL;
+	}
 
-	return ret;
+	return dst;
 }
 
-/*
-  casefold a dn. We need to casefold the attribute names, and canonicalize 
-  attribute values of case insensitive attributes.
-*/
-struct ldb_dn *ldb_dn_casefold(struct ldb_context *ldb, void *mem_ctx, const struct ldb_dn *edn)
+struct ldb_dn *ldb_dn_copy(void *mem_ctx, struct ldb_dn *dn)
 {
-	struct ldb_dn *cedn;
-	int i, ret;
-
-	if (edn == NULL) return NULL;
+	struct ldb_dn *new_dn;
 
-	cedn = ldb_dn_new(mem_ctx);
-	if (!cedn) {
+	if (!dn || dn->invalid) {
 		return NULL;
 	}
 
-	cedn->comp_num = edn->comp_num;
-	cedn->components = talloc_array(cedn, struct ldb_dn_component, edn->comp_num);
-	if (!cedn->components) {
-		talloc_free(cedn);
+	new_dn = talloc_zero(mem_ctx, struct ldb_dn);
+	if ( !new_dn) {
 		return NULL;
 	}
 
-	for (i = 0; i < edn->comp_num; i++) {
-		struct ldb_dn_component dc;
-		const struct ldb_attrib_handler *h;
+	*new_dn = *dn;
 
-		memset(&dc, 0, sizeof(dc));
-		dc.name = ldb_attr_casefold(cedn->components, edn->components[i].name);
-		if (!dc.name) {
-			talloc_free(cedn);
+	if (dn->valid_comp) {
+		int i;
+
+		new_dn->components = talloc_zero_array(new_dn, struct ldb_dn_component, dn->comp_num);
+		if ( ! new_dn->components) {
+			talloc_free(new_dn);
 			return NULL;
 		}
 
-		h = ldb_attrib_handler(ldb, dc.name);
-		ret = h->canonicalise_fn(ldb, cedn->components,
-					 &(edn->components[i].value),
-					 &(dc.value));
-		if (ret != 0) {
-			talloc_free(cedn);
-			return NULL;
+		for (i = 0; i < dn->comp_num; i++) {
+			new_dn->components[i] = ldb_dn_copy_component(new_dn->components, &dn->components[i]);
+			if ( ! new_dn->components[i].value.data) {
+				talloc_free(new_dn);
+				return NULL;
+			}
 		}
 
-		cedn->components[i] = dc;
+		if (dn->casefold) {
+			new_dn->casefold = talloc_strdup(new_dn, dn->casefold);
+			if ( ! new_dn->casefold) {
+				talloc_free(new_dn);
+				return NULL;
+			}
+		}
 	}
 
-	return cedn;
+	if (dn->valid_lin) {
+		new_dn->linearized = talloc_strdup(new_dn, dn->linearized);
+		if ( ! new_dn->linearized) {
+			talloc_free(new_dn);
+			return NULL;
+		}
+	}
+
+	return new_dn;
 }
 
-struct ldb_dn *ldb_dn_explode_casefold(struct ldb_context *ldb, void *mem_ctx, const char *dn)
+/* modify the given dn by adding a base.
+ *
+ * return true if successful and false if not
+ * if false is returned the dn may be marked invalid
+ */
+bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base)
 {
-	struct ldb_dn *edn, *cdn;
+	const char *s;
+	char *t;
 
-	if (dn == NULL) return NULL;
+	if ( !base || base->invalid || !dn || dn->invalid) {
+		return false;
+	}
 
-	edn = ldb_dn_explode(ldb, dn);
-	if (edn == NULL) return NULL;
+	if (dn->valid_comp) {
+		int i;
 
-	cdn = ldb_dn_casefold(ldb, mem_ctx, edn);
-	
-	talloc_free(edn);
-	return cdn;
-}
+		if ( ! ldb_dn_validate(base)) {
+			return false;
+		}
 
-char *ldb_dn_linearize_casefold(struct ldb_context *ldb, void *mem_ctx, const struct ldb_dn *edn)
-{
-	struct ldb_dn *cdn;
-	char *dn;
+		s = NULL;
+		if (dn->valid_case) {
+			if ( ! (s = ldb_dn_get_casefold(base))) {
+				return false;
+			}
+		}
 
-	if (edn == NULL) return NULL;
+		dn->components = talloc_realloc(dn,
+						dn->components,
+						struct ldb_dn_component,
+						dn->comp_num + base->comp_num);
+		if ( ! dn->components) {
+			dn->invalid = true;
+			return false;
+		}
 
-	/* Special DNs */
-	if (ldb_dn_is_special(edn)) {
-		dn = talloc_strdup(mem_ctx, (char *)edn->components[0].value.data);
-		return dn;
+		for (i = 0; i < base->comp_num; dn->comp_num++, i++) {
+			dn->components[dn->comp_num] = ldb_dn_copy_component(dn->components, &base->components[i]);
+			if (dn->components[dn->comp_num].value.data == NULL) {
+				dn->invalid = true;
+				return false;
+			}
+		}
+
+		if (s) {
+			t = talloc_asprintf(dn, "%s,%s", dn->casefold, s);
+			LDB_FREE(dn->casefold);
+			dn->casefold = t;
+		}
 	}
 
-	cdn = ldb_dn_casefold(ldb, mem_ctx, edn);
-	if (cdn == NULL) return NULL;
+	if (dn->valid_lin) {
 
-	dn = ldb_dn_linearize(ldb, cdn);
-	if (dn == NULL) {
-		talloc_free(cdn);
-		return NULL;
+		s = ldb_dn_get_linearized(base);
+		if ( ! s) {
+			return false;
+		}
+		
+		t = talloc_asprintf(dn, "%s,%s", dn->linearized, s);
+		if ( ! t) {
+			dn->invalid = true;
+			return false;
+		}
+		LDB_FREE(dn->linearized);
+		dn->linearized = t;
 	}
 
-	talloc_free(cdn);
-	return dn;
+	return true;
 }
 
-static struct ldb_dn_component ldb_dn_copy_component(void *mem_ctx, struct ldb_dn_component *src)
+/* modify the given dn by adding a base.
+ *
+ * return true if successful and false if not
+ * if false is returned the dn may be marked invalid
+ */
+bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...)
 {
-	struct ldb_dn_component dst;
-
-	memset(&dst, 0, sizeof(dst));
+	struct ldb_dn *base;
+	char *base_str;
+	va_list ap;
+	bool ret;
 
-	if (src == NULL) {
-		return dst;
+	if ( !dn || dn->invalid) {
+		return false;
 	}
 
-	dst.value = ldb_val_dup(mem_ctx, &(src->value));
-	if (dst.value.data == NULL) {
-		return dst;
-	}
+	va_start(ap, base_fmt);
+	base_str = talloc_vasprintf(dn, base_fmt, ap);
+	va_end(ap);
 
-	dst.name = talloc_strdup(mem_ctx, src->name);
-	if (dst.name == NULL) {
-		talloc_free(dst.value.data);
-		dst.value.data = NULL;
+	if (base_str == NULL) {
+		return false;
 	}
 
-	return dst;
-}
+	base = ldb_dn_new(base_str, dn->ldb, base_str);
 
-/* Copy a DN but replace the old with the new base DN. */
-struct ldb_dn *ldb_dn_copy_rebase(void *mem_ctx, const struct ldb_dn *old, const struct ldb_dn *old_base, const struct ldb_dn *new_base)
+	ret = ldb_dn_add_base(dn, base);
+
+	talloc_free(base_str);
+
+	return ret;
+}	
+
+/* modify the given dn by adding children elements.
+ *
+ * return true if successful and false if not
+ * if false is returned the dn may be marked invalid
+ */
+bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child)
 {
-	struct ldb_dn *new_dn;
-	int i, offset;
+	const char *s;
+	char *t;
 
-	/* Perhaps we don't need to rebase at all? */
-	if (!old_base || !new_base) {
-		return ldb_dn_copy(mem_ctx, old);
+	if ( !child || child->invalid || !dn || dn->invalid) {
+		return false;
 	}
 
-	offset = old->comp_num - old_base->comp_num;
-	new_dn = ldb_dn_copy_partial(mem_ctx, new_base, offset + new_base->comp_num);
-	for (i = 0; i < offset; i++) {
-		new_dn->components[i] = ldb_dn_copy_component(new_dn->components, &(old->components[i]));
-	}
+	if (dn->valid_comp) {
+		int n, i, j;
 
-	return new_dn;
-}
+		if ( ! ldb_dn_validate(child)) {
+			return false;
+		}
 
-/* 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 than 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 *newdn;
-	int i, n, e;
+		s = NULL;
+		if (dn->valid_case) {
+			if ( ! (s = ldb_dn_get_casefold(child))) {
+				return false;
+			}
+		}
+
+		n = dn->comp_num + child->comp_num;
 
-	if (dn == NULL) return NULL;
-	if (num_el <= 0) return NULL;
+		dn->components = talloc_realloc(dn,
+						dn->components,
+						struct ldb_dn_component,
+						n);
+		if ( ! dn->components) {
+			dn->invalid = true;
+			return false;
+		}
 
-	newdn = ldb_dn_new(mem_ctx);
-	LDB_DN_NULL_FAILED(newdn);
+		for (i = dn->comp_num - 1, j = n - 1; i >= 0; i--, j--) {
+			dn->components[j] = dn->components[i];
+		}
 
-	newdn->comp_num = num_el;
-	n = newdn->comp_num - 1;
-	newdn->components = talloc_array(newdn, struct ldb_dn_component, newdn->comp_num);
-	if (newdn->components == NULL) goto failed;
+		for (i = 0; i < child->comp_num; i++) {	
+			dn->components[i] = ldb_dn_copy_component(dn->components, &child->components[i]);
+			if (dn->components[i].value.data == NULL) {
+				dn->invalid = true;
+				return false;
+			}
+		}
 
-	if (dn->comp_num == 0) return newdn;
-	e = dn->comp_num - 1;
+		dn->comp_num = n;
 
-	for (i = 0; i < newdn->comp_num; i++) {
-		newdn->components[n - i] = ldb_dn_copy_component(newdn->components,
-								&(dn->components[e - i]));
-		if ((e - i) == 0) {
-			return newdn;
+		if (s) {
+			t = talloc_asprintf(dn, "%s,%s", s, dn->casefold);
+			LDB_FREE(dn->casefold);
+			dn->casefold = t;
 		}
 	}
 
-	return newdn;
+	if (dn->valid_lin) {
 
-failed:
-	talloc_free(newdn);
-	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);
-}
+		s = ldb_dn_get_linearized(child);
+		if ( ! s) {
+			return false;
+		}
+		
+		t = talloc_asprintf(dn, "%s,%s", s, dn->linearized);
+		if ( ! t) {
+			dn->invalid = true;
+			return false;
+		}
+		LDB_FREE(dn->linearized);
+		dn->linearized = t;
+	}
 
-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);
+	return true;
 }
 
-struct ldb_dn_component *ldb_dn_build_component(void *mem_ctx, const char *attr,
-						const char *val)
+/* modify the given dn by adding children elements.
+ *
+ * return true if successful and false if not
+ * if false is returned the dn may be marked invalid
+ */
+bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...)
 {
-	struct ldb_dn_component *dc;
+	struct ldb_dn *child;
+	char *child_str;
+	va_list ap;
+	bool ret;
 
-	if (attr == NULL || val == NULL) return NULL;
+	if ( !dn || dn->invalid) {
+		return false;
+	}
 
-	dc = talloc(mem_ctx, struct ldb_dn_component);
-	if (dc == NULL) return NULL;
+	va_start(ap, child_fmt);
+	child_str = talloc_vasprintf(dn, child_fmt, ap);
+	va_end(ap);
 
-	dc->name = talloc_strdup(dc, attr);
-	if (dc->name ==  NULL) {
-		talloc_free(dc);
-		return NULL;
+	if (child_str == NULL) {
+		return false;
 	}
 
-	dc->value.data = (uint8_t *)talloc_strdup(dc, val);
-	if (dc->value.data ==  NULL) {
-		talloc_free(dc);
-		return NULL;
-	}
+	child = ldb_dn_new(child_str, dn->ldb, child_str);
+
+	ret = ldb_dn_add_child(dn, child);
 
-	dc->value.length = strlen(val);
+	talloc_free(child_str);
 
-	return dc;
+	return ret;
 }
 
-struct ldb_dn *ldb_dn_build_child(void *mem_ctx, const char *attr,
-						 const char * value,
-						 const struct ldb_dn *base)
+bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num)
 {
-	struct ldb_dn *newdn;
-	if (! ldb_valid_attr_name(attr)) return NULL;
-	if (value == NULL || value == '\0') return NULL; 
-
-	if (base != NULL) {
-		newdn = ldb_dn_copy_partial(mem_ctx, base, base->comp_num + 1);
-		LDB_DN_NULL_FAILED(newdn);
-	} else {
-		newdn = ldb_dn_new(mem_ctx);
-		LDB_DN_NULL_FAILED(newdn);
-
-		newdn->comp_num = 1;
-		newdn->components = talloc_array(newdn, struct ldb_dn_component, newdn->comp_num);
+	if ( ! ldb_dn_validate(dn)) {
+		return false;
 	}
 
-	newdn->components[0].name = talloc_strdup(newdn->components, attr);
-	LDB_DN_NULL_FAILED(newdn->components[0].name);
+	if (dn->comp_num < num) {
+		return false;
+	}
 
-	newdn->components[0].value.data = (uint8_t *)talloc_strdup(newdn->components, value);
-	LDB_DN_NULL_FAILED(newdn->components[0].value.data);
-	newdn->components[0].value.length = strlen((char *)newdn->components[0].value.data);
+	dn->comp_num -= num;
 
-	return newdn;
+	dn->valid_case = false;
 
-failed:
-	talloc_free(newdn);
-	return NULL;
+	if (dn->valid_lin) {	
+		dn->valid_lin = false;
+		LDB_FREE(dn->linearized);
+	}
 
+	return true;
 }
 
-struct ldb_dn *ldb_dn_compose(void *mem_ctx, const struct ldb_dn *dn1, const struct ldb_dn *dn2)
+bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num)
 {
-	int i;
-	struct ldb_dn *newdn;
+	int i, j;
 
-	if (dn2 == NULL && dn1 == NULL) {
-		return NULL;
+	if ( ! ldb_dn_validate(dn)) {
+		return false;
 	}
 
-	if (dn2 == NULL) {
-		newdn = ldb_dn_new(mem_ctx);
-		LDB_DN_NULL_FAILED(newdn);
-
-		newdn->comp_num = dn1->comp_num;
-		newdn->components = talloc_array(newdn, struct ldb_dn_component, newdn->comp_num);
-	} else {
-		int comp_num = dn2->comp_num;
-		if (dn1 != NULL) comp_num += dn1->comp_num;
-		newdn = ldb_dn_copy_partial(mem_ctx, dn2, comp_num);
-		LDB_DN_NULL_FAILED(newdn);
+	if (dn->comp_num < num) {
+		return false;
 	}
 
-	if (dn1 == NULL) {
-		return newdn;
+	for (i = 0, j = num; j < dn->comp_num; i++, j++) {
+		dn->components[i] = dn->components[j];
 	}
 
-	for (i = 0; i < dn1->comp_num; i++) {
-		newdn->components[i] = ldb_dn_copy_component(newdn->components,
-							   &(dn1->components[i]));
-		if (newdn->components[i].value.data == NULL) {
-			goto failed;
-		}
-	}
+	dn->comp_num -= num;
 
-	return newdn;
+	dn->valid_case = false;
 
-failed:
-	talloc_free(newdn);
-	return NULL;
+	if (dn->valid_lin) {	
+		dn->valid_lin = false;
+		LDB_FREE(dn->linearized);
+	}
+
+	return true;
 }
 
-struct ldb_dn *ldb_dn_string_compose(void *mem_ctx, const struct ldb_dn *base, const char *child_fmt, ...)
+struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, struct ldb_dn *dn)
 {
-	struct ldb_dn *dn, *dn1;
-	char *child_str;
-	va_list ap;
-	
-	if (child_fmt == NULL) return NULL;
-
-	va_start(ap, child_fmt);
-	child_str = talloc_vasprintf(mem_ctx, child_fmt, ap);
-	va_end(ap);
-
-	if (child_str == NULL) return NULL;
+	struct ldb_dn *new_dn;
 
-	dn1 = ldb_dn_explode(mem_ctx, child_str);
-	dn = ldb_dn_compose(mem_ctx, dn1, base);
+	new_dn = ldb_dn_copy(mem_ctx, dn);
+	if ( !new_dn ) {
+		return NULL;
+	}
 
-	talloc_free(child_str);
-	talloc_free(dn1);
+	if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
+		talloc_free(new_dn);
+		return NULL;
+	}
 
-	return dn;
+	return new_dn;
 }
 
 /* Create a 'canonical name' string from a DN:
@@ -904,10 +1180,13 @@ struct ldb_dn *ldb_dn_string_compose(void *mem_ctx, const struct ldb_dn *base, c
    There are two formats, the EX format has the last / replaced with a newline (\n).
 
 */
-static char *ldb_dn_canonical(void *mem_ctx, const struct ldb_dn *dn, int ex_format) {
+static char *ldb_dn_canonical(void *mem_ctx, struct ldb_dn *dn, int ex_format) {
 	int i;
 	char *cracked = NULL;
-
+ 
+	if ( ! ldb_dn_validate(dn)) {
+		return NULL;
+	}
 	/* Walk backwards down the DN, grabbing 'dc' components at first */
 	for (i = dn->comp_num - 1 ; i >= 0; i--) {
 		if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
@@ -956,38 +1235,55 @@ static char *ldb_dn_canonical(void *mem_ctx, const struct ldb_dn *dn, int ex_for
 }
 
 /* Wrapper functions for the above, for the two different string formats */
-char *ldb_dn_canonical_string(void *mem_ctx, const struct ldb_dn *dn) {
+char *ldb_dn_canonical_string(void *mem_ctx, struct ldb_dn *dn) {
 	return ldb_dn_canonical(mem_ctx, dn, 0);
 
 }
 
-char *ldb_dn_canonical_ex_string(void *mem_ctx, const struct ldb_dn *dn) {
+char *ldb_dn_canonical_ex_string(void *mem_ctx, struct ldb_dn *dn) {
 	return ldb_dn_canonical(mem_ctx, dn, 1);
 }
 
-int ldb_dn_get_comp_num(const struct ldb_dn *dn)
+int ldb_dn_get_comp_num(struct ldb_dn *dn)
 {
+	if ( ! ldb_dn_validate(dn)) {
+		return -1;
+	}
 	return dn->comp_num;
 }
 
-const char *ldb_dn_get_component_name(const struct ldb_dn *dn, unsigned int num)
+const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
 {
+	if ( ! ldb_dn_validate(dn)) {
+		return NULL;
+	}
 	if (num >= dn->comp_num) return NULL;
 	return dn->components[num].name;
 }
 
-const struct ldb_val *ldb_dn_get_component_val(const struct ldb_dn *dn, unsigned int num)
+const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn, unsigned int num)
 {
+	if ( ! ldb_dn_validate(dn)) {
+		return NULL;
+	}
 	if (num >= dn->comp_num) return NULL;
 	return &dn->components[num].value;
 }
 
-const char *ldb_dn_get_rdn_name(const struct ldb_dn *dn) {
+const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
+{
+	if ( ! ldb_dn_validate(dn)) {
+		return NULL;
+	}
 	if (dn->comp_num == 0) return NULL;
 	return dn->components[0].name;
 }
 
-const struct ldb_val *ldb_dn_get_rdn_val(const struct ldb_dn *dn) {
+const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
+{
+	if ( ! ldb_dn_validate(dn)) {
+		return NULL;
+	}
 	if (dn->comp_num == 0) return NULL;
 	return &dn->components[0].value;
 }
@@ -997,6 +1293,10 @@ int ldb_dn_set_component(struct ldb_dn *dn, int num, const char *name, const str
 	char *n;
 	struct ldb_val v;
 
+	if ( ! ldb_dn_validate(dn)) {
+		return LDB_ERR_OTHER;
+	}
+
 	if (num >= dn->comp_num) {
 		return LDB_ERR_OTHER;
 	}
@@ -1017,5 +1317,39 @@ int ldb_dn_set_component(struct ldb_dn *dn, int num, const char *name, const str
 	dn->components[num].name = n;
 	dn->components[num].value = v;
 
+	if (dn->valid_case) dn->valid_case = false;
+	if (dn->casefold) LDB_FREE(dn->casefold);
+
 	return LDB_SUCCESS;
 }
+
+bool ldb_dn_is_valid(struct ldb_dn *dn)
+{
+	if ( ! dn) return false;
+	return ! dn->invalid;
+}
+
+bool ldb_dn_is_special(struct ldb_dn *dn)
+{
+	if ( ! dn || dn->invalid) return false;
+	return dn->special;
+}
+
+bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
+{
+	if ( ! dn || dn->invalid) return false;
+	return ! strcmp(dn->linearized, check);
+}
+
+bool ldb_dn_is_null(struct ldb_dn *dn)
+{
+	if ( ! dn || dn->invalid) return false;
+	if (dn->special) return false;
+	if (dn->valid_comp) {
+		if (dn->comp_num == 0) return true;
+		return false;
+	} else {
+		if (dn->linearized[0] == '\0') return true;
+	}
+	return false;
+}
diff --git a/source4/lib/ldb/common/ldb_ldif.c b/source4/lib/ldb/common/ldb_ldif.c
index 135ce9eecd..50e9f5e590 100644
--- a/source4/lib/ldb/common/ldb_ldif.c
+++ b/source4/lib/ldb/common/ldb_ldif.c
@@ -566,9 +566,9 @@ struct ldb_ldif *ldb_ldif_read(struct ldb_context *ldb,
 		goto failed;
 	}
 
-	msg->dn = ldb_dn_explode(msg, (char *)value.data);
+	msg->dn = ldb_dn_new(msg, ldb, (char *)value.data);
 
-	if (msg->dn == NULL) {
+	if ( ! ldb_dn_validate(msg->dn)) {
 		ldb_debug(ldb, LDB_DEBUG_ERROR, "Error: Unable to parse dn '%s'\n", 
 				  value.data);
 		goto failed;
diff --git a/source4/lib/ldb/common/ldb_match.c b/source4/lib/ldb/common/ldb_match.c
index 0cd220ad60..524214992b 100644
--- a/source4/lib/ldb/common/ldb_match.c
+++ b/source4/lib/ldb/common/ldb_match.c
@@ -40,8 +40,8 @@
   check if the scope matches in a search result
 */
 static int ldb_match_scope(struct ldb_context *ldb,
-			   const struct ldb_dn *base,
-			   const struct ldb_dn *dn,
+			   struct ldb_dn *base,
+			   struct ldb_dn *dn,
 			   enum ldb_scope scope)
 {
 	int ret = 0;
@@ -52,14 +52,14 @@ static int ldb_match_scope(struct ldb_context *ldb,
 
 	switch (scope) {
 	case LDB_SCOPE_BASE:
-		if (ldb_dn_compare(ldb, base, dn) == 0) {
+		if (ldb_dn_compare(base, dn) == 0) {
 			ret = 1;
 		}
 		break;
 
 	case LDB_SCOPE_ONELEVEL:
 		if (ldb_dn_get_comp_num(dn) == (ldb_dn_get_comp_num(base) + 1)) {
-			if (ldb_dn_compare_base(ldb, base, dn) == 0) {
+			if (ldb_dn_compare_base(base, dn) == 0) {
 				ret = 1;
 			}
 		}
@@ -67,7 +67,7 @@ static int ldb_match_scope(struct ldb_context *ldb,
 		
 	case LDB_SCOPE_SUBTREE:
 	default:
-		if (ldb_dn_compare_base(ldb, base, dn) == 0) {
+		if (ldb_dn_compare_base(base, dn) == 0) {
 			ret = 1;
 		}
 		break;
@@ -149,13 +149,12 @@ static int ldb_match_equality(struct ldb_context *ldb,
 	int ret;
 
 	if (ldb_attr_dn(tree->u.equality.attr) == 0) {
-		valuedn = ldb_dn_explode_casefold(ldb, ldb,
-						  (char *)tree->u.equality.value.data);
+		valuedn = ldb_dn_new(ldb, ldb, (char *)tree->u.equality.value.data);
 		if (valuedn == NULL) {
 			return 0;
 		}
 
-		ret = ldb_dn_compare(ldb, msg->dn, valuedn);
+		ret = ldb_dn_compare(msg->dn, valuedn);
 
 		talloc_free(valuedn);
 
@@ -420,7 +419,7 @@ static int ldb_match_message(struct ldb_context *ldb,
 int ldb_match_msg(struct ldb_context *ldb,
 		  const struct ldb_message *msg,
 		  const struct ldb_parse_tree *tree,
-		  const struct ldb_dn *base,
+		  struct ldb_dn *base,
 		  enum ldb_scope scope)
 {
 	if ( ! ldb_match_scope(ldb, base, msg->dn, scope) ) {
diff --git a/source4/lib/ldb/common/ldb_modules.c b/source4/lib/ldb/common/ldb_modules.c
index a6997b324a..28a619ddeb 100644
--- a/source4/lib/ldb/common/ldb_modules.c
+++ b/source4/lib/ldb/common/ldb_modules.c
@@ -327,7 +327,7 @@ int ldb_load_modules(struct ldb_context *ldb, const char *options[])
 		struct ldb_result *res = NULL;
 		struct ldb_dn *mods_dn;
 
-		mods_dn = ldb_dn_explode(mem_ctx, "@MODULES");
+		mods_dn = ldb_dn_new(mem_ctx, ldb, "@MODULES");
 		if (mods_dn == NULL) {
 			talloc_free(mem_ctx);
 			return -1;
diff --git a/source4/lib/ldb/common/ldb_msg.c b/source4/lib/ldb/common/ldb_msg.c
index 65d1ecacb7..2768786b83 100644
--- a/source4/lib/ldb/common/ldb_msg.c
+++ b/source4/lib/ldb/common/ldb_msg.c
@@ -126,6 +126,7 @@ int ldb_msg_add_empty(	struct ldb_message *msg,
 {
 	struct ldb_message_element *els;
 
+	/* FIXME: we should probably leave this to the schema module to check */
 	if (! ldb_valid_attr_name(attr_name)) {
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
@@ -411,17 +412,24 @@ const char *ldb_msg_find_attr_as_string(const struct ldb_message *msg,
 	return (const char *)v->data;
 }
 
-struct ldb_dn *ldb_msg_find_attr_as_dn(void *mem_ctx,
+struct ldb_dn *ldb_msg_find_attr_as_dn(struct ldb_context *ldb,
+				       void *mem_ctx,
 				       const struct ldb_message *msg,
 				       const char *attr_name)
 {
+	struct ldb_dn *res_dn;
 	const struct ldb_val *v;
 
 	v = ldb_msg_find_ldb_val(msg, attr_name);
 	if (!v || !v->data) {
 		return NULL;
 	}
-	return ldb_dn_explode(mem_ctx, (const char *)v->data);
+	res_dn = ldb_dn_new(mem_ctx, ldb, (const char *)v->data);
+	if ( ! ldb_dn_validate(res_dn)) {
+		talloc_free(res_dn);
+		return NULL;
+	}
+	return res_dn;
 }
 
 /*
diff --git a/source4/lib/ldb/include/ldb.h b/source4/lib/ldb/include/ldb.h
index 17a2ec7556..46894cd3c0 100644
--- a/source4/lib/ldb/include/ldb.h
+++ b/source4/lib/ldb/include/ldb.h
@@ -698,7 +698,7 @@ struct ldb_handle {
 };
 
 struct ldb_search {
-	const struct ldb_dn *base;
+	struct ldb_dn *base;
 	enum ldb_scope scope;
 	const struct ldb_parse_tree *tree;
 	const char * const *attrs;
@@ -714,12 +714,12 @@ struct  ldb_modify {
 };
 
 struct ldb_delete {
-	const struct ldb_dn *dn;
+	struct ldb_dn *dn;
 };
 
 struct ldb_rename {
-	const struct ldb_dn *olddn;
-	const struct ldb_dn *newdn;
+	struct ldb_dn *olddn;
+	struct ldb_dn *newdn;
 };
 
 struct ldb_register_control {
@@ -727,7 +727,7 @@ struct ldb_register_control {
 };
 
 struct ldb_register_partition {
-	const struct ldb_dn *dn;
+	struct ldb_dn *dn;
 };
 
 struct ldb_sequence_number {
@@ -825,7 +825,7 @@ int ldb_connect(struct ldb_context *ldb, const char *url, unsigned int flags, co
   return an automatic baseDN from the defaultNamingContext of the rootDSE
   This value have been set in an opaque pointer at connection time
 */
-const struct ldb_dn *ldb_get_default_basedn(struct ldb_context *ldb);
+struct ldb_dn *ldb_get_default_basedn(struct ldb_context *ldb);
 
 
 /**
@@ -868,7 +868,7 @@ int ldb_search_default_callback(struct ldb_context *ldb, void *context, struct l
 int ldb_build_search_req(struct ldb_request **ret_req,
 			struct ldb_context *ldb,
 			void *mem_ctx,
-			const struct ldb_dn *base,
+			struct ldb_dn *base,
 	       		enum ldb_scope scope,
 			const char *expression,
 			const char * const *attrs,
@@ -937,7 +937,7 @@ int ldb_build_mod_req(struct ldb_request **ret_req,
 int ldb_build_del_req(struct ldb_request **ret_req,
 			struct ldb_context *ldb,
 			void *mem_ctx,
-			const struct ldb_dn *dn,
+			struct ldb_dn *dn,
 			struct ldb_control **controls,
 			void *context,
 			ldb_request_callback_t callback);
@@ -960,8 +960,8 @@ int ldb_build_del_req(struct ldb_request **ret_req,
 int ldb_build_rename_req(struct ldb_request **ret_req,
 			struct ldb_context *ldb,
 			void *mem_ctx,
-			const struct ldb_dn *olddn,
-			const struct ldb_dn *newdn,
+			struct ldb_dn *olddn,
+			struct ldb_dn *newdn,
 			struct ldb_control **controls,
 			void *context,
 			ldb_request_callback_t callback);
@@ -984,7 +984,7 @@ int ldb_build_rename_req(struct ldb_request **ret_req,
   \note use talloc_free() to free the ldb_result returned
 */
 int ldb_search(struct ldb_context *ldb, 
-	       const struct ldb_dn *base,
+	       struct ldb_dn *base,
 	       enum ldb_scope scope,
 	       const char *expression,
 	       const char * const *attrs, struct ldb_result **res);
@@ -993,7 +993,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 struct ldb_dn *base,
+		      struct ldb_dn *base,
 		      enum ldb_scope scope,
 		      struct ldb_parse_tree *tree,
 		      const char * const *attrs, struct ldb_result **res);
@@ -1043,7 +1043,7 @@ int ldb_modify(struct ldb_context *ldb,
   \return result code (LDB_SUCCESS if the record was renamed as
   requested, otherwise a failure code)
 */
-int ldb_rename(struct ldb_context *ldb, const struct ldb_dn *olddn, const struct ldb_dn *newdn);
+int ldb_rename(struct ldb_context *ldb, struct ldb_dn *olddn, struct ldb_dn *newdn);
 
 /**
   Delete a record from the database
@@ -1057,7 +1057,7 @@ int ldb_rename(struct ldb_context *ldb, const struct ldb_dn *olddn, const struct
   \return result code (LDB_SUCCESS if the record was deleted,
   otherwise a failure code)
 */
-int ldb_delete(struct ldb_context *ldb, const struct ldb_dn *dn);
+int ldb_delete(struct ldb_context *ldb, struct ldb_dn *dn);
 
 /**
   start a transaction
@@ -1269,38 +1269,41 @@ int ldb_attrib_add_handlers(struct ldb_context *ldb,
 
 /* The following definitions come from lib/ldb/common/ldb_dn.c  */
 
-int ldb_dn_is_special(const struct ldb_dn *dn);
-int ldb_dn_check_special(const struct ldb_dn *dn, const char *check);
+struct ldb_dn *ldb_dn_new(void *mem_ctx, struct ldb_context *ldb, const char *dn);
+struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx, struct ldb_context *ldb, const char *new_fmt, ...);
+bool ldb_dn_validate(struct ldb_dn *dn);
+
 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);
-struct ldb_dn *ldb_dn_explode_or_special(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, 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, void *mem_ctx, const struct ldb_dn *edn);
-struct ldb_dn *ldb_dn_explode_casefold(struct ldb_context *ldb, void *mem_ctx, 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_copy_rebase(void *mem_ctx, const struct ldb_dn *old, const struct ldb_dn *old_base, const struct ldb_dn *new_base);
-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_compose(void *mem_ctx, const struct ldb_dn *dn1, const struct ldb_dn *dn2);
-struct ldb_dn *ldb_dn_string_compose(void *mem_ctx, const struct ldb_dn *base, const char *child_fmt, ...) PRINTF_ATTRIBUTE(3,4);
-char *ldb_dn_canonical_string(void *mem_ctx, const struct ldb_dn *dn);
-char *ldb_dn_canonical_ex_string(void *mem_ctx, const struct ldb_dn *dn);
-int ldb_dn_get_comp_num(const struct ldb_dn *dn);
-const char *ldb_dn_get_component_name(const struct ldb_dn *dn, unsigned int num);
-const struct ldb_val *ldb_dn_get_component_val(const struct ldb_dn *dn, unsigned int num);
-const char *ldb_dn_get_rdn_name(const struct ldb_dn *dn);
-const struct ldb_val *ldb_dn_get_rdn_val(const struct ldb_dn *dn);
+char *ldb_dn_linearize(void *mem_ctx, struct ldb_dn *dn);
+char *ldb_dn_casefold(void *mem_ctx, struct ldb_dn *dn);
+const char *ldb_dn_get_linearized(struct ldb_dn *dn);
+const char *ldb_dn_get_casefold(struct ldb_dn *dn);
+
+int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn);
+int ldb_dn_compare(struct ldb_dn *edn0, struct ldb_dn *edn1);
+
+bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base);
+bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...);
+bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child);
+bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...);
+bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num);
+bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num);
+
+struct ldb_dn *ldb_dn_copy(void *mem_ctx, struct ldb_dn *dn);
+struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, struct ldb_dn *dn);
+char *ldb_dn_canonical_string(void *mem_ctx, struct ldb_dn *dn);
+char *ldb_dn_canonical_ex_string(void *mem_ctx, struct ldb_dn *dn);
+int ldb_dn_get_comp_num(struct ldb_dn *dn);
+const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num);
+const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn, unsigned int num);
+const char *ldb_dn_get_rdn_name(struct ldb_dn *dn);
+const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn);
 int ldb_dn_set_component(struct ldb_dn *dn, int num, const char *name, const struct ldb_val val);
 
+bool ldb_dn_is_valid(struct ldb_dn *dn);
+bool ldb_dn_is_special(struct ldb_dn *dn);
+bool ldb_dn_check_special(struct ldb_dn *dn, const char *check);
+bool ldb_dn_is_null(struct ldb_dn *dn);
 
 
 /* useful functions for ldb_message structure manipulation */
@@ -1422,9 +1425,10 @@ const char *ldb_msg_find_attr_as_string(const struct ldb_message *msg,
 					const char *attr_name,
 					const char *default_value);
 
-struct ldb_dn *ldb_msg_find_attr_as_dn(void *mem_ctx,
+struct ldb_dn *ldb_msg_find_attr_as_dn(struct ldb_context *ldb,
+				       void *mem_ctx,
 				       const struct ldb_message *msg,
-				        const char *attr_name);
+				       const char *attr_name);
 
 void ldb_msg_sort_elements(struct ldb_message *msg);
 
diff --git a/source4/lib/ldb/include/ldb_private.h b/source4/lib/ldb/include/ldb_private.h
index f4049188ad..d597f30232 100644
--- a/source4/lib/ldb/include/ldb_private.h
+++ b/source4/lib/ldb/include/ldb_private.h
@@ -180,7 +180,7 @@ int ldb_sqlite3_init(void);
 int ldb_match_msg(struct ldb_context *ldb,
 		  const struct ldb_message *msg,
 		  const struct ldb_parse_tree *tree,
-		  const struct ldb_dn *base,
+		  struct ldb_dn *base,
 		  enum ldb_scope scope);
 
 void ldb_remove_attrib_handler(struct ldb_context *ldb, const char *attrib);
diff --git a/source4/lib/ldb/ldb_ildap/ldb_ildap.c b/source4/lib/ldb/ldb_ildap/ldb_ildap.c
index 51ae031cf9..a4abd4d151 100644
--- a/source4/lib/ldb/ldb_ildap/ldb_ildap.c
+++ b/source4/lib/ldb/ldb_ildap/ldb_ildap.c
@@ -273,8 +273,8 @@ static void ildb_callback(struct ldap_request *req)
 
 				search = &(msg->r.SearchResultEntry);
 		
-				ares->message->dn = ldb_dn_explode_or_special(ares->message, search->dn);
-				if (ares->message->dn == NULL) {
+				ares->message->dn = ldb_dn_new(ares->message, ac->module->ldb, search->dn);
+				if ( ! ldb_dn_validate(ares->message->dn)) {
 					handle->status = LDB_ERR_OPERATIONS_ERROR;
 					return;
 				}
diff --git a/source4/lib/ldb/ldb_ldap/ldb_ldap.c b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
index cdc1a500f8..ee2d818935 100644
--- a/source4/lib/ldb/ldb_ldap/ldb_ldap.c
+++ b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
@@ -527,8 +527,8 @@ static int lldb_parse_result(struct ldb_handle *handle, LDAPMessage *result)
 				ret = LDB_ERR_OPERATIONS_ERROR;
 				goto error;
 			}
-			ares->message->dn = ldb_dn_explode_or_special(ares->message, dn);
-			if (ares->message->dn == NULL) {
+			ares->message->dn = ldb_dn_new(ares->message, ac->module->ldb, dn);
+			if ( ! ldb_dn_validate(ares->message->dn)) {
 				ret = LDB_ERR_OPERATIONS_ERROR;
 				goto error;
 			}
diff --git a/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c b/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c
index 4f9b0f6370..7671b0d954 100644
--- a/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c
+++ b/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c
@@ -369,9 +369,8 @@ static char *parsetree_to_sql(struct ldb_module *module,
 
 		} else if (strcasecmp(t->u.equality.attr, "dn") == 0) {
 			/* DN query is a special ldb case */
-		 	char *cdn = ldb_dn_linearize_casefold(module->ldb,
-							      mem_ctx,
-							      ldb_dn_explode(module->ldb,
+		 	char *cdn = ldb_dn_casefold(mem_ctx,
+							ldb_dn_new(mem_ctx, module->ldb,
 							      (const char *)value.data));
 
 			return lsqlite3_tprintf(mem_ctx,
@@ -754,7 +753,7 @@ static int lsqlite3_search_callback(void *result, int col_num, char **cols, char
 	msg = ac->ares->message;
 
 	if (msg->dn == NULL) {
-		msg->dn = ldb_dn_explode(msg, cols[1]);
+		msg->dn = ldb_dn_new(msg, ac->module->ldb, cols[1]);
 		if (msg->dn == NULL)
 			return SQLITE_ABORT;
 	}
@@ -811,7 +810,7 @@ static long long lsqlite3_get_eid_ndn(sqlite3 *sqlite, void *mem_ctx, const char
 	return eid;
 }
 
-static long long lsqlite3_get_eid(struct ldb_module *module, const struct ldb_dn *dn)
+static long long lsqlite3_get_eid(struct ldb_module *module, struct ldb_dn *dn)
 {
 	TALLOC_CTX *local_ctx;
 	struct lsqlite3_private *lsqlite3 = module->private_data;
@@ -1044,7 +1043,7 @@ static int lsql_add(struct ldb_module *module, struct ldb_request *req)
 	if (ldb_dn_is_special(msg->dn)) {
 		struct ldb_dn *c;
 
-		c = ldb_dn_explode(lsql_ac, "@SUBCLASSES");
+		c = ldb_dn_new(lsql_ac, module->ldb, "@SUBCLASSES");
 		if (ldb_dn_compare(module->ldb, msg->dn, c) == 0) {
 #warning "insert subclasses into object class tree"
 			ret = LDB_ERR_UNWILLING_TO_PERFORM;
@@ -1052,7 +1051,7 @@ static int lsql_add(struct ldb_module *module, struct ldb_request *req)
 		}
 
 /*
-		c = ldb_dn_explode(local_ctx, "@INDEXLIST");
+		c = ldb_dn_new(local_ctx, module->ldb, "@INDEXLIST");
 		if (ldb_dn_compare(module->ldb, msg->dn, c) == 0) {
 #warning "should we handle indexes somehow ?"
 			ret = LDB_ERR_UNWILLING_TO_PERFORM;
@@ -1182,7 +1181,7 @@ static int lsql_modify(struct ldb_module *module, struct ldb_request *req)
 	if (ldb_dn_is_special(msg->dn)) {
 		struct ldb_dn *c;
 
-		c = ldb_dn_explode(lsql_ac, "@SUBCLASSES");
+		c = ldb_dn_new(lsql_ac, module->ldb, "@SUBCLASSES");
 		if (ldb_dn_compare(module->ldb, msg->dn, c) == 0) {
 #warning "modify subclasses into object class tree"
 			ret = LDB_ERR_UNWILLING_TO_PERFORM;
diff --git a/source4/lib/ldb/ldb_tdb/ldb_cache.c b/source4/lib/ldb/ldb_tdb/ldb_cache.c
index 467f1ac34d..756c198106 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_cache.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_cache.c
@@ -112,7 +112,7 @@ static int ltdb_attributes_load(struct ldb_module *module)
 	struct ldb_dn *dn;
 	int i;
 
-	dn = ldb_dn_explode(module->ldb, LTDB_ATTRIBUTES);
+	dn = ldb_dn_new(module, module->ldb, LTDB_ATTRIBUTES);
 	if (dn == NULL) goto failed;
 
 	if (ltdb_search_dn1(module, dn, msg) == -1) {
@@ -180,7 +180,7 @@ static int ltdb_subclasses_load(struct ldb_module *module)
 	struct ldb_dn *dn;
 	int i, j;
 
-	dn = ldb_dn_explode(module->ldb, LTDB_SUBCLASSES);
+	dn = ldb_dn_new(module, module->ldb, LTDB_SUBCLASSES);
 	if (dn == NULL) goto failed;
 
 	if (ltdb_search_dn1(module, dn, msg) == -1) {
@@ -253,7 +253,7 @@ static int ltdb_baseinfo_init(struct ldb_module *module)
 
 	msg->num_elements = 1;
 	msg->elements = &el;
-	msg->dn = ldb_dn_explode(msg, LTDB_BASEINFO);
+	msg->dn = ldb_dn_new(msg, module->ldb, LTDB_BASEINFO);
 	if (!msg->dn) {
 		goto failed;
 	}
@@ -338,7 +338,7 @@ int ltdb_cache_load(struct ldb_module *module)
 	baseinfo = talloc(ltdb->cache, struct ldb_message);
 	if (baseinfo == NULL) goto failed;
 
-	baseinfo_dn = ldb_dn_explode(module->ldb, LTDB_BASEINFO);
+	baseinfo_dn = ldb_dn_new(module, module->ldb, LTDB_BASEINFO);
 	if (baseinfo_dn == NULL) goto failed;
 
 	if (ltdb_search_dn1(module, baseinfo_dn, baseinfo) == -1) {
@@ -383,7 +383,7 @@ int ltdb_cache_load(struct ldb_module *module)
 		goto failed;
 	}
 	    
-	indexlist_dn = ldb_dn_explode(module->ldb, LTDB_INDEXLIST);
+	indexlist_dn = ldb_dn_new(module, module->ldb, LTDB_INDEXLIST);
 	if (indexlist_dn == NULL) goto failed;
 
 	if (ltdb_search_dn1(module, indexlist_dn, ltdb->cache->indexlist) == -1) {
@@ -439,7 +439,7 @@ int ltdb_increase_sequence_number(struct ldb_module *module)
 
 	msg->num_elements = ARRAY_SIZE(el);
 	msg->elements = el;
-	msg->dn = ldb_dn_explode(msg, LTDB_BASEINFO);
+	msg->dn = ldb_dn_new(msg, module->ldb, LTDB_BASEINFO);
 	if (msg->dn == NULL) {
 		talloc_free(msg);
 		errno = ENOMEM;
diff --git a/source4/lib/ldb/ldb_tdb/ldb_index.c b/source4/lib/ldb/ldb_tdb/ldb_index.c
index 0c9d1f33a1..874d047186 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_index.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_index.c
@@ -147,7 +147,7 @@ static struct ldb_dn *ldb_dn_key(struct ldb_context *ldb,
 	talloc_free(attr_folded);
 
 done:
-	ret = ldb_dn_explode(ldb, dn);
+	ret = ldb_dn_new(ldb, ldb, dn);
 	talloc_free(dn);
 	return ret;
 }
@@ -662,7 +662,7 @@ static int ltdb_index_filter(const struct dn_list *dn_list,
 		}
 
 
-		dn = ldb_dn_explode(ares->message, dn_list->dn[i]);
+		dn = ldb_dn_new(ares->message, ac->module->ldb, dn_list->dn[i]);
 		if (dn == NULL) {
 			talloc_free(ares);
 			return LDB_ERR_OPERATIONS_ERROR;
diff --git a/source4/lib/ldb/ldb_tdb/ldb_pack.c b/source4/lib/ldb/ldb_tdb/ldb_pack.c
index c6edf663ae..258c54356c 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_pack.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_pack.c
@@ -196,7 +196,7 @@ int ltdb_unpack_data(struct ldb_module *module,
 			errno = EIO;
 			goto failed;
 		}
-		message->dn = ldb_dn_explode(message, (char *)p);
+		message->dn = ldb_dn_new(message, ldb, (char *)p);
 		if (message->dn == NULL) {
 			errno = ENOMEM;
 			goto failed;
diff --git a/source4/lib/ldb/ldb_tdb/ldb_search.c b/source4/lib/ldb/ldb_tdb/ldb_search.c
index 884eccd362..3f04994ce4 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_search.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_search.c
@@ -209,7 +209,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 struct ldb_dn *dn, struct ldb_message *msg)
+int ltdb_search_dn1(struct ldb_module *module, struct ldb_dn *dn, struct ldb_message *msg)
 {
 	struct ltdb_private *ltdb = module->private_data;
 	int ret;
@@ -394,7 +394,7 @@ static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, voi
 	}
 
 	if (!ares->message->dn) {
-		ares->message->dn = ldb_dn_explode(ares->message, (char *)key.dptr + 3);
+		ares->message->dn = ldb_dn_new(ares->message, ac->module->ldb, (char *)key.dptr + 3);
 		if (ares->message->dn == NULL) {
 			handle->status = LDB_ERR_OPERATIONS_ERROR;
 			handle->state = LDB_ASYNC_DONE;
@@ -464,7 +464,7 @@ int ltdb_search(struct ldb_module *module, struct ldb_request *req)
 	struct ldb_reply *ares;
 	int ret;
 
-	if ((req->op.search.base == NULL || ldb_dn_get_comp_num(req->op.search.base) == 0) &&
+	if ((( ! ldb_dn_is_valid(req->op.search.base)) || ldb_dn_is_null(req->op.search.base)) &&
 	    (req->op.search.scope == LDB_SCOPE_BASE || req->op.search.scope == LDB_SCOPE_ONELEVEL))
 		return LDB_ERR_OPERATIONS_ERROR;
 
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.c b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
index 3f9db39097..d950ab9cf0 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_tdb.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
@@ -118,7 +118,7 @@ struct ldb_handle *init_ltdb_handle(struct ltdb_private *ltdb, struct ldb_module
   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 struct ldb_dn *dn)
+struct TDB_DATA ltdb_key(struct ldb_module *module, struct ldb_dn *dn)
 {
 	struct ldb_context *ldb = module->ldb;
 	TDB_DATA key;
@@ -137,15 +137,13 @@ struct TDB_DATA ltdb_key(struct ldb_module *module, const struct ldb_dn *dn)
 	     the rest
 	*/
 
-	dn_folded = ldb_dn_linearize_casefold(ldb, ldb, dn);
+	dn_folded = ldb_dn_get_casefold(dn);
 	if (!dn_folded) {
 		goto failed;
 	}
 
 	key_str = talloc_asprintf(ldb, "DN=%s", dn_folded);
 
-	talloc_free(dn_folded);
-
 	if (!key_str) {
 		goto failed;
 	}
@@ -194,7 +192,7 @@ 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 struct ldb_dn *dn)
+static int ltdb_modified(struct ldb_module *module, struct ldb_dn *dn)
 {
 	int ret = 0;
 
@@ -330,7 +328,7 @@ done:
   delete a record from the database, not updating indexes (used for deleting
   index records)
 */
-int ltdb_delete_noindex(struct ldb_module *module, const struct ldb_dn *dn)
+int ltdb_delete_noindex(struct ldb_module *module, struct ldb_dn *dn)
 {
 	struct ltdb_private *ltdb =
 		talloc_get_type(module->private_data, struct ltdb_private);
@@ -352,7 +350,7 @@ int ltdb_delete_noindex(struct ldb_module *module, const struct ldb_dn *dn)
 	return ret;
 }
 
-static int ltdb_delete_internal(struct ldb_module *module, const struct ldb_dn *dn)
+static int ltdb_delete_internal(struct ldb_module *module, struct ldb_dn *dn)
 {
 	struct ldb_message *msg;
 	int ret;
@@ -936,7 +934,7 @@ static int ltdb_sequence_number(struct ldb_module *module, struct ldb_request *r
 {
 	TALLOC_CTX *tmp_ctx = talloc_new(req);
 	struct ldb_message *msg = NULL;
-	struct ldb_dn *dn = ldb_dn_explode(tmp_ctx, LTDB_BASEINFO);
+	struct ldb_dn *dn = ldb_dn_new(tmp_ctx, module->ldb, LTDB_BASEINFO);
 	int tret;
 
 	if (tmp_ctx == NULL) {
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.h b/source4/lib/ldb/ldb_tdb/ldb_tdb.h
index 42f3dc2421..6b556153ad 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_tdb.h
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.h
@@ -46,7 +46,7 @@ struct ltdb_context {
 
 	/* search stuff */
 	const struct ldb_parse_tree *tree;
-	const struct ldb_dn *base;
+	struct ldb_dn *base;
 	enum ldb_scope scope;
 	const char * const *attrs;
 
@@ -101,7 +101,7 @@ 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 struct ldb_dn *dn, struct ldb_message *msg);
+int ltdb_search_dn1(struct ldb_module *module, struct ldb_dn *dn, struct ldb_message *msg);
 int ltdb_add_attr_results(struct ldb_module *module,
  			  TALLOC_CTX *mem_ctx, 
 			  struct ldb_message *msg,
@@ -114,9 +114,9 @@ int ltdb_search(struct ldb_module *module, struct ldb_request *req);
 /* The following definitions come from lib/ldb/ldb_tdb/ldb_tdb.c  */
 struct ldb_handle *init_ltdb_handle(struct ltdb_private *ltdb, struct ldb_module *module,
 				    struct ldb_request *req);
-struct TDB_DATA ltdb_key(struct ldb_module *module, const struct ldb_dn *dn);
+struct TDB_DATA ltdb_key(struct ldb_module *module, 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 struct ldb_dn *dn);
+int ltdb_delete_noindex(struct ldb_module *module, struct ldb_dn *dn);
 int ltdb_modify_internal(struct ldb_module *module, const struct ldb_message *msg);
 
 int ltdb_index_del_value(struct ldb_module *module, const char *dn, 
diff --git a/source4/lib/ldb/modules/asq.c b/source4/lib/ldb/modules/asq.c
index 2fed6aac50..7d10a31b34 100644
--- a/source4/lib/ldb/modules/asq.c
+++ b/source4/lib/ldb/modules/asq.c
@@ -313,8 +313,8 @@ static int asq_requests(struct ldb_handle *handle) {
 		if (ac->reqs[i] == NULL)
 			return LDB_ERR_OPERATIONS_ERROR;
 		ac->reqs[i]->operation = LDB_SEARCH;
-		ac->reqs[i]->op.search.base = ldb_dn_explode(ac->reqs[i], (const char *)el->values[i].data);
-		if (ac->reqs[i]->op.search.base == NULL) {
+		ac->reqs[i]->op.search.base = ldb_dn_new(ac->reqs[i], ac->module->ldb, (const char *)el->values[i].data);
+		if ( ! ldb_dn_validate(ac->reqs[i]->op.search.base)) {
 			ac->asq_ret = ASQ_CTRL_INVALID_ATTRIBUTE_SYNTAX;
 			return asq_terminate(handle);
 		}
diff --git a/source4/lib/ldb/modules/ldb_map.c b/source4/lib/ldb/modules/ldb_map.c
index bbd7b9603d..05a0459b4a 100644
--- a/source4/lib/ldb/modules/ldb_map.c
+++ b/source4/lib/ldb/modules/ldb_map.c
@@ -182,15 +182,61 @@ BOOL map_check_local_db(struct ldb_module *module)
 }
 
 /* Copy a DN with the base DN of the local partition. */
-static struct ldb_dn *ldb_dn_rebase_local(void *mem_ctx, const struct ldb_map_context *data, const struct ldb_dn *dn)
+static struct ldb_dn *ldb_dn_rebase_local(void *mem_ctx, const struct ldb_map_context *data, struct ldb_dn *dn)
 {
-	return ldb_dn_copy_rebase(mem_ctx, dn, data->remote_base_dn, data->local_base_dn);
+	struct ldb_dn *new_dn;
+
+	new_dn = ldb_dn_copy(mem_ctx, dn);
+	if ( ! ldb_dn_validate(new_dn)) {
+		talloc_free(new_dn);
+		return NULL;
+	}
+
+	/* may be we don't need to rebase at all */
+	if ( ! data->remote_base_dn || ! data->local_base_dn) {
+		return new_dn;
+	}
+
+	if ( ! ldb_dn_remove_base_components(new_dn, ldb_dn_get_comp_num(data->remote_base_dn))) {
+		talloc_free(new_dn);
+		return NULL;
+	}
+
+	if ( ! ldb_dn_add_base(new_dn, data->local_base_dn)) {
+		talloc_free(new_dn);
+		return NULL;
+	}
+
+	return new_dn;
 }
 
 /* Copy a DN with the base DN of the remote partition. */
-static struct ldb_dn *ldb_dn_rebase_remote(void *mem_ctx, const struct ldb_map_context *data, const struct ldb_dn *dn)
+static struct ldb_dn *ldb_dn_rebase_remote(void *mem_ctx, const struct ldb_map_context *data, struct ldb_dn *dn)
 {
-	return ldb_dn_copy_rebase(mem_ctx, dn, data->local_base_dn, data->remote_base_dn);
+	struct ldb_dn *new_dn;
+
+	new_dn = ldb_dn_copy(mem_ctx, dn);
+	if ( ! ldb_dn_validate(new_dn)) {
+		talloc_free(new_dn);
+		return NULL;
+	}
+
+	/* may be we don't need to rebase at all */
+	if ( ! data->remote_base_dn || ! data->local_base_dn) {
+		return new_dn;
+	}
+
+	if ( ! ldb_dn_remove_base_components(new_dn, ldb_dn_get_comp_num(data->local_base_dn))) {
+		talloc_free(new_dn);
+		return NULL;
+	}
+
+	if ( ! ldb_dn_add_base(new_dn, data->remote_base_dn)) {
+		talloc_free(new_dn);
+		return NULL;
+	}
+
+	return new_dn;
 }
 
 /* Run a request and make sure it targets the remote partition. */
@@ -443,7 +489,7 @@ struct ldb_val ldb_val_map_remote(struct ldb_module *module, void *mem_ctx,
  * =========== */
 
 /* Check whether a DN is below the local baseDN. */
-BOOL ldb_dn_check_local(struct ldb_module *module, const struct ldb_dn *dn)
+BOOL ldb_dn_check_local(struct ldb_module *module, struct ldb_dn *dn)
 {
 	const struct ldb_map_context *data = map_get_context(module);
 
@@ -451,11 +497,11 @@ BOOL ldb_dn_check_local(struct ldb_module *module, const struct ldb_dn *dn)
 		return True;
 	}
 
-	return ldb_dn_compare_base(module->ldb, data->local_base_dn, dn) == 0;
+	return ldb_dn_compare_base(data->local_base_dn, dn) == 0;
 }
 
 /* Map a DN into the remote partition. */
-struct ldb_dn *ldb_dn_map_local(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn)
+struct ldb_dn *ldb_dn_map_local(struct ldb_module *module, void *mem_ctx, struct ldb_dn *dn)
 {
 	const struct ldb_map_context *data = map_get_context(module);
 	struct ldb_dn *newdn;
@@ -527,7 +573,7 @@ failed:
 }
 
 /* Map a DN into the local partition. */
-struct ldb_dn *ldb_dn_map_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn)
+struct ldb_dn *ldb_dn_map_remote(struct ldb_module *module, void *mem_ctx, struct ldb_dn *dn)
 {
 	const struct ldb_map_context *data = map_get_context(module);
 	struct ldb_dn *newdn;
@@ -600,7 +646,7 @@ failed:
 
 /* Map a DN and its base into the local partition. */
 /* TODO: This should not be required with GUIDs. */
-struct ldb_dn *ldb_dn_map_rebase_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn)
+struct ldb_dn *ldb_dn_map_rebase_remote(struct ldb_module *module, void *mem_ctx, struct ldb_dn *dn)
 {
 	const struct ldb_map_context *data = map_get_context(module);
 	struct ldb_dn *dn1, *dn2;
@@ -622,7 +668,13 @@ static struct ldb_val ldb_dn_convert_local(struct ldb_module *module, void *mem_
 	struct ldb_dn *dn, *newdn;
 	struct ldb_val newval;
 
-	dn = ldb_dn_explode(mem_ctx, (char *)val->data);
+	dn = ldb_dn_new(mem_ctx, module->ldb, (char *)val->data);
+	if (! ldb_dn_validate(dn)) {
+		newval.length = 0;
+		newval.data = NULL;
+		talloc_free(dn);
+		return newval;
+	}
 	newdn = ldb_dn_map_local(module, mem_ctx, dn);
 	talloc_free(dn);
 
@@ -642,7 +694,13 @@ static struct ldb_val ldb_dn_convert_remote(struct ldb_module *module, void *mem
 	struct ldb_dn *dn, *newdn;
 	struct ldb_val newval;
 
-	dn = ldb_dn_explode(mem_ctx, (char *)val->data);
+	dn = ldb_dn_new(mem_ctx, module->ldb, (char *)val->data);
+	if (! ldb_dn_validate(dn)) {
+		newval.length = 0;
+		newval.data = NULL;
+		talloc_free(dn);
+		return newval;
+	}
 	newdn = ldb_dn_map_remote(module, mem_ctx, dn);
 	talloc_free(dn);
 
@@ -856,7 +914,7 @@ static int map_search_self_callback(struct ldb_context *ldb, void *context, stru
 }
 
 /* Build a request to search a record by its DN. */
-struct ldb_request *map_search_base_req(struct map_context *ac, const struct ldb_dn *dn, const char * const *attrs, const struct ldb_parse_tree *tree, void *context, ldb_search_callback callback)
+struct ldb_request *map_search_base_req(struct map_context *ac, struct ldb_dn *dn, const char * const *attrs, const struct ldb_parse_tree *tree, void *context, ldb_search_callback callback)
 {
 	struct ldb_request *req;
 
@@ -890,7 +948,7 @@ struct ldb_request *map_search_base_req(struct map_context *ac, const struct ldb
 }
 
 /* Build a request to search the local record by its DN. */
-struct ldb_request *map_search_self_req(struct map_context *ac, const struct ldb_dn *dn)
+struct ldb_request *map_search_self_req(struct map_context *ac, struct ldb_dn *dn)
 {
 	/* attrs[] is returned from this function in
 	 * ac->search_req->op.search.attrs, so it must be static, as
@@ -913,7 +971,7 @@ struct ldb_request *map_search_self_req(struct map_context *ac, const struct ldb
 }
 
 /* Build a request to update the 'IS_MAPPED' attribute */
-struct ldb_request *map_build_fixup_req(struct map_context *ac, const struct ldb_dn *olddn, const struct ldb_dn *newdn)
+struct ldb_request *map_build_fixup_req(struct map_context *ac, struct ldb_dn *olddn, struct ldb_dn *newdn)
 {
 	struct ldb_request *req;
 	struct ldb_message *msg;
@@ -1193,8 +1251,8 @@ static int map_init_dns(struct ldb_module *module, struct ldb_map_context *data,
 		return LDB_SUCCESS;
 	}
 
-	dn = ldb_dn_string_compose(data, NULL, "%s=%s", MAP_DN_NAME, name);
-	if (dn == NULL) {
+	dn = ldb_dn_new_fmt(data, module->ldb, "%s=%s", MAP_DN_NAME, name);
+	if ( ! ldb_dn_validate(dn)) {
 		ldb_debug(module->ldb, LDB_DEBUG_ERROR, "ldb_map: "
 			  "Failed to construct '%s' DN!\n", MAP_DN_NAME);
 		return LDB_ERR_OPERATIONS_ERROR;
@@ -1219,8 +1277,8 @@ static int map_init_dns(struct ldb_module *module, struct ldb_map_context *data,
 	}
 
 	msg = res->msgs[0];
-	data->local_base_dn = ldb_msg_find_attr_as_dn(data, msg, MAP_DN_FROM);
-	data->remote_base_dn = ldb_msg_find_attr_as_dn(data, msg, MAP_DN_TO);
+	data->local_base_dn = ldb_msg_find_attr_as_dn(module->ldb, data, msg, MAP_DN_FROM);
+	data->remote_base_dn = ldb_msg_find_attr_as_dn(module->ldb, data, msg, MAP_DN_TO);
 	talloc_free(res);
 
 	return LDB_SUCCESS;
diff --git a/source4/lib/ldb/modules/ldb_map.h b/source4/lib/ldb/modules/ldb_map.h
index c5c455bcb2..e8de2e3698 100644
--- a/source4/lib/ldb/modules/ldb_map.h
+++ b/source4/lib/ldb/modules/ldb_map.h
@@ -135,8 +135,8 @@ struct ldb_map_context {
 	const char * const *wildcard_attributes;
 
 	/* struct ldb_context *mapped_ldb; */
-	const struct ldb_dn *local_base_dn;
-	const struct ldb_dn *remote_base_dn;
+	struct ldb_dn *local_base_dn;
+	struct ldb_dn *remote_base_dn;
 };
 
 /* Global private data */
diff --git a/source4/lib/ldb/modules/ldb_map_private.h b/source4/lib/ldb/modules/ldb_map_private.h
index 8a08d0a5b6..1f4fecee8b 100644
--- a/source4/lib/ldb/modules/ldb_map_private.h
+++ b/source4/lib/ldb/modules/ldb_map_private.h
@@ -33,7 +33,7 @@ struct map_context {
 
 	struct ldb_module *module;
 
-	const struct ldb_dn *local_dn;
+	struct ldb_dn *local_dn;
 	const struct ldb_parse_tree *local_tree;
 	const char * const *local_attrs;
 	const char * const *remote_attrs;
@@ -70,7 +70,7 @@ int ldb_next_remote_request(struct ldb_module *module, struct ldb_request *reque
 
 BOOL map_check_local_db(struct ldb_module *module);
 BOOL map_attr_check_remote(const struct ldb_map_context *data, const char *attr);
-BOOL ldb_dn_check_local(struct ldb_module *module, const struct ldb_dn *dn);
+BOOL ldb_dn_check_local(struct ldb_module *module, struct ldb_dn *dn);
 
 const struct ldb_map_attribute *map_attr_find_local(const struct ldb_map_context *data, const char *name);
 const struct ldb_map_attribute *map_attr_find_remote(const struct ldb_map_context *data, const char *name);
@@ -82,13 +82,13 @@ int map_attrs_merge(struct ldb_module *module, void *mem_ctx, const char ***attr
 struct ldb_val ldb_val_map_local(struct ldb_module *module, void *mem_ctx, const struct ldb_map_attribute *map, const struct ldb_val *val);
 struct ldb_val ldb_val_map_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_map_attribute *map, const struct ldb_val *val);
 
-struct ldb_dn *ldb_dn_map_local(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn);
-struct ldb_dn *ldb_dn_map_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn);
-struct ldb_dn *ldb_dn_map_rebase_remote(struct ldb_module *module, void *mem_ctx, const struct ldb_dn *dn);
+struct ldb_dn *ldb_dn_map_local(struct ldb_module *module, void *mem_ctx, struct ldb_dn *dn);
+struct ldb_dn *ldb_dn_map_remote(struct ldb_module *module, void *mem_ctx, struct ldb_dn *dn);
+struct ldb_dn *ldb_dn_map_rebase_remote(struct ldb_module *module, void *mem_ctx, struct ldb_dn *dn);
 
-struct ldb_request *map_search_base_req(struct map_context *ac, const struct ldb_dn *dn, const char * const *attrs, const struct ldb_parse_tree *tree, void *context, ldb_search_callback callback);
-struct ldb_request *map_search_self_req(struct map_context *ac, const struct ldb_dn *dn);
-struct ldb_request *map_build_fixup_req(struct map_context *ac, const struct ldb_dn *olddn, const struct ldb_dn *newdn);
+struct ldb_request *map_search_base_req(struct map_context *ac, struct ldb_dn *dn, const char * const *attrs, const struct ldb_parse_tree *tree, void *context, ldb_search_callback callback);
+struct ldb_request *map_search_self_req(struct map_context *ac, struct ldb_dn *dn);
+struct ldb_request *map_build_fixup_req(struct map_context *ac, struct ldb_dn *olddn, struct ldb_dn *newdn);
 
 int map_subtree_collect_remote_simple(struct ldb_module *module, void *mem_ctx, struct ldb_parse_tree **new, const struct ldb_parse_tree *tree, const struct ldb_map_attribute *map);
 
diff --git a/source4/lib/ldb/modules/paged_searches.c b/source4/lib/ldb/modules/paged_searches.c
index c7d163307d..02d85e4c23 100644
--- a/source4/lib/ldb/modules/paged_searches.c
+++ b/source4/lib/ldb/modules/paged_searches.c
@@ -424,7 +424,7 @@ static int ps_init(struct ldb_module *module)
 	}
 
 	req->operation = LDB_SEARCH;
-	req->op.search.base = ldb_dn_new(req);
+	req->op.search.base = ldb_dn_new(req, module->ldb, NULL);
 	req->op.search.scope = LDB_SCOPE_BASE;
 
 	req->op.search.tree = ldb_parse_tree(req, "objectClass=*");
diff --git a/source4/lib/ldb/nssldb/ldb-nss.c b/source4/lib/ldb/nssldb/ldb-nss.c
index 614f6e170f..4577cea524 100644
--- a/source4/lib/ldb/nssldb/ldb-nss.c
+++ b/source4/lib/ldb/nssldb/ldb-nss.c
@@ -62,8 +62,8 @@ NSS_STATUS _ldb_nss_init(void)
 		goto failed;
 	}
 
-	_ldb_nss_ctx->base = ldb_dn_explode(_ldb_nss_ctx, _LDB_NSS_BASEDN);
-	if (_ldb_nss_ctx->base == NULL) {
+	_ldb_nss_ctx->base = ldb_dn_new(_ldb_nss_ctx, _ldb_nss_ctx->ldb, _LDB_NSS_BASEDN);
+	if ( ! ldb_dn_validate(_ldb_nss_ctx->base)) {
 		goto failed;
 	}
 
diff --git a/source4/lib/ldb/nssldb/ldb-nss.h b/source4/lib/ldb/nssldb/ldb-nss.h
index c780a21e81..1ed68033e0 100644
--- a/source4/lib/ldb/nssldb/ldb-nss.h
+++ b/source4/lib/ldb/nssldb/ldb-nss.h
@@ -46,7 +46,7 @@ struct _ldb_nss_context {
 	pid_t pid;
 
 	struct ldb_context *ldb;
-	const struct ldb_dn *base;
+	struct ldb_dn *base;
 
 	int pw_cur;
 	struct ldb_result *pw_res;
diff --git a/source4/lib/ldb/samba/ldif_handlers.c b/source4/lib/ldb/samba/ldif_handlers.c
index 8abfb87238..d017306176 100644
--- a/source4/lib/ldb/samba/ldif_handlers.c
+++ b/source4/lib/ldb/samba/ldif_handlers.c
@@ -300,8 +300,8 @@ static int ldif_canonicalise_objectCategory(struct ldb_context *ldb, void *mem_c
 	struct ldb_dn *dn1 = NULL;
 	char *oc1, *oc2;
 
-	dn1 = ldb_dn_explode(mem_ctx, (char *)in->data);
-	if (dn1 == NULL) {
+	dn1 = ldb_dn_new(mem_ctx, ldb, (char *)in->data);
+	if ( ! ldb_dn_validate(dn1)) {
 		oc1 = talloc_strndup(mem_ctx, (char *)in->data, in->length);
 	} else if (ldb_dn_get_comp_num(dn1) >= 1 && strcasecmp(ldb_dn_get_rdn_name(dn1), "cn") == 0) {
 		const struct ldb_val *val = ldb_dn_get_rdn_val(dn1);
@@ -325,8 +325,8 @@ static int ldif_comparison_objectCategory(struct ldb_context *ldb, void *mem_ctx
 	struct ldb_dn *dn1 = NULL, *dn2 = NULL;
 	const char *oc1, *oc2;
 
-	dn1 = ldb_dn_explode(mem_ctx, (char *)v1->data);
-	if (dn1 == NULL) {
+	dn1 = ldb_dn_new(mem_ctx, ldb, (char *)v1->data);
+	if ( ! ldb_dn_validate(dn1)) {
 		oc1 = talloc_strndup(mem_ctx, (char *)v1->data, v1->length);
 	} else if (ldb_dn_get_comp_num(dn1) >= 1 && strcasecmp(ldb_dn_get_rdn_name(dn1), "cn") == 0) {
 		const struct ldb_val *val = ldb_dn_get_rdn_val(dn1);
@@ -335,8 +335,8 @@ static int ldif_comparison_objectCategory(struct ldb_context *ldb, void *mem_ctx
 		oc1 = NULL;
 	}
 
-	dn2 = ldb_dn_explode(mem_ctx, (char *)v2->data);
-	if (dn2 == NULL) {
+	dn2 = ldb_dn_new(mem_ctx, ldb, (char *)v2->data);
+	if ( ! ldb_dn_validate(dn2)) {
 		oc2 = talloc_strndup(mem_ctx, (char *)v2->data, v2->length);
 	} else if (ldb_dn_get_comp_num(dn2) >= 2 && strcasecmp(ldb_dn_get_rdn_name(dn2), "cn") == 0) {
 		const struct ldb_val *val = ldb_dn_get_rdn_val(dn2);
diff --git a/source4/lib/ldb/tests/test-ldap.sh b/source4/lib/ldb/tests/test-ldap.sh
index b9d224e0af..14cfb5f979 100755
--- a/source4/lib/ldb/tests/test-ldap.sh
+++ b/source4/lib/ldb/tests/test-ldap.sh
@@ -49,6 +49,6 @@ else
     ret=$?
 fi
 
-$LDBDIR/tests/kill_slapd.sh
+#$LDBDIR/tests/kill_slapd.sh
 
 exit $ret
diff --git a/source4/lib/ldb/tools/ad2oLschema.c b/source4/lib/ldb/tools/ad2oLschema.c
index 62c6e01c2e..49c4fa1fd6 100644
--- a/source4/lib/ldb/tools/ad2oLschema.c
+++ b/source4/lib/ldb/tools/ad2oLschema.c
@@ -200,7 +200,7 @@ static struct ldb_dn *find_schema_dn(struct ldb_context *ldb, TALLOC_CTX *mem_ct
 {
 	const char *rootdse_attrs[] = {"schemaNamingContext", NULL};
 	struct ldb_dn *schemadn;
-	struct ldb_dn *basedn = ldb_dn_explode(mem_ctx, "");
+	struct ldb_dn *basedn = ldb_dn_new(mem_ctx, ldb, NULL);
 	struct ldb_result *rootdse_res;
 	int ldb_ret;
 	if (!basedn) {
@@ -222,7 +222,7 @@ static struct ldb_dn *find_schema_dn(struct ldb_context *ldb, TALLOC_CTX *mem_ct
 	}
 	
 	/* Locate schema */
-	schemadn = ldb_msg_find_attr_as_dn(mem_ctx, rootdse_res->msgs[0], "schemaNamingContext");
+	schemadn = ldb_msg_find_attr_as_dn(ldb, mem_ctx, rootdse_res->msgs[0], "schemaNamingContext");
 	if (!schemadn) {
 		return NULL;
 	}
diff --git a/source4/lib/ldb/tools/ldbdel.c b/source4/lib/ldb/tools/ldbdel.c
index 94f1da9903..b4da806b51 100644
--- a/source4/lib/ldb/tools/ldbdel.c
+++ b/source4/lib/ldb/tools/ldbdel.c
@@ -36,7 +36,7 @@
 #include "ldb/include/includes.h"
 #include "ldb/tools/cmdline.h"
 
-static int ldb_delete_recursive(struct ldb_context *ldb, const struct ldb_dn *dn)
+static int ldb_delete_recursive(struct ldb_context *ldb, struct ldb_dn *dn)
 {
 	int ret, i, total=0;
 	const char *attrs[] = { NULL };
@@ -91,10 +91,10 @@ int main(int argc, const char **argv)
 	}
 
 	for (i=0;i<options->argc;i++) {
-		const struct ldb_dn *dn;
+		struct ldb_dn *dn;
 
-		dn = ldb_dn_explode(ldb, options->argv[i]);
-		if (dn == NULL) {
+		dn = ldb_dn_new(ldb, ldb, options->argv[i]);
+		if ( ! ldb_dn_validate(dn)) {
 			printf("Invalid DN format\n");
 			exit(1);
 		}
diff --git a/source4/lib/ldb/tools/ldbedit.c b/source4/lib/ldb/tools/ldbedit.c
index 17ade152b7..429febb75b 100644
--- a/source4/lib/ldb/tools/ldbedit.c
+++ b/source4/lib/ldb/tools/ldbedit.c
@@ -91,11 +91,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 struct ldb_dn *dn)
+				    struct ldb_dn *dn)
 {
 	int i;
 	for (i=0;i<count;i++) {
-		if (ldb_dn_compare(ldb, dn, msgs[i]->dn) == 0) {
+		if (ldb_dn_compare(dn, msgs[i]->dn) == 0) {
 			return msgs[i];
 		}
 	}
@@ -300,8 +300,8 @@ int main(int argc, const char **argv)
 	}
 
 	if (options->basedn != NULL) {
-		basedn = ldb_dn_explode(ldb, options->basedn);
-		if (basedn == NULL) {
+		basedn = ldb_dn_new(ldb, ldb, options->basedn);
+		if ( ! ldb_dn_validate(basedn)) {
 			printf("Invalid Base DN format\n");
 			exit(1);
 		}
diff --git a/source4/lib/ldb/tools/ldbrename.c b/source4/lib/ldb/tools/ldbrename.c
index 9c0870721d..d7e1347fea 100644
--- a/source4/lib/ldb/tools/ldbrename.c
+++ b/source4/lib/ldb/tools/ldbrename.c
@@ -56,7 +56,7 @@ int main(int argc, const char **argv)
 	struct ldb_context *ldb;
 	int ret;
 	struct ldb_cmdline *options;
-	const struct ldb_dn *dn1, *dn2;
+	struct ldb_dn *dn1, *dn2;
 
 	ldb_global_init();
 
@@ -68,8 +68,17 @@ int main(int argc, const char **argv)
 		usage();
 	}
 
-	dn1 = ldb_dn_explode(ldb, options->argv[0]);
-	dn2 = ldb_dn_explode(ldb, options->argv[1]);
+	dn1 = ldb_dn_new(ldb, ldb, options->argv[0]);
+	dn2 = ldb_dn_new(ldb, ldb, options->argv[1]);
+
+	if ( ! ldb_dn_validate(dn1)) {
+		printf("Invalid DN1: %s\n", options->argv[0]);
+		return -1;
+	}
+	if ( ! ldb_dn_validate(dn2)) {
+		printf("Invalid DN2: %s\n", options->argv[1]);
+		return -1;
+	}
 
 	ret = ldb_rename(ldb, dn1, dn2);
 	if (ret == 0) {
diff --git a/source4/lib/ldb/tools/ldbsearch.c b/source4/lib/ldb/tools/ldbsearch.c
index 837dfc9088..7bf9d64fc2 100644
--- a/source4/lib/ldb/tools/ldbsearch.c
+++ b/source4/lib/ldb/tools/ldbsearch.c
@@ -54,8 +54,7 @@ static int do_compare_msg(struct ldb_message **el1,
 			  struct ldb_message **el2,
 			  void *opaque)
 {
-	struct ldb_context *ldb = talloc_get_type(opaque, struct ldb_context);
-	return ldb_dn_compare(ldb, (*el1)->dn, (*el2)->dn);
+	return ldb_dn_compare((*el1)->dn, (*el2)->dn);
 }
 
 struct search_context {
@@ -185,7 +184,7 @@ static int search_callback(struct ldb_context *ldb, void *context, struct ldb_re
 }
 
 static int do_search(struct ldb_context *ldb,
-		     const struct ldb_dn *basedn,
+		     struct ldb_dn *basedn,
 		     struct ldb_cmdline *options,
 		     const char *expression,
 		     const char * const *attrs)
@@ -298,8 +297,8 @@ int main(int argc, const char **argv)
 	}
 
 	if (options->basedn != NULL) {
-		basedn = ldb_dn_explode(ldb, options->basedn);
-		if (basedn == NULL) {
+		basedn = ldb_dn_new(ldb, ldb, options->basedn);
+		if ( ! ldb_dn_validate(basedn)) {
 			fprintf(stderr, "Invalid Base DN format\n");
 			exit(1);
 		}
diff --git a/source4/lib/ldb/tools/ldbtest.c b/source4/lib/ldb/tools/ldbtest.c
index 6cc8dfe19b..70b2b0148a 100644
--- a/source4/lib/ldb/tools/ldbtest.c
+++ b/source4/lib/ldb/tools/ldbtest.c
@@ -52,7 +52,7 @@ static double _end_timer(void)
 }
 
 static void add_records(struct ldb_context *ldb,
-			const struct ldb_dn *basedn,
+			struct ldb_dn *basedn,
 			int count)
 {
 	struct ldb_message msg;
@@ -72,7 +72,8 @@ static void add_records(struct ldb_context *ldb,
 
 		name = talloc_asprintf(tmp_ctx, "Test%d", i);
 
-		msg.dn = ldb_dn_build_child(tmp_ctx, "cn", name, basedn);
+		msg.dn = ldb_dn_copy(tmp_ctx, basedn);
+		ldb_dn_add_child_fmt(msg.dn, "cn=%s", name);
 		msg.num_elements = 6;
 		msg.elements = el;
 
@@ -140,7 +141,7 @@ static void add_records(struct ldb_context *ldb,
 }
 
 static void modify_records(struct ldb_context *ldb,
-			   const struct ldb_dn *basedn,
+			   struct ldb_dn *basedn,
 			   int count)
 {
 	struct ldb_message msg;
@@ -153,7 +154,8 @@ 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 = ldb_dn_build_child(tmp_ctx, "cn", name, basedn);
+		msg.dn = ldb_dn_copy(tmp_ctx, basedn);
+		ldb_dn_add_child_fmt(msg.dn, "cn=%s", name);
 
 		msg.num_elements = 3;
 		msg.elements = el;
@@ -192,7 +194,7 @@ static void modify_records(struct ldb_context *ldb,
 
 
 static void delete_records(struct ldb_context *ldb,
-			   const struct ldb_dn *basedn,
+			   struct ldb_dn *basedn,
 			   int count)
 {
 	int i;
@@ -200,13 +202,14 @@ static void delete_records(struct ldb_context *ldb,
 	for (i=0;i<count;i++) {
 		struct ldb_dn *dn;
 		char *name = talloc_asprintf(ldb, "Test%d", i);
-		dn = ldb_dn_build_child(name, "cn", name, basedn);
+		dn = ldb_dn_copy(name, basedn);
+		ldb_dn_add_child_fmt(dn, "cn=%s", name);
 
 		printf("Deleting uid Test%d\r", i);
 		fflush(stdout);
 
 		if (ldb_delete(ldb, dn) != 0) {
-			printf("Delete of %s failed - %s\n", ldb_dn_linearize(ldb, dn), ldb_errstring(ldb));
+			printf("Delete of %s failed - %s\n", ldb_dn_get_linearized(dn), ldb_errstring(ldb));
 			exit(1);
 		}
 		talloc_free(name);
@@ -252,7 +255,11 @@ static void start_test(struct ldb_context *ldb, int nrecords, int nsearches)
 {
 	struct ldb_dn *basedn;
 
-	basedn = ldb_dn_explode(ldb, options->basedn);
+	basedn = ldb_dn_new(ldb, ldb, options->basedn);
+	if ( ! ldb_dn_validate(basedn)) {
+		printf("Invalid base DN\n");
+		exit(1);
+	}
 
 	printf("Adding %d records\n", nrecords);
 	add_records(ldb, basedn, nrecords);
@@ -305,7 +312,7 @@ static void start_test_index(struct ldb_context **ldb)
 
 	printf("Starting index test\n");
 
-	indexlist = ldb_dn_explode(NULL, "@INDEXLIST");
+	indexlist = ldb_dn_new(*ldb, *ldb, "@INDEXLIST");
 
 	ldb_delete(*ldb, indexlist);
 
@@ -319,10 +326,11 @@ static void start_test_index(struct ldb_context **ldb)
 		exit(1);
 	}
 
-	basedn = ldb_dn_explode(NULL, options->basedn);
+	basedn = ldb_dn_new(*ldb, *ldb, options->basedn);
 
 	memset(msg, 0, sizeof(*msg));
-	msg->dn = ldb_dn_build_child(msg, "cn", "test", basedn);
+	msg->dn = ldb_dn_copy(msg, basedn);
+	ldb_dn_add_child_fmt(msg->dn, "cn=test");
 	ldb_msg_add_string(msg, "cn", strdup("test"));
 	ldb_msg_add_string(msg, "sn", strdup("test"));
 	ldb_msg_add_string(msg, "uid", strdup("test"));
@@ -339,13 +347,15 @@ static void start_test_index(struct ldb_context **ldb)
 	}
 
 	(*ldb) = ldb_init(options);
-	
+
 	ret = ldb_connect(*ldb, options->url, flags, NULL);
 	if (ret != 0) {
 		printf("failed to connect to %s\n", options->url);
 		exit(1);
 	}
 
+	basedn = ldb_dn_new(*ldb, *ldb, options->basedn);
+
 	ret = ldb_search(*ldb, basedn, LDB_SCOPE_SUBTREE, "uid=test", NULL, &res);
 	if (ret != LDB_SUCCESS) { 
 		printf("Search with (uid=test) filter failed!\n");
@@ -356,6 +366,8 @@ static void start_test_index(struct ldb_context **ldb)
 		exit(1);
 	}
 
+	indexlist = ldb_dn_new(*ldb, *ldb, "@INDEXLIST");
+
 	if (ldb_delete(*ldb, msg->dn) != 0 ||
 	    ldb_delete(*ldb, indexlist) != 0) {
 		printf("cleanup failed - %s\n", ldb_errstring(*ldb));
diff --git a/source4/lib/ldb/tools/oLschema2ldif.c b/source4/lib/ldb/tools/oLschema2ldif.c
index a9e157e323..7863f5dcb7 100644
--- a/source4/lib/ldb/tools/oLschema2ldif.c
+++ b/source4/lib/ldb/tools/oLschema2ldif.c
@@ -388,9 +388,8 @@ static struct ldb_message *process_entry(TALLOC_CTX *mem_ctx, const char *entry)
 			MSG_ADD_STRING("cn", token->value);
 			MSG_ADD_STRING("name", token->value);
 			MSG_ADD_STRING("lDAPDisplayName", token->value);
-			msg->dn = ldb_dn_string_compose(msg, basedn,
-							"CN=%s,CN=Schema,CN=Configuration",
-							token->value);
+			msg->dn = ldb_dn_copy(msg, basedn);
+			ldb_dn_add_child_fmt(msg->dn, "CN=%s,CN=Schema,CN=Configuration", token->value);
 			break;
 
 		case SCHEMA_SUP:
@@ -575,8 +574,8 @@ static void usage(void)
 		perror("Base DN not specified");
 		exit(1);
 	} else {
-		basedn = ldb_dn_explode(ctx, options->basedn);
-		if (basedn == NULL) {
+		basedn = ldb_dn_new(ctx, ldb_ctx, options->basedn);
+		if ( ! ldb_dn_validate(basedn)) {
 			perror("Malformed Base DN");
 			exit(1);
 		}
diff --git a/source4/lib/registry/reg_backend_ldb.c b/source4/lib/registry/reg_backend_ldb.c
index b9bfe8a230..5f9481fa67 100644
--- a/source4/lib/registry/reg_backend_ldb.c
+++ b/source4/lib/registry/reg_backend_ldb.c
@@ -27,7 +27,7 @@
 
 struct ldb_key_data 
 {
-	const struct ldb_dn *dn;
+	struct ldb_dn *dn;
 	struct ldb_message **subkeys, **values;
 	int subkey_count, value_count;
 };
@@ -115,15 +115,24 @@ static int reg_close_ldb_key(struct registry_key *key)
 static struct ldb_dn *reg_path_to_ldb(TALLOC_CTX *mem_ctx, const struct registry_key *from, const char *path, const char *add)
 {
 	TALLOC_CTX *local_ctx;
-	struct ldb_dn *ret = ldb_dn_new(mem_ctx);
+	struct ldb_dn *ret;
 	char *mypath = talloc_strdup(mem_ctx, path);
 	char *begin;
 	struct ldb_key_data *kd = talloc_get_type(from->backend_data, struct ldb_key_data);
+	struct ldb_context *ldb = talloc_get_type(from->hive->backend_data, struct ldb_context);
 
 	local_ctx = talloc_new(mem_ctx);
 
-	if (add) 
-		ret = ldb_dn_compose(local_ctx, ret, ldb_dn_explode(mem_ctx, add));
+	if (add) {
+		ret = ldb_dn_new(mem_ctx, ldb, add);
+	} else {
+		ret = ldb_dn_new(mem_ctx, ldb, NULL);
+	}
+	if ( ! ldb_dn_validate(ret)) {
+		talloc_free(ret);
+		talloc_free(local_ctx);
+		return NULL;
+	}
 
 	while(mypath) {
 		char *keyname;
@@ -134,10 +143,7 @@ static struct ldb_dn *reg_path_to_ldb(TALLOC_CTX *mem_ctx, const struct registry
 		else keyname = mypath;
 
 		if(strlen(keyname)) {
-			struct ldb_dn *base;
-
-			base = ldb_dn_build_child(local_ctx, "key", keyname, NULL);
-			ret = ldb_dn_compose(local_ctx, ret, base);
+			ldb_dn_add_base_fmt(ret, "key=%s", keyname);
 		}
 
 		if(begin) {
@@ -147,7 +153,7 @@ static struct ldb_dn *reg_path_to_ldb(TALLOC_CTX *mem_ctx, const struct registry
 		}
 	}
 
-	ret = ldb_dn_compose(mem_ctx, ret, kd->dn);
+	ldb_dn_add_base(ret, kd->dn);
 
 	talloc_free(local_ctx);
 
@@ -277,7 +283,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 = ldb_dn_explode(*k, "hive=NONE");
+	kd->dn = ldb_dn_new(*k, wrap, "hive=NONE");
 	
 
 	return WERR_OK;
@@ -316,7 +322,10 @@ static WERROR ldb_del_key (const struct registry_key *key, const char *child)
 	struct ldb_context *ctx = talloc_get_type(key->hive->backend_data, struct ldb_context);
 	int ret;
 	struct ldb_key_data *kd = talloc_get_type(key->backend_data, struct ldb_key_data);
-	struct ldb_dn *childdn = ldb_dn_build_child(ctx, "key", child, kd->dn);
+	struct ldb_dn *childdn;
+
+	childdn = ldb_dn_copy(ctx, kd->dn);
+	ldb_dn_add_child_fmt(childdn, "key=%s", child);
 
 	ret = ldb_delete(ctx, childdn);
 
@@ -335,7 +344,10 @@ static WERROR ldb_del_value (const struct registry_key *key, const char *child)
 	int ret;
 	struct ldb_context *ctx = talloc_get_type(key->hive->backend_data, struct ldb_context);
 	struct ldb_key_data *kd = talloc_get_type(key->backend_data, struct ldb_key_data);
-	struct ldb_dn *childdn = ldb_dn_build_child(ctx, "value", child, kd->dn);
+	struct ldb_dn *childdn;
+
+	childdn = ldb_dn_copy(ctx, kd->dn);
+	ldb_dn_add_child_fmt(childdn, "value=%s", child);
 
 	ret = ldb_delete(ctx, childdn);
 
@@ -359,7 +371,8 @@ static WERROR ldb_set_value (const struct registry_key *parent, const char *name
 
 	msg = reg_ldb_pack_value(ctx, mem_ctx, name, type, data);
 
-	msg->dn = ldb_dn_build_child(msg, "value", name, kd->dn);
+	msg->dn = ldb_dn_copy(msg, kd->dn);
+	ldb_dn_add_child_fmt(msg->dn, "value=%s", name);
 
 	ret = ldb_add(ctx, msg);
 	if (ret < 0) {
diff --git a/source4/libnet/libnet_join.c b/source4/libnet/libnet_join.c
index 01872eb7fc..e68b0d6235 100644
--- a/source4/libnet/libnet_join.c
+++ b/source4/libnet/libnet_join.c
@@ -62,7 +62,7 @@ static NTSTATUS libnet_JoinADSDomain(struct libnet_context *ctx, struct libnet_J
 	struct GUID drsuapi_bind_guid;
 
 	struct ldb_context *remote_ldb;
-	const struct ldb_dn *account_dn;
+	struct ldb_dn *account_dn;
 	const char *account_dn_str;
 	const char *remote_ldb_url;
 	struct ldb_result *res;
@@ -219,8 +219,8 @@ static NTSTATUS libnet_JoinADSDomain(struct libnet_context *ctx, struct libnet_J
 	/* Store the DN of our machine account. */
 	account_dn_str = r_crack_names.out.ctr.ctr1->array[0].result_name;
 
-	account_dn = ldb_dn_explode(tmp_ctx, account_dn_str);
-	if (!account_dn) {
+	account_dn = ldb_dn_new(tmp_ctx, remote_ldb, account_dn_str);
+	if (! ldb_dn_validate(account_dn)) {
 		r->out.error_string = talloc_asprintf(r, "Invalid account dn: %s",
 						      account_dn_str);
 		talloc_free(tmp_ctx);
@@ -855,7 +855,7 @@ static NTSTATUS libnet_Join_primary_domain(struct libnet_context *ctx,
 	struct libnet_JoinDomain *r2;
 	int ret, rtn;
 	struct ldb_context *ldb;
-	const struct ldb_dn *base_dn;
+	struct ldb_dn *base_dn;
 	struct ldb_message **msgs, *msg;
 	const char *sct;
 	const char * const attrs[] = {
@@ -961,15 +961,15 @@ static NTSTATUS libnet_Join_primary_domain(struct libnet_context *ctx,
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	base_dn = ldb_dn_explode(tmp_mem, "cn=Primary Domains");
+	base_dn = ldb_dn_new(tmp_mem, ldb, "cn=Primary Domains");
 	if (!base_dn) {
 		r->out.error_string = NULL;
 		talloc_free(tmp_mem);
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	msg->dn = ldb_dn_build_child(tmp_mem, "flatname", r2->out.domain_name, base_dn);
-	if (!msg->dn) {
+	msg->dn = ldb_dn_copy(tmp_mem, base_dn);
+	if ( ! ldb_dn_add_child_fmt(msg->dn, "flatname=%s", r2->out.domain_name)) {
 		r->out.error_string = NULL;
 		talloc_free(tmp_mem);
 		return NT_STATUS_NO_MEMORY;
diff --git a/source4/libnet/libnet_samsync_ldb.c b/source4/libnet/libnet_samsync_ldb.c
index a57e2735e7..3c34aca944 100644
--- a/source4/libnet/libnet_samsync_ldb.c
+++ b/source4/libnet/libnet_samsync_ldb.c
@@ -89,9 +89,9 @@ static NTSTATUS samsync_ldb_add_foreignSecurityPrincipal(TALLOC_CTX *mem_ctx,
 	}
 
 	/* add core elements to the ldb_message for the alias */
-	msg->dn = ldb_dn_build_child(mem_ctx, "CN", sidstr, basedn);
-	if (msg->dn == NULL)
-		return NT_STATUS_NO_MEMORY;
+	msg->dn = basedn;
+	if ( ! ldb_dn_add_child_fmt(msg->dn, "CN=%s", sidstr))
+		return NT_STATUS_UNSUCCESSFUL;
 	
 	samdb_msg_add_string(state->sam_ldb, mem_ctx, msg,
 			     "objectClass",
@@ -128,7 +128,7 @@ static NTSTATUS samsync_ldb_handle_domain(TALLOC_CTX *mem_ctx,
 	}
 
 	if (database == SAM_DATABASE_DOMAIN) {
-		const struct ldb_dn *partitions_basedn;
+		struct ldb_dn *partitions_basedn;
 		const char *domain_attrs[] =  {"nETBIOSName", "nCName", NULL};
 		struct ldb_message **msgs_domain;
 		int ret_domain;
@@ -149,7 +149,7 @@ static NTSTATUS samsync_ldb_handle_domain(TALLOC_CTX *mem_ctx,
 			return NT_STATUS_NO_SUCH_DOMAIN;		
 		}
 
-		state->base_dn[database] = samdb_result_dn(state, msgs_domain[0], "nCName", NULL);
+		state->base_dn[database] = samdb_result_dn(state->sam_ldb, state, msgs_domain[0], "nCName", NULL);
 
 		if (state->dom_sid[database]) {
 			/* Update the domain sid with the incoming
@@ -181,7 +181,10 @@ static NTSTATUS samsync_ldb_handle_domain(TALLOC_CTX *mem_ctx,
 		   fetching here */
 		const char *dnstring = samdb_search_string(state->sam_ldb, mem_ctx, NULL,
 							   "distinguishedName", "objectClass=builtinDomain");
-		state->base_dn[database] = ldb_dn_explode(state, dnstring);
+		state->base_dn[database] = ldb_dn_new(state, state->sam_ldb, dnstring);
+		if ( ! ldb_dn_validate(state->base_dn[database])) {
+			return NT_STATUS_INTERNAL_ERROR;
+		}
 	} else {
 		/* PRIVs DB */
 		return NT_STATUS_INVALID_PARAMETER;
@@ -418,8 +421,8 @@ static NTSTATUS samsync_ldb_handle_user(TALLOC_CTX *mem_ctx,
 		samdb_msg_add_string(state->sam_ldb, mem_ctx, msg, 
 				     "objectClass", obj_class);
 		if (!msg->dn) {
-			msg->dn = ldb_dn_string_compose(mem_ctx, state->base_dn[database],
-							"CN=%s, CN=%s", cn_name, container);
+			msg->dn = ldb_dn_copy(mem_ctx, state->base_dn[database]);
+			ldb_dn_add_child_fmt(msg->dn, "CN=%s,CN=%s", cn_name, container);
 			if (!msg->dn) {
 				return NT_STATUS_NO_MEMORY;		
 			}
@@ -565,8 +568,8 @@ 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 = ldb_dn_string_compose(mem_ctx, state->base_dn[database],
-						"CN=%s, CN=%s", cn_name, container);
+		msg->dn = ldb_dn_copy(mem_ctx, state->base_dn[database]);
+		ldb_dn_add_child_fmt(msg->dn, "CN=%s,CN=%s", cn_name, container);
 		if (!msg->dn) {
 			return NT_STATUS_NO_MEMORY;		
 		}
@@ -779,8 +782,8 @@ 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 = ldb_dn_string_compose(mem_ctx, state->base_dn[database],
-						"CN=%s, CN=%s", cn_name, container);
+		msg->dn = ldb_dn_copy(mem_ctx, state->base_dn[database]);
+		ldb_dn_add_child_fmt(msg->dn, "CN=%s,CN=%s", cn_name, container);
 		if (!msg->dn) {
 			return NT_STATUS_NO_MEMORY;		
 		}
diff --git a/source4/libnet/libnet_site.c b/source4/libnet/libnet_site.c
index ec4bb13290..0c42bf1c73 100644
--- a/source4/libnet/libnet_site.c
+++ b/source4/libnet/libnet_site.c
@@ -186,8 +186,8 @@ NTSTATUS libnet_JoinSite(struct ldb_context *remote_ldb,
 		return NT_STATUS_NO_MEMORY;
 	}
 
-	server_dn = ldb_dn_explode(tmp_ctx, server_dn_str);
-	if (server_dn == NULL) {
+	server_dn = ldb_dn_new(tmp_ctx, remote_ldb, server_dn_str);
+	if ( ! ldb_dn_validate(server_dn)) {
 		libnet_r->out.error_string = talloc_asprintf(libnet_r,
 					"Invalid server dn: %s",
 					server_dn_str);
diff --git a/source4/nbt_server/dgram/netlogon.c b/source4/nbt_server/dgram/netlogon.c
index 3b67a7f5c9..3984d1f933 100644
--- a/source4/nbt_server/dgram/netlogon.c
+++ b/source4/nbt_server/dgram/netlogon.c
@@ -45,7 +45,7 @@ static void nbtd_netlogon_getdc(struct dgram_mailslot_handler *dgmslot,
 	const char *ref_attrs[] = {"nETBIOSName", NULL};
 	struct ldb_message **ref_res;
 	struct ldb_context *samctx;
-	const struct ldb_dn *partitions_basedn;
+	struct ldb_dn *partitions_basedn;
 	int ret;
 
 	/* only answer getdc requests on the PDC or LOGON names */
@@ -112,7 +112,7 @@ static void nbtd_netlogon_getdc2(struct dgram_mailslot_handler *dgmslot,
 	int ret;
 	const char **services = lp_server_services();
 	const char *my_ip = reply_iface->ip_address; 
-	const struct ldb_dn *partitions_basedn;
+	struct ldb_dn *partitions_basedn;
 	if (!my_ip) {
 		DEBUG(0, ("Could not obtain own IP address for datagram socket\n"));
 		return;
@@ -142,7 +142,7 @@ static void nbtd_netlogon_getdc2(struct dgram_mailslot_handler *dgmslot,
 
 	/* try and find the domain */
 	ret = gendb_search_dn(samctx, samctx, 
-			      samdb_result_dn(samctx, ref_res[0], "ncName", NULL), 
+			      samdb_result_dn(samctx, 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",
diff --git a/source4/nbt_server/wins/winsdb.c b/source4/nbt_server/wins/winsdb.c
index bc518233ab..7b0a0756c6 100644
--- a/source4/nbt_server/wins/winsdb.c
+++ b/source4/nbt_server/wins/winsdb.c
@@ -41,7 +41,7 @@ uint64_t winsdb_get_maxVersion(struct winsdb_handle *h)
 	TALLOC_CTX *tmp_ctx = talloc_new(ldb);
 	uint64_t maxVersion = 0;
 
-	dn = ldb_dn_explode(tmp_ctx, "CN=VERSION");
+	dn = ldb_dn_new(tmp_ctx, ldb, "CN=VERSION");
 	if (!dn) goto failed;
 
 	/* find the record in the WINS database */
@@ -78,7 +78,7 @@ uint64_t winsdb_set_maxVersion(struct winsdb_handle *h, uint64_t newMaxVersion)
 	trans = ldb_transaction_start(wins_db);
 	if (trans != LDB_SUCCESS) goto failed;
 
-	dn = ldb_dn_explode(tmp_ctx, "CN=VERSION");
+	dn = ldb_dn_new(tmp_ctx, wins_db, "CN=VERSION");
 	if (!dn) goto failed;
 
 	/* find the record in the WINS database */
@@ -139,7 +139,7 @@ uint64_t winsdb_get_seqnumber(struct winsdb_handle *h)
 	TALLOC_CTX *tmp_ctx = talloc_new(ldb);
 	uint64_t seqnumber = 0;
 
-	dn = ldb_dn_explode(tmp_ctx, "@BASEINFO");
+	dn = ldb_dn_new(tmp_ctx, ldb, "@BASEINFO");
 	if (!dn) goto failed;
 
 	/* find the record in the WINS database */
@@ -161,16 +161,16 @@ failed:
 /*
   return a DN for a nbt_name
 */
-static struct ldb_dn *winsdb_dn(TALLOC_CTX *mem_ctx, struct nbt_name *name)
+static struct ldb_dn *winsdb_dn(TALLOC_CTX *mem_ctx, struct ldb_context *ldb, struct nbt_name *name)
 {
 	struct ldb_dn *dn;
 
-	dn = ldb_dn_string_compose(mem_ctx, NULL, "type=0x%02X", name->type);
-	if (dn && name->name && *name->name) {
-		dn = ldb_dn_string_compose(mem_ctx, dn, "name=%s", name->name);
+	dn = ldb_dn_new_fmt(mem_ctx, ldb, "type=0x%02X", name->type);
+	if (ldb_dn_is_valid(dn) && name->name && *name->name) {
+		ldb_dn_add_child_fmt(dn, "name=%s", name->name);
 	}
-	if (dn && name->scope && *name->scope) {
-		dn = ldb_dn_string_compose(mem_ctx, dn, "scope=%s", name->scope);
+	if (ldb_dn_is_valid(dn) && name->scope && *name->scope) {
+		ldb_dn_add_child_fmt(dn, "scope=%s", name->scope);
 	}
 	return dn;
 }
@@ -589,7 +589,7 @@ NTSTATUS winsdb_lookup(struct winsdb_handle *h,
 	time_t now = time(NULL);
 
 	/* find the record in the WINS database */
-	ret = ldb_search(wins_db, winsdb_dn(tmp_ctx, name), LDB_SCOPE_BASE, 
+	ret = ldb_search(wins_db, winsdb_dn(tmp_ctx, wins_db, name), LDB_SCOPE_BASE, 
 			 NULL, NULL, &res);
 
 	talloc_steal(tmp_ctx, res);
@@ -783,7 +783,7 @@ struct ldb_message *winsdb_message(struct ldb_context *ldb,
 		goto failed;
 	}
 
-	msg->dn = winsdb_dn(msg, rec->name);
+	msg->dn = winsdb_dn(msg, ldb, rec->name);
 	if (msg->dn == NULL) goto failed;
 	ret |= ldb_msg_add_fmt(msg, "type", "0x%02X", rec->name->type);
 	if (rec->name->name && *rec->name->name) {
@@ -918,14 +918,14 @@ uint8_t winsdb_delete(struct winsdb_handle *h, struct winsdb_record *rec)
 {
 	struct ldb_context *wins_db = h->ldb;
 	TALLOC_CTX *tmp_ctx = talloc_new(wins_db);
-	const struct ldb_dn *dn;
+	struct ldb_dn *dn;
 	int trans;
 	int ret;
 
 	trans = ldb_transaction_start(wins_db);
 	if (trans != LDB_SUCCESS) goto failed;
 
-	dn = winsdb_dn(tmp_ctx, rec->name);
+	dn = winsdb_dn(tmp_ctx, wins_db, rec->name);
 	if (dn == NULL) goto failed;
 
 	ret = ldb_delete(wins_db, dn);
@@ -959,7 +959,7 @@ static BOOL winsdb_check_or_add_module_list(struct winsdb_handle *h)
 	if (trans != LDB_SUCCESS) goto failed;
 
 	/* check if we have a special @MODULES record already */
-	dn = ldb_dn_explode(tmp_ctx, "@MODULES");
+	dn = ldb_dn_new(tmp_ctx, h->ldb, "@MODULES");
 	if (!dn) goto failed;
 
 	/* find the record in the WINS database */
diff --git a/source4/ntptr/simple_ldb/ntptr_simple_ldb.c b/source4/ntptr/simple_ldb/ntptr_simple_ldb.c
index 136dae352a..d504a53a83 100644
--- a/source4/ntptr/simple_ldb/ntptr_simple_ldb.c
+++ b/source4/ntptr/simple_ldb/ntptr_simple_ldb.c
@@ -49,14 +49,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 struct ldb_dn *basedn,
+			  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 struct ldb_dn *basedn,
+			  struct ldb_dn *basedn,
 			  struct ldb_message ***res,
 			  const char * const *attrs,
 			  const char *format, ...)
@@ -227,7 +227,7 @@ static WERROR sptr_EnumPrintServerForms(struct ntptr_GenericHandle *server, TALL
 	union spoolss_FormInfo *info;
 
 	count = sptr_db_search(sptr_db, mem_ctx,
-				ldb_dn_explode(mem_ctx, "CN=Forms,CN=PrintServer"),
+				ldb_dn_new(mem_ctx, sptr_db, "CN=Forms,CN=PrintServer"),
 				&msgs, NULL, "(&(objectClass=form))");
 
 	if (count == 0) return WERR_OK;
@@ -282,7 +282,7 @@ static WERROR sptr_AddPrintServerForm(struct ntptr_GenericHandle *server, TALLOC
 			return WERR_FOOBAR;
 		}
 		count = sptr_db_search(sptr_db, mem_ctx,
-				       ldb_dn_explode(mem_ctx, "CN=Forms,CN=PrintServer"),
+				       ldb_dn_new(mem_ctx, sptr_db, "CN=Forms,CN=PrintServer"),
 				       &msgs, attrs, "(&(form-name=%s)(objectClass=form))",
 				       r->in.info.info1->form_name);
 
@@ -298,9 +298,7 @@ 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 = ldb_dn_build_child(msg,
-					     "form-name", r->in.info.info1->form_name,
-					     ldb_dn_explode(msg, "CN=Forms,CN=PrintServer"));
+		msg->dn = ldb_dn_new_fmt(msg, sptr_db, "form-name=%s,CN=Forms,CN=PrintServer", r->in.info.info1->form_name);
 		SET_STRING(sptr_db, msg, "objectClass", "form");
 
 		SET_UINT(sptr_db, msg, "flags", r->in.info.info1->flags);
@@ -349,7 +347,7 @@ static WERROR sptr_SetPrintServerForm(struct ntptr_GenericHandle *server, TALLOC
 		}
 
 		count = sptr_db_search(sptr_db, mem_ctx,
-				       ldb_dn_explode(mem_ctx, "CN=Forms,CN=PrintServer"),
+				       ldb_dn_new(mem_ctx, sptr_db, "CN=Forms,CN=PrintServer"),
 				       &msgs, attrs, "(&(form-name=%s)(objectClass=form))",
 				       r->in.info.info1->form_name);
 
@@ -412,7 +410,7 @@ static WERROR sptr_DeletePrintServerForm(struct ntptr_GenericHandle *server, TAL
 	}
 
 	count = sptr_db_search(sptr_db, mem_ctx,
-			       ldb_dn_explode(mem_ctx, "CN=Forms,CN=PrintServer"),
+			       ldb_dn_new(mem_ctx, sptr_db, "CN=Forms,CN=PrintServer"),
 			       &msgs, attrs, "(&(form-name=%s)(objectclass=form))",
 			       r->in.form_name);
 
@@ -704,7 +702,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 struct ldb_dn *base_dn;
+	struct ldb_dn *base_dn;
 	int count;
 	union spoolss_FormInfo *info;
 
@@ -714,7 +712,7 @@ static WERROR sptr_GetPrinterForm(struct ntptr_GenericHandle *printer, TALLOC_CT
 	 * }
 	 */
 
-	base_dn = ldb_dn_string_compose(mem_ctx, NULL, "CN=Forms, CN=%s, CN=Printers", printer->object_name);
+	base_dn = ldb_dn_new_fmt(mem_ctx, sptr_db, "CN=Forms,CN=%s,CN=Printers", printer->object_name);
 	W_ERROR_HAVE_NO_MEMORY(base_dn);
 
 	count = sptr_db_search(sptr_db, mem_ctx, base_dn, &msgs, NULL,
diff --git a/source4/param/secrets.c b/source4/param/secrets.c
index 876be607f1..a7eb9607de 100644
--- a/source4/param/secrets.c
+++ b/source4/param/secrets.c
@@ -141,7 +141,7 @@ struct dom_sid *secrets_get_domain_sid(TALLOC_CTX *mem_ctx,
 	}
 
 	ldb_ret = gendb_search(ldb, ldb,
-			       ldb_dn_explode(mem_ctx, SECRETS_PRIMARY_DOMAIN_DN), 
+			       ldb_dn_new(mem_ctx, ldb, SECRETS_PRIMARY_DOMAIN_DN), 
 			       &msgs, attrs,
 			       SECRETS_PRIMARY_DOMAIN_FILTER, domain);
 
diff --git a/source4/param/share_ldb.c b/source4/param/share_ldb.c
index 62b529e6cf..8db3a02f1c 100644
--- a/source4/param/share_ldb.c
+++ b/source4/param/share_ldb.c
@@ -171,7 +171,7 @@ static NTSTATUS sldb_list_all(TALLOC_CTX *mem_ctx,
 
 	ldb = talloc_get_type(ctx->priv_data, struct ldb_context);
 
-	ret = ldb_search(ldb, ldb_dn_explode(tmp_ctx, "CN=SHARES"), LDB_SCOPE_SUBTREE, "(name=*)", NULL, &res);
+	ret = ldb_search(ldb, ldb_dn_new(tmp_ctx, ldb, "CN=SHARES"), LDB_SCOPE_SUBTREE, "(name=*)", NULL, &res);
 	talloc_steal(tmp_ctx, res);
 	if (ret != LDB_SUCCESS) {
 		talloc_free(tmp_ctx);
@@ -227,7 +227,7 @@ static NTSTATUS sldb_get_config(TALLOC_CTX *mem_ctx,
 		talloc_free(tmp_ctx);
 		return NT_STATUS_NO_MEMORY;
 	}
-	ret = ldb_search(ldb, ldb_dn_explode(tmp_ctx, "CN=SHARES"), LDB_SCOPE_SUBTREE, filter, NULL, &res);
+	ret = ldb_search(ldb, ldb_dn_new(tmp_ctx, ldb, "CN=SHARES"), LDB_SCOPE_SUBTREE, filter, NULL, &res);
 	talloc_steal(tmp_ctx, res);
 	if (ret != LDB_SUCCESS || res->count != 1) {
 		talloc_free(tmp_ctx);
@@ -324,7 +324,7 @@ NTSTATUS sldb_create(struct share_context *ctx, const char *name, struct share_i
 	}
 
 	/* TODO: escape info->name */
-	msg->dn = ldb_dn_string_compose(tmp_ctx, ldb_dn_new(tmp_ctx), "CN=%s,CN=SHARES", name);
+	msg->dn = ldb_dn_new_fmt(tmp_ctx, ldb, "CN=%s,CN=SHARES", name);
 	if (!msg->dn) {
 		DEBUG(0,("ERROR: Out of memory!\n"));
 		ret = NT_STATUS_NO_MEMORY;
@@ -454,7 +454,7 @@ NTSTATUS sldb_set(struct share_context *ctx, const char *name, struct share_info
 	}
 
 	/* TODO: escape name */
-	msg->dn = ldb_dn_string_compose(tmp_ctx, ldb_dn_new(tmp_ctx), "CN=%s,CN=SHARES", name);
+	msg->dn = ldb_dn_new_fmt(tmp_ctx, ldb, "CN=%s,CN=SHARES", name);
 	if (!msg->dn) {
 		DEBUG(0,("ERROR: Out of memory!\n"));
 		ret = NT_STATUS_NO_MEMORY;
@@ -493,7 +493,7 @@ NTSTATUS sldb_set(struct share_context *ctx, const char *name, struct share_info
 		olddn = msg->dn;
 
 		/* TODO: escape newname */
-		newdn = ldb_dn_string_compose(tmp_ctx, ldb_dn_new(tmp_ctx), "CN=%s,CN=SHARES", newname);
+		newdn = ldb_dn_new_fmt(tmp_ctx, ldb, "CN=%s,CN=SHARES", newname);
 		if (!newdn) {
 			DEBUG(0,("ERROR: Out of memory!\n"));
 			ret = NT_STATUS_NO_MEMORY;
@@ -549,7 +549,7 @@ NTSTATUS sldb_remove(struct share_context *ctx, const char *name)
 
 	ldb = talloc_get_type(ctx->priv_data, struct ldb_context);
 
-	dn = ldb_dn_string_compose(tmp_ctx, ldb_dn_new(tmp_ctx), "CN=%s,CN=SHARES", name);
+	dn = ldb_dn_new_fmt(tmp_ctx, ldb, "CN=%s,CN=SHARES", name);
 	if (!dn) {
 		DEBUG(0,("ERROR: Out of memory!\n"));
 		ret = NT_STATUS_NO_MEMORY;
diff --git a/source4/rpc_server/drsuapi/dcesrv_drsuapi.c b/source4/rpc_server/drsuapi/dcesrv_drsuapi.c
index e101195d9c..b7a5b2d242 100644
--- a/source4/rpc_server/drsuapi/dcesrv_drsuapi.c
+++ b/source4/rpc_server/drsuapi/dcesrv_drsuapi.c
@@ -280,8 +280,8 @@ static WERROR drsuapi_DsWriteAccountSpn(struct dcesrv_call_state *dce_call, TALL
 				return WERR_NOMEM;
 			}
 
-			msg->dn = ldb_dn_explode(msg, req->object_dn);
-			if (msg->dn == NULL) {
+			msg->dn = ldb_dn_new(msg, b_state->sam_ctx, req->object_dn);
+			if ( ! ldb_dn_validate(msg->dn)) {
 				r->out.res.res1.status = WERR_OK;
 				return WERR_OK;
 			}
diff --git a/source4/rpc_server/lsa/dcesrv_lsa.c b/source4/rpc_server/lsa/dcesrv_lsa.c
index 6dce61506d..af67835d03 100644
--- a/source4/rpc_server/lsa/dcesrv_lsa.c
+++ b/source4/rpc_server/lsa/dcesrv_lsa.c
@@ -52,9 +52,9 @@ struct lsa_policy_state {
 	struct ldb_context *sam_ldb;
 	struct sidmap_context *sidmap;
 	uint32_t access_mask;
-	const struct ldb_dn *domain_dn;
-	const struct ldb_dn *builtin_dn;
-	const struct ldb_dn *system_dn;
+	struct ldb_dn *domain_dn;
+	struct ldb_dn *builtin_dn;
+	struct ldb_dn *system_dn;
 	const char *domain_name;
 	const char *domain_dns;
 	struct dom_sid *domain_sid;
@@ -91,7 +91,7 @@ struct lsa_secret_state {
 struct lsa_trusted_domain_state {
 	struct lsa_policy_state *policy;
 	uint32_t access_mask;
-	const struct ldb_dn *trusted_domain_dn;
+	struct ldb_dn *trusted_domain_dn;
 };
 
 static NTSTATUS lsa_EnumAccountRights(struct dcesrv_call_state *dce_call, 
@@ -271,7 +271,7 @@ static NTSTATUS lsa_get_policy_state(struct dcesrv_call_state *dce_call, TALLOC_
 				     struct lsa_policy_state **_state)
 {
 	struct lsa_policy_state *state;
-	const struct ldb_dn *partitions_basedn;
+	struct ldb_dn *partitions_basedn;
 	struct ldb_result *dom_res;
 	const char *dom_attrs[] = {
 		"objectSid", 
@@ -833,10 +833,8 @@ static NTSTATUS lsa_CreateTrustedDomain(struct dcesrv_call_state *dce_call, TALL
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
 	
-	msg->dn = ldb_dn_build_child(mem_ctx, "cn",
-				     r->in.info->name.string, 
-				     policy_state->system_dn);
-	if (!msg->dn) {
+	msg->dn = ldb_dn_copy(mem_ctx, policy_state->system_dn);
+	if ( ! ldb_dn_add_child_fmt(msg->dn, "sn=%s", r->in.info->name.string)) {
 		return NT_STATUS_NO_MEMORY;
 	}
 	
@@ -2218,8 +2216,8 @@ static NTSTATUS lsa_CreateSecret(struct dcesrv_call_state *dce_call, TALLOC_CTX
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 
-		msg->dn = ldb_dn_build_child(mem_ctx, "cn", name2, policy_state->system_dn);
-		if (!name2 || !msg->dn) {
+		msg->dn = ldb_dn_copy(mem_ctx, policy_state->system_dn);
+		if (!name2 || ! ldb_dn_add_child_fmt(msg->dn, "cn=%s", name2)) {
 			return NT_STATUS_NO_MEMORY;
 		}
 		
@@ -2236,7 +2234,7 @@ 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,
-				   ldb_dn_explode(mem_ctx, "cn=LSA Secrets"),
+				   ldb_dn_new(mem_ctx, secret_state->sam_ldb, "cn=LSA Secrets"),
 				   &msgs, attrs,
 				   "(&(cn=%s)(objectclass=secret))", 
 				   ldb_binary_encode_string(mem_ctx, name));
@@ -2250,7 +2248,7 @@ static NTSTATUS lsa_CreateSecret(struct dcesrv_call_state *dce_call, TALLOC_CTX
 			return NT_STATUS_INTERNAL_DB_CORRUPTION;
 		}
 
-		msg->dn = ldb_dn_string_compose(mem_ctx, NULL, "cn=%s,cn=LSA Secrets", name);
+		msg->dn = ldb_dn_new_fmt(mem_ctx, secret_state->sam_ldb, "cn=%s,cn=LSA Secrets", name);
 		samdb_msg_add_string(secret_state->sam_ldb, mem_ctx, msg, "cn", name);
 	} 
 
@@ -2361,7 +2359,7 @@ 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,
-				   ldb_dn_explode(mem_ctx, "cn=LSA Secrets"),
+				   ldb_dn_new(mem_ctx, secret_state->sam_ldb, "cn=LSA Secrets"),
 				   &msgs, attrs,
 				   "(&(cn=%s)(objectclass=secret))", 
 				   ldb_binary_encode_string(mem_ctx, name));
diff --git a/source4/rpc_server/netlogon/dcerpc_netlogon.c b/source4/rpc_server/netlogon/dcerpc_netlogon.c
index bd8b289ae5..9b43d1c70f 100644
--- a/source4/rpc_server/netlogon/dcerpc_netlogon.c
+++ b/source4/rpc_server/netlogon/dcerpc_netlogon.c
@@ -874,7 +874,7 @@ static NTSTATUS netr_LogonGetDomainInfo(struct dcesrv_call_state *dce_call, TALL
 	struct netr_DomainInfo1 *info1;
 	int ret, ret1, ret2, i;
 	NTSTATUS status;
-	const struct ldb_dn *partitions_basedn;
+	struct ldb_dn *partitions_basedn;
 
 	const char *local_domain;
 
@@ -1130,7 +1130,7 @@ static WERROR netr_DsrEnumerateDomainTrusts(struct dcesrv_call_state *dce_call,
 	struct ldb_message **dom_res, **ref_res;
 	const char * const dom_attrs[] = { "objectSid", "objectGUID", NULL };
 	const char * const ref_attrs[] = { "nETBIOSName", "dnsRoot", NULL };
-	const struct ldb_dn *partitions_basedn;
+	struct ldb_dn *partitions_basedn;
 
 	ZERO_STRUCT(r->out);
 
diff --git a/source4/rpc_server/samr/dcesrv_samr.c b/source4/rpc_server/samr/dcesrv_samr.c
index b03c3789e7..3e8650eb55 100644
--- a/source4/rpc_server/samr/dcesrv_samr.c
+++ b/source4/rpc_server/samr/dcesrv_samr.c
@@ -225,7 +225,7 @@ static NTSTATUS samr_LookupDomain(struct dcesrv_call_state *dce_call, TALLOC_CTX
 	struct ldb_message **dom_msgs;
 	struct ldb_message **ref_msgs;
 	int ret;
-	const struct ldb_dn *partitions_basedn;
+	struct ldb_dn *partitions_basedn;
 
 	r->out.sid = NULL;
 
@@ -253,7 +253,7 @@ static NTSTATUS samr_LookupDomain(struct dcesrv_call_state *dce_call, TALLOC_CTX
 		}
 		
 		ret = gendb_search_dn(c_state->sam_ctx, mem_ctx, 
-				      samdb_result_dn(mem_ctx,
+				      samdb_result_dn(c_state->sam_ctx, mem_ctx,
 						      ref_msgs[0], "ncName", NULL), 
 				      &dom_msgs, dom_attrs);
 	}
@@ -291,7 +291,7 @@ static NTSTATUS samr_EnumDomains(struct dcesrv_call_state *dce_call, TALLOC_CTX
 	const char * const ref_attrs[] = { "nETBIOSName", NULL};
 	struct ldb_message **dom_msgs;
 	struct ldb_message **ref_msgs;
-	const struct ldb_dn *partitions_basedn;
+	struct ldb_dn *partitions_basedn;
 
 	*r->out.resume_handle = 0;
 	r->out.sam = NULL;
@@ -371,7 +371,7 @@ static NTSTATUS samr_OpenDomain(struct dcesrv_call_state *dce_call, TALLOC_CTX *
 	struct ldb_message **dom_msgs;
 	struct ldb_message **ref_msgs;
 	int ret;
-	const struct ldb_dn *partitions_basedn;
+	struct ldb_dn *partitions_basedn;
 
 	ZERO_STRUCTP(r->out.domain_handle);
 
@@ -934,8 +934,8 @@ static NTSTATUS samr_CreateDomainGroup(struct dcesrv_call_state *dce_call, TALLO
 	}
 
 	/* add core elements to the ldb_message for the user */
-	msg->dn = ldb_dn_string_compose(mem_ctx, d_state->domain_dn,
-					"CN=%s,CN=Users", groupname);
+	msg->dn = ldb_dn_copy(mem_ctx, d_state->domain_dn);
+	ldb_dn_add_child_fmt(msg->dn, "CN=%s,CN=Users", groupname);
 	if (!msg->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -1197,11 +1197,12 @@ static NTSTATUS samr_CreateUser2(struct dcesrv_call_state *dce_call, TALLOC_CTX
 	}
 
 	/* add core elements to the ldb_message for the user */
-	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) {
+	msg->dn = ldb_dn_copy(mem_ctx, d_state->domain_dn);
+	if ( ! ldb_dn_add_child_fmt(msg->dn, "CN=%s,CN=%s", cn_name, container)) {
 		ldb_transaction_cancel(d_state->sam_ctx);
-		return NT_STATUS_NO_MEMORY;		
+		return NT_STATUS_FOOBAR;
 	}
+
 	samdb_msg_add_string(d_state->sam_ctx, mem_ctx, msg, "sAMAccountName", account_name);
 	samdb_msg_add_string(d_state->sam_ctx, mem_ctx, msg, "objectClass", obj_class);
 	
@@ -1215,13 +1216,13 @@ static NTSTATUS samr_CreateUser2(struct dcesrv_call_state *dce_call, TALLOC_CTX
 	case  LDB_ERR_ENTRY_ALREADY_EXISTS:
 		ldb_transaction_cancel(d_state->sam_ctx);
 		DEBUG(0,("Failed to create user record %s: %s\n",
-			 ldb_dn_linearize(mem_ctx, msg->dn),
+			 ldb_dn_get_linearized(msg->dn),
 			 ldb_errstring(d_state->sam_ctx)));
 		return NT_STATUS_USER_EXISTS;
 	default:
 		ldb_transaction_cancel(d_state->sam_ctx);
 		DEBUG(0,("Failed to create user record %s: %s\n",
-			 ldb_dn_linearize(mem_ctx, msg->dn),
+			 ldb_dn_get_linearized(msg->dn),
 			 ldb_errstring(d_state->sam_ctx)));
 		return NT_STATUS_INTERNAL_DB_CORRUPTION;
 	}
@@ -1464,8 +1465,8 @@ static NTSTATUS samr_CreateDomAlias(struct dcesrv_call_state *dce_call, TALLOC_C
 	}
 
 	/* add core elements to the ldb_message for the alias */
-	msg->dn = ldb_dn_string_compose(mem_ctx, d_state->domain_dn,
-					"CN=%s, CN=Users", alias_name);
+	msg->dn = ldb_dn_copy(mem_ctx, d_state->domain_dn);
+	ldb_dn_add_child_fmt(msg->dn, "CN=%s,CN=Users", alias_name);
 	if (!msg->dn) {
 		return NT_STATUS_NO_MEMORY;
 	}
@@ -2288,7 +2289,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,
-					   ldb_dn_explode(mem_ctx, (const char *)el->values[i].data),
+					   ldb_dn_new(mem_ctx, a_state->sam_ctx, (const char *)el->values[i].data),
 					   &res2, attrs2);
 			if (ret != 1)
 				return NT_STATUS_INTERNAL_DB_CORRUPTION;
@@ -2682,7 +2683,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,
-					   ldb_dn_explode(mem_ctx, (const char *)el->values[i].data),
+					   ldb_dn_new(mem_ctx, a_state->sam_ctx, (const char *)el->values[i].data),
 					   &msgs2, attrs2);
 			if (ret != 1)
 				return NT_STATUS_INTERNAL_DB_CORRUPTION;
@@ -3782,7 +3783,7 @@ static NTSTATUS samr_RemoveMemberFromForeignDomain(struct dcesrv_call_state *dce
 			return NT_STATUS_NO_MEMORY;
 		}
 
-		mod->dn = samdb_result_dn(mod, res[i], "distinguishedName", NULL);
+		mod->dn = samdb_result_dn(d_state->sam_ctx, mod, res[i], "distinguishedName", 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 8e53fa7a10..bebc60e0e7 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 struct ldb_dn *domain_dn;
+	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 struct ldb_dn *account_dn;
+	struct ldb_dn *account_dn;
 };
diff --git a/source4/rpc_server/samr/samr_password.c b/source4/rpc_server/samr/samr_password.c
index a62e768980..3d15a29735 100644
--- a/source4/rpc_server/samr/samr_password.c
+++ b/source4/rpc_server/samr/samr_password.c
@@ -187,7 +187,7 @@ NTSTATUS samr_OemChangePasswordUser2(struct dcesrv_call_state *dce_call, TALLOC_
 	uint32_t new_pass_len;
 	struct samr_CryptPassword *pwbuf = r->in.password;
 	struct ldb_context *sam_ctx;
-	const struct ldb_dn *user_dn;
+	struct ldb_dn *user_dn;
 	int ret;
 	struct ldb_message **res, *mod;
 	const char * const attrs[] = { "objectSid", "lmPwdHash", NULL };
@@ -320,7 +320,7 @@ NTSTATUS samr_ChangePasswordUser3(struct dcesrv_call_state *dce_call,
 	char new_pass[512];
 	uint32_t new_pass_len;
 	struct ldb_context *sam_ctx = NULL;
-	const struct ldb_dn *user_dn;
+	struct ldb_dn *user_dn;
 	int ret;
 	struct ldb_message **res, *mod;
 	const char * const attrs[] = { "ntPwdHash", "lmPwdHash", NULL };
@@ -510,7 +510,7 @@ NTSTATUS samr_ChangePasswordUser2(struct dcesrv_call_state *dce_call, TALLOC_CTX
 */
 NTSTATUS samr_set_password(struct dcesrv_call_state *dce_call,
 			   void *sam_ctx,
-			   const struct ldb_dn *account_dn, const struct ldb_dn *domain_dn,
+			   struct ldb_dn *account_dn, struct ldb_dn *domain_dn,
 			   TALLOC_CTX *mem_ctx,
 			   struct ldb_message *msg, 
 			   struct samr_CryptPassword *pwbuf)
@@ -552,7 +552,7 @@ NTSTATUS samr_set_password(struct dcesrv_call_state *dce_call,
 */
 NTSTATUS samr_set_password_ex(struct dcesrv_call_state *dce_call,
 			      struct ldb_context *sam_ctx,
-			      const struct ldb_dn *account_dn, const struct ldb_dn *domain_dn,
+			      struct ldb_dn *account_dn, struct ldb_dn *domain_dn,
 			      TALLOC_CTX *mem_ctx,
 			      struct ldb_message *msg, 
 			      struct samr_CryptPasswordEx *pwbuf)
diff --git a/source4/scripting/ejs/smbcalls_ldb.c b/source4/scripting/ejs/smbcalls_ldb.c
index 0af9738b60..3c368bba4f 100644
--- a/source4/scripting/ejs/smbcalls_ldb.c
+++ b/source4/scripting/ejs/smbcalls_ldb.c
@@ -83,8 +83,8 @@ static int ejs_ldbSearch(MprVarHandle eid, int argc, struct MprVar **argv)
 		/* a null basedn is valid */
 	}
 	if (base != NULL) {
-		basedn = ldb_dn_explode(tmp_ctx, base);
-		if (basedn == NULL) {
+		basedn = ldb_dn_new(tmp_ctx, ldb, base);
+		if ( ! ldb_dn_validate(basedn)) {
 			ejsSetErrorMsg(eid, "ldb.search malformed base dn");
 			goto failed;
 		}
@@ -187,8 +187,8 @@ static int ejs_ldbDelete(MprVarHandle eid, int argc, struct MprVar **argv)
 		return -1;
 	}
 
-	dn = ldb_dn_explode(ldb, mprToString(argv[0]));
-	if (dn == NULL) {
+	dn = ldb_dn_new(ldb, ldb, mprToString(argv[0]));
+	if ( ! ldb_dn_validate(dn)) {
 		ejsSetErrorMsg(eid, "ldb.delete malformed dn");
 		return -1;
 	}
@@ -222,9 +222,9 @@ static int ejs_ldbRename(MprVarHandle eid, int argc, struct MprVar **argv)
 		return -1;
 	}
 
-	dn1 = ldb_dn_explode(ldb, mprToString(argv[0]));
-	dn2 = ldb_dn_explode(ldb, mprToString(argv[1]));
-	if (dn1 == NULL || dn2 == NULL) {
+	dn1 = ldb_dn_new(ldb, ldb, mprToString(argv[0]));
+	dn2 = ldb_dn_new(ldb, ldb, mprToString(argv[1]));
+	if ( ! ldb_dn_validate(dn1) ||  ! ldb_dn_validate(dn2)) {
 		ejsSetErrorMsg(eid, "ldb.rename invalid or malformed arguments");
 		return -1;
 	}
diff --git a/source4/torture/ldap/cldap.c b/source4/torture/ldap/cldap.c
index 05f9787191..fb2037f75e 100644
--- a/source4/torture/ldap/cldap.c
+++ b/source4/torture/ldap/cldap.c
@@ -167,12 +167,12 @@ done:
   use the convenient ldif dump routines in ldb to print out cldap
   search results
 */
-static struct ldb_message *ldap_msg_to_ldb(TALLOC_CTX *mem_ctx, struct ldap_SearchResEntry *res)
+static struct ldb_message *ldap_msg_to_ldb(TALLOC_CTX *mem_ctx, struct ldb_context *ldb, struct ldap_SearchResEntry *res)
 {
 	struct ldb_message *msg;
 
 	msg = ldb_msg_new(mem_ctx);
-	msg->dn = ldb_dn_explode_or_special(msg, res->dn);
+	msg->dn = ldb_dn_new(msg, ldb, res->dn);
 	msg->num_elements = res->num_attributes;
 	msg->elements = talloc_steal(msg, res->attributes);
 	return msg;
@@ -194,7 +194,7 @@ static void cldap_dump_results(struct cldap_search *search)
 	ldb = ldb_init(NULL);
 
 	ZERO_STRUCT(ldif);
-	ldif.msg = ldap_msg_to_ldb(ldb, search->out.response);
+	ldif.msg = ldap_msg_to_ldb(ldb, ldb, search->out.response);
 
 	ldb_ldif_write_file(ldb, stdout, &ldif);
 
diff --git a/source4/torture/ldap/schema.c b/source4/torture/ldap/schema.c
index bc8f1e38ce..2ab0c5e116 100644
--- a/source4/torture/ldap/schema.c
+++ b/source4/torture/ldap/schema.c
@@ -119,7 +119,7 @@ static BOOL test_search_rootDSE(struct ldb_context *ldb, struct test_rootDSE *ro
 
 	d_printf("Testing RootDSE Search\n");
 
-	ret = ldb_search(ldb, ldb_dn_new(ldb), LDB_SCOPE_BASE, 
+	ret = ldb_search(ldb, ldb_dn_new(ldb, ldb, NULL), LDB_SCOPE_BASE, 
 			 NULL, NULL, &r);
 	if (ret != LDB_SUCCESS) {
 		return False;
@@ -226,7 +226,7 @@ static BOOL test_create_schema_type(struct ldb_context *ldb, struct test_rootDSE
 	ctrl[1] = NULL;
 
 	req->operation = LDB_SEARCH;
-	req->op.search.base = ldb_dn_explode(req, root->schemadn);
+	req->op.search.base = ldb_dn_new(req, ldb, root->schemadn);
 	req->op.search.scope = LDB_SCOPE_SUBTREE;
 	req->op.search.tree = ldb_parse_tree(req, filter);
 	if (req->op.search.tree == NULL) return -1;
diff --git a/source4/torture/local/dbspeed.c b/source4/torture/local/dbspeed.c
index 555f02588c..2d521394ce 100644
--- a/source4/torture/local/dbspeed.c
+++ b/source4/torture/local/dbspeed.c
@@ -133,8 +133,7 @@ static BOOL ldb_add_record(struct ldb_context *ldb, unsigned rid)
 		return False;
 	}
 
-	msg->dn = ldb_dn_string_compose(msg, NULL, "SID=S-1-5-21-53173311-3623041448-2049097239-%u", 
-					rid);
+	msg->dn = ldb_dn_new_fmt(msg, ldb, "SID=S-1-5-21-53173311-3623041448-2049097239-%u", rid);
 	if (msg->dn == NULL) {
 		return False;
 	}
@@ -206,25 +205,20 @@ static BOOL test_ldb_speed(struct torture_context *torture, const void *_data)
 		char *expr;
 
 		i = random() % torture_entries;
-		dn = ldb_dn_string_compose(tmp_ctx, NULL, "SID=S-1-5-21-53173311-3623041448-2049097239-%u", 
-					i);
-		if (ldb_search(ldb, dn, LDB_SCOPE_BASE, NULL, NULL, &res) != LDB_SUCCESS ||
-		    res->count != 1) {
-			torture_fail(torture, talloc_asprintf(torture,
-												  "Failed to find SID %d\n", i));
+		dn = ldb_dn_new_fmt(tmp_ctx, ldb, "SID=S-1-5-21-53173311-3623041448-2049097239-%u", i);
+		if (ldb_search(ldb, dn, LDB_SCOPE_BASE, NULL, NULL, &res) != LDB_SUCCESS || res->count != 1) {
+			torture_fail(torture, talloc_asprintf(torture, "Failed to find SID %d\n", i));
 		}
 		talloc_free(res);
 		talloc_free(dn);
 		expr = talloc_asprintf(tmp_ctx, "(UID=%u)", i);
-		if (ldb_search(ldb, NULL, LDB_SCOPE_SUBTREE, expr, NULL, &res) != LDB_SUCCESS ||
-		    res->count != 1) {
-			torture_fail(torture, talloc_asprintf(torture, 
-												  "Failed to find UID %d\n", i));
+		if (ldb_search(ldb, NULL, LDB_SCOPE_SUBTREE, expr, NULL, &res) != LDB_SUCCESS || res->count != 1) {
+			torture_fail(torture, talloc_asprintf(torture, "Failed to find UID %d\n", i));
 		}
 		talloc_free(res);
 		talloc_free(expr);
 	}
-	
+
 	if (talloc_total_blocks(torture) > 100) {
 		torture_fail(torture, "memory leak in ldb search\n");
 		goto failed;
diff --git a/source4/torture/rpc/drsuapi_cracknames.c b/source4/torture/rpc/drsuapi_cracknames.c
index e6ff33d58d..adf14461c0 100644
--- a/source4/torture/rpc/drsuapi_cracknames.c
+++ b/source4/torture/rpc/drsuapi_cracknames.c
@@ -211,6 +211,7 @@ BOOL test_DsCrackNames(struct dcerpc_pipe *p, TALLOC_CTX *mem_ctx,
 	const char *dns_domain;
 	const char *nt4_domain;
 	const char *FQDN_1779_name;
+	struct ldb_context *ldb;
 	struct ldb_dn *FQDN_1779_dn;
 	struct ldb_dn *realm_dn;
 	const char *realm_dn_str;
@@ -318,9 +319,11 @@ BOOL test_DsCrackNames(struct dcerpc_pipe *p, TALLOC_CTX *mem_ctx,
 	if (!ret) {
 		return ret;
 	}
+
+	ldb = ldb_init(mem_ctx);
 	
 	realm_dn_str = r.out.ctr.ctr1->array[0].result_name;
-	realm_dn =  ldb_dn_explode(mem_ctx, realm_dn_str);
+	realm_dn =  ldb_dn_new(mem_ctx, ldb, realm_dn_str);
 	realm_canonical = ldb_dn_canonical_string(mem_ctx, realm_dn);
 
 	if (strcmp(realm_canonical, 
@@ -399,7 +402,7 @@ BOOL test_DsCrackNames(struct dcerpc_pipe *p, TALLOC_CTX *mem_ctx,
 
 	FQDN_1779_name = r.out.ctr.ctr1->array[0].result_name;
 
-	FQDN_1779_dn = ldb_dn_explode(mem_ctx, FQDN_1779_name);
+	FQDN_1779_dn = ldb_dn_new(mem_ctx, ldb, FQDN_1779_name);
 
 	canonical_name = ldb_dn_canonical_string(mem_ctx, FQDN_1779_dn);
 	canonical_ex_name = ldb_dn_canonical_ex_string(mem_ctx, FQDN_1779_dn);
diff --git a/source4/torture/rpc/testjoin.c b/source4/torture/rpc/testjoin.c
index d325f10cee..c9507287e8 100644
--- a/source4/torture/rpc/testjoin.c
+++ b/source4/torture/rpc/testjoin.c
@@ -424,8 +424,8 @@ NTSTATUS torture_leave_ads_domain(TALLOC_CTX *mem_ctx, struct libnet_JoinDomain
 	}
 
 	/* Remove CN=Servers,... entry from the AD. */ 
-	server_dn = ldb_dn_explode(tmp_ctx, libnet_r->out.server_dn_str);
-	if (!server_dn) {
+	server_dn = ldb_dn_new(tmp_ctx, ldb_ctx, libnet_r->out.server_dn_str);
+	if (! ldb_dn_validate(server_dn)) {
 		libnet_r->out.error_string = NULL;
 		talloc_free(tmp_ctx);
 		return NT_STATUS_NO_MEMORY;
diff --git a/source4/wrepl_server/wrepl_server.c b/source4/wrepl_server/wrepl_server.c
index 55ab76c228..bc24ae1abd 100644
--- a/source4/wrepl_server/wrepl_server.c
+++ b/source4/wrepl_server/wrepl_server.c
@@ -47,7 +47,7 @@ static uint64_t wins_config_db_get_seqnumber(struct ldb_context *ldb)
 	TALLOC_CTX *tmp_ctx = talloc_new(ldb);
 	uint64_t seqnumber = 0;
 
-	dn = ldb_dn_explode(tmp_ctx, "@BASEINFO");
+	dn = ldb_dn_new(tmp_ctx, ldb, "@BASEINFO");
 	if (!dn) goto failed;
 
 	/* find the record in the WINS database */
@@ -141,7 +141,7 @@ NTSTATUS wreplsrv_load_partners(struct wreplsrv_service *service)
 	service->config.seqnumber = new_seqnumber;
 
 	/* find the record in the WINS database */
-	ret = ldb_search(service->config.ldb, ldb_dn_explode(tmp_ctx, "CN=PARTNERS"), LDB_SCOPE_SUBTREE,
+	ret = ldb_search(service->config.ldb, ldb_dn_new(tmp_ctx, service->config.ldb, "CN=PARTNERS"), LDB_SCOPE_SUBTREE,
 			 "(objectClass=wreplPartner)", NULL, &res);
 	if (ret != LDB_SUCCESS) goto failed;
 	talloc_steal(tmp_ctx, res);