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