URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [uclinux/] [uClinux-2.0.x/] [net/] [unix/] [garbage.c] - Blame information for rev 1765

Details | Compare with Previous | View Log


/*
 * NET3:        Garbage Collector For AF_UNIX sockets
 *
 * Garbage Collector:
 *      Copyright (C) Barak A. Pearlmutter.
 *      Released under the GPL version 2 or later.
 *
 * 12/3/97 -- Flood
 * Internal stack is only allocated one page.  On systems with NR_FILE
 * > 1024, this makes it quite easy for a user-space program to open
 * a large number of AF_UNIX domain sockets, causing the garbage
 * collection routines to run up against the wall (and panic).
 * Changed the MAX_STACK to be associated to the system-wide open file
 * maximum, and use vmalloc() instead of get_free_page() [as more than
 * one page may be necessary].  As noted below, this should ideally be
 * done with a linked list.
 *
 * Chopped about by Alan Cox 22/3/96 to make it fit the AF_UNIX socket problem.
 * If it doesn't work blame me, it worked when Barak sent it.
 *
 * Assumptions:
 *
 *  - object w/ a bit
 *  - free list
 *
 * Current optimizations:
 *
 *  - explicit stack instead of recursion
 *  - tail recurse on first born instead of immediate push/pop
 *
 *  Future optimizations:
 *
 *  - don't just push entire root set; process in place
 *  - use linked list for internal stack
 *
 *      This program is free software; you can redistribute it and/or
 *      modify it under the terms of the GNU General Public License
 *      as published by the Free Software Foundation; either version
 *      2 of the License, or (at your option) any later version.
 *
 *  Fixes:
 *     Al Viro         11 Oct 1998
 *             Graph may have cycles. That is, we can send the descriptor
 *             of foo to bar and vice versa. Current code chokes on that.
 *             Fix: move SCM_RIGHTS ones into the separate list and then
 *             kfree_skb() them all instead of doing explicit fput's.
 *             Another problem: since fput() may block somebody may
 *             create a new unix_socket when we are in the middle of sweep
 *             phase. Fix: revert the logic wrt MARKED. Mark everything
 *             upon the beginning and unmark non-junk ones.
 *
 *             [12 Oct 1998] AAARGH! New code purges all SCM_RIGHTS
 *             sent to connect()'ed but still not accept()'ed sockets.
 *             Fixed. Old code had slightly different problem here:
 *             extra fput() in situation when we passed the descriptor via
 *             such socket and closed it (descriptor). That would happen on
 *             each unix_gc() until the accept(). Since the struct file in
 *             question would go to the free list and might be reused...
 *             That might be the reason of random oopses on close_fp() in
 *             unrelated processes.
 *
 */
 
#include <linux/kernel.h>
#include <linux/major.h>
#include <linux/signal.h>
#include <linux/sched.h>
#include <linux/errno.h>
#include <linux/string.h>
#include <linux/stat.h>
#include <linux/socket.h>
#include <linux/un.h>
#include <linux/fcntl.h>
#include <linux/termios.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/net.h>
#include <linux/in.h>
#include <linux/fs.h>
#include <linux/malloc.h>
#include <asm/segment.h>
#include <linux/skbuff.h>
#include <linux/netdevice.h>
#include <net/sock.h>
#include <net/tcp.h>
#include <net/af_unix.h>
#include <linux/proc_fs.h>
 
/* Internal data structures and random procedures: */
 
static unix_socket **stack;     /* stack of objects to mark */
static int in_stack = 0; /* first free entry in stack */
static int max_stack;           /* Calculated in unix_gc() */
 
extern inline unix_socket *unix_get_socket(struct file *filp)
{
        unix_socket * u_sock = NULL;
        struct inode *inode = filp->f_inode;
 
        /*
         *      Socket ?
         */
        if (inode && inode->i_sock) {
                struct socket * s = &inode->u.socket_i;
 
                /*
                 *      AF_UNIX ?
                 */
                if (s->ops == &unix_proto_ops)
                        u_sock = s->data;
        }
        return u_sock;
}
 
/*
 *      Keep the number of times in flight count for the file
 *      descriptor if it is for an AF_UNIX socket.
 */
 
void unix_inflight(struct file *fp)
{
        unix_socket *s=unix_get_socket(fp);
        if(s)
                s->protinfo.af_unix.inflight++;
}
 
void unix_notinflight(struct file *fp)
{
        unix_socket *s=unix_get_socket(fp);
        if(s)
                s->protinfo.af_unix.inflight--;
}
 
 
/*
 *      Garbage Collector Support Functions
 */
 
extern inline void push_stack(unix_socket *x)
{
        if (in_stack == max_stack)
                panic("can't push onto full stack");
        stack[in_stack++] = x;
}
 
extern inline unix_socket *pop_stack(void)
{
        if (in_stack == 0)
                panic("can't pop empty gc stack");
        return stack[--in_stack];
}
 
extern inline int empty_stack(void)
{
        return in_stack == 0;
}
 
extern inline void maybe_unmark_and_push(unix_socket *x)
{
        if (!(x->protinfo.af_unix.marksweep&MARKED))
                return;
        x->protinfo.af_unix.marksweep&=~MARKED;
        push_stack(x);
}
 
 
/* The external entry point: unix_gc() */
 
void unix_gc(void)
{
        static int in_unix_gc=0;
        unix_socket *s;
        struct sk_buff *skb;
        struct sk_buff_head hitlist;
 
        /*
         *      Avoid a recursive GC.
         */
 
        if(in_unix_gc)
                return;
        in_unix_gc=1;
 
        max_stack = max_files;
 
        stack=(unix_socket **)vmalloc(max_stack * sizeof(unix_socket **));
        if (!stack) {
                in_unix_gc=0;
                return;
        }
 
        /*
         *      Everything is now marked
         */
 
        for(s=unix_socket_list;s!=NULL;s=s->next)
        {
                s->protinfo.af_unix.marksweep|=MARKED;
        }
 
        /* Invariant to be maintained:
                - everything unmarked is either:
                -- (a) on the stack, or
                -- (b) has all of its children unmarked
                - everything on the stack is always unmarked
                - nothing is ever pushed onto the stack twice, because:
                -- nothing previously unmarked is ever pushed on the stack
         */
 
        /*
         *      Push root set
         */
 
        for(s=unix_socket_list;s!=NULL;s=s->next)
        {
                /*
                 *      If all instances of the descriptor are not
                 *      in flight we are in use.
                 */
                if(s->socket && s->socket->file &&
                        s->socket->file->f_count > s->protinfo.af_unix.inflight)
                        maybe_unmark_and_push(s);
        }
 
        /*
         *      Mark phase
         */
 
        while (!empty_stack())
        {
                unix_socket *x = pop_stack();
                unix_socket *f=NULL,*sk;
tail:
                skb=skb_peek(&x->receive_queue);
 
                /*
                 *      Loop through all but first born
                 */
 
                while(skb && skb != (struct sk_buff *)&x->receive_queue)
                {
                        /*
                         *      Do we have file descriptors ?
                         */
                        if(skb->h.filp)
                        {
                                /*
                                 *      Process the descriptors of this socket
                                 */
                                int nfd=*(int *)skb->h.filp;
                                struct file **fp=(struct file **)(skb->h.filp+sizeof(int));
                                while(nfd--)
                                {
                                        /*
                                         *      Get the socket the fd matches if
                                         *      it indeed does so
                                         */
                                        if((sk=unix_get_socket(*fp++))!=NULL)
                                        {
                                                /*
                                                 *      Remember the first, unmark the
                                                 *      rest.
                                                 */
                                                if(f==NULL)
                                                        f=sk;
                                                else
                                                        maybe_unmark_and_push(sk);
                                        }
                                }
                        }
                        /*
                         *      If we are connecting we need to handle this too
                         */
                        if(x->state == TCP_LISTEN)
                        {
                                if(f==NULL)
                                        f=skb->sk;
                                else
                                        maybe_unmark_and_push(skb->sk);
                        }
                        skb=skb->next;
                }
 
                /*
                 *      Handle first born specially
                 */
 
                if (f)
                {
                        if (f->protinfo.af_unix.marksweep&MARKED)
                        {
                                f->protinfo.af_unix.marksweep&=~MARKED;
                                x=f;
                                f=NULL;
                                goto tail;
                        }
                }
        }
 
        skb_queue_head_init(&hitlist);
 
        for(s=unix_socket_list;s!=NULL;s=s->next)
        {
                if (s->protinfo.af_unix.marksweep&MARKED)
                {
                        struct sk_buff *nextsk;
                        skb=skb_peek(&s->receive_queue);
                        while(skb && skb != (struct sk_buff *)&s->receive_queue)
                        {
                                nextsk=skb->next;
                                /*
                                 *      Do we have file descriptors ?
                                 */
                                if(*(int *)(skb->h.filp))
                                {
                                        /*
                                         *      Pull these buffers out of line
                                         *      so they will each be freed once
                                         *      at the end.
                                         */
                                        skb_unlink(skb);
                                        skb_queue_tail(&hitlist,skb);
                                }
                                skb=nextsk;
                        }
                }
        }
 
        /*
         *      Here we are. Hitlist is filled. Die.
         */
 
        while ((skb=skb_dequeue(&hitlist))!=NULL)
        {
                kfree_skb(skb, FREE_READ);
        }
 
        in_unix_gc=0;
        vfree(stack);
}

Browse

Tools

Subversion Repositories or1k

[/] [or1k/] [trunk/] [uclinux/] [uClinux-2.0.x/] [net/] [unix/] [garbage.c] - Blame information for rev 1765

Line No.	Rev	Author	Line
1	199	simons	`/*`
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			`* 12/3/97 -- Flood`
9			`* Internal stack is only allocated one page. On systems with NR_FILE`
10			`* > 1024, this makes it quite easy for a user-space program to open`
11			`* a large number of AF_UNIX domain sockets, causing the garbage`
12			`* collection routines to run up against the wall (and panic).`
13			`* Changed the MAX_STACK to be associated to the system-wide open file`
14			`* maximum, and use vmalloc() instead of get_free_page() [as more than`
15			`* one page may be necessary]. As noted below, this should ideally be`
16			`* done with a linked list.`
17			`*`
18			`* Chopped about by Alan Cox 22/3/96 to make it fit the AF_UNIX socket problem.`
19			`* If it doesn't work blame me, it worked when Barak sent it.`
20			`*`
21			`* Assumptions:`
22			`*`
23			`* - object w/ a bit`
24			`* - free list`
25			`*`
26			`* Current optimizations:`
27			`*`
28			`* - explicit stack instead of recursion`
29			`* - tail recurse on first born instead of immediate push/pop`
30			`*`
31			`* Future optimizations:`
32			`*`
33			`* - don't just push entire root set; process in place`
34			`* - use linked list for internal stack`
35			`*`
36			`* This program is free software; you can redistribute it and/or`
37			`* modify it under the terms of the GNU General Public License`
38			`* as published by the Free Software Foundation; either version`
39			`* 2 of the License, or (at your option) any later version.`
40			`*`
41			`* Fixes:`
42			`* Al Viro 11 Oct 1998`
43			`* Graph may have cycles. That is, we can send the descriptor`
44			`* of foo to bar and vice versa. Current code chokes on that.`
45			`* Fix: move SCM_RIGHTS ones into the separate list and then`
46			`* kfree_skb() them all instead of doing explicit fput's.`
47			`* Another problem: since fput() may block somebody may`
48			`* create a new unix_socket when we are in the middle of sweep`
49			`* phase. Fix: revert the logic wrt MARKED. Mark everything`
50			`* upon the beginning and unmark non-junk ones.`
51			`*`
52			`* [12 Oct 1998] AAARGH! New code purges all SCM_RIGHTS`
53			`* sent to connect()'ed but still not accept()'ed sockets.`
54			`* Fixed. Old code had slightly different problem here:`
55			`* extra fput() in situation when we passed the descriptor via`
56			`* such socket and closed it (descriptor). That would happen on`
57			`* each unix_gc() until the accept(). Since the struct file in`
58			`* question would go to the free list and might be reused...`
59			`* That might be the reason of random oopses on close_fp() in`
60			`* unrelated processes.`
61			`*`
62			`*/`
63
64			`#include <linux/kernel.h>`
65			`#include <linux/major.h>`
66			`#include <linux/signal.h>`
67			`#include <linux/sched.h>`
68			`#include <linux/errno.h>`
69			`#include <linux/string.h>`
70			`#include <linux/stat.h>`
71			`#include <linux/socket.h>`
72			`#include <linux/un.h>`
73			`#include <linux/fcntl.h>`
74			`#include <linux/termios.h>`
75			`#include <linux/socket.h>`
76			`#include <linux/sockios.h>`
77			`#include <linux/net.h>`
78			`#include <linux/in.h>`
79			`#include <linux/fs.h>`
80			`#include <linux/malloc.h>`
81			`#include <asm/segment.h>`
82			`#include <linux/skbuff.h>`
83			`#include <linux/netdevice.h>`
84			`#include <net/sock.h>`
85			`#include <net/tcp.h>`
86			`#include <net/af_unix.h>`
87			`#include <linux/proc_fs.h>`
88
89			`/* Internal data structures and random procedures: */`
90
91			`static unix_socket *stack; / stack of objects to mark */`
92			`static int in_stack = 0; /* first free entry in stack */`
93			`static int max_stack; /* Calculated in unix_gc() */`
94
95			`extern inline unix_socket unix_get_socket(struct file filp)`
96			`{`
97			`unix_socket * u_sock = NULL;`
98			`struct inode *inode = filp->f_inode;`
99
100			`/*`
101			`* Socket ?`
102			`*/`
103			`if (inode && inode->i_sock) {`
104			`struct socket * s = &inode->u.socket_i;`
105
106			`/*`
107			`* AF_UNIX ?`
108			`*/`
109			`if (s->ops == &unix_proto_ops)`
110			`u_sock = s->data;`
111			`}`
112			`return u_sock;`
113			`}`
114
115			`/*`
116			`* Keep the number of times in flight count for the file`
117			`* descriptor if it is for an AF_UNIX socket.`
118			`*/`
119
120			`void unix_inflight(struct file *fp)`
121			`{`
122			`unix_socket *s=unix_get_socket(fp);`
123			`if(s)`
124			`s->protinfo.af_unix.inflight++;`
125			`}`
126
127			`void unix_notinflight(struct file *fp)`
128			`{`
129			`unix_socket *s=unix_get_socket(fp);`
130			`if(s)`
131			`s->protinfo.af_unix.inflight--;`
132			`}`
133
134
135			`/*`
136			`* Garbage Collector Support Functions`
137			`*/`
138
139			`extern inline void push_stack(unix_socket *x)`
140			`{`
141			`if (in_stack == max_stack)`
142			`panic("can't push onto full stack");`
143			`stack[in_stack++] = x;`
144			`}`
145
146			`extern inline unix_socket *pop_stack(void)`
147			`{`
148			`if (in_stack == 0)`
149			`panic("can't pop empty gc stack");`
150			`return stack[--in_stack];`
151			`}`
152
153			`extern inline int empty_stack(void)`
154			`{`
155			`return in_stack == 0;`
156			`}`
157
158			`extern inline void maybe_unmark_and_push(unix_socket *x)`
159			`{`
160			`if (!(x->protinfo.af_unix.marksweep&MARKED))`
161			`return;`
162			`x->protinfo.af_unix.marksweep&=~MARKED;`
163			`push_stack(x);`
164			`}`
165
166
167			`/* The external entry point: unix_gc() */`
168
169			`void unix_gc(void)`
170			`{`
171			`static int in_unix_gc=0;`
172			`unix_socket *s;`
173			`struct sk_buff *skb;`
174			`struct sk_buff_head hitlist;`
175
176			`/*`
177			`* Avoid a recursive GC.`
178			`*/`
179
180			`if(in_unix_gc)`
181			`return;`
182			`in_unix_gc=1;`
183
184			`max_stack = max_files;`
185
186			`stack=(unix_socket *)vmalloc(max_stack sizeof(unix_socket **));`
187			`if (!stack) {`
188			`in_unix_gc=0;`
189			`return;`
190			`}`
191
192			`/*`
193			`* Everything is now marked`
194			`*/`
195
196			`for(s=unix_socket_list;s!=NULL;s=s->next)`
197			`{`
198			`s->protinfo.af_unix.marksweep\|=MARKED;`
199			`}`
200
201			`/* Invariant to be maintained:`
202			`- everything unmarked is either:`
203			`-- (a) on the stack, or`
204			`-- (b) has all of its children unmarked`
205			`- everything on the stack is always unmarked`
206			`- nothing is ever pushed onto the stack twice, because:`
207			`-- nothing previously unmarked is ever pushed on the stack`
208			`*/`
209
210			`/*`
211			`* Push root set`
212			`*/`
213
214			`for(s=unix_socket_list;s!=NULL;s=s->next)`
215			`{`
216			`/*`
217			`* If all instances of the descriptor are not`
218			`* in flight we are in use.`
219			`*/`
220			`if(s->socket && s->socket->file &&`
221			`s->socket->file->f_count > s->protinfo.af_unix.inflight)`
222			`maybe_unmark_and_push(s);`
223			`}`
224
225			`/*`
226			`* Mark phase`
227			`*/`
228
229			`while (!empty_stack())`
230			`{`
231			`unix_socket *x = pop_stack();`
232			`unix_socket f=NULL,sk;`
233			`tail:`
234			`skb=skb_peek(&x->receive_queue);`
235
236			`/*`
237			`* Loop through all but first born`
238			`*/`
239
240			`while(skb && skb != (struct sk_buff *)&x->receive_queue)`
241			`{`
242			`/*`
243			`* Do we have file descriptors ?`
244			`*/`
245			`if(skb->h.filp)`
246			`{`
247			`/*`
248			`* Process the descriptors of this socket`
249			`*/`
250			`int nfd=(int )skb->h.filp;`
251			`struct file fp=(struct file )(skb->h.filp+sizeof(int));`
252			`while(nfd--)`
253			`{`
254			`/*`
255			`* Get the socket the fd matches if`
256			`* it indeed does so`
257			`*/`
258			`if((sk=unix_get_socket(*fp++))!=NULL)`
259			`{`
260			`/*`
261			`* Remember the first, unmark the`
262			`* rest.`
263			`*/`
264			`if(f==NULL)`
265			`f=sk;`
266			`else`
267			`maybe_unmark_and_push(sk);`
268			`}`
269			`}`
270			`}`
271			`/*`
272			`* If we are connecting we need to handle this too`
273			`*/`
274			`if(x->state == TCP_LISTEN)`
275			`{`
276			`if(f==NULL)`
277			`f=skb->sk;`
278			`else`
279			`maybe_unmark_and_push(skb->sk);`
280			`}`
281			`skb=skb->next;`
282			`}`
283
284			`/*`
285			`* Handle first born specially`
286			`*/`
287
288			`if (f)`
289			`{`
290			`if (f->protinfo.af_unix.marksweep&MARKED)`
291			`{`
292			`f->protinfo.af_unix.marksweep&=~MARKED;`
293			`x=f;`
294			`f=NULL;`
295			`goto tail;`
296			`}`
297			`}`
298			`}`
299
300			`skb_queue_head_init(&hitlist);`
301
302			`for(s=unix_socket_list;s!=NULL;s=s->next)`
303			`{`
304			`if (s->protinfo.af_unix.marksweep&MARKED)`
305			`{`
306			`struct sk_buff *nextsk;`
307			`skb=skb_peek(&s->receive_queue);`
308			`while(skb && skb != (struct sk_buff *)&s->receive_queue)`
309			`{`
310			`nextsk=skb->next;`
311			`/*`
312			`* Do we have file descriptors ?`
313			`*/`
314			`if((int )(skb->h.filp))`
315			`{`
316			`/*`
317			`* Pull these buffers out of line`
318			`* so they will each be freed once`
319			`* at the end.`
320			`*/`
321			`skb_unlink(skb);`
322			`skb_queue_tail(&hitlist,skb);`
323			`}`
324			`skb=nextsk;`
325			`}`
326			`}`
327			`}`
328
329			`/*`
330			`* Here we are. Hitlist is filled. Die.`
331			`*/`
332
333			`while ((skb=skb_dequeue(&hitlist))!=NULL)`
334			`{`
335			`kfree_skb(skb, FREE_READ);`
336			`}`
337
338			`in_unix_gc=0;`
339			`vfree(stack);`
340			`}`