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

   1 /* search.c - search operation */
   2 /* $OpenLDAP$ */
   3 /*
   4  * Copyright 1998-2000 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 #include <ac/string.h>
  12
  13 #include "back-bdb.h"
  14 #include "external.h"
  15
  16 static int base_candidate(
  17         BackendDB       *be,
  18         Entry   *e,
  19         ID              *ids );
  20 static int search_candidates(
  21         BackendDB *be,
  22         Entry *e,
  23         Filter *filter,
  24         int scope,
  25         int deref,
  26         int manageDSAit,
  27         ID      *ids );
  28
  29 static ID idl_first( ID *ids, ID *cursor );
  30 static ID idl_next( ID *ids, ID *cursor );
  31
  32 int
  33 bdb_search(
  34         BackendDB       *be,
  35         Connection      *conn,
  36         Operation       *op,
  37         const char      *base,
  38         const char      *nbase,
  39         int             scope,
  40         int             deref,
  41         int             slimit,
  42         int             tlimit,
  43         Filter  *filter,
  44         const char      *filterstr,
  45         char    **attrs,
  46         int             attrsonly )
  47 {
  48         struct bdb_info *bdb = (struct bdb_info *) be->be_private;
  49         int              abandon;
  50         int             rc;
  51         const char *text = NULL;
  52         time_t          stoptime;
  53         ID              id, cursor;
  54         ID              candidates[BDB_IDL_SIZE];
  55         Entry           *e = NULL;
  56         struct berval **v2refs = NULL;
  57         Entry   *matched = NULL;
  58         char    *realbase = NULL;
  59         int             nentries = 0;
  60         int             manageDSAit;
  61
  62         Debug( LDAP_DEBUG_TRACE, "=> bdb_back_search\n",
  63                 0, 0, 0);
  64
  65         manageDSAit = get_manageDSAit( op );
  66
  67 #ifdef BDB_ALIASES
  68         /* get entry with reader lock */
  69         if ( deref & LDAP_DEREF_FINDING ) {
  70                 e = deref_dn_r( be, nbase, &err, &matched, &text );
  71
  72         } else
  73 #endif
  74         {
  75                 rc = bdb_dn2entry( be, NULL, nbase, &e, &matched, 0 );
  76         }
  77
  78         switch(rc) {
  79         case DB_NOTFOUND:
  80         case 0:
  81                 break;
  82         default:
  83                 send_ldap_result( conn, op, rc=LDAP_OTHER,
  84                         NULL, "internal error", NULL, NULL );
  85                 return rc;
  86         }
  87
  88         if ( e == NULL ) {
  89                 char *matched_dn = NULL;
  90                 struct berval **refs = NULL;
  91
  92                 if ( matched != NULL ) {
  93                         matched_dn = ch_strdup( matched->e_dn );
  94
  95                         refs = is_entry_referral( matched )
  96                                 ? get_entry_referrals( be, conn, op, matched )
  97                                 : NULL;
  98
  99                 } else {
 100                         refs = default_referral;
 101                 }
 102
 103                 send_ldap_result( conn, op,     rc=LDAP_REFERRAL ,
 104                         matched_dn, text, refs, NULL );
 105
 106                 if( matched != NULL ) {
 107                         ber_bvecfree( refs );
 108                         free( matched_dn );
 109                         bdb_entry_return( be, matched );
 110                 }
 111
 112                 return rc;
 113         }
 114
 115         if (!manageDSAit && is_entry_referral( e ) ) {
 116                 /* entry is a referral, don't allow add */
 117                 char *matched_dn = ch_strdup( e->e_dn );
 118                 struct berval **refs = get_entry_referrals( be,
 119                         conn, op, e );
 120
 121                 bdb_entry_return( be, e );
 122
 123                 Debug( LDAP_DEBUG_TRACE, "bdb_search: entry is referral\n",
 124                         0, 0, 0 );
 125
 126                 send_ldap_result( conn, op, LDAP_REFERRAL,
 127                         matched_dn, NULL, refs, NULL );
 128
 129                 ber_bvecfree( refs );
 130                 free( matched_dn );
 131
 132                 return 1;
 133         }
 134
 135         if ( tlimit == 0 && be_isroot( be, op->o_ndn ) ) {
 136                 tlimit = -1;    /* allow root to set no limit */
 137         } else {
 138                 tlimit = (tlimit > be->be_timelimit || tlimit < 1) ?
 139                         be->be_timelimit : tlimit;
 140                 stoptime = op->o_time + tlimit;
 141         }
 142
 143         if ( slimit == 0 && be_isroot( be, op->o_ndn ) ) {
 144                 slimit = -1;    /* allow root to set no limit */
 145         } else {
 146                 slimit = (slimit > be->be_sizelimit || slimit < 1) ?
 147                         be->be_sizelimit : slimit;
 148         }
 149
 150         if ( scope == LDAP_SCOPE_BASE ) {
 151                 rc = base_candidate( be, e, candidates );
 152
 153         } else {
 154                 rc = search_candidates( be, e, filter,
 155                         scope, deref, manageDSAit, candidates );
 156         }
 157
 158         /* need normalized dn below */
 159         realbase = ch_strdup( e->e_ndn );
 160
 161         /* start cursor at base entry's id */
 162         cursor = e->e_id;
 163
 164         bdb_entry_return( be, e );
 165
 166         if ( candidates[0] == 0 ) {
 167                 Debug( LDAP_DEBUG_TRACE, "bdb_search: no candidates\n",
 168                         0, 0, 0 );
 169
 170                 send_search_result( conn, op,
 171                         LDAP_SUCCESS,
 172                         NULL, NULL, NULL, NULL, 0 );
 173
 174                 rc = 1;
 175                 goto done;
 176         }
 177
 178         for ( id = idl_first( candidates, &cursor );
 179                 id != NOID;
 180                 id = idl_next( candidates, &cursor ) )
 181         {
 182                 int             scopeok = 0;
 183
 184                 /* check for abandon */
 185                 ldap_pvt_thread_mutex_lock( &op->o_abandonmutex );
 186                 abandon = op->o_abandon;
 187                 ldap_pvt_thread_mutex_unlock( &op->o_abandonmutex );
 188
 189                 if ( abandon ) {
 190                         rc = 0;
 191                         goto done;
 192                 }
 193
 194                 /* check time limit */
 195                 if ( tlimit != -1 && slap_get_time() > stoptime ) {
 196                         send_search_result( conn, op, rc = LDAP_TIMELIMIT_EXCEEDED,
 197                                 NULL, NULL, v2refs, NULL, nentries );
 198                         goto done;
 199                 }
 200
 201                 /* get the entry with reader lock */
 202                 rc = bdb_id2entry( be, NULL, id, &e );
 203
 204                 if ( e == NULL ) {
 205                         if( !BDB_IDL_IS_RANGE(candidates) ) {
 206                                 /* only complain for non-range IDLs */
 207                                 Debug( LDAP_DEBUG_TRACE,
 208                                         "bdb_search: candidate %ld not found\n",
 209                                         id, 0, 0 );
 210                         }
 211
 212                         goto loop_continue;
 213                 }
 214
 215 #ifdef BDB_ALIASES
 216                 if ( deref & LDAP_DEREF_SEARCHING && is_entry_alias( e ) ) {
 217                         Entry *matched;
 218                         int err;
 219                         const char *text;
 220
 221                         e = deref_entry_r( be, e, &err, &matched, &text );
 222
 223                         if( e == NULL ) {
 224                                 e = matched;
 225                                 goto loop_continue;
 226                         }
 227
 228                         if( e->e_id == id ) {
 229                                 /* circular loop */
 230                                 goto loop_continue;
 231                         }
 232
 233                         /* need to skip alias which deref into scope */
 234                         if( scope & LDAP_SCOPE_ONELEVEL ) {
 235                                 char *pdn = dn_parent( NULL, e->e_ndn );
 236                                 if ( pdn != NULL ) {
 237                                         if( strcmp( pdn, realbase ) ) {
 238                                                 free( pdn );
 239                                                 goto loop_continue;
 240                                         }
 241                                         free(pdn);
 242                                 }
 243
 244                         } else if ( dn_issuffix( e->e_ndn, realbase ) ) {
 245                                 /* alias is within scope */
 246                                 Debug( LDAP_DEBUG_TRACE,
 247                                         "bdb_search: \"%s\" in subtree\n",
 248                                         e->e_dn, 0, 0 );
 249                                 goto loop_continue;
 250                         }
 251
 252                         scopeok = 1;
 253                 }
 254 #endif
 255
 256                 /*
 257                  * if it's a referral, add it to the list of referrals. only do
 258                  * this for non-base searches, and don't check the filter
 259                  * explicitly here since it's only a candidate anyway.
 260                  */
 261                 if ( !manageDSAit && scope != LDAP_SCOPE_BASE &&
 262                         is_entry_referral( e ) )
 263                 {
 264                         struct berval **refs = get_entry_referrals(
 265                                 be, conn, op, e );
 266
 267                         send_search_reference( be, conn, op,
 268                                 e, refs, scope, NULL, &v2refs );
 269
 270                         ber_bvecfree( refs );
 271
 272                         goto loop_continue;
 273                 }
 274
 275                 /* if it matches the filter and scope, send it */
 276                 rc = test_filter( be, conn, op, e, filter );
 277                 if ( rc == LDAP_COMPARE_TRUE ) {
 278                         char    *dn;
 279
 280                         /* check scope */
 281                         if ( !scopeok && scope == LDAP_SCOPE_ONELEVEL ) {
 282                                 if ( (dn = dn_parent( be, e->e_ndn )) != NULL ) {
 283                                         (void) dn_normalize( dn );
 284                                         scopeok = (dn == realbase)
 285                                                 ? 1
 286                                                 : (strcmp( dn, realbase ) ? 0 : 1 );
 287                                         free( dn );
 288
 289                                 } else {
 290                                         scopeok = (realbase == NULL || *realbase == '\0');
 291                                 }
 292
 293                         } else if ( !scopeok && scope == LDAP_SCOPE_SUBTREE ) {
 294                                 dn = ch_strdup( e->e_ndn );
 295                                 scopeok = dn_issuffix( dn, realbase );
 296                                 free( dn );
 297
 298                         } else {
 299                                 scopeok = 1;
 300                         }
 301
 302                         if ( scopeok ) {
 303                                 /* check size limit */
 304                                 if ( --slimit == -1 ) {
 305                                         bdb_entry_return( be, e );
 306                                         send_search_result( conn, op,
 307                                                 rc = LDAP_SIZELIMIT_EXCEEDED, NULL, NULL,
 308                                                 v2refs, NULL, nentries );
 309                                         goto done;
 310                                 }
 311
 312                                 if (e) {
 313                                         int result = send_search_entry( be, conn, op,
 314                                                 e, attrs, attrsonly, NULL);
 315
 316                                         switch (result) {
 317                                         case 0:         /* entry sent ok */
 318                                                 nentries++;
 319                                                 break;
 320                                         case 1:         /* entry not sent */
 321                                                 break;
 322                                         case -1:        /* connection closed */
 323                                                 bdb_entry_return( be, e );
 324                                                 rc = LDAP_OTHER;
 325                                                 goto done;
 326                                         }
 327                                 }
 328                         } else {
 329                                 Debug( LDAP_DEBUG_TRACE,
 330                                         "bdb_search: %ld scope not okay\n",
 331                                         id, 0, 0 );
 332                         }
 333                 } else {
 334                         Debug( LDAP_DEBUG_TRACE,
 335                                 "bdb_search: %ld does match filter\n",
 336                                 id, 0, 0 );
 337                 }
 338
 339 loop_continue:
 340                 if( e != NULL ) {
 341                         /* free reader lock */
 342                         bdb_entry_return( be, e );
 343                 }
 344
 345                 ldap_pvt_thread_yield();
 346         }
 347         send_search_result( conn, op,
 348                 v2refs == NULL ? LDAP_SUCCESS : LDAP_REFERRAL,
 349                 NULL, NULL, v2refs, NULL, nentries );
 350
 351         rc = 0;
 352
 353 done:
 354         ber_bvecfree( v2refs );
 355         if( realbase ) ch_free( realbase );
 356
 357         return rc;
 358 }
 359
 360
 361 static int base_candidate(
 362         BackendDB       *be,
 363         Entry   *e,
 364         ID              *ids )
 365 {
 366         Debug(LDAP_DEBUG_ARGS, "base_candidates: base: \"%s\" (0x%08lx)\n",
 367                 e->e_dn, (long) e->e_id, 0);
 368
 369         ids[0] = 1;
 370         ids[1] = e->e_id;
 371         return 0;
 372 }
 373
 374 static int search_candidates(
 375         BackendDB *be,
 376         Entry *e,
 377         Filter *filter,
 378         int scope,
 379         int deref,
 380         int manageDSAit,
 381         ID      *ids )
 382 {
 383         int rc;
 384         Filter          f, fand, rf, af, xf;
 385         AttributeAssertion aa_ref, aa_alias;
 386
 387         Debug(LDAP_DEBUG_TRACE,
 388                 "search_candidates: base=\"%s\" (0x%08lx) scope=%d\n",
 389                 e->e_dn, (long) e->e_id, scope );
 390
 391         xf.f_or = filter;
 392         xf.f_choice = LDAP_FILTER_OR;
 393         xf.f_next = NULL;
 394
 395         if( !manageDSAit ) {
 396                 /* match referrals */
 397                 static struct berval bv_ref = { sizeof("REFERRAL")-1, "REFERRAL" };
 398                 rf.f_choice = LDAP_FILTER_EQUALITY;
 399                 rf.f_ava = &aa_ref;
 400                 rf.f_av_desc = slap_schema.si_ad_objectClass;
 401                 rf.f_av_value = &bv_ref;
 402                 rf.f_next = xf.f_or;
 403                 xf.f_or = &rf;
 404         }
 405
 406 #ifdef BDB_ALIASES
 407         if( deref & LDAP_DEREF_SEARCHING ) {
 408                 /* match aliases */
 409                 static struct berval bv_alias = { sizeof("ALIAS")-1, "ALIAS" };
 410                 af.f_choice = LDAP_FILTER_EQUALITY;
 411                 af.f_ava = &aa_alias;
 412                 af.f_av_desc = slap_schema.si_ad_objectClass;
 413                 af.f_av_value = &bv_alias;
 414                 af.f_next = xf.f_or;
 415                 xf.f_or = &af;
 416         }
 417 #endif
 418
 419         f.f_next = NULL;
 420         f.f_choice = LDAP_FILTER_AND;
 421         f.f_and = &fand;
 422         fand.f_choice = scope == LDAP_SCOPE_SUBTREE
 423                 ? SLAPD_FILTER_DN_SUBTREE
 424                 : SLAPD_FILTER_DN_ONE;
 425         fand.f_dn = e->e_ndn;
 426         fand.f_next = xf.f_or == filter ? filter : &xf ;
 427
 428 #if 0
 429         rc = bdb_filter_candidates( be, &f, ids );
 430 #else
 431         /* a quick hack */
 432         ids[0] = NOID;
 433         ids[1] = e->e_id;
 434         ids[2] = e->e_id+128;
 435         rc = 0;
 436 #endif
 437
 438         Debug(LDAP_DEBUG_TRACE,
 439                 "search_candidates: id=%ld first=%ld last=%ld\n",
 440                 ids[0], ids[1],
 441                 BDB_IDL_IS_RANGE( ids ) ? ids[2] : ids[ids[0]] );
 442
 443         return rc;
 444 }
 445
 446 static ID idl_first( ID *ids, ID *cursor )
 447 {
 448         ID pos;
 449
 450         if ( ids[0] == 0 ) {
 451                 *cursor = NOID;
 452                 return NOID;
 453         }
 454
 455         if ( BDB_IDL_IS_RANGE( ids ) ) {
 456                 if( *cursor < ids[1] ) {
 457                         *cursor = ids[1];
 458                 }
 459                 return *cursor;
 460         }
 461
 462         pos = bdb_idl_search( ids, *cursor );
 463
 464         if( pos > ids[0] ) {
 465                 return NOID;
 466         }
 467
 468         *cursor = pos;
 469         return ids[pos];
 470 }
 471
 472 static ID idl_next( ID *ids, ID *cursor )
 473 {
 474         if ( BDB_IDL_IS_RANGE( ids ) ) {
 475                 if( ids[2] < ++(*cursor) ) {
 476                         return NOID;
 477                 }
 478                 return *cursor;
 479         }
 480
 481         if ( *cursor < ids[0] ) {
 482                 return ids[(*cursor)++];
 483         }
 484
 485         return NOID;
 486 }
 487