1 /* $OpenBSD: index.c,v 1.13 2019/10/24 12:39:26 tb 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
index_attribute(struct namespace * ns,char * attr,struct btval * dn,struct ber_element * a)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 (ober_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
index_rdn_key(struct namespace * ns,struct btval * dn,struct btval * key)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 parent_dn = "";
142 } else {
143 rdnsz = parent_dn - (char *)dn->data;
144 pdnsz = dnsz - rdnsz - 1;
145 ++parent_dn;
146 }
147
148 if (asprintf(&t, "@%.*s,%.*s", pdnsz, parent_dn, rdnsz,
149 (char *)dn->data) == -1)
150 return -1;
151
152 normalize_dn(t);
153 key->data = t;
154 key->size = strlen(t);
155 key->free_data = 1;
156
157 return 0;
158 }
159
160 static int
index_rdn(struct namespace * ns,struct btval * dn)161 index_rdn(struct namespace *ns, struct btval *dn)
162 {
163 struct btval key, val;
164 int rc;
165
166 memset(&val, 0, sizeof(val));
167
168 assert(ns);
169 assert(ns->indx_txn);
170 assert(dn);
171
172 if (index_rdn_key(ns, dn, &key) < 0)
173 return 0;
174
175 log_debug("indexing rdn on %.*s", (int)key.size, (char *)key.data);
176 rc = btree_txn_put(NULL, ns->indx_txn, &key, &val, BT_NOOVERWRITE);
177 btval_reset(&key);
178 if (rc == -1 && errno != EEXIST)
179 return -1;
180 return 0;
181 }
182
183 static int
unindex_attribute(struct namespace * ns,char * attr,struct btval * dn,struct ber_element * a)184 unindex_attribute(struct namespace *ns, char *attr, struct btval *dn,
185 struct ber_element *a)
186 {
187 int dnsz, rc;
188 char *s, *t;
189 struct ber_element *v;
190 struct btval key;
191
192 assert(ns);
193 assert(ns->indx_txn);
194 assert(attr);
195 assert(dn);
196 assert(a);
197 assert(a->be_next);
198
199 log_debug("unindexing %.*s on %s",
200 (int)dn->size, (char *)dn->data, attr);
201
202 dnsz = dn->size - strlen(ns->suffix);
203
204 for (v = a->be_next->be_sub; v; v = v->be_next) {
205 if (ober_get_string(v, &s) != 0)
206 continue;
207 memset(&key, 0, sizeof(key));
208 key.size = asprintf(&t, "%s=%s,%.*s", attr, s, dnsz,
209 (char *)dn->data);
210 key.data = t;
211 normalize_dn(key.data);
212 rc = btree_txn_del(NULL, ns->indx_txn, &key, NULL);
213 free(t);
214 if (rc == BT_FAIL && errno != ENOENT)
215 return -1;
216 }
217
218 return 0;
219 }
220
221 int
index_entry(struct namespace * ns,struct btval * dn,struct ber_element * elm)222 index_entry(struct namespace *ns, struct btval *dn, struct ber_element *elm)
223 {
224 struct ber_element *a;
225 struct attr_index *ai;
226
227 assert(ns);
228 assert(dn);
229 assert(elm);
230 TAILQ_FOREACH(ai, &ns->indices, next) {
231 a = ldap_get_attribute(elm, ai->attr);
232 if (a && index_attribute(ns, ai->attr, dn, a) < 0)
233 return -1;
234 }
235
236 return index_rdn(ns, dn);
237 }
238
239 static int
unindex_rdn(struct namespace * ns,struct btval * dn)240 unindex_rdn(struct namespace *ns, struct btval *dn)
241 {
242 int rc;
243 struct btval key;
244
245 assert(ns);
246 assert(ns->indx_txn);
247 assert(dn);
248
249 if (index_rdn_key(ns, dn, &key) < 0)
250 return 0;
251
252 log_debug("unindexing rdn on %.*s", (int)key.size, (char *)key.data);
253 rc = btree_txn_del(NULL, ns->indx_txn, &key, NULL);
254 btval_reset(&key);
255 if (rc == BT_FAIL && errno != ENOENT)
256 return -1;
257 return 0;
258 }
259
260 int
unindex_entry(struct namespace * ns,struct btval * dn,struct ber_element * elm)261 unindex_entry(struct namespace *ns, struct btval *dn, struct ber_element *elm)
262 {
263 struct ber_element *a;
264 struct attr_index *ai;
265
266 assert(ns);
267 assert(dn);
268 assert(elm);
269 TAILQ_FOREACH(ai, &ns->indices, next) {
270 a = ldap_get_attribute(elm, ai->attr);
271 if (a && unindex_attribute(ns, ai->attr, dn, a) < 0)
272 return -1;
273 }
274
275 return unindex_rdn(ns, dn);
276 }
277
278 /* Reconstruct the full dn from the index key and the namespace suffix.
279 *
280 * Examples:
281 *
282 * index key:
283 * sn=Bacon,cn=chunky bacon,ou=people,
284 * full dn:
285 * cn=chunky bacon,ou=people,dc=example,dc=com
286 *
287 * index key:
288 * @ou=people,cn=chunky bacon
289 * full dn:
290 * cn=chunky bacon,ou=people,dc=example,dc=com
291 *
292 * index key:
293 * @,ou=people
294 * full dn:
295 * ou=people,dc=example,dc=com
296 *
297 * index key:
298 * @ou=staff,ou=people,cn=chunky bacon
299 * full dn:
300 * cn=chunky bacon,ou=staff,ou=people,dc=example,dc=com
301 *
302 * Filled in dn must be freed with btval_reset().
303 */
304 int
index_to_dn(struct namespace * ns,struct btval * indx,struct btval * dn)305 index_to_dn(struct namespace *ns, struct btval *indx, struct btval *dn)
306 {
307 char *rdn, *parent_rdn, indxtype, *dst;
308 int rdn_sz, prdn_sz;
309
310 /* Skip past first index part to get the RDN.
311 */
312
313 indxtype = ((char *)indx->data)[0];
314 if (indxtype == '@') {
315 /* One-level index.
316 * Full DN is made up of rdn + parent rdn + namespace suffix.
317 */
318 rdn = memrchr(indx->data, ',', indx->size);
319 if (rdn++ == NULL)
320 return -1;
321 rdn_sz = indx->size - (rdn - (char *)indx->data);
322
323 parent_rdn = (char *)indx->data + 1;
324 prdn_sz = rdn - parent_rdn - 1;
325 dn->size = indx->size + strlen(ns->suffix);
326 if (prdn_sz == 0)
327 dn->size--;
328 if ((dn->data = malloc(dn->size)) == NULL) {
329 log_warn("conn_search: malloc");
330 return -1;
331 }
332 dst = dn->data;
333 bcopy(rdn, dst, rdn_sz);
334 dst += rdn_sz;
335 *dst++ = ',';
336 bcopy(parent_rdn, dst, prdn_sz);
337 dst += prdn_sz;
338 if (prdn_sz > 0)
339 *dst++ = ',';
340 bcopy(ns->suffix, dst, strlen(ns->suffix));
341 } else {
342 /* Construct the full DN by appending namespace suffix.
343 */
344 rdn = memchr(indx->data, ',', indx->size);
345 if (rdn++ == NULL)
346 return -1;
347 rdn_sz = indx->size - (rdn - (char *)indx->data);
348 dn->size = rdn_sz + strlen(ns->suffix);
349 if ((dn->data = malloc(dn->size)) == NULL) {
350 log_warn("index_to_dn: malloc");
351 return -1;
352 }
353 bcopy(rdn, dn->data, rdn_sz);
354 bcopy(ns->suffix, (char *)dn->data + rdn_sz,
355 strlen(ns->suffix));
356 }
357
358 dn->free_data = 1;
359
360 return 0;
361 }
362
363