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