state.c

Go to the documentation of this file.

/*
 *   This program is free software; you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */
 
/**
 * $Id: 0b3cd938948b5a7cc2869ced2426589af28c91e1 $
 *
 * @brief Multi-packet state handling
 * @file src/lib/server/state.c
 *
 * @ingroup AVP
 *
 * For each round of a multi-round authentication method such as EAP,
 * or a 2FA method such as OTP, a state entry will be created.  The state
 * entry holds data that should be available during the complete lifecycle
 * of the authentication attempt.
 *
 * When a request is complete, #fr_state_store is called to transfer
 * ownership of the state fr_pair_ts and state_ctx (which the fr_pair_ts
 * are allocated in) to a #fr_state_entry_t.  This #fr_state_entry_t holds the
 * value of the State attribute, that will be send out in the response.
 *
 * When the next request is received, #fr_state_restore is called to transfer
 * the fr_pair_ts and state ctx to the new request.
 *
 * The ownership of the state_ctx and state fr_pair_ts is transferred as below:
 *
 * @verbatim
   request -> state_entry -> request -> state_entry -> request -> free()
          \-> reply                 \-> reply                 \-> access-reject/access-accept
 * @endverbatim
 *
 * @copyright 2014 The FreeRADIUS server project
 */
RCSID("$Id: 0b3cd938948b5a7cc2869ced2426589af28c91e1 $")
 
#include <freeradius-devel/server/request.h>
#include <freeradius-devel/server/request_data.h>
#include <freeradius-devel/server/state.h>
 
#include <freeradius-devel/io/listen.h>
 
#include <freeradius-devel/util/debug.h>
#include <freeradius-devel/util/md5.h>
#include <freeradius-devel/util/rand.h>
 
const conf_parser_t state_session_config[] = {
        { FR_CONF_OFFSET("timeout", fr_state_config_t, timeout), .dflt = "15" },
        { FR_CONF_OFFSET("max", fr_state_config_t, max_sessions), .dflt = "4096" },
        { FR_CONF_OFFSET("max_rounds", fr_state_config_t, max_rounds), .dflt = "50" },
        { FR_CONF_OFFSET("state_server_id", fr_state_config_t, server_id) },
        { FR_CONF_OFFSET("dedup_key", fr_state_config_t, dedup_key) },
 
        CONF_PARSER_TERMINATOR
};
 
 
/** Holds a state value, and associated fr_pair_ts and data
 *
 */
typedef struct {
        uint64_t                id;                             //!< State number
        fr_rb_node_t            node;                           //!< Entry in the state rbtree.
        union {
                /** Server ID components
                 *
                 * State values should be unique to a given server
                 */
                struct state_comp {
                        uint8_t         tries;                  //!< Number of rounds so far in this state sequence.
                        uint8_t         tx;                     //!< Bits changed in the tries counter for this round.
                        uint8_t         r_0;                    //!< Random component.
                        uint8_t         server_id;              //!< Configured server ID.  Used for debugging
                                                                //!< to locate authentication sessions originating
                                                                //!< from a particular backend authentication server.
 
                        uint32_t        context_id;             //!< Hash of the current virtual server, xor'd with
                                                                //!< r1, r2, r3, r4 after the original state value
                                                                //!< is sent, but before the state entry is inserted
                                                                //!< into the tree.  The receiving virtual server
                                                                //!< xor's its hash with the received state before
                                                                //!< performing the lookup.  This means one virtual
                                                                //!< server can't act on a state entry generated by
                                                                //!< another, even though the state tree is global
                                                                //!< to all virtual servers.
 
                        uint8_t         vx_0;                   //!< Random component.
                        uint8_t         r_1;                    //!< Random component.
                        uint8_t         vx_1;                   //!< Random component.
                        uint8_t         r_2;                    //!< Random component.
 
                        uint8_t         vx_2;                   //!< Random component.
                        uint8_t         vx_3;                   //!< Random component.
                        uint8_t         r_3;                    //!< Random component.
                        uint8_t         r_4;                    //!< Random component.
                } state_comp;
 
                uint8_t         state[sizeof(struct state_comp)];       //!< State value in binary.
        };
 
        uint64_t                seq_start;                      //!< Number of first request in this sequence.
        fr_time_t               cleanup;                        //!< When this entry should be cleaned up.
 
        /*
         *      Should only even be in one at a time
         */
        union {
                fr_dlist_t              expire_entry;           //!< Entry in the list of things to expire.
                fr_dlist_t              free_entry;             //!< Entry in the list of things to free.
        };
 
        unsigned int            tries;
 
        fr_pair_t               *ctx;                           //!< for all session specific data.
 
        fr_dlist_head_t         data;                           //!< Persistable request data, also parented by ctx.
 
        request_t               *thawed;                        //!< The request that thawed this entry.
 
        fr_value_box_t const    *dedup_key;                     //!< Key for dedup
        fr_rb_node_t            dedup_node;                     //!< Entry in the dedup rbtree
} fr_state_entry_t;
 
/** A child of a fr_state_entry_t
 *
 * Children are tracked using the request data of parents.
 *
 * request data is added with identifiers that uniquely identify the
 * subrequest it should be restored to.
 *
 * In this way a top level fr_state_entry_t can hold the session
 * information for multiple children, and the children may hold
 * state_child_entry_ts for grandchildren.
 */
typedef struct {
        fr_pair_t               *ctx;                           //!< for all session specific data.
 
        fr_dlist_head_t         data;                           //!< Persistable request data, also parented by ctx.
 
        request_t               *thawed;                        //!< The request that thawed this entry.
} state_child_entry_t;
 
struct fr_state_tree_s {
        uint64_t                id;                             //!< Next ID to assign.
        uint64_t                timed_out;                      //!< Number of states that were cleaned up due to
                                                                //!< timeout.
        fr_state_config_t       config;                         //!< a local copy
 
        fr_rb_tree_t            *tree;                          //!< rbtree used to lookup state value.
        fr_rb_tree_t            *dedup_tree;                    //!< rbtree used to do dedups
        fr_dlist_head_t         to_expire;                      //!< Linked list of entries to free.
 
        pthread_mutex_t         mutex;                          //!< Synchronisation mutex.
 
        fr_dict_attr_t const    *da;                            //!< Attribute where the state is stored.
};
 
#define PTHREAD_MUTEX_LOCK if (state->config.thread_safe) pthread_mutex_lock
#define PTHREAD_MUTEX_UNLOCK if (state->config.thread_safe) pthread_mutex_unlock
 
static void state_entry_unlink(fr_state_tree_t *state, fr_state_entry_t *entry);
 
/** Compare two fr_state_entry_t based on their state value i.e. the value of the attribute
 *
 */
static fr_cmp_ret_t state_entry_cmp(void const *one, void const *two)
{
        fr_state_entry_t const *a = one, *b = two;
        int ret;
 
        ret = memcmp(a->state, b->state, sizeof(a->state));
        return CMP(ret, 0);
}
 
/** Compare two fr_state_entry_t based on their dedup key
 *
 */
static fr_cmp_ret_t state_dedup_cmp(void const *one, void const *two)
{
        fr_state_entry_t const *a = one, *b = two;
 
        return fr_value_box_cmp(a->dedup_key, b->dedup_key);
}
 
 
/** Free the state tree
 *
 */
static int _state_tree_free(fr_state_tree_t *state)
{
        fr_state_entry_t *entry;
 
        if (state->config.thread_safe) pthread_mutex_destroy(&state->mutex);
 
        DEBUG4("Freeing state tree %p", state);
 
        while ((entry = fr_dlist_head(&state->to_expire)) != NULL) {
                state_entry_unlink(state, entry);
                DEBUG4("Freeing state entry %p (%" PRIu64 ")", entry, entry->id);
                talloc_free(entry);
        }
 
        /*
         *      Free the rbtree
         */
        talloc_free(state->tree);
 
        return 0;
}
 
/** Initialise a new state tree
 *
 * @param[in] ctx               to link the lifecycle of the state tree to.
 * @param[in] da                Attribute used to store and retrieve state from.
 * @param[in] config            the configuration data
 * @return
 *      - A new state tree.
 *      - NULL on failure.
 */
fr_state_tree_t *fr_state_tree_init(TALLOC_CTX *ctx, fr_dict_attr_t const *da, fr_state_config_t const *config)
{
        fr_state_tree_t *state;
 
        /*
         *      We can only handle 'octets' types.
         */
        if (da->type != FR_TYPE_OCTETS) {
                fr_strerror_printf("Input state attribute '%s' has data type %s instead of 'octets'",
                                   da->name, fr_type_to_str(da->type));
                return NULL;
        }
 
        state = talloc_zero(NULL, fr_state_tree_t);
        if (!state) return 0;
 
        state->config = *config;
        state->da = da;         /* Remember which attribute we use to load/store state */
 
        /*
         *      Some systems may start a new session before closing
         *      out the old one.  The dedup key lets us find
         *      pre-existing sessions, and close them out.
         */
        if (config->dedup_key) {
                if ((!tmpl_is_attr(config->dedup_key) &&
                     !tmpl_is_xlat(config->dedup_key)) ||
                    tmpl_needs_resolving(config->dedup_key)) {
                        fr_strerror_const("Invalid value for \"dedup_key\" - it must be an attribute reference or a simple expansion");
                        talloc_free(state);
                        return NULL;
                }
 
                if (tmpl_async_required(config->dedup_key)) {
                        fr_strerror_const("Invalid value for \"dedup_key\" - it must be a simple expansion, and cannot query external systems such as databases");
                        talloc_free(state);
                        return NULL;
                }
        }
 
        /*
         *      Create a break in the contexts.
         *      We still want this to be freed at the same time
         *      as the parent, but we also need it to be thread
         *      safe, and multiple threads could be using the
         *      tree.
         */
        talloc_link_ctx(ctx, state);
 
        if (state->config.thread_safe && (pthread_mutex_init(&state->mutex, NULL) != 0)) {
                talloc_free(state);
                return NULL;
        }
 
        fr_dlist_talloc_init(&state->to_expire, fr_state_entry_t, free_entry);
 
        /*
         *      We need to do controlled freeing of the
         *      rbtree, so that all the state entries
         *      are freed before it's destroyed.  Hence
         *      it being parented from the NULL ctx.
         */
        state->tree = fr_rb_inline_talloc_alloc(NULL, fr_state_entry_t, node, state_entry_cmp, NULL);
        if (!state->tree) {
                talloc_free(state);
                return NULL;
        }
        talloc_set_destructor(state, _state_tree_free);
 
        if (config->dedup_key) {
                state->dedup_tree = fr_rb_inline_talloc_alloc(state->tree, fr_state_entry_t, dedup_node, state_dedup_cmp, NULL);
                if (!state->dedup_tree) {
                        talloc_free(state);
                        return NULL;
                }
        }
 
        return state;
}
 
/** Unlink an entry and remove if from the tree
 *
 */
static inline CC_HINT(always_inline)
void state_entry_unlink(fr_state_tree_t *state, fr_state_entry_t *entry)
{
        /*
         *      Check the memory is still valid
         */
        (void) talloc_get_type_abort(entry, fr_state_entry_t);
 
        fr_dlist_remove(&state->to_expire, entry);
        fr_rb_delete(state->tree, entry);
        if (state->dedup_tree) fr_rb_delete(state->dedup_tree, entry);
 
        DEBUG4("State ID %" PRIu64 " unlinked", entry->id);
}
 
/** Frees any data associated with a state
 *
 */
static int _state_entry_free(fr_state_entry_t *entry)
{
#ifdef WITH_VERIFY_PTR
        fr_dcursor_t cursor;
        fr_pair_t *vp;
 
        /*
         *      Verify all state attributes are parented
         *      by the state context.
         */
        if (entry->ctx) {
                for (vp = fr_pair_dcursor_init(&cursor, &entry->ctx->children);
                     vp;
                     vp = fr_dcursor_next(&cursor)) {
                        fr_assert(entry->ctx == talloc_parent(vp));
                }
        }
 
        /*
         *      Ensure any request data is parented by us
         *      so we know it'll be cleaned up.
         */
        (void)fr_cond_assert(request_data_verify_parent(entry->ctx, &entry->data));
#endif
 
        /*
         *      Should also free any state attributes
         */
        if (entry->ctx) TALLOC_FREE(entry->ctx);
 
        DEBUG4("State ID %" PRIu64 " freed", entry->id);
 
        return 0;
}
 
static void state_entry_fill(fr_state_entry_t *entry, fr_value_box_t const *vb)
{
 
        uint64_t hash;
 
        /*
         *      Use the supplied State if it's the correct size.
         */
        if (vb->vb_length == sizeof(entry->state)) {
                memcpy(&entry->state, vb->vb_octets, vb->vb_length);
                return;
        }
 
        /*
         *      Otherwise hash the data.
         */
        memset(&entry->state, 0, sizeof(entry->state));
 
        hash = fr_hash64(vb->vb_octets, vb->vb_length);
        memcpy(&entry->state, &hash, sizeof(hash));
}
 
/** Create a new state entry
 *
 * @note Called with the mutex held.
 */
static fr_state_entry_t *state_entry_create(fr_state_tree_t *state, request_t *request,
                                            fr_pair_list_t *reply_list, fr_state_entry_t *old,
                                            fr_value_box_t const *dedup_key)
{
        fr_time_t               now = fr_time();
        fr_pair_t               *vp;
        fr_state_entry_t        *entry;
 
        uint64_t                timed_out = 0;
        bool                    too_many = false;
        fr_dlist_head_t         to_free;
 
        /*
         *      If we have a previous entry, then it can't be in an
         *      expiry list, and it can't be in the list of states
         *      where we have sent a reply.
         */
        fr_assert(!old ||
                  (!fr_dlist_entry_in_list(&old->expire_entry) &&
                   !fr_rb_node_inline_in_tree(&old->node)));
 
        /*
         *      If we have a previous entry and a dedup_tree, then we
         *      must have a dedup key, AND the entry must be in the
         *      dedup tree.
         */
        fr_assert(!old || !state->dedup_tree || (old->dedup_key && fr_rb_node_inline_in_tree(&old->dedup_node)));
 
        /*
         *      If there is an old entry, we can't have a dedup_key.
         */
        fr_assert(!old || !dedup_key);
 
        /*
         *      We track a separate free list, as we have to check
         *      expiration with the mutex locked.  But we want to free
         *      things with the mutex unlocked.
         */
        fr_dlist_init(&to_free, fr_state_entry_t, free_entry);
 
        /*
         *      Clean up expired entries which have not finished.  If
         *      the request fails, then the corresponding entry is
         *      discarded.  So the expiration list is only for entries
         *      which have been half-started, and then (many seconds
         *      later) haven't seen a "next" packet.
         */
        fr_dlist_foreach(&state->to_expire, fr_state_entry_t, expires) {
                (void)talloc_get_type_abort(expires, fr_state_entry_t); /* Allow examination */
 
                /*
                 *      It's active (and asserted so above), so it can't be in the expiry list.
                 */
                fr_assert(expires != old);
 
                /*
                 *      Too old, we can delete it.
                 */
                if (fr_time_lt(expires->cleanup, now)) {
                        state_entry_unlink(state, expires);
                        fr_dlist_insert_tail(&to_free, expires);
                        timed_out++;
                        continue;
                }
 
                break;
        }
 
        if (!old) {
                /*
                 *      We're inserting a new session.  Limit the
                 *      number of sessions based on how many are in
                 *      the RB tree.  If at least one session has
                 *      timed out, then we can definitely add a new
                 *      session.
                 *
                 *      Note that sessions being processed are removed
                 *      from the tree.  This means that the maximum
                 *      number of sessions might actually be
                 *      max_session+num_workers.  In practice this
                 *      shouldn't be a problem.
                 */
                too_many = (fr_rb_num_elements(state->tree) >= state->config.max_sessions) && (timed_out == 0);
 
                /*
                 *      If there is a previous session for the same dedup key, then remove the old one from
                 *      the dedup tree.
                 */
                if (dedup_key) {
                        fr_state_entry_t *unfinished;
 
                        /*
                         *      A comparator error means we can't tell whether a
                         *      previous session exists.  The insert into the dedup
                         *      tree below fails for the same reason, refusing the
                         *      new entry, so here we only report.
                         */
                        if (unlikely(fr_rb_find((void **)&unfinished, state->dedup_tree,
                                                &(fr_state_entry_t) { .dedup_key = dedup_key }) < 0)) {
                                RPEDEBUG("Failed checking for an existing session with the same dedup_key");
                        } else if (unfinished) {
                                state_entry_unlink(state, unfinished);
                                fr_dlist_insert_tail(&to_free, unfinished);
                        }
                }
        }
 
        PTHREAD_MUTEX_UNLOCK(&state->mutex);
 
        if (timed_out > 0) {
                RWDEBUG("Cleaning up %"PRIu64" timed out state entries", timed_out);
                state->timed_out += timed_out;
 
                /*
                 *      Now free the unlinked entries.
                 *
                 *      We do it here as freeing may involve significantly more
                 *      work than just freeing the data.
                 *
                 *      If there's request data that was persisted it will now
                 *      be freed also, and it may have complex destructors associated
                 *      with it.
                 */
                fr_dlist_talloc_free(&to_free);
 
        } else if (too_many) {
                talloc_const_free(dedup_key);
                RERROR("Failed inserting state entry - At maximum ongoing session limit (%u)",
                       state->config.max_sessions);
                return NULL;
        }
 
        /*
         *      Allocation doesn't need to occur inside the critical region
         *      and would add significantly to contention.
         */
        if (!old) {
                MEM(entry = talloc_zero(NULL, fr_state_entry_t));
                talloc_set_destructor(entry, _state_entry_free);
 
                entry->id = state->id++;
 
        } else {
                fr_assert(!old->ctx);
                entry = old;
        }
 
        request_data_list_init(&entry->data);
 
        /*
         *      Limit the lifetime of this entry based on how long the
         *      server takes to process a request.  Doing it this way
         *      isn't perfect, but it's reasonable, and it's one less
         *      thing for an administrator to configure.
         */
        entry->cleanup = fr_time_add(now, state->config.timeout);
 
        /*
         *      Some modules either create their own state, or need to
         *      synthesize it from data in a packet header.  If we
         *      have such a state, then use that in preference to
         *      creating a random one.
         */
        vp = fr_pair_find_by_da(reply_list, NULL, state->da);
        if (vp && vp->vp_length) {
                state_entry_fill(entry, &vp->data);
 
        } else {
                if (old) {
                        /*
                         *      Just re-use the old state.
                         */
                        entry->tries++;
 
                        if (entry->tries > state->config.max_rounds) {
                                RERROR("Failed tracking state entry - too many rounds (%u)", entry->tries);
                                goto fail;
                        }
                } else {
                        size_t i;
                        uint32_t hash;
 
                        if (dedup_key) entry->dedup_key = talloc_steal(entry, dedup_key);
 
                        /*
                         *      Get a bunch of random numbers.
                         */
                        for (i = 0; i < sizeof(entry->state); i+= 4) {
                                hash = fr_rand();
                                memcpy(&entry->state[i], &hash, sizeof(hash));
                        }
 
                        /*
                         *      Add in a server ID.  This lets a "FreeRADIUS
                         *      aware" load balancer direct the packet based
                         *      on the contents of the State attribute.
                         */
                        entry->state_comp.server_id = state->config.server_id;
 
                        /*
                         *      Add our own custom brand of magic.
                         */
                        entry->state_comp.vx_0 = entry->state_comp.r_0 ^
                                ((((uint32_t) HEXIFY(RADIUSD_VERSION)) >> 24) & 0xff);
                        entry->state_comp.vx_1 = entry->state_comp.r_0 ^
                                ((((uint32_t) HEXIFY(RADIUSD_VERSION)) >> 16) & 0xff);
                        entry->state_comp.vx_2 = entry->state_comp.r_0 ^
                                ((((uint32_t) HEXIFY(RADIUSD_VERSION)) >> 8) & 0xff);
                        entry->state_comp.vx_3 = entry->state_comp.r_0 ^
                                (((uint32_t) HEXIFY(RADIUSD_VERSION)) & 0xff);
                }
 
                /*
                 *      Track the number of round trips, too.
                 */
                entry->state_comp.tx ^= entry->tries;
                entry->state_comp.tries = entry->tries ^ entry->state_comp.r_3;
 
                MEM(vp = fr_pair_afrom_da(request->reply_ctx, state->da));
                fr_pair_value_memdup(vp, entry->state, sizeof(entry->state), false);
                fr_pair_append(reply_list, vp);
        }
 
        DEBUG4("State ID %" PRIu64 " created, value 0x%pH, expires %pV",
               entry->id, &vp->data,
               fr_box_time_delta(fr_time_sub(entry->cleanup, now)));
 
        /*
         *      XOR the server hash with four bytes of random context
         *      ID after adding it to the reply, but before inserting
         *      it into the RB rtree.  We XOR is again before looking
         *      it up in the tree, to ensure state lookups only
         *      succeed in the virtual server that created the state
         *      value.
         */
        entry->state_comp.context_id ^= state->config.context_id;
 
        PTHREAD_MUTEX_LOCK(&state->mutex);
 
        if (fr_rb_insert(state->tree, entry) != 0) {
        fail_unlock:
                PTHREAD_MUTEX_UNLOCK(&state->mutex);
                RERROR("Failed inserting state entry - Insertion into state tree failed");
        fail:
                fr_pair_delete_by_da(reply_list, state->da);
                talloc_free(entry);
                return NULL;
        }
 
        /*
         *      Ensure that we can de-duplicate things if the supplicant is misbehaving.
         */
        if (state->dedup_tree && !old) {
                if (fr_rb_insert(state->dedup_tree, entry) != 0) {
                        (void) fr_rb_remove(NULL, state->tree, entry);
                        goto fail_unlock;
                }
        }
 
        /*
         *      Link it to the end of the list, which is implicitly
         *      ordered by cleanup time.
         */
        fr_dlist_insert_tail(&state->to_expire, entry);
 
        entry->thawed = NULL;
 
        return entry;
}
 
/** Find the entry based on the State attribute and remove it from the state tree
 *
 */
static fr_state_entry_t *state_entry_find_and_unlink(fr_state_tree_t *state, fr_value_box_t const *vb)
{
        fr_state_entry_t *entry, my_entry;
 
        state_entry_fill(&my_entry, vb);
 
        /*
         *      Make it unique for different virtual servers handling the same request
         */
        my_entry.state_comp.context_id ^= state->config.context_id;
 
        fr_rb_remove((void **)&entry, state->tree, &my_entry);
        if (entry) {
                (void) talloc_get_type_abort(entry, fr_state_entry_t);
                fr_dlist_remove(&state->to_expire, entry);
        }
 
        return entry;
}
 
 
/** Called when sending an Access-Accept/Access-Reject to discard state information
 *
 * @param[in] state     tree to lookup state in.
 * @param[in] request   to discard state for.
 */
void fr_state_discard(fr_state_tree_t *state, request_t *request)
{
        fr_state_entry_t        *entry;
 
        /*
         *      The caller MUST have called fr_state_restore() before
         *      calling this function.  If so, there is request data
         *      that points to the state entry.
         *
         *      This function should only be called from the "outer"
         *      request.  Any child request should call
         *      fr_state_discard_child()
         *
         *      Relying on request data also means that the user can
         *      nuke request.State, and the code will still work.
         *
         *      Find a pointer to the entry, but leave the request
         *      data associated with the entry.  That way when the
         *      request is freed, the entry will also be freed.
         */
        entry = request_data_reference(request, state, 0);
        if (!entry) return;
 
        /*
         *      Unlink the entry to shrink the state tree, and make
         *      sure that the state is never re-used.
         *
         *      However, we don't wipe the session-state list, as the
         *      request can still be processed through a "finally"
         *      section.  And we want the session state data to be
         *      usable from there.
         */
        PTHREAD_MUTEX_LOCK(&state->mutex);
        state_entry_unlink(state, entry);
        PTHREAD_MUTEX_UNLOCK(&state->mutex);
 
        return;
}
 
/** Called to discard a state which is synthesized
 *
 *  Some protocols synthesize a state, which means that there is the
 *  possibility for conflict.  i.e. an old state exists which needs to
 *  be discarded.  The current request can't restore the old state, it
 *  instead needs to discard it.
 *
 * @param[in] state     tree to lookup state in.
 * @param[in] request   to discard state for.
 */
void fr_state_discard_by_state(fr_state_tree_t *state, request_t *request)
{
        fr_pair_t               *vp;
        fr_state_entry_t        *entry;
 
        vp = fr_pair_find_by_da(&request->request_pairs, NULL, state->da);
        if (!vp) return;
 
        PTHREAD_MUTEX_LOCK(&state->mutex);
        entry = state_entry_find_and_unlink(state, &vp->data);
        PTHREAD_MUTEX_UNLOCK(&state->mutex);
 
        if (entry) talloc_free(entry);
}
 
/** Copy a pointer to the head of the list of state fr_pair_ts (and their ctx) into the request
 *
 * @note Does not copy the actual fr_pair_ts.  The fr_pair_ts and their context
 *      are transferred between state entries as the conversation progresses.
 *
 * @note Called with the mutex free.
 *
 * @param[in] state     tree to lookup state in.
 * @param[in] request   to restore state for.
 * @return
 *      - 2 if the state attribute didn't match any known states.
 *      - 1 if no state attribute existed.
 *      - 0 on success (state restored)
 *      - -1 if a state entry has already been thawed by a another request.
 */
int fr_state_restore(fr_state_tree_t *state, request_t *request)
{
        fr_state_entry_t        *entry;
        fr_pair_t               *vp;
 
        /*
         *      No State, don't do anything.
         */
        vp = fr_pair_find_by_da(&request->request_pairs, NULL, state->da);
        if (!vp) {
                RDEBUG3("No request.%s attribute, can't restore session-state", state->da->name);
                if (request->seq_start == 0) request->seq_start = request->number;      /* Need check for fake requests */
                return 1;
        }
 
        PTHREAD_MUTEX_LOCK(&state->mutex);
        entry = state_entry_find_and_unlink(state, &vp->data);
        PTHREAD_MUTEX_UNLOCK(&state->mutex);
        if (!entry) {
                RDEBUG2("No state entry matching request.%pP found", vp);
                return 2;
        }
 
        /* Probably impossible in the current code */
        if (unlikely(entry->thawed && (entry->thawed != request))) {
                RERROR("State entry has already been thawed by a request %"PRIu64, entry->thawed->number);
                return -2;
        }
 
        /*
         *      Discard any existing session state, and replace it
         *      with the cached one.
         */
        fr_assert(entry->ctx);
        talloc_free(request_state_replace(request, entry->ctx));
        entry->ctx = NULL;
 
        request->seq_start = entry->seq_start;
 
        /*
         *      Associate old state with the request
         *
         *      If the request is freed, it's freed immediately.
         *
         *      Otherwise, if there's another round, we reuse
         *      the state entry and insert it back into the
         *      tree.
         */
        request_data_add(request, state, 0, entry, true, true, false);
        request_data_restore(request, &entry->data);
 
        entry->thawed = request;
 
        if (!fr_pair_list_empty(&request->session_state_pairs)) {
                RDEBUG2("Restored session-state");
                log_request_pair_list(L_DBG_LVL_2, request, NULL, &request->session_state_pairs, "session-state.");
        }
 
        RDEBUG3("%s - restored", state->da->name);
 
        /*
         *      Set sequence so that we can prioritize ongoing multi-packet sessions.
         */
        request->sequence = entry->tries;
        REQUEST_VERIFY(request);
        return 0;
}
 
 
/** Transfer ownership of the state fr_pair_ts and ctx, back to a state entry
 *
 * Put request->session_state_pairs into the State attribute.  Put the State attribute
 * into the vps list.  Delete the original entry, if it exists
 *
 * Also creates a new state entry.
 */
int fr_state_store(fr_state_tree_t *state, request_t *request)
{
        fr_state_entry_t        *entry, *old;
        fr_dlist_head_t         data;
        fr_pair_t               *state_ctx;
        fr_value_box_t          *dedup_key = NULL;
 
        old = request_data_get(request, state, 0);
        request_data_list_init(&data);
        request_data_by_persistance(&data, request, true);
 
        if (fr_pair_list_empty(&request->session_state_pairs) && fr_dlist_empty(&data)) return 0;
 
        if (!fr_pair_list_empty(&request->session_state_pairs)) {
                RDEBUG2("Saving session-state");
                log_request_pair_list(L_DBG_LVL_2, request, NULL, &request->session_state_pairs, "session-state.");
 
#ifdef WITH_VERIFY_PTR
                /*
                 *      Double check all the session state pairs
                 *      are parented correctly, else we'll get
                 *      memory errors when we restore.
                 */
                fr_pair_list_verify(__FILE__, __LINE__, request->session_state_ctx, &request->session_state_pairs, true);
#endif
        }
 
        /*
         *      If there's a dedup tree, then we need to expand the
         *      key, but only if we don't already have a pre-existing state.
         */
        if (state->dedup_tree && !old) {
                fr_value_box_list_t list;
 
                fr_value_box_list_init(&list);
 
                if (tmpl_eval(NULL, &list, request, state->config.dedup_key) < 0) {
                        REDEBUG("Failed expanding dedup_key - not doing dedup");
                } else {
                        dedup_key = fr_value_box_list_pop_head(&list);
                        if (!dedup_key) {
                                RDEBUG("Failed expanding dedup_key - not doing dedup due to empty output");
                        }
                        fr_value_box_list_talloc_free_head(&list);
                }
        }
 
        MEM(state_ctx = request_state_replace(request, NULL));
 
        /*
         *      Reuses old if possible, and leaves the mutex unlocked on failure.
         */
        PTHREAD_MUTEX_LOCK(&state->mutex);
        entry = state_entry_create(state, request, &request->reply_pairs, old, dedup_key);
        if (!entry) {
                talloc_free(request_state_replace(request, state_ctx));
                request_data_restore(request, &data);   /* Put it back again */
 
#ifdef __COVERITY__
                /*
                 *  Coverity doesn't see that state_entry_create releases
                 *  the lock on failure
                 */
                PTHREAD_MUTEX_UNLOCK(&state->mutex)
#endif
                return -1;
        }
 
        fr_assert(entry->ctx == NULL);
        fr_assert(request->session_state_ctx);
 
        entry->seq_start = request->seq_start;
        entry->ctx = state_ctx;
        fr_dlist_move(&entry->data, &data);
        PTHREAD_MUTEX_UNLOCK(&state->mutex);
 
        RDEBUG3("%s - saved", state->da->name);
        REQUEST_VERIFY(request);
 
        return 0;
}
 
/** Free any subrequest request data if the dlist head is freed
 *
 */
static int _free_child_data(state_child_entry_t *child_entry)
{
        fr_dlist_talloc_free(&child_entry->data);
        talloc_free(child_entry->ctx);          /* Free the child's session_state_ctx if we own it */
 
        return 0;
}
 
/** Store subrequest's session-state list and persistable request data in its parent
 *
 * @param[in] child             The child request to retrieve state from.
 * @param[in] unique_ptr        A parent may have multiple subrequests spawned
 *                              by different modules.  This identifies the module
 *                              or other facility that spawned the subrequest.
 * @param[in] unique_int        Further identification.
 */
void fr_state_store_in_parent(request_t *child, void const *unique_ptr, int unique_int)
{
        state_child_entry_t     *child_entry;
        request_t               *request = child; /* Stupid logging */
 
        if (!fr_cond_assert_msg(child->parent,
                                "Child request must have request->parent set when storing state")) return;
 
        RDEBUG3("Storing subrequest state in request %s", child->parent->name);
 
        if ((request_data_by_persistance_count(request, true) > 0) ||
                !fr_pair_list_empty(&request->session_state_pairs)) {
                MEM(child_entry = talloc_zero(request->parent->session_state_ctx, state_child_entry_t));
                request_data_list_init(&child_entry->data);
                talloc_set_destructor(child_entry, _free_child_data);
 
                child_entry->ctx = request_state_replace(child, NULL);
 
                /*
                 *      Pull everything out of the child,
                 *      add it to our temporary list head...
                 *
                 *      request_data_add allocs persistable
                 *      request dta in the session_state_ctx
                 *      which is why we don't need to copy or
                 *      reparent any of this.
                 */
                request_data_by_persistance(&child_entry->data, request, true);
 
                /*
                 *      ...and add the request_data from
                 *      the child back into the parent.
                 */
                request_data_talloc_add(request->parent, unique_ptr, unique_int,
                                        state_child_entry_t, child_entry, true, false, true);
        }
}
 
/** Restore subrequest data from a parent request
 *
 * @param[in] child             The child request to restore state to.
 * @param[in] unique_ptr        A parent may have multiple subrequests spawned
 *                              by different modules.  This identifies the module
 *                              or other facility that spawned the subrequest.
 * @param[in] unique_int        Further identification.
 */
void fr_state_restore_from_parent(request_t *child, void const *unique_ptr, int unique_int)
{
        state_child_entry_t     *child_entry;
        request_t               *request = child; /* Stupid logging */
 
        if (!fr_cond_assert_msg(child->parent,
                                "Child request must have request->parent set when restoring state")) return;
 
 
        child_entry = request_data_get(child->parent, unique_ptr, unique_int);
        if (!child_entry) {
                RDEBUG3("No child state found in parent %s", child->parent->name);
                return;
        }
 
        /*
         *      Shouldn't really be possible unless
         *      there's a logic bug in this API.
         */
        if (!fr_cond_assert_msg(!child_entry->thawed,
                                "Child state entry already thawed by %s - %p",
                                child_entry->thawed->name, child_entry->thawed)) return;
 
        RDEBUG3("Restoring subrequest state from request %s", child->parent->name);
 
        /*
         *      If we can restore from the parent, do so
         */
        fr_assert_msg(child_entry->ctx, "session child entry missing ctx");
        talloc_free(request_state_replace(child, child_entry->ctx));
        child_entry->ctx = NULL;                                /* No longer owns the ctx */
        child_entry->thawed = child;
 
        request_data_restore(child, &child_entry->data);        /* Put all the request data back */
 
        talloc_free(child_entry);
}
 
/** Remove state from a child
 *
 * This is useful for modules like EAP, where we keep a persistent eap_session
 * but may call multiple EAP method modules during negotiation, and need to
 * discard the state between each module call.
 *
 * @param[in] parent            Holding the child's state.
 * @param[in] unique_ptr        A parent may have multiple subrequests spawned
 *                              by different modules.  This identifies the module
 *                              or other facility that spawned the subrequest.
 * @param[in] unique_int        Further identification.
 */
void fr_state_discard_child(request_t *parent, void const *unique_ptr, int unique_int)
{
        state_child_entry_t     *child_entry;
        request_t               *request = parent; /* Stupid logging */
 
        child_entry = request_data_get(parent, unique_ptr, unique_int);
        if (!child_entry) {
                RDEBUG3("No child state found in parent %s", parent->name);
                return;
        }
 
        talloc_free(child_entry);
}