1 /* Copyright (c) 2003 by International Business Machines, Inc.
3 * International Business Machines, Inc. (hereinafter called IBM) grants
4 * permission under its copyrights to use, copy, modify, and distribute this
5 * Software with or without fee, provided that the above copyright notice and
6 * all paragraphs of this notice appear in all copies, and that the name of IBM
7 * not be used in connection with the marketing of any product incorporating
8 * the Software or modifications thereof, without specific, written prior
11 * THE SOFTWARE IS PROVIDED "AS IS", AND IBM DISCLAIMS ALL WARRANTIES,
12 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
13 * PARTICULAR PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL,
14 * DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER ARISING
15 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE, EVEN
16 * IF IBM IS APPRISED OF THE POSSIBILITY OF SUCH DAMAGES.
24 #include "../back-ldap/back-ldap.h"
25 #include "back-meta.h"
28 static void add_query_on_top (query_manager*, CachedQuery*);
29 static int base_scope_compare(struct berval* dn_stored,
30 struct berval* dn_incoming, int scope_stored,
33 /* check whether query is contained in any of
34 * the cached queries in template template_index
37 query_containment(query_manager* qm,
41 QueryTemplate* templa= qm->templates;
45 Filter* inputf = query->filter;
46 struct berval* base = &(query->base);
47 int scope = query->scope;
54 MatchingRule* mrule = NULL;
57 LDAP_LOG( BACK_META, DETAIL1, "Lock QC index = %d\n",
58 template_index, 0, 0 );
60 Debug( LDAP_DEBUG_ANY, "Lock QC index = %d\n",
61 template_index, 0, 0 );
63 ldap_pvt_thread_rdwr_rlock(&(templa[template_index].t_rwlock));
64 for(qc=templa[template_index].query; qc != NULL; qc= qc->next) {
66 if(base_scope_compare(&(q->base), base, q->scope, scope)) {
71 switch (fs->f_choice) {
72 case LDAP_FILTER_EQUALITY:
73 if (fi->f_choice == LDAP_FILTER_EQUALITY)
74 mrule = fs->f_ava->aa_desc->ad_type->sat_equality;
80 mrule = fs->f_ava->aa_desc->ad_type->sat_ordering;
86 rc = value_match(&ret, fs->f_ava->aa_desc, mrule,
87 SLAP_MR_VALUE_OF_ASSERTION_SYNTAX,
88 &(fi->f_ava->aa_value),
89 &(fs->f_ava->aa_value), &text);
90 if (rc != LDAP_SUCCESS) {
92 LDAP_LOG( BACK_META, DETAIL1,
93 "Unlock: Exiting QC index=%d\n",
94 template_index, 0, 0 );
96 Debug( LDAP_DEBUG_ANY,
97 "Unlock: Exiting QC index=%d\n",
98 template_index, 0, 0 );
100 ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
102 LDAP_LOG( BACK_META, DETAIL1,
103 "query_containment: Required "
104 "matching rule not defined for "
105 "a filter attribute",
108 Debug( LDAP_DEBUG_ANY,
109 "query_containment: Required "
110 "matching rule not defined for "
111 "a filter attribute",
117 switch (fs->f_choice) {
118 case LDAP_FILTER_AND:
123 case LDAP_FILTER_SUBSTRINGS:
124 /* check if the equality query can be
125 * answered with cached substring query */
126 if ((fi->f_choice == LDAP_FILTER_EQUALITY)
127 && substr_containment_equality(
130 /* check if the substring query can be
131 * answered with cached substring query */
132 if ((fi->f_choice ==LDAP_FILTER_SUBSTRINGS
133 ) && substr_containment_substr(
139 case LDAP_FILTER_PRESENT:
144 case LDAP_FILTER_EQUALITY:
165 } while((res) && (fi != NULL) && (fs != NULL));
168 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
169 if (qm->lru_top != qc) {
170 remove_query(qm, qc);
171 add_query_on_top(qm, qc);
173 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
179 LDAP_LOG( BACK_META, DETAIL1,
180 "Not answerable: Unlock QC index=%d\n",
181 template_index, 0, 0 );
183 Debug( LDAP_DEBUG_ANY,
184 "Not answerable: Unlock QC index=%d\n",
185 template_index, 0, 0 );
187 ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
192 /* remove_query from LRU list */
195 remove_query (query_manager* qm, CachedQuery* qc)
218 qc->lru_up = qc->lru_down = NULL;
221 /* add query on top of LRU list */
223 add_query_on_top (query_manager* qm, CachedQuery* qc)
225 CachedQuery* top = qm->lru_top;
226 Query* q = (Query*)qc;
238 LDAP_LOG( BACK_META, DETAIL1, "Base of added query = %s\n",
239 q->base.bv_val, 0, 0 );
241 Debug( LDAP_DEBUG_ANY, "Base of added query = %s\n",
242 q->base.bv_val, 0, 0 );
247 free_query (CachedQuery* qc)
249 Query* q = (Query*)qc;
251 filter_free(q->filter);
252 free (q->base.bv_val);
258 /* compare base and scope of incoming and cached queries */
259 int base_scope_compare(
260 struct berval* dn_stored,
261 struct berval* dn_incoming,
265 struct berval ndn_incoming = { 0L, NULL };
266 struct berval pdn_incoming = { 0L, NULL };
267 struct berval ndn_stored = { 0L, NULL };
271 if (scope_stored < scope_incoming)
274 dnNormalize2(NULL, dn_incoming, &ndn_incoming);
275 dnNormalize2(NULL, dn_stored, &ndn_stored);
277 i = dnIsSuffix(&ndn_incoming, &ndn_stored);
282 switch(scope_stored) {
283 case LDAP_SCOPE_BASE:
284 if (strlen(ndn_incoming.bv_val) == strlen(ndn_stored.bv_val))
289 case LDAP_SCOPE_ONELEVEL:
290 switch(scope_incoming){
291 case LDAP_SCOPE_BASE:
292 dnParent(&ndn_incoming, &pdn_incoming);
293 if(strcmp(pdn_incoming.bv_val, ndn_stored.bv_val) == 0)
298 case LDAP_SCOPE_ONELEVEL:
299 if (ndn_incoming.bv_len == ndn_stored.bv_len)
308 case LDAP_SCOPE_SUBTREE:
317 /* Add query to query cache */
323 struct exception* result)
325 CachedQuery* new_cached_query = (CachedQuery*) malloc(sizeof(CachedQuery));
326 QueryTemplate* templ = (qm->templates)+template_index;
328 new_cached_query->template_id = template_index;
329 new_cached_query->q_uuid = uuid;
330 new_cached_query->lru_up = NULL;
331 new_cached_query->lru_down = NULL;
332 new_cached_query->expiry_time = slap_get_time() + templ->ttl;
334 LDAP_LOG( BACK_META, DETAIL1, "Added query expires at %d\n",
335 new_cached_query->expiry_time, 0, 0 );
337 Debug( LDAP_DEBUG_ANY, "Added query expires at %d\n",
338 new_cached_query->expiry_time, 0, 0 );
340 new_query = (Query*)new_cached_query;
342 new_query->base.bv_val = ch_strdup(query->base.bv_val);
343 new_query->base.bv_len = query->base.bv_len;
344 new_query->scope = query->scope;
345 new_query->filter = query->filter;
346 new_query->attrs = query->attrs;
350 LDAP_LOG( BACK_META, DETAIL1, "Lock AQ index = %d\n",
351 template_index, 0, 0 );
353 Debug( LDAP_DEBUG_ANY, "Lock AQ index = %d\n",
354 template_index, 0, 0 );
356 ldap_pvt_thread_rdwr_wlock(&templ->t_rwlock);
357 if (templ->query == NULL)
358 templ->query_last = new_cached_query;
360 templ->query->prev = new_cached_query;
361 new_cached_query->next = templ->query;
362 new_cached_query->prev = NULL;
363 templ->query = new_cached_query;
364 templ->no_of_queries++;
366 LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES++ %d\n",
367 template_index, templ->no_of_queries, 0 );
369 Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES++ %d\n",
370 template_index, templ->no_of_queries, 0 );
374 LDAP_LOG( BACK_META, DETAIL1, "Unlock AQ index = %d \n",
375 template_index, 0, 0 );
377 Debug( LDAP_DEBUG_ANY, "Unlock AQ index = %d \n",
378 template_index, 0, 0 );
380 ldap_pvt_thread_rdwr_wunlock(&templ->t_rwlock);
382 /* Adding on top of LRU list */
383 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
384 add_query_on_top(qm, new_cached_query);
385 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
389 /* remove bottom query of LRU list from the query cache */
390 char* cache_replacement(query_manager* qm)
392 char* result = (char*)(malloc(40));
394 QueryTemplate* templ;
395 CachedQuery* query_curr;
398 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
399 bottom = qm->lru_bottom;
403 LDAP_LOG ( BACK_META, DETAIL1,
404 "Cache replacement invoked without "
405 "any query in LRU list\n", 0, 0, 0 );
407 Debug ( LDAP_DEBUG_ANY,
408 "Cache replacement invoked without "
409 "any query in LRU list\n", 0, 0, 0 );
414 temp_id = bottom->template_id;
415 remove_query(qm, bottom);
416 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
418 strcpy(result, bottom->q_uuid);
421 LDAP_LOG( BACK_META, DETAIL1, "Lock CR index = %d\n", temp_id, 0, 0 );
423 Debug( LDAP_DEBUG_ANY, "Lock CR index = %d\n", temp_id, 0, 0 );
425 ldap_pvt_thread_rdwr_wlock(&(qm->templates[temp_id].t_rwlock));
426 remove_from_template(bottom, (qm->templates+temp_id));
428 LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES-- %d\n",
429 temp_id, qm->templates[temp_id].no_of_queries, 0 );
431 Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES-- %d\n",
432 temp_id, qm->templates[temp_id].no_of_queries, 0 );
435 LDAP_LOG( BACK_META, DETAIL1, "Unlock CR index = %d\n", temp_id, 0, 0 );
437 Debug( LDAP_DEBUG_ANY, "Unlock CR index = %d\n", temp_id, 0, 0 );
439 ldap_pvt_thread_rdwr_wunlock(&(qm->templates[temp_id].t_rwlock));
445 remove_from_template (CachedQuery* qc, QueryTemplate* template)
447 if (!qc->prev && !qc->next) {
448 template->query_last = template->query = NULL;
449 } else if (qc->prev == NULL) {
450 qc->next->prev = NULL;
451 template->query = qc->next;
452 } else if (qc->next == NULL) {
453 qc->prev->next = NULL;
454 template->query_last = qc->prev;
456 qc->next->prev = qc->prev;
457 qc->prev->next = qc->next;
460 template->no_of_queries--;