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