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