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
33static char presence_keyval[] = {0,0,0,0,0};
34static struct berval presence_key[2] = {BER_BVC(presence_keyval), BER_BVNULL};
35
36AttrInfo *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 */
80int 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
163done:
164	*dbip = ai->ai_dbi;
165	*maskp = mask;
166	return LDAP_SUCCESS;
167}
168
169static 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
276done:
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
290static 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
379int 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 */
401int
402mdb_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 */
447int 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
479int
480mdb_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