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