sys/sun4v/cddl/mdesc/mdesc_diff.c

   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  * $FreeBSD$
  21  */
  22
  23 /*
  24  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
  25  * Use is subject to license terms.
  26  */
  27
  28 #pragma ident   "@(#)mdesc_diff.c       1.1     06/05/16 SMI"
  29
  30 #include <sys/types.h>
  31 #ifdef _KERNEL
  32 #include <sys/systm.h>
  33 #else /* _KERNEL */
  34 #include <string.h>
  35 #include <strings.h>
  36 #endif /* _KERNEL */
  37 #include <sys/note.h>
  38 #include <sys/mdesc.h>
  39 #include <sys/mdesc_impl.h>
  40
  41 #define MDD_FREE_CHECK(mdp, ptr, sz)            \
  42         do {                                    \
  43                 if (ptr) mdp->freep(ptr, sz);   \
  44         _NOTE(CONSTCOND) } while (0)
  45
  46 #define MD_DIFF_MAGIC                   0x4D445F4449464621ull   /* 'MD_DIFF!' */
  47 #define MD_DIFF_NOMATCH                 (-1)
  48 #define MD_DIFF_MATCH                   (1)
  49
  50 typedef struct {
  51         mde_cookie_t    *mdep;
  52         uint_t          nelem;
  53 } md_diff_t;
  54
  55 typedef struct {
  56         uint64_t        mdd_magic;
  57         md_diff_t       added;
  58         md_diff_t       removed;
  59         md_diff_t       match1;
  60         md_diff_t       match2;
  61         void            *(*allocp)(size_t);
  62         void            (*freep)(void *, size_t);
  63 } md_diff_impl_t;
  64
  65 /*
  66  * Internal utility functions
  67  */
  68 static int mdd_scan_for_nodes(md_t *mdp, mde_cookie_t start,
  69     char *compnodep, int *countp, mde_cookie_t **nodespp);
  70
  71 static boolean_t mdd_any_dup_nodes(md_impl_t *mdp, md_prop_match_t *pmp,
  72     int count, mde_cookie_t *nodesp);
  73
  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);
  77
  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);
  80
  81 /*
  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.
  87  */
  88 md_diff_cookie_t
  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)
  91 {
  92         int             idx;
  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;
  97         int             md1count = 0;
  98         int             md2count = 0;
  99         uint8_t         *seenp = NULL;
 100
 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;
 107         int             nadd = 0;
 108         int             nrem = 0;
 109         int             nmatch = 0;
 110
 111         /* sanity check params */
 112         if ((md1p == NULL) || (md2p == NULL))
 113                 return (MD_INVAL_DIFF_COOKIE);
 114
 115         if ((start1 == MDE_INVAL_ELEM_COOKIE) ||
 116             (start2 == MDE_INVAL_ELEM_COOKIE))
 117                 return (MD_INVAL_DIFF_COOKIE);
 118
 119         if ((compnodep == NULL) || (match_fieldsp == NULL))
 120                 return (MD_INVAL_DIFF_COOKIE);
 121
 122         /*
 123          * Prepare an array of the matching nodes from the first MD.
 124          */
 125         if (mdd_scan_for_nodes(md1p,
 126             start1, compnodep, &md1count, &md1nodesp) == -1)
 127                 return (MD_INVAL_DIFF_COOKIE);
 128
 129         /* sanity check that all nodes are unique */
 130         if (md1nodesp &&
 131             mdd_any_dup_nodes(md1, match_fieldsp, md1count, md1nodesp)) {
 132                 MDD_FREE_CHECK(md1, md1nodesp, sizeof (mde_cookie_t) *
 133                     md1count);
 134                 return (MD_INVAL_DIFF_COOKIE);
 135         }
 136
 137
 138         /*
 139          * Prepare an array of the matching nodes from the second MD.
 140          */
 141         if (mdd_scan_for_nodes(md2p,
 142             start2, compnodep, &md2count, &md2nodesp) == -1)
 143                 return (MD_INVAL_DIFF_COOKIE);
 144
 145         /* sanity check that all nodes are unique */
 146         if (md2nodesp &&
 147             mdd_any_dup_nodes(md2, match_fieldsp, md2count, md2nodesp)) {
 148                 MDD_FREE_CHECK(md1, md1nodesp, sizeof (mde_cookie_t) *
 149                     md1count);
 150                 MDD_FREE_CHECK(md2, md2nodesp, sizeof (mde_cookie_t) *
 151                     md2count);
 152                 return (MD_INVAL_DIFF_COOKIE);
 153         }
 154
 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;
 161
 162         /*
 163          * Special cases for empty lists
 164          */
 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);
 170         }
 171
 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);
 177         }
 178
 179         if ((md1count == 0) && (md2count == 0))
 180                 /* no nodes found */
 181                 return ((mde_cookie_t)diff_res);
 182
 183         /*
 184          * Both lists have some elements. Allocate some scratch
 185          * buffers to sort them into our three categories, added,
 186          * removed, and matched pairs.
 187          */
 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);
 192
 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);
 196
 197         /*
 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.
 202          */
 203         for (idx = 0; idx < md1count; idx++) {
 204
 205                 md_element_t *elem = &(md1->mdep[md1nodesp[idx]]);
 206
 207                 int match = mdd_node_list_match(md1, md2, elem, md2nodesp,
 208                     seenp, 0, md2count - 1, match_fieldsp);
 209
 210                 if (match == MD_DIFF_NOMATCH)
 211                         /* record deleted node */
 212                         mde_rem_scr[nrem++] = md1nodesp[idx];
 213                 else {
 214                         /* record matched node pair */
 215                         mde_match1_scr[nmatch] = md1nodesp[idx];
 216                         mde_match2_scr[nmatch] = md2nodesp[match];
 217                         nmatch++;
 218
 219                         /* mark that this match has been recorded */
 220                         seenp[match] = 1;
 221                 }
 222         }
 223
 224         /*
 225          * Make a pass through the md2 array. Any nodes that have
 226          * not been marked as seen have been added.
 227          */
 228         for (idx = 0; idx < md2count; idx++) {
 229                 if (!seenp[idx])
 230                         /* record added node */
 231                         mde_add_scr[nadd++] = md2nodesp[idx];
 232         }
 233
 234         /* fill in the added node list */
 235         if (nadd) {
 236                 int addsz = sizeof (mde_cookie_t) * nadd;
 237                 diff_res->added.mdep = (mde_cookie_t *)diff_res->allocp(addsz);
 238
 239                 bcopy(mde_add_scr, diff_res->added.mdep, addsz);
 240
 241                 diff_res->added.nelem = nadd;
 242         }
 243
 244         /* fill in the removed node list */
 245         if (nrem) {
 246                 int remsz = sizeof (mde_cookie_t) * nrem;
 247                 diff_res->removed.mdep =
 248                     (mde_cookie_t *)diff_res->allocp(remsz);
 249
 250                 bcopy(mde_rem_scr, diff_res->removed.mdep, remsz);
 251                 diff_res->removed.nelem = nrem;
 252         }
 253
 254         /* fill in the matching node lists */
 255         if (nmatch) {
 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);
 261
 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;
 266         }
 267
 268         /* clean up */
 269         md1->freep(md1nodesp, sizeof (mde_cookie_t) * md1count);
 270         md2->freep(md2nodesp, sizeof (mde_cookie_t) * md2count);
 271
 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);
 276
 277         diff_res->freep(seenp, sizeof (uint8_t) * md2count);
 278
 279         return ((md_diff_cookie_t)diff_res);
 280 }
 281
 282 /*
 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.
 287  */
 288 int
 289 md_diff_added(md_diff_cookie_t mdd, mde_cookie_t **mde_addedp)
 290 {
 291         md_diff_impl_t  *mddp = (md_diff_impl_t *)mdd;
 292
 293         if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
 294                 return (-1);
 295
 296         *mde_addedp = mddp->added.mdep;
 297
 298         return (mddp->added.nelem);
 299 }
 300
 301 /*
 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.
 306  */
 307 int
 308 md_diff_removed(md_diff_cookie_t mdd, mde_cookie_t **mde_removedp)
 309 {
 310         md_diff_impl_t  *mddp = (md_diff_impl_t *)mdd;
 311
 312         if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
 313                 return (-1);
 314
 315         *mde_removedp = mddp->removed.mdep;
 316
 317         return (mddp->removed.nelem);
 318 }
 319
 320 /*
 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
 325  * will be NULL.
 326  */
 327 int
 328 md_diff_matched(md_diff_cookie_t mdd, mde_cookie_t **mde_match1p,
 329     mde_cookie_t **mde_match2p)
 330 {
 331         md_diff_impl_t  *mddp = (md_diff_impl_t *)mdd;
 332
 333         if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
 334                 return (-1);
 335
 336         *mde_match1p = mddp->match1.mdep;
 337         *mde_match2p = mddp->match2.mdep;
 338
 339         return (mddp->match1.nelem);
 340 }
 341
 342 /*
 343  * Deallocate any storage used to store results of a previous
 344  * md_diff_init() call. Returns 0 on success and -1 on failure.
 345  */
 346 int
 347 md_diff_fini(md_diff_cookie_t mdd)
 348 {
 349         md_diff_impl_t  *mddp = (md_diff_impl_t *)mdd;
 350
 351         if ((mddp == NULL) || (mddp->mdd_magic != MD_DIFF_MAGIC))
 352                 return (-1);
 353
 354         mddp->mdd_magic = 0;
 355
 356         MDD_FREE_CHECK(mddp, mddp->added.mdep, mddp->added.nelem *
 357             sizeof (mde_cookie_t));
 358
 359         MDD_FREE_CHECK(mddp, mddp->removed.mdep, mddp->removed.nelem *
 360             sizeof (mde_cookie_t));
 361
 362         MDD_FREE_CHECK(mddp, mddp->match1.mdep, mddp->match1.nelem *
 363             sizeof (mde_cookie_t));
 364
 365         MDD_FREE_CHECK(mddp, mddp->match2.mdep, mddp->match2.nelem *
 366             sizeof (mde_cookie_t));
 367
 368         mddp->freep(mddp, sizeof (md_diff_impl_t));
 369
 370         return (0);
 371 }
 372
 373 /*
 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.
 379  *
 380  * Returns: 0 success; -1 failure
 381  */
 382 static int
 383 mdd_scan_for_nodes(md_t *mdp,
 384     mde_cookie_t start, char *compnodep, int *countp, mde_cookie_t **nodespp)
 385 {
 386         mde_str_cookie_t        cname;
 387         mde_str_cookie_t        aname;
 388         md_impl_t               *mdip = (md_impl_t *)mdp;
 389
 390         if (mdip == NULL)
 391                 return (-1);
 392
 393         cname = md_find_name(mdp, compnodep);
 394         aname = md_find_name(mdp, "fwd");
 395
 396         /* get the number of nodes of interest in the DAG */
 397         *countp = md_scan_dag(mdp, start, cname, aname, NULL);
 398         if (*countp == 0) {
 399                 *nodespp = NULL;
 400                 return (0);
 401         }
 402
 403         /* allocate the storage */
 404         *nodespp = mdip->allocp(sizeof (mde_cookie_t) * (*countp));
 405
 406         /* populate our array with the matching nodes */
 407         (void) md_scan_dag(mdp, start, cname, aname, *nodespp);
 408
 409         return (0);
 410 }
 411
 412 /*
 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
 416  * otherwise.
 417  */
 418 static boolean_t
 419 mdd_any_dup_nodes(md_impl_t *mdp, md_prop_match_t *pmp, int count,
 420     mde_cookie_t *nodesp)
 421 {
 422         int             idx;
 423         int             match;
 424         md_element_t    *elem;
 425
 426         ASSERT(count > 0 || nodesp == NULL);
 427
 428         for (idx = 0; idx < count; idx++) {
 429                 elem = &(mdp->mdep[nodesp[idx]]);
 430
 431                 match = mdd_node_list_match(mdp, mdp, elem, nodesp, NULL,
 432                     idx + 1, count - 1, pmp);
 433
 434                 if (match != MD_DIFF_NOMATCH)
 435                         return (B_TRUE);
 436         }
 437
 438         return (B_FALSE);
 439 }
 440
 441 /*
 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.
 446  *
 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.
 450  */
 451 static int
 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)
 455 {
 456         int             match;
 457         int             idx;
 458         md_element_t    *elem;
 459
 460         for (idx = start; idx <= end; idx++) {
 461
 462                 if ((match_seenp != NULL) && (match_seenp[idx]))
 463                         continue;
 464
 465                 elem = &(md2->mdep[match_listp[idx]]);
 466
 467                 match = mdd_node_compare(md1, md2, match_nodep, elem,
 468                     match_elemsp);
 469                 if (match == MD_DIFF_MATCH)
 470                         return (idx);
 471         }
 472
 473         return (MD_DIFF_NOMATCH);
 474 }
 475
 476 /*
 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.
 482  */
 483 static int
 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)
 486 {
 487         md_element_t    *ap;
 488         md_element_t    *bp;
 489         boolean_t       nodea_interest;
 490         boolean_t       nodeb_interest;
 491         int             idx;
 492
 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);
 496
 497         for (idx = 0; match_elemsp[idx].type != MDET_LIST_END; idx++) {
 498
 499                 int type;
 500
 501                 nodea_interest = B_FALSE;
 502                 nodeb_interest = B_FALSE;
 503
 504                 type = match_elemsp[idx].type;
 505
 506                 /*
 507                  * Check node A for the property of interest
 508                  */
 509                 for (ap = nodeap; MDE_TAG(ap) != MDET_NODE_END; ap++) {
 510                         char *elemname;
 511
 512                         if (MDE_TAG(ap) != type)
 513                                 continue;
 514
 515                         elemname = mdap->namep + MDE_NAME(ap);
 516
 517                         if (strcmp(elemname, match_elemsp[idx].namep) == 0) {
 518                                 /* found the property of interest */
 519                                 nodea_interest = B_TRUE;
 520                                 break;
 521                         }
 522                 }
 523
 524                 /* node A is not of interest */
 525                 if (!nodea_interest)
 526                         return (MD_DIFF_NOMATCH);
 527
 528                 /*
 529                  * Check node B for the property of interest
 530                  */
 531                 for (bp = nodebp; MDE_TAG(bp) != MDET_NODE_END; bp++) {
 532                         char *elemname;
 533
 534                         if (MDE_TAG(bp) != type)
 535                                 continue;
 536
 537                         elemname = mdbp->namep + MDE_NAME(bp);
 538
 539                         if (strcmp(elemname, match_elemsp[idx].namep) == 0) {
 540                                 nodeb_interest = B_TRUE;
 541                                 break;
 542                         }
 543                 }
 544
 545                 /* node B is not of interest */
 546                 if (!nodeb_interest)
 547                         return (MD_DIFF_NOMATCH);
 548
 549                 /*
 550                  * Both nodes have the property of interest. The
 551                  * nodes are not a match unless the value of that
 552                  * property match
 553                  */
 554                 switch (type) {
 555                 case MDET_PROP_VAL:
 556                         if (MDE_PROP_VALUE(ap) != MDE_PROP_VALUE(bp))
 557                                 return (MD_DIFF_NOMATCH);
 558                         break;
 559
 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));
 565
 566                         if (strcmp(stra, strb) != 0)
 567                                 return (MD_DIFF_NOMATCH);
 568                         break;
 569                 }
 570
 571                 case MDET_PROP_DAT: {
 572
 573                         caddr_t dataa;
 574                         caddr_t datab;
 575
 576                         if (MDE_PROP_DATA_LEN(ap) != MDE_PROP_DATA_LEN(bp))
 577                                 return (MD_DIFF_NOMATCH);
 578
 579                         dataa = (caddr_t)(mdap->datap +
 580                             MDE_PROP_DATA_OFFSET(ap));
 581                         datab = (caddr_t)(mdbp->datap +
 582                             MDE_PROP_DATA_OFFSET(bp));
 583
 584                         if (memcmp(dataa, datab, MDE_PROP_DATA_LEN(ap)) != 0)
 585                                 return (MD_DIFF_NOMATCH);
 586
 587                         break;
 588                 }
 589
 590                 default:
 591                         /* unsupported prop type */
 592                         return (MD_DIFF_NOMATCH);
 593                 }
 594         }
 595
 596         /*
 597          * All the specified properties exist in both
 598          * nodes and have the same value. The two nodes
 599          * match.
 600          */
 601
 602         return (MD_DIFF_MATCH);
 603 }