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)

36 files changed, 1227 insertions, 795 deletions

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) {