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, (unsigned long *)bh->b_data);
75		} else {
76			clear_bit(bit, sbi->s_imap[map]);
77			clear_bit(bit, (unsigned 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 successful.
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	unsigned 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, (unsigned 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	unsigned int map, bit;
180	int ret;
181
182	tmp = block;
183	bit = do_div(tmp, bits_per_entry);
184	map = tmp;
185
186	if (map >= sbi->s_imap_size)
187		return 0;
188
189	mutex_lock(&sbi->s_bitmap_lock);
190	ret = set_run(sb, map, bits_per_entry, bit, count, 0);
191	mutex_unlock(&sbi->s_bitmap_lock);
192	return ret;
193}
194