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