3 fs/ext3/namei.c | 582 +++++++++++++++++++++++++++++++++++++---------
5 include/linux/ext3_fs.h | 1
6 include/linux/ext3_fs_i.h | 6
7 6 files changed, 500 insertions(+), 109 deletions(-)
9 Index: linux-2.4.24/fs/ext3/namei.c
10 ===================================================================
11 --- linux-2.4.24.orig/fs/ext3/namei.c 2004-04-01 20:22:17.000000000 +0400
12 +++ linux-2.4.24/fs/ext3/namei.c 2004-04-01 20:24:48.000000000 +0400
15 struct buffer_head *bh;
17 + /* with parallel dir operations all appends
18 + * have to be serialized -bzzz */
19 + down(&EXT3_I(inode)->i_append_sem);
20 *block = inode->i_size >> inode->i_sb->s_blocksize_bits;
22 if ((bh = ext3_bread(handle, inode, *block, 1, err))) {
24 EXT3_I(inode)->i_disksize = inode->i_size;
25 ext3_journal_get_write_access(handle,bh);
27 + up(&EXT3_I(inode)->i_append_sem);
33 struct buffer_head *bh;
34 struct dx_entry *entries;
37 + unsigned int curidx;
45 +/* FIXME: this should be reworked using bb_spin_lock
46 + * introduced in -mm tree
50 +static inline void dx_lock_bh(struct buffer_head volatile *bh)
53 + while (test_and_set_bit(BH_DXLock, &bh->b_state)) {
54 + while (test_bit(BH_DXLock, &bh->b_state))
60 +static inline void dx_unlock_bh(struct buffer_head *bh)
63 + smp_mb__before_clear_bit();
64 + clear_bit(BH_DXLock, &bh->b_state);
69 #ifdef CONFIG_EXT3_INDEX
70 static inline unsigned dx_get_block (struct dx_entry *entry);
71 static void dx_set_block (struct dx_entry *entry, unsigned value);
73 static void dx_set_limit (struct dx_entry *entries, unsigned value);
74 static unsigned dx_root_limit (struct inode *dir, unsigned infosize);
75 static unsigned dx_node_limit (struct inode *dir);
76 -static struct dx_frame *dx_probe(struct dentry *dentry,
77 +static struct dx_frame *dx_probe(struct qstr *name,
79 struct dx_hash_info *hinfo,
80 struct dx_frame *frame,
82 static struct ext3_dir_entry_2 *dx_move_dirents (char *from, char *to,
83 struct dx_map_entry *offsets, int count);
84 static struct ext3_dir_entry_2* dx_pack_dirents (char *base, int size);
85 -static void dx_insert_block (struct dx_frame *frame, u32 hash, u32 block);
86 +static void dx_insert_block (struct inode *, struct dx_frame *, u32, u32, u32);
87 static int ext3_htree_next_block(struct inode *dir, __u32 hash,
88 struct dx_frame *frame,
89 struct dx_frame *frames, int *err,
91 static struct buffer_head * ext3_dx_find_entry(struct dentry *dentry,
92 - struct ext3_dir_entry_2 **res_dir, int *err);
93 + struct ext3_dir_entry_2 **res_dir, int *err,
94 + int rwlock, void **lock);
95 static int ext3_dx_add_entry(handle_t *handle, struct dentry *dentry,
97 +static inline void *ext3_lock_htree(struct inode *, unsigned long, int);
98 +static inline void ext3_unlock_htree(struct inode *, void *);
101 * Future: use high four bits of block for coalesce-on-delete flags
103 #endif /* DX_DEBUG */
108 + * search position of specified hash in index
112 +struct dx_entry * dx_find_position(struct dx_entry * entries, u32 hash)
114 + struct dx_entry *p, *q, *m;
117 + count = dx_get_count(entries);
119 + q = entries + count - 1;
123 + if (dx_get_hash(m) > hash)
132 + * returns 1 if path is unchanged
134 +int dx_check_path(struct dx_frame *frame, u32 hash)
136 + struct dx_entry *p;
139 + dx_lock_bh(frame->bh);
140 + p = dx_find_position(frame->entries, hash);
141 + if (frame->leaf != dx_get_block(p))
143 + dx_unlock_bh(frame->bh);
150 + * 1 - hasn't changed
153 +dx_check_full_path(struct dx_frame *frames, struct dx_hash_info *hinfo)
155 + struct dx_entry *p;
156 + struct dx_frame *frame = frames;
159 + /* check first level */
160 + dx_lock_bh(frame->bh);
161 + p = dx_find_position(frame->entries, hinfo->hash);
162 + leaf = dx_get_block(p);
163 + dx_unlock_bh(frame->bh);
165 + if (leaf != frame->leaf)
168 + /* is there 2nd level? */
170 + if (frame->bh == NULL)
173 + /* check second level */
174 + dx_lock_bh(frame->bh);
176 + /* probably 1st level got changed, check it */
177 + if (!dx_check_path(frames, hinfo->hash)) {
179 + dx_unlock_bh(frame->bh);
183 + p = dx_find_position(frame->entries, hinfo->hash);
184 + leaf = dx_get_block(p);
185 + dx_unlock_bh(frame->bh);
187 + if (leaf != frame->leaf)
194 * Probe for a directory leaf block to search.
196 * dx_probe can return ERR_BAD_DX_DIR, which means there was a format
197 @@ -315,19 +437,20 @@
200 static struct dx_frame *
201 -dx_probe(struct dentry *dentry, struct inode *dir,
202 +dx_probe(struct qstr *name, struct inode *dir,
203 struct dx_hash_info *hinfo, struct dx_frame *frame_in, int *err)
205 - unsigned count, indirect;
206 - struct dx_entry *at, *entries, *p, *q, *m;
208 + struct dx_entry *at, *entries;
209 struct dx_root *root;
210 struct buffer_head *bh;
211 struct dx_frame *frame = frame_in;
213 + unsigned int curidx;
217 - dir = dentry->d_parent->d_inode;
218 + frame[1].bh = NULL;
220 if (!(bh = ext3_bread (NULL,dir, 0, 0, err)))
222 root = (struct dx_root *) bh->b_data;
225 hinfo->hash_version = root->info.hash_version;
226 hinfo->seed = dir->i_sb->u.ext3_sb.s_hash_seed;
228 - ext3fs_dirhash(dentry->d_name.name, dentry->d_name.len, hinfo);
230 + ext3fs_dirhash(name->name, name->len, hinfo);
233 if (root->info.unused_flags & 1) {
240 + entries = (struct dx_entry *) (((char *)&root->info) +
241 + root->info.info_length);
242 + assert(dx_get_limit(entries) == dx_root_limit(dir,
243 + root->info.info_length));
244 + dxtrace (printk("Look up %x", hash));
246 + /* indirect must be initialized under bh lock because
247 + * 2nd level creation procedure may change it and dx_probe()
248 + * will suggest htree is still single-level -bzzz */
249 if ((indirect = root->info.indirect_levels) > 1) {
251 ext3_warning(dir->i_sb, __FUNCTION__,
252 "Unimplemented inode hash depth: %#06x",
253 root->info.indirect_levels);
254 @@ -364,56 +499,46 @@
255 *err = ERR_BAD_DX_DIR;
259 - entries = (struct dx_entry *) (((char *)&root->info) +
260 - root->info.info_length);
261 - assert(dx_get_limit(entries) == dx_root_limit(dir,
262 - root->info.info_length));
263 - dxtrace (printk("Look up %x", hash));
267 - count = dx_get_count(entries);
268 - assert (count && count <= dx_get_limit(entries));
270 - q = entries + count - 1;
274 - dxtrace(printk("."));
275 - if (dx_get_hash(m) > hash)
281 - if (0) // linear search cross check
283 - unsigned n = count - 1;
287 - dxtrace(printk(","));
288 - if (dx_get_hash(++at) > hash)
294 - assert (at == p - 1);
298 - dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
299 + at = dx_find_position(entries, hinfo->hash);
300 + dxtrace(printk(" %x->%u\n",
301 + at == entries? 0: dx_get_hash(at),
302 + dx_get_block(at)));
304 frame->entries = entries;
306 - if (!indirect--) return frame;
307 - if (!(bh = ext3_bread (NULL,dir, dx_get_block(at), 0, err)))
308 + frame->curidx = curidx;
309 + frame->leaf = dx_get_block(at);
315 + /* step into next htree level */
316 + curidx = dx_get_block(at);
318 + if (!(bh = ext3_bread (NULL,dir, frame->leaf, 0, err)))
322 + /* splitting may change root index block and move
323 + * hash we're looking for into another index block
324 + * so, we have to check this situation and repeat
325 + * from begining if path got changed -bzzz */
326 + if (!dx_check_path(frame, hash)) {
333 at = entries = ((struct dx_node *) bh->b_data)->entries;
334 assert (dx_get_limit(entries) == dx_node_limit (dir));
339 while (frame >= frame_in) {
343 if (frames[0].bh == NULL)
346 - if (((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels)
347 + if (frames[1].bh != NULL)
348 brelse(frames[1].bh);
349 brelse(frames[0].bh);
352 * nodes need to be read.
355 - if (++(p->at) < p->entries + dx_get_count(p->entries))
356 + if (++(p->at) < p->entries + dx_get_count(p->entries)) {
357 + p->leaf = dx_get_block(p->at);
363 @@ -497,13 +623,17 @@
364 * block so no check is necessary
366 while (num_frames--) {
367 - if (!(bh = ext3_bread(NULL, dir, dx_get_block(p->at),
371 + idx = p->leaf = dx_get_block(p->at);
372 + if (!(bh = ext3_bread(NULL, dir, idx, 0, err)))
373 return -1; /* Failure */
377 p->at = p->entries = ((struct dx_node *) bh->b_data)->entries;
379 + p->leaf = dx_get_block(p->at);
384 dir = dir_file->f_dentry->d_inode;
385 hinfo.hash = start_hash;
386 hinfo.minor_hash = 0;
387 - frame = dx_probe(0, dir_file->f_dentry->d_inode, &hinfo, frames, &err);
388 + frame = dx_probe(NULL, dir_file->f_dentry->d_inode, &hinfo, frames, &err);
395 /* XXX: do we need to check rec_len == 0 case? -Chris */
396 - de = (struct ext3_dir_entry_2 *) ((char *) de + le16_to_cpu(de->rec_len));
397 + de = (struct ext3_dir_entry_2 *)((char*)de +
398 + le16_to_cpu(de->rec_len));
406 -static void dx_insert_block(struct dx_frame *frame, u32 hash, u32 block)
407 +static void dx_insert_block(struct inode *dir, struct dx_frame *frame,
408 + u32 hash, u32 block, u32 idx)
410 struct dx_entry *entries = frame->entries;
411 struct dx_entry *old = frame->at, *new = old + 1;
413 dx_set_hash(new, hash);
414 dx_set_block(new, block);
415 dx_set_count(entries, count + 1);
423 static struct buffer_head * ext3_find_entry (struct dentry *dentry,
424 - struct ext3_dir_entry_2 ** res_dir)
425 + struct ext3_dir_entry_2 ** res_dir,
426 + int rwlock, void **lock)
428 struct super_block * sb;
429 struct buffer_head * bh_use[NAMEI_RA_SIZE];
434 + int do_not_use_dx = 0;
439 name = dentry->d_name.name;
440 if (namelen > EXT3_NAME_LEN)
443 #ifdef CONFIG_EXT3_INDEX
445 - bh = ext3_dx_find_entry(dentry, res_dir, &err);
446 + bh = ext3_dx_find_entry(dentry, res_dir, &err, rwlock, lock);
448 * On success, or if the error was file not found,
449 * return. Otherwise, fall back to doing a search the
451 if (bh || (err != ERR_BAD_DX_DIR))
453 dxtrace(printk("ext3_find_entry: dx failed, falling back\n"));
457 + *lock = ext3_lock_htree(dir, 0, rwlock);
458 + if (is_dx(dir) && !do_not_use_dx) {
459 + ext3_unlock_htree(dir, *lock);
462 nblocks = dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb);
463 start = EXT3_I(dir)->i_dir_start_lookup;
464 if (start >= nblocks)
465 @@ -859,12 +1001,17 @@
466 /* Clean up the read-ahead blocks */
467 for (; ra_ptr < ra_max; ra_ptr++)
468 brelse (bh_use[ra_ptr]);
470 + ext3_unlock_htree(dir, *lock);
476 #ifdef CONFIG_EXT3_INDEX
477 static struct buffer_head * ext3_dx_find_entry(struct dentry *dentry,
478 - struct ext3_dir_entry_2 **res_dir, int *err)
479 + struct ext3_dir_entry_2 **res_dir, int *err,
480 + int rwlock, void **lock)
482 struct super_block * sb;
483 struct dx_hash_info hinfo;
484 @@ -879,11 +1026,22 @@
485 struct inode *dir = dentry->d_parent->d_inode;
488 - if (!(frame = dx_probe (dentry, 0, &hinfo, frames, err)))
490 + if (!(frame = dx_probe (&dentry->d_name, dir, &hinfo, frames, err)))
493 + *lock = ext3_lock_htree(dir, frame->leaf, rwlock);
494 + /* while locking leaf we just found may get splitted
495 + * so, we need another leaf. check this */
496 + if (!dx_check_full_path(frames, &hinfo)) {
497 + ext3_unlock_htree(dir, *lock);
498 + dx_release(frames);
504 - block = dx_get_block(frame->at);
505 + block = frame->leaf;
506 if (!(bh = ext3_bread (NULL,dir, block, 0, err)))
508 de = (struct ext3_dir_entry_2 *) bh->b_data;
512 dxtrace(printk("%s not found\n", name));
513 + ext3_unlock_htree(dir, *lock);
519 struct inode * inode;
520 struct ext3_dir_entry_2 * de;
521 struct buffer_head * bh;
524 if (dentry->d_name.len > EXT3_NAME_LEN)
525 return ERR_PTR(-ENAMETOOLONG);
526 @@ -934,10 +1095,11 @@
527 if (ext3_check_for_iopen(dir, dentry))
530 - bh = ext3_find_entry(dentry, &de);
531 + bh = ext3_find_entry(dentry, &de, 0, &lock);
534 unsigned long ino = le32_to_cpu(de->inode);
535 + ext3_unlock_htree(dir, lock);
537 inode = iget(dir->i_sb, ino);
540 unsigned rec_len = 0;
543 - struct ext3_dir_entry_2 *de = (struct ext3_dir_entry_2 *) (from + map->offs);
544 + struct ext3_dir_entry_2 *de =
545 + (struct ext3_dir_entry_2 *) (from + map->offs);
546 rec_len = EXT3_DIR_REC_LEN(de->name_len);
547 memcpy (to, de, rec_len);
548 ((struct ext3_dir_entry_2 *) to)->rec_len = rec_len;
551 static struct ext3_dir_entry_2* dx_pack_dirents(char *base, int size)
553 - struct ext3_dir_entry_2 *next, *to, *prev, *de = (struct ext3_dir_entry_2 *) base;
554 + struct ext3_dir_entry_2 *next, *to, *prev;
555 + struct ext3_dir_entry_2 *de = (struct ext3_dir_entry_2 *) base;
556 unsigned rec_len = 0;
559 @@ -1009,7 +1173,8 @@
561 static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
562 struct buffer_head **bh,struct dx_frame *frame,
563 - struct dx_hash_info *hinfo, int *error)
564 + struct dx_hash_info *hinfo, void **target,
567 unsigned blocksize = dir->i_sb->s_blocksize;
568 unsigned count, continued;
569 @@ -1056,23 +1221,30 @@
570 hash2 = map[split].hash;
571 continued = hash2 == map[split - 1].hash;
572 dxtrace(printk("Split block %i at %x, %i/%i\n",
573 - dx_get_block(frame->at), hash2, split, count-split));
575 + frame->leaf, hash2, split, count-split));
577 /* Fancy dance to stay within two buffers */
578 de2 = dx_move_dirents(data1, data2, map + split, count - split);
579 de = dx_pack_dirents(data1,blocksize);
580 de->rec_len = cpu_to_le16(data1 + blocksize - (char *) de);
581 de2->rec_len = cpu_to_le16(data2 + blocksize - (char *) de2);
582 - dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data1, blocksize, 1));
583 - dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data2, blocksize, 1));
584 + dxtrace(dx_show_leaf(hinfo,(struct ext3_dir_entry_2*) data1, blocksize, 1));
585 + dxtrace(dx_show_leaf(hinfo,(struct ext3_dir_entry_2*) data2, blocksize, 1));
587 /* Which block gets the new entry? */
589 if (hinfo->hash >= hash2)
594 - dx_insert_block (frame, hash2 + continued, newblock);
596 + /* entry will be stored into new block
597 + * we have to lock it before add_dirent_to_buf */
598 + *target = ext3_lock_htree(dir, newblock, 1);
600 + dx_lock_bh(frame->bh);
601 + dx_insert_block (dir, frame, hash2 + continued, newblock, frame->curidx);
602 + dx_unlock_bh(frame->bh);
603 err = ext3_journal_dirty_metadata (handle, bh2);
606 @@ -1146,7 +1318,8 @@
607 nlen = EXT3_DIR_REC_LEN(de->name_len);
608 rlen = le16_to_cpu(de->rec_len);
610 - struct ext3_dir_entry_2 *de1 = (struct ext3_dir_entry_2 *)((char *)de + nlen);
611 + struct ext3_dir_entry_2 *de1 =
612 + (struct ext3_dir_entry_2 *)((char *)de + nlen);
613 de1->rec_len = cpu_to_le16(rlen - nlen);
614 de->rec_len = cpu_to_le16(nlen);
616 @@ -1204,7 +1377,8 @@
618 struct dx_hash_info hinfo;
621 + void *lock, *new_lock;
623 blocksize = dir->i_sb->s_blocksize;
624 dxtrace(printk("Creating index\n"));
625 retval = ext3_journal_get_write_access(handle, bh);
626 @@ -1215,7 +1389,6 @@
628 root = (struct dx_root *) bh->b_data;
630 - EXT3_I(dir)->i_flags |= EXT3_INDEX_FL;
631 bh2 = ext3_append (handle, dir, &block, &retval);
634 @@ -1223,6 +1396,8 @@
638 + lock = ext3_lock_htree(dir, block, 1);
640 /* The 0th block becomes the root, move the dirents out */
641 de = (struct ext3_dir_entry_2 *) &root->dotdot;
642 de = (struct ext3_dir_entry_2 *) ((char *)de + de->rec_len);
643 @@ -1252,13 +1427,25 @@
644 frame->entries = entries;
649 + frame[1].bh = NULL;
651 - de = do_split(handle,dir, &bh, frame, &hinfo, &retval);
652 + de = do_split(handle,dir, &bh, frame, &hinfo, &new_lock, &retval);
658 + retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
661 + ext3_unlock_htree(dir, new_lock);
662 + /* we mark directory indexed in order to
663 + * avoid races while htree being created -bzzz */
664 + EXT3_I(dir)->i_flags |= EXT3_INDEX_FL;
665 + ext3_unlock_htree(dir, lock);
667 - return add_dirent_to_buf(handle, dentry, inode, de, bh);
672 @@ -1287,11 +1474,13 @@
679 blocksize = sb->s_blocksize;
680 if (!dentry->d_name.len)
683 #ifdef CONFIG_EXT3_INDEX
685 retval = ext3_dx_add_entry(handle, dentry, inode);
686 @@ -1302,36 +1491,53 @@
687 ext3_mark_inode_dirty(handle, dir);
690 + lock = ext3_lock_htree(dir, 0, 1);
692 + /* we got lock for block 0
693 + * probably previous holder of the lock
694 + * created htree -bzzz */
695 + ext3_unlock_htree(dir, lock);
699 blocks = dir->i_size >> sb->s_blocksize_bits;
700 for (block = 0, offset = 0; block < blocks; block++) {
701 bh = ext3_bread(handle, dir, block, 0, &retval);
704 + ext3_unlock_htree(dir, lock);
707 retval = add_dirent_to_buf(handle, dentry, inode, 0, bh);
708 - if (retval != -ENOSPC)
709 + if (retval != -ENOSPC) {
710 + ext3_unlock_htree(dir, lock);
714 #ifdef CONFIG_EXT3_INDEX
715 if (blocks == 1 && !dx_fallback &&
716 - EXT3_HAS_COMPAT_FEATURE(sb, EXT3_FEATURE_COMPAT_DIR_INDEX))
717 - return make_indexed_dir(handle, dentry, inode, bh);
718 + EXT3_HAS_COMPAT_FEATURE(sb, EXT3_FEATURE_COMPAT_DIR_INDEX)) {
719 + retval = make_indexed_dir(handle, dentry, inode, bh);
720 + ext3_unlock_htree(dir, lock);
726 bh = ext3_append(handle, dir, &block, &retval);
729 + ext3_unlock_htree(dir, lock);
732 de = (struct ext3_dir_entry_2 *) bh->b_data;
734 de->rec_len = cpu_to_le16(rlen = blocksize);
736 - return add_dirent_to_buf(handle, dentry, inode, de, bh);
737 + retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
738 + ext3_unlock_htree(dir, lock);
742 #ifdef CONFIG_EXT3_INDEX
744 - * Returns 0 for success, or a negative error value
746 static int ext3_dx_add_entry(handle_t *handle, struct dentry *dentry,
749 @@ -1343,15 +1549,28 @@
750 struct super_block * sb = dir->i_sb;
751 struct ext3_dir_entry_2 *de;
754 - frame = dx_probe(dentry, 0, &hinfo, frames, &err);
756 + void *idx_lock, *leaf_lock, *newleaf_lock;
759 + frame = dx_probe(&dentry->d_name, dir, &hinfo, frames, &err);
762 - entries = frame->entries;
765 - if (!(bh = ext3_bread(handle,dir, dx_get_block(frame->at), 0, &err)))
766 + /* we're going to chage leaf, so lock it first */
767 + leaf_lock = ext3_lock_htree(dir, frame->leaf, 1);
769 + /* while locking leaf we just found may get splitted
770 + * so we need to check this */
771 + if (!dx_check_full_path(frames, &hinfo)) {
772 + ext3_unlock_htree(dir, leaf_lock);
773 + dx_release(frames);
776 + if (!(bh = ext3_bread(handle,dir, frame->leaf, 0, &err))) {
777 + printk("can't ext3_bread(%d) = %d\n", (int) frame->leaf, err);
781 BUFFER_TRACE(bh, "get_write_access");
782 err = ext3_journal_get_write_access(handle, bh);
783 @@ -1364,6 +1583,35 @@
787 + /* our leaf has no enough space. hence, we have to
788 + * split it. so lock index for this leaf first */
789 + curidx = frame->curidx;
790 + idx_lock = ext3_lock_htree(dir, curidx, 1);
792 + /* now check did path get changed? */
793 + dx_release(frames);
795 + frame = dx_probe(&dentry->d_name, dentry->d_parent->d_inode,
796 + &hinfo, frames, &err);
798 + /* FIXME: error handling here */
800 + ext3_unlock_htree(dir, idx_lock);
804 + if (frame->curidx != curidx) {
805 + /* path has been changed. we have to drop old lock
808 + ext3_unlock_htree(dir, idx_lock);
809 + ext3_unlock_htree(dir, leaf_lock);
810 + dx_release(frames);
813 + entries = frame->entries;
816 /* Block full, should compress but for now just split */
817 dxtrace(printk("using %u of %u node entries\n",
818 dx_get_count(entries), dx_get_limit(entries)));
819 @@ -1375,7 +1623,8 @@
820 struct dx_entry *entries2;
821 struct dx_node *node2;
822 struct buffer_head *bh2;
826 if (levels && (dx_get_count(frames->entries) ==
827 dx_get_limit(frames->entries))) {
828 ext3_warning(sb, __FUNCTION__,
829 @@ -1386,6 +1635,7 @@
830 bh2 = ext3_append (handle, dir, &newblock, &err);
833 + nb_lock = ext3_lock_htree(dir, newblock, 1);
834 node2 = (struct dx_node *)(bh2->b_data);
835 entries2 = node2->entries;
836 node2->fake.rec_len = cpu_to_le16(sb->s_blocksize);
837 @@ -1397,27 +1647,73 @@
839 unsigned icount1 = icount/2, icount2 = icount - icount1;
840 unsigned hash2 = dx_get_hash(entries + icount1);
843 + /* we have to protect root htree index against
844 + * another dx_add_entry() which would want to
845 + * split it too -bzzz */
846 + ri_lock = ext3_lock_htree(dir, 0, 1);
848 + /* as root index block blocked we must repeat
849 + * searching for current position of our 2nd index -bzzz */
850 + dx_lock_bh(frame->bh);
851 + frames->at = dx_find_position(frames->entries, hinfo.hash);
852 + dx_unlock_bh(frame->bh);
854 dxtrace(printk("Split index %i/%i\n", icount1, icount2));
856 - BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
858 + BUFFER_TRACE(frame->bh, "get_write_access");
859 err = ext3_journal_get_write_access(handle,
865 + /* copy index into new one */
866 memcpy ((char *) entries2, (char *) (entries + icount1),
867 icount2 * sizeof(struct dx_entry));
868 - dx_set_count (entries, icount1);
869 dx_set_count (entries2, icount2);
870 dx_set_limit (entries2, dx_node_limit(dir));
872 /* Which index block gets the new entry? */
873 if (at - entries >= icount1) {
874 + /* unlock index we won't use */
875 + ext3_unlock_htree(dir, idx_lock);
876 + idx_lock = nb_lock;
877 frame->at = at = at - entries - icount1 + entries2;
878 - frame->entries = entries = entries2;
879 + frame->entries = entries2;
880 + frame->curidx = curidx = newblock;
881 swap(frame->bh, bh2);
883 + /* we'll use old index,so new one may be freed */
884 + ext3_unlock_htree(dir, nb_lock);
886 - dx_insert_block (frames + 0, hash2, newblock);
888 + /* NOTE: very subtle piece of code
889 + * competing dx_probe() may find 2nd level index in root
890 + * index, then we insert new index here and set new count
891 + * in that 2nd level index. so, dx_probe() may see 2nd
892 + * level index w/o hash it looks for. the solution is
893 + * to check root index after we locked just founded 2nd
894 + * level index -bzzz */
895 + dx_lock_bh(frames[0].bh);
896 + dx_insert_block (dir, frames + 0, hash2, newblock, 0);
897 + dx_unlock_bh(frames[0].bh);
899 + /* now old and new 2nd level index blocks contain
900 + * all pointers, so dx_probe() may find it in the both.
903 + dx_lock_bh(frame->bh);
904 + dx_set_count(entries, icount1);
905 + dx_unlock_bh(frame->bh);
907 + /* now old 2nd level index block points to first half
908 + * of leafs. it's importand that dx_probe() must
909 + * check root index block for changes under
910 + * dx_lock_bh(frame->bh) -bzzz */
912 + ext3_unlock_htree(dir, ri_lock);
914 dxtrace(dx_show_index ("node", frames[1].entries));
915 dxtrace(dx_show_index ("node",
916 ((struct dx_node *) bh2->b_data)->entries));
917 @@ -1426,38 +1722,61 @@
921 + unsigned long leaf = frame->leaf;
923 dxtrace(printk("Creating second level index...\n"));
924 memcpy((char *) entries2, (char *) entries,
925 icount * sizeof(struct dx_entry));
926 dx_set_limit(entries2, dx_node_limit(dir));
929 + dx_lock_bh(frames[0].bh);
930 dx_set_count(entries, 1);
931 dx_set_block(entries + 0, newblock);
932 ((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
933 + dx_unlock_bh(frames[0].bh);
935 /* Add new access path frame */
937 frame->at = at = at - entries + entries2;
938 frame->entries = entries = entries2;
940 + frame->curidx = newblock;
941 + frame->leaf = leaf;
942 err = ext3_journal_get_write_access(handle,
947 + /* first level index was root. it's already initialized */
948 + /* we my unlock it now */
949 + ext3_unlock_htree(dir, idx_lock);
951 + /* current index is just created 2nd level index */
953 + idx_lock = nb_lock;
955 ext3_journal_dirty_metadata(handle, frames[0].bh);
957 - de = do_split(handle, dir, &bh, frame, &hinfo, &err);
958 + de = do_split(handle, dir, &bh, frame, &hinfo, &newleaf_lock, &err);
962 + /* index splitted */
963 + ext3_unlock_htree(dir, idx_lock);
965 err = add_dirent_to_buf(handle, dentry, inode, de, bh);
968 + ext3_unlock_htree(dir, newleaf_lock);
974 ext3_std_error(dir->i_sb, err);
976 + ext3_unlock_htree(dir, leaf_lock);
980 @@ -1901,6 +2220,7 @@
981 struct buffer_head * bh;
982 struct ext3_dir_entry_2 * de;
986 handle = ext3_journal_start(dir, EXT3_DELETE_TRANS_BLOCKS);
987 if (IS_ERR(handle)) {
988 @@ -1908,7 +2228,7 @@
992 - bh = ext3_find_entry (dentry, &de);
993 + bh = ext3_find_entry (dentry, &de, 1, &lock);
997 @@ -1919,14 +2239,19 @@
1001 - if (le32_to_cpu(de->inode) != inode->i_ino)
1002 + if (le32_to_cpu(de->inode) != inode->i_ino) {
1003 + ext3_unlock_htree(dir, lock);
1007 retval = -ENOTEMPTY;
1008 - if (!empty_dir (inode))
1009 + if (!empty_dir (inode)) {
1010 + ext3_unlock_htree(dir, lock);
1014 retval = ext3_delete_entry(handle, dir, de, bh);
1015 + ext3_unlock_htree(dir, lock);
1018 if (inode->i_nlink != 2)
1019 @@ -1985,6 +2310,7 @@
1020 struct buffer_head * bh;
1021 struct ext3_dir_entry_2 * de;
1025 handle = ext3_journal_start(dir, EXT3_DELETE_TRANS_BLOCKS);
1026 if (IS_ERR(handle)) {
1027 @@ -1995,7 +2321,7 @@
1031 - bh = ext3_find_entry (dentry, &de);
1032 + bh = ext3_find_entry (dentry, &de, 1, &lock);
1036 @@ -2003,8 +2329,10 @@
1040 - if (le32_to_cpu(de->inode) != inode->i_ino)
1041 + if (le32_to_cpu(de->inode) != inode->i_ino) {
1042 + ext3_unlock_htree(dir, lock);
1046 if (!inode->i_nlink) {
1047 ext3_warning (inode->i_sb, "ext3_unlink",
1048 @@ -2013,6 +2341,7 @@
1051 retval = ext3_delete_entry(handle, dir, de, bh);
1052 + ext3_unlock_htree(dir, lock);
1055 dir->i_ctime = dir->i_mtime = CURRENT_TIME;
1056 @@ -2151,6 +2480,7 @@
1057 struct buffer_head * old_bh, * new_bh, * dir_bh;
1058 struct ext3_dir_entry_2 * old_de, * new_de;
1060 + void *lock1 = NULL, *lock2 = NULL, *lock3 = NULL;
1062 old_bh = new_bh = dir_bh = NULL;
1064 @@ -2163,7 +2493,10 @@
1065 if (IS_SYNC(old_dir) || IS_SYNC(new_dir))
1068 - old_bh = ext3_find_entry (old_dentry, &old_de);
1069 + if (old_dentry->d_parent == new_dentry->d_parent)
1070 + down(&EXT3_I(old_dentry->d_parent->d_inode)->i_rename_sem);
1072 + old_bh = ext3_find_entry (old_dentry, &old_de, 1, &lock1 /* FIXME */);
1074 * Check for inode number is _not_ due to possible IO errors.
1075 * We might rmdir the source, keep it as pwd of some process
1076 @@ -2176,7 +2509,7 @@
1079 new_inode = new_dentry->d_inode;
1080 - new_bh = ext3_find_entry (new_dentry, &new_de);
1081 + new_bh = ext3_find_entry (new_dentry, &new_de, 1, &lock2 /* FIXME */);
1085 @@ -2239,7 +2572,7 @@
1086 struct buffer_head *old_bh2;
1087 struct ext3_dir_entry_2 *old_de2;
1089 - old_bh2 = ext3_find_entry(old_dentry, &old_de2);
1090 + old_bh2 = ext3_find_entry(old_dentry, &old_de2, 1, &lock3 /* FIXME */);
1092 retval = ext3_delete_entry(handle, old_dir,
1094 @@ -2282,6 +2615,14 @@
1099 + ext3_unlock_htree(old_dentry->d_parent->d_inode, lock1);
1101 + ext3_unlock_htree(new_dentry->d_parent->d_inode, lock2);
1103 + ext3_unlock_htree(old_dentry->d_parent->d_inode, lock3);
1104 + if (old_dentry->d_parent == new_dentry->d_parent)
1105 + up(&EXT3_I(old_dentry->d_parent->d_inode)->i_rename_sem);
1109 @@ -2290,6 +2631,29 @@
1113 + * this locking primitives are used to protect parts
1114 + * of dir's htree. protection unit is block: leaf or index
1116 +static inline void *ext3_lock_htree(struct inode *dir,
1117 + unsigned long value, int rwlock)
1121 + if (!test_opt(dir->i_sb, PDIROPS))
1123 + lock = dynlock_lock(&EXT3_I(dir)->i_htree_lock, value, 1, GFP_KERNEL);
1127 +static inline void ext3_unlock_htree(struct inode *dir,
1130 + if (!test_opt(dir->i_sb, PDIROPS) || !lock)
1132 + dynlock_unlock(&EXT3_I(dir)->i_htree_lock, lock);
1136 * directories can handle most operations...
1138 struct inode_operations ext3_dir_inode_operations = {
1139 Index: linux-2.4.24/fs/ext3/super.c
1140 ===================================================================
1141 --- linux-2.4.24.orig/fs/ext3/super.c 2004-04-01 20:22:17.000000000 +0400
1142 +++ linux-2.4.24/fs/ext3/super.c 2004-04-01 20:24:48.000000000 +0400
1147 + else if (!strcmp (this_char, "pdirops"))
1148 + set_opt (sbi->s_mount_opt, PDIROPS);
1149 else if (!strcmp (this_char, "grpid") ||
1150 !strcmp (this_char, "bsdgroups"))
1151 set_opt (*mount_options, GRPID);
1153 if (want_numeric(value, "sb", sb_block))
1156 + else if (!strcmp (this_char, "pdirops")) {
1157 + set_opt (sbi->s_mount_opt, PDIROPS);
1159 #ifdef CONFIG_JBD_DEBUG
1160 else if (!strcmp (this_char, "ro-after")) {
1162 @@ -891,6 +896,10 @@
1163 ext3_check_inodes_bitmap (sb);
1167 + if (test_opt (sb, PDIROPS))
1168 + sb->s_flags |= S_PDIROPS;
1173 @@ -1393,6 +1402,11 @@
1174 test_opt(sb,DATA_FLAGS) == EXT3_MOUNT_ORDERED_DATA ? "ordered":
1177 + if (test_opt(sb, PDIROPS)) {
1178 + printk (KERN_INFO "EXT3-fs: mounted filesystem with parallel dirops\n");
1179 + sb->s_flags |= S_PDIROPS;
1185 Index: linux-2.4.24/fs/ext3/inode.c
1186 ===================================================================
1187 --- linux-2.4.24.orig/fs/ext3/inode.c 2004-04-01 20:22:18.000000000 +0400
1188 +++ linux-2.4.24/fs/ext3/inode.c 2004-04-01 20:24:48.000000000 +0400
1189 @@ -2239,6 +2239,9 @@
1190 } else if (S_ISDIR(inode->i_mode)) {
1191 inode->i_op = &ext3_dir_inode_operations;
1192 inode->i_fop = &ext3_dir_operations;
1193 + dynlock_init(&EXT3_I(inode)->i_htree_lock);
1194 + sema_init(&EXT3_I(inode)->i_rename_sem, 1);
1195 + sema_init(&EXT3_I(inode)->i_append_sem, 1);
1196 } else if (S_ISLNK(inode->i_mode)) {
1197 if (ext3_inode_is_fast_symlink(inode))
1198 inode->i_op = &ext3_fast_symlink_inode_operations;
1199 Index: linux-2.4.24/fs/ext3/ialloc.c
1200 ===================================================================
1201 --- linux-2.4.24.orig/fs/ext3/ialloc.c 2004-04-01 20:22:17.000000000 +0400
1202 +++ linux-2.4.24/fs/ext3/ialloc.c 2004-04-01 20:24:48.000000000 +0400
1204 return ERR_PTR(-EDQUOT);
1206 ext3_debug ("allocating inode %lu\n", inode->i_ino);
1207 + dynlock_init(&EXT3_I(inode)->i_htree_lock);
1208 + sema_init(&EXT3_I(inode)->i_rename_sem, 1);
1209 + sema_init(&EXT3_I(inode)->i_append_sem, 1);
1213 Index: linux-2.4.24/include/linux/ext3_fs.h
1214 ===================================================================
1215 --- linux-2.4.24.orig/include/linux/ext3_fs.h 2004-04-01 20:22:17.000000000 +0400
1216 +++ linux-2.4.24/include/linux/ext3_fs.h 2004-04-01 20:24:48.000000000 +0400
1221 +#define EXT3_MOUNT_PDIROPS 0x800000/* Parallel dir operations */
1222 #define EXT3_MOUNT_CHECK 0x0001 /* Do mount-time checks */
1223 #define EXT3_MOUNT_GRPID 0x0004 /* Create files with directory's group */
1224 #define EXT3_MOUNT_DEBUG 0x0008 /* Some debugging messages */
1225 Index: linux-2.4.24/include/linux/ext3_fs_i.h
1226 ===================================================================
1227 --- linux-2.4.24.orig/include/linux/ext3_fs_i.h 2004-04-01 20:22:17.000000000 +0400
1228 +++ linux-2.4.24/include/linux/ext3_fs_i.h 2004-04-01 20:24:48.000000000 +0400
1230 #define _LINUX_EXT3_FS_I
1232 #include <linux/rwsem.h>
1233 +#include <linux/dynlocks.h>
1236 * second extended file system inode data in memory
1238 * by other means, so we have truncate_sem.
1240 struct rw_semaphore truncate_sem;
1242 + /* following fields for parallel directory operations -bzzz */
1243 + struct dynlock i_htree_lock;
1244 + struct semaphore i_append_sem;
1245 + struct semaphore i_rename_sem;
1248 #endif /* _LINUX_EXT3_FS_I */