net/unix/garbage.c

   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  *
  21  *  Future optimizations:
  22  *
  23  *  - don't just push entire root set; process in place
  24  *  - use linked list for internal stack
  25  *
  26  *      This program is free software; you can redistribute it and/or
  27  *      modify it under the terms of the GNU General Public License
  28  *      as published by the Free Software Foundation; either version
  29  *      2 of the License, or (at your option) any later version.
  30  *
  31  *  Fixes:
  32  *      Alan Cox        07 Sept 1997    Vmalloc internal stack as needed.
  33  *                                      Cope with changing max_files.
  34  *
  35  */
  36
  37 #include <linux/kernel.h>
  38 #include <linux/major.h>
  39 #include <linux/signal.h>
  40 #include <linux/sched.h>
  41 #include <linux/errno.h>
  42 #include <linux/string.h>
  43 #include <linux/stat.h>
  44 #include <linux/socket.h>
  45 #include <linux/un.h>
  46 #include <linux/fcntl.h>
  47 #include <linux/termios.h>
  48 #include <linux/socket.h>
  49 #include <linux/sockios.h>
  50 #include <linux/net.h>
  51 #include <linux/in.h>
  52 #include <linux/fs.h>
  53 #include <linux/malloc.h>
  54 #include <linux/vmalloc.h>
  55
  56 #include <asm/uaccess.h>
  57 #include <linux/skbuff.h>
  58 #include <linux/netdevice.h>
  59 #include <net/sock.h>
  60 #include <net/tcp.h>
  61 #include <net/af_unix.h>
  62 #include <linux/proc_fs.h>
  63 #include <net/scm.h>
  64
  65 /* Internal data structures and random procedures: */
  66
  67 static unix_socket **stack;     /* stack of objects to mark */
  68 static int in_stack = 0;        /* first free entry in stack */
  69 static int max_stack;           /* Top of stack */
  70
  71 extern inline unix_socket *unix_get_socket(struct file *filp)
  72 {
  73         unix_socket * u_sock = NULL;
  74         struct inode *inode = filp->f_dentry->d_inode;
  75
  76         /*
  77          *      Socket ?
  78          */
  79         if (inode && inode->i_sock) {
  80                 struct socket * sock = &inode->u.socket_i;
  81                 struct sock * s = sock->sk;
  82
  83                 /*
  84                  *      AF_UNIX ?
  85                  */
  86                 if (s && sock->ops && sock->ops->family == AF_UNIX)
  87                         u_sock = s;
  88         }
  89         return u_sock;
  90 }
  91
  92 /*
  93  *      Keep the number of times in flight count for the file
  94  *      descriptor if it is for an AF_UNIX socket.
  95  */
  96
  97 void unix_inflight(struct file *fp)
  98 {
  99         unix_socket *s=unix_get_socket(fp);
 100         if(s)
 101                 s->protinfo.af_unix.inflight++;
 102 }
 103
 104 void unix_notinflight(struct file *fp)
 105 {
 106         unix_socket *s=unix_get_socket(fp);
 107         if(s)
 108                 s->protinfo.af_unix.inflight--;
 109 }
 110
 111
 112 /*
 113  *      Garbage Collector Support Functions
 114  */
 115
 116 extern inline void push_stack(unix_socket *x)
 117 {
 118         if (in_stack == max_stack)
 119                 panic("can't push onto full stack");
 120         stack[in_stack++] = x;
 121 }
 122
 123 extern inline unix_socket *pop_stack(void)
 124 {
 125         if (in_stack == 0)
 126                 panic("can't pop empty gc stack");
 127         return stack[--in_stack];
 128 }
 129
 130 extern inline int empty_stack(void)
 131 {
 132         return in_stack == 0;
 133 }
 134
 135 extern inline void maybe_mark_and_push(unix_socket *x)
 136 {
 137         if (x->protinfo.af_unix.marksweep&MARKED)
 138                 return;
 139         x->protinfo.af_unix.marksweep|=MARKED;
 140         push_stack(x);
 141 }
 142
 143
 144 /* The external entry point: unix_gc() */
 145
 146 void unix_gc(void)
 147 {
 148         static int in_unix_gc=0;
 149         int i;
 150         unix_socket *s;
 151         unix_socket *next;
 152
 153         /*
 154          *      Avoid a recursive GC.
 155          */
 156
 157         if(in_unix_gc)
 158                 return;
 159         in_unix_gc=1;
 160
 161         if(stack==NULL || max_files>max_stack)
 162         {
 163                 if(stack)
 164                         vfree(stack);
 165                 stack=(unix_socket **)vmalloc(max_files*sizeof(struct unix_socket *));
 166                 if(stack==NULL)
 167                 {
 168                         printk(KERN_NOTICE "unix_gc: deferred due to low memory.\n");
 169                         in_unix_gc=0;
 170                         return;
 171                 }
 172                 max_stack=max_files;
 173         }
 174
 175         /*
 176          *      Assume everything is now unmarked
 177          */
 178
 179         /* Invariant to be maintained:
 180                 - everything marked is either:
 181                 -- (a) on the stack, or
 182                 -- (b) has all of its children marked
 183                 - everything on the stack is always marked
 184                 - nothing is ever pushed onto the stack twice, because:
 185                 -- nothing previously marked is ever pushed on the stack
 186          */
 187
 188         /*
 189          *      Push root set
 190          */
 191
 192         forall_unix_sockets(i, s)
 193         {
 194                 /*
 195                  *      If all instances of the descriptor are not
 196                  *      in flight we are in use.
 197                  */
 198                 if(s->socket && s->socket->file && s->socket->file->f_count > s->protinfo.af_unix.inflight)
 199                         maybe_mark_and_push(s);
 200         }
 201
 202         /*
 203          *      Mark phase
 204          */
 205
 206         while (!empty_stack())
 207         {
 208                 unix_socket *x = pop_stack();
 209                 unix_socket *f=NULL,*sk;
 210                 struct sk_buff *skb;
 211 tail:
 212                 skb=skb_peek(&x->receive_queue);
 213
 214                 /*
 215                  *      Loop through all but first born
 216                  */
 217
 218                 while(skb && skb != (struct sk_buff *)&x->receive_queue)
 219                 {
 220                         /*
 221                          *      Do we have file descriptors ?
 222                          */
 223                         if(UNIXCB(skb).fp)
 224                         {
 225                                 /*
 226                                  *      Process the descriptors of this socket
 227                                  */
 228                                 int nfd=UNIXCB(skb).fp->count;
 229                                 struct file **fp = UNIXCB(skb).fp->fp;
 230                                 while(nfd--)
 231                                 {
 232                                         /*
 233                                          *      Get the socket the fd matches if
 234                                          *      it indeed does so
 235                                          */
 236                                         if((sk=unix_get_socket(*fp++))!=NULL)
 237                                         {
 238                                                 /*
 239                                                  *      Remember the first, mark the
 240                                                  *      rest.
 241                                                  */
 242                                                 if(f==NULL)
 243                                                         f=sk;
 244                                                 else
 245                                                         maybe_mark_and_push(sk);
 246                                         }
 247                                 }
 248                         }
 249                         skb=skb->next;
 250                 }
 251                 /*
 252                  *      Handle first born specially
 253                  */
 254
 255                 if (f)
 256                 {
 257                         if (!(f->protinfo.af_unix.marksweep&MARKED))
 258                         {
 259                                 f->protinfo.af_unix.marksweep|=MARKED;
 260                                 x=f;
 261                                 f=NULL;
 262                                 goto tail;
 263                         }
 264                 }
 265         }
 266
 267         /*
 268          *      Sweep phase.  NOTE: this part dominates the time complexity
 269          */
 270
 271         forall_unix_sockets(i, s)
 272         {
 273                 next=s->next;
 274                 if (!(s->protinfo.af_unix.marksweep&MARKED))
 275                 {
 276                         /*
 277                          *      We exist only in the passing tree of sockets
 278                          *      that is no longer connected to active descriptors
 279                          *      Time to die..
 280                          *
 281                          *      Subtle item: We will correctly sweep out the
 282                          *      socket that has just been closed by the user.
 283                          *      We must not close this as we are in the middle
 284                          *      of its close at this moment. Skip that file
 285                          *      using f_count==0 to spot it.
 286                          */
 287
 288                         if(s->socket && s->socket->file && s->socket->file->f_count)
 289                                 close_fp(s->socket->file);
 290                 }
 291                 else
 292                         s->protinfo.af_unix.marksweep&=~MARKED; /* unmark everything for next collection */
 293         }
 294
 295         in_unix_gc=0;
 296
 297         free_page((long)stack);
 298 }