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-2013 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  * Also each child node contains a count of the number of entries in
  40  * its subtree, appended after its entryID.
  41  *
  42  * The diskNode is a variable length structure. This definition is not
  43  * directly usable for in-memory manipulation.
  44  */
  45 typedef struct diskNode {
  46         unsigned char nrdnlen[2];
  47         char nrdn[1];
  48         char rdn[1];                        /* variable placement */
  49         unsigned char entryID[sizeof(ID)];  /* variable placement */
  50         /* unsigned char nsubs[sizeof(ID)];     in child nodes only */
  51 } diskNode;
  52
  53 /* Sort function for the sorted duplicate data items of a dn2id key.
  54  * Sorts based on normalized RDN, in length order.
  55  */
  56 int
  57 mdb_dup_compare(
  58         const MDB_val *usrkey,
  59         const MDB_val *curkey
  60 )
  61 {
  62         diskNode *un, *cn;
  63         int rc, nrlen;
  64
  65         un = (diskNode *)usrkey->mv_data;
  66         cn = (diskNode *)curkey->mv_data;
  67
  68         /* data is not aligned, cannot compare directly */
  69         rc = un->nrdnlen[0] - cn->nrdnlen[0];
  70         if ( rc ) return rc;
  71         rc = un->nrdnlen[1] - cn->nrdnlen[1];
  72         if ( rc ) return rc;
  73
  74         nrlen = ((un->nrdnlen[0] & 0x7f) << 8) | un->nrdnlen[1];
  75         return strncmp( un->nrdn, cn->nrdn, nrlen );
  76 }
  77
  78 /* We add two elements to the DN2ID database - a data item under the parent's
  79  * entryID containing the child's RDN and entryID, and an item under the
  80  * child's entryID containing the parent's entryID.
  81  */
  82 int
  83 mdb_dn2id_add(
  84         Operation       *op,
  85         MDB_cursor      *mcp,
  86         MDB_cursor      *mcd,
  87         ID pid,
  88         ID nsubs,
  89         Entry           *e )
  90 {
  91         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
  92         MDB_val         key, data;
  93         ID              nid;
  94         int             rc, rlen, nrlen;
  95         diskNode *d;
  96         char *ptr;
  97
  98         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_add 0x%lx: \"%s\"\n",
  99                 e->e_id, e->e_ndn ? e->e_ndn : "", 0 );
 100
 101         nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
 102         if (nrlen) {
 103                 rlen = dn_rdnlen( op->o_bd, &e->e_name );
 104         } else {
 105                 nrlen = e->e_nname.bv_len;
 106                 rlen = e->e_name.bv_len;
 107         }
 108
 109         d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen + sizeof(ID), op->o_tmpmemctx);
 110         d->nrdnlen[1] = nrlen & 0xff;
 111         d->nrdnlen[0] = (nrlen >> 8) | 0x80;
 112         ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
 113         *ptr++ = '\0';
 114         ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
 115         *ptr++ = '\0';
 116         memcpy( ptr, &e->e_id, sizeof( ID ));
 117         ptr += sizeof( ID );
 118         memcpy( ptr, &nsubs, sizeof( ID ));
 119
 120         key.mv_size = sizeof(ID);
 121         key.mv_data = &nid;
 122
 123         nid = pid;
 124
 125         /* Need to make dummy root node once. Subsequent attempts
 126          * will fail harmlessly.
 127          */
 128         if ( pid == 0 ) {
 129                 diskNode dummy = {{0, 0}, "", "", ""};
 130                 data.mv_data = &dummy;
 131                 data.mv_size = sizeof(diskNode);
 132
 133                 mdb_cursor_put( mcp, &key, &data, MDB_NODUPDATA );
 134         }
 135
 136         data.mv_data = d;
 137         data.mv_size = sizeof(diskNode) + rlen + nrlen + sizeof( ID );
 138
 139         /* Add our child node under parent's key */
 140         rc = mdb_cursor_put( mcp, &key, &data, MDB_NODUPDATA );
 141
 142         /* Add our own node */
 143         if (rc == 0) {
 144                 int flag = MDB_NODUPDATA;
 145                 nid = e->e_id;
 146                 /* drop subtree count */
 147                 data.mv_size -= sizeof( ID );
 148                 ptr -= sizeof( ID );
 149                 memcpy( ptr, &pid, sizeof( ID ));
 150                 d->nrdnlen[0] ^= 0x80;
 151
 152                 if ((slapMode & SLAP_TOOL_MODE) || (e->e_id == mdb->mi_nextid))
 153                         flag |= MDB_APPEND;
 154                 rc = mdb_cursor_put( mcd, &key, &data, flag );
 155         }
 156         op->o_tmpfree( d, op->o_tmpmemctx );
 157
 158         /* Add our subtree count to all superiors */
 159         if ( rc == 0 && nsubs && pid ) {
 160                 ID subs;
 161                 nid = pid;
 162                 do {
 163                         /* Get parent's RDN */
 164                         rc = mdb_cursor_get( mcp, &key, &data, MDB_SET );
 165                         if ( !rc ) {
 166                                 char *p2;
 167                                 ptr = data.mv_data + data.mv_size - sizeof( ID );
 168                                 memcpy( &nid, ptr, sizeof( ID ));
 169                                 /* Get parent's node under grandparent */
 170                                 d = data.mv_data;
 171                                 rlen = ( d->nrdnlen[0] << 8 ) | d->nrdnlen[1];
 172                                 p2 = op->o_tmpalloc( rlen + 2, op->o_tmpmemctx );
 173                                 memcpy( p2, data.mv_data, rlen+2 );
 174                                 *p2 ^= 0x80;
 175                                 data.mv_data = p2;
 176                                 rc = mdb_cursor_get( mcp, &key, &data, MDB_GET_BOTH );
 177                                 op->o_tmpfree( p2, op->o_tmpmemctx );
 178                                 if ( !rc ) {
 179                                         /* Get parent's subtree count */
 180                                         ptr = data.mv_data + data.mv_size - sizeof( ID );
 181                                         memcpy( &subs, ptr, sizeof( ID ));
 182                                         subs += nsubs;
 183                                         p2 = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
 184                                         memcpy( p2, data.mv_data, data.mv_size - sizeof( ID ));
 185                                         memcpy( p2+data.mv_size - sizeof( ID ), &subs, sizeof( ID ));
 186                                         data.mv_data = p2;
 187                                         rc = mdb_cursor_put( mcp, &key, &data, MDB_CURRENT );
 188                                         op->o_tmpfree( p2, op->o_tmpmemctx );
 189                                 }
 190                         }
 191                         if ( rc )
 192                                 break;
 193                 } while ( nid );
 194         }
 195
 196         Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
 197
 198         return rc;
 199 }
 200
 201 /* mc must have been set by mdb_dn2id */
 202 int
 203 mdb_dn2id_delete(
 204         Operation       *op,
 205         MDB_cursor *mc,
 206         ID id,
 207         ID nsubs )
 208 {
 209         ID nid;
 210         char *ptr;
 211         int rc;
 212
 213         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_delete 0x%lx\n",
 214                 id, 0, 0 );
 215
 216         /* Delete our ID from the parent's list */
 217         rc = mdb_cursor_del( mc, 0 );
 218
 219         /* Delete our ID from the tree. With sorted duplicates, this
 220          * will leave any child nodes still hanging around. This is OK
 221          * for modrdn, which will add our info back in later.
 222          */
 223         if ( rc == 0 ) {
 224                 MDB_val key, data;
 225                 if ( nsubs ) {
 226                         mdb_cursor_get( mc, &key, NULL, MDB_GET_CURRENT );
 227                         memcpy( &nid, key.mv_data, sizeof( ID ));
 228                 }
 229                 key.mv_size = sizeof(ID);
 230                 key.mv_data = &id;
 231                 rc = mdb_cursor_get( mc, &key, &data, MDB_SET );
 232                 if ( rc == 0 )
 233                         rc = mdb_cursor_del( mc, 0 );
 234         }
 235
 236         /* Delete our subtree count from all superiors */
 237         if ( rc == 0 && nsubs && nid ) {
 238                 MDB_val key, data;
 239                 ID subs;
 240                 key.mv_data = &nid;
 241                 key.mv_size = sizeof( ID );
 242                 do {
 243                         rc = mdb_cursor_get( mc, &key, &data, MDB_SET );
 244                         if ( !rc ) {
 245                                 char *p2;
 246                                 diskNode *d;
 247                                 int rlen;
 248                                 ptr = data.mv_data + data.mv_size - sizeof( ID );
 249                                 memcpy( &nid, ptr, sizeof( ID ));
 250                                 /* Get parent's node under grandparent */
 251                                 d = data.mv_data;
 252                                 rlen = ( d->nrdnlen[0] << 8 ) | d->nrdnlen[1];
 253                                 p2 = op->o_tmpalloc( rlen + 2, op->o_tmpmemctx );
 254                                 memcpy( p2, data.mv_data, rlen+2 );
 255                                 *p2 ^= 0x80;
 256                                 data.mv_data = p2;
 257                                 rc = mdb_cursor_get( mc, &key, &data, MDB_GET_BOTH );
 258                                 op->o_tmpfree( p2, op->o_tmpmemctx );
 259                                 if ( !rc ) {
 260                                         /* Get parent's subtree count */
 261                                         ptr = data.mv_data + data.mv_size - sizeof( ID );
 262                                         memcpy( &subs, ptr, sizeof( ID ));
 263                                         subs -= nsubs;
 264                                         p2 = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
 265                                         memcpy( p2, data.mv_data, data.mv_size - sizeof( ID ));
 266                                         memcpy( p2+data.mv_size - sizeof( ID ), &subs, sizeof( ID ));
 267                                         data.mv_data = p2;
 268                                         rc = mdb_cursor_put( mc, &key, &data, MDB_CURRENT );
 269                                         op->o_tmpfree( p2, op->o_tmpmemctx );
 270                                 }
 271
 272                         }
 273                         if ( rc )
 274                                 break;
 275                 } while ( nid );
 276         }
 277
 278         Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_delete 0x%lx: %d\n", id, rc, 0 );
 279         return rc;
 280 }
 281
 282 /* return last found ID in *id if no match
 283  * If mc is provided, it will be left pointing to the RDN's
 284  * record under the parent's ID. If nsubs is provided, return
 285  * the number of entries in this entry's subtree.
 286  */
 287 int
 288 mdb_dn2id(
 289         Operation       *op,
 290         MDB_txn *txn,
 291         MDB_cursor      *mc,
 292         struct berval   *in,
 293         ID      *id,
 294         ID      *nsubs,
 295         struct berval   *matched,
 296         struct berval   *nmatched )
 297 {
 298         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 299         MDB_cursor *cursor;
 300         MDB_dbi dbi = mdb->mi_dn2id;
 301         MDB_val         key, data;
 302         int             rc = 0, nrlen;
 303         diskNode *d;
 304         char    *ptr;
 305         char dn[SLAP_LDAPDN_MAXLEN];
 306         ID pid, nid;
 307         struct berval tmp;
 308
 309         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id(\"%s\")\n", in->bv_val ? in->bv_val : "", 0, 0 );
 310
 311         if ( matched ) {
 312                 matched->bv_val = dn + sizeof(dn) - 1;
 313                 matched->bv_len = 0;
 314                 *matched->bv_val-- = '\0';
 315         }
 316         if ( nmatched ) {
 317                 nmatched->bv_len = 0;
 318                 nmatched->bv_val = 0;
 319         }
 320
 321         if ( !in->bv_len ) {
 322                 *id = 0;
 323                 nid = 0;
 324                 goto done;
 325         }
 326
 327         tmp = *in;
 328
 329         if ( op->o_bd->be_nsuffix[0].bv_len ) {
 330                 nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
 331                 tmp.bv_val += nrlen;
 332                 tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
 333         } else {
 334                 for ( ptr = tmp.bv_val + tmp.bv_len - 1; ptr >= tmp.bv_val; ptr-- )
 335                         if (DN_SEPARATOR(*ptr))
 336                                 break;
 337                 ptr++;
 338                 tmp.bv_len -= ptr - tmp.bv_val;
 339                 tmp.bv_val = ptr;
 340         }
 341         nid = 0;
 342         key.mv_size = sizeof(ID);
 343
 344         if ( mc ) {
 345                 cursor = mc;
 346         } else {
 347                 rc = mdb_cursor_open( txn, dbi, &cursor );
 348                 if ( rc ) return rc;
 349         }
 350
 351         for (;;) {
 352                 key.mv_data = &pid;
 353                 pid = nid;
 354
 355                 data.mv_size = sizeof(diskNode) + tmp.bv_len;
 356                 d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
 357                 d->nrdnlen[1] = tmp.bv_len & 0xff;
 358                 d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
 359                 ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
 360                 *ptr = '\0';
 361                 data.mv_data = d;
 362                 rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
 363                 op->o_tmpfree( d, op->o_tmpmemctx );
 364                 if ( rc )
 365                         break;
 366                 ptr = (char *) data.mv_data + data.mv_size - 2*sizeof(ID);
 367                 memcpy( &nid, ptr, sizeof(ID));
 368
 369                 /* grab the non-normalized RDN */
 370                 if ( matched ) {
 371                         int rlen;
 372                         d = data.mv_data;
 373                         rlen = data.mv_size - sizeof(diskNode) - tmp.bv_len - sizeof(ID);
 374                         matched->bv_len += rlen;
 375                         matched->bv_val -= rlen + 1;
 376                         ptr = lutil_strcopy( matched->bv_val, d->rdn + tmp.bv_len );
 377                         if ( pid ) {
 378                                 *ptr = ',';
 379                                 matched->bv_len++;
 380                         }
 381                 }
 382                 if ( nmatched ) {
 383                         nmatched->bv_val = tmp.bv_val;
 384                 }
 385
 386                 if ( tmp.bv_val > in->bv_val ) {
 387                         for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
 388                                 !DN_SEPARATOR(*ptr); ptr--)     /* empty */;
 389                         if ( ptr >= in->bv_val ) {
 390                                 if (DN_SEPARATOR(*ptr)) ptr++;
 391                                 tmp.bv_len = tmp.bv_val - ptr - 1;
 392                                 tmp.bv_val = ptr;
 393                         }
 394                 } else {
 395                         break;
 396                 }
 397         }
 398         *id = nid;
 399         /* return subtree count if requested */
 400         if ( !rc && nsubs ) {
 401                 ptr = data.mv_data + data.mv_size - sizeof(ID);
 402                 memcpy( nsubs, ptr, sizeof( ID ));
 403         }
 404         if ( !mc )
 405                 mdb_cursor_close( cursor );
 406 done:
 407         if ( matched ) {
 408                 if ( matched->bv_len ) {
 409                         ptr = op->o_tmpalloc( matched->bv_len+1, op->o_tmpmemctx );
 410                         strcpy( ptr, matched->bv_val );
 411                         matched->bv_val = ptr;
 412                 } else {
 413                         if ( BER_BVISEMPTY( &op->o_bd->be_nsuffix[0] ) && !nid ) {
 414                                 ber_dupbv( matched, (struct berval *)&slap_empty_bv );
 415                         } else {
 416                                 matched->bv_val = NULL;
 417                         }
 418                 }
 419         }
 420         if ( nmatched ) {
 421                 if ( nmatched->bv_val ) {
 422                         nmatched->bv_len = in->bv_len - (nmatched->bv_val - in->bv_val);
 423                 } else {
 424                         *nmatched = slap_empty_bv;
 425                 }
 426         }
 427
 428         if( rc != 0 ) {
 429                 Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: get failed: %s (%d)\n",
 430                         mdb_strerror( rc ), rc, 0 );
 431         } else {
 432                 Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: got id=0x%lx\n",
 433                         nid, 0, 0 );
 434         }
 435
 436         return rc;
 437 }
 438
 439 /* return IDs from root to parent of DN */
 440 int
 441 mdb_dn2sups(
 442         Operation       *op,
 443         MDB_txn *txn,
 444         struct berval   *in,
 445         ID      *ids )
 446 {
 447         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 448         MDB_cursor *cursor;
 449         MDB_dbi dbi = mdb->mi_dn2id;
 450         MDB_val         key, data;
 451         int             rc = 0, nrlen;
 452         diskNode *d;
 453         char    *ptr;
 454         ID pid, nid;
 455         struct berval tmp;
 456
 457         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2sups(\"%s\")\n", in->bv_val, 0, 0 );
 458
 459         if ( !in->bv_len ) {
 460                 goto done;
 461         }
 462
 463         tmp = *in;
 464
 465         nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
 466         tmp.bv_val += nrlen;
 467         tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
 468         nid = 0;
 469         key.mv_size = sizeof(ID);
 470
 471         rc = mdb_cursor_open( txn, dbi, &cursor );
 472         if ( rc ) return rc;
 473
 474         for (;;) {
 475                 key.mv_data = &pid;
 476                 pid = nid;
 477
 478                 data.mv_size = sizeof(diskNode) + tmp.bv_len;
 479                 d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
 480                 d->nrdnlen[1] = tmp.bv_len & 0xff;
 481                 d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
 482                 ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
 483                 *ptr = '\0';
 484                 data.mv_data = d;
 485                 rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
 486                 op->o_tmpfree( d, op->o_tmpmemctx );
 487                 if ( rc ) {
 488                         mdb_cursor_close( cursor );
 489                         break;
 490                 }
 491                 ptr = (char *) data.mv_data + data.mv_size - 2*sizeof(ID);
 492                 memcpy( &nid, ptr, sizeof(ID));
 493
 494                 if ( pid )
 495                         mdb_idl_insert( ids, pid );
 496
 497                 if ( tmp.bv_val > in->bv_val ) {
 498                         for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
 499                                 !DN_SEPARATOR(*ptr); ptr--)     /* empty */;
 500                         if ( ptr >= in->bv_val ) {
 501                                 if (DN_SEPARATOR(*ptr)) ptr++;
 502                                 tmp.bv_len = tmp.bv_val - ptr - 1;
 503                                 tmp.bv_val = ptr;
 504                         }
 505                 } else {
 506                         break;
 507                 }
 508         }
 509
 510 done:
 511         if( rc != 0 ) {
 512                 Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2sups: get failed: %s (%d)\n",
 513                         mdb_strerror( rc ), rc, 0 );
 514         }
 515
 516         return rc;
 517 }
 518
 519 int
 520 mdb_dn2id_children(
 521         Operation *op,
 522         MDB_txn *txn,
 523         Entry *e )
 524 {
 525         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 526         MDB_dbi dbi = mdb->mi_dn2id;
 527         MDB_val         key, data;
 528         MDB_cursor      *cursor;
 529         int             rc;
 530         ID              id;
 531
 532         key.mv_size = sizeof(ID);
 533         key.mv_data = &id;
 534         id = e->e_id;
 535
 536         rc = mdb_cursor_open( txn, dbi, &cursor );
 537         if ( rc ) return rc;
 538
 539         rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
 540         if ( rc == 0 ) {
 541                 size_t dkids;
 542                 rc = mdb_cursor_count( cursor, &dkids );
 543                 if ( rc == 0 ) {
 544                         if ( dkids < 2 ) rc = MDB_NOTFOUND;
 545                 }
 546         }
 547         mdb_cursor_close( cursor );
 548         return rc;
 549 }
 550
 551 int
 552 mdb_id2name(
 553         Operation *op,
 554         MDB_txn *txn,
 555         MDB_cursor **cursp,
 556         ID id,
 557         struct berval *name,
 558         struct berval *nname )
 559 {
 560         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 561         MDB_dbi dbi = mdb->mi_dn2id;
 562         MDB_val         key, data;
 563         MDB_cursor      *cursor;
 564         int             rc, len, nlen;
 565         char dn[SLAP_LDAPDN_MAXLEN], ndn[SLAP_LDAPDN_MAXLEN], *ptr;
 566         char *dptr, *nptr;
 567         diskNode *d;
 568
 569         key.mv_size = sizeof(ID);
 570
 571         if ( !*cursp ) {
 572                 rc = mdb_cursor_open( txn, dbi, cursp );
 573                 if ( rc ) return rc;
 574         }
 575         cursor = *cursp;
 576
 577         len = 0;
 578         nlen = 0;
 579         dptr = dn;
 580         nptr = ndn;
 581         while (id) {
 582                 unsigned int nrlen, rlen;
 583                 key.mv_data = &id;
 584                 data.mv_size = 0;
 585                 data.mv_data = "";
 586                 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
 587                 if ( rc ) break;
 588                 ptr = data.mv_data;
 589                 ptr += data.mv_size - sizeof(ID);
 590                 memcpy( &id, ptr, sizeof(ID) );
 591                 d = data.mv_data;
 592                 nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
 593                 rlen = data.mv_size - sizeof(diskNode) - nrlen;
 594                 assert( nrlen < 1024 && rlen < 1024 );  /* FIXME: Sanity check */
 595                 if (nptr > ndn) {
 596                         *nptr++ = ',';
 597                         *dptr++ = ',';
 598                 }
 599                 /* copy name and trailing NUL */
 600                 memcpy( nptr, d->nrdn, nrlen+1 );
 601                 memcpy( dptr, d->nrdn+nrlen+1, rlen+1 );
 602                 nptr += nrlen;
 603                 dptr += rlen;
 604         }
 605         if ( rc == 0 ) {
 606                 name->bv_len = dptr - dn;
 607                 nname->bv_len = nptr - ndn;
 608                 name->bv_val = op->o_tmpalloc( name->bv_len + 1, op->o_tmpmemctx );
 609                 nname->bv_val = op->o_tmpalloc( nname->bv_len + 1, op->o_tmpmemctx );
 610                 memcpy( name->bv_val, dn, name->bv_len );
 611                 name->bv_val[name->bv_len] = '\0';
 612                 memcpy( nname->bv_val, ndn, nname->bv_len );
 613                 nname->bv_val[nname->bv_len] = '\0';
 614         }
 615         return rc;
 616 }
 617
 618 /* Find each id in ids that is a child of base and move it to res.
 619  */
 620 int
 621 mdb_idscope(
 622         Operation *op,
 623         MDB_txn *txn,
 624         ID base,
 625         ID *ids,
 626         ID *res )
 627 {
 628         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 629         MDB_dbi dbi = mdb->mi_dn2id;
 630         MDB_val         key, data;
 631         MDB_cursor      *cursor;
 632         ID ida, id, cid, ci0, idc = 0;
 633         char    *ptr;
 634         int             rc;
 635
 636         key.mv_size = sizeof(ID);
 637
 638         MDB_IDL_ZERO( res );
 639
 640         rc = mdb_cursor_open( txn, dbi, &cursor );
 641         if ( rc ) return rc;
 642
 643         ida = mdb_idl_first( ids, &cid );
 644
 645         /* Don't bother moving out of ids if it's a range */
 646         if (!MDB_IDL_IS_RANGE(ids)) {
 647                 idc = ids[0];
 648                 ci0 = cid;
 649         }
 650
 651         while (ida != NOID) {
 652                 id = ida;
 653                 while (id) {
 654                         key.mv_data = &id;
 655                         rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
 656                         if ( rc ) {
 657                                 /* not found, move on to next */
 658                                 if (idc) {
 659                                         if (ci0 != cid)
 660                                                 ids[ci0] = ids[cid];
 661                                         ci0++;
 662                                 }
 663                                 break;
 664                         }
 665                         ptr = data.mv_data;
 666                         ptr += data.mv_size - sizeof(ID);
 667                         memcpy( &id, ptr, sizeof(ID) );
 668                         if ( id == base ) {
 669                                 res[0]++;
 670                                 res[res[0]] = ida;
 671                                 if (idc)
 672                                         idc--;
 673                                 break;
 674                         } else {
 675                                 if (idc) {
 676                                         if (ci0 != cid)
 677                                                 ids[ci0] = ids[cid];
 678                                         ci0++;
 679                                 }
 680                         }
 681                         if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
 682                                 break;
 683                 }
 684                 ida = mdb_idl_next( ids, &cid );
 685         }
 686         if (!MDB_IDL_IS_RANGE( ids ))
 687                 ids[0] = idc;
 688
 689         mdb_cursor_close( cursor );
 690         return rc;
 691 }
 692
 693 /* See if base is a child of any of the scopes
 694  */
 695 int
 696 mdb_idscopes(
 697         Operation *op,
 698         IdScopes *isc )
 699 {
 700         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 701         MDB_dbi dbi = mdb->mi_dn2id;
 702         MDB_val         key, data;
 703         ID id;
 704         ID2 id2;
 705         char    *ptr;
 706         int             rc = 0;
 707         unsigned int x;
 708         unsigned int nrlen, rlen;
 709         diskNode *d;
 710
 711         key.mv_size = sizeof(ID);
 712
 713         if ( !isc->mc ) {
 714                 rc = mdb_cursor_open( isc->mt, dbi, &isc->mc );
 715                 if ( rc ) return rc;
 716         }
 717
 718         id = isc->id;
 719         while (id) {
 720                 if ( !rc ) {
 721                         key.mv_data = &id;
 722                         rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
 723                         if ( rc )
 724                                 return rc;
 725
 726                         /* save RDN info */
 727                 }
 728                 d = data.mv_data;
 729                 nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
 730                 rlen = data.mv_size - sizeof(diskNode) - nrlen;
 731                 isc->nrdns[isc->numrdns].bv_len = nrlen;
 732                 isc->nrdns[isc->numrdns].bv_val = d->nrdn;
 733                 isc->rdns[isc->numrdns].bv_len = rlen;
 734                 isc->rdns[isc->numrdns].bv_val = d->nrdn+nrlen+1;
 735                 isc->numrdns++;
 736
 737                 if (!rc && id != isc->id) {
 738                         id2.mid = id;
 739                         id2.mval = data;
 740                         mdb_id2l_insert( isc->scopes, &id2 );
 741                 }
 742                 ptr = data.mv_data;
 743                 ptr += data.mv_size - sizeof(ID);
 744                 memcpy( &id, ptr, sizeof(ID) );
 745                 x = mdb_id2l_search( isc->scopes, id );
 746                 if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) {
 747                         if ( !isc->scopes[x].mval.mv_data ) {
 748                                 isc->nscope = x;
 749                                 return MDB_SUCCESS;
 750                         }
 751                         data = isc->scopes[x].mval;
 752                         rc = 1;
 753                 }
 754                 if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
 755                         break;
 756         }
 757         return MDB_SUCCESS;
 758 }
 759
 760 int
 761 mdb_dn2id_walk(
 762         Operation *op,
 763         IdScopes *isc
 764 )
 765 {
 766         MDB_val key, data;
 767         diskNode *d;
 768         char *ptr;
 769         int rc, n;
 770         ID nsubs;
 771
 772         if ( !isc->numrdns ) {
 773                 key.mv_data = &isc->id;
 774                 key.mv_size = sizeof(ID);
 775                 rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
 776                 isc->scopes[0].mid = isc->id;
 777                 isc->numrdns++;
 778                 isc->nscope = 0;
 779                 /* skip base if not a subtree walk */
 780                 if ( op->ors_scope == LDAP_SCOPE_SUBTREE ||
 781                         op->ors_scope == LDAP_SCOPE_BASE )
 782                         return rc;
 783         }
 784         if ( op->ors_scope == LDAP_SCOPE_BASE )
 785                 return MDB_NOTFOUND;
 786
 787         for (;;) {
 788                 /* Get next sibling */
 789                 rc = mdb_cursor_get( isc->mc, &key, &data, MDB_NEXT_DUP );
 790                 if ( !rc ) {
 791                         ptr = data.mv_data + data.mv_size - 2*sizeof(ID);
 792                         d = data.mv_data;
 793                         memcpy( &isc->id, ptr, sizeof(ID));
 794
 795                         /* If we're pushing down, see if there's any children to find */
 796                         if ( isc->nscope ) {
 797                                 ptr += sizeof(ID);
 798                                 memcpy( &nsubs, ptr, sizeof(ID));
 799                                 /* No children, go to next sibling */
 800                                 if ( nsubs < 2 )
 801                                         continue;
 802                         }
 803                         n = isc->numrdns;
 804                         isc->scopes[n].mid = isc->id;
 805                         n--;
 806                         isc->nrdns[n].bv_len = ((d->nrdnlen[0] & 0x7f) << 8) | d->nrdnlen[1];
 807                         isc->nrdns[n].bv_val = d->nrdn;
 808                         isc->rdns[n].bv_val = d->nrdn+isc->nrdns[n].bv_len+1;
 809                         isc->rdns[n].bv_len = data.mv_size - sizeof(diskNode) - isc->nrdns[n].bv_len - sizeof(ID);
 810                         /* return this ID to caller */
 811                         if ( !isc->nscope )
 812                                 break;
 813
 814                         /* push down to child */
 815                         key.mv_data = &isc->id;
 816                         mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
 817                         isc->nscope = 0;
 818                         isc->numrdns++;
 819                         continue;
 820
 821                 } else if ( rc == MDB_NOTFOUND ) {
 822                         if ( !isc->nscope && op->ors_scope != LDAP_SCOPE_ONELEVEL ) {
 823                                 /* reset to first dup */
 824                                 mdb_cursor_get( isc->mc, &key, NULL, MDB_GET_CURRENT );
 825                                 mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
 826                                 isc->nscope = 1;
 827                                 continue;
 828                         } else {
 829                                 isc->numrdns--;
 830                                 /* stack is empty? */
 831                                 if ( !isc->numrdns )
 832                                         break;
 833                                 /* pop up to prev node */
 834                                 n = isc->numrdns - 1;
 835                                 key.mv_data = &isc->scopes[n].mid;
 836                                 key.mv_size = sizeof(ID);
 837                                 data.mv_data = isc->nrdns[n].bv_val - 2;
 838                                 data.mv_size = 1;       /* just needs to be non-zero, mdb_dup_compare doesn't care */
 839                                 mdb_cursor_get( isc->mc, &key, &data, MDB_GET_BOTH );
 840                                 continue;
 841                         }
 842                 } else {
 843                         break;
 844                 }
 845         }
 846         return rc;
 847 }