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