aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBob Copeland <me@bobcopeland.com>2008-07-25 22:45:16 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2008-07-26 15:00:05 -0400
commita3ab7155ea21aadc8a4d5687e91b3d876973185e (patch)
tree40f74b9c4e38d12bbbbc269232fb8a5b7ad9448c
parent555e3775ced1d05203934fc6529bbf0560dd8733 (diff)
omfs: add directory routines
Add lookup and directory management routines for OMFS. The filesystem uses hashing based on the filename and stores collisions, unordered, in siblings of files' inode structures. To support telldir, the current position in the hash table is encoded in fpos. Signed-off-by: Bob Copeland <me@bobcopeland.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
-rw-r--r--fs/omfs/dir.c504
1 files changed, 504 insertions, 0 deletions
diff --git a/fs/omfs/dir.c b/fs/omfs/dir.c
new file mode 100644
index 000000000000..05a5bc31e4bd
--- /dev/null
+++ b/fs/omfs/dir.c
@@ -0,0 +1,504 @@
1/*
2 * OMFS (as used by RIO Karma) directory operations.
3 * Copyright (C) 2005 Bob Copeland <me@bobcopeland.com>
4 * Released under GPL v2.
5 */
6
7#include <linux/fs.h>
8#include <linux/ctype.h>
9#include <linux/buffer_head.h>
10#include "omfs.h"
11
12static int omfs_hash(const char *name, int namelen, int mod)
13{
14 int i, hash = 0;
15 for (i = 0; i < namelen; i++)
16 hash ^= tolower(name[i]) << (i % 24);
17 return hash % mod;
18}
19
20/*
21 * Finds the bucket for a given name and reads the containing block;
22 * *ofs is set to the offset of the first list entry.
23 */
24static struct buffer_head *omfs_get_bucket(struct inode *dir,
25 const char *name, int namelen, int *ofs)
26{
27 int nbuckets = (dir->i_size - OMFS_DIR_START)/8;
28 int block = clus_to_blk(OMFS_SB(dir->i_sb), dir->i_ino);
29 int bucket = omfs_hash(name, namelen, nbuckets);
30
31 *ofs = OMFS_DIR_START + bucket * 8;
32 return sb_bread(dir->i_sb, block);
33}
34
35static struct buffer_head *omfs_scan_list(struct inode *dir, u64 block,
36 const char *name, int namelen,
37 u64 *prev_block)
38{
39 struct buffer_head *bh;
40 struct omfs_inode *oi;
41 int err = -ENOENT;
42 *prev_block = ~0;
43
44 while (block != ~0) {
45 bh = sb_bread(dir->i_sb,
46 clus_to_blk(OMFS_SB(dir->i_sb), block));
47 if (!bh) {
48 err = -EIO;
49 goto err;
50 }
51
52 oi = (struct omfs_inode *) bh->b_data;
53 if (omfs_is_bad(OMFS_SB(dir->i_sb), &oi->i_head, block)) {
54 brelse(bh);
55 goto err;
56 }
57
58 if (strncmp(oi->i_name, name, namelen) == 0)
59 return bh;
60
61 *prev_block = block;
62 block = be64_to_cpu(oi->i_sibling);
63 brelse(bh);
64 }
65err:
66 return ERR_PTR(err);
67}
68
69static struct buffer_head *omfs_find_entry(struct inode *dir,
70 const char *name, int namelen)
71{
72 struct buffer_head *bh;
73 int ofs;
74 u64 block, dummy;
75
76 bh = omfs_get_bucket(dir, name, namelen, &ofs);
77 if (!bh)
78 return ERR_PTR(-EIO);
79
80 block = be64_to_cpu(*((__be64 *) &bh->b_data[ofs]));
81 brelse(bh);
82
83 return omfs_scan_list(dir, block, name, namelen, &dummy);
84}
85
86int omfs_make_empty(struct inode *inode, struct super_block *sb)
87{
88 struct omfs_sb_info *sbi = OMFS_SB(sb);
89 int block = clus_to_blk(sbi, inode->i_ino);
90 struct buffer_head *bh;
91 struct omfs_inode *oi;
92
93 bh = sb_bread(sb, block);
94 if (!bh)
95 return -ENOMEM;
96
97 memset(bh->b_data, 0, sizeof(struct omfs_inode));
98
99 if (inode->i_mode & S_IFDIR) {
100 memset(&bh->b_data[OMFS_DIR_START], 0xff,
101 sbi->s_sys_blocksize - OMFS_DIR_START);
102 } else
103 omfs_make_empty_table(bh, OMFS_EXTENT_START);
104
105 oi = (struct omfs_inode *) bh->b_data;
106 oi->i_head.h_self = cpu_to_be64(inode->i_ino);
107 oi->i_sibling = ~0ULL;
108
109 mark_buffer_dirty(bh);
110 brelse(bh);
111 return 0;
112}
113
114static int omfs_add_link(struct dentry *dentry, struct inode *inode)
115{
116 struct inode *dir = dentry->d_parent->d_inode;
117 const char *name = dentry->d_name.name;
118 int namelen = dentry->d_name.len;
119 struct omfs_inode *oi;
120 struct buffer_head *bh;
121 u64 block;
122 __be64 *entry;
123 int ofs;
124
125 /* just prepend to head of queue in proper bucket */
126 bh = omfs_get_bucket(dir, name, namelen, &ofs);
127 if (!bh)
128 goto out;
129
130 entry = (__be64 *) &bh->b_data[ofs];
131 block = be64_to_cpu(*entry);
132 *entry = cpu_to_be64(inode->i_ino);
133 mark_buffer_dirty(bh);
134 brelse(bh);
135
136 /* now set the sibling and parent pointers on the new inode */
137 bh = sb_bread(dir->i_sb, clus_to_blk(OMFS_SB(dir->i_sb), inode->i_ino));
138 if (!bh)
139 goto out;
140
141 oi = (struct omfs_inode *) bh->b_data;
142 memcpy(oi->i_name, name, namelen);
143 memset(oi->i_name + namelen, 0, OMFS_NAMELEN - namelen);
144 oi->i_sibling = cpu_to_be64(block);
145 oi->i_parent = cpu_to_be64(dir->i_ino);
146 mark_buffer_dirty(bh);
147 brelse(bh);
148
149 dir->i_ctime = CURRENT_TIME_SEC;
150
151 /* mark affected inodes dirty to rebuild checksums */
152 mark_inode_dirty(dir);
153 mark_inode_dirty(inode);
154 return 0;
155out:
156 return -ENOMEM;
157}
158
159static int omfs_delete_entry(struct dentry *dentry)
160{
161 struct inode *dir = dentry->d_parent->d_inode;
162 struct inode *dirty;
163 const char *name = dentry->d_name.name;
164 int namelen = dentry->d_name.len;
165 struct omfs_inode *oi;
166 struct buffer_head *bh, *bh2;
167 __be64 *entry, next;
168 u64 block, prev;
169 int ofs;
170 int err = -ENOMEM;
171
172 /* delete the proper node in the bucket's linked list */
173 bh = omfs_get_bucket(dir, name, namelen, &ofs);
174 if (!bh)
175 goto out;
176
177 entry = (__be64 *) &bh->b_data[ofs];
178 block = be64_to_cpu(*entry);
179
180 bh2 = omfs_scan_list(dir, block, name, namelen, &prev);
181 if (IS_ERR(bh2)) {
182 err = PTR_ERR(bh2);
183 goto out_free_bh;
184 }
185
186 oi = (struct omfs_inode *) bh2->b_data;
187 next = oi->i_sibling;
188 brelse(bh2);
189
190 if (prev != ~0) {
191 /* found in middle of list, get list ptr */
192 brelse(bh);
193 bh = sb_bread(dir->i_sb,
194 clus_to_blk(OMFS_SB(dir->i_sb), prev));
195 if (!bh)
196 goto out;
197
198 oi = (struct omfs_inode *) bh->b_data;
199 entry = &oi->i_sibling;
200 }
201
202 *entry = next;
203 mark_buffer_dirty(bh);
204
205 if (prev != ~0) {
206 dirty = omfs_iget(dir->i_sb, prev);
207 if (!IS_ERR(dirty)) {
208 mark_inode_dirty(dirty);
209 iput(dirty);
210 }
211 }
212
213 err = 0;
214out_free_bh:
215 brelse(bh);
216out:
217 return err;
218}
219
220static int omfs_dir_is_empty(struct inode *inode)
221{
222 int nbuckets = (inode->i_size - OMFS_DIR_START) / 8;
223 struct buffer_head *bh;
224 u64 *ptr;
225 int i;
226
227 bh = sb_bread(inode->i_sb, clus_to_blk(OMFS_SB(inode->i_sb),
228 inode->i_ino));
229
230 if (!bh)
231 return 0;
232
233 ptr = (u64 *) &bh->b_data[OMFS_DIR_START];
234
235 for (i = 0; i < nbuckets; i++, ptr++)
236 if (*ptr != ~0)
237 break;
238
239 brelse(bh);
240 return *ptr != ~0;
241}
242
243static int omfs_unlink(struct inode *dir, struct dentry *dentry)
244{
245 int ret;
246 struct inode *inode = dentry->d_inode;
247
248 ret = omfs_delete_entry(dentry);
249 if (ret)
250 goto end_unlink;
251
252 inode_dec_link_count(inode);
253 mark_inode_dirty(dir);
254
255end_unlink:
256 return ret;
257}
258
259static int omfs_rmdir(struct inode *dir, struct dentry *dentry)
260{
261 int err = -ENOTEMPTY;
262 struct inode *inode = dentry->d_inode;
263
264 if (omfs_dir_is_empty(inode)) {
265 err = omfs_unlink(dir, dentry);
266 if (!err)
267 inode_dec_link_count(inode);
268 }
269 return err;
270}
271
272static int omfs_add_node(struct inode *dir, struct dentry *dentry, int mode)
273{
274 int err;
275 struct inode *inode = omfs_new_inode(dir, mode);
276
277 if (IS_ERR(inode))
278 return PTR_ERR(inode);
279
280 err = omfs_make_empty(inode, dir->i_sb);
281 if (err)
282 goto out_free_inode;
283
284 err = omfs_add_link(dentry, inode);
285 if (err)
286 goto out_free_inode;
287
288 d_instantiate(dentry, inode);
289 return 0;
290
291out_free_inode:
292 iput(inode);
293 return err;
294}
295
296static int omfs_mkdir(struct inode *dir, struct dentry *dentry, int mode)
297{
298 return omfs_add_node(dir, dentry, mode | S_IFDIR);
299}
300
301static int omfs_create(struct inode *dir, struct dentry *dentry, int mode,
302 struct nameidata *nd)
303{
304 return omfs_add_node(dir, dentry, mode | S_IFREG);
305}
306
307static struct dentry *omfs_lookup(struct inode *dir, struct dentry *dentry,
308 struct nameidata *nd)
309{
310 struct buffer_head *bh;
311 struct inode *inode = NULL;
312
313 if (dentry->d_name.len > OMFS_NAMELEN)
314 return ERR_PTR(-ENAMETOOLONG);
315
316 bh = omfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len);
317 if (!IS_ERR(bh)) {
318 struct omfs_inode *oi = (struct omfs_inode *)bh->b_data;
319 ino_t ino = be64_to_cpu(oi->i_head.h_self);
320 brelse(bh);
321 inode = omfs_iget(dir->i_sb, ino);
322 if (IS_ERR(inode))
323 return ERR_CAST(inode);
324 }
325 d_add(dentry, inode);
326 return NULL;
327}
328
329/* sanity check block's self pointer */
330int omfs_is_bad(struct omfs_sb_info *sbi, struct omfs_header *header,
331 u64 fsblock)
332{
333 int is_bad;
334 u64 ino = be64_to_cpu(header->h_self);
335 is_bad = ((ino != fsblock) || (ino < sbi->s_root_ino) ||
336 (ino > sbi->s_num_blocks));
337
338 if (is_bad)
339 printk(KERN_WARNING "omfs: bad hash chain detected\n");
340
341 return is_bad;
342}
343
344static int omfs_fill_chain(struct file *filp, void *dirent, filldir_t filldir,
345 u64 fsblock, int hindex)
346{
347 struct inode *dir = filp->f_dentry->d_inode;
348 struct buffer_head *bh;
349 struct omfs_inode *oi;
350 u64 self;
351 int res = 0;
352 unsigned char d_type;
353
354 /* follow chain in this bucket */
355 while (fsblock != ~0) {
356 bh = sb_bread(dir->i_sb, clus_to_blk(OMFS_SB(dir->i_sb),
357 fsblock));
358 if (!bh)
359 goto out;
360
361 oi = (struct omfs_inode *) bh->b_data;
362 if (omfs_is_bad(OMFS_SB(dir->i_sb), &oi->i_head, fsblock)) {
363 brelse(bh);
364 goto out;
365 }
366
367 self = fsblock;
368 fsblock = be64_to_cpu(oi->i_sibling);
369
370 /* skip visited nodes */
371 if (hindex) {
372 hindex--;
373 brelse(bh);
374 continue;
375 }
376
377 d_type = (oi->i_type == OMFS_DIR) ? DT_DIR : DT_REG;
378
379 res = filldir(dirent, oi->i_name, strnlen(oi->i_name,
380 OMFS_NAMELEN), filp->f_pos, self, d_type);
381 if (res == 0)
382 filp->f_pos++;
383 brelse(bh);
384 }
385out:
386 return res;
387}
388
389static int omfs_rename(struct inode *old_dir, struct dentry *old_dentry,
390 struct inode *new_dir, struct dentry *new_dentry)
391{
392 struct inode *new_inode = new_dentry->d_inode;
393 struct inode *old_inode = old_dentry->d_inode;
394 struct buffer_head *bh;
395 int is_dir;
396 int err;
397
398 is_dir = S_ISDIR(old_inode->i_mode);
399
400 if (new_inode) {
401 /* overwriting existing file/dir */
402 err = -ENOTEMPTY;
403 if (is_dir && !omfs_dir_is_empty(new_inode))
404 goto out;
405
406 err = -ENOENT;
407 bh = omfs_find_entry(new_dir, new_dentry->d_name.name,
408 new_dentry->d_name.len);
409 if (IS_ERR(bh))
410 goto out;
411 brelse(bh);
412
413 err = omfs_unlink(new_dir, new_dentry);
414 if (err)
415 goto out;
416 }
417
418 /* since omfs locates files by name, we need to unlink _before_
419 * adding the new link or we won't find the old one */
420 inode_inc_link_count(old_inode);
421 err = omfs_unlink(old_dir, old_dentry);
422 if (err) {
423 inode_dec_link_count(old_inode);
424 goto out;
425 }
426
427 err = omfs_add_link(new_dentry, old_inode);
428 if (err)
429 goto out;
430
431 old_inode->i_ctime = CURRENT_TIME_SEC;
432out:
433 return err;
434}
435
436static int omfs_readdir(struct file *filp, void *dirent, filldir_t filldir)
437{
438 struct inode *dir = filp->f_dentry->d_inode;
439 struct buffer_head *bh;
440 loff_t offset, res;
441 unsigned int hchain, hindex;
442 int nbuckets;
443 u64 fsblock;
444 int ret = -EINVAL;
445
446 if (filp->f_pos >> 32)
447 goto success;
448
449 switch ((unsigned long) filp->f_pos) {
450 case 0:
451 if (filldir(dirent, ".", 1, 0, dir->i_ino, DT_DIR) < 0)
452 goto success;
453 filp->f_pos++;
454 /* fall through */
455 case 1:
456 if (filldir(dirent, "..", 2, 1,
457 parent_ino(filp->f_dentry), DT_DIR) < 0)
458 goto success;
459 filp->f_pos = 1 << 20;
460 /* fall through */
461 }
462
463 nbuckets = (dir->i_size - OMFS_DIR_START) / 8;
464
465 /* high 12 bits store bucket + 1 and low 20 bits store hash index */
466 hchain = (filp->f_pos >> 20) - 1;
467 hindex = filp->f_pos & 0xfffff;
468
469 bh = sb_bread(dir->i_sb, clus_to_blk(OMFS_SB(dir->i_sb), dir->i_ino));
470 if (!bh)
471 goto out;
472
473 offset = OMFS_DIR_START + hchain * 8;
474
475 for (; hchain < nbuckets; hchain++, offset += 8) {
476 fsblock = be64_to_cpu(*((__be64 *) &bh->b_data[offset]));
477
478 res = omfs_fill_chain(filp, dirent, filldir, fsblock, hindex);
479 hindex = 0;
480 if (res < 0)
481 break;
482
483 filp->f_pos = (hchain+2) << 20;
484 }
485 brelse(bh);
486success:
487 ret = 0;
488out:
489 return ret;
490}
491
492struct inode_operations omfs_dir_inops = {
493 .lookup = omfs_lookup,
494 .mkdir = omfs_mkdir,
495 .rename = omfs_rename,
496 .create = omfs_create,
497 .unlink = omfs_unlink,
498 .rmdir = omfs_rmdir,
499};
500
501struct file_operations omfs_dir_operations = {
502 .read = generic_read_dir,
503 .readdir = omfs_readdir,
504};