1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * CDDL HEADER START
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * The contents of this file are subject to the terms of the
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Common Development and Distribution License (the "License").
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * You may not use this file except in compliance with the License.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * See the License for the specific language governing permissions
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * and limitations under the License.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * When distributing Covered Code, include this CDDL HEADER in each
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * If applicable, add the following below this CDDL HEADER, with the
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * fields enclosed by brackets "[]" replaced with your own identifying
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * information: Portions Copyright [yyyy] [name of copyright owner]
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * CDDL HEADER END
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Use is subject to license terms.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo#pragma ident "%Z%%M% %I% %E% SMI"
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo#else /* _KERNEL */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo#endif /* _KERNEL */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo#define MD_DIFF_MAGIC 0x4D445F4449464621ull /* 'MD_DIFF!' */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppotypedef struct {
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppotypedef struct {
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Internal utility functions
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppostatic int mdd_scan_for_nodes(md_t *mdp, mde_cookie_t start,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo char *compnodep, int *countp, mde_cookie_t **nodespp);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppostatic boolean_t mdd_any_dup_nodes(md_impl_t *mdp, md_prop_match_t *pmp,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppostatic int mdd_node_list_match(md_impl_t *md1, md_impl_t *md2,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo uint8_t *match_seenp, int start, int end, md_prop_match_t *match_elemsp);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppostatic int mdd_node_compare(md_impl_t *mdap, md_impl_t *mdbp,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo md_element_t *nodeap, md_element_t *nodebp, md_prop_match_t *match_elemsp);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Given two DAGs and information about how to uniquely identify
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * the nodes of interest, determine which nodes have been added
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * to the second MD, removed from the first MD, or exist in both
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * MDs. This information is recorded and can be accessed using the
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * opaque cookie returned to the caller.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppomd_diff_init(md_t *md1p, mde_cookie_t start1, md_t *md2p, mde_cookie_t start2,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* variables used to gather results */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* sanity check params */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Prepare an array of the matching nodes from the first MD.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* sanity check that all nodes are unique */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo mdd_any_dup_nodes(md1, match_fieldsp, md1count, md1nodesp)) {
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo MDD_FREE_CHECK(md1, md1nodesp, sizeof (mde_cookie_t) *
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Prepare an array of the matching nodes from the second MD.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* sanity check that all nodes are unique */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo mdd_any_dup_nodes(md2, match_fieldsp, md2count, md2nodesp)) {
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo MDD_FREE_CHECK(md1, md1nodesp, sizeof (mde_cookie_t) *
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo MDD_FREE_CHECK(md2, md2nodesp, sizeof (mde_cookie_t) *
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* setup our result structure */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Special cases for empty lists
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* all the nodes found were added */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* all the nodes found were removed */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* no nodes found */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Both lists have some elements. Allocate some scratch
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * buffers to sort them into our three categories, added,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * removed, and matched pairs.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo mde_add_scr = diff_res->allocp(sizeof (mde_cookie_t) * md2count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo mde_rem_scr = diff_res->allocp(sizeof (mde_cookie_t) * md1count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo mde_match1_scr = diff_res->allocp(sizeof (mde_cookie_t) * md1count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo mde_match2_scr = diff_res->allocp(sizeof (mde_cookie_t) * md2count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* array of seen flags only needed for md2 */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo seenp = (uint8_t *)diff_res->allocp(sizeof (uint8_t) * md2count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Make a pass through the md1 node array. Make note of
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * any nodes not in the md2 array, indicating that they
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * have been removed. Also keep track of the nodes that
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * are present in both arrays for the matched pair results.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo int match = mdd_node_list_match(md1, md2, elem, md2nodesp,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* record deleted node */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* record matched node pair */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* mark that this match has been recorded */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Make a pass through the md2 array. Any nodes that have
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * not been marked as seen have been added.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* record added node */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* fill in the added node list */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo diff_res->added.mdep = (mde_cookie_t *)diff_res->allocp(addsz);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* fill in the removed node list */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* fill in the matching node lists */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo bcopy(mde_match1_scr, diff_res->match1.mdep, matchsz);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo bcopy(mde_match2_scr, diff_res->match2.mdep, matchsz);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* clean up */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo md1->freep(md1nodesp, sizeof (mde_cookie_t) * md1count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo md2->freep(md2nodesp, sizeof (mde_cookie_t) * md2count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo diff_res->freep(mde_add_scr, sizeof (mde_cookie_t) * md2count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo diff_res->freep(mde_rem_scr, sizeof (mde_cookie_t) * md1count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo diff_res->freep(mde_match1_scr, sizeof (mde_cookie_t) * md1count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo diff_res->freep(mde_match2_scr, sizeof (mde_cookie_t) * md2count);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Returns an array of the nodes added to the second MD in a
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * previous md_diff_init() call. Returns the number of elements
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * in the returned array. If the value is zero, the pointer
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * passed back will be NULL.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppomd_diff_added(md_diff_cookie_t mdd, mde_cookie_t **mde_addedp)
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo return (-1);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Returns an array of the nodes removed from the first MD in a
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * previous md_diff_init() call. Returns the number of elements
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * in the returned array. If the value is zero, the pointer
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * passed back will be NULL.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppomd_diff_removed(md_diff_cookie_t mdd, mde_cookie_t **mde_removedp)
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo return (-1);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Returns a pair of parallel arrays that contain nodes that were
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * considered matching based on the match criteria passed in to
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * a previous md_diff_init() call. Returns the number of elements
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * in the arrays. If the value is zero, both pointers passed back
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * will be NULL.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppomd_diff_matched(md_diff_cookie_t mdd, mde_cookie_t **mde_match1p,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo return (-1);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Deallocate any storage used to store results of a previous
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * md_diff_init() call. Returns 0 on success and -1 on failure.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo return (-1);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo MDD_FREE_CHECK(mddp, mddp->added.mdep, mddp->added.nelem *
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo MDD_FREE_CHECK(mddp, mddp->removed.mdep, mddp->removed.nelem *
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo MDD_FREE_CHECK(mddp, mddp->match1.mdep, mddp->match1.nelem *
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo MDD_FREE_CHECK(mddp, mddp->match2.mdep, mddp->match2.nelem *
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo return (0);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Walk the "fwd" DAG in an MD and return an array of nodes that are
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * of the specified type. The start param is used to start the walk
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * from an arbitrary location in the DAG. Returns an array of nodes
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * as well as a count of the number of nodes in the array. If the
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * count is zero, the node pointer will be passed back as NULL.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Returns: 0 success; -1 failure
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo mde_cookie_t start, char *compnodep, int *countp, mde_cookie_t **nodespp)
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo return (-1);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* get the number of nodes of interest in the DAG */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo *countp = md_scan_dag(mdp, start, cname, aname, NULL);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo if (*countp == 0) {
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo return (0);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* allocate the storage */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo *nodespp = mdip->allocp(sizeof (mde_cookie_t) * (*countp));
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* populate our array with the matching nodes */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo (void) md_scan_dag(mdp, start, cname, aname, *nodespp);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo return (0);
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Walk an array of nodes and check if there are any duplicate
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * nodes. A duplicate is determined based on the specified match
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * criteria. Returns B_TRUE if there are any duplicates and B_FALSE
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * otherwise.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppomdd_any_dup_nodes(md_impl_t *mdp, md_prop_match_t *pmp, int count,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo match = mdd_node_list_match(mdp, mdp, elem, nodesp, NULL,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Given a node and a array of nodes, compare the node to all elements
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * in the specified start-end range of the array. If the node matches
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * one of the nodes in the array, return the index of that node. Otherwise
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * return MD_DIFF_NOMATCH.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * The optional seen array parameter can be used to optimize repeated
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * calls to this function. If the seen array indicates that an element
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * has already been matched, the full comparison is not necessary.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppomdd_node_list_match(md_impl_t *md1, md_impl_t *md2, md_element_t *match_nodep,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo mde_cookie_t *match_listp, uint8_t *match_seenp, int start, int end,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Given two nodes and a list of properties, compare the nodes.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * A match is concluded if both nodes have all of the specified
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * properties and all the values of those properties are the
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * same. Returns MD_DIFF_NOMATCH if the nodes do not match and
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * MD_DIFF_MATCH otherwise.
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppomdd_node_compare(md_impl_t *mdap, md_impl_t *mdbp, md_element_t *nodeap,
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* make sure we are starting at the beginning of the nodes */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo if ((MDE_TAG(nodeap) != MDET_NODE) || (MDE_TAG(nodebp) != MDET_NODE))
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo for (idx = 0; match_elemsp[idx].type != MDET_LIST_END; idx++) {
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Check node A for the property of interest
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo for (ap = nodeap; MDE_TAG(ap) != MDET_NODE_END; ap++) {
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* found the property of interest */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* node A is not of interest */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Check node B for the property of interest
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo for (bp = nodebp; MDE_TAG(bp) != MDET_NODE_END; bp++) {
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* node B is not of interest */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * Both nodes have the property of interest. The
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * nodes are not a match unless the value of that
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * property match
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo /* unsupported prop type */
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * All the specified properties exist in both
1ae0874509b6811fdde1dfd46f0d93fd09867a3fheppo * nodes and have the same value. The two nodes