1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* Generic part */ |
3 | |
4 | typedef struct { |
5 | block_t *p; |
6 | block_t key; |
7 | struct buffer_head *bh; |
8 | } Indirect; |
9 | |
10 | static DEFINE_RWLOCK(pointers_lock); |
11 | |
12 | static 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 | |
18 | static 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 | |
25 | static inline block_t *block_end(struct buffer_head *bh) |
26 | { |
27 | return (block_t *)((char*)bh->b_data + bh->b_size); |
28 | } |
29 | |
30 | static 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(from: chain, to: 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 | |
59 | changed: |
60 | read_unlock(&pointers_lock); |
61 | brelse(bh); |
62 | *err = -EAGAIN; |
63 | goto no_block; |
64 | failure: |
65 | *err = -EIO; |
66 | no_block: |
67 | return p; |
68 | } |
69 | |
70 | static 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 | |
115 | static 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(from: chain, to: 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 | |
143 | changed: |
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 | |
152 | static 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 | |
165 | reread: |
166 | partial = get_branch(inode, depth, offsets, chain, &err); |
167 | |
168 | /* Simplest case - block found, no allocation needed */ |
169 | if (!partial) { |
170 | got_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) { |
179 | cleanup: |
180 | while (partial > chain) { |
181 | brelse(partial->bh); |
182 | partial--; |
183 | } |
184 | out: |
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, num: left, offsets: offsets+(partial-chain), branch: 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 | |
207 | changed: |
208 | while (partial > chain) { |
209 | brelse(partial->bh); |
210 | partial--; |
211 | } |
212 | goto reread; |
213 | } |
214 | |
215 | static 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 | |
223 | static 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 | } |
259 | no_top: |
260 | return partial; |
261 | } |
262 | |
263 | static 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 | |
276 | static 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 | |
300 | static 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 | } |
342 | do_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 | |
357 | static 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 | } |
372 | |