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