source4/lib/ldb/modules/sort.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Simo Sorce  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: ldb server side sort control module
  29  *
  30  *  Description: this module sorts the results of a search
  31  *
  32  *  Author: Simo Sorce
  33  */
  34
  35 #include "includes.h"
  36 #include "ldb/include/includes.h"
  37
  38 struct opaque {
  39         struct ldb_context *ldb;
  40         const struct ldb_attrib_handler *h;
  41         const char *attribute;
  42         int reverse;
  43         int result;
  44 };
  45
  46 struct sort_async_context {
  47         struct ldb_module *module;
  48         void *up_context;
  49         int (*up_callback)(struct ldb_context *, void *, struct ldb_async_result *);
  50         int timeout;
  51
  52         char *attributeName;
  53         char *orderingRule;
  54         int reverse;
  55
  56         struct ldb_request *req;
  57         struct ldb_message **msgs;
  58         char **referrals;
  59         struct ldb_control **controls;
  60         int num_msgs;
  61         int num_refs;
  62
  63         const struct ldb_attrib_handler *h;
  64         int sort_result;
  65 };
  66
  67 static struct ldb_async_handle *init_handle(void *mem_ctx, struct ldb_module *module,
  68                                             void *context,
  69                                             int (*callback)(struct ldb_context *, void *, struct ldb_async_result *),
  70                                             int timeout)
  71 {
  72         struct sort_async_context *ac;
  73         struct ldb_async_handle *h;
  74
  75         h = talloc_zero(mem_ctx, struct ldb_async_handle);
  76         if (h == NULL) {
  77                 ldb_set_errstring(module->ldb, talloc_asprintf(module, "Out of Memory"));
  78                 return NULL;
  79         }
  80
  81         h->module = module;
  82
  83         ac = talloc_zero(h, struct sort_async_context);
  84         if (ac == NULL) {
  85                 ldb_set_errstring(module->ldb, talloc_asprintf(module, "Out of Memory"));
  86                 talloc_free(h);
  87                 return NULL;
  88         }
  89
  90         h->private_data = (void *)ac;
  91
  92         ac->module = module;
  93         ac->up_context = context;
  94         ac->up_callback = callback;
  95         ac->timeout = timeout;
  96
  97         return h;
  98 }
  99
 100 static int build_response(void *mem_ctx, struct ldb_control ***ctrls, int result, const char *desc)
 101 {
 102         struct ldb_control **controls;
 103         struct ldb_sort_resp_control *resp;
 104         int i;
 105
 106         if (*ctrls) {
 107                 controls = *ctrls;
 108                 for (i = 0; controls[i]; i++);
 109                 controls = talloc_realloc(mem_ctx, controls, struct ldb_control *, i + 2);
 110         } else {
 111                 i = 0;
 112                 controls = talloc_array(mem_ctx, struct ldb_control *, 2);
 113         }
 114         if (! controls )
 115                 return LDB_ERR_OPERATIONS_ERROR;
 116
 117         *ctrls = controls;
 118
 119         controls[i+1] = NULL;
 120         controls[i] = talloc(controls, struct ldb_control);
 121         if (! controls[i] )
 122                 return LDB_ERR_OPERATIONS_ERROR;
 123
 124         controls[i]->oid = LDB_CONTROL_SORT_RESP_OID;
 125         controls[i]->critical = 0;
 126
 127         resp = talloc(controls[i], struct ldb_sort_resp_control);
 128         if (! resp )
 129                 return LDB_ERR_OPERATIONS_ERROR;
 130
 131         resp->result = result;
 132         resp->attr_desc = talloc_strdup(resp, desc);
 133
 134         if (! resp->attr_desc )
 135                 return LDB_ERR_OPERATIONS_ERROR;
 136
 137         controls[i]->data = resp;
 138
 139         return LDB_SUCCESS;
 140 }
 141
 142 static int sort_compare(struct ldb_message **msg1, struct ldb_message **msg2, void *opaque)
 143 {
 144         struct opaque *data = (struct opaque *)opaque;
 145         struct ldb_message_element *el1, *el2;
 146
 147         if (data->result != 0) {
 148                 /* an error occurred previously,
 149                  * let's exit the sorting by returning always 0 */
 150                 return 0;
 151         }
 152
 153         el1 = ldb_msg_find_element(*msg1, data->attribute);
 154         el2 = ldb_msg_find_element(*msg2, data->attribute);
 155
 156         if (!el1 || !el2) {
 157                 /* the attribute was not found return and
 158                  * set an error */
 159                 data->result = 53;
 160                 return 0;
 161         }
 162
 163         if (data->reverse)
 164                 return data->h->comparison_fn(data->ldb, data, &el2->values[0], &el1->values[0]);
 165
 166         return data->h->comparison_fn(data->ldb, data, &el1->values[0], &el2->values[0]);
 167 }
 168
 169 static int sort_compare_async(struct ldb_message **msg1, struct ldb_message **msg2, void *opaque)
 170 {
 171         struct sort_async_context *ac = talloc_get_type(opaque, struct sort_async_context);
 172         struct ldb_message_element *el1, *el2;
 173
 174         if (ac->sort_result != 0) {
 175                 /* an error occurred previously,
 176                  * let's exit the sorting by returning always 0 */
 177                 return 0;
 178         }
 179
 180         el1 = ldb_msg_find_element(*msg1, ac->attributeName);
 181         el2 = ldb_msg_find_element(*msg2, ac->attributeName);
 182
 183         if (!el1 || !el2) {
 184                 /* the attribute was not found return and
 185                  * set an error */
 186                 ac->sort_result = 53;
 187                 return 0;
 188         }
 189
 190         if (ac->reverse)
 191                 return ac->h->comparison_fn(ac->module->ldb, ac, &el2->values[0], &el1->values[0]);
 192
 193         return ac->h->comparison_fn(ac->module->ldb, ac, &el1->values[0], &el2->values[0]);
 194 }
 195
 196 /* search */
 197 static int server_sort_search(struct ldb_module *module, struct ldb_control *control, struct ldb_request *req)
 198 {
 199         struct ldb_result *sort_result = NULL;
 200         struct ldb_control **saved_controls;
 201         struct ldb_server_sort_control **sort_ctrls;
 202         int ret, result = 0;
 203         int do_sort = 1;
 204
 205         sort_ctrls = talloc_get_type(control->data, struct ldb_server_sort_control *);
 206         if (!sort_ctrls) {
 207                 return LDB_ERR_PROTOCOL_ERROR;
 208         }
 209
 210         /* FIXME: we do not support more than one attribute for sorting right now */
 211         /* FIXME: we need to check if the attribute type exist or return an error */
 212         if (sort_ctrls[1] != NULL)
 213                 do_sort = 0;
 214
 215         if (!do_sort && control->critical) {
 216                 sort_result = talloc_zero(req, struct ldb_result);
 217                 if (!sort_result)
 218                         return LDB_ERR_OPERATIONS_ERROR;
 219
 220                 req->op.search.res = sort_result;
 221
 222                 /* 53 = unwilling to perform */
 223                 if ((ret = build_response(sort_result, &sort_result->controls, 53, "sort control is not complete yet")) != LDB_SUCCESS) {
 224                         return ret;
 225                 }
 226
 227                 return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
 228         }
 229
 230         /* save it locally and remove it from the list */
 231         if (!save_controls(control, req, &saved_controls)) {
 232                 return LDB_ERR_OPERATIONS_ERROR;
 233         }
 234
 235         ret = ldb_next_request(module, req);
 236
 237         if (req->controls) talloc_free(req->controls);
 238         req->controls = saved_controls;
 239
 240         if (ret != LDB_SUCCESS) {
 241                 return ret;
 242         }
 243
 244         /* SORT HERE */
 245         if (do_sort) {
 246                 struct opaque *data;
 247
 248                 data = talloc(module, struct opaque);
 249                 if (!data)
 250                         return LDB_ERR_OPERATIONS_ERROR;
 251
 252                 data->attribute = sort_ctrls[0]->attributeName;
 253                 data->reverse = sort_ctrls[0]->reverse;
 254                 data->ldb = module->ldb;
 255                 data->h = ldb_attrib_handler(data->ldb, data->attribute);
 256                 data->result = 0;
 257                 sort_result = req->op.search.res;
 258
 259                 ldb_qsort(sort_result->msgs,
 260                           sort_result->count,
 261                           sizeof(struct ldb_message *),
 262                           data,
 263                           (ldb_qsort_cmp_fn_t)sort_compare);
 264
 265                 result = data->result;
 266
 267                 talloc_free(data);
 268         } else {
 269                 result = 53;
 270         }
 271
 272         if ((ret = build_response(sort_result, &sort_result->controls, result, "sort control is not complete yet")) != LDB_SUCCESS) {
 273                 return ret;
 274         }
 275
 276         return LDB_SUCCESS;
 277 }
 278
 279 static int server_sort_search_async_callback(struct ldb_context *ldb, void *context, struct ldb_async_result *ares)
 280 {
 281         struct sort_async_context *ac = NULL;
 282
 283         if (!context || !ares) {
 284                 ldb_set_errstring(ldb, talloc_asprintf(ldb, "NULL Context or Result in callback"));
 285                 goto error;
 286         }
 287
 288         ac = talloc_get_type(context, struct sort_async_context);
 289
 290         if (ares->type == LDB_REPLY_ENTRY) {
 291                 ac->msgs = talloc_realloc(ac, ac->msgs, struct ldb_message *, ac->num_msgs + 2);
 292                 if (! ac->msgs) {
 293                         goto error;
 294                 }
 295
 296                 ac->msgs[ac->num_msgs + 1] = NULL;
 297
 298                 ac->msgs[ac->num_msgs] = talloc_steal(ac->msgs, ares->message);
 299                 if (! ac->msgs[ac->num_msgs]) {
 300                         goto error;
 301                 }
 302
 303                 ac->num_msgs++;
 304         }
 305
 306         if (ares->type == LDB_REPLY_REFERRAL) {
 307                 ac->referrals = talloc_realloc(ac, ac->referrals, char *, ac->num_refs + 2);
 308                 if (! ac->referrals) {
 309                         goto error;
 310                 }
 311
 312                 ac->referrals[ac->num_refs + 1] = NULL;
 313
 314                 ac->referrals[ac->num_refs] = talloc_steal(ac->referrals, ares->referral);
 315                 if (! ac->referrals[ac->num_refs]) {
 316                         goto error;
 317                 }
 318
 319                 ac->num_refs++;
 320         }
 321
 322         if (ares->type == LDB_REPLY_DONE) {
 323                 if (ares->controls) {
 324                         ac->controls = talloc_steal(ac, ares->controls);
 325                         if (! ac->controls) {
 326                                 goto error;
 327                         }
 328                 }
 329         }
 330
 331         talloc_free(ares);
 332         return LDB_SUCCESS;
 333
 334 error:
 335         talloc_free(ares);
 336         return LDB_ERR_OPERATIONS_ERROR;
 337 }
 338
 339 static int server_sort_search_async(struct ldb_module *module, struct ldb_control *control, struct ldb_request *req)
 340 {
 341         struct ldb_server_sort_control **sort_ctrls;
 342         struct ldb_control **saved_controls;
 343         struct sort_async_context *ac;
 344         struct ldb_async_handle *h;
 345         int ret;
 346
 347         req->async.handle = NULL;
 348
 349         if (!req->async.callback || !req->async.context) {
 350                 ldb_set_errstring(module->ldb, talloc_asprintf(module, "Async interface called with NULL callback function or NULL context"));
 351                 return LDB_ERR_OPERATIONS_ERROR;
 352         }
 353
 354         h = init_handle(req, module, req->async.context, req->async.callback, req->async.timeout);
 355         if (!h) {
 356                 return LDB_ERR_OPERATIONS_ERROR;
 357         }
 358         ac = talloc_get_type(h->private_data, struct sort_async_context);
 359
 360         sort_ctrls = talloc_get_type(control->data, struct ldb_server_sort_control *);
 361         if (!sort_ctrls) {
 362                 return LDB_ERR_PROTOCOL_ERROR;
 363         }
 364
 365         /* FIXME: we do not support more than one attribute for sorting right now */
 366         /* FIXME: we need to check if the attribute type exist or return an error */
 367
 368         if (sort_ctrls[1] != NULL) {
 369                 if (control->critical) {
 370                         struct ldb_async_result *ares;
 371
 372                         ares = talloc_zero(req, struct ldb_async_result);
 373                         if (!ares)
 374                                 return LDB_ERR_OPERATIONS_ERROR;
 375
 376                         /* 53 = unwilling to perform */
 377                         ares->type = LDB_REPLY_DONE;
 378                         if ((ret = build_response(ares, &ares->controls, 53, "sort control is not complete yet")) != LDB_SUCCESS) {
 379                                 return ret;
 380                         }
 381
 382                         h->status = LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
 383                         h->state = LDB_ASYNC_DONE;
 384                         ret = ac->up_callback(module->ldb, ac->up_context, ares);
 385
 386                         return ret;
 387                 } else {
 388                         /* just pass the call down and don't do any sorting */
 389                         ldb_next_request(module, req);
 390                 }
 391         }
 392
 393         ac->attributeName = sort_ctrls[0]->attributeName;
 394         ac->orderingRule = sort_ctrls[0]->orderingRule;
 395         ac->reverse = sort_ctrls[0]->reverse;
 396
 397         ac->req = talloc(req, struct ldb_request);
 398
 399         ac->req->operation = req->operation;
 400         ac->req->op.search.base = req->op.search.base;
 401         ac->req->op.search.scope = req->op.search.scope;
 402         ac->req->op.search.tree = req->op.search.tree;
 403         ac->req->op.search.attrs = req->op.search.attrs;
 404         ac->req->controls = req->controls;
 405
 406         /* save it locally and remove it from the list */
 407         /* we do not need to replace them later as we
 408          * are keeping the original req intact */
 409         if (!save_controls(control, ac->req, &saved_controls)) {
 410                 return LDB_ERR_OPERATIONS_ERROR;
 411         }
 412
 413         ac->req->creds = req->creds;
 414
 415         ac->req->async.context = ac;
 416         ac->req->async.callback = server_sort_search_async_callback;
 417         ac->req->async.timeout = req->async.timeout;
 418
 419         req->async.handle = h;
 420
 421         return ldb_next_request(module, ac->req);
 422 }
 423
 424 static int server_sort(struct ldb_module *module, struct ldb_request *req)
 425 {
 426         struct ldb_control *control;
 427
 428         /* check if there's a paged request control */
 429         control = get_control_from_list(req->controls, LDB_CONTROL_SERVER_SORT_OID);
 430         if (control == NULL) {
 431                 /* not found go on */
 432                 return ldb_next_request(module, req);
 433         }
 434
 435         switch (req->operation) {
 436
 437         case LDB_REQ_SEARCH:
 438                 return server_sort_search(module, control, req);
 439
 440         case LDB_ASYNC_SEARCH:
 441                 return server_sort_search_async(module, control, req);
 442
 443         default:
 444                 return LDB_ERR_PROTOCOL_ERROR;
 445
 446         }
 447 }
 448
 449 static int server_sort_async_results(struct ldb_async_handle *handle)
 450 {
 451         struct sort_async_context *ac;
 452         struct ldb_async_result *ares;
 453         int i, ret;
 454
 455         ac = talloc_get_type(handle->private_data, struct sort_async_context);
 456
 457         ac->h = ldb_attrib_handler(ac->module->ldb, ac->attributeName);
 458         ac->sort_result = 0;
 459
 460         ldb_qsort(ac->msgs, ac->num_msgs,
 461                   sizeof(struct ldb_message *),
 462                   ac, (ldb_qsort_cmp_fn_t)sort_compare_async);
 463
 464         for (i = 0; i < ac->num_msgs; i++) {
 465                 ares = talloc_zero(ac, struct ldb_async_result);
 466                 if (!ares) {
 467                         handle->status = LDB_ERR_OPERATIONS_ERROR;
 468                         return handle->status;
 469                 }
 470
 471                 ares->type = LDB_REPLY_ENTRY;
 472                 ares->message = talloc_steal(ares, ac->msgs[i]);
 473
 474                 handle->status = ac->up_callback(ac->module->ldb, ac->up_context, ares);
 475                 if (handle->status != LDB_SUCCESS) {
 476                         return handle->status;
 477                 }
 478         }
 479
 480         for (i = 0; i < ac->num_refs; i++) {
 481                 ares = talloc_zero(ac, struct ldb_async_result);
 482                 if (!ares) {
 483                         handle->status = LDB_ERR_OPERATIONS_ERROR;
 484                         return handle->status;
 485                 }
 486
 487                 ares->type = LDB_REPLY_REFERRAL;
 488                 ares->referral = talloc_steal(ares, ac->referrals[i]);
 489
 490                 handle->status = ac->up_callback(ac->module->ldb, ac->up_context, ares);
 491                 if (handle->status != LDB_SUCCESS) {
 492                         return handle->status;
 493                 }
 494         }
 495
 496         ares = talloc_zero(ac, struct ldb_async_result);
 497         if (!ares) {
 498                 handle->status = LDB_ERR_OPERATIONS_ERROR;
 499                 return handle->status;
 500         }
 501
 502         ares->type = LDB_REPLY_DONE;
 503         ares->controls = talloc_steal(ares, ac->controls);
 504
 505         handle->status = ac->up_callback(ac->module->ldb, ac->up_context, ares);
 506         if (handle->status != LDB_SUCCESS) {
 507                 return handle->status;
 508         }
 509
 510         if ((ret = build_response(ac, &ac->controls, ac->sort_result, "sort control is not complete yet")) != LDB_SUCCESS) {
 511                 return ret;
 512         }
 513
 514         return LDB_SUCCESS;
 515 }
 516
 517 static int server_sort_async_wait(struct ldb_async_handle *handle, enum ldb_async_wait_type type)
 518 {
 519         struct sort_async_context *ac;
 520         int ret;
 521
 522         if (!handle || !handle->private_data) {
 523                 return LDB_ERR_OPERATIONS_ERROR;
 524         }
 525
 526         ac = talloc_get_type(handle->private_data, struct sort_async_context);
 527
 528         ret = ldb_async_wait(ac->req->async.handle, type);
 529
 530         if (ret != LDB_SUCCESS) {
 531                 handle->status = ret;
 532                 return ret;
 533         }
 534
 535         handle->state = ac->req->async.handle->state;
 536         handle->status = ac->req->async.handle->status;
 537
 538         if (handle->status != LDB_SUCCESS) {
 539                 return handle->status;
 540         }
 541
 542         if (handle->state == LDB_ASYNC_DONE) {
 543                 ret = server_sort_async_results(handle);
 544         }
 545
 546         return ret;
 547 }
 548
 549 static int server_sort_init(struct ldb_module *module)
 550 {
 551         struct ldb_request request;
 552         int ret;
 553
 554         request.operation = LDB_REQ_REGISTER;
 555         request.op.reg.oid = LDB_CONTROL_SERVER_SORT_OID;
 556         request.controls = NULL;
 557
 558         ret = ldb_request(module->ldb, &request);
 559         if (ret != LDB_SUCCESS) {
 560                 ldb_debug(module->ldb, LDB_DEBUG_ERROR, "server_sort: Unable to register control with rootdse!\n");
 561                 return LDB_ERR_OTHER;
 562         }
 563
 564         return ldb_next_init(module);
 565 }
 566
 567 static const struct ldb_module_ops server_sort_ops = {
 568         .name              = "server_sort",
 569         .request           = server_sort,
 570         .async_wait        = server_sort_async_wait,
 571         .init_context      = server_sort_init
 572 };
 573
 574 int ldb_sort_init(void)
 575 {
 576         return ldb_register_module(&server_sort_ops);
 577 }