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 (c) 1996, 2010, Oracle and/or its affiliates. All rights reserved.
24 */
25
26/*
27 * Processing of SHF_ORDERED sections.
28 */
29#include	<stdio.h>
30#include	<fcntl.h>
31#include	<link.h>
32#include	<debug.h>
33#include	"msg.h"
34#include	"_libld.h"
35
36/*
37 * Section Ordering History/Background:
38 *
39 * There are two forms of section ordering, SHF_ORDERED, and SHF_LINK_ORDER.
40 *
41 * SHF_ORDERED was invented at Sun in order to support the PowerPC port
42 * of Solaris 2.6, which used it for sorting tag words which describe
43 * the state of callee saves registers for given PC ranges. It was defined
44 * in the OS specific ELF section flag range. Some other values were defined
45 * at the same time:
46 *	SHF_EXCLUDE - Section is to be excluded from executables or shared
47 *		objects, and only kept in relocatable object output.
48 *	SHN_BEFORE/SHN_AFTER - Sections are placed before/after all other
49 *		sections, in the order they are encountered by the linker.
50 * Although initially conceived to support the PowerPC, the functionality
51 * was implemented for all platforms, and was later used to manage C++
52 * exceptions and stack unwinding. The PowerPC port was discontinued after
53 * one release, but SHF_ORDERED lives on.
54 *
55 * SHF_LINK_ORDER was invented later by the wider ELF community, and is
56 * therefore assigned a value in the generic ELF section flag range. It is
57 * essentially a simpler version of SHF_ORDERED, dispensing with some
58 * unnecessary features. The Solaris implementation of SHF_LINK_ORDER uses
59 * SHF_EXCLUDE, and SHF_BEFORE/SHN_AFTER as well, but it appears that these
60 * are still Solaris-only extensions not used by other implementations.
61 * SHF_LINK_ORDER has superseded SHF_ORDERED. The older mechanism is
62 * supported for the benefit of old pre-existing objects.
63 *
64 * -----
65 *
66 * SHF_ORDERED offers two distinct and separate abilities:
67 *
68 *	(1) To specify the output section
69 *	(2) To optionally be sorted relative to other sorted sections,
70 *		using a non-sorted section as a sort key.
71 *
72 * To  do this, it uses both the sh_link, and sh_info fields:
73 *
74 *    sh_link
75 *	Specifies the output section to receive this input section.
76 *	The sh_link field of an SHF_ORDERED section forms a linked list of
77 *	sections, all of which must have identical section header flags
78 *	(including SHF_ORDERED). The list is terminated by a final section
79 *	with a sh_link that points at itself. All input sections in this list
80 *	are assigned to the output section of the final section in the list.
81 *	Hence, if a section points at itself, the effect is that it gets
82 *	assigned to an output section in the usual default manner (i.e. an
83 *	output section with the same name as the input). However, it can
84 *	point at any arbitrary other section. This is a way to put a section
85 *	with one name into an output section with a different name. It should
86 *	be noted that this is of little value overall, because the link-editor
87 *	already supports a more general feature for directing input sections
88 *	to output sections: An input section named .text%foo will be sent to
89 *	an output section named ".text", and this works for all sections,
90 *	not just ordered ones.
91 *
92 *    sh_info
93 *	If sh_info is in the range (1 <= value < shnum), then this input section
94 *	is added to the group of sorted sections. The section referenced by
95 *	sh_info must be unsorted, and is used as the sort key.
96 *
97 *	If sh_info is SHN_BEFORE or SHN_AFTER, it is put in the pre/post group,
98 *	in the order it arrives (the before/after classes are not sorted).
99 *
100 *	If sh_info is "invalid" (typically 0), then this section is added to
101 *	the group of non-sorted sections, and goes into the output file in the
102 *	order it arrives. This is not a valuable feature, as the same effect
103 *	can be achieved more simply by not setting SHF_ORDERED at all.
104 *
105 * SHF_LINK_ORDER is a simplification of SHF_ORDERED. It uses sh_link to specify
106 * the section to use as a sort key and sh_info is set to 0. The standard
107 * ".text%foo" mechanism is used to direct input sections to output sections,
108 * and unordered sections indicate that by not setting SHF_LINK_ORDER.
109 */
110
111
112/*
113 * A "keyshndx" is the section index for the unordered section that should
114 * be used as a sort key for a ordered section. Verify that the given
115 * keyshndx is valid.
116 *
117 * exit:
118 *	Returns 0 if the keyshndx is valid. A non-zero DBG_ORDER_ code is
119 *	returned if the keyshndx is not valid to describe the problem.
120 */
121inline static Word
122is_keyshndx_ok(Ifl_desc *ifl, Word keyshndx)
123{
124	if ((keyshndx == SHN_BEFORE) || (keyshndx == SHN_AFTER))
125		return (0);
126
127	/*
128	 * Validate the key range.
129	 */
130	if ((keyshndx == 0) || (keyshndx >= ifl->ifl_shnum))
131		return (DBG_ORDER_LINK_OUTRANGE);
132
133	/*
134	 * The section pointed to by keyshndx should not be an ordered section.
135	 * Strictly speaking, we could test for SHF_ORDERED here instead of
136	 * ALL_SHF_ORDER as the two ordering flags are not supposed to be
137	 * mixed. Using ALL_SHF_ORDER costs the same and ensures that such
138	 * mixing doesn't go undetected.
139	 */
140	if (ifl->ifl_isdesc[keyshndx]->is_shdr->sh_flags & ALL_SHF_ORDER)
141		return (DBG_ORDER_INFO_ORDER);
142
143	return (0);
144}
145
146/*
147 * The sh_link field of an SHF_ORDERED section forms a linked list of
148 * sections. The list is terminated by a final section with a sh_link
149 * that points at itself. Given the index of an SHF_ORDERED section, find
150 * the index of the final section in the list.
151 *
152 * entry:
153 *	ofl - Output file descriptor
154 *	ifl - Input file descriptor
155 *	ndx - Section index of SHF_ORDERED section
156 *	alt_os_name - Address of pointer to string. If the final section
157 *		name is different than the section given by ndx, *alt_os_name
158 *		will be updated with the name of the final section. The caller
159 *		should initialize *alt_os_name to NULL before calling
160 *		this routine.
161 *
162 * exit:
163 *	On success: If the final section is different than the section
164 *	given by ndx, then *alt_os_name is set to its name. TRUE is returned.
165 *
166 *	On failure, FALSE is returned.
167 */
168static Boolean
169validate_shf_ordered_dest(Ofl_desc *ofl, Ifl_desc *ifl, Word ndx,
170    const char **alt_os_name)
171{
172	Word	shnum = ifl->ifl_shnum;
173	Word	isp1_ndx, isp2_ndx;
174	Is_desc	*isp1, *isp2;
175	int	error = 0;
176	size_t	iter = 0;
177
178	/*
179	 * Traverse the list until we find the termination, or encounter
180	 * an invalid condition in the object that prevents ordering.
181	 */
182	isp1_ndx = ndx;
183	isp1 = ifl->ifl_isdesc[ndx];
184	do {
185		/*
186		 * Obtain index of next section in list. Ensure it is in range.
187		 */
188		isp2_ndx = isp1->is_shdr->sh_link;
189		if ((isp2_ndx == 0) || (isp2_ndx >= shnum)) {
190			error = DBG_ORDER_LINK_OUTRANGE;
191			break;
192		}
193		isp2 = ifl->ifl_isdesc[isp2_ndx];
194
195		/* The section flags must match exactly */
196		if (isp1->is_shdr->sh_flags != isp2->is_shdr->sh_flags) {
197			/*
198			 * The case where the next section in the list does
199			 * not have the same ordered flag set as the original
200			 * ordered section gets a unique error code. This
201			 * provides more accurate/useful debugging diagnostics.
202			 */
203			error = ((isp2->is_flags & FLG_IS_ORDERED) == 0) ?
204			    DBG_ORDER_LINK_ERROR : DBG_ORDER_FLAGS;
205			break;
206		}
207
208		/*
209		 * The sh_info field specifies the section index of an
210		 * unorderd section which will be used as a sort key.
211		 * Ensure it is in range. If not, we terminate the list
212		 * at the current node instead of continuing on.
213		 */
214		if ((error = is_keyshndx_ok(ifl, isp2->is_shdr->sh_info)) != 0)
215			break;
216
217		/* If the section points at itself, it terminates the list */
218		if (isp1_ndx == isp2_ndx)
219			break;
220
221		/*
222		 * Advance to next section in list
223		 */
224		isp1_ndx = isp2_ndx;
225		isp1 = isp2;
226
227		/*
228		 * If we loop more times than the input file has sections,
229		 * we have encountered a malformed object in which the list
230		 * of SHF_ORDERED sections has a cycle. This can only happen
231		 * if the compiler generating the object has a bad bug.
232		 */
233		if (++iter >= shnum) {
234			error = DBG_ORDER_CYCLIC;
235			break;
236		}
237	/* CONSTANTCONDITION */
238	} while (1);
239
240	/*
241	 * If we have found a problem, issue a debug diagnostic and map
242	 * the output section to 0. This indicates that the section should
243	 * remove the ordering flag and treat it as a standard section.
244	 */
245	if (error != 0) {
246		isp2_ndx = 0;
247		DBG_CALL(Dbg_sec_order_error(ofl->ofl_lml, ifl, ndx, error));
248	}
249
250	/* Report success */
251	if (isp2_ndx != 0) {
252		/*
253		 * If the destination section is different than the input
254		 * section, then set *alt_os_name to the destination name.
255		 */
256		if (isp2_ndx != ndx)
257			*alt_os_name = ifl->ifl_isdesc[isp2_ndx]->is_name;
258		return (TRUE);
259	}
260
261	/* If we get here, there is no valid destination */
262	return (FALSE);
263}
264
265/*
266 * Called when an ordered section has a problem that prevents ordering.
267 * The order flag is removed, and then the section is placed as an
268 * unsorted section.
269 */
270static uintptr_t
271place_unordered(Ofl_desc *ofl, Is_desc *isp, Place_path_info *path_info)
272{
273	isp->is_flags &= ~FLG_IS_ORDERED;
274	if (isp->is_osdesc == NULL)
275		return ((uintptr_t)ld_place_section(ofl, isp, path_info,
276		    isp->is_keyident, NULL));
277	return ((uintptr_t)isp->is_osdesc);
278}
279
280/*
281 * Process ordered input section. Called from process_elf() after
282 * all the non-ordered sections have been placed.
283 *
284 * entry:
285 *	ofl - Output file descriptor
286 *	ifl - Input file descriptor
287 *	ndx - Section index of SHF_ORDERED section
288 *
289 * exit:
290 */
291uintptr_t
292ld_process_ordered(Ofl_desc *ofl, Ifl_desc *ifl, Place_path_info *path_info,
293    Word ndx)
294{
295	Is_desc		*isp2, *isp = ifl->ifl_isdesc[ndx];
296	Xword		shflags = isp->is_shdr->sh_flags;
297	const char	*alt_os_name = NULL;
298	Word		keyshndx;
299	Os_desc		*osp;
300	int		error = 0;
301
302	/*
303	 * Obtain the sort key section index for this ordered section.
304	 * SHF_ORDERED uses sh_info, while SHF_LINK_ORDER uses sh_link.
305	 * In order for this function to be called, one of SHF_ORDERED
306	 * or SHF_LINK_ORDER must be set. Testing for one implies the
307	 * state of the other.
308	 */
309	keyshndx = (shflags & SHF_ORDERED) ?
310	    isp->is_shdr->sh_info : isp->is_shdr->sh_link;
311
312	/*
313	 * Validate the sort key section index. If something is wrong,
314	 * fall back to treating it as a non-ordered section.
315	 */
316	if ((error = is_keyshndx_ok(ifl, keyshndx)) != 0) {
317		DBG_CALL(Dbg_sec_order_error(ofl->ofl_lml, ifl, ndx, error));
318		return (place_unordered(ofl, isp, path_info));
319	}
320
321	/*
322	 * If SHF_ORDERED is in effect, validate the destination section
323	 * name given by sh_link, and set alt_os_name to the name of the
324	 * destination if it differs from the section being processed.
325	 */
326	if ((shflags & SHF_ORDERED) &&
327	    (validate_shf_ordered_dest(ofl, ifl, ndx, &alt_os_name) == FALSE))
328		return (place_unordered(ofl, isp, path_info));
329
330	/*
331	 * Place the section into its output section. It's possible that this
332	 * section is discarded (possibly because it's defined COMDAT), in
333	 * which case we're done.
334	 */
335	if ((osp = isp->is_osdesc) == NULL) {
336		osp = ld_place_section(ofl, isp, path_info, isp->is_keyident,
337		    alt_os_name);
338		if ((osp == (Os_desc *)S_ERROR) || (osp == NULL))
339			return ((uintptr_t)osp);
340	}
341
342	/*
343	 * If the output section is not yet on the ordered list, place it on
344	 * the list.
345	 */
346	if (aplist_test(&ofl->ofl_ordered, osp, AL_CNT_OFL_ORDERED) ==
347	    ALE_ALLOCFAIL)
348		return ((uintptr_t)S_ERROR);
349
350	/*
351	 * Output section has been found - set up its sorting information.
352	 */
353	if ((keyshndx != SHN_BEFORE) && (keyshndx != SHN_AFTER)) {
354		Os_desc		*osp2;
355
356		isp2 = ifl->ifl_isdesc[keyshndx];
357		if (isp2->is_flags & FLG_IS_DISCARD) {
358			ld_eprintf(ofl, ERR_FATAL, MSG_INTL(MSG_FIL_BADORDREF),
359			    ifl->ifl_name, EC_WORD(isp->is_scnndx),
360			    isp->is_name, EC_WORD(isp2->is_scnndx),
361			    isp2->is_name);
362			return (S_ERROR);
363		}
364
365		/*
366		 * Indicate that this ordered input section will require a
367		 * sort key.  Propagate the key requirement through to the
368		 * associated output section, segment and file, to trigger
369		 * the sort key creation.  See ld_sec_validate();
370		 */
371		isp2->is_flags |= FLG_IS_KEY;
372
373		osp2 = isp2->is_osdesc;
374		osp2->os_flags |= FLG_OS_KEY;
375		osp2->os_sgdesc->sg_flags |= FLG_SG_KEY;
376
377		ofl->ofl_flags |= FLG_OF_KEY;
378	}
379
380	return ((uintptr_t)osp);
381}
382
383/*
384 * Traverse all segments looking for section ordering information that hasn't
385 * been used.  If found give a warning message to the user.  Also, check if
386 * there are any ordered key sections, and if so set up sort key values.
387 */
388void
389ld_sec_validate(Ofl_desc *ofl)
390{
391	Aliste		idx1;
392	Sg_desc		*sgp;
393	Word 		key = 1;
394
395	for (APLIST_TRAVERSE(ofl->ofl_segs, idx1, sgp)) {
396		Sec_order	*scop;
397		Os_desc		*osp;
398		Aliste		idx2;
399
400		for (ALIST_TRAVERSE(sgp->sg_os_order, idx2, scop)) {
401			if ((scop->sco_flags & FLG_SGO_USED) == 0) {
402				ld_eprintf(ofl, ERR_WARNING,
403				    MSG_INTL(MSG_MAP_SECORDER),
404				    sgp->sg_name, scop->sco_secname);
405			}
406		}
407		if ((sgp->sg_flags & FLG_SG_KEY) == 0)
408			continue;
409
410		for (APLIST_TRAVERSE(sgp->sg_osdescs, idx2, osp)) {
411			Aliste	idx3;
412			Is_desc	*isp;
413
414			if ((osp->os_flags & FLG_OS_KEY) == 0)
415				continue;
416
417			/*
418			 * The input sections used as sort keys are required
419			 * to be unordered, so we only have to look at the
420			 * DEFAULT list of input sections.
421			 */
422			for (APLIST_TRAVERSE(osp->os_isdescs[OS_ISD_DEFAULT],
423			    idx3, isp)) {
424				if (isp->is_flags & FLG_IS_KEY)
425					isp->is_keyident = key++;
426			}
427		}
428	}
429}
430
431static int
432comp(const void *ss1, const void *ss2)
433{
434	Is_desc		*s1 = *((Is_desc **)ss1);
435	Is_desc		*s2 = *((Is_desc **)ss2);
436	Is_desc		*i1, *i2;
437	Word		ndx1, ndx2;
438
439	if (s1->is_shdr->sh_flags & SHF_ORDERED)
440		ndx1 = s1->is_shdr->sh_info;
441	else
442		ndx1 = s1->is_shdr->sh_link;
443
444	if (s2->is_shdr->sh_flags & SHF_ORDERED)
445		ndx2 = s2->is_shdr->sh_info;
446	else
447		ndx2 = s2->is_shdr->sh_link;
448
449	i1 = s1->is_file->ifl_isdesc[ndx1];
450	i2 = s2->is_file->ifl_isdesc[ndx2];
451
452	if (i1->is_keyident > i2->is_keyident)
453		return (1);
454	if (i1->is_keyident < i2->is_keyident)
455		return (-1);
456	return (0);
457}
458
459/*
460 * Sort ordered input sections
461 */
462uintptr_t
463ld_sort_ordered(Ofl_desc *ofl)
464{
465	Aliste	idx1;
466	Os_desc *osp;
467
468	DBG_CALL(Dbg_sec_order_list(ofl, 0));
469
470	for (APLIST_TRAVERSE(ofl->ofl_ordered, idx1, osp)) {
471		APlist	*ap_list = osp->os_isdescs[OS_ISD_ORDERED];
472		Aliste	apl_nitems = aplist_nitems(ap_list);
473
474		/*
475		 * If this output section has a non-empty list of ordered
476		 * input sections, sort their APlist in place into their
477		 * final order.
478		 */
479		if (apl_nitems != 0)
480			qsort((char *)ap_list->apl_data, apl_nitems,
481			    sizeof (Is_desc *), comp);
482	}
483	DBG_CALL(Dbg_sec_order_list(ofl, 1));
484	return (0);
485}
486