1/* index.c - routines for dealing with attribute indexes */ 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 21#include <ac/string.h> 22#include <ac/socket.h> 23 24#include "slap.h" 25#include "back-bdb.h" 26#include "lutil_hash.h" 27 28static char presence_keyval[] = {0,0}; 29static struct berval presence_key = BER_BVC(presence_keyval); 30 31AttrInfo *bdb_index_mask( 32 Backend *be, 33 AttributeDescription *desc, 34 struct berval *atname ) 35{ 36 AttributeType *at; 37 AttrInfo *ai = bdb_attr_mask( be->be_private, desc ); 38 39 if( ai ) { 40 *atname = desc->ad_cname; 41 return ai; 42 } 43 44 /* If there is a tagging option, did we ever index the base 45 * type? If so, check for mask, otherwise it's not there. 46 */ 47 if( slap_ad_is_tagged( desc ) && desc != desc->ad_type->sat_ad ) { 48 /* has tagging option */ 49 ai = bdb_attr_mask( be->be_private, desc->ad_type->sat_ad ); 50 51 if ( ai && !( ai->ai_indexmask & SLAP_INDEX_NOTAGS ) ) { 52 *atname = desc->ad_type->sat_cname; 53 return ai; 54 } 55 } 56 57 /* see if supertype defined mask for its subtypes */ 58 for( at = desc->ad_type; at != NULL ; at = at->sat_sup ) { 59 /* If no AD, we've never indexed this type */ 60 if ( !at->sat_ad ) continue; 61 62 ai = bdb_attr_mask( be->be_private, at->sat_ad ); 63 64 if ( ai && !( ai->ai_indexmask & SLAP_INDEX_NOSUBTYPES ) ) { 65 *atname = at->sat_cname; 66 return ai; 67 } 68 } 69 70 return 0; 71} 72 73/* This function is only called when evaluating search filters. 74 */ 75int bdb_index_param( 76 Backend *be, 77 AttributeDescription *desc, 78 int ftype, 79 DB **dbp, 80 slap_mask_t *maskp, 81 struct berval *prefixp ) 82{ 83 AttrInfo *ai; 84 int rc; 85 slap_mask_t mask, type = 0; 86 DB *db; 87 88 ai = bdb_index_mask( be, desc, prefixp ); 89 90 if ( !ai ) { 91#ifdef BDB_MONITOR_IDX 92 switch ( ftype ) { 93 case LDAP_FILTER_PRESENT: 94 type = SLAP_INDEX_PRESENT; 95 break; 96 case LDAP_FILTER_APPROX: 97 type = SLAP_INDEX_APPROX; 98 break; 99 case LDAP_FILTER_EQUALITY: 100 type = SLAP_INDEX_EQUALITY; 101 break; 102 case LDAP_FILTER_SUBSTRINGS: 103 type = SLAP_INDEX_SUBSTR; 104 break; 105 default: 106 return LDAP_INAPPROPRIATE_MATCHING; 107 } 108 bdb_monitor_idx_add( be->be_private, desc, type ); 109#endif /* BDB_MONITOR_IDX */ 110 111 return LDAP_INAPPROPRIATE_MATCHING; 112 } 113 mask = ai->ai_indexmask; 114 115 rc = bdb_db_cache( be, prefixp, &db ); 116 117 if( rc != LDAP_SUCCESS ) { 118 return rc; 119 } 120 121 switch( ftype ) { 122 case LDAP_FILTER_PRESENT: 123 type = SLAP_INDEX_PRESENT; 124 if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) { 125 *prefixp = presence_key; 126 goto done; 127 } 128 break; 129 130 case LDAP_FILTER_APPROX: 131 type = SLAP_INDEX_APPROX; 132 if ( desc->ad_type->sat_approx ) { 133 if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) { 134 goto done; 135 } 136 break; 137 } 138 139 /* Use EQUALITY rule and index for approximate match */ 140 /* fall thru */ 141 142 case LDAP_FILTER_EQUALITY: 143 type = SLAP_INDEX_EQUALITY; 144 if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) { 145 goto done; 146 } 147 break; 148 149 case LDAP_FILTER_SUBSTRINGS: 150 type = SLAP_INDEX_SUBSTR; 151 if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) { 152 goto done; 153 } 154 break; 155 156 default: 157 return LDAP_OTHER; 158 } 159 160#ifdef BDB_MONITOR_IDX 161 bdb_monitor_idx_add( be->be_private, desc, type ); 162#endif /* BDB_MONITOR_IDX */ 163 164 return LDAP_INAPPROPRIATE_MATCHING; 165 166done: 167 *dbp = db; 168 *maskp = mask; 169 return LDAP_SUCCESS; 170} 171 172static int indexer( 173 Operation *op, 174 DB_TXN *txn, 175 AttributeDescription *ad, 176 struct berval *atname, 177 BerVarray vals, 178 ID id, 179 int opid, 180 slap_mask_t mask ) 181{ 182 int rc, i; 183 DB *db; 184 struct berval *keys; 185 186 assert( mask != 0 ); 187 188 rc = bdb_db_cache( op->o_bd, atname, &db ); 189 190 if ( rc != LDAP_SUCCESS ) { 191 Debug( LDAP_DEBUG_ANY, 192 "bdb_index_read: Could not open DB %s\n", 193 atname->bv_val, 0, 0 ); 194 return LDAP_OTHER; 195 } 196 197 if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) { 198 rc = bdb_key_change( op->o_bd, db, txn, &presence_key, id, opid ); 199 if( rc ) { 200 goto done; 201 } 202 } 203 204 if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) { 205 rc = ad->ad_type->sat_equality->smr_indexer( 206 LDAP_FILTER_EQUALITY, 207 mask, 208 ad->ad_type->sat_syntax, 209 ad->ad_type->sat_equality, 210 atname, vals, &keys, op->o_tmpmemctx ); 211 212 if( rc == LDAP_SUCCESS && keys != NULL ) { 213 for( i=0; keys[i].bv_val != NULL; i++ ) { 214 rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid ); 215 if( rc ) { 216 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 217 goto done; 218 } 219 } 220 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 221 } 222 rc = LDAP_SUCCESS; 223 } 224 225 if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) { 226 rc = ad->ad_type->sat_approx->smr_indexer( 227 LDAP_FILTER_APPROX, 228 mask, 229 ad->ad_type->sat_syntax, 230 ad->ad_type->sat_approx, 231 atname, vals, &keys, op->o_tmpmemctx ); 232 233 if( rc == LDAP_SUCCESS && keys != NULL ) { 234 for( i=0; keys[i].bv_val != NULL; i++ ) { 235 rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid ); 236 if( rc ) { 237 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 238 goto done; 239 } 240 } 241 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 242 } 243 244 rc = LDAP_SUCCESS; 245 } 246 247 if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) { 248 rc = ad->ad_type->sat_substr->smr_indexer( 249 LDAP_FILTER_SUBSTRINGS, 250 mask, 251 ad->ad_type->sat_syntax, 252 ad->ad_type->sat_substr, 253 atname, vals, &keys, op->o_tmpmemctx ); 254 255 if( rc == LDAP_SUCCESS && keys != NULL ) { 256 for( i=0; keys[i].bv_val != NULL; i++ ) { 257 rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid ); 258 if( rc ) { 259 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 260 goto done; 261 } 262 } 263 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 264 } 265 266 rc = LDAP_SUCCESS; 267 } 268 269done: 270 switch( rc ) { 271 /* The callers all know how to deal with these results */ 272 case 0: 273 case DB_LOCK_DEADLOCK: 274 case DB_LOCK_NOTGRANTED: 275 break; 276 /* Anything else is bad news */ 277 default: 278 rc = LDAP_OTHER; 279 } 280 return rc; 281} 282 283static int index_at_values( 284 Operation *op, 285 DB_TXN *txn, 286 AttributeDescription *ad, 287 AttributeType *type, 288 struct berval *tags, 289 BerVarray vals, 290 ID id, 291 int opid ) 292{ 293 int rc; 294 slap_mask_t mask = 0; 295 int ixop = opid; 296 AttrInfo *ai = NULL; 297 298 if ( opid == BDB_INDEX_UPDATE_OP ) 299 ixop = SLAP_INDEX_ADD_OP; 300 301 if( type->sat_sup ) { 302 /* recurse */ 303 rc = index_at_values( op, txn, NULL, 304 type->sat_sup, tags, 305 vals, id, opid ); 306 307 if( rc ) return rc; 308 } 309 310 /* If this type has no AD, we've never used it before */ 311 if( type->sat_ad ) { 312 ai = bdb_attr_mask( op->o_bd->be_private, type->sat_ad ); 313 if ( ai ) { 314#ifdef LDAP_COMP_MATCH 315 /* component indexing */ 316 if ( ai->ai_cr ) { 317 ComponentReference *cr; 318 for( cr = ai->ai_cr ; cr ; cr = cr->cr_next ) { 319 rc = indexer( op, txn, cr->cr_ad, &type->sat_cname, 320 cr->cr_nvals, id, ixop, 321 cr->cr_indexmask ); 322 } 323 } 324#endif 325 ad = type->sat_ad; 326 /* If we're updating the index, just set the new bits that aren't 327 * already in the old mask. 328 */ 329 if ( opid == BDB_INDEX_UPDATE_OP ) 330 mask = ai->ai_newmask & ~ai->ai_indexmask; 331 else 332 /* For regular updates, if there is a newmask use it. Otherwise 333 * just use the old mask. 334 */ 335 mask = ai->ai_newmask ? ai->ai_newmask : ai->ai_indexmask; 336 if( mask ) { 337 rc = indexer( op, txn, ad, &type->sat_cname, 338 vals, id, ixop, mask ); 339 340 if( rc ) return rc; 341 } 342 } 343 } 344 345 if( tags->bv_len ) { 346 AttributeDescription *desc; 347 348 desc = ad_find_tags( type, tags ); 349 if( desc ) { 350 ai = bdb_attr_mask( op->o_bd->be_private, desc ); 351 352 if( ai ) { 353 if ( opid == BDB_INDEX_UPDATE_OP ) 354 mask = ai->ai_newmask & ~ai->ai_indexmask; 355 else 356 mask = ai->ai_newmask ? ai->ai_newmask : ai->ai_indexmask; 357 if ( mask ) { 358 rc = indexer( op, txn, desc, &desc->ad_cname, 359 vals, id, ixop, mask ); 360 361 if( rc ) { 362 return rc; 363 } 364 } 365 } 366 } 367 } 368 369 return LDAP_SUCCESS; 370} 371 372int bdb_index_values( 373 Operation *op, 374 DB_TXN *txn, 375 AttributeDescription *desc, 376 BerVarray vals, 377 ID id, 378 int opid ) 379{ 380 int rc; 381 382 /* Never index ID 0 */ 383 if ( id == 0 ) 384 return 0; 385 386 rc = index_at_values( op, txn, desc, 387 desc->ad_type, &desc->ad_tags, 388 vals, id, opid ); 389 390 return rc; 391} 392 393/* Get the list of which indices apply to this attr */ 394int 395bdb_index_recset( 396 struct bdb_info *bdb, 397 Attribute *a, 398 AttributeType *type, 399 struct berval *tags, 400 IndexRec *ir ) 401{ 402 int rc, slot; 403 AttrList *al; 404 405 if( type->sat_sup ) { 406 /* recurse */ 407 rc = bdb_index_recset( bdb, a, type->sat_sup, tags, ir ); 408 if( rc ) return rc; 409 } 410 /* If this type has no AD, we've never used it before */ 411 if( type->sat_ad ) { 412 slot = bdb_attr_slot( bdb, type->sat_ad, NULL ); 413 if ( slot >= 0 ) { 414 ir[slot].ai = bdb->bi_attrs[slot]; 415 al = ch_malloc( sizeof( AttrList )); 416 al->attr = a; 417 al->next = ir[slot].attrs; 418 ir[slot].attrs = al; 419 } 420 } 421 if( tags->bv_len ) { 422 AttributeDescription *desc; 423 424 desc = ad_find_tags( type, tags ); 425 if( desc ) { 426 slot = bdb_attr_slot( bdb, desc, NULL ); 427 if ( slot >= 0 ) { 428 ir[slot].ai = bdb->bi_attrs[slot]; 429 al = ch_malloc( sizeof( AttrList )); 430 al->attr = a; 431 al->next = ir[slot].attrs; 432 ir[slot].attrs = al; 433 } 434 } 435 } 436 return LDAP_SUCCESS; 437} 438 439/* Apply the indices for the recset */ 440int bdb_index_recrun( 441 Operation *op, 442 struct bdb_info *bdb, 443 IndexRec *ir0, 444 ID id, 445 int base ) 446{ 447 IndexRec *ir; 448 AttrList *al; 449 int i, rc = 0; 450 451 /* Never index ID 0 */ 452 if ( id == 0 ) 453 return 0; 454 455 for (i=base; i<bdb->bi_nattrs; i+=slap_tool_thread_max-1) { 456 ir = ir0 + i; 457 if ( !ir->ai ) continue; 458 while (( al = ir->attrs )) { 459 ir->attrs = al->next; 460 rc = indexer( op, NULL, ir->ai->ai_desc, 461 &ir->ai->ai_desc->ad_type->sat_cname, 462 al->attr->a_nvals, id, SLAP_INDEX_ADD_OP, 463 ir->ai->ai_indexmask ); 464 free( al ); 465 if ( rc ) break; 466 } 467 } 468 return rc; 469} 470 471int 472bdb_index_entry( 473 Operation *op, 474 DB_TXN *txn, 475 int opid, 476 Entry *e ) 477{ 478 int rc; 479 Attribute *ap = e->e_attrs; 480#if 0 /* ifdef LDAP_COMP_MATCH */ 481 ComponentReference *cr_list = NULL; 482 ComponentReference *cr = NULL, *dupped_cr = NULL; 483 void* decoded_comp; 484 ComponentSyntaxInfo* csi_attr; 485 Syntax* syn; 486 AttributeType* at; 487 int i, num_attr; 488 void* mem_op; 489 struct berval value = {0}; 490#endif 491 492 /* Never index ID 0 */ 493 if ( e->e_id == 0 ) 494 return 0; 495 496 Debug( LDAP_DEBUG_TRACE, "=> index_entry_%s( %ld, \"%s\" )\n", 497 opid == SLAP_INDEX_DELETE_OP ? "del" : "add", 498 (long) e->e_id, e->e_dn ); 499 500 /* add each attribute to the indexes */ 501 for ( ; ap != NULL; ap = ap->a_next ) { 502#if 0 /* ifdef LDAP_COMP_MATCH */ 503 AttrInfo *ai; 504 /* see if attribute has components to be indexed */ 505 ai = bdb_attr_mask( op->o_bd->be_private, ap->a_desc->ad_type->sat_ad ); 506 if ( !ai ) continue; 507 cr_list = ai->ai_cr; 508 if ( attr_converter && cr_list ) { 509 syn = ap->a_desc->ad_type->sat_syntax; 510 ap->a_comp_data = op->o_tmpalloc( sizeof( ComponentData ), op->o_tmpmemctx ); 511 /* Memory chunk(nibble) pre-allocation for decoders */ 512 mem_op = nibble_mem_allocator ( 1024*16, 1024*4 ); 513 ap->a_comp_data->cd_mem_op = mem_op; 514 for( cr = cr_list ; cr ; cr = cr->cr_next ) { 515 /* count how many values in an attribute */ 516 for( num_attr=0; ap->a_vals[num_attr].bv_val != NULL; num_attr++ ); 517 num_attr++; 518 cr->cr_nvals = (BerVarray)op->o_tmpalloc( sizeof( struct berval )*num_attr, op->o_tmpmemctx ); 519 for( i=0; ap->a_vals[i].bv_val != NULL; i++ ) { 520 /* decoding attribute value */ 521 decoded_comp = attr_converter ( ap, syn, &ap->a_vals[i] ); 522 if ( !decoded_comp ) 523 return LDAP_DECODING_ERROR; 524 /* extracting the referenced component */ 525 dupped_cr = dup_comp_ref( op, cr ); 526 csi_attr = ((ComponentSyntaxInfo*)decoded_comp)->csi_comp_desc->cd_extract_i( mem_op, dupped_cr, decoded_comp ); 527 if ( !csi_attr ) 528 return LDAP_DECODING_ERROR; 529 cr->cr_asn_type_id = csi_attr->csi_comp_desc->cd_type_id; 530 cr->cr_ad = (AttributeDescription*)get_component_description ( cr->cr_asn_type_id ); 531 if ( !cr->cr_ad ) 532 return LDAP_INVALID_SYNTAX; 533 at = cr->cr_ad->ad_type; 534 /* encoding the value of component in GSER */ 535 rc = component_encoder( mem_op, csi_attr, &value ); 536 if ( rc != LDAP_SUCCESS ) 537 return LDAP_ENCODING_ERROR; 538 /* Normalize the encoded component values */ 539 if ( at->sat_equality && at->sat_equality->smr_normalize ) { 540 rc = at->sat_equality->smr_normalize ( 541 SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX, 542 at->sat_syntax, at->sat_equality, 543 &value, &cr->cr_nvals[i], op->o_tmpmemctx ); 544 } else { 545 cr->cr_nvals[i] = value; 546 } 547 } 548 /* The end of BerVarray */ 549 cr->cr_nvals[num_attr-1].bv_val = NULL; 550 cr->cr_nvals[num_attr-1].bv_len = 0; 551 } 552 op->o_tmpfree( ap->a_comp_data, op->o_tmpmemctx ); 553 nibble_mem_free ( mem_op ); 554 ap->a_comp_data = NULL; 555 } 556#endif 557 rc = bdb_index_values( op, txn, ap->a_desc, 558 ap->a_nvals, e->e_id, opid ); 559 560 if( rc != LDAP_SUCCESS ) { 561 Debug( LDAP_DEBUG_TRACE, 562 "<= index_entry_%s( %ld, \"%s\" ) failure\n", 563 opid == SLAP_INDEX_ADD_OP ? "add" : "del", 564 (long) e->e_id, e->e_dn ); 565 return rc; 566 } 567 } 568 569 Debug( LDAP_DEBUG_TRACE, "<= index_entry_%s( %ld, \"%s\" ) success\n", 570 opid == SLAP_INDEX_DELETE_OP ? "del" : "add", 571 (long) e->e_id, e->e_dn ); 572 573 return LDAP_SUCCESS; 574} 575