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-bdb.h"
26#include "lutil_hash.h"
27
28static char presence_keyval[] = {0,0};
29static struct berval presence_key = BER_BVC(presence_keyval);
30
31AttrInfo *bdb_index_mask(
32	Backend *be,
33	AttributeDescription *desc,
34	struct berval *atname )
35{
36	AttributeType *at;
37	AttrInfo *ai = bdb_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 = bdb_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 = bdb_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 */
75int bdb_index_param(
76	Backend *be,
77	AttributeDescription *desc,
78	int ftype,
79	DB **dbp,
80	slap_mask_t *maskp,
81	struct berval *prefixp )
82{
83	AttrInfo *ai;
84	int rc;
85	slap_mask_t mask, type = 0;
86	DB *db;
87
88	ai = bdb_index_mask( be, desc, prefixp );
89
90	if ( !ai ) {
91#ifdef BDB_MONITOR_IDX
92		switch ( ftype ) {
93		case LDAP_FILTER_PRESENT:
94			type = SLAP_INDEX_PRESENT;
95			break;
96		case LDAP_FILTER_APPROX:
97			type = SLAP_INDEX_APPROX;
98			break;
99		case LDAP_FILTER_EQUALITY:
100			type = SLAP_INDEX_EQUALITY;
101			break;
102		case LDAP_FILTER_SUBSTRINGS:
103			type = SLAP_INDEX_SUBSTR;
104			break;
105		default:
106			return LDAP_INAPPROPRIATE_MATCHING;
107		}
108		bdb_monitor_idx_add( be->be_private, desc, type );
109#endif /* BDB_MONITOR_IDX */
110
111		return LDAP_INAPPROPRIATE_MATCHING;
112	}
113	mask = ai->ai_indexmask;
114
115	rc = bdb_db_cache( be, prefixp, &db );
116
117	if( rc != LDAP_SUCCESS ) {
118		return rc;
119	}
120
121	switch( ftype ) {
122	case LDAP_FILTER_PRESENT:
123		type = SLAP_INDEX_PRESENT;
124		if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) {
125			*prefixp = presence_key;
126			goto done;
127		}
128		break;
129
130	case LDAP_FILTER_APPROX:
131		type = SLAP_INDEX_APPROX;
132		if ( desc->ad_type->sat_approx ) {
133			if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) {
134				goto done;
135			}
136			break;
137		}
138
139		/* Use EQUALITY rule and index for approximate match */
140		/* fall thru */
141
142	case LDAP_FILTER_EQUALITY:
143		type = SLAP_INDEX_EQUALITY;
144		if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) {
145			goto done;
146		}
147		break;
148
149	case LDAP_FILTER_SUBSTRINGS:
150		type = SLAP_INDEX_SUBSTR;
151		if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) {
152			goto done;
153		}
154		break;
155
156	default:
157		return LDAP_OTHER;
158	}
159
160#ifdef BDB_MONITOR_IDX
161	bdb_monitor_idx_add( be->be_private, desc, type );
162#endif /* BDB_MONITOR_IDX */
163
164	return LDAP_INAPPROPRIATE_MATCHING;
165
166done:
167	*dbp = db;
168	*maskp = mask;
169	return LDAP_SUCCESS;
170}
171
172static int indexer(
173	Operation *op,
174	DB_TXN *txn,
175	AttributeDescription *ad,
176	struct berval *atname,
177	BerVarray vals,
178	ID id,
179	int opid,
180	slap_mask_t mask )
181{
182	int rc, i;
183	DB *db;
184	struct berval *keys;
185
186	assert( mask != 0 );
187
188	rc = bdb_db_cache( op->o_bd, atname, &db );
189
190	if ( rc != LDAP_SUCCESS ) {
191		Debug( LDAP_DEBUG_ANY,
192			"bdb_index_read: Could not open DB %s\n",
193			atname->bv_val, 0, 0 );
194		return LDAP_OTHER;
195	}
196
197	if( IS_SLAP_INDEX( mask, SLAP_INDEX_PRESENT ) ) {
198		rc = bdb_key_change( op->o_bd, db, txn, &presence_key, id, opid );
199		if( rc ) {
200			goto done;
201		}
202	}
203
204	if( IS_SLAP_INDEX( mask, SLAP_INDEX_EQUALITY ) ) {
205		rc = ad->ad_type->sat_equality->smr_indexer(
206			LDAP_FILTER_EQUALITY,
207			mask,
208			ad->ad_type->sat_syntax,
209			ad->ad_type->sat_equality,
210			atname, vals, &keys, op->o_tmpmemctx );
211
212		if( rc == LDAP_SUCCESS && keys != NULL ) {
213			for( i=0; keys[i].bv_val != NULL; i++ ) {
214				rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid );
215				if( rc ) {
216					ber_bvarray_free_x( keys, op->o_tmpmemctx );
217					goto done;
218				}
219			}
220			ber_bvarray_free_x( keys, op->o_tmpmemctx );
221		}
222		rc = LDAP_SUCCESS;
223	}
224
225	if( IS_SLAP_INDEX( mask, SLAP_INDEX_APPROX ) ) {
226		rc = ad->ad_type->sat_approx->smr_indexer(
227			LDAP_FILTER_APPROX,
228			mask,
229			ad->ad_type->sat_syntax,
230			ad->ad_type->sat_approx,
231			atname, vals, &keys, op->o_tmpmemctx );
232
233		if( rc == LDAP_SUCCESS && keys != NULL ) {
234			for( i=0; keys[i].bv_val != NULL; i++ ) {
235				rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid );
236				if( rc ) {
237					ber_bvarray_free_x( keys, op->o_tmpmemctx );
238					goto done;
239				}
240			}
241			ber_bvarray_free_x( keys, op->o_tmpmemctx );
242		}
243
244		rc = LDAP_SUCCESS;
245	}
246
247	if( IS_SLAP_INDEX( mask, SLAP_INDEX_SUBSTR ) ) {
248		rc = ad->ad_type->sat_substr->smr_indexer(
249			LDAP_FILTER_SUBSTRINGS,
250			mask,
251			ad->ad_type->sat_syntax,
252			ad->ad_type->sat_substr,
253			atname, vals, &keys, op->o_tmpmemctx );
254
255		if( rc == LDAP_SUCCESS && keys != NULL ) {
256			for( i=0; keys[i].bv_val != NULL; i++ ) {
257				rc = bdb_key_change( op->o_bd, db, txn, &keys[i], id, opid );
258				if( rc ) {
259					ber_bvarray_free_x( keys, op->o_tmpmemctx );
260					goto done;
261				}
262			}
263			ber_bvarray_free_x( keys, op->o_tmpmemctx );
264		}
265
266		rc = LDAP_SUCCESS;
267	}
268
269done:
270	switch( rc ) {
271	/* The callers all know how to deal with these results */
272	case 0:
273	case DB_LOCK_DEADLOCK:
274	case DB_LOCK_NOTGRANTED:
275		break;
276	/* Anything else is bad news */
277	default:
278		rc = LDAP_OTHER;
279	}
280	return rc;
281}
282
283static int index_at_values(
284	Operation *op,
285	DB_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 == BDB_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 = bdb_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, 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 == BDB_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, 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 = bdb_attr_mask( op->o_bd->be_private, desc );
351
352			if( ai ) {
353				if ( opid == BDB_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, 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
372int bdb_index_values(
373	Operation *op,
374	DB_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 */
394int
395bdb_index_recset(
396	struct bdb_info *bdb,
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 = bdb_index_recset( bdb, 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 = bdb_attr_slot( bdb, type->sat_ad, NULL );
413		if ( slot >= 0 ) {
414			ir[slot].ai = bdb->bi_attrs[slot];
415			al = ch_malloc( sizeof( AttrList ));
416			al->attr = a;
417			al->next = ir[slot].attrs;
418			ir[slot].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 = bdb_attr_slot( bdb, desc, NULL );
427			if ( slot >= 0 ) {
428				ir[slot].ai = bdb->bi_attrs[slot];
429				al = ch_malloc( sizeof( AttrList ));
430				al->attr = a;
431				al->next = ir[slot].attrs;
432				ir[slot].attrs = al;
433			}
434		}
435	}
436	return LDAP_SUCCESS;
437}
438
439/* Apply the indices for the recset */
440int bdb_index_recrun(
441	Operation *op,
442	struct bdb_info *bdb,
443	IndexRec *ir0,
444	ID id,
445	int base )
446{
447	IndexRec *ir;
448	AttrList *al;
449	int i, rc = 0;
450
451	/* Never index ID 0 */
452	if ( id == 0 )
453		return 0;
454
455	for (i=base; i<bdb->bi_nattrs; i+=slap_tool_thread_max-1) {
456		ir = ir0 + i;
457		if ( !ir->ai ) continue;
458		while (( al = ir->attrs )) {
459			ir->attrs = al->next;
460			rc = indexer( op, NULL, ir->ai->ai_desc,
461				&ir->ai->ai_desc->ad_type->sat_cname,
462				al->attr->a_nvals, id, SLAP_INDEX_ADD_OP,
463				ir->ai->ai_indexmask );
464			free( al );
465			if ( rc ) break;
466		}
467	}
468	return rc;
469}
470
471int
472bdb_index_entry(
473	Operation *op,
474	DB_TXN *txn,
475	int opid,
476	Entry	*e )
477{
478	int rc;
479	Attribute *ap = e->e_attrs;
480#if 0 /* ifdef LDAP_COMP_MATCH */
481	ComponentReference *cr_list = NULL;
482	ComponentReference *cr = NULL, *dupped_cr = NULL;
483	void* decoded_comp;
484	ComponentSyntaxInfo* csi_attr;
485	Syntax* syn;
486	AttributeType* at;
487	int i, num_attr;
488	void* mem_op;
489	struct berval value = {0};
490#endif
491
492	/* Never index ID 0 */
493	if ( e->e_id == 0 )
494		return 0;
495
496	Debug( LDAP_DEBUG_TRACE, "=> index_entry_%s( %ld, \"%s\" )\n",
497		opid == SLAP_INDEX_DELETE_OP ? "del" : "add",
498		(long) e->e_id, e->e_dn );
499
500	/* add each attribute to the indexes */
501	for ( ; ap != NULL; ap = ap->a_next ) {
502#if 0 /* ifdef LDAP_COMP_MATCH */
503		AttrInfo *ai;
504		/* see if attribute has components to be indexed */
505		ai = bdb_attr_mask( op->o_bd->be_private, ap->a_desc->ad_type->sat_ad );
506		if ( !ai ) continue;
507		cr_list = ai->ai_cr;
508		if ( attr_converter && cr_list ) {
509			syn = ap->a_desc->ad_type->sat_syntax;
510			ap->a_comp_data = op->o_tmpalloc( sizeof( ComponentData ), op->o_tmpmemctx );
511                	/* Memory chunk(nibble) pre-allocation for decoders */
512                	mem_op = nibble_mem_allocator ( 1024*16, 1024*4 );
513			ap->a_comp_data->cd_mem_op = mem_op;
514			for( cr = cr_list ; cr ; cr = cr->cr_next ) {
515				/* count how many values in an attribute */
516				for( num_attr=0; ap->a_vals[num_attr].bv_val != NULL; num_attr++ );
517				num_attr++;
518				cr->cr_nvals = (BerVarray)op->o_tmpalloc( sizeof( struct berval )*num_attr, op->o_tmpmemctx );
519				for( i=0; ap->a_vals[i].bv_val != NULL; i++ ) {
520					/* decoding attribute value */
521					decoded_comp = attr_converter ( ap, syn, &ap->a_vals[i] );
522					if ( !decoded_comp )
523						return LDAP_DECODING_ERROR;
524					/* extracting the referenced component */
525					dupped_cr = dup_comp_ref( op, cr );
526					csi_attr = ((ComponentSyntaxInfo*)decoded_comp)->csi_comp_desc->cd_extract_i( mem_op, dupped_cr, decoded_comp );
527					if ( !csi_attr )
528						return LDAP_DECODING_ERROR;
529					cr->cr_asn_type_id = csi_attr->csi_comp_desc->cd_type_id;
530					cr->cr_ad = (AttributeDescription*)get_component_description ( cr->cr_asn_type_id );
531					if ( !cr->cr_ad )
532						return LDAP_INVALID_SYNTAX;
533					at = cr->cr_ad->ad_type;
534					/* encoding the value of component in GSER */
535					rc = component_encoder( mem_op, csi_attr, &value );
536					if ( rc != LDAP_SUCCESS )
537						return LDAP_ENCODING_ERROR;
538					/* Normalize the encoded component values */
539					if ( at->sat_equality && at->sat_equality->smr_normalize ) {
540						rc = at->sat_equality->smr_normalize (
541							SLAP_MR_VALUE_OF_ATTRIBUTE_SYNTAX,
542							at->sat_syntax, at->sat_equality,
543							&value, &cr->cr_nvals[i], op->o_tmpmemctx );
544					} else {
545						cr->cr_nvals[i] = value;
546					}
547				}
548				/* The end of BerVarray */
549				cr->cr_nvals[num_attr-1].bv_val = NULL;
550				cr->cr_nvals[num_attr-1].bv_len = 0;
551			}
552			op->o_tmpfree( ap->a_comp_data, op->o_tmpmemctx );
553			nibble_mem_free ( mem_op );
554			ap->a_comp_data = NULL;
555		}
556#endif
557		rc = bdb_index_values( op, txn, ap->a_desc,
558			ap->a_nvals, e->e_id, opid );
559
560		if( rc != LDAP_SUCCESS ) {
561			Debug( LDAP_DEBUG_TRACE,
562				"<= index_entry_%s( %ld, \"%s\" ) failure\n",
563				opid == SLAP_INDEX_ADD_OP ? "add" : "del",
564				(long) e->e_id, e->e_dn );
565			return rc;
566		}
567	}
568
569	Debug( LDAP_DEBUG_TRACE, "<= index_entry_%s( %ld, \"%s\" ) success\n",
570		opid == SLAP_INDEX_DELETE_OP ? "del" : "add",
571		(long) e->e_id, e->e_dn );
572
573	return LDAP_SUCCESS;
574}
575