Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
bitmap.c
Go to the documentation of this file.
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 #include <linux/slab.h>
11 #include "affs.h"
12 
13 u32
15 {
16  struct affs_bm_info *bm;
17  u32 free;
18  int i;
19 
20  pr_debug("AFFS: count_free_blocks()\n");
21 
22  if (sb->s_flags & MS_RDONLY)
23  return 0;
24 
25  mutex_lock(&AFFS_SB(sb)->s_bmlock);
26 
27  bm = AFFS_SB(sb)->s_bitmap;
28  free = 0;
29  for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
30  free += bm->bm_free;
31 
32  mutex_unlock(&AFFS_SB(sb)->s_bmlock);
33 
34  return free;
35 }
36 
37 void
39 {
40  struct affs_sb_info *sbi = AFFS_SB(sb);
41  struct affs_bm_info *bm;
42  struct buffer_head *bh;
43  u32 blk, bmap, bit, mask, tmp;
44  __be32 *data;
45 
46  pr_debug("AFFS: free_block(%u)\n", block);
47 
48  if (block > sbi->s_partition_size)
49  goto err_range;
50 
51  blk = block - sbi->s_reserved;
52  bmap = blk / sbi->s_bmap_bits;
53  bit = blk % sbi->s_bmap_bits;
54  bm = &sbi->s_bitmap[bmap];
55 
56  mutex_lock(&sbi->s_bmlock);
57 
58  bh = sbi->s_bmap_bh;
59  if (sbi->s_last_bmap != bmap) {
60  affs_brelse(bh);
61  bh = affs_bread(sb, bm->bm_key);
62  if (!bh)
63  goto err_bh_read;
64  sbi->s_bmap_bh = bh;
65  sbi->s_last_bmap = bmap;
66  }
67 
68  mask = 1 << (bit & 31);
69  data = (__be32 *)bh->b_data + bit / 32 + 1;
70 
71  /* mark block free */
72  tmp = be32_to_cpu(*data);
73  if (tmp & mask)
74  goto err_free;
75  *data = cpu_to_be32(tmp | mask);
76 
77  /* fix checksum */
78  tmp = be32_to_cpu(*(__be32 *)bh->b_data);
79  *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
80 
83  bm->bm_free++;
84 
85  mutex_unlock(&sbi->s_bmlock);
86  return;
87 
88 err_free:
89  affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
90  mutex_unlock(&sbi->s_bmlock);
91  return;
92 
93 err_bh_read:
94  affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
95  sbi->s_bmap_bh = NULL;
96  sbi->s_last_bmap = ~0;
97  mutex_unlock(&sbi->s_bmlock);
98  return;
99 
100 err_range:
101  affs_error(sb, "affs_free_block","Block %u outside partition", block);
102  return;
103 }
104 
105 /*
106  * Allocate a block in the given allocation zone.
107  * Since we have to byte-swap the bitmap on little-endian
108  * machines, this is rather expensive. Therefore we will
109  * preallocate up to 16 blocks from the same word, if
110  * possible. We are not doing preallocations in the
111  * header zone, though.
112  */
113 
114 u32
116 {
117  struct super_block *sb;
118  struct affs_sb_info *sbi;
119  struct affs_bm_info *bm;
120  struct buffer_head *bh;
121  __be32 *data, *enddata;
122  u32 blk, bmap, bit, mask, mask2, tmp;
123  int i;
124 
125  sb = inode->i_sb;
126  sbi = AFFS_SB(sb);
127 
128  pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
129 
130  if (AFFS_I(inode)->i_pa_cnt) {
131  pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
132  AFFS_I(inode)->i_pa_cnt--;
133  return ++AFFS_I(inode)->i_lastalloc;
134  }
135 
136  if (!goal || goal > sbi->s_partition_size) {
137  if (goal)
138  affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
139  //if (!AFFS_I(inode)->i_last_block)
140  // affs_warning(sb, "affs_balloc", "no last alloc block");
141  goal = sbi->s_reserved;
142  }
143 
144  blk = goal - sbi->s_reserved;
145  bmap = blk / sbi->s_bmap_bits;
146  bm = &sbi->s_bitmap[bmap];
147 
148  mutex_lock(&sbi->s_bmlock);
149 
150  if (bm->bm_free)
151  goto find_bmap_bit;
152 
153 find_bmap:
154  /* search for the next bmap buffer with free bits */
155  i = sbi->s_bmap_count;
156  do {
157  if (--i < 0)
158  goto err_full;
159  bmap++;
160  bm++;
161  if (bmap < sbi->s_bmap_count)
162  continue;
163  /* restart search at zero */
164  bmap = 0;
165  bm = sbi->s_bitmap;
166  } while (!bm->bm_free);
167  blk = bmap * sbi->s_bmap_bits;
168 
169 find_bmap_bit:
170 
171  bh = sbi->s_bmap_bh;
172  if (sbi->s_last_bmap != bmap) {
173  affs_brelse(bh);
174  bh = affs_bread(sb, bm->bm_key);
175  if (!bh)
176  goto err_bh_read;
177  sbi->s_bmap_bh = bh;
178  sbi->s_last_bmap = bmap;
179  }
180 
181  /* find an unused block in this bitmap block */
182  bit = blk % sbi->s_bmap_bits;
183  data = (__be32 *)bh->b_data + bit / 32 + 1;
184  enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
185  mask = ~0UL << (bit & 31);
186  blk &= ~31UL;
187 
188  tmp = be32_to_cpu(*data);
189  if (tmp & mask)
190  goto find_bit;
191 
192  /* scan the rest of the buffer */
193  do {
194  blk += 32;
195  if (++data >= enddata)
196  /* didn't find something, can only happen
197  * if scan didn't start at 0, try next bmap
198  */
199  goto find_bmap;
200  } while (!*data);
201  tmp = be32_to_cpu(*data);
202  mask = ~0;
203 
204 find_bit:
205  /* finally look for a free bit in the word */
206  bit = ffs(tmp & mask) - 1;
207  blk += bit + sbi->s_reserved;
208  mask2 = mask = 1 << (bit & 31);
209  AFFS_I(inode)->i_lastalloc = blk;
210 
211  /* prealloc as much as possible within this word */
212  while ((mask2 <<= 1)) {
213  if (!(tmp & mask2))
214  break;
215  AFFS_I(inode)->i_pa_cnt++;
216  mask |= mask2;
217  }
218  bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
219 
220  *data = cpu_to_be32(tmp & ~mask);
221 
222  /* fix checksum */
223  tmp = be32_to_cpu(*(__be32 *)bh->b_data);
224  *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
225 
226  mark_buffer_dirty(bh);
227  affs_mark_sb_dirty(sb);
228 
229  mutex_unlock(&sbi->s_bmlock);
230 
231  pr_debug("%d\n", blk);
232  return blk;
233 
234 err_bh_read:
235  affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
236  sbi->s_bmap_bh = NULL;
237  sbi->s_last_bmap = ~0;
238 err_full:
239  mutex_unlock(&sbi->s_bmlock);
240  pr_debug("failed\n");
241  return 0;
242 }
243 
245 {
246  struct affs_bm_info *bm;
247  struct buffer_head *bmap_bh = NULL, *bh = NULL;
248  __be32 *bmap_blk;
249  u32 size, blk, end, offset, mask;
250  int i, res = 0;
251  struct affs_sb_info *sbi = AFFS_SB(sb);
252 
253  if (*flags & MS_RDONLY)
254  return 0;
255 
256  if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
257  printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
258  sb->s_id);
259  *flags |= MS_RDONLY;
260  return 0;
261  }
262 
263  sbi->s_last_bmap = ~0;
264  sbi->s_bmap_bh = NULL;
265  sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
266  sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
267  sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
268  size = sbi->s_bmap_count * sizeof(*bm);
269  bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
270  if (!sbi->s_bitmap) {
271  printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
272  return -ENOMEM;
273  }
274 
275  bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
276  blk = sb->s_blocksize / 4 - 49;
277  end = blk + 25;
278 
279  for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
280  affs_brelse(bh);
281 
282  bm->bm_key = be32_to_cpu(bmap_blk[blk]);
283  bh = affs_bread(sb, bm->bm_key);
284  if (!bh) {
285  printk(KERN_ERR "AFFS: Cannot read bitmap\n");
286  res = -EIO;
287  goto out;
288  }
289  if (affs_checksum_block(sb, bh)) {
290  printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
291  bm->bm_key, sb->s_id);
292  *flags |= MS_RDONLY;
293  goto out;
294  }
295  pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
296  bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
297 
298  /* Don't try read the extension if this is the last block,
299  * but we also need the right bm pointer below
300  */
301  if (++blk < end || i == 1)
302  continue;
303  if (bmap_bh)
304  affs_brelse(bmap_bh);
305  bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
306  if (!bmap_bh) {
307  printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
308  res = -EIO;
309  goto out;
310  }
311  bmap_blk = (__be32 *)bmap_bh->b_data;
312  blk = 0;
313  end = sb->s_blocksize / 4 - 1;
314  }
315 
316  offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
317  mask = ~(0xFFFFFFFFU << (offset & 31));
318  pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
319  offset = offset / 32 + 1;
320 
321  if (mask) {
322  u32 old, new;
323 
324  /* Mark unused bits in the last word as allocated */
325  old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
326  new = old & mask;
327  //if (old != new) {
328  ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
329  /* fix checksum */
330  //new -= old;
331  //old = be32_to_cpu(*(__be32 *)bh->b_data);
332  //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
333  //mark_buffer_dirty(bh);
334  //}
335  /* correct offset for the bitmap count below */
336  //offset++;
337  }
338  while (++offset < sb->s_blocksize / 4)
339  ((__be32 *)bh->b_data)[offset] = 0;
340  ((__be32 *)bh->b_data)[0] = 0;
341  ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
342  mark_buffer_dirty(bh);
343 
344  /* recalculate bitmap count for last block */
345  bm--;
346  bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
347 
348 out:
349  affs_brelse(bh);
350  affs_brelse(bmap_bh);
351  return res;
352 }
353 
355 {
356  struct affs_sb_info *sbi = AFFS_SB(sb);
357 
358  if (!sbi->s_bitmap)
359  return;
360 
361  affs_brelse(sbi->s_bmap_bh);
362  sbi->s_bmap_bh = NULL;
363  sbi->s_last_bmap = ~0;
364  kfree(sbi->s_bitmap);
365  sbi->s_bitmap = NULL;
366 }