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