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 84static int 85index_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 125static int 126index_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 160static int 161index_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 183static int 184unindex_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 221int 222index_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 239static int 240unindex_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 260int 261unindex_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 */ 304int 305index_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