net/unix/garbage.c

/* */
This source file includes following definitions.
unix_get_socket
unix_inflight
unix_notinflight
push_stack
pop_stack
empty_stack
maybe_mark_and_push
unix_gc
   1 /*
   2  * NET3:        Garbage Collector For AF_UNIX sockets (STUBS)
   3  *
   4  * Garbage Collector:
   5  *      Copyright (C) Barak A. Pearlmutter.
   6  *      Released under the GPL version 2 or later.
   7  *
   8  * NOTE:
   9  *      We don't actually call this yet. I'm finishing some tests before I
  10  *      enable it. The bold can add it in themselves.
  11  *
  12  * Chopped about by Alan Cox 22/3/96 to make it fit the AF_UNIX socket problem.
  13  * If it doesnt work blame me, it worked when Barak sent it.
  14  *
  15  * Assumptions:
  16  *
  17  *  - object w/ a bit
  18  *  - free list
  19  *
  20  * Current optimizations:
  21  *
  22  *  - explicit stack instead of recursion
  23  *  - tail recurse on first born instead of immediate push/pop
  24  *
  25  *  Future optimizations:
  26  *
  27  *  - don't just push entire root set; process in place
  28  *  - use linked list for internal stack
  29  *
  30  *      This program is free software; you can redistribute it and/or
  31  *      modify it under the terms of the GNU General Public License
  32  *      as published by the Free Software Foundation; either version
  33  *      2 of the License, or (at your option) any later version.
  34  *
  35  *  Fixes:
  36  *
  37  */
  38  
  39 #include <linux/kernel.h>
  40 #include <linux/major.h>
  41 #include <linux/signal.h>
  42 #include <linux/sched.h>
  43 #include <linux/errno.h>
  44 #include <linux/string.h>
  45 #include <linux/stat.h>
  46 #include <linux/socket.h>
  47 #include <linux/un.h>
  48 #include <linux/fcntl.h>
  49 #include <linux/termios.h>
  50 #include <linux/socket.h>
  51 #include <linux/sockios.h>
  52 #include <linux/net.h>
  53 #include <linux/in.h>
  54 #include <linux/fs.h>
  55 #include <linux/malloc.h>
  56 #include <asm/segment.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 
  64 /* Internal data structures and random procedures: */
  65 
  66 #define MAX_STACK 1000          /* Maximum depth of tree (about 1 page) */
  67 static unix_socket **stack;     /* stack of objects to mark */
  68 static int in_stack = 0;        /* first free entry in stack */
  69 
  70 
  71 extern inline unix_socket *unix_get_socket(struct file *filp)
     /*  */
  72 {
  73         struct socket *s;
  74         /*
  75          *      Socket ?
  76          */
  77         if(filp->f_inode->i_mode!=S_IFSOCK)
  78                 return NULL;
  79         s=&(filp->f_inode->u.socket_i);
  80         /*
  81          *      AF_UNIX ?
  82          */
  83         if(s->ops!=&unix_proto_ops)
  84                 return NULL;
  85         /*
  86          *      Got one.
  87          */
  88         return s->data; 
  89 }
  90 
  91 /*
  92  *      Keep the number of times in flight count for the file
  93  *      descriptor if it is for an AF_UNIX socket.
  94  */
  95  
  96 void unix_inflight(struct file *fp)
     /*  */
  97 {
  98         unix_socket *s=unix_get_socket(fp);
  99         if(s)
 100                 s->protinfo.af_unix.inflight++;
 101 }
 102 
 103 void unix_notinflight(struct file *fp)
     /*  */
 104 {
 105         unix_socket *s=unix_get_socket(fp);
 106         if(s)
 107                 s->protinfo.af_unix.inflight--;
 108 }
 109 
 110 
 111 /*
 112  *      Garbage Collector Support Functions
 113  */
 114  
 115 extern inline void push_stack(unix_socket *x)
     /*  */
 116 {
 117         if (in_stack == MAX_STACK)
 118                 panic("can't push onto full stack");
 119         stack[in_stack++] = x;
 120 }
 121 
 122 extern inline unix_socket *pop_stack(void)
     /*  */
 123 {
 124         if (in_stack == 0)
 125                 panic("can't pop empty gc stack");
 126         return stack[--in_stack];
 127 }
 128 
 129 extern inline int empty_stack(void)
     /*  */
 130 {
 131         return in_stack == 0;
 132 }
 133 
 134 extern inline void maybe_mark_and_push(unix_socket *x)
     /*  */
 135 {
 136         if (x->protinfo.af_unix.marksweep&MARKED)
 137                 return;
 138         x->protinfo.af_unix.marksweep|=MARKED;
 139         push_stack(x);
 140 }
 141 
 142 
 143 /* The external entry point: unix_gc() */
 144 
 145 void unix_gc(void)
     /*  */
 146 {
 147         static int in_unix_gc=0;
 148         unix_socket *s;
 149         unix_socket *next;
 150         
 151         /*
 152          *      Avoid a recursive GC.
 153          */
 154 
 155         if(in_unix_gc)
 156                 return;
 157         in_unix_gc=1;
 158         
 159         stack=(unix_socket **)get_free_page(GFP_KERNEL);
 160         
 161         /*
 162          *      Assume everything is now unmarked 
 163          */
 164 
 165         /* Invariant to be maintained:
 166                 - everything marked is either:
 167                 -- (a) on the stack, or
 168                 -- (b) has all of its children marked
 169                 - everything on the stack is always marked
 170                 - nothing is ever pushed onto the stack twice, because:
 171                 -- nothing previously marked is ever pushed on the stack
 172          */
 173 
 174         /*
 175          *      Push root set
 176          */
 177 
 178         for(s=unix_socket_list;s!=NULL;s=s->next)
 179         {
 180                 /*
 181                  *      If all instances of the descriptor are not
 182                  *      in flight we are in use.
 183                  */
 184                 if(s->socket && s->socket->file && s->socket->file->f_count > s->protinfo.af_unix.inflight)
 185                         maybe_mark_and_push(s);
 186         }
 187 
 188         /*
 189          *      Mark phase 
 190          */
 191 
 192         while (!empty_stack())
 193         {
 194                 unix_socket *x = pop_stack();
 195                 unix_socket *f=NULL,*sk;
 196                 struct sk_buff *skb;
 197 tail:           
 198                 skb=skb_peek(&x->receive_queue);
 199                 
 200                 /*
 201                  *      Loop through all but first born 
 202                  */
 203                 
 204                 while(skb && skb != (struct sk_buff *)&x->receive_queue)
 205                 {
 206                         /*
 207                          *      Do we have file descriptors ?
 208                          */
 209                         if(skb->h.filp)
 210                         {
 211                                 /*
 212                                  *      Process the descriptors of this socket
 213                                  */
 214                                 int nfd=*(int *)skb->h.filp;
 215                                 struct file **fp=(struct file **)(skb->h.filp+sizeof(int));
 216                                 while(nfd--)
 217                                 {
 218                                         /*
 219                                          *      Get the socket the fd matches if
 220                                          *      it indeed does so
 221                                          */
 222                                         if((sk=unix_get_socket(*fp++))!=NULL)
 223                                         {
 224                                                 /*
 225                                                  *      Remember the first, mark the
 226                                                  *      rest.
 227                                                  */
 228                                                 if(f==NULL)
 229                                                         f=sk;
 230                                                 else
 231                                                         maybe_mark_and_push(sk);
 232                                         }
 233                                 }
 234                         }
 235                         skb=skb->next;
 236                 }
 237                 /*
 238                  *      Handle first born specially 
 239                  */
 240 
 241                 if (f) 
 242                 {
 243                         if (!(f->protinfo.af_unix.marksweep&MARKED))
 244                         {
 245                                 f->protinfo.af_unix.marksweep|=MARKED;
 246                                 x=f;
 247                                 f=NULL;
 248                                 goto tail;
 249                         }
 250                 }
 251         }
 252 
 253         /*
 254          *      Sweep phase.  NOTE: this part dominates the time complexity 
 255          */
 256 
 257         for(s=unix_socket_list;s!=NULL;s=next)
 258         {
 259                 next=s->next;
 260                 if (!(s->protinfo.af_unix.marksweep&MARKED))
 261                 {
 262                         /*
 263                          *      We exist only in the passing tree of sockets
 264                          *      that is no longer connected to active descriptors
 265                          *      Time to die..
 266                          */
 267                         if(s->socket && s->socket->file)
 268                                 close_fp(s->socket->file);
 269                 }
 270                 else
 271                         s->protinfo.af_unix.marksweep&=~MARKED; /* unmark everything for next collection */
 272         }
 273         
 274         in_unix_gc=0;
 275         
 276         free_page((long)stack);
 277 }
/* */
root/net/unix/garbage.c

DEFINITIONS
