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