garbage.c

  1// SPDX-License-Identifier: GPL-2.0-or-later
  2/*
  3 * NET3:	Garbage Collector For AF_UNIX sockets
  4 *
  5 * Garbage Collector:
  6 *	Copyright (C) Barak A. Pearlmutter.
  7 *
  8 * Chopped about by Alan Cox 22/3/96 to make it fit the AF_UNIX socket problem.
  9 * If it doesn't work blame me, it worked when Barak sent it.
 10 *
 11 * Assumptions:
 12 *
 13 *  - object w/ a bit
 14 *  - free list
 15 *
 16 * Current optimizations:
 17 *
 18 *  - explicit stack instead of recursion
 19 *  - tail recurse on first born instead of immediate push/pop
 20 *  - we gather the stuff that should not be killed into tree
 21 *    and stack is just a path from root to the current pointer.
 22 *
 23 *  Future optimizations:
 24 *
 25 *  - don't just push entire root set; process in place
 26 *
 27 *  Fixes:
 28 *	Alan Cox	07 Sept	1997	Vmalloc internal stack as needed.
 29 *					Cope with changing max_files.
 30 *	Al Viro		11 Oct 1998
 31 *		Graph may have cycles. That is, we can send the descriptor
 32 *		of foo to bar and vice versa. Current code chokes on that.
 33 *		Fix: move SCM_RIGHTS ones into the separate list and then
 34 *		skb_free() them all instead of doing explicit fput's.
 35 *		Another problem: since fput() may block somebody may
 36 *		create a new unix_socket when we are in the middle of sweep
 37 *		phase. Fix: revert the logic wrt MARKED. Mark everything
 38 *		upon the beginning and unmark non-junk ones.
 39 *
 40 *		[12 Oct 1998] AAARGH! New code purges all SCM_RIGHTS
 41 *		sent to connect()'ed but still not accept()'ed sockets.
 42 *		Fixed. Old code had slightly different problem here:
 43 *		extra fput() in situation when we passed the descriptor via
 44 *		such socket and closed it (descriptor). That would happen on
 45 *		each unix_gc() until the accept(). Since the struct file in
 46 *		question would go to the free list and might be reused...
 47 *		That might be the reason of random oopses on filp_close()
 48 *		in unrelated processes.
 49 *
 50 *	AV		28 Feb 1999
 51 *		Kill the explicit allocation of stack. Now we keep the tree
 52 *		with root in dummy + pointer (gc_current) to one of the nodes.
 53 *		Stack is represented as path from gc_current to dummy. Unmark
 54 *		now means "add to tree". Push == "make it a son of gc_current".
 55 *		Pop == "move gc_current to parent". We keep only pointers to
 56 *		parents (->gc_tree).
 57 *	AV		1 Mar 1999
 58 *		Damn. Added missing check for ->dead in listen queues scanning.
 59 *
 60 *	Miklos Szeredi 25 Jun 2007
 61 *		Reimplement with a cycle collecting algorithm. This should
 62 *		solve several problems with the previous code, like being racy
 63 *		wrt receive and holding up unrelated socket operations.
 64 */
 65
 66#include <linux/fs.h>
 67#include <linux/list.h>
 68#include <linux/skbuff.h>
 69#include <linux/socket.h>
 70#include <linux/workqueue.h>
 71#include <net/af_unix.h>
 72#include <net/scm.h>
 73#include <net/tcp_states.h>
 74
 75#include "af_unix.h"
 76
 77struct unix_vertex {
 78	struct list_head edges;
 79	struct list_head entry;
 80	struct list_head scc_entry;
 81	unsigned long out_degree;
 82	unsigned long index;
 83	unsigned long scc_index;
 84};
 85
 86struct unix_edge {
 87	struct unix_sock *predecessor;
 88	struct unix_sock *successor;
 89	struct list_head vertex_entry;
 90	struct list_head stack_entry;
 91};
 92
 93struct unix_sock *unix_get_socket(struct file *filp)
 94{
 95	struct inode *inode = file_inode(filp);
 96
 97	/* Socket ? */
 98	if (S_ISSOCK(inode->i_mode) && !(filp->f_mode & FMODE_PATH)) {
 99		struct socket *sock = SOCKET_I(inode);
100		const struct proto_ops *ops;
101		struct sock *sk = sock->sk;
102
103		ops = READ_ONCE(sock->ops);
104
105		/* PF_UNIX ? */
106		if (sk && ops && ops->family == PF_UNIX)
107			return unix_sk(sk);
108	}
109
110	return NULL;
111}
112
113static struct unix_vertex *unix_edge_successor(struct unix_edge *edge)
114{
115	/* If an embryo socket has a fd,
116	 * the listener indirectly holds the fd's refcnt.
117	 */
118	if (edge->successor->listener)
119		return unix_sk(edge->successor->listener)->vertex;
120
121	return edge->successor->vertex;
122}
123
124enum {
125	UNIX_GRAPH_NOT_CYCLIC,
126	UNIX_GRAPH_MAYBE_CYCLIC,
127	UNIX_GRAPH_CYCLIC,
128};
129
130static unsigned char unix_graph_state;
131
132static void unix_update_graph(struct unix_vertex *vertex)
133{
134	/* If the receiver socket is not inflight, no cyclic
135	 * reference could be formed.
136	 */
137	if (!vertex)
138		return;
139
140	WRITE_ONCE(unix_graph_state, UNIX_GRAPH_MAYBE_CYCLIC);
141}
142
143static LIST_HEAD(unix_unvisited_vertices);
144
145enum unix_vertex_index {
146	UNIX_VERTEX_INDEX_MARK1,
147	UNIX_VERTEX_INDEX_MARK2,
148	UNIX_VERTEX_INDEX_START,
149};
150
151static unsigned long unix_vertex_unvisited_index = UNIX_VERTEX_INDEX_MARK1;
152static unsigned long unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START;
153
154static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
155{
156	struct unix_vertex *vertex = edge->predecessor->vertex;
157
158	if (!vertex) {
159		vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry);
160		vertex->index = unix_vertex_unvisited_index;
161		vertex->scc_index = ++unix_vertex_max_scc_index;
162		vertex->out_degree = 0;
163		INIT_LIST_HEAD(&vertex->edges);
164		INIT_LIST_HEAD(&vertex->scc_entry);
165
166		list_move_tail(&vertex->entry, &unix_unvisited_vertices);
167		edge->predecessor->vertex = vertex;
168	}
169
170	vertex->out_degree++;
171	list_add_tail(&edge->vertex_entry, &vertex->edges);
172
173	unix_update_graph(unix_edge_successor(edge));
174}
175
176static void unix_del_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
177{
178	struct unix_vertex *vertex = edge->predecessor->vertex;
179
180	if (!fpl->dead)
181		unix_update_graph(unix_edge_successor(edge));
182
183	list_del(&edge->vertex_entry);
184	vertex->out_degree--;
185
186	if (!vertex->out_degree) {
187		edge->predecessor->vertex = NULL;
188		list_move_tail(&vertex->entry, &fpl->vertices);
189	}
190}
191
192static void unix_free_vertices(struct scm_fp_list *fpl)
193{
194	struct unix_vertex *vertex, *next_vertex;
195
196	list_for_each_entry_safe(vertex, next_vertex, &fpl->vertices, entry) {
197		list_del(&vertex->entry);
198		kfree(vertex);
199	}
200}
201
202static __cacheline_aligned_in_smp DEFINE_SPINLOCK(unix_gc_lock);
203
204void unix_add_edges(struct scm_fp_list *fpl, struct unix_sock *receiver)
205{
206	int i = 0, j = 0;
207
208	spin_lock(&unix_gc_lock);
209
210	if (!fpl->count_unix)
211		goto out;
212
213	do {
214		struct unix_sock *inflight = unix_get_socket(fpl->fp[j++]);
215		struct unix_edge *edge;
216
217		if (!inflight)
218			continue;
219
220		edge = fpl->edges + i++;
221		edge->predecessor = inflight;
222		edge->successor = receiver;
223
224		unix_add_edge(fpl, edge);
225	} while (i < fpl->count_unix);
226
227	receiver->scm_stat.nr_unix_fds += fpl->count_unix;
228out:
229	WRITE_ONCE(fpl->user->unix_inflight, fpl->user->unix_inflight + fpl->count);
230
231	spin_unlock(&unix_gc_lock);
232
233	fpl->inflight = true;
234
235	unix_free_vertices(fpl);
236}
237
238void unix_del_edges(struct scm_fp_list *fpl)
239{
240	struct unix_sock *receiver;
241	int i = 0;
242
243	spin_lock(&unix_gc_lock);
244
245	if (!fpl->count_unix)
246		goto out;
247
248	do {
249		struct unix_edge *edge = fpl->edges + i++;
250
251		unix_del_edge(fpl, edge);
252	} while (i < fpl->count_unix);
253
254	if (!fpl->dead) {
255		receiver = fpl->edges[0].successor;
256		receiver->scm_stat.nr_unix_fds -= fpl->count_unix;
257	}
258out:
259	WRITE_ONCE(fpl->user->unix_inflight, fpl->user->unix_inflight - fpl->count);
260
261	spin_unlock(&unix_gc_lock);
262
263	fpl->inflight = false;
264}
265
266void unix_update_edges(struct unix_sock *receiver)
267{
268	/* nr_unix_fds is only updated under unix_state_lock().
269	 * If it's 0 here, the embryo socket is not part of the
270	 * inflight graph, and GC will not see it, so no lock needed.
271	 */
272	if (!receiver->scm_stat.nr_unix_fds) {
273		receiver->listener = NULL;
274	} else {
275		spin_lock(&unix_gc_lock);
276		unix_update_graph(unix_sk(receiver->listener)->vertex);
277		receiver->listener = NULL;
278		spin_unlock(&unix_gc_lock);
279	}
280}
281
282int unix_prepare_fpl(struct scm_fp_list *fpl)
283{
284	struct unix_vertex *vertex;
285	int i;
286
287	if (!fpl->count_unix)
288		return 0;
289
290	for (i = 0; i < fpl->count_unix; i++) {
291		vertex = kmalloc(sizeof(*vertex), GFP_KERNEL);
292		if (!vertex)
293			goto err;
294
295		list_add(&vertex->entry, &fpl->vertices);
296	}
297
298	fpl->edges = kvmalloc_array(fpl->count_unix, sizeof(*fpl->edges),
299				    GFP_KERNEL_ACCOUNT);
300	if (!fpl->edges)
301		goto err;
302
303	unix_schedule_gc(fpl->user);
304
305	return 0;
306
307err:
308	unix_free_vertices(fpl);
309	return -ENOMEM;
310}
311
312void unix_destroy_fpl(struct scm_fp_list *fpl)
313{
314	if (fpl->inflight)
315		unix_del_edges(fpl);
316
317	kvfree(fpl->edges);
318	unix_free_vertices(fpl);
319}
320
321static bool gc_in_progress;
322static seqcount_t unix_peek_seq = SEQCNT_ZERO(unix_peek_seq);
323
324void unix_peek_fpl(struct scm_fp_list *fpl)
325{
326	static DEFINE_SPINLOCK(unix_peek_lock);
327
328	if (!fpl || !fpl->count_unix)
329		return;
330
331	if (!READ_ONCE(gc_in_progress))
332		return;
333
334	/* Invalidate the final refcnt check in unix_vertex_dead(). */
335	spin_lock(&unix_peek_lock);
336	raw_write_seqcount_barrier(&unix_peek_seq);
337	spin_unlock(&unix_peek_lock);
338}
339
340static bool unix_vertex_dead(struct unix_vertex *vertex)
341{
342	struct unix_edge *edge;
343	struct unix_sock *u;
344	long total_ref;
345
346	list_for_each_entry(edge, &vertex->edges, vertex_entry) {
347		struct unix_vertex *next_vertex = unix_edge_successor(edge);
348
349		/* The vertex's fd can be received by a non-inflight socket. */
350		if (!next_vertex)
351			return false;
352
353		/* The vertex's fd can be received by an inflight socket in
354		 * another SCC.
355		 */
356		if (next_vertex->scc_index != vertex->scc_index)
357			return false;
358	}
359
360	/* No receiver exists out of the same SCC. */
361
362	edge = list_first_entry(&vertex->edges, typeof(*edge), vertex_entry);
363	u = edge->predecessor;
364	total_ref = file_count(u->sk.sk_socket->file);
365
366	/* If not close()d, total_ref > out_degree. */
367	if (total_ref != vertex->out_degree)
368		return false;
369
370	return true;
371}
372
373static LIST_HEAD(unix_visited_vertices);
374static unsigned long unix_vertex_grouped_index = UNIX_VERTEX_INDEX_MARK2;
375
376static bool unix_scc_dead(struct list_head *scc, bool fast)
377{
378	struct unix_vertex *vertex;
379	bool scc_dead = true;
380	unsigned int seq;
381
382	seq = read_seqcount_begin(&unix_peek_seq);
383
384	list_for_each_entry_reverse(vertex, scc, scc_entry) {
385		/* Don't restart DFS from this vertex. */
386		list_move_tail(&vertex->entry, &unix_visited_vertices);
387
388		/* Mark vertex as off-stack for __unix_walk_scc(). */
389		if (!fast)
390			vertex->index = unix_vertex_grouped_index;
391
392		if (scc_dead)
393			scc_dead = unix_vertex_dead(vertex);
394	}
395
396	/* If MSG_PEEK intervened, defer this SCC to the next round. */
397	if (read_seqcount_retry(&unix_peek_seq, seq))
398		return false;
399
400	return scc_dead;
401}
402
403static void unix_collect_skb(struct list_head *scc, struct sk_buff_head *hitlist)
404{
405	struct unix_vertex *vertex;
406
407	list_for_each_entry_reverse(vertex, scc, scc_entry) {
408		struct sk_buff_head *queue;
409		struct unix_edge *edge;
410		struct unix_sock *u;
411
412		edge = list_first_entry(&vertex->edges, typeof(*edge), vertex_entry);
413		u = edge->predecessor;
414		queue = &u->sk.sk_receive_queue;
415
416		spin_lock(&queue->lock);
417
418		if (u->sk.sk_state == TCP_LISTEN) {
419			struct sk_buff *skb;
420
421			skb_queue_walk(queue, skb) {
422				struct sk_buff_head *embryo_queue = &skb->sk->sk_receive_queue;
423
424				spin_lock(&embryo_queue->lock);
425				skb_queue_splice_init(embryo_queue, hitlist);
426				spin_unlock(&embryo_queue->lock);
427			}
428		} else {
429			skb_queue_splice_init(queue, hitlist);
430		}
431
432		spin_unlock(&queue->lock);
433	}
434}
435
436static bool unix_scc_cyclic(struct list_head *scc)
437{
438	struct unix_vertex *vertex;
439	struct unix_edge *edge;
440
441	/* SCC containing multiple vertices ? */
442	if (!list_is_singular(scc))
443		return true;
444
445	vertex = list_first_entry(scc, typeof(*vertex), scc_entry);
446
447	/* Self-reference or a embryo-listener circle ? */
448	list_for_each_entry(edge, &vertex->edges, vertex_entry) {
449		if (unix_edge_successor(edge) == vertex)
450			return true;
451	}
452
453	return false;
454}
455
456static unsigned long __unix_walk_scc(struct unix_vertex *vertex,
457				     unsigned long *last_index,
458				     struct sk_buff_head *hitlist)
459{
460	unsigned long cyclic_sccs = 0;
461	LIST_HEAD(vertex_stack);
462	struct unix_edge *edge;
463	LIST_HEAD(edge_stack);
464
465next_vertex:
466	/* Push vertex to vertex_stack and mark it as on-stack
467	 * (index >= UNIX_VERTEX_INDEX_START).
468	 * The vertex will be popped when finalising SCC later.
469	 */
470	list_add(&vertex->scc_entry, &vertex_stack);
471
472	vertex->index = *last_index;
473	vertex->scc_index = *last_index;
474	(*last_index)++;
475
476	/* Explore neighbour vertices (receivers of the current vertex's fd). */
477	list_for_each_entry(edge, &vertex->edges, vertex_entry) {
478		struct unix_vertex *next_vertex = unix_edge_successor(edge);
479
480		if (!next_vertex)
481			continue;
482
483		if (next_vertex->index == unix_vertex_unvisited_index) {
484			/* Iterative deepening depth first search
485			 *
486			 *   1. Push a forward edge to edge_stack and set
487			 *      the successor to vertex for the next iteration.
488			 */
489			list_add(&edge->stack_entry, &edge_stack);
490
491			vertex = next_vertex;
492			goto next_vertex;
493
494			/*   2. Pop the edge directed to the current vertex
495			 *      and restore the ancestor for backtracking.
496			 */
497prev_vertex:
498			edge = list_first_entry(&edge_stack, typeof(*edge), stack_entry);
499			list_del_init(&edge->stack_entry);
500
501			next_vertex = vertex;
502			vertex = edge->predecessor->vertex;
503
504			/* If the successor has a smaller scc_index, two vertices
505			 * are in the same SCC, so propagate the smaller scc_index
506			 * to skip SCC finalisation.
507			 */
508			vertex->scc_index = min(vertex->scc_index, next_vertex->scc_index);
509		} else if (next_vertex->index != unix_vertex_grouped_index) {
510			/* Loop detected by a back/cross edge.
511			 *
512			 * The successor is on vertex_stack, so two vertices are in
513			 * the same SCC.  If the successor has a smaller *scc_index*,
514			 * propagate it to skip SCC finalisation.
515			 */
516			vertex->scc_index = min(vertex->scc_index, next_vertex->scc_index);
517		} else {
518			/* The successor was already grouped as another SCC */
519		}
520	}
521
522	if (vertex->index == vertex->scc_index) {
523		struct list_head scc;
524
525		/* SCC finalised.
526		 *
527		 * If the scc_index was not updated, all the vertices above on
528		 * vertex_stack are in the same SCC.  Group them using scc_entry.
529		 */
530		__list_cut_position(&scc, &vertex_stack, &vertex->scc_entry);
531
532		if (unix_scc_dead(&scc, false)) {
533			unix_collect_skb(&scc, hitlist);
534		} else {
535			if (unix_vertex_max_scc_index < vertex->scc_index)
536				unix_vertex_max_scc_index = vertex->scc_index;
537
538			if (unix_scc_cyclic(&scc))
539				cyclic_sccs++;
540		}
541
542		list_del(&scc);
543	}
544
545	/* Need backtracking ? */
546	if (!list_empty(&edge_stack))
547		goto prev_vertex;
548
549	return cyclic_sccs;
550}
551
552static unsigned long unix_graph_cyclic_sccs;
553
554static void unix_walk_scc(struct sk_buff_head *hitlist)
555{
556	unsigned long last_index = UNIX_VERTEX_INDEX_START;
557	unsigned long cyclic_sccs = 0;
558
559	unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START;
560
561	/* Visit every vertex exactly once.
562	 * __unix_walk_scc() moves visited vertices to unix_visited_vertices.
563	 */
564	while (!list_empty(&unix_unvisited_vertices)) {
565		struct unix_vertex *vertex;
566
567		vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
568		cyclic_sccs += __unix_walk_scc(vertex, &last_index, hitlist);
569	}
570
571	list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
572	swap(unix_vertex_unvisited_index, unix_vertex_grouped_index);
573
574	WRITE_ONCE(unix_graph_cyclic_sccs, cyclic_sccs);
575	WRITE_ONCE(unix_graph_state,
576		   cyclic_sccs ? UNIX_GRAPH_CYCLIC : UNIX_GRAPH_NOT_CYCLIC);
577}
578
579static void unix_walk_scc_fast(struct sk_buff_head *hitlist)
580{
581	unsigned long cyclic_sccs = unix_graph_cyclic_sccs;
582
583	while (!list_empty(&unix_unvisited_vertices)) {
584		struct unix_vertex *vertex;
585		struct list_head scc;
586
587		vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
588		list_add(&scc, &vertex->scc_entry);
589
590		if (unix_scc_dead(&scc, true)) {
591			cyclic_sccs--;
592			unix_collect_skb(&scc, hitlist);
593		}
594
595		list_del(&scc);
596	}
597
598	list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
599
600	WRITE_ONCE(unix_graph_cyclic_sccs, cyclic_sccs);
601	WRITE_ONCE(unix_graph_state,
602		   cyclic_sccs ? UNIX_GRAPH_CYCLIC : UNIX_GRAPH_NOT_CYCLIC);
603}
604
605static void unix_gc(struct work_struct *work)
606{
607	struct sk_buff_head hitlist;
608	struct sk_buff *skb;
609
610	spin_lock(&unix_gc_lock);
611
612	if (unix_graph_state == UNIX_GRAPH_NOT_CYCLIC) {
613		spin_unlock(&unix_gc_lock);
614		goto skip_gc;
615	}
616
617	__skb_queue_head_init(&hitlist);
618
619	if (unix_graph_state == UNIX_GRAPH_CYCLIC)
620		unix_walk_scc_fast(&hitlist);
621	else
622		unix_walk_scc(&hitlist);
623
624	spin_unlock(&unix_gc_lock);
625
626	skb_queue_walk(&hitlist, skb) {
627		if (UNIXCB(skb).fp)
628			UNIXCB(skb).fp->dead = true;
629	}
630
631	__skb_queue_purge_reason(&hitlist, SKB_DROP_REASON_SOCKET_CLOSE);
632skip_gc:
633	WRITE_ONCE(gc_in_progress, false);
634}
635
636static DECLARE_WORK(unix_gc_work, unix_gc);
637
638#define UNIX_INFLIGHT_SANE_USER		(SCM_MAX_FD * 8)
639
640void unix_schedule_gc(struct user_struct *user)
641{
642	if (READ_ONCE(unix_graph_state) == UNIX_GRAPH_NOT_CYCLIC)
643		return;
644
645	/* Penalise users who want to send AF_UNIX sockets
646	 * but whose sockets have not been received yet.
647	 */
648	if (user &&
649	    READ_ONCE(user->unix_inflight) < UNIX_INFLIGHT_SANE_USER)
650		return;
651
652	if (!READ_ONCE(gc_in_progress)) {
653		WRITE_ONCE(gc_in_progress, true);
654		queue_work(system_dfl_wq, &unix_gc_work);
655	}
656
657	if (user && READ_ONCE(unix_graph_cyclic_sccs))
658		flush_work(&unix_gc_work);
659}