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