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