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