1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// ring4: four nodes on a one-way ring (0 -> 1 -> 2 -> 3 -> 0). Node i keeps the packets that are
// at node i in a two-entry buffer. Each cycle the head packet of every buffer either leaves the
// ring (it has arrived) or moves to the next node's buffer if that buffer has a free entry.
// A host at each node injects new packets into its own node's buffer.
// FIX=1: a packet already on the ring wins over an injection (transit first).
// FIX=0: the host wins (local first), a change made to give busy hosts a fair share.
module ring4 #(parameter bit FIX = 1) (
  input  logic       clk, rst_n,
  input  logic [3:0] inj_valid,                   // host i has a packet for the ring
  input  logic [7:0] inj_dest,                    // 2 bits per host: destination node
  output logic [3:0] inj_ready,                   // host i's packet is taken this cycle
  output logic [3:0] eject                        // a packet left the ring at node i
);
  logic [1:0] dest [4][2];                        // buffer i, entry 0 is the head
  logic [1:0] cnt  [4];
  logic [3:0] move, arrive;
  always_comb begin
    for (int i = 0; i < 4; i++) begin
      int nx;
      nx = (i + 1) % 4;
      eject[i] = (cnt[i] != 0) && (dest[i][0] == 2'(i));
      move[i]  = (cnt[i] != 0) && (dest[i][0] != 2'(i)) && (cnt[nx] < 2'd2)
              && (FIX || !(inj_valid[nx]));            // local first: the host takes the free entry
    end
    for (int i = 0; i < 4; i++) begin
      arrive[i]    = move[(i + 3) % 4];
      inj_ready[i] = inj_valid[i] && !arrive[i] && (cnt[i] < 2'd2);
    end
  end
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) for (int i = 0; i < 4; i++) cnt[i] <= '0;
    else for (int i = 0; i < 4; i++) begin
      logic [1:0] c;
      logic       pop;
      pop = eject[i] || move[i];
      c = cnt[i];
      if (pop) begin dest[i][0] <= dest[i][1]; c = c - 2'd1; end
      if (arrive[i] || inj_ready[i]) begin
        dest[i][c[0]] <= arrive[i] ? dest[(i + 3) % 4][0] : inj_dest[2*i +: 2];
        c = c + 2'd1;
      end
      cnt[i] <= c;
    end
endmodule

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

"""cycles.py: find the cycles in a wait-for graph dumped at a hang.
usage: python3 cycles.py <edges.txt | ->   (no argument: the ring4 dump below, with a self-check)
Input lines: EDGE <waiter> <waited-for> <reason...>; other lines are ignored.
Prints every cycle (a strongly connected group of waiters), the agents blocked behind a cycle,
and the chains that end at an agent waiting for nothing (a lost event, not a deadlock)."""
import sys

RING4_SEED1 = """\
HANG at cycle 107: sent 12/14/9/13, delivered 40
EDGE buf0 buf1 head for node 2 needs a free entry in buf1 (full)
EDGE host0 buf0 new packet needs a free entry in buf0 (count 2)
EDGE buf1 buf2 head for node 3 needs a free entry in buf2 (full)
EDGE host1 buf1 new packet needs a free entry in buf1 (count 2)
EDGE buf2 buf3 head for node 0 needs a free entry in buf3 (full)
EDGE host2 buf2 new packet needs a free entry in buf2 (count 2)
EDGE buf3 buf0 head for node 0 needs a free entry in buf0 (full)
EDGE host3 buf3 new packet needs a free entry in buf3 (count 2)
"""


def parse(text):
    edges = {}                                    # waiter -> [(waited_for, reason)]
    for line in text.splitlines():
        tok = line.split(maxsplit=3)
        if len(tok) >= 3 and tok[0] == "EDGE":
            edges.setdefault(tok[1], []).append((tok[2], tok[3] if len(tok) > 3 else ""))
    return edges


def sccs(edges):
    """Tarjan's algorithm: groups of agents that can all reach each other."""
    nodes = sorted(set(edges) | {b for outs in edges.values() for b, _ in outs})
    index, low, on, stack, out, n = {}, {}, set(), [], [], [0]

    def visit(v):
        index[v] = low[v] = n[0]
        n[0] += 1
        stack.append(v)
        on.add(v)
        for w, _ in edges.get(v, []):
            if w not in index:
                visit(w)
                low[v] = min(low[v], low[w])
            elif w in on:
                low[v] = min(low[v], index[w])
        if low[v] == index[v]:
            group = []
            while True:
                w = stack.pop()
                on.discard(w)
                group.append(w)
                if w == v:
                    break
            out.append(group)

    for v in nodes:
        if v not in index:
            visit(v)
    return nodes, out


def cycle_order(group, edges):
    """Walk one cycle inside a strongly connected group, starting at its first name."""
    start = min(group)
    path = [start]
    while True:
        nxt = next(w for w, _ in edges[path[-1]] if w in group)
        if nxt == start:
            return path + [start]
        if nxt in path:                           # a smaller loop inside the group
            return path[path.index(nxt):] + [nxt]
        path.append(nxt)


def analyse(edges):
    nodes, groups = sccs(edges)
    cycles = [g for g in groups if len(g) > 1 or any(w == g[0] for w, _ in edges.get(g[0], []))]
    in_cycle = {v: i for i, g in enumerate(cycles) for v in g}
    reach = {}                                    # agent -> the cycle it is stuck behind, if any

    def behind(v, seen=()):
        if v in in_cycle:
            return in_cycle[v]
        if v in reach:
            return reach[v]
        for w, _ in edges.get(v, []):
            if w not in seen:
                c = behind(w, seen + (v,))
                if c is not None:
                    reach[v] = c
                    return c
        reach[v] = None
        return None

    report = {"cycles": [], "behind": {}, "dead_ends": []}   # dead_ends: waiters behind no cycle
    for i, g in enumerate(cycles):
        report["cycles"].append(cycle_order(g, edges))
    for v in nodes:
        if v in in_cycle or v not in edges:
            continue
        c = behind(v)
        if c is not None:
            report["behind"].setdefault(c, []).append(v)
        else:
            report["dead_ends"].append(v)
    return report


def show(edges, report):
    print(f"{sum(len(o) for o in edges.values())} waits between {len(set(edges) | {b for o in edges.values() for b, _ in o})} agents")
    for i, path in enumerate(report["cycles"], 1):
        print(f"cycle {i} ({len(path) - 1} agents): {' -> '.join(path)}")
        for a, b in zip(path, path[1:]):
            print(f"  {a} waits for {b}: " + next(r for w, r in edges[a] if w == b))
        if report["behind"].get(i - 1):
            print(f"  blocked behind it: {', '.join(report['behind'][i - 1])}")
    waited = {b for o in edges.values() for b, _ in o}
    for v in report["dead_ends"]:
        if v in waited:
            continue                              # printed as part of a longer chain
        path = [v]
        while True:
            onward = [w for w, _ in edges[path[-1]] if w in edges and w not in path]
            if not onward:
                break
            path.append(onward[0])
        ends = [w for w, _ in edges[path[-1]] if w not in edges]
        print(f"chain ends: {' -> '.join(path)} -> {' or '.join(ends)}, which wait for nothing (a lost event?)")
    if not report["cycles"]:
        print("no cycle: not a deadlock")


def main():
    if len(sys.argv) > 1:
        text = sys.stdin.read() if sys.argv[1] == "-" else open(sys.argv[1]).read()
        edges = parse(text)
        show(edges, analyse(edges))
        return
    edges = parse(RING4_SEED1)
    report = analyse(edges)
    show(edges, report)
    assert report["cycles"] == [["buf0", "buf1", "buf2", "buf3", "buf0"]], report
    assert sorted(report["behind"][0]) == ["host0", "host1", "host2", "host3"], report
    print("PASS: one 4-agent cycle, 4 hosts blocked behind it")


if __name__ == "__main__":
    main()