source/lib/ldb/modules/objectclass.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Andrew Bartlett <abartlet@samba.org> 2005
   5
   6      ** NOTE! The following LGPL license applies to the ldb
   7      ** library. This does NOT imply that all of Samba is released
   8      ** under the LGPL
   9
  10    This library is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU Lesser General Public
  12    License as published by the Free Software Foundation; either
  13    version 2 of the License, or (at your option) any later version.
  14
  15    This library 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 GNU
  18    Lesser General Public License for more details.
  19
  20    You should have received a copy of the GNU Lesser General Public
  21    License along with this library; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23 */
  24
  25 /*
  26  *  Name: ldb
  27  *
  28  *  Component: objectClass sorting module
  29  *
  30  *  Description: sort the objectClass attribute into the class hierarchy
  31  *
  32  *  Author: Andrew Bartlett
  33  */
  34
  35 #include "includes.h"
  36 #include "ldb/include/ldb.h"
  37 #include "ldb/include/ldb_private.h"
  38 #include "ldb/include/ldb_errors.h"
  39 #include "ldb/include/dlinklist.h"
  40
  41 /* It turns out the MMC assumes that the last objectClass in the list
  42  * is the most specific subclass.  As such, we must sort the list,
  43  * according to the schema.
  44  *
  45  * For performance, we do this on the add/modify, not on the search
  46  *
  47  * We perform the original add/modify, then search for that is now in
  48  * the objectClass list. We can then then replace that with the new
  49  * sorted list.  The backend is expected to preserve ordering for
  50  * subsequent searches.
  51  *
  52  * We are in a transaction, so this is all perfectly safe...
  53  */
  54
  55 static int objectclass_handle(struct ldb_module *module, struct ldb_request *req, const struct ldb_message *msg)
  56 {
  57         TALLOC_CTX *mem_ctx;
  58         int ret;
  59         struct ldb_request search_request;
  60         struct ldb_request modify_request;
  61         struct ldb_message *modify_msg;
  62         struct ldb_result *res;
  63         const char *attrs[] = { "objectClass", NULL };
  64         struct class_list {
  65                 struct class_list *prev, *next;
  66                 const char *objectclass;
  67         };
  68         struct class_list *sorted = NULL, *parent_class = NULL,
  69                 *subclass = NULL, *unsorted = NULL, *current, *poss_subclass;
  70         int i;
  71         int layer;
  72
  73         struct ldb_message_element *objectclass_element;
  74
  75         ldb_debug(module->ldb, LDB_DEBUG_TRACE, "objectclass_handle\n");
  76
  77         if (ldb_dn_is_special(msg->dn)) { /* do not manipulate our control entries */
  78                 return ldb_next_request(module, req);
  79         }
  80
  81         ret = ldb_next_request(module, req);
  82
  83         if (ret) {
  84                 return ret;
  85         }
  86
  87         if (ldb_msg_find_element(msg, "objectClass") == NULL ) {
  88                 /* No sign of the objectClass:  no change, nothing to see here */
  89                 return ret;
  90         }
  91
  92         /* Thanks to transactions: Now do a search, find the full list
  93          * of objectClasses and do the sort */
  94
  95         search_request.operation       = LDB_REQ_SEARCH;
  96         search_request.op.search.base  = msg->dn;
  97         search_request.op.search.scope = LDB_SCOPE_BASE;
  98         search_request.op.search.tree  = ldb_parse_tree(module->ldb, NULL);
  99         search_request.op.search.attrs = attrs;
 100
 101         ret = ldb_next_request(module, &search_request);
 102         if (ret) {
 103                 return ret;
 104         }
 105
 106         mem_ctx = talloc_new(module);
 107         if (!mem_ctx) {
 108                 return LDB_ERR_OPERATIONS_ERROR;
 109         }
 110
 111         res = search_request.op.search.res;
 112         talloc_steal(mem_ctx, res);
 113         if (res->count != 1) {
 114                 ldb_set_errstring(module,
 115                                   talloc_asprintf(mem_ctx, "objectClass_handle: "
 116                                                   "search for %s found %d != 1 objects, for entry we just added/modified",
 117                                                   ldb_dn_linearize(mem_ctx, msg->dn),
 118                                                   res->count));
 119                 /* What happened?  The above add/modify worked... */
 120                 talloc_free(mem_ctx);
 121                 return LDB_ERR_NO_SUCH_OBJECT;
 122         }
 123
 124         /* This is now the objectClass list from the database */
 125         objectclass_element = ldb_msg_find_element(res->msgs[0], "objectClass");
 126         if (!objectclass_element) {
 127                 /* Perhaps the above was a remove?  Move along now, nothing to see here */
 128                 talloc_free(mem_ctx);
 129                 return LDB_SUCCESS;
 130         }
 131
 132         /* DESIGN:
 133          *
 134          * We work on 4 different 'bins' (implemented here as linked lists):
 135          *
 136          * * sorted:       the eventual list, in the order we wish to push
 137          *                 into the database.  This is the only ordered list.
 138          *
 139          * * parent_class: The current parent class 'bin' we are
 140          *                 trying to find subclasses for
 141          *
 142          * * subclass:     The subclasses we have found so far
 143          *
 144          * * unsorted:     The remaining objectClasses
 145          *
 146          * The process is a matter of filtering objectClasses up from
 147          * unsorted into sorted.  Order is irrelevent in the later 3 'bins'.
 148          *
 149          * We start with 'top' (found and promoted to parent_class
 150          * initially).  Then we find (in unsorted) all the direct
 151          * subclasses of 'top'.  parent_classes is concatenated onto
 152          * the end of 'sorted', and subclass becomes the list in
 153          * parent_class.
 154          *
 155          * We then repeat, until we find no more subclasses.  Any left
 156          * over classes are added to the end.
 157          *
 158          */
 159
 160         /* Firstly, dump all the objectClass elements into the
 161          * unsorted bin, except for 'top', which is special */
 162         for (i=0; i < objectclass_element->num_values; i++) {
 163                 current = talloc(mem_ctx, struct class_list);
 164                 if (!current) {
 165                         talloc_free(mem_ctx);
 166                         return LDB_ERR_OPERATIONS_ERROR;
 167                 }
 168                 current->objectclass = (const char *)objectclass_element->values[i].data;
 169
 170                 /* this is the root of the tree.  We will start
 171                  * looking for subclasses from here */
 172                 if (ldb_attr_cmp("top", current->objectclass) == 0) {
 173                         DLIST_ADD(parent_class, current);
 174                 } else {
 175                         DLIST_ADD(unsorted, current);
 176                 }
 177         }
 178
 179         /* DEBUGGING aid:  how many layers are we down now? */
 180         layer = 0;
 181         do {
 182                 layer++;
 183                 /* Find all the subclasses of classes in the
 184                  * parent_classes.  Push them onto the subclass list */
 185
 186                 /* Ensure we don't bother if there are no unsorted entries left */
 187                 for (current = parent_class; unsorted && current; current = current->next) {
 188                         const char **subclasses = ldb_subclass_list(module->ldb, current->objectclass);
 189
 190                         /* Walk the list of possible subclasses in unsorted */
 191                         for (poss_subclass = unsorted; poss_subclass; ) {
 192                                 struct class_list *next;
 193
 194                                 /* Save the next pointer, as the DLIST_ macros will change poss_subclass->next */
 195                                 next = poss_subclass->next;
 196
 197                                 for (i = 0; subclasses && subclasses[i]; i++) {
 198                                         if (ldb_attr_cmp(poss_subclass->objectclass, subclasses[i]) == 0) {
 199                                                 DLIST_REMOVE(unsorted, poss_subclass);
 200                                                 DLIST_ADD(subclass, poss_subclass);
 201
 202                                                 break;
 203                                         }
 204                                 }
 205                                 poss_subclass = next;
 206                         }
 207                 }
 208
 209                 /* Now push the parent_classes as sorted, we are done with
 210                 these.  Add to the END of the list by concatenation */
 211                 DLIST_CONCATENATE(sorted, parent_class, struct class_list *);
 212
 213                 /* and now find subclasses of these */
 214                 parent_class = subclass;
 215                 subclass = NULL;
 216
 217                 /* If we didn't find any subclasses we will fall out
 218                  * the bottom here */
 219         } while (parent_class);
 220
 221         /* This shouldn't happen, and would break MMC, but we can't
 222          * afford to loose objectClasses.  Perhaps there was no 'top',
 223          * or some other schema error?
 224          *
 225          * Detecting schema errors is the job of the schema module, so
 226          * at this layer we just try not to loose data
 227          */
 228         DLIST_CONCATENATE(sorted, unsorted, struct class_list *);
 229
 230         modify_msg = ldb_msg_new(mem_ctx);
 231         if (!modify_msg) {
 232                 talloc_free(mem_ctx);
 233                 return LDB_ERR_OPERATIONS_ERROR;
 234         }
 235         modify_msg->dn = talloc_reference(modify_msg, msg->dn);
 236
 237         /* We must completely replace the existing objectClass entry.
 238          * We could do a constrained add/del, but we are meant to be
 239          * in a transaction... */
 240
 241         ret = ldb_msg_add_empty(modify_msg, "objectClass", LDB_FLAG_MOD_REPLACE);
 242         if (ret != LDB_SUCCESS) {
 243                 talloc_free(mem_ctx);
 244                 return ret;
 245         }
 246
 247         /* Move from the linked list back into an ldb msg */
 248         for (current = sorted; current; current = current->next) {
 249                 ret = ldb_msg_add_string(modify_msg, "objectClass", current->objectclass);
 250                 if (ret != LDB_SUCCESS) {
 251                         talloc_free(mem_ctx);
 252                         return ret;
 253                 }
 254         }
 255
 256         ret = ldb_msg_sanity_check(modify_msg);
 257         if (ret != LDB_SUCCESS) {
 258                 talloc_free(mem_ctx);
 259                 return ret;
 260         }
 261
 262         modify_request.operation = LDB_REQ_MODIFY;
 263         modify_request.op.mod.message = modify_msg;
 264
 265         /* And now push the write into the database */
 266         ret = ldb_next_request(module, &modify_request);
 267
 268         talloc_free(mem_ctx);
 269         return ret;
 270 }
 271
 272 static int objectclass_request(struct ldb_module *module, struct ldb_request *req)
 273 {
 274         switch (req->operation) {
 275
 276                 /* only care about add and modify requests */
 277         case LDB_REQ_ADD:
 278                 return objectclass_handle(module, req, req->op.add.message);
 279
 280         case LDB_REQ_MODIFY:
 281                 return objectclass_handle(module, req, req->op.mod.message);
 282
 283         default:
 284                 return ldb_next_request(module, req);
 285
 286         }
 287 }
 288
 289 static const struct ldb_module_ops objectclass_ops = {
 290         .name              = "objectclass",
 291         .request           = objectclass_request,
 292 };
 293
 294 struct ldb_module *objectclass_module_init(struct ldb_context *ldb, const char *options[])
 295 {
 296         struct ldb_module *ctx;
 297
 298         ctx = talloc(ldb, struct ldb_module);
 299         if (!ctx)
 300                 return NULL;
 301
 302         ctx->private_data = NULL;
 303
 304         ctx->ldb = ldb;
 305         ctx->prev = ctx->next = NULL;
 306         ctx->ops = &objectclass_ops;
 307
 308         return ctx;
 309 }