minix/lib/libsffs/inode.c

   1 /* This file deals with inode management.
   2  *
   3  * The entry points into this file are:
   4  *   init_inode         initialize the inode table, return the root inode
   5  *   find_inode         find an inode based on its inode number
   6  *   get_inode          increase the reference count of an inode
   7  *   put_inode          decrease the reference count of an inode
   8  *   link_inode         link an inode as a directory entry to another inode
   9  *   unlink_inode       unlink an inode from its parent directory
  10  *   get_free_inode     return a free inode object
  11  *   have_free_inode    check whether there is a free inode available
  12  *   have_used_inode    check whether any inode is still in use
  13  *   do_putnode         perform the PUTNODE file system call
  14  *
  15  * Created:
  16  *   April 2009 (D.C. van Moolenbroek)
  17  */
  18
  19 #include "inc.h"
  20
  21 static struct inode inodes[NUM_INODES];
  22
  23 static TAILQ_HEAD(free_head, inode) free_list;
  24
  25 /*===========================================================================*
  26  *                              init_inode                                   *
  27  *===========================================================================*/
  28 struct inode *init_inode(void)
  29 {
  30 /* Initialize inode table. Return the root inode.
  31  */
  32   struct inode *ino;
  33   unsigned int i;
  34
  35   TAILQ_INIT(&free_list);
  36
  37   dprintf(("%s: %d inodes, %u bytes each, equals %u bytes\n",
  38         sffs_name, NUM_INODES, sizeof(struct inode), sizeof(inodes)));
  39
  40   /* Mark all inodes except the root inode as free. */
  41   for (i = 1; i < NUM_INODES; i++) {
  42         ino = &inodes[i];
  43         ino->i_parent = NULL;
  44         LIST_INIT(&ino->i_child);
  45         ino->i_num = i + 1;
  46         ino->i_gen = (unsigned short)-1; /* aesthetics */
  47         ino->i_ref = 0;
  48         ino->i_flags = 0;
  49         TAILQ_INSERT_TAIL(&free_list, ino, i_free);
  50   }
  51
  52   /* Initialize and return the root inode. */
  53   ino = &inodes[0];
  54   ino->i_parent = ino;          /* root inode is its own parent */
  55   LIST_INIT(&ino->i_child);
  56   ino->i_num = ROOT_INODE_NR;
  57   ino->i_gen = 0;               /* unused by root node */
  58   ino->i_ref = 1;               /* root inode is hereby in use */
  59   ino->i_flags = I_DIR;         /* root inode is a directory */
  60   ino->i_name[0] = 0;           /* root inode has empty name */
  61
  62   return ino;
  63 }
  64
  65 /*===========================================================================*
  66  *                              find_inode                                   *
  67  *===========================================================================*/
  68 struct inode *find_inode(ino_t ino_nr)
  69 {
  70 /* Get an inode based on its inode number. Do not increase its reference count.
  71  */
  72   struct inode *ino;
  73   int i;
  74
  75   /* Inode 0 (= index -1) is not a valid inode number. */
  76   i = INODE_INDEX(ino_nr);
  77   if (i < 0) {
  78         printf("%s: VFS passed invalid inode number!\n", sffs_name);
  79
  80         return NULL;
  81   }
  82
  83   assert(i < NUM_INODES);
  84
  85   ino = &inodes[i];
  86
  87   /* Make sure the generation number matches. */
  88   if (INODE_GEN(ino_nr) != ino->i_gen) {
  89         printf("%s: VFS passed outdated inode number!\n", sffs_name);
  90
  91         return NULL;
  92   }
  93
  94   /* The VFS/FS protocol only uses referenced inodes. */
  95   if (ino->i_ref == 0)
  96         printf("%s: VFS passed unused inode!\n", sffs_name);
  97
  98   return ino;
  99 }
 100
 101 /*===========================================================================*
 102  *                              get_inode                                    *
 103  *===========================================================================*/
 104 void get_inode(struct inode *ino)
 105 {
 106 /* Increase the given inode's reference count. If both reference and link
 107  * count were zero before, remove the inode from the free list.
 108  */
 109
 110   dprintf(("%s: get_inode(%p) ['%s']\n", sffs_name, ino, ino->i_name));
 111
 112   /* (INUSE, CACHED) -> INUSE */
 113
 114   /* If this is the first reference, remove the node from the free list. */
 115   if (ino->i_ref == 0 && !HAS_CHILDREN(ino))
 116         TAILQ_REMOVE(&free_list, ino, i_free);
 117
 118   ino->i_ref++;
 119
 120   if (ino->i_ref == 0)
 121         panic("inode reference count wrapped");
 122 }
 123
 124 /*===========================================================================*
 125  *                              put_inode                                    *
 126  *===========================================================================*/
 127 void put_inode(struct inode *ino)
 128 {
 129 /* Decrease an inode's reference count. If this count has reached zero, close
 130  * the inode's file handle, if any. If both reference and link count have
 131  * reached zero, mark the inode as cached or free.
 132  */
 133
 134   dprintf(("%s: put_inode(%p) ['%s']\n", sffs_name, ino, ino->i_name));
 135
 136   assert(ino != NULL);
 137   assert(ino->i_ref > 0);
 138
 139   ino->i_ref--;
 140
 141   /* If there are still references to this inode, we're done here. */
 142   if (ino->i_ref > 0)
 143         return;
 144
 145   /* Close any file handle associated with this inode. */
 146   put_handle(ino);
 147
 148   /* Only add the inode to the free list if there are also no links to it. */
 149   if (HAS_CHILDREN(ino))
 150         return;
 151
 152   /* INUSE -> CACHED, DELETED -> FREE */
 153
 154   /* Add the inode to the head or tail of the free list, depending on whether
 155    * it is also deleted (and therefore can never be reused as is).
 156    */
 157   if (ino->i_parent == NULL)
 158         TAILQ_INSERT_HEAD(&free_list, ino, i_free);
 159   else
 160         TAILQ_INSERT_TAIL(&free_list, ino, i_free);
 161 }
 162
 163 /*===========================================================================*
 164  *                              link_inode                                   *
 165  *===========================================================================*/
 166 void link_inode(struct inode *parent, struct inode *ino)
 167 {
 168 /* Link an inode to a parent. If both reference and link count were zero
 169  * before, remove the inode from the free list. This function should only be
 170  * called from add_dentry().
 171  */
 172
 173   /* This can never happen, right? */
 174   if (parent->i_ref == 0 && !HAS_CHILDREN(parent))
 175         TAILQ_REMOVE(&free_list, parent, i_free);
 176
 177   LIST_INSERT_HEAD(&parent->i_child, ino, i_next);
 178
 179   ino->i_parent = parent;
 180 }
 181
 182 /*===========================================================================*
 183  *                              unlink_inode                                 *
 184  *===========================================================================*/
 185 void unlink_inode(struct inode *ino)
 186 {
 187 /* Unlink an inode from its parent. If both reference and link count have
 188  * reached zero, mark the inode as cached or free. This function should only
 189  * be used from del_dentry().
 190  */
 191   struct inode *parent;
 192
 193   parent = ino->i_parent;
 194
 195   LIST_REMOVE(ino, i_next);
 196
 197   if (parent->i_ref == 0 && !HAS_CHILDREN(parent)) {
 198         if (parent->i_parent == NULL)
 199                 TAILQ_INSERT_HEAD(&free_list, parent, i_free);
 200         else
 201                 TAILQ_INSERT_TAIL(&free_list, parent, i_free);
 202   }
 203
 204   ino->i_parent = NULL;
 205 }
 206
 207 /*===========================================================================*
 208  *                              get_free_inode                               *
 209  *===========================================================================*/
 210 struct inode *get_free_inode(void)
 211 {
 212 /* Return a free inode object (with reference count 1), if available.
 213  */
 214   struct inode *ino;
 215
 216   /* [CACHED -> FREE,] FREE -> DELETED */
 217
 218   /* If there are no inodes on the free list, we cannot satisfy the request. */
 219   if (TAILQ_EMPTY(&free_list)) {
 220         printf("%s: out of inodes!\n", sffs_name);
 221
 222         return NULL;
 223   }
 224
 225   ino = TAILQ_FIRST(&free_list);
 226   TAILQ_REMOVE(&free_list, ino, i_free);
 227
 228   assert(ino->i_ref == 0);
 229   assert(!HAS_CHILDREN(ino));
 230
 231   /* If this was a cached inode, free it first. */
 232   if (ino->i_parent != NULL)
 233         del_dentry(ino);
 234
 235   assert(ino->i_parent == NULL);
 236
 237   /* Initialize a subset of its fields */
 238   ino->i_gen++;
 239   ino->i_ref = 1;
 240
 241   return ino;
 242 }
 243
 244 /*===========================================================================*
 245  *                              have_free_inode                              *
 246  *===========================================================================*/
 247 int have_free_inode(void)
 248 {
 249 /* Check whether there are any free inodes at the moment. Kind of lame, but
 250  * this allows for easier error recovery in some places.
 251  */
 252
 253   return !TAILQ_EMPTY(&free_list);
 254 }
 255
 256 /*===========================================================================*
 257  *                              have_used_inode                              *
 258  *===========================================================================*/
 259 int have_used_inode(void)
 260 {
 261 /* Check whether any inodes are still in use, that is, any of the inodes have
 262  * a reference count larger than zero.
 263  */
 264   unsigned int i;
 265
 266   for (i = 0; i < NUM_INODES; i++)
 267         if (inodes[i].i_ref > 0)
 268                 return TRUE;
 269
 270   return FALSE;
 271 }
 272
 273 /*===========================================================================*
 274  *                              do_putnode                                   *
 275  *===========================================================================*/
 276 int do_putnode(ino_t ino_nr, unsigned int count)
 277 {
 278 /* Decrease an inode's reference count.
 279  */
 280   struct inode *ino;
 281
 282   if ((ino = find_inode(ino_nr)) == NULL)
 283         return EINVAL;
 284
 285   if (count > ino->i_ref) return EINVAL;
 286
 287   ino->i_ref -= count - 1;
 288
 289   put_inode(ino);
 290
 291   return OK;
 292 }