libctf/common/ctf_diff.c

/*
 * This file and its contents are supplied under the terms of the
 * Common Development and Distribution License ("CDDL"), version 1.0.
 * You may only use this file in accordance with the terms of version
 * 1.0 of the CDDL.
 *
 * A full copy of the text of the CDDL should have accompanied this
 * source.  A copy of the CDDL is also available via the Internet at
 * http://www.illumos.org/license/CDDL.
 */

/*
 * Copyright (c) 2015 Joyent, Inc.  All rights reserved.
 */

/*
 * The following is a basic overview of how we diff types in containers (the
 * generally interesting part of diff, and what's used by merge). We maintain
 * two mapping tables, a table of forward mappings (src->dest), and a reverse
 * mapping (dest->src). Both are initialized to contain no mapping, and can also
 * be updated to contain a negative mapping.
 *
 * What we do first is iterate over each type in the src container, and compare
 * it with a type in the destination container. This may involve doing recursive
 * comparisons -- which can involve cycles. To deal with this, whenever we
 * encounter something which may be cyclic, we insert a guess. In other words,
 * we assume that it may be true. This is necessary for the classic case of the
 * following structure:
 *
 * struct foo {
 *	struct foo *foo_next;
 * };
 *
 * If it turns out that we were wrong, we discard our guesses.
 *
 * If we find that a given type in src has no corresponding entry in dst, we
 * then mark its map as CTF_ERR (-1) to indicate that it has *no* match, as
 * opposed to the default value of 0, which indicates an unknown match.
 * Once we've done the first iteration through src, we know at that point in
 * time whether everything in dst is similar or not and can simply walk over it
 * and don't have to do any additional checks.
 */

#include <libctf.h>
#include <ctf_impl.h>
#include <sys/debug.h>

typedef struct ctf_diff_func {
	const char *cdf_name;
	ulong_t cdf_symidx;
	ulong_t cdf_matchidx;
} ctf_diff_func_t;

typedef struct ctf_diff_obj {
	const char *cdo_name;
	ulong_t cdo_symidx;
	ctf_id_t cdo_id;
	ulong_t cdo_matchidx;
} ctf_diff_obj_t;

typedef struct ctf_diff_guess {
	struct ctf_diff_guess *cdg_next;
	ctf_id_t cdg_iid;
	ctf_id_t cdg_oid;
} ctf_diff_guess_t;

/* typedef in libctf.h */
struct ctf_diff {
	uint_t cds_flags;
	boolean_t cds_tvalid;	/* types valid */
	ctf_file_t *cds_ifp;
	ctf_file_t *cds_ofp;
	ctf_id_t *cds_forward;
	ctf_id_t *cds_reverse;
	size_t cds_fsize;
	size_t cds_rsize;
	ctf_diff_type_f cds_func;
	ctf_diff_guess_t *cds_guess;
	void *cds_arg;
	uint_t cds_nifuncs;
	uint_t cds_nofuncs;
	uint_t cds_nextifunc;
	uint_t cds_nextofunc;
	ctf_diff_func_t *cds_ifuncs;
	ctf_diff_func_t *cds_ofuncs;
	boolean_t cds_ffillip;
	boolean_t cds_fvalid;
	uint_t cds_niobj;
	uint_t cds_noobj;
	uint_t cds_nextiobj;
	uint_t cds_nextoobj;
	ctf_diff_obj_t *cds_iobj;
	ctf_diff_obj_t *cds_oobj;
	boolean_t cds_ofillip;
	boolean_t cds_ovalid;
};

#define	TINDEX(tid) (tid - 1)

/*
 * Team Diff
 */
static int ctf_diff_type(ctf_diff_t *, ctf_file_t *, ctf_id_t, ctf_file_t *,
    ctf_id_t);

static int
ctf_diff_name(ctf_file_t *ifp, ctf_id_t iid, ctf_file_t *ofp, ctf_id_t oid)
{
	const char *iname, *oname;
	const ctf_type_t *itp, *otp;

	if ((itp = ctf_lookup_by_id(&ifp, iid)) == NULL)
		return (CTF_ERR);

	if ((otp = ctf_lookup_by_id(&ofp, oid)) == NULL)
		return (ctf_set_errno(ifp, iid));

	iname = ctf_strptr(ifp, itp->ctt_name);
	oname = ctf_strptr(ofp, otp->ctt_name);

	if ((iname == NULL || oname == NULL) && (iname != oname))
		return (B_TRUE);

	/* Two anonymous names are the same */
	if (iname == NULL && oname == NULL)
		return (B_FALSE);

	return (strcmp(iname, oname) == 0 ? B_FALSE: B_TRUE);
}

/*
 * For floats and ints
 */
static int
ctf_diff_number(ctf_file_t *ifp, ctf_id_t iid, ctf_file_t *ofp, ctf_id_t oid)
{
	ctf_encoding_t ien, den;

	if (ctf_type_encoding(ifp, iid, &ien) != 0)
		return (CTF_ERR);

	if (ctf_type_encoding(ofp, oid, &den) != 0)
		return (ctf_set_errno(ifp, iid));

	if (bcmp(&ien, &den, sizeof (ctf_encoding_t)) != 0)
		return (B_TRUE);

	return (B_FALSE);
}

/*
 * Two typedefs are equivalent, if after we resolve a chain of typedefs, they
 * point to equivalent types. This means that if a size_t is defined as follows:
 *
 * size_t -> ulong_t -> unsigned long
 * size_t -> unsigned long
 *
 * That we'll ultimately end up treating them the same.
 */
static int
ctf_diff_typedef(ctf_diff_t *cds, ctf_file_t *ifp, ctf_id_t iid,
    ctf_file_t *ofp, ctf_id_t oid)
{
	ctf_id_t iref = CTF_ERR, oref = CTF_ERR;

	while (ctf_type_kind(ifp, iid) == CTF_K_TYPEDEF) {
		iref = ctf_type_reference(ifp, iid);
		if (iref == CTF_ERR)
			return (CTF_ERR);
		iid = iref;
	}

	while (ctf_type_kind(ofp, oid) == CTF_K_TYPEDEF) {
		oref = ctf_type_reference(ofp, oid);
		if (oref == CTF_ERR)
			return (CTF_ERR);
		oid = oref;
	}

	VERIFY(iref != CTF_ERR && oref != CTF_ERR);
	return (ctf_diff_type(cds, ifp, iref, ofp, oref));
}

/*
 * Two qualifiers are equivalent iff they point to two equivalent types.
 */
static int
ctf_diff_qualifier(ctf_diff_t *cds, ctf_file_t *ifp, ctf_id_t iid,
    ctf_file_t *ofp, ctf_id_t oid)
{
	ctf_id_t iref, oref;

	iref = ctf_type_reference(ifp, iid);
	if (iref == CTF_ERR)
		return (CTF_ERR);

	oref = ctf_type_reference(ofp, oid);
	if (oref == CTF_ERR)
		return (ctf_set_errno(ifp, ctf_errno(ofp)));

	return (ctf_diff_type(cds, ifp, iref, ofp, oref));
}

/*
 * Two arrays are the same iff they have the same type for contents, the same
 * type for the index, and the same number of elements.
 */
static int
ctf_diff_array(ctf_diff_t *cds, ctf_file_t *ifp, ctf_id_t iid, ctf_file_t *ofp,
    ctf_id_t oid)
{
	int ret;
	ctf_arinfo_t iar, oar;

	if (ctf_array_info(ifp, iid, &iar) == CTF_ERR)
		return (CTF_ERR);

	if (ctf_array_info(ofp, oid, &oar) == CTF_ERR)
		return (ctf_set_errno(ifp, ctf_errno(ofp)));

	ret = ctf_diff_type(cds, ifp, iar.ctr_contents, ofp, oar.ctr_contents);
	if (ret != B_FALSE)
		return (ret);

	if (iar.ctr_nelems != oar.ctr_nelems)
		return (B_TRUE);

	/*
	 * If we're ignoring integer types names, then we're trying to do a bit
	 * of a logical diff and we don't really care about the fact that the
	 * index element might not be the same here, what we care about are the
	 * number of elements and that they're the same type.
	 */
	if ((cds->cds_flags & CTF_DIFF_F_IGNORE_INTNAMES) == 0) {
		ret = ctf_diff_type(cds, ifp, iar.ctr_index, ofp,
		    oar.ctr_index);
		if (ret != B_FALSE)
			return (ret);
	}

	return (B_FALSE);
}

/*
 * Two function pointers are the same if the following is all true:
 *
 *   o They have the same return type
 *   o They have the same number of arguments
 *   o The arguments are of the same type
 *   o They have the same flags
 */
static int
ctf_diff_fptr(ctf_diff_t *cds, ctf_file_t *ifp, ctf_id_t iid, ctf_file_t *ofp,
    ctf_id_t oid)
{
	int ret, i;
	ctf_funcinfo_t ifunc, ofunc;
	ctf_id_t *iids, *oids;

	if (ctf_func_info_by_id(ifp, iid, &ifunc) == CTF_ERR)
		return (CTF_ERR);

	if (ctf_func_info_by_id(ofp, oid, &ofunc) == CTF_ERR)
		return (ctf_set_errno(ifp, ctf_errno(ofp)));

	if (ifunc.ctc_argc != ofunc.ctc_argc)
		return (B_TRUE);

	if (ifunc.ctc_flags != ofunc.ctc_flags)
		return (B_TRUE);

	ret = ctf_diff_type(cds, ifp, ifunc.ctc_return, ofp, ofunc.ctc_return);
	if (ret != B_FALSE)
		return (ret);

	iids = ctf_alloc(sizeof (ctf_id_t) * ifunc.ctc_argc);
	if (iids == NULL)
		return (ctf_set_errno(ifp, ENOMEM));

	oids = ctf_alloc(sizeof (ctf_id_t) * ifunc.ctc_argc);
	if (oids == NULL) {
		ctf_free(iids, sizeof (ctf_id_t) * ifunc.ctc_argc);
		return (ctf_set_errno(ifp, ENOMEM));
	}

	if (ctf_func_args_by_id(ifp, iid, ifunc.ctc_argc, iids) == CTF_ERR) {
		ret = CTF_ERR;
		goto out;
	}

	if (ctf_func_args_by_id(ofp, oid, ofunc.ctc_argc, oids) == CTF_ERR) {
		ret = ctf_set_errno(ifp, ctf_errno(ofp));
		goto out;
	}

	ret = B_TRUE;
	for (i = 0; i < ifunc.ctc_argc; i++) {
		ret = ctf_diff_type(cds, ifp, iids[i], ofp, oids[i]);
		if (ret != B_FALSE)
			goto out;
	}
	ret = B_FALSE;

out:
	ctf_free(iids, sizeof (ctf_id_t) * ifunc.ctc_argc);
	ctf_free(oids, sizeof (ctf_id_t) * ofunc.ctc_argc);
	return (ret);
}

/*
 * Two structures are the same if every member is identical to its corresponding
 * type, at the same offset, and has the same name, as well as them having the
 * same overall size.
 */
static int
ctf_diff_struct(ctf_diff_t *cds, ctf_file_t *ifp, ctf_id_t iid, ctf_file_t *ofp,
    ctf_id_t oid)
{
	ctf_file_t *oifp;
	const ctf_type_t *itp, *otp;
	ssize_t isize, iincr, osize, oincr;
	const ctf_member_t *imp, *omp;
	const ctf_lmember_t *ilmp, *olmp;
	int n;
	ctf_diff_guess_t *cdg;

	oifp = ifp;

	if ((itp = ctf_lookup_by_id(&ifp, iid)) == NULL)
		return (CTF_ERR);

	if ((otp = ctf_lookup_by_id(&ofp, oid)) == NULL)
		return (ctf_set_errno(oifp, ctf_errno(ofp)));

	if (ctf_type_size(ifp, iid) != ctf_type_size(ofp, oid))
		return (B_TRUE);

	if (LCTF_INFO_VLEN(ifp, itp->ctt_info) !=
	    LCTF_INFO_VLEN(ofp, otp->ctt_info))
		return (B_TRUE);

	(void) ctf_get_ctt_size(ifp, itp, &isize, &iincr);
	(void) ctf_get_ctt_size(ofp, otp, &osize, &oincr);

	if (ifp->ctf_version == CTF_VERSION_1 || isize < CTF_LSTRUCT_THRESH) {
		imp = (const ctf_member_t *)((uintptr_t)itp + iincr);
		ilmp = NULL;
	} else {
		imp = NULL;
		ilmp = (const ctf_lmember_t *)((uintptr_t)itp + iincr);
	}

	if (ofp->ctf_version == CTF_VERSION_1 || osize < CTF_LSTRUCT_THRESH) {
		omp = (const ctf_member_t *)((uintptr_t)otp + oincr);
		olmp = NULL;
	} else {
		omp = NULL;
		olmp = (const ctf_lmember_t *)((uintptr_t)otp + oincr);
	}

	/*
	 * Insert our assumption that they're equal for the moment.
	 */
	cdg = ctf_alloc(sizeof (ctf_diff_guess_t));
	if (cdg == NULL)
		return (ctf_set_errno(ifp, ENOMEM));
	cdg->cdg_iid = iid;
	cdg->cdg_oid = oid;
	cdg->cdg_next = cds->cds_guess;
	cds->cds_guess = cdg;
	cds->cds_forward[TINDEX(iid)] = oid;
	cds->cds_reverse[TINDEX(oid)] = iid;

	for (n = LCTF_INFO_VLEN(ifp, itp->ctt_info); n != 0; n--) {
		const char *iname, *oname;
		ulong_t ioff, ooff;
		ctf_id_t itype, otype;
		int ret;

		if (imp != NULL) {
			iname = ctf_strptr(ifp, imp->ctm_name);
			ioff = imp->ctm_offset;
			itype = imp->ctm_type;
		} else {
			iname = ctf_strptr(ifp, ilmp->ctlm_name);
			ioff = CTF_LMEM_OFFSET(ilmp);
			itype = ilmp->ctlm_type;
		}

		if (omp != NULL) {
			oname = ctf_strptr(ofp, omp->ctm_name);
			ooff = omp->ctm_offset;
			otype = omp->ctm_type;
		} else {
			oname = ctf_strptr(ofp, olmp->ctlm_name);
			ooff = CTF_LMEM_OFFSET(olmp);
			otype = olmp->ctlm_type;
		}

		if (ioff != ooff) {
			return (B_TRUE);
		}
		if (strcmp(iname, oname) != 0) {
			return (B_TRUE);
		}
		ret = ctf_diff_type(cds, ifp, itype, ofp, otype);
		if (ret != B_FALSE) {
			return (ret);
		}

		/* Advance our pointers */
		if (imp != NULL)
			imp++;
		if (ilmp != NULL)
			ilmp++;
		if (omp != NULL)
			omp++;
		if (olmp != NULL)
			olmp++;
	}

	return (B_FALSE);
}

/*
 * Two unions are the same if they have the same set of members. This is similar
 * to, but slightly different from a struct. The offsets of members don't
 * matter. However, there is no guarantee of ordering so we have to fall back to
 * doing an O(N^2) scan.
 */
typedef struct ctf_diff_union_member {
	ctf_diff_t *cdum_cds;
	ctf_file_t *cdum_fp;
	ctf_file_t *cdum_iterfp;
	const char *cdum_name;
	ctf_id_t cdum_type;
	int cdum_ret;
} ctf_diff_union_member_t;

typedef struct ctf_diff_union_fp {
	ctf_diff_t *cduf_cds;
	ctf_file_t *cduf_curfp;
	ctf_file_t *cduf_altfp;
	ctf_id_t cduf_type;
	int cduf_ret;
} ctf_diff_union_fp_t;

/* ARGSUSED */
static int
ctf_diff_union_check_member(const char *name, ctf_id_t id, ulong_t off,
    void *arg)
{
	int ret;
	ctf_diff_union_member_t *cdump = arg;

	if (strcmp(name, cdump->cdum_name) != 0)
		return (0);

	ret = ctf_diff_type(cdump->cdum_cds, cdump->cdum_fp, cdump->cdum_type,
	    cdump->cdum_iterfp, id);
	if (ret == CTF_ERR) {
		cdump->cdum_ret = CTF_ERR;
		return (1);
	}

	if (ret == B_FALSE) {
		cdump->cdum_ret = B_FALSE;
		/* Return non-zero to stop iteration as we have a match */
		return (1);
	}

	return (0);
}

/* ARGSUSED */
static int
ctf_diff_union_check_fp(const char *name, ctf_id_t id, ulong_t off, void *arg)
{
	int ret;
	ctf_diff_union_member_t cdum;
	ctf_diff_union_fp_t *cdufp = arg;

	cdum.cdum_cds = cdufp->cduf_cds;
	cdum.cdum_fp = cdufp->cduf_curfp;
	cdum.cdum_iterfp = cdufp->cduf_altfp;
	cdum.cdum_name = name;
	cdum.cdum_type = id;
	cdum.cdum_ret = B_TRUE;

	ret = ctf_member_iter(cdum.cdum_iterfp, cdufp->cduf_type,
	    ctf_diff_union_check_member, &cdum);
	if (ret == 0 || cdum.cdum_ret == CTF_ERR) {
		/* No match found or error, terminate now */
		cdufp->cduf_ret = cdum.cdum_ret;
		return (1);
	} else if (ret == CTF_ERR) {
		(void) ctf_set_errno(cdum.cdum_fp, ctf_errno(cdum.cdum_iterfp));
		cdufp->cduf_ret = CTF_ERR;
		return (1);
	} else {
		ASSERT(cdum.cdum_ret == B_FALSE);
		cdufp->cduf_ret = cdum.cdum_ret;
		return (0);
	}
}

static int
ctf_diff_union(ctf_diff_t *cds, ctf_file_t *ifp, ctf_id_t iid, ctf_file_t *ofp,
    ctf_id_t oid)
{
	ctf_file_t *oifp;
	const ctf_type_t *itp, *otp;
	ctf_diff_union_fp_t cduf;
	ctf_diff_guess_t *cdg;
	int ret;

	oifp = ifp;
	if ((itp = ctf_lookup_by_id(&ifp, iid)) == NULL)
		return (CTF_ERR);
	if ((otp = ctf_lookup_by_id(&ofp, oid)) == NULL)
		return (ctf_set_errno(oifp, ctf_errno(ofp)));

	if (LCTF_INFO_VLEN(ifp, itp->ctt_info) !=
	    LCTF_INFO_VLEN(ofp, otp->ctt_info))
		return (B_TRUE);

	cdg = ctf_alloc(sizeof (ctf_diff_guess_t));
	if (cdg == NULL)
		return (ctf_set_errno(ifp, ENOMEM));
	cdg->cdg_iid = iid;
	cdg->cdg_oid = oid;
	cdg->cdg_next = cds->cds_guess;
	cds->cds_guess = cdg;
	cds->cds_forward[TINDEX(iid)] = oid;
	cds->cds_reverse[TINDEX(oid)] = iid;

	cduf.cduf_cds = cds;
	cduf.cduf_curfp = ifp;
	cduf.cduf_altfp = ofp;
	cduf.cduf_type = oid;
	cduf.cduf_ret = B_TRUE;
	ret = ctf_member_iter(ifp, iid, ctf_diff_union_check_fp, &cduf);
	if (ret != CTF_ERR)
		ret = cduf.cduf_ret;

	return (ret);
}

/*
 * Two enums are equivalent if they share the same underlying type and they have
 * the same set of members.
 */
static int
ctf_diff_enum(ctf_file_t *ifp, ctf_id_t iid, ctf_file_t *ofp, ctf_id_t oid)
{
	ctf_file_t *oifp;
	const ctf_type_t *itp, *otp;
	ssize_t iincr, oincr;
	const ctf_enum_t *iep, *oep;
	int n;

	oifp = ifp;
	if ((itp = ctf_lookup_by_id(&ifp, iid)) == NULL)
		return (CTF_ERR);
	if ((otp = ctf_lookup_by_id(&ofp, oid)) == NULL)
		return (ctf_set_errno(oifp, ctf_errno(ofp)));

	if (LCTF_INFO_VLEN(ifp, itp->ctt_info) !=
	    LCTF_INFO_VLEN(ofp, otp->ctt_info))
		return (B_TRUE);

	(void) ctf_get_ctt_size(ifp, itp, NULL, &iincr);
	(void) ctf_get_ctt_size(ofp, otp, NULL, &oincr);
	iep = (const ctf_enum_t *)((uintptr_t)itp + iincr);
	oep = (const ctf_enum_t *)((uintptr_t)otp + oincr);

	for (n = LCTF_INFO_VLEN(ifp, itp->ctt_info); n != 0;
	    n--, iep++, oep++) {
		if (strcmp(ctf_strptr(ifp, iep->cte_name),
		    ctf_strptr(ofp, oep->cte_name)) != 0)
			return (B_TRUE);

		if (iep->cte_value != oep->cte_value)
			return (B_TRUE);
	}

	return (B_FALSE);
}

/*
 * Two forwards are equivalent in one of two cases. If both are forwards, than
 * they are the same. Otherwise, they're equivalent if one is a struct or union
 * and the other is a forward.
 */
static int
ctf_diff_forward(ctf_file_t *ifp, ctf_id_t iid, ctf_file_t *ofp, ctf_id_t oid)
{
	int ikind, okind;

	ikind = ctf_type_kind(ifp, iid);
	okind = ctf_type_kind(ofp, oid);

	if (ikind == okind) {
		ASSERT(ikind == CTF_K_FORWARD);
		return (B_FALSE);
	} else if (ikind == CTF_K_FORWARD) {
		return (okind != CTF_K_UNION && okind != CTF_K_STRUCT);
	} else {
		return (ikind != CTF_K_UNION && ikind != CTF_K_STRUCT);
	}
}

/*
 * Are two types equivalent?
 */
int
ctf_diff_type(ctf_diff_t *cds, ctf_file_t *ifp, ctf_id_t iid, ctf_file_t *ofp,
    ctf_id_t oid)
{
	int ret, ikind, okind;

	/* Do a quick short circuit */
	if (ifp == ofp && iid == oid)
		return (B_FALSE);

	/*
	 * Check if it's something we've already encountered in a forward
	 * reference or forward negative table. Also double check the reverse
	 * table.
	 */
	if (cds->cds_forward[TINDEX(iid)] == oid)
		return (B_FALSE);
	if (cds->cds_forward[TINDEX(iid)] != 0)
		return (B_TRUE);
	if (cds->cds_reverse[TINDEX(oid)] == iid)
		return (B_FALSE);
	if ((cds->cds_flags & CTF_DIFF_F_IGNORE_INTNAMES) == 0 &&
	    cds->cds_reverse[TINDEX(oid)] != 0)
		return (B_TRUE);

	ikind = ctf_type_kind(ifp, iid);
	okind = ctf_type_kind(ofp, oid);

	if (ikind != okind &&
	    ikind != CTF_K_FORWARD && okind != CTF_K_FORWARD)
			return (B_TRUE);

	/* Check names */
	if ((ret = ctf_diff_name(ifp, iid, ofp, oid)) != B_FALSE) {
		if (ikind != okind || ikind != CTF_K_INTEGER ||
		    (cds->cds_flags & CTF_DIFF_F_IGNORE_INTNAMES) == 0)
			return (ret);
	}

	if (ikind == CTF_K_FORWARD || okind == CTF_K_FORWARD)
		return (ctf_diff_forward(ifp, iid, ofp, oid));

	switch (ikind) {
	case CTF_K_INTEGER:
	case CTF_K_FLOAT:
		ret = ctf_diff_number(ifp, iid, ofp, oid);
		break;
	case CTF_K_ARRAY:
		ret = ctf_diff_array(cds, ifp, iid, ofp, oid);
		break;
	case CTF_K_FUNCTION:
		ret = ctf_diff_fptr(cds, ifp, iid, ofp, oid);
		break;
	case CTF_K_STRUCT:
		ret = ctf_diff_struct(cds, ifp, iid, ofp, oid);
		break;
	case CTF_K_UNION:
		ret = ctf_diff_union(cds, ifp, iid, ofp, oid);
		break;
	case CTF_K_ENUM:
		ret = ctf_diff_enum(ifp, iid, ofp, oid);
		break;
	case CTF_K_FORWARD:
		ret = ctf_diff_forward(ifp, iid, ofp, oid);
		break;
	case CTF_K_TYPEDEF:
		ret = ctf_diff_typedef(cds, ifp, iid, ofp, oid);
		break;
	case CTF_K_POINTER:
	case CTF_K_VOLATILE:
	case CTF_K_CONST:
	case CTF_K_RESTRICT:
		ret = ctf_diff_qualifier(cds, ifp, iid, ofp, oid);
		break;
	case CTF_K_UNKNOWN:
		/*
		 * The current CTF tools use CTF_K_UNKNOWN as a padding type. We
		 * always declare two instances of CTF_K_UNKNOWN as different,
		 * even though this leads to additional diff noise.
		 */
		ret = B_TRUE;
		break;
	default:
		abort();
	}

	return (ret);
}

/*
 * Walk every type in the first container and try to find a match in the second.
 * If there is a match, then update both the forward and reverse mapping tables.
 *
 * The self variable tells us whether or not we should be comparing the input
 * ctf container with itself or not.
 */
static int
ctf_diff_pass1(ctf_diff_t *cds, boolean_t self)
{
	int i, j, diff;
	int istart, iend, jstart, jend;

	istart = 1;
	iend = cds->cds_ifp->ctf_typemax;
	if (cds->cds_ifp->ctf_flags & LCTF_CHILD) {
		istart += CTF_CHILD_START;
		iend += CTF_CHILD_START;
	}

	jstart = 1;
	jend = cds->cds_ofp->ctf_typemax;
	if (cds->cds_ofp->ctf_flags & LCTF_CHILD) {
		jstart += CTF_CHILD_START;
		jend += CTF_CHILD_START;
	}

	for (i = istart; i <= iend; i++) {
		diff = B_TRUE;

		/*
		 * If we're doing a self diff for dedup purposes, then we want
		 * to ensure that we compare a type i with every type in the
		 * range, [ 1, i ). Yes, this does mean that when i equals 1,
		 * we won't compare anything.
		 */
		if (self == B_TRUE) {
			jstart = istart;
			jend = i - 1;
		}
		for (j = jstart; j <= jend; j++) {
			ctf_diff_guess_t *cdg, *tofree;

			ASSERT(cds->cds_guess == NULL);
			diff = ctf_diff_type(cds, cds->cds_ifp, i,
			    cds->cds_ofp, j);
			if (diff == CTF_ERR)
				return (CTF_ERR);

			/* Clean up our guesses */
			cdg = cds->cds_guess;
			cds->cds_guess = NULL;
			while (cdg != NULL) {
				if (diff == B_TRUE) {
					cds->cds_forward[TINDEX(cdg->cdg_iid)] =
					    0;
					cds->cds_reverse[TINDEX(cdg->cdg_oid)] =
					    0;
				}
				tofree = cdg;
				cdg = cdg->cdg_next;
				ctf_free(tofree, sizeof (ctf_diff_guess_t));
			}

			/* Found a hit, update the tables */
			if (diff == B_FALSE) {
				cds->cds_forward[TINDEX(i)] = j;
				if (cds->cds_reverse[TINDEX(j)] == 0)
					cds->cds_reverse[TINDEX(j)] = i;
				break;
			}
		}

		/* Call the callback at this point */
		if (diff == B_TRUE) {
			cds->cds_forward[TINDEX(i)] = CTF_ERR;
			cds->cds_func(cds->cds_ifp, i, B_FALSE, NULL, CTF_ERR,
			    cds->cds_arg);
		} else {
			cds->cds_func(cds->cds_ifp, i, B_TRUE, cds->cds_ofp, j,
			    cds->cds_arg);
		}
	}

	return (0);
}

/*
 * Now we need to walk the second container and emit anything that we didn't
 * find as common in the first pass.
 */
static int
ctf_diff_pass2(ctf_diff_t *cds)
{
	int i, start, end;

	start = 0x1;
	end = cds->cds_ofp->ctf_typemax;
	if (cds->cds_ofp->ctf_flags & LCTF_CHILD) {
		start += CTF_CHILD_START;
		end += CTF_CHILD_START;
	}

	for (i = start; i <= end; i++) {
		if (cds->cds_reverse[TINDEX(i)] != 0)
			continue;
		cds->cds_func(cds->cds_ofp, i, B_FALSE, NULL, CTF_ERR,
		    cds->cds_arg);
	}

	return (0);
}

int
ctf_diff_init(ctf_file_t *ifp, ctf_file_t *ofp, ctf_diff_t **cdsp)
{
	ctf_diff_t *cds;
	size_t fsize, rsize;

	cds = ctf_alloc(sizeof (ctf_diff_t));
	if (cds == NULL)
		return (ctf_set_errno(ifp, ENOMEM));

	bzero(cds, sizeof (ctf_diff_t));
	cds->cds_ifp = ifp;
	cds->cds_ofp = ofp;

	fsize = sizeof (ctf_id_t) * ifp->ctf_typemax;
	rsize = sizeof (ctf_id_t) * ofp->ctf_typemax;
	if (ifp->ctf_flags & LCTF_CHILD)
		fsize += CTF_CHILD_START * sizeof (ctf_id_t);
	if (ofp->ctf_flags & LCTF_CHILD)
		rsize += CTF_CHILD_START * sizeof (ctf_id_t);

	cds->cds_forward = ctf_alloc(fsize);
	if (cds->cds_forward == NULL) {
		ctf_free(cds, sizeof (ctf_diff_t));
		return (ctf_set_errno(ifp, ENOMEM));
	}
	cds->cds_fsize = fsize;
	cds->cds_reverse = ctf_alloc(rsize);
	if (cds->cds_reverse == NULL) {
		ctf_free(cds->cds_forward, fsize);
		ctf_free(cds, sizeof (ctf_diff_t));
		return (ctf_set_errno(ifp, ENOMEM));
	}
	cds->cds_rsize = rsize;
	bzero(cds->cds_forward, fsize);
	bzero(cds->cds_reverse, rsize);

	cds->cds_ifp->ctf_refcnt++;
	cds->cds_ofp->ctf_refcnt++;
	*cdsp = cds;
	return (0);
}

int
ctf_diff_types(ctf_diff_t *cds, ctf_diff_type_f cb, void *arg)
{
	int ret;

	cds->cds_func = cb;
	cds->cds_arg = arg;

	ret = ctf_diff_pass1(cds, B_FALSE);
	if (ret == 0)
		ret = ctf_diff_pass2(cds);

	cds->cds_func = NULL;
	cds->cds_arg = NULL;
	cds->cds_tvalid = B_TRUE;
	return (ret);
}

/*
 * Do a diff where we're comparing a container with itself. In other words we'd
 * like to know what types are actually duplicates of existing types in the
 * container.
 *
 * Note this should remain private to libctf and not be exported in the public
 * mapfile for the time being.
 */
int
ctf_diff_self(ctf_diff_t *cds, ctf_diff_type_f cb, void *arg)
{
	if (cds->cds_ifp != cds->cds_ofp)
		return (EINVAL);

	cds->cds_func = cb;
	cds->cds_arg = arg;

	return (ctf_diff_pass1(cds, B_TRUE));
}


void
ctf_diff_fini(ctf_diff_t *cds)
{
	ctf_diff_guess_t *cdg;
	size_t fsize, rsize;

	if (cds == NULL)
		return;

	cds->cds_ifp->ctf_refcnt--;
	cds->cds_ofp->ctf_refcnt--;

	fsize = sizeof (ctf_id_t) * cds->cds_ifp->ctf_typemax;
	rsize = sizeof (ctf_id_t) * cds->cds_ofp->ctf_typemax;
	if (cds->cds_ifp->ctf_flags & LCTF_CHILD)
		fsize += CTF_CHILD_START * sizeof (ctf_id_t);
	if (cds->cds_ofp->ctf_flags & LCTF_CHILD)
		rsize += CTF_CHILD_START * sizeof (ctf_id_t);

	if (cds->cds_ifuncs != NULL)
		ctf_free(cds->cds_ifuncs,
		    sizeof (ctf_diff_func_t) * cds->cds_nifuncs);
	if (cds->cds_ofuncs != NULL)
		ctf_free(cds->cds_ofuncs,
		    sizeof (ctf_diff_func_t) * cds->cds_nofuncs);
	if (cds->cds_iobj != NULL)
		ctf_free(cds->cds_iobj,
		    sizeof (ctf_diff_obj_t) * cds->cds_niobj);
	if (cds->cds_oobj != NULL)
		ctf_free(cds->cds_oobj,
		    sizeof (ctf_diff_obj_t) * cds->cds_noobj);
	cdg = cds->cds_guess;
	while (cdg != NULL) {
		ctf_diff_guess_t *tofree = cdg;
		cdg = cdg->cdg_next;
		ctf_free(tofree, sizeof (ctf_diff_guess_t));
	}
	if (cds->cds_forward != NULL)
		ctf_free(cds->cds_forward, cds->cds_fsize);
	if (cds->cds_reverse != NULL)
		ctf_free(cds->cds_reverse, cds->cds_rsize);
	ctf_free(cds, sizeof (ctf_diff_t));
}

uint_t
ctf_diff_getflags(ctf_diff_t *cds)
{
	return (cds->cds_flags);
}

int
ctf_diff_setflags(ctf_diff_t *cds, uint_t flags)
{
	if ((flags & ~CTF_DIFF_F_IGNORE_INTNAMES) != 0)
		return (ctf_set_errno(cds->cds_ifp, EINVAL));

	cds->cds_flags = flags;
	return (0);
}

static boolean_t
ctf_diff_symid(ctf_diff_t *cds, ctf_id_t iid, ctf_id_t oid)
{
	ctf_file_t *ifp, *ofp;

	ifp = cds->cds_ifp;
	ofp = cds->cds_ofp;

	/*
	 * If we have parent containers on the scene here, we need to go through
	 * and do a full diff check because a diff for types will not actually
	 * go through and check types in the parent container.
	 */
	if (iid == 0 || oid == 0)
		return (iid == oid ? B_FALSE: B_TRUE);

	if (!(ifp->ctf_flags & LCTF_CHILD) && !(ofp->ctf_flags & LCTF_CHILD)) {
		if (cds->cds_forward[TINDEX(iid)] != oid)
			return (B_TRUE);
		return (B_FALSE);
	}

	return (ctf_diff_type(cds, ifp, iid, ofp, oid));
}

/* ARGSUSED */
static void
ctf_diff_void_cb(ctf_file_t *ifp, ctf_id_t iid, boolean_t same, ctf_file_t *ofp,
    ctf_id_t oid, void *arg)
{
}

/* ARGSUSED */
static int
ctf_diff_func_count(const char *name, ulong_t symidx, ctf_funcinfo_t *fip,
    void *arg)
{
	uint32_t *ip = arg;

	*ip = *ip + 1;
	return (0);
}

/* ARGSUSED */
static int
ctf_diff_func_fill_cb(const char *name, ulong_t symidx, ctf_funcinfo_t *fip,
    void *arg)
{
	uint_t *next, max;
	ctf_diff_func_t *funcptr;
	ctf_diff_t *cds = arg;

	if (cds->cds_ffillip == B_TRUE) {
		max = cds->cds_nifuncs;
		next = &cds->cds_nextifunc;
		funcptr = cds->cds_ifuncs + *next;
	} else {
		max = cds->cds_nofuncs;
		next = &cds->cds_nextofunc;
		funcptr = cds->cds_ofuncs + *next;

	}

	VERIFY(*next < max);
	funcptr->cdf_name = name;
	funcptr->cdf_symidx = symidx;
	funcptr->cdf_matchidx = ULONG_MAX;
	*next = *next + 1;

	return (0);
}

int
ctf_diff_func_fill(ctf_diff_t *cds)
{
	int ret;
	uint32_t ifcount, ofcount, idcnt, cti;
	ulong_t i, j;
	ctf_id_t *iids, *oids;

	ifcount = 0;
	ofcount = 0;
	idcnt = 0;
	iids = NULL;
	oids = NULL;

	ret = ctf_function_iter(cds->cds_ifp, ctf_diff_func_count, &ifcount);
	if (ret != 0)
		return (ret);
	ret = ctf_function_iter(cds->cds_ofp, ctf_diff_func_count, &ofcount);
	if (ret != 0)
		return (ret);

	cds->cds_ifuncs = ctf_alloc(sizeof (ctf_diff_func_t) * ifcount);
	if (cds->cds_ifuncs == NULL)
		return (ctf_set_errno(cds->cds_ifp, ENOMEM));

	cds->cds_nifuncs = ifcount;
	cds->cds_nextifunc = 0;

	cds->cds_ofuncs = ctf_alloc(sizeof (ctf_diff_func_t) * ofcount);
	if (cds->cds_ofuncs == NULL)
		return (ctf_set_errno(cds->cds_ifp, ENOMEM));

	cds->cds_nofuncs = ofcount;
	cds->cds_nextofunc = 0;

	cds->cds_ffillip = B_TRUE;
	if ((ret = ctf_function_iter(cds->cds_ifp, ctf_diff_func_fill_cb,
	    cds)) != 0)
		return (ret);

	cds->cds_ffillip = B_FALSE;
	if ((ret = ctf_function_iter(cds->cds_ofp, ctf_diff_func_fill_cb,
	    cds)) != 0)
		return (ret);

	/*
	 * Everything is initialized to not match. This could probably be faster
	 * with something that used a hash. But this part of the diff isn't used
	 * by merge.
	 */
	for (i = 0; i < cds->cds_nifuncs; i++) {
		for (j = 0; j < cds->cds_nofuncs; j++) {
			ctf_diff_func_t *ifd, *ofd;
			ctf_funcinfo_t ifip, ofip;
			boolean_t match;

			ifd = &cds->cds_ifuncs[i];
			ofd = &cds->cds_ofuncs[j];
			if (strcmp(ifd->cdf_name, ofd->cdf_name) != 0)
				continue;

			ret = ctf_func_info(cds->cds_ifp, ifd->cdf_symidx,
			    &ifip);
			if (ret != 0)
				goto out;
			ret = ctf_func_info(cds->cds_ofp, ofd->cdf_symidx,
			    &ofip);
			if (ret != 0) {
				ret = ctf_set_errno(cds->cds_ifp,
				    ctf_errno(cds->cds_ofp));
				goto out;
			}

			if (ifip.ctc_argc != ofip.ctc_argc &&
			    ifip.ctc_flags != ofip.ctc_flags)
				continue;

			/* Validate return type and arguments are the same */
			if (ctf_diff_symid(cds, ifip.ctc_return,
			    ofip.ctc_return))
				continue;

			if (ifip.ctc_argc > idcnt) {
				if (iids != NULL)
					ctf_free(iids,
					    sizeof (ctf_id_t) * idcnt);
				if (oids != NULL)
					ctf_free(oids,
					    sizeof (ctf_id_t) * idcnt);
				iids = oids = NULL;
				idcnt = ifip.ctc_argc;
				iids = ctf_alloc(sizeof (ctf_id_t) * idcnt);
				if (iids == NULL) {
					ret = ctf_set_errno(cds->cds_ifp,
					    ENOMEM);
					goto out;
				}
				oids = ctf_alloc(sizeof (ctf_id_t) * idcnt);
				if (iids == NULL) {
					ret = ctf_set_errno(cds->cds_ifp,
					    ENOMEM);
					goto out;
				}
			}

			if ((ret = ctf_func_args(cds->cds_ifp, ifd->cdf_symidx,
			    ifip.ctc_argc, iids)) != 0)
				goto out;
			if ((ret = ctf_func_args(cds->cds_ofp, ofd->cdf_symidx,
			    ofip.ctc_argc, oids)) != 0)
				goto out;

			match = B_TRUE;
			for (cti = 0; cti < ifip.ctc_argc; cti++) {
				if (ctf_diff_symid(cds, iids[cti], oids[cti])) {
					match = B_FALSE;
					break;
				}
			}

			if (match == B_FALSE)
				continue;

			ifd->cdf_matchidx = j;
			ofd->cdf_matchidx = i;
			break;
		}
	}

	ret = 0;

out:
	if (iids != NULL)
		ctf_free(iids, sizeof (ctf_id_t) * idcnt);
	if (oids != NULL)
		ctf_free(oids, sizeof (ctf_id_t) * idcnt);

	return (ret);
}

/*
 * In general, two functions are the same, if they have the same name and their
 * arguments have the same types, including the return type. Like types, we
 * basically have to do this in two passes. In the first phase we walk every
 * type in the first container and try to find a match in the second.
 */
int
ctf_diff_functions(ctf_diff_t *cds, ctf_diff_func_f cb, void *arg)
{
	int ret;
	ulong_t i;

	if (cds->cds_tvalid == B_FALSE) {
		if ((ret = ctf_diff_types(cds, ctf_diff_void_cb, NULL)) != 0)
			return (ret);
	}

	if (cds->cds_fvalid == B_FALSE) {
		if ((ret = ctf_diff_func_fill(cds)) != 0)
			return (ret);
		cds->cds_fvalid = B_TRUE;
	}

	for (i = 0; i < cds->cds_nifuncs; i++) {
		if (cds->cds_ifuncs[i].cdf_matchidx == ULONG_MAX) {
			cb(cds->cds_ifp, cds->cds_ifuncs[i].cdf_symidx,
			    B_FALSE, NULL, ULONG_MAX, arg);
		} else {
			ulong_t idx = cds->cds_ifuncs[i].cdf_matchidx;
			cb(cds->cds_ifp, cds->cds_ifuncs[i].cdf_symidx, B_TRUE,
			    cds->cds_ofp, cds->cds_ofuncs[idx].cdf_symidx, arg);
		}
	}

	for (i = 0; i < cds->cds_nofuncs; i++) {
		if (cds->cds_ofuncs[i].cdf_matchidx != ULONG_MAX)
			continue;
		cb(cds->cds_ofp, cds->cds_ofuncs[i].cdf_symidx, B_FALSE,
		    NULL, ULONG_MAX, arg);
	}

	return (0);
}

static int
ctf_diff_obj_fill_cb(const char *name, ctf_id_t id, ulong_t symidx, void *arg)
{
	uint_t *next, max;
	ctf_diff_obj_t *objptr;
	ctf_diff_t *cds = arg;

	if (cds->cds_ofillip == B_TRUE) {
		max = cds->cds_niobj;
		next = &cds->cds_nextiobj;
		objptr = cds->cds_iobj + *next;
	} else {
		max = cds->cds_noobj;
		next = &cds->cds_nextoobj;
		objptr = cds->cds_oobj+ *next;

	}

	VERIFY(*next < max);
	objptr->cdo_name = name;
	objptr->cdo_symidx = symidx;
	objptr->cdo_id = id;
	objptr->cdo_matchidx = ULONG_MAX;
	*next = *next + 1;

	return (0);
}

/* ARGSUSED */
static int
ctf_diff_obj_count(const char *name, ctf_id_t id, ulong_t symidx, void *arg)
{
	uint32_t *count = arg;

	*count = *count + 1;

	return (0);
}


static int
ctf_diff_obj_fill(ctf_diff_t *cds)
{
	int ret;
	uint32_t iocount, oocount;
	ulong_t i, j;

	iocount = 0;
	oocount = 0;

	ret = ctf_object_iter(cds->cds_ifp, ctf_diff_obj_count, &iocount);
	if (ret != 0)
		return (ret);

	ret = ctf_object_iter(cds->cds_ofp, ctf_diff_obj_count, &oocount);
	if (ret != 0)
		return (ret);

	cds->cds_iobj = ctf_alloc(sizeof (ctf_diff_obj_t) * iocount);
	if (cds->cds_iobj == NULL)
		return (ctf_set_errno(cds->cds_ifp, ENOMEM));
	cds->cds_niobj = iocount;
	cds->cds_nextiobj = 0;

	cds->cds_oobj = ctf_alloc(sizeof (ctf_diff_obj_t) * oocount);
	if (cds->cds_oobj == NULL)
		return (ctf_set_errno(cds->cds_ifp, ENOMEM));
	cds->cds_noobj = oocount;
	cds->cds_nextoobj = 0;

	cds->cds_ofillip = B_TRUE;
	if ((ret = ctf_object_iter(cds->cds_ifp, ctf_diff_obj_fill_cb,
	    cds)) != 0)
		return (ret);

	cds->cds_ofillip = B_FALSE;
	if ((ret = ctf_object_iter(cds->cds_ofp, ctf_diff_obj_fill_cb,
	    cds)) != 0)
		return (ret);

	for (i = 0; i < cds->cds_niobj; i++) {
		for (j = 0; j < cds->cds_noobj; j++) {
			ctf_diff_obj_t *id, *od;

			id = &cds->cds_iobj[i];
			od = &cds->cds_oobj[j];

			if (id->cdo_name == NULL || od->cdo_name == NULL)
				continue;
			if (strcmp(id->cdo_name, od->cdo_name) != 0)
				continue;

			if (ctf_diff_symid(cds, id->cdo_id, od->cdo_id)) {
				continue;
			}

			id->cdo_matchidx = j;
			od->cdo_matchidx = i;
			break;
		}
	}

	return (0);
}

int
ctf_diff_objects(ctf_diff_t *cds, ctf_diff_obj_f cb, void *arg)
{
	int ret;
	ulong_t i;

	if (cds->cds_tvalid == B_FALSE) {
		if ((ret = ctf_diff_types(cds, ctf_diff_void_cb, NULL)) != 0)
			return (ret);
	}

	if (cds->cds_ovalid == B_FALSE) {
		if ((ret = ctf_diff_obj_fill(cds)) != 0)
			return (ret);
		cds->cds_ovalid = B_TRUE;
	}

	for (i = 0; i < cds->cds_niobj; i++) {
		ctf_diff_obj_t *o = &cds->cds_iobj[i];

		if (cds->cds_iobj[i].cdo_matchidx == ULONG_MAX) {
			cb(cds->cds_ifp, o->cdo_symidx, o->cdo_id, B_FALSE,
			    NULL, ULONG_MAX, CTF_ERR, arg);
		} else {
			ctf_diff_obj_t *alt = &cds->cds_oobj[o->cdo_matchidx];
			cb(cds->cds_ifp, o->cdo_symidx, o->cdo_id, B_TRUE,
			    cds->cds_ofp, alt->cdo_symidx, alt->cdo_id, arg);
		}
	}

	for (i = 0; i < cds->cds_noobj; i++) {
		ctf_diff_obj_t *o = &cds->cds_oobj[i];
		if (o->cdo_matchidx != ULONG_MAX)
			continue;
		cb(cds->cds_ofp, o->cdo_symidx, o->cdo_id, B_FALSE, NULL,
		    ULONG_MAX, CTF_ERR, arg);
	}

	return (0);
}