GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.sbin/ldapctl/../ldapd/index.c Lines: 0 144 0.0 %
Date: 2017-11-13 Branches: 0 110 0.0 %

Line Branch Exec Source
1
/*	$OpenBSD: index.c,v 1.11 2017/01/20 11:55:08 benno Exp $ */
2
3
/*
4
 * Copyright (c) 2009 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
/* Indices are stored as unique keys in a btree. No data is stored.
20
 * The keys are made up of the attribute being indexed, concatenated
21
 * with the distinguished name of the entry. The namespace suffix is
22
 * stripped, however.
23
 *
24
 * Below, the namespace suffix dc=example,dc=com is stripped.
25
 *
26
 * Index b-tree sorts with plain strcmp:
27
 * ...
28
 * cn=Chunky Bacon,cn=chunky bacon,ou=people,
29
 * cn=Chunky Bacon,uid=cbacon,ou=accounts,
30
 * cn=Chunky Beans,cn=chunky beans,ou=people,
31
 * cn=Chunky Beans,uid=cbeans,ou=accounts,
32
 * cn=Crispy Bacon,cn=crispy bacon,ou=people,
33
 * ...
34
 * sn=Bacon,cn=chunky bacon,ou=people,
35
 * sn=Bacon,cn=crispy bacon,ou=people,
36
 * sn=Beans,cn=chunky beans,ou=people,
37
 * ...
38
 * This index can be used for equality, prefix and range searches.
39
 *
40
 * If an indexed attribute sorts numerically (integer), we might be able
41
 * to just pad it with zeros... otherwise this needs to be refined.
42
 *
43
 * Multiple attributes can be indexed in the same database.
44
 *
45
 * Presence index can be stored as:
46
 * !mail,cn=chunky bacon,ou=people,
47
 * !mail,cn=chunky beans,ou=people,
48
 * !mail,cn=crispy bacon,ou=people,
49
 *
50
 * Substring index could probably be stored like a suffix tree:
51
 * sn>Bacon,cn=chunky bacon,ou=people,
52
 * sn>acon,cn=chunky bacon,ou=people,
53
 * sn>con,cn=chunky bacon,ou=people,
54
 * sn>on,cn=chunky bacon,ou=people,
55
 * sn>n,cn=chunky bacon,ou=people,
56
 *
57
 * This facilitates both substring and suffix search.
58
 *
59
 * Approximate index:
60
 * sn~[soundex(bacon)],cn=chunky bacon,ou=people,
61
 *
62
 * One level searches can be indexed as follows:
63
 * @<parent-rdn>,<rdn>
64
 * example:
65
 * @ou=accounts,uid=cbacon
66
 * @ou=accounts,uid=cbeans
67
 * @ou=people,cn=chunky bacon
68
 * @ou=people,cn=chunky beans
69
 * @ou=people,cn=crispy bacon
70
 *
71
 */
72
73
#include <sys/types.h>
74
#include <sys/queue.h>
75
76
#include <assert.h>
77
#include <errno.h>
78
#include <stdlib.h>
79
#include <string.h>
80
81
#include "ldapd.h"
82
#include "log.h"
83
84
static int
85
index_attribute(struct namespace *ns, char *attr, struct btval *dn,
86
    struct ber_element *a)
87
{
88
	int			 dnsz, rc;
89
	char			*s, *t;
90
	struct ber_element	*v;
91
	struct btval		 key, val;
92
93
	assert(ns);
94
	assert(ns->indx_txn);
95
	assert(attr);
96
	assert(dn);
97
	assert(a);
98
	assert(a->be_next);
99
	memset(&val, 0, sizeof(val));
100
101
	log_debug("indexing %.*s on %s", (int)dn->size, (char *)dn->data, attr);
102
103
	dnsz = dn->size - strlen(ns->suffix);
104
105
	for (v = a->be_next->be_sub; v; v = v->be_next) {
106
		if (ber_get_string(v, &s) != 0)
107
			continue;
108
		memset(&key, 0, sizeof(key));
109
		key.size = asprintf(&t, "%s=%s,%.*s", attr, s, dnsz,
110
		    (char *)dn->data);
111
		if (key.size == (size_t)-1)
112
			return -1;
113
		key.data = t;
114
		normalize_dn(key.data);
115
		rc = btree_txn_put(NULL, ns->indx_txn, &key, &val,
116
		    BT_NOOVERWRITE);
117
		free(t);
118
		if (rc == -1 && errno != EEXIST)
119
			return -1;
120
	}
121
122
	return 0;
123
}
124
125
static int
126
index_rdn_key(struct namespace *ns, struct btval *dn, struct btval *key)
127
{
128
	int		 dnsz, rdnsz, pdnsz;
129
	char		*t, *parent_dn;
130
131
	memset(key, 0, sizeof(*key));
132
133
	dnsz = dn->size - strlen(ns->suffix);
134
	if (dnsz-- == 0)
135
		return -1;
136
137
	parent_dn = memchr(dn->data, ',', dnsz);
138
	if (parent_dn == NULL) {
139
		rdnsz = dnsz;
140
		pdnsz = 0;
141
	} else {
142
		rdnsz = parent_dn - (char *)dn->data;
143
		pdnsz = dnsz - rdnsz - 1;
144
		++parent_dn;
145
	}
146
147
	if (asprintf(&t, "@%.*s,%.*s", pdnsz, parent_dn, rdnsz,
148
	    (char *)dn->data) == -1)
149
		return -1;
150
151
	normalize_dn(t);
152
	key->data = t;
153
	key->size = strlen(t);
154
	key->free_data = 1;
155
156
	return 0;
157
}
158
159
static int
160
index_rdn(struct namespace *ns, struct btval *dn)
161
{
162
	struct btval	 key, val;
163
	int		 rc;
164
165
	memset(&val, 0, sizeof(val));
166
167
	assert(ns);
168
	assert(ns->indx_txn);
169
	assert(dn);
170
171
	if (index_rdn_key(ns, dn, &key) < 0)
172
		return 0;
173
174
	log_debug("indexing rdn on %.*s", (int)key.size, (char *)key.data);
175
	rc = btree_txn_put(NULL, ns->indx_txn, &key, &val, BT_NOOVERWRITE);
176
	btval_reset(&key);
177
	if (rc == -1 && errno != EEXIST)
178
		return -1;
179
	return 0;
180
}
181
182
static int
183
unindex_attribute(struct namespace *ns, char *attr, struct btval *dn,
184
    struct ber_element *a)
185
{
186
	int			 dnsz, rc;
187
	char			*s, *t;
188
	struct ber_element	*v;
189
	struct btval		 key;
190
191
	assert(ns);
192
	assert(ns->indx_txn);
193
	assert(attr);
194
	assert(dn);
195
	assert(a);
196
	assert(a->be_next);
197
198
	log_debug("unindexing %.*s on %s",
199
	    (int)dn->size, (char *)dn->data, attr);
200
201
	dnsz = dn->size - strlen(ns->suffix);
202
203
	for (v = a->be_next->be_sub; v; v = v->be_next) {
204
		if (ber_get_string(v, &s) != 0)
205
			continue;
206
		memset(&key, 0, sizeof(key));
207
		key.size = asprintf(&t, "%s=%s,%.*s", attr, s, dnsz,
208
		    (char *)dn->data);
209
		key.data = t;
210
		normalize_dn(key.data);
211
		rc = btree_txn_del(NULL, ns->indx_txn, &key, NULL);
212
		free(t);
213
		if (rc == BT_FAIL && errno != ENOENT)
214
			return -1;
215
	}
216
217
	return 0;
218
}
219
220
int
221
index_entry(struct namespace *ns, struct btval *dn, struct ber_element *elm)
222
{
223
	struct ber_element	*a;
224
	struct attr_index	*ai;
225
226
	assert(ns);
227
	assert(dn);
228
	assert(elm);
229
	TAILQ_FOREACH(ai, &ns->indices, next) {
230
		a = ldap_get_attribute(elm, ai->attr);
231
		if (a && index_attribute(ns, ai->attr, dn, a) < 0)
232
			return -1;
233
	}
234
235
	return index_rdn(ns, dn);
236
}
237
238
static int
239
unindex_rdn(struct namespace *ns, struct btval *dn)
240
{
241
	int		 rc;
242
	struct btval	 key;
243
244
	assert(ns);
245
	assert(ns->indx_txn);
246
	assert(dn);
247
248
	if (index_rdn_key(ns, dn, &key) < 0)
249
		return 0;
250
251
	log_debug("unindexing rdn on %.*s", (int)key.size, (char *)key.data);
252
	rc = btree_txn_del(NULL, ns->indx_txn, &key, NULL);
253
	btval_reset(&key);
254
	if (rc == BT_FAIL && errno != ENOENT)
255
		return -1;
256
	return 0;
257
}
258
259
int
260
unindex_entry(struct namespace *ns, struct btval *dn, struct ber_element *elm)
261
{
262
	struct ber_element	*a;
263
	struct attr_index	*ai;
264
265
	assert(ns);
266
	assert(dn);
267
	assert(elm);
268
	TAILQ_FOREACH(ai, &ns->indices, next) {
269
		a = ldap_get_attribute(elm, ai->attr);
270
		if (a && unindex_attribute(ns, ai->attr, dn, a) < 0)
271
			return -1;
272
	}
273
274
	return unindex_rdn(ns, dn);
275
}
276
277
/* Reconstruct the full dn from the index key and the namespace suffix.
278
 *
279
 * Examples:
280
 *
281
 * index key:
282
 *   sn=Bacon,cn=chunky bacon,ou=people,
283
 * full dn:
284
 *   cn=chunky bacon,ou=people,dc=example,dc=com
285
 *
286
 * index key:
287
 *   @ou=people,cn=chunky bacon
288
 * full dn:
289
 *   cn=chunky bacon,ou=people,dc=example,dc=com
290
 *
291
 * index key:
292
 *   @,ou=people
293
 * full dn:
294
 *   ou=people,dc=example,dc=com
295
 *
296
 * index key:
297
 *   @ou=staff,ou=people,cn=chunky bacon
298
 * full dn:
299
 *   cn=chunky bacon,ou=staff,ou=people,dc=example,dc=com
300
 *
301
 * Filled in dn must be freed with btval_reset().
302
 */
303
int
304
index_to_dn(struct namespace *ns, struct btval *indx, struct btval *dn)
305
{
306
	char		*rdn, *parent_rdn, indxtype, *dst;
307
	int		 rdn_sz, prdn_sz;
308
309
	/* Skip past first index part to get the RDN.
310
	 */
311
312
	indxtype = ((char *)indx->data)[0];
313
	if (indxtype == '@') {
314
		/* One-level index.
315
		 * Full DN is made up of rdn + parent rdn + namespace suffix.
316
		 */
317
		rdn = memrchr(indx->data, ',', indx->size);
318
		if (rdn++ == NULL)
319
			return -1;
320
		rdn_sz = indx->size - (rdn - (char *)indx->data);
321
322
		parent_rdn = (char *)indx->data + 1;
323
		prdn_sz = rdn - parent_rdn - 1;
324
		dn->size = indx->size + strlen(ns->suffix);
325
		if (prdn_sz == 0)
326
			dn->size--;
327
		if ((dn->data = malloc(dn->size)) == NULL) {
328
			log_warn("conn_search: malloc");
329
			return -1;
330
		}
331
		dst = dn->data;
332
		bcopy(rdn, dst, rdn_sz);
333
		dst += rdn_sz;
334
		*dst++ = ',';
335
		bcopy(parent_rdn, dst, prdn_sz);
336
		dst += prdn_sz;
337
		if (prdn_sz > 0)
338
			*dst++ = ',';
339
		bcopy(ns->suffix, dst, strlen(ns->suffix));
340
	} else {
341
		/* Construct the full DN by appending namespace suffix.
342
		 */
343
		rdn = memchr(indx->data, ',', indx->size);
344
		if (rdn++ == NULL)
345
			return -1;
346
		rdn_sz = indx->size - (rdn - (char *)indx->data);
347
		dn->size = rdn_sz + strlen(ns->suffix);
348
		if ((dn->data = malloc(dn->size)) == NULL) {
349
			log_warn("index_to_dn: malloc");
350
			return -1;
351
		}
352
		bcopy(rdn, dn->data, rdn_sz);
353
		bcopy(ns->suffix, (char *)dn->data + rdn_sz,
354
		    strlen(ns->suffix));
355
	}
356
357
	dn->free_data = 1;
358
359
	return 0;
360
}
361