bitmap.c 6.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * linux/fs/minix/bitmap.c
  4. *
  5. * Copyright (C) 1991, 1992 Linus Torvalds
  6. */
  7. /*
  8. * Modified for 680x0 by Hamish Macdonald
  9. * Fixed for 680x0 by Andreas Schwab
  10. */
  11. /* bitmap.c contains the code that handles the inode and block bitmaps */
  12. #include "minix.h"
  13. #include <linux/buffer_head.h>
  14. #include <linux/bitops.h>
  15. #include <linux/sched.h>
  16. static DEFINE_SPINLOCK(bitmap_lock);
  17. /*
  18. * bitmap consists of blocks filled with 16bit words
  19. * bit set == busy, bit clear == free
  20. * endianness is a mess, but for counting zero bits it really doesn't matter...
  21. */
  22. static __u32 count_free(struct buffer_head *map[], unsigned blocksize, __u32 numbits)
  23. {
  24. __u32 sum = 0;
  25. unsigned blocks = DIV_ROUND_UP(numbits, blocksize * 8);
  26. while (blocks--) {
  27. unsigned words = blocksize / 2;
  28. __u16 *p = (__u16 *)(*map++)->b_data;
  29. while (words--)
  30. sum += 16 - hweight16(*p++);
  31. }
  32. return sum;
  33. }
  34. void minix_free_block(struct inode *inode, unsigned long block)
  35. {
  36. struct super_block *sb = inode->i_sb;
  37. struct minix_sb_info *sbi = minix_sb(sb);
  38. struct buffer_head *bh;
  39. int k = sb->s_blocksize_bits + 3;
  40. unsigned long bit, zone;
  41. if (block < sbi->s_firstdatazone || block >= sbi->s_nzones) {
  42. printk("Trying to free block not in datazone\n");
  43. return;
  44. }
  45. zone = block - sbi->s_firstdatazone + 1;
  46. bit = zone & ((1<<k) - 1);
  47. zone >>= k;
  48. if (zone >= sbi->s_zmap_blocks) {
  49. printk("minix_free_block: nonexistent bitmap buffer\n");
  50. return;
  51. }
  52. bh = sbi->s_zmap[zone];
  53. spin_lock(&bitmap_lock);
  54. if (!minix_test_and_clear_bit(bit, bh->b_data))
  55. printk("minix_free_block (%s:%lu): bit already cleared\n",
  56. sb->s_id, block);
  57. spin_unlock(&bitmap_lock);
  58. mark_buffer_dirty(bh);
  59. return;
  60. }
  61. int minix_new_block(struct inode * inode)
  62. {
  63. struct minix_sb_info *sbi = minix_sb(inode->i_sb);
  64. int bits_per_zone = 8 * inode->i_sb->s_blocksize;
  65. int i;
  66. for (i = 0; i < sbi->s_zmap_blocks; i++) {
  67. struct buffer_head *bh = sbi->s_zmap[i];
  68. int j;
  69. spin_lock(&bitmap_lock);
  70. j = minix_find_first_zero_bit(bh->b_data, bits_per_zone);
  71. if (j < bits_per_zone) {
  72. minix_set_bit(j, bh->b_data);
  73. spin_unlock(&bitmap_lock);
  74. mark_buffer_dirty(bh);
  75. j += i * bits_per_zone + sbi->s_firstdatazone-1;
  76. if (j < sbi->s_firstdatazone || j >= sbi->s_nzones)
  77. break;
  78. return j;
  79. }
  80. spin_unlock(&bitmap_lock);
  81. }
  82. return 0;
  83. }
  84. unsigned long minix_count_free_blocks(struct super_block *sb)
  85. {
  86. struct minix_sb_info *sbi = minix_sb(sb);
  87. u32 bits = sbi->s_nzones - sbi->s_firstdatazone + 1;
  88. return (count_free(sbi->s_zmap, sb->s_blocksize, bits)
  89. << sbi->s_log_zone_size);
  90. }
  91. struct minix_inode *
  92. minix_V1_raw_inode(struct super_block *sb, ino_t ino, struct buffer_head **bh)
  93. {
  94. int block;
  95. struct minix_sb_info *sbi = minix_sb(sb);
  96. struct minix_inode *p;
  97. if (!ino || ino > sbi->s_ninodes) {
  98. printk("Bad inode number on dev %s: %ld is out of range\n",
  99. sb->s_id, (long)ino);
  100. return NULL;
  101. }
  102. ino--;
  103. block = 2 + sbi->s_imap_blocks + sbi->s_zmap_blocks +
  104. ino / MINIX_INODES_PER_BLOCK;
  105. *bh = sb_bread(sb, block);
  106. if (!*bh) {
  107. printk("Unable to read inode block\n");
  108. return NULL;
  109. }
  110. p = (void *)(*bh)->b_data;
  111. return p + ino % MINIX_INODES_PER_BLOCK;
  112. }
  113. struct minix2_inode *
  114. minix_V2_raw_inode(struct super_block *sb, ino_t ino, struct buffer_head **bh)
  115. {
  116. int block;
  117. struct minix_sb_info *sbi = minix_sb(sb);
  118. struct minix2_inode *p;
  119. int minix2_inodes_per_block = sb->s_blocksize / sizeof(struct minix2_inode);
  120. *bh = NULL;
  121. if (!ino || ino > sbi->s_ninodes) {
  122. printk("Bad inode number on dev %s: %ld is out of range\n",
  123. sb->s_id, (long)ino);
  124. return NULL;
  125. }
  126. ino--;
  127. block = 2 + sbi->s_imap_blocks + sbi->s_zmap_blocks +
  128. ino / minix2_inodes_per_block;
  129. *bh = sb_bread(sb, block);
  130. if (!*bh) {
  131. printk("Unable to read inode block\n");
  132. return NULL;
  133. }
  134. p = (void *)(*bh)->b_data;
  135. return p + ino % minix2_inodes_per_block;
  136. }
  137. /* Clear the link count and mode of a deleted inode on disk. */
  138. static void minix_clear_inode(struct inode *inode)
  139. {
  140. struct buffer_head *bh = NULL;
  141. if (INODE_VERSION(inode) == MINIX_V1) {
  142. struct minix_inode *raw_inode;
  143. raw_inode = minix_V1_raw_inode(inode->i_sb, inode->i_ino, &bh);
  144. if (raw_inode) {
  145. raw_inode->i_nlinks = 0;
  146. raw_inode->i_mode = 0;
  147. }
  148. } else {
  149. struct minix2_inode *raw_inode;
  150. raw_inode = minix_V2_raw_inode(inode->i_sb, inode->i_ino, &bh);
  151. if (raw_inode) {
  152. raw_inode->i_nlinks = 0;
  153. raw_inode->i_mode = 0;
  154. }
  155. }
  156. if (bh) {
  157. mark_buffer_dirty(bh);
  158. brelse (bh);
  159. }
  160. }
  161. void minix_free_inode(struct inode * inode)
  162. {
  163. struct super_block *sb = inode->i_sb;
  164. struct minix_sb_info *sbi = minix_sb(inode->i_sb);
  165. struct buffer_head *bh;
  166. int k = sb->s_blocksize_bits + 3;
  167. unsigned long ino, bit;
  168. ino = inode->i_ino;
  169. if (ino < 1 || ino > sbi->s_ninodes) {
  170. printk("minix_free_inode: inode 0 or nonexistent inode\n");
  171. return;
  172. }
  173. bit = ino & ((1<<k) - 1);
  174. ino >>= k;
  175. if (ino >= sbi->s_imap_blocks) {
  176. printk("minix_free_inode: nonexistent imap in superblock\n");
  177. return;
  178. }
  179. minix_clear_inode(inode); /* clear on-disk copy */
  180. bh = sbi->s_imap[ino];
  181. spin_lock(&bitmap_lock);
  182. if (!minix_test_and_clear_bit(bit, bh->b_data))
  183. printk("minix_free_inode: bit %lu already cleared\n", bit);
  184. spin_unlock(&bitmap_lock);
  185. mark_buffer_dirty(bh);
  186. }
  187. struct inode *minix_new_inode(const struct inode *dir, umode_t mode, int *error)
  188. {
  189. struct super_block *sb = dir->i_sb;
  190. struct minix_sb_info *sbi = minix_sb(sb);
  191. struct inode *inode = new_inode(sb);
  192. struct buffer_head * bh;
  193. int bits_per_zone = 8 * sb->s_blocksize;
  194. unsigned long j;
  195. int i;
  196. if (!inode) {
  197. *error = -ENOMEM;
  198. return NULL;
  199. }
  200. j = bits_per_zone;
  201. bh = NULL;
  202. *error = -ENOSPC;
  203. spin_lock(&bitmap_lock);
  204. for (i = 0; i < sbi->s_imap_blocks; i++) {
  205. bh = sbi->s_imap[i];
  206. j = minix_find_first_zero_bit(bh->b_data, bits_per_zone);
  207. if (j < bits_per_zone)
  208. break;
  209. }
  210. if (!bh || j >= bits_per_zone) {
  211. spin_unlock(&bitmap_lock);
  212. iput(inode);
  213. return NULL;
  214. }
  215. if (minix_test_and_set_bit(j, bh->b_data)) { /* shouldn't happen */
  216. spin_unlock(&bitmap_lock);
  217. printk("minix_new_inode: bit already set\n");
  218. iput(inode);
  219. return NULL;
  220. }
  221. spin_unlock(&bitmap_lock);
  222. mark_buffer_dirty(bh);
  223. j += i * bits_per_zone;
  224. if (!j || j > sbi->s_ninodes) {
  225. iput(inode);
  226. return NULL;
  227. }
  228. inode_init_owner(inode, dir, mode);
  229. inode->i_ino = j;
  230. inode->i_mtime = inode->i_atime = inode->i_ctime = current_time(inode);
  231. inode->i_blocks = 0;
  232. memset(&minix_i(inode)->u, 0, sizeof(minix_i(inode)->u));
  233. insert_inode_hash(inode);
  234. mark_inode_dirty(inode);
  235. *error = 0;
  236. return inode;
  237. }
  238. unsigned long minix_count_free_inodes(struct super_block *sb)
  239. {
  240. struct minix_sb_info *sbi = minix_sb(sb);
  241. u32 bits = sbi->s_ninodes + 1;
  242. return count_free(sbi->s_imap, sb->s_blocksize, bits);
  243. }