pcache.c 51.6 KB
Newer Older
1
2
3
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
Kurt Zeilenga's avatar
Kurt Zeilenga committed
4
 * Copyright 2003-2004 The OpenLDAP Foundation.
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 * Portions Copyright 2003 IBM Corporation.
 * Portions Copyright 2003 Symas Corporation.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in the file LICENSE in the
 * top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
 */
/* ACKNOWLEDGEMENTS:
 * This work was initially developed by Apurva Kumar for inclusion
Kurt Zeilenga's avatar
Kurt Zeilenga committed
19
 * in OpenLDAP Software and subsequently rewritten by Howard Chu.
20
21
22
23
 */

#include "portable.h"

Howard Chu's avatar
Howard Chu committed
24
25
#ifdef SLAPD_OVER_PROXYCACHE

26
27
28
29
30
31
32
33
#include <stdio.h>

#include <ac/string.h>
#include <ac/time.h>

#include "slap.h"
#include "ldap_pvt.h"
#include "lutil.h"
34
#include "ldap_rq.h"
35
36
37
38
39
40
41
42
43
44
45
46
47

/* query cache structs */
/* query */

typedef struct Query_s {
	Filter* 	filter; 	/* Search Filter */
	AttributeName* 	attrs;		/* Projected attributes */
	struct berval 	base; 		/* Search Base */
	int 		scope;		/* Search scope */
} Query;

/* struct representing a cached query */
typedef struct cached_query_s {
Howard Chu's avatar
Howard Chu committed
48
49
50
51
	Query 				query;		/* LDAP query */
	struct berval			q_uuid;		/* query identifier */
	int 				template_id;	/* template of the query */
	time_t 				expiry_time;	/* time till the query is considered valid */
52
53
	struct cached_query_s  		*next;  	/* next query in the template */
	struct cached_query_s  		*prev;  	/* previous query in the template */
Howard Chu's avatar
Howard Chu committed
54
55
56
	struct cached_query_s           *lru_up;	/* previous query in the LRU list */
	struct cached_query_s           *lru_down;	/* next query in the LRU list */
} CachedQuery;
57
58

/* struct representing a query template
Howard Chu's avatar
Howard Chu committed
59
 * e.g. template string = &(cn=)(mail=)
60
61
62
 */
typedef struct query_template_s {
	struct berval	querystr;	/* Filter string corresponding to the QT */
Howard Chu's avatar
Howard Chu committed
63
	int 		attr_set_index; /* determines the projected attributes */
64

Howard Chu's avatar
Howard Chu committed
65
66
	CachedQuery* 	query;	        /* most recent query cached for the template */
	CachedQuery* 	query_last;     /* oldest query cached for the template */
67
68

	int 		no_of_queries;  /* Total number of queries in the template */
Howard Chu's avatar
Howard Chu committed
69
70
	long 		ttl;		/* TTL for the queries of this template */
        ldap_pvt_thread_rdwr_t t_rwlock; /* Rd/wr lock for accessing queries in the template */
71
72
} QueryTemplate;

Howard Chu's avatar
Howard Chu committed
73
/*
74
 * Represents a set of projected attributes and any
Howard Chu's avatar
Howard Chu committed
75
 * supersets among all specified sets of attributes.
76
77
78
79
 */

struct attr_set {
	AttributeName*	attrs; 		/* specifies the set */
Howard Chu's avatar
Howard Chu committed
80
81
	int 		count;		/* number of attributes */
	int*		ID_array;	/* array of indices of supersets of 'attrs' */
82
83
};

Howard Chu's avatar
Howard Chu committed
84
struct query_manager_s;
85

Howard Chu's avatar
Howard Chu committed
86
87
/* prototypes for functions for 1) query containment
 * 2) query addition, 3) cache replacement
88
89
90
91
92
 */
typedef int 	(QCfunc)(struct query_manager_s*, Query*, int );
typedef void  	(AddQueryfunc)(struct query_manager_s*, Query*, int, struct berval*);
typedef void	(CRfunc)(struct query_manager_s*, struct berval * );

Howard Chu's avatar
Howard Chu committed
93
/* LDAP query cache */
94
95
96
97
98
99
100
101
102
103
typedef struct query_manager_s {
	struct attr_set* 	attr_sets;		/* possible sets of projected attributes */
	QueryTemplate*	  	templates;		/* cacheable templates */

	CachedQuery*		lru_top;		/* top and bottom of LRU list */
	CachedQuery*		lru_bottom;

	ldap_pvt_thread_mutex_t		lru_mutex;	/* mutex for accessing LRU list */

	/* Query cache methods */
Howard Chu's avatar
Howard Chu committed
104
	QCfunc			*qcfunc;			/* Query containment*/
105
	CRfunc 			*crfunc;			/* cache replacement */
Howard Chu's avatar
Howard Chu committed
106
107
	AddQueryfunc	*addfunc;			/* add query */
} query_manager;
108

Howard Chu's avatar
Howard Chu committed
109
/* LDAP query cache manager */
110
typedef struct cache_manager_s {
111
	BackendDB	db;	/* underlying database */
112
	unsigned long	num_cached_queries; 		/* total number of cached queries */
Howard Chu's avatar
Howard Chu committed
113
	unsigned long   max_queries;			/* upper bound on # of cached queries */
114
115
	int 	numattrsets;			/* number of attribute sets */
	int 	numtemplates;			/* number of cacheable templates */
Howard Chu's avatar
Howard Chu committed
116
117
118
	int 	cur_entries;			/* current number of entries cached */
	int 	max_entries;			/* max number of entries cached */
        int     num_entries_limit;		/* max # of entries in a cacheable query */
119

Howard Chu's avatar
Howard Chu committed
120
	int     cc_period;		/* interval between successive consistency checks (sec) */
121
122
	int	cc_paused;
	void	*cc_arg;
123

Howard Chu's avatar
Howard Chu committed
124
	ldap_pvt_thread_mutex_t		cache_mutex;
125
126
	ldap_pvt_thread_mutex_t		remove_mutex;

Howard Chu's avatar
Howard Chu committed
127
128
	query_manager*   qm;	/* query cache managed by the cache manager */
} cache_manager;
129
130
131
132
133
134
135
136

static AttributeDescription *ad_queryid;
static char *queryid_schema = "( 1.3.6.1.4.1.4203.666.1.12 NAME 'queryid' "
			"DESC 'list of queries the entry belongs to' "
			"EQUALITY octetStringMatch "
			"SYNTAX 1.3.6.1.4.1.1466.115.121.1.40{64} "
			"NO-USER-MODIFICATION USAGE directoryOperation )";

137
/* Return 1 for an added entry, else 0 */
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
static int
merge_entry(
	Operation		*op,
	Entry			*e,
	struct berval*		query_uuid )
{
	int		rc;
	Modifications* modlist = NULL;
	const char* 	text = NULL;
	Attribute		*attr;
	char			textbuf[SLAP_TEXT_BUFLEN];
	size_t			textlen = sizeof(textbuf);

	SlapReply sreply = {REP_RESULT};

153
	slap_callback cb = { NULL, slap_null_cb, NULL, NULL };
154
155
156
157

	attr = e->e_attrs;
	e->e_attrs = NULL;

Howard Chu's avatar
Howard Chu committed
158
	/* add queryid attribute */
159
160
161
162
163
164
165
166
167
168
169
170
	attr_merge_one( e, ad_queryid, query_uuid, NULL );

	/* append the attribute list from the fetched entry */
	e->e_attrs->a_next = attr;

	op->o_tag = LDAP_REQ_ADD;
	op->o_protocol = LDAP_VERSION3;
	op->o_callback = &cb;
	op->o_time = slap_get_time();
	op->o_do_not_cache = 1;

	op->ora_e = e;
Howard Chu's avatar
Howard Chu committed
171
172
	op->o_req_dn = e->e_name;
	op->o_req_ndn = e->e_nname;
173
174
175
176
177
178
179
180
	rc = op->o_bd->be_add( op, &sreply );

	if ( rc != LDAP_SUCCESS ) {
		if ( rc == LDAP_ALREADY_EXISTS ) {
			slap_entry2mods( e, &modlist, &text, textbuf, textlen );
			modlist->sml_op = LDAP_MOD_ADD;
			op->o_tag = LDAP_REQ_MODIFY;
			op->orm_modlist = modlist;
181
			op->o_bd->be_modify( op, &sreply );
182
183
184
185
			slap_mods_free( modlist );
		} else if ( rc == LDAP_REFERRAL ||
					rc == LDAP_NO_SUCH_OBJECT ) {
			syncrepl_add_glue( op, e );
Howard Chu's avatar
Howard Chu committed
186
			e = NULL;
187
188
189
190
191
			rc = 1;
		}
		if ( e ) {
			entry_free( e );
			rc = 0;
192
		}
Howard Chu's avatar
Howard Chu committed
193
194
	} else {
		be_entry_release_w( op, e );
195
		rc = 1;
196
197
	}

198
	return rc;
199
200
201
202
}

/* compare base and scope of incoming and cached queries */
static int base_scope_compare(
Howard Chu's avatar
Howard Chu committed
203
204
205
	struct berval* ndn_stored,
	struct berval* ndn_incoming,
	int scope_stored,
206
207
	int scope_incoming	)
{
Kurt Zeilenga's avatar
Kurt Zeilenga committed
208
	struct berval pdn_incoming = BER_BVNULL;
209
210
211
212
213
214

	if (scope_stored < scope_incoming)
		return 0;

	if ( !dnIsSuffix(ndn_incoming, ndn_stored))
		return 0;
Howard Chu's avatar
Howard Chu committed
215

216
217
218
219
220
221
222
	switch(scope_stored) {
	case LDAP_SCOPE_BASE:
		return (ndn_incoming->bv_len == ndn_stored->bv_len);

	case LDAP_SCOPE_ONELEVEL:
		switch(scope_incoming){
		case LDAP_SCOPE_BASE:
Howard Chu's avatar
Howard Chu committed
223
			dnParent(ndn_incoming, &pdn_incoming);
224
225
226
227
228
229
230
231
232
233
234
235
236
			return (pdn_incoming.bv_len == ndn_stored->bv_len);

		case LDAP_SCOPE_ONELEVEL:
			return (ndn_incoming->bv_len == ndn_stored->bv_len);

		default:
			return 0;
		}
	case LDAP_SCOPE_SUBTREE:
		return 1;
		break;
	default:
		return 0;
Howard Chu's avatar
Howard Chu committed
237
		break;
238
239
240
241
    }
}

/* add query on top of LRU list */
Howard Chu's avatar
Howard Chu committed
242
243
static void
add_query_on_top (query_manager* qm, CachedQuery* qc)
244
{
Howard Chu's avatar
Howard Chu committed
245
246
247
248
	CachedQuery* top = qm->lru_top;
	Query* q = (Query*)qc;

	qm->lru_top = qc;
249

Howard Chu's avatar
Howard Chu committed
250
251
	if (top)
		top->lru_up = qc;
252
	else
Howard Chu's avatar
Howard Chu committed
253
254
255
256
		qm->lru_bottom = qc;

	qc->lru_down = top;
	qc->lru_up = NULL;
257
258
259
260
261
262
263
264
265
266
267
#ifdef NEW_LOGGING
	LDAP_LOG( BACK_META, DETAIL1, "Base of added query = %s\n",
			q->base.bv_val, 0, 0 );
#else
	Debug( LDAP_DEBUG_ANY, "Base of added query = %s\n",
			q->base.bv_val, 0, 0 );
#endif
}

/* remove_query from LRU list */

Howard Chu's avatar
Howard Chu committed
268
269
static void
remove_query (query_manager* qm, CachedQuery* qc)
270
{
Howard Chu's avatar
Howard Chu committed
271
272
	CachedQuery* up;
	CachedQuery* down;
273

Howard Chu's avatar
Howard Chu committed
274
275
	if (!qc)
		return;
276

Howard Chu's avatar
Howard Chu committed
277
278
	up = qc->lru_up;
	down = qc->lru_down;
279

Howard Chu's avatar
Howard Chu committed
280
281
	if (!up)
		qm->lru_top = down;
282

Howard Chu's avatar
Howard Chu committed
283
284
	if (!down)
		qm->lru_bottom = up;
285

Howard Chu's avatar
Howard Chu committed
286
287
	if (down)
		down->lru_up = up;
288

Howard Chu's avatar
Howard Chu committed
289
290
	if (up)
		up->lru_down = down;
291

Howard Chu's avatar
Howard Chu committed
292
	qc->lru_up = qc->lru_down = NULL;
293
294
295
296
297
}

static void
invert_string( struct berval *bv )
{
Howard Chu's avatar
Howard Chu committed
298
	int i;
299
300
301
302
303
304
305
	char c;

	for (i=0; i<bv->bv_len/2; i++) {
		c = bv->bv_val[i];
		bv->bv_val[i] = bv->bv_val[bv->bv_len-i-1];
		bv->bv_val[bv->bv_len-i-1] = c;
	}
Howard Chu's avatar
Howard Chu committed
306
}
307

Howard Chu's avatar
Howard Chu committed
308
309
/* find and remove string2 from string1
 * from start if position = 1,
310
311
312
313
 * from end if position = 3,
 * from anywhere if position = 2
 */

Howard Chu's avatar
Howard Chu committed
314
static int
315
316
find_and_remove(struct berval* ber1, struct berval* ber2, int position)
{
Howard Chu's avatar
Howard Chu committed
317
318
	char* temp;
	int len;
319
320
	int ret=0;

Howard Chu's avatar
Howard Chu committed
321
	char* arg1, *arg2;
322
323
324
	char* string1=ber1->bv_val;
	char* string2=ber2->bv_val;

Howard Chu's avatar
Howard Chu committed
325
326
327
328
	if (string2 == NULL)
		return 1;
	if (string1 == NULL)
		return 0;
329
330

	if (position == 3) {
Howard Chu's avatar
Howard Chu committed
331
332
		invert_string(ber1);
		invert_string(ber2);
333
334
	}

Howard Chu's avatar
Howard Chu committed
335
336
	arg1 = string1;
	arg2 = string2;
337

Howard Chu's avatar
Howard Chu committed
338
	temp = strstr(arg1, arg2);
339
340
341
342
343
344
345
346
347
348

	len = ber2->bv_len;

	if ( temp && (position == 2 || temp == arg1) ) {
		string1 = temp+len;
		strcpy( arg1, string1 );
		ber1->bv_len -= len;
		ret = 1;
	}
	if ( position == 3 ) {
Howard Chu's avatar
Howard Chu committed
349
350
		invert_string(ber1);
		invert_string(ber2);
351
352
353
354
355
	}
	return ret;
}


Howard Chu's avatar
Howard Chu committed
356
static struct berval*
357
358
merge_init_final(struct berval* init, struct berval* any, struct berval* final)
{
Howard Chu's avatar
Howard Chu committed
359
360
	struct berval* merged, *temp;
	int i, any_count, count;
361
362
363
364

	for (any_count=0; any && any[any_count].bv_val; any_count++)
		;

Howard Chu's avatar
Howard Chu committed
365
	count = any_count;
366

Howard Chu's avatar
Howard Chu committed
367
368
	if (init->bv_val)
		count++;
369
	if (final->bv_val)
Howard Chu's avatar
Howard Chu committed
370
		count++;
371

Howard Chu's avatar
Howard Chu committed
372
373
	merged = (struct berval*)(ch_malloc((count+1)*sizeof(struct berval)));
	temp = merged;
374
375
376
377
378
379
380

	if (init->bv_val) {
		*temp++ = *init;
	}

	for (i=0; i<any_count; i++) {
		*temp++ = *any++;
Howard Chu's avatar
Howard Chu committed
381
	}
382

Howard Chu's avatar
Howard Chu committed
383
	if (final->bv_val){
384
		*temp++ = *final;
Howard Chu's avatar
Howard Chu committed
385
386
387
388
	}
	temp->bv_val = NULL;
	temp->bv_len = 0;
	return merged;
389
390
391
392
393
394
395
}

static int
strings_containment(struct berval* stored, struct berval* incoming)
{
	struct berval* element;
	int k=0;
Howard Chu's avatar
Howard Chu committed
396
397
	int j, rc = 0;

398
399
400
	for ( element=stored; element->bv_val != NULL; element++ ) {
		for (j = k; incoming[j].bv_val != NULL; j++) {
			if (find_and_remove(&(incoming[j]), element, 2)) {
Howard Chu's avatar
Howard Chu committed
401
402
403
				k = j;
				rc = 1;
				break;
404
			}
Howard Chu's avatar
Howard Chu committed
405
			rc = 0;
406
407
		}
		if ( rc ) {
Howard Chu's avatar
Howard Chu committed
408
			continue;
409
410
411
		} else {
			return 0;
		}
Howard Chu's avatar
Howard Chu committed
412
	}
413
414
415
416
	return 1;
}

static int
Howard Chu's avatar
Howard Chu committed
417
substr_containment_substr(Filter* stored, Filter* incoming)
418
{
Howard Chu's avatar
Howard Chu committed
419
	int i;
420
	int rc = 0;
Howard Chu's avatar
Howard Chu committed
421
	int any_count = 0;
422
423
424

	struct berval init_incoming;
	struct berval final_incoming;
Howard Chu's avatar
Howard Chu committed
425
426
427
428
429
430
431
432
433
434
435
436
	struct berval *any_incoming = NULL;
	struct berval *remaining_incoming = NULL;

	if ((!(incoming->f_sub_initial.bv_val) && (stored->f_sub_initial.bv_val))
	   || (!(incoming->f_sub_final.bv_val) && (stored->f_sub_final.bv_val)))
		return 0;


	ber_dupbv(&init_incoming, &(incoming->f_sub_initial));
	ber_dupbv(&final_incoming, &(incoming->f_sub_final));

	if (incoming->f_sub_any) {
437
438
439
		for ( any_count=0; incoming->f_sub_any[any_count].bv_val != NULL;
				any_count++ )
			;
Howard Chu's avatar
Howard Chu committed
440

441
		any_incoming = (struct berval*)ch_malloc((any_count+1) *
Howard Chu's avatar
Howard Chu committed
442
443
						sizeof(struct berval));

444
		for (i=0; i<any_count; i++) {
Howard Chu's avatar
Howard Chu committed
445
			ber_dupbv(&(any_incoming[i]), &(incoming->f_sub_any[i]));
446
		}
Howard Chu's avatar
Howard Chu committed
447
448
		any_incoming[any_count].bv_val = NULL;
		any_incoming[any_count].bv_len = 0;
449
	}
Howard Chu's avatar
Howard Chu committed
450
451
452
453

	if (find_and_remove(&init_incoming,
			&(stored->f_sub_initial), 1) && find_and_remove(&final_incoming,
			&(stored->f_sub_final), 3))
454
455
	{
		if (stored->f_sub_any == NULL) {
Howard Chu's avatar
Howard Chu committed
456
457
			rc = 1;
			goto final;
458
459
		}
		remaining_incoming = merge_init_final(&init_incoming,
Howard Chu's avatar
Howard Chu committed
460
						any_incoming, &final_incoming);
461
		rc = strings_containment(stored->f_sub_any, remaining_incoming);
Howard Chu's avatar
Howard Chu committed
462
	}
463
464
final:
	free(init_incoming.bv_val);
Howard Chu's avatar
Howard Chu committed
465
	free(final_incoming.bv_val);
466
467
	if (any_incoming) ber_bvarray_free( any_incoming );
	free(remaining_incoming);
Howard Chu's avatar
Howard Chu committed
468
469

	return rc;
470
471
472
}

static int
Howard Chu's avatar
Howard Chu committed
473
substr_containment_equality(Filter* stored, Filter* incoming)
474
475
476
{
	struct berval incoming_val[2];
	int rc = 0;
Howard Chu's avatar
Howard Chu committed
477

478
479
480
	ber_dupbv(incoming_val, &(incoming->f_av_value));
	incoming_val[1].bv_val = NULL;
	incoming_val[1].bv_len = 0;
Howard Chu's avatar
Howard Chu committed
481

482
	if (find_and_remove(incoming_val,
Howard Chu's avatar
Howard Chu committed
483
			&(stored->f_sub_initial), 1) && find_and_remove(incoming_val,
484
			&(stored->f_sub_final), 3)) {
Howard Chu's avatar
Howard Chu committed
485
		if (stored->f_sub_any == NULL){
486
487
			rc = 1;
			goto final;
Howard Chu's avatar
Howard Chu committed
488
		}
489
490
491
492
493
494
495
		rc = strings_containment(stored->f_sub_any, incoming_val);
	}
final:
	free(incoming_val[0].bv_val);
	return rc;
}

Howard Chu's avatar
Howard Chu committed
496
497
/* check whether query is contained in any of
 * the cached queries in template template_index
498
 */
Howard Chu's avatar
Howard Chu committed
499
500
501
static int
query_containment(query_manager *qm,
		  Query *query,
502
503
504
505
506
		  int template_index)
{
	QueryTemplate* templa= qm->templates;
	CachedQuery* qc;
	Query* q;
Howard Chu's avatar
Howard Chu committed
507
508
509
	Filter* inputf = query->filter;
	struct berval* base = &(query->base);
	int scope = query->scope;
510
511
512
	int res=0;
	Filter* fs;
	Filter* fi;
Howard Chu's avatar
Howard Chu committed
513
514
	int ret, rc;
	const char* text;
515
516
517
518
519
520
521
522
523
524

	MatchingRule* mrule = NULL;
	if (inputf != NULL) {
#ifdef NEW_LOGGING
		LDAP_LOG( BACK_META, DETAIL1, "Lock QC index = %d\n",
				template_index, 0, 0 );
#else
		Debug( LDAP_DEBUG_ANY, "Lock QC index = %d\n",
				template_index, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
525
		ldap_pvt_thread_rdwr_rlock(&(templa[template_index].t_rwlock));
526
		for(qc=templa[template_index].query; qc != NULL; qc= qc->next) {
Howard Chu's avatar
Howard Chu committed
527
			q = (Query*)qc;
528
529
			if(base_scope_compare(&(q->base), base, q->scope, scope)) {
				fi = inputf;
Howard Chu's avatar
Howard Chu committed
530
531
				fs = q->filter;
				do {
532
533
534
					res=0;
					switch (fs->f_choice) {
					case LDAP_FILTER_EQUALITY:
Howard Chu's avatar
Howard Chu committed
535
536
537
538
539
						if (fi->f_choice == LDAP_FILTER_EQUALITY)
							mrule = fs->f_ava->aa_desc->ad_type->sat_equality;
						else
							ret = 1;
						break;
540
541
					case LDAP_FILTER_GE:
					case LDAP_FILTER_LE:
Howard Chu's avatar
Howard Chu committed
542
543
544
545
						mrule = fs->f_ava->aa_desc->ad_type->sat_ordering;
						break;
					default:
						mrule = NULL; 
546
					}
Howard Chu's avatar
Howard Chu committed
547
548
549
550
551
					if (mrule) {
						rc = value_match(&ret, fs->f_ava->aa_desc, mrule,
						 	SLAP_MR_VALUE_OF_ASSERTION_SYNTAX,
							&(fi->f_ava->aa_value),
							&(fs->f_ava->aa_value), &text);
552
						if (rc != LDAP_SUCCESS) {
Howard Chu's avatar
Howard Chu committed
553
							ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
554
555
556
557
558
559
560
561
562
#ifdef NEW_LOGGING
							LDAP_LOG( BACK_META, DETAIL1,
							"Unlock: Exiting QC index=%d\n",
							template_index, 0, 0 );
#else
							Debug( LDAP_DEBUG_ANY,
							"Unlock: Exiting QC index=%d\n",
							template_index, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
563
							return 0;
564
565
566
						}
					}
					switch (fs->f_choice) {
Howard Chu's avatar
Howard Chu committed
567
					case LDAP_FILTER_OR:
568
569
570
571
					case LDAP_FILTER_AND:
						fs = fs->f_and;
						fi = fi->f_and;
						res=1;
Howard Chu's avatar
Howard Chu committed
572
573
574
						break;
					case LDAP_FILTER_SUBSTRINGS:
						/* check if the equality query can be
575
576
577
578
						* answered with cached substring query */
						if ((fi->f_choice == LDAP_FILTER_EQUALITY)
							&& substr_containment_equality(
							fs, fi))
Howard Chu's avatar
Howard Chu committed
579
580
							res=1;
						/* check if the substring query can be
581
582
583
584
585
586
						* answered with cached substring query */
						if ((fi->f_choice ==LDAP_FILTER_SUBSTRINGS
							) && substr_containment_substr(
							fs, fi))
							res= 1;
						fs=fs->f_next;
Howard Chu's avatar
Howard Chu committed
587
588
589
						fi=fi->f_next;
						break;
					case LDAP_FILTER_PRESENT:
590
591
						res=1;
						fs=fs->f_next;
Howard Chu's avatar
Howard Chu committed
592
593
594
595
						fi=fi->f_next;
						break;
					case LDAP_FILTER_EQUALITY:
						if (ret == 0)
596
597
							res = 1;
						fs=fs->f_next;
Howard Chu's avatar
Howard Chu committed
598
599
600
						fi=fi->f_next;
						break;
					case LDAP_FILTER_GE:
601
						if (ret >= 0)
Howard Chu's avatar
Howard Chu committed
602
							res = 1;
603
						fs=fs->f_next;
Howard Chu's avatar
Howard Chu committed
604
						fi=fi->f_next;
605
						break;
Howard Chu's avatar
Howard Chu committed
606
					case LDAP_FILTER_LE:
607
						if (ret <= 0)
Howard Chu's avatar
Howard Chu committed
608
							res = 1;
609
						fs=fs->f_next;
Howard Chu's avatar
Howard Chu committed
610
						fi=fi->f_next;
611
612
613
614
615
616
						break;
					case LDAP_FILTER_NOT:
						res=0;
						break;
					default:
						break;
Howard Chu's avatar
Howard Chu committed
617
					}
618
619
620
				} while((res) && (fi != NULL) && (fs != NULL));

				if(res) {
Howard Chu's avatar
Howard Chu committed
621
					ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
622
					if (qm->lru_top != qc) {
Howard Chu's avatar
Howard Chu committed
623
624
						remove_query(qm, qc);
						add_query_on_top(qm, qc);
625
					}
Howard Chu's avatar
Howard Chu committed
626
					ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
627
					return 1;
Howard Chu's avatar
Howard Chu committed
628
				}
629
630
631
632
633
634
635
636
637
638
639
			}
		}
#ifdef NEW_LOGGING
		LDAP_LOG( BACK_META, DETAIL1,
			"Not answerable: Unlock QC index=%d\n",
			template_index, 0, 0 );
#else
		Debug( LDAP_DEBUG_ANY,
			"Not answerable: Unlock QC index=%d\n",
			template_index, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
640
		ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
641
	}
Howard Chu's avatar
Howard Chu committed
642
	return 0;
643
644
}

Howard Chu's avatar
Howard Chu committed
645
646
static void
free_query (CachedQuery* qc)
647
{
Howard Chu's avatar
Howard Chu committed
648
	Query* q = (Query*)qc;
Howard Chu's avatar
Howard Chu committed
649
650
	int i;

Howard Chu's avatar
Howard Chu committed
651
652
653
	free(qc->q_uuid.bv_val);
	filter_free(q->filter);
	free (q->base.bv_val);
Howard Chu's avatar
Howard Chu committed
654
655
656
	for (i=0; q->attrs[i].an_name.bv_val; i++) {
		free(q->attrs[i].an_name.bv_val);
	}
Howard Chu's avatar
Howard Chu committed
657
658
	free(q->attrs);
	free(qc);
659
660
661
662
663
}


/* Add query to query cache */
static void add_query(
Howard Chu's avatar
Howard Chu committed
664
665
666
	query_manager* qm,
	Query* query,
	int template_index,
667
668
669
	struct berval* uuid)
{
	CachedQuery* new_cached_query = (CachedQuery*) ch_malloc(sizeof(CachedQuery));
Howard Chu's avatar
Howard Chu committed
670
	QueryTemplate* templ = (qm->templates)+template_index;
671
	Query* new_query;
Howard Chu's avatar
Howard Chu committed
672
673
674
675
676
	new_cached_query->template_id = template_index;
	new_cached_query->q_uuid = *uuid;
	new_cached_query->lru_up = NULL;
	new_cached_query->lru_down = NULL;
	new_cached_query->expiry_time = slap_get_time() + templ->ttl;
677
678
679
680
681
682
683
#ifdef NEW_LOGGING
	LDAP_LOG( BACK_META, DETAIL1, "Added query expires at %ld\n",
			(long) new_cached_query->expiry_time, 0, 0 );
#else
	Debug( LDAP_DEBUG_ANY, "Added query expires at %ld\n",
			(long) new_cached_query->expiry_time, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
684
	new_query = (Query*)new_cached_query;
685
686

	ber_dupbv(&new_query->base, &query->base);
Howard Chu's avatar
Howard Chu committed
687
	new_query->scope = query->scope;
688
	new_query->filter = query->filter;
Howard Chu's avatar
Howard Chu committed
689
	new_query->attrs = query->attrs;
690
691
692
693
694
695
696
697
698

	/* Adding a query    */
#ifdef NEW_LOGGING
	LDAP_LOG( BACK_META, DETAIL1, "Lock AQ index = %d\n",
			template_index, 0, 0 );
#else
	Debug( LDAP_DEBUG_ANY, "Lock AQ index = %d\n",
			template_index, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
699
700
701
702
703
704
705
706
707
	ldap_pvt_thread_rdwr_wlock(&templ->t_rwlock);
	if (templ->query == NULL)
		templ->query_last = new_cached_query;
	else
		templ->query->prev = new_cached_query;
	new_cached_query->next = templ->query;
	new_cached_query->prev = NULL;
	templ->query = new_cached_query;
	templ->no_of_queries++;
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
#ifdef NEW_LOGGING
	LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES++ %d\n",
			template_index, templ->no_of_queries, 0 );
#else
	Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES++ %d\n",
			template_index, templ->no_of_queries, 0 );
#endif

#ifdef NEW_LOGGING
	LDAP_LOG( BACK_META, DETAIL1, "Unlock AQ index = %d \n",
			template_index, 0, 0 );
#else
	Debug( LDAP_DEBUG_ANY, "Unlock AQ index = %d \n",
			template_index, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
723
	ldap_pvt_thread_rdwr_wunlock(&templ->t_rwlock);
724
725

	/* Adding on top of LRU list  */
Howard Chu's avatar
Howard Chu committed
726
727
728
	ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
	add_query_on_top(qm, new_cached_query);
	ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
729
730
731
732
733
734
}

static void
remove_from_template (CachedQuery* qc, QueryTemplate* template)
{
	if (!qc->prev && !qc->next) {
Howard Chu's avatar
Howard Chu committed
735
		template->query_last = template->query = NULL;
736
	} else if (qc->prev == NULL) {
Howard Chu's avatar
Howard Chu committed
737
738
		qc->next->prev = NULL;
		template->query = qc->next;
739
	} else if (qc->next == NULL) {
Howard Chu's avatar
Howard Chu committed
740
741
		qc->prev->next = NULL;
		template->query_last = qc->prev;
742
	} else {
Howard Chu's avatar
Howard Chu committed
743
744
		qc->next->prev = qc->prev;
		qc->prev->next = qc->next;
745
746
	}

Howard Chu's avatar
Howard Chu committed
747
	template->no_of_queries--;
748
749
}

Howard Chu's avatar
Howard Chu committed
750
/* remove bottom query of LRU list from the query cache */
751
752
static void cache_replacement(query_manager* qm, struct berval *result)
{
Howard Chu's avatar
Howard Chu committed
753
	CachedQuery* bottom;
754
755
	int temp_id;

Howard Chu's avatar
Howard Chu committed
756
757
	ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
	bottom = qm->lru_bottom;
758
759
760
761
762
763
764
765
766
767
768
769
770
771

	result->bv_val = NULL;
	result->bv_len = 0;

	if (!bottom) {
#ifdef NEW_LOGGING
		LDAP_LOG ( BACK_META, DETAIL1,
			"Cache replacement invoked without "
			"any query in LRU list\n", 0, 0, 0 );
#else
		Debug ( LDAP_DEBUG_ANY,
			"Cache replacement invoked without "
			"any query in LRU list\n", 0, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
772
		return;
773
774
775
	}

	temp_id = bottom->template_id;
Howard Chu's avatar
Howard Chu committed
776
777
	remove_query(qm, bottom);
	ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
778

Howard Chu's avatar
Howard Chu committed
779
	*result = bottom->q_uuid;
780
781
782
783
784
785
786
	bottom->q_uuid.bv_val = NULL;

#ifdef NEW_LOGGING
	LDAP_LOG( BACK_META, DETAIL1, "Lock CR index = %d\n", temp_id, 0, 0 );
#else
	Debug( LDAP_DEBUG_ANY, "Lock CR index = %d\n", temp_id, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
787
788
	ldap_pvt_thread_rdwr_wlock(&(qm->templates[temp_id].t_rwlock));
	remove_from_template(bottom, (qm->templates+temp_id));
789
790
791
792
793
794
795
796
797
798
799
800
#ifdef NEW_LOGGING
	LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES-- %d\n",
		temp_id, qm->templates[temp_id].no_of_queries, 0 );
#else
	Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES-- %d\n",
		temp_id, qm->templates[temp_id].no_of_queries, 0 );
#endif
#ifdef NEW_LOGGING
	LDAP_LOG( BACK_META, DETAIL1, "Unlock CR index = %d\n", temp_id, 0, 0 );
#else
	Debug( LDAP_DEBUG_ANY, "Unlock CR index = %d\n", temp_id, 0, 0 );
#endif
Howard Chu's avatar
Howard Chu committed
801
802
	ldap_pvt_thread_rdwr_wunlock(&(qm->templates[temp_id].t_rwlock));
	free_query(bottom);
803
804
805
}

struct query_info {
Howard Chu's avatar
Howard Chu committed
806
807
808
	struct query_info *next;
	struct berval xdn;
	int del;
Howard Chu's avatar
Howard Chu committed
809
810
};

811
812
813
814
815
816
static int
remove_func (
	Operation	*op,
	SlapReply	*rs
)
{
Howard Chu's avatar
Howard Chu committed
817
818
819
	Attribute *attr;
	struct query_info *qi;
	int count = 0;
820

Howard Chu's avatar
Howard Chu committed
821
	if ( rs->sr_type != REP_SEARCH ) return 0;
822
823
824

	for (attr = rs->sr_entry->e_attrs; attr!= NULL; attr = attr->a_next) {
		if (attr->a_desc == ad_queryid) {
Howard Chu's avatar
Howard Chu committed
825
			for (count=0; attr->a_vals[count].bv_val; count++)
826
				;
Howard Chu's avatar
Howard Chu committed
827
			break;
828
		}
Howard Chu's avatar
Howard Chu committed
829
	}
Howard Chu's avatar
Howard Chu committed
830
831
832
833
834
835
	if ( count == 0 ) return 0;
	qi = op->o_tmpalloc( sizeof( struct query_info ), op->o_tmpmemctx );
	qi->next = op->o_callback->sc_private;
	op->o_callback->sc_private = qi;
	ber_dupbv_x( &qi->xdn, &rs->sr_entry->e_nname, op->o_tmpmemctx );
	qi->del = ( count == 1 );
836
837
838

	return 0;
}
Howard Chu's avatar
Howard Chu committed
839
840

static int
841
842
843
844
845
remove_query_data (
	Operation	*op,
	SlapReply	*rs,
	struct berval* query_uuid)
{
Howard Chu's avatar
Howard Chu committed
846
	struct query_info	*qi, *qnext;
Howard Chu's avatar
Howard Chu committed
847
	char			filter_str[64];
Howard Chu's avatar
Howard Chu committed
848
	AttributeAssertion	ava;
849
	Filter			filter = {LDAP_FILTER_EQUALITY};
Howard Chu's avatar
Howard Chu committed
850
	SlapReply 		sreply = {REP_RESULT};
851
	slap_callback cb = { NULL, remove_func, NULL, NULL };
Howard Chu's avatar
Howard Chu committed
852
	int deleted = 0;
853

Howard Chu's avatar
Howard Chu committed
854
855
	sreply.sr_entry = NULL;
	sreply.sr_nentries = 0;
856
857
	op->ors_filterstr.bv_len = snprintf(filter_str, sizeof(filter_str),
		"(%s=%s)", ad_queryid->ad_cname.bv_val, query_uuid->bv_val);
Howard Chu's avatar
Howard Chu committed
858
	filter.f_ava = &ava;
859
860
	filter.f_av_desc = ad_queryid;
	filter.f_av_value = *query_uuid;
Howard Chu's avatar
Howard Chu committed
861

862
863
864
865
866
867
868
869
870
871
	op->o_tag = LDAP_REQ_SEARCH;
	op->o_protocol = LDAP_VERSION3;
	op->o_callback = &cb;
	op->o_time = slap_get_time();
	op->o_do_not_cache = 1;

	op->o_req_dn = op->o_bd->be_suffix[0];
	op->o_req_ndn = op->o_bd->be_nsuffix[0];
	op->ors_scope = LDAP_SCOPE_SUBTREE;
	op->ors_deref = LDAP_DEREF_NEVER;
872
873
	op->ors_slimit = SLAP_NO_LIMIT;
	op->ors_tlimit = SLAP_NO_LIMIT;
874
875
876
877
878
879
880
881
	op->ors_filter = &filter;
	op->ors_filterstr.bv_val = filter_str;
	op->ors_filterstr.bv_len = strlen(filter_str);
	op->ors_attrs = NULL;
	op->ors_attrsonly = 0;

	op->o_bd->be_search( op, &sreply );

Howard Chu's avatar
Howard Chu committed
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
	for ( qi=cb.sc_private; qi; qi=qnext ) {
		qnext = qi->next;

		op->o_req_dn = qi->xdn;
		op->o_req_ndn = qi->xdn;

		if ( qi->del) {
#ifdef NEW_LOGGING
			LDAP_LOG( BACK_META, DETAIL1,
				"DELETING ENTRY TEMPLATE=%s\n",
				query_uuid->bv_val, 0, 0 );
#else
			Debug( LDAP_DEBUG_ANY, "DELETING ENTRY TEMPLATE=%s\n",
				query_uuid->bv_val, 0, 0 );
#endif

			op->o_tag = LDAP_REQ_DELETE;

			if (op->o_bd->be_delete(op, &sreply) == LDAP_SUCCESS) {
				deleted++;
			}
		} else {
			Modifications mod;
			struct berval vals[2];

			vals[0] = *query_uuid;
			vals[1].bv_val = NULL;
			vals[1].bv_len = 0;
			mod.sml_op = LDAP_MOD_DELETE;
			mod.sml_desc = ad_queryid;
			mod.sml_type = ad_queryid->ad_cname;
Kurt Zeilenga's avatar
Kurt Zeilenga committed
913
			mod.sml_values = vals;
914
			mod.sml_nvalues = NULL;
Howard Chu's avatar
Howard Chu committed
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
			mod.sml_next = NULL;
#ifdef NEW_LOGGING
			LDAP_LOG( BACK_META, DETAIL1,
				"REMOVING TEMP ATTR : TEMPLATE=%s\n",
				query_uuid->bv_val, 0, 0 );
#else
			Debug( LDAP_DEBUG_ANY,
				"REMOVING TEMP ATTR : TEMPLATE=%s\n",
				query_uuid->bv_val, 0, 0 );
#endif

			op->orm_modlist = &mod;

			op->o_bd->be_modify( op, &sreply );
		}
		op->o_tmpfree( qi->xdn.bv_val, op->o_tmpmemctx );
		op->o_tmpfree( qi, op->o_tmpmemctx );
	}
	return deleted;
934
935
}

Howard Chu's avatar
Howard Chu committed
936
static int
937
get_attr_set(
Howard Chu's avatar
Howard Chu committed
938
939
	AttributeName* attrs,
	query_manager* qm,
940
941
942
	int num
);

Howard Chu's avatar
Howard Chu committed
943
static int
944
attrscmp(
Howard Chu's avatar
Howard Chu committed
945
	AttributeName* attrs_in,
946
947
948
	AttributeName* attrs
);

Howard Chu's avatar
Howard Chu committed
949
static int
950
is_temp_answerable(
Howard Chu's avatar
Howard Chu committed
951
952
953
	int attr_set,
	struct berval* tempstr,
	query_manager* qm,
954
955
956
957
958
	int template_id )
{
	QueryTemplate *qt = qm->templates + template_id;

	if (attr_set != qt->attr_set_index) {
Howard Chu's avatar
Howard Chu committed
959
		int* id_array = qm->attr_sets[attr_set].ID_array;
960
961
962
963

		while (*id_array != -1) {
			if (*id_array == qt->attr_set_index)
				break;
Howard Chu's avatar
Howard Chu committed
964
			id_array++;
965
966
		}
		if (*id_array == -1)
Howard Chu's avatar
Howard Chu committed
967
			return 0;
968
969
970
971
972
	}
	return (qt->querystr.bv_len == tempstr->bv_len &&
		strcasecmp(qt->querystr.bv_val, tempstr->bv_val) == 0);
}

Howard Chu's avatar
Howard Chu committed
973
static int
974
975
976
filter2template(
	Filter			*f,
	struct			berval *fstr,
Howard Chu's avatar
Howard Chu committed
977
	AttributeName**		filter_attrs,
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
	int*			filter_cnt )
{
	AttributeDescription *ad;

	switch ( f->f_choice ) {
	case LDAP_FILTER_EQUALITY:
		ad = f->f_av_desc;
		sprintf( fstr->bv_val+fstr->bv_len, "(%s=)", ad->ad_cname.bv_val );
		fstr->bv_len += ad->ad_cname.bv_len + ( sizeof("(=)") - 1 );
		break;

	case LDAP_FILTER_GE:
		ad = f->f_av_desc;
		sprintf( fstr->bv_val+fstr->bv_len, "(%s>=)", ad->ad_cname.bv_val);
		fstr->bv_len += ad->ad_cname.bv_len + ( sizeof("(>=)") - 1 );
		break;

	case LDAP_FILTER_LE:
		ad = f->f_av_desc;
		sprintf( fstr->bv_val+fstr->bv_len, "(%s<=)", ad->ad_cname.bv_val);
		fstr->bv_len += ad->ad_cname.bv_len + ( sizeof("(<=)") - 1 );
		break;

For faster browsing, not all history is shown. View entire blame