pcache.c 101 KB
Newer Older
1
2
3
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
4
 * Copyright 2003-2009 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
#include <stdio.h>

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

#include "slap.h"
#include "lutil.h"
33
#include "ldap_rq.h"
34
#include "avl.h"
35

36
37
#include "config.h"

38
39
40
41
42
43
44
45
46
47
48
49
50
#ifdef LDAP_DEVEL
/*
 * Control that allows to access the private DB
 * instead of the public one
 */
#define	PCACHE_CONTROL_PRIVDB		"1.3.6.1.4.1.4203.666.11.9.5.1"

/*
 * Extended Operation that allows to remove a query from the cache
 */
#define PCACHE_EXOP_QUERY_DELETE	"1.3.6.1.4.1.4203.666.11.9.6.1"
#endif

51
52
53
54
55
56
57
58
59
/* query cache structs */
/* query */

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

Howard Chu's avatar
Howard Chu committed
60
61
struct query_template_s;

62
63
64
typedef struct Qbase_s {
	Avlnode *scopes[4];		/* threaded AVL trees of cached queries */
	struct berval base;
Howard Chu's avatar
Howard Chu committed
65
	int queries;
66
67
} Qbase;

68
69
/* struct representing a cached query */
typedef struct cached_query_s {
70
71
72
73
	Filter					*filter;
	Filter					*first;
	Qbase					*qbase;
	int						scope;
Howard Chu's avatar
Howard Chu committed
74
	struct berval			q_uuid;		/* query identifier */
Ralf Haferkamp's avatar
Ralf Haferkamp committed
75
	int						q_sizelimit;
76
	struct query_template_s		*qtemp;	/* template of the query */
Ralf Haferkamp's avatar
Ralf Haferkamp committed
77
	time_t						expiry_time;	/* time till the query is considered valid */
78
79
	struct cached_query_s  		*next;  	/* next query in the template */
	struct cached_query_s  		*prev;  	/* previous query in the template */
Ralf Haferkamp's avatar
Ralf Haferkamp committed
80
81
82
	struct cached_query_s		*lru_up;	/* previous query in the LRU list */
	struct cached_query_s		*lru_down;	/* next query in the LRU list */
	ldap_pvt_thread_rdwr_t		rwlock;
Howard Chu's avatar
Howard Chu committed
83
} CachedQuery;
84

85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
 * URL representation:
 *
 * ldap:///<base>??<scope>?<filter>?x-uuid=<uid>,x-template=<template>,x-attrset=<attrset>,x-expiry=<expiry>
 *
 * <base> ::= CachedQuery.qbase->base
 * <scope> ::= CachedQuery.scope
 * <filter> ::= filter2bv(CachedQuery.filter)
 * <uuid> ::= CachedQuery.q_uuid
 * <attrset> ::= CachedQuery.qtemp->attr_set_index
 * <expiry> ::= CachedQuery.expiry_time
 *
 * quick hack: parse URI, call add_query() and then fix
 * CachedQuery.expiry_time and CachedQuery.q_uuid
 */

Howard Chu's avatar
Howard Chu committed
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
 * Represents a set of projected attributes.
 */

struct attr_set {
	struct query_template_s *templates;
	AttributeName*	attrs; 		/* specifies the set */
	unsigned	flags;
#define	PC_CONFIGURED	(0x1)
#define	PC_REFERENCED	(0x2)
#define	PC_GOT_OC		(0x4)
	int 		count;		/* number of attributes */
};

115
/* struct representing a query template
Howard Chu's avatar
Howard Chu committed
116
 * e.g. template string = &(cn=)(mail=)
117
118
 */
typedef struct query_template_s {
Howard Chu's avatar
Howard Chu committed
119
120
	struct query_template_s *qtnext;
	struct query_template_s *qmnext;
121

122
	Avlnode*		qbase;
Howard Chu's avatar
Howard Chu committed
123
124
	CachedQuery* 	query;	        /* most recent query cached for the template */
	CachedQuery* 	query_last;     /* oldest query cached for the template */
Howard Chu's avatar
Howard Chu committed
125
	ldap_pvt_thread_rdwr_t t_rwlock; /* Rd/wr lock for accessing queries in the template */
Howard Chu's avatar
Howard Chu committed
126
	struct berval	querystr;	/* Filter string corresponding to the QT */
127

Howard Chu's avatar
Howard Chu committed
128
	int 		attr_set_index; /* determines the projected attributes */
129
	int 		no_of_queries;  /* Total number of queries in the template */
130
	time_t		ttl;		/* TTL for the queries of this template */
131
	time_t		negttl;		/* TTL for negative results */
Ralf Haferkamp's avatar
Ralf Haferkamp committed
132
	time_t		limitttl;	/* TTL for sizelimit exceeding results */
Howard Chu's avatar
Howard Chu committed
133
	struct attr_set t_attrs;	/* filter attrs + attr_set */
134
135
} QueryTemplate;

Ralf Haferkamp's avatar
Ralf Haferkamp committed
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
typedef enum {
	PC_IGNORE = 0,
	PC_POSITIVE,
	PC_NEGATIVE,
	PC_SIZELIMIT
} pc_caching_reason_t;

static const char *pc_caching_reason_str[] = {
	"IGNORE",
	"POSITIVE",
	"NEGATIVE",
	"SIZELIMIT",

	NULL
};

Howard Chu's avatar
Howard Chu committed
152
struct query_manager_s;
153

Howard Chu's avatar
Howard Chu committed
154
155
/* prototypes for functions for 1) query containment
 * 2) query addition, 3) cache replacement
156
 */
Ralf Haferkamp's avatar
Ralf Haferkamp committed
157
158
159
160
161
typedef CachedQuery *(QCfunc)(Operation *op, struct query_manager_s*,
	Query*, QueryTemplate*);
typedef CachedQuery *(AddQueryfunc)(Operation *op, struct query_manager_s*,
	Query*, QueryTemplate*, pc_caching_reason_t, int wlock);
typedef void (CRfunc)(struct query_manager_s*, struct berval*);
162

Howard Chu's avatar
Howard Chu committed
163
/* LDAP query cache */
164
165
166
167
168
169
170
171
172
173
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
174
	QCfunc			*qcfunc;			/* Query containment*/
175
	CRfunc 			*crfunc;			/* cache replacement */
Howard Chu's avatar
Howard Chu committed
176
177
	AddQueryfunc	*addfunc;			/* add query */
} query_manager;
178

Howard Chu's avatar
Howard Chu committed
179
/* LDAP query cache manager */
180
typedef struct cache_manager_s {
181
	BackendDB	db;	/* underlying database */
182
	unsigned long	num_cached_queries; 		/* total number of cached queries */
Howard Chu's avatar
Howard Chu committed
183
	unsigned long   max_queries;			/* upper bound on # of cached queries */
184
	int		save_queries;			/* save cached queries across restarts */
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
185
	int	check_cacheability;		/* check whether a query is cacheable */
186
	int 	numattrsets;			/* number of attribute sets */
Howard Chu's avatar
Howard Chu committed
187
188
	int 	cur_entries;			/* current number of entries cached */
	int 	max_entries;			/* max number of entries cached */
Howard Chu's avatar
Howard Chu committed
189
	int 	num_entries_limit;		/* max # of entries in a cacheable query */
190

191
192
193
194
	char	response_cb;			/* install the response callback
						 * at the tail of the callback list */
#define PCACHE_RESPONSE_CB_HEAD	0
#define PCACHE_RESPONSE_CB_TAIL	1
Howard Chu's avatar
Howard Chu committed
195
	char	defer_db_open;			/* defer open for online add */
196

197
	time_t	cc_period;		/* interval between successive consistency checks (sec) */
Howard Chu's avatar
Howard Chu committed
198
	int 	cc_paused;
199
	void	*cc_arg;
200

Howard Chu's avatar
Howard Chu committed
201
	ldap_pvt_thread_mutex_t		cache_mutex;
202

Howard Chu's avatar
Howard Chu committed
203
204
	query_manager*   qm;	/* query cache managed by the cache manager */
} cache_manager;
205

Howard Chu's avatar
Howard Chu committed
206
207
static int pcache_debug;

208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
#ifdef PCACHE_CONTROL_PRIVDB
static int privDB_cid;
#endif /* PCACHE_CONTROL_PRIVDB */

static AttributeDescription *ad_queryId, *ad_cachedQueryURL;
static struct {
	char	*desc;
	AttributeDescription **adp;
} as[] = {
	{ "( 1.3.6.1.4.1.4203.666.11.9.1.1 "
		"NAME 'queryId' "
		"DESC 'ID of query the entry belongs to, formatted as a UUID' "
		"EQUALITY octetStringMatch "
		"SYNTAX 1.3.6.1.4.1.1466.115.121.1.40{64} "
		"NO-USER-MODIFICATION "
		"USAGE directoryOperation )",
		&ad_queryId },
	{ "( 1.3.6.1.4.1.4203.666.11.9.1.2 "
		"NAME 'cachedQueryURL' "
		"DESC 'URI describing a cached query' "
		"EQUALITY caseExactMatch "
		"SYNTAX 1.3.6.1.4.1.1466.115.121.1.15 "
		"NO-USER-MODIFICATION "
		"USAGE directoryOperation )",
		&ad_cachedQueryURL },
	{ NULL }
};

static int
filter2template(
	Operation		*op,
	Filter			*f,
	struct			berval *fstr,
	AttributeName**		filter_attrs,
	int*			filter_cnt,
	int*			filter_got_oc );

static CachedQuery *
add_query(
	Operation *op,
	query_manager* qm,
	Query* query,
	QueryTemplate *templ,
Ralf Haferkamp's avatar
Ralf Haferkamp committed
251
252
	pc_caching_reason_t why,
	int wlock);
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267

static int
remove_query_data(
	Operation	*op,
	SlapReply	*rs,
	struct berval	*query_uuid );

/*
 * Turn a cached query into its URL representation
 */
static int
query2url( Operation *op, CachedQuery *q, struct berval *urlbv )
{
	struct berval	bv_scope,
			bv_filter;
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
268
269
	char		attrset_buf[ LDAP_PVT_INTTYPE_CHARS( unsigned long ) ],
			expiry_buf[ LDAP_PVT_INTTYPE_CHARS( unsigned long ) ],
270
271
272
273
274
275
			*ptr;
	ber_len_t	attrset_len,
			expiry_len;

	ldap_pvt_scope2bv( q->scope, &bv_scope );
	filter2bv_x( op, q->filter, &bv_filter );
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
276
	attrset_len = sprintf( attrset_buf,
277
		"%lu", (unsigned long)q->qtemp->attr_set_index );
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
278
	expiry_len = sprintf( expiry_buf,
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
		"%lu", (unsigned long)q->expiry_time );

	urlbv->bv_len = STRLENOF( "ldap:///" )
		+ q->qbase->base.bv_len
		+ STRLENOF( "??" )
		+ bv_scope.bv_len
		+ STRLENOF( "?" )
		+ bv_filter.bv_len
		+ STRLENOF( "?x-uuid=" )
		+ q->q_uuid.bv_len
		+ STRLENOF( ",x-attrset=" )
		+ attrset_len
		+ STRLENOF( ",x-expiry=" )
		+ expiry_len;
	ptr = urlbv->bv_val = ber_memalloc_x( urlbv->bv_len + 1, op->o_tmpmemctx );
	ptr = lutil_strcopy( ptr, "ldap:///" );
	ptr = lutil_strcopy( ptr, q->qbase->base.bv_val );
	ptr = lutil_strcopy( ptr, "??" );
	ptr = lutil_strcopy( ptr, bv_scope.bv_val );
	ptr = lutil_strcopy( ptr, "?" );
	ptr = lutil_strcopy( ptr, bv_filter.bv_val );
	ptr = lutil_strcopy( ptr, "?x-uuid=" );
	ptr = lutil_strcopy( ptr, q->q_uuid.bv_val );
	ptr = lutil_strcopy( ptr, ",x-attrset=" );
	ptr = lutil_strcopy( ptr, attrset_buf );
	ptr = lutil_strcopy( ptr, ",x-expiry=" );
	ptr = lutil_strcopy( ptr, expiry_buf );

	ber_memfree_x( bv_filter.bv_val, op->o_tmpmemctx );

	return 0;
}

/*
 * Turn an URL representing a formerly cached query into a cached query,
 * and try to cache it
 */
static int
url2query(
	char		*url,
	Operation	*op,
	query_manager	*qm )
{
	Query		query = { 0 };
	QueryTemplate	*qt;
	CachedQuery	*cq;
	LDAPURLDesc	*lud = NULL;
	struct berval	base,
			tempstr = BER_BVNULL,
			uuid;
	int		attrset;
	time_t		expiry_time;
	int		i,
			got_uuid = 0,
			got_attrset = 0,
			got_expiry = 0,
			rc = 0;

	rc = ldap_url_parse( url, &lud );
	if ( rc != LDAP_URL_SUCCESS ) {
		return -1;
	}

	/* non-allowed fields */
	if ( lud->lud_host != NULL ) {
		rc = 1;
		goto error;
	}

	if ( lud->lud_attrs != NULL ) {
		rc = 1;
		goto error;
	}

	/* be pedantic */
	if ( strcmp( lud->lud_scheme, "ldap" ) != 0 ) {
		rc = 1;
		goto error;
	}

	/* required fields */
	if ( lud->lud_dn == NULL || lud->lud_dn[ 0 ] == '\0' ) {
		rc = 1;
		goto error;
	}

	switch ( lud->lud_scope ) {
	case LDAP_SCOPE_BASE:
	case LDAP_SCOPE_ONELEVEL:
	case LDAP_SCOPE_SUBTREE:
	case LDAP_SCOPE_SUBORDINATE:
		break;

	default:
		rc = 1;
		goto error;
	}

	if ( lud->lud_filter == NULL || lud->lud_filter[ 0 ] == '\0' ) {
		rc = 1;
		goto error;
	}

	if ( lud->lud_exts == NULL ) {
		rc = 1;
		goto error;
	}

	for ( i = 0; lud->lud_exts[ i ] != NULL; i++ ) {
		if ( strncmp( lud->lud_exts[ i ], "x-uuid=", STRLENOF( "x-uuid=" ) ) == 0 ) {
			struct berval	tmpUUID;
			Syntax		*syn_UUID = slap_schema.si_ad_entryUUID->ad_type->sat_syntax;

			ber_str2bv( &lud->lud_exts[ i ][ STRLENOF( "x-uuid=" ) ], 0, 0, &tmpUUID );
			rc = syn_UUID->ssyn_pretty( syn_UUID, &tmpUUID, &uuid, NULL );
			if ( rc != LDAP_SUCCESS ) {
				goto error;
			}
			got_uuid = 1;

		} else if ( strncmp( lud->lud_exts[ i ], "x-attrset=", STRLENOF( "x-attrset=" ) ) == 0 ) {
			rc = lutil_atoi( &attrset, &lud->lud_exts[ i ][ STRLENOF( "x-attrset=" ) ] );
			if ( rc ) {
				goto error;
			}
			got_attrset = 1;

		} else if ( strncmp( lud->lud_exts[ i ], "x-expiry=", STRLENOF( "x-expiry=" ) ) == 0 ) {
			unsigned long l;

			rc = lutil_atoul( &l, &lud->lud_exts[ i ][ STRLENOF( "x-expiry=" ) ] );
			if ( rc ) {
				goto error;
			}
			expiry_time = (time_t)l;
			got_expiry = 1;

		} else {
			rc = -1;
			goto error;
		}
	}

	if ( !got_uuid ) {
		rc = 1;
		goto error;
	}

	if ( !got_attrset ) {
		rc = 1;
		goto error;
	}

	if ( !got_expiry ) {
		rc = 1;
		goto error;
	}

	/* ignore expired queries */
	if ( expiry_time <= slap_get_time()) {
		Operation	op2 = *op;
		SlapReply	rs2 = { 0 };

		memset( &op2.oq_search, 0, sizeof( op2.oq_search ) );

		(void)remove_query_data( &op2, &rs2, &uuid );

		rc = 0;

	} else {
		ber_str2bv( lud->lud_dn, 0, 0, &base );
		rc = dnNormalize( 0, NULL, NULL, &base, &query.base, NULL );
		if ( rc != LDAP_SUCCESS ) {
			goto error;
		}
		query.scope = lud->lud_scope;
		query.filter = str2filter( lud->lud_filter );

		tempstr.bv_val = ch_malloc( strlen( lud->lud_filter ) + 1 );
		tempstr.bv_len = 0;
		if ( filter2template( op, query.filter, &tempstr, NULL, NULL, NULL ) ) {
			ch_free( tempstr.bv_val );
			rc = -1;
			goto error;
		}

		/* check for query containment */
		qt = qm->attr_sets[attrset].templates;
		for ( ; qt; qt = qt->qtnext ) {
			/* find if template i can potentially answer tempstr */
			if ( bvmatch( &qt->querystr, &tempstr ) ) {
				break;
			}
		}

		if ( qt == NULL ) {
			rc = 1;
			goto error;
		}

Ralf Haferkamp's avatar
Ralf Haferkamp committed
479
		cq = add_query( op, qm, &query, qt, PC_POSITIVE, 0 );
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
		if ( cq != NULL ) {
			cq->expiry_time = expiry_time;
			cq->q_uuid = uuid;

			/* it's now into cq->filter */
			BER_BVZERO( &uuid );
			query.filter = NULL;

		} else {
			rc = 1;
		}
	}

error:;
	if ( query.filter != NULL ) filter_free( query.filter );
	if ( !BER_BVISNULL( &tempstr ) ) ch_free( tempstr.bv_val );
	if ( !BER_BVISNULL( &query.base ) ) ch_free( query.base.bv_val );
	if ( !BER_BVISNULL( &uuid ) ) ch_free( uuid.bv_val );
	if ( lud != NULL ) ldap_free_urldesc( lud );

	return rc;
}
502

503
/* Return 1 for an added entry, else 0 */
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
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};

519
	slap_callback cb = { NULL, slap_null_cb, NULL, NULL };
520
521
522
523

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

524
525
	/* add queryId attribute */
	attr_merge_one( e, ad_queryId, query_uuid, NULL );
526
527
528
529
530
531
532
533
534
535
536

	/* 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
537
538
	op->o_req_dn = e->e_name;
	op->o_req_ndn = e->e_nname;
539
540
541
542
543
544
545
546
	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;
547
			op->o_bd->be_modify( op, &sreply );
548
			slap_mods_free( modlist, 1 );
549
550
551
		} else if ( rc == LDAP_REFERRAL ||
					rc == LDAP_NO_SUCH_OBJECT ) {
			syncrepl_add_glue( op, e );
Howard Chu's avatar
Howard Chu committed
552
			e = NULL;
553
554
555
556
557
			rc = 1;
		}
		if ( e ) {
			entry_free( e );
			rc = 0;
558
		}
Howard Chu's avatar
Howard Chu committed
559
	} else {
Howard Chu's avatar
Howard Chu committed
560
561
		if ( op->ora_e == e )
			be_entry_release_w( op, e );
562
		rc = 1;
563
564
	}

565
	return rc;
566
567
}

568
569
/* Length-ordered sort on normalized DNs */
static int pcache_dn_cmp( const void *v1, const void *v2 )
570
{
571
	const Qbase *q1 = v1, *q2 = v2;
572

573
574
575
576
577
	int rc = q1->base.bv_len - q2->base.bv_len;
	if ( rc == 0 )
		rc = strncmp( q1->base.bv_val, q2->base.bv_val, q1->base.bv_len );
	return rc;
}
578

Howard Chu's avatar
Howard Chu committed
579
580
581
582
583
584
585
586
587
588
589
590
static int lex_bvcmp( struct berval *bv1, struct berval *bv2 )
{
	int len, dif;
	dif = bv1->bv_len - bv2->bv_len;
	len = bv1->bv_len;
	if ( dif > 0 ) len -= dif;
	len = memcmp( bv1->bv_val, bv2->bv_val, len );
	if ( !len )
		len = dif;
	return len;
}

Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
591
592
/* compare the current value in each filter */
static int pcache_filter_cmp( Filter *f1, Filter *f2 )
593
594
{
	int rc, weight1, weight2;
595

Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
596
	switch( f1->f_choice ) {
597
598
599
600
601
602
603
	case LDAP_FILTER_PRESENT:
		weight1 = 0;
		break;
	case LDAP_FILTER_EQUALITY:
	case LDAP_FILTER_GE:
	case LDAP_FILTER_LE:
		weight1 = 1;
604
605
		break;
	default:
606
607
		weight1 = 2;
	}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
608
	switch( f2->f_choice ) {
609
610
611
612
613
614
615
	case LDAP_FILTER_PRESENT:
		weight2 = 0;
		break;
	case LDAP_FILTER_EQUALITY:
	case LDAP_FILTER_GE:
	case LDAP_FILTER_LE:
		weight2 = 1;
Howard Chu's avatar
Howard Chu committed
616
		break;
617
618
619
620
621
622
	default:
		weight2 = 2;
	}
	rc = weight1 - weight2;
	if ( !rc ) {
		switch( weight1 ) {
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
623
624
		case 0:
			break;
625
		case 1:
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
626
			rc = lex_bvcmp( &f1->f_av_value, &f2->f_av_value );
627
628
			break;
		case 2:
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
629
			if ( f1->f_choice == LDAP_FILTER_SUBSTRINGS ) {
630
				rc = 0;
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
631
632
633
634
				if ( !BER_BVISNULL( &f1->f_sub_initial )) {
					if ( !BER_BVISNULL( &f2->f_sub_initial )) {
						rc = lex_bvcmp( &f1->f_sub_initial,
							&f2->f_sub_initial );
635
636
637
					} else {
						rc = 1;
					}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
638
				} else if ( !BER_BVISNULL( &f2->f_sub_initial )) {
639
640
641
					rc = -1;
				}
				if ( rc ) break;
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
642
643
644
645
				if ( f1->f_sub_any ) {
					if ( f2->f_sub_any ) {
						rc = lex_bvcmp( f1->f_sub_any,
							f2->f_sub_any );
646
647
648
					} else {
						rc = 1;
					}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
649
				} else if ( f2->f_sub_any ) {
650
651
652
					rc = -1;
				}
				if ( rc ) break;
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
653
654
655
656
				if ( !BER_BVISNULL( &f1->f_sub_final )) {
					if ( !BER_BVISNULL( &f2->f_sub_final )) {
						rc = lex_bvcmp( &f1->f_sub_final,
							&f2->f_sub_final );
657
658
659
					} else {
						rc = 1;
					}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
660
				} else if ( !BER_BVISNULL( &f2->f_sub_final )) {
661
662
663
					rc = -1;
				}
			} else {
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
664
665
				rc = lex_bvcmp( &f1->f_mr_value,
					&f2->f_mr_value );
666
667
668
			}
			break;
		}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
		if ( !rc ) {
			f1 = f1->f_next;
			f2 = f2->f_next;
			if ( f1 || f2 ) {
				if ( !f1 )
					rc = -1;
				else if ( !f2 )
					rc = 1;
				else {
					while ( f1->f_choice == LDAP_FILTER_AND || f1->f_choice == LDAP_FILTER_OR )
						f1 = f1->f_and;
					while ( f2->f_choice == LDAP_FILTER_AND || f2->f_choice == LDAP_FILTER_OR )
						f2 = f2->f_and;
					rc = pcache_filter_cmp( f1, f2 );
				}
			}
		}
686
687
	}
	return rc;
688
689
}

Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
690
691
692
693
694
695
696
/* compare filters in each query */
static int pcache_query_cmp( const void *v1, const void *v2 )
{
	const CachedQuery *q1 = v1, *q2 =v2;
	return pcache_filter_cmp( q1->first, q2->first );
}

697
/* add query on top of LRU list */
Howard Chu's avatar
Howard Chu committed
698
699
static void
add_query_on_top (query_manager* qm, CachedQuery* qc)
700
{
Howard Chu's avatar
Howard Chu committed
701
702
703
	CachedQuery* top = qm->lru_top;

	qm->lru_top = qc;
704

Howard Chu's avatar
Howard Chu committed
705
706
	if (top)
		top->lru_up = qc;
707
	else
Howard Chu's avatar
Howard Chu committed
708
709
710
711
		qm->lru_bottom = qc;

	qc->lru_down = top;
	qc->lru_up = NULL;
Howard Chu's avatar
Howard Chu committed
712
	Debug( pcache_debug, "Base of added query = %s\n",
Howard Chu's avatar
Howard Chu committed
713
			qc->qbase->base.bv_val, 0, 0 );
714
715
716
717
}

/* remove_query from LRU list */

Howard Chu's avatar
Howard Chu committed
718
719
static void
remove_query (query_manager* qm, CachedQuery* qc)
720
{
Howard Chu's avatar
Howard Chu committed
721
722
	CachedQuery* up;
	CachedQuery* down;
723

Howard Chu's avatar
Howard Chu committed
724
725
	if (!qc)
		return;
726

Howard Chu's avatar
Howard Chu committed
727
728
	up = qc->lru_up;
	down = qc->lru_down;
729

Howard Chu's avatar
Howard Chu committed
730
731
	if (!up)
		qm->lru_top = down;
732

Howard Chu's avatar
Howard Chu committed
733
734
	if (!down)
		qm->lru_bottom = up;
735

Howard Chu's avatar
Howard Chu committed
736
737
	if (down)
		down->lru_up = up;
738

Howard Chu's avatar
Howard Chu committed
739
740
	if (up)
		up->lru_down = down;
741

Howard Chu's avatar
Howard Chu committed
742
	qc->lru_up = qc->lru_down = NULL;
743
744
}

Howard Chu's avatar
Howard Chu committed
745
746
/* find and remove string2 from string1
 * from start if position = 1,
747
748
 * from end if position = 3,
 * from anywhere if position = 2
749
 * string1 is overwritten if position = 2.
750
751
 */

Howard Chu's avatar
Howard Chu committed
752
static int
753
754
755
756
find_and_remove(struct berval* ber1, struct berval* ber2, int position)
{
	int ret=0;

757
	if ( !ber2->bv_val )
Howard Chu's avatar
Howard Chu committed
758
		return 1;
759
	if ( !ber1->bv_val )
Howard Chu's avatar
Howard Chu committed
760
		return 0;
761

762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
	switch( position ) {
	case 1:
		if ( ber1->bv_len >= ber2->bv_len && !memcmp( ber1->bv_val,
			ber2->bv_val, ber2->bv_len )) {
			ret = 1;
			ber1->bv_val += ber2->bv_len;
			ber1->bv_len -= ber2->bv_len;
		}
		break;
	case 2: {
		char *temp;
		ber1->bv_val[ber1->bv_len] = '\0';
		temp = strstr( ber1->bv_val, ber2->bv_val );
		if ( temp ) {
			strcpy( temp, temp+ber2->bv_len );
			ber1->bv_len -= ber2->bv_len;
			ret = 1;
		}
		break;
		}
	case 3:
		if ( ber1->bv_len >= ber2->bv_len &&
			!memcmp( ber1->bv_val+ber1->bv_len-ber2->bv_len, ber2->bv_val,
				ber2->bv_len )) {
			ret = 1;
			ber1->bv_len -= ber2->bv_len;
		}
		break;
790
791
792
793
794
	}
	return ret;
}


Howard Chu's avatar
Howard Chu committed
795
static struct berval*
796
797
merge_init_final(Operation *op, struct berval* init, struct berval* any,
	struct berval* final)
798
{
Howard Chu's avatar
Howard Chu committed
799
800
	struct berval* merged, *temp;
	int i, any_count, count;
801
802
803
804

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

Howard Chu's avatar
Howard Chu committed
805
	count = any_count;
806

Howard Chu's avatar
Howard Chu committed
807
808
	if (init->bv_val)
		count++;
809
	if (final->bv_val)
Howard Chu's avatar
Howard Chu committed
810
		count++;
811

812
813
	merged = (struct berval*)op->o_tmpalloc( (count+1)*sizeof(struct berval),
		op->o_tmpmemctx );
Howard Chu's avatar
Howard Chu committed
814
	temp = merged;
815
816

	if (init->bv_val) {
817
818
		ber_dupbv_x( temp, init, op->o_tmpmemctx );
		temp++;
819
820
821
	}

	for (i=0; i<any_count; i++) {
822
823
		ber_dupbv_x( temp, any, op->o_tmpmemctx );
		temp++; any++;
Howard Chu's avatar
Howard Chu committed
824
	}
825

Howard Chu's avatar
Howard Chu committed
826
	if (final->bv_val){
827
828
		ber_dupbv_x( temp, final, op->o_tmpmemctx );
		temp++;
Howard Chu's avatar
Howard Chu committed
829
	}
830
	BER_BVZERO( temp );
Howard Chu's avatar
Howard Chu committed
831
	return merged;
832
833
}

834
835
/* Each element in stored must be found in incoming. Incoming is overwritten.
 */
836
837
838
839
840
static int
strings_containment(struct berval* stored, struct berval* incoming)
{
	struct berval* element;
	int k=0;
Howard Chu's avatar
Howard Chu committed
841
842
	int j, rc = 0;

843
844
845
	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
846
847
848
				k = j;
				rc = 1;
				break;
849
			}
Howard Chu's avatar
Howard Chu committed
850
			rc = 0;
851
852
		}
		if ( rc ) {
Howard Chu's avatar
Howard Chu committed
853
			continue;
854
855
856
		} else {
			return 0;
		}
Howard Chu's avatar
Howard Chu committed
857
	}
858
859
860
861
	return 1;
}

static int
862
substr_containment_substr(Operation *op, Filter* stored, Filter* incoming)
863
864
865
866
867
{
	int rc = 0;

	struct berval init_incoming;
	struct berval final_incoming;
Howard Chu's avatar
Howard Chu committed
868
869
870
871
872
873
	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;

874
875
	init_incoming = incoming->f_sub_initial;
	final_incoming =  incoming->f_sub_final;
Howard Chu's avatar
Howard Chu committed
876
877
878
879

	if (find_and_remove(&init_incoming,
			&(stored->f_sub_initial), 1) && find_and_remove(&final_incoming,
			&(stored->f_sub_final), 3))
880
881
	{
		if (stored->f_sub_any == NULL) {
Howard Chu's avatar
Howard Chu committed
882
883
			rc = 1;
			goto final;
884
		}
885
886
		remaining_incoming = merge_init_final(op, &init_incoming,
						incoming->f_sub_any, &final_incoming);
887
		rc = strings_containment(stored->f_sub_any, remaining_incoming);
888
		ber_bvarray_free_x( remaining_incoming, op->o_tmpmemctx );
Howard Chu's avatar
Howard Chu committed
889
	}
890
final:
Howard Chu's avatar
Howard Chu committed
891
	return rc;
892
893
894
}

static int
895
substr_containment_equality(Operation *op, Filter* stored, Filter* incoming)
896
897
898
{
	struct berval incoming_val[2];
	int rc = 0;
Howard Chu's avatar
Howard Chu committed
899

900
	incoming_val[1] = incoming->f_av_value;
Howard Chu's avatar
Howard Chu committed
901

902
903
	if (find_and_remove(incoming_val+1,
			&(stored->f_sub_initial), 1) && find_and_remove(incoming_val+1,
904
			&(stored->f_sub_final), 3)) {
Howard Chu's avatar
Howard Chu committed
905
		if (stored->f_sub_any == NULL){
906
907
			rc = 1;
			goto final;
Howard Chu's avatar
Howard Chu committed
908
		}
909
910
		ber_dupbv_x( incoming_val, incoming_val+1, op->o_tmpmemctx );
		BER_BVZERO( incoming_val+1 );
911
		rc = strings_containment(stored->f_sub_any, incoming_val);
912
		op->o_tmpfree( incoming_val[0].bv_val, op->o_tmpmemctx );
913
914
915
916
917
	}
final:
	return rc;
}

918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
static Filter *
filter_first( Filter *f )
{
	while ( f->f_choice == LDAP_FILTER_OR || f->f_choice == LDAP_FILTER_AND )
		f = f->f_and;
	return f;
}


static CachedQuery *
find_filter( Operation *op, Avlnode *root, Filter *inputf, Filter *first )
{
	Filter* fs;
	Filter* fi;
	MatchingRule* mrule = NULL;
933
	int res=0, eqpass= 0;
934
935
936
937
938
939
940
941
942
943
944
945
946
947
	int ret, rc, dir;
	Avlnode *ptr;
	CachedQuery cq, *qc;

	cq.filter = inputf;
	cq.first = first;

	/* substring matches sort to the end, and we just have to
	 * walk the entire list.
	 */
	if ( first->f_choice == LDAP_FILTER_SUBSTRINGS ) {
		ptr = tavl_end( root, 1 );
		dir = TAVL_DIR_LEFT;
	} else {
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
948
		ptr = tavl_find3( root, &cq, pcache_query_cmp, &ret );
949
		dir = (first->f_choice == LDAP_FILTER_GE) ? TAVL_DIR_LEFT :
950
951
952
953
954
955
956
			TAVL_DIR_RIGHT;
	}

	while (ptr) {
		qc = ptr->avl_data;
		fi = inputf;
		fs = qc->filter;
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980

		/* an incoming substr query can only be satisfied by a cached
		 * substr query.
		 */
		if ( first->f_choice == LDAP_FILTER_SUBSTRINGS &&
			qc->first->f_choice != LDAP_FILTER_SUBSTRINGS )
			break;

		/* an incoming eq query can be satisfied by a cached eq or substr
		 * query
		 */
		if ( first->f_choice == LDAP_FILTER_EQUALITY ) {
			if ( eqpass == 0 ) {
				if ( qc->first->f_choice != LDAP_FILTER_EQUALITY ) {
nextpass:			eqpass = 1;
					ptr = tavl_end( root, 1 );
					dir = TAVL_DIR_LEFT;
					continue;
				}
			} else {
				if ( qc->first->f_choice != LDAP_FILTER_SUBSTRINGS )
					break;
			}
		}
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
		do {
			res=0;
			switch (fs->f_choice) {
			case LDAP_FILTER_EQUALITY:
				if (fi->f_choice == LDAP_FILTER_EQUALITY)
					mrule = fs->f_ava->aa_desc->ad_type->sat_equality;
				else
					ret = 1;
				break;
			case LDAP_FILTER_GE:
			case LDAP_FILTER_LE:
				mrule = fs->f_ava->aa_desc->ad_type->sat_ordering;
				break;
			default:
				mrule = NULL; 
			}
			if (mrule) {
				const char *text;
				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);
				if (rc != LDAP_SUCCESS) {
					return NULL;
				}
1006
1007
				if ( fi==first && fi->f_choice==LDAP_FILTER_EQUALITY && ret )
					goto nextpass;
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
			}
			switch (fs->f_choice) {
			case LDAP_FILTER_OR:
			case LDAP_FILTER_AND:
				fs = fs->f_and;
				fi = fi->f_and;
				res=1;
				break;
			case LDAP_FILTER_SUBSTRINGS:
				/* check if the equality query can be
				* answered with cached substring query */
				if ((fi->f_choice == LDAP_FILTER_EQUALITY)
					&& substr_containment_equality( op,
					fs, fi))
					res=1;
				/* check if the substring query can be
				* answered with cached substring query */
				if ((fi->f_choice ==LDAP_FILTER_SUBSTRINGS
					) && substr_containment_substr( op,
					fs, fi))
					res= 1;
				fs=fs->f_next;
				fi=fi->f_next;
				break;
			case LDAP_FILTER_PRESENT:
				res=1;
				fs=fs->f_next;
				fi=fi->f_next;
				break;
			case LDAP_FILTER_EQUALITY:
				if (ret == 0)
					res = 1;
				fs=fs->f_next;
				fi=fi->f_next;
				break;
			case LDAP_FILTER_GE:
				if (mrule && ret >= 0)
					res = 1;
				fs=fs->f_next;
				fi=fi->f_next;
				break;
			case LDAP_FILTER_LE:
				if (mrule && ret <= 0)
					res = 1;
				fs=fs->f_next;
				fi=fi->f_next;
				break;
			case LDAP_FILTER_NOT:
				res=0;
				break;
			default:
				break;
			}
		} while((res) && (fi != NULL) && (fs != NULL));

		if ( res )
			return qc;
		ptr = tavl_next( ptr, dir );
	}
	return NULL;
}

Howard Chu's avatar
Howard Chu committed
1070
/* check whether query is contained in any of
Howard Chu's avatar
Howard Chu committed
1071
 * the cached queries in template
1072
 */
1073
static CachedQuery *
1074
query_containment(Operation *op, query_manager *qm,
Howard Chu's avatar
Howard Chu committed
1075
		  Query *query,
Howard Chu's avatar
Howard Chu committed
1076
		  QueryTemplate *templa)
1077
1078
{
	CachedQuery* qc;
1079
1080
1081
1082
1083
1084
	int depth = 0, tscope;
	Qbase qbase, *qbptr = NULL;
	struct berval pdn;

	if (query->filter != NULL) {
		Filter *first;
1085

Howard Chu's avatar
Howard Chu committed
1086
		Debug( pcache_debug, "Lock QC index = %p\n",
1087
				(void *) templa, 0, 0 );
1088
1089
1090
1091
		qbase.base = query->base;

		first = filter_first( query->filter );

Howard Chu's avatar
Howard Chu committed
1092
		ldap_pvt_thread_rdwr_rlock(&templa->t_rwlock);
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
		for( ;; ) {
			/* Find the base */
			qbptr = avl_find( templa->qbase, &qbase, pcache_dn_cmp );
			if ( qbptr ) {
				tscope = query->scope;
				/* Find a matching scope:
				 * match at depth 0 OK
				 * scope is BASE,
				 *	one at depth 1 OK
				 *  subord at depth > 0 OK
				 *	subtree at any depth OK
				 * scope is ONE,
				 *  subtree or subord at any depth OK
				 * scope is SUBORD,
				 *  subtree or subord at any depth OK
				 * scope is SUBTREE,
				 *  subord at depth > 0 OK
				 *  subtree at any depth OK
				 */
				for ( tscope = 0 ; tscope <= LDAP_SCOPE_CHILDREN; tscope++ ) {
					switch ( query->scope ) {
					case LDAP_SCOPE_BASE:
						if ( tscope == LDAP_SCOPE_BASE && depth ) continue;
						if ( tscope == LDAP_SCOPE_ONE && depth != 1) continue;
						if ( tscope == LDAP_SCOPE_CHILDREN && !depth ) continue;
Howard Chu's avatar
Howard Chu committed
1118
						break;
1119
1120
1121
1122
1123
1124
1125
					case LDAP_SCOPE_ONE:
						if ( tscope == LDAP_SCOPE_BASE )
							tscope = LDAP_SCOPE_ONE;
						if ( tscope == LDAP_SCOPE_ONE && depth ) continue;
						if ( !depth ) break;
						if ( tscope < LDAP_SCOPE_SUBTREE )
							tscope = LDAP_SCOPE_SUBTREE;
Howard Chu's avatar
Howard Chu committed
1126
						break;
1127
1128
1129
1130
					case LDAP_SCOPE_SUBTREE:
						if ( tscope < LDAP_SCOPE_SUBTREE )
							tscope = LDAP_SCOPE_SUBTREE;
						if ( tscope == LDAP_SCOPE_CHILDREN && !depth ) continue;
Howard Chu's avatar
Howard Chu committed
1131
						break;
1132
1133
1134
					case LDAP_SCOPE_CHILDREN:
						if ( tscope < LDAP_SCOPE_SUBTREE )
							tscope = LDAP_SCOPE_SUBTREE;
1135
						break;
Howard Chu's avatar
Howard Chu committed
1136
					}
1137
1138
1139
1140
1141
1142
					if ( !qbptr->scopes[tscope] ) continue;

					/* Find filter */
					qc = find_filter( op, qbptr->scopes[tscope],
							query->filter, first );
					if ( qc ) {
Ralf Haferkamp's avatar
Ralf Haferkamp committed
1143
1144
1145
1146
						if ( qc->q_sizelimit ) {
							ldap_pvt_thread_rdwr_runlock(&templa->t_rwlock);
							return NULL;
						}
1147
1148
1149
1150
1151
1152
1153
						ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
						if (qm->lru_top != qc) {
							remove_query(qm, qc);
							add_query_on_top(qm, qc);
						}
						ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
						return qc;
1154
					}
Howard Chu's avatar
Howard Chu committed
1155
				}
1156
			}
1157
1158
1159
1160
1161
			if ( be_issuffix( op->o_bd, &qbase.base ))
				break;
			/* Up a level */
			dnParent( &qbase.base, &pdn );
			qbase.base = pdn;
Howard Chu's avatar
Howard Chu committed
1162
			depth++;
1163
		}
1164

Howard Chu's avatar
Howard Chu committed
1165
		Debug( pcache_debug,
Howard Chu's avatar
Howard Chu committed
1166
			"Not answerable: Unlock QC index=%p\n",
1167
			(void *) templa, 0, 0 );
Howard Chu's avatar
Howard Chu committed
1168
		ldap_pvt_thread_rdwr_runlock(&templa->t_rwlock);
1169
	}
1170
	return NULL;
1171
1172
}

Howard Chu's avatar
Howard Chu committed
1173
1174
static void
free_query (CachedQuery* qc)
1175
{
Howard Chu's avatar
Howard Chu committed
1176
	free(qc->q_uuid.bv_val);
1177
	filter_free(qc->filter);
1178
1179
	ldap_pvt_thread_rdwr_destroy( &qc->rwlock );
	memset(qc, 0, sizeof(*qc));
Howard Chu's avatar
Howard Chu committed
1180
	free(qc);
1181
1182
1183
}


Ralf Haferkamp's avatar
Ralf Haferkamp committed
1184
/* Add query to query cache, the returned Query is locked for writing */
1185
1186
static CachedQuery *
add_query(
Howard Chu's avatar
Howard Chu committed
1187
	Operation *op,
Howard Chu's avatar
Howard Chu committed
1188
1189
	query_manager* qm,
	Query* query,
Howard Chu's avatar
Howard Chu committed
1190
	QueryTemplate *templ,
Ralf Haferkamp's avatar
Ralf Haferkamp committed
1191
1192
	pc_caching_reason_t why,
	int wlock)
1193
1194
{
	CachedQuery* new_cached_query = (CachedQuery*) ch_malloc(sizeof(CachedQuery));
1195
	Qbase *qbase, qb;
Howard Chu's avatar
Howard Chu committed
1196
1197
	Filter *first;
	int rc;
Ralf Haferkamp's avatar
Ralf Haferkamp committed
1198
	time_t ttl = 0;;
1199

Howard Chu's avatar
Howard Chu committed
1200
	new_cached_query->qtemp = templ;
Howard Chu's avatar
Howard Chu committed
1201
	BER_BVZERO( &new_cached_query->q_uuid );
Ralf Haferkamp's avatar
Ralf Haferkamp committed
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
	new_cached_query->q_sizelimit = 0;

	switch ( why ) {
	case PC_POSITIVE:
		ttl = templ->ttl;
		break;

	case PC_NEGATIVE:
		ttl = templ->negttl;
		break;

	case PC_SIZELIMIT:
		ttl = templ->limitttl;
		break;

	default:
		assert( 0 );
		break;
1220
	}
Ralf Haferkamp's avatar
Ralf Haferkamp committed
1221
	new_cached_query->expiry_time = slap_get_time() + ttl;
Howard Chu's avatar
Howard Chu committed
1222
1223
	new_cached_query->lru_up = NULL;
	new_cached_query->lru_down = NULL;
Ralf Haferkamp's avatar
Ralf Haferkamp committed
1224
1225
1226
	Debug( pcache_debug, "Added query expires at %ld (%s)\n",
			(long) new_cached_query->expiry_time,
			pc_caching_reason_str[ why ], 0 );
1227

1228
1229
	new_cached_query->scope = query->scope;
	new_cached_query->filter = query->filter;
Howard Chu's avatar
Howard Chu committed
1230
	new_cached_query->first = first = filter_first( query->filter );
Ralf Haferkamp's avatar
Ralf Haferkamp committed
1231
1232
1233
1234
	
	ldap_pvt_thread_rdwr_init(&new_cached_query->rwlock);
	if (wlock)
		ldap_pvt_thread_rdwr_wlock(&new_cached_query->rwlock);
1235
1236

	qb.base = query->base;
1237
1238

	/* Adding a query    */
Howard Chu's avatar
Howard Chu committed
1239
	Debug( pcache_debug, "Lock AQ index = %p\n",
1240
			(void *) templ, 0, 0 );
Howard Chu's avatar
Howard Chu committed
1241
	ldap_pvt_thread_rdwr_wlock(&templ->t_rwlock);
1242
1243
1244
	qbase = avl_find( templ->qbase, &qb, pcache_dn_cmp );
	if ( !qbase ) {
		qbase = ch_calloc( 1, sizeof(Qbase) + qb.base.bv_len + 1 );
1245
		qbase->base.bv_len = qb.base.bv_len;
1246
1247
1248
1249
1250
		qbase->base.bv_val = (char *)(qbase+1);
		memcpy( qbase->base.bv_val, qb.base.bv_val, qb.base.bv_len );
		qbase->base.bv_val[qbase->base.bv_len] = '\0';
		avl_insert( &templ->qbase, qbase, pcache_dn_cmp, avl_dup_error );
	}
Howard Chu's avatar
Howard Chu committed
1251
1252
	new_cached_query->next = templ->query;
	new_cached_query->prev = NULL;
1253
	new_cached_query->qbase = qbase;
Howard Chu's avatar
Howard Chu committed
1254
	rc = tavl_insert( &qbase->scopes[query->scope], new_cached_query,
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
1255
		pcache_query_cmp, avl_dup_error );
Howard Chu's avatar
Howard Chu committed
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
	if ( rc == 0 ) {
		qbase->queries++;
		if (templ->query == NULL)
			templ->query_last = new_cached_query;
		else
			templ->query->prev = new_cached_query;
		templ->query = new_cached_query;
		templ->no_of_queries++;
	} else {
		ch_free( new_cached_query );
		new_cached_query = find_filter( op, qbase->scopes[query->scope],
							query->filter, first );
		filter_free( query->filter );
1269
		query->filter = NULL;
Howard Chu's avatar
Howard Chu committed
1270
	}
Howard Chu's avatar
Howard Chu committed
1271
	Debug( pcache_debug, "TEMPLATE %p QUERIES++ %d\n",
1272
			(void *) templ, templ->no_of_queries, 0 );
1273

Howard Chu's avatar
Howard Chu committed
1274
	Debug( pcache_debug, "Unlock AQ index = %p \n",
1275
			(void *) templ, 0, 0 );
Howard Chu's avatar
Howard Chu committed
1276
	ldap_pvt_thread_rdwr_wunlock(&templ->t_rwlock);
1277
1278

	/* Adding on top of LRU list  */
Howard Chu's avatar
Howard Chu committed
1279
1280
1281
1282
1283
1284
	if ( rc == 0 ) {
		ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
		add_query_on_top(qm, new_cached_query);
		ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
	}
	return rc == 0 ? new_cached_query : NULL;
1285
1286
1287
1288
1289
1290
}

static void
remove_from_template (CachedQuery* qc, QueryTemplate* template)
{
	if (!qc->prev && !qc->next) {
Howard Chu's avatar
Howard Chu committed
1291
		template->query_last = template->query = NULL;
1292
	} else if (qc->prev == NULL) {
Howard Chu's avatar
Howard Chu committed
1293
1294
		qc->next->prev = NULL;
		template->query = qc->next;
1295
	} else if (qc->next == NULL) {
Howard Chu's avatar
Howard Chu committed
1296
1297
		qc->prev->next = NULL;
		template->query_last = qc->prev;
1298
	} else {
Howard Chu's avatar
Howard Chu committed
1299
1300
		qc->next->prev = qc->prev;
		qc->prev->next = qc->next;
1301
	}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
1302
	tavl_delete( &qc->qbase->scopes[qc->scope], qc, pcache_query_cmp );
Howard Chu's avatar
Howard Chu committed
1303
1304
	qc->qbase->queries--;
	if ( qc->qbase->queries == 0 ) {
1305
1306
1307
1308
		avl_delete( &template->qbase, qc->qbase, pcache_dn_cmp );
		ch_free( qc->qbase );
		qc->qbase = NULL;
	}
1309

Howard Chu's avatar
Howard Chu committed
1310
	template->no_of_queries--;
1311
1312
}

Howard Chu's avatar
Howard Chu committed
1313
/* remove bottom query of LRU list from the query cache */
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
/*
 * NOTE: slight change in functionality.
 *
 * - if result->bv_val is NULL, the query at the bottom of the LRU
 *   is removed
 * - otherwise, the query whose UUID is *result is removed
 *	- if not found, result->bv_val is zeroed
 */
static void
cache_replacement(query_manager* qm, struct berval *result)
1324
{
Howard Chu's avatar
Howard Chu committed
1325
	CachedQuery* bottom;
Howard Chu's avatar
Howard Chu committed
1326
	QueryTemplate *temp;
1327

Howard Chu's avatar