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 and empty elements sort at the end (regardless of ac->reverse flag).
 126          * NULL elements come after empty ones.
 127          */
 128         if (el1 == el2) {
 129                 return 0;
 130         }
 131         if (el1 == NULL) {
 132                 return 1;
 133         }
 134         if (el2 == NULL) {
 135                 return -1;
 136         }
 137         if (unlikely(el1->num_values == 0 && el2->num_values == 0)) {
 138                 return 0;
 139         }
 140         if (unlikely(el1->num_values == 0)) {
 141                 return 1;
 142         }
 143         if (unlikely(el2->num_values == 0)) {
 144                 return -1;
 145         }
 146
 147         if (ac->reverse)
 148                 return ac->a->syntax->comparison_fn(ldb, ac, &el2->values[0], &el1->values[0]);
 149
 150         return ac->a->syntax->comparison_fn(ldb, ac, &el1->values[0], &el2->values[0]);
 151 }
 152
 153 static int server_sort_results(struct sort_context *ac)
 154 {
 155         struct ldb_context *ldb;
 156         struct ldb_reply *ares;
 157         unsigned int i;
 158         int ret;
 159
 160         ldb = ldb_module_get_ctx(ac->module);
 161
 162         ac->a = ldb_schema_attribute_by_name(ldb, ac->attributeName);
 163         ac->sort_result = 0;
 164
 165         LDB_TYPESAFE_QSORT(ac->msgs, ac->num_msgs, ac, sort_compare);
 166
 167         if (ac->sort_result != LDB_SUCCESS) {
 168                 return ac->sort_result;
 169         }
 170
 171         for (i = 0; i < ac->num_msgs; i++) {
 172                 ares = talloc_zero(ac, struct ldb_reply);
 173                 if (!ares) {
 174                         return LDB_ERR_OPERATIONS_ERROR;
 175                 }
 176
 177                 ares->type = LDB_REPLY_ENTRY;
 178                 ares->message = talloc_move(ares, &ac->msgs[i]);
 179                 if (ac->extra_sort_key) {
 180                         ldb_msg_remove_attr(ares->message, ac->extra_sort_key);
 181                 }
 182                 ret = ldb_module_send_entry(ac->req, ares->message, ares->controls);
 183                 if (ret != LDB_SUCCESS) {
 184                         return ret;
 185                 }
 186         }
 187
 188         for (i = 0; i < ac->num_refs; i++) {
 189                 ares = talloc_zero(ac, struct ldb_reply);
 190                 if (!ares) {
 191                         return LDB_ERR_OPERATIONS_ERROR;
 192                 }
 193
 194                 ares->type = LDB_REPLY_REFERRAL;
 195                 ares->referral = talloc_move(ares, &ac->referrals[i]);
 196
 197                 ret = ldb_module_send_referral(ac->req, ares->referral);
 198                 if (ret != LDB_SUCCESS) {
 199                         return ret;
 200                 }
 201         }
 202
 203         return LDB_SUCCESS;
 204 }
 205
 206 static int server_sort_search_callback(struct ldb_request *req, struct ldb_reply *ares)
 207 {
 208         struct sort_context *ac;
 209         struct ldb_context *ldb;
 210         int ret;
 211
 212         ac = talloc_get_type(req->context, struct sort_context);
 213         ldb = ldb_module_get_ctx(ac->module);
 214
 215         if (!ares) {
 216                 return ldb_module_done(ac->req, NULL, NULL,
 217                                         LDB_ERR_OPERATIONS_ERROR);
 218         }
 219         if (ares->error != LDB_SUCCESS) {
 220                 return ldb_module_done(ac->req, ares->controls,
 221                                         ares->response, ares->error);
 222         }
 223
 224         switch (ares->type) {
 225         case LDB_REPLY_ENTRY:
 226                 ac->msgs = talloc_realloc(ac, ac->msgs, struct ldb_message *, ac->num_msgs + 2);
 227                 if (! ac->msgs) {
 228                         talloc_free(ares);
 229                         ldb_oom(ldb);
 230                         return ldb_module_done(ac->req, NULL, NULL,
 231                                                 LDB_ERR_OPERATIONS_ERROR);
 232                 }
 233
 234                 ac->msgs[ac->num_msgs] = talloc_steal(ac->msgs, ares->message);
 235                 ac->num_msgs++;
 236                 ac->msgs[ac->num_msgs] = NULL;
 237
 238                 break;
 239
 240         case LDB_REPLY_REFERRAL:
 241                 ac->referrals = talloc_realloc(ac, ac->referrals, char *, ac->num_refs + 2);
 242                 if (! ac->referrals) {
 243                         talloc_free(ares);
 244                         ldb_oom(ldb);
 245                         return ldb_module_done(ac->req, NULL, NULL,
 246                                                 LDB_ERR_OPERATIONS_ERROR);
 247                 }
 248
 249                 ac->referrals[ac->num_refs] = talloc_steal(ac->referrals, ares->referral);
 250                 ac->num_refs++;
 251                 ac->referrals[ac->num_refs] = NULL;
 252
 253                 break;
 254
 255         case LDB_REPLY_DONE:
 256
 257                 ret = server_sort_results(ac);
 258                 return ldb_module_done(ac->req, ares->controls,
 259                                         ares->response, ret);
 260         }
 261
 262         talloc_free(ares);
 263         return LDB_SUCCESS;
 264 }
 265
 266 static int server_sort_search(struct ldb_module *module, struct ldb_request *req)
 267 {
 268         struct ldb_control *control;
 269         struct ldb_server_sort_control **sort_ctrls;
 270         struct ldb_control **saved_controls;
 271         struct ldb_request *down_req;
 272         struct sort_context *ac;
 273         struct ldb_context *ldb;
 274         int ret;
 275         const char * const *attrs;
 276         size_t n_attrs, i;
 277         const char *sort_attr;
 278
 279         ldb = ldb_module_get_ctx(module);
 280
 281         /* check if there's a server sort control */
 282         control = ldb_request_get_control(req, LDB_CONTROL_SERVER_SORT_OID);
 283         if (control == NULL) {
 284                 /* not found go on */
 285                 return ldb_next_request(module, req);
 286         }
 287
 288         ac = talloc_zero(req, struct sort_context);
 289         if (ac == NULL) {
 290                 ldb_oom(ldb);
 291                 return LDB_ERR_OPERATIONS_ERROR;
 292         }
 293
 294         ac->module = module;
 295         ac->req = req;
 296
 297         sort_ctrls = talloc_get_type(control->data, struct ldb_server_sort_control *);
 298         if (!sort_ctrls) {
 299                 return LDB_ERR_PROTOCOL_ERROR;
 300         }
 301
 302         /* FIXME: we do not support more than one attribute for sorting right now */
 303         /* FIXME: we need to check if the attribute type exist or return an error */
 304
 305         if (sort_ctrls[1] != NULL) {
 306                 if (control->critical) {
 307                         struct ldb_control **controls = NULL;
 308
 309                         /* callback immediately */
 310                         ret = build_response(req, &controls,
 311                                              LDB_ERR_UNWILLING_TO_PERFORM,
 312                                              "sort control is not complete yet");
 313                         if (ret != LDB_SUCCESS) {
 314                                 return ldb_module_done(req, NULL, NULL,
 315                                                     LDB_ERR_OPERATIONS_ERROR);
 316                         }
 317
 318                         return ldb_module_done(req, controls, NULL, ret);
 319                 } else {
 320                         /* just pass the call down and don't do any sorting */
 321                         return ldb_next_request(module, req);
 322                 }
 323         }
 324
 325         control->critical = 0;
 326
 327         /* We are asked to sort on an attribute, and if that attribute is not
 328            already in the search attributes we need to add it (and later
 329            remove it on the return journey).
 330         */
 331         sort_attr = sort_ctrls[0]->attributeName;
 332         if (req->op.search.attrs == NULL) {
 333                 /* This means all non-operational attributes, which means
 334                    there's nothing to add. */
 335                 attrs = NULL;
 336         } else {
 337                 n_attrs = 0;
 338                 while (req->op.search.attrs[n_attrs] != NULL) {
 339                         if (sort_attr &&
 340                             strcmp(req->op.search.attrs[n_attrs], sort_attr) == 0) {
 341                                 sort_attr = NULL;
 342                         }
 343                         n_attrs++;
 344                 }
 345
 346                 if (sort_attr == NULL) {
 347                         attrs = req->op.search.attrs;
 348                 } else {
 349                         const char **tmp = talloc_array(ac, const char *, n_attrs + 2);
 350
 351                         for (i = 0; i < n_attrs; i++) {
 352                                 tmp[i] = req->op.search.attrs[i];
 353                         }
 354                         ac->extra_sort_key = sort_attr;
 355                         tmp[n_attrs] = sort_attr;
 356                         tmp[n_attrs + 1] = NULL;
 357                         attrs = tmp;
 358                 }
 359         }
 360
 361         ac->attributeName = sort_ctrls[0]->attributeName;
 362         ac->orderingRule = sort_ctrls[0]->orderingRule;
 363         ac->reverse = sort_ctrls[0]->reverse;
 364
 365         ret = ldb_build_search_req_ex(&down_req, ldb, ac,
 366                                         req->op.search.base,
 367                                         req->op.search.scope,
 368                                         req->op.search.tree,
 369                                         attrs,
 370                                         req->controls,
 371                                         ac,
 372                                         server_sort_search_callback,
 373                                         req);
 374         if (ret != LDB_SUCCESS) {
 375                 return ret;
 376         }
 377
 378         /* save it locally and remove it from the list */
 379         /* we do not need to replace them later as we
 380          * are keeping the original req intact */
 381         if (!ldb_save_controls(control, down_req, &saved_controls)) {
 382                 return LDB_ERR_OPERATIONS_ERROR;
 383         }
 384
 385         return ldb_next_request(module, down_req);
 386 }
 387
 388 static int server_sort_init(struct ldb_module *module)
 389 {
 390         struct ldb_context *ldb;
 391         int ret;
 392
 393         ldb = ldb_module_get_ctx(module);
 394
 395         ret = ldb_mod_register_control(module, LDB_CONTROL_SERVER_SORT_OID);
 396         if (ret != LDB_SUCCESS) {
 397                 ldb_debug(ldb, LDB_DEBUG_WARNING,
 398                         "server_sort:"
 399                         "Unable to register control with rootdse!");
 400         }
 401
 402         return ldb_next_init(module);
 403 }
 404
 405 static const struct ldb_module_ops ldb_server_sort_module_ops = {
 406         .name              = "server_sort",
 407         .search            = server_sort_search,
 408         .init_context      = server_sort_init
 409 };
 410
 411 int ldb_server_sort_init(const char *version)
 412 {
 413         LDB_MODULE_CHECK_VERSION(version);
 414         return ldb_register_module(&ldb_server_sort_module_ops);
 415 }