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 );
 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                 unsigned long 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         MDB_txn *txn,
 723         MDB_cursor **cursp,
 724         ID base,
 725         ID *scopes )
 726 {
 727         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 728         MDB_dbi dbi = mdb->mi_dn2id;
 729         MDB_val         key, data;
 730         MDB_cursor      *cursor;
 731         ID id;
 732         char    *ptr;
 733         int             rc;
 734         unsigned int x;
 735
 736         key.mv_size = sizeof(ID);
 737
 738         if ( !*cursp ) {
 739                 rc = mdb_cursor_open( txn, dbi, cursp );
 740                 if ( rc ) return rc;
 741         }
 742         cursor = *cursp;
 743
 744         id = base;
 745         while (id) {
 746                 key.mv_data = &id;
 747                 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
 748                 if ( rc )
 749                         break;
 750                 ptr = data.mv_data;
 751                 ptr += data.mv_size - sizeof(ID);
 752                 memcpy( &id, ptr, sizeof(ID) );
 753                 x = mdb_idl_search( scopes, id );
 754                 if ( scopes[x] == id )
 755                         return MDB_SUCCESS;
 756                 if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
 757                         break;
 758         }
 759         return MDB_NOTFOUND;
 760 }
 761
 762 #if 0
 763 /* mdb_dn2idl:
 764  * We can't just use mdb_idl_fetch_key because
 765  * 1 - our data items are longer than just an entry ID
 766  * 2 - our data items are sorted alphabetically by nrdn, not by ID.
 767  *
 768  * We descend the tree recursively, so we define this cookie
 769  * to hold our necessary state information. The mdb_dn2idl_internal
 770  * function uses this cookie when calling itself.
 771  */
 772
 773 struct dn2id_cookie {
 774         struct mdb_info *mdb;
 775         Operation *op;
 776         DB_TXN *txn;
 777         EntryInfo *ei;
 778         ID *ids;
 779         ID *tmp;
 780         ID *buf;
 781         DB *db;
 782         DBC *dbc;
 783         DBT key;
 784         DBT data;
 785         ID dbuf;
 786         ID id;
 787         ID nid;
 788         int rc;
 789         int depth;
 790         char need_sort;
 791         char prefix;
 792 };
 793
 794 static int
 795 apply_func(
 796         void *data,
 797         void *arg )
 798 {
 799         EntryInfo *ei = data;
 800         ID *idl = arg;
 801
 802         mdb_idl_append_one( idl, ei->bei_id );
 803         return 0;
 804 }
 805
 806 static int
 807 mdb_dn2idl_internal(
 808         struct dn2id_cookie *cx
 809 )
 810 {
 811         MDB_IDL_ZERO( cx->tmp );
 812
 813         if ( cx->mdb->bi_idl_cache_size ) {
 814                 char *ptr = ((char *)&cx->id)-1;
 815
 816                 cx->key.data = ptr;
 817                 cx->key.size = sizeof(ID)+1;
 818                 if ( cx->prefix == DN_SUBTREE_PREFIX ) {
 819                         ID *ids = cx->depth ? cx->tmp : cx->ids;
 820                         *ptr = cx->prefix;
 821                         cx->rc = mdb_idl_cache_get(cx->mdb, cx->db, &cx->key, ids);
 822                         if ( cx->rc == LDAP_SUCCESS ) {
 823                                 if ( cx->depth ) {
 824                                         mdb_idl_append( cx->ids, cx->tmp );
 825                                         cx->need_sort = 1;
 826                                 }
 827                                 return cx->rc;
 828                         }
 829                 }
 830                 *ptr = DN_ONE_PREFIX;
 831                 cx->rc = mdb_idl_cache_get(cx->mdb, cx->db, &cx->key, cx->tmp);
 832                 if ( cx->rc == LDAP_SUCCESS ) {
 833                         goto gotit;
 834                 }
 835                 if ( cx->rc == DB_NOTFOUND ) {
 836                         return cx->rc;
 837                 }
 838         }
 839
 840         mdb_cache_entryinfo_lock( cx->ei );
 841
 842         /* If number of kids in the cache differs from on-disk, load
 843          * up all the kids from the database
 844          */
 845         if ( cx->ei->bei_ckids+1 != cx->ei->bei_dkids ) {
 846                 EntryInfo ei;
 847                 db_recno_t dkids = cx->ei->bei_dkids;
 848                 ei.bei_parent = cx->ei;
 849
 850                 /* Only one thread should load the cache */
 851                 while ( cx->ei->bei_state & CACHE_ENTRY_ONELEVEL ) {
 852                         mdb_cache_entryinfo_unlock( cx->ei );
 853                         ldap_pvt_thread_yield();
 854                         mdb_cache_entryinfo_lock( cx->ei );
 855                         if ( cx->ei->bei_ckids+1 == cx->ei->bei_dkids ) {
 856                                 goto synced;
 857                         }
 858                 }
 859
 860                 cx->ei->bei_state |= CACHE_ENTRY_ONELEVEL;
 861
 862                 mdb_cache_entryinfo_unlock( cx->ei );
 863
 864                 cx->rc = cx->db->cursor( cx->db, NULL, &cx->dbc,
 865                         cx->mdb->bi_db_opflags );
 866                 if ( cx->rc )
 867                         goto done_one;
 868
 869                 cx->data.data = &cx->dbuf;
 870                 cx->data.ulen = sizeof(ID);
 871                 cx->data.dlen = sizeof(ID);
 872                 cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 873
 874                 /* The first item holds the parent ID. Ignore it. */
 875                 cx->key.data = &cx->nid;
 876                 cx->key.size = sizeof(ID);
 877                 cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET );
 878                 if ( cx->rc ) {
 879                         cx->dbc->c_close( cx->dbc );
 880                         goto done_one;
 881                 }
 882
 883                 /* If the on-disk count is zero we've never checked it.
 884                  * Count it now.
 885                  */
 886                 if ( !dkids ) {
 887                         cx->dbc->c_count( cx->dbc, &dkids, 0 );
 888                         cx->ei->bei_dkids = dkids;
 889                 }
 890
 891                 cx->data.data = cx->buf;
 892                 cx->data.ulen = MDB_IDL_UM_SIZE * sizeof(ID);
 893                 cx->data.flags = DB_DBT_USERMEM;
 894
 895                 if ( dkids > 1 ) {
 896                         /* Fetch the rest of the IDs in a loop... */
 897                         while ( (cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data,
 898                                 DB_MULTIPLE | DB_NEXT_DUP )) == 0 ) {
 899                                 u_int8_t *j;
 900                                 size_t len;
 901                                 void *ptr;
 902                                 DB_MULTIPLE_INIT( ptr, &cx->data );
 903                                 while (ptr) {
 904                                         DB_MULTIPLE_NEXT( ptr, &cx->data, j, len );
 905                                         if (j) {
 906                                                 EntryInfo *ei2;
 907                                                 diskNode *d = (diskNode *)j;
 908                                                 short nrlen;
 909
 910                                                 MDB_DISK2ID( j + len - sizeof(ID), &ei.bei_id );
 911                                                 nrlen = ((d->nrdnlen[0] ^ 0x80) << 8) | d->nrdnlen[1];
 912                                                 ei.bei_nrdn.bv_len = nrlen;
 913                                                 /* nrdn/rdn are set in-place.
 914                                                  * mdb_cache_load will copy them as needed
 915                                                  */
 916                                                 ei.bei_nrdn.bv_val = d->nrdn;
 917                                                 ei.bei_rdn.bv_len = len - sizeof(diskNode)
 918                                                         - ei.bei_nrdn.bv_len;
 919                                                 ei.bei_rdn.bv_val = d->nrdn + ei.bei_nrdn.bv_len + 1;
 920                                                 mdb_idl_append_one( cx->tmp, ei.bei_id );
 921                                                 mdb_cache_load( cx->mdb, &ei, &ei2 );
 922                                         }
 923                                 }
 924                         }
 925                 }
 926
 927                 cx->rc = cx->dbc->c_close( cx->dbc );
 928 done_one:
 929                 mdb_cache_entryinfo_lock( cx->ei );
 930                 cx->ei->bei_state &= ~CACHE_ENTRY_ONELEVEL;
 931                 mdb_cache_entryinfo_unlock( cx->ei );
 932                 if ( cx->rc )
 933                         return cx->rc;
 934
 935         } else {
 936                 /* The in-memory cache is in sync with the on-disk data.
 937                  * do we have any kids?
 938                  */
 939 synced:
 940                 cx->rc = 0;
 941                 if ( cx->ei->bei_ckids > 0 ) {
 942                         /* Walk the kids tree; order is irrelevant since mdb_idl_sort
 943                          * will sort it later.
 944                          */
 945                         avl_apply( cx->ei->bei_kids, apply_func,
 946                                 cx->tmp, -1, AVL_POSTORDER );
 947                 }
 948                 mdb_cache_entryinfo_unlock( cx->ei );
 949         }
 950
 951         if ( !MDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 3 )
 952                 mdb_idl_sort( cx->tmp, cx->buf );
 953         if ( cx->mdb->bi_idl_cache_max_size && !MDB_IDL_IS_ZERO( cx->tmp )) {
 954                 char *ptr = ((char *)&cx->id)-1;
 955                 cx->key.data = ptr;
 956                 cx->key.size = sizeof(ID)+1;
 957                 *ptr = DN_ONE_PREFIX;
 958                 mdb_idl_cache_put( cx->mdb, cx->db, &cx->key, cx->tmp, cx->rc );
 959         }
 960
 961 gotit:
 962         if ( !MDB_IDL_IS_ZERO( cx->tmp )) {
 963                 if ( cx->prefix == DN_SUBTREE_PREFIX ) {
 964                         mdb_idl_append( cx->ids, cx->tmp );
 965                         cx->need_sort = 1;
 966                         if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) {
 967                                 ID *save, idcurs;
 968                                 EntryInfo *ei = cx->ei;
 969                                 int nokids = 1;
 970                                 save = cx->op->o_tmpalloc( MDB_IDL_SIZEOF( cx->tmp ),
 971                                         cx->op->o_tmpmemctx );
 972                                 MDB_IDL_CPY( save, cx->tmp );
 973
 974                                 idcurs = 0;
 975                                 cx->depth++;
 976                                 for ( cx->id = mdb_idl_first( save, &idcurs );
 977                                         cx->id != NOID;
 978                                         cx->id = mdb_idl_next( save, &idcurs )) {
 979                                         EntryInfo *ei2;
 980                                         cx->ei = NULL;
 981                                         if ( mdb_cache_find_id( cx->op, cx->txn, cx->id, &cx->ei,
 982                                                 ID_NOENTRY, NULL ))
 983                                                 continue;
 984                                         if ( cx->ei ) {
 985                                                 ei2 = cx->ei;
 986                                                 if ( !( ei2->bei_state & CACHE_ENTRY_NO_KIDS )) {
 987                                                         MDB_ID2DISK( cx->id, &cx->nid );
 988                                                         mdb_dn2idl_internal( cx );
 989                                                         if ( !MDB_IDL_IS_ZERO( cx->tmp ))
 990                                                                 nokids = 0;
 991                                                 }
 992                                                 mdb_cache_entryinfo_lock( ei2 );
 993                                                 ei2->bei_finders--;
 994                                                 mdb_cache_entryinfo_unlock( ei2 );
 995                                         }
 996                                 }
 997                                 cx->depth--;
 998                                 cx->op->o_tmpfree( save, cx->op->o_tmpmemctx );
 999                                 if ( nokids ) {
1000                                         mdb_cache_entryinfo_lock( ei );
1001                                         ei->bei_state |= CACHE_ENTRY_NO_GRANDKIDS;
1002                                         mdb_cache_entryinfo_unlock( ei );
1003                                 }
1004                         }
1005                         /* Make sure caller knows it had kids! */
1006                         cx->tmp[0]=1;
1007
1008                         cx->rc = 0;
1009                 } else {
1010                         MDB_IDL_CPY( cx->ids, cx->tmp );
1011                 }
1012         }
1013         return cx->rc;
1014 }
1015
1016 int
1017 mdb_dn2idl(
1018         Operation       *op,
1019         DB_TXN *txn,
1020         struct berval *ndn,
1021         EntryInfo       *ei,
1022         ID *ids,
1023         ID *stack )
1024 {
1025         struct mdb_info *mdb = (struct mdb_info *)op->o_bd->be_private;
1026         struct dn2id_cookie cx;
1027
1028         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2idl(\"%s\")\n",
1029                 ndn->bv_val, 0, 0 );
1030
1031 #ifndef MDB_MULTIPLE_SUFFIXES
1032         if ( op->ors_scope != LDAP_SCOPE_ONELEVEL &&
1033                 ( ei->bei_id == 0 ||
1034                 ( ei->bei_parent->bei_id == 0 && op->o_bd->be_suffix[0].bv_len )))
1035         {
1036                 MDB_IDL_ALL( mdb, ids );
1037                 return 0;
1038         }
1039 #endif
1040
1041         cx.id = ei->bei_id;
1042         MDB_ID2DISK( cx.id, &cx.nid );
1043         cx.ei = ei;
1044         cx.mdb = mdb;
1045         cx.db = cx.mdb->bi_dn2id->bdi_db;
1046         cx.prefix = (op->ors_scope == LDAP_SCOPE_ONELEVEL) ?
1047                 DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
1048         cx.ids = ids;
1049         cx.tmp = stack;
1050         cx.buf = stack + MDB_IDL_UM_SIZE;
1051         cx.op = op;
1052         cx.txn = txn;
1053         cx.need_sort = 0;
1054         cx.depth = 0;
1055
1056         if ( cx.prefix == DN_SUBTREE_PREFIX ) {
1057                 ids[0] = 1;
1058                 ids[1] = cx.id;
1059         } else {
1060                 MDB_IDL_ZERO( ids );
1061         }
1062         if ( cx.ei->bei_state & CACHE_ENTRY_NO_KIDS )
1063                 return LDAP_SUCCESS;
1064
1065         DBTzero(&cx.key);
1066         cx.key.ulen = sizeof(ID);
1067         cx.key.size = sizeof(ID);
1068         cx.key.flags = DB_DBT_USERMEM;
1069
1070         DBTzero(&cx.data);
1071
1072         mdb_dn2idl_internal(&cx);
1073         if ( cx.need_sort ) {
1074                 char *ptr = ((char *)&cx.id)-1;
1075                 if ( !MDB_IDL_IS_RANGE( cx.ids ) && cx.ids[0] > 3 )
1076                         mdb_idl_sort( cx.ids, cx.tmp );
1077                 cx.key.data = ptr;
1078                 cx.key.size = sizeof(ID)+1;
1079                 *ptr = cx.prefix;
1080                 cx.id = ei->bei_id;
1081                 if ( cx.mdb->bi_idl_cache_max_size )
1082                         mdb_idl_cache_put( cx.mdb, cx.db, &cx.key, cx.ids, cx.rc );
1083         }
1084
1085         if ( cx.rc == DB_NOTFOUND )
1086                 cx.rc = LDAP_SUCCESS;
1087
1088         return cx.rc;
1089 }
1090 #endif