Back to index

openldap  2.4.31
index.c
Go to the documentation of this file.
00001 /* index.c - routines for dealing with attribute indexes */
00002 /* $OpenLDAP$ */
00003 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
00004  *
00005  * Copyright 2000-2012 The OpenLDAP Foundation.
00006  * All rights reserved.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted only as authorized by the OpenLDAP
00010  * Public License.
00011  *
00012  * A copy of this license is available in the file LICENSE in the
00013  * top-level directory of the distribution or, alternatively, at
00014  * <http://www.OpenLDAP.org/license.html>.
00015  */
00016 
00017 #include "portable.h"
00018 
00019 #include <stdio.h>
00020 
00021 #include <ac/string.h>
00022 #include <ac/socket.h>
00023 
00024 #include "slap.h"
00025 #include "back-mdb.h"
00026 #include "lutil_hash.h"
00027 
00028 static char presence_keyval[] = {0,0,0,0,0};
00029 static struct berval presence_key[2] = {BER_BVC(presence_keyval), BER_BVNULL};
00030 
00031 AttrInfo *mdb_index_mask(
00032        Backend *be,
00033        AttributeDescription *desc,
00034        struct berval *atname )
00035 {
00036        AttributeType *at;
00037        AttrInfo *ai = mdb_attr_mask( be->be_private, desc );
00038 
00039        if( ai ) {
00040               *atname = desc->ad_cname;
00041               return ai;
00042        }
00043 
00044        /* If there is a tagging option, did we ever index the base
00045         * type? If so, check for mask, otherwise it's not there.
00046         */
00047        if( slap_ad_is_tagged( desc ) && desc != desc->ad_type->sat_ad ) {
00048               /* has tagging option */
00049               ai = mdb_attr_mask( be->be_private, desc->ad_type->sat_ad );
00050 
00051               if ( ai && !( ai->ai_indexmask & SLAP_INDEX_NOTAGS ) ) {
00052                      *atname = desc->ad_type->sat_cname;
00053                      return ai;
00054               }
00055        }
00056 
00057        /* see if supertype defined mask for its subtypes */
00058        for( at = desc->ad_type; at != NULL ; at = at->sat_sup ) {
00059               /* If no AD, we've never indexed this type */
00060               if ( !at->sat_ad ) continue;
00061 
00062               ai = mdb_attr_mask( be->be_private, at->sat_ad );
00063 
00064               if ( ai && !( ai->ai_indexmask & SLAP_INDEX_NOSUBTYPES ) ) {
00065                      *atname = at->sat_cname;
00066                      return ai;
00067               }
00068        }
00069 
00070        return 0;
00071 }
00072 
00073 /* This function is only called when evaluating search filters.
00074  */
00075 int mdb_index_param(
00076        Backend *be,
00077        AttributeDescription *desc,
00078        int ftype,
00079        MDB_dbi *dbip,
00080        slap_mask_t *maskp,
00081        struct berval *prefixp )
00082 {
00083        AttrInfo *ai;
00084        slap_mask_t mask, type = 0;
00085 
00086        ai = mdb_index_mask( be, desc, prefixp );
00087 
00088        if ( !ai ) {
00089 #ifdef MDB_MONITOR_IDX
00090               switch ( ftype ) {
00091               case LDAP_FILTER_PRESENT:
00092                      type = SLAP_INDEX_PRESENT;
00093                      break;
00094               case LDAP_FILTER_APPROX:
00095                      type = SLAP_INDEX_APPROX;
00096                      break;
00097               case LDAP_FILTER_EQUALITY:
00098                      type = SLAP_INDEX_EQUALITY;
00099                      break;
00100               case LDAP_FILTER_SUBSTRINGS:
00101                      type = SLAP_INDEX_SUBSTR;
00102                      break;
00103               default:
00104                      return LDAP_INAPPROPRIATE_MATCHING;
00105               }
00106               mdb_monitor_idx_add( be->be_private, desc, type );
00107 #endif /* MDB_MONITOR_IDX */
00108 
00109               return LDAP_INAPPROPRIATE_MATCHING;
00110        }
00111        mask = ai->ai_indexmask;
00112 
00113        switch( ftype ) {
00114        case LDAP_FILTER_PRESENT:
00115               type = SLAP_INDEX_PRESENT;
00116               if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) {
00117                      *prefixp = presence_key[0];
00118                      goto done;
00119               }
00120               break;
00121 
00122        case LDAP_FILTER_APPROX:
00123               type = SLAP_INDEX_APPROX;
00124               if ( desc->ad_type->sat_approx ) {
00125                      if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) {
00126                             goto done;
00127                      }
00128                      break;
00129               }
00130 
00131               /* Use EQUALITY rule and index for approximate match */
00132               /* fall thru */
00133 
00134        case LDAP_FILTER_EQUALITY:
00135               type = SLAP_INDEX_EQUALITY;
00136               if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) {
00137                      goto done;
00138               }
00139               break;
00140 
00141        case LDAP_FILTER_SUBSTRINGS:
00142               type = SLAP_INDEX_SUBSTR;
00143               if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) {
00144                      goto done;
00145               }
00146               break;
00147 
00148        default:
00149               return LDAP_OTHER;
00150        }
00151 
00152 #ifdef MDB_MONITOR_IDX
00153        mdb_monitor_idx_add( be->be_private, desc, type );
00154 #endif /* MDB_MONITOR_IDX */
00155 
00156        return LDAP_INAPPROPRIATE_MATCHING;
00157 
00158 done:
00159        *dbip = ai->ai_dbi;
00160        *maskp = mask;
00161        return LDAP_SUCCESS;
00162 }
00163 
00164 static int indexer(
00165        Operation *op,
00166        MDB_txn *txn,
00167        struct mdb_attrinfo *ai,
00168        AttributeDescription *ad,
00169        struct berval *atname,
00170        BerVarray vals,
00171        ID id,
00172        int opid,
00173        slap_mask_t mask )
00174 {
00175        int rc, i;
00176        struct berval *keys;
00177        MDB_cursor *mc = ai->ai_cursor;
00178        mdb_idl_keyfunc *keyfunc;
00179        char *err;
00180 
00181        assert( mask != 0 );
00182 
00183        if ( !mc ) {
00184               err = "c_open";
00185               rc = mdb_cursor_open( txn, ai->ai_dbi, &mc );
00186               if ( rc ) goto done;
00187               if ( slapMode & SLAP_TOOL_QUICK )
00188                      ai->ai_cursor = mc;
00189        }
00190 
00191        if ( opid == SLAP_INDEX_ADD_OP ) {
00192 #ifdef MDB_TOOL_IDL_CACHING
00193               if (( slapMode & SLAP_TOOL_QUICK ) && slap_tool_thread_max > 2 ) {
00194                      keyfunc = mdb_tool_idl_add;
00195                      mc = (MDB_cursor *)ai;
00196               } else
00197 #endif
00198                      keyfunc = mdb_idl_insert_keys;
00199        } else
00200               keyfunc = mdb_idl_delete_keys;
00201 
00202        if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) {
00203               rc = keyfunc( mc, presence_key, id );
00204               if( rc ) {
00205                      err = "presence";
00206                      goto done;
00207               }
00208        }
00209 
00210        if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) {
00211               rc = ad->ad_type->sat_equality->smr_indexer(
00212                      LDAP_FILTER_EQUALITY,
00213                      mask,
00214                      ad->ad_type->sat_syntax,
00215                      ad->ad_type->sat_equality,
00216                      atname, vals, &keys, op->o_tmpmemctx );
00217 
00218               if( rc == LDAP_SUCCESS && keys != NULL ) {
00219                      rc = keyfunc( mc, keys, id );
00220                      ber_bvarray_free_x( keys, op->o_tmpmemctx );
00221                      if ( rc ) {
00222                             err = "equality";
00223                             goto done;
00224                      }
00225               }
00226               rc = LDAP_SUCCESS;
00227        }
00228 
00229        if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) {
00230               rc = ad->ad_type->sat_approx->smr_indexer(
00231                      LDAP_FILTER_APPROX,
00232                      mask,
00233                      ad->ad_type->sat_syntax,
00234                      ad->ad_type->sat_approx,
00235                      atname, vals, &keys, op->o_tmpmemctx );
00236 
00237               if( rc == LDAP_SUCCESS && keys != NULL ) {
00238                      rc = keyfunc( mc, keys, id );
00239                      ber_bvarray_free_x( keys, op->o_tmpmemctx );
00240                      if ( rc ) {
00241                             err = "approx";
00242                             goto done;
00243                      }
00244               }
00245 
00246               rc = LDAP_SUCCESS;
00247        }
00248 
00249        if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) {
00250               rc = ad->ad_type->sat_substr->smr_indexer(
00251                      LDAP_FILTER_SUBSTRINGS,
00252                      mask,
00253                      ad->ad_type->sat_syntax,
00254                      ad->ad_type->sat_substr,
00255                      atname, vals, &keys, op->o_tmpmemctx );
00256 
00257               if( rc == LDAP_SUCCESS && keys != NULL ) {
00258                      rc = keyfunc( mc, keys, id );
00259                      ber_bvarray_free_x( keys, op->o_tmpmemctx );
00260                      if( rc ) {
00261                             err = "substr";
00262                             goto done;
00263                      }
00264               }
00265 
00266               rc = LDAP_SUCCESS;
00267        }
00268 
00269 done:
00270        if ( !(slapMode & SLAP_TOOL_QUICK))
00271               mdb_cursor_close( mc );
00272        switch( rc ) {
00273        /* The callers all know how to deal with these results */
00274        case 0:
00275               break;
00276        /* Anything else is bad news */
00277        default:
00278               rc = LDAP_OTHER;
00279        }
00280        return rc;
00281 }
00282 
00283 static int index_at_values(
00284        Operation *op,
00285        MDB_txn *txn,
00286        AttributeDescription *ad,
00287        AttributeType *type,
00288        struct berval *tags,
00289        BerVarray vals,
00290        ID id,
00291        int opid )
00292 {
00293        int rc;
00294        slap_mask_t mask = 0;
00295        int ixop = opid;
00296        AttrInfo *ai = NULL;
00297 
00298        if ( opid == MDB_INDEX_UPDATE_OP )
00299               ixop = SLAP_INDEX_ADD_OP;
00300 
00301        if( type->sat_sup ) {
00302               /* recurse */
00303               rc = index_at_values( op, txn, NULL,
00304                      type->sat_sup, tags,
00305                      vals, id, opid );
00306 
00307               if( rc ) return rc;
00308        }
00309 
00310        /* If this type has no AD, we've never used it before */
00311        if( type->sat_ad ) {
00312               ai = mdb_attr_mask( op->o_bd->be_private, type->sat_ad );
00313               if ( ai ) {
00314 #ifdef LDAP_COMP_MATCH
00315                      /* component indexing */
00316                      if ( ai->ai_cr ) {
00317                             ComponentReference *cr;
00318                             for( cr = ai->ai_cr ; cr ; cr = cr->cr_next ) {
00319                                    rc = indexer( op, txn, ai, cr->cr_ad, &type->sat_cname,
00320                                           cr->cr_nvals, id, ixop,
00321                                           cr->cr_indexmask );
00322                             }
00323                      }
00324 #endif
00325                      ad = type->sat_ad;
00326                      /* If we're updating the index, just set the new bits that aren't
00327                       * already in the old mask.
00328                       */
00329                      if ( opid == MDB_INDEX_UPDATE_OP )
00330                             mask = ai->ai_newmask & ~ai->ai_indexmask;
00331                      else
00332                      /* For regular updates, if there is a newmask use it. Otherwise
00333                       * just use the old mask.
00334                       */
00335                             mask = ai->ai_newmask ? ai->ai_newmask : ai->ai_indexmask;
00336                      if( mask ) {
00337                             rc = indexer( op, txn, ai, ad, &type->sat_cname,
00338                                    vals, id, ixop, mask );
00339 
00340                             if( rc ) return rc;
00341                      }
00342               }
00343        }
00344 
00345        if( tags->bv_len ) {
00346               AttributeDescription *desc;
00347 
00348               desc = ad_find_tags( type, tags );
00349               if( desc ) {
00350                      ai = mdb_attr_mask( op->o_bd->be_private, desc );
00351 
00352                      if( ai ) {
00353                             if ( opid == MDB_INDEX_UPDATE_OP )
00354                                    mask = ai->ai_newmask & ~ai->ai_indexmask;
00355                             else
00356                                    mask = ai->ai_newmask ? ai->ai_newmask : ai->ai_indexmask;
00357                             if ( mask ) {
00358                                    rc = indexer( op, txn, ai, desc, &desc->ad_cname,
00359                                           vals, id, ixop, mask );
00360 
00361                                    if( rc ) {
00362                                           return rc;
00363                                    }
00364                             }
00365                      }
00366               }
00367        }
00368 
00369        return LDAP_SUCCESS;
00370 }
00371 
00372 int mdb_index_values(
00373        Operation *op,
00374        MDB_txn *txn,
00375        AttributeDescription *desc,
00376        BerVarray vals,
00377        ID id,
00378        int opid )
00379 {
00380        int rc;
00381 
00382        /* Never index ID 0 */
00383        if ( id == 0 )
00384               return 0;
00385 
00386        rc = index_at_values( op, txn, desc,
00387               desc->ad_type, &desc->ad_tags,
00388               vals, id, opid );
00389 
00390        return rc;
00391 }
00392 
00393 /* Get the list of which indices apply to this attr */
00394 int
00395 mdb_index_recset(
00396        struct mdb_info *mdb,
00397        Attribute *a,
00398        AttributeType *type,
00399        struct berval *tags,
00400        IndexRec *ir )
00401 {
00402        int rc, slot;
00403        AttrList *al;
00404 
00405        if( type->sat_sup ) {
00406               /* recurse */
00407               rc = mdb_index_recset( mdb, a, type->sat_sup, tags, ir );
00408               if( rc ) return rc;
00409        }
00410        /* If this type has no AD, we've never used it before */
00411        if( type->sat_ad ) {
00412               slot = mdb_attr_slot( mdb, type->sat_ad, NULL );
00413               if ( slot >= 0 ) {
00414                      ir[slot].ir_ai = mdb->mi_attrs[slot];
00415                      al = ch_malloc( sizeof( AttrList ));
00416                      al->attr = a;
00417                      al->next = ir[slot].ir_attrs;
00418                      ir[slot].ir_attrs = al;
00419               }
00420        }
00421        if( tags->bv_len ) {
00422               AttributeDescription *desc;
00423 
00424               desc = ad_find_tags( type, tags );
00425               if( desc ) {
00426                      slot = mdb_attr_slot( mdb, desc, NULL );
00427                      if ( slot >= 0 ) {
00428                             ir[slot].ir_ai = mdb->mi_attrs[slot];
00429                             al = ch_malloc( sizeof( AttrList ));
00430                             al->attr = a;
00431                             al->next = ir[slot].ir_attrs;
00432                             ir[slot].ir_attrs = al;
00433                      }
00434               }
00435        }
00436        return LDAP_SUCCESS;
00437 }
00438 
00439 /* Apply the indices for the recset */
00440 int mdb_index_recrun(
00441        Operation *op,
00442        MDB_txn *txn,
00443        struct mdb_info *mdb,
00444        IndexRec *ir0,
00445        ID id,
00446        int base )
00447 {
00448        IndexRec *ir;
00449        AttrList *al;
00450        int i, rc = 0;
00451 
00452        /* Never index ID 0 */
00453        if ( id == 0 )
00454               return 0;
00455 
00456        for (i=base; i<mdb->mi_nattrs; i+=slap_tool_thread_max-1) {
00457               ir = ir0 + i;
00458               if ( !ir->ir_ai ) continue;
00459               while (( al = ir->ir_attrs )) {
00460                      ir->ir_attrs = al->next;
00461                      rc = indexer( op, txn, ir->ir_ai, ir->ir_ai->ai_desc,
00462                             &ir->ir_ai->ai_desc->ad_type->sat_cname,
00463                             al->attr->a_nvals, id, SLAP_INDEX_ADD_OP,
00464                             ir->ir_ai->ai_indexmask );
00465                      free( al );
00466                      if ( rc ) break;
00467               }
00468        }
00469        return rc;
00470 }
00471 
00472 int
00473 mdb_index_entry(
00474        Operation *op,
00475        MDB_txn *txn,
00476        int opid,
00477        Entry  *e )
00478 {
00479        int rc;
00480        Attribute *ap = e->e_attrs;
00481 #if 0 /* ifdef LDAP_COMP_MATCH */
00482        ComponentReference *cr_list = NULL;
00483        ComponentReference *cr = NULL, *dupped_cr = NULL;
00484        void* decoded_comp;
00485        ComponentSyntaxInfo* csi_attr;
00486        Syntax* syn;
00487        AttributeType* at;
00488        int i, num_attr;
00489        void* mem_op;
00490        struct berval value = {0};
00491 #endif
00492 
00493        /* Never index ID 0 */
00494        if ( e->e_id == 0 )
00495               return 0;
00496 
00497        Debug( LDAP_DEBUG_TRACE, "=> index_entry_%s( %ld, \"%s\" )\n",
00498               opid == SLAP_INDEX_DELETE_OP ? "del" : "add",
00499               (long) e->e_id, e->e_dn ? e->e_dn : "" );
00500 
00501        /* add each attribute to the indexes */
00502        for ( ; ap != NULL; ap = ap->a_next ) {
00503 #if 0 /* ifdef LDAP_COMP_MATCH */
00504               AttrInfo *ai;
00505               /* see if attribute has components to be indexed */
00506               ai = mdb_attr_mask( op->o_bd->be_private, ap->a_desc->ad_type->sat_ad );
00507               if ( !ai ) continue;
00508               cr_list = ai->ai_cr;
00509               if ( attr_converter && cr_list ) {
00510                      syn = ap->a_desc->ad_type->sat_syntax;
00511                      ap->a_comp_data = op->o_tmpalloc( sizeof( ComponentData ), op->o_tmpmemctx );
00512                      /* Memory chunk(nibble) pre-allocation for decoders */
00513                      mem_op = nibble_mem_allocator ( 1024*16, 1024*4 );
00514                      ap->a_comp_data->cd_mem_op = mem_op;
00515                      for( cr = cr_list ; cr ; cr = cr->cr_next ) {
00516                             /* count how many values in an attribute */
00517                             for( num_attr=0; ap->a_vals[num_attr].bv_val != NULL; num_attr++ );
00518                             num_attr++;
00519                             cr->cr_nvals = (BerVarray)op->o_tmpalloc( sizeof( struct berval )*num_attr, op->o_tmpmemctx );
00520                             for( i=0; ap->a_vals[i].bv_val != NULL; i++ ) {
00521                                    /* decoding attribute value */
00522                                    decoded_comp = attr_converter ( ap, syn, &ap->a_vals[i] );
00523                                    if ( !decoded_comp )
00524                                           return LDAP_DECODING_ERROR;
00525                                    /* extracting the referenced component */
00526                                    dupped_cr = dup_comp_ref( op, cr );
00527                                    csi_attr = ((ComponentSyntaxInfo*)decoded_comp)->csi_comp_desc->cd_extract_i( mem_op, dupped_cr, decoded_comp );
00528                                    if ( !csi_attr )
00529                                           return LDAP_DECODING_ERROR;
00530                                    cr->cr_asn_type_id = csi_attr->csi_comp_desc->cd_type_id;
00531                                    cr->cr_ad = (AttributeDescription*)get_component_description ( cr->cr_asn_type_id );
00532                                    if ( !cr->cr_ad )
00533                                           return LDAP_INVALID_SYNTAX;
00534                                    at = cr->cr_ad->ad_type;
00535                                    /* encoding the value of component in GSER */
00536                                    rc = component_encoder( mem_op, csi_attr, &value );
00537                                    if ( rc != LDAP_SUCCESS )
00538                                           return LDAP_ENCODING_ERROR;
00539                                    /* Normalize the encoded component values */
00540                                    if ( at->sat_equality && at->sat_equality->smr_normalize ) {
00541                                           rc = at->sat_equality->smr_normalize (
00542                                                  SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX,
00543                                                  at->sat_syntax, at->sat_equality,
00544                                                  &value, &cr->cr_nvals[i], op->o_tmpmemctx );
00545                                    } else {
00546                                           cr->cr_nvals[i] = value;
00547                                    }
00548                             }
00549                             /* The end of BerVarray */
00550                             cr->cr_nvals[num_attr-1].bv_val = NULL;
00551                             cr->cr_nvals[num_attr-1].bv_len = 0;
00552                      }
00553                      op->o_tmpfree( ap->a_comp_data, op->o_tmpmemctx );
00554                      nibble_mem_free ( mem_op );
00555                      ap->a_comp_data = NULL;
00556               }
00557 #endif
00558               rc = mdb_index_values( op, txn, ap->a_desc,
00559                      ap->a_nvals, e->e_id, opid );
00560 
00561               if( rc != LDAP_SUCCESS ) {
00562                      Debug( LDAP_DEBUG_TRACE,
00563                             "<= index_entry_%s( %ld, \"%s\" ) failure\n",
00564                             opid == SLAP_INDEX_ADD_OP ? "add" : "del",
00565                             (long) e->e_id, e->e_dn );
00566                      return rc;
00567               }
00568        }
00569 
00570        Debug( LDAP_DEBUG_TRACE, "<= index_entry_%s( %ld, \"%s\" ) success\n",
00571               opid == SLAP_INDEX_DELETE_OP ? "del" : "add",
00572               (long) e->e_id, e->e_dn ? e->e_dn : "" );
00573 
00574        return LDAP_SUCCESS;
00575 }