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