Resolves: 243227

Summary: Handle syncing add opererations that have a ntuniqueid present.

5 files changed, 490 insertions, 61 deletions

diff --git a/ldap/servers/plugins/replication/repl5.h b/ldap/servers/plugins/replication/repl5.h
index 304f1267..ed27f4e7 100644
--- a/ldap/servers/plugins/replication/repl5.h
+++ b/ldap/servers/plugins/replication/repl5.h
@@ -63,8 +63,8 @@
 #define REPLICA_TYPE_WINDOWS 1
 #define REPLICA_TYPE_MULTIMASTER 0
 #define REPL_DIRSYNC_CONTROL_OID "1.2.840.113556.1.4.841"
-#define CONN_SUPPORTS_DIRSYNC 12
-#define CONN_DOES_NOT_SUPPORT_DIRSYNC  13
+#define REPL_RETURN_DELETED_OBJS_CONTROL_OID "1.2.840.113556.1.4.417"
+#define REPL_WIN2K3_AD_OID "1.2.840.113556.1.4.1670"
 
 /* DS 5.0 replication protocol OIDs */
 #define REPL_START_NSDS50_REPLICATION_REQUEST_OID "2.16.840.1.113730.3.5.3"
@@ -358,7 +358,11 @@ typedef enum
 	CONN_SUPPORTS_DS71_REPL,
 	CONN_DOES_NOT_SUPPORT_DS71_REPL,
 	CONN_IS_READONLY,
-	CONN_IS_NOT_READONLY
+	CONN_IS_NOT_READONLY,
+	CONN_SUPPORTS_DIRSYNC,
+	CONN_DOES_NOT_SUPPORT_DIRSYNC,
+	CONN_IS_WIN2K3,
+	CONN_NOT_WIN2K3
 } ConnResult;  
 Repl_Connection *conn_new(Repl_Agmt *agmt);
 ConnResult conn_connect(Repl_Connection *conn);
diff --git a/ldap/servers/plugins/replication/windows_connection.c b/ldap/servers/plugins/replication/windows_connection.c
index 8ef08419..a898a8ce 100644
--- a/ldap/servers/plugins/replication/windows_connection.c
+++ b/ldap/servers/plugins/replication/windows_connection.c
@@ -83,6 +83,7 @@ typedef struct repl_connection
 	struct timeval timeout;
 	int flag_agmt_changed;
 	char *plain;
+	int is_win2k3; /* 1 if it is win2k3 or later, 0 if not, -1 if not determined */
 } repl_connection;
 
 /* #define DEFAULT_LINGER_TIME (5 * 60) */ /* 5 minutes */
@@ -167,6 +168,7 @@ windows_conn_new(Repl_Agmt *agmt)
 	rpc->supports_ds40_repl = -1;
 	rpc->supports_ds50_repl = -1;
 	rpc->supports_dirsync = -1;
+	rpc->is_win2k3 = -1;
 	rpc->linger_active = PR_FALSE;
 	rpc->delete_after_linger = PR_FALSE;
 	rpc->linger_event = NULL;
@@ -291,21 +293,18 @@ windows_conn_get_error(Repl_Connection *conn, int *operation, int *error)
 static ConnResult
 windows_perform_operation(Repl_Connection *conn, int optype, const char *dn,
 	LDAPMod **attrs, const char *newrdn, const char *newparent,
-	int deleteoldrdn, LDAPControl *update_control,
+	int deleteoldrdn, LDAPControl **server_controls,
 	const char *extop_oid, struct berval *extop_payload, char **retoidp,
 	struct berval **retdatap, LDAPControl ***returned_controls)
 {
 	int rc;
 	ConnResult return_value;
-	LDAPControl *server_controls[1];
 	LDAPControl **loc_returned_controls;
 	const char *op_string = NULL;
 	const char *extra_op_string = NULL;
 
 	LDAPDebug( LDAP_DEBUG_TRACE, "=> windows_perform_operation\n", 0, 0, 0 );
 
-	server_controls[0] = NULL;
-
 	if (windows_conn_connected(conn))
 	{
 		int msgid;
@@ -588,9 +587,17 @@ windows_LDAPMessage2Entry(LDAP * ld, LDAPMessage * msg, int attrsonly) {
     return e;
 }
 
+/* Perform a simple search against Windows with no controls */
 ConnResult
 windows_search_entry(Repl_Connection *conn, char* searchbase, char *filter, Slapi_Entry **entry)
 {
+	return windows_search_entry_ext(conn, searchbase, filter, entry, NULL);
+}
+
+/* Perform a simple search against Windows with optional controls */
+ConnResult
+windows_search_entry_ext(Repl_Connection *conn, char* searchbase, char *filter, Slapi_Entry **entry, LDAPControl **serverctrls)
+{
 	ConnResult return_value = 0;
 	int ldap_rc = 0;
 	LDAPMessage *res = NULL;
@@ -607,7 +614,7 @@ windows_search_entry(Repl_Connection *conn, char* searchbase, char *filter, Slap
 	{
 		ldap_rc = ldap_search_ext_s(conn->ld, searchbase, LDAP_SCOPE_SUBTREE,
 			filter, NULL, 0 /* attrsonly */,
-			NULL , NULL /* client controls */,
+			serverctrls , NULL /* client controls */,
 			&conn->timeout, 0 /* sizelimit */, &res);
 		if (LDAP_SUCCESS == ldap_rc)
 		{
@@ -684,9 +691,7 @@ send_dirsync_search(Repl_Connection *conn)
 			server_controls[0] = NULL; /* unsupported */
 		} else 
 		{
-			/* DBDB: I'm pretty sure that the control is leaked from here */
-			/* Purify agrees */
-			server_controls[0] = windows_private_dirsync_control(conn->agmt); /* yes, or don't know */
+			server_controls[0] = windows_private_dirsync_control(conn->agmt);
 		}
 
 		server_controls[1] = NULL;
@@ -746,12 +751,12 @@ send_dirsync_search(Repl_Connection *conn)
  */
 ConnResult
 windows_conn_send_add(Repl_Connection *conn, const char *dn, LDAPMod **attrs,
-	LDAPControl *update_control, LDAPControl ***returned_controls)
+	LDAPControl **server_controls, LDAPControl ***returned_controls)
 {
 	ConnResult res = 0;
 	LDAPDebug( LDAP_DEBUG_TRACE, "=> windows_conn_send_add\n", 0, 0, 0 );
 	res = windows_perform_operation(conn, CONN_ADD, dn, attrs, NULL /* newrdn */,
-		NULL /* newparent */, 0 /* deleteoldrdn */, update_control,
+		NULL /* newparent */, 0 /* deleteoldrdn */, server_controls,
 		NULL /* extop OID */, NULL /* extop payload */, NULL /* retoidp */,
 		NULL /* retdatap */, returned_controls);
 	LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_conn_send_add\n", 0, 0, 0 );
@@ -764,13 +769,13 @@ windows_conn_send_add(Repl_Connection *conn, const char *dn, LDAPMod **attrs,
  */
 ConnResult
 windows_conn_send_delete(Repl_Connection *conn, const char *dn,
-	LDAPControl *update_control, LDAPControl ***returned_controls)
+	LDAPControl **server_controls, LDAPControl ***returned_controls)
 {
 	LDAPDebug( LDAP_DEBUG_TRACE, "=> windows_conn_send_delete\n", 0, 0, 0 );
 	LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_conn_send_delete\n", 0, 0, 0 );
 	return windows_perform_operation(conn, CONN_DELETE, dn, NULL /* attrs */,
 		NULL /* newrdn */, NULL /* newparent */, 0 /* deleteoldrdn */,
-		update_control, NULL /* extop OID */, NULL /* extop payload */,
+		server_controls, NULL /* extop OID */, NULL /* extop payload */,
 		NULL /* retoidp */, NULL /* retdatap */, returned_controls);
 }
 
@@ -780,12 +785,12 @@ windows_conn_send_delete(Repl_Connection *conn, const char *dn,
  */
 ConnResult
 windows_conn_send_modify(Repl_Connection *conn, const char *dn, LDAPMod **mods,
-	LDAPControl *update_control, LDAPControl ***returned_controls)
+	LDAPControl **server_controls, LDAPControl ***returned_controls)
 {
 	LDAPDebug( LDAP_DEBUG_TRACE, "=> windows_conn_send_modify\n", 0, 0, 0 );
 	LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_conn_send_modify\n", 0, 0, 0 );
 	return windows_perform_operation(conn, CONN_MODIFY, dn, mods, NULL /* newrdn */,
-		NULL /* newparent */, 0 /* deleteoldrdn */, update_control,
+		NULL /* newparent */, 0 /* deleteoldrdn */, server_controls,
 		NULL /* extop OID */, NULL /* extop payload */, NULL /* retoidp */,
 		NULL /* retdatap */, returned_controls);
 }
@@ -796,12 +801,12 @@ windows_conn_send_modify(Repl_Connection *conn, const char *dn, LDAPMod **mods,
 ConnResult
 windows_conn_send_rename(Repl_Connection *conn, const char *dn,
 	const char *newrdn, const char *newparent, int deleteoldrdn,
-	LDAPControl *update_control, LDAPControl ***returned_controls)
+	LDAPControl **server_controls, LDAPControl ***returned_controls)
 {
 	LDAPDebug( LDAP_DEBUG_TRACE, "=> windows_conn_send_rename\n", 0, 0, 0 );
 	LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_conn_send_rename\n", 0, 0, 0 );
 	return windows_perform_operation(conn, CONN_RENAME, dn, NULL /* attrs */,
-		newrdn, newparent, deleteoldrdn, update_control,
+		newrdn, newparent, deleteoldrdn, server_controls,
 		NULL /* extop OID */, NULL /* extop payload */, NULL /* retoidp */,
 		NULL /* retdatap */, returned_controls);
 }
@@ -878,13 +883,13 @@ Slapi_Entry * windows_conn_get_search_result(Repl_Connection *conn)
 ConnResult
 windows_conn_send_extended_operation(Repl_Connection *conn, const char *extop_oid,
 	struct berval *payload, char **retoidp, struct berval **retdatap,
-	LDAPControl *update_control, LDAPControl ***returned_controls)
+	LDAPControl **server_controls, LDAPControl ***returned_controls)
 {
 	LDAPDebug( LDAP_DEBUG_TRACE, "=> windows_conn_send_extended_operation\n", 0, 0, 0 );
 	LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_conn_send_extended_operation\n", 0, 0, 0 );
 	return windows_perform_operation(conn, CONN_EXTENDED_OPERATION, NULL /* dn */, NULL /* attrs */,
 		NULL /* newrdn */, NULL /* newparent */,  0 /* deleteoldrdn */,
-		update_control, extop_oid, payload, retoidp, retdatap,
+		server_controls, extop_oid, payload, retoidp, retdatap,
 		returned_controls);
 }
 
@@ -1264,6 +1269,16 @@ windows_conn_connect(Repl_Connection *conn)
 		{
 			windows_private_set_isnt4(conn->agmt,0);
 		}
+
+		supports = windows_conn_replica_is_win2k3(conn);
+		if (CONN_IS_WIN2K3 == supports)
+		{
+			windows_private_set_iswin2k3(conn->agmt,1);
+			LDAPDebug( LDAP_DEBUG_REPL, "windows_conn_connect : detected Win2k3 peer\n", 0, 0, 0 );
+		} else
+		{
+			windows_private_set_iswin2k3(conn->agmt,0);
+		}
 	}
 
 	ber_bvfree(creds);
@@ -1472,6 +1487,71 @@ windows_conn_replica_supports_dirsync(Repl_Connection *conn)
 }
 
 
+/* Checks if the AD server is running win2k3 (or later) */
+ConnResult
+windows_conn_replica_is_win2k3(Repl_Connection *conn)
+{
+        ConnResult return_value;
+        int ldap_rc;
+
+        LDAPDebug( LDAP_DEBUG_TRACE, "=> windows_conn_replica_is_win2k3\n", 0, 0, 0 );
+
+        if (windows_conn_connected(conn))
+        {
+                if (conn->is_win2k3 == -1) {
+                        LDAPMessage *res = NULL;
+                        LDAPMessage *entry = NULL;
+                        char *attrs[] = {"supportedCapabilities", NULL};
+
+                        conn->status = STATUS_SEARCHING;
+                        ldap_rc = ldap_search_ext_s(conn->ld, "", LDAP_SCOPE_BASE,
+                                                                                "(objectclass=*)", attrs, 0 /* attrsonly */,
+                                                                                NULL /* server controls */, NULL /* client controls */,
+                                                                                &conn->timeout, LDAP_NO_LIMIT, &res);
+                        if (LDAP_SUCCESS == ldap_rc)
+                        {
+                                conn->is_win2k3 = 0;
+                                entry = ldap_first_entry(conn->ld, res);
+                                if (!attribute_string_value_present(conn->ld, entry, "supportedCapabilities", REPL_WIN2K3_AD_OID))
+                                {
+                                        return_value = CONN_NOT_WIN2K3;
+                                }
+                                else
+                                {
+
+                                        conn->is_win2k3 =1;
+                                        return_value = CONN_IS_WIN2K3;
+                                }
+                        }
+                        else
+                        {
+                                if (IS_DISCONNECT_ERROR(ldap_rc))
+                                {
+                                        conn->last_ldap_error = ldap_rc;        /* specific reason */
+                                        windows_conn_disconnect(conn);
+                                        return_value = CONN_NOT_CONNECTED;
+                                }
+                                else
+                                {
+                                        return_value = CONN_OPERATION_FAILED;
+                                }
+                        }
+                        if (NULL != res)
+                                ldap_msgfree(res);
+                        }
+                else {
+                        return_value = conn->is_win2k3 ? CONN_IS_WIN2K3 : CONN_NOT_WIN2K3;
+                }
+        }
+        else
+        {
+                /* Not connected */
+                return_value = CONN_NOT_CONNECTED;
+        }
+        LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_conn_replica_is_win2k3\n", 0, 0, 0 );
+        return return_value;
+}
+
 
 /*
  * Return 1 if "value" is a value of attribute type "type" in entry "entry".
diff --git a/ldap/servers/plugins/replication/windows_private.c b/ldap/servers/plugins/replication/windows_private.c
index 340047f7..1c2e0fbe 100644
--- a/ldap/servers/plugins/replication/windows_private.c
+++ b/ldap/servers/plugins/replication/windows_private.c
@@ -65,6 +65,7 @@ struct windowsprivate {
   PRBool create_groups_from_dirsync;
   char *windows_domain;
   int isnt4;
+  int iswin2k3;
 };
 
 static int
@@ -245,6 +246,38 @@ void windows_private_set_isnt4(const Repl_Agmt *ra, int isit)
 		LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_private_set_isnt4\n", 0, 0, 0 );
 }
 
+int windows_private_get_iswin2k3(const Repl_Agmt *ra)
+{
+		Dirsync_Private *dp;
+
+		LDAPDebug( LDAP_DEBUG_TRACE, "=> windows_private_get_iswin2k3\n", 0, 0, 0 );
+
+	PR_ASSERT(ra);
+
+		dp = (Dirsync_Private *) agmt_get_priv(ra);
+		PR_ASSERT (dp);
+
+		LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_private_get_iswin2k3\n", 0, 0, 0 );
+
+		return dp->iswin2k3;
+}
+
+void windows_private_set_iswin2k3(const Repl_Agmt *ra, int isit)
+{
+		Dirsync_Private *dp;
+
+		LDAPDebug( LDAP_DEBUG_TRACE, "=> windows_private_set_iswin2k3\n", 0, 0, 0 );
+
+	PR_ASSERT(ra);
+
+		dp = (Dirsync_Private *) agmt_get_priv(ra);
+		PR_ASSERT (dp);
+
+		dp->iswin2k3 = isit;
+
+		LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_private_set_iswin2k3\n", 0, 0, 0 );
+}
+
 
 /* Returns a copy of the Slapi_DN pointer, no need to free it */
 const Slapi_DN* windows_private_get_windows_subtree (const Repl_Agmt *ra)
diff --git a/ldap/servers/plugins/replication/windows_protocol_util.c b/ldap/servers/plugins/replication/windows_protocol_util.c
index 4ff364af..3e28c4cc 100644
--- a/ldap/servers/plugins/replication/windows_protocol_util.c
+++ b/ldap/servers/plugins/replication/windows_protocol_util.c
@@ -71,11 +71,16 @@ static int windows_get_local_entry(const Slapi_DN* local_dn,Slapi_Entry **local_
 static int windows_get_local_entry_by_uniqueid(Private_Repl_Protocol *prp,const char* uniqueid,Slapi_Entry **local_entry);
 static int map_entry_dn_outbound(Slapi_Entry *e, Slapi_DN **dn, Private_Repl_Protocol *prp, int *missing_entry, int want_guid);
 static char* extract_ntuserdomainid_from_entry(Slapi_Entry *e);
+static char* extract_container(const Slapi_DN *entry_dn, const Slapi_DN *suffix_dn);
 static int windows_get_remote_entry (Private_Repl_Protocol *prp, const Slapi_DN* remote_dn,Slapi_Entry **remote_entry);
+static int windows_get_remote_tombstone(Private_Repl_Protocol *prp, const Slapi_DN* remote_dn,Slapi_Entry **remote_entry);
+static int windows_reanimate_tombstone(Private_Repl_Protocol *prp, const Slapi_DN* tombstone_dn, const char* new_dn);
 static const char* op2string (int op);
 static int is_subject_of_agreemeent_remote(Slapi_Entry *e, const Repl_Agmt *ra);
 static int map_entry_dn_inbound(Slapi_Entry *e, Slapi_DN **dn, const Repl_Agmt *ra);
 static int windows_update_remote_entry(Private_Repl_Protocol *prp,Slapi_Entry *remote_entry,Slapi_Entry *local_entry);
+static int is_guid_dn(Slapi_DN *remote_dn);
+static int map_windows_tombstone_dn(Slapi_Entry *e, Slapi_DN **dn, Private_Repl_Protocol *prp, int *exists);
 
 
 /* Controls the direction of flow for mapped attributes */
@@ -363,7 +368,7 @@ windows_dump_entry(const char *string, Slapi_Entry *e)
 		slapi_log_error(SLAPI_LOG_REPL, NULL, "Windows sync entry: %s %s\n", string, buffer);
 		if (buffer)
 		{
-			slapi_ch_free((void**)&buffer);
+			slapi_ch_free_string(&buffer);
 		} 
 	}
 }
@@ -953,11 +958,85 @@ process_replay_add(Private_Repl_Protocol *prp, slapi_operation_parameters *op, S
 	int rc = 0;
 
 	slapi_log_error(SLAPI_LOG_REPL, repl_plugin_name,
-		"%s: process_replay_add: dn=\"%s\" (%s,%s)\n",
-		agmt_get_long_name(prp->agmt), slapi_sdn_get_dn(remote_dn), missing_entry ? "not present" : "already present" , remote_add_allowed ? "add allowed" : "add not allowed");
+		"%s: process_replay_add: dn=\"%s\" (%s,%s)\n", agmt_get_long_name(prp->agmt),
+		slapi_sdn_get_dn(remote_dn), missing_entry ? "not present" : "already present",
+		remote_add_allowed ? "add allowed" : "add not allowed");
 
 	if (missing_entry)
 	{
+		/* If DN is a GUID, we need to attempt to reanimate the tombstone */
+		if (is_guid_dn(remote_dn)) {
+			int tstone_exists = 0;
+			int reanimate_rc = -1;
+			char *new_dn_string = NULL;
+			char *cn_string = NULL;
+			Slapi_DN *tombstone_dn = NULL;
+
+			slapi_log_error(SLAPI_LOG_REPL, repl_plugin_name,
+				"%s: process_replay_add: dn=\"%s\" appears to have been"
+				"  deleted on remote side.  Searching for tombstone.\n",
+				agmt_get_long_name(prp->agmt), slapi_sdn_get_dn(remote_dn));
+
+			/* Map local entry to tombstone DN and verify that it exists on
+			 * AD side */
+			map_windows_tombstone_dn(local_entry, &tombstone_dn, prp, &tstone_exists);
+
+			/* We can't use a GUID DN, so rewrite to the new mapped DN. */
+			cn_string = slapi_entry_attr_get_charptr(local_entry,"cn");
+			if (!cn_string) {
+				cn_string = slapi_entry_attr_get_charptr(local_entry,"ntuserdomainid");
+			}
+
+			if (cn_string) {
+				char *rdnstr = NULL;
+				char *container_str = NULL;
+				const char *suffix = slapi_sdn_get_dn(windows_private_get_windows_subtree(prp->agmt));
+
+				container_str = extract_container(slapi_entry_get_sdn_const(local_entry),
+					windows_private_get_directory_subtree(prp->agmt));
+				new_dn_string = PR_smprintf("cn=%s,%s%s", cn_string, container_str, suffix);
+
+				if (new_dn_string) {
+					/* If the tombstone exists, reanimate it. If the tombstone
+					 * does not exist, we'll create a new entry in AD, which
+					 * will end up getting a new GUID generated by AD. */
+					if (tstone_exists) {
+						slapi_log_error(SLAPI_LOG_REPL, repl_plugin_name,
+							"%s: process_replay_add: Reanimating tombstone (dn=\"%s\") to"
+							" normal entry (dn=\"%s\").\n", agmt_get_long_name(prp->agmt),
+							slapi_sdn_get_dn(tombstone_dn), new_dn_string);
+						reanimate_rc = windows_reanimate_tombstone(prp, tombstone_dn, (const char *)new_dn_string);
+						if (reanimate_rc != 0) {
+							slapi_log_error(SLAPI_LOG_REPL, repl_plugin_name,
+								"%s: process_replay_add: Reanimation of tombstone"
+								" (dn=\"%s\") failed.  A new entry (dn=\"%s\")"
+								" will be added instead.\n", agmt_get_long_name(prp->agmt),
+								slapi_sdn_get_dn(tombstone_dn), new_dn_string);
+						}
+					}
+
+					/* Clear out the old GUID DN and use the new one. We hand off the memory
+					 * for new_dn_string into the remote_dn. */
+					slapi_sdn_done(remote_dn);
+					slapi_sdn_set_dn_passin(remote_dn, new_dn_string);
+				}
+
+				slapi_ch_free_string(&cn_string);
+				slapi_ch_free_string(&container_str);
+			}
+
+			if (tombstone_dn) {
+				slapi_sdn_free(&tombstone_dn);
+			}
+
+			if (reanimate_rc == 0) {
+				/* We reanimated a tombstone, so an add won't work.  We
+				 * fallback to doing a modify of the newly reanimated
+				 * entry. */
+				goto modify_fallback;
+			}
+		}
+
 		if (remote_add_allowed) {
 			LDAPMod **entryattrs = NULL;
 			Slapi_Entry *mapped_entry = NULL;
@@ -971,17 +1050,26 @@ process_replay_add(Private_Repl_Protocol *prp, slapi_operation_parameters *op, S
 				mapped_entry = NULL;
 				if (NULL == entryattrs)
 				{
-					slapi_log_error(SLAPI_LOG_FATAL, windows_repl_plugin_name,"%s: windows_replay_update: Cannot convert entry to LDAPMods.\n",agmt_get_long_name(prp->agmt));
+					slapi_log_error(SLAPI_LOG_FATAL, windows_repl_plugin_name,
+						"%s: windows_replay_update: Cannot convert entry to LDAPMods.\n",
+						agmt_get_long_name(prp->agmt));
 					return_value = CONN_LOCAL_ERROR;
 				}
 				else
 				{
 					windows_log_add_entry_remote(local_dn, remote_dn);
-					return_value = windows_conn_send_add(prp->conn, slapi_sdn_get_dn(remote_dn), entryattrs, NULL, NULL);
-					/* It's possible that the entry already exists in AD, in which case we fall back to modify it */
+					return_value = windows_conn_send_add(prp->conn, slapi_sdn_get_dn(remote_dn),
+						entryattrs, NULL, NULL);
+					/* It's possible that the entry already exists in AD, in which
+					 * case we fall back to modify it */
+					/* NGK - This fallback doesn't seem to happen, at least not at this point
+					 * in the code.  The only chance to fallback to doing a modify is if
+					 * missing_entry is set to 0 at the top of this function. */
 					if (return_value)
 					{
-						slapi_log_error(SLAPI_LOG_FATAL, windows_repl_plugin_name,"%s: windows_replay_update: Cannot replay add operation.\n",agmt_get_long_name(prp->agmt));
+						slapi_log_error(SLAPI_LOG_FATAL, windows_repl_plugin_name,
+							"%s: windows_replay_update: Cannot replay add operation.\n",
+							agmt_get_long_name(prp->agmt));
 					}
 					ldap_mods_free(entryattrs, 1);
 					entryattrs = NULL;
@@ -989,14 +1077,15 @@ process_replay_add(Private_Repl_Protocol *prp, slapi_operation_parameters *op, S
 			} else 
 			{
 				slapi_log_error(SLAPI_LOG_FATAL, repl_plugin_name,
-					"%s: process_replay_add: failed to create mapped entry dn=\"%s\"\n",agmt_get_long_name(prp->agmt), slapi_sdn_get_dn(remote_dn));
+					"%s: process_replay_add: failed to create mapped entry dn=\"%s\"\n",
+					agmt_get_long_name(prp->agmt), slapi_sdn_get_dn(remote_dn));
 			}
 		}
 	} else 
 	{
-
 		Slapi_Entry *remote_entry = NULL;
 
+modify_fallback:
 		/* Fetch the remote entry */
 		rc = windows_get_remote_entry(prp, remote_dn,&remote_entry);
 		if (0 == rc && remote_entry) {
@@ -1018,7 +1107,6 @@ ConnResult
 windows_replay_update(Private_Repl_Protocol *prp, slapi_operation_parameters *op)
 {
 	ConnResult return_value = 0;
-	LDAPControl *update_control = NULL; /* No controls used for AD */
 	int rc = 0;
 	char *password = NULL;
 	int is_ours = 0;
@@ -1097,7 +1185,7 @@ windows_replay_update(Private_Repl_Protocol *prp, slapi_operation_parameters *op
 							slapi_mod_dump(mapped_mods[i],i);
 						}
 					}
-					return_value = windows_conn_send_modify(prp->conn, slapi_sdn_get_dn(remote_dn), mapped_mods, update_control,NULL /* returned controls */);
+					return_value = windows_conn_send_modify(prp->conn, slapi_sdn_get_dn(remote_dn), mapped_mods, NULL, NULL /* returned controls */);
 				}
 				if (mapped_mods)
 				{
@@ -1109,7 +1197,7 @@ windows_replay_update(Private_Repl_Protocol *prp, slapi_operation_parameters *op
 		case SLAPI_OPERATION_DELETE:
 			if (delete_remote_entry_allowed(local_entry))
 			{
-				return_value = windows_conn_send_delete(prp->conn, slapi_sdn_get_dn(remote_dn), update_control, NULL /* returned controls */);
+				return_value = windows_conn_send_delete(prp->conn, slapi_sdn_get_dn(remote_dn), NULL, NULL /* returned controls */);
 					slapi_log_error(SLAPI_LOG_REPL, repl_plugin_name,
 					"%s: windows_replay_update: deleted remote entry, dn=\"%s\", result=%d\n",
 					agmt_get_long_name(prp->agmt), slapi_sdn_get_dn(remote_dn), return_value);
@@ -1125,7 +1213,7 @@ windows_replay_update(Private_Repl_Protocol *prp, slapi_operation_parameters *op
 				op->p.p_modrdn.modrdn_newrdn,
 				op->p.p_modrdn.modrdn_newsuperior_address.dn,
 				op->p.p_modrdn.modrdn_deloldrdn,
-				update_control, NULL /* returned controls */);
+				NULL, NULL /* returned controls */);
 			break;
 		default:
 			slapi_log_error(SLAPI_LOG_FATAL, windows_repl_plugin_name, "%s: replay_update: Unknown "
@@ -1296,7 +1384,7 @@ windows_create_remote_entry(Private_Repl_Protocol *prp,Slapi_Entry *original_ent
 		goto error;
 	}
 	new_entry = slapi_str2entry(entry_string, 0);
-	slapi_ch_free((void**)&entry_string);
+	slapi_ch_free_string(&entry_string);
 	if (NULL == new_entry) 
 	{
 		goto error;
@@ -1399,7 +1487,7 @@ windows_create_remote_entry(Private_Repl_Protocol *prp,Slapi_Entry *original_ent
 						slapi_attr_set_type(new_attr, new_type);
 					}
 				}
-				slapi_ch_free((void**)&new_type);
+				slapi_ch_free_string(&new_type);
 			}
 			/* password mods are treated specially */
 			if (0 == slapi_attr_type_cmp(type, PSEUDO_ATTR_UNHASHEDUSERPASSWORD, SLAPI_TYPE_CMP_SUBTYPE) )
@@ -1469,7 +1557,7 @@ windows_create_remote_entry(Private_Repl_Protocol *prp,Slapi_Entry *original_ent
 error:
 	if (username)
 	{
-		slapi_ch_free((void**)&username);
+		slapi_ch_free_string(&username);
 	}
 	if (new_entry) 
 	{
@@ -1633,7 +1721,7 @@ windows_map_mods_for_replay(Private_Repl_Protocol *prp,LDAPMod **original_mods,
 
 					slapi_mods_add_modbvps(&mapped_smods,mod->mod_op,mapped_type,mod->mod_bvalues);
 				}
-				slapi_ch_free((void**)&mapped_type);
+				slapi_ch_free_string(&mapped_type);
 			} else 
 			{
 				/* password mods are treated specially */
@@ -1832,6 +1920,70 @@ windows_get_remote_entry (Private_Repl_Protocol *prp, const Slapi_DN* remote_dn,
 	return retval;
 }
 
+/* Search for a tombstone entry in AD by DN */
+static int
+windows_get_remote_tombstone (Private_Repl_Protocol *prp, const Slapi_DN* remote_dn,Slapi_Entry **remote_entry)
+{
+	int retval = 0;
+	ConnResult cres = 0;
+	char *filter = "(objectclass=*)";
+	const char *searchbase = NULL;
+	Slapi_Entry *found_entry = NULL;
+	LDAPControl *server_controls[2];
+
+	/* We need to send the "Return Deleted Objects" control to search
+	 * for tombstones. */
+	slapi_build_control(REPL_RETURN_DELETED_OBJS_CONTROL_OID, NULL, PR_TRUE,
+			&server_controls[0]);
+	server_controls[1] = NULL;
+
+	searchbase = slapi_sdn_get_dn(remote_dn);
+	cres = windows_search_entry_ext(prp->conn, (char*)searchbase, filter,
+				&found_entry, server_controls);
+	if (cres) {
+		retval = -1;
+	} else {
+		if (found_entry) {
+			*remote_entry = found_entry;
+		}
+	}
+
+	ldap_control_free(server_controls[0]);
+	return retval;
+}
+
+/* Reanimate a tombstone in AD.  Returns 0 on success, otherwise you get the
+ * LDAP return code from the modify operation.  */
+static int
+windows_reanimate_tombstone(Private_Repl_Protocol *prp, const Slapi_DN* tombstone_dn, const char* new_dn)
+{
+	int retval = 0;
+	LDAPControl *server_controls[2];
+	Slapi_Mods smods = {0};
+
+	/* We need to send the "Return Deleted Objects" control to modify
+	 * tombstone entries. */
+	slapi_build_control(REPL_RETURN_DELETED_OBJS_CONTROL_OID, NULL, PR_TRUE,
+			&server_controls[0]);
+	server_controls[1] = NULL;
+
+	/* To reanimate a tombstone in AD, you need to send a modify
+	 * operation that does two things.  It must remove the isDeleted
+	 * attribute from the entry and it must modify the DN.  This DN
+	 * does not have to be the same place in the tree that the entry
+	 * previously existed. */ 
+	slapi_mods_init (&smods, 0);
+	slapi_mods_add_mod_values(&smods, LDAP_MOD_DELETE, "isDeleted", NULL);
+	slapi_mods_add_string(&smods, LDAP_MOD_REPLACE, "distinguishedName", new_dn);
+
+	retval = windows_conn_send_modify(prp->conn, slapi_sdn_get_dn(tombstone_dn),
+				 slapi_mods_get_ldapmods_byref(&smods), server_controls, NULL );
+
+	slapi_mods_done(&smods);
+	ldap_control_free(server_controls[0]);
+	return retval;
+}
+
 static int
 find_entry_by_attr_value(const char *attribute, const char *value, Slapi_Entry **e,  const Repl_Agmt *ra)
 {
@@ -1858,7 +2010,7 @@ find_entry_by_attr_value(const char *attribute, const char *value, Slapi_Entry *
         LDAP_SCOPE_SUBTREE, query, NULL, 0, NULL, NULL,
         (void *)plugin_get_default_component_id(), 0);
     slapi_search_internal_pb(pb);
-    slapi_ch_free((void **)&query);
+    slapi_ch_free_string(&query);
 
     slapi_pblock_get(pb, SLAPI_PLUGIN_INTOP_RESULT, &rval);
     if (rval != LDAP_SUCCESS)
@@ -1906,9 +2058,9 @@ find_entry_by_guid(const char *guid, Slapi_Entry **e, const Repl_Agmt *ra)
 		return find_entry_by_attr_value("ntUniqueId",guid,e,ra);
 }
 
-/* Remove dashes from a GUID string */
+/* Remove dashes from a GUID string. */
 static void
-dedash(char *str)
+dedash_guid(char *str)
 {
 	char *p = str;
 	char c = '\0';
@@ -1930,10 +2082,41 @@ dedash(char *str)
 	}
 }
 
+/* Add dashes into a GUID string.  If the guid is not formatted properly,
+ * we will free it and set the pointer to NULL. */
+static void
+dash_guid(char **str)
+{
+	if (strlen(*str) == NTUNIQUEID_LENGTH) {
+		char *p = NULL;
+		/* Add extra room for the dashes */
+		*str = slapi_ch_realloc(*str, AD_GUID_LENGTH + 1);
+
+		/* GUID needs to be in 8-4-4-4-12 format */
+		p = *str + 23;
+		memmove(p + 1, *str + 20, 12);
+		*p = '-';
+		p = *str + 18;
+		memmove(p + 1, *str + 16, 4);
+		*p = '-';
+		p = *str + 13;
+		memmove(p + 1, *str + 12, 4);
+		*p = '-';
+		p = *str + 8;
+		memmove(p + 1, *str + 8, 4);
+		*p = '-';
+		p = *str + 36;
+		*p = '\0';
+	} else {
+		/* This GUID does not appear to be valid */
+		slapi_ch_free_string(str);
+	}
+}
+
 /* For reasons not clear, the GUID returned in the tombstone DN is all 
  * messed up, like the guy in the movie 'the fly' after he want in the tranporter device */
 static void
-decrypt(char *guid)
+decrypt_guid(char *guid)
 {
 	static int decrypt_offsets[] = {6,7,4,5,2,3,0,1,10,11,8,9,14,15,12,13,16,17,18,19,
 		20,21,22,23,24,25,26,27,28,29,30,31};
@@ -1948,7 +2131,7 @@ decrypt(char *guid)
 		p++;
 		i++;
 	}
-	slapi_ch_free((void**)&cpy);
+	slapi_ch_free_string(&cpy);
 }
 
 static char*
@@ -1971,8 +2154,8 @@ extract_guid_from_tombstone_dn(const char *dn)
 		strncpy(guid,colon_offset+1,(comma_offset-colon_offset)-1);
 		guid[comma_offset-colon_offset-1] = '\0';
 		/* Finally remove the dashes since we don't store them on our side */
-		dedash(guid);
-		decrypt(guid);
+		dedash_guid(guid);
+		decrypt_guid(guid);
 	}
 	return guid;
 }
@@ -2004,6 +2187,82 @@ convert_to_hex(Slapi_Value *val)
 	return result;
 }
 
+/* Given a local entry, map it to it's AD tombstone DN. An AD
+ * tombstone DN is formatted like:
+ *
+ *     cn=<cn>\0ADEL:<guid>,cn=Deleted Objects,<suffix>
+ * 
+ * This function will allocate a new Slapi_DN.  It is up to the
+ * caller to free it when they are finished with it. */
+static int 
+map_windows_tombstone_dn(Slapi_Entry *e, Slapi_DN **dn, Private_Repl_Protocol *prp, int *exists)
+{
+	int rc = 0;
+	char *cn = NULL;
+	char *guid = NULL;
+	const char *suffix = NULL;
+	char *tombstone_dn = NULL;
+	Slapi_Entry *tombstone = NULL;
+
+	/* Initialize the output values */
+	*dn = NULL;
+	*exists = 0;
+
+	cn = slapi_entry_attr_get_charptr(e,"cn");
+	if (!cn) {
+		cn = slapi_entry_attr_get_charptr(e,"ntuserdomainid");
+	}
+
+	guid = slapi_entry_attr_get_charptr(e,"ntUniqueId");
+	if (guid) {
+		/* the GUID is in a different form in the tombstone DN, so
+		 * we need to transform it from the way we store it. */
+		decrypt_guid(guid);
+		dash_guid(&guid);
+	}
+
+	/* The tombstone suffix discards any containers, so we need
+	 * to trim the DN to only dc components. */
+	if (suffix = slapi_sdn_get_dn(windows_private_get_windows_subtree(prp->agmt))) {
+		/* If this isn't found, it is treated as an error below. */
+		suffix = (const char *) strcasestr(suffix,"dc=");
+	}
+
+	if (cn && guid && suffix) {
+		tombstone_dn = PR_smprintf("cn=%s\\0ADEL:%s,cn=Deleted Objects,%s",
+				cn, guid, suffix);
+
+		/* Hand off the memory to the Slapi_DN */
+		*dn = slapi_sdn_new_dn_passin(tombstone_dn);
+
+		windows_get_remote_tombstone(prp, *dn, &tombstone);
+		if (tombstone) {
+			*exists = 1;
+			slapi_entry_free(tombstone);
+		}
+	} else {
+		slapi_log_error(SLAPI_LOG_REPL, repl_plugin_name,
+			"%s: map_windows_tombstone_dn: Failed to map dn=\"%s\" "
+			"to windows tombstone dn.\n", agmt_get_long_name(prp->agmt),
+			slapi_entry_get_dn(e));
+		rc = 1;
+	}
+
+	slapi_ch_free_string(&cn);
+	slapi_ch_free_string(&guid);
+	return rc;
+}
+
+static int is_guid_dn(Slapi_DN *remote_dn)
+{
+	if ((remote_dn != NULL) && (strncasecmp("<GUID=",
+			slapi_sdn_get_dn(remote_dn), 6) == 0)) {
+		return 1;
+	} else {
+		return 0;
+	}
+}
+
 static char*
 extract_guid_from_entry(Slapi_Entry *e, int is_nt4)
 {
@@ -2151,8 +2410,54 @@ map_entry_dn_outbound(Slapi_Entry *e, Slapi_DN **dn, Private_Repl_Protocol *prp,
 	guid = slapi_entry_attr_get_charptr(e,"ntUniqueId");
 	if (guid && guid_form) 
 	{
+		int rc = 0;
+		Slapi_Entry *remote_entry = NULL;
 		new_dn = make_dn_from_guid(guid, is_nt4, suffix);
-		slapi_ch_free((void**)&guid);
+		slapi_ch_free_string(&guid);
+		/* There are certain cases where we will have a GUID, but the entry does not exist in
+		 * AD.  This happens when you delete an entry, then add it back elsewhere in the tree
+		 * without removing the ntUniqueID attribute.  We should verify that the entry really
+		 * exists in AD. */
+		rc = windows_get_remote_entry(prp, new_dn, &remote_entry);
+		if (0 == rc && remote_entry) {
+			slapi_entry_free(remote_entry);
+		} else {
+			/* We need to re-write the DN to a non-GUID DN if we're syncing to a
+			 * Windows 2000 Server since tombstone reanimation is not supported.
+			 * If we're syncing with Windows 2003 Server, we'll just use the GUID
+			 * to reanimate the tombstone when processing the add operation. */
+			*missing_entry = 1;
+			if (!windows_private_get_iswin2k3(prp->agmt)) {
+				char *new_dn_string = NULL;
+				char *cn_string = NULL;
+
+				/* We can't use a GUID DN, so rewrite to the mapped DN. */
+				cn_string = slapi_entry_attr_get_charptr(e,"cn");
+				if (!cn_string) {
+					cn_string = slapi_entry_attr_get_charptr(e,"ntuserdomainid");
+				}
+
+				if (cn_string) {
+					char *rdnstr = NULL;
+					char *container_str = NULL;
+
+					container_str = extract_container(slapi_entry_get_sdn_const(e),
+						windows_private_get_directory_subtree(prp->agmt));
+					new_dn_string = PR_smprintf("cn=%s,%s%s", cn_string, container_str, suffix);
+
+					if (new_dn_string) {
+						if (new_dn) {
+							slapi_sdn_free(&new_dn);
+						}
+						new_dn = slapi_sdn_new_dn_byval(new_dn_string);
+						PR_smprintf_free(new_dn_string);
+					}
+
+					slapi_ch_free_string(&cn_string);
+					slapi_ch_free_string(&container_str);
+                                 }
+			}
+		}
 	} else 
 	{
 		/* No GUID found, try ntUserDomainId */
@@ -2204,8 +2509,8 @@ map_entry_dn_outbound(Slapi_Entry *e, Slapi_DN **dn, Private_Repl_Protocol *prp,
 							new_dn = slapi_sdn_new_dn_byval(new_dn_string);
 							PR_smprintf_free(new_dn_string);
 						}
-						slapi_ch_free((void**)&cn_string);
-						slapi_ch_free((void**)&container_str);
+						slapi_ch_free_string(&cn_string);
+						slapi_ch_free_string(&container_str);
 					}
 				} else 
 				{
@@ -2217,7 +2522,7 @@ map_entry_dn_outbound(Slapi_Entry *e, Slapi_DN **dn, Private_Repl_Protocol *prp,
 					retval = -1;
 				}
 			}
-			slapi_ch_free((void**)&username);
+			slapi_ch_free_string(&username);
 		}
 		if (remote_entry)
 		{
@@ -2280,7 +2585,7 @@ map_tombstone_dn_inbound(Slapi_Entry *e, Slapi_DN **dn, const Repl_Agmt *ra)
 
 	if (guid) 
 	{
-		slapi_ch_free((void**)&guid);
+		slapi_ch_free_string(&guid);
 	}
 	if (matching_entry)
 	{
@@ -2387,7 +2692,7 @@ map_entry_dn_inbound(Slapi_Entry *e, Slapi_DN **dn, const Repl_Agmt *ra)
 			}
 			new_dn = slapi_sdn_new_dn_byval(new_dn_string);
 			PR_smprintf_free(new_dn_string);
-			slapi_ch_free((void**)&container_str);
+			slapi_ch_free_string(&container_str);
 			/* Clear any earlier error */
 			retval = 0;
 		} else 
@@ -2410,7 +2715,7 @@ error:
 	}
 	if (username)
 	{
-		slapi_ch_free((void **) &username);
+		slapi_ch_free_string(&username);
 	}
 	return retval;
 }
@@ -2542,7 +2847,7 @@ windows_create_local_entry(Private_Repl_Protocol *prp,Slapi_Entry *remote_entry,
 		goto error;
 	}
 	local_entry = slapi_str2entry(entry_string, 0);
-	slapi_ch_free((void**)&entry_string);
+	slapi_ch_free_string(&entry_string);
 	if (NULL == local_entry) 
 	{
 		goto error;
@@ -2583,7 +2888,7 @@ windows_create_local_entry(Private_Repl_Protocol *prp,Slapi_Entry *remote_entry,
 				{
 					slapi_entry_add_valueset(local_entry,new_type,vs);
 				}
-				slapi_ch_free((void**)&new_type);
+				slapi_ch_free_string(&new_type);
 			}
 		}
 		if (vs) 
@@ -2627,7 +2932,7 @@ error:
 	}
 	if (username) 
 	{
-		slapi_ch_free((void**)&username);
+		slapi_ch_free_string(&username);
 	}
 	LDAPDebug( LDAP_DEBUG_TRACE, "<= windows_create_local_entry\n", 0, 0, 0 );
 	return retval;
@@ -2812,7 +3117,7 @@ windows_generate_update_mods(Private_Repl_Protocol *prp,Slapi_Entry *remote_entr
 					if (guid)
 					{
 						slapi_mods_add_string(smods,LDAP_MOD_ADD,local_type,guid);
-						slapi_ch_free((void**)&guid);
+						slapi_ch_free_string(&guid);
 					}
 				} else
 				{
diff --git a/ldap/servers/plugins/replication/windowsrepl.h b/ldap/servers/plugins/replication/windowsrepl.h
index 121fbd74..a7d3267b 100644
--- a/ldap/servers/plugins/replication/windowsrepl.h
+++ b/ldap/servers/plugins/replication/windowsrepl.h
@@ -51,6 +51,7 @@ const Slapi_DN* windows_private_get_directory_subtree (const Repl_Agmt *ra);
 LDAPControl* windows_private_dirsync_control(const Repl_Agmt *ra);
 ConnResult send_dirsync_search(Repl_Connection *conn);
 ConnResult windows_search_entry(Repl_Connection *conn, char* searchbase, char *filter, Slapi_Entry **entry);
+ConnResult windows_search_entry_ext(Repl_Connection *conn, char* searchbase, char *filter, Slapi_Entry **entry, LDAPControl **serverctrls);
 Slapi_Entry *windows_conn_get_search_result(Repl_Connection *conn );
 void windows_private_update_dirsync_control(const Repl_Agmt *ra,LDAPControl **controls );
 PRBool windows_private_dirsync_has_more(const Repl_Agmt *ra);
@@ -65,6 +66,8 @@ const char *windows_private_get_windows_domain(const Repl_Agmt *ra);
 static void windows_private_set_windows_domain(const Repl_Agmt *ra, char *domain);
 int windows_private_get_isnt4(const Repl_Agmt *ra);
 void windows_private_set_isnt4(const Repl_Agmt *ra, int isit);
+int windows_private_get_iswin2k3(const Repl_Agmt *ra);
+void windows_private_set_iswin2k3(const Repl_Agmt *ra, int isit);
 const char* windows_private_get_purl(const Repl_Agmt *ra);
 
 /* in windows_connection.c */
@@ -73,22 +76,23 @@ void windows_conn_disconnect(Repl_Connection *conn);
 void windows_conn_delete(Repl_Connection *conn);
 void windows_conn_get_error(Repl_Connection *conn, int *operation, int *error);
 ConnResult windows_conn_send_add(Repl_Connection *conn, const char *dn, LDAPMod **attrs,
-	LDAPControl *update_control, LDAPControl ***returned_controls);
+	LDAPControl **server_controls, LDAPControl ***returned_controls);
 ConnResult windows_conn_send_delete(Repl_Connection *conn, const char *dn,
-	LDAPControl *update_control, LDAPControl ***returned_controls);
+	LDAPControl **server_controls, LDAPControl ***returned_controls);
 ConnResult windows_conn_send_modify(Repl_Connection *conn, const char *dn, LDAPMod **mods,
-	LDAPControl *update_control, LDAPControl ***returned_controls);
+	LDAPControl **server_controls, LDAPControl ***returned_controls);
 ConnResult windows_conn_send_rename(Repl_Connection *conn, const char *dn,
 	const char *newrdn, const char *newparent, int deleteoldrdn,
-	LDAPControl *update_control, LDAPControl ***returned_controls);
+	LDAPControl **server_controls, LDAPControl ***returned_controls);
 ConnResult windows_conn_send_extended_operation(Repl_Connection *conn, const char *extop_oid,
 	struct berval *payload, char **retoidp, struct berval **retdatap,
-	LDAPControl *update_control, LDAPControl ***returned_controls);
+	LDAPControl **server_controls, LDAPControl ***returned_controls);
 const char *windows_conn_get_status(Repl_Connection *conn);
 void windows_conn_start_linger(Repl_Connection *conn);
 void windows_conn_cancel_linger(Repl_Connection *conn);
 ConnResult windows_conn_replica_supports_ds5_repl(Repl_Connection *conn);
 ConnResult windows_conn_replica_supports_dirsync(Repl_Connection *conn);
+ConnResult windows_conn_replica_is_win2k3(Repl_Connection *conn);
 ConnResult windows_conn_read_entry_attribute(Repl_Connection *conn, const char *dn, char *type,
 	struct berval ***returned_bvals);
 ConnResult windows_conn_push_schema(Repl_Connection *conn, CSN **remotecsn);
@@ -102,3 +106,6 @@ void windows_conn_set_agmt_changed(Repl_Connection *conn);
 /* Used to check for pre-hashed passwords when syncing */
 #define PASSWD_CLEAR_PREFIX "{clear}"
 #define PASSWD_CLEAR_PREFIX_LEN 7
+/* Used for GUID format conversion */
+#define NTUNIQUEID_LENGTH 32
+#define AD_GUID_LENGTH 36