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