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