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-bdb.h" 23#include "idl.h" 24#include "lutil.h" 25 26#ifndef BDB_HIER 27int 28bdb_dn2id_add( 29 Operation *op, 30 DB_TXN *txn, 31 EntryInfo *eip, 32 Entry *e ) 33{ 34 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 35 DB *db = bdb->bi_dn2id->bdi_db; 36 int rc; 37 DBT key, data; 38 ID nid; 39 char *buf; 40 struct berval ptr, pdn; 41 42 Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_add 0x%lx: \"%s\"\n", 43 e->e_id, e->e_ndn, 0 ); 44 assert( e->e_id != NOID ); 45 46 DBTzero( &key ); 47 key.size = e->e_nname.bv_len + 2; 48 key.ulen = key.size; 49 key.flags = DB_DBT_USERMEM; 50 buf = op->o_tmpalloc( key.size, op->o_tmpmemctx ); 51 key.data = buf; 52 buf[0] = DN_BASE_PREFIX; 53 ptr.bv_val = buf + 1; 54 ptr.bv_len = e->e_nname.bv_len; 55 AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len ); 56 ptr.bv_val[ptr.bv_len] = '\0'; 57 58 DBTzero( &data ); 59 data.data = &nid; 60 data.size = sizeof( nid ); 61 BDB_ID2DISK( e->e_id, &nid ); 62 63 /* store it -- don't override */ 64 rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE ); 65 if( rc != 0 ) { 66 char buf[ SLAP_TEXT_BUFLEN ]; 67 snprintf( buf, sizeof( buf ), "%s => bdb_dn2id_add dn=\"%s\" ID=0x%lx", 68 op->o_log_prefix, e->e_name.bv_val, e->e_id ); 69 Debug( LDAP_DEBUG_ANY, "%s: put failed: %s %d\n", 70 buf, db_strerror(rc), rc ); 71 goto done; 72 } 73 74#ifndef BDB_MULTIPLE_SUFFIXES 75 if( !be_issuffix( op->o_bd, &ptr )) 76#endif 77 { 78 buf[0] = DN_SUBTREE_PREFIX; 79 rc = db->put( db, txn, &key, &data, DB_NOOVERWRITE ); 80 if( rc != 0 ) { 81 Debug( LDAP_DEBUG_ANY, 82 "=> bdb_dn2id_add 0x%lx: subtree (%s) put failed: %d\n", 83 e->e_id, ptr.bv_val, rc ); 84 goto done; 85 } 86 87#ifdef BDB_MULTIPLE_SUFFIXES 88 if( !be_issuffix( op->o_bd, &ptr )) 89#endif 90 { 91 dnParent( &ptr, &pdn ); 92 93 key.size = pdn.bv_len + 2; 94 key.ulen = key.size; 95 pdn.bv_val[-1] = DN_ONE_PREFIX; 96 key.data = pdn.bv_val-1; 97 ptr = pdn; 98 99 rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id ); 100 101 if( rc != 0 ) { 102 Debug( LDAP_DEBUG_ANY, 103 "=> bdb_dn2id_add 0x%lx: parent (%s) insert failed: %d\n", 104 e->e_id, ptr.bv_val, rc ); 105 goto done; 106 } 107 } 108 109#ifndef BDB_MULTIPLE_SUFFIXES 110 while( !be_issuffix( op->o_bd, &ptr )) 111#else 112 for (;;) 113#endif 114 { 115 ptr.bv_val[-1] = DN_SUBTREE_PREFIX; 116 117 rc = bdb_idl_insert_key( op->o_bd, db, txn, &key, e->e_id ); 118 119 if( rc != 0 ) { 120 Debug( LDAP_DEBUG_ANY, 121 "=> bdb_dn2id_add 0x%lx: subtree (%s) insert failed: %d\n", 122 e->e_id, ptr.bv_val, rc ); 123 break; 124 } 125#ifdef BDB_MULTIPLE_SUFFIXES 126 if( be_issuffix( op->o_bd, &ptr )) break; 127#endif 128 dnParent( &ptr, &pdn ); 129 130 key.size = pdn.bv_len + 2; 131 key.ulen = key.size; 132 key.data = pdn.bv_val - 1; 133 ptr = pdn; 134 } 135 } 136 137done: 138 op->o_tmpfree( buf, op->o_tmpmemctx ); 139 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 ); 140 return rc; 141} 142 143int 144bdb_dn2id_delete( 145 Operation *op, 146 DB_TXN *txn, 147 EntryInfo *eip, 148 Entry *e ) 149{ 150 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 151 DB *db = bdb->bi_dn2id->bdi_db; 152 char *buf; 153 DBT key; 154 struct berval pdn, ptr; 155 int rc; 156 157 Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_delete 0x%lx: \"%s\"\n", 158 e->e_id, e->e_ndn, 0 ); 159 160 DBTzero( &key ); 161 key.size = e->e_nname.bv_len + 2; 162 buf = op->o_tmpalloc( key.size, op->o_tmpmemctx ); 163 key.data = buf; 164 key.flags = DB_DBT_USERMEM; 165 buf[0] = DN_BASE_PREFIX; 166 ptr.bv_val = buf+1; 167 ptr.bv_len = e->e_nname.bv_len; 168 AC_MEMCPY( ptr.bv_val, e->e_nname.bv_val, e->e_nname.bv_len ); 169 ptr.bv_val[ptr.bv_len] = '\0'; 170 171 /* delete it */ 172 rc = db->del( db, txn, &key, 0 ); 173 if( rc != 0 ) { 174 Debug( LDAP_DEBUG_ANY, "=> bdb_dn2id_delete 0x%lx: delete failed: %s %d\n", 175 e->e_id, db_strerror(rc), rc ); 176 goto done; 177 } 178 179#ifndef BDB_MULTIPLE_SUFFIXES 180 if( !be_issuffix( op->o_bd, &ptr )) 181#endif 182 { 183 buf[0] = DN_SUBTREE_PREFIX; 184 rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id ); 185 if( rc != 0 ) { 186 Debug( LDAP_DEBUG_ANY, 187 "=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n", 188 e->e_id, ptr.bv_val, rc ); 189 goto done; 190 } 191 192#ifdef BDB_MULTIPLE_SUFFIXES 193 if( !be_issuffix( op->o_bd, &ptr )) 194#endif 195 { 196 dnParent( &ptr, &pdn ); 197 198 key.size = pdn.bv_len + 2; 199 key.ulen = key.size; 200 pdn.bv_val[-1] = DN_ONE_PREFIX; 201 key.data = pdn.bv_val - 1; 202 ptr = pdn; 203 204 rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id ); 205 206 if( rc != 0 ) { 207 Debug( LDAP_DEBUG_ANY, 208 "=> bdb_dn2id_delete 0x%lx: parent (%s) delete failed: %d\n", 209 e->e_id, ptr.bv_val, rc ); 210 goto done; 211 } 212 } 213 214#ifndef BDB_MULTIPLE_SUFFIXES 215 while( !be_issuffix( op->o_bd, &ptr )) 216#else 217 for (;;) 218#endif 219 { 220 ptr.bv_val[-1] = DN_SUBTREE_PREFIX; 221 222 rc = bdb_idl_delete_key( op->o_bd, db, txn, &key, e->e_id ); 223 if( rc != 0 ) { 224 Debug( LDAP_DEBUG_ANY, 225 "=> bdb_dn2id_delete 0x%lx: subtree (%s) delete failed: %d\n", 226 e->e_id, ptr.bv_val, rc ); 227 goto done; 228 } 229#ifdef BDB_MULTIPLE_SUFFIXES 230 if( be_issuffix( op->o_bd, &ptr )) break; 231#endif 232 dnParent( &ptr, &pdn ); 233 234 key.size = pdn.bv_len + 2; 235 key.ulen = key.size; 236 key.data = pdn.bv_val - 1; 237 ptr = pdn; 238 } 239 } 240 241done: 242 op->o_tmpfree( buf, op->o_tmpmemctx ); 243 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 ); 244 return rc; 245} 246 247int 248bdb_dn2id( 249 Operation *op, 250 struct berval *dn, 251 EntryInfo *ei, 252 DB_TXN *txn, 253 DBC **cursor ) 254{ 255 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 256 DB *db = bdb->bi_dn2id->bdi_db; 257 int rc; 258 DBT key, data; 259 ID nid; 260 261 Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id(\"%s\")\n", dn->bv_val, 0, 0 ); 262 263 DBTzero( &key ); 264 key.size = dn->bv_len + 2; 265 key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx ); 266 ((char *)key.data)[0] = DN_BASE_PREFIX; 267 AC_MEMCPY( &((char *)key.data)[1], dn->bv_val, key.size - 1 ); 268 269 /* store the ID */ 270 DBTzero( &data ); 271 data.data = &nid; 272 data.ulen = sizeof(ID); 273 data.flags = DB_DBT_USERMEM; 274 275 rc = db->cursor( db, txn, cursor, bdb->bi_db_opflags ); 276 277 /* fetch it */ 278 if ( !rc ) 279 rc = (*cursor)->c_get( *cursor, &key, &data, DB_SET ); 280 281 if( rc != 0 ) { 282 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: get failed: %s (%d)\n", 283 db_strerror( rc ), rc, 0 ); 284 } else { 285 BDB_DISK2ID( &nid, &ei->bei_id ); 286 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id: got id=0x%lx\n", 287 ei->bei_id, 0, 0 ); 288 } 289 op->o_tmpfree( key.data, op->o_tmpmemctx ); 290 return rc; 291} 292 293int 294bdb_dn2id_children( 295 Operation *op, 296 DB_TXN *txn, 297 Entry *e ) 298{ 299 DBT key, data; 300 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 301 DB *db = bdb->bi_dn2id->bdi_db; 302 ID id; 303 int rc; 304 305 Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2id_children(\"%s\")\n", 306 e->e_nname.bv_val, 0, 0 ); 307 DBTzero( &key ); 308 key.size = e->e_nname.bv_len + 2; 309 key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx ); 310 ((char *)key.data)[0] = DN_ONE_PREFIX; 311 AC_MEMCPY( &((char *)key.data)[1], e->e_nname.bv_val, key.size - 1 ); 312 313 if ( bdb->bi_idl_cache_size ) { 314 rc = bdb_idl_cache_get( bdb, db, &key, NULL ); 315 if ( rc != LDAP_NO_SUCH_OBJECT ) { 316 op->o_tmpfree( key.data, op->o_tmpmemctx ); 317 return rc; 318 } 319 } 320 /* we actually could do a empty get... */ 321 DBTzero( &data ); 322 data.data = &id; 323 data.ulen = sizeof(id); 324 data.flags = DB_DBT_USERMEM; 325 data.doff = 0; 326 data.dlen = sizeof(id); 327 328 rc = db->get( db, txn, &key, &data, bdb->bi_db_opflags ); 329 op->o_tmpfree( key.data, op->o_tmpmemctx ); 330 331 Debug( LDAP_DEBUG_TRACE, "<= bdb_dn2id_children(\"%s\"): %s (%d)\n", 332 e->e_nname.bv_val, 333 rc == 0 ? "" : ( rc == DB_NOTFOUND ? "no " : 334 db_strerror(rc) ), rc ); 335 336 return rc; 337} 338 339int 340bdb_dn2idl( 341 Operation *op, 342 DB_TXN *txn, 343 struct berval *ndn, 344 EntryInfo *ei, 345 ID *ids, 346 ID *stack ) 347{ 348 int rc; 349 DBT key; 350 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 351 DB *db = bdb->bi_dn2id->bdi_db; 352 int prefix = ( op->ors_scope == LDAP_SCOPE_ONELEVEL ) 353 ? DN_ONE_PREFIX : DN_SUBTREE_PREFIX; 354 355 Debug( LDAP_DEBUG_TRACE, "=> bdb_dn2idl(\"%s\")\n", 356 ndn->bv_val, 0, 0 ); 357 358#ifndef BDB_MULTIPLE_SUFFIXES 359 if ( prefix == DN_SUBTREE_PREFIX 360 && ( ei->bei_id == 0 || 361 ( ei->bei_parent->bei_id == 0 && op->o_bd->be_suffix[0].bv_len ))) { 362 BDB_IDL_ALL(bdb, ids); 363 return 0; 364 } 365#endif 366 367 DBTzero( &key ); 368 key.size = ndn->bv_len + 2; 369 key.ulen = key.size; 370 key.flags = DB_DBT_USERMEM; 371 key.data = op->o_tmpalloc( key.size, op->o_tmpmemctx ); 372 ((char *)key.data)[0] = prefix; 373 AC_MEMCPY( &((char *)key.data)[1], ndn->bv_val, key.size - 1 ); 374 375 BDB_IDL_ZERO( ids ); 376 rc = bdb_idl_fetch_key( op->o_bd, db, txn, &key, ids, NULL, 0 ); 377 378 if( rc != 0 ) { 379 Debug( LDAP_DEBUG_TRACE, 380 "<= bdb_dn2idl: get failed: %s (%d)\n", 381 db_strerror( rc ), rc, 0 ); 382 383 } else { 384 Debug( LDAP_DEBUG_TRACE, 385 "<= bdb_dn2idl: id=%ld first=%ld last=%ld\n", 386 (long) ids[0], 387 (long) BDB_IDL_FIRST( ids ), (long) BDB_IDL_LAST( ids ) ); 388 } 389 390 op->o_tmpfree( key.data, op->o_tmpmemctx ); 391 return rc; 392} 393 394#else /* BDB_HIER */ 395/* Management routines for a hierarchically structured database. 396 * 397 * Instead of a ldbm-style dn2id database, we use a hierarchical one. Each 398 * entry in this database is a struct diskNode, keyed by entryID and with 399 * the data containing the RDN and entryID of the node's children. We use 400 * a B-Tree with sorted duplicates to store all the children of a node under 401 * the same key. Also, the first item under the key contains the entry's own 402 * rdn and the ID of the node's parent, to allow bottom-up tree traversal as 403 * well as top-down. To keep this info first in the list, the high bit of all 404 * subsequent nrdnlen's is always set. This means we can only accomodate 405 * RDNs up to length 32767, but that's fine since full DNs are already 406 * restricted to 8192. 407 * 408 * The diskNode is a variable length structure. This definition is not 409 * directly usable for in-memory manipulation. 410 */ 411typedef struct diskNode { 412 unsigned char nrdnlen[2]; 413 char nrdn[1]; 414 char rdn[1]; /* variable placement */ 415 unsigned char entryID[sizeof(ID)]; /* variable placement */ 416} diskNode; 417 418/* Sort function for the sorted duplicate data items of a dn2id key. 419 * Sorts based on normalized RDN, in length order. 420 */ 421int 422hdb_dup_compare( 423 DB *db, 424 const DBT *usrkey, 425 const DBT *curkey 426) 427{ 428 diskNode *un, *cn; 429 int rc; 430 431 un = (diskNode *)usrkey->data; 432 cn = (diskNode *)curkey->data; 433 434 /* data is not aligned, cannot compare directly */ 435 rc = un->nrdnlen[0] - cn->nrdnlen[0]; 436 if ( rc ) return rc; 437 rc = un->nrdnlen[1] - cn->nrdnlen[1]; 438 if ( rc ) return rc; 439 440 return strcmp( un->nrdn, cn->nrdn ); 441} 442 443/* This function constructs a full DN for a given entry. 444 */ 445int hdb_fix_dn( 446 Entry *e, 447 int checkit ) 448{ 449 EntryInfo *ei; 450 int rlen = 0, nrlen = 0; 451 char *ptr, *nptr; 452 int max = 0; 453 454 if ( !e->e_id ) 455 return 0; 456 457 /* count length of all DN components */ 458 for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) { 459 rlen += ei->bei_rdn.bv_len + 1; 460 nrlen += ei->bei_nrdn.bv_len + 1; 461 if (ei->bei_modrdns > max) max = ei->bei_modrdns; 462 } 463 464 /* See if the entry DN was invalidated by a subtree rename */ 465 if ( checkit ) { 466 if ( BEI(e)->bei_modrdns >= max ) { 467 return 0; 468 } 469 /* We found a mismatch, tell the caller to lock it */ 470 if ( checkit == 1 ) { 471 return 1; 472 } 473 /* checkit == 2. do the fix. */ 474 free( e->e_name.bv_val ); 475 free( e->e_nname.bv_val ); 476 } 477 478 e->e_name.bv_len = rlen - 1; 479 e->e_nname.bv_len = nrlen - 1; 480 e->e_name.bv_val = ch_malloc(rlen); 481 e->e_nname.bv_val = ch_malloc(nrlen); 482 ptr = e->e_name.bv_val; 483 nptr = e->e_nname.bv_val; 484 for ( ei = BEI(e); ei && ei->bei_id; ei=ei->bei_parent ) { 485 ptr = lutil_strcopy(ptr, ei->bei_rdn.bv_val); 486 nptr = lutil_strcopy(nptr, ei->bei_nrdn.bv_val); 487 if ( ei->bei_parent ) { 488 *ptr++ = ','; 489 *nptr++ = ','; 490 } 491 } 492 BEI(e)->bei_modrdns = max; 493 if ( ptr > e->e_name.bv_val ) ptr[-1] = '\0'; 494 if ( nptr > e->e_nname.bv_val ) nptr[-1] = '\0'; 495 496 return 0; 497} 498 499/* We add two elements to the DN2ID database - a data item under the parent's 500 * entryID containing the child's RDN and entryID, and an item under the 501 * child's entryID containing the parent's entryID. 502 */ 503int 504hdb_dn2id_add( 505 Operation *op, 506 DB_TXN *txn, 507 EntryInfo *eip, 508 Entry *e ) 509{ 510 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 511 DB *db = bdb->bi_dn2id->bdi_db; 512 DBT key, data; 513 ID nid; 514 int rc, rlen, nrlen; 515 diskNode *d; 516 char *ptr; 517 518 Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_add 0x%lx: \"%s\"\n", 519 e->e_id, e->e_ndn, 0 ); 520 521 nrlen = dn_rdnlen( op->o_bd, &e->e_nname ); 522 if (nrlen) { 523 rlen = dn_rdnlen( op->o_bd, &e->e_name ); 524 } else { 525 nrlen = e->e_nname.bv_len; 526 rlen = e->e_name.bv_len; 527 } 528 529 d = op->o_tmpalloc(sizeof(diskNode) + rlen + nrlen, op->o_tmpmemctx); 530 d->nrdnlen[1] = nrlen & 0xff; 531 d->nrdnlen[0] = (nrlen >> 8) | 0x80; 532 ptr = lutil_strncopy( d->nrdn, e->e_nname.bv_val, nrlen ); 533 *ptr++ = '\0'; 534 ptr = lutil_strncopy( ptr, e->e_name.bv_val, rlen ); 535 *ptr++ = '\0'; 536 BDB_ID2DISK( e->e_id, ptr ); 537 538 DBTzero(&key); 539 DBTzero(&data); 540 key.size = sizeof(ID); 541 key.flags = DB_DBT_USERMEM; 542 BDB_ID2DISK( eip->bei_id, &nid ); 543 544 key.data = &nid; 545 546 /* Need to make dummy root node once. Subsequent attempts 547 * will fail harmlessly. 548 */ 549 if ( eip->bei_id == 0 ) { 550 diskNode dummy = {{0, 0}, "", "", ""}; 551 data.data = &dummy; 552 data.size = sizeof(diskNode); 553 data.flags = DB_DBT_USERMEM; 554 555 db->put( db, txn, &key, &data, DB_NODUPDATA ); 556 } 557 558 data.data = d; 559 data.size = sizeof(diskNode) + rlen + nrlen; 560 data.flags = DB_DBT_USERMEM; 561 562 rc = db->put( db, txn, &key, &data, DB_NODUPDATA ); 563 564 if (rc == 0) { 565 BDB_ID2DISK( e->e_id, &nid ); 566 BDB_ID2DISK( eip->bei_id, ptr ); 567 d->nrdnlen[0] ^= 0x80; 568 569 rc = db->put( db, txn, &key, &data, DB_NODUPDATA ); 570 } 571 572 /* Update all parents' IDL cache entries */ 573 if ( rc == 0 && bdb->bi_idl_cache_size ) { 574 ID tmp[2]; 575 char *ptr = ((char *)&tmp[1])-1; 576 key.data = ptr; 577 key.size = sizeof(ID)+1; 578 tmp[1] = eip->bei_id; 579 *ptr = DN_ONE_PREFIX; 580 bdb_idl_cache_add_id( bdb, db, &key, e->e_id ); 581 if ( eip->bei_parent ) { 582 *ptr = DN_SUBTREE_PREFIX; 583 for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) { 584 tmp[1] = eip->bei_id; 585 bdb_idl_cache_add_id( bdb, db, &key, e->e_id ); 586 } 587 /* Handle DB with empty suffix */ 588 if ( !op->o_bd->be_suffix[0].bv_len && eip ) { 589 tmp[1] = eip->bei_id; 590 bdb_idl_cache_add_id( bdb, db, &key, e->e_id ); 591 } 592 } 593 } 594 595 op->o_tmpfree( d, op->o_tmpmemctx ); 596 Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_add 0x%lx: %d\n", e->e_id, rc, 0 ); 597 598 return rc; 599} 600 601int 602hdb_dn2id_delete( 603 Operation *op, 604 DB_TXN *txn, 605 EntryInfo *eip, 606 Entry *e ) 607{ 608 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 609 DB *db = bdb->bi_dn2id->bdi_db; 610 DBT key, data; 611 DBC *cursor; 612 diskNode *d; 613 int rc; 614 ID nid; 615 unsigned char dlen[2]; 616 617 Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id_delete 0x%lx: \"%s\"\n", 618 e->e_id, e->e_ndn, 0 ); 619 620 DBTzero(&key); 621 key.size = sizeof(ID); 622 key.ulen = key.size; 623 key.flags = DB_DBT_USERMEM; 624 BDB_ID2DISK( eip->bei_id, &nid ); 625 626 DBTzero(&data); 627 data.size = sizeof(diskNode) + BEI(e)->bei_nrdn.bv_len - sizeof(ID) - 1; 628 data.ulen = data.size; 629 data.dlen = data.size; 630 data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL; 631 632 key.data = &nid; 633 634 d = op->o_tmpalloc( data.size, op->o_tmpmemctx ); 635 d->nrdnlen[1] = BEI(e)->bei_nrdn.bv_len & 0xff; 636 d->nrdnlen[0] = (BEI(e)->bei_nrdn.bv_len >> 8) | 0x80; 637 dlen[0] = d->nrdnlen[0]; 638 dlen[1] = d->nrdnlen[1]; 639 memcpy( d->nrdn, BEI(e)->bei_nrdn.bv_val, BEI(e)->bei_nrdn.bv_len+1 ); 640 data.data = d; 641 642 rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags ); 643 if ( rc ) goto func_leave; 644 645 /* Delete our ID from the parent's list */ 646 rc = cursor->c_get( cursor, &key, &data, DB_GET_BOTH_RANGE ); 647 if ( rc == 0 ) { 648 if ( dlen[1] == d->nrdnlen[1] && dlen[0] == d->nrdnlen[0] && 649 !strcmp( d->nrdn, BEI(e)->bei_nrdn.bv_val )) 650 rc = cursor->c_del( cursor, 0 ); 651 else 652 rc = DB_NOTFOUND; 653 } 654 655 /* Delete our ID from the tree. With sorted duplicates, this 656 * will leave any child nodes still hanging around. This is OK 657 * for modrdn, which will add our info back in later. 658 */ 659 if ( rc == 0 ) { 660 BDB_ID2DISK( e->e_id, &nid ); 661 rc = cursor->c_get( cursor, &key, &data, DB_SET ); 662 if ( rc == 0 ) 663 rc = cursor->c_del( cursor, 0 ); 664 } 665 666 cursor->c_close( cursor ); 667func_leave: 668 op->o_tmpfree( d, op->o_tmpmemctx ); 669 670 /* Delete IDL cache entries */ 671 if ( rc == 0 && bdb->bi_idl_cache_size ) { 672 ID tmp[2]; 673 char *ptr = ((char *)&tmp[1])-1; 674 key.data = ptr; 675 key.size = sizeof(ID)+1; 676 tmp[1] = eip->bei_id; 677 *ptr = DN_ONE_PREFIX; 678 bdb_idl_cache_del_id( bdb, db, &key, e->e_id ); 679 if ( eip ->bei_parent ) { 680 *ptr = DN_SUBTREE_PREFIX; 681 for (; eip && eip->bei_parent->bei_id; eip = eip->bei_parent) { 682 tmp[1] = eip->bei_id; 683 bdb_idl_cache_del_id( bdb, db, &key, e->e_id ); 684 } 685 /* Handle DB with empty suffix */ 686 if ( !op->o_bd->be_suffix[0].bv_len && eip ) { 687 tmp[1] = eip->bei_id; 688 bdb_idl_cache_del_id( bdb, db, &key, e->e_id ); 689 } 690 } 691 } 692 Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id_delete 0x%lx: %d\n", e->e_id, rc, 0 ); 693 return rc; 694} 695 696 697int 698hdb_dn2id( 699 Operation *op, 700 struct berval *in, 701 EntryInfo *ei, 702 DB_TXN *txn, 703 DBC **cursor ) 704{ 705 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 706 DB *db = bdb->bi_dn2id->bdi_db; 707 DBT key, data; 708 int rc = 0, nrlen; 709 diskNode *d; 710 char *ptr; 711 unsigned char dlen[2]; 712 ID idp, parentID; 713 714 Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2id(\"%s\")\n", in->bv_val, 0, 0 ); 715 716 nrlen = dn_rdnlen( op->o_bd, in ); 717 if (!nrlen) nrlen = in->bv_len; 718 719 DBTzero(&key); 720 key.size = sizeof(ID); 721 key.data = &idp; 722 key.ulen = sizeof(ID); 723 key.flags = DB_DBT_USERMEM; 724 parentID = ( ei->bei_parent != NULL ) ? ei->bei_parent->bei_id : 0; 725 BDB_ID2DISK( parentID, &idp ); 726 727 DBTzero(&data); 728 data.size = sizeof(diskNode) + nrlen - sizeof(ID) - 1; 729 data.ulen = data.size * 3; 730 data.dlen = data.ulen; 731 data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL; 732 733 rc = db->cursor( db, txn, cursor, bdb->bi_db_opflags ); 734 if ( rc ) return rc; 735 736 d = op->o_tmpalloc( data.size * 3, op->o_tmpmemctx ); 737 d->nrdnlen[1] = nrlen & 0xff; 738 d->nrdnlen[0] = (nrlen >> 8) | 0x80; 739 dlen[0] = d->nrdnlen[0]; 740 dlen[1] = d->nrdnlen[1]; 741 ptr = lutil_strncopy( d->nrdn, in->bv_val, nrlen ); 742 *ptr = '\0'; 743 data.data = d; 744 745 rc = (*cursor)->c_get( *cursor, &key, &data, DB_GET_BOTH_RANGE ); 746 if ( rc == 0 && (dlen[1] != d->nrdnlen[1] || dlen[0] != d->nrdnlen[0] || 747 strncmp( d->nrdn, in->bv_val, nrlen ))) { 748 rc = DB_NOTFOUND; 749 } 750 if ( rc == 0 ) { 751 ptr = (char *) data.data + data.size - sizeof(ID); 752 BDB_DISK2ID( ptr, &ei->bei_id ); 753 ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - nrlen; 754 ptr = d->nrdn + nrlen + 1; 755 ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn ); 756 if ( ei->bei_parent != NULL && !ei->bei_parent->bei_dkids ) { 757 db_recno_t dkids; 758 /* How many children does the parent have? */ 759 /* FIXME: do we need to lock the parent 760 * entryinfo? Seems safe... 761 */ 762 (*cursor)->c_count( *cursor, &dkids, 0 ); 763 ei->bei_parent->bei_dkids = dkids; 764 } 765 } 766 767 op->o_tmpfree( d, op->o_tmpmemctx ); 768 if( rc != 0 ) { 769 Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: get failed: %s (%d)\n", 770 db_strerror( rc ), rc, 0 ); 771 } else { 772 Debug( LDAP_DEBUG_TRACE, "<= hdb_dn2id: got id=0x%lx\n", 773 ei->bei_id, 0, 0 ); 774 } 775 776 return rc; 777} 778 779int 780hdb_dn2id_parent( 781 Operation *op, 782 DB_TXN *txn, 783 EntryInfo *ei, 784 ID *idp ) 785{ 786 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 787 DB *db = bdb->bi_dn2id->bdi_db; 788 DBT key, data; 789 DBC *cursor; 790 int rc = 0; 791 diskNode *d; 792 char *ptr; 793 ID nid; 794 795 DBTzero(&key); 796 key.size = sizeof(ID); 797 key.data = &nid; 798 key.ulen = sizeof(ID); 799 key.flags = DB_DBT_USERMEM; 800 BDB_ID2DISK( ei->bei_id, &nid ); 801 802 DBTzero(&data); 803 data.flags = DB_DBT_USERMEM; 804 805 rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags ); 806 if ( rc ) return rc; 807 808 data.ulen = sizeof(diskNode) + (SLAP_LDAPDN_MAXLEN * 2); 809 d = op->o_tmpalloc( data.ulen, op->o_tmpmemctx ); 810 data.data = d; 811 812 rc = cursor->c_get( cursor, &key, &data, DB_SET ); 813 if ( rc == 0 ) { 814 if (d->nrdnlen[0] & 0x80) { 815 rc = LDAP_OTHER; 816 } else { 817 db_recno_t dkids; 818 ptr = (char *) data.data + data.size - sizeof(ID); 819 BDB_DISK2ID( ptr, idp ); 820 ei->bei_nrdn.bv_len = (d->nrdnlen[0] << 8) | d->nrdnlen[1]; 821 ber_str2bv( d->nrdn, ei->bei_nrdn.bv_len, 1, &ei->bei_nrdn ); 822 ei->bei_rdn.bv_len = data.size - sizeof(diskNode) - 823 ei->bei_nrdn.bv_len; 824 ptr = d->nrdn + ei->bei_nrdn.bv_len + 1; 825 ber_str2bv( ptr, ei->bei_rdn.bv_len, 1, &ei->bei_rdn ); 826 /* How many children does this node have? */ 827 cursor->c_count( cursor, &dkids, 0 ); 828 ei->bei_dkids = dkids; 829 } 830 } 831 cursor->c_close( cursor ); 832 op->o_tmpfree( d, op->o_tmpmemctx ); 833 return rc; 834} 835 836int 837hdb_dn2id_children( 838 Operation *op, 839 DB_TXN *txn, 840 Entry *e ) 841{ 842 struct bdb_info *bdb = (struct bdb_info *) op->o_bd->be_private; 843 DB *db = bdb->bi_dn2id->bdi_db; 844 DBT key, data; 845 DBC *cursor; 846 int rc; 847 ID id; 848 diskNode d; 849 850 DBTzero(&key); 851 key.size = sizeof(ID); 852 key.data = &e->e_id; 853 key.flags = DB_DBT_USERMEM; 854 BDB_ID2DISK( e->e_id, &id ); 855 856 /* IDL cache is in host byte order */ 857 if ( bdb->bi_idl_cache_size ) { 858 rc = bdb_idl_cache_get( bdb, db, &key, NULL ); 859 if ( rc != LDAP_NO_SUCH_OBJECT ) { 860 return rc; 861 } 862 } 863 864 key.data = &id; 865 DBTzero(&data); 866 data.data = &d; 867 data.ulen = sizeof(d); 868 data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL; 869 data.dlen = sizeof(d); 870 871 rc = db->cursor( db, txn, &cursor, bdb->bi_db_opflags ); 872 if ( rc ) return rc; 873 874 rc = cursor->c_get( cursor, &key, &data, DB_SET ); 875 if ( rc == 0 ) { 876 db_recno_t dkids; 877 rc = cursor->c_count( cursor, &dkids, 0 ); 878 if ( rc == 0 ) { 879 BEI(e)->bei_dkids = dkids; 880 if ( dkids < 2 ) rc = DB_NOTFOUND; 881 } 882 } 883 cursor->c_close( cursor ); 884 return rc; 885} 886 887/* bdb_dn2idl: 888 * We can't just use bdb_idl_fetch_key because 889 * 1 - our data items are longer than just an entry ID 890 * 2 - our data items are sorted alphabetically by nrdn, not by ID. 891 * 892 * We descend the tree recursively, so we define this cookie 893 * to hold our necessary state information. The bdb_dn2idl_internal 894 * function uses this cookie when calling itself. 895 */ 896 897struct dn2id_cookie { 898 struct bdb_info *bdb; 899 Operation *op; 900 DB_TXN *txn; 901 EntryInfo *ei; 902 ID *ids; 903 ID *tmp; 904 ID *buf; 905 DB *db; 906 DBC *dbc; 907 DBT key; 908 DBT data; 909 ID dbuf; 910 ID id; 911 ID nid; 912 int rc; 913 int depth; 914 char need_sort; 915 char prefix; 916}; 917 918static int 919apply_func( 920 void *data, 921 void *arg ) 922{ 923 EntryInfo *ei = data; 924 ID *idl = arg; 925 926 bdb_idl_append_one( idl, ei->bei_id ); 927 return 0; 928} 929 930static int 931hdb_dn2idl_internal( 932 struct dn2id_cookie *cx 933) 934{ 935 BDB_IDL_ZERO( cx->tmp ); 936 937 if ( cx->bdb->bi_idl_cache_size ) { 938 char *ptr = ((char *)&cx->id)-1; 939 940 cx->key.data = ptr; 941 cx->key.size = sizeof(ID)+1; 942 if ( cx->prefix == DN_SUBTREE_PREFIX ) { 943 ID *ids = cx->depth ? cx->tmp : cx->ids; 944 *ptr = cx->prefix; 945 cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, ids); 946 if ( cx->rc == LDAP_SUCCESS ) { 947 if ( cx->depth ) { 948 bdb_idl_delete( cx->tmp, cx->id ); /* ITS#6983, drop our own ID */ 949 bdb_idl_append( cx->ids, cx->tmp ); 950 cx->need_sort = 1; 951 } 952 return cx->rc; 953 } 954 } 955 *ptr = DN_ONE_PREFIX; 956 cx->rc = bdb_idl_cache_get(cx->bdb, cx->db, &cx->key, cx->tmp); 957 if ( cx->rc == LDAP_SUCCESS ) { 958 goto gotit; 959 } 960 if ( cx->rc == DB_NOTFOUND ) { 961 return cx->rc; 962 } 963 } 964 965 bdb_cache_entryinfo_lock( cx->ei ); 966 967 /* If number of kids in the cache differs from on-disk, load 968 * up all the kids from the database 969 */ 970 if ( cx->ei->bei_ckids+1 != cx->ei->bei_dkids ) { 971 EntryInfo ei; 972 db_recno_t dkids = cx->ei->bei_dkids; 973 ei.bei_parent = cx->ei; 974 975 /* Only one thread should load the cache */ 976 while ( cx->ei->bei_state & CACHE_ENTRY_ONELEVEL ) { 977 bdb_cache_entryinfo_unlock( cx->ei ); 978 ldap_pvt_thread_yield(); 979 bdb_cache_entryinfo_lock( cx->ei ); 980 if ( cx->ei->bei_ckids+1 == cx->ei->bei_dkids ) { 981 goto synced; 982 } 983 } 984 985 cx->ei->bei_state |= CACHE_ENTRY_ONELEVEL; 986 987 bdb_cache_entryinfo_unlock( cx->ei ); 988 989 cx->rc = cx->db->cursor( cx->db, NULL, &cx->dbc, 990 cx->bdb->bi_db_opflags ); 991 if ( cx->rc ) 992 goto done_one; 993 994 cx->data.data = &cx->dbuf; 995 cx->data.ulen = sizeof(ID); 996 cx->data.dlen = sizeof(ID); 997 cx->data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL; 998 999 /* The first item holds the parent ID. Ignore it. */ 1000 cx->key.data = &cx->nid; 1001 cx->key.size = sizeof(ID); 1002 cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, DB_SET ); 1003 if ( cx->rc ) { 1004 cx->dbc->c_close( cx->dbc ); 1005 goto done_one; 1006 } 1007 1008 /* If the on-disk count is zero we've never checked it. 1009 * Count it now. 1010 */ 1011 if ( !dkids ) { 1012 cx->dbc->c_count( cx->dbc, &dkids, 0 ); 1013 cx->ei->bei_dkids = dkids; 1014 } 1015 1016 cx->data.data = cx->buf; 1017 cx->data.ulen = BDB_IDL_UM_SIZE * sizeof(ID); 1018 cx->data.flags = DB_DBT_USERMEM; 1019 1020 if ( dkids > 1 ) { 1021 /* Fetch the rest of the IDs in a loop... */ 1022 while ( (cx->rc = cx->dbc->c_get( cx->dbc, &cx->key, &cx->data, 1023 DB_MULTIPLE | DB_NEXT_DUP )) == 0 ) { 1024 u_int8_t *j; 1025 size_t len; 1026 void *ptr; 1027 DB_MULTIPLE_INIT( ptr, &cx->data ); 1028 while (ptr) { 1029 DB_MULTIPLE_NEXT( ptr, &cx->data, j, len ); 1030 if (j) { 1031 EntryInfo *ei2; 1032 diskNode *d = (diskNode *)j; 1033 short nrlen; 1034 1035 BDB_DISK2ID( j + len - sizeof(ID), &ei.bei_id ); 1036 nrlen = ((d->nrdnlen[0] ^ 0x80) << 8) | d->nrdnlen[1]; 1037 ei.bei_nrdn.bv_len = nrlen; 1038 /* nrdn/rdn are set in-place. 1039 * hdb_cache_load will copy them as needed 1040 */ 1041 ei.bei_nrdn.bv_val = d->nrdn; 1042 ei.bei_rdn.bv_len = len - sizeof(diskNode) 1043 - ei.bei_nrdn.bv_len; 1044 ei.bei_rdn.bv_val = d->nrdn + ei.bei_nrdn.bv_len + 1; 1045 bdb_idl_append_one( cx->tmp, ei.bei_id ); 1046 hdb_cache_load( cx->bdb, &ei, &ei2 ); 1047 } 1048 } 1049 } 1050 } 1051 1052 cx->rc = cx->dbc->c_close( cx->dbc ); 1053done_one: 1054 bdb_cache_entryinfo_lock( cx->ei ); 1055 cx->ei->bei_state &= ~CACHE_ENTRY_ONELEVEL; 1056 bdb_cache_entryinfo_unlock( cx->ei ); 1057 if ( cx->rc ) 1058 return cx->rc; 1059 1060 } else { 1061 /* The in-memory cache is in sync with the on-disk data. 1062 * do we have any kids? 1063 */ 1064synced: 1065 cx->rc = 0; 1066 if ( cx->ei->bei_ckids > 0 ) { 1067 /* Walk the kids tree; order is irrelevant since bdb_idl_sort 1068 * will sort it later. 1069 */ 1070 avl_apply( cx->ei->bei_kids, apply_func, 1071 cx->tmp, -1, AVL_POSTORDER ); 1072 } 1073 bdb_cache_entryinfo_unlock( cx->ei ); 1074 } 1075 1076 if ( !BDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 3 ) 1077 bdb_idl_sort( cx->tmp, cx->buf ); 1078 if ( cx->bdb->bi_idl_cache_max_size && !BDB_IDL_IS_ZERO( cx->tmp )) { 1079 char *ptr = ((char *)&cx->id)-1; 1080 cx->key.data = ptr; 1081 cx->key.size = sizeof(ID)+1; 1082 *ptr = DN_ONE_PREFIX; 1083 bdb_idl_cache_put( cx->bdb, cx->db, &cx->key, cx->tmp, cx->rc ); 1084 } 1085 1086gotit: 1087 if ( !BDB_IDL_IS_ZERO( cx->tmp )) { 1088 if ( cx->prefix == DN_SUBTREE_PREFIX ) { 1089 bdb_idl_append( cx->ids, cx->tmp ); 1090 cx->need_sort = 1; 1091 if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) { 1092 ID *save, idcurs; 1093 EntryInfo *ei = cx->ei; 1094 int nokids = 1; 1095 save = cx->op->o_tmpalloc( BDB_IDL_SIZEOF( cx->tmp ), 1096 cx->op->o_tmpmemctx ); 1097 BDB_IDL_CPY( save, cx->tmp ); 1098 1099 idcurs = 0; 1100 cx->depth++; 1101 for ( cx->id = bdb_idl_first( save, &idcurs ); 1102 cx->id != NOID; 1103 cx->id = bdb_idl_next( save, &idcurs )) { 1104 EntryInfo *ei2; 1105 cx->ei = NULL; 1106 if ( bdb_cache_find_id( cx->op, cx->txn, cx->id, &cx->ei, 1107 ID_NOENTRY, NULL )) 1108 continue; 1109 if ( cx->ei ) { 1110 ei2 = cx->ei; 1111 if ( !( ei2->bei_state & CACHE_ENTRY_NO_KIDS )) { 1112 BDB_ID2DISK( cx->id, &cx->nid ); 1113 hdb_dn2idl_internal( cx ); 1114 if ( !BDB_IDL_IS_ZERO( cx->tmp )) 1115 nokids = 0; 1116 } 1117 bdb_cache_entryinfo_lock( ei2 ); 1118 ei2->bei_finders--; 1119 bdb_cache_entryinfo_unlock( ei2 ); 1120 } 1121 } 1122 cx->depth--; 1123 cx->op->o_tmpfree( save, cx->op->o_tmpmemctx ); 1124 if ( nokids ) { 1125 bdb_cache_entryinfo_lock( ei ); 1126 ei->bei_state |= CACHE_ENTRY_NO_GRANDKIDS; 1127 bdb_cache_entryinfo_unlock( ei ); 1128 } 1129 } 1130 /* Make sure caller knows it had kids! */ 1131 cx->tmp[0]=1; 1132 1133 cx->rc = 0; 1134 } else { 1135 BDB_IDL_CPY( cx->ids, cx->tmp ); 1136 } 1137 } 1138 return cx->rc; 1139} 1140 1141int 1142hdb_dn2idl( 1143 Operation *op, 1144 DB_TXN *txn, 1145 struct berval *ndn, 1146 EntryInfo *ei, 1147 ID *ids, 1148 ID *stack ) 1149{ 1150 struct bdb_info *bdb = (struct bdb_info *)op->o_bd->be_private; 1151 struct dn2id_cookie cx; 1152 1153 Debug( LDAP_DEBUG_TRACE, "=> hdb_dn2idl(\"%s\")\n", 1154 ndn->bv_val, 0, 0 ); 1155 1156#ifndef BDB_MULTIPLE_SUFFIXES 1157 if ( op->ors_scope != LDAP_SCOPE_ONELEVEL && 1158 ( ei->bei_id == 0 || 1159 ( ei->bei_parent->bei_id == 0 && op->o_bd->be_suffix[0].bv_len ))) 1160 { 1161 BDB_IDL_ALL( bdb, ids ); 1162 return 0; 1163 } 1164#endif 1165 1166 cx.id = ei->bei_id; 1167 BDB_ID2DISK( cx.id, &cx.nid ); 1168 cx.ei = ei; 1169 cx.bdb = bdb; 1170 cx.db = cx.bdb->bi_dn2id->bdi_db; 1171 cx.prefix = (op->ors_scope == LDAP_SCOPE_ONELEVEL) ? 1172 DN_ONE_PREFIX : DN_SUBTREE_PREFIX; 1173 cx.ids = ids; 1174 cx.tmp = stack; 1175 cx.buf = stack + BDB_IDL_UM_SIZE; 1176 cx.op = op; 1177 cx.txn = txn; 1178 cx.need_sort = 0; 1179 cx.depth = 0; 1180 1181 if ( cx.prefix == DN_SUBTREE_PREFIX ) { 1182 ids[0] = 1; 1183 ids[1] = cx.id; 1184 } else { 1185 BDB_IDL_ZERO( ids ); 1186 } 1187 if ( cx.ei->bei_state & CACHE_ENTRY_NO_KIDS ) 1188 return LDAP_SUCCESS; 1189 1190 DBTzero(&cx.key); 1191 cx.key.ulen = sizeof(ID); 1192 cx.key.size = sizeof(ID); 1193 cx.key.flags = DB_DBT_USERMEM; 1194 1195 DBTzero(&cx.data); 1196 1197 hdb_dn2idl_internal(&cx); 1198 if ( cx.need_sort ) { 1199 char *ptr = ((char *)&cx.id)-1; 1200 if ( !BDB_IDL_IS_RANGE( cx.ids ) && cx.ids[0] > 3 ) 1201 bdb_idl_sort( cx.ids, cx.tmp ); 1202 cx.key.data = ptr; 1203 cx.key.size = sizeof(ID)+1; 1204 *ptr = cx.prefix; 1205 cx.id = ei->bei_id; 1206 if ( cx.bdb->bi_idl_cache_max_size ) 1207 bdb_idl_cache_put( cx.bdb, cx.db, &cx.key, cx.ids, cx.rc ); 1208 } 1209 1210 if ( cx.rc == DB_NOTFOUND ) 1211 cx.rc = LDAP_SUCCESS; 1212 1213 return cx.rc; 1214} 1215#endif /* BDB_HIER */ 1216