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

[Taras Glek]

On 03/08/2010 10:55 AM, Sriraman Tallam wrote:
> On Sat, Mar 6, 2010 at 1:53 PM, Sriraman Tallam<tmsriram@google.com>  wrote:
>    
>> Hi Taras,
>>
>> On Fri, Mar 5, 2010 at 3:11 PM, Taras Glek<tglek@mozilla.com>  wrote:
>>      
>>> On 03/02/2010 06:43 PM, Sriraman Tallam wrote:
>>>        
>>>> Hi Ian,
>>>>
>>>>      I finally got around to making the changes you specified. Please
>>>> take a look when you get a chance.
>>>>          
>>> Hi Sriraman,
>>> Ian pointed me at your patch when he realized I was trying to do the same
>>> thing with linker scripts. This is a big improvement over hacking linker
>>> scripts in terms of usability.
>>>
>>> I had two issues with the patch:
>>> a) It would be nice to specify the sections by symbol names alone. So
>>> instead of bss.globalvar one could say "globalvar". Ian pointed out that I
>>> solve this with a *.globalvar regexp since you use fnmatch(). Which lead me
>>> to my next problem.
>>> b) This patch appears to have N^2 behavior since you are doing fnmatch()
>>> through the entire input_section_order list.
>>>
>>> My link time for a large mozilla binary went from under 3s to over 10minutes
>>> when I specified the order(24K entries).
>>>        
>> This was the thing that bothered me a lot when I was writing this
>> patch. I just did not think somebody would face it this soon. I was
>> thinking about how I could incorporate some kind of binary search.
>>
>>      
>>> I think adding a second argument to -section-ordering-file could help. The
>>> second argument could be -section-ordering-match=<symbol|section|regexp>
>>> where symbol/section could use a more efficient search.
>>>        
>> Maybe for symbol and section, I could provide a binary search option
>> if you could pass the symbol and section names in sorted order. That
>> would bring it down to NlogN. Did you have anything else in mind ?
>>      
> I do not know what I was drinking when I wrote this as this does not
> make much sense.  You obviously cannot sort the section names in the
> input file as the order is fixed. However, I thought about this a
> little bit more. If you can provide the integer index of the position
> next to the symbol name in the input file then you can sort the names
> in the input file. A binary search is then possible. Thoughts ?
>    
That sounds like a pretty severe hack. You can just use an stl 
map<filename, position in order file> instead of the vector to achieve a 
similar effect.
  Seems like matching symbols enmass should be a relatively common 
problem. Perhaps Ian can suggest the best way to do such an operation 
efficiently?

An easy solution for me would be to get rid of wildcards in the input 
file and instead of do partial matches based on the ending of the 
string. Ie sort the section-ordering-file back-to-front(like you 
suggested in another email), then you could match ".text.main" and 
"main" equally effectively. I think nlogn behavior is ok for now.


Taras