r18781: Move the usnCreated and usnChanged handling around again.

This moves these attributes from objectguid into an optional backend
(objectguid), used by ltdb.  For OpenLDAP, the entryUUID module
converts entryCSN into usnChanged.

This also changes the sequence number API, and uses 'time based'
sequence numbers, when an LDAP or similar backend is detected.

To assist this, we also store the last modified time in the TDB,
whenever we change a value.

Andrew Bartlett
(This used to be commit 72858f859483c0c532dddb2c146d6bd7b9be5072)

4 files changed, 396 insertions, 18 deletions

diff --git a/source4/dsdb/samdb/ldb_modules/entryUUID.c b/source4/dsdb/samdb/ldb_modules/entryUUID.c
index ebe78f9fc4a..04beac7a948 100644
--- a/source4/dsdb/samdb/ldb_modules/entryUUID.c
+++ b/source4/dsdb/samdb/ldb_modules/entryUUID.c
@@ -38,6 +38,7 @@
 
 struct entryUUID_private {
 	struct ldb_result *objectclass_res;	
+	struct ldb_dn **base_dns;
 };
 
 static struct ldb_val encode_guid(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
@@ -188,6 +189,80 @@ static struct ldb_val normalise_to_signed32(struct ldb_module *module, TALLOC_CT
 	return val_copy(module, ctx, val);
 }
 
+static struct ldb_val usn_to_entryCSN(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+{
+	struct ldb_val out;
+	unsigned long long usn = strtoull(val->data, NULL, 10);
+	time_t t = (usn >> 24);
+	out = data_blob_string_const(talloc_asprintf(ctx, "%s#%06x#00#000000", ldb_timestring(ctx, t), (unsigned int)(usn & 0xFFFFFF)));
+	return out;
+}
+
+static unsigned long long entryCSN_to_usn_int(TALLOC_CTX *ctx, const struct ldb_val *val) 
+{
+	char *entryCSN = talloc_strdup(ctx, val->data);
+	char *mod_per_sec;
+	time_t t;
+	unsigned long long usn;
+	char *p;
+	if (!entryCSN) {
+		return 0;
+	}
+	p = strchr(entryCSN, '#');
+	if (!p) {
+		return 0;
+	}
+	p[0] = '\0';
+	p++;
+	mod_per_sec = p;
+
+	p = strchr(p, '#');
+	if (!p) {
+		return 0;
+	}
+	p[0] = '\0';
+	p++;
+
+	usn = strtol(mod_per_sec, NULL, 16);
+
+	t = ldb_string_to_time(entryCSN);
+	
+	usn = usn | ((unsigned long long)t <<24);
+	return usn;
+}
+
+static struct ldb_val entryCSN_to_usn(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+{
+	struct ldb_val out;
+	unsigned long long usn = entryCSN_to_usn_int(ctx, val);
+	out = data_blob_string_const(talloc_asprintf(ctx, "%lld", usn));
+	return out;
+}
+
+static struct ldb_val usn_to_timestamp(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+{
+	struct ldb_val out;
+	unsigned long long usn = strtoull(val->data, NULL, 10);
+	time_t t = (usn >> 24);
+	out = data_blob_string_const(ldb_timestring(ctx, t));
+	return out;
+}
+
+static struct ldb_val timestamp_to_usn(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
+{
+	struct ldb_val out;
+	time_t t;
+	unsigned long long usn;
+
+	t = ldb_string_to_time(val->data);
+	
+	usn = ((unsigned long long)t <<24);
+
+	out = data_blob_string_const(talloc_asprintf(ctx, "%lld", usn));
+	return out;
+}
+
+
 const struct ldb_map_attribute entryUUID_attributes[] = 
 {
 	/* objectGUID */
@@ -295,6 +370,28 @@ const struct ldb_map_attribute entryUUID_attributes[] =
 		}
 	},
 	{
+		.local_name = "usnChanged",
+		.type = MAP_CONVERT,
+		.u = {
+			.convert = {
+				 .remote_name = "entryCSN",
+				 .convert_local = usn_to_entryCSN,
+				 .convert_remote = entryCSN_to_usn
+			 },
+		},
+	},
+	{
+		.local_name = "usnCreated",
+		.type = MAP_CONVERT,
+		.u = {
+			.convert = {
+				 .remote_name = "createTimestamp",
+				 .convert_local = usn_to_timestamp,
+				 .convert_remote = timestamp_to_usn,
+			 },
+		},
+	},
+	{
 		.local_name = "*",
 		.type = MAP_KEEP,
 	},
@@ -309,6 +406,8 @@ const char * const wildcard_attributes[] = {
 	"objectGUID", 
 	"whenCreated", 
 	"whenChanged",
+	"usnCreated",
+	"usnChanged",
 	NULL
 };
 
@@ -373,6 +472,75 @@ static int fetch_objectclass_schema(struct ldb_context *ldb, struct ldb_dn *sche
 	return ret;
 }
 
+
+static int get_remote_rootdse(struct ldb_context *ldb, void *context, 
+		       struct ldb_reply *ares) 
+{
+	struct entryUUID_private *entryUUID_private;
+	entryUUID_private = talloc_get_type(context,
+					    struct entryUUID_private);
+	if (ares->type == LDB_REPLY_ENTRY) {
+		int i;
+		struct ldb_message_element *el = ldb_msg_find_element(ares->message, "namingContexts");
+		entryUUID_private->base_dns = talloc_realloc(entryUUID_private, entryUUID_private->base_dns, struct ldb_dn *, 
+							     el->num_values + 1);
+		for (i=0; i < el->num_values; i++) {
+			if (!entryUUID_private->base_dns) {
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			entryUUID_private->base_dns[i] = ldb_dn_explode(entryUUID_private->base_dns, (const char *)el->values[i].data);
+			if (!entryUUID_private->base_dns[i]) {
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+		}
+		entryUUID_private->base_dns[i] = NULL;
+	}
+}
+
+static int find_base_dns(struct ldb_module *module, 
+			  struct entryUUID_private *entryUUID_private) 
+{
+	int ret;
+	struct ldb_request *req;
+	const char *naming_context_attr[] = {
+		"namingContexts",
+		NULL
+	};
+	req = talloc(module, struct ldb_request);
+	if (req == NULL) {
+		ldb_set_errstring(module->ldb, "Out of Memory");
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	req->operation = LDB_SEARCH;
+	req->op.search.base = ldb_dn_new(req);
+	req->op.search.scope = LDB_SCOPE_BASE;
+
+	req->op.search.tree = ldb_parse_tree(req, "objectClass=*");
+	if (req->op.search.tree == NULL) {
+		ldb_set_errstring(module->ldb, "Unable to parse search expression");
+		talloc_free(req);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	req->op.search.attrs = naming_context_attr;
+	req->controls = NULL;
+	req->context = entryUUID_private;
+	req->callback = get_remote_rootdse;
+	ldb_set_timeout(module->ldb, req, 0); /* use default timeout */
+
+	ret = ldb_next_request(module, req);
+	
+	if (ret == LDB_SUCCESS) {
+		ret = ldb_wait(req->handle, LDB_WAIT_ALL);
+	}
+	
+	talloc_free(req);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+}
+
 /* the context init function */
 static int entryUUID_init(struct ldb_module *module)
 {
@@ -402,13 +570,104 @@ static int entryUUID_init(struct ldb_module *module)
 		ldb_asprintf_errstring(module->ldb, "Failed to fetch objectClass schema elements: %s\n", ldb_errstring(module->ldb));
 		return ret;
 	}	
-	
+
+	ret = find_base_dns(module, entryUUID_private);
+
 	return ldb_next_init(module);
 }
 
+static int get_seq(struct ldb_context *ldb, void *context, 
+		   struct ldb_reply *ares) 
+{
+	unsigned long long *max_seq = context;
+	unsigned long long seq;
+	if (ares->type == LDB_REPLY_ENTRY) {
+		struct ldb_message_element *el = ldb_msg_find_element(ares->message, "contextCSN");
+		if (el) {
+			seq = entryCSN_to_usn_int(ares, &el->values[0]);
+			*max_seq = MAX(seq, *max_seq);
+		}
+	}
+}
+
+static int entryUUID_sequence_number(struct ldb_module *module, struct ldb_request *req)
+{
+	int i, ret;
+	struct map_private *map_private;
+	struct entryUUID_private *entryUUID_private;
+	unsigned long long max_seq = 0;
+	struct ldb_request *search_req;
+	map_private = talloc_get_type(module->private_data, struct map_private);
+
+	entryUUID_private = talloc_get_type(map_private->caller_private, struct entryUUID_private);
+
+	/* Search the baseDNs for a sequence number */
+	for (i=0; entryUUID_private && 
+		     entryUUID_private->base_dns && 
+		     entryUUID_private->base_dns[i];
+		i++) {
+		static const char *contextCSN_attr[] = {
+			"contextCSN", NULL
+		};
+		search_req = talloc(req, struct ldb_request);
+		if (search_req == NULL) {
+			ldb_set_errstring(module->ldb, "Out of Memory");
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		
+		search_req->operation = LDB_SEARCH;
+		search_req->op.search.base = entryUUID_private->base_dns[i];
+		search_req->op.search.scope = LDB_SCOPE_BASE;
+		
+		search_req->op.search.tree = ldb_parse_tree(search_req, "objectClass=*");
+		if (search_req->op.search.tree == NULL) {
+			ldb_set_errstring(module->ldb, "Unable to parse search expression");
+			talloc_free(search_req);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		
+		search_req->op.search.attrs = contextCSN_attr;
+		search_req->controls = NULL;
+		search_req->context = &max_seq;
+		search_req->callback = get_seq;
+		ldb_set_timeout(module->ldb, search_req, 0); /* use default timeout */
+		
+		ret = ldb_next_request(module, search_req);
+		
+		if (ret == LDB_SUCCESS) {
+			ret = ldb_wait(search_req->handle, LDB_WAIT_ALL);
+		}
+		
+		talloc_free(search_req);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+	}
+
+	switch (req->op.seq_num.type) {
+	case LDB_SEQ_HIGHEST_SEQ:
+		req->op.seq_num.seq_num = max_seq;
+		break;
+	case LDB_SEQ_NEXT:
+		req->op.seq_num.seq_num = max_seq;
+		req->op.seq_num.seq_num++;
+		break;
+	case LDB_SEQ_HIGHEST_TIMESTAMP:
+	{
+		req->op.seq_num.seq_num = (max_seq >> 24);
+		break;
+	}
+	}
+	req->op.seq_num.flags = 0;
+	req->op.seq_num.flags |= LDB_SEQ_TIMESTAMP_SEQUENCE;
+	req->op.seq_num.flags |= LDB_SEQ_GLOBAL_SEQUENCE;
+	return LDB_SUCCESS;
+}
+
 static struct ldb_module_ops entryUUID_ops = {
 	.name		   = "entryUUID",
 	.init_context	   = entryUUID_init,
+	.sequence_number   = entryUUID_sequence_number
 };
 
 /* the init function */
@@ -421,6 +680,5 @@ int ldb_entryUUID_module_init(void)
 	entryUUID_ops.rename	= ops.rename;
 	entryUUID_ops.search	= ops.search;
 	entryUUID_ops.wait	= ops.wait;
-
 	return ldb_register_module(&entryUUID_ops);
 }
diff --git a/source4/dsdb/samdb/ldb_modules/objectguid.c b/source4/dsdb/samdb/ldb_modules/objectguid.c
index 7e475d1ef44..0c4a493adb9 100644
--- a/source4/dsdb/samdb/ldb_modules/objectguid.c
+++ b/source4/dsdb/samdb/ldb_modules/objectguid.c
@@ -3,6 +3,7 @@
 
    Copyright (C) Simo Sorce  2004-2006
    Copyright (C) Andrew Bartlett <abartlet@samba.org> 2005
+   Copyright (C) Andrew Tridgell 2005
 
      ** NOTE! The following LGPL license applies to the ldb
      ** library. This does NOT imply that all of Samba is released
@@ -79,6 +80,29 @@ static int add_time_element(struct ldb_message *msg, const char *attr, time_t t)
 	return 0;
 }
 
+/*
+  add a uint64_t element to a record
+*/
+static int add_uint64_element(struct ldb_message *msg, const char *attr, uint64_t v)
+{
+	struct ldb_message_element *el;
+
+	if (ldb_msg_find_element(msg, attr) != NULL) {
+		return 0;
+	}
+
+	if (ldb_msg_add_fmt(msg, attr, "%llu", (unsigned long long)v) != 0) {
+		return -1;
+	}
+
+	el = ldb_msg_find_element(msg, attr);
+	/* always set as replace. This works because on add ops, the flag
+	   is ignored */
+	el->flags = LDB_FLAG_MOD_REPLACE;
+
+	return 0;
+}
+
 /* add_record: add objectGUID attribute */
 static int objectguid_add(struct ldb_module *module, struct ldb_request *req)
 {
@@ -87,6 +111,7 @@ static int objectguid_add(struct ldb_module *module, struct ldb_request *req)
 	struct ldb_message *msg;
 	struct ldb_val v;
 	struct GUID guid;
+	uint64_t seq_num;
 	NTSTATUS nt_status;
 	int ret;
 	time_t t = time(NULL);
@@ -138,6 +163,16 @@ static int objectguid_add(struct ldb_module *module, struct ldb_request *req)
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
+	/* Get a sequence number from the backend */
+	ret = ldb_sequence_number(module->ldb, LDB_SEQ_NEXT, &seq_num);
+	if (ret == LDB_SUCCESS) {
+		if (add_uint64_element(msg, "uSNCreated", seq_num) != 0 ||
+		    add_uint64_element(msg, "uSNChanged", seq_num) != 0) {
+			talloc_free(down_req);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+	}
+
 	ldb_set_timeout_from_prev_req(module->ldb, req, down_req);
 
 	/* go on with the call chain */
@@ -159,6 +194,7 @@ static int objectguid_modify(struct ldb_module *module, struct ldb_request *req)
 	struct ldb_message *msg;
 	int ret;
 	time_t t = time(NULL);
+	uint64_t seq_num;
 
 	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "objectguid_add_record\n");
 
@@ -186,6 +222,15 @@ static int objectguid_modify(struct ldb_module *module, struct ldb_request *req)
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
+	/* Get a sequence number from the backend */
+	ret = ldb_sequence_number(module->ldb, LDB_SEQ_NEXT, &seq_num);
+	if (ret == LDB_SUCCESS) {
+		if (add_uint64_element(msg, "uSNChanged", seq_num) != 0) {
+			talloc_free(down_req);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+	}
+
 	ldb_set_timeout_from_prev_req(module->ldb, req, down_req);
 
 	/* go on with the call chain */
diff --git a/source4/dsdb/samdb/ldb_modules/partition.c b/source4/dsdb/samdb/ldb_modules/partition.c
index bb085e0b11a..437e288be50 100644
--- a/source4/dsdb/samdb/ldb_modules/partition.c
+++ b/source4/dsdb/samdb/ldb_modules/partition.c
@@ -474,28 +474,103 @@ static int partition_sequence_number(struct ldb_module *module, struct ldb_reque
 {
 	int i, ret;
 	uint64_t seq_number = 0;
+	uint64_t timestamp_sequence = 0;
+	uint64_t timestamp = 0;
 	struct partition_private_data *data = talloc_get_type(module->private_data, 
 							      struct partition_private_data);
-	ret = ldb_next_request(module, req);
-	if (ret != LDB_SUCCESS) {
-		return ret;
-	}
-	seq_number = seq_number + req->op.seq_num.seq_num;
 
-	/* Look at base DN */
-	/* Figure out which partition it is under */
-	/* Skip the lot if 'data' isn't here yet (initialistion) */
-	for (i=0; data && data->partitions && data->partitions[i]; i++) {
-		struct ldb_module *next = make_module_for_next_request(req, module->ldb, data->partitions[i]->module);
-		
-		ret = ldb_next_request(next, req);
-		talloc_free(next);
+	switch (req->op.seq_num.type) {
+	case LDB_SEQ_NEXT:
+	case LDB_SEQ_HIGHEST_SEQ:
+	       	ret = ldb_next_request(module, req);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+		if (req->op.seq_num.flags & LDB_SEQ_TIMESTAMP_SEQUENCE) {
+			timestamp_sequence = req->op.seq_num.seq_num;
+		} else {
+			seq_number = seq_number + req->op.seq_num.seq_num;
+		}
+
+		/* Look at base DN */
+		/* Figure out which partition it is under */
+		/* Skip the lot if 'data' isn't here yet (initialistion) */
+		for (i=0; data && data->partitions && data->partitions[i]; i++) {
+			struct ldb_module *next = make_module_for_next_request(req, module->ldb, data->partitions[i]->module);
+			
+			ret = ldb_next_request(next, req);
+			talloc_free(next);
+			if (ret != LDB_SUCCESS) {
+				return ret;
+			}
+			if (req->op.seq_num.flags & LDB_SEQ_TIMESTAMP_SEQUENCE) {
+				timestamp_sequence = MAX(timestamp_sequence, req->op.seq_num.seq_num);
+			} else {
+				seq_number = seq_number + req->op.seq_num.seq_num;
+			}
+		}
+		/* fall though */
+	case LDB_SEQ_HIGHEST_TIMESTAMP:
+	{
+		struct ldb_request *date_req = talloc(req, struct ldb_request);
+		if (!date_req) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		*date_req = *req;
+		date_req->op.seq_num.flags = LDB_SEQ_HIGHEST_TIMESTAMP;
+
+		ret = ldb_next_request(module, date_req);
 		if (ret != LDB_SUCCESS) {
 			return ret;
 		}
-		seq_number = seq_number + req->op.seq_num.seq_num;
+		timestamp = date_req->op.seq_num.seq_num;
+		
+		/* Look at base DN */
+		/* Figure out which partition it is under */
+		/* Skip the lot if 'data' isn't here yet (initialistion) */
+		for (i=0; data && data->partitions && data->partitions[i]; i++) {
+			struct ldb_module *next = make_module_for_next_request(req, module->ldb, data->partitions[i]->module);
+			
+			ret = ldb_next_request(next, date_req);
+			talloc_free(next);
+			if (ret != LDB_SUCCESS) {
+				return ret;
+			}
+			timestamp = MAX(timestamp, date_req->op.seq_num.seq_num);
+		}
+		break;
+	}
+	}
+
+	switch (req->op.seq_num.flags) {
+	case LDB_SEQ_NEXT:
+	case LDB_SEQ_HIGHEST_SEQ:
+		
+		req->op.seq_num.flags = 0;
+
+		/* Has someone above set a timebase sequence? */
+		if (timestamp_sequence) {
+			req->op.seq_num.seq_num = (((unsigned long long)timestamp << 24) | (seq_number & 0xFFFFFF));
+		} else {
+			req->op.seq_num.seq_num = seq_number;
+		}
+
+		if (timestamp_sequence > req->op.seq_num.seq_num) {
+			req->op.seq_num.seq_num = timestamp_sequence;
+			req->op.seq_num.flags |= LDB_SEQ_TIMESTAMP_SEQUENCE;
+		}
+
+		req->op.seq_num.flags |= LDB_SEQ_GLOBAL_SEQUENCE;
+		break;
+	case LDB_SEQ_HIGHEST_TIMESTAMP:
+		req->op.seq_num.seq_num = timestamp;
+		break;
+	}
+
+	switch (req->op.seq_num.flags) {
+	case LDB_SEQ_NEXT:
+		req->op.seq_num.seq_num++;
 	}
-	req->op.seq_num.seq_num = seq_number;
 	return LDB_SUCCESS;
 }
 
diff --git a/source4/dsdb/samdb/ldb_modules/rootdse.c b/source4/dsdb/samdb/ldb_modules/rootdse.c
index c180e2f1b0f..a8bc3fbdc27 100644
--- a/source4/dsdb/samdb/ldb_modules/rootdse.c
+++ b/source4/dsdb/samdb/ldb_modules/rootdse.c
@@ -118,7 +118,7 @@ static int rootdse_add_dynamic(struct ldb_module *module, struct ldb_message *ms
 
 	if (do_attribute(attrs, "highestCommittedUSN")) {
 		uint64_t seq_num;
-		int ret = ldb_sequence_number(module->ldb, &seq_num);
+		int ret = ldb_sequence_number(module->ldb, LDB_SEQ_HIGHEST_SEQ, &seq_num);
 		if (ret == LDB_SUCCESS) {
 			if (ldb_msg_add_fmt(msg, "highestCommittedUSN", 
 					    "%llu", (unsigned long long)seq_num) != 0) {