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