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