On Mon 6, May 2019 at 00:16:57, Nathanael Rensen wrote:
> On Sun, 5 May 2019 at 06:41, Martin Pieuchot <[email protected]> wrote:
[snip]
> > Do I understand correctly that you're not recursing if not object is
> > inserted?
>
> Yes.
>
> You have probably also noticed that using a single recurse flag is not
> optimally efficient. It is only necessary to recurse child nodes where
> n->data->grpsym_gen != _dl_grpsym_gen
> With my approach if any child node satisfies that then all child nodes
> are recursed.
[snip]
> What do you think about the approach below?
>
> static void
> _dl_insert_grpsym(elf_object_t *object)
> {
> struct dep_node *n;
>
> n = _dl_malloc(sizeof *n);
> if (n == NULL)
> _dl_oom();
> n->data = object;
> TAILQ_INSERT_TAIL(&_dl_loading_object->grpsym_list, n, next_sib);
> }
>
> void
> _dl_link_grpsym(elf_object_t *object)
> {
> struct dep_node *n;
>
> TAILQ_FOREACH(n, &_dl_loading_object->grpsym_list, next_sib)
> if (n->data == object && object->grpsym_gen == _dl_grpsym_gen)
> return; /* found, dont bother adding */
>
> _dl_insert_grpsym(object);
> object->grpsym_gen = _dl_grpsym_gen;
> }
>
> void
> _dl_cache_grpsym_list(elf_object_t *object)
> {
> struct dep_node *n;
>
> /*
> * grpsym_list is an ordered list of all child libs of the
> * _dl_loading_object with no dups. The order is equivalent
> * to a breadth-first traversal of the child list without dups.
> */
>
> TAILQ_FOREACH(n, &object->child_list, next_sib)
> if (n->data->grpsym_gen != _dl_grpsym_gen)
> _dl_insert_grpsym(n->data);
>
> TAILQ_FOREACH(n, &object->child_list, next_sib)
> if (n->data->grpsym_gen != _dl_grpsym_gen) {
> object->grpsym_gen = _dl_grpsym_gen;
> _dl_cache_grpsym_list(n->data);
> }
> }
For the record, the approach above is wrong. It is essential that
object->grpsym_gen is updated by _dl_insert_grpsym() otherwise a tree
such as that below would result in z being added to grpsym_list twice:
x -> y,z
y -> z
While processing x both children y and z are inserted without updating
grpsym_gen. Then while recursing into y, z is added a second time.
This can be fixed using a status flag as follows:
static void
_dl_insert_grpsym(elf_object_t *object)
{
struct dep_node *n;
object->grpsym_gen = _dl_grpsym_gen;
n = _dl_malloc(sizeof *n);
if (n == NULL)
_dl_oom();
n->data = object;
TAILQ_INSERT_TAIL(&_dl_loading_object->grpsym_list, n, next_sib);
}
void
_dl_link_grpsym(elf_object_t *object)
{
struct dep_node *n;
TAILQ_FOREACH(n, &_dl_loading_object->grpsym_list, next_sib)
if (n->data == object && object->grpsym_gen == _dl_grpsym_gen)
return; /* found, dont bother adding */
_dl_insert_grpsym(object);
}
void
_dl_cache_grpsym_list(elf_object_t *object)
{
struct dep_node *n;
/*
* grpsym_list is an ordered list of all child libs of the
* _dl_loading_object with no dups. The order is equivalent
* to a breadth-first traversal of the child list without dups.
*/
TAILQ_FOREACH(n, &object->child_list, next_sib)
if (n->data->grpsym_gen != _dl_grpsym_gen) {
n->data->status |= STAT_GS_RECURSE;
_dl_insert_grpsym(n->data);
}
TAILQ_FOREACH(n, &object->child_list, next_sib)
if (n->data->status & STAT_GS_RECURSE) {
n->data->status &= ~STAT_GS_RECURSE;
_dl_cache_grpsym_list(n->data);
}
}
This approach maintains the integrity of the grpsym_gen mechanism ensuring
a node will not be added to the grpsym_list multiple times. The
STAT_GS_RECURSE flag is used to record the requirement to recurse for
those nodes added on this iteration. This extends the per-iteration
recurse flag of the original diff to a per-child flag without damaging
the integrity of the grpsym_gen mechanism.
For the example tree above, while processing x both y and z are inserted
and STAT_GS_RECURSE is set on both. Then when recursing y, z is not
inserted again because grpsym_gen has already been updated.
The flaw described above is not present in the original part 1 diff, only
in the variation I proposed in response to mpi@'s questions.
Nathanael
