merge.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License, Version 1.0 only
* (the "License"). You may not use this file except in compliance
* with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* This file contains routines that merge one tdata_t tree, called the child,
* into another, called the parent. Note that these names are used mainly for
* convenience and to represent the direction of the merge. They are not meant
* to imply any relationship between the tdata_t graphs prior to the merge.
*
* tdata_t structures contain two main elements - a hash of iidesc_t nodes, and
* a directed graph of tdesc_t nodes, pointed to by the iidesc_t nodes. Simply
* put, we merge the tdesc_t graphs, followed by the iidesc_t nodes, and then we
* clean up loose ends.
*
* The algorithm is as follows:
*
* 1. Mapping iidesc_t nodes
*
* For each child iidesc_t node, we first try to map its tdesc_t subgraph
* against the tdesc_t graph in the parent. For each node in the child subgraph
* that exists in the parent, a mapping between the two (between their type IDs)
* is established. For the child nodes that cannot be mapped onto existing
* parent nodes, a mapping is established between the child node ID and a
* newly-allocated ID that the node will use when it is re-created in the
* parent. These unmappable nodes are added to the md_tdtba (tdesc_t To Be
* Added) hash, which tracks nodes that need to be created in the parent.
*
* If all of the nodes in the subgraph for an iidesc_t in the child can be
* mapped to existing nodes in the parent, then we can try to map the child
* iidesc_t onto an iidesc_t in the parent. If we cannot find an equivalent
* iidesc_t, or if we were not able to completely map the tdesc_t subgraph(s),
* then we add this iidesc_t to the md_iitba (iidesc_t To Be Added) list. This
* list tracks iidesc_t nodes that are to be created in the parent.
*
* While visiting the tdesc_t nodes, we may discover a forward declaration (a
* FORWARD tdesc_t) in the parent that is resolved in the child. That is, there
* may be a structure or union definition in the child with the same name as the
* forward declaration in the parent. If we find such a node, we record an
* association in the md_fdida (Forward => Definition ID Association) list
* between the parent ID of the forward declaration and the ID that the
* definition will use when re-created in the parent.
*
* 2. Creating new tdesc_t nodes (the md_tdtba hash)
*
* We have now attempted to map all tdesc_t nodes from the child into the
* parent, and have, in md_tdtba, a hash of all tdesc_t nodes that need to be
* created (or, as we so wittily call it, conjured) in the parent. We iterate
* through this hash, creating the indicated tdesc_t nodes. For a given tdesc_t
* node, conjuring requires two steps - the copying of the common tdesc_t data
* (name, type, etc) from the child node, and the creation of links from the
* newly-created node to the parent equivalents of other tdesc_t nodes pointed
* to by node being conjured. Note that in some cases, the targets of these
* links will be on the md_tdtba hash themselves, and may not have been created
* yet. As such, we can't establish the links from these new nodes into the
* parent graph. We therefore conjure them with links to nodes in the *child*
* graph, and add pointers to the links to be created to the md_tdtbr (tdesc_t
* To Be Remapped) hash. For example, a POINTER tdesc_t that could not be
* resolved would have its &tdesc_t->t_tdesc added to md_tdtbr.
*
* 3. Creating new iidesc_t nodes (the md_iitba list)
*
* When we have completed step 2, all tdesc_t nodes have been created (or
* already existed) in the parent. Some of them may have incorrect links (the
* members of the md_tdtbr list), but they've all been created. As such, we can
* create all of the iidesc_t nodes, as we can attach the tdesc_t subgraph
* pointers correctly. We create each node, and attach the pointers to the
* appropriate parts of the parent tdesc_t graph.
*
* 4. Resolving newly-created tdesc_t node links (the md_tdtbr list)
*
* As in step 3, we rely on the fact that all of the tdesc_t nodes have been
* created. Each entry in the md_tdtbr list is a pointer to where a link into
* the parent will be established. As saved in the md_tdtbr list, these
* pointers point into the child tdesc_t subgraph. We can thus get the target
* type ID from the child, look at the ID mapping to determine the desired link
* target, and redirect the link accordingly.
*
* 5. Parent => child forward declaration resolution
*
* If entries were made in the md_fdida list in step 1, we have forward
* declarations in the parent that need to be resolved to their definitions
* re-created in step 2 from the child. Using the md_fdida list, we can locate
* the definition for the forward declaration, and we can redirect all inbound
* edges to the forward declaration node to the actual definition.
*
* A pox on the house of anyone who changes the algorithm without updating
* this comment.
*/
#include <stdio.h>
#include <strings.h>
#include <assert.h>
#include <pthread.h>
#include "ctf_headers.h"
#include "ctftools.h"
#include "list.h"
#include "alist.h"
#include "memory.h"
#include "traverse.h"
typedef struct equiv_data equiv_data_t;
typedef struct merge_cb_data merge_cb_data_t;
/*
* There are two traversals in this file, for equivalency and for tdesc_t
* re-creation, that do not fit into the tdtraverse() framework. We have our
* own traversal mechanism and ops vector here for those two cases.
*/
typedef struct tdesc_ops {
char *name;
} tdesc_ops_t;
extern tdesc_ops_t tdesc_ops[];
/*
* The workhorse structure of tdata_t merging. Holds all lists of nodes to be
* processed during various phases of the merge algorithm.
*/
struct merge_cb_data {
int md_flags;
}; /* merge_cb_data_t */
/*
* When we first create a tdata_t from stabs data, we will have duplicate nodes.
* Normal merges, however, assume that the child tdata_t is already self-unique,
* and for speed reasons do not attempt to self-uniquify. If this flag is set,
* the merge algorithm will self-uniquify by avoiding the insertion of
* duplicates in the md_tdtdba list.
*/
#define MCD_F_SELFUNIQUIFY 0x1
/*
* When we merge the CTF data for the modules, we don't want it to contain any
* data that can be found in the reference module (usually genunix). If this
* flag is set, we're doing a merge between the fully merged tdata_t for this
* module and the tdata_t for the reference module, with the data unique to this
* module ending up in a third tdata_t. It is this third tdata_t that will end
* up in the .SUNW_ctf section for the module.
*/
#define MCD_F_REFMERGE 0x2
/*
* Mapping of child type IDs to parent type IDs
*/
static void
{
}
static tid_t
{
long ltgtid;
return ((int)ltgtid);
else
return (0);
}
/*
* Determining equivalence of tdesc_t subgraphs
*/
struct equiv_data {
int ed_clear_mark;
int ed_cur_mark;
int ed_selfuniquify;
}; /* equiv_data_t */
/*ARGSUSED2*/
static int
{
return (0);
return (0);
return (0);
return (1);
}
static int
{
}
static int
{
int i;
return (0);
return (0);
return (0);
}
return (1);
}
static int
{
return (0);
return (0);
return (1);
}
static int
{
return (0);
/*
* Don't do the recursive equivalency checking more than
* we have to.
*/
return (0);
}
}
return (0);
return (1);
}
/*ARGSUSED2*/
static int
{
return (0);
}
return (0);
return (1);
}
/*ARGSUSED*/
static int
{
/* foul, evil, and very bad - this is a "shouldn't happen" */
assert(1 == 0);
return (0);
}
static int
{
}
static int
{
int (*equiv)();
int mapping;
/*
* In normal (non-self-uniquify) mode, we don't want to do equivalency
* checking on a subgraph that has already been checked. If a mapping
* has already been established for a given child node, we can simply
* compare the mapping for the child node with the ID of the parent
* node. If we are in self-uniquify mode, then we're comparing two
* subgraphs within the child graph, and thus need to ignore any
* type mappings that have been created, as they are only valid into the
* parent.
*/
return (1);
return (0);
else
return (0);
}
ed->ed_cur_mark++;
return (1);
}
/*
* We perform an equivalency check on two subgraphs by traversing through them
* in lockstep. If a given node is equivalent in both the parent and the child,
* we mark it in both subgraphs, using the t_emark field, with a monotonically
* increasing number. If, in the course of the traversal, we reach a node that
* we have visited and numbered during this equivalency check, we have a cycle.
* If the previously-visited nodes don't have the same emark, then the edges
* that brought us to these nodes are not equivalent, and so the check ends.
* If the emarks are the same, the edges are equivalent. We then backtrack and
* continue the traversal. If we have exhausted all edges in the subgraph, and
* have not found any inequivalent nodes, then the subgraphs are equivalent.
*/
static int
{
/* matched. stop looking */
return (-1);
}
return (0);
}
/*ARGSUSED1*/
static int
{
return (0);
return (1);
}
/*ARGSUSED1*/
static int
{
ed.ed_selfuniquify = 0;
/* We found an equivalent node */
} else
/*
* We didn't find an equivalent node by looking through the
* layout hash, but we somehow found it by performing an
* exhaustive search through the entire graph. This usually
* means that the "name" hash function is broken.
*/
} else {
}
return (1);
}
/*ARGSUSED1*/
static int
{
/*
* We didn't find an equivalent node using the quick way (going
* through the hash normally), but we did find it by iterating
* through the entire hash. This usually means that the hash
* function is broken.
*/
terminate("Self-unique second pass for %d (%s) == %d\n",
} else {
}
return (1);
}
static tdtrav_cb_f map_pre[] = {
NULL,
map_td_tree_pre, /* intrinsic */
map_td_tree_pre, /* pointer */
map_td_tree_pre, /* array */
map_td_tree_pre, /* function */
map_td_tree_pre, /* struct */
map_td_tree_pre, /* union */
map_td_tree_pre, /* enum */
map_td_tree_pre, /* forward */
map_td_tree_pre, /* typedef */
tdtrav_assert, /* typedef_unres */
map_td_tree_pre, /* volatile */
map_td_tree_pre, /* const */
map_td_tree_pre /* restrict */
};
static tdtrav_cb_f map_post[] = {
NULL,
map_td_tree_post, /* intrinsic */
map_td_tree_post, /* pointer */
map_td_tree_post, /* array */
map_td_tree_post, /* function */
map_td_tree_post, /* struct */
map_td_tree_post, /* union */
map_td_tree_post, /* enum */
map_td_tree_post, /* forward */
map_td_tree_post, /* typedef */
tdtrav_assert, /* typedef_unres */
map_td_tree_post, /* volatile */
map_td_tree_post, /* const */
map_td_tree_post /* restrict */
};
static tdtrav_cb_f map_self_post[] = {
NULL,
map_td_tree_self_post, /* intrinsic */
map_td_tree_self_post, /* pointer */
map_td_tree_self_post, /* array */
map_td_tree_self_post, /* function */
map_td_tree_self_post, /* struct */
map_td_tree_self_post, /* union */
map_td_tree_self_post, /* enum */
map_td_tree_self_post, /* forward */
map_td_tree_self_post, /* typedef */
tdtrav_assert, /* typedef_unres */
map_td_tree_self_post, /* volatile */
map_td_tree_self_post, /* const */
map_td_tree_self_post /* restrict */
};
/*
* Determining equivalence of iidesc_t nodes
*/
typedef struct iifind_data {
int iif_newidx;
int iif_refmerge;
/*
* Check to see if this iidesc_t (node) - the current one on the list we're
* iterating through - matches the target one (iif->iif_template). Return -1
* if it matches, to stop the iteration.
*/
static int
{
int i;
return (0);
return (0);
return (0);
return (0);
}
if (iif->iif_refmerge) {
case II_GFUN:
case II_SFUN:
case II_GVAR:
case II_SVAR:
return (0);
case II_NOT:
case II_PSYM:
case II_SOU:
case II_TYPE:
break;
}
}
return (-1);
}
static int
{
/* Map the tdesc nodes */
mcd);
/* Map the iidesc nodes */
&iif) == 1)
/* successfully mapped */
return (1);
return (0);
}
static int
{
return (1);
}
(void *)&tgt))) {
oldid);
return (0);
}
return (1);
}
static tdesc_t *
{
return (new);
}
/*ARGSUSED2*/
static tdesc_t *
{
return (new);
}
static tdesc_t *
{
return (new);
}
static tdesc_t *
{
int i;
}
return (new);
}
static tdesc_t *
{
mcd);
mcd);
return (new);
}
static tdesc_t *
{
}
return (new);
}
/*ARGSUSED2*/
static tdesc_t *
{
}
return (new);
}
/*ARGSUSED2*/
static tdesc_t *
{
return (new);
}
/*ARGSUSED*/
static tdesc_t *
{
assert(1 == 0);
return (NULL);
}
static iidesc_t *
{
int i;
mcd);
}
return (new);
}
static int
{
return (0);
return (1);
}
static tdtrav_cb_f fwd_redir_cbs[] = {
NULL,
NULL, /* intrinsic */
NULL, /* pointer */
NULL, /* array */
NULL, /* function */
NULL, /* struct */
NULL, /* union */
NULL, /* enum */
fwd_redir, /* forward */
NULL, /* typedef */
tdtrav_assert, /* typedef_unres */
NULL, /* volatile */
NULL, /* const */
NULL /* restrict */
};
typedef struct redir_mstr_data {
static int
{
(void *)&defn)) {
}
return (1);
}
static void
{
}
}
static int
{
int newidx;
&iif) == 1) {
return (1);
}
return (1);
}
static int
{
/* couldn't map everything */
return (0);
return (1);
}
static int
{
int newid;
int rc;
return (rc);
}
static int
{
return (0);
return (1);
}
static void
{
terminate("Couldn't remap all nodes\n");
/*
* We now have an alist of master forwards and the ids of the new master
* definitions for those forwards in mcd->md_fdida. By this point,
* we're guaranteed that all of the master definitions referenced in
* fdida have been added to the master tree. We now traverse through
* the master tree, redirecting all edges inbound to forwards that have
* definitions to those definitions.
*/
}
}
void
{
if (tgt)
if (selfuniquify)
if (tgt)
if (debug_level >= 3) {
}
if (tgt)
}
tdesc_ops_t tdesc_ops[] = {
};