lib/libvtreefs/inode.c

   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.REQ_INODE_NR)) == NULL)
 593                 return EINVAL;
 594
 595         /* Decrease the reference count. */
 596         node->i_count -= fs_m_in.REQ_COUNT - 1;
 597
 598         assert(node->i_count > 0);
 599
 600         put_inode(node);
 601
 602         return OK;
 603 }