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