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