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

[Gary Benson]

Tom Tromey wrote:
> >>>>> "Gary" == Gary Benson <gbenson@redhat.com> writes:
> 
> Gary> This series alters solib-svr4's target_so_ops->current_sos
> Gary> to retain a pointer to each copy solib it passes to
> Gary> update_solib_list.  The copies are "acquired" before being
> Gary> passed to update_solib_list, and copies that update_solib_list
> Gary> frees are not freed but released back to solib-svr4's
> Gary> target_so_ops->current_sos for reuse.  Copies that are not
> Gary> released become the responsibility of update_solib_list (and
> Gary> GDB as a whole) and solib-svr4's target_so_ops->current_sos
> Gary> discards its pointers to them, creating a fresh copy the next
> Gary> time around.  This means solibs read by the probes-based
> Gary> interface are copied at most twice.
> 
> I'm having a bit of trouble wrapping my head around this patch.
> I wonder why any copying at all is needed.
> 
> My current understanding is that the problem is a combination of
> (1) lack of reference counting for so_list, and (2) the fact that
> the current_sos method returns a linked list, and so returning an
> so already in use is impossible, since it already has a 'next' field
> that must be preserved.
> 
> (1) could perhaps be fixed with a reference count biased by 1 (that
> is, the number of references == 1 + solib->refc).  That way, all the
> targets that use zalloc to allocate would do the right thing without
> change.
> 
> (2) could be fixed by using a VEC; either invasively by changing
> all the solib implementations, or less so by adding a new
> current_sos_vec that is used in preference if it is not NULL.
> Then solib-svr4 would implement this new method.
> 
> I feel as though I am missing something, though.

Don't worry, I do too :(

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

The current API is that target_so_ops->current_sos creates a list
which is returned to update_solib_list--and that list becomes
update_solib_list's responsibility.  update_solib_list maintains
its own list of what it thinks is loaded.  It does a pass over
both lists; if update_solib_list's internal list is LAST and the
list from target_so_ops->current_sos is THIS, it does:

  a) free anything in LAST that's not in THIS
  b) free anything in THIS that is in LAST

So then you have LAST (libraries that were loaded that still are)
and THIS (newly loaded libraries).  Finally it hooks the first
element of THIS into the last element of LAST, and now LAST is
up to date.

This is a fairly good fit with most of the backends:

  solib-darwin.c
  solib-dsbt.c
  solib-frv.c
  solib-irix.c
  solib-osf.c
  solib-pa64.c
  solib-som.c
  solib-sunos.c
  solib-svr4.c (without probes)

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

Backends that don't do this are:

  solib-aix.c
  solib-target.c
    (With these two some internal function creates a VEC, that
    gets converted into a list (with, in the case of solib-aix.c,
    some entries skipped)).

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

  solib-spu.c
    (This one defers to svr4_so_ops->current_sos() and then adds
    some extra entries to the end of the list.)

It's difficult to see how to make an API which doesn't add work to
some or all of the targets.  Creating a VEC to return means copying
a load of pointers, which is still quadratic although of course less
work than deep copying a whole list.  The OO way would probably be
to use some kind of iterator, but that then adds a ton of function
calls on every update.

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

Gary

--
http://gbenson.net/