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