Bug 266608 – AX: Move objectsForIds off of the main thread

• Status: RESOLVED
• Resolution: FIXED
• Component: Accessibility

[Joshua Hoffman]

We have to go to the main thread for AXIsolatedTree::objectsForIds when an object (typically a target/origin of a relation) is ignored. These objects should be cached to be served on the main thread.

[Radar WebKit Bug Importer]

<rdar://problem/119837270>

[Joshua Hoffman]

rdar://116133586

[Joshua Hoffman]

Created attachment 469121 [details]
Patch

[Tyler Wilcock]

Comment on attachment 469121 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=469121&action=review

> Source/WebCore/accessibility/AXObjectCache.cpp:4622
> +    auto* relationOrigin = getOrCreate(origin, IsPartOfRelation::Yes);
> +    auto* relationTarget = getOrCreate(target, IsPartOfRelation::Yes);

These should be RefPtrs. getOrCreate calls accessibilityIsIgnored(), which can cause objects to be destroyed as a side effect. We also directly call accessibilityIsIgnored() below.

> Source/WebCore/accessibility/AXObjectCache.cpp:4632
> +#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
> +    if (auto tree = AXIsolatedTree::treeForPageID(m_pageID)) {
> +        if (relationOrigin && relationOrigin->accessibilityIsIgnored())
> +            tree->addUnconnectedNode(*relationOrigin);
> +        if (relationTarget && relationTarget->accessibilityIsIgnored())
> +            tree->addUnconnectedNode(*relationTarget);
> +    }
> +#endif

Something I just realized about addUnconnectedNode: it doesn't check that the object exists before creating a brand new isolated object. That's not great, especially with the addition of this code, as it means we'll create a ton of duplicate copies of the same object over and over. You can imagine an ARIA component that aria-owns 100 children. I think we'd create the same object 100 times?

> Source/WebCore/accessibility/AXObjectCache.cpp:4739
> +#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
> +        // If this element has no more relations, and it is ignored, remove it from
> +        // the isolated tree.
> +        fprintf(stderr, "REmoving relation for %s\n", object->dbg().utf8().data());
> +        auto* relationTarget = objectForID(targetID);
> +        if (!relationTarget || !relationTarget->accessibilityIsIgnored())
> +            continue;
> +
> +        if (!hasNoRelations(targetID))
> +            continue;
> +
> +        if (auto tree = AXIsolatedTree::treeForPageID(m_pageID))
> +            tree->removeNode(*relationTarget);
> +#endif // ENABLE(ACCESSIBILITY_ISOLATED_TREE)

I understand that you've added this to cleanup objects that only exist in the isolated tree because they were added for relations reasons. But I wonder if it's necessary? Unconnected nodes will be cleaned up like normal when they're removed from the DOM / render tree, so not sure it's worth it to do all this work to try to clean them up for an uncommon scenario (an object is ignored, and used to have relations, but then lost them for some reason other than being deleted from the DOM).

What do you think?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:171
> +    for (auto& relatedObjectID : axObjectCache.relations().keys()) {
> +        auto* axObject = axObjectCache.objectForID(relatedObjectID);
> +        if (axObject && axObject->accessibilityIsIgnored()) {
> +            if (!tree->objectForID(relatedObjectID))
> +                tree->addUnconnectedNode(*axObject);
> +        }
> +    }

Is this necessary when we proactively add unconnected nodes if necessary in AXObjectCache::addRelations? Seems like we would need one or the other?

[Joshua Hoffman]

(In reply to Tyler Wilcock from comment #4)
> Comment on attachment 469121 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=469121&action=review
> 
> > Source/WebCore/accessibility/AXObjectCache.cpp:4622
> > +    auto* relationOrigin = getOrCreate(origin, IsPartOfRelation::Yes);
> > +    auto* relationTarget = getOrCreate(target, IsPartOfRelation::Yes);
> 
> These should be RefPtrs. getOrCreate calls accessibilityIsIgnored(), which
> can cause objects to be destroyed as a side effect. We also directly call
> accessibilityIsIgnored() below.

Good point—will update these.

> > Source/WebCore/accessibility/AXObjectCache.cpp:4632
> > +#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
> > +    if (auto tree = AXIsolatedTree::treeForPageID(m_pageID)) {
> > +        if (relationOrigin && relationOrigin->accessibilityIsIgnored())
> > +            tree->addUnconnectedNode(*relationOrigin);
> > +        if (relationTarget && relationTarget->accessibilityIsIgnored())
> > +            tree->addUnconnectedNode(*relationTarget);
> > +    }
> > +#endif
> 
> Something I just realized about addUnconnectedNode: it doesn't check that
> the object exists before creating a brand new isolated object. That's not
> great, especially with the addition of this code, as it means we'll create a
> ton of duplicate copies of the same object over and over. You can imagine an
> ARIA component that aria-owns 100 children. I think we'd create the same
> object 100 times?

Ah yeah, that is true! I'm curious if we don't check that now for a reason? I can easily add a m_readerThreadNodeMap.contains(id) inside addUnconnectedNode. 

> > Source/WebCore/accessibility/AXObjectCache.cpp:4739
> > +#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
> > +        // If this element has no more relations, and it is ignored, remove it from
> > +        // the isolated tree.
> > +        fprintf(stderr, "REmoving relation for %s\n", object->dbg().utf8().data());
> > +        auto* relationTarget = objectForID(targetID);
> > +        if (!relationTarget || !relationTarget->accessibilityIsIgnored())
> > +            continue;
> > +
> > +        if (!hasNoRelations(targetID))
> > +            continue;
> > +
> > +        if (auto tree = AXIsolatedTree::treeForPageID(m_pageID))
> > +            tree->removeNode(*relationTarget);
> > +#endif // ENABLE(ACCESSIBILITY_ISOLATED_TREE)
> 
> I understand that you've added this to cleanup objects that only exist in
> the isolated tree because they were added for relations reasons. But I
> wonder if it's necessary? Unconnected nodes will be cleaned up like normal
> when they're removed from the DOM / render tree, so not sure it's worth it
> to do all this work to try to clean them up for an uncommon scenario (an
> object is ignored, and used to have relations, but then lost them for some
> reason other than being deleted from the DOM).
> 
> What do you think?

My original thought was that if you have an object that is related to many other (ignored) objects, we should clean them up for space efficiency. But that case does seem extremely rare, so I totally get your point.

Your comment also makes me think that not removing the unconnected nodes helps prevent more work in case those relations are re-established. I think the space trade off would be worth it.

> > Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:171
> > +    for (auto& relatedObjectID : axObjectCache.relations().keys()) {
> > +        auto* axObject = axObjectCache.objectForID(relatedObjectID);
> > +        if (axObject && axObject->accessibilityIsIgnored()) {
> > +            if (!tree->objectForID(relatedObjectID))
> > +                tree->addUnconnectedNode(*axObject);
> > +        }
> > +    }
> 
> Is this necessary when we proactively add unconnected nodes if necessary in
> AXObjectCache::addRelations? Seems like we would need one or the other?

In AXObjectCache::addRelation, we have to get the tree using treeForPageID. The code above is executing before the tree is added to the tree cache in AXIsolatedTree::create, so addRelation isn't adding any unconnected nodes since the tree is null. We need this here so that we can add the nodes at initialization, and then for relations that change, AXObjectCache::addRelation will take care of those.

[Tyler Wilcock]

> > > Source/WebCore/accessibility/AXObjectCache.cpp:4632
> > > +#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
> > > +    if (auto tree = AXIsolatedTree::treeForPageID(m_pageID)) {
> > > +        if (relationOrigin && relationOrigin->accessibilityIsIgnored())
> > > +            tree->addUnconnectedNode(*relationOrigin);
> > > +        if (relationTarget && relationTarget->accessibilityIsIgnored())
> > > +            tree->addUnconnectedNode(*relationTarget);
> > > +    }
> > > +#endif
> > 
> > Something I just realized about addUnconnectedNode: it doesn't check that
> > the object exists before creating a brand new isolated object. That's not
> > great, especially with the addition of this code, as it means we'll create a
> > ton of duplicate copies of the same object over and over. You can imagine an
> > ARIA component that aria-owns 100 children. I think we'd create the same
> > object 100 times?
> 
> Ah yeah, that is true! I'm curious if we don't check that now for a reason?
> I can easily add a m_readerThreadNodeMap.contains(id) inside
> addUnconnectedNode.
m_readerThreadNodeMap can only be read / written from the secondary thread (see the comment above its definition) because it's a non-thread safe hashmap. Checking AXIsolatedTree::m_nodeMap should do the trick though. m_nodeMap is intended to provide a representation of the isolated tree on the main-thread (for purposes such as these).
 
> > > Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:171
> > > +    for (auto& relatedObjectID : axObjectCache.relations().keys()) {
> > > +        auto* axObject = axObjectCache.objectForID(relatedObjectID);
> > > +        if (axObject && axObject->accessibilityIsIgnored()) {
> > > +            if (!tree->objectForID(relatedObjectID))
> > > +                tree->addUnconnectedNode(*axObject);
> > > +        }
> > > +    }
> > 
> > Is this necessary when we proactively add unconnected nodes if necessary in
> > AXObjectCache::addRelations? Seems like we would need one or the other?
> 
> In AXObjectCache::addRelation, we have to get the tree using treeForPageID.
> The code above is executing before the tree is added to the tree cache in
> AXIsolatedTree::create, so addRelation isn't adding any unconnected nodes
> since the tree is null. We need this here so that we can add the nodes at
> initialization, and then for relations that change,
> AXObjectCache::addRelation will take care of those.
Ah right, should've noticed this is in AXIsolatedTree::create!

[Joshua Hoffman]

(In reply to Tyler Wilcock from comment #6)
> > > > Source/WebCore/accessibility/AXObjectCache.cpp:4632
> > > > +#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
> > > > +    if (auto tree = AXIsolatedTree::treeForPageID(m_pageID)) {
> > > > +        if (relationOrigin && relationOrigin->accessibilityIsIgnored())
> > > > +            tree->addUnconnectedNode(*relationOrigin);
> > > > +        if (relationTarget && relationTarget->accessibilityIsIgnored())
> > > > +            tree->addUnconnectedNode(*relationTarget);
> > > > +    }
> > > > +#endif
> > > 
> > > Something I just realized about addUnconnectedNode: it doesn't check that
> > > the object exists before creating a brand new isolated object. That's not
> > > great, especially with the addition of this code, as it means we'll create a
> > > ton of duplicate copies of the same object over and over. You can imagine an
> > > ARIA component that aria-owns 100 children. I think we'd create the same
> > > object 100 times?
> > 
> > Ah yeah, that is true! I'm curious if we don't check that now for a reason?
> > I can easily add a m_readerThreadNodeMap.contains(id) inside
> > addUnconnectedNode.
> m_readerThreadNodeMap can only be read / written from the secondary thread
> (see the comment above its definition) because it's a non-thread safe
> hashmap. Checking AXIsolatedTree::m_nodeMap should do the trick though.
> m_nodeMap is intended to provide a representation of the isolated tree on
> the main-thread (for purposes such as these).

Ah yes! I was under the impression, however, that unconnected nodes don't get added to the m_nodeMap (based on this comment in addUnconnectedNode):
// Because we are queuing a change for an object not intended to be connected to the rest of the tree,
// we don't need to update m_nodeMap or m_pendingChildrenUpdates for this object or its parent as is
// done in AXIsolatedTree::nodeChangeForObject and AXIsolatedTree::queueChange.

[Tyler Wilcock]

(In reply to Joshua Hoffman from comment #7)
> (In reply to Tyler Wilcock from comment #6)
> > > > > Source/WebCore/accessibility/AXObjectCache.cpp:4632
> > > > > +#if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
> > > > > +    if (auto tree = AXIsolatedTree::treeForPageID(m_pageID)) {
> > > > > +        if (relationOrigin && relationOrigin->accessibilityIsIgnored())
> > > > > +            tree->addUnconnectedNode(*relationOrigin);
> > > > > +        if (relationTarget && relationTarget->accessibilityIsIgnored())
> > > > > +            tree->addUnconnectedNode(*relationTarget);
> > > > > +    }
> > > > > +#endif
> > > > 
> > > > Something I just realized about addUnconnectedNode: it doesn't check that
> > > > the object exists before creating a brand new isolated object. That's not
> > > > great, especially with the addition of this code, as it means we'll create a
> > > > ton of duplicate copies of the same object over and over. You can imagine an
> > > > ARIA component that aria-owns 100 children. I think we'd create the same
> > > > object 100 times?
> > > 
> > > Ah yeah, that is true! I'm curious if we don't check that now for a reason?
> > > I can easily add a m_readerThreadNodeMap.contains(id) inside
> > > addUnconnectedNode.
> > m_readerThreadNodeMap can only be read / written from the secondary thread
> > (see the comment above its definition) because it's a non-thread safe
> > hashmap. Checking AXIsolatedTree::m_nodeMap should do the trick though.
> > m_nodeMap is intended to provide a representation of the isolated tree on
> > the main-thread (for purposes such as these).
> 
> Ah yes! I was under the impression, however, that unconnected nodes don't
> get added to the m_nodeMap (based on this comment in addUnconnectedNode):
> // Because we are queuing a change for an object not intended to be
> connected to the rest of the tree,
> // we don't need to update m_nodeMap or m_pendingChildrenUpdates for this
> object or its parent as is
> // done in AXIsolatedTree::nodeChangeForObject and
> AXIsolatedTree::queueChange.
Ah yup, that's true. We should investigate if there's any reason why adding these to the node map would cause incorrect behavior, or if the reason it wasn't done was purely for efficiency's sake. If the latter, it's probably more efficient overall to update the node map once, than to not update the node map and create boundless copies of the same object.

[Joshua Hoffman]

Created attachment 469123 [details]
Patch

[Joshua Hoffman]

(In reply to Tyler Wilcock from comment #8)
> (In reply to Joshua Hoffman from comment #7)
> > (In reply to Tyler Wilcock from comment #6)> > 
> > Ah yes! I was under the impression, however, that unconnected nodes don't
> > get added to the m_nodeMap (based on this comment in addUnconnectedNode):
> > // Because we are queuing a change for an object not intended to be
> > connected to the rest of the tree,
> > // we don't need to update m_nodeMap or m_pendingChildrenUpdates for this
> > object or its parent as is
> > // done in AXIsolatedTree::nodeChangeForObject and
> > AXIsolatedTree::queueChange.
> Ah yup, that's true. We should investigate if there's any reason why adding
> these to the node map would cause incorrect behavior, or if the reason it
> wasn't done was purely for efficiency's sake. If the latter, it's probably
> more efficient overall to update the node map once, than to not update the
> node map and create boundless copies of the same object.

Investigated this and this shouldn't cause any issues, and all tests still pass. Adding it in in the latest patch.

[Joshua Hoffman]

Created attachment 469129 [details]
Patch

[Tyler Wilcock]

> > Ah yup, that's true. We should investigate if there's any reason why adding
> > these to the node map would cause incorrect behavior, or if the reason it
> > wasn't done was purely for efficiency's sake. If the latter, it's probably
> > more efficient overall to update the node map once, than to not update the
> > node map and create boundless copies of the same object.
> 
> Investigated this and this shouldn't cause any issues, and all tests still
> pass. Adding it in in the latest patch.
OK I looked into it too, and I'm a bit worried that using the node map here will affect tree updates in an adverse way, as AXIsolatedTree::updateChildren does this:

    auto* axAncestor = Accessibility::findAncestor(axObject, true, [this] (auto& ancestor) {
        return m_nodeMap.find(ancestor.objectID()) != m_nodeMap.end();
    });

The intention is to find the nearest in-live-tree (a.k.a not ignored) ancestor that's also in the node map, and we will be breaking that invariant, which would result in missing content in some cases. We could add an accessibilityIsIgnored check, but this is a hot path and that function is expensive.

[Joshua Hoffman]

(In reply to Tyler Wilcock from comment #12)
> > > Ah yup, that's true. We should investigate if there's any reason why adding
> > > these to the node map would cause incorrect behavior, or if the reason it
> > > wasn't done was purely for efficiency's sake. If the latter, it's probably
> > > more efficient overall to update the node map once, than to not update the
> > > node map and create boundless copies of the same object.
> > 
> > Investigated this and this shouldn't cause any issues, and all tests still
> > pass. Adding it in in the latest patch.
> OK I looked into it too, and I'm a bit worried that using the node map here
> will affect tree updates in an adverse way, as
> AXIsolatedTree::updateChildren does this:
> 
>     auto* axAncestor = Accessibility::findAncestor(axObject, true, [this]
> (auto& ancestor) {
>         return m_nodeMap.find(ancestor.objectID()) != m_nodeMap.end();
>     });
> 
> The intention is to find the nearest in-live-tree (a.k.a not ignored)
> ancestor that's also in the node map, and we will be breaking that
> invariant, which would result in missing content in some cases. We could add
> an accessibilityIsIgnored check, but this is a hot path and that function is
> expensive.

Gotcha, in that case we can just add a m_unconnectedNodes HashSet store/remove IDs from there.

[Joshua Hoffman]

Created attachment 469132 [details]
Patch

[Tyler Wilcock]

Comment on attachment 469132 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=469132&action=review

> Source/WebCore/accessibility/AXObjectCache.cpp:4628
> +            tree->addUnconnectedNode(*relationOrigin);

Since we don't use the RefPtr anymore after this line, we can save ref-count churn by using relationOrigin.releaseNonNull(). Same for relationTarget.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:166
> +        auto* axObject = axObjectCache.objectForID(relatedObjectID);

Sorry for missing this before, but this should probably be a RefPtr too.

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:168
> +            if (!tree->objectForID(relatedObjectID))

We shouldn't call AXIsolatedTree::objectForID on the main-thread (it's basically a thin wrapper over m_readerThreadNodeMap). Can we remove this check entirely now that we have m_unconnectedNodes?

> Source/WebCore/accessibility/isolatedtree/AXIsolatedTree.cpp:1065
> +    if (m_unconnectedNodes.contains(objectID)) {
> +        m_unconnectedNodes.remove(objectID);

You can save one hash operation by using HashMap::remove, which returns a bool indicating whether the value was removed.

[Joshua Hoffman]

Created attachment 469133 [details]
Patch

[Joshua Hoffman]

(In reply to Tyler Wilcock from comment #15)
> Comment on attachment 469132 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=469132&action=review

Addressed all of your comments in the latest patch

[EWS]

Committed 272323@main (e4ad61660d18): <https://commits.webkit.org/272323@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 469133 [details].