1/* $NetBSD: index.c,v 1.3 2021/08/14 16:15:00 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-2021 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.3 2021/08/14 16:15:00 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 33static char presence_keyval[] = {0,0,0,0,0}; 34static struct berval presence_key[2] = {BER_BVC(presence_keyval), BER_BVNULL}; 35 36AttrInfo *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 */ 80int 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 163done: 164 *dbip = ai->ai_dbi; 165 *maskp = mask; 166 return LDAP_SUCCESS; 167} 168 169static 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; 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 AttrIxInfo *ax = (AttrIxInfo *)LDAP_SLIST_FIRST(&op->o_extra); 200 ax->ai_ai = ai; 201 keyfunc = mdb_tool_idl_add; 202 mc = (MDB_cursor *)ax; 203 } else 204#endif 205 keyfunc = mdb_idl_insert_keys; 206 } else 207 keyfunc = mdb_idl_delete_keys; 208 209 if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) { 210 rc = keyfunc( op->o_bd, mc, presence_key, id ); 211 if( rc ) { 212 err = "presence"; 213 goto done; 214 } 215 } 216 217 if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) { 218 rc = ad->ad_type->sat_equality->smr_indexer( 219 LDAP_FILTER_EQUALITY, 220 mask, 221 ad->ad_type->sat_syntax, 222 ad->ad_type->sat_equality, 223 atname, vals, &keys, op->o_tmpmemctx ); 224 225 if( rc == LDAP_SUCCESS && keys != NULL ) { 226 rc = keyfunc( op->o_bd, mc, keys, id ); 227 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 228 if ( rc ) { 229 err = "equality"; 230 goto done; 231 } 232 } 233 rc = LDAP_SUCCESS; 234 } 235 236 if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) { 237 rc = ad->ad_type->sat_approx->smr_indexer( 238 LDAP_FILTER_APPROX, 239 mask, 240 ad->ad_type->sat_syntax, 241 ad->ad_type->sat_approx, 242 atname, vals, &keys, op->o_tmpmemctx ); 243 244 if( rc == LDAP_SUCCESS && keys != NULL ) { 245 rc = keyfunc( op->o_bd, mc, keys, id ); 246 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 247 if ( rc ) { 248 err = "approx"; 249 goto done; 250 } 251 } 252 253 rc = LDAP_SUCCESS; 254 } 255 256 if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) { 257 rc = ad->ad_type->sat_substr->smr_indexer( 258 LDAP_FILTER_SUBSTRINGS, 259 mask, 260 ad->ad_type->sat_syntax, 261 ad->ad_type->sat_substr, 262 atname, vals, &keys, op->o_tmpmemctx ); 263 264 if( rc == LDAP_SUCCESS && keys != NULL ) { 265 rc = keyfunc( op->o_bd, mc, keys, id ); 266 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 267 if( rc ) { 268 err = "substr"; 269 goto done; 270 } 271 } 272 273 rc = LDAP_SUCCESS; 274 } 275 276done: 277 if ( !(slapMode & SLAP_TOOL_QUICK)) 278 mdb_cursor_close( mc ); 279 switch( rc ) { 280 /* The callers all know how to deal with these results */ 281 case 0: 282 break; 283 /* Anything else is bad news */ 284 default: 285 rc = LDAP_OTHER; 286 } 287 return rc; 288} 289 290static int index_at_values( 291 Operation *op, 292 MDB_txn *txn, 293 AttributeDescription *ad, 294 AttributeType *type, 295 struct berval *tags, 296 BerVarray vals, 297 ID id, 298 int opid ) 299{ 300 int rc; 301 slap_mask_t mask = 0; 302 int ixop = opid; 303 AttrInfo *ai = NULL; 304 305 if ( opid == MDB_INDEX_UPDATE_OP ) 306 ixop = SLAP_INDEX_ADD_OP; 307 308 if( type->sat_sup ) { 309 /* recurse */ 310 rc = index_at_values( op, txn, NULL, 311 type->sat_sup, tags, 312 vals, id, opid ); 313 314 if( rc ) return rc; 315 } 316 317 /* If this type has no AD, we've never used it before */ 318 if( type->sat_ad ) { 319 ai = mdb_attr_mask( op->o_bd->be_private, type->sat_ad ); 320 if ( ai && ( ai->ai_indexmask || ai->ai_newmask )) { 321#ifdef LDAP_COMP_MATCH 322 /* component indexing */ 323 if ( ai->ai_cr ) { 324 ComponentReference *cr; 325 for( cr = ai->ai_cr ; cr ; cr = cr->cr_next ) { 326 rc = indexer( op, txn, ai, cr->cr_ad, &type->sat_cname, 327 cr->cr_nvals, id, ixop, 328 cr->cr_indexmask ); 329 } 330 } 331#endif 332 ad = type->sat_ad; 333 /* If we're updating the index, just set the new bits that aren't 334 * already in the old mask. 335 */ 336 if ( opid == MDB_INDEX_UPDATE_OP ) 337 mask = ai->ai_newmask & ~ai->ai_indexmask; 338 else 339 /* For regular updates, if there is a newmask use it. Otherwise 340 * just use the old mask. 341 */ 342 mask = ai->ai_newmask ? ai->ai_newmask : ai->ai_indexmask; 343 if( mask ) { 344 rc = indexer( op, txn, ai, ad, &type->sat_cname, 345 vals, id, ixop, mask ); 346 347 if( rc ) return rc; 348 } 349 } 350 } 351 352 if( tags->bv_len ) { 353 AttributeDescription *desc; 354 355 desc = ad_find_tags( type, tags ); 356 if( desc ) { 357 ai = mdb_attr_mask( op->o_bd->be_private, desc ); 358 359 if( ai && ( ai->ai_indexmask || ai->ai_newmask )) { 360 if ( opid == MDB_INDEX_UPDATE_OP ) 361 mask = ai->ai_newmask & ~ai->ai_indexmask; 362 else 363 mask = ai->ai_newmask ? ai->ai_newmask : ai->ai_indexmask; 364 if ( mask ) { 365 rc = indexer( op, txn, ai, desc, &desc->ad_cname, 366 vals, id, ixop, mask ); 367 368 if( rc ) { 369 return rc; 370 } 371 } 372 } 373 } 374 } 375 376 return LDAP_SUCCESS; 377} 378 379int mdb_index_values( 380 Operation *op, 381 MDB_txn *txn, 382 AttributeDescription *desc, 383 BerVarray vals, 384 ID id, 385 int opid ) 386{ 387 int rc; 388 389 /* Never index ID 0 */ 390 if ( id == 0 ) 391 return 0; 392 393 rc = index_at_values( op, txn, desc, 394 desc->ad_type, &desc->ad_tags, 395 vals, id, opid ); 396 397 return rc; 398} 399 400/* Get the list of which indices apply to this attr */ 401int 402mdb_index_recset( 403 struct mdb_info *mdb, 404 Attribute *a, 405 AttributeType *type, 406 struct berval *tags, 407 IndexRec *ir ) 408{ 409 int rc, slot; 410 AttrList *al; 411 412 if( type->sat_sup ) { 413 /* recurse */ 414 rc = mdb_index_recset( mdb, a, type->sat_sup, tags, ir ); 415 if( rc ) return rc; 416 } 417 /* If this type has no AD, we've never used it before */ 418 if( type->sat_ad ) { 419 slot = mdb_attr_slot( mdb, type->sat_ad, NULL ); 420 if ( slot >= 0 ) { 421 ir[slot].ir_ai = mdb->mi_attrs[slot]; 422 al = ch_malloc( sizeof( AttrList )); 423 al->attr = a; 424 al->next = ir[slot].ir_attrs; 425 ir[slot].ir_attrs = al; 426 } 427 } 428 if( tags->bv_len ) { 429 AttributeDescription *desc; 430 431 desc = ad_find_tags( type, tags ); 432 if( desc ) { 433 slot = mdb_attr_slot( mdb, desc, NULL ); 434 if ( slot >= 0 ) { 435 ir[slot].ir_ai = mdb->mi_attrs[slot]; 436 al = ch_malloc( sizeof( AttrList )); 437 al->attr = a; 438 al->next = ir[slot].ir_attrs; 439 ir[slot].ir_attrs = al; 440 } 441 } 442 } 443 return LDAP_SUCCESS; 444} 445 446/* Apply the indices for the recset */ 447int mdb_index_recrun( 448 Operation *op, 449 MDB_txn *txn, 450 struct mdb_info *mdb, 451 IndexRec *ir0, 452 ID id, 453 int base ) 454{ 455 IndexRec *ir; 456 AttrList *al; 457 int i, rc = 0; 458 459 /* Never index ID 0 */ 460 if ( id == 0 ) 461 return 0; 462 463 for (i=base; i<mdb->mi_nattrs; i+=slap_tool_thread_max-1) { 464 ir = ir0 + i; 465 if ( !ir->ir_ai ) continue; 466 while (( al = ir->ir_attrs )) { 467 ir->ir_attrs = al->next; 468 rc = indexer( op, txn, ir->ir_ai, ir->ir_ai->ai_desc, 469 &ir->ir_ai->ai_desc->ad_type->sat_cname, 470 al->attr->a_nvals, id, SLAP_INDEX_ADD_OP, 471 ir->ir_ai->ai_indexmask ); 472 free( al ); 473 if ( rc ) break; 474 } 475 } 476 return rc; 477} 478 479int 480mdb_index_entry( 481 Operation *op, 482 MDB_txn *txn, 483 int opid, 484 Entry *e ) 485{ 486 int rc; 487 Attribute *ap = e->e_attrs; 488#if 0 /* ifdef LDAP_COMP_MATCH */ 489 ComponentReference *cr_list = NULL; 490 ComponentReference *cr = NULL, *dupped_cr = NULL; 491 void* decoded_comp; 492 ComponentSyntaxInfo* csi_attr; 493 Syntax* syn; 494 AttributeType* at; 495 int i, num_attr; 496 void* mem_op; 497 struct berval value = {0}; 498#endif 499 500 /* Never index ID 0 */ 501 if ( e->e_id == 0 ) 502 return 0; 503 504 Debug( LDAP_DEBUG_TRACE, "=> index_entry_%s( %ld, \"%s\" )\n", 505 opid == SLAP_INDEX_DELETE_OP ? "del" : "add", 506 (long) e->e_id, e->e_dn ? e->e_dn : "" ); 507 508 /* add each attribute to the indexes */ 509 for ( ; ap != NULL; ap = ap->a_next ) { 510#if 0 /* ifdef LDAP_COMP_MATCH */ 511 AttrInfo *ai; 512 /* see if attribute has components to be indexed */ 513 ai = mdb_attr_mask( op->o_bd->be_private, ap->a_desc->ad_type->sat_ad ); 514 if ( !ai ) continue; 515 cr_list = ai->ai_cr; 516 if ( attr_converter && cr_list ) { 517 syn = ap->a_desc->ad_type->sat_syntax; 518 ap->a_comp_data = op->o_tmpalloc( sizeof( ComponentData ), op->o_tmpmemctx ); 519 /* Memory chunk(nibble) pre-allocation for decoders */ 520 mem_op = nibble_mem_allocator ( 1024*16, 1024*4 ); 521 ap->a_comp_data->cd_mem_op = mem_op; 522 for( cr = cr_list ; cr ; cr = cr->cr_next ) { 523 /* count how many values in an attribute */ 524 for( num_attr=0; ap->a_vals[num_attr].bv_val != NULL; num_attr++ ); 525 num_attr++; 526 cr->cr_nvals = (BerVarray)op->o_tmpalloc( sizeof( struct berval )*num_attr, op->o_tmpmemctx ); 527 for( i=0; ap->a_vals[i].bv_val != NULL; i++ ) { 528 /* decoding attribute value */ 529 decoded_comp = attr_converter ( ap, syn, &ap->a_vals[i] ); 530 if ( !decoded_comp ) 531 return LDAP_DECODING_ERROR; 532 /* extracting the referenced component */ 533 dupped_cr = dup_comp_ref( op, cr ); 534 csi_attr = ((ComponentSyntaxInfo*)decoded_comp)->csi_comp_desc->cd_extract_i( mem_op, dupped_cr, decoded_comp ); 535 if ( !csi_attr ) 536 return LDAP_DECODING_ERROR; 537 cr->cr_asn_type_id = csi_attr->csi_comp_desc->cd_type_id; 538 cr->cr_ad = (AttributeDescription*)get_component_description ( cr->cr_asn_type_id ); 539 if ( !cr->cr_ad ) 540 return LDAP_INVALID_SYNTAX; 541 at = cr->cr_ad->ad_type; 542 /* encoding the value of component in GSER */ 543 rc = component_encoder( mem_op, csi_attr, &value ); 544 if ( rc != LDAP_SUCCESS ) 545 return LDAP_ENCODING_ERROR; 546 /* Normalize the encoded component values */ 547 if ( at->sat_equality && at->sat_equality->smr_normalize ) { 548 rc = at->sat_equality->smr_normalize ( 549 SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX, 550 at->sat_syntax, at->sat_equality, 551 &value, &cr->cr_nvals[i], op->o_tmpmemctx ); 552 } else { 553 cr->cr_nvals[i] = value; 554 } 555 } 556 /* The end of BerVarray */ 557 cr->cr_nvals[num_attr-1].bv_val = NULL; 558 cr->cr_nvals[num_attr-1].bv_len = 0; 559 } 560 op->o_tmpfree( ap->a_comp_data, op->o_tmpmemctx ); 561 nibble_mem_free ( mem_op ); 562 ap->a_comp_data = NULL; 563 } 564#endif 565 rc = mdb_index_values( op, txn, ap->a_desc, 566 ap->a_nvals, e->e_id, opid ); 567 568 if( rc != LDAP_SUCCESS ) { 569 Debug( LDAP_DEBUG_TRACE, 570 "<= index_entry_%s( %ld, \"%s\" ) failure\n", 571 opid == SLAP_INDEX_ADD_OP ? "add" : "del", 572 (long) e->e_id, e->e_dn ); 573 return rc; 574 } 575 } 576 577 Debug( LDAP_DEBUG_TRACE, "<= index_entry_%s( %ld, \"%s\" ) success\n", 578 opid == SLAP_INDEX_DELETE_OP ? "del" : "add", 579 (long) e->e_id, e->e_dn ? e->e_dn : "" ); 580 581 return LDAP_SUCCESS; 582} 583