Merge branch 'for-2.6.31' of git://git.kernel.dk/linux-2.6-block
[linux-2.6.git] / fs / gfs2 / rgrp.c
1 /*
2  * Copyright (C) Sistina Software, Inc.  1997-2003 All rights reserved.
3  * Copyright (C) 2004-2008 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 #include <linux/slab.h>
11 #include <linux/spinlock.h>
12 #include <linux/completion.h>
13 #include <linux/buffer_head.h>
14 #include <linux/fs.h>
15 #include <linux/gfs2_ondisk.h>
16 #include <linux/prefetch.h>
17 #include <linux/blkdev.h>
18
19 #include "gfs2.h"
20 #include "incore.h"
21 #include "glock.h"
22 #include "glops.h"
23 #include "lops.h"
24 #include "meta_io.h"
25 #include "quota.h"
26 #include "rgrp.h"
27 #include "super.h"
28 #include "trans.h"
29 #include "util.h"
30 #include "log.h"
31 #include "inode.h"
32
33 #define BFITNOENT ((u32)~0)
34 #define NO_BLOCK ((u64)~0)
35
36 #if BITS_PER_LONG == 32
37 #define LBITMASK   (0x55555555UL)
38 #define LBITSKIP55 (0x55555555UL)
39 #define LBITSKIP00 (0x00000000UL)
40 #else
41 #define LBITMASK   (0x5555555555555555UL)
42 #define LBITSKIP55 (0x5555555555555555UL)
43 #define LBITSKIP00 (0x0000000000000000UL)
44 #endif
45
46 /*
47  * These routines are used by the resource group routines (rgrp.c)
48  * to keep track of block allocation.  Each block is represented by two
49  * bits.  So, each byte represents GFS2_NBBY (i.e. 4) blocks.
50  *
51  * 0 = Free
52  * 1 = Used (not metadata)
53  * 2 = Unlinked (still in use) inode
54  * 3 = Used (metadata)
55  */
56
57 static const char valid_change[16] = {
58                 /* current */
59         /* n */ 0, 1, 1, 1,
60         /* e */ 1, 0, 0, 0,
61         /* w */ 0, 0, 0, 1,
62                 1, 0, 0, 0
63 };
64
65 static u32 rgblk_search(struct gfs2_rgrpd *rgd, u32 goal,
66                         unsigned char old_state, unsigned char new_state,
67                         unsigned int *n);
68
69 /**
70  * gfs2_setbit - Set a bit in the bitmaps
71  * @buffer: the buffer that holds the bitmaps
72  * @buflen: the length (in bytes) of the buffer
73  * @block: the block to set
74  * @new_state: the new state of the block
75  *
76  */
77
78 static inline void gfs2_setbit(struct gfs2_rgrpd *rgd, unsigned char *buf1,
79                                unsigned char *buf2, unsigned int offset,
80                                unsigned int buflen, u32 block,
81                                unsigned char new_state)
82 {
83         unsigned char *byte1, *byte2, *end, cur_state;
84         const unsigned int bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
85
86         byte1 = buf1 + offset + (block / GFS2_NBBY);
87         end = buf1 + offset + buflen;
88
89         BUG_ON(byte1 >= end);
90
91         cur_state = (*byte1 >> bit) & GFS2_BIT_MASK;
92
93         if (unlikely(!valid_change[new_state * 4 + cur_state])) {
94                 gfs2_consist_rgrpd(rgd);
95                 return;
96         }
97         *byte1 ^= (cur_state ^ new_state) << bit;
98
99         if (buf2) {
100                 byte2 = buf2 + offset + (block / GFS2_NBBY);
101                 cur_state = (*byte2 >> bit) & GFS2_BIT_MASK;
102                 *byte2 ^= (cur_state ^ new_state) << bit;
103         }
104 }
105
106 /**
107  * gfs2_testbit - test a bit in the bitmaps
108  * @buffer: the buffer that holds the bitmaps
109  * @buflen: the length (in bytes) of the buffer
110  * @block: the block to read
111  *
112  */
113
114 static inline unsigned char gfs2_testbit(struct gfs2_rgrpd *rgd,
115                                          const unsigned char *buffer,
116                                          unsigned int buflen, u32 block)
117 {
118         const unsigned char *byte, *end;
119         unsigned char cur_state;
120         unsigned int bit;
121
122         byte = buffer + (block / GFS2_NBBY);
123         bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
124         end = buffer + buflen;
125
126         gfs2_assert(rgd->rd_sbd, byte < end);
127
128         cur_state = (*byte >> bit) & GFS2_BIT_MASK;
129
130         return cur_state;
131 }
132
133 /**
134  * gfs2_bit_search
135  * @ptr: Pointer to bitmap data
136  * @mask: Mask to use (normally 0x55555.... but adjusted for search start)
137  * @state: The state we are searching for
138  *
139  * We xor the bitmap data with a patter which is the bitwise opposite
140  * of what we are looking for, this gives rise to a pattern of ones
141  * wherever there is a match. Since we have two bits per entry, we
142  * take this pattern, shift it down by one place and then and it with
143  * the original. All the even bit positions (0,2,4, etc) then represent
144  * successful matches, so we mask with 0x55555..... to remove the unwanted
145  * odd bit positions.
146  *
147  * This allows searching of a whole u64 at once (32 blocks) with a
148  * single test (on 64 bit arches).
149  */
150
151 static inline u64 gfs2_bit_search(const __le64 *ptr, u64 mask, u8 state)
152 {
153         u64 tmp;
154         static const u64 search[] = {
155                 [0] = 0xffffffffffffffffULL,
156                 [1] = 0xaaaaaaaaaaaaaaaaULL,
157                 [2] = 0x5555555555555555ULL,
158                 [3] = 0x0000000000000000ULL,
159         };
160         tmp = le64_to_cpu(*ptr) ^ search[state];
161         tmp &= (tmp >> 1);
162         tmp &= mask;
163         return tmp;
164 }
165
166 /**
167  * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
168  *       a block in a given allocation state.
169  * @buffer: the buffer that holds the bitmaps
170  * @len: the length (in bytes) of the buffer
171  * @goal: start search at this block's bit-pair (within @buffer)
172  * @state: GFS2_BLKST_XXX the state of the block we're looking for.
173  *
174  * Scope of @goal and returned block number is only within this bitmap buffer,
175  * not entire rgrp or filesystem.  @buffer will be offset from the actual
176  * beginning of a bitmap block buffer, skipping any header structures, but
177  * headers are always a multiple of 64 bits long so that the buffer is
178  * always aligned to a 64 bit boundary.
179  *
180  * The size of the buffer is in bytes, but is it assumed that it is
181  * always ok to to read a complete multiple of 64 bits at the end
182  * of the block in case the end is no aligned to a natural boundary.
183  *
184  * Return: the block number (bitmap buffer scope) that was found
185  */
186
187 static u32 gfs2_bitfit(const u8 *buf, const unsigned int len,
188                        u32 goal, u8 state)
189 {
190         u32 spoint = (goal << 1) & ((8*sizeof(u64)) - 1);
191         const __le64 *ptr = ((__le64 *)buf) + (goal >> 5);
192         const __le64 *end = (__le64 *)(buf + ALIGN(len, sizeof(u64)));
193         u64 tmp;
194         u64 mask = 0x5555555555555555ULL;
195         u32 bit;
196
197         BUG_ON(state > 3);
198
199         /* Mask off bits we don't care about at the start of the search */
200         mask <<= spoint;
201         tmp = gfs2_bit_search(ptr, mask, state);
202         ptr++;
203         while(tmp == 0 && ptr < end) {
204                 tmp = gfs2_bit_search(ptr, 0x5555555555555555ULL, state);
205                 ptr++;
206         }
207         /* Mask off any bits which are more than len bytes from the start */
208         if (ptr == end && (len & (sizeof(u64) - 1)))
209                 tmp &= (((u64)~0) >> (64 - 8*(len & (sizeof(u64) - 1))));
210         /* Didn't find anything, so return */
211         if (tmp == 0)
212                 return BFITNOENT;
213         ptr--;
214         bit = __ffs64(tmp);
215         bit /= 2;       /* two bits per entry in the bitmap */
216         return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
217 }
218
219 /**
220  * gfs2_bitcount - count the number of bits in a certain state
221  * @buffer: the buffer that holds the bitmaps
222  * @buflen: the length (in bytes) of the buffer
223  * @state: the state of the block we're looking for
224  *
225  * Returns: The number of bits
226  */
227
228 static u32 gfs2_bitcount(struct gfs2_rgrpd *rgd, const u8 *buffer,
229                          unsigned int buflen, u8 state)
230 {
231         const u8 *byte = buffer;
232         const u8 *end = buffer + buflen;
233         const u8 state1 = state << 2;
234         const u8 state2 = state << 4;
235         const u8 state3 = state << 6;
236         u32 count = 0;
237
238         for (; byte < end; byte++) {
239                 if (((*byte) & 0x03) == state)
240                         count++;
241                 if (((*byte) & 0x0C) == state1)
242                         count++;
243                 if (((*byte) & 0x30) == state2)
244                         count++;
245                 if (((*byte) & 0xC0) == state3)
246                         count++;
247         }
248
249         return count;
250 }
251
252 /**
253  * gfs2_rgrp_verify - Verify that a resource group is consistent
254  * @sdp: the filesystem
255  * @rgd: the rgrp
256  *
257  */
258
259 void gfs2_rgrp_verify(struct gfs2_rgrpd *rgd)
260 {
261         struct gfs2_sbd *sdp = rgd->rd_sbd;
262         struct gfs2_bitmap *bi = NULL;
263         u32 length = rgd->rd_length;
264         u32 count[4], tmp;
265         int buf, x;
266
267         memset(count, 0, 4 * sizeof(u32));
268
269         /* Count # blocks in each of 4 possible allocation states */
270         for (buf = 0; buf < length; buf++) {
271                 bi = rgd->rd_bits + buf;
272                 for (x = 0; x < 4; x++)
273                         count[x] += gfs2_bitcount(rgd,
274                                                   bi->bi_bh->b_data +
275                                                   bi->bi_offset,
276                                                   bi->bi_len, x);
277         }
278
279         if (count[0] != rgd->rd_free) {
280                 if (gfs2_consist_rgrpd(rgd))
281                         fs_err(sdp, "free data mismatch:  %u != %u\n",
282                                count[0], rgd->rd_free);
283                 return;
284         }
285
286         tmp = rgd->rd_data - rgd->rd_free - rgd->rd_dinodes;
287         if (count[1] + count[2] != tmp) {
288                 if (gfs2_consist_rgrpd(rgd))
289                         fs_err(sdp, "used data mismatch:  %u != %u\n",
290                                count[1], tmp);
291                 return;
292         }
293
294         if (count[3] != rgd->rd_dinodes) {
295                 if (gfs2_consist_rgrpd(rgd))
296                         fs_err(sdp, "used metadata mismatch:  %u != %u\n",
297                                count[3], rgd->rd_dinodes);
298                 return;
299         }
300
301         if (count[2] > count[3]) {
302                 if (gfs2_consist_rgrpd(rgd))
303                         fs_err(sdp, "unlinked inodes > inodes:  %u\n",
304                                count[2]);
305                 return;
306         }
307
308 }
309
310 static inline int rgrp_contains_block(struct gfs2_rgrpd *rgd, u64 block)
311 {
312         u64 first = rgd->rd_data0;
313         u64 last = first + rgd->rd_data;
314         return first <= block && block < last;
315 }
316
317 /**
318  * gfs2_blk2rgrpd - Find resource group for a given data/meta block number
319  * @sdp: The GFS2 superblock
320  * @n: The data block number
321  *
322  * Returns: The resource group, or NULL if not found
323  */
324
325 struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk)
326 {
327         struct gfs2_rgrpd *rgd;
328
329         spin_lock(&sdp->sd_rindex_spin);
330
331         list_for_each_entry(rgd, &sdp->sd_rindex_mru_list, rd_list_mru) {
332                 if (rgrp_contains_block(rgd, blk)) {
333                         list_move(&rgd->rd_list_mru, &sdp->sd_rindex_mru_list);
334                         spin_unlock(&sdp->sd_rindex_spin);
335                         return rgd;
336                 }
337         }
338
339         spin_unlock(&sdp->sd_rindex_spin);
340
341         return NULL;
342 }
343
344 /**
345  * gfs2_rgrpd_get_first - get the first Resource Group in the filesystem
346  * @sdp: The GFS2 superblock
347  *
348  * Returns: The first rgrp in the filesystem
349  */
350
351 struct gfs2_rgrpd *gfs2_rgrpd_get_first(struct gfs2_sbd *sdp)
352 {
353         gfs2_assert(sdp, !list_empty(&sdp->sd_rindex_list));
354         return list_entry(sdp->sd_rindex_list.next, struct gfs2_rgrpd, rd_list);
355 }
356
357 /**
358  * gfs2_rgrpd_get_next - get the next RG
359  * @rgd: A RG
360  *
361  * Returns: The next rgrp
362  */
363
364 struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
365 {
366         if (rgd->rd_list.next == &rgd->rd_sbd->sd_rindex_list)
367                 return NULL;
368         return list_entry(rgd->rd_list.next, struct gfs2_rgrpd, rd_list);
369 }
370
371 static void clear_rgrpdi(struct gfs2_sbd *sdp)
372 {
373         struct list_head *head;
374         struct gfs2_rgrpd *rgd;
375         struct gfs2_glock *gl;
376
377         spin_lock(&sdp->sd_rindex_spin);
378         sdp->sd_rindex_forward = NULL;
379         spin_unlock(&sdp->sd_rindex_spin);
380
381         head = &sdp->sd_rindex_list;
382         while (!list_empty(head)) {
383                 rgd = list_entry(head->next, struct gfs2_rgrpd, rd_list);
384                 gl = rgd->rd_gl;
385
386                 list_del(&rgd->rd_list);
387                 list_del(&rgd->rd_list_mru);
388
389                 if (gl) {
390                         gl->gl_object = NULL;
391                         gfs2_glock_put(gl);
392                 }
393
394                 kfree(rgd->rd_bits);
395                 kmem_cache_free(gfs2_rgrpd_cachep, rgd);
396         }
397 }
398
399 void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
400 {
401         mutex_lock(&sdp->sd_rindex_mutex);
402         clear_rgrpdi(sdp);
403         mutex_unlock(&sdp->sd_rindex_mutex);
404 }
405
406 static void gfs2_rindex_print(const struct gfs2_rgrpd *rgd)
407 {
408         printk(KERN_INFO "  ri_addr = %llu\n", (unsigned long long)rgd->rd_addr);
409         printk(KERN_INFO "  ri_length = %u\n", rgd->rd_length);
410         printk(KERN_INFO "  ri_data0 = %llu\n", (unsigned long long)rgd->rd_data0);
411         printk(KERN_INFO "  ri_data = %u\n", rgd->rd_data);
412         printk(KERN_INFO "  ri_bitbytes = %u\n", rgd->rd_bitbytes);
413 }
414
415 /**
416  * gfs2_compute_bitstructs - Compute the bitmap sizes
417  * @rgd: The resource group descriptor
418  *
419  * Calculates bitmap descriptors, one for each block that contains bitmap data
420  *
421  * Returns: errno
422  */
423
424 static int compute_bitstructs(struct gfs2_rgrpd *rgd)
425 {
426         struct gfs2_sbd *sdp = rgd->rd_sbd;
427         struct gfs2_bitmap *bi;
428         u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
429         u32 bytes_left, bytes;
430         int x;
431
432         if (!length)
433                 return -EINVAL;
434
435         rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
436         if (!rgd->rd_bits)
437                 return -ENOMEM;
438
439         bytes_left = rgd->rd_bitbytes;
440
441         for (x = 0; x < length; x++) {
442                 bi = rgd->rd_bits + x;
443
444                 bi->bi_flags = 0;
445                 /* small rgrp; bitmap stored completely in header block */
446                 if (length == 1) {
447                         bytes = bytes_left;
448                         bi->bi_offset = sizeof(struct gfs2_rgrp);
449                         bi->bi_start = 0;
450                         bi->bi_len = bytes;
451                 /* header block */
452                 } else if (x == 0) {
453                         bytes = sdp->sd_sb.sb_bsize - sizeof(struct gfs2_rgrp);
454                         bi->bi_offset = sizeof(struct gfs2_rgrp);
455                         bi->bi_start = 0;
456                         bi->bi_len = bytes;
457                 /* last block */
458                 } else if (x + 1 == length) {
459                         bytes = bytes_left;
460                         bi->bi_offset = sizeof(struct gfs2_meta_header);
461                         bi->bi_start = rgd->rd_bitbytes - bytes_left;
462                         bi->bi_len = bytes;
463                 /* other blocks */
464                 } else {
465                         bytes = sdp->sd_sb.sb_bsize -
466                                 sizeof(struct gfs2_meta_header);
467                         bi->bi_offset = sizeof(struct gfs2_meta_header);
468                         bi->bi_start = rgd->rd_bitbytes - bytes_left;
469                         bi->bi_len = bytes;
470                 }
471
472                 bytes_left -= bytes;
473         }
474
475         if (bytes_left) {
476                 gfs2_consist_rgrpd(rgd);
477                 return -EIO;
478         }
479         bi = rgd->rd_bits + (length - 1);
480         if ((bi->bi_start + bi->bi_len) * GFS2_NBBY != rgd->rd_data) {
481                 if (gfs2_consist_rgrpd(rgd)) {
482                         gfs2_rindex_print(rgd);
483                         fs_err(sdp, "start=%u len=%u offset=%u\n",
484                                bi->bi_start, bi->bi_len, bi->bi_offset);
485                 }
486                 return -EIO;
487         }
488
489         return 0;
490 }
491
492 /**
493  * gfs2_ri_total - Total up the file system space, according to the rindex.
494  *
495  */
496 u64 gfs2_ri_total(struct gfs2_sbd *sdp)
497 {
498         u64 total_data = 0;     
499         struct inode *inode = sdp->sd_rindex;
500         struct gfs2_inode *ip = GFS2_I(inode);
501         char buf[sizeof(struct gfs2_rindex)];
502         struct file_ra_state ra_state;
503         int error, rgrps;
504
505         mutex_lock(&sdp->sd_rindex_mutex);
506         file_ra_state_init(&ra_state, inode->i_mapping);
507         for (rgrps = 0;; rgrps++) {
508                 loff_t pos = rgrps * sizeof(struct gfs2_rindex);
509
510                 if (pos + sizeof(struct gfs2_rindex) >= ip->i_disksize)
511                         break;
512                 error = gfs2_internal_read(ip, &ra_state, buf, &pos,
513                                            sizeof(struct gfs2_rindex));
514                 if (error != sizeof(struct gfs2_rindex))
515                         break;
516                 total_data += be32_to_cpu(((struct gfs2_rindex *)buf)->ri_data);
517         }
518         mutex_unlock(&sdp->sd_rindex_mutex);
519         return total_data;
520 }
521
522 static void gfs2_rindex_in(struct gfs2_rgrpd *rgd, const void *buf)
523 {
524         const struct gfs2_rindex *str = buf;
525
526         rgd->rd_addr = be64_to_cpu(str->ri_addr);
527         rgd->rd_length = be32_to_cpu(str->ri_length);
528         rgd->rd_data0 = be64_to_cpu(str->ri_data0);
529         rgd->rd_data = be32_to_cpu(str->ri_data);
530         rgd->rd_bitbytes = be32_to_cpu(str->ri_bitbytes);
531 }
532
533 /**
534  * read_rindex_entry - Pull in a new resource index entry from the disk
535  * @gl: The glock covering the rindex inode
536  *
537  * Returns: 0 on success, error code otherwise
538  */
539
540 static int read_rindex_entry(struct gfs2_inode *ip,
541                              struct file_ra_state *ra_state)
542 {
543         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
544         loff_t pos = sdp->sd_rgrps * sizeof(struct gfs2_rindex);
545         char buf[sizeof(struct gfs2_rindex)];
546         int error;
547         struct gfs2_rgrpd *rgd;
548
549         error = gfs2_internal_read(ip, ra_state, buf, &pos,
550                                    sizeof(struct gfs2_rindex));
551         if (!error)
552                 return 0;
553         if (error != sizeof(struct gfs2_rindex)) {
554                 if (error > 0)
555                         error = -EIO;
556                 return error;
557         }
558
559         rgd = kmem_cache_zalloc(gfs2_rgrpd_cachep, GFP_NOFS);
560         error = -ENOMEM;
561         if (!rgd)
562                 return error;
563
564         mutex_init(&rgd->rd_mutex);
565         lops_init_le(&rgd->rd_le, &gfs2_rg_lops);
566         rgd->rd_sbd = sdp;
567
568         list_add_tail(&rgd->rd_list, &sdp->sd_rindex_list);
569         list_add_tail(&rgd->rd_list_mru, &sdp->sd_rindex_mru_list);
570
571         gfs2_rindex_in(rgd, buf);
572         error = compute_bitstructs(rgd);
573         if (error)
574                 return error;
575
576         error = gfs2_glock_get(sdp, rgd->rd_addr,
577                                &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
578         if (error)
579                 return error;
580
581         rgd->rd_gl->gl_object = rgd;
582         rgd->rd_flags &= ~GFS2_RDF_UPTODATE;
583         return error;
584 }
585
586 /**
587  * gfs2_ri_update - Pull in a new resource index from the disk
588  * @ip: pointer to the rindex inode
589  *
590  * Returns: 0 on successful update, error code otherwise
591  */
592
593 static int gfs2_ri_update(struct gfs2_inode *ip)
594 {
595         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
596         struct inode *inode = &ip->i_inode;
597         struct file_ra_state ra_state;
598         u64 rgrp_count = ip->i_disksize;
599         int error;
600
601         if (do_div(rgrp_count, sizeof(struct gfs2_rindex))) {
602                 gfs2_consist_inode(ip);
603                 return -EIO;
604         }
605
606         clear_rgrpdi(sdp);
607
608         file_ra_state_init(&ra_state, inode->i_mapping);
609         for (sdp->sd_rgrps = 0; sdp->sd_rgrps < rgrp_count; sdp->sd_rgrps++) {
610                 error = read_rindex_entry(ip, &ra_state);
611                 if (error) {
612                         clear_rgrpdi(sdp);
613                         return error;
614                 }
615         }
616
617         sdp->sd_rindex_uptodate = 1;
618         return 0;
619 }
620
621 /**
622  * gfs2_ri_update_special - Pull in a new resource index from the disk
623  *
624  * This is a special version that's safe to call from gfs2_inplace_reserve_i.
625  * In this case we know that we don't have any resource groups in memory yet.
626  *
627  * @ip: pointer to the rindex inode
628  *
629  * Returns: 0 on successful update, error code otherwise
630  */
631 static int gfs2_ri_update_special(struct gfs2_inode *ip)
632 {
633         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
634         struct inode *inode = &ip->i_inode;
635         struct file_ra_state ra_state;
636         int error;
637
638         file_ra_state_init(&ra_state, inode->i_mapping);
639         for (sdp->sd_rgrps = 0;; sdp->sd_rgrps++) {
640                 /* Ignore partials */
641                 if ((sdp->sd_rgrps + 1) * sizeof(struct gfs2_rindex) >
642                     ip->i_disksize)
643                         break;
644                 error = read_rindex_entry(ip, &ra_state);
645                 if (error) {
646                         clear_rgrpdi(sdp);
647                         return error;
648                 }
649         }
650
651         sdp->sd_rindex_uptodate = 1;
652         return 0;
653 }
654
655 /**
656  * gfs2_rindex_hold - Grab a lock on the rindex
657  * @sdp: The GFS2 superblock
658  * @ri_gh: the glock holder
659  *
660  * We grab a lock on the rindex inode to make sure that it doesn't
661  * change whilst we are performing an operation. We keep this lock
662  * for quite long periods of time compared to other locks. This
663  * doesn't matter, since it is shared and it is very, very rarely
664  * accessed in the exclusive mode (i.e. only when expanding the filesystem).
665  *
666  * This makes sure that we're using the latest copy of the resource index
667  * special file, which might have been updated if someone expanded the
668  * filesystem (via gfs2_grow utility), which adds new resource groups.
669  *
670  * Returns: 0 on success, error code otherwise
671  */
672
673 int gfs2_rindex_hold(struct gfs2_sbd *sdp, struct gfs2_holder *ri_gh)
674 {
675         struct gfs2_inode *ip = GFS2_I(sdp->sd_rindex);
676         struct gfs2_glock *gl = ip->i_gl;
677         int error;
678
679         error = gfs2_glock_nq_init(gl, LM_ST_SHARED, 0, ri_gh);
680         if (error)
681                 return error;
682
683         /* Read new copy from disk if we don't have the latest */
684         if (!sdp->sd_rindex_uptodate) {
685                 mutex_lock(&sdp->sd_rindex_mutex);
686                 if (!sdp->sd_rindex_uptodate) {
687                         error = gfs2_ri_update(ip);
688                         if (error)
689                                 gfs2_glock_dq_uninit(ri_gh);
690                 }
691                 mutex_unlock(&sdp->sd_rindex_mutex);
692         }
693
694         return error;
695 }
696
697 static void gfs2_rgrp_in(struct gfs2_rgrpd *rgd, const void *buf)
698 {
699         const struct gfs2_rgrp *str = buf;
700         u32 rg_flags;
701
702         rg_flags = be32_to_cpu(str->rg_flags);
703         rg_flags &= ~GFS2_RDF_MASK;
704         rgd->rd_flags &= GFS2_RDF_MASK;
705         rgd->rd_flags |= rg_flags;
706         rgd->rd_free = be32_to_cpu(str->rg_free);
707         rgd->rd_dinodes = be32_to_cpu(str->rg_dinodes);
708         rgd->rd_igeneration = be64_to_cpu(str->rg_igeneration);
709 }
710
711 static void gfs2_rgrp_out(struct gfs2_rgrpd *rgd, void *buf)
712 {
713         struct gfs2_rgrp *str = buf;
714
715         str->rg_flags = cpu_to_be32(rgd->rd_flags & ~GFS2_RDF_MASK);
716         str->rg_free = cpu_to_be32(rgd->rd_free);
717         str->rg_dinodes = cpu_to_be32(rgd->rd_dinodes);
718         str->__pad = cpu_to_be32(0);
719         str->rg_igeneration = cpu_to_be64(rgd->rd_igeneration);
720         memset(&str->rg_reserved, 0, sizeof(str->rg_reserved));
721 }
722
723 /**
724  * gfs2_rgrp_bh_get - Read in a RG's header and bitmaps
725  * @rgd: the struct gfs2_rgrpd describing the RG to read in
726  *
727  * Read in all of a Resource Group's header and bitmap blocks.
728  * Caller must eventually call gfs2_rgrp_relse() to free the bitmaps.
729  *
730  * Returns: errno
731  */
732
733 int gfs2_rgrp_bh_get(struct gfs2_rgrpd *rgd)
734 {
735         struct gfs2_sbd *sdp = rgd->rd_sbd;
736         struct gfs2_glock *gl = rgd->rd_gl;
737         unsigned int length = rgd->rd_length;
738         struct gfs2_bitmap *bi;
739         unsigned int x, y;
740         int error;
741
742         mutex_lock(&rgd->rd_mutex);
743
744         spin_lock(&sdp->sd_rindex_spin);
745         if (rgd->rd_bh_count) {
746                 rgd->rd_bh_count++;
747                 spin_unlock(&sdp->sd_rindex_spin);
748                 mutex_unlock(&rgd->rd_mutex);
749                 return 0;
750         }
751         spin_unlock(&sdp->sd_rindex_spin);
752
753         for (x = 0; x < length; x++) {
754                 bi = rgd->rd_bits + x;
755                 error = gfs2_meta_read(gl, rgd->rd_addr + x, 0, &bi->bi_bh);
756                 if (error)
757                         goto fail;
758         }
759
760         for (y = length; y--;) {
761                 bi = rgd->rd_bits + y;
762                 error = gfs2_meta_wait(sdp, bi->bi_bh);
763                 if (error)
764                         goto fail;
765                 if (gfs2_metatype_check(sdp, bi->bi_bh, y ? GFS2_METATYPE_RB :
766                                               GFS2_METATYPE_RG)) {
767                         error = -EIO;
768                         goto fail;
769                 }
770         }
771
772         if (!(rgd->rd_flags & GFS2_RDF_UPTODATE)) {
773                 for (x = 0; x < length; x++)
774                         clear_bit(GBF_FULL, &rgd->rd_bits[x].bi_flags);
775                 gfs2_rgrp_in(rgd, (rgd->rd_bits[0].bi_bh)->b_data);
776                 rgd->rd_flags |= (GFS2_RDF_UPTODATE | GFS2_RDF_CHECK);
777         }
778
779         spin_lock(&sdp->sd_rindex_spin);
780         rgd->rd_free_clone = rgd->rd_free;
781         rgd->rd_bh_count++;
782         spin_unlock(&sdp->sd_rindex_spin);
783
784         mutex_unlock(&rgd->rd_mutex);
785
786         return 0;
787
788 fail:
789         while (x--) {
790                 bi = rgd->rd_bits + x;
791                 brelse(bi->bi_bh);
792                 bi->bi_bh = NULL;
793                 gfs2_assert_warn(sdp, !bi->bi_clone);
794         }
795         mutex_unlock(&rgd->rd_mutex);
796
797         return error;
798 }
799
800 void gfs2_rgrp_bh_hold(struct gfs2_rgrpd *rgd)
801 {
802         struct gfs2_sbd *sdp = rgd->rd_sbd;
803
804         spin_lock(&sdp->sd_rindex_spin);
805         gfs2_assert_warn(rgd->rd_sbd, rgd->rd_bh_count);
806         rgd->rd_bh_count++;
807         spin_unlock(&sdp->sd_rindex_spin);
808 }
809
810 /**
811  * gfs2_rgrp_bh_put - Release RG bitmaps read in with gfs2_rgrp_bh_get()
812  * @rgd: the struct gfs2_rgrpd describing the RG to read in
813  *
814  */
815
816 void gfs2_rgrp_bh_put(struct gfs2_rgrpd *rgd)
817 {
818         struct gfs2_sbd *sdp = rgd->rd_sbd;
819         int x, length = rgd->rd_length;
820
821         spin_lock(&sdp->sd_rindex_spin);
822         gfs2_assert_warn(rgd->rd_sbd, rgd->rd_bh_count);
823         if (--rgd->rd_bh_count) {
824                 spin_unlock(&sdp->sd_rindex_spin);
825                 return;
826         }
827
828         for (x = 0; x < length; x++) {
829                 struct gfs2_bitmap *bi = rgd->rd_bits + x;
830                 kfree(bi->bi_clone);
831                 bi->bi_clone = NULL;
832                 brelse(bi->bi_bh);
833                 bi->bi_bh = NULL;
834         }
835
836         spin_unlock(&sdp->sd_rindex_spin);
837 }
838
839 static void gfs2_rgrp_send_discards(struct gfs2_sbd *sdp, u64 offset,
840                                     const struct gfs2_bitmap *bi)
841 {
842         struct super_block *sb = sdp->sd_vfs;
843         struct block_device *bdev = sb->s_bdev;
844         const unsigned int sects_per_blk = sdp->sd_sb.sb_bsize /
845                                            bdev_logical_block_size(sb->s_bdev);
846         u64 blk;
847         sector_t start = 0;
848         sector_t nr_sects = 0;
849         int rv;
850         unsigned int x;
851
852         for (x = 0; x < bi->bi_len; x++) {
853                 const u8 *orig = bi->bi_bh->b_data + bi->bi_offset + x;
854                 const u8 *clone = bi->bi_clone + bi->bi_offset + x;
855                 u8 diff = ~(*orig | (*orig >> 1)) & (*clone | (*clone >> 1));
856                 diff &= 0x55;
857                 if (diff == 0)
858                         continue;
859                 blk = offset + ((bi->bi_start + x) * GFS2_NBBY);
860                 blk *= sects_per_blk; /* convert to sectors */
861                 while(diff) {
862                         if (diff & 1) {
863                                 if (nr_sects == 0)
864                                         goto start_new_extent;
865                                 if ((start + nr_sects) != blk) {
866                                         rv = blkdev_issue_discard(bdev, start,
867                                                             nr_sects, GFP_NOFS);
868                                         if (rv)
869                                                 goto fail;
870                                         nr_sects = 0;
871 start_new_extent:
872                                         start = blk;
873                                 }
874                                 nr_sects += sects_per_blk;
875                         }
876                         diff >>= 2;
877                         blk += sects_per_blk;
878                 }
879         }
880         if (nr_sects) {
881                 rv = blkdev_issue_discard(bdev, start, nr_sects, GFP_NOFS);
882                 if (rv)
883                         goto fail;
884         }
885         return;
886 fail:
887         fs_warn(sdp, "error %d on discard request, turning discards off for this filesystem", rv);
888         sdp->sd_args.ar_discard = 0;
889 }
890
891 void gfs2_rgrp_repolish_clones(struct gfs2_rgrpd *rgd)
892 {
893         struct gfs2_sbd *sdp = rgd->rd_sbd;
894         unsigned int length = rgd->rd_length;
895         unsigned int x;
896
897         for (x = 0; x < length; x++) {
898                 struct gfs2_bitmap *bi = rgd->rd_bits + x;
899                 if (!bi->bi_clone)
900                         continue;
901                 if (sdp->sd_args.ar_discard)
902                         gfs2_rgrp_send_discards(sdp, rgd->rd_data0, bi);
903                 clear_bit(GBF_FULL, &bi->bi_flags);
904                 memcpy(bi->bi_clone + bi->bi_offset,
905                        bi->bi_bh->b_data + bi->bi_offset, bi->bi_len);
906         }
907
908         spin_lock(&sdp->sd_rindex_spin);
909         rgd->rd_free_clone = rgd->rd_free;
910         spin_unlock(&sdp->sd_rindex_spin);
911 }
912
913 /**
914  * gfs2_alloc_get - get the struct gfs2_alloc structure for an inode
915  * @ip: the incore GFS2 inode structure
916  *
917  * Returns: the struct gfs2_alloc
918  */
919
920 struct gfs2_alloc *gfs2_alloc_get(struct gfs2_inode *ip)
921 {
922         BUG_ON(ip->i_alloc != NULL);
923         ip->i_alloc = kzalloc(sizeof(struct gfs2_alloc), GFP_KERNEL);
924         return ip->i_alloc;
925 }
926
927 /**
928  * try_rgrp_fit - See if a given reservation will fit in a given RG
929  * @rgd: the RG data
930  * @al: the struct gfs2_alloc structure describing the reservation
931  *
932  * If there's room for the requested blocks to be allocated from the RG:
933  *   Sets the $al_rgd field in @al.
934  *
935  * Returns: 1 on success (it fits), 0 on failure (it doesn't fit)
936  */
937
938 static int try_rgrp_fit(struct gfs2_rgrpd *rgd, struct gfs2_alloc *al)
939 {
940         struct gfs2_sbd *sdp = rgd->rd_sbd;
941         int ret = 0;
942
943         if (rgd->rd_flags & (GFS2_RGF_NOALLOC | GFS2_RDF_ERROR))
944                 return 0;
945
946         spin_lock(&sdp->sd_rindex_spin);
947         if (rgd->rd_free_clone >= al->al_requested) {
948                 al->al_rgd = rgd;
949                 ret = 1;
950         }
951         spin_unlock(&sdp->sd_rindex_spin);
952
953         return ret;
954 }
955
956 /**
957  * try_rgrp_unlink - Look for any unlinked, allocated, but unused inodes
958  * @rgd: The rgrp
959  *
960  * Returns: The inode, if one has been found
961  */
962
963 static struct inode *try_rgrp_unlink(struct gfs2_rgrpd *rgd, u64 *last_unlinked)
964 {
965         struct inode *inode;
966         u32 goal = 0, block;
967         u64 no_addr;
968         struct gfs2_sbd *sdp = rgd->rd_sbd;
969         unsigned int n;
970
971         for(;;) {
972                 if (goal >= rgd->rd_data)
973                         break;
974                 down_write(&sdp->sd_log_flush_lock);
975                 n = 1;
976                 block = rgblk_search(rgd, goal, GFS2_BLKST_UNLINKED,
977                                      GFS2_BLKST_UNLINKED, &n);
978                 up_write(&sdp->sd_log_flush_lock);
979                 if (block == BFITNOENT)
980                         break;
981                 /* rgblk_search can return a block < goal, so we need to
982                    keep it marching forward. */
983                 no_addr = block + rgd->rd_data0;
984                 goal++;
985                 if (*last_unlinked != NO_BLOCK && no_addr <= *last_unlinked)
986                         continue;
987                 *last_unlinked = no_addr;
988                 inode = gfs2_inode_lookup(rgd->rd_sbd->sd_vfs, DT_UNKNOWN,
989                                           no_addr, -1, 1);
990                 if (!IS_ERR(inode))
991                         return inode;
992         }
993
994         rgd->rd_flags &= ~GFS2_RDF_CHECK;
995         return NULL;
996 }
997
998 /**
999  * recent_rgrp_next - get next RG from "recent" list
1000  * @cur_rgd: current rgrp
1001  *
1002  * Returns: The next rgrp in the recent list
1003  */
1004
1005 static struct gfs2_rgrpd *recent_rgrp_next(struct gfs2_rgrpd *cur_rgd)
1006 {
1007         struct gfs2_sbd *sdp = cur_rgd->rd_sbd;
1008         struct list_head *head;
1009         struct gfs2_rgrpd *rgd;
1010
1011         spin_lock(&sdp->sd_rindex_spin);
1012         head = &sdp->sd_rindex_mru_list;
1013         if (unlikely(cur_rgd->rd_list_mru.next == head)) {
1014                 spin_unlock(&sdp->sd_rindex_spin);
1015                 return NULL;
1016         }
1017         rgd = list_entry(cur_rgd->rd_list_mru.next, struct gfs2_rgrpd, rd_list_mru);
1018         spin_unlock(&sdp->sd_rindex_spin);
1019         return rgd;
1020 }
1021
1022 /**
1023  * forward_rgrp_get - get an rgrp to try next from full list
1024  * @sdp: The GFS2 superblock
1025  *
1026  * Returns: The rgrp to try next
1027  */
1028
1029 static struct gfs2_rgrpd *forward_rgrp_get(struct gfs2_sbd *sdp)
1030 {
1031         struct gfs2_rgrpd *rgd;
1032         unsigned int journals = gfs2_jindex_size(sdp);
1033         unsigned int rg = 0, x;
1034
1035         spin_lock(&sdp->sd_rindex_spin);
1036
1037         rgd = sdp->sd_rindex_forward;
1038         if (!rgd) {
1039                 if (sdp->sd_rgrps >= journals)
1040                         rg = sdp->sd_rgrps * sdp->sd_jdesc->jd_jid / journals;
1041
1042                 for (x = 0, rgd = gfs2_rgrpd_get_first(sdp); x < rg;
1043                      x++, rgd = gfs2_rgrpd_get_next(rgd))
1044                         /* Do Nothing */;
1045
1046                 sdp->sd_rindex_forward = rgd;
1047         }
1048
1049         spin_unlock(&sdp->sd_rindex_spin);
1050
1051         return rgd;
1052 }
1053
1054 /**
1055  * forward_rgrp_set - set the forward rgrp pointer
1056  * @sdp: the filesystem
1057  * @rgd: The new forward rgrp
1058  *
1059  */
1060
1061 static void forward_rgrp_set(struct gfs2_sbd *sdp, struct gfs2_rgrpd *rgd)
1062 {
1063         spin_lock(&sdp->sd_rindex_spin);
1064         sdp->sd_rindex_forward = rgd;
1065         spin_unlock(&sdp->sd_rindex_spin);
1066 }
1067
1068 /**
1069  * get_local_rgrp - Choose and lock a rgrp for allocation
1070  * @ip: the inode to reserve space for
1071  * @rgp: the chosen and locked rgrp
1072  *
1073  * Try to acquire rgrp in way which avoids contending with others.
1074  *
1075  * Returns: errno
1076  */
1077
1078 static struct inode *get_local_rgrp(struct gfs2_inode *ip, u64 *last_unlinked)
1079 {
1080         struct inode *inode = NULL;
1081         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1082         struct gfs2_rgrpd *rgd, *begin = NULL;
1083         struct gfs2_alloc *al = ip->i_alloc;
1084         int flags = LM_FLAG_TRY;
1085         int skipped = 0;
1086         int loops = 0;
1087         int error, rg_locked;
1088
1089         rgd = gfs2_blk2rgrpd(sdp, ip->i_goal);
1090
1091         while (rgd) {
1092                 rg_locked = 0;
1093
1094                 if (gfs2_glock_is_locked_by_me(rgd->rd_gl)) {
1095                         rg_locked = 1;
1096                         error = 0;
1097                 } else {
1098                         error = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_EXCLUSIVE,
1099                                                    LM_FLAG_TRY, &al->al_rgd_gh);
1100                 }
1101                 switch (error) {
1102                 case 0:
1103                         if (try_rgrp_fit(rgd, al))
1104                                 goto out;
1105                         if (rgd->rd_flags & GFS2_RDF_CHECK)
1106                                 inode = try_rgrp_unlink(rgd, last_unlinked);
1107                         if (!rg_locked)
1108                                 gfs2_glock_dq_uninit(&al->al_rgd_gh);
1109                         if (inode)
1110                                 return inode;
1111                         /* fall through */
1112                 case GLR_TRYFAILED:
1113                         rgd = recent_rgrp_next(rgd);
1114                         break;
1115
1116                 default:
1117                         return ERR_PTR(error);
1118                 }
1119         }
1120
1121         /* Go through full list of rgrps */
1122
1123         begin = rgd = forward_rgrp_get(sdp);
1124
1125         for (;;) {
1126                 rg_locked = 0;
1127
1128                 if (gfs2_glock_is_locked_by_me(rgd->rd_gl)) {
1129                         rg_locked = 1;
1130                         error = 0;
1131                 } else {
1132                         error = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_EXCLUSIVE, flags,
1133                                                    &al->al_rgd_gh);
1134                 }
1135                 switch (error) {
1136                 case 0:
1137                         if (try_rgrp_fit(rgd, al))
1138                                 goto out;
1139                         if (rgd->rd_flags & GFS2_RDF_CHECK)
1140                                 inode = try_rgrp_unlink(rgd, last_unlinked);
1141                         if (!rg_locked)
1142                                 gfs2_glock_dq_uninit(&al->al_rgd_gh);
1143                         if (inode)
1144                                 return inode;
1145                         break;
1146
1147                 case GLR_TRYFAILED:
1148                         skipped++;
1149                         break;
1150
1151                 default:
1152                         return ERR_PTR(error);
1153                 }
1154
1155                 rgd = gfs2_rgrpd_get_next(rgd);
1156                 if (!rgd)
1157                         rgd = gfs2_rgrpd_get_first(sdp);
1158
1159                 if (rgd == begin) {
1160                         if (++loops >= 3)
1161                                 return ERR_PTR(-ENOSPC);
1162                         if (!skipped)
1163                                 loops++;
1164                         flags = 0;
1165                         if (loops == 2)
1166                                 gfs2_log_flush(sdp, NULL);
1167                 }
1168         }
1169
1170 out:
1171         if (begin) {
1172                 spin_lock(&sdp->sd_rindex_spin);
1173                 list_move(&rgd->rd_list_mru, &sdp->sd_rindex_mru_list);
1174                 spin_unlock(&sdp->sd_rindex_spin);
1175                 rgd = gfs2_rgrpd_get_next(rgd);
1176                 if (!rgd)
1177                         rgd = gfs2_rgrpd_get_first(sdp);
1178                 forward_rgrp_set(sdp, rgd);
1179         }
1180
1181         return NULL;
1182 }
1183
1184 /**
1185  * gfs2_inplace_reserve_i - Reserve space in the filesystem
1186  * @ip: the inode to reserve space for
1187  *
1188  * Returns: errno
1189  */
1190
1191 int gfs2_inplace_reserve_i(struct gfs2_inode *ip, char *file, unsigned int line)
1192 {
1193         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1194         struct gfs2_alloc *al = ip->i_alloc;
1195         struct inode *inode;
1196         int error = 0;
1197         u64 last_unlinked = NO_BLOCK;
1198
1199         if (gfs2_assert_warn(sdp, al->al_requested))
1200                 return -EINVAL;
1201
1202 try_again:
1203         /* We need to hold the rindex unless the inode we're using is
1204            the rindex itself, in which case it's already held. */
1205         if (ip != GFS2_I(sdp->sd_rindex))
1206                 error = gfs2_rindex_hold(sdp, &al->al_ri_gh);
1207         else if (!sdp->sd_rgrps) /* We may not have the rindex read in, so: */
1208                 error = gfs2_ri_update_special(ip);
1209
1210         if (error)
1211                 return error;
1212
1213         inode = get_local_rgrp(ip, &last_unlinked);
1214         if (inode) {
1215                 if (ip != GFS2_I(sdp->sd_rindex))
1216                         gfs2_glock_dq_uninit(&al->al_ri_gh);
1217                 if (IS_ERR(inode))
1218                         return PTR_ERR(inode);
1219                 iput(inode);
1220                 gfs2_log_flush(sdp, NULL);
1221                 goto try_again;
1222         }
1223
1224         al->al_file = file;
1225         al->al_line = line;
1226
1227         return 0;
1228 }
1229
1230 /**
1231  * gfs2_inplace_release - release an inplace reservation
1232  * @ip: the inode the reservation was taken out on
1233  *
1234  * Release a reservation made by gfs2_inplace_reserve().
1235  */
1236
1237 void gfs2_inplace_release(struct gfs2_inode *ip)
1238 {
1239         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1240         struct gfs2_alloc *al = ip->i_alloc;
1241
1242         if (gfs2_assert_warn(sdp, al->al_alloced <= al->al_requested) == -1)
1243                 fs_warn(sdp, "al_alloced = %u, al_requested = %u "
1244                              "al_file = %s, al_line = %u\n",
1245                              al->al_alloced, al->al_requested, al->al_file,
1246                              al->al_line);
1247
1248         al->al_rgd = NULL;
1249         if (al->al_rgd_gh.gh_gl)
1250                 gfs2_glock_dq_uninit(&al->al_rgd_gh);
1251         if (ip != GFS2_I(sdp->sd_rindex))
1252                 gfs2_glock_dq_uninit(&al->al_ri_gh);
1253 }
1254
1255 /**
1256  * gfs2_get_block_type - Check a block in a RG is of given type
1257  * @rgd: the resource group holding the block
1258  * @block: the block number
1259  *
1260  * Returns: The block type (GFS2_BLKST_*)
1261  */
1262
1263 unsigned char gfs2_get_block_type(struct gfs2_rgrpd *rgd, u64 block)
1264 {
1265         struct gfs2_bitmap *bi = NULL;
1266         u32 length, rgrp_block, buf_block;
1267         unsigned int buf;
1268         unsigned char type;
1269
1270         length = rgd->rd_length;
1271         rgrp_block = block - rgd->rd_data0;
1272
1273         for (buf = 0; buf < length; buf++) {
1274                 bi = rgd->rd_bits + buf;
1275                 if (rgrp_block < (bi->bi_start + bi->bi_len) * GFS2_NBBY)
1276                         break;
1277         }
1278
1279         gfs2_assert(rgd->rd_sbd, buf < length);
1280         buf_block = rgrp_block - bi->bi_start * GFS2_NBBY;
1281
1282         type = gfs2_testbit(rgd, bi->bi_bh->b_data + bi->bi_offset,
1283                            bi->bi_len, buf_block);
1284
1285         return type;
1286 }
1287
1288 /**
1289  * rgblk_search - find a block in @old_state, change allocation
1290  *           state to @new_state
1291  * @rgd: the resource group descriptor
1292  * @goal: the goal block within the RG (start here to search for avail block)
1293  * @old_state: GFS2_BLKST_XXX the before-allocation state to find
1294  * @new_state: GFS2_BLKST_XXX the after-allocation block state
1295  * @n: The extent length
1296  *
1297  * Walk rgrp's bitmap to find bits that represent a block in @old_state.
1298  * Add the found bitmap buffer to the transaction.
1299  * Set the found bits to @new_state to change block's allocation state.
1300  *
1301  * This function never fails, because we wouldn't call it unless we
1302  * know (from reservation results, etc.) that a block is available.
1303  *
1304  * Scope of @goal and returned block is just within rgrp, not the whole
1305  * filesystem.
1306  *
1307  * Returns:  the block number allocated
1308  */
1309
1310 static u32 rgblk_search(struct gfs2_rgrpd *rgd, u32 goal,
1311                         unsigned char old_state, unsigned char new_state,
1312                         unsigned int *n)
1313 {
1314         struct gfs2_bitmap *bi = NULL;
1315         const u32 length = rgd->rd_length;
1316         u32 blk = BFITNOENT;
1317         unsigned int buf, x;
1318         const unsigned int elen = *n;
1319         const u8 *buffer = NULL;
1320
1321         *n = 0;
1322         /* Find bitmap block that contains bits for goal block */
1323         for (buf = 0; buf < length; buf++) {
1324                 bi = rgd->rd_bits + buf;
1325                 /* Convert scope of "goal" from rgrp-wide to within found bit block */
1326                 if (goal < (bi->bi_start + bi->bi_len) * GFS2_NBBY) {
1327                         goal -= bi->bi_start * GFS2_NBBY;
1328                         goto do_search;
1329                 }
1330         }
1331         buf = 0;
1332         goal = 0;
1333
1334 do_search:
1335         /* Search (up to entire) bitmap in this rgrp for allocatable block.
1336            "x <= length", instead of "x < length", because we typically start
1337            the search in the middle of a bit block, but if we can't find an
1338            allocatable block anywhere else, we want to be able wrap around and
1339            search in the first part of our first-searched bit block.  */
1340         for (x = 0; x <= length; x++) {
1341                 bi = rgd->rd_bits + buf;
1342
1343                 if (test_bit(GBF_FULL, &bi->bi_flags) &&
1344                     (old_state == GFS2_BLKST_FREE))
1345                         goto skip;
1346
1347                 /* The GFS2_BLKST_UNLINKED state doesn't apply to the clone
1348                    bitmaps, so we must search the originals for that. */
1349                 buffer = bi->bi_bh->b_data + bi->bi_offset;
1350                 if (old_state != GFS2_BLKST_UNLINKED && bi->bi_clone)
1351                         buffer = bi->bi_clone + bi->bi_offset;
1352
1353                 blk = gfs2_bitfit(buffer, bi->bi_len, goal, old_state);
1354                 if (blk != BFITNOENT)
1355                         break;
1356
1357                 if ((goal == 0) && (old_state == GFS2_BLKST_FREE))
1358                         set_bit(GBF_FULL, &bi->bi_flags);
1359
1360                 /* Try next bitmap block (wrap back to rgrp header if at end) */
1361 skip:
1362                 buf++;
1363                 buf %= length;
1364                 goal = 0;
1365         }
1366
1367         if (blk == BFITNOENT)
1368                 return blk;
1369         *n = 1;
1370         if (old_state == new_state)
1371                 goto out;
1372
1373         gfs2_trans_add_bh(rgd->rd_gl, bi->bi_bh, 1);
1374         gfs2_setbit(rgd, bi->bi_bh->b_data, bi->bi_clone, bi->bi_offset,
1375                     bi->bi_len, blk, new_state);
1376         goal = blk;
1377         while (*n < elen) {
1378                 goal++;
1379                 if (goal >= (bi->bi_len * GFS2_NBBY))
1380                         break;
1381                 if (gfs2_testbit(rgd, buffer, bi->bi_len, goal) !=
1382                     GFS2_BLKST_FREE)
1383                         break;
1384                 gfs2_setbit(rgd, bi->bi_bh->b_data, bi->bi_clone, bi->bi_offset,
1385                             bi->bi_len, goal, new_state);
1386                 (*n)++;
1387         }
1388 out:
1389         return (bi->bi_start * GFS2_NBBY) + blk;
1390 }
1391
1392 /**
1393  * rgblk_free - Change alloc state of given block(s)
1394  * @sdp: the filesystem
1395  * @bstart: the start of a run of blocks to free
1396  * @blen: the length of the block run (all must lie within ONE RG!)
1397  * @new_state: GFS2_BLKST_XXX the after-allocation block state
1398  *
1399  * Returns:  Resource group containing the block(s)
1400  */
1401
1402 static struct gfs2_rgrpd *rgblk_free(struct gfs2_sbd *sdp, u64 bstart,
1403                                      u32 blen, unsigned char new_state)
1404 {
1405         struct gfs2_rgrpd *rgd;
1406         struct gfs2_bitmap *bi = NULL;
1407         u32 length, rgrp_blk, buf_blk;
1408         unsigned int buf;
1409
1410         rgd = gfs2_blk2rgrpd(sdp, bstart);
1411         if (!rgd) {
1412                 if (gfs2_consist(sdp))
1413                         fs_err(sdp, "block = %llu\n", (unsigned long long)bstart);
1414                 return NULL;
1415         }
1416
1417         length = rgd->rd_length;
1418
1419         rgrp_blk = bstart - rgd->rd_data0;
1420
1421         while (blen--) {
1422                 for (buf = 0; buf < length; buf++) {
1423                         bi = rgd->rd_bits + buf;
1424                         if (rgrp_blk < (bi->bi_start + bi->bi_len) * GFS2_NBBY)
1425                                 break;
1426                 }
1427
1428                 gfs2_assert(rgd->rd_sbd, buf < length);
1429
1430                 buf_blk = rgrp_blk - bi->bi_start * GFS2_NBBY;
1431                 rgrp_blk++;
1432
1433                 if (!bi->bi_clone) {
1434                         bi->bi_clone = kmalloc(bi->bi_bh->b_size,
1435                                                GFP_NOFS | __GFP_NOFAIL);
1436                         memcpy(bi->bi_clone + bi->bi_offset,
1437                                bi->bi_bh->b_data + bi->bi_offset,
1438                                bi->bi_len);
1439                 }
1440                 gfs2_trans_add_bh(rgd->rd_gl, bi->bi_bh, 1);
1441                 gfs2_setbit(rgd, bi->bi_bh->b_data, NULL, bi->bi_offset,
1442                             bi->bi_len, buf_blk, new_state);
1443         }
1444
1445         return rgd;
1446 }
1447
1448 /**
1449  * gfs2_rgrp_dump - print out an rgrp
1450  * @seq: The iterator
1451  * @gl: The glock in question
1452  *
1453  */
1454
1455 int gfs2_rgrp_dump(struct seq_file *seq, const struct gfs2_glock *gl)
1456 {
1457         const struct gfs2_rgrpd *rgd = gl->gl_object;
1458         if (rgd == NULL)
1459                 return 0;
1460         gfs2_print_dbg(seq, " R: n:%llu f:%02x b:%u/%u i:%u\n",
1461                        (unsigned long long)rgd->rd_addr, rgd->rd_flags,
1462                        rgd->rd_free, rgd->rd_free_clone, rgd->rd_dinodes);
1463         return 0;
1464 }
1465
1466 /**
1467  * gfs2_alloc_block - Allocate one or more blocks
1468  * @ip: the inode to allocate the block for
1469  * @bn: Used to return the starting block number
1470  * @n: requested number of blocks/extent length (value/result)
1471  *
1472  * Returns: 0 or error
1473  */
1474
1475 int gfs2_alloc_block(struct gfs2_inode *ip, u64 *bn, unsigned int *n)
1476 {
1477         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1478         struct buffer_head *dibh;
1479         struct gfs2_alloc *al = ip->i_alloc;
1480         struct gfs2_rgrpd *rgd = al->al_rgd;
1481         u32 goal, blk;
1482         u64 block;
1483         int error;
1484
1485         if (rgrp_contains_block(rgd, ip->i_goal))
1486                 goal = ip->i_goal - rgd->rd_data0;
1487         else
1488                 goal = rgd->rd_last_alloc;
1489
1490         blk = rgblk_search(rgd, goal, GFS2_BLKST_FREE, GFS2_BLKST_USED, n);
1491
1492         /* Since all blocks are reserved in advance, this shouldn't happen */
1493         if (blk == BFITNOENT)
1494                 goto rgrp_error;
1495
1496         rgd->rd_last_alloc = blk;
1497         block = rgd->rd_data0 + blk;
1498         ip->i_goal = block;
1499         error = gfs2_meta_inode_buffer(ip, &dibh);
1500         if (error == 0) {
1501                 struct gfs2_dinode *di = (struct gfs2_dinode *)dibh->b_data;
1502                 gfs2_trans_add_bh(ip->i_gl, dibh, 1);
1503                 di->di_goal_meta = di->di_goal_data = cpu_to_be64(ip->i_goal);
1504                 brelse(dibh);
1505         }
1506         if (rgd->rd_free < *n)
1507                 goto rgrp_error;
1508
1509         rgd->rd_free -= *n;
1510
1511         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1512         gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
1513
1514         al->al_alloced += *n;
1515
1516         gfs2_statfs_change(sdp, 0, -(s64)*n, 0);
1517         gfs2_quota_change(ip, *n, ip->i_inode.i_uid, ip->i_inode.i_gid);
1518
1519         spin_lock(&sdp->sd_rindex_spin);
1520         rgd->rd_free_clone -= *n;
1521         spin_unlock(&sdp->sd_rindex_spin);
1522
1523         *bn = block;
1524         return 0;
1525
1526 rgrp_error:
1527         fs_warn(sdp, "rgrp %llu has an error, marking it readonly until umount\n",
1528                 (unsigned long long)rgd->rd_addr);
1529         fs_warn(sdp, "umount on all nodes and run fsck.gfs2 to fix the error\n");
1530         gfs2_rgrp_dump(NULL, rgd->rd_gl);
1531         rgd->rd_flags |= GFS2_RDF_ERROR;
1532         return -EIO;
1533 }
1534
1535 /**
1536  * gfs2_alloc_di - Allocate a dinode
1537  * @dip: the directory that the inode is going in
1538  *
1539  * Returns: the block allocated
1540  */
1541
1542 u64 gfs2_alloc_di(struct gfs2_inode *dip, u64 *generation)
1543 {
1544         struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode);
1545         struct gfs2_alloc *al = dip->i_alloc;
1546         struct gfs2_rgrpd *rgd = al->al_rgd;
1547         u32 blk;
1548         u64 block;
1549         unsigned int n = 1;
1550
1551         blk = rgblk_search(rgd, rgd->rd_last_alloc,
1552                            GFS2_BLKST_FREE, GFS2_BLKST_DINODE, &n);
1553         BUG_ON(blk == BFITNOENT);
1554
1555         rgd->rd_last_alloc = blk;
1556
1557         block = rgd->rd_data0 + blk;
1558
1559         gfs2_assert_withdraw(sdp, rgd->rd_free);
1560         rgd->rd_free--;
1561         rgd->rd_dinodes++;
1562         *generation = rgd->rd_igeneration++;
1563         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1564         gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
1565
1566         al->al_alloced++;
1567
1568         gfs2_statfs_change(sdp, 0, -1, +1);
1569         gfs2_trans_add_unrevoke(sdp, block, 1);
1570
1571         spin_lock(&sdp->sd_rindex_spin);
1572         rgd->rd_free_clone--;
1573         spin_unlock(&sdp->sd_rindex_spin);
1574
1575         return block;
1576 }
1577
1578 /**
1579  * gfs2_free_data - free a contiguous run of data block(s)
1580  * @ip: the inode these blocks are being freed from
1581  * @bstart: first block of a run of contiguous blocks
1582  * @blen: the length of the block run
1583  *
1584  */
1585
1586 void gfs2_free_data(struct gfs2_inode *ip, u64 bstart, u32 blen)
1587 {
1588         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1589         struct gfs2_rgrpd *rgd;
1590
1591         rgd = rgblk_free(sdp, bstart, blen, GFS2_BLKST_FREE);
1592         if (!rgd)
1593                 return;
1594
1595         rgd->rd_free += blen;
1596
1597         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1598         gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
1599
1600         gfs2_trans_add_rg(rgd);
1601
1602         gfs2_statfs_change(sdp, 0, +blen, 0);
1603         gfs2_quota_change(ip, -(s64)blen, ip->i_inode.i_uid, ip->i_inode.i_gid);
1604 }
1605
1606 /**
1607  * gfs2_free_meta - free a contiguous run of data block(s)
1608  * @ip: the inode these blocks are being freed from
1609  * @bstart: first block of a run of contiguous blocks
1610  * @blen: the length of the block run
1611  *
1612  */
1613
1614 void gfs2_free_meta(struct gfs2_inode *ip, u64 bstart, u32 blen)
1615 {
1616         struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1617         struct gfs2_rgrpd *rgd;
1618
1619         rgd = rgblk_free(sdp, bstart, blen, GFS2_BLKST_FREE);
1620         if (!rgd)
1621                 return;
1622
1623         rgd->rd_free += blen;
1624
1625         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1626         gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
1627
1628         gfs2_trans_add_rg(rgd);
1629
1630         gfs2_statfs_change(sdp, 0, +blen, 0);
1631         gfs2_quota_change(ip, -(s64)blen, ip->i_inode.i_uid, ip->i_inode.i_gid);
1632         gfs2_meta_wipe(ip, bstart, blen);
1633 }
1634
1635 void gfs2_unlink_di(struct inode *inode)
1636 {
1637         struct gfs2_inode *ip = GFS2_I(inode);
1638         struct gfs2_sbd *sdp = GFS2_SB(inode);
1639         struct gfs2_rgrpd *rgd;
1640         u64 blkno = ip->i_no_addr;
1641
1642         rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_UNLINKED);
1643         if (!rgd)
1644                 return;
1645         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1646         gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
1647         gfs2_trans_add_rg(rgd);
1648 }
1649
1650 static void gfs2_free_uninit_di(struct gfs2_rgrpd *rgd, u64 blkno)
1651 {
1652         struct gfs2_sbd *sdp = rgd->rd_sbd;
1653         struct gfs2_rgrpd *tmp_rgd;
1654
1655         tmp_rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_FREE);
1656         if (!tmp_rgd)
1657                 return;
1658         gfs2_assert_withdraw(sdp, rgd == tmp_rgd);
1659
1660         if (!rgd->rd_dinodes)
1661                 gfs2_consist_rgrpd(rgd);
1662         rgd->rd_dinodes--;
1663         rgd->rd_free++;
1664
1665         gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1666         gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
1667
1668         gfs2_statfs_change(sdp, 0, +1, -1);
1669         gfs2_trans_add_rg(rgd);
1670 }
1671
1672
1673 void gfs2_free_di(struct gfs2_rgrpd *rgd, struct gfs2_inode *ip)
1674 {
1675         gfs2_free_uninit_di(rgd, ip->i_no_addr);
1676         gfs2_quota_change(ip, -1, ip->i_inode.i_uid, ip->i_inode.i_gid);
1677         gfs2_meta_wipe(ip, ip->i_no_addr, 1);
1678 }
1679
1680 /**
1681  * gfs2_rlist_add - add a RG to a list of RGs
1682  * @sdp: the filesystem
1683  * @rlist: the list of resource groups
1684  * @block: the block
1685  *
1686  * Figure out what RG a block belongs to and add that RG to the list
1687  *
1688  * FIXME: Don't use NOFAIL
1689  *
1690  */
1691
1692 void gfs2_rlist_add(struct gfs2_sbd *sdp, struct gfs2_rgrp_list *rlist,
1693                     u64 block)
1694 {
1695         struct gfs2_rgrpd *rgd;
1696         struct gfs2_rgrpd **tmp;
1697         unsigned int new_space;
1698         unsigned int x;
1699
1700         if (gfs2_assert_warn(sdp, !rlist->rl_ghs))
1701                 return;
1702
1703         rgd = gfs2_blk2rgrpd(sdp, block);
1704         if (!rgd) {
1705                 if (gfs2_consist(sdp))
1706                         fs_err(sdp, "block = %llu\n", (unsigned long long)block);
1707                 return;
1708         }
1709
1710         for (x = 0; x < rlist->rl_rgrps; x++)
1711                 if (rlist->rl_rgd[x] == rgd)
1712                         return;
1713
1714         if (rlist->rl_rgrps == rlist->rl_space) {
1715                 new_space = rlist->rl_space + 10;
1716
1717                 tmp = kcalloc(new_space, sizeof(struct gfs2_rgrpd *),
1718                               GFP_NOFS | __GFP_NOFAIL);
1719
1720                 if (rlist->rl_rgd) {
1721                         memcpy(tmp, rlist->rl_rgd,
1722                                rlist->rl_space * sizeof(struct gfs2_rgrpd *));
1723                         kfree(rlist->rl_rgd);
1724                 }
1725
1726                 rlist->rl_space = new_space;
1727                 rlist->rl_rgd = tmp;
1728         }
1729
1730         rlist->rl_rgd[rlist->rl_rgrps++] = rgd;
1731 }
1732
1733 /**
1734  * gfs2_rlist_alloc - all RGs have been added to the rlist, now allocate
1735  *      and initialize an array of glock holders for them
1736  * @rlist: the list of resource groups
1737  * @state: the lock state to acquire the RG lock in
1738  * @flags: the modifier flags for the holder structures
1739  *
1740  * FIXME: Don't use NOFAIL
1741  *
1742  */
1743
1744 void gfs2_rlist_alloc(struct gfs2_rgrp_list *rlist, unsigned int state)
1745 {
1746         unsigned int x;
1747
1748         rlist->rl_ghs = kcalloc(rlist->rl_rgrps, sizeof(struct gfs2_holder),
1749                                 GFP_NOFS | __GFP_NOFAIL);
1750         for (x = 0; x < rlist->rl_rgrps; x++)
1751                 gfs2_holder_init(rlist->rl_rgd[x]->rd_gl,
1752                                 state, 0,
1753                                 &rlist->rl_ghs[x]);
1754 }
1755
1756 /**
1757  * gfs2_rlist_free - free a resource group list
1758  * @list: the list of resource groups
1759  *
1760  */
1761
1762 void gfs2_rlist_free(struct gfs2_rgrp_list *rlist)
1763 {
1764         unsigned int x;
1765
1766         kfree(rlist->rl_rgd);
1767
1768         if (rlist->rl_ghs) {
1769                 for (x = 0; x < rlist->rl_rgrps; x++)
1770                         gfs2_holder_uninit(&rlist->rl_ghs[x]);
1771                 kfree(rlist->rl_ghs);
1772         }
1773 }
1774