fs/minix/itree_common.c

   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(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
  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(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->i_ctime = current_time(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, 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
 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->i_mtime = inode->i_ctime = current_time(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 }