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