Loading...
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#include <linux/rbtree.h>
19
20#include "gfs2.h"
21#include "incore.h"
22#include "glock.h"
23#include "glops.h"
24#include "lops.h"
25#include "meta_io.h"
26#include "quota.h"
27#include "rgrp.h"
28#include "super.h"
29#include "trans.h"
30#include "util.h"
31#include "log.h"
32#include "inode.h"
33#include "trace_gfs2.h"
34
35#define BFITNOENT ((u32)~0)
36#define NO_BLOCK ((u64)~0)
37
38#if BITS_PER_LONG == 32
39#define LBITMASK (0x55555555UL)
40#define LBITSKIP55 (0x55555555UL)
41#define LBITSKIP00 (0x00000000UL)
42#else
43#define LBITMASK (0x5555555555555555UL)
44#define LBITSKIP55 (0x5555555555555555UL)
45#define LBITSKIP00 (0x0000000000000000UL)
46#endif
47
48/*
49 * These routines are used by the resource group routines (rgrp.c)
50 * to keep track of block allocation. Each block is represented by two
51 * bits. So, each byte represents GFS2_NBBY (i.e. 4) blocks.
52 *
53 * 0 = Free
54 * 1 = Used (not metadata)
55 * 2 = Unlinked (still in use) inode
56 * 3 = Used (metadata)
57 */
58
59static const char valid_change[16] = {
60 /* current */
61 /* n */ 0, 1, 1, 1,
62 /* e */ 1, 0, 0, 0,
63 /* w */ 0, 0, 0, 1,
64 1, 0, 0, 0
65};
66
67static u32 rgblk_search(struct gfs2_rgrpd *rgd, u32 goal,
68 unsigned char old_state,
69 struct gfs2_bitmap **rbi);
70
71/**
72 * gfs2_setbit - Set a bit in the bitmaps
73 * @rgd: the resource group descriptor
74 * @buf2: the clone buffer that holds the bitmaps
75 * @bi: the bitmap structure
76 * @block: the block to set
77 * @new_state: the new state of the block
78 *
79 */
80
81static inline void gfs2_setbit(struct gfs2_rgrpd *rgd, unsigned char *buf2,
82 struct gfs2_bitmap *bi, u32 block,
83 unsigned char new_state)
84{
85 unsigned char *byte1, *byte2, *end, cur_state;
86 unsigned int buflen = bi->bi_len;
87 const unsigned int bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
88
89 byte1 = bi->bi_bh->b_data + bi->bi_offset + (block / GFS2_NBBY);
90 end = bi->bi_bh->b_data + bi->bi_offset + buflen;
91
92 BUG_ON(byte1 >= end);
93
94 cur_state = (*byte1 >> bit) & GFS2_BIT_MASK;
95
96 if (unlikely(!valid_change[new_state * 4 + cur_state])) {
97 printk(KERN_WARNING "GFS2: buf_blk = 0x%llx old_state=%d, "
98 "new_state=%d\n",
99 (unsigned long long)block, cur_state, new_state);
100 printk(KERN_WARNING "GFS2: rgrp=0x%llx bi_start=0x%lx\n",
101 (unsigned long long)rgd->rd_addr,
102 (unsigned long)bi->bi_start);
103 printk(KERN_WARNING "GFS2: bi_offset=0x%lx bi_len=0x%lx\n",
104 (unsigned long)bi->bi_offset,
105 (unsigned long)bi->bi_len);
106 dump_stack();
107 gfs2_consist_rgrpd(rgd);
108 return;
109 }
110 *byte1 ^= (cur_state ^ new_state) << bit;
111
112 if (buf2) {
113 byte2 = buf2 + bi->bi_offset + (block / GFS2_NBBY);
114 cur_state = (*byte2 >> bit) & GFS2_BIT_MASK;
115 *byte2 ^= (cur_state ^ new_state) << bit;
116 }
117}
118
119/**
120 * gfs2_testbit - test a bit in the bitmaps
121 * @rgd: the resource group descriptor
122 * @buffer: the buffer that holds the bitmaps
123 * @buflen: the length (in bytes) of the buffer
124 * @block: the block to read
125 *
126 */
127
128static inline unsigned char gfs2_testbit(struct gfs2_rgrpd *rgd,
129 const unsigned char *buffer,
130 unsigned int buflen, u32 block)
131{
132 const unsigned char *byte, *end;
133 unsigned char cur_state;
134 unsigned int bit;
135
136 byte = buffer + (block / GFS2_NBBY);
137 bit = (block % GFS2_NBBY) * GFS2_BIT_SIZE;
138 end = buffer + buflen;
139
140 gfs2_assert(rgd->rd_sbd, byte < end);
141
142 cur_state = (*byte >> bit) & GFS2_BIT_MASK;
143
144 return cur_state;
145}
146
147/**
148 * gfs2_bit_search
149 * @ptr: Pointer to bitmap data
150 * @mask: Mask to use (normally 0x55555.... but adjusted for search start)
151 * @state: The state we are searching for
152 *
153 * We xor the bitmap data with a patter which is the bitwise opposite
154 * of what we are looking for, this gives rise to a pattern of ones
155 * wherever there is a match. Since we have two bits per entry, we
156 * take this pattern, shift it down by one place and then and it with
157 * the original. All the even bit positions (0,2,4, etc) then represent
158 * successful matches, so we mask with 0x55555..... to remove the unwanted
159 * odd bit positions.
160 *
161 * This allows searching of a whole u64 at once (32 blocks) with a
162 * single test (on 64 bit arches).
163 */
164
165static inline u64 gfs2_bit_search(const __le64 *ptr, u64 mask, u8 state)
166{
167 u64 tmp;
168 static const u64 search[] = {
169 [0] = 0xffffffffffffffffULL,
170 [1] = 0xaaaaaaaaaaaaaaaaULL,
171 [2] = 0x5555555555555555ULL,
172 [3] = 0x0000000000000000ULL,
173 };
174 tmp = le64_to_cpu(*ptr) ^ search[state];
175 tmp &= (tmp >> 1);
176 tmp &= mask;
177 return tmp;
178}
179
180/**
181 * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
182 * a block in a given allocation state.
183 * @buf: the buffer that holds the bitmaps
184 * @len: the length (in bytes) of the buffer
185 * @goal: start search at this block's bit-pair (within @buffer)
186 * @state: GFS2_BLKST_XXX the state of the block we're looking for.
187 *
188 * Scope of @goal and returned block number is only within this bitmap buffer,
189 * not entire rgrp or filesystem. @buffer will be offset from the actual
190 * beginning of a bitmap block buffer, skipping any header structures, but
191 * headers are always a multiple of 64 bits long so that the buffer is
192 * always aligned to a 64 bit boundary.
193 *
194 * The size of the buffer is in bytes, but is it assumed that it is
195 * always ok to read a complete multiple of 64 bits at the end
196 * of the block in case the end is no aligned to a natural boundary.
197 *
198 * Return: the block number (bitmap buffer scope) that was found
199 */
200
201static u32 gfs2_bitfit(const u8 *buf, const unsigned int len,
202 u32 goal, u8 state)
203{
204 u32 spoint = (goal << 1) & ((8*sizeof(u64)) - 1);
205 const __le64 *ptr = ((__le64 *)buf) + (goal >> 5);
206 const __le64 *end = (__le64 *)(buf + ALIGN(len, sizeof(u64)));
207 u64 tmp;
208 u64 mask = 0x5555555555555555ULL;
209 u32 bit;
210
211 BUG_ON(state > 3);
212
213 /* Mask off bits we don't care about at the start of the search */
214 mask <<= spoint;
215 tmp = gfs2_bit_search(ptr, mask, state);
216 ptr++;
217 while(tmp == 0 && ptr < end) {
218 tmp = gfs2_bit_search(ptr, 0x5555555555555555ULL, state);
219 ptr++;
220 }
221 /* Mask off any bits which are more than len bytes from the start */
222 if (ptr == end && (len & (sizeof(u64) - 1)))
223 tmp &= (((u64)~0) >> (64 - 8*(len & (sizeof(u64) - 1))));
224 /* Didn't find anything, so return */
225 if (tmp == 0)
226 return BFITNOENT;
227 ptr--;
228 bit = __ffs64(tmp);
229 bit /= 2; /* two bits per entry in the bitmap */
230 return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
231}
232
233/**
234 * gfs2_bitcount - count the number of bits in a certain state
235 * @rgd: the resource group descriptor
236 * @buffer: the buffer that holds the bitmaps
237 * @buflen: the length (in bytes) of the buffer
238 * @state: the state of the block we're looking for
239 *
240 * Returns: The number of bits
241 */
242
243static u32 gfs2_bitcount(struct gfs2_rgrpd *rgd, const u8 *buffer,
244 unsigned int buflen, u8 state)
245{
246 const u8 *byte = buffer;
247 const u8 *end = buffer + buflen;
248 const u8 state1 = state << 2;
249 const u8 state2 = state << 4;
250 const u8 state3 = state << 6;
251 u32 count = 0;
252
253 for (; byte < end; byte++) {
254 if (((*byte) & 0x03) == state)
255 count++;
256 if (((*byte) & 0x0C) == state1)
257 count++;
258 if (((*byte) & 0x30) == state2)
259 count++;
260 if (((*byte) & 0xC0) == state3)
261 count++;
262 }
263
264 return count;
265}
266
267/**
268 * gfs2_rgrp_verify - Verify that a resource group is consistent
269 * @rgd: the rgrp
270 *
271 */
272
273void gfs2_rgrp_verify(struct gfs2_rgrpd *rgd)
274{
275 struct gfs2_sbd *sdp = rgd->rd_sbd;
276 struct gfs2_bitmap *bi = NULL;
277 u32 length = rgd->rd_length;
278 u32 count[4], tmp;
279 int buf, x;
280
281 memset(count, 0, 4 * sizeof(u32));
282
283 /* Count # blocks in each of 4 possible allocation states */
284 for (buf = 0; buf < length; buf++) {
285 bi = rgd->rd_bits + buf;
286 for (x = 0; x < 4; x++)
287 count[x] += gfs2_bitcount(rgd,
288 bi->bi_bh->b_data +
289 bi->bi_offset,
290 bi->bi_len, x);
291 }
292
293 if (count[0] != rgd->rd_free) {
294 if (gfs2_consist_rgrpd(rgd))
295 fs_err(sdp, "free data mismatch: %u != %u\n",
296 count[0], rgd->rd_free);
297 return;
298 }
299
300 tmp = rgd->rd_data - rgd->rd_free - rgd->rd_dinodes;
301 if (count[1] != tmp) {
302 if (gfs2_consist_rgrpd(rgd))
303 fs_err(sdp, "used data mismatch: %u != %u\n",
304 count[1], tmp);
305 return;
306 }
307
308 if (count[2] + count[3] != rgd->rd_dinodes) {
309 if (gfs2_consist_rgrpd(rgd))
310 fs_err(sdp, "used metadata mismatch: %u != %u\n",
311 count[2] + count[3], rgd->rd_dinodes);
312 return;
313 }
314}
315
316static inline int rgrp_contains_block(struct gfs2_rgrpd *rgd, u64 block)
317{
318 u64 first = rgd->rd_data0;
319 u64 last = first + rgd->rd_data;
320 return first <= block && block < last;
321}
322
323/**
324 * gfs2_blk2rgrpd - Find resource group for a given data/meta block number
325 * @sdp: The GFS2 superblock
326 * @blk: The data block number
327 * @exact: True if this needs to be an exact match
328 *
329 * Returns: The resource group, or NULL if not found
330 */
331
332struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk, bool exact)
333{
334 struct rb_node *n, *next;
335 struct gfs2_rgrpd *cur;
336
337 spin_lock(&sdp->sd_rindex_spin);
338 n = sdp->sd_rindex_tree.rb_node;
339 while (n) {
340 cur = rb_entry(n, struct gfs2_rgrpd, rd_node);
341 next = NULL;
342 if (blk < cur->rd_addr)
343 next = n->rb_left;
344 else if (blk >= cur->rd_data0 + cur->rd_data)
345 next = n->rb_right;
346 if (next == NULL) {
347 spin_unlock(&sdp->sd_rindex_spin);
348 if (exact) {
349 if (blk < cur->rd_addr)
350 return NULL;
351 if (blk >= cur->rd_data0 + cur->rd_data)
352 return NULL;
353 }
354 return cur;
355 }
356 n = next;
357 }
358 spin_unlock(&sdp->sd_rindex_spin);
359
360 return NULL;
361}
362
363/**
364 * gfs2_rgrpd_get_first - get the first Resource Group in the filesystem
365 * @sdp: The GFS2 superblock
366 *
367 * Returns: The first rgrp in the filesystem
368 */
369
370struct gfs2_rgrpd *gfs2_rgrpd_get_first(struct gfs2_sbd *sdp)
371{
372 const struct rb_node *n;
373 struct gfs2_rgrpd *rgd;
374
375 spin_lock(&sdp->sd_rindex_spin);
376 n = rb_first(&sdp->sd_rindex_tree);
377 rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
378 spin_unlock(&sdp->sd_rindex_spin);
379
380 return rgd;
381}
382
383/**
384 * gfs2_rgrpd_get_next - get the next RG
385 * @rgd: the resource group descriptor
386 *
387 * Returns: The next rgrp
388 */
389
390struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
391{
392 struct gfs2_sbd *sdp = rgd->rd_sbd;
393 const struct rb_node *n;
394
395 spin_lock(&sdp->sd_rindex_spin);
396 n = rb_next(&rgd->rd_node);
397 if (n == NULL)
398 n = rb_first(&sdp->sd_rindex_tree);
399
400 if (unlikely(&rgd->rd_node == n)) {
401 spin_unlock(&sdp->sd_rindex_spin);
402 return NULL;
403 }
404 rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
405 spin_unlock(&sdp->sd_rindex_spin);
406 return rgd;
407}
408
409void gfs2_free_clones(struct gfs2_rgrpd *rgd)
410{
411 int x;
412
413 for (x = 0; x < rgd->rd_length; x++) {
414 struct gfs2_bitmap *bi = rgd->rd_bits + x;
415 kfree(bi->bi_clone);
416 bi->bi_clone = NULL;
417 }
418}
419
420void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
421{
422 struct rb_node *n;
423 struct gfs2_rgrpd *rgd;
424 struct gfs2_glock *gl;
425
426 while ((n = rb_first(&sdp->sd_rindex_tree))) {
427 rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
428 gl = rgd->rd_gl;
429
430 rb_erase(n, &sdp->sd_rindex_tree);
431
432 if (gl) {
433 spin_lock(&gl->gl_spin);
434 gl->gl_object = NULL;
435 spin_unlock(&gl->gl_spin);
436 gfs2_glock_add_to_lru(gl);
437 gfs2_glock_put(gl);
438 }
439
440 gfs2_free_clones(rgd);
441 kfree(rgd->rd_bits);
442 kmem_cache_free(gfs2_rgrpd_cachep, rgd);
443 }
444}
445
446static void gfs2_rindex_print(const struct gfs2_rgrpd *rgd)
447{
448 printk(KERN_INFO " ri_addr = %llu\n", (unsigned long long)rgd->rd_addr);
449 printk(KERN_INFO " ri_length = %u\n", rgd->rd_length);
450 printk(KERN_INFO " ri_data0 = %llu\n", (unsigned long long)rgd->rd_data0);
451 printk(KERN_INFO " ri_data = %u\n", rgd->rd_data);
452 printk(KERN_INFO " ri_bitbytes = %u\n", rgd->rd_bitbytes);
453}
454
455/**
456 * gfs2_compute_bitstructs - Compute the bitmap sizes
457 * @rgd: The resource group descriptor
458 *
459 * Calculates bitmap descriptors, one for each block that contains bitmap data
460 *
461 * Returns: errno
462 */
463
464static int compute_bitstructs(struct gfs2_rgrpd *rgd)
465{
466 struct gfs2_sbd *sdp = rgd->rd_sbd;
467 struct gfs2_bitmap *bi;
468 u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
469 u32 bytes_left, bytes;
470 int x;
471
472 if (!length)
473 return -EINVAL;
474
475 rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
476 if (!rgd->rd_bits)
477 return -ENOMEM;
478
479 bytes_left = rgd->rd_bitbytes;
480
481 for (x = 0; x < length; x++) {
482 bi = rgd->rd_bits + x;
483
484 bi->bi_flags = 0;
485 /* small rgrp; bitmap stored completely in header block */
486 if (length == 1) {
487 bytes = bytes_left;
488 bi->bi_offset = sizeof(struct gfs2_rgrp);
489 bi->bi_start = 0;
490 bi->bi_len = bytes;
491 /* header block */
492 } else if (x == 0) {
493 bytes = sdp->sd_sb.sb_bsize - sizeof(struct gfs2_rgrp);
494 bi->bi_offset = sizeof(struct gfs2_rgrp);
495 bi->bi_start = 0;
496 bi->bi_len = bytes;
497 /* last block */
498 } else if (x + 1 == length) {
499 bytes = bytes_left;
500 bi->bi_offset = sizeof(struct gfs2_meta_header);
501 bi->bi_start = rgd->rd_bitbytes - bytes_left;
502 bi->bi_len = bytes;
503 /* other blocks */
504 } else {
505 bytes = sdp->sd_sb.sb_bsize -
506 sizeof(struct gfs2_meta_header);
507 bi->bi_offset = sizeof(struct gfs2_meta_header);
508 bi->bi_start = rgd->rd_bitbytes - bytes_left;
509 bi->bi_len = bytes;
510 }
511
512 bytes_left -= bytes;
513 }
514
515 if (bytes_left) {
516 gfs2_consist_rgrpd(rgd);
517 return -EIO;
518 }
519 bi = rgd->rd_bits + (length - 1);
520 if ((bi->bi_start + bi->bi_len) * GFS2_NBBY != rgd->rd_data) {
521 if (gfs2_consist_rgrpd(rgd)) {
522 gfs2_rindex_print(rgd);
523 fs_err(sdp, "start=%u len=%u offset=%u\n",
524 bi->bi_start, bi->bi_len, bi->bi_offset);
525 }
526 return -EIO;
527 }
528
529 return 0;
530}
531
532/**
533 * gfs2_ri_total - Total up the file system space, according to the rindex.
534 * @sdp: the filesystem
535 *
536 */
537u64 gfs2_ri_total(struct gfs2_sbd *sdp)
538{
539 u64 total_data = 0;
540 struct inode *inode = sdp->sd_rindex;
541 struct gfs2_inode *ip = GFS2_I(inode);
542 char buf[sizeof(struct gfs2_rindex)];
543 int error, rgrps;
544
545 for (rgrps = 0;; rgrps++) {
546 loff_t pos = rgrps * sizeof(struct gfs2_rindex);
547
548 if (pos + sizeof(struct gfs2_rindex) > i_size_read(inode))
549 break;
550 error = gfs2_internal_read(ip, buf, &pos,
551 sizeof(struct gfs2_rindex));
552 if (error != sizeof(struct gfs2_rindex))
553 break;
554 total_data += be32_to_cpu(((struct gfs2_rindex *)buf)->ri_data);
555 }
556 return total_data;
557}
558
559static int rgd_insert(struct gfs2_rgrpd *rgd)
560{
561 struct gfs2_sbd *sdp = rgd->rd_sbd;
562 struct rb_node **newn = &sdp->sd_rindex_tree.rb_node, *parent = NULL;
563
564 /* Figure out where to put new node */
565 while (*newn) {
566 struct gfs2_rgrpd *cur = rb_entry(*newn, struct gfs2_rgrpd,
567 rd_node);
568
569 parent = *newn;
570 if (rgd->rd_addr < cur->rd_addr)
571 newn = &((*newn)->rb_left);
572 else if (rgd->rd_addr > cur->rd_addr)
573 newn = &((*newn)->rb_right);
574 else
575 return -EEXIST;
576 }
577
578 rb_link_node(&rgd->rd_node, parent, newn);
579 rb_insert_color(&rgd->rd_node, &sdp->sd_rindex_tree);
580 sdp->sd_rgrps++;
581 return 0;
582}
583
584/**
585 * read_rindex_entry - Pull in a new resource index entry from the disk
586 * @ip: Pointer to the rindex inode
587 *
588 * Returns: 0 on success, > 0 on EOF, error code otherwise
589 */
590
591static int read_rindex_entry(struct gfs2_inode *ip)
592{
593 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
594 loff_t pos = sdp->sd_rgrps * sizeof(struct gfs2_rindex);
595 struct gfs2_rindex buf;
596 int error;
597 struct gfs2_rgrpd *rgd;
598
599 if (pos >= i_size_read(&ip->i_inode))
600 return 1;
601
602 error = gfs2_internal_read(ip, (char *)&buf, &pos,
603 sizeof(struct gfs2_rindex));
604
605 if (error != sizeof(struct gfs2_rindex))
606 return (error == 0) ? 1 : error;
607
608 rgd = kmem_cache_zalloc(gfs2_rgrpd_cachep, GFP_NOFS);
609 error = -ENOMEM;
610 if (!rgd)
611 return error;
612
613 rgd->rd_sbd = sdp;
614 rgd->rd_addr = be64_to_cpu(buf.ri_addr);
615 rgd->rd_length = be32_to_cpu(buf.ri_length);
616 rgd->rd_data0 = be64_to_cpu(buf.ri_data0);
617 rgd->rd_data = be32_to_cpu(buf.ri_data);
618 rgd->rd_bitbytes = be32_to_cpu(buf.ri_bitbytes);
619
620 error = compute_bitstructs(rgd);
621 if (error)
622 goto fail;
623
624 error = gfs2_glock_get(sdp, rgd->rd_addr,
625 &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
626 if (error)
627 goto fail;
628
629 rgd->rd_gl->gl_object = rgd;
630 rgd->rd_flags &= ~GFS2_RDF_UPTODATE;
631 if (rgd->rd_data > sdp->sd_max_rg_data)
632 sdp->sd_max_rg_data = rgd->rd_data;
633 spin_lock(&sdp->sd_rindex_spin);
634 error = rgd_insert(rgd);
635 spin_unlock(&sdp->sd_rindex_spin);
636 if (!error)
637 return 0;
638
639 error = 0; /* someone else read in the rgrp; free it and ignore it */
640 gfs2_glock_put(rgd->rd_gl);
641
642fail:
643 kfree(rgd->rd_bits);
644 kmem_cache_free(gfs2_rgrpd_cachep, rgd);
645 return error;
646}
647
648/**
649 * gfs2_ri_update - Pull in a new resource index from the disk
650 * @ip: pointer to the rindex inode
651 *
652 * Returns: 0 on successful update, error code otherwise
653 */
654
655static int gfs2_ri_update(struct gfs2_inode *ip)
656{
657 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
658 int error;
659
660 do {
661 error = read_rindex_entry(ip);
662 } while (error == 0);
663
664 if (error < 0)
665 return error;
666
667 sdp->sd_rindex_uptodate = 1;
668 return 0;
669}
670
671/**
672 * gfs2_rindex_update - Update the rindex if required
673 * @sdp: The GFS2 superblock
674 *
675 * We grab a lock on the rindex inode to make sure that it doesn't
676 * change whilst we are performing an operation. We keep this lock
677 * for quite long periods of time compared to other locks. This
678 * doesn't matter, since it is shared and it is very, very rarely
679 * accessed in the exclusive mode (i.e. only when expanding the filesystem).
680 *
681 * This makes sure that we're using the latest copy of the resource index
682 * special file, which might have been updated if someone expanded the
683 * filesystem (via gfs2_grow utility), which adds new resource groups.
684 *
685 * Returns: 0 on succeess, error code otherwise
686 */
687
688int gfs2_rindex_update(struct gfs2_sbd *sdp)
689{
690 struct gfs2_inode *ip = GFS2_I(sdp->sd_rindex);
691 struct gfs2_glock *gl = ip->i_gl;
692 struct gfs2_holder ri_gh;
693 int error = 0;
694 int unlock_required = 0;
695
696 /* Read new copy from disk if we don't have the latest */
697 if (!sdp->sd_rindex_uptodate) {
698 if (!gfs2_glock_is_locked_by_me(gl)) {
699 error = gfs2_glock_nq_init(gl, LM_ST_SHARED, 0, &ri_gh);
700 if (error)
701 return error;
702 unlock_required = 1;
703 }
704 if (!sdp->sd_rindex_uptodate)
705 error = gfs2_ri_update(ip);
706 if (unlock_required)
707 gfs2_glock_dq_uninit(&ri_gh);
708 }
709
710 return error;
711}
712
713static void gfs2_rgrp_in(struct gfs2_rgrpd *rgd, const void *buf)
714{
715 const struct gfs2_rgrp *str = buf;
716 u32 rg_flags;
717
718 rg_flags = be32_to_cpu(str->rg_flags);
719 rg_flags &= ~GFS2_RDF_MASK;
720 rgd->rd_flags &= GFS2_RDF_MASK;
721 rgd->rd_flags |= rg_flags;
722 rgd->rd_free = be32_to_cpu(str->rg_free);
723 rgd->rd_dinodes = be32_to_cpu(str->rg_dinodes);
724 rgd->rd_igeneration = be64_to_cpu(str->rg_igeneration);
725}
726
727static void gfs2_rgrp_out(struct gfs2_rgrpd *rgd, void *buf)
728{
729 struct gfs2_rgrp *str = buf;
730
731 str->rg_flags = cpu_to_be32(rgd->rd_flags & ~GFS2_RDF_MASK);
732 str->rg_free = cpu_to_be32(rgd->rd_free);
733 str->rg_dinodes = cpu_to_be32(rgd->rd_dinodes);
734 str->__pad = cpu_to_be32(0);
735 str->rg_igeneration = cpu_to_be64(rgd->rd_igeneration);
736 memset(&str->rg_reserved, 0, sizeof(str->rg_reserved));
737}
738
739/**
740 * gfs2_rgrp_go_lock - Read in a RG's header and bitmaps
741 * @gh: The glock holder for the resource group
742 *
743 * Read in all of a Resource Group's header and bitmap blocks.
744 * Caller must eventually call gfs2_rgrp_relse() to free the bitmaps.
745 *
746 * Returns: errno
747 */
748
749int gfs2_rgrp_go_lock(struct gfs2_holder *gh)
750{
751 struct gfs2_rgrpd *rgd = gh->gh_gl->gl_object;
752 struct gfs2_sbd *sdp = rgd->rd_sbd;
753 struct gfs2_glock *gl = rgd->rd_gl;
754 unsigned int length = rgd->rd_length;
755 struct gfs2_bitmap *bi;
756 unsigned int x, y;
757 int error;
758
759 for (x = 0; x < length; x++) {
760 bi = rgd->rd_bits + x;
761 error = gfs2_meta_read(gl, rgd->rd_addr + x, 0, &bi->bi_bh);
762 if (error)
763 goto fail;
764 }
765
766 for (y = length; y--;) {
767 bi = rgd->rd_bits + y;
768 error = gfs2_meta_wait(sdp, bi->bi_bh);
769 if (error)
770 goto fail;
771 if (gfs2_metatype_check(sdp, bi->bi_bh, y ? GFS2_METATYPE_RB :
772 GFS2_METATYPE_RG)) {
773 error = -EIO;
774 goto fail;
775 }
776 }
777
778 if (!(rgd->rd_flags & GFS2_RDF_UPTODATE)) {
779 for (x = 0; x < length; x++)
780 clear_bit(GBF_FULL, &rgd->rd_bits[x].bi_flags);
781 gfs2_rgrp_in(rgd, (rgd->rd_bits[0].bi_bh)->b_data);
782 rgd->rd_flags |= (GFS2_RDF_UPTODATE | GFS2_RDF_CHECK);
783 rgd->rd_free_clone = rgd->rd_free;
784 }
785
786 return 0;
787
788fail:
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
796 return error;
797}
798
799/**
800 * gfs2_rgrp_go_unlock - Release RG bitmaps read in with gfs2_rgrp_bh_get()
801 * @gh: The glock holder for the resource group
802 *
803 */
804
805void gfs2_rgrp_go_unlock(struct gfs2_holder *gh)
806{
807 struct gfs2_rgrpd *rgd = gh->gh_gl->gl_object;
808 int x, length = rgd->rd_length;
809
810 for (x = 0; x < length; x++) {
811 struct gfs2_bitmap *bi = rgd->rd_bits + x;
812 brelse(bi->bi_bh);
813 bi->bi_bh = NULL;
814 }
815
816}
817
818int gfs2_rgrp_send_discards(struct gfs2_sbd *sdp, u64 offset,
819 struct buffer_head *bh,
820 const struct gfs2_bitmap *bi, unsigned minlen, u64 *ptrimmed)
821{
822 struct super_block *sb = sdp->sd_vfs;
823 struct block_device *bdev = sb->s_bdev;
824 const unsigned int sects_per_blk = sdp->sd_sb.sb_bsize /
825 bdev_logical_block_size(sb->s_bdev);
826 u64 blk;
827 sector_t start = 0;
828 sector_t nr_sects = 0;
829 int rv;
830 unsigned int x;
831 u32 trimmed = 0;
832 u8 diff;
833
834 for (x = 0; x < bi->bi_len; x++) {
835 const u8 *clone = bi->bi_clone ? bi->bi_clone : bi->bi_bh->b_data;
836 clone += bi->bi_offset;
837 clone += x;
838 if (bh) {
839 const u8 *orig = bh->b_data + bi->bi_offset + x;
840 diff = ~(*orig | (*orig >> 1)) & (*clone | (*clone >> 1));
841 } else {
842 diff = ~(*clone | (*clone >> 1));
843 }
844 diff &= 0x55;
845 if (diff == 0)
846 continue;
847 blk = offset + ((bi->bi_start + x) * GFS2_NBBY);
848 blk *= sects_per_blk; /* convert to sectors */
849 while(diff) {
850 if (diff & 1) {
851 if (nr_sects == 0)
852 goto start_new_extent;
853 if ((start + nr_sects) != blk) {
854 if (nr_sects >= minlen) {
855 rv = blkdev_issue_discard(bdev,
856 start, nr_sects,
857 GFP_NOFS, 0);
858 if (rv)
859 goto fail;
860 trimmed += nr_sects;
861 }
862 nr_sects = 0;
863start_new_extent:
864 start = blk;
865 }
866 nr_sects += sects_per_blk;
867 }
868 diff >>= 2;
869 blk += sects_per_blk;
870 }
871 }
872 if (nr_sects >= minlen) {
873 rv = blkdev_issue_discard(bdev, start, nr_sects, GFP_NOFS, 0);
874 if (rv)
875 goto fail;
876 trimmed += nr_sects;
877 }
878 if (ptrimmed)
879 *ptrimmed = trimmed;
880 return 0;
881
882fail:
883 if (sdp->sd_args.ar_discard)
884 fs_warn(sdp, "error %d on discard request, turning discards off for this filesystem", rv);
885 sdp->sd_args.ar_discard = 0;
886 return -EIO;
887}
888
889/**
890 * gfs2_fitrim - Generate discard requests for unused bits of the filesystem
891 * @filp: Any file on the filesystem
892 * @argp: Pointer to the arguments (also used to pass result)
893 *
894 * Returns: 0 on success, otherwise error code
895 */
896
897int gfs2_fitrim(struct file *filp, void __user *argp)
898{
899 struct inode *inode = filp->f_dentry->d_inode;
900 struct gfs2_sbd *sdp = GFS2_SB(inode);
901 struct request_queue *q = bdev_get_queue(sdp->sd_vfs->s_bdev);
902 struct buffer_head *bh;
903 struct gfs2_rgrpd *rgd;
904 struct gfs2_rgrpd *rgd_end;
905 struct gfs2_holder gh;
906 struct fstrim_range r;
907 int ret = 0;
908 u64 amt;
909 u64 trimmed = 0;
910 unsigned int x;
911
912 if (!capable(CAP_SYS_ADMIN))
913 return -EPERM;
914
915 if (!blk_queue_discard(q))
916 return -EOPNOTSUPP;
917
918 if (argp == NULL) {
919 r.start = 0;
920 r.len = ULLONG_MAX;
921 r.minlen = 0;
922 } else if (copy_from_user(&r, argp, sizeof(r)))
923 return -EFAULT;
924
925 ret = gfs2_rindex_update(sdp);
926 if (ret)
927 return ret;
928
929 rgd = gfs2_blk2rgrpd(sdp, r.start, 0);
930 rgd_end = gfs2_blk2rgrpd(sdp, r.start + r.len, 0);
931
932 while (1) {
933
934 ret = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_EXCLUSIVE, 0, &gh);
935 if (ret)
936 goto out;
937
938 if (!(rgd->rd_flags & GFS2_RGF_TRIMMED)) {
939 /* Trim each bitmap in the rgrp */
940 for (x = 0; x < rgd->rd_length; x++) {
941 struct gfs2_bitmap *bi = rgd->rd_bits + x;
942 ret = gfs2_rgrp_send_discards(sdp, rgd->rd_data0, NULL, bi, r.minlen, &amt);
943 if (ret) {
944 gfs2_glock_dq_uninit(&gh);
945 goto out;
946 }
947 trimmed += amt;
948 }
949
950 /* Mark rgrp as having been trimmed */
951 ret = gfs2_trans_begin(sdp, RES_RG_HDR, 0);
952 if (ret == 0) {
953 bh = rgd->rd_bits[0].bi_bh;
954 rgd->rd_flags |= GFS2_RGF_TRIMMED;
955 gfs2_trans_add_bh(rgd->rd_gl, bh, 1);
956 gfs2_rgrp_out(rgd, bh->b_data);
957 gfs2_trans_end(sdp);
958 }
959 }
960 gfs2_glock_dq_uninit(&gh);
961
962 if (rgd == rgd_end)
963 break;
964
965 rgd = gfs2_rgrpd_get_next(rgd);
966 }
967
968out:
969 r.len = trimmed << 9;
970 if (argp && copy_to_user(argp, &r, sizeof(r)))
971 return -EFAULT;
972
973 return ret;
974}
975
976/**
977 * gfs2_qadata_get - get the struct gfs2_qadata structure for an inode
978 * @ip: the incore GFS2 inode structure
979 *
980 * Returns: the struct gfs2_qadata
981 */
982
983struct gfs2_qadata *gfs2_qadata_get(struct gfs2_inode *ip)
984{
985 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
986 int error;
987 BUG_ON(ip->i_qadata != NULL);
988 ip->i_qadata = kzalloc(sizeof(struct gfs2_qadata), GFP_NOFS);
989 error = gfs2_rindex_update(sdp);
990 if (error)
991 fs_warn(sdp, "rindex update returns %d\n", error);
992 return ip->i_qadata;
993}
994
995/**
996 * gfs2_blkrsv_get - get the struct gfs2_blkreserv structure for an inode
997 * @ip: the incore GFS2 inode structure
998 *
999 * Returns: the struct gfs2_qadata
1000 */
1001
1002static int gfs2_blkrsv_get(struct gfs2_inode *ip)
1003{
1004 BUG_ON(ip->i_res != NULL);
1005 ip->i_res = kmem_cache_zalloc(gfs2_rsrv_cachep, GFP_NOFS);
1006 if (!ip->i_res)
1007 return -ENOMEM;
1008 return 0;
1009}
1010
1011/**
1012 * try_rgrp_fit - See if a given reservation will fit in a given RG
1013 * @rgd: the RG data
1014 * @ip: the inode
1015 *
1016 * If there's room for the requested blocks to be allocated from the RG:
1017 *
1018 * Returns: 1 on success (it fits), 0 on failure (it doesn't fit)
1019 */
1020
1021static int try_rgrp_fit(const struct gfs2_rgrpd *rgd, const struct gfs2_inode *ip)
1022{
1023 const struct gfs2_blkreserv *rs = ip->i_res;
1024
1025 if (rgd->rd_flags & (GFS2_RGF_NOALLOC | GFS2_RDF_ERROR))
1026 return 0;
1027 if (rgd->rd_free_clone >= rs->rs_requested)
1028 return 1;
1029 return 0;
1030}
1031
1032static inline u32 gfs2_bi2rgd_blk(struct gfs2_bitmap *bi, u32 blk)
1033{
1034 return (bi->bi_start * GFS2_NBBY) + blk;
1035}
1036
1037/**
1038 * try_rgrp_unlink - Look for any unlinked, allocated, but unused inodes
1039 * @rgd: The rgrp
1040 * @last_unlinked: block address of the last dinode we unlinked
1041 * @skip: block address we should explicitly not unlink
1042 *
1043 * Returns: 0 if no error
1044 * The inode, if one has been found, in inode.
1045 */
1046
1047static void try_rgrp_unlink(struct gfs2_rgrpd *rgd, u64 *last_unlinked, u64 skip)
1048{
1049 u32 goal = 0, block;
1050 u64 no_addr;
1051 struct gfs2_sbd *sdp = rgd->rd_sbd;
1052 struct gfs2_glock *gl;
1053 struct gfs2_inode *ip;
1054 int error;
1055 int found = 0;
1056 struct gfs2_bitmap *bi;
1057
1058 while (goal < rgd->rd_data) {
1059 down_write(&sdp->sd_log_flush_lock);
1060 block = rgblk_search(rgd, goal, GFS2_BLKST_UNLINKED, &bi);
1061 up_write(&sdp->sd_log_flush_lock);
1062 if (block == BFITNOENT)
1063 break;
1064
1065 block = gfs2_bi2rgd_blk(bi, block);
1066 /* rgblk_search can return a block < goal, so we need to
1067 keep it marching forward. */
1068 no_addr = block + rgd->rd_data0;
1069 goal = max(block + 1, goal + 1);
1070 if (*last_unlinked != NO_BLOCK && no_addr <= *last_unlinked)
1071 continue;
1072 if (no_addr == skip)
1073 continue;
1074 *last_unlinked = no_addr;
1075
1076 error = gfs2_glock_get(sdp, no_addr, &gfs2_inode_glops, CREATE, &gl);
1077 if (error)
1078 continue;
1079
1080 /* If the inode is already in cache, we can ignore it here
1081 * because the existing inode disposal code will deal with
1082 * it when all refs have gone away. Accessing gl_object like
1083 * this is not safe in general. Here it is ok because we do
1084 * not dereference the pointer, and we only need an approx
1085 * answer to whether it is NULL or not.
1086 */
1087 ip = gl->gl_object;
1088
1089 if (ip || queue_work(gfs2_delete_workqueue, &gl->gl_delete) == 0)
1090 gfs2_glock_put(gl);
1091 else
1092 found++;
1093
1094 /* Limit reclaim to sensible number of tasks */
1095 if (found > NR_CPUS)
1096 return;
1097 }
1098
1099 rgd->rd_flags &= ~GFS2_RDF_CHECK;
1100 return;
1101}
1102
1103/**
1104 * get_local_rgrp - Choose and lock a rgrp for allocation
1105 * @ip: the inode to reserve space for
1106 * @last_unlinked: the last unlinked block
1107 *
1108 * Try to acquire rgrp in way which avoids contending with others.
1109 *
1110 * Returns: errno
1111 */
1112
1113static int get_local_rgrp(struct gfs2_inode *ip, u64 *last_unlinked)
1114{
1115 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1116 struct gfs2_rgrpd *rgd, *begin = NULL;
1117 struct gfs2_blkreserv *rs = ip->i_res;
1118 int error, rg_locked, flags = LM_FLAG_TRY;
1119 int loops = 0;
1120
1121 if (ip->i_rgd && rgrp_contains_block(ip->i_rgd, ip->i_goal))
1122 rgd = begin = ip->i_rgd;
1123 else
1124 rgd = begin = gfs2_blk2rgrpd(sdp, ip->i_goal, 1);
1125
1126 if (rgd == NULL)
1127 return -EBADSLT;
1128
1129 while (loops < 3) {
1130 rg_locked = 0;
1131
1132 if (gfs2_glock_is_locked_by_me(rgd->rd_gl)) {
1133 rg_locked = 1;
1134 error = 0;
1135 } else {
1136 error = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_EXCLUSIVE,
1137 flags, &rs->rs_rgd_gh);
1138 }
1139 switch (error) {
1140 case 0:
1141 if (try_rgrp_fit(rgd, ip)) {
1142 ip->i_rgd = rgd;
1143 return 0;
1144 }
1145 if (rgd->rd_flags & GFS2_RDF_CHECK)
1146 try_rgrp_unlink(rgd, last_unlinked, ip->i_no_addr);
1147 if (!rg_locked)
1148 gfs2_glock_dq_uninit(&rs->rs_rgd_gh);
1149 /* fall through */
1150 case GLR_TRYFAILED:
1151 rgd = gfs2_rgrpd_get_next(rgd);
1152 if (rgd == begin) {
1153 flags = 0;
1154 loops++;
1155 }
1156 break;
1157 default:
1158 return error;
1159 }
1160 }
1161
1162 return -ENOSPC;
1163}
1164
1165static void gfs2_blkrsv_put(struct gfs2_inode *ip)
1166{
1167 BUG_ON(ip->i_res == NULL);
1168 kmem_cache_free(gfs2_rsrv_cachep, ip->i_res);
1169 ip->i_res = NULL;
1170}
1171
1172/**
1173 * gfs2_inplace_reserve - Reserve space in the filesystem
1174 * @ip: the inode to reserve space for
1175 * @requested: the number of blocks to be reserved
1176 *
1177 * Returns: errno
1178 */
1179
1180int gfs2_inplace_reserve(struct gfs2_inode *ip, u32 requested)
1181{
1182 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1183 struct gfs2_blkreserv *rs;
1184 int error;
1185 u64 last_unlinked = NO_BLOCK;
1186 int tries = 0;
1187
1188 error = gfs2_blkrsv_get(ip);
1189 if (error)
1190 return error;
1191
1192 rs = ip->i_res;
1193 rs->rs_requested = requested;
1194 if (gfs2_assert_warn(sdp, requested)) {
1195 error = -EINVAL;
1196 goto out;
1197 }
1198
1199 do {
1200 error = get_local_rgrp(ip, &last_unlinked);
1201 if (error != -ENOSPC)
1202 break;
1203 /* Check that fs hasn't grown if writing to rindex */
1204 if (ip == GFS2_I(sdp->sd_rindex) && !sdp->sd_rindex_uptodate) {
1205 error = gfs2_ri_update(ip);
1206 if (error)
1207 break;
1208 continue;
1209 }
1210 /* Flushing the log may release space */
1211 gfs2_log_flush(sdp, NULL);
1212 } while (tries++ < 3);
1213
1214out:
1215 if (error)
1216 gfs2_blkrsv_put(ip);
1217 return error;
1218}
1219
1220/**
1221 * gfs2_inplace_release - release an inplace reservation
1222 * @ip: the inode the reservation was taken out on
1223 *
1224 * Release a reservation made by gfs2_inplace_reserve().
1225 */
1226
1227void gfs2_inplace_release(struct gfs2_inode *ip)
1228{
1229 struct gfs2_blkreserv *rs = ip->i_res;
1230
1231 if (rs->rs_rgd_gh.gh_gl)
1232 gfs2_glock_dq_uninit(&rs->rs_rgd_gh);
1233 gfs2_blkrsv_put(ip);
1234}
1235
1236/**
1237 * gfs2_get_block_type - Check a block in a RG is of given type
1238 * @rgd: the resource group holding the block
1239 * @block: the block number
1240 *
1241 * Returns: The block type (GFS2_BLKST_*)
1242 */
1243
1244static unsigned char gfs2_get_block_type(struct gfs2_rgrpd *rgd, u64 block)
1245{
1246 struct gfs2_bitmap *bi = NULL;
1247 u32 length, rgrp_block, buf_block;
1248 unsigned int buf;
1249 unsigned char type;
1250
1251 length = rgd->rd_length;
1252 rgrp_block = block - rgd->rd_data0;
1253
1254 for (buf = 0; buf < length; buf++) {
1255 bi = rgd->rd_bits + buf;
1256 if (rgrp_block < (bi->bi_start + bi->bi_len) * GFS2_NBBY)
1257 break;
1258 }
1259
1260 gfs2_assert(rgd->rd_sbd, buf < length);
1261 buf_block = rgrp_block - bi->bi_start * GFS2_NBBY;
1262
1263 type = gfs2_testbit(rgd, bi->bi_bh->b_data + bi->bi_offset,
1264 bi->bi_len, buf_block);
1265
1266 return type;
1267}
1268
1269/**
1270 * rgblk_search - find a block in @state
1271 * @rgd: the resource group descriptor
1272 * @goal: the goal block within the RG (start here to search for avail block)
1273 * @state: GFS2_BLKST_XXX the before-allocation state to find
1274 * @rbi: address of the pointer to the bitmap containing the block found
1275 *
1276 * Walk rgrp's bitmap to find bits that represent a block in @state.
1277 *
1278 * This function never fails, because we wouldn't call it unless we
1279 * know (from reservation results, etc.) that a block is available.
1280 *
1281 * Scope of @goal is just within rgrp, not the whole filesystem.
1282 * Scope of @returned block is just within bitmap, not the whole filesystem.
1283 *
1284 * Returns: the block number found relative to the bitmap rbi
1285 */
1286
1287static u32 rgblk_search(struct gfs2_rgrpd *rgd, u32 goal, unsigned char state,
1288 struct gfs2_bitmap **rbi)
1289{
1290 struct gfs2_bitmap *bi = NULL;
1291 const u32 length = rgd->rd_length;
1292 u32 biblk = BFITNOENT;
1293 unsigned int buf, x;
1294 const u8 *buffer = NULL;
1295
1296 *rbi = NULL;
1297 /* Find bitmap block that contains bits for goal block */
1298 for (buf = 0; buf < length; buf++) {
1299 bi = rgd->rd_bits + buf;
1300 /* Convert scope of "goal" from rgrp-wide to within found bit block */
1301 if (goal < (bi->bi_start + bi->bi_len) * GFS2_NBBY) {
1302 goal -= bi->bi_start * GFS2_NBBY;
1303 goto do_search;
1304 }
1305 }
1306 buf = 0;
1307 goal = 0;
1308
1309do_search:
1310 /* Search (up to entire) bitmap in this rgrp for allocatable block.
1311 "x <= length", instead of "x < length", because we typically start
1312 the search in the middle of a bit block, but if we can't find an
1313 allocatable block anywhere else, we want to be able wrap around and
1314 search in the first part of our first-searched bit block. */
1315 for (x = 0; x <= length; x++) {
1316 bi = rgd->rd_bits + buf;
1317
1318 if (test_bit(GBF_FULL, &bi->bi_flags) &&
1319 (state == GFS2_BLKST_FREE))
1320 goto skip;
1321
1322 /* The GFS2_BLKST_UNLINKED state doesn't apply to the clone
1323 bitmaps, so we must search the originals for that. */
1324 buffer = bi->bi_bh->b_data + bi->bi_offset;
1325 WARN_ON(!buffer_uptodate(bi->bi_bh));
1326 if (state != GFS2_BLKST_UNLINKED && bi->bi_clone)
1327 buffer = bi->bi_clone + bi->bi_offset;
1328
1329 biblk = gfs2_bitfit(buffer, bi->bi_len, goal, state);
1330 if (biblk != BFITNOENT)
1331 break;
1332
1333 if ((goal == 0) && (state == GFS2_BLKST_FREE))
1334 set_bit(GBF_FULL, &bi->bi_flags);
1335
1336 /* Try next bitmap block (wrap back to rgrp header if at end) */
1337skip:
1338 buf++;
1339 buf %= length;
1340 goal = 0;
1341 }
1342
1343 if (biblk != BFITNOENT)
1344 *rbi = bi;
1345
1346 return biblk;
1347}
1348
1349/**
1350 * gfs2_alloc_extent - allocate an extent from a given bitmap
1351 * @rgd: the resource group descriptor
1352 * @bi: the bitmap within the rgrp
1353 * @blk: the block within the bitmap
1354 * @dinode: TRUE if the first block we allocate is for a dinode
1355 * @n: The extent length
1356 *
1357 * Add the found bitmap buffer to the transaction.
1358 * Set the found bits to @new_state to change block's allocation state.
1359 * Returns: starting block number of the extent (fs scope)
1360 */
1361static u64 gfs2_alloc_extent(struct gfs2_rgrpd *rgd, struct gfs2_bitmap *bi,
1362 u32 blk, bool dinode, unsigned int *n)
1363{
1364 const unsigned int elen = *n;
1365 u32 goal;
1366 const u8 *buffer = NULL;
1367
1368 *n = 0;
1369 buffer = bi->bi_bh->b_data + bi->bi_offset;
1370 gfs2_trans_add_bh(rgd->rd_gl, bi->bi_bh, 1);
1371 gfs2_setbit(rgd, bi->bi_clone, bi, blk,
1372 dinode ? GFS2_BLKST_DINODE : GFS2_BLKST_USED);
1373 (*n)++;
1374 goal = blk;
1375 while (*n < elen) {
1376 goal++;
1377 if (goal >= (bi->bi_len * GFS2_NBBY))
1378 break;
1379 if (gfs2_testbit(rgd, buffer, bi->bi_len, goal) !=
1380 GFS2_BLKST_FREE)
1381 break;
1382 gfs2_setbit(rgd, bi->bi_clone, bi, goal, GFS2_BLKST_USED);
1383 (*n)++;
1384 }
1385 blk = gfs2_bi2rgd_blk(bi, blk);
1386 rgd->rd_last_alloc = blk + *n - 1;
1387 return rgd->rd_data0 + blk;
1388}
1389
1390/**
1391 * rgblk_free - Change alloc state of given block(s)
1392 * @sdp: the filesystem
1393 * @bstart: the start of a run of blocks to free
1394 * @blen: the length of the block run (all must lie within ONE RG!)
1395 * @new_state: GFS2_BLKST_XXX the after-allocation block state
1396 *
1397 * Returns: Resource group containing the block(s)
1398 */
1399
1400static struct gfs2_rgrpd *rgblk_free(struct gfs2_sbd *sdp, u64 bstart,
1401 u32 blen, unsigned char new_state)
1402{
1403 struct gfs2_rgrpd *rgd;
1404 struct gfs2_bitmap *bi = NULL;
1405 u32 length, rgrp_blk, buf_blk;
1406 unsigned int buf;
1407
1408 rgd = gfs2_blk2rgrpd(sdp, bstart, 1);
1409 if (!rgd) {
1410 if (gfs2_consist(sdp))
1411 fs_err(sdp, "block = %llu\n", (unsigned long long)bstart);
1412 return NULL;
1413 }
1414
1415 length = rgd->rd_length;
1416
1417 rgrp_blk = bstart - rgd->rd_data0;
1418
1419 while (blen--) {
1420 for (buf = 0; buf < length; buf++) {
1421 bi = rgd->rd_bits + buf;
1422 if (rgrp_blk < (bi->bi_start + bi->bi_len) * GFS2_NBBY)
1423 break;
1424 }
1425
1426 gfs2_assert(rgd->rd_sbd, buf < length);
1427
1428 buf_blk = rgrp_blk - bi->bi_start * GFS2_NBBY;
1429 rgrp_blk++;
1430
1431 if (!bi->bi_clone) {
1432 bi->bi_clone = kmalloc(bi->bi_bh->b_size,
1433 GFP_NOFS | __GFP_NOFAIL);
1434 memcpy(bi->bi_clone + bi->bi_offset,
1435 bi->bi_bh->b_data + bi->bi_offset,
1436 bi->bi_len);
1437 }
1438 gfs2_trans_add_bh(rgd->rd_gl, bi->bi_bh, 1);
1439 gfs2_setbit(rgd, NULL, bi, buf_blk, new_state);
1440 }
1441
1442 return rgd;
1443}
1444
1445/**
1446 * gfs2_rgrp_dump - print out an rgrp
1447 * @seq: The iterator
1448 * @gl: The glock in question
1449 *
1450 */
1451
1452int gfs2_rgrp_dump(struct seq_file *seq, const struct gfs2_glock *gl)
1453{
1454 const struct gfs2_rgrpd *rgd = gl->gl_object;
1455 if (rgd == NULL)
1456 return 0;
1457 gfs2_print_dbg(seq, " R: n:%llu f:%02x b:%u/%u i:%u\n",
1458 (unsigned long long)rgd->rd_addr, rgd->rd_flags,
1459 rgd->rd_free, rgd->rd_free_clone, rgd->rd_dinodes);
1460 return 0;
1461}
1462
1463static void gfs2_rgrp_error(struct gfs2_rgrpd *rgd)
1464{
1465 struct gfs2_sbd *sdp = rgd->rd_sbd;
1466 fs_warn(sdp, "rgrp %llu has an error, marking it readonly until umount\n",
1467 (unsigned long long)rgd->rd_addr);
1468 fs_warn(sdp, "umount on all nodes and run fsck.gfs2 to fix the error\n");
1469 gfs2_rgrp_dump(NULL, rgd->rd_gl);
1470 rgd->rd_flags |= GFS2_RDF_ERROR;
1471}
1472
1473/**
1474 * gfs2_alloc_blocks - Allocate one or more blocks of data and/or a dinode
1475 * @ip: the inode to allocate the block for
1476 * @bn: Used to return the starting block number
1477 * @ndata: requested number of blocks/extent length (value/result)
1478 * @dinode: 1 if we're allocating a dinode block, else 0
1479 * @generation: the generation number of the inode
1480 *
1481 * Returns: 0 or error
1482 */
1483
1484int gfs2_alloc_blocks(struct gfs2_inode *ip, u64 *bn, unsigned int *nblocks,
1485 bool dinode, u64 *generation)
1486{
1487 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1488 struct buffer_head *dibh;
1489 struct gfs2_rgrpd *rgd;
1490 unsigned int ndata;
1491 u32 goal, blk; /* block, within the rgrp scope */
1492 u64 block; /* block, within the file system scope */
1493 int error;
1494 struct gfs2_bitmap *bi;
1495
1496 /* Only happens if there is a bug in gfs2, return something distinctive
1497 * to ensure that it is noticed.
1498 */
1499 if (ip->i_res == NULL)
1500 return -ECANCELED;
1501
1502 rgd = ip->i_rgd;
1503
1504 if (!dinode && rgrp_contains_block(rgd, ip->i_goal))
1505 goal = ip->i_goal - rgd->rd_data0;
1506 else
1507 goal = rgd->rd_last_alloc;
1508
1509 blk = rgblk_search(rgd, goal, GFS2_BLKST_FREE, &bi);
1510
1511 /* Since all blocks are reserved in advance, this shouldn't happen */
1512 if (blk == BFITNOENT)
1513 goto rgrp_error;
1514
1515 block = gfs2_alloc_extent(rgd, bi, blk, dinode, nblocks);
1516 ndata = *nblocks;
1517 if (dinode)
1518 ndata--;
1519
1520 if (!dinode) {
1521 ip->i_goal = block + ndata - 1;
1522 error = gfs2_meta_inode_buffer(ip, &dibh);
1523 if (error == 0) {
1524 struct gfs2_dinode *di =
1525 (struct gfs2_dinode *)dibh->b_data;
1526 gfs2_trans_add_bh(ip->i_gl, dibh, 1);
1527 di->di_goal_meta = di->di_goal_data =
1528 cpu_to_be64(ip->i_goal);
1529 brelse(dibh);
1530 }
1531 }
1532 if (rgd->rd_free < *nblocks)
1533 goto rgrp_error;
1534
1535 rgd->rd_free -= *nblocks;
1536 if (dinode) {
1537 rgd->rd_dinodes++;
1538 *generation = rgd->rd_igeneration++;
1539 if (*generation == 0)
1540 *generation = rgd->rd_igeneration++;
1541 }
1542
1543 gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1544 gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
1545
1546 gfs2_statfs_change(sdp, 0, -(s64)*nblocks, dinode ? 1 : 0);
1547 if (dinode)
1548 gfs2_trans_add_unrevoke(sdp, block, 1);
1549
1550 /*
1551 * This needs reviewing to see why we cannot do the quota change
1552 * at this point in the dinode case.
1553 */
1554 if (ndata)
1555 gfs2_quota_change(ip, ndata, ip->i_inode.i_uid,
1556 ip->i_inode.i_gid);
1557
1558 rgd->rd_free_clone -= *nblocks;
1559 trace_gfs2_block_alloc(ip, rgd, block, *nblocks,
1560 dinode ? GFS2_BLKST_DINODE : GFS2_BLKST_USED);
1561 *bn = block;
1562 return 0;
1563
1564rgrp_error:
1565 gfs2_rgrp_error(rgd);
1566 return -EIO;
1567}
1568
1569/**
1570 * __gfs2_free_blocks - free a contiguous run of block(s)
1571 * @ip: the inode these blocks are being freed from
1572 * @bstart: first block of a run of contiguous blocks
1573 * @blen: the length of the block run
1574 * @meta: 1 if the blocks represent metadata
1575 *
1576 */
1577
1578void __gfs2_free_blocks(struct gfs2_inode *ip, u64 bstart, u32 blen, int meta)
1579{
1580 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1581 struct gfs2_rgrpd *rgd;
1582
1583 rgd = rgblk_free(sdp, bstart, blen, GFS2_BLKST_FREE);
1584 if (!rgd)
1585 return;
1586 trace_gfs2_block_alloc(ip, rgd, bstart, blen, GFS2_BLKST_FREE);
1587 rgd->rd_free += blen;
1588 rgd->rd_flags &= ~GFS2_RGF_TRIMMED;
1589 gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1590 gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
1591
1592 /* Directories keep their data in the metadata address space */
1593 if (meta || ip->i_depth)
1594 gfs2_meta_wipe(ip, bstart, blen);
1595}
1596
1597/**
1598 * gfs2_free_meta - free a contiguous run of data block(s)
1599 * @ip: the inode these blocks are being freed from
1600 * @bstart: first block of a run of contiguous blocks
1601 * @blen: the length of the block run
1602 *
1603 */
1604
1605void gfs2_free_meta(struct gfs2_inode *ip, u64 bstart, u32 blen)
1606{
1607 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1608
1609 __gfs2_free_blocks(ip, bstart, blen, 1);
1610 gfs2_statfs_change(sdp, 0, +blen, 0);
1611 gfs2_quota_change(ip, -(s64)blen, ip->i_inode.i_uid, ip->i_inode.i_gid);
1612}
1613
1614void gfs2_unlink_di(struct inode *inode)
1615{
1616 struct gfs2_inode *ip = GFS2_I(inode);
1617 struct gfs2_sbd *sdp = GFS2_SB(inode);
1618 struct gfs2_rgrpd *rgd;
1619 u64 blkno = ip->i_no_addr;
1620
1621 rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_UNLINKED);
1622 if (!rgd)
1623 return;
1624 trace_gfs2_block_alloc(ip, rgd, blkno, 1, GFS2_BLKST_UNLINKED);
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
1629static void gfs2_free_uninit_di(struct gfs2_rgrpd *rgd, u64 blkno)
1630{
1631 struct gfs2_sbd *sdp = rgd->rd_sbd;
1632 struct gfs2_rgrpd *tmp_rgd;
1633
1634 tmp_rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_FREE);
1635 if (!tmp_rgd)
1636 return;
1637 gfs2_assert_withdraw(sdp, rgd == tmp_rgd);
1638
1639 if (!rgd->rd_dinodes)
1640 gfs2_consist_rgrpd(rgd);
1641 rgd->rd_dinodes--;
1642 rgd->rd_free++;
1643
1644 gfs2_trans_add_bh(rgd->rd_gl, rgd->rd_bits[0].bi_bh, 1);
1645 gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
1646
1647 gfs2_statfs_change(sdp, 0, +1, -1);
1648}
1649
1650
1651void gfs2_free_di(struct gfs2_rgrpd *rgd, struct gfs2_inode *ip)
1652{
1653 gfs2_free_uninit_di(rgd, ip->i_no_addr);
1654 trace_gfs2_block_alloc(ip, rgd, ip->i_no_addr, 1, GFS2_BLKST_FREE);
1655 gfs2_quota_change(ip, -1, ip->i_inode.i_uid, ip->i_inode.i_gid);
1656 gfs2_meta_wipe(ip, ip->i_no_addr, 1);
1657}
1658
1659/**
1660 * gfs2_check_blk_type - Check the type of a block
1661 * @sdp: The superblock
1662 * @no_addr: The block number to check
1663 * @type: The block type we are looking for
1664 *
1665 * Returns: 0 if the block type matches the expected type
1666 * -ESTALE if it doesn't match
1667 * or -ve errno if something went wrong while checking
1668 */
1669
1670int gfs2_check_blk_type(struct gfs2_sbd *sdp, u64 no_addr, unsigned int type)
1671{
1672 struct gfs2_rgrpd *rgd;
1673 struct gfs2_holder rgd_gh;
1674 int error = -EINVAL;
1675
1676 rgd = gfs2_blk2rgrpd(sdp, no_addr, 1);
1677 if (!rgd)
1678 goto fail;
1679
1680 error = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_SHARED, 0, &rgd_gh);
1681 if (error)
1682 goto fail;
1683
1684 if (gfs2_get_block_type(rgd, no_addr) != type)
1685 error = -ESTALE;
1686
1687 gfs2_glock_dq_uninit(&rgd_gh);
1688fail:
1689 return error;
1690}
1691
1692/**
1693 * gfs2_rlist_add - add a RG to a list of RGs
1694 * @ip: the inode
1695 * @rlist: the list of resource groups
1696 * @block: the block
1697 *
1698 * Figure out what RG a block belongs to and add that RG to the list
1699 *
1700 * FIXME: Don't use NOFAIL
1701 *
1702 */
1703
1704void gfs2_rlist_add(struct gfs2_inode *ip, struct gfs2_rgrp_list *rlist,
1705 u64 block)
1706{
1707 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1708 struct gfs2_rgrpd *rgd;
1709 struct gfs2_rgrpd **tmp;
1710 unsigned int new_space;
1711 unsigned int x;
1712
1713 if (gfs2_assert_warn(sdp, !rlist->rl_ghs))
1714 return;
1715
1716 if (ip->i_rgd && rgrp_contains_block(ip->i_rgd, block))
1717 rgd = ip->i_rgd;
1718 else
1719 rgd = gfs2_blk2rgrpd(sdp, block, 1);
1720 if (!rgd) {
1721 fs_err(sdp, "rlist_add: no rgrp for block %llu\n", (unsigned long long)block);
1722 return;
1723 }
1724 ip->i_rgd = rgd;
1725
1726 for (x = 0; x < rlist->rl_rgrps; x++)
1727 if (rlist->rl_rgd[x] == rgd)
1728 return;
1729
1730 if (rlist->rl_rgrps == rlist->rl_space) {
1731 new_space = rlist->rl_space + 10;
1732
1733 tmp = kcalloc(new_space, sizeof(struct gfs2_rgrpd *),
1734 GFP_NOFS | __GFP_NOFAIL);
1735
1736 if (rlist->rl_rgd) {
1737 memcpy(tmp, rlist->rl_rgd,
1738 rlist->rl_space * sizeof(struct gfs2_rgrpd *));
1739 kfree(rlist->rl_rgd);
1740 }
1741
1742 rlist->rl_space = new_space;
1743 rlist->rl_rgd = tmp;
1744 }
1745
1746 rlist->rl_rgd[rlist->rl_rgrps++] = rgd;
1747}
1748
1749/**
1750 * gfs2_rlist_alloc - all RGs have been added to the rlist, now allocate
1751 * and initialize an array of glock holders for them
1752 * @rlist: the list of resource groups
1753 * @state: the lock state to acquire the RG lock in
1754 *
1755 * FIXME: Don't use NOFAIL
1756 *
1757 */
1758
1759void gfs2_rlist_alloc(struct gfs2_rgrp_list *rlist, unsigned int state)
1760{
1761 unsigned int x;
1762
1763 rlist->rl_ghs = kcalloc(rlist->rl_rgrps, sizeof(struct gfs2_holder),
1764 GFP_NOFS | __GFP_NOFAIL);
1765 for (x = 0; x < rlist->rl_rgrps; x++)
1766 gfs2_holder_init(rlist->rl_rgd[x]->rd_gl,
1767 state, 0,
1768 &rlist->rl_ghs[x]);
1769}
1770
1771/**
1772 * gfs2_rlist_free - free a resource group list
1773 * @list: the list of resource groups
1774 *
1775 */
1776
1777void gfs2_rlist_free(struct gfs2_rgrp_list *rlist)
1778{
1779 unsigned int x;
1780
1781 kfree(rlist->rl_rgd);
1782
1783 if (rlist->rl_ghs) {
1784 for (x = 0; x < rlist->rl_rgrps; x++)
1785 gfs2_holder_uninit(&rlist->rl_ghs[x]);
1786 kfree(rlist->rl_ghs);
1787 }
1788}
1789
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#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
11
12#include <linux/slab.h>
13#include <linux/spinlock.h>
14#include <linux/completion.h>
15#include <linux/buffer_head.h>
16#include <linux/fs.h>
17#include <linux/gfs2_ondisk.h>
18#include <linux/prefetch.h>
19#include <linux/blkdev.h>
20#include <linux/rbtree.h>
21#include <linux/random.h>
22
23#include "gfs2.h"
24#include "incore.h"
25#include "glock.h"
26#include "glops.h"
27#include "lops.h"
28#include "meta_io.h"
29#include "quota.h"
30#include "rgrp.h"
31#include "super.h"
32#include "trans.h"
33#include "util.h"
34#include "log.h"
35#include "inode.h"
36#include "trace_gfs2.h"
37
38#define BFITNOENT ((u32)~0)
39#define NO_BLOCK ((u64)~0)
40
41#if BITS_PER_LONG == 32
42#define LBITMASK (0x55555555UL)
43#define LBITSKIP55 (0x55555555UL)
44#define LBITSKIP00 (0x00000000UL)
45#else
46#define LBITMASK (0x5555555555555555UL)
47#define LBITSKIP55 (0x5555555555555555UL)
48#define LBITSKIP00 (0x0000000000000000UL)
49#endif
50
51/*
52 * These routines are used by the resource group routines (rgrp.c)
53 * to keep track of block allocation. Each block is represented by two
54 * bits. So, each byte represents GFS2_NBBY (i.e. 4) blocks.
55 *
56 * 0 = Free
57 * 1 = Used (not metadata)
58 * 2 = Unlinked (still in use) inode
59 * 3 = Used (metadata)
60 */
61
62struct gfs2_extent {
63 struct gfs2_rbm rbm;
64 u32 len;
65};
66
67static const char valid_change[16] = {
68 /* current */
69 /* n */ 0, 1, 1, 1,
70 /* e */ 1, 0, 0, 0,
71 /* w */ 0, 0, 0, 1,
72 1, 0, 0, 0
73};
74
75static int gfs2_rbm_find(struct gfs2_rbm *rbm, u8 state, u32 *minext,
76 const struct gfs2_inode *ip, bool nowrap);
77
78
79/**
80 * gfs2_setbit - Set a bit in the bitmaps
81 * @rbm: The position of the bit to set
82 * @do_clone: Also set the clone bitmap, if it exists
83 * @new_state: the new state of the block
84 *
85 */
86
87static inline void gfs2_setbit(const struct gfs2_rbm *rbm, bool do_clone,
88 unsigned char new_state)
89{
90 unsigned char *byte1, *byte2, *end, cur_state;
91 struct gfs2_bitmap *bi = rbm_bi(rbm);
92 unsigned int buflen = bi->bi_len;
93 const unsigned int bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
94
95 byte1 = bi->bi_bh->b_data + bi->bi_offset + (rbm->offset / GFS2_NBBY);
96 end = bi->bi_bh->b_data + bi->bi_offset + buflen;
97
98 BUG_ON(byte1 >= end);
99
100 cur_state = (*byte1 >> bit) & GFS2_BIT_MASK;
101
102 if (unlikely(!valid_change[new_state * 4 + cur_state])) {
103 pr_warn("buf_blk = 0x%x old_state=%d, new_state=%d\n",
104 rbm->offset, cur_state, new_state);
105 pr_warn("rgrp=0x%llx bi_start=0x%x\n",
106 (unsigned long long)rbm->rgd->rd_addr, bi->bi_start);
107 pr_warn("bi_offset=0x%x bi_len=0x%x\n",
108 bi->bi_offset, bi->bi_len);
109 dump_stack();
110 gfs2_consist_rgrpd(rbm->rgd);
111 return;
112 }
113 *byte1 ^= (cur_state ^ new_state) << bit;
114
115 if (do_clone && bi->bi_clone) {
116 byte2 = bi->bi_clone + bi->bi_offset + (rbm->offset / GFS2_NBBY);
117 cur_state = (*byte2 >> bit) & GFS2_BIT_MASK;
118 *byte2 ^= (cur_state ^ new_state) << bit;
119 }
120}
121
122/**
123 * gfs2_testbit - test a bit in the bitmaps
124 * @rbm: The bit to test
125 *
126 * Returns: The two bit block state of the requested bit
127 */
128
129static inline u8 gfs2_testbit(const struct gfs2_rbm *rbm)
130{
131 struct gfs2_bitmap *bi = rbm_bi(rbm);
132 const u8 *buffer = bi->bi_bh->b_data + bi->bi_offset;
133 const u8 *byte;
134 unsigned int bit;
135
136 byte = buffer + (rbm->offset / GFS2_NBBY);
137 bit = (rbm->offset % GFS2_NBBY) * GFS2_BIT_SIZE;
138
139 return (*byte >> bit) & GFS2_BIT_MASK;
140}
141
142/**
143 * gfs2_bit_search
144 * @ptr: Pointer to bitmap data
145 * @mask: Mask to use (normally 0x55555.... but adjusted for search start)
146 * @state: The state we are searching for
147 *
148 * We xor the bitmap data with a patter which is the bitwise opposite
149 * of what we are looking for, this gives rise to a pattern of ones
150 * wherever there is a match. Since we have two bits per entry, we
151 * take this pattern, shift it down by one place and then and it with
152 * the original. All the even bit positions (0,2,4, etc) then represent
153 * successful matches, so we mask with 0x55555..... to remove the unwanted
154 * odd bit positions.
155 *
156 * This allows searching of a whole u64 at once (32 blocks) with a
157 * single test (on 64 bit arches).
158 */
159
160static inline u64 gfs2_bit_search(const __le64 *ptr, u64 mask, u8 state)
161{
162 u64 tmp;
163 static const u64 search[] = {
164 [0] = 0xffffffffffffffffULL,
165 [1] = 0xaaaaaaaaaaaaaaaaULL,
166 [2] = 0x5555555555555555ULL,
167 [3] = 0x0000000000000000ULL,
168 };
169 tmp = le64_to_cpu(*ptr) ^ search[state];
170 tmp &= (tmp >> 1);
171 tmp &= mask;
172 return tmp;
173}
174
175/**
176 * rs_cmp - multi-block reservation range compare
177 * @blk: absolute file system block number of the new reservation
178 * @len: number of blocks in the new reservation
179 * @rs: existing reservation to compare against
180 *
181 * returns: 1 if the block range is beyond the reach of the reservation
182 * -1 if the block range is before the start of the reservation
183 * 0 if the block range overlaps with the reservation
184 */
185static inline int rs_cmp(u64 blk, u32 len, struct gfs2_blkreserv *rs)
186{
187 u64 startblk = gfs2_rbm_to_block(&rs->rs_rbm);
188
189 if (blk >= startblk + rs->rs_free)
190 return 1;
191 if (blk + len - 1 < startblk)
192 return -1;
193 return 0;
194}
195
196/**
197 * gfs2_bitfit - Search an rgrp's bitmap buffer to find a bit-pair representing
198 * a block in a given allocation state.
199 * @buf: the buffer that holds the bitmaps
200 * @len: the length (in bytes) of the buffer
201 * @goal: start search at this block's bit-pair (within @buffer)
202 * @state: GFS2_BLKST_XXX the state of the block we're looking for.
203 *
204 * Scope of @goal and returned block number is only within this bitmap buffer,
205 * not entire rgrp or filesystem. @buffer will be offset from the actual
206 * beginning of a bitmap block buffer, skipping any header structures, but
207 * headers are always a multiple of 64 bits long so that the buffer is
208 * always aligned to a 64 bit boundary.
209 *
210 * The size of the buffer is in bytes, but is it assumed that it is
211 * always ok to read a complete multiple of 64 bits at the end
212 * of the block in case the end is no aligned to a natural boundary.
213 *
214 * Return: the block number (bitmap buffer scope) that was found
215 */
216
217static u32 gfs2_bitfit(const u8 *buf, const unsigned int len,
218 u32 goal, u8 state)
219{
220 u32 spoint = (goal << 1) & ((8*sizeof(u64)) - 1);
221 const __le64 *ptr = ((__le64 *)buf) + (goal >> 5);
222 const __le64 *end = (__le64 *)(buf + ALIGN(len, sizeof(u64)));
223 u64 tmp;
224 u64 mask = 0x5555555555555555ULL;
225 u32 bit;
226
227 /* Mask off bits we don't care about at the start of the search */
228 mask <<= spoint;
229 tmp = gfs2_bit_search(ptr, mask, state);
230 ptr++;
231 while(tmp == 0 && ptr < end) {
232 tmp = gfs2_bit_search(ptr, 0x5555555555555555ULL, state);
233 ptr++;
234 }
235 /* Mask off any bits which are more than len bytes from the start */
236 if (ptr == end && (len & (sizeof(u64) - 1)))
237 tmp &= (((u64)~0) >> (64 - 8*(len & (sizeof(u64) - 1))));
238 /* Didn't find anything, so return */
239 if (tmp == 0)
240 return BFITNOENT;
241 ptr--;
242 bit = __ffs64(tmp);
243 bit /= 2; /* two bits per entry in the bitmap */
244 return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
245}
246
247/**
248 * gfs2_rbm_from_block - Set the rbm based upon rgd and block number
249 * @rbm: The rbm with rgd already set correctly
250 * @block: The block number (filesystem relative)
251 *
252 * This sets the bi and offset members of an rbm based on a
253 * resource group and a filesystem relative block number. The
254 * resource group must be set in the rbm on entry, the bi and
255 * offset members will be set by this function.
256 *
257 * Returns: 0 on success, or an error code
258 */
259
260static int gfs2_rbm_from_block(struct gfs2_rbm *rbm, u64 block)
261{
262 u64 rblock = block - rbm->rgd->rd_data0;
263
264 if (WARN_ON_ONCE(rblock > UINT_MAX))
265 return -EINVAL;
266 if (block >= rbm->rgd->rd_data0 + rbm->rgd->rd_data)
267 return -E2BIG;
268
269 rbm->bii = 0;
270 rbm->offset = (u32)(rblock);
271 /* Check if the block is within the first block */
272 if (rbm->offset < rbm_bi(rbm)->bi_blocks)
273 return 0;
274
275 /* Adjust for the size diff between gfs2_meta_header and gfs2_rgrp */
276 rbm->offset += (sizeof(struct gfs2_rgrp) -
277 sizeof(struct gfs2_meta_header)) * GFS2_NBBY;
278 rbm->bii = rbm->offset / rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
279 rbm->offset -= rbm->bii * rbm->rgd->rd_sbd->sd_blocks_per_bitmap;
280 return 0;
281}
282
283/**
284 * gfs2_rbm_incr - increment an rbm structure
285 * @rbm: The rbm with rgd already set correctly
286 *
287 * This function takes an existing rbm structure and increments it to the next
288 * viable block offset.
289 *
290 * Returns: If incrementing the offset would cause the rbm to go past the
291 * end of the rgrp, true is returned, otherwise false.
292 *
293 */
294
295static bool gfs2_rbm_incr(struct gfs2_rbm *rbm)
296{
297 if (rbm->offset + 1 < rbm_bi(rbm)->bi_blocks) { /* in the same bitmap */
298 rbm->offset++;
299 return false;
300 }
301 if (rbm->bii == rbm->rgd->rd_length - 1) /* at the last bitmap */
302 return true;
303
304 rbm->offset = 0;
305 rbm->bii++;
306 return false;
307}
308
309/**
310 * gfs2_unaligned_extlen - Look for free blocks which are not byte aligned
311 * @rbm: Position to search (value/result)
312 * @n_unaligned: Number of unaligned blocks to check
313 * @len: Decremented for each block found (terminate on zero)
314 *
315 * Returns: true if a non-free block is encountered
316 */
317
318static bool gfs2_unaligned_extlen(struct gfs2_rbm *rbm, u32 n_unaligned, u32 *len)
319{
320 u32 n;
321 u8 res;
322
323 for (n = 0; n < n_unaligned; n++) {
324 res = gfs2_testbit(rbm);
325 if (res != GFS2_BLKST_FREE)
326 return true;
327 (*len)--;
328 if (*len == 0)
329 return true;
330 if (gfs2_rbm_incr(rbm))
331 return true;
332 }
333
334 return false;
335}
336
337/**
338 * gfs2_free_extlen - Return extent length of free blocks
339 * @rrbm: Starting position
340 * @len: Max length to check
341 *
342 * Starting at the block specified by the rbm, see how many free blocks
343 * there are, not reading more than len blocks ahead. This can be done
344 * using memchr_inv when the blocks are byte aligned, but has to be done
345 * on a block by block basis in case of unaligned blocks. Also this
346 * function can cope with bitmap boundaries (although it must stop on
347 * a resource group boundary)
348 *
349 * Returns: Number of free blocks in the extent
350 */
351
352static u32 gfs2_free_extlen(const struct gfs2_rbm *rrbm, u32 len)
353{
354 struct gfs2_rbm rbm = *rrbm;
355 u32 n_unaligned = rbm.offset & 3;
356 u32 size = len;
357 u32 bytes;
358 u32 chunk_size;
359 u8 *ptr, *start, *end;
360 u64 block;
361 struct gfs2_bitmap *bi;
362
363 if (n_unaligned &&
364 gfs2_unaligned_extlen(&rbm, 4 - n_unaligned, &len))
365 goto out;
366
367 n_unaligned = len & 3;
368 /* Start is now byte aligned */
369 while (len > 3) {
370 bi = rbm_bi(&rbm);
371 start = bi->bi_bh->b_data;
372 if (bi->bi_clone)
373 start = bi->bi_clone;
374 end = start + bi->bi_bh->b_size;
375 start += bi->bi_offset;
376 BUG_ON(rbm.offset & 3);
377 start += (rbm.offset / GFS2_NBBY);
378 bytes = min_t(u32, len / GFS2_NBBY, (end - start));
379 ptr = memchr_inv(start, 0, bytes);
380 chunk_size = ((ptr == NULL) ? bytes : (ptr - start));
381 chunk_size *= GFS2_NBBY;
382 BUG_ON(len < chunk_size);
383 len -= chunk_size;
384 block = gfs2_rbm_to_block(&rbm);
385 if (gfs2_rbm_from_block(&rbm, block + chunk_size)) {
386 n_unaligned = 0;
387 break;
388 }
389 if (ptr) {
390 n_unaligned = 3;
391 break;
392 }
393 n_unaligned = len & 3;
394 }
395
396 /* Deal with any bits left over at the end */
397 if (n_unaligned)
398 gfs2_unaligned_extlen(&rbm, n_unaligned, &len);
399out:
400 return size - len;
401}
402
403/**
404 * gfs2_bitcount - count the number of bits in a certain state
405 * @rgd: the resource group descriptor
406 * @buffer: the buffer that holds the bitmaps
407 * @buflen: the length (in bytes) of the buffer
408 * @state: the state of the block we're looking for
409 *
410 * Returns: The number of bits
411 */
412
413static u32 gfs2_bitcount(struct gfs2_rgrpd *rgd, const u8 *buffer,
414 unsigned int buflen, u8 state)
415{
416 const u8 *byte = buffer;
417 const u8 *end = buffer + buflen;
418 const u8 state1 = state << 2;
419 const u8 state2 = state << 4;
420 const u8 state3 = state << 6;
421 u32 count = 0;
422
423 for (; byte < end; byte++) {
424 if (((*byte) & 0x03) == state)
425 count++;
426 if (((*byte) & 0x0C) == state1)
427 count++;
428 if (((*byte) & 0x30) == state2)
429 count++;
430 if (((*byte) & 0xC0) == state3)
431 count++;
432 }
433
434 return count;
435}
436
437/**
438 * gfs2_rgrp_verify - Verify that a resource group is consistent
439 * @rgd: the rgrp
440 *
441 */
442
443void gfs2_rgrp_verify(struct gfs2_rgrpd *rgd)
444{
445 struct gfs2_sbd *sdp = rgd->rd_sbd;
446 struct gfs2_bitmap *bi = NULL;
447 u32 length = rgd->rd_length;
448 u32 count[4], tmp;
449 int buf, x;
450
451 memset(count, 0, 4 * sizeof(u32));
452
453 /* Count # blocks in each of 4 possible allocation states */
454 for (buf = 0; buf < length; buf++) {
455 bi = rgd->rd_bits + buf;
456 for (x = 0; x < 4; x++)
457 count[x] += gfs2_bitcount(rgd,
458 bi->bi_bh->b_data +
459 bi->bi_offset,
460 bi->bi_len, x);
461 }
462
463 if (count[0] != rgd->rd_free) {
464 if (gfs2_consist_rgrpd(rgd))
465 fs_err(sdp, "free data mismatch: %u != %u\n",
466 count[0], rgd->rd_free);
467 return;
468 }
469
470 tmp = rgd->rd_data - rgd->rd_free - rgd->rd_dinodes;
471 if (count[1] != tmp) {
472 if (gfs2_consist_rgrpd(rgd))
473 fs_err(sdp, "used data mismatch: %u != %u\n",
474 count[1], tmp);
475 return;
476 }
477
478 if (count[2] + count[3] != rgd->rd_dinodes) {
479 if (gfs2_consist_rgrpd(rgd))
480 fs_err(sdp, "used metadata mismatch: %u != %u\n",
481 count[2] + count[3], rgd->rd_dinodes);
482 return;
483 }
484}
485
486static inline int rgrp_contains_block(struct gfs2_rgrpd *rgd, u64 block)
487{
488 u64 first = rgd->rd_data0;
489 u64 last = first + rgd->rd_data;
490 return first <= block && block < last;
491}
492
493/**
494 * gfs2_blk2rgrpd - Find resource group for a given data/meta block number
495 * @sdp: The GFS2 superblock
496 * @blk: The data block number
497 * @exact: True if this needs to be an exact match
498 *
499 * Returns: The resource group, or NULL if not found
500 */
501
502struct gfs2_rgrpd *gfs2_blk2rgrpd(struct gfs2_sbd *sdp, u64 blk, bool exact)
503{
504 struct rb_node *n, *next;
505 struct gfs2_rgrpd *cur;
506
507 spin_lock(&sdp->sd_rindex_spin);
508 n = sdp->sd_rindex_tree.rb_node;
509 while (n) {
510 cur = rb_entry(n, struct gfs2_rgrpd, rd_node);
511 next = NULL;
512 if (blk < cur->rd_addr)
513 next = n->rb_left;
514 else if (blk >= cur->rd_data0 + cur->rd_data)
515 next = n->rb_right;
516 if (next == NULL) {
517 spin_unlock(&sdp->sd_rindex_spin);
518 if (exact) {
519 if (blk < cur->rd_addr)
520 return NULL;
521 if (blk >= cur->rd_data0 + cur->rd_data)
522 return NULL;
523 }
524 return cur;
525 }
526 n = next;
527 }
528 spin_unlock(&sdp->sd_rindex_spin);
529
530 return NULL;
531}
532
533/**
534 * gfs2_rgrpd_get_first - get the first Resource Group in the filesystem
535 * @sdp: The GFS2 superblock
536 *
537 * Returns: The first rgrp in the filesystem
538 */
539
540struct gfs2_rgrpd *gfs2_rgrpd_get_first(struct gfs2_sbd *sdp)
541{
542 const struct rb_node *n;
543 struct gfs2_rgrpd *rgd;
544
545 spin_lock(&sdp->sd_rindex_spin);
546 n = rb_first(&sdp->sd_rindex_tree);
547 rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
548 spin_unlock(&sdp->sd_rindex_spin);
549
550 return rgd;
551}
552
553/**
554 * gfs2_rgrpd_get_next - get the next RG
555 * @rgd: the resource group descriptor
556 *
557 * Returns: The next rgrp
558 */
559
560struct gfs2_rgrpd *gfs2_rgrpd_get_next(struct gfs2_rgrpd *rgd)
561{
562 struct gfs2_sbd *sdp = rgd->rd_sbd;
563 const struct rb_node *n;
564
565 spin_lock(&sdp->sd_rindex_spin);
566 n = rb_next(&rgd->rd_node);
567 if (n == NULL)
568 n = rb_first(&sdp->sd_rindex_tree);
569
570 if (unlikely(&rgd->rd_node == n)) {
571 spin_unlock(&sdp->sd_rindex_spin);
572 return NULL;
573 }
574 rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
575 spin_unlock(&sdp->sd_rindex_spin);
576 return rgd;
577}
578
579void check_and_update_goal(struct gfs2_inode *ip)
580{
581 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
582 if (!ip->i_goal || gfs2_blk2rgrpd(sdp, ip->i_goal, 1) == NULL)
583 ip->i_goal = ip->i_no_addr;
584}
585
586void gfs2_free_clones(struct gfs2_rgrpd *rgd)
587{
588 int x;
589
590 for (x = 0; x < rgd->rd_length; x++) {
591 struct gfs2_bitmap *bi = rgd->rd_bits + x;
592 kfree(bi->bi_clone);
593 bi->bi_clone = NULL;
594 }
595}
596
597/**
598 * gfs2_rsqa_alloc - make sure we have a reservation assigned to the inode
599 * plus a quota allocations data structure, if necessary
600 * @ip: the inode for this reservation
601 */
602int gfs2_rsqa_alloc(struct gfs2_inode *ip)
603{
604 return gfs2_qa_alloc(ip);
605}
606
607static void dump_rs(struct seq_file *seq, const struct gfs2_blkreserv *rs)
608{
609 gfs2_print_dbg(seq, " B: n:%llu s:%llu b:%u f:%u\n",
610 (unsigned long long)rs->rs_inum,
611 (unsigned long long)gfs2_rbm_to_block(&rs->rs_rbm),
612 rs->rs_rbm.offset, rs->rs_free);
613}
614
615/**
616 * __rs_deltree - remove a multi-block reservation from the rgd tree
617 * @rs: The reservation to remove
618 *
619 */
620static void __rs_deltree(struct gfs2_blkreserv *rs)
621{
622 struct gfs2_rgrpd *rgd;
623
624 if (!gfs2_rs_active(rs))
625 return;
626
627 rgd = rs->rs_rbm.rgd;
628 trace_gfs2_rs(rs, TRACE_RS_TREEDEL);
629 rb_erase(&rs->rs_node, &rgd->rd_rstree);
630 RB_CLEAR_NODE(&rs->rs_node);
631
632 if (rs->rs_free) {
633 struct gfs2_bitmap *bi = rbm_bi(&rs->rs_rbm);
634
635 /* return reserved blocks to the rgrp */
636 BUG_ON(rs->rs_rbm.rgd->rd_reserved < rs->rs_free);
637 rs->rs_rbm.rgd->rd_reserved -= rs->rs_free;
638 /* The rgrp extent failure point is likely not to increase;
639 it will only do so if the freed blocks are somehow
640 contiguous with a span of free blocks that follows. Still,
641 it will force the number to be recalculated later. */
642 rgd->rd_extfail_pt += rs->rs_free;
643 rs->rs_free = 0;
644 clear_bit(GBF_FULL, &bi->bi_flags);
645 }
646}
647
648/**
649 * gfs2_rs_deltree - remove a multi-block reservation from the rgd tree
650 * @rs: The reservation to remove
651 *
652 */
653void gfs2_rs_deltree(struct gfs2_blkreserv *rs)
654{
655 struct gfs2_rgrpd *rgd;
656
657 rgd = rs->rs_rbm.rgd;
658 if (rgd) {
659 spin_lock(&rgd->rd_rsspin);
660 __rs_deltree(rs);
661 BUG_ON(rs->rs_free);
662 spin_unlock(&rgd->rd_rsspin);
663 }
664}
665
666/**
667 * gfs2_rsqa_delete - delete a multi-block reservation and quota allocation
668 * @ip: The inode for this reservation
669 * @wcount: The inode's write count, or NULL
670 *
671 */
672void gfs2_rsqa_delete(struct gfs2_inode *ip, atomic_t *wcount)
673{
674 down_write(&ip->i_rw_mutex);
675 if ((wcount == NULL) || (atomic_read(wcount) <= 1))
676 gfs2_rs_deltree(&ip->i_res);
677 up_write(&ip->i_rw_mutex);
678 gfs2_qa_delete(ip, wcount);
679}
680
681/**
682 * return_all_reservations - return all reserved blocks back to the rgrp.
683 * @rgd: the rgrp that needs its space back
684 *
685 * We previously reserved a bunch of blocks for allocation. Now we need to
686 * give them back. This leave the reservation structures in tact, but removes
687 * all of their corresponding "no-fly zones".
688 */
689static void return_all_reservations(struct gfs2_rgrpd *rgd)
690{
691 struct rb_node *n;
692 struct gfs2_blkreserv *rs;
693
694 spin_lock(&rgd->rd_rsspin);
695 while ((n = rb_first(&rgd->rd_rstree))) {
696 rs = rb_entry(n, struct gfs2_blkreserv, rs_node);
697 __rs_deltree(rs);
698 }
699 spin_unlock(&rgd->rd_rsspin);
700}
701
702void gfs2_clear_rgrpd(struct gfs2_sbd *sdp)
703{
704 struct rb_node *n;
705 struct gfs2_rgrpd *rgd;
706 struct gfs2_glock *gl;
707
708 while ((n = rb_first(&sdp->sd_rindex_tree))) {
709 rgd = rb_entry(n, struct gfs2_rgrpd, rd_node);
710 gl = rgd->rd_gl;
711
712 rb_erase(n, &sdp->sd_rindex_tree);
713
714 if (gl) {
715 spin_lock(&gl->gl_lockref.lock);
716 gl->gl_object = NULL;
717 spin_unlock(&gl->gl_lockref.lock);
718 gfs2_glock_add_to_lru(gl);
719 gfs2_glock_put(gl);
720 }
721
722 gfs2_free_clones(rgd);
723 kfree(rgd->rd_bits);
724 rgd->rd_bits = NULL;
725 return_all_reservations(rgd);
726 kmem_cache_free(gfs2_rgrpd_cachep, rgd);
727 }
728}
729
730static void gfs2_rindex_print(const struct gfs2_rgrpd *rgd)
731{
732 pr_info("ri_addr = %llu\n", (unsigned long long)rgd->rd_addr);
733 pr_info("ri_length = %u\n", rgd->rd_length);
734 pr_info("ri_data0 = %llu\n", (unsigned long long)rgd->rd_data0);
735 pr_info("ri_data = %u\n", rgd->rd_data);
736 pr_info("ri_bitbytes = %u\n", rgd->rd_bitbytes);
737}
738
739/**
740 * gfs2_compute_bitstructs - Compute the bitmap sizes
741 * @rgd: The resource group descriptor
742 *
743 * Calculates bitmap descriptors, one for each block that contains bitmap data
744 *
745 * Returns: errno
746 */
747
748static int compute_bitstructs(struct gfs2_rgrpd *rgd)
749{
750 struct gfs2_sbd *sdp = rgd->rd_sbd;
751 struct gfs2_bitmap *bi;
752 u32 length = rgd->rd_length; /* # blocks in hdr & bitmap */
753 u32 bytes_left, bytes;
754 int x;
755
756 if (!length)
757 return -EINVAL;
758
759 rgd->rd_bits = kcalloc(length, sizeof(struct gfs2_bitmap), GFP_NOFS);
760 if (!rgd->rd_bits)
761 return -ENOMEM;
762
763 bytes_left = rgd->rd_bitbytes;
764
765 for (x = 0; x < length; x++) {
766 bi = rgd->rd_bits + x;
767
768 bi->bi_flags = 0;
769 /* small rgrp; bitmap stored completely in header block */
770 if (length == 1) {
771 bytes = bytes_left;
772 bi->bi_offset = sizeof(struct gfs2_rgrp);
773 bi->bi_start = 0;
774 bi->bi_len = bytes;
775 bi->bi_blocks = bytes * GFS2_NBBY;
776 /* header block */
777 } else if (x == 0) {
778 bytes = sdp->sd_sb.sb_bsize - sizeof(struct gfs2_rgrp);
779 bi->bi_offset = sizeof(struct gfs2_rgrp);
780 bi->bi_start = 0;
781 bi->bi_len = bytes;
782 bi->bi_blocks = bytes * GFS2_NBBY;
783 /* last block */
784 } else if (x + 1 == length) {
785 bytes = bytes_left;
786 bi->bi_offset = sizeof(struct gfs2_meta_header);
787 bi->bi_start = rgd->rd_bitbytes - bytes_left;
788 bi->bi_len = bytes;
789 bi->bi_blocks = bytes * GFS2_NBBY;
790 /* other blocks */
791 } else {
792 bytes = sdp->sd_sb.sb_bsize -
793 sizeof(struct gfs2_meta_header);
794 bi->bi_offset = sizeof(struct gfs2_meta_header);
795 bi->bi_start = rgd->rd_bitbytes - bytes_left;
796 bi->bi_len = bytes;
797 bi->bi_blocks = bytes * GFS2_NBBY;
798 }
799
800 bytes_left -= bytes;
801 }
802
803 if (bytes_left) {
804 gfs2_consist_rgrpd(rgd);
805 return -EIO;
806 }
807 bi = rgd->rd_bits + (length - 1);
808 if ((bi->bi_start + bi->bi_len) * GFS2_NBBY != rgd->rd_data) {
809 if (gfs2_consist_rgrpd(rgd)) {
810 gfs2_rindex_print(rgd);
811 fs_err(sdp, "start=%u len=%u offset=%u\n",
812 bi->bi_start, bi->bi_len, bi->bi_offset);
813 }
814 return -EIO;
815 }
816
817 return 0;
818}
819
820/**
821 * gfs2_ri_total - Total up the file system space, according to the rindex.
822 * @sdp: the filesystem
823 *
824 */
825u64 gfs2_ri_total(struct gfs2_sbd *sdp)
826{
827 u64 total_data = 0;
828 struct inode *inode = sdp->sd_rindex;
829 struct gfs2_inode *ip = GFS2_I(inode);
830 char buf[sizeof(struct gfs2_rindex)];
831 int error, rgrps;
832
833 for (rgrps = 0;; rgrps++) {
834 loff_t pos = rgrps * sizeof(struct gfs2_rindex);
835
836 if (pos + sizeof(struct gfs2_rindex) > i_size_read(inode))
837 break;
838 error = gfs2_internal_read(ip, buf, &pos,
839 sizeof(struct gfs2_rindex));
840 if (error != sizeof(struct gfs2_rindex))
841 break;
842 total_data += be32_to_cpu(((struct gfs2_rindex *)buf)->ri_data);
843 }
844 return total_data;
845}
846
847static int rgd_insert(struct gfs2_rgrpd *rgd)
848{
849 struct gfs2_sbd *sdp = rgd->rd_sbd;
850 struct rb_node **newn = &sdp->sd_rindex_tree.rb_node, *parent = NULL;
851
852 /* Figure out where to put new node */
853 while (*newn) {
854 struct gfs2_rgrpd *cur = rb_entry(*newn, struct gfs2_rgrpd,
855 rd_node);
856
857 parent = *newn;
858 if (rgd->rd_addr < cur->rd_addr)
859 newn = &((*newn)->rb_left);
860 else if (rgd->rd_addr > cur->rd_addr)
861 newn = &((*newn)->rb_right);
862 else
863 return -EEXIST;
864 }
865
866 rb_link_node(&rgd->rd_node, parent, newn);
867 rb_insert_color(&rgd->rd_node, &sdp->sd_rindex_tree);
868 sdp->sd_rgrps++;
869 return 0;
870}
871
872/**
873 * read_rindex_entry - Pull in a new resource index entry from the disk
874 * @ip: Pointer to the rindex inode
875 *
876 * Returns: 0 on success, > 0 on EOF, error code otherwise
877 */
878
879static int read_rindex_entry(struct gfs2_inode *ip)
880{
881 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
882 const unsigned bsize = sdp->sd_sb.sb_bsize;
883 loff_t pos = sdp->sd_rgrps * sizeof(struct gfs2_rindex);
884 struct gfs2_rindex buf;
885 int error;
886 struct gfs2_rgrpd *rgd;
887
888 if (pos >= i_size_read(&ip->i_inode))
889 return 1;
890
891 error = gfs2_internal_read(ip, (char *)&buf, &pos,
892 sizeof(struct gfs2_rindex));
893
894 if (error != sizeof(struct gfs2_rindex))
895 return (error == 0) ? 1 : error;
896
897 rgd = kmem_cache_zalloc(gfs2_rgrpd_cachep, GFP_NOFS);
898 error = -ENOMEM;
899 if (!rgd)
900 return error;
901
902 rgd->rd_sbd = sdp;
903 rgd->rd_addr = be64_to_cpu(buf.ri_addr);
904 rgd->rd_length = be32_to_cpu(buf.ri_length);
905 rgd->rd_data0 = be64_to_cpu(buf.ri_data0);
906 rgd->rd_data = be32_to_cpu(buf.ri_data);
907 rgd->rd_bitbytes = be32_to_cpu(buf.ri_bitbytes);
908 spin_lock_init(&rgd->rd_rsspin);
909
910 error = compute_bitstructs(rgd);
911 if (error)
912 goto fail;
913
914 error = gfs2_glock_get(sdp, rgd->rd_addr,
915 &gfs2_rgrp_glops, CREATE, &rgd->rd_gl);
916 if (error)
917 goto fail;
918
919 rgd->rd_rgl = (struct gfs2_rgrp_lvb *)rgd->rd_gl->gl_lksb.sb_lvbptr;
920 rgd->rd_flags &= ~(GFS2_RDF_UPTODATE | GFS2_RDF_PREFERRED);
921 if (rgd->rd_data > sdp->sd_max_rg_data)
922 sdp->sd_max_rg_data = rgd->rd_data;
923 spin_lock(&sdp->sd_rindex_spin);
924 error = rgd_insert(rgd);
925 spin_unlock(&sdp->sd_rindex_spin);
926 if (!error) {
927 rgd->rd_gl->gl_object = rgd;
928 rgd->rd_gl->gl_vm.start = (rgd->rd_addr * bsize) & PAGE_MASK;
929 rgd->rd_gl->gl_vm.end = PAGE_ALIGN((rgd->rd_addr +
930 rgd->rd_length) * bsize) - 1;
931 return 0;
932 }
933
934 error = 0; /* someone else read in the rgrp; free it and ignore it */
935 gfs2_glock_put(rgd->rd_gl);
936
937fail:
938 kfree(rgd->rd_bits);
939 rgd->rd_bits = NULL;
940 kmem_cache_free(gfs2_rgrpd_cachep, rgd);
941 return error;
942}
943
944/**
945 * set_rgrp_preferences - Run all the rgrps, selecting some we prefer to use
946 * @sdp: the GFS2 superblock
947 *
948 * The purpose of this function is to select a subset of the resource groups
949 * and mark them as PREFERRED. We do it in such a way that each node prefers
950 * to use a unique set of rgrps to minimize glock contention.
951 */
952static void set_rgrp_preferences(struct gfs2_sbd *sdp)
953{
954 struct gfs2_rgrpd *rgd, *first;
955 int i;
956
957 /* Skip an initial number of rgrps, based on this node's journal ID.
958 That should start each node out on its own set. */
959 rgd = gfs2_rgrpd_get_first(sdp);
960 for (i = 0; i < sdp->sd_lockstruct.ls_jid; i++)
961 rgd = gfs2_rgrpd_get_next(rgd);
962 first = rgd;
963
964 do {
965 rgd->rd_flags |= GFS2_RDF_PREFERRED;
966 for (i = 0; i < sdp->sd_journals; i++) {
967 rgd = gfs2_rgrpd_get_next(rgd);
968 if (!rgd || rgd == first)
969 break;
970 }
971 } while (rgd && rgd != first);
972}
973
974/**
975 * gfs2_ri_update - Pull in a new resource index from the disk
976 * @ip: pointer to the rindex inode
977 *
978 * Returns: 0 on successful update, error code otherwise
979 */
980
981static int gfs2_ri_update(struct gfs2_inode *ip)
982{
983 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
984 int error;
985
986 do {
987 error = read_rindex_entry(ip);
988 } while (error == 0);
989
990 if (error < 0)
991 return error;
992
993 set_rgrp_preferences(sdp);
994
995 sdp->sd_rindex_uptodate = 1;
996 return 0;
997}
998
999/**
1000 * gfs2_rindex_update - Update the rindex if required
1001 * @sdp: The GFS2 superblock
1002 *
1003 * We grab a lock on the rindex inode to make sure that it doesn't
1004 * change whilst we are performing an operation. We keep this lock
1005 * for quite long periods of time compared to other locks. This
1006 * doesn't matter, since it is shared and it is very, very rarely
1007 * accessed in the exclusive mode (i.e. only when expanding the filesystem).
1008 *
1009 * This makes sure that we're using the latest copy of the resource index
1010 * special file, which might have been updated if someone expanded the
1011 * filesystem (via gfs2_grow utility), which adds new resource groups.
1012 *
1013 * Returns: 0 on succeess, error code otherwise
1014 */
1015
1016int gfs2_rindex_update(struct gfs2_sbd *sdp)
1017{
1018 struct gfs2_inode *ip = GFS2_I(sdp->sd_rindex);
1019 struct gfs2_glock *gl = ip->i_gl;
1020 struct gfs2_holder ri_gh;
1021 int error = 0;
1022 int unlock_required = 0;
1023
1024 /* Read new copy from disk if we don't have the latest */
1025 if (!sdp->sd_rindex_uptodate) {
1026 if (!gfs2_glock_is_locked_by_me(gl)) {
1027 error = gfs2_glock_nq_init(gl, LM_ST_SHARED, 0, &ri_gh);
1028 if (error)
1029 return error;
1030 unlock_required = 1;
1031 }
1032 if (!sdp->sd_rindex_uptodate)
1033 error = gfs2_ri_update(ip);
1034 if (unlock_required)
1035 gfs2_glock_dq_uninit(&ri_gh);
1036 }
1037
1038 return error;
1039}
1040
1041static void gfs2_rgrp_in(struct gfs2_rgrpd *rgd, const void *buf)
1042{
1043 const struct gfs2_rgrp *str = buf;
1044 u32 rg_flags;
1045
1046 rg_flags = be32_to_cpu(str->rg_flags);
1047 rg_flags &= ~GFS2_RDF_MASK;
1048 rgd->rd_flags &= GFS2_RDF_MASK;
1049 rgd->rd_flags |= rg_flags;
1050 rgd->rd_free = be32_to_cpu(str->rg_free);
1051 rgd->rd_dinodes = be32_to_cpu(str->rg_dinodes);
1052 rgd->rd_igeneration = be64_to_cpu(str->rg_igeneration);
1053}
1054
1055static void gfs2_rgrp_out(struct gfs2_rgrpd *rgd, void *buf)
1056{
1057 struct gfs2_rgrp *str = buf;
1058
1059 str->rg_flags = cpu_to_be32(rgd->rd_flags & ~GFS2_RDF_MASK);
1060 str->rg_free = cpu_to_be32(rgd->rd_free);
1061 str->rg_dinodes = cpu_to_be32(rgd->rd_dinodes);
1062 str->__pad = cpu_to_be32(0);
1063 str->rg_igeneration = cpu_to_be64(rgd->rd_igeneration);
1064 memset(&str->rg_reserved, 0, sizeof(str->rg_reserved));
1065}
1066
1067static int gfs2_rgrp_lvb_valid(struct gfs2_rgrpd *rgd)
1068{
1069 struct gfs2_rgrp_lvb *rgl = rgd->rd_rgl;
1070 struct gfs2_rgrp *str = (struct gfs2_rgrp *)rgd->rd_bits[0].bi_bh->b_data;
1071
1072 if (rgl->rl_flags != str->rg_flags || rgl->rl_free != str->rg_free ||
1073 rgl->rl_dinodes != str->rg_dinodes ||
1074 rgl->rl_igeneration != str->rg_igeneration)
1075 return 0;
1076 return 1;
1077}
1078
1079static void gfs2_rgrp_ondisk2lvb(struct gfs2_rgrp_lvb *rgl, const void *buf)
1080{
1081 const struct gfs2_rgrp *str = buf;
1082
1083 rgl->rl_magic = cpu_to_be32(GFS2_MAGIC);
1084 rgl->rl_flags = str->rg_flags;
1085 rgl->rl_free = str->rg_free;
1086 rgl->rl_dinodes = str->rg_dinodes;
1087 rgl->rl_igeneration = str->rg_igeneration;
1088 rgl->__pad = 0UL;
1089}
1090
1091static void update_rgrp_lvb_unlinked(struct gfs2_rgrpd *rgd, u32 change)
1092{
1093 struct gfs2_rgrp_lvb *rgl = rgd->rd_rgl;
1094 u32 unlinked = be32_to_cpu(rgl->rl_unlinked) + change;
1095 rgl->rl_unlinked = cpu_to_be32(unlinked);
1096}
1097
1098static u32 count_unlinked(struct gfs2_rgrpd *rgd)
1099{
1100 struct gfs2_bitmap *bi;
1101 const u32 length = rgd->rd_length;
1102 const u8 *buffer = NULL;
1103 u32 i, goal, count = 0;
1104
1105 for (i = 0, bi = rgd->rd_bits; i < length; i++, bi++) {
1106 goal = 0;
1107 buffer = bi->bi_bh->b_data + bi->bi_offset;
1108 WARN_ON(!buffer_uptodate(bi->bi_bh));
1109 while (goal < bi->bi_len * GFS2_NBBY) {
1110 goal = gfs2_bitfit(buffer, bi->bi_len, goal,
1111 GFS2_BLKST_UNLINKED);
1112 if (goal == BFITNOENT)
1113 break;
1114 count++;
1115 goal++;
1116 }
1117 }
1118
1119 return count;
1120}
1121
1122
1123/**
1124 * gfs2_rgrp_bh_get - Read in a RG's header and bitmaps
1125 * @rgd: the struct gfs2_rgrpd describing the RG to read in
1126 *
1127 * Read in all of a Resource Group's header and bitmap blocks.
1128 * Caller must eventually call gfs2_rgrp_relse() to free the bitmaps.
1129 *
1130 * Returns: errno
1131 */
1132
1133static int gfs2_rgrp_bh_get(struct gfs2_rgrpd *rgd)
1134{
1135 struct gfs2_sbd *sdp = rgd->rd_sbd;
1136 struct gfs2_glock *gl = rgd->rd_gl;
1137 unsigned int length = rgd->rd_length;
1138 struct gfs2_bitmap *bi;
1139 unsigned int x, y;
1140 int error;
1141
1142 if (rgd->rd_bits[0].bi_bh != NULL)
1143 return 0;
1144
1145 for (x = 0; x < length; x++) {
1146 bi = rgd->rd_bits + x;
1147 error = gfs2_meta_read(gl, rgd->rd_addr + x, 0, 0, &bi->bi_bh);
1148 if (error)
1149 goto fail;
1150 }
1151
1152 for (y = length; y--;) {
1153 bi = rgd->rd_bits + y;
1154 error = gfs2_meta_wait(sdp, bi->bi_bh);
1155 if (error)
1156 goto fail;
1157 if (gfs2_metatype_check(sdp, bi->bi_bh, y ? GFS2_METATYPE_RB :
1158 GFS2_METATYPE_RG)) {
1159 error = -EIO;
1160 goto fail;
1161 }
1162 }
1163
1164 if (!(rgd->rd_flags & GFS2_RDF_UPTODATE)) {
1165 for (x = 0; x < length; x++)
1166 clear_bit(GBF_FULL, &rgd->rd_bits[x].bi_flags);
1167 gfs2_rgrp_in(rgd, (rgd->rd_bits[0].bi_bh)->b_data);
1168 rgd->rd_flags |= (GFS2_RDF_UPTODATE | GFS2_RDF_CHECK);
1169 rgd->rd_free_clone = rgd->rd_free;
1170 /* max out the rgrp allocation failure point */
1171 rgd->rd_extfail_pt = rgd->rd_free;
1172 }
1173 if (cpu_to_be32(GFS2_MAGIC) != rgd->rd_rgl->rl_magic) {
1174 rgd->rd_rgl->rl_unlinked = cpu_to_be32(count_unlinked(rgd));
1175 gfs2_rgrp_ondisk2lvb(rgd->rd_rgl,
1176 rgd->rd_bits[0].bi_bh->b_data);
1177 }
1178 else if (sdp->sd_args.ar_rgrplvb) {
1179 if (!gfs2_rgrp_lvb_valid(rgd)){
1180 gfs2_consist_rgrpd(rgd);
1181 error = -EIO;
1182 goto fail;
1183 }
1184 if (rgd->rd_rgl->rl_unlinked == 0)
1185 rgd->rd_flags &= ~GFS2_RDF_CHECK;
1186 }
1187 return 0;
1188
1189fail:
1190 while (x--) {
1191 bi = rgd->rd_bits + x;
1192 brelse(bi->bi_bh);
1193 bi->bi_bh = NULL;
1194 gfs2_assert_warn(sdp, !bi->bi_clone);
1195 }
1196
1197 return error;
1198}
1199
1200static int update_rgrp_lvb(struct gfs2_rgrpd *rgd)
1201{
1202 u32 rl_flags;
1203
1204 if (rgd->rd_flags & GFS2_RDF_UPTODATE)
1205 return 0;
1206
1207 if (cpu_to_be32(GFS2_MAGIC) != rgd->rd_rgl->rl_magic)
1208 return gfs2_rgrp_bh_get(rgd);
1209
1210 rl_flags = be32_to_cpu(rgd->rd_rgl->rl_flags);
1211 rl_flags &= ~GFS2_RDF_MASK;
1212 rgd->rd_flags &= GFS2_RDF_MASK;
1213 rgd->rd_flags |= (rl_flags | GFS2_RDF_UPTODATE | GFS2_RDF_CHECK);
1214 if (rgd->rd_rgl->rl_unlinked == 0)
1215 rgd->rd_flags &= ~GFS2_RDF_CHECK;
1216 rgd->rd_free = be32_to_cpu(rgd->rd_rgl->rl_free);
1217 rgd->rd_free_clone = rgd->rd_free;
1218 rgd->rd_dinodes = be32_to_cpu(rgd->rd_rgl->rl_dinodes);
1219 rgd->rd_igeneration = be64_to_cpu(rgd->rd_rgl->rl_igeneration);
1220 return 0;
1221}
1222
1223int gfs2_rgrp_go_lock(struct gfs2_holder *gh)
1224{
1225 struct gfs2_rgrpd *rgd = gh->gh_gl->gl_object;
1226 struct gfs2_sbd *sdp = rgd->rd_sbd;
1227
1228 if (gh->gh_flags & GL_SKIP && sdp->sd_args.ar_rgrplvb)
1229 return 0;
1230 return gfs2_rgrp_bh_get(rgd);
1231}
1232
1233/**
1234 * gfs2_rgrp_brelse - Release RG bitmaps read in with gfs2_rgrp_bh_get()
1235 * @rgd: The resource group
1236 *
1237 */
1238
1239void gfs2_rgrp_brelse(struct gfs2_rgrpd *rgd)
1240{
1241 int x, length = rgd->rd_length;
1242
1243 for (x = 0; x < length; x++) {
1244 struct gfs2_bitmap *bi = rgd->rd_bits + x;
1245 if (bi->bi_bh) {
1246 brelse(bi->bi_bh);
1247 bi->bi_bh = NULL;
1248 }
1249 }
1250
1251}
1252
1253/**
1254 * gfs2_rgrp_go_unlock - Unlock a rgrp glock
1255 * @gh: The glock holder for the resource group
1256 *
1257 */
1258
1259void gfs2_rgrp_go_unlock(struct gfs2_holder *gh)
1260{
1261 struct gfs2_rgrpd *rgd = gh->gh_gl->gl_object;
1262 int demote_requested = test_bit(GLF_DEMOTE, &gh->gh_gl->gl_flags) |
1263 test_bit(GLF_PENDING_DEMOTE, &gh->gh_gl->gl_flags);
1264
1265 if (rgd && demote_requested)
1266 gfs2_rgrp_brelse(rgd);
1267}
1268
1269int gfs2_rgrp_send_discards(struct gfs2_sbd *sdp, u64 offset,
1270 struct buffer_head *bh,
1271 const struct gfs2_bitmap *bi, unsigned minlen, u64 *ptrimmed)
1272{
1273 struct super_block *sb = sdp->sd_vfs;
1274 u64 blk;
1275 sector_t start = 0;
1276 sector_t nr_blks = 0;
1277 int rv;
1278 unsigned int x;
1279 u32 trimmed = 0;
1280 u8 diff;
1281
1282 for (x = 0; x < bi->bi_len; x++) {
1283 const u8 *clone = bi->bi_clone ? bi->bi_clone : bi->bi_bh->b_data;
1284 clone += bi->bi_offset;
1285 clone += x;
1286 if (bh) {
1287 const u8 *orig = bh->b_data + bi->bi_offset + x;
1288 diff = ~(*orig | (*orig >> 1)) & (*clone | (*clone >> 1));
1289 } else {
1290 diff = ~(*clone | (*clone >> 1));
1291 }
1292 diff &= 0x55;
1293 if (diff == 0)
1294 continue;
1295 blk = offset + ((bi->bi_start + x) * GFS2_NBBY);
1296 while(diff) {
1297 if (diff & 1) {
1298 if (nr_blks == 0)
1299 goto start_new_extent;
1300 if ((start + nr_blks) != blk) {
1301 if (nr_blks >= minlen) {
1302 rv = sb_issue_discard(sb,
1303 start, nr_blks,
1304 GFP_NOFS, 0);
1305 if (rv)
1306 goto fail;
1307 trimmed += nr_blks;
1308 }
1309 nr_blks = 0;
1310start_new_extent:
1311 start = blk;
1312 }
1313 nr_blks++;
1314 }
1315 diff >>= 2;
1316 blk++;
1317 }
1318 }
1319 if (nr_blks >= minlen) {
1320 rv = sb_issue_discard(sb, start, nr_blks, GFP_NOFS, 0);
1321 if (rv)
1322 goto fail;
1323 trimmed += nr_blks;
1324 }
1325 if (ptrimmed)
1326 *ptrimmed = trimmed;
1327 return 0;
1328
1329fail:
1330 if (sdp->sd_args.ar_discard)
1331 fs_warn(sdp, "error %d on discard request, turning discards off for this filesystem", rv);
1332 sdp->sd_args.ar_discard = 0;
1333 return -EIO;
1334}
1335
1336/**
1337 * gfs2_fitrim - Generate discard requests for unused bits of the filesystem
1338 * @filp: Any file on the filesystem
1339 * @argp: Pointer to the arguments (also used to pass result)
1340 *
1341 * Returns: 0 on success, otherwise error code
1342 */
1343
1344int gfs2_fitrim(struct file *filp, void __user *argp)
1345{
1346 struct inode *inode = file_inode(filp);
1347 struct gfs2_sbd *sdp = GFS2_SB(inode);
1348 struct request_queue *q = bdev_get_queue(sdp->sd_vfs->s_bdev);
1349 struct buffer_head *bh;
1350 struct gfs2_rgrpd *rgd;
1351 struct gfs2_rgrpd *rgd_end;
1352 struct gfs2_holder gh;
1353 struct fstrim_range r;
1354 int ret = 0;
1355 u64 amt;
1356 u64 trimmed = 0;
1357 u64 start, end, minlen;
1358 unsigned int x;
1359 unsigned bs_shift = sdp->sd_sb.sb_bsize_shift;
1360
1361 if (!capable(CAP_SYS_ADMIN))
1362 return -EPERM;
1363
1364 if (!blk_queue_discard(q))
1365 return -EOPNOTSUPP;
1366
1367 if (copy_from_user(&r, argp, sizeof(r)))
1368 return -EFAULT;
1369
1370 ret = gfs2_rindex_update(sdp);
1371 if (ret)
1372 return ret;
1373
1374 start = r.start >> bs_shift;
1375 end = start + (r.len >> bs_shift);
1376 minlen = max_t(u64, r.minlen,
1377 q->limits.discard_granularity) >> bs_shift;
1378
1379 if (end <= start || minlen > sdp->sd_max_rg_data)
1380 return -EINVAL;
1381
1382 rgd = gfs2_blk2rgrpd(sdp, start, 0);
1383 rgd_end = gfs2_blk2rgrpd(sdp, end, 0);
1384
1385 if ((gfs2_rgrpd_get_first(sdp) == gfs2_rgrpd_get_next(rgd_end))
1386 && (start > rgd_end->rd_data0 + rgd_end->rd_data))
1387 return -EINVAL; /* start is beyond the end of the fs */
1388
1389 while (1) {
1390
1391 ret = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_EXCLUSIVE, 0, &gh);
1392 if (ret)
1393 goto out;
1394
1395 if (!(rgd->rd_flags & GFS2_RGF_TRIMMED)) {
1396 /* Trim each bitmap in the rgrp */
1397 for (x = 0; x < rgd->rd_length; x++) {
1398 struct gfs2_bitmap *bi = rgd->rd_bits + x;
1399 ret = gfs2_rgrp_send_discards(sdp,
1400 rgd->rd_data0, NULL, bi, minlen,
1401 &amt);
1402 if (ret) {
1403 gfs2_glock_dq_uninit(&gh);
1404 goto out;
1405 }
1406 trimmed += amt;
1407 }
1408
1409 /* Mark rgrp as having been trimmed */
1410 ret = gfs2_trans_begin(sdp, RES_RG_HDR, 0);
1411 if (ret == 0) {
1412 bh = rgd->rd_bits[0].bi_bh;
1413 rgd->rd_flags |= GFS2_RGF_TRIMMED;
1414 gfs2_trans_add_meta(rgd->rd_gl, bh);
1415 gfs2_rgrp_out(rgd, bh->b_data);
1416 gfs2_rgrp_ondisk2lvb(rgd->rd_rgl, bh->b_data);
1417 gfs2_trans_end(sdp);
1418 }
1419 }
1420 gfs2_glock_dq_uninit(&gh);
1421
1422 if (rgd == rgd_end)
1423 break;
1424
1425 rgd = gfs2_rgrpd_get_next(rgd);
1426 }
1427
1428out:
1429 r.len = trimmed << bs_shift;
1430 if (copy_to_user(argp, &r, sizeof(r)))
1431 return -EFAULT;
1432
1433 return ret;
1434}
1435
1436/**
1437 * rs_insert - insert a new multi-block reservation into the rgrp's rb_tree
1438 * @ip: the inode structure
1439 *
1440 */
1441static void rs_insert(struct gfs2_inode *ip)
1442{
1443 struct rb_node **newn, *parent = NULL;
1444 int rc;
1445 struct gfs2_blkreserv *rs = &ip->i_res;
1446 struct gfs2_rgrpd *rgd = rs->rs_rbm.rgd;
1447 u64 fsblock = gfs2_rbm_to_block(&rs->rs_rbm);
1448
1449 BUG_ON(gfs2_rs_active(rs));
1450
1451 spin_lock(&rgd->rd_rsspin);
1452 newn = &rgd->rd_rstree.rb_node;
1453 while (*newn) {
1454 struct gfs2_blkreserv *cur =
1455 rb_entry(*newn, struct gfs2_blkreserv, rs_node);
1456
1457 parent = *newn;
1458 rc = rs_cmp(fsblock, rs->rs_free, cur);
1459 if (rc > 0)
1460 newn = &((*newn)->rb_right);
1461 else if (rc < 0)
1462 newn = &((*newn)->rb_left);
1463 else {
1464 spin_unlock(&rgd->rd_rsspin);
1465 WARN_ON(1);
1466 return;
1467 }
1468 }
1469
1470 rb_link_node(&rs->rs_node, parent, newn);
1471 rb_insert_color(&rs->rs_node, &rgd->rd_rstree);
1472
1473 /* Do our rgrp accounting for the reservation */
1474 rgd->rd_reserved += rs->rs_free; /* blocks reserved */
1475 spin_unlock(&rgd->rd_rsspin);
1476 trace_gfs2_rs(rs, TRACE_RS_INSERT);
1477}
1478
1479/**
1480 * rg_mblk_search - find a group of multiple free blocks to form a reservation
1481 * @rgd: the resource group descriptor
1482 * @ip: pointer to the inode for which we're reserving blocks
1483 * @ap: the allocation parameters
1484 *
1485 */
1486
1487static void rg_mblk_search(struct gfs2_rgrpd *rgd, struct gfs2_inode *ip,
1488 const struct gfs2_alloc_parms *ap)
1489{
1490 struct gfs2_rbm rbm = { .rgd = rgd, };
1491 u64 goal;
1492 struct gfs2_blkreserv *rs = &ip->i_res;
1493 u32 extlen;
1494 u32 free_blocks = rgd->rd_free_clone - rgd->rd_reserved;
1495 int ret;
1496 struct inode *inode = &ip->i_inode;
1497
1498 if (S_ISDIR(inode->i_mode))
1499 extlen = 1;
1500 else {
1501 extlen = max_t(u32, atomic_read(&rs->rs_sizehint), ap->target);
1502 extlen = clamp(extlen, RGRP_RSRV_MINBLKS, free_blocks);
1503 }
1504 if ((rgd->rd_free_clone < rgd->rd_reserved) || (free_blocks < extlen))
1505 return;
1506
1507 /* Find bitmap block that contains bits for goal block */
1508 if (rgrp_contains_block(rgd, ip->i_goal))
1509 goal = ip->i_goal;
1510 else
1511 goal = rgd->rd_last_alloc + rgd->rd_data0;
1512
1513 if (WARN_ON(gfs2_rbm_from_block(&rbm, goal)))
1514 return;
1515
1516 ret = gfs2_rbm_find(&rbm, GFS2_BLKST_FREE, &extlen, ip, true);
1517 if (ret == 0) {
1518 rs->rs_rbm = rbm;
1519 rs->rs_free = extlen;
1520 rs->rs_inum = ip->i_no_addr;
1521 rs_insert(ip);
1522 } else {
1523 if (goal == rgd->rd_last_alloc + rgd->rd_data0)
1524 rgd->rd_last_alloc = 0;
1525 }
1526}
1527
1528/**
1529 * gfs2_next_unreserved_block - Return next block that is not reserved
1530 * @rgd: The resource group
1531 * @block: The starting block
1532 * @length: The required length
1533 * @ip: Ignore any reservations for this inode
1534 *
1535 * If the block does not appear in any reservation, then return the
1536 * block number unchanged. If it does appear in the reservation, then
1537 * keep looking through the tree of reservations in order to find the
1538 * first block number which is not reserved.
1539 */
1540
1541static u64 gfs2_next_unreserved_block(struct gfs2_rgrpd *rgd, u64 block,
1542 u32 length,
1543 const struct gfs2_inode *ip)
1544{
1545 struct gfs2_blkreserv *rs;
1546 struct rb_node *n;
1547 int rc;
1548
1549 spin_lock(&rgd->rd_rsspin);
1550 n = rgd->rd_rstree.rb_node;
1551 while (n) {
1552 rs = rb_entry(n, struct gfs2_blkreserv, rs_node);
1553 rc = rs_cmp(block, length, rs);
1554 if (rc < 0)
1555 n = n->rb_left;
1556 else if (rc > 0)
1557 n = n->rb_right;
1558 else
1559 break;
1560 }
1561
1562 if (n) {
1563 while ((rs_cmp(block, length, rs) == 0) && (&ip->i_res != rs)) {
1564 block = gfs2_rbm_to_block(&rs->rs_rbm) + rs->rs_free;
1565 n = n->rb_right;
1566 if (n == NULL)
1567 break;
1568 rs = rb_entry(n, struct gfs2_blkreserv, rs_node);
1569 }
1570 }
1571
1572 spin_unlock(&rgd->rd_rsspin);
1573 return block;
1574}
1575
1576/**
1577 * gfs2_reservation_check_and_update - Check for reservations during block alloc
1578 * @rbm: The current position in the resource group
1579 * @ip: The inode for which we are searching for blocks
1580 * @minext: The minimum extent length
1581 * @maxext: A pointer to the maximum extent structure
1582 *
1583 * This checks the current position in the rgrp to see whether there is
1584 * a reservation covering this block. If not then this function is a
1585 * no-op. If there is, then the position is moved to the end of the
1586 * contiguous reservation(s) so that we are pointing at the first
1587 * non-reserved block.
1588 *
1589 * Returns: 0 if no reservation, 1 if @rbm has changed, otherwise an error
1590 */
1591
1592static int gfs2_reservation_check_and_update(struct gfs2_rbm *rbm,
1593 const struct gfs2_inode *ip,
1594 u32 minext,
1595 struct gfs2_extent *maxext)
1596{
1597 u64 block = gfs2_rbm_to_block(rbm);
1598 u32 extlen = 1;
1599 u64 nblock;
1600 int ret;
1601
1602 /*
1603 * If we have a minimum extent length, then skip over any extent
1604 * which is less than the min extent length in size.
1605 */
1606 if (minext) {
1607 extlen = gfs2_free_extlen(rbm, minext);
1608 if (extlen <= maxext->len)
1609 goto fail;
1610 }
1611
1612 /*
1613 * Check the extent which has been found against the reservations
1614 * and skip if parts of it are already reserved
1615 */
1616 nblock = gfs2_next_unreserved_block(rbm->rgd, block, extlen, ip);
1617 if (nblock == block) {
1618 if (!minext || extlen >= minext)
1619 return 0;
1620
1621 if (extlen > maxext->len) {
1622 maxext->len = extlen;
1623 maxext->rbm = *rbm;
1624 }
1625fail:
1626 nblock = block + extlen;
1627 }
1628 ret = gfs2_rbm_from_block(rbm, nblock);
1629 if (ret < 0)
1630 return ret;
1631 return 1;
1632}
1633
1634/**
1635 * gfs2_rbm_find - Look for blocks of a particular state
1636 * @rbm: Value/result starting position and final position
1637 * @state: The state which we want to find
1638 * @minext: Pointer to the requested extent length (NULL for a single block)
1639 * This is updated to be the actual reservation size.
1640 * @ip: If set, check for reservations
1641 * @nowrap: Stop looking at the end of the rgrp, rather than wrapping
1642 * around until we've reached the starting point.
1643 *
1644 * Side effects:
1645 * - If looking for free blocks, we set GBF_FULL on each bitmap which
1646 * has no free blocks in it.
1647 * - If looking for free blocks, we set rd_extfail_pt on each rgrp which
1648 * has come up short on a free block search.
1649 *
1650 * Returns: 0 on success, -ENOSPC if there is no block of the requested state
1651 */
1652
1653static int gfs2_rbm_find(struct gfs2_rbm *rbm, u8 state, u32 *minext,
1654 const struct gfs2_inode *ip, bool nowrap)
1655{
1656 struct buffer_head *bh;
1657 int initial_bii;
1658 u32 initial_offset;
1659 int first_bii = rbm->bii;
1660 u32 first_offset = rbm->offset;
1661 u32 offset;
1662 u8 *buffer;
1663 int n = 0;
1664 int iters = rbm->rgd->rd_length;
1665 int ret;
1666 struct gfs2_bitmap *bi;
1667 struct gfs2_extent maxext = { .rbm.rgd = rbm->rgd, };
1668
1669 /* If we are not starting at the beginning of a bitmap, then we
1670 * need to add one to the bitmap count to ensure that we search
1671 * the starting bitmap twice.
1672 */
1673 if (rbm->offset != 0)
1674 iters++;
1675
1676 while(1) {
1677 bi = rbm_bi(rbm);
1678 if (test_bit(GBF_FULL, &bi->bi_flags) &&
1679 (state == GFS2_BLKST_FREE))
1680 goto next_bitmap;
1681
1682 bh = bi->bi_bh;
1683 buffer = bh->b_data + bi->bi_offset;
1684 WARN_ON(!buffer_uptodate(bh));
1685 if (state != GFS2_BLKST_UNLINKED && bi->bi_clone)
1686 buffer = bi->bi_clone + bi->bi_offset;
1687 initial_offset = rbm->offset;
1688 offset = gfs2_bitfit(buffer, bi->bi_len, rbm->offset, state);
1689 if (offset == BFITNOENT)
1690 goto bitmap_full;
1691 rbm->offset = offset;
1692 if (ip == NULL)
1693 return 0;
1694
1695 initial_bii = rbm->bii;
1696 ret = gfs2_reservation_check_and_update(rbm, ip,
1697 minext ? *minext : 0,
1698 &maxext);
1699 if (ret == 0)
1700 return 0;
1701 if (ret > 0) {
1702 n += (rbm->bii - initial_bii);
1703 goto next_iter;
1704 }
1705 if (ret == -E2BIG) {
1706 rbm->bii = 0;
1707 rbm->offset = 0;
1708 n += (rbm->bii - initial_bii);
1709 goto res_covered_end_of_rgrp;
1710 }
1711 return ret;
1712
1713bitmap_full: /* Mark bitmap as full and fall through */
1714 if ((state == GFS2_BLKST_FREE) && initial_offset == 0)
1715 set_bit(GBF_FULL, &bi->bi_flags);
1716
1717next_bitmap: /* Find next bitmap in the rgrp */
1718 rbm->offset = 0;
1719 rbm->bii++;
1720 if (rbm->bii == rbm->rgd->rd_length)
1721 rbm->bii = 0;
1722res_covered_end_of_rgrp:
1723 if ((rbm->bii == 0) && nowrap)
1724 break;
1725 n++;
1726next_iter:
1727 if (n >= iters)
1728 break;
1729 }
1730
1731 if (minext == NULL || state != GFS2_BLKST_FREE)
1732 return -ENOSPC;
1733
1734 /* If the extent was too small, and it's smaller than the smallest
1735 to have failed before, remember for future reference that it's
1736 useless to search this rgrp again for this amount or more. */
1737 if ((first_offset == 0) && (first_bii == 0) &&
1738 (*minext < rbm->rgd->rd_extfail_pt))
1739 rbm->rgd->rd_extfail_pt = *minext;
1740
1741 /* If the maximum extent we found is big enough to fulfill the
1742 minimum requirements, use it anyway. */
1743 if (maxext.len) {
1744 *rbm = maxext.rbm;
1745 *minext = maxext.len;
1746 return 0;
1747 }
1748
1749 return -ENOSPC;
1750}
1751
1752/**
1753 * try_rgrp_unlink - Look for any unlinked, allocated, but unused inodes
1754 * @rgd: The rgrp
1755 * @last_unlinked: block address of the last dinode we unlinked
1756 * @skip: block address we should explicitly not unlink
1757 *
1758 * Returns: 0 if no error
1759 * The inode, if one has been found, in inode.
1760 */
1761
1762static void try_rgrp_unlink(struct gfs2_rgrpd *rgd, u64 *last_unlinked, u64 skip)
1763{
1764 u64 block;
1765 struct gfs2_sbd *sdp = rgd->rd_sbd;
1766 struct gfs2_glock *gl;
1767 struct gfs2_inode *ip;
1768 int error;
1769 int found = 0;
1770 struct gfs2_rbm rbm = { .rgd = rgd, .bii = 0, .offset = 0 };
1771
1772 while (1) {
1773 down_write(&sdp->sd_log_flush_lock);
1774 error = gfs2_rbm_find(&rbm, GFS2_BLKST_UNLINKED, NULL, NULL,
1775 true);
1776 up_write(&sdp->sd_log_flush_lock);
1777 if (error == -ENOSPC)
1778 break;
1779 if (WARN_ON_ONCE(error))
1780 break;
1781
1782 block = gfs2_rbm_to_block(&rbm);
1783 if (gfs2_rbm_from_block(&rbm, block + 1))
1784 break;
1785 if (*last_unlinked != NO_BLOCK && block <= *last_unlinked)
1786 continue;
1787 if (block == skip)
1788 continue;
1789 *last_unlinked = block;
1790
1791 error = gfs2_glock_get(sdp, block, &gfs2_iopen_glops, CREATE, &gl);
1792 if (error)
1793 continue;
1794
1795 /* If the inode is already in cache, we can ignore it here
1796 * because the existing inode disposal code will deal with
1797 * it when all refs have gone away. Accessing gl_object like
1798 * this is not safe in general. Here it is ok because we do
1799 * not dereference the pointer, and we only need an approx
1800 * answer to whether it is NULL or not.
1801 */
1802 ip = gl->gl_object;
1803
1804 if (ip || queue_work(gfs2_delete_workqueue, &gl->gl_delete) == 0)
1805 gfs2_glock_put(gl);
1806 else
1807 found++;
1808
1809 /* Limit reclaim to sensible number of tasks */
1810 if (found > NR_CPUS)
1811 return;
1812 }
1813
1814 rgd->rd_flags &= ~GFS2_RDF_CHECK;
1815 return;
1816}
1817
1818/**
1819 * gfs2_rgrp_congested - Use stats to figure out whether an rgrp is congested
1820 * @rgd: The rgrp in question
1821 * @loops: An indication of how picky we can be (0=very, 1=less so)
1822 *
1823 * This function uses the recently added glock statistics in order to
1824 * figure out whether a parciular resource group is suffering from
1825 * contention from multiple nodes. This is done purely on the basis
1826 * of timings, since this is the only data we have to work with and
1827 * our aim here is to reject a resource group which is highly contended
1828 * but (very important) not to do this too often in order to ensure that
1829 * we do not land up introducing fragmentation by changing resource
1830 * groups when not actually required.
1831 *
1832 * The calculation is fairly simple, we want to know whether the SRTTB
1833 * (i.e. smoothed round trip time for blocking operations) to acquire
1834 * the lock for this rgrp's glock is significantly greater than the
1835 * time taken for resource groups on average. We introduce a margin in
1836 * the form of the variable @var which is computed as the sum of the two
1837 * respective variences, and multiplied by a factor depending on @loops
1838 * and whether we have a lot of data to base the decision on. This is
1839 * then tested against the square difference of the means in order to
1840 * decide whether the result is statistically significant or not.
1841 *
1842 * Returns: A boolean verdict on the congestion status
1843 */
1844
1845static bool gfs2_rgrp_congested(const struct gfs2_rgrpd *rgd, int loops)
1846{
1847 const struct gfs2_glock *gl = rgd->rd_gl;
1848 const struct gfs2_sbd *sdp = gl->gl_name.ln_sbd;
1849 struct gfs2_lkstats *st;
1850 u64 r_dcount, l_dcount;
1851 u64 l_srttb, a_srttb = 0;
1852 s64 srttb_diff;
1853 u64 sqr_diff;
1854 u64 var;
1855 int cpu, nonzero = 0;
1856
1857 preempt_disable();
1858 for_each_present_cpu(cpu) {
1859 st = &per_cpu_ptr(sdp->sd_lkstats, cpu)->lkstats[LM_TYPE_RGRP];
1860 if (st->stats[GFS2_LKS_SRTTB]) {
1861 a_srttb += st->stats[GFS2_LKS_SRTTB];
1862 nonzero++;
1863 }
1864 }
1865 st = &this_cpu_ptr(sdp->sd_lkstats)->lkstats[LM_TYPE_RGRP];
1866 if (nonzero)
1867 do_div(a_srttb, nonzero);
1868 r_dcount = st->stats[GFS2_LKS_DCOUNT];
1869 var = st->stats[GFS2_LKS_SRTTVARB] +
1870 gl->gl_stats.stats[GFS2_LKS_SRTTVARB];
1871 preempt_enable();
1872
1873 l_srttb = gl->gl_stats.stats[GFS2_LKS_SRTTB];
1874 l_dcount = gl->gl_stats.stats[GFS2_LKS_DCOUNT];
1875
1876 if ((l_dcount < 1) || (r_dcount < 1) || (a_srttb == 0))
1877 return false;
1878
1879 srttb_diff = a_srttb - l_srttb;
1880 sqr_diff = srttb_diff * srttb_diff;
1881
1882 var *= 2;
1883 if (l_dcount < 8 || r_dcount < 8)
1884 var *= 2;
1885 if (loops == 1)
1886 var *= 2;
1887
1888 return ((srttb_diff < 0) && (sqr_diff > var));
1889}
1890
1891/**
1892 * gfs2_rgrp_used_recently
1893 * @rs: The block reservation with the rgrp to test
1894 * @msecs: The time limit in milliseconds
1895 *
1896 * Returns: True if the rgrp glock has been used within the time limit
1897 */
1898static bool gfs2_rgrp_used_recently(const struct gfs2_blkreserv *rs,
1899 u64 msecs)
1900{
1901 u64 tdiff;
1902
1903 tdiff = ktime_to_ns(ktime_sub(ktime_get_real(),
1904 rs->rs_rbm.rgd->rd_gl->gl_dstamp));
1905
1906 return tdiff > (msecs * 1000 * 1000);
1907}
1908
1909static u32 gfs2_orlov_skip(const struct gfs2_inode *ip)
1910{
1911 const struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1912 u32 skip;
1913
1914 get_random_bytes(&skip, sizeof(skip));
1915 return skip % sdp->sd_rgrps;
1916}
1917
1918static bool gfs2_select_rgrp(struct gfs2_rgrpd **pos, const struct gfs2_rgrpd *begin)
1919{
1920 struct gfs2_rgrpd *rgd = *pos;
1921 struct gfs2_sbd *sdp = rgd->rd_sbd;
1922
1923 rgd = gfs2_rgrpd_get_next(rgd);
1924 if (rgd == NULL)
1925 rgd = gfs2_rgrpd_get_first(sdp);
1926 *pos = rgd;
1927 if (rgd != begin) /* If we didn't wrap */
1928 return true;
1929 return false;
1930}
1931
1932/**
1933 * fast_to_acquire - determine if a resource group will be fast to acquire
1934 *
1935 * If this is one of our preferred rgrps, it should be quicker to acquire,
1936 * because we tried to set ourselves up as dlm lock master.
1937 */
1938static inline int fast_to_acquire(struct gfs2_rgrpd *rgd)
1939{
1940 struct gfs2_glock *gl = rgd->rd_gl;
1941
1942 if (gl->gl_state != LM_ST_UNLOCKED && list_empty(&gl->gl_holders) &&
1943 !test_bit(GLF_DEMOTE_IN_PROGRESS, &gl->gl_flags) &&
1944 !test_bit(GLF_DEMOTE, &gl->gl_flags))
1945 return 1;
1946 if (rgd->rd_flags & GFS2_RDF_PREFERRED)
1947 return 1;
1948 return 0;
1949}
1950
1951/**
1952 * gfs2_inplace_reserve - Reserve space in the filesystem
1953 * @ip: the inode to reserve space for
1954 * @ap: the allocation parameters
1955 *
1956 * We try our best to find an rgrp that has at least ap->target blocks
1957 * available. After a couple of passes (loops == 2), the prospects of finding
1958 * such an rgrp diminish. At this stage, we return the first rgrp that has
1959 * atleast ap->min_target blocks available. Either way, we set ap->allowed to
1960 * the number of blocks available in the chosen rgrp.
1961 *
1962 * Returns: 0 on success,
1963 * -ENOMEM if a suitable rgrp can't be found
1964 * errno otherwise
1965 */
1966
1967int gfs2_inplace_reserve(struct gfs2_inode *ip, struct gfs2_alloc_parms *ap)
1968{
1969 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
1970 struct gfs2_rgrpd *begin = NULL;
1971 struct gfs2_blkreserv *rs = &ip->i_res;
1972 int error = 0, rg_locked, flags = 0;
1973 u64 last_unlinked = NO_BLOCK;
1974 int loops = 0;
1975 u32 skip = 0;
1976
1977 if (sdp->sd_args.ar_rgrplvb)
1978 flags |= GL_SKIP;
1979 if (gfs2_assert_warn(sdp, ap->target))
1980 return -EINVAL;
1981 if (gfs2_rs_active(rs)) {
1982 begin = rs->rs_rbm.rgd;
1983 } else if (ip->i_rgd && rgrp_contains_block(ip->i_rgd, ip->i_goal)) {
1984 rs->rs_rbm.rgd = begin = ip->i_rgd;
1985 } else {
1986 check_and_update_goal(ip);
1987 rs->rs_rbm.rgd = begin = gfs2_blk2rgrpd(sdp, ip->i_goal, 1);
1988 }
1989 if (S_ISDIR(ip->i_inode.i_mode) && (ap->aflags & GFS2_AF_ORLOV))
1990 skip = gfs2_orlov_skip(ip);
1991 if (rs->rs_rbm.rgd == NULL)
1992 return -EBADSLT;
1993
1994 while (loops < 3) {
1995 rg_locked = 1;
1996
1997 if (!gfs2_glock_is_locked_by_me(rs->rs_rbm.rgd->rd_gl)) {
1998 rg_locked = 0;
1999 if (skip && skip--)
2000 goto next_rgrp;
2001 if (!gfs2_rs_active(rs)) {
2002 if (loops == 0 &&
2003 !fast_to_acquire(rs->rs_rbm.rgd))
2004 goto next_rgrp;
2005 if ((loops < 2) &&
2006 gfs2_rgrp_used_recently(rs, 1000) &&
2007 gfs2_rgrp_congested(rs->rs_rbm.rgd, loops))
2008 goto next_rgrp;
2009 }
2010 error = gfs2_glock_nq_init(rs->rs_rbm.rgd->rd_gl,
2011 LM_ST_EXCLUSIVE, flags,
2012 &rs->rs_rgd_gh);
2013 if (unlikely(error))
2014 return error;
2015 if (!gfs2_rs_active(rs) && (loops < 2) &&
2016 gfs2_rgrp_congested(rs->rs_rbm.rgd, loops))
2017 goto skip_rgrp;
2018 if (sdp->sd_args.ar_rgrplvb) {
2019 error = update_rgrp_lvb(rs->rs_rbm.rgd);
2020 if (unlikely(error)) {
2021 gfs2_glock_dq_uninit(&rs->rs_rgd_gh);
2022 return error;
2023 }
2024 }
2025 }
2026
2027 /* Skip unuseable resource groups */
2028 if ((rs->rs_rbm.rgd->rd_flags & (GFS2_RGF_NOALLOC |
2029 GFS2_RDF_ERROR)) ||
2030 (loops == 0 && ap->target > rs->rs_rbm.rgd->rd_extfail_pt))
2031 goto skip_rgrp;
2032
2033 if (sdp->sd_args.ar_rgrplvb)
2034 gfs2_rgrp_bh_get(rs->rs_rbm.rgd);
2035
2036 /* Get a reservation if we don't already have one */
2037 if (!gfs2_rs_active(rs))
2038 rg_mblk_search(rs->rs_rbm.rgd, ip, ap);
2039
2040 /* Skip rgrps when we can't get a reservation on first pass */
2041 if (!gfs2_rs_active(rs) && (loops < 1))
2042 goto check_rgrp;
2043
2044 /* If rgrp has enough free space, use it */
2045 if (rs->rs_rbm.rgd->rd_free_clone >= ap->target ||
2046 (loops == 2 && ap->min_target &&
2047 rs->rs_rbm.rgd->rd_free_clone >= ap->min_target)) {
2048 ip->i_rgd = rs->rs_rbm.rgd;
2049 ap->allowed = ip->i_rgd->rd_free_clone;
2050 return 0;
2051 }
2052check_rgrp:
2053 /* Check for unlinked inodes which can be reclaimed */
2054 if (rs->rs_rbm.rgd->rd_flags & GFS2_RDF_CHECK)
2055 try_rgrp_unlink(rs->rs_rbm.rgd, &last_unlinked,
2056 ip->i_no_addr);
2057skip_rgrp:
2058 /* Drop reservation, if we couldn't use reserved rgrp */
2059 if (gfs2_rs_active(rs))
2060 gfs2_rs_deltree(rs);
2061
2062 /* Unlock rgrp if required */
2063 if (!rg_locked)
2064 gfs2_glock_dq_uninit(&rs->rs_rgd_gh);
2065next_rgrp:
2066 /* Find the next rgrp, and continue looking */
2067 if (gfs2_select_rgrp(&rs->rs_rbm.rgd, begin))
2068 continue;
2069 if (skip)
2070 continue;
2071
2072 /* If we've scanned all the rgrps, but found no free blocks
2073 * then this checks for some less likely conditions before
2074 * trying again.
2075 */
2076 loops++;
2077 /* Check that fs hasn't grown if writing to rindex */
2078 if (ip == GFS2_I(sdp->sd_rindex) && !sdp->sd_rindex_uptodate) {
2079 error = gfs2_ri_update(ip);
2080 if (error)
2081 return error;
2082 }
2083 /* Flushing the log may release space */
2084 if (loops == 2)
2085 gfs2_log_flush(sdp, NULL, NORMAL_FLUSH);
2086 }
2087
2088 return -ENOSPC;
2089}
2090
2091/**
2092 * gfs2_inplace_release - release an inplace reservation
2093 * @ip: the inode the reservation was taken out on
2094 *
2095 * Release a reservation made by gfs2_inplace_reserve().
2096 */
2097
2098void gfs2_inplace_release(struct gfs2_inode *ip)
2099{
2100 struct gfs2_blkreserv *rs = &ip->i_res;
2101
2102 if (gfs2_holder_initialized(&rs->rs_rgd_gh))
2103 gfs2_glock_dq_uninit(&rs->rs_rgd_gh);
2104}
2105
2106/**
2107 * gfs2_get_block_type - Check a block in a RG is of given type
2108 * @rgd: the resource group holding the block
2109 * @block: the block number
2110 *
2111 * Returns: The block type (GFS2_BLKST_*)
2112 */
2113
2114static unsigned char gfs2_get_block_type(struct gfs2_rgrpd *rgd, u64 block)
2115{
2116 struct gfs2_rbm rbm = { .rgd = rgd, };
2117 int ret;
2118
2119 ret = gfs2_rbm_from_block(&rbm, block);
2120 WARN_ON_ONCE(ret != 0);
2121
2122 return gfs2_testbit(&rbm);
2123}
2124
2125
2126/**
2127 * gfs2_alloc_extent - allocate an extent from a given bitmap
2128 * @rbm: the resource group information
2129 * @dinode: TRUE if the first block we allocate is for a dinode
2130 * @n: The extent length (value/result)
2131 *
2132 * Add the bitmap buffer to the transaction.
2133 * Set the found bits to @new_state to change block's allocation state.
2134 */
2135static void gfs2_alloc_extent(const struct gfs2_rbm *rbm, bool dinode,
2136 unsigned int *n)
2137{
2138 struct gfs2_rbm pos = { .rgd = rbm->rgd, };
2139 const unsigned int elen = *n;
2140 u64 block;
2141 int ret;
2142
2143 *n = 1;
2144 block = gfs2_rbm_to_block(rbm);
2145 gfs2_trans_add_meta(rbm->rgd->rd_gl, rbm_bi(rbm)->bi_bh);
2146 gfs2_setbit(rbm, true, dinode ? GFS2_BLKST_DINODE : GFS2_BLKST_USED);
2147 block++;
2148 while (*n < elen) {
2149 ret = gfs2_rbm_from_block(&pos, block);
2150 if (ret || gfs2_testbit(&pos) != GFS2_BLKST_FREE)
2151 break;
2152 gfs2_trans_add_meta(pos.rgd->rd_gl, rbm_bi(&pos)->bi_bh);
2153 gfs2_setbit(&pos, true, GFS2_BLKST_USED);
2154 (*n)++;
2155 block++;
2156 }
2157}
2158
2159/**
2160 * rgblk_free - Change alloc state of given block(s)
2161 * @sdp: the filesystem
2162 * @bstart: the start of a run of blocks to free
2163 * @blen: the length of the block run (all must lie within ONE RG!)
2164 * @new_state: GFS2_BLKST_XXX the after-allocation block state
2165 *
2166 * Returns: Resource group containing the block(s)
2167 */
2168
2169static struct gfs2_rgrpd *rgblk_free(struct gfs2_sbd *sdp, u64 bstart,
2170 u32 blen, unsigned char new_state)
2171{
2172 struct gfs2_rbm rbm;
2173 struct gfs2_bitmap *bi, *bi_prev = NULL;
2174
2175 rbm.rgd = gfs2_blk2rgrpd(sdp, bstart, 1);
2176 if (!rbm.rgd) {
2177 if (gfs2_consist(sdp))
2178 fs_err(sdp, "block = %llu\n", (unsigned long long)bstart);
2179 return NULL;
2180 }
2181
2182 gfs2_rbm_from_block(&rbm, bstart);
2183 while (blen--) {
2184 bi = rbm_bi(&rbm);
2185 if (bi != bi_prev) {
2186 if (!bi->bi_clone) {
2187 bi->bi_clone = kmalloc(bi->bi_bh->b_size,
2188 GFP_NOFS | __GFP_NOFAIL);
2189 memcpy(bi->bi_clone + bi->bi_offset,
2190 bi->bi_bh->b_data + bi->bi_offset,
2191 bi->bi_len);
2192 }
2193 gfs2_trans_add_meta(rbm.rgd->rd_gl, bi->bi_bh);
2194 bi_prev = bi;
2195 }
2196 gfs2_setbit(&rbm, false, new_state);
2197 gfs2_rbm_incr(&rbm);
2198 }
2199
2200 return rbm.rgd;
2201}
2202
2203/**
2204 * gfs2_rgrp_dump - print out an rgrp
2205 * @seq: The iterator
2206 * @gl: The glock in question
2207 *
2208 */
2209
2210void gfs2_rgrp_dump(struct seq_file *seq, const struct gfs2_glock *gl)
2211{
2212 struct gfs2_rgrpd *rgd = gl->gl_object;
2213 struct gfs2_blkreserv *trs;
2214 const struct rb_node *n;
2215
2216 if (rgd == NULL)
2217 return;
2218 gfs2_print_dbg(seq, " R: n:%llu f:%02x b:%u/%u i:%u r:%u e:%u\n",
2219 (unsigned long long)rgd->rd_addr, rgd->rd_flags,
2220 rgd->rd_free, rgd->rd_free_clone, rgd->rd_dinodes,
2221 rgd->rd_reserved, rgd->rd_extfail_pt);
2222 spin_lock(&rgd->rd_rsspin);
2223 for (n = rb_first(&rgd->rd_rstree); n; n = rb_next(&trs->rs_node)) {
2224 trs = rb_entry(n, struct gfs2_blkreserv, rs_node);
2225 dump_rs(seq, trs);
2226 }
2227 spin_unlock(&rgd->rd_rsspin);
2228}
2229
2230static void gfs2_rgrp_error(struct gfs2_rgrpd *rgd)
2231{
2232 struct gfs2_sbd *sdp = rgd->rd_sbd;
2233 fs_warn(sdp, "rgrp %llu has an error, marking it readonly until umount\n",
2234 (unsigned long long)rgd->rd_addr);
2235 fs_warn(sdp, "umount on all nodes and run fsck.gfs2 to fix the error\n");
2236 gfs2_rgrp_dump(NULL, rgd->rd_gl);
2237 rgd->rd_flags |= GFS2_RDF_ERROR;
2238}
2239
2240/**
2241 * gfs2_adjust_reservation - Adjust (or remove) a reservation after allocation
2242 * @ip: The inode we have just allocated blocks for
2243 * @rbm: The start of the allocated blocks
2244 * @len: The extent length
2245 *
2246 * Adjusts a reservation after an allocation has taken place. If the
2247 * reservation does not match the allocation, or if it is now empty
2248 * then it is removed.
2249 */
2250
2251static void gfs2_adjust_reservation(struct gfs2_inode *ip,
2252 const struct gfs2_rbm *rbm, unsigned len)
2253{
2254 struct gfs2_blkreserv *rs = &ip->i_res;
2255 struct gfs2_rgrpd *rgd = rbm->rgd;
2256 unsigned rlen;
2257 u64 block;
2258 int ret;
2259
2260 spin_lock(&rgd->rd_rsspin);
2261 if (gfs2_rs_active(rs)) {
2262 if (gfs2_rbm_eq(&rs->rs_rbm, rbm)) {
2263 block = gfs2_rbm_to_block(rbm);
2264 ret = gfs2_rbm_from_block(&rs->rs_rbm, block + len);
2265 rlen = min(rs->rs_free, len);
2266 rs->rs_free -= rlen;
2267 rgd->rd_reserved -= rlen;
2268 trace_gfs2_rs(rs, TRACE_RS_CLAIM);
2269 if (rs->rs_free && !ret)
2270 goto out;
2271 /* We used up our block reservation, so we should
2272 reserve more blocks next time. */
2273 atomic_add(RGRP_RSRV_ADDBLKS, &rs->rs_sizehint);
2274 }
2275 __rs_deltree(rs);
2276 }
2277out:
2278 spin_unlock(&rgd->rd_rsspin);
2279}
2280
2281/**
2282 * gfs2_set_alloc_start - Set starting point for block allocation
2283 * @rbm: The rbm which will be set to the required location
2284 * @ip: The gfs2 inode
2285 * @dinode: Flag to say if allocation includes a new inode
2286 *
2287 * This sets the starting point from the reservation if one is active
2288 * otherwise it falls back to guessing a start point based on the
2289 * inode's goal block or the last allocation point in the rgrp.
2290 */
2291
2292static void gfs2_set_alloc_start(struct gfs2_rbm *rbm,
2293 const struct gfs2_inode *ip, bool dinode)
2294{
2295 u64 goal;
2296
2297 if (gfs2_rs_active(&ip->i_res)) {
2298 *rbm = ip->i_res.rs_rbm;
2299 return;
2300 }
2301
2302 if (!dinode && rgrp_contains_block(rbm->rgd, ip->i_goal))
2303 goal = ip->i_goal;
2304 else
2305 goal = rbm->rgd->rd_last_alloc + rbm->rgd->rd_data0;
2306
2307 gfs2_rbm_from_block(rbm, goal);
2308}
2309
2310/**
2311 * gfs2_alloc_blocks - Allocate one or more blocks of data and/or a dinode
2312 * @ip: the inode to allocate the block for
2313 * @bn: Used to return the starting block number
2314 * @nblocks: requested number of blocks/extent length (value/result)
2315 * @dinode: 1 if we're allocating a dinode block, else 0
2316 * @generation: the generation number of the inode
2317 *
2318 * Returns: 0 or error
2319 */
2320
2321int gfs2_alloc_blocks(struct gfs2_inode *ip, u64 *bn, unsigned int *nblocks,
2322 bool dinode, u64 *generation)
2323{
2324 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
2325 struct buffer_head *dibh;
2326 struct gfs2_rbm rbm = { .rgd = ip->i_rgd, };
2327 unsigned int ndata;
2328 u64 block; /* block, within the file system scope */
2329 int error;
2330
2331 gfs2_set_alloc_start(&rbm, ip, dinode);
2332 error = gfs2_rbm_find(&rbm, GFS2_BLKST_FREE, NULL, ip, false);
2333
2334 if (error == -ENOSPC) {
2335 gfs2_set_alloc_start(&rbm, ip, dinode);
2336 error = gfs2_rbm_find(&rbm, GFS2_BLKST_FREE, NULL, NULL, false);
2337 }
2338
2339 /* Since all blocks are reserved in advance, this shouldn't happen */
2340 if (error) {
2341 fs_warn(sdp, "inum=%llu error=%d, nblocks=%u, full=%d fail_pt=%d\n",
2342 (unsigned long long)ip->i_no_addr, error, *nblocks,
2343 test_bit(GBF_FULL, &rbm.rgd->rd_bits->bi_flags),
2344 rbm.rgd->rd_extfail_pt);
2345 goto rgrp_error;
2346 }
2347
2348 gfs2_alloc_extent(&rbm, dinode, nblocks);
2349 block = gfs2_rbm_to_block(&rbm);
2350 rbm.rgd->rd_last_alloc = block - rbm.rgd->rd_data0;
2351 if (gfs2_rs_active(&ip->i_res))
2352 gfs2_adjust_reservation(ip, &rbm, *nblocks);
2353 ndata = *nblocks;
2354 if (dinode)
2355 ndata--;
2356
2357 if (!dinode) {
2358 ip->i_goal = block + ndata - 1;
2359 error = gfs2_meta_inode_buffer(ip, &dibh);
2360 if (error == 0) {
2361 struct gfs2_dinode *di =
2362 (struct gfs2_dinode *)dibh->b_data;
2363 gfs2_trans_add_meta(ip->i_gl, dibh);
2364 di->di_goal_meta = di->di_goal_data =
2365 cpu_to_be64(ip->i_goal);
2366 brelse(dibh);
2367 }
2368 }
2369 if (rbm.rgd->rd_free < *nblocks) {
2370 pr_warn("nblocks=%u\n", *nblocks);
2371 goto rgrp_error;
2372 }
2373
2374 rbm.rgd->rd_free -= *nblocks;
2375 if (dinode) {
2376 rbm.rgd->rd_dinodes++;
2377 *generation = rbm.rgd->rd_igeneration++;
2378 if (*generation == 0)
2379 *generation = rbm.rgd->rd_igeneration++;
2380 }
2381
2382 gfs2_trans_add_meta(rbm.rgd->rd_gl, rbm.rgd->rd_bits[0].bi_bh);
2383 gfs2_rgrp_out(rbm.rgd, rbm.rgd->rd_bits[0].bi_bh->b_data);
2384 gfs2_rgrp_ondisk2lvb(rbm.rgd->rd_rgl, rbm.rgd->rd_bits[0].bi_bh->b_data);
2385
2386 gfs2_statfs_change(sdp, 0, -(s64)*nblocks, dinode ? 1 : 0);
2387 if (dinode)
2388 gfs2_trans_add_unrevoke(sdp, block, *nblocks);
2389
2390 gfs2_quota_change(ip, *nblocks, ip->i_inode.i_uid, ip->i_inode.i_gid);
2391
2392 rbm.rgd->rd_free_clone -= *nblocks;
2393 trace_gfs2_block_alloc(ip, rbm.rgd, block, *nblocks,
2394 dinode ? GFS2_BLKST_DINODE : GFS2_BLKST_USED);
2395 *bn = block;
2396 return 0;
2397
2398rgrp_error:
2399 gfs2_rgrp_error(rbm.rgd);
2400 return -EIO;
2401}
2402
2403/**
2404 * __gfs2_free_blocks - free a contiguous run of block(s)
2405 * @ip: the inode these blocks are being freed from
2406 * @bstart: first block of a run of contiguous blocks
2407 * @blen: the length of the block run
2408 * @meta: 1 if the blocks represent metadata
2409 *
2410 */
2411
2412void __gfs2_free_blocks(struct gfs2_inode *ip, u64 bstart, u32 blen, int meta)
2413{
2414 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
2415 struct gfs2_rgrpd *rgd;
2416
2417 rgd = rgblk_free(sdp, bstart, blen, GFS2_BLKST_FREE);
2418 if (!rgd)
2419 return;
2420 trace_gfs2_block_alloc(ip, rgd, bstart, blen, GFS2_BLKST_FREE);
2421 rgd->rd_free += blen;
2422 rgd->rd_flags &= ~GFS2_RGF_TRIMMED;
2423 gfs2_trans_add_meta(rgd->rd_gl, rgd->rd_bits[0].bi_bh);
2424 gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
2425 gfs2_rgrp_ondisk2lvb(rgd->rd_rgl, rgd->rd_bits[0].bi_bh->b_data);
2426
2427 /* Directories keep their data in the metadata address space */
2428 if (meta || ip->i_depth)
2429 gfs2_meta_wipe(ip, bstart, blen);
2430}
2431
2432/**
2433 * gfs2_free_meta - free a contiguous run of data block(s)
2434 * @ip: the inode these blocks are being freed from
2435 * @bstart: first block of a run of contiguous blocks
2436 * @blen: the length of the block run
2437 *
2438 */
2439
2440void gfs2_free_meta(struct gfs2_inode *ip, u64 bstart, u32 blen)
2441{
2442 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
2443
2444 __gfs2_free_blocks(ip, bstart, blen, 1);
2445 gfs2_statfs_change(sdp, 0, +blen, 0);
2446 gfs2_quota_change(ip, -(s64)blen, ip->i_inode.i_uid, ip->i_inode.i_gid);
2447}
2448
2449void gfs2_unlink_di(struct inode *inode)
2450{
2451 struct gfs2_inode *ip = GFS2_I(inode);
2452 struct gfs2_sbd *sdp = GFS2_SB(inode);
2453 struct gfs2_rgrpd *rgd;
2454 u64 blkno = ip->i_no_addr;
2455
2456 rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_UNLINKED);
2457 if (!rgd)
2458 return;
2459 trace_gfs2_block_alloc(ip, rgd, blkno, 1, GFS2_BLKST_UNLINKED);
2460 gfs2_trans_add_meta(rgd->rd_gl, rgd->rd_bits[0].bi_bh);
2461 gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
2462 gfs2_rgrp_ondisk2lvb(rgd->rd_rgl, rgd->rd_bits[0].bi_bh->b_data);
2463 update_rgrp_lvb_unlinked(rgd, 1);
2464}
2465
2466static void gfs2_free_uninit_di(struct gfs2_rgrpd *rgd, u64 blkno)
2467{
2468 struct gfs2_sbd *sdp = rgd->rd_sbd;
2469 struct gfs2_rgrpd *tmp_rgd;
2470
2471 tmp_rgd = rgblk_free(sdp, blkno, 1, GFS2_BLKST_FREE);
2472 if (!tmp_rgd)
2473 return;
2474 gfs2_assert_withdraw(sdp, rgd == tmp_rgd);
2475
2476 if (!rgd->rd_dinodes)
2477 gfs2_consist_rgrpd(rgd);
2478 rgd->rd_dinodes--;
2479 rgd->rd_free++;
2480
2481 gfs2_trans_add_meta(rgd->rd_gl, rgd->rd_bits[0].bi_bh);
2482 gfs2_rgrp_out(rgd, rgd->rd_bits[0].bi_bh->b_data);
2483 gfs2_rgrp_ondisk2lvb(rgd->rd_rgl, rgd->rd_bits[0].bi_bh->b_data);
2484 update_rgrp_lvb_unlinked(rgd, -1);
2485
2486 gfs2_statfs_change(sdp, 0, +1, -1);
2487}
2488
2489
2490void gfs2_free_di(struct gfs2_rgrpd *rgd, struct gfs2_inode *ip)
2491{
2492 gfs2_free_uninit_di(rgd, ip->i_no_addr);
2493 trace_gfs2_block_alloc(ip, rgd, ip->i_no_addr, 1, GFS2_BLKST_FREE);
2494 gfs2_quota_change(ip, -1, ip->i_inode.i_uid, ip->i_inode.i_gid);
2495 gfs2_meta_wipe(ip, ip->i_no_addr, 1);
2496}
2497
2498/**
2499 * gfs2_check_blk_type - Check the type of a block
2500 * @sdp: The superblock
2501 * @no_addr: The block number to check
2502 * @type: The block type we are looking for
2503 *
2504 * Returns: 0 if the block type matches the expected type
2505 * -ESTALE if it doesn't match
2506 * or -ve errno if something went wrong while checking
2507 */
2508
2509int gfs2_check_blk_type(struct gfs2_sbd *sdp, u64 no_addr, unsigned int type)
2510{
2511 struct gfs2_rgrpd *rgd;
2512 struct gfs2_holder rgd_gh;
2513 int error = -EINVAL;
2514
2515 rgd = gfs2_blk2rgrpd(sdp, no_addr, 1);
2516 if (!rgd)
2517 goto fail;
2518
2519 error = gfs2_glock_nq_init(rgd->rd_gl, LM_ST_SHARED, 0, &rgd_gh);
2520 if (error)
2521 goto fail;
2522
2523 if (gfs2_get_block_type(rgd, no_addr) != type)
2524 error = -ESTALE;
2525
2526 gfs2_glock_dq_uninit(&rgd_gh);
2527fail:
2528 return error;
2529}
2530
2531/**
2532 * gfs2_rlist_add - add a RG to a list of RGs
2533 * @ip: the inode
2534 * @rlist: the list of resource groups
2535 * @block: the block
2536 *
2537 * Figure out what RG a block belongs to and add that RG to the list
2538 *
2539 * FIXME: Don't use NOFAIL
2540 *
2541 */
2542
2543void gfs2_rlist_add(struct gfs2_inode *ip, struct gfs2_rgrp_list *rlist,
2544 u64 block)
2545{
2546 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
2547 struct gfs2_rgrpd *rgd;
2548 struct gfs2_rgrpd **tmp;
2549 unsigned int new_space;
2550 unsigned int x;
2551
2552 if (gfs2_assert_warn(sdp, !rlist->rl_ghs))
2553 return;
2554
2555 if (ip->i_rgd && rgrp_contains_block(ip->i_rgd, block))
2556 rgd = ip->i_rgd;
2557 else
2558 rgd = gfs2_blk2rgrpd(sdp, block, 1);
2559 if (!rgd) {
2560 fs_err(sdp, "rlist_add: no rgrp for block %llu\n", (unsigned long long)block);
2561 return;
2562 }
2563 ip->i_rgd = rgd;
2564
2565 for (x = 0; x < rlist->rl_rgrps; x++)
2566 if (rlist->rl_rgd[x] == rgd)
2567 return;
2568
2569 if (rlist->rl_rgrps == rlist->rl_space) {
2570 new_space = rlist->rl_space + 10;
2571
2572 tmp = kcalloc(new_space, sizeof(struct gfs2_rgrpd *),
2573 GFP_NOFS | __GFP_NOFAIL);
2574
2575 if (rlist->rl_rgd) {
2576 memcpy(tmp, rlist->rl_rgd,
2577 rlist->rl_space * sizeof(struct gfs2_rgrpd *));
2578 kfree(rlist->rl_rgd);
2579 }
2580
2581 rlist->rl_space = new_space;
2582 rlist->rl_rgd = tmp;
2583 }
2584
2585 rlist->rl_rgd[rlist->rl_rgrps++] = rgd;
2586}
2587
2588/**
2589 * gfs2_rlist_alloc - all RGs have been added to the rlist, now allocate
2590 * and initialize an array of glock holders for them
2591 * @rlist: the list of resource groups
2592 * @state: the lock state to acquire the RG lock in
2593 *
2594 * FIXME: Don't use NOFAIL
2595 *
2596 */
2597
2598void gfs2_rlist_alloc(struct gfs2_rgrp_list *rlist, unsigned int state)
2599{
2600 unsigned int x;
2601
2602 rlist->rl_ghs = kmalloc(rlist->rl_rgrps * sizeof(struct gfs2_holder),
2603 GFP_NOFS | __GFP_NOFAIL);
2604 for (x = 0; x < rlist->rl_rgrps; x++)
2605 gfs2_holder_init(rlist->rl_rgd[x]->rd_gl,
2606 state, 0,
2607 &rlist->rl_ghs[x]);
2608}
2609
2610/**
2611 * gfs2_rlist_free - free a resource group list
2612 * @rlist: the list of resource groups
2613 *
2614 */
2615
2616void gfs2_rlist_free(struct gfs2_rgrp_list *rlist)
2617{
2618 unsigned int x;
2619
2620 kfree(rlist->rl_rgd);
2621
2622 if (rlist->rl_ghs) {
2623 for (x = 0; x < rlist->rl_rgrps; x++)
2624 gfs2_holder_uninit(&rlist->rl_ghs[x]);
2625 kfree(rlist->rl_ghs);
2626 rlist->rl_ghs = NULL;
2627 }
2628}
2629