File: /usr/src/linux/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 inline void add_chain(Indirect *p, struct buffer_head *bh, block_t *v)
10 {
11 p->key = *(p->p = v);
12 p->bh = bh;
13 }
14
15 static inline int verify_chain(Indirect *from, Indirect *to)
16 {
17 while (from <= to && from->key == *from->p)
18 from++;
19 return (from > to);
20 }
21
22 static inline block_t *block_end(struct buffer_head *bh)
23 {
24 return (block_t *)((char*)bh->b_data + BLOCK_SIZE);
25 }
26
27 static inline Indirect *get_branch(struct inode *inode,
28 int depth,
29 int *offsets,
30 Indirect chain[DEPTH],
31 int *err)
32 {
33 kdev_t dev = inode->i_dev;
34 Indirect *p = chain;
35 struct buffer_head *bh;
36
37 *err = 0;
38 /* i_data is not going away, no lock needed */
39 add_chain (chain, NULL, i_data(inode) + *offsets);
40 if (!p->key)
41 goto no_block;
42 while (--depth) {
43 bh = bread(dev, block_to_cpu(p->key), BLOCK_SIZE);
44 if (!bh)
45 goto failure;
46 /* Reader: pointers */
47 if (!verify_chain(chain, p))
48 goto changed;
49 add_chain(++p, bh, (block_t *)bh->b_data + *++offsets);
50 /* Reader: end */
51 if (!p->key)
52 goto no_block;
53 }
54 return NULL;
55
56 changed:
57 *err = -EAGAIN;
58 goto no_block;
59 failure:
60 *err = -EIO;
61 no_block:
62 return p;
63 }
64
65 static int alloc_branch(struct inode *inode,
66 int num,
67 int *offsets,
68 Indirect *branch)
69 {
70 int n = 0;
71 int i;
72 int parent = minix_new_block(inode);
73
74 branch[0].key = cpu_to_block(parent);
75 if (parent) for (n = 1; n < num; n++) {
76 struct buffer_head *bh;
77 /* Allocate the next block */
78 int nr = minix_new_block(inode);
79 if (!nr)
80 break;
81 branch[n].key = cpu_to_block(nr);
82 bh = getblk(inode->i_dev, parent, BLOCK_SIZE);
83 lock_buffer(bh);
84 memset(bh->b_data, 0, BLOCK_SIZE);
85 branch[n].bh = bh;
86 branch[n].p = (block_t*) bh->b_data + offsets[n];
87 *branch[n].p = branch[n].key;
88 mark_buffer_uptodate(bh, 1);
89 unlock_buffer(bh);
90 mark_buffer_dirty_inode(bh, inode);
91 parent = nr;
92 }
93 if (n == num)
94 return 0;
95
96 /* Allocation failed, free what we already allocated */
97 for (i = 1; i < n; i++)
98 bforget(branch[i].bh);
99 for (i = 0; i < n; i++)
100 minix_free_block(inode, block_to_cpu(branch[i].key));
101 return -ENOSPC;
102 }
103
104 static inline int splice_branch(struct inode *inode,
105 Indirect chain[DEPTH],
106 Indirect *where,
107 int num)
108 {
109 int i;
110
111 /* Verify that place we are splicing to is still there and vacant */
112
113 /* Writer: pointers */
114 if (!verify_chain(chain, where-1) || *where->p)
115 /* Writer: end */
116 goto changed;
117
118 /* That's it */
119
120 *where->p = where->key;
121
122 /* Writer: end */
123
124 /* We are done with atomic stuff, now do the rest of housekeeping */
125
126 inode->i_ctime = CURRENT_TIME;
127
128 /* had we spliced it onto indirect block? */
129 if (where->bh)
130 mark_buffer_dirty_inode(where->bh, inode);
131
132 mark_inode_dirty(inode);
133 return 0;
134
135 changed:
136 for (i = 1; i < num; i++)
137 bforget(where[i].bh);
138 for (i = 0; i < num; i++)
139 minix_free_block(inode, block_to_cpu(where[i].key));
140 return -EAGAIN;
141 }
142
143 static inline int get_block(struct inode * inode, long block,
144 struct buffer_head *bh_result, int create)
145 {
146 int err = -EIO;
147 int offsets[DEPTH];
148 Indirect chain[DEPTH];
149 Indirect *partial;
150 int left;
151 int depth = block_to_path(inode, block, offsets);
152
153 if (depth == 0)
154 goto out;
155
156 lock_kernel();
157 reread:
158 partial = get_branch(inode, depth, offsets, chain, &err);
159
160 /* Simplest case - block found, no allocation needed */
161 if (!partial) {
162 got_it:
163 bh_result->b_dev = inode->i_dev;
164 bh_result->b_blocknr = block_to_cpu(chain[depth-1].key);
165 bh_result->b_state |= (1UL << BH_Mapped);
166 /* Clean up and exit */
167 partial = chain+depth-1; /* the whole chain */
168 goto cleanup;
169 }
170
171 /* Next simple case - plain lookup or failed read of indirect block */
172 if (!create || err == -EIO) {
173 cleanup:
174 while (partial > chain) {
175 brelse(partial->bh);
176 partial--;
177 }
178 unlock_kernel();
179 out:
180 return err;
181 }
182
183 /*
184 * Indirect block might be removed by truncate while we were
185 * reading it. Handling of that case (forget what we've got and
186 * reread) is taken out of the main path.
187 */
188 if (err == -EAGAIN)
189 goto changed;
190
191 left = (chain + depth) - partial;
192 err = alloc_branch(inode, left, offsets+(partial-chain), partial);
193 if (err)
194 goto cleanup;
195
196 if (splice_branch(inode, chain, partial, left) < 0)
197 goto changed;
198
199 bh_result->b_state |= (1UL << BH_New);
200 goto got_it;
201
202 changed:
203 while (partial > chain) {
204 brelse(partial->bh);
205 partial--;
206 }
207 goto reread;
208 }
209
210 static inline int all_zeroes(block_t *p, block_t *q)
211 {
212 while (p < q)
213 if (*p++)
214 return 0;
215 return 1;
216 }
217
218 static Indirect *find_shared(struct inode *inode,
219 int depth,
220 int offsets[DEPTH],
221 Indirect chain[DEPTH],
222 block_t *top)
223 {
224 Indirect *partial, *p;
225 int k, err;
226
227 *top = 0;
228 for (k = depth; k > 1 && !offsets[k-1]; k--)
229 ;
230 partial = get_branch(inode, k, offsets, chain, &err);
231 /* Writer: pointers */
232 if (!partial)
233 partial = chain + k-1;
234 if (!partial->key && *partial->p)
235 /* Writer: end */
236 goto no_top;
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 /* Writer: end */
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 = bread (inode->i_dev, nr, BLOCK_SIZE);
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 block_t *idata = i_data(inode);
296 int offsets[DEPTH];
297 Indirect chain[DEPTH];
298 Indirect *partial;
299 block_t nr = 0;
300 int n;
301 int first_whole;
302 long iblock;
303
304 iblock = (inode->i_size + BLOCK_SIZE-1) >> 10;
305 block_truncate_page(inode->i_mapping, inode->i_size, get_block);
306
307 n = block_to_path(inode, iblock, offsets);
308 if (!n)
309 return;
310
311 if (n == 1) {
312 free_data(inode, idata+offsets[0], idata + DIRECT);
313 first_whole = 0;
314 goto do_indirects;
315 }
316
317 first_whole = offsets[0] + 1 - DIRECT;
318 partial = find_shared(inode, n, offsets, chain, &nr);
319 if (nr) {
320 if (partial == chain)
321 mark_inode_dirty(inode);
322 else
323 mark_buffer_dirty_inode(partial->bh, inode);
324 free_branches(inode, &nr, &nr+1, (chain+n-1) - partial);
325 }
326 /* Clear the ends of indirect blocks on the shared branch */
327 while (partial > chain) {
328 free_branches(inode, partial->p + 1, block_end(partial->bh),
329 (chain+n-1) - partial);
330 mark_buffer_dirty_inode(partial->bh, inode);
331 brelse (partial->bh);
332 partial--;
333 }
334 do_indirects:
335 /* Kill the remaining (whole) subtrees */
336 while (first_whole < DEPTH-1) {
337 nr = idata[DIRECT+first_whole];
338 if (nr) {
339 idata[DIRECT+first_whole] = 0;
340 mark_inode_dirty(inode);
341 free_branches(inode, &nr, &nr+1, first_whole+1);
342 }
343 first_whole++;
344 }
345 inode->i_mtime = inode->i_ctime = CURRENT_TIME;
346 mark_inode_dirty(inode);
347 }
348