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