File: [local] / src / usr.sbin / ldapd / index.c (download)
Revision 1.13, Thu Oct 24 12:39:26 2019 UTC (4 years, 7 months ago) by tb
Branch: MAIN
CVS Tags: OPENBSD_7_5_BASE, OPENBSD_7_5, OPENBSD_7_4_BASE, OPENBSD_7_4, OPENBSD_7_3_BASE, OPENBSD_7_3, OPENBSD_7_2_BASE, OPENBSD_7_2, OPENBSD_7_1_BASE, OPENBSD_7_1, OPENBSD_7_0_BASE, OPENBSD_7_0, OPENBSD_6_9_BASE, OPENBSD_6_9, OPENBSD_6_8_BASE, OPENBSD_6_8, OPENBSD_6_7_BASE, OPENBSD_6_7, HEAD Changes since 1.12: +3 -3 lines
The ber_* namespace is used by liblber since time immemorial,
so move our BER API to the unused ober_* prefix to avoid some
breakage in ports.
Problem diagnosed by jmatthew with ber_free() in samba, but
there are many others as pointed out by sthen.
tests & ok rob
ok sthen (who had an almost identical diff for libutil)
"go head hit it" deraadt
|
/* $OpenBSD: index.c,v 1.13 2019/10/24 12:39:26 tb Exp $ */
/*
* Copyright (c) 2009 Martin Hedenfalk <martin@bzero.se>
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
/* Indices are stored as unique keys in a btree. No data is stored.
* The keys are made up of the attribute being indexed, concatenated
* with the distinguished name of the entry. The namespace suffix is
* stripped, however.
*
* Below, the namespace suffix dc=example,dc=com is stripped.
*
* Index b-tree sorts with plain strcmp:
* ...
* cn=Chunky Bacon,cn=chunky bacon,ou=people,
* cn=Chunky Bacon,uid=cbacon,ou=accounts,
* cn=Chunky Beans,cn=chunky beans,ou=people,
* cn=Chunky Beans,uid=cbeans,ou=accounts,
* cn=Crispy Bacon,cn=crispy bacon,ou=people,
* ...
* sn=Bacon,cn=chunky bacon,ou=people,
* sn=Bacon,cn=crispy bacon,ou=people,
* sn=Beans,cn=chunky beans,ou=people,
* ...
* This index can be used for equality, prefix and range searches.
*
* If an indexed attribute sorts numerically (integer), we might be able
* to just pad it with zeros... otherwise this needs to be refined.
*
* Multiple attributes can be indexed in the same database.
*
* Presence index can be stored as:
* !mail,cn=chunky bacon,ou=people,
* !mail,cn=chunky beans,ou=people,
* !mail,cn=crispy bacon,ou=people,
*
* Substring index could probably be stored like a suffix tree:
* sn>Bacon,cn=chunky bacon,ou=people,
* sn>acon,cn=chunky bacon,ou=people,
* sn>con,cn=chunky bacon,ou=people,
* sn>on,cn=chunky bacon,ou=people,
* sn>n,cn=chunky bacon,ou=people,
*
* This facilitates both substring and suffix search.
*
* Approximate index:
* sn~[soundex(bacon)],cn=chunky bacon,ou=people,
*
* One level searches can be indexed as follows:
* @<parent-rdn>,<rdn>
* example:
* @ou=accounts,uid=cbacon
* @ou=accounts,uid=cbeans
* @ou=people,cn=chunky bacon
* @ou=people,cn=chunky beans
* @ou=people,cn=crispy bacon
*
*/
#include <sys/types.h>
#include <sys/queue.h>
#include <assert.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include "ldapd.h"
#include "log.h"
static int
index_attribute(struct namespace *ns, char *attr, struct btval *dn,
struct ber_element *a)
{
int dnsz, rc;
char *s, *t;
struct ber_element *v;
struct btval key, val;
assert(ns);
assert(ns->indx_txn);
assert(attr);
assert(dn);
assert(a);
assert(a->be_next);
memset(&val, 0, sizeof(val));
log_debug("indexing %.*s on %s", (int)dn->size, (char *)dn->data, attr);
dnsz = dn->size - strlen(ns->suffix);
for (v = a->be_next->be_sub; v; v = v->be_next) {
if (ober_get_string(v, &s) != 0)
continue;
memset(&key, 0, sizeof(key));
key.size = asprintf(&t, "%s=%s,%.*s", attr, s, dnsz,
(char *)dn->data);
if (key.size == (size_t)-1)
return -1;
key.data = t;
normalize_dn(key.data);
rc = btree_txn_put(NULL, ns->indx_txn, &key, &val,
BT_NOOVERWRITE);
free(t);
if (rc == -1 && errno != EEXIST)
return -1;
}
return 0;
}
static int
index_rdn_key(struct namespace *ns, struct btval *dn, struct btval *key)
{
int dnsz, rdnsz, pdnsz;
char *t, *parent_dn;
memset(key, 0, sizeof(*key));
dnsz = dn->size - strlen(ns->suffix);
if (dnsz-- == 0)
return -1;
parent_dn = memchr(dn->data, ',', dnsz);
if (parent_dn == NULL) {
rdnsz = dnsz;
pdnsz = 0;
parent_dn = "";
} else {
rdnsz = parent_dn - (char *)dn->data;
pdnsz = dnsz - rdnsz - 1;
++parent_dn;
}
if (asprintf(&t, "@%.*s,%.*s", pdnsz, parent_dn, rdnsz,
(char *)dn->data) == -1)
return -1;
normalize_dn(t);
key->data = t;
key->size = strlen(t);
key->free_data = 1;
return 0;
}
static int
index_rdn(struct namespace *ns, struct btval *dn)
{
struct btval key, val;
int rc;
memset(&val, 0, sizeof(val));
assert(ns);
assert(ns->indx_txn);
assert(dn);
if (index_rdn_key(ns, dn, &key) < 0)
return 0;
log_debug("indexing rdn on %.*s", (int)key.size, (char *)key.data);
rc = btree_txn_put(NULL, ns->indx_txn, &key, &val, BT_NOOVERWRITE);
btval_reset(&key);
if (rc == -1 && errno != EEXIST)
return -1;
return 0;
}
static int
unindex_attribute(struct namespace *ns, char *attr, struct btval *dn,
struct ber_element *a)
{
int dnsz, rc;
char *s, *t;
struct ber_element *v;
struct btval key;
assert(ns);
assert(ns->indx_txn);
assert(attr);
assert(dn);
assert(a);
assert(a->be_next);
log_debug("unindexing %.*s on %s",
(int)dn->size, (char *)dn->data, attr);
dnsz = dn->size - strlen(ns->suffix);
for (v = a->be_next->be_sub; v; v = v->be_next) {
if (ober_get_string(v, &s) != 0)
continue;
memset(&key, 0, sizeof(key));
key.size = asprintf(&t, "%s=%s,%.*s", attr, s, dnsz,
(char *)dn->data);
key.data = t;
normalize_dn(key.data);
rc = btree_txn_del(NULL, ns->indx_txn, &key, NULL);
free(t);
if (rc == BT_FAIL && errno != ENOENT)
return -1;
}
return 0;
}
int
index_entry(struct namespace *ns, struct btval *dn, struct ber_element *elm)
{
struct ber_element *a;
struct attr_index *ai;
assert(ns);
assert(dn);
assert(elm);
TAILQ_FOREACH(ai, &ns->indices, next) {
a = ldap_get_attribute(elm, ai->attr);
if (a && index_attribute(ns, ai->attr, dn, a) < 0)
return -1;
}
return index_rdn(ns, dn);
}
static int
unindex_rdn(struct namespace *ns, struct btval *dn)
{
int rc;
struct btval key;
assert(ns);
assert(ns->indx_txn);
assert(dn);
if (index_rdn_key(ns, dn, &key) < 0)
return 0;
log_debug("unindexing rdn on %.*s", (int)key.size, (char *)key.data);
rc = btree_txn_del(NULL, ns->indx_txn, &key, NULL);
btval_reset(&key);
if (rc == BT_FAIL && errno != ENOENT)
return -1;
return 0;
}
int
unindex_entry(struct namespace *ns, struct btval *dn, struct ber_element *elm)
{
struct ber_element *a;
struct attr_index *ai;
assert(ns);
assert(dn);
assert(elm);
TAILQ_FOREACH(ai, &ns->indices, next) {
a = ldap_get_attribute(elm, ai->attr);
if (a && unindex_attribute(ns, ai->attr, dn, a) < 0)
return -1;
}
return unindex_rdn(ns, dn);
}
/* Reconstruct the full dn from the index key and the namespace suffix.
*
* Examples:
*
* index key:
* sn=Bacon,cn=chunky bacon,ou=people,
* full dn:
* cn=chunky bacon,ou=people,dc=example,dc=com
*
* index key:
* @ou=people,cn=chunky bacon
* full dn:
* cn=chunky bacon,ou=people,dc=example,dc=com
*
* index key:
* @,ou=people
* full dn:
* ou=people,dc=example,dc=com
*
* index key:
* @ou=staff,ou=people,cn=chunky bacon
* full dn:
* cn=chunky bacon,ou=staff,ou=people,dc=example,dc=com
*
* Filled in dn must be freed with btval_reset().
*/
int
index_to_dn(struct namespace *ns, struct btval *indx, struct btval *dn)
{
char *rdn, *parent_rdn, indxtype, *dst;
int rdn_sz, prdn_sz;
/* Skip past first index part to get the RDN.
*/
indxtype = ((char *)indx->data)[0];
if (indxtype == '@') {
/* One-level index.
* Full DN is made up of rdn + parent rdn + namespace suffix.
*/
rdn = memrchr(indx->data, ',', indx->size);
if (rdn++ == NULL)
return -1;
rdn_sz = indx->size - (rdn - (char *)indx->data);
parent_rdn = (char *)indx->data + 1;
prdn_sz = rdn - parent_rdn - 1;
dn->size = indx->size + strlen(ns->suffix);
if (prdn_sz == 0)
dn->size--;
if ((dn->data = malloc(dn->size)) == NULL) {
log_warn("conn_search: malloc");
return -1;
}
dst = dn->data;
bcopy(rdn, dst, rdn_sz);
dst += rdn_sz;
*dst++ = ',';
bcopy(parent_rdn, dst, prdn_sz);
dst += prdn_sz;
if (prdn_sz > 0)
*dst++ = ',';
bcopy(ns->suffix, dst, strlen(ns->suffix));
} else {
/* Construct the full DN by appending namespace suffix.
*/
rdn = memchr(indx->data, ',', indx->size);
if (rdn++ == NULL)
return -1;
rdn_sz = indx->size - (rdn - (char *)indx->data);
dn->size = rdn_sz + strlen(ns->suffix);
if ((dn->data = malloc(dn->size)) == NULL) {
log_warn("index_to_dn: malloc");
return -1;
}
bcopy(rdn, dn->data, rdn_sz);
bcopy(ns->suffix, (char *)dn->data + rdn_sz,
strlen(ns->suffix));
}
dn->free_data = 1;
return 0;
}