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