git.sur5r.net Git - openldap/blob - servers/slapd/overlays/pcache.c

   1 /* $OpenLDAP$ */
   2 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   3  *
   4  * Copyright 2003-2009 The OpenLDAP Foundation.
   5  * Portions Copyright 2003 IBM Corporation.
   6  * Portions Copyright 2003 Symas Corporation.
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted only as authorized by the OpenLDAP
  11  * Public License.
  12  *
  13  * A copy of this license is available in the file LICENSE in the
  14  * top-level directory of the distribution or, alternatively, at
  15  * <http://www.OpenLDAP.org/license.html>.
  16  */
  17 /* ACKNOWLEDGEMENTS:
  18  * This work was initially developed by Apurva Kumar for inclusion
  19  * in OpenLDAP Software and subsequently rewritten by Howard Chu.
  20  */
  21
  22 #include "portable.h"
  23
  24 #ifdef SLAPD_OVER_PROXYCACHE
  25
  26 #include <stdio.h>
  27
  28 #include <ac/string.h>
  29 #include <ac/time.h>
  30
  31 #include "slap.h"
  32 #include "lutil.h"
  33 #include "ldap_rq.h"
  34 #include "avl.h"
  35
  36 #include "config.h"
  37
  38 #ifdef LDAP_DEVEL
  39 /*
  40  * Control that allows to access the private DB
  41  * instead of the public one
  42  */
  43 #define PCACHE_CONTROL_PRIVDB           "1.3.6.1.4.1.4203.666.11.9.5.1"
  44
  45 /*
  46  * Extended Operation that allows to remove a query from the cache
  47  */
  48 #define PCACHE_EXOP_QUERY_DELETE        "1.3.6.1.4.1.4203.666.11.9.6.1"
  49 #endif
  50
  51 /* query cache structs */
  52 /* query */
  53
  54 typedef struct Query_s {
  55         Filter*         filter;         /* Search Filter */
  56         struct berval   base;           /* Search Base */
  57         int             scope;          /* Search scope */
  58 } Query;
  59
  60 struct query_template_s;
  61
  62 typedef struct Qbase_s {
  63         Avlnode *scopes[4];             /* threaded AVL trees of cached queries */
  64         struct berval base;
  65         int queries;
  66 } Qbase;
  67
  68 /* struct representing a cached query */
  69 typedef struct cached_query_s {
  70         Filter                                  *filter;
  71         Filter                                  *first;
  72         Qbase                                   *qbase;
  73         int                                             scope;
  74         struct berval                   q_uuid;         /* query identifier */
  75         int                                             q_sizelimit;
  76         struct query_template_s         *qtemp; /* template of the query */
  77         time_t                                          expiry_time;    /* time till the query is considered valid */
  78         struct cached_query_s           *next;          /* next query in the template */
  79         struct cached_query_s           *prev;          /* previous query in the template */
  80         struct cached_query_s           *lru_up;        /* previous query in the LRU list */
  81         struct cached_query_s           *lru_down;      /* next query in the LRU list */
  82         ldap_pvt_thread_rdwr_t          rwlock;
  83 } CachedQuery;
  84
  85 /*
  86  * URL representation:
  87  *
  88  * ldap:///<base>??<scope>?<filter>?x-uuid=<uid>,x-template=<template>,x-attrset=<attrset>,x-expiry=<expiry>
  89  *
  90  * <base> ::= CachedQuery.qbase->base
  91  * <scope> ::= CachedQuery.scope
  92  * <filter> ::= filter2bv(CachedQuery.filter)
  93  * <uuid> ::= CachedQuery.q_uuid
  94  * <attrset> ::= CachedQuery.qtemp->attr_set_index
  95  * <expiry> ::= CachedQuery.expiry_time
  96  *
  97  * quick hack: parse URI, call add_query() and then fix
  98  * CachedQuery.expiry_time and CachedQuery.q_uuid
  99  */
 100
 101 /*
 102  * Represents a set of projected attributes.
 103  */
 104
 105 struct attr_set {
 106         struct query_template_s *templates;
 107         AttributeName*  attrs;          /* specifies the set */
 108         unsigned        flags;
 109 #define PC_CONFIGURED   (0x1)
 110 #define PC_REFERENCED   (0x2)
 111 #define PC_GOT_OC               (0x4)
 112         int             count;          /* number of attributes */
 113 };
 114
 115 /* struct representing a query template
 116  * e.g. template string = &(cn=)(mail=)
 117  */
 118 typedef struct query_template_s {
 119         struct query_template_s *qtnext;
 120         struct query_template_s *qmnext;
 121
 122         Avlnode*                qbase;
 123         CachedQuery*    query;          /* most recent query cached for the template */
 124         CachedQuery*    query_last;     /* oldest query cached for the template */
 125         ldap_pvt_thread_rdwr_t t_rwlock; /* Rd/wr lock for accessing queries in the template */
 126         struct berval   querystr;       /* Filter string corresponding to the QT */
 127
 128         int             attr_set_index; /* determines the projected attributes */
 129         int             no_of_queries;  /* Total number of queries in the template */
 130         time_t          ttl;            /* TTL for the queries of this template */
 131         time_t          negttl;         /* TTL for negative results */
 132         time_t          limitttl;       /* TTL for sizelimit exceeding results */
 133         struct attr_set t_attrs;        /* filter attrs + attr_set */
 134 } QueryTemplate;
 135
 136 typedef enum {
 137         PC_IGNORE = 0,
 138         PC_POSITIVE,
 139         PC_NEGATIVE,
 140         PC_SIZELIMIT
 141 } pc_caching_reason_t;
 142
 143 static const char *pc_caching_reason_str[] = {
 144         "IGNORE",
 145         "POSITIVE",
 146         "NEGATIVE",
 147         "SIZELIMIT",
 148
 149         NULL
 150 };
 151
 152 struct query_manager_s;
 153
 154 /* prototypes for functions for 1) query containment
 155  * 2) query addition, 3) cache replacement
 156  */
 157 typedef CachedQuery *(QCfunc)(Operation *op, struct query_manager_s*,
 158         Query*, QueryTemplate*);
 159 typedef CachedQuery *(AddQueryfunc)(Operation *op, struct query_manager_s*,
 160         Query*, QueryTemplate*, pc_caching_reason_t, int wlock);
 161 typedef void (CRfunc)(struct query_manager_s*, struct berval*);
 162
 163 /* LDAP query cache */
 164 typedef struct query_manager_s {
 165         struct attr_set*        attr_sets;              /* possible sets of projected attributes */
 166         QueryTemplate*          templates;              /* cacheable templates */
 167
 168         CachedQuery*            lru_top;                /* top and bottom of LRU list */
 169         CachedQuery*            lru_bottom;
 170
 171         ldap_pvt_thread_mutex_t         lru_mutex;      /* mutex for accessing LRU list */
 172
 173         /* Query cache methods */
 174         QCfunc                  *qcfunc;                        /* Query containment*/
 175         CRfunc                  *crfunc;                        /* cache replacement */
 176         AddQueryfunc    *addfunc;                       /* add query */
 177 } query_manager;
 178
 179 /* LDAP query cache manager */
 180 typedef struct cache_manager_s {
 181         BackendDB       db;     /* underlying database */
 182         unsigned long   num_cached_queries;             /* total number of cached queries */
 183         unsigned long   max_queries;                    /* upper bound on # of cached queries */
 184         int             save_queries;                   /* save cached queries across restarts */
 185         int     check_cacheability;             /* check whether a query is cacheable */
 186         int     numattrsets;                    /* number of attribute sets */
 187         int     cur_entries;                    /* current number of entries cached */
 188         int     max_entries;                    /* max number of entries cached */
 189         int     num_entries_limit;              /* max # of entries in a cacheable query */
 190
 191         char    response_cb;                    /* install the response callback
 192                                                  * at the tail of the callback list */
 193 #define PCACHE_RESPONSE_CB_HEAD 0
 194 #define PCACHE_RESPONSE_CB_TAIL 1
 195         char    defer_db_open;                  /* defer open for online add */
 196
 197         time_t  cc_period;              /* interval between successive consistency checks (sec) */
 198 #define PCACHE_CC_PAUSED        1
 199 #define PCACHE_CC_OFFLINE       2
 200         int     cc_paused;
 201         void    *cc_arg;
 202
 203         ldap_pvt_thread_mutex_t         cache_mutex;
 204
 205         query_manager*   qm;    /* query cache managed by the cache manager */
 206 } cache_manager;
 207
 208 static int pcache_debug;
 209
 210 #ifdef PCACHE_CONTROL_PRIVDB
 211 static int privDB_cid;
 212 #endif /* PCACHE_CONTROL_PRIVDB */
 213
 214 static AttributeDescription *ad_queryId, *ad_cachedQueryURL;
 215 static struct {
 216         char    *desc;
 217         AttributeDescription **adp;
 218 } as[] = {
 219         { "( 1.3.6.1.4.1.4203.666.11.9.1.1 "
 220                 "NAME 'queryId' "
 221                 "DESC 'ID of query the entry belongs to, formatted as a UUID' "
 222                 "EQUALITY octetStringMatch "
 223                 "SYNTAX 1.3.6.1.4.1.1466.115.121.1.40{64} "
 224                 "NO-USER-MODIFICATION "
 225                 "USAGE directoryOperation )",
 226                 &ad_queryId },
 227         { "( 1.3.6.1.4.1.4203.666.11.9.1.2 "
 228                 "NAME 'cachedQueryURL' "
 229                 "DESC 'URI describing a cached query' "
 230                 "EQUALITY caseExactMatch "
 231                 "SYNTAX 1.3.6.1.4.1.1466.115.121.1.15 "
 232                 "NO-USER-MODIFICATION "
 233                 "USAGE directoryOperation )",
 234                 &ad_cachedQueryURL },
 235         { NULL }
 236 };
 237
 238 static int
 239 filter2template(
 240         Operation               *op,
 241         Filter                  *f,
 242         struct                  berval *fstr,
 243         AttributeName**         filter_attrs,
 244         int*                    filter_cnt,
 245         int*                    filter_got_oc );
 246
 247 static CachedQuery *
 248 add_query(
 249         Operation *op,
 250         query_manager* qm,
 251         Query* query,
 252         QueryTemplate *templ,
 253         pc_caching_reason_t why,
 254         int wlock);
 255
 256 static int
 257 remove_query_data(
 258         Operation       *op,
 259         SlapReply       *rs,
 260         struct berval   *query_uuid );
 261
 262 /*
 263  * Turn a cached query into its URL representation
 264  */
 265 static int
 266 query2url( Operation *op, CachedQuery *q, struct berval *urlbv )
 267 {
 268         struct berval   bv_scope,
 269                         bv_filter;
 270         char            attrset_buf[ LDAP_PVT_INTTYPE_CHARS( unsigned long ) ],
 271                         expiry_buf[ LDAP_PVT_INTTYPE_CHARS( unsigned long ) ],
 272                         *ptr;
 273         ber_len_t       attrset_len,
 274                         expiry_len;
 275
 276         ldap_pvt_scope2bv( q->scope, &bv_scope );
 277         filter2bv_x( op, q->filter, &bv_filter );
 278         attrset_len = sprintf( attrset_buf,
 279                 "%lu", (unsigned long)q->qtemp->attr_set_index );
 280         expiry_len = sprintf( expiry_buf,
 281                 "%lu", (unsigned long)q->expiry_time );
 282
 283         urlbv->bv_len = STRLENOF( "ldap:///" )
 284                 + q->qbase->base.bv_len
 285                 + STRLENOF( "??" )
 286                 + bv_scope.bv_len
 287                 + STRLENOF( "?" )
 288                 + bv_filter.bv_len
 289                 + STRLENOF( "?x-uuid=" )
 290                 + q->q_uuid.bv_len
 291                 + STRLENOF( ",x-attrset=" )
 292                 + attrset_len
 293                 + STRLENOF( ",x-expiry=" )
 294                 + expiry_len;
 295         ptr = urlbv->bv_val = ber_memalloc_x( urlbv->bv_len + 1, op->o_tmpmemctx );
 296         ptr = lutil_strcopy( ptr, "ldap:///" );
 297         ptr = lutil_strcopy( ptr, q->qbase->base.bv_val );
 298         ptr = lutil_strcopy( ptr, "??" );
 299         ptr = lutil_strcopy( ptr, bv_scope.bv_val );
 300         ptr = lutil_strcopy( ptr, "?" );
 301         ptr = lutil_strcopy( ptr, bv_filter.bv_val );
 302         ptr = lutil_strcopy( ptr, "?x-uuid=" );
 303         ptr = lutil_strcopy( ptr, q->q_uuid.bv_val );
 304         ptr = lutil_strcopy( ptr, ",x-attrset=" );
 305         ptr = lutil_strcopy( ptr, attrset_buf );
 306         ptr = lutil_strcopy( ptr, ",x-expiry=" );
 307         ptr = lutil_strcopy( ptr, expiry_buf );
 308
 309         ber_memfree_x( bv_filter.bv_val, op->o_tmpmemctx );
 310
 311         return 0;
 312 }
 313
 314 /*
 315  * Turn an URL representing a formerly cached query into a cached query,
 316  * and try to cache it
 317  */
 318 static int
 319 url2query(
 320         char            *url,
 321         Operation       *op,
 322         query_manager   *qm )
 323 {
 324         Query           query = { 0 };
 325         QueryTemplate   *qt;
 326         CachedQuery     *cq;
 327         LDAPURLDesc     *lud = NULL;
 328         struct berval   base,
 329                         tempstr = BER_BVNULL,
 330                         uuid;
 331         int             attrset;
 332         time_t          expiry_time;
 333         int             i,
 334                         got_uuid = 0,
 335                         got_attrset = 0,
 336                         got_expiry = 0,
 337                         rc = 0;
 338
 339         rc = ldap_url_parse( url, &lud );
 340         if ( rc != LDAP_URL_SUCCESS ) {
 341                 return -1;
 342         }
 343
 344         /* non-allowed fields */
 345         if ( lud->lud_host != NULL ) {
 346                 rc = 1;
 347                 goto error;
 348         }
 349
 350         if ( lud->lud_attrs != NULL ) {
 351                 rc = 1;
 352                 goto error;
 353         }
 354
 355         /* be pedantic */
 356         if ( strcmp( lud->lud_scheme, "ldap" ) != 0 ) {
 357                 rc = 1;
 358                 goto error;
 359         }
 360
 361         /* required fields */
 362         if ( lud->lud_dn == NULL || lud->lud_dn[ 0 ] == '\0' ) {
 363                 rc = 1;
 364                 goto error;
 365         }
 366
 367         switch ( lud->lud_scope ) {
 368         case LDAP_SCOPE_BASE:
 369         case LDAP_SCOPE_ONELEVEL:
 370         case LDAP_SCOPE_SUBTREE:
 371         case LDAP_SCOPE_SUBORDINATE:
 372                 break;
 373
 374         default:
 375                 rc = 1;
 376                 goto error;
 377         }
 378
 379         if ( lud->lud_filter == NULL || lud->lud_filter[ 0 ] == '\0' ) {
 380                 rc = 1;
 381                 goto error;
 382         }
 383
 384         if ( lud->lud_exts == NULL ) {
 385                 rc = 1;
 386                 goto error;
 387         }
 388
 389         for ( i = 0; lud->lud_exts[ i ] != NULL; i++ ) {
 390                 if ( strncmp( lud->lud_exts[ i ], "x-uuid=", STRLENOF( "x-uuid=" ) ) == 0 ) {
 391                         struct berval   tmpUUID;
 392                         Syntax          *syn_UUID = slap_schema.si_ad_entryUUID->ad_type->sat_syntax;
 393
 394                         ber_str2bv( &lud->lud_exts[ i ][ STRLENOF( "x-uuid=" ) ], 0, 0, &tmpUUID );
 395                         rc = syn_UUID->ssyn_pretty( syn_UUID, &tmpUUID, &uuid, NULL );
 396                         if ( rc != LDAP_SUCCESS ) {
 397                                 goto error;
 398                         }
 399                         got_uuid = 1;
 400
 401                 } else if ( strncmp( lud->lud_exts[ i ], "x-attrset=", STRLENOF( "x-attrset=" ) ) == 0 ) {
 402                         rc = lutil_atoi( &attrset, &lud->lud_exts[ i ][ STRLENOF( "x-attrset=" ) ] );
 403                         if ( rc ) {
 404                                 goto error;
 405                         }
 406                         got_attrset = 1;
 407
 408                 } else if ( strncmp( lud->lud_exts[ i ], "x-expiry=", STRLENOF( "x-expiry=" ) ) == 0 ) {
 409                         unsigned long l;
 410
 411                         rc = lutil_atoul( &l, &lud->lud_exts[ i ][ STRLENOF( "x-expiry=" ) ] );
 412                         if ( rc ) {
 413                                 goto error;
 414                         }
 415                         expiry_time = (time_t)l;
 416                         got_expiry = 1;
 417
 418                 } else {
 419                         rc = -1;
 420                         goto error;
 421                 }
 422         }
 423
 424         if ( !got_uuid ) {
 425                 rc = 1;
 426                 goto error;
 427         }
 428
 429         if ( !got_attrset ) {
 430                 rc = 1;
 431                 goto error;
 432         }
 433
 434         if ( !got_expiry ) {
 435                 rc = 1;
 436                 goto error;
 437         }
 438
 439         /* ignore expired queries */
 440         if ( expiry_time <= slap_get_time()) {
 441                 Operation       op2 = *op;
 442                 SlapReply       rs2 = { 0 };
 443
 444                 memset( &op2.oq_search, 0, sizeof( op2.oq_search ) );
 445
 446                 (void)remove_query_data( &op2, &rs2, &uuid );
 447
 448                 rc = 0;
 449
 450         } else {
 451                 ber_str2bv( lud->lud_dn, 0, 0, &base );
 452                 rc = dnNormalize( 0, NULL, NULL, &base, &query.base, NULL );
 453                 if ( rc != LDAP_SUCCESS ) {
 454                         goto error;
 455                 }
 456                 query.scope = lud->lud_scope;
 457                 query.filter = str2filter( lud->lud_filter );
 458
 459                 tempstr.bv_val = ch_malloc( strlen( lud->lud_filter ) + 1 );
 460                 tempstr.bv_len = 0;
 461                 if ( filter2template( op, query.filter, &tempstr, NULL, NULL, NULL ) ) {
 462                         ch_free( tempstr.bv_val );
 463                         rc = -1;
 464                         goto error;
 465                 }
 466
 467                 /* check for query containment */
 468                 qt = qm->attr_sets[attrset].templates;
 469                 for ( ; qt; qt = qt->qtnext ) {
 470                         /* find if template i can potentially answer tempstr */
 471                         if ( bvmatch( &qt->querystr, &tempstr ) ) {
 472                                 break;
 473                         }
 474                 }
 475
 476                 if ( qt == NULL ) {
 477                         rc = 1;
 478                         goto error;
 479                 }
 480
 481                 cq = add_query( op, qm, &query, qt, PC_POSITIVE, 0 );
 482                 if ( cq != NULL ) {
 483                         cq->expiry_time = expiry_time;
 484                         cq->q_uuid = uuid;
 485
 486                         /* it's now into cq->filter */
 487                         BER_BVZERO( &uuid );
 488                         query.filter = NULL;
 489
 490                 } else {
 491                         rc = 1;
 492                 }
 493         }
 494
 495 error:;
 496         if ( query.filter != NULL ) filter_free( query.filter );
 497         if ( !BER_BVISNULL( &tempstr ) ) ch_free( tempstr.bv_val );
 498         if ( !BER_BVISNULL( &query.base ) ) ch_free( query.base.bv_val );
 499         if ( !BER_BVISNULL( &uuid ) ) ch_free( uuid.bv_val );
 500         if ( lud != NULL ) ldap_free_urldesc( lud );
 501
 502         return rc;
 503 }
 504
 505 /* Return 1 for an added entry, else 0 */
 506 static int
 507 merge_entry(
 508         Operation               *op,
 509         Entry                   *e,
 510         struct berval*          query_uuid )
 511 {
 512         int             rc;
 513         Modifications* modlist = NULL;
 514         const char*     text = NULL;
 515         Attribute               *attr;
 516         char                    textbuf[SLAP_TEXT_BUFLEN];
 517         size_t                  textlen = sizeof(textbuf);
 518
 519         SlapReply sreply = {REP_RESULT};
 520
 521         slap_callback cb = { NULL, slap_null_cb, NULL, NULL };
 522
 523         attr = e->e_attrs;
 524         e->e_attrs = NULL;
 525
 526         /* add queryId attribute */
 527         attr_merge_one( e, ad_queryId, query_uuid, NULL );
 528
 529         /* append the attribute list from the fetched entry */
 530         e->e_attrs->a_next = attr;
 531
 532         op->o_tag = LDAP_REQ_ADD;
 533         op->o_protocol = LDAP_VERSION3;
 534         op->o_callback = &cb;
 535         op->o_time = slap_get_time();
 536         op->o_do_not_cache = 1;
 537
 538         op->ora_e = e;
 539         op->o_req_dn = e->e_name;
 540         op->o_req_ndn = e->e_nname;
 541         rc = op->o_bd->be_add( op, &sreply );
 542
 543         if ( rc != LDAP_SUCCESS ) {
 544                 if ( rc == LDAP_ALREADY_EXISTS ) {
 545                         slap_entry2mods( e, &modlist, &text, textbuf, textlen );
 546                         modlist->sml_op = LDAP_MOD_ADD;
 547                         op->o_tag = LDAP_REQ_MODIFY;
 548                         op->orm_modlist = modlist;
 549                         op->o_bd->be_modify( op, &sreply );
 550                         slap_mods_free( modlist, 1 );
 551                 } else if ( rc == LDAP_REFERRAL ||
 552                                         rc == LDAP_NO_SUCH_OBJECT ) {
 553                         syncrepl_add_glue( op, e );
 554                         e = NULL;
 555                         rc = 1;
 556                 }
 557                 if ( e ) {
 558                         entry_free( e );
 559                         rc = 0;
 560                 }
 561         } else {
 562                 if ( op->ora_e == e )
 563                         be_entry_release_w( op, e );
 564                 rc = 1;
 565         }
 566
 567         return rc;
 568 }
 569
 570 /* Length-ordered sort on normalized DNs */
 571 static int pcache_dn_cmp( const void *v1, const void *v2 )
 572 {
 573         const Qbase *q1 = v1, *q2 = v2;
 574
 575         int rc = q1->base.bv_len - q2->base.bv_len;
 576         if ( rc == 0 )
 577                 rc = strncmp( q1->base.bv_val, q2->base.bv_val, q1->base.bv_len );
 578         return rc;
 579 }
 580
 581 static int lex_bvcmp( struct berval *bv1, struct berval *bv2 )
 582 {
 583         int len, dif;
 584         dif = bv1->bv_len - bv2->bv_len;
 585         len = bv1->bv_len;
 586         if ( dif > 0 ) len -= dif;
 587         len = memcmp( bv1->bv_val, bv2->bv_val, len );
 588         if ( !len )
 589                 len = dif;
 590         return len;
 591 }
 592
 593 /* compare the current value in each filter */
 594 static int pcache_filter_cmp( Filter *f1, Filter *f2 )
 595 {
 596         int rc, weight1, weight2;
 597
 598         switch( f1->f_choice ) {
 599         case LDAP_FILTER_PRESENT:
 600                 weight1 = 0;
 601                 break;
 602         case LDAP_FILTER_EQUALITY:
 603         case LDAP_FILTER_GE:
 604         case LDAP_FILTER_LE:
 605                 weight1 = 1;
 606                 break;
 607         default:
 608                 weight1 = 2;
 609         }
 610         switch( f2->f_choice ) {
 611         case LDAP_FILTER_PRESENT:
 612                 weight2 = 0;
 613                 break;
 614         case LDAP_FILTER_EQUALITY:
 615         case LDAP_FILTER_GE:
 616         case LDAP_FILTER_LE:
 617                 weight2 = 1;
 618                 break;
 619         default:
 620                 weight2 = 2;
 621         }
 622         rc = weight1 - weight2;
 623         if ( !rc ) {
 624                 switch( weight1 ) {
 625                 case 0:
 626                         break;
 627                 case 1:
 628                         rc = lex_bvcmp( &f1->f_av_value, &f2->f_av_value );
 629                         break;
 630                 case 2:
 631                         if ( f1->f_choice == LDAP_FILTER_SUBSTRINGS ) {
 632                                 rc = 0;
 633                                 if ( !BER_BVISNULL( &f1->f_sub_initial )) {
 634                                         if ( !BER_BVISNULL( &f2->f_sub_initial )) {
 635                                                 rc = lex_bvcmp( &f1->f_sub_initial,
 636                                                         &f2->f_sub_initial );
 637                                         } else {
 638                                                 rc = 1;
 639                                         }
 640                                 } else if ( !BER_BVISNULL( &f2->f_sub_initial )) {
 641                                         rc = -1;
 642                                 }
 643                                 if ( rc ) break;
 644                                 if ( f1->f_sub_any ) {
 645                                         if ( f2->f_sub_any ) {
 646                                                 rc = lex_bvcmp( f1->f_sub_any,
 647                                                         f2->f_sub_any );
 648                                         } else {
 649                                                 rc = 1;
 650                                         }
 651                                 } else if ( f2->f_sub_any ) {
 652                                         rc = -1;
 653                                 }
 654                                 if ( rc ) break;
 655                                 if ( !BER_BVISNULL( &f1->f_sub_final )) {
 656                                         if ( !BER_BVISNULL( &f2->f_sub_final )) {
 657                                                 rc = lex_bvcmp( &f1->f_sub_final,
 658                                                         &f2->f_sub_final );
 659                                         } else {
 660                                                 rc = 1;
 661                                         }
 662                                 } else if ( !BER_BVISNULL( &f2->f_sub_final )) {
 663                                         rc = -1;
 664                                 }
 665                         } else {
 666                                 rc = lex_bvcmp( &f1->f_mr_value,
 667                                         &f2->f_mr_value );
 668                         }
 669                         break;
 670                 }
 671                 if ( !rc ) {
 672                         f1 = f1->f_next;
 673                         f2 = f2->f_next;
 674                         if ( f1 || f2 ) {
 675                                 if ( !f1 )
 676                                         rc = -1;
 677                                 else if ( !f2 )
 678                                         rc = 1;
 679                                 else {
 680                                         while ( f1->f_choice == LDAP_FILTER_AND || f1->f_choice == LDAP_FILTER_OR )
 681                                                 f1 = f1->f_and;
 682                                         while ( f2->f_choice == LDAP_FILTER_AND || f2->f_choice == LDAP_FILTER_OR )
 683                                                 f2 = f2->f_and;
 684                                         rc = pcache_filter_cmp( f1, f2 );
 685                                 }
 686                         }
 687                 }
 688         }
 689         return rc;
 690 }
 691
 692 /* compare filters in each query */
 693 static int pcache_query_cmp( const void *v1, const void *v2 )
 694 {
 695         const CachedQuery *q1 = v1, *q2 =v2;
 696         return pcache_filter_cmp( q1->first, q2->first );
 697 }
 698
 699 /* add query on top of LRU list */
 700 static void
 701 add_query_on_top (query_manager* qm, CachedQuery* qc)
 702 {
 703         CachedQuery* top = qm->lru_top;
 704
 705         qm->lru_top = qc;
 706
 707         if (top)
 708                 top->lru_up = qc;
 709         else
 710                 qm->lru_bottom = qc;
 711
 712         qc->lru_down = top;
 713         qc->lru_up = NULL;
 714         Debug( pcache_debug, "Base of added query = %s\n",
 715                         qc->qbase->base.bv_val, 0, 0 );
 716 }
 717
 718 /* remove_query from LRU list */
 719
 720 static void
 721 remove_query (query_manager* qm, CachedQuery* qc)
 722 {
 723         CachedQuery* up;
 724         CachedQuery* down;
 725
 726         if (!qc)
 727                 return;
 728
 729         up = qc->lru_up;
 730         down = qc->lru_down;
 731
 732         if (!up)
 733                 qm->lru_top = down;
 734
 735         if (!down)
 736                 qm->lru_bottom = up;
 737
 738         if (down)
 739                 down->lru_up = up;
 740
 741         if (up)
 742                 up->lru_down = down;
 743
 744         qc->lru_up = qc->lru_down = NULL;
 745 }
 746
 747 /* find and remove string2 from string1
 748  * from start if position = 1,
 749  * from end if position = 3,
 750  * from anywhere if position = 2
 751  * string1 is overwritten if position = 2.
 752  */
 753
 754 static int
 755 find_and_remove(struct berval* ber1, struct berval* ber2, int position)
 756 {
 757         int ret=0;
 758
 759         if ( !ber2->bv_val )
 760                 return 1;
 761         if ( !ber1->bv_val )
 762                 return 0;
 763
 764         switch( position ) {
 765         case 1:
 766                 if ( ber1->bv_len >= ber2->bv_len && !memcmp( ber1->bv_val,
 767                         ber2->bv_val, ber2->bv_len )) {
 768                         ret = 1;
 769                         ber1->bv_val += ber2->bv_len;
 770                         ber1->bv_len -= ber2->bv_len;
 771                 }
 772                 break;
 773         case 2: {
 774                 char *temp;
 775                 ber1->bv_val[ber1->bv_len] = '\0';
 776                 temp = strstr( ber1->bv_val, ber2->bv_val );
 777                 if ( temp ) {
 778                         strcpy( temp, temp+ber2->bv_len );
 779                         ber1->bv_len -= ber2->bv_len;
 780                         ret = 1;
 781                 }
 782                 break;
 783                 }
 784         case 3:
 785                 if ( ber1->bv_len >= ber2->bv_len &&
 786                         !memcmp( ber1->bv_val+ber1->bv_len-ber2->bv_len, ber2->bv_val,
 787                                 ber2->bv_len )) {
 788                         ret = 1;
 789                         ber1->bv_len -= ber2->bv_len;
 790                 }
 791                 break;
 792         }
 793         return ret;
 794 }
 795
 796
 797 static struct berval*
 798 merge_init_final(Operation *op, struct berval* init, struct berval* any,
 799         struct berval* final)
 800 {
 801         struct berval* merged, *temp;
 802         int i, any_count, count;
 803
 804         for (any_count=0; any && any[any_count].bv_val; any_count++)
 805                 ;
 806
 807         count = any_count;
 808
 809         if (init->bv_val)
 810                 count++;
 811         if (final->bv_val)
 812                 count++;
 813
 814         merged = (struct berval*)op->o_tmpalloc( (count+1)*sizeof(struct berval),
 815                 op->o_tmpmemctx );
 816         temp = merged;
 817
 818         if (init->bv_val) {
 819                 ber_dupbv_x( temp, init, op->o_tmpmemctx );
 820                 temp++;
 821         }
 822
 823         for (i=0; i<any_count; i++) {
 824                 ber_dupbv_x( temp, any, op->o_tmpmemctx );
 825                 temp++; any++;
 826         }
 827
 828         if (final->bv_val){
 829                 ber_dupbv_x( temp, final, op->o_tmpmemctx );
 830                 temp++;
 831         }
 832         BER_BVZERO( temp );
 833         return merged;
 834 }
 835
 836 /* Each element in stored must be found in incoming. Incoming is overwritten.
 837  */
 838 static int
 839 strings_containment(struct berval* stored, struct berval* incoming)
 840 {
 841         struct berval* element;
 842         int k=0;
 843         int j, rc = 0;
 844
 845         for ( element=stored; element->bv_val != NULL; element++ ) {
 846                 for (j = k; incoming[j].bv_val != NULL; j++) {
 847                         if (find_and_remove(&(incoming[j]), element, 2)) {
 848                                 k = j;
 849                                 rc = 1;
 850                                 break;
 851                         }
 852                         rc = 0;
 853                 }
 854                 if ( rc ) {
 855                         continue;
 856                 } else {
 857                         return 0;
 858                 }
 859         }
 860         return 1;
 861 }
 862
 863 static int
 864 substr_containment_substr(Operation *op, Filter* stored, Filter* incoming)
 865 {
 866         int rc = 0;
 867
 868         struct berval init_incoming;
 869         struct berval final_incoming;
 870         struct berval *remaining_incoming = NULL;
 871
 872         if ((!(incoming->f_sub_initial.bv_val) && (stored->f_sub_initial.bv_val))
 873            || (!(incoming->f_sub_final.bv_val) && (stored->f_sub_final.bv_val)))
 874                 return 0;
 875
 876         init_incoming = incoming->f_sub_initial;
 877         final_incoming =  incoming->f_sub_final;
 878
 879         if (find_and_remove(&init_incoming,
 880                         &(stored->f_sub_initial), 1) && find_and_remove(&final_incoming,
 881                         &(stored->f_sub_final), 3))
 882         {
 883                 if (stored->f_sub_any == NULL) {
 884                         rc = 1;
 885                         goto final;
 886                 }
 887                 remaining_incoming = merge_init_final(op, &init_incoming,
 888                                                 incoming->f_sub_any, &final_incoming);
 889                 rc = strings_containment(stored->f_sub_any, remaining_incoming);
 890                 ber_bvarray_free_x( remaining_incoming, op->o_tmpmemctx );
 891         }
 892 final:
 893         return rc;
 894 }
 895
 896 static int
 897 substr_containment_equality(Operation *op, Filter* stored, Filter* incoming)
 898 {
 899         struct berval incoming_val[2];
 900         int rc = 0;
 901
 902         incoming_val[1] = incoming->f_av_value;
 903
 904         if (find_and_remove(incoming_val+1,
 905                         &(stored->f_sub_initial), 1) && find_and_remove(incoming_val+1,
 906                         &(stored->f_sub_final), 3)) {
 907                 if (stored->f_sub_any == NULL){
 908                         rc = 1;
 909                         goto final;
 910                 }
 911                 ber_dupbv_x( incoming_val, incoming_val+1, op->o_tmpmemctx );
 912                 BER_BVZERO( incoming_val+1 );
 913                 rc = strings_containment(stored->f_sub_any, incoming_val);
 914                 op->o_tmpfree( incoming_val[0].bv_val, op->o_tmpmemctx );
 915         }
 916 final:
 917         return rc;
 918 }
 919
 920 static Filter *
 921 filter_first( Filter *f )
 922 {
 923         while ( f->f_choice == LDAP_FILTER_OR || f->f_choice == LDAP_FILTER_AND )
 924                 f = f->f_and;
 925         return f;
 926 }
 927
 928
 929 static CachedQuery *
 930 find_filter( Operation *op, Avlnode *root, Filter *inputf, Filter *first )
 931 {
 932         Filter* fs;
 933         Filter* fi;
 934         MatchingRule* mrule = NULL;
 935         int res=0, eqpass= 0;
 936         int ret, rc, dir;
 937         Avlnode *ptr;
 938         CachedQuery cq, *qc;
 939
 940         cq.filter = inputf;
 941         cq.first = first;
 942
 943         /* substring matches sort to the end, and we just have to
 944          * walk the entire list.
 945          */
 946         if ( first->f_choice == LDAP_FILTER_SUBSTRINGS ) {
 947                 ptr = tavl_end( root, 1 );
 948                 dir = TAVL_DIR_LEFT;
 949         } else {
 950                 ptr = tavl_find3( root, &cq, pcache_query_cmp, &ret );
 951                 dir = (first->f_choice == LDAP_FILTER_GE) ? TAVL_DIR_LEFT :
 952                         TAVL_DIR_RIGHT;
 953         }
 954
 955         while (ptr) {
 956                 qc = ptr->avl_data;
 957                 fi = inputf;
 958                 fs = qc->filter;
 959
 960                 /* an incoming substr query can only be satisfied by a cached
 961                  * substr query.
 962                  */
 963                 if ( first->f_choice == LDAP_FILTER_SUBSTRINGS &&
 964                         qc->first->f_choice != LDAP_FILTER_SUBSTRINGS )
 965                         break;
 966
 967                 /* an incoming eq query can be satisfied by a cached eq or substr
 968                  * query
 969                  */
 970                 if ( first->f_choice == LDAP_FILTER_EQUALITY ) {
 971                         if ( eqpass == 0 ) {
 972                                 if ( qc->first->f_choice != LDAP_FILTER_EQUALITY ) {
 973 nextpass:                       eqpass = 1;
 974                                         ptr = tavl_end( root, 1 );
 975                                         dir = TAVL_DIR_LEFT;
 976                                         continue;
 977                                 }
 978                         } else {
 979                                 if ( qc->first->f_choice != LDAP_FILTER_SUBSTRINGS )
 980                                         break;
 981                         }
 982                 }
 983                 do {
 984                         res=0;
 985                         switch (fs->f_choice) {
 986                         case LDAP_FILTER_EQUALITY:
 987                                 if (fi->f_choice == LDAP_FILTER_EQUALITY)
 988                                         mrule = fs->f_ava->aa_desc->ad_type->sat_equality;
 989                                 else
 990                                         ret = 1;
 991                                 break;
 992                         case LDAP_FILTER_GE:
 993                         case LDAP_FILTER_LE:
 994                                 mrule = fs->f_ava->aa_desc->ad_type->sat_ordering;
 995                                 break;
 996                         default:
 997                                 mrule = NULL;
 998                         }
 999                         if (mrule) {
1000                                 const char *text;
1001                                 rc = value_match(&ret, fs->f_ava->aa_desc, mrule,
1002                                         SLAP_MR_VALUE_OF_ASSERTION_SYNTAX,
1003                                         &(fi->f_ava->aa_value),
1004                                         &(fs->f_ava->aa_value), &text);
1005                                 if (rc != LDAP_SUCCESS) {
1006                                         return NULL;
1007                                 }
1008                                 if ( fi==first && fi->f_choice==LDAP_FILTER_EQUALITY && ret )
1009                                         goto nextpass;
1010                         }
1011                         switch (fs->f_choice) {
1012                         case LDAP_FILTER_OR:
1013                         case LDAP_FILTER_AND:
1014                                 fs = fs->f_and;
1015                                 fi = fi->f_and;
1016                                 res=1;
1017                                 break;
1018                         case LDAP_FILTER_SUBSTRINGS:
1019                                 /* check if the equality query can be
1020                                 * answered with cached substring query */
1021                                 if ((fi->f_choice == LDAP_FILTER_EQUALITY)
1022                                         && substr_containment_equality( op,
1023                                         fs, fi))
1024                                         res=1;
1025                                 /* check if the substring query can be
1026                                 * answered with cached substring query */
1027                                 if ((fi->f_choice ==LDAP_FILTER_SUBSTRINGS
1028                                         ) && substr_containment_substr( op,
1029                                         fs, fi))
1030                                         res= 1;
1031                                 fs=fs->f_next;
1032                                 fi=fi->f_next;
1033                                 break;
1034                         case LDAP_FILTER_PRESENT:
1035                                 res=1;
1036                                 fs=fs->f_next;
1037                                 fi=fi->f_next;
1038                                 break;
1039                         case LDAP_FILTER_EQUALITY:
1040                                 if (ret == 0)
1041                                         res = 1;
1042                                 fs=fs->f_next;
1043                                 fi=fi->f_next;
1044                                 break;
1045                         case LDAP_FILTER_GE:
1046                                 if (mrule && ret >= 0)
1047                                         res = 1;
1048                                 fs=fs->f_next;
1049                                 fi=fi->f_next;
1050                                 break;
1051                         case LDAP_FILTER_LE:
1052                                 if (mrule && ret <= 0)
1053                                         res = 1;
1054                                 fs=fs->f_next;
1055                                 fi=fi->f_next;
1056                                 break;
1057                         case LDAP_FILTER_NOT:
1058                                 res=0;
1059                                 break;
1060                         default:
1061                                 break;
1062                         }
1063                 } while((res) && (fi != NULL) && (fs != NULL));
1064
1065                 if ( res )
1066                         return qc;
1067                 ptr = tavl_next( ptr, dir );
1068         }
1069         return NULL;
1070 }
1071
1072 /* check whether query is contained in any of
1073  * the cached queries in template
1074  */
1075 static CachedQuery *
1076 query_containment(Operation *op, query_manager *qm,
1077                   Query *query,
1078                   QueryTemplate *templa)
1079 {
1080         CachedQuery* qc;
1081         int depth = 0, tscope;
1082         Qbase qbase, *qbptr = NULL;
1083         struct berval pdn;
1084
1085         if (query->filter != NULL) {
1086                 Filter *first;
1087
1088                 Debug( pcache_debug, "Lock QC index = %p\n",
1089                                 (void *) templa, 0, 0 );
1090                 qbase.base = query->base;
1091
1092                 first = filter_first( query->filter );
1093
1094                 ldap_pvt_thread_rdwr_rlock(&templa->t_rwlock);
1095                 for( ;; ) {
1096                         /* Find the base */
1097                         qbptr = avl_find( templa->qbase, &qbase, pcache_dn_cmp );
1098                         if ( qbptr ) {
1099                                 tscope = query->scope;
1100                                 /* Find a matching scope:
1101                                  * match at depth 0 OK
1102                                  * scope is BASE,
1103                                  *      one at depth 1 OK
1104                                  *  subord at depth > 0 OK
1105                                  *      subtree at any depth OK
1106                                  * scope is ONE,
1107                                  *  subtree or subord at any depth OK
1108                                  * scope is SUBORD,
1109                                  *  subtree or subord at any depth OK
1110                                  * scope is SUBTREE,
1111                                  *  subord at depth > 0 OK
1112                                  *  subtree at any depth OK
1113                                  */
1114                                 for ( tscope = 0 ; tscope <= LDAP_SCOPE_CHILDREN; tscope++ ) {
1115                                         switch ( query->scope ) {
1116                                         case LDAP_SCOPE_BASE:
1117                                                 if ( tscope == LDAP_SCOPE_BASE && depth ) continue;
1118                                                 if ( tscope == LDAP_SCOPE_ONE && depth != 1) continue;
1119                                                 if ( tscope == LDAP_SCOPE_CHILDREN && !depth ) continue;
1120                                                 break;
1121                                         case LDAP_SCOPE_ONE:
1122                                                 if ( tscope == LDAP_SCOPE_BASE )
1123                                                         tscope = LDAP_SCOPE_ONE;
1124                                                 if ( tscope == LDAP_SCOPE_ONE && depth ) continue;
1125                                                 if ( !depth ) break;
1126                                                 if ( tscope < LDAP_SCOPE_SUBTREE )
1127                                                         tscope = LDAP_SCOPE_SUBTREE;
1128                                                 break;
1129                                         case LDAP_SCOPE_SUBTREE:
1130                                                 if ( tscope < LDAP_SCOPE_SUBTREE )
1131                                                         tscope = LDAP_SCOPE_SUBTREE;
1132                                                 if ( tscope == LDAP_SCOPE_CHILDREN && !depth ) continue;
1133                                                 break;
1134                                         case LDAP_SCOPE_CHILDREN:
1135                                                 if ( tscope < LDAP_SCOPE_SUBTREE )
1136                                                         tscope = LDAP_SCOPE_SUBTREE;
1137                                                 break;
1138                                         }
1139                                         if ( !qbptr->scopes[tscope] ) continue;
1140
1141                                         /* Find filter */
1142                                         qc = find_filter( op, qbptr->scopes[tscope],
1143                                                         query->filter, first );
1144                                         if ( qc ) {
1145                                                 if ( qc->q_sizelimit ) {
1146                                                         ldap_pvt_thread_rdwr_runlock(&templa->t_rwlock);
1147                                                         return NULL;
1148                                                 }
1149                                                 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
1150                                                 if (qm->lru_top != qc) {
1151                                                         remove_query(qm, qc);
1152                                                         add_query_on_top(qm, qc);
1153                                                 }
1154                                                 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
1155                                                 return qc;
1156                                         }
1157                                 }
1158                         }
1159                         if ( be_issuffix( op->o_bd, &qbase.base ))
1160                                 break;
1161                         /* Up a level */
1162                         dnParent( &qbase.base, &pdn );
1163                         qbase.base = pdn;
1164                         depth++;
1165                 }
1166
1167                 Debug( pcache_debug,
1168                         "Not answerable: Unlock QC index=%p\n",
1169                         (void *) templa, 0, 0 );
1170                 ldap_pvt_thread_rdwr_runlock(&templa->t_rwlock);
1171         }
1172         return NULL;
1173 }
1174
1175 static void
1176 free_query (CachedQuery* qc)
1177 {
1178         free(qc->q_uuid.bv_val);
1179         filter_free(qc->filter);
1180         ldap_pvt_thread_rdwr_destroy( &qc->rwlock );
1181         memset(qc, 0, sizeof(*qc));
1182         free(qc);
1183 }
1184
1185
1186 /* Add query to query cache, the returned Query is locked for writing */
1187 static CachedQuery *
1188 add_query(
1189         Operation *op,
1190         query_manager* qm,
1191         Query* query,
1192         QueryTemplate *templ,
1193         pc_caching_reason_t why,
1194         int wlock)
1195 {
1196         CachedQuery* new_cached_query = (CachedQuery*) ch_malloc(sizeof(CachedQuery));
1197         Qbase *qbase, qb;
1198         Filter *first;
1199         int rc;
1200         time_t ttl = 0;;
1201
1202         new_cached_query->qtemp = templ;
1203         BER_BVZERO( &new_cached_query->q_uuid );
1204         new_cached_query->q_sizelimit = 0;
1205
1206         switch ( why ) {
1207         case PC_POSITIVE:
1208                 ttl = templ->ttl;
1209                 break;
1210
1211         case PC_NEGATIVE:
1212                 ttl = templ->negttl;
1213                 break;
1214
1215         case PC_SIZELIMIT:
1216                 ttl = templ->limitttl;
1217                 break;
1218
1219         default:
1220                 assert( 0 );
1221                 break;
1222         }
1223         new_cached_query->expiry_time = slap_get_time() + ttl;
1224         new_cached_query->lru_up = NULL;
1225         new_cached_query->lru_down = NULL;
1226         Debug( pcache_debug, "Added query expires at %ld (%s)\n",
1227                         (long) new_cached_query->expiry_time,
1228                         pc_caching_reason_str[ why ], 0 );
1229
1230         new_cached_query->scope = query->scope;
1231         new_cached_query->filter = query->filter;
1232         new_cached_query->first = first = filter_first( query->filter );
1233
1234         ldap_pvt_thread_rdwr_init(&new_cached_query->rwlock);
1235         if (wlock)
1236                 ldap_pvt_thread_rdwr_wlock(&new_cached_query->rwlock);
1237
1238         qb.base = query->base;
1239
1240         /* Adding a query    */
1241         Debug( pcache_debug, "Lock AQ index = %p\n",
1242                         (void *) templ, 0, 0 );
1243         ldap_pvt_thread_rdwr_wlock(&templ->t_rwlock);
1244         qbase = avl_find( templ->qbase, &qb, pcache_dn_cmp );
1245         if ( !qbase ) {
1246                 qbase = ch_calloc( 1, sizeof(Qbase) + qb.base.bv_len + 1 );
1247                 qbase->base.bv_len = qb.base.bv_len;
1248                 qbase->base.bv_val = (char *)(qbase+1);
1249                 memcpy( qbase->base.bv_val, qb.base.bv_val, qb.base.bv_len );
1250                 qbase->base.bv_val[qbase->base.bv_len] = '\0';
1251                 avl_insert( &templ->qbase, qbase, pcache_dn_cmp, avl_dup_error );
1252         }
1253         new_cached_query->next = templ->query;
1254         new_cached_query->prev = NULL;
1255         new_cached_query->qbase = qbase;
1256         rc = tavl_insert( &qbase->scopes[query->scope], new_cached_query,
1257                 pcache_query_cmp, avl_dup_error );
1258         if ( rc == 0 ) {
1259                 qbase->queries++;
1260                 if (templ->query == NULL)
1261                         templ->query_last = new_cached_query;
1262                 else
1263                         templ->query->prev = new_cached_query;
1264                 templ->query = new_cached_query;
1265                 templ->no_of_queries++;
1266         } else {
1267                 ch_free( new_cached_query );
1268                 new_cached_query = find_filter( op, qbase->scopes[query->scope],
1269                                                         query->filter, first );
1270                 filter_free( query->filter );
1271                 query->filter = NULL;
1272         }
1273         Debug( pcache_debug, "TEMPLATE %p QUERIES++ %d\n",
1274                         (void *) templ, templ->no_of_queries, 0 );
1275
1276         Debug( pcache_debug, "Unlock AQ index = %p \n",
1277                         (void *) templ, 0, 0 );
1278         ldap_pvt_thread_rdwr_wunlock(&templ->t_rwlock);
1279
1280         /* Adding on top of LRU list  */
1281         if ( rc == 0 ) {
1282                 ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
1283                 add_query_on_top(qm, new_cached_query);
1284                 ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
1285         }
1286         return rc == 0 ? new_cached_query : NULL;
1287 }
1288
1289 static void
1290 remove_from_template (CachedQuery* qc, QueryTemplate* template)
1291 {
1292         if (!qc->prev && !qc->next) {
1293                 template->query_last = template->query = NULL;
1294         } else if (qc->prev == NULL) {
1295                 qc->next->prev = NULL;
1296                 template->query = qc->next;
1297         } else if (qc->next == NULL) {
1298                 qc->prev->next = NULL;
1299                 template->query_last = qc->prev;
1300         } else {
1301                 qc->next->prev = qc->prev;
1302                 qc->prev->next = qc->next;
1303         }
1304         tavl_delete( &qc->qbase->scopes[qc->scope], qc, pcache_query_cmp );
1305         qc->qbase->queries--;
1306         if ( qc->qbase->queries == 0 ) {
1307                 avl_delete( &template->qbase, qc->qbase, pcache_dn_cmp );
1308                 ch_free( qc->qbase );
1309                 qc->qbase = NULL;
1310         }
1311
1312         template->no_of_queries--;
1313 }
1314
1315 /* remove bottom query of LRU list from the query cache */
1316 /*
1317  * NOTE: slight change in functionality.
1318  *
1319  * - if result->bv_val is NULL, the query at the bottom of the LRU
1320  *   is removed
1321  * - otherwise, the query whose UUID is *result is removed
1322  *      - if not found, result->bv_val is zeroed
1323  */
1324 static void
1325 cache_replacement(query_manager* qm, struct berval *result)
1326 {
1327         CachedQuery* bottom;
1328         QueryTemplate *temp;
1329
1330         ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
1331         if ( BER_BVISNULL( result ) ) {
1332                 bottom = qm->lru_bottom;
1333
1334                 if (!bottom) {
1335                         Debug ( pcache_debug,
1336                                 "Cache replacement invoked without "
1337                                 "any query in LRU list\n", 0, 0, 0 );
1338                         ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
1339                         return;
1340                 }
1341
1342         } else {
1343                 for ( bottom = qm->lru_bottom;
1344                         bottom != NULL;
1345                         bottom = bottom->lru_up )
1346                 {
1347                         if ( bvmatch( result, &bottom->q_uuid ) ) {
1348                                 break;
1349                         }
1350                 }
1351
1352                 if ( !bottom ) {
1353                         Debug ( pcache_debug,
1354                                 "Could not find query with uuid=\"%s\""
1355                                 "in LRU list\n", result->bv_val, 0, 0 );
1356                         ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
1357                         BER_BVZERO( result );
1358                         return;
1359                 }
1360         }
1361
1362         temp = bottom->qtemp;
1363         remove_query(qm, bottom);
1364         ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
1365
1366         *result = bottom->q_uuid;
1367         BER_BVZERO( &bottom->q_uuid );
1368
1369         Debug( pcache_debug, "Lock CR index = %p\n", (void *) temp, 0, 0 );
1370         ldap_pvt_thread_rdwr_wlock(&temp->t_rwlock);
1371         remove_from_template(bottom, temp);
1372         Debug( pcache_debug, "TEMPLATE %p QUERIES-- %d\n",
1373                 (void *) temp, temp->no_of_queries, 0 );
1374         Debug( pcache_debug, "Unlock CR index = %p\n", (void *) temp, 0, 0 );
1375         ldap_pvt_thread_rdwr_wunlock(&temp->t_rwlock);
1376         free_query(bottom);
1377 }
1378
1379 struct query_info {
1380         struct query_info *next;
1381         struct berval xdn;
1382         int del;
1383 };
1384
1385 static int
1386 remove_func (
1387         Operation       *op,
1388         SlapReply       *rs
1389 )
1390 {
1391         Attribute *attr;
1392         struct query_info *qi;
1393         int count = 0;
1394
1395         if ( rs->sr_type != REP_SEARCH ) return 0;
1396
1397         attr = attr_find( rs->sr_entry->e_attrs,  ad_queryId );
1398         if ( attr == NULL ) return 0;
1399
1400         count = attr->a_numvals;
1401         assert( count > 0 );
1402         qi = op->o_tmpalloc( sizeof( struct query_info ), op->o_tmpmemctx );
1403         qi->next = op->o_callback->sc_private;
1404         op->o_callback->sc_private = qi;
1405         ber_dupbv_x( &qi->xdn, &rs->sr_entry->e_nname, op->o_tmpmemctx );
1406         qi->del = ( count == 1 );
1407
1408         return 0;
1409 }
1410
1411 static int
1412 remove_query_data(
1413         Operation       *op,
1414         SlapReply       *rs,
1415         struct berval   *query_uuid )
1416 {
1417         struct query_info       *qi, *qnext;
1418         char                    filter_str[ LDAP_LUTIL_UUIDSTR_BUFSIZE + STRLENOF( "(queryId=)" ) ];
1419         AttributeAssertion      ava = ATTRIBUTEASSERTION_INIT;
1420         Filter                  filter = {LDAP_FILTER_EQUALITY};
1421         SlapReply               sreply = {REP_RESULT};
1422         slap_callback cb = { NULL, remove_func, NULL, NULL };
1423         int deleted = 0;
1424
1425         sreply.sr_entry = NULL;
1426         sreply.sr_nentries = 0;
1427         op->ors_filterstr.bv_len = snprintf(filter_str, sizeof(filter_str),
1428                 "(%s=%s)", ad_queryId->ad_cname.bv_val, query_uuid->bv_val);
1429         filter.f_ava = &ava;
1430         filter.f_av_desc = ad_queryId;
1431         filter.f_av_value = *query_uuid;
1432
1433         op->o_tag = LDAP_REQ_SEARCH;
1434         op->o_protocol = LDAP_VERSION3;
1435         op->o_callback = &cb;
1436         op->o_time = slap_get_time();
1437         op->o_do_not_cache = 1;
1438
1439         op->o_req_dn = op->o_bd->be_suffix[0];
1440         op->o_req_ndn = op->o_bd->be_nsuffix[0];
1441         op->ors_scope = LDAP_SCOPE_SUBTREE;
1442         op->ors_deref = LDAP_DEREF_NEVER;
1443         op->ors_slimit = SLAP_NO_LIMIT;
1444         op->ors_tlimit = SLAP_NO_LIMIT;
1445         op->ors_filter = &filter;
1446         op->ors_filterstr.bv_val = filter_str;
1447         op->ors_filterstr.bv_len = strlen(filter_str);
1448         op->ors_attrs = NULL;
1449         op->ors_attrsonly = 0;
1450
1451         op->o_bd->be_search( op, &sreply );
1452
1453         for ( qi=cb.sc_private; qi; qi=qnext ) {
1454                 qnext = qi->next;
1455
1456                 op->o_req_dn = qi->xdn;
1457                 op->o_req_ndn = qi->xdn;
1458
1459                 if ( qi->del ) {
1460                         Debug( pcache_debug, "DELETING ENTRY TEMPLATE=%s\n",
1461                                 query_uuid->bv_val, 0, 0 );
1462
1463                         op->o_tag = LDAP_REQ_DELETE;
1464
1465                         if (op->o_bd->be_delete(op, &sreply) == LDAP_SUCCESS) {
1466                                 deleted++;
1467                         }
1468
1469                 } else {
1470                         Modifications mod;
1471                         struct berval vals[2];
1472
1473                         vals[0] = *query_uuid;
1474                         vals[1].bv_val = NULL;
1475                         vals[1].bv_len = 0;
1476                         mod.sml_op = LDAP_MOD_DELETE;
1477                         mod.sml_flags = 0;
1478                         mod.sml_desc = ad_queryId;
1479                         mod.sml_type = ad_queryId->ad_cname;
1480                         mod.sml_values = vals;
1481                         mod.sml_nvalues = NULL;
1482                         mod.sml_numvals = 1;
1483                         mod.sml_next = NULL;
1484                         Debug( pcache_debug,
1485                                 "REMOVING TEMP ATTR : TEMPLATE=%s\n",
1486                                 query_uuid->bv_val, 0, 0 );
1487
1488                         op->orm_modlist = &mod;
1489
1490                         op->o_bd->be_modify( op, &sreply );
1491                 }
1492                 op->o_tmpfree( qi->xdn.bv_val, op->o_tmpmemctx );
1493                 op->o_tmpfree( qi, op->o_tmpmemctx );
1494         }
1495         return deleted;
1496 }
1497
1498 static int
1499 get_attr_set(
1500         AttributeName* attrs,
1501         query_manager* qm,
1502         int num
1503 );
1504
1505 static int
1506 filter2template(
1507         Operation               *op,
1508         Filter                  *f,
1509         struct                  berval *fstr,
1510         AttributeName**         filter_attrs,
1511         int*                    filter_cnt,
1512         int*                    filter_got_oc )
1513 {
1514         AttributeDescription *ad;
1515         int len, ret;
1516
1517         switch ( f->f_choice ) {
1518         case LDAP_FILTER_EQUALITY:
1519                 ad = f->f_av_desc;
1520                 len = STRLENOF( "(=)" ) + ad->ad_cname.bv_len;
1521                 ret = snprintf( fstr->bv_val+fstr->bv_len, len + 1, "(%s=)", ad->ad_cname.bv_val );
1522                 assert( ret == len );
1523                 fstr->bv_len += len;
1524                 break;
1525
1526         case LDAP_FILTER_GE:
1527                 ad = f->f_av_desc;
1528                 len = STRLENOF( "(>=)" ) + ad->ad_cname.bv_len;
1529                 ret = snprintf( fstr->bv_val+fstr->bv_len, len + 1, "(%s>=)", ad->ad_cname.bv_val);
1530                 assert( ret == len );
1531                 fstr->bv_len += len;
1532                 break;
1533
1534         case LDAP_FILTER_LE:
1535                 ad = f->f_av_desc;
1536                 len = STRLENOF( "(<=)" ) + ad->ad_cname.bv_len;
1537                 ret = snprintf( fstr->bv_val+fstr->bv_len, len + 1, "(%s<=)", ad->ad_cname.bv_val);
1538                 assert( ret == len );
1539                 fstr->bv_len += len;
1540                 break;
1541
1542         case LDAP_FILTER_APPROX:
1543                 ad = f->f_av_desc;
1544                 len = STRLENOF( "(~=)" ) + ad->ad_cname.bv_len;
1545                 ret = snprintf( fstr->bv_val+fstr->bv_len, len + 1, "(%s~=)", ad->ad_cname.bv_val);
1546                 assert( ret == len );
1547                 fstr->bv_len += len;
1548                 break;
1549
1550         case LDAP_FILTER_SUBSTRINGS:
1551                 ad = f->f_sub_desc;
1552                 len = STRLENOF( "(=)" ) + ad->ad_cname.bv_len;
1553                 ret = snprintf( fstr->bv_val+fstr->bv_len, len + 1, "(%s=)", ad->ad_cname.bv_val );
1554                 assert( ret == len );
1555                 fstr->bv_len += len;
1556                 break;
1557
1558         case LDAP_FILTER_PRESENT:
1559                 ad = f->f_desc;
1560                 len = STRLENOF( "(=*)" ) + ad->ad_cname.bv_len;
1561                 ret = snprintf( fstr->bv_val+fstr->bv_len, len + 1, "(%s=*)", ad->ad_cname.bv_val );
1562                 assert( ret == len );
1563                 fstr->bv_len += len;
1564                 break;
1565
1566         case LDAP_FILTER_AND:
1567         case LDAP_FILTER_OR:
1568         case LDAP_FILTER_NOT: {
1569                 int rc = 0;
1570                 fstr->bv_val[fstr->bv_len++] = '(';
1571                 switch ( f->f_choice ) {
1572                 case LDAP_FILTER_AND:
1573                         fstr->bv_val[fstr->bv_len] = '&';
1574                         break;
1575                 case LDAP_FILTER_OR:
1576                         fstr->bv_val[fstr->bv_len] = '|';
1577                         break;
1578                 case LDAP_FILTER_NOT:
1579                         fstr->bv_val[fstr->bv_len] = '!';
1580                         break;
1581                 }
1582                 fstr->bv_len++;
1583
1584                 for ( f = f->f_list; f != NULL; f = f->f_next ) {
1585                         rc = filter2template( op, f, fstr, filter_attrs, filter_cnt,
1586                                 filter_got_oc );
1587                         if ( rc ) break;
1588                 }
1589                 fstr->bv_val[fstr->bv_len++] = ')';
1590                 fstr->bv_val[fstr->bv_len] = '\0';
1591
1592                 return rc;
1593                 }
1594
1595         default:
1596                 /* a filter should at least have room for "()",
1597                  * an "=" and for a 1-char attr */
1598                 strcpy( fstr->bv_val, "(?=)" );
1599                 fstr->bv_len += STRLENOF("(?=)");
1600                 return -1;
1601         }
1602
1603         if ( filter_attrs != NULL ) {
1604                 *filter_attrs = (AttributeName *)op->o_tmprealloc(*filter_attrs,
1605                                 (*filter_cnt + 2)*sizeof(AttributeName), op->o_tmpmemctx);
1606
1607                 (*filter_attrs)[*filter_cnt].an_desc = ad;
1608                 (*filter_attrs)[*filter_cnt].an_name = ad->ad_cname;
1609                 (*filter_attrs)[*filter_cnt].an_oc = NULL;
1610                 (*filter_attrs)[*filter_cnt].an_flags = 0;
1611                 BER_BVZERO( &(*filter_attrs)[*filter_cnt+1].an_name );
1612                 (*filter_cnt)++;
1613                 if ( ad == slap_schema.si_ad_objectClass )
1614                         *filter_got_oc = 1;
1615         }
1616
1617         return 0;
1618 }
1619
1620 struct search_info {
1621         slap_overinst *on;
1622         Query query;
1623         QueryTemplate *qtemp;
1624         AttributeName*  save_attrs;     /* original attributes, saved for response */
1625         int swap_saved_attrs;
1626         int max;
1627         int over;
1628         int count;
1629         int slimit;
1630         int slimit_exceeded;
1631         pc_caching_reason_t caching_reason;
1632         Entry *head, *tail;
1633 };
1634
1635 static void
1636 remove_query_and_data(
1637         Operation       *op,
1638         SlapReply       *rs,
1639         cache_manager   *cm,
1640         struct berval   *uuid )
1641 {
1642         query_manager*          qm = cm->qm;
1643
1644         qm->crfunc( qm, uuid );
1645         if ( !BER_BVISNULL( uuid ) ) {
1646                 int     return_val;
1647
1648                 Debug( pcache_debug,
1649                         "Removing query UUID %s\n",
1650                         uuid->bv_val, 0, 0 );
1651                 return_val = remove_query_data( op, rs, uuid );
1652                 Debug( pcache_debug,
1653                         "QUERY REMOVED, SIZE=%d\n",
1654                         return_val, 0, 0);
1655                 ldap_pvt_thread_mutex_lock( &cm->cache_mutex );
1656                 cm->cur_entries -= return_val;
1657                 cm->num_cached_queries--;
1658                 Debug( pcache_debug,
1659                         "STORED QUERIES = %lu\n",
1660                         cm->num_cached_queries, 0, 0 );
1661                 ldap_pvt_thread_mutex_unlock( &cm->cache_mutex );
1662                 Debug( pcache_debug,
1663                         "QUERY REMOVED, CACHE ="
1664                         "%d entries\n",
1665                         cm->cur_entries, 0, 0 );
1666         }
1667 }
1668
1669 /*
1670  * Callback used to fetch queryId values based on entryUUID;
1671  * used by pcache_remove_entries_from_cache()
1672  */
1673 static int
1674 fetch_queryId_cb( Operation *op, SlapReply *rs )
1675 {
1676         int             rc = 0;
1677
1678         /* only care about searchEntry responses */
1679         if ( rs->sr_type != REP_SEARCH ) {
1680                 return 0;
1681         }
1682
1683         /* allow only one response per entryUUID */
1684         if ( op->o_callback->sc_private != NULL ) {
1685                 rc = 1;
1686
1687         } else {
1688                 Attribute       *a;
1689
1690                 /* copy all queryId values into callback's private data */
1691                 a = attr_find( rs->sr_entry->e_attrs, ad_queryId );
1692                 if ( a != NULL ) {
1693                         BerVarray       vals = NULL;
1694
1695                         ber_bvarray_dup_x( &vals, a->a_nvals, op->o_tmpmemctx );
1696                         op->o_callback->sc_private = (void *)vals;
1697                 }
1698         }
1699
1700         /* clear entry if required */
1701         if ( rs->sr_flags & REP_ENTRY_MUSTBEFREED ) {
1702                 entry_free( rs->sr_entry );
1703                 rs->sr_entry = NULL;
1704                 rs->sr_flags ^= REP_ENTRY_MUSTBEFREED;
1705         }
1706
1707         return rc;
1708 }
1709
1710 /*
1711  * Call that allows to remove a set of entries from the cache,
1712  * by forcing the removal of all the related queries.
1713  */
1714 int
1715 pcache_remove_entries_from_cache(
1716         Operation       *op,
1717         cache_manager   *cm,
1718         BerVarray       entryUUIDs )
1719 {
1720         Connection      conn = { 0 };
1721         OperationBuffer opbuf;
1722         Operation       op2;
1723         slap_callback   sc = { 0 };
1724         SlapReply       rs = { REP_RESULT };
1725         Filter          f = { 0 };
1726         char            filtbuf[ LDAP_LUTIL_UUIDSTR_BUFSIZE + STRLENOF( "(entryUUID=)" ) ];
1727         AttributeAssertion ava = ATTRIBUTEASSERTION_INIT;
1728         AttributeName   attrs[ 2 ] = {{{ 0 }}};
1729         int             s, rc;
1730
1731         if ( op == NULL ) {
1732                 void    *thrctx = ldap_pvt_thread_pool_context();
1733
1734                 connection_fake_init( &conn, &opbuf, thrctx );
1735                 op = &opbuf.ob_op;
1736
1737         } else {
1738                 op2 = *op;
1739                 op = &op2;
1740         }
1741
1742         memset( &op->oq_search, 0, sizeof( op->oq_search ) );
1743         op->ors_scope = LDAP_SCOPE_SUBTREE;
1744         op->ors_deref = LDAP_DEREF_NEVER;
1745         f.f_choice = LDAP_FILTER_EQUALITY;
1746         f.f_ava = &ava;
1747         ava.aa_desc = slap_schema.si_ad_entryUUID;
1748         op->ors_filter = &f;
1749         op->ors_slimit = 1;
1750         op->ors_tlimit = SLAP_NO_LIMIT;
1751         attrs[ 0 ].an_desc = ad_queryId;
1752         attrs[ 0 ].an_name = ad_queryId->ad_cname;
1753         op->ors_attrs = attrs;
1754         op->ors_attrsonly = 0;
1755
1756         op->o_req_dn = cm->db.be_suffix[ 0 ];
1757         op->o_req_ndn = cm->db.be_nsuffix[ 0 ];
1758
1759         op->o_tag = LDAP_REQ_SEARCH;
1760         op->o_protocol = LDAP_VERSION3;
1761         op->o_managedsait = SLAP_CONTROL_CRITICAL;
1762         op->o_bd = &cm->db;
1763         op->o_dn = op->o_bd->be_rootdn;
1764         op->o_ndn = op->o_bd->be_rootndn;
1765         sc.sc_response = fetch_queryId_cb;
1766         op->o_callback = &sc;
1767
1768         for ( s = 0; !BER_BVISNULL( &entryUUIDs[ s ] ); s++ ) {
1769                 BerVarray       vals = NULL;
1770
1771                 op->ors_filterstr.bv_len = snprintf( filtbuf, sizeof( filtbuf ),
1772                         "(entryUUID=%s)", entryUUIDs[ s ].bv_val );
1773                 op->ors_filterstr.bv_val = filtbuf;
1774                 ava.aa_value = entryUUIDs[ s ];
1775
1776                 rc = op->o_bd->be_search( op, &rs );
1777                 if ( rc != LDAP_SUCCESS ) {
1778                         continue;
1779                 }
1780
1781                 vals = (BerVarray)op->o_callback->sc_private;
1782                 if ( vals != NULL ) {
1783                         int             i;
1784
1785                         for ( i = 0; !BER_BVISNULL( &vals[ i ] ); i++ ) {
1786                                 struct berval   val = vals[ i ];
1787
1788                                 remove_query_and_data( op, &rs, cm, &val );
1789
1790                                 if ( !BER_BVISNULL( &val ) && val.bv_val != vals[ i ].bv_val ) {
1791                                         ch_free( val.bv_val );
1792                                 }
1793                         }
1794
1795                         ber_bvarray_free_x( vals, op->o_tmpmemctx );
1796                         op->o_callback->sc_private = NULL;
1797                 }
1798         }
1799
1800         return 0;
1801 }
1802
1803 /*
1804  * Call that allows to remove a query from the cache.
1805  */
1806 int
1807 pcache_remove_query_from_cache(
1808         Operation       *op,
1809         cache_manager   *cm,
1810         struct berval   *queryid )
1811 {
1812         Operation       op2 = *op;
1813         SlapReply       rs2 = { 0 };
1814
1815         op2.o_bd = &cm->db;
1816
1817         /* remove the selected query */
1818         remove_query_and_data( &op2, &rs2, cm, queryid );
1819
1820         return LDAP_SUCCESS;
1821 }
1822
1823 /*
1824  * Call that allows to remove a set of queries related to an entry
1825  * from the cache; if queryid is not null, the entry must belong to
1826  * the query indicated by queryid.
1827  */
1828 int
1829 pcache_remove_entry_queries_from_cache(
1830         Operation       *op,
1831         cache_manager   *cm,
1832         struct berval   *ndn,
1833         struct berval   *queryid )
1834 {
1835         Connection              conn = { 0 };
1836         OperationBuffer         opbuf;
1837         Operation               op2;
1838         slap_callback           sc = { 0 };
1839         SlapReply               rs = { REP_RESULT };
1840         Filter                  f = { 0 };
1841         char                    filter_str[ LDAP_LUTIL_UUIDSTR_BUFSIZE + STRLENOF( "(queryId=)" ) ];
1842         AttributeAssertion      ava = ATTRIBUTEASSERTION_INIT;
1843         AttributeName           attrs[ 2 ] = {{{ 0 }}};
1844         int                     rc;
1845
1846         BerVarray               vals = NULL;
1847
1848         if ( op == NULL ) {
1849                 void    *thrctx = ldap_pvt_thread_pool_context();
1850
1851                 connection_fake_init( &conn, &opbuf, thrctx );
1852                 op = &opbuf.ob_op;
1853
1854         } else {
1855                 op2 = *op;
1856                 op = &op2;
1857         }
1858
1859         memset( &op->oq_search, 0, sizeof( op->oq_search ) );
1860         op->ors_scope = LDAP_SCOPE_BASE;
1861         op->ors_deref = LDAP_DEREF_NEVER;
1862         if ( queryid == NULL || BER_BVISNULL( queryid ) ) {
1863                 BER_BVSTR( &op->ors_filterstr, "(objectClass=*)" );
1864                 f.f_choice = LDAP_FILTER_PRESENT;
1865                 f.f_desc = slap_schema.si_ad_objectClass;
1866
1867         } else {
1868                 op->ors_filterstr.bv_len = snprintf( filter_str,
1869                         sizeof( filter_str ), "(%s=%s)",
1870                         ad_queryId->ad_cname.bv_val, queryid->bv_val );
1871                 f.f_choice = LDAP_FILTER_EQUALITY;
1872                 f.f_ava = &ava;
1873                 f.f_av_desc = ad_queryId;
1874                 f.f_av_value = *queryid;
1875         }
1876         op->ors_filter = &f;
1877         op->ors_slimit = 1;
1878         op->ors_tlimit = SLAP_NO_LIMIT;
1879         attrs[ 0 ].an_desc = ad_queryId;
1880         attrs[ 0 ].an_name = ad_queryId->ad_cname;
1881         op->ors_attrs = attrs;
1882         op->ors_attrsonly = 0;
1883
1884         op->o_req_dn = *ndn;
1885         op->o_req_ndn = *ndn;
1886
1887         op->o_tag = LDAP_REQ_SEARCH;
1888         op->o_protocol = LDAP_VERSION3;
1889         op->o_managedsait = SLAP_CONTROL_CRITICAL;
1890         op->o_bd = &cm->db;
1891         op->o_dn = op->o_bd->be_rootdn;
1892         op->o_ndn = op->o_bd->be_rootndn;
1893         sc.sc_response = fetch_queryId_cb;
1894         op->o_callback = &sc;
1895
1896         rc = op->o_bd->be_search( op, &rs );
1897         if ( rc != LDAP_SUCCESS ) {
1898                 return rc;
1899         }
1900
1901         vals = (BerVarray)op->o_callback->sc_private;
1902         if ( vals != NULL ) {
1903                 int             i;
1904
1905                 for ( i = 0; !BER_BVISNULL( &vals[ i ] ); i++ ) {
1906                         struct berval   val = vals[ i ];
1907
1908                         remove_query_and_data( op, &rs, cm, &val );
1909
1910                         if ( !BER_BVISNULL( &val ) && val.bv_val != vals[ i ].bv_val ) {
1911                                 ch_free( val.bv_val );
1912                         }
1913                 }
1914
1915                 ber_bvarray_free_x( vals, op->o_tmpmemctx );
1916         }
1917
1918         return LDAP_SUCCESS;
1919 }
1920
1921 static int
1922 cache_entries(
1923         Operation       *op,
1924         SlapReply       *rs,
1925         struct berval *query_uuid )
1926 {
1927         struct search_info *si = op->o_callback->sc_private;
1928         slap_overinst *on = si->on;
1929         cache_manager *cm = on->on_bi.bi_private;
1930         int             return_val = 0;
1931         Entry           *e;
1932         struct berval   crp_uuid;
1933         char            uuidbuf[ LDAP_LUTIL_UUIDSTR_BUFSIZE ];
1934         Operation       *op_tmp;
1935         Connection      conn = {0};
1936         OperationBuffer opbuf;
1937         void            *thrctx = ldap_pvt_thread_pool_context();
1938
1939         query_uuid->bv_len = lutil_uuidstr(uuidbuf, sizeof(uuidbuf));
1940         ber_str2bv(uuidbuf, query_uuid->bv_len, 1, query_uuid);
1941
1942         connection_fake_init2( &conn, &opbuf, thrctx, 0 );
1943         op_tmp = &opbuf.ob_op;
1944         op_tmp->o_bd = &cm->db;
1945         op_tmp->o_dn = cm->db.be_rootdn;
1946         op_tmp->o_ndn = cm->db.be_rootndn;
1947
1948         Debug( pcache_debug, "UUID for query being added = %s\n",
1949                         uuidbuf, 0, 0 );
1950
1951         for ( e=si->head; e; e=si->head ) {
1952                 si->head = e->e_private;
1953                 e->e_private = NULL;
1954                 while ( cm->cur_entries > (cm->max_entries) ) {
1955                         BER_BVZERO( &crp_uuid );
1956                         remove_query_and_data( op_tmp, rs, cm, &crp_uuid );
1957                 }
1958
1959                 return_val = merge_entry(op_tmp, e, query_uuid);
1960                 ldap_pvt_thread_mutex_lock(&cm->cache_mutex);
1961                 cm->cur_entries += return_val;
1962                 Debug( pcache_debug,
1963                         "ENTRY ADDED/MERGED, CACHED ENTRIES=%d\n",
1964                         cm->cur_entries, 0, 0 );
1965                 return_val = 0;
1966                 ldap_pvt_thread_mutex_unlock(&cm->cache_mutex);
1967         }
1968
1969         return return_val;
1970 }
1971
1972 static int
1973 pcache_op_cleanup( Operation *op, SlapReply *rs ) {
1974         slap_callback   *cb = op->o_callback;
1975         struct search_info *si = cb->sc_private;
1976         slap_overinst *on = si->on;
1977         cache_manager *cm = on->on_bi.bi_private;
1978         query_manager*          qm = cm->qm;
1979
1980         if ( rs->sr_type == REP_SEARCH ) {
1981                 Entry *e;
1982
1983                 /* don't return more entries than requested by the client */
1984                 if ( si->slimit > 0 && rs->sr_nentries >= si->slimit ) {
1985                         si->slimit_exceeded = 1;
1986                 }
1987
1988                 /* If we haven't exceeded the limit for this query,
1989                  * build a chain of answers to store. If we hit the
1990                  * limit, empty the chain and ignore the rest.
1991                  */
1992                 if ( !si->over ) {
1993                         /* check if the entry contains undefined
1994                          * attributes/objectClasses (ITS#5680) */
1995                         if ( cm->check_cacheability && test_filter( op, rs->sr_entry, si->query.filter ) != LDAP_COMPARE_TRUE ) {
1996                                 Debug( pcache_debug, "%s: query not cacheable because of schema issues in DN \"%s\"\n",
1997                                         op->o_log_prefix, rs->sr_entry->e_name.bv_val, 0 );
1998                                 goto over;
1999                         }
2000
2001                         /* check for malformed entries: attrs with no values */
2002                         {
2003                                 Attribute *a = rs->sr_entry->e_attrs;
2004                                 for (; a; a=a->a_next) {
2005                                         if ( !a->a_numvals ) {
2006                                                 Debug( pcache_debug, "%s: query not cacheable because of attrs without values in DN \"%s\" (%s)\n",
2007                                                 op->o_log_prefix, rs->sr_entry->e_name.bv_val,
2008                                                 a->a_desc->ad_cname.bv_val );
2009                                                 goto over;
2010                                         }
2011                                 }
2012                         }
2013
2014                         if ( si->count < si->max ) {
2015                                 si->count++;
2016                                 e = entry_dup( rs->sr_entry );
2017                                 if ( !si->head ) si->head = e;
2018                                 if ( si->tail ) si->tail->e_private = e;
2019                                 si->tail = e;
2020
2021                         } else {
2022 over:;
2023                                 si->over = 1;
2024                                 si->count = 0;
2025                                 for (;si->head; si->head=e) {
2026                                         e = si->head->e_private;
2027                                         si->head->e_private = NULL;
2028                                         entry_free(si->head);
2029                                 }
2030                                 si->tail = NULL;
2031                         }
2032                 }
2033
2034         }
2035
2036         if ( rs->sr_type == REP_RESULT ||
2037                 op->o_abandon || rs->sr_err == SLAPD_ABANDON )
2038         {
2039                 if ( si->swap_saved_attrs ) {
2040                         rs->sr_attrs = si->save_attrs;
2041                         op->ors_attrs = si->save_attrs;
2042                 }
2043                 if ( (op->o_abandon || rs->sr_err == SLAPD_ABANDON) &&
2044                                 si->caching_reason == PC_IGNORE ) {
2045                         filter_free( si->query.filter );
2046                         if ( si->count ) {
2047                                 /* duplicate query, free it */
2048                                 Entry *e;
2049                                 for (;si->head; si->head=e) {
2050                                         e = si->head->e_private;
2051                                         si->head->e_private = NULL;
2052                                         entry_free(si->head);
2053                                 }
2054                         }
2055                         op->o_callback = op->o_callback->sc_next;
2056                         op->o_tmpfree( cb, op->o_tmpmemctx );
2057                 } else if ( si->caching_reason != PC_IGNORE ) {
2058                         CachedQuery *qc = qm->addfunc(op, qm, &si->query,
2059                                 si->qtemp, si->caching_reason, 1 );
2060
2061                         if ( qc != NULL ) {
2062                                 switch ( si->caching_reason ) {
2063                                 case PC_POSITIVE:
2064                                         cache_entries( op, rs, &qc->q_uuid );
2065                                         break;
2066
2067                                 case PC_SIZELIMIT:
2068                                         qc->q_sizelimit = rs->sr_nentries;
2069                                         break;
2070
2071                                 case PC_NEGATIVE:
2072                                         break;
2073
2074                                 default:
2075                                         assert( 0 );
2076                                         break;
2077                                 }
2078                                 ldap_pvt_thread_rdwr_wunlock(&qc->rwlock);
2079                                 ldap_pvt_thread_mutex_lock(&cm->cache_mutex);
2080                                 cm->num_cached_queries++;
2081                                 Debug( pcache_debug, "STORED QUERIES = %lu\n",
2082                                                 cm->num_cached_queries, 0, 0 );
2083                                 ldap_pvt_thread_mutex_unlock(&cm->cache_mutex);
2084
2085                                 /* If the consistency checker suspended itself,
2086                                  * wake it back up
2087                                  */
2088                                 if ( cm->cc_paused == PCACHE_CC_PAUSED ) {
2089                                         ldap_pvt_thread_mutex_lock( &slapd_rq.rq_mutex );
2090                                         if ( cm->cc_paused == PCACHE_CC_PAUSED ) {
2091                                                 cm->cc_paused = 0;
2092                                                 ldap_pvt_runqueue_resched( &slapd_rq, cm->cc_arg, 0 );
2093                                         }
2094                                         ldap_pvt_thread_mutex_unlock( &slapd_rq.rq_mutex );
2095                                 }
2096
2097                         } else if ( si->count ) {
2098                                 /* duplicate query, free it */
2099                                 Entry *e;
2100                                 for (;si->head; si->head=e) {
2101                                         e = si->head->e_private;
2102                                         si->head->e_private = NULL;
2103                                         entry_free(si->head);
2104                                 }
2105                         }
2106
2107                 } else {
2108                         filter_free( si->query.filter );
2109                 }
2110         }
2111
2112         return SLAP_CB_CONTINUE;
2113 }
2114
2115 static int
2116 pcache_response(
2117         Operation       *op,
2118         SlapReply       *rs )
2119 {
2120         struct search_info *si = op->o_callback->sc_private;
2121
2122         if ( si->swap_saved_attrs ) {
2123                 rs->sr_attrs = si->save_attrs;
2124                 op->ors_attrs = si->save_attrs;
2125         }
2126
2127         if ( rs->sr_type == REP_SEARCH ) {
2128                 /* don't return more entries than requested by the client */
2129                 if ( si->slimit_exceeded ) {
2130                         return 0;
2131                 }
2132
2133         } else if ( rs->sr_type == REP_RESULT ) {
2134
2135                 if ( si->count ) {
2136                         if ( rs->sr_err == LDAP_SUCCESS ) {
2137                                 si->caching_reason = PC_POSITIVE;
2138
2139                         } else if ( rs->sr_err == LDAP_SIZELIMIT_EXCEEDED
2140                                 && si->qtemp->limitttl )
2141                         {
2142                                 si->caching_reason = PC_SIZELIMIT;
2143                         }
2144
2145                 } else if ( si->qtemp->negttl && !si->count && !si->over &&
2146                                 rs->sr_err == LDAP_SUCCESS )
2147                 {
2148                         si->caching_reason = PC_NEGATIVE;
2149                 }
2150
2151
2152                 if ( si->slimit_exceeded ) {
2153                         rs->sr_err = LDAP_SIZELIMIT_EXCEEDED;
2154                 }
2155         }
2156
2157         return SLAP_CB_CONTINUE;
2158 }
2159
2160 static int
2161 add_filter_attrs(
2162         Operation *op,
2163         AttributeName** new_attrs,
2164         struct attr_set *attrs,
2165         AttributeName* filter_attrs,
2166         int fattr_cnt,
2167         int fattr_got_oc)
2168 {
2169         int alluser = 0;
2170         int allop = 0;
2171         int i, j;
2172         int count;
2173         int addoc = 0;
2174
2175         /* duplicate attrs */
2176         count = attrs->count + fattr_cnt;
2177         if ( !fattr_got_oc && !(attrs->flags & PC_GOT_OC)) {
2178                 addoc = 1;
2179                 count++;
2180         }
2181
2182         *new_attrs = (AttributeName*)ch_calloc( count + 1,
2183                 sizeof(AttributeName) );
2184         for (i=0; i<attrs->count; i++) {
2185                 (*new_attrs)[i].an_name = attrs->attrs[i].an_name;
2186                 (*new_attrs)[i].an_desc = attrs->attrs[i].an_desc;
2187         }
2188         BER_BVZERO( &(*new_attrs)[i].an_name );
2189         alluser = an_find( *new_attrs, slap_bv_all_user_attrs );
2190         allop = an_find( *new_attrs, slap_bv_all_operational_attrs );
2191
2192         j = i;
2193         for ( i=0; i<fattr_cnt; i++ ) {
2194                 if ( an_find(*new_attrs, &filter_attrs[i].an_name ) ) {
2195                         continue;
2196                 }
2197                 if ( is_at_operational(filter_attrs[i].an_desc->ad_type) ) {
2198                         if ( allop ) {
2199                                 continue;
2200                         }
2201                 } else if ( alluser ) {
2202                         continue;
2203                 }
2204                 (*new_attrs)[j].an_name = filter_attrs[i].an_name;
2205                 (*new_attrs)[j].an_desc = filter_attrs[i].an_desc;
2206                 (*new_attrs)[j].an_oc = NULL;
2207                 (*new_attrs)[j].an_flags = 0;
2208                 j++;
2209         }
2210         if ( addoc ) {
2211                 (*new_attrs)[j].an_name = slap_schema.si_ad_objectClass->ad_cname;
2212                 (*new_attrs)[j].an_desc = slap_schema.si_ad_objectClass;
2213                 (*new_attrs)[j].an_oc = NULL;
2214                 (*new_attrs)[j].an_flags = 0;
2215                 j++;
2216         }
2217         BER_BVZERO( &(*new_attrs)[j].an_name );
2218
2219         return j;
2220 }
2221
2222 /* NOTE: this is a quick workaround to let pcache minimally interact
2223  * with pagedResults.  A more articulated solutions would be to
2224  * perform the remote query without control and cache all results,
2225  * performing the pagedResults search only within the client
2226  * and the proxy.  This requires pcache to understand pagedResults. */
2227 static int
2228 pcache_chk_controls(
2229         Operation       *op,
2230         SlapReply       *rs )
2231 {
2232         const char      *non = "";
2233         const char      *stripped = "";
2234
2235         switch( op->o_pagedresults ) {
2236         case SLAP_CONTROL_NONCRITICAL:
2237                 non = "non-";
2238                 stripped = "; stripped";
2239                 /* fallthru */
2240
2241         case SLAP_CONTROL_CRITICAL:
2242                 Debug( pcache_debug, "%s: "
2243                         "%scritical pagedResults control "
2244                         "disabled with proxy cache%s.\n",
2245                         op->o_log_prefix, non, stripped );
2246
2247                 slap_remove_control( op, rs, slap_cids.sc_pagedResults, NULL );
2248                 break;
2249
2250         default:
2251                 rs->sr_err = SLAP_CB_CONTINUE;
2252                 break;
2253         }
2254
2255         return rs->sr_err;
2256 }
2257
2258 #ifdef PCACHE_CONTROL_PRIVDB
2259 static int
2260 pcache_op_privdb(
2261         Operation               *op,
2262         SlapReply               *rs )
2263 {
2264         slap_overinst   *on = (slap_overinst *)op->o_bd->bd_info;
2265         cache_manager   *cm = on->on_bi.bi_private;
2266         slap_callback   *save_cb;
2267         slap_op_t       type;
2268
2269         /* skip if control is unset */
2270         if ( op->o_ctrlflag[ privDB_cid ] != SLAP_CONTROL_CRITICAL ) {
2271                 return SLAP_CB_CONTINUE;
2272         }
2273
2274         /* The cache DB isn't open yet */
2275         if ( cm->defer_db_open ) {
2276                 send_ldap_error( op, rs, LDAP_UNAVAILABLE,
2277                         "pcachePrivDB: cacheDB not available" );
2278                 return rs->sr_err;
2279         }
2280
2281         /* FIXME: might be a little bit exaggerated... */
2282         if ( !be_isroot( op ) ) {
2283                 save_cb = op->o_callback;
2284                 op->o_callback = NULL;
2285                 send_ldap_error( op, rs, LDAP_UNWILLING_TO_PERFORM,
2286                         "pcachePrivDB: operation not allowed" );
2287                 op->o_callback = save_cb;
2288
2289                 return rs->sr_err;
2290         }
2291
2292         /* map tag to operation */
2293         type = slap_req2op( op->o_tag );
2294         if ( type != SLAP_OP_LAST ) {
2295                 BI_op_func      **func;
2296                 int             rc;
2297
2298                 /* execute, if possible */
2299                 func = &cm->db.be_bind;
2300                 if ( func[ type ] != NULL ) {
2301                         Operation       op2 = *op;
2302
2303                         op2.o_bd = &cm->db;
2304
2305                         rc = func[ type ]( &op2, rs );
2306                         if ( type == SLAP_OP_BIND && rc == LDAP_SUCCESS ) {
2307                                 op->o_conn->c_authz_cookie = cm->db.be_private;
2308                         }
2309                 }
2310         }
2311
2312         /* otherwise fall back to error */
2313         save_cb = op->o_callback;
2314         op->o_callback = NULL;
2315         send_ldap_error( op, rs, LDAP_UNWILLING_TO_PERFORM,
2316                 "operation not supported with pcachePrivDB control" );
2317         op->o_callback = save_cb;
2318
2319         return rs->sr_err;
2320 }
2321 #endif /* PCACHE_CONTROL_PRIVDB */
2322
2323 static int
2324 pcache_op_search(
2325         Operation       *op,
2326         SlapReply       *rs )
2327 {
2328         slap_overinst *on = (slap_overinst *)op->o_bd->bd_info;
2329         cache_manager *cm = on->on_bi.bi_private;
2330         query_manager*          qm = cm->qm;
2331
2332         int i = -1;
2333
2334         AttributeName   *filter_attrs = NULL;
2335
2336         Query           query;
2337         QueryTemplate   *qtemp = NULL;
2338
2339         int             attr_set = -1;
2340         CachedQuery     *answerable = NULL;
2341         int             cacheable = 0;
2342         int             fattr_cnt=0;
2343         int             fattr_got_oc = 0;
2344
2345         struct berval   tempstr;
2346
2347 #ifdef PCACHE_CONTROL_PRIVDB
2348         if ( op->o_ctrlflag[ privDB_cid ] == SLAP_CONTROL_CRITICAL ) {
2349                 return pcache_op_privdb( op, rs );
2350         }
2351 #endif /* PCACHE_CONTROL_PRIVDB */
2352
2353         /* The cache DB isn't open yet */
2354         if ( cm->defer_db_open ) {
2355                 send_ldap_error( op, rs, LDAP_UNAVAILABLE,
2356                         "pcachePrivDB: cacheDB not available" );
2357                 return rs->sr_err;
2358         }
2359
2360         /* pickup runtime ACL changes */
2361         cm->db.be_acl = op->o_bd->be_acl;
2362
2363         tempstr.bv_val = op->o_tmpalloc( op->ors_filterstr.bv_len+1, op->o_tmpmemctx );
2364         tempstr.bv_len = 0;
2365         if ( filter2template( op, op->ors_filter, &tempstr, &filter_attrs,
2366                 &fattr_cnt, &fattr_got_oc )) {
2367                 op->o_tmpfree( tempstr.bv_val, op->o_tmpmemctx );
2368                 return SLAP_CB_CONTINUE;
2369         }
2370
2371         Debug( pcache_debug, "query template of incoming query = %s\n",
2372                                         tempstr.bv_val, 0, 0 );
2373
2374         /* FIXME: cannot cache/answer requests with pagedResults control */
2375
2376         /* find attr set */
2377         attr_set = get_attr_set(op->ors_attrs, qm, cm->numattrsets);
2378
2379         query.filter = op->ors_filter;
2380         query.base = op->o_req_ndn;
2381         query.scope = op->ors_scope;
2382
2383         /* check for query containment */
2384         if (attr_set > -1) {
2385                 QueryTemplate *qt = qm->attr_sets[attr_set].templates;
2386                 for (; qt; qt = qt->qtnext ) {
2387                         /* find if template i can potentially answer tempstr */
2388                         if (qt->querystr.bv_len != tempstr.bv_len ||
2389                                 strcasecmp( qt->querystr.bv_val, tempstr.bv_val ))
2390                                 continue;
2391                         cacheable = 1;
2392                         qtemp = qt;
2393                         Debug( pcache_debug, "Entering QC, querystr = %s\n",
2394                                         op->ors_filterstr.bv_val, 0, 0 );
2395                         answerable = (*(qm->qcfunc))(op, qm, &query, qt);
2396
2397                         if (answerable)
2398                                 break;
2399                 }
2400         }
2401         op->o_tmpfree( tempstr.bv_val, op->o_tmpmemctx );
2402
2403         if (answerable) {
2404                 BackendDB       *save_bd = op->o_bd;
2405                 slap_callback   *save_cb = op->o_callback;
2406
2407                 Debug( pcache_debug, "QUERY ANSWERABLE\n", 0, 0, 0 );
2408                 op->o_tmpfree( filter_attrs, op->o_tmpmemctx );
2409                 ldap_pvt_thread_rdwr_rlock(&answerable->rwlock);
2410                 if ( BER_BVISNULL( &answerable->q_uuid )) {
2411                         /* No entries cached, just an empty result set */
2412                         i = rs->sr_err = 0;
2413                         send_ldap_result( op, rs );
2414                 } else {
2415                         op->o_bd = &cm->db;
2416                         if ( cm->response_cb == PCACHE_RESPONSE_CB_TAIL ) {
2417                                 /* The cached entry was already processed by any
2418                                  * other overlays, so don't let it get processed again.
2419                                  */
2420                                 op->o_callback = NULL;
2421                         }
2422                         i = cm->db.bd_info->bi_op_search( op, rs );
2423                 }
2424                 ldap_pvt_thread_rdwr_runlock(&answerable->rwlock);
2425                 ldap_pvt_thread_rdwr_runlock(&qtemp->t_rwlock);
2426                 op->o_bd = save_bd;
2427                 op->o_callback = save_cb;
2428                 return i;
2429         }
2430
2431         Debug( pcache_debug, "QUERY NOT ANSWERABLE\n", 0, 0, 0 );
2432
2433         ldap_pvt_thread_mutex_lock(&cm->cache_mutex);
2434         if (cm->num_cached_queries >= cm->max_queries) {
2435                 cacheable = 0;
2436         }
2437         ldap_pvt_thread_mutex_unlock(&cm->cache_mutex);
2438
2439         if (op->ors_attrsonly)
2440                 cacheable = 0;
2441
2442         if (cacheable) {
2443                 slap_callback           *cb;
2444                 struct search_info      *si;
2445
2446                 Debug( pcache_debug, "QUERY CACHEABLE\n", 0, 0, 0 );
2447                 query.filter = filter_dup(op->ors_filter, NULL);
2448                 ldap_pvt_thread_rdwr_wlock(&qtemp->t_rwlock);
2449                 if ( !qtemp->t_attrs.count ) {
2450                         qtemp->t_attrs.count = add_filter_attrs(op,
2451                                 &qtemp->t_attrs.attrs,
2452                                 &qm->attr_sets[attr_set],
2453                                 filter_attrs, fattr_cnt, fattr_got_oc);
2454                 }
2455                 ldap_pvt_thread_rdwr_wunlock(&qtemp->t_rwlock);
2456
2457                 cb = op->o_tmpalloc( sizeof(*cb) + sizeof(*si), op->o_tmpmemctx );
2458                 cb->sc_response = pcache_response;
2459                 cb->sc_cleanup = pcache_op_cleanup;
2460                 cb->sc_private = (cb+1);
2461                 si = cb->sc_private;
2462                 si->on = on;
2463                 si->query = query;
2464                 si->qtemp = qtemp;
2465                 si->max = cm->num_entries_limit ;
2466                 si->over = 0;
2467                 si->count = 0;
2468                 si->slimit = 0;
2469                 si->slimit_exceeded = 0;
2470                 si->caching_reason = PC_IGNORE;
2471                 if ( op->ors_slimit > 0 && op->ors_slimit < cm->num_entries_limit ) {
2472                         si->slimit = op->ors_slimit;
2473                         op->ors_slimit = cm->num_entries_limit;
2474                 }
2475                 si->head = NULL;
2476                 si->tail = NULL;
2477                 si->swap_saved_attrs = 1;
2478                 si->save_attrs = op->ors_attrs;
2479
2480                 op->ors_attrs = qtemp->t_attrs.attrs;
2481
2482                 if ( cm->response_cb == PCACHE_RESPONSE_CB_HEAD ) {
2483                         cb->sc_next = op->o_callback;
2484                         op->o_callback = cb;
2485
2486                 } else {
2487                         slap_callback           **pcb;
2488
2489                         /* need to move the callback at the end, in case other
2490                          * overlays are present, so that the final entry is
2491                          * actually cached */
2492                         cb->sc_next = NULL;
2493                         for ( pcb = &op->o_callback; *pcb; pcb = &(*pcb)->sc_next );
2494                         *pcb = cb;
2495                 }
2496
2497         } else {
2498                 Debug( pcache_debug, "QUERY NOT CACHEABLE\n",
2499                                         0, 0, 0);
2500         }
2501
2502         op->o_tmpfree( filter_attrs, op->o_tmpmemctx );
2503
2504         return SLAP_CB_CONTINUE;
2505 }
2506
2507 static int
2508 get_attr_set(
2509         AttributeName* attrs,
2510         query_manager* qm,
2511         int num )
2512 {
2513         int i;
2514         int count = 0;
2515
2516         if ( attrs ) {
2517                 for ( ; attrs[count].an_name.bv_val; count++ );
2518         }
2519
2520         /* recognize a single "*" or a "1.1" */
2521         if ( count == 0 ) {
2522                 count = 1;
2523                 attrs = slap_anlist_all_user_attributes;
2524
2525         } else if ( count == 1 && strcmp( attrs[0].an_name.bv_val, LDAP_NO_ATTRS ) == 0 ) {
2526                 count = 0;
2527                 attrs = NULL;
2528         }
2529
2530         for ( i = 0; i < num; i++ ) {
2531                 AttributeName *a2;
2532                 int found = 1;
2533
2534                 if ( count > qm->attr_sets[i].count ) {
2535                         continue;
2536                 }
2537
2538                 if ( !count ) {
2539                         if ( !qm->attr_sets[i].count ) {
2540                                 break;
2541                         }
2542                         continue;
2543                 }
2544
2545                 for ( a2 = attrs; a2->an_name.bv_val; a2++ ) {
2546                         if ( !an_find( qm->attr_sets[i].attrs, &a2->an_name ) ) {
2547                                 found = 0;
2548                                 break;
2549                         }
2550                 }
2551
2552                 if ( found ) {
2553                         break;
2554                 }
2555         }
2556
2557         if ( i == num ) {
2558                 i = -1;
2559         }
2560
2561         return i;
2562 }
2563
2564 static void*
2565 consistency_check(
2566         void *ctx,
2567         void *arg )
2568 {
2569         struct re_s *rtask = arg;
2570         slap_overinst *on = rtask->arg;
2571         cache_manager *cm = on->on_bi.bi_private;
2572         query_manager *qm = cm->qm;
2573         Connection conn = {0};
2574         OperationBuffer opbuf;
2575         Operation *op;
2576
2577         SlapReply rs = {REP_RESULT};
2578         CachedQuery* query;
2579         int return_val, pause = PCACHE_CC_PAUSED;
2580         QueryTemplate* templ;
2581
2582         /* Don't expire anything when we're offline */
2583         if ( cm->cc_paused & PCACHE_CC_OFFLINE ) {
2584                 pause = PCACHE_CC_OFFLINE;
2585                 goto leave;
2586         }
2587
2588         connection_fake_init( &conn, &opbuf, ctx );
2589         op = &opbuf.ob_op;
2590
2591         op->o_bd = &cm->db;
2592         op->o_dn = cm->db.be_rootdn;
2593         op->o_ndn = cm->db.be_rootndn;
2594
2595         cm->cc_arg = arg;
2596
2597         for (templ = qm->templates; templ; templ=templ->qmnext) {
2598                 query = templ->query_last;
2599                 if ( query ) pause = 0;
2600                 op->o_time = slap_get_time();
2601                 while (query && (query->expiry_time < op->o_time)) {
2602                         int rem = 0;
2603                         Debug( pcache_debug, "Lock CR index = %p\n",
2604                                         (void *) templ, 0, 0 );
2605                         ldap_pvt_thread_rdwr_wlock(&templ->t_rwlock);
2606                         if ( query == templ->query_last ) {
2607                                 rem = 1;
2608                                 remove_from_template(query, templ);
2609                                 Debug( pcache_debug, "TEMPLATE %p QUERIES-- %d\n",
2610                                                 (void *) templ, templ->no_of_queries, 0 );
2611                                 Debug( pcache_debug, "Unlock CR index = %p\n",
2612                                                 (void *) templ, 0, 0 );
2613                         }
2614                         ldap_pvt_thread_rdwr_wunlock(&templ->t_rwlock);
2615                         if ( !rem ) {
2616                                 query = templ->query_last;
2617                                 continue;
2618                         }
2619                         ldap_pvt_thread_mutex_lock(&qm->lru_mutex);
2620                         remove_query(qm, query);
2621                         ldap_pvt_thread_mutex_unlock(&qm->lru_mutex);
2622                         if ( BER_BVISNULL( &query->q_uuid ))
2623                                 return_val = 0;
2624                         else
2625                                 return_val = remove_query_data(op, &rs, &query->q_uuid);
2626                         Debug( pcache_debug, "STALE QUERY REMOVED, SIZE=%d\n",
2627                                                 return_val, 0, 0 );
2628                         ldap_pvt_thread_mutex_lock(&cm->cache_mutex);
2629                         cm->cur_entries -= return_val;
2630                         cm->num_cached_queries--;
2631                         Debug( pcache_debug, "STORED QUERIES = %lu\n",
2632                                         cm->num_cached_queries, 0, 0 );
2633                         ldap_pvt_thread_mutex_unlock(&cm->cache_mutex);
2634                         Debug( pcache_debug,
2635                                 "STALE QUERY REMOVED, CACHE ="
2636                                 "%d entries\n",
2637                                 cm->cur_entries, 0, 0 );
2638                         free_query(query);
2639                         query = templ->query_last;
2640                 }
2641         }
2642
2643 leave:
2644         ldap_pvt_thread_mutex_lock( &slapd_rq.rq_mutex );
2645         if ( ldap_pvt_runqueue_isrunning( &slapd_rq, rtask )) {
2646                 ldap_pvt_runqueue_stoptask( &slapd_rq, rtask );
2647         }
2648         /* If there were no queries, defer processing for a while */
2649         if ( cm->cc_paused != pause )
2650                 cm->cc_paused = pause;
2651         ldap_pvt_runqueue_resched( &slapd_rq, rtask, pause );
2652
2653         ldap_pvt_thread_mutex_unlock( &slapd_rq.rq_mutex );
2654         return NULL;
2655 }
2656
2657
2658 #define MAX_ATTR_SETS 500
2659
2660 enum {
2661         PC_MAIN = 1,
2662         PC_ATTR,
2663         PC_TEMP,
2664         PC_RESP,
2665         PC_QUERIES,
2666         PC_OFFLINE
2667 };
2668
2669 static ConfigDriver pc_cf_gen;
2670 static ConfigLDAPadd pc_ldadd;
2671 static ConfigCfAdd pc_cfadd;
2672
2673 static ConfigTable pccfg[] = {
2674         { "proxycache", "backend> <max_entries> <numattrsets> <entry limit> "
2675                                 "<cycle_time",
2676                 6, 6, 0, ARG_MAGIC|ARG_NO_DELETE|PC_MAIN, pc_cf_gen,
2677                 "( OLcfgOvAt:2.1 NAME 'olcProxyCache' "
2678                         "DESC 'ProxyCache basic parameters' "
2679                         "SYNTAX OMsDirectoryString SINGLE-VALUE )", NULL, NULL },
2680         { "proxyattrset", "index> <attributes...",
2681                 2, 0, 0, ARG_MAGIC|PC_ATTR, pc_cf_gen,
2682                 "( OLcfgOvAt:2.2 NAME 'olcProxyAttrset' "
2683                         "DESC 'A set of attributes to cache' "
2684                         "SYNTAX OMsDirectoryString )", NULL, NULL },
2685         { "proxytemplate", "filter> <attrset-index> <TTL> <negTTL",
2686                 4, 6, 0, ARG_MAGIC|PC_TEMP, pc_cf_gen,
2687                 "( OLcfgOvAt:2.3 NAME 'olcProxyTemplate' "
2688                         "DESC 'Filter template, attrset, cache TTL, "
2689                                 "optional negative TTL, optional sizelimit TTL' "
2690                         "SYNTAX OMsDirectoryString )", NULL, NULL },
2691         { "response-callback", "head|tail(default)",
2692                 2, 2, 0, ARG_MAGIC|PC_RESP, pc_cf_gen,
2693                 "( OLcfgOvAt:2.4 NAME 'olcProxyResponseCB' "
2694                         "DESC 'Response callback position in overlay stack' "
2695                         "SYNTAX OMsDirectoryString )", NULL, NULL },
2696         { "proxyCacheQueries", "queries",
2697                 2, 2, 0, ARG_INT|ARG_MAGIC|PC_QUERIES, pc_cf_gen,
2698                 "( OLcfgOvAt:2.5 NAME 'olcProxyCacheQueries' "
2699                         "DESC 'Maximum number of queries to cache' "
2700                         "SYNTAX OMsInteger )", NULL, NULL },
2701         { "proxySaveQueries", "TRUE|FALSE",
2702                 2, 2, 0, ARG_ON_OFF|ARG_OFFSET, (void *)offsetof(cache_manager, save_queries),
2703                 "( OLcfgOvAt:2.6 NAME 'olcProxySaveQueries' "
2704                         "DESC 'Save cached queries for hot restart' "
2705                         "SYNTAX OMsBoolean )", NULL, NULL },
2706         { "proxyCheckCacheability", "TRUE|FALSE",
2707                 2, 2, 0, ARG_ON_OFF|ARG_OFFSET, (void *)offsetof(cache_manager, check_cacheability),
2708                 "( OLcfgOvAt:2.7 NAME 'olcProxyCheckCacheability' "
2709                         "DESC 'Check whether the results of a query are cacheable, e.g. for schema issues' "
2710                         "SYNTAX OMsBoolean )", NULL, NULL },
2711         { "proxyCacheOffline", "TRUE|FALSE",
2712                 2, 2, 0, ARG_ON_OFF|ARG_MAGIC|PC_OFFLINE, pc_cf_gen,
2713                 "( OLcfgOvAt:2.8 NAME 'olcProxyCacheOffline' "
2714                         "DESC 'Set cache to offline mode and disable expiration' "
2715                         "SYNTAX OMsBoolean )", NULL, NULL },
2716
2717         { NULL, NULL, 0, 0, 0, ARG_IGNORED }
2718 };
2719
2720 static ConfigOCs pcocs[] = {
2721         { "( OLcfgOvOc:2.1 "
2722                 "NAME 'olcPcacheConfig' "
2723                 "DESC 'ProxyCache configuration' "
2724                 "SUP olcOverlayConfig "
2725                 "MUST ( olcProxyCache $ olcProxyAttrset $ olcProxyTemplate ) "
2726                 "MAY ( olcProxyResponseCB $ olcProxyCacheQueries $ olcProxySaveQueries $ olcProxyCheckCacheability $ olcProxyCacheOffline ) )",
2727                 Cft_Overlay, pccfg, NULL, pc_cfadd },
2728         { "( OLcfgOvOc:2.2 "
2729                 "NAME 'olcPcacheDatabase' "
2730                 "DESC 'Cache database configuration' "
2731                 "AUXILIARY )", Cft_Misc, olcDatabaseDummy, pc_ldadd },
2732         { NULL, 0, NULL }
2733 };
2734
2735 static int pcache_db_open2( slap_overinst *on, ConfigReply *cr );
2736
2737 static int
2738 pc_ldadd_cleanup( ConfigArgs *c )
2739 {
2740         slap_overinst *on = c->ca_private;
2741         return pcache_db_open2( on, &c->reply );
2742 }
2743
2744 static int
2745 pc_ldadd( CfEntryInfo *p, Entry *e, ConfigArgs *ca )
2746 {
2747         slap_overinst *on;
2748         cache_manager *cm;
2749
2750         if ( p->ce_type != Cft_Overlay || !p->ce_bi ||
2751                 p->ce_bi->bi_cf_ocs != pcocs )
2752                 return LDAP_CONSTRAINT_VIOLATION;
2753
2754         on = (slap_overinst *)p->ce_bi;
2755         cm = on->on_bi.bi_private;
2756         ca->be = &cm->db;
2757         /* Defer open if this is an LDAPadd */
2758         if ( CONFIG_ONLINE_ADD( ca ))
2759                 ca->cleanup = pc_ldadd_cleanup;
2760         else
2761                 cm->defer_db_open = 0;
2762         ca->ca_private = on;
2763         return LDAP_SUCCESS;
2764 }
2765
2766 static int
2767 pc_cfadd( Operation *op, SlapReply *rs, Entry *p, ConfigArgs *ca )
2768 {
2769         CfEntryInfo *pe = p->e_private;
2770         slap_overinst *on = (slap_overinst *)pe->ce_bi;
2771         cache_manager *cm = on->on_bi.bi_private;
2772         struct berval bv;
2773
2774         /* FIXME: should not hardcode "olcDatabase" here */
2775         bv.bv_len = snprintf( ca->cr_msg, sizeof( ca->cr_msg ),
2776                 "olcDatabase=" SLAP_X_ORDERED_FMT "%s",
2777                 0, cm->db.bd_info->bi_type );
2778         if ( bv.bv_len >= sizeof( ca->cr_msg ) ) {
2779                 return -1;
2780         }
2781         bv.bv_val = ca->cr_msg;
2782         ca->be = &cm->db;
2783         cm->defer_db_open = 0;
2784
2785         /* We can only create this entry if the database is table-driven
2786          */
2787         if ( cm->db.bd_info->bi_cf_ocs )
2788                 config_build_entry( op, rs, pe, ca, &bv, cm->db.bd_info->bi_cf_ocs,
2789                         &pcocs[1] );
2790
2791         return 0;
2792 }
2793
2794 static int
2795 pc_cf_gen( ConfigArgs *c )
2796 {
2797         slap_overinst   *on = (slap_overinst *)c->bi;
2798         cache_manager*  cm = on->on_bi.bi_private;
2799         query_manager*  qm = cm->qm;
2800         QueryTemplate*  temp;
2801         AttributeName*  attr_name;
2802         AttributeName*  attrarray;
2803         const char*     text=NULL;
2804         int             i, num, rc = 0;
2805         char            *ptr;
2806         unsigned long   t;
2807
2808         if ( c->op == SLAP_CONFIG_EMIT ) {
2809                 struct berval bv;
2810                 switch( c->type ) {
2811                 case PC_MAIN:
2812                         bv.bv_len = snprintf( c->cr_msg, sizeof( c->cr_msg ), "%s %d %d %d %ld",
2813                                 cm->db.bd_info->bi_type, cm->max_entries, cm->numattrsets,
2814                                 cm->num_entries_limit, cm->cc_period );
2815                         bv.bv_val = c->cr_msg;
2816                         value_add_one( &c->rvalue_vals, &bv );
2817                         break;
2818                 case PC_ATTR:
2819                         for (i=0; i<cm->numattrsets; i++) {
2820                                 if ( !qm->attr_sets[i].count ) continue;
2821
2822                                 bv.bv_len = snprintf( c->cr_msg, sizeof( c->cr_msg ), "%d", i );
2823
2824                                 /* count the attr length */
2825                                 for ( attr_name = qm->attr_sets[i].attrs;
2826                                         attr_name->an_name.bv_val; attr_name++ )
2827                                         bv.bv_len += attr_name->an_name.bv_len + 1;
2828
2829                                 bv.bv_val = ch_malloc( bv.bv_len+1 );
2830                                 ptr = lutil_strcopy( bv.bv_val, c->cr_msg );
2831                                 for ( attr_name = qm->attr_sets[i].attrs;
2832                                         attr_name->an_name.bv_val; attr_name++ ) {
2833                                         *ptr++ = ' ';
2834                                         ptr = lutil_strcopy( ptr, attr_name->an_name.bv_val );
2835                                 }
2836                                 ber_bvarray_add( &c->rvalue_vals, &bv );
2837                         }
2838                         if ( !c->rvalue_vals )
2839                                 rc = 1;
2840                         break;
2841                 case PC_TEMP:
2842                         for (temp=qm->templates; temp; temp=temp->qmnext) {
2843                                 /* HEADS-UP: always print all;
2844                                  * if optional == 0, ignore */
2845                                 bv.bv_len = snprintf( c->cr_msg, sizeof( c->cr_msg ),
2846                                         " %d %ld %ld %ld",
2847                                         temp->attr_set_index,
2848                                         temp->ttl,
2849                                         temp->negttl,
2850                                         temp->limitttl );
2851                                 bv.bv_len += temp->querystr.bv_len + 2;
2852                                 bv.bv_val = ch_malloc( bv.bv_len+1 );
2853                                 ptr = bv.bv_val;
2854                                 *ptr++ = '"';
2855                                 ptr = lutil_strcopy( ptr, temp->querystr.bv_val );
2856                                 *ptr++ = '"';
2857                                 strcpy( ptr, c->cr_msg );
2858                                 ber_bvarray_add( &c->rvalue_vals, &bv );
2859                         }
2860                         if ( !c->rvalue_vals )
2861                                 rc = 1;
2862                         break;
2863                 case PC_RESP:
2864                         if ( cm->response_cb == PCACHE_RESPONSE_CB_HEAD ) {
2865                                 BER_BVSTR( &bv, "head" );
2866                         } else {
2867                                 BER_BVSTR( &bv, "tail" );
2868                         }
2869                         value_add_one( &c->rvalue_vals, &bv );
2870                         break;
2871                 case PC_QUERIES:
2872                         c->value_int = cm->max_queries;
2873                         break;
2874                 case PC_OFFLINE:
2875                         c->value_int = (cm->cc_paused & PCACHE_CC_OFFLINE) != 0;
2876                         break;
2877                 }
2878                 return rc;
2879         } else if ( c->op == LDAP_MOD_DELETE ) {
2880                 rc = 1;
2881                 switch( c->type ) {
2882                 case PC_ATTR: /* FIXME */
2883                 case PC_TEMP:
2884                         break;
2885                 case PC_OFFLINE:
2886                         cm->cc_paused &= ~PCACHE_CC_OFFLINE;
2887                         rc = 0;
2888                         break;
2889                 }
2890                 return rc;
2891         }
2892
2893         switch( c->type ) {
2894         case PC_MAIN:
2895                 if ( cm->numattrsets > 0 ) {
2896                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "\"proxycache\" directive already provided" );
2897                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2898                         return( 1 );
2899                 }
2900
2901                 if ( lutil_atoi( &cm->numattrsets, c->argv[3] ) != 0 ) {
2902                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "unable to parse num attrsets=\"%s\" (arg #3)",
2903                                 c->argv[3] );
2904                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2905                         return( 1 );
2906                 }
2907                 if ( cm->numattrsets <= 0 ) {
2908                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "numattrsets (arg #3) must be positive" );
2909                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2910                         return( 1 );
2911                 }
2912                 if ( cm->numattrsets > MAX_ATTR_SETS ) {
2913                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "numattrsets (arg #3) must be <= %d", MAX_ATTR_SETS );
2914                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2915                         return( 1 );
2916                 }
2917
2918                 if ( !backend_db_init( c->argv[1], &cm->db, -1, NULL )) {
2919                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "unknown backend type (arg #1)" );
2920                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2921                         return( 1 );
2922                 }
2923
2924                 if ( lutil_atoi( &cm->max_entries, c->argv[2] ) != 0 ) {
2925                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "unable to parse max entries=\"%s\" (arg #2)",
2926                                 c->argv[2] );
2927                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2928                         return( 1 );
2929                 }
2930                 if ( cm->max_entries <= 0 ) {
2931                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "max entries (arg #2) must be positive.\n" );
2932                         Debug( LDAP_DEBUG_CONFIG, "%s: %s\n", c->log, c->cr_msg, 0 );
2933                         return( 1 );
2934                 }
2935
2936                 if ( lutil_atoi( &cm->num_entries_limit, c->argv[4] ) != 0 ) {
2937                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "unable to parse entry limit=\"%s\" (arg #4)",
2938                                 c->argv[4] );
2939                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2940                         return( 1 );
2941                 }
2942                 if ( cm->num_entries_limit <= 0 ) {
2943                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "entry limit (arg #4) must be positive" );
2944                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2945                         return( 1 );
2946                 }
2947                 if ( cm->num_entries_limit > cm->max_entries ) {
2948                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "entry limit (arg #4) must be less than max entries %d (arg #2)", cm->max_entries );
2949                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2950                         return( 1 );
2951                 }
2952
2953                 if ( lutil_parse_time( c->argv[5], &t ) != 0 ) {
2954                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "unable to parse period=\"%s\" (arg #5)",
2955                                 c->argv[5] );
2956                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2957                         return( 1 );
2958                 }
2959
2960                 cm->cc_period = (time_t)t;
2961                 Debug( pcache_debug,
2962                                 "Total # of attribute sets to be cached = %d.\n",
2963                                 cm->numattrsets, 0, 0 );
2964                 qm->attr_sets = ( struct attr_set * )ch_calloc( cm->numattrsets,
2965                                                 sizeof( struct attr_set ) );
2966                 break;
2967         case PC_ATTR:
2968                 if ( cm->numattrsets == 0 ) {
2969                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "\"proxycache\" directive not provided yet" );
2970                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2971                         return( 1 );
2972                 }
2973                 if ( lutil_atoi( &num, c->argv[1] ) != 0 ) {
2974                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "unable to parse attrset #=\"%s\"",
2975                                 c->argv[1] );
2976                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2977                         return( 1 );
2978                 }
2979
2980                 if ( num < 0 || num >= cm->numattrsets ) {
2981                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "attrset index %d out of bounds (must be %s%d)",
2982                                 num, cm->numattrsets > 1 ? "0->" : "", cm->numattrsets - 1 );
2983                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2984                         return 1;
2985                 }
2986                 qm->attr_sets[num].flags |= PC_CONFIGURED;
2987                 if ( c->argc == 2 ) {
2988                         /* assume "1.1" */
2989                         snprintf( c->cr_msg, sizeof( c->cr_msg ),
2990                                 "need an explicit attr in attrlist; use \"*\" to indicate all attrs" );
2991                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
2992                         return 1;
2993
2994                 } else if ( c->argc == 3 ) {
2995                         if ( strcmp( c->argv[2], LDAP_ALL_USER_ATTRIBUTES ) == 0 ) {
2996                                 qm->attr_sets[num].count = 1;
2997                                 qm->attr_sets[num].attrs = (AttributeName*)ch_calloc( 2,
2998                                         sizeof( AttributeName ) );
2999                                 BER_BVSTR( &qm->attr_sets[num].attrs[0].an_name, LDAP_ALL_USER_ATTRIBUTES );
3000                                 break;
3001
3002                         } else if ( strcmp( c->argv[2], LDAP_ALL_OPERATIONAL_ATTRIBUTES ) == 0 ) {
3003                                 qm->attr_sets[num].count = 1;
3004                                 qm->attr_sets[num].attrs = (AttributeName*)ch_calloc( 2,
3005                                         sizeof( AttributeName ) );
3006                                 BER_BVSTR( &qm->attr_sets[num].attrs[0].an_name, LDAP_ALL_OPERATIONAL_ATTRIBUTES );
3007                                 break;
3008
3009                         } else if ( strcmp( c->argv[2], LDAP_NO_ATTRS ) == 0 ) {
3010                                 break;
3011                         }
3012                         /* else: fallthru */
3013
3014                 } else if ( c->argc == 4 ) {
3015                         if ( ( strcmp( c->argv[2], LDAP_ALL_USER_ATTRIBUTES ) == 0 && strcmp( c->argv[3], LDAP_ALL_OPERATIONAL_ATTRIBUTES ) == 0 )
3016                                 || ( strcmp( c->argv[2], LDAP_ALL_OPERATIONAL_ATTRIBUTES ) == 0 && strcmp( c->argv[3], LDAP_ALL_USER_ATTRIBUTES ) == 0 ) )
3017                         {
3018                                 qm->attr_sets[num].count = 2;
3019                                 qm->attr_sets[num].attrs = (AttributeName*)ch_calloc( 3,
3020                                         sizeof( AttributeName ) );
3021                                 BER_BVSTR( &qm->attr_sets[num].attrs[0].an_name, LDAP_ALL_USER_ATTRIBUTES );
3022                                 BER_BVSTR( &qm->attr_sets[num].attrs[1].an_name, LDAP_ALL_OPERATIONAL_ATTRIBUTES );
3023                                 break;
3024                         }
3025                         /* else: fallthru */
3026                 }
3027
3028                 if ( c->argc > 2 ) {
3029                         int all_user = 0, all_op = 0;
3030
3031                         qm->attr_sets[num].count = c->argc - 2;
3032                         qm->attr_sets[num].attrs = (AttributeName*)ch_calloc( c->argc - 1,
3033                                 sizeof( AttributeName ) );
3034                         attr_name = qm->attr_sets[num].attrs;
3035                         for ( i = 2; i < c->argc; i++ ) {
3036                                 attr_name->an_desc = NULL;
3037                                 if ( strcmp( c->argv[i], LDAP_NO_ATTRS ) == 0 ) {
3038                                         snprintf( c->cr_msg, sizeof( c->cr_msg ),
3039                                                 "invalid attr #%d \"%s\" in attrlist",
3040                                                 i - 2, c->argv[i] );
3041                                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3042                                         ch_free( qm->attr_sets[num].attrs );
3043                                         qm->attr_sets[num].attrs = NULL;
3044                                         qm->attr_sets[num].count = 0;
3045                                         return 1;
3046                                 }
3047                                 if ( strcmp( c->argv[i], LDAP_ALL_USER_ATTRIBUTES ) == 0 ) {
3048                                         all_user = 1;
3049                                         BER_BVSTR( &attr_name->an_name, LDAP_ALL_USER_ATTRIBUTES );
3050                                 } else if ( strcmp( c->argv[i], LDAP_ALL_OPERATIONAL_ATTRIBUTES ) == 0 ) {
3051                                         all_op = 1;
3052                                         BER_BVSTR( &attr_name->an_name, LDAP_ALL_OPERATIONAL_ATTRIBUTES );
3053                                 } else {
3054                                         if ( slap_str2ad( c->argv[i], &attr_name->an_desc, &text ) ) {
3055                                                 strcpy( c->cr_msg, text );
3056                                                 Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3057                                                 ch_free( qm->attr_sets[num].attrs );
3058                                                 qm->attr_sets[num].attrs = NULL;
3059                                                 qm->attr_sets[num].count = 0;
3060                                                 return 1;
3061                                         }
3062                                         attr_name->an_name = attr_name->an_desc->ad_cname;
3063                                 }
3064                                 attr_name->an_oc = NULL;
3065                                 attr_name->an_flags = 0;
3066                                 if ( attr_name->an_desc == slap_schema.si_ad_objectClass )
3067                                         qm->attr_sets[num].flags |= PC_GOT_OC;
3068                                 attr_name++;
3069                                 BER_BVZERO( &attr_name->an_name );
3070                         }
3071
3072                         /* warn if list contains both "*" and "+" */
3073                         if ( i > 4 && all_user && all_op ) {
3074                                 snprintf( c->cr_msg, sizeof( c->cr_msg ),
3075                                         "warning: attribute list contains \"*\" and \"+\"" );
3076                                 Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3077                         }
3078                 }
3079                 break;
3080         case PC_TEMP:
3081                 if ( cm->numattrsets == 0 ) {
3082                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "\"proxycache\" directive not provided yet" );
3083                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3084                         return( 1 );
3085                 }
3086                 if ( lutil_atoi( &i, c->argv[2] ) != 0 ) {
3087                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "unable to parse template #=\"%s\"",
3088                                 c->argv[2] );
3089                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3090                         return( 1 );
3091                 }
3092
3093                 if ( i < 0 || i >= cm->numattrsets ||
3094                         !(qm->attr_sets[i].flags & PC_CONFIGURED )) {
3095                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "template index %d invalid (%s%d)",
3096                                 i, cm->numattrsets > 1 ? "0->" : "", cm->numattrsets - 1 );
3097                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3098                         return 1;
3099                 }
3100                 temp = ch_calloc( 1, sizeof( QueryTemplate ));
3101                 temp->qmnext = qm->templates;
3102                 qm->templates = temp;
3103                 ldap_pvt_thread_rdwr_init( &temp->t_rwlock );
3104                 temp->query = temp->query_last = NULL;
3105                 if ( lutil_parse_time( c->argv[3], &t ) != 0 ) {
3106                         snprintf( c->cr_msg, sizeof( c->cr_msg ),
3107                                 "unable to parse template ttl=\"%s\"",
3108                                 c->argv[3] );
3109                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3110                         return( 1 );
3111                 }
3112                 temp->ttl = (time_t)t;
3113                 temp->negttl = (time_t)0;
3114                 temp->limitttl = (time_t)0;
3115                 switch ( c->argc ) {
3116                 case 6:
3117                         if ( lutil_parse_time( c->argv[5], &t ) != 0 ) {
3118                                 snprintf( c->cr_msg, sizeof( c->cr_msg ),
3119                                         "unable to parse template sizelimit ttl=\"%s\"",
3120                                         c->argv[5] );
3121                                 Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3122                                         return( 1 );
3123                         }
3124                         temp->limitttl = (time_t)t;
3125                         /* fallthru */
3126
3127                 case 5:
3128                         if ( lutil_parse_time( c->argv[4], &t ) != 0 ) {
3129                                 snprintf( c->cr_msg, sizeof( c->cr_msg ),
3130                                         "unable to parse template negative ttl=\"%s\"",
3131                                         c->argv[4] );
3132                                 Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3133                                         return( 1 );
3134                         }
3135                         temp->negttl = (time_t)t;
3136                         break;
3137                 }
3138
3139                 temp->no_of_queries = 0;
3140
3141                 ber_str2bv( c->argv[1], 0, 1, &temp->querystr );
3142                 Debug( pcache_debug, "Template:\n", 0, 0, 0 );
3143                 Debug( pcache_debug, "  query template: %s\n",
3144                                 temp->querystr.bv_val, 0, 0 );
3145                 temp->attr_set_index = i;
3146                 qm->attr_sets[i].flags |= PC_REFERENCED;
3147                 temp->qtnext = qm->attr_sets[i].templates;
3148                 qm->attr_sets[i].templates = temp;
3149                 Debug( pcache_debug, "  attributes: \n", 0, 0, 0 );
3150                 if ( ( attrarray = qm->attr_sets[i].attrs ) != NULL ) {
3151                         for ( i=0; attrarray[i].an_name.bv_val; i++ )
3152                                 Debug( pcache_debug, "\t%s\n",
3153                                         attrarray[i].an_name.bv_val, 0, 0 );
3154                 }
3155                 break;
3156         case PC_RESP:
3157                 if ( strcasecmp( c->argv[1], "head" ) == 0 ) {
3158                         cm->response_cb = PCACHE_RESPONSE_CB_HEAD;
3159
3160                 } else if ( strcasecmp( c->argv[1], "tail" ) == 0 ) {
3161                         cm->response_cb = PCACHE_RESPONSE_CB_TAIL;
3162
3163                 } else {
3164                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "unknown specifier" );
3165                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3166                         return 1;
3167                 }
3168                 break;
3169         case PC_QUERIES:
3170                 if ( c->value_int <= 0 ) {
3171                         snprintf( c->cr_msg, sizeof( c->cr_msg ), "max queries must be positive" );
3172                         Debug( LDAP_DEBUG_CONFIG, "%s: %s.\n", c->log, c->cr_msg, 0 );
3173                         return( 1 );
3174                 }
3175                 cm->max_queries = c->value_int;
3176                 break;
3177         case PC_OFFLINE:
3178                 if ( c->value_int )
3179                         cm->cc_paused |= PCACHE_CC_OFFLINE;
3180                 else
3181                         cm->cc_paused &= ~PCACHE_CC_OFFLINE;
3182                 break;
3183         }
3184         return rc;
3185 }
3186
3187 static int
3188 pcache_db_config(
3189         BackendDB       *be,
3190         const char      *fname,
3191         int             lineno,
3192         int             argc,
3193         char            **argv
3194 )
3195 {
3196         slap_overinst   *on = (slap_overinst *)be->bd_info;
3197         cache_manager*  cm = on->on_bi.bi_private;
3198
3199         /* Something for the cache database? */
3200         if ( cm->db.bd_info && cm->db.bd_info->bi_db_config )
3201                 return cm->db.bd_info->bi_db_config( &cm->db, fname, lineno,
3202                         argc, argv );
3203         return SLAP_CONF_UNKNOWN;
3204 }
3205
3206 static int
3207 pcache_db_init(
3208         BackendDB *be,
3209         ConfigReply *cr)
3210 {
3211         slap_overinst *on = (slap_overinst *)be->bd_info;
3212         cache_manager *cm;
3213         query_manager *qm;
3214
3215         cm = (cache_manager *)ch_malloc(sizeof(cache_manager));
3216         on->on_bi.bi_private = cm;
3217
3218         qm = (query_manager*)ch_malloc(sizeof(query_manager));
3219
3220         cm->db = *be;
3221         SLAP_DBFLAGS(&cm->db) |= SLAP_DBFLAG_NO_SCHEMA_CHECK;
3222         cm->db.be_private = NULL;
3223         cm->db.bd_self = &cm->db;
3224         cm->qm = qm;
3225         cm->numattrsets = 0;
3226         cm->num_entries_limit = 5;
3227         cm->num_cached_queries = 0;
3228         cm->max_entries = 0;
3229         cm->cur_entries = 0;
3230         cm->max_queries = 10000;
3231         cm->save_queries = 0;
3232         cm->check_cacheability = 0;
3233         cm->response_cb = PCACHE_RESPONSE_CB_TAIL;
3234         cm->defer_db_open = 1;
3235         cm->cc_period = 1000;
3236         cm->cc_paused = 0;
3237         cm->cc_arg = NULL;
3238
3239         qm->attr_sets = NULL;
3240         qm->templates = NULL;
3241         qm->lru_top = NULL;
3242         qm->lru_bottom = NULL;
3243
3244         qm->qcfunc = query_containment;
3245         qm->crfunc = cache_replacement;
3246         qm->addfunc = add_query;
3247         ldap_pvt_thread_mutex_init(&qm->lru_mutex);
3248
3249         ldap_pvt_thread_mutex_init(&cm->cache_mutex);
3250         return 0;
3251 }
3252
3253 static int
3254 pcache_cachedquery_open_cb( Operation *op, SlapReply *rs )
3255 {
3256         assert( op->o_tag == LDAP_REQ_SEARCH );
3257
3258         if ( rs->sr_type == REP_SEARCH ) {
3259                 Attribute       *a;
3260
3261                 a = attr_find( rs->sr_entry->e_attrs, ad_cachedQueryURL );
3262                 if ( a != NULL ) {
3263                         BerVarray       *valsp;
3264
3265                         assert( a->a_nvals != NULL );
3266
3267                         valsp = op->o_callback->sc_private;
3268                         assert( *valsp == NULL );
3269
3270                         ber_bvarray_dup_x( valsp, a->a_nvals, op->o_tmpmemctx );
3271                 }
3272         }
3273
3274         return 0;
3275 }
3276
3277 static int
3278 pcache_cachedquery_count_cb( Operation *op, SlapReply *rs )
3279 {
3280         assert( op->o_tag == LDAP_REQ_SEARCH );
3281
3282         if ( rs->sr_type == REP_SEARCH ) {
3283                 int     *countp = (int *)op->o_callback->sc_private;
3284
3285                 (*countp)++;
3286         }
3287
3288         return 0;
3289 }
3290
3291 static int
3292 pcache_db_open2(
3293         slap_overinst *on,
3294         ConfigReply *cr )
3295 {
3296         cache_manager   *cm = on->on_bi.bi_private;
3297         query_manager*  qm = cm->qm;
3298         int rc;
3299
3300         rc = backend_startup_one( &cm->db, cr );
3301         if ( rc == 0 ) {
3302                 cm->defer_db_open = 0;
3303         }
3304
3305         /* There is no runqueue in TOOL mode */
3306         if (( slapMode & SLAP_SERVER_MODE ) && rc == 0 ) {
3307                 ldap_pvt_thread_mutex_lock( &slapd_rq.rq_mutex );
3308                 ldap_pvt_runqueue_insert( &slapd_rq, cm->cc_period,
3309                         consistency_check, on,
3310                         "pcache_consistency", cm->db.be_suffix[0].bv_val );
3311                 ldap_pvt_thread_mutex_unlock( &slapd_rq.rq_mutex );
3312
3313                 /* Cached database must have the rootdn */
3314                 if ( BER_BVISNULL( &cm->db.be_rootndn )
3315                                 || BER_BVISEMPTY( &cm->db.be_rootndn ) )
3316                 {
3317                         Debug( LDAP_DEBUG_ANY, "pcache_db_open(): "
3318                                 "underlying database of type \"%s\"\n"
3319                                 "    serving naming context \"%s\"\n"
3320                                 "    has no \"rootdn\", required by \"proxycache\".\n",
3321                                 on->on_info->oi_orig->bi_type,
3322                                 cm->db.be_suffix[0].bv_val, 0 );
3323                         return 1;
3324                 }
3325
3326                 if ( cm->save_queries ) {
3327                         void            *thrctx = ldap_pvt_thread_pool_context();
3328                         Connection      conn = { 0 };
3329                         OperationBuffer opbuf;
3330                         Operation       *op;
3331                         slap_callback   cb = { 0 };
3332                         SlapReply       rs = { 0 };
3333                         BerVarray       vals = NULL;
3334                         Filter          f = { 0 }, f2 = { 0 };
3335                         AttributeAssertion      ava = ATTRIBUTEASSERTION_INIT;
3336                         AttributeName   attrs[ 2 ] = {{{ 0 }}};
3337
3338                         connection_fake_init( &conn, &opbuf, thrctx );
3339                         op = &opbuf.ob_op;
3340
3341                         op->o_bd = &cm->db;
3342
3343                         op->o_tag = LDAP_REQ_SEARCH;
3344                         op->o_protocol = LDAP_VERSION3;
3345                         cb.sc_response = pcache_cachedquery_open_cb;
3346                         cb.sc_private = &vals;
3347                         op->o_callback = &cb;
3348                         op->o_time = slap_get_time();
3349                         op->o_do_not_cache = 1;
3350                         op->o_managedsait = SLAP_CONTROL_CRITICAL;
3351
3352                         op->o_dn = cm->db.be_rootdn;
3353                         op->o_ndn = cm->db.be_rootndn;
3354                         op->o_req_dn = cm->db.be_suffix[ 0 ];
3355                         op->o_req_ndn = cm->db.be_nsuffix[ 0 ];
3356
3357                         op->ors_scope = LDAP_SCOPE_BASE;
3358                         op->ors_deref = LDAP_DEREF_NEVER;
3359                         op->ors_slimit = 1;
3360                         op->ors_tlimit = SLAP_NO_LIMIT;
3361                         ber_str2bv( "(cachedQueryURL=*)", 0, 0, &op->ors_filterstr );
3362                         f.f_choice = LDAP_FILTER_PRESENT;
3363                         f.f_desc = ad_cachedQueryURL;
3364                         op->ors_filter = &f;
3365                         attrs[ 0 ].an_desc = ad_cachedQueryURL;
3366                         attrs[ 0 ].an_name = ad_cachedQueryURL->ad_cname;
3367                         op->ors_attrs = attrs;
3368                         op->ors_attrsonly = 0;
3369
3370                         rc = op->o_bd->be_search( op, &rs );
3371                         if ( rc == LDAP_SUCCESS && vals != NULL ) {
3372                                 int     i;
3373
3374                                 for ( i = 0; !BER_BVISNULL( &vals[ i ] ); i++ ) {
3375                                         if ( url2query( vals[ i ].bv_val, op, qm ) == 0 ) {
3376                                                 cm->num_cached_queries++;
3377                                         }
3378                                 }
3379
3380                                 ber_bvarray_free_x( vals, op->o_tmpmemctx );
3381                         }
3382
3383                         /* count cached entries */
3384                         f.f_choice = LDAP_FILTER_NOT;
3385                         f.f_not = &f2;
3386                         f2.f_choice = LDAP_FILTER_EQUALITY;
3387                         f2.f_ava = &ava;
3388                         f2.f_av_desc = slap_schema.si_ad_objectClass;
3389                         BER_BVSTR( &f2.f_av_value, "glue" );
3390                         ber_str2bv( "(!(objectClass=glue))", 0, 0, &op->ors_filterstr );
3391
3392                         op->ors_slimit = SLAP_NO_LIMIT;
3393                         op->ors_scope = LDAP_SCOPE_SUBTREE;
3394                         op->ors_attrs = slap_anlist_no_attrs;
3395
3396                         op->o_callback->sc_response = pcache_cachedquery_count_cb;
3397                         rs.sr_nentries = 0;
3398                         op->o_callback->sc_private = &rs.sr_nentries;
3399
3400                         rc = op->o_bd->be_search( op, &rs );
3401
3402                         cm->cur_entries = rs.sr_nentries;
3403
3404                         /* ignore errors */
3405                         rc = 0;
3406                 }
3407         }
3408         return rc;
3409 }
3410
3411 static int
3412 pcache_db_open(
3413         BackendDB *be,
3414         ConfigReply *cr )
3415 {
3416         slap_overinst   *on = (slap_overinst *)be->bd_info;
3417         cache_manager   *cm = on->on_bi.bi_private;
3418         query_manager*  qm = cm->qm;
3419         int             i, ncf = 0, rf = 0, nrf = 0, rc = 0;
3420
3421         /* check attr sets */
3422         for ( i = 0; i < cm->numattrsets; i++) {
3423                 if ( !( qm->attr_sets[i].flags & PC_CONFIGURED ) ) {
3424                         if ( qm->attr_sets[i].flags & PC_REFERENCED ) {
3425                                 Debug( LDAP_DEBUG_CONFIG, "pcache: attr set #%d not configured but referenced.\n", i, 0, 0 );
3426                                 rf++;
3427
3428                         } else {
3429                                 Debug( LDAP_DEBUG_CONFIG, "pcache: warning, attr set #%d not configured.\n", i, 0, 0 );
3430                         }
3431                         ncf++;
3432
3433                 } else if ( !( qm->attr_sets[i].flags & PC_REFERENCED ) ) {
3434                         Debug( LDAP_DEBUG_CONFIG, "pcache: attr set #%d configured but not referenced.\n", i, 0, 0 );
3435                         nrf++;
3436                 }
3437         }
3438
3439         if ( ncf || rf || nrf ) {
3440                 Debug( LDAP_DEBUG_CONFIG, "pcache: warning, %d attr sets configured but not referenced.\n", nrf, 0, 0 );
3441                 Debug( LDAP_DEBUG_CONFIG, "pcache: warning, %d attr sets not configured.\n", ncf, 0, 0 );
3442                 Debug( LDAP_DEBUG_CONFIG, "pcache: %d attr sets not configured but referenced.\n", rf, 0, 0 );
3443
3444                 if ( rf > 0 ) {
3445                         return 1;
3446                 }
3447         }
3448
3449         /* need to inherit something from the original database... */
3450         cm->db.be_def_limit = be->be_def_limit;
3451         cm->db.be_limits = be->be_limits;
3452         cm->db.be_acl = be->be_acl;
3453         cm->db.be_dfltaccess = be->be_dfltaccess;
3454
3455         if ( SLAP_DBMONITORING( be ) ) {
3456                 SLAP_DBFLAGS( &cm->db ) |= SLAP_DBFLAG_MONITORING;
3457
3458         } else {
3459                 SLAP_DBFLAGS( &cm->db ) &= ~SLAP_DBFLAG_MONITORING;
3460         }
3461
3462         if ( !cm->defer_db_open )
3463                 rc = pcache_db_open2( on, cr );
3464
3465         return rc;
3466 }
3467
3468 static void
3469 pcache_free_qbase( void *v )
3470 {
3471         Qbase *qb = v;
3472         int i;
3473
3474         for (i=0; i<3; i++)
3475                 tavl_free( qb->scopes[i], NULL );
3476         ch_free( qb );
3477 }
3478
3479 static int
3480 pcache_db_close(
3481         BackendDB *be,
3482         ConfigReply *cr
3483 )
3484 {
3485         slap_overinst *on = (slap_overinst *)be->bd_info;
3486         cache_manager *cm = on->on_bi.bi_private;
3487         query_manager *qm = cm->qm;
3488         QueryTemplate *tm;
3489         int i, rc = 0;
3490
3491         if ( cm->save_queries ) {
3492                 CachedQuery     *qc;
3493                 BerVarray       vals = NULL;
3494
3495                 void            *thrctx;
3496                 Connection      conn = { 0 };
3497                 OperationBuffer opbuf;
3498                 Operation       *op;
3499                 slap_callback   cb = { 0 };
3500
3501                 SlapReply       rs = { REP_RESULT };
3502                 Modifications   mod = {{ 0 }};
3503
3504                 thrctx = ldap_pvt_thread_pool_context();
3505
3506                 connection_fake_init( &conn, &opbuf, thrctx );
3507                 op = &opbuf.ob_op;
3508
3509                 if ( qm->templates != NULL ) {
3510                         for ( tm = qm->templates; tm != NULL; tm = tm->qmnext ) {
3511                                 for ( qc = tm->query; qc; qc = qc->next ) {
3512                                         struct berval   bv;
3513
3514                                         if ( query2url( op, qc, &bv ) == 0 ) {
3515                                                 ber_bvarray_add_x( &vals, &bv, op->o_tmpmemctx );
3516                                         }
3517                                 }
3518                         }
3519                 }
3520
3521                 op->o_bd = &cm->db;
3522                 op->o_dn = cm->db.be_rootdn;
3523                 op->o_ndn = cm->db.be_rootndn;
3524
3525                 op->o_tag = LDAP_REQ_MODIFY;
3526                 op->o_protocol = LDAP_VERSION3;
3527                 cb.sc_response = slap_null_cb;
3528                 op->o_callback = &cb;
3529                 op->o_time = slap_get_time();
3530                 op->o_do_not_cache = 1;
3531                 op->o_managedsait = SLAP_CONTROL_CRITICAL;
3532
3533                 op->o_req_dn = op->o_bd->be_suffix[0];
3534                 op->o_req_ndn = op->o_bd->be_nsuffix[0];
3535
3536                 mod.sml_op = LDAP_MOD_REPLACE;
3537                 mod.sml_flags = 0;
3538                 mod.sml_desc = ad_cachedQueryURL;
3539                 mod.sml_type = ad_cachedQueryURL->ad_cname;
3540                 mod.sml_values = vals;
3541                 mod.sml_nvalues = NULL;
3542                 mod.sml_numvals = 1;
3543                 mod.sml_next = NULL;
3544                 Debug( pcache_debug,
3545                         "%sSETTING CACHED QUERY URLS\n",
3546                         vals == NULL ? "RE" : "", 0, 0 );
3547
3548                 op->orm_modlist = &mod;
3549
3550                 op->o_bd->be_modify( op, &rs );
3551
3552                 ber_bvarray_free_x( vals, op->o_tmpmemctx );
3553         }
3554
3555         /* cleanup stuff inherited from the original database... */
3556         cm->db.be_limits = NULL;
3557         cm->db.be_acl = NULL;
3558
3559         /* stop the thread ... */
3560         if ( cm->cc_arg ) {
3561                 ldap_pvt_thread_mutex_lock( &slapd_rq.rq_mutex );
3562                 if ( ldap_pvt_runqueue_isrunning( &slapd_rq, cm->cc_arg ) ) {
3563                         ldap_pvt_runqueue_stoptask( &slapd_rq, cm->cc_arg );
3564                 }
3565                 ldap_pvt_runqueue_remove( &slapd_rq, cm->cc_arg );
3566                 ldap_pvt_thread_mutex_unlock( &slapd_rq.rq_mutex );
3567         }
3568
3569         if ( cm->db.bd_info->bi_db_close ) {
3570                 rc = cm->db.bd_info->bi_db_close( &cm->db, NULL );
3571         }
3572         while ( (tm = qm->templates) != NULL ) {
3573                 CachedQuery *qc, *qn;
3574                 qm->templates = tm->qmnext;
3575                 for ( qc = tm->query; qc; qc = qn ) {
3576                         qn = qc->next;
3577                         free_query( qc );
3578                 }
3579                 avl_free( tm->qbase, pcache_free_qbase );
3580                 free( tm->querystr.bv_val );
3581                 ldap_pvt_thread_rdwr_destroy( &tm->t_rwlock );
3582                 free( tm->t_attrs.attrs );
3583                 free( tm );
3584         }
3585
3586         for ( i=0; i<cm->numattrsets; i++ ) {
3587                 free( qm->attr_sets[i].attrs );
3588         }
3589         free( qm->attr_sets );
3590         qm->attr_sets = NULL;
3591
3592         return rc;
3593 }
3594
3595 static int
3596 pcache_db_destroy(
3597         BackendDB *be,
3598         ConfigReply *cr
3599 )
3600 {
3601         slap_overinst *on = (slap_overinst *)be->bd_info;
3602         cache_manager *cm = on->on_bi.bi_private;
3603         query_manager *qm = cm->qm;
3604
3605         if ( cm->db.be_private != NULL ) {
3606                 backend_stopdown_one( &cm->db );
3607         }
3608
3609         ldap_pvt_thread_mutex_destroy( &qm->lru_mutex );
3610         ldap_pvt_thread_mutex_destroy( &cm->cache_mutex );
3611         free( qm );
3612         free( cm );
3613
3614         return 0;
3615 }
3616
3617 #ifdef PCACHE_CONTROL_PRIVDB
3618 /*
3619         Control ::= SEQUENCE {
3620              controlType             LDAPOID,
3621              criticality             BOOLEAN DEFAULT FALSE,
3622              controlValue            OCTET STRING OPTIONAL }
3623
3624         controlType ::= 1.3.6.1.4.1.4203.666.11.9.5.1
3625
3626  * criticality must be TRUE; controlValue must be absent.
3627  */
3628 static int
3629 parse_privdb_ctrl(
3630         Operation       *op,
3631         SlapReply       *rs,
3632         LDAPControl     *ctrl )
3633 {
3634         if ( op->o_ctrlflag[ privDB_cid ] != SLAP_CONTROL_NONE ) {
3635                 rs->sr_text = "privateDB control specified multiple times";
3636                 return LDAP_PROTOCOL_ERROR;
3637         }
3638
3639         if ( !BER_BVISNULL( &ctrl->ldctl_value ) ) {
3640                 rs->sr_text = "privateDB control value not absent";
3641                 return LDAP_PROTOCOL_ERROR;
3642         }
3643
3644         if ( !ctrl->ldctl_iscritical ) {
3645                 rs->sr_text = "privateDB control criticality required";
3646                 return LDAP_PROTOCOL_ERROR;
3647         }
3648
3649         op->o_ctrlflag[ privDB_cid ] = SLAP_CONTROL_CRITICAL;
3650
3651         return LDAP_SUCCESS;
3652 }
3653
3654 static char *extops[] = {
3655         LDAP_EXOP_MODIFY_PASSWD,
3656         NULL
3657 };
3658 #endif /* PCACHE_CONTROL_PRIVDB */
3659
3660 #ifdef PCACHE_EXOP_QUERY_DELETE
3661 static struct berval pcache_exop_QUERY_DELETE = BER_BVC( PCACHE_EXOP_QUERY_DELETE );
3662
3663 #define LDAP_TAG_EXOP_QUERY_DELETE_BASE ((LBER_CLASS_CONTEXT|LBER_CONSTRUCTED) + 0)
3664 #define LDAP_TAG_EXOP_QUERY_DELETE_DN   ((LBER_CLASS_CONTEXT|LBER_CONSTRUCTED) + 1)
3665 #define LDAP_TAG_EXOP_QUERY_DELETE_UUID ((LBER_CLASS_CONTEXT|LBER_CONSTRUCTED) + 2)
3666
3667 /*
3668         ExtendedRequest ::= [APPLICATION 23] SEQUENCE {
3669              requestName      [0] LDAPOID,
3670              requestValue     [1] OCTET STRING OPTIONAL }
3671
3672         requestName ::= 1.3.6.1.4.1.4203.666.11.9.6.1
3673
3674         requestValue ::= SEQUENCE { CHOICE {
3675                   baseDN           [0] LDAPDN
3676                   entryDN          [1] LDAPDN },
3677              queryID          [2] OCTET STRING (SIZE(16))
3678                   -- constrained to UUID }
3679
3680  * Either baseDN or entryDN must be present, to allow database selection.
3681  *
3682  * 1. if baseDN and queryID are present, then the query corresponding
3683  *    to queryID is deleted;
3684  * 2. if baseDN is present and queryID is absent, then all queries
3685  *    are deleted;
3686  * 3. if entryDN is present and queryID is absent, then all queries
3687  *    corresponding to the queryID values present in entryDN are deleted;
3688  * 4. if entryDN and queryID are present, then all queries
3689  *    corresponding to the queryID values present in entryDN are deleted,
3690  *    but only if the value of queryID is contained in the entry;
3691  *
3692  * Currently, only 1, 3 and 4 are implemented.  2 can be obtained by either
3693  * recursively deleting the database (ldapdelete -r) with PRIVDB control,
3694  * or by removing the database files.
3695
3696         ExtendedResponse ::= [APPLICATION 24] SEQUENCE {
3697              COMPONENTS OF LDAPResult,
3698              responseName     [10] LDAPOID OPTIONAL,
3699              responseValue    [11] OCTET STRING OPTIONAL }
3700
3701  * responseName and responseValue must be absent.
3702  */
3703
3704 /*
3705  * - on success, *tagp is either LDAP_TAG_EXOP_QUERY_DELETE_BASE
3706  *   or LDAP_TAG_EXOP_QUERY_DELETE_DN.
3707  * - if ndn != NULL, it is set to the normalized DN in the request
3708  *   corresponding to either the baseDN or the entryDN, according
3709  *   to *tagp; memory is malloc'ed on the Operation's slab, and must
3710  *   be freed by the caller.
3711  * - if uuid != NULL, it is set to point to the normalized UUID;
3712  *   memory is malloc'ed on the Operation's slab, and must
3713  *   be freed by the caller.
3714  */
3715 static int
3716 pcache_parse_query_delete(
3717         struct berval   *in,
3718         ber_tag_t       *tagp,
3719         struct berval   *ndn,
3720         struct berval   *uuid,
3721         const char      **text,
3722         void            *ctx )
3723 {
3724         int                     rc = LDAP_SUCCESS;
3725         ber_tag_t               tag;
3726         ber_len_t               len = -1;
3727         BerElementBuffer        berbuf;
3728         BerElement              *ber = (BerElement *)&berbuf;
3729         struct berval           reqdata = BER_BVNULL;
3730
3731         *text = NULL;
3732
3733         if ( ndn ) {
3734                 BER_BVZERO( ndn );
3735         }
3736
3737         if ( uuid ) {
3738                 BER_BVZERO( uuid );
3739         }
3740
3741         if ( in == NULL || in->bv_len == 0 ) {
3742                 *text = "empty request data field in queryDelete exop";
3743                 return LDAP_PROTOCOL_ERROR;
3744         }
3745
3746         ber_dupbv_x( &reqdata, in, ctx );
3747
3748         /* ber_init2 uses reqdata directly, doesn't allocate new buffers */
3749         ber_init2( ber, &reqdata, 0 );
3750
3751         tag = ber_scanf( ber, "{" /*}*/ );
3752
3753         if ( tag == LBER_ERROR ) {
3754                 Debug( LDAP_DEBUG_TRACE,
3755                         "pcache_parse_query_delete: decoding error.\n",
3756                         0, 0, 0 );
3757                 goto decoding_error;
3758         }
3759
3760         tag = ber_peek_tag( ber, &len );
3761         if ( tag == LDAP_TAG_EXOP_QUERY_DELETE_BASE
3762                 || tag == LDAP_TAG_EXOP_QUERY_DELETE_DN )
3763         {
3764                 *tagp = tag;
3765
3766                 if ( ndn != NULL ) {
3767                         struct berval   dn;
3768
3769                         tag = ber_scanf( ber, "m", &dn );
3770                         if ( tag == LBER_ERROR ) {
3771                                 Debug( LDAP_DEBUG_TRACE,
3772                                         "pcache_parse_query_delete: DN parse failed.\n",
3773                                         0, 0, 0 );
3774                                 goto decoding_error;
3775                         }
3776
3777                         rc = dnNormalize( 0, NULL, NULL, &dn, ndn, ctx );
3778                         if ( rc != LDAP_SUCCESS ) {
3779                                 *text = "invalid DN in queryDelete exop request data";
3780                                 goto done;
3781                         }
3782
3783                 } else {
3784                         tag = ber_scanf( ber, "x" /* "m" */ );
3785                         if ( tag == LBER_DEFAULT ) {
3786                                 goto decoding_error;
3787                         }
3788                 }
3789
3790                 tag = ber_peek_tag( ber, &len );
3791         }
3792
3793         if ( tag == LDAP_TAG_EXOP_QUERY_DELETE_UUID ) {
3794                 if ( uuid != NULL ) {
3795                         struct berval   bv;
3796                         char            uuidbuf[ LDAP_LUTIL_UUIDSTR_BUFSIZE ];
3797
3798                         tag = ber_scanf( ber, "m", &bv );
3799                         if ( tag == LBER_ERROR ) {
3800                                 Debug( LDAP_DEBUG_TRACE,
3801                                         "pcache_parse_query_delete: UUID parse failed.\n",
3802                                         0, 0, 0 );
3803                                 goto decoding_error;
3804                         }
3805
3806                         if ( bv.bv_len != 16 ) {
3807                                 Debug( LDAP_DEBUG_TRACE,
3808                                         "pcache_parse_query_delete: invalid UUID length %lu.\n",
3809                                         (unsigned long)bv.bv_len, 0, 0 );
3810                                 goto decoding_error;
3811                         }
3812
3813                         rc = lutil_uuidstr_from_normalized(
3814                                 bv.bv_val, bv.bv_len,
3815                                 uuidbuf, sizeof( uuidbuf ) );
3816                         if ( rc == -1 ) {
3817                                 goto decoding_error;
3818                         }
3819                         ber_str2bv( uuidbuf, rc, 1, uuid );
3820                         rc = LDAP_SUCCESS;
3821
3822                 } else {
3823                         tag = ber_skip_tag( ber, &len );
3824                         if ( tag == LBER_DEFAULT ) {
3825                                 goto decoding_error;
3826                         }
3827
3828                         if ( len != 16 ) {
3829                                 Debug( LDAP_DEBUG_TRACE,
3830                                         "pcache_parse_query_delete: invalid UUID length %lu.\n",
3831                                         (unsigned long)len, 0, 0 );
3832                                 goto decoding_error;
3833                         }
3834                 }
3835
3836                 tag = ber_peek_tag( ber, &len );
3837         }
3838
3839         if ( tag != LBER_DEFAULT || len != 0 ) {
3840 decoding_error:;
3841                 Debug( LDAP_DEBUG_TRACE,
3842                         "pcache_parse_query_delete: decoding error\n",
3843                         0, 0, 0 );
3844                 rc = LDAP_PROTOCOL_ERROR;
3845                 *text = "queryDelete data decoding error";
3846
3847 done:;
3848                 if ( ndn && !BER_BVISNULL( ndn ) ) {
3849                         slap_sl_free( ndn->bv_val, ctx );
3850                         BER_BVZERO( ndn );
3851                 }
3852
3853                 if ( uuid && !BER_BVISNULL( uuid ) ) {
3854                         slap_sl_free( uuid->bv_val, ctx );
3855                         BER_BVZERO( uuid );
3856                 }
3857         }
3858
3859         if ( !BER_BVISNULL( &reqdata ) ) {
3860                 ber_memfree_x( reqdata.bv_val, ctx );
3861         }
3862
3863         return rc;
3864 }
3865
3866 static int
3867 pcache_exop_query_delete(
3868         Operation       *op,
3869         SlapReply       *rs )
3870 {
3871         BackendDB       *bd = op->o_bd;
3872
3873         struct berval   uuid = BER_BVNULL,
3874                         *uuidp = NULL;
3875         char            buf[ SLAP_TEXT_BUFLEN ];
3876         unsigned        len;
3877         ber_tag_t       tag = LBER_DEFAULT;
3878
3879         if ( LogTest( LDAP_DEBUG_STATS ) ) {
3880                 uuidp = &uuid;
3881         }
3882
3883         rs->sr_err = pcache_parse_query_delete( op->ore_reqdata,
3884                 &tag, &op->o_req_ndn, uuidp,
3885                 &rs->sr_text, op->o_tmpmemctx );
3886         if ( rs->sr_err != LDAP_SUCCESS ) {
3887                 return rs->sr_err;
3888         }
3889
3890         if ( LogTest( LDAP_DEBUG_STATS ) ) {
3891                 assert( !BER_BVISNULL( &op->o_req_ndn ) );
3892                 len = snprintf( buf, sizeof( buf ), " dn=\"%s\"", op->o_req_ndn.bv_val );
3893
3894                 if ( !BER_BVISNULL( &uuid ) && len < sizeof( buf ) ) {
3895                         snprintf( &buf[ len ], sizeof( buf ) - len, " queryId=\"%s\"", uuid.bv_val );
3896                 }
3897
3898                 Debug( LDAP_DEBUG_STATS, "%s QUERY DELETE%s\n",
3899                         op->o_log_prefix, buf, 0 );
3900         }
3901         op->o_req_dn = op->o_req_ndn;
3902
3903         op->o_bd = select_backend( &op->o_req_ndn, 0 );
3904         rs->sr_err = backend_check_restrictions( op, rs,
3905                 (struct berval *)&pcache_exop_QUERY_DELETE );
3906         if ( rs->sr_err != LDAP_SUCCESS ) {
3907                 goto done;
3908         }
3909
3910         if ( op->o_bd->be_extended == NULL ) {
3911                 send_ldap_error( op, rs, LDAP_UNAVAILABLE_CRITICAL_EXTENSION,
3912                         "backend does not support extended operations" );
3913                 goto done;
3914         }
3915
3916         op->o_bd->be_extended( op, rs );
3917
3918 done:;
3919         if ( !BER_BVISNULL( &op->o_req_ndn ) ) {
3920                 op->o_tmpfree( op->o_req_ndn.bv_val, op->o_tmpmemctx );
3921                 BER_BVZERO( &op->o_req_ndn );
3922                 BER_BVZERO( &op->o_req_dn );
3923         }
3924
3925         if ( !BER_BVISNULL( &uuid ) ) {
3926                 op->o_tmpfree( uuid.bv_val, op->o_tmpmemctx );
3927         }
3928
3929         op->o_bd = bd;
3930
3931         return rs->sr_err;
3932 }
3933
3934 static int
3935 pcache_op_extended( Operation *op, SlapReply *rs )
3936 {
3937         slap_overinst   *on = (slap_overinst *)op->o_bd->bd_info;
3938         cache_manager   *cm = on->on_bi.bi_private;
3939
3940 #ifdef PCACHE_CONTROL_PRIVDB
3941         if ( op->o_ctrlflag[ privDB_cid ] == SLAP_CONTROL_CRITICAL ) {
3942                 return pcache_op_privdb( op, rs );
3943         }
3944 #endif /* PCACHE_CONTROL_PRIVDB */
3945
3946         if ( bvmatch( &op->ore_reqoid, &pcache_exop_QUERY_DELETE ) ) {
3947                 struct berval   uuid = BER_BVNULL;
3948                 ber_tag_t       tag = LBER_DEFAULT;
3949
3950                 rs->sr_err = pcache_parse_query_delete( op->ore_reqdata,
3951                         &tag, NULL, &uuid, &rs->sr_text, op->o_tmpmemctx );
3952                 assert( rs->sr_err == LDAP_SUCCESS );
3953
3954                 if ( tag == LDAP_TAG_EXOP_QUERY_DELETE_DN ) {
3955                         /* remove all queries related to the selected entry */
3956                         rs->sr_err = pcache_remove_entry_queries_from_cache( op,
3957                                 cm, &op->o_req_ndn, &uuid );
3958
3959                 } else if ( tag == LDAP_TAG_EXOP_QUERY_DELETE_BASE ) {
3960                         if ( !BER_BVISNULL( &uuid ) ) {
3961                                 /* remove the selected query */
3962                                 rs->sr_err = pcache_remove_query_from_cache( op,
3963                                         cm, &uuid );
3964
3965                         } else {
3966                                 /* TODO: remove all queries */
3967                                 rs->sr_err = LDAP_UNWILLING_TO_PERFORM;
3968                                 rs->sr_text = "deletion of all queries not implemented";
3969                         }
3970                 }
3971
3972                 op->o_tmpfree( uuid.bv_val, op->o_tmpmemctx );
3973         }
3974
3975         return rs->sr_err;
3976 }
3977 #endif /* PCACHE_EXOP_QUERY_DELETE */
3978
3979 static slap_overinst pcache;
3980
3981 static char *obsolete_names[] = {
3982         "proxycache",
3983         NULL
3984 };
3985
3986 #if SLAPD_OVER_PROXYCACHE == SLAPD_MOD_DYNAMIC
3987 static
3988 #endif /* SLAPD_OVER_PROXYCACHE == SLAPD_MOD_DYNAMIC */
3989 int
3990 pcache_initialize()
3991 {
3992         int i, code;
3993         struct berval debugbv = BER_BVC("pcache");
3994
3995         code = slap_loglevel_get( &debugbv, &pcache_debug );
3996         if ( code ) {
3997                 return code;
3998         }
3999
4000 #ifdef PCACHE_CONTROL_PRIVDB
4001         code = register_supported_control( PCACHE_CONTROL_PRIVDB,
4002                 SLAP_CTRL_BIND|SLAP_CTRL_ACCESS|SLAP_CTRL_HIDE, extops,
4003                 parse_privdb_ctrl, &privDB_cid );
4004         if ( code != LDAP_SUCCESS ) {
4005                 Debug( LDAP_DEBUG_ANY,
4006                         "pcache_initialize: failed to register control %s (%d)\n",
4007                         PCACHE_CONTROL_PRIVDB, code, 0 );
4008                 return code;
4009         }
4010 #endif /* PCACHE_CONTROL_PRIVDB */
4011
4012 #ifdef PCACHE_EXOP_QUERY_DELETE
4013         code = load_extop2( (struct berval *)&pcache_exop_QUERY_DELETE,
4014                 SLAP_EXOP_WRITES|SLAP_EXOP_HIDE, pcache_exop_query_delete,
4015                 0 );
4016         if ( code != LDAP_SUCCESS ) {
4017                 Debug( LDAP_DEBUG_ANY,
4018                         "pcache_initialize: unable to register queryDelete exop: %d.\n",
4019                         code, 0, 0 );
4020                 return code;
4021         }
4022 #endif /* PCACHE_EXOP_QUERY_DELETE */
4023
4024         for ( i = 0; as[i].desc != NULL; i++ ) {
4025                 code = register_at( as[i].desc, as[i].adp, 0 );
4026                 if ( code ) {
4027                         Debug( LDAP_DEBUG_ANY,
4028                                 "pcache_initialize: register_at #%d failed\n", i, 0, 0 );
4029                         return code;
4030                 }
4031                 (*as[i].adp)->ad_type->sat_flags |= SLAP_AT_HIDE;
4032         }
4033
4034         pcache.on_bi.bi_type = "pcache";
4035         pcache.on_bi.bi_obsolete_names = obsolete_names;
4036         pcache.on_bi.bi_db_init = pcache_db_init;
4037         pcache.on_bi.bi_db_config = pcache_db_config;
4038         pcache.on_bi.bi_db_open = pcache_db_open;
4039         pcache.on_bi.bi_db_close = pcache_db_close;
4040         pcache.on_bi.bi_db_destroy = pcache_db_destroy;
4041
4042         pcache.on_bi.bi_op_search = pcache_op_search;
4043 #ifdef PCACHE_CONTROL_PRIVDB
4044         pcache.on_bi.bi_op_bind = pcache_op_privdb;
4045         pcache.on_bi.bi_op_compare = pcache_op_privdb;
4046         pcache.on_bi.bi_op_modrdn = pcache_op_privdb;
4047         pcache.on_bi.bi_op_modify = pcache_op_privdb;
4048         pcache.on_bi.bi_op_add = pcache_op_privdb;
4049         pcache.on_bi.bi_op_delete = pcache_op_privdb;
4050 #endif /* PCACHE_CONTROL_PRIVDB */
4051 #ifdef PCACHE_EXOP_QUERY_DELETE
4052         pcache.on_bi.bi_extended = pcache_op_extended;
4053 #elif defined( PCACHE_CONTROL_PRIVDB )
4054         pcache.on_bi.bi_extended = pcache_op_privdb;
4055 #endif
4056
4057         pcache.on_bi.bi_chk_controls = pcache_chk_controls;
4058
4059         pcache.on_bi.bi_cf_ocs = pcocs;
4060
4061         code = config_register_schema( pccfg, pcocs );
4062         if ( code ) return code;
4063
4064         return overlay_register( &pcache );
4065 }
4066
4067 #if SLAPD_OVER_PROXYCACHE == SLAPD_MOD_DYNAMIC
4068 int init_module(int argc, char *argv[]) {
4069         return pcache_initialize();
4070 }
4071 #endif
4072
4073 #endif  /* defined(SLAPD_OVER_PROXYCACHE) */