Pull misc-for-upstream into release branch
[linux-2.6] / fs / minix / itree_common.c
1 /* Generic part */
2
3 typedef struct {
4         block_t *p;
5         block_t key;
6         struct buffer_head *bh;
7 } Indirect;
8
9 static DEFINE_RWLOCK(pointers_lock);
10
11 static inline void add_chain(Indirect *p, struct buffer_head *bh, block_t *v)
12 {
13         p->key = *(p->p = v);
14         p->bh = bh;
15 }
16
17 static inline int verify_chain(Indirect *from, Indirect *to)
18 {
19         while (from <= to && from->key == *from->p)
20                 from++;
21         return (from > to);
22 }
23
24 static inline block_t *block_end(struct buffer_head *bh)
25 {
26         return (block_t *)((char*)bh->b_data + bh->b_size);
27 }
28
29 static inline Indirect *get_branch(struct inode *inode,
30                                         int depth,
31                                         int *offsets,
32                                         Indirect chain[DEPTH],
33                                         int *err)
34 {
35         struct super_block *sb = inode->i_sb;
36         Indirect *p = chain;
37         struct buffer_head *bh;
38
39         *err = 0;
40         /* i_data is not going away, no lock needed */
41         add_chain (chain, NULL, i_data(inode) + *offsets);
42         if (!p->key)
43                 goto no_block;
44         while (--depth) {
45                 bh = sb_bread(sb, block_to_cpu(p->key));
46                 if (!bh)
47                         goto failure;
48                 read_lock(&pointers_lock);
49                 if (!verify_chain(chain, p))
50                         goto changed;
51                 add_chain(++p, bh, (block_t *)bh->b_data + *++offsets);
52                 read_unlock(&pointers_lock);
53                 if (!p->key)
54                         goto no_block;
55         }
56         return NULL;
57
58 changed:
59         read_unlock(&pointers_lock);
60         brelse(bh);
61         *err = -EAGAIN;
62         goto no_block;
63 failure:
64         *err = -EIO;
65 no_block:
66         return p;
67 }
68
69 static int alloc_branch(struct inode *inode,
70                              int num,
71                              int *offsets,
72                              Indirect *branch)
73 {
74         int n = 0;
75         int i;
76         int parent = minix_new_block(inode);
77
78         branch[0].key = cpu_to_block(parent);
79         if (parent) for (n = 1; n < num; n++) {
80                 struct buffer_head *bh;
81                 /* Allocate the next block */
82                 int nr = minix_new_block(inode);
83                 if (!nr)
84                         break;
85                 branch[n].key = cpu_to_block(nr);
86                 bh = sb_getblk(inode->i_sb, parent);
87                 lock_buffer(bh);
88                 memset(bh->b_data, 0, bh->b_size);
89                 branch[n].bh = bh;
90                 branch[n].p = (block_t*) bh->b_data + offsets[n];
91                 *branch[n].p = branch[n].key;
92                 set_buffer_uptodate(bh);
93                 unlock_buffer(bh);
94                 mark_buffer_dirty_inode(bh, inode);
95                 parent = nr;
96         }
97         if (n == num)
98                 return 0;
99
100         /* Allocation failed, free what we already allocated */
101         for (i = 1; i < n; i++)
102                 bforget(branch[i].bh);
103         for (i = 0; i < n; i++)
104                 minix_free_block(inode, block_to_cpu(branch[i].key));
105         return -ENOSPC;
106 }
107
108 static inline int splice_branch(struct inode *inode,
109                                      Indirect chain[DEPTH],
110                                      Indirect *where,
111                                      int num)
112 {
113         int i;
114
115         write_lock(&pointers_lock);
116
117         /* Verify that place we are splicing to is still there and vacant */
118         if (!verify_chain(chain, where-1) || *where->p)
119                 goto changed;
120
121         *where->p = where->key;
122
123         write_unlock(&pointers_lock);
124
125         /* We are done with atomic stuff, now do the rest of housekeeping */
126
127         inode->i_ctime = CURRENT_TIME_SEC;
128
129         /* had we spliced it onto indirect block? */
130         if (where->bh)
131                 mark_buffer_dirty_inode(where->bh, inode);
132
133         mark_inode_dirty(inode);
134         return 0;
135
136 changed:
137         write_unlock(&pointers_lock);
138         for (i = 1; i < num; i++)
139                 bforget(where[i].bh);
140         for (i = 0; i < num; i++)
141                 minix_free_block(inode, block_to_cpu(where[i].key));
142         return -EAGAIN;
143 }
144
145 static inline int get_block(struct inode * inode, sector_t block,
146                         struct buffer_head *bh, int create)
147 {
148         int err = -EIO;
149         int offsets[DEPTH];
150         Indirect chain[DEPTH];
151         Indirect *partial;
152         int left;
153         int depth = block_to_path(inode, block, offsets);
154
155         if (depth == 0)
156                 goto out;
157
158 reread:
159         partial = get_branch(inode, depth, offsets, chain, &err);
160
161         /* Simplest case - block found, no allocation needed */
162         if (!partial) {
163 got_it:
164                 map_bh(bh, inode->i_sb, block_to_cpu(chain[depth-1].key));
165                 /* Clean up and exit */
166                 partial = chain+depth-1; /* the whole chain */
167                 goto cleanup;
168         }
169
170         /* Next simple case - plain lookup or failed read of indirect block */
171         if (!create || err == -EIO) {
172 cleanup:
173                 while (partial > chain) {
174                         brelse(partial->bh);
175                         partial--;
176                 }
177 out:
178                 return err;
179         }
180
181         /*
182          * Indirect block might be removed by truncate while we were
183          * reading it. Handling of that case (forget what we've got and
184          * reread) is taken out of the main path.
185          */
186         if (err == -EAGAIN)
187                 goto changed;
188
189         left = (chain + depth) - partial;
190         err = alloc_branch(inode, left, offsets+(partial-chain), partial);
191         if (err)
192                 goto cleanup;
193
194         if (splice_branch(inode, chain, partial, left) < 0)
195                 goto changed;
196
197         set_buffer_new(bh);
198         goto got_it;
199
200 changed:
201         while (partial > chain) {
202                 brelse(partial->bh);
203                 partial--;
204         }
205         goto reread;
206 }
207
208 static inline int all_zeroes(block_t *p, block_t *q)
209 {
210         while (p < q)
211                 if (*p++)
212                         return 0;
213         return 1;
214 }
215
216 static Indirect *find_shared(struct inode *inode,
217                                 int depth,
218                                 int offsets[DEPTH],
219                                 Indirect chain[DEPTH],
220                                 block_t *top)
221 {
222         Indirect *partial, *p;
223         int k, err;
224
225         *top = 0;
226         for (k = depth; k > 1 && !offsets[k-1]; k--)
227                 ;
228         partial = get_branch(inode, k, offsets, chain, &err);
229
230         write_lock(&pointers_lock);
231         if (!partial)
232                 partial = chain + k-1;
233         if (!partial->key && *partial->p) {
234                 write_unlock(&pointers_lock);
235                 goto no_top;
236         }
237         for (p=partial;p>chain && all_zeroes((block_t*)p->bh->b_data,p->p);p--)
238                 ;
239         if (p == chain + k - 1 && p > chain) {
240                 p->p--;
241         } else {
242                 *top = *p->p;
243                 *p->p = 0;
244         }
245         write_unlock(&pointers_lock);
246
247         while(partial > p)
248         {
249                 brelse(partial->bh);
250                 partial--;
251         }
252 no_top:
253         return partial;
254 }
255
256 static inline void free_data(struct inode *inode, block_t *p, block_t *q)
257 {
258         unsigned long nr;
259
260         for ( ; p < q ; p++) {
261                 nr = block_to_cpu(*p);
262                 if (nr) {
263                         *p = 0;
264                         minix_free_block(inode, nr);
265                 }
266         }
267 }
268
269 static void free_branches(struct inode *inode, block_t *p, block_t *q, int depth)
270 {
271         struct buffer_head * bh;
272         unsigned long nr;
273
274         if (depth--) {
275                 for ( ; p < q ; p++) {
276                         nr = block_to_cpu(*p);
277                         if (!nr)
278                                 continue;
279                         *p = 0;
280                         bh = sb_bread(inode->i_sb, nr);
281                         if (!bh)
282                                 continue;
283                         free_branches(inode, (block_t*)bh->b_data,
284                                       block_end(bh), depth);
285                         bforget(bh);
286                         minix_free_block(inode, nr);
287                         mark_inode_dirty(inode);
288                 }
289         } else
290                 free_data(inode, p, q);
291 }
292
293 static inline void truncate (struct inode * inode)
294 {
295         struct super_block *sb = inode->i_sb;
296         block_t *idata = i_data(inode);
297         int offsets[DEPTH];
298         Indirect chain[DEPTH];
299         Indirect *partial;
300         block_t nr = 0;
301         int n;
302         int first_whole;
303         long iblock;
304
305         iblock = (inode->i_size + sb->s_blocksize -1) >> sb->s_blocksize_bits;
306         block_truncate_page(inode->i_mapping, inode->i_size, get_block);
307
308         n = block_to_path(inode, iblock, offsets);
309         if (!n)
310                 return;
311
312         if (n == 1) {
313                 free_data(inode, idata+offsets[0], idata + DIRECT);
314                 first_whole = 0;
315                 goto do_indirects;
316         }
317
318         first_whole = offsets[0] + 1 - DIRECT;
319         partial = find_shared(inode, n, offsets, chain, &nr);
320         if (nr) {
321                 if (partial == chain)
322                         mark_inode_dirty(inode);
323                 else
324                         mark_buffer_dirty_inode(partial->bh, inode);
325                 free_branches(inode, &nr, &nr+1, (chain+n-1) - partial);
326         }
327         /* Clear the ends of indirect blocks on the shared branch */
328         while (partial > chain) {
329                 free_branches(inode, partial->p + 1, block_end(partial->bh),
330                                 (chain+n-1) - partial);
331                 mark_buffer_dirty_inode(partial->bh, inode);
332                 brelse (partial->bh);
333                 partial--;
334         }
335 do_indirects:
336         /* Kill the remaining (whole) subtrees */
337         while (first_whole < DEPTH-1) {
338                 nr = idata[DIRECT+first_whole];
339                 if (nr) {
340                         idata[DIRECT+first_whole] = 0;
341                         mark_inode_dirty(inode);
342                         free_branches(inode, &nr, &nr+1, first_whole+1);
343                 }
344                 first_whole++;
345         }
346         inode->i_mtime = inode->i_ctime = CURRENT_TIME_SEC;
347         mark_inode_dirty(inode);
348 }
349
350 static inline unsigned nblocks(loff_t size, struct super_block *sb)
351 {
352         int k = sb->s_blocksize_bits - 10;
353         unsigned blocks, res, direct = DIRECT, i = DEPTH;
354         blocks = (size + sb->s_blocksize - 1) >> (BLOCK_SIZE_BITS + k);
355         res = blocks;
356         while (--i && blocks > direct) {
357                 blocks -= direct;
358                 blocks += sb->s_blocksize/sizeof(block_t) - 1;
359                 blocks /= sb->s_blocksize/sizeof(block_t);
360                 res += blocks;
361                 direct = 1;
362         }
363         return res;
364 }