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

   1 /* $OpenLDAP$ */
   2 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   3  *
   4  * Copyright 1999-2003 The OpenLDAP Foundation.
   5  * Portions Copyright 2003 IBM Corporation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  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>.
  15  */
  16 /* ACKNOWLEDGEMENTS:
  17  * This work was initially developed by the Apurva Kumar for inclusion
  18  * in OpenLDAP Software.
  19  */
  20
  21 #include "portable.h"
  22
  23 #include <stdio.h>
  24
  25 #include <ac/string.h>
  26
  27 #include "slap.h"
  28 #include "../back-ldap/back-ldap.h"
  29 #include "back-meta.h"
  30
  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,
  34                                    int scope_incoming);
  35
  36 /* check whether query is contained in any of
  37  * the cached queries in template template_index
  38  */
  39 int
  40 query_containment(query_manager* qm,
  41                   Query* query,
  42                   int template_index)
  43 {
  44         QueryTemplate* templa= qm->templates;
  45         CachedQuery* qc;
  46         Query* q;
  47         Query* prev_q;
  48         Filter* inputf = query->filter;
  49         struct berval* base = &(query->base);
  50         int scope = query->scope;
  51         int i,res=0;
  52         Filter* fs;
  53         Filter* fi;
  54         int ret, rc;
  55         const char* text;
  56
  57         MatchingRule* mrule = NULL;
  58         if (inputf != NULL) {
  59 #ifdef NEW_LOGGING
  60                 LDAP_LOG( BACK_META, DETAIL1, "Lock QC index = %d\n",
  61                                 template_index, 0, 0 );
  62 #else
  63                 Debug( LDAP_DEBUG_ANY, "Lock QC index = %d\n",
  64                                 template_index, 0, 0 );
  65 #endif
  66                 ldap_pvt_thread_rdwr_rlock(&(templa[template_index].t_rwlock));
  67                 for(qc=templa[template_index].query; qc != NULL; qc= qc->next) {
  68                         q = (Query*)qc;
  69                         if(base_scope_compare(&(q->base), base, q->scope, scope)) {
  70                                 fi = inputf;
  71                                 fs = q->filter;
  72                                 do {
  73                                         res=0;
  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;
  78                                                 else
  79                                                         ret = 1;
  80                                                 break;
  81                                         case LDAP_FILTER_GE:
  82                                         case LDAP_FILTER_LE:
  83                                                 mrule = fs->f_ava->aa_desc->ad_type->sat_ordering;
  84                                                 break;
  85                                         default:
  86                                                 mrule = NULL;
  87                                         }
  88                                         if (mrule) {
  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) {
  94 #ifdef NEW_LOGGING
  95                                                         LDAP_LOG( BACK_META, DETAIL1,
  96                                                         "Unlock: Exiting QC index=%d\n",
  97                                                         template_index, 0, 0 );
  98 #else
  99                                                         Debug( LDAP_DEBUG_ANY,
 100                                                         "Unlock: Exiting QC index=%d\n",
 101                                                         template_index, 0, 0 );
 102 #endif
 103                                                         ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
 104 #ifdef NEW_LOGGING
 105                                                         LDAP_LOG( BACK_META, DETAIL1,
 106                                                         "query_containment: Required "
 107                                                         "matching rule not defined for "
 108                                                         "a filter attribute",
 109                                                         0, 0, 0 );
 110 #else
 111                                                         Debug( LDAP_DEBUG_ANY,
 112                                                         "query_containment: Required "
 113                                                         "matching rule not defined for "
 114                                                         "a filter attribute",
 115                                                         0, 0, 0 );
 116 #endif
 117                                                         return 0;
 118                                                 }
 119                                         }
 120                                         switch (fs->f_choice) {
 121                                         case LDAP_FILTER_OR:
 122                                         case LDAP_FILTER_AND:
 123                                                 fs = fs->f_and;
 124                                                 fi = fi->f_and;
 125                                                 res=1;
 126                                                 break;
 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(
 132                                                         fs, fi))
 133                                                         res=1;
 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(
 138                                                         fs, fi))
 139                                                         res= 1;
 140                                                 fs=fs->f_next;
 141                                                 fi=fi->f_next;
 142                                                 break;
 143                                         case LDAP_FILTER_PRESENT:
 144                                                 res=1;
 145                                                 fs=fs->f_next;
 146                                                 fi=fi->f_next;
 147                                                 break;
 148                                         case LDAP_FILTER_EQUALITY:
 149                                                 if (ret == 0)
 150                                                         res = 1;
 151                                                 fs=fs->f_next;
 152                                                 fi=fi->f_next;
 153                                                 break;
 154                                         case LDAP_FILTER_GE:
 155                                                 if (ret >= 0)
 156                                                         res = 1;
 157                                                 fs=fs->f_next;
 158                                                 fi=fi->f_next;
 159                                                 break;
 160                                         case LDAP_FILTER_LE:
 161                                                 if (ret <= 0)
 162                                                         res = 1;
 163                                                 fs=fs->f_next;
 164                                                 fi=fi->f_next;
 165                                                 break;
 166                                         case LDAP_FILTER_NOT:
 167                                                 res=0;
 168                                                 break;
 169                                         default:
 170                                                 break;
 171                                         }
 172                                 } while((res) && (fi != NULL) && (fs != NULL));
 173
 174                                 if(res) {
 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);
 179                                         }
 180                                         ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
 181                                         return 1;
 182                                 }
 183                         }
 184                 }
 185 #ifdef NEW_LOGGING
 186                 LDAP_LOG( BACK_META, DETAIL1,
 187                         "Not answerable: Unlock QC index=%d\n",
 188                         template_index, 0, 0 );
 189 #else
 190                 Debug( LDAP_DEBUG_ANY,
 191                         "Not answerable: Unlock QC index=%d\n",
 192                         template_index, 0, 0 );
 193 #endif
 194                 ldap_pvt_thread_rdwr_runlock(&(templa[template_index].t_rwlock));
 195         }
 196         return 0;
 197 }
 198
 199 /* remove_query from LRU list */
 200
 201 void
 202 remove_query (query_manager* qm, CachedQuery* qc)
 203 {
 204         CachedQuery* up;
 205         CachedQuery* down;
 206
 207         if (!qc)
 208                 return;
 209
 210         up = qc->lru_up;
 211         down = qc->lru_down;
 212
 213         if (!up)
 214                 qm->lru_top = down;
 215
 216         if (!down)
 217                 qm->lru_bottom = up;
 218
 219         if (down)
 220                 down->lru_up = up;
 221
 222         if (up)
 223                 up->lru_down = down;
 224
 225         qc->lru_up = qc->lru_down = NULL;
 226 }
 227
 228 /* add query on top of LRU list */
 229 void
 230 add_query_on_top (query_manager* qm, CachedQuery* qc)
 231 {
 232         CachedQuery* top = qm->lru_top;
 233         Query* q = (Query*)qc;
 234
 235         qm->lru_top = qc;
 236
 237         if (top)
 238                 top->lru_up = qc;
 239         else
 240                 qm->lru_bottom = qc;
 241
 242         qc->lru_down = top;
 243         qc->lru_up = NULL;
 244 #ifdef NEW_LOGGING
 245         LDAP_LOG( BACK_META, DETAIL1, "Base of added query = %s\n",
 246                         q->base.bv_val, 0, 0 );
 247 #else
 248         Debug( LDAP_DEBUG_ANY, "Base of added query = %s\n",
 249                         q->base.bv_val, 0, 0 );
 250 #endif
 251 }
 252
 253 void
 254 free_query (CachedQuery* qc)
 255 {
 256         Query* q = (Query*)qc;
 257         free(qc->q_uuid);
 258         filter_free(q->filter);
 259         free (q->base.bv_val);
 260
 261         free(q->attrs);
 262         free(qc);
 263 }
 264
 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,
 269         int scope_stored,
 270         int scope_incoming      )
 271 {
 272         struct berval ndn_incoming = { 0L, NULL };
 273         struct berval pdn_incoming = { 0L, NULL };
 274         struct berval ndn_stored = { 0L, NULL };
 275
 276         int i;
 277
 278         if (scope_stored < scope_incoming)
 279                 return 0;
 280
 281         dnNormalize(0, NULL, NULL, dn_incoming, &ndn_incoming, NULL);
 282         dnNormalize(0, NULL, NULL, dn_stored, &ndn_stored, NULL);
 283
 284         i = dnIsSuffix(&ndn_incoming, &ndn_stored);
 285
 286         if ( i == 0 )
 287                 return 0;
 288
 289         switch(scope_stored) {
 290         case LDAP_SCOPE_BASE:
 291                 if (strlen(ndn_incoming.bv_val) == strlen(ndn_stored.bv_val))
 292                         return 1;
 293                 else
 294                         return 0;
 295                 break;
 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)
 301                                 return 1;
 302                         else
 303                                 return 0;
 304                         break;
 305                 case LDAP_SCOPE_ONELEVEL:
 306                         if (ndn_incoming.bv_len == ndn_stored.bv_len)
 307                                 return 1;
 308                         else
 309                                 return 0;
 310                         break;
 311                 default:
 312                         return 0;
 313                         break;
 314                 }
 315         case LDAP_SCOPE_SUBTREE:
 316                 return 1;
 317                 break;
 318         default:
 319                 return 0;
 320                 break;
 321     }
 322 }
 323
 324 /* Add query to query cache */
 325 void add_query(
 326         query_manager* qm,
 327         Query* query,
 328         int template_index,
 329         char* uuid,
 330         struct exception* result)
 331 {
 332         CachedQuery* new_cached_query = (CachedQuery*) malloc(sizeof(CachedQuery));
 333         QueryTemplate* templ = (qm->templates)+template_index;
 334         Query* new_query;
 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;
 340 #ifdef NEW_LOGGING
 341         LDAP_LOG( BACK_META, DETAIL1, "Added query expires at %ld\n",
 342                         (long) new_cached_query->expiry_time, 0, 0 );
 343 #else
 344         Debug( LDAP_DEBUG_ANY, "Added query expires at %ld\n",
 345                         (long) new_cached_query->expiry_time, 0, 0 );
 346 #endif
 347         new_query = (Query*)new_cached_query;
 348
 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;
 354
 355         /* Adding a query    */
 356 #ifdef NEW_LOGGING
 357         LDAP_LOG( BACK_META, DETAIL1, "Lock AQ index = %d\n",
 358                         template_index, 0, 0 );
 359 #else
 360         Debug( LDAP_DEBUG_ANY, "Lock AQ index = %d\n",
 361                         template_index, 0, 0 );
 362 #endif
 363         ldap_pvt_thread_rdwr_wlock(&templ->t_rwlock);
 364         if (templ->query == NULL)
 365                 templ->query_last = new_cached_query;
 366         else
 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++;
 372 #ifdef NEW_LOGGING
 373         LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES++ %d\n",
 374                         template_index, templ->no_of_queries, 0 );
 375 #else
 376         Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES++ %d\n",
 377                         template_index, templ->no_of_queries, 0 );
 378 #endif
 379
 380 #ifdef NEW_LOGGING
 381         LDAP_LOG( BACK_META, DETAIL1, "Unlock AQ index = %d \n",
 382                         template_index, 0, 0 );
 383 #else
 384         Debug( LDAP_DEBUG_ANY, "Unlock AQ index = %d \n",
 385                         template_index, 0, 0 );
 386 #endif
 387         ldap_pvt_thread_rdwr_wunlock(&templ->t_rwlock);
 388
 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);
 393
 394 }
 395
 396 /* remove bottom query of LRU list from the query cache */
 397 char* cache_replacement(query_manager* qm)
 398 {
 399         char* result = (char*)(malloc(40));
 400         CachedQuery* bottom;
 401         QueryTemplate* templ;
 402         CachedQuery* query_curr;
 403         int temp_id;
 404
 405         ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
 406         bottom = qm->lru_bottom;
 407
 408         if (!bottom) {
 409 #ifdef NEW_LOGGING
 410                 LDAP_LOG ( BACK_META, DETAIL1,
 411                         "Cache replacement invoked without "
 412                         "any query in LRU list\n", 0, 0, 0 );
 413 #else
 414                 Debug ( LDAP_DEBUG_ANY,
 415                         "Cache replacement invoked without "
 416                         "any query in LRU list\n", 0, 0, 0 );
 417 #endif
 418                 return 0;
 419         }
 420
 421         temp_id = bottom->template_id;
 422         remove_query(qm, bottom);
 423         ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
 424
 425         strcpy(result, bottom->q_uuid);
 426
 427 #ifdef NEW_LOGGING
 428         LDAP_LOG( BACK_META, DETAIL1, "Lock CR index = %d\n", temp_id, 0, 0 );
 429 #else
 430         Debug( LDAP_DEBUG_ANY, "Lock CR index = %d\n", temp_id, 0, 0 );
 431 #endif
 432         ldap_pvt_thread_rdwr_wlock(&(qm->templates[temp_id].t_rwlock));
 433         remove_from_template(bottom, (qm->templates+temp_id));
 434 #ifdef NEW_LOGGING
 435         LDAP_LOG( BACK_META, DETAIL1, "TEMPLATE %d QUERIES-- %d\n",
 436                 temp_id, qm->templates[temp_id].no_of_queries, 0 );
 437 #else
 438         Debug( LDAP_DEBUG_ANY, "TEMPLATE %d QUERIES-- %d\n",
 439                 temp_id, qm->templates[temp_id].no_of_queries, 0 );
 440 #endif
 441 #ifdef NEW_LOGGING
 442         LDAP_LOG( BACK_META, DETAIL1, "Unlock CR index = %d\n", temp_id, 0, 0 );
 443 #else
 444         Debug( LDAP_DEBUG_ANY, "Unlock CR index = %d\n", temp_id, 0, 0 );
 445 #endif
 446         ldap_pvt_thread_rdwr_wunlock(&(qm->templates[temp_id].t_rwlock));
 447         free_query(bottom);
 448         return result;
 449 }
 450
 451 void
 452 remove_from_template (CachedQuery* qc, QueryTemplate* template)
 453 {
 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;
 462         } else {
 463                 qc->next->prev = qc->prev;
 464                 qc->prev->next = qc->next;
 465         }
 466
 467         template->no_of_queries--;
 468 }