blob: 2c2d700c1ccfcb112d7df6ee9303b2cfc1716116 [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;
Theodore Ts'o5e1f8c92008-10-28 13:21:55 -0400371 if (hinfo->hash_version <= DX_HASH_TEA)
372 hinfo->hash_version += EXT3_SB(dir->i_sb)->s_hash_unsigned;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700373 hinfo->seed = EXT3_SB(dir->i_sb)->s_hash_seed;
Al Viro734711a2008-08-24 07:26:48 -0400374 if (entry)
375 ext3fs_dirhash(entry->name, entry->len, hinfo);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376 hash = hinfo->hash;
377
378 if (root->info.unused_flags & 1) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700379 ext3_warning(dir->i_sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700380 "Unimplemented inode hash flags: %#06x",
381 root->info.unused_flags);
382 brelse(bh);
383 *err = ERR_BAD_DX_DIR;
384 goto fail;
385 }
386
387 if ((indirect = root->info.indirect_levels) > 1) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700388 ext3_warning(dir->i_sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700389 "Unimplemented inode hash depth: %#06x",
390 root->info.indirect_levels);
391 brelse(bh);
392 *err = ERR_BAD_DX_DIR;
393 goto fail;
394 }
395
396 entries = (struct dx_entry *) (((char *)&root->info) +
397 root->info.info_length);
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700398
399 if (dx_get_limit(entries) != dx_root_limit(dir,
400 root->info.info_length)) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700401 ext3_warning(dir->i_sb, __func__,
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700402 "dx entry: limit != root limit");
403 brelse(bh);
404 *err = ERR_BAD_DX_DIR;
405 goto fail;
406 }
407
Linus Torvalds1da177e2005-04-16 15:20:36 -0700408 dxtrace (printk("Look up %x", hash));
409 while (1)
410 {
411 count = dx_get_count(entries);
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700412 if (!count || count > dx_get_limit(entries)) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700413 ext3_warning(dir->i_sb, __func__,
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700414 "dx entry: no count or count > limit");
415 brelse(bh);
416 *err = ERR_BAD_DX_DIR;
417 goto fail2;
418 }
419
Linus Torvalds1da177e2005-04-16 15:20:36 -0700420 p = entries + 1;
421 q = entries + count - 1;
422 while (p <= q)
423 {
424 m = p + (q - p)/2;
425 dxtrace(printk("."));
426 if (dx_get_hash(m) > hash)
427 q = m - 1;
428 else
429 p = m + 1;
430 }
431
432 if (0) // linear search cross check
433 {
434 unsigned n = count - 1;
435 at = entries;
436 while (n--)
437 {
438 dxtrace(printk(","));
439 if (dx_get_hash(++at) > hash)
440 {
441 at--;
442 break;
443 }
444 }
445 assert (at == p - 1);
446 }
447
448 at = p - 1;
449 dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
450 frame->bh = bh;
451 frame->entries = entries;
452 frame->at = at;
453 if (!indirect--) return frame;
454 if (!(bh = ext3_bread (NULL,dir, dx_get_block(at), 0, err)))
455 goto fail2;
456 at = entries = ((struct dx_node *) bh->b_data)->entries;
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700457 if (dx_get_limit(entries) != dx_node_limit (dir)) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700458 ext3_warning(dir->i_sb, __func__,
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700459 "dx entry: limit != node limit");
460 brelse(bh);
461 *err = ERR_BAD_DX_DIR;
462 goto fail2;
463 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464 frame++;
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700465 frame->bh = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700466 }
467fail2:
468 while (frame >= frame_in) {
469 brelse(frame->bh);
470 frame--;
471 }
472fail:
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700473 if (*err == ERR_BAD_DX_DIR)
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700474 ext3_warning(dir->i_sb, __func__,
Eric Sandeen3d82aba2007-09-18 22:46:38 -0700475 "Corrupt dir inode %ld, running e2fsck is "
476 "recommended.", dir->i_ino);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477 return NULL;
478}
479
480static void dx_release (struct dx_frame *frames)
481{
482 if (frames[0].bh == NULL)
483 return;
484
485 if (((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels)
486 brelse(frames[1].bh);
487 brelse(frames[0].bh);
488}
489
490/*
491 * This function increments the frame pointer to search the next leaf
492 * block, and reads in the necessary intervening nodes if the search
493 * should be necessary. Whether or not the search is necessary is
494 * controlled by the hash parameter. If the hash value is even, then
495 * the search is only continued if the next block starts with that
496 * hash value. This is used if we are searching for a specific file.
497 *
498 * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
499 *
500 * This function returns 1 if the caller should continue to search,
501 * or 0 if it should not. If there is an error reading one of the
502 * index blocks, it will a negative error code.
503 *
504 * If start_hash is non-null, it will be filled in with the starting
505 * hash of the next page.
506 */
507static int ext3_htree_next_block(struct inode *dir, __u32 hash,
508 struct dx_frame *frame,
Mingming Caoae6ddcc2006-09-27 01:49:27 -0700509 struct dx_frame *frames,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510 __u32 *start_hash)
511{
512 struct dx_frame *p;
513 struct buffer_head *bh;
514 int err, num_frames = 0;
515 __u32 bhash;
516
517 p = frame;
518 /*
519 * Find the next leaf page by incrementing the frame pointer.
520 * If we run out of entries in the interior node, loop around and
521 * increment pointer in the parent node. When we break out of
522 * this loop, num_frames indicates the number of interior
523 * nodes need to be read.
524 */
525 while (1) {
526 if (++(p->at) < p->entries + dx_get_count(p->entries))
527 break;
528 if (p == frames)
529 return 0;
530 num_frames++;
531 p--;
532 }
533
534 /*
535 * If the hash is 1, then continue only if the next page has a
536 * continuation hash of any value. This is used for readdir
537 * handling. Otherwise, check to see if the hash matches the
538 * desired contiuation hash. If it doesn't, return since
539 * there's no point to read in the successive index pages.
540 */
541 bhash = dx_get_hash(p->at);
542 if (start_hash)
543 *start_hash = bhash;
544 if ((hash & 1) == 0) {
545 if ((bhash & ~1) != hash)
546 return 0;
547 }
548 /*
549 * If the hash is HASH_NB_ALWAYS, we always go to the next
550 * block so no check is necessary
551 */
552 while (num_frames--) {
553 if (!(bh = ext3_bread(NULL, dir, dx_get_block(p->at),
554 0, &err)))
555 return err; /* Failure */
556 p++;
557 brelse (p->bh);
558 p->bh = bh;
559 p->at = p->entries = ((struct dx_node *) bh->b_data)->entries;
560 }
561 return 1;
562}
563
564
565/*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566 * This function fills a red-black tree with information from a
567 * directory block. It returns the number directory entries loaded
568 * into the tree. If there is an error it is returned in err.
569 */
570static int htree_dirblock_to_tree(struct file *dir_file,
571 struct inode *dir, int block,
572 struct dx_hash_info *hinfo,
573 __u32 start_hash, __u32 start_minor_hash)
574{
575 struct buffer_head *bh;
576 struct ext3_dir_entry_2 *de, *top;
577 int err, count = 0;
578
579 dxtrace(printk("In htree dirblock_to_tree: block %d\n", block));
580 if (!(bh = ext3_bread (NULL, dir, block, 0, &err)))
581 return err;
582
583 de = (struct ext3_dir_entry_2 *) bh->b_data;
584 top = (struct ext3_dir_entry_2 *) ((char *) de +
585 dir->i_sb->s_blocksize -
586 EXT3_DIR_REC_LEN(0));
587 for (; de < top; de = ext3_next_entry(de)) {
Eric Sandeen40b85132006-12-06 20:36:26 -0800588 if (!ext3_check_dir_entry("htree_dirblock_to_tree", dir, de, bh,
589 (block<<EXT3_BLOCK_SIZE_BITS(dir->i_sb))
590 +((char *)de - bh->b_data))) {
591 /* On error, skip the f_pos to the next block. */
592 dir_file->f_pos = (dir_file->f_pos |
593 (dir->i_sb->s_blocksize - 1)) + 1;
594 brelse (bh);
595 return count;
596 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700597 ext3fs_dirhash(de->name, de->name_len, hinfo);
598 if ((hinfo->hash < start_hash) ||
599 ((hinfo->hash == start_hash) &&
600 (hinfo->minor_hash < start_minor_hash)))
601 continue;
602 if (de->inode == 0)
603 continue;
604 if ((err = ext3_htree_store_dirent(dir_file,
605 hinfo->hash, hinfo->minor_hash, de)) != 0) {
606 brelse(bh);
607 return err;
608 }
609 count++;
610 }
611 brelse(bh);
612 return count;
613}
614
615
616/*
617 * This function fills a red-black tree with information from a
618 * directory. We start scanning the directory in hash order, starting
619 * at start_hash and start_minor_hash.
620 *
621 * This function returns the number of entries inserted into the tree,
622 * or a negative error code.
623 */
624int ext3_htree_fill_tree(struct file *dir_file, __u32 start_hash,
625 __u32 start_minor_hash, __u32 *next_hash)
626{
627 struct dx_hash_info hinfo;
628 struct ext3_dir_entry_2 *de;
629 struct dx_frame frames[2], *frame;
630 struct inode *dir;
631 int block, err;
632 int count = 0;
633 int ret;
634 __u32 hashval;
635
636 dxtrace(printk("In htree_fill_tree, start hash: %x:%x\n", start_hash,
637 start_minor_hash));
Josef "Jeff" Sipekfe21a692006-12-08 02:36:38 -0800638 dir = dir_file->f_path.dentry->d_inode;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700639 if (!(EXT3_I(dir)->i_flags & EXT3_INDEX_FL)) {
640 hinfo.hash_version = EXT3_SB(dir->i_sb)->s_def_hash_version;
Theodore Ts'o5e1f8c92008-10-28 13:21:55 -0400641 if (hinfo.hash_version <= DX_HASH_TEA)
642 hinfo.hash_version +=
643 EXT3_SB(dir->i_sb)->s_hash_unsigned;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed;
645 count = htree_dirblock_to_tree(dir_file, dir, 0, &hinfo,
646 start_hash, start_minor_hash);
647 *next_hash = ~0;
648 return count;
649 }
650 hinfo.hash = start_hash;
651 hinfo.minor_hash = 0;
Josef "Jeff" Sipekfe21a692006-12-08 02:36:38 -0800652 frame = dx_probe(NULL, dir_file->f_path.dentry->d_inode, &hinfo, frames, &err);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653 if (!frame)
654 return err;
655
656 /* Add '.' and '..' from the htree header */
657 if (!start_hash && !start_minor_hash) {
658 de = (struct ext3_dir_entry_2 *) frames[0].bh->b_data;
659 if ((err = ext3_htree_store_dirent(dir_file, 0, 0, de)) != 0)
660 goto errout;
661 count++;
662 }
663 if (start_hash < 2 || (start_hash ==2 && start_minor_hash==0)) {
664 de = (struct ext3_dir_entry_2 *) frames[0].bh->b_data;
665 de = ext3_next_entry(de);
666 if ((err = ext3_htree_store_dirent(dir_file, 2, 0, de)) != 0)
667 goto errout;
668 count++;
669 }
670
671 while (1) {
672 block = dx_get_block(frame->at);
673 ret = htree_dirblock_to_tree(dir_file, dir, block, &hinfo,
674 start_hash, start_minor_hash);
675 if (ret < 0) {
676 err = ret;
677 goto errout;
678 }
679 count += ret;
680 hashval = ~0;
Mingming Caoae6ddcc2006-09-27 01:49:27 -0700681 ret = ext3_htree_next_block(dir, HASH_NB_ALWAYS,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700682 frame, frames, &hashval);
683 *next_hash = hashval;
684 if (ret < 0) {
685 err = ret;
686 goto errout;
687 }
688 /*
689 * Stop if: (a) there are no more entries, or
690 * (b) we have inserted at least one entry and the
691 * next hash value is not a continuation
692 */
693 if ((ret == 0) ||
694 (count && ((hashval & 1) == 0)))
695 break;
696 }
697 dx_release(frames);
Mingming Caoae6ddcc2006-09-27 01:49:27 -0700698 dxtrace(printk("Fill tree: returned %d entries, next hash: %x\n",
Linus Torvalds1da177e2005-04-16 15:20:36 -0700699 count, *next_hash));
700 return count;
701errout:
702 dx_release(frames);
703 return (err);
704}
705
706
707/*
708 * Directory block splitting, compacting
709 */
710
Eric Sandeenef2b02d2007-09-18 22:46:42 -0700711/*
712 * Create map of hash values, offsets, and sizes, stored at end of block.
713 * Returns number of entries mapped.
714 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700715static int dx_make_map (struct ext3_dir_entry_2 *de, int size,
716 struct dx_hash_info *hinfo, struct dx_map_entry *map_tail)
717{
718 int count = 0;
719 char *base = (char *) de;
720 struct dx_hash_info h = *hinfo;
721
722 while ((char *) de < base + size)
723 {
724 if (de->name_len && de->inode) {
725 ext3fs_dirhash(de->name, de->name_len, &h);
726 map_tail--;
727 map_tail->hash = h.hash;
Eric Sandeenef2b02d2007-09-18 22:46:42 -0700728 map_tail->offs = (u16) ((char *) de - base);
729 map_tail->size = le16_to_cpu(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700730 count++;
731 cond_resched();
732 }
733 /* XXX: do we need to check rec_len == 0 case? -Chris */
Jan Kara7c06a8d2007-11-14 17:00:19 -0800734 de = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700735 }
736 return count;
737}
738
Eric Sandeenef2b02d2007-09-18 22:46:42 -0700739/* Sort map by hash value */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700740static void dx_sort_map (struct dx_map_entry *map, unsigned count)
741{
742 struct dx_map_entry *p, *q, *top = map + count - 1;
743 int more;
744 /* Combsort until bubble sort doesn't suck */
745 while (count > 2)
746 {
747 count = count*10/13;
748 if (count - 9 < 2) /* 9, 10 -> 11 */
749 count = 11;
750 for (p = top, q = p - count; q >= map; p--, q--)
751 if (p->hash < q->hash)
752 swap(*p, *q);
753 }
754 /* Garden variety bubble sort */
755 do {
756 more = 0;
757 q = top;
758 while (q-- > map)
759 {
760 if (q[1].hash >= q[0].hash)
761 continue;
762 swap(*(q+1), *q);
763 more = 1;
764 }
765 } while(more);
766}
767
768static void dx_insert_block(struct dx_frame *frame, u32 hash, u32 block)
769{
770 struct dx_entry *entries = frame->entries;
771 struct dx_entry *old = frame->at, *new = old + 1;
772 int count = dx_get_count(entries);
773
774 assert(count < dx_get_limit(entries));
775 assert(old < entries + count);
776 memmove(new + 1, new, (char *)(entries + count) - (char *)(new));
777 dx_set_hash(new, hash);
778 dx_set_block(new, block);
779 dx_set_count(entries, count + 1);
780}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700781
782static void ext3_update_dx_flag(struct inode *inode)
783{
784 if (!EXT3_HAS_COMPAT_FEATURE(inode->i_sb,
785 EXT3_FEATURE_COMPAT_DIR_INDEX))
786 EXT3_I(inode)->i_flags &= ~EXT3_INDEX_FL;
787}
788
789/*
790 * NOTE! unlike strncmp, ext3_match returns 1 for success, 0 for failure.
791 *
792 * `len <= EXT3_NAME_LEN' is guaranteed by caller.
793 * `de != NULL' is guaranteed by caller.
794 */
795static inline int ext3_match (int len, const char * const name,
796 struct ext3_dir_entry_2 * de)
797{
798 if (len != de->name_len)
799 return 0;
800 if (!de->inode)
801 return 0;
802 return !memcmp(name, de->name, len);
803}
804
805/*
806 * Returns 0 if not found, -1 on failure, and 1 on success
807 */
808static inline int search_dirblock(struct buffer_head * bh,
809 struct inode *dir,
Al Viro734711a2008-08-24 07:26:48 -0400810 struct qstr *child,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700811 unsigned long offset,
812 struct ext3_dir_entry_2 ** res_dir)
813{
814 struct ext3_dir_entry_2 * de;
815 char * dlimit;
816 int de_len;
Al Viro734711a2008-08-24 07:26:48 -0400817 const char *name = child->name;
818 int namelen = child->len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700819
820 de = (struct ext3_dir_entry_2 *) bh->b_data;
821 dlimit = bh->b_data + dir->i_sb->s_blocksize;
822 while ((char *) de < dlimit) {
823 /* this code is executed quadratically often */
824 /* do minimal checking `by hand' */
825
826 if ((char *) de + namelen <= dlimit &&
827 ext3_match (namelen, name, de)) {
828 /* found a match - just to be sure, do a full check */
829 if (!ext3_check_dir_entry("ext3_find_entry",
830 dir, de, bh, offset))
831 return -1;
832 *res_dir = de;
833 return 1;
834 }
835 /* prevent looping on a bad block */
Jan Kara7c06a8d2007-11-14 17:00:19 -0800836 de_len = ext3_rec_len_from_disk(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700837 if (de_len <= 0)
838 return -1;
839 offset += de_len;
840 de = (struct ext3_dir_entry_2 *) ((char *) de + de_len);
841 }
842 return 0;
843}
844
845
846/*
847 * ext3_find_entry()
848 *
849 * finds an entry in the specified directory with the wanted name. It
850 * returns the cache buffer in which the entry was found, and the entry
851 * itself (as a parameter - res_dir). It does NOT read the inode of the
852 * entry - you'll have to do that yourself if you want to.
853 *
854 * The returned buffer_head has ->b_count elevated. The caller is expected
855 * to brelse() it when appropriate.
856 */
Al Viro734711a2008-08-24 07:26:48 -0400857static struct buffer_head *ext3_find_entry(struct inode *dir,
858 struct qstr *entry,
859 struct ext3_dir_entry_2 **res_dir)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700860{
861 struct super_block * sb;
862 struct buffer_head * bh_use[NAMEI_RA_SIZE];
863 struct buffer_head * bh, *ret = NULL;
864 unsigned long start, block, b;
865 int ra_max = 0; /* Number of bh's in the readahead
866 buffer, bh_use[] */
867 int ra_ptr = 0; /* Current index into readahead
868 buffer */
869 int num = 0;
870 int nblocks, i, err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871 int namelen;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700872
873 *res_dir = NULL;
874 sb = dir->i_sb;
Al Viro734711a2008-08-24 07:26:48 -0400875 namelen = entry->len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700876 if (namelen > EXT3_NAME_LEN)
877 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700878 if (is_dx(dir)) {
Al Viro734711a2008-08-24 07:26:48 -0400879 bh = ext3_dx_find_entry(dir, entry, res_dir, &err);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700880 /*
881 * On success, or if the error was file not found,
882 * return. Otherwise, fall back to doing a search the
883 * old fashioned way.
884 */
885 if (bh || (err != ERR_BAD_DX_DIR))
886 return bh;
887 dxtrace(printk("ext3_find_entry: dx failed, falling back\n"));
888 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700889 nblocks = dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb);
890 start = EXT3_I(dir)->i_dir_start_lookup;
891 if (start >= nblocks)
892 start = 0;
893 block = start;
894restart:
895 do {
896 /*
897 * We deal with the read-ahead logic here.
898 */
899 if (ra_ptr >= ra_max) {
900 /* Refill the readahead buffer */
901 ra_ptr = 0;
902 b = block;
903 for (ra_max = 0; ra_max < NAMEI_RA_SIZE; ra_max++) {
904 /*
905 * Terminate if we reach the end of the
906 * directory and must wrap, or if our
907 * search has finished at this block.
908 */
909 if (b >= nblocks || (num && block == start)) {
910 bh_use[ra_max] = NULL;
911 break;
912 }
913 num++;
914 bh = ext3_getblk(NULL, dir, b++, 0, &err);
915 bh_use[ra_max] = bh;
916 if (bh)
Jens Axboecaa38fb2006-07-23 01:41:26 +0200917 ll_rw_block(READ_META, 1, &bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700918 }
919 }
920 if ((bh = bh_use[ra_ptr++]) == NULL)
921 goto next;
922 wait_on_buffer(bh);
923 if (!buffer_uptodate(bh)) {
924 /* read error, skip block & hope for the best */
Harvey Harrisone05b6b52008-04-28 02:16:15 -0700925 ext3_error(sb, __func__, "reading directory #%lu "
Linus Torvalds1da177e2005-04-16 15:20:36 -0700926 "offset %lu", dir->i_ino, block);
927 brelse(bh);
928 goto next;
929 }
Al Viro734711a2008-08-24 07:26:48 -0400930 i = search_dirblock(bh, dir, entry,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700931 block << EXT3_BLOCK_SIZE_BITS(sb), res_dir);
932 if (i == 1) {
933 EXT3_I(dir)->i_dir_start_lookup = block;
934 ret = bh;
935 goto cleanup_and_exit;
936 } else {
937 brelse(bh);
938 if (i < 0)
939 goto cleanup_and_exit;
940 }
941 next:
942 if (++block >= nblocks)
943 block = 0;
944 } while (block != start);
945
946 /*
947 * If the directory has grown while we were searching, then
948 * search the last part of the directory before giving up.
949 */
950 block = nblocks;
951 nblocks = dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb);
952 if (block < nblocks) {
953 start = 0;
954 goto restart;
955 }
956
957cleanup_and_exit:
958 /* Clean up the read-ahead blocks */
959 for (; ra_ptr < ra_max; ra_ptr++)
960 brelse (bh_use[ra_ptr]);
961 return ret;
962}
963
Al Viro734711a2008-08-24 07:26:48 -0400964static struct buffer_head * ext3_dx_find_entry(struct inode *dir,
965 struct qstr *entry, struct ext3_dir_entry_2 **res_dir,
966 int *err)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700967{
968 struct super_block * sb;
969 struct dx_hash_info hinfo;
970 u32 hash;
971 struct dx_frame frames[2], *frame;
972 struct ext3_dir_entry_2 *de, *top;
973 struct buffer_head *bh;
974 unsigned long block;
975 int retval;
Al Viro734711a2008-08-24 07:26:48 -0400976 int namelen = entry->len;
977 const u8 *name = entry->name;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700978
979 sb = dir->i_sb;
Andreas Dilgeracfa1823d2005-06-23 00:09:45 -0700980 /* NFS may look up ".." - look at dx_root directory block */
Al Viro734711a2008-08-24 07:26:48 -0400981 if (namelen > 2 || name[0] != '.'|| (namelen == 2 && name[1] != '.')) {
982 if (!(frame = dx_probe(entry, dir, &hinfo, frames, err)))
Andreas Dilgeracfa1823d2005-06-23 00:09:45 -0700983 return NULL;
984 } else {
985 frame = frames;
986 frame->bh = NULL; /* for dx_release() */
987 frame->at = (struct dx_entry *)frames; /* hack for zero entry*/
988 dx_set_block(frame->at, 0); /* dx_root block is 0 */
989 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700990 hash = hinfo.hash;
991 do {
992 block = dx_get_block(frame->at);
993 if (!(bh = ext3_bread (NULL,dir, block, 0, err)))
994 goto errout;
995 de = (struct ext3_dir_entry_2 *) bh->b_data;
996 top = (struct ext3_dir_entry_2 *) ((char *) de + sb->s_blocksize -
997 EXT3_DIR_REC_LEN(0));
Duane Griffin275c0a82008-07-25 01:46:31 -0700998 for (; de < top; de = ext3_next_entry(de)) {
999 int off = (block << EXT3_BLOCK_SIZE_BITS(sb))
1000 + ((char *) de - bh->b_data);
1001
1002 if (!ext3_check_dir_entry(__func__, dir, de, bh, off)) {
1003 brelse(bh);
Dmitriy Monakhovfedee542007-05-08 00:25:34 -07001004 *err = ERR_BAD_DX_DIR;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001005 goto errout;
1006 }
Duane Griffin275c0a82008-07-25 01:46:31 -07001007
1008 if (ext3_match(namelen, name, de)) {
1009 *res_dir = de;
1010 dx_release(frames);
1011 return bh;
1012 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001013 }
1014 brelse (bh);
1015 /* Check to see if we should continue to search */
1016 retval = ext3_htree_next_block(dir, hash, frame,
1017 frames, NULL);
1018 if (retval < 0) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001019 ext3_warning(sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001020 "error reading index page in directory #%lu",
1021 dir->i_ino);
1022 *err = retval;
1023 goto errout;
1024 }
1025 } while (retval == 1);
1026
1027 *err = -ENOENT;
1028errout:
1029 dxtrace(printk("%s not found\n", name));
1030 dx_release (frames);
1031 return NULL;
1032}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001033
1034static struct dentry *ext3_lookup(struct inode * dir, struct dentry *dentry, struct nameidata *nd)
1035{
1036 struct inode * inode;
1037 struct ext3_dir_entry_2 * de;
1038 struct buffer_head * bh;
1039
1040 if (dentry->d_name.len > EXT3_NAME_LEN)
1041 return ERR_PTR(-ENAMETOOLONG);
1042
Al Viro734711a2008-08-24 07:26:48 -04001043 bh = ext3_find_entry(dir, &dentry->d_name, &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001044 inode = NULL;
1045 if (bh) {
1046 unsigned long ino = le32_to_cpu(de->inode);
1047 brelse (bh);
Neil Brown2ccb48e2006-07-30 03:03:01 -07001048 if (!ext3_valid_inum(dir->i_sb, ino)) {
1049 ext3_error(dir->i_sb, "ext3_lookup",
1050 "bad inode number: %lu", ino);
David Howells473043d2008-02-07 00:15:36 -08001051 return ERR_PTR(-EIO);
Vasily Averina6c15c22007-07-15 23:40:46 -07001052 }
David Howells473043d2008-02-07 00:15:36 -08001053 inode = ext3_iget(dir->i_sb, ino);
1054 if (IS_ERR(inode))
1055 return ERR_CAST(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001056 }
Pekka Enbergba7fe362006-01-14 13:21:08 -08001057 return d_splice_alias(inode, dentry);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001058}
1059
1060
1061struct dentry *ext3_get_parent(struct dentry *child)
1062{
1063 unsigned long ino;
Al Viro734711a2008-08-24 07:26:48 -04001064 struct qstr dotdot = {.name = "..", .len = 2};
Linus Torvalds1da177e2005-04-16 15:20:36 -07001065 struct ext3_dir_entry_2 * de;
1066 struct buffer_head *bh;
1067
Al Viro734711a2008-08-24 07:26:48 -04001068 bh = ext3_find_entry(child->d_inode, &dotdot, &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001069 if (!bh)
1070 return ERR_PTR(-ENOENT);
1071 ino = le32_to_cpu(de->inode);
1072 brelse(bh);
Neil Brown2ccb48e2006-07-30 03:03:01 -07001073
1074 if (!ext3_valid_inum(child->d_inode->i_sb, ino)) {
1075 ext3_error(child->d_inode->i_sb, "ext3_get_parent",
1076 "bad inode number: %lu", ino);
David Howells473043d2008-02-07 00:15:36 -08001077 return ERR_PTR(-EIO);
Vasily Averina6c15c22007-07-15 23:40:46 -07001078 }
1079
Christoph Hellwig44003722008-08-11 15:49:04 +02001080 return d_obtain_alias(ext3_iget(child->d_inode->i_sb, ino));
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001081}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001082
1083#define S_SHIFT 12
1084static unsigned char ext3_type_by_mode[S_IFMT >> S_SHIFT] = {
1085 [S_IFREG >> S_SHIFT] = EXT3_FT_REG_FILE,
1086 [S_IFDIR >> S_SHIFT] = EXT3_FT_DIR,
1087 [S_IFCHR >> S_SHIFT] = EXT3_FT_CHRDEV,
1088 [S_IFBLK >> S_SHIFT] = EXT3_FT_BLKDEV,
1089 [S_IFIFO >> S_SHIFT] = EXT3_FT_FIFO,
1090 [S_IFSOCK >> S_SHIFT] = EXT3_FT_SOCK,
1091 [S_IFLNK >> S_SHIFT] = EXT3_FT_SYMLINK,
1092};
1093
1094static inline void ext3_set_de_type(struct super_block *sb,
1095 struct ext3_dir_entry_2 *de,
1096 umode_t mode) {
1097 if (EXT3_HAS_INCOMPAT_FEATURE(sb, EXT3_FEATURE_INCOMPAT_FILETYPE))
1098 de->file_type = ext3_type_by_mode[(mode & S_IFMT)>>S_SHIFT];
1099}
1100
Eric Sandeenef2b02d2007-09-18 22:46:42 -07001101/*
1102 * Move count entries from end of map between two memory locations.
1103 * Returns pointer to last entry moved.
1104 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001105static struct ext3_dir_entry_2 *
1106dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count)
1107{
1108 unsigned rec_len = 0;
1109
1110 while (count--) {
1111 struct ext3_dir_entry_2 *de = (struct ext3_dir_entry_2 *) (from + map->offs);
1112 rec_len = EXT3_DIR_REC_LEN(de->name_len);
1113 memcpy (to, de, rec_len);
1114 ((struct ext3_dir_entry_2 *) to)->rec_len =
Jan Kara7c06a8d2007-11-14 17:00:19 -08001115 ext3_rec_len_to_disk(rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001116 de->inode = 0;
1117 map++;
1118 to += rec_len;
1119 }
1120 return (struct ext3_dir_entry_2 *) (to - rec_len);
1121}
1122
Eric Sandeenef2b02d2007-09-18 22:46:42 -07001123/*
1124 * Compact each dir entry in the range to the minimal rec_len.
1125 * Returns pointer to last entry in range.
1126 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001127static struct ext3_dir_entry_2* dx_pack_dirents(char *base, int size)
1128{
1129 struct ext3_dir_entry_2 *next, *to, *prev, *de = (struct ext3_dir_entry_2 *) base;
1130 unsigned rec_len = 0;
1131
1132 prev = to = de;
1133 while ((char*)de < base + size) {
Jan Kara7c06a8d2007-11-14 17:00:19 -08001134 next = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001135 if (de->inode && de->name_len) {
1136 rec_len = EXT3_DIR_REC_LEN(de->name_len);
1137 if (de > to)
1138 memmove(to, de, rec_len);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001139 to->rec_len = ext3_rec_len_to_disk(rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001140 prev = to;
1141 to = (struct ext3_dir_entry_2 *) (((char *) to) + rec_len);
1142 }
1143 de = next;
1144 }
1145 return prev;
1146}
1147
Eric Sandeenef2b02d2007-09-18 22:46:42 -07001148/*
1149 * Split a full leaf block to make room for a new dir entry.
1150 * Allocate a new block, and move entries so that they are approx. equally full.
1151 * Returns pointer to de in block into which the new entry will be inserted.
1152 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001153static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
1154 struct buffer_head **bh,struct dx_frame *frame,
1155 struct dx_hash_info *hinfo, int *error)
1156{
1157 unsigned blocksize = dir->i_sb->s_blocksize;
1158 unsigned count, continued;
1159 struct buffer_head *bh2;
1160 u32 newblock;
1161 u32 hash2;
1162 struct dx_map_entry *map;
1163 char *data1 = (*bh)->b_data, *data2;
Theodore Ts'o59e315b2008-12-06 16:58:39 -05001164 unsigned split, move, size;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001165 struct ext3_dir_entry_2 *de = NULL, *de2;
Theodore Ts'o59e315b2008-12-06 16:58:39 -05001166 int err = 0, i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001167
Dmitriy Monakhovfedee542007-05-08 00:25:34 -07001168 bh2 = ext3_append (handle, dir, &newblock, &err);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001169 if (!(bh2)) {
1170 brelse(*bh);
1171 *bh = NULL;
1172 goto errout;
1173 }
1174
1175 BUFFER_TRACE(*bh, "get_write_access");
1176 err = ext3_journal_get_write_access(handle, *bh);
Dmitriy Monakhovfedee542007-05-08 00:25:34 -07001177 if (err)
1178 goto journal_error;
1179
Linus Torvalds1da177e2005-04-16 15:20:36 -07001180 BUFFER_TRACE(frame->bh, "get_write_access");
1181 err = ext3_journal_get_write_access(handle, frame->bh);
1182 if (err)
1183 goto journal_error;
1184
1185 data2 = bh2->b_data;
1186
1187 /* create map in the end of data2 block */
1188 map = (struct dx_map_entry *) (data2 + blocksize);
1189 count = dx_make_map ((struct ext3_dir_entry_2 *) data1,
1190 blocksize, hinfo, map);
1191 map -= count;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001192 dx_sort_map (map, count);
Eric Sandeenef2b02d2007-09-18 22:46:42 -07001193 /* Split the existing block in the middle, size-wise */
1194 size = 0;
1195 move = 0;
1196 for (i = count-1; i >= 0; i--) {
1197 /* is more than half of this entry in 2nd half of the block? */
1198 if (size + map[i].size/2 > blocksize/2)
1199 break;
1200 size += map[i].size;
1201 move++;
1202 }
1203 /* map index at which we will split */
1204 split = count - move;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001205 hash2 = map[split].hash;
1206 continued = hash2 == map[split - 1].hash;
1207 dxtrace(printk("Split block %i at %x, %i/%i\n",
1208 dx_get_block(frame->at), hash2, split, count-split));
1209
1210 /* Fancy dance to stay within two buffers */
1211 de2 = dx_move_dirents(data1, data2, map + split, count - split);
1212 de = dx_pack_dirents(data1,blocksize);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001213 de->rec_len = ext3_rec_len_to_disk(data1 + blocksize - (char *) de);
1214 de2->rec_len = ext3_rec_len_to_disk(data2 + blocksize - (char *) de2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001215 dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data1, blocksize, 1));
1216 dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data2, blocksize, 1));
1217
1218 /* Which block gets the new entry? */
1219 if (hinfo->hash >= hash2)
1220 {
1221 swap(*bh, bh2);
1222 de = de2;
1223 }
1224 dx_insert_block (frame, hash2 + continued, newblock);
1225 err = ext3_journal_dirty_metadata (handle, bh2);
1226 if (err)
1227 goto journal_error;
1228 err = ext3_journal_dirty_metadata (handle, frame->bh);
1229 if (err)
1230 goto journal_error;
1231 brelse (bh2);
1232 dxtrace(dx_show_index ("frame", frame->entries));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001233 return de;
Dmitriy Monakhovfedee542007-05-08 00:25:34 -07001234
1235journal_error:
1236 brelse(*bh);
1237 brelse(bh2);
1238 *bh = NULL;
1239 ext3_std_error(dir->i_sb, err);
1240errout:
1241 *error = err;
1242 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001243}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001244
1245
1246/*
1247 * Add a new entry into a directory (leaf) block. If de is non-NULL,
1248 * it points to a directory entry which is guaranteed to be large
1249 * enough for new directory entry. If de is NULL, then
1250 * add_dirent_to_buf will attempt search the directory block for
1251 * space. It will return -ENOSPC if no space is available, and -EIO
1252 * and -EEXIST if directory entry already exists.
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001253 *
Linus Torvalds1da177e2005-04-16 15:20:36 -07001254 * NOTE! bh is NOT released in the case where ENOSPC is returned. In
1255 * all other cases bh is released.
1256 */
1257static int add_dirent_to_buf(handle_t *handle, struct dentry *dentry,
1258 struct inode *inode, struct ext3_dir_entry_2 *de,
1259 struct buffer_head * bh)
1260{
1261 struct inode *dir = dentry->d_parent->d_inode;
1262 const char *name = dentry->d_name.name;
1263 int namelen = dentry->d_name.len;
1264 unsigned long offset = 0;
1265 unsigned short reclen;
1266 int nlen, rlen, err;
1267 char *top;
1268
1269 reclen = EXT3_DIR_REC_LEN(namelen);
1270 if (!de) {
1271 de = (struct ext3_dir_entry_2 *)bh->b_data;
1272 top = bh->b_data + dir->i_sb->s_blocksize - reclen;
1273 while ((char *) de <= top) {
1274 if (!ext3_check_dir_entry("ext3_add_entry", dir, de,
1275 bh, offset)) {
1276 brelse (bh);
1277 return -EIO;
1278 }
1279 if (ext3_match (namelen, name, de)) {
1280 brelse (bh);
1281 return -EEXIST;
1282 }
1283 nlen = EXT3_DIR_REC_LEN(de->name_len);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001284 rlen = ext3_rec_len_from_disk(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001285 if ((de->inode? rlen - nlen: rlen) >= reclen)
1286 break;
1287 de = (struct ext3_dir_entry_2 *)((char *)de + rlen);
1288 offset += rlen;
1289 }
1290 if ((char *) de > top)
1291 return -ENOSPC;
1292 }
1293 BUFFER_TRACE(bh, "get_write_access");
1294 err = ext3_journal_get_write_access(handle, bh);
1295 if (err) {
1296 ext3_std_error(dir->i_sb, err);
1297 brelse(bh);
1298 return err;
1299 }
1300
1301 /* By now the buffer is marked for journaling */
1302 nlen = EXT3_DIR_REC_LEN(de->name_len);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001303 rlen = ext3_rec_len_from_disk(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001304 if (de->inode) {
1305 struct ext3_dir_entry_2 *de1 = (struct ext3_dir_entry_2 *)((char *)de + nlen);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001306 de1->rec_len = ext3_rec_len_to_disk(rlen - nlen);
1307 de->rec_len = ext3_rec_len_to_disk(nlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001308 de = de1;
1309 }
1310 de->file_type = EXT3_FT_UNKNOWN;
1311 if (inode) {
1312 de->inode = cpu_to_le32(inode->i_ino);
1313 ext3_set_de_type(dir->i_sb, de, inode->i_mode);
1314 } else
1315 de->inode = 0;
1316 de->name_len = namelen;
1317 memcpy (de->name, name, namelen);
1318 /*
1319 * XXX shouldn't update any times until successful
1320 * completion of syscall, but too many callers depend
1321 * on this.
1322 *
1323 * XXX similarly, too many callers depend on
1324 * ext3_new_inode() setting the times, but error
1325 * recovery deletes the inode, so the worst that can
1326 * happen is that the times are slightly out of date
1327 * and/or different from the directory change time.
1328 */
1329 dir->i_mtime = dir->i_ctime = CURRENT_TIME_SEC;
1330 ext3_update_dx_flag(dir);
1331 dir->i_version++;
1332 ext3_mark_inode_dirty(handle, dir);
1333 BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata");
1334 err = ext3_journal_dirty_metadata(handle, bh);
1335 if (err)
1336 ext3_std_error(dir->i_sb, err);
1337 brelse(bh);
1338 return 0;
1339}
1340
Linus Torvalds1da177e2005-04-16 15:20:36 -07001341/*
1342 * This converts a one block unindexed directory to a 3 block indexed
1343 * directory, and adds the dentry to the indexed directory.
1344 */
1345static int make_indexed_dir(handle_t *handle, struct dentry *dentry,
1346 struct inode *inode, struct buffer_head *bh)
1347{
1348 struct inode *dir = dentry->d_parent->d_inode;
1349 const char *name = dentry->d_name.name;
1350 int namelen = dentry->d_name.len;
1351 struct buffer_head *bh2;
1352 struct dx_root *root;
1353 struct dx_frame frames[2], *frame;
1354 struct dx_entry *entries;
1355 struct ext3_dir_entry_2 *de, *de2;
1356 char *data1, *top;
1357 unsigned len;
1358 int retval;
1359 unsigned blocksize;
1360 struct dx_hash_info hinfo;
1361 u32 block;
1362 struct fake_dirent *fde;
1363
1364 blocksize = dir->i_sb->s_blocksize;
1365 dxtrace(printk("Creating index\n"));
1366 retval = ext3_journal_get_write_access(handle, bh);
1367 if (retval) {
1368 ext3_std_error(dir->i_sb, retval);
1369 brelse(bh);
1370 return retval;
1371 }
1372 root = (struct dx_root *) bh->b_data;
1373
1374 bh2 = ext3_append (handle, dir, &block, &retval);
1375 if (!(bh2)) {
1376 brelse(bh);
1377 return retval;
1378 }
1379 EXT3_I(dir)->i_flags |= EXT3_INDEX_FL;
1380 data1 = bh2->b_data;
1381
1382 /* The 0th block becomes the root, move the dirents out */
1383 fde = &root->dotdot;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001384 de = (struct ext3_dir_entry_2 *)((char *)fde +
1385 ext3_rec_len_from_disk(fde->rec_len));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386 len = ((char *) root) + blocksize - (char *) de;
1387 memcpy (data1, de, len);
1388 de = (struct ext3_dir_entry_2 *) data1;
1389 top = data1 + len;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001390 while ((char *)(de2 = ext3_next_entry(de)) < top)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391 de = de2;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001392 de->rec_len = ext3_rec_len_to_disk(data1 + blocksize - (char *) de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001393 /* Initialize the root; the dot dirents already exist */
1394 de = (struct ext3_dir_entry_2 *) (&root->dotdot);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001395 de->rec_len = ext3_rec_len_to_disk(blocksize - EXT3_DIR_REC_LEN(2));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001396 memset (&root->info, 0, sizeof(root->info));
1397 root->info.info_length = sizeof(root->info);
1398 root->info.hash_version = EXT3_SB(dir->i_sb)->s_def_hash_version;
1399 entries = root->entries;
1400 dx_set_block (entries, 1);
1401 dx_set_count (entries, 1);
1402 dx_set_limit (entries, dx_root_limit(dir, sizeof(root->info)));
1403
1404 /* Initialize as for dx_probe */
1405 hinfo.hash_version = root->info.hash_version;
Theodore Ts'o5e1f8c92008-10-28 13:21:55 -04001406 if (hinfo.hash_version <= DX_HASH_TEA)
1407 hinfo.hash_version += EXT3_SB(dir->i_sb)->s_hash_unsigned;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001408 hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed;
1409 ext3fs_dirhash(name, namelen, &hinfo);
1410 frame = frames;
1411 frame->entries = entries;
1412 frame->at = entries;
1413 frame->bh = bh;
1414 bh = bh2;
1415 de = do_split(handle,dir, &bh, frame, &hinfo, &retval);
1416 dx_release (frames);
1417 if (!(de))
1418 return retval;
1419
1420 return add_dirent_to_buf(handle, dentry, inode, de, bh);
1421}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001422
1423/*
1424 * ext3_add_entry()
1425 *
1426 * adds a file entry to the specified directory, using the same
1427 * semantics as ext3_find_entry(). It returns NULL if it failed.
1428 *
1429 * NOTE!! The inode part of 'de' is left at 0 - which means you
1430 * may not sleep between calling this and putting something into
1431 * the entry, as someone else might have used it while you slept.
1432 */
1433static int ext3_add_entry (handle_t *handle, struct dentry *dentry,
1434 struct inode *inode)
1435{
1436 struct inode *dir = dentry->d_parent->d_inode;
1437 unsigned long offset;
1438 struct buffer_head * bh;
1439 struct ext3_dir_entry_2 *de;
1440 struct super_block * sb;
1441 int retval;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001442 int dx_fallback=0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001443 unsigned blocksize;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001444 u32 block, blocks;
1445
1446 sb = dir->i_sb;
1447 blocksize = sb->s_blocksize;
1448 if (!dentry->d_name.len)
1449 return -EINVAL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001450 if (is_dx(dir)) {
1451 retval = ext3_dx_add_entry(handle, dentry, inode);
1452 if (!retval || (retval != ERR_BAD_DX_DIR))
1453 return retval;
1454 EXT3_I(dir)->i_flags &= ~EXT3_INDEX_FL;
1455 dx_fallback++;
1456 ext3_mark_inode_dirty(handle, dir);
1457 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001458 blocks = dir->i_size >> sb->s_blocksize_bits;
1459 for (block = 0, offset = 0; block < blocks; block++) {
1460 bh = ext3_bread(handle, dir, block, 0, &retval);
1461 if(!bh)
1462 return retval;
1463 retval = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1464 if (retval != -ENOSPC)
1465 return retval;
1466
Linus Torvalds1da177e2005-04-16 15:20:36 -07001467 if (blocks == 1 && !dx_fallback &&
1468 EXT3_HAS_COMPAT_FEATURE(sb, EXT3_FEATURE_COMPAT_DIR_INDEX))
1469 return make_indexed_dir(handle, dentry, inode, bh);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001470 brelse(bh);
1471 }
1472 bh = ext3_append(handle, dir, &block, &retval);
1473 if (!bh)
1474 return retval;
1475 de = (struct ext3_dir_entry_2 *) bh->b_data;
1476 de->inode = 0;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001477 de->rec_len = ext3_rec_len_to_disk(blocksize);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001478 return add_dirent_to_buf(handle, dentry, inode, de, bh);
1479}
1480
Linus Torvalds1da177e2005-04-16 15:20:36 -07001481/*
1482 * Returns 0 for success, or a negative error value
1483 */
1484static int ext3_dx_add_entry(handle_t *handle, struct dentry *dentry,
1485 struct inode *inode)
1486{
1487 struct dx_frame frames[2], *frame;
1488 struct dx_entry *entries, *at;
1489 struct dx_hash_info hinfo;
1490 struct buffer_head * bh;
1491 struct inode *dir = dentry->d_parent->d_inode;
1492 struct super_block * sb = dir->i_sb;
1493 struct ext3_dir_entry_2 *de;
1494 int err;
1495
Al Viro734711a2008-08-24 07:26:48 -04001496 frame = dx_probe(&dentry->d_name, dir, &hinfo, frames, &err);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001497 if (!frame)
1498 return err;
1499 entries = frame->entries;
1500 at = frame->at;
1501
1502 if (!(bh = ext3_bread(handle,dir, dx_get_block(frame->at), 0, &err)))
1503 goto cleanup;
1504
1505 BUFFER_TRACE(bh, "get_write_access");
1506 err = ext3_journal_get_write_access(handle, bh);
1507 if (err)
1508 goto journal_error;
1509
1510 err = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1511 if (err != -ENOSPC) {
1512 bh = NULL;
1513 goto cleanup;
1514 }
1515
1516 /* Block full, should compress but for now just split */
1517 dxtrace(printk("using %u of %u node entries\n",
1518 dx_get_count(entries), dx_get_limit(entries)));
1519 /* Need to split index? */
1520 if (dx_get_count(entries) == dx_get_limit(entries)) {
1521 u32 newblock;
1522 unsigned icount = dx_get_count(entries);
1523 int levels = frame - frames;
1524 struct dx_entry *entries2;
1525 struct dx_node *node2;
1526 struct buffer_head *bh2;
1527
1528 if (levels && (dx_get_count(frames->entries) ==
1529 dx_get_limit(frames->entries))) {
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001530 ext3_warning(sb, __func__,
Glauber de Oliveira Costa9f406682006-01-08 01:03:22 -08001531 "Directory index full!");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001532 err = -ENOSPC;
1533 goto cleanup;
1534 }
1535 bh2 = ext3_append (handle, dir, &newblock, &err);
1536 if (!(bh2))
1537 goto cleanup;
1538 node2 = (struct dx_node *)(bh2->b_data);
1539 entries2 = node2->entries;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001540 node2->fake.rec_len = ext3_rec_len_to_disk(sb->s_blocksize);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001541 node2->fake.inode = 0;
1542 BUFFER_TRACE(frame->bh, "get_write_access");
1543 err = ext3_journal_get_write_access(handle, frame->bh);
1544 if (err)
1545 goto journal_error;
1546 if (levels) {
1547 unsigned icount1 = icount/2, icount2 = icount - icount1;
1548 unsigned hash2 = dx_get_hash(entries + icount1);
1549 dxtrace(printk("Split index %i/%i\n", icount1, icount2));
1550
1551 BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
1552 err = ext3_journal_get_write_access(handle,
1553 frames[0].bh);
1554 if (err)
1555 goto journal_error;
1556
1557 memcpy ((char *) entries2, (char *) (entries + icount1),
1558 icount2 * sizeof(struct dx_entry));
1559 dx_set_count (entries, icount1);
1560 dx_set_count (entries2, icount2);
1561 dx_set_limit (entries2, dx_node_limit(dir));
1562
1563 /* Which index block gets the new entry? */
1564 if (at - entries >= icount1) {
1565 frame->at = at = at - entries - icount1 + entries2;
1566 frame->entries = entries = entries2;
1567 swap(frame->bh, bh2);
1568 }
1569 dx_insert_block (frames + 0, hash2, newblock);
1570 dxtrace(dx_show_index ("node", frames[1].entries));
1571 dxtrace(dx_show_index ("node",
1572 ((struct dx_node *) bh2->b_data)->entries));
1573 err = ext3_journal_dirty_metadata(handle, bh2);
1574 if (err)
1575 goto journal_error;
1576 brelse (bh2);
1577 } else {
1578 dxtrace(printk("Creating second level index...\n"));
1579 memcpy((char *) entries2, (char *) entries,
1580 icount * sizeof(struct dx_entry));
1581 dx_set_limit(entries2, dx_node_limit(dir));
1582
1583 /* Set up root */
1584 dx_set_count(entries, 1);
1585 dx_set_block(entries + 0, newblock);
1586 ((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
1587
1588 /* Add new access path frame */
1589 frame = frames + 1;
1590 frame->at = at = at - entries + entries2;
1591 frame->entries = entries = entries2;
1592 frame->bh = bh2;
1593 err = ext3_journal_get_write_access(handle,
1594 frame->bh);
1595 if (err)
1596 goto journal_error;
1597 }
1598 ext3_journal_dirty_metadata(handle, frames[0].bh);
1599 }
1600 de = do_split(handle, dir, &bh, frame, &hinfo, &err);
1601 if (!de)
1602 goto cleanup;
1603 err = add_dirent_to_buf(handle, dentry, inode, de, bh);
1604 bh = NULL;
1605 goto cleanup;
1606
1607journal_error:
1608 ext3_std_error(dir->i_sb, err);
1609cleanup:
1610 if (bh)
1611 brelse(bh);
1612 dx_release(frames);
1613 return err;
1614}
Linus Torvalds1da177e2005-04-16 15:20:36 -07001615
1616/*
1617 * ext3_delete_entry deletes a directory entry by merging it with the
1618 * previous entry
1619 */
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001620static int ext3_delete_entry (handle_t *handle,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001621 struct inode * dir,
1622 struct ext3_dir_entry_2 * de_del,
1623 struct buffer_head * bh)
1624{
1625 struct ext3_dir_entry_2 * de, * pde;
1626 int i;
1627
1628 i = 0;
1629 pde = NULL;
1630 de = (struct ext3_dir_entry_2 *) bh->b_data;
1631 while (i < bh->b_size) {
1632 if (!ext3_check_dir_entry("ext3_delete_entry", dir, de, bh, i))
1633 return -EIO;
1634 if (de == de_del) {
1635 BUFFER_TRACE(bh, "get_write_access");
1636 ext3_journal_get_write_access(handle, bh);
1637 if (pde)
Jan Kara7c06a8d2007-11-14 17:00:19 -08001638 pde->rec_len = ext3_rec_len_to_disk(
1639 ext3_rec_len_from_disk(pde->rec_len) +
1640 ext3_rec_len_from_disk(de->rec_len));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001641 else
1642 de->inode = 0;
1643 dir->i_version++;
1644 BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata");
1645 ext3_journal_dirty_metadata(handle, bh);
1646 return 0;
1647 }
Jan Kara7c06a8d2007-11-14 17:00:19 -08001648 i += ext3_rec_len_from_disk(de->rec_len);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001649 pde = de;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001650 de = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001651 }
1652 return -ENOENT;
1653}
1654
Linus Torvalds1da177e2005-04-16 15:20:36 -07001655static int ext3_add_nondir(handle_t *handle,
1656 struct dentry *dentry, struct inode *inode)
1657{
1658 int err = ext3_add_entry(handle, dentry, inode);
1659 if (!err) {
1660 ext3_mark_inode_dirty(handle, inode);
1661 d_instantiate(dentry, inode);
Al Viroc38012d2008-12-30 02:02:50 -05001662 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001663 return 0;
1664 }
Eric Sandeen731b9a52007-02-10 01:46:16 -08001665 drop_nlink(inode);
Al Viroc38012d2008-12-30 02:02:50 -05001666 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001667 iput(inode);
1668 return err;
1669}
1670
1671/*
1672 * By the time this is called, we already have created
1673 * the directory cache entry for the new file, but it
1674 * is so far negative - it has no inode.
1675 *
1676 * If the create succeeds, we fill in the inode information
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001677 * with d_instantiate().
Linus Torvalds1da177e2005-04-16 15:20:36 -07001678 */
1679static int ext3_create (struct inode * dir, struct dentry * dentry, int mode,
1680 struct nameidata *nd)
1681{
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001682 handle_t *handle;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001683 struct inode * inode;
1684 int err, retries = 0;
1685
1686retry:
Jan Kara1f545872005-06-23 22:01:04 -07001687 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Linus Torvalds1da177e2005-04-16 15:20:36 -07001688 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3 +
Jan Kara1f545872005-06-23 22:01:04 -07001689 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001690 if (IS_ERR(handle))
1691 return PTR_ERR(handle);
1692
1693 if (IS_DIRSYNC(dir))
1694 handle->h_sync = 1;
1695
1696 inode = ext3_new_inode (handle, dir, mode);
1697 err = PTR_ERR(inode);
1698 if (!IS_ERR(inode)) {
1699 inode->i_op = &ext3_file_inode_operations;
1700 inode->i_fop = &ext3_file_operations;
1701 ext3_set_aops(inode);
1702 err = ext3_add_nondir(handle, dentry, inode);
1703 }
1704 ext3_journal_stop(handle);
1705 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
1706 goto retry;
1707 return err;
1708}
1709
1710static int ext3_mknod (struct inode * dir, struct dentry *dentry,
1711 int mode, dev_t rdev)
1712{
1713 handle_t *handle;
1714 struct inode *inode;
1715 int err, retries = 0;
1716
1717 if (!new_valid_dev(rdev))
1718 return -EINVAL;
1719
1720retry:
Jan Kara1f545872005-06-23 22:01:04 -07001721 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Dave Kleikampe9ad5622006-09-27 01:49:35 -07001722 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3 +
Jan Kara1f545872005-06-23 22:01:04 -07001723 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001724 if (IS_ERR(handle))
1725 return PTR_ERR(handle);
1726
1727 if (IS_DIRSYNC(dir))
1728 handle->h_sync = 1;
1729
1730 inode = ext3_new_inode (handle, dir, mode);
1731 err = PTR_ERR(inode);
1732 if (!IS_ERR(inode)) {
1733 init_special_inode(inode, inode->i_mode, rdev);
1734#ifdef CONFIG_EXT3_FS_XATTR
1735 inode->i_op = &ext3_special_inode_operations;
1736#endif
1737 err = ext3_add_nondir(handle, dentry, inode);
1738 }
1739 ext3_journal_stop(handle);
1740 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
1741 goto retry;
1742 return err;
1743}
1744
1745static int ext3_mkdir(struct inode * dir, struct dentry * dentry, int mode)
1746{
1747 handle_t *handle;
1748 struct inode * inode;
1749 struct buffer_head * dir_block;
1750 struct ext3_dir_entry_2 * de;
1751 int err, retries = 0;
1752
1753 if (dir->i_nlink >= EXT3_LINK_MAX)
1754 return -EMLINK;
1755
1756retry:
Jan Kara1f545872005-06-23 22:01:04 -07001757 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Linus Torvalds1da177e2005-04-16 15:20:36 -07001758 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3 +
Jan Kara1f545872005-06-23 22:01:04 -07001759 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001760 if (IS_ERR(handle))
1761 return PTR_ERR(handle);
1762
1763 if (IS_DIRSYNC(dir))
1764 handle->h_sync = 1;
1765
1766 inode = ext3_new_inode (handle, dir, S_IFDIR | mode);
1767 err = PTR_ERR(inode);
1768 if (IS_ERR(inode))
1769 goto out_stop;
1770
1771 inode->i_op = &ext3_dir_inode_operations;
1772 inode->i_fop = &ext3_dir_operations;
1773 inode->i_size = EXT3_I(inode)->i_disksize = inode->i_sb->s_blocksize;
1774 dir_block = ext3_bread (handle, inode, 0, 1, &err);
1775 if (!dir_block) {
Dave Hansen9a53c3a2006-09-30 23:29:03 -07001776 drop_nlink(inode); /* is this nlink == 0? */
Al Viroc38012d2008-12-30 02:02:50 -05001777 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001778 ext3_mark_inode_dirty(handle, inode);
1779 iput (inode);
1780 goto out_stop;
1781 }
1782 BUFFER_TRACE(dir_block, "get_write_access");
1783 ext3_journal_get_write_access(handle, dir_block);
1784 de = (struct ext3_dir_entry_2 *) dir_block->b_data;
1785 de->inode = cpu_to_le32(inode->i_ino);
1786 de->name_len = 1;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001787 de->rec_len = ext3_rec_len_to_disk(EXT3_DIR_REC_LEN(de->name_len));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001788 strcpy (de->name, ".");
1789 ext3_set_de_type(dir->i_sb, de, S_IFDIR);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001790 de = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001791 de->inode = cpu_to_le32(dir->i_ino);
Jan Kara7c06a8d2007-11-14 17:00:19 -08001792 de->rec_len = ext3_rec_len_to_disk(inode->i_sb->s_blocksize -
1793 EXT3_DIR_REC_LEN(1));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001794 de->name_len = 2;
1795 strcpy (de->name, "..");
1796 ext3_set_de_type(dir->i_sb, de, S_IFDIR);
1797 inode->i_nlink = 2;
1798 BUFFER_TRACE(dir_block, "call ext3_journal_dirty_metadata");
1799 ext3_journal_dirty_metadata(handle, dir_block);
1800 brelse (dir_block);
1801 ext3_mark_inode_dirty(handle, inode);
1802 err = ext3_add_entry (handle, dentry, inode);
1803 if (err) {
1804 inode->i_nlink = 0;
Al Viroc38012d2008-12-30 02:02:50 -05001805 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001806 ext3_mark_inode_dirty(handle, inode);
1807 iput (inode);
1808 goto out_stop;
1809 }
Dave Hansend8c76e62006-09-30 23:29:04 -07001810 inc_nlink(dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001811 ext3_update_dx_flag(dir);
1812 ext3_mark_inode_dirty(handle, dir);
1813 d_instantiate(dentry, inode);
Al Viroc38012d2008-12-30 02:02:50 -05001814 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001815out_stop:
1816 ext3_journal_stop(handle);
1817 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
1818 goto retry;
1819 return err;
1820}
1821
1822/*
1823 * routine to check that the specified directory is empty (for rmdir)
1824 */
1825static int empty_dir (struct inode * inode)
1826{
1827 unsigned long offset;
1828 struct buffer_head * bh;
1829 struct ext3_dir_entry_2 * de, * de1;
1830 struct super_block * sb;
1831 int err = 0;
1832
1833 sb = inode->i_sb;
1834 if (inode->i_size < EXT3_DIR_REC_LEN(1) + EXT3_DIR_REC_LEN(2) ||
1835 !(bh = ext3_bread (NULL, inode, 0, 0, &err))) {
1836 if (err)
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001837 ext3_error(inode->i_sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001838 "error %d reading directory #%lu offset 0",
1839 err, inode->i_ino);
1840 else
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001841 ext3_warning(inode->i_sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001842 "bad directory (dir #%lu) - no data block",
1843 inode->i_ino);
1844 return 1;
1845 }
1846 de = (struct ext3_dir_entry_2 *) bh->b_data;
Jan Kara7c06a8d2007-11-14 17:00:19 -08001847 de1 = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001848 if (le32_to_cpu(de->inode) != inode->i_ino ||
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001849 !le32_to_cpu(de1->inode) ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001850 strcmp (".", de->name) ||
1851 strcmp ("..", de1->name)) {
Dave Kleikampe9ad5622006-09-27 01:49:35 -07001852 ext3_warning (inode->i_sb, "empty_dir",
Linus Torvalds1da177e2005-04-16 15:20:36 -07001853 "bad directory (dir #%lu) - no `.' or `..'",
1854 inode->i_ino);
1855 brelse (bh);
1856 return 1;
1857 }
Jan Kara7c06a8d2007-11-14 17:00:19 -08001858 offset = ext3_rec_len_from_disk(de->rec_len) +
1859 ext3_rec_len_from_disk(de1->rec_len);
1860 de = ext3_next_entry(de1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001861 while (offset < inode->i_size ) {
1862 if (!bh ||
1863 (void *) de >= (void *) (bh->b_data+sb->s_blocksize)) {
1864 err = 0;
1865 brelse (bh);
1866 bh = ext3_bread (NULL, inode,
1867 offset >> EXT3_BLOCK_SIZE_BITS(sb), 0, &err);
1868 if (!bh) {
1869 if (err)
Harvey Harrisone05b6b52008-04-28 02:16:15 -07001870 ext3_error(sb, __func__,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001871 "error %d reading directory"
1872 " #%lu offset %lu",
1873 err, inode->i_ino, offset);
1874 offset += sb->s_blocksize;
1875 continue;
1876 }
1877 de = (struct ext3_dir_entry_2 *) bh->b_data;
1878 }
1879 if (!ext3_check_dir_entry("empty_dir", inode, de, bh, offset)) {
1880 de = (struct ext3_dir_entry_2 *)(bh->b_data +
1881 sb->s_blocksize);
1882 offset = (offset | (sb->s_blocksize - 1)) + 1;
1883 continue;
1884 }
1885 if (le32_to_cpu(de->inode)) {
1886 brelse (bh);
1887 return 0;
1888 }
Jan Kara7c06a8d2007-11-14 17:00:19 -08001889 offset += ext3_rec_len_from_disk(de->rec_len);
1890 de = ext3_next_entry(de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001891 }
1892 brelse (bh);
1893 return 1;
1894}
1895
1896/* ext3_orphan_add() links an unlinked or truncated inode into a list of
1897 * such inodes, starting at the superblock, in case we crash before the
1898 * file is closed/deleted, or in case the inode truncate spans multiple
1899 * transactions and the last transaction is not recovered after a crash.
1900 *
1901 * At filesystem recovery time, we walk this list deleting unlinked
1902 * inodes and truncating linked inodes in ext3_orphan_cleanup().
1903 */
1904int ext3_orphan_add(handle_t *handle, struct inode *inode)
1905{
1906 struct super_block *sb = inode->i_sb;
1907 struct ext3_iloc iloc;
1908 int err = 0, rc;
1909
1910 lock_super(sb);
1911 if (!list_empty(&EXT3_I(inode)->i_orphan))
1912 goto out_unlock;
1913
1914 /* Orphan handling is only valid for files with data blocks
1915 * being truncated, or files being unlinked. */
1916
1917 /* @@@ FIXME: Observation from aviro:
Mingming Caoae6ddcc2006-09-27 01:49:27 -07001918 * I think I can trigger J_ASSERT in ext3_orphan_add(). We block
Linus Torvalds1da177e2005-04-16 15:20:36 -07001919 * here (on lock_super()), so race with ext3_link() which might bump
1920 * ->i_nlink. For, say it, character device. Not a regular file,
1921 * not a directory, not a symlink and ->i_nlink > 0.
1922 */
1923 J_ASSERT ((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
1924 S_ISLNK(inode->i_mode)) || inode->i_nlink == 0);
1925
1926 BUFFER_TRACE(EXT3_SB(sb)->s_sbh, "get_write_access");
1927 err = ext3_journal_get_write_access(handle, EXT3_SB(sb)->s_sbh);
1928 if (err)
1929 goto out_unlock;
1930
1931 err = ext3_reserve_inode_write(handle, inode, &iloc);
1932 if (err)
1933 goto out_unlock;
1934
1935 /* Insert this inode at the head of the on-disk orphan list... */
1936 NEXT_ORPHAN(inode) = le32_to_cpu(EXT3_SB(sb)->s_es->s_last_orphan);
1937 EXT3_SB(sb)->s_es->s_last_orphan = cpu_to_le32(inode->i_ino);
1938 err = ext3_journal_dirty_metadata(handle, EXT3_SB(sb)->s_sbh);
1939 rc = ext3_mark_iloc_dirty(handle, inode, &iloc);
1940 if (!err)
1941 err = rc;
1942
1943 /* Only add to the head of the in-memory list if all the
1944 * previous operations succeeded. If the orphan_add is going to
1945 * fail (possibly taking the journal offline), we can't risk
1946 * leaving the inode on the orphan list: stray orphan-list
1947 * entries can cause panics at unmount time.
1948 *
1949 * This is safe: on error we're going to ignore the orphan list
1950 * anyway on the next recovery. */
1951 if (!err)
1952 list_add(&EXT3_I(inode)->i_orphan, &EXT3_SB(sb)->s_orphan);
1953
Eric Sandeeneee194e2006-09-27 01:49:30 -07001954 jbd_debug(4, "superblock will point to %lu\n", inode->i_ino);
1955 jbd_debug(4, "orphan inode %lu will point to %d\n",
Linus Torvalds1da177e2005-04-16 15:20:36 -07001956 inode->i_ino, NEXT_ORPHAN(inode));
1957out_unlock:
1958 unlock_super(sb);
1959 ext3_std_error(inode->i_sb, err);
1960 return err;
1961}
1962
1963/*
1964 * ext3_orphan_del() removes an unlinked or truncated inode from the list
1965 * of such inodes stored on disk, because it is finally being cleaned up.
1966 */
1967int ext3_orphan_del(handle_t *handle, struct inode *inode)
1968{
1969 struct list_head *prev;
1970 struct ext3_inode_info *ei = EXT3_I(inode);
1971 struct ext3_sb_info *sbi;
1972 unsigned long ino_next;
1973 struct ext3_iloc iloc;
1974 int err = 0;
1975
1976 lock_super(inode->i_sb);
1977 if (list_empty(&ei->i_orphan)) {
1978 unlock_super(inode->i_sb);
1979 return 0;
1980 }
1981
1982 ino_next = NEXT_ORPHAN(inode);
1983 prev = ei->i_orphan.prev;
1984 sbi = EXT3_SB(inode->i_sb);
1985
1986 jbd_debug(4, "remove inode %lu from orphan list\n", inode->i_ino);
1987
1988 list_del_init(&ei->i_orphan);
1989
1990 /* If we're on an error path, we may not have a valid
1991 * transaction handle with which to update the orphan list on
1992 * disk, but we still need to remove the inode from the linked
1993 * list in memory. */
1994 if (!handle)
1995 goto out;
1996
1997 err = ext3_reserve_inode_write(handle, inode, &iloc);
1998 if (err)
1999 goto out_err;
2000
2001 if (prev == &sbi->s_orphan) {
2002 jbd_debug(4, "superblock will point to %lu\n", ino_next);
2003 BUFFER_TRACE(sbi->s_sbh, "get_write_access");
2004 err = ext3_journal_get_write_access(handle, sbi->s_sbh);
2005 if (err)
2006 goto out_brelse;
2007 sbi->s_es->s_last_orphan = cpu_to_le32(ino_next);
2008 err = ext3_journal_dirty_metadata(handle, sbi->s_sbh);
2009 } else {
2010 struct ext3_iloc iloc2;
2011 struct inode *i_prev =
2012 &list_entry(prev, struct ext3_inode_info, i_orphan)->vfs_inode;
2013
2014 jbd_debug(4, "orphan inode %lu will point to %lu\n",
2015 i_prev->i_ino, ino_next);
2016 err = ext3_reserve_inode_write(handle, i_prev, &iloc2);
2017 if (err)
2018 goto out_brelse;
2019 NEXT_ORPHAN(i_prev) = ino_next;
2020 err = ext3_mark_iloc_dirty(handle, i_prev, &iloc2);
2021 }
2022 if (err)
2023 goto out_brelse;
2024 NEXT_ORPHAN(inode) = 0;
2025 err = ext3_mark_iloc_dirty(handle, inode, &iloc);
2026
2027out_err:
2028 ext3_std_error(inode->i_sb, err);
2029out:
2030 unlock_super(inode->i_sb);
2031 return err;
2032
2033out_brelse:
2034 brelse(iloc.bh);
2035 goto out_err;
2036}
2037
2038static int ext3_rmdir (struct inode * dir, struct dentry *dentry)
2039{
2040 int retval;
2041 struct inode * inode;
2042 struct buffer_head * bh;
2043 struct ext3_dir_entry_2 * de;
2044 handle_t *handle;
2045
2046 /* Initialize quotas before so that eventual writes go in
2047 * separate transaction */
2048 DQUOT_INIT(dentry->d_inode);
Jan Kara1f545872005-06-23 22:01:04 -07002049 handle = ext3_journal_start(dir, EXT3_DELETE_TRANS_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002050 if (IS_ERR(handle))
2051 return PTR_ERR(handle);
2052
2053 retval = -ENOENT;
Al Viro734711a2008-08-24 07:26:48 -04002054 bh = ext3_find_entry(dir, &dentry->d_name, &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002055 if (!bh)
2056 goto end_rmdir;
2057
2058 if (IS_DIRSYNC(dir))
2059 handle->h_sync = 1;
2060
2061 inode = dentry->d_inode;
2062
2063 retval = -EIO;
2064 if (le32_to_cpu(de->inode) != inode->i_ino)
2065 goto end_rmdir;
2066
2067 retval = -ENOTEMPTY;
2068 if (!empty_dir (inode))
2069 goto end_rmdir;
2070
2071 retval = ext3_delete_entry(handle, dir, de, bh);
2072 if (retval)
2073 goto end_rmdir;
2074 if (inode->i_nlink != 2)
2075 ext3_warning (inode->i_sb, "ext3_rmdir",
2076 "empty directory has nlink!=2 (%d)",
2077 inode->i_nlink);
2078 inode->i_version++;
Dave Hansence71ec32006-09-30 23:29:06 -07002079 clear_nlink(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002080 /* There's no need to set i_disksize: the fact that i_nlink is
2081 * zero will ensure that the right thing happens during any
2082 * recovery. */
2083 inode->i_size = 0;
2084 ext3_orphan_add(handle, inode);
2085 inode->i_ctime = dir->i_ctime = dir->i_mtime = CURRENT_TIME_SEC;
2086 ext3_mark_inode_dirty(handle, inode);
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002087 drop_nlink(dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002088 ext3_update_dx_flag(dir);
2089 ext3_mark_inode_dirty(handle, dir);
2090
2091end_rmdir:
2092 ext3_journal_stop(handle);
2093 brelse (bh);
2094 return retval;
2095}
2096
2097static int ext3_unlink(struct inode * dir, struct dentry *dentry)
2098{
2099 int retval;
2100 struct inode * inode;
2101 struct buffer_head * bh;
2102 struct ext3_dir_entry_2 * de;
2103 handle_t *handle;
2104
2105 /* Initialize quotas before so that eventual writes go
2106 * in separate transaction */
2107 DQUOT_INIT(dentry->d_inode);
Jan Kara1f545872005-06-23 22:01:04 -07002108 handle = ext3_journal_start(dir, EXT3_DELETE_TRANS_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002109 if (IS_ERR(handle))
2110 return PTR_ERR(handle);
2111
2112 if (IS_DIRSYNC(dir))
2113 handle->h_sync = 1;
2114
2115 retval = -ENOENT;
Al Viro734711a2008-08-24 07:26:48 -04002116 bh = ext3_find_entry(dir, &dentry->d_name, &de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002117 if (!bh)
2118 goto end_unlink;
2119
2120 inode = dentry->d_inode;
2121
2122 retval = -EIO;
2123 if (le32_to_cpu(de->inode) != inode->i_ino)
2124 goto end_unlink;
2125
2126 if (!inode->i_nlink) {
2127 ext3_warning (inode->i_sb, "ext3_unlink",
2128 "Deleting nonexistent file (%lu), %d",
2129 inode->i_ino, inode->i_nlink);
2130 inode->i_nlink = 1;
2131 }
2132 retval = ext3_delete_entry(handle, dir, de, bh);
2133 if (retval)
2134 goto end_unlink;
2135 dir->i_ctime = dir->i_mtime = CURRENT_TIME_SEC;
2136 ext3_update_dx_flag(dir);
2137 ext3_mark_inode_dirty(handle, dir);
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002138 drop_nlink(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002139 if (!inode->i_nlink)
2140 ext3_orphan_add(handle, inode);
2141 inode->i_ctime = dir->i_ctime;
2142 ext3_mark_inode_dirty(handle, inode);
2143 retval = 0;
2144
2145end_unlink:
2146 ext3_journal_stop(handle);
2147 brelse (bh);
2148 return retval;
2149}
2150
2151static int ext3_symlink (struct inode * dir,
2152 struct dentry *dentry, const char * symname)
2153{
2154 handle_t *handle;
2155 struct inode * inode;
2156 int l, err, retries = 0;
2157
2158 l = strlen(symname)+1;
2159 if (l > dir->i_sb->s_blocksize)
2160 return -ENAMETOOLONG;
2161
2162retry:
Jan Kara1f545872005-06-23 22:01:04 -07002163 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Dave Kleikampe9ad5622006-09-27 01:49:35 -07002164 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 5 +
Jan Kara1f545872005-06-23 22:01:04 -07002165 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07002166 if (IS_ERR(handle))
2167 return PTR_ERR(handle);
2168
2169 if (IS_DIRSYNC(dir))
2170 handle->h_sync = 1;
2171
2172 inode = ext3_new_inode (handle, dir, S_IFLNK|S_IRWXUGO);
2173 err = PTR_ERR(inode);
2174 if (IS_ERR(inode))
2175 goto out_stop;
2176
2177 if (l > sizeof (EXT3_I(inode)->i_data)) {
2178 inode->i_op = &ext3_symlink_inode_operations;
2179 ext3_set_aops(inode);
2180 /*
2181 * page_symlink() calls into ext3_prepare/commit_write.
2182 * We have a transaction open. All is sweetness. It also sets
2183 * i_size in generic_commit_write().
2184 */
Nick Piggin54566b22009-01-04 12:00:53 -08002185 err = __page_symlink(inode, symname, l, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002186 if (err) {
Eric Sandeen731b9a52007-02-10 01:46:16 -08002187 drop_nlink(inode);
Al Viroc38012d2008-12-30 02:02:50 -05002188 unlock_new_inode(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002189 ext3_mark_inode_dirty(handle, inode);
2190 iput (inode);
2191 goto out_stop;
2192 }
2193 } else {
2194 inode->i_op = &ext3_fast_symlink_inode_operations;
2195 memcpy((char*)&EXT3_I(inode)->i_data,symname,l);
2196 inode->i_size = l-1;
2197 }
2198 EXT3_I(inode)->i_disksize = inode->i_size;
2199 err = ext3_add_nondir(handle, dentry, inode);
2200out_stop:
2201 ext3_journal_stop(handle);
2202 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
2203 goto retry;
2204 return err;
2205}
2206
2207static int ext3_link (struct dentry * old_dentry,
2208 struct inode * dir, struct dentry *dentry)
2209{
2210 handle_t *handle;
2211 struct inode *inode = old_dentry->d_inode;
2212 int err, retries = 0;
2213
2214 if (inode->i_nlink >= EXT3_LINK_MAX)
2215 return -EMLINK;
Eric Sandeen2988a772007-02-10 01:46:16 -08002216 /*
2217 * Return -ENOENT if we've raced with unlink and i_nlink is 0. Doing
2218 * otherwise has the potential to corrupt the orphan inode list.
2219 */
2220 if (inode->i_nlink == 0)
2221 return -ENOENT;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002222
2223retry:
Jan Kara1f545872005-06-23 22:01:04 -07002224 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) +
Linus Torvalds1da177e2005-04-16 15:20:36 -07002225 EXT3_INDEX_EXTRA_TRANS_BLOCKS);
2226 if (IS_ERR(handle))
2227 return PTR_ERR(handle);
2228
2229 if (IS_DIRSYNC(dir))
2230 handle->h_sync = 1;
2231
2232 inode->i_ctime = CURRENT_TIME_SEC;
Eric Sandeen731b9a52007-02-10 01:46:16 -08002233 inc_nlink(inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002234 atomic_inc(&inode->i_count);
2235
Al Viroc38012d2008-12-30 02:02:50 -05002236 err = ext3_add_entry(handle, dentry, inode);
2237 if (!err) {
2238 ext3_mark_inode_dirty(handle, inode);
2239 d_instantiate(dentry, inode);
2240 } else {
2241 drop_nlink(inode);
2242 iput(inode);
2243 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07002244 ext3_journal_stop(handle);
2245 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries))
2246 goto retry;
2247 return err;
2248}
2249
2250#define PARENT_INO(buffer) \
Jan Kara7c06a8d2007-11-14 17:00:19 -08002251 (ext3_next_entry((struct ext3_dir_entry_2 *)(buffer))->inode)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002252
2253/*
2254 * Anybody can rename anything with this: the permission checks are left to the
2255 * higher-level routines.
2256 */
2257static int ext3_rename (struct inode * old_dir, struct dentry *old_dentry,
2258 struct inode * new_dir,struct dentry *new_dentry)
2259{
2260 handle_t *handle;
2261 struct inode * old_inode, * new_inode;
2262 struct buffer_head * old_bh, * new_bh, * dir_bh;
2263 struct ext3_dir_entry_2 * old_de, * new_de;
2264 int retval;
2265
2266 old_bh = new_bh = dir_bh = NULL;
2267
2268 /* Initialize quotas before so that eventual writes go
2269 * in separate transaction */
2270 if (new_dentry->d_inode)
2271 DQUOT_INIT(new_dentry->d_inode);
Jan Kara1f545872005-06-23 22:01:04 -07002272 handle = ext3_journal_start(old_dir, 2 *
2273 EXT3_DATA_TRANS_BLOCKS(old_dir->i_sb) +
Dave Kleikampe9ad5622006-09-27 01:49:35 -07002274 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002275 if (IS_ERR(handle))
2276 return PTR_ERR(handle);
2277
2278 if (IS_DIRSYNC(old_dir) || IS_DIRSYNC(new_dir))
2279 handle->h_sync = 1;
2280
Al Viro734711a2008-08-24 07:26:48 -04002281 old_bh = ext3_find_entry(old_dir, &old_dentry->d_name, &old_de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002282 /*
2283 * Check for inode number is _not_ due to possible IO errors.
2284 * We might rmdir the source, keep it as pwd of some process
2285 * and merrily kill the link to whatever was created under the
2286 * same name. Goodbye sticky bit ;-<
2287 */
2288 old_inode = old_dentry->d_inode;
2289 retval = -ENOENT;
2290 if (!old_bh || le32_to_cpu(old_de->inode) != old_inode->i_ino)
2291 goto end_rename;
2292
2293 new_inode = new_dentry->d_inode;
Al Viro734711a2008-08-24 07:26:48 -04002294 new_bh = ext3_find_entry(new_dir, &new_dentry->d_name, &new_de);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002295 if (new_bh) {
2296 if (!new_inode) {
2297 brelse (new_bh);
2298 new_bh = NULL;
2299 }
2300 }
2301 if (S_ISDIR(old_inode->i_mode)) {
2302 if (new_inode) {
2303 retval = -ENOTEMPTY;
2304 if (!empty_dir (new_inode))
2305 goto end_rename;
2306 }
2307 retval = -EIO;
2308 dir_bh = ext3_bread (handle, old_inode, 0, 0, &retval);
2309 if (!dir_bh)
2310 goto end_rename;
2311 if (le32_to_cpu(PARENT_INO(dir_bh->b_data)) != old_dir->i_ino)
2312 goto end_rename;
2313 retval = -EMLINK;
2314 if (!new_inode && new_dir!=old_dir &&
2315 new_dir->i_nlink >= EXT3_LINK_MAX)
2316 goto end_rename;
2317 }
2318 if (!new_bh) {
2319 retval = ext3_add_entry (handle, new_dentry, old_inode);
2320 if (retval)
2321 goto end_rename;
2322 } else {
2323 BUFFER_TRACE(new_bh, "get write access");
2324 ext3_journal_get_write_access(handle, new_bh);
2325 new_de->inode = cpu_to_le32(old_inode->i_ino);
2326 if (EXT3_HAS_INCOMPAT_FEATURE(new_dir->i_sb,
2327 EXT3_FEATURE_INCOMPAT_FILETYPE))
2328 new_de->file_type = old_de->file_type;
2329 new_dir->i_version++;
Jan Kara0b230762008-04-28 02:16:12 -07002330 new_dir->i_ctime = new_dir->i_mtime = CURRENT_TIME_SEC;
2331 ext3_mark_inode_dirty(handle, new_dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002332 BUFFER_TRACE(new_bh, "call ext3_journal_dirty_metadata");
2333 ext3_journal_dirty_metadata(handle, new_bh);
2334 brelse(new_bh);
2335 new_bh = NULL;
2336 }
2337
2338 /*
2339 * Like most other Unix systems, set the ctime for inodes on a
2340 * rename.
2341 */
2342 old_inode->i_ctime = CURRENT_TIME_SEC;
2343 ext3_mark_inode_dirty(handle, old_inode);
2344
2345 /*
2346 * ok, that's it
2347 */
2348 if (le32_to_cpu(old_de->inode) != old_inode->i_ino ||
2349 old_de->name_len != old_dentry->d_name.len ||
2350 strncmp(old_de->name, old_dentry->d_name.name, old_de->name_len) ||
2351 (retval = ext3_delete_entry(handle, old_dir,
2352 old_de, old_bh)) == -ENOENT) {
2353 /* old_de could have moved from under us during htree split, so
2354 * make sure that we are deleting the right entry. We might
2355 * also be pointing to a stale entry in the unused part of
2356 * old_bh so just checking inum and the name isn't enough. */
2357 struct buffer_head *old_bh2;
2358 struct ext3_dir_entry_2 *old_de2;
2359
Al Viro734711a2008-08-24 07:26:48 -04002360 old_bh2 = ext3_find_entry(old_dir, &old_dentry->d_name,
2361 &old_de2);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002362 if (old_bh2) {
2363 retval = ext3_delete_entry(handle, old_dir,
2364 old_de2, old_bh2);
2365 brelse(old_bh2);
2366 }
2367 }
2368 if (retval) {
2369 ext3_warning(old_dir->i_sb, "ext3_rename",
2370 "Deleting old file (%lu), %d, error=%d",
2371 old_dir->i_ino, old_dir->i_nlink, retval);
2372 }
2373
2374 if (new_inode) {
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002375 drop_nlink(new_inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002376 new_inode->i_ctime = CURRENT_TIME_SEC;
2377 }
2378 old_dir->i_ctime = old_dir->i_mtime = CURRENT_TIME_SEC;
2379 ext3_update_dx_flag(old_dir);
2380 if (dir_bh) {
2381 BUFFER_TRACE(dir_bh, "get_write_access");
2382 ext3_journal_get_write_access(handle, dir_bh);
2383 PARENT_INO(dir_bh->b_data) = cpu_to_le32(new_dir->i_ino);
2384 BUFFER_TRACE(dir_bh, "call ext3_journal_dirty_metadata");
2385 ext3_journal_dirty_metadata(handle, dir_bh);
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002386 drop_nlink(old_dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002387 if (new_inode) {
Dave Hansen9a53c3a2006-09-30 23:29:03 -07002388 drop_nlink(new_inode);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002389 } else {
Dave Hansend8c76e62006-09-30 23:29:04 -07002390 inc_nlink(new_dir);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002391 ext3_update_dx_flag(new_dir);
2392 ext3_mark_inode_dirty(handle, new_dir);
2393 }
2394 }
2395 ext3_mark_inode_dirty(handle, old_dir);
2396 if (new_inode) {
2397 ext3_mark_inode_dirty(handle, new_inode);
2398 if (!new_inode->i_nlink)
2399 ext3_orphan_add(handle, new_inode);
2400 }
2401 retval = 0;
2402
2403end_rename:
2404 brelse (dir_bh);
2405 brelse (old_bh);
2406 brelse (new_bh);
2407 ext3_journal_stop(handle);
2408 return retval;
2409}
2410
2411/*
2412 * directories can handle most operations...
2413 */
Arjan van de Ven754661f2007-02-12 00:55:38 -08002414const struct inode_operations ext3_dir_inode_operations = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002415 .create = ext3_create,
2416 .lookup = ext3_lookup,
2417 .link = ext3_link,
2418 .unlink = ext3_unlink,
2419 .symlink = ext3_symlink,
2420 .mkdir = ext3_mkdir,
2421 .rmdir = ext3_rmdir,
2422 .mknod = ext3_mknod,
2423 .rename = ext3_rename,
2424 .setattr = ext3_setattr,
2425#ifdef CONFIG_EXT3_FS_XATTR
2426 .setxattr = generic_setxattr,
2427 .getxattr = generic_getxattr,
2428 .listxattr = ext3_listxattr,
2429 .removexattr = generic_removexattr,
2430#endif
2431 .permission = ext3_permission,
2432};
2433
Arjan van de Ven754661f2007-02-12 00:55:38 -08002434const struct inode_operations ext3_special_inode_operations = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07002435 .setattr = ext3_setattr,
2436#ifdef CONFIG_EXT3_FS_XATTR
2437 .setxattr = generic_setxattr,
2438 .getxattr = generic_getxattr,
2439 .listxattr = ext3_listxattr,
2440 .removexattr = generic_removexattr,
2441#endif
2442 .permission = ext3_permission,
Mingming Caoae6ddcc2006-09-27 01:49:27 -07002443};