xref: /titanic_41/usr/src/common/mdesc/mdesc_diff.c (revision 1ae0874509b6811fdde1dfd46f0d93fd09867a3f)
1 /*
2  * CDDL HEADER START
3  *
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.
7  *
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.
12  *
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]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 #pragma ident	"%Z%%M%	%I%	%E% SMI"
28 
29 #include <sys/types.h>
30 #ifdef _KERNEL
31 #include <sys/systm.h>
32 #else /* _KERNEL */
33 #include <string.h>
34 #include <strings.h>
35 #endif /* _KERNEL */
36 #include <sys/note.h>
37 #include <sys/mdesc.h>
38 #include <sys/mdesc_impl.h>
39 
40 #define	MDD_FREE_CHECK(mdp, ptr, sz)		\
41 	do {					\
42 		if (ptr) mdp->freep(ptr, sz);	\
43 	_NOTE(CONSTCOND) } while (0)
44 
45 #define	MD_DIFF_MAGIC			0x4D445F4449464621ull	/* 'MD_DIFF!' */
46 #define	MD_DIFF_NOMATCH			(-1)
47 #define	MD_DIFF_MATCH			(1)
48 
49 typedef struct {
50 	mde_cookie_t	*mdep;
51 	uint_t		nelem;
52 } md_diff_t;
53 
54 typedef struct {
55 	uint64_t	mdd_magic;
56 	md_diff_t	added;
57 	md_diff_t	removed;
58 	md_diff_t	match1;
59 	md_diff_t	match2;
60 	void 		*(*allocp)(size_t);
61 	void		(*freep)(void *, size_t);
62 } md_diff_impl_t;
63 
64 /*
65  * Internal utility functions
66  */
67 static int mdd_scan_for_nodes(md_t *mdp, mde_cookie_t start,
68     char *compnodep, int *countp, mde_cookie_t **nodespp);
69 
70 static boolean_t mdd_any_dup_nodes(md_impl_t *mdp, md_prop_match_t *pmp,
71     int count, mde_cookie_t *nodesp);
72 
73 static int mdd_node_list_match(md_impl_t *md1, md_impl_t *md2,
74     md_element_t *match_nodep, mde_cookie_t *match_listp,
75     uint8_t *match_seenp, int start, int end, md_prop_match_t *match_elemsp);
76 
77 static int mdd_node_compare(md_impl_t *mdap, md_impl_t *mdbp,
78     md_element_t *nodeap, md_element_t *nodebp, md_prop_match_t *match_elemsp);
79 
80 /*
81  * Given two DAGs and information about how to uniquely identify
82  * the nodes of interest, determine which nodes have been added
83  * to the second MD, removed from the first MD, or exist in both
84  * MDs. This information is recorded and can be accessed using the
85  * opaque cookie returned to the caller.
86  */
87 md_diff_cookie_t
md_diff_init(md_t * md1p,mde_cookie_t start1,md_t * md2p,mde_cookie_t start2,char * compnodep,md_prop_match_t * match_fieldsp)88 md_diff_init(md_t *md1p, mde_cookie_t start1, md_t *md2p, mde_cookie_t start2,
89     char *compnodep, md_prop_match_t *match_fieldsp)
90 {
91 	int		idx;
92 	md_impl_t	*md1 = (md_impl_t *)md1p;
93 	md_impl_t	*md2 = (md_impl_t *)md2p;
94 	mde_cookie_t	*md1nodesp = NULL;
95 	mde_cookie_t	*md2nodesp = NULL;
96 	int		md1count = 0;
97 	int		md2count = 0;
98 	uint8_t		*seenp = NULL;
99 
100 	/* variables used to gather results */
101 	md_diff_impl_t	*diff_res;
102 	mde_cookie_t	*mde_add_scr;
103 	mde_cookie_t	*mde_rem_scr;
104 	mde_cookie_t	*mde_match1_scr;
105 	mde_cookie_t	*mde_match2_scr;
106 	int		nadd = 0;
107 	int		nrem = 0;
108 	int		nmatch = 0;
109 
110 	/* sanity check params */
111 	if ((md1p == NULL) || (md2p == NULL))
112 		return (MD_INVAL_DIFF_COOKIE);
113 
114 	if ((start1 == MDE_INVAL_ELEM_COOKIE) ||
115 	    (start2 == MDE_INVAL_ELEM_COOKIE))
116 		return (MD_INVAL_DIFF_COOKIE);
117 
118 	if ((compnodep == NULL) || (match_fieldsp == NULL))
119 		return (MD_INVAL_DIFF_COOKIE);
120 
121 	/*
122 	 * Prepare an array of the matching nodes from the first MD.
123 	 */
124 	if (mdd_scan_for_nodes(md1p,
125 	    start1, compnodep, &md1count, &md1nodesp) == -1)
126 		return (MD_INVAL_DIFF_COOKIE);
127 
128 	/* sanity check that all nodes are unique */
129 	if (md1nodesp &&
130 	    mdd_any_dup_nodes(md1, match_fieldsp, md1count, md1nodesp)) {
131 		MDD_FREE_CHECK(md1, md1nodesp, sizeof (mde_cookie_t) *
132 		    md1count);
133 		return (MD_INVAL_DIFF_COOKIE);
134 	}
135 
136 
137 	/*
138 	 * Prepare an array of the matching nodes from the second MD.
139 	 */
140 	if (mdd_scan_for_nodes(md2p,
141 	    start2, compnodep, &md2count, &md2nodesp) == -1)
142 		return (MD_INVAL_DIFF_COOKIE);
143 
144 	/* sanity check that all nodes are unique */
145 	if (md2nodesp &&
146 	    mdd_any_dup_nodes(md2, match_fieldsp, md2count, md2nodesp)) {
147 		MDD_FREE_CHECK(md1, md1nodesp, sizeof (mde_cookie_t) *
148 		    md1count);
149 		MDD_FREE_CHECK(md2, md2nodesp, sizeof (mde_cookie_t) *
150 		    md2count);
151 		return (MD_INVAL_DIFF_COOKIE);
152 	}
153 
154 	/* setup our result structure */
155 	diff_res = md1->allocp(sizeof (md_diff_impl_t));
156 	bzero(diff_res, sizeof (md_diff_impl_t));
157 	diff_res->allocp = md1->allocp;
158 	diff_res->freep = md1->freep;
159 	diff_res->mdd_magic = MD_DIFF_MAGIC;
160 
161 	/*
162 	 * Special cases for empty lists
163 	 */
164 	if ((md1count == 0) && (md2count != 0)) {
165 		/* all the nodes found were added */
166 		diff_res->added.mdep = md2nodesp;
167 		diff_res->added.nelem = md2count;
168 		return ((mde_cookie_t)diff_res);
169 	}
170 
171 	if ((md1count != 0) && (md2count == 0)) {
172 		/* all the nodes found were removed */
173 		diff_res->removed.mdep = md1nodesp;
174 		diff_res->removed.nelem = md1count;
175 		return ((mde_cookie_t)diff_res);
176 	}
177 
178 	if ((md1count == 0) && (md2count == 0))
179 		/* no nodes found */
180 		return ((mde_cookie_t)diff_res);
181 
182 	/*
183 	 * Both lists have some elements. Allocate some scratch
184 	 * buffers to sort them into our three categories, added,
185 	 * removed, and matched pairs.
186 	 */
187 	mde_add_scr = diff_res->allocp(sizeof (mde_cookie_t) * md2count);
188 	mde_rem_scr = diff_res->allocp(sizeof (mde_cookie_t) * md1count);
189 	mde_match1_scr = diff_res->allocp(sizeof (mde_cookie_t) * md1count);
190 	mde_match2_scr = diff_res->allocp(sizeof (mde_cookie_t) * md2count);
191 
192 	/* array of seen flags only needed for md2 */
193 	seenp = (uint8_t *)diff_res->allocp(sizeof (uint8_t) * md2count);
194 	bzero(seenp, sizeof (uint8_t) * md2count);
195 
196 	/*
197 	 * Make a pass through the md1 node array. Make note of
198 	 * any nodes not in the md2 array, indicating that they
199 	 * have been removed. Also keep track of the nodes that
200 	 * are present in both arrays for the matched pair results.
201 	 */
202 	for (idx = 0; idx < md1count; idx++) {
203 
204 		md_element_t *elem = &(md1->mdep[md1nodesp[idx]]);
205 
206 		int match = mdd_node_list_match(md1, md2, elem, md2nodesp,
207 		    seenp, 0, md2count - 1, match_fieldsp);
208 
209 		if (match == MD_DIFF_NOMATCH)
210 			/* record deleted node */
211 			mde_rem_scr[nrem++] = md1nodesp[idx];
212 		else {
213 			/* record matched node pair */
214 			mde_match1_scr[nmatch] = md1nodesp[idx];
215 			mde_match2_scr[nmatch] = md2nodesp[match];
216 			nmatch++;
217 
218 			/* mark that this match has been recorded */
219 			seenp[match] = 1;
220 		}
221 	}
222 
223 	/*
224 	 * Make a pass through the md2 array. Any nodes that have
225 	 * not been marked as seen have been added.
226 	 */
227 	for (idx = 0; idx < md2count; idx++) {
228 		if (!seenp[idx])
229 			/* record added node */
230 			mde_add_scr[nadd++] = md2nodesp[idx];
231 	}
232 
233 	/* fill in the added node list */
234 	if (nadd) {
235 		int addsz = sizeof (mde_cookie_t) * nadd;
236 		diff_res->added.mdep = (mde_cookie_t *)diff_res->allocp(addsz);
237 
238 		bcopy(mde_add_scr, diff_res->added.mdep, addsz);
239 
240 		diff_res->added.nelem = nadd;
241 	}
242 
243 	/* fill in the removed node list */
244 	if (nrem) {
245 		int remsz = sizeof (mde_cookie_t) * nrem;
246 		diff_res->removed.mdep =
247 		    (mde_cookie_t *)diff_res->allocp(remsz);
248 
249 		bcopy(mde_rem_scr, diff_res->removed.mdep, remsz);
250 		diff_res->removed.nelem = nrem;
251 	}
252 
253 	/* fill in the matching node lists */
254 	if (nmatch) {
255 		int matchsz = sizeof (mde_cookie_t) * nmatch;
256 		diff_res->match1.mdep =
257 		    (mde_cookie_t *)diff_res->allocp(matchsz);
258 		diff_res->match2.mdep =
259 		    (mde_cookie_t *)diff_res->allocp(matchsz);
260 
261 		bcopy(mde_match1_scr, diff_res->match1.mdep, matchsz);
262 		bcopy(mde_match2_scr, diff_res->match2.mdep, matchsz);
263 		diff_res->match1.nelem = nmatch;
264 		diff_res->match2.nelem = nmatch;
265 	}
266 
267 	/* clean up */
268 	md1->freep(md1nodesp, sizeof (mde_cookie_t) * md1count);
269 	md2->freep(md2nodesp, sizeof (mde_cookie_t) * md2count);
270 
271 	diff_res->freep(mde_add_scr, sizeof (mde_cookie_t) * md2count);
272 	diff_res->freep(mde_rem_scr, sizeof (mde_cookie_t) * md1count);
273 	diff_res->freep(mde_match1_scr, sizeof (mde_cookie_t) * md1count);
274 	diff_res->freep(mde_match2_scr, sizeof (mde_cookie_t) * md2count);
275 
276 	diff_res->freep(seenp, sizeof (uint8_t) * md2count);
277 
278 	return ((md_diff_cookie_t)diff_res);
279 }
280 
281 /*
282  * Returns an array of the nodes added to the second MD in a
283  * previous md_diff_init() call. Returns the number of elements
284  * in the returned array. If the value is zero, the pointer
285  * passed back will be NULL.
286  */
287 int
md_diff_added(md_diff_cookie_t mdd,mde_cookie_t ** mde_addedp)288 md_diff_added(md_diff_cookie_t mdd, mde_cookie_t **mde_addedp)
289 {
290 	md_diff_impl_t	*mddp = (md_diff_impl_t *)mdd;
291 
292 	if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
293 		return (-1);
294 
295 	*mde_addedp = mddp->added.mdep;
296 
297 	return (mddp->added.nelem);
298 }
299 
300 /*
301  * Returns an array of the nodes removed from the first MD in a
302  * previous md_diff_init() call. Returns the number of elements
303  * in the returned array. If the value is zero, the pointer
304  * passed back will be NULL.
305  */
306 int
md_diff_removed(md_diff_cookie_t mdd,mde_cookie_t ** mde_removedp)307 md_diff_removed(md_diff_cookie_t mdd, mde_cookie_t **mde_removedp)
308 {
309 	md_diff_impl_t	*mddp = (md_diff_impl_t *)mdd;
310 
311 	if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
312 		return (-1);
313 
314 	*mde_removedp = mddp->removed.mdep;
315 
316 	return (mddp->removed.nelem);
317 }
318 
319 /*
320  * Returns a pair of parallel arrays that contain nodes that were
321  * considered matching based on the match criteria passed in to
322  * a previous md_diff_init() call. Returns the number of elements
323  * in the arrays. If the value is zero, both pointers passed back
324  * will be NULL.
325  */
326 int
md_diff_matched(md_diff_cookie_t mdd,mde_cookie_t ** mde_match1p,mde_cookie_t ** mde_match2p)327 md_diff_matched(md_diff_cookie_t mdd, mde_cookie_t **mde_match1p,
328     mde_cookie_t **mde_match2p)
329 {
330 	md_diff_impl_t	*mddp = (md_diff_impl_t *)mdd;
331 
332 	if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
333 		return (-1);
334 
335 	*mde_match1p = mddp->match1.mdep;
336 	*mde_match2p = mddp->match2.mdep;
337 
338 	return (mddp->match1.nelem);
339 }
340 
341 /*
342  * Deallocate any storage used to store results of a previous
343  * md_diff_init() call. Returns 0 on success and -1 on failure.
344  */
345 int
md_diff_fini(md_diff_cookie_t mdd)346 md_diff_fini(md_diff_cookie_t mdd)
347 {
348 	md_diff_impl_t	*mddp = (md_diff_impl_t *)mdd;
349 
350 	if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
351 		return (-1);
352 
353 	mddp->mdd_magic = 0;
354 
355 	MDD_FREE_CHECK(mddp, mddp->added.mdep, mddp->added.nelem *
356 	    sizeof (mde_cookie_t));
357 
358 	MDD_FREE_CHECK(mddp, mddp->removed.mdep, mddp->removed.nelem *
359 	    sizeof (mde_cookie_t));
360 
361 	MDD_FREE_CHECK(mddp, mddp->match1.mdep, mddp->match1.nelem *
362 	    sizeof (mde_cookie_t));
363 
364 	MDD_FREE_CHECK(mddp, mddp->match2.mdep, mddp->match2.nelem *
365 	    sizeof (mde_cookie_t));
366 
367 	mddp->freep(mddp, sizeof (md_diff_impl_t));
368 
369 	return (0);
370 }
371 
372 /*
373  * Walk the "fwd" DAG in an MD and return an array of nodes that are
374  * of the specified type. The start param is used to start the walk
375  * from an arbitrary location in the DAG. Returns an array of nodes
376  * as well as a count of the number of nodes in the array.  If the
377  * count is zero, the node pointer will be passed back as NULL.
378  *
379  * Returns: 0 success; -1 failure
380  */
381 static int
mdd_scan_for_nodes(md_t * mdp,mde_cookie_t start,char * compnodep,int * countp,mde_cookie_t ** nodespp)382 mdd_scan_for_nodes(md_t *mdp,
383     mde_cookie_t start, char *compnodep, int *countp, mde_cookie_t **nodespp)
384 {
385 	mde_str_cookie_t	cname;
386 	mde_str_cookie_t	aname;
387 	md_impl_t		*mdip = (md_impl_t *)mdp;
388 
389 	if (mdip == NULL)
390 		return (-1);
391 
392 	cname = md_find_name(mdp, compnodep);
393 	aname = md_find_name(mdp, "fwd");
394 
395 	/* get the number of nodes of interest in the DAG */
396 	*countp = md_scan_dag(mdp, start, cname, aname, NULL);
397 	if (*countp == 0) {
398 		*nodespp = NULL;
399 		return (0);
400 	}
401 
402 	/* allocate the storage */
403 	*nodespp = mdip->allocp(sizeof (mde_cookie_t) * (*countp));
404 
405 	/* populate our array with the matching nodes */
406 	(void) md_scan_dag(mdp, start, cname, aname, *nodespp);
407 
408 	return (0);
409 }
410 
411 /*
412  * Walk an array of nodes and check if there are any duplicate
413  * nodes. A duplicate is determined based on the specified match
414  * criteria. Returns B_TRUE if there are any duplicates and B_FALSE
415  * otherwise.
416  */
417 static boolean_t
mdd_any_dup_nodes(md_impl_t * mdp,md_prop_match_t * pmp,int count,mde_cookie_t * nodesp)418 mdd_any_dup_nodes(md_impl_t *mdp, md_prop_match_t *pmp, int count,
419     mde_cookie_t *nodesp)
420 {
421 	int		idx;
422 	int		match;
423 	md_element_t	*elem;
424 
425 	ASSERT(count > 0 || nodesp == NULL);
426 
427 	for (idx = 0; idx < count; idx++) {
428 		elem = &(mdp->mdep[nodesp[idx]]);
429 
430 		match = mdd_node_list_match(mdp, mdp, elem, nodesp, NULL,
431 		    idx + 1, count - 1, pmp);
432 
433 		if (match != MD_DIFF_NOMATCH)
434 			return (B_TRUE);
435 	}
436 
437 	return (B_FALSE);
438 }
439 
440 /*
441  * Given a node and a array of nodes, compare the node to all elements
442  * in the specified start-end range of the array. If the node matches
443  * one of the nodes in the array, return the index of that node. Otherwise
444  * return MD_DIFF_NOMATCH.
445  *
446  * The optional seen array parameter can be used to optimize repeated
447  * calls to this function. If the seen array indicates that an element
448  * has already been matched, the full comparison is not necessary.
449  */
450 static int
mdd_node_list_match(md_impl_t * md1,md_impl_t * md2,md_element_t * match_nodep,mde_cookie_t * match_listp,uint8_t * match_seenp,int start,int end,md_prop_match_t * match_elemsp)451 mdd_node_list_match(md_impl_t *md1, md_impl_t *md2, md_element_t *match_nodep,
452     mde_cookie_t *match_listp, uint8_t *match_seenp, int start, int end,
453     md_prop_match_t *match_elemsp)
454 {
455 	int		match;
456 	int		idx;
457 	md_element_t	*elem;
458 
459 	for (idx = start; idx <= end; idx++) {
460 
461 		if ((match_seenp != NULL) && (match_seenp[idx]))
462 			continue;
463 
464 		elem = &(md2->mdep[match_listp[idx]]);
465 
466 		match = mdd_node_compare(md1, md2, match_nodep, elem,
467 		    match_elemsp);
468 		if (match == MD_DIFF_MATCH)
469 			return (idx);
470 	}
471 
472 	return (MD_DIFF_NOMATCH);
473 }
474 
475 /*
476  * Given two nodes and a list of properties, compare the nodes.
477  * A match is concluded if both nodes have all of the specified
478  * properties and all the values of those properties are the
479  * same. Returns MD_DIFF_NOMATCH if the nodes do not match and
480  * MD_DIFF_MATCH otherwise.
481  */
482 static int
mdd_node_compare(md_impl_t * mdap,md_impl_t * mdbp,md_element_t * nodeap,md_element_t * nodebp,md_prop_match_t * match_elemsp)483 mdd_node_compare(md_impl_t *mdap, md_impl_t *mdbp, md_element_t *nodeap,
484     md_element_t *nodebp, md_prop_match_t *match_elemsp)
485 {
486 	md_element_t	*ap;
487 	md_element_t	*bp;
488 	boolean_t	nodea_interest;
489 	boolean_t	nodeb_interest;
490 	int		idx;
491 
492 	/* make sure we are starting at the beginning of the nodes */
493 	if ((MDE_TAG(nodeap) != MDET_NODE) || (MDE_TAG(nodebp) != MDET_NODE))
494 		return (MD_DIFF_NOMATCH);
495 
496 	for (idx = 0; match_elemsp[idx].type != MDET_LIST_END; idx++) {
497 
498 		int type;
499 
500 		nodea_interest = B_FALSE;
501 		nodeb_interest = B_FALSE;
502 
503 		type = match_elemsp[idx].type;
504 
505 		/*
506 		 * Check node A for the property of interest
507 		 */
508 		for (ap = nodeap; MDE_TAG(ap) != MDET_NODE_END; ap++) {
509 			char *elemname;
510 
511 			if (MDE_TAG(ap) != type)
512 				continue;
513 
514 			elemname = mdap->namep + MDE_NAME(ap);
515 
516 			if (strcmp(elemname, match_elemsp[idx].namep) == 0) {
517 				/* found the property of interest */
518 				nodea_interest = B_TRUE;
519 				break;
520 			}
521 		}
522 
523 		/* node A is not of interest */
524 		if (!nodea_interest)
525 			return (MD_DIFF_NOMATCH);
526 
527 		/*
528 		 * Check node B for the property of interest
529 		 */
530 		for (bp = nodebp; MDE_TAG(bp) != MDET_NODE_END; bp++) {
531 			char *elemname;
532 
533 			if (MDE_TAG(bp) != type)
534 				continue;
535 
536 			elemname = mdbp->namep + MDE_NAME(bp);
537 
538 			if (strcmp(elemname, match_elemsp[idx].namep) == 0) {
539 				nodeb_interest = B_TRUE;
540 				break;
541 			}
542 		}
543 
544 		/* node B is not of interest */
545 		if (!nodeb_interest)
546 			return (MD_DIFF_NOMATCH);
547 
548 		/*
549 		 * Both nodes have the property of interest. The
550 		 * nodes are not a match unless the value of that
551 		 * property match
552 		 */
553 		switch (type) {
554 		case MDET_PROP_VAL:
555 			if (MDE_PROP_VALUE(ap) != MDE_PROP_VALUE(bp))
556 				return (MD_DIFF_NOMATCH);
557 			break;
558 
559 		case MDET_PROP_STR: {
560 			char *stra = (char *)(mdap->datap +
561 			    MDE_PROP_DATA_OFFSET(ap));
562 			char *strb = (char *)(mdbp->datap +
563 			    MDE_PROP_DATA_OFFSET(bp));
564 
565 			if (strcmp(stra, strb) != 0)
566 				return (MD_DIFF_NOMATCH);
567 			break;
568 		}
569 
570 		case MDET_PROP_DAT: {
571 
572 			caddr_t dataa;
573 			caddr_t datab;
574 
575 			if (MDE_PROP_DATA_LEN(ap) != MDE_PROP_DATA_LEN(bp))
576 				return (MD_DIFF_NOMATCH);
577 
578 			dataa = (caddr_t)(mdap->datap +
579 			    MDE_PROP_DATA_OFFSET(ap));
580 			datab = (caddr_t)(mdbp->datap +
581 			    MDE_PROP_DATA_OFFSET(bp));
582 
583 			if (memcmp(dataa, datab, MDE_PROP_DATA_LEN(ap)) != 0)
584 				return (MD_DIFF_NOMATCH);
585 
586 			break;
587 		}
588 
589 		default:
590 			/* unsupported prop type */
591 			return (MD_DIFF_NOMATCH);
592 		}
593 	}
594 
595 	/*
596 	 * All the specified properties exist in both
597 	 * nodes and have the same value. The two nodes
598 	 * match.
599 	 */
600 
601 	return (MD_DIFF_MATCH);
602 }
603