[PATCH] [POWERPC] Optimize counting distinct entries in the relocation sections

[Medve Emilian]

Hello Paul,


> 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
== 0.

> 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
get_plt_size().


Thanks for your time and patience,
Emil.