minix/lib/libsffs/dentry.c

   1 /* This file contains directory entry management and the name lookup hashtable.
   2  *
   3  * The entry points into this file are:
   4  *   init_dentry        initialize the directory entry name lookup hashtable
   5  *   lookup_dentry      find an inode based on parent directory and name
   6  *   add_dentry         add an inode as directory entry to a parent directory
   7  *   del_dentry         delete an inode from its parent directory
   8  *
   9  * Created:
  10  *   April 2009 (D.C. van Moolenbroek)
  11  */
  12
  13 #include "inc.h"
  14
  15 static LIST_HEAD(hash_head, inode) hash_table[NUM_HASH_SLOTS];
  16
  17 static unsigned int hash_dentry(struct inode *parent, char *name);
  18
  19 /*===========================================================================*
  20  *                              init_dentry                                  *
  21  *===========================================================================*/
  22 void init_dentry(void)
  23 {
  24 /* Initialize the names hashtable.
  25  */
  26   int i;
  27
  28   for (i = 0; i < NUM_HASH_SLOTS; i++)
  29         LIST_INIT(&hash_table[i]);
  30 }
  31
  32 /*===========================================================================*
  33  *                              lookup_dentry                                *
  34  *===========================================================================*/
  35 struct inode *lookup_dentry(struct inode *parent, char *name)
  36 {
  37 /* Given a directory inode and a component name, look up the inode associated
  38  * with that directory entry. Return the inode (with increased reference
  39  * count) if found, or NULL otherwise.
  40  */
  41   struct inode *ino;
  42   unsigned int slot;
  43
  44   assert(IS_DIR(parent));
  45
  46   slot = hash_dentry(parent, name);
  47
  48   LIST_FOREACH(ino, &hash_table[slot], i_hash) {
  49         if (compare_name(ino->i_name, name) == TRUE)
  50                 break;
  51   }
  52
  53   if (ino == NULL)
  54         return NULL;
  55
  56   get_inode(ino);
  57
  58   return ino;
  59 }
  60
  61 /*===========================================================================*
  62  *                              add_dentry                                   *
  63  *===========================================================================*/
  64 void add_dentry(struct inode *parent, char *name, struct inode *ino)
  65 {
  66 /* Add an entry to a parent inode, in the form of a new inode, with the given
  67  * name. An entry with this name must not already exist.
  68  */
  69   unsigned int slot;
  70
  71   assert(IS_DIR(parent));
  72   assert(parent->i_ref > 0);
  73   assert(ino->i_ref > 0);
  74   assert(name[0]);
  75   assert(strlen(name) <= NAME_MAX);
  76
  77   link_inode(parent, ino);
  78
  79   strlcpy(ino->i_name, name, sizeof(ino->i_name));
  80
  81   /* hash_add(ino); */
  82   slot = hash_dentry(parent, ino->i_name);
  83   LIST_INSERT_HEAD(&hash_table[slot], ino, i_hash);
  84 }
  85
  86 /*===========================================================================*
  87  *                              del_one_dentry                               *
  88  *===========================================================================*/
  89 static void del_one_dentry(struct inode *ino)
  90 {
  91 /* This inode has become inaccessible by name. Disassociate it from its parent
  92  * and remove it from the names hash table.
  93  */
  94
  95   /* There can and must be exactly one root inode, so don't delete it! */
  96   if (IS_ROOT(ino))
  97         return;
  98
  99   /* INUSE -> DELETED, CACHED -> FREE */
 100
 101   /* Remove the entry from the hashtable.
 102    * Decrease parent's refcount, possibly adding it to the free list.
 103    * Do not touch open handles. Do not add to the free list.
 104    */
 105
 106   assert(ino->i_parent != NULL);
 107
 108   /* hash_del(ino); */
 109   LIST_REMOVE(ino, i_hash);
 110
 111   ino->i_name[0] = 0;
 112
 113   unlink_inode(ino);
 114 }
 115
 116 /*===========================================================================*
 117  *                              del_dentry                                   *
 118  *===========================================================================*/
 119 void del_dentry(struct inode *ino)
 120 {
 121 /* Disassociate an inode from its parent, effectively deleting it. Recursively
 122  * delete all its children as well, fragmenting the deleted branch into single
 123  * inodes.
 124  */
 125   LIST_HEAD(work_list, inode) work_list;
 126   struct inode *child;
 127
 128   del_one_dentry(ino);
 129
 130   /* Quick way out: one directory entry that itself has no children. */
 131   if (!HAS_CHILDREN(ino))
 132         return;
 133
 134   /* Recursively delete all children of the inode as well.
 135    * Iterative version: this is potentially 128 levels deep.
 136    */
 137
 138   LIST_INIT(&work_list);
 139   LIST_INSERT_HEAD(&work_list, ino, i_next);
 140
 141   do {
 142         ino = LIST_FIRST(&work_list);
 143         LIST_REMOVE(ino, i_next);
 144
 145         assert(IS_DIR(ino));
 146
 147         while (!LIST_EMPTY(&ino->i_child)) {
 148                 child = LIST_FIRST(&ino->i_child);
 149                 LIST_REMOVE(child, i_next);
 150
 151                 del_one_dentry(child);
 152
 153                 if (HAS_CHILDREN(child))
 154                         LIST_INSERT_HEAD(&work_list, child, i_next);
 155         }
 156   } while (!LIST_EMPTY(&work_list));
 157 }
 158
 159 /*===========================================================================*
 160  *                              hash_dentry                                  *
 161  *===========================================================================*/
 162 static unsigned int hash_dentry(struct inode *parent, char *name)
 163 {
 164 /* Generate a hash value for a given name. Normalize the name first, so that
 165  * different variations of the name will result in the same hash value.
 166  */
 167   unsigned int val;
 168   char buf[NAME_MAX+1], *p;
 169
 170   dprintf(("%s: hash_dentry for '%s'\n", sffs_name, name));
 171
 172   normalize_name(buf, name);
 173
 174   /* djb2 string hash algorithm, XOR variant */
 175   val = 5381;
 176   for (p = buf; *p; p++)
 177         val = ((val << 5) + val) ^ *p;
 178
 179   /* Mix with inode number: typically, many file names occur in several
 180    * different directories.
 181    */
 182   return (val ^ parent->i_num) % NUM_HASH_SLOTS;
 183 }