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                         Debug( LDAP_DEBUG_TRACE,
 206                                 "bdb_search: candidate %ld not found\n",
 207                                 id, 0, 0 );
 208
 209                         goto loop_continue;
 210                 }
 211
 212 #ifdef BDB_ALIASES
 213                 if ( deref & LDAP_DEREF_SEARCHING && is_entry_alias( e ) ) {
 214                         Entry *matched;
 215                         int err;
 216                         const char *text;
 217
 218                         e = deref_entry_r( be, e, &err, &matched, &text );
 219
 220                         if( e == NULL ) {
 221                                 e = matched;
 222                                 goto loop_continue;
 223                         }
 224
 225                         if( e->e_id == id ) {
 226                                 /* circular loop */
 227                                 goto loop_continue;
 228                         }
 229
 230                         /* need to skip alias which deref into scope */
 231                         if( scope & LDAP_SCOPE_ONELEVEL ) {
 232                                 char *pdn = dn_parent( NULL, e->e_ndn );
 233                                 if ( pdn != NULL ) {
 234                                         if( strcmp( pdn, realbase ) ) {
 235                                                 free( pdn );
 236                                                 goto loop_continue;
 237                                         }
 238                                         free(pdn);
 239                                 }
 240
 241                         } else if ( dn_issuffix( e->e_ndn, realbase ) ) {
 242                                 /* alias is within scope */
 243                                 Debug( LDAP_DEBUG_TRACE,
 244                                         "bdb_search: \"%s\" in subtree\n",
 245                                         e->e_dn, 0, 0 );
 246                                 goto loop_continue;
 247                         }
 248
 249                         scopeok = 1;
 250                 }
 251 #endif
 252
 253                 /*
 254                  * if it's a referral, add it to the list of referrals. only do
 255                  * this for non-base searches, and don't check the filter
 256                  * explicitly here since it's only a candidate anyway.
 257                  */
 258                 if ( !manageDSAit && scope != LDAP_SCOPE_BASE &&
 259                         is_entry_referral( e ) )
 260                 {
 261                         struct berval **refs = get_entry_referrals(
 262                                 be, conn, op, e );
 263
 264                         send_search_reference( be, conn, op,
 265                                 e, refs, scope, NULL, &v2refs );
 266
 267                         ber_bvecfree( refs );
 268
 269                         goto loop_continue;
 270                 }
 271
 272                 /* if it matches the filter and scope, send it */
 273                 rc = test_filter( be, conn, op, e, filter );
 274                 if ( rc == LDAP_COMPARE_TRUE ) {
 275                         char    *dn;
 276
 277                         /* check scope */
 278                         if ( !scopeok && scope == LDAP_SCOPE_ONELEVEL ) {
 279                                 if ( (dn = dn_parent( be, e->e_ndn )) != NULL ) {
 280                                         (void) dn_normalize( dn );
 281                                         scopeok = (dn == realbase)
 282                                                 ? 1
 283                                                 : (strcmp( dn, realbase ) ? 0 : 1 );
 284                                         free( dn );
 285
 286                                 } else {
 287                                         scopeok = (realbase == NULL || *realbase == '\0');
 288                                 }
 289
 290                         } else if ( !scopeok && scope == LDAP_SCOPE_SUBTREE ) {
 291                                 dn = ch_strdup( e->e_ndn );
 292                                 scopeok = dn_issuffix( dn, realbase );
 293                                 free( dn );
 294
 295                         } else {
 296                                 scopeok = 1;
 297                         }
 298
 299                         if ( scopeok ) {
 300                                 /* check size limit */
 301                                 if ( --slimit == -1 ) {
 302                                         bdb_entry_return( be, e );
 303                                         send_search_result( conn, op,
 304                                                 rc = LDAP_SIZELIMIT_EXCEEDED, NULL, NULL,
 305                                                 v2refs, NULL, nentries );
 306                                         goto done;
 307                                 }
 308
 309                                 if (e) {
 310                                         int result = send_search_entry( be, conn, op,
 311                                                 e, attrs, attrsonly, NULL);
 312
 313                                         switch (result) {
 314                                         case 0:         /* entry sent ok */
 315                                                 nentries++;
 316                                                 break;
 317                                         case 1:         /* entry not sent */
 318                                                 break;
 319                                         case -1:        /* connection closed */
 320                                                 bdb_entry_return( be, e );
 321                                                 rc = LDAP_OTHER;
 322                                                 goto done;
 323                                         }
 324                                 }
 325                         } else {
 326                                 Debug( LDAP_DEBUG_TRACE,
 327                                         "bdb_search: %ld scope not okay\n",
 328                                         id, 0, 0 );
 329                         }
 330                 } else {
 331                         Debug( LDAP_DEBUG_TRACE,
 332                                 "bdb_search: %ld does match filter\n",
 333                                 id, 0, 0 );
 334                 }
 335
 336 loop_continue:
 337                 if( e != NULL ) {
 338                         /* free reader lock */
 339                         bdb_entry_return( be, e );
 340                 }
 341
 342                 ldap_pvt_thread_yield();
 343         }
 344         send_search_result( conn, op,
 345                 v2refs == NULL ? LDAP_SUCCESS : LDAP_REFERRAL,
 346                 NULL, NULL, v2refs, NULL, nentries );
 347
 348         rc = 0;
 349
 350 done:
 351         ber_bvecfree( v2refs );
 352         if( realbase ) ch_free( realbase );
 353
 354         return rc;
 355 }
 356
 357
 358 static int base_candidate(
 359         BackendDB       *be,
 360         Entry   *e,
 361         ID              *ids )
 362 {
 363         Debug(LDAP_DEBUG_ARGS, "base_candidates: base: \"%s\" (0x%08lx)\n",
 364                 e->e_dn, (long) e->e_id, 0);
 365
 366         ids[0] = 1;
 367         ids[1] = e->e_id;
 368         return 0;
 369 }
 370
 371 static int search_candidates(
 372         BackendDB *be,
 373         Entry *e,
 374         Filter *filter,
 375         int scope,
 376         int deref,
 377         int manageDSAit,
 378         ID      *ids )
 379 {
 380         int rc;
 381         Filter          f, fand, rf, af, xf;
 382         AttributeAssertion aa_ref, aa_alias;
 383
 384         Debug(LDAP_DEBUG_TRACE,
 385                 "search_candidates: base=\"%s\" (0x%08lx) scope=%d\n",
 386                 e->e_dn, (long) e->e_id, scope );
 387
 388         xf.f_or = filter;
 389         xf.f_choice = LDAP_FILTER_OR;
 390         xf.f_next = NULL;
 391
 392         if( !manageDSAit ) {
 393                 /* match referrals */
 394                 static struct berval bv_ref = { sizeof("REFERRAL")-1, "REFERRAL" };
 395                 rf.f_choice = LDAP_FILTER_EQUALITY;
 396                 rf.f_ava = &aa_ref;
 397                 rf.f_av_desc = slap_schema.si_ad_objectClass;
 398                 rf.f_av_value = &bv_ref;
 399                 rf.f_next = xf.f_or;
 400                 xf.f_or = &rf;
 401         }
 402
 403 #ifdef BDB_ALIASES
 404         if( deref & LDAP_DEREF_SEARCHING ) {
 405                 /* match aliases */
 406                 static struct berval bv_alias = { sizeof("ALIAS")-1, "ALIAS" };
 407                 af.f_choice = LDAP_FILTER_EQUALITY;
 408                 af.f_ava = &aa_alias;
 409                 af.f_av_desc = slap_schema.si_ad_objectClass;
 410                 af.f_av_value = &bv_alias;
 411                 af.f_next = xf.f_or;
 412                 xf.f_or = &af;
 413         }
 414 #endif
 415
 416         f.f_next = NULL;
 417         f.f_choice = LDAP_FILTER_AND;
 418         f.f_and = &fand;
 419         fand.f_choice = scope == LDAP_SCOPE_SUBTREE
 420                 ? SLAPD_FILTER_DN_SUBTREE
 421                 : SLAPD_FILTER_DN_ONE;
 422         fand.f_dn = e->e_ndn;
 423         fand.f_next = xf.f_or == filter ? filter : &xf ;
 424
 425 #if 0
 426         rc = bdb_filter_candidates( be, &f, ids );
 427 #else
 428         /* a quick hack */
 429         ids[0] = NOID;
 430         ids[1] = e->e_id;
 431         ids[2] = e->e_id+128;
 432         rc = 0;
 433 #endif
 434
 435         Debug(LDAP_DEBUG_TRACE,
 436                 "search_candidates: id=%ld first=%ld last=%ld\n",
 437                 ids[0], ids[1],
 438                 BDB_IDL_IS_RANGE( ids ) ? ids[2] : ids[ids[0]] );
 439
 440         return rc;
 441 }
 442
 443 static ID idl_first( ID *ids, ID *cursor )
 444 {
 445         ID pos;
 446
 447         if ( ids[0] == 0 ) {
 448                 *cursor = NOID;
 449                 return NOID;
 450         }
 451
 452         if ( BDB_IDL_IS_RANGE( ids ) ) {
 453                 if( *cursor < ids[1] ) {
 454                         *cursor = ids[1];
 455                 }
 456                 return *cursor;
 457         }
 458
 459         pos = bdb_idl_search( ids, *cursor );
 460
 461         if( pos > ids[0] ) {
 462                 return NOID;
 463         }
 464
 465         *cursor = pos;
 466         return ids[pos];
 467 }
 468
 469 static ID idl_next( ID *ids, ID *cursor )
 470 {
 471         if ( BDB_IDL_IS_RANGE( ids ) ) {
 472                 if( ids[2] < ++(*cursor) ) {
 473                         return NOID;
 474                 }
 475                 return *cursor;
 476         }
 477
 478         if ( *cursor < ids[0] ) {
 479                 return ids[(*cursor)++];
 480         }
 481
 482         return NOID;
 483 }
 484