Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
itree_common.c
Go to the documentation of this file.
1 /* Generic part */
2 
3 typedef struct {
6  struct buffer_head *bh;
7 } Indirect;
8 
9 static DEFINE_RWLOCK(pointers_lock);
10 
11 static 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 
17 static 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 
24 static inline block_t *block_end(struct buffer_head *bh)
25 {
26  return (block_t *)((char*)bh->b_data + bh->b_size);
27 }
28 
29 static inline Indirect *get_branch(struct inode *inode,
30  int depth,
31  int *offsets,
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 
58 changed:
59  read_unlock(&pointers_lock);
60  brelse(bh);
61  *err = -EAGAIN;
62  goto no_block;
63 failure:
64  *err = -EIO;
65 no_block:
66  return p;
67 }
68 
69 static int alloc_branch(struct inode *inode,
70  int num,
71  int *offsets,
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 
108 static 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 
136 changed:
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 
145 static 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];
151  Indirect *partial;
152  int left;
153  int depth = block_to_path(inode, block, offsets);
154 
155  if (depth == 0)
156  goto out;
157 
158 reread:
159  partial = get_branch(inode, depth, offsets, chain, &err);
160 
161  /* Simplest case - block found, no allocation needed */
162  if (!partial) {
163 got_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) {
172 cleanup:
173  while (partial > chain) {
174  brelse(partial->bh);
175  partial--;
176  }
177 out:
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 
200 changed:
201  while (partial > chain) {
202  brelse(partial->bh);
203  partial--;
204  }
205  goto reread;
206 }
207 
208 static 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 
216 static 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  }
252 no_top:
253  return partial;
254 }
255 
256 static 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 
269 static 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 
293 static 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  }
335 do_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 
350 static 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 }