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