From bee0650d9ccf930491f6b9cbf2e149a93e0770d8 Mon Sep 17 00:00:00 2001 From: Kurt Zeilenga Date: Fri, 15 Jun 2001 07:08:37 +0000 Subject: [PATCH] Work in progress codes. !UNTESTED! --- servers/slapd/back-bdb/add.c | 4 +- servers/slapd/back-bdb/back-bdb.h | 13 +- servers/slapd/back-bdb/backbdb.dsp | 8 + servers/slapd/back-bdb/dn2id.c | 45 ++ servers/slapd/back-bdb/filterindex.c | 598 +++++++++++++++++++++++++++ servers/slapd/back-bdb/idl.c | 225 ++++++++++ servers/slapd/back-bdb/idl.h | 57 +++ servers/slapd/back-bdb/modify.c | 11 +- servers/slapd/back-bdb/modrdn.c | 5 +- servers/slapd/back-bdb/nextid.c | 3 + servers/slapd/back-bdb/passwd.c | 5 +- servers/slapd/back-bdb/proto-bdb.h | 64 ++- servers/slapd/back-bdb/search.c | 74 +--- 13 files changed, 1039 insertions(+), 73 deletions(-) create mode 100644 servers/slapd/back-bdb/filterindex.c create mode 100644 servers/slapd/back-bdb/idl.h diff --git a/servers/slapd/back-bdb/add.c b/servers/slapd/back-bdb/add.c index 346c032f10..06de7a69df 100644 --- a/servers/slapd/back-bdb/add.c +++ b/servers/slapd/back-bdb/add.c @@ -25,6 +25,8 @@ bdb_add( Entry *p = NULL; int rc; const char *text; + char textbuf[SLAP_TEXT_BUFLEN]; + size_t textlen = sizeof textbuf; AttributeDescription *children = slap_schema.si_ad_children; DB_TXN *ltid = NULL; struct bdb_op_info opinfo; @@ -32,7 +34,7 @@ bdb_add( Debug(LDAP_DEBUG_ARGS, "==> bdb_add: %s\n", e->e_dn, 0, 0); /* check entry's schema */ - rc = entry_schema_check( e, NULL, &text ); + rc = entry_schema_check( e, NULL, &text, textbuf, textlen ); if ( rc != LDAP_SUCCESS ) { Debug( LDAP_DEBUG_TRACE, "bdb_add: entry failed schema check: %s (%d)\n", diff --git a/servers/slapd/back-bdb/back-bdb.h b/servers/slapd/back-bdb/back-bdb.h index 0d37f74b89..74a55cecd2 100644 --- a/servers/slapd/back-bdb/back-bdb.h +++ b/servers/slapd/back-bdb/back-bdb.h @@ -15,16 +15,6 @@ LDAP_BEGIN_DECL -#define BDB_IDL_DB_SIZE (1<<16) /* 64K IDL on disk */ -#define BDB_IDL_DB_MAX (BDB_IDL_DB_SIZE-32) -/* #define BDB_IDL_DB_ALLOC (BDB_IDL_DB_SIZE * sizeof(ID)) */ - -#define BDB_IDL_SIZE (1<<17) /* 128K IDL in memory */ -#define BDB_IDL_MAX (BDB_IDL_DB_SIZE-32) -/* #define BDB_IDL_DB_ALLOC (BDB_IDL_DB_SIZE * sizeof(ID)) */ - -#define BDB_IDL_RANGE_SIZE (3 * sizeof(ID)) -#define BDB_IDL_IS_RANGE(ids) ((ids)[0] == NOID) #define DN_BASE_PREFIX SLAP_INDEX_EQUALITY_PREFIX #define DN_ONE_PREFIX '%' @@ -79,7 +69,10 @@ struct bdb_info { int bi_lock_detect_seconds; ldap_pvt_thread_t bi_lock_detect_tid; #endif + + ID bi_lastid; }; + #define bi_nextid bi_databases[BDB_NEXTID] #define bi_id2entry bi_databases[BDB_ID2ENTRY] #define bi_dn2id bi_databases[BDB_DN2ID] diff --git a/servers/slapd/back-bdb/backbdb.dsp b/servers/slapd/back-bdb/backbdb.dsp index e31cc1a786..8e97d8dd40 100644 --- a/servers/slapd/back-bdb/backbdb.dsp +++ b/servers/slapd/back-bdb/backbdb.dsp @@ -171,6 +171,10 @@ SOURCE=.\external.h # End Source File # Begin Source File +SOURCE=.\filterindex.c +# End Source File +# Begin Source File + SOURCE=.\id2entry.c # End Source File # Begin Source File @@ -179,6 +183,10 @@ SOURCE=.\idl.c # End Source File # Begin Source File +SOURCE=.\idl.h +# End Source File +# Begin Source File + SOURCE=.\init.c # End Source File # Begin Source File diff --git a/servers/slapd/back-bdb/dn2id.c b/servers/slapd/back-bdb/dn2id.c index f7f573eabd..71ff928a9a 100644 --- a/servers/slapd/back-bdb/dn2id.c +++ b/servers/slapd/back-bdb/dn2id.c @@ -11,6 +11,7 @@ #include #include "back-bdb.h" +#include "idl.h" int bdb_dn2id_add( @@ -347,3 +348,47 @@ bdb_dn2id_children( return rc; } + +int +bdb_dn2idl( + BackendDB *be, + const char *dn, + int prefix, + ID *ids ) +{ + int rc; + DBT key, data; + struct bdb_info *bdb = (struct bdb_info *) be->be_private; + DB *db = bdb->bi_dn2id->bdi_db; + + Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl( \"%s\" )\n", dn, 0, 0 ); + + DBTzero( &key ); + key.size = strlen( dn ) + 2; + key.data = ch_malloc( key.size ); + ((char *)key.data)[0] = prefix; + AC_MEMCPY( &((char *)key.data)[1], dn, key.size - 1 ); + + /* store the ID */ + DBTzero( &data ); + data.data = ids; + data.ulen = sizeof(ID); + data.flags = DB_DBT_USERMEM; + + /* fetch it */ + rc = db->get( db, NULL, &key, &data, 0 ); + + if( rc != 0 ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_dn2idl: get failed: %s (%d)\n", + db_strerror( rc ), rc, 0 ); + } else { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_dn2idl: id=%ld first=%ld last=%ld\n", + ids[0], BDB_IDL_FIRST( ids ), BDB_IDL_LAST( ids ) ); + } + + ch_free( key.data ); + return rc; +} + diff --git a/servers/slapd/back-bdb/filterindex.c b/servers/slapd/back-bdb/filterindex.c new file mode 100644 index 0000000000..dc76338b19 --- /dev/null +++ b/servers/slapd/back-bdb/filterindex.c @@ -0,0 +1,598 @@ +/* filterindex.c - generate the list of candidate entries from a filter */ +/* $OpenLDAP$ */ +/* + * Copyright 1998-2000 The OpenLDAP Foundation, All Rights Reserved. + * COPYING RESTRICTIONS APPLY, see COPYRIGHT file + */ + +#include "portable.h" + +#include +#include + +#include "back-bdb.h" +#include "idl.h" + +#ifdef BDB_FILTER_INDICES + +static int presence_candidates( + Backend *be, + ID *range, + AttributeDescription *desc, + ID *ids ); +static int equality_candidates( + Backend *be, + ID *range, + AttributeAssertion *ava, + ID *ids ); +static int approx_candidates( + Backend *be, + ID *range, + AttributeAssertion *ava, + ID *ids ); +static int substring_candidates( + Backend *be, + ID *range, + SubstringsAssertion *sub, + ID *ids ); + +static int list_candidates( + Backend *be, + ID *range, + Filter *flist, + int ftype, + ID *ids ); + + +int +bdb_filter_candidates( + Backend *be, + ID *range, + Filter *f, + ID *ids ) +{ + int rc = -1; + Debug( LDAP_DEBUG_FILTER, "=> bdb_filter_candidates\n", 0, 0, 0 ); + + switch ( f->f_choice ) { + case SLAPD_FILTER_DN_ONE: + Debug( LDAP_DEBUG_FILTER, "\tDN ONE\n", 0, 0, 0 ); + rc = bdb_dn2idl( be, f->f_dn, DN_ONE_PREFIX, ids ); + break; + + case SLAPD_FILTER_DN_SUBTREE: + Debug( LDAP_DEBUG_FILTER, "\tDN SUBTREE\n", 0, 0, 0 ); + rc = bdb_dn2idl( be, f->f_dn, DN_SUBTREE_PREFIX, ids ); + break; + + case LDAP_FILTER_PRESENT: + Debug( LDAP_DEBUG_FILTER, "\tPRESENT\n", 0, 0, 0 ); + rc = presence_candidates( be, range, f->f_desc, ids ); + break; + +#if 0 + case LDAP_FILTER_EQUALITY: + Debug( LDAP_DEBUG_FILTER, "\tEQUALITY\n", 0, 0, 0 ); + rc = equality_candidates( be, range, f->f_ava, ids ); + break; + + case LDAP_FILTER_APPROX: + Debug( LDAP_DEBUG_FILTER, "\tAPPROX\n", 0, 0, 0 ); + rc = approx_candidates( be, range, f->f_ava, ids ); + break; + + case LDAP_FILTER_SUBSTRINGS: + Debug( LDAP_DEBUG_FILTER, "\tSUBSTRINGS\n", 0, 0, 0 ); + rc = substring_candidates( be, range, f->f_sub, ids ); + break; +#endif + + case LDAP_FILTER_GE: + Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 ); + rc = 0; + break; + + case LDAP_FILTER_LE: + Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 ); + rc = 0; + break; + + case LDAP_FILTER_NOT: { + ID tmp[BDB_IDL_SIZE]; + + Debug( LDAP_DEBUG_FILTER, "\tNOT\n", 0, 0, 0 ); + rc = bdb_filter_candidates( be, range, f->f_not, tmp ); + if( rc == 0 ) { + rc = bdb_idl_notin( range, tmp, ids ); + } + } break; + + case LDAP_FILTER_AND: + Debug( LDAP_DEBUG_FILTER, "\tAND\n", 0, 0, 0 ); + rc = list_candidates( be, range, + f->f_and, LDAP_FILTER_AND, ids ); + break; + + case LDAP_FILTER_OR: + Debug( LDAP_DEBUG_FILTER, "\tOR\n", 0, 0, 0 ); + rc = list_candidates( be, range, + f->f_or, LDAP_FILTER_OR, ids ); + break; + + default: + Debug( LDAP_DEBUG_FILTER, "\tUNKNOWN %d\n", + f->f_choice, 0, 0 ); + } + + if( rc ) { + BDB_IDL_CPY( ids, range ); + } + + Debug( LDAP_DEBUG_FILTER, + "<= bdb_filter_candidates: id=%ld first=%ld last=%ld\n", + ids[0], ids[1], + BDB_IDL_IS_RANGE( ids ) ? ids[2] : ids[ids[0]] ); + + return 0; +} + +static int +list_candidates( + Backend *be, + ID *range, + Filter *flist, + int ftype, + ID *ids ) +{ + int rc = 0; + Filter *f; + + Debug( LDAP_DEBUG_FILTER, "=> bdb_list_candidates 0x%x\n", ftype, 0, 0 ); + + if( ftype == LDAP_FILTER_AND ) { + BDB_IDL_CPY( ids, range ); + } else { + BDB_IDL_ZERO( ids ); + } + + for ( f = flist; f != NULL; f = f->f_next ) { + ID tmp[BDB_IDL_SIZE]; + ID result[BDB_IDL_SIZE]; + rc = bdb_filter_candidates( be, range, f, tmp ); + + if ( rc != 0 ) { + /* Error: treat as undefined */ + if( ftype == LDAP_FILTER_AND ) { + continue; + } + BDB_IDL_CPY( ids, range ); + break; + } + + + if ( ftype == LDAP_FILTER_AND ) { + bdb_idl_intersection( tmp, ids, result ); + if( BDB_IDL_IS_ZERO( result ) ) { + BDB_IDL_ZERO( ids ); + break; + } + } else { + bdb_idl_union( tmp, ids, result ); + if( BDB_IDL_IS_ALL( range, result ) ) { + BDB_IDL_CPY( ids, range ); + break; + } + } + + BDB_IDL_CPY( ids, result ); + } + + Debug( LDAP_DEBUG_FILTER, + "<= bdb_list_candidates: id=%ld first=%ld last=%ld\n", + ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) ); + return 0; +} + +static int +presence_candidates( + Backend *be, + ID *range, + AttributeDescription *desc, + ID *ids ) +{ + DB *db; + int rc; + slap_mask_t mask; + struct berval *prefix; + + Debug( LDAP_DEBUG_TRACE, "=> bdb_presence_candidates\n", 0, 0, 0 ); + BDB_IDL_ZERO( ids ); + + rc = bdb_index_param( be, desc, LDAP_FILTER_PRESENT, + &db, &mask, &prefix ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_presence_candidates: index_param returned=%d\n", + rc, 0, 0 ); + return rc; + } + + if( db == NULL ) { + /* not indexed */ + Debug( LDAP_DEBUG_TRACE, + "<= bdb_presense_candidates: not indexed\n", + 0, 0, 0 ); + rc = -1; + goto done; + } + + if( prefix == NULL ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_presense_candidates: no prefix\n", + 0, 0, 0 ); + rc = -1; + goto done; + } + + rc = bdb_key_read( be, db, prefix, ids ); + + if( rc == DB_NOTFOUND ) { + rc = 0; + + } else if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_presense_candidates: key read failed (%d)\n", + rc, 0, 0 ); + goto done; + } + + Debug(LDAP_DEBUG_TRACE, + "<= bdb_presence_candidates: id=%ld first=%ld last=%ld\n", + ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) ); + +done: + ber_bvfree( prefix ); + return rc; +} + +static int +equality_candidates( + Backend *be, + ID *range, + AttributeAssertion *ava, + ID *ids ) +{ + DB *db; + int i; + int rc; + char *dbname; + slap_mask_t mask; + struct berval *prefix; + struct berval **keys = NULL; + MatchingRule *mr; + + Debug( LDAP_DEBUG_TRACE, "=> bdb_equality_candidates\n", 0, 0, 0 ); + + BDB_IDL_RANGE_CPY( range, ids ); + + rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_EQUALITY, + &db, &mask, &prefix ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_ANY, + "<= equality_candidates: index_param failed (%d)\n", + rc, 0, 0 ); + return 0; + } + + mr = ava->aa_desc->ad_type->sat_equality; + if( !mr ) { + ber_bvfree( prefix ); + return 0; + } + + if( !mr->smr_filter ) { + ber_bvfree( prefix ); + return 0; + } + + rc = (mr->smr_filter)( + LDAP_FILTER_EQUALITY, + mask, + ava->aa_desc->ad_type->sat_syntax, + mr, + prefix, + ava->aa_value, + &keys ); + + ber_bvfree( prefix ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_equality_candidates: (%s%s) MR filter failed (%d)\n", + "", "", rc ); + return 0; + } + + if( keys == NULL ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_equality_candidates: no keys (%s%s)\n", + "", "", 0 ); + return 0; + } + + for ( i= 0; keys[i] != NULL; i++ ) { + ID save[BDB_IDL_SIZE]; + ID tmp[BDB_IDL_SIZE]; + + rc = bdb_key_read( be, db, keys[i], tmp ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_equality_candidates key read failed (%d)\n", + rc, 0, 0 ); + break; + } + + if( tmp == NULL ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_equality_candidates NULL\n", + 0, 0, 0 ); + break; + } + + save = idl; + idl = idl_intersection( be, idl, tmp ); + idl_free( save ); + idl_free( tmp ); + + if( idl == NULL ) break; + } + + ber_bvecfree( keys ); + + Debug( LDAP_DEBUG_TRACE, + "<= bdb_equality_candidates %ld\n", + ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) ); + return( idl ); +} + + +static int +approx_candidates( + Backend *be, + ID *range, + AttributeAssertion *ava, + ID *ids ) +{ + ID_BLOCK *idl; + DBCache *db; + int i; + int rc; + char *dbname; + slap_mask_t mask; + struct berval *prefix; + struct berval **keys = NULL; + MatchingRule *mr; + + Debug( LDAP_DEBUG_TRACE, "=> approx_candidates\n", 0, 0, 0 ); + + rc = bdb_index_param( be, ava->aa_desc, LDAP_FILTER_APPROX, + &db, &mask, &prefix ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_ANY, + "<= approx_candidates: index_param failed (%d)\n", + rc, 0, 0 ); + return idl; + } + + mr = ava->aa_desc->ad_type->sat_approx; + if( !mr ) { + /* no approx matching rule, try equality matching rule */ + mr = ava->aa_desc->ad_type->sat_equality; + } + + if( !mr ) { + ber_bvfree( prefix ); + return idl; + } + + if( !mr->smr_filter ) { + ber_bvfree( prefix ); + return idl; + } + + rc = (mr->smr_filter)( + LDAP_FILTER_APPROX, + mask, + ava->aa_desc->ad_type->sat_syntax, + mr, + prefix, + ava->aa_value, + &keys ); + + ber_bvfree( prefix ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_TRACE, + "<= approx_candidates: (%s%s) MR filter failed (%d)\n", + dbname, LDBM_SUFFIX, rc ); + return idl; + } + + if( keys == NULL ) { + Debug( LDAP_DEBUG_TRACE, + "<= approx_candidates: no keys (%s%s)\n", + dbname, LDBM_SUFFIX, 0 ); + return idl; + } + + if ( db == NULL ) { + Debug( LDAP_DEBUG_ANY, + "<= approx_candidates db open failed (%s%s)\n", + dbname, LDBM_SUFFIX, 0 ); + return idl; + } + + for ( i= 0; keys[i] != NULL; i++ ) { + ID_BLOCK *save; + ID_BLOCK *tmp; + + rc = key_read( be, db, keys[i], &tmp ); + + if( rc != LDAP_SUCCESS ) { + idl_free( idl ); + idl = NULL; + Debug( LDAP_DEBUG_TRACE, "<= approx_candidates key read failed (%d)\n", + rc, 0, 0 ); + break; + } + + if( tmp == NULL ) { + idl_free( idl ); + idl = NULL; + Debug( LDAP_DEBUG_TRACE, "<= approx_candidates NULL\n", + 0, 0, 0 ); + break; + } + + save = idl; + idl = idl_intersection( be, idl, tmp ); + idl_free( save ); + + if( idl == NULL ) break; + } + + ber_bvecfree( keys ); + + Debug( LDAP_DEBUG_TRACE, "<= approx_candidates %ld\n", + ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) ); + + return( idl ); +} + +static int +substring_candidates( + Backend *be, + ID *range, + SubstringsAssertion *sub, + ID *ids ) +{ + ID_BLOCK *idl; + DBCache *db; + int i; + int rc; + slap_mask_t mask; + struct berval *prefix; + struct berval **keys = NULL; + MatchingRule *mr; + + Debug( LDAP_DEBUG_TRACE, "=> substrings_candidates\n", 0, 0, 0 ); + + idl = idl_allids( be ); + + rc = bdb_index_param( be, sub->sa_desc, LDAP_FILTER_SUBSTRINGS, + &db, &mask, &prefix ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_ANY, + "<= substrings_candidates: index_param failed (%d)\n", + rc, 0, 0 ); + return idl; + } + + if( dbname == NULL ) { + /* not indexed */ + Debug( LDAP_DEBUG_ANY, + "<= substrings_candidates: not indexed\n", + 0, 0, 0 ); + ber_bvfree( prefix ); + return idl; + } + + mr = sub->sa_desc->ad_type->sat_substr; + + if( !mr ) { + ber_bvfree( prefix ); + return idl; + } + + if( !mr->smr_filter ) { + ber_bvfree( prefix ); + return idl; + } + + rc = (mr->smr_filter)( + LDAP_FILTER_SUBSTRINGS, + mask, + sub->sa_desc->ad_type->sat_syntax, + mr, + prefix, + sub, + &keys ); + + ber_bvfree( prefix ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_TRACE, + "<= substrings_candidates: (%s%s) MR filter failed (%d)\n", + dbname, LDBM_SUFFIX, rc ); + return idl; + } + + if( keys == NULL ) { + Debug( LDAP_DEBUG_TRACE, + "<= substrings_candidates: (0x%04lx) no keys (%s%s)\n", + mask, dbname, LDBM_SUFFIX ); + return idl; + } + + db = ldbm_cache_open( be, dbname, LDBM_SUFFIX, LDBM_READER ); + + if ( db == NULL ) { + Debug( LDAP_DEBUG_ANY, + "<= substrings_candidates db open failed (%s%s)\n", + dbname, LDBM_SUFFIX, 0 ); + return idl; + } + + for ( i= 0; keys[i] != NULL; i++ ) { + ID_BLOCK *save; + ID_BLOCK *tmp; + + rc = key_read( be, db, keys[i], &tmp ); + + if( rc != LDAP_SUCCESS ) { + idl_free( idl ); + idl = NULL; + Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates key read failed (%d)\n", + rc, 0, 0 ); + break; + } + + if( tmp == NULL ) { + idl_free( idl ); + idl = NULL; + Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates NULL\n", + 0, 0, 0 ); + break; + } + + save = idl; + idl = idl_intersection( be, idl, tmp ); + idl_free( save ); + + if( idl == NULL ) break; + } + + ber_bvecfree( keys ); + + Debug( LDAP_DEBUG_TRACE, "<= substrings_candidates %ld\n", + ids[0], BDB_IDL_FIRST(ids), BDB_IDL_LAST(ids) ); + + return( idl ); +} + +#endif \ No newline at end of file diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c index 1531f14d65..45505e5928 100644 --- a/servers/slapd/back-bdb/idl.c +++ b/servers/slapd/back-bdb/idl.c @@ -11,6 +11,10 @@ #include #include "back-bdb.h" +#include "idl.h" + +#define IDL_MAX(x,y) ( x > y ? x : y ) +#define IDL_MIN(x,y) ( x < y ? x : y ) #define IDL_CMP(x,y) ( x < y ? -1 : ( x > y ? 1 : 0 ) ) @@ -340,3 +344,224 @@ bdb_idl_delete_key( return rc; } + + +/* + * idl_intersection - return a intersection b + */ +int +bdb_idl_intersection( + ID *a, + ID *b, + ID *ids ) +{ + ID ida, idb; + ID cursora, cursorb; + + if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) { + ids[0] = 0; + return 0; + } + + if ( BDB_IDL_IS_RANGE( a ) && BDB_IDL_IS_RANGE(b) ) { + ids[0] = NOID; + ids[1] = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) ); + ids[2] = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_FIRST(b) ); + + if ( ids[1] == ids[2] ) { + ids[0] = 1; + } else if( ids[1] > ids[2] ) { + ids[0] = 0; + } + return 0; + } + + if( BDB_IDL_IS_RANGE( a ) ) { + ID *tmp = a; + a = b; + b = tmp; + } + + ida = bdb_idl_first( a, &cursora ), + idb = bdb_idl_first( b, &cursorb ); + + ids[0] = 0; + + while( ida != NOID && idb != NOID ) { + if( ida == idb ) { + ids[++ids[0]] = ida; + ida = bdb_idl_next( a, &cursora ); + idb = bdb_idl_next( b, &cursorb ); + if( BDB_IDL_IS_RANGE( b ) && idb < ida ) { + if( ida > BDB_IDL_LAST( b ) ) { + idb = NOID; + } else { + idb = ida; + cursorb = ida; + } + } + } else if ( ida < idb ) { + ida = bdb_idl_next( a, &cursora ); + } else { + idb = bdb_idl_next( b, &cursorb ); + } + } + + return 0; +} + + +/* + * idl_union - return a union b + */ +int +bdb_idl_union( + ID *a, + ID *b, + ID *ids ) +{ + ID ida, idb; + ID cursora, cursorb; + + if ( BDB_IDL_IS_ZERO( a ) ) { + BDB_IDL_CPY( ids, b ); + return 0; + } + + if ( BDB_IDL_IS_ZERO( b ) ) { + BDB_IDL_CPY( ids, a ); + return 0; + } + + if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) { + ids[0] = NOID; + ids[1] = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) ); + ids[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_FIRST(b) ); + return 0; + } + + ida = bdb_idl_first( a, &cursora ), + idb = bdb_idl_first( b, &cursorb ); + + ids[0] = 0; + + while( ida != NOID && idb != NOID ) { + if( ++ids[0] > BDB_IDL_MAX ) { + ids[0] = NOID; + ids[2] = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) ); + break; + } + + if ( ida < idb ) { + ids[ids[0]] = ida; + ida = bdb_idl_next( a, &cursora ); + + } else if ( ida > idb ) { + ids[ids[0]] = idb; + idb = bdb_idl_next( b, &cursorb ); + + } else { + ids[ids[0]] = ida; + ida = bdb_idl_next( a, &cursora ); + idb = bdb_idl_next( b, &cursorb ); + } + } + + return 0; +} + + +/* + * bdb_idl_notin - return a intersection ~b (or a minus b) + */ +int +bdb_idl_notin( + ID *a, + ID *b, + ID *ids ) +{ + ID ida, idb; + ID cursora, cursorb; + + if( BDB_IDL_IS_ZERO( a ) || + BDB_IDL_IS_ZERO( b ) || + BDB_IDL_IS_RANGE( b ) ) + { + BDB_IDL_CPY( ids, a ); + return 0; + } + + if( BDB_IDL_IS_RANGE( a ) ) { + BDB_IDL_CPY( ids, a ); + return 0; + } + + ida = bdb_idl_first( a, &cursora ), + idb = bdb_idl_first( b, &cursorb ); + + ids[0] = 0; + + while( ida != NOID ) { + if ( idb == NOID ) { + /* we could shortcut this */ + ids[++ids[0]] = ida; + ida = bdb_idl_next( a, &cursora ); + + } else if ( ida < idb ) { + ids[++ids[0]] = ida; + ida = bdb_idl_next( a, &cursora ); + + } else if ( ida > idb ) { + idb = bdb_idl_next( b, &cursorb ); + + } else { + ida = bdb_idl_next( a, &cursora ); + idb = bdb_idl_next( b, &cursorb ); + } + } + + return 0; +} + +ID bdb_idl_first( ID *ids, ID *cursor ) +{ + ID pos; + + if ( ids[0] == 0 ) { + *cursor = NOID; + return NOID; + } + + if ( BDB_IDL_IS_RANGE( ids ) ) { + if( *cursor < ids[1] ) { + *cursor = ids[1]; + } + return *cursor; + } + + pos = bdb_idl_search( ids, *cursor ); + + if( pos > ids[0] ) { + return NOID; + } + + *cursor = pos; + return ids[pos]; +} + +ID bdb_idl_next( ID *ids, ID *cursor ) +{ + if ( BDB_IDL_IS_RANGE( ids ) ) { + if( ids[2] < ++(*cursor) ) { + return NOID; + } + return *cursor; + } + + if ( *cursor < ids[0] ) { + return ids[(*cursor)++]; + } + + return NOID; +} + diff --git a/servers/slapd/back-bdb/idl.h b/servers/slapd/back-bdb/idl.h new file mode 100644 index 0000000000..3ce8e19ed1 --- /dev/null +++ b/servers/slapd/back-bdb/idl.h @@ -0,0 +1,57 @@ +/* back-bdb.h - ldap ldbm back-end header file */ +/* $OpenLDAP$ */ +/* + * Copyright 2000 The OpenLDAP Foundation, All Rights Reserved. + * COPYING RESTRICTIONS APPLY, see COPYRIGHT file + */ + +#ifndef _BDB_IDL_H_ +#define _BDB_IDL_H_ + +#include + +#include "slap.h" + +#define BDB_IDL_DB_SIZE (1<<16) /* 64K IDL on disk */ +#define BDB_IDL_DB_MAX (BDB_IDL_DB_SIZE-32) +/* #define BDB_IDL_DB_ALLOC (BDB_IDL_DB_SIZE * sizeof(ID)) */ + +#define BDB_IDL_SIZE (1<<17) /* 128K IDL in memory */ +#define BDB_IDL_MAX (BDB_IDL_DB_SIZE-32) +/* #define BDB_IDL_DB_ALLOC (BDB_IDL_DB_SIZE * sizeof(ID)) */ + +#define BDB_IDL_IS_RANGE(ids) ((ids)[0] == NOID) +#define BDB_IDL_RANGE_SIZE (3 * sizeof(ID)) +#define BDB_IDL_SIZEOF(ids) ( BDB_IDL_IS_RANGE(ids) \ + ? BDB_IDL_RANGE_SIZE : ((ids)[0]+1) * sizeof(ID) ) + +#define BDB_IDL_RANGE( ids, f, l ) \ + do { \ + (ids)[0] = NOID; \ + (ids)[1] = (f); \ + (ids)[2] = (l); \ + } while(0) + +#define BDB_IDL_ZERO(ids) \ + do { \ + (ids)[0] = 0; \ + (ids)[1] = 0; \ + (ids)[2] = 0; \ + } while(0); + +#define BDB_IDL_IS_ZERO(ids) ( (ids)[0] == 0 ) +#define BDB_IDL_IS_ALL( range, ids ) ( (ids)[0] == NOID \ + && (ids)[1] <= (range)[1] && (range)[2] <= (ids)[2] ) + +#define BDB_IDL_CPY( dst, src ) (memcpy( dst, src, BDB_IDL_SIZEOF( src ) )) + +#define BDB_IDL_ID( bdb, ids, id ) BDB_IDL_RANGE( ids, id, ((bdb)->bi_lastid) ) +#define BDB_IDL_ALL( bdb, ids ) BDB_IDL_RANGE( ids, 1, ((bdb)->bi_lastid) ) + +#define BDB_IDL_FIRST( ids ) ( ids[1] ) +#define BDB_IDL_LAST( ids ) ( BDB_IDL_IS_RANGE(ids) ? ids[2] : ids[ids[0]] ) + +LDAP_BEGIN_DECL +LDAP_END_DECL + +#endif \ No newline at end of file diff --git a/servers/slapd/back-bdb/modify.c b/servers/slapd/back-bdb/modify.c index dd41037ca0..03c0c29b0b 100644 --- a/servers/slapd/back-bdb/modify.c +++ b/servers/slapd/back-bdb/modify.c @@ -25,7 +25,9 @@ int bdb_modify_internal( DB_TXN *tid, Modifications *modlist, Entry *e, - const char **text ) + const char **text, + char *textbuf, + size_t textlen ) { int rc, err; Modification *mod; @@ -116,7 +118,7 @@ int bdb_modify_internal( } /* check that the entry still obeys the schema */ - rc = entry_schema_check( e, save_attrs, text ); + rc = entry_schema_check( e, save_attrs, text, textbuf, textlen ); if ( rc != LDAP_SUCCESS ) { attrs_free( e->e_attrs ); e->e_attrs = save_attrs; @@ -154,6 +156,8 @@ bdb_modify( Entry *e; int manageDSAit = get_manageDSAit( op ); const char *text = NULL; + char textbuf[SLAP_TEXT_BUFLEN]; + size_t textlen = sizeof textbuf; DB_TXN *ltid; struct bdb_op_info opinfo; @@ -256,7 +260,8 @@ retry: /* transaction retry */ } /* Modify the entry */ - rc = bdb_modify_internal( be, conn, op, ltid, modlist, e, &text ); + rc = bdb_modify_internal( be, conn, op, ltid, modlist, e, + &text, textbuf, textlen ); if( rc != LDAP_SUCCESS ) { Debug( LDAP_DEBUG_TRACE, diff --git a/servers/slapd/back-bdb/modrdn.c b/servers/slapd/back-bdb/modrdn.c index c1cc3a42d1..54d6cd0e05 100644 --- a/servers/slapd/back-bdb/modrdn.c +++ b/servers/slapd/back-bdb/modrdn.c @@ -33,6 +33,8 @@ bdb_modrdn( Entry *matched; int rc; const char *text; + char textbuf[SLAP_TEXT_BUFLEN]; + size_t textlen = sizeof textbuf; DB_TXN * ltid; struct bdb_op_info opinfo; @@ -472,7 +474,8 @@ retry: /* transaction retry */ } /* modify entry */ - rc = bdb_modify_internal( be, conn, op, ltid, &mod[0], e, &text ); + rc = bdb_modify_internal( be, conn, op, ltid, &mod[0], e, + &text, textbuf, textlen ); if( rc != LDAP_SUCCESS ) { switch( rc ) { diff --git a/servers/slapd/back-bdb/nextid.c b/servers/slapd/back-bdb/nextid.c index d3278f3e62..a534840ae3 100644 --- a/servers/slapd/back-bdb/nextid.c +++ b/servers/slapd/back-bdb/nextid.c @@ -100,6 +100,9 @@ retry: if( tid != NULL ) { case 0: *out = id; + + bdb->bi_lastid = id; + rc = txn_commit( ltid, 0 ); if( rc != 0 ) { diff --git a/servers/slapd/back-bdb/passwd.c b/servers/slapd/back-bdb/passwd.c index 76613bbb7d..3642eacfc5 100644 --- a/servers/slapd/back-bdb/passwd.c +++ b/servers/slapd/back-bdb/passwd.c @@ -32,6 +32,8 @@ bdb_exop_passwd( struct berval *hash = NULL; DB_TXN *ltid = NULL; struct bdb_op_info opinfo; + char textbuf[SLAP_TEXT_BUFLEN]; + size_t textlen = sizeof textbuf; struct berval *id = NULL; struct berval *new = NULL; @@ -162,11 +164,12 @@ retry: /* transaction retry */ ml.sml_next = NULL; rc = bdb_modify_internal( be, conn, op, ltid, - &ml, e, text ); + &ml, e, text, textbuf, textlen ); switch(rc) { case DB_LOCK_DEADLOCK: case DB_LOCK_NOTGRANTED: + *text = NULL; bdb_entry_return( be, e ); e = NULL; goto retry; diff --git a/servers/slapd/back-bdb/proto-bdb.h b/servers/slapd/back-bdb/proto-bdb.h index 04cab9d048..1c473150a9 100644 --- a/servers/slapd/back-bdb/proto-bdb.h +++ b/servers/slapd/back-bdb/proto-bdb.h @@ -64,6 +64,13 @@ int bdb_dn2id_children( DB_TXN *tid, const char *dn ); +int +bdb_dn2idl( + BackendDB *be, + const char *dn, + int prefix, + ID *ids ); + /* * entry.c */ @@ -74,6 +81,15 @@ int bdb_entry_return( BackendDB *be, Entry *e ); */ void bdb_errcall( const char *pfx, char * msg ); +/* + * filterentry.c + */ +int bdb_filter_candidates( + Backend *be, + ID *range, + Filter *f, + ID *ids ); + /* * id2entry */ @@ -117,6 +133,50 @@ int bdb_idl_delete_key( DBT *key, ID id ); +int +bdb_idl_notin( + ID *a, + ID *b, + ID *ids ); + +int +bdb_idl_intersection( + ID *a, + ID *b, + ID *ids ); + +int +bdb_idl_union( + ID *a, + ID *b, + ID *ids ); + +ID bdb_idl_first( ID *ids, ID *cursor ); +ID bdb_idl_next( ID *ids, ID *cursor ); + + +/* + * index.c + */ +extern int +bdb_index_param( + Backend *be, + AttributeDescription *desc, + int ftype, + DB **db, + slap_mask_t *mask, + struct berval **prefix ); + +/* + * key.c + */ +extern int +bdb_key_read( + Backend *be, + DB *db, + struct berval *k, + ID *ids ); + /* * nextid.c */ @@ -132,7 +192,9 @@ int bdb_modify_internal( DB_TXN *tid, Modifications *modlist, Entry *e, - const char **text ); + const char **text, + char *textbuf, + size_t textlen ); /* * passwd.c diff --git a/servers/slapd/back-bdb/search.c b/servers/slapd/back-bdb/search.c index 629ab39d3e..20e44d0ebd 100644 --- a/servers/slapd/back-bdb/search.c +++ b/servers/slapd/back-bdb/search.c @@ -11,6 +11,7 @@ #include #include "back-bdb.h" +#include "idl.h" #include "external.h" static int base_candidate( @@ -26,9 +27,6 @@ static int search_candidates( int manageDSAit, ID *ids ); -static ID idl_first( ID *ids, ID *cursor ); -static ID idl_next( ID *ids, ID *cursor ); - int bdb_search( BackendDB *be, @@ -178,9 +176,9 @@ bdb_search( goto done; } - for ( id = idl_first( candidates, &cursor ); + for ( id = bdb_idl_first( candidates, &cursor ); id != NOID; - id = idl_next( candidates, &cursor ) ) + id = bdb_idl_next( candidates, &cursor ) ) { int scopeok = 0; @@ -386,8 +384,13 @@ static int search_candidates( ID *ids ) { int rc; - Filter f, fand, rf, af, xf; - AttributeAssertion aa_ref, aa_alias; + Filter f, fand, rf, xf; + AttributeAssertion aa_ref; + struct bdb_info *bdb = (struct bdb_info *) be->be_private; +#ifdef BDB_ALIASES + Filter af; + AttributeAssertion aa_alias; +#endif Debug(LDAP_DEBUG_TRACE, "search_candidates: base=\"%s\" (0x%08lx) scope=%d\n", @@ -430,13 +433,15 @@ static int search_candidates( fand.f_dn = e->e_ndn; fand.f_next = xf.f_or == filter ? filter : &xf ; -#if 0 - rc = bdb_filter_candidates( be, &f, ids ); + +#ifdef BDB_FILTER_INDICES + { + ID range[3]; + BDB_IDL_ID( bdb, range, e->e_id ); + rc = bdb_filter_candidates( be, range, &f, ids ); + } #else - /* a quick hack */ - ids[0] = NOID; - ids[1] = e->e_id; - ids[2] = e->e_id+128; + BDB_IDL_ID( bdb, ids, e->e_id ); rc = 0; #endif @@ -447,46 +452,3 @@ static int search_candidates( return rc; } - -static ID idl_first( ID *ids, ID *cursor ) -{ - ID pos; - - if ( ids[0] == 0 ) { - *cursor = NOID; - return NOID; - } - - if ( BDB_IDL_IS_RANGE( ids ) ) { - if( *cursor < ids[1] ) { - *cursor = ids[1]; - } - return *cursor; - } - - pos = bdb_idl_search( ids, *cursor ); - - if( pos > ids[0] ) { - return NOID; - } - - *cursor = pos; - return ids[pos]; -} - -static ID idl_next( ID *ids, ID *cursor ) -{ - if ( BDB_IDL_IS_RANGE( ids ) ) { - if( ids[2] < ++(*cursor) ) { - return NOID; - } - return *cursor; - } - - if ( *cursor < ids[0] ) { - return ids[(*cursor)++]; - } - - return NOID; -} - -- 2.39.5