GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/ldapd/search.c Lines: 0 523 0.0 %
Date: 2017-11-13 Branches: 0 504 0.0 %

Line Branch Exec Source
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