GNU Linux-libre 5.10.219-gnu1
[releases.git] / fs / omfs / bitmap.c
1 // SPDX-License-Identifier: GPL-2.0
2 #include <linux/kernel.h>
3 #include <linux/fs.h>
4 #include <linux/buffer_head.h>
5 #include <asm/div64.h>
6 #include "omfs.h"
7
8 unsigned long omfs_count_free(struct super_block *sb)
9 {
10         unsigned int i;
11         unsigned long sum = 0;
12         struct omfs_sb_info *sbi = OMFS_SB(sb);
13         int nbits = sb->s_blocksize * 8;
14
15         for (i = 0; i < sbi->s_imap_size; i++)
16                 sum += nbits - bitmap_weight(sbi->s_imap[i], nbits);
17
18         return sum;
19 }
20
21 /*
22  *  Counts the run of zero bits starting at bit up to max.
23  *  It handles the case where a run might spill over a buffer.
24  *  Called with bitmap lock.
25  */
26 static int count_run(unsigned long **addr, int nbits,
27                 int addrlen, int bit, int max)
28 {
29         int count = 0;
30         int x;
31
32         for (; addrlen > 0; addrlen--, addr++) {
33                 x = find_next_bit(*addr, nbits, bit);
34                 count += x - bit;
35
36                 if (x < nbits || count > max)
37                         return min(count, max);
38
39                 bit = 0;
40         }
41         return min(count, max);
42 }
43
44 /*
45  * Sets or clears the run of count bits starting with bit.
46  * Called with bitmap lock.
47  */
48 static int set_run(struct super_block *sb, int map,
49                 int nbits, int bit, int count, int set)
50 {
51         int i;
52         int err;
53         struct buffer_head *bh;
54         struct omfs_sb_info *sbi = OMFS_SB(sb);
55
56         err = -ENOMEM;
57         bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino) + map);
58         if (!bh)
59                 goto out;
60
61         for (i = 0; i < count; i++, bit++) {
62                 if (bit >= nbits) {
63                         bit = 0;
64                         map++;
65
66                         mark_buffer_dirty(bh);
67                         brelse(bh);
68                         bh = sb_bread(sb,
69                                 clus_to_blk(sbi, sbi->s_bitmap_ino) + map);
70                         if (!bh)
71                                 goto out;
72                 }
73                 if (set) {
74                         set_bit(bit, sbi->s_imap[map]);
75                         set_bit(bit, (unsigned long *)bh->b_data);
76                 } else {
77                         clear_bit(bit, sbi->s_imap[map]);
78                         clear_bit(bit, (unsigned long *)bh->b_data);
79                 }
80         }
81         mark_buffer_dirty(bh);
82         brelse(bh);
83         err = 0;
84 out:
85         return err;
86 }
87
88 /*
89  * Tries to allocate exactly one block.  Returns true if successful.
90  */
91 int omfs_allocate_block(struct super_block *sb, u64 block)
92 {
93         struct buffer_head *bh;
94         struct omfs_sb_info *sbi = OMFS_SB(sb);
95         int bits_per_entry = 8 * sb->s_blocksize;
96         unsigned int map, bit;
97         int ret = 0;
98         u64 tmp;
99
100         tmp = block;
101         bit = do_div(tmp, bits_per_entry);
102         map = tmp;
103
104         mutex_lock(&sbi->s_bitmap_lock);
105         if (map >= sbi->s_imap_size || test_and_set_bit(bit, sbi->s_imap[map]))
106                 goto out;
107
108         if (sbi->s_bitmap_ino > 0) {
109                 bh = sb_bread(sb, clus_to_blk(sbi, sbi->s_bitmap_ino) + map);
110                 if (!bh)
111                         goto out;
112
113                 set_bit(bit, (unsigned long *)bh->b_data);
114                 mark_buffer_dirty(bh);
115                 brelse(bh);
116         }
117         ret = 1;
118 out:
119         mutex_unlock(&sbi->s_bitmap_lock);
120         return ret;
121 }
122
123
124 /*
125  *  Tries to allocate a set of blocks.  The request size depends on the
126  *  type: for inodes, we must allocate sbi->s_mirrors blocks, and for file
127  *  blocks, we try to allocate sbi->s_clustersize, but can always get away
128  *  with just one block.
129  */
130 int omfs_allocate_range(struct super_block *sb,
131                         int min_request,
132                         int max_request,
133                         u64 *return_block,
134                         int *return_size)
135 {
136         struct omfs_sb_info *sbi = OMFS_SB(sb);
137         int bits_per_entry = 8 * sb->s_blocksize;
138         int ret = 0;
139         int i, run, bit;
140
141         mutex_lock(&sbi->s_bitmap_lock);
142         for (i = 0; i < sbi->s_imap_size; i++) {
143                 bit = 0;
144                 while (bit < bits_per_entry) {
145                         bit = find_next_zero_bit(sbi->s_imap[i], bits_per_entry,
146                                 bit);
147
148                         if (bit == bits_per_entry)
149                                 break;
150
151                         run = count_run(&sbi->s_imap[i], bits_per_entry,
152                                 sbi->s_imap_size-i, bit, max_request);
153
154                         if (run >= min_request)
155                                 goto found;
156                         bit += run;
157                 }
158         }
159         ret = -ENOSPC;
160         goto out;
161
162 found:
163         *return_block = (u64) i * bits_per_entry + bit;
164         *return_size = run;
165         ret = set_run(sb, i, bits_per_entry, bit, run, 1);
166
167 out:
168         mutex_unlock(&sbi->s_bitmap_lock);
169         return ret;
170 }
171
172 /*
173  * Clears count bits starting at a given block.
174  */
175 int omfs_clear_range(struct super_block *sb, u64 block, int count)
176 {
177         struct omfs_sb_info *sbi = OMFS_SB(sb);
178         int bits_per_entry = 8 * sb->s_blocksize;
179         u64 tmp;
180         unsigned int map, bit;
181         int ret;
182
183         tmp = block;
184         bit = do_div(tmp, bits_per_entry);
185         map = tmp;
186
187         if (map >= sbi->s_imap_size)
188                 return 0;
189
190         mutex_lock(&sbi->s_bitmap_lock);
191         ret = set_run(sb, map, bits_per_entry, bit, count, 0);
192         mutex_unlock(&sbi->s_bitmap_lock);
193         return ret;
194 }