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