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