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