bitmap.c 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220
  1. /*
  2. * linux/fs/hfsplus/bitmap.c
  3. *
  4. * Copyright (C) 2001
  5. * Brad Boyer (flar@allandria.com)
  6. * (C) 2003 Ardis Technologies <roman@ardistech.com>
  7. *
  8. * Handling of allocation file
  9. */
  10. #include <linux/pagemap.h>
  11. #include "hfsplus_fs.h"
  12. #include "hfsplus_raw.h"
  13. #define PAGE_CACHE_BITS (PAGE_CACHE_SIZE * 8)
  14. int hfsplus_block_allocate(struct super_block *sb, u32 size, u32 offset, u32 *max)
  15. {
  16. struct page *page;
  17. struct address_space *mapping;
  18. __be32 *pptr, *curr, *end;
  19. u32 mask, start, len, n;
  20. __be32 val;
  21. int i;
  22. len = *max;
  23. if (!len)
  24. return size;
  25. dprint(DBG_BITMAP, "block_allocate: %u,%u,%u\n", size, offset, len);
  26. mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
  27. mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
  28. page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
  29. pptr = kmap(page);
  30. curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
  31. i = offset % 32;
  32. offset &= ~(PAGE_CACHE_BITS - 1);
  33. if ((size ^ offset) / PAGE_CACHE_BITS)
  34. end = pptr + PAGE_CACHE_BITS / 32;
  35. else
  36. end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
  37. /* scan the first partial u32 for zero bits */
  38. val = *curr;
  39. if (~val) {
  40. n = be32_to_cpu(val);
  41. mask = (1U << 31) >> i;
  42. for (; i < 32; mask >>= 1, i++) {
  43. if (!(n & mask))
  44. goto found;
  45. }
  46. }
  47. curr++;
  48. /* scan complete u32s for the first zero bit */
  49. while (1) {
  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. curr++;
  61. }
  62. kunmap(page);
  63. offset += PAGE_CACHE_BITS;
  64. if (offset >= size)
  65. break;
  66. page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
  67. NULL);
  68. curr = pptr = kmap(page);
  69. if ((size ^ offset) / PAGE_CACHE_BITS)
  70. end = pptr + PAGE_CACHE_BITS / 32;
  71. else
  72. end = pptr + ((size + 31) & (PAGE_CACHE_BITS - 1)) / 32;
  73. }
  74. dprint(DBG_BITMAP, "bitmap full\n");
  75. start = size;
  76. goto out;
  77. found:
  78. start = offset + (curr - pptr) * 32 + i;
  79. if (start >= size) {
  80. dprint(DBG_BITMAP, "bitmap full\n");
  81. goto out;
  82. }
  83. /* do any partial u32 at the start */
  84. len = min(size - start, len);
  85. while (1) {
  86. n |= mask;
  87. if (++i >= 32)
  88. break;
  89. mask >>= 1;
  90. if (!--len || n & mask)
  91. goto done;
  92. }
  93. if (!--len)
  94. goto done;
  95. *curr++ = cpu_to_be32(n);
  96. /* do full u32s */
  97. while (1) {
  98. while (curr < end) {
  99. n = be32_to_cpu(*curr);
  100. if (len < 32)
  101. goto last;
  102. if (n) {
  103. len = 32;
  104. goto last;
  105. }
  106. *curr++ = cpu_to_be32(0xffffffff);
  107. len -= 32;
  108. }
  109. set_page_dirty(page);
  110. kunmap(page);
  111. offset += PAGE_CACHE_BITS;
  112. page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS,
  113. NULL);
  114. pptr = kmap(page);
  115. curr = pptr;
  116. end = pptr + PAGE_CACHE_BITS / 32;
  117. }
  118. last:
  119. /* do any partial u32 at end */
  120. mask = 1U << 31;
  121. for (i = 0; i < len; i++) {
  122. if (n & mask)
  123. break;
  124. n |= mask;
  125. mask >>= 1;
  126. }
  127. done:
  128. *curr = cpu_to_be32(n);
  129. set_page_dirty(page);
  130. kunmap(page);
  131. *max = offset + (curr - pptr) * 32 + i - start;
  132. HFSPLUS_SB(sb).free_blocks -= *max;
  133. sb->s_dirt = 1;
  134. dprint(DBG_BITMAP, "-> %u,%u\n", start, *max);
  135. out:
  136. mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
  137. return start;
  138. }
  139. int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
  140. {
  141. struct page *page;
  142. struct address_space *mapping;
  143. __be32 *pptr, *curr, *end;
  144. u32 mask, len, pnr;
  145. int i;
  146. /* is there any actual work to be done? */
  147. if (!count)
  148. return 0;
  149. dprint(DBG_BITMAP, "block_free: %u,%u\n", offset, count);
  150. /* are all of the bits in range? */
  151. if ((offset + count) > HFSPLUS_SB(sb).total_blocks)
  152. return -2;
  153. mutex_lock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
  154. mapping = HFSPLUS_SB(sb).alloc_file->i_mapping;
  155. pnr = offset / PAGE_CACHE_BITS;
  156. page = read_mapping_page(mapping, pnr, NULL);
  157. pptr = kmap(page);
  158. curr = pptr + (offset & (PAGE_CACHE_BITS - 1)) / 32;
  159. end = pptr + PAGE_CACHE_BITS / 32;
  160. len = count;
  161. /* do any partial u32 at the start */
  162. i = offset % 32;
  163. if (i) {
  164. int j = 32 - i;
  165. mask = 0xffffffffU << j;
  166. if (j > count) {
  167. mask |= 0xffffffffU >> (i + count);
  168. *curr++ &= cpu_to_be32(mask);
  169. goto out;
  170. }
  171. *curr++ &= cpu_to_be32(mask);
  172. count -= j;
  173. }
  174. /* do full u32s */
  175. while (1) {
  176. while (curr < end) {
  177. if (count < 32)
  178. goto done;
  179. *curr++ = 0;
  180. count -= 32;
  181. }
  182. if (!count)
  183. break;
  184. set_page_dirty(page);
  185. kunmap(page);
  186. page = read_mapping_page(mapping, ++pnr, NULL);
  187. pptr = kmap(page);
  188. curr = pptr;
  189. end = pptr + PAGE_CACHE_BITS / 32;
  190. }
  191. done:
  192. /* do any partial u32 at end */
  193. if (count) {
  194. mask = 0xffffffffU >> count;
  195. *curr &= cpu_to_be32(mask);
  196. }
  197. out:
  198. set_page_dirty(page);
  199. kunmap(page);
  200. HFSPLUS_SB(sb).free_blocks += len;
  201. sb->s_dirt = 1;
  202. mutex_unlock(&HFSPLUS_SB(sb).alloc_file->i_mutex);
  203. return 0;
  204. }