bitmap.c 6.8 KB

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