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