]> git.ipfire.org Git - thirdparty/systemd.git/commit
udev: do not build full list of dependencies 40364/head
authorYu Watanabe <watanabe.yu+github@gmail.com>
Fri, 16 Jan 2026 19:14:05 +0000 (04:14 +0900)
committerYu Watanabe <watanabe.yu+github@gmail.com>
Wed, 4 Feb 2026 07:04:10 +0000 (16:04 +0900)
commitcb16d47f30cc0d848ca6868c39b844810520d713
tree904d4d3dda92a670fb0fbf29c4ae5c313cba311e
parent59bc3e7cd6fc7bcfc1d01245ccefd10ad1d3c304
udev: do not build full list of dependencies

Suppose the following dependent events are queued:

A(1000) -> C(1002)
                   \
                     --> E(1004)
                   /
B(1001) -> D(1003)

Here, each number is the seqnum of the event, and A -> B means that
event B depends on event A, that is, event B cannot be started until
event A is processed.

In this case, to know if event E can be started, we only need to check
if event C and D are processed, and not necessary to check the state of
event A or B.

However, the commit e1ae931064be9483aa98249294f6e195537f43d1 introduced
full dependency list (in the above example, all A, B, C, D are listed as
the blocker for E), but it is overkill and most information is not necessary.
Also, before the commit e1ae931064be9483aa98249294f6e195537f43d1, we
found blocker from the beginning of the queued events, but that's also
not necessary, as even A is processed, still C may be queued, and we
anyway need to check if C is processed or not.

This makes each event only stores the last blocker event for the event,
and finds the blocker from the end of the queue. With this change, the
memory cost can be reduced from O(n^2) to O(n). Also, as previously we
used Set for managing blockers, but now we only increment/decrement
the reference counter of events, so the speed should be also improved.

Fixes #39583 and #39817.
src/udev/udev-manager.c