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 *===========================================================================*/
init_inode(void)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 *===========================================================================*/
find_inode(ino_t ino_nr)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 *===========================================================================*/
get_inode(struct inode * ino)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 *===========================================================================*/
put_inode(struct inode * ino)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 *===========================================================================*/
link_inode(struct inode * parent,struct inode * ino)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 *===========================================================================*/
unlink_inode(struct inode * ino)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 *===========================================================================*/
get_free_inode(void)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 *===========================================================================*/
have_free_inode(void)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 *===========================================================================*/
have_used_inode(void)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 *===========================================================================*/
do_putnode(ino_t ino_nr,unsigned int count)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