389-ds-base/ldap/servers/plugins/cos/cos_cache.c

/** BEGIN COPYRIGHT BLOCK
 * Copyright (C) 2001 Sun Microsystems, Inc. Used by permission.
 * Copyright (C) 2005 Red Hat, Inc.
 * All rights reserved.
 *
 * License: GPL (version 3 or any later version).
 * See LICENSE for details.
 * END COPYRIGHT BLOCK **/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

/*
    The cos cache keeps in memory all of
    the data related to cos.  This allows
    very fast lookups at the expense of RAM.
    All meta data is indexed, allowing fast
    binary search lookups.
    The cache is not dynamic, in the sense
    that it does not iteratively modify
    itself as changes are made to the cos
    meta-data.  Rather, it is designed to
    be fast to read, with non-locking
    multiple thread access to the cache,
    at the expense of modification speed.
    This means that when changes do occur,
    the cache must be rebuilt from scratch.
    However, this is achieved in such a way,
    so as to allow cache queries during the
    building of the new cache - so once a
    cache has been built, there is no down
    time.
    Of course, the configuration of the cos meta
    data is likely to be a thing which does not
    happen often.  Any other use, is probably a
    mis-use of the mechanism, and certainly will
    suffer from performance problems.
*/

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#include "portable.h"
#include "slapi-plugin.h"

/* this is naughty, but the api for backend state change is currently here */
#include "slapi-private.h"

/* include NSPR header files */
#include "prthread.h"
#include "prlock.h"
#include "prerror.h"
#include "prcvar.h"
#include "prio.h"
#include "vattr_spi.h"

#include "cos_cache.h"

#include "views.h"
static void **views_api;

/*** secret functions and structs in slapd ***/

/*
    these are required here because they are not available
    in any public header.  They must exactly match their
    counterparts in the server or they will fail to work
    correctly.
*/

/*** from slap.h ***/

struct objclass
{
    char *oc_name;     /* NAME */
    char *oc_desc;     /* DESC */
    char *oc_oid;      /* object identifier */
    char *oc_superior; /* SUP -- XXXmcs: should be an array */
    PRUint8 oc_kind;   /* ABSTRACT/STRUCTURAL/AUXILIARY */
    PRUint8 oc_flags;  /* misc. flags, e.g., OBSOLETE */
    char **oc_required;
    char **oc_allowed;
    char **oc_orig_required; /* MUST */
    char **oc_orig_allowed;  /* MAY */
    char **oc_origin;        /* X-ORIGIN extension */
    struct objclass *oc_next;
};

/*** from proto-slap.h ***/

int config_get_schemacheck(void);
void oc_lock_read(void);
void oc_unlock(void);
struct objclass *g_get_global_oc_nolock(void);
int slapd_log_error_proc(int sev_level, char *subsystem, char *fmt, ...);

/* defined in cos.c */
void *cos_get_plugin_identity(void);

/*** end secrets ***/

#define COS_PLUGIN_SUBSYSTEM "cos-plugin" /* used for logging */

#define COSTYPE_BADTYPE 0
#define COSTYPE_CLASSIC 1
#define COSTYPE_POINTER 2
#define COSTYPE_INDIRECT 3
#define COS_DEF_ERROR_NO_TEMPLATES -2

/* the global plugin handle */
static volatile vattr_sp_handle *vattr_handle = NULL;

/* both variables are protected by change_lock */
static int cos_cache_notify_flag = 0;
static PRBool cos_cache_at_work = PR_FALSE;

/* service definition cache structs */

/*    cosIndexedLinkedList: provides an object oriented type interface to
    link lists where each element contains an index for the entire
    list.  All structures that contain this one must specify this one
    as the first member otherwise the supporting functions will not work.

    {PARPAR} The indexing ability is not currently used since the
    fastest lookup is achieved via a cache level index of all attributes,
    however this mechanism may prove useful in the future
*/
struct _cosIndexedLinkedList
{
    void *pNext;
    void **index;
};
typedef struct _cosIndexedLinkedList cosIndexedLinkedList;

struct _cosAttrValue
{
    cosIndexedLinkedList list;
    char *val;
};
typedef struct _cosAttrValue cosAttrValue;

struct _cosAttribute
{
    cosIndexedLinkedList list;
    char *pAttrName;
    cosAttrValue *pAttrValue;
    cosAttrValue *pObjectclasses;
    int attr_override;
    int attr_operational;
    int attr_operational_default;
    int attr_cos_merge;
    void *pParent;
};
typedef struct _cosAttribute cosAttributes;

struct _cosTemplate
{
    cosIndexedLinkedList list;
    cosAttrValue *pDn;
    cosAttrValue *pObjectclasses;
    cosAttributes *pAttrs;
    char *cosGrade;
    int template_default;
    void *pParent;
    unsigned long cosPriority;
};

typedef struct _cosTemplate cosTemplates;

struct _cosDefinition
{
    cosIndexedLinkedList list;
    int cosType;
    cosAttrValue *pDn;
    cosAttrValue *pCosTargetTree;
    cosAttrValue *pCosTemplateDn;
    cosAttrValue *pCosSpecifier;
    cosAttrValue *pCosAttrs;
    cosAttrValue *pCosOverrides;
    cosAttrValue *pCosOperational;
    cosAttrValue *pCosOpDefault;
    cosAttrValue *pCosMerge;
    cosTemplates *pCosTmps;
};
typedef struct _cosDefinition cosDefinitions;

struct _cos_cache
{
    cosDefinitions *pDefs;
    cosAttributes **ppAttrIndex;
    int attrCount;
    char **ppTemplateList;
    int templateCount;
    int refCount;
    int vattr_cacheable;
};
typedef struct _cos_cache cosCache;

/* cache manipulation function prototypes*/
static cosCache *pCache; /* always the current global cache, only use getref to get */

/* the place to start if you want a new cache */
static int cos_cache_create_unlock(void);
static int cos_cache_creation_lock(void);

/* cache index related functions */
static int cos_cache_index_all(cosCache *pCache);
static int cos_cache_attr_compare(const void *e1, const void *e2);
static int cos_cache_template_index_compare(const void *e1, const void *e2);
static int cos_cache_string_compare(const void *e1, const void *e2);
static int cos_cache_template_index_bsearch(const char *dn);
static int cos_cache_attr_index_bsearch(const cosCache *pCache, const cosAttributes *key, int lower, int upper);

/* the multi purpose list creation function, pass it something and it links it */
static void cos_cache_add_ll_entry(void **attrval, void *theVal, int (*compare)(const void *elem1, const void *elem2));

/* cosAttrValue manipulation */
static int cos_cache_add_attrval(cosAttrValue **attrval, char *val);
static void cos_cache_del_attrval_list(cosAttrValue **pVal);
static int cos_cache_attrval_exists(cosAttrValue *pAttrs, const char *val);

/* cosAttributes manipulation */
static int cos_cache_add_attr(cosAttributes **pAttrs, char *name, cosAttrValue *val);
static void cos_cache_del_attr_list(cosAttributes **pAttrs);
static int cos_cache_find_attr(cosCache *pCache, char *type);
static int cos_cache_total_attr_count(cosCache *pCache);
static int cos_cache_cos_2_slapi_valueset(cosAttributes *pAttr, Slapi_ValueSet **out_vs);
static int cos_cache_cmp_attr(cosAttributes *pAttr, Slapi_Value *test_this, int *result);

/* cosTemplates manipulation */
static int cos_cache_add_dn_tmpls(char *dn, cosAttrValue *pCosSpecifier, cosAttrValue *pAttrs, cosTemplates **pTmpls);
static int cos_cache_add_tmpl(cosTemplates **pTemplates, cosAttrValue *dn, cosAttrValue *objclasses, cosAttrValue *pCosSpecifier, cosAttributes *pAttrs, cosAttrValue *cosPriority);

/* cosDefinitions manipulation */
static int cos_cache_build_definition_list(cosDefinitions **pDefs, int *vattr_cacheable);
static int cos_cache_add_dn_defs(char *dn, cosDefinitions **pDefs);
static int cos_cache_add_defn(cosDefinitions **pDefs, cosAttrValue **dn, int cosType, cosAttrValue **tree, cosAttrValue **tmpDn, cosAttrValue **spec, cosAttrValue **pAttrs, cosAttrValue **pOverrides, cosAttrValue **pOperational, cosAttrValue **pCosMerge, cosAttrValue **pCosOpDefault);
static int cos_cache_entry_is_cos_related(Slapi_Entry *e);

/* schema checking */
static int cos_cache_schema_check(cosCache *pCache, int cache_attr_index, Slapi_Attr *pObjclasses);
static int cos_cache_schema_build(cosCache *pCache);
static void cos_cache_del_schema(cosCache *pCache);

/* special cos scheme implimentations (special = other than cos classic) */
static int cos_cache_follow_pointer(vattr_context *context, const char *dn, char *type, Slapi_ValueSet **out_vs, Slapi_Value *test_this, int *result, int flags);


/* this dude is the thread function which performs dynamic config of the cache */
static void cos_cache_wait_on_change(void *arg);

/* this gets called when a backend changes state */
void cos_cache_backend_state_change(void *handle, char *be_name, int old_be_state, int new_be_state);

/* operation callbacks for vattr service */
static int cos_cache_vattr_get(vattr_sp_handle *handle, vattr_context *c, Slapi_Entry *e, char *type, Slapi_ValueSet **results, int *type_name_disposition, char **actual_type_name, int flags, int *free_flags, void *hint);
static int cos_cache_vattr_compare(vattr_sp_handle *handle, vattr_context *c, Slapi_Entry *e, char *type, Slapi_Value *test_this, int *result, int flags, void *hint);
static int cos_cache_vattr_types(vattr_sp_handle *handle, Slapi_Entry *e, vattr_type_list_context *type_context, int flags);
static int cos_cache_query_attr(cos_cache *ptheCache, vattr_context *context, Slapi_Entry *e, char *type, Slapi_ValueSet **out_attr, Slapi_Value *test_this, int *result, int *ops, int *indirect_cos);

/*
    compares s2 to s1 starting from end of string until the beginning of either
    matches result in the s2 value being clipped from s1 with a NULL char
    and 1 being returned as opposed to 0
*/
static int cos_cache_backwards_stricmp_and_clip(char *s1, char *s2);

/* module level thread control stuff */

static int keeprunning = 0;
static int started = 0;

static Slapi_Mutex *cache_lock;
static Slapi_Mutex *change_lock;
static Slapi_Mutex *start_lock;
static Slapi_Mutex *stop_lock;
static Slapi_CondVar *something_changed = NULL;
static Slapi_CondVar *start_cond = NULL;


/*
    cos_cache_init
    --------------
    starts up the thread which waits for changes and
    fires off the cache re-creation when one is detected
    also registers vattr callbacks
*/
int
cos_cache_init(void)
{
    int ret = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_init\n");

    slapi_vattrcache_cache_none();
    cache_lock = slapi_new_mutex();
    change_lock = slapi_new_mutex();
    stop_lock = slapi_new_mutex();
    something_changed = slapi_new_condvar(change_lock);
    keeprunning = 1;
    start_lock = slapi_new_mutex();
    start_cond = slapi_new_condvar(start_lock);
    started = 0;

    if (stop_lock == NULL ||
        change_lock == NULL ||
        cache_lock == NULL ||
        stop_lock == NULL ||
        start_lock == NULL ||
        start_cond == NULL ||
        something_changed == NULL) {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM,
                      "cos_cache_init - Cannot create mutexes\n");
        ret = -1;
        goto out;
    }

    /* grab the views interface */
    if (slapi_apib_get_interface(Views_v1_0_GUID, &views_api)) {
        /* lets be tolerant if views is disabled */
        views_api = 0;
    }

    if (slapi_vattrspi_register((vattr_sp_handle **)&vattr_handle,
                                cos_cache_vattr_get,
                                cos_cache_vattr_compare,
                                cos_cache_vattr_types) != 0) {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM,
                      "cos_cache_init - Cannot register as service provider\n");
        ret = -1;
        goto out;
    }

    if (PR_CreateThread(PR_USER_THREAD,
                        cos_cache_wait_on_change,
                        NULL,
                        PR_PRIORITY_NORMAL,
                        PR_GLOBAL_THREAD,
                        PR_UNJOINABLE_THREAD,
                        SLAPD_DEFAULT_THREAD_STACKSIZE) == NULL) {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM,
                      "cos_cache_init - PR_CreateThread failed\n");
        ret = -1;
        goto out;
    }

    /* wait for that thread to get started */
    if (ret == 0) {
        slapi_lock_mutex(start_lock);
        while (!started) {
            while (slapi_wait_condvar(start_cond, NULL) == 0)
                ;
        }
        slapi_unlock_mutex(start_lock);
    }


out:
    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_init\n");
    return ret;
}

/*
    cos_cache_wait_on_change
    ------------------------
    sit around waiting on a notification that something has
    changed, then fires off the cache re-creation

    The way this stuff is written, we can look for the
    template for a definiton, before the template has been added--I think
    that's OK--we'll see it when it arrives--get this error message:
    "skipping cos definition cn=cosPointerGenerateSt,ou=People,o=cosAll--no templates found"

*/
static void
cos_cache_wait_on_change(void *arg __attribute__((unused)))
{
    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_wait_on_change thread\n");

    slapi_lock_mutex(stop_lock);
    slapi_lock_mutex(change_lock);

    /* first register our backend state change func (we'll use func pointer as handle) */
    slapi_register_backend_state_change((void *)cos_cache_backend_state_change, cos_cache_backend_state_change);

    pCache = 0;

    /* create initial cache */
    cos_cache_creation_lock();

    slapi_lock_mutex(start_lock);
    started = 1;
    slapi_notify_condvar(start_cond, 1);
    slapi_unlock_mutex(start_lock);

    while (keeprunning) {
        slapi_unlock_mutex(change_lock);
        slapi_lock_mutex(change_lock);
        if (!cos_cache_notify_flag && keeprunning) {
            /*
             * Nothing to do right now, so go to sleep--as
             * we have the mutex, we are sure to wait before any modify
             * thread notifies our condvar, and so we will not miss any
             * notifications, including the shutdown notification.
             */
            slapi_wait_condvar(something_changed, NULL);
        } else {
            /* Something to do...do it below */
        }
        /*
         * We're here because:
         * 1. we were asleep and got a signal, on our condvar OR
         * 2. we were about to wait on the condvar and noticed that a modfiy
         * thread
         * had passed, setting the cos_cache_notify_flag and notifying us--
         * we did not wait in that case as we would have missed the notify
         * (notify when noone is waiting == no-op).
         * before we go running off doing lots of stuff lets check if we should stop
        */
        if (keeprunning) {
            cos_cache_creation_lock();
        }
        cos_cache_notify_flag = 0; /* Dealt with it */
    }                              /* while */

    /* shut down the cache */
    slapi_unlock_mutex(change_lock);
    slapi_unlock_mutex(stop_lock);

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_wait_on_change thread exit\n");
}


/*
    cos_cache_create_unlock
    ---------------------
    Walks the definitions in the DIT and creates the cache.
    Once created, it swaps the new cache for the old one,
    releasing its refcount to the old cache and allowing it
    to be destroyed.

        called while change_lock is NOT held
*/
static int
cos_cache_create_unlock(void)
{
    int ret = -1;
    cosCache *pNewCache;
    static int firstTime = 1;
    int cache_built = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_create_unlock\n");

    pNewCache = (cosCache *)slapi_ch_malloc(sizeof(cosCache));
    if (pNewCache) {
        pNewCache->pDefs = 0;
        pNewCache->refCount = 1;        /* 1 is for us */
        pNewCache->vattr_cacheable = 0; /* default is not cacheable */

        ret = cos_cache_build_definition_list(&(pNewCache->pDefs), &(pNewCache->vattr_cacheable));
        if (!ret) {
            /* OK, we have a cache, lets add indexing for
            that faster than slow feeling */

            ret = cos_cache_index_all(pNewCache);
            if (ret == 0) {
                /* right, indexed cache, lets do our duty for the schema */

                ret = cos_cache_schema_build(pNewCache);
                if (ret == 0) {
                    /* now to swap the new cache for the old cache */
                    cosCache *pOldCache;

                    slapi_lock_mutex(cache_lock);

                    /* turn off caching until the old cache is done */
                    if (pCache) {
                        slapi_vattrcache_cache_none();

                        /*
                         * be sure not to uncache other stuff
                         * like roles if there is no change in
                         * state
                         */
                        if (pCache->vattr_cacheable)
                            slapi_entrycache_vattrcache_watermark_invalidate();
                    } else {
                        if (pNewCache && pNewCache->vattr_cacheable) {
                            slapi_vattrcache_cache_all();
                        }
                    }

                    pOldCache = pCache;
                    pCache = pNewCache;

                    slapi_unlock_mutex(cache_lock);

                    if (pOldCache)
                        cos_cache_release(pOldCache);

                    cache_built = 1;
                } else {
                    /* we should not go on without proper schema checking */
                    cos_cache_release(pNewCache);
                    slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_create_unlock - Failed to cache the schema\n");
                }
            } else {
                /* currently we cannot go on without the indexes */
                cos_cache_release(pNewCache);
                slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_create_unlock - Failed to index cache\n");
            }
        } else {
            if (firstTime) {
                slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_create_unlock - cos disabled\n");
                firstTime = 0;
            }

            slapi_ch_free((void **)&pNewCache);
        }
    } else
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_create_unlock - Memory allocation failure\n");


    /* make sure we have a new cache */
    if (!cache_built) {
        /* we do not have a new cache, must make sure the old cache is destroyed */

        cosCache *pOldCache;

        slapi_lock_mutex(cache_lock);

        slapi_vattrcache_cache_none();

        /*
         * be sure not to uncache other stuff
         * like roles if there is no change in
         * state
         */
        if (pCache && pCache->vattr_cacheable)
            slapi_entrycache_vattrcache_watermark_invalidate();

        pOldCache = pCache;
        pCache = NULL;

        slapi_unlock_mutex(cache_lock);

        if (pOldCache)
            cos_cache_release(pOldCache); /* release our reference to the old cache */
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_create_unlock\n");
    return ret;
}

/* cos_cache_creation_lock is called with change_lock being hold:
 *    slapi_lock_mutex(change_lock)
 *
 * To rebuild the cache cos_cache_creation gets cos definitions from backend, that
 * means change_lock is held then cos_cache_creation will acquire some backend pages.
 *
 * A deadlock can happen if cos_post_op is called while backend is locked.
 * For example if a bepreop (urp) does an internal update on a cos definition,
 * the thread holds backend pages that will be needed by cos_cache_creation.
 *
 * A solution is to use a flag 'cos_cache_at_work' protected by change_lock,
 * release change_lock, recreate the cos_cache, acquire change_lock reset the flag.
 *
 * returned value: result of cos_cache_create_unlock
 *
 */
static int
cos_cache_creation_lock(void)
{
    int ret = -1;
    int max_tries = 10;

    for (; max_tries != 0; max_tries--) {
        /* if the cos_cache is already under work (cos_cache_create_unlock)
         * wait 1 second
         */
        if (cos_cache_at_work) {
            slapi_log_err(SLAPI_LOG_FATAL, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_creation_lock already rebuilding cos_cache... retry\n");
            DS_Sleep(PR_MillisecondsToInterval(1000));
            continue;
        }
        cos_cache_at_work = PR_TRUE;
        slapi_unlock_mutex(change_lock);
        ret = cos_cache_create_unlock();
        slapi_lock_mutex(change_lock);
        cos_cache_at_work = PR_FALSE;
        break;
    }
    if (!max_tries) {
        slapi_log_err(SLAPI_LOG_FATAL, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_creation_lock  rebuilt was to long, skip this rebuild\n");
    }

    return ret;
}

/*
    cos_cache_build_definition_list
    -------------------------------
    builds the list of cos definitions by searching for them throughout the DIT
*/
static int
cos_cache_build_definition_list(cosDefinitions **pDefs, int *vattr_cacheable)
{
    int ret = 0;
    Slapi_PBlock *pSuffixSearch = 0;
    Slapi_Entry **pSuffixList = 0;
    Slapi_Attr *suffixAttr;
    struct berval **suffixVals;
    char *attrType = 0;
    char *attrs[2];
    int suffixIndex = 0;
    int valIndex = 0;
    int cos_def_available = 0;
    static int firstTime = 1;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_build_definition_list\n");

    /*
     * The class of service definitions may be anywhere in the DIT,
     * so our first task is to find them.
     */

    attrs[0] = "namingcontexts";
    attrs[1] = 0;

    slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_build_definition_list - "
                                                          "Building class of service cache after status change.\n");

    /*
     * XXXrbyrne: this looks really inefficient--should be using
     * slapi_get_next_suffix(), rather than searching for namingcontexts.
     */

    pSuffixSearch = slapi_search_internal("", LDAP_SCOPE_BASE, "(objectclass=*)", NULL, attrs, 0);
    if (pSuffixSearch)
        slapi_pblock_get(pSuffixSearch, SLAPI_PLUGIN_INTOP_RESULT, &ret);

    if (!pSuffixSearch || ret != LDAP_SUCCESS) {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM,
                      "cos_cache_build_definition_list - Failed to find suffixes\n");
        ret = -1;
        goto next;
    }

    /* iterate through the suffixes and search for cos definitions */
    slapi_pblock_get(pSuffixSearch, SLAPI_PLUGIN_INTOP_SEARCH_ENTRIES,
                     &pSuffixList);
    if (!pSuffixList) {
        goto next;
    }
    while (pSuffixList[suffixIndex]) {
        if (!slapi_entry_first_attr(pSuffixList[suffixIndex], &suffixAttr)) {
            do {
                attrType = 0;
                slapi_attr_get_type(suffixAttr, &attrType);
                if (attrType && !slapi_utf8casecmp((unsigned char *)attrType, (unsigned char *)"namingcontexts")) {
                    if (!slapi_attr_get_bervals_copy(suffixAttr, &suffixVals)) {
                        valIndex = 0;

                        if (suffixVals) {
                            while (suffixVals[valIndex]) {
                                /* here's a suffix, lets search it... */
                                if (suffixVals[valIndex]->bv_val) {
                                    if (!cos_cache_add_dn_defs(suffixVals[valIndex]->bv_val, pDefs)) {
                                        *vattr_cacheable = -1;
                                        cos_def_available = 1;
                                    }
                                }
                                valIndex++;
                            }
                            ber_bvecfree(suffixVals);
                            suffixVals = NULL;
                        }
                    }
                }
            } while (!slapi_entry_next_attr(pSuffixList[suffixIndex], suffixAttr, &suffixAttr));
        }
        suffixIndex++;
    }
next:
    if (cos_def_available == 0) {
        if (firstTime) {
            slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_build_definition_list - "
                                                                  "Found no cos definitions, cos disabled while waiting for updates\n");
            firstTime = 0;
        }

        ret = -1;
    } else
        slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_build_definition_list - "
                                                              "Class of service cache built.\n");

    /* clean up */
    if (pSuffixSearch) {
        slapi_free_search_results_internal(pSuffixSearch);
        slapi_pblock_destroy(pSuffixSearch);
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_build_definition_list\n");
    return ret;
}


/* struct to support search callback API */
struct dn_defs_info
{
    cosDefinitions **pDefs;
    int vattr_cacheable;
    int ret;
};

/*
 * Currently, always returns 0 to continue the search for definitions, even
 * if a particular attempt to add a definition fails: info.ret gets set to
 * zero only if we succeed to add a def.
*/
static int
cos_dn_defs_cb(Slapi_Entry *e, void *callback_data)
{
    struct dn_defs_info *info;
    cosAttrValue **pSneakyVal = 0;
    cosAttrValue *pObjectclass = 0;
    cosAttrValue *pCosTargetTree = 0;
    cosAttrValue *pCosTemplateDn = 0;
    cosAttrValue *pCosSpecifier = 0;
    cosAttrValue *pCosAttribute = 0;
    cosAttrValue *pCosOverrides = 0;
    cosAttrValue *pCosOperational = 0;
    cosAttrValue *pCosOpDefault = 0;
    cosAttrValue *pCosMerge = 0;
    cosAttrValue *pDn = 0;
    struct berval **dnVals;
    int cosType = 0;
    int valIndex = 0;
    Slapi_Attr *dnAttr;
    char *attrType = 0;
    char *norm_dn = NULL;
    info = (struct dn_defs_info *)callback_data;

    cos_cache_add_attrval(&pDn, slapi_entry_get_dn(e));
    if (slapi_entry_first_attr(e, &dnAttr)) {
        goto bail;
    }

    do {
        attrType = 0;
        /* we need to fill in the details of the definition now */
        slapi_attr_get_type(dnAttr, &attrType);
        if (!attrType) {
            continue;
        }
        pSneakyVal = 0;
        if (!slapi_utf8casecmp((unsigned char *)attrType, (unsigned char *)"objectclass"))
            pSneakyVal = &pObjectclass;
        else if (!slapi_utf8casecmp((unsigned char *)attrType, (unsigned char *)"cosTargetTree")) {
            if (pCosTargetTree) {
                norm_dn = slapi_create_dn_string("%s", pCosTargetTree->val);
                if (norm_dn) {
                    slapi_ch_free_string(&pCosTargetTree->val);
                    pCosTargetTree->val = norm_dn;
                }
            }
            pSneakyVal = &pCosTargetTree;
        } else if (!slapi_utf8casecmp((unsigned char *)attrType, (unsigned char *)"cosTemplateDn"))
            pSneakyVal = &pCosTemplateDn;
        else if (!slapi_utf8casecmp((unsigned char *)attrType, (unsigned char *)"cosSpecifier"))
            pSneakyVal = &pCosSpecifier;
        else if (!slapi_utf8casecmp((unsigned char *)attrType, (unsigned char *)"cosAttribute"))
            pSneakyVal = &pCosAttribute;
        else if (!slapi_utf8casecmp((unsigned char *)attrType, (unsigned char *)"cosIndirectSpecifier"))
            pSneakyVal = &pCosSpecifier;
        if (!pSneakyVal) {
            continue;
        }
        /* It's a type we're interested in */
        if (slapi_attr_get_bervals_copy(dnAttr, &dnVals)) {
            continue;
        }
        valIndex = 0;
        if (!dnVals) {
            continue;
        }
        for (valIndex = 0; dnVals[valIndex]; valIndex++) {
            if (!dnVals[valIndex]->bv_val) {
                continue;
            }
            /*
            parse any overide or default values
            and deal with them
            */
            if (pSneakyVal == &pCosAttribute) {
                int qualifier_hit = 0;
                int op_qualifier_hit = 0;
                int merge_schemes_qualifier_hit = 0;
                int override_qualifier_hit = 0;
                int default_qualifier_hit = 0;
                int operational_default_qualifier_hit = 0;
                do {
                    qualifier_hit = 0;

                    if (cos_cache_backwards_stricmp_and_clip(dnVals[valIndex]->bv_val, " operational")) {
                        /* matched */
                        op_qualifier_hit = 1;
                        qualifier_hit = 1;
                    }

                    if (cos_cache_backwards_stricmp_and_clip(dnVals[valIndex]->bv_val, " merge-schemes")) {
                        /* matched */
                        merge_schemes_qualifier_hit = 1;
                        qualifier_hit = 1;
                    }

                    if (cos_cache_backwards_stricmp_and_clip(dnVals[valIndex]->bv_val, " override")) {
                        /* matched */
                        override_qualifier_hit = 1;
                        qualifier_hit = 1;
                    }

                    if (cos_cache_backwards_stricmp_and_clip(dnVals[valIndex]->bv_val, " default")) {
                        default_qualifier_hit = 1;
                        qualifier_hit = 1;
                    }

                    if (cos_cache_backwards_stricmp_and_clip(dnVals[valIndex]->bv_val, " operational-default")) {
                        operational_default_qualifier_hit = 1;
                        qualifier_hit = 1;
                    }
                } while (qualifier_hit == 1);

                /*
                * At this point, dnVals[valIndex]->bv_val
                * is the value of cosAttribute, stripped of
                * any qualifiers, so add this pure attribute type to
                * the appropriate lists.
                */

                if (op_qualifier_hit) {
                    cos_cache_add_attrval(&pCosOperational,
                                          dnVals[valIndex]->bv_val);
                }
                if (merge_schemes_qualifier_hit) {
                    cos_cache_add_attrval(&pCosMerge, dnVals[valIndex]->bv_val);
                }
                if (override_qualifier_hit) {
                    cos_cache_add_attrval(&pCosOverrides,
                                          dnVals[valIndex]->bv_val);
                }
                if (default_qualifier_hit) {
                    /* attr is added below in pSneakyVal, in any case */
                }

                if (operational_default_qualifier_hit) {
                    cos_cache_add_attrval(&pCosOpDefault,
                                          dnVals[valIndex]->bv_val);
                }

                slapi_vattrspi_regattr((vattr_sp_handle *)vattr_handle,
                                       dnVals[valIndex]->bv_val, NULL, NULL);
            } /* if(attrType is cosAttribute) */

            /*
             * Add the attributetype to the appropriate
             * list.
             */
            cos_cache_add_attrval(pSneakyVal, dnVals[valIndex]->bv_val);

        } /* for (valIndex = 0; dnVals[valIndex]; valIndex++) */

        ber_bvecfree(dnVals);
        dnVals = NULL;
    } while (!slapi_entry_next_attr(e, dnAttr, &dnAttr));

    if (pCosAttribute && (!pCosTargetTree || !pCosTemplateDn)) {
        /* get the parent of the definition */
        char *orig = slapi_dn_parent(pDn->val);
        char *parent = NULL;
        if (orig) {
            parent = slapi_create_dn_string("%s", orig);
            if (!parent) {
                parent = orig;
                slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM,
                              "cos_dn_defs_cb - "
                              "Failed to normalize parent dn %s. "
                              "Adding the pre normalized dn.\n",
                              parent);
            }
            if (!pCosTargetTree) {
                cos_cache_add_attrval(&pCosTargetTree, parent);
            }
            if (!pCosTemplateDn) {
                cos_cache_add_attrval(&pCosTemplateDn, parent);
            }
            if (parent != orig) {
                slapi_ch_free_string(&parent);
            }
            slapi_ch_free_string(&orig);
        } else {
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM,
                          "cos_dn_defs_cb - "
                          "Failed to get parent dn of cos definition %s.\n",
                          pDn->val);
            if (!pCosTemplateDn) {
                if (!pCosTargetTree) {
                    slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_dn_defs_cb - cosTargetTree and cosTemplateDn are not set.\n");
                } else {
                    slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_dn_defs_cb - cosTemplateDn is not set.\n");
                }
            } else if (!pCosTargetTree) {
                slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_dn_defs_cb - cosTargetTree is not set.\n");
            }
        }
    }

    /*
    determine the type of class of service scheme
    */

    if (pObjectclass) {
        if (cos_cache_attrval_exists(pObjectclass, "cosDefinition")) {
            cosType = COSTYPE_CLASSIC;
        } else if (cos_cache_attrval_exists(pObjectclass, "cosClassicDefinition")) {
            cosType = COSTYPE_CLASSIC;

        } else if (cos_cache_attrval_exists(pObjectclass, "cosPointerDefinition")) {
            cosType = COSTYPE_POINTER;

        } else if (cos_cache_attrval_exists(pObjectclass, "cosIndirectDefinition")) {
            cosType = COSTYPE_INDIRECT;

        } else
            cosType = COSTYPE_BADTYPE;
    }

    /*
    we should now have a full definition,
    do some sanity checks because we don't
    want bogus entries in the cache
    then ship it
    */

    /* these must exist */
    if (pDn && pObjectclass &&
        ((cosType == COSTYPE_CLASSIC &&
          pCosTemplateDn &&
          pCosSpecifier &&
          pCosAttribute) ||
         (cosType == COSTYPE_POINTER &&
          pCosTemplateDn &&
          pCosAttribute) ||
         (cosType == COSTYPE_INDIRECT &&
          pCosSpecifier &&
          pCosAttribute))) {
        int rc = 0;
        /*
    we'll leave the referential integrity stuff
    up to the referint plug-in and assume all
    is good - if it's not then we just have a
    useless definition and we'll nag copiously later.
        */
        char *pTmpDn = slapi_ch_strdup(pDn->val); /* because dn gets hosed on error */

        if (!(rc = cos_cache_add_defn(info->pDefs, &pDn, cosType,
                                      &pCosTargetTree, &pCosTemplateDn,
                                      &pCosSpecifier, &pCosAttribute,
                                      &pCosOverrides, &pCosOperational,
                                      &pCosMerge, &pCosOpDefault))) {
            info->ret = 0; /* we have succeeded to add the defn*/
        } else {
            /*
             * Failed but we will continue the search for other defs
             * Don't reset info->ret....it keeps track of any success
            */
            if (rc == COS_DEF_ERROR_NO_TEMPLATES) {
                slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_dn_defs_cb - Skipping CoS Definition %s"
                                                                   "--no CoS Templates found, which should be added before the CoS Definition.\n",
                              pTmpDn);
            } else {
                slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_dn_defs_cb - Skipping CoS Definition %s\n"
                                                                   "--error(%d)\n",
                              pTmpDn, rc);
            }
        }

        slapi_ch_free_string(&pTmpDn);
    } else {
        /*
    this definition is brain dead - bail
    if we have a dn use it to report, if not then *really* bad
    things are going on
        */
        if (pDn) {
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_dn_defs_cb - "
                                                               "Incomplete cos definition detected in %s, discarding from cache.\n",
                          pDn->val);
        } else
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_dn_defs_cb - "
                                                               "Incomplete cos definition detected, no DN to report, discarding from cache.\n");

        if (pCosTargetTree)
            cos_cache_del_attrval_list(&pCosTargetTree);
        if (pCosTemplateDn)
            cos_cache_del_attrval_list(&pCosTemplateDn);
        if (pCosSpecifier)
            cos_cache_del_attrval_list(&pCosSpecifier);
        if (pCosAttribute)
            cos_cache_del_attrval_list(&pCosAttribute);
        if (pDn)
            cos_cache_del_attrval_list(&pDn);
    }
bail:
    /* we don't keep the objectclasses, so lets free them */
    if (pObjectclass) {
        cos_cache_del_attrval_list(&pObjectclass);
    }
    /* This particular definition may not have yielded anything
     * worth caching (eg. no template was found for it) but
     * that should not cause us to abort the search for other more well behaved
     * definitions unless we are shutting down.
     * return info->ret;
     */
    return slapi_is_shutting_down();
}

/*
    cos_cache_add_dn_defs
    -------------------------
    takes a dn as argument and searches the dn for cos definitions,
    adding any found to the definition list. Change to use search callback API.

    Returns: 0: found at least one definition entry that got added to the
        cache successfully.
             non-zero: added no cos defs to the cache.
*/

#define DN_DEF_FILTER "(&(|(objectclass=cosSuperDefinition)(objectclass=cosDefinition))(objectclass=ldapsubentry))"

static int
cos_cache_add_dn_defs(char *dn, cosDefinitions **pDefs)
{
    Slapi_PBlock *pDnSearch = 0;
    struct dn_defs_info info = {NULL, 0, 0};
    pDnSearch = slapi_pblock_new();
    if (pDnSearch) {
        info.ret = -1; /* assume no good defs */
        info.pDefs = pDefs;
        slapi_search_internal_set_pb(pDnSearch, dn, LDAP_SCOPE_SUBTREE,
                                     DN_DEF_FILTER, NULL, 0,
                                     NULL, NULL, cos_get_plugin_identity(), 0);
        slapi_search_internal_callback_pb(pDnSearch,
                                          &info /* callback_data */,
                                          NULL /* result_callback */,
                                          cos_dn_defs_cb,
                                          NULL /* referral_callback */);
        slapi_pblock_destroy(pDnSearch);
    }

    return info.ret;
}


/* struct to support call back API */

struct tmpl_info
{
    cosAttrValue *pCosSpecifier;
    cosAttrValue *pAttrs;
    cosTemplates **pTmpls;
    int ret;
};


/*
 * Currently, always returns 0 to continue the search for templates, even
 * if a particular attempt to add a template fails: info.ret gets set to
 * zero only if we succeed to add at least one tmpl.
*/
static int
cos_dn_tmpl_entries_cb(Slapi_Entry *e, void *callback_data)
{
    cosAttrValue *pDn = 0;
    cosAttrValue *pCosPriority = 0;
    cosAttributes *pAttributes = 0;
    cosAttrValue *pObjectclass = 0;
    cosAttrValue *pCosAttribute = 0;
    Slapi_Attr *dnAttr;
    struct berval **dnVals;
    int itsAnAttr = 0;
    int valIndex = 0;
    cosAttrValue **pSneakyVal = 0;
    char *attrType = 0;
    struct tmpl_info *info;
    info = (struct tmpl_info *)callback_data;

    pDn = 0;
    cos_cache_add_attrval(&pDn, slapi_entry_get_dn(e));
    pAttributes = 0;
    pObjectclass = 0;
    pCosPriority = 0;

    if (!slapi_entry_first_attr(e, &dnAttr)) {
        int attrs_present = 0;

        do {
            attrType = 0;
            pCosAttribute = 0;

            /* we need to fill in the details of the template now */
            slapi_attr_get_type(dnAttr, &attrType);

            if (attrType) {
                itsAnAttr = 0;
                pSneakyVal = 0;

                if (!slapi_utf8casecmp((unsigned char *)attrType,
                                       (unsigned char *)"objectclass"))
                    pSneakyVal = &pObjectclass;

                if (!slapi_utf8casecmp((unsigned char *)attrType,
                                       (unsigned char *)"cosPriority"))
                    pSneakyVal = &pCosPriority;

                if (pSneakyVal == NULL) {
                    /* look for the attribute in the dynamic attributes */
                    if (cos_cache_attrval_exists(info->pAttrs, attrType)) {
                        pSneakyVal = &pCosAttribute;
                        itsAnAttr = 1;
                        attrs_present = 1;
                    }
                }

                if (pSneakyVal) {
                    if (!slapi_attr_get_bervals_copy(dnAttr, &dnVals)) {
                        valIndex = 0;

                        if (dnVals) {
                            while (dnVals[valIndex]) {
                                if (dnVals[valIndex]->bv_val)
                                    cos_cache_add_attrval(pSneakyVal,
                                                          dnVals[valIndex]->bv_val);

                                valIndex++;
                            }

                            if (itsAnAttr) {
                                /* got all vals, add this attribute to the attribute list */
                                cos_cache_add_attr(&pAttributes, attrType,
                                                   *pSneakyVal);
                            }

                            ber_bvecfree(dnVals);
                            dnVals = NULL;
                        }
                    }
                }
            }

        } while (!slapi_entry_next_attr(e, dnAttr, &dnAttr));

        /*
        we should now have a full template,
        do some sanity checks because we don't
        want bogus entries in the cache if we can help it
        - then ship it
        */

        /* these must exist */
        if (
            attrs_present &&
            pObjectclass &&
            pAttributes &&
            pDn) {
            /*
        we'll leave the referential integrity stuff
        up to the referint plug-in if set up and assume all
        is good - if it's not then we just have a
        useless definition and we'll nag copiously later.
            */

            if (!cos_cache_add_tmpl(info->pTmpls, pDn, pObjectclass,
                                    info->pCosSpecifier, pAttributes, pCosPriority)) {
                info->ret = 0; /* we have succeed to add the tmpl */
            } else {
                /* Don't reset info->ret....it keeps track of any success */
                slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_dn_tmpl_entries_cb - "
                                                                   "Could not cache cos template %s\n",
                              pDn->val);
            }
        } else {
            /*
        this template is brain dead - bail
        if we have a dn use it to report, if not then *really* bad
        things are going on
        - of course it might not be a template, so lets
        not tell the world unless the world wants to know,
        we'll make it a plugin level message
            */
            if (pDn) {
                slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_dn_tmpls - "
                                                                      "Incomplete cos template detected in %s, discarding from cache.\n",
                              pDn->val);
            } else
                slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_dn_tmpls - "
                                                                      "Incomplete cos template detected, no DN to report, discarding from cache.\n");

            if (pObjectclass)
                cos_cache_del_attrval_list(&pObjectclass);
            if (pCosAttribute)
                cos_cache_del_attrval_list(&pCosAttribute);
            if (pDn)
                cos_cache_del_attrval_list(&pDn);
            if (pAttributes)
                cos_cache_del_attr_list(&pAttributes);
            if (pCosPriority)
                cos_cache_del_attrval_list(&pCosPriority);
        }
    }
    /*
     * Always continue the search even if a particular attempt
     * to add a template failed unless we are shutting down
     */
    return slapi_is_shutting_down();
}

/*
    cos_cache_add_dn_tmpls
    -------------------------
    takes a dn as argument and searches the dn for cos templates,
    adding any found to the template list
    This is the new version using call back search API

    Returns: zero for success--found at least one good tmpl for this def.
            non-zero: failed to add any templs for this def.
*/

#define TMPL_FILTER "(&(objectclass=costemplate)(|(objectclass=costemplate)(objectclass=ldapsubentry)))"

static int
cos_cache_add_dn_tmpls(char *dn, cosAttrValue *pCosSpecifier, cosAttrValue *pAttrs, cosTemplates **pTmpls)
{
    void *plugin_id;
    int scope;
    struct tmpl_info info = {NULL, 0, 0, 0};
    Slapi_PBlock *pDnSearch = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_add_dn_tmpls\n");

    /* no cos specifier means this is an indirect scheme */
    if (pCosSpecifier)
        scope = LDAP_SCOPE_ONELEVEL;
    else
        scope = LDAP_SCOPE_BASE;

    /* Use new internal operation API */
    pDnSearch = slapi_pblock_new();
    plugin_id = cos_get_plugin_identity();
    if (pDnSearch) {
        info.pAttrs = pAttrs;
        info.pTmpls = pTmpls;
        info.pCosSpecifier = pCosSpecifier;
        info.ret = -1; /* assume no good tmpls */
        slapi_search_internal_set_pb(pDnSearch, dn, scope,
                                     TMPL_FILTER, NULL, 0,
                                     NULL, NULL, plugin_id, 0);
        slapi_search_internal_callback_pb(pDnSearch,
                                          &info /* callback_data */,
                                          NULL /* result_callback */,
                                          cos_dn_tmpl_entries_cb,
                                          NULL /* referral_callback */);
        slapi_pblock_destroy(pDnSearch);
    }
    /*
     * info.ret comes out zero only if we succeed to add at least one
     * tmpl to the cache.
    */
    return (info.ret);
}

/*
    cos_cache_add_defn
    ------------------
    Add a cos definition to the list and create the template
    cache for this definition
    returns: 0: successfully added the definition to the cache
            non-zero: failed to add the definition to the cache (eg. because
                    there was no template for it.)
                    ret==COS_DEF_ERROR_NO_TEMPLATES then no templs were found
                    for thsi def.  We make a special case of this and pass the
                    back the error so we can roll two messages into one--this
                    is to reduce the number of error messages at cos definiton
                    load time--it is common to see the defs before the tmpls
                    arrive.

*/
static int
cos_cache_add_defn(
    cosDefinitions **pDefs,
    cosAttrValue **dn,
    int cosType,
    cosAttrValue **tree,
    cosAttrValue **tmpDn,
    cosAttrValue **spec,
    cosAttrValue **pAttrs,
    cosAttrValue **pOverrides,
    cosAttrValue **pOperational,
    cosAttrValue **pCosMerge,
    cosAttrValue **pCosOpDefault)
{
    int ret = 0;
    int tmplCount = 0;
    cosDefinitions *theDef = 0;
    cosAttrValue *pTmpTmplDn = 0;
    cosAttrValue *pDummyAttrVal = 0;
    cosAttrValue *pAttrsIter = 0;
    cosAttributes *pDummyAttributes = 0;
    cosAttrValue *pSpecsIter = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_add_defn\n");

    if (!spec) {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_defn - Missing spec\n");
        ret = -1;
        goto out;
    }
    pSpecsIter = *spec;

    if (!tmpDn) {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_defn - Missing tmpDn\n");
        ret = -1;
        goto out;
    }
    pTmpTmplDn = *tmpDn;

    /* we don't want cosspecifiers that can be supplied by the same scheme */
    while (pSpecsIter) {
        if (cos_cache_attrval_exists(*pAttrs, pSpecsIter->val)) {
            /* no, this is not sane, lets reject the whole darn scheme in disgust */
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_defn - "
                                                               "cos definition %s supplies its own cosspecifier, rejecting scheme\n",
                          (*dn)->val);
            ret = -1;
        }

        pSpecsIter = pSpecsIter->list.pNext;
    }

    /* create the definition */
    if (0 == ret) {
        theDef = (cosDefinitions *)slapi_ch_malloc(sizeof(cosDefinitions));
        if (theDef) {
            theDef->pCosTmps = NULL;

            /* process each template in turn */

            slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_defn - "
                                                                  "Processing cosDefinition %s\n",
                          (*dn)->val);

            while (pTmpTmplDn && cosType != COSTYPE_INDIRECT) {
                /* create the template */
                if (!cos_cache_add_dn_tmpls(pTmpTmplDn->val, *spec, *pAttrs, &(theDef->pCosTmps)))
                    tmplCount++;

                pTmpTmplDn = pTmpTmplDn->list.pNext;
            }

            if (tmplCount == 0 && cosType != COSTYPE_INDIRECT) {
                /* without our golden templates we are nothing
                slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_defn -"
                "no templates for cos definition at %s.\n",(*dn)->val);*/
                ret = COS_DEF_ERROR_NO_TEMPLATES;
            } else {
                if (cosType == COSTYPE_INDIRECT) {
                    /*
                        Indirect cos schemes have no templates,
                        however, in order to take advantage of existing code
                        which is optimized to do a binary search on attributes
                        which are found through their templates, we add a dummy
                        template and dummy attributes.  The value of the attributes
                        will be ignored when later assessing a query.
                    */
                    pAttrsIter = *pAttrs;

                    while (pAttrsIter) {
                        pDummyAttrVal = NULL;
                        cos_cache_add_attrval(&pDummyAttrVal, "not used");
                        cos_cache_add_attr(&pDummyAttributes, pAttrsIter->val, pDummyAttrVal);

                        pAttrsIter = pAttrsIter->list.pNext;
                    }

                    cos_cache_add_attrval(tmpDn, "cn=dummy,");

                    cos_cache_add_tmpl(&(theDef->pCosTmps), *tmpDn, NULL, *spec, pDummyAttributes, NULL);
                    *tmpDn = 0;
                }

                theDef->pDn = *dn;
                theDef->cosType = cosType;
                theDef->pCosTargetTree = *tree;
                theDef->pCosTemplateDn = *tmpDn;
                theDef->pCosSpecifier = *spec;
                theDef->pCosAttrs = *pAttrs;
                theDef->pCosOverrides = *pOverrides;
                theDef->pCosOperational = *pOperational;
                theDef->pCosMerge = *pCosMerge;
                theDef->pCosOpDefault = *pCosOpDefault;

                cos_cache_add_ll_entry((void **)pDefs, theDef, NULL);
                slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_defn - "
                                                                      "Added cosDefinition %s\n",
                              (*dn)->val);
            }
        } else {
            ret = -1;
        }
    }
out:
    if (ret < 0) {
        slapi_ch_free((void **)&theDef);
        if (dn)
            cos_cache_del_attrval_list(dn);
        if (tree)
            cos_cache_del_attrval_list(tree);
        if (tmpDn)
            cos_cache_del_attrval_list(tmpDn);
        if (spec)
            cos_cache_del_attrval_list(spec);
        if (pAttrs)
            cos_cache_del_attrval_list(pAttrs);
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_add_defn\n");
    return ret;
}

/*
    cos_cache_del_attrval_list
    --------------------------
    walks the list deleting as it goes
*/
static void
cos_cache_del_attrval_list(cosAttrValue **pVal)
{
    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_del_attrval_list\n");

    while (*pVal) {
        cosAttrValue *pTmp = (*pVal)->list.pNext;

        slapi_ch_free((void **)&((*pVal)->val));
        slapi_ch_free((void **)&(*pVal));
        *pVal = pTmp;
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_del_attrval_list\n");
}


/*
    cos_cache_add_attrval
    ---------------------
    adds a value to an attribute value list
*/
static int
cos_cache_add_attrval(cosAttrValue **attrval, char *val)
{
    int ret = 0;
    cosAttrValue *theVal;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_add_attrval\n");

    /* create the attrvalue */
    theVal = (cosAttrValue *)slapi_ch_malloc(sizeof(cosAttrValue));
    if (theVal) {
        theVal->val = slapi_ch_strdup(val);
        if (theVal->val) {
            cos_cache_add_ll_entry((void **)attrval, theVal, NULL);
        } else {
            slapi_ch_free((void **)&theVal);
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_attrval - Failed to allocate memory\n");
            ret = -1;
        }
    } else {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_attrval - Failed to allocate memory\n");
        ret = -1;
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_add_attrval\n");
    return ret;
}

/*
    cos_cache_add_ll_entry - RECURSIVE for sorted lists
    ---------------------------------------------------
    if a compare function is passed as argument, the element
    is added to the linked list in the sorted order according
    to that compare functions algorithm.  This prepares the list
    for ultra fast indexing - requiring only to walk the list once
    to build the index.
    if no compare function is passed, the element is added
    to the head of the linked list
    the index is created after the linked list is complete,
    and so is always null until explicitly indexed

    *NOTE* this function assumes and *requires* that the structures
    passed to it in "attrval" and "theVal" have a cosIndexedLinkedList
    member, and it is the *first* member of the structure.  This
    is safe because this is a module level function, and all functions
    which call this one are part of the same sub-system.

    The compare function will also make a similar assumption, but
    likely one that recognizes the full structure or type, it is
    the responsibility of the caller to match input structures with
    the appropriate compare function.

    WARNING: current recursive sorting code never used, never tested
*/
static void
cos_cache_add_ll_entry(void **attrval, void *theVal, int (*compare)(const void *elem1, const void *elem2))
{
    static cosIndexedLinkedList *pLastList = 0;
    static cosIndexedLinkedList *first_element;
    static int call_count = 0;

    call_count++;
    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_add_ll_entry - "
                                                         "recursion level %d\n",
                  call_count);


    /*
        need to save the first element of the list
        we update this first element whenever an entry
        is added to the start of the list, this way
        we can ensure that the head of the list is always
        *attrval - callers pass us the head of the list
        and can expect that what they get back is also
        the head of the list
    */
    if (call_count == 1)
        first_element = *attrval;

    if (*attrval) {
        if (compare == NULL) {
            /* we dont want this list sorted */
            /* push this to the start of the list (because its quick) */
            ((cosIndexedLinkedList *)theVal)->pNext = *attrval;
            ((cosIndexedLinkedList *)theVal)->index = NULL;
            *attrval = theVal;
        } else {
            /* insert this in the list in sorted order
            (because its quicker for building indexes later) */
            int comp_ret = 0;

            comp_ret = compare(*attrval, theVal);
            if (comp_ret == 0 || comp_ret > 0) {
                /* insert prior to this element */
                if (pLastList)
                    pLastList->pNext = theVal;
                else
                    first_element = theVal;

                ((cosIndexedLinkedList *)theVal)->pNext = *attrval;
                ((cosIndexedLinkedList *)theVal)->index = NULL;
            } else {
                /* still looking - recurse on next element */
                pLastList = (cosIndexedLinkedList *)attrval;
                cos_cache_add_ll_entry(&(((cosIndexedLinkedList *)attrval)->pNext), theVal, compare);
            }

            if (call_count == 1)
                *attrval = first_element;
        }
    } else {
        /* new or end of list */
        ((cosIndexedLinkedList *)theVal)->pNext = NULL;
        ((cosIndexedLinkedList *)theVal)->index = NULL;
        if (call_count == 1) /* if new list */
            *attrval = theVal;
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_add_ll_entry - recursion level %d\n", call_count);
    call_count--;
}


/*
    cos_cache_getref
    ----------------
    retrieves a reference to the current cache and adds to the cache reference count
*/
int
cos_cache_getref(cos_cache **pptheCache)
{
    int ret = -1;
    static int first_time = 1;
    cosCache **ppCache = (cosCache **)pptheCache;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_getref\n");

    if (first_time) {
        first_time = 0;
        /* first customer, create the cache */
        slapi_lock_mutex(change_lock);
        if (pCache == NULL) {
            if (cos_cache_creation_lock()) {
                /* there was a problem or no COS definitions were found */
                slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_getref - No cos cache created\n");
            }
        }
        slapi_unlock_mutex(change_lock);
    }

    slapi_lock_mutex(cache_lock);

    *ppCache = pCache;

    if (pCache)
        ret = ++((*ppCache)->refCount);

    slapi_unlock_mutex(cache_lock);


    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_getref\n");
    return ret;
}

/*
    cos_cache_addref
    ----------------
    adds 1 to the cache reference count
*/
int
cos_cache_addref(cos_cache *ptheCache)
{
    int ret = 0;
    cosCache *pCache = (cosCache *)ptheCache;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_addref\n");

    slapi_lock_mutex(cache_lock);

    if (pCache)
        ret = ++(pCache->refCount);

    slapi_unlock_mutex(cache_lock);

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_addref\n");

    return ret;
}


/*
    cos_cache_release
    -----------------
    subtracts 1 from the cache reference count, if the count falls
    below 1, the cache is destroyed.
*/
int
cos_cache_release(cos_cache *ptheCache)
{
    int ret = 0;
    int destroy = 0;
    cosCache *pOldCache = (cosCache *)ptheCache;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_release\n");

    slapi_lock_mutex(cache_lock);

    if (pOldCache) {
        ret = --(pOldCache->refCount);
        if (ret == 0)
            destroy = 1;
    }

    slapi_unlock_mutex(cache_lock);

    if (destroy) {
        cosDefinitions *pDef = pOldCache->pDefs;

        /* now is the first time it is
         * safe to assess whether
         * vattr caching can be turned on
         */
        if (pCache && pCache->vattr_cacheable) {
            slapi_vattrcache_cache_all();
        }

        /* destroy the cache here - no locking required, no references outstanding */

        if (pDef)
            cos_cache_del_schema(pOldCache);

        while (pDef) {
            cosDefinitions *pTmpD = pDef;
            cosTemplates *pCosTmps = pDef->pCosTmps;

            while (pCosTmps) {
                cosTemplates *pTmpT = pCosTmps;

                pCosTmps = pCosTmps->list.pNext;

                cos_cache_del_attr_list(&(pTmpT->pAttrs));
                cos_cache_del_attrval_list(&(pTmpT->pObjectclasses));
                cos_cache_del_attrval_list(&(pTmpT->pDn));
                slapi_ch_free((void **)&(pTmpT->cosGrade));
                slapi_ch_free((void **)&pTmpT);
            }

            pDef = pDef->list.pNext;

            cos_cache_del_attrval_list(&(pTmpD->pDn));
            cos_cache_del_attrval_list(&(pTmpD->pCosTargetTree));
            cos_cache_del_attrval_list(&(pTmpD->pCosTemplateDn));
            cos_cache_del_attrval_list(&(pTmpD->pCosSpecifier));
            cos_cache_del_attrval_list(&(pTmpD->pCosAttrs));
            cos_cache_del_attrval_list(&(pTmpD->pCosOverrides));
            cos_cache_del_attrval_list(&(pTmpD->pCosOperational));
            cos_cache_del_attrval_list(&(pTmpD->pCosMerge));
            cos_cache_del_attrval_list(&(pTmpD->pCosOpDefault));
            slapi_ch_free((void **)&pTmpD);
        }

        if (pOldCache->ppAttrIndex)
            slapi_ch_free((void **)&(pOldCache->ppAttrIndex));
        if (pOldCache->ppTemplateList)
            slapi_ch_free((void **)&(pOldCache->ppTemplateList));
        slapi_ch_free((void **)&pOldCache);
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_release\n");

    return ret;
}


/*
    cos_cache_del_attr_list
    -----------------------
    walk the list deleting as we go
*/
static void
cos_cache_del_attr_list(cosAttributes **pAttrs)
{
    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_del_attr_list\n");

    while (*pAttrs) {
        cosAttributes *pTmp = (*pAttrs)->list.pNext;

        cos_cache_del_attrval_list(&((*pAttrs)->pAttrValue));
        slapi_ch_free((void **)&((*pAttrs)->pAttrName));
        slapi_ch_free((void **)&(*pAttrs));
        *pAttrs = pTmp;
    }


    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_del_attr_list\n");
}


/*
    cos_cache_del_schema
    --------------------
    delete the object class lists used for schema checking
*/
static void
cos_cache_del_schema(cosCache *pCache)
{
    char *pLastName = 0;
    int attr_index = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_del_schema\n");

    if (pCache && pCache->attrCount && pCache->ppAttrIndex) {
        pLastName = pCache->ppAttrIndex[0]->pAttrName;

        for (attr_index = 1; attr_index < pCache->attrCount; attr_index++) {
            if (slapi_utf8casecmp((unsigned char *)pCache->ppAttrIndex[attr_index]->pAttrName, (unsigned char *)pLastName)) {
                /* remember what went before */
                pLastName = pCache->ppAttrIndex[attr_index]->pAttrName;

                /* then blow it away */
                cos_cache_del_attrval_list(&(pCache->ppAttrIndex[attr_index]->pObjectclasses));
            }
        }
        /* Finally, remove the first attribute's objectclass list */
        cos_cache_del_attrval_list(&(pCache->ppAttrIndex[0]->pObjectclasses));
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_del_schema\n");
}


/*
    cos_cache_add_attr
    ------------------
    Adds an attribute to the list
*/
static int
cos_cache_add_attr(cosAttributes **pAttrs, char *name, cosAttrValue *val)
{
    int ret = 0;
    cosAttributes *theAttr;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_add_attr\n");

    /* create the attribute */
    theAttr = (cosAttributes *)slapi_ch_malloc(sizeof(cosAttributes));
    if (theAttr) {
        theAttr->pAttrValue = val;
        theAttr->pObjectclasses = 0; /* schema issues come later */
        theAttr->pAttrName = slapi_ch_strdup(name);
        if (theAttr->pAttrName) {
            cos_cache_add_ll_entry((void **)pAttrs, theAttr, NULL);
            slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_attr - Added attribute %s\n", name);
        } else {
            slapi_ch_free((void **)&theAttr);
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_attr - Failed to allocate memory\n");
            ret = -1;
        }
    } else {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_attr - Failed to allocate memory\n");
        ret = -1;
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_add_attr\n");
    return ret;
}


/*
    cos_cache_add_tmpl
    ------------------
    Adds a template to the list
*/
static int
cos_cache_add_tmpl(cosTemplates **pTemplates, cosAttrValue *dn, cosAttrValue *objclasses, cosAttrValue *pCosSpecifier, cosAttributes *pAttrs, cosAttrValue *cosPriority)
{
    int ret = 0;
    cosTemplates *theTemp;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_add_tmpl\n");

    /* create the attribute */
    theTemp = (cosTemplates *)slapi_ch_malloc(sizeof(cosTemplates));
    if (theTemp) {
        char *grade = NULL;
        int grade_index = 0;
        int index = 0;
        int template_default = 0;
        char *ptr = NULL;
        char *normed = slapi_create_dn_string("%s", dn->val);
        if (normed) {
            slapi_ch_free_string(&dn->val);
            dn->val = normed;
        } else {
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM,
                          "cos_cache_add_tmpl - Failed to normalize dn %s. "
                          "Processing the pre normalized dn.\n",
                          dn->val);
        }
        grade = (char *)slapi_ch_malloc(strlen(dn->val) + 1);

        /* extract the cos grade */
        ptr = strchr(dn->val, '=');

        if (ptr) {
            int quotes = 0;
            int lastindex = strlen(dn->val) - 1;
            index = ptr - dn->val + 1;

            /* copy the grade (supports one level of quote nesting in rdn) */
            while (dn->val[index] != ',' || dn->val[index - 1] == '\\' || quotes == 1) {
                if (dn->val[index] == '"') {
                    if (quotes == 0)
                        quotes = 1;
                    else
                        quotes = 0;
                } else {
                    if (dn->val[index] == '\\') {
                        if ((index + 2 <= lastindex) && isxdigit(dn->val[index + 1]) &&
                            isxdigit(dn->val[index + 2])) {
                            /* Convert ESC HEX HEX to a real char */
                            int n = slapi_hexchar2int(dn->val[index + 1]);
                            int n2 = slapi_hexchar2int(dn->val[index + 2]);
                            n = (n << 4) + n2;
                            if (n == 0) {                              /* don't change \00 */
                                grade[grade_index] = dn->val[index++]; /* '\\' */
                                grade_index++;
                                grade[grade_index] = dn->val[index++]; /* 0 */
                                grade_index++;
                                grade[grade_index] = dn->val[index]; /* 0 */
                                grade_index++;
                            } else {
                                grade[grade_index] = n;
                                index += 2;
                                grade_index++;
                            }
                        } /* else: skip escape chars */
                    } else {
                        grade[grade_index] = dn->val[index];
                        grade_index++;
                    }
                }

                index++;
            }

            grade[grade_index] = '\0';

            /* ok, grade copied, is it the default template? */

            if (pCosSpecifier) /* some schemes don't have one */
            {
                char tmpGrade[BUFSIZ];

                if (strlen(pCosSpecifier->val) < (sizeof(tmpGrade) - 9)) { /* 9 for "-default" */
                    strcpy(tmpGrade, pCosSpecifier->val);
                    strcat(tmpGrade, "-default");
                    if (!slapi_utf8casecmp((unsigned char *)grade, (unsigned char *)tmpGrade))
                        template_default = 1;
                } else {
                    /*
                     * We shouldn't pass ever through this code as we expect
                     * pCosSpecifier values to be reasonably smaller than BUFSIZ
                     *
                     * only 2 lines of code -> no need to set an indirect char *
                     * duplicate the lines of code for clearness instead
                     */
                    char *newTmpGrade = PR_smprintf("%s-default", pCosSpecifier->val);
                    if (!slapi_utf8casecmp((unsigned char *)grade, (unsigned char *)newTmpGrade))
                        template_default = 1;
                    PR_smprintf_free(newTmpGrade);
                }
            }

        } else {
            /* mmm, should never get here, it means the dn is whacky */
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_tmpl - Malformed dn detected: %s\n", dn->val);
            grade[0] = '\0';
        }

        /* now fill in the blanks */
        theTemp->pDn = dn;
        theTemp->pObjectclasses = objclasses;
        theTemp->pAttrs = pAttrs;
        theTemp->cosGrade = slapi_ch_strdup(grade);
        theTemp->template_default = template_default;
        theTemp->cosPriority = (unsigned long)-1;

        if (cosPriority) {
            theTemp->cosPriority = atol(cosPriority->val);
            cos_cache_del_attrval_list(&cosPriority);
        }

        cos_cache_add_ll_entry((void **)pTemplates, theTemp, NULL);
        slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_tmpl - Added template %s\n", dn->val);

        slapi_ch_free((void **)&grade);
    } else {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_add_tmpl - Failed to allocate memory\n");
        ret = -1;
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_add_tmpl\n");
    return ret;
}

/*
    cos_cache_attrval_exists
    ------------------------
    performs linear search on the list for a
    cosAttrValue that matches val
    however, if the "index" member of cosAttrValue
    is non-null then a binary search is performed
    on the index {PARPAR: TO BE DONE}

    return 1 on found, 0 otherwise
*/
static int
cos_cache_attrval_exists(cosAttrValue *pAttrs, const char *val)
{
    int ret = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_attrval_exists\n");

    while (pAttrs) {
        if (!slapi_utf8casecmp((unsigned char *)pAttrs->val, (unsigned char *)val)) {
            ret = 1;
            break;
        }

        pAttrs = pAttrs->list.pNext;
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_attrval_exists\n");
    return ret;
}


static int
cos_cache_vattr_get(vattr_sp_handle *handle __attribute__((unused)),
                    vattr_context *c,
                    Slapi_Entry *e,
                    char *type,
                    Slapi_ValueSet **results,
                    int *type_name_disposition,
                    char **actual_type_name,
                    int flags __attribute__((unused)),
                    int *free_flags,
                    void *hint __attribute__((unused)))
{
    cos_cache *pCache = 0;
    int indirect_cos = 0;
    int ret = -1;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_vattr_get\n");

    if (cos_cache_getref(&pCache) < 1) {
        /* problems we are hosed */
        slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_vattr_get - "
                                                              "Failed to get class of service reference\n");
        goto bail;
    }

    ret = cos_cache_query_attr(pCache, c, e, type, results, NULL, NULL, NULL, &indirect_cos);
    if (ret == 0) {
        if (indirect_cos) {
            /* we can't cache indirect cos */
            *free_flags = SLAPI_VIRTUALATTRS_RETURNED_COPIES;
        } else {
            *free_flags = SLAPI_VIRTUALATTRS_RETURNED_COPIES | SLAPI_VIRTUALATTRS_VALUES_CACHEABLE;
        }
        *actual_type_name = slapi_ch_strdup(type);
        *type_name_disposition = SLAPI_VIRTUALATTRS_TYPE_NAME_MATCHED_EXACTLY_OR_ALIAS;
    }
    cos_cache_release(pCache);

bail:

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_vattr_get\n");
    return ret;
}


static int
cos_cache_vattr_compare(vattr_sp_handle *handle __attribute__((unused)),
                        vattr_context *c,
                        Slapi_Entry *e,
                        char *type,
                        Slapi_Value *test_this,
                        int *result,
                        int flags __attribute__((unused)),
                        void *hint __attribute__((unused)))
{
    int ret = -1;
    cos_cache *pCache = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_vattr_compare\n");

    if (cos_cache_getref(&pCache) < 1) {
        /* problems we are hosed */
        slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_vattr_compare - Failed to get class of service reference\n");
        goto bail;
    }

    ret = cos_cache_query_attr(pCache, c, e, type, NULL, test_this, result, NULL, NULL);

    cos_cache_release(pCache);

bail:

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_vattr_compare\n");
    return ret;
}

/*
 * this imp is damn slow
 *
 */
static int
cos_cache_vattr_types(vattr_sp_handle *handle __attribute__((unused)),
                      Slapi_Entry *e,
                      vattr_type_list_context *type_context,
                      int flags __attribute__((unused)))
{
    int ret = 0;
    int index = 0;
    cosCache *pCache;
    char *lastattr = "thisisfakeforcos";
    int props = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_vattr_types\n");

    if (cos_cache_getref((cos_cache **)&pCache) < 1) {
        /* problems we are hosed */
        slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_vattr_types - Failed to get class of service reference\n");
        goto bail;
    }

    while (index < pCache->attrCount) {
        if (slapi_utf8casecmp(
                (unsigned char *)pCache->ppAttrIndex[index]->pAttrName,
                (unsigned char *)lastattr)) {
            lastattr = pCache->ppAttrIndex[index]->pAttrName;

            if (1 == cos_cache_query_attr(pCache, NULL, e, lastattr, NULL, NULL,
                                          NULL, &props, NULL)) {
                /* entry contains this attr */
                vattr_type_thang thang = {0};

                thang.type_name = lastattr;
                thang.type_flags = props;

                slapi_vattrspi_add_type(type_context, &thang, 0);
            }
        }
        index++;
    }
    cos_cache_release(pCache);

bail:

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_vattr_types\n");
    return ret;
}


/*
    cos_cache_query_attr
    --------------------
    queries the cache to determine if this entry
    should have an attribute of "type", and if so,
    returns the attribute values in "vals" - which
    should be subsequently freed by a call to
    cos_cache_query_attr_free()

    returns
        0 on success, we added a computed attribute
        1 on outright failure
        > LDAP ERROR CODE
        -1 when doesn't know about attribute

    {PARPAR} must also check the attribute does not exist if we are not
    overriding and allow the DS logic to pick it up by denying knowledge
    of attribute
*/
static int
cos_cache_query_attr(cos_cache *ptheCache, vattr_context *context, Slapi_Entry *e, char *type, Slapi_ValueSet **out_attr, Slapi_Value *test_this, int *result, int *props, int *indirect_cos)
{
    int ret = -1;
    cosCache *pCache = (cosCache *)ptheCache;
    char *pDn = 0;
    Slapi_Attr *pObjclasses = 0;
    int attr_index = 0;         /* for looping through attributes */
    int attr_matched_index = 0; /* for identifying the matched attribute */
    int hit = 0;
    cosAttributes *pDefAttr = 0;
    Slapi_Value *val;
    /*    int type_name_disposition;
    char *actual_type_name;
    int flags = 0;
    int free_flags;*/
    Slapi_Attr *pTmpVals;
    int using_default = 0;
    int entry_has_value = 0;
    int merge_mode = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_query_attr\n");


    if (out_attr)
        *out_attr = 0;

    /*
        to perform this operation we need to know:

        * if we know about the attribute, if not just exit
        --
        * dn,to determine its relevancy to any cos definition,
          it must be a child of cosTargetTree
        --
        * objectclasses,to determine if the cos attribute will
          violate schema (only when schema checking is on)
        --
        * class of service specifier, for matching definitions
          - cosSpecifier is the attribute name and is used to
          determine the cosDefinition to use, its value determines
          the template to use
        --
        * the cosAttribute(s) (from the cosDefinition(s)) that match
        the attribute name.
        ($$)If these have a postfix of "default", then it is the same
        as no postfix i.e. this acts as the default value.  If it has
        a postfix of "override", then the value in the matching template
        is used regardless of any value stored in the entry.  This has
        been worked out previously so we can use a bool indicator in
        the cosDefinition structure to determine what to do.
        --
        * the value of the attribute in the entry -
          if present it overrides any default template value (see $$)

        Also this ordering ensures least work done to fail (in this
        implementation)
    */

    /** attribute **/
    /*
        lets be sure we need to do something
        most of the time we probably don't
    */
    attr_index = cos_cache_find_attr(pCache, type);
    if (attr_index == -1) {
        /* we don't know about this attribute */
        goto bail;
    }

    /*
        if there is a value in the entry the outcome
        of the cos attribute resolution may be different
    */
    slapi_entry_attr_find(e, type, &pTmpVals);
    if (pTmpVals)
        entry_has_value = 1;

    /** dn **/
    pDn = slapi_entry_get_dn(e);

    if (pDn == 0) {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_query_attr - Failed to get entry dn\n");
        ret = 1;
        goto bail;
    }

    slapi_dn_normalize(pDn);

    /** objectclasses **/
    if (pCache->ppAttrIndex[attr_index]->attr_operational == 0 && config_get_schemacheck() &&
        pCache->ppAttrIndex[attr_index]->attr_operational_default == 0) {
        /* does this entry violate schema? */

        if (slapi_entry_attr_find(e, "objectclass", &pObjclasses)) {
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_query_attr - Failed to get objectclass from %s\n", pDn);
            goto bail;
        }

        if (!cos_cache_schema_check(pCache, attr_index, pObjclasses)) {
            slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_query_attr - cos attribute %s failed schema check on dn: %s\n", type, pDn);
            goto bail;
        }
    }

    /** class of service specifier **/
    /*
        Now we need to iterate through the attributes to discover
        if one fits all the criteria, we'll take the first that does
        and blow off the rest unless the definition has merge-scheme
        set.
    */
    do {
        /* for convenience, define some pointers */
        cosAttributes *pAttr = pCache->ppAttrIndex[attr_index];
        cosTemplates *pTemplate = (cosTemplates *)pAttr->pParent;
        cosDefinitions *pDef = (cosDefinitions *)pTemplate->pParent;
        cosAttrValue *pTargetTree = pDef->pCosTargetTree;

        /* now for the tests */

        /* would we be allowed to supply this attribute if we had one? */
        if (entry_has_value && !pAttr->attr_override && !pAttr->attr_operational && !pAttr->attr_operational_default) {
            /* answer: no, move on to the next attribute */
            attr_index++;
            continue;
        }

        /* if we are in merge_mode, can the attribute be merged? */
        if (merge_mode && pAttr->attr_cos_merge == 0) {
            /* answer: no, move on to the next attribute */
            attr_index++;
            continue;
        }

        /* If we haven't found a hit yet, or if we are in merge mode, look for
         * hits.  We only check if this entry is a child of the target tree(s). */
        while ((hit == 0 || merge_mode) && pTargetTree) {
            if (pTargetTree->val == 0 ||
                slapi_dn_issuffix(pDn, pTargetTree->val) != 0 ||
                (views_api && views_entry_exists(views_api, pTargetTree->val, e)) /* might be in a view */
                ) {
                cosAttrValue *pSpec = pDef->pCosSpecifier;
                Slapi_ValueSet *pAttrSpecs = 0;


                /* Does this entry have a correct cosSpecifier? */
                do {
                    int type_name_disposition = 0;
                    char *actual_type_name = 0;
                    int free_flags = 0;

                    if (pSpec && pSpec->val) {
                        ret = slapi_vattr_values_get_sp(context, e, pSpec->val, &pAttrSpecs, &type_name_disposition, &actual_type_name, 0, &free_flags);
                        /* MAB: We need to free actual_type_name here !!!
                        XXX BAD--should use slapi_vattr_values_free() */
                        slapi_ch_free((void **)&actual_type_name);
                    }

                    if (pAttrSpecs || pDef->cosType == COSTYPE_POINTER) {
                        int index = 0;

                        /* does the cosSpecifier value correspond to this template? */
                        if (pDef->cosType == COSTYPE_INDIRECT) {
                            /*
                                it always does correspond for indirect schemes (it's a dummy value)
                                now we must follow the dn of our pointer and retrieve a value to
                                return
                                Note: we support one dn only, the result of multiple pointers is undefined
                            */
                            Slapi_Value *indirectdn;
                            Slapi_ValueSet *tmp_vals = NULL;
                            int pointer_flags = 0;
                            int hint = 0;

                            hint = slapi_valueset_first_value(pAttrSpecs, &indirectdn);

                            if (props)
                                pointer_flags = *props;

                            while (indirectdn != NULL) {
                                if (cos_cache_follow_pointer(context, (char *)slapi_value_get_string(indirectdn),
                                                             type, &tmp_vals, test_this, result, pointer_flags) == 0) {
                                    if (indirect_cos) {
                                        *indirect_cos = 1;
                                    }
                                    hit = 1;
                                    /* If the caller requested values, set them.  We need
                                     * to append values when we follow multiple pointers DNs. */
                                    if (out_attr && tmp_vals) {
                                        if (*out_attr) {
                                            Slapi_Attr *attr = NULL;
                                            Slapi_Value *val = NULL;
                                            int idx = 0;

                                            /* Create an attr to use for duplicate detection. */
                                            attr = slapi_attr_new();
                                            slapi_attr_init(attr, type);

                                            /* Copy any values into out_attr if they don't already exist. */
                                            for (idx = slapi_valueset_first_value(tmp_vals, &val);
                                                 val && (idx != -1);
                                                 idx = slapi_valueset_next_value(tmp_vals, idx, &val)) {
                                                if (slapi_valueset_find(attr, *out_attr, val) == NULL) {
                                                    slapi_valueset_add_value(*out_attr, val);
                                                }
                                            }

                                            slapi_attr_free(&attr);
                                            slapi_valueset_free(tmp_vals);
                                            tmp_vals = NULL;
                                        } else {
                                            *out_attr = tmp_vals;
                                            tmp_vals = NULL;
                                        }
                                    }
                                }

                                /* If this definition has merge-scheme set, we
                                 * need to follow the rest of the pointers. */
                                if (pAttr->attr_cos_merge) {
                                    hint = slapi_valueset_next_value(pAttrSpecs, hint, &indirectdn);
                                } else {
                                    indirectdn = NULL;
                                }
                            }

                            /* If merge-scheme is specified, set merge mode.  This will allow
                             * us to merge in values from other CoS definitions for this attr. */
                            if (pAttr->attr_cos_merge) {
                                merge_mode = 1;
                                attr_matched_index = attr_index;
                            }
                        } else {
                            if (pDef->cosType != COSTYPE_POINTER)
                                index = slapi_valueset_first_value(pAttrSpecs, &val);

                            while (pDef->cosType == COSTYPE_POINTER || val) {
                                if (pDef->cosType == COSTYPE_POINTER || !slapi_utf8casecmp((unsigned char *)pTemplate->cosGrade, (unsigned char *)slapi_value_get_string(val))) {
                                    /* we have a hit */


                                    if (out_attr) {
                                        if (cos_cache_cos_2_slapi_valueset(pAttr, out_attr) == 0)
                                            hit = 1;
                                        else {
                                            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM,
                                                          "cos_cache_query_attr - Could not create values to return\n");
                                            goto bail;
                                        }

                                        if (pAttr->attr_cos_merge) {
                                            merge_mode = 1;
                                            attr_matched_index = attr_index;
                                        }
                                    } else {
                                        if (test_this && result) {
                                            /* compare op */
                                            if (cos_cache_cmp_attr(pAttr, test_this, result)) {
                                                hit = 1;
                                            }
                                        } else {
                                            /* well, this must be a request for type only */
                                            hit = 1;
                                        }
                                    }

                                    break;
                                }

                                if (pDef->cosType != COSTYPE_POINTER)
                                    index = slapi_valueset_next_value(pAttrSpecs, index, &val);
                            }
                        }
                    }

                    if (pSpec)
                        pSpec = pSpec->list.pNext;

                } while (hit == 0 && pSpec);

                /* MAB: We need to free pAttrSpecs here !!!
                XXX BAD--should use slapi_vattr_values_free()*/
                slapi_valueset_free(pAttrSpecs);

                /* is the cosTemplate the default template? */
                if (hit == 0 && pTemplate->template_default && !pDefAttr) {
                    /* then lets save the attr in case we need it later */
                    pDefAttr = pAttr;
                }
            }

            pTargetTree = pTargetTree->list.pNext;

        } /* while(hit == 0 && pTargetTree) */


        if (hit == 0 || merge_mode)
            attr_index++;

    } while (
        (hit == 0 || merge_mode) &&
        pCache->attrCount > attr_index &&
        !slapi_utf8casecmp((unsigned char *)type, (unsigned char *)pCache->ppAttrIndex[attr_index]->pAttrName));

    if (!merge_mode)
        attr_matched_index = attr_index;

    /* should we use a default value? */
    if (hit == 0 && pDefAttr) {
        /* we have a hit */

        using_default = 1;

        if (out_attr) {
            if (cos_cache_cos_2_slapi_valueset(pDefAttr, out_attr) == 0)
                hit = 1;
            else {
                slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_query_attr - "
                                                                   "Could not create values to return\n");
                goto bail;
            }
        } else {
            if (test_this && result) {
                /* compare op */
                if (cos_cache_cmp_attr(pDefAttr, test_this, result))
                    hit = 1;
            } else {
                /* well, this must be a request for type only and the entry gets default template value */
                hit = 1;
            }
        }
    }

    if (hit == 1 && out_attr == NULL && test_this == NULL)
        ret = 1;
    else if (hit == 1)
        ret = 0;
    else
        ret = -1;

    if (props)
        *props = 0;

    if (hit == 1 && props) {
        if (
            (using_default && pDefAttr &&
             ((pDefAttr->attr_operational == 1) || (pDefAttr->attr_operational_default == 1))) ||
            (!using_default && pCache && pCache->ppAttrIndex && pCache->ppAttrIndex[attr_matched_index] &&
             ((pCache->ppAttrIndex[attr_matched_index]->attr_operational == 1) ||
              (pCache->ppAttrIndex[attr_matched_index]->attr_operational_default == 1)))) {
            /* this is an operational attribute, lets mark it so */
            *props |= SLAPI_ATTR_FLAG_OPATTR;
        }
    }

bail:

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_query_attr\n");
    return ret;
}

/*
    cos_cache_find_attr
    -------------------
    searches for the attribute "type", and if found returns the index
    of the first occurrance of the attribute in the cache top level
    indexed attribute list.
*/
static int
cos_cache_find_attr(cosCache *pCache, char *type)
{
    int ret = -1; /* assume failure */
    cosAttributes attr;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_find_attr\n");

    attr.pAttrName = type;

    if (pCache->attrCount - 1 != 0)
        ret = cos_cache_attr_index_bsearch(pCache, &attr, 0, pCache->attrCount - 1);
    else {
        /* only one attribute (that will fool our bsearch) lets check it here */
        if (!slapi_utf8casecmp((unsigned char *)type, (unsigned char *)(pCache->ppAttrIndex)[0]->pAttrName)) {
            ret = 0;
        }
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_find_attr\n");
    return ret;
}


/*
    cos_cache_schema_check
    ----------------------
    check those object classes which match in the input list and the
    cached set for allowed attribute types

    return non-null for schema matches, zero otherwise
*/
static int
cos_cache_schema_check(cosCache *pCache, int attr_index, Slapi_Attr *pObjclasses)
{
    int ret = 0; /* assume failure */
    Slapi_Value *val;
    int hint;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_schema_check\n");

    hint = slapi_attr_first_value(pObjclasses, &val);
    while (hint != -1) {
        ret = cos_cache_attrval_exists(pCache->ppAttrIndex[attr_index]->pObjectclasses, (char *)slapi_value_get_string(val));
        if (ret)
            break;

        hint = slapi_attr_next_value(pObjclasses, hint, &val);
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_schema_check\n");
    return ret;
}

/*
    cos_cache_schema_build
    ----------------------
    For each attribute in our global cache add the objectclasses which allow it.
    This may be referred to later to check schema is not being violated.
*/
static int
cos_cache_schema_build(cosCache *pCache)
{
    int ret = 0; /* we assume success, with operational attributes not supplied in schema we might fail otherwise */
    struct objclass *oc;
    char *pLastName = 0;
    cosAttrValue *pLastRef = 0;
    int attr_index = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_schema_build\n");

    if (!config_get_schemacheck())
        ret = 0;

    /*
        it is expected that in all but the most hard core cases, the number of
        objectclasses will out number the attributes we look after - so we make
        the objectclasses the outside loop.  However, even if they are not, we
        perform binary searches on the attribute list anyway, so it should be
        considerably faster to search than the linked list of objectclasses (even
        with the string comparisons going on)
    */
    oc_lock_read();
    for (oc = g_get_global_oc_nolock(); oc != NULL; oc = oc->oc_next) {
        char **pppAttrs[2];
        int index;
        int attrType = 0;

        pppAttrs[0] = oc->oc_required;
        pppAttrs[1] = oc->oc_allowed;

        /* we need to check both required and allowed attributes I think */
        while (attrType < 2) {
            if (pppAttrs[attrType]) {
                index = 0;

                while (pppAttrs[attrType][index]) {
                    attr_index = cos_cache_find_attr(pCache, pppAttrs[attrType][index]);
                    if (attr_index != -1) {
                        /*
                            this attribute is one of ours, add this
                            objectclass to the objectclass list
                            note the index refers to the first
                            occurrence of this attribute in the list,
                            later we will copy over references to this
                            list to all the other attribute duplicates.
                        */

                        cos_cache_add_attrval(&(pCache->ppAttrIndex[attr_index]->pObjectclasses), oc->oc_name);
                        ret = 0;
                    }
                    index++;
                }
            }

            attrType++;
        }
    }
    oc_unlock();

    /*
        OK, now we need to add references to the real
        lists to the duplicate attribute entries.
        (this allows the schema check to be a little
        less complex and just a little quicker)
    */
    pLastName = pCache->ppAttrIndex[0]->pAttrName;
    pLastRef = pCache->ppAttrIndex[0]->pObjectclasses;

    for (attr_index = 1; attr_index < pCache->attrCount; attr_index++) {
        if (!slapi_utf8casecmp((unsigned char *)pCache->ppAttrIndex[attr_index]->pAttrName, (unsigned char *)pLastName)) {
            /* copy over reference */
            pCache->ppAttrIndex[attr_index]->pObjectclasses = pLastRef;
        } else {
            /* remember what went before */
            pLastName = pCache->ppAttrIndex[attr_index]->pAttrName;
            pLastRef = pCache->ppAttrIndex[attr_index]->pObjectclasses;
        }
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_schema_build\n");
    return ret;
}


/*
    cos_cache_index_all
    -------------------
    Indexes every attribute in the cache for fast binary lookup
    on attributes from the top level of the cache.
    Also fixes up all parent pointers so that a single attribute
    lookup will allow access to all information regarding that attribute.
    Attributes that appear more than once in the cache will also
    be indexed more than once - this means that a pure binary
    search is not possible, but it is possible to make use of a
    duplicate entry aware binary search function - which are rare beasts,
    so we'll need to provide cos_cache_attr_bsearch()

    This is also a handy time to mark the attributes as overides if
    necessary
*/

static int
cos_cache_index_all(cosCache *pCache)
{
    int ret = -1;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_index_all\n");

    /*
        first fixup the index array so we can use qsort()
        also fixup the parent pointers
    */

    pCache->ppTemplateList = 0;
    pCache->templateCount = 0;
    pCache->ppAttrIndex = 0;

    pCache->attrCount = cos_cache_total_attr_count(pCache);
    if (pCache->attrCount && pCache->templateCount) {
        int tmpindex = 0;
        int cmpindex = 0;
        int actualCount = 0;

        pCache->ppAttrIndex = (cosAttributes **)slapi_ch_malloc(sizeof(cosAttributes *) * pCache->attrCount);
        pCache->ppTemplateList = (char **)slapi_ch_calloc((pCache->templateCount + 1) * 2, sizeof(char *));
        if (pCache->ppAttrIndex && pCache->ppTemplateList) {
            int attrcount = 0;
            cosDefinitions *pDef = pCache->pDefs;
            cosAttrValue *pAttrVal = 0;

            while (pDef) {
                cosTemplates *pCosTmps = pDef->pCosTmps;

                while (pCosTmps) {
                    cosAttributes *pAttrs = pCosTmps->pAttrs;

                    pCosTmps->pParent = pDef;

                    while (pAttrs) {
                        pAttrs->pParent = pCosTmps;
                        (pCache->ppAttrIndex)[attrcount] = pAttrs;

                        if (cos_cache_attrval_exists(pDef->pCosOverrides, pAttrs->pAttrName))
                            pAttrs->attr_override = 1;
                        else
                            pAttrs->attr_override = 0;

                        if (cos_cache_attrval_exists(pDef->pCosOperational, pAttrs->pAttrName))
                            pAttrs->attr_operational = 1;
                        else
                            pAttrs->attr_operational = 0;

                        if (cos_cache_attrval_exists(pDef->pCosMerge, pAttrs->pAttrName))
                            pAttrs->attr_cos_merge = 1;
                        else
                            pAttrs->attr_cos_merge = 0;

                        if (cos_cache_attrval_exists(pDef->pCosOpDefault, pAttrs->pAttrName))
                            pAttrs->attr_operational_default = 1;
                        else
                            pAttrs->attr_operational_default = 0;

                        attrcount++;

                        pAttrs = pAttrs->list.pNext;
                    }

                    pCosTmps = pCosTmps->list.pNext;
                }

                /*
                    we need to build the template dn list too,
                    we are going to take care that we do not
                    add duplicate dns or dns that have
                    ancestors elsewhere in the list since this
                    list will be binary searched (with a special
                    BS alg) to find an ancestor tree for a target
                    that has been modified - that comes later in
                    this function however - right now we'll just
                    slap them in the list
                */
                pAttrVal = pDef->pCosTemplateDn;

                while (pAttrVal) {
                    char *normed = slapi_create_dn_string("%s", pAttrVal->val);
                    if (normed) {
                        slapi_ch_free_string(&pAttrVal->val);
                        pAttrVal->val = normed;
                    } else {
                        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM,
                                      "cos_cache_index_all - Failed to normalize dn %s. "
                                      "Processing the pre normalized dn.\n",
                                      pAttrVal->val);
                    }
                    pCache->ppTemplateList[tmpindex] = pAttrVal->val;

                    tmpindex++;
                    pAttrVal = pAttrVal->list.pNext;
                }

                pDef = pDef->list.pNext;
            }

            /* now sort the index array */
            qsort(pCache->ppAttrIndex, attrcount, sizeof(cosAttributes *), cos_cache_attr_compare);
            qsort(pCache->ppTemplateList, tmpindex, sizeof(char *), cos_cache_string_compare);

            /*
                now we have the sorted template dn list, we can get rid of
                duplicates and entries that have an ancestor elsewhere in
                the list - all this in the name of faster searches
            */

            /* first go through zapping the useless  PARPAR - THIS DOES NOT WORK */
            tmpindex = 1;
            cmpindex = 0;
            actualCount = pCache->templateCount;

            while (tmpindex < pCache->templateCount) {
                if (
                    !slapi_utf8casecmp((unsigned char *)pCache->ppTemplateList[tmpindex], (unsigned char *)pCache->ppTemplateList[cmpindex]) ||
                    slapi_dn_issuffix(pCache->ppTemplateList[tmpindex], pCache->ppTemplateList[cmpindex])) {
                    /* this guy is a waste of space */
                    pCache->ppTemplateList[tmpindex] = 0;
                    actualCount--;
                } else
                    cmpindex = tmpindex;

                tmpindex++;
            }

            /* now shuffle everything up to the front to cover the bald spots */
            tmpindex = 1;
            cmpindex = 0;

            while (tmpindex < pCache->templateCount) {
                if (pCache->ppTemplateList[tmpindex] != 0) {
                    if (cmpindex) {
                        pCache->ppTemplateList[cmpindex] = pCache->ppTemplateList[tmpindex];
                        pCache->ppTemplateList[tmpindex] = 0;
                        cmpindex++;
                    }
                } else {
                    if (cmpindex == 0)
                        cmpindex = tmpindex;
                }

                tmpindex++;
            }

            pCache->templateCount = actualCount;

            slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_index_all - cos cache index built\n");

            ret = 0;
        } else {
            if (pCache->ppAttrIndex)
                slapi_ch_free((void **)(&pCache->ppAttrIndex));

            if (pCache->ppTemplateList)
                slapi_ch_free((void **)(&pCache->ppTemplateList));

            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_index_all - "
                                                               "Failed to allocate index memory\n");
        }
    } else
        slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_index_all - No attributes to index\n");

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_index_all\n");
    return ret;
}


/*
    cos_cache_total_attr_count
    --------------------------
    walks the entire cache counting all attributes
    note: this is coded so that it may be called
    prior to the cache indexing of attributes - in
    fact it is called by the code that creates the
    index.  Once indexing has been performed, it is
    *much* *much* faster to get the count from the
    cache object itself - cosCache::attrCount.

    Additionally - a side effect is that the template
    target trees are counted and placed in the cache level
    target tree count - probably should be renamed,
    but lets let it slide for now

    returns the number of attributes counted
*/
static int
cos_cache_total_attr_count(cosCache *pCache)
{
    int count = 0;
    cosDefinitions *pDef = pCache->pDefs;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_total_attr_count\n");

    pCache->templateCount = 0;

    while (pDef) {
        cosTemplates *pCosTmps = pDef->pCosTmps;

        while (pCosTmps) {
            cosAttributes *pAttrs = pCosTmps->pAttrs;

            while (pAttrs) {
                count++;
                pAttrs = pAttrs->list.pNext;
            }

            pCache->templateCount++;
            pCosTmps = pCosTmps->list.pNext;
        }

        pDef = pDef->list.pNext;
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_total_attr_count\n");
    return count;
}


static int
cos_cache_attr_compare(const void *e1, const void *e2)
{
    int com_Result;
    cosAttributes *pAttr = (*(cosAttributes **)e1);
    cosTemplates *pTemplate = (cosTemplates *)pAttr->pParent;
    cosAttributes *pAttr1 = (*(cosAttributes **)e2);
    cosTemplates *pTemplate1 = (cosTemplates *)pAttr1->pParent;

    /* Now compare the names of the attributes */
    com_Result = slapi_utf8casecmp((unsigned char *)(*(cosAttributes **)e1)->pAttrName,
                                   (unsigned char *)(*(cosAttributes **)e2)->pAttrName);
    if (0 == com_Result) {
        /* Now compare the cosPriorities */
        com_Result = pTemplate->cosPriority - pTemplate1->cosPriority;
    }
    if (0 == com_Result)
        return -1;

    return com_Result;
}

static int
cos_cache_string_compare(const void *e1, const void *e2)
{
    if (!e1 && e2) {
        return 1;
    } else if (e1 && !e2) {
        return -1;
    } else if (!e1 && !e2) {
        return 0;
    }
    return slapi_utf8casecmp((*(unsigned char **)e1), (*(unsigned char **)e2));
}

static int
cos_cache_template_index_compare(const void *e1, const void *e2)
{
    int ret = 0;

    if (!e1 && e2) {
        return 1;
    } else if (e1 && !e2) {
        return -1;
    } else if (!e1 && !e2) {
        return 0;
    }
    if (0 == slapi_dn_issuffix((const char *)e1, *(const char **)e2))
        ret = slapi_utf8casecmp(*(unsigned char **)e2, (unsigned char *)e1);
    else
        ret = 0;

    return ret;
}

/*
    cos_cache_template_index_bsearch
    --------------------------------
    searches the template dn index for a match
*/
static int
cos_cache_template_index_bsearch(const char *dn)
{
    int ret = 0;
    cosCache *pCache;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_template_index_bsearch\n");

    if (-1 != cos_cache_getref((cos_cache **)&pCache)) {
        if (bsearch(dn, pCache->ppTemplateList, pCache->templateCount, sizeof(char *), cos_cache_template_index_compare))
            ret = 1;

        cos_cache_release((cos_cache *)pCache);
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_template_index_bsearch\n");

    return ret;
}

/*
    cos_cache_attr_index_bsearch - RECURSIVE
    ----------------------------------------
    performs a binary search on the cache attribute index
    return -1 if key is not found
    the index into attribute index array of the first occurrance
    of that attribute type otherwise
*/
static int
cos_cache_attr_index_bsearch(const cosCache *pCache, const cosAttributes *key, int lower, int upper)
{
    int ret = -1;
    int index = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_attr_index_bsearch\n");

    if (upper >= lower) {
        if (upper != 0)
            index = ((upper - lower) / 2) + lower;
        else
            index = 0;

        ret = slapi_utf8casecmp((unsigned char *)key->pAttrName, (unsigned char *)(pCache->ppAttrIndex)[index]->pAttrName);
        if (ret == 0) {
            /*
                we have a match, backtrack to the
                first occurrance of this attribute
                type
            */
            do {
                index--;
                if (index >= 0)
                    ret = slapi_utf8casecmp((unsigned char *)key->pAttrName, (unsigned char *)(pCache->ppAttrIndex)[index]->pAttrName);
            } while (index >= 0 && ret == 0);

            index++;
        } else {
            /* seek elsewhere */
            if (ret < 0) {
                /* take the low road */
                index = cos_cache_attr_index_bsearch(pCache, key, lower, index - 1);
            } else {
                /* go high */
                index = cos_cache_attr_index_bsearch(pCache, key, index + 1, upper);
            }
        }
    } else
        index = -1;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_attr_index_bsearch\n");
    return index;
}


static int
cos_cache_cmp_attr(cosAttributes *pAttr, Slapi_Value *test_this, int *result)
{
    int ret = 0;
    int index = 0;
    cosAttrValue *pAttrVal = pAttr->pAttrValue;
    char *the_cmp = (char *)slapi_value_get_string(test_this);

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_cmp_attr\n");

    *result = 0;

    while (pAttrVal) {
        ret = 1; /* CoS attribute exists; return 1 */
        if (!slapi_utf8casecmp((unsigned char *)the_cmp, (unsigned char *)pAttrVal->val)) {
            /* compare match */
            *result = 1;
            break;
        }

        pAttrVal = pAttrVal->list.pNext;
        index++;
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_cmp_attr\n");
    return ret;
}


/*
    cos_cache_cos_2_slapi_attr
    ----------------------
    converts a cosAttributes structure to a Slapi_Attribute
*/
static int
cos_cache_cos_2_slapi_valueset(cosAttributes *pAttr, Slapi_ValueSet **out_vs)
{
    int ret = 0;
    int index = 0;
    cosAttrValue *pAttrVal = pAttr->pAttrValue;
    int add_mode = 0;
    static Slapi_Attr *attr = 0; /* allocated once, never freed */
    static int done_once = 0;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_cos_2_slapi_valueset\n");

    /* test out_vs for existing values */
    if (*out_vs) {
        add_mode = 1;
        if (!done_once) {
            attr = slapi_attr_new(); /* lord knows why this is needed by slapi_valueset_find*/
            slapi_attr_init(attr, "cos-bogus");
            done_once = 1;
        }
    } else
        *out_vs = slapi_valueset_new();

    if (*out_vs) {
        if (!add_mode)
            slapi_valueset_init(*out_vs);

        while (pAttrVal) {
            Slapi_Value *val = slapi_value_new_string(pAttrVal->val);
            if (val) {
                if (!add_mode || !slapi_valueset_find(attr, *out_vs, val)) {
                    slapi_valueset_add_value_ext(*out_vs, val, SLAPI_VALUE_FLAG_PASSIN);
                } else {
                    slapi_value_free(&val);
                }
            } else {
                slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_cos_2_slapi_valueset - "
                                                                   "Memory allocation error\n");
                ret = -1;
                goto bail;
            }

            pAttrVal = pAttrVal->list.pNext;
            index++;
        }
    } else {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_cos_2_slapi_valueset - "
                                                           "Memory allocation error\n");
        ret = -1;
    }

bail:

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_cos_2_slapi_valueset\n");
    return ret;
}


/*
    cos_cache_change_notify
    -----------------------
    determines if the change effects the cache and if so
    signals a rebuild.

    XXXrbyrne This whole mechanism needs to be revisited--it means that
    the modifying client gets his LDAP response, and an unspecified and
    variable
    period of time later, his mods get taken into account in the cos cache.
    This makes it hard to program reliable admin tools for COS--DSAME
    has already indicated this is an issue for them.
    Additionally, it regenerates the _whole_ cache even for eeny weeny mods--
    does it really neeed to ?  Additionally, in order to ensure we
    do not miss any mods, we may tend to regen the cache, even if we've already
    taken a mod into account in an earlier regeneration--currently there is no
    way to know we've already dealt with the mod.
    The right thing is something like: figure out what's being changed
    and change only that in the cos cache and do it _before_ the response
    goes to the client....or do a task that he can poll.
*/
void
cos_cache_change_notify(Slapi_PBlock *pb)
{
    const char *dn;
    Slapi_DN *sdn = NULL;
    int do_update = 0;
    struct slapi_entry *e;
    Slapi_Backend *be = NULL;
    int rc = 0;
    int optype = -1;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_change_notify\n");

    /* Don't update local cache when remote entries are updated. */
    slapi_pblock_get(pb, SLAPI_BACKEND, &be);
    if ((be && (slapi_be_is_flag_set(be, SLAPI_BE_FLAG_REMOTE_DATA))) ||
        (NULL == be)) {
        goto bail;
    }

    /* need to work out if a cache rebuild is necessary */
    if (slapi_pblock_get(pb, SLAPI_TARGET_SDN, &sdn)) {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_change_notify - "
                                                           "Failed to get dn of changed entry\n");
        goto bail;
    }
    dn = slapi_sdn_get_dn(sdn);

    slapi_pblock_get(pb, SLAPI_PLUGIN_OPRETURN, &rc);
    if (0 != rc) {
        /* The operation did not succeed. As far as the cos cache is concerned, no need to update anything */
        goto bail;
    }

    /*
     * For DELETE, MODIFY, MODRDN: see if the pre-op entry was cos significant.
     * For ADD, MODIFY, MODRDN: see if the post-op was cos significant.
     * Touching a cos significant entry triggers the update
     * of the whole cache.
    */
    slapi_pblock_get(pb, SLAPI_OPERATION_TYPE, &optype);
    if (optype == SLAPI_OPERATION_DELETE ||
        optype == SLAPI_OPERATION_MODIFY ||
        optype == SLAPI_OPERATION_MODRDN) {

        slapi_pblock_get(pb, SLAPI_ENTRY_PRE_OP, &e);
        if (cos_cache_entry_is_cos_related(e)) {
            do_update = 1;
        }
    }
    if (!do_update &&
        (optype == SLAPI_OPERATION_ADD ||
         optype == SLAPI_OPERATION_MODIFY ||
         optype == SLAPI_OPERATION_MODRDN)) {

        /* Adds have null pre-op entries */
        slapi_pblock_get(pb, SLAPI_ENTRY_POST_OP, &e);
        if (cos_cache_entry_is_cos_related(e)) {
            do_update = 1;
        }
    }

    /*
     * Check if this was an entry in a template tree (dn contains
     * the old dn value).
     * It's only relevant for indirect templates, which will
     * not usually contain the "objectclass: costemplate" pair
     * and so will not get detected by the above code.
     * In fact, everything would still work fine if
     * we just ignored a mod of one of these indirect templates,
     * as we do not cache values from them, but the advantage of
     * triggering an update here is that
     * we can maintain the invariant that we only ever cache
     * definitions that have _valid_ templates--the active cache
     * stays lean in the face of errors.
    */
    if (!do_update && cos_cache_template_index_bsearch(dn)) {
        slapi_log_err(SLAPI_LOG_PLUGIN, COS_PLUGIN_SUBSYSTEM, "cos_cache_change_notify - "
                                                              "Updating due to indirect template change(%s)\n",
                      dn);
        do_update = 1;
    }

    /* Do the update if required */
    if (do_update) {
        slapi_lock_mutex(change_lock);
        slapi_notify_condvar(something_changed, 1);
        cos_cache_notify_flag = 1;
        slapi_unlock_mutex(change_lock);
    }

bail:
    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_change_notify\n");
}

/*
    cos_cache_stop
    --------------
    notifies the cache thread we are stopping
*/
void
cos_cache_stop(void)
{
    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_stop\n");

    /* first deregister our state change func */
    slapi_unregister_backend_state_change((void *)cos_cache_backend_state_change);

    slapi_lock_mutex(change_lock);
    keeprunning = 0;
    slapi_notify_condvar(something_changed, 1);
    slapi_unlock_mutex(change_lock);

    /* wait on shutdown */
    slapi_lock_mutex(stop_lock);

    /* release the caches reference to the cache */
    cos_cache_release(pCache);
    slapi_destroy_mutex(cache_lock);
    cache_lock = NULL;
    slapi_destroy_mutex(change_lock);
    change_lock = NULL;
    slapi_destroy_condvar(something_changed);
    something_changed = NULL;

    slapi_unlock_mutex(stop_lock);

    slapi_destroy_mutex(stop_lock);
    stop_lock = NULL;
    slapi_destroy_condvar(start_cond);
    start_cond = NULL;
    slapi_destroy_mutex(start_lock);
    start_lock = NULL;

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_stop\n");
}

/*
    cos_cache_backwards_stricmp_and_clip
    ------------------------------------
    compares s2 to s1 starting from end of the strings until the beginning of
    either matches result in the s2 value being clipped from s1 with a NULL char
    and 1 being returned as opposed to 0

*/
static int
cos_cache_backwards_stricmp_and_clip(char *s1, char *s2)
{
    int ret = 0;
    int s1len = 0;
    int s2len = 0;

    s1len = strlen(s1);
    s2len = strlen(s2);

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "--> cos_cache_backwards_stricmp_and_clip - s1 %d s2 %d\n", s1len, s2len);

    if (s1len > s2len && s2len > 0) {
        /* In some cases this can go below 0 causing invalid reads
         * We make the check for > 0, because if we are at 1 -> 0 is next
         * If the check is > -1, we can easily get to 0, then -1, creating invalid read.
         */
        while (s1len > 0 && s2len > 0) {
            s1len--;
            s2len--;

            if (s1[s1len] != s2[s2len])
                break;
            else {
                if (s2len == 0) {
                    /* hit! now clip */
                    ret = 1;
                    s1[s1len] = '\0';
                }
            }
        }
    }

    slapi_log_err(SLAPI_LOG_TRACE, COS_PLUGIN_SUBSYSTEM, "<-- cos_cache_backwards_stricmp_and_clip\n");
    return ret;
}


static int
cos_cache_follow_pointer(vattr_context *c, const char *dn, char *type, Slapi_ValueSet **out_vs, Slapi_Value *test_this, int *result, int flags)
{
    int ret = -1; /* assume failure */
    Slapi_PBlock *pDnSearch = 0;
    Slapi_Entry **pEntryList = 0;
    char *attrs[2];
    int op = 0;
    int type_test = 0;
    int type_name_disposition = 0;
    char *actual_type_name = 0;
    int free_flags = 0;
    Slapi_ValueSet *tmp_vs = 0;

    attrs[0] = type;
    attrs[1] = 0;

    /* Use new internal operation API */
    pDnSearch = slapi_pblock_new();
    if (pDnSearch) {
        slapi_search_internal_set_pb(pDnSearch, dn, LDAP_SCOPE_BASE, "(|(objectclass=*)(objectclass=ldapsubentry))", attrs,
                                     0, NULL, NULL, cos_get_plugin_identity(), 0);
        slapi_search_internal_pb(pDnSearch);
        slapi_pblock_get(pDnSearch, SLAPI_PLUGIN_INTOP_RESULT, &ret);
    }

    if (pDnSearch && (ret == LDAP_SUCCESS)) {
        ret = -1;

        slapi_pblock_get(pDnSearch, SLAPI_PLUGIN_INTOP_SEARCH_ENTRIES, &pEntryList);
        if (pEntryList) {
            if (out_vs) /* if this set, a value is required */
                op = 1;
            else if (test_this && result) /* compare op */
                op = 2;
            else {
                /* requires only type present */
                op = 1;
                type_test = 1;
            }

            switch (op) {
            case 1:
                /* straight value return or type test */
                if (type_test)
                    out_vs = &tmp_vs;

                ret = slapi_vattr_values_get_sp(c, pEntryList[0], type, out_vs, &type_name_disposition, &actual_type_name, flags, &free_flags);

                if (actual_type_name)
                    slapi_ch_free((void **)&actual_type_name);

                if (type_test && free_flags == SLAPI_VIRTUALATTRS_RETURNED_COPIES)
                    slapi_valueset_free(*out_vs);

                break;

            case 2:
                /* this must be a compare op */
                ret = slapi_vattr_value_compare_sp(c, pEntryList[0], type, test_this, result, flags);
                break;
            }
        }
    }

    /* clean up */
    if (pDnSearch) {
        slapi_free_search_results_internal(pDnSearch);
        slapi_pblock_destroy(pDnSearch);
    }

    return ret;
}


/*
 * cos_cache_backend_state_change()
 * --------------------------------
 * This is called when a backend changes state
 * We simply signal to rebuild the cos cache in this case
 *
 */
void
cos_cache_backend_state_change(void *handle __attribute__((unused)),
                               char *be_name __attribute__((unused)),
                               int old_be_state __attribute__((unused)),
                               int new_be_state __attribute__((unused)))
{
    slapi_lock_mutex(change_lock);
    slapi_notify_condvar(something_changed, 1);
    slapi_unlock_mutex(change_lock);
}

/*
 * returns non-zero: entry is cos significant (note does not detect indirect
 *                    template entries).
 *             0       : entry is not cos significant.
 */
static int
cos_cache_entry_is_cos_related(Slapi_Entry *e)
{

    int rc = 0;
    Slapi_Attr *pObjclasses = NULL;

    if (e == NULL) {
        slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_entry_is_cos_related - "
                                                           "Modified entry is NULL--updating cache just in case\n");
        rc = 1;
    } else {

        if (slapi_entry_attr_find(e, "objectclass", &pObjclasses)) {
            slapi_log_err(SLAPI_LOG_ERR, COS_PLUGIN_SUBSYSTEM, "cos_cache_entry_is_cos_related - "
                                                               "Failed to get objectclass from %s\n",
                          slapi_entry_get_dn(e));
            rc = 0;
        } else {

            Slapi_Value *val = NULL;
            int index = 0;
            char *pObj;

            /* check out the object classes to see if this was a cosDefinition */

            index = slapi_attr_first_value(pObjclasses, &val);
            while (!rc && val) {
                pObj = (char *)slapi_value_get_string(val);

                if (!strcasecmp(pObj, "cosdefinition") ||
                    !strcasecmp(pObj, "cossuperdefinition") ||
                    !strcasecmp(pObj, "costemplate")) {
                    rc = 1;
                }

                index = slapi_attr_next_value(pObjclasses, index, &val);
            }
        }
    }
    return (rc);
}