[systemd-devel] Confusing hwdb matching behaviour

[David Herrmann]

Hey!

On Wed, Aug 31, 2016 at 6:37 AM, Peter Hutterer
<peter.hutterer at who-t.net> wrote:
> The hwdb behaviour is a bit hard to predict when multiple matches with globs
> apply to a device so I'm wondering whether this is just an implementation
> result or intended behaviour.
>
> Example 1:
> $> cat 99-test.hwdb
> test:*
>  match=generic
>
> test:specific*
>  match=specific
>
> $> systemd-hwdb  query "test:specific_match"
> match=specific
>
> This is what I would expect from the hwdb entries. But if we have a rule where
> glob matches before specific, the generic one overwrites the specific one:
>
> Example 2:
> $> cat 99-test.hwdb
> test:*
>  match=generic
>
> test:*specific*
>  match=specific
>  match2=yep
>
> $> systemd-hwdb  query "test:specific_match"
> match=generic
> match2=yep
>
> Definitely not what I expected (note: the order of the entries
> doesn't matter). This is actually a problem for libinput because it means we
> can't overwrite generic matches with specific matches.
> But it gets even weirder once we start stacking more:
>
> Example 3:
> $> cat 99-test.hwdb
> test:*
>  match=generic
>
> test:*specific*
>  match=specific
>  match2=yep
>
> test:*specific_match
>  match=specific
>  match2=nope
>  match3=yep
>
> $> sudo systemd-hwdb  query "test:specific_match"
> match=generic
> match2=nope
> match3=yep
>
> It picks the most generic one last but the more specific one over the less
> specific one. This is confusing and hard to predict. But it gets worse:
>
> Example 4:
> $> cat 99-test.hwdb
> test:*
>  match=generic
>
> test:*specific*
>  match=specific
>  match2=yep
>
> test:*spe*match
>  match=specific
>  match2=nope
>  match3=yep
>
> test:*specific*match
>  match=specific
>  match2=oh
>  match3=what
>  match4=confused
>
> $> sudo systemd-hwdb  query "test:specific_match"
> match=generic
> match2=yep
> match3=what
> match4=confused
>
> And now I'm lost :)
> As a homework, try predicting what this one produces:
>
> Exercise:
> test:*
>  MATCH=generic
>
> # changing this to test:specific gives different results
> test:*specific*
>  MATCH=specific
>  MATCH2=yep
>
> test:*spe*match
>  MATCH=specific
>  MATCH2=nope
>  MATCH3=yep
>
> test:*specific_*
>  MATCH=specific
>  MATCH2=oh
>  MATCH3=crap
>  MATCH4=what?
>
> test:*specific*match
>  MATCH=specific
>  MATCH2=doh
>  MATCH3=what
>  MATCH4=confused
>  MATCH5=boo
>
>
> Solution:
> "generic, oh, crap, what?, boo" with the glob, without the glob it's
> "specific, yep, crap, what?, boo"
>
> So the question is: is this the intended behaviour (if so, we should
> document it and make it official) or is this a side-effect. If that, can we
> change it or is it set in stone? I think no-one but me is currently eagerly
> stacking hwdb snippets, so maybe there's room to move.

The matching order always matches children before a node itself, and
children in alphabetical order (ASCII). The trie is built based on
prefix-matches. So parsing order does not matter. Lets look at your
last example (with both possible scenarios):

    test:*
    test:specific
    test:*specific*
    test:*spe*match
    test:*specific_*
    test:*specific*match

This will be searched in this order:

    test:*spe*match
    test:*specific*match
    test:*specific*
    test:*specific_*
    test:*
    test:specific

(Ascii order: '*' < UPPER-CASE < '_' < LOWER-CASE)
(Later matches override properties of earlier matches)

I'm not saying this is a useful order, I'm just describing what the
code currently does.

> As for expected behaviour, I'd intuitively expect a more sequential matching,
> with an entry in 99-test.hwd overwriting whatever entry was in 10-test.hwdb.

If things are not stored in ASCII order, you break bsearch() and
lookup performance would drop.

A much easier solution would be to use multiple virtual tries: Prefix
your generic matches with "test-generic:*foobar*" and your specific
ones with "test-specific:*foobar*" and then always lookup both. This
obviously only works if the number of levels is static.

As a hack, I think you can use "**", "***", ... to change the ordering
to your needs.

We could also say each hwdb-source gets its own virtual trie and
they're searched in alphabetical order. This would break ABI, but
would make it a lot more powerful.

Not sure. Maybe Kay has some comments?
David