repl_meta_data: Remove the correct forward link for dn+binary attributes
[samba.git] / source4 / dsdb / samdb / ldb_modules / repl_meta_data.c
1 /*
2    ldb database library
3
4    Copyright (C) Simo Sorce  2004-2008
5    Copyright (C) Andrew Bartlett <abartlet@samba.org> 2005-2013
6    Copyright (C) Andrew Tridgell 2005-2009
7    Copyright (C) Stefan Metzmacher <metze@samba.org> 2007
8    Copyright (C) Matthieu Patou <mat@samba.org> 2010-2011
9
10    This program is free software; you can redistribute it and/or modify
11    it under the terms of the GNU General Public License as published by
12    the Free Software Foundation; either version 3 of the License, or
13    (at your option) any later version.
14
15    This program is distributed in the hope that it will be useful,
16    but WITHOUT ANY WARRANTY; without even the implied warranty of
17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18    GNU General Public License for more details.
19
20    You should have received a copy of the GNU General Public License
21    along with this program.  If not, see <http://www.gnu.org/licenses/>.
22 */
23
24 /*
25  *  Name: ldb
26  *
27  *  Component: ldb repl_meta_data module
28  *
29  *  Description: - add a unique objectGUID onto every new record,
30  *               - handle whenCreated, whenChanged timestamps
31  *               - handle uSNCreated, uSNChanged numbers
32  *               - handle replPropertyMetaData attribute
33  *
34  *  Author: Simo Sorce
35  *  Author: Stefan Metzmacher
36  */
37
38 #include "includes.h"
39 #include "ldb_module.h"
40 #include "dsdb/samdb/samdb.h"
41 #include "dsdb/common/proto.h"
42 #include "../libds/common/flags.h"
43 #include "librpc/gen_ndr/ndr_misc.h"
44 #include "librpc/gen_ndr/ndr_drsuapi.h"
45 #include "librpc/gen_ndr/ndr_drsblobs.h"
46 #include "param/param.h"
47 #include "libcli/security/security.h"
48 #include "lib/util/dlinklist.h"
49 #include "dsdb/samdb/ldb_modules/util.h"
50 #include "lib/util/binsearch.h"
51 #include "lib/util/tsort.h"
52
53 /*
54  * It's 29/12/9999 at 23:59:59 UTC as specified in MS-ADTS 7.1.1.4.2
55  * Deleted Objects Container
56  */
57 static const NTTIME DELETED_OBJECT_CONTAINER_CHANGE_TIME = 2650466015990000000ULL;
58
59 struct replmd_private {
60         TALLOC_CTX *la_ctx;
61         struct la_entry *la_list;
62         TALLOC_CTX *bl_ctx;
63         struct la_backlink *la_backlinks;
64         struct nc_entry {
65                 struct nc_entry *prev, *next;
66                 struct ldb_dn *dn;
67                 uint64_t mod_usn;
68                 uint64_t mod_usn_urgent;
69         } *ncs;
70         struct ldb_dn *schema_dn;
71         bool originating_updates;
72         bool sorted_links;
73 };
74
75 struct la_entry {
76         struct la_entry *next, *prev;
77         struct drsuapi_DsReplicaLinkedAttribute *la;
78 };
79
80 struct replmd_replicated_request {
81         struct ldb_module *module;
82         struct ldb_request *req;
83
84         const struct dsdb_schema *schema;
85         struct GUID our_invocation_id;
86
87         /* the controls we pass down */
88         struct ldb_control **controls;
89
90         /* details for the mode where we apply a bunch of inbound replication meessages */
91         bool apply_mode;
92         uint32_t index_current;
93         struct dsdb_extended_replicated_objects *objs;
94
95         struct ldb_message *search_msg;
96         struct GUID local_parent_guid;
97
98         uint64_t seq_num;
99         bool is_urgent;
100
101         bool isDeleted;
102 };
103
104 struct parsed_dn {
105         struct dsdb_dn *dsdb_dn;
106         struct GUID guid;
107         struct ldb_val *v;
108 };
109
110 static int replmd_replicated_apply_merge(struct replmd_replicated_request *ar);
111 static int replmd_delete_internals(struct ldb_module *module, struct ldb_request *req, bool re_delete);
112 static int replmd_check_upgrade_links(struct ldb_context *ldb,
113                                       struct parsed_dn *dns, uint32_t count,
114                                       struct ldb_message_element *el,
115                                       const char *ldap_oid);
116
117 enum urgent_situation {
118         REPL_URGENT_ON_CREATE = 1,
119         REPL_URGENT_ON_UPDATE = 2,
120         REPL_URGENT_ON_DELETE = 4
121 };
122
123 enum deletion_state {
124         OBJECT_NOT_DELETED=1,
125         OBJECT_DELETED=2,
126         OBJECT_RECYCLED=3,
127         OBJECT_TOMBSTONE=4,
128         OBJECT_REMOVED=5
129 };
130
131 static void replmd_deletion_state(struct ldb_module *module,
132                                   const struct ldb_message *msg,
133                                   enum deletion_state *current_state,
134                                   enum deletion_state *next_state)
135 {
136         int ret;
137         bool enabled = false;
138
139         if (msg == NULL) {
140                 *current_state = OBJECT_REMOVED;
141                 if (next_state != NULL) {
142                         *next_state = OBJECT_REMOVED;
143                 }
144                 return;
145         }
146
147         ret = dsdb_recyclebin_enabled(module, &enabled);
148         if (ret != LDB_SUCCESS) {
149                 enabled = false;
150         }
151
152         if (ldb_msg_check_string_attribute(msg, "isDeleted", "TRUE")) {
153                 if (!enabled) {
154                         *current_state = OBJECT_TOMBSTONE;
155                         if (next_state != NULL) {
156                                 *next_state = OBJECT_REMOVED;
157                         }
158                         return;
159                 }
160
161                 if (ldb_msg_check_string_attribute(msg, "isRecycled", "TRUE")) {
162                         *current_state = OBJECT_RECYCLED;
163                         if (next_state != NULL) {
164                                 *next_state = OBJECT_REMOVED;
165                         }
166                         return;
167                 }
168
169                 *current_state = OBJECT_DELETED;
170                 if (next_state != NULL) {
171                         *next_state = OBJECT_RECYCLED;
172                 }
173                 return;
174         }
175
176         *current_state = OBJECT_NOT_DELETED;
177         if (next_state == NULL) {
178                 return;
179         }
180
181         if (enabled) {
182                 *next_state = OBJECT_DELETED;
183         } else {
184                 *next_state = OBJECT_TOMBSTONE;
185         }
186 }
187
188 static const struct {
189         const char *update_name;
190         enum urgent_situation repl_situation;
191 } urgent_objects[] = {
192                 {"nTDSDSA", (REPL_URGENT_ON_CREATE | REPL_URGENT_ON_DELETE)},
193                 {"crossRef", (REPL_URGENT_ON_CREATE | REPL_URGENT_ON_DELETE)},
194                 {"attributeSchema", (REPL_URGENT_ON_CREATE | REPL_URGENT_ON_UPDATE)},
195                 {"classSchema", (REPL_URGENT_ON_CREATE | REPL_URGENT_ON_UPDATE)},
196                 {"secret", (REPL_URGENT_ON_CREATE | REPL_URGENT_ON_UPDATE)},
197                 {"rIDManager", (REPL_URGENT_ON_CREATE | REPL_URGENT_ON_UPDATE)},
198                 {NULL, 0}
199 };
200
201 /* Attributes looked for when updating or deleting, to check for a urgent replication needed */
202 static const char *urgent_attrs[] = {
203                 "lockoutTime",
204                 "pwdLastSet",
205                 "userAccountControl",
206                 NULL
207 };
208
209
210 static bool replmd_check_urgent_objectclass(const struct ldb_message_element *objectclass_el,
211                                         enum urgent_situation situation)
212 {
213         unsigned int i, j;
214         for (i=0; urgent_objects[i].update_name; i++) {
215
216                 if ((situation & urgent_objects[i].repl_situation) == 0) {
217                         continue;
218                 }
219
220                 for (j=0; j<objectclass_el->num_values; j++) {
221                         const struct ldb_val *v = &objectclass_el->values[j];
222                         if (ldb_attr_cmp((const char *)v->data, urgent_objects[i].update_name) == 0) {
223                                 return true;
224                         }
225                 }
226         }
227         return false;
228 }
229
230 static bool replmd_check_urgent_attribute(const struct ldb_message_element *el)
231 {
232         if (ldb_attr_in_list(urgent_attrs, el->name)) {
233                 return true;
234         }
235         return false;
236 }
237
238
239 static int replmd_replicated_apply_isDeleted(struct replmd_replicated_request *ar);
240
241 /*
242   initialise the module
243   allocate the private structure and build the list
244   of partition DNs for use by replmd_notify()
245  */
246 static int replmd_init(struct ldb_module *module)
247 {
248         struct replmd_private *replmd_private;
249         struct ldb_context *ldb = ldb_module_get_ctx(module);
250         static const char *samba_dsdb_attrs[] = { SAMBA_COMPATIBLE_FEATURES_ATTR, NULL };
251         struct ldb_dn *samba_dsdb_dn;
252         struct ldb_result *res;
253         int ret;
254         TALLOC_CTX *frame = talloc_stackframe();
255         replmd_private = talloc_zero(module, struct replmd_private);
256         if (replmd_private == NULL) {
257                 ldb_oom(ldb);
258                 TALLOC_FREE(frame);
259                 return LDB_ERR_OPERATIONS_ERROR;
260         }
261         ldb_module_set_private(module, replmd_private);
262
263         replmd_private->schema_dn = ldb_get_schema_basedn(ldb);
264
265         samba_dsdb_dn = ldb_dn_new(frame, ldb, "@SAMBA_DSDB");
266         if (!samba_dsdb_dn) {
267                 TALLOC_FREE(frame);
268                 return ldb_oom(ldb);
269         }
270
271         ret = dsdb_module_search_dn(module, frame, &res, samba_dsdb_dn,
272                                     samba_dsdb_attrs, DSDB_FLAG_NEXT_MODULE, NULL);
273         if (ret == LDB_SUCCESS) {
274                 replmd_private->sorted_links
275                         = ldb_msg_check_string_attribute(res->msgs[0],
276                                                          SAMBA_COMPATIBLE_FEATURES_ATTR,
277                                                          SAMBA_SORTED_LINKS_FEATURE);
278         }
279         TALLOC_FREE(frame);
280
281         return ldb_next_init(module);
282 }
283
284 /*
285   cleanup our per-transaction contexts
286  */
287 static void replmd_txn_cleanup(struct replmd_private *replmd_private)
288 {
289         talloc_free(replmd_private->la_ctx);
290         replmd_private->la_list = NULL;
291         replmd_private->la_ctx = NULL;
292
293         talloc_free(replmd_private->bl_ctx);
294         replmd_private->la_backlinks = NULL;
295         replmd_private->bl_ctx = NULL;
296 }
297
298
299 struct la_backlink {
300         struct la_backlink *next, *prev;
301         const char *attr_name;
302         struct GUID forward_guid, target_guid;
303         bool active;
304 };
305
306 /*
307   a ldb_modify request operating on modules below the
308   current module
309  */
310 static int linked_attr_modify(struct ldb_module *module,
311                               const struct ldb_message *message,
312                               struct ldb_request *parent)
313 {
314         struct ldb_request *mod_req;
315         int ret;
316         struct ldb_context *ldb = ldb_module_get_ctx(module);
317         TALLOC_CTX *tmp_ctx = talloc_new(module);
318         struct ldb_result *res;
319
320         res = talloc_zero(tmp_ctx, struct ldb_result);
321         if (!res) {
322                 talloc_free(tmp_ctx);
323                 return ldb_oom(ldb_module_get_ctx(module));
324         }
325
326         ret = ldb_build_mod_req(&mod_req, ldb, tmp_ctx,
327                                 message,
328                                 NULL,
329                                 res,
330                                 ldb_modify_default_callback,
331                                 parent);
332         LDB_REQ_SET_LOCATION(mod_req);
333         if (ret != LDB_SUCCESS) {
334                 talloc_free(tmp_ctx);
335                 return ret;
336         }
337
338         ret = ldb_request_add_control(mod_req, DSDB_CONTROL_REPLICATED_UPDATE_OID,
339                                       false, NULL);
340         if (ret != LDB_SUCCESS) {
341                 return ret;
342         }
343
344         /* Run the new request */
345         ret = ldb_next_request(module, mod_req);
346
347         if (ret == LDB_SUCCESS) {
348                 ret = ldb_wait(mod_req->handle, LDB_WAIT_ALL);
349         }
350
351         talloc_free(tmp_ctx);
352         return ret;
353 }
354
355 /*
356   process a backlinks we accumulated during a transaction, adding and
357   deleting the backlinks from the target objects
358  */
359 static int replmd_process_backlink(struct ldb_module *module, struct la_backlink *bl, struct ldb_request *parent)
360 {
361         struct ldb_dn *target_dn, *source_dn;
362         int ret;
363         struct ldb_context *ldb = ldb_module_get_ctx(module);
364         struct ldb_message *msg;
365         TALLOC_CTX *tmp_ctx = talloc_new(bl);
366         char *dn_string;
367
368         /*
369           - find DN of target
370           - find DN of source
371           - construct ldb_message
372               - either an add or a delete
373          */
374         ret = dsdb_module_dn_by_guid(module, tmp_ctx, &bl->target_guid, &target_dn, parent);
375         if (ret != LDB_SUCCESS) {
376                 DEBUG(2,(__location__ ": WARNING: Failed to find target DN for linked attribute with GUID %s\n",
377                          GUID_string(bl, &bl->target_guid)));
378                 return LDB_SUCCESS;
379         }
380
381         ret = dsdb_module_dn_by_guid(module, tmp_ctx, &bl->forward_guid, &source_dn, parent);
382         if (ret != LDB_SUCCESS) {
383                 ldb_asprintf_errstring(ldb, "Failed to find source DN for linked attribute with GUID %s\n",
384                                        GUID_string(bl, &bl->forward_guid));
385                 talloc_free(tmp_ctx);
386                 return ret;
387         }
388
389         msg = ldb_msg_new(tmp_ctx);
390         if (msg == NULL) {
391                 ldb_module_oom(module);
392                 talloc_free(tmp_ctx);
393                 return LDB_ERR_OPERATIONS_ERROR;
394         }
395
396         /* construct a ldb_message for adding/deleting the backlink */
397         msg->dn = target_dn;
398         dn_string = ldb_dn_get_extended_linearized(tmp_ctx, source_dn, 1);
399         if (!dn_string) {
400                 ldb_module_oom(module);
401                 talloc_free(tmp_ctx);
402                 return LDB_ERR_OPERATIONS_ERROR;
403         }
404         ret = ldb_msg_add_steal_string(msg, bl->attr_name, dn_string);
405         if (ret != LDB_SUCCESS) {
406                 talloc_free(tmp_ctx);
407                 return ret;
408         }
409         msg->elements[0].flags = bl->active?LDB_FLAG_MOD_ADD:LDB_FLAG_MOD_DELETE;
410
411         /* a backlink should never be single valued. Unfortunately the
412            exchange schema has a attribute
413            msExchBridgeheadedLocalConnectorsDNBL which is single
414            valued and a backlink. We need to cope with that by
415            ignoring the single value flag */
416         msg->elements[0].flags |= LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK;
417
418         ret = dsdb_module_modify(module, msg, DSDB_FLAG_NEXT_MODULE, parent);
419         if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE && !bl->active) {
420                 /* we allow LDB_ERR_NO_SUCH_ATTRIBUTE as success to
421                    cope with possible corruption where the backlink has
422                    already been removed */
423                 DEBUG(3,("WARNING: backlink from %s already removed from %s - %s\n",
424                          ldb_dn_get_linearized(target_dn),
425                          ldb_dn_get_linearized(source_dn),
426                          ldb_errstring(ldb)));
427                 ret = LDB_SUCCESS;
428         } else if (ret != LDB_SUCCESS) {
429                 ldb_asprintf_errstring(ldb, "Failed to %s backlink from %s to %s - %s",
430                                        bl->active?"add":"remove",
431                                        ldb_dn_get_linearized(source_dn),
432                                        ldb_dn_get_linearized(target_dn),
433                                        ldb_errstring(ldb));
434                 talloc_free(tmp_ctx);
435                 return ret;
436         }
437         talloc_free(tmp_ctx);
438         return ret;
439 }
440
441 /*
442   add a backlink to the list of backlinks to add/delete in the prepare
443   commit
444  */
445 static int replmd_add_backlink(struct ldb_module *module,
446                                struct replmd_private *replmd_private,
447                                const struct dsdb_schema *schema,
448                                struct GUID *forward_guid,
449                                struct GUID *target_guid, bool active,
450                                const struct dsdb_attribute *schema_attr,
451                                bool immediate)
452 {
453         const struct dsdb_attribute *target_attr;
454         struct la_backlink *bl;
455
456         target_attr = dsdb_attribute_by_linkID(schema, schema_attr->linkID ^ 1);
457         if (!target_attr) {
458                 /*
459                  * windows 2003 has a broken schema where the
460                  * definition of msDS-IsDomainFor is missing (which is
461                  * supposed to be the backlink of the
462                  * msDS-HasDomainNCs attribute
463                  */
464                 return LDB_SUCCESS;
465         }
466
467         /* see if its already in the list */
468         for (bl=replmd_private->la_backlinks; bl; bl=bl->next) {
469                 if (GUID_equal(forward_guid, &bl->forward_guid) &&
470                     GUID_equal(target_guid, &bl->target_guid) &&
471                     (target_attr->lDAPDisplayName == bl->attr_name ||
472                      strcmp(target_attr->lDAPDisplayName, bl->attr_name) == 0)) {
473                         break;
474                 }
475         }
476
477         if (bl) {
478                 /* we found an existing one */
479                 if (bl->active == active) {
480                         return LDB_SUCCESS;
481                 }
482                 DLIST_REMOVE(replmd_private->la_backlinks, bl);
483                 talloc_free(bl);
484                 return LDB_SUCCESS;
485         }
486
487         if (replmd_private->bl_ctx == NULL) {
488                 replmd_private->bl_ctx = talloc_new(replmd_private);
489                 if (replmd_private->bl_ctx == NULL) {
490                         ldb_module_oom(module);
491                         return LDB_ERR_OPERATIONS_ERROR;
492                 }
493         }
494
495         /* its a new one */
496         bl = talloc(replmd_private->bl_ctx, struct la_backlink);
497         if (bl == NULL) {
498                 ldb_module_oom(module);
499                 return LDB_ERR_OPERATIONS_ERROR;
500         }
501
502         /* Ensure the schema does not go away before the bl->attr_name is used */
503         if (!talloc_reference(bl, schema)) {
504                 talloc_free(bl);
505                 ldb_module_oom(module);
506                 return LDB_ERR_OPERATIONS_ERROR;
507         }
508
509         bl->attr_name = target_attr->lDAPDisplayName;
510         bl->forward_guid = *forward_guid;
511         bl->target_guid = *target_guid;
512         bl->active = active;
513
514         /* the caller may ask for this backlink to be processed
515            immediately */
516         if (immediate) {
517                 int ret = replmd_process_backlink(module, bl, NULL);
518                 talloc_free(bl);
519                 return ret;
520         }
521
522         DLIST_ADD(replmd_private->la_backlinks, bl);
523
524         return LDB_SUCCESS;
525 }
526
527
528 /*
529  * Callback for most write operations in this module:
530  *
531  * notify the repl task that a object has changed. The notifies are
532  * gathered up in the replmd_private structure then written to the
533  * @REPLCHANGED object in each partition during the prepare_commit
534  */
535 static int replmd_op_callback(struct ldb_request *req, struct ldb_reply *ares)
536 {
537         int ret;
538         struct replmd_replicated_request *ac =
539                 talloc_get_type_abort(req->context, struct replmd_replicated_request);
540         struct replmd_private *replmd_private =
541                 talloc_get_type_abort(ldb_module_get_private(ac->module), struct replmd_private);
542         struct nc_entry *modified_partition;
543         struct ldb_control *partition_ctrl;
544         const struct dsdb_control_current_partition *partition;
545
546         struct ldb_control **controls;
547
548         partition_ctrl = ldb_reply_get_control(ares, DSDB_CONTROL_CURRENT_PARTITION_OID);
549
550         controls = ares->controls;
551         if (ldb_request_get_control(ac->req,
552                                     DSDB_CONTROL_CURRENT_PARTITION_OID) == NULL) {
553                 /*
554                  * Remove the current partition control from what we pass up
555                  * the chain if it hasn't been requested manually.
556                  */
557                 controls = ldb_controls_except_specified(ares->controls, ares,
558                                                          partition_ctrl);
559         }
560
561         if (ares->error != LDB_SUCCESS) {
562                 DEBUG(5,("%s failure. Error is: %s\n", __FUNCTION__, ldb_strerror(ares->error)));
563                 return ldb_module_done(ac->req, controls,
564                                         ares->response, ares->error);
565         }
566
567         if (ares->type != LDB_REPLY_DONE) {
568                 ldb_set_errstring(ldb_module_get_ctx(ac->module), "Invalid reply type for notify\n!");
569                 return ldb_module_done(ac->req, NULL,
570                                        NULL, LDB_ERR_OPERATIONS_ERROR);
571         }
572
573         if (!partition_ctrl) {
574                 ldb_set_errstring(ldb_module_get_ctx(ac->module),"No partition control on reply");
575                 return ldb_module_done(ac->req, NULL,
576                                        NULL, LDB_ERR_OPERATIONS_ERROR);
577         }
578
579         partition = talloc_get_type_abort(partition_ctrl->data,
580                                     struct dsdb_control_current_partition);
581
582         if (ac->seq_num > 0) {
583                 for (modified_partition = replmd_private->ncs; modified_partition;
584                      modified_partition = modified_partition->next) {
585                         if (ldb_dn_compare(modified_partition->dn, partition->dn) == 0) {
586                                 break;
587                         }
588                 }
589
590                 if (modified_partition == NULL) {
591                         modified_partition = talloc_zero(replmd_private, struct nc_entry);
592                         if (!modified_partition) {
593                                 ldb_oom(ldb_module_get_ctx(ac->module));
594                                 return ldb_module_done(ac->req, NULL,
595                                                        NULL, LDB_ERR_OPERATIONS_ERROR);
596                         }
597                         modified_partition->dn = ldb_dn_copy(modified_partition, partition->dn);
598                         if (!modified_partition->dn) {
599                                 ldb_oom(ldb_module_get_ctx(ac->module));
600                                 return ldb_module_done(ac->req, NULL,
601                                                        NULL, LDB_ERR_OPERATIONS_ERROR);
602                         }
603                         DLIST_ADD(replmd_private->ncs, modified_partition);
604                 }
605
606                 if (ac->seq_num > modified_partition->mod_usn) {
607                         modified_partition->mod_usn = ac->seq_num;
608                         if (ac->is_urgent) {
609                                 modified_partition->mod_usn_urgent = ac->seq_num;
610                         }
611                 }
612                 if (!ac->apply_mode) {
613                         replmd_private->originating_updates = true;
614                 }
615         }
616
617         if (ac->apply_mode) {
618                 ret = replmd_replicated_apply_isDeleted(ac);
619                 if (ret != LDB_SUCCESS) {
620                         return ldb_module_done(ac->req, NULL, NULL, ret);
621                 }
622                 return ret;
623         } else {
624                 /* free the partition control container here, for the
625                  * common path.  Other cases will have it cleaned up
626                  * eventually with the ares */
627                 talloc_free(partition_ctrl);
628                 return ldb_module_done(ac->req, controls,
629                                        ares->response, LDB_SUCCESS);
630         }
631 }
632
633
634 /*
635  * update a @REPLCHANGED record in each partition if there have been
636  * any writes of replicated data in the partition
637  */
638 static int replmd_notify_store(struct ldb_module *module, struct ldb_request *parent)
639 {
640         struct replmd_private *replmd_private =
641                 talloc_get_type(ldb_module_get_private(module), struct replmd_private);
642
643         while (replmd_private->ncs) {
644                 int ret;
645                 struct nc_entry *modified_partition = replmd_private->ncs;
646
647                 ret = dsdb_module_save_partition_usn(module, modified_partition->dn,
648                                                      modified_partition->mod_usn,
649                                                      modified_partition->mod_usn_urgent, parent);
650                 if (ret != LDB_SUCCESS) {
651                         DEBUG(0,(__location__ ": Failed to save partition uSN for %s\n",
652                                  ldb_dn_get_linearized(modified_partition->dn)));
653                         return ret;
654                 }
655
656                 if (ldb_dn_compare(modified_partition->dn,
657                                    replmd_private->schema_dn) == 0) {
658                         struct ldb_result *ext_res;
659                         ret = dsdb_module_extended(module,
660                                                    replmd_private->schema_dn,
661                                                    &ext_res,
662                                                    DSDB_EXTENDED_SCHEMA_UPDATE_NOW_OID,
663                                                    ext_res,
664                                                    DSDB_FLAG_NEXT_MODULE,
665                                                    parent);
666                         if (ret != LDB_SUCCESS) {
667                                 return ret;
668                         }
669                         talloc_free(ext_res);
670                 }
671
672                 DLIST_REMOVE(replmd_private->ncs, modified_partition);
673                 talloc_free(modified_partition);
674         }
675
676         return LDB_SUCCESS;
677 }
678
679
680 /*
681   created a replmd_replicated_request context
682  */
683 static struct replmd_replicated_request *replmd_ctx_init(struct ldb_module *module,
684                                                          struct ldb_request *req)
685 {
686         struct ldb_context *ldb;
687         struct replmd_replicated_request *ac;
688         const struct GUID *our_invocation_id;
689
690         ldb = ldb_module_get_ctx(module);
691
692         ac = talloc_zero(req, struct replmd_replicated_request);
693         if (ac == NULL) {
694                 ldb_oom(ldb);
695                 return NULL;
696         }
697
698         ac->module = module;
699         ac->req = req;
700
701         ac->schema = dsdb_get_schema(ldb, ac);
702         if (!ac->schema) {
703                 ldb_debug_set(ldb, LDB_DEBUG_FATAL,
704                               "replmd_modify: no dsdb_schema loaded");
705                 DEBUG(0,(__location__ ": %s\n", ldb_errstring(ldb)));
706                 talloc_free(ac);
707                 return NULL;
708         }
709
710         /* get our invocationId */
711         our_invocation_id = samdb_ntds_invocation_id(ldb);
712         if (!our_invocation_id) {
713                 ldb_debug_set(ldb, LDB_DEBUG_FATAL,
714                               "replmd_add: unable to find invocationId\n");
715                 talloc_free(ac);
716                 return NULL;
717         }
718         ac->our_invocation_id = *our_invocation_id;
719
720         return ac;
721 }
722
723 /*
724   add a time element to a record
725 */
726 static int add_time_element(struct ldb_message *msg, const char *attr, time_t t)
727 {
728         struct ldb_message_element *el;
729         char *s;
730         int ret;
731
732         if (ldb_msg_find_element(msg, attr) != NULL) {
733                 return LDB_SUCCESS;
734         }
735
736         s = ldb_timestring(msg, t);
737         if (s == NULL) {
738                 return LDB_ERR_OPERATIONS_ERROR;
739         }
740
741         ret = ldb_msg_add_string(msg, attr, s);
742         if (ret != LDB_SUCCESS) {
743                 return ret;
744         }
745
746         el = ldb_msg_find_element(msg, attr);
747         /* always set as replace. This works because on add ops, the flag
748            is ignored */
749         el->flags = LDB_FLAG_MOD_REPLACE;
750
751         return LDB_SUCCESS;
752 }
753
754 /*
755   add a uint64_t element to a record
756 */
757 static int add_uint64_element(struct ldb_context *ldb, struct ldb_message *msg,
758                               const char *attr, uint64_t v)
759 {
760         struct ldb_message_element *el;
761         int ret;
762
763         if (ldb_msg_find_element(msg, attr) != NULL) {
764                 return LDB_SUCCESS;
765         }
766
767         ret = samdb_msg_add_uint64(ldb, msg, msg, attr, v);
768         if (ret != LDB_SUCCESS) {
769                 return ret;
770         }
771
772         el = ldb_msg_find_element(msg, attr);
773         /* always set as replace. This works because on add ops, the flag
774            is ignored */
775         el->flags = LDB_FLAG_MOD_REPLACE;
776
777         return LDB_SUCCESS;
778 }
779
780 static int replmd_replPropertyMetaData1_attid_sort(const struct replPropertyMetaData1 *m1,
781                                                    const struct replPropertyMetaData1 *m2,
782                                                    const uint32_t *rdn_attid)
783 {
784         /*
785          * This assignment seems inoccous, but it is critical for the
786          * system, as we need to do the comparisons as a unsigned
787          * quantity, not signed (enums are signed integers)
788          */
789         uint32_t attid_1 = m1->attid;
790         uint32_t attid_2 = m2->attid;
791
792         if (attid_1 == attid_2) {
793                 return 0;
794         }
795
796         /*
797          * See above regarding this being an unsigned comparison.
798          * Otherwise when the high bit is set on non-standard
799          * attributes, they would end up first, before objectClass
800          * (0).
801          */
802         return attid_1 > attid_2 ? 1 : -1;
803 }
804
805 static int replmd_replPropertyMetaDataCtr1_verify(struct ldb_context *ldb,
806                                                   struct replPropertyMetaDataCtr1 *ctr1,
807                                                   struct ldb_dn *dn)
808 {
809         if (ctr1->count == 0) {
810                 ldb_debug_set(ldb, LDB_DEBUG_FATAL,
811                               "No elements found in replPropertyMetaData for %s!\n",
812                               ldb_dn_get_linearized(dn));
813                 return LDB_ERR_CONSTRAINT_VIOLATION;
814         }
815
816         /* the objectClass attribute is value 0x00000000, so must be first */
817         if (ctr1->array[0].attid != DRSUAPI_ATTID_objectClass) {
818                 ldb_debug_set(ldb, LDB_DEBUG_FATAL,
819                               "No objectClass found in replPropertyMetaData for %s!\n",
820                               ldb_dn_get_linearized(dn));
821                 return LDB_ERR_OBJECT_CLASS_VIOLATION;
822         }
823
824         return LDB_SUCCESS;
825 }
826
827 static int replmd_replPropertyMetaDataCtr1_sort_and_verify(struct ldb_context *ldb,
828                                                            struct replPropertyMetaDataCtr1 *ctr1,
829                                                            struct ldb_dn *dn)
830 {
831         /* Note this is O(n^2) for the almost-sorted case, which this is */
832         LDB_TYPESAFE_QSORT(ctr1->array, ctr1->count, NULL,
833                            replmd_replPropertyMetaData1_attid_sort);
834         return replmd_replPropertyMetaDataCtr1_verify(ldb, ctr1, dn);
835 }
836
837 static int replmd_ldb_message_element_attid_sort(const struct ldb_message_element *e1,
838                                                  const struct ldb_message_element *e2,
839                                                  const struct dsdb_schema *schema)
840 {
841         const struct dsdb_attribute *a1;
842         const struct dsdb_attribute *a2;
843
844         /*
845          * TODO: make this faster by caching the dsdb_attribute pointer
846          *       on the ldb_messag_element
847          */
848
849         a1 = dsdb_attribute_by_lDAPDisplayName(schema, e1->name);
850         a2 = dsdb_attribute_by_lDAPDisplayName(schema, e2->name);
851
852         /*
853          * TODO: remove this check, we should rely on e1 and e2 having valid attribute names
854          *       in the schema
855          */
856         if (!a1 || !a2) {
857                 return strcasecmp(e1->name, e2->name);
858         }
859         if (a1->attributeID_id == a2->attributeID_id) {
860                 return 0;
861         }
862         return a1->attributeID_id > a2->attributeID_id ? 1 : -1;
863 }
864
865 static void replmd_ldb_message_sort(struct ldb_message *msg,
866                                     const struct dsdb_schema *schema)
867 {
868         LDB_TYPESAFE_QSORT(msg->elements, msg->num_elements, schema, replmd_ldb_message_element_attid_sort);
869 }
870
871 static int replmd_build_la_val(TALLOC_CTX *mem_ctx, struct ldb_val *v, struct dsdb_dn *dsdb_dn,
872                                const struct GUID *invocation_id, uint64_t seq_num,
873                                uint64_t local_usn, NTTIME nttime, uint32_t version, bool deleted);
874
875 static int get_parsed_dns(struct ldb_module *module, TALLOC_CTX *mem_ctx,
876                           struct ldb_message_element *el, struct parsed_dn **pdn,
877                           const char *ldap_oid, struct ldb_request *parent);
878
879 /*
880   fix up linked attributes in replmd_add.
881   This involves setting up the right meta-data in extended DN
882   components, and creating backlinks to the object
883  */
884 static int replmd_add_fix_la(struct ldb_module *module, TALLOC_CTX *mem_ctx,
885                              struct replmd_private *replmd_private,
886                              struct ldb_message_element *el,
887                              uint64_t seq_num, const struct GUID *invocationId, NTTIME now,
888                              struct GUID *guid, const struct dsdb_attribute *sa,
889                              struct ldb_request *parent)
890 {
891         unsigned int i;
892         TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
893         struct ldb_context *ldb = ldb_module_get_ctx(module);
894         struct parsed_dn *pdn;
895         /* We will take a reference to the schema in replmd_add_backlink */
896         const struct dsdb_schema *schema = dsdb_get_schema(ldb, NULL);
897         struct ldb_val *new_values = NULL;
898
899         int ret = get_parsed_dns(module, tmp_ctx, el, &pdn,
900                                  sa->syntax->ldap_oid, parent);
901         if (ret != LDB_SUCCESS) {
902                 talloc_free(tmp_ctx);
903                 return ret;
904         }
905
906         new_values = talloc_array(tmp_ctx, struct ldb_val, el->num_values);
907         if (new_values == NULL) {
908                 ldb_module_oom(module);
909                 talloc_free(tmp_ctx);
910                 return LDB_ERR_OPERATIONS_ERROR;
911         }
912
913         for (i = 0; i < el->num_values; i++) {
914                 struct parsed_dn *p = &pdn[i];
915                 ret = replmd_build_la_val(el->values, p->v, p->dsdb_dn,
916                                           invocationId,
917                                           seq_num, seq_num, now, 0, false);
918                 if (ret != LDB_SUCCESS) {
919                         talloc_free(tmp_ctx);
920                         return ret;
921                 }
922
923                 /* This is the only place we are doing deferred back-links */
924                 ret = replmd_add_backlink(module, replmd_private,
925                                           schema, guid, &p->guid, true, sa,
926                                           false);
927                 if (ret != LDB_SUCCESS) {
928                         talloc_free(tmp_ctx);
929                         return ret;
930                 }
931
932                 new_values[i] = *p->v;
933         }
934         el->values = talloc_steal(mem_ctx, new_values);
935
936         talloc_free(tmp_ctx);
937         return LDB_SUCCESS;
938 }
939
940
941 /*
942   intercept add requests
943  */
944 static int replmd_add(struct ldb_module *module, struct ldb_request *req)
945 {
946         struct ldb_context *ldb;
947         struct ldb_control *control;
948         struct replmd_replicated_request *ac;
949         enum ndr_err_code ndr_err;
950         struct ldb_request *down_req;
951         struct ldb_message *msg;
952         const DATA_BLOB *guid_blob;
953         struct GUID guid;
954         struct replPropertyMetaDataBlob nmd;
955         struct ldb_val nmd_value;
956
957         /*
958          * The use of a time_t here seems odd, but as the NTTIME
959          * elements are actually declared as NTTIME_1sec in the IDL,
960          * getting a higher resolution timestamp is not required.
961          */
962         time_t t = time(NULL);
963         NTTIME now;
964         char *time_str;
965         int ret;
966         unsigned int i;
967         unsigned int functional_level;
968         uint32_t ni=0;
969         bool allow_add_guid = false;
970         bool remove_current_guid = false;
971         bool is_urgent = false;
972         bool is_schema_nc = false;
973         struct ldb_message_element *objectclass_el;
974         struct replmd_private *replmd_private =
975                 talloc_get_type_abort(ldb_module_get_private(module), struct replmd_private);
976
977         /* check if there's a show relax control (used by provision to say 'I know what I'm doing') */
978         control = ldb_request_get_control(req, LDB_CONTROL_RELAX_OID);
979         if (control) {
980                 allow_add_guid = true;
981         }
982
983         /* do not manipulate our control entries */
984         if (ldb_dn_is_special(req->op.add.message->dn)) {
985                 return ldb_next_request(module, req);
986         }
987
988         ldb = ldb_module_get_ctx(module);
989
990         ldb_debug(ldb, LDB_DEBUG_TRACE, "replmd_add\n");
991
992         guid_blob = ldb_msg_find_ldb_val(req->op.add.message, "objectGUID");
993         if (guid_blob != NULL) {
994                 if (!allow_add_guid) {
995                         ldb_set_errstring(ldb,
996                                           "replmd_add: it's not allowed to add an object with objectGUID!");
997                         return LDB_ERR_UNWILLING_TO_PERFORM;
998                 } else {
999                         NTSTATUS status = GUID_from_data_blob(guid_blob,&guid);
1000                         if (!NT_STATUS_IS_OK(status)) {
1001                                 ldb_set_errstring(ldb,
1002                                                   "replmd_add: Unable to parse the 'objectGUID' as a GUID!");
1003                                 return LDB_ERR_UNWILLING_TO_PERFORM;
1004                         }
1005                         /* we remove this attribute as it can be a string and
1006                          * will not be treated correctly and then we will re-add
1007                          * it later on in the good format */
1008                         remove_current_guid = true;
1009                 }
1010         } else {
1011                 /* a new GUID */
1012                 guid = GUID_random();
1013         }
1014
1015         ac = replmd_ctx_init(module, req);
1016         if (ac == NULL) {
1017                 return ldb_module_oom(module);
1018         }
1019
1020         functional_level = dsdb_functional_level(ldb);
1021
1022         /* Get a sequence number from the backend */
1023         ret = ldb_sequence_number(ldb, LDB_SEQ_NEXT, &ac->seq_num);
1024         if (ret != LDB_SUCCESS) {
1025                 talloc_free(ac);
1026                 return ret;
1027         }
1028
1029         /* we have to copy the message as the caller might have it as a const */
1030         msg = ldb_msg_copy_shallow(ac, req->op.add.message);
1031         if (msg == NULL) {
1032                 ldb_oom(ldb);
1033                 talloc_free(ac);
1034                 return LDB_ERR_OPERATIONS_ERROR;
1035         }
1036
1037         /* generated times */
1038         unix_to_nt_time(&now, t);
1039         time_str = ldb_timestring(msg, t);
1040         if (!time_str) {
1041                 ldb_oom(ldb);
1042                 talloc_free(ac);
1043                 return LDB_ERR_OPERATIONS_ERROR;
1044         }
1045         if (remove_current_guid) {
1046                 ldb_msg_remove_attr(msg,"objectGUID");
1047         }
1048
1049         /*
1050          * remove autogenerated attributes
1051          */
1052         ldb_msg_remove_attr(msg, "whenCreated");
1053         ldb_msg_remove_attr(msg, "whenChanged");
1054         ldb_msg_remove_attr(msg, "uSNCreated");
1055         ldb_msg_remove_attr(msg, "uSNChanged");
1056         ldb_msg_remove_attr(msg, "replPropertyMetaData");
1057
1058         /*
1059          * readd replicated attributes
1060          */
1061         ret = ldb_msg_add_string(msg, "whenCreated", time_str);
1062         if (ret != LDB_SUCCESS) {
1063                 ldb_oom(ldb);
1064                 talloc_free(ac);
1065                 return ret;
1066         }
1067
1068         /* build the replication meta_data */
1069         ZERO_STRUCT(nmd);
1070         nmd.version             = 1;
1071         nmd.ctr.ctr1.count      = msg->num_elements;
1072         nmd.ctr.ctr1.array      = talloc_array(msg,
1073                                                struct replPropertyMetaData1,
1074                                                nmd.ctr.ctr1.count);
1075         if (!nmd.ctr.ctr1.array) {
1076                 ldb_oom(ldb);
1077                 talloc_free(ac);
1078                 return LDB_ERR_OPERATIONS_ERROR;
1079         }
1080
1081         is_schema_nc = ldb_dn_compare_base(replmd_private->schema_dn, msg->dn) == 0;
1082
1083         for (i=0; i < msg->num_elements;) {
1084                 struct ldb_message_element *e = &msg->elements[i];
1085                 struct replPropertyMetaData1 *m = &nmd.ctr.ctr1.array[ni];
1086                 const struct dsdb_attribute *sa;
1087
1088                 if (e->name[0] == '@') {
1089                         i++;
1090                         continue;
1091                 }
1092
1093                 sa = dsdb_attribute_by_lDAPDisplayName(ac->schema, e->name);
1094                 if (!sa) {
1095                         ldb_debug_set(ldb, LDB_DEBUG_ERROR,
1096                                       "replmd_add: attribute '%s' not defined in schema\n",
1097                                       e->name);
1098                         talloc_free(ac);
1099                         return LDB_ERR_NO_SUCH_ATTRIBUTE;
1100                 }
1101
1102                 if ((sa->systemFlags & DS_FLAG_ATTR_NOT_REPLICATED) || (sa->systemFlags & DS_FLAG_ATTR_IS_CONSTRUCTED)) {
1103                         /* if the attribute is not replicated (0x00000001)
1104                          * or constructed (0x00000004) it has no metadata
1105                          */
1106                         i++;
1107                         continue;
1108                 }
1109
1110                 if (sa->linkID != 0 && functional_level > DS_DOMAIN_FUNCTION_2000) {
1111                         ret = replmd_add_fix_la(module, msg->elements,
1112                                                 replmd_private, e,
1113                                                 ac->seq_num,
1114                                                 &ac->our_invocation_id, now,
1115                                                 &guid, sa, req);
1116                         if (ret != LDB_SUCCESS) {
1117                                 talloc_free(ac);
1118                                 return ret;
1119                         }
1120                         /* linked attributes are not stored in
1121                            replPropertyMetaData in FL above w2k */
1122                         i++;
1123                         continue;
1124                 }
1125
1126                 m->attid   = dsdb_attribute_get_attid(sa, is_schema_nc);
1127                 m->version = 1;
1128                 if (m->attid == DRSUAPI_ATTID_isDeleted) {
1129                         const struct ldb_val *rdn_val = ldb_dn_get_rdn_val(msg->dn);
1130                         const char* rdn;
1131
1132                         if (rdn_val == NULL) {
1133                                 ldb_oom(ldb);
1134                                 talloc_free(ac);
1135                                 return LDB_ERR_OPERATIONS_ERROR;
1136                         }
1137
1138                         rdn = (const char*)rdn_val->data;
1139                         if (strcmp(rdn, "Deleted Objects") == 0) {
1140                                 /*
1141                                  * Set the originating_change_time to 29/12/9999 at 23:59:59
1142                                  * as specified in MS-ADTS 7.1.1.4.2 Deleted Objects Container
1143                                  */
1144                                 m->originating_change_time      = DELETED_OBJECT_CONTAINER_CHANGE_TIME;
1145                         } else {
1146                                 m->originating_change_time      = now;
1147                         }
1148                 } else {
1149                         m->originating_change_time      = now;
1150                 }
1151                 m->originating_invocation_id    = ac->our_invocation_id;
1152                 m->originating_usn              = ac->seq_num;
1153                 m->local_usn                    = ac->seq_num;
1154                 ni++;
1155
1156                 if (!(e->flags & DSDB_FLAG_INTERNAL_FORCE_META_DATA)) {
1157                         i++;
1158                         continue;
1159                 }
1160
1161                 e->flags &= ~DSDB_FLAG_INTERNAL_FORCE_META_DATA;
1162
1163                 if (e->num_values != 0) {
1164                         i++;
1165                         continue;
1166                 }
1167
1168                 ldb_msg_remove_element(msg, e);
1169         }
1170
1171         /* fix meta data count */
1172         nmd.ctr.ctr1.count = ni;
1173
1174         /*
1175          * sort meta data array
1176          */
1177         ret = replmd_replPropertyMetaDataCtr1_sort_and_verify(ldb, &nmd.ctr.ctr1, msg->dn);
1178         if (ret != LDB_SUCCESS) {
1179                 ldb_asprintf_errstring(ldb, "%s: error during direct ADD: %s", __func__, ldb_errstring(ldb));
1180                 talloc_free(ac);
1181                 return ret;
1182         }
1183
1184         /* generated NDR encoded values */
1185         ndr_err = ndr_push_struct_blob(&nmd_value, msg,
1186                                        &nmd,
1187                                        (ndr_push_flags_fn_t)ndr_push_replPropertyMetaDataBlob);
1188         if (!NDR_ERR_CODE_IS_SUCCESS(ndr_err)) {
1189                 ldb_oom(ldb);
1190                 talloc_free(ac);
1191                 return LDB_ERR_OPERATIONS_ERROR;
1192         }
1193
1194         /*
1195          * add the autogenerated values
1196          */
1197         ret = dsdb_msg_add_guid(msg, &guid, "objectGUID");
1198         if (ret != LDB_SUCCESS) {
1199                 ldb_oom(ldb);
1200                 talloc_free(ac);
1201                 return ret;
1202         }
1203         ret = ldb_msg_add_string(msg, "whenChanged", time_str);
1204         if (ret != LDB_SUCCESS) {
1205                 ldb_oom(ldb);
1206                 talloc_free(ac);
1207                 return ret;
1208         }
1209         ret = samdb_msg_add_uint64(ldb, msg, msg, "uSNCreated", ac->seq_num);
1210         if (ret != LDB_SUCCESS) {
1211                 ldb_oom(ldb);
1212                 talloc_free(ac);
1213                 return ret;
1214         }
1215         ret = samdb_msg_add_uint64(ldb, msg, msg, "uSNChanged", ac->seq_num);
1216         if (ret != LDB_SUCCESS) {
1217                 ldb_oom(ldb);
1218                 talloc_free(ac);
1219                 return ret;
1220         }
1221         ret = ldb_msg_add_value(msg, "replPropertyMetaData", &nmd_value, NULL);
1222         if (ret != LDB_SUCCESS) {
1223                 ldb_oom(ldb);
1224                 talloc_free(ac);
1225                 return ret;
1226         }
1227
1228         /*
1229          * sort the attributes by attid before storing the object
1230          */
1231         replmd_ldb_message_sort(msg, ac->schema);
1232
1233         /*
1234          * Assert that we do have an objectClass
1235          */
1236         objectclass_el = ldb_msg_find_element(msg, "objectClass");
1237         if (objectclass_el == NULL) {
1238                 ldb_asprintf_errstring(ldb, __location__
1239                                        ": objectClass missing on %s\n",
1240                                        ldb_dn_get_linearized(msg->dn));
1241                 talloc_free(ac);
1242                 return LDB_ERR_OBJECT_CLASS_VIOLATION;
1243         }
1244         is_urgent = replmd_check_urgent_objectclass(objectclass_el,
1245                                                         REPL_URGENT_ON_CREATE);
1246
1247         ac->is_urgent = is_urgent;
1248         ret = ldb_build_add_req(&down_req, ldb, ac,
1249                                 msg,
1250                                 req->controls,
1251                                 ac, replmd_op_callback,
1252                                 req);
1253
1254         LDB_REQ_SET_LOCATION(down_req);
1255         if (ret != LDB_SUCCESS) {
1256                 talloc_free(ac);
1257                 return ret;
1258         }
1259
1260         /* current partition control is needed by "replmd_op_callback" */
1261         if (ldb_request_get_control(req, DSDB_CONTROL_CURRENT_PARTITION_OID) == NULL) {
1262                 ret = ldb_request_add_control(down_req,
1263                                               DSDB_CONTROL_CURRENT_PARTITION_OID,
1264                                               false, NULL);
1265                 if (ret != LDB_SUCCESS) {
1266                         talloc_free(ac);
1267                         return ret;
1268                 }
1269         }
1270
1271         if (functional_level == DS_DOMAIN_FUNCTION_2000) {
1272                 ret = ldb_request_add_control(down_req, DSDB_CONTROL_APPLY_LINKS, false, NULL);
1273                 if (ret != LDB_SUCCESS) {
1274                         talloc_free(ac);
1275                         return ret;
1276                 }
1277         }
1278
1279         /* mark the control done */
1280         if (control) {
1281                 control->critical = 0;
1282         }
1283         /* go on with the call chain */
1284         return ldb_next_request(module, down_req);
1285 }
1286
1287
1288 /*
1289  * update the replPropertyMetaData for one element
1290  */
1291 static int replmd_update_rpmd_element(struct ldb_context *ldb,
1292                                       struct ldb_message *msg,
1293                                       struct ldb_message_element *el,
1294                                       struct ldb_message_element *old_el,
1295                                       struct replPropertyMetaDataBlob *omd,
1296                                       const struct dsdb_schema *schema,
1297                                       uint64_t *seq_num,
1298                                       const struct GUID *our_invocation_id,
1299                                       NTTIME now,
1300                                       bool is_schema_nc,
1301                                       struct ldb_request *req)
1302 {
1303         uint32_t i;
1304         const struct dsdb_attribute *a;
1305         struct replPropertyMetaData1 *md1;
1306         bool may_skip = false;
1307         uint32_t attid;
1308
1309         a = dsdb_attribute_by_lDAPDisplayName(schema, el->name);
1310         if (a == NULL) {
1311                 if (ldb_request_get_control(req, LDB_CONTROL_RELAX_OID)) {
1312                         /* allow this to make it possible for dbcheck
1313                            to remove bad attributes */
1314                         return LDB_SUCCESS;
1315                 }
1316
1317                 DEBUG(0,(__location__ ": Unable to find attribute %s in schema\n",
1318                          el->name));
1319                 return LDB_ERR_OPERATIONS_ERROR;
1320         }
1321
1322         attid = dsdb_attribute_get_attid(a, is_schema_nc);
1323
1324         if ((a->systemFlags & DS_FLAG_ATTR_NOT_REPLICATED) || (a->systemFlags & DS_FLAG_ATTR_IS_CONSTRUCTED)) {
1325                 return LDB_SUCCESS;
1326         }
1327
1328         /*
1329          * if the attribute's value haven't changed, and this isn't
1330          * just a delete of everything then return LDB_SUCCESS Unless
1331          * we have the provision control or if the attribute is
1332          * interSiteTopologyGenerator as this page explain:
1333          * http://support.microsoft.com/kb/224815 this attribute is
1334          * periodicaly written by the DC responsible for the intersite
1335          * generation in a given site
1336          *
1337          * Unchanged could be deleting or replacing an already-gone
1338          * thing with an unconstrained delete/empty replace or a
1339          * replace with the same value, but not an add with the same
1340          * value because that could be about adding a duplicate (which
1341          * is for someone else to error out on).
1342          */
1343         if (old_el != NULL && ldb_msg_element_equal_ordered(el, old_el)) {
1344                 if (LDB_FLAG_MOD_TYPE(el->flags) == LDB_FLAG_MOD_REPLACE) {
1345                         may_skip = true;
1346                 }
1347         } else if (old_el == NULL && el->num_values == 0) {
1348                 if (LDB_FLAG_MOD_TYPE(el->flags) == LDB_FLAG_MOD_REPLACE) {
1349                         may_skip = true;
1350                 } else if (LDB_FLAG_MOD_TYPE(el->flags) == LDB_FLAG_MOD_DELETE) {
1351                         may_skip = true;
1352                 }
1353         } else if (a->linkID != 0 && LDB_FLAG_MOD_TYPE(el->flags) == LDB_FLAG_MOD_DELETE &&
1354                    ldb_request_get_control(req, DSDB_CONTROL_REPLMD_VANISH_LINKS) != NULL) {
1355                 /*
1356                  * We intentionally skip the version bump when attempting to
1357                  * vanish links.
1358                  *
1359                  * The control is set by dbcheck and expunge-tombstones which
1360                  * both attempt to be non-replicating. Otherwise, making an
1361                  * alteration to the replication state would trigger a
1362                  * broadcast of all expunged objects.
1363                  */
1364                 may_skip = true;
1365         }
1366
1367         if (el->flags & DSDB_FLAG_INTERNAL_FORCE_META_DATA) {
1368                 may_skip = false;
1369                 el->flags &= ~DSDB_FLAG_INTERNAL_FORCE_META_DATA;
1370         }
1371
1372         if (may_skip) {
1373                 if (strcmp(el->name, "interSiteTopologyGenerator") != 0 &&
1374                     !ldb_request_get_control(req, LDB_CONTROL_PROVISION_OID)) {
1375                         /*
1376                          * allow this to make it possible for dbcheck
1377                          * to rebuild broken metadata
1378                          */
1379                         return LDB_SUCCESS;
1380                 }
1381         }
1382
1383         for (i=0; i<omd->ctr.ctr1.count; i++) {
1384                 /*
1385                  * First check if we find it under the msDS-IntID,
1386                  * then check if we find it under the OID and
1387                  * prefixMap ID.
1388                  *
1389                  * This allows the administrator to simply re-write
1390                  * the attributes and so restore replication, which is
1391                  * likely what they will try to do.
1392                  */
1393                 if (attid == omd->ctr.ctr1.array[i].attid) {
1394                         break;
1395                 }
1396
1397                 if (a->attributeID_id == omd->ctr.ctr1.array[i].attid) {
1398                         break;
1399                 }
1400         }
1401
1402         if (a->linkID != 0 && dsdb_functional_level(ldb) > DS_DOMAIN_FUNCTION_2000) {
1403                 /* linked attributes are not stored in
1404                    replPropertyMetaData in FL above w2k, but we do
1405                    raise the seqnum for the object  */
1406                 if (*seq_num == 0 &&
1407                     ldb_sequence_number(ldb, LDB_SEQ_NEXT, seq_num) != LDB_SUCCESS) {
1408                         return LDB_ERR_OPERATIONS_ERROR;
1409                 }
1410                 return LDB_SUCCESS;
1411         }
1412
1413         if (i == omd->ctr.ctr1.count) {
1414                 /* we need to add a new one */
1415                 omd->ctr.ctr1.array = talloc_realloc(msg, omd->ctr.ctr1.array,
1416                                                      struct replPropertyMetaData1, omd->ctr.ctr1.count+1);
1417                 if (omd->ctr.ctr1.array == NULL) {
1418                         ldb_oom(ldb);
1419                         return LDB_ERR_OPERATIONS_ERROR;
1420                 }
1421                 omd->ctr.ctr1.count++;
1422                 ZERO_STRUCT(omd->ctr.ctr1.array[i]);
1423         }
1424
1425         /* Get a new sequence number from the backend. We only do this
1426          * if we have a change that requires a new
1427          * replPropertyMetaData element
1428          */
1429         if (*seq_num == 0) {
1430                 int ret = ldb_sequence_number(ldb, LDB_SEQ_NEXT, seq_num);
1431                 if (ret != LDB_SUCCESS) {
1432                         return LDB_ERR_OPERATIONS_ERROR;
1433                 }
1434         }
1435
1436         md1 = &omd->ctr.ctr1.array[i];
1437         md1->version++;
1438         md1->attid = attid;
1439         if (md1->attid == DRSUAPI_ATTID_isDeleted) {
1440                 const struct ldb_val *rdn_val = ldb_dn_get_rdn_val(msg->dn);
1441                 const char* rdn;
1442
1443                 if (rdn_val == NULL) {
1444                         ldb_oom(ldb);
1445                         return LDB_ERR_OPERATIONS_ERROR;
1446                 }
1447
1448                 rdn = (const char*)rdn_val->data;
1449                 if (strcmp(rdn, "Deleted Objects") == 0) {
1450                         /*
1451                          * Set the originating_change_time to 29/12/9999 at 23:59:59
1452                          * as specified in MS-ADTS 7.1.1.4.2 Deleted Objects Container
1453                          */
1454                         md1->originating_change_time    = DELETED_OBJECT_CONTAINER_CHANGE_TIME;
1455                 } else {
1456                         md1->originating_change_time    = now;
1457                 }
1458         } else {
1459                 md1->originating_change_time    = now;
1460         }
1461         md1->originating_invocation_id = *our_invocation_id;
1462         md1->originating_usn           = *seq_num;
1463         md1->local_usn                 = *seq_num;
1464
1465         return LDB_SUCCESS;
1466 }
1467
1468 /*
1469  * Bump the replPropertyMetaData version on an attribute, and if it
1470  * has changed (or forced by leaving rdn_old NULL), update the value
1471  * in the entry.
1472  *
1473  * This is important, as calling a modify operation may not change the
1474  * version number if the values appear unchanged, but a rename between
1475  * parents bumps this value.
1476  *
1477  */
1478 static int replmd_update_rpmd_rdn_attr(struct ldb_context *ldb,
1479                                        struct ldb_message *msg,
1480                                        const struct ldb_val *rdn_new,
1481                                        const struct ldb_val *rdn_old,
1482                                        struct replPropertyMetaDataBlob *omd,
1483                                        struct replmd_replicated_request *ar,
1484                                        NTTIME now,
1485                                        bool is_schema_nc)
1486 {
1487         const char *rdn_name = ldb_dn_get_rdn_name(msg->dn);
1488         const struct dsdb_attribute *rdn_attr =
1489                 dsdb_attribute_by_lDAPDisplayName(ar->schema, rdn_name);
1490         const char *attr_name = rdn_attr != NULL ?
1491                                 rdn_attr->lDAPDisplayName :
1492                                 rdn_name;
1493         struct ldb_message_element new_el = {
1494                 .flags = LDB_FLAG_MOD_REPLACE,
1495                 .name = attr_name,
1496                 .num_values = 1,
1497                 .values = discard_const_p(struct ldb_val, rdn_new)
1498         };
1499         struct ldb_message_element old_el = {
1500                 .flags = LDB_FLAG_MOD_REPLACE,
1501                 .name = attr_name,
1502                 .num_values = rdn_old ? 1 : 0,
1503                 .values = discard_const_p(struct ldb_val, rdn_old)
1504         };
1505
1506         if (ldb_msg_element_equal_ordered(&new_el, &old_el) == false) {
1507                 int ret = ldb_msg_add(msg, &new_el, LDB_FLAG_MOD_REPLACE);
1508                 if (ret != LDB_SUCCESS) {
1509                         return ldb_oom(ldb);
1510                 }
1511         }
1512
1513         return replmd_update_rpmd_element(ldb, msg, &new_el, NULL,
1514                                           omd, ar->schema, &ar->seq_num,
1515                                           &ar->our_invocation_id,
1516                                           now, is_schema_nc, ar->req);
1517
1518 }
1519
1520 static uint64_t find_max_local_usn(struct replPropertyMetaDataBlob omd)
1521 {
1522         uint32_t count = omd.ctr.ctr1.count;
1523         uint64_t max = 0;
1524         uint32_t i;
1525         for (i=0; i < count; i++) {
1526                 struct replPropertyMetaData1 m = omd.ctr.ctr1.array[i];
1527                 if (max < m.local_usn) {
1528                         max = m.local_usn;
1529                 }
1530         }
1531         return max;
1532 }
1533
1534 /*
1535  * update the replPropertyMetaData object each time we modify an
1536  * object. This is needed for DRS replication, as the merge on the
1537  * client is based on this object
1538  */
1539 static int replmd_update_rpmd(struct ldb_module *module,
1540                               const struct dsdb_schema *schema,
1541                               struct ldb_request *req,
1542                               const char * const *rename_attrs,
1543                               struct ldb_message *msg, uint64_t *seq_num,
1544                               time_t t, bool is_schema_nc,
1545                               bool *is_urgent, bool *rodc)
1546 {
1547         const struct ldb_val *omd_value;
1548         enum ndr_err_code ndr_err;
1549         struct replPropertyMetaDataBlob omd;
1550         unsigned int i;
1551         NTTIME now;
1552         const struct GUID *our_invocation_id;
1553         int ret;
1554         const char * const *attrs = NULL;
1555         const char * const attrs2[] = { "uSNChanged", "objectClass", "instanceType", NULL };
1556         struct ldb_result *res;
1557         struct ldb_context *ldb;
1558         struct ldb_message_element *objectclass_el;
1559         enum urgent_situation situation;
1560         bool rmd_is_provided;
1561         bool rmd_is_just_resorted = false;
1562         const char *not_rename_attrs[4 + msg->num_elements];
1563
1564         if (rename_attrs) {
1565                 attrs = rename_attrs;
1566         } else {
1567                 for (i = 0; i < msg->num_elements; i++) {
1568                         not_rename_attrs[i] = msg->elements[i].name;
1569                 }
1570                 not_rename_attrs[i] = "replPropertyMetaData";
1571                 not_rename_attrs[i+1] = "objectClass";
1572                 not_rename_attrs[i+2] = "instanceType";
1573                 not_rename_attrs[i+3] = NULL;
1574                 attrs = not_rename_attrs;
1575         }
1576
1577         ldb = ldb_module_get_ctx(module);
1578
1579         our_invocation_id = samdb_ntds_invocation_id(ldb);
1580         if (!our_invocation_id) {
1581                 /* this happens during an initial vampire while
1582                    updating the schema */
1583                 DEBUG(5,("No invocationID - skipping replPropertyMetaData update\n"));
1584                 return LDB_SUCCESS;
1585         }
1586
1587         unix_to_nt_time(&now, t);
1588
1589         if (ldb_request_get_control(req, DSDB_CONTROL_CHANGEREPLMETADATA_OID)) {
1590                 rmd_is_provided = true;
1591                 if (ldb_request_get_control(req, DSDB_CONTROL_CHANGEREPLMETADATA_RESORT_OID)) {
1592                         rmd_is_just_resorted = true;
1593                 }
1594         } else {
1595                 rmd_is_provided = false;
1596         }
1597
1598         /* if isDeleted is present and is TRUE, then we consider we are deleting,
1599          * otherwise we consider we are updating */
1600         if (ldb_msg_check_string_attribute(msg, "isDeleted", "TRUE")) {
1601                 situation = REPL_URGENT_ON_DELETE;
1602         } else if (rename_attrs) {
1603                 situation = REPL_URGENT_ON_CREATE | REPL_URGENT_ON_DELETE;
1604         } else {
1605                 situation = REPL_URGENT_ON_UPDATE;
1606         }
1607
1608         if (rmd_is_provided) {
1609                 /* In this case the change_replmetadata control was supplied */
1610                 /* We check that it's the only attribute that is provided
1611                  * (it's a rare case so it's better to keep the code simplier)
1612                  * We also check that the highest local_usn is bigger or the same as
1613                  * uSNChanged. */
1614                 uint64_t db_seq;
1615                 if( msg->num_elements != 1 ||
1616                         strncmp(msg->elements[0].name,
1617                                 "replPropertyMetaData", 20) ) {
1618                         DEBUG(0,(__location__ ": changereplmetada control called without "\
1619                                 "a specified replPropertyMetaData attribute or with others\n"));
1620                         return LDB_ERR_OPERATIONS_ERROR;
1621                 }
1622                 if (situation != REPL_URGENT_ON_UPDATE) {
1623                         DEBUG(0,(__location__ ": changereplmetada control can't be called when deleting an object\n"));
1624                         return LDB_ERR_OPERATIONS_ERROR;
1625                 }
1626                 omd_value = ldb_msg_find_ldb_val(msg, "replPropertyMetaData");
1627                 if (!omd_value) {
1628                         DEBUG(0,(__location__ ": replPropertyMetaData was not specified for Object %s\n",
1629                                  ldb_dn_get_linearized(msg->dn)));
1630                         return LDB_ERR_OPERATIONS_ERROR;
1631                 }
1632                 ndr_err = ndr_pull_struct_blob(omd_value, msg, &omd,
1633                                                (ndr_pull_flags_fn_t)ndr_pull_replPropertyMetaDataBlob);
1634                 if (!NDR_ERR_CODE_IS_SUCCESS(ndr_err)) {
1635                         DEBUG(0,(__location__ ": Failed to parse replPropertyMetaData for %s\n",
1636                                  ldb_dn_get_linearized(msg->dn)));
1637                         return LDB_ERR_OPERATIONS_ERROR;
1638                 }
1639
1640                 ret = dsdb_module_search_dn(module, msg, &res, msg->dn, attrs2,
1641                                             DSDB_FLAG_NEXT_MODULE |
1642                                             DSDB_SEARCH_SHOW_RECYCLED |
1643                                             DSDB_SEARCH_SHOW_EXTENDED_DN |
1644                                             DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT |
1645                                             DSDB_SEARCH_REVEAL_INTERNALS, req);
1646
1647                 if (ret != LDB_SUCCESS) {
1648                         return ret;
1649                 }
1650
1651                 if (rmd_is_just_resorted == false) {
1652                         *seq_num = find_max_local_usn(omd);
1653
1654                         db_seq = ldb_msg_find_attr_as_uint64(res->msgs[0], "uSNChanged", 0);
1655
1656                         /*
1657                          * The test here now allows for a new
1658                          * replPropertyMetaData with no change, if was
1659                          * just dbcheck re-sorting the values.
1660                          */
1661                         if (*seq_num <= db_seq) {
1662                                 DEBUG(0,(__location__ ": changereplmetada control provided but max(local_usn)" \
1663                                          " is less than uSNChanged (max = %lld uSNChanged = %lld)\n",
1664                                          (long long)*seq_num, (long long)db_seq));
1665                                 return LDB_ERR_OPERATIONS_ERROR;
1666                         }
1667                 }
1668
1669         } else {
1670                 /* search for the existing replPropertyMetaDataBlob. We need
1671                  * to use REVEAL and ask for DNs in storage format to support
1672                  * the check for values being the same in
1673                  * replmd_update_rpmd_element()
1674                  */
1675                 ret = dsdb_module_search_dn(module, msg, &res, msg->dn, attrs,
1676                                             DSDB_FLAG_NEXT_MODULE |
1677                                             DSDB_SEARCH_SHOW_RECYCLED |
1678                                             DSDB_SEARCH_SHOW_EXTENDED_DN |
1679                                             DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT |
1680                                             DSDB_SEARCH_REVEAL_INTERNALS, req);
1681                 if (ret != LDB_SUCCESS) {
1682                         return ret;
1683                 }
1684
1685                 omd_value = ldb_msg_find_ldb_val(res->msgs[0], "replPropertyMetaData");
1686                 if (!omd_value) {
1687                         DEBUG(0,(__location__ ": Object %s does not have a replPropertyMetaData attribute\n",
1688                                  ldb_dn_get_linearized(msg->dn)));
1689                         return LDB_ERR_OPERATIONS_ERROR;
1690                 }
1691
1692                 ndr_err = ndr_pull_struct_blob(omd_value, msg, &omd,
1693                                                (ndr_pull_flags_fn_t)ndr_pull_replPropertyMetaDataBlob);
1694                 if (!NDR_ERR_CODE_IS_SUCCESS(ndr_err)) {
1695                         DEBUG(0,(__location__ ": Failed to parse replPropertyMetaData for %s\n",
1696                                  ldb_dn_get_linearized(msg->dn)));
1697                         return LDB_ERR_OPERATIONS_ERROR;
1698                 }
1699
1700                 if (omd.version != 1) {
1701                         DEBUG(0,(__location__ ": bad version %u in replPropertyMetaData for %s\n",
1702                                  omd.version, ldb_dn_get_linearized(msg->dn)));
1703                         return LDB_ERR_OPERATIONS_ERROR;
1704                 }
1705
1706                 for (i=0; i<msg->num_elements;) {
1707                         struct ldb_message_element *el = &msg->elements[i];
1708                         struct ldb_message_element *old_el;
1709
1710                         old_el = ldb_msg_find_element(res->msgs[0], el->name);
1711                         ret = replmd_update_rpmd_element(ldb, msg, el, old_el,
1712                                                          &omd, schema, seq_num,
1713                                                          our_invocation_id,
1714                                                          now, is_schema_nc,
1715                                                          req);
1716                         if (ret != LDB_SUCCESS) {
1717                                 return ret;
1718                         }
1719
1720                         if (!*is_urgent && (situation == REPL_URGENT_ON_UPDATE)) {
1721                                 *is_urgent = replmd_check_urgent_attribute(el);
1722                         }
1723
1724                         if (!(el->flags & DSDB_FLAG_INTERNAL_FORCE_META_DATA)) {
1725                                 i++;
1726                                 continue;
1727                         }
1728
1729                         el->flags &= ~DSDB_FLAG_INTERNAL_FORCE_META_DATA;
1730
1731                         if (el->num_values != 0) {
1732                                 i++;
1733                                 continue;
1734                         }
1735
1736                         ldb_msg_remove_element(msg, el);
1737                 }
1738         }
1739
1740         /*
1741          * Assert that we have an objectClass attribute - this is major
1742          * corruption if we don't have this!
1743          */
1744         objectclass_el = ldb_msg_find_element(res->msgs[0], "objectClass");
1745         if (objectclass_el != NULL) {
1746                 /*
1747                  * Now check if this objectClass means we need to do urgent replication
1748                  */
1749                 if (!*is_urgent && replmd_check_urgent_objectclass(objectclass_el,
1750                                                                    situation)) {
1751                         *is_urgent = true;
1752                 }
1753         } else if (!ldb_request_get_control(req, DSDB_CONTROL_DBCHECK)) {
1754                 ldb_asprintf_errstring(ldb, __location__
1755                                        ": objectClass missing on %s\n",
1756                                        ldb_dn_get_linearized(msg->dn));
1757                 return LDB_ERR_OBJECT_CLASS_VIOLATION;
1758         }
1759
1760         /*
1761          * replmd_update_rpmd_element has done an update if the
1762          * seq_num is set
1763          */
1764         if (*seq_num != 0 || rmd_is_just_resorted == true) {
1765                 struct ldb_val *md_value;
1766                 struct ldb_message_element *el;
1767
1768                 /*if we are RODC and this is a DRSR update then its ok*/
1769                 if (!ldb_request_get_control(req, DSDB_CONTROL_REPLICATED_UPDATE_OID)
1770                     && !ldb_request_get_control(req, DSDB_CONTROL_DBCHECK_MODIFY_RO_REPLICA)) {
1771                         unsigned instanceType;
1772
1773                         ret = samdb_rodc(ldb, rodc);
1774                         if (ret != LDB_SUCCESS) {
1775                                 DEBUG(4, (__location__ ": unable to tell if we are an RODC\n"));
1776                         } else if (*rodc) {
1777                                 ldb_set_errstring(ldb, "RODC modify is forbidden!");
1778                                 return LDB_ERR_REFERRAL;
1779                         }
1780
1781                         instanceType = ldb_msg_find_attr_as_uint(res->msgs[0], "instanceType", INSTANCE_TYPE_WRITE);
1782                         if (!(instanceType & INSTANCE_TYPE_WRITE)) {
1783                                 return ldb_error(ldb, LDB_ERR_UNWILLING_TO_PERFORM,
1784                                                  "cannot change replicated attribute on partial replica");
1785                         }
1786                 }
1787
1788                 md_value = talloc(msg, struct ldb_val);
1789                 if (md_value == NULL) {
1790                         ldb_oom(ldb);
1791                         return LDB_ERR_OPERATIONS_ERROR;
1792                 }
1793
1794                 ret = replmd_replPropertyMetaDataCtr1_sort_and_verify(ldb, &omd.ctr.ctr1, msg->dn);
1795                 if (ret != LDB_SUCCESS) {
1796                         ldb_asprintf_errstring(ldb, "%s: %s", __func__, ldb_errstring(ldb));
1797                         return ret;
1798                 }
1799
1800                 ndr_err = ndr_push_struct_blob(md_value, msg, &omd,
1801                                                (ndr_push_flags_fn_t)ndr_push_replPropertyMetaDataBlob);
1802                 if (!NDR_ERR_CODE_IS_SUCCESS(ndr_err)) {
1803                         DEBUG(0,(__location__ ": Failed to marshall replPropertyMetaData for %s\n",
1804                                  ldb_dn_get_linearized(msg->dn)));
1805                         return LDB_ERR_OPERATIONS_ERROR;
1806                 }
1807
1808                 ret = ldb_msg_add_empty(msg, "replPropertyMetaData", LDB_FLAG_MOD_REPLACE, &el);
1809                 if (ret != LDB_SUCCESS) {
1810                         DEBUG(0,(__location__ ": Failed to add updated replPropertyMetaData %s\n",
1811                                  ldb_dn_get_linearized(msg->dn)));
1812                         return ret;
1813                 }
1814
1815                 el->num_values = 1;
1816                 el->values = md_value;
1817         }
1818
1819         return LDB_SUCCESS;
1820 }
1821
1822 struct compare_ctx {
1823         struct GUID *guid;
1824         struct ldb_context *ldb;
1825         TALLOC_CTX *mem_ctx;
1826         const char *ldap_oid;
1827         int err;
1828         const struct GUID *invocation_id;
1829 };
1830
1831 /* When a parsed_dn comes from the database, sometimes it is not really parsed. */
1832
1833 static int really_parse_trusted_dn(TALLOC_CTX *mem_ctx, struct ldb_context *ldb,
1834                                    struct parsed_dn *pdn, const char *ldap_oid)
1835 {
1836         NTSTATUS status;
1837         struct dsdb_dn *dsdb_dn = dsdb_dn_parse_trusted(mem_ctx, ldb, pdn->v,
1838                                                         ldap_oid);
1839         if (dsdb_dn == NULL) {
1840                 return LDB_ERR_INVALID_DN_SYNTAX;
1841         }
1842
1843         status = dsdb_get_extended_dn_guid(dsdb_dn->dn, &pdn->guid, "GUID");
1844         if (!NT_STATUS_IS_OK(status)) {
1845                 return LDB_ERR_OPERATIONS_ERROR;
1846         }
1847         pdn->dsdb_dn = dsdb_dn;
1848         return LDB_SUCCESS;
1849 }
1850
1851 /*
1852  * We choose, as the sort order, the same order as is used in DRS replication,
1853  * which is the memcmp() order of the NDR GUID, not that obtained from
1854  * GUID_compare().
1855  *
1856  * This means that sorted links will be in the same order as a new DC would
1857  * see them.
1858  */
1859 static int ndr_guid_compare(struct GUID *guid1, struct GUID *guid2)
1860 {
1861         uint8_t v1_data[16];
1862         struct ldb_val v1 = data_blob_const(v1_data, sizeof(v1_data));
1863         uint8_t v2_data[16];
1864         struct ldb_val v2 = data_blob_const(v2_data, sizeof(v2_data));
1865
1866         /* This can't fail */
1867         ndr_push_struct_into_fixed_blob(&v1, guid1,
1868                                         (ndr_push_flags_fn_t)ndr_push_GUID);
1869         /* This can't fail */
1870         ndr_push_struct_into_fixed_blob(&v2, guid2,
1871                                         (ndr_push_flags_fn_t)ndr_push_GUID);
1872         return data_blob_cmp(&v1, &v2);
1873 }
1874
1875 static int parsed_dn_compare(struct parsed_dn *pdn1, struct parsed_dn *pdn2)
1876 {
1877         return ndr_guid_compare(&pdn1->guid, &pdn2->guid);
1878 }
1879
1880 static int la_guid_compare_with_trusted_dn(struct compare_ctx *ctx,
1881                                            struct parsed_dn *p)
1882 {
1883         /*
1884          * This works like a standard compare function in its return values,
1885          * but has an extra trick to deal with errors: zero is returned and
1886          * ctx->err is set to the ldb error code.
1887          *
1888          * That is, if (as is expected in most cases) you get a non-zero
1889          * result, you don't need to check for errors.
1890          *
1891          * We assume the second argument refers to a DN is from the database
1892          * and has a GUID -- but this GUID might not have been parsed out yet.
1893          */
1894         if (p->dsdb_dn == NULL) {
1895                 int ret = really_parse_trusted_dn(ctx->mem_ctx, ctx->ldb, p,
1896                                                   ctx->ldap_oid);
1897                 if (ret != LDB_SUCCESS) {
1898                         ctx->err = ret;
1899                         return 0;
1900                 }
1901         }
1902         return ndr_guid_compare(ctx->guid, &p->guid);
1903 }
1904
1905
1906
1907 static int parsed_dn_find(struct ldb_context *ldb, struct parsed_dn *pdn,
1908                           unsigned int count,
1909                           struct GUID *guid,
1910                           struct ldb_dn *target_dn,
1911                           struct parsed_dn **exact,
1912                           struct parsed_dn **next,
1913                           const char *ldap_oid)
1914 {
1915         unsigned int i;
1916         struct compare_ctx ctx;
1917         if (pdn == NULL) {
1918                 *exact = NULL;
1919                 *next = NULL;
1920                 return LDB_SUCCESS;
1921         }
1922
1923         if (unlikely(GUID_all_zero(guid))) {
1924                 /*
1925                  * When updating a link using DRS, we sometimes get a NULL
1926                  * GUID when a forward link has been deleted and its GUID has
1927                  * for some reason been forgotten. The best we can do is try
1928                  * and match by DN via a linear search. Note that this
1929                  * probably only happens in the ADD case, in which we only
1930                  * allow modification of link if it is already deleted, so
1931                  * this seems very close to an elaborate NO-OP, but we are not
1932                  * quite prepared to declare it so.
1933                  *
1934                  * If the DN is not in our list, we have to add it to the
1935                  * beginning of the list, where it would naturally sort.
1936                  */
1937                 struct parsed_dn *p;
1938                 if (target_dn == NULL) {
1939                         /* We don't know the target DN, so we can't search for DN */
1940                         DEBUG(1, ("parsed_dn_find has a NULL GUID for a linked "
1941                                   "attribute but we don't have a DN to compare "
1942                                   "it with\n"));
1943                         return LDB_ERR_OPERATIONS_ERROR;
1944                 }
1945                 *exact = NULL;
1946                 *next = NULL;
1947
1948                 DEBUG(3, ("parsed_dn_find has a NULL GUID for a link to DN "
1949                           "%s; searching through links for it",
1950                           ldb_dn_get_linearized(target_dn)));
1951
1952                 for (i = 0; i < count; i++) {
1953                         int cmp;
1954                         p = &pdn[i];
1955                         if (p->dsdb_dn == NULL) {
1956                                 int ret = really_parse_trusted_dn(pdn, ldb, p, ldap_oid);
1957                                 if (ret != LDB_SUCCESS) {
1958                                         return LDB_ERR_OPERATIONS_ERROR;
1959                                 }
1960                         }
1961
1962                         cmp = ldb_dn_compare(p->dsdb_dn->dn, target_dn);
1963                         if (cmp == 0) {
1964                                 *exact = p;
1965                                 return LDB_SUCCESS;
1966                         }
1967                 }
1968                 /*
1969                  * Here we have a null guid which doesn't match any existing
1970                  * link. This is a bit unexpected because null guids occur
1971                  * when a forward link has been deleted and we are replicating
1972                  * that deletion.
1973                  *
1974                  * The best thing to do is weep into the logs and add the
1975                  * offending link to the beginning of the list which is
1976                  * at least the correct sort position.
1977                  */
1978                 DEBUG(1, ("parsed_dn_find has been given a NULL GUID for a "
1979                           "link to unknown DN %s\n",
1980                           ldb_dn_get_linearized(target_dn)));
1981                 *next = pdn;
1982                 return LDB_SUCCESS;
1983         }
1984
1985         ctx.guid = guid;
1986         ctx.ldb = ldb;
1987         ctx.mem_ctx = pdn;
1988         ctx.ldap_oid = ldap_oid;
1989         ctx.err = 0;
1990
1991         BINARY_ARRAY_SEARCH_GTE(pdn, count, &ctx, la_guid_compare_with_trusted_dn,
1992                                 *exact, *next);
1993
1994         if (ctx.err != 0) {
1995                 return ctx.err;
1996         }
1997         return LDB_SUCCESS;
1998 }
1999
2000 /*
2001   get a series of message element values as an array of DNs and GUIDs
2002   the result is sorted by GUID
2003  */
2004 static int get_parsed_dns(struct ldb_module *module, TALLOC_CTX *mem_ctx,
2005                           struct ldb_message_element *el, struct parsed_dn **pdn,
2006                           const char *ldap_oid, struct ldb_request *parent)
2007 {
2008         unsigned int i;
2009         bool values_are_sorted = true;
2010         struct ldb_context *ldb = ldb_module_get_ctx(module);
2011
2012         if (el == NULL) {
2013                 *pdn = NULL;
2014                 return LDB_SUCCESS;
2015         }
2016
2017         (*pdn) = talloc_array(mem_ctx, struct parsed_dn, el->num_values);
2018         if (!*pdn) {
2019                 ldb_module_oom(module);
2020                 return LDB_ERR_OPERATIONS_ERROR;
2021         }
2022
2023         for (i=0; i<el->num_values; i++) {
2024                 struct ldb_val *v = &el->values[i];
2025                 NTSTATUS status;
2026                 struct ldb_dn *dn;
2027                 struct parsed_dn *p;
2028
2029                 p = &(*pdn)[i];
2030
2031                 p->dsdb_dn = dsdb_dn_parse(*pdn, ldb, v, ldap_oid);
2032                 if (p->dsdb_dn == NULL) {
2033                         return LDB_ERR_INVALID_DN_SYNTAX;
2034                 }
2035
2036                 dn = p->dsdb_dn->dn;
2037
2038                 status = dsdb_get_extended_dn_guid(dn, &p->guid, "GUID");
2039                 if (NT_STATUS_EQUAL(status, NT_STATUS_OBJECT_NAME_NOT_FOUND) ||
2040                     unlikely(GUID_all_zero(&p->guid))) {
2041                         /* we got a DN without a GUID - go find the GUID */
2042                         int ret = dsdb_module_guid_by_dn(module, dn, &p->guid, parent);
2043                         if (ret != LDB_SUCCESS) {
2044                                 ldb_asprintf_errstring(ldb, "Unable to find GUID for DN %s\n",
2045                                                        ldb_dn_get_linearized(dn));
2046                                 if (ret == LDB_ERR_NO_SUCH_OBJECT &&
2047                                     LDB_FLAG_MOD_TYPE(el->flags) == LDB_FLAG_MOD_DELETE &&
2048                                     ldb_attr_cmp(el->name, "member") == 0) {
2049                                         return LDB_ERR_UNWILLING_TO_PERFORM;
2050                                 }
2051                                 return ret;
2052                         }
2053                         ret = dsdb_set_extended_dn_guid(dn, &p->guid, "GUID");
2054                         if (ret != LDB_SUCCESS) {
2055                                 return ret;
2056                         }
2057                 } else if (!NT_STATUS_IS_OK(status)) {
2058                         return LDB_ERR_OPERATIONS_ERROR;
2059                 }
2060                 if (i > 0 && values_are_sorted) {
2061                         int cmp = parsed_dn_compare(p, &(*pdn)[i - 1]);
2062                         if (cmp < 0) {
2063                                 values_are_sorted = false;
2064                         }
2065                 }
2066                 /* keep a pointer to the original ldb_val */
2067                 p->v = v;
2068         }
2069         if (! values_are_sorted) {
2070                 TYPESAFE_QSORT(*pdn, el->num_values, parsed_dn_compare);
2071         }
2072         return LDB_SUCCESS;
2073 }
2074
2075 /*
2076  * Get a series of trusted message element values. The result is sorted by
2077  * GUID, even though the GUIDs might not be known. That works because we trust
2078  * the database to give us the elements like that if the
2079  * replmd_private->sorted_links flag is set.
2080  *
2081  * We also ensure that the links are in the Functional Level 2003
2082  * linked attributes format.
2083  */
2084 static int get_parsed_dns_trusted(struct ldb_module *module,
2085                                   struct replmd_private *replmd_private,
2086                                   TALLOC_CTX *mem_ctx,
2087                                   struct ldb_message_element *el,
2088                                   struct parsed_dn **pdn,
2089                                   const char *ldap_oid,
2090                                   struct ldb_request *parent)
2091 {
2092         unsigned int i;
2093         int ret;
2094         if (el == NULL) {
2095                 *pdn = NULL;
2096                 return LDB_SUCCESS;
2097         }
2098
2099         if (!replmd_private->sorted_links) {
2100                 /* We need to sort the list. This is the slow old path we want
2101                    to avoid.
2102                  */
2103                 ret = get_parsed_dns(module, mem_ctx, el, pdn, ldap_oid,
2104                                       parent);
2105                 if (ret != LDB_SUCCESS) {
2106                         return ret;
2107                 }
2108         } else {
2109                 /* Here we get a list of 'struct parsed_dns' without the parsing */
2110                 *pdn = talloc_zero_array(mem_ctx, struct parsed_dn,
2111                                          el->num_values);
2112                 if (!*pdn) {
2113                         ldb_module_oom(module);
2114                         return LDB_ERR_OPERATIONS_ERROR;
2115                 }
2116
2117                 for (i = 0; i < el->num_values; i++) {
2118                         (*pdn)[i].v = &el->values[i];
2119                 }
2120         }
2121
2122         /*
2123          * This upgrades links to FL2003 style, and sorts the result
2124          * if that was needed.
2125          *
2126          * TODO: Add a database feature that asserts we have no FL2000
2127          *       style links to avoid this check or add a feature that
2128          *       uses a similar check to find sorted/unsorted links
2129          *       for an on-the-fly upgrade.
2130          */
2131
2132         ret = replmd_check_upgrade_links(ldb_module_get_ctx(module),
2133                                          *pdn, el->num_values,
2134                                          el,
2135                                          ldap_oid);
2136         if (ret != LDB_SUCCESS) {
2137                 return ret;
2138         }
2139
2140         return LDB_SUCCESS;
2141 }
2142
2143 /*
2144   build a new extended DN, including all meta data fields
2145
2146   RMD_FLAGS           = DSDB_RMD_FLAG_* bits
2147   RMD_ADDTIME         = originating_add_time
2148   RMD_INVOCID         = originating_invocation_id
2149   RMD_CHANGETIME      = originating_change_time
2150   RMD_ORIGINATING_USN = originating_usn
2151   RMD_LOCAL_USN       = local_usn
2152   RMD_VERSION         = version
2153  */
2154 static int replmd_build_la_val(TALLOC_CTX *mem_ctx, struct ldb_val *v, struct dsdb_dn *dsdb_dn,
2155                                const struct GUID *invocation_id, uint64_t seq_num,
2156                                uint64_t local_usn, NTTIME nttime, uint32_t version, bool deleted)
2157 {
2158         struct ldb_dn *dn = dsdb_dn->dn;
2159         const char *tstring, *usn_string, *flags_string;
2160         struct ldb_val tval;
2161         struct ldb_val iid;
2162         struct ldb_val usnv, local_usnv;
2163         struct ldb_val vers, flagsv;
2164         NTSTATUS status;
2165         int ret;
2166         const char *dnstring;
2167         char *vstring;
2168         uint32_t rmd_flags = deleted?DSDB_RMD_FLAG_DELETED:0;
2169
2170         tstring = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)nttime);
2171         if (!tstring) {
2172                 return LDB_ERR_OPERATIONS_ERROR;
2173         }
2174         tval = data_blob_string_const(tstring);
2175
2176         usn_string = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)seq_num);
2177         if (!usn_string) {
2178                 return LDB_ERR_OPERATIONS_ERROR;
2179         }
2180         usnv = data_blob_string_const(usn_string);
2181
2182         usn_string = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)local_usn);
2183         if (!usn_string) {
2184                 return LDB_ERR_OPERATIONS_ERROR;
2185         }
2186         local_usnv = data_blob_string_const(usn_string);
2187
2188         vstring = talloc_asprintf(mem_ctx, "%lu", (unsigned long)version);
2189         if (!vstring) {
2190                 return LDB_ERR_OPERATIONS_ERROR;
2191         }
2192         vers = data_blob_string_const(vstring);
2193
2194         status = GUID_to_ndr_blob(invocation_id, dn, &iid);
2195         if (!NT_STATUS_IS_OK(status)) {
2196                 return LDB_ERR_OPERATIONS_ERROR;
2197         }
2198
2199         flags_string = talloc_asprintf(mem_ctx, "%u", rmd_flags);
2200         if (!flags_string) {
2201                 return LDB_ERR_OPERATIONS_ERROR;
2202         }
2203         flagsv = data_blob_string_const(flags_string);
2204
2205         ret = ldb_dn_set_extended_component(dn, "RMD_FLAGS", &flagsv);
2206         if (ret != LDB_SUCCESS) return ret;
2207         ret = ldb_dn_set_extended_component(dn, "RMD_ADDTIME", &tval);
2208         if (ret != LDB_SUCCESS) return ret;
2209         ret = ldb_dn_set_extended_component(dn, "RMD_INVOCID", &iid);
2210         if (ret != LDB_SUCCESS) return ret;
2211         ret = ldb_dn_set_extended_component(dn, "RMD_CHANGETIME", &tval);
2212         if (ret != LDB_SUCCESS) return ret;
2213         ret = ldb_dn_set_extended_component(dn, "RMD_LOCAL_USN", &local_usnv);
2214         if (ret != LDB_SUCCESS) return ret;
2215         ret = ldb_dn_set_extended_component(dn, "RMD_ORIGINATING_USN", &usnv);
2216         if (ret != LDB_SUCCESS) return ret;
2217         ret = ldb_dn_set_extended_component(dn, "RMD_VERSION", &vers);
2218         if (ret != LDB_SUCCESS) return ret;
2219
2220         dnstring = dsdb_dn_get_extended_linearized(mem_ctx, dsdb_dn, 1);
2221         if (dnstring == NULL) {
2222                 return LDB_ERR_OPERATIONS_ERROR;
2223         }
2224         *v = data_blob_string_const(dnstring);
2225
2226         return LDB_SUCCESS;
2227 }
2228
2229 static int replmd_update_la_val(TALLOC_CTX *mem_ctx, struct ldb_val *v, struct dsdb_dn *dsdb_dn,
2230                                 struct dsdb_dn *old_dsdb_dn, const struct GUID *invocation_id,
2231                                 uint64_t seq_num, uint64_t local_usn, NTTIME nttime,
2232                                 uint32_t version, bool deleted);
2233
2234 /*
2235   check if any links need upgrading from w2k format
2236  */
2237 static int replmd_check_upgrade_links(struct ldb_context *ldb,
2238                                       struct parsed_dn *dns, uint32_t count,
2239                                       struct ldb_message_element *el,
2240                                       const char *ldap_oid)
2241 {
2242         uint32_t i;
2243         const struct GUID *invocation_id = NULL;
2244         for (i=0; i<count; i++) {
2245                 NTSTATUS status;
2246                 uint32_t version;
2247                 int ret;
2248                 if (dns[i].dsdb_dn == NULL) {
2249                         ret = really_parse_trusted_dn(dns, ldb, &dns[i],
2250                                                       ldap_oid);
2251                         if (ret != LDB_SUCCESS) {
2252                                 return LDB_ERR_INVALID_DN_SYNTAX;
2253                         }
2254                 }
2255
2256                 status = dsdb_get_extended_dn_uint32(dns[i].dsdb_dn->dn,
2257                                                      &version, "RMD_VERSION");
2258                 if (!NT_STATUS_EQUAL(status, NT_STATUS_OBJECT_NAME_NOT_FOUND)) {
2259                         /*
2260                          *  We optimistically assume they are all the same; if
2261                          *  the first one is fixed, they are all fixed.
2262                          *
2263                          *  If the first one was *not* fixed and we find a
2264                          *  later one that is, that is an occasion to shout
2265                          *  with DEBUG(0).
2266                          */
2267                         if (i == 0) {
2268                                 return LDB_SUCCESS;
2269                         }
2270                         DEBUG(0, ("Mixed w2k and fixed format "
2271                                   "linked attributes\n"));
2272                         continue;
2273                 }
2274
2275                 if (invocation_id == NULL) {
2276                         invocation_id = samdb_ntds_invocation_id(ldb);
2277                         if (invocation_id == NULL) {
2278                                 return LDB_ERR_OPERATIONS_ERROR;
2279                         }
2280                 }
2281
2282
2283                 /* it's an old one that needs upgrading */
2284                 ret = replmd_update_la_val(el->values, dns[i].v,
2285                                            dns[i].dsdb_dn, dns[i].dsdb_dn,
2286                                            invocation_id, 1, 1, 0, 0, false);
2287                 if (ret != LDB_SUCCESS) {
2288                         return ret;
2289                 }
2290         }
2291
2292         /*
2293          * This sort() is critical for the operation of
2294          * get_parsed_dns_trusted() because callers of this function
2295          * expect a sorted list, and FL2000 style links are not
2296          * sorted.  In particular, as well as the upgrade case,
2297          * get_parsed_dns_trusted() is called from
2298          * replmd_delete_remove_link() even in FL2000 mode
2299          *
2300          * We do not normally pay the cost of the qsort() due to the
2301          * early return in the RMD_VERSION found case.
2302          */
2303         TYPESAFE_QSORT(dns, count, parsed_dn_compare);
2304         return LDB_SUCCESS;
2305 }
2306
2307 /*
2308   update an extended DN, including all meta data fields
2309
2310   see replmd_build_la_val for value names
2311  */
2312 static int replmd_update_la_val(TALLOC_CTX *mem_ctx, struct ldb_val *v, struct dsdb_dn *dsdb_dn,
2313                                 struct dsdb_dn *old_dsdb_dn, const struct GUID *invocation_id,
2314                                 uint64_t usn, uint64_t local_usn, NTTIME nttime,
2315                                 uint32_t version, bool deleted)
2316 {
2317         struct ldb_dn *dn = dsdb_dn->dn;
2318         const char *tstring, *usn_string, *flags_string;
2319         struct ldb_val tval;
2320         struct ldb_val iid;
2321         struct ldb_val usnv, local_usnv;
2322         struct ldb_val vers, flagsv;
2323         const struct ldb_val *old_addtime;
2324         uint32_t old_version;
2325         NTSTATUS status;
2326         int ret;
2327         const char *dnstring;
2328         char *vstring;
2329         uint32_t rmd_flags = deleted?DSDB_RMD_FLAG_DELETED:0;
2330
2331         tstring = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)nttime);
2332         if (!tstring) {
2333                 return LDB_ERR_OPERATIONS_ERROR;
2334         }
2335         tval = data_blob_string_const(tstring);
2336
2337         usn_string = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)usn);
2338         if (!usn_string) {
2339                 return LDB_ERR_OPERATIONS_ERROR;
2340         }
2341         usnv = data_blob_string_const(usn_string);
2342
2343         usn_string = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)local_usn);
2344         if (!usn_string) {
2345                 return LDB_ERR_OPERATIONS_ERROR;
2346         }
2347         local_usnv = data_blob_string_const(usn_string);
2348
2349         status = GUID_to_ndr_blob(invocation_id, dn, &iid);
2350         if (!NT_STATUS_IS_OK(status)) {
2351                 return LDB_ERR_OPERATIONS_ERROR;
2352         }
2353
2354         flags_string = talloc_asprintf(mem_ctx, "%u", rmd_flags);
2355         if (!flags_string) {
2356                 return LDB_ERR_OPERATIONS_ERROR;
2357         }
2358         flagsv = data_blob_string_const(flags_string);
2359
2360         ret = ldb_dn_set_extended_component(dn, "RMD_FLAGS", &flagsv);
2361         if (ret != LDB_SUCCESS) return ret;
2362
2363         /* get the ADDTIME from the original */
2364         old_addtime = ldb_dn_get_extended_component(old_dsdb_dn->dn, "RMD_ADDTIME");
2365         if (old_addtime == NULL) {
2366                 old_addtime = &tval;
2367         }
2368         if (dsdb_dn != old_dsdb_dn ||
2369             ldb_dn_get_extended_component(dn, "RMD_ADDTIME") == NULL) {
2370                 ret = ldb_dn_set_extended_component(dn, "RMD_ADDTIME", old_addtime);
2371                 if (ret != LDB_SUCCESS) return ret;
2372         }
2373
2374         /* use our invocation id */
2375         ret = ldb_dn_set_extended_component(dn, "RMD_INVOCID", &iid);
2376         if (ret != LDB_SUCCESS) return ret;
2377
2378         /* changetime is the current time */
2379         ret = ldb_dn_set_extended_component(dn, "RMD_CHANGETIME", &tval);
2380         if (ret != LDB_SUCCESS) return ret;
2381
2382         /* update the USN */
2383         ret = ldb_dn_set_extended_component(dn, "RMD_ORIGINATING_USN", &usnv);
2384         if (ret != LDB_SUCCESS) return ret;
2385
2386         ret = ldb_dn_set_extended_component(dn, "RMD_LOCAL_USN", &local_usnv);
2387         if (ret != LDB_SUCCESS) return ret;
2388
2389         /* increase the version by 1 */
2390         status = dsdb_get_extended_dn_uint32(old_dsdb_dn->dn, &old_version, "RMD_VERSION");
2391         if (NT_STATUS_IS_OK(status) && old_version >= version) {
2392                 version = old_version+1;
2393         }
2394         vstring = talloc_asprintf(dn, "%lu", (unsigned long)version);
2395         vers = data_blob_string_const(vstring);
2396         ret = ldb_dn_set_extended_component(dn, "RMD_VERSION", &vers);
2397         if (ret != LDB_SUCCESS) return ret;
2398
2399         dnstring = dsdb_dn_get_extended_linearized(mem_ctx, dsdb_dn, 1);
2400         if (dnstring == NULL) {
2401                 return LDB_ERR_OPERATIONS_ERROR;
2402         }
2403         *v = data_blob_string_const(dnstring);
2404
2405         return LDB_SUCCESS;
2406 }
2407
2408 /*
2409   handle adding a linked attribute
2410  */
2411 static int replmd_modify_la_add(struct ldb_module *module,
2412                                 struct replmd_private *replmd_private,
2413                                 const struct dsdb_schema *schema,
2414                                 struct ldb_message *msg,
2415                                 struct ldb_message_element *el,
2416                                 struct ldb_message_element *old_el,
2417                                 const struct dsdb_attribute *schema_attr,
2418                                 uint64_t seq_num,
2419                                 time_t t,
2420                                 struct GUID *msg_guid,
2421                                 struct ldb_request *parent)
2422 {
2423         unsigned int i, j;
2424         struct parsed_dn *dns, *old_dns;
2425         TALLOC_CTX *tmp_ctx = talloc_new(msg);
2426         int ret;
2427         struct ldb_val *new_values = NULL;
2428         unsigned old_num_values = old_el ? old_el->num_values : 0;
2429         unsigned num_values = 0;
2430         unsigned max_num_values;
2431         const struct GUID *invocation_id;
2432         struct ldb_context *ldb = ldb_module_get_ctx(module);
2433         NTTIME now;
2434         unix_to_nt_time(&now, t);
2435
2436         invocation_id = samdb_ntds_invocation_id(ldb);
2437         if (!invocation_id) {
2438                 talloc_free(tmp_ctx);
2439                 return LDB_ERR_OPERATIONS_ERROR;
2440         }
2441
2442         /* get the DNs to be added, fully parsed.
2443          *
2444          * We need full parsing because they came off the wire and we don't
2445          * trust them, besides which we need their details to know where to put
2446          * them.
2447          */
2448         ret = get_parsed_dns(module, tmp_ctx, el, &dns,
2449                              schema_attr->syntax->ldap_oid, parent);
2450         if (ret != LDB_SUCCESS) {
2451                 talloc_free(tmp_ctx);
2452                 return ret;
2453         }
2454
2455         /* get the existing DNs, lazily parsed */
2456         ret = get_parsed_dns_trusted(module, replmd_private,
2457                                      tmp_ctx, old_el, &old_dns,
2458                                      schema_attr->syntax->ldap_oid, parent);
2459
2460         if (ret != LDB_SUCCESS) {
2461                 talloc_free(tmp_ctx);
2462                 return ret;
2463         }
2464
2465         max_num_values = old_num_values + el->num_values;
2466         if (max_num_values < old_num_values) {
2467                 DEBUG(0, ("we seem to have overflow in replmd_modify_la_add. "
2468                           "old values: %u, new values: %u, sum: %u",
2469                           old_num_values, el->num_values, max_num_values));
2470                 talloc_free(tmp_ctx);
2471                 return LDB_ERR_OPERATIONS_ERROR;
2472         }
2473
2474         new_values = talloc_zero_array(tmp_ctx, struct ldb_val, max_num_values);
2475
2476         if (new_values == NULL) {
2477                 ldb_module_oom(module);
2478                 talloc_free(tmp_ctx);
2479                 return LDB_ERR_OPERATIONS_ERROR;
2480         }
2481
2482         /*
2483          * For each new value, find where it would go in the list. If there is
2484          * a matching GUID there, we update the existing value; otherwise we
2485          * put it in place.
2486          */
2487         j = 0;
2488         for (i = 0; i < el->num_values; i++) {
2489                 struct parsed_dn *exact;
2490                 struct parsed_dn *next;
2491                 unsigned offset;
2492                 int err = parsed_dn_find(ldb, old_dns, old_num_values,
2493                                          &dns[i].guid,
2494                                          dns[i].dsdb_dn->dn,
2495                                          &exact, &next,
2496                                          schema_attr->syntax->ldap_oid);
2497                 if (err != LDB_SUCCESS) {
2498                         talloc_free(tmp_ctx);
2499                         return err;
2500                 }
2501
2502                 if (exact != NULL) {
2503                         /*
2504                          * We are trying to add one that exists, which is only
2505                          * allowed if it was previously deleted.
2506                          *
2507                          * When we do undelete a link we change it in place.
2508                          * It will be copied across into the right spot in due
2509                          * course.
2510                          */
2511                         uint32_t rmd_flags;
2512                         rmd_flags = dsdb_dn_rmd_flags(exact->dsdb_dn->dn);
2513
2514                         if (!(rmd_flags & DSDB_RMD_FLAG_DELETED)) {
2515                                 struct GUID_txt_buf guid_str;
2516                                 ldb_asprintf_errstring(ldb,
2517                                                        "Attribute %s already "
2518                                                        "exists for target GUID %s",
2519                                                        el->name,
2520                                                        GUID_buf_string(&exact->guid,
2521                                                                        &guid_str));
2522                                 talloc_free(tmp_ctx);
2523                                 /* error codes for 'member' need to be
2524                                    special cased */
2525                                 if (ldb_attr_cmp(el->name, "member") == 0) {
2526                                         return LDB_ERR_ENTRY_ALREADY_EXISTS;
2527                                 } else {
2528                                         return LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
2529                                 }
2530                         }
2531
2532                         ret = replmd_update_la_val(new_values, exact->v,
2533                                                    dns[i].dsdb_dn,
2534                                                    exact->dsdb_dn,
2535                                                    invocation_id, seq_num,
2536                                                    seq_num, now, 0, false);
2537                         if (ret != LDB_SUCCESS) {
2538                                 talloc_free(tmp_ctx);
2539                                 return ret;
2540                         }
2541
2542                         ret = replmd_add_backlink(module, replmd_private,
2543                                                   schema, msg_guid,
2544                                                   &dns[i].guid, true,
2545                                                   schema_attr, true);
2546                         if (ret != LDB_SUCCESS) {
2547                                 talloc_free(tmp_ctx);
2548                                 return ret;
2549                                 }
2550                         continue;
2551                 }
2552                 /*
2553                  * Here we don't have an exact match.
2554                  *
2555                  * If next is NULL, this one goes beyond the end of the
2556                  * existing list, so we need to add all of those ones first.
2557                  *
2558                  * If next is not NULL, we need to add all the ones before
2559                  * next.
2560                  */
2561                 if (next == NULL) {
2562                         offset = old_num_values;
2563                 } else {
2564                         /* next should have been parsed, but let's make sure */
2565                         if (next->dsdb_dn == NULL) {
2566                                 ret = really_parse_trusted_dn(tmp_ctx, ldb, next,
2567                                                               schema_attr->syntax->ldap_oid);
2568                                 if (ret != LDB_SUCCESS) {
2569                                         return ret;
2570                                 }
2571                         }
2572                         offset = MIN(next - old_dns, old_num_values);
2573                 }
2574
2575                 /* put all the old ones before next on the list */
2576                 for (; j < offset; j++) {
2577                         new_values[num_values] = *old_dns[j].v;
2578                         num_values++;
2579                 }
2580
2581                 ret = replmd_add_backlink(module, replmd_private,
2582                                           schema, msg_guid, &dns[i].guid,
2583                                           true, schema_attr, true);
2584                 /* Make the new linked attribute ldb_val. */
2585                 ret = replmd_build_la_val(new_values, &new_values[num_values],
2586                                           dns[i].dsdb_dn, invocation_id,
2587                                           seq_num, seq_num,
2588                                           now, 0, false);
2589                 if (ret != LDB_SUCCESS) {
2590                         talloc_free(tmp_ctx);
2591                         return ret;
2592                 }
2593                 num_values++;
2594                 if (ret != LDB_SUCCESS) {
2595                         talloc_free(tmp_ctx);
2596                         return ret;
2597                 }
2598         }
2599         /* copy the rest of the old ones (if any) */
2600         for (; j < old_num_values; j++) {
2601                 new_values[num_values] = *old_dns[j].v;
2602                 num_values++;
2603         }
2604
2605         talloc_steal(msg->elements, new_values);
2606         if (old_el != NULL) {
2607                 talloc_steal(msg->elements, old_el->values);
2608         }
2609         el->values = new_values;
2610         el->num_values = num_values;
2611
2612         talloc_free(tmp_ctx);
2613
2614         /* we now tell the backend to replace all existing values
2615            with the one we have constructed */
2616         el->flags = LDB_FLAG_MOD_REPLACE;
2617
2618         return LDB_SUCCESS;
2619 }
2620
2621
2622 /*
2623   handle deleting all active linked attributes
2624  */
2625 static int replmd_modify_la_delete(struct ldb_module *module,
2626                                    struct replmd_private *replmd_private,
2627                                    const struct dsdb_schema *schema,
2628                                    struct ldb_message *msg,
2629                                    struct ldb_message_element *el,
2630                                    struct ldb_message_element *old_el,
2631                                    const struct dsdb_attribute *schema_attr,
2632                                    uint64_t seq_num,
2633                                    time_t t,
2634                                    struct GUID *msg_guid,
2635                                    struct ldb_request *parent)
2636 {
2637         unsigned int i;
2638         struct parsed_dn *dns, *old_dns;
2639         TALLOC_CTX *tmp_ctx = NULL;
2640         int ret;
2641         struct ldb_context *ldb = ldb_module_get_ctx(module);
2642         struct ldb_control *vanish_links_ctrl = NULL;
2643         bool vanish_links = false;
2644         unsigned int num_to_delete = el->num_values;
2645         uint32_t rmd_flags;
2646         const struct GUID *invocation_id;
2647         NTTIME now;
2648
2649         unix_to_nt_time(&now, t);
2650
2651         invocation_id = samdb_ntds_invocation_id(ldb);
2652         if (!invocation_id) {
2653                 return LDB_ERR_OPERATIONS_ERROR;
2654         }
2655
2656         if (old_el == NULL || old_el->num_values == 0) {
2657                 /* there is nothing to delete... */
2658                 if (num_to_delete == 0) {
2659                         /* and we're deleting nothing, so that's OK */
2660                         return LDB_SUCCESS;
2661                 }
2662                 return LDB_ERR_NO_SUCH_ATTRIBUTE;
2663         }
2664
2665         tmp_ctx = talloc_new(msg);
2666         if (tmp_ctx == NULL) {
2667                 return LDB_ERR_OPERATIONS_ERROR;
2668         }
2669
2670         ret = get_parsed_dns(module, tmp_ctx, el, &dns,
2671                              schema_attr->syntax->ldap_oid, parent);
2672         if (ret != LDB_SUCCESS) {
2673                 talloc_free(tmp_ctx);
2674                 return ret;
2675         }
2676
2677         ret = get_parsed_dns_trusted(module, replmd_private,
2678                                      tmp_ctx, old_el, &old_dns,
2679                                      schema_attr->syntax->ldap_oid, parent);
2680
2681         if (ret != LDB_SUCCESS) {
2682                 talloc_free(tmp_ctx);
2683                 return ret;
2684         }
2685
2686         if (parent) {
2687                 vanish_links_ctrl = ldb_request_get_control(parent, DSDB_CONTROL_REPLMD_VANISH_LINKS);
2688                 if (vanish_links_ctrl) {
2689                         vanish_links = true;
2690                         vanish_links_ctrl->critical = false;
2691                 }
2692         }
2693
2694         /* we empty out el->values here to avoid damage if we return early. */
2695         el->num_values = 0;
2696         el->values = NULL;
2697
2698         /*
2699          * If vanish links is set, we are actually removing members of
2700          *  old_el->values; otherwise we are just marking them deleted.
2701          *
2702          * There is a special case when no values are given: we remove them
2703          * all. When we have the vanish_links control we just have to remove
2704          * the backlinks and change our element to replace the existing values
2705          * with the empty list.
2706          */
2707
2708         if (num_to_delete == 0) {
2709                 for (i = 0; i < old_el->num_values; i++) {
2710                         struct parsed_dn *p = &old_dns[i];
2711                         if (p->dsdb_dn == NULL) {
2712                                 ret = really_parse_trusted_dn(tmp_ctx, ldb, p,
2713                                                               schema_attr->syntax->ldap_oid);
2714                                 if (ret != LDB_SUCCESS) {
2715                                         return ret;
2716                                 }
2717                         }
2718                         ret = replmd_add_backlink(module, replmd_private,
2719                                                   schema, msg_guid, &p->guid,
2720                                                   false, schema_attr, true);
2721                         if (ret != LDB_SUCCESS) {
2722                                 talloc_free(tmp_ctx);
2723                                 return ret;
2724                         }
2725                         if (vanish_links) {
2726                                 continue;
2727                         }
2728
2729                         rmd_flags = dsdb_dn_rmd_flags(p->dsdb_dn->dn);
2730                         if (rmd_flags & DSDB_RMD_FLAG_DELETED) {
2731                                 continue;
2732                         }
2733
2734                         ret = replmd_update_la_val(old_el->values, p->v,
2735                                                    p->dsdb_dn, p->dsdb_dn,
2736                                                    invocation_id, seq_num,
2737                                                    seq_num, now, 0, true);
2738                         if (ret != LDB_SUCCESS) {
2739                                 talloc_free(tmp_ctx);
2740                                 return ret;
2741                         }
2742                 }
2743
2744                 if (vanish_links) {
2745                         el->flags = LDB_FLAG_MOD_REPLACE;
2746                         talloc_free(tmp_ctx);
2747                         return LDB_SUCCESS;
2748                 }
2749         }
2750
2751
2752         for (i = 0; i < num_to_delete; i++) {
2753                 struct parsed_dn *p = &dns[i];
2754                 struct parsed_dn *exact = NULL;
2755                 struct parsed_dn *next = NULL;
2756                 ret = parsed_dn_find(ldb, old_dns, old_el->num_values,
2757                                      &p->guid,
2758                                      NULL,
2759                                      &exact, &next,
2760                                      schema_attr->syntax->ldap_oid);
2761                 if (ret != LDB_SUCCESS) {
2762                         talloc_free(tmp_ctx);
2763                         return ret;
2764                 }
2765                 if (exact == NULL) {
2766                         struct GUID_txt_buf buf;
2767                         ldb_asprintf_errstring(ldb, "Attribute %s doesn't "
2768                                                "exist for target GUID %s",
2769                                                el->name,
2770                                                GUID_buf_string(&p->guid, &buf));
2771                         if (ldb_attr_cmp(el->name, "member") == 0) {
2772                                 talloc_free(tmp_ctx);
2773                                 return LDB_ERR_UNWILLING_TO_PERFORM;
2774                         } else {
2775                                 talloc_free(tmp_ctx);
2776                                 return LDB_ERR_NO_SUCH_ATTRIBUTE;
2777                         }
2778                 }
2779
2780                 if (vanish_links) {
2781                         if (CHECK_DEBUGLVL(5)) {
2782                                 rmd_flags = dsdb_dn_rmd_flags(exact->dsdb_dn->dn);
2783                                 if ((rmd_flags & DSDB_RMD_FLAG_DELETED)) {
2784                                         struct GUID_txt_buf buf;
2785                                         const char *guid_str = \
2786                                                 GUID_buf_string(&p->guid, &buf);
2787                                         DEBUG(5, ("Deleting deleted linked "
2788                                                   "attribute %s to %s, because "
2789                                                   "vanish_links control is set\n",
2790                                                   el->name, guid_str));
2791                                 }
2792                         }
2793
2794                         /* remove the backlink */
2795                         ret = replmd_add_backlink(module,
2796                                                   replmd_private,
2797                                                   schema, msg_guid,
2798                                                   &p->guid,
2799                                                   false, schema_attr,
2800                                                   true);
2801                         if (ret != LDB_SUCCESS) {
2802                                 talloc_free(tmp_ctx);
2803                                 return ret;
2804                         }
2805
2806                         /* We flag the deletion and tidy it up later. */
2807                         exact->v = NULL;
2808                         continue;
2809                 }
2810
2811                 rmd_flags = dsdb_dn_rmd_flags(exact->dsdb_dn->dn);
2812
2813                 if (rmd_flags & DSDB_RMD_FLAG_DELETED) {
2814                         struct GUID_txt_buf buf;
2815                         const char *guid_str = GUID_buf_string(&p->guid, &buf);
2816                         ldb_asprintf_errstring(ldb, "Attribute %s already "
2817                                                "deleted for target GUID %s",
2818                                                el->name, guid_str);
2819                         if (ldb_attr_cmp(el->name, "member") == 0) {
2820                                 talloc_free(tmp_ctx);
2821                                 return LDB_ERR_UNWILLING_TO_PERFORM;
2822                         } else {
2823                                 talloc_free(tmp_ctx);
2824                                 return LDB_ERR_NO_SUCH_ATTRIBUTE;
2825                         }
2826                 }
2827
2828                 ret = replmd_update_la_val(old_el->values, exact->v,
2829                                            exact->dsdb_dn, exact->dsdb_dn,
2830                                            invocation_id, seq_num, seq_num,
2831                                            now, 0, true);
2832                 if (ret != LDB_SUCCESS) {
2833                         talloc_free(tmp_ctx);
2834                         return ret;
2835                 }
2836                 ret = replmd_add_backlink(module, replmd_private,
2837                                           schema, msg_guid, &p->guid,
2838                                           false, schema_attr, true);
2839                 if (ret != LDB_SUCCESS) {
2840                         talloc_free(tmp_ctx);
2841                         return ret;
2842                 }
2843         }
2844
2845         if (vanish_links) {
2846                 unsigned j = 0;
2847                 for (i = 0; i < old_el->num_values; i++) {
2848                         if (old_dns[i].v != NULL) {
2849                                 old_el->values[j] = *old_dns[i].v;
2850                                 j++;
2851                         }
2852                 }
2853                 old_el->num_values = j;
2854         }
2855
2856         el->values = talloc_steal(msg->elements, old_el->values);
2857         el->num_values = old_el->num_values;
2858
2859         talloc_free(tmp_ctx);
2860
2861         /* we now tell the backend to replace all existing values
2862            with the one we have constructed */
2863         el->flags = LDB_FLAG_MOD_REPLACE;
2864
2865         return LDB_SUCCESS;
2866 }
2867
2868 /*
2869   handle replacing a linked attribute
2870  */
2871 static int replmd_modify_la_replace(struct ldb_module *module,
2872                                     struct replmd_private *replmd_private,
2873                                     const struct dsdb_schema *schema,
2874                                     struct ldb_message *msg,
2875                                     struct ldb_message_element *el,
2876                                     struct ldb_message_element *old_el,
2877                                     const struct dsdb_attribute *schema_attr,
2878                                     uint64_t seq_num,
2879                                     time_t t,
2880                                     struct GUID *msg_guid,
2881                                     struct ldb_request *parent)
2882 {
2883         unsigned int i, old_i, new_i;
2884         struct parsed_dn *dns, *old_dns;
2885         TALLOC_CTX *tmp_ctx = talloc_new(msg);
2886         int ret;
2887         const struct GUID *invocation_id;
2888         struct ldb_context *ldb = ldb_module_get_ctx(module);
2889         struct ldb_val *new_values = NULL;
2890         const char *ldap_oid = schema_attr->syntax->ldap_oid;
2891         unsigned int old_num_values;
2892         unsigned int repl_num_values;
2893         unsigned int max_num_values;
2894         NTTIME now;
2895
2896         unix_to_nt_time(&now, t);
2897
2898         invocation_id = samdb_ntds_invocation_id(ldb);
2899         if (!invocation_id) {
2900                 return LDB_ERR_OPERATIONS_ERROR;
2901         }
2902
2903         /*
2904          * The replace operation is unlike the replace and delete cases in that
2905          * we need to look at every existing link to see whether it is being
2906          * retained or deleted. In other words, we can't avoid parsing the GUIDs.
2907          *
2908          * As we are trying to combine two sorted lists, the algorithm we use
2909          * is akin to the merge phase of a merge sort. We interleave the two
2910          * lists, doing different things depending on which side the current
2911          * item came from.
2912          *
2913          * There are three main cases, with some sub-cases.
2914          *
2915          *  - a DN is in the old list but not the new one. It needs to be
2916          *    marked as deleted (but left in the list).
2917          *     - maybe it is already deleted, and we have less to do.
2918          *
2919          *  - a DN is in both lists. The old data gets replaced by the new,
2920          *    and the list doesn't grow. The old link may have been marked as
2921          *    deleted, in which case we undelete it.
2922          *
2923          *  - a DN is in the new list only. We add it in the right place.
2924          */
2925
2926         old_num_values = old_el ? old_el->num_values : 0;
2927         repl_num_values = el->num_values;
2928         max_num_values = old_num_values + repl_num_values;
2929
2930         if (max_num_values == 0) {
2931                 /* There is nothing to do! */
2932                 return LDB_SUCCESS;
2933         }
2934
2935         ret = get_parsed_dns(module, tmp_ctx, el, &dns, ldap_oid, parent);
2936         if (ret != LDB_SUCCESS) {
2937                 talloc_free(tmp_ctx);
2938                 return ret;
2939         }
2940
2941         ret = get_parsed_dns(module, tmp_ctx, old_el, &old_dns,
2942                              ldap_oid, parent);
2943         if (ret != LDB_SUCCESS) {
2944                 talloc_free(tmp_ctx);
2945                 return ret;
2946         }
2947
2948         ret = replmd_check_upgrade_links(ldb, old_dns, old_num_values,
2949                                          old_el, ld