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