git.sur5r.net Git - openldap/blob - servers/slapd/back-mdb/dn2id.c

   1 /* dn2id.c - routines to deal with the dn2id index */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2000-2011 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include "portable.h"
  18
  19 #include <stdio.h>
  20 #include <ac/string.h>
  21
  22 #include "back-mdb.h"
  23 #include "idl.h"
  24 #include "lutil.h"
  25
  26 /* Management routines for a hierarchically structured database.
  27  *
  28  * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each
  29  * entry in this database is a struct diskNode, keyed by entryID and with
  30  * the data containing the RDN and entryID of the node's children. We use
  31  * a B-Tree with sorted duplicates to store all the children of a node under
  32  * the same key. Also, the first item under the key contains the entry's own
  33  * rdn and the ID of the node's parent, to allow bottom-up tree traversal as
  34  * well as top-down. To keep this info first in the list, the high bit of all
  35  * subsequent nrdnlen's is always set. This means we can only accomodate
  36  * RDNs up to length 32767, but that's fine since full DNs are already
  37  * restricted to 8192.
  38  *
  39  * The diskNode is a variable length structure. This definition is not
  40  * directly usable for in-memory manipulation.
  41  */
  42 typedef struct diskNode {
  43         unsigned char nrdnlen[2];
  44         char nrdn[1];
  45         char rdn[1];                        /* variable placement */
  46         unsigned char entryID[sizeof(ID)];  /* variable placement */
  47 } diskNode;
  48
  49 /* Sort function for the sorted duplicate data items of a dn2id key.
  50  * Sorts based on normalized RDN, in length order.
  51  */
  52 int
  53 mdb_dup_compare(
  54         const MDB_val *usrkey,
  55         const MDB_val *curkey
  56 )
  57 {
  58         diskNode *un, *cn;
  59         int rc, nrlen;
  60
  61         un = (diskNode *)usrkey->mv_data;
  62         cn = (diskNode *)curkey->mv_data;
  63
  64         /* data is not aligned, cannot compare directly */
  65         rc = un->nrdnlen[0] - cn->nrdnlen[0];
  66         if ( rc ) return rc;
  67         rc = un->nrdnlen[1] - cn->nrdnlen[1];
  68         if ( rc ) return rc;
  69
  70         nrlen = (un->nrdnlen[0] << 8) | un->nrdnlen[1];
  71         return strncmp( un->nrdn, cn->nrdn, nrlen );
  72 }
  73
  74 #if 0
  75 /* This function constructs a full DN for a given entry.
  76  */
  77 int mdb_fix_dn(
  78         Entry *e,
  79         int checkit )
  80 {
  81         EntryInfo *ei;
  82         int rlen = 0, nrlen = 0;
  83         char *ptr, *nptr;
  84         int max = 0;
  85
  86         if ( !e->e_id )
  87                 return 0;
  88
  89         /* count length of all DN components */
  90         for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
  91                 rlen += ei->bei_rdn.bv_len + 1;
  92                 nrlen += ei->bei_nrdn.bv_len + 1;
  93                 if (ei->bei_modrdns > max) max = ei->bei_modrdns;
  94         }
  95
  96         /* See if the entry DN was invalidated by a subtree rename */
  97         if ( checkit ) {
  98                 if ( BEI(e)->bei_modrdns >= max ) {
  99                         return 0;
 100                 }
 101                 /* We found a mismatch, tell the caller to lock it */
 102                 if ( checkit == 1 ) {
 103                         return 1;
 104                 }
 105                 /* checkit == 2. do the fix. */
 106                 free( e->e_name.bv_val );
 107                 free( e->e_nname.bv_val );
 108         }
 109
 110         e->e_name.bv_len = rlen - 1;
 111         e->e_nname.bv_len = nrlen - 1;
 112         e->e_name.bv_val = ch_malloc(rlen);
 113         e->e_nname.bv_val = ch_malloc(nrlen);
 114         ptr = e->e_name.bv_val;
 115         nptr = e->e_nname.bv_val;
 116         for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) {
 117                 ptr = lutil_strcopy(ptr, ei->bei_rdn.bv_val);
 118                 nptr = lutil_strcopy(nptr, ei->bei_nrdn.bv_val);
 119                 if ( ei->bei_parent ) {
 120                         *ptr++ = ',';
 121                         *nptr++ = ',';
 122                 }
 123         }
 124         BEI(e)->bei_modrdns = max;
 125         if ( ptr > e->e_name.bv_val ) ptr[-1] = '\0';
 126         if ( nptr > e->e_nname.bv_val ) nptr[-1] = '\0';
 127
 128         return 0;
 129 }
 130 #endif
 131
 132 /* We add two elements to the DN2ID database - a data item under the parent's
 133  * entryID containing the child's RDN and entryID, and an item under the
 134  * child's entryID containing the parent's entryID.
 135  */
 136 int
 137 mdb_dn2id_add(
 138         Operation       *op,
 139         MDB_txn *txn,
 140         ID pid,
 141         Entry           *e )
 142 {
 143         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 144         MDB_dbi dbi = mdb->mi_dn2id;
 145         MDB_val         key, data;
 146         ID              nid;
 147         int             rc, rlen, nrlen;
 148         diskNode *d;
 149         char *ptr;
 150
 151         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_add 0x%lx: \"%s\"\n",
 152                 e->e_id, e->e_ndn, 0 );
 153
 154         nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
 155         if (nrlen) {
 156                 rlen = dn_rdnlen( op->o_bd, &e->e_name );
 157         } else {
 158                 nrlen = e->e_nname.bv_len;
 159                 rlen = e->e_name.bv_len;
 160         }
 161
 162         d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx);
 163         d->nrdnlen[1] = nrlen & 0xff;
 164         d->nrdnlen[0] = (nrlen >> 8) | 0x80;
 165         ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen );
 166         *ptr++ = '\0';
 167         ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen );
 168         *ptr++ = '\0';
 169         memcpy( ptr, &e->e_id, sizeof( ID ));
 170
 171         key.mv_size = sizeof(ID);
 172         key.mv_data = &nid;
 173
 174         nid = pid;
 175
 176         /* Need to make dummy root node once. Subsequent attempts
 177          * will fail harmlessly.
 178          */
 179         if ( pid == 0 ) {
 180                 diskNode dummy = {{0, 0}, "", "", ""};
 181                 data.mv_data = &dummy;
 182                 data.mv_size = sizeof(diskNode);
 183
 184                 mdb_put( txn, dbi, &key, &data, MDB_NODUPDATA );
 185         }
 186
 187         data.mv_data = d;
 188         data.mv_size = sizeof(diskNode) + rlen + nrlen;
 189
 190         rc = mdb_put( txn, dbi, &key, &data, MDB_NODUPDATA );
 191
 192         if (rc == 0) {
 193                 nid = e->e_id;
 194                 memcpy( ptr, &pid, sizeof( ID ));
 195                 d->nrdnlen[0] ^= 0x80;
 196
 197                 rc = mdb_put( txn, dbi, &key, &data, MDB_NODUPDATA );
 198         }
 199
 200         op->o_tmpfree( d, op->o_tmpmemctx );
 201         Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 );
 202
 203         return rc;
 204 }
 205
 206 int
 207 mdb_dn2id_delete(
 208         Operation       *op,
 209         MDB_txn *txn,
 210         ID pid,
 211         Entry   *e )
 212 {
 213         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 214         MDB_dbi dbi = mdb->mi_dn2id;
 215         MDB_val key, data;
 216         diskNode *d;
 217         int rc, nrlen;
 218         ID      nid;
 219
 220         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id_delete 0x%lx: \"%s\"\n",
 221                 e->e_id, e->e_ndn, 0 );
 222
 223         key.mv_size = sizeof(ID);
 224         key.mv_data = &nid;
 225         nid = pid;
 226
 227         nrlen = dn_rdnlen( op->o_bd, &e->e_nname );
 228         data.mv_size = sizeof(diskNode) + nrlen - sizeof(ID) - 1;
 229
 230         d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
 231         d->nrdnlen[1] = nrlen & 0xff;
 232         d->nrdnlen[0] = (nrlen >> 8) | 0x80;
 233         memcpy( d->nrdn, e->e_nname.bv_val, nrlen );
 234         data.mv_data = d;
 235
 236         /* Delete our ID from the parent's list */
 237         rc = mdb_del( txn, dbi, &key, &data, MDB_DEL_DUP );
 238
 239         /* Delete our ID from the tree. With sorted duplicates, this
 240          * will leave any child nodes still hanging around. This is OK
 241          * for modrdn, which will add our info back in later.
 242          */
 243         if ( rc == 0 ) {
 244                 nid = e->e_id;
 245                 d->nrdnlen[0] ^= 0x80;
 246                 rc = mdb_del( txn, dbi, &key, &data, MDB_DEL_DUP );
 247         }
 248
 249         op->o_tmpfree( d, op->o_tmpmemctx );
 250
 251         Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 );
 252         return rc;
 253 }
 254
 255 /* return last found ID in *id if no match */
 256 int
 257 mdb_dn2id(
 258         Operation       *op,
 259         MDB_txn *txn,
 260         struct berval   *in,
 261         ID      *id,
 262         struct berval   *matched )
 263 {
 264         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 265         MDB_cursor *cursor;
 266         MDB_dbi dbi = mdb->mi_dn2id;
 267         MDB_val         key, data;
 268         int             rc = 0, nrlen;
 269         diskNode *d;
 270         char    *ptr;
 271         char dn[SLAP_LDAPDN_MAXLEN];
 272         ID pid, nid;
 273         struct berval tmp;
 274
 275         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2id(\"%s\")\n", in->bv_val, 0, 0 );
 276
 277         if ( !in->bv_len ) {
 278                 *id = 0;
 279                 nid = 0;
 280                 goto done;
 281         }
 282
 283         tmp = *in;
 284
 285         if ( matched ) {
 286                 matched->bv_val = dn + sizeof(dn) - 1;
 287                 matched->bv_len = 0;
 288                 *matched->bv_val-- = '\0';
 289         }
 290
 291         nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
 292         tmp.bv_val += nrlen;
 293         tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
 294         nid = 0;
 295         key.mv_size = sizeof(ID);
 296
 297         rc = mdb_cursor_open( txn, dbi, &cursor );
 298         if ( rc ) return rc;
 299
 300         for (;;) {
 301                 key.mv_data = &pid;
 302                 pid = nid;
 303
 304                 data.mv_size = sizeof(diskNode) + tmp.bv_len;
 305                 d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
 306                 d->nrdnlen[1] = tmp.bv_len & 0xff;
 307                 d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
 308                 ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
 309                 *ptr = '\0';
 310                 data.mv_data = d;
 311                 rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
 312                 op->o_tmpfree( d, op->o_tmpmemctx );
 313                 if ( rc == MDB_NOTFOUND ) {
 314                         if ( matched && matched->bv_len ) {
 315                                 ptr = op->o_tmpalloc( matched->bv_len+1, op->o_tmpmemctx );
 316                                 strcpy( ptr, matched->bv_val );
 317                                 matched->bv_val = ptr;
 318                         }
 319                 }
 320                 if ( rc ) {
 321                         mdb_cursor_close( cursor );
 322                         break;
 323                 }
 324                 ptr = (char *) data.mv_data + data.mv_size - sizeof(ID);
 325                 memcpy( &nid, ptr, sizeof(ID));
 326
 327                 /* grab the non-normalized RDN */
 328                 if ( matched ) {
 329                         int rlen;
 330                         d = data.mv_data;
 331                         rlen = data.mv_size - sizeof(diskNode) - tmp.bv_len;
 332                         matched->bv_len += rlen;
 333                         matched->bv_val -= rlen + 1;
 334                         ptr = lutil_strcopy( matched->bv_val, d->rdn + tmp.bv_len );
 335                         if ( pid ) {
 336                                 *ptr = ',';
 337                                 matched->bv_len++;
 338                         }
 339                 }
 340                 if ( tmp.bv_val > in->bv_val ) {
 341                         for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
 342                                 !DN_SEPARATOR(*ptr); ptr--)     /* empty */;
 343                         if ( ptr >= in->bv_val ) {
 344                                 if (DN_SEPARATOR(*ptr)) ptr++;
 345                                 tmp.bv_len = tmp.bv_val - ptr - 1;
 346                                 tmp.bv_val = ptr;
 347                         }
 348                 } else {
 349                         break;
 350                 }
 351         }
 352         *id = nid;
 353
 354 done:
 355         if( rc != 0 ) {
 356                 Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: get failed: %s (%d)\n",
 357                         mdb_strerror( rc ), rc, 0 );
 358         } else {
 359                 Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: got id=0x%lx\n",
 360                         nid, 0, 0 );
 361         }
 362
 363         return rc;
 364 }
 365
 366 /* return IDs from root to parent of DN */
 367 int
 368 mdb_dn2sups(
 369         Operation       *op,
 370         MDB_txn *txn,
 371         struct berval   *in,
 372         ID      *ids )
 373 {
 374         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 375         MDB_cursor *cursor;
 376         MDB_dbi dbi = mdb->mi_dn2id;
 377         MDB_val         key, data;
 378         int             rc = 0, nrlen;
 379         diskNode *d;
 380         char    *ptr;
 381         ID pid, nid;
 382         struct berval tmp;
 383
 384         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2sups(\"%s\")\n", in->bv_val, 0, 0 );
 385
 386         if ( !in->bv_len ) {
 387                 goto done;
 388         }
 389
 390         tmp = *in;
 391
 392         nrlen = tmp.bv_len - op->o_bd->be_nsuffix[0].bv_len;
 393         tmp.bv_val += nrlen;
 394         tmp.bv_len = op->o_bd->be_nsuffix[0].bv_len;
 395         nid = 0;
 396         key.mv_size = sizeof(ID);
 397
 398         rc = mdb_cursor_open( txn, dbi, &cursor );
 399         if ( rc ) return rc;
 400
 401         for (;;) {
 402                 key.mv_data = &pid;
 403                 pid = nid;
 404
 405                 data.mv_size = sizeof(diskNode) + tmp.bv_len;
 406                 d = op->o_tmpalloc( data.mv_size, op->o_tmpmemctx );
 407                 d->nrdnlen[1] = tmp.bv_len & 0xff;
 408                 d->nrdnlen[0] = (tmp.bv_len >> 8) | 0x80;
 409                 ptr = lutil_strncopy( d->nrdn, tmp.bv_val, tmp.bv_len );
 410                 *ptr = '\0';
 411                 data.mv_data = d;
 412                 rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
 413                 op->o_tmpfree( d, op->o_tmpmemctx );
 414                 if ( rc ) {
 415                         mdb_cursor_close( cursor );
 416                         break;
 417                 }
 418                 ptr = (char *) data.mv_data + data.mv_size - sizeof(ID);
 419                 memcpy( &nid, ptr, sizeof(ID));
 420
 421                 if ( pid )
 422                         mdb_idl_insert( ids, pid );
 423
 424                 if ( tmp.bv_val > in->bv_val ) {
 425                         for (ptr = tmp.bv_val - 2; ptr > in->bv_val &&
 426                                 !DN_SEPARATOR(*ptr); ptr--)     /* empty */;
 427                         if ( ptr >= in->bv_val ) {
 428                                 if (DN_SEPARATOR(*ptr)) ptr++;
 429                                 tmp.bv_len = tmp.bv_val - ptr - 1;
 430                                 tmp.bv_val = ptr;
 431                         }
 432                 } else {
 433                         break;
 434                 }
 435         }
 436
 437 done:
 438         if( rc != 0 ) {
 439                 Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2sups: get failed: %s (%d)\n",
 440                         mdb_strerror( rc ), rc, 0 );
 441         }
 442
 443         return rc;
 444 }
 445
 446 #if 0
 447 int
 448 mdb_dn2id_parent(
 449         Operation *op,
 450         DB_TXN *txn,
 451         EntryInfo *ei,
 452         ID *idp )
 453 {
 454         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 455         DB *db = mdb->bi_dn2id->bdi_db;
 456         DBT             key, data;
 457         DBC     *cursor;
 458         int             rc = 0;
 459         diskNode *d;
 460         char    *ptr;
 461         ID      nid;
 462
 463         DBTzero(&key);
 464         key.size = sizeof(ID);
 465         key.data = &nid;
 466         key.ulen = sizeof(ID);
 467         key.flags = DB_DBT_USERMEM;
 468         MDB_ID2DISK( ei->bei_id, &nid );
 469
 470         DBTzero(&data);
 471         data.flags = DB_DBT_USERMEM;
 472
 473         rc = db->cursor( db, txn, &cursor, mdb->bi_db_opflags );
 474         if ( rc ) return rc;
 475
 476         data.ulen = sizeof(diskNode) + (SLAP_LDAPDN_MAXLEN * 2);
 477         d = op->o_tmpalloc( data.ulen, op->o_tmpmemctx );
 478         data.data = d;
 479
 480         rc = cursor->c_get( cursor, &key, &data, DB_SET );
 481         if ( rc == 0 ) {
 482                 if (d->nrdnlen[0] & 0x80) {
 483                         rc = LDAP_OTHER;
 484                 } else {
 485                         db_recno_t dkids;
 486                         ptr = (char *) data.data + data.size - sizeof(ID);
 487                         MDB_DISK2ID( ptr, idp );
 488                         ei->bei_nrdn.bv_len = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
 489                         ber_str2bv( d->nrdn, ei->bei_nrdn.bv_len, 1, &ei->bei_nrdn );
 490                         ei->bei_rdn.bv_len = data.size - sizeof(diskNode) -
 491                                 ei->bei_nrdn.bv_len;
 492                         ptr = d->nrdn + ei->bei_nrdn.bv_len + 1;
 493                         ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn );
 494                         /* How many children does this node have? */
 495                         cursor->c_count( cursor, &dkids, 0 );
 496                         ei->bei_dkids = dkids;
 497                 }
 498         }
 499         cursor->c_close( cursor );
 500         op->o_tmpfree( d, op->o_tmpmemctx );
 501         return rc;
 502 }
 503 #endif
 504
 505 int
 506 mdb_dn2id_children(
 507         Operation *op,
 508         MDB_txn *txn,
 509         Entry *e )
 510 {
 511         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 512         MDB_dbi dbi = mdb->mi_dn2id;
 513         MDB_val         key, data;
 514         MDB_cursor      *cursor;
 515         int             rc;
 516         ID              id;
 517
 518         key.mv_size = sizeof(ID);
 519         key.mv_data = &id;
 520         id = e->e_id;
 521
 522         rc = mdb_cursor_open( txn, dbi, &cursor );
 523         if ( rc ) return rc;
 524
 525         rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
 526         if ( rc == 0 ) {
 527                 unsigned long dkids;
 528                 rc = mdb_cursor_count( cursor, &dkids );
 529                 if ( rc == 0 ) {
 530                         if ( dkids < 2 ) rc = MDB_NOTFOUND;
 531                 }
 532         }
 533         mdb_cursor_close( cursor );
 534         return rc;
 535 }
 536
 537 int
 538 mdb_id2name(
 539         Operation *op,
 540         MDB_txn *txn,
 541         ID id,
 542         struct berval *name,
 543         struct berval *nname )
 544 {
 545         struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private;
 546         MDB_dbi dbi = mdb->mi_dn2id;
 547         MDB_val         key, data;
 548         MDB_cursor      *cursor;
 549         int             rc, len, nlen;
 550         char dn[SLAP_LDAPDN_MAXLEN], ndn[SLAP_LDAPDN_MAXLEN], *ptr;
 551         char *dptr, *nptr;
 552         diskNode *d;
 553
 554         key.mv_size = sizeof(ID);
 555
 556         rc = mdb_cursor_open( txn, dbi, &cursor );
 557         if ( rc ) return rc;
 558
 559         len = 0;
 560         nlen = 0;
 561         dptr = dn;
 562         nptr = ndn;
 563         while (id) {
 564                 int nrlen, rlen;
 565                 key.mv_data = &id;
 566                 data.mv_size = 0;
 567                 data.mv_data = "";
 568                 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
 569                 if ( rc ) break;
 570                 ptr = data.mv_data;
 571                 ptr += data.mv_size - sizeof(ID);
 572                 memcpy( &id, ptr, sizeof(ID) );
 573                 d = data.mv_data;
 574                 nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1];
 575                 if (nptr > ndn) {
 576                         *nptr++ = ',';
 577                         *dptr++ = ',';
 578                 }
 579                 /* copy name and trailing NUL */
 580                 memcpy( nptr, d->nrdn, nrlen+1 );
 581                 rlen = data.mv_size - sizeof(diskNode) - nrlen;
 582                 memcpy( dptr, d->nrdn+nrlen+1, rlen+1 );
 583                 nptr += nrlen;
 584                 dptr += rlen;
 585         }
 586         if ( rc == 0 ) {
 587                 name->bv_len = dptr - dn;
 588                 nname->bv_len = nptr - ndn;
 589                 name->bv_val = op->o_tmpalloc( name->bv_len + 1, op->o_tmpmemctx );
 590                 nname->bv_val = op->o_tmpalloc( nname->bv_len + 1, op->o_tmpmemctx );
 591                 memcpy( name->bv_val, dn, name->bv_len );
 592                 name->bv_val[name->bv_len] = '\0';
 593                 memcpy( nname->bv_val, ndn, nname->bv_len );
 594                 nname->bv_val[nname->bv_len] = '\0';
 595         }
 596         mdb_cursor_close( cursor );
 597         return rc;
 598 }
 599
 600 #if 0
 601 /* mdb_dn2idl:
 602  * We can't just use mdb_idl_fetch_key because
 603  * 1 - our data items are longer than just an entry ID
 604  * 2 - our data items are sorted alphabetically by nrdn, not by ID.
 605  *
 606  * We descend the tree recursively, so we define this cookie
 607  * to hold our necessary state information. The mdb_dn2idl_internal
 608  * function uses this cookie when calling itself.
 609  */
 610
 611 struct dn2id_cookie {
 612         struct mdb_info *mdb;
 613         Operation *op;
 614         DB_TXN *txn;
 615         EntryInfo *ei;
 616         ID *ids;
 617         ID *tmp;
 618         ID *buf;
 619         DB *db;
 620         DBC *dbc;
 621         DBT key;
 622         DBT data;
 623         ID dbuf;
 624         ID id;
 625         ID nid;
 626         int rc;
 627         int depth;
 628         char need_sort;
 629         char prefix;
 630 };
 631
 632 static int
 633 apply_func(
 634         void *data,
 635         void *arg )
 636 {
 637         EntryInfo *ei = data;
 638         ID *idl = arg;
 639
 640         mdb_idl_append_one( idl, ei->bei_id );
 641         return 0;
 642 }
 643
 644 static int
 645 mdb_dn2idl_internal(
 646         struct dn2id_cookie *cx
 647 )
 648 {
 649         MDB_IDL_ZERO( cx->tmp );
 650
 651         if ( cx->mdb->bi_idl_cache_size ) {
 652                 char *ptr = ((char *)&cx->id)-1;
 653
 654                 cx->key.data = ptr;
 655                 cx->key.size = sizeof(ID)+1;
 656                 if ( cx->prefix == DN_SUBTREE_PREFIX ) {
 657                         ID *ids = cx->depth ? cx->tmp : cx->ids;
 658                         *ptr = cx->prefix;
 659                         cx->rc = mdb_idl_cache_get(cx->mdb, cx->db, &cx->key, ids);
 660                         if ( cx->rc == LDAP_SUCCESS ) {
 661                                 if ( cx->depth ) {
 662                                         mdb_idl_append( cx->ids, cx->tmp );
 663                                         cx->need_sort = 1;
 664                                 }
 665                                 return cx->rc;
 666                         }
 667                 }
 668                 *ptr = DN_ONE_PREFIX;
 669                 cx->rc = mdb_idl_cache_get(cx->mdb, cx->db, &cx->key, cx->tmp);
 670                 if ( cx->rc == LDAP_SUCCESS ) {
 671                         goto gotit;
 672                 }
 673                 if ( cx->rc == DB_NOTFOUND ) {
 674                         return cx->rc;
 675                 }
 676         }
 677
 678         mdb_cache_entryinfo_lock( cx->ei );
 679
 680         /* If number of kids in the cache differs from on-disk, load
 681          * up all the kids from the database
 682          */
 683         if ( cx->ei->bei_ckids+1 != cx->ei->bei_dkids ) {
 684                 EntryInfo ei;
 685                 db_recno_t dkids = cx->ei->bei_dkids;
 686                 ei.bei_parent = cx->ei;
 687
 688                 /* Only one thread should load the cache */
 689                 while ( cx->ei->bei_state & CACHE_ENTRY_ONELEVEL ) {
 690                         mdb_cache_entryinfo_unlock( cx->ei );
 691                         ldap_pvt_thread_yield();
 692                         mdb_cache_entryinfo_lock( cx->ei );
 693                         if ( cx->ei->bei_ckids+1 == cx->ei->bei_dkids ) {
 694                                 goto synced;
 695                         }
 696                 }
 697
 698                 cx->ei->bei_state |= CACHE_ENTRY_ONELEVEL;
 699
 700                 mdb_cache_entryinfo_unlock( cx->ei );
 701
 702                 cx->rc = cx->db->cursor( cx->db, NULL, &cx->dbc,
 703                         cx->mdb->bi_db_opflags );
 704                 if ( cx->rc )
 705                         goto done_one;
 706
 707                 cx->data.data = &cx->dbuf;
 708                 cx->data.ulen = sizeof(ID);
 709                 cx->data.dlen = sizeof(ID);
 710                 cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
 711
 712                 /* The first item holds the parent ID. Ignore it. */
 713                 cx->key.data = &cx->nid;
 714                 cx->key.size = sizeof(ID);
 715                 cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET );
 716                 if ( cx->rc ) {
 717                         cx->dbc->c_close( cx->dbc );
 718                         goto done_one;
 719                 }
 720
 721                 /* If the on-disk count is zero we've never checked it.
 722                  * Count it now.
 723                  */
 724                 if ( !dkids ) {
 725                         cx->dbc->c_count( cx->dbc, &dkids, 0 );
 726                         cx->ei->bei_dkids = dkids;
 727                 }
 728
 729                 cx->data.data = cx->buf;
 730                 cx->data.ulen = MDB_IDL_UM_SIZE * sizeof(ID);
 731                 cx->data.flags = DB_DBT_USERMEM;
 732
 733                 if ( dkids > 1 ) {
 734                         /* Fetch the rest of the IDs in a loop... */
 735                         while ( (cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data,
 736                                 DB_MULTIPLE | DB_NEXT_DUP )) == 0 ) {
 737                                 u_int8_t *j;
 738                                 size_t len;
 739                                 void *ptr;
 740                                 DB_MULTIPLE_INIT( ptr, &cx->data );
 741                                 while (ptr) {
 742                                         DB_MULTIPLE_NEXT( ptr, &cx->data, j, len );
 743                                         if (j) {
 744                                                 EntryInfo *ei2;
 745                                                 diskNode *d = (diskNode *)j;
 746                                                 short nrlen;
 747
 748                                                 MDB_DISK2ID( j + len - sizeof(ID), &ei.bei_id );
 749                                                 nrlen = ((d->nrdnlen[0] ^ 0x80) << 8) | d->nrdnlen[1];
 750                                                 ei.bei_nrdn.bv_len = nrlen;
 751                                                 /* nrdn/rdn are set in-place.
 752                                                  * mdb_cache_load will copy them as needed
 753                                                  */
 754                                                 ei.bei_nrdn.bv_val = d->nrdn;
 755                                                 ei.bei_rdn.bv_len = len - sizeof(diskNode)
 756                                                         - ei.bei_nrdn.bv_len;
 757                                                 ei.bei_rdn.bv_val = d->nrdn + ei.bei_nrdn.bv_len + 1;
 758                                                 mdb_idl_append_one( cx->tmp, ei.bei_id );
 759                                                 mdb_cache_load( cx->mdb, &ei, &ei2 );
 760                                         }
 761                                 }
 762                         }
 763                 }
 764
 765                 cx->rc = cx->dbc->c_close( cx->dbc );
 766 done_one:
 767                 mdb_cache_entryinfo_lock( cx->ei );
 768                 cx->ei->bei_state &= ~CACHE_ENTRY_ONELEVEL;
 769                 mdb_cache_entryinfo_unlock( cx->ei );
 770                 if ( cx->rc )
 771                         return cx->rc;
 772
 773         } else {
 774                 /* The in-memory cache is in sync with the on-disk data.
 775                  * do we have any kids?
 776                  */
 777 synced:
 778                 cx->rc = 0;
 779                 if ( cx->ei->bei_ckids > 0 ) {
 780                         /* Walk the kids tree; order is irrelevant since mdb_idl_sort
 781                          * will sort it later.
 782                          */
 783                         avl_apply( cx->ei->bei_kids, apply_func,
 784                                 cx->tmp, -1, AVL_POSTORDER );
 785                 }
 786                 mdb_cache_entryinfo_unlock( cx->ei );
 787         }
 788
 789         if ( !MDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 3 )
 790                 mdb_idl_sort( cx->tmp, cx->buf );
 791         if ( cx->mdb->bi_idl_cache_max_size && !MDB_IDL_IS_ZERO( cx->tmp )) {
 792                 char *ptr = ((char *)&cx->id)-1;
 793                 cx->key.data = ptr;
 794                 cx->key.size = sizeof(ID)+1;
 795                 *ptr = DN_ONE_PREFIX;
 796                 mdb_idl_cache_put( cx->mdb, cx->db, &cx->key, cx->tmp, cx->rc );
 797         }
 798
 799 gotit:
 800         if ( !MDB_IDL_IS_ZERO( cx->tmp )) {
 801                 if ( cx->prefix == DN_SUBTREE_PREFIX ) {
 802                         mdb_idl_append( cx->ids, cx->tmp );
 803                         cx->need_sort = 1;
 804                         if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) {
 805                                 ID *save, idcurs;
 806                                 EntryInfo *ei = cx->ei;
 807                                 int nokids = 1;
 808                                 save = cx->op->o_tmpalloc( MDB_IDL_SIZEOF( cx->tmp ),
 809                                         cx->op->o_tmpmemctx );
 810                                 MDB_IDL_CPY( save, cx->tmp );
 811
 812                                 idcurs = 0;
 813                                 cx->depth++;
 814                                 for ( cx->id = mdb_idl_first( save, &idcurs );
 815                                         cx->id != NOID;
 816                                         cx->id = mdb_idl_next( save, &idcurs )) {
 817                                         EntryInfo *ei2;
 818                                         cx->ei = NULL;
 819                                         if ( mdb_cache_find_id( cx->op, cx->txn, cx->id, &cx->ei,
 820                                                 ID_NOENTRY, NULL ))
 821                                                 continue;
 822                                         if ( cx->ei ) {
 823                                                 ei2 = cx->ei;
 824                                                 if ( !( ei2->bei_state & CACHE_ENTRY_NO_KIDS )) {
 825                                                         MDB_ID2DISK( cx->id, &cx->nid );
 826                                                         mdb_dn2idl_internal( cx );
 827                                                         if ( !MDB_IDL_IS_ZERO( cx->tmp ))
 828                                                                 nokids = 0;
 829                                                 }
 830                                                 mdb_cache_entryinfo_lock( ei2 );
 831                                                 ei2->bei_finders--;
 832                                                 mdb_cache_entryinfo_unlock( ei2 );
 833                                         }
 834                                 }
 835                                 cx->depth--;
 836                                 cx->op->o_tmpfree( save, cx->op->o_tmpmemctx );
 837                                 if ( nokids ) {
 838                                         mdb_cache_entryinfo_lock( ei );
 839                                         ei->bei_state |= CACHE_ENTRY_NO_GRANDKIDS;
 840                                         mdb_cache_entryinfo_unlock( ei );
 841                                 }
 842                         }
 843                         /* Make sure caller knows it had kids! */
 844                         cx->tmp[0]=1;
 845
 846                         cx->rc = 0;
 847                 } else {
 848                         MDB_IDL_CPY( cx->ids, cx->tmp );
 849                 }
 850         }
 851         return cx->rc;
 852 }
 853
 854 int
 855 mdb_dn2idl(
 856         Operation       *op,
 857         DB_TXN *txn,
 858         struct berval *ndn,
 859         EntryInfo       *ei,
 860         ID *ids,
 861         ID *stack )
 862 {
 863         struct mdb_info *mdb = (struct mdb_info *)op->o_bd->be_private;
 864         struct dn2id_cookie cx;
 865
 866         Debug( LDAP_DEBUG_TRACE, "=> mdb_dn2idl(\"%s\")\n",
 867                 ndn->bv_val, 0, 0 );
 868
 869 #ifndef MDB_MULTIPLE_SUFFIXES
 870         if ( op->ors_scope != LDAP_SCOPE_ONELEVEL &&
 871                 ( ei->bei_id == 0 ||
 872                 ( ei->bei_parent->bei_id == 0 && op->o_bd->be_suffix[0].bv_len )))
 873         {
 874                 MDB_IDL_ALL( mdb, ids );
 875                 return 0;
 876         }
 877 #endif
 878
 879         cx.id = ei->bei_id;
 880         MDB_ID2DISK( cx.id, &cx.nid );
 881         cx.ei = ei;
 882         cx.mdb = mdb;
 883         cx.db = cx.mdb->bi_dn2id->bdi_db;
 884         cx.prefix = (op->ors_scope == LDAP_SCOPE_ONELEVEL) ?
 885                 DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
 886         cx.ids = ids;
 887         cx.tmp = stack;
 888         cx.buf = stack + MDB_IDL_UM_SIZE;
 889         cx.op = op;
 890         cx.txn = txn;
 891         cx.need_sort = 0;
 892         cx.depth = 0;
 893
 894         if ( cx.prefix == DN_SUBTREE_PREFIX ) {
 895                 ids[0] = 1;
 896                 ids[1] = cx.id;
 897         } else {
 898                 MDB_IDL_ZERO( ids );
 899         }
 900         if ( cx.ei->bei_state & CACHE_ENTRY_NO_KIDS )
 901                 return LDAP_SUCCESS;
 902
 903         DBTzero(&cx.key);
 904         cx.key.ulen = sizeof(ID);
 905         cx.key.size = sizeof(ID);
 906         cx.key.flags = DB_DBT_USERMEM;
 907
 908         DBTzero(&cx.data);
 909
 910         mdb_dn2idl_internal(&cx);
 911         if ( cx.need_sort ) {
 912                 char *ptr = ((char *)&cx.id)-1;
 913                 if ( !MDB_IDL_IS_RANGE( cx.ids ) && cx.ids[0] > 3 )
 914                         mdb_idl_sort( cx.ids, cx.tmp );
 915                 cx.key.data = ptr;
 916                 cx.key.size = sizeof(ID)+1;
 917                 *ptr = cx.prefix;
 918                 cx.id = ei->bei_id;
 919                 if ( cx.mdb->bi_idl_cache_max_size )
 920                         mdb_idl_cache_put( cx.mdb, cx.db, &cx.key, cx.ids, cx.rc );
 921         }
 922
 923         if ( cx.rc == DB_NOTFOUND )
 924                 cx.rc = LDAP_SUCCESS;
 925
 926         return cx.rc;
 927 }
 928 #endif