[RFA 0/14] Remove quadratic behaviour from probes linker interface

[Tom Tromey]

>>>>> "Gary" == Gary Benson <gbenson@redhat.com> writes:

Gary> I think the issue is the API itself.  It makes sense for *most*
Gary> targets (or, at least, it's not too awful) but for some targets
Gary> it's not what they want to do.

I think we can either change it, or, if that is too hard, add a second
optional API just for solib-svr4.c.

Gary> These all walk some data structure in the inferior using
Gary> target_read_memory or similar, building a list as they go.
Gary> This list gets passed to update_solib_list, which frees or
Gary> takes the entries as it sees fit.

Gary>   solib-ia64-hpux.c
Gary>   solib-svr4.c (with probes)
Gary>     (These two maintain an internal list, which is copied for
Gary>     returning to update_solib_list.)

Gary> It's difficult to see how to make an API which doesn't add work to
Gary> some or all of the targets.  Creating a VEC to return means copying
Gary> a load of pointers, which is still quadratic although of course less
Gary> work than deep copying a whole list.

It seems that in the probe case we know we can get an incremental list
of updates from the inferior.  But, the internal API doesn't let us
transfer this knowledge from solib-svr4.c to solib.c.

If that's correct, then it is just a self-induced problem that we can
fix by a better internal API.  For example, couldn't we add a method to
target_so_ops like:

    void (*changes) (VEC (solist_ptr) *new_sos,
                     VEC (solist_ptr) *removed_sos);

... and then change update_solib_list to call this method if it exists?

Maybe I'm still missing something here.


Also it seems like the quadratic behavior in update_solib_list can be
solved by introducing a new data structure locally, to avoid nested
walks of the linked lists.  E.g., if target_so_ops also had a "hash"
method (needed since there is the "same" method), we could make a hash
table storing the so_list objects.

This behavior would still be an issue (more minor I think) even in the
probe case if we could notice the deletion of more than one so_list in a
single update.  I'm not sure if that is possible.

Gary> There is the added complexity that adding dlmopen support to
Gary> solib-svr4.c will likely change what happens in there.  I hadn't
Gary> really considered that until right now, but it may be that trying
Gary> to optimize the API or create a new one that's better for probes
Gary> would end up creating something that's not suitable for that.

Either way is fine.  We can always revamp later, especially since
dlmopen still seems a ways off.

Tom