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