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