pcache.c 99.8 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-2008 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 */
185
	int 	numattrsets;			/* number of attribute sets */
Howard Chu's avatar
Howard Chu committed
186
187
	int 	cur_entries;			/* current number of entries cached */
	int 	max_entries;			/* max number of entries cached */
Howard Chu's avatar
Howard Chu committed
188
	int 	num_entries_limit;		/* max # of entries in a cacheable query */
189

190
191
192
193
	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
194
	char	defer_db_open;			/* defer open for online add */
195

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

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

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

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

207
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
#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
250
251
	pc_caching_reason_t why,
	int wlock);
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
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

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;
	char		attrset_buf[ 32 ],
			expiry_buf[ 32 ],
			*ptr;
	ber_len_t	attrset_len,
			expiry_len;

	ldap_pvt_scope2bv( q->scope, &bv_scope );
	filter2bv_x( op, q->filter, &bv_filter );
	attrset_len = snprintf( attrset_buf, sizeof( attrset_buf ),
		"%lu", (unsigned long)q->qtemp->attr_set_index );
	expiry_len = snprintf( expiry_buf, sizeof( expiry_buf ),
		"%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
478
		cq = add_query( op, qm, &query, qt, PC_POSITIVE, 0 );
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
		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;
}
501

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

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

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

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

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

564
	return rc;
565
566
}

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

572
573
574
575
576
	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;
}
577

Howard Chu's avatar
Howard Chu committed
578
579
580
581
582
583
584
585
586
587
588
589
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;
}

590
591
592
593
594
/* compare the first value in each filter */
static int pcache_filter_cmp( const void *v1, const void *v2 )
{
	const CachedQuery *q1 = v1, *q2 =v2;
	int rc, weight1, weight2;
595

596
597
598
599
600
601
602
603
	switch( q1->first->f_choice ) {
	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
608
609
610
611
612
613
614
615
		weight1 = 2;
	}
	switch( q2->first->f_choice ) {
	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
623
624
	default:
		weight2 = 2;
	}
	rc = weight1 - weight2;
	if ( !rc ) {
		switch( weight1 ) {
		case 0:	return 0;
		case 1:
Howard Chu's avatar
Howard Chu committed
625
			rc = lex_bvcmp( &q1->first->f_av_value, &q2->first->f_av_value );
626
627
628
629
630
631
			break;
		case 2:
			if ( q1->first->f_choice == LDAP_FILTER_SUBSTRINGS ) {
				rc = 0;
				if ( !BER_BVISNULL( &q1->first->f_sub_initial )) {
					if ( !BER_BVISNULL( &q2->first->f_sub_initial )) {
Howard Chu's avatar
Howard Chu committed
632
						rc = lex_bvcmp( &q1->first->f_sub_initial,
633
634
635
636
637
638
639
640
641
642
							&q2->first->f_sub_initial );
					} else {
						rc = 1;
					}
				} else if ( !BER_BVISNULL( &q2->first->f_sub_initial )) {
					rc = -1;
				}
				if ( rc ) break;
				if ( q1->first->f_sub_any ) {
					if ( q2->first->f_sub_any ) {
Howard Chu's avatar
Howard Chu committed
643
						rc = lex_bvcmp( q1->first->f_sub_any,
644
645
646
647
648
649
650
651
652
653
							q2->first->f_sub_any );
					} else {
						rc = 1;
					}
				} else if ( q2->first->f_sub_any ) {
					rc = -1;
				}
				if ( rc ) break;
				if ( !BER_BVISNULL( &q1->first->f_sub_final )) {
					if ( !BER_BVISNULL( &q2->first->f_sub_final )) {
Howard Chu's avatar
Howard Chu committed
654
						rc = lex_bvcmp( &q1->first->f_sub_final,
655
656
657
658
659
660
661
662
							&q2->first->f_sub_final );
					} else {
						rc = 1;
					}
				} else if ( !BER_BVISNULL( &q2->first->f_sub_final )) {
					rc = -1;
				}
			} else {
Howard Chu's avatar
Howard Chu committed
663
				rc = lex_bvcmp( &q1->first->f_mr_value,
664
665
666
667
668
669
670
					&q2->first->f_mr_value );
			}
			break;
		}
	}

	return rc;
671
672
673
}

/* add query on top of LRU list */
Howard Chu's avatar
Howard Chu committed
674
675
static void
add_query_on_top (query_manager* qm, CachedQuery* qc)
676
{
Howard Chu's avatar
Howard Chu committed
677
678
679
	CachedQuery* top = qm->lru_top;

	qm->lru_top = qc;
680

Howard Chu's avatar
Howard Chu committed
681
682
	if (top)
		top->lru_up = qc;
683
	else
Howard Chu's avatar
Howard Chu committed
684
685
686
687
		qm->lru_bottom = qc;

	qc->lru_down = top;
	qc->lru_up = NULL;
Howard Chu's avatar
Howard Chu committed
688
	Debug( pcache_debug, "Base of added query = %s\n",
Howard Chu's avatar
Howard Chu committed
689
			qc->qbase->base.bv_val, 0, 0 );
690
691
692
693
}

/* remove_query from LRU list */

Howard Chu's avatar
Howard Chu committed
694
695
static void
remove_query (query_manager* qm, CachedQuery* qc)
696
{
Howard Chu's avatar
Howard Chu committed
697
698
	CachedQuery* up;
	CachedQuery* down;
699

Howard Chu's avatar
Howard Chu committed
700
701
	if (!qc)
		return;
702

Howard Chu's avatar
Howard Chu committed
703
704
	up = qc->lru_up;
	down = qc->lru_down;
705

Howard Chu's avatar
Howard Chu committed
706
707
	if (!up)
		qm->lru_top = down;
708

Howard Chu's avatar
Howard Chu committed
709
710
	if (!down)
		qm->lru_bottom = up;
711

Howard Chu's avatar
Howard Chu committed
712
713
	if (down)
		down->lru_up = up;
714

Howard Chu's avatar
Howard Chu committed
715
716
	if (up)
		up->lru_down = down;
717

Howard Chu's avatar
Howard Chu committed
718
	qc->lru_up = qc->lru_down = NULL;
719
720
}

Howard Chu's avatar
Howard Chu committed
721
722
/* find and remove string2 from string1
 * from start if position = 1,
723
724
 * from end if position = 3,
 * from anywhere if position = 2
725
 * string1 is overwritten if position = 2.
726
727
 */

Howard Chu's avatar
Howard Chu committed
728
static int
729
730
731
732
find_and_remove(struct berval* ber1, struct berval* ber2, int position)
{
	int ret=0;

733
	if ( !ber2->bv_val )
Howard Chu's avatar
Howard Chu committed
734
		return 1;
735
	if ( !ber1->bv_val )
Howard Chu's avatar
Howard Chu committed
736
		return 0;
737

738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
	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;
766
767
768
769
770
	}
	return ret;
}


Howard Chu's avatar
Howard Chu committed
771
static struct berval*
772
773
merge_init_final(Operation *op, struct berval* init, struct berval* any,
	struct berval* final)
774
{
Howard Chu's avatar
Howard Chu committed
775
776
	struct berval* merged, *temp;
	int i, any_count, count;
777
778
779
780

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

Howard Chu's avatar
Howard Chu committed
781
	count = any_count;
782

Howard Chu's avatar
Howard Chu committed
783
784
	if (init->bv_val)
		count++;
785
	if (final->bv_val)
Howard Chu's avatar
Howard Chu committed
786
		count++;
787

788
789
	merged = (struct berval*)op->o_tmpalloc( (count+1)*sizeof(struct berval),
		op->o_tmpmemctx );
Howard Chu's avatar
Howard Chu committed
790
	temp = merged;
791
792

	if (init->bv_val) {
793
794
		ber_dupbv_x( temp, init, op->o_tmpmemctx );
		temp++;
795
796
797
	}

	for (i=0; i<any_count; i++) {
798
799
		ber_dupbv_x( temp, any, op->o_tmpmemctx );
		temp++; any++;
Howard Chu's avatar
Howard Chu committed
800
	}
801

Howard Chu's avatar
Howard Chu committed
802
	if (final->bv_val){
803
804
		ber_dupbv_x( temp, final, op->o_tmpmemctx );
		temp++;
Howard Chu's avatar
Howard Chu committed
805
	}
806
	BER_BVZERO( temp );
Howard Chu's avatar
Howard Chu committed
807
	return merged;
808
809
}

810
811
/* Each element in stored must be found in incoming. Incoming is overwritten.
 */
812
813
814
815
816
static int
strings_containment(struct berval* stored, struct berval* incoming)
{
	struct berval* element;
	int k=0;
Howard Chu's avatar
Howard Chu committed
817
818
	int j, rc = 0;

819
820
821
	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
822
823
824
				k = j;
				rc = 1;
				break;
825
			}
Howard Chu's avatar
Howard Chu committed
826
			rc = 0;
827
828
		}
		if ( rc ) {
Howard Chu's avatar
Howard Chu committed
829
			continue;
830
831
832
		} else {
			return 0;
		}
Howard Chu's avatar
Howard Chu committed
833
	}
834
835
836
837
	return 1;
}

static int
838
substr_containment_substr(Operation *op, Filter* stored, Filter* incoming)
839
840
841
842
843
{
	int rc = 0;

	struct berval init_incoming;
	struct berval final_incoming;
Howard Chu's avatar
Howard Chu committed
844
845
846
847
848
849
	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;

850
851
	init_incoming = incoming->f_sub_initial;
	final_incoming =  incoming->f_sub_final;
Howard Chu's avatar
Howard Chu committed
852
853
854
855

	if (find_and_remove(&init_incoming,
			&(stored->f_sub_initial), 1) && find_and_remove(&final_incoming,
			&(stored->f_sub_final), 3))
856
857
	{
		if (stored->f_sub_any == NULL) {
Howard Chu's avatar
Howard Chu committed
858
859
			rc = 1;
			goto final;
860
		}
861
862
		remaining_incoming = merge_init_final(op, &init_incoming,
						incoming->f_sub_any, &final_incoming);
863
		rc = strings_containment(stored->f_sub_any, remaining_incoming);
864
		ber_bvarray_free_x( remaining_incoming, op->o_tmpmemctx );
Howard Chu's avatar
Howard Chu committed
865
	}
866
final:
Howard Chu's avatar
Howard Chu committed
867
	return rc;
868
869
870
}

static int
871
substr_containment_equality(Operation *op, Filter* stored, Filter* incoming)
872
873
874
{
	struct berval incoming_val[2];
	int rc = 0;
Howard Chu's avatar
Howard Chu committed
875

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

878
879
	if (find_and_remove(incoming_val+1,
			&(stored->f_sub_initial), 1) && find_and_remove(incoming_val+1,
880
			&(stored->f_sub_final), 3)) {
Howard Chu's avatar
Howard Chu committed
881
		if (stored->f_sub_any == NULL){
882
883
			rc = 1;
			goto final;
Howard Chu's avatar
Howard Chu committed
884
		}
885
886
		ber_dupbv_x( incoming_val, incoming_val+1, op->o_tmpmemctx );
		BER_BVZERO( incoming_val+1 );
887
		rc = strings_containment(stored->f_sub_any, incoming_val);
888
		op->o_tmpfree( incoming_val[0].bv_val, op->o_tmpmemctx );
889
890
891
892
893
	}
final:
	return rc;
}

894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
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;
909
	int res=0, eqpass= 0;
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
	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 {
		ptr = tavl_find3( root, &cq, pcache_filter_cmp, &ret );
925
		dir = (first->f_choice == LDAP_FILTER_GE) ? TAVL_DIR_LEFT :
926
927
928
929
930
931
932
			TAVL_DIR_RIGHT;
	}

	while (ptr) {
		qc = ptr->avl_data;
		fi = inputf;
		fs = qc->filter;
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956

		/* 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;
			}
		}
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
		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;
				}
982
983
				if ( fi==first && fi->f_choice==LDAP_FILTER_EQUALITY && ret )
					goto nextpass;
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
			}
			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 */
For faster browsing, not all history is shown. View entire blame