ZZZ Digital Lab

Back to WaitLens

waitlens/core.py

"""Parse only the documented pidin default column layout. Never execute input.

Reference: https://www.qnx.com/developers/docs/8.0/com.qnx.doc.neutrino.utilities/topic/p/pidin.html
SEND/REPLY identify a destination process, not a destination thread.
"""

from collections import Counter, defaultdict
from dataclasses import asdict, dataclass
import hashlib
import re

PIDIN_URL = "https://www.qnx.com/developers/docs/8.0/com.qnx.doc.neutrino.utilities/topic/p/pidin.html"
CAUTION = ("pidin queries processes sequentially; this is not an atomic snapshot. "
           "Process-level cycle candidates do not prove deadlock. Destination threads "
           "and timing guarantees cannot be inferred. PID/TID reuse can affect comparisons.")
STATES = set("BARRIER CONDVAR DEAD INTR JOIN MQ_RECEIVE MQ_SEND MUTEX NANOSLEEP READY "
             "RECEIVE REPLY RUNNING RWLOCK_READ RWLOCK_WRITE SEM SEND SIGSUSPEND "
             "SIGWAITINFO STOPPED WAITCTX WAITPAGE WAITTHREAD STACK WAITPROCESS".split())
ROW = re.compile(r"^\s*(\d+)\s+(\d+)\s+(.+?)\s+(\d+)([A-Za-z])\s+([A-Z_]+)(?:\s+(.*?))?\s*$")
ZOMBIE = re.compile(r"^\s*(\d+)\s+\(Zombie\)\s*$")


class InputError(ValueError):
    """Input is incomplete, unsupported, or ambiguous."""


@dataclass(frozen=True)
class Thread:
    pid: int
    tid: int
    name: str
    priority: int
    policy: str
    state: str
    blocked: str
    line: int

    @property
    def key(self):
        return f"{self.pid}:{self.tid}"


def parse(text):
    """One pidin invocation only; reject repeated headers/duplicate threads.

    Accept CRLF, a UTF-8 BOM, names containing spaces, and explicit custom
    formatting with the same six columns. Do not guess layouts for pidin mem,
    threads, -v, or -F %I. Return line-numbered errors instead of partial success.
    """
    threads, zombies, errors, seen = [], [], [], set()
    headers = 0
    for line_no, raw in enumerate(text.lstrip("\ufeff").splitlines(), 1):
        line = raw.strip()
        if not line:
            continue
        if line.split() == ["pid", "tid", "name", "prio", "STATE", "Blocked"]:
            headers += 1
            if headers > 1 or threads or zombies:
                errors.append(f"line {line_no}: multiple snapshots or misplaced header")
            continue
        zombie = ZOMBIE.fullmatch(raw)
        if zombie:
            zombies.append(int(zombie[1]))
            continue
        match = ROW.fullmatch(raw)
        if not match:
            errors.append(f"line {line_no}: unsupported row; use one non-verbose pidin snapshot")
            continue
        pid, tid, name, priority, policy, state, blocked = match.groups()
        thread = Thread(int(pid), int(tid), name, int(priority), policy, state, blocked or "", line_no)
        if thread.pid < 1 or thread.tid < 1 or not 0 <= thread.priority <= 255:
            errors.append(f"line {line_no}: invalid PID, TID, or priority")
        if state not in STATES:
            errors.append(f"line {line_no}: unknown state {state}")
        if thread.key in seen:
            errors.append(f"line {line_no}: duplicate thread {thread.key}; split loop output first")
        seen.add(thread.key)
        if state in {"SEND", "REPLY"} and not re.fullmatch(r"[1-9]\d*", thread.blocked):
            errors.append(f"line {line_no}: SEND/REPLY needs a plain destination PID; omit -v")
        threads.append(thread)
    if not threads and not zombies:
        errors.append("no thread or zombie rows; an empty capture is not a healthy system")
    if len(set(zombies)) != len(zombies) or set(zombies) & {t.pid for t in threads}:
        errors.append("duplicate zombie or PID present as both live and zombie")
    if errors:
        raise InputError("\n".join(errors))
    return threads, sorted(zombies)


def cycle_components(edges):
    """Iterative Kosaraju SCC; linear work and no Python recursion limit."""
    graph, reverse = defaultdict(set), defaultdict(set)
    for edge in edges:
        src, dst = edge["source_pid"], edge["destination_pid"]
        graph[src].add(dst)
        graph[dst]
        reverse[dst].add(src)
        reverse[src]
    visited, order = set(), []
    for root in sorted(graph):
        if root in visited:
            continue
        stack = [(root, False)]
        while stack:
            node, expanded = stack.pop()
            if expanded:
                order.append(node)
            elif node not in visited:
                visited.add(node)
                stack.append((node, True))
                stack.extend((n, False) for n in sorted(graph[node], reverse=True) if n not in visited)
    visited, components = set(), []
    for root in reversed(order):
        if root in visited:
            continue
        stack, component = [root], []
        visited.add(root)
        while stack:
            node = stack.pop()
            component.append(node)
            for nxt in sorted(reverse[node]):
                if nxt not in visited:
                    visited.add(nxt)
                    stack.append(nxt)
        if len(component) > 1 or root in graph[root]:
            components.append(sorted(component))
    return sorted(components)


def analyze(text, *, provenance="unspecified", label="snapshot"):
    threads, zombies = parse(text)
    pids = {t.pid for t in threads}
    edges = [{"source_pid": t.pid, "source_tid": t.tid,
              "destination_pid": int(t.blocked), "state": t.state,
              "destination_observed": int(t.blocked) in pids, "line": t.line}
             for t in threads if t.state in {"SEND", "REPLY"}]
    warnings = []
    missing = sorted({e["destination_pid"] for e in edges if not e["destination_observed"]})
    if missing:
        warnings.append("Destination PIDs absent from capture: " + ", ".join(map(str, missing))
                        + ". Filtering, permissions, or process exit may explain this.")
    if zombies:
        warnings.append("Zombie rows have no thread state and are excluded from IPC edges.")
    return {"schema_version": 1, "label": label, "provenance": provenance,
            "authenticity": "Input provenance is supplied by the caller, not independently verified.",
            "input_sha256": hashlib.sha256(text.encode("utf-8")).hexdigest(),
            "qnx_reference": PIDIN_URL, "caution": CAUTION,
            "summary": {"processes": len(pids), "threads": len(threads),
                        "ipc_waits": len(edges), "zombies": len(zombies),
                        "states": dict(sorted(Counter(t.state for t in threads).items()))},
            "threads": [asdict(t) for t in sorted(threads, key=lambda t: (t.pid, t.tid))],
            "edges": sorted(edges, key=lambda e: (e["source_pid"], e["source_tid"])),
            "cycle_candidates": cycle_components(edges), "zombie_pids": zombies,
            "warnings": warnings}


def compare(before, after):
    """Compare observed identities only; persistence is not a duration measure."""
    left = {(t["pid"], t["tid"]): t for t in before["threads"]}
    right = {(t["pid"], t["tid"]): t for t in after["threads"]}
    changes = []
    for key in sorted(left.keys() | right.keys()):
        a, b = left.get(key), right.get(key)
        if a is None:
            kind = "appeared"
        elif b is None:
            kind = "disappeared"
        elif a["name"] != b["name"]:
            kind = "identity-changed"
        elif (a["state"], a["blocked"], a["priority"], a["policy"]) != (b["state"], b["blocked"], b["priority"], b["policy"]):
            kind = "changed"
        else:
            continue
        changes.append({"pid": key[0], "tid": key[1], "kind": kind, "before": a, "after": b})
    return {"schema_version": 1, "kind": "comparison", "before": before, "after": after,
            "caution": CAUTION, "changes": changes}