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

   1 /* search.c - search operation */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2000-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 #include <ac/string.h>
  21
  22 #include "back-bdb.h"
  23 #include "idl.h"
  24 #include "external.h"
  25
  26 static int base_candidate(
  27         BackendDB       *be,
  28         Entry   *e,
  29         ID              *ids );
  30
  31 static int search_candidates(
  32         Operation *stackop,     /* op with the current threadctx/slab cache */
  33         Operation *sop,         /* search op */
  34         SlapReply *rs,
  35         Entry *e,
  36         u_int32_t locker,
  37         ID      *ids,
  38         ID      *scopes );
  39
  40 static int parse_paged_cookie( Operation *op, SlapReply *rs );
  41
  42 static void send_paged_response(
  43         Operation *op,
  44         SlapReply *rs,
  45         ID  *lastid,
  46         int tentries );
  47
  48 static int bdb_pfid_cmp( const void *v_id1, const void *v_id2 );
  49 static ID* bdb_id_dup( Operation *op, ID *id );
  50
  51 /* Dereference aliases for a single alias entry. Return the final
  52  * dereferenced entry on success, NULL on any failure.
  53  */
  54 static Entry * deref_base (
  55         Operation *op,
  56         SlapReply *rs,
  57         Entry *e,
  58         Entry **matched,
  59         u_int32_t locker,
  60         DB_LOCK *lock,
  61         ID      *tmp,
  62         ID      *visited )
  63 {
  64         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
  65         struct berval ndn;
  66         EntryInfo *ei;
  67         DB_LOCK lockr;
  68
  69         rs->sr_err = LDAP_ALIAS_DEREF_PROBLEM;
  70         rs->sr_text = "maximum deref depth exceeded";
  71
  72         while (BDB_IDL_N(tmp) < op->o_bd->be_max_deref_depth) {
  73                 /* Remember the last entry we looked at, so we can
  74                  * report broken links
  75                  */
  76                 *matched = e;
  77
  78                 /* If this is part of a subtree or onelevel search,
  79                  * have we seen this ID before? If so, quit.
  80                  */
  81                 if ( visited && bdb_idl_insert( visited, e->e_id ) ) {
  82                         e = NULL;
  83                         break;
  84                 }
  85
  86                 /* If we've seen this ID during this deref iteration,
  87                  * we've hit a loop.
  88                  */
  89                 if ( bdb_idl_insert( tmp, e->e_id ) ) {
  90                         rs->sr_err = LDAP_ALIAS_PROBLEM;
  91                         rs->sr_text = "circular alias";
  92                         e = NULL;
  93                         break;
  94                 }
  95
  96                 /* If there was a problem getting the aliasedObjectName,
  97                  * get_alias_dn will have set the error status.
  98                  */
  99                 if ( get_alias_dn(e, &ndn, &rs->sr_err, &rs->sr_text) ) {
 100                         e = NULL;
 101                         break;
 102                 }
 103
 104                 rs->sr_err = bdb_dn2entry( op, NULL, &ndn, &ei,
 105                         0, locker, &lockr );
 106
 107                 if ( ei ) {
 108                         e = ei->bei_e;
 109                 } else {
 110                         e = NULL;
 111                 }
 112
 113                 if (!e) {
 114                         rs->sr_err = LDAP_ALIAS_PROBLEM;
 115                         rs->sr_text = "aliasedObject not found";
 116                         break;
 117                 }
 118
 119                 /* Free the previous entry, continue to work with the
 120                  * one we just retrieved.
 121                  */
 122                 bdb_cache_return_entry_r( bdb->bi_dbenv, &bdb->bi_cache,
 123                         *matched, lock);
 124                 *lock = lockr;
 125
 126                 /* We found a regular entry. Return this to the caller. The
 127                  * entry is still locked for Read.
 128                  */
 129                 if (!is_entry_alias(e)) {
 130                         rs->sr_err = LDAP_SUCCESS;
 131                         rs->sr_text = NULL;
 132                         break;
 133                 }
 134         }
 135         return e;
 136 }
 137
 138 /* Look for and dereference all aliases within the search scope. Adds
 139  * the dereferenced entries to the "ids" list. Requires "stack" to be
 140  * able to hold 8 levels of DB_SIZE IDLs. Of course we're hardcoded to
 141  * require a minimum of 8 UM_SIZE IDLs so this is never a problem.
 142  */
 143 static int search_aliases(
 144         Operation *op,
 145         SlapReply *rs,
 146         Entry *e,
 147         u_int32_t locker,
 148         ID *ids,
 149         ID *scopes,
 150         ID *stack )
 151 {
 152         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 153         ID *aliases, *curscop, *subscop, *visited, *newsubs, *oldsubs, *tmp;
 154         ID cursora, ida, cursoro, ido, *subscop2;
 155         Entry *matched, *a;
 156         EntryInfo *ei;
 157         struct berval bv_alias = BER_BVC( "alias" );
 158         AttributeAssertion aa_alias;
 159         Filter  af;
 160         DB_LOCK locka, lockr;
 161         int first = 1;
 162
 163         aliases = stack;        /* IDL of all aliases in the database */
 164         curscop = aliases + BDB_IDL_DB_SIZE;    /* Aliases in the current scope */
 165         subscop = curscop + BDB_IDL_DB_SIZE;    /* The current scope */
 166         visited = subscop + BDB_IDL_DB_SIZE;    /* IDs we've seen in this search */
 167         newsubs = visited + BDB_IDL_DB_SIZE;    /* New subtrees we've added */
 168         oldsubs = newsubs + BDB_IDL_DB_SIZE;    /* Subtrees added previously */
 169         tmp = oldsubs + BDB_IDL_DB_SIZE;        /* Scratch space for deref_base() */
 170
 171         /* A copy of subscop, because subscop gets clobbered by
 172          * the bdb_idl_union/intersection routines
 173          */
 174         subscop2 = tmp + BDB_IDL_DB_SIZE;
 175
 176         af.f_choice = LDAP_FILTER_EQUALITY;
 177         af.f_ava = &aa_alias;
 178         af.f_av_desc = slap_schema.si_ad_objectClass;
 179         af.f_av_value = bv_alias;
 180         af.f_next = NULL;
 181
 182         /* Find all aliases in database */
 183         BDB_IDL_ZERO( aliases );
 184         rs->sr_err = bdb_filter_candidates( op, &af, aliases,
 185                 curscop, visited );
 186         if (rs->sr_err != LDAP_SUCCESS) {
 187                 return rs->sr_err;
 188         }
 189         oldsubs[0] = 1;
 190         oldsubs[1] = e->e_id;
 191
 192         BDB_IDL_ZERO( ids );
 193         BDB_IDL_ZERO( visited );
 194         BDB_IDL_ZERO( newsubs );
 195
 196         cursoro = 0;
 197         ido = bdb_idl_first( oldsubs, &cursoro );
 198
 199         for (;;) {
 200                 /* Set curscop to only the aliases in the current scope. Start with
 201                  * all the aliases, obtain the IDL for the current scope, and then
 202                  * get the intersection of these two IDLs. Add the current scope
 203                  * to the cumulative list of candidates.
 204                  */
 205                 BDB_IDL_CPY( curscop, aliases );
 206                 rs->sr_err = bdb_dn2idl( op, e, subscop,
 207                         subscop2+BDB_IDL_DB_SIZE );
 208                 if (first) {
 209                         first = 0;
 210                 } else {
 211                         bdb_cache_return_entry_r (bdb->bi_dbenv, &bdb->bi_cache, e, &locka);
 212                 }
 213                 BDB_IDL_CPY(subscop2, subscop);
 214                 rs->sr_err = bdb_idl_intersection(curscop, subscop);
 215                 bdb_idl_union( ids, subscop2 );
 216
 217                 /* Dereference all of the aliases in the current scope. */
 218                 cursora = 0;
 219                 for (ida = bdb_idl_first(curscop, &cursora); ida != NOID;
 220                         ida = bdb_idl_next(curscop, &cursora))
 221                 {
 222                         ei = NULL;
 223 retry1:
 224                         rs->sr_err = bdb_cache_find_id(op, NULL,
 225                                 ida, &ei, 0, locker, &lockr );
 226                         if (rs->sr_err != LDAP_SUCCESS) {
 227                                 if ( rs->sr_err == DB_LOCK_DEADLOCK ||
 228                                         rs->sr_err == DB_LOCK_NOTGRANTED ) goto retry1;
 229                                 continue;
 230                         }
 231                         a = ei->bei_e;
 232
 233                         /* This should only happen if the curscop IDL has maxed out and
 234                          * turned into a range that spans IDs indiscriminately
 235                          */
 236                         if (!is_entry_alias(a)) {
 237                                 bdb_cache_return_entry_r (bdb->bi_dbenv, &bdb->bi_cache,
 238                                         a, &lockr);
 239                                 continue;
 240                         }
 241
 242                         /* Actually dereference the alias */
 243                         BDB_IDL_ZERO(tmp);
 244                         a = deref_base( op, rs, a, &matched, locker, &lockr,
 245                                 tmp, visited );
 246                         if (a) {
 247                                 /* If the target was not already in our current candidates,
 248                                  * make note of it in the newsubs list. Also
 249                                  * set it in the scopes list so that bdb_search
 250                                  * can check it.
 251                                  */
 252                                 if (bdb_idl_insert(ids, a->e_id) == 0) {
 253                                         bdb_idl_insert(newsubs, a->e_id);
 254                                         bdb_idl_insert(scopes, a->e_id);
 255                                 }
 256                                 bdb_cache_return_entry_r( bdb->bi_dbenv, &bdb->bi_cache,
 257                                         a, &lockr);
 258
 259                         } else if (matched) {
 260                                 /* Alias could not be dereferenced, or it deref'd to
 261                                  * an ID we've already seen. Ignore it.
 262                                  */
 263                                 bdb_cache_return_entry_r( bdb->bi_dbenv, &bdb->bi_cache,
 264                                         matched, &lockr );
 265                                 rs->sr_text = NULL;
 266                         }
 267                 }
 268                 /* If this is a OneLevel search, we're done; oldsubs only had one
 269                  * ID in it. For a Subtree search, oldsubs may be a list of scope IDs.
 270                  */
 271                 if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) break;
 272 nextido:
 273                 ido = bdb_idl_next( oldsubs, &cursoro );
 274
 275                 /* If we're done processing the old scopes, did we add any new
 276                  * scopes in this iteration? If so, go back and do those now.
 277                  */
 278                 if (ido == NOID) {
 279                         if (BDB_IDL_IS_ZERO(newsubs)) break;
 280                         BDB_IDL_CPY(oldsubs, newsubs);
 281                         BDB_IDL_ZERO(newsubs);
 282                         cursoro = 0;
 283                         ido = bdb_idl_first( oldsubs, &cursoro );
 284                 }
 285
 286                 /* Find the entry corresponding to the next scope. If it can't
 287                  * be found, ignore it and move on. This should never happen;
 288                  * we should never see the ID of an entry that doesn't exist.
 289                  * Set the name so that the scope's IDL can be retrieved.
 290                  */
 291                 ei = NULL;
 292 sameido:
 293                 rs->sr_err = bdb_cache_find_id(op, NULL, ido, &ei,
 294                         0, locker, &locka );
 295                 if ( rs->sr_err != LDAP_SUCCESS ) {
 296                         if ( rs->sr_err == DB_LOCK_DEADLOCK ||
 297                                 rs->sr_err == DB_LOCK_NOTGRANTED )
 298                                 goto sameido;
 299                         goto nextido;
 300                 }
 301                 e = ei->bei_e;
 302         }
 303         return rs->sr_err;
 304 }
 305
 306 #define is_sync_protocol(op)    \
 307         ((op)->o_sync_mode & SLAP_SYNC_REFRESH_AND_PERSIST)
 308
 309 #define IS_BDB_REPLACE(type) (( type == LDAP_PSEARCH_BY_DELETE ) || \
 310         ( type == LDAP_PSEARCH_BY_SCOPEOUT ))
 311 #define IS_PSEARCH (op != sop)
 312 #define IS_POST_SEARCH ( op->ors_post_search_id != NOID )
 313
 314 static Operation *
 315 bdb_drop_psearch( Operation *op, ber_int_t msgid )
 316 {
 317         Operation       *ps_list;
 318         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 319
 320         LDAP_LIST_FOREACH ( ps_list, &bdb->bi_psearch_list, o_ps_link ) {
 321                 if ( ps_list->o_connid == op->o_connid ) {
 322                         if ( ps_list->o_msgid == msgid ) {
 323                                 ps_list->o_abandon = 1;
 324                                 LDAP_LIST_REMOVE( ps_list, o_ps_link );
 325                                 ldap_pvt_thread_mutex_lock( &op->o_conn->c_mutex );
 326                                 LDAP_STAILQ_REMOVE( &op->o_conn->c_ops, ps_list,
 327                                         slap_op, o_next );
 328                                 LDAP_STAILQ_NEXT( ps_list, o_next ) = NULL;
 329                                 op->o_conn->c_n_ops_executing--;
 330                                 op->o_conn->c_n_ops_completed++;
 331                                 ldap_pvt_thread_mutex_unlock( &op->o_conn->c_mutex );
 332                                 return ps_list;
 333                         }
 334                 }
 335         }
 336
 337         return NULL;
 338 }
 339
 340 int
 341 bdb_abandon( Operation *op, SlapReply *rs )
 342 {
 343         Operation       *ps;
 344         void            *saved_tmpmemctx;
 345
 346         ps = bdb_drop_psearch( op, op->oq_abandon.rs_msgid );
 347         if ( ps ) {
 348                 saved_tmpmemctx = ps->o_tmpmemctx;
 349
 350                 if (!BER_BVISNULL(&ps->o_req_dn)) {
 351                         slap_sl_free(ps->o_req_dn.bv_val, ps->o_tmpmemctx );
 352                 }
 353                 if (!BER_BVISNULL(&ps->o_req_ndn)) {
 354                         slap_sl_free(ps->o_req_ndn.bv_val, ps->o_tmpmemctx );
 355                 }
 356                 if (!BER_BVISNULL(&ps->ors_filterstr)) {
 357                         ps->o_tmpfree(ps->ors_filterstr.bv_val, ps->o_tmpmemctx);
 358                 }
 359                 if (ps->ors_filter != NULL) {
 360                         filter_free_x(ps, ps->ors_filter);
 361                 }
 362                 if (ps->ors_attrs != NULL) {
 363                         ps->o_tmpfree(ps->ors_attrs, ps->o_tmpmemctx);
 364                 }
 365
 366                 slap_op_free ( ps );
 367
 368                 if ( saved_tmpmemctx ) {
 369                         slap_sl_mem_destroy( NULL, saved_tmpmemctx );
 370                 }
 371
 372                 return LDAP_SUCCESS;
 373         }
 374         return LDAP_UNAVAILABLE;
 375 }
 376
 377 int
 378 bdb_cancel( Operation *op, SlapReply *rs )
 379 {
 380         Operation       *ps;
 381         void            *saved_tmpmemctx;
 382
 383         ps = bdb_drop_psearch( op, op->oq_cancel.rs_msgid );
 384         if ( ps ) {
 385                 saved_tmpmemctx = ps->o_tmpmemctx;
 386
 387                 rs->sr_err = LDAP_CANCELLED;
 388                 send_ldap_result( ps, rs );
 389
 390                 if (!BER_BVISNULL(&ps->o_req_dn)) {
 391                         slap_sl_free(ps->o_req_dn.bv_val, ps->o_tmpmemctx );
 392                 }
 393                 if (!BER_BVISNULL(&ps->o_req_ndn)) {
 394                         slap_sl_free(ps->o_req_ndn.bv_val, ps->o_tmpmemctx );
 395                 }
 396                 if (!BER_BVISNULL(&ps->ors_filterstr)) {
 397                         ps->o_tmpfree(ps->ors_filterstr.bv_val, ps->o_tmpmemctx);
 398                 }
 399                 if (ps->ors_filter != NULL) {
 400                         filter_free_x(ps, ps->ors_filter);
 401                 }
 402                 if (ps->ors_attrs != NULL) {
 403                         ps->o_tmpfree(ps->ors_attrs, ps->o_tmpmemctx);
 404                 }
 405
 406                 slap_op_free ( ps );
 407
 408                 if ( saved_tmpmemctx ) {
 409                         slap_sl_mem_destroy( NULL, saved_tmpmemctx );
 410                 }
 411
 412                 return LDAP_SUCCESS;
 413         }
 414         return LDAP_UNAVAILABLE;
 415 }
 416
 417 int bdb_search( Operation *op, SlapReply *rs )
 418 {
 419         int rc;
 420         struct pc_entry *pce = NULL;
 421         struct pc_entry *tmp_pce = NULL;
 422         Entry ps_e = {0};
 423         Attribute *a;
 424
 425         ps_e.e_private = NULL;
 426         ldap_pvt_thread_mutex_init( &op->o_pcmutex );
 427         LDAP_TAILQ_INIT( &op->o_ps_pre_candidates );
 428         LDAP_TAILQ_INIT( &op->o_ps_post_candidates );
 429
 430         op->ors_post_search_id = NOID;
 431         rc = bdb_do_search( op, rs, op, NULL, 0 );
 432
 433         ldap_pvt_thread_mutex_lock( &op->o_pcmutex );
 434         pce = LDAP_TAILQ_FIRST( &op->o_ps_post_candidates );
 435         ldap_pvt_thread_mutex_unlock( &op->o_pcmutex );
 436
 437         while ( rc == LDAP_SUCCESS && pce &&
 438                         op->o_sync_mode & SLAP_SYNC_REFRESH_AND_PERSIST ) {
 439
 440                 ps_e.e_id = op->ors_post_search_id = pce->pc_id;
 441                 if ( op->o_sync_csn.bv_val ) {
 442                         ch_free( op->o_sync_csn.bv_val );
 443                         op->o_sync_csn.bv_val = NULL;
 444                 }
 445                 ber_dupbv( &op->o_sync_csn, &pce->pc_csn );
 446                 ber_dupbv( &ps_e.e_name, &pce->pc_ename );
 447                 ber_dupbv( &ps_e.e_nname, &pce->pc_enname );
 448                 a = ch_calloc( 1, sizeof( Attribute ));
 449                 a->a_desc = slap_schema.si_ad_entryUUID;
 450                 a->a_vals = ch_calloc( 2, sizeof( struct berval ));
 451                 ber_dupbv( &a->a_vals[0], &pce->pc_entryUUID );
 452                 a->a_nvals = a->a_vals;
 453                 a->a_next = NULL;
 454                 ps_e.e_attrs = a;
 455
 456                 rc = bdb_do_search( op, rs, op, &ps_e, 0 );
 457
 458                 tmp_pce = pce;
 459                 ldap_pvt_thread_mutex_lock( &op->o_pcmutex );
 460                 pce = LDAP_TAILQ_NEXT( pce, pc_link );
 461                 LDAP_TAILQ_REMOVE( &op->o_ps_post_candidates, tmp_pce, pc_link );
 462                 ldap_pvt_thread_mutex_unlock( &op->o_pcmutex );
 463
 464                 ch_free( tmp_pce->pc_csn.bv_val );
 465                 ch_free( tmp_pce->pc_entryUUID.bv_val );
 466                 ch_free( tmp_pce->pc_ename.bv_val );
 467                 ch_free( tmp_pce->pc_enname.bv_val );
 468                 ch_free( tmp_pce );
 469                 entry_clean( &ps_e );
 470         }
 471         return rc;
 472 }
 473
 474 #define BDB_PSEARCH_MAX_WAIT 3
 475 int bdb_psearch( Operation *op, SlapReply *rs, Operation *sop,
 476         Entry *ps_e, int ps_type )
 477 {
 478         int     rc;
 479         struct pc_entry *pce = NULL;
 480         struct pc_entry *p = NULL;
 481         int num_retries = 0;
 482
 483         op->ors_post_search_id = NOID;
 484
 485         switch (ps_type) {
 486         case LDAP_PSEARCH_BY_PREMODIFY:
 487         case LDAP_PSEARCH_BY_PREDELETE:
 488
 489                 if ( !op->o_ps_send_wait ) {
 490                         if ( sop->o_refresh_in_progress ) {
 491                                 pce = (struct pc_entry *) ch_calloc(
 492                                                         1, sizeof( struct pc_entry ));
 493                                 pce->pc_id = ps_e->e_id;
 494                                 ldap_pvt_thread_mutex_lock( &sop->o_pcmutex );
 495                                 if ( LDAP_TAILQ_EMPTY( &sop->o_ps_pre_candidates )) {
 496                                         LDAP_TAILQ_INSERT_HEAD(
 497                                                         &sop->o_ps_pre_candidates, pce, pc_link );
 498                                 } else {
 499                                         LDAP_TAILQ_FOREACH( p,
 500                                                         &sop->o_ps_pre_candidates, pc_link ) {
 501                                                 if ( p->pc_id > pce->pc_id )
 502                                                         break;
 503                                         }
 504
 505                                         if ( p ) {
 506                                                 LDAP_TAILQ_INSERT_BEFORE( p, pce, pc_link );
 507                                         } else {
 508                                                 LDAP_TAILQ_INSERT_TAIL(
 509                                                                 &sop->o_ps_pre_candidates,
 510                                                                 pce, pc_link );
 511                                         }
 512                                 }
 513                                 ldap_pvt_thread_mutex_unlock( &sop->o_pcmutex );
 514                         } else {
 515                                 rc = bdb_do_search( op, rs, sop, ps_e, ps_type );
 516                                 return rc;
 517                         }
 518                 } else {
 519                         pce = op->o_ps_send_wait;
 520                 }
 521
 522                 /* Wait until refresh search send the entry */
 523                 while ( !pce->pc_sent ) {
 524                         if ( sop->o_refresh_in_progress ) {
 525                                 if ( num_retries == BDB_PSEARCH_MAX_WAIT ) {
 526                                         op->o_ps_send_wait = pce;
 527                                         return LDAP_BUSY;
 528                                 }
 529                                 ldap_pvt_thread_yield();
 530                                 bdb_trans_backoff( ++num_retries );
 531                         } else {
 532                                 break;
 533                         }
 534                 }
 535
 536                 op->o_ps_send_wait = NULL;
 537
 538                 if ( !sop->o_refresh_in_progress && !pce->pc_sent ) {
 539                         /* refresh ended without processing pce */
 540                         /* need to perform psearch for ps_e */
 541                         ldap_pvt_thread_mutex_lock( &sop->o_pcmutex );
 542                         LDAP_TAILQ_REMOVE( &sop->o_ps_pre_candidates, pce, pc_link );
 543                         ldap_pvt_thread_mutex_unlock( &sop->o_pcmutex );
 544                         ch_free( pce );
 545                         rc = bdb_do_search( op, rs, sop, ps_e, ps_type );
 546                         return rc;
 547                 } else {
 548                         /* the pce entry was sent in the refresh phase */
 549                         if ( ps_type == LDAP_PSEARCH_BY_PREMODIFY ) {
 550                                 struct psid_entry* psid_e;
 551                                 psid_e = (struct psid_entry *) ch_calloc(1,
 552                                                         sizeof(struct psid_entry));
 553                                 psid_e->ps_op = sop;
 554                                 LDAP_LIST_INSERT_HEAD( &op->o_pm_list, psid_e, ps_link );
 555                         }
 556
 557                         ldap_pvt_thread_mutex_lock( &sop->o_pcmutex );
 558                         LDAP_TAILQ_REMOVE( &sop->o_ps_pre_candidates, pce, pc_link );
 559                         ldap_pvt_thread_mutex_unlock( &sop->o_pcmutex );
 560                         ch_free( pce );
 561                         return LDAP_SUCCESS;
 562                 }
 563                 break;
 564         case LDAP_PSEARCH_BY_DELETE:
 565         case LDAP_PSEARCH_BY_SCOPEOUT:
 566         case LDAP_PSEARCH_BY_ADD:
 567         case LDAP_PSEARCH_BY_MODIFY:
 568                 ldap_pvt_thread_mutex_lock( &op->o_pcmutex );
 569                 if ( sop->o_refresh_in_progress ||
 570                                 !LDAP_TAILQ_EMPTY( &sop->o_ps_post_candidates )) {
 571                         pce = (struct pc_entry *) ch_calloc( 1, sizeof( struct pc_entry ));
 572                         pce->pc_id = ps_e->e_id;
 573                         ber_dupbv( &pce->pc_csn, &op->o_sync_csn );
 574                         if ( ps_type == LDAP_PSEARCH_BY_DELETE ) {
 575                                 Attribute *a;
 576                                 for ( a = ps_e->e_attrs; a != NULL; a = a->a_next ) {
 577                                         AttributeDescription *desc = a->a_desc;
 578                                         if ( desc == slap_schema.si_ad_entryUUID ) {
 579                                                 ber_dupbv( &pce->pc_entryUUID, &a->a_nvals[0] );
 580                                         }
 581                                 }
 582                         }
 583                         ber_dupbv( &pce->pc_ename, &ps_e->e_name );
 584                         ber_dupbv( &pce->pc_enname, &ps_e->e_nname );
 585                         LDAP_TAILQ_INSERT_TAIL( &sop->o_ps_post_candidates, pce, pc_link );
 586                         ldap_pvt_thread_mutex_unlock( &op->o_pcmutex );
 587                 } else {
 588                         ldap_pvt_thread_mutex_unlock( &op->o_pcmutex );
 589                         rc = bdb_do_search( op, rs, sop, ps_e, ps_type );
 590                         return rc;
 591                 }
 592                 break;
 593         default:
 594                 Debug( LDAP_DEBUG_TRACE, "do_psearch: invalid psearch type\n",
 595                                 0, 0, 0 );
 596                 return LDAP_OTHER;
 597         }
 598 }
 599
 600 /* For persistent searches, op is the currently executing operation,
 601  * sop is the persistent search. For regular searches, sop = op.
 602  */
 603 int
 604 bdb_do_search( Operation *op, SlapReply *rs, Operation *sop,
 605         Entry *ps_e, int ps_type )
 606 {
 607         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 608         time_t          stoptime;
 609         ID              id, cursor;
 610         ID              candidates[BDB_IDL_UM_SIZE];
 611         ID              scopes[BDB_IDL_DB_SIZE];
 612         Entry           *e = NULL, base, e_root = {0};
 613         Entry           *matched = NULL;
 614         EntryInfo       *ei, ei_root = {0};
 615         struct berval   realbase = BER_BVNULL;
 616         int             manageDSAit;
 617         int             tentries = 0;
 618         ID              lastid = NOID;
 619         AttributeName   *attrs;
 620
 621         Filter          contextcsnand, contextcsnle, cookief, csnfnot,
 622                         csnfeq, csnfand, csnfge;
 623         AttributeAssertion aa_ge, aa_eq, aa_le;
 624         struct berval   *search_context_csn = NULL;
 625         DB_LOCK         ctxcsn_lock;
 626         LDAPControl     *ctrls[SLAP_MAX_RESPONSE_CONTROLS];
 627         int             num_ctrls = 0;
 628         AttributeName   uuid_attr[2];
 629         int             rc_sync = 0;
 630         int             entry_sync_state = -1;
 631         AttributeName   null_attr;
 632         int             no_sync_state_change = 0;
 633
 634         u_int32_t       locker = 0;
 635         DB_LOCK         lock;
 636
 637         Operation       *ps_list;
 638         int                     sync_send_present_mode = 1;
 639         int                     match;
 640         MatchingRule *mr;
 641         const char *text;
 642         int                     slog_found = 0;
 643
 644         struct pc_entry *pce = NULL;
 645         BerVarray       syncUUID_set = NULL;
 646         int                     syncUUID_set_cnt = 0;
 647
 648         struct  bdb_op_info     *opinfo = NULL;
 649         DB_TXN                  *ltid = NULL;
 650
 651         Debug( LDAP_DEBUG_TRACE, "=> bdb_search\n", 0, 0, 0);
 652         attrs = sop->oq_search.rs_attrs;
 653
 654         opinfo = (struct bdb_op_info *) op->o_private;
 655
 656         if ( !IS_POST_SEARCH && !IS_PSEARCH &&
 657                         sop->o_sync_mode & SLAP_SYNC_REFRESH_AND_PERSIST ) {
 658                 struct slap_session_entry *sent;
 659                 if ( sop->o_sync_state.sid >= 0 ) {
 660                         LDAP_LIST_FOREACH( sent, &bdb->bi_session_list, se_link ) {
 661                                 if ( sent->se_id == sop->o_sync_state.sid ) {
 662                                         sop->o_sync_slog_size = sent->se_size;
 663                                         break;
 664                                 }
 665                         }
 666                 }
 667         }
 668
 669         /* psearch needs to be registered before refresh begins */
 670         if ( !IS_POST_SEARCH && !IS_PSEARCH &&
 671                         sop->o_sync_mode & SLAP_SYNC_PERSIST ) {
 672                 sop->o_refresh_in_progress = 1;
 673                 ldap_pvt_thread_rdwr_wlock( &bdb->bi_pslist_rwlock );
 674                 LDAP_LIST_INSERT_HEAD( &bdb->bi_psearch_list, sop, o_ps_link );
 675                 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_pslist_rwlock );
 676
 677         } else if ( !IS_POST_SEARCH && !IS_PSEARCH &&
 678                                 sop->o_sync_mode & SLAP_SYNC_REFRESH_AND_PERSIST
 679                                 && sop->o_sync_slog_size >= 0 )
 680         {
 681                 ldap_pvt_thread_rdwr_wlock( &bdb->bi_pslist_rwlock );
 682                 LDAP_LIST_FOREACH( ps_list, &bdb->bi_psearch_list, o_ps_link ) {
 683                         if ( ps_list->o_sync_slog_size >= 0 ) {
 684                                 if ( ps_list->o_sync_state.sid == sop->o_sync_state.sid ) {
 685                                         slog_found = 1;
 686                                         break;
 687                                 }
 688                         }
 689                 }
 690
 691                 if ( slog_found ) {
 692                         if ( ps_list->o_sync_slog_omitcsn.bv_len != 0 ) {
 693                                 mr = slap_schema.si_ad_entryCSN->ad_type->sat_ordering;
 694                                 if ( sop->o_sync_state.ctxcsn &&
 695                                         sop->o_sync_state.ctxcsn->bv_val != NULL )
 696                                 {
 697                                         value_match( &match, slap_schema.si_ad_entryCSN, mr,
 698                                                 SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX,
 699                                                 sop->o_sync_state.ctxcsn,
 700                                                 &ps_list->o_sync_slog_omitcsn,
 701                                                 &text );
 702                                 } else {
 703                                         match = -1;
 704                                 }
 705                                 if ( match >= 0 ) {
 706                                         sync_send_present_mode = 0;
 707                                 }
 708                         } else {
 709                                 sync_send_present_mode = 0;
 710                         }
 711                 } else if ( sop->o_sync_slog_size >= 0 ) {
 712                         LDAP_LIST_INSERT_HEAD( &bdb->bi_psearch_list, sop, o_ps_link );
 713                 } else {
 714                         sop->o_sync_state.sid = -1;
 715                 }
 716                 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_pslist_rwlock );
 717         }
 718
 719         null_attr.an_desc = NULL;
 720         null_attr.an_oc = NULL;
 721         null_attr.an_oc_exclude = 0;
 722         BER_BVZERO( &null_attr.an_name );
 723
 724         for( num_ctrls = 0; num_ctrls < SLAP_MAX_RESPONSE_CONTROLS; num_ctrls++ ) {
 725                 ctrls[num_ctrls] = NULL;
 726         }
 727         num_ctrls = 0;
 728
 729         if ( IS_PSEARCH && IS_BDB_REPLACE(ps_type)) {
 730                 attrs = uuid_attr;
 731                 attrs[0].an_desc = NULL;
 732                 attrs[0].an_oc = NULL;
 733                 attrs[0].an_oc_exclude = 0;
 734                 BER_BVZERO( &attrs[0].an_name );
 735         }
 736
 737         manageDSAit = get_manageDSAit( sop );
 738
 739         /* Sync control overrides manageDSAit */
 740         if ( !IS_PSEARCH && sop->o_sync_mode & SLAP_SYNC_REFRESH ) {
 741                 if ( manageDSAit == SLAP_NO_CONTROL ) {
 742                         manageDSAit = SLAP_CRITICAL_CONTROL;
 743                 }
 744         } else if ( IS_PSEARCH ) {
 745                 if ( manageDSAit == SLAP_NO_CONTROL ) {
 746                         manageDSAit = SLAP_CRITICAL_CONTROL;
 747                 }
 748         }
 749
 750         if ( opinfo && opinfo->boi_txn ) {
 751                 ltid = opinfo->boi_txn;
 752                 locker = TXN_ID( ltid );
 753         } else {
 754                 rs->sr_err = LOCK_ID( bdb->bi_dbenv, &locker );
 755
 756                 switch(rs->sr_err) {
 757                 case 0:
 758                         break;
 759                 default:
 760                         send_ldap_error( sop, rs, LDAP_OTHER, "internal error" );
 761                         return rs->sr_err;
 762                 }
 763         }
 764
 765         if ( IS_POST_SEARCH ) {
 766                 cursor = 0;
 767                 candidates[0] = 1;
 768                 candidates[1] = op->ors_post_search_id;
 769                 search_context_csn = ber_dupbv( NULL, &op->o_sync_csn );
 770                 goto loop_start;
 771         }
 772
 773         if ( sop->o_req_ndn.bv_len == 0 ) {
 774                 /* DIT root special case */
 775                 ei_root.bei_e = &e_root;
 776                 ei_root.bei_parent = &ei_root;
 777                 e_root.e_private = &ei_root;
 778                 e_root.e_id = 0;
 779                 BER_BVSTR( &e_root.e_nname, "" );
 780                 BER_BVSTR( &e_root.e_name, "" );
 781                 ei = &ei_root;
 782                 rs->sr_err = LDAP_SUCCESS;
 783         } else {
 784 dn2entry_retry:
 785                 /* get entry with reader lock */
 786                 rs->sr_err = bdb_dn2entry( op, ltid, &sop->o_req_ndn, &ei,
 787                         1, locker, &lock );
 788         }
 789
 790         switch(rs->sr_err) {
 791         case DB_NOTFOUND:
 792                 matched = ei->bei_e;
 793                 break;
 794         case 0:
 795                 e = ei->bei_e;
 796                 break;
 797         case LDAP_BUSY:
 798                 send_ldap_error( sop, rs, LDAP_BUSY, "ldap server busy" );
 799                 if ( !opinfo )
 800                         LOCK_ID_FREE (bdb->bi_dbenv, locker );
 801                 return LDAP_BUSY;
 802         case DB_LOCK_DEADLOCK:
 803         case DB_LOCK_NOTGRANTED:
 804                 goto dn2entry_retry;
 805         default:
 806                 send_ldap_error( sop, rs, LDAP_OTHER, "internal error" );
 807                 if ( !opinfo )
 808                         LOCK_ID_FREE (bdb->bi_dbenv, locker );
 809                 return rs->sr_err;
 810         }
 811
 812         if ( e && (op->ors_deref & LDAP_DEREF_FINDING) && is_entry_alias(e) ) {
 813                 BDB_IDL_ZERO(candidates);
 814                 e = deref_base( op, rs, e, &matched, locker, &lock,
 815                         candidates, NULL );
 816         }
 817
 818         if ( e == NULL ) {
 819                 struct berval matched_dn = BER_BVNULL;
 820
 821                 if ( matched != NULL ) {
 822                         BerVarray erefs;
 823                         ber_dupbv( &matched_dn, &matched->e_name );
 824
 825                         erefs = is_entry_referral( matched )
 826                                 ? get_entry_referrals( op, matched )
 827                                 : NULL;
 828
 829                         bdb_cache_return_entry_r (bdb->bi_dbenv, &bdb->bi_cache,
 830                                 matched, &lock);
 831                         matched = NULL;
 832
 833                         if( erefs ) {
 834                                 rs->sr_ref = referral_rewrite( erefs, &matched_dn,
 835                                         &sop->o_req_dn, sop->oq_search.rs_scope );
 836                                 ber_bvarray_free( erefs );
 837                         }
 838
 839                 } else {
 840                         rs->sr_ref = referral_rewrite( default_referral,
 841                                 NULL, &sop->o_req_dn, sop->oq_search.rs_scope );
 842                 }
 843
 844                 rs->sr_err = LDAP_REFERRAL;
 845                 rs->sr_matched = matched_dn.bv_val;
 846                 send_ldap_result( sop, rs );
 847
 848                 if ( !opinfo )
 849                         LOCK_ID_FREE (bdb->bi_dbenv, locker );
 850                 if ( rs->sr_ref ) {
 851                         ber_bvarray_free( rs->sr_ref );
 852                         rs->sr_ref = NULL;
 853                 }
 854                 if ( matched_dn.bv_val ) {
 855                         ber_memfree( matched_dn.bv_val );
 856                         rs->sr_matched = NULL;
 857                 }
 858                 return rs->sr_err;
 859         }
 860
 861         if ( !manageDSAit && e != &e_root && is_entry_referral( e ) ) {
 862                 /* entry is a referral, don't allow add */
 863                 struct berval matched_dn;
 864                 BerVarray erefs;
 865
 866                 ber_dupbv( &matched_dn, &e->e_name );
 867                 erefs = get_entry_referrals( op, e );
 868
 869                 bdb_cache_return_entry_r( bdb->bi_dbenv, &bdb->bi_cache, e, &lock );
 870                 e = NULL;
 871
 872                 if( erefs ) {
 873                         rs->sr_ref = referral_rewrite( erefs, &matched_dn,
 874                                 &sop->o_req_dn, sop->oq_search.rs_scope );
 875                         ber_bvarray_free( erefs );
 876                 }
 877
 878                 Debug( LDAP_DEBUG_TRACE, "bdb_search: entry is referral\n",
 879                         0, 0, 0 );
 880
 881                 if (!rs->sr_ref) rs->sr_text = "bad_referral object";
 882                 rs->sr_err = LDAP_REFERRAL;
 883                 rs->sr_matched = matched_dn.bv_val;
 884                 send_ldap_result( sop, rs );
 885
 886                 if ( !opinfo )
 887                         LOCK_ID_FREE (bdb->bi_dbenv, locker );
 888                 ber_bvarray_free( rs->sr_ref );
 889                 rs->sr_ref = NULL;
 890                 ber_memfree( matched_dn.bv_val );
 891                 rs->sr_matched = NULL;
 892                 return 1;
 893         }
 894
 895         if ( get_assert( op ) &&
 896                 ( test_filter( op, e, get_assertion( op )) != LDAP_COMPARE_TRUE ))
 897         {
 898                 rs->sr_err = LDAP_ASSERTION_FAILED;
 899                 send_ldap_result( sop, rs );
 900                 return 1;
 901         }
 902
 903         /* compute it anyway; root does not use it */
 904         stoptime = op->o_time + sop->ors_tlimit;
 905
 906         /* need normalized dn below */
 907         ber_dupbv( &realbase, &e->e_nname );
 908
 909         /* Copy info to base, must free entry before accessing the database
 910          * in search_candidates, to avoid deadlocks.
 911          */
 912         base.e_private = e->e_private;
 913         base.e_nname = realbase;
 914         base.e_id = e->e_id;
 915
 916         if ( e != &e_root ) {
 917                 bdb_cache_return_entry_r(bdb->bi_dbenv, &bdb->bi_cache, e, &lock);
 918         }
 919         e = NULL;
 920
 921         if ( !IS_PSEARCH ) {
 922                 rs->sr_err = bdb_get_commit_csn( sop, rs, &search_context_csn,
 923                         locker, &ctxcsn_lock );
 924
 925                 if ( rs->sr_err != LDAP_SUCCESS ) {
 926                         send_ldap_error( sop, rs, rs->sr_err,
 927                                 "error in csn management in search" );
 928                         goto done;
 929                 }
 930
 931                 if ( sop->o_sync_mode != SLAP_SYNC_NONE &&
 932                         sop->o_sync_state.ctxcsn &&
 933                         sop->o_sync_state.ctxcsn->bv_val &&
 934                         ber_bvcmp( &sop->o_sync_state.ctxcsn[0], search_context_csn ) == 0 )
 935                 {
 936                         bdb_cache_entry_db_unlock( bdb->bi_dbenv, &ctxcsn_lock );
 937                         goto nochange;
 938                 }
 939         } else {
 940                 search_context_csn = ber_dupbv( NULL, &op->o_sync_csn );
 941         }
 942
 943         /* select candidates */
 944         if ( sop->oq_search.rs_scope == LDAP_SCOPE_BASE ) {
 945                 rs->sr_err = base_candidate( op->o_bd, &base, candidates );
 946
 947         } else {
 948                 BDB_IDL_ZERO( candidates );
 949                 BDB_IDL_ZERO( scopes );
 950                 rs->sr_err = search_candidates( op, sop, rs, &base,
 951                         locker, candidates, scopes );
 952         }
 953
 954         if ( !IS_PSEARCH && sop->o_sync_mode != SLAP_SYNC_NONE ) {
 955                 bdb_cache_entry_db_unlock( bdb->bi_dbenv, &ctxcsn_lock );
 956         }
 957
 958         /* start cursor at beginning of candidates.
 959          */
 960         cursor = 0;
 961         if (IS_PSEARCH) {
 962                 if ( !BDB_IDL_IS_RANGE( candidates ) ) {
 963                         cursor = bdb_idl_search( candidates, ps_e->e_id );
 964                         if ( candidates[cursor] != ps_e->e_id ) {
 965                                 rs->sr_err = LDAP_SUCCESS;
 966                                 goto done;
 967                         }
 968                 } else if ( ps_e->e_id < BDB_IDL_RANGE_FIRST( candidates ) ||
 969                         ps_e->e_id > BDB_IDL_RANGE_LAST( candidates ))
 970                 {
 971                         rs->sr_err = LDAP_SUCCESS;
 972                         goto done;
 973                 }
 974                 candidates[0] = 1;
 975                 candidates[1] = ps_e->e_id;
 976         }
 977
 978         if ( candidates[0] == 0 ) {
 979                 Debug( LDAP_DEBUG_TRACE, "bdb_search: no candidates\n",
 980                         0, 0, 0 );
 981
 982                 goto nochange;
 983         }
 984
 985         /* if not root and candidates exceed to-be-checked entries, abort */
 986         if ( sop->ors_limit     /* isroot == FALSE */ &&
 987                 sop->ors_limit->lms_s_unchecked != -1 &&
 988                 BDB_IDL_N(candidates) > (unsigned) sop->ors_limit->lms_s_unchecked )
 989         {
 990                 rs->sr_err = LDAP_ADMINLIMIT_EXCEEDED;
 991                 send_ldap_result( sop, rs );
 992                 rs->sr_err = LDAP_SUCCESS;
 993                 goto done;
 994         }
 995
 996         if ( sop->ors_limit == NULL     /* isroot == TRUE */ ||
 997                 !sop->ors_limit->lms_s_pr_hide )
 998         {
 999                 tentries = BDB_IDL_N(candidates);
1000         }
1001
1002         if ( get_pagedresults( sop ) > SLAP_NO_CONTROL ) {
1003                 /* deferred cookie parsing */
1004                 rs->sr_err = parse_paged_cookie( sop, rs );
1005                 if ( rs->sr_err != LDAP_SUCCESS ) {
1006                         send_ldap_result( sop, rs );
1007                         goto done;
1008                 }
1009
1010                 if ( (ID)( sop->o_pagedresults_state.ps_cookie ) == 0 ) {
1011                         id = bdb_idl_first( candidates, &cursor );
1012
1013                 } else {
1014                         if ( sop->o_pagedresults_size == 0 ) {
1015                                 rs->sr_err = LDAP_SUCCESS;
1016                                 rs->sr_text = "search abandoned by pagedResult size=0";
1017                                 send_ldap_result( sop, rs );
1018                                 goto done;
1019                         }
1020                         for ( id = bdb_idl_first( candidates, &cursor );
1021                                 id != NOID &&
1022                                         id <= (ID)( sop->o_pagedresults_state.ps_cookie );
1023                                 id = bdb_idl_next( candidates, &cursor ) )
1024                         {
1025                                 /* empty */;
1026                         }
1027                 }
1028
1029                 if ( cursor == NOID ) {
1030                         Debug( LDAP_DEBUG_TRACE,
1031                                 "bdb_search: no paged results candidates\n",
1032                                 0, 0, 0 );
1033                         send_paged_response( sop, rs, &lastid, 0 );
1034
1035                         rs->sr_err = LDAP_OTHER;
1036                         goto done;
1037                 }
1038                 goto loop_begin;
1039         }
1040
1041         if (( sop->o_sync_mode & SLAP_SYNC_REFRESH ) || IS_PSEARCH ) {
1042                 int match;
1043
1044                 cookief.f_choice = LDAP_FILTER_AND;
1045                 cookief.f_and = &csnfnot;
1046                 cookief.f_next = NULL;
1047
1048                 csnfnot.f_choice = LDAP_FILTER_NOT;
1049                 csnfnot.f_not = &csnfeq;
1050                 csnfnot.f_next = &csnfand;
1051
1052                 csnfeq.f_choice = LDAP_FILTER_EQUALITY;
1053                 csnfeq.f_ava = &aa_eq;
1054                 csnfeq.f_av_desc = slap_schema.si_ad_entryCSN;
1055                 if ( sop->o_sync_state.ctxcsn != NULL ) {
1056                         csnfeq.f_av_value = *sop->o_sync_state.ctxcsn;
1057                 } else {
1058                         csnfeq.f_av_value = slap_empty_bv;
1059                 }
1060
1061                 csnfand.f_choice = LDAP_FILTER_AND;
1062                 csnfand.f_and = &csnfge;
1063                 csnfand.f_next = NULL;
1064
1065                 csnfge.f_choice = LDAP_FILTER_GE;
1066                 csnfge.f_ava = &aa_ge;
1067                 csnfge.f_av_desc = slap_schema.si_ad_entryCSN;
1068                 if ( sop->o_sync_state.ctxcsn != NULL ) {
1069                         csnfge.f_av_value = *sop->o_sync_state.ctxcsn;
1070                 } else {
1071                         csnfge.f_av_value = slap_empty_bv;
1072                 }
1073
1074                 if ( search_context_csn && !IS_PSEARCH ) {
1075                         csnfge.f_next = &contextcsnand;
1076
1077                         contextcsnand.f_choice = LDAP_FILTER_AND;
1078                         contextcsnand.f_and = &contextcsnle;
1079                         contextcsnand.f_next = NULL;
1080
1081                         contextcsnle.f_choice = LDAP_FILTER_LE;
1082                         contextcsnle.f_ava = &aa_le;
1083                         contextcsnle.f_av_desc = slap_schema.si_ad_entryCSN;
1084                         contextcsnle.f_av_value = *search_context_csn;
1085                         contextcsnle.f_next = sop->oq_search.rs_filter;
1086
1087                         mr = slap_schema.si_ad_entryCSN->ad_type->sat_ordering;
1088                         if ( sop->o_sync_state.ctxcsn &&
1089                                 sop->o_sync_state.ctxcsn->bv_val != NULL )
1090                         {
1091                                 value_match( &match, slap_schema.si_ad_entryCSN, mr,
1092                                                 SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX,
1093                                                 &sop->o_sync_state.ctxcsn[0], search_context_csn,
1094                                                 &text );
1095                         } else {
1096                                 match = -1;
1097                         }
1098                         no_sync_state_change = ( match >= 0 );
1099                 } else {
1100                         csnfge.f_next = sop->oq_search.rs_filter;
1101                 }
1102         }
1103
1104 loop_start:
1105
1106         for ( id = bdb_idl_first( candidates, &cursor );
1107                   id != NOID && !no_sync_state_change;
1108                 id = bdb_idl_next( candidates, &cursor ) )
1109         {
1110                 int scopeok = 0;
1111                 ID* idhole = NULL;
1112
1113 loop_begin:
1114
1115                 if ( !IS_POST_SEARCH ) {
1116                         idhole = (ID*) avl_find( sop->o_psearch_finished,
1117                                                                          (caddr_t)&id, bdb_pfid_cmp );
1118                         if ( idhole ) {
1119                                 avl_delete( &sop->o_psearch_finished,
1120                                                         (caddr_t)idhole, bdb_pfid_cmp );
1121                                 sop->o_tmpfree( idhole, sop->o_tmpmemctx );
1122                                 goto loop_continue;
1123                         }
1124
1125                         if ( sop->o_refresh_in_progress ) {
1126                                 ldap_pvt_thread_mutex_lock( &sop->o_pcmutex );
1127                                 pce = LDAP_TAILQ_FIRST( &sop->o_ps_pre_candidates );
1128                                 while ( pce && pce->pc_sent ) {
1129                                         pce = LDAP_TAILQ_NEXT( pce, pc_link );
1130                                 }
1131                                 ldap_pvt_thread_mutex_unlock( &sop->o_pcmutex );
1132                                 if ( pce ) {
1133                                         ID pos;
1134                                         if ( BDB_IDL_IS_RANGE( candidates ) ) {
1135                                                 if ( pce->pc_id >= candidates[1] &&
1136                                                          pce->pc_id <= candidates[2] &&
1137                                                          pce->pc_id > cursor-1 ) {
1138                                                         id = pce->pc_id;
1139                                                         cursor--;
1140                                                         avl_insert( &sop->o_psearch_finished,
1141                                                                                 (caddr_t)bdb_id_dup( sop, &pce->pc_id ),
1142                                                                                 bdb_pfid_cmp, avl_dup_error );
1143                                                 } else {
1144                                                         pce->pc_sent = 1;
1145                                                 }
1146                                         } else {
1147                                                 pos = bdb_idl_search(candidates, pce->pc_id);
1148                                                 if ( pos > cursor-1 && pos <= candidates[0] ) {
1149                                                         id = pce->pc_id;
1150                                                         cursor--;
1151                                                         avl_insert( &sop->o_psearch_finished,
1152                                                                                 (caddr_t)bdb_id_dup( sop, &pce->pc_id ),
1153                                                                                 bdb_pfid_cmp, avl_dup_error );
1154                                                 } else {
1155                                                         pce->pc_sent = 1;
1156                                                 }
1157                                         }
1158                                 }
1159                         }
1160                 }
1161
1162                 /* check for abandon */
1163                 if ( sop->o_abandon ) {
1164                         if ( sop != op ) {
1165                                 bdb_drop_psearch( sop, sop->o_msgid );
1166                         }
1167                         rs->sr_err = LDAP_SUCCESS;
1168                         goto done;
1169                 }
1170
1171                 if ( sop->o_cancel ) {
1172                         assert( sop->o_cancel == SLAP_CANCEL_REQ );
1173                         rs->sr_err = LDAP_CANCELLED;
1174                         send_ldap_result( sop, rs );
1175                         sop->o_cancel = SLAP_CANCEL_ACK;
1176                         rs->sr_err = LDAP_SUCCESS;
1177                         goto done;
1178                 }
1179
1180                 /* check time limit */
1181                 if ( sop->ors_tlimit != SLAP_NO_LIMIT
1182                                 && slap_get_time() > stoptime )
1183                 {
1184                         rs->sr_err = LDAP_TIMELIMIT_EXCEEDED;
1185                         rs->sr_ref = rs->sr_v2ref;
1186                         send_ldap_result( sop, rs );
1187                         rs->sr_err = LDAP_SUCCESS;
1188                         goto done;
1189                 }
1190
1191                 if (!IS_PSEARCH) {
1192 id2entry_retry:
1193                         /* get the entry with reader lock */
1194                         ei = NULL;
1195                         rs->sr_err = bdb_cache_find_id( op, ltid,
1196                                 id, &ei, 0, locker, &lock );
1197
1198                         if (rs->sr_err == LDAP_BUSY) {
1199                                 rs->sr_text = "ldap server busy";
1200                                 send_ldap_result( sop, rs );
1201                                 goto done;
1202
1203                         } else if ( rs->sr_err == DB_LOCK_DEADLOCK
1204                                 || rs->sr_err == DB_LOCK_NOTGRANTED )
1205                         {
1206                                 goto id2entry_retry;
1207                         }
1208
1209                         if ( ei && rs->sr_err == LDAP_SUCCESS ) {
1210                                 e = ei->bei_e;
1211                         } else {
1212                                 e = NULL;
1213                         }
1214
1215                         if ( e == NULL ) {
1216                                 if ( IS_POST_SEARCH ) {
1217                                         /* send LDAP_SYNC_DELETE */
1218                                         rs->sr_entry = e = ps_e;
1219                                         goto post_search_no_entry;
1220                                 } else if( !BDB_IDL_IS_RANGE(candidates) ) {
1221                                         /* only complain for non-range IDLs */
1222                                         Debug( LDAP_DEBUG_TRACE,
1223                                                 "bdb_search: candidate %ld not found\n",
1224                                                 (long) id, 0, 0 );
1225                                 }
1226
1227                                 goto loop_continue;
1228                         }
1229                 } else {
1230                         e = ps_e;
1231                 }
1232
1233                 rs->sr_entry = e;
1234
1235 #ifdef BDB_SUBENTRIES
1236                 /* FIXME: send all but syncrepl */
1237 #if 0
1238                 if ( !is_sync_protocol( sop ) )
1239 #endif
1240                 {
1241                         if ( is_entry_subentry( e ) ) {
1242                                 if( sop->oq_search.rs_scope != LDAP_SCOPE_BASE ) {
1243                                         if(!get_subentries_visibility( sop )) {
1244                                                 /* only subentries are visible */
1245                                                 goto loop_continue;
1246                                         }
1247
1248                                 } else if ( get_subentries( sop ) &&
1249                                         !get_subentries_visibility( sop ))
1250                                 {
1251                                         /* only subentries are visible */
1252                                         goto loop_continue;
1253                                 }
1254
1255                         } else if ( get_subentries_visibility( sop )) {
1256                                 /* only subentries are visible */
1257                                 goto loop_continue;
1258                         }
1259                 }
1260 #endif /* BDB_SUBENTRIES */
1261
1262                 /* Does this candidate actually satisfy the search scope?
1263                  *
1264                  * Note that we don't lock access to the bei_parent pointer.
1265                  * Since only leaf nodes can be deleted, the parent of any
1266                  * node will always be a valid node. Also since we have
1267                  * a Read lock on the data, it cannot be renamed out of the
1268                  * scope while we are looking at it, and unless we're using
1269                  * BDB_HIER, its parents cannot be moved either.
1270                  */
1271                 switch( sop->ors_scope ) {
1272                 case LDAP_SCOPE_BASE:
1273                         /* This is always true, yes? */
1274                         if ( id == base.e_id ) scopeok = 1;
1275                         break;
1276
1277                 case LDAP_SCOPE_ONELEVEL:
1278                         if ( ei->bei_parent->bei_id == base.e_id ) scopeok = 1;
1279                         break;
1280
1281 #ifdef LDAP_SCOPE_CHILDREN
1282                 case LDAP_SCOPE_CHILDREN:
1283                         if ( id == base.e_id ) break;
1284                         /* Fall-thru */
1285 #endif
1286                 case LDAP_SCOPE_SUBTREE: {
1287                         EntryInfo *tmp;
1288                         for ( tmp = BEI(e); tmp; tmp = tmp->bei_parent ) {
1289                                 if ( tmp->bei_id == base.e_id ) {
1290                                         scopeok = 1;
1291                                         break;
1292                                 }
1293                         }
1294                         } break;
1295                 }
1296
1297                 /* aliases were already dereferenced in candidate list */
1298                 if ( sop->ors_deref & LDAP_DEREF_SEARCHING ) {
1299                         /* but if the search base is an alias, and we didn't
1300                          * deref it when finding, return it.
1301                          */
1302                         if ( is_entry_alias(e) &&
1303                                 ((sop->ors_deref & LDAP_DEREF_FINDING) ||
1304                                         !bvmatch(&e->e_nname, &op->o_req_ndn)))
1305                         {
1306                                 goto loop_continue;
1307                         }
1308
1309                         /* scopes is only non-empty for onelevel or subtree */
1310                         if ( !scopeok && BDB_IDL_N(scopes) ) {
1311                                 unsigned x;
1312                                 if ( sop->ors_scope == LDAP_SCOPE_ONELEVEL ) {
1313                                         x = bdb_idl_search( scopes, e->e_id );
1314                                         if ( scopes[x] == e->e_id ) scopeok = 1;
1315                                 } else {
1316                                         /* subtree, walk up the tree */
1317                                         EntryInfo *tmp = BEI(e);
1318                                         for (;tmp->bei_parent; tmp=tmp->bei_parent) {
1319                                                 x = bdb_idl_search( scopes, tmp->bei_id );
1320                                                 if ( scopes[x] == tmp->bei_id ) {
1321                                                         scopeok = 1;
1322                                                         break;
1323                                                 }
1324                                         }
1325                                 }
1326                         }
1327                 }
1328
1329                 /* Not in scope, ignore it */
1330                 if ( !IS_POST_SEARCH && !scopeok ) {
1331                         Debug( LDAP_DEBUG_TRACE,
1332                                 "bdb_search: %ld scope not okay\n",
1333                                 (long) id, 0, 0 );
1334                         goto loop_continue;
1335                 }
1336
1337                 /*
1338                  * if it's a referral, add it to the list of referrals. only do
1339                  * this for non-base searches, and don't check the filter
1340                  * explicitly here since it's only a candidate anyway.
1341                  */
1342                 if ( !manageDSAit && sop->oq_search.rs_scope != LDAP_SCOPE_BASE
1343                         && is_entry_referral( e ) )
1344                 {
1345                         BerVarray erefs = get_entry_referrals( sop, e );
1346                         rs->sr_ref = referral_rewrite( erefs, &e->e_name, NULL,
1347                                 sop->oq_search.rs_scope == LDAP_SCOPE_ONELEVEL
1348                                         ? LDAP_SCOPE_BASE : LDAP_SCOPE_SUBTREE );
1349
1350                         send_search_reference( sop, rs );
1351
1352                         ber_bvarray_free( rs->sr_ref );
1353                         ber_bvarray_free( erefs );
1354                         rs->sr_ref = NULL;
1355
1356                         goto loop_continue;
1357                 }
1358
1359                 if ( !manageDSAit && is_entry_glue( e )) {
1360                         goto loop_continue;
1361                 }
1362
1363                 /* if it matches the filter and scope, send it */
1364                 if (IS_PSEARCH) {
1365                         if (ps_type != LDAP_PSEARCH_BY_SCOPEOUT) {
1366                                 rs->sr_err = test_filter( sop, rs->sr_entry, &cookief );
1367                         } else {
1368                                 rs->sr_err = LDAP_COMPARE_TRUE;
1369                         }
1370
1371                 } else {
1372                         if ( !IS_POST_SEARCH ) {
1373                                 if ( sop->o_sync_mode & SLAP_SYNC_REFRESH ) {
1374                                         rc_sync = test_filter( sop, rs->sr_entry, &cookief );
1375                                         rs->sr_err = test_filter( sop, rs->sr_entry,
1376                                                                                 &contextcsnand );
1377                                         if ( rs->sr_err == LDAP_COMPARE_TRUE ) {
1378                                                 if ( rc_sync == LDAP_COMPARE_TRUE ) {
1379                                                         if ( no_sync_state_change ) {
1380                                                                 Debug( LDAP_DEBUG_TRACE,
1381                                                                         "bdb_search: "
1382                                                                         "error in context csn management\n",
1383                                                                         0, 0, 0 );
1384                                                         }
1385                                                         entry_sync_state = LDAP_SYNC_ADD;
1386
1387                                                 } else {
1388                                                         if ( no_sync_state_change ) {
1389                                                                 goto loop_continue;
1390                                                         }
1391                                                         entry_sync_state = LDAP_SYNC_PRESENT;
1392                                                 }
1393                                         }
1394                                 } else {
1395                                         rs->sr_err = test_filter( sop,
1396                                                 rs->sr_entry, sop->oq_search.rs_filter );
1397                                 }
1398                         } else {
1399                                 if ( scopeok ) {
1400                                         rs->sr_err = test_filter( sop,
1401                                                 rs->sr_entry, sop->oq_search.rs_filter );
1402                                 } else {
1403                                         rs->sr_err = LDAP_COMPARE_TRUE;
1404                                 }
1405                         }
1406                 }
1407
1408                 if ( rs->sr_err == LDAP_COMPARE_TRUE ) {
1409                         /* check size limit */
1410                         if ( --sop->ors_slimit == -1 &&
1411                                 sop->o_sync_slog_size == -1 )
1412                         {
1413                                 if (!IS_PSEARCH) {
1414                                         bdb_cache_return_entry_r( bdb->bi_dbenv,
1415                                                 &bdb->bi_cache, e, &lock );
1416                                 }
1417                                 e = NULL;
1418                                 rs->sr_entry = NULL;
1419                                 rs->sr_err = LDAP_SIZELIMIT_EXCEEDED;
1420                                 rs->sr_ref = rs->sr_v2ref;
1421                                 send_ldap_result( sop, rs );
1422                                 rs->sr_err = LDAP_SUCCESS;
1423                                 goto done;
1424                         }
1425
1426                         if ( get_pagedresults(sop) > SLAP_NO_CONTROL ) {
1427                                 if ( rs->sr_nentries >= sop->o_pagedresults_size ) {
1428                                         send_paged_response( sop, rs, &lastid, tentries );
1429                                         goto done;
1430                                 }
1431                                 lastid = id;
1432                         }
1433
1434                         if (e) {
1435                                 /* safe default */
1436                                 int result = -1;
1437
1438                                 if (IS_PSEARCH || IS_POST_SEARCH) {
1439                                         int premodify_found = 0;
1440
1441                                         if ( IS_POST_SEARCH ||
1442                                                  ps_type == LDAP_PSEARCH_BY_ADD ||
1443                                                  ps_type == LDAP_PSEARCH_BY_DELETE ||
1444                                                  ps_type == LDAP_PSEARCH_BY_MODIFY ||
1445                                                  ps_type == LDAP_PSEARCH_BY_SCOPEOUT )
1446                                         {
1447                                                 if ( !IS_POST_SEARCH &&
1448                                                          ps_type == LDAP_PSEARCH_BY_MODIFY ) {
1449                                                         struct psid_entry* psid_e;
1450                                                         LDAP_LIST_FOREACH( psid_e,
1451                                                                 &op->o_pm_list, ps_link)
1452                                                         {
1453                                                                 if( psid_e->ps_op == sop ) {
1454                                                                         premodify_found = 1;
1455                                                                         LDAP_LIST_REMOVE(psid_e, ps_link);
1456                                                                         break;
1457                                                                 }
1458                                                         }
1459                                                         if (psid_e != NULL) free (psid_e);
1460                                                 }
1461
1462                                                 if ( IS_POST_SEARCH ) {
1463                                                         if ( scopeok ) {
1464                                                                 entry_sync_state = LDAP_SYNC_ADD;
1465                                                         } else {
1466 post_search_no_entry:
1467                                                                 entry_sync_state = LDAP_SYNC_DELETE;
1468                                                         }
1469                                                 } else if ( ps_type == LDAP_PSEARCH_BY_ADD ) {
1470                                                         entry_sync_state = LDAP_SYNC_ADD;
1471                                                 } else if ( ps_type == LDAP_PSEARCH_BY_DELETE ) {
1472                                                         entry_sync_state = LDAP_SYNC_DELETE;
1473                                                 } else if ( ps_type == LDAP_PSEARCH_BY_MODIFY ) {
1474                                                         if ( premodify_found ) {
1475                                                                 entry_sync_state = LDAP_SYNC_MODIFY;
1476                                                         } else {
1477                                                                 entry_sync_state = LDAP_SYNC_ADD;
1478                                                         }
1479                                                 } else if ( ps_type == LDAP_PSEARCH_BY_SCOPEOUT ) {
1480                                                         entry_sync_state = LDAP_SYNC_DELETE;
1481                                                 } else {
1482                                                         rs->sr_err = LDAP_OTHER;
1483                                                         goto done;
1484                                                 }
1485
1486                                                 if ( sop->o_sync_slog_size != -1 ) {
1487                                                         if ( entry_sync_state == LDAP_SYNC_DELETE ) {
1488                                                                 result = slap_add_session_log( op, sop, e );
1489                                                         } else {
1490                                                                 result = 1;
1491                                                         }
1492                                                 } else {
1493                                                         struct berval cookie;
1494                                                         slap_compose_sync_cookie( sop, &cookie,
1495                                                                 search_context_csn,
1496                                                                 sop->o_sync_state.sid,
1497                                                                 sop->o_sync_state.rid );
1498                                                         rs->sr_err = slap_build_sync_state_ctrl(
1499                                                                 sop, rs, e, entry_sync_state, ctrls,
1500                                                                 num_ctrls++, 1, &cookie );
1501                                                         if ( rs->sr_err != LDAP_SUCCESS ) goto done;
1502                                                         if (!(IS_POST_SEARCH &&
1503                                                                 entry_sync_state == LDAP_SYNC_DELETE)) {
1504                                                                 rs->sr_attrs = attrs;
1505                                                         } else {
1506                                                                 rs->sr_attrs = NULL;
1507                                                         }
1508                                                         rs->sr_operational_attrs = NULL;
1509                                                         rs->sr_ctrls = ctrls;
1510                                                         rs->sr_flags = 0;
1511                                                         result = send_search_entry( sop, rs );
1512                                                         if ( cookie.bv_val ) ch_free( cookie.bv_val );
1513                                                         slap_sl_free(
1514                                                                 ctrls[num_ctrls-1]->ldctl_value.bv_val,
1515                                                                 sop->o_tmpmemctx );
1516                                                         slap_sl_free( ctrls[--num_ctrls],
1517                                                                 sop->o_tmpmemctx );
1518                                                         ctrls[num_ctrls] = NULL;
1519                                                         rs->sr_ctrls = NULL;
1520                                                 }
1521
1522                                         } else if ( ps_type == LDAP_PSEARCH_BY_PREMODIFY ) {
1523                                                 struct psid_entry* psid_e;
1524                                                 psid_e = (struct psid_entry *) ch_calloc(1,
1525                                                         sizeof(struct psid_entry));
1526                                                 psid_e->ps_op = sop;
1527                                                 LDAP_LIST_INSERT_HEAD( &op->o_pm_list,
1528                                                         psid_e, ps_link );
1529
1530                                         } else {
1531                                                 Debug( LDAP_DEBUG_TRACE,
1532                                                         "bdb_search: invalid ps_type (%d) \n",
1533                                                         ps_type, 0, 0);
1534                                         }
1535
1536                                 } else {
1537                                         if ( sop->o_sync_mode & SLAP_SYNC_REFRESH ) {
1538                                                 if ( rc_sync == LDAP_COMPARE_TRUE ) { /* ADD */
1539                                                         rs->sr_err = slap_build_sync_state_ctrl(
1540                                                                 sop, rs, e, entry_sync_state, ctrls,
1541                                                                 num_ctrls++, 0, NULL );
1542                                                         if ( rs->sr_err != LDAP_SUCCESS ) goto done;
1543                                                         rs->sr_ctrls = ctrls;
1544                                                         rs->sr_attrs = sop->oq_search.rs_attrs;
1545                                                         rs->sr_operational_attrs = NULL;
1546                                                         rs->sr_flags = 0;
1547                                                         result = send_search_entry( sop, rs );
1548                                                         slap_sl_free(
1549                                                                 ctrls[num_ctrls-1]->ldctl_value.bv_val,
1550                                                                 sop->o_tmpmemctx );
1551                                                         slap_sl_free( ctrls[--num_ctrls],
1552                                                                 sop->o_tmpmemctx );
1553                                                         ctrls[num_ctrls] = NULL;
1554                                                         rs->sr_ctrls = NULL;
1555
1556                                                 } else { /* PRESENT */
1557                                                         if ( sync_send_present_mode ) {
1558                                                                 result = slap_build_syncUUID_set( sop,
1559                                                                         &syncUUID_set, e );
1560                                                                 if ( result <= 0 ) {
1561                                                                         result = -1;
1562                                                                 } else {
1563                                                                         syncUUID_set_cnt++;
1564                                                                         if ( syncUUID_set_cnt ==
1565                                                                                 SLAP_SYNCUUID_SET_SIZE )
1566                                                                         {
1567                                                                                 rs->sr_err = LDAP_SUCCESS;
1568                                                                                 rs->sr_rspoid = LDAP_SYNC_INFO;
1569                                                                                 rs->sr_ctrls = NULL;
1570                                                                                 result = slap_send_syncinfo( sop, rs,
1571                                                                                         LDAP_TAG_SYNC_ID_SET,
1572                                                                                         NULL, 0, syncUUID_set, 0 );
1573                                                                                 if ( result != LDAP_SUCCESS ) {
1574                                                                                         result = -1;
1575                                                                                 }
1576                                                                                 ber_bvarray_free_x( syncUUID_set,
1577                                                                                         sop->o_tmpmemctx );
1578                                                                                 syncUUID_set = NULL;
1579                                                                                 syncUUID_set_cnt = 0;
1580                                                                         }
1581                                                                 }
1582
1583                                                         } else {
1584                                                                 result = 1;
1585                                                         }
1586                                                 }
1587
1588                                         } else {
1589                                                 rs->sr_attrs = sop->oq_search.rs_attrs;
1590                                                 rs->sr_operational_attrs = NULL;
1591                                                 rs->sr_ctrls = NULL;
1592                                                 rs->sr_flags = 0;
1593                                                 rs->sr_err = LDAP_SUCCESS;
1594                                                 result = send_search_entry( sop, rs );
1595                                         }
1596                                 }
1597
1598                                 switch (result) {
1599                                 case 0:         /* entry sent ok */
1600                                         break;
1601                                 case 1:         /* entry not sent */
1602                                         break;
1603                                 case -1:        /* connection closed */
1604                                         if (!IS_PSEARCH) {
1605                                                 bdb_cache_return_entry_r(bdb->bi_dbenv,
1606                                                         &bdb->bi_cache, e, &lock);
1607                                         }
1608                                         e = NULL;
1609                                         rs->sr_entry = NULL;
1610                                         rs->sr_err = LDAP_OTHER;
1611                                         goto done;
1612                                 }
1613                         }
1614
1615                 } else {
1616                         Debug( LDAP_DEBUG_TRACE,
1617                                 "bdb_search: %ld does not match filter\n",
1618                                 (long) id, 0, 0 );
1619                 }
1620
1621 loop_continue:
1622                 if( e != NULL ) {
1623                         /* free reader lock */
1624                         if (!IS_PSEARCH) {
1625                                 if (!(IS_POST_SEARCH &&
1626                                                  entry_sync_state == LDAP_SYNC_DELETE)) {
1627                                         bdb_cache_return_entry_r( bdb->bi_dbenv,
1628                                                 &bdb->bi_cache, e , &lock );
1629                                         if ( sop->o_nocaching ) {
1630                                                 bdb_cache_delete_entry( bdb, ei, locker, &lock );
1631                                         }
1632                                 }
1633                         }
1634                         e = NULL;
1635                         rs->sr_entry = NULL;
1636                 }
1637
1638                 if ( sop->o_refresh_in_progress ) {
1639                         if ( pce ) {
1640                                 pce->pc_sent = 1;
1641                         }
1642                 }
1643
1644                 ldap_pvt_thread_yield();
1645         }
1646
1647         if ( syncUUID_set_cnt > 0 ) {
1648                 rs->sr_err = LDAP_SUCCESS;
1649                 rs->sr_rspoid = LDAP_SYNC_INFO;
1650                 rs->sr_ctrls = NULL;
1651                 slap_send_syncinfo( sop, rs, LDAP_TAG_SYNC_ID_SET,
1652                         NULL, 0, syncUUID_set, 0 );
1653                 ber_bvarray_free_x( syncUUID_set, sop->o_tmpmemctx );
1654                 syncUUID_set_cnt = 0;
1655         }
1656
1657 nochange:
1658         if (!IS_PSEARCH && !IS_POST_SEARCH) {
1659                 if ( sop->o_sync_mode & SLAP_SYNC_REFRESH ) {
1660                         if ( sop->o_sync_mode & SLAP_SYNC_PERSIST ) {
1661                                 struct berval cookie;
1662                                 slap_compose_sync_cookie( sop, &cookie, search_context_csn,
1663                                         sop->o_sync_state.sid, sop->o_sync_state.rid );
1664
1665                                 if ( sync_send_present_mode ) {
1666                                         rs->sr_err = LDAP_SUCCESS;
1667                                         rs->sr_rspoid = LDAP_SYNC_INFO;
1668                                         rs->sr_ctrls = NULL;
1669                                         slap_send_syncinfo( sop, rs,
1670                                                 LDAP_TAG_SYNC_REFRESH_PRESENT, &cookie, 1, NULL, 0 );
1671
1672                                 } else {
1673                                         if ( !no_sync_state_change ) {
1674                                                 int slog_found = 0;
1675                                                 ldap_pvt_thread_rdwr_rlock( &bdb->bi_pslist_rwlock );
1676                                                 LDAP_LIST_FOREACH( ps_list, &bdb->bi_psearch_list,
1677                                                         o_ps_link )
1678                                                 {
1679                                                         if ( ps_list->o_sync_slog_size > 0 ) {
1680                                                                 if ( ps_list->o_sync_state.sid ==
1681                                                                         sop->o_sync_state.sid )
1682                                                                 {
1683                                                                         slog_found = 1;
1684                                                                         break;
1685                                                                 }
1686                                                         }
1687                                                 }
1688
1689                                                 if ( slog_found ) {
1690                                                         rs->sr_err = LDAP_SUCCESS;
1691                                                         rs->sr_rspoid = NULL;
1692                                                         rs->sr_ctrls = NULL;
1693                                                         slap_send_session_log( op, ps_list, rs );
1694                                                 }
1695                                                 ldap_pvt_thread_rdwr_runlock( &bdb->bi_pslist_rwlock );
1696                                         }
1697
1698                                         rs->sr_err = LDAP_SUCCESS;
1699                                         rs->sr_rspoid = LDAP_SYNC_INFO;
1700                                         rs->sr_ctrls = NULL;
1701                                         slap_send_syncinfo( sop, rs,
1702                                                 LDAP_TAG_SYNC_REFRESH_DELETE, &cookie, 1, NULL, 0 );
1703                                 }
1704
1705                                 if ( cookie.bv_val ) ch_free( cookie.bv_val );
1706
1707                         } else {
1708                                 /* refreshOnly mode */
1709                                 struct berval cookie;
1710                                 slap_compose_sync_cookie( sop, &cookie, search_context_csn,
1711                                         sop->o_sync_state.sid, sop->o_sync_state.rid );
1712
1713                                 if ( sync_send_present_mode ) {
1714                                         slap_build_sync_done_ctrl( sop, rs, ctrls,
1715                                                 num_ctrls++, 1, &cookie, LDAP_SYNC_REFRESH_PRESENTS );
1716
1717                                 } else {
1718                                         if ( !no_sync_state_change ) {
1719                                                 int slog_found = 0;
1720                                                 ldap_pvt_thread_rdwr_rlock( &bdb->bi_pslist_rwlock );
1721                                                 LDAP_LIST_FOREACH( ps_list, &bdb->bi_psearch_list,
1722                                                         o_ps_link )
1723                                                 {
1724                                                         if ( ps_list->o_sync_slog_size > 0 ) {
1725                                                                 if ( ps_list->o_sync_state.sid ==
1726                                                                                 sop->o_sync_state.sid ) {
1727                                                                         slog_found = 1;
1728                                                                         break;
1729                                                                 }
1730                                                         }
1731                                                 }
1732
1733                                                 if ( slog_found ) {
1734                                                         slap_send_session_log( op, ps_list, rs );
1735                                                 }
1736                                                 ldap_pvt_thread_rdwr_runlock( &bdb->bi_pslist_rwlock );
1737                                         }
1738
1739                                         slap_build_sync_done_ctrl( sop, rs, ctrls,
1740                                                 num_ctrls++, 1, &cookie, LDAP_SYNC_REFRESH_DELETES );
1741                                 }
1742
1743                                 rs->sr_ctrls = ctrls;
1744                                 rs->sr_ref = rs->sr_v2ref;
1745                                 rs->sr_err = (rs->sr_v2ref == NULL)
1746                                         ? LDAP_SUCCESS : LDAP_REFERRAL;
1747                                 rs->sr_rspoid = NULL;
1748                                 send_ldap_result( sop, rs );
1749                                 if ( ctrls[num_ctrls-1]->ldctl_value.bv_val != NULL ) {
1750                                         slap_sl_free( ctrls[num_ctrls-1]->ldctl_value.bv_val,
1751                                                 sop->o_tmpmemctx );
1752                                 }
1753                                 slap_sl_free( ctrls[--num_ctrls], sop->o_tmpmemctx );
1754                                 ctrls[num_ctrls] = NULL;
1755                                 if ( cookie.bv_val ) ch_free( cookie.bv_val );
1756                         }
1757
1758                 } else {
1759                         rs->sr_ctrls = NULL;
1760                         rs->sr_ref = rs->sr_v2ref;
1761                         rs->sr_err = (rs->sr_v2ref == NULL) ? LDAP_SUCCESS : LDAP_REFERRAL;
1762                         rs->sr_rspoid = NULL;
1763                         if ( get_pagedresults(sop) > SLAP_NO_CONTROL ) {
1764                                 send_paged_response( sop, rs, NULL, 0 );
1765                         } else {
1766                                 send_ldap_result( sop, rs );
1767                         }
1768                 }
1769         }
1770
1771         if ( sop->o_refresh_in_progress ) {
1772                 sop->o_refresh_in_progress = 0;
1773         }
1774
1775         rs->sr_err = LDAP_SUCCESS;
1776
1777 done:
1778         if ( sop->o_psearch_finished ) {
1779                 avl_free( sop->o_psearch_finished, ch_free );
1780         }
1781
1782         if( !IS_PSEARCH && e != NULL ) {
1783                 /* free reader lock */
1784                 bdb_cache_return_entry_r( bdb->bi_dbenv, &bdb->bi_cache, e, &lock );
1785         }
1786
1787         if ( !opinfo )
1788                 LOCK_ID_FREE( bdb->bi_dbenv, locker );
1789
1790         ber_bvfree( search_context_csn );
1791
1792         if( rs->sr_v2ref ) {
1793                 ber_bvarray_free( rs->sr_v2ref );
1794                 rs->sr_v2ref = NULL;
1795         }
1796         if( realbase.bv_val ) ch_free( realbase.bv_val );
1797
1798         return rs->sr_err;
1799 }
1800
1801
1802 static int base_candidate(
1803         BackendDB       *be,
1804         Entry   *e,
1805         ID              *ids )
1806 {
1807         Debug(LDAP_DEBUG_ARGS, "base_candidates: base: \"%s\" (0x%08lx)\n",
1808                 e->e_nname.bv_val, (long) e->e_id, 0);
1809
1810         ids[0] = 1;
1811         ids[1] = e->e_id;
1812         return 0;
1813 }
1814
1815 /* Look for "objectClass Present" in this filter.
1816  * Also count depth of filter tree while we're at it.
1817  */
1818 static int oc_filter(
1819         Filter *f,
1820         int cur,
1821         int *max )
1822 {
1823         int rc = 0;
1824
1825         assert( f );
1826
1827         if( cur > *max ) *max = cur;
1828
1829         switch( f->f_choice ) {
1830         case LDAP_FILTER_PRESENT:
1831                 if (f->f_desc == slap_schema.si_ad_objectClass) {
1832                         rc = 1;
1833                 }
1834                 break;
1835
1836         case LDAP_FILTER_AND:
1837         case LDAP_FILTER_OR:
1838                 cur++;
1839                 for ( f=f->f_and; f; f=f->f_next ) {
1840                         (void) oc_filter(f, cur, max);
1841                 }
1842                 break;
1843
1844         default:
1845                 break;
1846         }
1847         return rc;
1848 }
1849
1850 static void search_stack_free( void *key, void *data )
1851 {
1852         ber_memfree_x(data, NULL);
1853 }
1854
1855 static void *search_stack( Operation *op )
1856 {
1857         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
1858         void *ret = NULL;
1859
1860         if ( op->o_threadctx ) {
1861                 ldap_pvt_thread_pool_getkey( op->o_threadctx, search_stack,
1862                         &ret, NULL );
1863         } else {
1864                 ret = bdb->bi_search_stack;
1865         }
1866
1867         if ( !ret ) {
1868                 ret = ch_malloc( bdb->bi_search_stack_depth * BDB_IDL_UM_SIZE
1869                         * sizeof( ID ) );
1870                 if ( op->o_threadctx ) {
1871                         ldap_pvt_thread_pool_setkey( op->o_threadctx, search_stack,
1872                                 ret, search_stack_free );
1873                 } else {
1874                         bdb->bi_search_stack = ret;
1875                 }
1876         }
1877         return ret;
1878 }
1879
1880 static int search_candidates(
1881         Operation *stackop,
1882         Operation *op,
1883         SlapReply *rs,
1884         Entry *e,
1885         u_int32_t locker,
1886         ID      *ids,
1887         ID      *scopes )
1888 {
1889         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
1890         int rc, depth = 1;
1891         Filter          f, rf, xf, nf;
1892         ID              *stack;
1893         AttributeAssertion aa_ref;
1894 #ifdef BDB_SUBENTRIES
1895         Filter  sf;
1896         AttributeAssertion aa_subentry;
1897 #endif
1898
1899         /*
1900          * This routine takes as input a filter (user-filter)
1901          * and rewrites it as follows:
1902          *      (&(scope=DN)[(objectClass=subentry)]
1903          *              (|[(objectClass=referral)(objectClass=alias)](user-filter))
1904          */
1905
1906         Debug(LDAP_DEBUG_TRACE,
1907                 "search_candidates: base=\"%s\" (0x%08lx) scope=%d\n",
1908                 e->e_nname.bv_val, (long) e->e_id, op->oq_search.rs_scope );
1909
1910         xf.f_or = op->oq_search.rs_filter;
1911         xf.f_choice = LDAP_FILTER_OR;
1912         xf.f_next = NULL;
1913
1914         /* If the user's filter uses objectClass=*,
1915          * these clauses are redundant.
1916          */
1917         if (!oc_filter(op->oq_search.rs_filter, 1, &depth)
1918                 && !get_subentries_visibility(op)
1919                 && !is_sync_protocol(op) )
1920         {
1921                 if( !get_manageDSAit(op) && !get_domainScope(op) ) {
1922                         /* match referral objects */
1923                         struct berval bv_ref = BER_BVC( "referral" );
1924                         rf.f_choice = LDAP_FILTER_EQUALITY;
1925                         rf.f_ava = &aa_ref;
1926                         rf.f_av_desc = slap_schema.si_ad_objectClass;
1927                         rf.f_av_value = bv_ref;
1928                         rf.f_next = xf.f_or;
1929                         xf.f_or = &rf;
1930                         depth++;
1931                 }
1932         }
1933
1934         f.f_next = NULL;
1935         f.f_choice = LDAP_FILTER_AND;
1936         f.f_and = &nf;
1937         /* Dummy; we compute scope separately now */
1938         nf.f_choice = SLAPD_FILTER_COMPUTED;
1939         nf.f_result = LDAP_SUCCESS;
1940         nf.f_next = ( xf.f_or == op->oq_search.rs_filter )
1941                 ? op->oq_search.rs_filter : &xf ;
1942         /* Filter depth increased again, adding dummy clause */
1943         depth++;
1944
1945 #ifdef BDB_SUBENTRIES
1946         if( get_subentries_visibility( op ) ) {
1947                 struct berval bv_subentry = BER_BVC( "SUBENTRY" );
1948                 sf.f_choice = LDAP_FILTER_EQUALITY;
1949                 sf.f_ava = &aa_subentry;
1950                 sf.f_av_desc = slap_schema.si_ad_objectClass;
1951                 sf.f_av_value = bv_subentry;
1952                 sf.f_next = nf.f_next;
1953                 nf.f_next = &sf;
1954         }
1955 #endif
1956
1957         /* Allocate IDL stack, plus 1 more for former tmp */
1958         if ( depth+1 > bdb->bi_search_stack_depth ) {
1959                 stack = ch_malloc( (depth + 1) * BDB_IDL_UM_SIZE * sizeof( ID ) );
1960         } else {
1961                 stack = search_stack( stackop );
1962         }
1963
1964         if( op->ors_deref & LDAP_DEREF_SEARCHING ) {
1965                 rc = search_aliases( op, rs, e, locker, ids, scopes, stack );
1966         } else {
1967                 rc = bdb_dn2idl( op, e, ids, stack );
1968         }
1969
1970         if ( rc == LDAP_SUCCESS ) {
1971                 rc = bdb_filter_candidates( op, &f, ids,
1972                         stack, stack+BDB_IDL_UM_SIZE );
1973         }
1974
1975         if ( depth+1 > bdb->bi_search_stack_depth ) {
1976                 ch_free( stack );
1977         }
1978
1979         if( rc ) {
1980                 Debug(LDAP_DEBUG_TRACE,
1981                         "bdb_search_candidates: failed (rc=%d)\n",
1982                         rc, NULL, NULL );
1983
1984         } else {
1985                 Debug(LDAP_DEBUG_TRACE,
1986                         "bdb_search_candidates: id=%ld first=%ld last=%ld\n",
1987                         (long) ids[0],
1988                         (long) BDB_IDL_FIRST(ids),
1989                         (long) BDB_IDL_LAST(ids) );
1990         }
1991
1992         return rc;
1993 }
1994
1995 static int
1996 parse_paged_cookie( Operation *op, SlapReply *rs )
1997 {
1998         LDAPControl     **c;
1999         int             rc = LDAP_SUCCESS;
2000         ber_tag_t       tag;
2001         ber_int_t       size;
2002         BerElement      *ber;
2003         struct berval   cookie = BER_BVNULL;
2004
2005         /* this function must be invoked only if the pagedResults
2006          * control has been detected, parsed and partially checked
2007          * by the frontend */
2008         assert( get_pagedresults( op ) > SLAP_NO_CONTROL );
2009
2010         /* look for the appropriate ctrl structure */
2011         for ( c = op->o_ctrls; c[0] != NULL; c++ ) {
2012                 if ( strcmp( c[0]->ldctl_oid, LDAP_CONTROL_PAGEDRESULTS ) == 0 )
2013                 {
2014                         break;
2015                 }
2016         }
2017
2018         if ( c[0] == NULL ) {
2019                 rs->sr_text = "missing pagedResults control";
2020                 return LDAP_PROTOCOL_ERROR;
2021         }
2022
2023         /* Tested by frontend */
2024         assert( c[0]->ldctl_value.bv_len > 0 );
2025
2026         /* Parse the control value
2027          *      realSearchControlValue ::= SEQUENCE {
2028          *              size    INTEGER (0..maxInt),
2029          *                              -- requested page size from client
2030          *                              -- result set size estimate from server
2031          *              cookie  OCTET STRING
2032          * }
2033          */
2034         ber = ber_init( &c[0]->ldctl_value );
2035         if ( ber == NULL ) {
2036                 rs->sr_text = "internal error";
2037                 return LDAP_OTHER;
2038         }
2039
2040         tag = ber_scanf( ber, "{im}", &size, &cookie );
2041
2042         /* Tested by frontend */
2043         assert( tag != LBER_ERROR );
2044         assert( size >= 0 );
2045
2046         /* cookie decoding/checks deferred to backend... */
2047         if ( cookie.bv_len ) {
2048                 PagedResultsCookie reqcookie;
2049                 if( cookie.bv_len != sizeof( reqcookie ) ) {
2050                         /* bad cookie */
2051                         rs->sr_text = "paged results cookie is invalid";
2052                         rc = LDAP_PROTOCOL_ERROR;
2053                         goto done;
2054                 }
2055
2056                 AC_MEMCPY( &reqcookie, cookie.bv_val, sizeof( reqcookie ));
2057
2058                 if ( reqcookie > op->o_pagedresults_state.ps_cookie ) {
2059                         /* bad cookie */
2060                         rs->sr_text = "paged results cookie is invalid";
2061                         rc = LDAP_PROTOCOL_ERROR;
2062                         goto done;
2063
2064                 } else if ( reqcookie < op->o_pagedresults_state.ps_cookie ) {
2065                         rs->sr_text = "paged results cookie is invalid or old";
2066                         rc = LDAP_UNWILLING_TO_PERFORM;
2067                         goto done;
2068                 }
2069
2070         } else {
2071                 /* Initial request.  Initialize state. */
2072 #if 0
2073                 if ( op->o_conn->c_pagedresults_state.ps_cookie != 0 ) {
2074                         /* There's another pagedResults control on the
2075                          * same connection; reject new pagedResults controls
2076                          * (allowed by RFC2696) */
2077                         rs->sr_text = "paged results cookie unavailable; try later";
2078                         rc = LDAP_UNWILLING_TO_PERFORM;
2079                         goto done;
2080                 }
2081 #endif
2082                 op->o_pagedresults_state.ps_cookie = 0;
2083                 op->o_pagedresults_state.ps_count = 0;
2084         }
2085
2086 done:;
2087         (void)ber_free( ber, 1 );
2088
2089         return rc;
2090 }
2091
2092 static void
2093 send_paged_response(
2094         Operation       *op,
2095         SlapReply       *rs,
2096         ID              *lastid,
2097         int             tentries )
2098 {
2099         LDAPControl     ctrl, *ctrls[2];
2100         BerElementBuffer berbuf;
2101         BerElement      *ber = (BerElement *)&berbuf;
2102         PagedResultsCookie respcookie;
2103         struct berval cookie;
2104
2105         Debug(LDAP_DEBUG_ARGS,
2106                 "send_paged_response: lastid=0x%08lx nentries=%d\n",
2107                 lastid ? *lastid : 0, rs->sr_nentries, NULL );
2108
2109         BER_BVZERO( &ctrl.ldctl_value );
2110         ctrls[0] = &ctrl;
2111         ctrls[1] = NULL;
2112
2113         ber_init2( ber, NULL, LBER_USE_DER );
2114
2115         if ( lastid ) {
2116                 respcookie = ( PagedResultsCookie )(*lastid);
2117                 cookie.bv_len = sizeof( respcookie );
2118                 cookie.bv_val = (char *)&respcookie;
2119
2120         } else {
2121                 respcookie = ( PagedResultsCookie )0;
2122                 BER_BVSTR( &cookie, "" );
2123         }
2124
2125         op->o_conn->c_pagedresults_state.ps_cookie = respcookie;
2126         op->o_conn->c_pagedresults_state.ps_count =
2127                 op->o_pagedresults_state.ps_count + rs->sr_nentries;
2128
2129         /* return size of 0 -- no estimate */
2130         ber_printf( ber, "{iO}", 0, &cookie );
2131
2132         if ( ber_flatten2( ber, &ctrls[0]->ldctl_value, 0 ) == -1 ) {
2133                 goto done;
2134         }
2135
2136         ctrls[0]->ldctl_oid = LDAP_CONTROL_PAGEDRESULTS;
2137         ctrls[0]->ldctl_iscritical = 0;
2138
2139         rs->sr_ctrls = ctrls;
2140         rs->sr_err = LDAP_SUCCESS;
2141         send_ldap_result( op, rs );
2142         rs->sr_ctrls = NULL;
2143
2144 done:
2145         (void) ber_free_buf( ber );
2146 }
2147
2148 static int
2149 bdb_pfid_cmp( const void *v_id1, const void *v_id2 )
2150 {
2151     const ID *p1 = v_id1, *p2 = v_id2;
2152         return *p1 - *p2;
2153 }
2154
2155 static ID*
2156 bdb_id_dup( Operation *op, ID *id )
2157 {
2158         ID *new;
2159         new = ch_malloc( sizeof(ID) );
2160         *new = *id;
2161         return new;
2162 }