pcache.c 141 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
 * Portions Copyright 2003 IBM Corporation.
6
 * Portions Copyright 2003-2009 Symas Corporation.
7
8
9
10
11
12
13
14
15
16
17
18
 * 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 "../back-monitor/back-monitor.h"

38
39
#include "config.h"

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"
51
52
53
54
55

/*
 * Monitoring
 */
#define PCACHE_MONITOR
56
57
#endif

58
59
60
61
62
63
64
65
66
/* 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
67
68
struct query_template_s;

69
70
71
typedef struct Qbase_s {
	Avlnode *scopes[4];		/* threaded AVL trees of cached queries */
	struct berval base;
Howard Chu's avatar
Howard Chu committed
72
	int queries;
73
74
} Qbase;

75
76
/* struct representing a cached query */
typedef struct cached_query_s {
77
78
79
80
	Filter					*filter;
	Filter					*first;
	Qbase					*qbase;
	int						scope;
Howard Chu's avatar
Howard Chu committed
81
	struct berval			q_uuid;		/* query identifier */
Ralf Haferkamp's avatar
Ralf Haferkamp committed
82
	int						q_sizelimit;
83
	struct query_template_s		*qtemp;	/* template of the query */
84
85
86
	time_t						expiry_time;	/* time till the query is considered invalid */
	time_t						refresh_time;	/* time till the query is refreshed */
	time_t						bindref_time;	/* time till the bind is refreshed */
87
	unsigned long			answerable_cnt; /* how many times it was answerable */
88
	int						refcnt;	/* references since last refresh */
89
	ldap_pvt_thread_mutex_t		answerable_cnt_mutex;
90
91
	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
92
93
94
	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
95
} CachedQuery;
96

97
98
99
/*
 * URL representation:
 *
100
 * ldap:///<base>??<scope>?<filter>?x-uuid=<uid>,x-template=<template>,x-attrset=<attrset>,x-expiry=<expiry>,x-refresh=<refresh>
101
102
103
104
105
106
107
 *
 * <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
108
 * <refresh> ::= CachedQuery.refresh_time
109
110
111
 *
 * quick hack: parse URI, call add_query() and then fix
 * CachedQuery.expiry_time and CachedQuery.q_uuid
112
113
 *
 * NOTE: if the <attrset> changes, all stored URLs will be invalidated.
114
115
 */

Howard Chu's avatar
Howard Chu committed
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*
 * 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 */
};

130
/* struct representing a query template
Howard Chu's avatar
Howard Chu committed
131
 * e.g. template string = &(cn=)(mail=)
132
133
 */
typedef struct query_template_s {
Howard Chu's avatar
Howard Chu committed
134
135
	struct query_template_s *qtnext;
	struct query_template_s *qmnext;
136

137
	Avlnode*		qbase;
Howard Chu's avatar
Howard Chu committed
138
139
	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
140
	ldap_pvt_thread_rdwr_t t_rwlock; /* Rd/wr lock for accessing queries in the template */
Howard Chu's avatar
Howard Chu committed
141
	struct berval	querystr;	/* Filter string corresponding to the QT */
142
143
144
145
146
147
148
149
	struct berval	bindbase;	/* base DN for Bind request */
	struct berval	bindfilterstr;	/* Filter string for Bind request */
	struct berval	bindftemp;	/* bind filter template */
	Filter		*bindfilter;
	AttributeDescription **bindfattrs;	/* attrs to substitute in ftemp */

	int			bindnattrs;		/* number of bindfattrs */
	int			bindscope;
Howard Chu's avatar
Howard Chu committed
150
	int 		attr_set_index; /* determines the projected attributes */
151
	int 		no_of_queries;  /* Total number of queries in the template */
152
	time_t		ttl;		/* TTL for the queries of this template */
153
	time_t		negttl;		/* TTL for negative results */
Ralf Haferkamp's avatar
Ralf Haferkamp committed
154
	time_t		limitttl;	/* TTL for sizelimit exceeding results */
155
156
	time_t		ttr;	/* time to refresh */
	time_t		bindttr;	/* TTR for cached binds */
Howard Chu's avatar
Howard Chu committed
157
	struct attr_set t_attrs;	/* filter attrs + attr_set */
158
159
} QueryTemplate;

Ralf Haferkamp's avatar
Ralf Haferkamp committed
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
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
176
struct query_manager_s;
177

Howard Chu's avatar
Howard Chu committed
178
179
/* prototypes for functions for 1) query containment
 * 2) query addition, 3) cache replacement
180
 */
Ralf Haferkamp's avatar
Ralf Haferkamp committed
181
182
183
184
185
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*);
186

Howard Chu's avatar
Howard Chu committed
187
/* LDAP query cache */
188
189
190
191
192
193
194
195
196
197
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
198
	QCfunc			*qcfunc;			/* Query containment*/
199
	CRfunc 			*crfunc;			/* cache replacement */
Howard Chu's avatar
Howard Chu committed
200
201
	AddQueryfunc	*addfunc;			/* add query */
} query_manager;
202

Howard Chu's avatar
Howard Chu committed
203
/* LDAP query cache manager */
204
typedef struct cache_manager_s {
205
	BackendDB	db;	/* underlying database */
206
	unsigned long	num_cached_queries; 		/* total number of cached queries */
Howard Chu's avatar
Howard Chu committed
207
	unsigned long   max_queries;			/* upper bound on # of cached queries */
208
	int		save_queries;			/* save cached queries across restarts */
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
209
	int	check_cacheability;		/* check whether a query is cacheable */
210
	int 	numattrsets;			/* number of attribute sets */
Howard Chu's avatar
Howard Chu committed
211
212
	int 	cur_entries;			/* current number of entries cached */
	int 	max_entries;			/* max number of entries cached */
Howard Chu's avatar
Howard Chu committed
213
	int 	num_entries_limit;		/* max # of entries in a cacheable query */
214

215
216
217
218
	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
219
	char	defer_db_open;			/* defer open for online add */
220
	char	cache_binds;			/* cache binds or just passthru */
221

222
	time_t	cc_period;		/* interval between successive consistency checks (sec) */
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
223
224
#define PCACHE_CC_PAUSED	1
#define PCACHE_CC_OFFLINE	2
Howard Chu's avatar
Howard Chu committed
225
	int 	cc_paused;
226
	void	*cc_arg;
227

Howard Chu's avatar
Howard Chu committed
228
	ldap_pvt_thread_mutex_t		cache_mutex;
229

Howard Chu's avatar
Howard Chu committed
230
	query_manager*   qm;	/* query cache managed by the cache manager */
231
232
233
234
235

#ifdef PCACHE_MONITOR
	void		*monitor_cb;
	struct berval	monitor_ndn;
#endif /* PCACHE_MONITOR */
Howard Chu's avatar
Howard Chu committed
236
} cache_manager;
237

238
239
240
241
242
243
244
#ifdef PCACHE_MONITOR
static int pcache_monitor_db_init( BackendDB *be );
static int pcache_monitor_db_open( BackendDB *be );
static int pcache_monitor_db_close( BackendDB *be );
static int pcache_monitor_db_destroy( BackendDB *be );
#endif /* PCACHE_MONITOR */

Howard Chu's avatar
Howard Chu committed
245
246
static int pcache_debug;

247
248
249
250
#ifdef PCACHE_CONTROL_PRIVDB
static int privDB_cid;
#endif /* PCACHE_CONTROL_PRIVDB */

251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
static AttributeDescription	*ad_queryId, *ad_cachedQueryURL;

#ifdef PCACHE_MONITOR
static AttributeDescription	*ad_numQueries, *ad_numEntries;
static ObjectClass		*oc_olmPCache;
#endif /* PCACHE_MONITOR */

static struct {
	char			*name;
	char			*oid;
}		s_oid[] = {
	{ "PCacheOID",			"1.3.6.1.4.1.4203.666.11.9.1" },
	{ "PCacheAttributes",		"PCacheOID:1" },
	{ "PCacheObjectClasses",	"PCacheOID:2" },

	{ NULL }
};

269
270
271
static struct {
	char	*desc;
	AttributeDescription **adp;
272
273
274
} s_ad[] = {
	{ "( PCacheAttributes:1 "
		"NAME 'pcacheQueryID' "
275
276
277
278
279
280
		"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 },
281
282
	{ "( PCacheAttributes:2 "
		"NAME 'pcacheQueryURL' "
283
284
285
286
287
288
		"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 },
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
#ifdef PCACHE_MONITOR
	{ "( PCacheAttributes:3 "
		"NAME 'pcacheNumQueries' "
		"DESC 'Number of cached queries' "
		"EQUALITY integerMatch "
		"SYNTAX 1.3.6.1.4.1.1466.115.121.1.27 "
		"NO-USER-MODIFICATION "
		"USAGE directoryOperation )",
		&ad_numQueries },
	{ "( PCacheAttributes:4 "
		"NAME 'pcacheNumEntries' "
		"DESC 'Number of cached entries' "
		"EQUALITY integerMatch "
		"SYNTAX 1.3.6.1.4.1.1466.115.121.1.27 "
		"NO-USER-MODIFICATION "
		"USAGE directoryOperation )",
		&ad_numEntries },
#endif /* PCACHE_MONITOR */

	{ NULL }
};

static struct {
	char		*desc;
	ObjectClass	**ocp;
}		s_oc[] = {
#ifdef PCACHE_MONITOR
	/* augments an existing object, so it must be AUXILIARY */
	{ "( PCacheObjectClasses:1 "
		"NAME ( 'olmPCache' ) "
		"SUP top AUXILIARY "
		"MAY ( "
			"pcacheQueryURL "
			"$ pcacheNumQueries "
			"$ pcacheNumEntries "
			" ) )",
		&oc_olmPCache },
#endif /* PCACHE_MONITOR */

328
329
330
331
332
333
334
	{ NULL }
};

static int
filter2template(
	Operation		*op,
	Filter			*f,
335
	struct			berval *fstr );
336
337
338
339
340
341
342

static CachedQuery *
add_query(
	Operation *op,
	query_manager* qm,
	Query* query,
	QueryTemplate *templ,
Ralf Haferkamp's avatar
Ralf Haferkamp committed
343
344
	pc_caching_reason_t why,
	int wlock);
345
346
347
348
349
350
351
352
353
354
355

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

/*
 * Turn a cached query into its URL representation
 */
static int
356
query2url( Operation *op, CachedQuery *q, struct berval *urlbv, int dolock )
357
358
359
{
	struct berval	bv_scope,
			bv_filter;
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
360
361
	char		attrset_buf[ LDAP_PVT_INTTYPE_CHARS( unsigned long ) ],
			expiry_buf[ LDAP_PVT_INTTYPE_CHARS( unsigned long ) ],
362
			refresh_buf[ LDAP_PVT_INTTYPE_CHARS( unsigned long ) ],
363
			answerable_buf[ LDAP_PVT_INTTYPE_CHARS( unsigned long ) ],
364
365
			*ptr;
	ber_len_t	attrset_len,
366
			expiry_len,
367
			refresh_len,
368
369
370
371
372
			answerable_len;

	if ( dolock ) {
		ldap_pvt_thread_rdwr_rlock( &q->rwlock );
	}
373
374
375

	ldap_pvt_scope2bv( q->scope, &bv_scope );
	filter2bv_x( op, q->filter, &bv_filter );
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
376
	attrset_len = sprintf( attrset_buf,
377
		"%lu", (unsigned long)q->qtemp->attr_set_index );
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
378
	expiry_len = sprintf( expiry_buf,
379
		"%lu", (unsigned long)q->expiry_time );
380
381
	answerable_len = snprintf( answerable_buf, sizeof( answerable_buf ),
		"%lu", q->answerable_cnt );
382
383
384
385
386
	if ( q->refresh_time )
		refresh_len = sprintf( refresh_buf,
			"%lu", (unsigned long)q->refresh_time );
	else
		refresh_len = 0;
387
388
389
390
391
392
393
394
395
396
397
398

	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=" )
399
400
401
		+ expiry_len
		+ STRLENOF( ",x-answerable=" )
		+ answerable_len;
402
403
404
405
	if ( refresh_len )
		urlbv->bv_len += STRLENOF( ",x-refresh=" )
		+ refresh_len;

406
407
408
409
410
411
412
413
414
415
416
417
418
	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 );
419
420
	ptr = lutil_strcopy( ptr, ",x-answerable=" );
	ptr = lutil_strcopy( ptr, answerable_buf );
421
422
423
424
	if ( refresh_len ) {
		ptr = lutil_strcopy( ptr, ",x-refresh=" );
		ptr = lutil_strcopy( ptr, refresh_buf );
	}
425
426
427

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

428
429
430
431
	if ( dolock ) {
		ldap_pvt_thread_rdwr_runlock( &q->rwlock );
	}

432
433
434
	return 0;
}

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
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
/* Find and record the empty filter clauses */

static int
ftemp_attrs( struct berval *ftemp, struct berval *template,
	AttributeDescription ***ret, const char **text )
{
	int i;
	int attr_cnt=0;
	struct berval bv;
	char *p1, *p2, *t1;
	AttributeDescription *ad;
	AttributeDescription **descs = NULL;
	char *temp2;

	temp2 = ch_malloc( ftemp->bv_len );
	p1 = ftemp->bv_val;
	t1 = temp2;

	*ret = NULL;

	for (;;) {
		while ( *p1 == '(' || *p1 == '&' || *p1 == '|' || *p1 == ')' )
			*t1++ = *p1++;

		p2 = strchr( p1, '=' );
		if ( !p2 )
			break;
		i = p2 - p1;
		AC_MEMCPY( t1, p1, i );
		t1 += i;
		*t1++ = '=';

		if ( p2[-1] == '<' || p2[-1] == '>' ) p2--;
		bv.bv_val = p1;
		bv.bv_len = p2 - p1;
		ad = NULL;
		i = slap_bv2ad( &bv, &ad, text );
		if ( i ) {
			ch_free( descs );
			return -1;
		}
		if ( *p2 == '<' || *p2 == '>' ) p2++;
		if ( p2[1] != ')' ) {
			p2++;
			while ( *p2 != ')' ) p2++;
			p1 = p2;
			continue;
		}

		descs = (AttributeDescription **)ch_realloc(descs,
				(attr_cnt + 2)*sizeof(AttributeDescription *));

		descs[attr_cnt++] = ad;

		p1 = p2+1;
	}
	*t1 = '\0';
	descs[attr_cnt] = NULL;
	*ret = descs;
	template->bv_val = temp2;
	template->bv_len = t1 - temp2;
	return attr_cnt;
}

static int
template_attrs( char *template, struct attr_set *set, AttributeName **ret,
	const char **text )
{
	int got_oc = 0;
	int alluser = 0;
	int allop = 0;
	int i;
	int attr_cnt;
	int t_cnt = 0;
	struct berval bv;
	char *p1, *p2;
	AttributeDescription *ad;
	AttributeName *attrs;

	p1 = template;

	*ret = NULL;

	attrs = ch_calloc( set->count + 1, sizeof(AttributeName) );
	for ( i=0; i < set->count; i++ )
		attrs[i] = set->attrs[i];
	attr_cnt = i;
	alluser = an_find( attrs, slap_bv_all_user_attrs );
	allop = an_find( attrs, slap_bv_all_operational_attrs );

	for (;;) {
		while ( *p1 == '(' || *p1 == '&' || *p1 == '|' || *p1 == ')' ) p1++;
		p2 = strchr( p1, '=' );
		if ( !p2 )
			break;
		if ( p2[-1] == '<' || p2[-1] == '>' ) p2--;
		bv.bv_val = p1;
		bv.bv_len = p2 - p1;
		ad = NULL;
		i = slap_bv2ad( &bv, &ad, text );
		if ( i ) {
			ch_free( attrs );
			return -1;
		}
		t_cnt++;

		if ( ad == slap_schema.si_ad_objectClass )
			got_oc = 1;

		if ( is_at_operational(ad->ad_type)) {
			if ( allop ) {
				goto bottom;
			}
		} else if ( alluser ) {
			goto bottom;
		}
		if ( !ad_inlist( ad, attrs )) {
			attrs = (AttributeName *)ch_realloc(attrs,
					(attr_cnt + 2)*sizeof(AttributeName));

			attrs[attr_cnt].an_desc = ad;
			attrs[attr_cnt].an_name = ad->ad_cname;
			attrs[attr_cnt].an_oc = NULL;
			attrs[attr_cnt].an_flags = 0;
			BER_BVZERO( &attrs[attr_cnt+1].an_name );
			attr_cnt++;
		}

bottom:
		p1 = p2+2;
	}
	if ( !t_cnt ) {
		*text = "couldn't parse template";
		return -1;
	}
	if ( !got_oc && !( set->flags & PC_GOT_OC )) {
		attrs = (AttributeName *)ch_realloc(attrs,
				(attr_cnt + 2)*sizeof(AttributeName));

		ad = slap_schema.si_ad_objectClass;
		attrs[attr_cnt].an_desc = ad;
		attrs[attr_cnt].an_name = ad->ad_cname;
		attrs[attr_cnt].an_oc = NULL;
		attrs[attr_cnt].an_flags = 0;
		BER_BVZERO( &attrs[attr_cnt+1].an_name );
		attr_cnt++;
	}
	*ret = attrs;
	return attr_cnt;
}

586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
/*
 * 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;
605
	time_t		refresh_time;
606
	unsigned long	answerable_cnt;
607
	int		i,
608
609
610
611
612
			got = 0,
#define GOT_UUID	0x1U
#define GOT_ATTRSET	0x2U
#define GOT_EXPIRY	0x4U
#define GOT_ANSWERABLE	0x8U
613
#define GOT_REFRESH	0x10U
614
#define GOT_ALL		(GOT_UUID|GOT_ATTRSET|GOT_EXPIRY|GOT_ANSWERABLE)
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
			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;

672
673
674
675
676
			if ( got & GOT_UUID ) {
				rc = 1;
				goto error;
			}

677
678
679
680
681
			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;
			}
682
			got |= GOT_UUID;
683
684

		} else if ( strncmp( lud->lud_exts[ i ], "x-attrset=", STRLENOF( "x-attrset=" ) ) == 0 ) {
685
686
687
688
689
			if ( got & GOT_ATTRSET ) {
				rc = 1;
				goto error;
			}

690
691
692
693
			rc = lutil_atoi( &attrset, &lud->lud_exts[ i ][ STRLENOF( "x-attrset=" ) ] );
			if ( rc ) {
				goto error;
			}
694
			got |= GOT_ATTRSET;
695
696
697
698

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

699
700
701
702
703
			if ( got & GOT_EXPIRY ) {
				rc = 1;
				goto error;
			}

704
705
706
707
708
			rc = lutil_atoul( &l, &lud->lud_exts[ i ][ STRLENOF( "x-expiry=" ) ] );
			if ( rc ) {
				goto error;
			}
			expiry_time = (time_t)l;
709
710
711
712
713
714
715
716
717
718
719
720
721
			got |= GOT_EXPIRY;

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

			rc = lutil_atoul( &answerable_cnt, &lud->lud_exts[ i ][ STRLENOF( "x-answerable=" ) ] );
			if ( rc ) {
				goto error;
			}
			got |= GOT_ANSWERABLE;
722

723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
		} else if ( strncmp( lud->lud_exts[ i ], "x-refresh=", STRLENOF( "x-refresh=" ) ) == 0 ) {
			unsigned long l;

			if ( got & GOT_REFRESH ) {
				rc = 1;
				goto error;
			}

			rc = lutil_atoul( &l, &lud->lud_exts[ i ][ STRLENOF( "x-refresh=" ) ] );
			if ( rc ) {
				goto error;
			}
			refresh_time = (time_t)l;
			got |= GOT_REFRESH;

738
739
740
741
742
743
		} else {
			rc = -1;
			goto error;
		}
	}

744
	if ( got != GOT_ALL ) {
745
746
747
748
		rc = 1;
		goto error;
	}

749
750
751
	if ( !(got & GOT_REFRESH ))
		refresh_time = 0;

752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
	/* 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;
774
		if ( filter2template( op, query.filter, &tempstr ) ) {
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
			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
794
		cq = add_query( op, qm, &query, qt, PC_POSITIVE, 0 );
795
796
		if ( cq != NULL ) {
			cq->expiry_time = expiry_time;
797
			cq->refresh_time = refresh_time;
798
			cq->q_uuid = uuid;
799
			cq->answerable_cnt = answerable_cnt;
800
			cq->refcnt = 0;
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819

			/* 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;
}
820

821
/* Return 1 for an added entry, else 0 */
822
823
824
825
static int
merge_entry(
	Operation		*op,
	Entry			*e,
826
	int			dup,
827
828
829
830
831
832
833
834
835
836
837
	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};

838
	slap_callback cb = { NULL, slap_null_cb, NULL, NULL };
839

840
841
	if ( dup )
		e = entry_dup( e );
842
843
844
	attr = e->e_attrs;
	e->e_attrs = NULL;

845
846
	/* add queryId attribute */
	attr_merge_one( e, ad_queryId, query_uuid, NULL );
847
848
849
850
851
852
853
854
855
856
857

	/* 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
858
859
	op->o_req_dn = e->e_name;
	op->o_req_ndn = e->e_nname;
860
861
862
863
864
865
866
867
	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;
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
868
			op->o_managedsait = SLAP_CONTROL_CRITICAL;
869
			op->o_bd->be_modify( op, &sreply );
870
			slap_mods_free( modlist, 1 );
871
872
873
		} else if ( rc == LDAP_REFERRAL ||
					rc == LDAP_NO_SUCH_OBJECT ) {
			syncrepl_add_glue( op, e );
Howard Chu's avatar
Howard Chu committed
874
			e = NULL;
875
876
877
878
879
			rc = 1;
		}
		if ( e ) {
			entry_free( e );
			rc = 0;
880
		}
Howard Chu's avatar
Howard Chu committed
881
	} else {
Howard Chu's avatar
Howard Chu committed
882
		if ( op->ora_e == e )
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
883
			entry_free( e );
884
		rc = 1;
885
886
	}

887
	return rc;
888
889
}

890
891
/* Length-ordered sort on normalized DNs */
static int pcache_dn_cmp( const void *v1, const void *v2 )
892
{
893
	const Qbase *q1 = v1, *q2 = v2;
894

895
896
897
898
899
	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;
}
900

Howard Chu's avatar
Howard Chu committed
901
902
903
904
905
906
907
908
909
910
911
912
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
913
914
/* compare the current value in each filter */
static int pcache_filter_cmp( Filter *f1, Filter *f2 )
915
916
{
	int rc, weight1, weight2;
917

Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
918
	switch( f1->f_choice ) {
919
920
921
922
923
924
925
	case LDAP_FILTER_PRESENT:
		weight1 = 0;
		break;
	case LDAP_FILTER_EQUALITY:
	case LDAP_FILTER_GE:
	case LDAP_FILTER_LE:
		weight1 = 1;
926
927
		break;
	default:
928
929
		weight1 = 2;
	}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
930
	switch( f2->f_choice ) {
931
932
933
934
935
936
937
	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
938
		break;
939
940
941
942
943
944
	default:
		weight2 = 2;
	}
	rc = weight1 - weight2;
	if ( !rc ) {
		switch( weight1 ) {
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
945
946
		case 0:
			break;
947
		case 1:
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
948
			rc = lex_bvcmp( &f1->f_av_value, &f2->f_av_value );
949
950
			break;
		case 2:
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
951
			if ( f1->f_choice == LDAP_FILTER_SUBSTRINGS ) {
952
				rc = 0;
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
953
954
955
956
				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 );
957
958
959
					} else {
						rc = 1;
					}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
960
				} else if ( !BER_BVISNULL( &f2->f_sub_initial )) {
961
962
963
					rc = -1;
				}
				if ( rc ) break;
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
964
965
966
967
				if ( f1->f_sub_any ) {
					if ( f2->f_sub_any ) {
						rc = lex_bvcmp( f1->f_sub_any,
							f2->f_sub_any );
968
969
970
					} else {
						rc = 1;
					}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
971
				} else if ( f2->f_sub_any ) {
972
973
974
					rc = -1;
				}
				if ( rc ) break;
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
975
976
977
978
				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 );
979
980
981
					} else {
						rc = 1;
					}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
982
				} else if ( !BER_BVISNULL( &f2->f_sub_final )) {
983
984
985
					rc = -1;
				}
			} else {
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
986
987
				rc = lex_bvcmp( &f1->f_mr_value,
					&f2->f_mr_value );
988
989
990
			}
			break;
		}
Quanah Gibson-Mount's avatar
Quanah Gibson-Mount committed
991
992
993
994
995
996
997
998
999
1000
		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 )
For faster browsing, not all history is shown. View entire blame