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