lib/ldb/modules/sort.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Simo Sorce  2005-2008
   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 3 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, see <http://www.gnu.org/licenses/>.
  22 */
  23
  24 /*
  25  *  Name: ldb
  26  *
  27  *  Component: ldb server side sort control module
  28  *
  29  *  Description: this module sorts the results of a search
  30  *
  31  *  Author: Simo Sorce
  32  */
  33
  34 #include "replace.h"
  35 #include "system/filesys.h"
  36 #include "system/time.h"
  37 #include "ldb_module.h"
  38
  39 struct opaque {
  40         struct ldb_context *ldb;
  41         const struct ldb_attrib_handler *h;
  42         const char *attribute;
  43         int reverse;
  44         int result;
  45 };
  46
  47 struct sort_context {
  48         struct ldb_module *module;
  49
  50         const char *attributeName;
  51         const char *orderingRule;
  52         int reverse;
  53
  54         struct ldb_request *req;
  55         struct ldb_message **msgs;
  56         char **referrals;
  57         unsigned int num_msgs;
  58         unsigned int num_refs;
  59         const char *extra_sort_key;
  60
  61         const struct ldb_schema_attribute *a;
  62         int sort_result;
  63 };
  64
  65 static int build_response(void *mem_ctx, struct ldb_control ***ctrls, int result, const char *desc)
  66 {
  67         struct ldb_control **controls;
  68         struct ldb_sort_resp_control *resp;
  69         unsigned int i;
  70
  71         if (*ctrls) {
  72                 controls = *ctrls;
  73                 for (i = 0; controls[i]; i++);
  74                 controls = talloc_realloc(mem_ctx, controls, struct ldb_control *, i + 2);
  75         } else {
  76                 i = 0;
  77                 controls = talloc_array(mem_ctx, struct ldb_control *, 2);
  78         }
  79         if (! controls )
  80                 return LDB_ERR_OPERATIONS_ERROR;
  81
  82         *ctrls = controls;
  83
  84         controls[i+1] = NULL;
  85         controls[i] = talloc(controls, struct ldb_control);
  86         if (! controls[i] )
  87                 return LDB_ERR_OPERATIONS_ERROR;
  88
  89         controls[i]->oid = LDB_CONTROL_SORT_RESP_OID;
  90         controls[i]->critical = 0;
  91
  92         resp = talloc(controls[i], struct ldb_sort_resp_control);
  93         if (! resp )
  94                 return LDB_ERR_OPERATIONS_ERROR;
  95
  96         resp->result = result;
  97         resp->attr_desc = talloc_strdup(resp, desc);
  98
  99         if (! resp->attr_desc )
 100                 return LDB_ERR_OPERATIONS_ERROR;
 101
 102         controls[i]->data = resp;
 103
 104         return LDB_SUCCESS;
 105 }
 106
 107 static int sort_compare(struct ldb_message **msg1, struct ldb_message **msg2, void *opaque)
 108 {
 109         struct sort_context *ac = talloc_get_type(opaque, struct sort_context);
 110         struct ldb_message_element *el1, *el2;
 111         struct ldb_context *ldb;
 112
 113         ldb = ldb_module_get_ctx(ac->module);
 114
 115         if (ac->sort_result != 0) {
 116                 /* an error occurred previously,
 117                  * let's exit the sorting by returning always 0 */
 118                 return 0;
 119         }
 120
 121         el1 = ldb_msg_find_element(*msg1, ac->attributeName);
 122         el2 = ldb_msg_find_element(*msg2, ac->attributeName);
 123
 124         /*
 125          * NULL elements sort at the end (regardless of ac->reverse flag).
 126          */
 127         if (el1 == NULL && el2 == NULL) {
 128                 return 0;
 129         }
 130         if (el1 == NULL) {
 131                 return 1;
 132         }
 133         if (el2 == NULL) {
 134                 return -1;
 135         }
 136
 137         if (ac->reverse)
 138                 return ac->a->syntax->comparison_fn(ldb, ac, &el2->values[0], &el1->values[0]);
 139
 140         return ac->a->syntax->comparison_fn(ldb, ac, &el1->values[0], &el2->values[0]);
 141 }
 142
 143 static int server_sort_results(struct sort_context *ac)
 144 {
 145         struct ldb_context *ldb;
 146         struct ldb_reply *ares;
 147         unsigned int i;
 148         int ret;
 149
 150         ldb = ldb_module_get_ctx(ac->module);
 151
 152         ac->a = ldb_schema_attribute_by_name(ldb, ac->attributeName);
 153         ac->sort_result = 0;
 154
 155         LDB_TYPESAFE_QSORT(ac->msgs, ac->num_msgs, ac, sort_compare);
 156
 157         if (ac->sort_result != LDB_SUCCESS) {
 158                 return ac->sort_result;
 159         }
 160
 161         for (i = 0; i < ac->num_msgs; i++) {
 162                 ares = talloc_zero(ac, struct ldb_reply);
 163                 if (!ares) {
 164                         return LDB_ERR_OPERATIONS_ERROR;
 165                 }
 166
 167                 ares->type = LDB_REPLY_ENTRY;
 168                 ares->message = talloc_move(ares, &ac->msgs[i]);
 169                 if (ac->extra_sort_key) {
 170                         ldb_msg_remove_attr(ares->message, ac->extra_sort_key);
 171                 }
 172                 ret = ldb_module_send_entry(ac->req, ares->message, ares->controls);
 173                 if (ret != LDB_SUCCESS) {
 174                         return ret;
 175                 }
 176         }
 177
 178         for (i = 0; i < ac->num_refs; i++) {
 179                 ares = talloc_zero(ac, struct ldb_reply);
 180                 if (!ares) {
 181                         return LDB_ERR_OPERATIONS_ERROR;
 182                 }
 183
 184                 ares->type = LDB_REPLY_REFERRAL;
 185                 ares->referral = talloc_move(ares, &ac->referrals[i]);
 186
 187                 ret = ldb_module_send_referral(ac->req, ares->referral);
 188                 if (ret != LDB_SUCCESS) {
 189                         return ret;
 190                 }
 191         }
 192
 193         return LDB_SUCCESS;
 194 }
 195
 196 static int server_sort_search_callback(struct ldb_request *req, struct ldb_reply *ares)
 197 {
 198         struct sort_context *ac;
 199         struct ldb_context *ldb;
 200         int ret;
 201
 202         ac = talloc_get_type(req->context, struct sort_context);
 203         ldb = ldb_module_get_ctx(ac->module);
 204
 205         if (!ares) {
 206                 return ldb_module_done(ac->req, NULL, NULL,
 207                                         LDB_ERR_OPERATIONS_ERROR);
 208         }
 209         if (ares->error != LDB_SUCCESS) {
 210                 return ldb_module_done(ac->req, ares->controls,
 211                                         ares->response, ares->error);
 212         }
 213
 214         switch (ares->type) {
 215         case LDB_REPLY_ENTRY:
 216                 ac->msgs = talloc_realloc(ac, ac->msgs, struct ldb_message *, ac->num_msgs + 2);
 217                 if (! ac->msgs) {
 218                         talloc_free(ares);
 219                         ldb_oom(ldb);
 220                         return ldb_module_done(ac->req, NULL, NULL,
 221                                                 LDB_ERR_OPERATIONS_ERROR);
 222                 }
 223
 224                 ac->msgs[ac->num_msgs] = talloc_steal(ac->msgs, ares->message);
 225                 ac->num_msgs++;
 226                 ac->msgs[ac->num_msgs] = NULL;
 227
 228                 break;
 229
 230         case LDB_REPLY_REFERRAL:
 231                 ac->referrals = talloc_realloc(ac, ac->referrals, char *, ac->num_refs + 2);
 232                 if (! ac->referrals) {
 233                         talloc_free(ares);
 234                         ldb_oom(ldb);
 235                         return ldb_module_done(ac->req, NULL, NULL,
 236                                                 LDB_ERR_OPERATIONS_ERROR);
 237                 }
 238
 239                 ac->referrals[ac->num_refs] = talloc_steal(ac->referrals, ares->referral);
 240                 ac->num_refs++;
 241                 ac->referrals[ac->num_refs] = NULL;
 242
 243                 break;
 244
 245         case LDB_REPLY_DONE:
 246
 247                 ret = server_sort_results(ac);
 248                 return ldb_module_done(ac->req, ares->controls,
 249                                         ares->response, ret);
 250         }
 251
 252         talloc_free(ares);
 253         return LDB_SUCCESS;
 254 }
 255
 256 static int server_sort_search(struct ldb_module *module, struct ldb_request *req)
 257 {
 258         struct ldb_control *control;
 259         struct ldb_server_sort_control **sort_ctrls;
 260         struct ldb_control **saved_controls;
 261         struct ldb_request *down_req;
 262         struct sort_context *ac;
 263         struct ldb_context *ldb;
 264         int ret;
 265         const char * const *attrs;
 266         size_t n_attrs, i;
 267         const char *sort_attr;
 268
 269         ldb = ldb_module_get_ctx(module);
 270
 271         /* check if there's a server sort control */
 272         control = ldb_request_get_control(req, LDB_CONTROL_SERVER_SORT_OID);
 273         if (control == NULL) {
 274                 /* not found go on */
 275                 return ldb_next_request(module, req);
 276         }
 277
 278         ac = talloc_zero(req, struct sort_context);
 279         if (ac == NULL) {
 280                 ldb_oom(ldb);
 281                 return LDB_ERR_OPERATIONS_ERROR;
 282         }
 283
 284         ac->module = module;
 285         ac->req = req;
 286
 287         sort_ctrls = talloc_get_type(control->data, struct ldb_server_sort_control *);
 288         if (!sort_ctrls) {
 289                 return LDB_ERR_PROTOCOL_ERROR;
 290         }
 291
 292         /* FIXME: we do not support more than one attribute for sorting right now */
 293         /* FIXME: we need to check if the attribute type exist or return an error */
 294
 295         if (sort_ctrls[1] != NULL) {
 296                 if (control->critical) {
 297                         struct ldb_control **controls = NULL;
 298
 299                         /* callback immediately */
 300                         ret = build_response(req, &controls,
 301                                              LDB_ERR_UNWILLING_TO_PERFORM,
 302                                              "sort control is not complete yet");
 303                         if (ret != LDB_SUCCESS) {
 304                                 return ldb_module_done(req, NULL, NULL,
 305                                                     LDB_ERR_OPERATIONS_ERROR);
 306                         }
 307
 308                         return ldb_module_done(req, controls, NULL, ret);
 309                 } else {
 310                         /* just pass the call down and don't do any sorting */
 311                         return ldb_next_request(module, req);
 312                 }
 313         }
 314
 315         control->critical = 0;
 316
 317         /* We are asked to sort on an attribute, and if that attribute is not
 318            already in the search attributes we need to add it (and later
 319            remove it on the return journey).
 320         */
 321         sort_attr = sort_ctrls[0]->attributeName;
 322         if (req->op.search.attrs == NULL) {
 323                 /* This means all non-operational attributes, which means
 324                    there's nothing to add. */
 325                 attrs = NULL;
 326         } else {
 327                 n_attrs = 0;
 328                 while (req->op.search.attrs[n_attrs] != NULL) {
 329                         if (sort_attr &&
 330                             strcmp(req->op.search.attrs[n_attrs], sort_attr) == 0) {
 331                                 sort_attr = NULL;
 332                         }
 333                         n_attrs++;
 334                 }
 335
 336                 if (sort_attr == NULL) {
 337                         attrs = req->op.search.attrs;
 338                 } else {
 339                         const char **tmp = talloc_array(ac, const char *, n_attrs + 2);
 340
 341                         for (i = 0; i < n_attrs; i++) {
 342                                 tmp[i] = req->op.search.attrs[i];
 343                         }
 344                         ac->extra_sort_key = sort_attr;
 345                         tmp[n_attrs] = sort_attr;
 346                         tmp[n_attrs + 1] = NULL;
 347                         attrs = tmp;
 348                 }
 349         }
 350
 351         ac->attributeName = sort_ctrls[0]->attributeName;
 352         ac->orderingRule = sort_ctrls[0]->orderingRule;
 353         ac->reverse = sort_ctrls[0]->reverse;
 354
 355         ret = ldb_build_search_req_ex(&down_req, ldb, ac,
 356                                         req->op.search.base,
 357                                         req->op.search.scope,
 358                                         req->op.search.tree,
 359                                         attrs,
 360                                         req->controls,
 361                                         ac,
 362                                         server_sort_search_callback,
 363                                         req);
 364         if (ret != LDB_SUCCESS) {
 365                 return ret;
 366         }
 367
 368         /* save it locally and remove it from the list */
 369         /* we do not need to replace them later as we
 370          * are keeping the original req intact */
 371         if (!ldb_save_controls(control, down_req, &saved_controls)) {
 372                 return LDB_ERR_OPERATIONS_ERROR;
 373         }
 374
 375         return ldb_next_request(module, down_req);
 376 }
 377
 378 static int server_sort_init(struct ldb_module *module)
 379 {
 380         struct ldb_context *ldb;
 381         int ret;
 382
 383         ldb = ldb_module_get_ctx(module);
 384
 385         ret = ldb_mod_register_control(module, LDB_CONTROL_SERVER_SORT_OID);
 386         if (ret != LDB_SUCCESS) {
 387                 ldb_debug(ldb, LDB_DEBUG_WARNING,
 388                         "server_sort:"
 389                         "Unable to register control with rootdse!");
 390         }
 391
 392         return ldb_next_init(module);
 393 }
 394
 395 static const struct ldb_module_ops ldb_server_sort_module_ops = {
 396         .name              = "server_sort",
 397         .search            = server_sort_search,
 398         .init_context      = server_sort_init
 399 };
 400
 401 int ldb_server_sort_init(const char *version)
 402 {
 403         LDB_MODULE_CHECK_VERSION(version);
 404         return ldb_register_module(&ldb_server_sort_module_ops);
 405 }