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

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

Version: ~ [ linux-5.10-rc6 ] ~ [ linux-5.9.12 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.81 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.161 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.210 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.247 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.247 ] ~ [ 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/hfs/bitmap.c
  3  *
  4  * Copyright (C) 1996-1997  Paul H. Hargrove
  5  * (C) 2003 Ardis Technologies <roman@ardistech.com>
  6  * This file may be distributed under the terms of the GNU General Public License.
  7  *
  8  * Based on GPLed code Copyright (C) 1995  Michael Dreher
  9  *
 10  * This file contains the code to modify the volume bitmap:
 11  * search/set/clear bits.
 12  */
 13 
 14 #include "hfs_fs.h"
 15 
 16 /*
 17  * hfs_find_zero_bit()
 18  *
 19  * Description:
 20  *  Given a block of memory, its length in bits, and a starting bit number,
 21  *  determine the number of the first zero bits (in left-to-right ordering)
 22  *  in that range.
 23  *
 24  *  Returns >= 'size' if no zero bits are found in the range.
 25  *
 26  *  Accesses memory in 32-bit aligned chunks of 32-bits and thus
 27  *  may read beyond the 'size'th bit.
 28  */
 29 static u32 hfs_find_set_zero_bits(__be32 *bitmap, u32 size, u32 offset, u32 *max)
 30 {
 31         __be32 *curr, *end;
 32         u32 mask, start, len, n;
 33         __be32 val;
 34         int i;
 35 
 36         len = *max;
 37         if (!len)
 38                 return size;
 39 
 40         curr = bitmap + (offset / 32);
 41         end = bitmap + ((size + 31) / 32);
 42 
 43         /* scan the first partial u32 for zero bits */
 44         val = *curr;
 45         if (~val) {
 46                 n = be32_to_cpu(val);
 47                 i = offset % 32;
 48                 mask = (1U << 31) >> i;
 49                 for (; i < 32; mask >>= 1, i++) {
 50                         if (!(n & mask))
 51                                 goto found;
 52                 }
 53         }
 54 
 55         /* scan complete u32s for the first zero bit */
 56         while (++curr < end) {
 57                 val = *curr;
 58                 if (~val) {
 59                         n = be32_to_cpu(val);
 60                         mask = 1 << 31;
 61                         for (i = 0; i < 32; mask >>= 1, i++) {
 62                                 if (!(n & mask))
 63                                         goto found;
 64                         }
 65                 }
 66         }
 67         return size;
 68 
 69 found:
 70         start = (curr - bitmap) * 32 + i;
 71         if (start >= size)
 72                 return start;
 73         /* do any partial u32 at the start */
 74         len = min(size - start, len);
 75         while (1) {
 76                 n |= mask;
 77                 if (++i >= 32)
 78                         break;
 79                 mask >>= 1;
 80                 if (!--len || n & mask)
 81                         goto done;
 82         }
 83         if (!--len)
 84                 goto done;
 85         *curr++ = cpu_to_be32(n);
 86         /* do full u32s */
 87         while (1) {
 88                 n = be32_to_cpu(*curr);
 89                 if (len < 32)
 90                         break;
 91                 if (n) {
 92                         len = 32;
 93                         break;
 94                 }
 95                 *curr++ = cpu_to_be32(0xffffffff);
 96                 len -= 32;
 97         }
 98         /* do any partial u32 at end */
 99         mask = 1U << 31;
100         for (i = 0; i < len; i++) {
101                 if (n & mask)
102                         break;
103                 n |= mask;
104                 mask >>= 1;
105         }
106 done:
107         *curr = cpu_to_be32(n);
108         *max = (curr - bitmap) * 32 + i - start;
109         return start;
110 }
111 
112 /*
113  * hfs_vbm_search_free()
114  *
115  * Description:
116  *   Search for 'num_bits' consecutive cleared bits in the bitmap blocks of
117  *   the hfs MDB. 'mdb' had better be locked or the returned range
118  *   may be no longer free, when this functions returns!
119  *   XXX Currently the search starts from bit 0, but it should start with
120  *   the bit number stored in 's_alloc_ptr' of the MDB.
121  * Input Variable(s):
122  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
123  *   u16 *num_bits: Pointer to the number of cleared bits
124  *     to search for
125  * Output Variable(s):
126  *   u16 *num_bits: The number of consecutive clear bits of the
127  *     returned range. If the bitmap is fragmented, this will be less than
128  *     requested and it will be zero, when the disk is full.
129  * Returns:
130  *   The number of the first bit of the range of cleared bits which has been
131  *   found. When 'num_bits' is zero, this is invalid!
132  * Preconditions:
133  *   'mdb' points to a "valid" (struct hfs_mdb).
134  *   'num_bits' points to a variable of type (u16), which contains
135  *      the number of cleared bits to find.
136  * Postconditions:
137  *   'num_bits' is set to the length of the found sequence.
138  */
139 u32 hfs_vbm_search_free(struct super_block *sb, u32 goal, u32 *num_bits)
140 {
141         void *bitmap;
142         u32 pos;
143 
144         /* make sure we have actual work to perform */
145         if (!*num_bits)
146                 return 0;
147 
148         mutex_lock(&HFS_SB(sb)->bitmap_lock);
149         bitmap = HFS_SB(sb)->bitmap;
150 
151         pos = hfs_find_set_zero_bits(bitmap, HFS_SB(sb)->fs_ablocks, goal, num_bits);
152         if (pos >= HFS_SB(sb)->fs_ablocks) {
153                 if (goal)
154                         pos = hfs_find_set_zero_bits(bitmap, goal, 0, num_bits);
155                 if (pos >= HFS_SB(sb)->fs_ablocks) {
156                         *num_bits = pos = 0;
157                         goto out;
158                 }
159         }
160 
161         hfs_dbg(BITMAP, "alloc_bits: %u,%u\n", pos, *num_bits);
162         HFS_SB(sb)->free_ablocks -= *num_bits;
163         hfs_bitmap_dirty(sb);
164 out:
165         mutex_unlock(&HFS_SB(sb)->bitmap_lock);
166         return pos;
167 }
168 
169 
170 /*
171  * hfs_clear_vbm_bits()
172  *
173  * Description:
174  *   Clear the requested bits in the volume bitmap of the hfs filesystem
175  * Input Variable(s):
176  *   struct hfs_mdb *mdb: Pointer to the hfs MDB
177  *   u16 start: The offset of the first bit
178  *   u16 count: The number of bits
179  * Output Variable(s):
180  *   None
181  * Returns:
182  *    0: no error
183  *   -1: One of the bits was already clear.  This is a strange
184  *       error and when it happens, the filesystem must be repaired!
185  *   -2: One or more of the bits are out of range of the bitmap.
186  * Preconditions:
187  *   'mdb' points to a "valid" (struct hfs_mdb).
188  * Postconditions:
189  *   Starting with bit number 'start', 'count' bits in the volume bitmap
190  *   are cleared. The affected bitmap blocks are marked "dirty", the free
191  *   block count of the MDB is updated and the MDB is marked dirty.
192  */
193 int hfs_clear_vbm_bits(struct super_block *sb, u16 start, u16 count)
194 {
195         __be32 *curr;
196         u32 mask;
197         int i, len;
198 
199         /* is there any actual work to be done? */
200         if (!count)
201                 return 0;
202 
203         hfs_dbg(BITMAP, "clear_bits: %u,%u\n", start, count);
204         /* are all of the bits in range? */
205         if ((start + count) > HFS_SB(sb)->fs_ablocks)
206                 return -2;
207 
208         mutex_lock(&HFS_SB(sb)->bitmap_lock);
209         /* bitmap is always on a 32-bit boundary */
210         curr = HFS_SB(sb)->bitmap + (start / 32);
211         len = count;
212 
213         /* do any partial u32 at the start */
214         i = start % 32;
215         if (i) {
216                 int j = 32 - i;
217                 mask = 0xffffffffU << j;
218                 if (j > count) {
219                         mask |= 0xffffffffU >> (i + count);
220                         *curr &= cpu_to_be32(mask);
221                         goto out;
222                 }
223                 *curr++ &= cpu_to_be32(mask);
224                 count -= j;
225         }
226 
227         /* do full u32s */
228         while (count >= 32) {
229                 *curr++ = 0;
230                 count -= 32;
231         }
232         /* do any partial u32 at end */
233         if (count) {
234                 mask = 0xffffffffU >> count;
235                 *curr &= cpu_to_be32(mask);
236         }
237 out:
238         HFS_SB(sb)->free_ablocks += len;
239         mutex_unlock(&HFS_SB(sb)->bitmap_lock);
240         hfs_bitmap_dirty(sb);
241 
242         return 0;
243 }
244 

~ [ 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