common/mdesc/mdesc_walkdag.c

908f1e1388f616898b4e515d343c0414f2a6472esd/*
908f1e1388f616898b4e515d343c0414f2a6472esd * CDDL HEADER START
908f1e1388f616898b4e515d343c0414f2a6472esd *
908f1e1388f616898b4e515d343c0414f2a6472esd * The contents of this file are subject to the terms of the
908f1e1388f616898b4e515d343c0414f2a6472esd * Common Development and Distribution License (the "License").
908f1e1388f616898b4e515d343c0414f2a6472esd * You may not use this file except in compliance with the License.
908f1e1388f616898b4e515d343c0414f2a6472esd *
908f1e1388f616898b4e515d343c0414f2a6472esd * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
908f1e1388f616898b4e515d343c0414f2a6472esd * or http://www.opensolaris.org/os/licensing.
908f1e1388f616898b4e515d343c0414f2a6472esd * See the License for the specific language governing permissions
908f1e1388f616898b4e515d343c0414f2a6472esd * and limitations under the License.
908f1e1388f616898b4e515d343c0414f2a6472esd *
908f1e1388f616898b4e515d343c0414f2a6472esd * When distributing Covered Code, include this CDDL HEADER in each
908f1e1388f616898b4e515d343c0414f2a6472esd * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
908f1e1388f616898b4e515d343c0414f2a6472esd * If applicable, add the following below this CDDL HEADER, with the
908f1e1388f616898b4e515d343c0414f2a6472esd * fields enclosed by brackets "[]" replaced with your own identifying
908f1e1388f616898b4e515d343c0414f2a6472esd * information: Portions Copyright [yyyy] [name of copyright owner]
908f1e1388f616898b4e515d343c0414f2a6472esd *
908f1e1388f616898b4e515d343c0414f2a6472esd * CDDL HEADER END
908f1e1388f616898b4e515d343c0414f2a6472esd */
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd/*
908f1e1388f616898b4e515d343c0414f2a6472esd * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
908f1e1388f616898b4e515d343c0414f2a6472esd * Use is subject to license terms.
908f1e1388f616898b4e515d343c0414f2a6472esd */
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd#pragma ident   "%Z%%M% %I% %E% SMI"
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd#include <sys/types.h>
908f1e1388f616898b4e515d343c0414f2a6472esd#include <sys/param.h>
908f1e1388f616898b4e515d343c0414f2a6472esd#ifdef _KERNEL
908f1e1388f616898b4e515d343c0414f2a6472esd#include <sys/systm.h>
908f1e1388f616898b4e515d343c0414f2a6472esd#else
908f1e1388f616898b4e515d343c0414f2a6472esd#include <string.h>
908f1e1388f616898b4e515d343c0414f2a6472esd#include <strings.h>
908f1e1388f616898b4e515d343c0414f2a6472esd#endif
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd#include <sys/mdesc.h>
908f1e1388f616898b4e515d343c0414f2a6472esd#include <sys/mdesc_impl.h>
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esdstatic int
908f1e1388f616898b4e515d343c0414f2a6472esdmdl_walk_dag(md_impl_t *, mde_cookie_t, mde_cookie_t, mde_str_cookie_t,
908f1e1388f616898b4e515d343c0414f2a6472esd    mde_str_cookie_t, uint8_t *, md_walk_fn_t, void *, int);
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd/*
908f1e1388f616898b4e515d343c0414f2a6472esd * Walk the machine description directed graph from a starting
908f1e1388f616898b4e515d343c0414f2a6472esd * node searching for nodes of a given node name and using a
908f1e1388f616898b4e515d343c0414f2a6472esd * given arc type.  Call a callback function for each node found.
908f1e1388f616898b4e515d343c0414f2a6472esd * Each node will be visited only once.
908f1e1388f616898b4e515d343c0414f2a6472esd *
908f1e1388f616898b4e515d343c0414f2a6472esd * Input        Description
908f1e1388f616898b4e515d343c0414f2a6472esd * -------------------  ----------------------------------------
908f1e1388f616898b4e515d343c0414f2a6472esd * md_t *       Pointer to md session
908f1e1388f616898b4e515d343c0414f2a6472esd * mde_cookie_t     Index of the starting node
908f1e1388f616898b4e515d343c0414f2a6472esd * mde_str_cookie_t Node name cookie of the nodes to call
908f1e1388f616898b4e515d343c0414f2a6472esd *          the walk function
908f1e1388f616898b4e515d343c0414f2a6472esd * mde_str_cookie_t Arc name cookie of the path to follow
908f1e1388f616898b4e515d343c0414f2a6472esd * md_walk_fn_t     The function to call for each node
908f1e1388f616898b4e515d343c0414f2a6472esd * void *       Private data to pass to the walker function
908f1e1388f616898b4e515d343c0414f2a6472esd *
908f1e1388f616898b4e515d343c0414f2a6472esd */
908f1e1388f616898b4e515d343c0414f2a6472esdint
908f1e1388f616898b4e515d343c0414f2a6472esdmd_walk_dag(md_t *ptr, mde_cookie_t startnode,
908f1e1388f616898b4e515d343c0414f2a6472esd    mde_str_cookie_t node_name_cookie, mde_str_cookie_t arc_name_cookie,
908f1e1388f616898b4e515d343c0414f2a6472esd    md_walk_fn_t func, void *private)
908f1e1388f616898b4e515d343c0414f2a6472esd{
908f1e1388f616898b4e515d343c0414f2a6472esd    int     res;
908f1e1388f616898b4e515d343c0414f2a6472esd    uint8_t     *seenp;
908f1e1388f616898b4e515d343c0414f2a6472esd    md_impl_t   *mdp;
908f1e1388f616898b4e515d343c0414f2a6472esd    mde_cookie_t    start;
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    mdp = (md_impl_t *)ptr;
908f1e1388f616898b4e515d343c0414f2a6472esd    if (mdp == NULL) {
908f1e1388f616898b4e515d343c0414f2a6472esd        return (-1);
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /*
908f1e1388f616898b4e515d343c0414f2a6472esd     * Possible the caller was lazy and didn't check the
908f1e1388f616898b4e515d343c0414f2a6472esd     * validitiy of either the node name or the arc name
908f1e1388f616898b4e515d343c0414f2a6472esd     * on calling ... in which case fail to find any
908f1e1388f616898b4e515d343c0414f2a6472esd     * nodes.
908f1e1388f616898b4e515d343c0414f2a6472esd     * This is distinct, from a fail (-1) since we return
908f1e1388f616898b4e515d343c0414f2a6472esd     * that nothing was found.
908f1e1388f616898b4e515d343c0414f2a6472esd     */
908f1e1388f616898b4e515d343c0414f2a6472esd    if (node_name_cookie == MDE_INVAL_STR_COOKIE ||
908f1e1388f616898b4e515d343c0414f2a6472esd        arc_name_cookie == MDE_INVAL_STR_COOKIE) {
908f1e1388f616898b4e515d343c0414f2a6472esd        return (0);
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /*
908f1e1388f616898b4e515d343c0414f2a6472esd     * if we want to start at the top, start at index 0
908f1e1388f616898b4e515d343c0414f2a6472esd     */
908f1e1388f616898b4e515d343c0414f2a6472esd    start = startnode;
908f1e1388f616898b4e515d343c0414f2a6472esd    if (start == MDE_INVAL_ELEM_COOKIE) {
908f1e1388f616898b4e515d343c0414f2a6472esd        start = 0;
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /*
908f1e1388f616898b4e515d343c0414f2a6472esd     * Scan from the start point until the first node.
908f1e1388f616898b4e515d343c0414f2a6472esd     */
908f1e1388f616898b4e515d343c0414f2a6472esd    while (start < mdp->element_count &&
908f1e1388f616898b4e515d343c0414f2a6472esd        MDE_TAG(&mdp->mdep[start]) == MDET_NULL) {
908f1e1388f616898b4e515d343c0414f2a6472esd        start++;
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /*
908f1e1388f616898b4e515d343c0414f2a6472esd     * This was a bogus start point if no node found
908f1e1388f616898b4e515d343c0414f2a6472esd     */
908f1e1388f616898b4e515d343c0414f2a6472esd    if (MDE_TAG(&mdp->mdep[start]) != MDET_NODE) {
908f1e1388f616898b4e515d343c0414f2a6472esd        return (-1);    /* illegal start node specified */
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /*
908f1e1388f616898b4e515d343c0414f2a6472esd     * Allocate a recursion detection structure so we only visit
908f1e1388f616898b4e515d343c0414f2a6472esd     * each node once.
908f1e1388f616898b4e515d343c0414f2a6472esd     */
908f1e1388f616898b4e515d343c0414f2a6472esd    seenp = (uint8_t *)mdp->allocp(mdp->element_count);
908f1e1388f616898b4e515d343c0414f2a6472esd    if (seenp == NULL) {
908f1e1388f616898b4e515d343c0414f2a6472esd        return (-1);
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd    (void) memset(seenp, 0, mdp->element_count);
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /*
908f1e1388f616898b4e515d343c0414f2a6472esd     * Now build the list of requested nodes.
908f1e1388f616898b4e515d343c0414f2a6472esd     */
908f1e1388f616898b4e515d343c0414f2a6472esd    res = mdl_walk_dag(mdp, MDE_INVAL_ELEM_COOKIE, start,
908f1e1388f616898b4e515d343c0414f2a6472esd        node_name_cookie, arc_name_cookie, seenp, func, private, 0);
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    mdp->freep(seenp, mdp->element_count);
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    return (res >= 0 ? 0 : res);
908f1e1388f616898b4e515d343c0414f2a6472esd}
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esdstatic int
908f1e1388f616898b4e515d343c0414f2a6472esdmdl_walk_dag(md_impl_t *mdp, mde_cookie_t parentidx, mde_cookie_t nodeidx,
908f1e1388f616898b4e515d343c0414f2a6472esd    mde_str_cookie_t node_name_cookie, mde_str_cookie_t arc_name_cookie,
908f1e1388f616898b4e515d343c0414f2a6472esd    uint8_t *seenp, md_walk_fn_t func, void *private, int level)
908f1e1388f616898b4e515d343c0414f2a6472esd{
908f1e1388f616898b4e515d343c0414f2a6472esd    int     result;
908f1e1388f616898b4e515d343c0414f2a6472esd    md_element_t    *mdep;
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /* Get the node element from the session */
908f1e1388f616898b4e515d343c0414f2a6472esd    mdep = &(mdp->mdep[nodeidx]);
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /* see if cookie is infact a node */
908f1e1388f616898b4e515d343c0414f2a6472esd    if (MDE_TAG(mdep) != MDET_NODE) {
908f1e1388f616898b4e515d343c0414f2a6472esd        return (MDE_WALK_ERROR);
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /* have we been here before ? */
908f1e1388f616898b4e515d343c0414f2a6472esd    if (seenp[nodeidx]) {
908f1e1388f616898b4e515d343c0414f2a6472esd        return (MDE_WALK_NEXT);
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd    seenp[nodeidx] = 1;
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd#ifdef  DEBUG_LIBMDESC
908f1e1388f616898b4e515d343c0414f2a6472esd    {
908f1e1388f616898b4e515d343c0414f2a6472esd        int x;
908f1e1388f616898b4e515d343c0414f2a6472esd        for (x = 0; x < level; x++) {
908f1e1388f616898b4e515d343c0414f2a6472esd            printf("-");
908f1e1388f616898b4e515d343c0414f2a6472esd        }
908f1e1388f616898b4e515d343c0414f2a6472esd        printf("%d (%s)\n", nodeidx,
908f1e1388f616898b4e515d343c0414f2a6472esd            (char *)(mdp->datap + MDE_NAME(mdep)));
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd#endif
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /* is this node of the type we seek ? */
908f1e1388f616898b4e515d343c0414f2a6472esd    if (MDE_NAME(mdep) == node_name_cookie) {
908f1e1388f616898b4e515d343c0414f2a6472esd        /*
908f1e1388f616898b4e515d343c0414f2a6472esd         * Yes.  Call the callback function.
908f1e1388f616898b4e515d343c0414f2a6472esd         */
908f1e1388f616898b4e515d343c0414f2a6472esd        result = (func)((md_t *)mdp, parentidx, nodeidx, private);
908f1e1388f616898b4e515d343c0414f2a6472esd        if (result != MDE_WALK_NEXT) {
908f1e1388f616898b4e515d343c0414f2a6472esd            return (result);
908f1e1388f616898b4e515d343c0414f2a6472esd        }
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    /*
908f1e1388f616898b4e515d343c0414f2a6472esd     * Simply walk the elements in the node.
908f1e1388f616898b4e515d343c0414f2a6472esd     * if we find a matching arc, then recursively call
908f1e1388f616898b4e515d343c0414f2a6472esd     * the subordinate looking for a match
908f1e1388f616898b4e515d343c0414f2a6472esd     */
908f1e1388f616898b4e515d343c0414f2a6472esd    result = MDE_WALK_NEXT;
908f1e1388f616898b4e515d343c0414f2a6472esd    for (mdep++; MDE_TAG(mdep) != MDET_NODE_END; mdep++) {
908f1e1388f616898b4e515d343c0414f2a6472esd        if (MDE_TAG(mdep) == MDET_PROP_ARC &&
908f1e1388f616898b4e515d343c0414f2a6472esd            MDE_NAME(mdep) == arc_name_cookie) {
908f1e1388f616898b4e515d343c0414f2a6472esd            /*
908f1e1388f616898b4e515d343c0414f2a6472esd             * The current node becomes the parent node, and the
908f1e1388f616898b4e515d343c0414f2a6472esd             * arc index is the new current node.
908f1e1388f616898b4e515d343c0414f2a6472esd             */
908f1e1388f616898b4e515d343c0414f2a6472esd            result = mdl_walk_dag(mdp, nodeidx, mdep->d.prop_idx,
908f1e1388f616898b4e515d343c0414f2a6472esd                node_name_cookie, arc_name_cookie, seenp, func,
908f1e1388f616898b4e515d343c0414f2a6472esd                private, level+1);
908f1e1388f616898b4e515d343c0414f2a6472esd            if (result != MDE_WALK_NEXT) {
908f1e1388f616898b4e515d343c0414f2a6472esd                /* The walk is complete or terminated. */
908f1e1388f616898b4e515d343c0414f2a6472esd                return (result);
908f1e1388f616898b4e515d343c0414f2a6472esd            }
908f1e1388f616898b4e515d343c0414f2a6472esd        }
908f1e1388f616898b4e515d343c0414f2a6472esd    }
908f1e1388f616898b4e515d343c0414f2a6472esd
908f1e1388f616898b4e515d343c0414f2a6472esd    return (result);
908f1e1388f616898b4e515d343c0414f2a6472esd}