git.sur5r.net Git - openldap/blob - servers/slapd/back-ldbm/search.c

   1 /* search.c - ldbm backend search function */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 1998-2005 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include "portable.h"
  18
  19 #include <stdio.h>
  20
  21 #include <ac/string.h>
  22 #include <ac/socket.h>
  23
  24 #include "slap.h"
  25 #include "back-ldbm.h"
  26 #include "proto-back-ldbm.h"
  27
  28 static ID_BLOCK *base_candidate(
  29         Backend *be, Entry *e );
  30
  31 static ID_BLOCK *search_candidates(
  32         Operation *op, Entry *e, Filter *filter,
  33         int scope, int deref, int manageDSAit );
  34
  35
  36 int
  37 ldbm_back_search(
  38     Operation   *op,
  39     SlapReply   *rs )
  40 {
  41         struct ldbminfo *li = (struct ldbminfo *) op->o_bd->be_private;
  42         int             rc;
  43         time_t          stoptime;
  44         ID_BLOCK                *candidates;
  45         ID              id, cursor;
  46         Entry           *e;
  47         Entry   *matched = NULL;
  48         struct berval   realbase = BER_BVNULL;
  49         int             manageDSAit = get_manageDSAit( op );
  50
  51         Debug(LDAP_DEBUG_TRACE, "=> ldbm_back_search\n", 0, 0, 0);
  52
  53         /* grab giant lock for reading */
  54         ldap_pvt_thread_rdwr_rlock(&li->li_giant_rwlock);
  55
  56         if ( op->o_req_ndn.bv_len == 0 ) {
  57                 /* DIT root special case */
  58                 e = (Entry *) &slap_entry_root;
  59
  60                 /* need normalized dn below */
  61                 ber_dupbv( &realbase, &e->e_nname );
  62
  63                 candidates = search_candidates( op, e, op->ors_filter,
  64                         op->ors_scope, op->ors_deref,
  65                         manageDSAit || get_domainScope(op) );
  66
  67                 goto searchit;
  68
  69         } else if ( op->ors_deref & LDAP_DEREF_FINDING ) {
  70                 /* deref dn and get entry with reader lock */
  71                 e = deref_dn_r( op->o_bd, &op->o_req_ndn,
  72                         &rs->sr_err, &matched, &rs->sr_text );
  73
  74                 if( rs->sr_err == LDAP_NO_SUCH_OBJECT ) rs->sr_err = LDAP_REFERRAL;
  75
  76         } else {
  77                 /* get entry with reader lock */
  78                 e = dn2entry_r( op->o_bd, &op->o_req_ndn, &matched );
  79                 rs->sr_err = e != NULL ? LDAP_SUCCESS : LDAP_REFERRAL;
  80                 rs->sr_text = NULL;
  81         }
  82
  83         if ( e == NULL ) {
  84                 struct berval matched_dn = BER_BVNULL;
  85
  86                 if ( matched != NULL ) {
  87                         BerVarray erefs = NULL;
  88
  89 #ifdef SLAP_ACL_HONOR_DISCLOSE
  90                         if ( ! access_allowed( op, matched,
  91                                                 slap_schema.si_ad_entry,
  92                                                 NULL, ACL_DISCLOSE, NULL ) )
  93                         {
  94                                 rs->sr_err = LDAP_NO_SUCH_OBJECT;
  95
  96                         } else
  97 #endif /* SLAP_ACL_HONOR_DISCLOSE */
  98                         {
  99                                 ber_dupbv( &matched_dn, &matched->e_name );
 100
 101                                 erefs = is_entry_referral( matched )
 102                                         ? get_entry_referrals( op, matched )
 103                                         : NULL;
 104                         }
 105
 106                         cache_return_entry_r( &li->li_cache, matched );
 107
 108                         if ( erefs ) {
 109                                 rs->sr_ref = referral_rewrite( erefs, &matched_dn,
 110                                         &op->o_req_dn, op->ors_scope );
 111
 112                                 ber_bvarray_free( erefs );
 113                         }
 114
 115                 } else {
 116                         rs->sr_ref = referral_rewrite( default_referral,
 117                                 NULL, &op->o_req_dn, op->ors_scope );
 118                 }
 119
 120                 ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
 121
 122                 rs->sr_matched = matched_dn.bv_val;
 123                 send_ldap_result( op, rs );
 124
 125                 ber_bvarray_free( rs->sr_ref );
 126                 ber_memfree( matched_dn.bv_val );
 127                 rs->sr_ref = NULL;
 128                 rs->sr_matched = NULL;
 129                 return rs->sr_err;
 130         }
 131
 132 #ifdef SLAP_ACL_HONOR_DISCLOSE
 133         if ( ! access_allowed( op, e, slap_schema.si_ad_entry,
 134                                 NULL, ACL_DISCLOSE, NULL ) )
 135         {
 136                 rs->sr_err = LDAP_NO_SUCH_OBJECT;
 137
 138                 cache_return_entry_r( &li->li_cache, e );
 139                 ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
 140
 141                 send_ldap_result( op, rs );
 142                 return rs->sr_err;
 143         }
 144 #endif /* SLAP_ACL_HONOR_DISCLOSE */
 145
 146         if ( !manageDSAit && is_entry_referral( e ) ) {
 147                 /* entry is a referral, don't allow add */
 148                 struct berval   matched_dn = BER_BVNULL;
 149                 BerVarray       erefs = NULL;
 150
 151                 rs->sr_ref = NULL;
 152                 rs->sr_err = LDAP_OTHER;
 153                 rs->sr_text = "bad referral object";
 154
 155                 ber_dupbv( &matched_dn, &e->e_name );
 156                 erefs = get_entry_referrals( op, e );
 157
 158                 cache_return_entry_r( &li->li_cache, e );
 159                 ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
 160
 161                 Debug( LDAP_DEBUG_TRACE,
 162                         "ldbm_search: entry is referral\n",
 163                         0, 0, 0 );
 164
 165                 if ( erefs ) {
 166                         rs->sr_ref = referral_rewrite( erefs, &matched_dn,
 167                                 &op->o_req_dn, op->ors_scope );
 168
 169                         ber_bvarray_free( erefs );
 170
 171                         if ( rs->sr_ref ) {
 172                                 rs->sr_err = LDAP_REFERRAL;
 173                                 rs->sr_text = NULL;
 174                         }
 175                 }
 176
 177                 rs->sr_matched = matched_dn.bv_val;
 178                 send_ldap_result( op, rs );
 179                 ber_bvarray_free( rs->sr_ref );
 180                 ber_memfree( matched_dn.bv_val );
 181                 rs->sr_ref = NULL;
 182                 rs->sr_matched = NULL;
 183                 return rs->sr_err;
 184         }
 185
 186         if ( is_entry_alias( e ) ) {
 187                 /* don't deref */
 188                 op->ors_deref = LDAP_DEREF_NEVER;
 189         }
 190
 191         if ( op->ors_scope == LDAP_SCOPE_BASE ) {
 192                 candidates = base_candidate( op->o_bd, e );
 193
 194         } else {
 195                 candidates = search_candidates( op, e, op->ors_filter,
 196                     op->ors_scope, op->ors_deref, manageDSAit );
 197         }
 198
 199         /* need normalized dn below */
 200         ber_dupbv( &realbase, &e->e_nname );
 201
 202         cache_return_entry_r( &li->li_cache, e );
 203
 204 searchit:
 205         if ( candidates == NULL ) {
 206                 /* no candidates */
 207                 Debug( LDAP_DEBUG_TRACE, "ldbm_search: no candidates\n",
 208                         0, 0, 0 );
 209
 210                 rs->sr_err = LDAP_SUCCESS;
 211                 send_ldap_result( op, rs );
 212
 213                 rc = LDAP_SUCCESS;
 214                 goto done;
 215         }
 216
 217         /* if candidates exceed to-be-checked entries, abort */
 218         if ( op->ors_limit      /* isroot == FALSE */
 219                         && op->ors_limit->lms_s_unchecked != -1
 220                         && ID_BLOCK_NIDS( candidates ) > (unsigned) op->ors_limit->lms_s_unchecked )
 221         {
 222                 send_ldap_error( op, rs, LDAP_ADMINLIMIT_EXCEEDED, NULL );
 223                 rc = LDAP_SUCCESS;
 224                 goto done;
 225         }
 226
 227         /* compute it anyway; root does not use it */
 228         stoptime = op->o_time + op->ors_tlimit;
 229         rs->sr_attrs = op->ors_attrs;
 230
 231         for ( id = idl_firstid( candidates, &cursor ); id != NOID;
 232             id = idl_nextid( candidates, &cursor ) )
 233         {
 234                 int scopeok = 0;
 235                 int result = 0;
 236
 237                 /* check for abandon */
 238                 if ( op->o_abandon ) {
 239                         rc = SLAPD_ABANDON;
 240                         goto done;
 241                 }
 242
 243                 /* check time limit */
 244                 if ( op->ors_tlimit != SLAP_NO_LIMIT
 245                                 && slap_get_time() > stoptime )
 246                 {
 247                         rs->sr_err = LDAP_TIMELIMIT_EXCEEDED;
 248                         send_ldap_result( op, rs );
 249                         rc = LDAP_SUCCESS;
 250                         goto done;
 251                 }
 252
 253                 /* get the entry with reader lock */
 254                 e = id2entry_r( op->o_bd, id );
 255
 256                 if ( e == NULL ) {
 257                         Debug( LDAP_DEBUG_TRACE,
 258                                 "ldbm_search: candidate %ld not found\n",
 259                                 id, 0, 0 );
 260
 261                         goto loop_continue;
 262                 }
 263
 264                 rs->sr_entry = e;
 265
 266 #ifdef LDBM_SUBENTRIES
 267                 if ( is_entry_subentry( e ) ) {
 268                         if( op->ors_scope != LDAP_SCOPE_BASE ) {
 269                                 if(!get_subentries_visibility( op )) {
 270                                         /* only subentries are visible */
 271                                         goto loop_continue;
 272                                 }
 273                         } else if ( get_subentries( op ) &&
 274                                 !get_subentries_visibility( op ))
 275                         {
 276                                 /* only subentries are visible */
 277                                 goto loop_continue;
 278                         }
 279                 } else if ( get_subentries_visibility( op )) {
 280                         /* only subentries are visible */
 281                         goto loop_continue;
 282                 }
 283 #endif
 284
 285                 if ( op->ors_deref & LDAP_DEREF_SEARCHING &&
 286                         is_entry_alias( e ) )
 287                 {
 288                         Entry *matched;
 289                         int err;
 290                         const char *text;
 291
 292                         e = deref_entry_r( op->o_bd, e, &err, &matched, &text );
 293
 294                         if( e == NULL ) {
 295                                 e = matched;
 296                                 goto loop_continue;
 297                         }
 298
 299                         if( e->e_id == id ) {
 300                                 /* circular loop */
 301                                 goto loop_continue;
 302                         }
 303
 304                         /* need to skip alias which deref into scope */
 305                         if( op->ors_scope == LDAP_SCOPE_ONELEVEL ) {
 306                                 struct berval pdn;
 307                                 dnParent( &e->e_nname, &pdn );
 308                                 if ( ber_bvcmp( &pdn, &realbase ) ) {
 309                                         goto loop_continue;
 310                                 }
 311
 312                         } else if ( dnIsSuffix( &e->e_nname, &realbase ) ) {
 313                                 /* alias is within scope */
 314                                 Debug( LDAP_DEBUG_TRACE,
 315                                         "ldbm_search: alias \"%s\" in subtree\n",
 316                                         e->e_dn, 0, 0 );
 317
 318                                 goto loop_continue;
 319                         }
 320
 321                         rs->sr_entry = e;
 322
 323                         scopeok = 1;
 324                 }
 325
 326                 /*
 327                  * If it's a referral, add it to the list of referrals.
 328                  * Only do this for non-base searches, and don't check
 329                  * the filter explicitly here since it's only a candidate
 330                  * anyway.
 331                  */
 332                 if ( !manageDSAit && op->ors_scope != LDAP_SCOPE_BASE &&
 333                         is_entry_referral( e ) )
 334                 {
 335                         struct berval   dn;
 336
 337                         /* check scope */
 338                         if ( !scopeok && op->ors_scope == LDAP_SCOPE_ONELEVEL ) {
 339                                 if ( !be_issuffix( op->o_bd, &e->e_nname ) ) {
 340                                         dnParent( &e->e_nname, &dn );
 341                                         scopeok = dn_match( &dn, &realbase );
 342                                 } else {
 343                                         scopeok = (realbase.bv_len == 0);
 344                                 }
 345
 346                         } else if ( !scopeok
 347                                 && op->ors_scope == LDAP_SCOPE_SUBTREE )
 348                         {
 349                                 scopeok = dnIsSuffix( &e->e_nname, &realbase );
 350
 351 #ifdef LDAP_SCOPE_SUBORDINATE
 352                         } else if ( !scopeok
 353                                 && op->ors_scope == LDAP_SCOPE_SUBORDINATE )
 354                         {
 355                                 scopeok = !dn_match( &e->e_nname, &realbase )
 356                                         && dnIsSuffix( &e->e_nname, &realbase );
 357 #endif
 358
 359                         } else {
 360                                 scopeok = 1;
 361                         }
 362
 363                         if( scopeok ) {
 364                                 BerVarray erefs = get_entry_referrals( op, e );
 365                                 rs->sr_ref = referral_rewrite( erefs,
 366                                         &e->e_name, NULL,
 367                                         op->ors_scope == LDAP_SCOPE_ONELEVEL
 368                                                 ? LDAP_SCOPE_BASE
 369                                                 : LDAP_SCOPE_SUBTREE );
 370
 371                                 ber_bvarray_free( erefs );
 372
 373                                 send_search_reference( op, rs );
 374
 375                                 ber_bvarray_free( rs->sr_ref );
 376                                 rs->sr_ref = NULL;
 377
 378                         } else {
 379                                 Debug( LDAP_DEBUG_TRACE,
 380                                         "ldbm_search: candidate referral %ld scope not okay\n",
 381                                         id, 0, 0 );
 382                         }
 383
 384                         goto loop_continue;
 385                 }
 386
 387                 if ( !manageDSAit && is_entry_glue( e )) {
 388                         goto loop_continue;
 389                 }
 390
 391                 /* if it matches the filter and scope, send it */
 392                 result = test_filter( op, e, op->ors_filter );
 393
 394                 if ( result == LDAP_COMPARE_TRUE ) {
 395                         struct berval   dn;
 396
 397                         /* check scope */
 398                         if ( !scopeok && op->ors_scope == LDAP_SCOPE_ONELEVEL ) {
 399                                 if ( !be_issuffix( op->o_bd, &e->e_nname ) ) {
 400                                         dnParent( &e->e_nname, &dn );
 401                                         scopeok = dn_match( &dn, &realbase );
 402                                 } else {
 403                                         scopeok = (realbase.bv_len == 0);
 404                                 }
 405
 406                         } else if ( !scopeok &&
 407                                 op->ors_scope == LDAP_SCOPE_SUBTREE )
 408                         {
 409                                 scopeok = dnIsSuffix( &e->e_nname, &realbase );
 410
 411 #ifdef LDAP_SCOPE_SUBORDINATE
 412                         } else if ( !scopeok &&
 413                                 op->ors_scope == LDAP_SCOPE_SUBORDINATE )
 414                         {
 415                                 scopeok = !dn_match( &e->e_nname, &realbase )
 416                                         && dnIsSuffix( &e->e_nname, &realbase );
 417 #endif
 418
 419                         } else {
 420                                 scopeok = 1;
 421                         }
 422
 423                         if ( scopeok ) {
 424                                 /* check size limit */
 425                                 if ( --op->ors_slimit == -1 ) {
 426                                         cache_return_entry_r( &li->li_cache, e );
 427                                         rs->sr_err = LDAP_SIZELIMIT_EXCEEDED;
 428                                         rs->sr_entry = NULL;
 429                                         send_ldap_result( op, rs );
 430                                         rc = LDAP_SUCCESS;
 431                                         goto done;
 432                                 }
 433
 434                                 if (e) {
 435                                         rs->sr_flags = 0;
 436                                         result = send_search_entry( op, rs );
 437
 438                                         switch (result) {
 439                                         case 0:         /* entry sent ok */
 440                                                 break;
 441                                         case 1:         /* entry not sent */
 442                                                 break;
 443                                         case -1:        /* connection closed */
 444                                                 cache_return_entry_r( &li->li_cache, e );
 445                                                 rc = LDAP_SUCCESS;
 446                                                 goto done;
 447                                         }
 448                                 }
 449
 450                         } else {
 451                                 Debug( LDAP_DEBUG_TRACE,
 452                                         "ldbm_search: candidate entry %ld scope not okay\n",
 453                                         id, 0, 0 );
 454                         }
 455
 456                 } else {
 457                         Debug( LDAP_DEBUG_TRACE,
 458                                 "ldbm_search: candidate entry %ld does not match filter\n",
 459                                 id, 0, 0 );
 460                 }
 461
 462 loop_continue:
 463                 if( e != NULL ) {
 464                         /* free reader lock */
 465                         cache_return_entry_r( &li->li_cache, e );
 466                 }
 467
 468                 ldap_pvt_thread_yield();
 469         }
 470
 471         rs->sr_err = rs->sr_v2ref ? LDAP_REFERRAL : LDAP_SUCCESS;
 472         rs->sr_ref = rs->sr_v2ref;
 473         send_ldap_result( op, rs );
 474
 475         rc = LDAP_SUCCESS;
 476
 477 done:
 478         ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
 479
 480         if( candidates != NULL )
 481                 idl_free( candidates );
 482
 483         if( rs->sr_v2ref ) ber_bvarray_free( rs->sr_v2ref );
 484         if( realbase.bv_val ) free( realbase.bv_val );
 485
 486         return rc;
 487 }
 488
 489 static ID_BLOCK *
 490 base_candidate(
 491     Backend     *be,
 492         Entry   *e )
 493 {
 494         ID_BLOCK                *idl;
 495
 496         Debug(LDAP_DEBUG_TRACE, "base_candidates: base: \"%s\"\n",
 497                 e->e_dn, 0, 0);
 498
 499
 500         idl = idl_alloc( 1 );
 501         idl_insert( &idl, e->e_id, 1 );
 502
 503         return( idl );
 504 }
 505
 506 static ID_BLOCK *
 507 search_candidates(
 508     Operation   *op,
 509     Entry       *e,
 510     Filter      *filter,
 511     int         scope,
 512         int             deref,
 513         int             manageDSAit )
 514 {
 515         ID_BLOCK                *candidates;
 516         Filter          f, fand, rf, af, xf;
 517     AttributeAssertion aa_ref, aa_alias;
 518         struct berval bv_ref = { sizeof("referral")-1, "referral" };
 519         struct berval bv_alias = { sizeof("alias")-1, "alias" };
 520 #ifdef LDBM_SUBENTRIES
 521         Filter  sf;
 522         AttributeAssertion aa_subentry;
 523 #endif
 524
 525         Debug(LDAP_DEBUG_TRACE,
 526                 "search_candidates: base=\"%s\" s=%d d=%d\n",
 527                 e->e_ndn, scope, deref );
 528
 529
 530         xf.f_or = filter;
 531         xf.f_choice = LDAP_FILTER_OR;
 532         xf.f_next = NULL;
 533
 534         if( !manageDSAit ) {
 535                 /* match referrals */
 536                 rf.f_choice = LDAP_FILTER_EQUALITY;
 537                 rf.f_ava = &aa_ref;
 538                 rf.f_av_desc = slap_schema.si_ad_objectClass;
 539                 rf.f_av_value = bv_ref;
 540                 rf.f_next = xf.f_or;
 541                 xf.f_or = &rf;
 542         }
 543
 544         if( deref & LDAP_DEREF_SEARCHING ) {
 545                 /* match aliases */
 546                 af.f_choice = LDAP_FILTER_EQUALITY;
 547                 af.f_ava = &aa_alias;
 548                 af.f_av_desc = slap_schema.si_ad_objectClass;
 549                 af.f_av_value = bv_alias;
 550                 af.f_next = xf.f_or;
 551                 xf.f_or = &af;
 552         }
 553
 554         f.f_next = NULL;
 555         f.f_choice = LDAP_FILTER_AND;
 556         f.f_and = &fand;
 557         fand.f_choice = scope == LDAP_SCOPE_ONELEVEL
 558                 ? SLAPD_FILTER_DN_ONE
 559                 : SLAPD_FILTER_DN_SUBTREE;
 560         fand.f_dn = &e->e_nname;
 561         fand.f_next = xf.f_or == filter ? filter : &xf ;
 562
 563 #ifdef LDBM_SUBENTRIES
 564         if ( get_subentries_visibility( op )) {
 565                 struct berval bv_subentry = { sizeof("SUBENTRY")-1, "SUBENTRY" };
 566                 sf.f_choice = LDAP_FILTER_EQUALITY;
 567                 sf.f_ava = &aa_subentry;
 568                 sf.f_av_desc = slap_schema.si_ad_objectClass;
 569                 sf.f_av_value = bv_subentry;
 570                 sf.f_next = fand.f_next;
 571                 fand.f_next = &sf;
 572         }
 573 #endif
 574
 575         candidates = filter_candidates( op, &f );
 576         return( candidates );
 577 }