GFS2: Make resource groups "append only" during life of fs
[linux-3.10.git] / fs / gfs2 / dir.c
1 /*
2  * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
3  * Copyright (C) 2004-2006 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 version 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_diskflags & 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
46  * block pointer in the array that points to the same leaf. In fact, when a
47  * directory is first converted from linear to exhash, all of the pointers
48  * point to the 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/slab.h>
57 #include <linux/spinlock.h>
58 #include <linux/buffer_head.h>
59 #include <linux/sort.h>
60 #include <linux/gfs2_ondisk.h>
61 #include <linux/crc32.h>
62 #include <linux/vmalloc.h>
63
64 #include "gfs2.h"
65 #include "incore.h"
66 #include "dir.h"
67 #include "glock.h"
68 #include "inode.h"
69 #include "meta_io.h"
70 #include "quota.h"
71 #include "rgrp.h"
72 #include "trans.h"
73 #include "bmap.h"
74 #include "util.h"
75
76 #define IS_LEAF     1 /* Hashed (leaf) directory */
77 #define IS_DINODE   2 /* Linear (stuffed dinode block) directory */
78
79 #define gfs2_disk_hash2offset(h) (((u64)(h)) >> 1)
80 #define gfs2_dir_offset2hash(p) ((u32)(((u64)(p)) << 1))
81
82 struct qstr gfs2_qdot __read_mostly;
83 struct qstr gfs2_qdotdot __read_mostly;
84
85 typedef int (*gfs2_dscan_t)(const struct gfs2_dirent *dent,
86                             const struct qstr *name, void *opaque);
87
88 int gfs2_dir_get_new_buffer(struct gfs2_inode *ip, u64 block,
89                             struct buffer_head **bhp)
90 {
91         struct buffer_head *bh;
92
93         bh = gfs2_meta_new(ip->i_gl, block);
94         gfs2_trans_add_bh(ip->i_gl, bh, 1);
95         gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD);
96         gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));
97         *bhp = bh;
98         return 0;
99 }
100
101 static int gfs2_dir_get_existing_buffer(struct gfs2_inode *ip, u64 block,
102                                         struct buffer_head **bhp)
103 {
104         struct buffer_head *bh;
105         int error;
106
107         error = gfs2_meta_read(ip->i_gl, block, DIO_WAIT, &bh);
108         if (error)
109                 return error;
110         if (gfs2_metatype_check(GFS2_SB(&ip->i_inode), bh, GFS2_METATYPE_JD)) {
111                 brelse(bh);
112                 return -EIO;
113         }
114         *bhp = bh;
115         return 0;
116 }
117
118 static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf,
119                                   unsigned int offset, unsigned int size)
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_dinode), buf, size);
130         if (ip->i_inode.i_size < offset + size)
131                 i_size_write(&ip->i_inode, offset + size);
132         ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;
133         gfs2_dinode_out(ip, 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                                u64 offset, unsigned int size)
153 {
154         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
155         struct buffer_head *dibh;
156         u64 lblock, dblock;
157         u32 extlen = 0;
158         unsigned int o;
159         int copied = 0;
160         int error = 0;
161         int new = 0;
162
163         if (!size)
164                 return 0;
165
166         if (gfs2_is_stuffed(ip) &&
167             offset + size <= sdp->sd_sb.sb_bsize - sizeof(struct gfs2_dinode))
168                 return gfs2_dir_write_stuffed(ip, buf, (unsigned int)offset,
169                                               size);
170
171         if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
172                 return -EINVAL;
173
174         if (gfs2_is_stuffed(ip)) {
175                 error = gfs2_unstuff_dinode(ip, NULL);
176                 if (error)
177                         return error;
178         }
179
180         lblock = offset;
181         o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
182
183         while (copied < size) {
184                 unsigned int amount;
185                 struct buffer_head *bh;
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_extent_map(&ip->i_inode, lblock, &new,
194                                                 &dblock, &extlen);
195                         if (error)
196                                 goto fail;
197                         error = -EIO;
198                         if (gfs2_assert_withdraw(sdp, dblock))
199                                 goto fail;
200                 }
201
202                 if (amount == sdp->sd_jbsize || new)
203                         error = gfs2_dir_get_new_buffer(ip, dblock, &bh);
204                 else
205                         error = gfs2_dir_get_existing_buffer(ip, dblock, &bh);
206
207                 if (error)
208                         goto fail;
209
210                 gfs2_trans_add_bh(ip->i_gl, bh, 1);
211                 memcpy(bh->b_data + o, buf, amount);
212                 brelse(bh);
213
214                 buf += amount;
215                 copied += amount;
216                 lblock++;
217                 dblock++;
218                 extlen--;
219
220                 o = sizeof(struct gfs2_meta_header);
221         }
222
223 out:
224         error = gfs2_meta_inode_buffer(ip, &dibh);
225         if (error)
226                 return error;
227
228         if (ip->i_inode.i_size < offset + copied)
229                 i_size_write(&ip->i_inode, offset + copied);
230         ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;
231
232         gfs2_trans_add_bh(ip->i_gl, dibh, 1);
233         gfs2_dinode_out(ip, dibh->b_data);
234         brelse(dibh);
235
236         return copied;
237 fail:
238         if (copied)
239                 goto out;
240         return error;
241 }
242
243 static int gfs2_dir_read_stuffed(struct gfs2_inode *ip, __be64 *buf,
244                                  unsigned int size)
245 {
246         struct buffer_head *dibh;
247         int error;
248
249         error = gfs2_meta_inode_buffer(ip, &dibh);
250         if (!error) {
251                 memcpy(buf, dibh->b_data + sizeof(struct gfs2_dinode), 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  * @size: Amount of data to transfer
264  *
265  * Returns: The amount of data actually copied or the error
266  */
267 static int gfs2_dir_read_data(struct gfs2_inode *ip, __be64 *buf,
268                               unsigned int size)
269 {
270         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
271         u64 lblock, dblock;
272         u32 extlen = 0;
273         unsigned int o;
274         int copied = 0;
275         int error = 0;
276
277         if (gfs2_is_stuffed(ip))
278                 return gfs2_dir_read_stuffed(ip, buf, size);
279
280         if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip)))
281                 return -EINVAL;
282
283         lblock = 0;
284         o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header);
285
286         while (copied < size) {
287                 unsigned int amount;
288                 struct buffer_head *bh;
289                 int new;
290
291                 amount = size - copied;
292                 if (amount > sdp->sd_sb.sb_bsize - o)
293                         amount = sdp->sd_sb.sb_bsize - o;
294
295                 if (!extlen) {
296                         new = 0;
297                         error = gfs2_extent_map(&ip->i_inode, lblock, &new,
298                                                 &dblock, &extlen);
299                         if (error || !dblock)
300                                 goto fail;
301                         BUG_ON(extlen < 1);
302                         bh = gfs2_meta_ra(ip->i_gl, dblock, extlen);
303                 } else {
304                         error = gfs2_meta_read(ip->i_gl, dblock, DIO_WAIT, &bh);
305                         if (error)
306                                 goto fail;
307                 }
308                 error = gfs2_metatype_check(sdp, bh, GFS2_METATYPE_JD);
309                 if (error) {
310                         brelse(bh);
311                         goto fail;
312                 }
313                 dblock++;
314                 extlen--;
315                 memcpy(buf, bh->b_data + o, amount);
316                 brelse(bh);
317                 buf += (amount/sizeof(__be64));
318                 copied += amount;
319                 lblock++;
320                 o = sizeof(struct gfs2_meta_header);
321         }
322
323         return copied;
324 fail:
325         return (copied) ? copied : error;
326 }
327
328 /**
329  * gfs2_dir_get_hash_table - Get pointer to the dir hash table
330  * @ip: The inode in question
331  *
332  * Returns: The hash table or an error
333  */
334
335 static __be64 *gfs2_dir_get_hash_table(struct gfs2_inode *ip)
336 {
337         struct inode *inode = &ip->i_inode;
338         int ret;
339         u32 hsize;
340         __be64 *hc;
341
342         BUG_ON(!(ip->i_diskflags & GFS2_DIF_EXHASH));
343
344         hc = ip->i_hash_cache;
345         if (hc)
346                 return hc;
347
348         hsize = 1 << ip->i_depth;
349         hsize *= sizeof(__be64);
350         if (hsize != i_size_read(&ip->i_inode)) {
351                 gfs2_consist_inode(ip);
352                 return ERR_PTR(-EIO);
353         }
354
355         hc = kmalloc(hsize, GFP_NOFS);
356         ret = -ENOMEM;
357         if (hc == NULL)
358                 return ERR_PTR(-ENOMEM);
359
360         ret = gfs2_dir_read_data(ip, hc, hsize);
361         if (ret < 0) {
362                 kfree(hc);
363                 return ERR_PTR(ret);
364         }
365
366         spin_lock(&inode->i_lock);
367         if (ip->i_hash_cache)
368                 kfree(hc);
369         else
370                 ip->i_hash_cache = hc;
371         spin_unlock(&inode->i_lock);
372
373         return ip->i_hash_cache;
374 }
375
376 /**
377  * gfs2_dir_hash_inval - Invalidate dir hash
378  * @ip: The directory inode
379  *
380  * Must be called with an exclusive glock, or during glock invalidation.
381  */
382 void gfs2_dir_hash_inval(struct gfs2_inode *ip)
383 {
384         __be64 *hc = ip->i_hash_cache;
385         ip->i_hash_cache = NULL;
386         kfree(hc);
387 }
388
389 static inline int gfs2_dirent_sentinel(const struct gfs2_dirent *dent)
390 {
391         return dent->de_inum.no_addr == 0 || dent->de_inum.no_formal_ino == 0;
392 }
393
394 static inline int __gfs2_dirent_find(const struct gfs2_dirent *dent,
395                                      const struct qstr *name, int ret)
396 {
397         if (!gfs2_dirent_sentinel(dent) &&
398             be32_to_cpu(dent->de_hash) == name->hash &&
399             be16_to_cpu(dent->de_name_len) == name->len &&
400             memcmp(dent+1, name->name, name->len) == 0)
401                 return ret;
402         return 0;
403 }
404
405 static int gfs2_dirent_find(const struct gfs2_dirent *dent,
406                             const struct qstr *name,
407                             void *opaque)
408 {
409         return __gfs2_dirent_find(dent, name, 1);
410 }
411
412 static int gfs2_dirent_prev(const struct gfs2_dirent *dent,
413                             const struct qstr *name,
414                             void *opaque)
415 {
416         return __gfs2_dirent_find(dent, name, 2);
417 }
418
419 /*
420  * name->name holds ptr to start of block.
421  * name->len holds size of block.
422  */
423 static int gfs2_dirent_last(const struct gfs2_dirent *dent,
424                             const struct qstr *name,
425                             void *opaque)
426 {
427         const char *start = name->name;
428         const char *end = (const char *)dent + be16_to_cpu(dent->de_rec_len);
429         if (name->len == (end - start))
430                 return 1;
431         return 0;
432 }
433
434 static int gfs2_dirent_find_space(const struct gfs2_dirent *dent,
435                                   const struct qstr *name,
436                                   void *opaque)
437 {
438         unsigned required = GFS2_DIRENT_SIZE(name->len);
439         unsigned actual = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
440         unsigned totlen = be16_to_cpu(dent->de_rec_len);
441
442         if (gfs2_dirent_sentinel(dent))
443                 actual = 0;
444         if (totlen - actual >= required)
445                 return 1;
446         return 0;
447 }
448
449 struct dirent_gather {
450         const struct gfs2_dirent **pdent;
451         unsigned offset;
452 };
453
454 static int gfs2_dirent_gather(const struct gfs2_dirent *dent,
455                               const struct qstr *name,
456                               void *opaque)
457 {
458         struct dirent_gather *g = opaque;
459         if (!gfs2_dirent_sentinel(dent)) {
460                 g->pdent[g->offset++] = dent;
461         }
462         return 0;
463 }
464
465 /*
466  * Other possible things to check:
467  * - Inode located within filesystem size (and on valid block)
468  * - Valid directory entry type
469  * Not sure how heavy-weight we want to make this... could also check
470  * hash is correct for example, but that would take a lot of extra time.
471  * For now the most important thing is to check that the various sizes
472  * are correct.
473  */
474 static int gfs2_check_dirent(struct gfs2_dirent *dent, unsigned int offset,
475                              unsigned int size, unsigned int len, int first)
476 {
477         const char *msg = "gfs2_dirent too small";
478         if (unlikely(size < sizeof(struct gfs2_dirent)))
479                 goto error;
480         msg = "gfs2_dirent misaligned";
481         if (unlikely(offset & 0x7))
482                 goto error;
483         msg = "gfs2_dirent points beyond end of block";
484         if (unlikely(offset + size > len))
485                 goto error;
486         msg = "zero inode number";
487         if (unlikely(!first && gfs2_dirent_sentinel(dent)))
488                 goto error;
489         msg = "name length is greater than space in dirent";
490         if (!gfs2_dirent_sentinel(dent) &&
491             unlikely(sizeof(struct gfs2_dirent)+be16_to_cpu(dent->de_name_len) >
492                      size))
493                 goto error;
494         return 0;
495 error:
496         printk(KERN_WARNING "gfs2_check_dirent: %s (%s)\n", msg,
497                first ? "first in block" : "not first in block");
498         return -EIO;
499 }
500
501 static int gfs2_dirent_offset(const void *buf)
502 {
503         const struct gfs2_meta_header *h = buf;
504         int offset;
505
506         BUG_ON(buf == NULL);
507
508         switch(be32_to_cpu(h->mh_type)) {
509         case GFS2_METATYPE_LF:
510                 offset = sizeof(struct gfs2_leaf);
511                 break;
512         case GFS2_METATYPE_DI:
513                 offset = sizeof(struct gfs2_dinode);
514                 break;
515         default:
516                 goto wrong_type;
517         }
518         return offset;
519 wrong_type:
520         printk(KERN_WARNING "gfs2_scan_dirent: wrong block type %u\n",
521                be32_to_cpu(h->mh_type));
522         return -1;
523 }
524
525 static struct gfs2_dirent *gfs2_dirent_scan(struct inode *inode, void *buf,
526                                             unsigned int len, gfs2_dscan_t scan,
527                                             const struct qstr *name,
528                                             void *opaque)
529 {
530         struct gfs2_dirent *dent, *prev;
531         unsigned offset;
532         unsigned size;
533         int ret = 0;
534
535         ret = gfs2_dirent_offset(buf);
536         if (ret < 0)
537                 goto consist_inode;
538
539         offset = ret;
540         prev = NULL;
541         dent = buf + offset;
542         size = be16_to_cpu(dent->de_rec_len);
543         if (gfs2_check_dirent(dent, offset, size, len, 1))
544                 goto consist_inode;
545         do {
546                 ret = scan(dent, name, opaque);
547                 if (ret)
548                         break;
549                 offset += size;
550                 if (offset == len)
551                         break;
552                 prev = dent;
553                 dent = buf + offset;
554                 size = be16_to_cpu(dent->de_rec_len);
555                 if (gfs2_check_dirent(dent, offset, size, len, 0))
556                         goto consist_inode;
557         } while(1);
558
559         switch(ret) {
560         case 0:
561                 return NULL;
562         case 1:
563                 return dent;
564         case 2:
565                 return prev ? prev : dent;
566         default:
567                 BUG_ON(ret > 0);
568                 return ERR_PTR(ret);
569         }
570
571 consist_inode:
572         gfs2_consist_inode(GFS2_I(inode));
573         return ERR_PTR(-EIO);
574 }
575
576 static int dirent_check_reclen(struct gfs2_inode *dip,
577                                const struct gfs2_dirent *d, const void *end_p)
578 {
579         const void *ptr = d;
580         u16 rec_len = be16_to_cpu(d->de_rec_len);
581
582         if (unlikely(rec_len < sizeof(struct gfs2_dirent)))
583                 goto broken;
584         ptr += rec_len;
585         if (ptr < end_p)
586                 return rec_len;
587         if (ptr == end_p)
588                 return -ENOENT;
589 broken:
590         gfs2_consist_inode(dip);
591         return -EIO;
592 }
593
594 /**
595  * dirent_next - Next dirent
596  * @dip: the directory
597  * @bh: The buffer
598  * @dent: Pointer to list of dirents
599  *
600  * Returns: 0 on success, error code otherwise
601  */
602
603 static int dirent_next(struct gfs2_inode *dip, struct buffer_head *bh,
604                        struct gfs2_dirent **dent)
605 {
606         struct gfs2_dirent *cur = *dent, *tmp;
607         char *bh_end = bh->b_data + bh->b_size;
608         int ret;
609
610         ret = dirent_check_reclen(dip, cur, bh_end);
611         if (ret < 0)
612                 return ret;
613
614         tmp = (void *)cur + ret;
615         ret = dirent_check_reclen(dip, tmp, bh_end);
616         if (ret == -EIO)
617                 return ret;
618
619         /* Only the first dent could ever have de_inum.no_addr == 0 */
620         if (gfs2_dirent_sentinel(tmp)) {
621                 gfs2_consist_inode(dip);
622                 return -EIO;
623         }
624
625         *dent = tmp;
626         return 0;
627 }
628
629 /**
630  * dirent_del - Delete a dirent
631  * @dip: The GFS2 inode
632  * @bh: The buffer
633  * @prev: The previous dirent
634  * @cur: The current dirent
635  *
636  */
637
638 static void dirent_del(struct gfs2_inode *dip, struct buffer_head *bh,
639                        struct gfs2_dirent *prev, struct gfs2_dirent *cur)
640 {
641         u16 cur_rec_len, prev_rec_len;
642
643         if (gfs2_dirent_sentinel(cur)) {
644                 gfs2_consist_inode(dip);
645                 return;
646         }
647
648         gfs2_trans_add_bh(dip->i_gl, bh, 1);
649
650         /* If there is no prev entry, this is the first entry in the block.
651            The de_rec_len is already as big as it needs to be.  Just zero
652            out the inode number and return.  */
653
654         if (!prev) {
655                 cur->de_inum.no_addr = 0;
656                 cur->de_inum.no_formal_ino = 0;
657                 return;
658         }
659
660         /*  Combine this dentry with the previous one.  */
661
662         prev_rec_len = be16_to_cpu(prev->de_rec_len);
663         cur_rec_len = be16_to_cpu(cur->de_rec_len);
664
665         if ((char *)prev + prev_rec_len != (char *)cur)
666                 gfs2_consist_inode(dip);
667         if ((char *)cur + cur_rec_len > bh->b_data + bh->b_size)
668                 gfs2_consist_inode(dip);
669
670         prev_rec_len += cur_rec_len;
671         prev->de_rec_len = cpu_to_be16(prev_rec_len);
672 }
673
674 /*
675  * Takes a dent from which to grab space as an argument. Returns the
676  * newly created dent.
677  */
678 static struct gfs2_dirent *gfs2_init_dirent(struct inode *inode,
679                                             struct gfs2_dirent *dent,
680                                             const struct qstr *name,
681                                             struct buffer_head *bh)
682 {
683         struct gfs2_inode *ip = GFS2_I(inode);
684         struct gfs2_dirent *ndent;
685         unsigned offset = 0, totlen;
686
687         if (!gfs2_dirent_sentinel(dent))
688                 offset = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len));
689         totlen = be16_to_cpu(dent->de_rec_len);
690         BUG_ON(offset + name->len > totlen);
691         gfs2_trans_add_bh(ip->i_gl, bh, 1);
692         ndent = (struct gfs2_dirent *)((char *)dent + offset);
693         dent->de_rec_len = cpu_to_be16(offset);
694         gfs2_qstr2dirent(name, totlen - offset, ndent);
695         return ndent;
696 }
697
698 static struct gfs2_dirent *gfs2_dirent_alloc(struct inode *inode,
699                                              struct buffer_head *bh,
700                                              const struct qstr *name)
701 {
702         struct gfs2_dirent *dent;
703         dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
704                                 gfs2_dirent_find_space, name, NULL);
705         if (!dent || IS_ERR(dent))
706                 return dent;
707         return gfs2_init_dirent(inode, dent, name, bh);
708 }
709
710 static int get_leaf(struct gfs2_inode *dip, u64 leaf_no,
711                     struct buffer_head **bhp)
712 {
713         int error;
714
715         error = gfs2_meta_read(dip->i_gl, leaf_no, DIO_WAIT, bhp);
716         if (!error && gfs2_metatype_check(GFS2_SB(&dip->i_inode), *bhp, GFS2_METATYPE_LF)) {
717                 /* printk(KERN_INFO "block num=%llu\n", leaf_no); */
718                 error = -EIO;
719         }
720
721         return error;
722 }
723
724 /**
725  * get_leaf_nr - Get a leaf number associated with the index
726  * @dip: The GFS2 inode
727  * @index:
728  * @leaf_out:
729  *
730  * Returns: 0 on success, error code otherwise
731  */
732
733 static int get_leaf_nr(struct gfs2_inode *dip, u32 index,
734                        u64 *leaf_out)
735 {
736         __be64 *hash;
737
738         hash = gfs2_dir_get_hash_table(dip);
739         if (IS_ERR(hash))
740                 return PTR_ERR(hash);
741         *leaf_out = be64_to_cpu(*(hash + index));
742         return 0;
743 }
744
745 static int get_first_leaf(struct gfs2_inode *dip, u32 index,
746                           struct buffer_head **bh_out)
747 {
748         u64 leaf_no;
749         int error;
750
751         error = get_leaf_nr(dip, index, &leaf_no);
752         if (!error)
753                 error = get_leaf(dip, leaf_no, bh_out);
754
755         return error;
756 }
757
758 static struct gfs2_dirent *gfs2_dirent_search(struct inode *inode,
759                                               const struct qstr *name,
760                                               gfs2_dscan_t scan,
761                                               struct buffer_head **pbh)
762 {
763         struct buffer_head *bh;
764         struct gfs2_dirent *dent;
765         struct gfs2_inode *ip = GFS2_I(inode);
766         int error;
767
768         if (ip->i_diskflags & GFS2_DIF_EXHASH) {
769                 struct gfs2_leaf *leaf;
770                 unsigned hsize = 1 << ip->i_depth;
771                 unsigned index;
772                 u64 ln;
773                 if (hsize * sizeof(u64) != i_size_read(inode)) {
774                         gfs2_consist_inode(ip);
775                         return ERR_PTR(-EIO);
776                 }
777
778                 index = name->hash >> (32 - ip->i_depth);
779                 error = get_first_leaf(ip, index, &bh);
780                 if (error)
781                         return ERR_PTR(error);
782                 do {
783                         dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
784                                                 scan, name, NULL);
785                         if (dent)
786                                 goto got_dent;
787                         leaf = (struct gfs2_leaf *)bh->b_data;
788                         ln = be64_to_cpu(leaf->lf_next);
789                         brelse(bh);
790                         if (!ln)
791                                 break;
792
793                         error = get_leaf(ip, ln, &bh);
794                 } while(!error);
795
796                 return error ? ERR_PTR(error) : NULL;
797         }
798
799
800         error = gfs2_meta_inode_buffer(ip, &bh);
801         if (error)
802                 return ERR_PTR(error);
803         dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size, scan, name, NULL);
804 got_dent:
805         if (unlikely(dent == NULL || IS_ERR(dent))) {
806                 brelse(bh);
807                 bh = NULL;
808         }
809         *pbh = bh;
810         return dent;
811 }
812
813 static struct gfs2_leaf *new_leaf(struct inode *inode, struct buffer_head **pbh, u16 depth)
814 {
815         struct gfs2_inode *ip = GFS2_I(inode);
816         unsigned int n = 1;
817         u64 bn;
818         int error;
819         struct buffer_head *bh;
820         struct gfs2_leaf *leaf;
821         struct gfs2_dirent *dent;
822         struct qstr name = { .name = "", .len = 0, .hash = 0 };
823
824         error = gfs2_alloc_block(ip, &bn, &n);
825         if (error)
826                 return NULL;
827         bh = gfs2_meta_new(ip->i_gl, bn);
828         if (!bh)
829                 return NULL;
830
831         gfs2_trans_add_unrevoke(GFS2_SB(inode), bn, 1);
832         gfs2_trans_add_bh(ip->i_gl, bh, 1);
833         gfs2_metatype_set(bh, GFS2_METATYPE_LF, GFS2_FORMAT_LF);
834         leaf = (struct gfs2_leaf *)bh->b_data;
835         leaf->lf_depth = cpu_to_be16(depth);
836         leaf->lf_entries = 0;
837         leaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE);
838         leaf->lf_next = 0;
839         memset(leaf->lf_reserved, 0, sizeof(leaf->lf_reserved));
840         dent = (struct gfs2_dirent *)(leaf+1);
841         gfs2_qstr2dirent(&name, bh->b_size - sizeof(struct gfs2_leaf), dent);
842         *pbh = bh;
843         return leaf;
844 }
845
846 /**
847  * dir_make_exhash - Convert a stuffed directory into an ExHash directory
848  * @dip: The GFS2 inode
849  *
850  * Returns: 0 on success, error code otherwise
851  */
852
853 static int dir_make_exhash(struct inode *inode)
854 {
855         struct gfs2_inode *dip = GFS2_I(inode);
856         struct gfs2_sbd *sdp = GFS2_SB(inode);
857         struct gfs2_dirent *dent;
858         struct qstr args;
859         struct buffer_head *bh, *dibh;
860         struct gfs2_leaf *leaf;
861         int y;
862         u32 x;
863         __be64 *lp;
864         u64 bn;
865         int error;
866
867         error = gfs2_meta_inode_buffer(dip, &dibh);
868         if (error)
869                 return error;
870
871         /*  Turn over a new leaf  */
872
873         leaf = new_leaf(inode, &bh, 0);
874         if (!leaf)
875                 return -ENOSPC;
876         bn = bh->b_blocknr;
877
878         gfs2_assert(sdp, dip->i_entries < (1 << 16));
879         leaf->lf_entries = cpu_to_be16(dip->i_entries);
880
881         /*  Copy dirents  */
882
883         gfs2_buffer_copy_tail(bh, sizeof(struct gfs2_leaf), dibh,
884                              sizeof(struct gfs2_dinode));
885
886         /*  Find last entry  */
887
888         x = 0;
889         args.len = bh->b_size - sizeof(struct gfs2_dinode) +
890                    sizeof(struct gfs2_leaf);
891         args.name = bh->b_data;
892         dent = gfs2_dirent_scan(&dip->i_inode, bh->b_data, bh->b_size,
893                                 gfs2_dirent_last, &args, NULL);
894         if (!dent) {
895                 brelse(bh);
896                 brelse(dibh);
897                 return -EIO;
898         }
899         if (IS_ERR(dent)) {
900                 brelse(bh);
901                 brelse(dibh);
902                 return PTR_ERR(dent);
903         }
904
905         /*  Adjust the last dirent's record length
906            (Remember that dent still points to the last entry.)  */
907
908         dent->de_rec_len = cpu_to_be16(be16_to_cpu(dent->de_rec_len) +
909                 sizeof(struct gfs2_dinode) -
910                 sizeof(struct gfs2_leaf));
911
912         brelse(bh);
913
914         /*  We're done with the new leaf block, now setup the new
915             hash table.  */
916
917         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
918         gfs2_buffer_clear_tail(dibh, sizeof(struct gfs2_dinode));
919
920         lp = (__be64 *)(dibh->b_data + sizeof(struct gfs2_dinode));
921
922         for (x = sdp->sd_hash_ptrs; x--; lp++)
923                 *lp = cpu_to_be64(bn);
924
925         i_size_write(inode, sdp->sd_sb.sb_bsize / 2);
926         gfs2_add_inode_blocks(&dip->i_inode, 1);
927         dip->i_diskflags |= GFS2_DIF_EXHASH;
928
929         for (x = sdp->sd_hash_ptrs, y = -1; x; x >>= 1, y++) ;
930         dip->i_depth = y;
931
932         gfs2_dinode_out(dip, dibh->b_data);
933
934         brelse(dibh);
935
936         return 0;
937 }
938
939 /**
940  * dir_split_leaf - Split a leaf block into two
941  * @dip: The GFS2 inode
942  * @index:
943  * @leaf_no:
944  *
945  * Returns: 0 on success, error code on failure
946  */
947
948 static int dir_split_leaf(struct inode *inode, const struct qstr *name)
949 {
950         struct gfs2_inode *dip = GFS2_I(inode);
951         struct buffer_head *nbh, *obh, *dibh;
952         struct gfs2_leaf *nleaf, *oleaf;
953         struct gfs2_dirent *dent = NULL, *prev = NULL, *next = NULL, *new;
954         u32 start, len, half_len, divider;
955         u64 bn, leaf_no;
956         __be64 *lp;
957         u32 index;
958         int x, moved = 0;
959         int error;
960
961         index = name->hash >> (32 - dip->i_depth);
962         error = get_leaf_nr(dip, index, &leaf_no);
963         if (error)
964                 return error;
965
966         /*  Get the old leaf block  */
967         error = get_leaf(dip, leaf_no, &obh);
968         if (error)
969                 return error;
970
971         oleaf = (struct gfs2_leaf *)obh->b_data;
972         if (dip->i_depth == be16_to_cpu(oleaf->lf_depth)) {
973                 brelse(obh);
974                 return 1; /* can't split */
975         }
976
977         gfs2_trans_add_bh(dip->i_gl, obh, 1);
978
979         nleaf = new_leaf(inode, &nbh, be16_to_cpu(oleaf->lf_depth) + 1);
980         if (!nleaf) {
981                 brelse(obh);
982                 return -ENOSPC;
983         }
984         bn = nbh->b_blocknr;
985
986         /*  Compute the start and len of leaf pointers in the hash table.  */
987         len = 1 << (dip->i_depth - be16_to_cpu(oleaf->lf_depth));
988         half_len = len >> 1;
989         if (!half_len) {
990                 printk(KERN_WARNING "i_depth %u lf_depth %u index %u\n", dip->i_depth, be16_to_cpu(oleaf->lf_depth), index);
991                 gfs2_consist_inode(dip);
992                 error = -EIO;
993                 goto fail_brelse;
994         }
995
996         start = (index & ~(len - 1));
997
998         /* Change the pointers.
999            Don't bother distinguishing stuffed from non-stuffed.
1000            This code is complicated enough already. */
1001         lp = kmalloc(half_len * sizeof(__be64), GFP_NOFS);
1002         if (!lp) {
1003                 error = -ENOMEM;
1004                 goto fail_brelse;
1005         }
1006
1007         /*  Change the pointers  */
1008         for (x = 0; x < half_len; x++)
1009                 lp[x] = cpu_to_be64(bn);
1010
1011         gfs2_dir_hash_inval(dip);
1012
1013         error = gfs2_dir_write_data(dip, (char *)lp, start * sizeof(u64),
1014                                     half_len * sizeof(u64));
1015         if (error != half_len * sizeof(u64)) {
1016                 if (error >= 0)
1017                         error = -EIO;
1018                 goto fail_lpfree;
1019         }
1020
1021         kfree(lp);
1022
1023         /*  Compute the divider  */
1024         divider = (start + half_len) << (32 - dip->i_depth);
1025
1026         /*  Copy the entries  */
1027         dent = (struct gfs2_dirent *)(obh->b_data + sizeof(struct gfs2_leaf));
1028
1029         do {
1030                 next = dent;
1031                 if (dirent_next(dip, obh, &next))
1032                         next = NULL;
1033
1034                 if (!gfs2_dirent_sentinel(dent) &&
1035                     be32_to_cpu(dent->de_hash) < divider) {
1036                         struct qstr str;
1037                         str.name = (char*)(dent+1);
1038                         str.len = be16_to_cpu(dent->de_name_len);
1039                         str.hash = be32_to_cpu(dent->de_hash);
1040                         new = gfs2_dirent_alloc(inode, nbh, &str);
1041                         if (IS_ERR(new)) {
1042                                 error = PTR_ERR(new);
1043                                 break;
1044                         }
1045
1046                         new->de_inum = dent->de_inum; /* No endian worries */
1047                         new->de_type = dent->de_type; /* No endian worries */
1048                         be16_add_cpu(&nleaf->lf_entries, 1);
1049
1050                         dirent_del(dip, obh, prev, dent);
1051
1052                         if (!oleaf->lf_entries)
1053                                 gfs2_consist_inode(dip);
1054                         be16_add_cpu(&oleaf->lf_entries, -1);
1055
1056                         if (!prev)
1057                                 prev = dent;
1058
1059                         moved = 1;
1060                 } else {
1061                         prev = dent;
1062                 }
1063                 dent = next;
1064         } while (dent);
1065
1066         oleaf->lf_depth = nleaf->lf_depth;
1067
1068         error = gfs2_meta_inode_buffer(dip, &dibh);
1069         if (!gfs2_assert_withdraw(GFS2_SB(&dip->i_inode), !error)) {
1070                 gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1071                 gfs2_add_inode_blocks(&dip->i_inode, 1);
1072                 gfs2_dinode_out(dip, dibh->b_data);
1073                 brelse(dibh);
1074         }
1075
1076         brelse(obh);
1077         brelse(nbh);
1078
1079         return error;
1080
1081 fail_lpfree:
1082         kfree(lp);
1083
1084 fail_brelse:
1085         brelse(obh);
1086         brelse(nbh);
1087         return error;
1088 }
1089
1090 /**
1091  * dir_double_exhash - Double size of ExHash table
1092  * @dip: The GFS2 dinode
1093  *
1094  * Returns: 0 on success, error code on failure
1095  */
1096
1097 static int dir_double_exhash(struct gfs2_inode *dip)
1098 {
1099         struct buffer_head *dibh;
1100         u32 hsize;
1101         u32 hsize_bytes;
1102         __be64 *hc;
1103         __be64 *hc2, *h;
1104         int x;
1105         int error = 0;
1106
1107         hsize = 1 << dip->i_depth;
1108         hsize_bytes = hsize * sizeof(__be64);
1109
1110         hc = gfs2_dir_get_hash_table(dip);
1111         if (IS_ERR(hc))
1112                 return PTR_ERR(hc);
1113
1114         h = hc2 = kmalloc(hsize_bytes * 2, GFP_NOFS);
1115         if (!hc2)
1116                 return -ENOMEM;
1117
1118         error = gfs2_meta_inode_buffer(dip, &dibh);
1119         if (error)
1120                 goto out_kfree;
1121
1122         for (x = 0; x < hsize; x++) {
1123                 *h++ = *hc;
1124                 *h++ = *hc;
1125                 hc++;
1126         }
1127
1128         error = gfs2_dir_write_data(dip, (char *)hc2, 0, hsize_bytes * 2);
1129         if (error != (hsize_bytes * 2))
1130                 goto fail;
1131
1132         gfs2_dir_hash_inval(dip);
1133         dip->i_hash_cache = hc2;
1134         dip->i_depth++;
1135         gfs2_dinode_out(dip, dibh->b_data);
1136         brelse(dibh);
1137         return 0;
1138
1139 fail:
1140         /* Replace original hash table & size */
1141         gfs2_dir_write_data(dip, (char *)hc, 0, hsize_bytes);
1142         i_size_write(&dip->i_inode, hsize_bytes);
1143         gfs2_dinode_out(dip, dibh->b_data);
1144         brelse(dibh);
1145 out_kfree:
1146         kfree(hc2);
1147         return error;
1148 }
1149
1150 /**
1151  * compare_dents - compare directory entries by hash value
1152  * @a: first dent
1153  * @b: second dent
1154  *
1155  * When comparing the hash entries of @a to @b:
1156  *   gt: returns 1
1157  *   lt: returns -1
1158  *   eq: returns 0
1159  */
1160
1161 static int compare_dents(const void *a, const void *b)
1162 {
1163         const struct gfs2_dirent *dent_a, *dent_b;
1164         u32 hash_a, hash_b;
1165         int ret = 0;
1166
1167         dent_a = *(const struct gfs2_dirent **)a;
1168         hash_a = be32_to_cpu(dent_a->de_hash);
1169
1170         dent_b = *(const struct gfs2_dirent **)b;
1171         hash_b = be32_to_cpu(dent_b->de_hash);
1172
1173         if (hash_a > hash_b)
1174                 ret = 1;
1175         else if (hash_a < hash_b)
1176                 ret = -1;
1177         else {
1178                 unsigned int len_a = be16_to_cpu(dent_a->de_name_len);
1179                 unsigned int len_b = be16_to_cpu(dent_b->de_name_len);
1180
1181                 if (len_a > len_b)
1182                         ret = 1;
1183                 else if (len_a < len_b)
1184                         ret = -1;
1185                 else
1186                         ret = memcmp(dent_a + 1, dent_b + 1, len_a);
1187         }
1188
1189         return ret;
1190 }
1191
1192 /**
1193  * do_filldir_main - read out directory entries
1194  * @dip: The GFS2 inode
1195  * @offset: The offset in the file to read from
1196  * @opaque: opaque data to pass to filldir
1197  * @filldir: The function to pass entries to
1198  * @darr: an array of struct gfs2_dirent pointers to read
1199  * @entries: the number of entries in darr
1200  * @copied: pointer to int that's non-zero if a entry has been copied out
1201  *
1202  * Jump through some hoops to make sure that if there are hash collsions,
1203  * they are read out at the beginning of a buffer.  We want to minimize
1204  * the possibility that they will fall into different readdir buffers or
1205  * that someone will want to seek to that location.
1206  *
1207  * Returns: errno, >0 on exception from filldir
1208  */
1209
1210 static int do_filldir_main(struct gfs2_inode *dip, u64 *offset,
1211                            void *opaque, filldir_t filldir,
1212                            const struct gfs2_dirent **darr, u32 entries,
1213                            int *copied)
1214 {
1215         const struct gfs2_dirent *dent, *dent_next;
1216         u64 off, off_next;
1217         unsigned int x, y;
1218         int run = 0;
1219         int error = 0;
1220
1221         sort(darr, entries, sizeof(struct gfs2_dirent *), compare_dents, NULL);
1222
1223         dent_next = darr[0];
1224         off_next = be32_to_cpu(dent_next->de_hash);
1225         off_next = gfs2_disk_hash2offset(off_next);
1226
1227         for (x = 0, y = 1; x < entries; x++, y++) {
1228                 dent = dent_next;
1229                 off = off_next;
1230
1231                 if (y < entries) {
1232                         dent_next = darr[y];
1233                         off_next = be32_to_cpu(dent_next->de_hash);
1234                         off_next = gfs2_disk_hash2offset(off_next);
1235
1236                         if (off < *offset)
1237                                 continue;
1238                         *offset = off;
1239
1240                         if (off_next == off) {
1241                                 if (*copied && !run)
1242                                         return 1;
1243                                 run = 1;
1244                         } else
1245                                 run = 0;
1246                 } else {
1247                         if (off < *offset)
1248                                 continue;
1249                         *offset = off;
1250                 }
1251
1252                 error = filldir(opaque, (const char *)(dent + 1),
1253                                 be16_to_cpu(dent->de_name_len),
1254                                 off, be64_to_cpu(dent->de_inum.no_addr),
1255                                 be16_to_cpu(dent->de_type));
1256                 if (error)
1257                         return 1;
1258
1259                 *copied = 1;
1260         }
1261
1262         /* Increment the *offset by one, so the next time we come into the
1263            do_filldir fxn, we get the next entry instead of the last one in the
1264            current leaf */
1265
1266         (*offset)++;
1267
1268         return 0;
1269 }
1270
1271 static void *gfs2_alloc_sort_buffer(unsigned size)
1272 {
1273         void *ptr = NULL;
1274
1275         if (size < KMALLOC_MAX_SIZE)
1276                 ptr = kmalloc(size, GFP_NOFS | __GFP_NOWARN);
1277         if (!ptr)
1278                 ptr = __vmalloc(size, GFP_NOFS, PAGE_KERNEL);
1279         return ptr;
1280 }
1281
1282 static void gfs2_free_sort_buffer(void *ptr)
1283 {
1284         if (is_vmalloc_addr(ptr))
1285                 vfree(ptr);
1286         else
1287                 kfree(ptr);
1288 }
1289
1290 static int gfs2_dir_read_leaf(struct inode *inode, u64 *offset, void *opaque,
1291                               filldir_t filldir, int *copied, unsigned *depth,
1292                               u64 leaf_no)
1293 {
1294         struct gfs2_inode *ip = GFS2_I(inode);
1295         struct gfs2_sbd *sdp = GFS2_SB(inode);
1296         struct buffer_head *bh;
1297         struct gfs2_leaf *lf;
1298         unsigned entries = 0, entries2 = 0;
1299         unsigned leaves = 0;
1300         const struct gfs2_dirent **darr, *dent;
1301         struct dirent_gather g;
1302         struct buffer_head **larr;
1303         int leaf = 0;
1304         int error, i;
1305         u64 lfn = leaf_no;
1306
1307         do {
1308                 error = get_leaf(ip, lfn, &bh);
1309                 if (error)
1310                         goto out;
1311                 lf = (struct gfs2_leaf *)bh->b_data;
1312                 if (leaves == 0)
1313                         *depth = be16_to_cpu(lf->lf_depth);
1314                 entries += be16_to_cpu(lf->lf_entries);
1315                 leaves++;
1316                 lfn = be64_to_cpu(lf->lf_next);
1317                 brelse(bh);
1318         } while(lfn);
1319
1320         if (!entries)
1321                 return 0;
1322
1323         error = -ENOMEM;
1324         /*
1325          * The extra 99 entries are not normally used, but are a buffer
1326          * zone in case the number of entries in the leaf is corrupt.
1327          * 99 is the maximum number of entries that can fit in a single
1328          * leaf block.
1329          */
1330         larr = gfs2_alloc_sort_buffer((leaves + entries + 99) * sizeof(void *));
1331         if (!larr)
1332                 goto out;
1333         darr = (const struct gfs2_dirent **)(larr + leaves);
1334         g.pdent = darr;
1335         g.offset = 0;
1336         lfn = leaf_no;
1337
1338         do {
1339                 error = get_leaf(ip, lfn, &bh);
1340                 if (error)
1341                         goto out_free;
1342                 lf = (struct gfs2_leaf *)bh->b_data;
1343                 lfn = be64_to_cpu(lf->lf_next);
1344                 if (lf->lf_entries) {
1345                         entries2 += be16_to_cpu(lf->lf_entries);
1346                         dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size,
1347                                                 gfs2_dirent_gather, NULL, &g);
1348                         error = PTR_ERR(dent);
1349                         if (IS_ERR(dent))
1350                                 goto out_free;
1351                         if (entries2 != g.offset) {
1352                                 fs_warn(sdp, "Number of entries corrupt in dir "
1353                                                 "leaf %llu, entries2 (%u) != "
1354                                                 "g.offset (%u)\n",
1355                                         (unsigned long long)bh->b_blocknr,
1356                                         entries2, g.offset);
1357                                         
1358                                 error = -EIO;
1359                                 goto out_free;
1360                         }
1361                         error = 0;
1362                         larr[leaf++] = bh;
1363                 } else {
1364                         brelse(bh);
1365                 }
1366         } while(lfn);
1367
1368         BUG_ON(entries2 != entries);
1369         error = do_filldir_main(ip, offset, opaque, filldir, darr,
1370                                 entries, copied);
1371 out_free:
1372         for(i = 0; i < leaf; i++)
1373                 brelse(larr[i]);
1374         gfs2_free_sort_buffer(larr);
1375 out:
1376         return error;
1377 }
1378
1379
1380 /**
1381  * dir_e_read - Reads the entries from a directory into a filldir buffer
1382  * @dip: dinode pointer
1383  * @offset: the hash of the last entry read shifted to the right once
1384  * @opaque: buffer for the filldir function to fill
1385  * @filldir: points to the filldir function to use
1386  *
1387  * Returns: errno
1388  */
1389
1390 static int dir_e_read(struct inode *inode, u64 *offset, void *opaque,
1391                       filldir_t filldir)
1392 {
1393         struct gfs2_inode *dip = GFS2_I(inode);
1394         u32 hsize, len = 0;
1395         u32 hash, index;
1396         __be64 *lp;
1397         int copied = 0;
1398         int error = 0;
1399         unsigned depth = 0;
1400
1401         hsize = 1 << dip->i_depth;
1402         hash = gfs2_dir_offset2hash(*offset);
1403         index = hash >> (32 - dip->i_depth);
1404
1405         lp = gfs2_dir_get_hash_table(dip);
1406         if (IS_ERR(lp))
1407                 return PTR_ERR(lp);
1408
1409         while (index < hsize) {
1410                 error = gfs2_dir_read_leaf(inode, offset, opaque, filldir,
1411                                            &copied, &depth,
1412                                            be64_to_cpu(lp[index]));
1413                 if (error)
1414                         break;
1415
1416                 len = 1 << (dip->i_depth - depth);
1417                 index = (index & ~(len - 1)) + len;
1418         }
1419
1420         if (error > 0)
1421                 error = 0;
1422         return error;
1423 }
1424
1425 int gfs2_dir_read(struct inode *inode, u64 *offset, void *opaque,
1426                   filldir_t filldir)
1427 {
1428         struct gfs2_inode *dip = GFS2_I(inode);
1429         struct gfs2_sbd *sdp = GFS2_SB(inode);
1430         struct dirent_gather g;
1431         const struct gfs2_dirent **darr, *dent;
1432         struct buffer_head *dibh;
1433         int copied = 0;
1434         int error;
1435
1436         if (!dip->i_entries)
1437                 return 0;
1438
1439         if (dip->i_diskflags & GFS2_DIF_EXHASH)
1440                 return dir_e_read(inode, offset, opaque, filldir);
1441
1442         if (!gfs2_is_stuffed(dip)) {
1443                 gfs2_consist_inode(dip);
1444                 return -EIO;
1445         }
1446
1447         error = gfs2_meta_inode_buffer(dip, &dibh);
1448         if (error)
1449                 return error;
1450
1451         error = -ENOMEM;
1452         /* 96 is max number of dirents which can be stuffed into an inode */
1453         darr = kmalloc(96 * sizeof(struct gfs2_dirent *), GFP_NOFS);
1454         if (darr) {
1455                 g.pdent = darr;
1456                 g.offset = 0;
1457                 dent = gfs2_dirent_scan(inode, dibh->b_data, dibh->b_size,
1458                                         gfs2_dirent_gather, NULL, &g);
1459                 if (IS_ERR(dent)) {
1460                         error = PTR_ERR(dent);
1461                         goto out;
1462                 }
1463                 if (dip->i_entries != g.offset) {
1464                         fs_warn(sdp, "Number of entries corrupt in dir %llu, "
1465                                 "ip->i_entries (%u) != g.offset (%u)\n",
1466                                 (unsigned long long)dip->i_no_addr,
1467                                 dip->i_entries,
1468                                 g.offset);
1469                         error = -EIO;
1470                         goto out;
1471                 }
1472                 error = do_filldir_main(dip, offset, opaque, filldir, darr,
1473                                         dip->i_entries, &copied);
1474 out:
1475                 kfree(darr);
1476         }
1477
1478         if (error > 0)
1479                 error = 0;
1480
1481         brelse(dibh);
1482
1483         return error;
1484 }
1485
1486 /**
1487  * gfs2_dir_search - Search a directory
1488  * @dip: The GFS2 inode
1489  * @filename:
1490  * @inode:
1491  *
1492  * This routine searches a directory for a file or another directory.
1493  * Assumes a glock is held on dip.
1494  *
1495  * Returns: errno
1496  */
1497
1498 struct inode *gfs2_dir_search(struct inode *dir, const struct qstr *name)
1499 {
1500         struct buffer_head *bh;
1501         struct gfs2_dirent *dent;
1502         struct inode *inode;
1503
1504         dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh);
1505         if (dent) {
1506                 if (IS_ERR(dent))
1507                         return ERR_CAST(dent);
1508                 inode = gfs2_inode_lookup(dir->i_sb, 
1509                                 be16_to_cpu(dent->de_type),
1510                                 be64_to_cpu(dent->de_inum.no_addr),
1511                                 be64_to_cpu(dent->de_inum.no_formal_ino), 0);
1512                 brelse(bh);
1513                 return inode;
1514         }
1515         return ERR_PTR(-ENOENT);
1516 }
1517
1518 int gfs2_dir_check(struct inode *dir, const struct qstr *name,
1519                    const struct gfs2_inode *ip)
1520 {
1521         struct buffer_head *bh;
1522         struct gfs2_dirent *dent;
1523         int ret = -ENOENT;
1524
1525         dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh);
1526         if (dent) {
1527                 if (IS_ERR(dent))
1528                         return PTR_ERR(dent);
1529                 if (ip) {
1530                         if (be64_to_cpu(dent->de_inum.no_addr) != ip->i_no_addr)
1531                                 goto out;
1532                         if (be64_to_cpu(dent->de_inum.no_formal_ino) !=
1533                             ip->i_no_formal_ino)
1534                                 goto out;
1535                         if (unlikely(IF2DT(ip->i_inode.i_mode) !=
1536                             be16_to_cpu(dent->de_type))) {
1537                                 gfs2_consist_inode(GFS2_I(dir));
1538                                 ret = -EIO;
1539                                 goto out;
1540                         }
1541                 }
1542                 ret = 0;
1543 out:
1544                 brelse(bh);
1545         }
1546         return ret;
1547 }
1548
1549 static int dir_new_leaf(struct inode *inode, const struct qstr *name)
1550 {
1551         struct buffer_head *bh, *obh;
1552         struct gfs2_inode *ip = GFS2_I(inode);
1553         struct gfs2_leaf *leaf, *oleaf;
1554         int error;
1555         u32 index;
1556         u64 bn;
1557
1558         index = name->hash >> (32 - ip->i_depth);
1559         error = get_first_leaf(ip, index, &obh);
1560         if (error)
1561                 return error;
1562         do {
1563                 oleaf = (struct gfs2_leaf *)obh->b_data;
1564                 bn = be64_to_cpu(oleaf->lf_next);
1565                 if (!bn)
1566                         break;
1567                 brelse(obh);
1568                 error = get_leaf(ip, bn, &obh);
1569                 if (error)
1570                         return error;
1571         } while(1);
1572
1573         gfs2_trans_add_bh(ip->i_gl, obh, 1);
1574
1575         leaf = new_leaf(inode, &bh, be16_to_cpu(oleaf->lf_depth));
1576         if (!leaf) {
1577                 brelse(obh);
1578                 return -ENOSPC;
1579         }
1580         oleaf->lf_next = cpu_to_be64(bh->b_blocknr);
1581         brelse(bh);
1582         brelse(obh);
1583
1584         error = gfs2_meta_inode_buffer(ip, &bh);
1585         if (error)
1586                 return error;
1587         gfs2_trans_add_bh(ip->i_gl, bh, 1);
1588         gfs2_add_inode_blocks(&ip->i_inode, 1);
1589         gfs2_dinode_out(ip, bh->b_data);
1590         brelse(bh);
1591         return 0;
1592 }
1593
1594 /**
1595  * gfs2_dir_add - Add new filename into directory
1596  * @dip: The GFS2 inode
1597  * @filename: The new name
1598  * @inode: The inode number of the entry
1599  * @type: The type of the entry
1600  *
1601  * Returns: 0 on success, error code on failure
1602  */
1603
1604 int gfs2_dir_add(struct inode *inode, const struct qstr *name,
1605                  const struct gfs2_inode *nip)
1606 {
1607         struct gfs2_inode *ip = GFS2_I(inode);
1608         struct buffer_head *bh;
1609         struct gfs2_dirent *dent;
1610         struct gfs2_leaf *leaf;
1611         int error;
1612
1613         while(1) {
1614                 dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space,
1615                                           &bh);
1616                 if (dent) {
1617                         if (IS_ERR(dent))
1618                                 return PTR_ERR(dent);
1619                         dent = gfs2_init_dirent(inode, dent, name, bh);
1620                         gfs2_inum_out(nip, dent);
1621                         dent->de_type = cpu_to_be16(IF2DT(nip->i_inode.i_mode));
1622                         if (ip->i_diskflags & GFS2_DIF_EXHASH) {
1623                                 leaf = (struct gfs2_leaf *)bh->b_data;
1624                                 be16_add_cpu(&leaf->lf_entries, 1);
1625                         }
1626                         brelse(bh);
1627                         error = gfs2_meta_inode_buffer(ip, &bh);
1628                         if (error)
1629                                 break;
1630                         gfs2_trans_add_bh(ip->i_gl, bh, 1);
1631                         ip->i_entries++;
1632                         ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME;
1633                         if (S_ISDIR(nip->i_inode.i_mode))
1634                                 inc_nlink(&ip->i_inode);
1635                         gfs2_dinode_out(ip, bh->b_data);
1636                         brelse(bh);
1637                         error = 0;
1638                         break;
1639                 }
1640                 if (!(ip->i_diskflags & GFS2_DIF_EXHASH)) {
1641                         error = dir_make_exhash(inode);
1642                         if (error)
1643                                 break;
1644                         continue;
1645                 }
1646                 error = dir_split_leaf(inode, name);
1647                 if (error == 0)
1648                         continue;
1649                 if (error < 0)
1650                         break;
1651                 if (ip->i_depth < GFS2_DIR_MAX_DEPTH) {
1652                         error = dir_double_exhash(ip);
1653                         if (error)
1654                                 break;
1655                         error = dir_split_leaf(inode, name);
1656                         if (error < 0)
1657                                 break;
1658                         if (error == 0)
1659                                 continue;
1660                 }
1661                 error = dir_new_leaf(inode, name);
1662                 if (!error)
1663                         continue;
1664                 error = -ENOSPC;
1665                 break;
1666         }
1667         return error;
1668 }
1669
1670
1671 /**
1672  * gfs2_dir_del - Delete a directory entry
1673  * @dip: The GFS2 inode
1674  * @filename: The filename
1675  *
1676  * Returns: 0 on success, error code on failure
1677  */
1678
1679 int gfs2_dir_del(struct gfs2_inode *dip, const struct dentry *dentry)
1680 {
1681         const struct qstr *name = &dentry->d_name;
1682         struct gfs2_dirent *dent, *prev = NULL;
1683         struct buffer_head *bh;
1684
1685         /* Returns _either_ the entry (if its first in block) or the
1686            previous entry otherwise */
1687         dent = gfs2_dirent_search(&dip->i_inode, name, gfs2_dirent_prev, &bh);
1688         if (!dent) {
1689                 gfs2_consist_inode(dip);
1690                 return -EIO;
1691         }
1692         if (IS_ERR(dent)) {
1693                 gfs2_consist_inode(dip);
1694                 return PTR_ERR(dent);
1695         }
1696         /* If not first in block, adjust pointers accordingly */
1697         if (gfs2_dirent_find(dent, name, NULL) == 0) {
1698                 prev = dent;
1699                 dent = (struct gfs2_dirent *)((char *)dent + be16_to_cpu(prev->de_rec_len));
1700         }
1701
1702         dirent_del(dip, bh, prev, dent);
1703         if (dip->i_diskflags & GFS2_DIF_EXHASH) {
1704                 struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data;
1705                 u16 entries = be16_to_cpu(leaf->lf_entries);
1706                 if (!entries)
1707                         gfs2_consist_inode(dip);
1708                 leaf->lf_entries = cpu_to_be16(--entries);
1709         }
1710         brelse(bh);
1711
1712         if (!dip->i_entries)
1713                 gfs2_consist_inode(dip);
1714         dip->i_entries--;
1715         dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME;
1716         if (S_ISDIR(dentry->d_inode->i_mode))
1717                 drop_nlink(&dip->i_inode);
1718         mark_inode_dirty(&dip->i_inode);
1719
1720         return 0;
1721 }
1722
1723 /**
1724  * gfs2_dir_mvino - Change inode number of directory entry
1725  * @dip: The GFS2 inode
1726  * @filename:
1727  * @new_inode:
1728  *
1729  * This routine changes the inode number of a directory entry.  It's used
1730  * by rename to change ".." when a directory is moved.
1731  * Assumes a glock is held on dvp.
1732  *
1733  * Returns: errno
1734  */
1735
1736 int gfs2_dir_mvino(struct gfs2_inode *dip, const struct qstr *filename,
1737                    const struct gfs2_inode *nip, unsigned int new_type)
1738 {
1739         struct buffer_head *bh;
1740         struct gfs2_dirent *dent;
1741         int error;
1742
1743         dent = gfs2_dirent_search(&dip->i_inode, filename, gfs2_dirent_find, &bh);
1744         if (!dent) {
1745                 gfs2_consist_inode(dip);
1746                 return -EIO;
1747         }
1748         if (IS_ERR(dent))
1749                 return PTR_ERR(dent);
1750
1751         gfs2_trans_add_bh(dip->i_gl, bh, 1);
1752         gfs2_inum_out(nip, dent);
1753         dent->de_type = cpu_to_be16(new_type);
1754
1755         if (dip->i_diskflags & GFS2_DIF_EXHASH) {
1756                 brelse(bh);
1757                 error = gfs2_meta_inode_buffer(dip, &bh);
1758                 if (error)
1759                         return error;
1760                 gfs2_trans_add_bh(dip->i_gl, bh, 1);
1761         }
1762
1763         dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME;
1764         gfs2_dinode_out(dip, bh->b_data);
1765         brelse(bh);
1766         return 0;
1767 }
1768
1769 /**
1770  * leaf_dealloc - Deallocate a directory leaf
1771  * @dip: the directory
1772  * @index: the hash table offset in the directory
1773  * @len: the number of pointers to this leaf
1774  * @leaf_no: the leaf number
1775  * @leaf_bh: buffer_head for the starting leaf
1776  * last_dealloc: 1 if this is the final dealloc for the leaf, else 0
1777  *
1778  * Returns: errno
1779  */
1780
1781 static int leaf_dealloc(struct gfs2_inode *dip, u32 index, u32 len,
1782                         u64 leaf_no, struct buffer_head *leaf_bh,
1783                         int last_dealloc)
1784 {
1785         struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode);
1786         struct gfs2_leaf *tmp_leaf;
1787         struct gfs2_rgrp_list rlist;
1788         struct buffer_head *bh, *dibh;
1789         u64 blk, nblk;
1790         unsigned int rg_blocks = 0, l_blocks = 0;
1791         char *ht;
1792         unsigned int x, size = len * sizeof(u64);
1793         int error;
1794
1795         memset(&rlist, 0, sizeof(struct gfs2_rgrp_list));
1796
1797         ht = kzalloc(size, GFP_NOFS);
1798         if (!ht)
1799                 return -ENOMEM;
1800
1801         if (!gfs2_alloc_get(dip)) {
1802                 error = -ENOMEM;
1803                 goto out;
1804         }
1805
1806         error = gfs2_quota_hold(dip, NO_QUOTA_CHANGE, NO_QUOTA_CHANGE);
1807         if (error)
1808                 goto out_put;
1809
1810         /*  Count the number of leaves  */
1811         bh = leaf_bh;
1812
1813         for (blk = leaf_no; blk; blk = nblk) {
1814                 if (blk != leaf_no) {
1815                         error = get_leaf(dip, blk, &bh);
1816                         if (error)
1817                                 goto out_rlist;
1818                 }
1819                 tmp_leaf = (struct gfs2_leaf *)bh->b_data;
1820                 nblk = be64_to_cpu(tmp_leaf->lf_next);
1821                 if (blk != leaf_no)
1822                         brelse(bh);
1823
1824                 gfs2_rlist_add(sdp, &rlist, blk);
1825                 l_blocks++;
1826         }
1827
1828         gfs2_rlist_alloc(&rlist, LM_ST_EXCLUSIVE);
1829
1830         for (x = 0; x < rlist.rl_rgrps; x++) {
1831                 struct gfs2_rgrpd *rgd;
1832                 rgd = rlist.rl_ghs[x].gh_gl->gl_object;
1833                 rg_blocks += rgd->rd_length;
1834         }
1835
1836         error = gfs2_glock_nq_m(rlist.rl_rgrps, rlist.rl_ghs);
1837         if (error)
1838                 goto out_rlist;
1839
1840         error = gfs2_trans_begin(sdp,
1841                         rg_blocks + (DIV_ROUND_UP(size, sdp->sd_jbsize) + 1) +
1842                         RES_DINODE + RES_STATFS + RES_QUOTA, l_blocks);
1843         if (error)
1844                 goto out_rg_gunlock;
1845
1846         bh = leaf_bh;
1847
1848         for (blk = leaf_no; blk; blk = nblk) {
1849                 if (blk != leaf_no) {
1850                         error = get_leaf(dip, blk, &bh);
1851                         if (error)
1852                                 goto out_end_trans;
1853                 }
1854                 tmp_leaf = (struct gfs2_leaf *)bh->b_data;
1855                 nblk = be64_to_cpu(tmp_leaf->lf_next);
1856                 if (blk != leaf_no)
1857                         brelse(bh);
1858
1859                 gfs2_free_meta(dip, blk, 1);
1860                 gfs2_add_inode_blocks(&dip->i_inode, -1);
1861         }
1862
1863         error = gfs2_dir_write_data(dip, ht, index * sizeof(u64), size);
1864         if (error != size) {
1865                 if (error >= 0)
1866                         error = -EIO;
1867                 goto out_end_trans;
1868         }
1869
1870         error = gfs2_meta_inode_buffer(dip, &dibh);
1871         if (error)
1872                 goto out_end_trans;
1873
1874         gfs2_trans_add_bh(dip->i_gl, dibh, 1);
1875         /* On the last dealloc, make this a regular file in case we crash.
1876            (We don't want to free these blocks a second time.)  */
1877         if (last_dealloc)
1878                 dip->i_inode.i_mode = S_IFREG;
1879         gfs2_dinode_out(dip, dibh->b_data);
1880         brelse(dibh);
1881
1882 out_end_trans:
1883         gfs2_trans_end(sdp);
1884 out_rg_gunlock:
1885         gfs2_glock_dq_m(rlist.rl_rgrps, rlist.rl_ghs);
1886 out_rlist:
1887         gfs2_rlist_free(&rlist);
1888         gfs2_quota_unhold(dip);
1889 out_put:
1890         gfs2_alloc_put(dip);
1891 out:
1892         kfree(ht);
1893         return error;
1894 }
1895
1896 /**
1897  * gfs2_dir_exhash_dealloc - free all the leaf blocks in a directory
1898  * @dip: the directory
1899  *
1900  * Dealloc all on-disk directory leaves to FREEMETA state
1901  * Change on-disk inode type to "regular file"
1902  *
1903  * Returns: errno
1904  */
1905
1906 int gfs2_dir_exhash_dealloc(struct gfs2_inode *dip)
1907 {
1908         struct buffer_head *bh;
1909         struct gfs2_leaf *leaf;
1910         u32 hsize, len;
1911         u32 index = 0, next_index;
1912         __be64 *lp;
1913         u64 leaf_no;
1914         int error = 0, last;
1915
1916         hsize = 1 << dip->i_depth;
1917
1918         lp = gfs2_dir_get_hash_table(dip);
1919         if (IS_ERR(lp))
1920                 return PTR_ERR(lp);
1921
1922         while (index < hsize) {
1923                 leaf_no = be64_to_cpu(lp[index]);
1924                 if (leaf_no) {
1925                         error = get_leaf(dip, leaf_no, &bh);
1926                         if (error)
1927                                 goto out;
1928                         leaf = (struct gfs2_leaf *)bh->b_data;
1929                         len = 1 << (dip->i_depth - be16_to_cpu(leaf->lf_depth));
1930
1931                         next_index = (index & ~(len - 1)) + len;
1932                         last = ((next_index >= hsize) ? 1 : 0);
1933                         error = leaf_dealloc(dip, index, len, leaf_no, bh,
1934                                              last);
1935                         brelse(bh);
1936                         if (error)
1937                                 goto out;
1938                         index = next_index;
1939                 } else
1940                         index++;
1941         }
1942
1943         if (index != hsize) {
1944                 gfs2_consist_inode(dip);
1945                 error = -EIO;
1946         }
1947
1948 out:
1949
1950         return error;
1951 }
1952
1953 /**
1954  * gfs2_diradd_alloc_required - find if adding entry will require an allocation
1955  * @ip: the file being written to
1956  * @filname: the filename that's going to be added
1957  *
1958  * Returns: 1 if alloc required, 0 if not, -ve on error
1959  */
1960
1961 int gfs2_diradd_alloc_required(struct inode *inode, const struct qstr *name)
1962 {
1963         struct gfs2_dirent *dent;
1964         struct buffer_head *bh;
1965
1966         dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space, &bh);
1967         if (!dent) {
1968                 return 1;
1969         }
1970         if (IS_ERR(dent))
1971                 return PTR_ERR(dent);
1972         brelse(bh);
1973         return 0;
1974 }
1975