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
uniqdn_cmp(struct uniqdn * a,struct uniqdn * b)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
is_operational(char * adesc)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
should_include_attribute(char * adesc,struct search * search,int explicit)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
search_result(const char * dn,size_t dnlen,struct ber_element * attrs,struct search * search)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
search_close(struct search * search)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
is_child_of(struct btval * key,const char * base)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
check_search_entry(struct btval * key,struct btval * val,struct search * search)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
mk_dup(struct search * search,struct btval * key)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
is_dup(struct search * search,struct btval * key)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
conn_search(struct search * search)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
ldap_search_root_dse(struct search * search)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
ldap_search_subschema(struct search * search)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
add_index(struct plan * plan,const char * fmt,...)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
plan_get_attr(struct plan * plan,struct namespace * ns,char * attr)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 *
search_planner(struct namespace * ns,struct ber_element * filter)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
filter_free(struct plan * filter)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
ldap_search(struct request * req)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