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