1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * linux/fs/sysv/itree.c 4 * 5 * Handling of indirect blocks' trees. 6 * AV, Sep--Dec 2000 7 */ 8 9 #include <linux/buffer_head.h> 10 #include <linux/mount.h> 11 #include <linux/string.h> 12 #include "sysv.h" 13 14 enum {DIRECT = 10, DEPTH = 4}; /* Have triple indirect */ 15 16 static inline void dirty_indirect(struct buffer_head *bh, struct inode *inode) 17 { 18 mark_buffer_dirty_inode(bh, inode); 19 if (IS_SYNC(inode)) 20 sync_dirty_buffer(bh); 21 } 22 23 static int block_to_path(struct inode *inode, long block, int offsets[DEPTH]) 24 { 25 struct super_block *sb = inode->i_sb; 26 struct sysv_sb_info *sbi = SYSV_SB(sb); 27 int ptrs_bits = sbi->s_ind_per_block_bits; 28 unsigned long indirect_blocks = sbi->s_ind_per_block, 29 double_blocks = sbi->s_ind_per_block_2; 30 int n = 0; 31 32 if (block < 0) { 33 printk("sysv_block_map: block < 0\n"); 34 } else if (block < DIRECT) { 35 offsets[n++] = block; 36 } else if ( (block -= DIRECT) < indirect_blocks) { 37 offsets[n++] = DIRECT; 38 offsets[n++] = block; 39 } else if ((block -= indirect_blocks) < double_blocks) { 40 offsets[n++] = DIRECT+1; 41 offsets[n++] = block >> ptrs_bits; 42 offsets[n++] = block & (indirect_blocks - 1); 43 } else if (((block -= double_blocks) >> (ptrs_bits * 2)) < indirect_blocks) { 44 offsets[n++] = DIRECT+2; 45 offsets[n++] = block >> (ptrs_bits * 2); 46 offsets[n++] = (block >> ptrs_bits) & (indirect_blocks - 1); 47 offsets[n++] = block & (indirect_blocks - 1); 48 } else { 49 /* nothing */; 50 } 51 return n; 52 } 53 54 static inline int block_to_cpu(struct sysv_sb_info *sbi, sysv_zone_t nr) 55 { 56 return sbi->s_block_base + fs32_to_cpu(sbi, nr); 57 } 58 59 typedef struct { 60 sysv_zone_t *p; 61 sysv_zone_t key; 62 struct buffer_head *bh; 63 } Indirect; 64 65 static DEFINE_RWLOCK(pointers_lock); 66 67 static inline void add_chain(Indirect *p, struct buffer_head *bh, sysv_zone_t *v) 68 { 69 p->key = *(p->p = v); 70 p->bh = bh; 71 } 72 73 static inline int verify_chain(Indirect *from, Indirect *to) 74 { 75 while (from <= to && from->key == *from->p) 76 from++; 77 return (from > to); 78 } 79 80 static inline sysv_zone_t *block_end(struct buffer_head *bh) 81 { 82 return (sysv_zone_t*)((char*)bh->b_data + bh->b_size); 83 } 84 85 /* 86 * Requires read_lock(&pointers_lock) or write_lock(&pointers_lock) 87 */ 88 static Indirect *get_branch(struct inode *inode, 89 int depth, 90 int offsets[], 91 Indirect chain[], 92 int *err) 93 { 94 struct super_block *sb = inode->i_sb; 95 Indirect *p = chain; 96 struct buffer_head *bh; 97 98 *err = 0; 99 add_chain(chain, NULL, SYSV_I(inode)->i_data + *offsets); 100 if (!p->key) 101 goto no_block; 102 while (--depth) { 103 int block = block_to_cpu(SYSV_SB(sb), p->key); 104 bh = sb_bread(sb, block); 105 if (!bh) 106 goto failure; 107 if (!verify_chain(chain, p)) 108 goto changed; 109 add_chain(++p, bh, (sysv_zone_t*)bh->b_data + *++offsets); 110 if (!p->key) 111 goto no_block; 112 } 113 return NULL; 114 115 changed: 116 brelse(bh); 117 *err = -EAGAIN; 118 goto no_block; 119 failure: 120 *err = -EIO; 121 no_block: 122 return p; 123 } 124 125 static int alloc_branch(struct inode *inode, 126 int num, 127 int *offsets, 128 Indirect *branch) 129 { 130 int blocksize = inode->i_sb->s_blocksize; 131 int n = 0; 132 int i; 133 134 branch[0].key = sysv_new_block(inode->i_sb); 135 if (branch[0].key) for (n = 1; n < num; n++) { 136 struct buffer_head *bh; 137 int parent; 138 /* Allocate the next block */ 139 branch[n].key = sysv_new_block(inode->i_sb); 140 if (!branch[n].key) 141 break; 142 /* 143 * Get buffer_head for parent block, zero it out and set 144 * the pointer to new one, then send parent to disk. 145 */ 146 parent = block_to_cpu(SYSV_SB(inode->i_sb), branch[n-1].key); 147 bh = sb_getblk(inode->i_sb, parent); 148 if (!bh) { 149 sysv_free_block(inode->i_sb, branch[n].key); 150 break; 151 } 152 lock_buffer(bh); 153 memset(bh->b_data, 0, blocksize); 154 branch[n].bh = bh; 155 branch[n].p = (sysv_zone_t*) bh->b_data + offsets[n]; 156 *branch[n].p = branch[n].key; 157 set_buffer_uptodate(bh); 158 unlock_buffer(bh); 159 dirty_indirect(bh, inode); 160 } 161 if (n == num) 162 return 0; 163 164 /* Allocation failed, free what we already allocated */ 165 for (i = 1; i < n; i++) 166 bforget(branch[i].bh); 167 for (i = 0; i < n; i++) 168 sysv_free_block(inode->i_sb, branch[i].key); 169 return -ENOSPC; 170 } 171 172 static inline int splice_branch(struct inode *inode, 173 Indirect chain[], 174 Indirect *where, 175 int num) 176 { 177 int i; 178 179 /* Verify that place we are splicing to is still there and vacant */ 180 write_lock(&pointers_lock); 181 if (!verify_chain(chain, where-1) || *where->p) 182 goto changed; 183 *where->p = where->key; 184 write_unlock(&pointers_lock); 185 186 inode->i_ctime = current_time(inode); 187 188 /* had we spliced it onto indirect block? */ 189 if (where->bh) 190 dirty_indirect(where->bh, inode); 191 192 if (IS_SYNC(inode)) 193 sysv_sync_inode(inode); 194 else 195 mark_inode_dirty(inode); 196 return 0; 197 198 changed: 199 write_unlock(&pointers_lock); 200 for (i = 1; i < num; i++) 201 bforget(where[i].bh); 202 for (i = 0; i < num; i++) 203 sysv_free_block(inode->i_sb, where[i].key); 204 return -EAGAIN; 205 } 206 207 static int get_block(struct inode *inode, sector_t iblock, struct buffer_head *bh_result, int create) 208 { 209 int err = -EIO; 210 int offsets[DEPTH]; 211 Indirect chain[DEPTH]; 212 struct super_block *sb = inode->i_sb; 213 Indirect *partial; 214 int left; 215 int depth = block_to_path(inode, iblock, offsets); 216 217 if (depth == 0) 218 goto out; 219 220 reread: 221 read_lock(&pointers_lock); 222 partial = get_branch(inode, depth, offsets, chain, &err); 223 read_unlock(&pointers_lock); 224 225 /* Simplest case - block found, no allocation needed */ 226 if (!partial) { 227 got_it: 228 map_bh(bh_result, sb, block_to_cpu(SYSV_SB(sb), 229 chain[depth-1].key)); 230 /* Clean up and exit */ 231 partial = chain+depth-1; /* the whole chain */ 232 goto cleanup; 233 } 234 235 /* Next simple case - plain lookup or failed read of indirect block */ 236 if (!create || err == -EIO) { 237 cleanup: 238 while (partial > chain) { 239 brelse(partial->bh); 240 partial--; 241 } 242 out: 243 return err; 244 } 245 246 /* 247 * Indirect block might be removed by truncate while we were 248 * reading it. Handling of that case (forget what we've got and 249 * reread) is taken out of the main path. 250 */ 251 if (err == -EAGAIN) 252 goto changed; 253 254 left = (chain + depth) - partial; 255 err = alloc_branch(inode, left, offsets+(partial-chain), partial); 256 if (err) 257 goto cleanup; 258 259 if (splice_branch(inode, chain, partial, left) < 0) 260 goto changed; 261 262 set_buffer_new(bh_result); 263 goto got_it; 264 265 changed: 266 while (partial > chain) { 267 brelse(partial->bh); 268 partial--; 269 } 270 goto reread; 271 } 272 273 static inline int all_zeroes(sysv_zone_t *p, sysv_zone_t *q) 274 { 275 while (p < q) 276 if (*p++) 277 return 0; 278 return 1; 279 } 280 281 static Indirect *find_shared(struct inode *inode, 282 int depth, 283 int offsets[], 284 Indirect chain[], 285 sysv_zone_t *top) 286 { 287 Indirect *partial, *p; 288 int k, err; 289 290 *top = 0; 291 for (k = depth; k > 1 && !offsets[k-1]; k--) 292 ; 293 294 write_lock(&pointers_lock); 295 partial = get_branch(inode, k, offsets, chain, &err); 296 if (!partial) 297 partial = chain + k-1; 298 /* 299 * If the branch acquired continuation since we've looked at it - 300 * fine, it should all survive and (new) top doesn't belong to us. 301 */ 302 if (!partial->key && *partial->p) { 303 write_unlock(&pointers_lock); 304 goto no_top; 305 } 306 for (p=partial; p>chain && all_zeroes((sysv_zone_t*)p->bh->b_data,p->p); p--) 307 ; 308 /* 309 * OK, we've found the last block that must survive. The rest of our 310 * branch should be detached before unlocking. However, if that rest 311 * of branch is all ours and does not grow immediately from the inode 312 * it's easier to cheat and just decrement partial->p. 313 */ 314 if (p == chain + k - 1 && p > chain) { 315 p->p--; 316 } else { 317 *top = *p->p; 318 *p->p = 0; 319 } 320 write_unlock(&pointers_lock); 321 322 while (partial > p) { 323 brelse(partial->bh); 324 partial--; 325 } 326 no_top: 327 return partial; 328 } 329 330 static inline void free_data(struct inode *inode, sysv_zone_t *p, sysv_zone_t *q) 331 { 332 for ( ; p < q ; p++) { 333 sysv_zone_t nr = *p; 334 if (nr) { 335 *p = 0; 336 sysv_free_block(inode->i_sb, nr); 337 mark_inode_dirty(inode); 338 } 339 } 340 } 341 342 static void free_branches(struct inode *inode, sysv_zone_t *p, sysv_zone_t *q, int depth) 343 { 344 struct buffer_head * bh; 345 struct super_block *sb = inode->i_sb; 346 347 if (depth--) { 348 for ( ; p < q ; p++) { 349 int block; 350 sysv_zone_t nr = *p; 351 if (!nr) 352 continue; 353 *p = 0; 354 block = block_to_cpu(SYSV_SB(sb), nr); 355 bh = sb_bread(sb, block); 356 if (!bh) 357 continue; 358 free_branches(inode, (sysv_zone_t*)bh->b_data, 359 block_end(bh), depth); 360 bforget(bh); 361 sysv_free_block(sb, nr); 362 mark_inode_dirty(inode); 363 } 364 } else 365 free_data(inode, p, q); 366 } 367 368 void sysv_truncate (struct inode * inode) 369 { 370 sysv_zone_t *i_data = SYSV_I(inode)->i_data; 371 int offsets[DEPTH]; 372 Indirect chain[DEPTH]; 373 Indirect *partial; 374 sysv_zone_t nr = 0; 375 int n; 376 long iblock; 377 unsigned blocksize; 378 379 if (!(S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) || 380 S_ISLNK(inode->i_mode))) 381 return; 382 383 blocksize = inode->i_sb->s_blocksize; 384 iblock = (inode->i_size + blocksize-1) 385 >> inode->i_sb->s_blocksize_bits; 386 387 block_truncate_page(inode->i_mapping, inode->i_size, get_block); 388 389 n = block_to_path(inode, iblock, offsets); 390 if (n == 0) 391 return; 392 393 if (n == 1) { 394 free_data(inode, i_data+offsets[0], i_data + DIRECT); 395 goto do_indirects; 396 } 397 398 partial = find_shared(inode, n, offsets, chain, &nr); 399 /* Kill the top of shared branch (already detached) */ 400 if (nr) { 401 if (partial == chain) 402 mark_inode_dirty(inode); 403 else 404 dirty_indirect(partial->bh, inode); 405 free_branches(inode, &nr, &nr+1, (chain+n-1) - partial); 406 } 407 /* Clear the ends of indirect blocks on the shared branch */ 408 while (partial > chain) { 409 free_branches(inode, partial->p + 1, block_end(partial->bh), 410 (chain+n-1) - partial); 411 dirty_indirect(partial->bh, inode); 412 brelse (partial->bh); 413 partial--; 414 } 415 do_indirects: 416 /* Kill the remaining (whole) subtrees (== subtrees deeper than...) */ 417 while (n < DEPTH) { 418 nr = i_data[DIRECT + n - 1]; 419 if (nr) { 420 i_data[DIRECT + n - 1] = 0; 421 mark_inode_dirty(inode); 422 free_branches(inode, &nr, &nr+1, n); 423 } 424 n++; 425 } 426 inode->i_mtime = inode->i_ctime = current_time(inode); 427 if (IS_SYNC(inode)) 428 sysv_sync_inode (inode); 429 else 430 mark_inode_dirty(inode); 431 } 432 433 static unsigned sysv_nblocks(struct super_block *s, loff_t size) 434 { 435 struct sysv_sb_info *sbi = SYSV_SB(s); 436 int ptrs_bits = sbi->s_ind_per_block_bits; 437 unsigned blocks, res, direct = DIRECT, i = DEPTH; 438 blocks = (size + s->s_blocksize - 1) >> s->s_blocksize_bits; 439 res = blocks; 440 while (--i && blocks > direct) { 441 blocks = ((blocks - direct - 1) >> ptrs_bits) + 1; 442 res += blocks; 443 direct = 1; 444 } 445 return res; 446 } 447 448 int sysv_getattr(struct mnt_idmap *idmap, const struct path *path, 449 struct kstat *stat, u32 request_mask, unsigned int flags) 450 { 451 struct super_block *s = path->dentry->d_sb; 452 generic_fillattr(&nop_mnt_idmap, d_inode(path->dentry), stat); 453 stat->blocks = (s->s_blocksize / 512) * sysv_nblocks(s, stat->size); 454 stat->blksize = s->s_blocksize; 455 return 0; 456 } 457 458 static int sysv_writepage(struct page *page, struct writeback_control *wbc) 459 { 460 return block_write_full_page(page,get_block,wbc); 461 } 462 463 static int sysv_read_folio(struct file *file, struct folio *folio) 464 { 465 return block_read_full_folio(folio, get_block); 466 } 467 468 int sysv_prepare_chunk(struct page *page, loff_t pos, unsigned len) 469 { 470 return __block_write_begin(page, pos, len, get_block); 471 } 472 473 static void sysv_write_failed(struct address_space *mapping, loff_t to) 474 { 475 struct inode *inode = mapping->host; 476 477 if (to > inode->i_size) { 478 truncate_pagecache(inode, inode->i_size); 479 sysv_truncate(inode); 480 } 481 } 482 483 static int sysv_write_begin(struct file *file, struct address_space *mapping, 484 loff_t pos, unsigned len, 485 struct page **pagep, void **fsdata) 486 { 487 int ret; 488 489 ret = block_write_begin(mapping, pos, len, pagep, get_block); 490 if (unlikely(ret)) 491 sysv_write_failed(mapping, pos + len); 492 493 return ret; 494 } 495 496 static sector_t sysv_bmap(struct address_space *mapping, sector_t block) 497 { 498 return generic_block_bmap(mapping,block,get_block); 499 } 500 501 const struct address_space_operations sysv_aops = { 502 .dirty_folio = block_dirty_folio, 503 .invalidate_folio = block_invalidate_folio, 504 .read_folio = sysv_read_folio, 505 .writepage = sysv_writepage, 506 .write_begin = sysv_write_begin, 507 .write_end = generic_write_end, 508 .bmap = sysv_bmap 509 }; 510