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 362