bitmap.c 5.8 KB

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