← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to fs/ext4/namei.c

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
Import upstream version 3.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
fs/ext4/namei.c
 
1
/*
 
2
 *  linux/fs/ext4/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
 
18
 *      for B-tree directories by Theodore Ts'o (tytso@mit.edu), 1998
 
19
 *  Hash Tree Directory indexing (c)
 
20
 *      Daniel Phillips, 2001
 
21
 *  Hash Tree Directory indexing porting
 
22
 *      Christopher Li, 2002
 
23
 *  Hash Tree Directory indexing cleanup
 
24
 *      Theodore Ts'o, 2002
 
25
 */
 
26
 
 
27
#include <linux/fs.h>
 
28
#include <linux/pagemap.h>
 
29
#include <linux/jbd2.h>
 
30
#include <linux/time.h>
 
31
#include <linux/fcntl.h>
 
32
#include <linux/stat.h>
 
33
#include <linux/string.h>
 
34
#include <linux/quotaops.h>
 
35
#include <linux/buffer_head.h>
 
36
#include <linux/bio.h>
 
37
#include "ext4.h"
 
38
#include "ext4_jbd2.h"
 
39
 
 
40
#include "xattr.h"
 
41
#include "acl.h"
 
42
 
 
43
#include <trace/events/ext4.h>
 
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
 
 
52
static struct buffer_head *ext4_append(handle_t *handle,
 
53
                                        struct inode *inode,
 
54
                                        ext4_lblk_t *block, int *err)
 
55
{
 
56
        struct buffer_head *bh;
 
57
 
 
58
        *block = inode->i_size >> inode->i_sb->s_blocksize_bits;
 
59
 
 
60
        bh = ext4_bread(handle, inode, *block, 1, err);
 
61
        if (bh) {
 
62
                inode->i_size += inode->i_sb->s_blocksize;
 
63
                EXT4_I(inode)->i_disksize = inode->i_size;
 
64
                *err = ext4_journal_get_write_access(handle, bh);
 
65
                if (*err) {
 
66
                        brelse(bh);
 
67
                        bh = NULL;
 
68
                }
 
69
        }
 
70
        return bh;
 
71
}
 
72
 
 
73
#ifndef assert
 
74
#define assert(test) J_ASSERT(test)
 
75
#endif
 
76
 
 
77
#ifdef DX_DEBUG
 
78
#define dxtrace(command) command
 
79
#else
 
80
#define dxtrace(command)
 
81
#endif
 
82
 
 
83
struct fake_dirent
 
84
{
 
85
        __le32 inode;
 
86
        __le16 rec_len;
 
87
        u8 name_len;
 
88
        u8 file_type;
 
89
};
 
90
 
 
91
struct dx_countlimit
 
92
{
 
93
        __le16 limit;
 
94
        __le16 count;
 
95
};
 
96
 
 
97
struct dx_entry
 
98
{
 
99
        __le32 hash;
 
100
        __le32 block;
 
101
};
 
102
 
 
103
/*
 
104
 * dx_root_info is laid out so that if it should somehow get overlaid by a
 
105
 * dirent the two low bits of the hash version will be zero.  Therefore, the
 
106
 * hash version mod 4 should never be 0.  Sincerely, the paranoia department.
 
107
 */
 
108
 
 
109
struct dx_root
 
110
{
 
111
        struct fake_dirent dot;
 
112
        char dot_name[4];
 
113
        struct fake_dirent dotdot;
 
114
        char dotdot_name[4];
 
115
        struct dx_root_info
 
116
        {
 
117
                __le32 reserved_zero;
 
118
                u8 hash_version;
 
119
                u8 info_length; /* 8 */
 
120
                u8 indirect_levels;
 
121
                u8 unused_flags;
 
122
        }
 
123
        info;
 
124
        struct dx_entry entries[0];
 
125
};
 
126
 
 
127
struct dx_node
 
128
{
 
129
        struct fake_dirent fake;
 
130
        struct dx_entry entries[0];
 
131
};
 
132
 
 
133
 
 
134
struct dx_frame
 
135
{
 
136
        struct buffer_head *bh;
 
137
        struct dx_entry *entries;
 
138
        struct dx_entry *at;
 
139
};
 
140
 
 
141
struct dx_map_entry
 
142
{
 
143
        u32 hash;
 
144
        u16 offs;
 
145
        u16 size;
 
146
};
 
147
 
 
148
static inline ext4_lblk_t dx_get_block(struct dx_entry *entry);
 
149
static void dx_set_block(struct dx_entry *entry, ext4_lblk_t value);
 
150
static inline unsigned dx_get_hash(struct dx_entry *entry);
 
151
static void dx_set_hash(struct dx_entry *entry, unsigned value);
 
152
static unsigned dx_get_count(struct dx_entry *entries);
 
153
static unsigned dx_get_limit(struct dx_entry *entries);
 
154
static void dx_set_count(struct dx_entry *entries, unsigned value);
 
155
static void dx_set_limit(struct dx_entry *entries, unsigned value);
 
156
static unsigned dx_root_limit(struct inode *dir, unsigned infosize);
 
157
static unsigned dx_node_limit(struct inode *dir);
 
158
static struct dx_frame *dx_probe(const struct qstr *d_name,
 
159
                                 struct inode *dir,
 
160
                                 struct dx_hash_info *hinfo,
 
161
                                 struct dx_frame *frame,
 
162
                                 int *err);
 
163
static void dx_release(struct dx_frame *frames);
 
164
static int dx_make_map(struct ext4_dir_entry_2 *de, unsigned blocksize,
 
165
                       struct dx_hash_info *hinfo, struct dx_map_entry map[]);
 
166
static void dx_sort_map(struct dx_map_entry *map, unsigned count);
 
167
static struct ext4_dir_entry_2 *dx_move_dirents(char *from, char *to,
 
168
                struct dx_map_entry *offsets, int count, unsigned blocksize);
 
169
static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize);
 
170
static void dx_insert_block(struct dx_frame *frame,
 
171
                                        u32 hash, ext4_lblk_t block);
 
172
static int ext4_htree_next_block(struct inode *dir, __u32 hash,
 
173
                                 struct dx_frame *frame,
 
174
                                 struct dx_frame *frames,
 
175
                                 __u32 *start_hash);
 
176
static struct buffer_head * ext4_dx_find_entry(struct inode *dir,
 
177
                const struct qstr *d_name,
 
178
                struct ext4_dir_entry_2 **res_dir,
 
179
                int *err);
 
180
static int ext4_dx_add_entry(handle_t *handle, struct dentry *dentry,
 
181
                             struct inode *inode);
 
182
 
 
183
/*
 
184
 * p is at least 6 bytes before the end of page
 
185
 */
 
186
static inline struct ext4_dir_entry_2 *
 
187
ext4_next_entry(struct ext4_dir_entry_2 *p, unsigned long blocksize)
 
188
{
 
189
        return (struct ext4_dir_entry_2 *)((char *)p +
 
190
                ext4_rec_len_from_disk(p->rec_len, blocksize));
 
191
}
 
192
 
 
193
/*
 
194
 * Future: use high four bits of block for coalesce-on-delete flags
 
195
 * Mask them off for now.
 
196
 */
 
197
 
 
198
static inline ext4_lblk_t dx_get_block(struct dx_entry *entry)
 
199
{
 
200
        return le32_to_cpu(entry->block) & 0x00ffffff;
 
201
}
 
202
 
 
203
static inline void dx_set_block(struct dx_entry *entry, ext4_lblk_t value)
 
204
{
 
205
        entry->block = cpu_to_le32(value);
 
206
}
 
207
 
 
208
static inline unsigned dx_get_hash(struct dx_entry *entry)
 
209
{
 
210
        return le32_to_cpu(entry->hash);
 
211
}
 
212
 
 
213
static inline void dx_set_hash(struct dx_entry *entry, unsigned value)
 
214
{
 
215
        entry->hash = cpu_to_le32(value);
 
216
}
 
217
 
 
218
static inline unsigned dx_get_count(struct dx_entry *entries)
 
219
{
 
220
        return le16_to_cpu(((struct dx_countlimit *) entries)->count);
 
221
}
 
222
 
 
223
static inline unsigned dx_get_limit(struct dx_entry *entries)
 
224
{
 
225
        return le16_to_cpu(((struct dx_countlimit *) entries)->limit);
 
226
}
 
227
 
 
228
static inline void dx_set_count(struct dx_entry *entries, unsigned value)
 
229
{
 
230
        ((struct dx_countlimit *) entries)->count = cpu_to_le16(value);
 
231
}
 
232
 
 
233
static inline void dx_set_limit(struct dx_entry *entries, unsigned value)
 
234
{
 
235
        ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
 
236
}
 
237
 
 
238
static inline unsigned dx_root_limit(struct inode *dir, unsigned infosize)
 
239
{
 
240
        unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(1) -
 
241
                EXT4_DIR_REC_LEN(2) - infosize;
 
242
        return entry_space / sizeof(struct dx_entry);
 
243
}
 
244
 
 
245
static inline unsigned dx_node_limit(struct inode *dir)
 
246
{
 
247
        unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(0);
 
248
        return entry_space / sizeof(struct dx_entry);
 
249
}
 
250
 
 
251
/*
 
252
 * Debug
 
253
 */
 
254
#ifdef DX_DEBUG
 
255
static void dx_show_index(char * label, struct dx_entry *entries)
 
256
{
 
257
        int i, n = dx_get_count (entries);
 
258
        printk(KERN_DEBUG "%s index ", label);
 
259
        for (i = 0; i < n; i++) {
 
260
                printk("%x->%lu ", i ? dx_get_hash(entries + i) :
 
261
                                0, (unsigned long)dx_get_block(entries + i));
 
262
        }
 
263
        printk("\n");
 
264
}
 
265
 
 
266
struct stats
 
267
{
 
268
        unsigned names;
 
269
        unsigned space;
 
270
        unsigned bcount;
 
271
};
 
272
 
 
273
static struct stats dx_show_leaf(struct dx_hash_info *hinfo, struct ext4_dir_entry_2 *de,
 
274
                                 int size, int show_names)
 
275
{
 
276
        unsigned names = 0, space = 0;
 
277
        char *base = (char *) de;
 
278
        struct dx_hash_info h = *hinfo;
 
279
 
 
280
        printk("names: ");
 
281
        while ((char *) de < base + size)
 
282
        {
 
283
                if (de->inode)
 
284
                {
 
285
                        if (show_names)
 
286
                        {
 
287
                                int len = de->name_len;
 
288
                                char *name = de->name;
 
289
                                while (len--) printk("%c", *name++);
 
290
                                ext4fs_dirhash(de->name, de->name_len, &h);
 
291
                                printk(":%x.%u ", h.hash,
 
292
                                       (unsigned) ((char *) de - base));
 
293
                        }
 
294
                        space += EXT4_DIR_REC_LEN(de->name_len);
 
295
                        names++;
 
296
                }
 
297
                de = ext4_next_entry(de, size);
 
298
        }
 
299
        printk("(%i)\n", names);
 
300
        return (struct stats) { names, space, 1 };
 
301
}
 
302
 
 
303
struct stats dx_show_entries(struct dx_hash_info *hinfo, struct inode *dir,
 
304
                             struct dx_entry *entries, int levels)
 
305
{
 
306
        unsigned blocksize = dir->i_sb->s_blocksize;
 
307
        unsigned count = dx_get_count(entries), names = 0, space = 0, i;
 
308
        unsigned bcount = 0;
 
309
        struct buffer_head *bh;
 
310
        int err;
 
311
        printk("%i indexed blocks...\n", count);
 
312
        for (i = 0; i < count; i++, entries++)
 
313
        {
 
314
                ext4_lblk_t block = dx_get_block(entries);
 
315
                ext4_lblk_t hash  = i ? dx_get_hash(entries): 0;
 
316
                u32 range = i < count - 1? (dx_get_hash(entries + 1) - hash): ~hash;
 
317
                struct stats stats;
 
318
                printk("%s%3u:%03u hash %8x/%8x ",levels?"":"   ", i, block, hash, range);
 
319
                if (!(bh = ext4_bread (NULL,dir, block, 0,&err))) continue;
 
320
                stats = levels?
 
321
                   dx_show_entries(hinfo, dir, ((struct dx_node *) bh->b_data)->entries, levels - 1):
 
322
                   dx_show_leaf(hinfo, (struct ext4_dir_entry_2 *) bh->b_data, blocksize, 0);
 
323
                names += stats.names;
 
324
                space += stats.space;
 
325
                bcount += stats.bcount;
 
326
                brelse(bh);
 
327
        }
 
328
        if (bcount)
 
329
                printk(KERN_DEBUG "%snames %u, fullness %u (%u%%)\n",
 
330
                       levels ? "" : "   ", names, space/bcount,
 
331
                       (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
 */
 
345
static struct dx_frame *
 
346
dx_probe(const struct qstr *d_name, struct inode *dir,
 
347
         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;
 
357
        if (!(bh = ext4_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) {
 
363
                ext4_warning(dir->i_sb, "Unrecognised inode hash code %d",
 
364
                             root->info.hash_version);
 
365
                brelse(bh);
 
366
                *err = ERR_BAD_DX_DIR;
 
367
                goto fail;
 
368
        }
 
369
        hinfo->hash_version = root->info.hash_version;
 
370
        if (hinfo->hash_version <= DX_HASH_TEA)
 
371
                hinfo->hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
 
372
        hinfo->seed = EXT4_SB(dir->i_sb)->s_hash_seed;
 
373
        if (d_name)
 
374
                ext4fs_dirhash(d_name->name, d_name->len, hinfo);
 
375
        hash = hinfo->hash;
 
376
 
 
377
        if (root->info.unused_flags & 1) {
 
378
                ext4_warning(dir->i_sb, "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) {
 
386
                ext4_warning(dir->i_sb, "Unimplemented inode hash depth: %#06x",
 
387
                             root->info.indirect_levels);
 
388
                brelse(bh);
 
389
                *err = ERR_BAD_DX_DIR;
 
390
                goto fail;
 
391
        }
 
392
 
 
393
        entries = (struct dx_entry *) (((char *)&root->info) +
 
394
                                       root->info.info_length);
 
395
 
 
396
        if (dx_get_limit(entries) != dx_root_limit(dir,
 
397
                                                   root->info.info_length)) {
 
398
                ext4_warning(dir->i_sb, "dx entry: limit != root limit");
 
399
                brelse(bh);
 
400
                *err = ERR_BAD_DX_DIR;
 
401
                goto fail;
 
402
        }
 
403
 
 
404
        dxtrace(printk("Look up %x", hash));
 
405
        while (1)
 
406
        {
 
407
                count = dx_get_count(entries);
 
408
                if (!count || count > dx_get_limit(entries)) {
 
409
                        ext4_warning(dir->i_sb,
 
410
                                     "dx entry: no count or count > limit");
 
411
                        brelse(bh);
 
412
                        *err = ERR_BAD_DX_DIR;
 
413
                        goto fail2;
 
414
                }
 
415
 
 
416
                p = entries + 1;
 
417
                q = entries + count - 1;
 
418
                while (p <= q)
 
419
                {
 
420
                        m = p + (q - p)/2;
 
421
                        dxtrace(printk("."));
 
422
                        if (dx_get_hash(m) > hash)
 
423
                                q = m - 1;
 
424
                        else
 
425
                                p = m + 1;
 
426
                }
 
427
 
 
428
                if (0) // linear search cross check
 
429
                {
 
430
                        unsigned n = count - 1;
 
431
                        at = entries;
 
432
                        while (n--)
 
433
                        {
 
434
                                dxtrace(printk(","));
 
435
                                if (dx_get_hash(++at) > hash)
 
436
                                {
 
437
                                        at--;
 
438
                                        break;
 
439
                                }
 
440
                        }
 
441
                        assert (at == p - 1);
 
442
                }
 
443
 
 
444
                at = p - 1;
 
445
                dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
 
446
                frame->bh = bh;
 
447
                frame->entries = entries;
 
448
                frame->at = at;
 
449
                if (!indirect--) return frame;
 
450
                if (!(bh = ext4_bread (NULL,dir, dx_get_block(at), 0, err)))
 
451
                        goto fail2;
 
452
                at = entries = ((struct dx_node *) bh->b_data)->entries;
 
453
                if (dx_get_limit(entries) != dx_node_limit (dir)) {
 
454
                        ext4_warning(dir->i_sb,
 
455
                                     "dx entry: limit != node limit");
 
456
                        brelse(bh);
 
457
                        *err = ERR_BAD_DX_DIR;
 
458
                        goto fail2;
 
459
                }
 
460
                frame++;
 
461
                frame->bh = NULL;
 
462
        }
 
463
fail2:
 
464
        while (frame >= frame_in) {
 
465
                brelse(frame->bh);
 
466
                frame--;
 
467
        }
 
468
fail:
 
469
        if (*err == ERR_BAD_DX_DIR)
 
470
                ext4_warning(dir->i_sb,
 
471
                             "Corrupt dir inode %ld, running e2fsck is "
 
472
                             "recommended.", dir->i_ino);
 
473
        return NULL;
 
474
}
 
475
 
 
476
static void dx_release (struct dx_frame *frames)
 
477
{
 
478
        if (frames[0].bh == NULL)
 
479
                return;
 
480
 
 
481
        if (((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels)
 
482
                brelse(frames[1].bh);
 
483
        brelse(frames[0].bh);
 
484
}
 
485
 
 
486
/*
 
487
 * This function increments the frame pointer to search the next leaf
 
488
 * block, and reads in the necessary intervening nodes if the search
 
489
 * should be necessary.  Whether or not the search is necessary is
 
490
 * controlled by the hash parameter.  If the hash value is even, then
 
491
 * the search is only continued if the next block starts with that
 
492
 * hash value.  This is used if we are searching for a specific file.
 
493
 *
 
494
 * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
 
495
 *
 
496
 * This function returns 1 if the caller should continue to search,
 
497
 * or 0 if it should not.  If there is an error reading one of the
 
498
 * index blocks, it will a negative error code.
 
499
 *
 
500
 * If start_hash is non-null, it will be filled in with the starting
 
501
 * hash of the next page.
 
502
 */
 
503
static int ext4_htree_next_block(struct inode *dir, __u32 hash,
 
504
                                 struct dx_frame *frame,
 
505
                                 struct dx_frame *frames,
 
506
                                 __u32 *start_hash)
 
507
{
 
508
        struct dx_frame *p;
 
509
        struct buffer_head *bh;
 
510
        int err, num_frames = 0;
 
511
        __u32 bhash;
 
512
 
 
513
        p = frame;
 
514
        /*
 
515
         * Find the next leaf page by incrementing the frame pointer.
 
516
         * If we run out of entries in the interior node, loop around and
 
517
         * increment pointer in the parent node.  When we break out of
 
518
         * this loop, num_frames indicates the number of interior
 
519
         * nodes need to be read.
 
520
         */
 
521
        while (1) {
 
522
                if (++(p->at) < p->entries + dx_get_count(p->entries))
 
523
                        break;
 
524
                if (p == frames)
 
525
                        return 0;
 
526
                num_frames++;
 
527
                p--;
 
528
        }
 
529
 
 
530
        /*
 
531
         * If the hash is 1, then continue only if the next page has a
 
532
         * continuation hash of any value.  This is used for readdir
 
533
         * handling.  Otherwise, check to see if the hash matches the
 
534
         * desired contiuation hash.  If it doesn't, return since
 
535
         * there's no point to read in the successive index pages.
 
536
         */
 
537
        bhash = dx_get_hash(p->at);
 
538
        if (start_hash)
 
539
                *start_hash = bhash;
 
540
        if ((hash & 1) == 0) {
 
541
                if ((bhash & ~1) != hash)
 
542
                        return 0;
 
543
        }
 
544
        /*
 
545
         * If the hash is HASH_NB_ALWAYS, we always go to the next
 
546
         * block so no check is necessary
 
547
         */
 
548
        while (num_frames--) {
 
549
                if (!(bh = ext4_bread(NULL, dir, dx_get_block(p->at),
 
550
                                      0, &err)))
 
551
                        return err; /* Failure */
 
552
                p++;
 
553
                brelse(p->bh);
 
554
                p->bh = bh;
 
555
                p->at = p->entries = ((struct dx_node *) bh->b_data)->entries;
 
556
        }
 
557
        return 1;
 
558
}
 
559
 
 
560
 
 
561
/*
 
562
 * This function fills a red-black tree with information from a
 
563
 * directory block.  It returns the number directory entries loaded
 
564
 * into the tree.  If there is an error it is returned in err.
 
565
 */
 
566
static int htree_dirblock_to_tree(struct file *dir_file,
 
567
                                  struct inode *dir, ext4_lblk_t block,
 
568
                                  struct dx_hash_info *hinfo,
 
569
                                  __u32 start_hash, __u32 start_minor_hash)
 
570
{
 
571
        struct buffer_head *bh;
 
572
        struct ext4_dir_entry_2 *de, *top;
 
573
        int err, count = 0;
 
574
 
 
575
        dxtrace(printk(KERN_INFO "In htree dirblock_to_tree: block %lu\n",
 
576
                                                        (unsigned long)block));
 
577
        if (!(bh = ext4_bread (NULL, dir, block, 0, &err)))
 
578
                return err;
 
579
 
 
580
        de = (struct ext4_dir_entry_2 *) bh->b_data;
 
581
        top = (struct ext4_dir_entry_2 *) ((char *) de +
 
582
                                           dir->i_sb->s_blocksize -
 
583
                                           EXT4_DIR_REC_LEN(0));
 
584
        for (; de < top; de = ext4_next_entry(de, dir->i_sb->s_blocksize)) {
 
585
                if (ext4_check_dir_entry(dir, NULL, de, bh,
 
586
                                (block<<EXT4_BLOCK_SIZE_BITS(dir->i_sb))
 
587
                                         + ((char *)de - bh->b_data))) {
 
588
                        /* On error, skip the f_pos to the next block. */
 
589
                        dir_file->f_pos = (dir_file->f_pos |
 
590
                                        (dir->i_sb->s_blocksize - 1)) + 1;
 
591
                        brelse(bh);
 
592
                        return count;
 
593
                }
 
594
                ext4fs_dirhash(de->name, de->name_len, hinfo);
 
595
                if ((hinfo->hash < start_hash) ||
 
596
                    ((hinfo->hash == start_hash) &&
 
597
                     (hinfo->minor_hash < start_minor_hash)))
 
598
                        continue;
 
599
                if (de->inode == 0)
 
600
                        continue;
 
601
                if ((err = ext4_htree_store_dirent(dir_file,
 
602
                                   hinfo->hash, hinfo->minor_hash, de)) != 0) {
 
603
                        brelse(bh);
 
604
                        return err;
 
605
                }
 
606
                count++;
 
607
        }
 
608
        brelse(bh);
 
609
        return count;
 
610
}
 
611
 
 
612
 
 
613
/*
 
614
 * This function fills a red-black tree with information from a
 
615
 * directory.  We start scanning the directory in hash order, starting
 
616
 * at start_hash and start_minor_hash.
 
617
 *
 
618
 * This function returns the number of entries inserted into the tree,
 
619
 * or a negative error code.
 
620
 */
 
621
int ext4_htree_fill_tree(struct file *dir_file, __u32 start_hash,
 
622
                         __u32 start_minor_hash, __u32 *next_hash)
 
623
{
 
624
        struct dx_hash_info hinfo;
 
625
        struct ext4_dir_entry_2 *de;
 
626
        struct dx_frame frames[2], *frame;
 
627
        struct inode *dir;
 
628
        ext4_lblk_t block;
 
629
        int count = 0;
 
630
        int ret, err;
 
631
        __u32 hashval;
 
632
 
 
633
        dxtrace(printk(KERN_DEBUG "In htree_fill_tree, start hash: %x:%x\n",
 
634
                       start_hash, start_minor_hash));
 
635
        dir = dir_file->f_path.dentry->d_inode;
 
636
        if (!(ext4_test_inode_flag(dir, EXT4_INODE_INDEX))) {
 
637
                hinfo.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
 
638
                if (hinfo.hash_version <= DX_HASH_TEA)
 
639
                        hinfo.hash_version +=
 
640
                                EXT4_SB(dir->i_sb)->s_hash_unsigned;
 
641
                hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
 
642
                count = htree_dirblock_to_tree(dir_file, dir, 0, &hinfo,
 
643
                                               start_hash, start_minor_hash);
 
644
                *next_hash = ~0;
 
645
                return count;
 
646
        }
 
647
        hinfo.hash = start_hash;
 
648
        hinfo.minor_hash = 0;
 
649
        frame = dx_probe(NULL, dir, &hinfo, frames, &err);
 
650
        if (!frame)
 
651
                return err;
 
652
 
 
653
        /* Add '.' and '..' from the htree header */
 
654
        if (!start_hash && !start_minor_hash) {
 
655
                de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
 
656
                if ((err = ext4_htree_store_dirent(dir_file, 0, 0, de)) != 0)
 
657
                        goto errout;
 
658
                count++;
 
659
        }
 
660
        if (start_hash < 2 || (start_hash ==2 && start_minor_hash==0)) {
 
661
                de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
 
662
                de = ext4_next_entry(de, dir->i_sb->s_blocksize);
 
663
                if ((err = ext4_htree_store_dirent(dir_file, 2, 0, de)) != 0)
 
664
                        goto errout;
 
665
                count++;
 
666
        }
 
667
 
 
668
        while (1) {
 
669
                block = dx_get_block(frame->at);
 
670
                ret = htree_dirblock_to_tree(dir_file, dir, block, &hinfo,
 
671
                                             start_hash, start_minor_hash);
 
672
                if (ret < 0) {
 
673
                        err = ret;
 
674
                        goto errout;
 
675
                }
 
676
                count += ret;
 
677
                hashval = ~0;
 
678
                ret = ext4_htree_next_block(dir, HASH_NB_ALWAYS,
 
679
                                            frame, frames, &hashval);
 
680
                *next_hash = hashval;
 
681
                if (ret < 0) {
 
682
                        err = ret;
 
683
                        goto errout;
 
684
                }
 
685
                /*
 
686
                 * Stop if:  (a) there are no more entries, or
 
687
                 * (b) we have inserted at least one entry and the
 
688
                 * next hash value is not a continuation
 
689
                 */
 
690
                if ((ret == 0) ||
 
691
                    (count && ((hashval & 1) == 0)))
 
692
                        break;
 
693
        }
 
694
        dx_release(frames);
 
695
        dxtrace(printk(KERN_DEBUG "Fill tree: returned %d entries, "
 
696
                       "next hash: %x\n", count, *next_hash));
 
697
        return count;
 
698
errout:
 
699
        dx_release(frames);
 
700
        return (err);
 
701
}
 
702
 
 
703
 
 
704
/*
 
705
 * Directory block splitting, compacting
 
706
 */
 
707
 
 
708
/*
 
709
 * Create map of hash values, offsets, and sizes, stored at end of block.
 
710
 * Returns number of entries mapped.
 
711
 */
 
712
static int dx_make_map(struct ext4_dir_entry_2 *de, unsigned blocksize,
 
713
                       struct dx_hash_info *hinfo,
 
714
                       struct dx_map_entry *map_tail)
 
715
{
 
716
        int count = 0;
 
717
        char *base = (char *) de;
 
718
        struct dx_hash_info h = *hinfo;
 
719
 
 
720
        while ((char *) de < base + blocksize) {
 
721
                if (de->name_len && de->inode) {
 
722
                        ext4fs_dirhash(de->name, de->name_len, &h);
 
723
                        map_tail--;
 
724
                        map_tail->hash = h.hash;
 
725
                        map_tail->offs = ((char *) de - base)>>2;
 
726
                        map_tail->size = le16_to_cpu(de->rec_len);
 
727
                        count++;
 
728
                        cond_resched();
 
729
                }
 
730
                /* XXX: do we need to check rec_len == 0 case? -Chris */
 
731
                de = ext4_next_entry(de, blocksize);
 
732
        }
 
733
        return count;
 
734
}
 
735
 
 
736
/* Sort map by hash value */
 
737
static void dx_sort_map (struct dx_map_entry *map, unsigned count)
 
738
{
 
739
        struct dx_map_entry *p, *q, *top = map + count - 1;
 
740
        int more;
 
741
        /* Combsort until bubble sort doesn't suck */
 
742
        while (count > 2) {
 
743
                count = count*10/13;
 
744
                if (count - 9 < 2) /* 9, 10 -> 11 */
 
745
                        count = 11;
 
746
                for (p = top, q = p - count; q >= map; p--, q--)
 
747
                        if (p->hash < q->hash)
 
748
                                swap(*p, *q);
 
749
        }
 
750
        /* Garden variety bubble sort */
 
751
        do {
 
752
                more = 0;
 
753
                q = top;
 
754
                while (q-- > map) {
 
755
                        if (q[1].hash >= q[0].hash)
 
756
                                continue;
 
757
                        swap(*(q+1), *q);
 
758
                        more = 1;
 
759
                }
 
760
        } while(more);
 
761
}
 
762
 
 
763
static void dx_insert_block(struct dx_frame *frame, u32 hash, ext4_lblk_t 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
}
 
776
 
 
777
static void ext4_update_dx_flag(struct inode *inode)
 
778
{
 
779
        if (!EXT4_HAS_COMPAT_FEATURE(inode->i_sb,
 
780
                                     EXT4_FEATURE_COMPAT_DIR_INDEX))
 
781
                ext4_clear_inode_flag(inode, EXT4_INODE_INDEX);
 
782
}
 
783
 
 
784
/*
 
785
 * NOTE! unlike strncmp, ext4_match returns 1 for success, 0 for failure.
 
786
 *
 
787
 * `len <= EXT4_NAME_LEN' is guaranteed by caller.
 
788
 * `de != NULL' is guaranteed by caller.
 
789
 */
 
790
static inline int ext4_match (int len, const char * const name,
 
791
                              struct ext4_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
 */
 
803
static inline int search_dirblock(struct buffer_head *bh,
 
804
                                  struct inode *dir,
 
805
                                  const struct qstr *d_name,
 
806
                                  unsigned int offset,
 
807
                                  struct ext4_dir_entry_2 ** res_dir)
 
808
{
 
809
        struct ext4_dir_entry_2 * de;
 
810
        char * dlimit;
 
811
        int de_len;
 
812
        const char *name = d_name->name;
 
813
        int namelen = d_name->len;
 
814
 
 
815
        de = (struct ext4_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
                    ext4_match (namelen, name, de)) {
 
823
                        /* found a match - just to be sure, do a full check */
 
824
                        if (ext4_check_dir_entry(dir, NULL, de, bh, offset))
 
825
                                return -1;
 
826
                        *res_dir = de;
 
827
                        return 1;
 
828
                }
 
829
                /* prevent looping on a bad block */
 
830
                de_len = ext4_rec_len_from_disk(de->rec_len,
 
831
                                                dir->i_sb->s_blocksize);
 
832
                if (de_len <= 0)
 
833
                        return -1;
 
834
                offset += de_len;
 
835
                de = (struct ext4_dir_entry_2 *) ((char *) de + de_len);
 
836
        }
 
837
        return 0;
 
838
}
 
839
 
 
840
 
 
841
/*
 
842
 *      ext4_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
 */
 
852
static struct buffer_head * ext4_find_entry (struct inode *dir,
 
853
                                        const struct qstr *d_name,
 
854
                                        struct ext4_dir_entry_2 ** res_dir)
 
855
{
 
856
        struct super_block *sb;
 
857
        struct buffer_head *bh_use[NAMEI_RA_SIZE];
 
858
        struct buffer_head *bh, *ret = NULL;
 
859
        ext4_lblk_t start, block, b;
 
860
        const u8 *name = d_name->name;
 
861
        int ra_max = 0;         /* Number of bh's in the readahead
 
862
                                   buffer, bh_use[] */
 
863
        int ra_ptr = 0;         /* Current index into readahead
 
864
                                   buffer */
 
865
        int num = 0;
 
866
        ext4_lblk_t  nblocks;
 
867
        int i, err;
 
868
        int namelen;
 
869
 
 
870
        *res_dir = NULL;
 
871
        sb = dir->i_sb;
 
872
        namelen = d_name->len;
 
873
        if (namelen > EXT4_NAME_LEN)
 
874
                return NULL;
 
875
        if ((namelen <= 2) && (name[0] == '.') &&
 
876
            (name[1] == '.' || name[1] == '\0')) {
 
877
                /*
 
878
                 * "." or ".." will only be in the first block
 
879
                 * NFS may look up ".."; "." should be handled by the VFS
 
880
                 */
 
881
                block = start = 0;
 
882
                nblocks = 1;
 
883
                goto restart;
 
884
        }
 
885
        if (is_dx(dir)) {
 
886
                bh = ext4_dx_find_entry(dir, d_name, res_dir, &err);
 
887
                /*
 
888
                 * On success, or if the error was file not found,
 
889
                 * return.  Otherwise, fall back to doing a search the
 
890
                 * old fashioned way.
 
891
                 */
 
892
                if (bh || (err != ERR_BAD_DX_DIR))
 
893
                        return bh;
 
894
                dxtrace(printk(KERN_DEBUG "ext4_find_entry: dx failed, "
 
895
                               "falling back\n"));
 
896
        }
 
897
        nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
 
898
        start = EXT4_I(dir)->i_dir_start_lookup;
 
899
        if (start >= nblocks)
 
900
                start = 0;
 
901
        block = start;
 
902
restart:
 
903
        do {
 
904
                /*
 
905
                 * We deal with the read-ahead logic here.
 
906
                 */
 
907
                if (ra_ptr >= ra_max) {
 
908
                        /* Refill the readahead buffer */
 
909
                        ra_ptr = 0;
 
910
                        b = block;
 
911
                        for (ra_max = 0; ra_max < NAMEI_RA_SIZE; ra_max++) {
 
912
                                /*
 
913
                                 * Terminate if we reach the end of the
 
914
                                 * directory and must wrap, or if our
 
915
                                 * search has finished at this block.
 
916
                                 */
 
917
                                if (b >= nblocks || (num && block == start)) {
 
918
                                        bh_use[ra_max] = NULL;
 
919
                                        break;
 
920
                                }
 
921
                                num++;
 
922
                                bh = ext4_getblk(NULL, dir, b++, 0, &err);
 
923
                                bh_use[ra_max] = bh;
 
924
                                if (bh)
 
925
                                        ll_rw_block(READ | REQ_META | REQ_PRIO,
 
926
                                                    1, &bh);
 
927
                        }
 
928
                }
 
929
                if ((bh = bh_use[ra_ptr++]) == NULL)
 
930
                        goto next;
 
931
                wait_on_buffer(bh);
 
932
                if (!buffer_uptodate(bh)) {
 
933
                        /* read error, skip block & hope for the best */
 
934
                        EXT4_ERROR_INODE(dir, "reading directory lblock %lu",
 
935
                                         (unsigned long) block);
 
936
                        brelse(bh);
 
937
                        goto next;
 
938
                }
 
939
                i = search_dirblock(bh, dir, d_name,
 
940
                            block << EXT4_BLOCK_SIZE_BITS(sb), res_dir);
 
941
                if (i == 1) {
 
942
                        EXT4_I(dir)->i_dir_start_lookup = block;
 
943
                        ret = bh;
 
944
                        goto cleanup_and_exit;
 
945
                } else {
 
946
                        brelse(bh);
 
947
                        if (i < 0)
 
948
                                goto cleanup_and_exit;
 
949
                }
 
950
        next:
 
951
                if (++block >= nblocks)
 
952
                        block = 0;
 
953
        } while (block != start);
 
954
 
 
955
        /*
 
956
         * If the directory has grown while we were searching, then
 
957
         * search the last part of the directory before giving up.
 
958
         */
 
959
        block = nblocks;
 
960
        nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
 
961
        if (block < nblocks) {
 
962
                start = 0;
 
963
                goto restart;
 
964
        }
 
965
 
 
966
cleanup_and_exit:
 
967
        /* Clean up the read-ahead blocks */
 
968
        for (; ra_ptr < ra_max; ra_ptr++)
 
969
                brelse(bh_use[ra_ptr]);
 
970
        return ret;
 
971
}
 
972
 
 
973
static struct buffer_head * ext4_dx_find_entry(struct inode *dir, const struct qstr *d_name,
 
974
                       struct ext4_dir_entry_2 **res_dir, int *err)
 
975
{
 
976
        struct super_block * sb = dir->i_sb;
 
977
        struct dx_hash_info     hinfo;
 
978
        struct dx_frame frames[2], *frame;
 
979
        struct buffer_head *bh;
 
980
        ext4_lblk_t block;
 
981
        int retval;
 
982
 
 
983
        if (!(frame = dx_probe(d_name, dir, &hinfo, frames, err)))
 
984
                return NULL;
 
985
        do {
 
986
                block = dx_get_block(frame->at);
 
987
                if (!(bh = ext4_bread(NULL, dir, block, 0, err)))
 
988
                        goto errout;
 
989
 
 
990
                retval = search_dirblock(bh, dir, d_name,
 
991
                                         block << EXT4_BLOCK_SIZE_BITS(sb),
 
992
                                         res_dir);
 
993
                if (retval == 1) {      /* Success! */
 
994
                        dx_release(frames);
 
995
                        return bh;
 
996
                }
 
997
                brelse(bh);
 
998
                if (retval == -1) {
 
999
                        *err = ERR_BAD_DX_DIR;
 
1000
                        goto errout;
 
1001
                }
 
1002
 
 
1003
                /* Check to see if we should continue to search */
 
1004
                retval = ext4_htree_next_block(dir, hinfo.hash, frame,
 
1005
                                               frames, NULL);
 
1006
                if (retval < 0) {
 
1007
                        ext4_warning(sb,
 
1008
                             "error reading index page in directory #%lu",
 
1009
                             dir->i_ino);
 
1010
                        *err = retval;
 
1011
                        goto errout;
 
1012
                }
 
1013
        } while (retval == 1);
 
1014
 
 
1015
        *err = -ENOENT;
 
1016
errout:
 
1017
        dxtrace(printk(KERN_DEBUG "%s not found\n", d_name->name));
 
1018
        dx_release (frames);
 
1019
        return NULL;
 
1020
}
 
1021
 
 
1022
static struct dentry *ext4_lookup(struct inode *dir, struct dentry *dentry, struct nameidata *nd)
 
1023
{
 
1024
        struct inode *inode;
 
1025
        struct ext4_dir_entry_2 *de;
 
1026
        struct buffer_head *bh;
 
1027
 
 
1028
        if (dentry->d_name.len > EXT4_NAME_LEN)
 
1029
                return ERR_PTR(-ENAMETOOLONG);
 
1030
 
 
1031
        bh = ext4_find_entry(dir, &dentry->d_name, &de);
 
1032
        inode = NULL;
 
1033
        if (bh) {
 
1034
                __u32 ino = le32_to_cpu(de->inode);
 
1035
                brelse(bh);
 
1036
                if (!ext4_valid_inum(dir->i_sb, ino)) {
 
1037
                        EXT4_ERROR_INODE(dir, "bad inode number: %u", ino);
 
1038
                        return ERR_PTR(-EIO);
 
1039
                }
 
1040
                inode = ext4_iget(dir->i_sb, ino);
 
1041
                if (inode == ERR_PTR(-ESTALE)) {
 
1042
                        EXT4_ERROR_INODE(dir,
 
1043
                                         "deleted inode referenced: %u",
 
1044
                                         ino);
 
1045
                        return ERR_PTR(-EIO);
 
1046
                }
 
1047
        }
 
1048
        return d_splice_alias(inode, dentry);
 
1049
}
 
1050
 
 
1051
 
 
1052
struct dentry *ext4_get_parent(struct dentry *child)
 
1053
{
 
1054
        __u32 ino;
 
1055
        static const struct qstr dotdot = {
 
1056
                .name = "..",
 
1057
                .len = 2,
 
1058
        };
 
1059
        struct ext4_dir_entry_2 * de;
 
1060
        struct buffer_head *bh;
 
1061
 
 
1062
        bh = ext4_find_entry(child->d_inode, &dotdot, &de);
 
1063
        if (!bh)
 
1064
                return ERR_PTR(-ENOENT);
 
1065
        ino = le32_to_cpu(de->inode);
 
1066
        brelse(bh);
 
1067
 
 
1068
        if (!ext4_valid_inum(child->d_inode->i_sb, ino)) {
 
1069
                EXT4_ERROR_INODE(child->d_inode,
 
1070
                                 "bad parent inode number: %u", ino);
 
1071
                return ERR_PTR(-EIO);
 
1072
        }
 
1073
 
 
1074
        return d_obtain_alias(ext4_iget(child->d_inode->i_sb, ino));
 
1075
}
 
1076
 
 
1077
#define S_SHIFT 12
 
1078
static unsigned char ext4_type_by_mode[S_IFMT >> S_SHIFT] = {
 
1079
        [S_IFREG >> S_SHIFT]    = EXT4_FT_REG_FILE,
 
1080
        [S_IFDIR >> S_SHIFT]    = EXT4_FT_DIR,
 
1081
        [S_IFCHR >> S_SHIFT]    = EXT4_FT_CHRDEV,
 
1082
        [S_IFBLK >> S_SHIFT]    = EXT4_FT_BLKDEV,
 
1083
        [S_IFIFO >> S_SHIFT]    = EXT4_FT_FIFO,
 
1084
        [S_IFSOCK >> S_SHIFT]   = EXT4_FT_SOCK,
 
1085
        [S_IFLNK >> S_SHIFT]    = EXT4_FT_SYMLINK,
 
1086
};
 
1087
 
 
1088
static inline void ext4_set_de_type(struct super_block *sb,
 
1089
                                struct ext4_dir_entry_2 *de,
 
1090
                                umode_t mode) {
 
1091
        if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_FILETYPE))
 
1092
                de->file_type = ext4_type_by_mode[(mode & S_IFMT)>>S_SHIFT];
 
1093
}
 
1094
 
 
1095
/*
 
1096
 * Move count entries from end of map between two memory locations.
 
1097
 * Returns pointer to last entry moved.
 
1098
 */
 
1099
static struct ext4_dir_entry_2 *
 
1100
dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count,
 
1101
                unsigned blocksize)
 
1102
{
 
1103
        unsigned rec_len = 0;
 
1104
 
 
1105
        while (count--) {
 
1106
                struct ext4_dir_entry_2 *de = (struct ext4_dir_entry_2 *)
 
1107
                                                (from + (map->offs<<2));
 
1108
                rec_len = EXT4_DIR_REC_LEN(de->name_len);
 
1109
                memcpy (to, de, rec_len);
 
1110
                ((struct ext4_dir_entry_2 *) to)->rec_len =
 
1111
                                ext4_rec_len_to_disk(rec_len, blocksize);
 
1112
                de->inode = 0;
 
1113
                map++;
 
1114
                to += rec_len;
 
1115
        }
 
1116
        return (struct ext4_dir_entry_2 *) (to - rec_len);
 
1117
}
 
1118
 
 
1119
/*
 
1120
 * Compact each dir entry in the range to the minimal rec_len.
 
1121
 * Returns pointer to last entry in range.
 
1122
 */
 
1123
static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize)
 
1124
{
 
1125
        struct ext4_dir_entry_2 *next, *to, *prev, *de = (struct ext4_dir_entry_2 *) base;
 
1126
        unsigned rec_len = 0;
 
1127
 
 
1128
        prev = to = de;
 
1129
        while ((char*)de < base + blocksize) {
 
1130
                next = ext4_next_entry(de, blocksize);
 
1131
                if (de->inode && de->name_len) {
 
1132
                        rec_len = EXT4_DIR_REC_LEN(de->name_len);
 
1133
                        if (de > to)
 
1134
                                memmove(to, de, rec_len);
 
1135
                        to->rec_len = ext4_rec_len_to_disk(rec_len, blocksize);
 
1136
                        prev = to;
 
1137
                        to = (struct ext4_dir_entry_2 *) (((char *) to) + rec_len);
 
1138
                }
 
1139
                de = next;
 
1140
        }
 
1141
        return prev;
 
1142
}
 
1143
 
 
1144
/*
 
1145
 * Split a full leaf block to make room for a new dir entry.
 
1146
 * Allocate a new block, and move entries so that they are approx. equally full.
 
1147
 * Returns pointer to de in block into which the new entry will be inserted.
 
1148
 */
 
1149
static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
 
1150
                        struct buffer_head **bh,struct dx_frame *frame,
 
1151
                        struct dx_hash_info *hinfo, int *error)
 
1152
{
 
1153
        unsigned blocksize = dir->i_sb->s_blocksize;
 
1154
        unsigned count, continued;
 
1155
        struct buffer_head *bh2;
 
1156
        ext4_lblk_t newblock;
 
1157
        u32 hash2;
 
1158
        struct dx_map_entry *map;
 
1159
        char *data1 = (*bh)->b_data, *data2;
 
1160
        unsigned split, move, size;
 
1161
        struct ext4_dir_entry_2 *de = NULL, *de2;
 
1162
        int     err = 0, i;
 
1163
 
 
1164
        bh2 = ext4_append (handle, dir, &newblock, &err);
 
1165
        if (!(bh2)) {
 
1166
                brelse(*bh);
 
1167
                *bh = NULL;
 
1168
                goto errout;
 
1169
        }
 
1170
 
 
1171
        BUFFER_TRACE(*bh, "get_write_access");
 
1172
        err = ext4_journal_get_write_access(handle, *bh);
 
1173
        if (err)
 
1174
                goto journal_error;
 
1175
 
 
1176
        BUFFER_TRACE(frame->bh, "get_write_access");
 
1177
        err = ext4_journal_get_write_access(handle, frame->bh);
 
1178
        if (err)
 
1179
                goto journal_error;
 
1180
 
 
1181
        data2 = bh2->b_data;
 
1182
 
 
1183
        /* create map in the end of data2 block */
 
1184
        map = (struct dx_map_entry *) (data2 + blocksize);
 
1185
        count = dx_make_map((struct ext4_dir_entry_2 *) data1,
 
1186
                             blocksize, hinfo, map);
 
1187
        map -= count;
 
1188
        dx_sort_map(map, count);
 
1189
        /* Split the existing block in the middle, size-wise */
 
1190
        size = 0;
 
1191
        move = 0;
 
1192
        for (i = count-1; i >= 0; i--) {
 
1193
                /* is more than half of this entry in 2nd half of the block? */
 
1194
                if (size + map[i].size/2 > blocksize/2)
 
1195
                        break;
 
1196
                size += map[i].size;
 
1197
                move++;
 
1198
        }
 
1199
        /* map index at which we will split */
 
1200
        split = count - move;
 
1201
        hash2 = map[split].hash;
 
1202
        continued = hash2 == map[split - 1].hash;
 
1203
        dxtrace(printk(KERN_INFO "Split block %lu at %x, %i/%i\n",
 
1204
                        (unsigned long)dx_get_block(frame->at),
 
1205
                                        hash2, split, count-split));
 
1206
 
 
1207
        /* Fancy dance to stay within two buffers */
 
1208
        de2 = dx_move_dirents(data1, data2, map + split, count - split, blocksize);
 
1209
        de = dx_pack_dirents(data1, blocksize);
 
1210
        de->rec_len = ext4_rec_len_to_disk(data1 + blocksize - (char *) de,
 
1211
                                           blocksize);
 
1212
        de2->rec_len = ext4_rec_len_to_disk(data2 + blocksize - (char *) de2,
 
1213
                                            blocksize);
 
1214
        dxtrace(dx_show_leaf (hinfo, (struct ext4_dir_entry_2 *) data1, blocksize, 1));
 
1215
        dxtrace(dx_show_leaf (hinfo, (struct ext4_dir_entry_2 *) data2, blocksize, 1));
 
1216
 
 
1217
        /* Which block gets the new entry? */
 
1218
        if (hinfo->hash >= hash2)
 
1219
        {
 
1220
                swap(*bh, bh2);
 
1221
                de = de2;
 
1222
        }
 
1223
        dx_insert_block(frame, hash2 + continued, newblock);
 
1224
        err = ext4_handle_dirty_metadata(handle, dir, bh2);
 
1225
        if (err)
 
1226
                goto journal_error;
 
1227
        err = ext4_handle_dirty_metadata(handle, dir, frame->bh);
 
1228
        if (err)
 
1229
                goto journal_error;
 
1230
        brelse(bh2);
 
1231
        dxtrace(dx_show_index("frame", frame->entries));
 
1232
        return de;
 
1233
 
 
1234
journal_error:
 
1235
        brelse(*bh);
 
1236
        brelse(bh2);
 
1237
        *bh = NULL;
 
1238
        ext4_std_error(dir->i_sb, err);
 
1239
errout:
 
1240
        *error = err;
 
1241
        return NULL;
 
1242
}
 
1243
 
 
1244
/*
 
1245
 * Add a new entry into a directory (leaf) block.  If de is non-NULL,
 
1246
 * it points to a directory entry which is guaranteed to be large
 
1247
 * enough for new directory entry.  If de is NULL, then
 
1248
 * add_dirent_to_buf will attempt search the directory block for
 
1249
 * space.  It will return -ENOSPC if no space is available, and -EIO
 
1250
 * and -EEXIST if directory entry already exists.
 
1251
 */
 
1252
static int add_dirent_to_buf(handle_t *handle, struct dentry *dentry,
 
1253
                             struct inode *inode, struct ext4_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 int    offset = 0;
 
1260
        unsigned int    blocksize = dir->i_sb->s_blocksize;
 
1261
        unsigned short  reclen;
 
1262
        int             nlen, rlen, err;
 
1263
        char            *top;
 
1264
 
 
1265
        reclen = EXT4_DIR_REC_LEN(namelen);
 
1266
        if (!de) {
 
1267
                de = (struct ext4_dir_entry_2 *)bh->b_data;
 
1268
                top = bh->b_data + blocksize - reclen;
 
1269
                while ((char *) de <= top) {
 
1270
                        if (ext4_check_dir_entry(dir, NULL, de, bh, offset))
 
1271
                                return -EIO;
 
1272
                        if (ext4_match(namelen, name, de))
 
1273
                                return -EEXIST;
 
1274
                        nlen = EXT4_DIR_REC_LEN(de->name_len);
 
1275
                        rlen = ext4_rec_len_from_disk(de->rec_len, blocksize);
 
1276
                        if ((de->inode? rlen - nlen: rlen) >= reclen)
 
1277
                                break;
 
1278
                        de = (struct ext4_dir_entry_2 *)((char *)de + rlen);
 
1279
                        offset += rlen;
 
1280
                }
 
1281
                if ((char *) de > top)
 
1282
                        return -ENOSPC;
 
1283
        }
 
1284
        BUFFER_TRACE(bh, "get_write_access");
 
1285
        err = ext4_journal_get_write_access(handle, bh);
 
1286
        if (err) {
 
1287
                ext4_std_error(dir->i_sb, err);
 
1288
                return err;
 
1289
        }
 
1290
 
 
1291
        /* By now the buffer is marked for journaling */
 
1292
        nlen = EXT4_DIR_REC_LEN(de->name_len);
 
1293
        rlen = ext4_rec_len_from_disk(de->rec_len, blocksize);
 
1294
        if (de->inode) {
 
1295
                struct ext4_dir_entry_2 *de1 = (struct ext4_dir_entry_2 *)((char *)de + nlen);
 
1296
                de1->rec_len = ext4_rec_len_to_disk(rlen - nlen, blocksize);
 
1297
                de->rec_len = ext4_rec_len_to_disk(nlen, blocksize);
 
1298
                de = de1;
 
1299
        }
 
1300
        de->file_type = EXT4_FT_UNKNOWN;
 
1301
        if (inode) {
 
1302
                de->inode = cpu_to_le32(inode->i_ino);
 
1303
                ext4_set_de_type(dir->i_sb, de, inode->i_mode);
 
1304
        } else
 
1305
                de->inode = 0;
 
1306
        de->name_len = namelen;
 
1307
        memcpy(de->name, name, namelen);
 
1308
        /*
 
1309
         * XXX shouldn't update any times until successful
 
1310
         * completion of syscall, but too many callers depend
 
1311
         * on this.
 
1312
         *
 
1313
         * XXX similarly, too many callers depend on
 
1314
         * ext4_new_inode() setting the times, but error
 
1315
         * recovery deletes the inode, so the worst that can
 
1316
         * happen is that the times are slightly out of date
 
1317
         * and/or different from the directory change time.
 
1318
         */
 
1319
        dir->i_mtime = dir->i_ctime = ext4_current_time(dir);
 
1320
        ext4_update_dx_flag(dir);
 
1321
        dir->i_version++;
 
1322
        ext4_mark_inode_dirty(handle, dir);
 
1323
        BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
 
1324
        err = ext4_handle_dirty_metadata(handle, dir, bh);
 
1325
        if (err)
 
1326
                ext4_std_error(dir->i_sb, err);
 
1327
        return 0;
 
1328
}
 
1329
 
 
1330
/*
 
1331
 * This converts a one block unindexed directory to a 3 block indexed
 
1332
 * directory, and adds the dentry to the indexed directory.
 
1333
 */
 
1334
static int make_indexed_dir(handle_t *handle, struct dentry *dentry,
 
1335
                            struct inode *inode, struct buffer_head *bh)
 
1336
{
 
1337
        struct inode    *dir = dentry->d_parent->d_inode;
 
1338
        const char      *name = dentry->d_name.name;
 
1339
        int             namelen = dentry->d_name.len;
 
1340
        struct buffer_head *bh2;
 
1341
        struct dx_root  *root;
 
1342
        struct dx_frame frames[2], *frame;
 
1343
        struct dx_entry *entries;
 
1344
        struct ext4_dir_entry_2 *de, *de2;
 
1345
        char            *data1, *top;
 
1346
        unsigned        len;
 
1347
        int             retval;
 
1348
        unsigned        blocksize;
 
1349
        struct dx_hash_info hinfo;
 
1350
        ext4_lblk_t  block;
 
1351
        struct fake_dirent *fde;
 
1352
 
 
1353
        blocksize =  dir->i_sb->s_blocksize;
 
1354
        dxtrace(printk(KERN_DEBUG "Creating index: inode %lu\n", dir->i_ino));
 
1355
        retval = ext4_journal_get_write_access(handle, bh);
 
1356
        if (retval) {
 
1357
                ext4_std_error(dir->i_sb, retval);
 
1358
                brelse(bh);
 
1359
                return retval;
 
1360
        }
 
1361
        root = (struct dx_root *) bh->b_data;
 
1362
 
 
1363
        /* The 0th block becomes the root, move the dirents out */
 
1364
        fde = &root->dotdot;
 
1365
        de = (struct ext4_dir_entry_2 *)((char *)fde +
 
1366
                ext4_rec_len_from_disk(fde->rec_len, blocksize));
 
1367
        if ((char *) de >= (((char *) root) + blocksize)) {
 
1368
                EXT4_ERROR_INODE(dir, "invalid rec_len for '..'");
 
1369
                brelse(bh);
 
1370
                return -EIO;
 
1371
        }
 
1372
        len = ((char *) root) + blocksize - (char *) de;
 
1373
 
 
1374
        /* Allocate new block for the 0th block's dirents */
 
1375
        bh2 = ext4_append(handle, dir, &block, &retval);
 
1376
        if (!(bh2)) {
 
1377
                brelse(bh);
 
1378
                return retval;
 
1379
        }
 
1380
        ext4_set_inode_flag(dir, EXT4_INODE_INDEX);
 
1381
        data1 = bh2->b_data;
 
1382
 
 
1383
        memcpy (data1, de, len);
 
1384
        de = (struct ext4_dir_entry_2 *) data1;
 
1385
        top = data1 + len;
 
1386
        while ((char *)(de2 = ext4_next_entry(de, blocksize)) < top)
 
1387
                de = de2;
 
1388
        de->rec_len = ext4_rec_len_to_disk(data1 + blocksize - (char *) de,
 
1389
                                           blocksize);
 
1390
        /* Initialize the root; the dot dirents already exist */
 
1391
        de = (struct ext4_dir_entry_2 *) (&root->dotdot);
 
1392
        de->rec_len = ext4_rec_len_to_disk(blocksize - EXT4_DIR_REC_LEN(2),
 
1393
                                           blocksize);
 
1394
        memset (&root->info, 0, sizeof(root->info));
 
1395
        root->info.info_length = sizeof(root->info);
 
1396
        root->info.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
 
1397
        entries = root->entries;
 
1398
        dx_set_block(entries, 1);
 
1399
        dx_set_count(entries, 1);
 
1400
        dx_set_limit(entries, dx_root_limit(dir, sizeof(root->info)));
 
1401
 
 
1402
        /* Initialize as for dx_probe */
 
1403
        hinfo.hash_version = root->info.hash_version;
 
1404
        if (hinfo.hash_version <= DX_HASH_TEA)
 
1405
                hinfo.hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
 
1406
        hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
 
1407
        ext4fs_dirhash(name, namelen, &hinfo);
 
1408
        frame = frames;
 
1409
        frame->entries = entries;
 
1410
        frame->at = entries;
 
1411
        frame->bh = bh;
 
1412
        bh = bh2;
 
1413
 
 
1414
        ext4_handle_dirty_metadata(handle, dir, frame->bh);
 
1415
        ext4_handle_dirty_metadata(handle, dir, bh);
 
1416
 
 
1417
        de = do_split(handle,dir, &bh, frame, &hinfo, &retval);
 
1418
        if (!de) {
 
1419
                /*
 
1420
                 * Even if the block split failed, we have to properly write
 
1421
                 * out all the changes we did so far. Otherwise we can end up
 
1422
                 * with corrupted filesystem.
 
1423
                 */
 
1424
                ext4_mark_inode_dirty(handle, dir);
 
1425
                dx_release(frames);
 
1426
                return retval;
 
1427
        }
 
1428
        dx_release(frames);
 
1429
 
 
1430
        retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
 
1431
        brelse(bh);
 
1432
        return retval;
 
1433
}
 
1434
 
 
1435
/*
 
1436
 *      ext4_add_entry()
 
1437
 *
 
1438
 * adds a file entry to the specified directory, using the same
 
1439
 * semantics as ext4_find_entry(). It returns NULL if it failed.
 
1440
 *
 
1441
 * NOTE!! The inode part of 'de' is left at 0 - which means you
 
1442
 * may not sleep between calling this and putting something into
 
1443
 * the entry, as someone else might have used it while you slept.
 
1444
 */
 
1445
static int ext4_add_entry(handle_t *handle, struct dentry *dentry,
 
1446
                          struct inode *inode)
 
1447
{
 
1448
        struct inode *dir = dentry->d_parent->d_inode;
 
1449
        struct buffer_head *bh;
 
1450
        struct ext4_dir_entry_2 *de;
 
1451
        struct super_block *sb;
 
1452
        int     retval;
 
1453
        int     dx_fallback=0;
 
1454
        unsigned blocksize;
 
1455
        ext4_lblk_t block, blocks;
 
1456
 
 
1457
        sb = dir->i_sb;
 
1458
        blocksize = sb->s_blocksize;
 
1459
        if (!dentry->d_name.len)
 
1460
                return -EINVAL;
 
1461
        if (is_dx(dir)) {
 
1462
                retval = ext4_dx_add_entry(handle, dentry, inode);
 
1463
                if (!retval || (retval != ERR_BAD_DX_DIR))
 
1464
                        return retval;
 
1465
                ext4_clear_inode_flag(dir, EXT4_INODE_INDEX);
 
1466
                dx_fallback++;
 
1467
                ext4_mark_inode_dirty(handle, dir);
 
1468
        }
 
1469
        blocks = dir->i_size >> sb->s_blocksize_bits;
 
1470
        for (block = 0; block < blocks; block++) {
 
1471
                bh = ext4_bread(handle, dir, block, 0, &retval);
 
1472
                if(!bh)
 
1473
                        return retval;
 
1474
                retval = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
 
1475
                if (retval != -ENOSPC) {
 
1476
                        brelse(bh);
 
1477
                        return retval;
 
1478
                }
 
1479
 
 
1480
                if (blocks == 1 && !dx_fallback &&
 
1481
                    EXT4_HAS_COMPAT_FEATURE(sb, EXT4_FEATURE_COMPAT_DIR_INDEX))
 
1482
                        return make_indexed_dir(handle, dentry, inode, bh);
 
1483
                brelse(bh);
 
1484
        }
 
1485
        bh = ext4_append(handle, dir, &block, &retval);
 
1486
        if (!bh)
 
1487
                return retval;
 
1488
        de = (struct ext4_dir_entry_2 *) bh->b_data;
 
1489
        de->inode = 0;
 
1490
        de->rec_len = ext4_rec_len_to_disk(blocksize, blocksize);
 
1491
        retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
 
1492
        brelse(bh);
 
1493
        if (retval == 0)
 
1494
                ext4_set_inode_state(inode, EXT4_STATE_NEWENTRY);
 
1495
        return retval;
 
1496
}
 
1497
 
 
1498
/*
 
1499
 * Returns 0 for success, or a negative error value
 
1500
 */
 
1501
static int ext4_dx_add_entry(handle_t *handle, struct dentry *dentry,
 
1502
                             struct inode *inode)
 
1503
{
 
1504
        struct dx_frame frames[2], *frame;
 
1505
        struct dx_entry *entries, *at;
 
1506
        struct dx_hash_info hinfo;
 
1507
        struct buffer_head *bh;
 
1508
        struct inode *dir = dentry->d_parent->d_inode;
 
1509
        struct super_block *sb = dir->i_sb;
 
1510
        struct ext4_dir_entry_2 *de;
 
1511
        int err;
 
1512
 
 
1513
        frame = dx_probe(&dentry->d_name, dir, &hinfo, frames, &err);
 
1514
        if (!frame)
 
1515
                return err;
 
1516
        entries = frame->entries;
 
1517
        at = frame->at;
 
1518
 
 
1519
        if (!(bh = ext4_bread(handle,dir, dx_get_block(frame->at), 0, &err)))
 
1520
                goto cleanup;
 
1521
 
 
1522
        BUFFER_TRACE(bh, "get_write_access");
 
1523
        err = ext4_journal_get_write_access(handle, bh);
 
1524
        if (err)
 
1525
                goto journal_error;
 
1526
 
 
1527
        err = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
 
1528
        if (err != -ENOSPC)
 
1529
                goto cleanup;
 
1530
 
 
1531
        /* Block full, should compress but for now just split */
 
1532
        dxtrace(printk(KERN_DEBUG "using %u of %u node entries\n",
 
1533
                       dx_get_count(entries), dx_get_limit(entries)));
 
1534
        /* Need to split index? */
 
1535
        if (dx_get_count(entries) == dx_get_limit(entries)) {
 
1536
                ext4_lblk_t newblock;
 
1537
                unsigned icount = dx_get_count(entries);
 
1538
                int levels = frame - frames;
 
1539
                struct dx_entry *entries2;
 
1540
                struct dx_node *node2;
 
1541
                struct buffer_head *bh2;
 
1542
 
 
1543
                if (levels && (dx_get_count(frames->entries) ==
 
1544
                               dx_get_limit(frames->entries))) {
 
1545
                        ext4_warning(sb, "Directory index full!");
 
1546
                        err = -ENOSPC;
 
1547
                        goto cleanup;
 
1548
                }
 
1549
                bh2 = ext4_append (handle, dir, &newblock, &err);
 
1550
                if (!(bh2))
 
1551
                        goto cleanup;
 
1552
                node2 = (struct dx_node *)(bh2->b_data);
 
1553
                entries2 = node2->entries;
 
1554
                memset(&node2->fake, 0, sizeof(struct fake_dirent));
 
1555
                node2->fake.rec_len = ext4_rec_len_to_disk(sb->s_blocksize,
 
1556
                                                           sb->s_blocksize);
 
1557
                BUFFER_TRACE(frame->bh, "get_write_access");
 
1558
                err = ext4_journal_get_write_access(handle, frame->bh);
 
1559
                if (err)
 
1560
                        goto journal_error;
 
1561
                if (levels) {
 
1562
                        unsigned icount1 = icount/2, icount2 = icount - icount1;
 
1563
                        unsigned hash2 = dx_get_hash(entries + icount1);
 
1564
                        dxtrace(printk(KERN_DEBUG "Split index %i/%i\n",
 
1565
                                       icount1, icount2));
 
1566
 
 
1567
                        BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
 
1568
                        err = ext4_journal_get_write_access(handle,
 
1569
                                                             frames[0].bh);
 
1570
                        if (err)
 
1571
                                goto journal_error;
 
1572
 
 
1573
                        memcpy((char *) entries2, (char *) (entries + icount1),
 
1574
                               icount2 * sizeof(struct dx_entry));
 
1575
                        dx_set_count(entries, icount1);
 
1576
                        dx_set_count(entries2, icount2);
 
1577
                        dx_set_limit(entries2, dx_node_limit(dir));
 
1578
 
 
1579
                        /* Which index block gets the new entry? */
 
1580
                        if (at - entries >= icount1) {
 
1581
                                frame->at = at = at - entries - icount1 + entries2;
 
1582
                                frame->entries = entries = entries2;
 
1583
                                swap(frame->bh, bh2);
 
1584
                        }
 
1585
                        dx_insert_block(frames + 0, hash2, newblock);
 
1586
                        dxtrace(dx_show_index("node", frames[1].entries));
 
1587
                        dxtrace(dx_show_index("node",
 
1588
                               ((struct dx_node *) bh2->b_data)->entries));
 
1589
                        err = ext4_handle_dirty_metadata(handle, dir, bh2);
 
1590
                        if (err)
 
1591
                                goto journal_error;
 
1592
                        brelse (bh2);
 
1593
                } else {
 
1594
                        dxtrace(printk(KERN_DEBUG
 
1595
                                       "Creating second level index...\n"));
 
1596
                        memcpy((char *) entries2, (char *) entries,
 
1597
                               icount * sizeof(struct dx_entry));
 
1598
                        dx_set_limit(entries2, dx_node_limit(dir));
 
1599
 
 
1600
                        /* Set up root */
 
1601
                        dx_set_count(entries, 1);
 
1602
                        dx_set_block(entries + 0, newblock);
 
1603
                        ((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
 
1604
 
 
1605
                        /* Add new access path frame */
 
1606
                        frame = frames + 1;
 
1607
                        frame->at = at = at - entries + entries2;
 
1608
                        frame->entries = entries = entries2;
 
1609
                        frame->bh = bh2;
 
1610
                        err = ext4_journal_get_write_access(handle,
 
1611
                                                             frame->bh);
 
1612
                        if (err)
 
1613
                                goto journal_error;
 
1614
                }
 
1615
                err = ext4_handle_dirty_metadata(handle, dir, frames[0].bh);
 
1616
                if (err) {
 
1617
                        ext4_std_error(inode->i_sb, err);
 
1618
                        goto cleanup;
 
1619
                }
 
1620
        }
 
1621
        de = do_split(handle, dir, &bh, frame, &hinfo, &err);
 
1622
        if (!de)
 
1623
                goto cleanup;
 
1624
        err = add_dirent_to_buf(handle, dentry, inode, de, bh);
 
1625
        goto cleanup;
 
1626
 
 
1627
journal_error:
 
1628
        ext4_std_error(dir->i_sb, err);
 
1629
cleanup:
 
1630
        if (bh)
 
1631
                brelse(bh);
 
1632
        dx_release(frames);
 
1633
        return err;
 
1634
}
 
1635
 
 
1636
/*
 
1637
 * ext4_delete_entry deletes a directory entry by merging it with the
 
1638
 * previous entry
 
1639
 */
 
1640
static int ext4_delete_entry(handle_t *handle,
 
1641
                             struct inode *dir,
 
1642
                             struct ext4_dir_entry_2 *de_del,
 
1643
                             struct buffer_head *bh)
 
1644
{
 
1645
        struct ext4_dir_entry_2 *de, *pde;
 
1646
        unsigned int blocksize = dir->i_sb->s_blocksize;
 
1647
        int i, err;
 
1648
 
 
1649
        i = 0;
 
1650
        pde = NULL;
 
1651
        de = (struct ext4_dir_entry_2 *) bh->b_data;
 
1652
        while (i < bh->b_size) {
 
1653
                if (ext4_check_dir_entry(dir, NULL, de, bh, i))
 
1654
                        return -EIO;
 
1655
                if (de == de_del)  {
 
1656
                        BUFFER_TRACE(bh, "get_write_access");
 
1657
                        err = ext4_journal_get_write_access(handle, bh);
 
1658
                        if (unlikely(err)) {
 
1659
                                ext4_std_error(dir->i_sb, err);
 
1660
                                return err;
 
1661
                        }
 
1662
                        if (pde)
 
1663
                                pde->rec_len = ext4_rec_len_to_disk(
 
1664
                                        ext4_rec_len_from_disk(pde->rec_len,
 
1665
                                                               blocksize) +
 
1666
                                        ext4_rec_len_from_disk(de->rec_len,
 
1667
                                                               blocksize),
 
1668
                                        blocksize);
 
1669
                        else
 
1670
                                de->inode = 0;
 
1671
                        dir->i_version++;
 
1672
                        BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
 
1673
                        err = ext4_handle_dirty_metadata(handle, dir, bh);
 
1674
                        if (unlikely(err)) {
 
1675
                                ext4_std_error(dir->i_sb, err);
 
1676
                                return err;
 
1677
                        }
 
1678
                        return 0;
 
1679
                }
 
1680
                i += ext4_rec_len_from_disk(de->rec_len, blocksize);
 
1681
                pde = de;
 
1682
                de = ext4_next_entry(de, blocksize);
 
1683
        }
 
1684
        return -ENOENT;
 
1685
}
 
1686
 
 
1687
/*
 
1688
 * DIR_NLINK feature is set if 1) nlinks > EXT4_LINK_MAX or 2) nlinks == 2,
 
1689
 * since this indicates that nlinks count was previously 1.
 
1690
 */
 
1691
static void ext4_inc_count(handle_t *handle, struct inode *inode)
 
1692
{
 
1693
        inc_nlink(inode);
 
1694
        if (is_dx(inode) && inode->i_nlink > 1) {
 
1695
                /* limit is 16-bit i_links_count */
 
1696
                if (inode->i_nlink >= EXT4_LINK_MAX || inode->i_nlink == 2) {
 
1697
                        set_nlink(inode, 1);
 
1698
                        EXT4_SET_RO_COMPAT_FEATURE(inode->i_sb,
 
1699
                                              EXT4_FEATURE_RO_COMPAT_DIR_NLINK);
 
1700
                }
 
1701
        }
 
1702
}
 
1703
 
 
1704
/*
 
1705
 * If a directory had nlink == 1, then we should let it be 1. This indicates
 
1706
 * directory has >EXT4_LINK_MAX subdirs.
 
1707
 */
 
1708
static void ext4_dec_count(handle_t *handle, struct inode *inode)
 
1709
{
 
1710
        if (!S_ISDIR(inode->i_mode) || inode->i_nlink > 2)
 
1711
                drop_nlink(inode);
 
1712
}
 
1713
 
 
1714
 
 
1715
static int ext4_add_nondir(handle_t *handle,
 
1716
                struct dentry *dentry, struct inode *inode)
 
1717
{
 
1718
        int err = ext4_add_entry(handle, dentry, inode);
 
1719
        if (!err) {
 
1720
                ext4_mark_inode_dirty(handle, inode);
 
1721
                d_instantiate(dentry, inode);
 
1722
                unlock_new_inode(inode);
 
1723
                return 0;
 
1724
        }
 
1725
        drop_nlink(inode);
 
1726
        unlock_new_inode(inode);
 
1727
        iput(inode);
 
1728
        return err;
 
1729
}
 
1730
 
 
1731
/*
 
1732
 * By the time this is called, we already have created
 
1733
 * the directory cache entry for the new file, but it
 
1734
 * is so far negative - it has no inode.
 
1735
 *
 
1736
 * If the create succeeds, we fill in the inode information
 
1737
 * with d_instantiate().
 
1738
 */
 
1739
static int ext4_create(struct inode *dir, struct dentry *dentry, int mode,
 
1740
                       struct nameidata *nd)
 
1741
{
 
1742
        handle_t *handle;
 
1743
        struct inode *inode;
 
1744
        int err, retries = 0;
 
1745
 
 
1746
        dquot_initialize(dir);
 
1747
 
 
1748
retry:
 
1749
        handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
 
1750
                                        EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
 
1751
                                        EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
 
1752
        if (IS_ERR(handle))
 
1753
                return PTR_ERR(handle);
 
1754
 
 
1755
        if (IS_DIRSYNC(dir))
 
1756
                ext4_handle_sync(handle);
 
1757
 
 
1758
        inode = ext4_new_inode(handle, dir, mode, &dentry->d_name, 0, NULL);
 
1759
        err = PTR_ERR(inode);
 
1760
        if (!IS_ERR(inode)) {
 
1761
                inode->i_op = &ext4_file_inode_operations;
 
1762
                inode->i_fop = &ext4_file_operations;
 
1763
                ext4_set_aops(inode);
 
1764
                err = ext4_add_nondir(handle, dentry, inode);
 
1765
        }
 
1766
        ext4_journal_stop(handle);
 
1767
        if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
 
1768
                goto retry;
 
1769
        return err;
 
1770
}
 
1771
 
 
1772
static int ext4_mknod(struct inode *dir, struct dentry *dentry,
 
1773
                      int mode, dev_t rdev)
 
1774
{
 
1775
        handle_t *handle;
 
1776
        struct inode *inode;
 
1777
        int err, retries = 0;
 
1778
 
 
1779
        if (!new_valid_dev(rdev))
 
1780
                return -EINVAL;
 
1781
 
 
1782
        dquot_initialize(dir);
 
1783
 
 
1784
retry:
 
1785
        handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
 
1786
                                        EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
 
1787
                                        EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
 
1788
        if (IS_ERR(handle))
 
1789
                return PTR_ERR(handle);
 
1790
 
 
1791
        if (IS_DIRSYNC(dir))
 
1792
                ext4_handle_sync(handle);
 
1793
 
 
1794
        inode = ext4_new_inode(handle, dir, mode, &dentry->d_name, 0, NULL);
 
1795
        err = PTR_ERR(inode);
 
1796
        if (!IS_ERR(inode)) {
 
1797
                init_special_inode(inode, inode->i_mode, rdev);
 
1798
#ifdef CONFIG_EXT4_FS_XATTR
 
1799
                inode->i_op = &ext4_special_inode_operations;
 
1800
#endif
 
1801
                err = ext4_add_nondir(handle, dentry, inode);
 
1802
        }
 
1803
        ext4_journal_stop(handle);
 
1804
        if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
 
1805
                goto retry;
 
1806
        return err;
 
1807
}
 
1808
 
 
1809
static int ext4_mkdir(struct inode *dir, struct dentry *dentry, int mode)
 
1810
{
 
1811
        handle_t *handle;
 
1812
        struct inode *inode;
 
1813
        struct buffer_head *dir_block = NULL;
 
1814
        struct ext4_dir_entry_2 *de;
 
1815
        unsigned int blocksize = dir->i_sb->s_blocksize;
 
1816
        int err, retries = 0;
 
1817
 
 
1818
        if (EXT4_DIR_LINK_MAX(dir))
 
1819
                return -EMLINK;
 
1820
 
 
1821
        dquot_initialize(dir);
 
1822
 
 
1823
retry:
 
1824
        handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
 
1825
                                        EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
 
1826
                                        EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb));
 
1827
        if (IS_ERR(handle))
 
1828
                return PTR_ERR(handle);
 
1829
 
 
1830
        if (IS_DIRSYNC(dir))
 
1831
                ext4_handle_sync(handle);
 
1832
 
 
1833
        inode = ext4_new_inode(handle, dir, S_IFDIR | mode,
 
1834
                               &dentry->d_name, 0, NULL);
 
1835
        err = PTR_ERR(inode);
 
1836
        if (IS_ERR(inode))
 
1837
                goto out_stop;
 
1838
 
 
1839
        inode->i_op = &ext4_dir_inode_operations;
 
1840
        inode->i_fop = &ext4_dir_operations;
 
1841
        inode->i_size = EXT4_I(inode)->i_disksize = inode->i_sb->s_blocksize;
 
1842
        dir_block = ext4_bread(handle, inode, 0, 1, &err);
 
1843
        if (!dir_block)
 
1844
                goto out_clear_inode;
 
1845
        BUFFER_TRACE(dir_block, "get_write_access");
 
1846
        err = ext4_journal_get_write_access(handle, dir_block);
 
1847
        if (err)
 
1848
                goto out_clear_inode;
 
1849
        de = (struct ext4_dir_entry_2 *) dir_block->b_data;
 
1850
        de->inode = cpu_to_le32(inode->i_ino);
 
1851
        de->name_len = 1;
 
1852
        de->rec_len = ext4_rec_len_to_disk(EXT4_DIR_REC_LEN(de->name_len),
 
1853
                                           blocksize);
 
1854
        strcpy(de->name, ".");
 
1855
        ext4_set_de_type(dir->i_sb, de, S_IFDIR);
 
1856
        de = ext4_next_entry(de, blocksize);
 
1857
        de->inode = cpu_to_le32(dir->i_ino);
 
1858
        de->rec_len = ext4_rec_len_to_disk(blocksize - EXT4_DIR_REC_LEN(1),
 
1859
                                           blocksize);
 
1860
        de->name_len = 2;
 
1861
        strcpy(de->name, "..");
 
1862
        ext4_set_de_type(dir->i_sb, de, S_IFDIR);
 
1863
        set_nlink(inode, 2);
 
1864
        BUFFER_TRACE(dir_block, "call ext4_handle_dirty_metadata");
 
1865
        err = ext4_handle_dirty_metadata(handle, inode, dir_block);
 
1866
        if (err)
 
1867
                goto out_clear_inode;
 
1868
        err = ext4_mark_inode_dirty(handle, inode);
 
1869
        if (!err)
 
1870
                err = ext4_add_entry(handle, dentry, inode);
 
1871
        if (err) {
 
1872
out_clear_inode:
 
1873
                clear_nlink(inode);
 
1874
                unlock_new_inode(inode);
 
1875
                ext4_mark_inode_dirty(handle, inode);
 
1876
                iput(inode);
 
1877
                goto out_stop;
 
1878
        }
 
1879
        ext4_inc_count(handle, dir);
 
1880
        ext4_update_dx_flag(dir);
 
1881
        err = ext4_mark_inode_dirty(handle, dir);
 
1882
        if (err)
 
1883
                goto out_clear_inode;
 
1884
        d_instantiate(dentry, inode);
 
1885
        unlock_new_inode(inode);
 
1886
out_stop:
 
1887
        brelse(dir_block);
 
1888
        ext4_journal_stop(handle);
 
1889
        if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
 
1890
                goto retry;
 
1891
        return err;
 
1892
}
 
1893
 
 
1894
/*
 
1895
 * routine to check that the specified directory is empty (for rmdir)
 
1896
 */
 
1897
static int empty_dir(struct inode *inode)
 
1898
{
 
1899
        unsigned int offset;
 
1900
        struct buffer_head *bh;
 
1901
        struct ext4_dir_entry_2 *de, *de1;
 
1902
        struct super_block *sb;
 
1903
        int err = 0;
 
1904
 
 
1905
        sb = inode->i_sb;
 
1906
        if (inode->i_size < EXT4_DIR_REC_LEN(1) + EXT4_DIR_REC_LEN(2) ||
 
1907
            !(bh = ext4_bread(NULL, inode, 0, 0, &err))) {
 
1908
                if (err)
 
1909
                        EXT4_ERROR_INODE(inode,
 
1910
                                "error %d reading directory lblock 0", err);
 
1911
                else
 
1912
                        ext4_warning(inode->i_sb,
 
1913
                                     "bad directory (dir #%lu) - no data block",
 
1914
                                     inode->i_ino);
 
1915
                return 1;
 
1916
        }
 
1917
        de = (struct ext4_dir_entry_2 *) bh->b_data;
 
1918
        de1 = ext4_next_entry(de, sb->s_blocksize);
 
1919
        if (le32_to_cpu(de->inode) != inode->i_ino ||
 
1920
                        !le32_to_cpu(de1->inode) ||
 
1921
                        strcmp(".", de->name) ||
 
1922
                        strcmp("..", de1->name)) {
 
1923
                ext4_warning(inode->i_sb,
 
1924
                             "bad directory (dir #%lu) - no `.' or `..'",
 
1925
                             inode->i_ino);
 
1926
                brelse(bh);
 
1927
                return 1;
 
1928
        }
 
1929
        offset = ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize) +
 
1930
                 ext4_rec_len_from_disk(de1->rec_len, sb->s_blocksize);
 
1931
        de = ext4_next_entry(de1, sb->s_blocksize);
 
1932
        while (offset < inode->i_size) {
 
1933
                if (!bh ||
 
1934
                    (void *) de >= (void *) (bh->b_data+sb->s_blocksize)) {
 
1935
                        unsigned int lblock;
 
1936
                        err = 0;
 
1937
                        brelse(bh);
 
1938
                        lblock = offset >> EXT4_BLOCK_SIZE_BITS(sb);
 
1939
                        bh = ext4_bread(NULL, inode, lblock, 0, &err);
 
1940
                        if (!bh) {
 
1941
                                if (err)
 
1942
                                        EXT4_ERROR_INODE(inode,
 
1943
                                                "error %d reading directory "
 
1944
                                                "lblock %u", err, lblock);
 
1945
                                offset += sb->s_blocksize;
 
1946
                                continue;
 
1947
                        }
 
1948
                        de = (struct ext4_dir_entry_2 *) bh->b_data;
 
1949
                }
 
1950
                if (ext4_check_dir_entry(inode, NULL, de, bh, offset)) {
 
1951
                        de = (struct ext4_dir_entry_2 *)(bh->b_data +
 
1952
                                                         sb->s_blocksize);
 
1953
                        offset = (offset | (sb->s_blocksize - 1)) + 1;
 
1954
                        continue;
 
1955
                }
 
1956
                if (le32_to_cpu(de->inode)) {
 
1957
                        brelse(bh);
 
1958
                        return 0;
 
1959
                }
 
1960
                offset += ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize);
 
1961
                de = ext4_next_entry(de, sb->s_blocksize);
 
1962
        }
 
1963
        brelse(bh);
 
1964
        return 1;
 
1965
}
 
1966
 
 
1967
/* ext4_orphan_add() links an unlinked or truncated inode into a list of
 
1968
 * such inodes, starting at the superblock, in case we crash before the
 
1969
 * file is closed/deleted, or in case the inode truncate spans multiple
 
1970
 * transactions and the last transaction is not recovered after a crash.
 
1971
 *
 
1972
 * At filesystem recovery time, we walk this list deleting unlinked
 
1973
 * inodes and truncating linked inodes in ext4_orphan_cleanup().
 
1974
 */
 
1975
int ext4_orphan_add(handle_t *handle, struct inode *inode)
 
1976
{
 
1977
        struct super_block *sb = inode->i_sb;
 
1978
        struct ext4_iloc iloc;
 
1979
        int err = 0, rc;
 
1980
 
 
1981
        if (!ext4_handle_valid(handle))
 
1982
                return 0;
 
1983
 
 
1984
        mutex_lock(&EXT4_SB(sb)->s_orphan_lock);
 
1985
        if (!list_empty(&EXT4_I(inode)->i_orphan))
 
1986
                goto out_unlock;
 
1987
 
 
1988
        /*
 
1989
         * Orphan handling is only valid for files with data blocks
 
1990
         * being truncated, or files being unlinked. Note that we either
 
1991
         * hold i_mutex, or the inode can not be referenced from outside,
 
1992
         * so i_nlink should not be bumped due to race
 
1993
         */
 
1994
        J_ASSERT((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
 
1995
                  S_ISLNK(inode->i_mode)) || inode->i_nlink == 0);
 
1996
 
 
1997
        BUFFER_TRACE(EXT4_SB(sb)->s_sbh, "get_write_access");
 
1998
        err = ext4_journal_get_write_access(handle, EXT4_SB(sb)->s_sbh);
 
1999
        if (err)
 
2000
                goto out_unlock;
 
2001
 
 
2002
        err = ext4_reserve_inode_write(handle, inode, &iloc);
 
2003
        if (err)
 
2004
                goto out_unlock;
 
2005
        /*
 
2006
         * Due to previous errors inode may be already a part of on-disk
 
2007
         * orphan list. If so skip on-disk list modification.
 
2008
         */
 
2009
        if (NEXT_ORPHAN(inode) && NEXT_ORPHAN(inode) <=
 
2010
                (le32_to_cpu(EXT4_SB(sb)->s_es->s_inodes_count)))
 
2011
                        goto mem_insert;
 
2012
 
 
2013
        /* Insert this inode at the head of the on-disk orphan list... */
 
2014
        NEXT_ORPHAN(inode) = le32_to_cpu(EXT4_SB(sb)->s_es->s_last_orphan);
 
2015
        EXT4_SB(sb)->s_es->s_last_orphan = cpu_to_le32(inode->i_ino);
 
2016
        err = ext4_handle_dirty_metadata(handle, NULL, EXT4_SB(sb)->s_sbh);
 
2017
        rc = ext4_mark_iloc_dirty(handle, inode, &iloc);
 
2018
        if (!err)
 
2019
                err = rc;
 
2020
 
 
2021
        /* Only add to the head of the in-memory list if all the
 
2022
         * previous operations succeeded.  If the orphan_add is going to
 
2023
         * fail (possibly taking the journal offline), we can't risk
 
2024
         * leaving the inode on the orphan list: stray orphan-list
 
2025
         * entries can cause panics at unmount time.
 
2026
         *
 
2027
         * This is safe: on error we're going to ignore the orphan list
 
2028
         * anyway on the next recovery. */
 
2029
mem_insert:
 
2030
        if (!err)
 
2031
                list_add(&EXT4_I(inode)->i_orphan, &EXT4_SB(sb)->s_orphan);
 
2032
 
 
2033
        jbd_debug(4, "superblock will point to %lu\n", inode->i_ino);
 
2034
        jbd_debug(4, "orphan inode %lu will point to %d\n",
 
2035
                        inode->i_ino, NEXT_ORPHAN(inode));
 
2036
out_unlock:
 
2037
        mutex_unlock(&EXT4_SB(sb)->s_orphan_lock);
 
2038
        ext4_std_error(inode->i_sb, err);
 
2039
        return err;
 
2040
}
 
2041
 
 
2042
/*
 
2043
 * ext4_orphan_del() removes an unlinked or truncated inode from the list
 
2044
 * of such inodes stored on disk, because it is finally being cleaned up.
 
2045
 */
 
2046
int ext4_orphan_del(handle_t *handle, struct inode *inode)
 
2047
{
 
2048
        struct list_head *prev;
 
2049
        struct ext4_inode_info *ei = EXT4_I(inode);
 
2050
        struct ext4_sb_info *sbi;
 
2051
        __u32 ino_next;
 
2052
        struct ext4_iloc iloc;
 
2053
        int err = 0;
 
2054
 
 
2055
        /* ext4_handle_valid() assumes a valid handle_t pointer */
 
2056
        if (handle && !ext4_handle_valid(handle))
 
2057
                return 0;
 
2058
 
 
2059
        mutex_lock(&EXT4_SB(inode->i_sb)->s_orphan_lock);
 
2060
        if (list_empty(&ei->i_orphan))
 
2061
                goto out;
 
2062
 
 
2063
        ino_next = NEXT_ORPHAN(inode);
 
2064
        prev = ei->i_orphan.prev;
 
2065
        sbi = EXT4_SB(inode->i_sb);
 
2066
 
 
2067
        jbd_debug(4, "remove inode %lu from orphan list\n", inode->i_ino);
 
2068
 
 
2069
        list_del_init(&ei->i_orphan);
 
2070
 
 
2071
        /* If we're on an error path, we may not have a valid
 
2072
         * transaction handle with which to update the orphan list on
 
2073
         * disk, but we still need to remove the inode from the linked
 
2074
         * list in memory. */
 
2075
        if (sbi->s_journal && !handle)
 
2076
                goto out;
 
2077
 
 
2078
        err = ext4_reserve_inode_write(handle, inode, &iloc);
 
2079
        if (err)
 
2080
                goto out_err;
 
2081
 
 
2082
        if (prev == &sbi->s_orphan) {
 
2083
                jbd_debug(4, "superblock will point to %u\n", ino_next);
 
2084
                BUFFER_TRACE(sbi->s_sbh, "get_write_access");
 
2085
                err = ext4_journal_get_write_access(handle, sbi->s_sbh);
 
2086
                if (err)
 
2087
                        goto out_brelse;
 
2088
                sbi->s_es->s_last_orphan = cpu_to_le32(ino_next);
 
2089
                err = ext4_handle_dirty_metadata(handle, NULL, sbi->s_sbh);
 
2090
        } else {
 
2091
                struct ext4_iloc iloc2;
 
2092
                struct inode *i_prev =
 
2093
                        &list_entry(prev, struct ext4_inode_info, i_orphan)->vfs_inode;
 
2094
 
 
2095
                jbd_debug(4, "orphan inode %lu will point to %u\n",
 
2096
                          i_prev->i_ino, ino_next);
 
2097
                err = ext4_reserve_inode_write(handle, i_prev, &iloc2);
 
2098
                if (err)
 
2099
                        goto out_brelse;
 
2100
                NEXT_ORPHAN(i_prev) = ino_next;
 
2101
                err = ext4_mark_iloc_dirty(handle, i_prev, &iloc2);
 
2102
        }
 
2103
        if (err)
 
2104
                goto out_brelse;
 
2105
        NEXT_ORPHAN(inode) = 0;
 
2106
        err = ext4_mark_iloc_dirty(handle, inode, &iloc);
 
2107
 
 
2108
out_err:
 
2109
        ext4_std_error(inode->i_sb, err);
 
2110
out:
 
2111
        mutex_unlock(&EXT4_SB(inode->i_sb)->s_orphan_lock);
 
2112
        return err;
 
2113
 
 
2114
out_brelse:
 
2115
        brelse(iloc.bh);
 
2116
        goto out_err;
 
2117
}
 
2118
 
 
2119
static int ext4_rmdir(struct inode *dir, struct dentry *dentry)
 
2120
{
 
2121
        int retval;
 
2122
        struct inode *inode;
 
2123
        struct buffer_head *bh;
 
2124
        struct ext4_dir_entry_2 *de;
 
2125
        handle_t *handle;
 
2126
 
 
2127
        /* Initialize quotas before so that eventual writes go in
 
2128
         * separate transaction */
 
2129
        dquot_initialize(dir);
 
2130
        dquot_initialize(dentry->d_inode);
 
2131
 
 
2132
        handle = ext4_journal_start(dir, EXT4_DELETE_TRANS_BLOCKS(dir->i_sb));
 
2133
        if (IS_ERR(handle))
 
2134
                return PTR_ERR(handle);
 
2135
 
 
2136
        retval = -ENOENT;
 
2137
        bh = ext4_find_entry(dir, &dentry->d_name, &de);
 
2138
        if (!bh)
 
2139
                goto end_rmdir;
 
2140
 
 
2141
        if (IS_DIRSYNC(dir))
 
2142
                ext4_handle_sync(handle);
 
2143
 
 
2144
        inode = dentry->d_inode;
 
2145
 
 
2146
        retval = -EIO;
 
2147
        if (le32_to_cpu(de->inode) != inode->i_ino)
 
2148
                goto end_rmdir;
 
2149
 
 
2150
        retval = -ENOTEMPTY;
 
2151
        if (!empty_dir(inode))
 
2152
                goto end_rmdir;
 
2153
 
 
2154
        retval = ext4_delete_entry(handle, dir, de, bh);
 
2155
        if (retval)
 
2156
                goto end_rmdir;
 
2157
        if (!EXT4_DIR_LINK_EMPTY(inode))
 
2158
                ext4_warning(inode->i_sb,
 
2159
                             "empty directory has too many links (%d)",
 
2160
                             inode->i_nlink);
 
2161
        inode->i_version++;
 
2162
        clear_nlink(inode);
 
2163
        /* There's no need to set i_disksize: the fact that i_nlink is
 
2164
         * zero will ensure that the right thing happens during any
 
2165
         * recovery. */
 
2166
        inode->i_size = 0;
 
2167
        ext4_orphan_add(handle, inode);
 
2168
        inode->i_ctime = dir->i_ctime = dir->i_mtime = ext4_current_time(inode);
 
2169
        ext4_mark_inode_dirty(handle, inode);
 
2170
        ext4_dec_count(handle, dir);
 
2171
        ext4_update_dx_flag(dir);
 
2172
        ext4_mark_inode_dirty(handle, dir);
 
2173
 
 
2174
end_rmdir:
 
2175
        ext4_journal_stop(handle);
 
2176
        brelse(bh);
 
2177
        return retval;
 
2178
}
 
2179
 
 
2180
static int ext4_unlink(struct inode *dir, struct dentry *dentry)
 
2181
{
 
2182
        int retval;
 
2183
        struct inode *inode;
 
2184
        struct buffer_head *bh;
 
2185
        struct ext4_dir_entry_2 *de;
 
2186
        handle_t *handle;
 
2187
 
 
2188
        trace_ext4_unlink_enter(dir, dentry);
 
2189
        /* Initialize quotas before so that eventual writes go
 
2190
         * in separate transaction */
 
2191
        dquot_initialize(dir);
 
2192
        dquot_initialize(dentry->d_inode);
 
2193
 
 
2194
        handle = ext4_journal_start(dir, EXT4_DELETE_TRANS_BLOCKS(dir->i_sb));
 
2195
        if (IS_ERR(handle))
 
2196
                return PTR_ERR(handle);
 
2197
 
 
2198
        if (IS_DIRSYNC(dir))
 
2199
                ext4_handle_sync(handle);
 
2200
 
 
2201
        retval = -ENOENT;
 
2202
        bh = ext4_find_entry(dir, &dentry->d_name, &de);
 
2203
        if (!bh)
 
2204
                goto end_unlink;
 
2205
 
 
2206
        inode = dentry->d_inode;
 
2207
 
 
2208
        retval = -EIO;
 
2209
        if (le32_to_cpu(de->inode) != inode->i_ino)
 
2210
                goto end_unlink;
 
2211
 
 
2212
        if (!inode->i_nlink) {
 
2213
                ext4_warning(inode->i_sb,
 
2214
                             "Deleting nonexistent file (%lu), %d",
 
2215
                             inode->i_ino, inode->i_nlink);
 
2216
                set_nlink(inode, 1);
 
2217
        }
 
2218
        retval = ext4_delete_entry(handle, dir, de, bh);
 
2219
        if (retval)
 
2220
                goto end_unlink;
 
2221
        dir->i_ctime = dir->i_mtime = ext4_current_time(dir);
 
2222
        ext4_update_dx_flag(dir);
 
2223
        ext4_mark_inode_dirty(handle, dir);
 
2224
        drop_nlink(inode);
 
2225
        if (!inode->i_nlink)
 
2226
                ext4_orphan_add(handle, inode);
 
2227
        inode->i_ctime = ext4_current_time(inode);
 
2228
        ext4_mark_inode_dirty(handle, inode);
 
2229
        retval = 0;
 
2230
 
 
2231
end_unlink:
 
2232
        ext4_journal_stop(handle);
 
2233
        brelse(bh);
 
2234
        trace_ext4_unlink_exit(dentry, retval);
 
2235
        return retval;
 
2236
}
 
2237
 
 
2238
static int ext4_symlink(struct inode *dir,
 
2239
                        struct dentry *dentry, const char *symname)
 
2240
{
 
2241
        handle_t *handle;
 
2242
        struct inode *inode;
 
2243
        int l, err, retries = 0;
 
2244
        int credits;
 
2245
 
 
2246
        l = strlen(symname)+1;
 
2247
        if (l > dir->i_sb->s_blocksize)
 
2248
                return -ENAMETOOLONG;
 
2249
 
 
2250
        dquot_initialize(dir);
 
2251
 
 
2252
        if (l > EXT4_N_BLOCKS * 4) {
 
2253
                /*
 
2254
                 * For non-fast symlinks, we just allocate inode and put it on
 
2255
                 * orphan list in the first transaction => we need bitmap,
 
2256
                 * group descriptor, sb, inode block, quota blocks, and
 
2257
                 * possibly selinux xattr blocks.
 
2258
                 */
 
2259
                credits = 4 + EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb) +
 
2260
                          EXT4_XATTR_TRANS_BLOCKS;
 
2261
        } else {
 
2262
                /*
 
2263
                 * Fast symlink. We have to add entry to directory
 
2264
                 * (EXT4_DATA_TRANS_BLOCKS + EXT4_INDEX_EXTRA_TRANS_BLOCKS),
 
2265
                 * allocate new inode (bitmap, group descriptor, inode block,
 
2266
                 * quota blocks, sb is already counted in previous macros).
 
2267
                 */
 
2268
                credits = EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
 
2269
                          EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3 +
 
2270
                          EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb);
 
2271
        }
 
2272
retry:
 
2273
        handle = ext4_journal_start(dir, credits);
 
2274
        if (IS_ERR(handle))
 
2275
                return PTR_ERR(handle);
 
2276
 
 
2277
        if (IS_DIRSYNC(dir))
 
2278
                ext4_handle_sync(handle);
 
2279
 
 
2280
        inode = ext4_new_inode(handle, dir, S_IFLNK|S_IRWXUGO,
 
2281
                               &dentry->d_name, 0, NULL);
 
2282
        err = PTR_ERR(inode);
 
2283
        if (IS_ERR(inode))
 
2284
                goto out_stop;
 
2285
 
 
2286
        if (l > EXT4_N_BLOCKS * 4) {
 
2287
                inode->i_op = &ext4_symlink_inode_operations;
 
2288
                ext4_set_aops(inode);
 
2289
                /*
 
2290
                 * We cannot call page_symlink() with transaction started
 
2291
                 * because it calls into ext4_write_begin() which can wait
 
2292
                 * for transaction commit if we are running out of space
 
2293
                 * and thus we deadlock. So we have to stop transaction now
 
2294
                 * and restart it when symlink contents is written.
 
2295
                 * 
 
2296
                 * To keep fs consistent in case of crash, we have to put inode
 
2297
                 * to orphan list in the mean time.
 
2298
                 */
 
2299
                drop_nlink(inode);
 
2300
                err = ext4_orphan_add(handle, inode);
 
2301
                ext4_journal_stop(handle);
 
2302
                if (err)
 
2303
                        goto err_drop_inode;
 
2304
                err = __page_symlink(inode, symname, l, 1);
 
2305
                if (err)
 
2306
                        goto err_drop_inode;
 
2307
                /*
 
2308
                 * Now inode is being linked into dir (EXT4_DATA_TRANS_BLOCKS
 
2309
                 * + EXT4_INDEX_EXTRA_TRANS_BLOCKS), inode is also modified
 
2310
                 */
 
2311
                handle = ext4_journal_start(dir,
 
2312
                                EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
 
2313
                                EXT4_INDEX_EXTRA_TRANS_BLOCKS + 1);
 
2314
                if (IS_ERR(handle)) {
 
2315
                        err = PTR_ERR(handle);
 
2316
                        goto err_drop_inode;
 
2317
                }
 
2318
                inc_nlink(inode);
 
2319
                err = ext4_orphan_del(handle, inode);
 
2320
                if (err) {
 
2321
                        ext4_journal_stop(handle);
 
2322
                        clear_nlink(inode);
 
2323
                        goto err_drop_inode;
 
2324
                }
 
2325
        } else {
 
2326
                /* clear the extent format for fast symlink */
 
2327
                ext4_clear_inode_flag(inode, EXT4_INODE_EXTENTS);
 
2328
                inode->i_op = &ext4_fast_symlink_inode_operations;
 
2329
                memcpy((char *)&EXT4_I(inode)->i_data, symname, l);
 
2330
                inode->i_size = l-1;
 
2331
        }
 
2332
        EXT4_I(inode)->i_disksize = inode->i_size;
 
2333
        err = ext4_add_nondir(handle, dentry, inode);
 
2334
out_stop:
 
2335
        ext4_journal_stop(handle);
 
2336
        if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
 
2337
                goto retry;
 
2338
        return err;
 
2339
err_drop_inode:
 
2340
        unlock_new_inode(inode);
 
2341
        iput(inode);
 
2342
        return err;
 
2343
}
 
2344
 
 
2345
static int ext4_link(struct dentry *old_dentry,
 
2346
                     struct inode *dir, struct dentry *dentry)
 
2347
{
 
2348
        handle_t *handle;
 
2349
        struct inode *inode = old_dentry->d_inode;
 
2350
        int err, retries = 0;
 
2351
 
 
2352
        if (inode->i_nlink >= EXT4_LINK_MAX)
 
2353
                return -EMLINK;
 
2354
 
 
2355
        dquot_initialize(dir);
 
2356
 
 
2357
retry:
 
2358
        handle = ext4_journal_start(dir, EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
 
2359
                                        EXT4_INDEX_EXTRA_TRANS_BLOCKS);
 
2360
        if (IS_ERR(handle))
 
2361
                return PTR_ERR(handle);
 
2362
 
 
2363
        if (IS_DIRSYNC(dir))
 
2364
                ext4_handle_sync(handle);
 
2365
 
 
2366
        inode->i_ctime = ext4_current_time(inode);
 
2367
        ext4_inc_count(handle, inode);
 
2368
        ihold(inode);
 
2369
 
 
2370
        err = ext4_add_entry(handle, dentry, inode);
 
2371
        if (!err) {
 
2372
                ext4_mark_inode_dirty(handle, inode);
 
2373
                d_instantiate(dentry, inode);
 
2374
        } else {
 
2375
                drop_nlink(inode);
 
2376
                iput(inode);
 
2377
        }
 
2378
        ext4_journal_stop(handle);
 
2379
        if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
 
2380
                goto retry;
 
2381
        return err;
 
2382
}
 
2383
 
 
2384
#define PARENT_INO(buffer, size) \
 
2385
        (ext4_next_entry((struct ext4_dir_entry_2 *)(buffer), size)->inode)
 
2386
 
 
2387
/*
 
2388
 * Anybody can rename anything with this: the permission checks are left to the
 
2389
 * higher-level routines.
 
2390
 */
 
2391
static int ext4_rename(struct inode *old_dir, struct dentry *old_dentry,
 
2392
                       struct inode *new_dir, struct dentry *new_dentry)
 
2393
{
 
2394
        handle_t *handle;
 
2395
        struct inode *old_inode, *new_inode;
 
2396
        struct buffer_head *old_bh, *new_bh, *dir_bh;
 
2397
        struct ext4_dir_entry_2 *old_de, *new_de;
 
2398
        int retval, force_da_alloc = 0;
 
2399
 
 
2400
        dquot_initialize(old_dir);
 
2401
        dquot_initialize(new_dir);
 
2402
 
 
2403
        old_bh = new_bh = dir_bh = NULL;
 
2404
 
 
2405
        /* Initialize quotas before so that eventual writes go
 
2406
         * in separate transaction */
 
2407
        if (new_dentry->d_inode)
 
2408
                dquot_initialize(new_dentry->d_inode);
 
2409
        handle = ext4_journal_start(old_dir, 2 *
 
2410
                                        EXT4_DATA_TRANS_BLOCKS(old_dir->i_sb) +
 
2411
                                        EXT4_INDEX_EXTRA_TRANS_BLOCKS + 2);
 
2412
        if (IS_ERR(handle))
 
2413
                return PTR_ERR(handle);
 
2414
 
 
2415
        if (IS_DIRSYNC(old_dir) || IS_DIRSYNC(new_dir))
 
2416
                ext4_handle_sync(handle);
 
2417
 
 
2418
        old_bh = ext4_find_entry(old_dir, &old_dentry->d_name, &old_de);
 
2419
        /*
 
2420
         *  Check for inode number is _not_ due to possible IO errors.
 
2421
         *  We might rmdir the source, keep it as pwd of some process
 
2422
         *  and merrily kill the link to whatever was created under the
 
2423
         *  same name. Goodbye sticky bit ;-<
 
2424
         */
 
2425
        old_inode = old_dentry->d_inode;
 
2426
        retval = -ENOENT;
 
2427
        if (!old_bh || le32_to_cpu(old_de->inode) != old_inode->i_ino)
 
2428
                goto end_rename;
 
2429
 
 
2430
        new_inode = new_dentry->d_inode;
 
2431
        new_bh = ext4_find_entry(new_dir, &new_dentry->d_name, &new_de);
 
2432
        if (new_bh) {
 
2433
                if (!new_inode) {
 
2434
                        brelse(new_bh);
 
2435
                        new_bh = NULL;
 
2436
                }
 
2437
        }
 
2438
        if (S_ISDIR(old_inode->i_mode)) {
 
2439
                if (new_inode) {
 
2440
                        retval = -ENOTEMPTY;
 
2441
                        if (!empty_dir(new_inode))
 
2442
                                goto end_rename;
 
2443
                }
 
2444
                retval = -EIO;
 
2445
                dir_bh = ext4_bread(handle, old_inode, 0, 0, &retval);
 
2446
                if (!dir_bh)
 
2447
                        goto end_rename;
 
2448
                if (le32_to_cpu(PARENT_INO(dir_bh->b_data,
 
2449
                                old_dir->i_sb->s_blocksize)) != old_dir->i_ino)
 
2450
                        goto end_rename;
 
2451
                retval = -EMLINK;
 
2452
                if (!new_inode && new_dir != old_dir &&
 
2453
                    EXT4_DIR_LINK_MAX(new_dir))
 
2454
                        goto end_rename;
 
2455
                BUFFER_TRACE(dir_bh, "get_write_access");
 
2456
                retval = ext4_journal_get_write_access(handle, dir_bh);
 
2457
                if (retval)
 
2458
                        goto end_rename;
 
2459
        }
 
2460
        if (!new_bh) {
 
2461
                retval = ext4_add_entry(handle, new_dentry, old_inode);
 
2462
                if (retval)
 
2463
                        goto end_rename;
 
2464
        } else {
 
2465
                BUFFER_TRACE(new_bh, "get write access");
 
2466
                retval = ext4_journal_get_write_access(handle, new_bh);
 
2467
                if (retval)
 
2468
                        goto end_rename;
 
2469
                new_de->inode = cpu_to_le32(old_inode->i_ino);
 
2470
                if (EXT4_HAS_INCOMPAT_FEATURE(new_dir->i_sb,
 
2471
                                              EXT4_FEATURE_INCOMPAT_FILETYPE))
 
2472
                        new_de->file_type = old_de->file_type;
 
2473
                new_dir->i_version++;
 
2474
                new_dir->i_ctime = new_dir->i_mtime =
 
2475
                                        ext4_current_time(new_dir);
 
2476
                ext4_mark_inode_dirty(handle, new_dir);
 
2477
                BUFFER_TRACE(new_bh, "call ext4_handle_dirty_metadata");
 
2478
                retval = ext4_handle_dirty_metadata(handle, new_dir, new_bh);
 
2479
                if (unlikely(retval)) {
 
2480
                        ext4_std_error(new_dir->i_sb, retval);
 
2481
                        goto end_rename;
 
2482
                }
 
2483
                brelse(new_bh);
 
2484
                new_bh = NULL;
 
2485
        }
 
2486
 
 
2487
        /*
 
2488
         * Like most other Unix systems, set the ctime for inodes on a
 
2489
         * rename.
 
2490
         */
 
2491
        old_inode->i_ctime = ext4_current_time(old_inode);
 
2492
        ext4_mark_inode_dirty(handle, old_inode);
 
2493
 
 
2494
        /*
 
2495
         * ok, that's it
 
2496
         */
 
2497
        if (le32_to_cpu(old_de->inode) != old_inode->i_ino ||
 
2498
            old_de->name_len != old_dentry->d_name.len ||
 
2499
            strncmp(old_de->name, old_dentry->d_name.name, old_de->name_len) ||
 
2500
            (retval = ext4_delete_entry(handle, old_dir,
 
2501
                                        old_de, old_bh)) == -ENOENT) {
 
2502
                /* old_de could have moved from under us during htree split, so
 
2503
                 * make sure that we are deleting the right entry.  We might
 
2504
                 * also be pointing to a stale entry in the unused part of
 
2505
                 * old_bh so just checking inum and the name isn't enough. */
 
2506
                struct buffer_head *old_bh2;
 
2507
                struct ext4_dir_entry_2 *old_de2;
 
2508
 
 
2509
                old_bh2 = ext4_find_entry(old_dir, &old_dentry->d_name, &old_de2);
 
2510
                if (old_bh2) {
 
2511
                        retval = ext4_delete_entry(handle, old_dir,
 
2512
                                                   old_de2, old_bh2);
 
2513
                        brelse(old_bh2);
 
2514
                }
 
2515
        }
 
2516
        if (retval) {
 
2517
                ext4_warning(old_dir->i_sb,
 
2518
                                "Deleting old file (%lu), %d, error=%d",
 
2519
                                old_dir->i_ino, old_dir->i_nlink, retval);
 
2520
        }
 
2521
 
 
2522
        if (new_inode) {
 
2523
                ext4_dec_count(handle, new_inode);
 
2524
                new_inode->i_ctime = ext4_current_time(new_inode);
 
2525
        }
 
2526
        old_dir->i_ctime = old_dir->i_mtime = ext4_current_time(old_dir);
 
2527
        ext4_update_dx_flag(old_dir);
 
2528
        if (dir_bh) {
 
2529
                PARENT_INO(dir_bh->b_data, new_dir->i_sb->s_blocksize) =
 
2530
                                                cpu_to_le32(new_dir->i_ino);
 
2531
                BUFFER_TRACE(dir_bh, "call ext4_handle_dirty_metadata");
 
2532
                retval = ext4_handle_dirty_metadata(handle, old_inode, dir_bh);
 
2533
                if (retval) {
 
2534
                        ext4_std_error(old_dir->i_sb, retval);
 
2535
                        goto end_rename;
 
2536
                }
 
2537
                ext4_dec_count(handle, old_dir);
 
2538
                if (new_inode) {
 
2539
                        /* checked empty_dir above, can't have another parent,
 
2540
                         * ext4_dec_count() won't work for many-linked dirs */
 
2541
                        clear_nlink(new_inode);
 
2542
                } else {
 
2543
                        ext4_inc_count(handle, new_dir);
 
2544
                        ext4_update_dx_flag(new_dir);
 
2545
                        ext4_mark_inode_dirty(handle, new_dir);
 
2546
                }
 
2547
        }
 
2548
        ext4_mark_inode_dirty(handle, old_dir);
 
2549
        if (new_inode) {
 
2550
                ext4_mark_inode_dirty(handle, new_inode);
 
2551
                if (!new_inode->i_nlink)
 
2552
                        ext4_orphan_add(handle, new_inode);
 
2553
                if (!test_opt(new_dir->i_sb, NO_AUTO_DA_ALLOC))
 
2554
                        force_da_alloc = 1;
 
2555
        }
 
2556
        retval = 0;
 
2557
 
 
2558
end_rename:
 
2559
        brelse(dir_bh);
 
2560
        brelse(old_bh);
 
2561
        brelse(new_bh);
 
2562
        ext4_journal_stop(handle);
 
2563
        if (retval == 0 && force_da_alloc)
 
2564
                ext4_alloc_da_blocks(old_inode);
 
2565
        return retval;
 
2566
}
 
2567
 
 
2568
/*
 
2569
 * directories can handle most operations...
 
2570
 */
 
2571
const struct inode_operations ext4_dir_inode_operations = {
 
2572
        .create         = ext4_create,
 
2573
        .lookup         = ext4_lookup,
 
2574
        .link           = ext4_link,
 
2575
        .unlink         = ext4_unlink,
 
2576
        .symlink        = ext4_symlink,
 
2577
        .mkdir          = ext4_mkdir,
 
2578
        .rmdir          = ext4_rmdir,
 
2579
        .mknod          = ext4_mknod,
 
2580
        .rename         = ext4_rename,
 
2581
        .setattr        = ext4_setattr,
 
2582
#ifdef CONFIG_EXT4_FS_XATTR
 
2583
        .setxattr       = generic_setxattr,
 
2584
        .getxattr       = generic_getxattr,
 
2585
        .listxattr      = ext4_listxattr,
 
2586
        .removexattr    = generic_removexattr,
 
2587
#endif
 
2588
        .get_acl        = ext4_get_acl,
 
2589
        .fiemap         = ext4_fiemap,
 
2590
};
 
2591
 
 
2592
const struct inode_operations ext4_special_inode_operations = {
 
2593
        .setattr        = ext4_setattr,
 
2594
#ifdef CONFIG_EXT4_FS_XATTR
 
2595
        .setxattr       = generic_setxattr,
 
2596
        .getxattr       = generic_getxattr,
 
2597
        .listxattr      = ext4_listxattr,
 
2598
        .removexattr    = generic_removexattr,
 
2599
#endif
 
2600
        .get_acl        = ext4_get_acl,
 
2601
};