Open Bug 1794974 Opened 2 years ago Updated 9 months ago

[CTW] Runtime adjustment of requested cache domains

Categories

(Core :: Disability Access APIs, enhancement)

Product:
Core
Component:
Disability Access APIs
Type:
enhancement

Tracking

()

People

(Reporter: Jamie, Unassigned)

References

Details

Not every client needs all the information we cache. Screen readers tend to need almost everything, but we know we have millions of non-screen reader clients. As an example, enterprise SSO tools, IMEs for East Asian languages, etc. probably only need role and states. Voice control probably cares about name, role and actions, but not much else.
To improve performance for these clients, we're eventually going to want a way to only cache a subset of info from content a11y trees.

Our CacheDomain concept provides the foundation for this. Broadly, we're going to need to do the following:

  1. We should have a static variable somewhere which specifies the cache domains currently required.
  2. Instead of using CacheDomain::All when sending the cache for new Accessibles, this should be a function which retrieves the static variable (1).
  3. We'll need a new parent -> content IPDL method (perhaps in PContent?) which is called to add additional cache domains that are now required. In the content process, that method will need to update the static variable (1), then walk all documents and all Accessibles, sending a cache update with the newly requested domains.
  4. (3) only works for existing content processes. For new content processes, PContent::ActivateA11y should take an extra parameter specifying the currently requested cache domains. This parameter will be supplied when the parent process requests a11y in the new content process.
  5. There should be a new method in the parent process to request additional cache domains. This method will update the static variable (1) and send the IPDL message (3) to all content processes requesting the new domains.
  6. RemoteAccessibleBase methods should be updated so that if they're called and the required domain is not being requested, they fail and call the method (5) to request the required domain. For example, if RemoteAccessible::BoundsWithOffset is called but CacheDomain::Bounds is not one of the domains we're requesting (2), it should call the method (5) to request CacheDomain::Bounds.
  7. We should decide on a minimum set of cache domains to request and initialise the static variable in the parent process (1) accordingly.
  8. For clients we know about and detect (e.g. NVDA, JAWS, VoiceOver), we may wish to automatically request a larger set of cache domains, rather than having client calls fail (6).
  9. We may need to reorganise cache domains a little for optimal results. For example, some clients might want text but not text attributes, but these are currently both part of CacheDomain::Text.

I'm really hoping we won't need to do this before we ship, but I wanted to make sure I documented my thinking here regardless.

Noting this here so we don't end up trying to figure this out again:
It's possible for a11y to be initialised in content but not parent; see bug 1310833, bug 1312816 and this code. This is not something we really support and should never happen in the real world. (After bug 1312816, this shouldn't even happen in testing.) I don't think we should bother supporting this here.

  • We will enable all cache domains by default when XPCOM a11y is initialised.
    • Our tests expect everything to be available. Updating them all to request different cache domains seems like wasteful work. Also, a11y gets enabled by the platform on some systems, which will mess up the test expectations across different systems.
    • We can then have specific tests which adjust the requested domains to test the switching behaviour.
  • The text string of text leaf Accessibles is currently part of the Text domain. However, the text is actually the Name of text leaf Accessibles and Name is one of the basic things that should probably always be enabled. We will probably need to move the text (but not the attributes, line boundaries, etc.) into NameAndDescription.
See Also: → 1838250

As part of my work on bug 1743749, I've been looking at all our cache keys and domains. Here are some relevant things to consider (whether in this bug or in follow-ups):

  1. nsGkAtoms::_moz_device_pixel_ratio and nsGkAtoms::resolution are needed to calculate Bounds, but they aren't currently included in a cache domain. That said, these are only cached for the document, so maybe we can just always cache them. Or perhaps we can move them into the Bounds domain.
  2. nsGkAtoms::role, nsGkAtoms::tag and nsGkAtoms::textInputType aren't included in a domain. They are only sent for an initial cache update. They'll probably need a domain.
  3. nsGkAtoms::state is only sent for an initial cache update. It is updated using state change events henceforth. The initial restriction should probably be removed.
  4. nsGkAtoms::headerContentTypeisn't included in a cache domain and is only sent for an initial cache update. That said, this is only cached for the document, so maybe we can just always cache it.
  5. nsGkAtoms::spelling has its own domain, but it must currently also be updated when text is updated. If spelling is disabled, we probably don't want to update that when text is updated. Maybe text updates should also queue a spelling update instead?
  6. We may want to consider splitting out text attributes (nsGkAtoms::style) into its own domain.
  7. nsGkAtoms::line (line start offsets) and nsGkAtoms::characterData (character bounds) are pushed for either the Text or Bounds domains. Maybe we need to split them into their own domain and have text and bounds updates queue an update for that domain too?
  8. nsGkAtoms::overflow and nsGkAtoms::position are part of the Style cache domain, but they're needed for bounds. Maybe we should move them into the Bounds domain?

This patch might also be useful. It documents all the keys and the domains they're part of.

(In reply to James Teh [:Jamie] from comment #4)

  1. nsGkAtoms::line (line start offsets) and nsGkAtoms::characterData (character bounds) are pushed for either the Text or Bounds domains. Maybe we need to split them into their own domain and have text and bounds updates queue an update for that domain too?

Note that if this new domain is requested in the parent process, we'll also need to request the bounds domain, since line starts and character bounds depend on knowing about bounds changes.

One other thing to note is that the text of a TextLeafAccessible is returned when Accessible::Name is called on it. Accessible::Name thus needs to request either NameAndDescription or Text, depending on what it is called on.

I've been thinking about how we can improve our attribute querying in light of how we plan to split up cache domains. There are a few classes of bugs I'd like to make difficult to write:

  • Requesting a value for a cache key associated with an inactive domain
  • Forgetting to properly request the relevant domains for the function at hand
  • Passing the wrong template type for the given cache key to GetAttribute

There are a few things I'd like to accomplish to address these issues:

  1. Make it easy to get domains associated with cache keys
    a. Do this in a constexpr way so we don't incur any runtime penalty (hash lookups or memory) and don't have to worry about static initialization
    b. Do this while also using the cache key static atom aliases, for readability
  2. Make it easy to request domains and return early if any of the domains associated with cache keys are not active
  3. Make it easy to get the data type associated with each cache key
  4. Enforce the rule that any requested cache key must be domain-checked before querying it. That is, don't let ourselves request a cache key without ensuring that the associated domain is already active.

I've been toying around and proving out ideas to address these hopes.

Getting and Requesting Cache Domains

To get the domain associated with each cache key, I'd like to introduce a function of this form:

constexpr uint64_t GetCacheDomainForKey(const nsStaticAtom* aCacheKey) {
  if (aCacheKey == CacheKey::Name) {
    return CacheDomain::NameAndDescription;
  } else if (aCacheKey == CacheKey::State) {
    return CacheDomain::State;
  } else if (/* and so on... */) {}
}

Because static atoms are comparable at compile time, we can write

constexpr uint64_t domainForCacheKey = GetCacheDomainForKey(CacheKey::Name);

and resolve this domain at compile time, without the need for a hash table or other runtime lookup.

For any number of cache keys, we could use something like:

constexpr uint64_t GetRequiredCacheDomains(
  std::initializer_list<nsStaticAtom*> aCacheKeys) {
  uint64_t requiredCacheDomains = 0;
  for (nsStaticAtom* cacheKey : aCacheKeys) {
    requiredCacheDomains |= GetCacheDomainForKey(cacheKey);
  }
  return requiredCacheDomains;
}

Then,

constexpr uint64_t requiredCacheDomains = GetRequiredCacheDomains(CacheKey::Name, CacheKey::State);

also resolves at compile time.

Next, assume we have a function RequestDomainsIfMissing which takes the required cache domains and compares them to the active cache domains, sending off requests to all content processes and returning true if any domains were missing. We can then write a macro like so (name WIP) which returns the "domain not cached" result and fires off requests to content if any associated domain is missing:

#define CHECK_ATTRIBUTE_DOMAINS_CACHED(aAttributesNotCachedResult, ...) \
  {                                                                     \
    constexpr uint64_t requiredCacheDomains =                           \
        GetRequiredCacheDomains({__VA_ARGS__});                         \
    if (RequestDomainsIfMissing(requiredCacheDomains)) {                \
      return aAttributesNotCachedResult;                                \
    }                                                                   \
  }

This macro can be invoked at the top of every RemoteAccessible function that requests something from the cache. For instance:

CHECK_ATTRIBUTE_DOMAINS_CACHED(false, CacheKey::Name, CacheKey::State)

I think marshaling all attributes into a domain, even if that domain is an "Always" domain or similar, would help us here. This solves (1) and (2) above.

Getting the Data Type Associated with each Cache Key

(3) Is not a directly pressing problem, but I think it's worth solving. Crucially, we know the data types associated with each cache key at compile time. We open ourselves up to really annoying-to-hunt-down programming mistakes that we could solve entirely at compile time. The actual address of cache keys is not known at compile time, but their offset from the start of the static atoms array (mozilla::detail::gGkAtoms.mAtoms) is. We can use this information to build pointer-to-type associations. Imagine this utility function:

constexpr size_t AtomOffset(const nsStaticAtom* aAtom) {
  return aAtom - mozilla::detail::gGkAtoms.mAtoms;
}

And this template struct + template alias combo:

namespace detail {
template <size_t AtomOffset>
struct GetAttrType {};
template <>
struct GetAttrType<AtomOffset(CacheKey::Name)> {
  using type = nsString;
};
template <>
struct GetAttrType<AtomOffset(CacheKey::State)> {
  using type = uint64_t;
};
// ... and so on for each cache key ...
}  // namespace detail

// utility type alias, akin to standard library type aliasing
template <size_t AtomOffset>
using GetAttrTypeT = typename detail::GetAttrType<AtomOffset>::type;

We could then get the attribute type like so:

using NameAttrType = GetAttrTypeT<AtomOffset(CacheKey::Name)>;
static_assert(std::is_same_v<NameAttrType, nsString>, "types are the same!");

This helps us build a member function in AccAttributes:

template <size_t AtomOffset>
decltype(auto) GetAttributeSafe() const {
  return GetAttribute<GetAttrTypeT<AtomOffset>>(nsGkAtoms::GetAtomByIndex(AtomOffset));
}

which we can use like so in RemoteAccessible:

mCachedFields->GetAttributeSafe<AtomOffset(CacheKey::Name)>();

With that, we have the ability to safely (read: checked at compile time) get an attribute value for a cache key without having to specify the type at the call site, addressing (3) above. We can collect cache keys and their associated types in one place, centralizing how we add new cache keys. The semantics of this might be a little grating, but we can improve things with a macro, which I'll detail in the next section.

Ensuring All Requested Cache Keys are Domain-Checked before Querying

It would be nice to assert that the cache keys we're looking to query in a function have been domain-checked, without having to think too hard about it. I want to eliminate the class of error where someone adds a new GetAttribute call but forgets to add the attribute to the CHECK_ATTRIBUTE_DOMAINS_CACHED macro invocation, since that might mean they're looking for info in an uncached domain.

To solve this, we can expand the CHECK_ATTRIBUTE_DOMAINS_CACHED macro, adding:

const auto _CHECKER_FN = GetCheckerFunction({__VA_ARGS__});

where GetCheckerFunction is defined as such:

std::function<bool(const nsStaticAtom*)> GetCheckerFunction(
    std::initializer_list<nsStaticAtom*> atoms) {
  return [atoms](const nsStaticAtom* aAtom) {
    for (auto atom : atoms) {
      if (aAtom == atom) {
        return true;
      }
    }
    return false;
  };
}

This puts a function at function scope that we can call to verify that the requested cache key has been domain-associated. I think this should probably only happen in debug builds, to avoid the std::function overhead. Consider this new RemoteAccessible function:

template <typename T>
Maybe<const T&> GetAttributeSafeInternal(
    nsStaticAtom* aCacheKey,
    const std::function<bool(nsStaticAtom*)> aCheckerFn) const {
  MOZ_ASSERT(mCachedFields);
  MOZ_ASSERT(
      aCheckerFn(aCacheKey),
      "Requested cache key is not domain-checked at the top of the calling "
      "function. Please add it to the CHECK_ATTRIBUTES_DOMAIN_CACHED macro.");
  return mCachedFields->GetAttribute<T>(aCacheKey);
}

This enables us to write the following macro for getting cache values:

#define GetAttributeSafe(cache_key)  \
  GetAttributeSafeInternal<GetAttrTypeT<AtomOffset(cache_key)>>(cache_key, _CHECKER_FN)

meaning we can write, simply:

GetAttributeSafe(CacheKey::Name);

and get all of the safety checks that we're hoping for.

Putting it Together

Take the current implementation of RemoteAccessible::IsClipped:

bool RemoteAccessible::IsClipped() const {
  MOZ_ASSERT(mCachedFields);
  if (mCachedFields->GetAttribute<bool>(nsGkAtoms::clip_rule)) {
    return true;
  }
  return false;
}

With this above utilities, we could write:

bool RemoteAccessible::IsClipped() const {
  CHECK_ATTRIBUTE_DOMAINS_CACHED(false, CacheKey::IsClipped);
  if (GetAttributeSafe(CacheKey::IsClipped)) {
    return true;
  }
  return false;
}

I'm not sold on any of these ideas, but I think some subset of them might be useful and would like peoples' thoughts on them.

Thanks for all the thought you've put into this. You've definitely identified some opportunities/concerns I hadn't considered. Before I dive too deep here, I want to raise a couple of high level points.

This macro can be invoked at the top of every RemoteAccessible function that requests something from the cache. For instance:

CHECK_ATTRIBUTE_DOMAINS_CACHED(false, CacheKey::Name, CacheKey::State)

I'm not sure if this is a real issue or a stylistic preference, but outside of isolated contexts, I don't love macros which make the caller return something. They definitely shorten the code, but they also make it harder to spot returns, especially if you're not super familiar with it. It also makes it difficult to handle cases where you need to do something other than just return a result; e.g. maybe you need to set an out parameter in a certain way. Our style guide has this to say, albeit less than confidently:

Previously, the NS_ENSURE_* macros were used for this purpose, but those macros hide return statements, and should not be used in new code. (This coding style rule isn’t generally agreed, so use of NS_ENSURE_* can be valid.)

As verbose as it is, I think I'd prefer (name also TBD):

if (RequestDomainsForAttributesIfMissing(CacheKey::Name, CacheKey::State) {
  return false;
}

I think marshaling all attributes into a domain, even if that domain is an "Always" domain or similar, would help us here.

That's probably a good idea anyway, probably even necessary for other reasons.

Getting the Data Type Associated with each Cache Key

Having very recently looked through all our cache keys, I don't think we do this anywhere in the top level cache at present, but I do wonder whether there'll ever be a point where a key could have multiple types. I'm pretty sure we do this in at least one nested AccAttributes. Specifically, I think CacheKey::ARIAAttributes can include attributes which are either atoms or strings, depending on whether we were able to normalize the token [or not(https://searchfox.org/mozilla-central/rev/ee35c5249171669c4428739f84ee7a7eb0f30316/accessible/base/ARIAMap.cpp#1635). That doesn't impact your work here; I just raise it as an example of where we've done this in the past. The benefits of type checking might outweigh the potential for flexibility here, though. And we can always do the raw calls if we absolutely need to do something special here.

On a related note, there definitely are cases where we rely on AccAttributes to do the string conversion for us, even if we only ever set the key with one value type. We do this a lot when getting string attributes or converting atom attributes to strings. (Note that many attributes are stored as atoms to optimise memory usage, even if we know the client will mostly want a string.) I don't think your current magic handles this case. It probably isn't hard to add, but I thought it worth flagging.

namespace detail {
template <size_t AtomOffset>
struct GetAttrType {};
template <>
struct GetAttrType<AtomOffset(CacheKey::Name)> {
  using type = nsString;
};

Ug. I really wish there were a way we could do this with if constexpr or something. I guess there's no way to do that, but I find these kinds of C++ boilerplate really hard to read. They tend to result in "just copy/paste when you're adding something new and move on", rather than "actually understand what this does before you copy/paste it". :) I guess we could encapsulate this in a macro at the very least.

As verbose as it is, I think I'd prefer (name also TBD):
if (RequestDomainsForAttributesIfMissing(CacheKey::Name, CacheKey::State) {

Agreed, this seems clearer.

I do wonder whether there'll ever be a point where a key could have multiple types.

Ah! I assumed it was a one to one mapping without knowing for sure. Raw calls are still fine. The type checking isn't crucial, it just feels like a class of bugs we could eliminate for the common use case.

there definitely are cases where we rely on AccAttributes to do the string conversion for us

I think this is referring to the GetAttribute overload with the nsAString second parameter; good call-out, thanks. It should be a matter of adding an overload, but I haven't actually proved this out to myself locally yet.

Ug. I really wish there were a way we could do this with if constexpr or something.

Yeah, it doesn't feel great, and I'm probably a bit too used to it to where it doesn't register as weird to me. I wish there was a way to if constexpr it, but we need to "return" a type, so we're forced to use a metafunction. The other big annoyance here is that C++ won't accept nsStaticAtom* as a template argument (the actual pointer value is determined at runtime, we only have the offset at compile time), meaning we have to do the AtomOffset hop. A macro like

#define DEFINE_CACHE_ATTRIBUTE_TYPE(aCacheKey, aType) \
  template <>                                         \
  struct GetTypeForAttr<AtomOffset(aCacheKey)> {      \
    using type = aType;                               \
  };

should make it a lot clearer.

I think this work needs to have an accompanying document, "how to add a new cache attribute." My hope is that the work of defining a new attribute will be contained to one file, not including its uses.

(In reply to Nathan LaPré from comment #9)

As verbose as it is, I think I'd prefer (name also TBD):
if (RequestDomainsForAttributesIfMissing(CacheKey::Name, CacheKey::State) {

Agreed, this seems clearer.

Agh, except that it removes our ability to define the cache key checker function used to verify that GetAttribute calls have requested the domain of the cache key in questions, since we're no longer using a macro. It also makes it harder (in that I haven't found a way around it) to guarantee constexpr evaluation of the key-to-domain associations. Hmph. I'll have to think more about this.

(In reply to Nathan LaPré from comment #9)

The type checking isn't crucial, it just feels like a class of bugs we could eliminate for the common use case.

That's fair.

I think this is referring to the GetAttribute overload with the nsAString second parameter

Yup.

Ug. I really wish there were a way we could do this with if constexpr or something.

Yeah, it doesn't feel great, and I'm probably a bit too used to it to where it doesn't register as weird to me.

To be fair, I guess this is just one of the things you have to live with if you're doing C++ and I should probably just get used to it. This kind of thing has always felt kinda like a hack that became a feature of the language rather than a properly defined feature, but at the end of the day, it is what it is. I'm glad we have things like if constexpr to move us away from some of this, but it's unfortunate we can't do that here.

I think this work needs to have an accompanying document, "how to add a new cache attribute." My hope is that the work of defining a new attribute will be contained to one file, not including its uses.

I wonder if we can somehow get all of this into one macro, kinda like we do with RoleMap.h:

CACHE_KEY(Name, nsString, CacheDomain::NameAndDescription)

Definitely an abuse of the pre-processor, but if it makes defining new things easier, I'm okay with that. :)

(In reply to Nathan LaPré from comment #10)

Agh, except that it removes our ability to define the cache key checker function used to verify that GetAttribute calls have requested the domain of the cache key in questions, since we're no longer using a macro.

This doesn't have to be a function; it can still be a macro, I think? It just needs to be a macro that evaluates to true, rather than returning itself.

I wonder if we can somehow get all of this into one macro, kinda like we do with RoleMap.h

Definitely; this would be ideal, and I think it should be pretty simple to do. They gave us a preprocessor, we might as well use it.

This doesn't have to be a function; it can still be a macro, I think? It just needs to be a macro that evaluates to true, rather than returning itself.

It could still be a macro, yes. I'm referring to the construction of what I called _CHECKER_FN above, a function that's used by the GetAttributeSafe macro to automatically verify that the cache key being requested has been cache-domain-checked at the top of the function. It's also useful to be able to force constexpr evaluation of cache key to attribute associations via a macro'd constexpr variable definition (not easily possible in an if statement), though I need to check whether compilers actually need that in order to resolve it at compile time (I don't think so, in practice). Regardless, I might be able to do this a different way. I have an idea or two to try.

Oh, I get it. The if/return thing is not essential, just preferred. If you can't make it work, I think the earlier approach is fine.

Okay, I've worked at this a bit and have a new idea that feels better. By making a cache query helper class, we can store the required cache key (offsets) at compile time, like so:

template <size_t... AtomOffsets>
struct CacheQueryHelper {
    static constexpr std::array<size_t, sizeof...(AtomOffsets)> mOffsets{AtomOffsets...};
};

Then we can put the query-related functions there. This method also achieves something I didn't get before: we can now static_assert that any requested attribute via GetAttribute has been "registered" with the query helper! I much prefer compile-time errors. Plus we can wrap up the runtime assert on mCachedFields. Two helper macros make this better:

#define ADD_ATOM_OFFSET(cache_key) AtomOffset(cache_key)
#define MAKE_CACHE_QUERY_HELPER(...) \
  CacheQueryHelper<MOZ_FOR_EACH_SEPARATED(ADD_ATOM_OFFSET, (, ), (), (__VA_ARGS__))> {}

I'm pretty happy with this. Thanks for the feedback!

I've written an initial implementation that allows us to restrict the cached domains and also keep the browser reasonably stable, in order to get some preliminary numbers for the memory savings we can expect from this work.

There are three situations I tested: (1) Everything is cached (the current behavior when accessibility is instantiated), (2) Only a minimal set is cached, including name, description, and state info (representative of the needs of less-demanding assistive technologies), and (3) Only the things that are always cached on initial update. Here are some web pages, paired with their cache's memory footprint:

  • Wikipedia, WWI:
    • Everything cached: 19.6 MiB
    • Minimal set: 8.1 MiB
    • Memory reduction: 11.5 MiB, ~59%
  • WHATWG HTML spec:
    • Everything cached: 428.5 MiB
    • Minimal set: 192.15 MiB
    • Memory reduction: 236.35 MiB, ~55%
  • RemoteAccessible.cpp on Searchfox:
    • Everything cached: 25.35 MiB
    • Minimal set: 11.47 MiB
    • Memory reduction: 13.88 MiB, ~55%

I should note that caching fewer things also makes large pages load more quickly. That's harder to quantify, but it was noticeable as I was running these tests. If we measure only what's always cached for the three situations above, we get:

  • Wikipedia, WWI: 3.95 MiB, ~20% of total
  • WHATWG HTML spec: 97.85 MiB, ~23% of total
  • RemoteAccessible.cpp on Searchfox: 7.12 MiB, ~28% of total

I think there are more savings to be had if we can cut into that always-cached information, but that'll be more work.

You need to log in before you can comment on or make changes to this bug.