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