1 /* $NetBSD: search.c,v 1.2 2021/08/14 16:15:02 christos Exp $ */ 2 3 /* OpenLDAP WiredTiger backend */ 4 /* $OpenLDAP$ */ 5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>. 6 * 7 * Copyright 2002-2021 The OpenLDAP Foundation. 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted only as authorized by the OpenLDAP 12 * Public License. 13 * 14 * A copy of this license is available in the file LICENSE in the 15 * top-level directory of the distribution or, alternatively, at 16 * <http://www.OpenLDAP.org/license.html>. 17 */ 18 /* ACKNOWLEDGEMENTS: 19 * This work was developed by HAMANO Tsukasa <hamano@osstech.co.jp> 20 * based on back-bdb for inclusion in OpenLDAP Software. 21 * WiredTiger is a product of MongoDB Inc. 22 */ 23 24 #include <sys/cdefs.h> 25 __RCSID("$NetBSD: search.c,v 1.2 2021/08/14 16:15:02 christos Exp $"); 26 27 #include "portable.h" 28 29 #include <stdio.h> 30 #include <ac/string.h> 31 32 #include "back-wt.h" 33 #include "idl.h" 34 35 static int search_aliases( 36 Operation *op, 37 SlapReply *rs, 38 Entry *e, 39 WT_SESSION *session, 40 ID *ids, 41 ID *scopes, 42 ID *stack ) 43 { 44 /* TODO: search_aliases does not implement yet. */ 45 WT_IDL_ZERO( ids ); 46 return 0; 47 } 48 49 static int base_candidate( 50 BackendDB *be, 51 Entry *e, 52 ID *ids ) 53 { 54 Debug(LDAP_DEBUG_ARGS, 55 LDAP_XSTRING(base_candidate) 56 ": base: \"%s\" (0x%08lx)\n", 57 e->e_nname.bv_val, (long) e->e_id ); 58 59 ids[0] = 1; 60 ids[1] = e->e_id; 61 return 0; 62 } 63 64 /* Look for "objectClass Present" in this filter. 65 * Also count depth of filter tree while we're at it. 66 */ 67 static int oc_filter( 68 Filter *f, 69 int cur, 70 int *max ) 71 { 72 int rc = 0; 73 74 assert( f != NULL ); 75 76 if( cur > *max ) *max = cur; 77 78 switch( f->f_choice ) { 79 case LDAP_FILTER_PRESENT: 80 if (f->f_desc == slap_schema.si_ad_objectClass) { 81 rc = 1; 82 } 83 break; 84 85 case LDAP_FILTER_AND: 86 case LDAP_FILTER_OR: 87 cur++; 88 for ( f=f->f_and; f; f=f->f_next ) { 89 (void) oc_filter(f, cur, max); 90 } 91 break; 92 93 default: 94 break; 95 } 96 return rc; 97 } 98 99 static void search_stack_free( void *key, void *data ) 100 { 101 ber_memfree_x(data, NULL); 102 } 103 104 static void *search_stack( Operation *op ) 105 { 106 struct wt_info *wi = (struct wt_info *) op->o_bd->be_private; 107 void *ret = NULL; 108 109 if ( op->o_threadctx ) { 110 ldap_pvt_thread_pool_getkey( op->o_threadctx, (void *)search_stack, 111 &ret, NULL ); 112 } else { 113 ret = wi->wi_search_stack; 114 } 115 116 if ( !ret ) { 117 ret = ch_malloc( wi->wi_search_stack_depth * WT_IDL_UM_SIZE 118 * sizeof( ID ) ); 119 if ( op->o_threadctx ) { 120 ldap_pvt_thread_pool_setkey( op->o_threadctx, (void *)search_stack, 121 ret, search_stack_free, NULL, NULL ); 122 } else { 123 wi->wi_search_stack = ret; 124 } 125 } 126 return ret; 127 } 128 129 static int search_candidates( 130 Operation *op, 131 SlapReply *rs, 132 Entry *e, 133 wt_ctx *wc, 134 ID *ids, 135 ID *scopes ) 136 { 137 struct wt_info *wi = (struct wt_info *) op->o_bd->be_private; 138 int rc, depth = 1; 139 Filter f, rf, xf, nf; 140 ID *stack; 141 AttributeAssertion aa_ref = ATTRIBUTEASSERTION_INIT; 142 Filter sf; 143 AttributeAssertion aa_subentry = ATTRIBUTEASSERTION_INIT; 144 145 Debug(LDAP_DEBUG_TRACE, 146 LDAP_XSTRING(wt_search_candidates) 147 ": base=\"%s\" (0x%08lx) scope=%d\n", 148 e->e_nname.bv_val, (long) e->e_id, op->oq_search.rs_scope ); 149 150 xf.f_or = op->oq_search.rs_filter; 151 xf.f_choice = LDAP_FILTER_OR; 152 xf.f_next = NULL; 153 154 /* If the user's filter uses objectClass=*, 155 * these clauses are redundant. 156 */ 157 if (!oc_filter(op->oq_search.rs_filter, 1, &depth) 158 && !get_subentries_visibility(op)) { 159 if( !get_manageDSAit(op) && !get_domainScope(op) ) { 160 /* match referral objects */ 161 struct berval bv_ref = BER_BVC( "referral" ); 162 rf.f_choice = LDAP_FILTER_EQUALITY; 163 rf.f_ava = &aa_ref; 164 rf.f_av_desc = slap_schema.si_ad_objectClass; 165 rf.f_av_value = bv_ref; 166 rf.f_next = xf.f_or; 167 xf.f_or = &rf; 168 depth++; 169 } 170 } 171 172 f.f_next = NULL; 173 f.f_choice = LDAP_FILTER_AND; 174 f.f_and = &nf; 175 /* Dummy; we compute scope separately now */ 176 nf.f_choice = SLAPD_FILTER_COMPUTED; 177 nf.f_result = LDAP_SUCCESS; 178 nf.f_next = ( xf.f_or == op->oq_search.rs_filter ) 179 ? op->oq_search.rs_filter : &xf ; 180 /* Filter depth increased again, adding dummy clause */ 181 depth++; 182 183 if( get_subentries_visibility( op ) ) { 184 struct berval bv_subentry = BER_BVC( "subentry" ); 185 sf.f_choice = LDAP_FILTER_EQUALITY; 186 sf.f_ava = &aa_subentry; 187 sf.f_av_desc = slap_schema.si_ad_objectClass; 188 sf.f_av_value = bv_subentry; 189 sf.f_next = nf.f_next; 190 nf.f_next = &sf; 191 } 192 193 /* Allocate IDL stack, plus 1 more for former tmp */ 194 if ( depth+1 > wi->wi_search_stack_depth ) { 195 stack = ch_malloc( (depth + 1) * WT_IDL_UM_SIZE * sizeof( ID ) ); 196 } else { 197 stack = search_stack( op ); 198 } 199 200 if( op->ors_deref & LDAP_DEREF_SEARCHING ) { 201 rc = search_aliases( op, rs, e, wc->session, ids, scopes, stack ); 202 if ( WT_IDL_IS_ZERO( ids ) && rc == LDAP_SUCCESS ) 203 rc = wt_dn2idl( op, wc->session, &e->e_nname, e, ids, stack ); 204 } else { 205 rc = wt_dn2idl(op, wc->session, &e->e_nname, e, ids, stack ); 206 } 207 208 if ( rc == LDAP_SUCCESS ) { 209 rc = wt_filter_candidates( op, wc, &f, ids, 210 stack, stack+WT_IDL_UM_SIZE ); 211 } 212 213 if ( depth+1 > wi->wi_search_stack_depth ) { 214 ch_free( stack ); 215 } 216 217 if( rc ) { 218 Debug(LDAP_DEBUG_TRACE, 219 LDAP_XSTRING(wt_search_candidates) 220 ": failed (rc=%d)\n", 221 rc ); 222 223 } else { 224 Debug(LDAP_DEBUG_TRACE, 225 LDAP_XSTRING(wt_search_candidates) 226 ": id=%ld first=%ld last=%ld\n", 227 (long) ids[0], 228 (long) WT_IDL_FIRST(ids), 229 (long) WT_IDL_LAST(ids)); 230 } 231 return 0; 232 } 233 234 static int 235 parse_paged_cookie( Operation *op, SlapReply *rs ) 236 { 237 int rc = LDAP_SUCCESS; 238 PagedResultsState *ps = op->o_pagedresults_state; 239 240 /* this function must be invoked only if the pagedResults 241 * control has been detected, parsed and partially checked 242 * by the frontend */ 243 assert( get_pagedresults( op ) > SLAP_CONTROL_IGNORED ); 244 245 /* cookie decoding/checks deferred to backend... */ 246 if ( ps->ps_cookieval.bv_len ) { 247 PagedResultsCookie reqcookie; 248 if( ps->ps_cookieval.bv_len != sizeof( reqcookie ) ) { 249 /* bad cookie */ 250 rs->sr_text = "paged results cookie is invalid"; 251 rc = LDAP_PROTOCOL_ERROR; 252 goto done; 253 } 254 255 AC_MEMCPY( &reqcookie, ps->ps_cookieval.bv_val, sizeof( reqcookie )); 256 257 if ( reqcookie > ps->ps_cookie ) { 258 /* bad cookie */ 259 rs->sr_text = "paged results cookie is invalid"; 260 rc = LDAP_PROTOCOL_ERROR; 261 goto done; 262 263 } else if ( reqcookie < ps->ps_cookie ) { 264 rs->sr_text = "paged results cookie is invalid or old"; 265 rc = LDAP_UNWILLING_TO_PERFORM; 266 goto done; 267 } 268 269 } else { 270 /* we're going to use ps_cookie */ 271 op->o_conn->c_pagedresults_state.ps_cookie = 0; 272 } 273 274 done:; 275 276 return rc; 277 } 278 279 static void 280 send_paged_response( 281 Operation *op, 282 SlapReply *rs, 283 ID *lastid, 284 int tentries ) 285 { 286 LDAPControl *ctrls[2]; 287 BerElementBuffer berbuf; 288 BerElement *ber = (BerElement *)&berbuf; 289 PagedResultsCookie respcookie; 290 struct berval cookie; 291 292 Debug(LDAP_DEBUG_ARGS, 293 LDAP_XSTRING(send_paged_response) 294 ": lastid=0x%08lx nentries=%d\n", 295 lastid ? *lastid : 0, rs->sr_nentries ); 296 297 ctrls[1] = NULL; 298 299 ber_init2( ber, NULL, LBER_USE_DER ); 300 301 if ( lastid ) { 302 respcookie = ( PagedResultsCookie )(*lastid); 303 cookie.bv_len = sizeof( respcookie ); 304 cookie.bv_val = (char *)&respcookie; 305 306 } else { 307 respcookie = ( PagedResultsCookie )0; 308 BER_BVSTR( &cookie, "" ); 309 } 310 311 op->o_conn->c_pagedresults_state.ps_cookie = respcookie; 312 op->o_conn->c_pagedresults_state.ps_count = 313 ((PagedResultsState *)op->o_pagedresults_state)->ps_count + 314 rs->sr_nentries; 315 316 /* return size of 0 -- no estimate */ 317 ber_printf( ber, "{iO}", 0, &cookie ); 318 319 ctrls[0] = op->o_tmpalloc( sizeof(LDAPControl), op->o_tmpmemctx ); 320 if ( ber_flatten2( ber, &ctrls[0]->ldctl_value, 0 ) == -1 ) { 321 goto done; 322 } 323 324 ctrls[0]->ldctl_oid = LDAP_CONTROL_PAGEDRESULTS; 325 ctrls[0]->ldctl_iscritical = 0; 326 327 slap_add_ctrls( op, rs, ctrls ); 328 rs->sr_err = LDAP_SUCCESS; 329 send_ldap_result( op, rs ); 330 331 done: 332 (void) ber_free_buf( ber ); 333 } 334 335 int 336 wt_search( Operation *op, SlapReply *rs ) 337 { 338 struct wt_info *wi = (struct wt_info *) op->o_bd->be_private; 339 ID id, cursor; 340 ID lastid = NOID; 341 AttributeName *attrs; 342 OpExtra *oex; 343 int manageDSAit; 344 wt_ctx *wc; 345 int rc; 346 Entry *e = NULL; 347 Entry *base = NULL; 348 slap_mask_t mask; 349 time_t stoptime; 350 351 ID candidates[WT_IDL_UM_SIZE]; 352 ID iscopes[WT_IDL_DB_SIZE]; 353 ID scopes[WT_IDL_DB_SIZE]; 354 int tentries = 0; 355 unsigned nentries = 0; 356 357 Debug( LDAP_DEBUG_ARGS, "==> " LDAP_XSTRING(wt_search) ": %s\n", 358 op->o_req_dn.bv_val ); 359 attrs = op->oq_search.rs_attrs; 360 361 manageDSAit = get_manageDSAit( op ); 362 363 wc = wt_ctx_get(op, wi); 364 if( !wc ){ 365 Debug( LDAP_DEBUG_ANY, 366 LDAP_XSTRING(wt_search) 367 ": wt_ctx_get failed: %d\n", 368 rc ); 369 send_ldap_error( op, rs, LDAP_OTHER, "internal error" ); 370 return rc; 371 } 372 373 /* get entry */ 374 rc = wt_dn2entry(op->o_bd, wc, &op->o_req_ndn, &e); 375 switch( rc ) { 376 case 0: 377 break; 378 case WT_NOTFOUND: 379 Debug( LDAP_DEBUG_ARGS, 380 "<== " LDAP_XSTRING(wt_search) 381 ": no such object %s\n", 382 op->o_req_dn.bv_val ); 383 rs->sr_err = LDAP_REFERRAL; 384 rs->sr_flags = REP_MATCHED_MUSTBEFREED | REP_REF_MUSTBEFREED; 385 send_ldap_result( op, rs ); 386 goto done; 387 default: 388 /* TODO: error handling */ 389 Debug( LDAP_DEBUG_ANY, 390 LDAP_XSTRING(wt_delete) 391 ": error at wt_dn2entry() rc=%d\n", 392 rc ); 393 send_ldap_error( op, rs, LDAP_OTHER, "internal error" ); 394 goto done; 395 } 396 397 if ( op->ors_deref & LDAP_DEREF_FINDING ) { 398 /* not implement yet */ 399 } 400 401 if ( e == NULL ) { 402 // TODO 403 } 404 405 /* NOTE: __NEW__ "search" access is required 406 * on searchBase object */ 407 if ( ! access_allowed_mask( op, e, slap_schema.si_ad_entry, 408 NULL, ACL_SEARCH, NULL, &mask ) ) 409 { 410 if ( !ACL_GRANT( mask, ACL_DISCLOSE ) ) { 411 rs->sr_err = LDAP_NO_SUCH_OBJECT; 412 } else { 413 rs->sr_err = LDAP_INSUFFICIENT_ACCESS; 414 } 415 416 send_ldap_result( op, rs ); 417 goto done; 418 } 419 420 if ( !manageDSAit && is_entry_referral( e ) ) { 421 /* entry is a referral */ 422 /* TODO: */ 423 } 424 425 if ( get_assert( op ) && 426 ( test_filter( op, e, get_assertion( op )) != LDAP_COMPARE_TRUE )) 427 { 428 rs->sr_err = LDAP_ASSERTION_FAILED; 429 send_ldap_result( op, rs ); 430 goto done; 431 } 432 433 /* compute it anyway; root does not use it */ 434 stoptime = op->o_time + op->ors_tlimit; 435 436 base = e; 437 438 e = NULL; 439 440 /* select candidates */ 441 if ( op->oq_search.rs_scope == LDAP_SCOPE_BASE ) { 442 rs->sr_err = base_candidate( op->o_bd, base, candidates ); 443 }else{ 444 WT_IDL_ZERO( candidates ); 445 WT_IDL_ZERO( scopes ); 446 rc = search_candidates( op, rs, base, 447 wc, candidates, scopes ); 448 switch(rc){ 449 case 0: 450 case WT_NOTFOUND: 451 break; 452 default: 453 Debug( LDAP_DEBUG_ANY, 454 LDAP_XSTRING(wt_search) ": error search_candidates\n" ); 455 send_ldap_error( op, rs, LDAP_OTHER, "internal error" ); 456 goto done; 457 } 458 } 459 460 /* start cursor at beginning of candidates. 461 */ 462 cursor = 0; 463 464 if ( candidates[0] == 0 ) { 465 Debug( LDAP_DEBUG_TRACE, 466 LDAP_XSTRING(wt_search) ": no candidates\n" ); 467 goto nochange; 468 } 469 470 if ( op->ors_limit && 471 op->ors_limit->lms_s_unchecked != -1 && 472 WT_IDL_N(candidates) > (unsigned) op->ors_limit->lms_s_unchecked ) 473 { 474 rs->sr_err = LDAP_ADMINLIMIT_EXCEEDED; 475 send_ldap_result( op, rs ); 476 rs->sr_err = LDAP_SUCCESS; 477 goto done; 478 } 479 480 if ( op->ors_limit == NULL /* isroot == TRUE */ || 481 !op->ors_limit->lms_s_pr_hide ) 482 { 483 tentries = WT_IDL_N(candidates); 484 } 485 486 if ( get_pagedresults( op ) > SLAP_CONTROL_IGNORED ) { 487 /* TODO: pageresult */ 488 PagedResultsState *ps = op->o_pagedresults_state; 489 /* deferred cookie parsing */ 490 rs->sr_err = parse_paged_cookie( op, rs ); 491 if ( rs->sr_err != LDAP_SUCCESS ) { 492 send_ldap_result( op, rs ); 493 goto done; 494 } 495 496 cursor = (ID) ps->ps_cookie; 497 if ( cursor && ps->ps_size == 0 ) { 498 rs->sr_err = LDAP_SUCCESS; 499 rs->sr_text = "search abandoned by pagedResult size=0"; 500 send_ldap_result( op, rs ); 501 goto done; 502 } 503 id = wt_idl_first( candidates, &cursor ); 504 if ( id == NOID ) { 505 Debug( LDAP_DEBUG_TRACE, 506 LDAP_XSTRING(wt_search) 507 ": no paged results candidates\n" ); 508 send_paged_response( op, rs, &lastid, 0 ); 509 510 rs->sr_err = LDAP_OTHER; 511 goto done; 512 } 513 nentries = ps->ps_count; 514 if ( id == (ID)ps->ps_cookie ) 515 id = wt_idl_next( candidates, &cursor ); 516 goto loop_begin; 517 } 518 519 for ( id = wt_idl_first( candidates, &cursor ); 520 id != NOID ; id = wt_idl_next( candidates, &cursor ) ) 521 { 522 int scopeok; 523 524 loop_begin: 525 526 /* check for abandon */ 527 if ( op->o_abandon ) { 528 rs->sr_err = SLAPD_ABANDON; 529 send_ldap_result( op, rs ); 530 goto done; 531 } 532 533 /* mostly needed by internal searches, 534 * e.g. related to syncrepl, for whom 535 * abandon does not get set... */ 536 if ( slapd_shutdown ) { 537 rs->sr_err = LDAP_UNAVAILABLE; 538 send_ldap_disconnect( op, rs ); 539 goto done; 540 } 541 542 /* check time limit */ 543 if ( op->ors_tlimit != SLAP_NO_LIMIT 544 && slap_get_time() > stoptime ) 545 { 546 rs->sr_err = LDAP_TIMELIMIT_EXCEEDED; 547 rs->sr_ref = rs->sr_v2ref; 548 send_ldap_result( op, rs ); 549 rs->sr_err = LDAP_SUCCESS; 550 goto done; 551 } 552 553 nentries++; 554 555 fetch_entry_retry: 556 557 rc = wt_id2entry(op->o_bd, wc->session, id, &e); 558 /* TODO: error handling */ 559 if ( e == NULL ) { 560 /* TODO: */ 561 goto loop_continue; 562 } 563 if ( is_entry_subentry( e ) ) { 564 if( op->oq_search.rs_scope != LDAP_SCOPE_BASE ) { 565 if(!get_subentries_visibility( op )) { 566 /* only subentries are visible */ 567 goto loop_continue; 568 } 569 570 } else if ( get_subentries( op ) && 571 !get_subentries_visibility( op )) 572 { 573 /* only subentries are visible */ 574 goto loop_continue; 575 } 576 577 } else if ( get_subentries_visibility( op )) { 578 /* only subentries are visible */ 579 goto loop_continue; 580 } 581 582 scopeok = 0; 583 switch( op->ors_scope ) { 584 case LDAP_SCOPE_BASE: 585 /* This is always true, yes? */ 586 if ( id == base->e_id ) scopeok = 1; 587 break; 588 case LDAP_SCOPE_ONELEVEL: 589 scopeok = 1; 590 break; 591 case LDAP_SCOPE_SUBTREE: 592 scopeok = 1; 593 break; 594 } 595 596 /* aliases were already dereferenced in candidate list */ 597 if ( op->ors_deref & LDAP_DEREF_SEARCHING ) { 598 /* but if the search base is an alias, and we didn't 599 * deref it when finding, return it. 600 */ 601 if ( is_entry_alias(e) && 602 ((op->ors_deref & LDAP_DEREF_FINDING) || 603 !bvmatch(&e->e_nname, &op->o_req_ndn))) 604 { 605 goto loop_continue; 606 } 607 /* TODO: alias handling */ 608 } 609 610 /* Not in scope, ignore it */ 611 if ( !scopeok ) 612 { 613 Debug( LDAP_DEBUG_TRACE, 614 LDAP_XSTRING(wt_search) 615 ": %ld scope not okay\n", 616 (long) id ); 617 goto loop_continue; 618 } 619 620 /* 621 * if it's a referral, add it to the list of referrals. only do 622 * this for non-base searches, and don't check the filter 623 * explicitly here since it's only a candidate anyway. 624 */ 625 if ( !manageDSAit && op->oq_search.rs_scope != LDAP_SCOPE_BASE 626 && is_entry_referral( e ) ) 627 { 628 /* TODO: referral */ 629 } 630 631 if ( !manageDSAit && is_entry_glue( e )) { 632 goto loop_continue; 633 } 634 635 /* if it matches the filter and scope, send it */ 636 rs->sr_err = test_filter( op, e, op->oq_search.rs_filter ); 637 if ( rs->sr_err == LDAP_COMPARE_TRUE ) { 638 /* check size limit */ 639 if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) { 640 /* TODO: */ 641 } 642 643 if (e) { 644 /* safe default */ 645 rs->sr_attrs = op->oq_search.rs_attrs; 646 rs->sr_operational_attrs = NULL; 647 rs->sr_ctrls = NULL; 648 rs->sr_entry = e; 649 RS_ASSERT( e->e_private != NULL ); 650 rs->sr_flags = REP_ENTRY_MUSTRELEASE; 651 rs->sr_err = LDAP_SUCCESS; 652 rs->sr_err = send_search_entry( op, rs ); 653 rs->sr_attrs = NULL; 654 rs->sr_entry = NULL; 655 e = NULL; 656 } 657 switch ( rs->sr_err ) { 658 case LDAP_SUCCESS: /* entry sent ok */ 659 break; 660 default: 661 /* TODO: error handling */ 662 break; 663 } 664 } else { 665 Debug( LDAP_DEBUG_TRACE, 666 LDAP_XSTRING(wt_search) 667 ": %ld does not match filter\n", 668 (long) id ); 669 } 670 671 loop_continue: 672 if( e ) { 673 wt_entry_return( e ); 674 e = NULL; 675 } 676 } 677 678 nochange: 679 rs->sr_ctrls = NULL; 680 rs->sr_ref = rs->sr_v2ref; 681 rs->sr_err = (rs->sr_v2ref == NULL) ? LDAP_SUCCESS : LDAP_REFERRAL; 682 rs->sr_rspoid = NULL; 683 if ( get_pagedresults(op) > SLAP_CONTROL_IGNORED ) { 684 /* not implement yet */ 685 /* send_paged_response( op, rs, NULL, 0 ); */ 686 } else { 687 send_ldap_result( op, rs ); 688 } 689 690 rs->sr_err = LDAP_SUCCESS; 691 692 done: 693 694 if( base ) { 695 wt_entry_return( base ); 696 } 697 698 if( e ) { 699 wt_entry_return( e ); 700 } 701 702 return rs->sr_err; 703 } 704 705 /* 706 * Local variables: 707 * indent-tabs-mode: t 708 * tab-width: 4 709 * c-basic-offset: 4 710 * End: 711 */ 712