schema_init.c

/* schema_init.c - init builtin schema */
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
 * Copyright 1998-2020 The OpenLDAP Foundation.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in the file LICENSE in the
 * top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
 */

/*
 * Syntaxes - implementation notes:
 *
 * Validate function(syntax, value):
 *   Called before the other functions here to check if the value
 *   is valid according to the syntax.
 *
 * Pretty function(syntax, input value, output prettified...):
 *   If it exists, maps different notations of the same value to a
 *   unique representation which can be stored in the directory and
 *   possibly be passed to the Match/Indexer/Filter() functions.
 *
 *   E.g. DN "2.5.4.3 = foo\,bar, o = BAZ" -> "cn=foo\2Cbar,o=BAZ",
 *   but unlike DN normalization, "BAZ" is not mapped to "baz".
 */

/*
 * Matching rules - implementation notes:
 *
 * Matching rules match an attribute value (often from the directory)
 * against an asserted value (e.g. from a filter).
 *
 * Invoked with validated and commonly pretty/normalized arguments, thus
 * a number of matching rules can simply use the octetString functions.
 *
 * Normalize function(...input value, output normalized...):
 *   If it exists, maps matching values to a unique representation
 *   which is passed to the Match/Indexer/Filter() functions.
 *
 *   Different matching rules can normalize values of the same syntax
 *   differently.  E.g. caseIgnore rules normalize to lowercase,
 *   caseExact rules do not.
 *
 * Match function(*output matchp, ...value, asserted value):
 *   On success, set *matchp.  0 means match.  For ORDERING/most EQUALITY,
 *   less/greater than 0 means value less/greater than asserted.  However:
 *
 *   In extensible match filters, ORDERING rules match if value<asserted.
 *
 *   EQUALITY rules may order values differently than ORDERING rules for
 *   speed, since EQUALITY ordering is only used for SLAP_AT_SORTED_VAL.
 *   Some EQUALITY rules do not order values (ITS#6722).
 *
 * Indexer function(...attribute values, *output keysp,...):
 *   Generates index keys for the attribute values.  Backends can store
 *   them in an index, a {key->entry ID set} mapping, for the attribute.
 *
 *   A search can look up the DN/scope and asserted values in the
 *   indexes, if any, to narrow down the number of entires to check
 *   against the search criteria.
 *
 * Filter function(...asserted value, *output keysp,...):
 *   Generates index key(s) for the asserted value, to be looked up in
 *   the index from the Indexer function.  *keysp is an array because
 *   substring matching rules can generate multiple lookup keys.
 *
 * Index keys:
 *   A key is usually a hash of match type, attribute value and schema
 *   info, because one index can contain keys for many filtering types.
 *
 *   Some indexes instead have EQUALITY keys ordered so that if
 *   key(val1) < key(val2), then val1 < val2 by the ORDERING rule.
 *   That way the ORDERING rule can use the EQUALITY index.
 *
 * Substring indexing:
 *   This chops the attribute values up in small chunks and indexes all
 *   possible chunks of certain sizes.  Substring filtering looks up
 *   SOME of the asserted value's chunks, and the caller uses the
 *   intersection of the resulting entry ID sets.
 *   See the index_substr_* keywords in slapd.conf(5).
 */

#include "portable.h"

#include <stdio.h>
#ifdef HAVE_LIMITS_H
#include <limits.h>
#endif

#include <ac/ctype.h>
#include <ac/errno.h>
#include <ac/string.h>
#include <ac/socket.h>

#include "slap.h"
#include "../../libraries/liblber/lber-int.h" /* get ber_ptrlen() */

#include "ldap_utf8.h"

#include "lutil.h"
#include "lutil_hash.h"
#define HASH_BYTES				LUTIL_HASH_BYTES
#define HASH_CONTEXT			lutil_HASH_CTX
#define HASH_Init(c)			lutil_HASHInit(c)
#define HASH_Update(c,buf,len)	lutil_HASHUpdate(c,buf,len)
#define HASH_Final(d,c)			lutil_HASHFinal(d,c)

/* approx matching rules */
#define directoryStringApproxMatchOID	"1.3.6.1.4.1.4203.666.4.4"
#define directoryStringApproxMatch		approxMatch
#define directoryStringApproxIndexer	approxIndexer
#define directoryStringApproxFilter		approxFilter
#define IA5StringApproxMatchOID			"1.3.6.1.4.1.4203.666.4.5"
#define IA5StringApproxMatch			approxMatch
#define IA5StringApproxIndexer			approxIndexer
#define IA5StringApproxFilter			approxFilter

/* Change Sequence Number (CSN) - much of this will change */
#define csnMatch				octetStringMatch
#define csnOrderingMatch		octetStringOrderingMatch
#define csnIndexer				generalizedTimeIndexer
#define csnFilter				generalizedTimeFilter

#define authzMatch				octetStringMatch

/* X.509 PMI ldapSyntaxes */
/* FIXME: need to create temporary OIDs under OpenLDAP's arc;
 * these are currently hijacked
 *
 *	1.3.6.1.4.1.4203.666		OpenLDAP
 *	1.3.6.1.4.1.4203.666.11		self-contained works
 *	1.3.6.1.4.1.4203.666.11.10	X.509 PMI
 *	1.3.6.1.4.1.4203.666.11.10.2	X.509 PMI ldapSyntaxes
 *	1.3.6.1.4.1.4203.666.11.10.2.1	AttributeCertificate (supported)
 *	1.3.6.1.4.1.4203.666.11.10.2.2	AttributeCertificateExactAssertion (supported)
 *	1.3.6.1.4.1.4203.666.11.10.2.3	AttributeCertificateAssertion (not supported)
 *	1.3.6.1.4.1.4203.666.11.10.2.4	AttCertPath (X-SUBST'ed right now in pmi.schema)
 *	1.3.6.1.4.1.4203.666.11.10.2.5	PolicySyntax (X-SUBST'ed right now in pmi.schema)
 *	1.3.6.1.4.1.4203.666.11.10.2.6	RoleSyntax (X-SUBST'ed right now in pmi.schema)
 */
#if 0 /* from <draft-ietf-pkix-ldap-schema-02.txt> (expired) */
#define attributeCertificateSyntaxOID			"1.2.826.0.1.3344810.7.5"
#define attributeCertificateExactAssertionSyntaxOID	"1.2.826.0.1.3344810.7.6"
#define attributeCertificateAssertionSyntaxOID		"1.2.826.0.1.3344810.7.7"
#else /* from OpenLDAP's experimental oid arc */
#define X509_PMI_SyntaxOID				"1.3.6.1.4.1.4203.666.11.10.2"
#define attributeCertificateSyntaxOID			X509_PMI_SyntaxOID ".1"
#define attributeCertificateExactAssertionSyntaxOID	X509_PMI_SyntaxOID ".2"
#define attributeCertificateAssertionSyntaxOID		X509_PMI_SyntaxOID ".3"
#endif

unsigned int index_substr_if_minlen = SLAP_INDEX_SUBSTR_IF_MINLEN_DEFAULT;
unsigned int index_substr_if_maxlen = SLAP_INDEX_SUBSTR_IF_MAXLEN_DEFAULT;
unsigned int index_substr_any_len = SLAP_INDEX_SUBSTR_ANY_LEN_DEFAULT;
unsigned int index_substr_any_step = SLAP_INDEX_SUBSTR_ANY_STEP_DEFAULT;

unsigned int index_intlen = SLAP_INDEX_INTLEN_DEFAULT;
unsigned int index_intlen_strlen = SLAP_INDEX_INTLEN_STRLEN(
	SLAP_INDEX_INTLEN_DEFAULT );

ldap_pvt_thread_mutex_t	ad_index_mutex;
ldap_pvt_thread_mutex_t	ad_undef_mutex;
ldap_pvt_thread_mutex_t	oc_undef_mutex;

static int
generalizedTimeValidate(
	Syntax *syntax,
	struct berval *in );

#ifdef SUPPORT_OBSOLETE_UTC_SYNTAX
static int
utcTimeValidate(
	Syntax *syntax,
	struct berval *in );
#endif /* SUPPORT_OBSOLETE_UTC_SYNTAX */

static int
inValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* no value allowed */
	return LDAP_INVALID_SYNTAX;
}

static int
blobValidate(
	Syntax *syntax,
	struct berval *in )
{
	/* any value allowed */
	return LDAP_SUCCESS;
}

#define berValidate blobValidate

static int
sequenceValidate(
	Syntax *syntax,
	struct berval *in )
{
	if ( in->bv_len < 2 ) return LDAP_INVALID_SYNTAX;
	if ( in->bv_val[0] != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;

	return LDAP_SUCCESS;
}

/* X.509 related stuff */

enum {
	SLAP_X509_V1		= 0,
	SLAP_X509_V2		= 1,
	SLAP_X509_V3		= 2
};

enum {
	SLAP_TAG_UTCTIME		= 0x17U,
	SLAP_TAG_GENERALIZEDTIME	= 0x18U
};


#define	SLAP_X509_OPTION	(LBER_CLASS_CONTEXT|LBER_CONSTRUCTED)

enum {
	SLAP_X509_OPT_C_VERSION		= SLAP_X509_OPTION + 0,
	SLAP_X509_OPT_C_ISSUERUNIQUEID	= LBER_CLASS_CONTEXT + 1,
	SLAP_X509_OPT_C_SUBJECTUNIQUEID	= LBER_CLASS_CONTEXT + 2,
	SLAP_X509_OPT_C_EXTENSIONS	= SLAP_X509_OPTION + 3
};

enum {
	SLAP_X509_OPT_CL_CRLEXTENSIONS	= SLAP_X509_OPTION + 0
};

/*
GeneralName ::= CHOICE {
  otherName                 [0] INSTANCE OF OTHER-NAME,
  rfc822Name                [1] IA5String,
  dNSName                   [2] IA5String,
  x400Address               [3] ORAddress,
  directoryName             [4] Name,
  ediPartyName              [5] EDIPartyName,
  uniformResourceIdentifier [6] IA5String,
  iPAddress                 [7] OCTET STRING,
  registeredID              [8] OBJECT IDENTIFIER }
*/
enum {
	SLAP_X509_GN_OTHERNAME		= SLAP_X509_OPTION + 0,
	SLAP_X509_GN_RFC822NAME		= SLAP_X509_OPTION + 1,
	SLAP_X509_GN_DNSNAME		= SLAP_X509_OPTION + 2,
	SLAP_X509_GN_X400ADDRESS	= SLAP_X509_OPTION + 3,
	SLAP_X509_GN_DIRECTORYNAME	= SLAP_X509_OPTION + 4,
	SLAP_X509_GN_EDIPARTYNAME	= SLAP_X509_OPTION + 5,
	SLAP_X509_GN_URI		= SLAP_X509_OPTION + 6,
	SLAP_X509_GN_IPADDRESS		= SLAP_X509_OPTION + 7,
	SLAP_X509_GN_REGISTEREDID	= SLAP_X509_OPTION + 8
};

/* X.509 PMI related stuff */
enum {
	SLAP_X509AC_V1		= 0,
	SLAP_X509AC_V2		= 1
};

enum {
	SLAP_X509AC_ISSUER	= SLAP_X509_OPTION + 0
};

/* X.509 certificate validation */
static int
certificateValidate( Syntax *syntax, struct berval *in )
{
	BerElementBuffer berbuf;
	BerElement *ber = (BerElement *)&berbuf;
	ber_tag_t tag;
	ber_len_t len;
	ber_int_t version = SLAP_X509_V1;

	ber_init2( ber, in, LBER_USE_DER );
	tag = ber_skip_tag( ber, &len );	/* Signed wrapper */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	tag = ber_skip_tag( ber, &len );	/* Sequence */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	tag = ber_peek_tag( ber, &len );
	/* Optional version */
	if ( tag == SLAP_X509_OPT_C_VERSION ) {
		tag = ber_skip_tag( ber, &len );
		tag = ber_get_int( ber, &version );
		if ( tag != LBER_INTEGER ) return LDAP_INVALID_SYNTAX;
	}
	/* NOTE: don't try to parse Serial, because it might be longer
	 * than sizeof(ber_int_t); deferred to certificateExactNormalize() */
	tag = ber_skip_tag( ber, &len );	/* Serial */
	if ( tag != LBER_INTEGER ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );	/* Signature Algorithm */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );	/* Issuer DN */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );	/* Validity */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );	/* Subject DN */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );	/* Subject PublicKeyInfo */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );
	if ( tag == SLAP_X509_OPT_C_ISSUERUNIQUEID ) {	/* issuerUniqueID */
		if ( version < SLAP_X509_V2 ) return LDAP_INVALID_SYNTAX;
		ber_skip_data( ber, len );
		tag = ber_skip_tag( ber, &len );
	}
	if ( tag == SLAP_X509_OPT_C_SUBJECTUNIQUEID ) {	/* subjectUniqueID */
		if ( version < SLAP_X509_V2 ) return LDAP_INVALID_SYNTAX;
		ber_skip_data( ber, len );
		tag = ber_skip_tag( ber, &len );
	}
	if ( tag == SLAP_X509_OPT_C_EXTENSIONS ) {	/* Extensions */
		if ( version < SLAP_X509_V3 ) return LDAP_INVALID_SYNTAX;
		tag = ber_skip_tag( ber, &len );
		if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
		ber_skip_data( ber, len );
		tag = ber_skip_tag( ber, &len );
	}
	/* signatureAlgorithm */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );
	/* Signature */
	if ( tag != LBER_BITSTRING ) return LDAP_INVALID_SYNTAX; 
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );
	/* Must be at end now */
	if ( len || tag != LBER_DEFAULT ) return LDAP_INVALID_SYNTAX;
	return LDAP_SUCCESS;
}

/* X.509 certificate list validation */
static int
checkTime( struct berval *in, struct berval *out );

static int
certificateListValidate( Syntax *syntax, struct berval *in )
{
	BerElementBuffer berbuf;
	BerElement *ber = (BerElement *)&berbuf;
	ber_tag_t tag;
	ber_len_t len, wrapper_len;
	char *wrapper_start;
	int wrapper_ok = 0;
	ber_int_t version = SLAP_X509_V1;
	struct berval bvdn, bvtu;

	ber_init2( ber, in, LBER_USE_DER );
	tag = ber_skip_tag( ber, &wrapper_len );	/* Signed wrapper */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	wrapper_start = ber->ber_ptr;
	tag = ber_skip_tag( ber, &len );	/* Sequence */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	tag = ber_peek_tag( ber, &len );
	/* Optional version */
	if ( tag == LBER_INTEGER ) {
		tag = ber_get_int( ber, &version );
		assert( tag == LBER_INTEGER );
		if ( version != SLAP_X509_V2 ) return LDAP_INVALID_SYNTAX;
	}
	tag = ber_skip_tag( ber, &len );	/* Signature Algorithm */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );
	tag = ber_peek_tag( ber, &len );	/* Issuer DN */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	len = ber_ptrlen( ber );
	bvdn.bv_val = in->bv_val + len;
	bvdn.bv_len = in->bv_len - len;
	tag = ber_skip_tag( ber, &len );
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );	/* thisUpdate */
	/* Time is a CHOICE { UTCTime, GeneralizedTime } */
	if ( tag != SLAP_TAG_UTCTIME && tag != SLAP_TAG_GENERALIZEDTIME ) return LDAP_INVALID_SYNTAX;
	bvtu.bv_val = (char *)ber->ber_ptr;
	bvtu.bv_len = len;
	ber_skip_data( ber, len );
	/* Optional nextUpdate */
	tag = ber_skip_tag( ber, &len );
	if ( tag == SLAP_TAG_UTCTIME || tag == SLAP_TAG_GENERALIZEDTIME ) {
		ber_skip_data( ber, len );
		tag = ber_skip_tag( ber, &len );
	}
	/* revokedCertificates - Sequence of Sequence, Optional */
	if ( tag == LBER_SEQUENCE ) {
		ber_len_t seqlen;
		ber_tag_t stag;
		stag = ber_peek_tag( ber, &seqlen );
		if ( stag == LBER_SEQUENCE || !len ) {
			/* RFC5280 requires non-empty, but X.509(2005) allows empty. */
			if ( len )
				ber_skip_data( ber, len );
			tag = ber_skip_tag( ber, &len );
		}
	}
	/* Optional Extensions - Sequence of Sequence */
	if ( tag == SLAP_X509_OPT_CL_CRLEXTENSIONS ) { /* ? */
		ber_len_t seqlen;
		if ( version != SLAP_X509_V2 ) return LDAP_INVALID_SYNTAX;
		tag = ber_peek_tag( ber, &seqlen );
		if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
		ber_skip_data( ber, len );
		tag = ber_skip_tag( ber, &len );
	}
	/* signatureAlgorithm */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );
	tag = ber_skip_tag( ber, &len );
	/* Signature */
	if ( tag != LBER_BITSTRING ) return LDAP_INVALID_SYNTAX; 
	ber_skip_data( ber, len );
	if ( ber->ber_ptr == wrapper_start + wrapper_len ) wrapper_ok = 1;
	tag = ber_skip_tag( ber, &len );
	/* Must be at end now */
	/* NOTE: OpenSSL tolerates CL with garbage past the end */
	if ( len || tag != LBER_DEFAULT ) {
		struct berval issuer_dn = BER_BVNULL, thisUpdate;
		char tubuf[STRLENOF("YYYYmmddHHMMSSZ") + 1];
		int rc;

		if ( ! wrapper_ok ) {
			return LDAP_INVALID_SYNTAX;
		}

		rc = dnX509normalize( &bvdn, &issuer_dn );
		if ( rc != LDAP_SUCCESS ) {
			rc = LDAP_INVALID_SYNTAX;
			goto done;
		}

		thisUpdate.bv_val = tubuf;
		thisUpdate.bv_len = sizeof(tubuf); 
		if ( checkTime( &bvtu, &thisUpdate ) ) {
			rc = LDAP_INVALID_SYNTAX;
			goto done;
		}

		Debug( LDAP_DEBUG_ANY,
			"certificateListValidate issuer=\"%s\", thisUpdate=%s: extra cruft past end of certificateList\n",
			issuer_dn.bv_val, thisUpdate.bv_val, 0 );

done:;
		if ( ! BER_BVISNULL( &issuer_dn ) ) {
			ber_memfree( issuer_dn.bv_val );
		}

		return rc;
	}

	return LDAP_SUCCESS;
}

/* X.509 PMI Attribute Certificate Validate */
static int
attributeCertificateValidate( Syntax *syntax, struct berval *in )
{
	BerElementBuffer berbuf;
	BerElement *ber = (BerElement *)&berbuf;
	ber_tag_t tag;
	ber_len_t len;
	ber_int_t version;
	int cont = 0;

	ber_init2( ber, in, LBER_USE_DER );
	
	tag = ber_skip_tag( ber, &len );	/* Signed wrapper */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;

	tag = ber_skip_tag( ber, &len );	/* Sequence */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;

	tag = ber_peek_tag( ber, &len );	/* Version */
	if ( tag != LBER_INTEGER ) return LDAP_INVALID_SYNTAX;
	tag = ber_get_int( ber, &version );	/* X.509 only allows v2 */
	if ( version != SLAP_X509AC_V2 ) return LDAP_INVALID_SYNTAX;

	tag = ber_skip_tag( ber, &len );	/* Holder */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );

	tag = ber_skip_tag( ber, &len );	/* Issuer */
	if ( tag != SLAP_X509AC_ISSUER ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );

	tag = ber_skip_tag( ber, &len );	/* Signature */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );

	tag = ber_skip_tag( ber, &len );	/* Serial number */
	if ( tag != LBER_INTEGER ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );

	tag = ber_skip_tag( ber, &len );	/* AttCertValidityPeriod */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );

	tag = ber_skip_tag( ber, &len );	/* Attributes */
	if ( tag != LBER_SEQUENCE ) return LDAP_INVALID_SYNTAX;
	ber_skip_data( ber, len );

	tag = ber_peek_tag( ber, &len );

	if ( tag == LBER_BITSTRING ) {	/* issuerUniqueID */
		tag = ber_skip_tag( ber, &len );
		ber_skip_data( ber, len );
		tag = ber_peek_tag( ber, &len );
	}

	if ( tag == LBER_SEQUENCE ) {	/* extensions or signatureAlgorithm */
		tag = ber_skip_tag( ber, &len );
		ber_skip_data( ber, len );
		cont++;
		tag = ber_peek_tag( ber, &len );
	}

	if ( tag == LBER_SEQUENCE ) {	/* signatureAlgorithm */
		tag = ber_skip_tag( ber, &len );
		ber_skip_data( ber, len );
		cont++;
		tag = ber_peek_tag( ber, &len );
	}

	if ( tag == LBER_BITSTRING ) {	/* Signature */
		tag = ber_skip_tag( ber, &len );
		ber_skip_data( ber, len );
		cont++;
		tag = ber_peek_tag( ber, &len );
	}

	/* Must be at end now */
	if ( len != 0 || tag != LBER_DEFAULT || cont < 2 ) return LDAP_INVALID_SYNTAX;

	return LDAP_SUCCESS;
}

int
octetStringMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	struct berval *asserted = (struct berval *) assertedValue;
	ber_slen_t d = (ber_slen_t) value->bv_len - (ber_slen_t) asserted->bv_len;

	/* For speed, order first by length, then by contents */
	*matchp = d ? (sizeof(d) == sizeof(int) ? d : d < 0 ? -1 : 1)
		: memcmp( value->bv_val, asserted->bv_val, value->bv_len );

	return LDAP_SUCCESS;
}

int
octetStringOrderingMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	struct berval *asserted = (struct berval *) assertedValue;
	ber_len_t v_len  = value->bv_len;
	ber_len_t av_len = asserted->bv_len;

	int match = memcmp( value->bv_val, asserted->bv_val,
		(v_len < av_len ? v_len : av_len) );

	if( match == 0 )
		match = sizeof(v_len) == sizeof(int)
			? (int) v_len - (int) av_len
			: v_len < av_len ? -1 : v_len > av_len;

	/* If used in extensible match filter, match if value < asserted */
	if ( flags & SLAP_MR_EXT )
		match = (match >= 0);

	*matchp = match;
	return LDAP_SUCCESS;
}

/* Initialize HASHcontext from match type and schema info */
static void
hashPreset(
	HASH_CONTEXT *HASHcontext,
	struct berval *prefix,
	char pre,
	Syntax *syntax,
	MatchingRule *mr)
{
	HASH_Init(HASHcontext);
	if(prefix && prefix->bv_len > 0) {
		HASH_Update(HASHcontext,
			(unsigned char *)prefix->bv_val, prefix->bv_len);
	}
	if(pre) HASH_Update(HASHcontext, (unsigned char*)&pre, sizeof(pre));
	HASH_Update(HASHcontext, (unsigned char*)syntax->ssyn_oid, syntax->ssyn_oidlen);
	HASH_Update(HASHcontext, (unsigned char*)mr->smr_oid, mr->smr_oidlen);
	return;
}

/* Set HASHdigest from HASHcontext and value:len */
static void
hashIter(
	HASH_CONTEXT *HASHcontext,
	unsigned char *HASHdigest,
	unsigned char *value,
	int len)
{
	HASH_CONTEXT ctx = *HASHcontext;
	HASH_Update( &ctx, value, len );
	HASH_Final( HASHdigest, &ctx );
}

/* Index generation function: Attribute values -> index hash keys */
int octetStringIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	BerVarray values,
	BerVarray *keysp,
	void *ctx )
{
	int i;
	size_t slen, mlen;
	BerVarray keys;
	HASH_CONTEXT HASHcontext;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval digest;
	digest.bv_val = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	for( i=0; !BER_BVISNULL( &values[i] ); i++ ) {
		/* just count them */
	}

	/* we should have at least one value at this point */
	assert( i > 0 );

	keys = slap_sl_malloc( sizeof( struct berval ) * (i+1), ctx );

	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;

	hashPreset( &HASHcontext, prefix, 0, syntax, mr);
	for( i=0; !BER_BVISNULL( &values[i] ); i++ ) {
		hashIter( &HASHcontext, HASHdigest,
			(unsigned char *)values[i].bv_val, values[i].bv_len );
		ber_dupbv_x( &keys[i], &digest, ctx );
	}

	BER_BVZERO( &keys[i] );

	*keysp = keys;

	return LDAP_SUCCESS;
}

/* Index generation function: Asserted value -> index hash key */
int octetStringFilter(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertedValue,
	BerVarray *keysp,
	void *ctx )
{
	size_t slen, mlen;
	BerVarray keys;
	HASH_CONTEXT HASHcontext;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval *value = (struct berval *) assertedValue;
	struct berval digest;
	digest.bv_val = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;

	keys = slap_sl_malloc( sizeof( struct berval ) * 2, ctx );

	hashPreset( &HASHcontext, prefix, 0, syntax, mr );
	hashIter( &HASHcontext, HASHdigest,
		(unsigned char *)value->bv_val, value->bv_len );

	ber_dupbv_x( keys, &digest, ctx );
	BER_BVZERO( &keys[1] );

	*keysp = keys;

	return LDAP_SUCCESS;
}

static int
octetStringSubstringsMatch(
	int *matchp,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *value,
	void *assertedValue )
{
	int match = 0;
	SubstringsAssertion *sub = assertedValue;
	struct berval left = *value;
	int i;
	ber_len_t inlen = 0;

	/* Add up asserted input length */
	if ( !BER_BVISNULL( &sub->sa_initial ) ) {
		inlen += sub->sa_initial.bv_len;
	}
	if ( sub->sa_any ) {
		for ( i = 0; !BER_BVISNULL( &sub->sa_any[i] ); i++ ) {
			inlen += sub->sa_any[i].bv_len;
		}
	}
	if ( !BER_BVISNULL( &sub->sa_final ) ) {
		inlen += sub->sa_final.bv_len;
	}

	if ( !BER_BVISNULL( &sub->sa_initial ) ) {
		if ( inlen > left.bv_len ) {
			match = 1;
			goto done;
		}

		match = memcmp( sub->sa_initial.bv_val, left.bv_val,
			sub->sa_initial.bv_len );

		if ( match != 0 ) {
			goto done;
		}

		left.bv_val += sub->sa_initial.bv_len;
		left.bv_len -= sub->sa_initial.bv_len;
		inlen -= sub->sa_initial.bv_len;
	}

	if ( !BER_BVISNULL( &sub->sa_final ) ) {
		if ( inlen > left.bv_len ) {
			match = 1;
			goto done;
		}

		match = memcmp( sub->sa_final.bv_val,
			&left.bv_val[left.bv_len - sub->sa_final.bv_len],
			sub->sa_final.bv_len );

		if ( match != 0 ) {
			goto done;
		}

		left.bv_len -= sub->sa_final.bv_len;
		inlen -= sub->sa_final.bv_len;
	}

	if ( sub->sa_any ) {
		for ( i = 0; !BER_BVISNULL( &sub->sa_any[i] ); i++ ) {
			ber_len_t idx;
			char *p;

retry:
			if ( inlen > left.bv_len ) {
				/* not enough length */
				match = 1;
				goto done;
			}

			if ( BER_BVISEMPTY( &sub->sa_any[i] ) ) {
				continue;
			}

			p = memchr( left.bv_val, *sub->sa_any[i].bv_val, left.bv_len );

			if( p == NULL ) {
				match = 1;
				goto done;
			}

			idx = p - left.bv_val;

			if ( idx >= left.bv_len ) {
				/* this shouldn't happen */
				return LDAP_OTHER;
			}

			left.bv_val = p;
			left.bv_len -= idx;

			if ( sub->sa_any[i].bv_len > left.bv_len ) {
				/* not enough left */
				match = 1;
				goto done;
			}

			match = memcmp( left.bv_val,
				sub->sa_any[i].bv_val,
				sub->sa_any[i].bv_len );

			if ( match != 0 ) {
				left.bv_val++;
				left.bv_len--;
				goto retry;
			}

			left.bv_val += sub->sa_any[i].bv_len;
			left.bv_len -= sub->sa_any[i].bv_len;
			inlen -= sub->sa_any[i].bv_len;
		}
	}

done:
	*matchp = match;
	return LDAP_SUCCESS;
}

/* Substring index generation function: Attribute values -> index hash keys */
static int
octetStringSubstringsIndexer(
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	BerVarray values,
	BerVarray *keysp,
	void *ctx )
{
	ber_len_t i, nkeys;
	size_t slen, mlen;
	BerVarray keys;

	HASH_CONTEXT HCany, HCini, HCfin;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval digest;
	digest.bv_val = (char *)HASHdigest;
	digest.bv_len = sizeof(HASHdigest);

	nkeys = 0;

	for ( i = 0; !BER_BVISNULL( &values[i] ); i++ ) {
		/* count number of indices to generate */
		if( flags & SLAP_INDEX_SUBSTR_INITIAL ) {
			if( values[i].bv_len >= index_substr_if_maxlen ) {
				nkeys += index_substr_if_maxlen -
					(index_substr_if_minlen - 1);
			} else if( values[i].bv_len >= index_substr_if_minlen ) {
				nkeys += values[i].bv_len - (index_substr_if_minlen - 1);
			}
		}

		if( flags & SLAP_INDEX_SUBSTR_ANY ) {
			if( values[i].bv_len >= index_substr_any_len ) {
				nkeys += values[i].bv_len - (index_substr_any_len - 1);
			}
		}

		if( flags & SLAP_INDEX_SUBSTR_FINAL ) {
			if( values[i].bv_len >= index_substr_if_maxlen ) {
				nkeys += index_substr_if_maxlen -
					(index_substr_if_minlen - 1);
			} else if( values[i].bv_len >= index_substr_if_minlen ) {
				nkeys += values[i].bv_len - (index_substr_if_minlen - 1);
			}
		}
	}

	if( nkeys == 0 ) {
		/* no keys to generate */
		*keysp = NULL;
		return LDAP_SUCCESS;
	}

	keys = slap_sl_malloc( sizeof( struct berval ) * (nkeys+1), ctx );

	slen = syntax->ssyn_oidlen;
	mlen = mr->smr_oidlen;

	if ( flags & SLAP_INDEX_SUBSTR_ANY )
		hashPreset( &HCany, prefix, SLAP_INDEX_SUBSTR_PREFIX, syntax, mr );
	if( flags & SLAP_INDEX_SUBSTR_INITIAL )
		hashPreset( &HCini, prefix, SLAP_INDEX_SUBSTR_INITIAL_PREFIX, syntax, mr );
	if( flags & SLAP_INDEX_SUBSTR_FINAL )
		hashPreset( &HCfin, prefix, SLAP_INDEX_SUBSTR_FINAL_PREFIX, syntax, mr );

	nkeys = 0;
	for ( i = 0; !BER_BVISNULL( &values[i] ); i++ ) {
		ber_len_t j,max;

		if( ( flags & SLAP_INDEX_SUBSTR_ANY ) &&
			( values[i].bv_len >= index_substr_any_len ) )
		{
			max = values[i].bv_len - (index_substr_any_len - 1);

			for( j=0; j<max; j++ ) {
				hashIter( &HCany, HASHdigest,
					(unsigned char *)&values[i].bv_val[j],
					index_substr_any_len );
				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}
		}

		/* skip if too short */ 
		if( values[i].bv_len < index_substr_if_minlen ) continue;

		max = index_substr_if_maxlen < values[i].bv_len
			? index_substr_if_maxlen : values[i].bv_len;

		for( j=index_substr_if_minlen; j<=max; j++ ) {

			if( flags & SLAP_INDEX_SUBSTR_INITIAL ) {
				hashIter( &HCini, HASHdigest,
					(unsigned char *)values[i].bv_val, j );
				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}

			if( flags & SLAP_INDEX_SUBSTR_FINAL ) {
				hashIter( &HCfin, HASHdigest,
					(unsigned char *)&values[i].bv_val[values[i].bv_len-j], j );
				ber_dupbv_x( &keys[nkeys++], &digest, ctx );
			}

		}
	}

	if( nkeys > 0 ) {
		BER_BVZERO( &keys[nkeys] );
		*keysp = keys;
	} else {
		ch_free( keys );
		*keysp = NULL;
	}

	return LDAP_SUCCESS;
}

/* Substring index generation function: Assertion value -> index hash keys */
static int
octetStringSubstringsFilter (
	slap_mask_t use,
	slap_mask_t flags,
	Syntax *syntax,
	MatchingRule *mr,
	struct berval *prefix,
	void * assertedValue,
	BerVarray *keysp,
	void *ctx)
{
	SubstringsAssertion *sa;
	char pre;
	ber_len_t nkeys = 0;
	size_t slen, mlen, klen;
	BerVarray keys;
	HASH_CONTEXT HASHcontext;
	unsigned char HASHdigest[HASH_BYTES];
	struct berval *value;
	struct berval digest;

	sa = (SubstringsAssertion *) assertedValue;

	if( flags & SLAP_INDEX_SUBSTR_INITIAL &&
		!BER_BVISNULL( &sa->sa_initial ) &&
		sa->sa_initial.bv_len >= index_substr_if_minlen )
	{
		nkeys++;
		if ( sa->sa_initial.bv_len > index_substr_if_maxlen &&
			( flags & SLAP_INDEX_SUBSTR_ANY ))
		{
			nkeys += 1 + (sa->sa_initial.bv_len - index_substr_if_maxlen) / index_substr_any_step;
		}
	}

	if ( flags & SLAP_INDEX_SUBSTR_ANY && sa->sa_any != NULL ) {
		ber_len_t i;
		for( i=0; !BER_BVISNULL( &sa->sa_any[i] ); i++ ) {
			if( sa->sa_any[i].bv_len >= index_substr_any_len ) {
				/* don't bother accounting with stepping */
				nkeys += sa->sa_any[i].bv_len -