Re: Patch to do reorder text and data sections according to a user specified sequence.

[Sriraman Tallam <tmsriram at google dot com>]

Hi,

    I fixed a bug Taras ran into. Here is the new patch.

	* gold.h (is_wildcard_string): New function.
	* layout.cc (Layout::layout): Pass this pointer to add_input_section.
	(Layout::layout_eh_frame): Ditto.
	(Layout::find_section_order_index): New method.
	(Layout::read_layout_from_file): New method.
	* layout.h (Layout::find_section_order_index): New method.
	(Layout::read_layout_from_file): New method.
	(Layout::input_section_position_): New private member.
	(Layout::input_section_glob_): New private member.
	* main.cc (main): Call read_layout_from_file here.
	* options.h (--section-ordering-file): New option.
	* output.cc (Output_section::input_section_order_specified_): New
	member.
	(Output_section::Output_section): Initialize new member.
	(Output_section::add_input_section): Add new parameter.
	Keep input sections when --section-ordering-file is used.
	(Output_section::set_final_data_size): Sort input sections when
	section ordering file is specified.
	(Output_section::Input_section_sort_entry): Add new parameter.
	Check sorting type.
	(Output_section::Input_section_sort_entry::is_before_in_sequence):
	New method.
	(Output_section::Input_section_sort_compare::operator()): Change to
	consider section_order_index.
	(Output_section::Input_section_sort_init_fini_compare::operator()):
	Change to consider section_order_index.
	(Output_section::Input_section_sort_section_order_index_compare
	::operator()): New method.
	(Output_section::sort_attached_input_sections): Change to sort
	according to section order when specified.
	(Output_section::add_input_section<32, true>): Add new parameter.
	(Output_section::add_input_section<64, true>): Add new parameter.
	(Output_section::add_input_section<32, false>): Add new parameter.
	(Output_section::add_input_section<64, false>): Add new parameter.
	* output.h (Output_section::add_input_section): Add new parameter.
	(Output_section::input_section_order_specified): New
	method.
	(Output_section::set_input_section_order_specified): New method.
	(Input_section::Input_section): Initialize section_order_index_.
	(Input_section::section_order_index): New method.
	(Input_section::set_section_order_index): New method.
	(Input_section::section_order_index_): New member.
	(Input_section::Input_section_sort_section_order_index_compare): New
	struct.
	(Output_section::input_section_order_specified_): New member.
	* script-sections.cc (is_wildcard_string): Delete and move modified
	method to gold.h.
	(Output_section_element_input::Output_section_element_input): Modify
	call to is_wildcard_string.
	(Output_section_element_input::Input_section_pattern
	::Input_section_pattern): Ditto.
	(Output_section_element_input::Output_section_element_input): Ditto.
	* testsuite/Makefile.am (final_layout): New test case.
	* testsuite/Makefile.in: Regenerate.
	* testsuite/final_layout.cc: New file.
	* testsuite/final_layout.sh: New file.


Thanks,
-Sri.

On Mon, May 24, 2010 at 12:26 PM, Taras Glek <tglek@mozilla.com> wrote:
> On 05/21/2010 06:41 PM, Sriraman Tallam wrote:
>>
>> Hi Taras,
>>
>> ? ? ?Did you get a chance to test the timings with the new patch ?
>>
>
> I've only tested it briefly on Friday. I'm having some problems with the new
> patch. It ranges from working perfectly to occasionally taking longer than
> the previous one and/or crashing. I'll let you know more once I have more
> time to play with it
>
> Taras
>>
>> Thanks,
>> -Sri.
>>
>> On Thu, May 13, 2010 at 5:58 PM, Sriraman Tallam<tmsriram@google.com>
>> ?wrote:
>>
>>>
>>> Hi Ian and Taras,
>>>
>>> ? ? Sorry for taking this long to get back. I have modified the patch
>>> to address Taras' timing issue. Basically, I split patterns specified
>>> into glob and non-glob by just looking for wild-card characters in the
>>> pattern. Non-glob look-ups are through a hash table and fast. Glob
>>> patterns are be searched linearly. So, if you specify non-glob symbol
>>> names in the section ordering file, the link should be faster than
>>> before.
>>>
>>> ? ? Further, I have prioritized non-glob patters over glob patterns.
>>> Let me explain with an example :
>>>
>>> If object main.o has sections .text._foov, .text._barv, and
>>> .text._zapv and the seection ordering file is :
>>> ===============================
>>> *bar*
>>> .text.*
>>> .text._barv
>>> ===============================
>>>
>>> Then, .text._barv will be the last section in .text even though it
>>> matches the first glob pattern.
>>>
>>>
>>> The changes are :
>>>
>>> ? ? ? ?* gold.h (is_wildcard_string): New function.
>>> ? ? ? ?* layout.cc (Layout::layout): Pass this pointer to
>>> add_input_section.
>>> ? ? ? ?(Layout::layout_eh_frame): Ditto.
>>> ? ? ? ?(Layout::find_section_order_index): New method.
>>> ? ? ? ?(Layout::read_layout_from_file): New method.
>>> ? ? ? ?* layout.h (Layout::find_section_order_index): New method.
>>> ? ? ? ?(Layout::read_layout_from_file): New method.
>>> ? ? ? ?(Layout::input_section_position_): New private member.
>>> ? ? ? ?(Layout::input_section_glob_): New private member.
>>> ? ? ? ?* main.cc (main): Call read_layout_from_file here.
>>> ? ? ? ?* options.h (--section-ordering-file): New option.
>>> ? ? ? ?* output.cc (Output_section::input_section_order_specified_): New
>>> ? ? ? ?member.
>>> ? ? ? ?(Output_section::Output_section): Initialize new member.
>>> ? ? ? ?(Output_section::add_input_section): Add new parameter.
>>> ? ? ? ?Keep input sections when --section-ordering-file is used.
>>> ? ? ? ?(Output_section::set_final_data_size): Sort input sections when
>>> ? ? ? ?section ordering file is specified.
>>> ? ? ? ?(Output_section::Input_section_sort_entry): Add new parameter.
>>> ? ? ? ?Check sorting type.
>>> ? ? ? ?(Output_section::Input_section_sort_entry::is_before_in_sequence):
>>> ? ? ? ?New method.
>>> ? ? ? ?(Output_section::Input_section_sort_compare::operator()): Change
>>> to
>>> ? ? ? ?consider section_order_index.
>>>
>>> ?(Output_section::Input_section_sort_init_fini_compare::operator()):
>>> ? ? ? ?Change to consider section_order_index.
>>> ? ? ? ?(Output_section::Input_section_sort_section_order_index_compare
>>> ? ? ? ?::operator()): New method.
>>> ? ? ? ?(Output_section::sort_attached_input_sections): Change to sort
>>> ? ? ? ?according to section order when specified.
>>> ? ? ? ?(Output_section::add_input_section<32, true>): Add new parameter.
>>> ? ? ? ?(Output_section::add_input_section<64, true>): Add new parameter.
>>> ? ? ? ?(Output_section::add_input_section<32, false>): Add new parameter.
>>> ? ? ? ?(Output_section::add_input_section<64, false>): Add new parameter.
>>> ? ? ? ?* output.h (Output_section::add_input_section): Add new parameter.
>>> ? ? ? ?(Output_section::input_section_order_specified): New
>>> ? ? ? ?method.
>>> ? ? ? ?(Output_section::set_input_section_order_specified): New method.
>>> ? ? ? ?(Input_section::Input_section): Initialize section_order_index_.
>>> ? ? ? ?(Input_section::section_order_index): New method.
>>> ? ? ? ?(Input_section::set_section_order_index): New method.
>>> ? ? ? ?(Input_section::section_order_index_): New member.
>>> ? ? ? ?(Input_section::Input_section_sort_section_order_index_compare):
>>> New
>>> ? ? ? ?struct.
>>> ? ? ? ?(Output_section::input_section_order_specified_): New member.
>>> ? ? ? ?* script-sections.cc (is_wildcard_string): Delete and move
>>> modified
>>> ? ? ? ?method to gold.h.
>>> ? ? ? ?(Output_section_element_input::Output_section_element_input):
>>> Modify
>>> ? ? ? ?call to is_wildcard_string.
>>> ? ? ? ?(Output_section_element_input::Input_section_pattern
>>> ? ? ? ?::Input_section_pattern): Ditto.
>>> ? ? ? ?(Output_section_element_input::Output_section_element_input):
>>> Ditto.
>>> ? ? ? ?* testsuite/Makefile.am (final_layout): New test case.
>>> ? ? ? ?* testsuite/Makefile.in: Regenerate.
>>> ? ? ? ?* testsuite/final_layout.cc: New file.
>>> ? ? ? ?* testsuite/final_layout.sh: New file.
>>>
>>> Please let me know what you think.
>>>
>>> Thanks,
>>> -Sri.
>>>
>>>
>>>
>>> On Tue, Mar 2, 2010 at 7:43 PM, Sriraman Tallam<tmsriram@google.com>
>>> ?wrote:
>>>
>>>>
>>>> Hi Ian,
>>>>
>>>> ? ?I finally got around to making the changes you specified. Please
>>>> take a look when you get a chance.
>>>>
>>>> ? ? ? ?* layout.cc (Layout::read_layout_from_file): New method.
>>>> ? ? ? ?(Layout::layout): Pass this pointer to add_input_section.
>>>> ? ? ? ?(Layout::layout_eh_frame): Ditto.
>>>> ? ? ? ?* layout.h (Layout::read_layout_from_file): New method.
>>>> ? ? ? ?(Layout::input_section_order): New method.
>>>> ? ? ? ?(Layout::input_section_order_): New private member.
>>>> ? ? ? ?* main.cc (main): Call read_layout_from_file here.
>>>> ? ? ? ?* options.h (--section-ordering-file): New option.
>>>> ? ? ? ?* output.cc (Output_section::input_section_order_specified_): New
>>>> ? ? ? ?member.
>>>> ? ? ? ?(Output_section::add_input_section): Add new parameter.
>>>> ? ? ? ?Keep input sections when --section-ordering-file is used.
>>>> ? ? ? ?(Output_section::set_final_data_size): Sort input sections when
>>>> ? ? ? ?section ordering file is specified.
>>>> ? ? ? ?(Output_section::Input_section_sort_entry::section_order_index_):
>>>> New
>>>> ? ? ? ?member.
>>>> ? ? ? ?(Output_section::Input_section_sort_entry::section_order_index):
>>>> New
>>>> ? ? ? ?method.
>>>> ? ? ? ?(Output_section::Input_section_sort_compare::operator()): Change
>>>> to
>>>> ? ? ? ?consider section_order_index.
>>>>
>>>> ?(Output_section::Input_section_sort_init_fini_compare::operator()):
>>>> ? ? ? ?Change to consider section_order_index.
>>>> ? ? ? ?(Output_section::Input_section_sort_section_order_index_compare
>>>> ? ? ? ?::operator()): New method.
>>>> ? ? ? ?(Output_section::sort_attached_input_sections): Change to sort
>>>> ? ? ? ?according to section order when specified.
>>>> ? ? ? ?* output.h (Output_section::input_section_order_specified): New
>>>> ? ? ? ?method.
>>>> ? ? ? ?(Output_section::set_input_section_order_specified): New method.
>>>> ? ? ? ?(Input_section::glob_pattern_number): New method.
>>>> ? ? ? ?(Input_section::set_glob_pattern_number): New method.
>>>> ? ? ? ?(Input_section::glob_pattern_number_): New member.
>>>> ? ? ? ?(Input_section::Input_section_sort_section_order_index_compare):
>>>> New
>>>> ? ? ? ?struct.
>>>> ? ? ? ?(Output_section::input_section_order_specified_): New member.
>>>> ? ? ? ?* testsuite/Makefile.am (final_layout): New test case.
>>>> ? ? ? ?* testsuite/Makefile.in: Regenerate.
>>>> ? ? ? ?* testsuite/final_layout.cc: New file.
>>>> ? ? ? ?* testsuite/final_layout.sh: New file
>>>>
>>>>
>>>> Thanks,
>>>> -Sriraman.
>>>>
>>>>
>>>> On Thu, Feb 11, 2010 at 9:29 PM, Ian Lance Taylor<iant@google.com>
>>>> ?wrote:
>>>>
>>>>>
>>>>> Sriraman Tallam<tmsriram@google.com> ?writes:
>>>>>
>>>>>
>>>>>>
>>>>>> ? ?I have attached a patch to reorder text and data sections in the
>>>>>> linker according to a user specified sequence. I have added a new
>>>>>> option --final-layout to do this. Currently, this could be done using
>>>>>> linker scripts but this patch makes it really easy to do this. Let me
>>>>>> explain using a simple example.
>>>>>>
>>>>>> test.cc
>>>>>>
>>>>>> void foo()
>>>>>> { }
>>>>>>
>>>>>> void bar()
>>>>>> { }
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>> ? return 0;
>>>>>> }
>>>>>>
>>>>>> $ g++ -ffunction-sections test.cc
>>>>>> $ nm -n a.out
>>>>>> ...
>>>>>> 000000000040038c T _Z3foov
>>>>>> 0000000000400392 T _Z3barv
>>>>>> ....
>>>>>>
>>>>>> foo is laid to be before bar. Now, I can change this order as follows.
>>>>>>
>>>>>> $ (echo "_Z3barv"&& ?echo "_Z3foov")> ?sequence.txt
>>>>>> $ g++ -ffunction-sections test.cc -Wl,--final-layout,sequence.txt
>>>>>> $ nm -n a.out
>>>>>> ...
>>>>>> 0000000000400658 T _Z3barv
>>>>>> 000000000040065e T _Z3foov
>>>>>> ...
>>>>>>
>>>>>> The order is changed.
>>>>>>
>>>>>> This can be done for text or data sections.
>>>>>>
>>>>>
>>>>> As I understand it, in linker terms, you are sorting the sections by
>>>>> suffixes. ?When two input sections are in the same output section, and
>>>>> both input sections have suffixes which appear in the file, then the
>>>>> input sections are sorted in the order in which the suffixes appear in
>>>>> the file.
>>>>>
>>>>> I think it would be more natural to sort the input sections by name
>>>>> rather than by suffix. ?Since you don't want to fuss with writing
>>>>> ".text." all the time, suppose we say that we sort the input sections
>>>>> by name, and we match the input section names using glob patterns. ?We
>>>>> already use glob patterns in linker scripts, so that is not a big
>>>>> stretch.
>>>>>
>>>>> Just a few comments on the rest of the patch.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> +// Read the sequence of input sections from the file specified with
>>>>>> +// --final-layout.
>>>>>> +
>>>>>> +bool
>>>>>> +Layout::read_layout_from_file()
>>>>>> +{
>>>>>> + ?const char* filename = parameters->options().final_layout();
>>>>>> + ?char *buf = NULL;
>>>>>> + ?size_t len = 0;
>>>>>> + ?FILE* fp = fopen(filename, "r");
>>>>>> +
>>>>>> + ?if (fp == NULL)
>>>>>> + ? ?{
>>>>>> + ? ? ?gold_error(_("Error opening layout file : %s\n"), filename);
>>>>>> + ? ? ?gold_exit(false);
>>>>>> + ? ?}
>>>>>> +
>>>>>> + ?while (getline(&buf,&len, fp) != -1)
>>>>>> + ? ?{
>>>>>> + ? ? ?buf[strlen(buf) - 1] = 0;
>>>>>> + ? ? ?this->input_section_order_.push_back(std::string(buf));
>>>>>> + ? ?}
>>>>>> +
>>>>>> + ?if (buf != NULL)
>>>>>> + ? ?free(buf);
>>>>>> +
>>>>>> + ?fclose(fp);
>>>>>> + ?return true;
>>>>>> +}
>>>>>>
>>>>>
>>>>> The getline function is insufficient portable for use in gold. ?Search
>>>>> for std::getline in options.cc for an alternate approach you can use.
>>>>> Emulate the error message style you see there too--no capital letter,
>>>>> name the file, no space before colon, no \n. ?And if you really want
>>>>> to exit on failure, call gold_fatal.
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> +// If --final-layout option is used, reorder the input sections in
>>>>>> +// .text, .data, .bss and .rodata according to the specified
>>>>>> sequence.
>>>>>> +
>>>>>> +void
>>>>>> +Layout::section_reorder()
>>>>>> +{
>>>>>> + ?this->read_layout_from_file();
>>>>>> +
>>>>>> + ?for (Section_list::iterator p = this->section_list_.begin();
>>>>>> + ? ? ? p != this->section_list_.end();
>>>>>> + ? ? ? ++p)
>>>>>> + ? ?{
>>>>>> + ? ? ?if (strcmp(".text", (*p)->name()) == 0
>>>>>> + ? ? ? ? ?|| strcmp(".data", (*p)->name()) == 0
>>>>>> + ? ? ? ? ?|| strcmp(".bss", (*p)->name()) == 0
>>>>>> + ? ? ? ? ?|| strcmp(".rodata", (*p)->name()) == 0)
>>>>>> + ? ? ? ?(*p)->reorder_layout(this);
>>>>>> + ? ?}
>>>>>> +}
>>>>>>
>>>>>
>>>>> Why restrict this to those output sections? ?Why not sort input
>>>>> sections in any output section?
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> + ?DEFINE_string(final_layout, options::TWO_DASHES, '\0', NULL,
>>>>>> + ? ? ? ? ? ? N_("Layout functions and data in the order specified."),
>>>>>> + ? ? ? ? ? ? N_("FILENAME"));
>>>>>>
>>>>>
>>>>> I'm not sure I care for --final-layout as the option name. ?Perhaps
>>>>> --section-ordering-file? ?Perhaps somebody else has a better idea.
>>>>>
>>>>>
>>>>>
>>>>>>
>>>>>> + ?// the future, we keep track of the sections. ?If the
>>>>>> --final-layout
>>>>>> + ?// option is used to specify the order of sections, we need to keep
>>>>>> + ?// track of sections.
>>>>>> ? ?if (have_sections_script
>>>>>> ? ? ? ?|| !this->input_sections_.empty()
>>>>>> ? ? ? ?|| this->may_sort_attached_input_sections()
>>>>>> ? ? ? ?|| this->must_sort_attached_input_sections()
>>>>>> ? ? ? ?|| parameters->options().user_set_Map()
>>>>>> - ? ? ?|| parameters->target().may_relax())
>>>>>> - ? ?this->input_sections_.push_back(Input_section(object, shndx,
>>>>>> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? shdr.get_sh_size(),
>>>>>> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? addralign));
>>>>>> + ? ? ?|| parameters->target().may_relax()
>>>>>> + ? ? ?|| parameters->options().final_layout())
>>>>>> + ? ?{
>>>>>> + ? ? ?Input_section isecn(object, shndx, shdr.get_sh_size(),
>>>>>> addralign);
>>>>>> + ? ? ?isecn.set_section_name(secname);
>>>>>> + ? ? ?this->input_sections_.push_back(isecn);
>>>>>> + ? ?}
>>>>>>
>>>>>
>>>>> Don't save the string here, that's just going to bloat memory usage.
>>>>> Instead, when you read the file, give each line a number. ?Then match
>>>>> the section name which you have here against the list of patterns. ?If
>>>>> you find a match, store the number in the Input_section structure.
>>>>> Also, if you find a match, set a flag in the output section. ?Then
>>>>> sort the sections, by number, in a function called from
>>>>> set_final_data_size.
>>>>>
>>>>> You will see that there is already some section ordering in that
>>>>> function, which is used to implement constructor/destructor priority
>>>>> ordering. ?I guess the priority ordering should take precedence.
>>>>> Maybe.
>>>>>
>>>>> Ian
>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>
>

Attachment: final_layout_patch.txt
Description: Text document