/*-
 * Copyright (c) 2015-2016 Landon Fuller <landonf@FreeBSD.org>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer,
 *    without modification.
 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
 *    similar to the "NO WARRANTY" disclaimer below ("Disclaimer") and any
 *    redistribution must be conditioned upon including a substantially
 *    similar Disclaimer requirement for further binary redistribution.
 *
 * NO WARRANTY
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF NONINFRINGEMENT, MERCHANTIBILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
 * THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY,
 * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGES.
 */

#include <sys/param.h>
#include <sys/hash.h>
#include <sys/queue.h>

#ifdef _KERNEL

#include <sys/ctype.h>
#include <sys/systm.h>

#include <machine/_inttypes.h>

#else /* !_KERNEL */

#include <ctype.h>
#include <errno.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#endif /* _KERNEL */

#include "bhnd_nvram_private.h"
#include "bhnd_nvram_datavar.h"

#include "bhnd_nvram_storevar.h"

static int bhnd_nvstore_idx_cmp(const void *lhs, const void *rhs, void *ctx);

/**
 * Allocate and initialize a new path instance.
 * 
 * The caller is responsible for deallocating the instance via
 * bhnd_nvstore_path_free().
 * 
 * @param       path_str        The path's canonical string representation.
 * @param       path_len        The length of @p path_str.
 * 
 * @retval non-NULL     success
 * @retval NULL         if allocation fails.
 */
bhnd_nvstore_path *
bhnd_nvstore_path_new(const char *path_str, size_t path_len)
{
        bhnd_nvstore_path *path;

        /* Allocate new entry */
        path = bhnd_nv_malloc(sizeof(*path));
        if (path == NULL)
                return (NULL);

        path->index = NULL;
        path->num_vars = 0;

        path->pending = bhnd_nvram_plist_new();
        if (path->pending == NULL)
                goto failed;

        path->path_str = bhnd_nv_strndup(path_str, path_len);
        if (path->path_str == NULL)
                goto failed;

        return (path);

failed:
        if (path->pending != NULL)
                bhnd_nvram_plist_release(path->pending);

        if (path->path_str != NULL)
                bhnd_nv_free(path->path_str);

        bhnd_nv_free(path);

        return (NULL);
}

/**
 * Free an NVRAM path instance, releasing all associated resources.
 */
void
bhnd_nvstore_path_free(struct bhnd_nvstore_path *path)
{
        /* Free the per-path index */
        if (path->index != NULL)
                bhnd_nvstore_index_free(path->index);

        bhnd_nvram_plist_release(path->pending);
        bhnd_nv_free(path->path_str);
        bhnd_nv_free(path);
}

/**
 * Allocate and initialize a new index instance with @p capacity.
 * 
 * The caller is responsible for deallocating the instance via
 * bhnd_nvstore_index_free().
 * 
 * @param       capacity        The maximum number of variables to be indexed.
 * 
 * @retval non-NULL     success
 * @retval NULL         if allocation fails.
 */
bhnd_nvstore_index *
bhnd_nvstore_index_new(size_t capacity)
{
        bhnd_nvstore_index      *index;
        size_t                   bytes;

        /* Allocate and populate variable index */
        bytes = sizeof(struct bhnd_nvstore_index) + (sizeof(void *) * capacity);
        index = bhnd_nv_malloc(bytes);
        if (index == NULL) {
                BHND_NV_LOG("error allocating %zu byte index\n", bytes);
                return (NULL);
        }

        index->count = 0;
        index->capacity = capacity;

        return (index);
}

/**
 * Free an index instance, releasing all associated resources.
 * 
 * @param       index   An index instance previously allocated via
 *                      bhnd_nvstore_index_new().
 */
void
bhnd_nvstore_index_free(bhnd_nvstore_index *index)
{
        bhnd_nv_free(index);
}

/**
 * Append a new NVRAM variable's @p cookiep value to @p index.
 * 
 * After one or more append requests, the index must be prepared via
 * bhnd_nvstore_index_prepare() before any indexed lookups are performed.
 *
 * @param       sc      The NVRAM store from which NVRAM values will be queried.
 * @param       index   The index to be modified.
 * @param       cookiep The cookiep value (as provided by the backing NVRAM
 *                      data instance of @p sc) to be included in @p index.
 * 
 * @retval 0            success
 * @retval ENOMEM       if appending an additional entry would exceed the
 *                      capacity of @p index.
 */
int
bhnd_nvstore_index_append(struct bhnd_nvram_store *sc,
    bhnd_nvstore_index *index, void *cookiep)
{
        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        if (index->count >= index->capacity)
                return (ENOMEM);

        index->cookiep[index->count] = cookiep;
        index->count++;
        return (0);
}

/* sort function for bhnd_nvstore_index_prepare() */
static int
bhnd_nvstore_idx_cmp(const void *lhs, const void *rhs, void *ctx)
{
        struct bhnd_nvram_store *sc;
        void                    *l_cookiep, *r_cookiep;
        const char              *l_str, *r_str;
        const char              *l_name, *r_name;
        int                      order;

        sc = ctx;
        l_cookiep = *(void * const *)lhs;
        r_cookiep = *(void * const *)rhs;

        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        /* Fetch string pointers from the cookiep values */
        l_str = bhnd_nvram_data_getvar_name(sc->data, l_cookiep);
        r_str = bhnd_nvram_data_getvar_name(sc->data, r_cookiep);

        /* Trim device path prefixes */
        if (sc->data_caps & BHND_NVRAM_DATA_CAP_DEVPATHS) {
                l_name = bhnd_nvram_trim_path_name(l_str);
                r_name = bhnd_nvram_trim_path_name(r_str);
        } else {
                l_name = l_str;
                r_name = r_str;
        }

        /* Perform comparison */
        order = strcmp(l_name, r_name);
        if (order != 0 || lhs == rhs)
                return (order);

        /* If the backing data incorrectly contains variables with duplicate
         * names, we need a sort order that provides stable behavior.
         * 
         * Since Broadcom's own code varies wildly on this question, we just
         * use a simple precedence rule: The first declaration of a variable
         * takes precedence. */
        return (bhnd_nvram_data_getvar_order(sc->data, l_cookiep, r_cookiep));
}

/**
 * Prepare @p index for querying via bhnd_nvstore_index_lookup().
 * 
 * After one or more append requests, the index must be prepared via
 * bhnd_nvstore_index_prepare() before any indexed lookups are performed.
 *
 * @param       sc      The NVRAM store from which NVRAM values will be queried.
 * @param       index   The index to be prepared.
 * 
 * @retval 0            success
 * @retval non-zero     if preparing @p index otherwise fails, a regular unix
 *                      error code will be returned.
 */
int
bhnd_nvstore_index_prepare(struct bhnd_nvram_store *sc,
    bhnd_nvstore_index *index)
{
        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        /* Sort the index table */
        qsort_r(index->cookiep, index->count, sizeof(index->cookiep[0]),
            bhnd_nvstore_idx_cmp, sc);

        return (0);
}

/**
 * Return a borrowed reference to the root path node.
 * 
 * @param       sc      The NVRAM store.
 */
bhnd_nvstore_path *
bhnd_nvstore_get_root_path(struct bhnd_nvram_store *sc)
{
        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);
        return (sc->root_path);
}

/**
 * Return true if @p path is the root path node.
 * 
 * @param       sc      The NVRAM store.
 * @param       path    The path to query.
 */
bool
bhnd_nvstore_is_root_path(struct bhnd_nvram_store *sc, bhnd_nvstore_path *path)
{
        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);
        return (sc->root_path == path);
}

/**
 * Return the update entry matching @p name in @p path, or NULL if no entry
 * found.
 * 
 * @param sc    The NVRAM store.
 * @param path  The path to query.
 * @param name  The NVRAM variable name to search for in @p path's update list.
 * 
 * @retval non-NULL     success
 * @retval NULL         if @p name is not found in @p path.
 */
bhnd_nvram_prop *
bhnd_nvstore_path_get_update(struct bhnd_nvram_store *sc,
    bhnd_nvstore_path *path, const char *name)
{
        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);
        return (bhnd_nvram_plist_get_prop(path->pending, name));
}

/**
 * Register or remove an update record for @p name in @p path.
 * 
 * @param sc    The NVRAM store.
 * @param path  The path to be modified.
 * @param name  The path-relative variable name to be modified.
 * @param value The new value. A value of BHND_NVRAM_TYPE_NULL denotes deletion.
 * 
 * @retval 0            success
 * @retval ENOMEM       if allocation fails.
 * @retval ENOENT       if @p name is unknown.
 * @retval EINVAL       if @p value is NULL, and deletion of @p is not
 *                      supported.
 * @retval EINVAL       if @p value cannot be converted to a supported value
 *                      type.
 */
int
bhnd_nvstore_path_register_update(struct bhnd_nvram_store *sc,
    bhnd_nvstore_path *path, const char *name, bhnd_nvram_val *value)
{
        bhnd_nvram_val          *prop_val;
        const char              *full_name;
        void                    *cookiep;
        char                    *namebuf;
        int                      error;
        bool                     nvram_committed;

        namebuf = NULL;
        prop_val = NULL;

        /* Determine whether the variable is currently defined in the
         * backing NVRAM data, and derive its full path-prefixed name */
        nvram_committed = false;
        cookiep = bhnd_nvstore_path_data_lookup(sc, path, name);
        if (cookiep != NULL) {
                /* Variable is defined in the backing data */
                nvram_committed = true;

                /* Use the existing variable name */
                full_name = bhnd_nvram_data_getvar_name(sc->data, cookiep);
        } else if (path == sc->root_path) {
                /* No prefix required for root path */
                full_name = name;
        } else {
                bhnd_nvstore_alias      *alias;
                int                      len;

                /* New variable is being set; we need to determine the
                 * appropriate path prefix */
                alias = bhnd_nvstore_find_alias(sc, path->path_str);
                if (alias != NULL) {
                        /* Use <alias>:name */
                        len = bhnd_nv_asprintf(&namebuf, "%lu:%s", alias->alias,
                            name);
                } else {
                        /* Use path/name */
                        len = bhnd_nv_asprintf(&namebuf, "%s/%s",
                            path->path_str, name);
                }

                if (len < 0)
                        return (ENOMEM);

                full_name = namebuf;
        }

        /* Allow the data store to filter the NVRAM operation */
        if (bhnd_nvram_val_type(value) == BHND_NVRAM_TYPE_NULL) {
                error = bhnd_nvram_data_filter_unsetvar(sc->data, full_name);
                if (error) {
                        BHND_NV_LOG("cannot unset property %s: %d\n", full_name,
                            error);
                        goto cleanup;
                }

                if ((prop_val = bhnd_nvram_val_copy(value)) == NULL) {
                        error = ENOMEM;
                        goto cleanup;
                }
        } else {
                error = bhnd_nvram_data_filter_setvar(sc->data, full_name,
                    value,  &prop_val);
                if (error) {
                        BHND_NV_LOG("cannot set property %s: %d\n", full_name,
                            error);
                        goto cleanup;
                }
        }

        /* Add relative variable name to the per-path update list */
        if (bhnd_nvram_val_type(value) == BHND_NVRAM_TYPE_NULL &&
            !nvram_committed)
        {
                /* This is a deletion request for a variable not defined in
                 * out backing store; we can simply remove the corresponding
                 * update entry. */
                bhnd_nvram_plist_remove(path->pending, name);
        } else {
                /* Update or append a pending update entry */
                error = bhnd_nvram_plist_replace_val(path->pending, name,
                    prop_val);
                if (error)
                        goto cleanup;
        }

        /* Success */
        error = 0;

cleanup:
        if (namebuf != NULL)
                bhnd_nv_free(namebuf);

        if (prop_val != NULL)
                bhnd_nvram_val_release(prop_val);

        return (error);
}

/**
 * Iterate over all variable cookiep values retrievable from the backing
 * data store in @p path.
 * 
 * @warning Pending updates in @p path are ignored by this function.
 *
 * @param               sc      The NVRAM store.
 * @param               path    The NVRAM path to be iterated.
 * @param[in,out]       indexp  A pointer to an opaque indexp value previously
 *                              returned by bhnd_nvstore_path_data_next(), or a
 *                              NULL value to begin iteration.
 *
 * @return Returns the next variable name, or NULL if there are no more
 * variables defined in @p path.
 */
void *
bhnd_nvstore_path_data_next(struct bhnd_nvram_store *sc,
     bhnd_nvstore_path *path, void **indexp)
{
        void **index_ref;

        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        /* No index */
        if (path->index == NULL) {
                /* An index is required for all non-empty, non-root path
                 * instances */
                BHND_NV_ASSERT(bhnd_nvstore_is_root_path(sc, path),
                    ("missing index for non-root path %s", path->path_str));

                /* Iterate NVRAM data directly, using the NVRAM data's cookiep
                 * value as our indexp context */
                if ((bhnd_nvram_data_next(sc->data, indexp)) == NULL)
                        return (NULL);

                return (*indexp);
        }

        /* Empty index */
        if (path->index->count == 0)
                return (NULL);

        if (*indexp == NULL) {
                /* First index entry */
                index_ref = &path->index->cookiep[0];
        } else {
                size_t idxpos;

                /* Advance to next index entry */
                index_ref = *indexp;
                index_ref++;

                /* Hit end of index? */
                BHND_NV_ASSERT(index_ref > path->index->cookiep,
                    ("invalid indexp"));

                idxpos = (index_ref - path->index->cookiep);
                if (idxpos >= path->index->count)
                        return (NULL);
        }

        /* Provide new index position */
        *indexp = index_ref;

        /* Return the data's cookiep value */
        return (*index_ref);
}

/**
 * Perform an lookup of @p name in the backing NVRAM data for @p path,
 * returning the associated cookiep value, or NULL if the variable is not found
 * in the backing NVRAM data.
 * 
 * @warning Pending updates in @p path are ignored by this function.
 * 
 * @param       sc      The NVRAM store from which NVRAM values will be queried.
 * @param       path    The path to be queried.
 * @param       name    The variable name to be queried.
 * 
 * @retval non-NULL     success
 * @retval NULL         if @p name is not found in @p index.
 */
void *
bhnd_nvstore_path_data_lookup(struct bhnd_nvram_store *sc,
    bhnd_nvstore_path *path, const char *name)
{
        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        /* No index */
        if (path->index == NULL) {
                /* An index is required for all non-empty, non-root path
                 * instances */
                BHND_NV_ASSERT(bhnd_nvstore_is_root_path(sc, path),
                    ("missing index for non-root path %s", path->path_str));

                /* Look up directly in NVRAM data */
                return (bhnd_nvram_data_find(sc->data, name));
        }

        /* Otherwise, delegate to an index-based lookup */
        return (bhnd_nvstore_index_lookup(sc, path->index, name));
}

/**
 * Perform an index lookup of @p name, returning the associated cookiep
 * value, or NULL if the variable does not exist.
 * 
 * @param       sc      The NVRAM store from which NVRAM values will be queried.
 * @param       index   The index to be queried.
 * @param       name    The variable name to be queried.
 * 
 * @retval non-NULL     success
 * @retval NULL         if @p name is not found in @p index.
 */
void *
bhnd_nvstore_index_lookup(struct bhnd_nvram_store *sc,
    bhnd_nvstore_index *index, const char *name)
{
        void            *cookiep;
        const char      *indexed_name;
        size_t           min, mid, max;
        uint32_t         data_caps;
        int              order;

        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);
        BHND_NV_ASSERT(index != NULL, ("NULL index"));

        /*
         * Locate the requested variable using a binary search.
         */
        if (index->count == 0)
                return (NULL);

        data_caps = sc->data_caps;
        min = 0;
        max = index->count - 1;

        while (max >= min) {
                /* Select midpoint */
                mid = (min + max) / 2;
                cookiep = index->cookiep[mid];

                /* Fetch variable name */
                indexed_name = bhnd_nvram_data_getvar_name(sc->data, cookiep);

                /* Trim any path prefix */
                if (data_caps & BHND_NVRAM_DATA_CAP_DEVPATHS)
                        indexed_name = bhnd_nvram_trim_path_name(indexed_name);

                /* Determine which side of the partition to search */
                order = strcmp(indexed_name, name);
                if (order < 0) {
                        /* Search upper partition */
                        min = mid + 1;
                } else if (order > 0) {
                        /* Search (non-empty) lower partition */
                        if (mid == 0)
                                break;
                        max = mid - 1;
                } else if (order == 0) {
                        size_t  idx;

                        /*
                         * Match found.
                         * 
                         * If this happens to be a key with multiple definitions
                         * in the backing store, we need to find the entry with
                         * the highest declaration precedence.
                         * 
                         * Duplicates are sorted in order of descending
                         * precedence; to find the highest precedence entry,
                         * we search backwards through the index.
                         */
                        idx = mid;
                        while (idx > 0) {
                                void            *dup_cookiep;
                                const char      *dup_name;

                                /* Fetch preceding index entry */
                                idx--;
                                dup_cookiep = index->cookiep[idx];
                                dup_name = bhnd_nvram_data_getvar_name(sc->data,
                                    dup_cookiep);

                                /* Trim any path prefix */
                                if (data_caps & BHND_NVRAM_DATA_CAP_DEVPATHS) {
                                        dup_name = bhnd_nvram_trim_path_name(
                                            dup_name);
                                }

                                /* If no match, current cookiep is the variable
                                 * definition with the highest precedence */
                                if (strcmp(indexed_name, dup_name) != 0)
                                        return (cookiep);

                                /* Otherwise, prefer this earlier definition,
                                 * and keep searching for a higher-precedence
                                 * definitions */
                                cookiep = dup_cookiep;
                        }

                        return (cookiep);
                }
        }

        /* Not found */
        return (NULL);
}

/**
 * Return the device path entry registered for @p path, if any.
 * 
 * @param       sc              The NVRAM store to be queried.
 * @param       path            The device path to search for.
 * @param       path_len        The length of @p path.
 *
 * @retval non-NULL     if found.
 * @retval NULL         if not found.
 */
bhnd_nvstore_path *
bhnd_nvstore_get_path(struct bhnd_nvram_store *sc, const char *path,
    size_t path_len)
{
        bhnd_nvstore_path_list  *plist;
        bhnd_nvstore_path       *p;
        uint32_t                 h;

        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        /* Use hash lookup */
        h = hash32_strn(path, path_len, HASHINIT);
        plist = &sc->paths[h % nitems(sc->paths)];

        LIST_FOREACH(p, plist, np_link) {
                /* Check for prefix match */
                if (strncmp(p->path_str, path, path_len) != 0)
                        continue;

                /* Check for complete match */
                if (strnlen(path, path_len) != strlen(p->path_str))
                        continue;

                return (p);
        }

        /* Not found */
        return (NULL);
}

/**
 * Resolve @p aval to its corresponding device path entry, if any.
 * 
 * @param       sc              The NVRAM store to be queried.
 * @param       aval            The device path alias value to search for.
 *
 * @retval non-NULL     if found.
 * @retval NULL         if not found.
 */
bhnd_nvstore_path *
bhnd_nvstore_resolve_path_alias(struct bhnd_nvram_store *sc, u_long aval)
{
        bhnd_nvstore_alias *alias;

        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        /* Fetch alias entry */
        if ((alias = bhnd_nvstore_get_alias(sc, aval)) == NULL)
                return (NULL);

        return (alias->path);
}

/**
 * Register a device path entry for the path referenced by variable name
 * @p info, if any.
 *
 * @param       sc              The NVRAM store to be updated.
 * @param       info            The NVRAM variable name info.
 * @param       cookiep         The NVRAM variable's cookiep value.
 *
 * @retval 0            if the path was successfully registered, or an identical
 *                      path or alias entry exists.
 * @retval EEXIST       if a conflicting entry already exists for the path or
 *                      alias referenced by @p info.
 * @retval ENOENT       if @p info contains a dangling alias reference.
 * @retval EINVAL       if @p info contains an unsupported bhnd_nvstore_var_type
 *                      and bhnd_nvstore_path_type combination.
 * @retval ENOMEM       if allocation fails.
 */
int
bhnd_nvstore_var_register_path(struct bhnd_nvram_store *sc,
    bhnd_nvstore_name_info *info, void *cookiep)
{
        switch (info->type) {
        case BHND_NVSTORE_VAR:
                /* Variable */
                switch (info->path_type) {
                case BHND_NVSTORE_PATH_STRING:
                        /* Variable contains a full path string
                         * (pci/1/1/varname); register the path */
                        return (bhnd_nvstore_register_path(sc,
                            info->path.str.value, info->path.str.value_len));

                case BHND_NVSTORE_PATH_ALIAS:
                        /* Variable contains an alias reference (0:varname).
                         * There's no path to register */
                        return (0);
                }

                BHND_NV_PANIC("unsupported path type %d", info->path_type);
                break;

        case BHND_NVSTORE_ALIAS_DECL:
                /* Alias declaration */
                return (bhnd_nvstore_register_alias(sc, info, cookiep));
        }

        BHND_NV_PANIC("unsupported var type %d", info->type);
}

/**
 * Resolve the device path entry referenced by @p info.
 *
 * @param       sc              The NVRAM store to be updated.
 * @param       info            Variable name information descriptor containing
 *                              the path or path alias to be resolved.
 *
 * @retval non-NULL     if found.
 * @retval NULL         if not found.
 */
bhnd_nvstore_path *
bhnd_nvstore_var_get_path(struct bhnd_nvram_store *sc,
    bhnd_nvstore_name_info *info)
{
        switch (info->path_type) {
        case BHND_NVSTORE_PATH_STRING:
                return (bhnd_nvstore_get_path(sc, info->path.str.value,
                    info->path.str.value_len));
        case BHND_NVSTORE_PATH_ALIAS:
                return (bhnd_nvstore_resolve_path_alias(sc,
                    info->path.alias.value));
        }

        BHND_NV_PANIC("unsupported path type %d", info->path_type);
}

/**
 * Return the device path alias entry registered for @p alias_val, if any.
 * 
 * @param       sc              The NVRAM store to be queried.
 * @param       alias_val       The alias value to search for.
 *
 * @retval non-NULL     if found.
 * @retval NULL         if not found.
 */
bhnd_nvstore_alias *
bhnd_nvstore_get_alias(struct bhnd_nvram_store *sc, u_long alias_val)
{
        bhnd_nvstore_alias_list *alist;
        bhnd_nvstore_alias      *alias;

        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        /* Can use hash lookup */
        alist = &sc->aliases[alias_val % nitems(sc->aliases)];
        LIST_FOREACH(alias, alist, na_link) {
                if (alias->alias == alias_val)
                        return (alias);                 
        }

        /* Not found */
        return (NULL);
}

/**
 * Return the device path alias entry registered for @p path, if any.
 * 
 * @param       sc      The NVRAM store to be queried.
 * @param       path    The alias path to search for.
 *
 * @retval non-NULL     if found.
 * @retval NULL         if not found.
 */
bhnd_nvstore_alias *
bhnd_nvstore_find_alias(struct bhnd_nvram_store *sc, const char *path)
{
        bhnd_nvstore_alias *alias;

        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        /* Have to scan the full table */
        for (size_t i = 0; i < nitems(sc->aliases); i++) {
                LIST_FOREACH(alias, &sc->aliases[i], na_link) {
                        if (strcmp(alias->path->path_str, path) == 0)
                                return (alias);                 
                }
        }

        /* Not found */
        return (NULL);
}

/**
 * Register a device path entry for @p path.
 * 
 * @param       sc              The NVRAM store to be updated.
 * @param       path_str        The absolute device path string.
 * @param       path_len        The length of @p path_str.
 * 
 * @retval 0            if the path was successfully registered, or an identical
 *                      path/alias entry already exists.
 * @retval ENOMEM       if allocation fails.
 */
int
bhnd_nvstore_register_path(struct bhnd_nvram_store *sc, const char *path_str,
    size_t path_len)
{
        bhnd_nvstore_path_list  *plist;
        bhnd_nvstore_path       *path;
        uint32_t                 h;

        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        /* Already exists? */
        if (bhnd_nvstore_get_path(sc, path_str, path_len) != NULL)
                return (0);

        /* Can't represent more than SIZE_MAX paths */
        if (sc->num_paths == SIZE_MAX)
                return (ENOMEM);

        /* Allocate new entry */
        path = bhnd_nvstore_path_new(path_str, path_len);
        if (path == NULL)
                return (ENOMEM);

        /* Insert in path hash table */
        h = hash32_str(path->path_str, HASHINIT);
        plist = &sc->paths[h % nitems(sc->paths)];
        LIST_INSERT_HEAD(plist, path, np_link);

        /* Increment path count */
        sc->num_paths++;

        return (0);
}

/**
 * Register a device path alias for an NVRAM 'devpathX' variable.
 * 
 * The path value for the alias will be fetched from the backing NVRAM data.
 * 
 * @param       sc      The NVRAM store to be updated.
 * @param       info    The NVRAM variable name info.
 * @param       cookiep The NVRAM variable's cookiep value.
 * 
 * @retval 0            if the alias was successfully registered, or an
 *                      identical alias entry exists.
 * @retval EEXIST       if a conflicting alias or path entry already exists.
 * @retval EINVAL       if @p info is not a BHND_NVSTORE_ALIAS_DECL or does
 *                      not contain a BHND_NVSTORE_PATH_ALIAS entry.
 * @retval ENOMEM       if allocation fails.
 */
int
bhnd_nvstore_register_alias(struct bhnd_nvram_store *sc,
    const bhnd_nvstore_name_info *info, void *cookiep)
{
        bhnd_nvstore_alias_list *alist;
        bhnd_nvstore_alias      *alias;
        bhnd_nvstore_path       *path;
        char                    *path_str;
        size_t                   path_len;
        int                      error;

        BHND_NVSTORE_LOCK_ASSERT(sc, MA_OWNED);

        path_str = NULL;
        alias = NULL;

        /* Can't represent more than SIZE_MAX aliases */
        if (sc->num_aliases == SIZE_MAX)
                return (ENOMEM);

        /* Must be an alias declaration */
        if (info->type != BHND_NVSTORE_ALIAS_DECL)
                return (EINVAL);

        if (info->path_type != BHND_NVSTORE_PATH_ALIAS)
                return (EINVAL);

        /* Fetch the devpath variable's value length */
        error = bhnd_nvram_data_getvar(sc->data, cookiep, NULL, &path_len,
            BHND_NVRAM_TYPE_STRING);
        if (error)
                return (ENOMEM);

        /* Allocate path string buffer */
        if ((path_str = bhnd_nv_malloc(path_len)) == NULL)
                return (ENOMEM);

        /* Decode to our new buffer */
        error = bhnd_nvram_data_getvar(sc->data, cookiep, path_str, &path_len,
            BHND_NVRAM_TYPE_STRING);
        if (error)
                goto failed;

        /* Trim trailing '/' character(s) from the path length */
        path_len = strnlen(path_str, path_len);
        while (path_len > 0 && path_str[path_len-1] == '/') {
                path_str[path_len-1] = '\0';
                path_len--;
        }

        /* Is a conflicting alias entry already registered for this alias
         * value? */
        alias = bhnd_nvstore_get_alias(sc, info->path.alias.value);
        if (alias != NULL) {
                if (alias->cookiep != cookiep ||
                    strcmp(alias->path->path_str, path_str) != 0)
                {
                        error = EEXIST;
                        goto failed;
                }
        }

        /* Is a conflicting entry already registered for the alias path? */
        if ((alias = bhnd_nvstore_find_alias(sc, path_str)) != NULL) {
                if (alias->alias != info->path.alias.value ||
                    alias->cookiep != cookiep ||
                    strcmp(alias->path->path_str, path_str) != 0)
                {
                        error = EEXIST;
                        goto failed;
                }
        }

        /* Get (or register) the target path entry */
        path = bhnd_nvstore_get_path(sc, path_str, path_len);
        if (path == NULL) {
                error = bhnd_nvstore_register_path(sc, path_str, path_len);
                if (error)
                        goto failed;

                path = bhnd_nvstore_get_path(sc, path_str, path_len);
                BHND_NV_ASSERT(path != NULL, ("missing registered path"));
        }

        /* Allocate alias entry */
        alias = bhnd_nv_calloc(1, sizeof(*alias));
        if (alias == NULL) {
                error = ENOMEM;
                goto failed;
        }

        alias->path = path;
        alias->cookiep = cookiep;
        alias->alias = info->path.alias.value;

        /* Insert in alias hash table */
        alist = &sc->aliases[alias->alias % nitems(sc->aliases)];
        LIST_INSERT_HEAD(alist, alias, na_link);

        /* Increment alias count */
        sc->num_aliases++;

        bhnd_nv_free(path_str);
        return (0);

failed:
        if (path_str != NULL)
                bhnd_nv_free(path_str);

        if (alias != NULL)
                bhnd_nv_free(alias);

        return (error);
}

/**
 * If @p child is equal to or a child path of @p parent, return a pointer to
 * @p child's path component(s) relative to @p parent; otherwise, return NULL.
 */
const char *
bhnd_nvstore_parse_relpath(const char *parent, const char *child)
{
        size_t prefix_len;

        /* All paths have an implicit leading '/'; this allows us to treat
         * our manufactured root path of "/" as a prefix to all NVRAM-defined
         * paths (which do not necessarily include a leading '/' */
        if (*parent == '/')
                parent++;

        if (*child == '/')
                child++;

        /* Is parent a prefix of child? */
        prefix_len = strlen(parent);
        if (strncmp(parent, child, prefix_len) != 0)
                return (NULL);

        /* A zero-length prefix matches everything */
        if (prefix_len == 0)
                return (child);

        /* Is child equal to parent? */
        if (child[prefix_len] == '\0')
                return (child + prefix_len);

        /* Is child actually a child of parent? */
        if (child[prefix_len] == '/')
                return (child + prefix_len + 1);

        /* No match (e.g. parent=/foo..., child=/fooo...) */
        return (NULL);
}

/**
 * Parse a raw NVRAM variable name and return its @p entry_type, its
 * type-specific @p prefix (e.g. '0:', 'pci/1/1', 'devpath'), and its
 * type-specific @p suffix (e.g. 'varname', '0').
 * 
 * @param       name            The NVRAM variable name to be parsed. This
 *                              value must remain valid for the lifetime of
 *                              @p info.
 * @param       type            The NVRAM name type -- either INTERNAL for names
 *                              parsed from backing NVRAM data, or EXTERNAL for
 *                              names provided by external NVRAM store clients.
 * @param       data_caps       The backing NVRAM data capabilities
 *                              (see bhnd_nvram_data_caps()).
 * @param[out]  info            On success, the parsed variable name info.
 * 
 * @retval 0            success
 * @retval non-zero     if parsing @p name otherwise fails, a regular unix
 *                      error code will be returned.
 */
int
bhnd_nvstore_parse_name_info(const char *name, bhnd_nvstore_name_type type,
    uint32_t data_caps, bhnd_nvstore_name_info *info)
{
        const char      *p;
        char            *endp;

        /* Skip path parsing? */
        if (data_caps & BHND_NVRAM_DATA_CAP_DEVPATHS) {
                /* devpath declaration? (devpath0=pci/1/1) */
                if (strncmp(name, "devpath", strlen("devpath")) == 0) {
                        u_long alias;

                        /* Perform standard validation on the relative
                         * variable name */
                        if (type != BHND_NVSTORE_NAME_INTERNAL &&
                            !bhnd_nvram_validate_name(name))
                        {
                                return (ENOENT);
                        }

                        /* Parse alias value that should follow a 'devpath'
                         * prefix */
                        p = name + strlen("devpath");
                        alias = strtoul(p, &endp, 10);
                        if (endp != p && *endp == '\0') {
                                info->type = BHND_NVSTORE_ALIAS_DECL;
                                info->path_type = BHND_NVSTORE_PATH_ALIAS;
                                info->name = name;
                                info->path.alias.value = alias;

                                return (0);
                        }
                }

                /* device aliased variable? (0:varname) */
                if (bhnd_nv_isdigit(*name)) {
                        u_long alias;

                        /* Parse '0:' alias prefix */
                        alias = strtoul(name, &endp, 10);
                        if (endp != name && *endp == ':') {
                                /* Perform standard validation on the relative
                                 * variable name */
                                if (type != BHND_NVSTORE_NAME_INTERNAL &&
                                    !bhnd_nvram_validate_name(name))
                                {
                                        return (ENOENT);
                                }

                                info->type = BHND_NVSTORE_VAR;
                                info->path_type = BHND_NVSTORE_PATH_ALIAS;

                                /* name follows 0: prefix */
                                info->name = endp + 1;
                                info->path.alias.value = alias;

                                return (0);
                        }
                }

                /* device variable? (pci/1/1/varname) */
                if ((p = strrchr(name, '/')) != NULL) {
                        const char      *path, *relative_name;
                        size_t           path_len;

                        /* Determine the path length; 'p' points at the last
                         * path separator in 'name' */
                        path_len = p - name;
                        path = name;

                        /* The relative variable name directly follows the
                         * final path separator '/' */
                        relative_name = path + path_len + 1;

                        /* Now that we calculated the name offset, exclude all
                         * trailing '/' characters from the path length */
                        while (path_len > 0 && path[path_len-1] == '/')
                                path_len--;

                        /* Perform standard validation on the relative
                         * variable name */
                        if (type != BHND_NVSTORE_NAME_INTERNAL &&
                            !bhnd_nvram_validate_name(relative_name))
                        {
                                return (ENOENT);
                        }

                        /* Initialize result with pointers into the name
                         * buffer */
                        info->type = BHND_NVSTORE_VAR;
                        info->path_type = BHND_NVSTORE_PATH_STRING;
                        info->name = relative_name;
                        info->path.str.value = path;
                        info->path.str.value_len = path_len;

                        return (0);
                }
        }

        /* If all other parsing fails, the result is a simple variable with
         * an implicit path of "/" */
        if (type != BHND_NVSTORE_NAME_INTERNAL &&
            !bhnd_nvram_validate_name(name))
        {
                /* Invalid relative name */
                return (ENOENT);
        }

        info->type = BHND_NVSTORE_VAR;
        info->path_type = BHND_NVSTORE_PATH_STRING;
        info->name = name;
        info->path.str.value = BHND_NVSTORE_ROOT_PATH;
        info->path.str.value_len = BHND_NVSTORE_ROOT_PATH_LEN;

        return (0);
}