bitmap.c 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * linux/fs/affs/bitmap.c
  4. *
  5. * (c) 1996 Hans-Joachim Widmaier
  6. *
  7. * bitmap.c contains the code that handles all bitmap related stuff -
  8. * block allocation, deallocation, calculation of free space.
  9. */
  10. #include <linux/slab.h>
  11. #include "affs.h"
  12. u32
  13. affs_count_free_blocks(struct super_block *sb)
  14. {
  15. struct affs_bm_info *bm;
  16. u32 free;
  17. int i;
  18. pr_debug("%s()\n", __func__);
  19. if (sb_rdonly(sb))
  20. return 0;
  21. mutex_lock(&AFFS_SB(sb)->s_bmlock);
  22. bm = AFFS_SB(sb)->s_bitmap;
  23. free = 0;
  24. for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
  25. free += bm->bm_free;
  26. mutex_unlock(&AFFS_SB(sb)->s_bmlock);
  27. return free;
  28. }
  29. void
  30. affs_free_block(struct super_block *sb, u32 block)
  31. {
  32. struct affs_sb_info *sbi = AFFS_SB(sb);
  33. struct affs_bm_info *bm;
  34. struct buffer_head *bh;
  35. u32 blk, bmap, bit, mask, tmp;
  36. __be32 *data;
  37. pr_debug("%s(%u)\n", __func__, block);
  38. if (block > sbi->s_partition_size)
  39. goto err_range;
  40. blk = block - sbi->s_reserved;
  41. bmap = blk / sbi->s_bmap_bits;
  42. bit = blk % sbi->s_bmap_bits;
  43. bm = &sbi->s_bitmap[bmap];
  44. mutex_lock(&sbi->s_bmlock);
  45. bh = sbi->s_bmap_bh;
  46. if (sbi->s_last_bmap != bmap) {
  47. affs_brelse(bh);
  48. bh = affs_bread(sb, bm->bm_key);
  49. if (!bh)
  50. goto err_bh_read;
  51. sbi->s_bmap_bh = bh;
  52. sbi->s_last_bmap = bmap;
  53. }
  54. mask = 1 << (bit & 31);
  55. data = (__be32 *)bh->b_data + bit / 32 + 1;
  56. /* mark block free */
  57. tmp = be32_to_cpu(*data);
  58. if (tmp & mask)
  59. goto err_free;
  60. *data = cpu_to_be32(tmp | mask);
  61. /* fix checksum */
  62. tmp = be32_to_cpu(*(__be32 *)bh->b_data);
  63. *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
  64. mark_buffer_dirty(bh);
  65. affs_mark_sb_dirty(sb);
  66. bm->bm_free++;
  67. mutex_unlock(&sbi->s_bmlock);
  68. return;
  69. err_free:
  70. affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
  71. mutex_unlock(&sbi->s_bmlock);
  72. return;
  73. err_bh_read:
  74. affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
  75. sbi->s_bmap_bh = NULL;
  76. sbi->s_last_bmap = ~0;
  77. mutex_unlock(&sbi->s_bmlock);
  78. return;
  79. err_range:
  80. affs_error(sb, "affs_free_block","Block %u outside partition", block);
  81. }
  82. /*
  83. * Allocate a block in the given allocation zone.
  84. * Since we have to byte-swap the bitmap on little-endian
  85. * machines, this is rather expensive. Therefore we will
  86. * preallocate up to 16 blocks from the same word, if
  87. * possible. We are not doing preallocations in the
  88. * header zone, though.
  89. */
  90. u32
  91. affs_alloc_block(struct inode *inode, u32 goal)
  92. {
  93. struct super_block *sb;
  94. struct affs_sb_info *sbi;
  95. struct affs_bm_info *bm;
  96. struct buffer_head *bh;
  97. __be32 *data, *enddata;
  98. u32 blk, bmap, bit, mask, mask2, tmp;
  99. int i;
  100. sb = inode->i_sb;
  101. sbi = AFFS_SB(sb);
  102. pr_debug("balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
  103. if (AFFS_I(inode)->i_pa_cnt) {
  104. pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
  105. AFFS_I(inode)->i_pa_cnt--;
  106. return ++AFFS_I(inode)->i_lastalloc;
  107. }
  108. if (!goal || goal > sbi->s_partition_size) {
  109. if (goal)
  110. affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
  111. //if (!AFFS_I(inode)->i_last_block)
  112. // affs_warning(sb, "affs_balloc", "no last alloc block");
  113. goal = sbi->s_reserved;
  114. }
  115. blk = goal - sbi->s_reserved;
  116. bmap = blk / sbi->s_bmap_bits;
  117. bm = &sbi->s_bitmap[bmap];
  118. mutex_lock(&sbi->s_bmlock);
  119. if (bm->bm_free)
  120. goto find_bmap_bit;
  121. find_bmap:
  122. /* search for the next bmap buffer with free bits */
  123. i = sbi->s_bmap_count;
  124. do {
  125. if (--i < 0)
  126. goto err_full;
  127. bmap++;
  128. bm++;
  129. if (bmap < sbi->s_bmap_count)
  130. continue;
  131. /* restart search at zero */
  132. bmap = 0;
  133. bm = sbi->s_bitmap;
  134. } while (!bm->bm_free);
  135. blk = bmap * sbi->s_bmap_bits;
  136. find_bmap_bit:
  137. bh = sbi->s_bmap_bh;
  138. if (sbi->s_last_bmap != bmap) {
  139. affs_brelse(bh);
  140. bh = affs_bread(sb, bm->bm_key);
  141. if (!bh)
  142. goto err_bh_read;
  143. sbi->s_bmap_bh = bh;
  144. sbi->s_last_bmap = bmap;
  145. }
  146. /* find an unused block in this bitmap block */
  147. bit = blk % sbi->s_bmap_bits;
  148. data = (__be32 *)bh->b_data + bit / 32 + 1;
  149. enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
  150. mask = ~0UL << (bit & 31);
  151. blk &= ~31UL;
  152. tmp = be32_to_cpu(*data);
  153. if (tmp & mask)
  154. goto find_bit;
  155. /* scan the rest of the buffer */
  156. do {
  157. blk += 32;
  158. if (++data >= enddata)
  159. /* didn't find something, can only happen
  160. * if scan didn't start at 0, try next bmap
  161. */
  162. goto find_bmap;
  163. } while (!*data);
  164. tmp = be32_to_cpu(*data);
  165. mask = ~0;
  166. find_bit:
  167. /* finally look for a free bit in the word */
  168. bit = ffs(tmp & mask) - 1;
  169. blk += bit + sbi->s_reserved;
  170. mask2 = mask = 1 << (bit & 31);
  171. AFFS_I(inode)->i_lastalloc = blk;
  172. /* prealloc as much as possible within this word */
  173. while ((mask2 <<= 1)) {
  174. if (!(tmp & mask2))
  175. break;
  176. AFFS_I(inode)->i_pa_cnt++;
  177. mask |= mask2;
  178. }
  179. bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
  180. *data = cpu_to_be32(tmp & ~mask);
  181. /* fix checksum */
  182. tmp = be32_to_cpu(*(__be32 *)bh->b_data);
  183. *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
  184. mark_buffer_dirty(bh);
  185. affs_mark_sb_dirty(sb);
  186. mutex_unlock(&sbi->s_bmlock);
  187. pr_debug("%d\n", blk);
  188. return blk;
  189. err_bh_read:
  190. affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
  191. sbi->s_bmap_bh = NULL;
  192. sbi->s_last_bmap = ~0;
  193. err_full:
  194. mutex_unlock(&sbi->s_bmlock);
  195. pr_debug("failed\n");
  196. return 0;
  197. }
  198. int affs_init_bitmap(struct super_block *sb, int *flags)
  199. {
  200. struct affs_bm_info *bm;
  201. struct buffer_head *bmap_bh = NULL, *bh = NULL;
  202. __be32 *bmap_blk;
  203. u32 size, blk, end, offset, mask;
  204. int i, res = 0;
  205. struct affs_sb_info *sbi = AFFS_SB(sb);
  206. if (*flags & SB_RDONLY)
  207. return 0;
  208. if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
  209. pr_notice("Bitmap invalid - mounting %s read only\n", sb->s_id);
  210. *flags |= SB_RDONLY;
  211. return 0;
  212. }
  213. sbi->s_last_bmap = ~0;
  214. sbi->s_bmap_bh = NULL;
  215. sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
  216. sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
  217. sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
  218. size = sbi->s_bmap_count * sizeof(*bm);
  219. bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
  220. if (!sbi->s_bitmap) {
  221. pr_err("Bitmap allocation failed\n");
  222. return -ENOMEM;
  223. }
  224. bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
  225. blk = sb->s_blocksize / 4 - 49;
  226. end = blk + 25;
  227. for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
  228. affs_brelse(bh);
  229. bm->bm_key = be32_to_cpu(bmap_blk[blk]);
  230. bh = affs_bread(sb, bm->bm_key);
  231. if (!bh) {
  232. pr_err("Cannot read bitmap\n");
  233. res = -EIO;
  234. goto out;
  235. }
  236. if (affs_checksum_block(sb, bh)) {
  237. pr_warn("Bitmap %u invalid - mounting %s read only.\n",
  238. bm->bm_key, sb->s_id);
  239. *flags |= SB_RDONLY;
  240. goto out;
  241. }
  242. pr_debug("read bitmap block %d: %d\n", blk, bm->bm_key);
  243. bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
  244. /* Don't try read the extension if this is the last block,
  245. * but we also need the right bm pointer below
  246. */
  247. if (++blk < end || i == 1)
  248. continue;
  249. if (bmap_bh)
  250. affs_brelse(bmap_bh);
  251. bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
  252. if (!bmap_bh) {
  253. pr_err("Cannot read bitmap extension\n");
  254. res = -EIO;
  255. goto out;
  256. }
  257. bmap_blk = (__be32 *)bmap_bh->b_data;
  258. blk = 0;
  259. end = sb->s_blocksize / 4 - 1;
  260. }
  261. offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
  262. mask = ~(0xFFFFFFFFU << (offset & 31));
  263. pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
  264. offset = offset / 32 + 1;
  265. if (mask) {
  266. u32 old, new;
  267. /* Mark unused bits in the last word as allocated */
  268. old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
  269. new = old & mask;
  270. //if (old != new) {
  271. ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
  272. /* fix checksum */
  273. //new -= old;
  274. //old = be32_to_cpu(*(__be32 *)bh->b_data);
  275. //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
  276. //mark_buffer_dirty(bh);
  277. //}
  278. /* correct offset for the bitmap count below */
  279. //offset++;
  280. }
  281. while (++offset < sb->s_blocksize / 4)
  282. ((__be32 *)bh->b_data)[offset] = 0;
  283. ((__be32 *)bh->b_data)[0] = 0;
  284. ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
  285. mark_buffer_dirty(bh);
  286. /* recalculate bitmap count for last block */
  287. bm--;
  288. bm->bm_free = memweight(bh->b_data + 4, sb->s_blocksize - 4);
  289. out:
  290. affs_brelse(bh);
  291. affs_brelse(bmap_bh);
  292. return res;
  293. }
  294. void affs_free_bitmap(struct super_block *sb)
  295. {
  296. struct affs_sb_info *sbi = AFFS_SB(sb);
  297. if (!sbi->s_bitmap)
  298. return;
  299. affs_brelse(sbi->s_bmap_bh);
  300. sbi->s_bmap_bh = NULL;
  301. sbi->s_last_bmap = ~0;
  302. kfree(sbi->s_bitmap);
  303. sbi->s_bitmap = NULL;
  304. }