projects/linux·blob master · refs

663 lines · 16.5 KiB

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 list_del(&vertex->scc_entry);
190 }
191}
192
193static void unix_free_vertices(struct scm_fp_list *fpl)
194{
195 struct unix_vertex *vertex, *next_vertex;
196
197 list_for_each_entry_safe(vertex, next_vertex, &fpl->vertices, entry) {
198 list_del(&vertex->entry);
199 kfree(vertex);
200 }
201}
202
203static __cacheline_aligned_in_smp DEFINE_SPINLOCK(unix_gc_lock);
204
205void unix_add_edges(struct scm_fp_list *fpl, struct unix_sock *receiver)
206{
207 int i = 0, j = 0;
208
209 spin_lock(&unix_gc_lock);
210
211 if (!fpl->count_unix)
212 goto out;
213
214 do {
215 struct unix_sock *inflight = unix_get_socket(fpl->fp[j++]);
216 struct unix_edge *edge;
217
218 if (!inflight)
219 continue;
220
221 edge = fpl->edges + i++;
222 edge->predecessor = inflight;
223 edge->successor = receiver;
224
225 unix_add_edge(fpl, edge);
226 } while (i < fpl->count_unix);
227
228 receiver->scm_stat.nr_unix_fds += fpl->count_unix;
229out:
230 WRITE_ONCE(fpl->user->unix_inflight, fpl->user->unix_inflight + fpl->count);
231
232 spin_unlock(&unix_gc_lock);
233
234 fpl->inflight = true;
235
236 unix_free_vertices(fpl);
237}
238
239void unix_del_edges(struct scm_fp_list *fpl)
240{
241 struct unix_sock *receiver;
242 int i = 0;
243
244 spin_lock(&unix_gc_lock);
245
246 if (!fpl->count_unix)
247 goto out;
248
249 do {
250 struct unix_edge *edge = fpl->edges + i++;
251
252 unix_del_edge(fpl, edge);
253 } while (i < fpl->count_unix);
254
255 if (!fpl->dead) {
256 receiver = fpl->edges[0].successor;
257 receiver->scm_stat.nr_unix_fds -= fpl->count_unix;
258 }
259out:
260 WRITE_ONCE(fpl->user->unix_inflight, fpl->user->unix_inflight - fpl->count);
261
262 spin_unlock(&unix_gc_lock);
263
264 fpl->inflight = false;
265}
266
267void unix_update_edges(struct unix_sock *receiver)
268{
269 /* nr_unix_fds is only updated under unix_state_lock().
270 * If it's 0 here, the embryo socket is not part of the
271 * inflight graph, and GC will not see it, so no lock needed.
272 */
273 if (!receiver->scm_stat.nr_unix_fds) {
274 receiver->listener = NULL;
275 } else {
276 spin_lock(&unix_gc_lock);
277 unix_update_graph(unix_sk(receiver->listener)->vertex);
278 receiver->listener = NULL;
279 spin_unlock(&unix_gc_lock);
280 }
281}
282
283int unix_prepare_fpl(struct scm_fp_list *fpl)
284{
285 struct unix_vertex *vertex;
286 int i;
287
288 if (!fpl->count_unix)
289 return 0;
290
291 for (i = 0; i < fpl->count_unix; i++) {
292 vertex = kmalloc_obj(*vertex);
293 if (!vertex)
294 goto err;
295
296 list_add(&vertex->entry, &fpl->vertices);
297 }
298
299 fpl->edges = kvmalloc_objs(*fpl->edges, fpl->count_unix,
300 GFP_KERNEL_ACCOUNT);
301 if (!fpl->edges)
302 goto err;
303
304 unix_schedule_gc(fpl->user);
305
306 return 0;
307
308err:
309 unix_free_vertices(fpl);
310 return -ENOMEM;
311}
312
313void unix_destroy_fpl(struct scm_fp_list *fpl)
314{
315 if (fpl->inflight)
316 unix_del_edges(fpl);
317
318 kvfree(fpl->edges);
319 unix_free_vertices(fpl);
320}
321
322static bool gc_in_progress;
323static seqcount_t unix_peek_seq = SEQCNT_ZERO(unix_peek_seq);
324
325void unix_peek_fpl(struct scm_fp_list *fpl)
326{
327 static DEFINE_SPINLOCK(unix_peek_lock);
328
329 if (!fpl || !fpl->count_unix)
330 return;
331
332 if (!READ_ONCE(gc_in_progress))
333 return;
334
335 /* Invalidate the final refcnt check in unix_vertex_dead(). */
336 spin_lock(&unix_peek_lock);
337 raw_write_seqcount_barrier(&unix_peek_seq);
338 spin_unlock(&unix_peek_lock);
339}
340
341static bool unix_vertex_dead(struct unix_vertex *vertex)
342{
343 struct unix_edge *edge;
344 struct unix_sock *u;
345 long total_ref;
346
347 list_for_each_entry(edge, &vertex->edges, vertex_entry) {
348 struct unix_vertex *next_vertex = unix_edge_successor(edge);
349
350 /* The vertex's fd can be received by a non-inflight socket. */
351 if (!next_vertex)
352 return false;
353
354 /* The vertex's fd can be received by an inflight socket in
355 * another SCC.
356 */
357 if (next_vertex->scc_index != vertex->scc_index)
358 return false;
359 }
360
361 /* No receiver exists out of the same SCC. */
362
363 edge = list_first_entry(&vertex->edges, typeof(*edge), vertex_entry);
364 u = edge->predecessor;
365 total_ref = file_count(u->sk.sk_socket->file);
366
367 /* If not close()d, total_ref > out_degree. */
368 if (total_ref != vertex->out_degree)
369 return false;
370
371 return true;
372}
373
374static LIST_HEAD(unix_visited_vertices);
375static unsigned long unix_vertex_grouped_index = UNIX_VERTEX_INDEX_MARK2;
376
377static bool unix_scc_dead(struct list_head *scc)
378{
379 struct unix_vertex *vertex;
380 bool scc_dead = true;
381 unsigned int seq;
382
383 seq = read_seqcount_begin(&unix_peek_seq);
384
385 list_for_each_entry_reverse(vertex, scc, scc_entry) {
386 /* Don't restart DFS from this vertex. */
387 list_move_tail(&vertex->entry, &unix_visited_vertices);
388
389 if (scc_dead)
390 scc_dead = unix_vertex_dead(vertex);
391 }
392
393 /* If MSG_PEEK intervened, defer this SCC to the next round. */
394 if (read_seqcount_retry(&unix_peek_seq, seq))
395 return false;
396
397 return scc_dead;
398}
399
400static void unix_collect_skb(struct list_head *scc, struct sk_buff_head *hitlist)
401{
402 struct unix_vertex *vertex;
403
404 list_for_each_entry_reverse(vertex, scc, scc_entry) {
405 struct sk_buff_head *queue;
406 struct unix_edge *edge;
407 struct unix_sock *u;
408
409 edge = list_first_entry(&vertex->edges, typeof(*edge), vertex_entry);
410 u = edge->predecessor;
411 queue = &u->sk.sk_receive_queue;
412
413 spin_lock(&queue->lock);
414
415 if (u->sk.sk_state == TCP_LISTEN) {
416 struct sk_buff *skb;
417
418 skb_queue_walk(queue, skb) {
419 struct sk_buff_head *embryo_queue = &skb->sk->sk_receive_queue;
420
421 spin_lock(&embryo_queue->lock);
422 skb_queue_splice_init(embryo_queue, hitlist);
423 spin_unlock(&embryo_queue->lock);
424 }
425 } else {
426 skb_queue_splice_init(queue, hitlist);
427 }
428
429 spin_unlock(&queue->lock);
430 }
431}
432
433static bool unix_scc_cyclic(struct list_head *scc)
434{
435 struct unix_vertex *vertex;
436 struct unix_edge *edge;
437
438 /* SCC containing multiple vertices ? */
439 if (!list_is_singular(scc))
440 return true;
441
442 vertex = list_first_entry(scc, typeof(*vertex), scc_entry);
443
444 /* Self-reference or a embryo-listener circle ? */
445 list_for_each_entry(edge, &vertex->edges, vertex_entry) {
446 if (unix_edge_successor(edge) == vertex)
447 return true;
448 }
449
450 return false;
451}
452
453static unsigned long __unix_walk_scc(struct unix_vertex *vertex,
454 unsigned long *last_index,
455 struct sk_buff_head *hitlist)
456{
457 unsigned long cyclic_sccs = 0;
458 LIST_HEAD(vertex_stack);
459 struct unix_edge *edge;
460 LIST_HEAD(edge_stack);
461
462next_vertex:
463 /* Push vertex to vertex_stack and mark it as on-stack
464 * (index >= UNIX_VERTEX_INDEX_START).
465 * The vertex will be popped when finalising SCC later.
466 */
467 list_add(&vertex->scc_entry, &vertex_stack);
468
469 vertex->index = *last_index;
470 vertex->scc_index = *last_index;
471 (*last_index)++;
472
473 /* Explore neighbour vertices (receivers of the current vertex's fd). */
474 list_for_each_entry(edge, &vertex->edges, vertex_entry) {
475 struct unix_vertex *next_vertex = unix_edge_successor(edge);
476
477 if (!next_vertex)
478 continue;
479
480 if (next_vertex->index == unix_vertex_unvisited_index) {
481 /* Iterative deepening depth first search
482 *
483 * 1. Push a forward edge to edge_stack and set
484 * the successor to vertex for the next iteration.
485 */
486 list_add(&edge->stack_entry, &edge_stack);
487
488 vertex = next_vertex;
489 goto next_vertex;
490
491 /* 2. Pop the edge directed to the current vertex
492 * and restore the ancestor for backtracking.
493 */
494prev_vertex:
495 edge = list_first_entry(&edge_stack, typeof(*edge), stack_entry);
496 list_del_init(&edge->stack_entry);
497
498 next_vertex = vertex;
499 vertex = edge->predecessor->vertex;
500
501 /* If the successor has a smaller scc_index, two vertices
502 * are in the same SCC, so propagate the smaller scc_index
503 * to skip SCC finalisation.
504 */
505 vertex->scc_index = min(vertex->scc_index, next_vertex->scc_index);
506 } else if (next_vertex->index != unix_vertex_grouped_index) {
507 /* Loop detected by a back/cross edge.
508 *
509 * The successor is on vertex_stack, so two vertices are in
510 * the same SCC. If the successor has a smaller *scc_index*,
511 * propagate it to skip SCC finalisation.
512 */
513 vertex->scc_index = min(vertex->scc_index, next_vertex->scc_index);
514 } else {
515 /* The successor was already grouped as another SCC */
516 }
517 }
518
519 if (vertex->index == vertex->scc_index) {
520 struct unix_vertex *v;
521 struct list_head scc;
522
523 /* SCC finalised.
524 *
525 * If the scc_index was not updated, all the vertices above on
526 * vertex_stack are in the same SCC. Group them using scc_entry.
527 */
528 __list_cut_position(&scc, &vertex_stack, &vertex->scc_entry);
529
530 list_for_each_entry_reverse(v, &scc, scc_entry) {
531 /* Mark vertex as off-stack and assign a unique ID. */
532 v->index = unix_vertex_grouped_index;
533 v->scc_index = vertex->scc_index;
534 }
535
536 if (unix_scc_dead(&scc)) {
537 unix_collect_skb(&scc, hitlist);
538 } else {
539 if (unix_vertex_max_scc_index < vertex->scc_index)
540 unix_vertex_max_scc_index = vertex->scc_index;
541
542 if (unix_scc_cyclic(&scc))
543 cyclic_sccs++;
544 }
545
546 list_del(&scc);
547 }
548
549 /* Need backtracking ? */
550 if (!list_empty(&edge_stack))
551 goto prev_vertex;
552
553 return cyclic_sccs;
554}
555
556static unsigned long unix_graph_cyclic_sccs;
557
558static void unix_walk_scc(struct sk_buff_head *hitlist)
559{
560 unsigned long last_index = UNIX_VERTEX_INDEX_START;
561 unsigned long cyclic_sccs = 0;
562
563 unix_vertex_max_scc_index = UNIX_VERTEX_INDEX_START;
564
565 /* Visit every vertex exactly once.
566 * __unix_walk_scc() moves visited vertices to unix_visited_vertices.
567 */
568 while (!list_empty(&unix_unvisited_vertices)) {
569 struct unix_vertex *vertex;
570
571 vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
572 cyclic_sccs += __unix_walk_scc(vertex, &last_index, hitlist);
573 }
574
575 list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
576 swap(unix_vertex_unvisited_index, unix_vertex_grouped_index);
577
578 WRITE_ONCE(unix_graph_cyclic_sccs, cyclic_sccs);
579 WRITE_ONCE(unix_graph_state,
580 cyclic_sccs ? UNIX_GRAPH_CYCLIC : UNIX_GRAPH_NOT_CYCLIC);
581}
582
583static void unix_walk_scc_fast(struct sk_buff_head *hitlist)
584{
585 unsigned long cyclic_sccs = unix_graph_cyclic_sccs;
586
587 while (!list_empty(&unix_unvisited_vertices)) {
588 struct unix_vertex *vertex;
589 struct list_head scc;
590
591 vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
592 list_add(&scc, &vertex->scc_entry);
593
594 if (unix_scc_dead(&scc)) {
595 cyclic_sccs--;
596 unix_collect_skb(&scc, hitlist);
597 }
598
599 list_del(&scc);
600 }
601
602 list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
603
604 WRITE_ONCE(unix_graph_cyclic_sccs, cyclic_sccs);
605 WRITE_ONCE(unix_graph_state,
606 cyclic_sccs ? UNIX_GRAPH_CYCLIC : UNIX_GRAPH_NOT_CYCLIC);
607}
608
609static void unix_gc(struct work_struct *work)
610{
611 struct sk_buff_head hitlist;
612 struct sk_buff *skb;
613
614 WRITE_ONCE(gc_in_progress, true);
615
616 spin_lock(&unix_gc_lock);
617
618 if (unix_graph_state == UNIX_GRAPH_NOT_CYCLIC) {
619 spin_unlock(&unix_gc_lock);
620 goto skip_gc;
621 }
622
623 __skb_queue_head_init(&hitlist);
624
625 if (unix_graph_state == UNIX_GRAPH_CYCLIC)
626 unix_walk_scc_fast(&hitlist);
627 else
628 unix_walk_scc(&hitlist);
629
630 spin_unlock(&unix_gc_lock);
631
632 skb_queue_walk(&hitlist, skb) {
633 if (UNIXCB(skb).fp)
634 UNIXCB(skb).fp->dead = true;
635 }
636
637 __skb_queue_purge_reason(&hitlist, SKB_DROP_REASON_SOCKET_CLOSE);
638skip_gc:
639 WRITE_ONCE(gc_in_progress, false);
640}
641
642static DECLARE_WORK(unix_gc_work, unix_gc);
643
644#define UNIX_INFLIGHT_SANE_USER (SCM_MAX_FD * 8)
645
646void unix_schedule_gc(struct user_struct *user)
647{
648 if (READ_ONCE(unix_graph_state) == UNIX_GRAPH_NOT_CYCLIC)
649 return;
650
651 /* Penalise users who want to send AF_UNIX sockets
652 * but whose sockets have not been received yet.
653 */
654 if (user &&
655 READ_ONCE(user->unix_inflight) < UNIX_INFLIGHT_SANE_USER)
656 return;
657
658 if (!READ_ONCE(gc_in_progress))
659 queue_work(system_dfl_wq, &unix_gc_work);
660
661 if (user && READ_ONCE(unix_graph_cyclic_sccs))
662 flush_work(&unix_gc_work);
663}