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