1 /* search.c - ldbm backend search function */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 1998-2005 The OpenLDAP Foundation.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
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>.
21 #include <ac/string.h>
22 #include <ac/socket.h>
25 #include "back-ldbm.h"
26 #include "proto-back-ldbm.h"
28 static ID_BLOCK *base_candidate(
29 Backend *be, Entry *e );
31 static ID_BLOCK *search_candidates(
32 Operation *op, Entry *e, Filter *filter,
33 int scope, int deref, int manageDSAit );
41 struct ldbminfo *li = (struct ldbminfo *) op->o_bd->be_private;
43 const char *text = NULL;
48 Entry *matched = NULL;
49 struct berval realbase = BER_BVNULL;
50 int manageDSAit = get_manageDSAit( op );
52 Debug(LDAP_DEBUG_TRACE, "=> ldbm_back_search\n", 0, 0, 0);
54 /* grab giant lock for reading */
55 ldap_pvt_thread_rdwr_rlock(&li->li_giant_rwlock);
57 if ( op->o_req_ndn.bv_len == 0 ) {
58 /* DIT root special case */
59 e = (Entry *) &slap_entry_root;
61 /* need normalized dn below */
62 ber_dupbv( &realbase, &e->e_nname );
64 candidates = search_candidates( op, e, op->ors_filter,
65 op->ors_scope, op->ors_deref,
66 manageDSAit || get_domainScope(op) );
70 } else if ( op->ors_deref & LDAP_DEREF_FINDING ) {
71 /* deref dn and get entry with reader lock */
72 e = deref_dn_r( op->o_bd, &op->o_req_ndn,
73 &rs->sr_err, &matched, &rs->sr_text );
75 if( rs->sr_err == LDAP_NO_SUCH_OBJECT ) rs->sr_err = LDAP_REFERRAL;
78 /* get entry with reader lock */
79 e = dn2entry_r( op->o_bd, &op->o_req_ndn, &matched );
80 rs->sr_err = e != NULL ? LDAP_SUCCESS : LDAP_REFERRAL;
85 struct berval matched_dn = BER_BVNULL;
87 if ( matched != NULL ) {
88 BerVarray erefs = NULL;
90 if ( ! access_allowed( op, matched,
91 slap_schema.si_ad_entry,
92 NULL, ACL_DISCLOSE, NULL ) )
94 rs->sr_err = LDAP_NO_SUCH_OBJECT;
97 ber_dupbv( &matched_dn, &matched->e_name );
99 erefs = is_entry_referral( matched )
100 ? get_entry_referrals( op, matched )
104 cache_return_entry_r( &li->li_cache, matched );
107 rs->sr_ref = referral_rewrite( erefs, &matched_dn,
108 &op->o_req_dn, op->ors_scope );
110 ber_bvarray_free( erefs );
114 rs->sr_ref = referral_rewrite( default_referral,
115 NULL, &op->o_req_dn, op->ors_scope );
118 ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
120 rs->sr_matched = matched_dn.bv_val;
121 send_ldap_result( op, rs );
123 ber_bvarray_free( rs->sr_ref );
124 ber_memfree( matched_dn.bv_val );
126 rs->sr_matched = NULL;
130 if ( ! access_allowed( op, e, slap_schema.si_ad_entry,
131 NULL, ACL_DISCLOSE, NULL ) )
133 rs->sr_err = LDAP_NO_SUCH_OBJECT;
135 cache_return_entry_r( &li->li_cache, e );
136 ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
138 send_ldap_result( op, rs );
142 if ( !manageDSAit && is_entry_referral( e ) ) {
143 /* entry is a referral, don't allow add */
144 struct berval matched_dn = BER_BVNULL;
145 BerVarray erefs = NULL;
148 rs->sr_err = LDAP_OTHER;
149 rs->sr_text = "bad referral object";
151 ber_dupbv( &matched_dn, &e->e_name );
152 erefs = get_entry_referrals( op, e );
154 cache_return_entry_r( &li->li_cache, e );
155 ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
157 Debug( LDAP_DEBUG_TRACE,
158 "ldbm_search: entry is referral\n",
162 rs->sr_ref = referral_rewrite( erefs, &matched_dn,
163 &op->o_req_dn, op->ors_scope );
165 ber_bvarray_free( erefs );
168 rs->sr_err = LDAP_REFERRAL;
173 rs->sr_matched = matched_dn.bv_val;
174 send_ldap_result( op, rs );
175 ber_bvarray_free( rs->sr_ref );
176 ber_memfree( matched_dn.bv_val );
178 rs->sr_matched = NULL;
182 if ( is_entry_alias( e ) ) {
184 op->ors_deref = LDAP_DEREF_NEVER;
187 if ( op->ors_scope == LDAP_SCOPE_BASE ) {
188 candidates = base_candidate( op->o_bd, e );
191 candidates = search_candidates( op, e, op->ors_filter,
192 op->ors_scope, op->ors_deref, manageDSAit );
195 /* need normalized dn below */
196 ber_dupbv( &realbase, &e->e_nname );
198 cache_return_entry_r( &li->li_cache, e );
201 if ( candidates == NULL ) {
203 Debug( LDAP_DEBUG_TRACE, "ldbm_search: no candidates\n",
206 rs->sr_err = LDAP_SUCCESS;
207 send_ldap_result( op, rs );
213 /* if candidates exceed to-be-checked entries, abort */
214 if ( op->ors_limit /* isroot == FALSE */
215 && op->ors_limit->lms_s_unchecked != -1
216 && ID_BLOCK_NIDS( candidates ) > (unsigned) op->ors_limit->lms_s_unchecked )
218 send_ldap_error( op, rs, LDAP_ADMINLIMIT_EXCEEDED, NULL );
223 /* compute it anyway; root does not use it */
224 stoptime = op->o_time + op->ors_tlimit;
225 rs->sr_attrs = op->ors_attrs;
227 for ( id = idl_firstid( candidates, &cursor ); id != NOID;
228 id = idl_nextid( candidates, &cursor ) )
233 /* check for abandon */
234 if ( op->o_abandon ) {
239 /* check time limit */
240 if ( op->ors_tlimit != SLAP_NO_LIMIT
241 && slap_get_time() > stoptime )
243 rs->sr_err = LDAP_TIMELIMIT_EXCEEDED;
244 send_ldap_result( op, rs );
249 /* get the entry with reader lock */
250 e = id2entry_r( op->o_bd, id );
253 Debug( LDAP_DEBUG_TRACE,
254 "ldbm_search: candidate %ld not found\n",
262 #ifdef LDBM_SUBENTRIES
263 if ( is_entry_subentry( e ) ) {
264 if( op->ors_scope != LDAP_SCOPE_BASE ) {
265 if(!get_subentries_visibility( op )) {
266 /* only subentries are visible */
269 } else if ( get_subentries( op ) &&
270 !get_subentries_visibility( op ))
272 /* only subentries are visible */
275 } else if ( get_subentries_visibility( op )) {
276 /* only subentries are visible */
281 if ( op->ors_deref & LDAP_DEREF_SEARCHING &&
282 is_entry_alias( e ) )
288 e = deref_entry_r( op->o_bd, e, &err, &matched, &text );
295 if( e->e_id == id ) {
300 /* need to skip alias which deref into scope */
301 if( op->ors_scope == LDAP_SCOPE_ONELEVEL ) {
303 dnParent( &e->e_nname, &pdn );
304 if ( ber_bvcmp( &pdn, &realbase ) ) {
308 } else if ( dnIsSuffix( &e->e_nname, &realbase ) ) {
309 /* alias is within scope */
310 Debug( LDAP_DEBUG_TRACE,
311 "ldbm_search: alias \"%s\" in subtree\n",
323 * If it's a referral, add it to the list of referrals.
324 * Only do this for non-base searches, and don't check
325 * the filter explicitly here since it's only a candidate
328 if ( !manageDSAit && op->ors_scope != LDAP_SCOPE_BASE &&
329 is_entry_referral( e ) )
334 if ( !scopeok && op->ors_scope == LDAP_SCOPE_ONELEVEL ) {
335 if ( !be_issuffix( op->o_bd, &e->e_nname ) ) {
336 dnParent( &e->e_nname, &dn );
337 scopeok = dn_match( &dn, &realbase );
339 scopeok = (realbase.bv_len == 0);
343 && op->ors_scope == LDAP_SCOPE_SUBTREE )
345 scopeok = dnIsSuffix( &e->e_nname, &realbase );
347 #ifdef LDAP_SCOPE_SUBORDINATE
349 && op->ors_scope == LDAP_SCOPE_SUBORDINATE )
351 scopeok = !dn_match( &e->e_nname, &realbase )
352 && dnIsSuffix( &e->e_nname, &realbase );
360 BerVarray erefs = get_entry_referrals( op, e );
361 rs->sr_ref = referral_rewrite( erefs,
363 op->ors_scope == LDAP_SCOPE_ONELEVEL
365 : LDAP_SCOPE_SUBTREE );
367 send_search_reference( op, rs );
369 ber_bvarray_free( rs->sr_ref );
373 Debug( LDAP_DEBUG_TRACE,
374 "ldbm_search: candidate referral %ld scope not okay\n",
381 if ( !manageDSAit && is_entry_glue( e )) {
385 /* if it matches the filter and scope, send it */
386 result = test_filter( op, e, op->ors_filter );
388 if ( result == LDAP_COMPARE_TRUE ) {
392 if ( !scopeok && op->ors_scope == LDAP_SCOPE_ONELEVEL ) {
393 if ( !be_issuffix( op->o_bd, &e->e_nname ) ) {
394 dnParent( &e->e_nname, &dn );
395 scopeok = dn_match( &dn, &realbase );
397 scopeok = (realbase.bv_len == 0);
400 } else if ( !scopeok &&
401 op->ors_scope == LDAP_SCOPE_SUBTREE )
403 scopeok = dnIsSuffix( &e->e_nname, &realbase );
405 #ifdef LDAP_SCOPE_SUBORDINATE
406 } else if ( !scopeok &&
407 op->ors_scope == LDAP_SCOPE_SUBORDINATE )
409 scopeok = !dn_match( &e->e_nname, &realbase )
410 && dnIsSuffix( &e->e_nname, &realbase );
418 /* check size limit */
419 if ( --op->ors_slimit == -1 ) {
420 cache_return_entry_r( &li->li_cache, e );
421 rs->sr_err = LDAP_SIZELIMIT_EXCEEDED;
423 send_ldap_result( op, rs );
430 result = send_search_entry( op, rs );
433 case 0: /* entry sent ok */
435 case 1: /* entry not sent */
437 case -1: /* connection closed */
438 cache_return_entry_r( &li->li_cache, e );
445 Debug( LDAP_DEBUG_TRACE,
446 "ldbm_search: candidate entry %ld scope not okay\n",
451 Debug( LDAP_DEBUG_TRACE,
452 "ldbm_search: candidate entry %ld does not match filter\n",
458 /* free reader lock */
459 cache_return_entry_r( &li->li_cache, e );
462 ldap_pvt_thread_yield();
465 rs->sr_err = rs->sr_v2ref ? LDAP_REFERRAL : LDAP_SUCCESS;
466 rs->sr_ref = rs->sr_v2ref;
467 send_ldap_result( op, rs );
472 ldap_pvt_thread_rdwr_runlock(&li->li_giant_rwlock);
474 if( candidates != NULL )
475 idl_free( candidates );
477 if( rs->sr_v2ref ) ber_bvarray_free( rs->sr_v2ref );
478 if( realbase.bv_val ) free( realbase.bv_val );
490 Debug(LDAP_DEBUG_TRACE, "base_candidates: base: \"%s\"\n",
494 idl = idl_alloc( 1 );
495 idl_insert( &idl, e->e_id, 1 );
509 ID_BLOCK *candidates;
510 Filter f, fand, rf, af, xf;
511 AttributeAssertion aa_ref, aa_alias;
512 struct berval bv_ref = { sizeof("referral")-1, "referral" };
513 struct berval bv_alias = { sizeof("alias")-1, "alias" };
514 #ifdef LDBM_SUBENTRIES
516 AttributeAssertion aa_subentry;
519 Debug(LDAP_DEBUG_TRACE,
520 "search_candidates: base=\"%s\" s=%d d=%d\n",
521 e->e_ndn, scope, deref );
525 xf.f_choice = LDAP_FILTER_OR;
529 /* match referrals */
530 rf.f_choice = LDAP_FILTER_EQUALITY;
532 rf.f_av_desc = slap_schema.si_ad_objectClass;
533 rf.f_av_value = bv_ref;
538 if( deref & LDAP_DEREF_SEARCHING ) {
540 af.f_choice = LDAP_FILTER_EQUALITY;
541 af.f_ava = &aa_alias;
542 af.f_av_desc = slap_schema.si_ad_objectClass;
543 af.f_av_value = bv_alias;
549 f.f_choice = LDAP_FILTER_AND;
551 fand.f_choice = scope == LDAP_SCOPE_ONELEVEL
552 ? SLAPD_FILTER_DN_ONE
553 : SLAPD_FILTER_DN_SUBTREE;
554 fand.f_dn = &e->e_nname;
555 fand.f_next = xf.f_or == filter ? filter : &xf ;
557 #ifdef LDBM_SUBENTRIES
558 if ( get_subentries_visibility( op )) {
559 struct berval bv_subentry = { sizeof("SUBENTRY")-1, "SUBENTRY" };
560 sf.f_choice = LDAP_FILTER_EQUALITY;
561 sf.f_ava = &aa_subentry;
562 sf.f_av_desc = slap_schema.si_ad_objectClass;
563 sf.f_av_value = bv_subentry;
564 sf.f_next = fand.f_next;
569 candidates = filter_candidates( op, &f );
570 return( candidates );