lib/ldb/ldb_tdb/ldb_search.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Andrew Tridgell  2004
   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 search functions
  28  *
  29  *  Description: functions to search ldb+tdb databases
  30  *
  31  *  Author: Andrew Tridgell
  32  */
  33
  34 #include "ldb_tdb.h"
  35 #include "ldb_private.h"
  36 #include <tdb.h>
  37
  38 /*
  39   add one element to a message
  40 */
  41 static int msg_add_element(struct ldb_message *ret,
  42                            const struct ldb_message_element *el,
  43                            int check_duplicates)
  44 {
  45         unsigned int i;
  46         struct ldb_message_element *e2, *elnew;
  47
  48         if (check_duplicates && ldb_msg_find_element(ret, el->name)) {
  49                 /* its already there */
  50                 return 0;
  51         }
  52
  53         e2 = talloc_realloc(ret, ret->elements, struct ldb_message_element, ret->num_elements+1);
  54         if (!e2) {
  55                 return -1;
  56         }
  57         ret->elements = e2;
  58
  59         elnew = &e2[ret->num_elements];
  60
  61         elnew->name = talloc_strdup(ret->elements, el->name);
  62         if (!elnew->name) {
  63                 return -1;
  64         }
  65
  66         if (el->num_values) {
  67                 elnew->values = talloc_array(ret->elements, struct ldb_val, el->num_values);
  68                 if (!elnew->values) {
  69                         return -1;
  70                 }
  71         } else {
  72                 elnew->values = NULL;
  73         }
  74
  75         for (i=0;i<el->num_values;i++) {
  76                 elnew->values[i] = ldb_val_dup(elnew->values, &el->values[i]);
  77                 if (elnew->values[i].length != el->values[i].length) {
  78                         return -1;
  79                 }
  80         }
  81
  82         elnew->num_values = el->num_values;
  83         elnew->flags = el->flags;
  84
  85         ret->num_elements++;
  86
  87         return 0;
  88 }
  89
  90 /*
  91   add the special distinguishedName element
  92 */
  93 static int msg_add_distinguished_name(struct ldb_message *msg)
  94 {
  95         struct ldb_message_element el;
  96         struct ldb_val val;
  97         int ret;
  98
  99         el.flags = 0;
 100         el.name = "distinguishedName";
 101         el.num_values = 1;
 102         el.values = &val;
 103         el.flags = 0;
 104         val.data = (uint8_t *)ldb_dn_alloc_linearized(msg, msg->dn);
 105         val.length = strlen((char *)val.data);
 106
 107         ret = msg_add_element(msg, &el, 1);
 108         return ret;
 109 }
 110
 111 /*
 112   search the database for a single simple dn.
 113   return LDB_ERR_NO_SUCH_OBJECT on record-not-found
 114   and LDB_SUCCESS on success
 115 */
 116 static int ltdb_search_base(struct ldb_module *module, struct ldb_dn *dn)
 117 {
 118         void *data = ldb_module_get_private(module);
 119         struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
 120         TDB_DATA tdb_key;
 121         int exists;
 122
 123         if (ldb_dn_is_null(dn)) {
 124                 return LDB_ERR_NO_SUCH_OBJECT;
 125         }
 126
 127         /* form the key */
 128         tdb_key = ltdb_key(module, dn);
 129         if (!tdb_key.dptr) {
 130                 return LDB_ERR_OPERATIONS_ERROR;
 131         }
 132
 133         exists = tdb_exists(ltdb->tdb, tdb_key);
 134         talloc_free(tdb_key.dptr);
 135
 136         if (exists) {
 137                 return LDB_SUCCESS;
 138         }
 139         return LDB_ERR_NO_SUCH_OBJECT;
 140 }
 141
 142 struct ltdb_parse_data_unpack_ctx {
 143         struct ldb_message *msg;
 144         struct ldb_module *module;
 145         unsigned int unpack_flags;
 146 };
 147
 148 static int ltdb_parse_data_unpack(TDB_DATA key, TDB_DATA data,
 149                                   void *private_data)
 150 {
 151         struct ltdb_parse_data_unpack_ctx *ctx = private_data;
 152         unsigned int nb_elements_in_db;
 153         int ret;
 154         struct ldb_context *ldb = ldb_module_get_ctx(ctx->module);
 155         struct ldb_val data_parse = {
 156                 .data = data.dptr,
 157                 .length = data.dsize
 158         };
 159
 160         if (ctx->unpack_flags & LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC) {
 161                 /*
 162                  * If we got LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC
 163                  * we need at least do a memdup on the whole
 164                  * data buffer as that may change later
 165                  * and the caller needs a stable result.
 166                  */
 167                 data_parse.data = talloc_memdup(ctx->msg,
 168                                                 data.dptr,
 169                                                 data.dsize);
 170                 if (data_parse.data == NULL) {
 171                         ldb_debug(ldb, LDB_DEBUG_ERROR,
 172                                   "Unable to allocate data(%d) for %*.*s\n",
 173                                   (int)data.dsize,
 174                                   (int)key.dsize, (int)key.dsize, key.dptr);
 175                         return LDB_ERR_OPERATIONS_ERROR;
 176                 }
 177         }
 178
 179         ret = ldb_unpack_data_only_attr_list_flags(ldb, &data_parse,
 180                                                    ctx->msg,
 181                                                    NULL, 0,
 182                                                    ctx->unpack_flags,
 183                                                    &nb_elements_in_db);
 184         if (ret == -1) {
 185                 if (data_parse.data != data.dptr) {
 186                         talloc_free(data_parse.data);
 187                 }
 188
 189                 ldb_debug(ldb, LDB_DEBUG_ERROR, "Invalid data for index %*.*s\n",
 190                           (int)key.dsize, (int)key.dsize, key.dptr);
 191                 return LDB_ERR_OPERATIONS_ERROR;
 192         }
 193         return ret;
 194 }
 195
 196 /*
 197   search the database for a single simple dn, returning all attributes
 198   in a single message
 199
 200   return LDB_ERR_NO_SUCH_OBJECT on record-not-found
 201   and LDB_SUCCESS on success
 202 */
 203 int ltdb_search_dn1(struct ldb_module *module, struct ldb_dn *dn, struct ldb_message *msg,
 204                     unsigned int unpack_flags)
 205 {
 206         void *data = ldb_module_get_private(module);
 207         struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
 208         int ret;
 209         TDB_DATA tdb_key;
 210         struct ltdb_parse_data_unpack_ctx ctx = {
 211                 .msg = msg,
 212                 .module = module,
 213                 .unpack_flags = unpack_flags
 214         };
 215
 216         /* form the key */
 217         tdb_key = ltdb_key(module, dn);
 218         if (!tdb_key.dptr) {
 219                 return LDB_ERR_OPERATIONS_ERROR;
 220         }
 221
 222         memset(msg, 0, sizeof(*msg));
 223
 224         msg->num_elements = 0;
 225         msg->elements = NULL;
 226
 227         ret = tdb_parse_record(ltdb->tdb, tdb_key,
 228                                ltdb_parse_data_unpack, &ctx);
 229         talloc_free(tdb_key.dptr);
 230
 231         if (ret == -1) {
 232                 if (tdb_error(ltdb->tdb) == TDB_ERR_NOEXIST) {
 233                         return LDB_ERR_NO_SUCH_OBJECT;
 234                 }
 235                 return LDB_ERR_OPERATIONS_ERROR;
 236         } else if (ret != LDB_SUCCESS) {
 237                 return ret;
 238         }
 239
 240         if ((unpack_flags & LDB_UNPACK_DATA_FLAG_NO_DN) == 0) {
 241                 if (!msg->dn) {
 242                         msg->dn = ldb_dn_copy(msg, dn);
 243                 }
 244                 if (!msg->dn) {
 245                         return LDB_ERR_OPERATIONS_ERROR;
 246                 }
 247         }
 248
 249         return LDB_SUCCESS;
 250 }
 251
 252 /*
 253   filter the specified list of attributes from a message
 254   removing not requested attrs from the new message constructed.
 255
 256   The reason this makes a new message is that the old one may not be
 257   individually allocated, which is what our callers expect.
 258
 259  */
 260 int ltdb_filter_attrs(TALLOC_CTX *mem_ctx,
 261                       const struct ldb_message *msg, const char * const *attrs,
 262                       struct ldb_message **filtered_msg)
 263 {
 264         unsigned int i;
 265         bool keep_all = false;
 266         bool add_dn = false;
 267         uint32_t num_elements;
 268         uint32_t elements_size;
 269         struct ldb_message *msg2;
 270
 271         msg2 = ldb_msg_new(mem_ctx);
 272         if (msg2 == NULL) {
 273                 goto failed;
 274         }
 275
 276         msg2->dn = ldb_dn_copy(msg2, msg->dn);
 277         if (msg2->dn == NULL) {
 278                 goto failed;
 279         }
 280
 281         if (attrs) {
 282                 /* check for special attrs */
 283                 for (i = 0; attrs[i]; i++) {
 284                         int cmp = strcmp(attrs[i], "*");
 285                         if (cmp == 0) {
 286                                 keep_all = true;
 287                                 break;
 288                         }
 289                         cmp = ldb_attr_cmp(attrs[i], "distinguishedName");
 290                         if (cmp == 0) {
 291                                 add_dn = true;
 292                         }
 293                 }
 294         } else {
 295                 keep_all = true;
 296         }
 297
 298         if (keep_all) {
 299                 add_dn = true;
 300                 elements_size = msg->num_elements + 1;
 301
 302         /* Shortcuts for the simple cases */
 303         } else if (add_dn && i == 1) {
 304                 if (msg_add_distinguished_name(msg2) != 0) {
 305                         return -1;
 306                 }
 307                 *filtered_msg = msg2;
 308                 return 0;
 309         } else if (i == 0) {
 310                 *filtered_msg = msg2;
 311                 return 0;
 312
 313         /* Otherwise we are copying at most as many element as we have attributes */
 314         } else {
 315                 elements_size = i;
 316         }
 317
 318         msg2->elements = talloc_array(msg2, struct ldb_message_element,
 319                                       elements_size);
 320         if (msg2->elements == NULL) goto failed;
 321
 322         num_elements = 0;
 323
 324         for (i = 0; i < msg->num_elements; i++) {
 325                 struct ldb_message_element *el = &msg->elements[i];
 326                 struct ldb_message_element *el2 = &msg2->elements[num_elements];
 327                 unsigned int j;
 328
 329                 if (keep_all == false) {
 330                         bool found = false;
 331                         for (j = 0; attrs[j]; j++) {
 332                                 int cmp = ldb_attr_cmp(el->name, attrs[j]);
 333                                 if (cmp == 0) {
 334                                         found = true;
 335                                         break;
 336                                 }
 337                         }
 338                         if (found == false) {
 339                                 continue;
 340                         }
 341                 }
 342                 *el2 = *el;
 343                 el2->name = talloc_strdup(msg2->elements, el->name);
 344                 if (el2->name == NULL) {
 345                         goto failed;
 346                 }
 347                 el2->values = talloc_array(msg2->elements, struct ldb_val, el->num_values);
 348                 if (el2->values == NULL) {
 349                         goto failed;
 350                 }
 351                 for (j=0;j<el->num_values;j++) {
 352                         el2->values[j] = ldb_val_dup(el2->values, &el->values[j]);
 353                         if (el2->values[j].data == NULL && el->values[j].length != 0) {
 354                                 goto failed;
 355                         }
 356                 }
 357                 num_elements++;
 358
 359                 /* Pidginhole principle: we can't have more elements
 360                  * than the number of attributes if they are unique in
 361                  * the DB */
 362                 if (num_elements > elements_size) {
 363                         goto failed;
 364                 }
 365         }
 366
 367         msg2->num_elements = num_elements;
 368
 369         if (add_dn) {
 370                 if (msg_add_distinguished_name(msg2) != 0) {
 371                         return -1;
 372                 }
 373         }
 374
 375         if (msg2->num_elements > 0) {
 376                 msg2->elements = talloc_realloc(msg2, msg2->elements,
 377                                                 struct ldb_message_element,
 378                                                 msg2->num_elements);
 379                 if (msg2->elements == NULL) {
 380                         return -1;
 381                 }
 382         } else {
 383                 talloc_free(msg2->elements);
 384                 msg2->elements = NULL;
 385         }
 386
 387         *filtered_msg = msg2;
 388
 389         return 0;
 390 failed:
 391         return -1;
 392 }
 393
 394 /*
 395   search function for a non-indexed search
 396  */
 397 static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
 398 {
 399         struct ldb_context *ldb;
 400         struct ltdb_context *ac;
 401         struct ldb_message *msg, *filtered_msg;
 402         const struct ldb_val val = {
 403                 .data = data.dptr,
 404                 .length = data.dsize,
 405         };
 406         int ret;
 407         bool matched;
 408         unsigned int nb_elements_in_db;
 409
 410         ac = talloc_get_type(state, struct ltdb_context);
 411         ldb = ldb_module_get_ctx(ac->module);
 412
 413         if (ltdb_key_is_record(key) == false) {
 414                 return 0;
 415         }
 416
 417         msg = ldb_msg_new(ac);
 418         if (!msg) {
 419                 ac->error = LDB_ERR_OPERATIONS_ERROR;
 420                 return -1;
 421         }
 422
 423         /* unpack the record */
 424         ret = ldb_unpack_data_only_attr_list_flags(ldb, &val,
 425                                                    msg,
 426                                                    NULL, 0,
 427                                                    LDB_UNPACK_DATA_FLAG_NO_DATA_ALLOC|
 428                                                    LDB_UNPACK_DATA_FLAG_NO_VALUES_ALLOC,
 429                                                    &nb_elements_in_db);
 430         if (ret == -1) {
 431                 talloc_free(msg);
 432                 ac->error = LDB_ERR_OPERATIONS_ERROR;
 433                 return -1;
 434         }
 435
 436         if (!msg->dn) {
 437                 msg->dn = ldb_dn_new(msg, ldb,
 438                                      (char *)key.dptr + 3);
 439                 if (msg->dn == NULL) {
 440                         talloc_free(msg);
 441                         ac->error = LDB_ERR_OPERATIONS_ERROR;
 442                         return -1;
 443                 }
 444         }
 445
 446         /* see if it matches the given expression */
 447         ret = ldb_match_msg_error(ldb, msg,
 448                                   ac->tree, ac->base, ac->scope, &matched);
 449         if (ret != LDB_SUCCESS) {
 450                 talloc_free(msg);
 451                 ac->error = LDB_ERR_OPERATIONS_ERROR;
 452                 return -1;
 453         }
 454         if (!matched) {
 455                 talloc_free(msg);
 456                 return 0;
 457         }
 458
 459         /* filter the attributes that the user wants */
 460         ret = ltdb_filter_attrs(ac, msg, ac->attrs, &filtered_msg);
 461         talloc_free(msg);
 462
 463         if (ret == -1) {
 464                 ac->error = LDB_ERR_OPERATIONS_ERROR;
 465                 return -1;
 466         }
 467
 468         ret = ldb_module_send_entry(ac->req, filtered_msg, NULL);
 469         if (ret != LDB_SUCCESS) {
 470                 ac->request_terminated = true;
 471                 /* the callback failed, abort the operation */
 472                 ac->error = LDB_ERR_OPERATIONS_ERROR;
 473                 return -1;
 474         }
 475
 476         return 0;
 477 }
 478
 479
 480 /*
 481   search the database with a LDAP-like expression.
 482   this is the "full search" non-indexed variant
 483 */
 484 static int ltdb_search_full(struct ltdb_context *ctx)
 485 {
 486         void *data = ldb_module_get_private(ctx->module);
 487         struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
 488         int ret;
 489
 490         ctx->error = LDB_SUCCESS;
 491         if (ltdb->in_transaction != 0) {
 492                 ret = tdb_traverse(ltdb->tdb, search_func, ctx);
 493         } else {
 494                 ret = tdb_traverse_read(ltdb->tdb, search_func, ctx);
 495         }
 496
 497         if (ret < 0) {
 498                 return LDB_ERR_OPERATIONS_ERROR;
 499         }
 500
 501         return ctx->error;
 502 }
 503
 504 /*
 505   search the database with a LDAP-like expression.
 506   choses a search method
 507 */
 508 int ltdb_search(struct ltdb_context *ctx)
 509 {
 510         struct ldb_context *ldb;
 511         struct ldb_module *module = ctx->module;
 512         struct ldb_request *req = ctx->req;
 513         void *data = ldb_module_get_private(module);
 514         struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
 515         int ret;
 516
 517         ldb = ldb_module_get_ctx(module);
 518
 519         ldb_request_set_state(req, LDB_ASYNC_PENDING);
 520
 521         if (ltdb_lock_read(module) != 0) {
 522                 return LDB_ERR_OPERATIONS_ERROR;
 523         }
 524
 525         if (ltdb_cache_load(module) != 0) {
 526                 ltdb_unlock_read(module);
 527                 return LDB_ERR_OPERATIONS_ERROR;
 528         }
 529
 530         if (req->op.search.tree == NULL) {
 531                 ltdb_unlock_read(module);
 532                 return LDB_ERR_OPERATIONS_ERROR;
 533         }
 534
 535         if ((req->op.search.base == NULL) || (ldb_dn_is_null(req->op.search.base) == true)) {
 536
 537                 /* Check what we should do with a NULL dn */
 538                 switch (req->op.search.scope) {
 539                 case LDB_SCOPE_BASE:
 540                         ldb_asprintf_errstring(ldb,
 541                                                "NULL Base DN invalid for a base search");
 542                         ret = LDB_ERR_INVALID_DN_SYNTAX;
 543                         break;
 544                 case LDB_SCOPE_ONELEVEL:
 545                         ldb_asprintf_errstring(ldb,
 546                                                "NULL Base DN invalid for a one-level search");
 547                         ret = LDB_ERR_INVALID_DN_SYNTAX;
 548                         break;
 549                 case LDB_SCOPE_SUBTREE:
 550                 default:
 551                         /* We accept subtree searches from a NULL base DN, ie over the whole DB */
 552                         ret = LDB_SUCCESS;
 553                 }
 554         } else if (ldb_dn_is_valid(req->op.search.base) == false) {
 555
 556                 /* We don't want invalid base DNs here */
 557                 ldb_asprintf_errstring(ldb,
 558                                        "Invalid Base DN: %s",
 559                                        ldb_dn_get_linearized(req->op.search.base));
 560                 ret = LDB_ERR_INVALID_DN_SYNTAX;
 561
 562         } else if (ltdb->check_base) {
 563                 /* This database has been marked as 'checkBaseOnSearch', so do a spot check of the base dn */
 564                 ret = ltdb_search_base(module, req->op.search.base);
 565
 566                 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
 567                         ldb_asprintf_errstring(ldb,
 568                                                "No such Base DN: %s",
 569                                                ldb_dn_get_linearized(req->op.search.base));
 570                 }
 571
 572         } else {
 573                 /* If we are not checking the base DN life is easy */
 574                 ret = LDB_SUCCESS;
 575         }
 576
 577         ctx->tree = req->op.search.tree;
 578         ctx->scope = req->op.search.scope;
 579         ctx->base = req->op.search.base;
 580         ctx->attrs = req->op.search.attrs;
 581
 582         if (ret == LDB_SUCCESS) {
 583                 uint32_t match_count = 0;
 584
 585                 ret = ltdb_search_indexed(ctx, &match_count);
 586                 if (ret == LDB_ERR_NO_SUCH_OBJECT) {
 587                         /* Not in the index, therefore OK! */
 588                         ret = LDB_SUCCESS;
 589
 590                 }
 591                 /* Check if we got just a normal error.
 592                  * In that case proceed to a full search unless we got a
 593                  * callback error */
 594                 if ( ! ctx->request_terminated && ret != LDB_SUCCESS) {
 595                         /* Not indexed, so we need to do a full scan */
 596                         if (ltdb->warn_unindexed) {
 597                                 /* useful for debugging when slow performance
 598                                  * is caused by unindexed searches */
 599                                 char *expression = ldb_filter_from_tree(ctx, ctx->tree);
 600                                 ldb_debug(ldb, LDB_DEBUG_ERROR, "ldb FULL SEARCH: %s SCOPE: %s DN: %s",
 601                                                         expression,
 602                                                         req->op.search.scope==LDB_SCOPE_BASE?"base":
 603                                                         req->op.search.scope==LDB_SCOPE_ONELEVEL?"one":
 604                                                         req->op.search.scope==LDB_SCOPE_SUBTREE?"sub":"UNKNOWN",
 605                                                         ldb_dn_get_linearized(req->op.search.base));
 606
 607                                 talloc_free(expression);
 608                         }
 609                         if (match_count != 0) {
 610                                 /* the indexing code gave an error
 611                                  * after having returned at least one
 612                                  * entry. This means the indexes are
 613                                  * corrupt or a database record is
 614                                  * corrupt. We cannot continue with a
 615                                  * full search or we may return
 616                                  * duplicate entries
 617                                  */
 618                                 ltdb_unlock_read(module);
 619                                 return LDB_ERR_OPERATIONS_ERROR;
 620                         }
 621                         ret = ltdb_search_full(ctx);
 622                         if (ret != LDB_SUCCESS) {
 623                                 ldb_set_errstring(ldb, "Indexed and full searches both failed!\n");
 624                         }
 625                 }
 626         }
 627
 628         ltdb_unlock_read(module);
 629
 630         return ret;
 631 }
 632