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
34void			 filter_free(struct plan *filter);
35static int		 search_result(const char *dn,
36				size_t dnlen,
37				struct ber_element *attrs,
38				struct search *search);
39
40static int
41uniqdn_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
50RB_GENERATE(dn_tree, uniqdn, link, uniqdn_cmp);
51
52/* Return true if the attribute is operational.
53 */
54static int
55is_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 */
68static int
69should_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
96static int
97search_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;
167fail:
168	log_warn("search result");
169	if (root)
170		ober_free_elements(root);
171	free(searchdn);
172	return -1;
173}
174
175void
176search_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 */
203int
204is_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
217static int
218check_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
264static int
265mk_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 */
283static int
284is_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
293void
294conn_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
489static void
490ldap_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
545static void
546ldap_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
625done:
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
632static int
633add_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
658static int
659plan_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
680static struct plan *
681search_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
823fail:
824	free(plan);
825	return NULL;
826}
827
828void
829filter_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
848int
849ldap_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
1009done:
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