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
LIST_HEAD(hash_head,inode)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 *===========================================================================*/
lookup_dentry(struct inode * parent,char * name)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 *===========================================================================*/
add_dentry(struct inode * parent,char * name,struct inode * ino)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 *===========================================================================*/
del_one_dentry(struct inode * ino)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 *===========================================================================*/
del_dentry(struct inode * ino)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 *===========================================================================*/
hash_dentry(struct inode * parent,char * name)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