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