Discovery Over CXL.io

Chapter 5.5 walked a capability list: given a device you already have, follow the chain of structures inside it until you find CXL DVSEC. That is a walk within one function, and it assumes you already know the function is there.

This chapter is the step before it. Software has just been handed a machine it has never seen, and it has to find out what is in it.

1. The Engineering Problem — Nobody Told the Host What Is Plugged In

At power-on the host knows one thing: where its own root complex is. It does not know how many devices exist, what they are, how deep the tree goes, whether a slot is populated, or whether the thing in a slot is working. There is no manifest. The topology has to be discovered by asking.

Everything about discovery follows from the fact that the only tool available is a probe, and a probe is a question whose answer might not arrive.

That produces three problems that have nothing to do with each other:

The third is the one that separates a walk from a hang. A traversal that terminates because the tree is well formed does not terminate — it just has not met a bad tree yet.

2. The One-Sentence Model

Discovery is a bounded traversal of untrusted data. The host walks a structure it did not build and cannot verify in advance, so every step must be safe against a topology that is malformed, cyclic, larger than expected, or partly unresponsive — and the walk must terminate and report what it could not see.

Call it the untrusted walk. Not "enumerate the devices", which makes it sound like reading a list. The list is what you are trying to produce, and the thing you are reading is a graph supplied by hardware that may be broken.

3. What This Chapter Owns

4. A Probe Has Three Answers, Not Two

The instinct is that a probe either finds a device or does not. It has three outcomes, and collapsing any two of them loses information a human operator needs.

Absent is a normal, expected, successful outcome. Most of the address space a host probes is empty. An empty slot is not an error, it produces no log entry, and treating it as one buries the real errors under thousands of routine non-findings.

Unresponsive is not absent. A device that is plugged in and failing to answer is the single most interesting thing discovery can find, and a design that reports it as "nothing there" removes it from the topology entirely. The operator then looks at a slot that reports no fault, containing a card that does not work.

That distinction drives the first module.

5. Teaching-model boundary

6. One Probe, End to End

Three things in that picture are the whole chapter.

The probe is a configuration read over CXL.io. This is why discovery belongs to CXL.io and not to CXL.cache or CXL.mem — and why an unmodified host can enumerate a CXL device at all (7.1).

The second exchange never reaches a device, because there is no device. The switch answers on its behalf. The host learns "nothing there" and that is a successful probe, not a failure.

Neither exchange shows the third case: no answer at all. That one has no arrow because nothing comes back, which is exactly why it needs a timer rather than a response.

7. RTL 1 — Present, Absent, Unresponsive

module probe_timeout #(
  parameter int unsigned LIMIT = 8,
  parameter bit TIMEOUT_IS_ABSENT = 1'b0   // 1 = a timeout reports "not there"
) ( ... );
  assign expired          = busy_q && (cnt_q >= LIMIT[7:0]);
  assign result_valid     = busy_q && (resp_valid || expired);
  assign res_present      = busy_q && resp_valid && resp_present;
  assign res_absent       = (busy_q && resp_valid && !resp_present)
                          || (expired && TIMEOUT_IS_ABSENT);
  assign res_unresponsive = expired && !TIMEOUT_IS_ABSENT;
  assign hot              = 2'd0 + res_present + res_absent + res_unresponsive;

hot counts how many of the three answers are asserted, and the checker requires it to be exactly one whenever a result is produced. That is a real property, not decoration: the natural way to write these three expressions produces overlapping conditions, and a probe that reports both absent and unresponsive leaves the caller to pick one arbitrarily.

=== EXP8: absent, present and unresponsive are three answers ===
  a node that answers yes : present=1 absent=0 unresponsive=0
  present, and exactly one of the three answers      : ok
  a node that answers no  : present=0 absent=1 unresponsive=0
  absent, and absence is an answer not a failure     : ok
  a node that never answers: timeouts=1 answered=2 unresponsive seen=1
  unresponsive is its own answer, not absence        : ok
  two answers and one timeout, all bounded          : ok
  no probe ran past its bound                       : ok
  the collapsing variant called a live device absent: ok

The last line is the TIMEOUT_IS_ABSENT instance, running on identical stimulus and reporting the unresponsive node as absent. It never fails a functional test. It simply produces a topology with a device missing from it.

There is a second bound in this module, and it is deliberately not the same as the first:

      // The bound must be independent of the response path, or a probe that
      // hangs also disables the detector that is supposed to notice.
      if (busy_q && cnt_q > LIMIT[7:0] + 8'd4) hang_err <= 1'b1;

hang_err catches the case where the timeout mechanism itself fails to fire. If the diagnostic were derived from expired, then a broken expired would disable both the timeout and the detector for it — the shared-blind-spot failure. A watchdog that depends on the thing it is watching is not a watchdog.

8. RTL 2 — What Is Worth Probing

Most probes find nothing, so the cost of ruling out an empty location is a first-order concern. Boot time on a large machine is dominated by enumeration, and enumeration is dominated by probes that come back empty.

  // The rule: function 0 must be present, and only a multi-function device
  // has functions 1..7 worth probing at all.
  assign want_more = PROBE_ALL_FUNCS ? 1'b1
                   : (IGNORE_F0_ABSENT ? f0_multifunc
                                       : (f0_present && f0_multifunc));

Two variants, two different kinds of wrong.

=== EXP7: how many functions are worth probing ===
  single-function device : correct probes=1 | probe-all probes=8
  guessing costs 8 probes where 1 suffices          : ok
  absent function 0 : correct probes=2 | ignore-absent probes=9
  probing past an absent function 0 was flagged     : ok
  the correct iterator stopped at function 0        : ok

PROBE_ALL_FUNCS is not incorrect. It finds exactly the same devices. It costs eight probes where one suffices, and multiplied across every location in a large hierarchy that is the difference between a boot that feels instant and one that does not. This is worth naming because it is the clearest example in the batch of a change that no functional test can fail and that is still the wrong design.

IGNORE_F0_ABSENT is incorrect, and subtly so. If function 0 does not respond, the device is not there, and functions 1 through 7 of a device that is not there cannot be there either. Probing them is not merely wasteful — it is asking questions of an address with no owner, which is exactly the traffic most likely to produce a completion timeout (7.5 takes up what that costs).

9. RTL 3 — The Work Queue, and the Subtree You Did Not Walk

A traversal needs a list of places still to go. That list is finite, and what happens when it fills decides whether the walk is honest.

  // NO_BOUND accepts unconditionally: the write wraps and silently overwrites
  // an entry that has not been walked yet.
  assign accepted  = enq && (NO_BOUND || !full);
 
  // A refused enqueue is an unexplored subtree, and it must be recorded.
  if (enq && !accepted) begin
    n_refused_q     <= n_refused_q + 8'd1;
    incomplete_flag <= 1'b1;
  end

This is 7.3's silent-drop lesson with a much worse consequence. There, the loss was an event record. Here, the lost item is a device that will never appear in the topology — and the walk goes on to report success.

=== EXP5: the work queue refuses rather than overwrites ===
  6 enqueues into depth 4 : level=4 peak=4 enq=4 refused=2 incomplete=1
  peak occupancy recorded the true high-water mark   : ok
  every enqueue was accepted or counted as refused  : ok
  the skipped subtree is software-visible           : ok
  no-bound variant : enq=6 refused=0 overran=1
  the unbounded variant overwrote unwalked entries  : ok
  the correct queue still holds its first entry     : ok

The last line matters. The correct queue still has node 10 at its head — it refused the two it had no room for and kept the four it had already accepted. The NO_BOUND variant wrapped and overwrote entries it had not yet walked, so it lost devices it had already found, which is worse than never finding them: the walk had the information and destroyed it.

The occupancy counter uses the same exhaustive case as 7.3's event queue, for the same reason:

=== EXP6: simultaneous enqueue and dequeue ===
  3 cycles of enq+deq together : level 3->3 enq=7 deq=4
  occupancy held across simultaneous traffic        : ok
  nothing was refused while a slot was free         : ok

That test needed an adjustment before it was meaningful. On the first attempt it opened with the queue full, so the first cycle legitimately refused the enqueue and accepted the dequeue, and the level fell by one. The measured behaviour was correct and the expectation was wrong — so the test now opens a slot first, and additionally asserts that nothing was refused while a slot was free. A test whose expected value is wrong is worse than no test, because it gets "fixed" by changing the design.

10. RTL 4 — Termination, and Why the Bound Must Stand Apart

The topology is data. It arrived from hardware. It can be malformed by a bug, by a marginal link, or by a device that is actively hostile.

  // NO_VISITED reports every node as unseen, so a cycle is walked forever.
  assign seen = NO_VISITED ? 1'b0 : bits_q[test_node[4:0]];

A cyclic topology — a node whose child is its own ancestor — is walked forever by any traversal that trusts the tree to be a tree. Cycle protection is what makes the walk terminate on well-formed and malformed input.

And then the important part, which is what happens if cycle protection is itself broken:

      // Independent watchdog: cycles, not nodes, not the visited set.
      if (running_q && cycles_q >= CYCLE_BOUND[15:0]) begin
        bound_hit_q <= 1'b1; running_q <= 1'b0; st_q <= S_DONE; done_q <= 1'b1;
      end

cycles_q counts clock cycles. It does not count nodes, it does not consult the visited set, and it does not depend on the topology being sane. This is deliberate. A bound expressed as "stop after N nodes" is computed from the same machinery that the cycle protection uses, so the fault that breaks one breaks the other — and the walk hangs with its own hang-detector disabled.

Measured on a topology whose third node points back at the root:

=== EXP3: a topology that points back at itself ===
  cyclic topology : correct visited=3 bound_hit=0 | no-visited bound_hit=1
  cycle protection terminated the walk              : ok
  without it the walk ran until the bound stopped it: ok
  no-visited variant visited=80 before the bound fired

Read those two flags together. The correct walk terminated on its own, with bound_hit clear — the bound was never needed. The variant without cycle protection visited the same three nodes eighty times and was stopped by the watchdog. Both terminated; only one was correct.

bound_hit clear is part of the pass criterion. A walk that finishes only because the watchdog fired has not enumerated the machine, and a design that treats hitting the bound as success is indistinguishable from one that works.

11. RTL 5 — The Walk

The traversal FSM ties the pieces together: pop a node, test whether it has been seen, probe it, record it, enqueue its children, repeat.

  always_comb begin
    q_enq = 1'b0; q_deq = 1'b0; v_mark = 1'b0; t_rec = 1'b0;
    case (st_q)
      S_POP:  q_deq = !q_empty;
      S_TEST: if (!v_seen) v_mark = 1'b1;
      S_REC:  t_rec = cur_present;
      S_ENQ:  if (ci_q < cur_nchild) begin
                q_enq = 1'b1;
                q_enq_node = cur_children[{4'd0, ci_q} * 8 +: 8];
              end
      default: ;
    endcase
  end

The marker at cycle 5 is the invariant worth taking away. visited increments in the last cycle of a node's processing, after every child has been enqueued — not when the node is popped. The difference shows up the moment a node does not complete:

=== EXP2: counting nodes finished, not nodes started ===
  correct visited=6 | count-pops variant=7
  the two counters disagree, as they must           : ok

Seven nodes were popped; six were finished. The seventh is an empty slot. A counter that increments on pop reports the machine as having seven devices, one of which does not exist — and it is the same defect class as 7.3's "count arrivals, not completions", which is the third time this shape has appeared in this track.

12. Reaching the End

The tail of the same walk shows both remaining behaviours: an empty slot, and termination.

Node 7 passes through REC without recording anything and goes straight back to POP — no record, no children, no error, no log entry. That is what a correct response to absence looks like: nothing happens.

Then the queue is empty and the machine enters DONE with bound_hit low. The walk ended because it ran out of work, which is the only ending that means the enumeration is complete.

=== EXP1: walking a well-formed tree ===
  6 present nodes and 1 empty slot : visited=6 recorded=6 enqueued=6 bound_hit=0
  the walk terminated on its own, not on the bound  : ok
  nothing was skipped and nothing was truncated     : ok

Six enqueued children plus the root, seven nodes examined, six present, six recorded, and the walk stopped by itself.

13. RTL 6 — A Device List Is Not a Topology

The output of discovery is not a set of devices. It is a graph, and the edges are what every subsequent decision depends on.

        node_m[count_q]    <= node_id;
        par_m[count_q]     <= NO_PARENT ? 8'hFF : parent_id;
        kind_m[count_q]    <= node_kind;
        ...
        if (node_kind != 2'd0 && !parent_known) orphan_err <= 1'b1;

parent_known searches the table for the parent before accepting the record. Every node except the root must attach to something already discovered, which is the structural invariant that makes the result a tree rather than a bag.

=== EXP9: a device list is not a topology ===
  index 1 : correct parent=0 | no-parent variant=255
  the tree edge survived into the record            : ok
  the flat variant cannot say what sits behind what : ok
  5 nodes into capacity 4 : count=4 refused=1 truncated=1
  a partial topology says that it is partial        : ok

Losing the parent pointer is not a cosmetic loss. Without it you cannot answer which switch a device sits behind — and that is the question behind bandwidth sharing, fault domains, power sequencing, hot-plug scope and error containment. A flat list of devices supports none of those decisions.

The capacity behaviour mirrors the work queue: refuse, count, and set a software-visible truncated_flag. Two different structures in this chapter can silently produce a partial topology, and both have to admit it.

14. RTL 7 — Four Numbers

      // Every node found was recorded or skipped.
      if (n_present_q != n_recorded_q + n_skipped_q) accounting_err <= 1'b1;
      // The table cannot hold more nodes than were found.
      if (n_recorded_q > n_present_q) recorded_exceeds_present_err <= 1'b1;

=== EXP10: four numbers, and the law between them ===
  probed=40 present=30 recorded=23 skipped=7
  conservation present == recorded + skipped : 30 == 30
  conservation held                                 : ok
  every count matched an independent oracle         : ok
  probed 40 slots and found 30 devices: 10 were empty

Four numbers, all four checked against an independent testbench oracle that counts in its own variables without touching the design's logic.

Read them as a report. Forty probes, thirty devices — ten probes found nothing, and that is the normal case, not a fault. Twenty-three recorded and seven skipped means the record ran out of room: the topology software receives is missing seven devices that were definitely found. Without skipped, that topology looks complete.

15. Assertions

Icarus Verilog 13.0 does not support concurrent SystemVerilog assertions, so every property below is implemented as synthesisable checker logic and verified in simulation. The assert property form states the intent.

Two of them are the ones that would catch a real design.

"Bound not needed" is stronger than "walk terminates". Every walk terminates if you put a watchdog on it. The property that says the enumeration actually worked is that the watchdog was never required.

"Peak is the maximum" was missing from the first testbench, and a mutation found the gap — see below.

16. Mutation Testing

Twenty mutations, each a plausible mistake. Twenty killed.

The first run scored eighteen of twenty, and both survivors were genuine testbench gaps rather than equivalent mutants.

Peak occupancy lags by one — a missing check. peak_q was never printed and never asserted anywhere in the testbench. It was simply an output nobody looked at, which is the easiest gap of all to have: the signal exists, the design computes it, and no line of the testbench ever mentions it. Adding one assertion in EXP5 killed it. The general form is worth stating: a testbench that never names a signal cannot test it, however thoroughly it exercises the surrounding logic.

Double mark not flagged — a vacuous checker. double_mark_err fires when a node is marked visited twice. The correct traversal always tests before it marks, so through the FSM that condition is unreachable and deleting the checker changes nothing. The fix is the same pattern 7.3 needed: an instance reserved for illegal stimulus.

  // The correct traversal always tests before it marks, so double_mark_err
  // can never fire through the FSM. Prove it is reachable at all.
  visited_set u_vx(...);

  abuse instance flagged a double mark (revisits=1) : ok
  a re-mark did not inflate the distinct-node count  : ok

The second line is the extra property that fell out of writing the test: a re-mark must be counted as a revisit and must not increment the distinct-node count. Without it, a walk with a cycle-protection bug would over-report how many devices it found.

Two mutations are worth noting for what killed them rather than that they died. NO_VISITED and "nodes tested but never marked" were both caught by the correct walk hit its cycle bound — the assertion that says the enumeration finished on its own. That single property catches every failure of cycle protection regardless of mechanism, which is what makes it worth more than a check on the visited set itself.

17. Verification Plan

The coverage model is a cross of topology shape against node outcome: tree, cycle and oversized, each crossed with present, absent and unresponsive. Random topology generation is worth adding on top, and its value is exactly that it produces shapes nobody thought to write down — but the directed cyclic case must be there explicitly, because a random generator that builds trees will never produce a cycle.

18. Debug Lab

// Walk step: no record of where we have been.
if (cur_present) begin
  record_node();
  enqueue_children();
end

  cyclic topology : correct visited=3 bound_hit=0 | no-visited bound_hit=1
  no-visited variant visited=80 before the bound fired

if (!seen(node)) begin
  mark(node);
  if (cur_present) begin record_node(); enqueue_children(); end
end

// Walk terminates when the node budget runs out; that counts as done.
if (nodes_walked >= MAX_NODES) begin
  done_q <= 1'b1;          // no indication that this is not a normal ending
end

  cyclic topology : correct visited=3 bound_hit=0 | no-visited bound_hit=1

// Independent watchdog: cycles, not nodes, not the visited set.
if (running_q && cycles_q >= CYCLE_BOUND[15:0]) begin
  bound_hit_q <= 1'b1;     // a DIFFERENT ending, and it is visible
  done_q      <= 1'b1;
end

assign res_absent = (resp_valid && !resp_present) || expired;   // timeout == absent

  a node that never answers: timeouts=1 answered=2 unresponsive seen=1
  the collapsing variant called a live device absent: ok

assign res_absent       = resp_valid && !resp_present;   // it answered: nothing there
assign res_unresponsive = expired && !TIMEOUT_IS_ABSENT; // it did not answer at all

// Enqueue a discovered child.
mem_q[wr_q] <= child_id;
wr_q        <= wr_q + 1;      // no room check, and no record if there is none

  6 enqueues into depth 4 : level=4 peak=4 enq=4 refused=2 incomplete=1
  no-bound variant : enq=6 refused=0 overran=1

assign accepted = enq && !full;
if (enq && !accepted) begin
  n_refused_q     <= n_refused_q + 8'd1;
  incomplete_flag <= 1'b1;        // software-visible: this topology is partial
end

S_TEST: begin
  n_visited_q <= n_visited_q + 8'd1;    // counted on entry
  ...
end

  correct visited=6 | count-pops variant=7

S_ENQ: begin
  if (ci_q < cur_nchild) ci_q <= ci_q + 2'd1;
  else begin
    n_visited_q <= n_visited_q + 8'd1;   // finished: children all queued
    st_q        <= S_POP;
  end
end

// Record what we found.
node_m[count_q] <= node_id;
kind_m[count_q] <= node_kind;
// parent is not recorded

  index 1 : correct parent=0 | no-parent variant=255
  the flat variant cannot say what sits behind what : ok

node_m[count_q] <= node_id;
par_m[count_q]  <= parent_id;         // the edge, not just the node
kind_m[count_q] <= node_kind;
if (node_kind != 2'd0 && !parent_known) orphan_err <= 1'b1;

// Probe every function at every location.
assign want_more = 1'b1;

  single-function device : correct probes=1 | probe-all probes=8

assign want_more = f0_present && f0_multifunc;

19. Design Review

1. Does the walk terminate on a cyclic topology? If the answer relies on the tree being a tree, it does not.
2. Is the termination bound independent of the mechanism that can fail? Count cycles, not nodes.
3. Can the caller distinguish "finished" from "gave up"? If not, an incomplete topology is indistinguishable from a complete one.
4. How many outcomes does a probe have? If two, unresponsive devices are being reported as empty slots.
5. What happens when the work queue fills? Refuse and record, never overwrite.
6. Are the edges recorded, or only the nodes? A list is not a topology.
7. What does the device counter count — starts or completions? Empty slots expose the difference.
8. How many probes does enumeration issue? Correct and slow is still a defect on a large machine.
9. Which structures can silently truncate the result? Each needs its own software-visible flag.

20. How This Appears in Real Engineering

Bring-up. Discovery is the first thing that has to work, and a discovery bug looks like a hang with no output — the hardest possible failure to diagnose, because the mechanism that would report the problem is the one that failed.

Firmware. Most of this logic lives in host firmware, where the untrusted-data discipline matters most: firmware runs before any of the protections a running OS provides, and the data it is walking came from a device that may be faulty.

Hot plug. Every property here has to hold while the topology is changing. A device removed mid-walk produces exactly the unresponsive case, and a walk that treats it as absent produces a topology that silently disagrees with reality.

Large systems. Probe count is a boot-time budget. On a machine with many slots the difference between one probe and eight per location is measured in seconds of boot time, and it is the kind of regression that ships because nothing fails.

Fleet diagnostics. incomplete_flag, truncated_flag and bound_hit are the three bits that distinguish "this machine has four devices" from "this machine reported four devices and we do not know how many it has".

21. Common Misconceptions

22. Interview Reasoning

23. Exercises

1. Analysis. A machine reports probed=512, present=64, recorded=64, skipped=0, bound_hit=0, incomplete=0, and an operator insists a card is missing from a populated slot. Nothing in those numbers is inconsistent. Name the two implementation faults still compatible with that report, and the one extra counter that would distinguish them.

2. Design. Extend the walk to record depth, and enforce a maximum depth as a third independent bound. State what this catches that the visited set and the cycle watchdog do not, and give the topology that distinguishes all three.

3. RTL task. Change the traversal from breadth-first to depth-first by making the work queue a stack. State which properties in §15 remain true unchanged, which need restating, and what happens to the peak-occupancy requirement on a deep narrow topology versus a shallow wide one.

4. DV task. Write the coverage cross for this walk, then explain why a random topology generator cannot close it, and which two points must be directed tests.

5. Debug task. Enumeration is correct on every machine but boot time doubled after a firmware update that changed no enumeration logic. Give your investigation order and the single measurement that settles it.

6. Design review. A colleague proposes dropping incomplete_flag because "the walk sizes its queue from the maximum supported topology, so it can never fill". Give the strongest version of that argument, then name the two conditions under which it is false and what the flag costs.

24. Summary

Discovery is a bounded traversal of untrusted data, and every property follows from not trusting the topology.

• A probe has three answers: present, absent, unresponsive. Collapsing the third into the second deletes a broken device from the topology and leaves an operator with a slot that reports no fault.
• Absence is the common, successful case. Correct handling of it is that nothing happens.
• Cycle protection makes the walk terminate on malformed input, and the watchdog behind it must count something the fault cannot stop — cycles, not nodes.
• Finishing is not enumerating. done && !bound_hit is the property that means the topology is whole; done alone is satisfied by giving up.
• A full work queue must refuse and record, never overwrite: overwriting loses devices the walk had already found.
• A device list is not a topology. Without the parent edge, nothing downstream can answer what sits behind what.
• Count nodes finished, not nodes started — the third appearance of this defect in the track, and empty slots are what expose it.
• Correct and slow is still a defect: eight probes where one suffices is a boot-time regression no functional test can catch.
• Verification lesson: a testbench cannot test a signal it never names, and a checker the correct design cannot trigger needs an instance reserved for illegal stimulus.

Chapter 7.5 takes the transaction underneath all of this apart: why a configuration read blocks and a memory write does not, what a completion is for, and what it costs when one never arrives.