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