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