?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Patrick Welche <prlw1@cam.ac.uk>
[netbsd-mini2440.git] / external / bsd / openldap / dist / servers / slapd / back-bdb / search.c
blob1bde4830b0d71617e83dc437c3efefe7ab60ed75
1 /* search.c - search operation */
2 /* $OpenLDAP: pkg/ldap/servers/slapd/back-bdb/search.c,v 1.246.2.14 2008/05/01 21:39:35 quanah Exp $ */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 2000-2008 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
25 static int base_candidate(
26 BackendDB *be,
27 Entry *e,
28 ID *ids );
29
30 static int search_candidates(
31 Operation *op,
32 SlapReply *rs,
33 Entry *e,
34 BDB_LOCKER locker,
35 ID *ids,
36 ID *scopes );
37
38 static int parse_paged_cookie( Operation *op, SlapReply *rs );
39
40 static void send_paged_response(
41 Operation *op,
42 SlapReply *rs,
43 ID *lastid,
44 int tentries );
45
46 /* Dereference aliases for a single alias entry. Return the final
47 * dereferenced entry on success, NULL on any failure.
48 */
49 static Entry * deref_base (
50 Operation *op,
51 SlapReply *rs,
52 Entry *e,
53 Entry **matched,
54 BDB_LOCKER locker,
55 DB_LOCK *lock,
56 ID *tmp,
57 ID *visited )
58 {
59 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
60 struct berval ndn;
61 EntryInfo *ei;
62 DB_LOCK lockr;
63
64 rs->sr_err = LDAP_ALIAS_DEREF_PROBLEM;
65 rs->sr_text = "maximum deref depth exceeded";
66
67 for (;;) {
68 /* Remember the last entry we looked at, so we can
69 * report broken links
70 */
71 *matched = e;
72
73 if (BDB_IDL_N(tmp) >= op->o_bd->be_max_deref_depth) {
74 e = NULL;
75 break;
76 }
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, *matched, lock);
123 *lock = lockr;
124
125 /* We found a regular entry. Return this to the caller. The
126 * entry is still locked for Read.
127 */
128 if (!is_entry_alias(e)) {
129 rs->sr_err = LDAP_SUCCESS;
130 rs->sr_text = NULL;
131 break;
132 }
133 }
134 return e;
135 }
136
137 /* Look for and dereference all aliases within the search scope. Adds
138 * the dereferenced entries to the "ids" list. Requires "stack" to be
139 * able to hold 8 levels of DB_SIZE IDLs. Of course we're hardcoded to
140 * require a minimum of 8 UM_SIZE IDLs so this is never a problem.
141 */
142 static int search_aliases(
143 Operation *op,
144 SlapReply *rs,
145 Entry *e,
146 BDB_LOCKER locker,
147 ID *ids,
148 ID *scopes,
149 ID *stack )
150 {
151 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
152 ID *aliases, *curscop, *subscop, *visited, *newsubs, *oldsubs, *tmp;
153 ID cursora, ida, cursoro, ido, *subscop2;
154 Entry *matched, *a;
155 EntryInfo *ei;
156 struct berval bv_alias = BER_BVC( "alias" );
157 AttributeAssertion aa_alias = ATTRIBUTEASSERTION_INIT;
158 Filter af;
159 DB_LOCK locka, lockr;
160 int first = 1;
161
162 aliases = stack; /* IDL of all aliases in the database */
163 curscop = aliases + BDB_IDL_DB_SIZE; /* Aliases in the current scope */
164 subscop = curscop + BDB_IDL_DB_SIZE; /* The current scope */
165 visited = subscop + BDB_IDL_DB_SIZE; /* IDs we've seen in this search */
166 newsubs = visited + BDB_IDL_DB_SIZE; /* New subtrees we've added */
167 oldsubs = newsubs + BDB_IDL_DB_SIZE; /* Subtrees added previously */
168 tmp = oldsubs + BDB_IDL_DB_SIZE; /* Scratch space for deref_base() */
169
170 /* A copy of subscop, because subscop gets clobbered by
171 * the bdb_idl_union/intersection routines
172 */
173 subscop2 = tmp + BDB_IDL_DB_SIZE;
174
175 af.f_choice = LDAP_FILTER_EQUALITY;
176 af.f_ava = &aa_alias;
177 af.f_av_desc = slap_schema.si_ad_objectClass;
178 af.f_av_value = bv_alias;
179 af.f_next = NULL;
180
181 /* Find all aliases in database */
182 BDB_IDL_ZERO( aliases );
183 rs->sr_err = bdb_filter_candidates( op, locker, &af, aliases,
184 curscop, visited );
185 if (rs->sr_err != LDAP_SUCCESS) {
186 return rs->sr_err;
187 }
188 oldsubs[0] = 1;
189 oldsubs[1] = e->e_id;
190
191 BDB_IDL_ZERO( ids );
192 BDB_IDL_ZERO( visited );
193 BDB_IDL_ZERO( newsubs );
194
195 cursoro = 0;
196 ido = bdb_idl_first( oldsubs, &cursoro );
197
198 for (;;) {
199 /* Set curscop to only the aliases in the current scope. Start with
200 * all the aliases, obtain the IDL for the current scope, and then
201 * get the intersection of these two IDLs. Add the current scope
202 * to the cumulative list of candidates.
203 */
204 BDB_IDL_CPY( curscop, aliases );
205 rs->sr_err = bdb_dn2idl( op, locker, &e->e_nname, BEI(e), subscop,
206 subscop2+BDB_IDL_DB_SIZE );
207 if (first) {
208 first = 0;
209 } else {
210 bdb_cache_return_entry_r (bdb, e, &locka);
211 }
212 BDB_IDL_CPY(subscop2, subscop);
213 rs->sr_err = bdb_idl_intersection(curscop, subscop);
214 bdb_idl_union( ids, subscop2 );
215
216 /* Dereference all of the aliases in the current scope. */
217 cursora = 0;
218 for (ida = bdb_idl_first(curscop, &cursora); ida != NOID;
219 ida = bdb_idl_next(curscop, &cursora))
220 {
221 ei = NULL;
222 retry1:
223 rs->sr_err = bdb_cache_find_id(op, NULL,
224 ida, &ei, 0, locker, &lockr );
225 if (rs->sr_err != LDAP_SUCCESS) {
226 if ( rs->sr_err == DB_LOCK_DEADLOCK ||
227 rs->sr_err == DB_LOCK_NOTGRANTED ) goto retry1;
228 continue;
229 }
230 a = ei->bei_e;
231
232 /* This should only happen if the curscop IDL has maxed out and
233 * turned into a range that spans IDs indiscriminately
234 */
235 if (!is_entry_alias(a)) {
236 bdb_cache_return_entry_r (bdb, a, &lockr);
237 continue;
238 }
239
240 /* Actually dereference the alias */
241 BDB_IDL_ZERO(tmp);
242 a = deref_base( op, rs, a, &matched, locker, &lockr,
243 tmp, visited );
244 if (a) {
245 /* If the target was not already in our current candidates,
246 * make note of it in the newsubs list. Also
247 * set it in the scopes list so that bdb_search
248 * can check it.
249 */
250 if (bdb_idl_insert(ids, a->e_id) == 0) {
251 bdb_idl_insert(newsubs, a->e_id);
252 bdb_idl_insert(scopes, a->e_id);
253 }
254 bdb_cache_return_entry_r( bdb, a, &lockr);
255
256 } else if (matched) {
257 /* Alias could not be dereferenced, or it deref'd to
258 * an ID we've already seen. Ignore it.
259 */
260 bdb_cache_return_entry_r( bdb, matched, &lockr );
261 rs->sr_text = NULL;
262 }
263 }
264 /* If this is a OneLevel search, we're done; oldsubs only had one
265 * ID in it. For a Subtree search, oldsubs may be a list of scope IDs.
266 */
267 if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) break;
268 nextido:
269 ido = bdb_idl_next( oldsubs, &cursoro );
270
271 /* If we're done processing the old scopes, did we add any new
272 * scopes in this iteration? If so, go back and do those now.
273 */
274 if (ido == NOID) {
275 if (BDB_IDL_IS_ZERO(newsubs)) break;
276 BDB_IDL_CPY(oldsubs, newsubs);
277 BDB_IDL_ZERO(newsubs);
278 cursoro = 0;
279 ido = bdb_idl_first( oldsubs, &cursoro );
280 }
281
282 /* Find the entry corresponding to the next scope. If it can't
283 * be found, ignore it and move on. This should never happen;
284 * we should never see the ID of an entry that doesn't exist.
285 * Set the name so that the scope's IDL can be retrieved.
286 */
287 ei = NULL;
288 sameido:
289 rs->sr_err = bdb_cache_find_id(op, NULL, ido, &ei,
290 0, locker, &locka );
291 if ( rs->sr_err != LDAP_SUCCESS ) {
292 if ( rs->sr_err == DB_LOCK_DEADLOCK ||
293 rs->sr_err == DB_LOCK_NOTGRANTED )
294 goto sameido;
295 goto nextido;
296 }
297 e = ei->bei_e;
298 }
299 return rs->sr_err;
300 }
301
302 int
303 bdb_search( Operation *op, SlapReply *rs )
304 {
305 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
306 ID id, cursor;
307 ID lastid = NOID;
308 ID candidates[BDB_IDL_UM_SIZE];
309 ID scopes[BDB_IDL_DB_SIZE];
310 Entry *e = NULL, base, *e_root;
311 Entry *matched = NULL;
312 EntryInfo *ei;
313 AttributeName *attrs;
314 struct berval realbase = BER_BVNULL;
315 slap_mask_t mask;
316 time_t stoptime;
317 int manageDSAit;
318 int tentries = 0, nentries = 0;
319 int idflag = 0;
320
321 BDB_LOCKER locker = 0;
322 DB_LOCK lock;
323 struct bdb_op_info *opinfo = NULL;
324 DB_TXN *ltid = NULL;
325 OpExtra *oex;
326
327 Debug( LDAP_DEBUG_TRACE, "=> " LDAP_XSTRING(bdb_search) "\n", 0, 0, 0);
328 attrs = op->oq_search.rs_attrs;
329
330 LDAP_SLIST_FOREACH( oex, &op->o_extra, oe_next ) {
331 if ( oex->oe_key == bdb )
332 break;
333 }
334 opinfo = (struct bdb_op_info *) oex;
335
336 manageDSAit = get_manageDSAit( op );
337
338 if ( opinfo && opinfo->boi_txn ) {
339 ltid = opinfo->boi_txn;
340 locker = TXN_ID( ltid );
341 } else {
342 rs->sr_err = LOCK_ID( bdb->bi_dbenv, &locker );
343
344 switch(rs->sr_err) {
345 case 0:
346 break;
347 default:
348 send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
349 return rs->sr_err;
350 }
351 }
352
353 e_root = bdb->bi_cache.c_dntree.bei_e;
354 if ( op->o_req_ndn.bv_len == 0 ) {
355 /* DIT root special case */
356 ei = e_root->e_private;
357 rs->sr_err = LDAP_SUCCESS;
358 } else {
359 if ( op->ors_deref & LDAP_DEREF_FINDING ) {
360 BDB_IDL_ZERO(candidates);
361 }
362 dn2entry_retry:
363 /* get entry with reader lock */
364 rs->sr_err = bdb_dn2entry( op, ltid, &op->o_req_ndn, &ei,
365 1, locker, &lock );
366 }
367
368 switch(rs->sr_err) {
369 case DB_NOTFOUND:
370 matched = ei->bei_e;
371 break;
372 case 0:
373 e = ei->bei_e;
374 break;
375 case LDAP_BUSY:
376 send_ldap_error( op, rs, LDAP_BUSY, "ldap server busy" );
377 if ( !opinfo )
378 LOCK_ID_FREE (bdb->bi_dbenv, locker );
379 return LDAP_BUSY;
380 case DB_LOCK_DEADLOCK:
381 case DB_LOCK_NOTGRANTED:
382 goto dn2entry_retry;
383 default:
384 send_ldap_error( op, rs, LDAP_OTHER, "internal error" );
385 if ( !opinfo )
386 LOCK_ID_FREE (bdb->bi_dbenv, locker );
387 return rs->sr_err;
388 }
389
390 if ( op->ors_deref & LDAP_DEREF_FINDING ) {
391 if ( matched && is_entry_alias( matched )) {
392 struct berval stub;
393
394 stub.bv_val = op->o_req_ndn.bv_val;
395 stub.bv_len = op->o_req_ndn.bv_len - matched->e_nname.bv_len - 1;
396 e = deref_base( op, rs, matched, &matched, locker, &lock,
397 candidates, NULL );
398 if ( e ) {
399 build_new_dn( &op->o_req_ndn, &e->e_nname, &stub,
400 op->o_tmpmemctx );
401 bdb_cache_return_entry_r (bdb, e, &lock);
402 matched = NULL;
403 goto dn2entry_retry;
404 }
405 } else if ( e && is_entry_alias( e )) {
406 e = deref_base( op, rs, e, &matched, locker, &lock,
407 candidates, NULL );
408 }
409 }
410
411 if ( e == NULL ) {
412 struct berval matched_dn = BER_BVNULL;
413
414 if ( matched != NULL ) {
415 BerVarray erefs = NULL;
416
417 /* return referral only if "disclose"
418 * is granted on the object */
419 if ( ! access_allowed( op, matched,
420 slap_schema.si_ad_entry,
421 NULL, ACL_DISCLOSE, NULL ) )
422 {
423 rs->sr_err = LDAP_NO_SUCH_OBJECT;
424
425 } else {
426 ber_dupbv( &matched_dn, &matched->e_name );
427
428 erefs = is_entry_referral( matched )
429 ? get_entry_referrals( op, matched )
430 : NULL;
431 if ( rs->sr_err == DB_NOTFOUND )
432 rs->sr_err = LDAP_REFERRAL;
433 rs->sr_matched = matched_dn.bv_val;
434 }
435
436 #ifdef SLAP_ZONE_ALLOC
437 slap_zn_runlock(bdb->bi_cache.c_zctx, matched);
438 #endif
439 bdb_cache_return_entry_r (bdb, matched, &lock);
440 matched = NULL;
441
442 if ( erefs ) {
443 rs->sr_ref = referral_rewrite( erefs, &matched_dn,
444 &op->o_req_dn, op->oq_search.rs_scope );
445 ber_bvarray_free( erefs );
446 }
447
448 } else {
449 #ifdef SLAP_ZONE_ALLOC
450 slap_zn_runlock(bdb->bi_cache.c_zctx, matched);
451 #endif
452 rs->sr_ref = referral_rewrite( default_referral,
453 NULL, &op->o_req_dn, op->oq_search.rs_scope );
454 rs->sr_err = rs->sr_ref != NULL ? LDAP_REFERRAL : LDAP_NO_SUCH_OBJECT;
455 }
456
457 send_ldap_result( op, rs );
458
459 if ( !opinfo )
460 LOCK_ID_FREE (bdb->bi_dbenv, locker );
461 if ( rs->sr_ref ) {
462 ber_bvarray_free( rs->sr_ref );
463 rs->sr_ref = NULL;
464 }
465 if ( !BER_BVISNULL( &matched_dn ) ) {
466 ber_memfree( matched_dn.bv_val );
467 rs->sr_matched = NULL;
468 }
469 return rs->sr_err;
470 }
471
472 /* NOTE: __NEW__ "search" access is required
473 * on searchBase object */
474 if ( ! access_allowed_mask( op, e, slap_schema.si_ad_entry,
475 NULL, ACL_SEARCH, NULL, &mask ) )
476 {
477 if ( !ACL_GRANT( mask, ACL_DISCLOSE ) ) {
478 rs->sr_err = LDAP_NO_SUCH_OBJECT;
479 } else {
480 rs->sr_err = LDAP_INSUFFICIENT_ACCESS;
481 }
482
483 #ifdef SLAP_ZONE_ALLOC
484 slap_zn_runlock(bdb->bi_cache.c_zctx, e);
485 #endif
486 if ( e != e_root ) {
487 bdb_cache_return_entry_r(bdb, e, &lock);
488 }
489 send_ldap_result( op, rs );
490 return rs->sr_err;
491 }
492
493 if ( !manageDSAit && e != e_root && is_entry_referral( e ) ) {
494 /* entry is a referral, don't allow add */
495 struct berval matched_dn = BER_BVNULL;
496 BerVarray erefs = NULL;
497
498 ber_dupbv( &matched_dn, &e->e_name );
499 erefs = get_entry_referrals( op, e );
500
501 rs->sr_err = LDAP_REFERRAL;
502
503 #ifdef SLAP_ZONE_ALLOC
504 slap_zn_runlock(bdb->bi_cache.c_zctx, e);
505 #endif
506 bdb_cache_return_entry_r( bdb, e, &lock );
507 e = NULL;
508
509 if ( erefs ) {
510 rs->sr_ref = referral_rewrite( erefs, &matched_dn,
511 &op->o_req_dn, op->oq_search.rs_scope );
512 ber_bvarray_free( erefs );
513
514 if ( !rs->sr_ref ) {
515 rs->sr_text = "bad_referral object";
516 }
517 }
518
519 Debug( LDAP_DEBUG_TRACE,
520 LDAP_XSTRING(bdb_search) ": entry is referral\n",
521 0, 0, 0 );
522
523 rs->sr_matched = matched_dn.bv_val;
524 send_ldap_result( op, rs );
525
526 if ( !opinfo ) {
527 LOCK_ID_FREE (bdb->bi_dbenv, locker );
528 }
529 ber_bvarray_free( rs->sr_ref );
530 rs->sr_ref = NULL;
531 ber_memfree( matched_dn.bv_val );
532 rs->sr_matched = NULL;
533 return 1;
534 }
535
536 if ( get_assert( op ) &&
537 ( test_filter( op, e, get_assertion( op )) != LDAP_COMPARE_TRUE ))
538 {
539 rs->sr_err = LDAP_ASSERTION_FAILED;
540 #ifdef SLAP_ZONE_ALLOC
541 slap_zn_runlock(bdb->bi_cache.c_zctx, e);
542 #endif
543 if ( e != e_root ) {
544 bdb_cache_return_entry_r(bdb, e, &lock);
545 }
546 send_ldap_result( op, rs );
547 return 1;
548 }
549
550 /* compute it anyway; root does not use it */
551 stoptime = op->o_time + op->ors_tlimit;
552
553 /* need normalized dn below */
554 ber_dupbv( &realbase, &e->e_nname );
555
556 /* Copy info to base, must free entry before accessing the database
557 * in search_candidates, to avoid deadlocks.
558 */
559 base.e_private = e->e_private;
560 base.e_nname = realbase;
561 base.e_id = e->e_id;
562
563 #ifdef SLAP_ZONE_ALLOC
564 slap_zn_runlock(bdb->bi_cache.c_zctx, e);
565 #endif
566 if ( e != e_root ) {
567 bdb_cache_return_entry_r(bdb, e, &lock);
568 }
569 e = NULL;
570
571 /* select candidates */
572 if ( op->oq_search.rs_scope == LDAP_SCOPE_BASE ) {
573 rs->sr_err = base_candidate( op->o_bd, &base, candidates );
574
575 } else {
576 BDB_IDL_ZERO( candidates );
577 BDB_IDL_ZERO( scopes );
578 rs->sr_err = search_candidates( op, rs, &base,
579 locker, candidates, scopes );
580 }
581
582 /* start cursor at beginning of candidates.
583 */
584 cursor = 0;
585
586 if ( candidates[0] == 0 ) {
587 Debug( LDAP_DEBUG_TRACE,
588 LDAP_XSTRING(bdb_search) ": no candidates\n",
589 0, 0, 0 );
590
591 goto nochange;
592 }
593
594 /* if not root and candidates exceed to-be-checked entries, abort */
595 if ( op->ors_limit /* isroot == FALSE */ &&
596 op->ors_limit->lms_s_unchecked != -1 &&
597 BDB_IDL_N(candidates) > (unsigned) op->ors_limit->lms_s_unchecked )
598 {
599 rs->sr_err = LDAP_ADMINLIMIT_EXCEEDED;
600 send_ldap_result( op, rs );
601 rs->sr_err = LDAP_SUCCESS;
602 goto done;
603 }
604
605 if ( op->ors_limit == NULL /* isroot == TRUE */ ||
606 !op->ors_limit->lms_s_pr_hide )
607 {
608 tentries = BDB_IDL_N(candidates);
609 }
610
611 if ( get_pagedresults( op ) > SLAP_CONTROL_IGNORED ) {
612 PagedResultsState *ps = op->o_pagedresults_state;
613 /* deferred cookie parsing */
614 rs->sr_err = parse_paged_cookie( op, rs );
615 if ( rs->sr_err != LDAP_SUCCESS ) {
616 send_ldap_result( op, rs );
617 goto done;
618 }
619
620 cursor = (ID) ps->ps_cookie;
621 if ( cursor && ps->ps_size == 0 ) {
622 rs->sr_err = LDAP_SUCCESS;
623 rs->sr_text = "search abandoned by pagedResult size=0";
624 send_ldap_result( op, rs );
625 goto done;
626 }
627 id = bdb_idl_first( candidates, &cursor );
628 if ( id == NOID ) {
629 Debug( LDAP_DEBUG_TRACE,
630 LDAP_XSTRING(bdb_search)
631 ": no paged results candidates\n",
632 0, 0, 0 );
633 send_paged_response( op, rs, &lastid, 0 );
634
635 rs->sr_err = LDAP_OTHER;
636 goto done;
637 }
638 nentries = ps->ps_count;
639 if ( id == (ID)ps->ps_cookie )
640 id = bdb_idl_next( candidates, &cursor );
641 goto loop_begin;
642 }
643
644 for ( id = bdb_idl_first( candidates, &cursor );
645 id != NOID ; id = bdb_idl_next( candidates, &cursor ) )
646 {
647 int scopeok;
648
649 loop_begin:
650
651 /* check for abandon */
652 if ( op->o_abandon ) {
653 rs->sr_err = SLAPD_ABANDON;
654 goto done;
655 }
656
657 /* mostly needed by internal searches,
658 * e.g. related to syncrepl, for whom
659 * abandon does not get set... */
660 if ( slapd_shutdown ) {
661 rs->sr_err = LDAP_UNAVAILABLE;
662 send_ldap_disconnect( op, rs );
663 goto done;
664 }
665
666 /* check time limit */
667 if ( op->ors_tlimit != SLAP_NO_LIMIT
668 && slap_get_time() > stoptime )
669 {
670 rs->sr_err = LDAP_TIMELIMIT_EXCEEDED;
671 rs->sr_ref = rs->sr_v2ref;
672 send_ldap_result( op, rs );
673 rs->sr_err = LDAP_SUCCESS;
674 goto done;
675 }
676
677 /* If we inspect more entries than will
678 * fit into the entry cache, stop caching
679 * any subsequent entries
680 */
681 nentries++;
682 if ( nentries > bdb->bi_cache.c_maxsize && !idflag )
683 idflag = ID_NOCACHE;
684
685 fetch_entry_retry:
686 /* get the entry with reader lock */
687 ei = NULL;
688 rs->sr_err = bdb_cache_find_id( op, ltid,
689 id, &ei, idflag, locker, &lock );
690
691 if (rs->sr_err == LDAP_BUSY) {
692 rs->sr_text = "ldap server busy";
693 send_ldap_result( op, rs );
694 goto done;
695
696 } else if ( rs->sr_err == DB_LOCK_DEADLOCK
697 || rs->sr_err == DB_LOCK_NOTGRANTED )
698 {
699 goto fetch_entry_retry;
700 } else if ( rs->sr_err == LDAP_OTHER ) {
701 rs->sr_text = "internal error";
702 send_ldap_result( op, rs );
703 goto done;
704 }
705
706 if ( ei && rs->sr_err == LDAP_SUCCESS ) {
707 e = ei->bei_e;
708 } else {
709 e = NULL;
710 }
711
712 if ( e == NULL ) {
713 if( !BDB_IDL_IS_RANGE(candidates) ) {
714 /* only complain for non-range IDLs */
715 Debug( LDAP_DEBUG_TRACE,
716 LDAP_XSTRING(bdb_search)
717 ": candidate %ld not found\n",
718 (long) id, 0, 0 );
719 }
720
721 goto loop_continue;
722 }
723
724 rs->sr_entry = e;
725
726 if ( is_entry_subentry( e ) ) {
727 if( op->oq_search.rs_scope != LDAP_SCOPE_BASE ) {
728 if(!get_subentries_visibility( op )) {
729 /* only subentries are visible */
730 goto loop_continue;
731 }
732
733 } else if ( get_subentries( op ) &&
734 !get_subentries_visibility( op ))
735 {
736 /* only subentries are visible */
737 goto loop_continue;
738 }
739
740 } else if ( get_subentries_visibility( op )) {
741 /* only subentries are visible */
742 goto loop_continue;
743 }
744
745 /* Does this candidate actually satisfy the search scope?
746 *
747 * Note that we don't lock access to the bei_parent pointer.
748 * Since only leaf nodes can be deleted, the parent of any
749 * node will always be a valid node. Also since we have
750 * a Read lock on the data, it cannot be renamed out of the
751 * scope while we are looking at it, and unless we're using
752 * BDB_HIER, its parents cannot be moved either.
753 */
754 scopeok = 0;
755 switch( op->ors_scope ) {
756 case LDAP_SCOPE_BASE:
757 /* This is always true, yes? */
758 if ( id == base.e_id ) scopeok = 1;
759 break;
760
761 case LDAP_SCOPE_ONELEVEL:
762 if ( ei->bei_parent->bei_id == base.e_id ) scopeok = 1;
763 break;
764
765 #ifdef LDAP_SCOPE_CHILDREN
766 case LDAP_SCOPE_CHILDREN:
767 if ( id == base.e_id ) break;
768 /* Fall-thru */
769 #endif
770 case LDAP_SCOPE_SUBTREE: {
771 EntryInfo *tmp;
772 for ( tmp = BEI(e); tmp; tmp = tmp->bei_parent ) {
773 if ( tmp->bei_id == base.e_id ) {
774 scopeok = 1;
775 break;
776 }
777 }
778 } break;
779 }
780
781 /* aliases were already dereferenced in candidate list */
782 if ( op->ors_deref & LDAP_DEREF_SEARCHING ) {
783 /* but if the search base is an alias, and we didn't
784 * deref it when finding, return it.
785 */
786 if ( is_entry_alias(e) &&
787 ((op->ors_deref & LDAP_DEREF_FINDING) ||
788 !bvmatch(&e->e_nname, &op->o_req_ndn)))
789 {
790 goto loop_continue;
791 }
792
793 /* scopes is only non-empty for onelevel or subtree */
794 if ( !scopeok && BDB_IDL_N(scopes) ) {
795 unsigned x;
796 if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) {
797 x = bdb_idl_search( scopes, e->e_id );
798 if ( scopes[x] == e->e_id ) scopeok = 1;
799 } else {
800 /* subtree, walk up the tree */
801 EntryInfo *tmp = BEI(e);
802 for (;tmp->bei_parent; tmp=tmp->bei_parent) {
803 x = bdb_idl_search( scopes, tmp->bei_id );
804 if ( scopes[x] == tmp->bei_id ) {
805 scopeok = 1;
806 break;
807 }
808 }
809 }
810 }
811 }
812
813 /* Not in scope, ignore it */
814 if ( !scopeok )
815 {
816 Debug( LDAP_DEBUG_TRACE,
817 LDAP_XSTRING(bdb_search)
818 ": %ld scope not okay\n",
819 (long) id, 0, 0 );
820 goto loop_continue;
821 }
822
823 /*
824 * if it's a referral, add it to the list of referrals. only do
825 * this for non-base searches, and don't check the filter
826 * explicitly here since it's only a candidate anyway.
827 */
828 if ( !manageDSAit && op->oq_search.rs_scope != LDAP_SCOPE_BASE
829 && is_entry_referral( e ) )
830 {
831 BerVarray erefs = get_entry_referrals( op, e );
832 rs->sr_ref = referral_rewrite( erefs, &e->e_name, NULL,
833 op->oq_search.rs_scope == LDAP_SCOPE_ONELEVEL
834 ? LDAP_SCOPE_BASE : LDAP_SCOPE_SUBTREE );
835
836 send_search_reference( op, rs );
837
838 ber_bvarray_free( rs->sr_ref );
839 ber_bvarray_free( erefs );
840 rs->sr_ref = NULL;
841
842 goto loop_continue;
843 }
844
845 if ( !manageDSAit && is_entry_glue( e )) {
846 goto loop_continue;
847 }
848
849 /* if it matches the filter and scope, send it */
850 rs->sr_err = test_filter( op, rs->sr_entry, op->oq_search.rs_filter );
851
852 if ( rs->sr_err == LDAP_COMPARE_TRUE ) {
853 /* check size limit */
854 if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) {
855 if ( rs->sr_nentries >= ((PagedResultsState *)op->o_pagedresults_state)->ps_size ) {
856 #ifdef SLAP_ZONE_ALLOC
857 slap_zn_runlock(bdb->bi_cache.c_zctx, e);
858 #endif
859 bdb_cache_return_entry_r( bdb, e, &lock );
860 e = NULL;
861 send_paged_response( op, rs, &lastid, tentries );
862 goto done;
863 }
864 lastid = id;
865 }
866
867 if (e) {
868 /* safe default */
869 rs->sr_attrs = op->oq_search.rs_attrs;
870 rs->sr_operational_attrs = NULL;
871 rs->sr_ctrls = NULL;
872 rs->sr_flags = 0;
873 rs->sr_err = LDAP_SUCCESS;
874 rs->sr_err = send_search_entry( op, rs );
875
876 switch ( rs->sr_err ) {
877 case LDAP_SUCCESS: /* entry sent ok */
878 break;
879 default: /* entry not sent */
880 break;
881 case LDAP_UNAVAILABLE:
882 case LDAP_SIZELIMIT_EXCEEDED:
883 #ifdef SLAP_ZONE_ALLOC
884 slap_zn_runlock(bdb->bi_cache.c_zctx, e);
885 #endif
886 bdb_cache_return_entry_r(bdb, e, &lock);
887 e = NULL;
888 rs->sr_entry = NULL;
889 if ( rs->sr_err == LDAP_SIZELIMIT_EXCEEDED ) {
890 rs->sr_ref = rs->sr_v2ref;
891 send_ldap_result( op, rs );
892 rs->sr_err = LDAP_SUCCESS;
893
894 } else {
895 rs->sr_err = LDAP_OTHER;
896 }
897 goto done;
898 }
899 }
900
901 } else {
902 Debug( LDAP_DEBUG_TRACE,
903 LDAP_XSTRING(bdb_search)
904 ": %ld does not match filter\n",
905 (long) id, 0, 0 );
906 }
907
908 loop_continue:
909 if( e != NULL ) {
910 /* free reader lock */
911 #ifdef SLAP_ZONE_ALLOC
912 slap_zn_runlock(bdb->bi_cache.c_zctx, e);
913 #endif
914 bdb_cache_return_entry_r( bdb, e , &lock );
915 e = NULL;
916 rs->sr_entry = NULL;
917 }
918 }
919
920 nochange:
921 rs->sr_ctrls = NULL;
922 rs->sr_ref = rs->sr_v2ref;
923 rs->sr_err = (rs->sr_v2ref == NULL) ? LDAP_SUCCESS : LDAP_REFERRAL;
924 rs->sr_rspoid = NULL;
925 if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) {
926 send_paged_response( op, rs, NULL, 0 );
927 } else {
928 send_ldap_result( op, rs );
929 }
930
931 rs->sr_err = LDAP_SUCCESS;
932
933 done:
934 if ( !opinfo )
935 LOCK_ID_FREE( bdb->bi_dbenv, locker );
936
937 if( rs->sr_v2ref ) {
938 ber_bvarray_free( rs->sr_v2ref );
939 rs->sr_v2ref = NULL;
940 }
941 if( realbase.bv_val ) ch_free( realbase.bv_val );
942
943 return rs->sr_err;
944 }
945
946
947 static int base_candidate(
948 BackendDB *be,
949 Entry *e,
950 ID *ids )
951 {
952 Debug(LDAP_DEBUG_ARGS, "base_candidates: base: \"%s\" (0x%08lx)\n",
953 e->e_nname.bv_val, (long) e->e_id, 0);
954
955 ids[0] = 1;
956 ids[1] = e->e_id;
957 return 0;
958 }
959
960 /* Look for "objectClass Present" in this filter.
961 * Also count depth of filter tree while we're at it.
962 */
963 static int oc_filter(
964 Filter *f,
965 int cur,
966 int *max )
967 {
968 int rc = 0;
969
970 assert( f != NULL );
971
972 if( cur > *max ) *max = cur;
973
974 switch( f->f_choice ) {
975 case LDAP_FILTER_PRESENT:
976 if (f->f_desc == slap_schema.si_ad_objectClass) {
977 rc = 1;
978 }
979 break;
980
981 case LDAP_FILTER_AND:
982 case LDAP_FILTER_OR:
983 cur++;
984 for ( f=f->f_and; f; f=f->f_next ) {
985 (void) oc_filter(f, cur, max);
986 }
987 break;
988
989 default:
990 break;
991 }
992 return rc;
993 }
994
995 static void search_stack_free( void *key, void *data )
996 {
997 ber_memfree_x(data, NULL);
998 }
999
1000 static void *search_stack( Operation *op )
1001 {
1002 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
1003 void *ret = NULL;
1004
1005 if ( op->o_threadctx ) {
1006 ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)search_stack,
1007 &ret, NULL );
1008 } else {
1009 ret = bdb->bi_search_stack;
1010 }
1011
1012 if ( !ret ) {
1013 ret = ch_malloc( bdb->bi_search_stack_depth * BDB_IDL_UM_SIZE
1014 * sizeof( ID ) );
1015 if ( op->o_threadctx ) {
1016 ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)search_stack,
1017 ret, search_stack_free, NULL, NULL );
1018 } else {
1019 bdb->bi_search_stack = ret;
1020 }
1021 }
1022 return ret;
1023 }
1024
1025 static int search_candidates(
1026 Operation *op,
1027 SlapReply *rs,
1028 Entry *e,
1029 BDB_LOCKER locker,
1030 ID *ids,
1031 ID *scopes )
1032 {
1033 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
1034 int rc, depth = 1;
1035 Filter f, rf, xf, nf;
1036 ID *stack;
1037 AttributeAssertion aa_ref = ATTRIBUTEASSERTION_INIT;
1038 Filter sf;
1039 AttributeAssertion aa_subentry = ATTRIBUTEASSERTION_INIT;
1040
1041 /*
1042 * This routine takes as input a filter (user-filter)
1043 * and rewrites it as follows:
1044 * (&(scope=DN)[(objectClass=subentry)]
1045 * (|[(objectClass=referral)(objectClass=alias)](user-filter))
1046 */
1047
1048 Debug(LDAP_DEBUG_TRACE,
1049 "search_candidates: base=\"%s\" (0x%08lx) scope=%d\n",
1050 e->e_nname.bv_val, (long) e->e_id, op->oq_search.rs_scope );
1051
1052 xf.f_or = op->oq_search.rs_filter;
1053 xf.f_choice = LDAP_FILTER_OR;
1054 xf.f_next = NULL;
1055
1056 /* If the user's filter uses objectClass=*,
1057 * these clauses are redundant.
1058 */
1059 if (!oc_filter(op->oq_search.rs_filter, 1, &depth)
1060 && !get_subentries_visibility(op)) {
1061 if( !get_manageDSAit(op) && !get_domainScope(op) ) {
1062 /* match referral objects */
1063 struct berval bv_ref = BER_BVC( "referral" );
1064 rf.f_choice = LDAP_FILTER_EQUALITY;
1065 rf.f_ava = &aa_ref;
1066 rf.f_av_desc = slap_schema.si_ad_objectClass;
1067 rf.f_av_value = bv_ref;
1068 rf.f_next = xf.f_or;
1069 xf.f_or = &rf;
1070 depth++;
1071 }
1072 }
1073
1074 f.f_next = NULL;
1075 f.f_choice = LDAP_FILTER_AND;
1076 f.f_and = &nf;
1077 /* Dummy; we compute scope separately now */
1078 nf.f_choice = SLAPD_FILTER_COMPUTED;
1079 nf.f_result = LDAP_SUCCESS;
1080 nf.f_next = ( xf.f_or == op->oq_search.rs_filter )
1081 ? op->oq_search.rs_filter : &xf ;
1082 /* Filter depth increased again, adding dummy clause */
1083 depth++;
1084
1085 if( get_subentries_visibility( op ) ) {
1086 struct berval bv_subentry = BER_BVC( "subentry" );
1087 sf.f_choice = LDAP_FILTER_EQUALITY;
1088 sf.f_ava = &aa_subentry;
1089 sf.f_av_desc = slap_schema.si_ad_objectClass;
1090 sf.f_av_value = bv_subentry;
1091 sf.f_next = nf.f_next;
1092 nf.f_next = &sf;
1093 }
1094
1095 /* Allocate IDL stack, plus 1 more for former tmp */
1096 if ( depth+1 > bdb->bi_search_stack_depth ) {
1097 stack = ch_malloc( (depth + 1) * BDB_IDL_UM_SIZE * sizeof( ID ) );
1098 } else {
1099 stack = search_stack( op );
1100 }
1101
1102 if( op->ors_deref & LDAP_DEREF_SEARCHING ) {
1103 rc = search_aliases( op, rs, e, locker, ids, scopes, stack );
1104 } else {
1105 rc = bdb_dn2idl( op, locker, &e->e_nname, BEI(e), ids, stack );
1106 }
1107
1108 if ( rc == LDAP_SUCCESS ) {
1109 rc = bdb_filter_candidates( op, locker, &f, ids,
1110 stack, stack+BDB_IDL_UM_SIZE );
1111 }
1112
1113 if ( depth+1 > bdb->bi_search_stack_depth ) {
1114 ch_free( stack );
1115 }
1116
1117 if( rc ) {
1118 Debug(LDAP_DEBUG_TRACE,
1119 "bdb_search_candidates: failed (rc=%d)\n",
1120 rc, NULL, NULL );
1121
1122 } else {
1123 Debug(LDAP_DEBUG_TRACE,
1124 "bdb_search_candidates: id=%ld first=%ld last=%ld\n",
1125 (long) ids[0],
1126 (long) BDB_IDL_FIRST(ids),
1127 (long) BDB_IDL_LAST(ids) );
1128 }
1129
1130 return rc;
1131 }
1132
1133 static int
1134 parse_paged_cookie( Operation *op, SlapReply *rs )
1135 {
1136 int rc = LDAP_SUCCESS;
1137 PagedResultsState *ps = op->o_pagedresults_state;
1138
1139 /* this function must be invoked only if the pagedResults
1140 * control has been detected, parsed and partially checked
1141 * by the frontend */
1142 assert( get_pagedresults( op ) > SLAP_CONTROL_IGNORED );
1143
1144 /* cookie decoding/checks deferred to backend... */
1145 if ( ps->ps_cookieval.bv_len ) {
1146 PagedResultsCookie reqcookie;
1147 if( ps->ps_cookieval.bv_len != sizeof( reqcookie ) ) {
1148 /* bad cookie */
1149 rs->sr_text = "paged results cookie is invalid";
1150 rc = LDAP_PROTOCOL_ERROR;
1151 goto done;
1152 }
1153
1154 AC_MEMCPY( &reqcookie, ps->ps_cookieval.bv_val, sizeof( reqcookie ));
1155
1156 if ( reqcookie > ps->ps_cookie ) {
1157 /* bad cookie */
1158 rs->sr_text = "paged results cookie is invalid";
1159 rc = LDAP_PROTOCOL_ERROR;
1160 goto done;
1161
1162 } else if ( reqcookie < ps->ps_cookie ) {
1163 rs->sr_text = "paged results cookie is invalid or old";
1164 rc = LDAP_UNWILLING_TO_PERFORM;
1165 goto done;
1166 }
1167
1168 }
1169
1170 done:;
1171
1172 return rc;
1173 }
1174
1175 static void
1176 send_paged_response(
1177 Operation *op,
1178 SlapReply *rs,
1179 ID *lastid,
1180 int tentries )
1181 {
1182 LDAPControl ctrl, *ctrls[2];
1183 BerElementBuffer berbuf;
1184 BerElement *ber = (BerElement *)&berbuf;
1185 PagedResultsCookie respcookie;
1186 struct berval cookie;
1187
1188 Debug(LDAP_DEBUG_ARGS,
1189 "send_paged_response: lastid=0x%08lx nentries=%d\n",
1190 lastid ? *lastid : 0, rs->sr_nentries, NULL );
1191
1192 BER_BVZERO( &ctrl.ldctl_value );
1193 ctrls[0] = &ctrl;
1194 ctrls[1] = NULL;
1195
1196 ber_init2( ber, NULL, LBER_USE_DER );
1197
1198 if ( lastid ) {
1199 respcookie = ( PagedResultsCookie )(*lastid);
1200 cookie.bv_len = sizeof( respcookie );
1201 cookie.bv_val = (char *)&respcookie;
1202
1203 } else {
1204 respcookie = ( PagedResultsCookie )0;
1205 BER_BVSTR( &cookie, "" );
1206 }
1207
1208 op->o_conn->c_pagedresults_state.ps_cookie = respcookie;
1209 op->o_conn->c_pagedresults_state.ps_count =
1210 ((PagedResultsState *)op->o_pagedresults_state)->ps_count +
1211 rs->sr_nentries;
1212
1213 /* return size of 0 -- no estimate */
1214 ber_printf( ber, "{iO}", 0, &cookie );
1215
1216 if ( ber_flatten2( ber, &ctrls[0]->ldctl_value, 0 ) == -1 ) {
1217 goto done;
1218 }
1219
1220 ctrls[0]->ldctl_oid = LDAP_CONTROL_PAGEDRESULTS;
1221 ctrls[0]->ldctl_iscritical = 0;
1222
1223 rs->sr_ctrls = ctrls;
1224 rs->sr_err = LDAP_SUCCESS;
1225 send_ldap_result( op, rs );
1226 rs->sr_ctrls = NULL;
1227
1228 done:
1229 (void) ber_free_buf( ber );
1230 }
1231
NetBSD on the FriendlyARM MINI2440