[PATCH] [POWERPC] Optimize counting distinct entries in the relocation sections
Emilian.Medve at freescale.com
Tue Nov 13 03:50:45 EST 2007
> Actually I notice that count_relocs is counting all relocs, not just
> the R_PPC_REL24 ones, which are all that we actually care about in
> sizing the PLT. And I would be willing to bet that every single
> R_PPC_REL24 reloc has r_addend == 0.
I'll count only the R_PPC_REL24 and I'll validate if they have r_addend
> Also I notice that even with your patch, the actual process of doing
> the relocations will take time proportional to the product of the
> number of PLT entries times the number of R_PPC_REL24 relocations,
> since we do a linear search through the PLT entries each time.
The reason I started working on this patch was because the kernel
detected a soft lockup in count_relocs(). It didn't complain about other
parts so I did nothing about them.
> So, two approaches suggest themselves. Both optimize the r_addend=0
> case and fall back to something like the current code if r_addend is
> not zero. The first is to use the st_other field in the symbol to
> record whether we have seen a R_PPC_REL24 reloc referring to the
> symbol with r_addend=0. That would make count_relocs of complexity
> O(N) for N relocs.
Will look into it.
> The second is to allocate an array with 1 pointer per symbol that
> points to the PLT entry (if any) for the symbol. The count_relocs
> scan can then use that array to store a 'seen before' flag to make its
> scan O(N), and do_plt_call can then later use the same array to find
> PLT entries without needing the linear scan.
This uses extra memory (which could be 'significant' for small boards)
and I was trying to avoid that.
> As far as your proposed patch is concerned, I don't like having a
> function called "count_relocs" changing the array of relocations. At
> the very least it needs a different name. But I also think we can do
> better than O(N * log N), as I have explained above, if my assertion
> that r_addend=0 in all the cases we care about is correct.
The array of relocations is not changed in count_relocs() but in
Thanks for your time and patience,
More information about the Linuxppc-dev