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