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