1 /* $OpenBSD: search.c,v 1.14 2010/11/10 08:00:54 martinh 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 = malloc(key->size + 1)) == NULL) { 219 log_warn("malloc"); 220 return 0; 221 } 222 strncpy(dn0, key->data, key->size); 223 dn0[key->size] = 0; 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 bzero(&key, sizeof(key)); 295 bzero(&val, 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 bzero(&key, 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 bzero(&key, 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 623 if ((indx = calloc(1, sizeof(*indx))) == NULL) 624 return -1; 625 626 va_start(ap, fmt); 627 vasprintf(&indx->prefix, fmt, ap); 628 va_end(ap); 629 630 normalize_dn(indx->prefix); 631 632 TAILQ_INSERT_TAIL(&plan->indices, indx, next); 633 plan->indexed++; 634 635 return 0; 636 } 637 638 static int 639 plan_get_attr(struct plan *plan, struct namespace *ns, char *attr) 640 { 641 if (ns->relax) { 642 /* 643 * Under relaxed schema checking, all attributes 644 * are considered directory strings with case-insensitive 645 * matching. 646 */ 647 plan->at = lookup_attribute(conf->schema, "name"); 648 plan->adesc = attr; 649 } else 650 plan->at = lookup_attribute(conf->schema, attr); 651 652 if (plan->at == NULL) { 653 log_debug("%s: no such attribute, undefined term", attr); 654 return -1; 655 } 656 657 return 0; 658 } 659 660 static struct plan * 661 search_planner(struct namespace *ns, struct ber_element *filter) 662 { 663 int class; 664 unsigned long type; 665 char *s, *attr; 666 struct ber_element *elm; 667 struct index *indx; 668 struct plan *plan, *arg = NULL; 669 670 if (filter->be_class != BER_CLASS_CONTEXT) { 671 log_warnx("invalid class %d in filter", filter->be_class); 672 return NULL; 673 } 674 675 if ((plan = calloc(1, sizeof(*plan))) == NULL) { 676 log_warn("search_planner: calloc"); 677 return NULL; 678 } 679 plan->op = filter->be_type; 680 TAILQ_INIT(&plan->args); 681 TAILQ_INIT(&plan->indices); 682 683 switch (filter->be_type) { 684 case LDAP_FILT_EQ: 685 case LDAP_FILT_APPR: 686 if (ber_scanf_elements(filter, "{ss", &attr, &s) != 0) 687 goto fail; 688 if (plan_get_attr(plan, ns, attr) == -1) 689 plan->undefined = 1; 690 else if (plan->at->equality == NULL) { 691 log_debug("'%s' doesn't define equality matching", 692 attr); 693 plan->undefined = 1; 694 } else { 695 plan->assert.value = s; 696 if (namespace_has_index(ns, attr, INDEX_EQUAL)) 697 add_index(plan, "%s=%s,", attr, s); 698 } 699 break; 700 case LDAP_FILT_SUBS: 701 if (ber_scanf_elements(filter, "{s{ets", 702 &attr, &plan->assert.substring, &class, &type, &s) != 0) 703 goto fail; 704 if (plan_get_attr(plan, ns, attr) == -1) 705 plan->undefined = 1; 706 else if (plan->at->substr == NULL) { 707 log_debug("'%s' doesn't define substring matching", 708 attr); 709 plan->undefined = 1; 710 } else if (class == BER_CLASS_CONTEXT && 711 type == LDAP_FILT_SUBS_INIT) { 712 /* Only prefix substrings are usable as index. */ 713 if (namespace_has_index(ns, attr, INDEX_EQUAL)) 714 add_index(plan, "%s=%s", attr, s); 715 } 716 break; 717 case LDAP_FILT_PRES: 718 if (ber_scanf_elements(filter, "s", &attr) != 0) 719 goto fail; 720 if (plan_get_attr(plan, ns, attr) == -1) 721 plan->undefined = 1; 722 else if (strcasecmp(attr, "objectClass") != 0) { 723 if (namespace_has_index(ns, attr, INDEX_PRESENCE)) 724 add_index(plan, "%s=", attr); 725 } 726 break; 727 case LDAP_FILT_AND: 728 if (ber_scanf_elements(filter, "(e", &elm) != 0) 729 goto fail; 730 for (; elm; elm = elm->be_next) { 731 if ((arg = search_planner(ns, elm)) == NULL) 732 goto fail; 733 if (arg->undefined) { 734 plan->undefined = 1; 735 break; 736 } 737 TAILQ_INSERT_TAIL(&plan->args, arg, next); 738 } 739 740 /* The term is undefined if any arg is undefined. */ 741 if (plan->undefined) 742 break; 743 744 /* Select an index to use. */ 745 TAILQ_FOREACH(arg, &plan->args, next) { 746 if (arg->indexed) { 747 while ((indx = TAILQ_FIRST(&arg->indices))) { 748 TAILQ_REMOVE(&arg->indices, indx, next); 749 TAILQ_INSERT_TAIL(&plan->indices, indx, 750 next); 751 } 752 plan->indexed = arg->indexed; 753 break; 754 } 755 } 756 break; 757 case LDAP_FILT_OR: 758 if (ber_scanf_elements(filter, "(e", &elm) != 0) 759 goto fail; 760 for (; elm; elm = elm->be_next) { 761 if ((arg = search_planner(ns, elm)) == NULL) 762 goto fail; 763 TAILQ_INSERT_TAIL(&plan->args, arg, next); 764 } 765 766 /* The term is undefined iff all args are undefined. */ 767 plan->undefined = 1; 768 TAILQ_FOREACH(arg, &plan->args, next) 769 if (!arg->undefined) { 770 plan->undefined = 0; 771 break; 772 } 773 774 TAILQ_FOREACH(arg, &plan->args, next) { 775 if (!arg->indexed) { 776 plan->indexed = 0; 777 break; 778 } 779 while ((indx = TAILQ_FIRST(&arg->indices))) { 780 TAILQ_REMOVE(&arg->indices, indx, next); 781 TAILQ_INSERT_TAIL(&plan->indices, indx,next); 782 plan->indexed++; 783 } 784 } 785 break; 786 case LDAP_FILT_NOT: 787 if (ber_scanf_elements(filter, "{e", &elm) != 0) 788 goto fail; 789 if ((arg = search_planner(ns, elm)) == NULL) 790 goto fail; 791 TAILQ_INSERT_TAIL(&plan->args, arg, next); 792 793 plan->undefined = arg->undefined; 794 if (plan->indexed) { 795 log_debug("NOT filter forced unindexed search"); 796 plan->indexed = 0; 797 } 798 break; 799 800 default: 801 log_warnx("filter type %d not implemented", filter->be_type); 802 plan->undefined = 1; 803 break; 804 } 805 806 return plan; 807 808 fail: 809 free(plan); 810 return NULL; 811 } 812 813 void 814 filter_free(struct plan *filter) 815 { 816 struct index *indx; 817 struct plan *arg; 818 819 if (filter) { 820 while ((arg = TAILQ_FIRST(&filter->args)) != NULL) { 821 TAILQ_REMOVE(&filter->args, arg, next); 822 filter_free(arg); 823 } 824 while ((indx = TAILQ_FIRST(&filter->indices)) != NULL) { 825 TAILQ_REMOVE(&filter->indices, indx, next); 826 free(indx->prefix); 827 free(indx); 828 } 829 free(filter); 830 } 831 } 832 833 int 834 ldap_search(struct request *req) 835 { 836 long long reason = LDAP_OTHER; 837 struct referrals *refs; 838 struct search *search = NULL; 839 840 if (stats.searches > MAX_SEARCHES) { 841 log_warnx("refusing more than %u concurrent searches", 842 MAX_SEARCHES); 843 reason = LDAP_BUSY; 844 goto done; 845 } 846 ++stats.searches; 847 ++stats.req_search; 848 849 if ((search = calloc(1, sizeof(*search))) == NULL) 850 return -1; 851 search->req = req; 852 search->conn = req->conn; 853 search->init = 0; 854 search->started_at = time(0); 855 TAILQ_INSERT_HEAD(&req->conn->searches, search, next); 856 RB_INIT(&search->uniqdns); 857 858 if (ber_scanf_elements(req->op, "{sEEiibeSeS", 859 &search->basedn, 860 &search->scope, 861 &search->deref, 862 &search->szlim, 863 &search->tmlim, 864 &search->typesonly, 865 &search->filter, 866 &search->attrlist) != 0) { 867 log_warnx("failed to parse search request"); 868 reason = LDAP_PROTOCOL_ERROR; 869 goto done; 870 } 871 872 normalize_dn(search->basedn); 873 log_debug("base dn = %s, scope = %d", search->basedn, search->scope); 874 875 if (*search->basedn == '\0') { 876 /* request for the root DSE */ 877 if (!authorized(req->conn, NULL, ACI_READ, "", 878 LDAP_SCOPE_BASE)) { 879 reason = LDAP_INSUFFICIENT_ACCESS; 880 goto done; 881 } 882 if (search->scope != LDAP_SCOPE_BASE) { 883 /* only base searches are valid */ 884 reason = LDAP_NO_SUCH_OBJECT; 885 goto done; 886 } 887 /* TODO: verify filter is (objectClass=*) */ 888 ldap_search_root_dse(search); 889 return 0; 890 } 891 892 if (strcasecmp(search->basedn, "cn=schema") == 0) { 893 /* request for the subschema subentries */ 894 if (!authorized(req->conn, NULL, ACI_READ, 895 "cn=schema", LDAP_SCOPE_BASE)) { 896 reason = LDAP_INSUFFICIENT_ACCESS; 897 goto done; 898 } 899 if (search->scope != LDAP_SCOPE_BASE) { 900 /* only base searches are valid */ 901 reason = LDAP_NO_SUCH_OBJECT; 902 goto done; 903 } 904 /* TODO: verify filter is (objectClass=subschema) */ 905 ldap_search_subschema(search); 906 return 0; 907 } 908 909 if ((search->ns = namespace_for_base(search->basedn)) == NULL) { 910 refs = namespace_referrals(search->basedn); 911 if (refs != NULL) { 912 ldap_refer(req, search->basedn, search, refs); 913 search->req = NULL; /* request free'd by ldap_refer */ 914 search_close(search); 915 return LDAP_REFERRAL; 916 } 917 log_debug("no database configured for suffix %s", 918 search->basedn); 919 reason = LDAP_NO_SUCH_OBJECT; 920 goto done; 921 } 922 923 if (!authorized(req->conn, search->ns, ACI_READ, 924 search->basedn, search->scope)) { 925 reason = LDAP_INSUFFICIENT_ACCESS; 926 goto done; 927 } 928 929 if (namespace_begin_txn(search->ns, &search->data_txn, 930 &search->indx_txn, 1) != BT_SUCCESS) { 931 if (errno == EBUSY) { 932 if (namespace_queue_request(search->ns, req) != 0) { 933 reason = LDAP_BUSY; 934 goto done; 935 } 936 search->req = NULL; /* keep the scheduled request */ 937 search_close(search); 938 return 0; 939 } 940 reason = LDAP_OTHER; 941 goto done; 942 } 943 944 if (search->scope == LDAP_SCOPE_BASE) { 945 struct btval key, val; 946 947 bzero(&key, sizeof(key)); 948 bzero(&val, sizeof(val)); 949 key.data = search->basedn; 950 key.size = strlen(key.data); 951 952 if (btree_txn_get(NULL, search->data_txn, &key, &val) == 0) { 953 check_search_entry(&key, &val, search); 954 btval_reset(&val); 955 reason = LDAP_SUCCESS; 956 } else if (errno == ENOENT) 957 reason = LDAP_NO_SUCH_OBJECT; 958 else 959 reason = LDAP_OTHER; 960 goto done; 961 } 962 963 if (!namespace_exists(search->ns, search->basedn)) { 964 reason = LDAP_NO_SUCH_OBJECT; 965 goto done; 966 } 967 968 search->plan = search_planner(search->ns, search->filter); 969 if (search->plan == NULL) { 970 reason = LDAP_PROTOCOL_ERROR; 971 goto done; 972 } 973 974 if (search->plan->undefined) { 975 log_debug("whole search filter is undefined"); 976 reason = LDAP_SUCCESS; 977 goto done; 978 } 979 980 if (!search->plan->indexed && search->scope == LDAP_SCOPE_ONELEVEL) { 981 int sz; 982 sz = strlen(search->basedn) - strlen(search->ns->suffix); 983 if (sz > 0 && search->basedn[sz - 1] == ',') 984 sz--; 985 add_index(search->plan, "@%.*s,", sz, search->basedn); 986 } 987 988 if (!search->plan->indexed) 989 ++stats.unindexed; 990 991 bufferevent_enable(req->conn->bev, EV_WRITE); 992 return 0; 993 994 done: 995 send_ldap_result(req->conn, req->msgid, LDAP_RES_SEARCH_RESULT, reason); 996 if (search) 997 search_close(search); 998 return 0; 999 } 1000 1001