home *** CD-ROM | disk | FTP | other *** search
/ Magazyn WWW 2000 January / www_01_2000.iso / poland / garbage / g / varia / garbage.c next >
C/C++ Source or Header  |  1999-12-01  |  8KB  |  341 lines
  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.  * 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. }
  341.