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