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