s4-dsdb: Try to avoid much of the time a db search for msDS-IntID

We search in the schema if we have already this intid (using dsdb_attribute_by_attributeID_id because
in the range 0x80000000 0xBFFFFFFFF, attributeID is a DSDB_ATTID_TYPE_INTID).
If so generate another random value.
If not check if the highest USN in the database for the schema partition is the
one that we know.
If so it means that's only this ldb context that is touching the schema in the database.
If not it means that's someone else has modified the database while we are doing our changes too
(this case should be very bery rare) in order to be sure do the search in the database.

3 files changed, 97 insertions, 14 deletions

diff --git a/source4/dsdb/samdb/ldb_modules/repl_meta_data.c b/source4/dsdb/samdb/ldb_modules/repl_meta_data.c
index a558a64999..49fca5f376 100644
--- a/source4/dsdb/samdb/ldb_modules/repl_meta_data.c
+++ b/source4/dsdb/samdb/ldb_modules/repl_meta_data.c
@@ -751,6 +751,7 @@ static int replmd_add_fix_la(struct ldb_module *module, struct ldb_message_eleme
  */
 static int replmd_add(struct ldb_module *module, struct ldb_request *req)
 {
+	struct samldb_msds_intid_persistant *msds_intid_struct;
 	struct ldb_context *ldb;
         struct ldb_control *control;
 	struct replmd_replicated_request *ac;
@@ -1053,7 +1054,14 @@ static int replmd_add(struct ldb_module *module, struct ldb_request *req)
 	if (control) {
 		control->critical = 0;
 	}
+	if (ldb_dn_compare_base(ac->schema->base_dn, req->op.add.message->dn) != 0) {
 
+		/* Update the usn in the SAMLDB_MSDS_INTID_OPAQUE opaque */
+		msds_intid_struct = (struct samldb_msds_intid_persistant *) ldb_get_opaque(ldb, SAMLDB_MSDS_INTID_OPAQUE);
+		if (msds_intid_struct) {
+			msds_intid_struct->usn = ac->seq_num;
+		}
+	}
 	/* go on with the call chain */
 	return ldb_next_request(module, down_req);
 }
@@ -2294,6 +2302,7 @@ static int replmd_modify_handle_linked_attribs(struct ldb_module *module,
 
 static int replmd_modify(struct ldb_module *module, struct ldb_request *req)
 {
+	struct samldb_msds_intid_persistant *msds_intid_struct;
 	struct ldb_context *ldb;
 	struct replmd_replicated_request *ac;
 	struct ldb_request *down_req;
@@ -2426,6 +2435,14 @@ static int replmd_modify(struct ldb_module *module, struct ldb_request *req)
 		}
 	}
 
+	if (!ldb_dn_compare_base(ac->schema->base_dn, msg->dn)) {
+		/* Update the usn in the SAMLDB_MSDS_INTID_OPAQUE opaque */
+		msds_intid_struct = (struct samldb_msds_intid_persistant *) ldb_get_opaque(ldb, SAMLDB_MSDS_INTID_OPAQUE);
+		if (msds_intid_struct) {
+			msds_intid_struct->usn = ac->seq_num;
+		}
+	}
+
 	/* go on with the call chain */
 	return ldb_next_request(module, down_req);
 }
diff --git a/source4/dsdb/samdb/ldb_modules/samldb.c b/source4/dsdb/samdb/ldb_modules/samldb.c
index 7b98dd62c1..a859fc9c73 100644
--- a/source4/dsdb/samdb/ldb_modules/samldb.c
+++ b/source4/dsdb/samdb/ldb_modules/samldb.c
@@ -462,36 +462,95 @@ static int samldb_add_handle_msDS_IntId(struct samldb_ctx *ac)
 	if (system_flags & SYSTEM_FLAG_SCHEMA_BASE_OBJECT) {
 		return LDB_SUCCESS;
 	}
+	schema = dsdb_get_schema(ldb, NULL);
+	if (!schema) {
+		ldb_debug_set(ldb, LDB_DEBUG_FATAL,
+			      "samldb_schema_info_update: no dsdb_schema loaded");
+		DEBUG(0,(__location__ ": %s\n", ldb_errstring(ldb)));
+		return ldb_operr(ldb);
+	}
 
-	/* Generate new value for msDs-IntId
-	 * Value should be in 0x80000000..0xBFFFFFFF range */
-	msds_intid = generate_random() % 0X3FFFFFFF;
-	msds_intid += 0x80000000;
+	msds_intid_struct = (struct samldb_msds_intid_persistant*) ldb_get_opaque(ldb, SAMLDB_MSDS_INTID_OPAQUE);
+	if (!msds_intid_struct) {
+		msds_intid_struct = talloc(ldb, struct samldb_msds_intid_persistant);
+		/* Generate new value for msDs-IntId
+		* Value should be in 0x80000000..0xBFFFFFFF range */
+		msds_intid = generate_random() % 0X3FFFFFFF;
+		msds_intid += 0x80000000;
+		msds_intid_struct->msds_intid = msds_intid;
+		msds_intid_struct->usn = schema->loaded_usn;
+		DEBUG(2, ("No samldb_msds_intid_persistant struct, allocating a new one\n"));
+	} else {
+		msds_intid = msds_intid_struct->msds_intid;
+	}
 
 	/* probe id values until unique one is found */
 	do {
+		uint64_t current_usn;
 		msds_intid++;
 		if (msds_intid > 0xBFFFFFFF) {
 			msds_intid = 0x80000001;
 		}
+		/*
+		 * Alternative strategy to a costly (even indexed search) to the
+		 * database.
+		 * We search in the schema if we have already this intid (using dsdb_attribute_by_attributeID_id because
+		 * in the range 0x80000000 0xBFFFFFFFF, attributeID is a DSDB_ATTID_TYPE_INTID).
+		 * If so generate another random value.
+		 * If not check if the highest USN in the database for the schema partition is the
+		 * one that we know.
+		 * If so it means that's only this ldb context that is touching the schema in the database.
+		 * If not it means that's someone else has modified the database while we are doing our changes too
+		 * (this case should be very bery rare) in order to be sure do the search in the database.
+		 */
+		if (dsdb_attribute_by_attributeID_id(schema, msds_intid)) {
+			msds_intid = generate_random() % 0X3FFFFFFF;
+			msds_intid += 0x80000000;
+			continue;
+		}
 
-		ret = dsdb_module_search(ac->module, ac,
-		                         &ldb_res,
-		                         schema_dn, LDB_SCOPE_ONELEVEL, NULL,
-		                         DSDB_FLAG_NEXT_MODULE,
-					 ac->req,
-		                         "(msDS-IntId=%d)", msds_intid);
+		ret = dsdb_module_load_partition_usn(ac->module, schema->base_dn, &current_usn, NULL, NULL);
 		if (ret != LDB_SUCCESS) {
 			ldb_debug_set(ldb, LDB_DEBUG_ERROR,
-				      __location__": Searching for msDS-IntId=%d failed - %s\n",
-				      msds_intid,
+				      __location__": Searching for schema USN failed: %s\n",
 				      ldb_errstring(ldb));
 			return ldb_operr(ldb);
 		}
-		id_exists = (ldb_res->count > 0);
 
-		talloc_free(ldb_res);
+		/* current_usn can be lesser than msds_intid_struct-> if there is
+		 * uncommited changes.
+		 */
+		if (current_usn > msds_intid_struct->usn) {
+			/* oups something has changed, someone/something
+			 * else is modifying or has modified the schema
+			 * we'd better check this intid is the database directly
+			 */
+
+			DEBUG(2, ("Schema has changed, searching the database for the unicity of %d\n",
+					msds_intid));
+
+			ret = dsdb_module_search(ac->module, ac,
+						&ldb_res,
+						schema_dn, LDB_SCOPE_ONELEVEL, NULL,
+						DSDB_FLAG_NEXT_MODULE,
+						ac->req,
+						"(msDS-IntId=%d)", msds_intid);
+			if (ret != LDB_SUCCESS) {
+				ldb_debug_set(ldb, LDB_DEBUG_ERROR,
+					__location__": Searching for msDS-IntId=%d failed - %s\n",
+					msds_intid,
+					ldb_errstring(ldb));
+				return ldb_operr(ldb);
+			}
+			id_exists = (ldb_res->count > 0);
+			talloc_free(ldb_res);
+		} else {
+			id_exists = 0;
+		}
+
 	} while(id_exists);
+	msds_intid_struct->msds_intid = msds_intid;
+	ldb_set_opaque(ldb, SAMLDB_MSDS_INTID_OPAQUE, msds_intid_struct);
 
 	return samdb_msg_add_int(ldb, ac->msg, ac->msg, "msDS-IntId",
 				 msds_intid);
diff --git a/source4/dsdb/samdb/samdb.h b/source4/dsdb/samdb/samdb.h
index 2a4bd355eb..73da3e20cf 100644
--- a/source4/dsdb/samdb/samdb.h
+++ b/source4/dsdb/samdb/samdb.h
@@ -191,6 +191,13 @@ struct dsdb_openldap_dereference_result_control {
 	struct dsdb_openldap_dereference_result **attributes;
 };
 
+struct samldb_msds_intid_persistant {
+	uint32_t msds_intid;
+	uint64_t usn;
+};
+
+#define SAMLDB_MSDS_INTID_OPAQUE "SAMLDB_MSDS_INTID_OPAQUE"
+
 #define DSDB_PARTITION_DN "@PARTITION"
 #define DSDB_PARTITION_ATTR "partition"