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