ReactOS 0.4.15-dev-5672-gf73ac17
htree.c
Go to the documentation of this file.
1/*
2 * COPYRIGHT: See COPYRIGHT.TXT
3 * PROJECT: Ext2 File System Driver for WinNT/2K/XP
4 * FILE: lock.c
5 * PROGRAMMER: Matt Wu <mattwu@163.com>
6 * HOMEPAGE: http://www.ext2fsd.com
7 * UPDATE HISTORY:
8 * Copied from linux/lib/halfmd4.c
9 * linux/fs/ext3/hash.c
10 */
11
12/* INCLUDES *****************************************************************/
13
14#include "ext2fs.h"
15
16#ifdef EXT2_HTREE_INDEX
17
18#define DX_DEBUG 0
19
20#if DX_DEBUG
21#define dxtrace(command) command
22#else
23#define dxtrace(command)
24#endif
25
26#ifndef swap
27#define swap(type, x, y) do { type z = x; x = y; y = z; } while (0)
28#endif
29
30/* F, G and H are basic MD4 functions: selection, majority, parity */
31#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
32#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
33#define H(x, y, z) ((x) ^ (y) ^ (z))
34
35/*
36 * The generic round function. The application is so specific that
37 * we don't bother protecting all the arguments with parens, as is generally
38 * good macro practice, in favor of extra legibility.
39 * Rotation is separate from addition to prevent recomputation
40 */
41#define ROUND(f, a, b, c, d, x, s) \
42 (a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s)))
43#define K1 0
44#define K2 013240474631
45#define K3 015666365641
46
47/*
48 * Basic cut-down MD4 transform. Returns only 32 bits of result.
49 */
50__u32 half_md4_transform(__u32 buf[4], __u32 const in[8])
51{
52 __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3];
53
54 /* Round 1 */
55 ROUND(F, a, b, c, d, in[0] + K1, 3);
56 ROUND(F, d, a, b, c, in[1] + K1, 7);
57 ROUND(F, c, d, a, b, in[2] + K1, 11);
58 ROUND(F, b, c, d, a, in[3] + K1, 19);
59 ROUND(F, a, b, c, d, in[4] + K1, 3);
60 ROUND(F, d, a, b, c, in[5] + K1, 7);
61 ROUND(F, c, d, a, b, in[6] + K1, 11);
62 ROUND(F, b, c, d, a, in[7] + K1, 19);
63
64 /* Round 2 */
65 ROUND(G, a, b, c, d, in[1] + K2, 3);
66 ROUND(G, d, a, b, c, in[3] + K2, 5);
67 ROUND(G, c, d, a, b, in[5] + K2, 9);
68 ROUND(G, b, c, d, a, in[7] + K2, 13);
69 ROUND(G, a, b, c, d, in[0] + K2, 3);
70 ROUND(G, d, a, b, c, in[2] + K2, 5);
71 ROUND(G, c, d, a, b, in[4] + K2, 9);
72 ROUND(G, b, c, d, a, in[6] + K2, 13);
73
74 /* Round 3 */
75 ROUND(H, a, b, c, d, in[3] + K3, 3);
76 ROUND(H, d, a, b, c, in[7] + K3, 9);
77 ROUND(H, c, d, a, b, in[2] + K3, 11);
78 ROUND(H, b, c, d, a, in[6] + K3, 15);
79 ROUND(H, a, b, c, d, in[1] + K3, 3);
80 ROUND(H, d, a, b, c, in[5] + K3, 9);
81 ROUND(H, c, d, a, b, in[0] + K3, 11);
82 ROUND(H, b, c, d, a, in[4] + K3, 15);
83
84 buf[0] += a;
85 buf[1] += b;
86 buf[2] += c;
87 buf[3] += d;
88
89 return buf[1]; /* "most hashed" word */
90}
91
92#define DELTA 0x9E3779B9
93
94static void TEA_transform(__u32 buf[4], __u32 const in[])
95{
96 __u32 sum = 0;
97 __u32 b0 = buf[0], b1 = buf[1];
98 __u32 a = in[0], b = in[1], c = in[2], d = in[3];
99 int n = 16;
100
101 do {
102 sum += DELTA;
103 b0 += ((b1 << 4)+a) ^ (b1+sum) ^ ((b1 >> 5)+b);
104 b1 += ((b0 << 4)+c) ^ (b0+sum) ^ ((b0 >> 5)+d);
105 } while (--n);
106
107 buf[0] += b0;
108 buf[1] += b1;
109}
110
111
112/* The old legacy hash */
113static __u32 dx_hack_hash_unsigned(const char *name, int len)
114{
115 __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
116 const unsigned char *ucp = (const unsigned char *) name;
117
118 while (len--) {
119 hash = hash1 + (hash0 ^ (((int) *ucp++) * 7152373));
120
121 if (hash & 0x80000000)
122 hash -= 0x7fffffff;
123 hash1 = hash0;
124 hash0 = hash;
125 }
126 return hash0 << 1;
127}
128
129static __u32 dx_hack_hash_signed(const char *name, int len)
130{
131 __u32 hash, hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
132 const signed char *scp = (const signed char *) name;
133
134 while (len--) {
135 hash = hash1 + (hash0 ^ (((int) *scp++) * 7152373));
136
137 if (hash & 0x80000000)
138 hash -= 0x7fffffff;
139 hash1 = hash0;
140 hash0 = hash;
141 }
142 return hash0 << 1;
143}
144
145static void str2hashbuf_signed(const char *msg, int len, __u32 *buf, int num)
146{
147 __u32 pad, val;
148 int i;
149 const signed char *scp = (const signed char *) msg;
150
151 pad = (__u32)len | ((__u32)len << 8);
152 pad |= pad << 16;
153
154 val = pad;
155 if (len > num*4)
156 len = num * 4;
157 for (i = 0; i < len; i++) {
158 if ((i % 4) == 0)
159 val = pad;
160 val = ((int) scp[i]) + (val << 8);
161 if ((i % 4) == 3) {
162 *buf++ = val;
163 val = pad;
164 num--;
165 }
166 }
167 if (--num >= 0)
168 *buf++ = val;
169 while (--num >= 0)
170 *buf++ = pad;
171}
172
173static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num)
174{
175 __u32 pad, val;
176 int i;
177 const unsigned char *ucp = (const unsigned char *) msg;
178
179 pad = (__u32)len | ((__u32)len << 8);
180 pad |= pad << 16;
181
182 val = pad;
183 if (len > num*4)
184 len = num * 4;
185 for (i = 0; i < len; i++) {
186 if ((i % 4) == 0)
187 val = pad;
188 val = ((int) ucp[i]) + (val << 8);
189 if ((i % 4) == 3) {
190 *buf++ = val;
191 val = pad;
192 num--;
193 }
194 }
195 if (--num >= 0)
196 *buf++ = val;
197 while (--num >= 0)
198 *buf++ = pad;
199}
200
201
202#endif /* EXT2_HTREE_INDEX */
203
205{
206 LARGE_INTEGER SysTime;
207 KeQuerySystemTime(&SysTime);
208
209 return Ext2LinuxTime(SysTime);
210}
211
212void ext3_warning (struct super_block * sb, const char * function,
213 char * fmt, ...)
214{
215#if DX_DEBUG
217
218 va_start(args, fmt);
219 printk("EXT3-fs warning (device %s): %s: ",
220 sb->s_id, function);
221 printk(fmt, args);
222 printk("\n");
223 va_end(args);
224#endif
225}
226
227
228/* ext3_bread is safe for meta-data blocks. it's not safe to read file data,
229 since file data is managed by file cache, not volume cache */
230struct buffer_head *ext3_bread(struct ext2_icb *icb, struct inode *inode,
231 unsigned long block, int *err)
232{
233 struct buffer_head * bh = NULL;
235 ULONG lbn = 0, num = 0;
236
238
239 /* for symlink file, read it's target instead */
240 if (NULL != Mcb && IsMcbSymLink(Mcb))
241 Mcb = Mcb->Target;
242 if (NULL == Mcb) {
243 *err = -EINVAL;
244 return NULL;
245 }
246
247 /* mapping file offset to ext2 block */
248 if (INODE_HAS_EXTENT(&Mcb->Inode)) {
249 status = Ext2MapExtent(icb, inode->i_sb->s_priv,
250 Mcb, block, FALSE,
251 &lbn, &num);
252 } else {
253 status = Ext2MapIndirect(icb, inode->i_sb->s_priv,
254 Mcb, block, FALSE,
255 &lbn, &num);
256 }
257
258 if (!NT_SUCCESS(status)) {
260 return bh;
261 }
262
263 bh = sb_getblk(inode->i_sb, lbn);
264 if (!bh) {
265 *err = -ENOMEM;
266 return bh;
267 }
268 if (buffer_uptodate(bh))
269 return bh;
270
271 *err = bh_submit_read(bh);
272 if (*err) {
273 __brelse(bh);
274 return NULL;
275 }
276 return bh;
277}
278
279struct buffer_head *ext3_append(struct ext2_icb *icb, struct inode *inode,
280 ext3_lblk_t *block, int *err)
281{
283 PEXT2_FCB dcb = mcb->Fcb;
285
286 ASSERT(dcb);
287 ASSERT(inode == dcb->Inode);
288
289 /* allocate new block since there's no space for us */
290 *block = (ext3_lblk_t)(inode->i_size >> inode->i_sb->s_blocksize_bits);
291 dcb->Header.AllocationSize.QuadPart += dcb->Vcb->BlockSize;
292 status = Ext2ExpandFile(icb, dcb->Vcb, mcb, &(dcb->Header.AllocationSize));
293 if (NT_SUCCESS(status)) {
294
295 /* update Dcb */
296 dcb->Header.ValidDataLength = dcb->Header.FileSize = dcb->Header.AllocationSize;
297 mcb->Inode.i_size = dcb->Header.AllocationSize.QuadPart;
298
299 /* save parent directory's inode */
300 Ext2SaveInode(icb, dcb->Vcb, inode);
301 }
302
303 return ext3_bread(icb, inode, *block, err);
304}
305
306
308{
309 inode->i_nlink++;
310}
311
313{
314 inode->i_nlink--;
315}
316
318{
319 unsigned char type = 0;
320
321 switch (mode & S_IFMT) {
322 case S_IFREG:
324 break;
325 case S_IFDIR:
327 break;
328 case S_IFCHR:
330 break;
331 case S_IFBLK:
333 break;
334 case S_IFIFO:
336 break;
337 case S_IFSOCK:
339 break;
340 case S_IFLNK:
342 }
343
344 return type;
345};
346
348 struct ext3_dir_entry_2 *de,
350{
353}
354
355/*
356 * ext3_mark_inode_dirty is somewhat expensive, so unlike ext2 we
357 * do not perform it in these functions. We perform it at the call site,
358 * if it is needed.
359 */
360int ext3_mark_inode_dirty(struct ext2_icb *icb, struct inode *in)
361{
362 if (Ext2SaveInode(icb, in->i_sb->s_priv, in))
363 return 0;
364
365 return -ENOMEM;
366}
367
369{
372 EXT3_I(inode)->i_flags &= ~EXT3_INDEX_FL;
373}
374
375/*
376 * Add a new entry into a directory (leaf) block. If de is non-NULL,
377 * it points to a directory entry which is guaranteed to be large
378 * enough for new directory entry. If de is NULL, then
379 * add_dirent_to_buf will attempt search the directory block for
380 * space. It will return -ENOSPC if no space is available, and -EIO
381 * and -EEXIST if directory entry already exists.
382 *
383 * NOTE! bh is NOT released in the case where ENOSPC is returned. In
384 * all other cases bh is released.
385 */
386int add_dirent_to_buf(struct ext2_icb *icb, struct dentry *dentry,
387 struct inode *inode, struct ext3_dir_entry_2 *de,
388 struct buffer_head *bh)
389{
390 struct inode *dir = dentry->d_parent->d_inode;
391 const char *name = dentry->d_name.name;
392 int namelen = dentry->d_name.len;
393 unsigned int offset = 0;
394 unsigned short reclen;
395 int nlen, rlen, err;
396 char *top;
397
398 reclen = EXT3_DIR_REC_LEN(namelen);
399 if (!de) {
400 de = (struct ext3_dir_entry_2 *)bh->b_data;
401 top = bh->b_data + dir->i_sb->s_blocksize - reclen;
402 while ((char *) de <= top) {
403 if (!ext3_check_dir_entry("ext3_add_entry", dir, de,
404 bh, offset)) {
405 __brelse(bh);
406 return -EIO;
407 }
408 if (ext3_match(namelen, name, de)) {
409 __brelse(bh);
410 return -EEXIST;
411 }
412 nlen = EXT3_DIR_REC_LEN(de->name_len);
414 if ((de->inode? rlen - nlen: rlen) >= reclen)
415 break;
416 de = (struct ext3_dir_entry_2 *)((char *)de + rlen);
417 offset += rlen;
418 }
419 if ((char *) de > top)
420 return -ENOSPC;
421 }
422
423 /* By now the buffer is marked for journaling */
424 nlen = EXT3_DIR_REC_LEN(de->name_len);
426 if (de->inode) {
427 struct ext3_dir_entry_2 *de1 = (struct ext3_dir_entry_2 *)((char *)de + nlen);
428 de1->rec_len = ext3_rec_len_to_disk(rlen - nlen);
429 de->rec_len = ext3_rec_len_to_disk(nlen);
430 de = de1;
431 }
433 if (inode) {
435 ext3_set_de_type(dir->i_sb, de, inode->i_mode);
436 } else
437 de->inode = 0;
438 de->name_len = (__u8)namelen;
439 memcpy(de->name, name, namelen);
440
441 /*
442 * XXX shouldn't update any times until successful
443 * completion of syscall, but too many callers depend
444 * on this.
445 *
446 * XXX similarly, too many callers depend on
447 * ext4_new_inode() setting the times, but error
448 * recovery deletes the inode, so the worst that can
449 * happen is that the times are slightly out of date
450 * and/or different from the directory change time.
451 */
452 dir->i_mtime = dir->i_ctime = ext3_current_time(dir);
454 dir->i_version++;
456 set_buffer_dirty(bh);
457 __brelse(bh);
458 return 0;
459}
460
461#ifdef EXT2_HTREE_INDEX
462
463/*
464 * Returns the hash of a filename. If len is 0 and name is NULL, then
465 * this function can be used to test whether or not a hash version is
466 * supported.
467 *
468 * The seed is an 4 longword (32 bits) "secret" which can be used to
469 * uniquify a hash. If the seed is all zero's, then some default seed
470 * may be used.
471 *
472 * A particular hash version specifies whether or not the seed is
473 * represented, and whether or not the returned hash is 32 bits or 64
474 * bits. 32 bit hashes will return 0 for the minor hash.
475 */
476int ext3_dirhash(const char *name, int len, struct dx_hash_info *hinfo)
477{
478 __u32 hash;
479 __u32 minor_hash = 0;
480 const char *p;
481 int i;
482 __u32 in[8], buf[4];
483
484 void (*str2hashbuf)(const char *, int, __u32 *, int) =
485 str2hashbuf_signed;
486
487 /* Initialize the default seed for the hash checksum functions */
488 buf[0] = 0x67452301;
489 buf[1] = 0xefcdab89;
490 buf[2] = 0x98badcfe;
491 buf[3] = 0x10325476;
492
493 /* Check to see if the seed is all zero's */
494 if (hinfo->seed) {
495 for (i = 0; i < 4; i++) {
496 if (hinfo->seed[i])
497 break;
498 }
499 if (i < 4)
500 memcpy(buf, hinfo->seed, sizeof(buf));
501 }
502
503 switch (hinfo->hash_version) {
505 hash = dx_hack_hash_unsigned(name, len);
506 break;
507 case DX_HASH_LEGACY:
508 hash = dx_hack_hash_signed(name, len);
509 break;
511 str2hashbuf = str2hashbuf_unsigned;
512 case DX_HASH_HALF_MD4:
513 p = name;
514 while (len > 0) {
515 (*str2hashbuf)(p, len, in, 8);
516 half_md4_transform(buf, in);
517 len -= 32;
518 p += 32;
519 }
520 minor_hash = buf[2];
521 hash = buf[1];
522 break;
524 str2hashbuf = str2hashbuf_unsigned;
525 case DX_HASH_TEA:
526 p = name;
527 while (len > 0) {
528 (*str2hashbuf)(p, len, in, 4);
529 TEA_transform(buf, in);
530 len -= 16;
531 p += 16;
532 }
533 hash = buf[0];
534 minor_hash = buf[1];
535 break;
536 default:
537 hinfo->hash = 0;
538 return -1;
539 }
540 hash = hash & ~1;
541 if (hash == (EXT4_HTREE_EOF_32BIT << 1))
542 hash = (EXT4_HTREE_EOF_32BIT - 1) << 1;
543 hinfo->hash = hash;
544 hinfo->minor_hash = minor_hash;
545 return 0;
546}
547EXPORT_SYMBOL(ext3_dirhash);
548
549
550/*
551 * These functions convert from the major/minor hash to an f_pos
552 * value.
553 *
554 * Currently we only use major hash numer. This is unfortunate, but
555 * on 32-bit machines, the same VFS interface is used for lseek and
556 * llseek, so if we use the 64 bit offset, then the 32-bit versions of
557 * lseek/telldir/seekdir will blow out spectacularly, and from within
558 * the ext2 low-level routine, we don't know if we're being called by
559 * a 64-bit version of the system call or the 32-bit version of the
560 * system call. Worse yet, NFSv2 only allows for a 32-bit readdir
561 * cookie. Sigh.
562 */
563#define hash2pos(major, minor) (major >> 1)
564#define pos2maj_hash(pos) ((pos << 1) & 0xffffffff)
565#define pos2min_hash(pos) (0)
566
567/*
568 * This structure holds the nodes of the red-black tree used to store
569 * the directory entry in hash order.
570 */
571struct fname {
572 __u32 hash;
573 __u32 minor_hash;
574 struct rb_node rb_hash;
575 struct fname *next;
576 __u32 inode;
577 __u8 name_len;
579 char name[0];
580};
581
582/*
583 * This functoin implements a non-recursive way of freeing all of the
584 * nodes in the red-black tree.
585 */
586static void free_rb_tree_fname(struct rb_root *root)
587{
588 struct rb_node *n = root->rb_node;
589 struct rb_node *parent;
590 struct fname *fname;
591
592 while (n) {
593 /* Do the node's children first */
594 if ((n)->rb_left) {
595 n = n->rb_left;
596 continue;
597 }
598 if (n->rb_right) {
599 n = n->rb_right;
600 continue;
601 }
602 /*
603 * The node has no children; free it, and then zero
604 * out parent's link to it. Finally go to the
605 * beginning of the loop and try to free the parent
606 * node.
607 */
608 parent = rb_parent(n);
609 fname = rb_entry(n, struct fname, rb_hash);
610 while (fname) {
611 struct fname * old = fname;
612 fname = fname->next;
613 kfree (old);
614 }
615 if (!parent)
616 root->rb_node = NULL;
617 else if (parent->rb_left == n)
618 parent->rb_left = NULL;
619 else if (parent->rb_right == n)
620 parent->rb_right = NULL;
621 n = parent;
622 }
623 root->rb_node = NULL;
624}
625
626
627static struct dir_private_info *create_dir_info(loff_t pos)
628{
629 struct dir_private_info *p;
630
631 p = kmalloc(sizeof(struct dir_private_info), GFP_KERNEL);
632 if (!p)
633 return NULL;
634 p->root.rb_node = NULL;
635 p->curr_node = NULL;
636 p->extra_fname = NULL;
637 p->last_pos = 0;
638 p->curr_hash = (__u32)pos2maj_hash(pos);
639 p->curr_minor_hash = (__u32)pos2min_hash(pos);
640 p->next_hash = 0;
641 return p;
642}
643
644void ext3_htree_free_dir_info(struct dir_private_info *p)
645{
646 free_rb_tree_fname(&p->root);
647 kfree(p);
648}
649
650/*
651 * Given a directory entry, enter it into the fname rb tree.
652 */
653int ext3_htree_store_dirent(struct file *dir_file, __u32 hash,
654 __u32 minor_hash,
655 struct ext3_dir_entry_2 *dirent)
656{
657 struct rb_node **p, *parent = NULL;
658 struct fname * fname, *new_fn;
659 struct dir_private_info *info;
660 int extra_data = 0;
661 int len;
662
663 info = (struct dir_private_info *) dir_file->private_data;
664 p = &info->root.rb_node;
665
666 /* Create and allocate the fname structure */
667 if (dirent->file_type & EXT3_DIRENT_LUFID)
668 extra_data = ext3_get_dirent_data_len(dirent);
669
670 len = sizeof(struct fname) + dirent->name_len + extra_data;
671 new_fn = kmalloc(len, GFP_KERNEL);
672 if (!new_fn)
673 return -ENOMEM;
674 memset(new_fn, 0, len);
675 new_fn->hash = hash;
676 new_fn->minor_hash = minor_hash;
677 new_fn->inode = le32_to_cpu(dirent->inode);
678 new_fn->name_len = dirent->name_len;
679 new_fn->file_type = dirent->file_type;
680 memcpy(&new_fn->name[0], &dirent->name[0],
681 dirent->name_len + extra_data);
682 new_fn->name[dirent->name_len] = 0;
683
684 while (*p) {
685 parent = *p;
686 fname = rb_entry(parent, struct fname, rb_hash);
687
688 /*
689 * If the hash and minor hash match up, then we put
690 * them on a linked list. This rarely happens...
691 */
692 if ((new_fn->hash == fname->hash) &&
693 (new_fn->minor_hash == fname->minor_hash)) {
694 new_fn->next = fname->next;
695 fname->next = new_fn;
696 return 0;
697 }
698
699 if (new_fn->hash < fname->hash)
700 p = &(*p)->rb_left;
701 else if (new_fn->hash > fname->hash)
702 p = &(*p)->rb_right;
703 else if (new_fn->minor_hash < fname->minor_hash)
704 p = &(*p)->rb_left;
705 else /* if (new_fn->minor_hash > fname->minor_hash) */
706 p = &(*p)->rb_right;
707 }
708
709 rb_link_node(&new_fn->rb_hash, parent, p);
710 rb_insert_color(&new_fn->rb_hash, &info->root);
711 return 0;
712}
713
714static unsigned char ext3_filetype_table[] = {
716};
717
718static unsigned char get_dtype(struct super_block *sb, int filetype)
719{
722 return DT_UNKNOWN;
723
724 return (ext3_filetype_table[filetype]);
725}
726
727/*
728 * This is a helper function for ext3_dx_readdir. It calls filldir
729 * for all entres on the fname linked list. (Normally there is only
730 * one entry on the linked list, unless there are 62 bit hash collisions.)
731 */
732static int call_filldir(struct file * filp, void * cookie,
733 filldir_t filldir, struct fname *fname)
734{
735 struct dir_private_info *info = filp->private_data;
736 loff_t curr_pos;
737 struct inode *inode = filp->f_dentry->d_inode;
738 struct super_block * sb;
739 int error;
740
741 sb = inode->i_sb;
742
743 if (!fname) {
744 printk("call_filldir: called with null fname?!?\n");
745 return 0;
746 }
747 curr_pos = hash2pos(fname->hash, fname->minor_hash);
748 while (fname) {
749 error = filldir(cookie, fname->name,
750 fname->name_len, (ULONG)curr_pos,
751 fname->inode, get_dtype(sb, fname->file_type));
752 if (error) {
753 filp->f_pos = curr_pos;
754 info->extra_fname = fname;
755 return error;
756 }
757 fname = fname->next;
758 }
759 return 0;
760}
761
762struct fake_dirent
763{
765 __le16 rec_len;
766 __u8 name_len;
768};
769
770struct dx_countlimit
771{
774};
775
776struct dx_entry
777{
778 __le32 hash;
780};
781
782/*
783 * dx_root_info is laid out so that if it should somehow get overlaid by a
784 * dirent the two low bits of the hash version will be zero. Therefore, the
785 * hash version mod 4 should never be 0. Sincerely, the paranoia department.
786 */
787
788struct dx_root
789{
790 struct fake_dirent dot;
791 char dot_name[4];
792 struct fake_dirent dotdot;
793 char dotdot_name[4];
794 struct dx_root_info
795 {
796 __le32 reserved_zero;
797 __u8 hash_version;
798 __u8 info_length; /* 8 */
799 __u8 indirect_levels;
800 __u8 unused_flags;
801 }
802 info;
803 struct dx_entry entries[0];
804};
805
806struct dx_node
807{
808 struct fake_dirent fake;
809 struct dx_entry entries[0];
810};
811
812
813struct dx_frame
814{
815 struct buffer_head *bh;
816 struct dx_entry *entries;
817 struct dx_entry *at;
818};
819
820struct dx_map_entry
821{
822 __u32 hash;
823 __u16 offs;
824 __u16 size;
825};
826
827#if defined(__REACTOS__) && !defined(_MSC_VER)
828struct ext3_dir_entry_2 *
829 do_split(struct ext2_icb *icb, struct inode *dir,
830 struct buffer_head **bh,struct dx_frame *frame,
831 struct dx_hash_info *hinfo, int *error);
832#endif
833
834/*
835 * Future: use high four bits of block for coalesce-on-delete flags
836 * Mask them off for now.
837 */
838
839static inline unsigned dx_get_block (struct dx_entry *entry)
840{
841 return le32_to_cpu(entry->block) & 0x00ffffff;
842}
843
844static inline void dx_set_block (struct dx_entry *entry, unsigned value)
845{
846 entry->block = cpu_to_le32(value);
847}
848
849static inline unsigned dx_get_hash (struct dx_entry *entry)
850{
851 return le32_to_cpu(entry->hash);
852}
853
854static inline void dx_set_hash (struct dx_entry *entry, unsigned value)
855{
856 entry->hash = cpu_to_le32(value);
857}
858
859static inline unsigned dx_get_count (struct dx_entry *entries)
860{
861 return le16_to_cpu(((struct dx_countlimit *) entries)->count);
862}
863
864static inline unsigned dx_get_limit (struct dx_entry *entries)
865{
866 return le16_to_cpu(((struct dx_countlimit *) entries)->limit);
867}
868
869static inline void dx_set_count (struct dx_entry *entries, unsigned value)
870{
871 ((struct dx_countlimit *) entries)->count = cpu_to_le16(value);
872}
873
874static inline void dx_set_limit (struct dx_entry *entries, unsigned value)
875{
876 ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
877}
878
879static inline unsigned dx_root_limit (struct inode *dir, unsigned infosize)
880{
881 unsigned entry_space = dir->i_sb->s_blocksize - EXT3_DIR_REC_LEN(1) -
882 EXT3_DIR_REC_LEN(2) - infosize;
883 return 0? 20: entry_space / sizeof(struct dx_entry);
884}
885
886static inline unsigned dx_node_limit (struct inode *dir)
887{
888 unsigned entry_space = dir->i_sb->s_blocksize - EXT3_DIR_REC_LEN(0);
889 return 0? 22: entry_space / sizeof(struct dx_entry);
890}
891
892/*
893 * Debug
894 */
895#if DX_DEBUG
896static void dx_show_index (char * label, struct dx_entry *entries)
897{
898 int i, n = dx_get_count (entries);
899 printk("%s index ", label);
900 for (i = 0; i < n; i++)
901 {
902 printk("%x->%u ", i? dx_get_hash(entries + i): 0, dx_get_block(entries + i));
903 }
904 printk("\n");
905}
906
907struct stats
908{
909 unsigned names;
910 unsigned space;
911 unsigned bcount;
912};
913
914struct stats dx_show_leaf(struct ext2_icb *icb, struct dx_hash_info *hinfo,
915 struct ext3_dir_entry_2 *de, int size, int show_names)
916{
917 struct stats rc;
918 unsigned names = 0, space = 0;
919 char *base = (char *) de;
920 struct dx_hash_info h = *hinfo;
921
922 printk("names: ");
923 while ((char *) de < base + size)
924 {
925 if (de->inode)
926 {
927 if (show_names)
928 {
929 int len = de->name_len;
930 char *name = de->name;
931 while (len--) printk("%c", *name++);
932 ext3_dirhash(de->name, de->name_len, &h);
933 printk(":%x.%u ", h.hash,
934 ((char *) de - base));
935 }
937 names++;
938 }
939 de = (struct ext3_dir_entry_2 *) ((char *) de + le16_to_cpu(de->rec_len));
940 }
941 printk("(%i)\n", names);
942
943 rc.names = names;
944 rc.space = space;
945 rc.bcount = 1;
946
947 return rc;
948}
949
950struct stats dx_show_entries(struct ext2_icb *icb, struct dx_hash_info *hinfo,
951 struct inode *dir, struct dx_entry *entries, int levels)
952{
953 unsigned blocksize = dir->i_sb->s_blocksize;
954 unsigned count = dx_get_count (entries), names = 0, space = 0, i;
955 unsigned bcount = 0;
956 struct buffer_head *bh;
957 struct stats rc;
958 int err;
959
960 printk("%i indexed blocks...\n", count);
961 for (i = 0; i < count; i++, entries++)
962 {
963 u32 block = dx_get_block(entries), hash = i? dx_get_hash(entries): 0;
964 u32 range = i < count - 1? (dx_get_hash(entries + 1) - hash): ~hash;
965 struct stats stats;
966 printk("%s%3u:%03u hash %8x/%8x ",levels?"":" ", i, block, hash, range);
967 if (!(bh = ext3_bread (icb, dir, block, &err))) continue;
968 stats = levels?
969 dx_show_entries(icb, hinfo, dir, ((struct dx_node *) bh->b_data)->entries, levels - 1):
970 dx_show_leaf(icb, hinfo, (struct ext3_dir_entry_2 *) bh->b_data, blocksize, 0);
971 names += stats.names;
972 space += stats.space;
973 bcount += stats.bcount;
974 __brelse (bh);
975 }
976 if (bcount)
977 printk("%snames %u, fullness %u (%u%%)\n", levels?"":" ",
978 names, space/bcount,(space/bcount)*100/blocksize);
979
980 rc.names = names;
981 rc.space = space;
982 rc.bcount = 1;
983
984 return rc;
985}
986#endif /* DX_DEBUG */
987
988
989int ext3_save_inode ( struct ext2_icb *icb, struct inode *in)
990{
991 return Ext2SaveInode(icb, in->i_sb->s_priv, in);
992}
993
994/*
995 * Probe for a directory leaf block to search.
996 *
997 * dx_probe can return ERR_BAD_DX_DIR, which means there was a format
998 * error in the directory index, and the caller should fall back to
999 * searching the directory normally. The callers of dx_probe **MUST**
1000 * check for this error code, and make sure it never gets reflected
1001 * back to userspace.
1002 */
1003static struct dx_frame *
1004 dx_probe(struct ext2_icb *icb, struct dentry *dentry, struct inode *dir,
1005 struct dx_hash_info *hinfo, struct dx_frame *frame_in, int *err)
1006{
1007 unsigned count, indirect;
1008 struct dx_entry *at, *entries, *p, *q, *m;
1009 struct dx_root *root;
1010 struct buffer_head *bh;
1011 struct dx_frame *frame = frame_in;
1012 u32 hash;
1013
1014 frame->bh = NULL;
1015 if (dentry)
1016 dir = dentry->d_parent->d_inode;
1017 if (!(bh = ext3_bread (icb, dir, 0, err)))
1018 goto fail;
1019 root = (struct dx_root *) bh->b_data;
1020 if (root->info.hash_version != DX_HASH_TEA &&
1021 root->info.hash_version != DX_HASH_HALF_MD4 &&
1022 root->info.hash_version != DX_HASH_LEGACY) {
1024 "Unrecognised inode hash code %d",
1025 root->info.hash_version);
1026 __brelse(bh);
1027 *err = ERR_BAD_DX_DIR;
1028 goto fail;
1029 }
1030 hinfo->hash_version = root->info.hash_version;
1031 hinfo->seed = EXT3_SB(dir->i_sb)->s_hash_seed;
1032 if (dentry)
1033 ext3_dirhash(dentry->d_name.name, dentry->d_name.len, hinfo);
1034 hash = hinfo->hash;
1035
1036 if (root->info.unused_flags & 1) {
1038 "Unimplemented inode hash flags: %#06x",
1039 root->info.unused_flags);
1040 brelse(bh);
1041 *err = ERR_BAD_DX_DIR;
1042 goto fail;
1043 }
1044
1045 if ((indirect = root->info.indirect_levels) > 1) {
1047 "Unimplemented inode hash depth: %#06x",
1048 root->info.indirect_levels);
1049 brelse(bh);
1050 *err = ERR_BAD_DX_DIR;
1051 goto fail;
1052 }
1053
1054 entries = (struct dx_entry *) (((char *)&root->info) +
1055 root->info.info_length);
1056
1057 if (dx_get_limit(entries) != dx_root_limit(dir,
1058 root->info.info_length)) {
1060 "dx entry: limit != root limit");
1061 brelse(bh);
1062 *err = ERR_BAD_DX_DIR;
1063 goto fail;
1064 }
1065
1066 dxtrace(printk("Look up %x", hash));
1067 while (1)
1068 {
1069 count = dx_get_count(entries);
1070 if (!count || count > dx_get_limit(entries)) {
1072 "dx entry: no count or count > limit");
1073 brelse(bh);
1074 *err = ERR_BAD_DX_DIR;
1075 goto fail2;
1076 }
1077
1078 p = entries + 1;
1079 q = entries + count - 1;
1080 while (p <= q)
1081 {
1082 m = p + (q - p)/2;
1083 if (dx_get_hash(m) > hash)
1084 q = m - 1;
1085 else
1086 p = m + 1;
1087 }
1088
1089 if (0) // linear search cross check
1090 {
1091 unsigned n = count - 1;
1092 at = entries;
1093 while (n--)
1094 {
1095 if (dx_get_hash(++at) > hash)
1096 {
1097 at--;
1098 break;
1099 }
1100 }
1101 ASSERT(at == p - 1);
1102 }
1103
1104 at = p - 1;
1105 frame->bh = bh;
1106 frame->entries = entries;
1107 frame->at = at;
1108 if (!indirect--) return frame;
1109 if (!(bh = ext3_bread(icb, dir, dx_get_block(at), err)))
1110 goto fail2;
1111 at = entries = ((struct dx_node *) bh->b_data)->entries;
1112 if (dx_get_limit(entries) != dx_node_limit (dir)) {
1114 "dx entry: limit != node limit");
1115 brelse(bh);
1116 *err = ERR_BAD_DX_DIR;
1117 goto fail2;
1118 }
1119 frame++;
1120 frame->bh = NULL;
1121 }
1122fail2:
1123 while (frame >= frame_in) {
1124 brelse(frame->bh);
1125 frame--;
1126 }
1127fail:
1128 if (*err == ERR_BAD_DX_DIR)
1130 "Corrupt dir inode %ld, running e2fsck is "
1131 "recommended.", dir->i_ino);
1132 return NULL;
1133}
1134
1135static void dx_release (struct dx_frame *frames)
1136{
1137 if (frames[0].bh == NULL)
1138 return;
1139
1140 if (((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels)
1141 brelse(frames[1].bh);
1142 brelse(frames[0].bh);
1143}
1144
1145/*
1146 * This function increments the frame pointer to search the next leaf
1147 * block, and reads in the necessary intervening nodes if the search
1148 * should be necessary. Whether or not the search is necessary is
1149 * controlled by the hash parameter. If the hash value is even, then
1150 * the search is only continued if the next block starts with that
1151 * hash value. This is used if we are searching for a specific file.
1152 *
1153 * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
1154 *
1155 * This function returns 1 if the caller should continue to search,
1156 * or 0 if it should not. If there is an error reading one of the
1157 * index blocks, it will a negative error code.
1158 *
1159 * If start_hash is non-null, it will be filled in with the starting
1160 * hash of the next page.
1161 */
1162int ext3_htree_next_block(struct ext2_icb *icb, struct inode *dir,
1163 __u32 hash, struct dx_frame *frame,
1164 struct dx_frame *frames, __u32 *start_hash)
1165{
1166 struct dx_frame *p;
1167 struct buffer_head *bh;
1168 int err, num_frames = 0;
1169 __u32 bhash;
1170
1171 p = frame;
1172 /*
1173 * Find the next leaf page by incrementing the frame pointer.
1174 * If we run out of entries in the interior node, loop around and
1175 * increment pointer in the parent node. When we break out of
1176 * this loop, num_frames indicates the number of interior
1177 * nodes need to be read.
1178 */
1179 while (1) {
1180 if (++(p->at) < p->entries + dx_get_count(p->entries))
1181 break;
1182 if (p == frames)
1183 return 0;
1184 num_frames++;
1185 p--;
1186 }
1187
1188 /*
1189 * If the hash is 1, then continue only if the next page has a
1190 * continuation hash of any value. This is used for readdir
1191 * handling. Otherwise, check to see if the hash matches the
1192 * desired contiuation hash. If it doesn't, return since
1193 * there's no point to read in the successive index pages.
1194 */
1195 bhash = dx_get_hash(p->at);
1196 if (start_hash)
1197 *start_hash = bhash;
1198 if ((hash & 1) == 0) {
1199 if ((bhash & ~1) != hash)
1200 return 0;
1201 }
1202 /*
1203 * If the hash is HASH_NB_ALWAYS, we always go to the next
1204 * block so no check is necessary
1205 */
1206 while (num_frames--) {
1207 if (!(bh = ext3_bread(icb, dir, dx_get_block(p->at), &err)))
1208 return err; /* Failure */
1209 p++;
1210 brelse (p->bh);
1211 p->bh = bh;
1212 p->at = p->entries = ((struct dx_node *) bh->b_data)->entries;
1213 }
1214 return 1;
1215}
1216
1217/*
1218 * This function fills a red-black tree with information from a
1219 * directory block. It returns the number directory entries loaded
1220 * into the tree. If there is an error it is returned in err.
1221 */
1222int htree_dirblock_to_tree(struct ext2_icb *icb, struct file *dir_file,
1223 struct inode *dir, int block,
1224 struct dx_hash_info *hinfo,
1225 __u32 start_hash, __u32 start_minor_hash)
1226{
1227 struct buffer_head *bh;
1228 struct ext3_dir_entry_2 *de, *top;
1229 int err, count = 0;
1230
1231 dxtrace(printk("In htree dirblock_to_tree: block %d\n", block));
1232 if (!(bh = ext3_bread (icb, dir, block, &err)))
1233 return err;
1234
1235 de = (struct ext3_dir_entry_2 *) bh->b_data;
1236 top = (struct ext3_dir_entry_2 *) ((char *) de +
1237 dir->i_sb->s_blocksize -
1238 EXT3_DIR_REC_LEN(0));
1239 for (; de < top; de = ext3_next_entry(de)) {
1240 if (!ext3_check_dir_entry("htree_dirblock_to_tree", dir, de, bh,
1241 ((unsigned long)block<<EXT3_BLOCK_SIZE_BITS(dir->i_sb))
1242 + (unsigned long)((char *)de - bh->b_data))) {
1243 /* On error, skip the f_pos to the next block. */
1244 dir_file->f_pos = (dir_file->f_pos |
1245 (dir->i_sb->s_blocksize - 1)) + 1;
1246 brelse (bh);
1247 return count;
1248 }
1249 ext3_dirhash(de->name, de->name_len, hinfo);
1250 if ((hinfo->hash < start_hash) ||
1251 ((hinfo->hash == start_hash) &&
1252 (hinfo->minor_hash < start_minor_hash)))
1253 continue;
1254 if (de->inode == 0)
1255 continue;
1256 if ((err = ext3_htree_store_dirent(dir_file,
1257 hinfo->hash, hinfo->minor_hash, de)) != 0) {
1258 brelse(bh);
1259 return err;
1260 }
1261 count++;
1262 }
1263 brelse(bh);
1264 return count;
1265}
1266
1267/*
1268 * This function fills a red-black tree with information from a
1269 * directory. We start scanning the directory in hash order, starting
1270 * at start_hash and start_minor_hash.
1271 *
1272 * This function returns the number of entries inserted into the tree,
1273 * or a negative error code.
1274 */
1275int ext3_htree_fill_tree(struct ext2_icb *icb, struct file *dir_file,
1276 __u32 start_hash, __u32 start_minor_hash,
1277 __u32 *next_hash)
1278{
1279 struct dx_hash_info hinfo;
1280 struct ext3_dir_entry_2 *de;
1281 struct dx_frame frames[2], *frame;
1282 int block, err = 0;
1283 struct inode *dir;
1284 int count = 0;
1285 int ret;
1286 __u32 hashval;
1287
1288 dxtrace(printk("In htree_fill_tree, start hash: %x:%x\n", start_hash,
1289 start_minor_hash));
1290 dir = dir_file->f_dentry->d_inode;
1291 if (!(EXT3_I(dir)->i_flags & EXT3_INDEX_FL)) {
1292 hinfo.hash_version = EXT3_SB(dir->i_sb)->s_def_hash_version;
1293 hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed;
1294 count = htree_dirblock_to_tree(icb, dir_file, dir, 0, &hinfo,
1295 start_hash, start_minor_hash);
1296 *next_hash = ~0;
1297 return count;
1298 }
1299
1300 hinfo.hash = start_hash;
1301 hinfo.minor_hash = 0;
1302 frame = dx_probe(icb, NULL, dir_file->f_dentry->d_inode, &hinfo, frames, &err);
1303 if (!frame)
1304 return err;
1305
1306 /* Add '.' and '..' from the htree header */
1307 if (!start_hash && !start_minor_hash) {
1308 de = (struct ext3_dir_entry_2 *) frames[0].bh->b_data;
1309 if ((err = ext3_htree_store_dirent(dir_file, 0, 0, de)) != 0)
1310 goto errout;
1311 count++;
1312 }
1313 if (start_hash < 2 || (start_hash ==2 && start_minor_hash==0)) {
1314 de = (struct ext3_dir_entry_2 *) frames[0].bh->b_data;
1315 de = ext3_next_entry(de);
1316 if ((err = ext3_htree_store_dirent(dir_file, 2, 0, de)) != 0)
1317 goto errout;
1318 count++;
1319 }
1320
1321 while (1) {
1322 block = dx_get_block(frame->at);
1323 ret = htree_dirblock_to_tree(icb, dir_file, dir, block, &hinfo,
1324 start_hash, start_minor_hash);
1325 if (ret < 0) {
1326 err = ret;
1327 goto errout;
1328 }
1329 count += ret;
1330 hashval = ~0;
1331 ret = ext3_htree_next_block(icb, dir, HASH_NB_ALWAYS,
1332 frame, frames, &hashval);
1333 *next_hash = hashval;
1334 if (ret < 0) {
1335 err = ret;
1336 goto errout;
1337 }
1338 /*
1339 * Stop if: (a) there are no more entries, or
1340 * (b) we have inserted at least one entry and the
1341 * next hash value is not a continuation
1342 */
1343 if ((ret == 0) ||
1344 (count && ((hashval & 1) == 0)))
1345 break;
1346 }
1347 dx_release(frames);
1348 dxtrace(printk("Fill tree: returned %d entries, next hash: %x\n",
1349 count, *next_hash));
1350 return count;
1351errout:
1352 dx_release(frames);
1353
1354 return (err);
1355}
1356
1357
1358/*
1359 * Directory block splitting, compacting
1360 */
1361
1362/*
1363 * Create map of hash values, offsets, and sizes, stored at end of block.
1364 * Returns number of entries mapped.
1365 */
1366static int dx_make_map (struct ext3_dir_entry_2 *de, int size,
1367 struct dx_hash_info *hinfo, struct dx_map_entry *map_tail)
1368{
1369 int count = 0;
1370 char *base = (char *) de;
1371 struct dx_hash_info h = *hinfo;
1372
1373 while ((char *) de < base + size)
1374 {
1375 if (de->name_len && de->inode) {
1376 ext3_dirhash(de->name, de->name_len, &h);
1377 map_tail--;
1378 map_tail->hash = h.hash;
1379 map_tail->offs = (u16) ((char *) de - base);
1380 map_tail->size = le16_to_cpu(de->rec_len);
1381 count++;
1382 cond_resched();
1383 }
1384 /* XXX: do we need to check rec_len == 0 case? -Chris */
1385 de = (struct ext3_dir_entry_2 *) ((char *) de + le16_to_cpu(de->rec_len));
1386 }
1387 return count;
1388}
1389
1390/* Sort map by hash value */
1391static void dx_sort_map (struct dx_map_entry *map, unsigned count)
1392{
1393 struct dx_map_entry *p, *q, *top = map + count - 1;
1394 int more;
1395 /* Combsort until bubble sort doesn't suck */
1396 while (count > 2)
1397 {
1398 count = count*10/13;
1399 if (count - 9 < 2) /* 9, 10 -> 11 */
1400 count = 11;
1401 for (p = top, q = p - count; q >= map; p--, q--)
1402 if (p->hash < q->hash)
1403 swap(struct dx_map_entry, *p, *q);
1404 }
1405 /* Garden variety bubble sort */
1406 do {
1407 more = 0;
1408 q = top;
1409 while (q-- > map)
1410 {
1411 if (q[1].hash >= q[0].hash)
1412 continue;
1413 swap(struct dx_map_entry, *(q+1), *q);
1414 more = 1;
1415 }
1416 } while (more);
1417}
1418
1419static void dx_insert_block(struct dx_frame *frame, u32 hash, u32 block)
1420{
1421 struct dx_entry *entries = frame->entries;
1422 struct dx_entry *old = frame->at, *new = old + 1;
1423 unsigned int count = dx_get_count(entries);
1424
1425 ASSERT(count < dx_get_limit(entries));
1426 ASSERT(old < entries + count);
1427 memmove(new + 1, new, (char *)(entries + count) - (char *)(new));
1428 dx_set_hash(new, hash);
1429 dx_set_block(new, block);
1430 dx_set_count(entries, count + 1);
1431}
1432
1433struct buffer_head *
1434 ext3_dx_find_entry(struct ext2_icb *icb, struct dentry *dentry,
1435 struct ext3_dir_entry_2 **res_dir, int *err)
1436{
1437 struct super_block * sb;
1438 struct dx_hash_info hinfo = {0};
1439 u32 hash;
1440 struct dx_frame frames[2], *frame;
1441 struct ext3_dir_entry_2 *de, *top;
1442 struct buffer_head *bh;
1443 unsigned long block;
1444 int retval;
1445 int namelen = dentry->d_name.len;
1446 const __u8 *name = dentry->d_name.name;
1447 struct inode *dir = dentry->d_parent->d_inode;
1448
1449 sb = dir->i_sb;
1450 /* NFS may look up ".." - look at dx_root directory block */
1451 if (namelen > 2 || name[0] != '.'||(name[1] != '.' && name[1] != '\0')) {
1452 if (!(frame = dx_probe(icb, dentry, NULL, &hinfo, frames, err)))
1453 return NULL;
1454 } else {
1455 frame = frames;
1456 frame->bh = NULL; /* for dx_release() */
1457 frame->at = (struct dx_entry *)frames; /* hack for zero entry*/
1458 dx_set_block(frame->at, 0); /* dx_root block is 0 */
1459 }
1460 hash = hinfo.hash;
1461 do {
1462 block = dx_get_block(frame->at);
1463 if (!(bh = ext3_bread (icb, dir, block, err)))
1464 goto errout;
1465 de = (struct ext3_dir_entry_2 *) bh->b_data;
1466 top = (struct ext3_dir_entry_2 *) ((char *) de + sb->s_blocksize -
1467 EXT3_DIR_REC_LEN(0));
1468 for (; de < top; de = ext3_next_entry(de))
1469 if (ext3_match (namelen, name, de)) {
1470 if (!ext3_check_dir_entry("ext3_find_entry",
1471 dir, de, bh,
1473 + (unsigned long)((char *)de - bh->b_data))) {
1474 brelse (bh);
1475 goto errout;
1476 }
1477 *res_dir = de;
1478 dx_release (frames);
1479 return bh;
1480 }
1481 brelse (bh);
1482 /* Check to see if we should continue to search */
1483 retval = ext3_htree_next_block(icb, dir, hash, frame,
1484 frames, NULL);
1485 if (retval < 0) {
1487 "error reading index page in directory #%lu",
1488 dir->i_ino);
1489 *err = retval;
1490 goto errout;
1491 }
1492 } while (retval == 1);
1493
1494 *err = -ENOENT;
1495errout:
1496 dxtrace(printk("%s not found\n", name));
1497 dx_release (frames);
1498 return NULL;
1499}
1500
1501int ext3_dx_readdir(struct file *filp, filldir_t filldir,
1502 void * context)
1503{
1504 struct dir_private_info *info = filp->private_data;
1505 struct inode *inode = filp->f_dentry->d_inode;
1506 struct fname *fname;
1508 int ret;
1509
1510 if (!info) {
1511 info = create_dir_info(filp->f_pos);
1512 if (!info)
1513 return -ENOMEM;
1514 filp->private_data = info;
1515 }
1516
1517 if (filp->f_pos == EXT3_HTREE_EOF)
1518 return 0; /* EOF */
1519
1520 /* Some one has messed with f_pos; reset the world */
1521 if (info->last_pos != filp->f_pos) {
1522 free_rb_tree_fname(&info->root);
1523 info->curr_node = NULL;
1524 info->extra_fname = NULL;
1525 info->curr_hash = (__u32)pos2maj_hash(filp->f_pos);
1526 info->curr_minor_hash = (__u32)pos2min_hash(filp->f_pos);
1527 }
1528
1529 /*
1530 * If there are any leftover names on the hash collision
1531 * chain, return them first.
1532 */
1533 if (info->extra_fname) {
1534 if (call_filldir(filp, context, filldir, info->extra_fname))
1535 goto finished;
1536 info->extra_fname = NULL;
1537 goto next_node;
1538 } else if (!info->curr_node)
1539 info->curr_node = rb_first(&info->root);
1540
1541 while (1) {
1542 /*
1543 * Fill the rbtree if we have no more entries,
1544 * or the inode has changed since we last read in the
1545 * cached entries.
1546 */
1547 if ((!info->curr_node) ||
1548 (filp->f_version != inode->i_version)) {
1549 info->curr_node = NULL;
1550 free_rb_tree_fname(&info->root);
1551 filp->f_version = inode->i_version;
1552 ret = ext3_htree_fill_tree(fc->efc_irp, filp, info->curr_hash,
1553 info->curr_minor_hash, &info->next_hash);
1554 if (ret < 0)
1555 return ret;
1556 if (ret == 0) {
1557 filp->f_pos = EXT3_HTREE_EOF;
1558 break;
1559 }
1560 info->curr_node = rb_first(&info->root);
1561 }
1562
1563 fname = rb_entry(info->curr_node, struct fname, rb_hash);
1564 info->curr_hash = fname->hash;
1565 info->curr_minor_hash = fname->minor_hash;
1566 if (call_filldir(filp, context, filldir, fname))
1567 break;
1568next_node:
1569 info->curr_node = rb_next(info->curr_node);
1570 if (info->curr_node) {
1571 fname = rb_entry(info->curr_node, struct fname,
1572 rb_hash);
1573 info->curr_hash = fname->hash;
1574 info->curr_minor_hash = fname->minor_hash;
1575 } else {
1576 if (info->next_hash == ~0) {
1577 filp->f_pos = EXT3_HTREE_EOF;
1578 break;
1579 }
1580 info->curr_hash = info->next_hash;
1581 info->curr_minor_hash = 0;
1582 }
1583 }
1584finished:
1585 info->last_pos = filp->f_pos;
1586 return 0;
1587}
1588
1589int ext3_release_dir (struct inode * inode, struct file * filp)
1590{
1591 if (filp->private_data) {
1592 ext3_htree_free_dir_info(filp->private_data);
1593 filp->private_data = NULL;
1594 }
1595
1596 return 0;
1597}
1598
1599/* FIXME: Inspect the clang-cl code path */
1600#if defined(__REACTOS__) && defined(__clang__)
1601struct ext3_dir_entry_2* do_split(struct ext2_icb *icb, struct inode *dir, struct buffer_head **bh,struct dx_frame *frame, struct dx_hash_info *hinfo, int *error);
1602#endif
1603
1604/*
1605 * Returns 0 for success, or a negative error value
1606 */
1607int ext3_dx_add_entry(struct ext2_icb *icb, struct dentry *dentry,
1608 struct inode *inode)
1609{
1610 struct dx_frame frames[2], *frame;
1611 struct dx_entry *entries, *at;
1612 struct dx_hash_info hinfo;
1613 struct buffer_head * bh;
1614 struct inode *dir = dentry->d_parent->d_inode;
1615 struct super_block * sb = dir->i_sb;
1616 struct ext3_dir_entry_2 *de;
1617 int err;
1618
1619 frame = dx_probe(icb, dentry, NULL, &hinfo, frames, &err);
1620 if (!frame)
1621 return err;
1622 entries = frame->entries;
1623 at = frame->at;
1624
1625 if (!(bh = ext3_bread(icb, dir, dx_get_block(frame->at), &err)))
1626 goto cleanup;
1627
1628 err = add_dirent_to_buf(icb, dentry, inode, NULL, bh);
1629 if (err != -ENOSPC) {
1630 bh = NULL;
1631 goto cleanup;
1632 }
1633
1634 /* Block full, should compress but for now just split */
1635 dxtrace(printk("using %u of %u node entries\n",
1636 dx_get_count(entries), dx_get_limit(entries)));
1637 /* Need to split index? */
1638 if (dx_get_count(entries) == dx_get_limit(entries)) {
1639 u32 newblock;
1640 unsigned icount = dx_get_count(entries);
1641 int levels = (int)(frame - frames);
1642 struct dx_entry *entries2;
1643 struct dx_node *node2;
1644 struct buffer_head *bh2;
1645
1646 if (levels && (dx_get_count(frames->entries) ==
1647 dx_get_limit(frames->entries))) {
1649 "Directory index full!");
1650 err = -ENOSPC;
1651 goto cleanup;
1652 }
1653 bh2 = ext3_append (icb, dir, &newblock, &err);
1654 if (!(bh2))
1655 goto cleanup;
1656 node2 = (struct dx_node *)(bh2->b_data);
1657 entries2 = node2->entries;
1658 node2->fake.rec_len = cpu_to_le16(sb->s_blocksize);
1659 node2->fake.inode = 0;
1660
1661 if (levels) {
1662 unsigned icount1 = icount/2, icount2 = icount - icount1;
1663 unsigned hash2 = dx_get_hash(entries + icount1);
1664 dxtrace(printk("Split index %i/%i\n", icount1, icount2));
1665
1666 memcpy ((char *) entries2, (char *) (entries + icount1),
1667 icount2 * sizeof(struct dx_entry));
1668 dx_set_count (entries, icount1);
1669 dx_set_count (entries2, icount2);
1670 dx_set_limit (entries2, dx_node_limit(dir));
1671
1672 /* Which index block gets the new entry? */
1673 if ((unsigned int)(at - entries) >= icount1) {
1674 frame->at = at = at - entries - icount1 + entries2;
1675 frame->entries = entries = entries2;
1676 swap(struct buffer_head *, frame->bh, bh2);
1677 }
1678 dx_insert_block (frames + 0, hash2, newblock);
1679 dxtrace(dx_show_index ("node", frames[1].entries));
1680 dxtrace(dx_show_index ("node",
1681 ((struct dx_node *) bh2->b_data)->entries));
1682 set_buffer_dirty(bh2);
1683 brelse (bh2);
1684 } else {
1685 dxtrace(printk("Creating second level index...\n"));
1686 memcpy((char *) entries2, (char *) entries,
1687 icount * sizeof(struct dx_entry));
1688 dx_set_limit(entries2, dx_node_limit(dir));
1689
1690 /* Set up root */
1691 dx_set_count(entries, 1);
1692 dx_set_block(entries + 0, newblock);
1693 ((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
1694
1695 /* Add new access path frame */
1696 frame = frames + 1;
1697 frame->at = at = at - entries + entries2;
1698 frame->entries = entries = entries2;
1699 frame->bh = bh2;
1700 }
1701 // ext3_journal_dirty_metadata(handle, frames[0].bh);
1702 set_buffer_dirty(frames[0].bh);
1703 }
1704 de = do_split(icb, dir, &bh, frame, &hinfo, &err);
1705 if (!de)
1706 goto cleanup;
1707 err = add_dirent_to_buf(icb, dentry, inode, de, bh);
1708 bh = NULL;
1709 goto cleanup;
1710
1711cleanup:
1712 if (bh)
1713 brelse(bh);
1714 dx_release(frames);
1715 return err;
1716}
1717
1718/*
1719 * Move count entries from end of map between two memory locations.
1720 * Returns pointer to last entry moved.
1721 */
1722struct ext3_dir_entry_2 *
1723 dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count)
1724{
1725 unsigned rec_len = 0;
1726
1727 while (count--) {
1728 struct ext3_dir_entry_2 *de = (struct ext3_dir_entry_2 *) (from + map->offs);
1730 memcpy (to, de, rec_len);
1731 ((struct ext3_dir_entry_2 *) to)->rec_len =
1733 de->inode = 0;
1734 map++;
1735 to += rec_len;
1736 }
1737 return (struct ext3_dir_entry_2 *) (to - rec_len);
1738}
1739
1740/*
1741 * Compact each dir entry in the range to the minimal rec_len.
1742 * Returns pointer to last entry in range.
1743 */
1744struct ext3_dir_entry_2* dx_pack_dirents(char *base, int size)
1745{
1746 struct ext3_dir_entry_2 *next, *to, *prev, *de = (struct ext3_dir_entry_2 *) base;
1747 unsigned rec_len = 0;
1748
1749 prev = to = de;
1750 while ((char*)de < base + size) {
1751 next = (struct ext3_dir_entry_2 *) ((char *) de +
1752 le16_to_cpu(de->rec_len));
1753 if (de->inode && de->name_len) {
1755 if (de > to)
1756 memmove(to, de, rec_len);
1758 prev = to;
1759 to = (struct ext3_dir_entry_2 *) (((char *) to) + rec_len);
1760 }
1761 de = next;
1762 }
1763 return prev;
1764}
1765
1766/*
1767 * Split a full leaf block to make room for a new dir entry.
1768 * Allocate a new block, and move entries so that they are approx. equally full.
1769 * Returns pointer to de in block into which the new entry will be inserted.
1770 */
1771struct ext3_dir_entry_2 *
1772 do_split(struct ext2_icb *icb, struct inode *dir,
1773 struct buffer_head **bh,struct dx_frame *frame,
1774 struct dx_hash_info *hinfo, int *error)
1775{
1776 unsigned blocksize = dir->i_sb->s_blocksize;
1777 unsigned count, continued;
1778 struct buffer_head *bh2;
1779 u32 newblock;
1780 u32 hash2;
1781 struct dx_map_entry *map;
1782 char *data1 = (*bh)->b_data, *data2;
1783 unsigned split, move, size;
1784 struct ext3_dir_entry_2 *de = NULL, *de2;
1785 int err, i;
1786
1787 bh2 = ext3_append (icb, dir, &newblock, error);
1788 if (!(bh2)) {
1789 brelse(*bh);
1790 *bh = NULL;
1791 goto errout;
1792 }
1793
1794 data2 = bh2->b_data;
1795
1796 /* create map in the end of data2 block */
1797 map = (struct dx_map_entry *) (data2 + blocksize);
1798 count = dx_make_map ((struct ext3_dir_entry_2 *) data1,
1799 blocksize, hinfo, map);
1800 map -= count;
1801 dx_sort_map (map, count);
1802 /* Split the existing block in the middle, size-wise */
1803 size = 0;
1804 move = 0;
1805 for (i = count-1; i >= 0; i--) {
1806 /* is more than half of this entry in 2nd half of the block? */
1807 if (size + map[i].size/2 > blocksize/2)
1808 break;
1809 size += map[i].size;
1810 move++;
1811 }
1812 /* map index at which we will split */
1813 split = count - move;
1814 hash2 = map[split].hash;
1815 continued = hash2 == map[split - 1].hash;
1816 dxtrace(printk("Split block %i at %x, %i/%i\n",
1817 dx_get_block(frame->at), hash2, split, count-split));
1818
1819 /* Fancy dance to stay within two buffers */
1820 de2 = dx_move_dirents(data1, data2, map + split, count - split);
1821 de = dx_pack_dirents(data1,blocksize);
1822 de->rec_len = cpu_to_le16(data1 + blocksize - (char *) de);
1823 de2->rec_len = cpu_to_le16(data2 + blocksize - (char *) de2);
1824 dxtrace(dx_show_leaf (icb, hinfo, (struct ext3_dir_entry_2 *) data1, blocksize, 1));
1825 dxtrace(dx_show_leaf (icb, hinfo, (struct ext3_dir_entry_2 *) data2, blocksize, 1));
1826
1827 /* Which block gets the new entry? */
1828 if (hinfo->hash >= hash2)
1829 {
1830 swap(struct buffer_head *, *bh, bh2);
1831 de = de2;
1832 }
1833 dx_insert_block (frame, hash2 + continued, newblock);
1834 set_buffer_dirty(bh2);
1835 set_buffer_dirty(frame->bh);
1836
1837 brelse (bh2);
1838 dxtrace(dx_show_index ("frame", frame->entries));
1839errout:
1840 return de;
1841}
1842
1843/*
1844 * This converts a one block unindexed directory to a 3 block indexed
1845 * directory, and adds the dentry to the indexed directory.
1846 */
1847int make_indexed_dir(struct ext2_icb *icb, struct dentry *dentry,
1848 struct inode *inode, struct buffer_head *bh)
1849{
1850 struct inode *dir = dentry->d_parent->d_inode;
1851 const char *name = dentry->d_name.name;
1852 int namelen = dentry->d_name.len;
1853 struct buffer_head *bh2;
1854 struct dx_root *root;
1855 struct dx_frame frames[2], *frame;
1856 struct dx_entry *entries;
1857 struct ext3_dir_entry_2 *de, *de2;
1858 char *data1, *top;
1859 unsigned len;
1860 int retval;
1861 unsigned blocksize;
1862 struct dx_hash_info hinfo;
1864 struct fake_dirent *fde;
1865
1866 blocksize = dir->i_sb->s_blocksize;
1867 dxtrace(printk("Creating index: inode %lu\n", dir->i_ino));
1868
1869 root = (struct dx_root *) bh->b_data;
1870
1871 /* The 0th block becomes the root, move the dirents out */
1872 fde = &root->dotdot;
1873 de = (struct ext3_dir_entry_2 *)((char *)fde +
1874 ext3_rec_len_from_disk(fde->rec_len));
1875 if ((char *) de >= (((char *) root) + blocksize)) {
1876 DEBUG(DL_ERR, ( "%s: invalid rec_len for '..' in inode %lu", __FUNCTION__,
1877 dir->i_ino));
1878 brelse(bh);
1879 return -EIO;
1880 }
1881 len = (unsigned int)((char *) root + blocksize - (char *) de);
1882
1883 /* Allocate new block for the 0th block's dirents */
1884 bh2 = ext3_append(icb, dir, &block, &retval);
1885 if (!(bh2)) {
1886 brelse(bh);
1887 return retval;
1888 }
1889 EXT3_I(dir)->i_flags |= EXT3_INDEX_FL;
1890 data1 = bh2->b_data;
1891
1892 memcpy (data1, de, len);
1893 de = (struct ext3_dir_entry_2 *) data1;
1894 top = data1 + len;
1895 while ((char *)(de2 = ext3_next_entry(de)) < top)
1896 de = de2;
1897 de->rec_len = ext3_rec_len_to_disk(blocksize + (__u32)(data1 - (char *)de));
1898 /* Initialize the root; the dot dirents already exist */
1899 de = (struct ext3_dir_entry_2 *) (&root->dotdot);
1900 de->rec_len = ext3_rec_len_to_disk(blocksize - EXT3_DIR_REC_LEN(2));
1901 memset (&root->info, 0, sizeof(root->info));
1902 root->info.info_length = sizeof(root->info);
1903 root->info.hash_version = (__u8)(EXT3_SB(dir->i_sb)->s_def_hash_version);
1904 entries = root->entries;
1905 dx_set_block(entries, 1);
1906 dx_set_count(entries, 1);
1907 dx_set_limit(entries, dx_root_limit(dir, sizeof(root->info)));
1908
1909 /* Initialize as for dx_probe */
1910 hinfo.hash_version = root->info.hash_version;
1911 hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed;
1912 ext3_dirhash(name, namelen, &hinfo);
1913 frame = frames;
1914 frame->entries = entries;
1915 frame->at = entries;
1916 frame->bh = bh;
1917 bh = bh2;
1918 /* bh and bh2 are to be marked as dirty in do_split */
1919 de = do_split(icb, dir, &bh, frame, &hinfo, &retval);
1920 dx_release (frames);
1921 if (!(de))
1922 return retval;
1923
1924 return add_dirent_to_buf(icb, dentry, inode, de, bh);
1925}
1926
1927#else /* EXT2_HTREE_INDEX */
1928
1929int ext3_release_dir (struct inode * inode, struct file * filp)
1930{
1931 return 0;
1932}
1933
1934#endif /* !EXT2_HTREE_INDEX */
1935
1936/*
1937 * ext3_add_entry()
1938 *
1939 * adds a file entry to the specified directory, using the same
1940 * semantics as ext3_find_entry(). It returns NULL if it failed.
1941 *
1942 * NOTE!! The inode part of 'de' is left at 0 - which means you
1943 * may not sleep between calling this and putting something into
1944 * the entry, as someone else might have used it while you slept.
1945 */
1946int ext3_add_entry(struct ext2_icb *icb, struct dentry *dentry, struct inode *inode)
1947{
1948 struct inode *dir = dentry->d_parent->d_inode;
1949 struct buffer_head *bh;
1950 struct ext3_dir_entry_2 *de;
1951 struct super_block *sb;
1952 int retval;
1953#ifdef EXT2_HTREE_INDEX
1954 int dx_fallback=0;
1955#endif
1956 unsigned blocksize;
1958
1959 sb = dir->i_sb;
1960 blocksize = sb->s_blocksize;
1961 if (!dentry->d_name.len)
1962 return -EINVAL;
1963
1964#ifdef EXT2_HTREE_INDEX
1965 if (is_dx(dir)) {
1966 retval = ext3_dx_add_entry(icb, dentry, inode);
1967 if (!retval || (retval != ERR_BAD_DX_DIR))
1968 return retval;
1969 EXT3_I(dir)->i_flags &= ~EXT3_INDEX_FL;
1970 dx_fallback++;
1971 ext3_save_inode(icb, dir);
1972 }
1973#endif
1974
1975 blocks = (ext3_lblk_t)(dir->i_size >> sb->s_blocksize_bits);
1976 for (block = 0; block < blocks; block++) {
1977 bh = ext3_bread(icb, dir, block, &retval);
1978 if (!bh)
1979 return retval;
1980 retval = add_dirent_to_buf(icb, dentry, inode, NULL, bh);
1981 if (retval != -ENOSPC)
1982 return retval;
1983
1984#ifdef EXT2_HTREE_INDEX
1985 if (blocks == 1 && !dx_fallback &&
1987 return make_indexed_dir(icb, dentry, inode, bh);
1988#endif
1989
1990 brelse(bh);
1991 }
1992 bh = ext3_append(icb, dir, &block, &retval);
1993 if (!bh)
1994 return retval;
1995 de = (struct ext3_dir_entry_2 *) bh->b_data;
1996 de->inode = 0;
1997 de->rec_len = ext3_rec_len_to_disk(blocksize);
1998 return add_dirent_to_buf(icb, dentry, inode, de, bh);
1999}
2000
2001/*
2002 * ext3_delete_entry deletes a directory entry by merging it with the
2003 * previous entry
2004 */
2005int ext3_delete_entry(struct ext2_icb *icb, struct inode *dir,
2006 struct ext3_dir_entry_2 *de_del,
2007 struct buffer_head *bh)
2008{
2009 struct ext3_dir_entry_2 *de, *pde = NULL;
2010 size_t i = 0;
2011
2012 de = (struct ext3_dir_entry_2 *) bh->b_data;
2013 while (i < bh->b_size) {
2014 if (!ext3_check_dir_entry("ext3_delete_entry", dir, de, bh, i))
2015 return -EIO;
2016 if (de == de_del) {
2017 if (pde)
2021 else
2022 de->inode = 0;
2023 dir->i_version++;
2024 /* ext3_journal_dirty_metadata(handle, bh); */
2025 set_buffer_dirty(bh);
2026 return 0;
2027 }
2029 pde = de;
2030 de = ext3_next_entry(de);
2031 }
2032 return -ENOENT;
2033}
2034
2035/*
2036 * routine to check that the specified directory is empty (for rmdir)
2037 */
2038int ext3_is_dir_empty(struct ext2_icb *icb, struct inode *inode)
2039{
2040 unsigned int offset;
2041 struct buffer_head *bh;
2042 struct ext3_dir_entry_2 *de, *de1;
2043 struct super_block *sb;
2044 int err = 0;
2045
2046 sb = inode->i_sb;
2048 !(bh = ext3_bread(icb, inode, 0, &err))) {
2049 if (err)
2051 "error %d reading directory #%lu offset 0",
2052 err, inode->i_ino);
2053 else
2055 "bad directory (dir #%lu) - no data block",
2056 inode->i_ino);
2057 return 1;
2058 }
2059 de = (struct ext3_dir_entry_2 *) bh->b_data;
2060 de1 = ext3_next_entry(de);
2061 if (le32_to_cpu(de->inode) != inode->i_ino ||
2062 !le32_to_cpu(de1->inode) ||
2063 strcmp(".", de->name) ||
2064 strcmp("..", de1->name)) {
2065 ext3_warning(inode->i_sb, "empty_dir",
2066 "bad directory (dir #%lu) - no `.' or `..'",
2067 inode->i_ino);
2068 brelse(bh);
2069 return 1;
2070 }
2073 de = ext3_next_entry(de1);
2074 while (offset < inode->i_size) {
2075 if (!bh ||
2076 (void *) de >= (void *) (bh->b_data+sb->s_blocksize)) {
2077 err = 0;
2078 brelse(bh);
2080 if (!bh) {
2081 if (err)
2082 ext3_error(sb, __FUNCTION__, "error %d reading directory"
2083 " #%lu offset %u", err, inode->i_ino, offset);
2084 offset += sb->s_blocksize;
2085 continue;
2086 }
2087 de = (struct ext3_dir_entry_2 *) bh->b_data;
2088 }
2089 if (!ext3_check_dir_entry("empty_dir", inode, de, bh, offset)) {
2090 de = (struct ext3_dir_entry_2 *)(bh->b_data +
2091 sb->s_blocksize);
2092 offset = (offset | (sb->s_blocksize - 1)) + 1;
2093 continue;
2094 }
2095 if (le32_to_cpu(de->inode)) {
2096 brelse(bh);
2097 return 0;
2098 }
2100 de = ext3_next_entry(de);
2101 }
2102 brelse(bh);
2103 return 1;
2104}
2105
2106/*
2107 * Returns 0 if not found, -1 on failure, and 1 on success
2108 */
2109static inline int search_dirblock(struct buffer_head * bh,
2110 struct inode *dir,
2111 struct dentry *dentry,
2112 unsigned long offset,
2113 struct ext3_dir_entry_2 ** res_dir)
2114{
2115 struct ext3_dir_entry_2 * de;
2116 char * dlimit;
2117 int de_len;
2118 const char *name = dentry->d_name.name;
2119 int namelen = dentry->d_name.len;
2120
2121 de = (struct ext3_dir_entry_2 *) bh->b_data;
2122 dlimit = bh->b_data + dir->i_sb->s_blocksize;
2123 while ((char *) de < dlimit) {
2124 /* this code is executed quadratically often */
2125 /* do minimal checking `by hand' */
2126
2127 if ((char *) de + namelen <= dlimit &&
2128 ext3_match (namelen, name, de)) {
2129 /* found a match - just to be sure, do a full check */
2130 if (!ext3_check_dir_entry("ext3_find_entry",
2131 dir, de, bh, offset))
2132 return -1;
2133 *res_dir = de;
2134 return 1;
2135 }
2136 /* prevent looping on a bad block */
2137 de_len = ext3_rec_len_from_disk(de->rec_len);
2138
2139 if (de_len <= 0)
2140 return -1;
2141 offset += de_len;
2142 de = (struct ext3_dir_entry_2 *) ((char *) de + de_len);
2143 }
2144 return 0;
2145}
2146
2147/*
2148 * define how far ahead to read directories while searching them.
2149 */
2150#define NAMEI_RA_CHUNKS 2
2151#define NAMEI_RA_BLOCKS 4
2152#define NAMEI_RA_SIZE (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)
2153#define NAMEI_RA_INDEX(c,b) (((c) * NAMEI_RA_BLOCKS) + (b))
2154
2155/*
2156 * ext4_find_entry()
2157 *
2158 * finds an entry in the specified directory with the wanted name. It
2159 * returns the cache buffer in which the entry was found, and the entry
2160 * itself (as a parameter - res_dir). It does NOT read the inode of the
2161 * entry - you'll have to do that yourself if you want to.
2162 *
2163 * The returned buffer_head has ->b_count elevated. The caller is expected
2164 * to brelse() it when appropriate.
2165 */
2167 struct dentry *dentry,
2168 struct ext3_dir_entry_2 ** res_dir)
2169{
2170 struct inode *dir = dentry->d_parent->d_inode;
2171 struct super_block *sb = dir->i_sb;
2172 struct buffer_head *bh_use[NAMEI_RA_SIZE];
2173 struct buffer_head *bh, *ret = NULL;
2175 int ra_max = 0; /* Number of bh's in the readahead
2176 buffer, bh_use[] */
2177 int ra_ptr = 0; /* Current index into readahead
2178 buffer */
2179 int num = 0;
2180 ext3_lblk_t nblocks;
2181 int i, err;
2182 int namelen = dentry->d_name.len;
2183
2184 *res_dir = NULL;
2185 if (namelen > EXT3_NAME_LEN)
2186 return NULL;
2187
2188#ifdef EXT2_HTREE_INDEX
2189 if (icb->MajorFunction != IRP_MJ_CREATE && is_dx(dir)) {
2190 bh = ext3_dx_find_entry(icb, dentry, res_dir, &err);
2191 /*
2192 * On success, or if the error was file not found,
2193 * return. Otherwise, fall back to doing a search the
2194 * old fashioned way.
2195 */
2196 if (bh || (err != ERR_BAD_DX_DIR))
2197 return bh;
2198 dxtrace(printk("ext4_find_entry: dx failed, "
2199 "falling back\n"));
2200 }
2201#endif
2202
2203 nblocks = (ext3_lblk_t)(dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb));
2204 start = 0;
2205 block = start;
2206restart:
2207 do {
2208 /*
2209 * We deal with the read-ahead logic here.
2210 */
2211 if (ra_ptr >= ra_max) {
2212 /* Refill the readahead buffer */
2213 ra_ptr = 0;
2214 b = block;
2215 for (ra_max = 0; ra_max < NAMEI_RA_SIZE; ra_max++) {
2216 /*
2217 * Terminate if we reach the end of the
2218 * directory and must wrap, or if our
2219 * search has finished at this block.
2220 */
2221 if (b >= nblocks || (num && block == start)) {
2222 bh_use[ra_max] = NULL;
2223 break;
2224 }
2225 num++;
2226 bh = ext3_bread(icb, dir, b++, &err);
2227 bh_use[ra_max] = bh;
2228 }
2229 }
2230 if ((bh = bh_use[ra_ptr++]) == NULL)
2231 goto next;
2232 wait_on_buffer(bh);
2233 if (!buffer_uptodate(bh)) {
2234 /* read error, skip block & hope for the best */
2235 ext3_error(sb, __FUNCTION__, "reading directory #%lu "
2236 "offset %lu", dir->i_ino,
2237 (unsigned long)block);
2238 brelse(bh);
2239 goto next;
2240 }
2241 i = search_dirblock(bh, dir, dentry,
2242 block << EXT3_BLOCK_SIZE_BITS(sb), res_dir);
2243 if (i == 1) {
2244 ret = bh;
2245 goto cleanup_and_exit;
2246 } else {
2247 brelse(bh);
2248 if (i < 0)
2249 goto cleanup_and_exit;
2250 }
2251next:
2252 if (++block >= nblocks)
2253 block = 0;
2254 } while (block != start);
2255
2256 /*
2257 * If the directory has grown while we were searching, then
2258 * search the last part of the directory before giving up.
2259 */
2260 block = nblocks;
2261 nblocks = (ext3_lblk_t)(dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb));
2262 if (block < nblocks) {
2263 start = 0;
2264 goto restart;
2265 }
2266
2267cleanup_and_exit:
2268 /* Clean up the read-ahead blocks */
2269 for (; ra_ptr < ra_max; ra_ptr++)
2270 brelse(bh_use[ra_ptr]);
2271 return ret;
2272}
#define ENOENT
Definition: acclib.h:79
#define EEXIST
Definition: acclib.h:88
#define EINVAL
Definition: acclib.h:90
int strcmp(const char *String1, const char *String2)
Definition: utclib.c:469
#define ENOMEM
Definition: acclib.h:84
#define EIO
Definition: acclib.h:81
char * va_list
Definition: acmsvcex.h:78
#define va_end(ap)
Definition: acmsvcex.h:90
#define va_start(ap, A)
Definition: acmsvcex.h:91
#define S_IFDIR
Definition: acwin.h:115
unsigned int dir
Definition: maze.c:112
#define msg(x)
Definition: auth_time.c:54
LONG NTSTATUS
Definition: precomp.h:26
#define DEBUG(args)
Definition: rdesktop.h:129
void restart(int argc, const char *argv[])
Definition: cmds.c:2115
PFOR_CONTEXT fc
Definition: for.c:57
#define G(r, i, a, b, c, d)
Definition: blake2b-ref.c:117
#define ROUND(r)
Definition: blake2b-ref.c:129
u16 __u16
Definition: btrfs.h:18
u8 __u8
Definition: btrfs.h:17
ULONG32 u32
Definition: btrfs.h:14
u32 __u32
Definition: btrfs.h:19
struct _root root
while(CdLookupNextInitialFileDirent(IrpContext, Fcb, FileContext))
Definition: _map.h:48
size_type size() const
Definition: _map.h:172
static LPSTR * split(LPSTR s, LPINT args)
Definition: cmdcons.c:163
#define NULL
Definition: types.h:112
#define FALSE
Definition: types.h:117
#define NT_SUCCESS(StatCode)
Definition: apphelp.c:32
BOOL next_node(stream_t *stream, strbuf_t *buf)
Definition: stream.c:140
static void cleanup(void)
Definition: main.c:1335
unsigned int(__cdecl typeof(jpeg_read_scanlines))(struct jpeg_decompress_struct *
Definition: typeof.h:31
superblock * sb
Definition: btrfs.c:4261
r parent
Definition: btrfs.c:3010
#define ENOSPC
Definition: errno.h:34
#define DT_DIR
Definition: fs.h:149
#define DT_BLK
Definition: fs.h:150
#define DT_UNKNOWN
Definition: fs.h:146
#define DT_FIFO
Definition: fs.h:147
#define DT_CHR
Definition: fs.h:148
#define DT_REG
Definition: fs.h:151
#define DT_LNK
Definition: fs.h:152
#define DT_SOCK
Definition: fs.h:153
static void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)
Definition: rbtree.h:149
struct rb_node * rb_first(struct rb_root *)
Definition: rbtree.c:294
struct rb_node * rb_next(struct rb_node *)
Definition: rbtree.c:320
struct rb_node * rb_left
Definition: rbtree.h:4
void rb_insert_color(struct rb_node *, struct rb_root *)
Definition: rbtree.c:71
#define rb_parent(r)
Definition: rbtree.h:113
#define rb_entry(ptr, type, member)
Definition: rbtree.h:130
#define __le16
Definition: types.h:39
#define __le32
Definition: types.h:40
#define __FUNCTION__
Definition: types.h:112
unsigned short umode_t
Definition: types.h:71
unsigned __int64 loff_t
Definition: types.h:80
#define u16
Definition: types.h:8
#define __u32
Definition: types.h:15
#define __u8
Definition: types.h:12
#define KeQuerySystemTime(t)
Definition: env_spec_w32.h:570
#define IsMcbSymLink(Mcb)
Definition: ext2fs.h:953
#define S_IFREG
Definition: ext2fs.h:356
#define S_IFSOCK
Definition: ext2fs.h:354
struct ext3_dir_entry_2 * do_split(struct ext2_icb *icb, struct inode *dir, struct buffer_head **bh, struct dx_frame *frame, struct dx_hash_info *hinfo, int *error)
struct buffer_head * ext3_dx_find_entry(struct ext2_icb *, struct dentry *dentry, struct ext3_dir_entry_2 **res_dir, int *err)
int ext3_check_dir_entry(const char *function, struct inode *dir, struct ext3_dir_entry_2 *de, struct buffer_head *bh, unsigned long offset)
Definition: generic.c:2135
#define S_IFIFO
Definition: ext2fs.h:360
BOOLEAN Ext2SaveInode(IN PEXT2_IRP_CONTEXT IrpContext, IN PEXT2_VCB Vcb, IN struct inode *Inode)
Definition: generic.c:548
#define S_IFBLK
Definition: ext2fs.h:357
int ext3_dx_readdir(struct file *filp, filldir_t filldir, void *context)
NTSTATUS Ext2MapExtent(IN PEXT2_IRP_CONTEXT IrpContext, IN PEXT2_VCB Vcb, IN PEXT2_MCB Mcb, IN ULONG Index, IN BOOLEAN Alloc, OUT PULONG Block, OUT PULONG Number)
Definition: extents.c:25
ULONG Ext2LinuxTime(IN LARGE_INTEGER SysTime)
Definition: misc.c:51
#define S_IFMT
Definition: ext2fs.h:353
#define ext3_error
Definition: ext2fs.h:2475
#define DL_ERR
Definition: ext2fs.h:1397
NTSTATUS Ext2ExpandFile(PEXT2_IRP_CONTEXT IrpContext, PEXT2_VCB Vcb, PEXT2_MCB Mcb, PLARGE_INTEGER Size)
Definition: fileinfo.c:1147
NTSTATUS Ext2MapIndirect(IN PEXT2_IRP_CONTEXT IrpContext, IN PEXT2_VCB Vcb, IN PEXT2_MCB Mcb, IN ULONG Index, IN BOOLEAN bAlloc, OUT PULONG pBlock, OUT PULONG Number)
Definition: indirect.c:823
struct ext3_dir_entry_2 * ext3_next_entry(struct ext3_dir_entry_2 *p)
Definition: generic.c:2170
int(* filldir_t)(void *, const char *, int, unsigned long, __u32, unsigned)
Definition: ext2fs.h:2491
int Ext2LinuxError(NTSTATUS Status)
Definition: misc.c:304
#define S_IFCHR
Definition: ext2fs.h:359
#define S_IFLNK
Definition: ext2fs.h:355
#define DX_HASH_LEGACY_UNSIGNED
Definition: ext3_fs.h:911
#define DX_HASH_HALF_MD4
Definition: ext3_fs.h:909
#define EXT3_FEATURE_INCOMPAT_FILETYPE
Definition: ext3_fs.h:679
static __le16 ext3_rec_len_to_disk(unsigned len)
Definition: ext3_fs.h:880
#define EXT3_DIRENT_LUFID
Definition: ext3_fs.h:859
#define EXT3_FT_FIFO
Definition: ext3_fs.h:791
#define EXT3_SB(sb)
Definition: ext3_fs.h:615
#define EXT3_FT_SOCK
Definition: ext3_fs.h:792
#define EXT3_FEATURE_COMPAT_DIR_INDEX
Definition: ext3_fs.h:669
#define EXT3_FT_MAX
Definition: ext3_fs.h:795
#define EXT3_FT_DIR
Definition: ext3_fs.h:788
#define EXT3_DIR_REC_LEN(len)
Definition: ext3_fs.h:867
#define EXT3_NAME_LEN
Definition: ext3_fs.h:759
#define EXT3_HAS_COMPAT_FEATURE(sb, mask)
Definition: ext3_fs.h:645
#define EXT3_FT_UNKNOWN
Definition: ext3_fs.h:786
#define EXT3_FT_BLKDEV
Definition: ext3_fs.h:790
#define EXT3_HAS_INCOMPAT_FEATURE(sb, mask)
Definition: ext3_fs.h:649
#define EXT3_INDEX_FL
Definition: ext3_fs.h:220
#define EXT3_FT_REG_FILE
Definition: ext3_fs.h:787
#define EXT3_FT_SYMLINK
Definition: ext3_fs.h:793
#define DX_HASH_TEA
Definition: ext3_fs.h:910
static unsigned ext3_rec_len_from_disk(__le16 dlen)
Definition: ext3_fs.h:871
#define DX_HASH_TEA_UNSIGNED
Definition: ext3_fs.h:913
#define EXT3_BLOCK_SIZE_BITS(s)
Definition: ext3_fs.h:87
#define is_dx(dir)
Definition: ext3_fs.h:901
#define DX_HASH_HALF_MD4_UNSIGNED
Definition: ext3_fs.h:912
#define DX_HASH_LEGACY
Definition: ext3_fs.h:908
#define EXT3_FT_CHRDEV
Definition: ext3_fs.h:789
static int ext3_get_dirent_data_len(struct ext3_dir_entry_2 *de)
Definition: ext3_fs.h:831
__u32 ext3_lblk_t
Definition: ext3_fs_i.h:30
#define INODE_HAS_EXTENT(i)
Definition: ext4_ext.h:228
IN PVCB IN ULONG IN OUT PULONG IN BOOLEAN OUT PLARGE_MCB Mcb
Definition: fatprocs.h:348
GLuint start
Definition: gl.h:1545
GLuint GLuint GLsizei GLenum type
Definition: gl.h:1545
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
GLsizeiptr size
Definition: glext.h:5919
GLdouble n
Definition: glext.h:7729
const GLvoid * indirect
Definition: glext.h:7408
GLuint GLuint * names
Definition: glext.h:11545
const GLubyte * c
Definition: glext.h:8905
GLint namelen
Definition: glext.h:7232
GLdouble GLdouble GLdouble GLdouble top
Definition: glext.h:10859
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLint limit
Definition: glext.h:10326
GLenum GLint * range
Definition: glext.h:7539
GLenum mode
Definition: glext.h:6217
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
GLuint in
Definition: glext.h:9616
GLsizei levels
Definition: glext.h:7884
GLuint GLfloat * val
Definition: glext.h:7180
GLfloat GLfloat p
Definition: glext.h:8902
GLuint GLuint num
Definition: glext.h:9618
GLenum GLsizei len
Definition: glext.h:6722
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
GLintptr offset
Definition: glext.h:5920
const GLfloat * m
Definition: glext.h:10848
GLfloat GLfloat GLfloat GLfloat h
Definition: glext.h:7723
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
unsigned char ext3_type_by_mode(umode_t mode)
Definition: htree.c:317
__u32 ext3_current_time(struct inode *in)
Definition: htree.c:204
#define NAMEI_RA_SIZE
Definition: htree.c:2152
int ext3_mark_inode_dirty(struct ext2_icb *icb, struct inode *in)
Definition: htree.c:360
struct buffer_head * ext3_find_entry(struct ext2_icb *icb, struct dentry *dentry, struct ext3_dir_entry_2 **res_dir)
Definition: htree.c:2166
int ext3_is_dir_empty(struct ext2_icb *icb, struct inode *inode)
Definition: htree.c:2038
void ext3_warning(struct super_block *sb, const char *function, char *fmt,...)
Definition: htree.c:212
struct buffer_head * ext3_bread(struct ext2_icb *icb, struct inode *inode, unsigned long block, int *err)
Definition: htree.c:230
int ext3_add_entry(struct ext2_icb *icb, struct dentry *dentry, struct inode *inode)
Definition: htree.c:1946
void ext3_dec_count(struct inode *inode)
Definition: htree.c:312
static int search_dirblock(struct buffer_head *bh, struct inode *dir, struct dentry *dentry, unsigned long offset, struct ext3_dir_entry_2 **res_dir)
Definition: htree.c:2109
int ext3_release_dir(struct inode *inode, struct file *filp)
Definition: htree.c:1929
struct buffer_head * ext3_append(struct ext2_icb *icb, struct inode *inode, ext3_lblk_t *block, int *err)
Definition: htree.c:279
int ext3_delete_entry(struct ext2_icb *icb, struct inode *dir, struct ext3_dir_entry_2 *de_del, struct buffer_head *bh)
Definition: htree.c:2005
void ext3_set_de_type(struct super_block *sb, struct ext3_dir_entry_2 *de, umode_t mode)
Definition: htree.c:347
void ext3_update_dx_flag(struct inode *inode)
Definition: htree.c:368
int add_dirent_to_buf(struct ext2_icb *icb, struct dentry *dentry, struct inode *inode, struct ext3_dir_entry_2 *de, struct buffer_head *bh)
Definition: htree.c:386
void ext3_inc_count(struct inode *inode)
Definition: htree.c:307
uint32_t entry
Definition: isohybrid.c:63
#define d
Definition: ke_i.h:81
#define a
Definition: ke_i.h:78
#define c
Definition: ke_i.h:80
#define b
Definition: ke_i.h:79
if(dx< 0)
Definition: linetemp.h:194
static int blocks
Definition: mkdosfs.c:527
#define error(str)
Definition: mkdosfs.c:1605
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
#define memmove(s1, s2, n)
Definition: mkisofs.h:881
#define ASSERT(a)
Definition: mode.c:44
#define EXPORT_SYMBOL(x)
Definition: module.h:270
static int cond_resched()
Definition: module.h:432
#define kmalloc(size, gfp)
Definition: module.h:1115
#define GFP_KERNEL
Definition: module.h:658
#define le16_to_cpu
Definition: module.h:149
#define cpu_to_le32
Definition: module.h:146
#define printk
Definition: module.h:229
static void wait_on_buffer(struct buffer_head *bh)
Definition: module.h:1011
int bh_submit_read(struct buffer_head *bh)
Definition: linux.c:884
static struct buffer_head * sb_getblk(struct super_block *sb, sector_t block)
Definition: module.h:966
#define kfree(p)
Definition: module.h:1116
#define le32_to_cpu
Definition: module.h:147
static void brelse(struct buffer_head *bh)
Definition: module.h:945
void __brelse(struct buffer_head *)
Definition: linux.c:800
#define cpu_to_le16
Definition: module.h:148
static const WCHAR label[]
Definition: itemdlg.c:1546
static CRYPT_DATA_BLOB b1[]
Definition: msg.c:573
#define H
static int sum(int x_, int y_)
Definition: ptr2_test.cpp:35
#define swap(a, b)
Definition: qsort.c:63
static unsigned __int64 next
Definition: rand_nt.c:6
#define IRP_MJ_CREATE
Definition: rdpdr.c:44
#define err(...)
#define F(x, y, z)
Definition: md5.c:51
FD_TYPE file_type(FDSC **curr, char *fixed)
Definition: file.c:221
#define memset(x, y, z)
Definition: compat.h:39
#define args
Definition: format.c:66
LOCAL char * filetype(int t)
Definition: tree.c:114
#define STATUS_SUCCESS
Definition: shellext.h:65
CardRegion * from
Definition: spigame.cpp:19
struct inode * Inode
Definition: ext2fs.h:857
PEXT2_VCB Vcb
Definition: ext2fs.h:860
PEXT2_FCB Fcb
Definition: ext2fs.h:905
struct inode Inode
Definition: ext2fs.h:936
ULONG BlockSize
Definition: ext2fs.h:719
Definition: match.c:390
char * b_data
Definition: module.h:725
Definition: http.c:7252
Definition: cookie.c:34
WCHAR * name
Definition: cookie.c:36
Definition: tftpd.h:126
Definition: tftpd.h:138
struct define * next
Definition: compiler.c:65
Definition: fs.h:117
struct dentry * d_parent
Definition: fs.h:124
struct dentry::@695 d_name
Definition: fatfs.h:198
UCHAR MajorFunction
Definition: ext2fs.h:1047
Definition: ext3_fs.h:774
char name[EXT3_NAME_LEN]
Definition: ext3_fs.h:779
__le32 inode
Definition: ext3_fs.h:775
__u8 name_len
Definition: ext3_fs.h:777
__le16 rec_len
Definition: ext3_fs.h:776
__u8 file_type
Definition: ext3_fs.h:778
Definition: fci.c:127
__u32 f_version
Definition: fs.h:133
loff_t f_pos
Definition: fs.h:135
void * private_data
Definition: fs.h:137
struct dentry * f_dentry
Definition: fs.h:136
Definition: dsound.c:943
Definition: _hash_fun.h:40
Definition: fs.h:78
__u32 i_version
Definition: fs.h:93
__u32 i_ino
Definition: fs.h:79
loff_t i_size
Definition: fs.h:80
__u32 i_flags
Definition: fs.h:94
umode_t i_mode
Definition: fs.h:87
struct super_block * i_sb
Definition: fs.h:96
__u16 i_nlink
Definition: fs.h:91
Definition: name.c:39
Definition: rbtree.h:98
Definition: ps.c:97
Definition: fs.h:64
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
uint32_t ULONG
Definition: typedefs.h:59
Definition: pdh_main.c:94
int ret
static unsigned int block
Definition: xmlmemory.c:101