minix/lib/libvtreefs/inode.c

   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 * 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
 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
 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
 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
 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 *
 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 *
 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 *
 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
 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
 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
 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 *
 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 *
 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 *
 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
 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
 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
 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 *
 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 *
 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 *
 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 *
 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
 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
 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
 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
 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
 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
 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 }