Head

GCC Code Coverage Report

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


/*	$OpenBSD: index.c,v 1.11 2017/01/20 11:55:08 benno Exp $ */

/*
 * Copyright (c) 2009 Martin Hedenfalk <martin@bzero.se>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/* Indices are stored as unique keys in a btree. No data is stored.
 * The keys are made up of the attribute being indexed, concatenated
 * with the distinguished name of the entry. The namespace suffix is
 * stripped, however.
 *
 * Below, the namespace suffix dc=example,dc=com is stripped.
 *
 * Index b-tree sorts with plain strcmp:
 * ...
 * cn=Chunky Bacon,cn=chunky bacon,ou=people,
 * cn=Chunky Bacon,uid=cbacon,ou=accounts,
 * cn=Chunky Beans,cn=chunky beans,ou=people,
 * cn=Chunky Beans,uid=cbeans,ou=accounts,
 * cn=Crispy Bacon,cn=crispy bacon,ou=people,
 * ...
 * sn=Bacon,cn=chunky bacon,ou=people,
 * sn=Bacon,cn=crispy bacon,ou=people,
 * sn=Beans,cn=chunky beans,ou=people,
 * ...
 * This index can be used for equality, prefix and range searches.
 *
 * If an indexed attribute sorts numerically (integer), we might be able
 * to just pad it with zeros... otherwise this needs to be refined.
 *
 * Multiple attributes can be indexed in the same database.
 *
 * Presence index can be stored as:
 * !mail,cn=chunky bacon,ou=people,
 * !mail,cn=chunky beans,ou=people,
 * !mail,cn=crispy bacon,ou=people,
 *
 * Substring index could probably be stored like a suffix tree:
 * sn>Bacon,cn=chunky bacon,ou=people,
 * sn>acon,cn=chunky bacon,ou=people,
 * sn>con,cn=chunky bacon,ou=people,
 * sn>on,cn=chunky bacon,ou=people,
 * sn>n,cn=chunky bacon,ou=people,
 *
 * This facilitates both substring and suffix search.
 *
 * Approximate index:
 * sn~[soundex(bacon)],cn=chunky bacon,ou=people,
 *
 * One level searches can be indexed as follows:
 * @<parent-rdn>,<rdn>
 * example:
 * @ou=accounts,uid=cbacon
 * @ou=accounts,uid=cbeans
 * @ou=people,cn=chunky bacon
 * @ou=people,cn=chunky beans
 * @ou=people,cn=crispy bacon
 *
 */

#include <sys/types.h>
#include <sys/queue.h>

#include <assert.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>

#include "ldapd.h"
#include "log.h"

static int
index_attribute(struct namespace *ns, char *attr, struct btval *dn,
    struct ber_element *a)
{
	int			 dnsz, rc;
	char			*s, *t;
	struct ber_element	*v;
	struct btval		 key, val;

	assert(ns);
	assert(ns->indx_txn);
	assert(attr);
	assert(dn);
	assert(a);
	assert(a->be_next);
	memset(&val, 0, sizeof(val));

	log_debug("indexing %.*s on %s", (int)dn->size, (char *)dn->data, attr);

	dnsz = dn->size - strlen(ns->suffix);

	for (v = a->be_next->be_sub; v; v = v->be_next) {
		if (ber_get_string(v, &s) != 0)
			continue;
		memset(&key, 0, sizeof(key));
		key.size = asprintf(&t, "%s=%s,%.*s", attr, s, dnsz,
		    (char *)dn->data);
		if (key.size == (size_t)-1)
			return -1;
		key.data = t;
		normalize_dn(key.data);
		rc = btree_txn_put(NULL, ns->indx_txn, &key, &val,
		    BT_NOOVERWRITE);
		free(t);
		if (rc == -1 && errno != EEXIST)
			return -1;
	}

	return 0;
}

static int
index_rdn_key(struct namespace *ns, struct btval *dn, struct btval *key)
{
	int		 dnsz, rdnsz, pdnsz;
	char		*t, *parent_dn;

	memset(key, 0, sizeof(*key));

	dnsz = dn->size - strlen(ns->suffix);
	if (dnsz-- == 0)
		return -1;

	parent_dn = memchr(dn->data, ',', dnsz);
	if (parent_dn == NULL) {
		rdnsz = dnsz;
		pdnsz = 0;
	} else {
		rdnsz = parent_dn - (char *)dn->data;
		pdnsz = dnsz - rdnsz - 1;
		++parent_dn;
	}

	if (asprintf(&t, "@%.*s,%.*s", pdnsz, parent_dn, rdnsz,
	    (char *)dn->data) == -1)
		return -1;

	normalize_dn(t);
	key->data = t;
	key->size = strlen(t);
	key->free_data = 1;

	return 0;
}

static int
index_rdn(struct namespace *ns, struct btval *dn)
{
	struct btval	 key, val;
	int		 rc;

	memset(&val, 0, sizeof(val));

	assert(ns);
	assert(ns->indx_txn);
	assert(dn);

	if (index_rdn_key(ns, dn, &key) < 0)
		return 0;

	log_debug("indexing rdn on %.*s", (int)key.size, (char *)key.data);
	rc = btree_txn_put(NULL, ns->indx_txn, &key, &val, BT_NOOVERWRITE);
	btval_reset(&key);
	if (rc == -1 && errno != EEXIST)
		return -1;
	return 0;
}

static int
unindex_attribute(struct namespace *ns, char *attr, struct btval *dn,
    struct ber_element *a)
{
	int			 dnsz, rc;
	char			*s, *t;
	struct ber_element	*v;
	struct btval		 key;

	assert(ns);
	assert(ns->indx_txn);
	assert(attr);
	assert(dn);
	assert(a);
	assert(a->be_next);

	log_debug("unindexing %.*s on %s",
	    (int)dn->size, (char *)dn->data, attr);

	dnsz = dn->size - strlen(ns->suffix);

	for (v = a->be_next->be_sub; v; v = v->be_next) {
		if (ber_get_string(v, &s) != 0)
			continue;
		memset(&key, 0, sizeof(key));
		key.size = asprintf(&t, "%s=%s,%.*s", attr, s, dnsz,
		    (char *)dn->data);
		key.data = t;
		normalize_dn(key.data);
		rc = btree_txn_del(NULL, ns->indx_txn, &key, NULL);
		free(t);
		if (rc == BT_FAIL && errno != ENOENT)
			return -1;
	}

	return 0;
}

int
index_entry(struct namespace *ns, struct btval *dn, struct ber_element *elm)
{
	struct ber_element	*a;
	struct attr_index	*ai;

	assert(ns);
	assert(dn);
	assert(elm);
	TAILQ_FOREACH(ai, &ns->indices, next) {
		a = ldap_get_attribute(elm, ai->attr);
		if (a && index_attribute(ns, ai->attr, dn, a) < 0)
			return -1;
	}

	return index_rdn(ns, dn);
}

static int
unindex_rdn(struct namespace *ns, struct btval *dn)
{
	int		 rc;
	struct btval	 key;

	assert(ns);
	assert(ns->indx_txn);
	assert(dn);

	if (index_rdn_key(ns, dn, &key) < 0)
		return 0;

	log_debug("unindexing rdn on %.*s", (int)key.size, (char *)key.data);
	rc = btree_txn_del(NULL, ns->indx_txn, &key, NULL);
	btval_reset(&key);
	if (rc == BT_FAIL && errno != ENOENT)
		return -1;
	return 0;
}

int
unindex_entry(struct namespace *ns, struct btval *dn, struct ber_element *elm)
{
	struct ber_element	*a;
	struct attr_index	*ai;

	assert(ns);
	assert(dn);
	assert(elm);
	TAILQ_FOREACH(ai, &ns->indices, next) {
		a = ldap_get_attribute(elm, ai->attr);
		if (a && unindex_attribute(ns, ai->attr, dn, a) < 0)
			return -1;
	}

	return unindex_rdn(ns, dn);
}

/* Reconstruct the full dn from the index key and the namespace suffix.
 *
 * Examples:
 *
 * index key:
 *   sn=Bacon,cn=chunky bacon,ou=people,
 * full dn:
 *   cn=chunky bacon,ou=people,dc=example,dc=com
 *
 * index key:
 *   @ou=people,cn=chunky bacon
 * full dn:
 *   cn=chunky bacon,ou=people,dc=example,dc=com
 *
 * index key:
 *   @,ou=people
 * full dn:
 *   ou=people,dc=example,dc=com
 *
 * index key:
 *   @ou=staff,ou=people,cn=chunky bacon
 * full dn:
 *   cn=chunky bacon,ou=staff,ou=people,dc=example,dc=com
 *
 * Filled in dn must be freed with btval_reset().
 */
int
index_to_dn(struct namespace *ns, struct btval *indx, struct btval *dn)
{
	char		*rdn, *parent_rdn, indxtype, *dst;
	int		 rdn_sz, prdn_sz;

	/* Skip past first index part to get the RDN.
	 */

	indxtype = ((char *)indx->data)[0];
	if (indxtype == '@') {
		/* One-level index.
		 * Full DN is made up of rdn + parent rdn + namespace suffix.
		 */
		rdn = memrchr(indx->data, ',', indx->size);
		if (rdn++ == NULL)
			return -1;
		rdn_sz = indx->size - (rdn - (char *)indx->data);

		parent_rdn = (char *)indx->data + 1;
		prdn_sz = rdn - parent_rdn - 1;
		dn->size = indx->size + strlen(ns->suffix);
		if (prdn_sz == 0)
			dn->size--;
		if ((dn->data = malloc(dn->size)) == NULL) {
			log_warn("conn_search: malloc");
			return -1;
		}
		dst = dn->data;
		bcopy(rdn, dst, rdn_sz);
		dst += rdn_sz;
		*dst++ = ',';
		bcopy(parent_rdn, dst, prdn_sz);
		dst += prdn_sz;
		if (prdn_sz > 0)
			*dst++ = ',';
		bcopy(ns->suffix, dst, strlen(ns->suffix));
	} else {
		/* Construct the full DN by appending namespace suffix.
		 */
		rdn = memchr(indx->data, ',', indx->size);
		if (rdn++ == NULL)
			return -1;
		rdn_sz = indx->size - (rdn - (char *)indx->data);
		dn->size = rdn_sz + strlen(ns->suffix);
		if ((dn->data = malloc(dn->size)) == NULL) {
			log_warn("index_to_dn: malloc");
			return -1;
		}
		bcopy(rdn, dn->data, rdn_sz);
		bcopy(ns->suffix, (char *)dn->data + rdn_sz,
		    strlen(ns->suffix));
	}

	dn->free_data = 1;

	return 0;
}



Generated by: GCOVR (Version 3.3)

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