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)

7 files changed, 962 insertions, 621 deletions

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;
 }
 
 /*