bitmap.c 8.7 KB

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