Back to index

openldap  2.4.31
dn2id.c
Go to the documentation of this file.
00001 /* dn2id.c - routines to deal with the dn2id index */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 2000-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in the file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 
00017 #include "portable.h"
00018 
00019 #include <stdio.h>
00020 #include <ac/string.h>
00021 
00022 #include "back-mdb.h"
00023 #include "idl.h"
00024 #include "lutil.h"
00025 
00026 /* Management routines for a hierarchically structured database.
00027  *
00028  * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each
00029  * entry in this database is a struct diskNode, keyed by entryID and with
00030  * the data containing the RDN and entryID of the node's children. We use
00031  * a B-Tree with sorted duplicates to store all the children of a node under
00032  * the same key. Also, the first item under the key contains the entry's own
00033  * rdn and the ID of the node's parent, to allow bottom-up tree traversal as
00034  * well as top-down. To keep this info first in the list, the high bit of all
00035  * subsequent nrdnlen's is always set. This means we can only accomodate
00036  * RDNs up to length 32767, but that's fine since full DNs are already
00037  * restricted to 8192.
00038  *
00039  * The diskNode is a variable length structure. This definition is not
00040  * directly usable for in-memory manipulation.
00041  */
00042 typedef struct diskNode {
00043        unsigned char nrdnlen[2];
00044        char nrdn[1];
00045        char rdn[1];                        /* variable placement */
00046        unsigned char entryID[sizeof(ID)];  /* variable placement */
00047 } diskNode;
00048 
00049 /* Sort function for the sorted duplicate data items of a dn2id key.
00050  * Sorts based on normalized RDN, in length order.
00051  */
00052 int
00053 mdb_dup_compare(
00054        const MDB_val *usrkey,
00055        const MDB_val *curkey
00056 )
00057 {
00058        diskNode *un, *cn;
00059        int rc, nrlen;
00060 
00061        un = (diskNode *)usrkey->mv_data;
00062        cn = (diskNode *)curkey->mv_data;
00063 
00064        /* data is not aligned, cannot compare directly */
00065        rc = un->nrdnlen[0] - cn->nrdnlen[0];
00066        if ( rc ) return rc;
00067        rc = un->nrdnlen[1] - cn->nrdnlen[1];
00068        if ( rc ) return rc;
00069 
00070        nrlen = (un->nrdnlen[0] << 8) | un->nrdnlen[1];
00071        return strncmp( un->nrdn, cn->nrdn, nrlen );
00072 }
00073 
00074 #if 0
00075 /* This function constructs a full DN for a given entry.
00076  */
00077 int mdb_fix_dn(
00078        Entry *e,
00079        int checkit )
00080 {
00081        EntryInfo *ei;
00082        int rlen = 0, nrlen = 0;
00083        char *ptr, *nptr;
00084        int max = 0;
00085 
00086        if ( !e->e_id )
00087               return 0;
00088 
00089        /* count length of all DN components */
00090        for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
00091               rlen += ei->bei_rdn.bv_len + 1;
00092               nrlen += ei->bei_nrdn.bv_len + 1;
00093               if (ei->bei_modrdns > max) max = ei->bei_modrdns;
00094        }
00095 
00096        /* See if the entry DN was invalidated by a subtree rename */
00097        if ( checkit ) {
00098               if ( BEI(e)->bei_modrdns >= max ) {
00099                      return 0;
00100               }
00101               /* We found a mismatch, tell the caller to lock it */
00102               if ( checkit == 1 ) {
00103                      return 1;
00104               }
00105               /* checkit == 2. do the fix. */
00106               free( e->e_name.bv_val );
00107               free( e->e_nname.bv_val );
00108        }
00109 
00110        e->e_name.bv_len = rlen - 1;
00111        e->e_nname.bv_len = nrlen - 1;
00112        e->e_name.bv_val = ch_malloc(rlen);
00113        e->e_nname.bv_val = ch_malloc(nrlen);
00114        ptr = e->e_name.bv_val;
00115        nptr = e->e_nname.bv_val;
00116        for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
00117               ptr = lutil_strcopy(ptr, ei->bei_rdn.bv_val);
00118               nptr = lutil_strcopy(nptr, ei->bei_nrdn.bv_val);
00119               if ( ei->bei_parent ) {
00120                      *ptr++ = ',';
00121                      *nptr++ = ',';
00122               }
00123        }
00124        BEI(e)->bei_modrdns = max;
00125        if ( ptr > e->e_name.bv_val ) ptr[-1] = '\0';
00126        if ( nptr > e->e_nname.bv_val ) nptr[-1] = '\0';
00127 
00128        return 0;
00129 }
00130 #endif
00131 
00132 /* We add two elements to the DN2ID database - a data item under the parent's
00133  * entryID containing the child's RDN and entryID, and an item under the
00134  * child's entryID containing the parent's entryID.
00135  */
00136 int
00137 mdb_dn2id_add(
00138        Operation     *op,
00139        MDB_cursor    *mcp,
00140        MDB_cursor    *mcd,
00141        ID pid,
00142        Entry         *e )
00143 {
00144        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00145        MDB_val              key, data;
00146        ID            nid;
00147        int           rc, rlen, nrlen;
00148        diskNode *d;
00149        char *ptr;
00150 
00151        Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_add 0x%lx: \"%s\"\n",
00152               e->e_id, e->e_ndn ? e->e_ndn : "", 0 );
00153 
00154        nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
00155        if (nrlen) {
00156               rlen = dn_rdnlen( op->o_bd, &e->e_name );
00157        } else {
00158               nrlen = e->e_nname.bv_len;
00159               rlen = e->e_name.bv_len;
00160        }
00161 
00162        d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx);
00163        d->nrdnlen[1] = nrlen & 0xff;
00164        d->nrdnlen[0] = (nrlen >> 8) | 0x80;
00165        ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
00166        *ptr++ = '\0';
00167        ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
00168        *ptr++ = '\0';
00169        memcpy( ptr, &e->e_id, sizeof( ID ));
00170 
00171        key.mv_size = sizeof(ID);
00172        key.mv_data = &nid;
00173 
00174        nid = pid;
00175 
00176        /* Need to make dummy root node once. Subsequent attempts
00177         * will fail harmlessly.
00178         */
00179        if ( pid == 0 ) {
00180               diskNode dummy = {{0, 0}, "", "", ""};
00181               data.mv_data = &dummy;
00182               data.mv_size = sizeof(diskNode);
00183 
00184               mdb_cursor_put( mcp, &key, &data, MDB_NODUPDATA );
00185        }
00186 
00187        data.mv_data = d;
00188        data.mv_size = sizeof(diskNode) + rlen + nrlen;
00189 
00190        rc = mdb_cursor_put( mcp, &key, &data, MDB_NODUPDATA );
00191 
00192        if (rc == 0) {
00193               int flag = MDB_NODUPDATA;
00194               nid = e->e_id;
00195               memcpy( ptr, &pid, sizeof( ID ));
00196               d->nrdnlen[0] ^= 0x80;
00197 
00198               if (slapMode & SLAP_TOOL_MODE)
00199                      flag |= MDB_APPEND;
00200               rc = mdb_cursor_put( mcd, &key, &data, flag );
00201        }
00202 
00203 fail:
00204        op->o_tmpfree( d, op->o_tmpmemctx );
00205        Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
00206 
00207        return rc;
00208 }
00209 
00210 /* mc must have been set by mdb_dn2id */
00211 int
00212 mdb_dn2id_delete(
00213        Operation     *op,
00214        MDB_cursor *mc,
00215        ID id )
00216 {
00217        int rc;
00218 
00219        Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_delete 0x%lx\n",
00220               id, 0, 0 );
00221 
00222        /* Delete our ID from the parent's list */
00223        rc = mdb_cursor_del( mc, 0 );
00224 
00225        /* Delete our ID from the tree. With sorted duplicates, this
00226         * will leave any child nodes still hanging around. This is OK
00227         * for modrdn, which will add our info back in later.
00228         */
00229        if ( rc == 0 ) {
00230               MDB_val       key;
00231               key.mv_size = sizeof(ID);
00232               key.mv_data = &id;
00233               rc = mdb_cursor_get( mc, &key, NULL, MDB_SET );
00234               if ( rc == 0 )
00235                      rc = mdb_cursor_del( mc, 0 );
00236        }
00237 
00238        Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_delete 0x%lx: %d\n", id, rc, 0 );
00239        return rc;
00240 }
00241 
00242 /* return last found ID in *id if no match
00243  * If mc is provided, it will be left pointing to the RDN's
00244  * record under the parent's ID.
00245  */
00246 int
00247 mdb_dn2id(
00248        Operation     *op,
00249        MDB_txn *txn,
00250        MDB_cursor    *mc,
00251        struct berval *in,
00252        ID     *id,
00253        struct berval *matched,
00254        struct berval *nmatched )
00255 {
00256        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00257        MDB_cursor *cursor;
00258        MDB_dbi dbi = mdb->mi_dn2id;
00259        MDB_val              key, data;
00260        int           rc = 0, nrlen;
00261        diskNode *d;
00262        char   *ptr;
00263        char dn[SLAP_LDAPDN_MAXLEN];
00264        ID pid, nid;
00265        struct berval tmp;
00266 
00267        Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id(\"%s\")\n", in->bv_val ? in->bv_val : "", 0, 0 );
00268 
00269        if ( matched ) {
00270               matched->bv_val = dn + sizeof(dn) - 1;
00271               matched->bv_len = 0;
00272               *matched->bv_val-- = '\0';
00273        }
00274        if ( nmatched ) {
00275               nmatched->bv_len = 0;
00276               nmatched->bv_val = 0;
00277        }
00278 
00279        if ( !in->bv_len ) {
00280               *id = 0;
00281               nid = 0;
00282               goto done;
00283        }
00284 
00285        tmp = *in;
00286 
00287        if ( op->o_bd->be_nsuffix[0].bv_len ) {
00288               nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
00289               tmp.bv_val += nrlen;
00290               tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
00291        } else {
00292               for ( ptr = tmp.bv_val + tmp.bv_len - 1; ptr >= tmp.bv_val; ptr-- )
00293                      if (DN_SEPARATOR(*ptr))
00294                             break;
00295               ptr++;
00296               tmp.bv_len -= ptr - tmp.bv_val;
00297               tmp.bv_val = ptr;
00298        }
00299        nid = 0;
00300        key.mv_size = sizeof(ID);
00301 
00302        if ( mc ) {
00303               cursor = mc;
00304        } else {
00305               rc = mdb_cursor_open( txn, dbi, &cursor );
00306               if ( rc ) return rc;
00307        }
00308 
00309        for (;;) {
00310               key.mv_data = &pid;
00311               pid = nid;
00312 
00313               data.mv_size = sizeof(diskNode) + tmp.bv_len;
00314               d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
00315               d->nrdnlen[1] = tmp.bv_len & 0xff;
00316               d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
00317               ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
00318               *ptr = '\0';
00319               data.mv_data = d;
00320               rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
00321               op->o_tmpfree( d, op->o_tmpmemctx );
00322               if ( rc )
00323                      break;
00324               ptr = (char *) data.mv_data + data.mv_size - sizeof(ID);
00325               memcpy( &nid, ptr, sizeof(ID));
00326 
00327               /* grab the non-normalized RDN */
00328               if ( matched ) {
00329                      int rlen;
00330                      d = data.mv_data;
00331                      rlen = data.mv_size - sizeof(diskNode) - tmp.bv_len;
00332                      matched->bv_len += rlen;
00333                      matched->bv_val -= rlen + 1;
00334                      ptr = lutil_strcopy( matched->bv_val, d->rdn + tmp.bv_len );
00335                      if ( pid ) {
00336                             *ptr = ',';
00337                             matched->bv_len++;
00338                      }
00339               }
00340               if ( nmatched ) {
00341                      nmatched->bv_val = tmp.bv_val;
00342               }
00343 
00344               if ( tmp.bv_val > in->bv_val ) {
00345                      for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
00346                             !DN_SEPARATOR(*ptr); ptr--) /* empty */;
00347                      if ( ptr >= in->bv_val ) {
00348                             if (DN_SEPARATOR(*ptr)) ptr++;
00349                             tmp.bv_len = tmp.bv_val - ptr - 1;
00350                             tmp.bv_val = ptr;
00351                      }
00352               } else {
00353                      break;
00354               }
00355        }
00356        *id = nid; 
00357        if ( !mc )
00358               mdb_cursor_close( cursor );
00359 done:
00360        if ( matched ) {
00361               if ( matched->bv_len ) {
00362                      ptr = op->o_tmpalloc( matched->bv_len+1, op->o_tmpmemctx );
00363                      strcpy( ptr, matched->bv_val );
00364                      matched->bv_val = ptr;
00365               } else {
00366                      if ( BER_BVISEMPTY( &op->o_bd->be_nsuffix[0] ) && !nid ) {
00367                             ber_dupbv( matched, (struct berval *)&slap_empty_bv );
00368                      } else {
00369                             matched->bv_val = NULL;
00370                      }
00371               }
00372        }
00373        if ( nmatched ) {
00374               if ( nmatched->bv_val ) {
00375                      nmatched->bv_len = in->bv_len - (nmatched->bv_val - in->bv_val);
00376               } else {
00377                      *nmatched = slap_empty_bv;
00378               }
00379        }
00380 
00381        if( rc != 0 ) {
00382               Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: get failed: %s (%d)\n",
00383                      mdb_strerror( rc ), rc, 0 );
00384        } else {
00385               Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: got id=0x%lx\n",
00386                      nid, 0, 0 );
00387        }
00388 
00389        return rc;
00390 }
00391 
00392 /* return IDs from root to parent of DN */
00393 int
00394 mdb_dn2sups(
00395        Operation     *op,
00396        MDB_txn *txn,
00397        struct berval *in,
00398        ID     *ids )
00399 {
00400        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00401        MDB_cursor *cursor;
00402        MDB_dbi dbi = mdb->mi_dn2id;
00403        MDB_val              key, data;
00404        int           rc = 0, nrlen;
00405        diskNode *d;
00406        char   *ptr;
00407        ID pid, nid;
00408        struct berval tmp;
00409 
00410        Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2sups(\"%s\")\n", in->bv_val, 0, 0 );
00411 
00412        if ( !in->bv_len ) {
00413               goto done;
00414        }
00415 
00416        tmp = *in;
00417 
00418        nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
00419        tmp.bv_val += nrlen;
00420        tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
00421        nid = 0;
00422        key.mv_size = sizeof(ID);
00423 
00424        rc = mdb_cursor_open( txn, dbi, &cursor );
00425        if ( rc ) return rc;
00426 
00427        for (;;) {
00428               key.mv_data = &pid;
00429               pid = nid;
00430 
00431               data.mv_size = sizeof(diskNode) + tmp.bv_len;
00432               d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
00433               d->nrdnlen[1] = tmp.bv_len & 0xff;
00434               d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
00435               ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
00436               *ptr = '\0';
00437               data.mv_data = d;
00438               rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
00439               op->o_tmpfree( d, op->o_tmpmemctx );
00440               if ( rc ) {
00441                      mdb_cursor_close( cursor );
00442                      break;
00443               }
00444               ptr = (char *) data.mv_data + data.mv_size - sizeof(ID);
00445               memcpy( &nid, ptr, sizeof(ID));
00446 
00447               if ( pid )
00448                      mdb_idl_insert( ids, pid );
00449 
00450               if ( tmp.bv_val > in->bv_val ) {
00451                      for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
00452                             !DN_SEPARATOR(*ptr); ptr--) /* empty */;
00453                      if ( ptr >= in->bv_val ) {
00454                             if (DN_SEPARATOR(*ptr)) ptr++;
00455                             tmp.bv_len = tmp.bv_val - ptr - 1;
00456                             tmp.bv_val = ptr;
00457                      }
00458               } else {
00459                      break;
00460               }
00461        }
00462 
00463 done:
00464        if( rc != 0 ) {
00465               Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2sups: get failed: %s (%d)\n",
00466                      mdb_strerror( rc ), rc, 0 );
00467        }
00468 
00469        return rc;
00470 }
00471 
00472 #if 0
00473 int
00474 mdb_dn2id_parent(
00475        Operation *op,
00476        DB_TXN *txn,
00477        EntryInfo *ei,
00478        ID *idp )
00479 {
00480        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00481        DB *db = mdb->bi_dn2id->bdi_db;
00482        DBT           key, data;
00483        DBC    *cursor;
00484        int           rc = 0;
00485        diskNode *d;
00486        char   *ptr;
00487        ID     nid;
00488 
00489        DBTzero(&key);
00490        key.size = sizeof(ID);
00491        key.data = &nid;
00492        key.ulen = sizeof(ID);
00493        key.flags = DB_DBT_USERMEM;
00494        MDB_ID2DISK( ei->bei_id, &nid );
00495 
00496        DBTzero(&data);
00497        data.flags = DB_DBT_USERMEM;
00498 
00499        rc = db->cursor( db, txn, &cursor, mdb->bi_db_opflags );
00500        if ( rc ) return rc;
00501 
00502        data.ulen = sizeof(diskNode) + (SLAP_LDAPDN_MAXLEN * 2);
00503        d = op->o_tmpalloc( data.ulen, op->o_tmpmemctx );
00504        data.data = d;
00505 
00506        rc = cursor->c_get( cursor, &key, &data, DB_SET );
00507        if ( rc == 0 ) {
00508               if (d->nrdnlen[0] & 0x80) {
00509                      rc = LDAP_OTHER;
00510               } else {
00511                      db_recno_t dkids;
00512                      ptr = (char *) data.data + data.size - sizeof(ID);
00513                      MDB_DISK2ID( ptr, idp );
00514                      ei->bei_nrdn.bv_len = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
00515                      ber_str2bv( d->nrdn, ei->bei_nrdn.bv_len, 1, &ei->bei_nrdn );
00516                      ei->bei_rdn.bv_len = data.size - sizeof(diskNode) -
00517                             ei->bei_nrdn.bv_len;
00518                      ptr = d->nrdn + ei->bei_nrdn.bv_len + 1;
00519                      ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
00520                      /* How many children does this node have? */
00521                      cursor->c_count( cursor, &dkids, 0 );
00522                      ei->bei_dkids = dkids;
00523               }
00524        }
00525        cursor->c_close( cursor );
00526        op->o_tmpfree( d, op->o_tmpmemctx );
00527        return rc;
00528 }
00529 #endif
00530 
00531 int
00532 mdb_dn2id_children(
00533        Operation *op,
00534        MDB_txn *txn,
00535        Entry *e )
00536 {
00537        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00538        MDB_dbi dbi = mdb->mi_dn2id;
00539        MDB_val              key, data;
00540        MDB_cursor    *cursor;
00541        int           rc;
00542        ID            id;
00543 
00544        key.mv_size = sizeof(ID);
00545        key.mv_data = &id;
00546        id = e->e_id;
00547 
00548        rc = mdb_cursor_open( txn, dbi, &cursor );
00549        if ( rc ) return rc;
00550 
00551        rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
00552        if ( rc == 0 ) {
00553               size_t dkids;
00554               rc = mdb_cursor_count( cursor, &dkids );
00555               if ( rc == 0 ) {
00556                      if ( dkids < 2 ) rc = MDB_NOTFOUND;
00557               }
00558        }
00559        mdb_cursor_close( cursor );
00560        return rc;
00561 }
00562 
00563 int
00564 mdb_id2name(
00565        Operation *op,
00566        MDB_txn *txn,
00567        MDB_cursor **cursp,
00568        ID id,
00569        struct berval *name,
00570        struct berval *nname )
00571 {
00572        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00573        MDB_dbi dbi = mdb->mi_dn2id;
00574        MDB_val              key, data;
00575        MDB_cursor    *cursor;
00576        int           rc, len, nlen;
00577        char dn[SLAP_LDAPDN_MAXLEN], ndn[SLAP_LDAPDN_MAXLEN], *ptr;
00578        char *dptr, *nptr;
00579        diskNode *d;
00580 
00581        key.mv_size = sizeof(ID);
00582 
00583        if ( !*cursp ) {
00584               rc = mdb_cursor_open( txn, dbi, cursp );
00585               if ( rc ) return rc;
00586        }
00587        cursor = *cursp;
00588 
00589        len = 0;
00590        nlen = 0;
00591        dptr = dn;
00592        nptr = ndn;
00593        while (id) {
00594               unsigned int nrlen, rlen;
00595               key.mv_data = &id;
00596               data.mv_size = 0;
00597               data.mv_data = "";
00598               rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
00599               if ( rc ) break;
00600               ptr = data.mv_data;
00601               ptr += data.mv_size - sizeof(ID);
00602               memcpy( &id, ptr, sizeof(ID) );
00603               d = data.mv_data;
00604               nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
00605               rlen = data.mv_size - sizeof(diskNode) - nrlen;
00606               assert( nrlen < 1024 && rlen < 1024 );    /* FIXME: Sanity check */
00607               if (nptr > ndn) {
00608                      *nptr++ = ',';
00609                      *dptr++ = ',';
00610               }
00611               /* copy name and trailing NUL */
00612               memcpy( nptr, d->nrdn, nrlen+1 );
00613               memcpy( dptr, d->nrdn+nrlen+1, rlen+1 );
00614               nptr += nrlen;
00615               dptr += rlen;
00616        }
00617        if ( rc == 0 ) {
00618               name->bv_len = dptr - dn;
00619               nname->bv_len = nptr - ndn;
00620               name->bv_val = op->o_tmpalloc( name->bv_len + 1, op->o_tmpmemctx );
00621               nname->bv_val = op->o_tmpalloc( nname->bv_len + 1, op->o_tmpmemctx );
00622               memcpy( name->bv_val, dn, name->bv_len );
00623               name->bv_val[name->bv_len] = '\0';
00624               memcpy( nname->bv_val, ndn, nname->bv_len );
00625               nname->bv_val[nname->bv_len] = '\0';
00626        }
00627        return rc;
00628 }
00629 
00630 /* Find each id in ids that is a child of base and move it to res.
00631  */
00632 int
00633 mdb_idscope(
00634        Operation *op,
00635        MDB_txn *txn,
00636        ID base,
00637        ID *ids,
00638        ID *res )
00639 {
00640        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00641        MDB_dbi dbi = mdb->mi_dn2id;
00642        MDB_val              key, data;
00643        MDB_cursor    *cursor;
00644        ID ida, id, cid, ci0, idc = 0;
00645        char   *ptr;
00646        int           rc;
00647 
00648        key.mv_size = sizeof(ID);
00649 
00650        MDB_IDL_ZERO( res );
00651 
00652        rc = mdb_cursor_open( txn, dbi, &cursor );
00653        if ( rc ) return rc;
00654 
00655        ida = mdb_idl_first( ids, &cid );
00656 
00657        /* Don't bother moving out of ids if it's a range */
00658        if (!MDB_IDL_IS_RANGE(ids)) {
00659               idc = ids[0];
00660               ci0 = cid;
00661        }
00662 
00663        while (ida != NOID) {
00664               id = ida;
00665               while (id) {
00666                      key.mv_data = &id;
00667                      rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
00668                      if ( rc ) {
00669                             /* not found, move on to next */
00670                             if (idc) {
00671                                    if (ci0 != cid)
00672                                           ids[ci0] = ids[cid];
00673                                    ci0++;
00674                             }
00675                             break;
00676                      }
00677                      ptr = data.mv_data;
00678                      ptr += data.mv_size - sizeof(ID);
00679                      memcpy( &id, ptr, sizeof(ID) );
00680                      if ( id == base ) {
00681                             res[0]++;
00682                             res[res[0]] = ida;
00683                             if (idc)
00684                                    idc--;
00685                             break;
00686                      } else {
00687                             if (idc) {
00688                                    if (ci0 != cid)
00689                                           ids[ci0] = ids[cid];
00690                                    ci0++;
00691                             }
00692                      }
00693                      if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
00694                             break;
00695               }
00696               ida = mdb_idl_next( ids, &cid );
00697        }
00698        if (!MDB_IDL_IS_RANGE( ids ))
00699               ids[0] = idc;
00700 
00701        mdb_cursor_close( cursor );
00702        return rc;
00703 }
00704 
00705 /* See if base is a child of any of the scopes
00706  */
00707 int
00708 mdb_idscopes(
00709        Operation *op,
00710        IdScopes *isc )
00711 {
00712        struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
00713        MDB_dbi dbi = mdb->mi_dn2id;
00714        MDB_val              key, data;
00715        ID id;
00716        ID2 id2;
00717        char   *ptr;
00718        int           rc = 0;
00719        unsigned int x;
00720        unsigned int nrlen, rlen;
00721        diskNode *d;
00722 
00723        key.mv_size = sizeof(ID);
00724 
00725        if ( !isc->mc ) {
00726               rc = mdb_cursor_open( isc->mt, dbi, &isc->mc );
00727               if ( rc ) return rc;
00728        }
00729 
00730        id = isc->id;
00731        while (id) {
00732               if ( !rc ) {
00733                      key.mv_data = &id;
00734                      rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET );
00735                      if ( rc )
00736                             break;
00737 
00738                      /* save RDN info */
00739               }
00740               d = data.mv_data;
00741               nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
00742               rlen = data.mv_size - sizeof(diskNode) - nrlen;
00743               isc->nrdns[isc->numrdns].bv_len = nrlen;
00744               isc->nrdns[isc->numrdns].bv_val = d->nrdn;
00745               isc->rdns[isc->numrdns].bv_len = rlen;
00746               isc->rdns[isc->numrdns].bv_val = d->nrdn+nrlen+1;
00747               isc->numrdns++;
00748 
00749               if (!rc && id != isc->id) {
00750                      id2.mid = id;
00751                      id2.mval = data;
00752                      mdb_id2l_insert( isc->scopes, &id2 );
00753               }
00754               ptr = data.mv_data;
00755               ptr += data.mv_size - sizeof(ID);
00756               memcpy( &id, ptr, sizeof(ID) );
00757               x = mdb_id2l_search( isc->scopes, id );
00758               if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) {
00759                      if ( !isc->scopes[x].mval.mv_data ) {
00760                             isc->nscope = x;
00761                             return MDB_SUCCESS;
00762                      }
00763                      data = isc->scopes[x].mval;
00764                      rc = 1;
00765               }
00766               if ( op->ors_scope == LDAP_SCOPE_ONELEVEL )
00767                      break;
00768        }
00769        return MDB_NOTFOUND;
00770 }
00771 
00772 #if 0
00773 /* mdb_dn2idl:
00774  * We can't just use mdb_idl_fetch_key because
00775  * 1 - our data items are longer than just an entry ID
00776  * 2 - our data items are sorted alphabetically by nrdn, not by ID.
00777  *
00778  * We descend the tree recursively, so we define this cookie
00779  * to hold our necessary state information. The mdb_dn2idl_internal
00780  * function uses this cookie when calling itself.
00781  */
00782 
00783 struct dn2id_cookie {
00784        struct mdb_info *mdb;
00785        Operation *op;
00786        DB_TXN *txn;
00787        EntryInfo *ei;
00788        ID *ids;
00789        ID *tmp;
00790        ID *buf;
00791        DB *db;
00792        DBC *dbc;
00793        DBT key;
00794        DBT data;
00795        ID dbuf;
00796        ID id;
00797        ID nid;
00798        int rc;
00799        int depth;
00800        char need_sort;
00801        char prefix;
00802 };
00803 
00804 static int
00805 apply_func(
00806        void *data,
00807        void *arg )
00808 {
00809        EntryInfo *ei = data;
00810        ID *idl = arg;
00811 
00812        mdb_idl_append_one( idl, ei->bei_id );
00813        return 0;
00814 }
00815 
00816 static int
00817 mdb_dn2idl_internal(
00818        struct dn2id_cookie *cx
00819 )
00820 {
00821        MDB_IDL_ZERO( cx->tmp );
00822 
00823        if ( cx->mdb->bi_idl_cache_size ) {
00824               char *ptr = ((char *)&cx->id)-1;
00825 
00826               cx->key.data = ptr;
00827               cx->key.size = sizeof(ID)+1;
00828               if ( cx->prefix == DN_SUBTREE_PREFIX ) {
00829                      ID *ids = cx->depth ? cx->tmp : cx->ids;
00830                      *ptr = cx->prefix;
00831                      cx->rc = mdb_idl_cache_get(cx->mdb, cx->db, &cx->key, ids);
00832                      if ( cx->rc == LDAP_SUCCESS ) {
00833                             if ( cx->depth ) {
00834                                    mdb_idl_append( cx->ids, cx->tmp );
00835                                    cx->need_sort = 1;
00836                             }
00837                             return cx->rc;
00838                      }
00839               }
00840               *ptr = DN_ONE_PREFIX;
00841               cx->rc = mdb_idl_cache_get(cx->mdb, cx->db, &cx->key, cx->tmp);
00842               if ( cx->rc == LDAP_SUCCESS ) {
00843                      goto gotit;
00844               }
00845               if ( cx->rc == DB_NOTFOUND ) {
00846                      return cx->rc;
00847               }
00848        }
00849 
00850        mdb_cache_entryinfo_lock( cx->ei );
00851 
00852        /* If number of kids in the cache differs from on-disk, load
00853         * up all the kids from the database
00854         */
00855        if ( cx->ei->bei_ckids+1 != cx->ei->bei_dkids ) {
00856               EntryInfo ei;
00857               db_recno_t dkids = cx->ei->bei_dkids;
00858               ei.bei_parent = cx->ei;
00859 
00860               /* Only one thread should load the cache */
00861               while ( cx->ei->bei_state & CACHE_ENTRY_ONELEVEL ) {
00862                      mdb_cache_entryinfo_unlock( cx->ei );
00863                      ldap_pvt_thread_yield();
00864                      mdb_cache_entryinfo_lock( cx->ei );
00865                      if ( cx->ei->bei_ckids+1 == cx->ei->bei_dkids ) {
00866                             goto synced;
00867                      }
00868               }
00869 
00870               cx->ei->bei_state |= CACHE_ENTRY_ONELEVEL;
00871 
00872               mdb_cache_entryinfo_unlock( cx->ei );
00873 
00874               cx->rc = cx->db->cursor( cx->db, NULL, &cx->dbc,
00875                      cx->mdb->bi_db_opflags );
00876               if ( cx->rc )
00877                      goto done_one;
00878 
00879               cx->data.data = &cx->dbuf;
00880               cx->data.ulen = sizeof(ID);
00881               cx->data.dlen = sizeof(ID);
00882               cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
00883 
00884               /* The first item holds the parent ID. Ignore it. */
00885               cx->key.data = &cx->nid;
00886               cx->key.size = sizeof(ID);
00887               cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET );
00888               if ( cx->rc ) {
00889                      cx->dbc->c_close( cx->dbc );
00890                      goto done_one;
00891               }
00892 
00893               /* If the on-disk count is zero we've never checked it.
00894                * Count it now.
00895                */
00896               if ( !dkids ) {
00897                      cx->dbc->c_count( cx->dbc, &dkids, 0 );
00898                      cx->ei->bei_dkids = dkids;
00899               }
00900 
00901               cx->data.data = cx->buf;
00902               cx->data.ulen = MDB_IDL_UM_SIZE * sizeof(ID);
00903               cx->data.flags = DB_DBT_USERMEM;
00904 
00905               if ( dkids > 1 ) {
00906                      /* Fetch the rest of the IDs in a loop... */
00907                      while ( (cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data,
00908                             DB_MULTIPLE | DB_NEXT_DUP )) == 0 ) {
00909                             uint8_t *j;
00910                             size_t len;
00911                             void *ptr;
00912                             DB_MULTIPLE_INIT( ptr, &cx->data );
00913                             while (ptr) {
00914                                    DB_MULTIPLE_NEXT( ptr, &cx->data, j, len );
00915                                    if (j) {
00916                                           EntryInfo *ei2;
00917                                           diskNode *d = (diskNode *)j;
00918                                           short nrlen;
00919 
00920                                           MDB_DISK2ID( j + len - sizeof(ID), &ei.bei_id );
00921                                           nrlen = ((d->nrdnlen[0] ^ 0x80) << 8) | d->nrdnlen[1];
00922                                           ei.bei_nrdn.bv_len = nrlen;
00923                                           /* nrdn/rdn are set in-place.
00924                                            * mdb_cache_load will copy them as needed
00925                                            */
00926                                           ei.bei_nrdn.bv_val = d->nrdn;
00927                                           ei.bei_rdn.bv_len = len - sizeof(diskNode)
00928                                                  - ei.bei_nrdn.bv_len;
00929                                           ei.bei_rdn.bv_val = d->nrdn + ei.bei_nrdn.bv_len + 1;
00930                                           mdb_idl_append_one( cx->tmp, ei.bei_id );
00931                                           mdb_cache_load( cx->mdb, &ei, &ei2 );
00932                                    }
00933                             }
00934                      }
00935               }
00936 
00937               cx->rc = cx->dbc->c_close( cx->dbc );
00938 done_one:
00939               mdb_cache_entryinfo_lock( cx->ei );
00940               cx->ei->bei_state &= ~CACHE_ENTRY_ONELEVEL;
00941               mdb_cache_entryinfo_unlock( cx->ei );
00942               if ( cx->rc )
00943                      return cx->rc;
00944 
00945        } else {
00946               /* The in-memory cache is in sync with the on-disk data.
00947                * do we have any kids?
00948                */
00949 synced:
00950               cx->rc = 0;
00951               if ( cx->ei->bei_ckids > 0 ) {
00952                      /* Walk the kids tree; order is irrelevant since mdb_idl_sort
00953                       * will sort it later.
00954                       */
00955                      avl_apply( cx->ei->bei_kids, apply_func,
00956                             cx->tmp, -1, AVL_POSTORDER );
00957               }
00958               mdb_cache_entryinfo_unlock( cx->ei );
00959        }
00960 
00961        if ( !MDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 3 )
00962               mdb_idl_sort( cx->tmp, cx->buf );
00963        if ( cx->mdb->bi_idl_cache_max_size && !MDB_IDL_IS_ZERO( cx->tmp )) {
00964               char *ptr = ((char *)&cx->id)-1;
00965               cx->key.data = ptr;
00966               cx->key.size = sizeof(ID)+1;
00967               *ptr = DN_ONE_PREFIX;
00968               mdb_idl_cache_put( cx->mdb, cx->db, &cx->key, cx->tmp, cx->rc );
00969        }
00970 
00971 gotit:
00972        if ( !MDB_IDL_IS_ZERO( cx->tmp )) {
00973               if ( cx->prefix == DN_SUBTREE_PREFIX ) {
00974                      mdb_idl_append( cx->ids, cx->tmp );
00975                      cx->need_sort = 1;
00976                      if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) {
00977                             ID *save, idcurs;
00978                             EntryInfo *ei = cx->ei;
00979                             int nokids = 1;
00980                             save = cx->op->o_tmpalloc( MDB_IDL_SIZEOF( cx->tmp ),
00981                                    cx->op->o_tmpmemctx );
00982                             MDB_IDL_CPY( save, cx->tmp );
00983 
00984                             idcurs = 0;
00985                             cx->depth++;
00986                             for ( cx->id = mdb_idl_first( save, &idcurs );
00987                                    cx->id != NOID;
00988                                    cx->id = mdb_idl_next( save, &idcurs )) {
00989                                    EntryInfo *ei2;
00990                                    cx->ei = NULL;
00991                                    if ( mdb_cache_find_id( cx->op, cx->txn, cx->id, &cx->ei,
00992                                           ID_NOENTRY, NULL ))
00993                                           continue;
00994                                    if ( cx->ei ) {
00995                                           ei2 = cx->ei;
00996                                           if ( !( ei2->bei_state & CACHE_ENTRY_NO_KIDS )) {
00997                                                  MDB_ID2DISK( cx->id, &cx->nid );
00998                                                  mdb_dn2idl_internal( cx );
00999                                                  if ( !MDB_IDL_IS_ZERO( cx->tmp ))
01000                                                         nokids = 0;
01001                                           }
01002                                           mdb_cache_entryinfo_lock( ei2 );
01003                                           ei2->bei_finders--;
01004                                           mdb_cache_entryinfo_unlock( ei2 );
01005                                    }
01006                             }
01007                             cx->depth--;
01008                             cx->op->o_tmpfree( save, cx->op->o_tmpmemctx );
01009                             if ( nokids ) {
01010                                    mdb_cache_entryinfo_lock( ei );
01011                                    ei->bei_state |= CACHE_ENTRY_NO_GRANDKIDS;
01012                                    mdb_cache_entryinfo_unlock( ei );
01013                             }
01014                      }
01015                      /* Make sure caller knows it had kids! */
01016                      cx->tmp[0]=1;
01017 
01018                      cx->rc = 0;
01019               } else {
01020                      MDB_IDL_CPY( cx->ids, cx->tmp );
01021               }
01022        }
01023        return cx->rc;
01024 }
01025 
01026 int
01027 mdb_dn2idl(
01028        Operation     *op,
01029        DB_TXN *txn,
01030        struct berval *ndn,
01031        EntryInfo     *ei,
01032        ID *ids,
01033        ID *stack )
01034 {
01035        struct mdb_info *mdb = (struct mdb_info *)op->o_bd->be_private;
01036        struct dn2id_cookie cx;
01037 
01038        Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2idl(\"%s\")\n",
01039               ndn->bv_val, 0, 0 );
01040 
01041 #ifndef MDB_MULTIPLE_SUFFIXES
01042        if ( op->ors_scope != LDAP_SCOPE_ONELEVEL && 
01043               ( ei->bei_id == 0 ||
01044               ( ei->bei_parent->bei_id == 0 && op->o_bd->be_suffix[0].bv_len )))
01045        {
01046               MDB_IDL_ALL( mdb, ids );
01047               return 0;
01048        }
01049 #endif
01050 
01051        cx.id = ei->bei_id;
01052        MDB_ID2DISK( cx.id, &cx.nid );
01053        cx.ei = ei;
01054        cx.mdb = mdb;
01055        cx.db = cx.mdb->bi_dn2id->bdi_db;
01056        cx.prefix = (op->ors_scope == LDAP_SCOPE_ONELEVEL) ?
01057               DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
01058        cx.ids = ids;
01059        cx.tmp = stack;
01060        cx.buf = stack + MDB_IDL_UM_SIZE;
01061        cx.op = op;
01062        cx.txn = txn;
01063        cx.need_sort = 0;
01064        cx.depth = 0;
01065 
01066        if ( cx.prefix == DN_SUBTREE_PREFIX ) {
01067               ids[0] = 1;
01068               ids[1] = cx.id;
01069        } else {
01070               MDB_IDL_ZERO( ids );
01071        }
01072        if ( cx.ei->bei_state & CACHE_ENTRY_NO_KIDS )
01073               return LDAP_SUCCESS;
01074 
01075        DBTzero(&cx.key);
01076        cx.key.ulen = sizeof(ID);
01077        cx.key.size = sizeof(ID);
01078        cx.key.flags = DB_DBT_USERMEM;
01079 
01080        DBTzero(&cx.data);
01081 
01082        mdb_dn2idl_internal(&cx);
01083        if ( cx.need_sort ) {
01084               char *ptr = ((char *)&cx.id)-1;
01085               if ( !MDB_IDL_IS_RANGE( cx.ids ) && cx.ids[0] > 3 ) 
01086                      mdb_idl_sort( cx.ids, cx.tmp );
01087               cx.key.data = ptr;
01088               cx.key.size = sizeof(ID)+1;
01089               *ptr = cx.prefix;
01090               cx.id = ei->bei_id;
01091               if ( cx.mdb->bi_idl_cache_max_size )
01092                      mdb_idl_cache_put( cx.mdb, cx.db, &cx.key, cx.ids, cx.rc );
01093        }
01094 
01095        if ( cx.rc == DB_NOTFOUND )
01096               cx.rc = LDAP_SUCCESS;
01097 
01098        return cx.rc;
01099 }
01100 #endif