git.sur5r.net Git - openldap/blob - servers/slapd/back-meta/cache-query.c

   1 /* Copyright (c) 2003 by International Business Machines, Inc.
   2  *
   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
   9  * permission.
  10  *
  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.
  17  */
  18
  19 #include "portable.h"
  20
  21 #include <stdio.h>
  22
  23 #include "slap.h"
  24 #include "../back-ldap/back-ldap.h"
  25 #include "back-meta.h"
  26
  27 #ifdef LDAP_CACHING
  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,
  31                                    int scope_incoming);
  32
  33 /* check whether query is contained in any of
  34  * the cached queries in template template_index
  35  */
  36 int
  37 query_containment(query_manager* qm,
  38                   Query* query,
  39                   int template_index)
  40 {
  41         QueryTemplate* templa= qm->templates;
  42         CachedQuery* qc;
  43         Query* q;
  44         Query* prev_q;
  45         Filter* inputf = query->filter;
  46         struct berval* base = &(query->base);
  47         int scope = query->scope;
  48         int i,res=0;
  49         Filter* fs;
  50         Filter* fi;
  51         int ret, rc;
  52         const char* text;
  53
  54         MatchingRule* mrule = NULL;
  55         if (inputf != NULL) {
  56 #ifdef NEW_LOGGING
  57                 LDAP_LOG( BACK_META, DETAIL1, "Lock QC index = %d\n",
  58                                 template_index, 0, 0 );
  59 #else
  60                 Debug( LDAP_DEBUG_ANY, "Lock QC index = %d\n",
  61                                 template_index, 0, 0 );
  62 #endif
  63                 ldap_pvt_thread_rdwr_rlock(&(templa[template_index].t_rwlock));
  64                 for(qc=templa[template_index].query; qc != NULL; qc= qc->next) {
  65                         q = (Query*)qc;
  66                         if(base_scope_compare(&(q->base), base, q->scope, scope)) {
  67                                 fi = inputf;
  68                                 fs = q->filter;
  69                                 do {
  70                                         res=0;
  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;
  75                                                 else
  76                                                         ret = 1;
  77                                                 break;
  78                                         case LDAP_FILTER_GE:
  79                                         case LDAP_FILTER_LE:
  80                                                 mrule = fs->f_ava->aa_desc->ad_type->sat_ordering;
  81                                                 break;
  82                                         default:
  83                                                 mrule = NULL;
  84                                         }
  85                                         if (mrule) {
  86                                                 rc = value_match(&ret, fs->f_ava->aa_desc, mrule,
  87                                                         SLAP_MR_ASSERTION_SYNTAX_MATCH,
  88                                                         &(fi->f_ava->aa_value),
  89                                                         &(fs->f_ava->aa_value), &text);
  90                                                 if (rc != LDAP_SUCCESS) {
  91 #ifdef NEW_LOGGING
  92                                                         LDAP_LOG( BACK_META, DETAIL1,
  93                                                         "Unlock: Exiting QC index=%d\n",
  94                                                         template_index, 0, 0 );
  95 #else
  96                                                         Debug( LDAP_DEBUG_ANY,
  97                                                         "Unlock: Exiting QC index=%d\n",
  98                                                         template_index, 0, 0 );
  99 #endif
 100                                                         ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
 101 #ifdef NEW_LOGGING
 102                                                         LDAP_LOG( BACK_META, DETAIL1,
 103                                                         "query_containment: Required "
 104                                                         "matching rule not defined for "
 105                                                         "a filter attribute",
 106                                                         0, 0, 0 );
 107 #else
 108                                                         Debug( LDAP_DEBUG_ANY,
 109                                                         "query_containment: Required "
 110                                                         "matching rule not defined for "
 111                                                         "a filter attribute",
 112                                                         0, 0, 0 );
 113 #endif
 114                                                         return 0;
 115                                                 }
 116                                         }
 117                                         switch (fs->f_choice) {
 118                                         case LDAP_FILTER_AND:
 119                                                 fs = fs->f_and;
 120                                                 fi = fi->f_and;
 121                                                 res=1;
 122                                                 break;
 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(
 128                                                         fs, fi))
 129                                                         res=1;
 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(
 134                                                         fs, fi))
 135                                                         res= 1;
 136                                                 fs=fs->f_next;
 137                                                 fi=fi->f_next;
 138                                                 break;
 139                                         case LDAP_FILTER_PRESENT:
 140                                                 res=1;
 141                                                 fs=fs->f_next;
 142                                                 fi=fi->f_next;
 143                                                 break;
 144                                         case LDAP_FILTER_EQUALITY:
 145                                                 if (ret == 0)
 146                                                         res = 1;
 147                                                 fs=fs->f_next;
 148                                                 fi=fi->f_next;
 149                                                 break;
 150                                         case LDAP_FILTER_GE:
 151                                                 if (ret >= 0)
 152                                                         res = 1;
 153                                                 fs=fs->f_next;
 154                                                 fi=fi->f_next;
 155                                                 break;
 156                                         case LDAP_FILTER_LE:
 157                                                 if (ret <= 0)
 158                                                         res = 1;
 159                                                 fs=fs->f_next;
 160                                                 fi=fi->f_next;
 161                                                 break;
 162                                         default:
 163                                                 break;
 164                                         }
 165                                 } while((res) && (fi != NULL) && (fs != NULL));
 166
 167                                 if(res) {
 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);
 172                                         }
 173                                         ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
 174                                         return 1;
 175                                 }
 176                         }
 177                 }
 178 #ifdef NEW_LOGGING
 179                 LDAP_LOG( BACK_META, DETAIL1,
 180                         "Not answerable: Unlock QC index=%d\n",
 181                         template_index, 0, 0 );
 182 #else
 183                 Debug( LDAP_DEBUG_ANY,
 184                         "Not answerable: Unlock QC index=%d\n",
 185                         template_index, 0, 0 );
 186 #endif
 187                 ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
 188         }
 189         return 0;
 190 }
 191
 192 /* remove_query from LRU list */
 193
 194 void
 195 remove_query (query_manager* qm, CachedQuery* qc)
 196 {
 197         CachedQuery* up;
 198         CachedQuery* down;
 199
 200         if (!qc)
 201                 return;
 202
 203         up = qc->lru_up;
 204         down = qc->lru_down;
 205
 206         if (!up)
 207                 qm->lru_top = down;
 208
 209         if (!down)
 210                 qm->lru_bottom = up;
 211
 212         if (down)
 213                 down->lru_up = up;
 214
 215         if (up)
 216                 up->lru_down = down;
 217
 218         qc->lru_up = qc->lru_down = NULL;
 219 }
 220
 221 /* add query on top of LRU list */
 222 void
 223 add_query_on_top (query_manager* qm, CachedQuery* qc)
 224 {
 225         CachedQuery* top = qm->lru_top;
 226         Query* q = (Query*)qc;
 227
 228         qm->lru_top = qc;
 229
 230         if (top)
 231                 top->lru_up = qc;
 232         else
 233                 qm->lru_bottom = qc;
 234
 235         qc->lru_down = top;
 236         qc->lru_up = NULL;
 237 #ifdef NEW_LOGGING
 238         LDAP_LOG( BACK_META, DETAIL1, "Base of added query = %s\n",
 239                         q->base.bv_val, 0, 0 );
 240 #else
 241         Debug( LDAP_DEBUG_ANY, "Base of added query = %s\n",
 242                         q->base.bv_val, 0, 0 );
 243 #endif
 244 }
 245
 246 void
 247 free_query (CachedQuery* qc)
 248 {
 249         Query* q = (Query*)qc;
 250         free(qc->q_uuid);
 251         filter_free(q->filter);
 252         free (q->base.bv_val);
 253
 254         free(q->attrs);
 255         free(qc);
 256 }
 257
 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,
 262         int scope_stored,
 263         int scope_incoming      )
 264 {
 265         struct berval* ndn_incoming = NULL;
 266         struct berval* pdn_incoming = NULL;
 267         struct berval* ndn_stored = NULL;
 268
 269         int i;
 270
 271         if (scope_stored < scope_incoming)
 272                 return 0;
 273
 274         dnNormalize(NULL, dn_incoming, &ndn_incoming);
 275         dnNormalize(NULL, dn_stored, &ndn_stored);
 276
 277         i = dnIsSuffix(ndn_incoming, ndn_stored);
 278
 279         if ( i == 0 )
 280                 return 0;
 281
 282         switch(scope_stored) {
 283         case LDAP_SCOPE_BASE:
 284                 if (strlen(ndn_incoming->bv_val) == strlen(ndn_stored->bv_val))
 285                         return 1;
 286                 else
 287                         return 0;
 288                 break;
 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)
 294                                 return 1;
 295                         else
 296                                 return 0;
 297                         break;
 298                 case LDAP_SCOPE_ONELEVEL:
 299                         if (ndn_incoming->bv_len == ndn_stored->bv_len)
 300                                 return 1;
 301                         else
 302                                 return 0;
 303                         break;
 304                 default:
 305                         return 0;
 306                         break;
 307                 }
 308         case LDAP_SCOPE_SUBTREE:
 309                 return 1;
 310                 break;
 311         default:
 312                 return 0;
 313                 break;
 314     }
 315 }
 316
 317 /* Add query to query cache */
 318 void add_query(
 319         query_manager* qm,
 320         Query* query,
 321         int template_index,
 322         char* uuid,
 323         struct exception* result)
 324 {
 325         CachedQuery* new_cached_query = (CachedQuery*) malloc(sizeof(CachedQuery));
 326         QueryTemplate* templ = (qm->templates)+template_index;
 327         Query* new_query;
 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;
 333 #ifdef NEW_LOGGING
 334         LDAP_LOG( BACK_META, DETAIL1, "Added query expires at %d\n",
 335                         new_cached_query->expiry_time, 0, 0 );
 336 #else
 337         Debug( LDAP_DEBUG_ANY, "Added query expires at %d\n",
 338                         new_cached_query->expiry_time, 0, 0 );
 339 #endif
 340         new_query = (Query*)new_cached_query;
 341
 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;
 347
 348         /* Adding a query    */
 349 #ifdef NEW_LOGGING
 350         LDAP_LOG( BACK_META, DETAIL1, "Lock AQ index = %d\n",
 351                         template_index, 0, 0 );
 352 #else
 353         Debug( LDAP_DEBUG_ANY, "Lock AQ index = %d\n",
 354                         template_index, 0, 0 );
 355 #endif
 356         ldap_pvt_thread_rdwr_wlock(&templ->t_rwlock);
 357         if (templ->query == NULL)
 358                 templ->query_last = new_cached_query;
 359         else
 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++;
 365 #ifdef NEW_LOGGING
 366         LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES++ %d\n",
 367                         template_index, templ->no_of_queries, 0 );
 368 #else
 369         Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES++ %d\n",
 370                         template_index, templ->no_of_queries, 0 );
 371 #endif
 372
 373 #ifdef NEW_LOGGING
 374         LDAP_LOG( BACK_META, DETAIL1, "Unlock AQ index = %d \n",
 375                         template_index, 0, 0 );
 376 #else
 377         Debug( LDAP_DEBUG_ANY, "Unlock AQ index = %d \n",
 378                         template_index, 0, 0 );
 379 #endif
 380         ldap_pvt_thread_rdwr_wunlock(&templ->t_rwlock);
 381
 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);
 386
 387 }
 388
 389 /* remove bottom query of LRU list from the query cache */
 390 char* cache_replacement(query_manager* qm)
 391 {
 392         char* result = (char*)(malloc(40));
 393         CachedQuery* bottom;
 394         QueryTemplate* templ;
 395         CachedQuery* query_curr;
 396         int temp_id;
 397
 398         ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
 399         bottom = qm->lru_bottom;
 400
 401         if (!bottom) {
 402 #ifdef NEW_LOGGING
 403                 LDAP_LOG ( BACK_META, DETAIL1,
 404                         "Cache replacement invoked without "
 405                         "any query in LRU list\n", 0, 0, 0 );
 406 #else
 407                 Debug ( LDAP_DEBUG_ANY,
 408                         "Cache replacement invoked without "
 409                         "any query in LRU list\n", 0, 0, 0 );
 410 #endif
 411                 return 0;
 412         }
 413
 414         temp_id = bottom->template_id;
 415         remove_query(qm, bottom);
 416         ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
 417
 418         strcpy(result, bottom->q_uuid);
 419
 420 #ifdef NEW_LOGGING
 421         LDAP_LOG( BACK_META, DETAIL1, "Lock CR index = %d\n", temp_id, 0, 0 );
 422 #else
 423         Debug( LDAP_DEBUG_ANY, "Lock CR index = %d\n", temp_id, 0, 0 );
 424 #endif
 425         ldap_pvt_thread_rdwr_wlock(&(qm->templates[temp_id].t_rwlock));
 426         remove_from_template(bottom, (qm->templates+temp_id));
 427 #ifdef NEW_LOGGING
 428         LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES-- %d\n",
 429                 temp_id, qm->templates[temp_id].no_of_queries, 0 );
 430 #else
 431         Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES-- %d\n",
 432                 temp_id, qm->templates[temp_id].no_of_queries, 0 );
 433 #endif
 434 #ifdef NEW_LOGGING
 435         LDAP_LOG( BACK_META, DETAIL1, "Unlock CR index = %d\n", temp_id, 0, 0 );
 436 #else
 437         Debug( LDAP_DEBUG_ANY, "Unlock CR index = %d\n", temp_id, 0, 0 );
 438 #endif
 439         ldap_pvt_thread_rdwr_wunlock(&(qm->templates[temp_id].t_rwlock));
 440         free_query(bottom);
 441         return result;
 442 }
 443
 444 void
 445 remove_from_template (CachedQuery* qc, QueryTemplate* template)
 446 {
 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;
 455         } else {
 456                 qc->next->prev = qc->prev;
 457                 qc->prev->next = qc->next;
 458         }
 459
 460         template->no_of_queries--;
 461 }
 462 #endif