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 } 293