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