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