2 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 * Copyright 1999-2003 The OpenLDAP Foundation.
5 * Portions Copyright 2003 IBM Corporation.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
12 * A copy of this license is available in the file LICENSE in the
13 * top-level directory of the distribution or, alternatively, at
14 * <http://www.OpenLDAP.org/license.html>.
17 * This work was initially developed by the Apurva Kumar for inclusion
18 * in OpenLDAP Software.
25 #include <ac/string.h>
28 #include "../back-ldap/back-ldap.h"
29 #include "back-meta.h"
31 static void add_query_on_top (query_manager*, CachedQuery*);
32 static int base_scope_compare(struct berval* dn_stored,
33 struct berval* dn_incoming, int scope_stored,
36 /* check whether query is contained in any of
37 * the cached queries in template template_index
40 query_containment(query_manager* qm,
44 QueryTemplate* templa= qm->templates;
48 Filter* inputf = query->filter;
49 struct berval* base = &(query->base);
50 int scope = query->scope;
57 MatchingRule* mrule = NULL;
60 LDAP_LOG( BACK_META, DETAIL1, "Lock QC index = %d\n",
61 template_index, 0, 0 );
63 Debug( LDAP_DEBUG_ANY, "Lock QC index = %d\n",
64 template_index, 0, 0 );
66 ldap_pvt_thread_rdwr_rlock(&(templa[template_index].t_rwlock));
67 for(qc=templa[template_index].query; qc != NULL; qc= qc->next) {
69 if(base_scope_compare(&(q->base), base, q->scope, scope)) {
74 switch (fs->f_choice) {
75 case LDAP_FILTER_EQUALITY:
76 if (fi->f_choice == LDAP_FILTER_EQUALITY)
77 mrule = fs->f_ava->aa_desc->ad_type->sat_equality;
83 mrule = fs->f_ava->aa_desc->ad_type->sat_ordering;
89 rc = value_match(&ret, fs->f_ava->aa_desc, mrule,
90 SLAP_MR_VALUE_OF_ASSERTION_SYNTAX,
91 &(fi->f_ava->aa_value),
92 &(fs->f_ava->aa_value), &text);
93 if (rc != LDAP_SUCCESS) {
95 LDAP_LOG( BACK_META, DETAIL1,
96 "Unlock: Exiting QC index=%d\n",
97 template_index, 0, 0 );
99 Debug( LDAP_DEBUG_ANY,
100 "Unlock: Exiting QC index=%d\n",
101 template_index, 0, 0 );
103 ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
105 LDAP_LOG( BACK_META, DETAIL1,
106 "query_containment: Required "
107 "matching rule not defined for "
108 "a filter attribute",
111 Debug( LDAP_DEBUG_ANY,
112 "query_containment: Required "
113 "matching rule not defined for "
114 "a filter attribute",
120 switch (fs->f_choice) {
122 case LDAP_FILTER_AND:
127 case LDAP_FILTER_SUBSTRINGS:
128 /* check if the equality query can be
129 * answered with cached substring query */
130 if ((fi->f_choice == LDAP_FILTER_EQUALITY)
131 && substr_containment_equality(
134 /* check if the substring query can be
135 * answered with cached substring query */
136 if ((fi->f_choice ==LDAP_FILTER_SUBSTRINGS
137 ) && substr_containment_substr(
143 case LDAP_FILTER_PRESENT:
148 case LDAP_FILTER_EQUALITY:
166 case LDAP_FILTER_NOT:
172 } while((res) && (fi != NULL) && (fs != NULL));
175 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
176 if (qm->lru_top != qc) {
177 remove_query(qm, qc);
178 add_query_on_top(qm, qc);
180 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
186 LDAP_LOG( BACK_META, DETAIL1,
187 "Not answerable: Unlock QC index=%d\n",
188 template_index, 0, 0 );
190 Debug( LDAP_DEBUG_ANY,
191 "Not answerable: Unlock QC index=%d\n",
192 template_index, 0, 0 );
194 ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
199 /* remove_query from LRU list */
202 remove_query (query_manager* qm, CachedQuery* qc)
225 qc->lru_up = qc->lru_down = NULL;
228 /* add query on top of LRU list */
230 add_query_on_top (query_manager* qm, CachedQuery* qc)
232 CachedQuery* top = qm->lru_top;
233 Query* q = (Query*)qc;
245 LDAP_LOG( BACK_META, DETAIL1, "Base of added query = %s\n",
246 q->base.bv_val, 0, 0 );
248 Debug( LDAP_DEBUG_ANY, "Base of added query = %s\n",
249 q->base.bv_val, 0, 0 );
254 free_query (CachedQuery* qc)
256 Query* q = (Query*)qc;
258 filter_free(q->filter);
259 free (q->base.bv_val);
265 /* compare base and scope of incoming and cached queries */
266 int base_scope_compare(
267 struct berval* dn_stored,
268 struct berval* dn_incoming,
272 struct berval ndn_incoming = { 0L, NULL };
273 struct berval pdn_incoming = { 0L, NULL };
274 struct berval ndn_stored = { 0L, NULL };
278 if (scope_stored < scope_incoming)
281 dnNormalize(0, NULL, NULL, dn_incoming, &ndn_incoming, NULL);
282 dnNormalize(0, NULL, NULL, dn_stored, &ndn_stored, NULL);
284 i = dnIsSuffix(&ndn_incoming, &ndn_stored);
289 switch(scope_stored) {
290 case LDAP_SCOPE_BASE:
291 if (strlen(ndn_incoming.bv_val) == strlen(ndn_stored.bv_val))
296 case LDAP_SCOPE_ONELEVEL:
297 switch(scope_incoming){
298 case LDAP_SCOPE_BASE:
299 dnParent(&ndn_incoming, &pdn_incoming);
300 if(strcmp(pdn_incoming.bv_val, ndn_stored.bv_val) == 0)
305 case LDAP_SCOPE_ONELEVEL:
306 if (ndn_incoming.bv_len == ndn_stored.bv_len)
315 case LDAP_SCOPE_SUBTREE:
324 /* Add query to query cache */
330 struct exception* result)
332 CachedQuery* new_cached_query = (CachedQuery*) malloc(sizeof(CachedQuery));
333 QueryTemplate* templ = (qm->templates)+template_index;
335 new_cached_query->template_id = template_index;
336 new_cached_query->q_uuid = uuid;
337 new_cached_query->lru_up = NULL;
338 new_cached_query->lru_down = NULL;
339 new_cached_query->expiry_time = slap_get_time() + templ->ttl;
341 LDAP_LOG( BACK_META, DETAIL1, "Added query expires at %ld\n",
342 (long) new_cached_query->expiry_time, 0, 0 );
344 Debug( LDAP_DEBUG_ANY, "Added query expires at %ld\n",
345 (long) new_cached_query->expiry_time, 0, 0 );
347 new_query = (Query*)new_cached_query;
349 new_query->base.bv_val = ch_strdup(query->base.bv_val);
350 new_query->base.bv_len = query->base.bv_len;
351 new_query->scope = query->scope;
352 new_query->filter = query->filter;
353 new_query->attrs = query->attrs;
357 LDAP_LOG( BACK_META, DETAIL1, "Lock AQ index = %d\n",
358 template_index, 0, 0 );
360 Debug( LDAP_DEBUG_ANY, "Lock AQ index = %d\n",
361 template_index, 0, 0 );
363 ldap_pvt_thread_rdwr_wlock(&templ->t_rwlock);
364 if (templ->query == NULL)
365 templ->query_last = new_cached_query;
367 templ->query->prev = new_cached_query;
368 new_cached_query->next = templ->query;
369 new_cached_query->prev = NULL;
370 templ->query = new_cached_query;
371 templ->no_of_queries++;
373 LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES++ %d\n",
374 template_index, templ->no_of_queries, 0 );
376 Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES++ %d\n",
377 template_index, templ->no_of_queries, 0 );
381 LDAP_LOG( BACK_META, DETAIL1, "Unlock AQ index = %d \n",
382 template_index, 0, 0 );
384 Debug( LDAP_DEBUG_ANY, "Unlock AQ index = %d \n",
385 template_index, 0, 0 );
387 ldap_pvt_thread_rdwr_wunlock(&templ->t_rwlock);
389 /* Adding on top of LRU list */
390 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
391 add_query_on_top(qm, new_cached_query);
392 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
396 /* remove bottom query of LRU list from the query cache */
397 char* cache_replacement(query_manager* qm)
399 char* result = (char*)(malloc(40));
401 QueryTemplate* templ;
402 CachedQuery* query_curr;
405 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
406 bottom = qm->lru_bottom;
410 LDAP_LOG ( BACK_META, DETAIL1,
411 "Cache replacement invoked without "
412 "any query in LRU list\n", 0, 0, 0 );
414 Debug ( LDAP_DEBUG_ANY,
415 "Cache replacement invoked without "
416 "any query in LRU list\n", 0, 0, 0 );
421 temp_id = bottom->template_id;
422 remove_query(qm, bottom);
423 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
425 strcpy(result, bottom->q_uuid);
428 LDAP_LOG( BACK_META, DETAIL1, "Lock CR index = %d\n", temp_id, 0, 0 );
430 Debug( LDAP_DEBUG_ANY, "Lock CR index = %d\n", temp_id, 0, 0 );
432 ldap_pvt_thread_rdwr_wlock(&(qm->templates[temp_id].t_rwlock));
433 remove_from_template(bottom, (qm->templates+temp_id));
435 LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES-- %d\n",
436 temp_id, qm->templates[temp_id].no_of_queries, 0 );
438 Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES-- %d\n",
439 temp_id, qm->templates[temp_id].no_of_queries, 0 );
442 LDAP_LOG( BACK_META, DETAIL1, "Unlock CR index = %d\n", temp_id, 0, 0 );
444 Debug( LDAP_DEBUG_ANY, "Unlock CR index = %d\n", temp_id, 0, 0 );
446 ldap_pvt_thread_rdwr_wunlock(&(qm->templates[temp_id].t_rwlock));
452 remove_from_template (CachedQuery* qc, QueryTemplate* template)
454 if (!qc->prev && !qc->next) {
455 template->query_last = template->query = NULL;
456 } else if (qc->prev == NULL) {
457 qc->next->prev = NULL;
458 template->query = qc->next;
459 } else if (qc->next == NULL) {
460 qc->prev->next = NULL;
461 template->query_last = qc->prev;
463 qc->next->prev = qc->prev;
464 qc->prev->next = qc->next;
467 template->no_of_queries--;