Branch data Line data Source code
1 : : /*
2 : : * NET3: Garbage Collector For AF_UNIX sockets
3 : : *
4 : : * Garbage Collector:
5 : : * Copyright (C) Barak A. Pearlmutter.
6 : : * Released under the GPL version 2 or later.
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 : : * This program is free software; you can redistribute it and/or
28 : : * modify it under the terms of the GNU General Public License
29 : : * as published by the Free Software Foundation; either version
30 : : * 2 of the License, or (at your option) any later version.
31 : : *
32 : : * Fixes:
33 : : * Alan Cox 07 Sept 1997 Vmalloc internal stack as needed.
34 : : * Cope with changing max_files.
35 : : * Al Viro 11 Oct 1998
36 : : * Graph may have cycles. That is, we can send the descriptor
37 : : * of foo to bar and vice versa. Current code chokes on that.
38 : : * Fix: move SCM_RIGHTS ones into the separate list and then
39 : : * skb_free() them all instead of doing explicit fput's.
40 : : * Another problem: since fput() may block somebody may
41 : : * create a new unix_socket when we are in the middle of sweep
42 : : * phase. Fix: revert the logic wrt MARKED. Mark everything
43 : : * upon the beginning and unmark non-junk ones.
44 : : *
45 : : * [12 Oct 1998] AAARGH! New code purges all SCM_RIGHTS
46 : : * sent to connect()'ed but still not accept()'ed sockets.
47 : : * Fixed. Old code had slightly different problem here:
48 : : * extra fput() in situation when we passed the descriptor via
49 : : * such socket and closed it (descriptor). That would happen on
50 : : * each unix_gc() until the accept(). Since the struct file in
51 : : * question would go to the free list and might be reused...
52 : : * That might be the reason of random oopses on filp_close()
53 : : * in unrelated processes.
54 : : *
55 : : * AV 28 Feb 1999
56 : : * Kill the explicit allocation of stack. Now we keep the tree
57 : : * with root in dummy + pointer (gc_current) to one of the nodes.
58 : : * Stack is represented as path from gc_current to dummy. Unmark
59 : : * now means "add to tree". Push == "make it a son of gc_current".
60 : : * Pop == "move gc_current to parent". We keep only pointers to
61 : : * parents (->gc_tree).
62 : : * AV 1 Mar 1999
63 : : * Damn. Added missing check for ->dead in listen queues scanning.
64 : : *
65 : : * Miklos Szeredi 25 Jun 2007
66 : : * Reimplement with a cycle collecting algorithm. This should
67 : : * solve several problems with the previous code, like being racy
68 : : * wrt receive and holding up unrelated socket operations.
69 : : */
70 : :
71 : : #include <linux/kernel.h>
72 : : #include <linux/string.h>
73 : : #include <linux/socket.h>
74 : : #include <linux/un.h>
75 : : #include <linux/net.h>
76 : : #include <linux/fs.h>
77 : : #include <linux/skbuff.h>
78 : : #include <linux/netdevice.h>
79 : : #include <linux/file.h>
80 : : #include <linux/proc_fs.h>
81 : : #include <linux/mutex.h>
82 : : #include <linux/wait.h>
83 : :
84 : : #include <net/sock.h>
85 : : #include <net/af_unix.h>
86 : : #include <net/scm.h>
87 : : #include <net/tcp_states.h>
88 : :
89 : : /* Internal data structures and random procedures: */
90 : :
91 : : static LIST_HEAD(gc_inflight_list);
92 : : static LIST_HEAD(gc_candidates);
93 : : static DEFINE_SPINLOCK(unix_gc_lock);
94 : : static DECLARE_WAIT_QUEUE_HEAD(unix_gc_wait);
95 : :
96 : : unsigned int unix_tot_inflight;
97 : :
98 : :
99 : 0 : struct sock *unix_get_socket(struct file *filp)
100 : : {
101 : : struct sock *u_sock = NULL;
102 : : struct inode *inode = file_inode(filp);
103 : :
104 : : /*
105 : : * Socket ?
106 : : */
107 [ - + ][ # # ]: 8 : if (S_ISSOCK(inode->i_mode) && !(filp->f_mode & FMODE_PATH)) {
108 : : struct socket *sock = SOCKET_I(inode);
109 : 0 : struct sock *s = sock->sk;
110 : :
111 : : /*
112 : : * PF_UNIX ?
113 : : */
114 [ # # ][ # # ]: 0 : if (s && sock->ops && sock->ops->family == PF_UNIX)
[ # # ]
115 : : u_sock = s;
116 : : }
117 : 0 : return u_sock;
118 : : }
119 : :
120 : : /*
121 : : * Keep the number of times in flight count for the file
122 : : * descriptor if it is for an AF_UNIX socket.
123 : : */
124 : :
125 : 0 : void unix_inflight(struct file *fp)
126 : : {
127 : 0 : struct sock *s = unix_get_socket(fp);
128 [ # # ]: 0 : if (s) {
129 : : struct unix_sock *u = unix_sk(s);
130 : : spin_lock(&unix_gc_lock);
131 [ # # ]: 0 : if (atomic_long_inc_return(&u->inflight) == 1) {
132 [ # # ]: 0 : BUG_ON(!list_empty(&u->link));
133 : : list_add_tail(&u->link, &gc_inflight_list);
134 : : } else {
135 [ # # ]: 0 : BUG_ON(list_empty(&u->link));
136 : : }
137 : 0 : unix_tot_inflight++;
138 : : spin_unlock(&unix_gc_lock);
139 : : }
140 : 0 : }
141 : :
142 : 0 : void unix_notinflight(struct file *fp)
143 : : {
144 : 4 : struct sock *s = unix_get_socket(fp);
145 [ - + ]: 4 : if (s) {
146 : : struct unix_sock *u = unix_sk(s);
147 : : spin_lock(&unix_gc_lock);
148 [ # # ]: 0 : BUG_ON(list_empty(&u->link));
149 [ # # ]: 0 : if (atomic_long_dec_and_test(&u->inflight))
150 : : list_del_init(&u->link);
151 : 0 : unix_tot_inflight--;
152 : : spin_unlock(&unix_gc_lock);
153 : : }
154 : 4 : }
155 : :
156 : 0 : static void scan_inflight(struct sock *x, void (*func)(struct unix_sock *),
157 : : struct sk_buff_head *hitlist)
158 : : {
159 : : struct sk_buff *skb;
160 : : struct sk_buff *next;
161 : :
162 : : spin_lock(&x->sk_receive_queue.lock);
163 [ # # ]: 0 : skb_queue_walk_safe(&x->sk_receive_queue, skb, next) {
164 : : /*
165 : : * Do we have file descriptors ?
166 : : */
167 [ # # ]: 0 : if (UNIXCB(skb).fp) {
168 : : bool hit = false;
169 : : /*
170 : : * Process the descriptors of this socket
171 : : */
172 : 0 : int nfd = UNIXCB(skb).fp->count;
173 : 0 : struct file **fp = UNIXCB(skb).fp->fp;
174 [ # # ]: 0 : while (nfd--) {
175 : : /*
176 : : * Get the socket the fd matches
177 : : * if it indeed does so
178 : : */
179 : 0 : struct sock *sk = unix_get_socket(*fp++);
180 [ # # ]: 0 : if (sk) {
181 : : struct unix_sock *u = unix_sk(sk);
182 : :
183 : : /*
184 : : * Ignore non-candidates, they could
185 : : * have been added to the queues after
186 : : * starting the garbage collection
187 : : */
188 [ # # ]: 0 : if (test_bit(UNIX_GC_CANDIDATE, &u->gc_flags)) {
189 : : hit = true;
190 : 0 : func(u);
191 : : }
192 : : }
193 : : }
194 [ # # ]: 0 : if (hit && hitlist != NULL) {
195 : : __skb_unlink(skb, &x->sk_receive_queue);
196 : : __skb_queue_tail(hitlist, skb);
197 : : }
198 : : }
199 : : }
200 : : spin_unlock(&x->sk_receive_queue.lock);
201 : 0 : }
202 : :
203 : 0 : static void scan_children(struct sock *x, void (*func)(struct unix_sock *),
204 : : struct sk_buff_head *hitlist)
205 : : {
206 [ # # ]: 0 : if (x->sk_state != TCP_LISTEN)
207 : 0 : scan_inflight(x, func, hitlist);
208 : : else {
209 : : struct sk_buff *skb;
210 : : struct sk_buff *next;
211 : : struct unix_sock *u;
212 : 0 : LIST_HEAD(embryos);
213 : :
214 : : /*
215 : : * For a listening socket collect the queued embryos
216 : : * and perform a scan on them as well.
217 : : */
218 : : spin_lock(&x->sk_receive_queue.lock);
219 [ # # ]: 0 : skb_queue_walk_safe(&x->sk_receive_queue, skb, next) {
220 : 0 : u = unix_sk(skb->sk);
221 : :
222 : : /*
223 : : * An embryo cannot be in-flight, so it's safe
224 : : * to use the list link.
225 : : */
226 [ # # ]: 0 : BUG_ON(!list_empty(&u->link));
227 : : list_add_tail(&u->link, &embryos);
228 : : }
229 : : spin_unlock(&x->sk_receive_queue.lock);
230 : :
231 [ # # ]: 0 : while (!list_empty(&embryos)) {
232 : : u = list_entry(embryos.next, struct unix_sock, link);
233 : 0 : scan_inflight(&u->sk, func, hitlist);
234 : 0 : list_del_init(&u->link);
235 : : }
236 : : }
237 : 0 : }
238 : :
239 : 0 : static void dec_inflight(struct unix_sock *usk)
240 : : {
241 : 0 : atomic_long_dec(&usk->inflight);
242 : 0 : }
243 : :
244 : 0 : static void inc_inflight(struct unix_sock *usk)
245 : : {
246 : 0 : atomic_long_inc(&usk->inflight);
247 : 0 : }
248 : :
249 : 0 : static void inc_inflight_move_tail(struct unix_sock *u)
250 : : {
251 : 0 : atomic_long_inc(&u->inflight);
252 : : /*
253 : : * If this still might be part of a cycle, move it to the end
254 : : * of the list, so that it's checked even if it was already
255 : : * passed over
256 : : */
257 [ # # ]: 0 : if (test_bit(UNIX_GC_MAYBE_CYCLE, &u->gc_flags))
258 : 0 : list_move_tail(&u->link, &gc_candidates);
259 : 0 : }
260 : :
261 : : static bool gc_in_progress = false;
262 : : #define UNIX_INFLIGHT_TRIGGER_GC 16000
263 : :
264 : 0 : void wait_for_unix_gc(void)
265 : : {
266 : : /*
267 : : * If number of inflight sockets is insane,
268 : : * force a garbage collect right now.
269 : : */
270 [ - + ][ # # ]: 1213034 : if (unix_tot_inflight > UNIX_INFLIGHT_TRIGGER_GC && !gc_in_progress)
271 : 0 : unix_gc();
272 [ - + ][ # # ]: 2452525 : wait_event(unix_gc_wait, gc_in_progress == false);
273 : 1239491 : }
274 : :
275 : : /* The external entry point: unix_gc() */
276 : 0 : void unix_gc(void)
277 : : {
278 : : struct unix_sock *u;
279 : : struct unix_sock *next;
280 : : struct sk_buff_head hitlist;
281 : : struct list_head cursor;
282 : 0 : LIST_HEAD(not_cycle_list);
283 : :
284 : : spin_lock(&unix_gc_lock);
285 : :
286 : : /* Avoid a recursive GC. */
287 [ # # ]: 0 : if (gc_in_progress)
288 : : goto out;
289 : :
290 : 0 : gc_in_progress = true;
291 : : /*
292 : : * First, select candidates for garbage collection. Only
293 : : * in-flight sockets are considered, and from those only ones
294 : : * which don't have any external reference.
295 : : *
296 : : * Holding unix_gc_lock will protect these candidates from
297 : : * being detached, and hence from gaining an external
298 : : * reference. Since there are no possible receivers, all
299 : : * buffers currently on the candidates' queues stay there
300 : : * during the garbage collection.
301 : : *
302 : : * We also know that no new candidate can be added onto the
303 : : * receive queues. Other, non candidate sockets _can_ be
304 : : * added to queue, so we must make sure only to touch
305 : : * candidates.
306 : : */
307 [ # # ]: 0 : list_for_each_entry_safe(u, next, &gc_inflight_list, link) {
308 : : long total_refs;
309 : : long inflight_refs;
310 : :
311 : 0 : total_refs = file_count(u->sk.sk_socket->file);
312 : : inflight_refs = atomic_long_read(&u->inflight);
313 : :
314 [ # # ]: 0 : BUG_ON(inflight_refs < 1);
315 [ # # ]: 0 : BUG_ON(total_refs < inflight_refs);
316 [ # # ]: 0 : if (total_refs == inflight_refs) {
317 : : list_move_tail(&u->link, &gc_candidates);
318 : : __set_bit(UNIX_GC_CANDIDATE, &u->gc_flags);
319 : : __set_bit(UNIX_GC_MAYBE_CYCLE, &u->gc_flags);
320 : : }
321 : : }
322 : :
323 : : /*
324 : : * Now remove all internal in-flight reference to children of
325 : : * the candidates.
326 : : */
327 [ # # ]: 0 : list_for_each_entry(u, &gc_candidates, link)
328 : 0 : scan_children(&u->sk, dec_inflight, NULL);
329 : :
330 : : /*
331 : : * Restore the references for children of all candidates,
332 : : * which have remaining references. Do this recursively, so
333 : : * only those remain, which form cyclic references.
334 : : *
335 : : * Use a "cursor" link, to make the list traversal safe, even
336 : : * though elements might be moved about.
337 : : */
338 : : list_add(&cursor, &gc_candidates);
339 [ # # ]: 0 : while (cursor.next != &gc_candidates) {
340 : : u = list_entry(cursor.next, struct unix_sock, link);
341 : :
342 : : /* Move cursor to after the current position. */
343 : 0 : list_move(&cursor, &u->link);
344 : :
345 [ # # ]: 0 : if (atomic_long_read(&u->inflight) > 0) {
346 : : list_move_tail(&u->link, ¬_cycle_list);
347 : : __clear_bit(UNIX_GC_MAYBE_CYCLE, &u->gc_flags);
348 : 0 : scan_children(&u->sk, inc_inflight_move_tail, NULL);
349 : : }
350 : : }
351 : : list_del(&cursor);
352 : :
353 : : /*
354 : : * not_cycle_list contains those sockets which do not make up a
355 : : * cycle. Restore these to the inflight list.
356 : : */
357 [ # # ]: 0 : while (!list_empty(¬_cycle_list)) {
358 : : u = list_entry(not_cycle_list.next, struct unix_sock, link);
359 : : __clear_bit(UNIX_GC_CANDIDATE, &u->gc_flags);
360 : 0 : list_move_tail(&u->link, &gc_inflight_list);
361 : : }
362 : :
363 : : /*
364 : : * Now gc_candidates contains only garbage. Restore original
365 : : * inflight counters for these as well, and remove the skbuffs
366 : : * which are creating the cycle(s).
367 : : */
368 : : skb_queue_head_init(&hitlist);
369 [ # # ]: 0 : list_for_each_entry(u, &gc_candidates, link)
370 : 0 : scan_children(&u->sk, inc_inflight, &hitlist);
371 : :
372 : : spin_unlock(&unix_gc_lock);
373 : :
374 : : /* Here we are. Hitlist is filled. Die. */
375 : : __skb_queue_purge(&hitlist);
376 : :
377 : : spin_lock(&unix_gc_lock);
378 : :
379 : : /* All candidates should have been detached by now. */
380 [ # # ]: 0 : BUG_ON(!list_empty(&gc_candidates));
381 : 0 : gc_in_progress = false;
382 : 0 : wake_up(&unix_gc_wait);
383 : :
384 : : out:
385 : : spin_unlock(&unix_gc_lock);
386 : 0 : }
|
