/* dn2id.c - routines to deal with the dn2id index */ /* $OpenLDAP: pkg/ldap/servers/slapd/back-bdb/dn2id.c,v 1.106.2.15 2007/01/02 21:44:00 kurt Exp $ */ /* This work is part of OpenLDAP Software . * * 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 * . */ #include "portable.h" #include #include #include "back-bdb.h" #include "idl.h" #include "lutil.h" #ifndef BDB_HIER int bdb_dn2id_add( Operation *op, DB_TXN *txn, EntryInfo *eip, Entry *e ) { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; int rc; DBT key, data; ID nid; char *buf; struct berval ptr, pdn; Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add( \"%s\", 0x%08lx )\n", e->e_ndn, (long) e->e_id, 0 ); assert( e->e_id != NOID ); DBTzero( &key ); key.size = e->e_nname.bv_len + 2; key.ulen = key.size; key.flags = DB_DBT_USERMEM; buf = op->o_tmpalloc( key.size, op->o_tmpmemctx ); key.data = buf; buf[0] = DN_BASE_PREFIX; ptr.bv_val = buf + 1; ptr.bv_len = e->e_nname.bv_len; AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len ); ptr.bv_val[ptr.bv_len] = '\0'; DBTzero( &data ); data.data = &nid; data.size = sizeof( nid ); BDB_ID2DISK( e->e_id, &nid ); /* store it -- don't override */ rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE ); if( rc != 0 ) { Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add: put failed: %s %d\n", db_strerror(rc), rc, 0 ); goto done; } #ifndef BDB_MULTIPLE_SUFFIXES if( !be_issuffix( op->o_bd, &ptr )) #endif { buf[0] = DN_SUBTREE_PREFIX; rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE ); if( rc != 0 ) { Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add: subtree (%s) put failed: %d\n", ptr.bv_val, rc, 0 ); goto done; } #ifdef BDB_MULTIPLE_SUFFIXES if( !be_issuffix( op->o_bd, &ptr )) #endif { dnParent( &ptr, &pdn ); key.size = pdn.bv_len + 2; key.ulen = key.size; pdn.bv_val[-1] = DN_ONE_PREFIX; key.data = pdn.bv_val-1; ptr = pdn; rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id ); if( rc != 0 ) { Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add: parent (%s) insert failed: %d\n", ptr.bv_val, rc, 0 ); goto done; } } #ifndef BDB_MULTIPLE_SUFFIXES while( !be_issuffix( op->o_bd, &ptr )) #else for (;;) #endif { ptr.bv_val[-1] = DN_SUBTREE_PREFIX; rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id ); if( rc != 0 ) { Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_add: subtree (%s) insert failed: %d\n", ptr.bv_val, rc, 0 ); break; } #ifdef BDB_MULTIPLE_SUFFIXES if( be_issuffix( op->o_bd, &ptr )) break; #endif dnParent( &ptr, &pdn ); key.size = pdn.bv_len + 2; key.ulen = key.size; key.data = pdn.bv_val - 1; ptr = pdn; } } done: op->o_tmpfree( buf, op->o_tmpmemctx ); Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add: %d\n", rc, 0, 0 ); return rc; } int bdb_dn2id_delete( Operation *op, DB_TXN *txn, EntryInfo *eip, Entry *e ) { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; int rc; DBT key; char *buf; struct berval pdn, ptr; Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete( \"%s\", 0x%08lx )\n", e->e_ndn, e->e_id, 0 ); DBTzero( &key ); key.size = e->e_nname.bv_len + 2; buf = op->o_tmpalloc( key.size, op->o_tmpmemctx ); key.data = buf; key.flags = DB_DBT_USERMEM; buf[0] = DN_BASE_PREFIX; ptr.bv_val = buf+1; ptr.bv_len = e->e_nname.bv_len; AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len ); ptr.bv_val[ptr.bv_len] = '\0'; /* delete it */ rc = db->del( db, txn, &key, 0 ); if( rc != 0 ) { Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete: delete failed: %s %d\n", db_strerror(rc), rc, 0 ); goto done; } #ifndef BDB_MULTIPLE_SUFFIXES if( !be_issuffix( op->o_bd, &ptr )) #endif { buf[0] = DN_SUBTREE_PREFIX; rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id ); if( rc != 0 ) { Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n", ptr.bv_val, rc, 0 ); goto done; } #ifdef BDB_MULTIPLE_SUFFIXES if( !be_issuffix( op->o_bd, &ptr )) #endif { dnParent( &ptr, &pdn ); key.size = pdn.bv_len + 2; key.ulen = key.size; pdn.bv_val[-1] = DN_ONE_PREFIX; key.data = pdn.bv_val - 1; ptr = pdn; rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id ); if( rc != 0 ) { Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete: parent (%s) delete failed: %d\n", ptr.bv_val, rc, 0 ); goto done; } } #ifndef BDB_MULTIPLE_SUFFIXES while( !be_issuffix( op->o_bd, &ptr )) #else for (;;) #endif { ptr.bv_val[-1] = DN_SUBTREE_PREFIX; rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id ); if( rc != 0 ) { Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete: subtree (%s) delete failed: %d\n", ptr.bv_val, rc, 0 ); goto done; } #ifdef BDB_MULTIPLE_SUFFIXES if( be_issuffix( op->o_bd, &ptr )) break; #endif dnParent( &ptr, &pdn ); key.size = pdn.bv_len + 2; key.ulen = key.size; key.data = pdn.bv_val - 1; ptr = pdn; } } done: op->o_tmpfree( buf, op->o_tmpmemctx ); Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete %d\n", rc, 0, 0 ); return rc; } int bdb_dn2id( Operation *op, DB_TXN *txn, struct berval *dn, EntryInfo *ei ) { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; int rc; DBT key, data; ID nid; Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id(\"%s\")\n", dn->bv_val, 0, 0 ); DBTzero( &key ); key.size = dn->bv_len + 2; key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx ); ((char *)key.data)[0] = DN_BASE_PREFIX; AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 ); /* store the ID */ DBTzero( &data ); data.data = &nid; data.ulen = sizeof(ID); data.flags = DB_DBT_USERMEM; /* fetch it */ rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags ); if( rc != 0 ) { Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n", db_strerror( rc ), rc, 0 ); } else { BDB_DISK2ID( &nid, &ei->bei_id ); Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%08lx\n", ei->bei_id, 0, 0 ); } op->o_tmpfree( key.data, op->o_tmpmemctx ); return rc; } int bdb_dn2id_children( Operation *op, DB_TXN *txn, Entry *e ) { DBT key, data; struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; ID id; int rc; Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children(\"%s\")\n", e->e_nname.bv_val, 0, 0 ); DBTzero( &key ); key.size = e->e_nname.bv_len + 2; key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx ); ((char *)key.data)[0] = DN_ONE_PREFIX; AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 ); if ( bdb->bi_idl_cache_size ) { rc = bdb_idl_cache_get( bdb, db, &key, NULL ); if ( rc != LDAP_NO_SUCH_OBJECT ) { op->o_tmpfree( key.data, op->o_tmpmemctx ); return rc; } } /* we actually could do a empty get... */ DBTzero( &data ); data.data = &id; data.ulen = sizeof(id); data.flags = DB_DBT_USERMEM; data.doff = 0; data.dlen = sizeof(id); rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags ); op->o_tmpfree( key.data, op->o_tmpmemctx ); Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children(\"%s\"): %s (%d)\n", e->e_nname.bv_val, rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " : db_strerror(rc) ), rc ); return rc; } int bdb_dn2idl( Operation *op, Entry *e, ID *ids, ID *stack ) { int rc; DBT key; struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; int prefix = ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) ? DN_ONE_PREFIX : DN_SUBTREE_PREFIX; Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl(\"%s\")\n", e->e_nname.bv_val, 0, 0 ); #ifndef BDB_MULTIPLE_SUFFIXES if ( prefix == DN_SUBTREE_PREFIX && BEI(e)->bei_parent->bei_id == 0 ) { BDB_IDL_ALL(bdb, ids); return 0; } #endif DBTzero( &key ); key.size = e->e_nname.bv_len + 2; key.ulen = key.size; key.flags = DB_DBT_USERMEM; key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx ); ((char *)key.data)[0] = prefix; AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 ); BDB_IDL_ZERO( ids ); rc = bdb_idl_fetch_key( op->o_bd, db, NULL, &key, ids, NULL, 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", (long) ids[0], (long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) ); } op->o_tmpfree( key.data, op->o_tmpmemctx ); return rc; } #else /* BDB_HIER */ /* Management routines for a hierarchically structured database. * * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each * entry in this database is a struct diskNode, keyed by entryID and with * the data containing the RDN and entryID of the node's children. We use * a B-Tree with sorted duplicates to store all the children of a node under * the same key. Also, the first item under the key contains the entry's own * rdn and the ID of the node's parent, to allow bottom-up tree traversal as * well as top-down. To keep this info first in the list, the high bit of all * subsequent nrdnlen's is always set. This means we can only accomodate * RDNs up to length 32767, but that's fine since full DNs are already * restricted to 8192. * * The diskNode is a variable length structure. This definition is not * directly usable for in-memory manipulation. */ typedef struct diskNode { unsigned char nrdnlen[2]; char nrdn[1]; char rdn[1]; /* variable placement */ unsigned char entryID[sizeof(ID)]; /* variable placement */ } diskNode; /* This function constructs a full DN for a given entry. */ int hdb_fix_dn( Entry *e, int checkit ) { EntryInfo *ei; int rlen = 0, nrlen = 0; char *ptr, *nptr; int max = 0; if ( !e->e_id ) return 0; /* count length of all DN components */ for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) { rlen += ei->bei_rdn.bv_len + 1; nrlen += ei->bei_nrdn.bv_len + 1; if (ei->bei_modrdns > max) max = ei->bei_modrdns; } /* See if the entry DN was invalidated by a subtree rename */ if ( checkit ) { if ( BEI(e)->bei_modrdns >= max ) { return 0; } /* We found a mismatch, tell the caller to lock it */ if ( checkit == 1 ) { return 1; } /* checkit == 2. do the fix. */ free( e->e_name.bv_val ); free( e->e_nname.bv_val ); } e->e_name.bv_len = rlen - 1; e->e_nname.bv_len = nrlen - 1; e->e_name.bv_val = ch_malloc(rlen); e->e_nname.bv_val = ch_malloc(nrlen); ptr = e->e_name.bv_val; nptr = e->e_nname.bv_val; for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) { ptr = lutil_strcopy(ptr, ei->bei_rdn.bv_val); nptr = lutil_strcopy(nptr, ei->bei_nrdn.bv_val); if ( ei->bei_parent ) { *ptr++ = ','; *nptr++ = ','; } } BEI(e)->bei_modrdns = max; ptr[-1] = '\0'; nptr[-1] = '\0'; return 0; } /* We add two elements to the DN2ID database - a data item under the parent's * entryID containing the child's RDN and entryID, and an item under the * child's entryID containing the parent's entryID. */ int hdb_dn2id_add( Operation *op, DB_TXN *txn, EntryInfo *eip, Entry *e ) { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; DBT key, data; ID nid; int rc, rlen, nrlen; diskNode *d; char *ptr; nrlen = dn_rdnlen( op->o_bd, &e->e_nname ); if (nrlen) { rlen = dn_rdnlen( op->o_bd, &e->e_name ); } else { nrlen = e->e_nname.bv_len; rlen = e->e_name.bv_len; } d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx); d->nrdnlen[1] = nrlen & 0xff; d->nrdnlen[0] = (nrlen >> 8) | 0x80; ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen ); *ptr++ = '\0'; ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen ); *ptr++ = '\0'; BDB_ID2DISK( e->e_id, ptr ); DBTzero(&key); DBTzero(&data); key.size = sizeof(ID); key.flags = DB_DBT_USERMEM; BDB_ID2DISK( eip->bei_id, &nid ); key.data = &nid; /* Need to make dummy root node once. Subsequent attempts * will fail harmlessly. */ if ( eip->bei_id == 0 ) { diskNode dummy = {{0, 0}, "", "", ""}; data.data = &dummy; data.size = sizeof(diskNode); data.flags = DB_DBT_USERMEM; db->put( db, txn, &key, &data, DB_NODUPDATA ); } data.data = d; data.size = sizeof(diskNode) + rlen + nrlen; data.flags = DB_DBT_USERMEM; rc = db->put( db, txn, &key, &data, DB_NODUPDATA ); if (rc == 0) { BDB_ID2DISK( e->e_id, &nid ); BDB_ID2DISK( eip->bei_id, ptr ); d->nrdnlen[0] ^= 0x80; rc = db->put( db, txn, &key, &data, DB_NODUPDATA ); } /* Update all parents' IDL cache entries */ if ( rc == 0 && bdb->bi_idl_cache_size ) { ID tmp[2]; char *ptr = ((char *)&tmp[1])-1; key.data = ptr; key.size = sizeof(ID)+1; tmp[1] = eip->bei_id; *ptr = DN_ONE_PREFIX; bdb_idl_cache_add_id( bdb, db, &key, e->e_id ); *ptr = DN_SUBTREE_PREFIX; for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) { tmp[1] = eip->bei_id; bdb_idl_cache_add_id( bdb, db, &key, e->e_id ); } } op->o_tmpfree( d, op->o_tmpmemctx ); return rc; } int hdb_dn2id_delete( Operation *op, DB_TXN *txn, EntryInfo *eip, Entry *e ) { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; DBT key, data; DBC *cursor; diskNode *d; int rc; ID nid; unsigned char dlen[2]; DBTzero(&key); key.size = sizeof(ID); key.ulen = key.size; key.flags = DB_DBT_USERMEM; BDB_ID2DISK( eip->bei_id, &nid ); DBTzero(&data); data.size = sizeof(diskNode) + BEI(e)->bei_nrdn.bv_len - sizeof(ID) - 1; data.ulen = data.size; data.dlen = data.size; data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL; key.data = &nid; rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags ); if ( rc ) return rc; d = op->o_tmpalloc( data.size, op->o_tmpmemctx ); d->nrdnlen[1] = BEI(e)->bei_nrdn.bv_len & 0xff; d->nrdnlen[0] = (BEI(e)->bei_nrdn.bv_len >> 8) | 0x80; dlen[0] = d->nrdnlen[0]; dlen[1] = d->nrdnlen[1]; strcpy( d->nrdn, BEI(e)->bei_nrdn.bv_val ); data.data = d; /* Delete our ID from the parent's list */ rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE ); if ( rc == 0 ) { if ( dlen[1] == d->nrdnlen[1] && dlen[0] == d->nrdnlen[0] && !strcmp( d->nrdn, BEI(e)->bei_nrdn.bv_val )) rc = cursor->c_del( cursor, 0 ); else rc = DB_NOTFOUND; } /* Delete our ID from the tree. With sorted duplicates, this * will leave any child nodes still hanging around. This is OK * for modrdn, which will add our info back in later. */ if ( rc == 0 ) { BDB_ID2DISK( e->e_id, &nid ); rc = cursor->c_get( cursor, &key, &data, DB_SET ); if ( rc == 0 ) rc = cursor->c_del( cursor, 0 ); } cursor->c_close( cursor ); op->o_tmpfree( d, op->o_tmpmemctx ); /* Delete IDL cache entries */ if ( rc == 0 && bdb->bi_idl_cache_size ) { ID tmp[2]; char *ptr = ((char *)&tmp[1])-1; key.data = ptr; key.size = sizeof(ID)+1; tmp[1] = eip->bei_id; *ptr = DN_ONE_PREFIX; bdb_idl_cache_del_id( bdb, db, &key, e->e_id ); *ptr = DN_SUBTREE_PREFIX; for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) { tmp[1] = eip->bei_id; bdb_idl_cache_del_id( bdb, db, &key, e->e_id ); } } return rc; } int hdb_dn2id( Operation *op, DB_TXN *txn, struct berval *in, EntryInfo *ei ) { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; DBT key, data; DBC *cursor; int rc = 0, nrlen; diskNode *d; char *ptr; unsigned char dlen[2]; ID idp, parentID; nrlen = dn_rdnlen( op->o_bd, in ); if (!nrlen) nrlen = in->bv_len; DBTzero(&key); key.size = sizeof(ID); key.data = &idp; key.ulen = sizeof(ID); key.flags = DB_DBT_USERMEM; parentID = ( ei->bei_parent != NULL ) ? ei->bei_parent->bei_id : 0; BDB_ID2DISK( parentID, &idp ); DBTzero(&data); data.size = sizeof(diskNode) + nrlen - sizeof(ID) - 1; data.ulen = data.size * 3; data.dlen = data.ulen; data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL; rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags ); if ( rc ) return rc; d = op->o_tmpalloc( data.size * 3, op->o_tmpmemctx ); d->nrdnlen[1] = nrlen & 0xff; d->nrdnlen[0] = (nrlen >> 8) | 0x80; dlen[0] = d->nrdnlen[0]; dlen[1] = d->nrdnlen[1]; ptr = lutil_strncopy( d->nrdn, in->bv_val, nrlen ); *ptr = '\0'; data.data = d; rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE ); if ( rc == 0 && (dlen[1] != d->nrdnlen[1] || dlen[0] != d->nrdnlen[0] || strncmp( d->nrdn, in->bv_val, nrlen ))) { rc = DB_NOTFOUND; } if ( rc == 0 ) { ptr = (char *) data.data + data.size - sizeof(ID); BDB_DISK2ID( ptr, &ei->bei_id ); ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - nrlen; ptr = d->nrdn + nrlen + 1; ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn ); if ( ei->bei_parent != NULL && !ei->bei_parent->bei_dkids ) { db_recno_t dkids; /* How many children does the parent have? */ /* FIXME: do we need to lock the parent * entryinfo? Seems safe... */ cursor->c_count( cursor, &dkids, 0 ); ei->bei_parent->bei_dkids = dkids; } } cursor->c_close( cursor ); op->o_tmpfree( d, op->o_tmpmemctx ); return rc; } int hdb_dn2id_parent( Operation *op, DB_TXN *txn, u_int32_t locker, EntryInfo *ei, ID *idp ) { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; DBT key, data; DBC *cursor; int rc = 0; diskNode *d; char *ptr; ID nid; DBTzero(&key); key.size = sizeof(ID); key.data = &nid; key.ulen = sizeof(ID); key.flags = DB_DBT_USERMEM; BDB_ID2DISK( ei->bei_id, &nid ); DBTzero(&data); data.flags = DB_DBT_USERMEM; rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags ); if ( rc ) return rc; if ( !txn && locker ) { cursor->locker = locker; } data.ulen = sizeof(diskNode) + (SLAP_LDAPDN_MAXLEN * 2); d = op->o_tmpalloc( data.ulen, op->o_tmpmemctx ); data.data = d; rc = cursor->c_get( cursor, &key, &data, DB_SET ); if ( rc == 0 ) { if (d->nrdnlen[0] & 0x80) { rc = LDAP_OTHER; } else { db_recno_t dkids; ptr = (char *) data.data + data.size - sizeof(ID); BDB_DISK2ID( ptr, idp ); ei->bei_nrdn.bv_len = (d->nrdnlen[0] << 8) | d->nrdnlen[1]; ber_str2bv( d->nrdn, ei->bei_nrdn.bv_len, 1, &ei->bei_nrdn ); ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - ei->bei_nrdn.bv_len; ptr = d->nrdn + ei->bei_nrdn.bv_len + 1; ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn ); /* How many children does this node have? */ cursor->c_count( cursor, &dkids, 0 ); ei->bei_dkids = dkids; } } cursor->c_close( cursor ); op->o_tmpfree( d, op->o_tmpmemctx ); return rc; } int hdb_dn2id_children( Operation *op, DB_TXN *txn, Entry *e ) { struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; DB *db = bdb->bi_dn2id->bdi_db; DBT key, data; DBC *cursor; int rc; ID id; diskNode d; DBTzero(&key); key.size = sizeof(ID); key.data = &e->e_id; key.flags = DB_DBT_USERMEM; BDB_ID2DISK( e->e_id, &id ); /* IDL cache is in host byte order */ if ( bdb->bi_idl_cache_size ) { rc = bdb_idl_cache_get( bdb, db, &key, NULL ); if ( rc != LDAP_NO_SUCH_OBJECT ) { return rc; } } key.data = &id; DBTzero(&data); data.data = &d; data.ulen = sizeof(d); data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL; data.dlen = sizeof(d); rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags ); if ( rc ) return rc; rc = cursor->c_get( cursor, &key, &data, DB_SET ); if ( rc == 0 ) { db_recno_t dkids; rc = cursor->c_count( cursor, &dkids, 0 ); if ( rc == 0 ) { BEI(e)->bei_dkids = dkids; if ( dkids < 2 ) rc = DB_NOTFOUND; } } cursor->c_close( cursor ); return rc; } /* bdb_dn2idl: * We can't just use bdb_idl_fetch_key because * 1 - our data items are longer than just an entry ID * 2 - our data items are sorted alphabetically by nrdn, not by ID. * * We descend the tree recursively, so we define this cookie * to hold our necessary state information. The bdb_dn2idl_internal * function uses this cookie when calling itself. */ struct dn2id_cookie { struct bdb_info *bdb; Operation *op; EntryInfo *ei; ID *ids; ID *tmp; ID *buf; DB *db; DBC *dbc; DBT key; DBT data; ID dbuf; ID id; ID nid; int rc; int depth; char need_sort; char prefix; }; static int apply_func( void *data, void *arg ) { EntryInfo *ei = data; ID *idl = arg; bdb_idl_append_one( idl, ei->bei_id ); return 0; } static int hdb_dn2idl_internal( struct dn2id_cookie *cx ) { BDB_IDL_ZERO( cx->tmp ); if ( cx->bdb->bi_idl_cache_size ) { char *ptr = ((char *)&cx->id)-1; cx->key.data = ptr; cx->key.size = sizeof(ID)+1; if ( cx->prefix == DN_SUBTREE_PREFIX ) { ID *ids = cx->depth ? cx->tmp : cx->ids; *ptr = cx->prefix; cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, ids); if ( cx->rc == LDAP_SUCCESS ) { if ( cx->depth ) { bdb_idl_append( cx->ids, cx->tmp ); cx->need_sort = 1; } return cx->rc; } } *ptr = DN_ONE_PREFIX; cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, cx->tmp); if ( cx->rc == LDAP_SUCCESS ) { goto gotit; } if ( cx->rc == DB_NOTFOUND ) { return cx->rc; } } bdb_cache_entryinfo_lock( cx->ei ); /* If number of kids in the cache differs from on-disk, load * up all the kids from the database */ if ( cx->ei->bei_ckids+1 != cx->ei->bei_dkids ) { EntryInfo ei; db_recno_t dkids = cx->ei->bei_dkids; ei.bei_parent = cx->ei; /* Only one thread should load the cache */ while ( cx->ei->bei_state & CACHE_ENTRY_ONELEVEL ) { bdb_cache_entryinfo_unlock( cx->ei ); ldap_pvt_thread_yield(); bdb_cache_entryinfo_lock( cx->ei ); if ( cx->ei->bei_ckids+1 == cx->ei->bei_dkids ) { goto synced; } } cx->ei->bei_state |= CACHE_ENTRY_ONELEVEL; bdb_cache_entryinfo_unlock( cx->ei ); cx->rc = cx->db->cursor( cx->db, NULL, &cx->dbc, cx->bdb->bi_db_opflags ); if ( cx->rc ) goto done_one; cx->data.data = &cx->dbuf; cx->data.ulen = sizeof(ID); cx->data.dlen = sizeof(ID); cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL; /* The first item holds the parent ID. Ignore it. */ cx->key.data = &cx->nid; cx->key.size = sizeof(ID); cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET ); if ( cx->rc ) { cx->dbc->c_close( cx->dbc ); goto done_one; } /* If the on-disk count is zero we've never checked it. * Count it now. */ if ( !dkids ) { cx->dbc->c_count( cx->dbc, &dkids, 0 ); cx->ei->bei_dkids = dkids; } cx->data.data = cx->buf; cx->data.ulen = BDB_IDL_UM_SIZE * sizeof(ID); cx->data.flags = DB_DBT_USERMEM; if ( dkids > 1 ) { /* Fetch the rest of the IDs in a loop... */ while ( (cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_MULTIPLE | DB_NEXT_DUP )) == 0 ) { u_int8_t *j; size_t len; void *ptr; DB_MULTIPLE_INIT( ptr, &cx->data ); while (ptr) { DB_MULTIPLE_NEXT( ptr, &cx->data, j, len ); if (j) { EntryInfo *ei2; diskNode *d = (diskNode *)j; short nrlen; BDB_DISK2ID( j + len - sizeof(ID), &ei.bei_id ); nrlen = ((d->nrdnlen[0] ^ 0x80) << 8) | d->nrdnlen[1]; ei.bei_nrdn.bv_len = nrlen; /* nrdn/rdn are set in-place. * hdb_cache_load will copy them as needed */ ei.bei_nrdn.bv_val = d->nrdn; ei.bei_rdn.bv_len = len - sizeof(diskNode) - ei.bei_nrdn.bv_len; ei.bei_rdn.bv_val = d->nrdn + ei.bei_nrdn.bv_len + 1; bdb_idl_append_one( cx->tmp, ei.bei_id ); hdb_cache_load( cx->bdb, &ei, &ei2 ); } } } } cx->rc = cx->dbc->c_close( cx->dbc ); done_one: bdb_cache_entryinfo_lock( cx->ei ); cx->ei->bei_state ^= CACHE_ENTRY_ONELEVEL; bdb_cache_entryinfo_unlock( cx->ei ); if ( cx->rc ) return cx->rc; } else { /* The in-memory cache is in sync with the on-disk data. * do we have any kids? */ synced: cx->rc = 0; if ( cx->ei->bei_ckids > 0 ) { /* Walk the kids tree; order is irrelevant since bdb_idl_sort * will sort it later. */ avl_apply( cx->ei->bei_kids, apply_func, cx->tmp, -1, AVL_POSTORDER ); } bdb_cache_entryinfo_unlock( cx->ei ); } if ( !BDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 3 ) bdb_idl_sort( cx->tmp, cx->buf ); if ( cx->bdb->bi_idl_cache_max_size && !BDB_IDL_IS_ZERO( cx->tmp )) { char *ptr = ((char *)&cx->id)-1; cx->key.data = ptr; cx->key.size = sizeof(ID)+1; *ptr = DN_ONE_PREFIX; bdb_idl_cache_put( cx->bdb, cx->db, &cx->key, cx->tmp, cx->rc ); } gotit: if ( !BDB_IDL_IS_ZERO( cx->tmp )) { if ( cx->prefix == DN_SUBTREE_PREFIX ) { bdb_idl_append( cx->ids, cx->tmp ); cx->need_sort = 1; if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) { ID *save, idcurs; EntryInfo *ei = cx->ei; int nokids = 1; save = cx->op->o_tmpalloc( BDB_IDL_SIZEOF( cx->tmp ), cx->op->o_tmpmemctx ); BDB_IDL_CPY( save, cx->tmp ); idcurs = 0; cx->depth++; for ( cx->id = bdb_idl_first( save, &idcurs ); cx->id != NOID; cx->id = bdb_idl_next( save, &idcurs )) { cx->ei = bdb_cache_find_info( cx->bdb, cx->id ); if ( !cx->ei || ( cx->ei->bei_state & CACHE_ENTRY_NO_KIDS )) continue; BDB_ID2DISK( cx->id, &cx->nid ); hdb_dn2idl_internal( cx ); if ( !BDB_IDL_IS_ZERO( cx->tmp )) nokids = 0; } cx->depth--; cx->op->o_tmpfree( save, cx->op->o_tmpmemctx ); if ( nokids ) ei->bei_state |= CACHE_ENTRY_NO_GRANDKIDS; } /* Make sure caller knows it had kids! */ cx->tmp[0]=1; cx->rc = 0; } else { BDB_IDL_CPY( cx->ids, cx->tmp ); } } return cx->rc; } int hdb_dn2idl( Operation *op, Entry *e, ID *ids, ID *stack ) { struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private; struct dn2id_cookie cx; Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2idl(\"%s\")\n", e->e_nname.bv_val, 0, 0 ); #ifndef BDB_MULTIPLE_SUFFIXES if ( op->ors_scope != LDAP_SCOPE_ONELEVEL && BEI(e)->bei_parent->bei_id == 0 ) { BDB_IDL_ALL( bdb, ids ); return 0; } #endif cx.id = e->e_id; BDB_ID2DISK( cx.id, &cx.nid ); cx.ei = e->e_id ? BEI(e) : &bdb->bi_cache.c_dntree; cx.bdb = bdb; cx.db = cx.bdb->bi_dn2id->bdi_db; cx.prefix = (op->ors_scope == LDAP_SCOPE_ONELEVEL) ? DN_ONE_PREFIX : DN_SUBTREE_PREFIX; cx.ids = ids; cx.tmp = stack; cx.buf = stack + BDB_IDL_UM_SIZE; cx.op = op; cx.need_sort = 0; cx.depth = 0; if ( cx.prefix == DN_SUBTREE_PREFIX ) { ids[0] = 1; ids[1] = cx.id; } else { BDB_IDL_ZERO( ids ); } if ( cx.ei->bei_state & CACHE_ENTRY_NO_KIDS ) return LDAP_SUCCESS; DBTzero(&cx.key); cx.key.ulen = sizeof(ID); cx.key.size = sizeof(ID); cx.key.flags = DB_DBT_USERMEM; DBTzero(&cx.data); hdb_dn2idl_internal(&cx); if ( cx.need_sort ) { char *ptr = ((char *)&cx.id)-1; if ( !BDB_IDL_IS_RANGE( cx.ids ) && cx.ids[0] > 3 ) bdb_idl_sort( cx.ids, cx.tmp ); cx.key.data = ptr; cx.key.size = sizeof(ID)+1; *ptr = cx.prefix; cx.id = e->e_id; bdb_idl_cache_put( cx.bdb, cx.db, &cx.key, cx.ids, cx.rc ); } if ( cx.rc == DB_NOTFOUND ) cx.rc = LDAP_SUCCESS; return cx.rc; } #endif /* BDB_HIER */