From 61a15be30a64e79667f96c0998f5f507254fd751 Mon Sep 17 00:00:00 2001 From: Kurt Zeilenga Date: Mon, 25 Sep 2000 18:59:15 +0000 Subject: [PATCH] Rough in search routine --- servers/slapd/back-bdb/back-bdb.h | 10 +- servers/slapd/back-bdb/dn2entry.c | 1 + servers/slapd/back-bdb/id2entry.c | 2 + servers/slapd/back-bdb/idl.c | 20 +- servers/slapd/back-bdb/nextid.c | 2 +- servers/slapd/back-bdb/proto-bdb.h | 2 + servers/slapd/back-bdb/search.c | 394 +++++++++++++++++++++++++++++ 7 files changed, 417 insertions(+), 14 deletions(-) create mode 100644 servers/slapd/back-bdb/search.c diff --git a/servers/slapd/back-bdb/back-bdb.h b/servers/slapd/back-bdb/back-bdb.h index 5003574b93..e47b9e5310 100644 --- a/servers/slapd/back-bdb/back-bdb.h +++ b/servers/slapd/back-bdb/back-bdb.h @@ -15,9 +15,13 @@ LDAP_BEGIN_DECL -#define BDB_IDL_SIZE (1<<16) -#define BDB_IDL_MAX (BDB_IDL_SIZE-32) -/* #define BDB_IDL_ALLOC (BDB_IDL_SIZE * sizeof(ID)) */ +#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_IS_ALLIDS(ids) ((ids)[0] == NOID) diff --git a/servers/slapd/back-bdb/dn2entry.c b/servers/slapd/back-bdb/dn2entry.c index 77482ef3d4..7568035eeb 100644 --- a/servers/slapd/back-bdb/dn2entry.c +++ b/servers/slapd/back-bdb/dn2entry.c @@ -46,6 +46,7 @@ bdb_dn2entry( if( matchedDN == NULL ) { rc = bdb_id2entry( be, tid, id, e ); } else { + ch_free( matchedDN ); rc = bdb_id2entry( be, tid, id, matched ); } diff --git a/servers/slapd/back-bdb/id2entry.c b/servers/slapd/back-bdb/id2entry.c index 2725c4e557..04b27ea1b2 100644 --- a/servers/slapd/back-bdb/id2entry.c +++ b/servers/slapd/back-bdb/id2entry.c @@ -53,6 +53,8 @@ int bdb_id2entry( struct berval bv; int rc; + *e = NULL; + DBTzero( &key ); key.data = (char *) &id; key.size = sizeof(ID); diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c index c3f2148ce5..f8e0347073 100644 --- a/servers/slapd/back-bdb/idl.c +++ b/servers/slapd/back-bdb/idl.c @@ -14,7 +14,7 @@ #define IDL_CMP(x,y) ( x < y ? -1 : ( x > y ? 1 : 0 ) ) -static int idl_search( ID *ids, ID id ) +int bdb_idl_search( ID *ids, ID id ) { /* * binary search of id in ids @@ -22,7 +22,7 @@ static int idl_search( ID *ids, ID id ) * if not found, returns first postion greater than id */ int base = 0; - int cursor; + int cursor = 0; int val; int n = ids[0]; @@ -43,16 +43,16 @@ static int idl_search( ID *ids, ID id ) } } - if( val < 0 ) { - return cursor + 1; - } else { + if( val > 0 ) { return cursor + 2; + } else { + return cursor + 1; } } static int idl_insert( ID *ids, ID id ) { - int x = idl_search( ids, id ); + int x = bdb_idl_search( ids, id ); if( ids[x] == id ) { /* duplicate */ @@ -64,7 +64,7 @@ static int idl_insert( ID *ids, ID id ) ids[0]++; ids[ids[0]] = id; - } else if ( ++ids[0] >= BDB_IDL_MAX ) { + } else if ( ++ids[0] >= BDB_IDL_DB_MAX ) { ids[0] = NOID; } else { @@ -79,7 +79,7 @@ static int idl_insert( ID *ids, ID id ) static int idl_delete( ID *ids, ID id ) { - int x = idl_search( ids, id ); + int x = bdb_idl_search( ids, id ); if( x == 0 || ids[x] != id ) { /* not found */ @@ -104,7 +104,7 @@ bdb_idl_insert_key( ID id ) { int rc; - ID ids[BDB_IDL_SIZE]; + ID ids[BDB_IDL_DB_SIZE]; DBT data; assert( id != NOID ); @@ -158,7 +158,7 @@ bdb_idl_delete_key( ID id ) { int rc; - ID ids[BDB_IDL_SIZE]; + ID ids[BDB_IDL_DB_SIZE]; DBT data; assert( id != NOID ); diff --git a/servers/slapd/back-bdb/nextid.c b/servers/slapd/back-bdb/nextid.c index dbbbfb2633..dda51467db 100644 --- a/servers/slapd/back-bdb/nextid.c +++ b/servers/slapd/back-bdb/nextid.c @@ -57,7 +57,7 @@ retry: if( tid != NULL ) { goto retry; case DB_NOTFOUND: - id = NOID; + id = 0; break; case 0: diff --git a/servers/slapd/back-bdb/proto-bdb.h b/servers/slapd/back-bdb/proto-bdb.h index e7a869ba4b..1f4daa3fd5 100644 --- a/servers/slapd/back-bdb/proto-bdb.h +++ b/servers/slapd/back-bdb/proto-bdb.h @@ -102,6 +102,8 @@ int bdb_id2entry( /* * idl.c */ +int bdb_idl_search( ID *ids, ID id ); + int bdb_idl_insert_key( BackendDB *be, DB *db, diff --git a/servers/slapd/back-bdb/search.c b/servers/slapd/back-bdb/search.c new file mode 100644 index 0000000000..4b0a7ef670 --- /dev/null +++ b/servers/slapd/back-bdb/search.c @@ -0,0 +1,394 @@ +/* search.c - search operation */ +/* $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" + +static int base_candidate( + Backend *be, + Entry *e, + ID *ids ); +int search_candidates(); + +static ID idl_first( ID *ids, ID *cursor ); +static ID idl_next( ID *ids, ID *cursor ); + +int +bdb_search( + Backend *be, + Connection *conn, + Operation *op, + const char *base, + const char *nbase, + int scope, + int deref, + int slimit, + int tlimit, + Filter *filter, + const char *filterstr, + char **attrs, + int attrsonly ) +{ + int abandon; + struct bdb_info *bdb = (struct bdb_info *) be->be_private; + int rc, err; + const char *text = NULL; + time_t stoptime; + ID candidates[BDB_IDL_SIZE]; + ID id, cursor; + Entry *e = NULL; + struct berval **v2refs = NULL; + Entry *matched = NULL; + char *realbase = NULL; + int nentries = 0; + int manageDSAit = get_manageDSAit( op ); + + Debug(LDAP_DEBUG_TRACE, "=> ldbm_back_search\n", 0, 0, 0); + + /* obtain entry */ + rc = dn2entry_r( be, NULL, nbase, &e, &matched ); + + switch(rc) { + case DB_NOTFOUND: + case 0: + break; + default: + send_ldap_result( conn, op, rc=LDAP_OTHER, + NULL, "internal error", NULL, NULL ); + return rc; + } + + if ( e == NULL ) { + char *matched_dn = NULL; + struct berval **refs = NULL; + + if ( matched != NULL ) { + matched_dn = ch_strdup( matched->e_dn ); + + refs = is_entry_referral( matched ) + ? get_entry_referrals( be, conn, op, matched ) + : NULL; + + } else { + refs = default_referral; + } + + send_ldap_result( conn, op, err, + matched_dn, text, refs, NULL ); + + if( matched != NULL ) { + ber_bvecfree( refs ); + free( matched_dn ); + bdb_entry_return( be, matched ); + } + + return 1; + } + + if (!manageDSAit && is_entry_referral( e ) ) { + /* entry is a referral, don't allow add */ + char *matched_dn = ch_strdup( e->e_dn ); + struct berval **refs = get_entry_referrals( be, + conn, op, e ); + + bdb_entry_return( be, e ); + + Debug( LDAP_DEBUG_TRACE, "bdb_search: entry is referral\n", + 0, 0, 0 ); + + send_ldap_result( conn, op, LDAP_REFERRAL, + matched_dn, NULL, refs, NULL ); + + ber_bvecfree( refs ); + free( matched_dn ); + + return 1; + } + + if ( is_entry_alias( e ) ) { + /* don't deref */ + deref = LDAP_DEREF_NEVER; + } + + if ( tlimit == 0 && be_isroot( be, op->o_ndn ) ) { + tlimit = -1; /* allow root to set no limit */ + } else { + tlimit = (tlimit > be->be_timelimit || tlimit < 1) ? + be->be_timelimit : tlimit; + stoptime = op->o_time + tlimit; + } + + if ( slimit == 0 && be_isroot( be, op->o_ndn ) ) { + slimit = -1; /* allow root to set no limit */ + } else { + slimit = (slimit > be->be_sizelimit || slimit < 1) ? + be->be_sizelimit : slimit; + } + + if ( scope == LDAP_SCOPE_BASE ) { + rc = base_candidate( be, e, candidates ); + + } else { + rc = search_candidates( be, e, filter, + scope, deref, manageDSAit, candidates ); + } + + /* need normalized dn below */ + realbase = ch_strdup( e->e_ndn ); + + /* start cursor at base entry's id */ + cursor = e->e_id; + + bdb_entry_return( be, e ); + + if ( candidates[0] == 0 ) { + Debug( LDAP_DEBUG_TRACE, "bdb_search: no candidates\n", + 0, 0, 0 ); + + send_search_result( conn, op, + LDAP_SUCCESS, + NULL, NULL, NULL, NULL, 0 ); + + rc = 1; + goto done; + } + + for ( id = idl_first( candidates, &cursor ); + id != NOID; + id = idl_next( candidates, &cursor ) ) + { + int scopeok = 0; + + /* check for abandon */ + ldap_pvt_thread_mutex_lock( &op->o_abandonmutex ); + abandon = op->o_abandon; + ldap_pvt_thread_mutex_unlock( &op->o_abandonmutex ); + + if ( abandon ) { + rc = 0; + goto done; + } + + /* check time limit */ + if ( tlimit != -1 && slap_get_time() > stoptime ) { + send_search_result( conn, op, LDAP_TIMELIMIT_EXCEEDED, + NULL, NULL, v2refs, NULL, nentries ); + rc = 0; + goto done; + } + + /* get the entry with reader lock */ + rc = bdb_id2entry( be, NULL, id, &e ); + + if ( e == NULL ) { + Debug( LDAP_DEBUG_TRACE, + "bdb_search: candidate %ld not found\n", + id, 0, 0 ); + + goto loop_continue; + } + + if ( deref & LDAP_DEREF_SEARCHING && is_entry_alias( e ) ) { + Entry *matched; + int err; + const char *text; + + e = deref_entry_r( be, e, &err, &matched, &text ); + + if( e == NULL ) { + e = matched; + goto loop_continue; + } + + if( e->e_id == id ) { + /* circular loop */ + goto loop_continue; + } + + /* need to skip alias which deref into scope */ + if( scope & LDAP_SCOPE_ONELEVEL ) { + char *pdn = dn_parent( NULL, e->e_ndn ); + if ( pdn != NULL ) { + if( strcmp( pdn, realbase ) ) { + free( pdn ); + goto loop_continue; + } + free(pdn); + } + + } else if ( dn_issuffix( e->e_ndn, realbase ) ) { + /* alias is within scope */ + Debug( LDAP_DEBUG_TRACE, + "bdb_search: \"%s\" in subtree\n", + e->e_dn, 0, 0 ); + goto loop_continue; + } + + scopeok = 1; + } + + /* + * if it's a referral, add it to the list of referrals. only do + * this for non-base searches, and don't check the filter + * explicitly here since it's only a candidate anyway. + */ + if ( !manageDSAit && scope != LDAP_SCOPE_BASE && + is_entry_referral( e ) ) + { + struct berval **refs = get_entry_referrals( + be, conn, op, e ); + + send_search_reference( be, conn, op, + e, refs, scope, NULL, &v2refs ); + + ber_bvecfree( refs ); + + goto loop_continue; + } + + /* if it matches the filter and scope, send it */ + if ( test_filter( be, conn, op, e, filter ) == LDAP_COMPARE_TRUE ) { + char *dn; + + /* check scope */ + if ( !scopeok && scope == LDAP_SCOPE_ONELEVEL ) { + if ( (dn = dn_parent( be, e->e_ndn )) != NULL ) { + (void) dn_normalize( dn ); + scopeok = (dn == realbase) + ? 1 + : (strcmp( dn, realbase ) ? 0 : 1 ); + free( dn ); + + } else { + scopeok = (realbase == NULL || *realbase == '\0'); + } + + } else if ( !scopeok && scope == LDAP_SCOPE_SUBTREE ) { + dn = ch_strdup( e->e_ndn ); + scopeok = dn_issuffix( dn, realbase ); + free( dn ); + + } else { + scopeok = 1; + } + + if ( scopeok ) { + /* check size limit */ + if ( --slimit == -1 ) { + bdb_entry_return( be, e ); + send_search_result( conn, op, + LDAP_SIZELIMIT_EXCEEDED, NULL, NULL, + v2refs, NULL, nentries ); + rc = 0; + goto done; + } + + if (e) { + int result = send_search_entry( be, conn, op, + e, attrs, attrsonly, NULL); + + switch (result) { + case 0: /* entry sent ok */ + nentries++; + break; + case 1: /* entry not sent */ + break; + case -1: /* connection closed */ + bdb_entry_return( be, e ); + rc = 0; + goto done; + } + } + } else { + Debug( LDAP_DEBUG_TRACE, + "bdb_search: %ld scope not okay\n", + id, 0, 0 ); + } + } else { + Debug( LDAP_DEBUG_TRACE, + "bdb_search: %ld does match filter\n", + id, 0, 0 ); + } + +loop_continue: + if( e != NULL ) { + /* free reader lock */ + bdb_entry_return( be, e ); + } + + ldap_pvt_thread_yield(); + } + send_search_result( conn, op, + v2refs == NULL ? LDAP_SUCCESS : LDAP_REFERRAL, + NULL, NULL, v2refs, NULL, nentries ); + + rc = 0; + +done: + ber_bvecfree( v2refs ); + if( realbase ) free( realbase ); + + return rc; +} + + +static int base_candidate( + Backend *be, + Entry *e, + ID *ids ) +{ + Debug(LDAP_DEBUG_TRACE, "base_candidates: base: \"%s\" (0x08lx)\n", + e->e_dn, (long) e->e_id, 0); + + ids[0] = 1; + ids[1] = e->e_id; + return 0; +} + +static ID idl_first( ID *ids, ID *cursor ) +{ + ID pos; + + if ( ids[0] == 0 ) { + *cursor = NOID; + return NOID; + } + + if ( BDB_IS_ALLIDS( ids ) ) { + 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_IS_ALLIDS( ids ) ) { + if( ++(*cursor) < ids[1] ) { + return *cursor; + } + return NOID; + } + + if ( *cursor < ids[0] ) { + return ids[(*cursor)++]; + } + + return NOID; +} + -- 2.39.5