~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/affs/bitmap.c

Version: ~ [ linux-5.11-rc3 ] ~ [ linux-5.10.7 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.89 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.167 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.215 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.251 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.251 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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
 14 affs_count_free_blocks(struct super_block *sb)
 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
 38 affs_free_block(struct super_block *sb, u32 block)
 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 
 81         mark_buffer_dirty(bh);
 82         affs_mark_sb_dirty(sb);
 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
115 affs_alloc_block(struct inode *inode, u32 goal)
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 
244 int affs_init_bitmap(struct super_block *sb, int *flags)
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 
354 void affs_free_bitmap(struct super_block *sb)
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 }
367 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp