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
8unsigned 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(src: 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 */
26static 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: *addr, size: nbits, offset: 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 */
48static 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, block: clus_to_blk(sbi, block: 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 block: clus_to_blk(sbi, block: sbi->s_bitmap_ino) + map);
70 if (!bh)
71 goto out;
72 }
73 if (set) {
74 set_bit(nr: bit, addr: sbi->s_imap[map]);
75 set_bit(nr: bit, addr: (unsigned long *)bh->b_data);
76 } else {
77 clear_bit(nr: bit, addr: sbi->s_imap[map]);
78 clear_bit(nr: bit, addr: (unsigned long *)bh->b_data);
79 }
80 }
81 mark_buffer_dirty(bh);
82 brelse(bh);
83 err = 0;
84out:
85 return err;
86}
87
88/*
89 * Tries to allocate exactly one block. Returns true if successful.
90 */
91int 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(nr: bit, addr: sbi->s_imap[map]))
106 goto out;
107
108 if (sbi->s_bitmap_ino > 0) {
109 bh = sb_bread(sb, block: clus_to_blk(sbi, block: sbi->s_bitmap_ino) + map);
110 if (!bh)
111 goto out;
112
113 set_bit(nr: bit, addr: (unsigned long *)bh->b_data);
114 mark_buffer_dirty(bh);
115 brelse(bh);
116 }
117 ret = 1;
118out:
119 mutex_unlock(lock: &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 */
130int 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(addr: sbi->s_imap[i], size: bits_per_entry,
146 offset: bit);
147
148 if (bit == bits_per_entry)
149 break;
150
151 run = count_run(addr: &sbi->s_imap[i], nbits: bits_per_entry,
152 addrlen: sbi->s_imap_size-i, bit, max: max_request);
153
154 if (run >= min_request)
155 goto found;
156 bit += run;
157 }
158 }
159 ret = -ENOSPC;
160 goto out;
161
162found:
163 *return_block = (u64) i * bits_per_entry + bit;
164 *return_size = run;
165 ret = set_run(sb, map: i, nbits: bits_per_entry, bit, count: run, set: 1);
166
167out:
168 mutex_unlock(lock: &sbi->s_bitmap_lock);
169 return ret;
170}
171
172/*
173 * Clears count bits starting at a given block.
174 */
175int 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, nbits: bits_per_entry, bit, count, set: 0);
192 mutex_unlock(lock: &sbi->s_bitmap_lock);
193 return ret;
194}
195

source code of linux/fs/omfs/bitmap.c