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