1 /* $NetBSD: dn2id.c,v 1.1.1.3 2018/02/06 01:53:17 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-2017 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.1.1.3 2018/02/06 01:53:17 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 accomodate 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 : "", 0 ); 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, 0 ); 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, 0, 0 ); 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, 0 ); 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 : "", 0, 0 ); 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, 0 ); 437 } else { 438 Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2id: got id=0x%lx\n", 439 nid, 0, 0 ); 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, 0, 0 ); 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 mdb_cursor_close( cursor ); 495 break; 496 } 497 ptr = (char *) data.mv_data + data.mv_size - 2*sizeof(ID); 498 memcpy( &nid, ptr, sizeof(ID)); 499 500 if ( pid ) 501 mdb_idl_insert( ids, pid ); 502 503 if ( tmp.bv_val > in->bv_val ) { 504 for (ptr = tmp.bv_val - 2; ptr > in->bv_val && 505 !DN_SEPARATOR(*ptr); ptr--) /* empty */; 506 if ( ptr >= in->bv_val ) { 507 if (DN_SEPARATOR(*ptr)) ptr++; 508 tmp.bv_len = tmp.bv_val - ptr - 1; 509 tmp.bv_val = ptr; 510 } 511 } else { 512 break; 513 } 514 } 515 516 done: 517 if( rc != 0 ) { 518 Debug( LDAP_DEBUG_TRACE, "<= mdb_dn2sups: get failed: %s (%d)\n", 519 mdb_strerror( rc ), rc, 0 ); 520 } 521 522 return rc; 523 } 524 525 int 526 mdb_dn2id_children( 527 Operation *op, 528 MDB_txn *txn, 529 Entry *e ) 530 { 531 struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private; 532 MDB_dbi dbi = mdb->mi_dn2id; 533 MDB_val key, data; 534 MDB_cursor *cursor; 535 int rc; 536 ID id; 537 538 key.mv_size = sizeof(ID); 539 key.mv_data = &id; 540 id = e->e_id; 541 542 rc = mdb_cursor_open( txn, dbi, &cursor ); 543 if ( rc ) return rc; 544 545 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET ); 546 if ( rc == 0 ) { 547 size_t dkids; 548 rc = mdb_cursor_count( cursor, &dkids ); 549 if ( rc == 0 ) { 550 if ( dkids < 2 ) rc = MDB_NOTFOUND; 551 } 552 } 553 mdb_cursor_close( cursor ); 554 return rc; 555 } 556 557 int 558 mdb_id2name( 559 Operation *op, 560 MDB_txn *txn, 561 MDB_cursor **cursp, 562 ID id, 563 struct berval *name, 564 struct berval *nname ) 565 { 566 struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private; 567 MDB_dbi dbi = mdb->mi_dn2id; 568 MDB_val key, data; 569 MDB_cursor *cursor; 570 int rc, len, nlen; 571 char dn[SLAP_LDAPDN_MAXLEN], ndn[SLAP_LDAPDN_MAXLEN], *ptr; 572 char *dptr, *nptr; 573 diskNode *d; 574 575 key.mv_size = sizeof(ID); 576 577 if ( !*cursp ) { 578 rc = mdb_cursor_open( txn, dbi, cursp ); 579 if ( rc ) return rc; 580 } 581 cursor = *cursp; 582 583 len = 0; 584 nlen = 0; 585 dptr = dn; 586 nptr = ndn; 587 while (id) { 588 unsigned int nrlen, rlen; 589 key.mv_data = &id; 590 data.mv_size = 0; 591 data.mv_data = ""; 592 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET ); 593 if ( rc ) break; 594 ptr = data.mv_data; 595 ptr += data.mv_size - sizeof(ID); 596 memcpy( &id, ptr, sizeof(ID) ); 597 d = data.mv_data; 598 nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1]; 599 rlen = data.mv_size - sizeof(diskNode) - nrlen; 600 assert( nrlen < 1024 && rlen < 1024 ); /* FIXME: Sanity check */ 601 if (nptr > ndn) { 602 *nptr++ = ','; 603 *dptr++ = ','; 604 } 605 /* copy name and trailing NUL */ 606 memcpy( nptr, d->nrdn, nrlen+1 ); 607 memcpy( dptr, d->nrdn+nrlen+1, rlen+1 ); 608 nptr += nrlen; 609 dptr += rlen; 610 } 611 if ( rc == 0 ) { 612 name->bv_len = dptr - dn; 613 nname->bv_len = nptr - ndn; 614 name->bv_val = op->o_tmpalloc( name->bv_len + 1, op->o_tmpmemctx ); 615 nname->bv_val = op->o_tmpalloc( nname->bv_len + 1, op->o_tmpmemctx ); 616 memcpy( name->bv_val, dn, name->bv_len ); 617 name->bv_val[name->bv_len] = '\0'; 618 memcpy( nname->bv_val, ndn, nname->bv_len ); 619 nname->bv_val[nname->bv_len] = '\0'; 620 } 621 return rc; 622 } 623 624 /* Find each id in ids that is a child of base and move it to res. 625 */ 626 int 627 mdb_idscope( 628 Operation *op, 629 MDB_txn *txn, 630 ID base, 631 ID *ids, 632 ID *res ) 633 { 634 struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private; 635 MDB_dbi dbi = mdb->mi_dn2id; 636 MDB_val key, data; 637 MDB_cursor *cursor; 638 ID ida, id, cid = 0, ci0 = 0, idc = 0; 639 char *ptr; 640 int rc, copy; 641 642 key.mv_size = sizeof(ID); 643 644 MDB_IDL_ZERO( res ); 645 646 rc = mdb_cursor_open( txn, dbi, &cursor ); 647 if ( rc ) return rc; 648 649 ida = mdb_idl_first( ids, &cid ); 650 651 /* Don't bother moving out of ids if it's a range */ 652 if (!MDB_IDL_IS_RANGE(ids)) { 653 idc = ids[0]; 654 ci0 = cid; 655 } 656 657 while (ida != NOID) { 658 copy = 1; 659 id = ida; 660 while (id) { 661 key.mv_data = &id; 662 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET ); 663 if ( rc ) { 664 /* not found, drop this from ids */ 665 copy = 0; 666 break; 667 } 668 ptr = data.mv_data; 669 ptr += data.mv_size - sizeof(ID); 670 memcpy( &id, ptr, sizeof(ID) ); 671 if ( id == base ) { 672 if ( res[0] >= MDB_IDL_DB_SIZE-1 ) { 673 /* too many aliases in scope. Fallback to range */ 674 MDB_IDL_RANGE( res, MDB_IDL_FIRST( ids ), MDB_IDL_LAST( ids )); 675 goto leave; 676 } 677 res[0]++; 678 res[res[0]] = ida; 679 copy = 0; 680 break; 681 } 682 if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) 683 break; 684 } 685 if (idc) { 686 if (copy) { 687 if (ci0 != cid) 688 ids[ci0] = ids[cid]; 689 ci0++; 690 } else 691 idc--; 692 } 693 ida = mdb_idl_next( ids, &cid ); 694 } 695 if (!MDB_IDL_IS_RANGE( ids )) 696 ids[0] = idc; 697 698 leave: 699 mdb_cursor_close( cursor ); 700 return rc; 701 } 702 703 /* See if base is a child of any of the scopes 704 */ 705 int 706 mdb_idscopes( 707 Operation *op, 708 IdScopes *isc ) 709 { 710 struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private; 711 MDB_dbi dbi = mdb->mi_dn2id; 712 MDB_val key, data; 713 ID id, prev; 714 ID2 id2; 715 char *ptr; 716 int rc = 0; 717 unsigned int x; 718 unsigned int nrlen, rlen; 719 diskNode *d; 720 721 key.mv_size = sizeof(ID); 722 723 if ( !isc->mc ) { 724 rc = mdb_cursor_open( isc->mt, dbi, &isc->mc ); 725 if ( rc ) return rc; 726 } 727 728 id = isc->id; 729 730 /* Catch entries from deref'd aliases */ 731 x = mdb_id2l_search( isc->scopes, id ); 732 if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) { 733 isc->nscope = x; 734 return MDB_SUCCESS; 735 } 736 737 isc->sctmp[0].mid = 0; 738 while (id) { 739 if ( !rc ) { 740 key.mv_data = &id; 741 rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET ); 742 if ( rc ) 743 return rc; 744 745 /* save RDN info */ 746 } 747 d = data.mv_data; 748 nrlen = (d->nrdnlen[0] << 8) | d->nrdnlen[1]; 749 rlen = data.mv_size - sizeof(diskNode) - nrlen; 750 isc->nrdns[isc->numrdns].bv_len = nrlen; 751 isc->nrdns[isc->numrdns].bv_val = d->nrdn; 752 isc->rdns[isc->numrdns].bv_len = rlen; 753 isc->rdns[isc->numrdns].bv_val = d->nrdn+nrlen+1; 754 isc->numrdns++; 755 756 if (!rc && id != isc->id) { 757 /* remember our chain of parents */ 758 id2.mid = id; 759 id2.mval = data; 760 mdb_id2l_insert( isc->sctmp, &id2 ); 761 } 762 ptr = data.mv_data; 763 ptr += data.mv_size - sizeof(ID); 764 prev = id; 765 memcpy( &id, ptr, sizeof(ID) ); 766 /* If we didn't advance, some parent is missing */ 767 if ( id == prev ) 768 return MDB_NOTFOUND; 769 770 x = mdb_id2l_search( isc->scopes, id ); 771 if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) { 772 if ( !isc->scopes[x].mval.mv_data ) { 773 /* This node is in scope, add parent chain to scope */ 774 int i; 775 for ( i = 1; i <= isc->sctmp[0].mid; i++ ) { 776 rc = mdb_id2l_insert( isc->scopes, &isc->sctmp[i] ); 777 if ( rc ) 778 break; 779 } 780 /* check id again since inserts may have changed its position */ 781 if ( isc->scopes[x].mid != id ) 782 x = mdb_id2l_search( isc->scopes, id ); 783 isc->nscope = x; 784 return MDB_SUCCESS; 785 } 786 data = isc->scopes[x].mval; 787 rc = 1; 788 } 789 if ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) 790 break; 791 } 792 return MDB_SUCCESS; 793 } 794 795 /* See if ID is a child of any of the scopes, 796 * return MDB_KEYEXIST if so. 797 */ 798 int 799 mdb_idscopechk( 800 Operation *op, 801 IdScopes *isc ) 802 { 803 struct mdb_info *mdb = (struct mdb_info *) op->o_bd->be_private; 804 MDB_val key, data; 805 ID id, prev; 806 char *ptr; 807 int rc = 0; 808 unsigned int x; 809 810 key.mv_size = sizeof(ID); 811 812 if ( !isc->mc ) { 813 rc = mdb_cursor_open( isc->mt, mdb->mi_dn2id, &isc->mc ); 814 if ( rc ) return rc; 815 } 816 817 id = isc->id; 818 819 while (id) { 820 if ( !rc ) { 821 key.mv_data = &id; 822 rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET ); 823 if ( rc ) 824 return rc; 825 } 826 827 ptr = data.mv_data; 828 ptr += data.mv_size - sizeof(ID); 829 prev = id; 830 memcpy( &id, ptr, sizeof(ID) ); 831 /* If we didn't advance, some parent is missing */ 832 if ( id == prev ) 833 return MDB_NOTFOUND; 834 835 x = mdb_id2l_search( isc->scopes, id ); 836 if ( x <= isc->scopes[0].mid && isc->scopes[x].mid == id ) 837 return MDB_KEYEXIST; 838 } 839 return MDB_SUCCESS; 840 } 841 842 int 843 mdb_dn2id_walk( 844 Operation *op, 845 IdScopes *isc 846 ) 847 { 848 MDB_val key, data; 849 diskNode *d; 850 char *ptr; 851 int rc, n; 852 ID nsubs; 853 854 if ( !isc->numrdns ) { 855 key.mv_data = &isc->id; 856 key.mv_size = sizeof(ID); 857 rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET ); 858 isc->scopes[0].mid = isc->id; 859 isc->numrdns++; 860 isc->nscope = 0; 861 /* skip base if not a subtree walk */ 862 if ( isc->oscope == LDAP_SCOPE_SUBTREE || 863 isc->oscope == LDAP_SCOPE_BASE ) 864 return rc; 865 } 866 if ( isc->oscope == LDAP_SCOPE_BASE ) 867 return MDB_NOTFOUND; 868 869 for (;;) { 870 /* Get next sibling */ 871 rc = mdb_cursor_get( isc->mc, &key, &data, MDB_NEXT_DUP ); 872 if ( !rc ) { 873 ptr = (char *)data.mv_data + data.mv_size - 2*sizeof(ID); 874 d = data.mv_data; 875 memcpy( &isc->id, ptr, sizeof(ID)); 876 877 /* If we're pushing down, see if there's any children to find */ 878 if ( isc->nscope ) { 879 ptr += sizeof(ID); 880 memcpy( &nsubs, ptr, sizeof(ID)); 881 /* No children, go to next sibling */ 882 if ( nsubs < 2 ) 883 continue; 884 } 885 n = isc->numrdns; 886 isc->scopes[n].mid = isc->id; 887 n--; 888 isc->nrdns[n].bv_len = ((d->nrdnlen[0] & 0x7f) << 8) | d->nrdnlen[1]; 889 isc->nrdns[n].bv_val = d->nrdn; 890 isc->rdns[n].bv_val = d->nrdn+isc->nrdns[n].bv_len+1; 891 isc->rdns[n].bv_len = data.mv_size - sizeof(diskNode) - isc->nrdns[n].bv_len - sizeof(ID); 892 /* return this ID to caller */ 893 if ( !isc->nscope ) 894 break; 895 896 /* push down to child */ 897 key.mv_data = &isc->id; 898 mdb_cursor_get( isc->mc, &key, &data, MDB_SET ); 899 isc->nscope = 0; 900 isc->numrdns++; 901 continue; 902 903 } else if ( rc == MDB_NOTFOUND ) { 904 if ( !isc->nscope && isc->oscope != LDAP_SCOPE_ONELEVEL ) { 905 /* reset to first dup */ 906 mdb_cursor_get( isc->mc, &key, NULL, MDB_GET_CURRENT ); 907 mdb_cursor_get( isc->mc, &key, &data, MDB_SET ); 908 isc->nscope = 1; 909 continue; 910 } else { 911 isc->numrdns--; 912 /* stack is empty? */ 913 if ( !isc->numrdns ) 914 break; 915 /* pop up to prev node */ 916 n = isc->numrdns - 1; 917 key.mv_data = &isc->scopes[n].mid; 918 key.mv_size = sizeof(ID); 919 data.mv_data = isc->nrdns[n].bv_val - 2; 920 data.mv_size = 1; /* just needs to be non-zero, mdb_dup_compare doesn't care */ 921 mdb_cursor_get( isc->mc, &key, &data, MDB_GET_BOTH ); 922 continue; 923 } 924 } else { 925 break; 926 } 927 } 928 return rc; 929 } 930 931 /* restore the nrdn/rdn pointers after a txn reset */ 932 void mdb_dn2id_wrestore ( 933 Operation *op, 934 IdScopes *isc 935 ) 936 { 937 MDB_val key, data; 938 diskNode *d; 939 int rc, n, nrlen; 940 char *ptr; 941 942 /* We only need to restore up to the n-1th element, 943 * the nth element will be replaced anyway 944 */ 945 key.mv_size = sizeof(ID); 946 for ( n=0; n<isc->numrdns-1; n++ ) { 947 key.mv_data = &isc->scopes[n+1].mid; 948 rc = mdb_cursor_get( isc->mc, &key, &data, MDB_SET ); 949 if ( rc ) 950 continue; 951 /* we can't use this data directly since its nrlen 952 * is missing the high bit setting, so copy it and 953 * set it properly. we just copy enough to satisfy 954 * mdb_dup_compare. 955 */ 956 d = data.mv_data; 957 nrlen = ((d->nrdnlen[0] & 0x7f) << 8) | d->nrdnlen[1]; 958 ptr = op->o_tmpalloc( nrlen+2, op->o_tmpmemctx ); 959 memcpy( ptr, data.mv_data, nrlen+2 ); 960 key.mv_data = &isc->scopes[n].mid; 961 data.mv_data = ptr; 962 data.mv_size = 1; 963 *ptr |= 0x80; 964 mdb_cursor_get( isc->mc, &key, &data, MDB_GET_BOTH ); 965 op->o_tmpfree( ptr, op->o_tmpmemctx ); 966 967 /* now we're back to where we wanted to be */ 968 d = data.mv_data; 969 isc->nrdns[n].bv_val = d->nrdn; 970 isc->rdns[n].bv_val = d->nrdn+isc->nrdns[n].bv_len+1; 971 } 972 } 973