From 62b6b326338d5162b0f570eaeb8a227fbc5a9c62 Mon Sep 17 00:00:00 2001 From: Howard Chu Date: Tue, 28 Sep 2004 13:11:11 +0000 Subject: [PATCH] Add SLAP_MR_ORDERED_INDEX - support for inequality indexing. Currently only implemented for generalizedTime syntax. --- servers/slapd/back-bdb/dn2id.c | 2 +- servers/slapd/back-bdb/filterindex.c | 141 +++++++++++++++++++++++++-- servers/slapd/back-bdb/idl.c | 62 ++++++++++-- servers/slapd/back-bdb/key.c | 6 +- servers/slapd/back-bdb/proto-bdb.h | 16 +-- servers/slapd/schema_init.c | 114 +++++++++++++++++++++- servers/slapd/slap.h | 3 +- 7 files changed, 317 insertions(+), 27 deletions(-) diff --git a/servers/slapd/back-bdb/dn2id.c b/servers/slapd/back-bdb/dn2id.c index 3747945185..4509062ab1 100644 --- a/servers/slapd/back-bdb/dn2id.c +++ b/servers/slapd/back-bdb/dn2id.c @@ -357,7 +357,7 @@ bdb_dn2idl( ((char *)key.data)[0] = prefix; AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 ); - rc = bdb_idl_fetch_key( op->o_bd, db, NULL, &key, ids ); + rc = bdb_idl_fetch_key( op->o_bd, db, NULL, &key, ids, NULL, 0 ); if( rc != 0 ) { Debug( LDAP_DEBUG_TRACE, diff --git a/servers/slapd/back-bdb/filterindex.c b/servers/slapd/back-bdb/filterindex.c index ff04cd3e2a..573f5890a2 100644 --- a/servers/slapd/back-bdb/filterindex.c +++ b/servers/slapd/back-bdb/filterindex.c @@ -32,6 +32,12 @@ static int equality_candidates( AttributeAssertion *ava, ID *ids, ID *tmp ); +static int inequality_candidates( + Operation *op, + AttributeAssertion *ava, + ID *ids, + ID *tmp, + int gtorlt ); static int approx_candidates( Operation *op, AttributeAssertion *ava, @@ -127,15 +133,23 @@ bdb_filter_candidates( break; case LDAP_FILTER_GE: - /* no GE index, use pres */ + /* if no GE index, use pres */ Debug( LDAP_DEBUG_FILTER, "\tGE\n", 0, 0, 0 ); - rc = presence_candidates( op, f->f_ava->aa_desc, ids ); + if( f->f_ava->aa_desc->ad_type->sat_ordering && + ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage && SLAP_MR_ORDERED_INDEX ) ) + rc = inequality_candidates( op, f->f_ava, ids, tmp, LDAP_FILTER_GE ); + else + rc = presence_candidates( op, f->f_ava->aa_desc, ids ); break; case LDAP_FILTER_LE: - /* no LE index, use pres */ + /* if no LE index, use pres */ Debug( LDAP_DEBUG_FILTER, "\tLE\n", 0, 0, 0 ); - rc = presence_candidates( op, f->f_ava->aa_desc, ids ); + if( f->f_ava->aa_desc->ad_type->sat_ordering && + ( f->f_ava->aa_desc->ad_type->sat_ordering->smr_usage && SLAP_MR_ORDERED_INDEX ) ) + rc = inequality_candidates( op, f->f_ava, ids, tmp, LDAP_FILTER_LE ); + else + rc = presence_candidates( op, f->f_ava->aa_desc, ids ); break; case LDAP_FILTER_NOT: @@ -289,7 +303,7 @@ presence_candidates( return -1; } - rc = bdb_key_read( op->o_bd, db, NULL, &prefix, ids ); + rc = bdb_key_read( op->o_bd, db, NULL, &prefix, ids, NULL, 0 ); if( rc == DB_NOTFOUND ) { BDB_IDL_ZERO( ids ); @@ -385,7 +399,7 @@ equality_candidates( } for ( i= 0; keys[i].bv_val != NULL; i++ ) { - rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp ); + rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 ); if( rc == DB_NOTFOUND ) { BDB_IDL_ZERO( ids ); @@ -506,7 +520,7 @@ approx_candidates( } for ( i= 0; keys[i].bv_val != NULL; i++ ) { - rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp ); + rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 ); if( rc == DB_NOTFOUND ) { BDB_IDL_ZERO( ids ); @@ -621,7 +635,7 @@ substring_candidates( } for ( i= 0; keys[i].bv_val != NULL; i++ ) { - rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp ); + rc = bdb_key_read( op->o_bd, db, NULL, &keys[i], tmp, NULL, 0 ); if( rc == DB_NOTFOUND ) { BDB_IDL_ZERO( ids ); @@ -662,3 +676,114 @@ substring_candidates( return( rc ); } +static int +inequality_candidates( + Operation *op, + AttributeAssertion *ava, + ID *ids, + ID *tmp, + int gtorlt ) +{ + struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; + DB *db; + int i; + int rc; + slap_mask_t mask; + struct berval prefix = {0, NULL}; + struct berval *keys = NULL; + MatchingRule *mr; + DBC * cursor = NULL; + + Debug( LDAP_DEBUG_TRACE, "=> bdb_inequality_candidates (%s)\n", + ava->aa_desc->ad_cname.bv_val, 0, 0 ); + + BDB_IDL_ALL( bdb, ids ); + + rc = bdb_index_param( op->o_bd, ava->aa_desc, LDAP_FILTER_EQUALITY, + &db, &mask, &prefix ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_ANY, + "<= bdb_inequality_candidates: (%s) " + "index_param failed (%d)\n", + ava->aa_desc->ad_cname.bv_val, rc, 0 ); + return 0; + } + + if ( db == NULL ) { + Debug( LDAP_DEBUG_ANY, + "<= bdb_inequality_candidates: (%s) not indexed\n", + ava->aa_desc->ad_cname.bv_val, 0, 0 ); + return 0; + } + + mr = ava->aa_desc->ad_type->sat_equality; + if( !mr ) { + return 0; + } + + if( !mr->smr_filter ) { + return 0; + } + + rc = (mr->smr_filter)( + LDAP_FILTER_EQUALITY, + mask, + ava->aa_desc->ad_type->sat_syntax, + mr, + &prefix, + &ava->aa_value, + &keys, op->o_tmpmemctx ); + + if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_inequality_candidates: (%s, %s) " + "MR filter failed (%d)\n", + prefix.bv_val, ava->aa_desc->ad_cname.bv_val, rc ); + return 0; + } + + if( keys == NULL ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_inequality_candidates: (%s) no keys\n", + ava->aa_desc->ad_cname.bv_val, 0, 0 ); + return 0; + } + + BDB_IDL_ZERO( ids ); + while(1) { + rc = bdb_key_read( op->o_bd, db, NULL, &keys[0], tmp, &cursor, gtorlt ); + + if( rc == DB_NOTFOUND ) { + rc = 0; + break; + } else if( rc != LDAP_SUCCESS ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_inequality_candidates: (%s) " + "key read failed (%d)\n", + ava->aa_desc->ad_cname.bv_val, rc, 0 ); + break; + } + + if( BDB_IDL_IS_ZERO( tmp ) ) { + Debug( LDAP_DEBUG_TRACE, + "<= bdb_inequality_candidates: (%s) NULL\n", + ava->aa_desc->ad_cname.bv_val, 0, 0 ); + break; + } + + bdb_idl_union( ids, tmp ); + + if( BDB_IDL_IS_ZERO( ids ) ) + break; + i++; + } + ber_bvarray_free_x( keys, op->o_tmpmemctx ); + + Debug( LDAP_DEBUG_TRACE, + "<= bdb_inequality_candidates: id=%ld, first=%ld, last=%ld\n", + (long) ids[0], + (long) BDB_IDL_FIRST(ids), + (long) BDB_IDL_LAST(ids) ); + return( rc ); +} diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c index 71779baa40..b005d90d51 100644 --- a/servers/slapd/back-bdb/idl.c +++ b/servers/slapd/back-bdb/idl.c @@ -413,17 +413,20 @@ bdb_idl_fetch_key( DB *db, DB_TXN *tid, DBT *key, - ID *ids ) + ID *ids, + DBC **saved_cursor, + int get_flag ) { struct bdb_info *bdb = (struct bdb_info *) be->be_private; int rc; - DBT data; + DBT data, key2, *kptr; DBC *cursor; ID *i; void *ptr; size_t len; int rc2; int flags = bdb->bi_db_opflags | DB_MULTIPLE; + int opflag; /* If using BerkeleyDB 4.0, the buf must be large enough to * grab the entire IDL in one get(), otherwise BDB will leak @@ -450,7 +453,18 @@ bdb_idl_fetch_key( assert( ids != NULL ); - if ( bdb->bi_idl_cache_size ) { + if ( saved_cursor && *saved_cursor ) { + opflag = DB_NEXT; + } else if ( get_flag == LDAP_FILTER_GE ) { + opflag = DB_SET_RANGE; + } else if ( get_flag == LDAP_FILTER_LE ) { + opflag = DB_FIRST; + } else { + opflag = DB_SET; + } + + /* only non-range lookups can use the IDL cache */ + if ( bdb->bi_idl_cache_size && opflag == DB_SET ) { rc = bdb_idl_cache_get( bdb, db, key, ids ); if ( rc != LDAP_NO_SUCH_OBJECT ) return rc; } @@ -463,14 +477,44 @@ bdb_idl_fetch_key( if ( tid ) flags |= DB_RMW; - rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags ); + /* If we're not reusing an existing cursor, get a new one */ + if( opflag != DB_NEXT ) + rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags ); + else + cursor = *saved_cursor; if( rc != 0 ) { Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: " "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 ); return rc; } + + /* If this is a LE lookup, save original key so we can determine + * when to stop + */ + if ( get_flag == LDAP_FILTER_LE ) { + DBTzero( &key2 ); + key2.flags = DB_DBT_USERMEM; + key2.ulen = sizeof(keybuf); + key2.data = keybuf; + AC_MEMCPY( keybuf, key->data, key->size ); + kptr = &key2; + } else { + kptr = key; + } + len = key->size; + rc = cursor->c_get( cursor, kptr, &data, flags | opflag ); - rc = cursor->c_get( cursor, key, &data, flags | DB_SET ); + /* skip presence key on range inequality lookups */ + while (rc == 0 && kptr->size != len) { + rc = cursor->c_get( cursor, kptr, &data, flags | DB_NEXT_NODUP ); + } + /* If we're doing a LE compare and the new key is greater than + * our search key, we're done + */ + if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->data, + key->data, key->size ) > 0 ) { + rc = DB_NOTFOUND; + } if (rc == 0) { i = ids; while (rc == 0) { @@ -502,7 +546,13 @@ bdb_idl_fetch_key( data.size = BDB_IDL_SIZEOF(ids); } - rc2 = cursor->c_close( cursor ); + if ( saved_cursor && rc == 0 ) { + if ( !*saved_cursor ) + *saved_cursor = cursor; + rc2 = 0; + } + else + rc2 = cursor->c_close( cursor ); if (rc2) { Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: " "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 ); diff --git a/servers/slapd/back-bdb/key.c b/servers/slapd/back-bdb/key.c index c84028542d..563489bccf 100644 --- a/servers/slapd/back-bdb/key.c +++ b/servers/slapd/back-bdb/key.c @@ -32,7 +32,9 @@ bdb_key_read( DB *db, DB_TXN *txn, struct berval *k, - ID *ids + ID *ids, + DBC **saved_cursor, + int get_flag ) { int rc; @@ -45,7 +47,7 @@ bdb_key_read( key.ulen = key.size; key.flags = DB_DBT_USERMEM; - rc = bdb_idl_fetch_key( be, db, txn, &key, ids ); + rc = bdb_idl_fetch_key( be, db, txn, &key, ids, saved_cursor, get_flag ); if( rc != LDAP_SUCCESS ) { Debug( LDAP_DEBUG_TRACE, "<= bdb_index_read: failed (%d)\n", diff --git a/servers/slapd/back-bdb/proto-bdb.h b/servers/slapd/back-bdb/proto-bdb.h index ccdb1aa505..6d1c507d83 100644 --- a/servers/slapd/back-bdb/proto-bdb.h +++ b/servers/slapd/back-bdb/proto-bdb.h @@ -242,11 +242,13 @@ bdb_idl_cache_del( unsigned bdb_idl_search( ID *ids, ID id ); int bdb_idl_fetch_key( - BackendDB *be, - DB *db, - DB_TXN *txn, - DBT *key, - ID *ids ); + BackendDB *be, + DB *db, + DB_TXN *tid, + DBT *key, + ID *ids, + DBC **saved_cursor, + int get_flag ); int bdb_idl_insert( ID *ids, ID id ); @@ -343,7 +345,9 @@ bdb_key_read( DB *db, DB_TXN *txn, struct berval *k, - ID *ids ); + ID *ids, + DBC **saved_cursor, + int get_flags ); extern int bdb_key_change( diff --git a/servers/slapd/schema_init.c b/servers/slapd/schema_init.c index d107ddad84..7c85723617 100644 --- a/servers/slapd/schema_init.c +++ b/servers/slapd/schema_init.c @@ -40,6 +40,7 @@ #include #endif +#include "lutil.h" #include "lutil_hash.h" #define HASH_BYTES LUTIL_HASH_BYTES #define HASH_CONTEXT lutil_HASH_CTX @@ -2644,6 +2645,113 @@ generalizedTimeOrderingMatch( return LDAP_SUCCESS; } +/* Index generation function */ +int generalizedTimeIndexer( + slap_mask_t use, + slap_mask_t flags, + Syntax *syntax, + MatchingRule *mr, + struct berval *prefix, + BerVarray values, + BerVarray *keysp, + void *ctx ) +{ + int i, j; + size_t slen, mlen; + BerVarray keys; + char tmp[5]; + BerValue bvtmp; /* 40 bit index */ + struct lutil_tm tm; + struct lutil_timet tt; + + bvtmp.bv_len = sizeof(tmp); + bvtmp.bv_val = tmp; + for( i=0; values[i].bv_val != NULL; 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 ); + + /* GeneralizedTime YYYYmmddHH[MM[SS]][(./,)d...](Z|(+/-)HH[MM]) */ + for( i=0, j=0; values[i].bv_val != NULL; i++ ) { + assert(values[i].bv_val != NULL && values[i].bv_len >= 10); + /* Use 40 bits of time for key */ + if ( lutil_parsetime( values[i].bv_val, &tm ) == 0 ) { + lutil_tm2time( &tm, &tt ); + tmp[0] = tt.tt_gsec & 0xff; + tmp[4] = tt.tt_sec & 0xff; + tt.tt_sec >>= 8; + tmp[3] = tt.tt_sec & 0xff; + tt.tt_sec >>= 8; + tmp[2] = tt.tt_sec & 0xff; + tt.tt_sec >>= 8; + tmp[1] = tt.tt_sec & 0xff; + + ber_dupbv_x(&keys[j++], &bvtmp, ctx ); + } + } + + keys[j].bv_val = NULL; + keys[j].bv_len = 0; + + *keysp = keys; + + return LDAP_SUCCESS; +} + +/* Index generation function */ +int generalizedTimeFilter( + slap_mask_t use, + slap_mask_t flags, + Syntax *syntax, + MatchingRule *mr, + struct berval *prefix, + void * assertedValue, + BerVarray *keysp, + void *ctx ) +{ + BerVarray keys; + char tmp[5]; + BerValue bvtmp; /* 40 bit index */ + BerValue *value = (BerValue *) assertedValue; + struct lutil_tm tm; + struct lutil_timet tt; + + bvtmp.bv_len = sizeof(tmp); + bvtmp.bv_val = tmp; + keys = slap_sl_malloc( sizeof( struct berval ) * 2, ctx ); + + /* GeneralizedTime YYYYmmddHH[MM[SS]][(./,)d...](Z|(+/-)HH[MM]) */ + assert(value->bv_val != NULL && value->bv_len >= 10); + /* Use 40 bits of time for key */ + if ( lutil_parsetime( value->bv_val, &tm ) == 0 ) { + lutil_tm2time( &tm, &tt ); + tmp[0] = tt.tt_gsec & 0xff; + tmp[4] = tt.tt_sec & 0xff; + tt.tt_sec >>= 8; + tmp[3] = tt.tt_sec & 0xff; + tt.tt_sec >>= 8; + tmp[2] = tt.tt_sec & 0xff; + tt.tt_sec >>= 8; + tmp[1] = tt.tt_sec & 0xff; + + ber_dupbv_x(keys, &bvtmp, ctx ); + } else { + keys[0].bv_val = NULL; + keys[0].bv_len = 0; + } + + keys[1].bv_val = NULL; + keys[1].bv_len = 0; + + *keysp = keys; + + return LDAP_SUCCESS; +} + static int deliveryMethodValidate( Syntax *syntax, @@ -3375,14 +3483,14 @@ static slap_mrule_defs_rec mrule_defs[] = { {"( 2.5.13.27 NAME 'generalizedTimeMatch' " "SYNTAX 1.3.6.1.4.1.1466.115.121.1.24 )", - SLAP_MR_EQUALITY | SLAP_MR_EXT, NULL, + SLAP_MR_EQUALITY | SLAP_MR_EXT | SLAP_MR_ORDERED_INDEX, NULL, NULL, generalizedTimeNormalize, octetStringMatch, - NULL, NULL, + generalizedTimeIndexer, generalizedTimeFilter, NULL }, {"( 2.5.13.28 NAME 'generalizedTimeOrderingMatch' " "SYNTAX 1.3.6.1.4.1.1466.115.121.1.24 )", - SLAP_MR_ORDERING, NULL, + SLAP_MR_ORDERING | SLAP_MR_ORDERED_INDEX, NULL, NULL, generalizedTimeNormalize, generalizedTimeOrderingMatch, NULL, NULL, "generalizedTimeMatch" }, diff --git a/servers/slapd/slap.h b/servers/slapd/slap.h index 4d4bf0ed41..6b762c6bbc 100644 --- a/servers/slapd/slap.h +++ b/servers/slapd/slap.h @@ -476,8 +476,9 @@ typedef struct slap_matching_rule { #define SLAP_MR_ORDERING 0x0200U #define SLAP_MR_SUBSTR 0x0400U #define SLAP_MR_EXT 0x0800U /* implicitly extensible */ +#define SLAP_MR_ORDERED_INDEX 0x1000U #ifdef LDAP_COMP_MATCH -#define SLAP_MR_COMPONENT 0x1000U +#define SLAP_MR_COMPONENT 0x2000U #endif #define SLAP_MR_EQUALITY_APPROX ( SLAP_MR_EQUALITY | 0x0010U ) -- 2.39.5