1/* $NetBSD: index.c,v 1.1.1.3 2010/12/12 15:22:56 adam Exp $ */ 2 3/* index.c - routines for dealing with attribute indexes */ 4/* OpenLDAP: pkg/ldap/servers/slapd/back-bdb/index.c,v 1.61.2.9 2010/04/13 20:23:25 kurt Exp */ 5/* This work is part of OpenLDAP Software <http://www.openldap.org/>. 6 * 7 * Copyright 2000-2010 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-bdb.h" 28#include "lutil_hash.h" 29 30static char presence_keyval[] = {0,0}; 31static struct berval presence_key = BER_BVC(presence_keyval); 32 33AttrInfo *bdb_index_mask( 34 Backend *be, 35 AttributeDescription *desc, 36 struct berval *atname ) 37{ 38 AttributeType *at; 39 AttrInfo *ai = bdb_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 = bdb_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 = bdb_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 */ 77int bdb_index_param( 78 Backend *be, 79 AttributeDescription *desc, 80 int ftype, 81 DB **dbp, 82 slap_mask_t *maskp, 83 struct berval *prefixp ) 84{ 85 AttrInfo *ai; 86 int rc; 87 slap_mask_t mask, type = 0; 88 DB *db; 89 90 ai = bdb_index_mask( be, desc, prefixp ); 91 92 if ( !ai ) { 93#ifdef BDB_MONITOR_IDX 94 switch ( ftype ) { 95 case LDAP_FILTER_PRESENT: 96 type = SLAP_INDEX_PRESENT; 97 break; 98 case LDAP_FILTER_APPROX: 99 type = SLAP_INDEX_APPROX; 100 break; 101 case LDAP_FILTER_EQUALITY: 102 type = SLAP_INDEX_EQUALITY; 103 break; 104 case LDAP_FILTER_SUBSTRINGS: 105 type = SLAP_INDEX_SUBSTR; 106 break; 107 default: 108 return LDAP_INAPPROPRIATE_MATCHING; 109 } 110 bdb_monitor_idx_add( be->be_private, desc, type ); 111#endif /* BDB_MONITOR_IDX */ 112 113 return LDAP_INAPPROPRIATE_MATCHING; 114 } 115 mask = ai->ai_indexmask; 116 117 rc = bdb_db_cache( be, prefixp, &db ); 118 119 if( rc != LDAP_SUCCESS ) { 120 return rc; 121 } 122 123 switch( ftype ) { 124 case LDAP_FILTER_PRESENT: 125 type = SLAP_INDEX_PRESENT; 126 if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) { 127 *prefixp = presence_key; 128 goto done; 129 } 130 break; 131 132 case LDAP_FILTER_APPROX: 133 type = SLAP_INDEX_APPROX; 134 if ( desc->ad_type->sat_approx ) { 135 if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) { 136 goto done; 137 } 138 break; 139 } 140 141 /* Use EQUALITY rule and index for approximate match */ 142 /* fall thru */ 143 144 case LDAP_FILTER_EQUALITY: 145 type = SLAP_INDEX_EQUALITY; 146 if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) { 147 goto done; 148 } 149 break; 150 151 case LDAP_FILTER_SUBSTRINGS: 152 type = SLAP_INDEX_SUBSTR; 153 if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) { 154 goto done; 155 } 156 break; 157 158 default: 159 return LDAP_OTHER; 160 } 161 162#ifdef BDB_MONITOR_IDX 163 bdb_monitor_idx_add( be->be_private, desc, type ); 164#endif /* BDB_MONITOR_IDX */ 165 166 return LDAP_INAPPROPRIATE_MATCHING; 167 168done: 169 *dbp = db; 170 *maskp = mask; 171 return LDAP_SUCCESS; 172} 173 174static int indexer( 175 Operation *op, 176 DB_TXN *txn, 177 AttributeDescription *ad, 178 struct berval *atname, 179 BerVarray vals, 180 ID id, 181 int opid, 182 slap_mask_t mask ) 183{ 184 int rc, i; 185 DB *db; 186 struct berval *keys; 187 188 assert( mask != 0 ); 189 190 rc = bdb_db_cache( op->o_bd, atname, &db ); 191 192 if ( rc != LDAP_SUCCESS ) { 193 Debug( LDAP_DEBUG_ANY, 194 "bdb_index_read: Could not open DB %s\n", 195 atname->bv_val, 0, 0 ); 196 return LDAP_OTHER; 197 } 198 199 if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) { 200 rc = bdb_key_change( op->o_bd, db, txn, &presence_key, id, opid ); 201 if( rc ) { 202 goto done; 203 } 204 } 205 206 if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) { 207 rc = ad->ad_type->sat_equality->smr_indexer( 208 LDAP_FILTER_EQUALITY, 209 mask, 210 ad->ad_type->sat_syntax, 211 ad->ad_type->sat_equality, 212 atname, vals, &keys, op->o_tmpmemctx ); 213 214 if( rc == LDAP_SUCCESS && keys != NULL ) { 215 for( i=0; keys[i].bv_val != NULL; i++ ) { 216 rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid ); 217 if( rc ) { 218 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 219 goto done; 220 } 221 } 222 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 223 } 224 rc = LDAP_SUCCESS; 225 } 226 227 if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) { 228 rc = ad->ad_type->sat_approx->smr_indexer( 229 LDAP_FILTER_APPROX, 230 mask, 231 ad->ad_type->sat_syntax, 232 ad->ad_type->sat_approx, 233 atname, vals, &keys, op->o_tmpmemctx ); 234 235 if( rc == LDAP_SUCCESS && keys != NULL ) { 236 for( i=0; keys[i].bv_val != NULL; i++ ) { 237 rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid ); 238 if( rc ) { 239 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 240 goto done; 241 } 242 } 243 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 244 } 245 246 rc = LDAP_SUCCESS; 247 } 248 249 if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) { 250 rc = ad->ad_type->sat_substr->smr_indexer( 251 LDAP_FILTER_SUBSTRINGS, 252 mask, 253 ad->ad_type->sat_syntax, 254 ad->ad_type->sat_substr, 255 atname, vals, &keys, op->o_tmpmemctx ); 256 257 if( rc == LDAP_SUCCESS && keys != NULL ) { 258 for( i=0; keys[i].bv_val != NULL; i++ ) { 259 rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid ); 260 if( rc ) { 261 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 262 goto done; 263 } 264 } 265 ber_bvarray_free_x( keys, op->o_tmpmemctx ); 266 } 267 268 rc = LDAP_SUCCESS; 269 } 270 271done: 272 switch( rc ) { 273 /* The callers all know how to deal with these results */ 274 case 0: 275 case DB_LOCK_DEADLOCK: 276 case DB_LOCK_NOTGRANTED: 277 break; 278 /* Anything else is bad news */ 279 default: 280 rc = LDAP_OTHER; 281 } 282 return rc; 283} 284 285static int index_at_values( 286 Operation *op, 287 DB_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 == BDB_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 = bdb_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, 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 == BDB_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, 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 = bdb_attr_mask( op->o_bd->be_private, desc ); 353 354 if( ai ) { 355 if ( opid == BDB_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, 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 374int bdb_index_values( 375 Operation *op, 376 DB_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 */ 396int 397bdb_index_recset( 398 struct bdb_info *bdb, 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 = bdb_index_recset( bdb, 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 = bdb_attr_slot( bdb, type->sat_ad, NULL ); 415 if ( slot >= 0 ) { 416 ir[slot].ai = bdb->bi_attrs[slot]; 417 al = ch_malloc( sizeof( AttrList )); 418 al->attr = a; 419 al->next = ir[slot].attrs; 420 ir[slot].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 = bdb_attr_slot( bdb, desc, NULL ); 429 if ( slot >= 0 ) { 430 ir[slot].ai = bdb->bi_attrs[slot]; 431 al = ch_malloc( sizeof( AttrList )); 432 al->attr = a; 433 al->next = ir[slot].attrs; 434 ir[slot].attrs = al; 435 } 436 } 437 } 438 return LDAP_SUCCESS; 439} 440 441/* Apply the indices for the recset */ 442int bdb_index_recrun( 443 Operation *op, 444 struct bdb_info *bdb, 445 IndexRec *ir0, 446 ID id, 447 int base ) 448{ 449 IndexRec *ir; 450 AttrList *al; 451 int i, rc = 0; 452 453 /* Never index ID 0 */ 454 if ( id == 0 ) 455 return 0; 456 457 for (i=base; i<bdb->bi_nattrs; i+=slap_tool_thread_max) { 458 ir = ir0 + i; 459 if ( !ir->ai ) continue; 460 while (( al = ir->attrs )) { 461 ir->attrs = al->next; 462 rc = indexer( op, NULL, ir->ai->ai_desc, 463 &ir->ai->ai_desc->ad_type->sat_cname, 464 al->attr->a_nvals, id, SLAP_INDEX_ADD_OP, 465 ir->ai->ai_indexmask ); 466 free( al ); 467 if ( rc ) break; 468 } 469 } 470 return rc; 471} 472 473int 474bdb_index_entry( 475 Operation *op, 476 DB_TXN *txn, 477 int opid, 478 Entry *e ) 479{ 480 int rc; 481 Attribute *ap = e->e_attrs; 482#if 0 /* ifdef LDAP_COMP_MATCH */ 483 ComponentReference *cr_list = NULL; 484 ComponentReference *cr = NULL, *dupped_cr = NULL; 485 void* decoded_comp; 486 ComponentSyntaxInfo* csi_attr; 487 Syntax* syn; 488 AttributeType* at; 489 int i, num_attr; 490 void* mem_op; 491 struct berval value = {0}; 492#endif 493 494 /* Never index ID 0 */ 495 if ( e->e_id == 0 ) 496 return 0; 497 498 Debug( LDAP_DEBUG_TRACE, "=> index_entry_%s( %ld, \"%s\" )\n", 499 opid == SLAP_INDEX_DELETE_OP ? "del" : "add", 500 (long) e->e_id, e->e_dn ); 501 502 /* add each attribute to the indexes */ 503 for ( ; ap != NULL; ap = ap->a_next ) { 504#if 0 /* ifdef LDAP_COMP_MATCH */ 505 AttrInfo *ai; 506 /* see if attribute has components to be indexed */ 507 ai = bdb_attr_mask( op->o_bd->be_private, ap->a_desc->ad_type->sat_ad ); 508 if ( !ai ) continue; 509 cr_list = ai->ai_cr; 510 if ( attr_converter && cr_list ) { 511 syn = ap->a_desc->ad_type->sat_syntax; 512 ap->a_comp_data = op->o_tmpalloc( sizeof( ComponentData ), op->o_tmpmemctx ); 513 /* Memory chunk(nibble) pre-allocation for decoders */ 514 mem_op = nibble_mem_allocator ( 1024*16, 1024*4 ); 515 ap->a_comp_data->cd_mem_op = mem_op; 516 for( cr = cr_list ; cr ; cr = cr->cr_next ) { 517 /* count how many values in an attribute */ 518 for( num_attr=0; ap->a_vals[num_attr].bv_val != NULL; num_attr++ ); 519 num_attr++; 520 cr->cr_nvals = (BerVarray)op->o_tmpalloc( sizeof( struct berval )*num_attr, op->o_tmpmemctx ); 521 for( i=0; ap->a_vals[i].bv_val != NULL; i++ ) { 522 /* decoding attribute value */ 523 decoded_comp = attr_converter ( ap, syn, &ap->a_vals[i] ); 524 if ( !decoded_comp ) 525 return LDAP_DECODING_ERROR; 526 /* extracting the referenced component */ 527 dupped_cr = dup_comp_ref( op, cr ); 528 csi_attr = ((ComponentSyntaxInfo*)decoded_comp)->csi_comp_desc->cd_extract_i( mem_op, dupped_cr, decoded_comp ); 529 if ( !csi_attr ) 530 return LDAP_DECODING_ERROR; 531 cr->cr_asn_type_id = csi_attr->csi_comp_desc->cd_type_id; 532 cr->cr_ad = (AttributeDescription*)get_component_description ( cr->cr_asn_type_id ); 533 if ( !cr->cr_ad ) 534 return LDAP_INVALID_SYNTAX; 535 at = cr->cr_ad->ad_type; 536 /* encoding the value of component in GSER */ 537 rc = component_encoder( mem_op, csi_attr, &value ); 538 if ( rc != LDAP_SUCCESS ) 539 return LDAP_ENCODING_ERROR; 540 /* Normalize the encoded component values */ 541 if ( at->sat_equality && at->sat_equality->smr_normalize ) { 542 rc = at->sat_equality->smr_normalize ( 543 SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX, 544 at->sat_syntax, at->sat_equality, 545 &value, &cr->cr_nvals[i], op->o_tmpmemctx ); 546 } else { 547 cr->cr_nvals[i] = value; 548 } 549 } 550 /* The end of BerVarray */ 551 cr->cr_nvals[num_attr-1].bv_val = NULL; 552 cr->cr_nvals[num_attr-1].bv_len = 0; 553 } 554 op->o_tmpfree( ap->a_comp_data, op->o_tmpmemctx ); 555 nibble_mem_free ( mem_op ); 556 ap->a_comp_data = NULL; 557 } 558#endif 559 rc = bdb_index_values( op, txn, ap->a_desc, 560 ap->a_nvals, e->e_id, opid ); 561 562 if( rc != LDAP_SUCCESS ) { 563 Debug( LDAP_DEBUG_TRACE, 564 "<= index_entry_%s( %ld, \"%s\" ) failure\n", 565 opid == SLAP_INDEX_ADD_OP ? "add" : "del", 566 (long) e->e_id, e->e_dn ); 567 return rc; 568 } 569 } 570 571 Debug( LDAP_DEBUG_TRACE, "<= index_entry_%s( %ld, \"%s\" ) success\n", 572 opid == SLAP_INDEX_DELETE_OP ? "del" : "add", 573 (long) e->e_id, e->e_dn ); 574 575 return LDAP_SUCCESS; 576} 577