1 /* $OpenBSD: search.c,v 1.26 2020/01/28 15:51:26 bket Exp $ */ 2 3 /* 4 * Copyright (c) 2009, 2010 Martin Hedenfalk <martin@bzero.se> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 #include <sys/queue.h> 20 #include <sys/types.h> 21 #include <sys/tree.h> 22 23 #include <errno.h> 24 #include <event.h> 25 #include <stdlib.h> 26 #include <string.h> 27 #include <time.h> 28 29 #include "ldapd.h" 30 #include "log.h" 31 32 #define MAX_SEARCHES 200 33 34 void filter_free(struct plan *filter); 35 static int search_result(const char *dn, 36 size_t dnlen, 37 struct ber_element *attrs, 38 struct search *search); 39 40 static int 41 uniqdn_cmp(struct uniqdn *a, struct uniqdn *b) 42 { 43 if (a->key.size < b->key.size) 44 return -1; 45 if (a->key.size > b->key.size) 46 return +1; 47 return memcmp(a->key.data, b->key.data, a->key.size); 48 } 49 50 RB_GENERATE(dn_tree, uniqdn, link, uniqdn_cmp); 51 52 /* Return true if the attribute is operational. 53 */ 54 static int 55 is_operational(char *adesc) 56 { 57 struct attr_type *at; 58 59 at = lookup_attribute(conf->schema, adesc); 60 if (at) 61 return at->usage != USAGE_USER_APP; 62 63 return 0; 64 } 65 66 /* Return true if attr should be included in search entry. 67 */ 68 static int 69 should_include_attribute(char *adesc, struct search *search, int explicit) 70 { 71 char *fdesc; 72 struct ber_element *elm; 73 74 if (search->attrlist->be_sub == NULL || 75 search->attrlist->be_sub->be_encoding == BER_TYPE_EOC) { 76 /* An empty list with no attributes requests the return of 77 * all user attributes. */ 78 return !is_operational(adesc); 79 } 80 81 for (elm = search->attrlist->be_sub; elm; elm = elm->be_next) { 82 if (ober_get_string(elm, &fdesc) != 0) 83 continue; 84 if (strcasecmp(fdesc, adesc) == 0) 85 return 1; 86 if (strcmp(fdesc, "*") == 0 && !is_operational(adesc)) 87 return 1; 88 if (strcmp(fdesc, "+") == 0 && is_operational(adesc) && 89 !explicit) 90 return 1; 91 } 92 93 return 0; 94 } 95 96 static int 97 search_result(const char *dn, size_t dnlen, struct ber_element *attrs, 98 struct search *search) 99 { 100 int rc; 101 struct conn *conn = search->conn; 102 struct ber_element *root, *elm, *filtered_attrs = NULL, *link, *a; 103 struct ber_element *prev, *next; 104 char *adesc; 105 void *buf, *searchdn = NULL; 106 107 if ((root = ober_add_sequence(NULL)) == NULL) 108 goto fail; 109 110 if ((filtered_attrs = ober_add_sequence(NULL)) == NULL) 111 goto fail; 112 link = filtered_attrs; 113 114 if ((searchdn = strndup(dn, dnlen)) == NULL) 115 goto fail; 116 117 for (prev = NULL, a = attrs->be_sub; a; a = next) { 118 if (ober_get_string(a->be_sub, &adesc) != 0) 119 goto fail; 120 /* 121 * Check if read access to the attribute is allowed and if it 122 * should be included in the search result. The attribute is 123 * filtered out in the result if one of these conditions fails. 124 */ 125 if (authorized(search->conn, search->ns, ACI_READ, 126 searchdn, adesc, LDAP_SCOPE_BASE) && 127 should_include_attribute(adesc, search, 0)) { 128 next = a->be_next; 129 if (prev != NULL) 130 prev->be_next = a->be_next; /* unlink a */ 131 else 132 attrs->be_sub = a->be_next; 133 a->be_next = NULL; /* break chain*/ 134 ober_link_elements(link, a); 135 link = a; 136 } else { 137 prev = a; 138 next = a->be_next; 139 } 140 } 141 142 elm = ober_printf_elements(root, "i{txe", search->req->msgid, 143 BER_CLASS_APP, LDAP_RES_SEARCH_ENTRY, 144 dn, dnlen, filtered_attrs); 145 if (elm == NULL) 146 goto fail; 147 148 ldap_debug_elements(root, LDAP_RES_SEARCH_ENTRY, 149 "sending search entry on fd %d", conn->fd); 150 151 rc = ober_write_elements(&conn->ber, root); 152 ober_free_elements(root); 153 154 if (rc < 0) { 155 log_warn("failed to create search-entry response"); 156 return -1; 157 } 158 159 ober_get_writebuf(&conn->ber, &buf); 160 if (bufferevent_write(conn->bev, buf, rc) != 0) { 161 log_warn("failed to send ldap result"); 162 return -1; 163 } 164 165 free(searchdn); 166 return 0; 167 fail: 168 log_warn("search result"); 169 if (root) 170 ober_free_elements(root); 171 free(searchdn); 172 return -1; 173 } 174 175 void 176 search_close(struct search *search) 177 { 178 struct uniqdn *dn, *next; 179 180 for (dn = RB_MIN(dn_tree, &search->uniqdns); dn; dn = next) { 181 next = RB_NEXT(dn_tree, &search->uniqdns, dn); 182 RB_REMOVE(dn_tree, &search->uniqdns, dn); 183 free(dn->key.data); 184 free(dn); 185 } 186 187 btree_cursor_close(search->cursor); 188 btree_txn_abort(search->data_txn); 189 btree_txn_abort(search->indx_txn); 190 191 if (search->req != NULL) { 192 log_debug("finished search on msgid %lld", search->req->msgid); 193 request_free(search->req); 194 } 195 TAILQ_REMOVE(&search->conn->searches, search, next); 196 filter_free(search->plan); 197 free(search); 198 --stats.searches; 199 } 200 201 /* Returns true (1) if key is a direct subordinate of base. 202 */ 203 int 204 is_child_of(struct btval *key, const char *base) 205 { 206 size_t ksz, bsz; 207 char *p; 208 209 if ((p = memchr(key->data, ',', key->size)) == NULL) 210 return 0; 211 p++; 212 ksz = key->size - (p - (char *)key->data); 213 bsz = strlen(base); 214 return (ksz == bsz && bcmp(p, base, ksz) == 0); 215 } 216 217 static int 218 check_search_entry(struct btval *key, struct btval *val, struct search *search) 219 { 220 int rc; 221 char *dn0; 222 struct ber_element *elm; 223 224 /* verify entry is a direct subordinate of basedn */ 225 if (search->scope == LDAP_SCOPE_ONELEVEL && 226 !is_child_of(key, search->basedn)) { 227 log_debug("not a direct subordinate of base"); 228 return 0; 229 } 230 231 if ((dn0 = strndup(key->data, key->size)) == NULL) { 232 log_warn("malloc"); 233 return 0; 234 } 235 236 if (!authorized(search->conn, search->ns, ACI_READ, dn0, 237 NULL, LDAP_SCOPE_BASE)) { 238 /* LDAP_INSUFFICIENT_ACCESS */ 239 free(dn0); 240 return 0; 241 } 242 free(dn0); 243 244 if ((elm = namespace_db2ber(search->ns, val)) == NULL) { 245 log_warnx("failed to parse entry [%.*s]", 246 (int)key->size, (char *)key->data); 247 return 0; 248 } 249 250 if (ldap_matches_filter(elm, search->plan) != 0) { 251 ober_free_elements(elm); 252 return 0; 253 } 254 255 rc = search_result(key->data, key->size, elm, search); 256 ober_free_elements(elm); 257 258 if (rc == 0) 259 search->nmatched++; 260 261 return rc; 262 } 263 264 static int 265 mk_dup(struct search *search, struct btval *key) 266 { 267 struct uniqdn *udn; 268 269 if ((udn = calloc(1, sizeof(*udn))) == NULL) 270 return BT_FAIL; 271 272 if ((udn->key.data = malloc(key->size)) == NULL) { 273 free(udn); 274 return BT_FAIL; 275 } 276 bcopy(key->data, udn->key.data, key->size); 277 udn->key.size = key->size; 278 RB_INSERT(dn_tree, &search->uniqdns, udn); 279 return BT_SUCCESS; 280 } 281 282 /* check if this entry was already sent */ 283 static int 284 is_dup(struct search *search, struct btval *key) 285 { 286 struct uniqdn find; 287 288 find.key.data = key->data; 289 find.key.size = key->size; 290 return RB_FIND(dn_tree, &search->uniqdns, &find) != NULL; 291 } 292 293 void 294 conn_search(struct search *search) 295 { 296 int i, rc = BT_SUCCESS; 297 unsigned int reason = LDAP_SUCCESS; 298 unsigned int op = BT_NEXT; 299 time_t now; 300 struct conn *conn; 301 struct btree_txn *txn; 302 struct btval key, ikey, val; 303 304 conn = search->conn; 305 306 memset(&key, 0, sizeof(key)); 307 memset(&val, 0, sizeof(val)); 308 309 if (search->plan->indexed) 310 txn = search->indx_txn; 311 else 312 txn = search->data_txn; 313 314 if (!search->init) { 315 search->cursor = btree_txn_cursor_open(NULL, txn); 316 if (search->cursor == NULL) { 317 log_warn("btree_cursor_open"); 318 search_close(search); 319 return; 320 } 321 322 if (search->plan->indexed) { 323 search->cindx = TAILQ_FIRST(&search->plan->indices); 324 key.data = search->cindx->prefix; 325 log_debug("init index scan on [%s]", 326 search->cindx->prefix); 327 } else { 328 if (*search->basedn) 329 key.data = search->basedn; 330 log_debug("init full scan"); 331 } 332 333 if (key.data) { 334 key.size = strlen(key.data); 335 op = BT_CURSOR; 336 } 337 338 search->init = 1; 339 } 340 341 for (i = 0; i < 10 && rc == BT_SUCCESS; i++) { 342 rc = btree_cursor_get(search->cursor, &key, &val, op); 343 op = BT_NEXT; 344 345 if (rc == BT_SUCCESS && search->plan->indexed) { 346 log_debug("found index %.*s", (int)key.size, 347 (char *)key.data); 348 349 if (!has_prefix(&key, search->cindx->prefix)) { 350 log_debug("scanned past index prefix [%s]", 351 search->cindx->prefix); 352 btval_reset(&val); 353 btval_reset(&key); 354 rc = BT_FAIL; 355 errno = ENOENT; 356 } 357 } 358 359 if (rc == BT_FAIL && errno == ENOENT && 360 search->plan->indexed > 1) { 361 search->cindx = TAILQ_NEXT(search->cindx, next); 362 if (search->cindx != NULL) { 363 rc = BT_SUCCESS; 364 memset(&key, 0, sizeof(key)); 365 key.data = search->cindx->prefix; 366 key.size = strlen(key.data); 367 log_debug("re-init cursor on [%s]", 368 search->cindx->prefix); 369 op = BT_CURSOR; 370 continue; 371 } 372 } 373 374 if (rc != BT_SUCCESS) { 375 if (errno != ENOENT) { 376 log_warnx("btree failure"); 377 reason = LDAP_OTHER; 378 } 379 break; 380 } 381 382 search->nscanned++; 383 384 if (search->plan->indexed) { 385 bcopy(&key, &ikey, sizeof(key)); 386 memset(&key, 0, sizeof(key)); 387 btval_reset(&val); 388 389 rc = index_to_dn(search->ns, &ikey, &key); 390 btval_reset(&ikey); 391 if (rc != 0) { 392 reason = LDAP_OTHER; 393 break; 394 } 395 396 log_debug("lookup indexed key [%.*s]", 397 (int)key.size, (char *)key.data); 398 399 /* verify entry is a direct subordinate */ 400 if (search->scope == LDAP_SCOPE_ONELEVEL && 401 !is_child_of(&key, search->basedn)) { 402 log_debug("not a direct subordinate of base"); 403 btval_reset(&key); 404 continue; 405 } 406 407 if (search->plan->indexed > 1 && is_dup(search, &key)) { 408 log_debug("skipping duplicate dn %.*s", 409 (int)key.size, (char *)key.data); 410 search->ndups++; 411 btval_reset(&key); 412 continue; 413 } 414 415 rc = btree_txn_get(NULL, search->data_txn, &key, &val); 416 if (rc == BT_FAIL) { 417 if (errno == ENOENT) { 418 log_warnx("indexed key [%.*s]" 419 " doesn't exist!", 420 (int)key.size, (char *)key.data); 421 btval_reset(&key); 422 rc = BT_SUCCESS; 423 continue; 424 } 425 log_warnx("btree failure"); 426 btval_reset(&key); 427 reason = LDAP_OTHER; 428 break; 429 } 430 } 431 432 log_debug("found dn %.*s", (int)key.size, (char *)key.data); 433 434 if (!has_suffix(&key, search->basedn)) { 435 btval_reset(&val); 436 btval_reset(&key); 437 if (search->plan->indexed) 438 continue; 439 else { 440 log_debug("scanned past basedn suffix"); 441 rc = 1; 442 break; 443 } 444 } 445 446 rc = check_search_entry(&key, &val, search); 447 btval_reset(&val); 448 if (rc == BT_SUCCESS && search->plan->indexed > 1) 449 rc = mk_dup(search, &key); 450 451 btval_reset(&key); 452 453 /* Check if we have passed the size limit. */ 454 if (rc == BT_SUCCESS && search->szlim > 0 && 455 search->nmatched > search->szlim) { 456 log_debug("search %d/%lld has exceeded size limit (%lld)", 457 search->conn->fd, search->req->msgid, 458 search->szlim); 459 reason = LDAP_SIZELIMIT_EXCEEDED; 460 rc = BT_FAIL; 461 } 462 } 463 464 /* Check if we have passed the time limit. */ 465 now = time(0); 466 if (rc == 0 && search->tmlim > 0 && 467 search->started_at + search->tmlim < now) { 468 log_debug("search %d/%lld has exceeded time limit (%lld)", 469 search->conn->fd, search->req->msgid, 470 search->tmlim); 471 reason = LDAP_TIMELIMIT_EXCEEDED; 472 rc = 1; 473 ++stats.timeouts; 474 } 475 476 if (rc == 0) { 477 bufferevent_enable(search->conn->bev, EV_WRITE); 478 } else { 479 log_debug("%u scanned, %u matched, %u dups", 480 search->nscanned, search->nmatched, search->ndups); 481 send_ldap_result(conn, search->req->msgid, 482 LDAP_RES_SEARCH_RESULT, reason); 483 if (errno != ENOENT) 484 log_debug("search failed: %s", strerror(errno)); 485 search_close(search); 486 } 487 } 488 489 static void 490 ldap_search_root_dse(struct search *search) 491 { 492 struct namespace *ns; 493 struct ber_element *root, *elm, *key, *val; 494 495 if ((root = ober_add_sequence(NULL)) == NULL) { 496 return; 497 } 498 499 elm = ober_add_sequence(root); 500 key = ober_add_string(elm, "objectClass"); 501 val = ober_add_set(key); 502 ober_add_string(val, "top"); 503 504 elm = ober_add_sequence(elm); 505 key = ober_add_string(elm, "supportedLDAPVersion"); 506 val = ober_add_set(key); 507 ober_add_string(val, "3"); 508 509 elm = ober_add_sequence(elm); 510 key = ober_add_string(elm, "namingContexts"); 511 val = ober_add_set(key); 512 TAILQ_FOREACH(ns, &conf->namespaces, next) 513 val = ober_add_string(val, ns->suffix); 514 515 elm = ober_add_sequence(elm); 516 key = ober_add_string(elm, "supportedExtension"); 517 val = ober_add_set(key); 518 ober_add_string(val, "1.3.6.1.4.1.1466.20037"); /* StartTLS */ 519 520 elm = ober_add_sequence(elm); 521 key = ober_add_string(elm, "supportedFeatures"); 522 val = ober_add_set(key); 523 /* All Operational Attributes (RFC 3673) */ 524 ober_add_string(val, "1.3.6.1.4.1.4203.1.5.1"); 525 526 elm = ober_add_sequence(elm); 527 key = ober_add_string(elm, "subschemaSubentry"); 528 val = ober_add_set(key); 529 ober_add_string(val, "cn=schema"); 530 531 if ((search->conn->s_flags & F_SECURE) == F_SECURE) { 532 elm = ober_add_sequence(elm); 533 key = ober_add_string(elm, "supportedSASLMechanisms"); 534 val = ober_add_set(key); 535 ober_add_string(val, "PLAIN"); 536 } 537 538 search_result("", 0, root, search); 539 ober_free_elements(root); 540 send_ldap_result(search->conn, search->req->msgid, 541 LDAP_RES_SEARCH_RESULT, LDAP_SUCCESS); 542 search_close(search); 543 } 544 545 static void 546 ldap_search_subschema(struct search *search) 547 { 548 char buf[1024]; 549 struct ber_element *root, *elm, *key, *val; 550 struct object *obj; 551 struct attr_type *at; 552 int rc, i; 553 554 if ((root = ober_add_sequence(NULL)) == NULL) { 555 return; 556 } 557 558 elm = ober_add_sequence(root); 559 key = ober_add_string(elm, "objectClass"); 560 val = ober_add_set(key); 561 val = ober_add_string(val, "top"); 562 ober_add_string(val, "subschema"); 563 564 elm = ober_add_sequence(elm); 565 key = ober_add_string(elm, "createTimestamp"); 566 val = ober_add_set(key); 567 ober_add_string(val, ldap_strftime(stats.started_at)); 568 569 elm = ober_add_sequence(elm); 570 key = ober_add_string(elm, "modifyTimestamp"); 571 val = ober_add_set(key); 572 ober_add_string(val, ldap_strftime(stats.started_at)); 573 574 elm = ober_add_sequence(elm); 575 key = ober_add_string(elm, "subschemaSubentry"); 576 val = ober_add_set(key); 577 ober_add_string(val, "cn=schema"); 578 579 if (should_include_attribute("objectClasses", search, 1)) { 580 elm = ober_add_sequence(elm); 581 key = ober_add_string(elm, "objectClasses"); 582 val = ober_add_set(key); 583 584 RB_FOREACH(obj, object_tree, &conf->schema->objects) { 585 if (schema_dump_object(obj, buf, sizeof(buf)) != 0) { 586 rc = LDAP_OTHER; 587 goto done; 588 } 589 val = ober_add_string(val, buf); 590 } 591 } 592 593 if (should_include_attribute("attributeTypes", search, 1)) { 594 elm = ober_add_sequence(elm); 595 key = ober_add_string(elm, "attributeTypes"); 596 val = ober_add_set(key); 597 598 RB_FOREACH(at, attr_type_tree, &conf->schema->attr_types) { 599 if (schema_dump_attribute(at, buf, sizeof(buf)) != 0) { 600 rc = LDAP_OTHER; 601 goto done; 602 } 603 val = ober_add_string(val, buf); 604 } 605 } 606 607 if (should_include_attribute("matchingRules", search, 1)) { 608 elm = ober_add_sequence(elm); 609 key = ober_add_string(elm, "matchingRules"); 610 val = ober_add_set(key); 611 612 for (i = 0; i < num_match_rules; i++) { 613 if (schema_dump_match_rule(&match_rules[i], buf, 614 sizeof(buf)) != 0) { 615 rc = LDAP_OTHER; 616 goto done; 617 } 618 val = ober_add_string(val, buf); 619 } 620 } 621 622 search_result("cn=schema", 9, root, search); 623 rc = LDAP_SUCCESS; 624 625 done: 626 ober_free_elements(root); 627 send_ldap_result(search->conn, search->req->msgid, 628 LDAP_RES_SEARCH_RESULT, rc); 629 search_close(search); 630 } 631 632 static int 633 add_index(struct plan *plan, const char *fmt, ...) 634 { 635 struct index *indx; 636 va_list ap; 637 int rc; 638 639 if ((indx = calloc(1, sizeof(*indx))) == NULL) 640 return -1; 641 642 va_start(ap, fmt); 643 rc = vasprintf(&indx->prefix, fmt, ap); 644 va_end(ap); 645 if (rc == -1) { 646 free(indx); 647 return -1; 648 } 649 650 normalize_dn(indx->prefix); 651 652 TAILQ_INSERT_TAIL(&plan->indices, indx, next); 653 plan->indexed++; 654 655 return 0; 656 } 657 658 static int 659 plan_get_attr(struct plan *plan, struct namespace *ns, char *attr) 660 { 661 if (ns->relax) { 662 /* 663 * Under relaxed schema checking, all attributes 664 * are considered directory strings with case-insensitive 665 * matching. 666 */ 667 plan->at = lookup_attribute(conf->schema, "name"); 668 plan->adesc = attr; 669 } else 670 plan->at = lookup_attribute(conf->schema, attr); 671 672 if (plan->at == NULL) { 673 log_debug("%s: no such attribute, undefined term", attr); 674 return -1; 675 } 676 677 return 0; 678 } 679 680 static struct plan * 681 search_planner(struct namespace *ns, struct ber_element *filter) 682 { 683 int class; 684 unsigned int type; 685 char *s, *attr; 686 struct ber_element *elm; 687 struct index *indx; 688 struct plan *plan, *arg = NULL; 689 690 if (filter->be_class != BER_CLASS_CONTEXT) { 691 log_warnx("invalid class %d in filter", filter->be_class); 692 return NULL; 693 } 694 695 if ((plan = calloc(1, sizeof(*plan))) == NULL) { 696 log_warn("search_planner: calloc"); 697 return NULL; 698 } 699 plan->op = filter->be_type; 700 TAILQ_INIT(&plan->args); 701 TAILQ_INIT(&plan->indices); 702 703 switch (filter->be_type) { 704 case LDAP_FILT_EQ: 705 case LDAP_FILT_APPR: 706 if (ober_scanf_elements(filter, "{ss", &attr, &s) != 0) 707 goto fail; 708 if (plan_get_attr(plan, ns, attr) == -1) 709 plan->undefined = 1; 710 else if (plan->at->equality == NULL) { 711 log_debug("'%s' doesn't define equality matching", 712 attr); 713 plan->undefined = 1; 714 } else { 715 plan->assert.value = s; 716 if (namespace_has_index(ns, attr, INDEX_EQUAL)) 717 add_index(plan, "%s=%s,", attr, s); 718 } 719 break; 720 case LDAP_FILT_SUBS: 721 if (ober_scanf_elements(filter, "{s{ets", 722 &attr, &plan->assert.substring, &class, &type, &s) != 0) 723 goto fail; 724 if (plan_get_attr(plan, ns, attr) == -1) 725 plan->undefined = 1; 726 else if (plan->at->substr == NULL) { 727 log_debug("'%s' doesn't define substring matching", 728 attr); 729 plan->undefined = 1; 730 } else if (class == BER_CLASS_CONTEXT && 731 type == LDAP_FILT_SUBS_INIT) { 732 /* Only prefix substrings are usable as index. */ 733 if (namespace_has_index(ns, attr, INDEX_EQUAL)) 734 add_index(plan, "%s=%s", attr, s); 735 } 736 break; 737 case LDAP_FILT_PRES: 738 if (ober_scanf_elements(filter, "s", &attr) != 0) 739 goto fail; 740 if (plan_get_attr(plan, ns, attr) == -1) 741 plan->undefined = 1; 742 else if (strcasecmp(attr, "objectClass") != 0) { 743 if (namespace_has_index(ns, attr, INDEX_PRESENCE)) 744 add_index(plan, "%s=", attr); 745 } 746 break; 747 case LDAP_FILT_AND: 748 if (ober_scanf_elements(filter, "(e", &elm) != 0) 749 goto fail; 750 for (; elm; elm = elm->be_next) { 751 if ((arg = search_planner(ns, elm)) == NULL) 752 goto fail; 753 if (arg->undefined) { 754 plan->undefined = 1; 755 break; 756 } 757 TAILQ_INSERT_TAIL(&plan->args, arg, next); 758 } 759 760 /* The term is undefined if any arg is undefined. */ 761 if (plan->undefined) 762 break; 763 764 /* Select an index to use. */ 765 TAILQ_FOREACH(arg, &plan->args, next) { 766 if (arg->indexed) { 767 TAILQ_CONCAT(&plan->indices, &arg->indices, 768 next); 769 plan->indexed = arg->indexed; 770 break; 771 } 772 } 773 break; 774 case LDAP_FILT_OR: 775 if (ober_scanf_elements(filter, "(e", &elm) != 0) 776 goto fail; 777 for (; elm; elm = elm->be_next) { 778 if ((arg = search_planner(ns, elm)) == NULL) 779 goto fail; 780 TAILQ_INSERT_TAIL(&plan->args, arg, next); 781 } 782 783 /* The term is undefined iff all args are undefined. */ 784 plan->undefined = 1; 785 TAILQ_FOREACH(arg, &plan->args, next) 786 if (!arg->undefined) { 787 plan->undefined = 0; 788 break; 789 } 790 791 TAILQ_FOREACH(arg, &plan->args, next) { 792 if (!arg->indexed) { 793 plan->indexed = 0; 794 break; 795 } 796 TAILQ_FOREACH(indx, &arg->indices, next) 797 plan->indexed++; 798 TAILQ_CONCAT(&plan->indices, &arg->indices, next); 799 } 800 break; 801 case LDAP_FILT_NOT: 802 if (ober_scanf_elements(filter, "{e", &elm) != 0) 803 goto fail; 804 if ((arg = search_planner(ns, elm)) == NULL) 805 goto fail; 806 TAILQ_INSERT_TAIL(&plan->args, arg, next); 807 808 plan->undefined = arg->undefined; 809 if (plan->indexed) { 810 log_debug("NOT filter forced unindexed search"); 811 plan->indexed = 0; 812 } 813 break; 814 815 default: 816 log_warnx("filter type %u not implemented", filter->be_type); 817 plan->undefined = 1; 818 break; 819 } 820 821 return plan; 822 823 fail: 824 free(plan); 825 return NULL; 826 } 827 828 void 829 filter_free(struct plan *filter) 830 { 831 struct index *indx; 832 struct plan *arg; 833 834 if (filter) { 835 while ((arg = TAILQ_FIRST(&filter->args)) != NULL) { 836 TAILQ_REMOVE(&filter->args, arg, next); 837 filter_free(arg); 838 } 839 while ((indx = TAILQ_FIRST(&filter->indices)) != NULL) { 840 TAILQ_REMOVE(&filter->indices, indx, next); 841 free(indx->prefix); 842 free(indx); 843 } 844 free(filter); 845 } 846 } 847 848 int 849 ldap_search(struct request *req) 850 { 851 long long reason = LDAP_OTHER; 852 struct referrals *refs; 853 struct search *search = NULL; 854 855 if (stats.searches > MAX_SEARCHES) { 856 log_warnx("refusing more than %u concurrent searches", 857 MAX_SEARCHES); 858 reason = LDAP_BUSY; 859 goto done; 860 } 861 ++stats.searches; 862 ++stats.req_search; 863 864 if ((search = calloc(1, sizeof(*search))) == NULL) 865 return -1; 866 search->req = req; 867 search->conn = req->conn; 868 search->init = 0; 869 search->started_at = time(0); 870 TAILQ_INSERT_HEAD(&req->conn->searches, search, next); 871 RB_INIT(&search->uniqdns); 872 873 if (ober_scanf_elements(req->op, "{sEEiibeSeS", 874 &search->basedn, 875 &search->scope, 876 &search->deref, 877 &search->szlim, 878 &search->tmlim, 879 &search->typesonly, 880 &search->filter, 881 &search->attrlist) != 0) { 882 log_warnx("failed to parse search request"); 883 reason = LDAP_PROTOCOL_ERROR; 884 goto done; 885 } 886 887 normalize_dn(search->basedn); 888 log_debug("base dn = %s, scope = %lld", search->basedn, search->scope); 889 890 if (*search->basedn == '\0') { 891 /* request for the root DSE */ 892 if (!authorized(req->conn, NULL, ACI_READ, "", 893 NULL, LDAP_SCOPE_BASE)) { 894 reason = LDAP_INSUFFICIENT_ACCESS; 895 goto done; 896 } 897 if (search->scope != LDAP_SCOPE_BASE) { 898 /* only base searches are valid */ 899 reason = LDAP_NO_SUCH_OBJECT; 900 goto done; 901 } 902 /* TODO: verify filter is (objectClass=*) */ 903 ldap_search_root_dse(search); 904 return 0; 905 } 906 907 if (strcasecmp(search->basedn, "cn=schema") == 0) { 908 /* request for the subschema subentries */ 909 if (!authorized(req->conn, NULL, ACI_READ, 910 "cn=schema", NULL, LDAP_SCOPE_BASE)) { 911 reason = LDAP_INSUFFICIENT_ACCESS; 912 goto done; 913 } 914 if (search->scope != LDAP_SCOPE_BASE) { 915 /* only base searches are valid */ 916 reason = LDAP_NO_SUCH_OBJECT; 917 goto done; 918 } 919 /* TODO: verify filter is (objectClass=subschema) */ 920 ldap_search_subschema(search); 921 return 0; 922 } 923 924 if ((search->ns = namespace_for_base(search->basedn)) == NULL) { 925 refs = namespace_referrals(search->basedn); 926 if (refs != NULL) { 927 ldap_refer(req, search->basedn, search, refs); 928 search->req = NULL; /* request free'd by ldap_refer */ 929 search_close(search); 930 return LDAP_REFERRAL; 931 } 932 log_debug("no database configured for suffix %s", 933 search->basedn); 934 reason = LDAP_NO_SUCH_OBJECT; 935 goto done; 936 } 937 938 if (!authorized(req->conn, search->ns, ACI_READ, 939 search->basedn, NULL, search->scope)) { 940 reason = LDAP_INSUFFICIENT_ACCESS; 941 goto done; 942 } 943 944 if (namespace_begin_txn(search->ns, &search->data_txn, 945 &search->indx_txn, 1) != BT_SUCCESS) { 946 if (errno == EBUSY) { 947 if (namespace_queue_request(search->ns, req) != 0) { 948 reason = LDAP_BUSY; 949 goto done; 950 } 951 search->req = NULL; /* keep the scheduled request */ 952 search_close(search); 953 return 0; 954 } 955 reason = LDAP_OTHER; 956 goto done; 957 } 958 959 if (search->scope == LDAP_SCOPE_BASE) { 960 struct btval key, val; 961 962 memset(&key, 0, sizeof(key)); 963 memset(&val, 0, sizeof(val)); 964 key.data = search->basedn; 965 key.size = strlen(key.data); 966 967 if (btree_txn_get(NULL, search->data_txn, &key, &val) == 0) { 968 check_search_entry(&key, &val, search); 969 btval_reset(&val); 970 reason = LDAP_SUCCESS; 971 } else if (errno == ENOENT) 972 reason = LDAP_NO_SUCH_OBJECT; 973 else 974 reason = LDAP_OTHER; 975 goto done; 976 } 977 978 if (!namespace_exists(search->ns, search->basedn)) { 979 reason = LDAP_NO_SUCH_OBJECT; 980 goto done; 981 } 982 983 search->plan = search_planner(search->ns, search->filter); 984 if (search->plan == NULL) { 985 reason = LDAP_PROTOCOL_ERROR; 986 goto done; 987 } 988 989 if (search->plan->undefined) { 990 log_debug("whole search filter is undefined"); 991 reason = LDAP_SUCCESS; 992 goto done; 993 } 994 995 if (!search->plan->indexed && search->scope == LDAP_SCOPE_ONELEVEL) { 996 int sz; 997 sz = strlen(search->basedn) - strlen(search->ns->suffix); 998 if (sz > 0 && search->basedn[sz - 1] == ',') 999 sz--; 1000 add_index(search->plan, "@%.*s,", sz, search->basedn); 1001 } 1002 1003 if (!search->plan->indexed) 1004 ++stats.unindexed; 1005 1006 bufferevent_enable(req->conn->bev, EV_WRITE); 1007 return 0; 1008 1009 done: 1010 send_ldap_result(req->conn, req->msgid, LDAP_RES_SEARCH_RESULT, reason); 1011 if (search) 1012 search_close(search); 1013 return 0; 1014 } 1015 1016