[GFS2] Change ondisk format (hopefully for the last time)
[linux-2.6.git] / fs / gfs2 / dir.c
1 /*
2  * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
3  * Copyright (C) 2004-2005 Red Hat, Inc.  All rights reserved.
4  *
5  * This copyrighted material is made available to anyone wishing to use,
6  * modify, copy, or redistribute it subject to the terms and conditions
7  * of the GNU General Public License v.2.
8  */
9
10 /*
11 * Implements Extendible Hashing as described in:
12 *   "Extendible Hashing" by Fagin, et al in
13 *     __ACM Trans. on Database Systems__, Sept 1979.
14 *
15 *
16 * Here's the layout of dirents which is essentially the same as that of ext2
17 * within a single block. The field de_name_len is the number of bytes
18 * actually required for the name (no null terminator). The field de_rec_len
19 * is the number of bytes allocated to the dirent. The offset of the next
20 * dirent in the block is (dirent + dirent->de_rec_len). When a dirent is
21 * deleted, the preceding dirent inherits its allocated space, ie
22 * prev->de_rec_len += deleted->de_rec_len. Since the next dirent is obtained
23 * by adding de_rec_len to the current dirent, this essentially causes the
24 * deleted dirent to get jumped over when iterating through all the dirents.
25 *
26 * When deleting the first dirent in a block, there is no previous dirent so
27 * the field de_ino is set to zero to designate it as deleted. When allocating
28 * a dirent, gfs2_dirent_alloc iterates through the dirents in a block. If the
29 * first dirent has (de_ino == 0) and de_rec_len is large enough, this first
30 * dirent is allocated. Otherwise it must go through all the 'used' dirents
31 * searching for one in which the amount of total space minus the amount of
32 * used space will provide enough space for the new dirent.
33 *
34 * There are two types of blocks in which dirents reside. In a stuffed dinode,
35 * the dirents begin at offset sizeof(struct gfs2_dinode) from the beginning of
36 * the block.  In leaves, they begin at offset sizeof(struct gfs2_leaf) from the
37 * beginning of the leaf block. The dirents reside in leaves when
38 *
39 * dip->i_di.di_flags & GFS2_DIF_EXHASH is true
40 *
41 * Otherwise, the dirents are "linear", within a single stuffed dinode block.
42 *
43 * When the dirents are in leaves, the actual contents of the directory file are
44 * used as an array of 64-bit block pointers pointing to the leaf blocks. The
45 * dirents are NOT in the directory file itself. There can be more than one block
46 * pointer in the array that points to the same leaf. In fact, when a directory
47 * is first converted from linear to exhash, all of the pointers point to the
48 * same leaf.
49 *
50 * When a leaf is completely full, the size of the hash table can be
51 * doubled unless it is already at the maximum size which is hard coded into
52 * GFS2_DIR_MAX_DEPTH. After that, leaves are chained together in a linked list,
53 * but never before the maximum hash table size has been reached.
54 */
55
56 #include <linux/sched.h>
57 #include <linux/slab.h>
58 #include <linux/spinlock.h>
59 #include <linux/completion.h>
60 #include <linux/buffer_head.h>
61 #include <linux/sort.h>
62 #include <asm/semaphore.h>
63
64 #include "gfs2.h"
65 #include "dir.h"
66 #include "glock.h"
67 #include "inode.h"
68 #include "meta_io.h"
69 #include "quota.h"
70 #include "rgrp.h"
71 #include "trans.h"
72 #include "bmap.h"
73
74 #define IS_LEAF     1 /* Hashed (leaf) directory */
75 #define IS_DINODE   2 /* Linear (stuffed dinode block) directory */
76
77 #if 1
78 #define gfs2_disk_hash2offset(h) (((uint64_t)(h)) >> 1)
79 #define gfs2_dir_offset2hash(p) ((uint32_t)(((uint64_t)(p)) << 1))
80 #else
81 #define gfs2_disk_hash2offset(h) (((uint64_t)(h)))
82 #define gfs2_dir_offset2hash(p) ((uint32_t)(((uint64_t)(p))))
83 #endif
84
85 typedef int (*leaf_call_t) (struct gfs2_inode *dip,
86                             uint32_t index, uint32_t len, uint64_t leaf_no,
87                             void *data);
88
89 int gfs2_dir_get_buffer(struct gfs2_inode *ip, uint64_t block, int new,
90                          struct buffer_head **bhp)
91 {
92         struct buffer_head *bh;
93         int error = 0;
94
95         if (new) {
96                 bh = gfs2_meta_new(ip->i_gl, block);
97                 gfs2_trans_add_bh(ip->i_gl, bh, 1);
98                 gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD);
99                 gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));
100         } else {
101                 error = gfs2_meta_read(ip->i_gl, block, DIO_START | DIO_WAIT, &bh);
102                 if (error)
103                         return error;
104                 if (gfs2_metatype_check(ip->i_sbd, bh, GFS2_METATYPE_JD)) {
105                         brelse(bh);
106                         return -EIO;
107                 }
108         }
109
110         *bhp = bh;
111         return 0;
112 }
113
114
115
116 static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf,
117                                   unsigned int offset, unsigned int size)
118                                
119 {
120         struct buffer_head *dibh;
121         int error;
122
123         error = gfs2_meta_inode_buffer(ip, &dibh);
124         if (error)
125                 return error;
126
127         gfs2_trans_add_bh(ip->i_gl, dibh, 1);
128         memcpy(dibh->b_data + offset + sizeof(struct gfs2_inode), buf, size);
129         if (ip->i_di.di_size < offset + size)
130                 ip->i_di.di_size = offset + size;
131         ip->i_di.di_mtime = ip->i_di.di_ctime = get_seconds();
132         gfs2_dinode_out(&ip->i_di, dibh->b_data);
133
134         brelse(dibh);
135
136         return size;
137 }
138
139
140
141 /**
142  * gfs2_dir_write_data - Write directory information to the inode
143  * @ip: The GFS2 inode
144  * @buf: The buffer containing information to be written
145  * @offset: The file offset to start writing at
146  * @size: The amount of data to write
147  *
148  * Returns: The number of bytes correctly written or error code
149  */
150 static int gfs2_dir_write_data(struct gfs2_inode *ip, const char *buf,
151                                uint64_t offset, unsigned int size)
152 {
153         struct gfs2_sbd *sdp = ip->i_sbd;
154         struct buffer_head *dibh;
155         uint64_t lblock, dblock;
156         uint32_t extlen = 0;
157         unsigned int o;
158         int copied = 0;
159         int error = 0;
160
161         if (!size)
162                 return 0;
163
164         if (gfs2_is_stuffed(ip) &&
165             offset + size <= sdp->sd_sb.sb_bsize - sizeof(struct gfs2_dinode))
166                 return gfs2_dir_write_stuffed(ip, buf, (unsigned int)offset, size);
167
168         if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
169                 return -EINVAL;
170
171         if (gfs2_is_stuffed(ip)) {
172                 error = gfs2_unstuff_dinode(ip, NULL, NULL);
173                 if (error)
174                 return error;
175         }
176
177         lblock = offset;
178         o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
179
180         while (copied < size) {
181                 unsigned int amount;
182                 struct buffer_head *bh;
183                 int new;
184
185                 amount = size - copied;
186                 if (amount > sdp->sd_sb.sb_bsize - o)
187                         amount = sdp->sd_sb.sb_bsize - o;
188
189                 if (!extlen) {
190                         new = 1;
191                         error = gfs2_block_map(ip, lblock, &new, &dblock, &extlen);
192                         if (error)
193                                 goto fail;
194                         error = -EIO;
195                         if (gfs2_assert_withdraw(sdp, dblock))
196                                 goto fail;
197                 }
198
199                 error = gfs2_dir_get_buffer(ip, dblock, (amount == sdp->sd_jbsize) ? 1 : new, &bh);
200                 if (error)
201                         goto fail;
202
203                 gfs2_trans_add_bh(ip->i_gl, bh, 1);
204                 memcpy(bh->b_data + o, buf, amount);
205                 brelse(bh);
206                 if (error)
207                         goto fail;
208
209                 copied += amount;
210                 lblock++;
211                 dblock++;
212                 extlen--;
213
214                 o = sizeof(struct gfs2_meta_header);
215         }
216
217 out:
218         error = gfs2_meta_inode_buffer(ip, &dibh);
219         if (error)
220                 return error;
221
222         if (ip->i_di.di_size < offset + copied)
223                 ip->i_di.di_size = offset + copied;
224         ip->i_di.di_mtime = ip->i_di.di_ctime = get_seconds();
225
226         gfs2_trans_add_bh(ip->i_gl, dibh, 1);
227         gfs2_dinode_out(&ip->i_di, dibh->b_data);
228         brelse(dibh);
229
230         return copied;
231 fail:
232         if (copied)
233                 goto out;
234         return error;
235 }
236
237 static int gfs2_dir_read_stuffed(struct gfs2_inode *ip, char *buf,
238                                 unsigned int offset, unsigned int size)
239 {
240         struct buffer_head *dibh;
241         int error;
242
243         error = gfs2_meta_inode_buffer(ip, &dibh);
244         if (!error) {
245                 offset += sizeof(struct gfs2_dinode);
246                 memcpy(buf, dibh->b_data + offset, size);
247                 brelse(dibh);
248         }
249
250         return (error) ? error : size;
251 }
252
253
254 /**
255  * gfs2_dir_read_data - Read a data from a directory inode
256  * @ip: The GFS2 Inode
257  * @buf: The buffer to place result into
258  * @offset: File offset to begin jdata_readng from
259  * @size: Amount of data to transfer
260  *
261  * Returns: The amount of data actually copied or the error
262  */
263 static int gfs2_dir_read_data(struct gfs2_inode *ip, char *buf,
264                               uint64_t offset, unsigned int size)
265 {
266         struct gfs2_sbd *sdp = ip->i_sbd;
267         uint64_t lblock, dblock;
268         uint32_t extlen = 0;
269         unsigned int o;
270         int copied = 0;
271         int error = 0;
272
273         if (offset >= ip->i_di.di_size)
274                 return 0;
275
276         if ((offset + size) > ip->i_di.di_size)
277                 size = ip->i_di.di_size - offset;
278
279         if (!size)
280                 return 0;
281
282         if (gfs2_is_stuffed(ip))
283                 return gfs2_dir_read_stuffed(ip, buf, (unsigned int)offset, size);
284
285         if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
286                 return -EINVAL;
287
288         lblock = offset;
289         o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
290
291         while (copied < size) {
292                 unsigned int amount;
293                 struct buffer_head *bh;
294                 int new;
295
296                 amount = size - copied;
297                 if (amount > sdp->sd_sb.sb_bsize - o)
298                         amount = sdp->sd_sb.sb_bsize - o;
299
300                 if (!extlen) {
301                         new = 0;
302                         error = gfs2_block_map(ip, lblock, &new, &dblock, &extlen);
303                         if (error)
304                                 goto fail;
305                 }
306
307                 if (extlen > 1)
308                         gfs2_meta_ra(ip->i_gl, dblock, extlen);
309
310                 if (dblock) {
311                         error = gfs2_dir_get_buffer(ip, dblock, new, &bh);
312                         if (error)
313                                 goto fail;
314                         dblock++;
315                         extlen--;
316                 } else
317                         bh = NULL;
318
319                 memcpy(buf, bh->b_data + o, amount);
320                 brelse(bh);
321                 if (error)
322                         goto fail;
323
324                 copied += amount;
325                 lblock++;
326
327                 o = sizeof(struct gfs2_meta_header);
328         }
329
330         return copied;
331 fail:
332         return (copied) ? copied : error;
333 }
334
335 /**
336  * int gfs2_filecmp - Compare two filenames
337  * @file1: The first filename
338  * @file2: The second filename
339  * @len_of_file2: The length of the second file
340  *
341  * This routine compares two filenames and returns 1 if they are equal.
342  *
343  * Returns: 1 if the files are the same, otherwise 0.
344  */
345
346 int gfs2_filecmp(struct qstr *file1, char *file2, int len_of_file2)
347 {
348         if (file1->len != len_of_file2)
349                 return 0;
350         if (memcmp(file1->name, file2, file1->len))
351                 return 0;
352         return 1;
353 }
354
355 /**
356  * dirent_first - Return the first dirent
357  * @dip: the directory
358  * @bh: The buffer
359  * @dent: Pointer to list of dirents
360  *
361  * return first dirent whether bh points to leaf or stuffed dinode
362  *
363  * Returns: IS_LEAF, IS_DINODE, or -errno
364  */
365
366 static int dirent_first(struct gfs2_inode *dip, struct buffer_head *bh,
367                         struct gfs2_dirent **dent)
368 {
369         struct gfs2_meta_header *h = (struct gfs2_meta_header *)bh->b_data;
370
371         if (be16_to_cpu(h->mh_type) == GFS2_METATYPE_LF) {
372                 if (gfs2_meta_check(dip->i_sbd, bh))
373                         return -EIO;
374                 *dent = (struct gfs2_dirent *)(bh->b_data +
375                                                sizeof(struct gfs2_leaf));
376                 return IS_LEAF;
377         } else {
378                 if (gfs2_metatype_check(dip->i_sbd, bh, GFS2_METATYPE_DI))
379                         return -EIO;
380                 *dent = (struct gfs2_dirent *)(bh->b_data +
381                                                sizeof(struct gfs2_dinode));
382                 return IS_DINODE;
383         }
384 }
385
386 /**
387  * dirent_next - Next dirent
388  * @dip: the directory
389  * @bh: The buffer
390  * @dent: Pointer to list of dirents
391  *
392  * Returns: 0 on success, error code otherwise
393  */
394
395 static int dirent_next(struct gfs2_inode *dip, struct buffer_head *bh,
396                        struct gfs2_dirent **dent)
397 {
398         struct gfs2_dirent *tmp, *cur;
399         char *bh_end;
400         uint16_t cur_rec_len;
401
402         cur = *dent;
403         bh_end = bh->b_data + bh->b_size;
404         cur_rec_len = be16_to_cpu(cur->de_rec_len);
405
406         if ((char *)cur + cur_rec_len >= bh_end) {
407                 if ((char *)cur + cur_rec_len > bh_end) {
408                         gfs2_consist_inode(dip);
409                         return -EIO;
410                 }
411                 return -ENOENT;
412         }
413
414         tmp = (struct gfs2_dirent *)((char *)cur + cur_rec_len);
415
416         if ((char *)tmp + be16_to_cpu(tmp->de_rec_len) > bh_end) {
417                 gfs2_consist_inode(dip);
418                 return -EIO;
419         }
420         /* Only the first dent could ever have de_inum.no_addr == 0 */
421         if (!tmp->de_inum.no_addr) {
422                 gfs2_consist_inode(dip);
423                 return -EIO;
424         }
425
426         *dent = tmp;
427
428         return 0;
429 }
430
431 /**
432  * dirent_del - Delete a dirent
433  * @dip: The GFS2 inode
434  * @bh: The buffer
435  * @prev: The previous dirent
436  * @cur: The current dirent
437  *
438  */
439
440 static void dirent_del(struct gfs2_inode *dip, struct buffer_head *bh,
441                        struct gfs2_dirent *prev, struct gfs2_dirent *cur)
442 {
443         uint16_t cur_rec_len, prev_rec_len;
444
445         if (!cur->de_inum.no_addr) {
446                 gfs2_consist_inode(dip);
447                 return;
448         }
449
450         gfs2_trans_add_bh(dip->i_gl, bh, 1);
451
452         /* If there is no prev entry, this is the first entry in the block.
453            The de_rec_len is already as big as it needs to be.  Just zero
454            out the inode number and return.  */
455
456         if (!prev) {
457                 cur->de_inum.no_addr = 0;       /* No endianess worries */
458                 return;
459         }
460
461         /*  Combine this dentry with the previous one.  */
462
463         prev_rec_len = be16_to_cpu(prev->de_rec_len);
464         cur_rec_len = be16_to_cpu(cur->de_rec_len);
465
466         if ((char *)prev + prev_rec_len != (char *)cur)
467                 gfs2_consist_inode(dip);
468         if ((char *)cur + cur_rec_len > bh->b_data + bh->b_size)
469                 gfs2_consist_inode(dip);
470
471         prev_rec_len += cur_rec_len;
472         prev->de_rec_len = cpu_to_be16(prev_rec_len);
473 }
474
475 /**
476  * gfs2_dirent_alloc - Allocate a directory entry
477  * @dip: The GFS2 inode
478  * @bh: The buffer
479  * @name_len: The length of the name
480  * @dent_out: Pointer to list of dirents
481  *
482  * Returns: 0 on success, error code otherwise
483  */
484
485 int gfs2_dirent_alloc(struct gfs2_inode *dip, struct buffer_head *bh,
486                       int name_len, struct gfs2_dirent **dent_out)
487 {
488         struct gfs2_dirent *dent, *new;
489         unsigned int rec_len = GFS2_DIRENT_SIZE(name_len);
490         unsigned int entries = 0, offset = 0;
491         int type;
492
493         type = dirent_first(dip, bh, &dent);
494         if (type < 0)
495                 return type;
496
497         if (type == IS_LEAF) {
498                 struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
499                 entries = be16_to_cpu(leaf->lf_entries);
500                 offset = sizeof(struct gfs2_leaf);
501         } else {
502                 struct gfs2_dinode *dinode = (struct gfs2_dinode *)bh->b_data;
503                 entries = be32_to_cpu(dinode->di_entries);
504                 offset = sizeof(struct gfs2_dinode);
505         }
506
507         if (!entries) {
508                 if (dent->de_inum.no_addr) {
509                         gfs2_consist_inode(dip);
510                         return -EIO;
511                 }
512
513                 gfs2_trans_add_bh(dip->i_gl, bh, 1);
514
515                 dent->de_rec_len = bh->b_size - offset;
516                 dent->de_rec_len = cpu_to_be16(dent->de_rec_len);
517                 dent->de_name_len = name_len;
518
519                 *dent_out = dent;
520                 return 0;
521         }
522
523         do {
524                 uint16_t cur_rec_len;
525                 uint32_t cur_name_len;
526
527                 cur_rec_len = be16_to_cpu(dent->de_rec_len);
528                 cur_name_len = dent->de_name_len;
529
530                 if ((!dent->de_inum.no_addr && cur_rec_len >= rec_len) ||
531                     (cur_rec_len >= GFS2_DIRENT_SIZE(cur_name_len) + rec_len)) {
532                         gfs2_trans_add_bh(dip->i_gl, bh, 1);
533
534                         if (dent->de_inum.no_addr) {
535                                 new = (struct gfs2_dirent *)((char *)dent +
536                                                             GFS2_DIRENT_SIZE(cur_name_len));
537                                 memset(new, 0, sizeof(struct gfs2_dirent));
538
539                                 new->de_rec_len = cur_rec_len - GFS2_DIRENT_SIZE(cur_name_len);
540                                 new->de_rec_len = cpu_to_be16(new->de_rec_len);
541                                 new->de_name_len = name_len;
542
543                                 dent->de_rec_len = cur_rec_len - be16_to_cpu(new->de_rec_len);
544                                 dent->de_rec_len = cpu_to_be16(dent->de_rec_len);
545
546                                 *dent_out = new;
547                                 return 0;
548                         }
549
550                         dent->de_name_len = name_len;
551
552                         *dent_out = dent;
553                         return 0;
554                 }
555         } while (dirent_next(dip, bh, &dent) == 0);
556
557         return -ENOSPC;
558 }
559
560 /**
561  * dirent_fits - See if we can fit a entry in this buffer
562  * @dip: The GFS2 inode
563  * @bh: The buffer
564  * @name_len: The length of the name
565  *
566  * Returns: 1 if it can fit, 0 otherwise
567  */
568
569 static int dirent_fits(struct gfs2_inode *dip, struct buffer_head *bh,
570                        int name_len)
571 {
572         struct gfs2_dirent *dent;
573         unsigned int rec_len = GFS2_DIRENT_SIZE(name_len);
574         unsigned int entries = 0;
575         int type;
576
577         type = dirent_first(dip, bh, &dent);
578         if (type < 0)
579                 return type;
580
581         if (type == IS_LEAF) {
582                 struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
583                 entries = be16_to_cpu(leaf->lf_entries);
584         } else {
585                 struct gfs2_dinode *dinode = (struct gfs2_dinode *)bh->b_data;
586                 entries = be32_to_cpu(dinode->di_entries);
587         }
588
589         if (!entries)
590                 return 1;
591
592         do {
593                 uint16_t cur_rec_len;
594                 uint32_t cur_name_len;
595
596                 cur_rec_len = be16_to_cpu(dent->de_rec_len);
597                 cur_name_len = dent->de_name_len;
598
599                 if ((!dent->de_inum.no_addr && cur_rec_len >= rec_len) ||
600                     (cur_rec_len >= GFS2_DIRENT_SIZE(cur_name_len) + rec_len))
601                         return 1;
602         } while (dirent_next(dip, bh, &dent) == 0);
603
604         return 0;
605 }
606
607 static int leaf_search(struct gfs2_inode *dip, struct buffer_head *bh,
608                        struct qstr *filename, struct gfs2_dirent **dent_out,
609                        struct gfs2_dirent **dent_prev)
610 {
611         uint32_t hash;
612         struct gfs2_dirent *dent, *prev = NULL;
613         unsigned int entries = 0;
614         int type;
615
616         type = dirent_first(dip, bh, &dent);
617         if (type < 0)
618                 return type;
619
620         if (type == IS_LEAF) {
621                 struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
622                 entries = be16_to_cpu(leaf->lf_entries);
623         } else if (type == IS_DINODE) {
624                 struct gfs2_dinode *dinode = (struct gfs2_dinode *)bh->b_data;
625                 entries = be32_to_cpu(dinode->di_entries);
626         }
627
628         hash = gfs2_disk_hash(filename->name, filename->len);
629
630         do {
631                 if (!dent->de_inum.no_addr) {
632                         prev = dent;
633                         continue;
634                 }
635
636                 if (be32_to_cpu(dent->de_hash) == hash &&
637                     gfs2_filecmp(filename, (char *)(dent + 1),
638                                  dent->de_name_len)) {
639                         *dent_out = dent;
640                         if (dent_prev)
641                                 *dent_prev = prev;
642
643                         return 0;
644                 }
645
646                 prev = dent;
647         } while (dirent_next(dip, bh, &dent) == 0);
648
649         return -ENOENT;
650 }
651
652 static int get_leaf(struct gfs2_inode *dip, uint64_t leaf_no,
653                     struct buffer_head **bhp)
654 {
655         int error;
656
657         error = gfs2_meta_read(dip->i_gl, leaf_no, DIO_START | DIO_WAIT, bhp);
658         if (!error && gfs2_metatype_check(dip->i_sbd, *bhp, GFS2_METATYPE_LF))
659                 error = -EIO;
660
661         return error;
662 }
663
664 /**
665  * get_leaf_nr - Get a leaf number associated with the index
666  * @dip: The GFS2 inode
667  * @index:
668  * @leaf_out:
669  *
670  * Returns: 0 on success, error code otherwise
671  */
672
673 static int get_leaf_nr(struct gfs2_inode *dip, uint32_t index,
674                        uint64_t *leaf_out)
675 {
676         uint64_t leaf_no;
677         int error;
678
679         error = gfs2_dir_read_data(dip, (char *)&leaf_no,
680                                     index * sizeof(uint64_t),
681                                     sizeof(uint64_t));
682         if (error != sizeof(uint64_t))
683                 return (error < 0) ? error : -EIO;
684
685         *leaf_out = be64_to_cpu(leaf_no);
686
687         return 0;
688 }
689
690 static int get_first_leaf(struct gfs2_inode *dip, uint32_t index,
691                           struct buffer_head **bh_out)
692 {
693         uint64_t leaf_no;
694         int error;
695
696         error = get_leaf_nr(dip, index, &leaf_no);
697         if (!error)
698                 error = get_leaf(dip, leaf_no, bh_out);
699
700         return error;
701 }
702
703 static int get_next_leaf(struct gfs2_inode *dip, struct buffer_head *bh_in,
704                          struct buffer_head **bh_out)
705 {
706         struct gfs2_leaf *leaf;
707         int error;
708
709         leaf = (struct gfs2_leaf *)bh_in->b_data;
710
711         if (!leaf->lf_next)
712                 error = -ENOENT;
713         else
714                 error = get_leaf(dip, be64_to_cpu(leaf->lf_next), bh_out);
715
716         return error;
717 }
718
719 static int linked_leaf_search(struct gfs2_inode *dip, struct qstr *filename,
720                               struct gfs2_dirent **dent_out,
721                               struct gfs2_dirent **dent_prev,
722                               struct buffer_head **bh_out)
723 {
724         struct buffer_head *bh = NULL, *bh_next;
725         uint32_t hsize, index;
726         uint32_t hash;
727         int error;
728
729         hsize = 1 << dip->i_di.di_depth;
730         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
731                 gfs2_consist_inode(dip);
732                 return -EIO;
733         }
734
735         /*  Figure out the address of the leaf node.  */
736
737         hash = gfs2_disk_hash(filename->name, filename->len);
738         index = hash >> (32 - dip->i_di.di_depth);
739
740         error = get_first_leaf(dip, index, &bh_next);
741         if (error)
742                 return error;
743
744         /*  Find the entry  */
745
746         do {
747                 brelse(bh);
748
749                 bh = bh_next;
750
751                 error = leaf_search(dip, bh, filename, dent_out, dent_prev);
752                 switch (error) {
753                 case 0:
754                         *bh_out = bh;
755                         return 0;
756
757                 case -ENOENT:
758                         break;
759
760                 default:
761                         brelse(bh);
762                         return error;
763                 }
764
765                 error = get_next_leaf(dip, bh, &bh_next);
766         }
767         while (!error);
768
769         brelse(bh);
770
771         return error;
772 }
773
774 /**
775  * dir_make_exhash - Convert a stuffed directory into an ExHash directory
776  * @dip: The GFS2 inode
777  *
778  * Returns: 0 on success, error code otherwise
779  */
780
781 static int dir_make_exhash(struct gfs2_inode *dip)
782 {
783         struct gfs2_sbd *sdp = dip->i_sbd;
784         struct gfs2_dirent *dent;
785         struct buffer_head *bh, *dibh;
786         struct gfs2_leaf *leaf;
787         int y;
788         uint32_t x;
789         uint64_t *lp, bn;
790         int error;
791
792         error = gfs2_meta_inode_buffer(dip, &dibh);
793         if (error)
794                 return error;
795
796         /*  Allocate a new block for the first leaf node  */
797
798         bn = gfs2_alloc_meta(dip);
799
800         /*  Turn over a new leaf  */
801
802         bh = gfs2_meta_new(dip->i_gl, bn);
803         gfs2_trans_add_bh(dip->i_gl, bh, 1);
804         gfs2_metatype_set(bh, GFS2_METATYPE_LF, GFS2_FORMAT_LF);
805         gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));
806
807         /*  Fill in the leaf structure  */
808
809         leaf = (struct gfs2_leaf *)bh->b_data;
810
811         gfs2_assert(sdp, dip->i_di.di_entries < (1 << 16));
812
813         leaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
814         leaf->lf_entries = cpu_to_be16(dip->i_di.di_entries);
815
816         /*  Copy dirents  */
817
818         gfs2_buffer_copy_tail(bh, sizeof(struct gfs2_leaf), dibh,
819                              sizeof(struct gfs2_dinode));
820
821         /*  Find last entry  */
822
823         x = 0;
824         dirent_first(dip, bh, &dent);
825
826         do {
827                 if (!dent->de_inum.no_addr)
828                         continue;
829                 if (++x == dip->i_di.di_entries)
830                         break;
831         }
832         while (dirent_next(dip, bh, &dent) == 0);
833
834         /*  Adjust the last dirent's record length
835            (Remember that dent still points to the last entry.)  */
836
837         dent->de_rec_len = be16_to_cpu(dent->de_rec_len) +
838                 sizeof(struct gfs2_dinode) -
839                 sizeof(struct gfs2_leaf);
840         dent->de_rec_len = cpu_to_be16(dent->de_rec_len);
841
842         brelse(bh);
843
844         /*  We're done with the new leaf block, now setup the new
845             hash table.  */
846
847         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
848         gfs2_buffer_clear_tail(dibh, sizeof(struct gfs2_dinode));
849
850         lp = (uint64_t *)(dibh->b_data + sizeof(struct gfs2_dinode));
851
852         for (x = sdp->sd_hash_ptrs; x--; lp++)
853                 *lp = cpu_to_be64(bn);
854
855         dip->i_di.di_size = sdp->sd_sb.sb_bsize / 2;
856         dip->i_di.di_blocks++;
857         dip->i_di.di_flags |= GFS2_DIF_EXHASH;
858         dip->i_di.di_payload_format = 0;
859
860         for (x = sdp->sd_hash_ptrs, y = -1; x; x >>= 1, y++) ;
861         dip->i_di.di_depth = y;
862
863         gfs2_dinode_out(&dip->i_di, dibh->b_data);
864
865         brelse(dibh);
866
867         return 0;
868 }
869
870 /**
871  * dir_split_leaf - Split a leaf block into two
872  * @dip: The GFS2 inode
873  * @index:
874  * @leaf_no:
875  *
876  * Returns: 0 on success, error code on failure
877  */
878
879 static int dir_split_leaf(struct gfs2_inode *dip, uint32_t index,
880                           uint64_t leaf_no)
881 {
882         struct buffer_head *nbh, *obh, *dibh;
883         struct gfs2_leaf *nleaf, *oleaf;
884         struct gfs2_dirent *dent, *prev = NULL, *next = NULL, *new;
885         uint32_t start, len, half_len, divider;
886         uint64_t bn, *lp;
887         uint32_t name_len;
888         int x, moved = 0;
889         int error;
890
891         /*  Allocate the new leaf block  */
892
893         bn = gfs2_alloc_meta(dip);
894
895         /*  Get the new leaf block  */
896
897         nbh = gfs2_meta_new(dip->i_gl, bn);
898         gfs2_trans_add_bh(dip->i_gl, nbh, 1);
899         gfs2_metatype_set(nbh, GFS2_METATYPE_LF, GFS2_FORMAT_LF);
900         gfs2_buffer_clear_tail(nbh, sizeof(struct gfs2_meta_header));
901
902         nleaf = (struct gfs2_leaf *)nbh->b_data;
903
904         nleaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
905
906         /*  Get the old leaf block  */
907
908         error = get_leaf(dip, leaf_no, &obh);
909         if (error)
910                 goto fail;
911
912         gfs2_trans_add_bh(dip->i_gl, obh, 1);
913
914         oleaf = (struct gfs2_leaf *)obh->b_data;
915
916         /*  Compute the start and len of leaf pointers in the hash table.  */
917
918         len = 1 << (dip->i_di.di_depth - be16_to_cpu(oleaf->lf_depth));
919         half_len = len >> 1;
920         if (!half_len) {
921                 gfs2_consist_inode(dip);
922                 error = -EIO;
923                 goto fail_brelse;
924         }
925
926         start = (index & ~(len - 1));
927
928         /* Change the pointers.
929            Don't bother distinguishing stuffed from non-stuffed.
930            This code is complicated enough already. */
931
932         lp = kcalloc(half_len, sizeof(uint64_t), GFP_KERNEL | __GFP_NOFAIL);
933
934         error = gfs2_dir_read_data(dip, (char *)lp, start * sizeof(uint64_t),
935                                     half_len * sizeof(uint64_t));
936         if (error != half_len * sizeof(uint64_t)) {
937                 if (error >= 0)
938                         error = -EIO;
939                 goto fail_lpfree;
940         }
941
942         /*  Change the pointers  */
943
944         for (x = 0; x < half_len; x++)
945                 lp[x] = cpu_to_be64(bn);
946
947         error = gfs2_dir_write_data(dip, (char *)lp, start * sizeof(uint64_t),
948                                      half_len * sizeof(uint64_t));
949         if (error != half_len * sizeof(uint64_t)) {
950                 if (error >= 0)
951                         error = -EIO;
952                 goto fail_lpfree;
953         }
954
955         kfree(lp);
956
957         /*  Compute the divider  */
958
959         divider = (start + half_len) << (32 - dip->i_di.di_depth);
960
961         /*  Copy the entries  */
962
963         dirent_first(dip, obh, &dent);
964
965         do {
966                 next = dent;
967                 if (dirent_next(dip, obh, &next))
968                         next = NULL;
969
970                 if (dent->de_inum.no_addr &&
971                     be32_to_cpu(dent->de_hash) < divider) {
972                         name_len = dent->de_name_len;
973
974                         gfs2_dirent_alloc(dip, nbh, name_len, &new);
975
976                         new->de_inum = dent->de_inum; /* No endian worries */
977                         new->de_hash = dent->de_hash; /* No endian worries */
978                         new->de_type = dent->de_type; /* No endian worries */
979                         memcpy((char *)(new + 1), (char *)(dent + 1),
980                                name_len);
981
982                         nleaf->lf_entries = be16_to_cpu(nleaf->lf_entries)+1;
983                         nleaf->lf_entries = cpu_to_be16(nleaf->lf_entries);
984
985                         dirent_del(dip, obh, prev, dent);
986
987                         if (!oleaf->lf_entries)
988                                 gfs2_consist_inode(dip);
989                         oleaf->lf_entries = be16_to_cpu(oleaf->lf_entries)-1;
990                         oleaf->lf_entries = cpu_to_be16(oleaf->lf_entries);
991
992                         if (!prev)
993                                 prev = dent;
994
995                         moved = 1;
996                 } else
997                         prev = dent;
998
999                 dent = next;
1000         }
1001         while (dent);
1002
1003         /* If none of the entries got moved into the new leaf,
1004            artificially fill in the first entry. */
1005
1006         if (!moved) {
1007                 gfs2_dirent_alloc(dip, nbh, 0, &new);
1008                 new->de_inum.no_addr = 0;
1009         }
1010
1011         oleaf->lf_depth = be16_to_cpu(oleaf->lf_depth) + 1;
1012         oleaf->lf_depth = cpu_to_be16(oleaf->lf_depth);
1013         nleaf->lf_depth = oleaf->lf_depth;
1014
1015         error = gfs2_meta_inode_buffer(dip, &dibh);
1016         if (!gfs2_assert_withdraw(dip->i_sbd, !error)) {
1017                 dip->i_di.di_blocks++;
1018                 gfs2_dinode_out(&dip->i_di, dibh->b_data);
1019                 brelse(dibh);
1020         }
1021
1022         brelse(obh);
1023         brelse(nbh);
1024
1025         return error;
1026
1027  fail_lpfree:
1028         kfree(lp);
1029
1030  fail_brelse:
1031         brelse(obh);
1032
1033  fail:
1034         brelse(nbh);
1035         return error;
1036 }
1037
1038 /**
1039  * dir_double_exhash - Double size of ExHash table
1040  * @dip: The GFS2 dinode
1041  *
1042  * Returns: 0 on success, error code on failure
1043  */
1044
1045 static int dir_double_exhash(struct gfs2_inode *dip)
1046 {
1047         struct gfs2_sbd *sdp = dip->i_sbd;
1048         struct buffer_head *dibh;
1049         uint32_t hsize;
1050         uint64_t *buf;
1051         uint64_t *from, *to;
1052         uint64_t block;
1053         int x;
1054         int error = 0;
1055
1056         hsize = 1 << dip->i_di.di_depth;
1057         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
1058                 gfs2_consist_inode(dip);
1059                 return -EIO;
1060         }
1061
1062         /*  Allocate both the "from" and "to" buffers in one big chunk  */
1063
1064         buf = kcalloc(3, sdp->sd_hash_bsize, GFP_KERNEL | __GFP_NOFAIL);
1065
1066         for (block = dip->i_di.di_size >> sdp->sd_hash_bsize_shift; block--;) {
1067                 error = gfs2_dir_read_data(dip, (char *)buf,
1068                                             block * sdp->sd_hash_bsize,
1069                                             sdp->sd_hash_bsize);
1070                 if (error != sdp->sd_hash_bsize) {
1071                         if (error >= 0)
1072                                 error = -EIO;
1073                         goto fail;
1074                 }
1075
1076                 from = buf;
1077                 to = (uint64_t *)((char *)buf + sdp->sd_hash_bsize);
1078
1079                 for (x = sdp->sd_hash_ptrs; x--; from++) {
1080                         *to++ = *from;  /*  No endianess worries  */
1081                         *to++ = *from;
1082                 }
1083
1084                 error = gfs2_dir_write_data(dip,
1085                                              (char *)buf + sdp->sd_hash_bsize,
1086                                              block * sdp->sd_sb.sb_bsize,
1087                                              sdp->sd_sb.sb_bsize);
1088                 if (error != sdp->sd_sb.sb_bsize) {
1089                         if (error >= 0)
1090                                 error = -EIO;
1091                         goto fail;
1092                 }
1093         }
1094
1095         kfree(buf);
1096
1097         error = gfs2_meta_inode_buffer(dip, &dibh);
1098         if (!gfs2_assert_withdraw(sdp, !error)) {
1099                 dip->i_di.di_depth++;
1100                 gfs2_dinode_out(&dip->i_di, dibh->b_data);
1101                 brelse(dibh);
1102         }
1103
1104         return error;
1105
1106  fail:
1107         kfree(buf);
1108
1109         return error;
1110 }
1111
1112 /**
1113  * compare_dents - compare directory entries by hash value
1114  * @a: first dent
1115  * @b: second dent
1116  *
1117  * When comparing the hash entries of @a to @b:
1118  *   gt: returns 1
1119  *   lt: returns -1
1120  *   eq: returns 0
1121  */
1122
1123 static int compare_dents(const void *a, const void *b)
1124 {
1125         struct gfs2_dirent *dent_a, *dent_b;
1126         uint32_t hash_a, hash_b;
1127         int ret = 0;
1128
1129         dent_a = *(struct gfs2_dirent **)a;
1130         hash_a = dent_a->de_hash;
1131         hash_a = be32_to_cpu(hash_a);
1132
1133         dent_b = *(struct gfs2_dirent **)b;
1134         hash_b = dent_b->de_hash;
1135         hash_b = be32_to_cpu(hash_b);
1136
1137         if (hash_a > hash_b)
1138                 ret = 1;
1139         else if (hash_a < hash_b)
1140                 ret = -1;
1141         else {
1142                 unsigned int len_a = dent_a->de_name_len;
1143                 unsigned int len_b = dent_b->de_name_len;
1144
1145                 if (len_a > len_b)
1146                         ret = 1;
1147                 else if (len_a < len_b)
1148                         ret = -1;
1149                 else
1150                         ret = memcmp((char *)(dent_a + 1),
1151                                      (char *)(dent_b + 1),
1152                                      len_a);
1153         }
1154
1155         return ret;
1156 }
1157
1158 /**
1159  * do_filldir_main - read out directory entries
1160  * @dip: The GFS2 inode
1161  * @offset: The offset in the file to read from
1162  * @opaque: opaque data to pass to filldir
1163  * @filldir: The function to pass entries to
1164  * @darr: an array of struct gfs2_dirent pointers to read
1165  * @entries: the number of entries in darr
1166  * @copied: pointer to int that's non-zero if a entry has been copied out
1167  *
1168  * Jump through some hoops to make sure that if there are hash collsions,
1169  * they are read out at the beginning of a buffer.  We want to minimize
1170  * the possibility that they will fall into different readdir buffers or
1171  * that someone will want to seek to that location.
1172  *
1173  * Returns: errno, >0 on exception from filldir
1174  */
1175
1176 static int do_filldir_main(struct gfs2_inode *dip, uint64_t *offset,
1177                            void *opaque, gfs2_filldir_t filldir,
1178                            struct gfs2_dirent **darr, uint32_t entries,
1179                            int *copied)
1180 {
1181         struct gfs2_dirent *dent, *dent_next;
1182         struct gfs2_inum inum;
1183         uint64_t off, off_next;
1184         unsigned int x, y;
1185         int run = 0;
1186         int error = 0;
1187
1188         sort(darr, entries, sizeof(struct gfs2_dirent *), compare_dents, NULL);
1189
1190         dent_next = darr[0];
1191         off_next = be32_to_cpu(dent_next->de_hash);
1192         off_next = gfs2_disk_hash2offset(off_next);
1193
1194         for (x = 0, y = 1; x < entries; x++, y++) {
1195                 dent = dent_next;
1196                 off = off_next;
1197
1198                 if (y < entries) {
1199                         dent_next = darr[y];
1200                         off_next = be32_to_cpu(dent_next->de_hash);
1201                         off_next = gfs2_disk_hash2offset(off_next);
1202
1203                         if (off < *offset)
1204                                 continue;
1205                         *offset = off;
1206
1207                         if (off_next == off) {
1208                                 if (*copied && !run)
1209                                         return 1;
1210                                 run = 1;
1211                         } else
1212                                 run = 0;
1213                 } else {
1214                         if (off < *offset)
1215                                 continue;
1216                         *offset = off;
1217                 }
1218
1219                 gfs2_inum_in(&inum, (char *)&dent->de_inum);
1220
1221                 error = filldir(opaque, (char *)(dent + 1),
1222                                 dent->de_name_len,
1223                                 off, &inum,
1224                                 dent->de_type);
1225                 if (error)
1226                         return 1;
1227
1228                 *copied = 1;
1229         }
1230
1231         /* Increment the *offset by one, so the next time we come into the
1232            do_filldir fxn, we get the next entry instead of the last one in the
1233            current leaf */
1234
1235         (*offset)++;
1236
1237         return 0;
1238 }
1239
1240 /**
1241  * do_filldir_single - Read directory entries out of a single block
1242  * @dip: The GFS2 inode
1243  * @offset: The offset in the file to read from
1244  * @opaque: opaque data to pass to filldir
1245  * @filldir: The function to pass entries to
1246  * @bh: the block
1247  * @entries: the number of entries in the block
1248  * @copied: pointer to int that's non-zero if a entry has been copied out
1249  *
1250  * Returns: errno, >0 on exception from filldir
1251  */
1252
1253 static int do_filldir_single(struct gfs2_inode *dip, uint64_t *offset,
1254                              void *opaque, gfs2_filldir_t filldir,
1255                              struct buffer_head *bh, uint32_t entries,
1256                              int *copied)
1257 {
1258         struct gfs2_dirent **darr;
1259         struct gfs2_dirent *de;
1260         unsigned int e = 0;
1261         int error;
1262
1263         if (!entries)
1264                 return 0;
1265
1266         darr = kcalloc(entries, sizeof(struct gfs2_dirent *), GFP_KERNEL);
1267         if (!darr)
1268                 return -ENOMEM;
1269
1270         dirent_first(dip, bh, &de);
1271         do {
1272                 if (!de->de_inum.no_addr)
1273                         continue;
1274                 if (e >= entries) {
1275                         gfs2_consist_inode(dip);
1276                         error = -EIO;
1277                         goto out;
1278                 }
1279                 darr[e++] = de;
1280         }
1281         while (dirent_next(dip, bh, &de) == 0);
1282
1283         if (e != entries) {
1284                 gfs2_consist_inode(dip);
1285                 error = -EIO;
1286                 goto out;
1287         }
1288
1289         error = do_filldir_main(dip, offset, opaque, filldir, darr,
1290                                 entries, copied);
1291
1292  out:
1293         kfree(darr);
1294
1295         return error;
1296 }
1297
1298 /**
1299  * do_filldir_multi - Read directory entries out of a linked leaf list
1300  * @dip: The GFS2 inode
1301  * @offset: The offset in the file to read from
1302  * @opaque: opaque data to pass to filldir
1303  * @filldir: The function to pass entries to
1304  * @bh: the first leaf in the list
1305  * @copied: pointer to int that's non-zero if a entry has been copied out
1306  *
1307  * Returns: errno, >0 on exception from filldir
1308  */
1309
1310 static int do_filldir_multi(struct gfs2_inode *dip, uint64_t *offset,
1311                             void *opaque, gfs2_filldir_t filldir,
1312                             struct buffer_head *bh, int *copied)
1313 {
1314         struct buffer_head **larr = NULL;
1315         struct gfs2_dirent **darr;
1316         struct gfs2_leaf *leaf;
1317         struct buffer_head *tmp_bh;
1318         struct gfs2_dirent *de;
1319         unsigned int entries, e = 0;
1320         unsigned int leaves = 0, l = 0;
1321         unsigned int x;
1322         uint64_t ln;
1323         int error = 0;
1324
1325         /*  Count leaves and entries  */
1326
1327         leaf = (struct gfs2_leaf *)bh->b_data;
1328         entries = be16_to_cpu(leaf->lf_entries);
1329         ln = leaf->lf_next;
1330
1331         while (ln) {
1332                 ln = be64_to_cpu(ln);
1333
1334                 error = get_leaf(dip, ln, &tmp_bh);
1335                 if (error)
1336                         return error;
1337
1338                 leaf = (struct gfs2_leaf *)tmp_bh->b_data;
1339                 if (leaf->lf_entries) {
1340                         entries += be16_to_cpu(leaf->lf_entries);
1341                         leaves++;
1342                 }
1343                 ln = leaf->lf_next;
1344
1345                 brelse(tmp_bh);
1346         }
1347
1348         if (!entries)
1349                 return 0;
1350
1351         if (leaves) {
1352                 larr = kcalloc(leaves, sizeof(struct buffer_head *),GFP_KERNEL);
1353                 if (!larr)
1354                         return -ENOMEM;
1355         }
1356
1357         darr = kcalloc(entries, sizeof(struct gfs2_dirent *), GFP_KERNEL);
1358         if (!darr) {
1359                 kfree(larr);
1360                 return -ENOMEM;
1361         }
1362
1363         leaf = (struct gfs2_leaf *)bh->b_data;
1364         if (leaf->lf_entries) {
1365                 dirent_first(dip, bh, &de);
1366                 do {
1367                         if (!de->de_inum.no_addr)
1368                                 continue;
1369                         if (e >= entries) {
1370                                 gfs2_consist_inode(dip);
1371                                 error = -EIO;
1372                                 goto out;
1373                         }
1374                         darr[e++] = de;
1375                 }
1376                 while (dirent_next(dip, bh, &de) == 0);
1377         }
1378         ln = leaf->lf_next;
1379
1380         while (ln) {
1381                 ln = be64_to_cpu(ln);
1382
1383                 error = get_leaf(dip, ln, &tmp_bh);
1384                 if (error)
1385                         goto out;
1386
1387                 leaf = (struct gfs2_leaf *)tmp_bh->b_data;
1388                 if (leaf->lf_entries) {
1389                         dirent_first(dip, tmp_bh, &de);
1390                         do {
1391                                 if (!de->de_inum.no_addr)
1392                                         continue;
1393                                 if (e >= entries) {
1394                                         gfs2_consist_inode(dip);
1395                                         error = -EIO;
1396                                         goto out;
1397                                 }
1398                                 darr[e++] = de;
1399                         }
1400                         while (dirent_next(dip, tmp_bh, &de) == 0);
1401
1402                         larr[l++] = tmp_bh;
1403
1404                         ln = leaf->lf_next;
1405                 } else {
1406                         ln = leaf->lf_next;
1407                         brelse(tmp_bh);
1408                 }
1409         }
1410
1411         if (gfs2_assert_withdraw(dip->i_sbd, l == leaves)) {
1412                 error = -EIO;
1413                 goto out;
1414         }
1415         if (e != entries) {
1416                 gfs2_consist_inode(dip);
1417                 error = -EIO;
1418                 goto out;
1419         }
1420
1421         error = do_filldir_main(dip, offset, opaque, filldir, darr,
1422                                 entries, copied);
1423
1424  out:
1425         kfree(darr);
1426         for (x = 0; x < l; x++)
1427                 brelse(larr[x]);
1428         kfree(larr);
1429
1430         return error;
1431 }
1432
1433 /**
1434  * dir_e_search - Search exhash (leaf) dir for inode matching name
1435  * @dip: The GFS2 inode
1436  * @filename: Filename string
1437  * @inode: If non-NULL, function fills with formal inode # and block address
1438  * @type: If non-NULL, function fills with DT_... dinode type
1439  *
1440  * Returns:
1441  */
1442
1443 static int dir_e_search(struct gfs2_inode *dip, struct qstr *filename,
1444                         struct gfs2_inum *inum, unsigned int *type)
1445 {
1446         struct buffer_head *bh;
1447         struct gfs2_dirent *dent;
1448         int error;
1449
1450         error = linked_leaf_search(dip, filename, &dent, NULL, &bh);
1451         if (error)
1452                 return error;
1453
1454         if (inum)
1455                 gfs2_inum_in(inum, (char *)&dent->de_inum);
1456         if (type)
1457                 *type = dent->de_type;
1458
1459         brelse(bh);
1460
1461         return 0;
1462 }
1463
1464 static int dir_e_add(struct gfs2_inode *dip, struct qstr *filename,
1465                      struct gfs2_inum *inum, unsigned int type)
1466 {
1467         struct buffer_head *bh, *nbh, *dibh;
1468         struct gfs2_leaf *leaf, *nleaf;
1469         struct gfs2_dirent *dent;
1470         uint32_t hsize, index;
1471         uint32_t hash;
1472         uint64_t leaf_no, bn;
1473         int error;
1474
1475  restart:
1476         hsize = 1 << dip->i_di.di_depth;
1477         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
1478                 gfs2_consist_inode(dip);
1479                 return -EIO;
1480         }
1481
1482         /*  Figure out the address of the leaf node.  */
1483
1484         hash = gfs2_disk_hash(filename->name, filename->len);
1485         index = hash >> (32 - dip->i_di.di_depth);
1486
1487         error = get_leaf_nr(dip, index, &leaf_no);
1488         if (error)
1489                 return error;
1490
1491         /*  Add entry to the leaf  */
1492
1493         for (;;) {
1494                 error = get_leaf(dip, leaf_no, &bh);
1495                 if (error)
1496                         return error;
1497
1498                 leaf = (struct gfs2_leaf *)bh->b_data;
1499
1500                 if (gfs2_dirent_alloc(dip, bh, filename->len, &dent)) {
1501
1502                         if (be16_to_cpu(leaf->lf_depth) < dip->i_di.di_depth) {
1503                                 /* Can we split the leaf? */
1504
1505                                 brelse(bh);
1506
1507                                 error = dir_split_leaf(dip, index, leaf_no);
1508                                 if (error)
1509                                         return error;
1510
1511                                 goto restart;
1512
1513                         } else if (dip->i_di.di_depth < GFS2_DIR_MAX_DEPTH) {
1514                                 /* Can we double the hash table? */
1515
1516                                 brelse(bh);
1517
1518                                 error = dir_double_exhash(dip);
1519                                 if (error)
1520                                         return error;
1521
1522                                 goto restart;
1523
1524                         } else if (leaf->lf_next) {
1525                                 /* Can we try the next leaf in the list? */
1526                                 leaf_no = be64_to_cpu(leaf->lf_next);
1527                                 brelse(bh);
1528                                 continue;
1529
1530                         } else {
1531                                 /* Create a new leaf and add it to the list. */
1532
1533                                 bn = gfs2_alloc_meta(dip);
1534
1535                                 nbh = gfs2_meta_new(dip->i_gl, bn);
1536                                 gfs2_trans_add_bh(dip->i_gl, nbh, 1);
1537                                 gfs2_metatype_set(nbh,
1538                                                  GFS2_METATYPE_LF,
1539                                                  GFS2_FORMAT_LF);
1540                                 gfs2_buffer_clear_tail(nbh,
1541                                         sizeof(struct gfs2_meta_header));
1542
1543                                 gfs2_trans_add_bh(dip->i_gl, bh, 1);
1544                                 leaf->lf_next = cpu_to_be64(bn);
1545
1546                                 nleaf = (struct gfs2_leaf *)nbh->b_data;
1547                                 nleaf->lf_depth = leaf->lf_depth;
1548                                 nleaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
1549
1550                                 gfs2_dirent_alloc(dip, nbh, filename->len,
1551                                                   &dent);
1552
1553                                 dip->i_di.di_blocks++;
1554
1555                                 brelse(bh);
1556
1557                                 bh = nbh;
1558                                 leaf = nleaf;
1559                         }
1560                 }
1561
1562                 /* If the gfs2_dirent_alloc() succeeded, it pinned the "bh" */
1563
1564                 gfs2_inum_out(inum, (char *)&dent->de_inum);
1565                 dent->de_hash = cpu_to_be32(hash);
1566                 dent->de_type = type;
1567                 memcpy((char *)(dent + 1), filename->name, filename->len);
1568
1569                 leaf->lf_entries = be16_to_cpu(leaf->lf_entries) + 1;
1570                 leaf->lf_entries = cpu_to_be16(leaf->lf_entries);
1571
1572                 brelse(bh);
1573
1574                 error = gfs2_meta_inode_buffer(dip, &dibh);
1575                 if (error)
1576                         return error;
1577
1578                 dip->i_di.di_entries++;
1579                 dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1580
1581                 gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1582                 gfs2_dinode_out(&dip->i_di, dibh->b_data);
1583                 brelse(dibh);
1584
1585                 return 0;
1586         }
1587
1588         return -ENOENT;
1589 }
1590
1591 static int dir_e_del(struct gfs2_inode *dip, struct qstr *filename)
1592 {
1593         struct buffer_head *bh, *dibh;
1594         struct gfs2_dirent *dent, *prev;
1595         struct gfs2_leaf *leaf;
1596         unsigned int entries;
1597         int error;
1598
1599         error = linked_leaf_search(dip, filename, &dent, &prev, &bh);
1600         if (error == -ENOENT) {
1601                 gfs2_consist_inode(dip);
1602                 return -EIO;
1603         }
1604         if (error)
1605                 return error;
1606
1607         dirent_del(dip, bh, prev, dent); /* Pins bh */
1608
1609         leaf = (struct gfs2_leaf *)bh->b_data;
1610         entries = be16_to_cpu(leaf->lf_entries);
1611         if (!entries)
1612                 gfs2_consist_inode(dip);
1613         entries--;
1614         leaf->lf_entries = cpu_to_be16(entries);
1615
1616         brelse(bh);
1617
1618         error = gfs2_meta_inode_buffer(dip, &dibh);
1619         if (error)
1620                 return error;
1621
1622         if (!dip->i_di.di_entries)
1623                 gfs2_consist_inode(dip);
1624         dip->i_di.di_entries--;
1625         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1626
1627         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1628         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1629         brelse(dibh);
1630
1631         return 0;
1632 }
1633
1634 /**
1635  * dir_e_read - Reads the entries from a directory into a filldir buffer
1636  * @dip: dinode pointer
1637  * @offset: the hash of the last entry read shifted to the right once
1638  * @opaque: buffer for the filldir function to fill
1639  * @filldir: points to the filldir function to use
1640  *
1641  * Returns: errno
1642  */
1643
1644 static int dir_e_read(struct gfs2_inode *dip, uint64_t *offset, void *opaque,
1645                       gfs2_filldir_t filldir)
1646 {
1647         struct gfs2_sbd *sdp = dip->i_sbd;
1648         struct buffer_head *bh;
1649         struct gfs2_leaf leaf;
1650         uint32_t hsize, len;
1651         uint32_t ht_offset, lp_offset, ht_offset_cur = -1;
1652         uint32_t hash, index;
1653         uint64_t *lp;
1654         int copied = 0;
1655         int error = 0;
1656
1657         hsize = 1 << dip->i_di.di_depth;
1658         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
1659                 gfs2_consist_inode(dip);
1660                 return -EIO;
1661         }
1662
1663         hash = gfs2_dir_offset2hash(*offset);
1664         index = hash >> (32 - dip->i_di.di_depth);
1665
1666         lp = kmalloc(sdp->sd_hash_bsize, GFP_KERNEL);
1667         if (!lp)
1668                 return -ENOMEM;
1669
1670         while (index < hsize) {
1671                 lp_offset = index & (sdp->sd_hash_ptrs - 1);
1672                 ht_offset = index - lp_offset;
1673
1674                 if (ht_offset_cur != ht_offset) {
1675                         error = gfs2_dir_read_data(dip, (char *)lp,
1676                                                 ht_offset * sizeof(uint64_t),
1677                                                 sdp->sd_hash_bsize);
1678                         if (error != sdp->sd_hash_bsize) {
1679                                 if (error >= 0)
1680                                         error = -EIO;
1681                                 goto out;
1682                         }
1683                         ht_offset_cur = ht_offset;
1684                 }
1685
1686                 error = get_leaf(dip, be64_to_cpu(lp[lp_offset]), &bh);
1687                 if (error)
1688                         goto out;
1689
1690                 gfs2_leaf_in(&leaf, bh->b_data);
1691
1692                 if (leaf.lf_next)
1693                         error = do_filldir_multi(dip, offset, opaque, filldir,
1694                                                  bh, &copied);
1695                 else
1696                         error = do_filldir_single(dip, offset, opaque, filldir,
1697                                                   bh, leaf.lf_entries, &copied);
1698
1699                 brelse(bh);
1700
1701                 if (error) {
1702                         if (error > 0)
1703                                 error = 0;
1704                         goto out;
1705                 }
1706
1707                 len = 1 << (dip->i_di.di_depth - leaf.lf_depth);
1708                 index = (index & ~(len - 1)) + len;
1709         }
1710
1711  out:
1712         kfree(lp);
1713
1714         return error;
1715 }
1716
1717 static int dir_e_mvino(struct gfs2_inode *dip, struct qstr *filename,
1718                        struct gfs2_inum *inum, unsigned int new_type)
1719 {
1720         struct buffer_head *bh, *dibh;
1721         struct gfs2_dirent *dent;
1722         int error;
1723
1724         error = linked_leaf_search(dip, filename, &dent, NULL, &bh);
1725         if (error == -ENOENT) {
1726                 gfs2_consist_inode(dip);
1727                 return -EIO;
1728         }
1729         if (error)
1730                 return error;
1731
1732         gfs2_trans_add_bh(dip->i_gl, bh, 1);
1733
1734         gfs2_inum_out(inum, (char *)&dent->de_inum);
1735         dent->de_type = new_type;
1736
1737         brelse(bh);
1738
1739         error = gfs2_meta_inode_buffer(dip, &dibh);
1740         if (error)
1741                 return error;
1742
1743         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1744
1745         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1746         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1747         brelse(dibh);
1748
1749         return 0;
1750 }
1751
1752 /**
1753  * dir_l_search - Search linear (stuffed dinode) dir for inode matching name
1754  * @dip: The GFS2 inode
1755  * @filename: Filename string
1756  * @inode: If non-NULL, function fills with formal inode # and block address
1757  * @type: If non-NULL, function fills with DT_... dinode type
1758  *
1759  * Returns:
1760  */
1761
1762 static int dir_l_search(struct gfs2_inode *dip, struct qstr *filename,
1763                         struct gfs2_inum *inum, unsigned int *type)
1764 {
1765         struct buffer_head *dibh;
1766         struct gfs2_dirent *dent;
1767         int error;
1768
1769         if (!gfs2_is_stuffed(dip)) {
1770                 gfs2_consist_inode(dip);
1771                 return -EIO;
1772         }
1773
1774         error = gfs2_meta_inode_buffer(dip, &dibh);
1775         if (error)
1776                 return error;
1777
1778         error = leaf_search(dip, dibh, filename, &dent, NULL);
1779         if (!error) {
1780                 if (inum)
1781                         gfs2_inum_in(inum, (char *)&dent->de_inum);
1782                 if (type)
1783                         *type = dent->de_type;
1784         }
1785
1786         brelse(dibh);
1787
1788         return error;
1789 }
1790
1791 static int dir_l_add(struct gfs2_inode *dip, struct qstr *filename,
1792                      struct gfs2_inum *inum, unsigned int type)
1793 {
1794         struct buffer_head *dibh;
1795         struct gfs2_dirent *dent;
1796         int error;
1797
1798         if (!gfs2_is_stuffed(dip)) {
1799                 gfs2_consist_inode(dip);
1800                 return -EIO;
1801         }
1802
1803         error = gfs2_meta_inode_buffer(dip, &dibh);
1804         if (error)
1805                 return error;
1806
1807         if (gfs2_dirent_alloc(dip, dibh, filename->len, &dent)) {
1808                 brelse(dibh);
1809
1810                 error = dir_make_exhash(dip);
1811                 if (!error)
1812                         error = dir_e_add(dip, filename, inum, type);
1813
1814                 return error;
1815         }
1816
1817         /*  gfs2_dirent_alloc() pins  */
1818
1819         gfs2_inum_out(inum, (char *)&dent->de_inum);
1820         dent->de_hash = gfs2_disk_hash(filename->name, filename->len);
1821         dent->de_hash = cpu_to_be32(dent->de_hash);
1822         dent->de_type = type;
1823         memcpy((char *)(dent + 1), filename->name, filename->len);
1824
1825         dip->i_di.di_entries++;
1826         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1827
1828         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1829         brelse(dibh);
1830
1831         return 0;
1832 }
1833
1834 static int dir_l_del(struct gfs2_inode *dip, struct qstr *filename)
1835 {
1836         struct buffer_head *dibh;
1837         struct gfs2_dirent *dent, *prev;
1838         int error;
1839
1840         if (!gfs2_is_stuffed(dip)) {
1841                 gfs2_consist_inode(dip);
1842                 return -EIO;
1843         }
1844
1845         error = gfs2_meta_inode_buffer(dip, &dibh);
1846         if (error)
1847                 return error;
1848
1849         error = leaf_search(dip, dibh, filename, &dent, &prev);
1850         if (error == -ENOENT) {
1851                 gfs2_consist_inode(dip);
1852                 error = -EIO;
1853                 goto out;
1854         }
1855         if (error)
1856                 goto out;
1857
1858         dirent_del(dip, dibh, prev, dent);
1859
1860         /*  dirent_del() pins  */
1861
1862         if (!dip->i_di.di_entries)
1863                 gfs2_consist_inode(dip);
1864         dip->i_di.di_entries--;
1865
1866         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1867
1868         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1869
1870  out:
1871         brelse(dibh);
1872
1873         return error;
1874 }
1875
1876 static int dir_l_read(struct gfs2_inode *dip, uint64_t *offset, void *opaque,
1877                       gfs2_filldir_t filldir)
1878 {
1879         struct buffer_head *dibh;
1880         int copied = 0;
1881         int error;
1882
1883         if (!gfs2_is_stuffed(dip)) {
1884                 gfs2_consist_inode(dip);
1885                 return -EIO;
1886         }
1887
1888         if (!dip->i_di.di_entries)
1889                 return 0;
1890
1891         error = gfs2_meta_inode_buffer(dip, &dibh);
1892         if (error)
1893                 return error;
1894
1895         error = do_filldir_single(dip, offset,
1896                                   opaque, filldir,
1897                                   dibh, dip->i_di.di_entries,
1898                                   &copied);
1899         if (error > 0)
1900                 error = 0;
1901
1902         brelse(dibh);
1903
1904         return error;
1905 }
1906
1907 static int dir_l_mvino(struct gfs2_inode *dip, struct qstr *filename,
1908                        struct gfs2_inum *inum, unsigned int new_type)
1909 {
1910         struct buffer_head *dibh;
1911         struct gfs2_dirent *dent;
1912         int error;
1913
1914         if (!gfs2_is_stuffed(dip)) {
1915                 gfs2_consist_inode(dip);
1916                 return -EIO;
1917         }
1918
1919         error = gfs2_meta_inode_buffer(dip, &dibh);
1920         if (error)
1921                 return error;
1922
1923         error = leaf_search(dip, dibh, filename, &dent, NULL);
1924         if (error == -ENOENT) {
1925                 gfs2_consist_inode(dip);
1926                 error = -EIO;
1927                 goto out;
1928         }
1929         if (error)
1930                 goto out;
1931
1932         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1933
1934         gfs2_inum_out(inum, (char *)&dent->de_inum);
1935         dent->de_type = new_type;
1936
1937         dip->i_di.di_mtime = dip->i_di.di_ctime = get_seconds();
1938
1939         gfs2_dinode_out(&dip->i_di, dibh->b_data);
1940
1941  out:
1942         brelse(dibh);
1943
1944         return error;
1945 }
1946
1947 /**
1948  * gfs2_dir_search - Search a directory
1949  * @dip: The GFS2 inode
1950  * @filename:
1951  * @inode:
1952  *
1953  * This routine searches a directory for a file or another directory.
1954  * Assumes a glock is held on dip.
1955  *
1956  * Returns: errno
1957  */
1958
1959 int gfs2_dir_search(struct gfs2_inode *dip, struct qstr *filename,
1960                     struct gfs2_inum *inum, unsigned int *type)
1961 {
1962         int error;
1963
1964         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
1965                 error = dir_e_search(dip, filename, inum, type);
1966         else
1967                 error = dir_l_search(dip, filename, inum, type);
1968
1969         return error;
1970 }
1971
1972 /**
1973  * gfs2_dir_add - Add new filename into directory
1974  * @dip: The GFS2 inode
1975  * @filename: The new name
1976  * @inode: The inode number of the entry
1977  * @type: The type of the entry
1978  *
1979  * Returns: 0 on success, error code on failure
1980  */
1981
1982 int gfs2_dir_add(struct gfs2_inode *dip, struct qstr *filename,
1983                  struct gfs2_inum *inum, unsigned int type)
1984 {
1985         int error;
1986
1987         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
1988                 error = dir_e_add(dip, filename, inum, type);
1989         else
1990                 error = dir_l_add(dip, filename, inum, type);
1991
1992         return error;
1993 }
1994
1995 /**
1996  * gfs2_dir_del - Delete a directory entry
1997  * @dip: The GFS2 inode
1998  * @filename: The filename
1999  *
2000  * Returns: 0 on success, error code on failure
2001  */
2002
2003 int gfs2_dir_del(struct gfs2_inode *dip, struct qstr *filename)
2004 {
2005         int error;
2006
2007         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
2008                 error = dir_e_del(dip, filename);
2009         else
2010                 error = dir_l_del(dip, filename);
2011
2012         return error;
2013 }
2014
2015 int gfs2_dir_read(struct gfs2_inode *dip, uint64_t *offset, void *opaque,
2016                   gfs2_filldir_t filldir)
2017 {
2018         int error;
2019
2020         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
2021                 error = dir_e_read(dip, offset, opaque, filldir);
2022         else
2023                 error = dir_l_read(dip, offset, opaque, filldir);
2024
2025         return error;
2026 }
2027
2028 /**
2029  * gfs2_dir_mvino - Change inode number of directory entry
2030  * @dip: The GFS2 inode
2031  * @filename:
2032  * @new_inode:
2033  *
2034  * This routine changes the inode number of a directory entry.  It's used
2035  * by rename to change ".." when a directory is moved.
2036  * Assumes a glock is held on dvp.
2037  *
2038  * Returns: errno
2039  */
2040
2041 int gfs2_dir_mvino(struct gfs2_inode *dip, struct qstr *filename,
2042                    struct gfs2_inum *inum, unsigned int new_type)
2043 {
2044         int error;
2045
2046         if (dip->i_di.di_flags & GFS2_DIF_EXHASH)
2047                 error = dir_e_mvino(dip, filename, inum, new_type);
2048         else
2049                 error = dir_l_mvino(dip, filename, inum, new_type);
2050
2051         return error;
2052 }
2053
2054 /**
2055  * foreach_leaf - call a function for each leaf in a directory
2056  * @dip: the directory
2057  * @lc: the function to call for each each
2058  * @data: private data to pass to it
2059  *
2060  * Returns: errno
2061  */
2062
2063 static int foreach_leaf(struct gfs2_inode *dip, leaf_call_t lc, void *data)
2064 {
2065         struct gfs2_sbd *sdp = dip->i_sbd;
2066         struct buffer_head *bh;
2067         struct gfs2_leaf leaf;
2068         uint32_t hsize, len;
2069         uint32_t ht_offset, lp_offset, ht_offset_cur = -1;
2070         uint32_t index = 0;
2071         uint64_t *lp;
2072         uint64_t leaf_no;
2073         int error = 0;
2074
2075         hsize = 1 << dip->i_di.di_depth;
2076         if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
2077                 gfs2_consist_inode(dip);
2078                 return -EIO;
2079         }
2080
2081         lp = kmalloc(sdp->sd_hash_bsize, GFP_KERNEL);
2082         if (!lp)
2083                 return -ENOMEM;
2084
2085         while (index < hsize) {
2086                 lp_offset = index & (sdp->sd_hash_ptrs - 1);
2087                 ht_offset = index - lp_offset;
2088
2089                 if (ht_offset_cur != ht_offset) {
2090                         error = gfs2_dir_read_data(dip, (char *)lp,
2091                                                 ht_offset * sizeof(uint64_t),
2092                                                 sdp->sd_hash_bsize);
2093                         if (error != sdp->sd_hash_bsize) {
2094                                 if (error >= 0)
2095                                         error = -EIO;
2096                                 goto out;
2097                         }
2098                         ht_offset_cur = ht_offset;
2099                 }
2100
2101                 leaf_no = be64_to_cpu(lp[lp_offset]);
2102                 if (leaf_no) {
2103                         error = get_leaf(dip, leaf_no, &bh);
2104                         if (error)
2105                                 goto out;
2106                         gfs2_leaf_in(&leaf, bh->b_data);
2107                         brelse(bh);
2108
2109                         len = 1 << (dip->i_di.di_depth - leaf.lf_depth);
2110
2111                         error = lc(dip, index, len, leaf_no, data);
2112                         if (error)
2113                                 goto out;
2114
2115                         index = (index & ~(len - 1)) + len;
2116                 } else
2117                         index++;
2118         }
2119
2120         if (index != hsize) {
2121                 gfs2_consist_inode(dip);
2122                 error = -EIO;
2123         }
2124
2125  out:
2126         kfree(lp);
2127
2128         return error;
2129 }
2130
2131 /**
2132  * leaf_dealloc - Deallocate a directory leaf
2133  * @dip: the directory
2134  * @index: the hash table offset in the directory
2135  * @len: the number of pointers to this leaf
2136  * @leaf_no: the leaf number
2137  * @data: not used
2138  *
2139  * Returns: errno
2140  */
2141
2142 static int leaf_dealloc(struct gfs2_inode *dip, uint32_t index, uint32_t len,
2143                         uint64_t leaf_no, void *data)
2144 {
2145         struct gfs2_sbd *sdp = dip->i_sbd;
2146         struct gfs2_leaf tmp_leaf;
2147         struct gfs2_rgrp_list rlist;
2148         struct buffer_head *bh, *dibh;
2149         uint64_t blk;
2150         unsigned int rg_blocks = 0, l_blocks = 0;
2151         char *ht;
2152         unsigned int x, size = len * sizeof(uint64_t);
2153         int error;
2154
2155         memset(&rlist, 0, sizeof(struct gfs2_rgrp_list));
2156
2157         ht = kzalloc(size, GFP_KERNEL);
2158         if (!ht)
2159                 return -ENOMEM;
2160
2161         gfs2_alloc_get(dip);
2162
2163         error = gfs2_quota_hold(dip, NO_QUOTA_CHANGE, NO_QUOTA_CHANGE);
2164         if (error)
2165                 goto out;
2166
2167         error = gfs2_rindex_hold(sdp, &dip->i_alloc.al_ri_gh);
2168         if (error)
2169                 goto out_qs;
2170
2171         /*  Count the number of leaves  */
2172
2173         for (blk = leaf_no; blk; blk = tmp_leaf.lf_next) {
2174                 error = get_leaf(dip, blk, &bh);
2175                 if (error)
2176                         goto out_rlist;
2177                 gfs2_leaf_in(&tmp_leaf, (bh)->b_data);
2178                 brelse(bh);
2179
2180                 gfs2_rlist_add(sdp, &rlist, blk);
2181                 l_blocks++;
2182         }
2183
2184         gfs2_rlist_alloc(&rlist, LM_ST_EXCLUSIVE, 0);
2185
2186         for (x = 0; x < rlist.rl_rgrps; x++) {
2187                 struct gfs2_rgrpd *rgd;
2188                 rgd = get_gl2rgd(rlist.rl_ghs[x].gh_gl);
2189                 rg_blocks += rgd->rd_ri.ri_length;
2190         }
2191
2192         error = gfs2_glock_nq_m(rlist.rl_rgrps, rlist.rl_ghs);
2193         if (error)
2194                 goto out_rlist;
2195
2196         error = gfs2_trans_begin(sdp,
2197                         rg_blocks + (DIV_RU(size, sdp->sd_jbsize) + 1) +
2198                         RES_DINODE + RES_STATFS + RES_QUOTA, l_blocks);
2199         if (error)
2200                 goto out_rg_gunlock;
2201
2202         for (blk = leaf_no; blk; blk = tmp_leaf.lf_next) {
2203                 error = get_leaf(dip, blk, &bh);
2204                 if (error)
2205                         goto out_end_trans;
2206                 gfs2_leaf_in(&tmp_leaf, bh->b_data);
2207                 brelse(bh);
2208
2209                 gfs2_free_meta(dip, blk, 1);
2210
2211                 if (!dip->i_di.di_blocks)
2212                         gfs2_consist_inode(dip);
2213                 dip->i_di.di_blocks--;
2214         }
2215
2216         error = gfs2_dir_write_data(dip, ht, index * sizeof(uint64_t), size);
2217         if (error != size) {
2218                 if (error >= 0)
2219                         error = -EIO;
2220                 goto out_end_trans;
2221         }
2222
2223         error = gfs2_meta_inode_buffer(dip, &dibh);
2224         if (error)
2225                 goto out_end_trans;
2226
2227         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
2228         gfs2_dinode_out(&dip->i_di, dibh->b_data);
2229         brelse(dibh);
2230
2231  out_end_trans:
2232         gfs2_trans_end(sdp);
2233
2234  out_rg_gunlock:
2235         gfs2_glock_dq_m(rlist.rl_rgrps, rlist.rl_ghs);
2236
2237  out_rlist:
2238         gfs2_rlist_free(&rlist);
2239         gfs2_glock_dq_uninit(&dip->i_alloc.al_ri_gh);
2240
2241  out_qs:
2242         gfs2_quota_unhold(dip);
2243
2244  out:
2245         gfs2_alloc_put(dip);
2246         kfree(ht);
2247
2248         return error;
2249 }
2250
2251 /**
2252  * gfs2_dir_exhash_dealloc - free all the leaf blocks in a directory
2253  * @dip: the directory
2254  *
2255  * Dealloc all on-disk directory leaves to FREEMETA state
2256  * Change on-disk inode type to "regular file"
2257  *
2258  * Returns: errno
2259  */
2260
2261 int gfs2_dir_exhash_dealloc(struct gfs2_inode *dip)
2262 {
2263         struct gfs2_sbd *sdp = dip->i_sbd;
2264         struct buffer_head *bh;
2265         int error;
2266
2267         /* Dealloc on-disk leaves to FREEMETA state */
2268         error = foreach_leaf(dip, leaf_dealloc, NULL);
2269         if (error)
2270                 return error;
2271
2272         /* Make this a regular file in case we crash.
2273            (We don't want to free these blocks a second time.)  */
2274
2275         error = gfs2_trans_begin(sdp, RES_DINODE, 0);
2276         if (error)
2277                 return error;
2278
2279         error = gfs2_meta_inode_buffer(dip, &bh);
2280         if (!error) {
2281                 gfs2_trans_add_bh(dip->i_gl, bh, 1);
2282                 ((struct gfs2_dinode *)bh->b_data)->di_mode = cpu_to_be32(S_IFREG);
2283                 brelse(bh);
2284         }
2285
2286         gfs2_trans_end(sdp);
2287
2288         return error;
2289 }
2290
2291 /**
2292  * gfs2_diradd_alloc_required - find if adding entry will require an allocation
2293  * @ip: the file being written to
2294  * @filname: the filename that's going to be added
2295  * @alloc_required: set to 1 if an alloc is required, 0 otherwise
2296  *
2297  * Returns: errno
2298  */
2299
2300 int gfs2_diradd_alloc_required(struct gfs2_inode *dip, struct qstr *filename,
2301                                int *alloc_required)
2302 {
2303         struct buffer_head *bh = NULL, *bh_next;
2304         uint32_t hsize, hash, index;
2305         int error = 0;
2306
2307         *alloc_required = 0;
2308
2309         if (dip->i_di.di_flags & GFS2_DIF_EXHASH) {
2310                 hsize = 1 << dip->i_di.di_depth;
2311                 if (hsize * sizeof(uint64_t) != dip->i_di.di_size) {
2312                         gfs2_consist_inode(dip);
2313                         return -EIO;
2314                 }
2315
2316                 hash = gfs2_disk_hash(filename->name, filename->len);
2317                 index = hash >> (32 - dip->i_di.di_depth);
2318
2319                 error = get_first_leaf(dip, index, &bh_next);
2320                 if (error)
2321                         return error;
2322
2323                 do {
2324                         brelse(bh);
2325
2326                         bh = bh_next;
2327
2328                         if (dirent_fits(dip, bh, filename->len))
2329                                 break;
2330
2331                         error = get_next_leaf(dip, bh, &bh_next);
2332                         if (error == -ENOENT) {
2333                                 *alloc_required = 1;
2334                                 error = 0;
2335                                 break;
2336                         }
2337                 }
2338                 while (!error);
2339
2340                 brelse(bh);
2341         } else {
2342                 error = gfs2_meta_inode_buffer(dip, &bh);
2343                 if (error)
2344                         return error;
2345
2346                 if (!dirent_fits(dip, bh, filename->len))
2347                         *alloc_required = 1;
2348
2349                 brelse(bh);
2350         }
2351
2352         return error;
2353 }
2354