git.sur5r.net Git - openldap/blob - servers/slapd/back-bdb/dn2id.c

   1 /* dn2id.c - routines to deal with the dn2id index */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2000-2009 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include "portable.h"
  18
  19 #include <stdio.h>
  20 #include <ac/string.h>
  21
  22 #include "back-bdb.h"
  23 #include "idl.h"
  24 #include "lutil.h"
  25
  26 #define bdb_dn2id_lock                                  BDB_SYMBOL(dn2id_lock)
  27
  28 static int
  29 bdb_dn2id_lock( struct bdb_info *bdb, struct berval *dn,
  30         int rw, DB_TXN *txn, DB_LOCK *lock )
  31 {
  32         int       rc;
  33         DBT       lockobj;
  34         int       db_rw;
  35
  36         if (!txn)
  37                 return 0;
  38
  39         if (rw)
  40                 db_rw = DB_LOCK_WRITE;
  41         else
  42                 db_rw = DB_LOCK_READ;
  43
  44         lockobj.data = dn->bv_val;
  45         lockobj.size = dn->bv_len;
  46
  47         rc = LOCK_GET(bdb->bi_dbenv, TXN_ID(txn), DB_LOCK_NOWAIT,
  48                                         &lockobj, db_rw, lock);
  49         return rc;
  50 }
  51
  52 #ifndef BDB_HIER
  53 int
  54 bdb_dn2id_add(
  55         Operation *op,
  56         DB_TXN *txn,
  57         EntryInfo *eip,
  58         Entry           *e )
  59 {
  60         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
  61         DB *db = bdb->bi_dn2id->bdi_db;
  62         int             rc;
  63         DBT             key, data;
  64         ID              nid;
  65         char            *buf;
  66         struct berval   ptr, pdn;
  67
  68         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add 0x%lx: \"%s\"\n",
  69                 e->e_id, e->e_ndn, 0 );
  70         assert( e->e_id != NOID );
  71
  72         DBTzero( &key );
  73         key.size = e->e_nname.bv_len + 2;
  74         key.ulen = key.size;
  75         key.flags = DB_DBT_USERMEM;
  76         buf = op->o_tmpalloc( key.size, op->o_tmpmemctx );
  77         key.data = buf;
  78         buf[0] = DN_BASE_PREFIX;
  79         ptr.bv_val = buf + 1;
  80         ptr.bv_len = e->e_nname.bv_len;
  81         AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
  82         ptr.bv_val[ptr.bv_len] = '\0';
  83
  84         DBTzero( &data );
  85         data.data = &nid;
  86         data.size = sizeof( nid );
  87         BDB_ID2DISK( e->e_id, &nid );
  88
  89         /* store it -- don't override */
  90         rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
  91         if( rc != 0 ) {
  92                 char buf[ SLAP_TEXT_BUFLEN ];
  93                 snprintf( buf, sizeof( buf ), "%s => bdb_dn2id_add dn=\"%s\" ID=0x%lx",
  94                         op->o_log_prefix, e->e_name.bv_val, e->e_id );
  95                 Debug( LDAP_DEBUG_ANY, "%s: put failed: %s %d\n",
  96                         buf, db_strerror(rc), rc );
  97                 goto done;
  98         }
  99
 100 #ifndef BDB_MULTIPLE_SUFFIXES
 101         if( !be_issuffix( op->o_bd, &ptr ))
 102 #endif
 103         {
 104                 buf[0] = DN_SUBTREE_PREFIX;
 105                 rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE );
 106                 if( rc != 0 ) {
 107                         Debug( LDAP_DEBUG_ANY,
 108                         "=> bdb_dn2id_add 0x%lx: subtree (%s) put failed: %d\n",
 109                         e->e_id, ptr.bv_val, rc );
 110                         goto done;
 111                 }
 112
 113 #ifdef BDB_MULTIPLE_SUFFIXES
 114         if( !be_issuffix( op->o_bd, &ptr ))
 115 #endif
 116         {
 117                 dnParent( &ptr, &pdn );
 118
 119                 key.size = pdn.bv_len + 2;
 120                 key.ulen = key.size;
 121                 pdn.bv_val[-1] = DN_ONE_PREFIX;
 122                 key.data = pdn.bv_val-1;
 123                 ptr = pdn;
 124
 125                 rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id );
 126
 127                 if( rc != 0 ) {
 128                         Debug( LDAP_DEBUG_ANY,
 129                                 "=> bdb_dn2id_add 0x%lx: parent (%s) insert failed: %d\n",
 130                                         e->e_id, ptr.bv_val, rc );
 131                         goto done;
 132                 }
 133         }
 134
 135 #ifndef BDB_MULTIPLE_SUFFIXES
 136         while( !be_issuffix( op->o_bd, &ptr ))
 137 #else
 138         for (;;)
 139 #endif
 140         {
 141                 ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
 142
 143                 rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id );
 144
 145                 if( rc != 0 ) {
 146                         Debug( LDAP_DEBUG_ANY,
 147                                 "=> bdb_dn2id_add 0x%lx: subtree (%s) insert failed: %d\n",
 148                                         e->e_id, ptr.bv_val, rc );
 149                         break;
 150                 }
 151 #ifdef BDB_MULTIPLE_SUFFIXES
 152                 if( be_issuffix( op->o_bd, &ptr )) break;
 153 #endif
 154                 dnParent( &ptr, &pdn );
 155
 156                 key.size = pdn.bv_len + 2;
 157                 key.ulen = key.size;
 158                 key.data = pdn.bv_val - 1;
 159                 ptr = pdn;
 160         }
 161         }
 162
 163 done:
 164         op->o_tmpfree( buf, op->o_tmpmemctx );
 165         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
 166         return rc;
 167 }
 168
 169 int
 170 bdb_dn2id_delete(
 171         Operation *op,
 172         DB_TXN *txn,
 173         EntryInfo       *eip,
 174         Entry           *e )
 175 {
 176         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 177         DB *db = bdb->bi_dn2id->bdi_db;
 178         char            *buf;
 179         DBT             key;
 180         DB_LOCK lock;
 181         struct berval   pdn, ptr;
 182         int             rc;
 183
 184         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete 0x%lx: \"%s\"\n",
 185                 e->e_id, e->e_ndn, 0 );
 186
 187         DBTzero( &key );
 188         key.size = e->e_nname.bv_len + 2;
 189         buf = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 190         key.data = buf;
 191         key.flags = DB_DBT_USERMEM;
 192         buf[0] = DN_BASE_PREFIX;
 193         ptr.bv_val = buf+1;
 194         ptr.bv_len = e->e_nname.bv_len;
 195         AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len );
 196         ptr.bv_val[ptr.bv_len] = '\0';
 197
 198         /* We hold this lock until the TXN completes */
 199         rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, txn, &lock );
 200         if ( rc ) goto done;
 201
 202         /* delete it */
 203         rc = db->del( db, txn, &key, 0 );
 204         if( rc != 0 ) {
 205                 Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete 0x%lx: delete failed: %s %d\n",
 206                         e->e_id, db_strerror(rc), rc );
 207                 goto done;
 208         }
 209
 210 #ifndef BDB_MULTIPLE_SUFFIXES
 211         if( !be_issuffix( op->o_bd, &ptr ))
 212 #endif
 213         {
 214                 buf[0] = DN_SUBTREE_PREFIX;
 215                 rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
 216                 if( rc != 0 ) {
 217                         Debug( LDAP_DEBUG_ANY,
 218                         "=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
 219                         e->e_id, ptr.bv_val, rc );
 220                         goto done;
 221                 }
 222
 223 #ifdef BDB_MULTIPLE_SUFFIXES
 224         if( !be_issuffix( op->o_bd, &ptr ))
 225 #endif
 226         {
 227                 dnParent( &ptr, &pdn );
 228
 229                 key.size = pdn.bv_len + 2;
 230                 key.ulen = key.size;
 231                 pdn.bv_val[-1] = DN_ONE_PREFIX;
 232                 key.data = pdn.bv_val - 1;
 233                 ptr = pdn;
 234
 235                 rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
 236
 237                 if( rc != 0 ) {
 238                         Debug( LDAP_DEBUG_ANY,
 239                                 "=> bdb_dn2id_delete 0x%lx: parent (%s) delete failed: %d\n",
 240                                 e->e_id, ptr.bv_val, rc );
 241                         goto done;
 242                 }
 243         }
 244
 245 #ifndef BDB_MULTIPLE_SUFFIXES
 246         while( !be_issuffix( op->o_bd, &ptr ))
 247 #else
 248         for (;;)
 249 #endif
 250         {
 251                 ptr.bv_val[-1] = DN_SUBTREE_PREFIX;
 252
 253                 rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id );
 254                 if( rc != 0 ) {
 255                         Debug( LDAP_DEBUG_ANY,
 256                                 "=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n",
 257                                 e->e_id, ptr.bv_val, rc );
 258                         goto done;
 259                 }
 260 #ifdef BDB_MULTIPLE_SUFFIXES
 261                 if( be_issuffix( op->o_bd, &ptr )) break;
 262 #endif
 263                 dnParent( &ptr, &pdn );
 264
 265                 key.size = pdn.bv_len + 2;
 266                 key.ulen = key.size;
 267                 key.data = pdn.bv_val - 1;
 268                 ptr = pdn;
 269         }
 270         }
 271
 272 done:
 273         op->o_tmpfree( buf, op->o_tmpmemctx );
 274         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
 275         return rc;
 276 }
 277
 278 int
 279 bdb_dn2id(
 280         Operation *op,
 281         struct berval   *dn,
 282         EntryInfo *ei,
 283         DB_TXN *txn,
 284         DB_LOCK *lock )
 285 {
 286         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 287         DB *db = bdb->bi_dn2id->bdi_db;
 288         DBC     *cursor;
 289         int             rc;
 290         DBT             key, data;
 291         ID              nid;
 292
 293         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id(\"%s\")\n", dn->bv_val, 0, 0 );
 294
 295         DBTzero( &key );
 296         key.size = dn->bv_len + 2;
 297         key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 298         ((char *)key.data)[0] = DN_BASE_PREFIX;
 299         AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 );
 300
 301         /* store the ID */
 302         DBTzero( &data );
 303         data.data = &nid;
 304         data.ulen = sizeof(ID);
 305         data.flags = DB_DBT_USERMEM;
 306
 307         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 308         if ( rc ) goto func_leave;
 309
 310         rc = bdb_dn2id_lock( bdb, dn, 0, txn, lock );
 311         if ( rc ) goto nolock;
 312
 313         /* fetch it */
 314         rc = cursor->c_get( cursor, &key, &data, DB_SET );
 315
 316 nolock:
 317         cursor->c_close( cursor );
 318 func_leave:
 319
 320         if( rc != 0 ) {
 321                 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n",
 322                         db_strerror( rc ), rc, 0 );
 323         } else {
 324                 BDB_DISK2ID( &nid, &ei->bei_id );
 325                 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%lx\n",
 326                         ei->bei_id, 0, 0 );
 327         }
 328         op->o_tmpfree( key.data, op->o_tmpmemctx );
 329         return rc;
 330 }
 331
 332 int
 333 bdb_dn2id_children(
 334         Operation *op,
 335         DB_TXN *txn,
 336         Entry *e )
 337 {
 338         DBT             key, data;
 339         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 340         DB *db = bdb->bi_dn2id->bdi_db;
 341         ID              id;
 342         int             rc;
 343
 344         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children(\"%s\")\n",
 345                 e->e_nname.bv_val, 0, 0 );
 346         DBTzero( &key );
 347         key.size = e->e_nname.bv_len + 2;
 348         key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 349         ((char *)key.data)[0] = DN_ONE_PREFIX;
 350         AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );
 351
 352         if ( bdb->bi_idl_cache_size ) {
 353                 rc = bdb_idl_cache_get( bdb, db, &key, NULL );
 354                 if ( rc != LDAP_NO_SUCH_OBJECT ) {
 355                         op->o_tmpfree( key.data, op->o_tmpmemctx );
 356                         return rc;
 357                 }
 358         }
 359         /* we actually could do a empty get... */
 360         DBTzero( &data );
 361         data.data = &id;
 362         data.ulen = sizeof(id);
 363         data.flags = DB_DBT_USERMEM;
 364         data.doff = 0;
 365         data.dlen = sizeof(id);
 366
 367         rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
 368         op->o_tmpfree( key.data, op->o_tmpmemctx );
 369
 370         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children(\"%s\"): %s (%d)\n",
 371                 e->e_nname.bv_val,
 372                 rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
 373                         db_strerror(rc) ), rc );
 374
 375         return rc;
 376 }
 377
 378 int
 379 bdb_dn2idl(
 380         Operation *op,
 381         DB_TXN *txn,
 382         struct berval *ndn,
 383         EntryInfo *ei,
 384         ID *ids,
 385         ID *stack )
 386 {
 387         int             rc;
 388         DBT             key;
 389         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 390         DB *db = bdb->bi_dn2id->bdi_db;
 391         int prefix = ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
 392                 ? DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
 393
 394         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl(\"%s\")\n",
 395                 ndn->bv_val, 0, 0 );
 396
 397 #ifndef BDB_MULTIPLE_SUFFIXES
 398         if ( prefix == DN_SUBTREE_PREFIX
 399                 && ( ei->bei_id == 0 ||
 400                 ( ei->bei_parent->bei_id == 0 && op->o_bd->be_suffix[0].bv_len ))) {
 401                 BDB_IDL_ALL(bdb, ids);
 402                 return 0;
 403         }
 404 #endif
 405
 406         DBTzero( &key );
 407         key.size = ndn->bv_len + 2;
 408         key.ulen = key.size;
 409         key.flags = DB_DBT_USERMEM;
 410         key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 411         ((char *)key.data)[0] = prefix;
 412         AC_MEMCPY( &((char *)key.data)[1], ndn->bv_val, key.size - 1 );
 413
 414         BDB_IDL_ZERO( ids );
 415         rc = bdb_idl_fetch_key( op->o_bd, db, txn, &key, ids, NULL, 0 );
 416
 417         if( rc != 0 ) {
 418                 Debug( LDAP_DEBUG_TRACE,
 419                         "<= bdb_dn2idl: get failed: %s (%d)\n",
 420                         db_strerror( rc ), rc, 0 );
 421
 422         } else {
 423                 Debug( LDAP_DEBUG_TRACE,
 424                         "<= bdb_dn2idl: id=%ld first=%ld last=%ld\n",
 425                         (long) ids[0],
 426                         (long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) );
 427         }
 428
 429         op->o_tmpfree( key.data, op->o_tmpmemctx );
 430         return rc;
 431 }
 432
 433 #else   /* BDB_HIER */
 434 /* Management routines for a hierarchically structured database.
 435  *
 436  * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each
 437  * entry in this database is a struct diskNode, keyed by entryID and with
 438  * the data containing the RDN and entryID of the node's children. We use
 439  * a B-Tree with sorted duplicates to store all the children of a node under
 440  * the same key. Also, the first item under the key contains the entry's own
 441  * rdn and the ID of the node's parent, to allow bottom-up tree traversal as
 442  * well as top-down. To keep this info first in the list, the high bit of all
 443  * subsequent nrdnlen's is always set. This means we can only accomodate
 444  * RDNs up to length 32767, but that's fine since full DNs are already
 445  * restricted to 8192.
 446  *
 447  * The diskNode is a variable length structure. This definition is not
 448  * directly usable for in-memory manipulation.
 449  */
 450 typedef struct diskNode {
 451         unsigned char nrdnlen[2];
 452         char nrdn[1];
 453         char rdn[1];                        /* variable placement */
 454         unsigned char entryID[sizeof(ID)];  /* variable placement */
 455 } diskNode;
 456
 457 /* Sort function for the sorted duplicate data items of a dn2id key.
 458  * Sorts based on normalized RDN, in length order.
 459  */
 460 int
 461 hdb_dup_compare(
 462         DB *db,
 463         const DBT *usrkey,
 464         const DBT *curkey
 465 )
 466 {
 467         diskNode *un, *cn;
 468         int rc;
 469
 470         un = (diskNode *)usrkey->data;
 471         cn = (diskNode *)curkey->data;
 472
 473         /* data is not aligned, cannot compare directly */
 474         rc = un->nrdnlen[0] - cn->nrdnlen[0];
 475         if ( rc ) return rc;
 476         rc = un->nrdnlen[1] - cn->nrdnlen[1];
 477         if ( rc ) return rc;
 478
 479         return strcmp( un->nrdn, cn->nrdn );
 480 }
 481
 482 /* This function constructs a full DN for a given entry.
 483  */
 484 int hdb_fix_dn(
 485         Entry *e,
 486         int checkit )
 487 {
 488         EntryInfo *ei;
 489         int rlen = 0, nrlen = 0;
 490         char *ptr, *nptr;
 491         int max = 0;
 492
 493         if ( !e->e_id )
 494                 return 0;
 495
 496         /* count length of all DN components */
 497         for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
 498                 rlen += ei->bei_rdn.bv_len + 1;
 499                 nrlen += ei->bei_nrdn.bv_len + 1;
 500                 if (ei->bei_modrdns > max) max = ei->bei_modrdns;
 501         }
 502
 503         /* See if the entry DN was invalidated by a subtree rename */
 504         if ( checkit ) {
 505                 if ( BEI(e)->bei_modrdns >= max ) {
 506                         return 0;
 507                 }
 508                 /* We found a mismatch, tell the caller to lock it */
 509                 if ( checkit == 1 ) {
 510                         return 1;
 511                 }
 512                 /* checkit == 2. do the fix. */
 513                 free( e->e_name.bv_val );
 514                 free( e->e_nname.bv_val );
 515         }
 516
 517         e->e_name.bv_len = rlen - 1;
 518         e->e_nname.bv_len = nrlen - 1;
 519         e->e_name.bv_val = ch_malloc(rlen);
 520         e->e_nname.bv_val = ch_malloc(nrlen);
 521         ptr = e->e_name.bv_val;
 522         nptr = e->e_nname.bv_val;
 523         for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
 524                 ptr = lutil_strcopy(ptr, ei->bei_rdn.bv_val);
 525                 nptr = lutil_strcopy(nptr, ei->bei_nrdn.bv_val);
 526                 if ( ei->bei_parent ) {
 527                         *ptr++ = ',';
 528                         *nptr++ = ',';
 529                 }
 530         }
 531         BEI(e)->bei_modrdns = max;
 532         if ( ptr > e->e_name.bv_val ) ptr[-1] = '\0';
 533         if ( nptr > e->e_nname.bv_val ) nptr[-1] = '\0';
 534
 535         return 0;
 536 }
 537
 538 /* We add two elements to the DN2ID database - a data item under the parent's
 539  * entryID containing the child's RDN and entryID, and an item under the
 540  * child's entryID containing the parent's entryID.
 541  */
 542 int
 543 hdb_dn2id_add(
 544         Operation       *op,
 545         DB_TXN *txn,
 546         EntryInfo       *eip,
 547         Entry           *e )
 548 {
 549         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 550         DB *db = bdb->bi_dn2id->bdi_db;
 551         DBT             key, data;
 552         ID              nid;
 553         int             rc, rlen, nrlen;
 554         diskNode *d;
 555         char *ptr;
 556
 557         Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_add 0x%lx: \"%s\"\n",
 558                 e->e_id, e->e_ndn, 0 );
 559
 560         nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
 561         if (nrlen) {
 562                 rlen = dn_rdnlen( op->o_bd, &e->e_name );
 563         } else {
 564                 nrlen = e->e_nname.bv_len;
 565                 rlen = e->e_name.bv_len;
 566         }
 567
 568         d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx);
 569         d->nrdnlen[1] = nrlen & 0xff;
 570         d->nrdnlen[0] = (nrlen >> 8) | 0x80;
 571         ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
 572         *ptr++ = '\0';
 573         ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
 574         *ptr++ = '\0';
 575         BDB_ID2DISK( e->e_id, ptr );
 576
 577         DBTzero(&key);
 578         DBTzero(&data);
 579         key.size = sizeof(ID);
 580         key.flags = DB_DBT_USERMEM;
 581         BDB_ID2DISK( eip->bei_id, &nid );
 582
 583         key.data = &nid;
 584
 585         /* Need to make dummy root node once. Subsequent attempts
 586          * will fail harmlessly.
 587          */
 588         if ( eip->bei_id == 0 ) {
 589                 diskNode dummy = {{0, 0}, "", "", ""};
 590                 data.data = &dummy;
 591                 data.size = sizeof(diskNode);
 592                 data.flags = DB_DBT_USERMEM;
 593
 594                 db->put( db, txn, &key, &data, DB_NODUPDATA );
 595         }
 596
 597         data.data = d;
 598         data.size = sizeof(diskNode) + rlen + nrlen;
 599         data.flags = DB_DBT_USERMEM;
 600
 601         rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
 602
 603         if (rc == 0) {
 604                 BDB_ID2DISK( e->e_id, &nid );
 605                 BDB_ID2DISK( eip->bei_id, ptr );
 606                 d->nrdnlen[0] ^= 0x80;
 607
 608                 rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
 609         }
 610
 611         /* Update all parents' IDL cache entries */
 612         if ( rc == 0 && bdb->bi_idl_cache_size ) {
 613                 ID tmp[2];
 614                 char *ptr = ((char *)&tmp[1])-1;
 615                 key.data = ptr;
 616                 key.size = sizeof(ID)+1;
 617                 tmp[1] = eip->bei_id;
 618                 *ptr = DN_ONE_PREFIX;
 619                 bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
 620                 if ( eip->bei_parent ) {
 621                         *ptr = DN_SUBTREE_PREFIX;
 622                         for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
 623                                 tmp[1] = eip->bei_id;
 624                                 bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
 625                         }
 626                         /* Handle DB with empty suffix */
 627                         if ( !op->o_bd->be_suffix[0].bv_len && eip ) {
 628                                 tmp[1] = eip->bei_id;
 629                                 bdb_idl_cache_add_id( bdb, db, &key, e->e_id );
 630                         }
 631                 }
 632         }
 633
 634         op->o_tmpfree( d, op->o_tmpmemctx );
 635         Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
 636
 637         return rc;
 638 }
 639
 640 int
 641 hdb_dn2id_delete(
 642         Operation       *op,
 643         DB_TXN *txn,
 644         EntryInfo       *eip,
 645         Entry   *e )
 646 {
 647         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 648         DB *db = bdb->bi_dn2id->bdi_db;
 649         DBT             key, data;
 650         DBC     *cursor;
 651         diskNode *d;
 652         int rc;
 653         ID      nid;
 654         unsigned char dlen[2];
 655         DB_LOCK lock;
 656
 657         Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_delete 0x%lx: \"%s\"\n",
 658                 e->e_id, e->e_ndn, 0 );
 659
 660         DBTzero(&key);
 661         key.size = sizeof(ID);
 662         key.ulen = key.size;
 663         key.flags = DB_DBT_USERMEM;
 664         BDB_ID2DISK( eip->bei_id, &nid );
 665
 666         DBTzero(&data);
 667         data.size = sizeof(diskNode) + BEI(e)->bei_nrdn.bv_len - sizeof(ID) - 1;
 668         data.ulen = data.size;
 669         data.dlen = data.size;
 670         data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 671
 672         key.data = &nid;
 673
 674         d = op->o_tmpalloc( data.size, op->o_tmpmemctx );
 675         d->nrdnlen[1] = BEI(e)->bei_nrdn.bv_len & 0xff;
 676         d->nrdnlen[0] = (BEI(e)->bei_nrdn.bv_len >> 8) | 0x80;
 677         dlen[0] = d->nrdnlen[0];
 678         dlen[1] = d->nrdnlen[1];
 679         strcpy( d->nrdn, BEI(e)->bei_nrdn.bv_val );
 680         data.data = d;
 681
 682         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 683         if ( rc ) goto func_leave;
 684
 685         /* We hold this lock until the TXN completes */
 686         rc = bdb_dn2id_lock( bdb, &e->e_nname, 1, txn, &lock );
 687         if ( rc ) goto nolock;
 688
 689         /* Delete our ID from the parent's list */
 690         rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
 691         if ( rc == 0 ) {
 692                 if ( dlen[1] == d->nrdnlen[1] && dlen[0] == d->nrdnlen[0] &&
 693                         !strcmp( d->nrdn, BEI(e)->bei_nrdn.bv_val ))
 694                         rc = cursor->c_del( cursor, 0 );
 695                 else
 696                         rc = DB_NOTFOUND;
 697         }
 698
 699         /* Delete our ID from the tree. With sorted duplicates, this
 700          * will leave any child nodes still hanging around. This is OK
 701          * for modrdn, which will add our info back in later.
 702          */
 703         if ( rc == 0 ) {
 704                 BDB_ID2DISK( e->e_id, &nid );
 705                 rc = cursor->c_get( cursor, &key, &data, DB_SET );
 706                 if ( rc == 0 )
 707                         rc = cursor->c_del( cursor, 0 );
 708         }
 709
 710 nolock:
 711         cursor->c_close( cursor );
 712 func_leave:
 713         op->o_tmpfree( d, op->o_tmpmemctx );
 714
 715         /* Delete IDL cache entries */
 716         if ( rc == 0 && bdb->bi_idl_cache_size ) {
 717                 ID tmp[2];
 718                 char *ptr = ((char *)&tmp[1])-1;
 719                 key.data = ptr;
 720                 key.size = sizeof(ID)+1;
 721                 tmp[1] = eip->bei_id;
 722                 *ptr = DN_ONE_PREFIX;
 723                 bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
 724                 if ( eip ->bei_parent ) {
 725                         *ptr = DN_SUBTREE_PREFIX;
 726                         for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) {
 727                                 tmp[1] = eip->bei_id;
 728                                 bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
 729                         }
 730                         /* Handle DB with empty suffix */
 731                         if ( !op->o_bd->be_suffix[0].bv_len && eip ) {
 732                                 tmp[1] = eip->bei_id;
 733                                 bdb_idl_cache_del_id( bdb, db, &key, e->e_id );
 734                         }
 735                 }
 736         }
 737         Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
 738         return rc;
 739 }
 740
 741
 742 int
 743 hdb_dn2id(
 744         Operation       *op,
 745         struct berval   *in,
 746         EntryInfo       *ei,
 747         DB_TXN *txn,
 748         DB_LOCK *lock )
 749 {
 750         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 751         DB *db = bdb->bi_dn2id->bdi_db;
 752         DBT             key, data;
 753         DBC     *cursor;
 754         int             rc = 0, nrlen;
 755         diskNode *d;
 756         char    *ptr;
 757         unsigned char dlen[2];
 758         ID idp, parentID;
 759
 760         Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id(\"%s\")\n", in->bv_val, 0, 0 );
 761
 762         nrlen = dn_rdnlen( op->o_bd, in );
 763         if (!nrlen) nrlen = in->bv_len;
 764
 765         DBTzero(&key);
 766         key.size = sizeof(ID);
 767         key.data = &idp;
 768         key.ulen = sizeof(ID);
 769         key.flags = DB_DBT_USERMEM;
 770         parentID = ( ei->bei_parent != NULL ) ? ei->bei_parent->bei_id : 0;
 771         BDB_ID2DISK( parentID, &idp );
 772
 773         DBTzero(&data);
 774         data.size = sizeof(diskNode) + nrlen - sizeof(ID) - 1;
 775         data.ulen = data.size * 3;
 776         data.dlen = data.ulen;
 777         data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 778
 779         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 780         if ( rc ) return rc;
 781
 782         d = op->o_tmpalloc( data.size * 3, op->o_tmpmemctx );
 783         d->nrdnlen[1] = nrlen & 0xff;
 784         d->nrdnlen[0] = (nrlen >> 8) | 0x80;
 785         dlen[0] = d->nrdnlen[0];
 786         dlen[1] = d->nrdnlen[1];
 787         ptr = lutil_strncopy( d->nrdn, in->bv_val, nrlen );
 788         *ptr = '\0';
 789         data.data = d;
 790
 791         rc = bdb_dn2id_lock( bdb, in, 0, txn, lock );
 792         if ( rc ) goto func_leave;
 793
 794         rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE );
 795         if ( rc == 0 && (dlen[1] != d->nrdnlen[1] || dlen[0] != d->nrdnlen[0] ||
 796                 strncmp( d->nrdn, in->bv_val, nrlen ))) {
 797                 rc = DB_NOTFOUND;
 798         }
 799         if ( rc == 0 ) {
 800                 ptr = (char *) data.data + data.size - sizeof(ID);
 801                 BDB_DISK2ID( ptr, &ei->bei_id );
 802                 ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - nrlen;
 803                 ptr = d->nrdn + nrlen + 1;
 804                 ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
 805                 if ( ei->bei_parent != NULL && !ei->bei_parent->bei_dkids ) {
 806                         db_recno_t dkids;
 807                         /* How many children does the parent have? */
 808                         /* FIXME: do we need to lock the parent
 809                          * entryinfo? Seems safe...
 810                          */
 811                         cursor->c_count( cursor, &dkids, 0 );
 812                         ei->bei_parent->bei_dkids = dkids;
 813                 }
 814         }
 815
 816 func_leave:
 817         cursor->c_close( cursor );
 818         op->o_tmpfree( d, op->o_tmpmemctx );
 819         if( rc != 0 ) {
 820                 Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: get failed: %s (%d)\n",
 821                         db_strerror( rc ), rc, 0 );
 822         } else {
 823                 Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: got id=0x%lx\n",
 824                         ei->bei_id, 0, 0 );
 825         }
 826
 827         return rc;
 828 }
 829
 830 int
 831 hdb_dn2id_parent(
 832         Operation *op,
 833         DB_TXN *txn,
 834         EntryInfo *ei,
 835         ID *idp )
 836 {
 837         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 838         DB *db = bdb->bi_dn2id->bdi_db;
 839         DBT             key, data;
 840         DBC     *cursor;
 841         int             rc = 0;
 842         diskNode *d;
 843         char    *ptr;
 844         ID      nid;
 845
 846         DBTzero(&key);
 847         key.size = sizeof(ID);
 848         key.data = &nid;
 849         key.ulen = sizeof(ID);
 850         key.flags = DB_DBT_USERMEM;
 851         BDB_ID2DISK( ei->bei_id, &nid );
 852
 853         DBTzero(&data);
 854         data.flags = DB_DBT_USERMEM;
 855
 856         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 857         if ( rc ) return rc;
 858
 859         data.ulen = sizeof(diskNode) + (SLAP_LDAPDN_MAXLEN * 2);
 860         d = op->o_tmpalloc( data.ulen, op->o_tmpmemctx );
 861         data.data = d;
 862
 863         rc = cursor->c_get( cursor, &key, &data, DB_SET );
 864         if ( rc == 0 ) {
 865                 if (d->nrdnlen[0] & 0x80) {
 866                         rc = LDAP_OTHER;
 867                 } else {
 868                         db_recno_t dkids;
 869                         ptr = (char *) data.data + data.size - sizeof(ID);
 870                         BDB_DISK2ID( ptr, idp );
 871                         ei->bei_nrdn.bv_len = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
 872                         ber_str2bv( d->nrdn, ei->bei_nrdn.bv_len, 1, &ei->bei_nrdn );
 873                         ei->bei_rdn.bv_len = data.size - sizeof(diskNode) -
 874                                 ei->bei_nrdn.bv_len;
 875                         ptr = d->nrdn + ei->bei_nrdn.bv_len + 1;
 876                         ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
 877                         /* How many children does this node have? */
 878                         cursor->c_count( cursor, &dkids, 0 );
 879                         ei->bei_dkids = dkids;
 880                 }
 881         }
 882         cursor->c_close( cursor );
 883         op->o_tmpfree( d, op->o_tmpmemctx );
 884         return rc;
 885 }
 886
 887 int
 888 hdb_dn2id_children(
 889         Operation *op,
 890         DB_TXN *txn,
 891         Entry *e )
 892 {
 893         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 894         DB *db = bdb->bi_dn2id->bdi_db;
 895         DBT             key, data;
 896         DBC             *cursor;
 897         int             rc;
 898         ID              id;
 899         diskNode d;
 900
 901         DBTzero(&key);
 902         key.size = sizeof(ID);
 903         key.data = &e->e_id;
 904         key.flags = DB_DBT_USERMEM;
 905         BDB_ID2DISK( e->e_id, &id );
 906
 907         /* IDL cache is in host byte order */
 908         if ( bdb->bi_idl_cache_size ) {
 909                 rc = bdb_idl_cache_get( bdb, db, &key, NULL );
 910                 if ( rc != LDAP_NO_SUCH_OBJECT ) {
 911                         return rc;
 912                 }
 913         }
 914
 915         key.data = &id;
 916         DBTzero(&data);
 917         data.data = &d;
 918         data.ulen = sizeof(d);
 919         data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 920         data.dlen = sizeof(d);
 921
 922         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 923         if ( rc ) return rc;
 924
 925         rc = cursor->c_get( cursor, &key, &data, DB_SET );
 926         if ( rc == 0 ) {
 927                 db_recno_t dkids;
 928                 rc = cursor->c_count( cursor, &dkids, 0 );
 929                 if ( rc == 0 ) {
 930                         BEI(e)->bei_dkids = dkids;
 931                         if ( dkids < 2 ) rc = DB_NOTFOUND;
 932                 }
 933         }
 934         cursor->c_close( cursor );
 935         return rc;
 936 }
 937
 938 /* bdb_dn2idl:
 939  * We can't just use bdb_idl_fetch_key because
 940  * 1 - our data items are longer than just an entry ID
 941  * 2 - our data items are sorted alphabetically by nrdn, not by ID.
 942  *
 943  * We descend the tree recursively, so we define this cookie
 944  * to hold our necessary state information. The bdb_dn2idl_internal
 945  * function uses this cookie when calling itself.
 946  */
 947
 948 struct dn2id_cookie {
 949         struct bdb_info *bdb;
 950         Operation *op;
 951         DB_TXN *txn;
 952         EntryInfo *ei;
 953         ID *ids;
 954         ID *tmp;
 955         ID *buf;
 956         DB *db;
 957         DBC *dbc;
 958         DBT key;
 959         DBT data;
 960         ID dbuf;
 961         ID id;
 962         ID nid;
 963         int rc;
 964         int depth;
 965         char need_sort;
 966         char prefix;
 967 };
 968
 969 static int
 970 apply_func(
 971         void *data,
 972         void *arg )
 973 {
 974         EntryInfo *ei = data;
 975         ID *idl = arg;
 976
 977         bdb_idl_append_one( idl, ei->bei_id );
 978         return 0;
 979 }
 980
 981 static int
 982 hdb_dn2idl_internal(
 983         struct dn2id_cookie *cx
 984 )
 985 {
 986         BDB_IDL_ZERO( cx->tmp );
 987
 988         if ( cx->bdb->bi_idl_cache_size ) {
 989                 char *ptr = ((char *)&cx->id)-1;
 990
 991                 cx->key.data = ptr;
 992                 cx->key.size = sizeof(ID)+1;
 993                 if ( cx->prefix == DN_SUBTREE_PREFIX ) {
 994                         ID *ids = cx->depth ? cx->tmp : cx->ids;
 995                         *ptr = cx->prefix;
 996                         cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, ids);
 997                         if ( cx->rc == LDAP_SUCCESS ) {
 998                                 if ( cx->depth ) {
 999                                         bdb_idl_append( cx->ids, cx->tmp );
1000                                         cx->need_sort = 1;
1001                                 }
1002                                 return cx->rc;
1003                         }
1004                 }
1005                 *ptr = DN_ONE_PREFIX;
1006                 cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, cx->tmp);
1007                 if ( cx->rc == LDAP_SUCCESS ) {
1008                         goto gotit;
1009                 }
1010                 if ( cx->rc == DB_NOTFOUND ) {
1011                         return cx->rc;
1012                 }
1013         }
1014
1015         bdb_cache_entryinfo_lock( cx->ei );
1016
1017         /* If number of kids in the cache differs from on-disk, load
1018          * up all the kids from the database
1019          */
1020         if ( cx->ei->bei_ckids+1 != cx->ei->bei_dkids ) {
1021                 EntryInfo ei;
1022                 db_recno_t dkids = cx->ei->bei_dkids;
1023                 ei.bei_parent = cx->ei;
1024
1025                 /* Only one thread should load the cache */
1026                 while ( cx->ei->bei_state & CACHE_ENTRY_ONELEVEL ) {
1027                         bdb_cache_entryinfo_unlock( cx->ei );
1028                         ldap_pvt_thread_yield();
1029                         bdb_cache_entryinfo_lock( cx->ei );
1030                         if ( cx->ei->bei_ckids+1 == cx->ei->bei_dkids ) {
1031                                 goto synced;
1032                         }
1033                 }
1034
1035                 cx->ei->bei_state |= CACHE_ENTRY_ONELEVEL;
1036
1037                 bdb_cache_entryinfo_unlock( cx->ei );
1038
1039                 cx->rc = cx->db->cursor( cx->db, NULL, &cx->dbc,
1040                         cx->bdb->bi_db_opflags );
1041                 if ( cx->rc )
1042                         goto done_one;
1043
1044                 cx->data.data = &cx->dbuf;
1045                 cx->data.ulen = sizeof(ID);
1046                 cx->data.dlen = sizeof(ID);
1047                 cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
1048
1049                 /* The first item holds the parent ID. Ignore it. */
1050                 cx->key.data = &cx->nid;
1051                 cx->key.size = sizeof(ID);
1052                 cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET );
1053                 if ( cx->rc ) {
1054                         cx->dbc->c_close( cx->dbc );
1055                         goto done_one;
1056                 }
1057
1058                 /* If the on-disk count is zero we've never checked it.
1059                  * Count it now.
1060                  */
1061                 if ( !dkids ) {
1062                         cx->dbc->c_count( cx->dbc, &dkids, 0 );
1063                         cx->ei->bei_dkids = dkids;
1064                 }
1065
1066                 cx->data.data = cx->buf;
1067                 cx->data.ulen = BDB_IDL_UM_SIZE * sizeof(ID);
1068                 cx->data.flags = DB_DBT_USERMEM;
1069
1070                 if ( dkids > 1 ) {
1071                         /* Fetch the rest of the IDs in a loop... */
1072                         while ( (cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data,
1073                                 DB_MULTIPLE | DB_NEXT_DUP )) == 0 ) {
1074                                 u_int8_t *j;
1075                                 size_t len;
1076                                 void *ptr;
1077                                 DB_MULTIPLE_INIT( ptr, &cx->data );
1078                                 while (ptr) {
1079                                         DB_MULTIPLE_NEXT( ptr, &cx->data, j, len );
1080                                         if (j) {
1081                                                 EntryInfo *ei2;
1082                                                 diskNode *d = (diskNode *)j;
1083                                                 short nrlen;
1084
1085                                                 BDB_DISK2ID( j + len - sizeof(ID), &ei.bei_id );
1086                                                 nrlen = ((d->nrdnlen[0] ^ 0x80) << 8) | d->nrdnlen[1];
1087                                                 ei.bei_nrdn.bv_len = nrlen;
1088                                                 /* nrdn/rdn are set in-place.
1089                                                  * hdb_cache_load will copy them as needed
1090                                                  */
1091                                                 ei.bei_nrdn.bv_val = d->nrdn;
1092                                                 ei.bei_rdn.bv_len = len - sizeof(diskNode)
1093                                                         - ei.bei_nrdn.bv_len;
1094                                                 ei.bei_rdn.bv_val = d->nrdn + ei.bei_nrdn.bv_len + 1;
1095                                                 bdb_idl_append_one( cx->tmp, ei.bei_id );
1096                                                 hdb_cache_load( cx->bdb, &ei, &ei2 );
1097                                         }
1098                                 }
1099                         }
1100                 }
1101
1102                 cx->rc = cx->dbc->c_close( cx->dbc );
1103 done_one:
1104                 bdb_cache_entryinfo_lock( cx->ei );
1105                 cx->ei->bei_state &= ~CACHE_ENTRY_ONELEVEL;
1106                 bdb_cache_entryinfo_unlock( cx->ei );
1107                 if ( cx->rc )
1108                         return cx->rc;
1109
1110         } else {
1111                 /* The in-memory cache is in sync with the on-disk data.
1112                  * do we have any kids?
1113                  */
1114 synced:
1115                 cx->rc = 0;
1116                 if ( cx->ei->bei_ckids > 0 ) {
1117                         /* Walk the kids tree; order is irrelevant since bdb_idl_sort
1118                          * will sort it later.
1119                          */
1120                         avl_apply( cx->ei->bei_kids, apply_func,
1121                                 cx->tmp, -1, AVL_POSTORDER );
1122                 }
1123                 bdb_cache_entryinfo_unlock( cx->ei );
1124         }
1125
1126         if ( !BDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 3 )
1127                 bdb_idl_sort( cx->tmp, cx->buf );
1128         if ( cx->bdb->bi_idl_cache_max_size && !BDB_IDL_IS_ZERO( cx->tmp )) {
1129                 char *ptr = ((char *)&cx->id)-1;
1130                 cx->key.data = ptr;
1131                 cx->key.size = sizeof(ID)+1;
1132                 *ptr = DN_ONE_PREFIX;
1133                 bdb_idl_cache_put( cx->bdb, cx->db, &cx->key, cx->tmp, cx->rc );
1134         }
1135
1136 gotit:
1137         if ( !BDB_IDL_IS_ZERO( cx->tmp )) {
1138                 if ( cx->prefix == DN_SUBTREE_PREFIX ) {
1139                         bdb_idl_append( cx->ids, cx->tmp );
1140                         cx->need_sort = 1;
1141                         if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) {
1142                                 ID *save, idcurs;
1143                                 EntryInfo *ei = cx->ei;
1144                                 int nokids = 1;
1145                                 save = cx->op->o_tmpalloc( BDB_IDL_SIZEOF( cx->tmp ),
1146                                         cx->op->o_tmpmemctx );
1147                                 BDB_IDL_CPY( save, cx->tmp );
1148
1149                                 idcurs = 0;
1150                                 cx->depth++;
1151                                 for ( cx->id = bdb_idl_first( save, &idcurs );
1152                                         cx->id != NOID;
1153                                         cx->id = bdb_idl_next( save, &idcurs )) {
1154                                         EntryInfo *ei2;
1155                                         cx->ei = NULL;
1156                                         if ( bdb_cache_find_id( cx->op, cx->txn, cx->id, &cx->ei,
1157                                                 ID_NOENTRY, NULL ))
1158                                                 continue;
1159                                         if ( cx->ei ) {
1160                                                 ei2 = cx->ei;
1161                                                 if ( !( ei2->bei_state & CACHE_ENTRY_NO_KIDS )) {
1162                                                         BDB_ID2DISK( cx->id, &cx->nid );
1163                                                         hdb_dn2idl_internal( cx );
1164                                                         if ( !BDB_IDL_IS_ZERO( cx->tmp ))
1165                                                                 nokids = 0;
1166                                                 }
1167                                                 bdb_cache_entryinfo_lock( ei2 );
1168                                                 ei2->bei_finders--;
1169                                                 bdb_cache_entryinfo_unlock( ei2 );
1170                                         }
1171                                 }
1172                                 cx->depth--;
1173                                 cx->op->o_tmpfree( save, cx->op->o_tmpmemctx );
1174                                 if ( nokids ) {
1175                                         bdb_cache_entryinfo_lock( ei );
1176                                         ei->bei_state |= CACHE_ENTRY_NO_GRANDKIDS;
1177                                         bdb_cache_entryinfo_unlock( ei );
1178                                 }
1179                         }
1180                         /* Make sure caller knows it had kids! */
1181                         cx->tmp[0]=1;
1182
1183                         cx->rc = 0;
1184                 } else {
1185                         BDB_IDL_CPY( cx->ids, cx->tmp );
1186                 }
1187         }
1188         return cx->rc;
1189 }
1190
1191 int
1192 hdb_dn2idl(
1193         Operation       *op,
1194         DB_TXN *txn,
1195         struct berval *ndn,
1196         EntryInfo       *ei,
1197         ID *ids,
1198         ID *stack )
1199 {
1200         struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private;
1201         struct dn2id_cookie cx;
1202
1203         Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2idl(\"%s\")\n",
1204                 ndn->bv_val, 0, 0 );
1205
1206 #ifndef BDB_MULTIPLE_SUFFIXES
1207         if ( op->ors_scope != LDAP_SCOPE_ONELEVEL &&
1208                 ( ei->bei_id == 0 ||
1209                 ( ei->bei_parent->bei_id == 0 && op->o_bd->be_suffix[0].bv_len )))
1210         {
1211                 BDB_IDL_ALL( bdb, ids );
1212                 return 0;
1213         }
1214 #endif
1215
1216         cx.id = ei->bei_id;
1217         BDB_ID2DISK( cx.id, &cx.nid );
1218         cx.ei = ei;
1219         cx.bdb = bdb;
1220         cx.db = cx.bdb->bi_dn2id->bdi_db;
1221         cx.prefix = (op->ors_scope == LDAP_SCOPE_ONELEVEL) ?
1222                 DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
1223         cx.ids = ids;
1224         cx.tmp = stack;
1225         cx.buf = stack + BDB_IDL_UM_SIZE;
1226         cx.op = op;
1227         cx.txn = txn;
1228         cx.need_sort = 0;
1229         cx.depth = 0;
1230
1231         if ( cx.prefix == DN_SUBTREE_PREFIX ) {
1232                 ids[0] = 1;
1233                 ids[1] = cx.id;
1234         } else {
1235                 BDB_IDL_ZERO( ids );
1236         }
1237         if ( cx.ei->bei_state & CACHE_ENTRY_NO_KIDS )
1238                 return LDAP_SUCCESS;
1239
1240         DBTzero(&cx.key);
1241         cx.key.ulen = sizeof(ID);
1242         cx.key.size = sizeof(ID);
1243         cx.key.flags = DB_DBT_USERMEM;
1244
1245         DBTzero(&cx.data);
1246
1247         hdb_dn2idl_internal(&cx);
1248         if ( cx.need_sort ) {
1249                 char *ptr = ((char *)&cx.id)-1;
1250                 if ( !BDB_IDL_IS_RANGE( cx.ids ) && cx.ids[0] > 3 )
1251                         bdb_idl_sort( cx.ids, cx.tmp );
1252                 cx.key.data = ptr;
1253                 cx.key.size = sizeof(ID)+1;
1254                 *ptr = cx.prefix;
1255                 cx.id = ei->bei_id;
1256                 if ( cx.bdb->bi_idl_cache_max_size )
1257                         bdb_idl_cache_put( cx.bdb, cx.db, &cx.key, cx.ids, cx.rc );
1258         }
1259
1260         if ( cx.rc == DB_NOTFOUND )
1261                 cx.rc = LDAP_SUCCESS;
1262
1263         return cx.rc;
1264 }
1265 #endif  /* BDB_HIER */