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 #ifdef SLAP_IDL_CACHE
 387         if ( bdb->bi_idl_cache_size ) {
 388                 rc = bdb_idl_cache_get( bdb, db, &key, NULL );
 389                 if ( rc != LDAP_NO_SUCH_OBJECT ) {
 390                         op->o_tmpfree( key.data, op->o_tmpmemctx );
 391                         return rc;
 392                 }
 393         }
 394 #endif
 395         /* we actually could do a empty get... */
 396         DBTzero( &data );
 397         data.data = &id;
 398         data.ulen = sizeof(id);
 399         data.flags = DB_DBT_USERMEM;
 400         data.doff = 0;
 401         data.dlen = sizeof(id);
 402
 403         rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags );
 404         op->o_tmpfree( key.data, op->o_tmpmemctx );
 405
 406 #ifdef NEW_LOGGING
 407         LDAP_LOG ( INDEX, DETAIL1,
 408                 "<= bdb_dn2id_children( %s ): %s (%d)\n",
 409                 e->e_nname.bv_val, rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
 410                 db_strerror(rc)), rc );
 411 #else
 412         Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children( %s ): %s (%d)\n",
 413                 e->e_nname.bv_val,
 414                 rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " :
 415                         db_strerror(rc) ), rc );
 416 #endif
 417
 418         return rc;
 419 }
 420
 421 int
 422 bdb_dn2idl(
 423         Operation *op,
 424         Entry *e,
 425         ID *ids,
 426         ID *stack )
 427 {
 428         int             rc;
 429         DBT             key;
 430         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 431         DB *db = bdb->bi_dn2id->bdi_db;
 432         int prefix = ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
 433                 ? DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
 434
 435 #ifdef NEW_LOGGING
 436         LDAP_LOG ( INDEX, ARGS, "=> bdb_dn2ididl( \"%s\" )\n",
 437                 e->e_nname.bv_val, 0, 0 );
 438 #else
 439         Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl( \"%s\" )\n",
 440                 e->e_nname.bv_val, 0, 0 );
 441 #endif
 442
 443 #ifndef BDB_MULTIPLE_SUFFIXES
 444         if ( prefix == DN_SUBTREE_PREFIX && BEI(e)->bei_parent->bei_id == 0 ) {
 445                 BDB_IDL_ALL(bdb, ids);
 446                 return 0;
 447         }
 448 #endif
 449
 450         DBTzero( &key );
 451         key.size = e->e_nname.bv_len + 2;
 452         key.ulen = key.size;
 453         key.flags = DB_DBT_USERMEM;
 454         key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx );
 455         ((char *)key.data)[0] = prefix;
 456         AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 );
 457
 458         rc = bdb_idl_fetch_key( op->o_bd, db, NULL, &key, ids );
 459
 460         if( rc != 0 ) {
 461 #ifdef NEW_LOGGING
 462                 LDAP_LOG ( INDEX, ERR,
 463                         "<= bdb_dn2ididl: get failed: %s (%d)\n", db_strerror(rc), rc, 0 );
 464 #else
 465                 Debug( LDAP_DEBUG_TRACE,
 466                         "<= bdb_dn2idl: get failed: %s (%d)\n",
 467                         db_strerror( rc ), rc, 0 );
 468 #endif
 469
 470         } else {
 471 #ifdef NEW_LOGGING
 472                 LDAP_LOG ( INDEX, RESULTS,
 473                         "<= bdb_dn2ididl: id=%ld first=%ld last=%ld\n",
 474                         (long) ids[0], (long) BDB_IDL_FIRST( ids ),
 475                         (long) BDB_IDL_LAST( ids ) );
 476 #else
 477                 Debug( LDAP_DEBUG_TRACE,
 478                         "<= bdb_dn2idl: id=%ld first=%ld last=%ld\n",
 479                         (long) ids[0],
 480                         (long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) );
 481 #endif
 482         }
 483
 484         op->o_tmpfree( key.data, op->o_tmpmemctx );
 485         return rc;
 486 }
 487
 488 #else   /* BDB_HIER */
 489 /* Experimental management routines for a hierarchically structured database.
 490  *
 491  * Unsupported! Use at your own risk!
 492  * -- Howard Chu, Symas Corp. 2003.
 493  *
 494  * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each
 495  * entry in this database is a struct diskNode, keyed by entryID and with
 496  * the data containing the RDN and entryID of the node's children. We use
 497  * a B-Tree with sorted duplicates to store all the children of a node under
 498  * the same key. Also, the first item under the key contains the entry's own
 499  * rdn and the ID of the node's parent, to allow bottom-up tree traversal as
 500  * well as top-down. To keep this info first in the list, the nrdnlen is set
 501  * to the negative of its value.
 502  *
 503  * The diskNode is a variable length structure. This definition is not
 504  * directly usable for in-memory manipulation.
 505  */
 506 typedef struct diskNode {
 507         ID entryID;
 508         short nrdnlen;
 509         char nrdn[1];
 510         char rdn[1];
 511 } diskNode;
 512
 513 /* Sort function for the sorted duplicate data items of a dn2id key.
 514  * Sorts based on normalized RDN, in length order.
 515  */
 516 int
 517 hdb_dup_compare(
 518         DB *db,
 519         const DBT *usrkey,
 520         const DBT *curkey )
 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         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         /* Need to make dummy root node once. Subsequent attempts
 633          * will fail harmlessly.
 634          */
 635         if ( eip->bei_id == 0 ) {
 636                 diskNode dummy = {0};
 637                 data.data = &dummy;
 638                 data.size = sizeof(diskNode);
 639                 data.flags = DB_DBT_USERMEM;
 640
 641                 db->put( db, txn, &key, &data, DB_NODUPDATA );
 642         }
 643
 644 #ifdef SLAP_IDL_CACHE
 645         if ( bdb->bi_idl_cache_size ) {
 646                 bdb_idl_cache_del( bdb, db, &key );
 647         }
 648 #endif
 649         data.data = d;
 650         data.size = sizeof(diskNode) + rlen + nrlen;
 651         data.flags = DB_DBT_USERMEM;
 652
 653         rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
 654
 655         if (rc == 0) {
 656                 key.data = &e->e_id;
 657                 d->entryID = eip->bei_id;
 658                 d->nrdnlen = 0 - nrlen;
 659
 660                 rc = db->put( db, txn, &key, &data, DB_NODUPDATA );
 661         }
 662
 663         op->o_tmpfree( d, op->o_tmpmemctx );
 664
 665         return rc;
 666 }
 667
 668 int
 669 hdb_dn2id_delete(
 670         Operation       *op,
 671         DB_TXN *txn,
 672         EntryInfo       *eip,
 673         Entry   *e )
 674 {
 675         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 676         DB *db = bdb->bi_dn2id->bdi_db;
 677         DBT             key, data;
 678         DBC     *cursor;
 679         diskNode *d;
 680         int rc, nrlen;
 681
 682         DBTzero(&key);
 683         key.size = sizeof(ID);
 684         key.ulen = key.size;
 685         key.data = &eip->bei_id;
 686         key.flags = DB_DBT_USERMEM;
 687
 688         DBTzero(&data);
 689         data.size = sizeof(diskNode) + BEI(e)->bei_nrdn.bv_len;
 690         data.ulen = data.size;
 691         data.dlen = data.size;
 692         data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 693
 694 #ifdef SLAP_IDL_CACHE
 695         if ( bdb->bi_idl_cache_size ) {
 696                 bdb_idl_cache_del( bdb, db, &key );
 697         }
 698 #endif
 699         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 700         if ( rc ) return rc;
 701
 702         d = op->o_tmpalloc( data.size, op->o_tmpmemctx );
 703         d->entryID = e->e_id;
 704         d->nrdnlen = BEI(e)->bei_nrdn.bv_len;
 705         strcpy( d->nrdn, BEI(e)->bei_nrdn.bv_val );
 706         data.data = d;
 707
 708         /* Delete our ID from the parent's list */
 709         rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH | DB_RMW );
 710         if ( rc == 0 )
 711                 rc = cursor->c_del( cursor, 0 );
 712
 713         /* Delete our ID from the tree. With sorted duplicates, this
 714          * will leave any child nodes still hanging around. This is OK
 715          * for modrdn, which will add our info back in later.
 716          */
 717         if ( rc == 0 ) {
 718                 key.data = &e->e_id;
 719                 rc = cursor->c_get( cursor, &key, &data, DB_SET | DB_RMW );
 720                 if ( rc == 0 )
 721                         rc = cursor->c_del( cursor, 0 );
 722         }
 723         cursor->c_close( cursor );
 724         op->o_tmpfree( d, op->o_tmpmemctx );
 725
 726         return rc;
 727 }
 728
 729
 730 int
 731 hdb_dn2id(
 732         Operation       *op,
 733         DB_TXN *txn,
 734         struct berval   *in,
 735         EntryInfo       *ei )
 736 {
 737         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 738         DB *db = bdb->bi_dn2id->bdi_db;
 739         DBT             key, data;
 740         DBC     *cursor;
 741         int             rc = 0, nrlen;
 742         diskNode *d;
 743         char    *ptr;
 744         ID idp = ei->bei_parent->bei_id;
 745
 746         nrlen = dn_rdnlen( op->o_bd, in );
 747         if (!nrlen) nrlen = in->bv_len;
 748
 749         DBTzero(&key);
 750         key.size = sizeof(ID);
 751         key.data = &idp;
 752         key.ulen = sizeof(ID);
 753         key.flags = DB_DBT_USERMEM;
 754
 755         DBTzero(&data);
 756         data.size = sizeof(diskNode) + nrlen;
 757         data.ulen = data.size * 3;
 758         data.flags = DB_DBT_USERMEM;
 759
 760         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 761         if ( rc ) return rc;
 762
 763         d = op->o_tmpalloc( data.size * 3, op->o_tmpmemctx );
 764         d->nrdnlen = nrlen;
 765         ptr = lutil_strncopy( d->nrdn, in->bv_val, nrlen );
 766         *ptr = '\0';
 767         data.data = d;
 768
 769         rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH );
 770         if ( rc == 0 ) {
 771                 ei->bei_id = d->entryID;
 772                 ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - nrlen;
 773                 ptr = d->nrdn + nrlen + 1;
 774                 ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
 775                 if ( !ei->bei_parent->bei_dkids ) {
 776                         db_recno_t dkids;
 777                         /* How many children does the parent have? */
 778                         /* FIXME: do we need to lock the parent
 779                          * entryinfo? Seems safe...
 780                          */
 781                         cursor->c_count( cursor, &dkids, 0 );
 782                         ei->bei_parent->bei_dkids = dkids;
 783                 }
 784         }
 785         cursor->c_close( cursor );
 786         op->o_tmpfree( d, op->o_tmpmemctx );
 787
 788         return rc;
 789 }
 790
 791 int
 792 hdb_dn2id_parent(
 793         Operation *op,
 794         DB_TXN *txn,
 795         EntryInfo *ei,
 796         ID *idp )
 797 {
 798         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 799         DB *db = bdb->bi_dn2id->bdi_db;
 800         DBT             key, data;
 801         DBC     *cursor;
 802         int             rc = 0;
 803         diskNode *d;
 804         char    *ptr;
 805         unsigned char *pt2;
 806
 807         DBTzero(&key);
 808         key.size = sizeof(ID);
 809         key.data = &ei->bei_id;
 810         key.ulen = sizeof(ID);
 811         key.flags = DB_DBT_USERMEM;
 812
 813         DBTzero(&data);
 814         data.flags = DB_DBT_USERMEM;
 815
 816         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 817         if ( rc ) return rc;
 818
 819         data.ulen = sizeof(diskNode) + (SLAP_LDAPDN_MAXLEN * 2);
 820         d = op->o_tmpalloc( data.ulen, op->o_tmpmemctx );
 821         data.data = d;
 822
 823         rc = cursor->c_get( cursor, &key, &data, DB_SET );
 824         if ( rc == 0 ) {
 825                 if (d->nrdnlen >= 0) {
 826                         rc = LDAP_OTHER;
 827                 } else {
 828                         db_recno_t dkids;
 829                         *idp = d->entryID;
 830                         ei->bei_nrdn.bv_len = 0 - d->nrdnlen;
 831                         ber_str2bv( d->nrdn, ei->bei_nrdn.bv_len, 1, &ei->bei_nrdn );
 832                         ei->bei_rdn.bv_len = data.size - sizeof(diskNode) -
 833                                 ei->bei_nrdn.bv_len;
 834                         ptr = d->nrdn + ei->bei_nrdn.bv_len + 1;
 835                         ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
 836                         /* How many children does this node have? */
 837                         cursor->c_count( cursor, &dkids, 0 );
 838                         ei->bei_dkids = dkids;
 839                 }
 840         }
 841         cursor->c_close( cursor );
 842         op->o_tmpfree( d, op->o_tmpmemctx );
 843         return rc;
 844 }
 845
 846 int
 847 hdb_dn2id_children(
 848         Operation *op,
 849         DB_TXN *txn,
 850         Entry *e )
 851 {
 852         struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private;
 853         DB *db = bdb->bi_dn2id->bdi_db;
 854         DBT             key, data;
 855         DBC             *cursor;
 856         int             rc;
 857         ID              id;
 858         diskNode d;
 859
 860         DBTzero(&key);
 861         key.size = sizeof(ID);
 862         key.data = &e->e_id;
 863         key.flags = DB_DBT_USERMEM;
 864
 865 #ifdef SLAP_IDL_CACHE
 866         if ( bdb->bi_idl_cache_size ) {
 867                 rc = bdb_idl_cache_get( bdb, db, &key, NULL );
 868                 if ( rc != LDAP_NO_SUCH_OBJECT ) {
 869                         return rc;
 870                 }
 871         }
 872 #endif
 873         DBTzero(&data);
 874         data.data = &d;
 875         data.ulen = sizeof(d);
 876         data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 877         data.dlen = sizeof(d);
 878
 879         rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags );
 880         if ( rc ) return rc;
 881
 882         rc = cursor->c_get( cursor, &key, &data, DB_SET );
 883         if ( rc == 0 ) {
 884                 db_recno_t dkids;
 885                 rc = cursor->c_count( cursor, &dkids, 0 );
 886                 if ( rc == 0 ) {
 887                         BEI(e)->bei_dkids = dkids;
 888                         if ( dkids < 2 ) rc = DB_NOTFOUND;
 889                 }
 890         }
 891         cursor->c_close( cursor );
 892         return rc;
 893 }
 894
 895 /* bdb_dn2idl:
 896  * We can't just use bdb_idl_fetch_key because
 897  * 1 - our data items are longer than just an entry ID
 898  * 2 - our data items are sorted alphabetically by nrdn, not by ID.
 899  *
 900  * We descend the tree recursively, so we define this cookie
 901  * to hold our necessary state information. The bdb_dn2idl_internal
 902  * function uses this cookie when calling itself.
 903  */
 904
 905 struct dn2id_cookie {
 906         struct bdb_info *bdb;
 907         DB *db;
 908         int prefix;
 909         int rc;
 910         EntryInfo *ei;
 911         ID id;
 912         ID dbuf;
 913         ID *ids;
 914         void *ptr;
 915         ID tmp[BDB_IDL_DB_SIZE];
 916         ID *buf;
 917         DBT key;
 918         DBT data;
 919         DBC *dbc;
 920         Operation *op;
 921 };
 922
 923 static int
 924 apply_func(
 925         void *data,
 926         void *arg )
 927 {
 928         EntryInfo *ei = data;
 929         ID *idl = arg;
 930
 931         bdb_idl_insert( idl, ei->bei_id );
 932         return 0;
 933 }
 934
 935 static int
 936 hdb_dn2idl_internal(
 937         struct dn2id_cookie *cx
 938 )
 939 {
 940 #ifdef SLAP_IDL_CACHE
 941         if ( cx->bdb->bi_idl_cache_size ) {
 942                 cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, cx->tmp);
 943                 if ( cx->rc == DB_NOTFOUND ) {
 944                         return cx->rc;
 945                 }
 946                 if ( cx->rc == LDAP_SUCCESS ) {
 947                         goto gotit;
 948                 }
 949         }
 950 #endif
 951         BDB_IDL_ZERO( cx->tmp );
 952
 953         if ( !cx->ei ) {
 954                 cx->ei = bdb_cache_find_info( cx->bdb, cx->id );
 955                 if ( !cx->ei ) {
 956                         cx->rc = DB_NOTFOUND;
 957                         goto saveit;
 958                 }
 959         }
 960
 961         bdb_cache_entryinfo_lock( cx->ei );
 962
 963         /* If number of kids in the cache differs from on-disk, load
 964          * up all the kids from the database
 965          */
 966         if ( cx->ei->bei_ckids+1 != cx->ei->bei_dkids ) {
 967                 EntryInfo ei;
 968                 db_recno_t dkids = cx->ei->bei_dkids;
 969                 ei.bei_parent = cx->ei;
 970
 971                 bdb_cache_entryinfo_unlock( cx->ei );
 972
 973                 cx->rc = cx->db->cursor( cx->db, NULL, &cx->dbc,
 974                         cx->bdb->bi_db_opflags );
 975                 if ( cx->rc ) return cx->rc;
 976
 977                 cx->data.data = &cx->dbuf;
 978                 cx->data.ulen = sizeof(ID);
 979                 cx->data.dlen = sizeof(ID);
 980                 cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 981
 982                 /* The first item holds the parent ID. Ignore it. */
 983                 cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET );
 984                 if ( cx->rc ) {
 985                         cx->dbc->c_close( cx->dbc );
 986                         if ( cx->rc == DB_NOTFOUND ) goto saveit;
 987                         return cx->rc;
 988                 }
 989
 990                 /* If the on-disk count is zero we've never checked it.
 991                  * Count it now.
 992                  */
 993                 if ( !dkids ) {
 994                         cx->dbc->c_count( cx->dbc, &dkids, 0 );
 995                         cx->ei->bei_dkids = dkids;
 996                 }
 997
 998                 cx->data.data = cx->buf;
 999                 cx->data.ulen = BDB_IDL_UM_SIZE * sizeof(ID);
1000                 cx->data.flags = DB_DBT_USERMEM;
1001
1002                 /* Fetch the rest of the IDs in a loop... */
1003                 while ( (cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data,
1004                         DB_MULTIPLE | DB_NEXT_DUP )) == 0 ) {
1005                         u_int8_t *j;
1006                         size_t len;
1007                         DB_MULTIPLE_INIT( cx->ptr, &cx->data );
1008                         while (cx->ptr) {
1009                                 DB_MULTIPLE_NEXT( cx->ptr, &cx->data, j, len );
1010                                 if (j) {
1011                                         EntryInfo *ei2;
1012                                         diskNode *d = (diskNode *)j;
1013                                         short nrlen;
1014
1015                                         AC_MEMCPY( &ei.bei_id, &d->entryID, sizeof(ID) );
1016                                         AC_MEMCPY( &nrlen, &d->nrdnlen, sizeof(d->nrdnlen) );
1017                                         ei.bei_nrdn.bv_len = nrlen;
1018                                         /* nrdn/rdn are set in-place.
1019                                          * hdb_cache_load will copy them as needed
1020                                          */
1021                                         ei.bei_nrdn.bv_val = d->nrdn;
1022                                         ei.bei_rdn.bv_len = len - sizeof(diskNode)
1023                                                 - 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                         /* Walk the kids tree; order is irrelevant since bdb_idl_insert
1038                          * will insert in sorted order.
1039                          */
1040                         avl_apply( cx->ei->bei_kids, apply_func,
1041                                 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",
1105                 e->e_nname.bv_val, 0, 0 );
1106 #endif
1107
1108 #ifndef BDB_MULTIPLE_SUFFIXES
1109         if ( op->ors_scope != LDAP_SCOPE_ONELEVEL &&
1110                 BEI(e)->bei_parent->bei_id == 0 )
1111         {
1112                 BDB_IDL_ALL( bdb, ids );
1113                 return 0;
1114         }
1115 #endif
1116
1117         cx.id = e->e_id;
1118         cx.ei = e->e_id ? BEI(e) : &bdb->bi_cache.c_dntree;
1119         cx.bdb = bdb;
1120         cx.db = cx.bdb->bi_dn2id->bdi_db;
1121         cx.prefix = op->ors_scope == LDAP_SCOPE_ONELEVEL
1122                 ? DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
1123         cx.ids = ids;
1124         cx.buf = stack;
1125         cx.op = op;
1126
1127         BDB_IDL_ZERO( ids );
1128         if ( cx.prefix == DN_SUBTREE_PREFIX ) {
1129                 bdb_idl_insert( ids, cx.id );
1130         }
1131
1132         DBTzero(&cx.key);
1133         cx.key.data = &cx.id;
1134         cx.key.ulen = sizeof(ID);
1135         cx.key.size = sizeof(ID);
1136         cx.key.flags = DB_DBT_USERMEM;
1137
1138         DBTzero(&cx.data);
1139
1140         return hdb_dn2idl_internal(&cx);
1141 }
1142 #endif  /* BDB_HIER */