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.
23 #include <ac/string.h>
26 #include "../back-ldap/back-ldap.h"
27 #include "back-meta.h"
29 static void add_query_on_top (query_manager*, CachedQuery*);
30 static int base_scope_compare(struct berval* dn_stored,
31 struct berval* dn_incoming, int scope_stored,
34 /* check whether query is contained in any of
35 * the cached queries in template template_index
38 query_containment(query_manager* qm,
42 QueryTemplate* templa= qm->templates;
46 Filter* inputf = query->filter;
47 struct berval* base = &(query->base);
48 int scope = query->scope;
55 MatchingRule* mrule = NULL;
58 LDAP_LOG( BACK_META, DETAIL1, "Lock QC index = %d\n",
59 template_index, 0, 0 );
61 Debug( LDAP_DEBUG_ANY, "Lock QC index = %d\n",
62 template_index, 0, 0 );
64 ldap_pvt_thread_rdwr_rlock(&(templa[template_index].t_rwlock));
65 for(qc=templa[template_index].query; qc != NULL; qc= qc->next) {
67 if(base_scope_compare(&(q->base), base, q->scope, scope)) {
72 switch (fs->f_choice) {
73 case LDAP_FILTER_EQUALITY:
74 if (fi->f_choice == LDAP_FILTER_EQUALITY)
75 mrule = fs->f_ava->aa_desc->ad_type->sat_equality;
81 mrule = fs->f_ava->aa_desc->ad_type->sat_ordering;
87 rc = value_match(&ret, fs->f_ava->aa_desc, mrule,
88 SLAP_MR_VALUE_OF_ASSERTION_SYNTAX,
89 &(fi->f_ava->aa_value),
90 &(fs->f_ava->aa_value), &text);
91 if (rc != LDAP_SUCCESS) {
93 LDAP_LOG( BACK_META, DETAIL1,
94 "Unlock: Exiting QC index=%d\n",
95 template_index, 0, 0 );
97 Debug( LDAP_DEBUG_ANY,
98 "Unlock: Exiting QC index=%d\n",
99 template_index, 0, 0 );
101 ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
103 LDAP_LOG( BACK_META, DETAIL1,
104 "query_containment: Required "
105 "matching rule not defined for "
106 "a filter attribute",
109 Debug( LDAP_DEBUG_ANY,
110 "query_containment: Required "
111 "matching rule not defined for "
112 "a filter attribute",
118 switch (fs->f_choice) {
120 case LDAP_FILTER_AND:
125 case LDAP_FILTER_SUBSTRINGS:
126 /* check if the equality query can be
127 * answered with cached substring query */
128 if ((fi->f_choice == LDAP_FILTER_EQUALITY)
129 && substr_containment_equality(
132 /* check if the substring query can be
133 * answered with cached substring query */
134 if ((fi->f_choice ==LDAP_FILTER_SUBSTRINGS
135 ) && substr_containment_substr(
141 case LDAP_FILTER_PRESENT:
146 case LDAP_FILTER_EQUALITY:
164 case LDAP_FILTER_NOT:
170 } while((res) && (fi != NULL) && (fs != NULL));
173 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
174 if (qm->lru_top != qc) {
175 remove_query(qm, qc);
176 add_query_on_top(qm, qc);
178 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
184 LDAP_LOG( BACK_META, DETAIL1,
185 "Not answerable: Unlock QC index=%d\n",
186 template_index, 0, 0 );
188 Debug( LDAP_DEBUG_ANY,
189 "Not answerable: Unlock QC index=%d\n",
190 template_index, 0, 0 );
192 ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
197 /* remove_query from LRU list */
200 remove_query (query_manager* qm, CachedQuery* qc)
223 qc->lru_up = qc->lru_down = NULL;
226 /* add query on top of LRU list */
228 add_query_on_top (query_manager* qm, CachedQuery* qc)
230 CachedQuery* top = qm->lru_top;
231 Query* q = (Query*)qc;
243 LDAP_LOG( BACK_META, DETAIL1, "Base of added query = %s\n",
244 q->base.bv_val, 0, 0 );
246 Debug( LDAP_DEBUG_ANY, "Base of added query = %s\n",
247 q->base.bv_val, 0, 0 );
252 free_query (CachedQuery* qc)
254 Query* q = (Query*)qc;
256 filter_free(q->filter);
257 free (q->base.bv_val);
263 /* compare base and scope of incoming and cached queries */
264 int base_scope_compare(
265 struct berval* dn_stored,
266 struct berval* dn_incoming,
270 struct berval ndn_incoming = { 0L, NULL };
271 struct berval pdn_incoming = { 0L, NULL };
272 struct berval ndn_stored = { 0L, NULL };
276 if (scope_stored < scope_incoming)
279 dnNormalize(0, NULL, NULL, dn_incoming, &ndn_incoming, NULL);
280 dnNormalize(0, NULL, NULL, dn_stored, &ndn_stored, NULL);
282 i = dnIsSuffix(&ndn_incoming, &ndn_stored);
287 switch(scope_stored) {
288 case LDAP_SCOPE_BASE:
289 if (strlen(ndn_incoming.bv_val) == strlen(ndn_stored.bv_val))
294 case LDAP_SCOPE_ONELEVEL:
295 switch(scope_incoming){
296 case LDAP_SCOPE_BASE:
297 dnParent(&ndn_incoming, &pdn_incoming);
298 if(strcmp(pdn_incoming.bv_val, ndn_stored.bv_val) == 0)
303 case LDAP_SCOPE_ONELEVEL:
304 if (ndn_incoming.bv_len == ndn_stored.bv_len)
313 case LDAP_SCOPE_SUBTREE:
322 /* Add query to query cache */
328 struct exception* result)
330 CachedQuery* new_cached_query = (CachedQuery*) malloc(sizeof(CachedQuery));
331 QueryTemplate* templ = (qm->templates)+template_index;
333 new_cached_query->template_id = template_index;
334 new_cached_query->q_uuid = uuid;
335 new_cached_query->lru_up = NULL;
336 new_cached_query->lru_down = NULL;
337 new_cached_query->expiry_time = slap_get_time() + templ->ttl;
339 LDAP_LOG( BACK_META, DETAIL1, "Added query expires at %ld\n",
340 (long) new_cached_query->expiry_time, 0, 0 );
342 Debug( LDAP_DEBUG_ANY, "Added query expires at %ld\n",
343 (long) new_cached_query->expiry_time, 0, 0 );
345 new_query = (Query*)new_cached_query;
347 new_query->base.bv_val = ch_strdup(query->base.bv_val);
348 new_query->base.bv_len = query->base.bv_len;
349 new_query->scope = query->scope;
350 new_query->filter = query->filter;
351 new_query->attrs = query->attrs;
355 LDAP_LOG( BACK_META, DETAIL1, "Lock AQ index = %d\n",
356 template_index, 0, 0 );
358 Debug( LDAP_DEBUG_ANY, "Lock AQ index = %d\n",
359 template_index, 0, 0 );
361 ldap_pvt_thread_rdwr_wlock(&templ->t_rwlock);
362 if (templ->query == NULL)
363 templ->query_last = new_cached_query;
365 templ->query->prev = new_cached_query;
366 new_cached_query->next = templ->query;
367 new_cached_query->prev = NULL;
368 templ->query = new_cached_query;
369 templ->no_of_queries++;
371 LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES++ %d\n",
372 template_index, templ->no_of_queries, 0 );
374 Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES++ %d\n",
375 template_index, templ->no_of_queries, 0 );
379 LDAP_LOG( BACK_META, DETAIL1, "Unlock AQ index = %d \n",
380 template_index, 0, 0 );
382 Debug( LDAP_DEBUG_ANY, "Unlock AQ index = %d \n",
383 template_index, 0, 0 );
385 ldap_pvt_thread_rdwr_wunlock(&templ->t_rwlock);
387 /* Adding on top of LRU list */
388 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
389 add_query_on_top(qm, new_cached_query);
390 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
394 /* remove bottom query of LRU list from the query cache */
395 char* cache_replacement(query_manager* qm)
397 char* result = (char*)(malloc(40));
399 QueryTemplate* templ;
400 CachedQuery* query_curr;
403 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
404 bottom = qm->lru_bottom;
408 LDAP_LOG ( BACK_META, DETAIL1,
409 "Cache replacement invoked without "
410 "any query in LRU list\n", 0, 0, 0 );
412 Debug ( LDAP_DEBUG_ANY,
413 "Cache replacement invoked without "
414 "any query in LRU list\n", 0, 0, 0 );
419 temp_id = bottom->template_id;
420 remove_query(qm, bottom);
421 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
423 strcpy(result, bottom->q_uuid);
426 LDAP_LOG( BACK_META, DETAIL1, "Lock CR index = %d\n", temp_id, 0, 0 );
428 Debug( LDAP_DEBUG_ANY, "Lock CR index = %d\n", temp_id, 0, 0 );
430 ldap_pvt_thread_rdwr_wlock(&(qm->templates[temp_id].t_rwlock));
431 remove_from_template(bottom, (qm->templates+temp_id));
433 LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES-- %d\n",
434 temp_id, qm->templates[temp_id].no_of_queries, 0 );
436 Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES-- %d\n",
437 temp_id, qm->templates[temp_id].no_of_queries, 0 );
440 LDAP_LOG( BACK_META, DETAIL1, "Unlock CR index = %d\n", temp_id, 0, 0 );
442 Debug( LDAP_DEBUG_ANY, "Unlock CR index = %d\n", temp_id, 0, 0 );
444 ldap_pvt_thread_rdwr_wunlock(&(qm->templates[temp_id].t_rwlock));
450 remove_from_template (CachedQuery* qc, QueryTemplate* template)
452 if (!qc->prev && !qc->next) {
453 template->query_last = template->query = NULL;
454 } else if (qc->prev == NULL) {
455 qc->next->prev = NULL;
456 template->query = qc->next;
457 } else if (qc->next == NULL) {
458 qc->prev->next = NULL;
459 template->query_last = qc->prev;
461 qc->next->prev = qc->prev;
462 qc->prev->next = qc->next;
465 template->no_of_queries--;