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