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