source4/dsdb/kcc/garbage_collect_tombstones.c

   1 /*
   2    Unix SMB/CIFS implementation.
   3
   4    handle removal of deleted objects
   5
   6    Copyright (C) 2009 Andrew Tridgell
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20
  21 */
  22
  23 #include "includes.h"
  24 #include <ldb_errors.h>
  25 #include "../lib/util/dlinklist.h"
  26 #include "librpc/gen_ndr/ndr_misc.h"
  27 #include "librpc/gen_ndr/ndr_drsuapi.h"
  28 #include "librpc/gen_ndr/ndr_drsblobs.h"
  29 #include "param/param.h"
  30 #include "lib/util/dlinklist.h"
  31 #include "ldb.h"
  32 #include "dsdb/kcc/garbage_collect_tombstones.h"
  33 #include "lib/ldb-samba/ldb_matching_rules.h"
  34 #include "lib/util/time.h"
  35
  36 /*
  37  * Per MS-ADTS 3.1.1.5.5 Delete Operation
  38  *
  39  * "Tombstones are a type of deleted object distinguished from
  40  *  existing-objects by the presence of the isDeleted attribute with the
  41  *  value true."
  42  *
  43  * "After a time period at least as large as a tombstone lifetime, the
  44  *  tombstone is removed from the directory."
  45  *
  46  * The purpose of this routine is to remove such objects.  It is
  47  * called from a timed event in the KCC, and from samba-tool domain
  48  * expunge tombstones.
  49  *
  50  * Additionally, linked attributes have similar properties.
  51  */
  52 NTSTATUS dsdb_garbage_collect_tombstones(TALLOC_CTX *mem_ctx,
  53                                          struct ldb_context *samdb,
  54                                          struct dsdb_ldb_dn_list_node *part,
  55                                          time_t current_time,
  56                                          uint32_t tombstoneLifetime,
  57                                          unsigned int *num_objects_removed,
  58                                          unsigned int *num_links_removed,
  59                                          char **error_string)
  60 {
  61         int ret;
  62
  63         const char **attrs = NULL;
  64         char *filter = NULL;
  65
  66         unsigned int i;
  67         struct dsdb_attribute *next_attr;
  68         unsigned int num_link_attrs;
  69         struct dsdb_schema *schema = dsdb_get_schema(samdb, mem_ctx);
  70         unsigned long long expunge_time = current_time - tombstoneLifetime*60*60*24;
  71         char *expunge_time_string = ldb_timestring_utc(mem_ctx, expunge_time);
  72         NTTIME expunge_time_nttime;
  73         unix_to_nt_time(&expunge_time_nttime, expunge_time);
  74
  75         *num_objects_removed = 0;
  76         *num_links_removed = 0;
  77         *error_string = NULL;
  78         num_link_attrs = 0;
  79
  80         /*
  81          * This filter is a bit strange, but the idea is to filter for
  82          * objects that need to have tombstones expunged without
  83          * bringing a potentially large databse all into memory.  To
  84          * do that, we could use callbacks, but instead we use a
  85          * custom match rule to triage the objects during the search,
  86          * and ideally avoid memory allocation for most of the
  87          * un-matched objects.
  88          *
  89          * The parameter to DSDB_MATCH_FOR_EXPUNGE is the NTTIME, we
  90          * return records with deleted links deleted before this time.
  91          *
  92          * We use a date comparison on whenChanged to avoid returning
  93          * all isDeleted records
  94          */
  95
  96         filter = talloc_asprintf(mem_ctx, "(|");
  97         for (next_attr = schema->attributes; next_attr != NULL; next_attr = next_attr->next) {
  98                 if (next_attr->linkID != 0 && ((next_attr->linkID & 1) == 0)) {
  99                         num_link_attrs++;
 100                         filter = talloc_asprintf_append(filter,
 101                                                         "(%s:" DSDB_MATCH_FOR_EXPUNGE ":=%llu)",
 102                                                         next_attr->lDAPDisplayName,
 103                                                         (unsigned long long)expunge_time_nttime);
 104                         if (filter == NULL) {
 105                                 return NT_STATUS_NO_MEMORY;
 106                         }
 107                 }
 108         }
 109
 110         attrs = talloc_array(mem_ctx, const char *, num_link_attrs + 2);
 111         i = 0;
 112         for (next_attr = schema->attributes; next_attr != NULL; next_attr = next_attr->next) {
 113                 if (next_attr->linkID != 0 && ((next_attr->linkID & 1) == 0)) {
 114                         attrs[i++] = next_attr->lDAPDisplayName;
 115                 }
 116         }
 117         attrs[i] = "isDeleted";
 118         attrs[i+1] = NULL;
 119
 120         filter = talloc_asprintf_append(filter, "(&(isDeleted=TRUE)(whenChanged<=%s)))", expunge_time_string);
 121         if (filter == NULL) {
 122                 return NT_STATUS_NO_MEMORY;
 123         }
 124
 125         schema = dsdb_get_schema(samdb, mem_ctx);
 126
 127         for (; part != NULL; part = part->next) {
 128                 struct ldb_dn *do_dn;
 129                 struct ldb_result *res;
 130                 unsigned int j, k;
 131                 uint32_t flags;
 132                 TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
 133                 if (!tmp_ctx) {
 134                         return NT_STATUS_NO_MEMORY;
 135                 }
 136
 137                 ret = dsdb_get_deleted_objects_dn(samdb, tmp_ctx, part->dn, &do_dn);
 138                 if (ret != LDB_SUCCESS) {
 139                         TALLOC_FREE(tmp_ctx);
 140                         /* some partitions have no Deleted Objects
 141                            container */
 142                         continue;
 143                 }
 144
 145                 DEBUG(1, ("Doing a full scan on %s and looking for deleted objects\n",
 146                           ldb_dn_get_linearized(part->dn)));
 147
 148                 flags = DSDB_SEARCH_SHOW_RECYCLED |
 149                         DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT |
 150                         DSDB_SEARCH_REVEAL_INTERNALS;
 151                 ret = dsdb_search(samdb, tmp_ctx, &res, part->dn, LDB_SCOPE_SUBTREE,
 152                                   attrs, flags, filter);
 153
 154                 if (ret != LDB_SUCCESS) {
 155                         *error_string = talloc_asprintf(mem_ctx, "Failed to search for deleted objects in %s: %s",
 156                                                         ldb_dn_get_linearized(do_dn),
 157                                                         ldb_errstring(samdb));
 158                         TALLOC_FREE(tmp_ctx);
 159                         return NT_STATUS_INTERNAL_ERROR;
 160                 }
 161
 162                 for (i=0; i<res->count; i++) {
 163                         struct ldb_message *cleanup_msg = NULL;
 164                         unsigned int num_modified = 0;
 165
 166                         bool isDeleted = ldb_msg_find_attr_as_bool(res->msgs[i], "isDeleted", false);
 167                         if (isDeleted) {
 168                                 if (ldb_dn_compare(do_dn, res->msgs[i]->dn) == 0) {
 169                                         /* Skip the Deleted Object Container */
 170                                         continue;
 171                                 }
 172
 173                                 ret = dsdb_delete(samdb, res->msgs[i]->dn, DSDB_SEARCH_SHOW_RECYCLED|DSDB_MODIFY_RELAX);
 174                                 if (ret != LDB_SUCCESS) {
 175                                         DEBUG(1,(__location__ ": Failed to remove deleted object %s\n",
 176                                                  ldb_dn_get_linearized(res->msgs[i]->dn)));
 177                                 } else {
 178                                         DEBUG(4,("Removed deleted object %s\n",
 179                                                  ldb_dn_get_linearized(res->msgs[i]->dn)));
 180                                         (*num_objects_removed)++;
 181                                 }
 182                                 continue;
 183                         }
 184
 185                         /* This must have a linked attribute */
 186
 187                         /*
 188                          * From MS-ADTS 3.1.1.1.9 DCs, usn Counters, and the Originating Update Stamp
 189                          *
 190                          * "A link value r is deleted, but exists as a
 191                          *  tombstone, if r.stamp.timeDeleted ≠ 0. When
 192                          *  the current time minus r.stamp.timeDeleted
 193                          *  exceeds the tombstone lifetime, the link
 194                          *  value r is garbage-collected; that is,
 195                          *  removed from its containing forward link
 196                          *  attribute. "
 197                          */
 198
 199                         for (j=0; j < res->msgs[i]->num_elements; j++) {
 200                                 struct ldb_message_element *element = &res->msgs[i]->elements[j];
 201                                 /* TODO this is O(log n) per attribute with deleted values */
 202                                 const struct dsdb_attribute *attrib
 203                                         = dsdb_attribute_by_lDAPDisplayName(schema, element->name);
 204
 205                                 /* This avoids parsing isDeleted as a link */
 206                                 if (attrib->linkID == 0 || ((attrib->linkID & 1) == 1)) {
 207                                         continue;
 208                                 }
 209
 210                                 for (k = 0; k < element->num_values; k++) {
 211                                         struct ldb_val *value = &element->values[k];
 212                                         uint64_t whenChanged = 0;
 213                                         NTSTATUS status;
 214                                         struct dsdb_dn *dn;
 215                                         struct ldb_message_element *cleanup_elem = NULL;
 216                                         char *guid_search_str = NULL, *guid_buf_str = NULL;
 217                                         struct ldb_val cleanup_val;
 218                                         struct GUID_txt_buf buf_guid;
 219                                         struct GUID guid;
 220                                         const struct ldb_val *guid_blob;
 221
 222                                         if (dsdb_dn_is_deleted_val(value) == false) {
 223                                                 continue;
 224                                         }
 225
 226                                         dn = dsdb_dn_parse(tmp_ctx, samdb, &element->values[k],
 227                                                            attrib->syntax->ldap_oid);
 228                                         if (dn == NULL) {
 229                                                 DEBUG(1, ("Failed to parse linked attribute blob of %s on %s while expunging expired links\n", element->name,
 230                                                           ldb_dn_get_linearized(res->msgs[i]->dn)));
 231                                                 continue;
 232                                         }
 233
 234                                         status = dsdb_get_extended_dn_uint64(dn->dn, &whenChanged, "RMD_CHANGETIME");
 235                                         if (!NT_STATUS_IS_OK(status)) {
 236                                                 DEBUG(1, ("Error: RMD_CHANGETIME is missing on a forward link.\n"));
 237                                                 talloc_free(dn);
 238                                                 continue;
 239                                         }
 240
 241                                         if (whenChanged >= expunge_time_nttime) {
 242                                                 talloc_free(dn);
 243                                                 continue;
 244                                         }
 245
 246                                         guid_blob = ldb_dn_get_extended_component(dn->dn, "GUID");
 247                                         status = GUID_from_ndr_blob(guid_blob, &guid);
 248                                         if (!NT_STATUS_IS_OK(status)) {
 249                                                 DEBUG(1, ("Error: Invalid GUID on link target.\n"));
 250                                                 talloc_free(dn);
 251                                                 continue;
 252                                         }
 253
 254                                         guid_buf_str = GUID_buf_string(&guid, &buf_guid);
 255                                         guid_search_str = talloc_asprintf(mem_ctx, "<GUID=%s>", guid_buf_str);
 256                                         cleanup_val = data_blob_string_const(guid_search_str);
 257
 258                                         talloc_free(dn);
 259
 260                                         if (cleanup_msg == NULL) {
 261                                                 cleanup_msg = ldb_msg_new(mem_ctx);
 262                                                 if (cleanup_msg == NULL) {
 263                                                         return NT_STATUS_NO_MEMORY;
 264                                                 }
 265                                                 cleanup_msg->dn = res->msgs[i]->dn;
 266                                         }
 267
 268                                         ret = ldb_msg_add_value(cleanup_msg, element->name, &cleanup_val, &cleanup_elem);
 269                                         if (ret != LDB_SUCCESS) {
 270                                                 return NT_STATUS_NO_MEMORY;
 271                                         }
 272                                         cleanup_elem->flags = LDB_FLAG_MOD_DELETE;
 273                                         num_modified++;
 274                                 }
 275                         }
 276
 277                         if (num_modified > 0) {
 278                                 ret = dsdb_modify(samdb, cleanup_msg, DSDB_REPLMD_VANISH_LINKS);
 279                                 if (ret != LDB_SUCCESS) {
 280                                         DEBUG(1,(__location__ ": Failed to remove deleted object %s\n",
 281                                                  ldb_dn_get_linearized(res->msgs[i]->dn)));
 282                                 } else {
 283                                         DEBUG(4,("Removed deleted object %s\n",
 284                                                  ldb_dn_get_linearized(res->msgs[i]->dn)));
 285                                         *num_links_removed = *num_links_removed + num_modified;
 286                                 }
 287
 288                         }
 289                 }
 290                 TALLOC_FREE(tmp_ctx);
 291
 292         }
 293
 294         return NT_STATUS_OK;
 295 }