diff options
Diffstat (limited to 'docs/briefs/tb0004-device-tree-ownership-and-registries.rst')
| -rw-r--r-- | docs/briefs/tb0004-device-tree-ownership-and-registries.rst | 226 |
1 files changed, 226 insertions, 0 deletions
diff --git a/docs/briefs/tb0004-device-tree-ownership-and-registries.rst b/docs/briefs/tb0004-device-tree-ownership-and-registries.rst new file mode 100644 index 00000000..b90d1063 --- /dev/null +++ b/docs/briefs/tb0004-device-tree-ownership-and-registries.rst @@ -0,0 +1,226 @@ +Technical Brief 0004: Device Tree Ownership and the Three Registries +======================================================================== + +:doc:`/briefs/tb0003-facet-based-capability-dispatch` covers how one device or driver answers "do you support capability X". +The :doc:`/guides/device-drivers` guide covers how a driver gets matched and bound to a device. +Neither asks a more basic pair of questions: **who keeps a device alive, and how does anything outside its own parent bus find it again?** + +Those two questions are what this brief answers: the ownership graph that decides when a device is actually destroyed, the locking primitive that protects it, and the three separate registries (``device_registry``, ``driver_registry``, ``facet_registry``) that each answer a different "find things" question over the same tree. + +The Ownership Graph +----------------------- + +A ``bus`` owns its children strongly, whereas a child only ever points back at its parent weakly. +This is the whole graph, and it is worth being precise about why it has to be exactly this shape. + +.. code-block:: cpp + + // kapi/kapi/devices/bus.hpp + struct bus : device + { + // ... + private: + kstd::vector<kstd::shared_ptr<device>> m_devices{}; // strong: the bus owns its children + }; + + // kapi/kapi/devices/device.hpp + struct device : kstd::enable_shared_from_this<device> + { + // ... + private: + kstd::weak_ptr<bus> m_parent; // weak: a child never keeps its parent alive + kstd::weak_ptr<struct driver> m_driver{}; // weak: a device never keeps its bound driver alive + }; + +``bus::add_child()`` sets the back-pointer and takes ownership in that order: + +.. code-block:: cpp + + // kernel/kapi/devices/bus.cpp + auto bus::add_child(kstd::shared_ptr<device> const & child) -> void + { + { + auto guard = kstd::lock_guard{m_lock}; + child->set_parent(kstd::static_pointer_cast<bus>(shared_from_this())); // weak back-edge + } + + if (!kapi::devices::device_registry::get().add(child)) { /* ... */ } + + auto attached = kstd::shared_ptr<device>{}; + { + auto guard = kstd::lock_guard{m_lock}; + attached = m_devices.emplace_back(std::move(child)); // strong forward-edge + } + + attached->set_state(state::present); + driver_registry::get().device_attached(attached); + } + +A cycle of two ``shared_ptr``\ s never gets collected, as each side's reference count stays above zero forever, because each is the reason the other is never zero. +If ``m_parent`` were a ``kstd::shared_ptr<bus>`` instead of a ``kstd::weak_ptr<bus>``, every subtree in the device tree would leak permanently the moment it was attached. +The bus keeps its children alive, and every child would be keeping its own parent alive. +``device::parent()`` and ``device::bound_driver()`` both call ``.lock()`` on their respective weak pointers precisely because neither edge is allowed to be a source of ownership. +A device is only allowed to to *ask*, if the thing being (parent bus or driver) is still there: + +.. code-block:: cpp + + // kernel/kapi/devices/device.cpp + auto device::parent() const -> kstd::shared_ptr<bus> + { + auto guard = kstd::lock_guard{m_lock}; + return m_parent.lock(); + } + + auto device::bound_driver() const noexcept -> driver * + { + auto guard = kstd::lock_guard{m_lock}; + return m_driver.lock().get(); + } + +The same rule governs every registry below: all three hold devices (and, where relevant, drivers) by ``weak_ptr``, never ``shared_ptr``. +A registry is an index, not an owner — a fact worth stating explicitly, because "the registry has a pointer to every device" reads, at a glance, like a reason a registry might need strong ownership, when it is exactly the opposite: an index that could keep its entries alive forever is not an index, it is a second, competing owner. + +``weak_ptr::lock()`` itself is safe to call while the object it refers to is concurrently being destroyed on another core. +Thus, a ``lock()`` call racing a bus tearing down its last strong reference to a child gets one of two well-defined outcomes: a valid, fully-alive ``shared_ptr``, or an empty one. +``lock()`` will never return a pointer to an object that is mid-destruction. + +``tracked_mutex``: What "Tracked" Actually Means +------------------------------------------------------ + +Every mutable field discussed so far — a device's own state, a bus's child list, each registry's own bookkeeping — is guarded by a ``kapi::tracked_mutex`` (``kapi/kapi/tracked_mutex.hpp``), not a plain spinlock. It is worth being precise about what "tracked" buys, because the name can suggest more than it delivers: this is not a general deadlock detector across multiple locks, or across cores waiting on each other. It solves one specific, real problem — a single core silently re-entering a lock it already holds — by recording which CPU currently owns the lock and refusing to let anything but that CPU release it: + +.. code-block:: cpp + + struct tracked_mutex + { + //! @warning This function will panic if a recursive lock on a single core is detected! + auto lock() -> void; + + //! @warning This function will panic if the core executing the call does not own the lock on this mutex! + auto unlock() -> void; + + private: + std::atomic<kapi::cpu::id> m_owner{kapi::cpu::invalid_id}; + }; + +A plain spinlock would deadlock a core against itself silently and permanently (core 3 already holds the lock; core 3 tries to take it again; core 3 now spins forever waiting for a release that will never come, because the only core that could release it is itself, and it is busy spinning). ``tracked_mutex`` turns that into an immediate, diagnosable panic at the exact call site that re-entered the lock, rather than a hang discovered later by a watchdog or a confused bug report. It does **not** detect the more general two-lock deadlock (core A holds lock 1 and waits for lock 2; core B holds lock 2 and waits for lock 1) — that remains the caller's responsibility, governed by whatever lock-ordering discipline the surrounding code follows. + +The Three Registries +------------------------ + +The tree itself (parent/child pointers on ``bus``/``device``) only answers one question: "who are this bus's direct children". Everything else — "find the device named X anywhere in the tree", "who currently implements facet Y", "which driver, if any, wants this device" — goes through one of three purpose-built, independent registries, each a system-wide singleton reached through its own ``get()``. + +.. list-table:: + :header-rows: 1 + + * - Registry + - Answers + - Keyed by + - Owns entries? + * - ``device_registry`` + - "Is there a device named X, anywhere in the tree?" + - device tree-name (``kstd::string``) + - No — ``weak_ptr<device>`` + * - ``driver_registry`` + - "Try every registered driver against this device" / vice versa + - not keyed — a flat list, tried in full each time + - Yes — ``shared_ptr<driver>`` (drivers are not tree members; something has to own them) + * - ``facet_registry`` + - "Which devices currently implement facet Y?" (:doc:`/briefs/tb0003-facet-based-capability-dispatch`) + - ``facet_id`` + - No — ``weak_ptr<device>`` + +``device_registry`` is the simplest of the three: a flat map from name to a weakly-held device, populated by ``bus::add_child()`` and pruned by ``bus::do_remove_child()``, with ``find()``/``all()`` as its read side: + +.. code-block:: cpp + + // kapi/kapi/devices/device_registry.hpp + struct device_registry + { + auto add(kstd::shared_ptr<device> const & device) -> bool; + auto remove(device & device) -> bool; + [[nodiscard]] auto find(std::string_view name) const -> kstd::shared_ptr<device>; + [[nodiscard]] auto all() const -> kstd::vector<kstd::shared_ptr<device>>; + auto subscribe(kstd::weak_ptr<device_registry_observer> observer) -> void; + }; + +``driver_registry`` looks similar on the surface (also a system-wide singleton with an ``add()``) but is not a lookup structure at all — it has no ``find()``, no name, no key. Its entire purpose is the matching algorithm covered in the driver guide (:doc:`/guides/device-drivers`); "which drivers exist" is never a question anything outside ``driver_registry`` itself needs to ask, so there is no API for it. + +``facet_registry`` sits in between: like ``device_registry`` it is a read-and-subscribe index over weakly-held devices, but its key is a capability (``facet_id``) rather than an identity (a name), and — a real, deliberate asymmetry worth noticing — it offers *two* different subscription shapes, not one: + +.. code-block:: cpp + + // kapi/kapi/devices/facet_registry.hpp + auto subscribe(kstd::weak_ptr<facet_registry_observer> observer) -> void; // safe if the observer dies unregistered + auto subscribe(facet_registry_observer & observer) -> void; // observer must outlive its subscription + auto unsubscribe(facet_registry_observer & observer) -> void; + +``device_registry_observer`` only ever gets the first, safer shape. ``facet_registry`` additionally accepts a raw, must-outlive-or-else reference — useful for a long-lived, non-``shared_ptr``-managed subsystem (a singleton driver of drivers, say) that would rather not pay for a ``weak_ptr`` it knows it will never need, at the cost of undefined behavior if that assumption is ever wrong. Both registries prune expired weak subscriptions lazily, on the next notification pass, rather than eagerly. + +Why three registries, and not one generic one? This is worth asking directly, because :doc:`/briefs/tb0003-facet-based-capability-dispatch` makes the opposite argument for facets — one generic ``facet_registry`` rather than one bespoke registry per capability — and it would be reasonable to expect the same collapse here. It does not apply, for a structural reason: a generic facet is *interchangeable* with any other facet from the registry's point of view (the registry never inspects what a facet actually does, only that a ``facet_id`` names it) — that is exactly what let ``interface_registry``-turned-``facet_registry`` become one type. Identity-by-name, capability-by-facet, and driver-binding-state are not interchangeable in that sense: they answer structurally different questions, over different notions of "the same entry" (a name is unique per bus; a facet can be published under many different names by many different devices; a driver has no name-like key at all). Collapsing them would not remove duplicated bookkeeping the way unifying the facet registries did — it would conflate three genuinely different concerns back into one type, which is precisely the failure mode the whole facet mechanism exists to avoid in the first place. + +A Known Issue: Duplicate Names in ``device_registry::add()`` +------------------------------------------------------------------ + +Tracing ``device_registry::add()`` for this brief turned up a real discrepancy between its documented contract and its current behavior, worth recording plainly rather than silently working around in the prose above. + +The header says: *"@return true if the device was registered successfully, false otherwise."* The one test that exists for this registry (``kernel/kapi/devices.tests.cpp``) is scoped even more narrowly — its own scenario name is *"the device registry holds devices weakly and prunes stale entries lazily"*, and it only exercises reusing a name whose previous registration has already **expired**. Neither promises that registering a second device under a name that is still **live** should succeed — the reasonable reading of "registered successfully, false otherwise" is that a live name collision is exactly the "otherwise" case. + +The implementation does not do that: + +.. code-block:: cpp + + // kernel/kapi/devices/device_registry.cpp + auto found = m_devices.find(device->name()); + if (found != m_devices.end()) + { + if (!found->second.expired()) + { + added = false; + } + + found->second = device; // <-- unconditional, regardless of the branch above + added = true; // <-- unconditional, overwriting the false set two lines up + } + else + { + added = m_devices.emplace(device->name(), device).second; + } + +The ``added = false;`` inside the ``!expired()`` branch is immediately overwritten by the unconditional ``found->second = device; added = true;`` that follows it, regardless of which branch ran. As written, registering a second, live device under a name that is already registered to a different, still-live device always succeeds, silently replaces the registry's entry, and returns ``true`` — the live-collision rejection the surrounding code visibly intends (the ``expired()`` check would otherwise have no purpose at all) never actually triggers. This is not exercised by any existing test, since the one test that touches name reuse only covers the expired case. + +This looks like an unintentional gap between intent and implementation rather than a deliberate design choice, and is flagged here rather than fixed silently, since fixing it changes observable behavior (a second ``add_child()`` under a colliding, still-live name would start returning ``false`` and, per ``bus::add_child()``'s own panic-on-registration-failure path, would newly ``panic`` instead of silently proceeding) — a decision worth making deliberately rather than as a side effect of writing this brief. + +Parallels in Other Systems +------------------------------ + +**Linux's device/driver-core registries** are the closest relative, and split along a similar seam: ``/sys`` (backed by ``struct kobject``/``kset``) is Linux's name-addressable device index — the rough analogue of ``device_registry`` — while each ``struct bus_type`` keeps its own driver list, matched against devices exactly where ``driver_registry`` sits here. Linux additionally layers ``struct class`` on top for a capability-flavored view (all block devices, regardless of bus) — closer in spirit to ``facet_registry`` than to either of the other two, though implemented as its own bespoke mechanism rather than TeachOS's one generic capability index (see the Linux comparison in :doc:`/briefs/tb0003-facet-based-capability-dispatch` for why that unification doesn't have a direct Linux equivalent). + +**GObject's weak-reference bookkeeping** (``g_object_add_weak_pointer()``/``g_object_weak_ref()``) is a close parallel to the pruning behavior of ``device_registry``'s and ``facet_registry``'s observer lists: a callback registered against an object's lifetime that is automatically, safely skipped once the object is gone, rather than left to dereference a dangling pointer — the same guarantee ``kstd::weak_ptr``-based subscription buys here, in a garbage-collected-adjacent language that still has to solve the same problem for non-refcounted or externally-owned objects. + +**COM's ownership discipline** (``AddRef``/``Release``, introduced in :doc:`/briefs/tb0003-facet-based-capability-dispatch` for its ``QueryInterface`` parallel) is the reason the weak-back-edge argument above should feel familiar: COM objects that hold pointers to each other in a cycle have exactly the same leak problem ``shared_ptr`` cycles do, and COM's answer — one side of any potential cycle must not hold a counted reference — is the same rule TeachOS enforces structurally by typing ``m_parent`` and ``m_driver`` as ``weak_ptr`` rather than leaving it to convention. + +Benefits +----------- + +* **The ownership rule is enforced by the type system, not by convention.** ``m_parent`` and ``m_driver`` being ``weak_ptr`` rather than ``shared_ptr`` means a cycle-introducing bug (accidentally storing a strong parent reference somewhere) shows up as a type error or a deliberate ``.lock()`` call, not as a leak discovered by watching memory usage climb. +* **Every registry is provably incapable of keeping a device alive past its real lifetime.** Because all three hold only ``weak_ptr<device>``, a device that is genuinely unreferenced everywhere else is destroyed on schedule regardless of how many registries still have a stale entry for it — the entry simply resolves to ``nullptr`` on the next lookup. +* **``tracked_mutex`` turns one whole class of concurrency bug into an immediate, attributable panic.** A same-core recursive lock is caught the moment it happens, at the exact call site responsible, rather than manifesting as an unexplained hang discovered much later. +* **Splitting identity, capability, and binding into three registries keeps each one's contract simple.** ``device_registry`` never has to reason about facets; ``facet_registry`` never has to reason about driver-binding state; ``driver_registry`` never has to reason about names. Each type is small enough to read end to end. + +Drawbacks and Limitations +----------------------------- + +* **The duplicate-name gap above is a real, live correctness issue**, not a hypothetical one — a driver or bus author who assumes ``device_registry::add()`` rejects a name collision (as its own documentation states, and as the one existing test's scenario title implies) is currently wrong, silently, with no test catching it either way. +* **``device_registry`` has no dedicated test file at all** (``kernel/kapi/devices.tests.cpp`` exercises it only indirectly, through a handful of scenarios) — the exact kind of gap that let the issue above go unnoticed, and a real argument for giving this registry the same direct, scenario-driven test coverage ``facet_registry`` and ``driver_registry`` already have. +* **Three registries is three places to remember to check**, not one. A subsystem that wants "everything currently known about a device" has to separately query ``device_registry`` (does it exist, by name), ``facet_registry`` (what can it do), and ``device.bound_driver()`` (who's driving it) — there is no single call that answers all three at once, by design, but it is still a real seam a newcomer has to learn rather than discover from one type's API surface. +* **``tracked_mutex``'s name promises more than it delivers if read quickly.** "Tracked" means same-core re-entrancy detection specifically, not deadlock detection generally — a two-lock, two-core deadlock is exactly as possible here as with a plain spinlock, and nothing in the type's name or its panic messages says so. +* **Neither ``device_registry`` nor ``facet_registry`` notifies observers atomically with the mutation that triggered them.** Both take a lock, mutate, release the lock, then take it again separately to snapshot the observer list before calling out to each one unlocked — deliberately, so an observer's callback never runs while the registry's own lock is held (avoiding a lock-order problem an observer callback that re-enters the registry would otherwise create) — but it does mean a second thread could observe the registry's new state before a given observer has been notified of the change that produced it. + +Checklist +------------ + +* A back-edge (child → parent, device → bound driver, any registry → device) is always ``weak_ptr``. If you find yourself typing ``shared_ptr`` for one of these, stop — it is almost certainly the wrong direction. +* Query a ``weak_ptr`` with ``.lock()`` and check the result; never assume it is still valid because you "just" saw it alive. +* Pick the registry that matches the actual question: a name → ``device_registry``; a capability → ``facet_registry`` (:doc:`/briefs/tb0003-facet-based-capability-dispatch`); "should a driver claim this" → the matching machinery in :doc:`/guides/device-drivers`, not a registry lookup at all. +* Don't assume ``device_registry::add()`` rejects a live name collision today — see *A Known Issue*, above — until it is either fixed or its documented contract is corrected to match what it actually does. |