1 /*
2 * linux/fs/affs/bitmap.c
3 *
4 * (c) 1996 Hans-Joachim Widmaier
5 *
6 * bitmap.c contains the code that handles all bitmap related stuff -
7 * block allocation, deallocation, calculation of free space.
8 */
9
10 #define DEBUG 0
11 #include <linux/sched.h>
12 #include <linux/affs_fs.h>
13 #include <linux/stat.h>
14 #include <linux/kernel.h>
15 #include <linux/string.h>
16 #include <linux/locks.h>
17 #include <linux/amigaffs.h>
18
19 #include <asm/bitops.h>
20
21 /* This is, of course, shamelessly stolen from fs/minix */
22
23 static int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
24
25 int
26 affs_count_free_bits(int blocksize, const char *data)
27 {
28 int free;
29 int i;
30
31 free = 0;
32 for (i = 0; i < blocksize; i++) {
33 free += nibblemap[data[i] & 0xF] + nibblemap[(data[i]>>4) & 0xF];
34 }
35
36 return free;
37 }
38
39 int
40 affs_count_free_blocks(struct super_block *s)
41 {
42 int free;
43 int i;
44
45 pr_debug("AFFS: count_free_blocks()\n");
46
47 free = 0;
48 if (s->u.affs_sb.s_flags & SF_BM_VALID) {
49 for (i = 0; i < s->u.affs_sb.s_num_az; i++) {
50 free += s->u.affs_sb.s_alloc[i].az_free;
51 }
52 }
53 return free;
54 }
55
56 void
57 affs_free_block(struct super_block *sb, s32 block)
58 {
59 int bmap;
60 int bit;
61 int blk;
62 int zone_no;
63 struct affs_bm_info *bm;
64
65 pr_debug("AFFS: free_block(%d)\n",block);
66
67 blk = block - sb->u.affs_sb.s_reserved;
68 bmap = blk / (sb->s_blocksize * 8 - 32);
69 bit = blk % (sb->s_blocksize * 8 - 32);
70 zone_no = (bmap << (sb->s_blocksize_bits - 7)) + bit / 1024;
71 bm = &sb->u.affs_sb.s_bitmap[bmap];
72 if (bmap >= sb->u.affs_sb.s_bm_count) {
73 affs_error(sb,"affs_free_block","Block %d outside partition",block);
74 return;
75 }
76 blk = 0;
77 set_bit(bit & 31,&blk);
78
79 lock_super(sb);
80 bm->bm_count++;
81 if (!bm->bm_bh) {
82 bm->bm_bh = affs_bread(sb->s_dev,bm->bm_key,sb->s_blocksize);
83 if (!bm->bm_bh) {
84 bm->bm_count--;
85 unlock_super(sb);
86 affs_error(sb,"affs_free_block","Cannot read bitmap block %d",bm->bm_key);
87 return;
88 }
89 }
90 if (test_and_set_bit(bit ^ BO_EXBITS,bm->bm_bh->b_data + 4))
91 affs_warning(sb,"affs_free_block","Trying to free block %d which is already free",
92 block);
93 else {
94 sb->u.affs_sb.s_alloc[zone_no].az_free++;
95 ((u32 *)bm->bm_bh->b_data)[0] = cpu_to_be32(be32_to_cpu(((u32 *)bm->bm_bh->b_data)[0]) - blk);
96 mark_buffer_dirty(bm->bm_bh);
97 sb->s_dirt = 1;
98 }
99 if (--bm->bm_count == 0) {
100 affs_brelse(bm->bm_bh);
101 bm->bm_bh = NULL;
102 }
103 unlock_super(sb);
104 }
105
106 /*
107 * Allocate a block in the given allocation zone.
108 * Since we have to byte-swap the bitmap on little-endian
109 * machines, this is rather expensive. Therefor we will
110 * preallocate up to 16 blocks from the same word, if
111 * possible. We are not doing preallocations in the
112 * header zone, though.
113 */
114
115 static s32
116 affs_balloc(struct inode *inode, int zone_no)
117 {
118 u32 w;
119 u32 *bm;
120 int fb;
121 int i;
122 int fwb;
123 s32 block;
124 struct affs_zone *zone;
125 struct affs_alloc_zone *az;
126 struct super_block *sb;
127
128 sb = inode->i_sb;
129 zone = &sb->u.affs_sb.s_zones[zone_no];
130
131 if (!zone->z_bm || !zone->z_bm->bm_bh)
132 return 0;
133
134 pr_debug("AFFS: balloc(inode=%lu,zone=%d)\n",inode->i_ino,zone_no);
135
136 az = &sb->u.affs_sb.s_alloc[zone->z_az_no];
137 bm = (u32 *)zone->z_bm->bm_bh->b_data;
138 repeat:
139 for (i = zone->z_start; i < zone->z_end; i++) {
140 if (bm[i])
141 goto found;
142 }
143 return 0;
144
145 found:
146 fwb = zone->z_bm->bm_firstblk + (i - 1) * 32;
147 lock_super(sb);
148 zone->z_start = i;
149 w = ~be32_to_cpu(bm[i]);
150 fb = find_first_zero_bit(&w,32);
151 if (fb > 31 || !test_and_clear_bit(fb ^ BO_EXBITS,&bm[i])) {
152 unlock_super(sb);
153 affs_warning(sb,"balloc","Empty block disappeared somehow");
154 goto repeat;
155 }
156 block = fwb + fb;
157 az->az_free--;
158
159 /* prealloc as much as possible within this word, but not in header zone */
160
161 if (zone_no) {
162 while (inode->u.affs_i.i_pa_cnt < AFFS_MAX_PREALLOC && ++fb < 32) {
163 fb = find_next_zero_bit(&w,32,fb);
164 if (fb > 31)
165 break;
166 if (!test_and_clear_bit(fb ^ BO_EXBITS,&bm[i])) {
167 affs_warning(sb,"balloc","Empty block disappeared somehow");
168 break;
169 }
170 inode->u.affs_i.i_data[inode->u.affs_i.i_pa_last++] = fwb + fb;
171 inode->u.affs_i.i_pa_last &= AFFS_MAX_PREALLOC - 1;
172 inode->u.affs_i.i_pa_cnt++;
173 az->az_free--;
174 }
175 }
176 w = ~w - be32_to_cpu(bm[i]);
177 bm[0] = cpu_to_be32(be32_to_cpu(bm[0]) + w);
178 unlock_super(sb);
179 mark_buffer_dirty(zone->z_bm->bm_bh);
180 sb->s_dirt = 1;
181 zone->z_lru_time = jiffies;
182
183 return block;
184 }
185
186 /* Find a new allocation zone, starting at zone_no. */
187
188 static int
189 affs_find_new_zone(struct super_block *sb, int zone_no)
190 {
191 struct affs_bm_info *bm;
192 struct affs_zone *zone;
193 struct affs_alloc_zone *az;
194 int bestfree;
195 int bestno;
196 int bestused;
197 int lusers;
198 int i;
199 int min;
200
201 pr_debug("AFFS: find_new_zone(zone_no=%d)\n",zone_no);
202
203 bestfree = 0;
204 bestused = -1;
205 bestno = -1;
206 lusers = MAX_ZONES;
207 min = zone_no ? AFFS_DATA_MIN_FREE : AFFS_HDR_MIN_FREE;
208 lock_super(sb);
209 zone = &sb->u.affs_sb.s_zones[zone_no];
210 i = zone->z_az_no;
211 az = &sb->u.affs_sb.s_alloc[i];
212 if (zone->z_bm && zone->z_bm->bm_count) {
213 if (--zone->z_bm->bm_count == 0) {
214 affs_brelse(zone->z_bm->bm_bh);
215 zone->z_bm->bm_bh = NULL;
216 }
217 if (az->az_count)
218 az->az_count--;
219 else
220 affs_error(sb,"find_new_zone","az_count=0, but bm used");
221
222 }
223 while (1) {
224 az = &sb->u.affs_sb.s_alloc[i];
225 if (!az->az_count) {
226 if (az->az_free > min) {
227 break;
228 }
229 if (az->az_free > bestfree) {
230 bestfree = az->az_free;
231 bestno = i;
232 }
233 } else if (az->az_free && az->az_count < lusers) {
234 lusers = az->az_count;
235 bestused = i;
236 }
237 if (++i >= sb->u.affs_sb.s_num_az)
238 i = 0;
239 if (i == zone->z_az_no) { /* Seen all */
240 if (bestno >= 0) {
241 i = bestno;
242 } else {
243 i = bestused;
244 }
245 break;
246 }
247 }
248 if (i < 0) {
249 /* Didn't find a single free block anywhere. */
250 unlock_super(sb);
251 return 0;
252 }
253 az = &sb->u.affs_sb.s_alloc[i];
254 az->az_count++;
255 bm = &sb->u.affs_sb.s_bitmap[i >> (sb->s_blocksize_bits - 7)];
256 bm->bm_count++;
257 if (!bm->bm_bh)
258 bm->bm_bh = affs_bread(sb->s_dev,bm->bm_key,sb->s_blocksize);
259 if (!bm->bm_bh) {
260 bm->bm_count--;
261 az->az_count--;
262 unlock_super(sb);
263 affs_error(sb,"find_new_zone","Cannot read bitmap");
264 return 0;
265 }
266 zone->z_bm = bm;
267 zone->z_start = (i & ((sb->s_blocksize / 128) - 1)) * 32 + 1;
268 zone->z_end = zone->z_start + az->az_size;
269 zone->z_az_no = i;
270 zone->z_lru_time = jiffies;
271 pr_debug("AFFS: found zone (%d) in bm %d at lw offset %d with %d free blocks\n",
272 i,(i >> (sb->s_blocksize_bits - 7)),zone->z_start,az->az_free);
273 unlock_super(sb);
274 return az->az_free;
275 }
276
277 /* Allocate a new header block. */
278
279 s32
280 affs_new_header(struct inode *inode)
281 {
282 s32 block;
283
284 pr_debug("AFFS: new_header(ino=%lu)\n",inode->i_ino);
285
286 if (!(block = affs_balloc(inode,0))) {
287 while (affs_find_new_zone(inode->i_sb,0)) {
288 if ((block = affs_balloc(inode,0)))
289 return block;
290 schedule();
291 }
292 return 0;
293 }
294 return block;
295 }
296
297 /* Allocate a new data block. */
298
299 s32
300 affs_new_data(struct inode *inode)
301 {
302 int empty, old;
303 unsigned long oldest;
304 struct affs_zone *zone;
305 struct super_block *sb;
306 int i = 0;
307 s32 block;
308
309 pr_debug("AFFS: new_data(ino=%lu)\n",inode->i_ino);
310
311 sb = inode->i_sb;
312 lock_super(sb);
313 if (inode->u.affs_i.i_pa_cnt) {
314 inode->u.affs_i.i_pa_cnt--;
315 unlock_super(sb);
316 block = inode->u.affs_i.i_data[inode->u.affs_i.i_pa_next++];
317 inode->u.affs_i.i_pa_next &= AFFS_MAX_PREALLOC - 1;
318 return block;
319 }
320 unlock_super(sb);
321 oldest = jiffies;
322 old = 0;
323 empty = 0;
324 zone = &sb->u.affs_sb.s_zones[inode->u.affs_i.i_zone];
325 if (zone->z_ino == inode->i_ino) {
326 i = inode->u.affs_i.i_zone;
327 goto found;
328 }
329 for (i = 1; i < MAX_ZONES; i++) {
330 zone = &sb->u.affs_sb.s_zones[i];
331 if (!empty && zone->z_bm && !zone->z_ino)
332 empty = i;
333 if (zone->z_bm && zone->z_lru_time < oldest) {
334 old = i;
335 oldest = zone->z_lru_time;
336 }
337 }
338 if (empty)
339 i = empty;
340 else if (old)
341 i = old;
342 else {
343 inode->u.affs_i.i_zone = 0;
344 return affs_new_header(inode);
345 }
346
347 inode->u.affs_i.i_zone = i;
348 zone->z_ino = inode->i_ino;
349
350 found:
351 zone = &sb->u.affs_sb.s_zones[i];
352 if (!(block = affs_balloc(inode,i))) { /* No data zones left */
353 while (affs_find_new_zone(sb,i)) {
354 if ((block = affs_balloc(inode,i)))
355 return block;
356 schedule();
357 }
358 inode->u.affs_i.i_zone = 0;
359 zone->z_ino = -1;
360 return 0;
361 }
362 return block;
363 }
364
365 void
366 affs_make_zones(struct super_block *sb)
367 {
368 int i, mid;
369
370 pr_debug("AFFS: make_zones(): num_zones=%d\n",sb->u.affs_sb.s_num_az);
371
372 mid = (sb->u.affs_sb.s_num_az + 1) / 2;
373 for (i = 0; i < MAX_ZONES; i++) {
374 sb->u.affs_sb.s_zones[i].z_az_no = mid;
375 affs_find_new_zone(sb,i);
376 }
377 }
378
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.