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-bdb.h"
00026 #include "lutil_hash.h"
00027 
00028 static char presence_keyval[] = {0,0};
00029 static struct berval presence_key = BER_BVC(presence_keyval);
00030 
00031 AttrInfo *bdb_index_mask(
00032        Backend *be,
00033        AttributeDescription *desc,
00034        struct berval *atname )
00035 {
00036        AttributeType *at;
00037        AttrInfo *ai = bdb_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 = bdb_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 = bdb_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 bdb_index_param(
00076        Backend *be,
00077        AttributeDescription *desc,
00078        int ftype,
00079        DB **dbp,
00080        slap_mask_t *maskp,
00081        struct berval *prefixp )
00082 {
00083        AttrInfo *ai;
00084        int rc;
00085        slap_mask_t mask, type = 0;
00086        DB *db;
00087 
00088        ai = bdb_index_mask( be, desc, prefixp );
00089 
00090        if ( !ai ) {
00091 #ifdef BDB_MONITOR_IDX
00092               switch ( ftype ) {
00093               case LDAP_FILTER_PRESENT:
00094                      type = SLAP_INDEX_PRESENT;
00095                      break;
00096               case LDAP_FILTER_APPROX:
00097                      type = SLAP_INDEX_APPROX;
00098                      break;
00099               case LDAP_FILTER_EQUALITY:
00100                      type = SLAP_INDEX_EQUALITY;
00101                      break;
00102               case LDAP_FILTER_SUBSTRINGS:
00103                      type = SLAP_INDEX_SUBSTR;
00104                      break;
00105               default:
00106                      return LDAP_INAPPROPRIATE_MATCHING;
00107               }
00108               bdb_monitor_idx_add( be->be_private, desc, type );
00109 #endif /* BDB_MONITOR_IDX */
00110 
00111               return LDAP_INAPPROPRIATE_MATCHING;
00112        }
00113        mask = ai->ai_indexmask;
00114 
00115        rc = bdb_db_cache( be, prefixp, &db );
00116 
00117        if( rc != LDAP_SUCCESS ) {
00118               return rc;
00119        }
00120 
00121        switch( ftype ) {
00122        case LDAP_FILTER_PRESENT:
00123               type = SLAP_INDEX_PRESENT;
00124               if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) {
00125                      *prefixp = presence_key;
00126                      goto done;
00127               }
00128               break;
00129 
00130        case LDAP_FILTER_APPROX:
00131               type = SLAP_INDEX_APPROX;
00132               if ( desc->ad_type->sat_approx ) {
00133                      if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) {
00134                             goto done;
00135                      }
00136                      break;
00137               }
00138 
00139               /* Use EQUALITY rule and index for approximate match */
00140               /* fall thru */
00141 
00142        case LDAP_FILTER_EQUALITY:
00143               type = SLAP_INDEX_EQUALITY;
00144               if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) {
00145                      goto done;
00146               }
00147               break;
00148 
00149        case LDAP_FILTER_SUBSTRINGS:
00150               type = SLAP_INDEX_SUBSTR;
00151               if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) {
00152                      goto done;
00153               }
00154               break;
00155 
00156        default:
00157               return LDAP_OTHER;
00158        }
00159 
00160 #ifdef BDB_MONITOR_IDX
00161        bdb_monitor_idx_add( be->be_private, desc, type );
00162 #endif /* BDB_MONITOR_IDX */
00163 
00164        return LDAP_INAPPROPRIATE_MATCHING;
00165 
00166 done:
00167        *dbp = db;
00168        *maskp = mask;
00169        return LDAP_SUCCESS;
00170 }
00171 
00172 static int indexer(
00173        Operation *op,
00174        DB_TXN *txn,
00175        AttributeDescription *ad,
00176        struct berval *atname,
00177        BerVarray vals,
00178        ID id,
00179        int opid,
00180        slap_mask_t mask )
00181 {
00182        int rc, i;
00183        DB *db;
00184        struct berval *keys;
00185 
00186        assert( mask != 0 );
00187 
00188        rc = bdb_db_cache( op->o_bd, atname, &db );
00189        
00190        if ( rc != LDAP_SUCCESS ) {
00191               Debug( LDAP_DEBUG_ANY,
00192                      "bdb_index_read: Could not open DB %s\n",
00193                      atname->bv_val, 0, 0 );
00194               return LDAP_OTHER;
00195        }
00196 
00197        if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) {
00198               rc = bdb_key_change( op->o_bd, db, txn, &presence_key, id, opid );
00199               if( rc ) {
00200                      goto done;
00201               }
00202        }
00203 
00204        if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) {
00205               rc = ad->ad_type->sat_equality->smr_indexer(
00206                      LDAP_FILTER_EQUALITY,
00207                      mask,
00208                      ad->ad_type->sat_syntax,
00209                      ad->ad_type->sat_equality,
00210                      atname, vals, &keys, op->o_tmpmemctx );
00211 
00212               if( rc == LDAP_SUCCESS && keys != NULL ) {
00213                      for( i=0; keys[i].bv_val != NULL; i++ ) {
00214                             rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid );
00215                             if( rc ) {
00216                                    ber_bvarray_free_x( keys, op->o_tmpmemctx );
00217                                    goto done;
00218                             }
00219                      }
00220                      ber_bvarray_free_x( keys, op->o_tmpmemctx );
00221               }
00222               rc = LDAP_SUCCESS;
00223        }
00224 
00225        if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) {
00226               rc = ad->ad_type->sat_approx->smr_indexer(
00227                      LDAP_FILTER_APPROX,
00228                      mask,
00229                      ad->ad_type->sat_syntax,
00230                      ad->ad_type->sat_approx,
00231                      atname, vals, &keys, op->o_tmpmemctx );
00232 
00233               if( rc == LDAP_SUCCESS && keys != NULL ) {
00234                      for( i=0; keys[i].bv_val != NULL; i++ ) {
00235                             rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid );
00236                             if( rc ) {
00237                                    ber_bvarray_free_x( keys, op->o_tmpmemctx );
00238                                    goto done;
00239                             }
00240                      }
00241                      ber_bvarray_free_x( keys, op->o_tmpmemctx );
00242               }
00243 
00244               rc = LDAP_SUCCESS;
00245        }
00246 
00247        if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) {
00248               rc = ad->ad_type->sat_substr->smr_indexer(
00249                      LDAP_FILTER_SUBSTRINGS,
00250                      mask,
00251                      ad->ad_type->sat_syntax,
00252                      ad->ad_type->sat_substr,
00253                      atname, vals, &keys, op->o_tmpmemctx );
00254 
00255               if( rc == LDAP_SUCCESS && keys != NULL ) {
00256                      for( i=0; keys[i].bv_val != NULL; i++ ) {
00257                             rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid );
00258                             if( rc ) {
00259                                    ber_bvarray_free_x( keys, op->o_tmpmemctx );
00260                                    goto done;
00261                             }
00262                      }
00263                      ber_bvarray_free_x( keys, op->o_tmpmemctx );
00264               }
00265 
00266               rc = LDAP_SUCCESS;
00267        }
00268 
00269 done:
00270        switch( rc ) {
00271        /* The callers all know how to deal with these results */
00272        case 0:
00273        case DB_LOCK_DEADLOCK:
00274        case DB_LOCK_NOTGRANTED:
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        DB_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 == BDB_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 = bdb_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, 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 == BDB_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, 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 = bdb_attr_mask( op->o_bd->be_private, desc );
00351 
00352                      if( ai ) {
00353                             if ( opid == BDB_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, 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 bdb_index_values(
00373        Operation *op,
00374        DB_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 bdb_index_recset(
00396        struct bdb_info *bdb,
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 = bdb_index_recset( bdb, 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 = bdb_attr_slot( bdb, type->sat_ad, NULL );
00413               if ( slot >= 0 ) {
00414                      ir[slot].ai = bdb->bi_attrs[slot];
00415                      al = ch_malloc( sizeof( AttrList ));
00416                      al->attr = a;
00417                      al->next = ir[slot].attrs;
00418                      ir[slot].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 = bdb_attr_slot( bdb, desc, NULL );
00427                      if ( slot >= 0 ) {
00428                             ir[slot].ai = bdb->bi_attrs[slot];
00429                             al = ch_malloc( sizeof( AttrList ));
00430                             al->attr = a;
00431                             al->next = ir[slot].attrs;
00432                             ir[slot].attrs = al;
00433                      }
00434               }
00435        }
00436        return LDAP_SUCCESS;
00437 }
00438 
00439 /* Apply the indices for the recset */
00440 int bdb_index_recrun(
00441        Operation *op,
00442        struct bdb_info *bdb,
00443        IndexRec *ir0,
00444        ID id,
00445        int base )
00446 {
00447        IndexRec *ir;
00448        AttrList *al;
00449        int i, rc = 0;
00450 
00451        /* Never index ID 0 */
00452        if ( id == 0 )
00453               return 0;
00454 
00455        for (i=base; i<bdb->bi_nattrs; i+=slap_tool_thread_max-1) {
00456               ir = ir0 + i;
00457               if ( !ir->ai ) continue;
00458               while (( al = ir->attrs )) {
00459                      ir->attrs = al->next;
00460                      rc = indexer( op, NULL, ir->ai->ai_desc,
00461                             &ir->ai->ai_desc->ad_type->sat_cname,
00462                             al->attr->a_nvals, id, SLAP_INDEX_ADD_OP,
00463                             ir->ai->ai_indexmask );
00464                      free( al );
00465                      if ( rc ) break;
00466               }
00467        }
00468        return rc;
00469 }
00470 
00471 int
00472 bdb_index_entry(
00473        Operation *op,
00474        DB_TXN *txn,
00475        int opid,
00476        Entry  *e )
00477 {
00478        int rc;
00479        Attribute *ap = e->e_attrs;
00480 #if 0 /* ifdef LDAP_COMP_MATCH */
00481        ComponentReference *cr_list = NULL;
00482        ComponentReference *cr = NULL, *dupped_cr = NULL;
00483        void* decoded_comp;
00484        ComponentSyntaxInfo* csi_attr;
00485        Syntax* syn;
00486        AttributeType* at;
00487        int i, num_attr;
00488        void* mem_op;
00489        struct berval value = {0};
00490 #endif
00491 
00492        /* Never index ID 0 */
00493        if ( e->e_id == 0 )
00494               return 0;
00495 
00496        Debug( LDAP_DEBUG_TRACE, "=> index_entry_%s( %ld, \"%s\" )\n",
00497               opid == SLAP_INDEX_DELETE_OP ? "del" : "add",
00498               (long) e->e_id, e->e_dn );
00499 
00500        /* add each attribute to the indexes */
00501        for ( ; ap != NULL; ap = ap->a_next ) {
00502 #if 0 /* ifdef LDAP_COMP_MATCH */
00503               AttrInfo *ai;
00504               /* see if attribute has components to be indexed */
00505               ai = bdb_attr_mask( op->o_bd->be_private, ap->a_desc->ad_type->sat_ad );
00506               if ( !ai ) continue;
00507               cr_list = ai->ai_cr;
00508               if ( attr_converter && cr_list ) {
00509                      syn = ap->a_desc->ad_type->sat_syntax;
00510                      ap->a_comp_data = op->o_tmpalloc( sizeof( ComponentData ), op->o_tmpmemctx );
00511                      /* Memory chunk(nibble) pre-allocation for decoders */
00512                      mem_op = nibble_mem_allocator ( 1024*16, 1024*4 );
00513                      ap->a_comp_data->cd_mem_op = mem_op;
00514                      for( cr = cr_list ; cr ; cr = cr->cr_next ) {
00515                             /* count how many values in an attribute */
00516                             for( num_attr=0; ap->a_vals[num_attr].bv_val != NULL; num_attr++ );
00517                             num_attr++;
00518                             cr->cr_nvals = (BerVarray)op->o_tmpalloc( sizeof( struct berval )*num_attr, op->o_tmpmemctx );
00519                             for( i=0; ap->a_vals[i].bv_val != NULL; i++ ) {
00520                                    /* decoding attribute value */
00521                                    decoded_comp = attr_converter ( ap, syn, &ap->a_vals[i] );
00522                                    if ( !decoded_comp )
00523                                           return LDAP_DECODING_ERROR;
00524                                    /* extracting the referenced component */
00525                                    dupped_cr = dup_comp_ref( op, cr );
00526                                    csi_attr = ((ComponentSyntaxInfo*)decoded_comp)->csi_comp_desc->cd_extract_i( mem_op, dupped_cr, decoded_comp );
00527                                    if ( !csi_attr )
00528                                           return LDAP_DECODING_ERROR;
00529                                    cr->cr_asn_type_id = csi_attr->csi_comp_desc->cd_type_id;
00530                                    cr->cr_ad = (AttributeDescription*)get_component_description ( cr->cr_asn_type_id );
00531                                    if ( !cr->cr_ad )
00532                                           return LDAP_INVALID_SYNTAX;
00533                                    at = cr->cr_ad->ad_type;
00534                                    /* encoding the value of component in GSER */
00535                                    rc = component_encoder( mem_op, csi_attr, &value );
00536                                    if ( rc != LDAP_SUCCESS )
00537                                           return LDAP_ENCODING_ERROR;
00538                                    /* Normalize the encoded component values */
00539                                    if ( at->sat_equality && at->sat_equality->smr_normalize ) {
00540                                           rc = at->sat_equality->smr_normalize (
00541                                                  SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX,
00542                                                  at->sat_syntax, at->sat_equality,
00543                                                  &value, &cr->cr_nvals[i], op->o_tmpmemctx );
00544                                    } else {
00545                                           cr->cr_nvals[i] = value;
00546                                    }
00547                             }
00548                             /* The end of BerVarray */
00549                             cr->cr_nvals[num_attr-1].bv_val = NULL;
00550                             cr->cr_nvals[num_attr-1].bv_len = 0;
00551                      }
00552                      op->o_tmpfree( ap->a_comp_data, op->o_tmpmemctx );
00553                      nibble_mem_free ( mem_op );
00554                      ap->a_comp_data = NULL;
00555               }
00556 #endif
00557               rc = bdb_index_values( op, txn, ap->a_desc,
00558                      ap->a_nvals, e->e_id, opid );
00559 
00560               if( rc != LDAP_SUCCESS ) {
00561                      Debug( LDAP_DEBUG_TRACE,
00562                             "<= index_entry_%s( %ld, \"%s\" ) failure\n",
00563                             opid == SLAP_INDEX_ADD_OP ? "add" : "del",
00564                             (long) e->e_id, e->e_dn );
00565                      return rc;
00566               }
00567        }
00568 
00569        Debug( LDAP_DEBUG_TRACE, "<= index_entry_%s( %ld, \"%s\" ) success\n",
00570               opid == SLAP_INDEX_DELETE_OP ? "del" : "add",
00571               (long) e->e_id, e->e_dn );
00572 
00573        return LDAP_SUCCESS;
00574 }