8322 nl: misleading-indentation

[unleashed/tickless.git] / usr / src / cmd / sgs / libld / common / order.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (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
 * or http://www.opensolaris.org/os/licensing.
 * 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 (c) 1996, 2010, Oracle and/or its affiliates. All rights reserved.
 */

/*
 * Processing of SHF_ORDERED sections.
 */
#include        <stdio.h>
#include        <fcntl.h>
#include        <link.h>
#include        <debug.h>
#include        "msg.h"
#include        "_libld.h"

/*
 * Section Ordering History/Background:
 *
 * There are two forms of section ordering, SHF_ORDERED, and SHF_LINK_ORDER.
 *
 * SHF_ORDERED was invented at Sun in order to support the PowerPC port
 * of Solaris 2.6, which used it for sorting tag words which describe
 * the state of callee saves registers for given PC ranges. It was defined
 * in the OS specific ELF section flag range. Some other values were defined
 * at the same time:
 *      SHF_EXCLUDE - Section is to be excluded from executables or shared
 *              objects, and only kept in relocatable object output.
 *      SHN_BEFORE/SHN_AFTER - Sections are placed before/after all other
 *              sections, in the order they are encountered by the linker.
 * Although initially conceived to support the PowerPC, the functionality
 * was implemented for all platforms, and was later used to manage C++
 * exceptions and stack unwinding. The PowerPC port was discontinued after
 * one release, but SHF_ORDERED lives on.
 *
 * SHF_LINK_ORDER was invented later by the wider ELF community, and is
 * therefore assigned a value in the generic ELF section flag range. It is
 * essentially a simpler version of SHF_ORDERED, dispensing with some
 * unnecessary features. The Solaris implementation of SHF_LINK_ORDER uses
 * SHF_EXCLUDE, and SHF_BEFORE/SHN_AFTER as well, but it appears that these
 * are still Solaris-only extensions not used by other implementations.
 * SHF_LINK_ORDER has superseded SHF_ORDERED. The older mechanism is
 * supported for the benefit of old pre-existing objects.
 *
 * -----
 *
 * SHF_ORDERED offers two distinct and separate abilities:
 *
 *      (1) To specify the output section
 *      (2) To optionally be sorted relative to other sorted sections,
 *              using a non-sorted section as a sort key.
 *
 * To  do this, it uses both the sh_link, and sh_info fields:
 *
 *    sh_link
 *      Specifies the output section to receive this input section.
 *      The sh_link field of an SHF_ORDERED section forms a linked list of
 *      sections, all of which must have identical section header flags
 *      (including SHF_ORDERED). The list is terminated by a final section
 *      with a sh_link that points at itself. All input sections in this list
 *      are assigned to the output section of the final section in the list.
 *      Hence, if a section points at itself, the effect is that it gets
 *      assigned to an output section in the usual default manner (i.e. an
 *      output section with the same name as the input). However, it can
 *      point at any arbitrary other section. This is a way to put a section
 *      with one name into an output section with a different name. It should
 *      be noted that this is of little value overall, because the link-editor
 *      already supports a more general feature for directing input sections
 *      to output sections: An input section named .text%foo will be sent to
 *      an output section named ".text", and this works for all sections,
 *      not just ordered ones.
 *
 *    sh_info
 *      If sh_info is in the range (1 <= value < shnum), then this input section
 *      is added to the group of sorted sections. The section referenced by
 *      sh_info must be unsorted, and is used as the sort key.
 *
 *      If sh_info is SHN_BEFORE or SHN_AFTER, it is put in the pre/post group,
 *      in the order it arrives (the before/after classes are not sorted).
 *
 *      If sh_info is "invalid" (typically 0), then this section is added to
 *      the group of non-sorted sections, and goes into the output file in the
 *      order it arrives. This is not a valuable feature, as the same effect
 *      can be achieved more simply by not setting SHF_ORDERED at all.
 *
 * SHF_LINK_ORDER is a simplification of SHF_ORDERED. It uses sh_link to specify
 * the section to use as a sort key and sh_info is set to 0. The standard
 * ".text%foo" mechanism is used to direct input sections to output sections,
 * and unordered sections indicate that by not setting SHF_LINK_ORDER.
 */


/*
 * A "keyshndx" is the section index for the unordered section that should
 * be used as a sort key for a ordered section. Verify that the given
 * keyshndx is valid.
 *
 * exit:
 *      Returns 0 if the keyshndx is valid. A non-zero DBG_ORDER_ code is
 *      returned if the keyshndx is not valid to describe the problem.
 */
inline static Word
is_keyshndx_ok(Ifl_desc *ifl, Word keyshndx)
{
        if ((keyshndx == SHN_BEFORE) || (keyshndx == SHN_AFTER))
                return (0);

        /*
         * Validate the key range.
         */
        if ((keyshndx == 0) || (keyshndx >= ifl->ifl_shnum))
                return (DBG_ORDER_LINK_OUTRANGE);

        /*
         * The section pointed to by keyshndx should not be an ordered section.
         * Strictly speaking, we could test for SHF_ORDERED here instead of
         * ALL_SHF_ORDER as the two ordering flags are not supposed to be
         * mixed. Using ALL_SHF_ORDER costs the same and ensures that such
         * mixing doesn't go undetected.
         */
        if (ifl->ifl_isdesc[keyshndx]->is_shdr->sh_flags & ALL_SHF_ORDER)
                return (DBG_ORDER_INFO_ORDER);

        return (0);
}

/*
 * The sh_link field of an SHF_ORDERED section forms a linked list of
 * sections. The list is terminated by a final section with a sh_link
 * that points at itself. Given the index of an SHF_ORDERED section, find
 * the index of the final section in the list.
 *
 * entry:
 *      ofl - Output file descriptor
 *      ifl - Input file descriptor
 *      ndx - Section index of SHF_ORDERED section
 *      alt_os_name - Address of pointer to string. If the final section
 *              name is different than the section given by ndx, *alt_os_name
 *              will be updated with the name of the final section. The caller
 *              should initialize *alt_os_name to NULL before calling
 *              this routine.
 *
 * exit:
 *      On success: If the final section is different than the section
 *      given by ndx, then *alt_os_name is set to its name. TRUE is returned.
 *
 *      On failure, FALSE is returned.
 */
static Boolean
validate_shf_ordered_dest(Ofl_desc *ofl, Ifl_desc *ifl, Word ndx,
    const char **alt_os_name)
{
        Word    shnum = ifl->ifl_shnum;
        Word    isp1_ndx, isp2_ndx;
        Is_desc *isp1, *isp2;
        int     error = 0;
        size_t  iter = 0;

        /*
         * Traverse the list until we find the termination, or encounter
         * an invalid condition in the object that prevents ordering.
         */
        isp1_ndx = ndx;
        isp1 = ifl->ifl_isdesc[ndx];
        do {
                /*
                 * Obtain index of next section in list. Ensure it is in range.
                 */
                isp2_ndx = isp1->is_shdr->sh_link;
                if ((isp2_ndx == 0) || (isp2_ndx >= shnum)) {
                        error = DBG_ORDER_LINK_OUTRANGE;
                        break;
                }
                isp2 = ifl->ifl_isdesc[isp2_ndx];

                /* The section flags must match exactly */
                if (isp1->is_shdr->sh_flags != isp2->is_shdr->sh_flags) {
                        /*
                         * The case where the next section in the list does
                         * not have the same ordered flag set as the original
                         * ordered section gets a unique error code. This
                         * provides more accurate/useful debugging diagnostics.
                         */
                        error = ((isp2->is_flags & FLG_IS_ORDERED) == 0) ?
                            DBG_ORDER_LINK_ERROR : DBG_ORDER_FLAGS;
                        break;
                }

                /*
                 * The sh_info field specifies the section index of an
                 * unorderd section which will be used as a sort key.
                 * Ensure it is in range. If not, we terminate the list
                 * at the current node instead of continuing on.
                 */
                if ((error = is_keyshndx_ok(ifl, isp2->is_shdr->sh_info)) != 0)
                        break;

                /* If the section points at itself, it terminates the list */
                if (isp1_ndx == isp2_ndx)
                        break;

                /*
                 * Advance to next section in list
                 */
                isp1_ndx = isp2_ndx;
                isp1 = isp2;

                /*
                 * If we loop more times than the input file has sections,
                 * we have encountered a malformed object in which the list
                 * of SHF_ORDERED sections has a cycle. This can only happen
                 * if the compiler generating the object has a bad bug.
                 */
                if (++iter >= shnum) {
                        error = DBG_ORDER_CYCLIC;
                        break;
                }
        /* CONSTANTCONDITION */
        } while (1);

        /*
         * If we have found a problem, issue a debug diagnostic and map
         * the output section to 0. This indicates that the section should
         * remove the ordering flag and treat it as a standard section.
         */
        if (error != 0) {
                isp2_ndx = 0;
                DBG_CALL(Dbg_sec_order_error(ofl->ofl_lml, ifl, ndx, error));
        }

        /* Report success */
        if (isp2_ndx != 0) {
                /*
                 * If the destination section is different than the input
                 * section, then set *alt_os_name to the destination name.
                 */
                if (isp2_ndx != ndx)
                        *alt_os_name = ifl->ifl_isdesc[isp2_ndx]->is_name;
                return (TRUE);
        }

        /* If we get here, there is no valid destination */
        return (FALSE);
}

/*
 * Called when an ordered section has a problem that prevents ordering.
 * The order flag is removed, and then the section is placed as an
 * unsorted section.
 */
static uintptr_t
place_unordered(Ofl_desc *ofl, Is_desc *isp, Place_path_info *path_info)
{
        isp->is_flags &= ~FLG_IS_ORDERED;
        if (isp->is_osdesc == NULL)
                return ((uintptr_t)ld_place_section(ofl, isp, path_info,
                    isp->is_keyident, NULL));
        return ((uintptr_t)isp->is_osdesc);
}

/*
 * Process ordered input section. Called from process_elf() after
 * all the non-ordered sections have been placed.
 *
 * entry:
 *      ofl - Output file descriptor
 *      ifl - Input file descriptor
 *      ndx - Section index of SHF_ORDERED section
 *
 * exit:
 */
uintptr_t
ld_process_ordered(Ofl_desc *ofl, Ifl_desc *ifl, Place_path_info *path_info,
    Word ndx)
{
        Is_desc         *isp2, *isp = ifl->ifl_isdesc[ndx];
        Xword           shflags = isp->is_shdr->sh_flags;
        const char      *alt_os_name = NULL;
        Word            keyshndx;
        Os_desc         *osp;
        int             error = 0;

        /*
         * Obtain the sort key section index for this ordered section.
         * SHF_ORDERED uses sh_info, while SHF_LINK_ORDER uses sh_link.
         * In order for this function to be called, one of SHF_ORDERED
         * or SHF_LINK_ORDER must be set. Testing for one implies the
         * state of the other.
         */
        keyshndx = (shflags & SHF_ORDERED) ?
            isp->is_shdr->sh_info : isp->is_shdr->sh_link;

        /*
         * Validate the sort key section index. If something is wrong,
         * fall back to treating it as a non-ordered section.
         */
        if ((error = is_keyshndx_ok(ifl, keyshndx)) != 0) {
                DBG_CALL(Dbg_sec_order_error(ofl->ofl_lml, ifl, ndx, error));
                return (place_unordered(ofl, isp, path_info));
        }

        /*
         * If SHF_ORDERED is in effect, validate the destination section
         * name given by sh_link, and set alt_os_name to the name of the
         * destination if it differs from the section being processed.
         */
        if ((shflags & SHF_ORDERED) &&
            (validate_shf_ordered_dest(ofl, ifl, ndx, &alt_os_name) == FALSE))
                return (place_unordered(ofl, isp, path_info));

        /*
         * Place the section into its output section. It's possible that this
         * section is discarded (possibly because it's defined COMDAT), in
         * which case we're done.
         */
        if ((osp = isp->is_osdesc) == NULL) {
                osp = ld_place_section(ofl, isp, path_info, isp->is_keyident,
                    alt_os_name);
                if ((osp == (Os_desc *)S_ERROR) || (osp == NULL))
                        return ((uintptr_t)osp);
        }

        /*
         * If the output section is not yet on the ordered list, place it on
         * the list.
         */
        if (aplist_test(&ofl->ofl_ordered, osp, AL_CNT_OFL_ORDERED) ==
            ALE_ALLOCFAIL)
                return ((uintptr_t)S_ERROR);

        /*
         * Output section has been found - set up its sorting information.
         */
        if ((keyshndx != SHN_BEFORE) && (keyshndx != SHN_AFTER)) {
                Os_desc         *osp2;

                isp2 = ifl->ifl_isdesc[keyshndx];
                if (isp2->is_flags & FLG_IS_DISCARD) {
                        ld_eprintf(ofl, ERR_FATAL, MSG_INTL(MSG_FIL_BADORDREF),
                            ifl->ifl_name, EC_WORD(isp->is_scnndx),
                            isp->is_name, EC_WORD(isp2->is_scnndx),
                            isp2->is_name);
                        return (S_ERROR);
                }

                /*
                 * Indicate that this ordered input section will require a
                 * sort key.  Propagate the key requirement through to the
                 * associated output section, segment and file, to trigger
                 * the sort key creation.  See ld_sec_validate();
                 */
                isp2->is_flags |= FLG_IS_KEY;

                osp2 = isp2->is_osdesc;
                osp2->os_flags |= FLG_OS_KEY;
                osp2->os_sgdesc->sg_flags |= FLG_SG_KEY;

                ofl->ofl_flags |= FLG_OF_KEY;
        }

        return ((uintptr_t)osp);
}

/*
 * Traverse all segments looking for section ordering information that hasn't
 * been used.  If found give a warning message to the user.  Also, check if
 * there are any ordered key sections, and if so set up sort key values.
 */
void
ld_sec_validate(Ofl_desc *ofl)
{
        Aliste          idx1;
        Sg_desc         *sgp;
        Word            key = 1;

        for (APLIST_TRAVERSE(ofl->ofl_segs, idx1, sgp)) {
                Sec_order       *scop;
                Os_desc         *osp;
                Aliste          idx2;

                for (ALIST_TRAVERSE(sgp->sg_os_order, idx2, scop)) {
                        if ((scop->sco_flags & FLG_SGO_USED) == 0) {
                                ld_eprintf(ofl, ERR_WARNING,
                                    MSG_INTL(MSG_MAP_SECORDER),
                                    sgp->sg_name, scop->sco_secname);
                        }
                }
                if ((sgp->sg_flags & FLG_SG_KEY) == 0)
                        continue;

                for (APLIST_TRAVERSE(sgp->sg_osdescs, idx2, osp)) {
                        Aliste  idx3;
                        Is_desc *isp;

                        if ((osp->os_flags & FLG_OS_KEY) == 0)
                                continue;

                        /*
                         * The input sections used as sort keys are required
                         * to be unordered, so we only have to look at the
                         * DEFAULT list of input sections.
                         */
                        for (APLIST_TRAVERSE(osp->os_isdescs[OS_ISD_DEFAULT],
                            idx3, isp)) {
                                if (isp->is_flags & FLG_IS_KEY)
                                        isp->is_keyident = key++;
                        }
                }
        }
}

static int
comp(const void *ss1, const void *ss2)
{
        Is_desc         *s1 = *((Is_desc **)ss1);
        Is_desc         *s2 = *((Is_desc **)ss2);
        Is_desc         *i1, *i2;
        Word            ndx1, ndx2;

        if (s1->is_shdr->sh_flags & SHF_ORDERED)
                ndx1 = s1->is_shdr->sh_info;
        else
                ndx1 = s1->is_shdr->sh_link;

        if (s2->is_shdr->sh_flags & SHF_ORDERED)
                ndx2 = s2->is_shdr->sh_info;
        else
                ndx2 = s2->is_shdr->sh_link;

        i1 = s1->is_file->ifl_isdesc[ndx1];
        i2 = s2->is_file->ifl_isdesc[ndx2];

        if (i1->is_keyident > i2->is_keyident)
                return (1);
        if (i1->is_keyident < i2->is_keyident)
                return (-1);
        return (0);
}

/*
 * Sort ordered input sections
 */
uintptr_t
ld_sort_ordered(Ofl_desc *ofl)
{
        Aliste  idx1;
        Os_desc *osp;

        DBG_CALL(Dbg_sec_order_list(ofl, 0));

        for (APLIST_TRAVERSE(ofl->ofl_ordered, idx1, osp)) {
                APlist  *ap_list = osp->os_isdescs[OS_ISD_ORDERED];
                Aliste  apl_nitems = aplist_nitems(ap_list);

                /*
                 * If this output section has a non-empty list of ordered
                 * input sections, sort their APlist in place into their
                 * final order.
                 */
                if (apl_nitems != 0)
                        qsort((char *)ap_list->apl_data, apl_nitems,
                            sizeof (Is_desc *), comp);
        }
        DBG_CALL(Dbg_sec_order_list(ofl, 1));
        return (0);
}