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