Unix GC Remastered – Moe's VR blog

IntroductionThe AF_UNIX garbage collector is an interesting piece of the kernel. It exists because sockets can be sent with SCM_RIGHTS but they can become unreachable from user-space while still being kept alive by the kernel, which is not memory efficient; in this situation, the garbage collector intervenes to free them. Not long ago, the subsystem was rewritten from scratch on top of a graph/Strongly-Connected-Components model; but it is still bug prone. This post walks the rewrite end-to-end, and discusses a Use-After-Free bug.AF_UNIX Garbage Collector — BackgroundA per-subsystem garbage collector is responsible for reclaiming kernel objects that can no longer be reached through user-space handles. For AF_UNIX, the entry point is unix_gc():static DECLARE_WORK(unix_gc_work, __unix_gc);

void unix_gc(void) { WRITE_ONCE(gc_in_progress, true); queue_work(system_dfl_wq, &unix_gc_work); } Its real body is __unix_gc():static void __unix_gc(struct work_struct *work) { struct sk_buff_head hitlist; struct sk_buff *skb;

spin_lock(&unix_gc_lock);

if (!unix_graph_maybe_cyclic) { spin_unlock(&unix_gc_lock); goto skip_gc; }

__skb_queue_head_init(&hitlist);

if (unix_graph_grouped) unix_walk_scc_fast(&hitlist); else unix_walk_scc(&hitlist);

spin_unlock(&unix_gc_lock);

skb_queue_walk(&hitlist, skb) { if (UNIXCB(skb).fp) UNIXCB(skb).fp->dead = true; }

__skb_queue_purge_reason(&hitlist, SKB_DROP_REASON_SOCKET_CLOSE); skip_gc: WRITE_ONCE(gc_in_progress, false); } The unix_sock structurestruct

unix_sock { /* WARNING: sk has to be the first member */ struct sock sk; /* inheritance */ struct unix_address *addr; /* bound name */ struct path path; /* filesystem path if bound */ struct mutex iolock, bindlock; struct sock *peer; /* connected peer */ struct list_head link; atomic_long_t inflight; /* [1] SCM_RIGHTS fd count */ /* ... */ struct sk_buff *oob_skb; }; The critical field for GC is inflight ([1]). A socket is “in flight” when its struct file * is riding as SCM_RIGHTS payload — sent by process A, not yet accepted by process B. Each time it is sent, inflight is incremented; each time it is received, inflight is decremented. The GC is looking for sockets for which file_count == inflight: the only remaining references are the ones trapped in other sockets’ receive queues, i.e. no user-space handle can ever reach them again.The LWN “AF_UNIX GC rework” article puts it more concisely:Let’s say we send a fd of AF_UNIX socket A to B and vice versa and close() both sockets. When created, each socket’s struct file initially has one reference. After the fd exchange, both refcounts are bumped up to 2. Then, close() decreases both to 1. From this point on, no one can touch the file/socket. However, the struct file has one refcount and thus never calls the release() function of the AF_UNIX socket. That’s why we need to track all inflight AF_UNIX sockets and run garbage collection.The kernel maintains a global unix_tot_inflight counter, incremented on every inflight transition and decremented on every accept.When GC runsThere are two triggers:Too many inflight sockets:if (READ_ONCE(unix_tot_inflight) > UNIX_INFLIGHT_TRIGGER_GC && !

READ_ONCE(gc_in_progress)) unix_gc(); (UNIX_INFLIGHT_TRIGGER_GC == 16000.)A socket close, if anything is inflight:static const struct proto_ops unix_stream_ops = { .family = PF_UNIX, .owner = THIS_MODULE, .release = unix_release, /* ... */ };

static void unix_release_sock(struct sock *sk, int embrion) { /* ... */ if (READ_ONCE(unix_tot_inflight)) unix_gc(); } The Old GCThe pre-2024 collector is well described in the Google P0 post “The quantum state of Linux kernel garbage collection”, which covers both the algorithm and a 2021 Android in-the-wild exploit. That post is the recommended companion read; here is just the one-line summary: the old GC walked the inflight graph, marked cycles, and checked inflight != refcount to decide whether each cycle was collectable.Here’s a nice mermaid diagram: The New GCFrom the GC Rework announcement:[It] replaces the current GC implementation that locks each inflight socket’s receive queue and requires trickiness in other places. The new GC does not lock each socket’s queue to minimise its effect and tries to be lightweight if there is no cyclic reference or no update in the shape of the inflight fd graph.Graph representationEach inflight socket becomes a vertex; each backing struct file * carried in an SCM_RIGHTS cmsg becomes a directed edge (predecessor → successor).Example — send A to C, C to D, B to D. Three inflight sockets (A, B, C — not D), giving the graph:Tarjan’s algorithm then partitions this graph into strongly connected components. Why SCCs? For any directed graph, any SCC of more than one vertex necessarily contains at least one cycle:A cycle is a necessary but not sufficient condition for a vertex to be collectable: collection requires the vertex to be inflight, and unreachable from user-space (file_count == out_degree). Sockets not in any cycle cannot possibly be mutually-pinning garbage, and are skipped.

How __unix_gc dispatchesstatic void __unix_gc(struct work_struct *work) { struct sk_buff_head hitlist; /* [2] final hit-list of skbs to free */ struct sk_buff *skb; /* ... */ __skb_queue_head_init(&hitlist); /* [2.5] */

if (!unix_graph_maybe_cyclic) { /* [3] fast bail */ spin_unlock(&unix_gc_lock); goto skip_gc; } /* ... */ } unix_graph_maybe_cyclic is flipped on whenever a new edge is added with both endpoints inflight:static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge) { struct unix_vertex *vertex = edge->predecessor->vertex;

if (!vertex) { vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry); vertex->index = unix_vertex_unvisited_index; /* ... */ }

vertex->out_degree++; list_add_tail(&edge->vertex_entry, &vertex->edges); unix_update_graph(unix_edge_successor(edge)); }

static void unix_update_graph(struct unix_vertex *vertex) { /* If the receiver socket is not inflight, no cyclic * reference could be formed. */ if (!vertex) return;

WRITE_ONCE(unix_graph_state, UNIX_GRAPH_MAYBE_CYCLIC); unix_graph_grouped = false; } Note that unix_update_graph() also resets unix_graph_grouped = false, forcing the next GC to rebuild SCCs from scratch.Dispatch between slow and fast paths:if (unix_graph_grouped) unix_walk_scc_fast(&hitlist); else unix_walk_scc(&hitlist); Slow path — unix_walk_scc()This is where SCCs are actually built:static void unix_walk_scc(struct sk_buff_head *hitlist) { unsigned long last_index = UNIX_VERTEX_INDEX_START;

unix_graph_maybe_cyclic = false; unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START;

while (!

list_empty(&unix_unvisited_vertices)) { struct unix_vertex *vertex; vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry); __unix_walk_scc(vertex, &last_index, hitlist); }

list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices); swap(unix_vertex_unvisited_index, unix_vertex_grouped_index);

unix_graph_grouped = true; } Indexing starts at UNIX_VERTEX_INDEX_START == 2. At the top of the walk the graph is assumed acyclic; the walk promotes it back to cyclic if and only if it actually finds a cycle.Complexity note. The outer while only iterates more than once when the graph is a forest of disconnected sub-graphs. For any weakly-connected graph G(V, E) a single iteration visits every vertex. End-to-end cost is O(|V| + |E|).Tarjan’s algorithmTarjan’s algorithm takes a directed graph and produces its SCCs. Each vertex ends up in exactly one SCC; vertices with no incoming or outgoing cycle form a trivial singleton SCC. The idea is a DFS where every vertex starts labelled (index, scc_index) = (k, k) for a monotonically increasing k, and then neighbours’ scc_index values are propagated back up the stack so that all vertices in a cycle converge on the smallest scc_index in that cycle.See the Wikipedia page for the formal write-up.Pseudocode, matching the kernel’s in-place iterative form:For each unvisited vertex v: __unix_walk_scc(v, last_index, hitlist)

__unix_walk_scc(v, last_index, hitlist): vertex_S, edge_S, edge |------------------------------------| next_vertex: vertex_S.push(v) v.index <- last_index v.scc_index <- last_index last_index += 1

for each edge e: (v, w) in the Graph: // w == e.successor if vertex w is not yet visited: edge_S.push(e: (v, w)) v

<- w goto next_vertex |------------------------------| -> prev_vertex: // returning from recursion edge = edge_S.pop() // backtrack w <- v v <- edge.predecessor.vertex v.scc_index = min(v.scc_index, w.scc_index) else if w is not in another SCC: v.scc_index = min(v.scc_index, w.scc_index) |-----------------------------------------------| if v.index == v.scc_index: scc <- {} scc_dead <- true

// vertex_S == [SCC(0)][SCC(1)][...][SCC(N)] // cut off [v ...] into `scc` scc <- [v ...]

while scc is not empty: u <- scc.pop() unix_visited_vertices.add(u) u.index <- unix_vertex_grouped_index if scc_dead: scc_dead <- unix_vertex_dead(v)

if scc_dead: unix_collect_skb(&scc, hitlist) else: if unix_vertex_max_scc_index < v.scc_index: unix_vertex_max_scc_index <- vertex.scc_index if not unix_graph_maybe_cyclic: unix_graph_maybe_cyclic <- unix_scc_cyclic(&scc) |-----------------------------------------------| if edge_stack is not empty goto prev_vertex Fast path — unix_walk_scc_fast()When the graph shape is unchanged since the last GC (unix_graph_grouped == true), the SCCs are reused as-is:static void unix_walk_scc_fast(struct sk_buff_head *hitlist) { unix_graph_maybe_cyclic = false;

while (!list_empty(&unix_unvisited_vertices)) { /* [4] */ struct unix_vertex *vertex; struct list_head scc; bool scc_dead = true;

vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry); list_add(&scc, &vertex->scc_entry);

list_for_each_entry_reverse(vertex,