4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
24 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
25 * Use is subject to license terms.
28 #pragma ident "@(#)mdesc_diff.c 1.1 06/05/16 SMI"
30 #include <sys/types.h>
32 #include <sys/systm.h>
38 #include <sys/mdesc.h>
39 #include <sys/mdesc_impl.h>
41 #define MDD_FREE_CHECK(mdp, ptr, sz) \
43 if (ptr) mdp->freep(ptr, sz); \
44 _NOTE(CONSTCOND) } while (0)
46 #define MD_DIFF_MAGIC 0x4D445F4449464621ull /* 'MD_DIFF!' */
47 #define MD_DIFF_NOMATCH (-1)
48 #define MD_DIFF_MATCH (1)
61 void *(*allocp)(size_t);
62 void (*freep)(void *, size_t);
66 * Internal utility functions
68 static int mdd_scan_for_nodes(md_t *mdp, mde_cookie_t start,
69 char *compnodep, int *countp, mde_cookie_t **nodespp);
71 static boolean_t mdd_any_dup_nodes(md_impl_t *mdp, md_prop_match_t *pmp,
72 int count, mde_cookie_t *nodesp);
74 static int mdd_node_list_match(md_impl_t *md1, md_impl_t *md2,
75 md_element_t *match_nodep, mde_cookie_t *match_listp,
76 uint8_t *match_seenp, int start, int end, md_prop_match_t *match_elemsp);
78 static int mdd_node_compare(md_impl_t *mdap, md_impl_t *mdbp,
79 md_element_t *nodeap, md_element_t *nodebp, md_prop_match_t *match_elemsp);
82 * Given two DAGs and information about how to uniquely identify
83 * the nodes of interest, determine which nodes have been added
84 * to the second MD, removed from the first MD, or exist in both
85 * MDs. This information is recorded and can be accessed using the
86 * opaque cookie returned to the caller.
89 md_diff_init(md_t *md1p, mde_cookie_t start1, md_t *md2p, mde_cookie_t start2,
90 char *compnodep, md_prop_match_t *match_fieldsp)
93 md_impl_t *md1 = (md_impl_t *)md1p;
94 md_impl_t *md2 = (md_impl_t *)md2p;
95 mde_cookie_t *md1nodesp = NULL;
96 mde_cookie_t *md2nodesp = NULL;
99 uint8_t *seenp = NULL;
101 /* variables used to gather results */
102 md_diff_impl_t *diff_res;
103 mde_cookie_t *mde_add_scr;
104 mde_cookie_t *mde_rem_scr;
105 mde_cookie_t *mde_match1_scr;
106 mde_cookie_t *mde_match2_scr;
111 /* sanity check params */
112 if ((md1p == NULL) || (md2p == NULL))
113 return (MD_INVAL_DIFF_COOKIE);
115 if ((start1 == MDE_INVAL_ELEM_COOKIE) ||
116 (start2 == MDE_INVAL_ELEM_COOKIE))
117 return (MD_INVAL_DIFF_COOKIE);
119 if ((compnodep == NULL) || (match_fieldsp == NULL))
120 return (MD_INVAL_DIFF_COOKIE);
123 * Prepare an array of the matching nodes from the first MD.
125 if (mdd_scan_for_nodes(md1p,
126 start1, compnodep, &md1count, &md1nodesp) == -1)
127 return (MD_INVAL_DIFF_COOKIE);
129 /* sanity check that all nodes are unique */
131 mdd_any_dup_nodes(md1, match_fieldsp, md1count, md1nodesp)) {
132 MDD_FREE_CHECK(md1, md1nodesp, sizeof (mde_cookie_t) *
134 return (MD_INVAL_DIFF_COOKIE);
139 * Prepare an array of the matching nodes from the second MD.
141 if (mdd_scan_for_nodes(md2p,
142 start2, compnodep, &md2count, &md2nodesp) == -1)
143 return (MD_INVAL_DIFF_COOKIE);
145 /* sanity check that all nodes are unique */
147 mdd_any_dup_nodes(md2, match_fieldsp, md2count, md2nodesp)) {
148 MDD_FREE_CHECK(md1, md1nodesp, sizeof (mde_cookie_t) *
150 MDD_FREE_CHECK(md2, md2nodesp, sizeof (mde_cookie_t) *
152 return (MD_INVAL_DIFF_COOKIE);
155 /* setup our result structure */
156 diff_res = md1->allocp(sizeof (md_diff_impl_t));
157 bzero(diff_res, sizeof (md_diff_impl_t));
158 diff_res->allocp = md1->allocp;
159 diff_res->freep = md1->freep;
160 diff_res->mdd_magic = MD_DIFF_MAGIC;
163 * Special cases for empty lists
165 if ((md1count == 0) && (md2count != 0)) {
166 /* all the nodes found were added */
167 diff_res->added.mdep = md2nodesp;
168 diff_res->added.nelem = md2count;
169 return ((mde_cookie_t)diff_res);
172 if ((md1count != 0) && (md2count == 0)) {
173 /* all the nodes found were removed */
174 diff_res->removed.mdep = md1nodesp;
175 diff_res->removed.nelem = md1count;
176 return ((mde_cookie_t)diff_res);
179 if ((md1count == 0) && (md2count == 0))
181 return ((mde_cookie_t)diff_res);
184 * Both lists have some elements. Allocate some scratch
185 * buffers to sort them into our three categories, added,
186 * removed, and matched pairs.
188 mde_add_scr = diff_res->allocp(sizeof (mde_cookie_t) * md2count);
189 mde_rem_scr = diff_res->allocp(sizeof (mde_cookie_t) * md1count);
190 mde_match1_scr = diff_res->allocp(sizeof (mde_cookie_t) * md1count);
191 mde_match2_scr = diff_res->allocp(sizeof (mde_cookie_t) * md2count);
193 /* array of seen flags only needed for md2 */
194 seenp = (uint8_t *)diff_res->allocp(sizeof (uint8_t) * md2count);
195 bzero(seenp, sizeof (uint8_t) * md2count);
198 * Make a pass through the md1 node array. Make note of
199 * any nodes not in the md2 array, indicating that they
200 * have been removed. Also keep track of the nodes that
201 * are present in both arrays for the matched pair results.
203 for (idx = 0; idx < md1count; idx++) {
205 md_element_t *elem = &(md1->mdep[md1nodesp[idx]]);
207 int match = mdd_node_list_match(md1, md2, elem, md2nodesp,
208 seenp, 0, md2count - 1, match_fieldsp);
210 if (match == MD_DIFF_NOMATCH)
211 /* record deleted node */
212 mde_rem_scr[nrem++] = md1nodesp[idx];
214 /* record matched node pair */
215 mde_match1_scr[nmatch] = md1nodesp[idx];
216 mde_match2_scr[nmatch] = md2nodesp[match];
219 /* mark that this match has been recorded */
225 * Make a pass through the md2 array. Any nodes that have
226 * not been marked as seen have been added.
228 for (idx = 0; idx < md2count; idx++) {
230 /* record added node */
231 mde_add_scr[nadd++] = md2nodesp[idx];
234 /* fill in the added node list */
236 int addsz = sizeof (mde_cookie_t) * nadd;
237 diff_res->added.mdep = (mde_cookie_t *)diff_res->allocp(addsz);
239 bcopy(mde_add_scr, diff_res->added.mdep, addsz);
241 diff_res->added.nelem = nadd;
244 /* fill in the removed node list */
246 int remsz = sizeof (mde_cookie_t) * nrem;
247 diff_res->removed.mdep =
248 (mde_cookie_t *)diff_res->allocp(remsz);
250 bcopy(mde_rem_scr, diff_res->removed.mdep, remsz);
251 diff_res->removed.nelem = nrem;
254 /* fill in the matching node lists */
256 int matchsz = sizeof (mde_cookie_t) * nmatch;
257 diff_res->match1.mdep =
258 (mde_cookie_t *)diff_res->allocp(matchsz);
259 diff_res->match2.mdep =
260 (mde_cookie_t *)diff_res->allocp(matchsz);
262 bcopy(mde_match1_scr, diff_res->match1.mdep, matchsz);
263 bcopy(mde_match2_scr, diff_res->match2.mdep, matchsz);
264 diff_res->match1.nelem = nmatch;
265 diff_res->match2.nelem = nmatch;
269 md1->freep(md1nodesp, sizeof (mde_cookie_t) * md1count);
270 md2->freep(md2nodesp, sizeof (mde_cookie_t) * md2count);
272 diff_res->freep(mde_add_scr, sizeof (mde_cookie_t) * md2count);
273 diff_res->freep(mde_rem_scr, sizeof (mde_cookie_t) * md1count);
274 diff_res->freep(mde_match1_scr, sizeof (mde_cookie_t) * md1count);
275 diff_res->freep(mde_match2_scr, sizeof (mde_cookie_t) * md2count);
277 diff_res->freep(seenp, sizeof (uint8_t) * md2count);
279 return ((md_diff_cookie_t)diff_res);
283 * Returns an array of the nodes added to the second MD in a
284 * previous md_diff_init() call. Returns the number of elements
285 * in the returned array. If the value is zero, the pointer
286 * passed back will be NULL.
289 md_diff_added(md_diff_cookie_t mdd, mde_cookie_t **mde_addedp)
291 md_diff_impl_t *mddp = (md_diff_impl_t *)mdd;
293 if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
296 *mde_addedp = mddp->added.mdep;
298 return (mddp->added.nelem);
302 * Returns an array of the nodes removed from the first MD in a
303 * previous md_diff_init() call. Returns the number of elements
304 * in the returned array. If the value is zero, the pointer
305 * passed back will be NULL.
308 md_diff_removed(md_diff_cookie_t mdd, mde_cookie_t **mde_removedp)
310 md_diff_impl_t *mddp = (md_diff_impl_t *)mdd;
312 if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
315 *mde_removedp = mddp->removed.mdep;
317 return (mddp->removed.nelem);
321 * Returns a pair of parallel arrays that contain nodes that were
322 * considered matching based on the match criteria passed in to
323 * a previous md_diff_init() call. Returns the number of elements
324 * in the arrays. If the value is zero, both pointers passed back
328 md_diff_matched(md_diff_cookie_t mdd, mde_cookie_t **mde_match1p,
329 mde_cookie_t **mde_match2p)
331 md_diff_impl_t *mddp = (md_diff_impl_t *)mdd;
333 if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
336 *mde_match1p = mddp->match1.mdep;
337 *mde_match2p = mddp->match2.mdep;
339 return (mddp->match1.nelem);
343 * Deallocate any storage used to store results of a previous
344 * md_diff_init() call. Returns 0 on success and -1 on failure.
347 md_diff_fini(md_diff_cookie_t mdd)
349 md_diff_impl_t *mddp = (md_diff_impl_t *)mdd;
351 if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
356 MDD_FREE_CHECK(mddp, mddp->added.mdep, mddp->added.nelem *
357 sizeof (mde_cookie_t));
359 MDD_FREE_CHECK(mddp, mddp->removed.mdep, mddp->removed.nelem *
360 sizeof (mde_cookie_t));
362 MDD_FREE_CHECK(mddp, mddp->match1.mdep, mddp->match1.nelem *
363 sizeof (mde_cookie_t));
365 MDD_FREE_CHECK(mddp, mddp->match2.mdep, mddp->match2.nelem *
366 sizeof (mde_cookie_t));
368 mddp->freep(mddp, sizeof (md_diff_impl_t));
374 * Walk the "fwd" DAG in an MD and return an array of nodes that are
375 * of the specified type. The start param is used to start the walk
376 * from an arbitrary location in the DAG. Returns an array of nodes
377 * as well as a count of the number of nodes in the array. If the
378 * count is zero, the node pointer will be passed back as NULL.
380 * Returns: 0 success; -1 failure
383 mdd_scan_for_nodes(md_t *mdp,
384 mde_cookie_t start, char *compnodep, int *countp, mde_cookie_t **nodespp)
386 mde_str_cookie_t cname;
387 mde_str_cookie_t aname;
388 md_impl_t *mdip = (md_impl_t *)mdp;
393 cname = md_find_name(mdp, compnodep);
394 aname = md_find_name(mdp, "fwd");
396 /* get the number of nodes of interest in the DAG */
397 *countp = md_scan_dag(mdp, start, cname, aname, NULL);
403 /* allocate the storage */
404 *nodespp = mdip->allocp(sizeof (mde_cookie_t) * (*countp));
406 /* populate our array with the matching nodes */
407 (void) md_scan_dag(mdp, start, cname, aname, *nodespp);
413 * Walk an array of nodes and check if there are any duplicate
414 * nodes. A duplicate is determined based on the specified match
415 * criteria. Returns B_TRUE if there are any duplicates and B_FALSE
419 mdd_any_dup_nodes(md_impl_t *mdp, md_prop_match_t *pmp, int count,
420 mde_cookie_t *nodesp)
426 ASSERT(count > 0 || nodesp == NULL);
428 for (idx = 0; idx < count; idx++) {
429 elem = &(mdp->mdep[nodesp[idx]]);
431 match = mdd_node_list_match(mdp, mdp, elem, nodesp, NULL,
432 idx + 1, count - 1, pmp);
434 if (match != MD_DIFF_NOMATCH)
442 * Given a node and a array of nodes, compare the node to all elements
443 * in the specified start-end range of the array. If the node matches
444 * one of the nodes in the array, return the index of that node. Otherwise
445 * return MD_DIFF_NOMATCH.
447 * The optional seen array parameter can be used to optimize repeated
448 * calls to this function. If the seen array indicates that an element
449 * has already been matched, the full comparison is not necessary.
452 mdd_node_list_match(md_impl_t *md1, md_impl_t *md2, md_element_t *match_nodep,
453 mde_cookie_t *match_listp, uint8_t *match_seenp, int start, int end,
454 md_prop_match_t *match_elemsp)
460 for (idx = start; idx <= end; idx++) {
462 if ((match_seenp != NULL) && (match_seenp[idx]))
465 elem = &(md2->mdep[match_listp[idx]]);
467 match = mdd_node_compare(md1, md2, match_nodep, elem,
469 if (match == MD_DIFF_MATCH)
473 return (MD_DIFF_NOMATCH);
477 * Given two nodes and a list of properties, compare the nodes.
478 * A match is concluded if both nodes have all of the specified
479 * properties and all the values of those properties are the
480 * same. Returns MD_DIFF_NOMATCH if the nodes do not match and
481 * MD_DIFF_MATCH otherwise.
484 mdd_node_compare(md_impl_t *mdap, md_impl_t *mdbp, md_element_t *nodeap,
485 md_element_t *nodebp, md_prop_match_t *match_elemsp)
489 boolean_t nodea_interest;
490 boolean_t nodeb_interest;
493 /* make sure we are starting at the beginning of the nodes */
494 if ((MDE_TAG(nodeap) != MDET_NODE) || (MDE_TAG(nodebp) != MDET_NODE))
495 return (MD_DIFF_NOMATCH);
497 for (idx = 0; match_elemsp[idx].type != MDET_LIST_END; idx++) {
501 nodea_interest = B_FALSE;
502 nodeb_interest = B_FALSE;
504 type = match_elemsp[idx].type;
507 * Check node A for the property of interest
509 for (ap = nodeap; MDE_TAG(ap) != MDET_NODE_END; ap++) {
512 if (MDE_TAG(ap) != type)
515 elemname = mdap->namep + MDE_NAME(ap);
517 if (strcmp(elemname, match_elemsp[idx].namep) == 0) {
518 /* found the property of interest */
519 nodea_interest = B_TRUE;
524 /* node A is not of interest */
526 return (MD_DIFF_NOMATCH);
529 * Check node B for the property of interest
531 for (bp = nodebp; MDE_TAG(bp) != MDET_NODE_END; bp++) {
534 if (MDE_TAG(bp) != type)
537 elemname = mdbp->namep + MDE_NAME(bp);
539 if (strcmp(elemname, match_elemsp[idx].namep) == 0) {
540 nodeb_interest = B_TRUE;
545 /* node B is not of interest */
547 return (MD_DIFF_NOMATCH);
550 * Both nodes have the property of interest. The
551 * nodes are not a match unless the value of that
556 if (MDE_PROP_VALUE(ap) != MDE_PROP_VALUE(bp))
557 return (MD_DIFF_NOMATCH);
560 case MDET_PROP_STR: {
561 char *stra = (char *)(mdap->datap +
562 MDE_PROP_DATA_OFFSET(ap));
563 char *strb = (char *)(mdbp->datap +
564 MDE_PROP_DATA_OFFSET(bp));
566 if (strcmp(stra, strb) != 0)
567 return (MD_DIFF_NOMATCH);
571 case MDET_PROP_DAT: {
576 if (MDE_PROP_DATA_LEN(ap) != MDE_PROP_DATA_LEN(bp))
577 return (MD_DIFF_NOMATCH);
579 dataa = (caddr_t)(mdap->datap +
580 MDE_PROP_DATA_OFFSET(ap));
581 datab = (caddr_t)(mdbp->datap +
582 MDE_PROP_DATA_OFFSET(bp));
584 if (memcmp(dataa, datab, MDE_PROP_DATA_LEN(ap)) != 0)
585 return (MD_DIFF_NOMATCH);
591 /* unsupported prop type */
592 return (MD_DIFF_NOMATCH);
597 * All the specified properties exist in both
598 * nodes and have the same value. The two nodes
602 return (MD_DIFF_MATCH);