1 /* VTreeFS - inode.c - inode management */
2
3 #include "inc.h"
4
5 /* The number of inodes and hash table slots. */
6 static unsigned int nr_inodes;
7
8 /* The table of all the inodes. */
9 static struct inode *inode;
10
11 /* The list of unused inodes. */
12 static TAILQ_HEAD(unused_head, inode) unused_inodes;
13
14 /* The hash tables for lookup of <parent,name> and <parent,index> to inode. */
LIST_HEAD(name_head,inode)15 static LIST_HEAD(name_head, inode) *parent_name_head;
16 static LIST_HEAD(index_head, inode) *parent_index_head;
17
18 /* Internal integrity check. */
19 #define CHECK_INODE(node) \
20 do { \
21 assert(node >= &inode[0] && node < &inode[nr_inodes]); \
22 assert((unsigned int)(node - &inode[0]) == node->i_num);\
23 assert(node == &inode[0] || node->i_parent != NULL || \
24 (node->i_flags & I_DELETED)); \
25 } while (0);
26
27 /*
28 * Initialize the inode-related state.
29 */
30 int
31 init_inodes(unsigned int inodes, struct inode_stat * istat,
32 index_t nr_indexed_entries)
33 {
34 struct inode *node;
35 unsigned int i;
36
37 assert(inodes > 0);
38 assert(nr_indexed_entries >= 0);
39
40 nr_inodes = inodes;
41
42 /* Allocate the inode and hash tables. */
43 if ((inode = malloc(nr_inodes * sizeof(inode[0]))) == NULL)
44 return ENOMEM;
45
46 parent_name_head = malloc(nr_inodes * sizeof(parent_name_head[0]));
47 if (parent_name_head == NULL) {
48 free(inode);
49 return ENOMEM;
50 }
51
52 parent_index_head = malloc(nr_inodes * sizeof(parent_index_head[0]));
53 if (parent_index_head == NULL) {
54 free(parent_name_head);
55 free(inode);
56 return ENOMEM;
57 }
58
59 #if DEBUG
60 printf("VTREEFS: allocated %zu+%zu+%zu bytes\n",
61 nr_inodes * sizeof(inode[0]),
62 nr_inodes * sizeof(parent_name_head[0]),
63 nr_inodes * sizeof(parent_index_head[0]));
64 #endif
65
66 /* Initialize the free/unused list. */
67 TAILQ_INIT(&unused_inodes);
68
69 /* Add free inodes to the unused/free list. Skip the root inode. */
70 for (i = 1; i < nr_inodes; i++) {
71 node = &inode[i];
72 node->i_num = i;
73 node->i_name = NULL;
74 node->i_parent = NULL;
75 node->i_count = 0;
76 TAILQ_INIT(&node->i_children);
77 TAILQ_INSERT_HEAD(&unused_inodes, node, i_unused);
78 }
79
80 /* Initialize the hash lists. */
81 for (i = 0; i < nr_inodes; i++) {
82 LIST_INIT(&parent_name_head[i]);
83 LIST_INIT(&parent_index_head[i]);
84 }
85
86 /* Initialize the root inode. */
87 node = &inode[0];
88 node->i_num = 0;
89 node->i_parent = NULL;
90 node->i_count = 0;
91 TAILQ_INIT(&node->i_children);
92 node->i_flags = 0;
93 node->i_index = NO_INDEX;
94 set_inode_stat(node, istat);
95 node->i_indexed = nr_indexed_entries;
96 node->i_cbdata = NULL;
97
98 return OK;
99 }
100
101 /*
102 * Clean up the inode-related state.
103 */
104 void
cleanup_inodes(void)105 cleanup_inodes(void)
106 {
107
108 /* Free the inode and hash tables. */
109 free(parent_index_head);
110 free(parent_name_head);
111 free(inode);
112 }
113
114 /*
115 * Return the hash value of <parent,name> tuple.
116 */
117 static int
parent_name_hash(const struct inode * parent,const char * name)118 parent_name_hash(const struct inode * parent, const char *name)
119 {
120 unsigned int name_hash;
121
122 /* Use the sdbm algorithm to hash the name. */
123 name_hash = sdbm_hash(name, strlen(name));
124
125 /* The parent hash is a simple array entry. */
126 return (parent->i_num ^ name_hash) % nr_inodes;
127 }
128
129 /*
130 * Return the hash value of a <parent,index> tuple.
131 */
132 static int
parent_index_hash(const struct inode * parent,index_t idx)133 parent_index_hash(const struct inode * parent, index_t idx)
134 {
135
136 return (parent->i_num ^ idx) % nr_inodes;
137 }
138
139 /*
140 * Delete a deletable inode to make room for a new inode.
141 */
142 static void
purge_inode(struct inode * parent)143 purge_inode(struct inode * parent)
144 {
145 /*
146 * An inode is deletable if:
147 * - it is in use;
148 * - it is indexed;
149 * - it is not the given parent inode;
150 * - it has a zero reference count;
151 * - it does not have any children.
152 * The first point is true for all inodes, or we would not be here.
153 * The latter two points also imply that I_DELETED is not set.
154 */
155 static int last_checked = 0;
156 struct inode *node;
157 unsigned int count;
158
159 assert(TAILQ_EMPTY(&unused_inodes));
160
161 /*
162 * This should not happen often enough to warrant an extra linked list,
163 * especially as maintenance of that list would be rather error-prone..
164 */
165 for (count = 0; count < nr_inodes; count++) {
166 node = &inode[last_checked];
167 last_checked = (last_checked + 1) % nr_inodes;
168
169 if (node != parent && node->i_index != NO_INDEX &&
170 node->i_count == 0 && TAILQ_EMPTY(&node->i_children)) {
171
172 assert(!(node->i_flags & I_DELETED));
173
174 delete_inode(node);
175
176 break;
177 }
178 }
179 }
180
181 /*
182 * Add an inode.
183 */
184 struct inode *
add_inode(struct inode * parent,const char * name,index_t idx,const struct inode_stat * istat,index_t nr_indexed_entries,cbdata_t cbdata)185 add_inode(struct inode * parent, const char * name, index_t idx,
186 const struct inode_stat * istat, index_t nr_indexed_entries,
187 cbdata_t cbdata)
188 {
189 struct inode *newnode;
190 char *newname;
191 int slot;
192
193 CHECK_INODE(parent);
194 assert(S_ISDIR(parent->i_stat.mode));
195 assert(!(parent->i_flags & I_DELETED));
196 assert(strlen(name) <= NAME_MAX);
197 assert(idx >= 0 || idx == NO_INDEX);
198 assert(istat != NULL);
199 assert(nr_indexed_entries >= 0);
200 assert(get_inode_by_name(parent, name) == NULL);
201
202 /* Get a free inode. Free one up if necessary. */
203 if (TAILQ_EMPTY(&unused_inodes))
204 purge_inode(parent);
205
206 assert(!TAILQ_EMPTY(&unused_inodes));
207
208 newnode = TAILQ_FIRST(&unused_inodes);
209
210 /* Use the static name buffer if the name is short enough. Otherwise,
211 * allocate heap memory for the name.
212 */
213 newname = newnode->i_namebuf;
214 if (strlen(name) > PNAME_MAX &&
215 (newname = malloc(strlen(name) + 1)) == NULL)
216 return NULL;
217
218 TAILQ_REMOVE(&unused_inodes, newnode, i_unused);
219
220 assert(newnode->i_count == 0);
221
222 /* Copy the relevant data to the inode. */
223 newnode->i_parent = parent;
224 newnode->i_name = newname;
225 newnode->i_flags = 0;
226 newnode->i_index = idx;
227 newnode->i_stat = *istat;
228 newnode->i_indexed = nr_indexed_entries;
229 newnode->i_cbdata = cbdata;
230 strcpy(newnode->i_name, name);
231
232 /* Clear the extra data for this inode, if present. */
233 clear_inode_extra(newnode);
234
235 /* Add the inode to the list of children inodes of the parent. */
236 TAILQ_INSERT_HEAD(&parent->i_children, newnode, i_siblings);
237
238 /* Add the inode to the <parent,name> hash table. */
239 slot = parent_name_hash(parent, name);
240 LIST_INSERT_HEAD(&parent_name_head[slot], newnode, i_hname);
241
242 /* Add the inode to the <parent,index> hash table. */
243 if (idx != NO_INDEX) {
244 slot = parent_index_hash(parent, idx);
245 LIST_INSERT_HEAD(&parent_index_head[slot], newnode, i_hindex);
246 }
247
248 return newnode;
249 }
250
251 /*
252 * Return the file system's root inode.
253 */
254 struct inode *
get_root_inode(void)255 get_root_inode(void)
256 {
257
258 /* The root node is always the first node in the inode table. */
259 return &inode[0];
260 }
261
262 /*
263 * Return the name that an inode has in its parent directory.
264 */
265 const char *
get_inode_name(const struct inode * node)266 get_inode_name(const struct inode * node)
267 {
268
269 CHECK_INODE(node);
270 assert(!(node->i_flags & I_DELETED));
271 assert(node->i_name != NULL);
272
273 return node->i_name;
274 }
275
276 /*
277 * Return the index that an inode has in its parent directory.
278 */
279 index_t
get_inode_index(const struct inode * node)280 get_inode_index(const struct inode * node)
281 {
282
283 CHECK_INODE(node);
284
285 return node->i_index;
286 }
287
288 /*
289 * Return the number of indexed slots for the given (directory) inode.
290 */
291 index_t
get_inode_slots(const struct inode * node)292 get_inode_slots(const struct inode * node)
293 {
294
295 CHECK_INODE(node);
296
297 return node->i_indexed;
298 }
299
300 /*
301 * Return the callback data associated with the given inode.
302 */
303 cbdata_t
get_inode_cbdata(const struct inode * node)304 get_inode_cbdata(const struct inode * node)
305 {
306
307 CHECK_INODE(node);
308
309 return node->i_cbdata;
310 }
311
312 /*
313 * Return an inode's parent inode.
314 */
315 struct inode *
get_parent_inode(const struct inode * node)316 get_parent_inode(const struct inode * node)
317 {
318
319 CHECK_INODE(node);
320
321 /* The root inode does not have parent. */
322 if (node == &inode[0])
323 return NULL;
324
325 return node->i_parent;
326 }
327
328 /*
329 * Return a directory's first (non-deleted) child inode.
330 */
331 struct inode *
get_first_inode(const struct inode * parent)332 get_first_inode(const struct inode * parent)
333 {
334 struct inode *node;
335
336 CHECK_INODE(parent);
337 assert(S_ISDIR(parent->i_stat.mode));
338
339 node = TAILQ_FIRST(&parent->i_children);
340
341 while (node != NULL && (node->i_flags & I_DELETED))
342 node = TAILQ_NEXT(node, i_siblings);
343
344 return node;
345 }
346
347 /*
348 * Return a directory's next (non-deleted) child inode.
349 */
350 struct inode *
get_next_inode(const struct inode * previous)351 get_next_inode(const struct inode * previous)
352 {
353 struct inode *node;
354
355 CHECK_INODE(previous);
356
357 node = TAILQ_NEXT(previous, i_siblings);
358
359 while (node != NULL && (node->i_flags & I_DELETED))
360 node = TAILQ_NEXT(node, i_siblings);
361
362 return node;
363 }
364
365 /*
366 * Return the inode number of the given inode.
367 */
368 int
get_inode_number(const struct inode * node)369 get_inode_number(const struct inode * node)
370 {
371
372 CHECK_INODE(node);
373
374 return node->i_num + 1;
375 }
376
377 /*
378 * Retrieve an inode's status.
379 */
380 void
get_inode_stat(const struct inode * node,struct inode_stat * istat)381 get_inode_stat(const struct inode * node, struct inode_stat * istat)
382 {
383
384 CHECK_INODE(node);
385
386 *istat = node->i_stat;
387 }
388
389 /*
390 * Set an inode's status.
391 */
392 void
set_inode_stat(struct inode * node,struct inode_stat * istat)393 set_inode_stat(struct inode * node, struct inode_stat * istat)
394 {
395
396 CHECK_INODE(node);
397
398 node->i_stat = *istat;
399 }
400
401 /*
402 * Look up an inode using a <parent,name> tuple.
403 */
404 struct inode *
get_inode_by_name(const struct inode * parent,const char * name)405 get_inode_by_name(const struct inode * parent, const char * name)
406 {
407 struct inode *node;
408 int slot;
409
410 CHECK_INODE(parent);
411 assert(strlen(name) <= NAME_MAX);
412 assert(S_ISDIR(parent->i_stat.mode));
413
414 /* Get the hash value, and search for the inode. */
415 slot = parent_name_hash(parent, name);
416 LIST_FOREACH(node, &parent_name_head[slot], i_hname) {
417 if (parent == node->i_parent && !strcmp(name, node->i_name))
418 return node; /* found */
419 }
420
421 return NULL;
422 }
423
424 /*
425 * Look up an inode using a <parent,index> tuple.
426 */
427 struct inode *
get_inode_by_index(const struct inode * parent,index_t idx)428 get_inode_by_index(const struct inode * parent, index_t idx)
429 {
430 struct inode *node;
431 int slot;
432
433 CHECK_INODE(parent);
434 assert(S_ISDIR(parent->i_stat.mode));
435 assert(idx >= 0);
436
437 if (idx >= parent->i_indexed)
438 return NULL;
439
440 /* Get the hash value, and search for the inode. */
441 slot = parent_index_hash(parent, idx);
442 LIST_FOREACH(node, &parent_index_head[slot], i_hindex) {
443 if (parent == node->i_parent && idx == node->i_index)
444 return node; /* found */
445 }
446
447 return NULL;
448 }
449
450 /*
451 * Retrieve an inode by inode number.
452 */
453 struct inode *
find_inode(ino_t num)454 find_inode(ino_t num)
455 {
456 struct inode *node;
457
458 node = &inode[num - 1];
459
460 CHECK_INODE(node);
461
462 return node;
463 }
464
465 /*
466 * Retrieve an inode by inode number, and increase its reference count.
467 */
468 struct inode *
get_inode(ino_t num)469 get_inode(ino_t num)
470 {
471 struct inode *node;
472
473 if ((node = find_inode(num)) == NULL)
474 return NULL;
475
476 node->i_count++;
477 return node;
478 }
479
480 /*
481 * Decrease an inode's reference count.
482 */
483 void
put_inode(struct inode * node)484 put_inode(struct inode * node)
485 {
486
487 CHECK_INODE(node);
488 assert(node->i_count > 0);
489
490 node->i_count--;
491
492 /*
493 * If the inode is scheduled for deletion, and has no more references,
494 * actually delete it now.
495 */
496 if ((node->i_flags & I_DELETED) && node->i_count == 0)
497 delete_inode(node);
498 }
499
500 /*
501 * Increase an inode's reference count.
502 */
503 void
ref_inode(struct inode * node)504 ref_inode(struct inode * node)
505 {
506
507 CHECK_INODE(node);
508
509 node->i_count++;
510 }
511
512 /*
513 * Unlink the given node from its parent, if it is still linked in.
514 */
515 static void
unlink_inode(struct inode * node)516 unlink_inode(struct inode * node)
517 {
518 struct inode *parent;
519
520 assert(node->i_flags & I_DELETED);
521
522 parent = node->i_parent;
523 if (parent == NULL)
524 return;
525
526 /* Delete the node from the parent list. */
527 node->i_parent = NULL;
528
529 TAILQ_REMOVE(&parent->i_children, node, i_siblings);
530
531 /* Optionally recheck if the parent can now be deleted. */
532 if (parent->i_flags & I_DELETED)
533 delete_inode(parent);
534 }
535
536 /*
537 * Delete the given inode. If its reference count is nonzero, or it still has
538 * children that cannot be deleted for the same reason, keep the inode around
539 * for the time being. If the node is a directory, keep around its parent so
540 * that we can still do a "cd .." out of it. For these reasons, this function
541 * may be called on an inode more than once before it is actually deleted.
542 */
543 void
delete_inode(struct inode * node)544 delete_inode(struct inode * node)
545 {
546 struct inode *cnode, *ctmp;
547
548 CHECK_INODE(node);
549 assert(node != &inode[0]);
550
551 /*
552 * If the inode was not already scheduled for deletion, partially
553 * remove the node.
554 */
555 if (!(node->i_flags & I_DELETED)) {
556 /* Remove any children first (before I_DELETED is set!). */
557 TAILQ_FOREACH_SAFE(cnode, &node->i_children, i_siblings, ctmp)
558 delete_inode(cnode);
559
560 /* Unhash the inode from the <parent,name> table. */
561 LIST_REMOVE(node, i_hname);
562
563 /* Unhash the inode from the <parent,index> table if needed. */
564 if (node->i_index != NO_INDEX)
565 LIST_REMOVE(node, i_hindex);
566
567 /* Free the name if allocated dynamically. */
568 assert(node->i_name != NULL);
569 if (node->i_name != node->i_namebuf)
570 free(node->i_name);
571 node->i_name = NULL;
572
573 node->i_flags |= I_DELETED;
574
575 /*
576 * If this inode is not a directory, we don't care about being
577 * able to find its parent. Unlink it from the parent now.
578 */
579 if (!S_ISDIR(node->i_stat.mode))
580 unlink_inode(node);
581 }
582
583 if (node->i_count == 0 && TAILQ_EMPTY(&node->i_children)) {
584 /*
585 * If this inode still has a parent at this point, unlink it
586 * now; noone can possibly refer to it anymore.
587 */
588 if (node->i_parent != NULL)
589 unlink_inode(node);
590
591 /* Delete the actual node. */
592 TAILQ_INSERT_HEAD(&unused_inodes, node, i_unused);
593 }
594 }
595
596 /*
597 * Return whether the given inode has been deleted.
598 */
599 int
is_inode_deleted(const struct inode * node)600 is_inode_deleted(const struct inode * node)
601 {
602
603 return (node->i_flags & I_DELETED);
604 }
605
606 /*
607 * Find the inode specified by the request message, and decrease its reference
608 * count.
609 */
610 int
fs_putnode(ino_t ino_nr,unsigned int count)611 fs_putnode(ino_t ino_nr, unsigned int count)
612 {
613 struct inode *node;
614
615 /* Get the inode specified by its number. */
616 if ((node = find_inode(ino_nr)) == NULL)
617 return EINVAL;
618
619 /* Decrease the reference count. */
620 assert(node->i_count >= count);
621
622 node->i_count -= count - 1;
623 put_inode(node);
624
625 return OK;
626 }
627