blob: 297ea8dfac7cc8a6a65a8be491b9de8ac5346bce [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * linux/fs/ext3/namei.c
3 *
4 * Copyright (C) 1992, 1993, 1994, 1995
5 * Remy Card (card@masi.ibp.fr)
6 * Laboratoire MASI - Institut Blaise Pascal
7 * Universite Pierre et Marie Curie (Paris VI)
8 *
9 * from
10 *
11 * linux/fs/minix/namei.c
12 *
13 * Copyright (C) 1991, 1992 Linus Torvalds
14 *
15 * Big-endian to little-endian byte-swapping/bitmaps by
16 * David S. Miller (davem@caip.rutgers.edu), 1995
17 * Directory entry file type support and forward compatibility hooks
Dave Kleikampe9ad5622006-09-27 01:49:35 -070018 * for B-tree directories by Theodore Ts'o (tytso@mit.edu), 1998
Linus Torvalds1da177e2005-04-16 15:20:36 -070019 * Hash Tree Directory indexing (c)
Dave Kleikampe9ad5622006-09-27 01:49:35 -070020 * Daniel Phillips, 2001
Linus Torvalds1da177e2005-04-16 15:20:36 -070021 * Hash Tree Directory indexing porting
Dave Kleikampe9ad5622006-09-27 01:49:35 -070022 * Christopher Li, 2002
Linus Torvalds1da177e2005-04-16 15:20:36 -070023 * Hash Tree Directory indexing cleanup
Dave Kleikampe9ad5622006-09-27 01:49:35 -070024 * Theodore Ts'o, 2002
Linus Torvalds1da177e2005-04-16 15:20:36 -070025 */
26
27#include <linux/fs.h>
28#include <linux/pagemap.h>
29#include <linux/jbd.h>
30#include <linux/time.h>
31#include <linux/ext3_fs.h>
32#include <linux/ext3_jbd.h>
33#include <linux/fcntl.h>
34#include <linux/stat.h>
35#include <linux/string.h>
36#include <linux/quotaops.h>
37#include <linux/buffer_head.h>
Jens Axboecaa38fb2006-07-23 01:41:26 +020038#include <linux/bio.h>
Ben Dooks381be252005-10-30 15:02:56 -080039
40#include "namei.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070041#include "xattr.h"
42#include "acl.h"
43
44/*
45 * define how far ahead to read directories while searching them.
46 */
47#define NAMEI_RA_CHUNKS 2
48#define NAMEI_RA_BLOCKS 4
49#define NAMEI_RA_SIZE (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)
50#define NAMEI_RA_INDEX(c,b) (((c) * NAMEI_RA_BLOCKS) + (b))
51
52static struct buffer_head *ext3_append(handle_t *handle,
53 struct inode *inode,
54 u32 *block, int *err)
55{
56 struct buffer_head *bh;
57
58 *block = inode->i_size >> inode->i_sb->s_blocksize_bits;
59
Akinobu Mita33575f82008-04-28 02:16:08 -070060 bh = ext3_bread(handle, inode, *block, 1, err);
61 if (bh) {
Linus Torvalds1da177e2005-04-16 15:20:36 -070062 inode->i_size += inode->i_sb->s_blocksize;
63 EXT3_I(inode)->i_disksize = inode->i_size;
Akinobu Mita33575f82008-04-28 02:16:08 -070064 *err = ext3_journal_get_write_access(handle, bh);
65 if (*err) {
66 brelse(bh);
67 bh = NULL;
68 }
Linus Torvalds1da177e2005-04-16 15:20:36 -070069 }
70 return bh;
71}
72
73#ifndef assert
74#define assert(test) J_ASSERT(test)
75#endif
76
77#ifndef swap
78#define swap(x, y) do { typeof(x) z = x; x = y; y = z; } while (0)
79#endif
80
81#ifdef DX_DEBUG
82#define dxtrace(command) command
83#else
Mingming Caoae6ddcc2006-09-27 01:49:27 -070084#define dxtrace(command)
Linus Torvalds1da177e2005-04-16 15:20:36 -070085#endif
86
87struct fake_dirent
88{
89 __le32 inode;
90 __le16 rec_len;
91 u8 name_len;
92 u8 file_type;
93};
94
95struct dx_countlimit
96{
97 __le16 limit;
98 __le16 count;
99};
100
101struct dx_entry
102{
103 __le32 hash;
104 __le32 block;
105};
106
107/*
108 * dx_root_info is laid out so that if it should somehow get overlaid by a
109 * dirent the two low bits of the hash version will be zero. Therefore, the
110 * hash version mod 4 should never be 0. Sincerely, the paranoia department.
111 */
112
113struct dx_root
114{
115 struct fake_dirent dot;
116 char dot_name[4];
117 struct fake_dirent dotdot;
118 char dotdot_name[4];
119 struct dx_root_info
120 {
121 __le32 reserved_zero;
122 u8 hash_version;
123 u8 info_length; /* 8 */
124 u8 indirect_levels;
125 u8 unused_flags;
126 }
127 info;
128 struct dx_entry entries[0];
129};
130
131struct dx_node
132{
133 struct fake_dirent fake;
134 struct dx_entry entries[0];
135};
136
137
138struct dx_frame
139{
140 struct buffer_head *bh;
141 struct dx_entry *entries;
142 struct dx_entry *at;
143};
144
145struct dx_map_entry
146{
147 u32 hash;
Eric Sandeenef2b02d2007-09-18 22:46:42 -0700148 u16 offs;
149 u16 size;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700150};
151
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152static inline unsigned dx_get_block (struct dx_entry *entry);
153static void dx_set_block (struct dx_entry *entry, unsigned value);
154static inline unsigned dx_get_hash (struct dx_entry *entry);
155static void dx_set_hash (struct dx_entry *entry, unsigned value);
156static unsigned dx_get_count (struct dx_entry *entries);
157static unsigned dx_get_limit (struct dx_entry *entries);
158static void dx_set_count (struct dx_entry *entries, unsigned value);
159static void dx_set_limit (struct dx_entry *entries, unsigned value);
160static unsigned dx_root_limit (struct inode *dir, unsigned infosize);
161static unsigned dx_node_limit (struct inode *dir);
Al Viro734711a2008-08-24 07:26:48 -0400162static struct dx_frame *dx_probe(struct qstr *entry,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163 struct inode *dir,
164 struct dx_hash_info *hinfo,
165 struct dx_frame *frame,
166 int *err);
167static void dx_release (struct dx_frame *frames);
168static int dx_make_map (struct ext3_dir_entry_2 *de, int size,
169 struct dx_hash_info *hinfo, struct dx_map_entry map[]);
170static void dx_sort_map(struct dx_map_entry *map, unsigned count);
171static struct ext3_dir_entry_2 *dx_move_dirents (char *from, char *to,
172 struct dx_map_entry *offsets, int count);
173static struct ext3_dir_entry_2* dx_pack_dirents (char *base, int size);
174static void dx_insert_block (struct dx_frame *frame, u32 hash, u32 block);
175static int ext3_htree_next_block(struct inode *dir, __u32 hash,
176 struct dx_frame *frame,
Mingming Caoae6ddcc2006-09-27 01:49:27 -0700177 struct dx_frame *frames,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700178 __u32 *start_hash);
Al Viro734711a2008-08-24 07:26:48 -0400179static struct buffer_head * ext3_dx_find_entry(struct inode *dir,
180 struct qstr *entry, struct ext3_dir_entry_2 **res_dir,
181 int *err);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700182static int ext3_dx_add_entry(handle_t *handle, struct dentry *dentry,
183 struct inode *inode);
184
185/*
Jan Kara7c06a8d2007-11-14 17:00:19 -0800186 * p is at least 6 bytes before the end of page
187 */
188static inline struct ext3_dir_entry_2 *
189ext3_next_entry(struct ext3_dir_entry_2 *p)
190{
191 return (struct ext3_dir_entry_2 *)((char *)p +
192 ext3_rec_len_from_disk(p->rec_len));
193}
194
195/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196 * Future: use high four bits of block for coalesce-on-delete flags
197 * Mask them off for now.
198 */
199
200static inline unsigned dx_get_block (struct dx_entry *entry)
201{
202 return le32_to_cpu(entry->block) & 0x00ffffff;
203}
204
205static inline void dx_set_block (struct dx_entry *entry, unsigned value)
206{
207 entry->block = cpu_to_le32(value);
208}
209
210static inline unsigned dx_get_hash (struct dx_entry *entry)
211{
212 return le32_to_cpu(entry->hash);
213}
214
215static inline void dx_set_hash (struct dx_entry *entry, unsigned value)
216{
217 entry->hash = cpu_to_le32(value);
218}
219
220static inline unsigned dx_get_count (struct dx_entry *entries)
221{
222 return le16_to_cpu(((struct dx_countlimit *) entries)->count);
223}
224
225static inline unsigned dx_get_limit (struct dx_entry *entries)
226{
227 return le16_to_cpu(((struct dx_countlimit *) entries)->limit);
228}
229
230static inline void dx_set_count (struct dx_entry *entries, unsigned value)
231{
232 ((struct dx_countlimit *) entries)->count = cpu_to_le16(value);
233}
234
235static inline void dx_set_limit (struct dx_entry *entries, unsigned value)
236{
237 ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
238}
239
240static inline unsigned dx_root_limit (struct inode *dir, unsigned infosize)
241{
242 unsigned entry_space = dir->i_sb->s_blocksize - EXT3_DIR_REC_LEN(1) -
243 EXT3_DIR_REC_LEN(2) - infosize;
Li Zefan8ef27202008-07-25 01:46:29 -0700244 return entry_space / sizeof(struct dx_entry);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700245}
246
247static inline unsigned dx_node_limit (struct inode *dir)
248{
249 unsigned entry_space = dir->i_sb->s_blocksize - EXT3_DIR_REC_LEN(0);
Li Zefan8ef27202008-07-25 01:46:29 -0700250 return entry_space / sizeof(struct dx_entry);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700251}
252
253/*
254 * Debug
255 */
256#ifdef DX_DEBUG
257static void dx_show_index (char * label, struct dx_entry *entries)
258{
259 int i, n = dx_get_count (entries);
260 printk("%s index ", label);
261 for (i = 0; i < n; i++)
262 {
263 printk("%x->%u ", i? dx_get_hash(entries + i): 0, dx_get_block(entries + i));
264 }
265 printk("\n");
266}
267
268struct stats
Mingming Caoae6ddcc2006-09-27 01:49:27 -0700269{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700270 unsigned names;
271 unsigned space;
272 unsigned bcount;
273};
274
275static struct stats dx_show_leaf(struct dx_hash_info *hinfo, struct ext3_dir_entry_2 *de,
276 int size, int show_names)
277{
278 unsigned names = 0, space = 0;
279 char *base = (char *) de;
280 struct dx_hash_info h = *hinfo;
281
282 printk("names: ");
283 while ((char *) de < base + size)
284 {
285 if (de->inode)
286 {
287 if (show_names)
288 {
289 int len = de->name_len;
290 char *name = de->name;
291 while (len--) printk("%c", *name++);
292 ext3fs_dirhash(de->name, de->name_len, &h);
293 printk(":%x.%u ", h.hash,
294 ((char *) de - base));
295 }
296 space += EXT3_DIR_REC_LEN(de->name_len);
Dave Kleikampe9ad5622006-09-27 01:49:35 -0700297 names++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700298 }
Jan Kara7c06a8d2007-11-14 17:00:19 -0800299 de = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700300 }
301 printk("(%i)\n", names);
302 return (struct stats) { names, space, 1 };
303}
304
305struct stats dx_show_entries(struct dx_hash_info *hinfo, struct inode *dir,
306 struct dx_entry *entries, int levels)
307{
308 unsigned blocksize = dir->i_sb->s_blocksize;
309 unsigned count = dx_get_count (entries), names = 0, space = 0, i;
310 unsigned bcount = 0;
311 struct buffer_head *bh;
312 int err;
313 printk("%i indexed blocks...\n", count);
314 for (i = 0; i < count; i++, entries++)
315 {
316 u32 block = dx_get_block(entries), hash = i? dx_get_hash(entries): 0;
317 u32 range = i < count - 1? (dx_get_hash(entries + 1) - hash): ~hash;
318 struct stats stats;
319 printk("%s%3u:%03u hash %8x/%8x ",levels?"":" ", i, block, hash, range);
320 if (!(bh = ext3_bread (NULL,dir, block, 0,&err))) continue;
321 stats = levels?
322 dx_show_entries(hinfo, dir, ((struct dx_node *) bh->b_data)->entries, levels - 1):
323 dx_show_leaf(hinfo, (struct ext3_dir_entry_2 *) bh->b_data, blocksize, 0);
324 names += stats.names;
325 space += stats.space;
326 bcount += stats.bcount;
327 brelse (bh);
328 }
329 if (bcount)
330 printk("%snames %u, fullness %u (%u%%)\n", levels?"":" ",
331 names, space/bcount,(space/bcount)*100/blocksize);
332 return (struct stats) { names, space, bcount};
333}
334#endif /* DX_DEBUG */
335
336/*
337 * Probe for a directory leaf block to search.
338 *
339 * dx_probe can return ERR_BAD_DX_DIR, which means there was a format
340 * error in the directory index, and the caller should fall back to
341 * searching the directory normally. The callers of dx_probe **MUST**
342 * check for this error code, and make sure it never gets reflected
343 * back to userspace.
344 */
345static struct dx_frame *
Al Viro734711a2008-08-24 07:26:48 -0400346dx_probe(struct qstr *entry, struct inode *dir,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700347 struct dx_hash_info *hinfo, struct dx_frame *frame_in, int *err)
348{
349 unsigned count, indirect;
350 struct dx_entry *at, *entries, *p, *q, *m;
351 struct dx_root *root;
352 struct buffer_head *bh;
353 struct dx_frame *frame = frame_in;
354 u32 hash;
355
356 frame->bh = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700357 if (!(bh = ext3_bread (NULL,dir, 0, 0, err)))
358 goto fail;
359 root = (struct dx_root *) bh->b_data;
360 if (root->info.hash_version != DX_HASH_TEA &&
361 root->info.hash_version != DX_HASH_HALF_MD4 &&
362 root->info.hash_version != DX_HASH_LEGACY) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700363 ext3_warning(dir->i_sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700364 "Unrecognised inode hash code %d",
365 root->info.hash_version);
366 brelse(bh);
367 *err = ERR_BAD_DX_DIR;
368 goto fail;
369 }
370 hinfo->hash_version = root->info.hash_version;
371 hinfo->seed = EXT3_SB(dir->i_sb)->s_hash_seed;
Al Viro734711a2008-08-24 07:26:48 -0400372 if (entry)
373 ext3fs_dirhash(entry->name, entry->len, hinfo);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700374 hash = hinfo->hash;
375
376 if (root->info.unused_flags & 1) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700377 ext3_warning(dir->i_sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700378 "Unimplemented inode hash flags: %#06x",
379 root->info.unused_flags);
380 brelse(bh);
381 *err = ERR_BAD_DX_DIR;
382 goto fail;
383 }
384
385 if ((indirect = root->info.indirect_levels) > 1) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700386 ext3_warning(dir->i_sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387 "Unimplemented inode hash depth: %#06x",
388 root->info.indirect_levels);
389 brelse(bh);
390 *err = ERR_BAD_DX_DIR;
391 goto fail;
392 }
393
394 entries = (struct dx_entry *) (((char *)&root->info) +
395 root->info.info_length);
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700396
397 if (dx_get_limit(entries) != dx_root_limit(dir,
398 root->info.info_length)) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700399 ext3_warning(dir->i_sb, __func__,
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700400 "dx entry: limit != root limit");
401 brelse(bh);
402 *err = ERR_BAD_DX_DIR;
403 goto fail;
404 }
405
Linus Torvalds1da177e2005-04-16 15:20:36 -0700406 dxtrace (printk("Look up %x", hash));
407 while (1)
408 {
409 count = dx_get_count(entries);
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700410 if (!count || count > dx_get_limit(entries)) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700411 ext3_warning(dir->i_sb, __func__,
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700412 "dx entry: no count or count > limit");
413 brelse(bh);
414 *err = ERR_BAD_DX_DIR;
415 goto fail2;
416 }
417
Linus Torvalds1da177e2005-04-16 15:20:36 -0700418 p = entries + 1;
419 q = entries + count - 1;
420 while (p <= q)
421 {
422 m = p + (q - p)/2;
423 dxtrace(printk("."));
424 if (dx_get_hash(m) > hash)
425 q = m - 1;
426 else
427 p = m + 1;
428 }
429
430 if (0) // linear search cross check
431 {
432 unsigned n = count - 1;
433 at = entries;
434 while (n--)
435 {
436 dxtrace(printk(","));
437 if (dx_get_hash(++at) > hash)
438 {
439 at--;
440 break;
441 }
442 }
443 assert (at == p - 1);
444 }
445
446 at = p - 1;
447 dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
448 frame->bh = bh;
449 frame->entries = entries;
450 frame->at = at;
451 if (!indirect--) return frame;
452 if (!(bh = ext3_bread (NULL,dir, dx_get_block(at), 0, err)))
453 goto fail2;
454 at = entries = ((struct dx_node *) bh->b_data)->entries;
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700455 if (dx_get_limit(entries) != dx_node_limit (dir)) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700456 ext3_warning(dir->i_sb, __func__,
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700457 "dx entry: limit != node limit");
458 brelse(bh);
459 *err = ERR_BAD_DX_DIR;
460 goto fail2;
461 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700462 frame++;
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700463 frame->bh = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464 }
465fail2:
466 while (frame >= frame_in) {
467 brelse(frame->bh);
468 frame--;
469 }
470fail:
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700471 if (*err == ERR_BAD_DX_DIR)
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700472 ext3_warning(dir->i_sb, __func__,
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700473 "Corrupt dir inode %ld, running e2fsck is "
474 "recommended.", dir->i_ino);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700475 return NULL;
476}
477
478static void dx_release (struct dx_frame *frames)
479{
480 if (frames[0].bh == NULL)
481 return;
482
483 if (((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels)
484 brelse(frames[1].bh);
485 brelse(frames[0].bh);
486}
487
488/*
489 * This function increments the frame pointer to search the next leaf
490 * block, and reads in the necessary intervening nodes if the search
491 * should be necessary. Whether or not the search is necessary is
492 * controlled by the hash parameter. If the hash value is even, then
493 * the search is only continued if the next block starts with that
494 * hash value. This is used if we are searching for a specific file.
495 *
496 * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
497 *
498 * This function returns 1 if the caller should continue to search,
499 * or 0 if it should not. If there is an error reading one of the
500 * index blocks, it will a negative error code.
501 *
502 * If start_hash is non-null, it will be filled in with the starting
503 * hash of the next page.
504 */
505static int ext3_htree_next_block(struct inode *dir, __u32 hash,
506 struct dx_frame *frame,
Mingming Caoae6ddcc2006-09-27 01:49:27 -0700507 struct dx_frame *frames,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700508 __u32 *start_hash)
509{
510 struct dx_frame *p;
511 struct buffer_head *bh;
512 int err, num_frames = 0;
513 __u32 bhash;
514
515 p = frame;
516 /*
517 * Find the next leaf page by incrementing the frame pointer.
518 * If we run out of entries in the interior node, loop around and
519 * increment pointer in the parent node. When we break out of
520 * this loop, num_frames indicates the number of interior
521 * nodes need to be read.
522 */
523 while (1) {
524 if (++(p->at) < p->entries + dx_get_count(p->entries))
525 break;
526 if (p == frames)
527 return 0;
528 num_frames++;
529 p--;
530 }
531
532 /*
533 * If the hash is 1, then continue only if the next page has a
534 * continuation hash of any value. This is used for readdir
535 * handling. Otherwise, check to see if the hash matches the
536 * desired contiuation hash. If it doesn't, return since
537 * there's no point to read in the successive index pages.
538 */
539 bhash = dx_get_hash(p->at);
540 if (start_hash)
541 *start_hash = bhash;
542 if ((hash & 1) == 0) {
543 if ((bhash & ~1) != hash)
544 return 0;
545 }
546 /*
547 * If the hash is HASH_NB_ALWAYS, we always go to the next
548 * block so no check is necessary
549 */
550 while (num_frames--) {
551 if (!(bh = ext3_bread(NULL, dir, dx_get_block(p->at),
552 0, &err)))
553 return err; /* Failure */
554 p++;
555 brelse (p->bh);
556 p->bh = bh;
557 p->at = p->entries = ((struct dx_node *) bh->b_data)->entries;
558 }
559 return 1;
560}
561
562
563/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564 * This function fills a red-black tree with information from a
565 * directory block. It returns the number directory entries loaded
566 * into the tree. If there is an error it is returned in err.
567 */
568static int htree_dirblock_to_tree(struct file *dir_file,
569 struct inode *dir, int block,
570 struct dx_hash_info *hinfo,
571 __u32 start_hash, __u32 start_minor_hash)
572{
573 struct buffer_head *bh;
574 struct ext3_dir_entry_2 *de, *top;
575 int err, count = 0;
576
577 dxtrace(printk("In htree dirblock_to_tree: block %d\n", block));
578 if (!(bh = ext3_bread (NULL, dir, block, 0, &err)))
579 return err;
580
581 de = (struct ext3_dir_entry_2 *) bh->b_data;
582 top = (struct ext3_dir_entry_2 *) ((char *) de +
583 dir->i_sb->s_blocksize -
584 EXT3_DIR_REC_LEN(0));
585 for (; de < top; de = ext3_next_entry(de)) {
Eric Sandeen40b85132006-12-06 20:36:26 -0800586 if (!ext3_check_dir_entry("htree_dirblock_to_tree", dir, de, bh,
587 (block<<EXT3_BLOCK_SIZE_BITS(dir->i_sb))
588 +((char *)de - bh->b_data))) {
589 /* On error, skip the f_pos to the next block. */
590 dir_file->f_pos = (dir_file->f_pos |
591 (dir->i_sb->s_blocksize - 1)) + 1;
592 brelse (bh);
593 return count;
594 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700595 ext3fs_dirhash(de->name, de->name_len, hinfo);
596 if ((hinfo->hash < start_hash) ||
597 ((hinfo->hash == start_hash) &&
598 (hinfo->minor_hash < start_minor_hash)))
599 continue;
600 if (de->inode == 0)
601 continue;
602 if ((err = ext3_htree_store_dirent(dir_file,
603 hinfo->hash, hinfo->minor_hash, de)) != 0) {
604 brelse(bh);
605 return err;
606 }
607 count++;
608 }
609 brelse(bh);
610 return count;
611}
612
613
614/*
615 * This function fills a red-black tree with information from a
616 * directory. We start scanning the directory in hash order, starting
617 * at start_hash and start_minor_hash.
618 *
619 * This function returns the number of entries inserted into the tree,
620 * or a negative error code.
621 */
622int ext3_htree_fill_tree(struct file *dir_file, __u32 start_hash,
623 __u32 start_minor_hash, __u32 *next_hash)
624{
625 struct dx_hash_info hinfo;
626 struct ext3_dir_entry_2 *de;
627 struct dx_frame frames[2], *frame;
628 struct inode *dir;
629 int block, err;
630 int count = 0;
631 int ret;
632 __u32 hashval;
633
634 dxtrace(printk("In htree_fill_tree, start hash: %x:%x\n", start_hash,
635 start_minor_hash));
Josef "Jeff" Sipekfe21a692006-12-08 02:36:38 -0800636 dir = dir_file->f_path.dentry->d_inode;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700637 if (!(EXT3_I(dir)->i_flags & EXT3_INDEX_FL)) {
638 hinfo.hash_version = EXT3_SB(dir->i_sb)->s_def_hash_version;
639 hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed;
640 count = htree_dirblock_to_tree(dir_file, dir, 0, &hinfo,
641 start_hash, start_minor_hash);
642 *next_hash = ~0;
643 return count;
644 }
645 hinfo.hash = start_hash;
646 hinfo.minor_hash = 0;
Josef "Jeff" Sipekfe21a692006-12-08 02:36:38 -0800647 frame = dx_probe(NULL, dir_file->f_path.dentry->d_inode, &hinfo, frames, &err);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700648 if (!frame)
649 return err;
650
651 /* Add '.' and '..' from the htree header */
652 if (!start_hash && !start_minor_hash) {
653 de = (struct ext3_dir_entry_2 *) frames[0].bh->b_data;
654 if ((err = ext3_htree_store_dirent(dir_file, 0, 0, de)) != 0)
655 goto errout;
656 count++;
657 }
658 if (start_hash < 2 || (start_hash ==2 && start_minor_hash==0)) {
659 de = (struct ext3_dir_entry_2 *) frames[0].bh->b_data;
660 de = ext3_next_entry(de);
661 if ((err = ext3_htree_store_dirent(dir_file, 2, 0, de)) != 0)
662 goto errout;
663 count++;
664 }
665
666 while (1) {
667 block = dx_get_block(frame->at);
668 ret = htree_dirblock_to_tree(dir_file, dir, block, &hinfo,
669 start_hash, start_minor_hash);
670 if (ret < 0) {
671 err = ret;
672 goto errout;
673 }
674 count += ret;
675 hashval = ~0;
Mingming Caoae6ddcc2006-09-27 01:49:27 -0700676 ret = ext3_htree_next_block(dir, HASH_NB_ALWAYS,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700677 frame, frames, &hashval);
678 *next_hash = hashval;
679 if (ret < 0) {
680 err = ret;
681 goto errout;
682 }
683 /*
684 * Stop if: (a) there are no more entries, or
685 * (b) we have inserted at least one entry and the
686 * next hash value is not a continuation
687 */
688 if ((ret == 0) ||
689 (count && ((hashval & 1) == 0)))
690 break;
691 }
692 dx_release(frames);
Mingming Caoae6ddcc2006-09-27 01:49:27 -0700693 dxtrace(printk("Fill tree: returned %d entries, next hash: %x\n",
Linus Torvalds1da177e2005-04-16 15:20:36 -0700694 count, *next_hash));
695 return count;
696errout:
697 dx_release(frames);
698 return (err);
699}
700
701
702/*
703 * Directory block splitting, compacting
704 */
705
Eric Sandeenef2b02d2007-09-18 22:46:42 -0700706/*
707 * Create map of hash values, offsets, and sizes, stored at end of block.
708 * Returns number of entries mapped.
709 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700710static int dx_make_map (struct ext3_dir_entry_2 *de, int size,
711 struct dx_hash_info *hinfo, struct dx_map_entry *map_tail)
712{
713 int count = 0;
714 char *base = (char *) de;
715 struct dx_hash_info h = *hinfo;
716
717 while ((char *) de < base + size)
718 {
719 if (de->name_len && de->inode) {
720 ext3fs_dirhash(de->name, de->name_len, &h);
721 map_tail--;
722 map_tail->hash = h.hash;
Eric Sandeenef2b02d2007-09-18 22:46:42 -0700723 map_tail->offs = (u16) ((char *) de - base);
724 map_tail->size = le16_to_cpu(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700725 count++;
726 cond_resched();
727 }
728 /* XXX: do we need to check rec_len == 0 case? -Chris */
Jan Kara7c06a8d2007-11-14 17:00:19 -0800729 de = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700730 }
731 return count;
732}
733
Eric Sandeenef2b02d2007-09-18 22:46:42 -0700734/* Sort map by hash value */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700735static void dx_sort_map (struct dx_map_entry *map, unsigned count)
736{
737 struct dx_map_entry *p, *q, *top = map + count - 1;
738 int more;
739 /* Combsort until bubble sort doesn't suck */
740 while (count > 2)
741 {
742 count = count*10/13;
743 if (count - 9 < 2) /* 9, 10 -> 11 */
744 count = 11;
745 for (p = top, q = p - count; q >= map; p--, q--)
746 if (p->hash < q->hash)
747 swap(*p, *q);
748 }
749 /* Garden variety bubble sort */
750 do {
751 more = 0;
752 q = top;
753 while (q-- > map)
754 {
755 if (q[1].hash >= q[0].hash)
756 continue;
757 swap(*(q+1), *q);
758 more = 1;
759 }
760 } while(more);
761}
762
763static void dx_insert_block(struct dx_frame *frame, u32 hash, u32 block)
764{
765 struct dx_entry *entries = frame->entries;
766 struct dx_entry *old = frame->at, *new = old + 1;
767 int count = dx_get_count(entries);
768
769 assert(count < dx_get_limit(entries));
770 assert(old < entries + count);
771 memmove(new + 1, new, (char *)(entries + count) - (char *)(new));
772 dx_set_hash(new, hash);
773 dx_set_block(new, block);
774 dx_set_count(entries, count + 1);
775}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700776
777static void ext3_update_dx_flag(struct inode *inode)
778{
779 if (!EXT3_HAS_COMPAT_FEATURE(inode->i_sb,
780 EXT3_FEATURE_COMPAT_DIR_INDEX))
781 EXT3_I(inode)->i_flags &= ~EXT3_INDEX_FL;
782}
783
784/*
785 * NOTE! unlike strncmp, ext3_match returns 1 for success, 0 for failure.
786 *
787 * `len <= EXT3_NAME_LEN' is guaranteed by caller.
788 * `de != NULL' is guaranteed by caller.
789 */
790static inline int ext3_match (int len, const char * const name,
791 struct ext3_dir_entry_2 * de)
792{
793 if (len != de->name_len)
794 return 0;
795 if (!de->inode)
796 return 0;
797 return !memcmp(name, de->name, len);
798}
799
800/*
801 * Returns 0 if not found, -1 on failure, and 1 on success
802 */
803static inline int search_dirblock(struct buffer_head * bh,
804 struct inode *dir,
Al Viro734711a2008-08-24 07:26:48 -0400805 struct qstr *child,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700806 unsigned long offset,
807 struct ext3_dir_entry_2 ** res_dir)
808{
809 struct ext3_dir_entry_2 * de;
810 char * dlimit;
811 int de_len;
Al Viro734711a2008-08-24 07:26:48 -0400812 const char *name = child->name;
813 int namelen = child->len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700814
815 de = (struct ext3_dir_entry_2 *) bh->b_data;
816 dlimit = bh->b_data + dir->i_sb->s_blocksize;
817 while ((char *) de < dlimit) {
818 /* this code is executed quadratically often */
819 /* do minimal checking `by hand' */
820
821 if ((char *) de + namelen <= dlimit &&
822 ext3_match (namelen, name, de)) {
823 /* found a match - just to be sure, do a full check */
824 if (!ext3_check_dir_entry("ext3_find_entry",
825 dir, de, bh, offset))
826 return -1;
827 *res_dir = de;
828 return 1;
829 }
830 /* prevent looping on a bad block */
Jan Kara7c06a8d2007-11-14 17:00:19 -0800831 de_len = ext3_rec_len_from_disk(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700832 if (de_len <= 0)
833 return -1;
834 offset += de_len;
835 de = (struct ext3_dir_entry_2 *) ((char *) de + de_len);
836 }
837 return 0;
838}
839
840
841/*
842 * ext3_find_entry()
843 *
844 * finds an entry in the specified directory with the wanted name. It
845 * returns the cache buffer in which the entry was found, and the entry
846 * itself (as a parameter - res_dir). It does NOT read the inode of the
847 * entry - you'll have to do that yourself if you want to.
848 *
849 * The returned buffer_head has ->b_count elevated. The caller is expected
850 * to brelse() it when appropriate.
851 */
Al Viro734711a2008-08-24 07:26:48 -0400852static struct buffer_head *ext3_find_entry(struct inode *dir,
853 struct qstr *entry,
854 struct ext3_dir_entry_2 **res_dir)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700855{
856 struct super_block * sb;
857 struct buffer_head * bh_use[NAMEI_RA_SIZE];
858 struct buffer_head * bh, *ret = NULL;
859 unsigned long start, block, b;
860 int ra_max = 0; /* Number of bh's in the readahead
861 buffer, bh_use[] */
862 int ra_ptr = 0; /* Current index into readahead
863 buffer */
864 int num = 0;
865 int nblocks, i, err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700866 int namelen;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867
868 *res_dir = NULL;
869 sb = dir->i_sb;
Al Viro734711a2008-08-24 07:26:48 -0400870 namelen = entry->len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871 if (namelen > EXT3_NAME_LEN)
872 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700873 if (is_dx(dir)) {
Al Viro734711a2008-08-24 07:26:48 -0400874 bh = ext3_dx_find_entry(dir, entry, res_dir, &err);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875 /*
876 * On success, or if the error was file not found,
877 * return. Otherwise, fall back to doing a search the
878 * old fashioned way.
879 */
880 if (bh || (err != ERR_BAD_DX_DIR))
881 return bh;
882 dxtrace(printk("ext3_find_entry: dx failed, falling back\n"));
883 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700884 nblocks = dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb);
885 start = EXT3_I(dir)->i_dir_start_lookup;
886 if (start >= nblocks)
887 start = 0;
888 block = start;
889restart:
890 do {
891 /*
892 * We deal with the read-ahead logic here.
893 */
894 if (ra_ptr >= ra_max) {
895 /* Refill the readahead buffer */
896 ra_ptr = 0;
897 b = block;
898 for (ra_max = 0; ra_max < NAMEI_RA_SIZE; ra_max++) {
899 /*
900 * Terminate if we reach the end of the
901 * directory and must wrap, or if our
902 * search has finished at this block.
903 */
904 if (b >= nblocks || (num && block == start)) {
905 bh_use[ra_max] = NULL;
906 break;
907 }
908 num++;
909 bh = ext3_getblk(NULL, dir, b++, 0, &err);
910 bh_use[ra_max] = bh;
911 if (bh)
Jens Axboecaa38fb2006-07-23 01:41:26 +0200912 ll_rw_block(READ_META, 1, &bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700913 }
914 }
915 if ((bh = bh_use[ra_ptr++]) == NULL)
916 goto next;
917 wait_on_buffer(bh);
918 if (!buffer_uptodate(bh)) {
919 /* read error, skip block & hope for the best */
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700920 ext3_error(sb, __func__, "reading directory #%lu "
Linus Torvalds1da177e2005-04-16 15:20:36 -0700921 "offset %lu", dir->i_ino, block);
922 brelse(bh);
923 goto next;
924 }
Al Viro734711a2008-08-24 07:26:48 -0400925 i = search_dirblock(bh, dir, entry,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700926 block << EXT3_BLOCK_SIZE_BITS(sb), res_dir);
927 if (i == 1) {
928 EXT3_I(dir)->i_dir_start_lookup = block;
929 ret = bh;
930 goto cleanup_and_exit;
931 } else {
932 brelse(bh);
933 if (i < 0)
934 goto cleanup_and_exit;
935 }
936 next:
937 if (++block >= nblocks)
938 block = 0;
939 } while (block != start);
940
941 /*
942 * If the directory has grown while we were searching, then
943 * search the last part of the directory before giving up.
944 */
945 block = nblocks;
946 nblocks = dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb);
947 if (block < nblocks) {
948 start = 0;
949 goto restart;
950 }
951
952cleanup_and_exit:
953 /* Clean up the read-ahead blocks */
954 for (; ra_ptr < ra_max; ra_ptr++)
955 brelse (bh_use[ra_ptr]);
956 return ret;
957}
958
Al Viro734711a2008-08-24 07:26:48 -0400959static struct buffer_head * ext3_dx_find_entry(struct inode *dir,
960 struct qstr *entry, struct ext3_dir_entry_2 **res_dir,
961 int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700962{
963 struct super_block * sb;
964 struct dx_hash_info hinfo;
965 u32 hash;
966 struct dx_frame frames[2], *frame;
967 struct ext3_dir_entry_2 *de, *top;
968 struct buffer_head *bh;
969 unsigned long block;
970 int retval;
Al Viro734711a2008-08-24 07:26:48 -0400971 int namelen = entry->len;
972 const u8 *name = entry->name;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973
974 sb = dir->i_sb;
Andreas Dilgeracfa1823d2005-06-23 00:09:45 -0700975 /* NFS may look up ".." - look at dx_root directory block */
Al Viro734711a2008-08-24 07:26:48 -0400976 if (namelen > 2 || name[0] != '.'|| (namelen == 2 && name[1] != '.')) {
977 if (!(frame = dx_probe(entry, dir, &hinfo, frames, err)))
Andreas Dilgeracfa1823d2005-06-23 00:09:45 -0700978 return NULL;
979 } else {
980 frame = frames;
981 frame->bh = NULL; /* for dx_release() */
982 frame->at = (struct dx_entry *)frames; /* hack for zero entry*/
983 dx_set_block(frame->at, 0); /* dx_root block is 0 */
984 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700985 hash = hinfo.hash;
986 do {
987 block = dx_get_block(frame->at);
988 if (!(bh = ext3_bread (NULL,dir, block, 0, err)))
989 goto errout;
990 de = (struct ext3_dir_entry_2 *) bh->b_data;
991 top = (struct ext3_dir_entry_2 *) ((char *) de + sb->s_blocksize -
992 EXT3_DIR_REC_LEN(0));
Duane Griffin275c0a82008-07-25 01:46:31 -0700993 for (; de < top; de = ext3_next_entry(de)) {
994 int off = (block << EXT3_BLOCK_SIZE_BITS(sb))
995 + ((char *) de - bh->b_data);
996
997 if (!ext3_check_dir_entry(__func__, dir, de, bh, off)) {
998 brelse(bh);
Dmitriy Monakhovfedee542007-05-08 00:25:34 -0700999 *err = ERR_BAD_DX_DIR;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001000 goto errout;
1001 }
Duane Griffin275c0a82008-07-25 01:46:31 -07001002
1003 if (ext3_match(namelen, name, de)) {
1004 *res_dir = de;
1005 dx_release(frames);
1006 return bh;
1007 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001008 }
1009 brelse (bh);
1010 /* Check to see if we should continue to search */
1011 retval = ext3_htree_next_block(dir, hash, frame,
1012 frames, NULL);
1013 if (retval < 0) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001014 ext3_warning(sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001015 "error reading index page in directory #%lu",
1016 dir->i_ino);
1017 *err = retval;
1018 goto errout;
1019 }
1020 } while (retval == 1);
1021
1022 *err = -ENOENT;
1023errout:
1024 dxtrace(printk("%s not found\n", name));
1025 dx_release (frames);
1026 return NULL;
1027}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001028
1029static struct dentry *ext3_lookup(struct inode * dir, struct dentry *dentry, struct nameidata *nd)
1030{
1031 struct inode * inode;
1032 struct ext3_dir_entry_2 * de;
1033 struct buffer_head * bh;
1034
1035 if (dentry->d_name.len > EXT3_NAME_LEN)
1036 return ERR_PTR(-ENAMETOOLONG);
1037
Al Viro734711a2008-08-24 07:26:48 -04001038 bh = ext3_find_entry(dir, &dentry->d_name, &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001039 inode = NULL;
1040 if (bh) {
1041 unsigned long ino = le32_to_cpu(de->inode);
1042 brelse (bh);
Neil Brown2ccb48e2006-07-30 03:03:01 -07001043 if (!ext3_valid_inum(dir->i_sb, ino)) {
1044 ext3_error(dir->i_sb, "ext3_lookup",
1045 "bad inode number: %lu", ino);
David Howells473043d2008-02-07 00:15:36 -08001046 return ERR_PTR(-EIO);
Vasily Averina6c15c22007-07-15 23:40:46 -07001047 }
David Howells473043d2008-02-07 00:15:36 -08001048 inode = ext3_iget(dir->i_sb, ino);
1049 if (IS_ERR(inode))
1050 return ERR_CAST(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001051 }
Pekka Enbergba7fe362006-01-14 13:21:08 -08001052 return d_splice_alias(inode, dentry);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001053}
1054
1055
1056struct dentry *ext3_get_parent(struct dentry *child)
1057{
1058 unsigned long ino;
Al Viro734711a2008-08-24 07:26:48 -04001059 struct qstr dotdot = {.name = "..", .len = 2};
Linus Torvalds1da177e2005-04-16 15:20:36 -07001060 struct ext3_dir_entry_2 * de;
1061 struct buffer_head *bh;
1062
Al Viro734711a2008-08-24 07:26:48 -04001063 bh = ext3_find_entry(child->d_inode, &dotdot, &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001064 if (!bh)
1065 return ERR_PTR(-ENOENT);
1066 ino = le32_to_cpu(de->inode);
1067 brelse(bh);
Neil Brown2ccb48e2006-07-30 03:03:01 -07001068
1069 if (!ext3_valid_inum(child->d_inode->i_sb, ino)) {
1070 ext3_error(child->d_inode->i_sb, "ext3_get_parent",
1071 "bad inode number: %lu", ino);
David Howells473043d2008-02-07 00:15:36 -08001072 return ERR_PTR(-EIO);
Vasily Averina6c15c22007-07-15 23:40:46 -07001073 }
1074
Christoph Hellwig44003722008-08-11 15:49:04 +02001075 return d_obtain_alias(ext3_iget(child->d_inode->i_sb, ino));
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001076}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001077
1078#define S_SHIFT 12
1079static unsigned char ext3_type_by_mode[S_IFMT >> S_SHIFT] = {
1080 [S_IFREG >> S_SHIFT] = EXT3_FT_REG_FILE,
1081 [S_IFDIR >> S_SHIFT] = EXT3_FT_DIR,
1082 [S_IFCHR >> S_SHIFT] = EXT3_FT_CHRDEV,
1083 [S_IFBLK >> S_SHIFT] = EXT3_FT_BLKDEV,
1084 [S_IFIFO >> S_SHIFT] = EXT3_FT_FIFO,
1085 [S_IFSOCK >> S_SHIFT] = EXT3_FT_SOCK,
1086 [S_IFLNK >> S_SHIFT] = EXT3_FT_SYMLINK,
1087};
1088
1089static inline void ext3_set_de_type(struct super_block *sb,
1090 struct ext3_dir_entry_2 *de,
1091 umode_t mode) {
1092 if (EXT3_HAS_INCOMPAT_FEATURE(sb, EXT3_FEATURE_INCOMPAT_FILETYPE))
1093 de->file_type = ext3_type_by_mode[(mode & S_IFMT)>>S_SHIFT];
1094}
1095
Eric Sandeenef2b02d2007-09-18 22:46:42 -07001096/*
1097 * Move count entries from end of map between two memory locations.
1098 * Returns pointer to last entry moved.
1099 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001100static struct ext3_dir_entry_2 *
1101dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count)
1102{
1103 unsigned rec_len = 0;
1104
1105 while (count--) {
1106 struct ext3_dir_entry_2 *de = (struct ext3_dir_entry_2 *) (from + map->offs);
1107 rec_len = EXT3_DIR_REC_LEN(de->name_len);
1108 memcpy (to, de, rec_len);
1109 ((struct ext3_dir_entry_2 *) to)->rec_len =
Jan Kara7c06a8d2007-11-14 17:00:19 -08001110 ext3_rec_len_to_disk(rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001111 de->inode = 0;
1112 map++;
1113 to += rec_len;
1114 }
1115 return (struct ext3_dir_entry_2 *) (to - rec_len);
1116}
1117
Eric Sandeenef2b02d2007-09-18 22:46:42 -07001118/*
1119 * Compact each dir entry in the range to the minimal rec_len.
1120 * Returns pointer to last entry in range.
1121 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001122static struct ext3_dir_entry_2* dx_pack_dirents(char *base, int size)
1123{
1124 struct ext3_dir_entry_2 *next, *to, *prev, *de = (struct ext3_dir_entry_2 *) base;
1125 unsigned rec_len = 0;
1126
1127 prev = to = de;
1128 while ((char*)de < base + size) {
Jan Kara7c06a8d2007-11-14 17:00:19 -08001129 next = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001130 if (de->inode && de->name_len) {
1131 rec_len = EXT3_DIR_REC_LEN(de->name_len);
1132 if (de > to)
1133 memmove(to, de, rec_len);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001134 to->rec_len = ext3_rec_len_to_disk(rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001135 prev = to;
1136 to = (struct ext3_dir_entry_2 *) (((char *) to) + rec_len);
1137 }
1138 de = next;
1139 }
1140 return prev;
1141}
1142
Eric Sandeenef2b02d2007-09-18 22:46:42 -07001143/*
1144 * Split a full leaf block to make room for a new dir entry.
1145 * Allocate a new block, and move entries so that they are approx. equally full.
1146 * Returns pointer to de in block into which the new entry will be inserted.
1147 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001148static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
1149 struct buffer_head **bh,struct dx_frame *frame,
1150 struct dx_hash_info *hinfo, int *error)
1151{
1152 unsigned blocksize = dir->i_sb->s_blocksize;
1153 unsigned count, continued;
1154 struct buffer_head *bh2;
1155 u32 newblock;
1156 u32 hash2;
1157 struct dx_map_entry *map;
1158 char *data1 = (*bh)->b_data, *data2;
Eric Sandeenef2b02d2007-09-18 22:46:42 -07001159 unsigned split, move, size, i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001160 struct ext3_dir_entry_2 *de = NULL, *de2;
Dmitriy Monakhovfedee542007-05-08 00:25:34 -07001161 int err = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001162
Dmitriy Monakhovfedee542007-05-08 00:25:34 -07001163 bh2 = ext3_append (handle, dir, &newblock, &err);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001164 if (!(bh2)) {
1165 brelse(*bh);
1166 *bh = NULL;
1167 goto errout;
1168 }
1169
1170 BUFFER_TRACE(*bh, "get_write_access");
1171 err = ext3_journal_get_write_access(handle, *bh);
Dmitriy Monakhovfedee542007-05-08 00:25:34 -07001172 if (err)
1173 goto journal_error;
1174
Linus Torvalds1da177e2005-04-16 15:20:36 -07001175 BUFFER_TRACE(frame->bh, "get_write_access");
1176 err = ext3_journal_get_write_access(handle, frame->bh);
1177 if (err)
1178 goto journal_error;
1179
1180 data2 = bh2->b_data;
1181
1182 /* create map in the end of data2 block */
1183 map = (struct dx_map_entry *) (data2 + blocksize);
1184 count = dx_make_map ((struct ext3_dir_entry_2 *) data1,
1185 blocksize, hinfo, map);
1186 map -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001187 dx_sort_map (map, count);
Eric Sandeenef2b02d2007-09-18 22:46:42 -07001188 /* Split the existing block in the middle, size-wise */
1189 size = 0;
1190 move = 0;
1191 for (i = count-1; i >= 0; i--) {
1192 /* is more than half of this entry in 2nd half of the block? */
1193 if (size + map[i].size/2 > blocksize/2)
1194 break;
1195 size += map[i].size;
1196 move++;
1197 }
1198 /* map index at which we will split */
1199 split = count - move;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001200 hash2 = map[split].hash;
1201 continued = hash2 == map[split - 1].hash;
1202 dxtrace(printk("Split block %i at %x, %i/%i\n",
1203 dx_get_block(frame->at), hash2, split, count-split));
1204
1205 /* Fancy dance to stay within two buffers */
1206 de2 = dx_move_dirents(data1, data2, map + split, count - split);
1207 de = dx_pack_dirents(data1,blocksize);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001208 de->rec_len = ext3_rec_len_to_disk(data1 + blocksize - (char *) de);
1209 de2->rec_len = ext3_rec_len_to_disk(data2 + blocksize - (char *) de2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001210 dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data1, blocksize, 1));
1211 dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data2, blocksize, 1));
1212
1213 /* Which block gets the new entry? */
1214 if (hinfo->hash >= hash2)
1215 {
1216 swap(*bh, bh2);
1217 de = de2;
1218 }
1219 dx_insert_block (frame, hash2 + continued, newblock);
1220 err = ext3_journal_dirty_metadata (handle, bh2);
1221 if (err)
1222 goto journal_error;
1223 err = ext3_journal_dirty_metadata (handle, frame->bh);
1224 if (err)
1225 goto journal_error;
1226 brelse (bh2);
1227 dxtrace(dx_show_index ("frame", frame->entries));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001228 return de;
Dmitriy Monakhovfedee542007-05-08 00:25:34 -07001229
1230journal_error:
1231 brelse(*bh);
1232 brelse(bh2);
1233 *bh = NULL;
1234 ext3_std_error(dir->i_sb, err);
1235errout:
1236 *error = err;
1237 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001238}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001239
1240
1241/*
1242 * Add a new entry into a directory (leaf) block. If de is non-NULL,
1243 * it points to a directory entry which is guaranteed to be large
1244 * enough for new directory entry. If de is NULL, then
1245 * add_dirent_to_buf will attempt search the directory block for
1246 * space. It will return -ENOSPC if no space is available, and -EIO
1247 * and -EEXIST if directory entry already exists.
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001248 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07001249 * NOTE! bh is NOT released in the case where ENOSPC is returned. In
1250 * all other cases bh is released.
1251 */
1252static int add_dirent_to_buf(handle_t *handle, struct dentry *dentry,
1253 struct inode *inode, struct ext3_dir_entry_2 *de,
1254 struct buffer_head * bh)
1255{
1256 struct inode *dir = dentry->d_parent->d_inode;
1257 const char *name = dentry->d_name.name;
1258 int namelen = dentry->d_name.len;
1259 unsigned long offset = 0;
1260 unsigned short reclen;
1261 int nlen, rlen, err;
1262 char *top;
1263
1264 reclen = EXT3_DIR_REC_LEN(namelen);
1265 if (!de) {
1266 de = (struct ext3_dir_entry_2 *)bh->b_data;
1267 top = bh->b_data + dir->i_sb->s_blocksize - reclen;
1268 while ((char *) de <= top) {
1269 if (!ext3_check_dir_entry("ext3_add_entry", dir, de,
1270 bh, offset)) {
1271 brelse (bh);
1272 return -EIO;
1273 }
1274 if (ext3_match (namelen, name, de)) {
1275 brelse (bh);
1276 return -EEXIST;
1277 }
1278 nlen = EXT3_DIR_REC_LEN(de->name_len);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001279 rlen = ext3_rec_len_from_disk(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001280 if ((de->inode? rlen - nlen: rlen) >= reclen)
1281 break;
1282 de = (struct ext3_dir_entry_2 *)((char *)de + rlen);
1283 offset += rlen;
1284 }
1285 if ((char *) de > top)
1286 return -ENOSPC;
1287 }
1288 BUFFER_TRACE(bh, "get_write_access");
1289 err = ext3_journal_get_write_access(handle, bh);
1290 if (err) {
1291 ext3_std_error(dir->i_sb, err);
1292 brelse(bh);
1293 return err;
1294 }
1295
1296 /* By now the buffer is marked for journaling */
1297 nlen = EXT3_DIR_REC_LEN(de->name_len);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001298 rlen = ext3_rec_len_from_disk(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299 if (de->inode) {
1300 struct ext3_dir_entry_2 *de1 = (struct ext3_dir_entry_2 *)((char *)de + nlen);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001301 de1->rec_len = ext3_rec_len_to_disk(rlen - nlen);
1302 de->rec_len = ext3_rec_len_to_disk(nlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001303 de = de1;
1304 }
1305 de->file_type = EXT3_FT_UNKNOWN;
1306 if (inode) {
1307 de->inode = cpu_to_le32(inode->i_ino);
1308 ext3_set_de_type(dir->i_sb, de, inode->i_mode);
1309 } else
1310 de->inode = 0;
1311 de->name_len = namelen;
1312 memcpy (de->name, name, namelen);
1313 /*
1314 * XXX shouldn't update any times until successful
1315 * completion of syscall, but too many callers depend
1316 * on this.
1317 *
1318 * XXX similarly, too many callers depend on
1319 * ext3_new_inode() setting the times, but error
1320 * recovery deletes the inode, so the worst that can
1321 * happen is that the times are slightly out of date
1322 * and/or different from the directory change time.
1323 */
1324 dir->i_mtime = dir->i_ctime = CURRENT_TIME_SEC;
1325 ext3_update_dx_flag(dir);
1326 dir->i_version++;
1327 ext3_mark_inode_dirty(handle, dir);
1328 BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata");
1329 err = ext3_journal_dirty_metadata(handle, bh);
1330 if (err)
1331 ext3_std_error(dir->i_sb, err);
1332 brelse(bh);
1333 return 0;
1334}
1335
Linus Torvalds1da177e2005-04-16 15:20:36 -07001336/*
1337 * This converts a one block unindexed directory to a 3 block indexed
1338 * directory, and adds the dentry to the indexed directory.
1339 */
1340static int make_indexed_dir(handle_t *handle, struct dentry *dentry,
1341 struct inode *inode, struct buffer_head *bh)
1342{
1343 struct inode *dir = dentry->d_parent->d_inode;
1344 const char *name = dentry->d_name.name;
1345 int namelen = dentry->d_name.len;
1346 struct buffer_head *bh2;
1347 struct dx_root *root;
1348 struct dx_frame frames[2], *frame;
1349 struct dx_entry *entries;
1350 struct ext3_dir_entry_2 *de, *de2;
1351 char *data1, *top;
1352 unsigned len;
1353 int retval;
1354 unsigned blocksize;
1355 struct dx_hash_info hinfo;
1356 u32 block;
1357 struct fake_dirent *fde;
1358
1359 blocksize = dir->i_sb->s_blocksize;
1360 dxtrace(printk("Creating index\n"));
1361 retval = ext3_journal_get_write_access(handle, bh);
1362 if (retval) {
1363 ext3_std_error(dir->i_sb, retval);
1364 brelse(bh);
1365 return retval;
1366 }
1367 root = (struct dx_root *) bh->b_data;
1368
1369 bh2 = ext3_append (handle, dir, &block, &retval);
1370 if (!(bh2)) {
1371 brelse(bh);
1372 return retval;
1373 }
1374 EXT3_I(dir)->i_flags |= EXT3_INDEX_FL;
1375 data1 = bh2->b_data;
1376
1377 /* The 0th block becomes the root, move the dirents out */
1378 fde = &root->dotdot;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001379 de = (struct ext3_dir_entry_2 *)((char *)fde +
1380 ext3_rec_len_from_disk(fde->rec_len));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001381 len = ((char *) root) + blocksize - (char *) de;
1382 memcpy (data1, de, len);
1383 de = (struct ext3_dir_entry_2 *) data1;
1384 top = data1 + len;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001385 while ((char *)(de2 = ext3_next_entry(de)) < top)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386 de = de2;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001387 de->rec_len = ext3_rec_len_to_disk(data1 + blocksize - (char *) de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001388 /* Initialize the root; the dot dirents already exist */
1389 de = (struct ext3_dir_entry_2 *) (&root->dotdot);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001390 de->rec_len = ext3_rec_len_to_disk(blocksize - EXT3_DIR_REC_LEN(2));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391 memset (&root->info, 0, sizeof(root->info));
1392 root->info.info_length = sizeof(root->info);
1393 root->info.hash_version = EXT3_SB(dir->i_sb)->s_def_hash_version;
1394 entries = root->entries;
1395 dx_set_block (entries, 1);
1396 dx_set_count (entries, 1);
1397 dx_set_limit (entries, dx_root_limit(dir, sizeof(root->info)));
1398
1399 /* Initialize as for dx_probe */
1400 hinfo.hash_version = root->info.hash_version;
1401 hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed;
1402 ext3fs_dirhash(name, namelen, &hinfo);
1403 frame = frames;
1404 frame->entries = entries;
1405 frame->at = entries;
1406 frame->bh = bh;
1407 bh = bh2;
1408 de = do_split(handle,dir, &bh, frame, &hinfo, &retval);
1409 dx_release (frames);
1410 if (!(de))
1411 return retval;
1412
1413 return add_dirent_to_buf(handle, dentry, inode, de, bh);
1414}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001415
1416/*
1417 * ext3_add_entry()
1418 *
1419 * adds a file entry to the specified directory, using the same
1420 * semantics as ext3_find_entry(). It returns NULL if it failed.
1421 *
1422 * NOTE!! The inode part of 'de' is left at 0 - which means you
1423 * may not sleep between calling this and putting something into
1424 * the entry, as someone else might have used it while you slept.
1425 */
1426static int ext3_add_entry (handle_t *handle, struct dentry *dentry,
1427 struct inode *inode)
1428{
1429 struct inode *dir = dentry->d_parent->d_inode;
1430 unsigned long offset;
1431 struct buffer_head * bh;
1432 struct ext3_dir_entry_2 *de;
1433 struct super_block * sb;
1434 int retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001435 int dx_fallback=0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001436 unsigned blocksize;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001437 u32 block, blocks;
1438
1439 sb = dir->i_sb;
1440 blocksize = sb->s_blocksize;
1441 if (!dentry->d_name.len)
1442 return -EINVAL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001443 if (is_dx(dir)) {
1444 retval = ext3_dx_add_entry(handle, dentry, inode);
1445 if (!retval || (retval != ERR_BAD_DX_DIR))
1446 return retval;
1447 EXT3_I(dir)->i_flags &= ~EXT3_INDEX_FL;
1448 dx_fallback++;
1449 ext3_mark_inode_dirty(handle, dir);
1450 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001451 blocks = dir->i_size >> sb->s_blocksize_bits;
1452 for (block = 0, offset = 0; block < blocks; block++) {
1453 bh = ext3_bread(handle, dir, block, 0, &retval);
1454 if(!bh)
1455 return retval;
1456 retval = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1457 if (retval != -ENOSPC)
1458 return retval;
1459
Linus Torvalds1da177e2005-04-16 15:20:36 -07001460 if (blocks == 1 && !dx_fallback &&
1461 EXT3_HAS_COMPAT_FEATURE(sb, EXT3_FEATURE_COMPAT_DIR_INDEX))
1462 return make_indexed_dir(handle, dentry, inode, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001463 brelse(bh);
1464 }
1465 bh = ext3_append(handle, dir, &block, &retval);
1466 if (!bh)
1467 return retval;
1468 de = (struct ext3_dir_entry_2 *) bh->b_data;
1469 de->inode = 0;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001470 de->rec_len = ext3_rec_len_to_disk(blocksize);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001471 return add_dirent_to_buf(handle, dentry, inode, de, bh);
1472}
1473
Linus Torvalds1da177e2005-04-16 15:20:36 -07001474/*
1475 * Returns 0 for success, or a negative error value
1476 */
1477static int ext3_dx_add_entry(handle_t *handle, struct dentry *dentry,
1478 struct inode *inode)
1479{
1480 struct dx_frame frames[2], *frame;
1481 struct dx_entry *entries, *at;
1482 struct dx_hash_info hinfo;
1483 struct buffer_head * bh;
1484 struct inode *dir = dentry->d_parent->d_inode;
1485 struct super_block * sb = dir->i_sb;
1486 struct ext3_dir_entry_2 *de;
1487 int err;
1488
Al Viro734711a2008-08-24 07:26:48 -04001489 frame = dx_probe(&dentry->d_name, dir, &hinfo, frames, &err);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001490 if (!frame)
1491 return err;
1492 entries = frame->entries;
1493 at = frame->at;
1494
1495 if (!(bh = ext3_bread(handle,dir, dx_get_block(frame->at), 0, &err)))
1496 goto cleanup;
1497
1498 BUFFER_TRACE(bh, "get_write_access");
1499 err = ext3_journal_get_write_access(handle, bh);
1500 if (err)
1501 goto journal_error;
1502
1503 err = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1504 if (err != -ENOSPC) {
1505 bh = NULL;
1506 goto cleanup;
1507 }
1508
1509 /* Block full, should compress but for now just split */
1510 dxtrace(printk("using %u of %u node entries\n",
1511 dx_get_count(entries), dx_get_limit(entries)));
1512 /* Need to split index? */
1513 if (dx_get_count(entries) == dx_get_limit(entries)) {
1514 u32 newblock;
1515 unsigned icount = dx_get_count(entries);
1516 int levels = frame - frames;
1517 struct dx_entry *entries2;
1518 struct dx_node *node2;
1519 struct buffer_head *bh2;
1520
1521 if (levels && (dx_get_count(frames->entries) ==
1522 dx_get_limit(frames->entries))) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001523 ext3_warning(sb, __func__,
Glauber de Oliveira Costa9f406682006-01-08 01:03:22 -08001524 "Directory index full!");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001525 err = -ENOSPC;
1526 goto cleanup;
1527 }
1528 bh2 = ext3_append (handle, dir, &newblock, &err);
1529 if (!(bh2))
1530 goto cleanup;
1531 node2 = (struct dx_node *)(bh2->b_data);
1532 entries2 = node2->entries;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001533 node2->fake.rec_len = ext3_rec_len_to_disk(sb->s_blocksize);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001534 node2->fake.inode = 0;
1535 BUFFER_TRACE(frame->bh, "get_write_access");
1536 err = ext3_journal_get_write_access(handle, frame->bh);
1537 if (err)
1538 goto journal_error;
1539 if (levels) {
1540 unsigned icount1 = icount/2, icount2 = icount - icount1;
1541 unsigned hash2 = dx_get_hash(entries + icount1);
1542 dxtrace(printk("Split index %i/%i\n", icount1, icount2));
1543
1544 BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
1545 err = ext3_journal_get_write_access(handle,
1546 frames[0].bh);
1547 if (err)
1548 goto journal_error;
1549
1550 memcpy ((char *) entries2, (char *) (entries + icount1),
1551 icount2 * sizeof(struct dx_entry));
1552 dx_set_count (entries, icount1);
1553 dx_set_count (entries2, icount2);
1554 dx_set_limit (entries2, dx_node_limit(dir));
1555
1556 /* Which index block gets the new entry? */
1557 if (at - entries >= icount1) {
1558 frame->at = at = at - entries - icount1 + entries2;
1559 frame->entries = entries = entries2;
1560 swap(frame->bh, bh2);
1561 }
1562 dx_insert_block (frames + 0, hash2, newblock);
1563 dxtrace(dx_show_index ("node", frames[1].entries));
1564 dxtrace(dx_show_index ("node",
1565 ((struct dx_node *) bh2->b_data)->entries));
1566 err = ext3_journal_dirty_metadata(handle, bh2);
1567 if (err)
1568 goto journal_error;
1569 brelse (bh2);
1570 } else {
1571 dxtrace(printk("Creating second level index...\n"));
1572 memcpy((char *) entries2, (char *) entries,
1573 icount * sizeof(struct dx_entry));
1574 dx_set_limit(entries2, dx_node_limit(dir));
1575
1576 /* Set up root */
1577 dx_set_count(entries, 1);
1578 dx_set_block(entries + 0, newblock);
1579 ((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
1580
1581 /* Add new access path frame */
1582 frame = frames + 1;
1583 frame->at = at = at - entries + entries2;
1584 frame->entries = entries = entries2;
1585 frame->bh = bh2;
1586 err = ext3_journal_get_write_access(handle,
1587 frame->bh);
1588 if (err)
1589 goto journal_error;
1590 }
1591 ext3_journal_dirty_metadata(handle, frames[0].bh);
1592 }
1593 de = do_split(handle, dir, &bh, frame, &hinfo, &err);
1594 if (!de)
1595 goto cleanup;
1596 err = add_dirent_to_buf(handle, dentry, inode, de, bh);
1597 bh = NULL;
1598 goto cleanup;
1599
1600journal_error:
1601 ext3_std_error(dir->i_sb, err);
1602cleanup:
1603 if (bh)
1604 brelse(bh);
1605 dx_release(frames);
1606 return err;
1607}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001608
1609/*
1610 * ext3_delete_entry deletes a directory entry by merging it with the
1611 * previous entry
1612 */
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001613static int ext3_delete_entry (handle_t *handle,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001614 struct inode * dir,
1615 struct ext3_dir_entry_2 * de_del,
1616 struct buffer_head * bh)
1617{
1618 struct ext3_dir_entry_2 * de, * pde;
1619 int i;
1620
1621 i = 0;
1622 pde = NULL;
1623 de = (struct ext3_dir_entry_2 *) bh->b_data;
1624 while (i < bh->b_size) {
1625 if (!ext3_check_dir_entry("ext3_delete_entry", dir, de, bh, i))
1626 return -EIO;
1627 if (de == de_del) {
1628 BUFFER_TRACE(bh, "get_write_access");
1629 ext3_journal_get_write_access(handle, bh);
1630 if (pde)
Jan Kara7c06a8d2007-11-14 17:00:19 -08001631 pde->rec_len = ext3_rec_len_to_disk(
1632 ext3_rec_len_from_disk(pde->rec_len) +
1633 ext3_rec_len_from_disk(de->rec_len));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001634 else
1635 de->inode = 0;
1636 dir->i_version++;
1637 BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata");
1638 ext3_journal_dirty_metadata(handle, bh);
1639 return 0;
1640 }
Jan Kara7c06a8d2007-11-14 17:00:19 -08001641 i += ext3_rec_len_from_disk(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001642 pde = de;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001643 de = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001644 }
1645 return -ENOENT;
1646}
1647
Linus Torvalds1da177e2005-04-16 15:20:36 -07001648static int ext3_add_nondir(handle_t *handle,
1649 struct dentry *dentry, struct inode *inode)
1650{
1651 int err = ext3_add_entry(handle, dentry, inode);
1652 if (!err) {
1653 ext3_mark_inode_dirty(handle, inode);
1654 d_instantiate(dentry, inode);
Al Viroc38012d2008-12-30 02:02:50 -05001655 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001656 return 0;
1657 }
Eric Sandeen731b9a52007-02-10 01:46:16 -08001658 drop_nlink(inode);
Al Viroc38012d2008-12-30 02:02:50 -05001659 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001660 iput(inode);
1661 return err;
1662}
1663
1664/*
1665 * By the time this is called, we already have created
1666 * the directory cache entry for the new file, but it
1667 * is so far negative - it has no inode.
1668 *
1669 * If the create succeeds, we fill in the inode information
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001670 * with d_instantiate().
Linus Torvalds1da177e2005-04-16 15:20:36 -07001671 */
1672static int ext3_create (struct inode * dir, struct dentry * dentry, int mode,
1673 struct nameidata *nd)
1674{
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001675 handle_t *handle;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001676 struct inode * inode;
1677 int err, retries = 0;
1678
1679retry:
Jan Kara1f545872005-06-23 22:01:04 -07001680 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Linus Torvalds1da177e2005-04-16 15:20:36 -07001681 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3 +
Jan Kara1f545872005-06-23 22:01:04 -07001682 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001683 if (IS_ERR(handle))
1684 return PTR_ERR(handle);
1685
1686 if (IS_DIRSYNC(dir))
1687 handle->h_sync = 1;
1688
1689 inode = ext3_new_inode (handle, dir, mode);
1690 err = PTR_ERR(inode);
1691 if (!IS_ERR(inode)) {
1692 inode->i_op = &ext3_file_inode_operations;
1693 inode->i_fop = &ext3_file_operations;
1694 ext3_set_aops(inode);
1695 err = ext3_add_nondir(handle, dentry, inode);
1696 }
1697 ext3_journal_stop(handle);
1698 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
1699 goto retry;
1700 return err;
1701}
1702
1703static int ext3_mknod (struct inode * dir, struct dentry *dentry,
1704 int mode, dev_t rdev)
1705{
1706 handle_t *handle;
1707 struct inode *inode;
1708 int err, retries = 0;
1709
1710 if (!new_valid_dev(rdev))
1711 return -EINVAL;
1712
1713retry:
Jan Kara1f545872005-06-23 22:01:04 -07001714 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Dave Kleikampe9ad5622006-09-27 01:49:35 -07001715 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3 +
Jan Kara1f545872005-06-23 22:01:04 -07001716 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001717 if (IS_ERR(handle))
1718 return PTR_ERR(handle);
1719
1720 if (IS_DIRSYNC(dir))
1721 handle->h_sync = 1;
1722
1723 inode = ext3_new_inode (handle, dir, mode);
1724 err = PTR_ERR(inode);
1725 if (!IS_ERR(inode)) {
1726 init_special_inode(inode, inode->i_mode, rdev);
1727#ifdef CONFIG_EXT3_FS_XATTR
1728 inode->i_op = &ext3_special_inode_operations;
1729#endif
1730 err = ext3_add_nondir(handle, dentry, inode);
1731 }
1732 ext3_journal_stop(handle);
1733 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
1734 goto retry;
1735 return err;
1736}
1737
1738static int ext3_mkdir(struct inode * dir, struct dentry * dentry, int mode)
1739{
1740 handle_t *handle;
1741 struct inode * inode;
1742 struct buffer_head * dir_block;
1743 struct ext3_dir_entry_2 * de;
1744 int err, retries = 0;
1745
1746 if (dir->i_nlink >= EXT3_LINK_MAX)
1747 return -EMLINK;
1748
1749retry:
Jan Kara1f545872005-06-23 22:01:04 -07001750 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Linus Torvalds1da177e2005-04-16 15:20:36 -07001751 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3 +
Jan Kara1f545872005-06-23 22:01:04 -07001752 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001753 if (IS_ERR(handle))
1754 return PTR_ERR(handle);
1755
1756 if (IS_DIRSYNC(dir))
1757 handle->h_sync = 1;
1758
1759 inode = ext3_new_inode (handle, dir, S_IFDIR | mode);
1760 err = PTR_ERR(inode);
1761 if (IS_ERR(inode))
1762 goto out_stop;
1763
1764 inode->i_op = &ext3_dir_inode_operations;
1765 inode->i_fop = &ext3_dir_operations;
1766 inode->i_size = EXT3_I(inode)->i_disksize = inode->i_sb->s_blocksize;
1767 dir_block = ext3_bread (handle, inode, 0, 1, &err);
1768 if (!dir_block) {
Dave Hansen9a53c3a2006-09-30 23:29:03 -07001769 drop_nlink(inode); /* is this nlink == 0? */
Al Viroc38012d2008-12-30 02:02:50 -05001770 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001771 ext3_mark_inode_dirty(handle, inode);
1772 iput (inode);
1773 goto out_stop;
1774 }
1775 BUFFER_TRACE(dir_block, "get_write_access");
1776 ext3_journal_get_write_access(handle, dir_block);
1777 de = (struct ext3_dir_entry_2 *) dir_block->b_data;
1778 de->inode = cpu_to_le32(inode->i_ino);
1779 de->name_len = 1;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001780 de->rec_len = ext3_rec_len_to_disk(EXT3_DIR_REC_LEN(de->name_len));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001781 strcpy (de->name, ".");
1782 ext3_set_de_type(dir->i_sb, de, S_IFDIR);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001783 de = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001784 de->inode = cpu_to_le32(dir->i_ino);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001785 de->rec_len = ext3_rec_len_to_disk(inode->i_sb->s_blocksize -
1786 EXT3_DIR_REC_LEN(1));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001787 de->name_len = 2;
1788 strcpy (de->name, "..");
1789 ext3_set_de_type(dir->i_sb, de, S_IFDIR);
1790 inode->i_nlink = 2;
1791 BUFFER_TRACE(dir_block, "call ext3_journal_dirty_metadata");
1792 ext3_journal_dirty_metadata(handle, dir_block);
1793 brelse (dir_block);
1794 ext3_mark_inode_dirty(handle, inode);
1795 err = ext3_add_entry (handle, dentry, inode);
1796 if (err) {
1797 inode->i_nlink = 0;
Al Viroc38012d2008-12-30 02:02:50 -05001798 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001799 ext3_mark_inode_dirty(handle, inode);
1800 iput (inode);
1801 goto out_stop;
1802 }
Dave Hansend8c76e62006-09-30 23:29:04 -07001803 inc_nlink(dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001804 ext3_update_dx_flag(dir);
1805 ext3_mark_inode_dirty(handle, dir);
1806 d_instantiate(dentry, inode);
Al Viroc38012d2008-12-30 02:02:50 -05001807 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001808out_stop:
1809 ext3_journal_stop(handle);
1810 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
1811 goto retry;
1812 return err;
1813}
1814
1815/*
1816 * routine to check that the specified directory is empty (for rmdir)
1817 */
1818static int empty_dir (struct inode * inode)
1819{
1820 unsigned long offset;
1821 struct buffer_head * bh;
1822 struct ext3_dir_entry_2 * de, * de1;
1823 struct super_block * sb;
1824 int err = 0;
1825
1826 sb = inode->i_sb;
1827 if (inode->i_size < EXT3_DIR_REC_LEN(1) + EXT3_DIR_REC_LEN(2) ||
1828 !(bh = ext3_bread (NULL, inode, 0, 0, &err))) {
1829 if (err)
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001830 ext3_error(inode->i_sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001831 "error %d reading directory #%lu offset 0",
1832 err, inode->i_ino);
1833 else
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001834 ext3_warning(inode->i_sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001835 "bad directory (dir #%lu) - no data block",
1836 inode->i_ino);
1837 return 1;
1838 }
1839 de = (struct ext3_dir_entry_2 *) bh->b_data;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001840 de1 = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001841 if (le32_to_cpu(de->inode) != inode->i_ino ||
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001842 !le32_to_cpu(de1->inode) ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001843 strcmp (".", de->name) ||
1844 strcmp ("..", de1->name)) {
Dave Kleikampe9ad5622006-09-27 01:49:35 -07001845 ext3_warning (inode->i_sb, "empty_dir",
Linus Torvalds1da177e2005-04-16 15:20:36 -07001846 "bad directory (dir #%lu) - no `.' or `..'",
1847 inode->i_ino);
1848 brelse (bh);
1849 return 1;
1850 }
Jan Kara7c06a8d2007-11-14 17:00:19 -08001851 offset = ext3_rec_len_from_disk(de->rec_len) +
1852 ext3_rec_len_from_disk(de1->rec_len);
1853 de = ext3_next_entry(de1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001854 while (offset < inode->i_size ) {
1855 if (!bh ||
1856 (void *) de >= (void *) (bh->b_data+sb->s_blocksize)) {
1857 err = 0;
1858 brelse (bh);
1859 bh = ext3_bread (NULL, inode,
1860 offset >> EXT3_BLOCK_SIZE_BITS(sb), 0, &err);
1861 if (!bh) {
1862 if (err)
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001863 ext3_error(sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001864 "error %d reading directory"
1865 " #%lu offset %lu",
1866 err, inode->i_ino, offset);
1867 offset += sb->s_blocksize;
1868 continue;
1869 }
1870 de = (struct ext3_dir_entry_2 *) bh->b_data;
1871 }
1872 if (!ext3_check_dir_entry("empty_dir", inode, de, bh, offset)) {
1873 de = (struct ext3_dir_entry_2 *)(bh->b_data +
1874 sb->s_blocksize);
1875 offset = (offset | (sb->s_blocksize - 1)) + 1;
1876 continue;
1877 }
1878 if (le32_to_cpu(de->inode)) {
1879 brelse (bh);
1880 return 0;
1881 }
Jan Kara7c06a8d2007-11-14 17:00:19 -08001882 offset += ext3_rec_len_from_disk(de->rec_len);
1883 de = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001884 }
1885 brelse (bh);
1886 return 1;
1887}
1888
1889/* ext3_orphan_add() links an unlinked or truncated inode into a list of
1890 * such inodes, starting at the superblock, in case we crash before the
1891 * file is closed/deleted, or in case the inode truncate spans multiple
1892 * transactions and the last transaction is not recovered after a crash.
1893 *
1894 * At filesystem recovery time, we walk this list deleting unlinked
1895 * inodes and truncating linked inodes in ext3_orphan_cleanup().
1896 */
1897int ext3_orphan_add(handle_t *handle, struct inode *inode)
1898{
1899 struct super_block *sb = inode->i_sb;
1900 struct ext3_iloc iloc;
1901 int err = 0, rc;
1902
1903 lock_super(sb);
1904 if (!list_empty(&EXT3_I(inode)->i_orphan))
1905 goto out_unlock;
1906
1907 /* Orphan handling is only valid for files with data blocks
1908 * being truncated, or files being unlinked. */
1909
1910 /* @@@ FIXME: Observation from aviro:
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001911 * I think I can trigger J_ASSERT in ext3_orphan_add(). We block
Linus Torvalds1da177e2005-04-16 15:20:36 -07001912 * here (on lock_super()), so race with ext3_link() which might bump
1913 * ->i_nlink. For, say it, character device. Not a regular file,
1914 * not a directory, not a symlink and ->i_nlink > 0.
1915 */
1916 J_ASSERT ((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
1917 S_ISLNK(inode->i_mode)) || inode->i_nlink == 0);
1918
1919 BUFFER_TRACE(EXT3_SB(sb)->s_sbh, "get_write_access");
1920 err = ext3_journal_get_write_access(handle, EXT3_SB(sb)->s_sbh);
1921 if (err)
1922 goto out_unlock;
1923
1924 err = ext3_reserve_inode_write(handle, inode, &iloc);
1925 if (err)
1926 goto out_unlock;
1927
1928 /* Insert this inode at the head of the on-disk orphan list... */
1929 NEXT_ORPHAN(inode) = le32_to_cpu(EXT3_SB(sb)->s_es->s_last_orphan);
1930 EXT3_SB(sb)->s_es->s_last_orphan = cpu_to_le32(inode->i_ino);
1931 err = ext3_journal_dirty_metadata(handle, EXT3_SB(sb)->s_sbh);
1932 rc = ext3_mark_iloc_dirty(handle, inode, &iloc);
1933 if (!err)
1934 err = rc;
1935
1936 /* Only add to the head of the in-memory list if all the
1937 * previous operations succeeded. If the orphan_add is going to
1938 * fail (possibly taking the journal offline), we can't risk
1939 * leaving the inode on the orphan list: stray orphan-list
1940 * entries can cause panics at unmount time.
1941 *
1942 * This is safe: on error we're going to ignore the orphan list
1943 * anyway on the next recovery. */
1944 if (!err)
1945 list_add(&EXT3_I(inode)->i_orphan, &EXT3_SB(sb)->s_orphan);
1946
Eric Sandeeneee194e2006-09-27 01:49:30 -07001947 jbd_debug(4, "superblock will point to %lu\n", inode->i_ino);
1948 jbd_debug(4, "orphan inode %lu will point to %d\n",
Linus Torvalds1da177e2005-04-16 15:20:36 -07001949 inode->i_ino, NEXT_ORPHAN(inode));
1950out_unlock:
1951 unlock_super(sb);
1952 ext3_std_error(inode->i_sb, err);
1953 return err;
1954}
1955
1956/*
1957 * ext3_orphan_del() removes an unlinked or truncated inode from the list
1958 * of such inodes stored on disk, because it is finally being cleaned up.
1959 */
1960int ext3_orphan_del(handle_t *handle, struct inode *inode)
1961{
1962 struct list_head *prev;
1963 struct ext3_inode_info *ei = EXT3_I(inode);
1964 struct ext3_sb_info *sbi;
1965 unsigned long ino_next;
1966 struct ext3_iloc iloc;
1967 int err = 0;
1968
1969 lock_super(inode->i_sb);
1970 if (list_empty(&ei->i_orphan)) {
1971 unlock_super(inode->i_sb);
1972 return 0;
1973 }
1974
1975 ino_next = NEXT_ORPHAN(inode);
1976 prev = ei->i_orphan.prev;
1977 sbi = EXT3_SB(inode->i_sb);
1978
1979 jbd_debug(4, "remove inode %lu from orphan list\n", inode->i_ino);
1980
1981 list_del_init(&ei->i_orphan);
1982
1983 /* If we're on an error path, we may not have a valid
1984 * transaction handle with which to update the orphan list on
1985 * disk, but we still need to remove the inode from the linked
1986 * list in memory. */
1987 if (!handle)
1988 goto out;
1989
1990 err = ext3_reserve_inode_write(handle, inode, &iloc);
1991 if (err)
1992 goto out_err;
1993
1994 if (prev == &sbi->s_orphan) {
1995 jbd_debug(4, "superblock will point to %lu\n", ino_next);
1996 BUFFER_TRACE(sbi->s_sbh, "get_write_access");
1997 err = ext3_journal_get_write_access(handle, sbi->s_sbh);
1998 if (err)
1999 goto out_brelse;
2000 sbi->s_es->s_last_orphan = cpu_to_le32(ino_next);
2001 err = ext3_journal_dirty_metadata(handle, sbi->s_sbh);
2002 } else {
2003 struct ext3_iloc iloc2;
2004 struct inode *i_prev =
2005 &list_entry(prev, struct ext3_inode_info, i_orphan)->vfs_inode;
2006
2007 jbd_debug(4, "orphan inode %lu will point to %lu\n",
2008 i_prev->i_ino, ino_next);
2009 err = ext3_reserve_inode_write(handle, i_prev, &iloc2);
2010 if (err)
2011 goto out_brelse;
2012 NEXT_ORPHAN(i_prev) = ino_next;
2013 err = ext3_mark_iloc_dirty(handle, i_prev, &iloc2);
2014 }
2015 if (err)
2016 goto out_brelse;
2017 NEXT_ORPHAN(inode) = 0;
2018 err = ext3_mark_iloc_dirty(handle, inode, &iloc);
2019
2020out_err:
2021 ext3_std_error(inode->i_sb, err);
2022out:
2023 unlock_super(inode->i_sb);
2024 return err;
2025
2026out_brelse:
2027 brelse(iloc.bh);
2028 goto out_err;
2029}
2030
2031static int ext3_rmdir (struct inode * dir, struct dentry *dentry)
2032{
2033 int retval;
2034 struct inode * inode;
2035 struct buffer_head * bh;
2036 struct ext3_dir_entry_2 * de;
2037 handle_t *handle;
2038
2039 /* Initialize quotas before so that eventual writes go in
2040 * separate transaction */
2041 DQUOT_INIT(dentry->d_inode);
Jan Kara1f545872005-06-23 22:01:04 -07002042 handle = ext3_journal_start(dir, EXT3_DELETE_TRANS_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002043 if (IS_ERR(handle))
2044 return PTR_ERR(handle);
2045
2046 retval = -ENOENT;
Al Viro734711a2008-08-24 07:26:48 -04002047 bh = ext3_find_entry(dir, &dentry->d_name, &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002048 if (!bh)
2049 goto end_rmdir;
2050
2051 if (IS_DIRSYNC(dir))
2052 handle->h_sync = 1;
2053
2054 inode = dentry->d_inode;
2055
2056 retval = -EIO;
2057 if (le32_to_cpu(de->inode) != inode->i_ino)
2058 goto end_rmdir;
2059
2060 retval = -ENOTEMPTY;
2061 if (!empty_dir (inode))
2062 goto end_rmdir;
2063
2064 retval = ext3_delete_entry(handle, dir, de, bh);
2065 if (retval)
2066 goto end_rmdir;
2067 if (inode->i_nlink != 2)
2068 ext3_warning (inode->i_sb, "ext3_rmdir",
2069 "empty directory has nlink!=2 (%d)",
2070 inode->i_nlink);
2071 inode->i_version++;
Dave Hansence71ec32006-09-30 23:29:06 -07002072 clear_nlink(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002073 /* There's no need to set i_disksize: the fact that i_nlink is
2074 * zero will ensure that the right thing happens during any
2075 * recovery. */
2076 inode->i_size = 0;
2077 ext3_orphan_add(handle, inode);
2078 inode->i_ctime = dir->i_ctime = dir->i_mtime = CURRENT_TIME_SEC;
2079 ext3_mark_inode_dirty(handle, inode);
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002080 drop_nlink(dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002081 ext3_update_dx_flag(dir);
2082 ext3_mark_inode_dirty(handle, dir);
2083
2084end_rmdir:
2085 ext3_journal_stop(handle);
2086 brelse (bh);
2087 return retval;
2088}
2089
2090static int ext3_unlink(struct inode * dir, struct dentry *dentry)
2091{
2092 int retval;
2093 struct inode * inode;
2094 struct buffer_head * bh;
2095 struct ext3_dir_entry_2 * de;
2096 handle_t *handle;
2097
2098 /* Initialize quotas before so that eventual writes go
2099 * in separate transaction */
2100 DQUOT_INIT(dentry->d_inode);
Jan Kara1f545872005-06-23 22:01:04 -07002101 handle = ext3_journal_start(dir, EXT3_DELETE_TRANS_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002102 if (IS_ERR(handle))
2103 return PTR_ERR(handle);
2104
2105 if (IS_DIRSYNC(dir))
2106 handle->h_sync = 1;
2107
2108 retval = -ENOENT;
Al Viro734711a2008-08-24 07:26:48 -04002109 bh = ext3_find_entry(dir, &dentry->d_name, &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002110 if (!bh)
2111 goto end_unlink;
2112
2113 inode = dentry->d_inode;
2114
2115 retval = -EIO;
2116 if (le32_to_cpu(de->inode) != inode->i_ino)
2117 goto end_unlink;
2118
2119 if (!inode->i_nlink) {
2120 ext3_warning (inode->i_sb, "ext3_unlink",
2121 "Deleting nonexistent file (%lu), %d",
2122 inode->i_ino, inode->i_nlink);
2123 inode->i_nlink = 1;
2124 }
2125 retval = ext3_delete_entry(handle, dir, de, bh);
2126 if (retval)
2127 goto end_unlink;
2128 dir->i_ctime = dir->i_mtime = CURRENT_TIME_SEC;
2129 ext3_update_dx_flag(dir);
2130 ext3_mark_inode_dirty(handle, dir);
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002131 drop_nlink(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002132 if (!inode->i_nlink)
2133 ext3_orphan_add(handle, inode);
2134 inode->i_ctime = dir->i_ctime;
2135 ext3_mark_inode_dirty(handle, inode);
2136 retval = 0;
2137
2138end_unlink:
2139 ext3_journal_stop(handle);
2140 brelse (bh);
2141 return retval;
2142}
2143
2144static int ext3_symlink (struct inode * dir,
2145 struct dentry *dentry, const char * symname)
2146{
2147 handle_t *handle;
2148 struct inode * inode;
2149 int l, err, retries = 0;
2150
2151 l = strlen(symname)+1;
2152 if (l > dir->i_sb->s_blocksize)
2153 return -ENAMETOOLONG;
2154
2155retry:
Jan Kara1f545872005-06-23 22:01:04 -07002156 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Dave Kleikampe9ad5622006-09-27 01:49:35 -07002157 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 5 +
Jan Kara1f545872005-06-23 22:01:04 -07002158 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002159 if (IS_ERR(handle))
2160 return PTR_ERR(handle);
2161
2162 if (IS_DIRSYNC(dir))
2163 handle->h_sync = 1;
2164
2165 inode = ext3_new_inode (handle, dir, S_IFLNK|S_IRWXUGO);
2166 err = PTR_ERR(inode);
2167 if (IS_ERR(inode))
2168 goto out_stop;
2169
2170 if (l > sizeof (EXT3_I(inode)->i_data)) {
2171 inode->i_op = &ext3_symlink_inode_operations;
2172 ext3_set_aops(inode);
2173 /*
2174 * page_symlink() calls into ext3_prepare/commit_write.
2175 * We have a transaction open. All is sweetness. It also sets
2176 * i_size in generic_commit_write().
2177 */
Kirill Korotaev0adb25d2006-03-11 03:27:13 -08002178 err = __page_symlink(inode, symname, l,
2179 mapping_gfp_mask(inode->i_mapping) & ~__GFP_FS);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002180 if (err) {
Eric Sandeen731b9a52007-02-10 01:46:16 -08002181 drop_nlink(inode);
Al Viroc38012d2008-12-30 02:02:50 -05002182 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002183 ext3_mark_inode_dirty(handle, inode);
2184 iput (inode);
2185 goto out_stop;
2186 }
2187 } else {
2188 inode->i_op = &ext3_fast_symlink_inode_operations;
2189 memcpy((char*)&EXT3_I(inode)->i_data,symname,l);
2190 inode->i_size = l-1;
2191 }
2192 EXT3_I(inode)->i_disksize = inode->i_size;
2193 err = ext3_add_nondir(handle, dentry, inode);
2194out_stop:
2195 ext3_journal_stop(handle);
2196 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
2197 goto retry;
2198 return err;
2199}
2200
2201static int ext3_link (struct dentry * old_dentry,
2202 struct inode * dir, struct dentry *dentry)
2203{
2204 handle_t *handle;
2205 struct inode *inode = old_dentry->d_inode;
2206 int err, retries = 0;
2207
2208 if (inode->i_nlink >= EXT3_LINK_MAX)
2209 return -EMLINK;
Eric Sandeen2988a772007-02-10 01:46:16 -08002210 /*
2211 * Return -ENOENT if we've raced with unlink and i_nlink is 0. Doing
2212 * otherwise has the potential to corrupt the orphan inode list.
2213 */
2214 if (inode->i_nlink == 0)
2215 return -ENOENT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002216
2217retry:
Jan Kara1f545872005-06-23 22:01:04 -07002218 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Linus Torvalds1da177e2005-04-16 15:20:36 -07002219 EXT3_INDEX_EXTRA_TRANS_BLOCKS);
2220 if (IS_ERR(handle))
2221 return PTR_ERR(handle);
2222
2223 if (IS_DIRSYNC(dir))
2224 handle->h_sync = 1;
2225
2226 inode->i_ctime = CURRENT_TIME_SEC;
Eric Sandeen731b9a52007-02-10 01:46:16 -08002227 inc_nlink(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002228 atomic_inc(&inode->i_count);
2229
Al Viroc38012d2008-12-30 02:02:50 -05002230 err = ext3_add_entry(handle, dentry, inode);
2231 if (!err) {
2232 ext3_mark_inode_dirty(handle, inode);
2233 d_instantiate(dentry, inode);
2234 } else {
2235 drop_nlink(inode);
2236 iput(inode);
2237 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002238 ext3_journal_stop(handle);
2239 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
2240 goto retry;
2241 return err;
2242}
2243
2244#define PARENT_INO(buffer) \
Jan Kara7c06a8d2007-11-14 17:00:19 -08002245 (ext3_next_entry((struct ext3_dir_entry_2 *)(buffer))->inode)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002246
2247/*
2248 * Anybody can rename anything with this: the permission checks are left to the
2249 * higher-level routines.
2250 */
2251static int ext3_rename (struct inode * old_dir, struct dentry *old_dentry,
2252 struct inode * new_dir,struct dentry *new_dentry)
2253{
2254 handle_t *handle;
2255 struct inode * old_inode, * new_inode;
2256 struct buffer_head * old_bh, * new_bh, * dir_bh;
2257 struct ext3_dir_entry_2 * old_de, * new_de;
2258 int retval;
2259
2260 old_bh = new_bh = dir_bh = NULL;
2261
2262 /* Initialize quotas before so that eventual writes go
2263 * in separate transaction */
2264 if (new_dentry->d_inode)
2265 DQUOT_INIT(new_dentry->d_inode);
Jan Kara1f545872005-06-23 22:01:04 -07002266 handle = ext3_journal_start(old_dir, 2 *
2267 EXT3_DATA_TRANS_BLOCKS(old_dir->i_sb) +
Dave Kleikampe9ad5622006-09-27 01:49:35 -07002268 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002269 if (IS_ERR(handle))
2270 return PTR_ERR(handle);
2271
2272 if (IS_DIRSYNC(old_dir) || IS_DIRSYNC(new_dir))
2273 handle->h_sync = 1;
2274
Al Viro734711a2008-08-24 07:26:48 -04002275 old_bh = ext3_find_entry(old_dir, &old_dentry->d_name, &old_de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002276 /*
2277 * Check for inode number is _not_ due to possible IO errors.
2278 * We might rmdir the source, keep it as pwd of some process
2279 * and merrily kill the link to whatever was created under the
2280 * same name. Goodbye sticky bit ;-<
2281 */
2282 old_inode = old_dentry->d_inode;
2283 retval = -ENOENT;
2284 if (!old_bh || le32_to_cpu(old_de->inode) != old_inode->i_ino)
2285 goto end_rename;
2286
2287 new_inode = new_dentry->d_inode;
Al Viro734711a2008-08-24 07:26:48 -04002288 new_bh = ext3_find_entry(new_dir, &new_dentry->d_name, &new_de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002289 if (new_bh) {
2290 if (!new_inode) {
2291 brelse (new_bh);
2292 new_bh = NULL;
2293 }
2294 }
2295 if (S_ISDIR(old_inode->i_mode)) {
2296 if (new_inode) {
2297 retval = -ENOTEMPTY;
2298 if (!empty_dir (new_inode))
2299 goto end_rename;
2300 }
2301 retval = -EIO;
2302 dir_bh = ext3_bread (handle, old_inode, 0, 0, &retval);
2303 if (!dir_bh)
2304 goto end_rename;
2305 if (le32_to_cpu(PARENT_INO(dir_bh->b_data)) != old_dir->i_ino)
2306 goto end_rename;
2307 retval = -EMLINK;
2308 if (!new_inode && new_dir!=old_dir &&
2309 new_dir->i_nlink >= EXT3_LINK_MAX)
2310 goto end_rename;
2311 }
2312 if (!new_bh) {
2313 retval = ext3_add_entry (handle, new_dentry, old_inode);
2314 if (retval)
2315 goto end_rename;
2316 } else {
2317 BUFFER_TRACE(new_bh, "get write access");
2318 ext3_journal_get_write_access(handle, new_bh);
2319 new_de->inode = cpu_to_le32(old_inode->i_ino);
2320 if (EXT3_HAS_INCOMPAT_FEATURE(new_dir->i_sb,
2321 EXT3_FEATURE_INCOMPAT_FILETYPE))
2322 new_de->file_type = old_de->file_type;
2323 new_dir->i_version++;
Jan Kara0b230762008-04-28 02:16:12 -07002324 new_dir->i_ctime = new_dir->i_mtime = CURRENT_TIME_SEC;
2325 ext3_mark_inode_dirty(handle, new_dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002326 BUFFER_TRACE(new_bh, "call ext3_journal_dirty_metadata");
2327 ext3_journal_dirty_metadata(handle, new_bh);
2328 brelse(new_bh);
2329 new_bh = NULL;
2330 }
2331
2332 /*
2333 * Like most other Unix systems, set the ctime for inodes on a
2334 * rename.
2335 */
2336 old_inode->i_ctime = CURRENT_TIME_SEC;
2337 ext3_mark_inode_dirty(handle, old_inode);
2338
2339 /*
2340 * ok, that's it
2341 */
2342 if (le32_to_cpu(old_de->inode) != old_inode->i_ino ||
2343 old_de->name_len != old_dentry->d_name.len ||
2344 strncmp(old_de->name, old_dentry->d_name.name, old_de->name_len) ||
2345 (retval = ext3_delete_entry(handle, old_dir,
2346 old_de, old_bh)) == -ENOENT) {
2347 /* old_de could have moved from under us during htree split, so
2348 * make sure that we are deleting the right entry. We might
2349 * also be pointing to a stale entry in the unused part of
2350 * old_bh so just checking inum and the name isn't enough. */
2351 struct buffer_head *old_bh2;
2352 struct ext3_dir_entry_2 *old_de2;
2353
Al Viro734711a2008-08-24 07:26:48 -04002354 old_bh2 = ext3_find_entry(old_dir, &old_dentry->d_name,
2355 &old_de2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002356 if (old_bh2) {
2357 retval = ext3_delete_entry(handle, old_dir,
2358 old_de2, old_bh2);
2359 brelse(old_bh2);
2360 }
2361 }
2362 if (retval) {
2363 ext3_warning(old_dir->i_sb, "ext3_rename",
2364 "Deleting old file (%lu), %d, error=%d",
2365 old_dir->i_ino, old_dir->i_nlink, retval);
2366 }
2367
2368 if (new_inode) {
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002369 drop_nlink(new_inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002370 new_inode->i_ctime = CURRENT_TIME_SEC;
2371 }
2372 old_dir->i_ctime = old_dir->i_mtime = CURRENT_TIME_SEC;
2373 ext3_update_dx_flag(old_dir);
2374 if (dir_bh) {
2375 BUFFER_TRACE(dir_bh, "get_write_access");
2376 ext3_journal_get_write_access(handle, dir_bh);
2377 PARENT_INO(dir_bh->b_data) = cpu_to_le32(new_dir->i_ino);
2378 BUFFER_TRACE(dir_bh, "call ext3_journal_dirty_metadata");
2379 ext3_journal_dirty_metadata(handle, dir_bh);
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002380 drop_nlink(old_dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002381 if (new_inode) {
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002382 drop_nlink(new_inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002383 } else {
Dave Hansend8c76e62006-09-30 23:29:04 -07002384 inc_nlink(new_dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002385 ext3_update_dx_flag(new_dir);
2386 ext3_mark_inode_dirty(handle, new_dir);
2387 }
2388 }
2389 ext3_mark_inode_dirty(handle, old_dir);
2390 if (new_inode) {
2391 ext3_mark_inode_dirty(handle, new_inode);
2392 if (!new_inode->i_nlink)
2393 ext3_orphan_add(handle, new_inode);
2394 }
2395 retval = 0;
2396
2397end_rename:
2398 brelse (dir_bh);
2399 brelse (old_bh);
2400 brelse (new_bh);
2401 ext3_journal_stop(handle);
2402 return retval;
2403}
2404
2405/*
2406 * directories can handle most operations...
2407 */
Arjan van de Ven754661f2007-02-12 00:55:38 -08002408const struct inode_operations ext3_dir_inode_operations = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002409 .create = ext3_create,
2410 .lookup = ext3_lookup,
2411 .link = ext3_link,
2412 .unlink = ext3_unlink,
2413 .symlink = ext3_symlink,
2414 .mkdir = ext3_mkdir,
2415 .rmdir = ext3_rmdir,
2416 .mknod = ext3_mknod,
2417 .rename = ext3_rename,
2418 .setattr = ext3_setattr,
2419#ifdef CONFIG_EXT3_FS_XATTR
2420 .setxattr = generic_setxattr,
2421 .getxattr = generic_getxattr,
2422 .listxattr = ext3_listxattr,
2423 .removexattr = generic_removexattr,
2424#endif
2425 .permission = ext3_permission,
2426};
2427
Arjan van de Ven754661f2007-02-12 00:55:38 -08002428const struct inode_operations ext3_special_inode_operations = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002429 .setattr = ext3_setattr,
2430#ifdef CONFIG_EXT3_FS_XATTR
2431 .setxattr = generic_setxattr,
2432 .getxattr = generic_getxattr,
2433 .listxattr = ext3_listxattr,
2434 .removexattr = generic_removexattr,
2435#endif
2436 .permission = ext3_permission,
Mingming Caoae6ddcc2006-09-27 01:49:27 -07002437};