idl.c

ldap服务器源码

/* idl.c - ldap id list handling routines */
/* $OpenLDAP: pkg/ldap/servers/slapd/back-bdb/idl.c,v 1.94.2.15 2007/01/02 21:44:00 kurt Exp $ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
 * Copyright 2000-2007 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>.
 */

#include "portable.h"

#include <stdio.h>
#include <ac/string.h>

#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 ) )

#define IDL_LRU_DELETE( bdb, e ) do { 					\
	if ( e->idl_lru_prev != NULL ) {				\
		e->idl_lru_prev->idl_lru_next = e->idl_lru_next; 	\
	} else {							\
		bdb->bi_idl_lru_head = e->idl_lru_next;			\
	}								\
	if ( e->idl_lru_next != NULL ) {				\
		e->idl_lru_next->idl_lru_prev = e->idl_lru_prev;	\
	} else {							\
		bdb->bi_idl_lru_tail = e->idl_lru_prev;			\
	}								\
} while ( 0 )

#define IDL_LRU_ADD( bdb, e ) do {					\
	e->idl_lru_next = bdb->bi_idl_lru_head;				\
	if ( e->idl_lru_next != NULL ) {				\
		e->idl_lru_next->idl_lru_prev = (e);			\
	}								\
	(bdb)->bi_idl_lru_head = (e);					\
	e->idl_lru_prev = NULL;						\
	if ( (bdb)->bi_idl_lru_tail == NULL ) {				\
		(bdb)->bi_idl_lru_tail = (e);				\
	}								\
} while ( 0 )

static int
bdb_idl_entry_cmp( const void *v_idl1, const void *v_idl2 )
{
	const bdb_idl_cache_entry_t *idl1 = v_idl1, *idl2 = v_idl2;
	int rc;

	if ((rc = SLAP_PTRCMP( idl1->db, idl2->db ))) return rc;
	if ((rc = idl1->kstr.bv_len - idl2->kstr.bv_len )) return rc;
	return ( memcmp ( idl1->kstr.bv_val, idl2->kstr.bv_val , idl1->kstr.bv_len ) );
}

#if IDL_DEBUG > 0
static void idl_check( ID *ids )
{
	if( BDB_IDL_IS_RANGE( ids ) ) {
		assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) );
	} else {
		ID i;
		for( i=1; i < ids[0]; i++ ) {
			assert( ids[i+1] > ids[i] );
		}
	}
}

#if IDL_DEBUG > 1
static void idl_dump( ID *ids )
{
	if( BDB_IDL_IS_RANGE( ids ) ) {
		Debug( LDAP_DEBUG_ANY,
			"IDL: range ( %ld - %ld )\n",
			(long) BDB_IDL_RANGE_FIRST( ids ),
			(long) BDB_IDL_RANGE_LAST( ids ) );

	} else {
		ID i;
		Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );

		for( i=1; i<=ids[0]; i++ ) {
			if( i % 16 == 1 ) {
				Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
			}
			Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
		}

		Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
	}

	idl_check( ids );
}
#endif /* IDL_DEBUG > 1 */
#endif /* IDL_DEBUG > 0 */

unsigned bdb_idl_search( ID *ids, ID id )
{
#define IDL_BINARY_SEARCH 1
#ifdef IDL_BINARY_SEARCH
	/*
	 * binary search of id in ids
	 * if found, returns position of id
	 * if not found, returns first postion greater than id
	 */
	unsigned base = 0;
	unsigned cursor = 0;
	int val = 0;
	unsigned n = ids[0];

#if IDL_DEBUG > 0
	idl_check( ids );
#endif

	while( 0 < n ) {
		int pivot = n >> 1;
		cursor = base + pivot;
		val = IDL_CMP( id, ids[cursor + 1] );

		if( val < 0 ) {
			n = pivot;

		} else if ( val > 0 ) {
			base = cursor + 1;
			n -= pivot + 1;

		} else {
			return cursor + 1;
		}
	}
	
	if( val > 0 ) {
		return cursor + 2;
	} else {
		return cursor + 1;
	}

#else
	/* (reverse) linear search */
	int i;

#if IDL_DEBUG > 0
	idl_check( ids );
#endif

	for( i=ids[0]; i; i-- ) {
		if( id > ids[i] ) {
			break;
		}
	}

	return i+1;
#endif
}

int bdb_idl_insert( ID *ids, ID id )
{
	unsigned x;

#if IDL_DEBUG > 1
	Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
	idl_dump( ids );
#elif IDL_DEBUG > 0
	idl_check( ids );
#endif

	if (BDB_IDL_IS_RANGE( ids )) {
		/* if already in range, treat as a dup */
		if (id >= BDB_IDL_FIRST(ids) && id <= BDB_IDL_LAST(ids))
			return -1;
		if (id < BDB_IDL_FIRST(ids))
			ids[1] = id;
		else if (id > BDB_IDL_LAST(ids))
			ids[2] = id;
		return 0;
	}

	x = bdb_idl_search( ids, id );
	assert( x > 0 );

	if( x < 1 ) {
		/* internal error */
		return -2;
	}

	if ( x <= ids[0] && ids[x] == id ) {
		/* duplicate */
		return -1;
	}

	if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
		if( id < ids[1] ) {
			ids[1] = id;
			ids[2] = ids[ids[0]-1];
		} else if ( ids[ids[0]-1] < id ) {
			ids[2] = id;
		} else {
			ids[2] = ids[ids[0]-1];
		}
		ids[0] = NOID;
	
	} else {
		/* insert id */
		AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
		ids[x] = id;
	}

#if IDL_DEBUG > 1
	idl_dump( ids );
#elif IDL_DEBUG > 0
	idl_check( ids );
#endif

	return 0;
}

static int bdb_idl_delete( ID *ids, ID id )
{
	unsigned x;

#if IDL_DEBUG > 1
	Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
	idl_dump( ids );
#elif IDL_DEBUG > 0
	idl_check( ids );
#endif

	if (BDB_IDL_IS_RANGE( ids )) {
		/* If deleting a range boundary, adjust */
		if ( ids[1] == id )
			ids[1]++;
		else if ( ids[2] == id )
			ids[2]--;
		/* deleting from inside a range is a no-op */

		/* If the range has collapsed, re-adjust */
		if ( ids[1] > ids[2] )
			ids[0] = 0;
		else if ( ids[1] == ids[2] )
			ids[1] = 1;
		return 0;
	}

	x = bdb_idl_search( ids, id );
	assert( x > 0 );

	if( x <= 0 ) {
		/* internal error */
		return -2;
	}

	if( x > ids[0] || ids[x] != id ) {
		/* not found */
		return -1;

	} else if ( --ids[0] == 0 ) {
		if( x != 1 ) {
			return -3;
		}

	} else {
		AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
	}

#if IDL_DEBUG > 1
	idl_dump( ids );
#elif IDL_DEBUG > 0
	idl_check( ids );
#endif

	return 0;
}

static char *
bdb_show_key(
	DBT		*key,
	char		*buf )
{
	if ( key->size == 4 /* LUTIL_HASH_BYTES */ ) {
		unsigned char *c = key->data;
		sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
		return buf;
	} else {
		return key->data;
	}
}

/* Find a db/key pair in the IDL cache. If ids is non-NULL,
 * copy the cached IDL into it, otherwise just return the status.
 */
int
bdb_idl_cache_get(
	struct bdb_info	*bdb,
	DB			*db,
	DBT			*key,
	ID			*ids )
{
	bdb_idl_cache_entry_t idl_tmp;
	bdb_idl_cache_entry_t *matched_idl_entry;
	int rc = LDAP_NO_SUCH_OBJECT;

	DBT2bv( key, &idl_tmp.kstr );
	idl_tmp.db = db;
	ldap_pvt_thread_rdwr_rlock( &bdb->bi_idl_tree_rwlock );
	matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
				      bdb_idl_entry_cmp );
	if ( matched_idl_entry != NULL ) {
		if ( matched_idl_entry->idl && ids )
			BDB_IDL_CPY( ids, matched_idl_entry->idl );
		ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
		IDL_LRU_DELETE( bdb, matched_idl_entry );
		IDL_LRU_ADD( bdb, matched_idl_entry );
		ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
		if ( matched_idl_entry->idl )
			rc = LDAP_SUCCESS;
		else
			rc = DB_NOTFOUND;
	}
	ldap_pvt_thread_rdwr_runlock( &bdb->bi_idl_tree_rwlock );

	return rc;
}

void
bdb_idl_cache_put(
	struct bdb_info	*bdb,
	DB			*db,
	DBT			*key,
	ID			*ids,
	int			rc )
{
	bdb_idl_cache_entry_t idl_tmp;
	bdb_idl_cache_entry_t *ee;

	if ( rc == DB_NOTFOUND || BDB_IDL_IS_ZERO( ids ))
		return;

	DBT2bv( key, &idl_tmp.kstr );

	ee = (bdb_idl_cache_entry_t *) ch_malloc(
		sizeof( bdb_idl_cache_entry_t ) );
	ee->db = db;
	ee->idl = (ID*) ch_malloc( BDB_IDL_SIZEOF ( ids ) );
	BDB_IDL_CPY( ee->idl, ids );

	ee->idl_lru_prev = NULL;
	ee->idl_lru_next = NULL;
	ber_dupbv( &ee->kstr, &idl_tmp.kstr );
	ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
	if ( avl_insert( &bdb->bi_idl_tree, (caddr_t) ee,
		bdb_idl_entry_cmp, avl_dup_error ))
	{
		ch_free( ee->kstr.bv_val );
		ch_free( ee->idl );
		ch_free( ee );
		ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
		return;
	}
	ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
	IDL_LRU_ADD( bdb, ee );
	if ( ++bdb->bi_idl_cache_size > bdb->bi_idl_cache_max_size ) {
		int i = 0;
		while ( bdb->bi_idl_lru_tail != NULL && i < 10 ) {
			ee = bdb->bi_idl_lru_tail;
			if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) ee,
				    bdb_idl_entry_cmp ) == NULL ) {
				Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_put: "
					"AVL delete failed\n",
					0, 0, 0 );
			}
			IDL_LRU_DELETE( bdb, ee );
			i++;
			--bdb->bi_idl_cache_size;
			ch_free( ee->kstr.bv_val );
			ch_free( ee->idl );
			ch_free( ee );
		}
	}

	ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
}

void
bdb_idl_cache_del(
	struct bdb_info	*bdb,
	DB			*db,
	DBT			*key )
{
	bdb_idl_cache_entry_t *matched_idl_entry, idl_tmp;
	DBT2bv( key, &idl_tmp.kstr );
	idl_tmp.db = db;
	ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
	matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
				      bdb_idl_entry_cmp );
	if ( matched_idl_entry != NULL ) {
		if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) matched_idl_entry,
				    bdb_idl_entry_cmp ) == NULL ) {
			Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: "
				"AVL delete failed\n",
				0, 0, 0 );
		}
		--bdb->bi_idl_cache_size;
		ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
		IDL_LRU_DELETE( bdb, matched_idl_entry );
		ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
		free( matched_idl_entry->kstr.bv_val );
		if ( matched_idl_entry->idl )
			free( matched_idl_entry->idl );
		free( matched_idl_entry );
	}
	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
}

void
bdb_idl_cache_add_id(
	struct bdb_info	*bdb,
	DB			*db,
	DBT			*key,
	ID			id )
{
	bdb_idl_cache_entry_t *cache_entry, idl_tmp;
	DBT2bv( key, &idl_tmp.kstr );
	idl_tmp.db = db;
	ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
	cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
				      bdb_idl_entry_cmp );
	if ( cache_entry != NULL ) {
		if ( !BDB_IDL_IS_RANGE( cache_entry->idl ) &&
			cache_entry->idl[0] < BDB_IDL_DB_MAX ) {
			size_t s = BDB_IDL_SIZEOF( cache_entry->idl ) + sizeof(ID);
			cache_entry->idl = ch_realloc( cache_entry->idl, s );
		}
		bdb_idl_insert( cache_entry->idl, id );
	}
	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
}

void
bdb_idl_cache_del_id(
	struct bdb_info	*bdb,
	DB			*db,
	DBT			*key,
	ID			id )
{
	bdb_idl_cache_entry_t *cache_entry, idl_tmp;
	DBT2bv( key, &idl_tmp.kstr );
	idl_tmp.db = db;
	ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
	cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
				      bdb_idl_entry_cmp );
	if ( cache_entry != NULL ) {
		bdb_idl_delete( cache_entry->idl, id );
		if ( cache_entry->idl[0] == 0 ) {
			if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) cache_entry,
						bdb_idl_entry_cmp ) == NULL ) {
				Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: "
					"AVL delete failed\n",
					0, 0, 0 );
			}
			--bdb->bi_idl_cache_size;
			ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
			IDL_LRU_DELETE( bdb, cache_entry );
			ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
			free( cache_entry->kstr.bv_val );
			free( cache_entry->idl );
			free( cache_entry );
		}
	}
	ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
}

int
bdb_idl_fetch_key(
	BackendDB	*be,
	DB			*db,
	DB_TXN		*tid,
	DBT			*key,
	ID			*ids,
	DBC                     **saved_cursor,
	int                     get_flag )
{
	struct bdb_info *bdb = (struct bdb_info *) be->be_private;
	int rc;
	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
	 * resources on subsequent get's.  We can safely call get()
	 * twice - once for the data, and once to get the DB_NOTFOUND
	 * result meaning there's no more data. See ITS#2040 for details.
	 * This bug is fixed in BDB 4.1 so a smaller buffer will work if
	 * stack space is too limited.
	 *
	 * configure now requires Berkeley DB 4.1.
	 */
#if DB_VERSION_FULL < 0x04010000
#	define BDB_ENOUGH 5
#else
	/* We sometimes test with tiny IDLs, and BDB always wants buffers
	 * that are at least one page in size.
	 */