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

   1 /* search.c - ldbm backend search function */
   2 /* $OpenLDAP$ */
   3 /*
   4  * Copyright 1998-2002 The OpenLDAP Foundation, All Rights Reserved.
   5  * COPYING RESTRICTIONS APPLY, see COPYRIGHT file
   6  */
   7
   8 #include "portable.h"
   9
  10 #include <stdio.h>
  11
  12 #include <ac/string.h>
  13 #include <ac/socket.h>
  14
  15 #include "slap.h"
  16 #include "back-ldbm.h"
  17 #include "proto-back-ldbm.h"
  18
  19 static ID_BLOCK *base_candidate(
  20         Backend *be, Entry *e );
  21
  22 static ID_BLOCK *search_candidates(
  23         Backend *be, Entry *e, Filter *filter,
  24         int scope, int deref, int manageDSAit );
  25
  26
  27 int
  28 ldbm_back_search(
  29     Backend     *be,
  30     Connection  *conn,
  31     Operation   *op,
  32     struct berval       *base,
  33     struct berval       *nbase,
  34     int         scope,
  35     int         deref,
  36     int         slimit,
  37     int         tlimit,
  38     Filter      *filter,
  39     struct berval       *filterstr,
  40     AttributeName       *attrs,
  41     int         attrsonly )
  42 {
  43         struct ldbminfo *li = (struct ldbminfo *) be->be_private;
  44         int             rc, err;
  45         const char *text = NULL;
  46         time_t          stoptime;
  47         ID_BLOCK                *candidates;
  48         ID              id, cursor;
  49         Entry           *e;
  50         BerVarray               v2refs = NULL;
  51         Entry   *matched = NULL;
  52         struct berval   realbase = { 0, NULL };
  53         int             nentries = 0;
  54         int             manageDSAit = get_manageDSAit( op );
  55         int             cscope = LDAP_SCOPE_DEFAULT;
  56
  57         struct slap_limits_set *limit = NULL;
  58         int isroot = 0;
  59
  60 #ifdef SLAP_X_FILTER_HASSUBORDINATES
  61         int             filter_hasSubordinates = 0;
  62 #endif /* SLAP_X_FILTER_HASSUBORDINATES */
  63
  64 #ifdef NEW_LOGGING
  65         LDAP_LOG( BACK_LDBM, ENTRY, "ldbm_back_search: enter\n", 0, 0, 0 );
  66 #else
  67         Debug(LDAP_DEBUG_TRACE, "=> ldbm_back_search\n", 0, 0, 0);
  68 #endif
  69
  70         /* grab giant lock for reading */
  71         ldap_pvt_thread_rdwr_rlock(&li->li_giant_rwlock);
  72
  73         if ( nbase->bv_len == 0 ) {
  74                 /* DIT root special case */
  75                 e = (Entry *) &slap_entry_root;
  76
  77                 /* need normalized dn below */
  78                 ber_dupbv( &realbase, &e->e_nname );
  79
  80                 candidates = search_candidates( be, e, filter,
  81                     scope, deref, manageDSAit );
  82
  83                 goto searchit;
  84
  85         } else if ( deref & LDAP_DEREF_FINDING ) {
  86                 /* deref dn and get entry with reader lock */
  87                 e = deref_dn_r( be, nbase, &err, &matched, &text );
  88
  89                 if( err == LDAP_NO_SUCH_OBJECT ) err = LDAP_REFERRAL;
  90
  91         } else {
  92                 /* get entry with reader lock */
  93                 e = dn2entry_r( be, nbase, &matched );
  94                 err = e != NULL ? LDAP_SUCCESS : LDAP_REFERRAL;
  95                 text = NULL;
  96         }
  97
  98         if ( e == NULL ) {
  99                 struct berval matched_dn = { 0, NULL };
 100                 BerVarray refs = NULL;
 101
 102                 if ( matched != NULL ) {
 103                         BerVarray erefs;
 104                         ber_dupbv( &matched_dn, &matched->e_name );
 105
 106                         erefs = is_entry_referral( matched )
 107                                 ? get_entry_referrals( be, conn, op, matched )
 108                                 : NULL;
 109
 110                         cache_return_entry_r( &li->li_cache, matched );
 111
 112                         if( erefs ) {
 113                                 refs = referral_rewrite( erefs, &matched_dn,
 114                                         base, scope );
 115
 116                                 ber_bvarray_free( erefs );
 117                         }
 118
 119                 } else {
 120                         refs = referral_rewrite( default_referral,
 121                                 NULL, base, scope );
 122                 }
 123
 124                 ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
 125
 126                 send_ldap_result( conn, op, err, matched_dn.bv_val,
 127                         text, refs, NULL );
 128
 129                 ber_bvarray_free( refs );
 130                 ber_memfree( matched_dn.bv_val );
 131                 return 1;
 132         }
 133
 134         if (!manageDSAit && is_entry_referral( e ) ) {
 135                 /* entry is a referral, don't allow add */
 136                 struct berval matched_dn;
 137                 BerVarray erefs;
 138                 BerVarray refs;
 139
 140                 ber_dupbv( &matched_dn, &e->e_name );
 141                 erefs = get_entry_referrals( be, conn, op, e );
 142                 refs = NULL;
 143
 144                 cache_return_entry_r( &li->li_cache, e );
 145                 ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
 146
 147 #ifdef NEW_LOGGING
 148                 LDAP_LOG( BACK_LDBM, INFO,
 149                         "ldbm_search: entry (%s) is a referral.\n",
 150                         e->e_dn, 0, 0 );
 151 #else
 152                 Debug( LDAP_DEBUG_TRACE,
 153                         "ldbm_search: entry is referral\n",
 154                         0, 0, 0 );
 155 #endif
 156
 157                 if( erefs ) {
 158                         refs = referral_rewrite( erefs, &matched_dn,
 159                                 base, scope );
 160
 161                         ber_bvarray_free( erefs );
 162                 }
 163
 164                 if( refs ) {
 165                         send_ldap_result( conn, op, LDAP_REFERRAL,
 166                                 matched_dn.bv_val, NULL, refs, NULL );
 167                         ber_bvarray_free( refs );
 168
 169                 } else {
 170                         send_ldap_result( conn, op, LDAP_OTHER,
 171                                 matched_dn.bv_val,
 172                         "bad referral object", NULL, NULL );
 173                 }
 174
 175                 ber_memfree( matched_dn.bv_val );
 176                 return 1;
 177         }
 178
 179         if ( is_entry_alias( e ) ) {
 180                 /* don't deref */
 181                 deref = LDAP_DEREF_NEVER;
 182         }
 183
 184         if ( scope == LDAP_SCOPE_BASE ) {
 185                 cscope = LDAP_SCOPE_BASE;
 186                 candidates = base_candidate( be, e );
 187
 188         } else {
 189                 cscope = ( scope != LDAP_SCOPE_SUBTREE )
 190                         ? LDAP_SCOPE_BASE : LDAP_SCOPE_SUBTREE;
 191                 candidates = search_candidates( be, e, filter,
 192                     scope, deref, manageDSAit );
 193         }
 194
 195         /* need normalized dn below */
 196         ber_dupbv( &realbase, &e->e_nname );
 197
 198         cache_return_entry_r( &li->li_cache, e );
 199
 200 searchit:
 201         if ( candidates == NULL ) {
 202                 /* no candidates */
 203 #ifdef NEW_LOGGING
 204                 LDAP_LOG( BACK_LDBM, INFO,
 205                         "ldbm_search: no candidates\n" , 0, 0, 0);
 206 #else
 207                 Debug( LDAP_DEBUG_TRACE, "ldbm_search: no candidates\n",
 208                         0, 0, 0 );
 209 #endif
 210
 211                 send_search_result( conn, op,
 212                         LDAP_SUCCESS,
 213                         NULL, NULL, NULL, NULL, 0 );
 214
 215                 rc = 1;
 216                 goto done;
 217         }
 218
 219         /* if not root, get appropriate limits */
 220         if ( be_isroot( be, &op->o_ndn ) ) {
 221                 isroot = 1;
 222         } else {
 223                 ( void ) get_limits( be, &op->o_ndn, &limit );
 224         }
 225
 226         /* if candidates exceed to-be-checked entries, abort */
 227         if ( !isroot && limit->lms_s_unchecked != -1 ) {
 228                 if ( ID_BLOCK_NIDS( candidates ) > (unsigned) limit->lms_s_unchecked ) {
 229                         send_search_result( conn, op, LDAP_ADMINLIMIT_EXCEEDED,
 230                                         NULL, NULL, NULL, NULL, 0 );
 231                         rc = 0;
 232                         goto done;
 233                 }
 234         }
 235
 236         /* if root an no specific limit is required, allow unlimited search */
 237         if ( isroot ) {
 238                 if ( tlimit == 0 ) {
 239                         tlimit = -1;
 240                 }
 241
 242                 if ( slimit == 0 ) {
 243                         slimit = -1;
 244                 }
 245
 246         } else {
 247                 /* if no limit is required, use soft limit */
 248                 if ( tlimit <= 0 ) {
 249                         tlimit = limit->lms_t_soft;
 250
 251                 /* if requested limit higher than hard limit, abort */
 252                 } else if ( tlimit > limit->lms_t_hard ) {
 253                         /* no hard limit means use soft instead */
 254                         if ( limit->lms_t_hard == 0 && tlimit > limit->lms_t_soft ) {
 255                                 tlimit = limit->lms_t_soft;
 256
 257                         /* positive hard limit means abort */
 258                         } else if ( limit->lms_t_hard > 0 ) {
 259                                 send_search_result( conn, op,
 260                                                 LDAP_UNWILLING_TO_PERFORM,
 261                                                 NULL, NULL, NULL, NULL, 0 );
 262                                 rc = 0;
 263                                 goto done;
 264                         }
 265
 266                         /* negative hard limit means no limit */
 267                 }
 268
 269                 /* if no limit is required, use soft limit */
 270                 if ( slimit <= 0 ) {
 271                         slimit = limit->lms_s_soft;
 272
 273                 /* if requested limit higher than hard limit, abort */
 274                 } else if ( slimit > limit->lms_s_hard ) {
 275                         /* no hard limit means use soft instead */
 276                         if ( limit->lms_s_hard == 0 && slimit > limit->lms_s_soft ) {
 277                                 slimit = limit->lms_s_soft;
 278
 279                         /* positive hard limit means abort */
 280                         } else if ( limit->lms_s_hard > 0 ) {
 281                                 send_search_result( conn, op,
 282                                                 LDAP_UNWILLING_TO_PERFORM,
 283                                                 NULL, NULL, NULL, NULL, 0 );
 284                                 rc = 0;
 285                                 goto done;
 286                         }
 287
 288                         /* negative hard limit means no limit */
 289                 }
 290         }
 291
 292         /* compute it anyway; root does not use it */
 293         stoptime = op->o_time + tlimit;
 294
 295 #ifdef SLAP_X_FILTER_HASSUBORDINATES
 296         /*
 297          * is hasSubordinates used in the filter ?
 298          * FIXME: we may compute this directly when parsing the filter
 299          */
 300         filter_hasSubordinates = filter_has_subordinates( filter );
 301 #endif /* SLAP_X_FILTER_HASSUBORDINATES */
 302
 303         for ( id = idl_firstid( candidates, &cursor ); id != NOID;
 304             id = idl_nextid( candidates, &cursor ) )
 305         {
 306                 int scopeok = 0;
 307                 int result = 0;
 308 #ifdef SLAP_X_FILTER_HASSUBORDINATES
 309                 Attribute       *hasSubordinates = NULL;
 310 #endif /* SLAP_X_FILTER_HASSUBORDINATES */
 311
 312                 /* check for abandon */
 313                 if ( op->o_abandon ) {
 314                         rc = 0;
 315                         goto done;
 316                 }
 317
 318                 /* check time limit */
 319                 if ( tlimit != -1 && slap_get_time() > stoptime ) {
 320                         send_search_result( conn, op, LDAP_TIMELIMIT_EXCEEDED,
 321                                 NULL, NULL, v2refs, NULL, nentries );
 322                         rc = 0;
 323                         goto done;
 324                 }
 325
 326                 /* get the entry with reader lock */
 327                 e = id2entry_r( be, id );
 328
 329                 if ( e == NULL ) {
 330 #ifdef NEW_LOGGING
 331                         LDAP_LOG( BACK_LDBM, INFO,
 332                                 "ldbm_search: candidate %ld not found.\n", id, 0, 0 );
 333 #else
 334                         Debug( LDAP_DEBUG_TRACE,
 335                                 "ldbm_search: candidate %ld not found\n",
 336                                 id, 0, 0 );
 337 #endif
 338
 339                         goto loop_continue;
 340                 }
 341
 342                 if ( deref & LDAP_DEREF_SEARCHING && is_entry_alias( e ) ) {
 343                         Entry *matched;
 344                         int err;
 345                         const char *text;
 346
 347                         e = deref_entry_r( be, e, &err, &matched, &text );
 348
 349                         if( e == NULL ) {
 350                                 e = matched;
 351                                 goto loop_continue;
 352                         }
 353
 354                         if( e->e_id == id ) {
 355                                 /* circular loop */
 356                                 goto loop_continue;
 357                         }
 358
 359                         /* need to skip alias which deref into scope */
 360                         if( scope & LDAP_SCOPE_ONELEVEL ) {
 361                                 struct berval pdn;
 362                                 dnParent( &e->e_nname, &pdn );
 363                                 if ( ber_bvcmp( &pdn, &realbase ) ) {
 364                                         goto loop_continue;
 365                                 }
 366
 367                         } else if ( dnIsSuffix( &e->e_nname, &realbase ) ) {
 368                                 /* alias is within scope */
 369 #ifdef NEW_LOGGING
 370                                 LDAP_LOG( BACK_LDBM, DETAIL1,
 371                                         "ldbm_search: alias \"%s\" in subtree\n", e->e_dn, 0, 0 );
 372 #else
 373                                 Debug( LDAP_DEBUG_TRACE,
 374                                         "ldbm_search: alias \"%s\" in subtree\n",
 375                                         e->e_dn, 0, 0 );
 376 #endif
 377
 378                                 goto loop_continue;
 379                         }
 380
 381                         scopeok = 1;
 382                 }
 383
 384                 /*
 385                  * if it's a referral, add it to the list of referrals. only do
 386                  * this for non-base searches, and don't check the filter
 387                  * explicitly here since it's only a candidate anyway.
 388                  */
 389                 if ( !manageDSAit && scope != LDAP_SCOPE_BASE &&
 390                         is_entry_referral( e ) )
 391                 {
 392                         struct berval   dn;
 393
 394                         /* check scope */
 395                         if ( !scopeok && scope == LDAP_SCOPE_ONELEVEL ) {
 396                                 if ( !be_issuffix( be, &e->e_nname ) ) {
 397                                         dnParent( &e->e_nname, &dn );
 398                                         scopeok = dn_match( &dn, &realbase );
 399                                 } else {
 400                                         scopeok = (realbase.bv_len == 0);
 401                                 }
 402
 403                         } else if ( !scopeok && scope == LDAP_SCOPE_SUBTREE ) {
 404                                 scopeok = dnIsSuffix( &e->e_nname, &realbase );
 405
 406                         } else {
 407                                 scopeok = 1;
 408                         }
 409
 410                         if( scopeok ) {
 411                                 BerVarray erefs = get_entry_referrals(
 412                                         be, conn, op, e );
 413                                 BerVarray refs = referral_rewrite( erefs,
 414                                         &e->e_name, NULL,
 415                                         scope == LDAP_SCOPE_SUBTREE
 416                                                 ? LDAP_SCOPE_SUBTREE
 417                                                 : LDAP_SCOPE_BASE );
 418
 419                                 send_search_reference( be, conn, op,
 420                                         e, refs, NULL, &v2refs );
 421
 422                                 ber_bvarray_free( refs );
 423
 424                         } else {
 425 #ifdef NEW_LOGGING
 426                                 LDAP_LOG( BACK_LDBM, DETAIL2,
 427                                         "ldbm_search: candidate referral %ld scope not okay\n",
 428                                         id, 0, 0 );
 429 #else
 430                                 Debug( LDAP_DEBUG_TRACE,
 431                                         "ldbm_search: candidate referral %ld scope not okay\n",
 432                                         id, 0, 0 );
 433 #endif
 434                         }
 435
 436                         goto loop_continue;
 437                 }
 438
 439 #ifdef SLAP_X_FILTER_HASSUBORDINATES
 440                 /*
 441                  * if hasSubordinates is used in the filter,
 442                  * append it to the entry's attributes
 443                  */
 444                 if ( filter_hasSubordinates ) {
 445                         int     hs;
 446
 447                         hs = has_children( be, e );
 448                         hasSubordinates = slap_operational_hasSubordinate( hs );
 449                         if ( hasSubordinates == NULL ) {
 450                                 goto loop_continue;
 451                         }
 452
 453                         hasSubordinates->a_next = e->e_attrs;
 454                         e->e_attrs = hasSubordinates;
 455                 }
 456 #endif /* SLAP_X_FILTER_HASSUBORDINATES */
 457
 458                 /* if it matches the filter and scope, send it */
 459                 result = test_filter( be, conn, op, e, filter );
 460
 461 #ifdef SLAP_X_FILTER_HASSUBORDINATES
 462                 if ( hasSubordinates ) {
 463                         /*
 464                          * FIXME: this is fairly inefficient, because
 465                          * if hasSubordinates is among the required
 466                          * attrs, it will be added again later;
 467                          * maybe we should leave it and check
 468                          * check later if it's already present,
 469                          * if required
 470                          */
 471                         e->e_attrs = e->e_attrs->a_next;
 472                         attr_free( hasSubordinates );
 473                 }
 474 #endif /* SLAP_X_FILTER_HASSUBORDINATES */
 475
 476                 if ( result == LDAP_COMPARE_TRUE ) {
 477                         struct berval   dn;
 478
 479                         /* check scope */
 480                         if ( !scopeok && scope == LDAP_SCOPE_ONELEVEL ) {
 481                                 if ( !be_issuffix( be, &e->e_nname ) ) {
 482                                         dnParent( &e->e_nname, &dn );
 483                                         scopeok = dn_match( &dn, &realbase );
 484                                 } else {
 485                                         scopeok = (realbase.bv_len == 0);
 486                                 }
 487
 488                         } else if ( !scopeok && scope == LDAP_SCOPE_SUBTREE ) {
 489                                 scopeok = dnIsSuffix( &e->e_nname, &realbase );
 490
 491                         } else {
 492                                 scopeok = 1;
 493                         }
 494
 495                         if ( scopeok ) {
 496                                 /* check size limit */
 497                                 if ( --slimit == -1 ) {
 498                                         cache_return_entry_r( &li->li_cache, e );
 499                                         send_search_result( conn, op,
 500                                                 LDAP_SIZELIMIT_EXCEEDED, NULL, NULL,
 501                                                 v2refs, NULL, nentries );
 502                                         rc = 0;
 503                                         goto done;
 504                                 }
 505
 506                                 if (e) {
 507                                         result = send_search_entry(be, conn, op,
 508                                                 e, attrs, attrsonly, NULL);
 509
 510                                         switch (result) {
 511                                         case 0:         /* entry sent ok */
 512                                                 nentries++;
 513                                                 break;
 514                                         case 1:         /* entry not sent */
 515                                                 break;
 516                                         case -1:        /* connection closed */
 517                                                 cache_return_entry_r( &li->li_cache, e );
 518                                                 rc = 0;
 519                                                 goto done;
 520                                         }
 521                                 }
 522                         } else {
 523 #ifdef NEW_LOGGING
 524                                 LDAP_LOG( BACK_LDBM, DETAIL2,
 525                                         "ldbm_search: candidate entry %ld scope not okay\n",
 526                                         id, 0, 0 );
 527 #else
 528                                 Debug( LDAP_DEBUG_TRACE,
 529                                         "ldbm_search: candidate entry %ld scope not okay\n",
 530                                         id, 0, 0 );
 531 #endif
 532                         }
 533
 534                 } else {
 535 #ifdef NEW_LOGGING
 536                         LDAP_LOG( BACK_LDBM, DETAIL2,
 537                                 "ldbm_search: candidate entry %ld does not match filter\n",
 538                                 id, 0, 0 );
 539 #else
 540                         Debug( LDAP_DEBUG_TRACE,
 541                                 "ldbm_search: candidate entry %ld does not match filter\n",
 542                                 id, 0, 0 );
 543 #endif
 544                 }
 545
 546 loop_continue:
 547                 if( e != NULL ) {
 548                         /* free reader lock */
 549                         cache_return_entry_r( &li->li_cache, e );
 550                 }
 551
 552                 ldap_pvt_thread_yield();
 553         }
 554
 555         send_search_result( conn, op,
 556                 v2refs == NULL ? LDAP_SUCCESS : LDAP_REFERRAL,
 557                 NULL, NULL, v2refs, NULL, nentries );
 558
 559         rc = 0;
 560
 561 done:
 562         ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
 563
 564         if( candidates != NULL )
 565                 idl_free( candidates );
 566
 567         if( v2refs ) ber_bvarray_free( v2refs );
 568         if( realbase.bv_val ) free( realbase.bv_val );
 569
 570         return rc;
 571 }
 572
 573 static ID_BLOCK *
 574 base_candidate(
 575     Backend     *be,
 576         Entry   *e )
 577 {
 578         ID_BLOCK                *idl;
 579
 580 #ifdef NEW_LOGGING
 581         LDAP_LOG( BACK_LDBM, ENTRY, "base_candidate: base (%s)\n", e->e_dn, 0, 0 );
 582 #else
 583         Debug(LDAP_DEBUG_TRACE, "base_candidates: base: \"%s\"\n",
 584                 e->e_dn, 0, 0);
 585 #endif
 586
 587
 588         idl = idl_alloc( 1 );
 589         idl_insert( &idl, e->e_id, 1 );
 590
 591         return( idl );
 592 }
 593
 594 static ID_BLOCK *
 595 search_candidates(
 596     Backend     *be,
 597     Entry       *e,
 598     Filter      *filter,
 599     int         scope,
 600         int             deref,
 601         int             manageDSAit )
 602 {
 603         ID_BLOCK                *candidates;
 604         Filter          f, fand, rf, af, xf;
 605     AttributeAssertion aa_ref, aa_alias;
 606         struct berval bv_ref = { sizeof("REFERRAL")-1, "REFERRAL" };
 607         struct berval bv_alias = { sizeof("ALIAS")-1, "ALIAS" };
 608
 609 #ifdef NEW_LOGGING
 610         LDAP_LOG( BACK_LDBM, DETAIL1,
 611                    "search_candidates: base (%s) scope %d deref %d\n",
 612                    e->e_ndn, scope, deref );
 613 #else
 614         Debug(LDAP_DEBUG_TRACE,
 615                 "search_candidates: base=\"%s\" s=%d d=%d\n",
 616                 e->e_ndn, scope, deref );
 617 #endif
 618
 619
 620         xf.f_or = filter;
 621         xf.f_choice = LDAP_FILTER_OR;
 622         xf.f_next = NULL;
 623
 624         if( !manageDSAit ) {
 625                 /* match referrals */
 626                 rf.f_choice = LDAP_FILTER_EQUALITY;
 627                 rf.f_ava = &aa_ref;
 628                 rf.f_av_desc = slap_schema.si_ad_objectClass;
 629                 rf.f_av_value = bv_ref;
 630                 rf.f_next = xf.f_or;
 631                 xf.f_or = &rf;
 632         }
 633
 634         if( deref & LDAP_DEREF_SEARCHING ) {
 635                 /* match aliases */
 636                 af.f_choice = LDAP_FILTER_EQUALITY;
 637                 af.f_ava = &aa_alias;
 638                 af.f_av_desc = slap_schema.si_ad_objectClass;
 639                 af.f_av_value = bv_alias;
 640                 af.f_next = xf.f_or;
 641                 xf.f_or = &af;
 642         }
 643
 644         f.f_next = NULL;
 645         f.f_choice = LDAP_FILTER_AND;
 646         f.f_and = &fand;
 647         fand.f_choice = scope == LDAP_SCOPE_SUBTREE
 648                 ? SLAPD_FILTER_DN_SUBTREE
 649                 : SLAPD_FILTER_DN_ONE;
 650         fand.f_dn = &e->e_nname;
 651         fand.f_next = xf.f_or == filter ? filter : &xf ;
 652
 653         candidates = filter_candidates( be, &f );
 654
 655         return( candidates );
 656 }