Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
xfs_da_btree.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000-2005 Silicon Graphics, Inc.
3  * All Rights Reserved.
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License as
7  * published by the Free Software Foundation.
8  *
9  * This program is distributed in the hope that it would be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write the Free Software Foundation,
16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17  */
18 #include "xfs.h"
19 #include "xfs_fs.h"
20 #include "xfs_types.h"
21 #include "xfs_bit.h"
22 #include "xfs_log.h"
23 #include "xfs_trans.h"
24 #include "xfs_sb.h"
25 #include "xfs_ag.h"
26 #include "xfs_mount.h"
27 #include "xfs_da_btree.h"
28 #include "xfs_bmap_btree.h"
29 #include "xfs_dir2.h"
30 #include "xfs_dir2_format.h"
31 #include "xfs_dir2_priv.h"
32 #include "xfs_dinode.h"
33 #include "xfs_inode.h"
34 #include "xfs_inode_item.h"
35 #include "xfs_alloc.h"
36 #include "xfs_bmap.h"
37 #include "xfs_attr.h"
38 #include "xfs_attr_leaf.h"
39 #include "xfs_error.h"
40 #include "xfs_trace.h"
41 
42 /*
43  * xfs_da_btree.c
44  *
45  * Routines to implement directories as Btrees of hashed names.
46  */
47 
48 /*========================================================================
49  * Function prototypes for the kernel.
50  *========================================================================*/
51 
52 /*
53  * Routines used for growing the Btree.
54  */
55 STATIC int xfs_da_root_split(xfs_da_state_t *state,
56  xfs_da_state_blk_t *existing_root,
57  xfs_da_state_blk_t *new_child);
58 STATIC int xfs_da_node_split(xfs_da_state_t *state,
59  xfs_da_state_blk_t *existing_blk,
60  xfs_da_state_blk_t *split_blk,
61  xfs_da_state_blk_t *blk_to_add,
62  int treelevel,
63  int *result);
64 STATIC void xfs_da_node_rebalance(xfs_da_state_t *state,
65  xfs_da_state_blk_t *node_blk_1,
66  xfs_da_state_blk_t *node_blk_2);
67 STATIC void xfs_da_node_add(xfs_da_state_t *state,
68  xfs_da_state_blk_t *old_node_blk,
69  xfs_da_state_blk_t *new_node_blk);
70 
71 /*
72  * Routines used for shrinking the Btree.
73  */
74 STATIC int xfs_da_root_join(xfs_da_state_t *state,
75  xfs_da_state_blk_t *root_blk);
76 STATIC int xfs_da_node_toosmall(xfs_da_state_t *state, int *retval);
77 STATIC void xfs_da_node_remove(xfs_da_state_t *state,
78  xfs_da_state_blk_t *drop_blk);
79 STATIC void xfs_da_node_unbalance(xfs_da_state_t *state,
80  xfs_da_state_blk_t *src_node_blk,
81  xfs_da_state_blk_t *dst_node_blk);
82 
83 /*
84  * Utility routines.
85  */
86 STATIC uint xfs_da_node_lasthash(struct xfs_buf *bp, int *count);
87 STATIC int xfs_da_node_order(struct xfs_buf *node1_bp,
88  struct xfs_buf *node2_bp);
89 STATIC int xfs_da_blk_unlink(xfs_da_state_t *state,
90  xfs_da_state_blk_t *drop_blk,
91  xfs_da_state_blk_t *save_blk);
92 STATIC void xfs_da_state_kill_altpath(xfs_da_state_t *state);
93 
94 /*========================================================================
95  * Routines used for growing the Btree.
96  *========================================================================*/
97 
98 /*
99  * Create the initial contents of an intermediate node.
100  */
101 int
102 xfs_da_node_create(xfs_da_args_t *args, xfs_dablk_t blkno, int level,
103  struct xfs_buf **bpp, int whichfork)
104 {
105  xfs_da_intnode_t *node;
106  struct xfs_buf *bp;
107  int error;
108  xfs_trans_t *tp;
109 
110  trace_xfs_da_node_create(args);
111 
112  tp = args->trans;
113  error = xfs_da_get_buf(tp, args->dp, blkno, -1, &bp, whichfork);
114  if (error)
115  return(error);
116  ASSERT(bp != NULL);
117  node = bp->b_addr;
118  node->hdr.info.forw = 0;
119  node->hdr.info.back = 0;
120  node->hdr.info.magic = cpu_to_be16(XFS_DA_NODE_MAGIC);
121  node->hdr.info.pad = 0;
122  node->hdr.count = 0;
123  node->hdr.level = cpu_to_be16(level);
124 
125  xfs_trans_log_buf(tp, bp,
126  XFS_DA_LOGRANGE(node, &node->hdr, sizeof(node->hdr)));
127 
128  *bpp = bp;
129  return(0);
130 }
131 
132 /*
133  * Split a leaf node, rebalance, then possibly split
134  * intermediate nodes, rebalance, etc.
135  */
136 int /* error */
137 xfs_da_split(xfs_da_state_t *state)
138 {
139  xfs_da_state_blk_t *oldblk, *newblk, *addblk;
140  xfs_da_intnode_t *node;
141  struct xfs_buf *bp;
142  int max, action, error, i;
143 
144  trace_xfs_da_split(state->args);
145 
146  /*
147  * Walk back up the tree splitting/inserting/adjusting as necessary.
148  * If we need to insert and there isn't room, split the node, then
149  * decide which fragment to insert the new block from below into.
150  * Note that we may split the root this way, but we need more fixup.
151  */
152  max = state->path.active - 1;
153  ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));
154  ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||
155  state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
156 
157  addblk = &state->path.blk[max]; /* initial dummy value */
158  for (i = max; (i >= 0) && addblk; state->path.active--, i--) {
159  oldblk = &state->path.blk[i];
160  newblk = &state->altpath.blk[i];
161 
162  /*
163  * If a leaf node then
164  * Allocate a new leaf node, then rebalance across them.
165  * else if an intermediate node then
166  * We split on the last layer, must we split the node?
167  */
168  switch (oldblk->magic) {
169  case XFS_ATTR_LEAF_MAGIC:
170  error = xfs_attr_leaf_split(state, oldblk, newblk);
171  if ((error != 0) && (error != ENOSPC)) {
172  return(error); /* GROT: attr is inconsistent */
173  }
174  if (!error) {
175  addblk = newblk;
176  break;
177  }
178  /*
179  * Entry wouldn't fit, split the leaf again.
180  */
181  state->extravalid = 1;
182  if (state->inleaf) {
183  state->extraafter = 0; /* before newblk */
184  trace_xfs_attr_leaf_split_before(state->args);
185  error = xfs_attr_leaf_split(state, oldblk,
186  &state->extrablk);
187  } else {
188  state->extraafter = 1; /* after newblk */
189  trace_xfs_attr_leaf_split_after(state->args);
190  error = xfs_attr_leaf_split(state, newblk,
191  &state->extrablk);
192  }
193  if (error)
194  return(error); /* GROT: attr inconsistent */
195  addblk = newblk;
196  break;
197  case XFS_DIR2_LEAFN_MAGIC:
198  error = xfs_dir2_leafn_split(state, oldblk, newblk);
199  if (error)
200  return error;
201  addblk = newblk;
202  break;
203  case XFS_DA_NODE_MAGIC:
204  error = xfs_da_node_split(state, oldblk, newblk, addblk,
205  max - i, &action);
206  addblk->bp = NULL;
207  if (error)
208  return(error); /* GROT: dir is inconsistent */
209  /*
210  * Record the newly split block for the next time thru?
211  */
212  if (action)
213  addblk = newblk;
214  else
215  addblk = NULL;
216  break;
217  }
218 
219  /*
220  * Update the btree to show the new hashval for this child.
221  */
222  xfs_da_fixhashpath(state, &state->path);
223  }
224  if (!addblk)
225  return(0);
226 
227  /*
228  * Split the root node.
229  */
230  ASSERT(state->path.active == 0);
231  oldblk = &state->path.blk[0];
232  error = xfs_da_root_split(state, oldblk, addblk);
233  if (error) {
234  addblk->bp = NULL;
235  return(error); /* GROT: dir is inconsistent */
236  }
237 
238  /*
239  * Update pointers to the node which used to be block 0 and
240  * just got bumped because of the addition of a new root node.
241  * There might be three blocks involved if a double split occurred,
242  * and the original block 0 could be at any position in the list.
243  */
244 
245  node = oldblk->bp->b_addr;
246  if (node->hdr.info.forw) {
247  if (be32_to_cpu(node->hdr.info.forw) == addblk->blkno) {
248  bp = addblk->bp;
249  } else {
250  ASSERT(state->extravalid);
251  bp = state->extrablk.bp;
252  }
253  node = bp->b_addr;
254  node->hdr.info.back = cpu_to_be32(oldblk->blkno);
255  xfs_trans_log_buf(state->args->trans, bp,
256  XFS_DA_LOGRANGE(node, &node->hdr.info,
257  sizeof(node->hdr.info)));
258  }
259  node = oldblk->bp->b_addr;
260  if (node->hdr.info.back) {
261  if (be32_to_cpu(node->hdr.info.back) == addblk->blkno) {
262  bp = addblk->bp;
263  } else {
264  ASSERT(state->extravalid);
265  bp = state->extrablk.bp;
266  }
267  node = bp->b_addr;
268  node->hdr.info.forw = cpu_to_be32(oldblk->blkno);
269  xfs_trans_log_buf(state->args->trans, bp,
270  XFS_DA_LOGRANGE(node, &node->hdr.info,
271  sizeof(node->hdr.info)));
272  }
273  addblk->bp = NULL;
274  return(0);
275 }
276 
277 /*
278  * Split the root. We have to create a new root and point to the two
279  * parts (the split old root) that we just created. Copy block zero to
280  * the EOF, extending the inode in process.
281  */
282 STATIC int /* error */
283 xfs_da_root_split(xfs_da_state_t *state, xfs_da_state_blk_t *blk1,
284  xfs_da_state_blk_t *blk2)
285 {
286  xfs_da_intnode_t *node, *oldroot;
287  xfs_da_args_t *args;
288  xfs_dablk_t blkno;
289  struct xfs_buf *bp;
290  int error, size;
291  xfs_inode_t *dp;
292  xfs_trans_t *tp;
293  xfs_mount_t *mp;
294  xfs_dir2_leaf_t *leaf;
295 
296  trace_xfs_da_root_split(state->args);
297 
298  /*
299  * Copy the existing (incorrect) block from the root node position
300  * to a free space somewhere.
301  */
302  args = state->args;
303  ASSERT(args != NULL);
304  error = xfs_da_grow_inode(args, &blkno);
305  if (error)
306  return(error);
307  dp = args->dp;
308  tp = args->trans;
309  mp = state->mp;
310  error = xfs_da_get_buf(tp, dp, blkno, -1, &bp, args->whichfork);
311  if (error)
312  return(error);
313  ASSERT(bp != NULL);
314  node = bp->b_addr;
315  oldroot = blk1->bp->b_addr;
316  if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC)) {
317  size = (int)((char *)&oldroot->btree[be16_to_cpu(oldroot->hdr.count)] -
318  (char *)oldroot);
319  } else {
320  ASSERT(oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC));
321  leaf = (xfs_dir2_leaf_t *)oldroot;
322  size = (int)((char *)&leaf->ents[be16_to_cpu(leaf->hdr.count)] -
323  (char *)leaf);
324  }
325  memcpy(node, oldroot, size);
326  xfs_trans_log_buf(tp, bp, 0, size - 1);
327  blk1->bp = bp;
328  blk1->blkno = blkno;
329 
330  /*
331  * Set up the new root node.
332  */
333  error = xfs_da_node_create(args,
334  (args->whichfork == XFS_DATA_FORK) ? mp->m_dirleafblk : 0,
335  be16_to_cpu(node->hdr.level) + 1, &bp, args->whichfork);
336  if (error)
337  return(error);
338  node = bp->b_addr;
339  node->btree[0].hashval = cpu_to_be32(blk1->hashval);
340  node->btree[0].before = cpu_to_be32(blk1->blkno);
341  node->btree[1].hashval = cpu_to_be32(blk2->hashval);
342  node->btree[1].before = cpu_to_be32(blk2->blkno);
343  node->hdr.count = cpu_to_be16(2);
344 
345 #ifdef DEBUG
346  if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC)) {
347  ASSERT(blk1->blkno >= mp->m_dirleafblk &&
348  blk1->blkno < mp->m_dirfreeblk);
349  ASSERT(blk2->blkno >= mp->m_dirleafblk &&
350  blk2->blkno < mp->m_dirfreeblk);
351  }
352 #endif
353 
354  /* Header is already logged by xfs_da_node_create */
355  xfs_trans_log_buf(tp, bp,
356  XFS_DA_LOGRANGE(node, node->btree,
357  sizeof(xfs_da_node_entry_t) * 2));
358 
359  return(0);
360 }
361 
362 /*
363  * Split the node, rebalance, then add the new entry.
364  */
365 STATIC int /* error */
366 xfs_da_node_split(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk,
367  xfs_da_state_blk_t *newblk,
368  xfs_da_state_blk_t *addblk,
369  int treelevel, int *result)
370 {
371  xfs_da_intnode_t *node;
372  xfs_dablk_t blkno;
373  int newcount, error;
374  int useextra;
375 
376  trace_xfs_da_node_split(state->args);
377 
378  node = oldblk->bp->b_addr;
379  ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
380 
381  /*
382  * With V2 dirs the extra block is data or freespace.
383  */
384  useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;
385  newcount = 1 + useextra;
386  /*
387  * Do we have to split the node?
388  */
389  if ((be16_to_cpu(node->hdr.count) + newcount) > state->node_ents) {
390  /*
391  * Allocate a new node, add to the doubly linked chain of
392  * nodes, then move some of our excess entries into it.
393  */
394  error = xfs_da_grow_inode(state->args, &blkno);
395  if (error)
396  return(error); /* GROT: dir is inconsistent */
397 
398  error = xfs_da_node_create(state->args, blkno, treelevel,
399  &newblk->bp, state->args->whichfork);
400  if (error)
401  return(error); /* GROT: dir is inconsistent */
402  newblk->blkno = blkno;
403  newblk->magic = XFS_DA_NODE_MAGIC;
404  xfs_da_node_rebalance(state, oldblk, newblk);
405  error = xfs_da_blk_link(state, oldblk, newblk);
406  if (error)
407  return(error);
408  *result = 1;
409  } else {
410  *result = 0;
411  }
412 
413  /*
414  * Insert the new entry(s) into the correct block
415  * (updating last hashval in the process).
416  *
417  * xfs_da_node_add() inserts BEFORE the given index,
418  * and as a result of using node_lookup_int() we always
419  * point to a valid entry (not after one), but a split
420  * operation always results in a new block whose hashvals
421  * FOLLOW the current block.
422  *
423  * If we had double-split op below us, then add the extra block too.
424  */
425  node = oldblk->bp->b_addr;
426  if (oldblk->index <= be16_to_cpu(node->hdr.count)) {
427  oldblk->index++;
428  xfs_da_node_add(state, oldblk, addblk);
429  if (useextra) {
430  if (state->extraafter)
431  oldblk->index++;
432  xfs_da_node_add(state, oldblk, &state->extrablk);
433  state->extravalid = 0;
434  }
435  } else {
436  newblk->index++;
437  xfs_da_node_add(state, newblk, addblk);
438  if (useextra) {
439  if (state->extraafter)
440  newblk->index++;
441  xfs_da_node_add(state, newblk, &state->extrablk);
442  state->extravalid = 0;
443  }
444  }
445 
446  return(0);
447 }
448 
449 /*
450  * Balance the btree elements between two intermediate nodes,
451  * usually one full and one empty.
452  *
453  * NOTE: if blk2 is empty, then it will get the upper half of blk1.
454  */
455 STATIC void
456 xfs_da_node_rebalance(xfs_da_state_t *state, xfs_da_state_blk_t *blk1,
457  xfs_da_state_blk_t *blk2)
458 {
459  xfs_da_intnode_t *node1, *node2, *tmpnode;
460  xfs_da_node_entry_t *btree_s, *btree_d;
461  int count, tmp;
462  xfs_trans_t *tp;
463 
464  trace_xfs_da_node_rebalance(state->args);
465 
466  node1 = blk1->bp->b_addr;
467  node2 = blk2->bp->b_addr;
468  /*
469  * Figure out how many entries need to move, and in which direction.
470  * Swap the nodes around if that makes it simpler.
471  */
472  if ((be16_to_cpu(node1->hdr.count) > 0) && (be16_to_cpu(node2->hdr.count) > 0) &&
473  ((be32_to_cpu(node2->btree[0].hashval) < be32_to_cpu(node1->btree[0].hashval)) ||
474  (be32_to_cpu(node2->btree[be16_to_cpu(node2->hdr.count)-1].hashval) <
475  be32_to_cpu(node1->btree[be16_to_cpu(node1->hdr.count)-1].hashval)))) {
476  tmpnode = node1;
477  node1 = node2;
478  node2 = tmpnode;
479  }
480  ASSERT(node1->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
481  ASSERT(node2->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
482  count = (be16_to_cpu(node1->hdr.count) - be16_to_cpu(node2->hdr.count)) / 2;
483  if (count == 0)
484  return;
485  tp = state->args->trans;
486  /*
487  * Two cases: high-to-low and low-to-high.
488  */
489  if (count > 0) {
490  /*
491  * Move elements in node2 up to make a hole.
492  */
493  if ((tmp = be16_to_cpu(node2->hdr.count)) > 0) {
494  tmp *= (uint)sizeof(xfs_da_node_entry_t);
495  btree_s = &node2->btree[0];
496  btree_d = &node2->btree[count];
497  memmove(btree_d, btree_s, tmp);
498  }
499 
500  /*
501  * Move the req'd B-tree elements from high in node1 to
502  * low in node2.
503  */
504  be16_add_cpu(&node2->hdr.count, count);
505  tmp = count * (uint)sizeof(xfs_da_node_entry_t);
506  btree_s = &node1->btree[be16_to_cpu(node1->hdr.count) - count];
507  btree_d = &node2->btree[0];
508  memcpy(btree_d, btree_s, tmp);
509  be16_add_cpu(&node1->hdr.count, -count);
510  } else {
511  /*
512  * Move the req'd B-tree elements from low in node2 to
513  * high in node1.
514  */
515  count = -count;
516  tmp = count * (uint)sizeof(xfs_da_node_entry_t);
517  btree_s = &node2->btree[0];
518  btree_d = &node1->btree[be16_to_cpu(node1->hdr.count)];
519  memcpy(btree_d, btree_s, tmp);
520  be16_add_cpu(&node1->hdr.count, count);
521  xfs_trans_log_buf(tp, blk1->bp,
522  XFS_DA_LOGRANGE(node1, btree_d, tmp));
523 
524  /*
525  * Move elements in node2 down to fill the hole.
526  */
527  tmp = be16_to_cpu(node2->hdr.count) - count;
528  tmp *= (uint)sizeof(xfs_da_node_entry_t);
529  btree_s = &node2->btree[count];
530  btree_d = &node2->btree[0];
531  memmove(btree_d, btree_s, tmp);
532  be16_add_cpu(&node2->hdr.count, -count);
533  }
534 
535  /*
536  * Log header of node 1 and all current bits of node 2.
537  */
538  xfs_trans_log_buf(tp, blk1->bp,
539  XFS_DA_LOGRANGE(node1, &node1->hdr, sizeof(node1->hdr)));
540  xfs_trans_log_buf(tp, blk2->bp,
541  XFS_DA_LOGRANGE(node2, &node2->hdr,
542  sizeof(node2->hdr) +
543  sizeof(node2->btree[0]) * be16_to_cpu(node2->hdr.count)));
544 
545  /*
546  * Record the last hashval from each block for upward propagation.
547  * (note: don't use the swapped node pointers)
548  */
549  node1 = blk1->bp->b_addr;
550  node2 = blk2->bp->b_addr;
551  blk1->hashval = be32_to_cpu(node1->btree[be16_to_cpu(node1->hdr.count)-1].hashval);
552  blk2->hashval = be32_to_cpu(node2->btree[be16_to_cpu(node2->hdr.count)-1].hashval);
553 
554  /*
555  * Adjust the expected index for insertion.
556  */
557  if (blk1->index >= be16_to_cpu(node1->hdr.count)) {
558  blk2->index = blk1->index - be16_to_cpu(node1->hdr.count);
559  blk1->index = be16_to_cpu(node1->hdr.count) + 1; /* make it invalid */
560  }
561 }
562 
563 /*
564  * Add a new entry to an intermediate node.
565  */
566 STATIC void
567 xfs_da_node_add(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk,
568  xfs_da_state_blk_t *newblk)
569 {
570  xfs_da_intnode_t *node;
571  xfs_da_node_entry_t *btree;
572  int tmp;
573 
574  trace_xfs_da_node_add(state->args);
575 
576  node = oldblk->bp->b_addr;
577  ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
578  ASSERT((oldblk->index >= 0) && (oldblk->index <= be16_to_cpu(node->hdr.count)));
579  ASSERT(newblk->blkno != 0);
580  if (state->args->whichfork == XFS_DATA_FORK)
581  ASSERT(newblk->blkno >= state->mp->m_dirleafblk &&
582  newblk->blkno < state->mp->m_dirfreeblk);
583 
584  /*
585  * We may need to make some room before we insert the new node.
586  */
587  tmp = 0;
588  btree = &node->btree[ oldblk->index ];
589  if (oldblk->index < be16_to_cpu(node->hdr.count)) {
590  tmp = (be16_to_cpu(node->hdr.count) - oldblk->index) * (uint)sizeof(*btree);
591  memmove(btree + 1, btree, tmp);
592  }
593  btree->hashval = cpu_to_be32(newblk->hashval);
594  btree->before = cpu_to_be32(newblk->blkno);
595  xfs_trans_log_buf(state->args->trans, oldblk->bp,
596  XFS_DA_LOGRANGE(node, btree, tmp + sizeof(*btree)));
597  be16_add_cpu(&node->hdr.count, 1);
598  xfs_trans_log_buf(state->args->trans, oldblk->bp,
599  XFS_DA_LOGRANGE(node, &node->hdr, sizeof(node->hdr)));
600 
601  /*
602  * Copy the last hash value from the oldblk to propagate upwards.
603  */
604  oldblk->hashval = be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1 ].hashval);
605 }
606 
607 /*========================================================================
608  * Routines used for shrinking the Btree.
609  *========================================================================*/
610 
611 /*
612  * Deallocate an empty leaf node, remove it from its parent,
613  * possibly deallocating that block, etc...
614  */
615 int
616 xfs_da_join(xfs_da_state_t *state)
617 {
618  xfs_da_state_blk_t *drop_blk, *save_blk;
619  int action, error;
620 
621  trace_xfs_da_join(state->args);
622 
623  action = 0;
624  drop_blk = &state->path.blk[ state->path.active-1 ];
625  save_blk = &state->altpath.blk[ state->path.active-1 ];
626  ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);
627  ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC ||
628  drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
629 
630  /*
631  * Walk back up the tree joining/deallocating as necessary.
632  * When we stop dropping blocks, break out.
633  */
634  for ( ; state->path.active >= 2; drop_blk--, save_blk--,
635  state->path.active--) {
636  /*
637  * See if we can combine the block with a neighbor.
638  * (action == 0) => no options, just leave
639  * (action == 1) => coalesce, then unlink
640  * (action == 2) => block empty, unlink it
641  */
642  switch (drop_blk->magic) {
643  case XFS_ATTR_LEAF_MAGIC:
644  error = xfs_attr_leaf_toosmall(state, &action);
645  if (error)
646  return(error);
647  if (action == 0)
648  return(0);
649  xfs_attr_leaf_unbalance(state, drop_blk, save_blk);
650  break;
651  case XFS_DIR2_LEAFN_MAGIC:
652  error = xfs_dir2_leafn_toosmall(state, &action);
653  if (error)
654  return error;
655  if (action == 0)
656  return 0;
657  xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);
658  break;
659  case XFS_DA_NODE_MAGIC:
660  /*
661  * Remove the offending node, fixup hashvals,
662  * check for a toosmall neighbor.
663  */
664  xfs_da_node_remove(state, drop_blk);
665  xfs_da_fixhashpath(state, &state->path);
666  error = xfs_da_node_toosmall(state, &action);
667  if (error)
668  return(error);
669  if (action == 0)
670  return 0;
671  xfs_da_node_unbalance(state, drop_blk, save_blk);
672  break;
673  }
674  xfs_da_fixhashpath(state, &state->altpath);
675  error = xfs_da_blk_unlink(state, drop_blk, save_blk);
676  xfs_da_state_kill_altpath(state);
677  if (error)
678  return(error);
679  error = xfs_da_shrink_inode(state->args, drop_blk->blkno,
680  drop_blk->bp);
681  drop_blk->bp = NULL;
682  if (error)
683  return(error);
684  }
685  /*
686  * We joined all the way to the top. If it turns out that
687  * we only have one entry in the root, make the child block
688  * the new root.
689  */
690  xfs_da_node_remove(state, drop_blk);
691  xfs_da_fixhashpath(state, &state->path);
692  error = xfs_da_root_join(state, &state->path.blk[0]);
693  return(error);
694 }
695 
696 #ifdef DEBUG
697 static void
698 xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)
699 {
700  __be16 magic = blkinfo->magic;
701 
702  if (level == 1) {
703  ASSERT(magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
704  magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC));
705  } else
706  ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
707  ASSERT(!blkinfo->forw);
708  ASSERT(!blkinfo->back);
709 }
710 #else /* !DEBUG */
711 #define xfs_da_blkinfo_onlychild_validate(blkinfo, level)
712 #endif /* !DEBUG */
713 
714 /*
715  * We have only one entry in the root. Copy the only remaining child of
716  * the old root to block 0 as the new root node.
717  */
718 STATIC int
719 xfs_da_root_join(xfs_da_state_t *state, xfs_da_state_blk_t *root_blk)
720 {
721  xfs_da_intnode_t *oldroot;
722  xfs_da_args_t *args;
723  xfs_dablk_t child;
724  struct xfs_buf *bp;
725  int error;
726 
727  trace_xfs_da_root_join(state->args);
728 
729  args = state->args;
730  ASSERT(args != NULL);
731  ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);
732  oldroot = root_blk->bp->b_addr;
733  ASSERT(oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
734  ASSERT(!oldroot->hdr.info.forw);
735  ASSERT(!oldroot->hdr.info.back);
736 
737  /*
738  * If the root has more than one child, then don't do anything.
739  */
740  if (be16_to_cpu(oldroot->hdr.count) > 1)
741  return(0);
742 
743  /*
744  * Read in the (only) child block, then copy those bytes into
745  * the root block's buffer and free the original child block.
746  */
747  child = be32_to_cpu(oldroot->btree[0].before);
748  ASSERT(child != 0);
749  error = xfs_da_read_buf(args->trans, args->dp, child, -1, &bp,
750  args->whichfork);
751  if (error)
752  return(error);
753  ASSERT(bp != NULL);
754  xfs_da_blkinfo_onlychild_validate(bp->b_addr,
755  be16_to_cpu(oldroot->hdr.level));
756 
757  memcpy(root_blk->bp->b_addr, bp->b_addr, state->blocksize);
758  xfs_trans_log_buf(args->trans, root_blk->bp, 0, state->blocksize - 1);
759  error = xfs_da_shrink_inode(args, child, bp);
760  return(error);
761 }
762 
763 /*
764  * Check a node block and its neighbors to see if the block should be
765  * collapsed into one or the other neighbor. Always keep the block
766  * with the smaller block number.
767  * If the current block is over 50% full, don't try to join it, return 0.
768  * If the block is empty, fill in the state structure and return 2.
769  * If it can be collapsed, fill in the state structure and return 1.
770  * If nothing can be done, return 0.
771  */
772 STATIC int
773 xfs_da_node_toosmall(xfs_da_state_t *state, int *action)
774 {
775  xfs_da_intnode_t *node;
776  xfs_da_state_blk_t *blk;
777  xfs_da_blkinfo_t *info;
778  int count, forward, error, retval, i;
779  xfs_dablk_t blkno;
780  struct xfs_buf *bp;
781 
782  /*
783  * Check for the degenerate case of the block being over 50% full.
784  * If so, it's not worth even looking to see if we might be able
785  * to coalesce with a sibling.
786  */
787  blk = &state->path.blk[ state->path.active-1 ];
788  info = blk->bp->b_addr;
789  ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
790  node = (xfs_da_intnode_t *)info;
791  count = be16_to_cpu(node->hdr.count);
792  if (count > (state->node_ents >> 1)) {
793  *action = 0; /* blk over 50%, don't try to join */
794  return(0); /* blk over 50%, don't try to join */
795  }
796 
797  /*
798  * Check for the degenerate case of the block being empty.
799  * If the block is empty, we'll simply delete it, no need to
800  * coalesce it with a sibling block. We choose (arbitrarily)
801  * to merge with the forward block unless it is NULL.
802  */
803  if (count == 0) {
804  /*
805  * Make altpath point to the block we want to keep and
806  * path point to the block we want to drop (this one).
807  */
808  forward = (info->forw != 0);
809  memcpy(&state->altpath, &state->path, sizeof(state->path));
810  error = xfs_da_path_shift(state, &state->altpath, forward,
811  0, &retval);
812  if (error)
813  return(error);
814  if (retval) {
815  *action = 0;
816  } else {
817  *action = 2;
818  }
819  return(0);
820  }
821 
822  /*
823  * Examine each sibling block to see if we can coalesce with
824  * at least 25% free space to spare. We need to figure out
825  * whether to merge with the forward or the backward block.
826  * We prefer coalescing with the lower numbered sibling so as
827  * to shrink a directory over time.
828  */
829  /* start with smaller blk num */
830  forward = (be32_to_cpu(info->forw) < be32_to_cpu(info->back));
831  for (i = 0; i < 2; forward = !forward, i++) {
832  if (forward)
833  blkno = be32_to_cpu(info->forw);
834  else
835  blkno = be32_to_cpu(info->back);
836  if (blkno == 0)
837  continue;
838  error = xfs_da_read_buf(state->args->trans, state->args->dp,
839  blkno, -1, &bp, state->args->whichfork);
840  if (error)
841  return(error);
842  ASSERT(bp != NULL);
843 
844  node = (xfs_da_intnode_t *)info;
845  count = state->node_ents;
846  count -= state->node_ents >> 2;
847  count -= be16_to_cpu(node->hdr.count);
848  node = bp->b_addr;
849  ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
850  count -= be16_to_cpu(node->hdr.count);
851  xfs_trans_brelse(state->args->trans, bp);
852  if (count >= 0)
853  break; /* fits with at least 25% to spare */
854  }
855  if (i >= 2) {
856  *action = 0;
857  return(0);
858  }
859 
860  /*
861  * Make altpath point to the block we want to keep (the lower
862  * numbered block) and path point to the block we want to drop.
863  */
864  memcpy(&state->altpath, &state->path, sizeof(state->path));
865  if (blkno < blk->blkno) {
866  error = xfs_da_path_shift(state, &state->altpath, forward,
867  0, &retval);
868  if (error) {
869  return(error);
870  }
871  if (retval) {
872  *action = 0;
873  return(0);
874  }
875  } else {
876  error = xfs_da_path_shift(state, &state->path, forward,
877  0, &retval);
878  if (error) {
879  return(error);
880  }
881  if (retval) {
882  *action = 0;
883  return(0);
884  }
885  }
886  *action = 1;
887  return(0);
888 }
889 
890 /*
891  * Walk back up the tree adjusting hash values as necessary,
892  * when we stop making changes, return.
893  */
894 void
895 xfs_da_fixhashpath(xfs_da_state_t *state, xfs_da_state_path_t *path)
896 {
897  xfs_da_state_blk_t *blk;
898  xfs_da_intnode_t *node;
899  xfs_da_node_entry_t *btree;
900  xfs_dahash_t lasthash=0;
901  int level, count;
902 
903  level = path->active-1;
904  blk = &path->blk[ level ];
905  switch (blk->magic) {
906  case XFS_ATTR_LEAF_MAGIC:
907  lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
908  if (count == 0)
909  return;
910  break;
911  case XFS_DIR2_LEAFN_MAGIC:
912  lasthash = xfs_dir2_leafn_lasthash(blk->bp, &count);
913  if (count == 0)
914  return;
915  break;
916  case XFS_DA_NODE_MAGIC:
917  lasthash = xfs_da_node_lasthash(blk->bp, &count);
918  if (count == 0)
919  return;
920  break;
921  }
922  for (blk--, level--; level >= 0; blk--, level--) {
923  node = blk->bp->b_addr;
924  ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
925  btree = &node->btree[ blk->index ];
926  if (be32_to_cpu(btree->hashval) == lasthash)
927  break;
928  blk->hashval = lasthash;
929  btree->hashval = cpu_to_be32(lasthash);
930  xfs_trans_log_buf(state->args->trans, blk->bp,
931  XFS_DA_LOGRANGE(node, btree, sizeof(*btree)));
932 
933  lasthash = be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1].hashval);
934  }
935 }
936 
937 /*
938  * Remove an entry from an intermediate node.
939  */
940 STATIC void
941 xfs_da_node_remove(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk)
942 {
943  xfs_da_intnode_t *node;
944  xfs_da_node_entry_t *btree;
945  int tmp;
946 
947  trace_xfs_da_node_remove(state->args);
948 
949  node = drop_blk->bp->b_addr;
950  ASSERT(drop_blk->index < be16_to_cpu(node->hdr.count));
951  ASSERT(drop_blk->index >= 0);
952 
953  /*
954  * Copy over the offending entry, or just zero it out.
955  */
956  btree = &node->btree[drop_blk->index];
957  if (drop_blk->index < (be16_to_cpu(node->hdr.count)-1)) {
958  tmp = be16_to_cpu(node->hdr.count) - drop_blk->index - 1;
959  tmp *= (uint)sizeof(xfs_da_node_entry_t);
960  memmove(btree, btree + 1, tmp);
961  xfs_trans_log_buf(state->args->trans, drop_blk->bp,
962  XFS_DA_LOGRANGE(node, btree, tmp));
963  btree = &node->btree[be16_to_cpu(node->hdr.count)-1];
964  }
965  memset((char *)btree, 0, sizeof(xfs_da_node_entry_t));
966  xfs_trans_log_buf(state->args->trans, drop_blk->bp,
967  XFS_DA_LOGRANGE(node, btree, sizeof(*btree)));
968  be16_add_cpu(&node->hdr.count, -1);
969  xfs_trans_log_buf(state->args->trans, drop_blk->bp,
970  XFS_DA_LOGRANGE(node, &node->hdr, sizeof(node->hdr)));
971 
972  /*
973  * Copy the last hash value from the block to propagate upwards.
974  */
975  btree--;
976  drop_blk->hashval = be32_to_cpu(btree->hashval);
977 }
978 
979 /*
980  * Unbalance the btree elements between two intermediate nodes,
981  * move all Btree elements from one node into another.
982  */
983 STATIC void
984 xfs_da_node_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
985  xfs_da_state_blk_t *save_blk)
986 {
987  xfs_da_intnode_t *drop_node, *save_node;
988  xfs_da_node_entry_t *btree;
989  int tmp;
990  xfs_trans_t *tp;
991 
992  trace_xfs_da_node_unbalance(state->args);
993 
994  drop_node = drop_blk->bp->b_addr;
995  save_node = save_blk->bp->b_addr;
996  ASSERT(drop_node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
997  ASSERT(save_node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
998  tp = state->args->trans;
999 
1000  /*
1001  * If the dying block has lower hashvals, then move all the
1002  * elements in the remaining block up to make a hole.
1003  */
1004  if ((be32_to_cpu(drop_node->btree[0].hashval) < be32_to_cpu(save_node->btree[ 0 ].hashval)) ||
1005  (be32_to_cpu(drop_node->btree[be16_to_cpu(drop_node->hdr.count)-1].hashval) <
1006  be32_to_cpu(save_node->btree[be16_to_cpu(save_node->hdr.count)-1].hashval)))
1007  {
1008  btree = &save_node->btree[be16_to_cpu(drop_node->hdr.count)];
1009  tmp = be16_to_cpu(save_node->hdr.count) * (uint)sizeof(xfs_da_node_entry_t);
1010  memmove(btree, &save_node->btree[0], tmp);
1011  btree = &save_node->btree[0];
1012  xfs_trans_log_buf(tp, save_blk->bp,
1013  XFS_DA_LOGRANGE(save_node, btree,
1014  (be16_to_cpu(save_node->hdr.count) + be16_to_cpu(drop_node->hdr.count)) *
1015  sizeof(xfs_da_node_entry_t)));
1016  } else {
1017  btree = &save_node->btree[be16_to_cpu(save_node->hdr.count)];
1018  xfs_trans_log_buf(tp, save_blk->bp,
1019  XFS_DA_LOGRANGE(save_node, btree,
1020  be16_to_cpu(drop_node->hdr.count) *
1021  sizeof(xfs_da_node_entry_t)));
1022  }
1023 
1024  /*
1025  * Move all the B-tree elements from drop_blk to save_blk.
1026  */
1027  tmp = be16_to_cpu(drop_node->hdr.count) * (uint)sizeof(xfs_da_node_entry_t);
1028  memcpy(btree, &drop_node->btree[0], tmp);
1029  be16_add_cpu(&save_node->hdr.count, be16_to_cpu(drop_node->hdr.count));
1030 
1031  xfs_trans_log_buf(tp, save_blk->bp,
1032  XFS_DA_LOGRANGE(save_node, &save_node->hdr,
1033  sizeof(save_node->hdr)));
1034 
1035  /*
1036  * Save the last hashval in the remaining block for upward propagation.
1037  */
1038  save_blk->hashval = be32_to_cpu(save_node->btree[be16_to_cpu(save_node->hdr.count)-1].hashval);
1039 }
1040 
1041 /*========================================================================
1042  * Routines used for finding things in the Btree.
1043  *========================================================================*/
1044 
1045 /*
1046  * Walk down the Btree looking for a particular filename, filling
1047  * in the state structure as we go.
1048  *
1049  * We will set the state structure to point to each of the elements
1050  * in each of the nodes where either the hashval is or should be.
1051  *
1052  * We support duplicate hashval's so for each entry in the current
1053  * node that could contain the desired hashval, descend. This is a
1054  * pruned depth-first tree search.
1055  */
1056 int /* error */
1057 xfs_da_node_lookup_int(xfs_da_state_t *state, int *result)
1058 {
1059  xfs_da_state_blk_t *blk;
1060  xfs_da_blkinfo_t *curr;
1061  xfs_da_intnode_t *node;
1062  xfs_da_node_entry_t *btree;
1063  xfs_dablk_t blkno;
1064  int probe, span, max, error, retval;
1065  xfs_dahash_t hashval, btreehashval;
1066  xfs_da_args_t *args;
1067 
1068  args = state->args;
1069 
1070  /*
1071  * Descend thru the B-tree searching each level for the right
1072  * node to use, until the right hashval is found.
1073  */
1074  blkno = (args->whichfork == XFS_DATA_FORK)? state->mp->m_dirleafblk : 0;
1075  for (blk = &state->path.blk[0], state->path.active = 1;
1076  state->path.active <= XFS_DA_NODE_MAXDEPTH;
1077  blk++, state->path.active++) {
1078  /*
1079  * Read the next node down in the tree.
1080  */
1081  blk->blkno = blkno;
1082  error = xfs_da_read_buf(args->trans, args->dp, blkno,
1083  -1, &blk->bp, args->whichfork);
1084  if (error) {
1085  blk->blkno = 0;
1086  state->path.active--;
1087  return(error);
1088  }
1089  curr = blk->bp->b_addr;
1090  blk->magic = be16_to_cpu(curr->magic);
1091  ASSERT(blk->magic == XFS_DA_NODE_MAGIC ||
1092  blk->magic == XFS_DIR2_LEAFN_MAGIC ||
1093  blk->magic == XFS_ATTR_LEAF_MAGIC);
1094 
1095  /*
1096  * Search an intermediate node for a match.
1097  */
1098  if (blk->magic == XFS_DA_NODE_MAGIC) {
1099  node = blk->bp->b_addr;
1100  max = be16_to_cpu(node->hdr.count);
1101  blk->hashval = be32_to_cpu(node->btree[max-1].hashval);
1102 
1103  /*
1104  * Binary search. (note: small blocks will skip loop)
1105  */
1106  probe = span = max / 2;
1107  hashval = args->hashval;
1108  for (btree = &node->btree[probe]; span > 4;
1109  btree = &node->btree[probe]) {
1110  span /= 2;
1111  btreehashval = be32_to_cpu(btree->hashval);
1112  if (btreehashval < hashval)
1113  probe += span;
1114  else if (btreehashval > hashval)
1115  probe -= span;
1116  else
1117  break;
1118  }
1119  ASSERT((probe >= 0) && (probe < max));
1120  ASSERT((span <= 4) || (be32_to_cpu(btree->hashval) == hashval));
1121 
1122  /*
1123  * Since we may have duplicate hashval's, find the first
1124  * matching hashval in the node.
1125  */
1126  while ((probe > 0) && (be32_to_cpu(btree->hashval) >= hashval)) {
1127  btree--;
1128  probe--;
1129  }
1130  while ((probe < max) && (be32_to_cpu(btree->hashval) < hashval)) {
1131  btree++;
1132  probe++;
1133  }
1134 
1135  /*
1136  * Pick the right block to descend on.
1137  */
1138  if (probe == max) {
1139  blk->index = max-1;
1140  blkno = be32_to_cpu(node->btree[max-1].before);
1141  } else {
1142  blk->index = probe;
1143  blkno = be32_to_cpu(btree->before);
1144  }
1145  } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1146  blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
1147  break;
1148  } else if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
1149  blk->hashval = xfs_dir2_leafn_lasthash(blk->bp, NULL);
1150  break;
1151  }
1152  }
1153 
1154  /*
1155  * A leaf block that ends in the hashval that we are interested in
1156  * (final hashval == search hashval) means that the next block may
1157  * contain more entries with the same hashval, shift upward to the
1158  * next leaf and keep searching.
1159  */
1160  for (;;) {
1161  if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
1162  retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
1163  &blk->index, state);
1164  } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1165  retval = xfs_attr_leaf_lookup_int(blk->bp, args);
1166  blk->index = args->index;
1167  args->blkno = blk->blkno;
1168  } else {
1169  ASSERT(0);
1170  return XFS_ERROR(EFSCORRUPTED);
1171  }
1172  if (((retval == ENOENT) || (retval == ENOATTR)) &&
1173  (blk->hashval == args->hashval)) {
1174  error = xfs_da_path_shift(state, &state->path, 1, 1,
1175  &retval);
1176  if (error)
1177  return(error);
1178  if (retval == 0) {
1179  continue;
1180  } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
1181  /* path_shift() gives ENOENT */
1182  retval = XFS_ERROR(ENOATTR);
1183  }
1184  }
1185  break;
1186  }
1187  *result = retval;
1188  return(0);
1189 }
1190 
1191 /*========================================================================
1192  * Utility routines.
1193  *========================================================================*/
1194 
1195 /*
1196  * Link a new block into a doubly linked list of blocks (of whatever type).
1197  */
1198 int /* error */
1199 xfs_da_blk_link(xfs_da_state_t *state, xfs_da_state_blk_t *old_blk,
1200  xfs_da_state_blk_t *new_blk)
1201 {
1202  xfs_da_blkinfo_t *old_info, *new_info, *tmp_info;
1203  xfs_da_args_t *args;
1204  int before=0, error;
1205  struct xfs_buf *bp;
1206 
1207  /*
1208  * Set up environment.
1209  */
1210  args = state->args;
1211  ASSERT(args != NULL);
1212  old_info = old_blk->bp->b_addr;
1213  new_info = new_blk->bp->b_addr;
1214  ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC ||
1215  old_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
1216  old_blk->magic == XFS_ATTR_LEAF_MAGIC);
1217  ASSERT(old_blk->magic == be16_to_cpu(old_info->magic));
1218  ASSERT(new_blk->magic == be16_to_cpu(new_info->magic));
1219  ASSERT(old_blk->magic == new_blk->magic);
1220 
1221  switch (old_blk->magic) {
1222  case XFS_ATTR_LEAF_MAGIC:
1223  before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
1224  break;
1225  case XFS_DIR2_LEAFN_MAGIC:
1226  before = xfs_dir2_leafn_order(old_blk->bp, new_blk->bp);
1227  break;
1228  case XFS_DA_NODE_MAGIC:
1229  before = xfs_da_node_order(old_blk->bp, new_blk->bp);
1230  break;
1231  }
1232 
1233  /*
1234  * Link blocks in appropriate order.
1235  */
1236  if (before) {
1237  /*
1238  * Link new block in before existing block.
1239  */
1240  trace_xfs_da_link_before(args);
1241  new_info->forw = cpu_to_be32(old_blk->blkno);
1242  new_info->back = old_info->back;
1243  if (old_info->back) {
1244  error = xfs_da_read_buf(args->trans, args->dp,
1245  be32_to_cpu(old_info->back),
1246  -1, &bp, args->whichfork);
1247  if (error)
1248  return(error);
1249  ASSERT(bp != NULL);
1250  tmp_info = bp->b_addr;
1251  ASSERT(be16_to_cpu(tmp_info->magic) == be16_to_cpu(old_info->magic));
1252  ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno);
1253  tmp_info->forw = cpu_to_be32(new_blk->blkno);
1254  xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
1255  }
1256  old_info->back = cpu_to_be32(new_blk->blkno);
1257  } else {
1258  /*
1259  * Link new block in after existing block.
1260  */
1261  trace_xfs_da_link_after(args);
1262  new_info->forw = old_info->forw;
1263  new_info->back = cpu_to_be32(old_blk->blkno);
1264  if (old_info->forw) {
1265  error = xfs_da_read_buf(args->trans, args->dp,
1266  be32_to_cpu(old_info->forw),
1267  -1, &bp, args->whichfork);
1268  if (error)
1269  return(error);
1270  ASSERT(bp != NULL);
1271  tmp_info = bp->b_addr;
1272  ASSERT(tmp_info->magic == old_info->magic);
1273  ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);
1274  tmp_info->back = cpu_to_be32(new_blk->blkno);
1275  xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
1276  }
1277  old_info->forw = cpu_to_be32(new_blk->blkno);
1278  }
1279 
1280  xfs_trans_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
1281  xfs_trans_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
1282  return(0);
1283 }
1284 
1285 /*
1286  * Compare two intermediate nodes for "order".
1287  */
1288 STATIC int
1289 xfs_da_node_order(
1290  struct xfs_buf *node1_bp,
1291  struct xfs_buf *node2_bp)
1292 {
1293  xfs_da_intnode_t *node1, *node2;
1294 
1295  node1 = node1_bp->b_addr;
1296  node2 = node2_bp->b_addr;
1297  ASSERT(node1->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) &&
1298  node2->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
1299  if ((be16_to_cpu(node1->hdr.count) > 0) && (be16_to_cpu(node2->hdr.count) > 0) &&
1300  ((be32_to_cpu(node2->btree[0].hashval) <
1301  be32_to_cpu(node1->btree[0].hashval)) ||
1302  (be32_to_cpu(node2->btree[be16_to_cpu(node2->hdr.count)-1].hashval) <
1303  be32_to_cpu(node1->btree[be16_to_cpu(node1->hdr.count)-1].hashval)))) {
1304  return(1);
1305  }
1306  return(0);
1307 }
1308 
1309 /*
1310  * Pick up the last hashvalue from an intermediate node.
1311  */
1312 STATIC uint
1313 xfs_da_node_lasthash(
1314  struct xfs_buf *bp,
1315  int *count)
1316 {
1317  xfs_da_intnode_t *node;
1318 
1319  node = bp->b_addr;
1320  ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
1321  if (count)
1322  *count = be16_to_cpu(node->hdr.count);
1323  if (!node->hdr.count)
1324  return(0);
1325  return be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1].hashval);
1326 }
1327 
1328 /*
1329  * Unlink a block from a doubly linked list of blocks.
1330  */
1331 STATIC int /* error */
1332 xfs_da_blk_unlink(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
1333  xfs_da_state_blk_t *save_blk)
1334 {
1335  xfs_da_blkinfo_t *drop_info, *save_info, *tmp_info;
1336  xfs_da_args_t *args;
1337  struct xfs_buf *bp;
1338  int error;
1339 
1340  /*
1341  * Set up environment.
1342  */
1343  args = state->args;
1344  ASSERT(args != NULL);
1345  save_info = save_blk->bp->b_addr;
1346  drop_info = drop_blk->bp->b_addr;
1347  ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC ||
1348  save_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
1349  save_blk->magic == XFS_ATTR_LEAF_MAGIC);
1350  ASSERT(save_blk->magic == be16_to_cpu(save_info->magic));
1351  ASSERT(drop_blk->magic == be16_to_cpu(drop_info->magic));
1352  ASSERT(save_blk->magic == drop_blk->magic);
1353  ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||
1354  (be32_to_cpu(save_info->back) == drop_blk->blkno));
1355  ASSERT((be32_to_cpu(drop_info->forw) == save_blk->blkno) ||
1356  (be32_to_cpu(drop_info->back) == save_blk->blkno));
1357 
1358  /*
1359  * Unlink the leaf block from the doubly linked chain of leaves.
1360  */
1361  if (be32_to_cpu(save_info->back) == drop_blk->blkno) {
1362  trace_xfs_da_unlink_back(args);
1363  save_info->back = drop_info->back;
1364  if (drop_info->back) {
1365  error = xfs_da_read_buf(args->trans, args->dp,
1366  be32_to_cpu(drop_info->back),
1367  -1, &bp, args->whichfork);
1368  if (error)
1369  return(error);
1370  ASSERT(bp != NULL);
1371  tmp_info = bp->b_addr;
1372  ASSERT(tmp_info->magic == save_info->magic);
1373  ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);
1374  tmp_info->forw = cpu_to_be32(save_blk->blkno);
1375  xfs_trans_log_buf(args->trans, bp, 0,
1376  sizeof(*tmp_info) - 1);
1377  }
1378  } else {
1379  trace_xfs_da_unlink_forward(args);
1380  save_info->forw = drop_info->forw;
1381  if (drop_info->forw) {
1382  error = xfs_da_read_buf(args->trans, args->dp,
1383  be32_to_cpu(drop_info->forw),
1384  -1, &bp, args->whichfork);
1385  if (error)
1386  return(error);
1387  ASSERT(bp != NULL);
1388  tmp_info = bp->b_addr;
1389  ASSERT(tmp_info->magic == save_info->magic);
1390  ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);
1391  tmp_info->back = cpu_to_be32(save_blk->blkno);
1392  xfs_trans_log_buf(args->trans, bp, 0,
1393  sizeof(*tmp_info) - 1);
1394  }
1395  }
1396 
1397  xfs_trans_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
1398  return(0);
1399 }
1400 
1401 /*
1402  * Move a path "forward" or "!forward" one block at the current level.
1403  *
1404  * This routine will adjust a "path" to point to the next block
1405  * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
1406  * Btree, including updating pointers to the intermediate nodes between
1407  * the new bottom and the root.
1408  */
1409 int /* error */
1410 xfs_da_path_shift(xfs_da_state_t *state, xfs_da_state_path_t *path,
1411  int forward, int release, int *result)
1412 {
1413  xfs_da_state_blk_t *blk;
1414  xfs_da_blkinfo_t *info;
1415  xfs_da_intnode_t *node;
1416  xfs_da_args_t *args;
1417  xfs_dablk_t blkno=0;
1418  int level, error;
1419 
1420  /*
1421  * Roll up the Btree looking for the first block where our
1422  * current index is not at the edge of the block. Note that
1423  * we skip the bottom layer because we want the sibling block.
1424  */
1425  args = state->args;
1426  ASSERT(args != NULL);
1427  ASSERT(path != NULL);
1428  ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
1429  level = (path->active-1) - 1; /* skip bottom layer in path */
1430  for (blk = &path->blk[level]; level >= 0; blk--, level--) {
1431  ASSERT(blk->bp != NULL);
1432  node = blk->bp->b_addr;
1433  ASSERT(node->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
1434  if (forward && (blk->index < be16_to_cpu(node->hdr.count)-1)) {
1435  blk->index++;
1436  blkno = be32_to_cpu(node->btree[blk->index].before);
1437  break;
1438  } else if (!forward && (blk->index > 0)) {
1439  blk->index--;
1440  blkno = be32_to_cpu(node->btree[blk->index].before);
1441  break;
1442  }
1443  }
1444  if (level < 0) {
1445  *result = XFS_ERROR(ENOENT); /* we're out of our tree */
1446  ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
1447  return(0);
1448  }
1449 
1450  /*
1451  * Roll down the edge of the subtree until we reach the
1452  * same depth we were at originally.
1453  */
1454  for (blk++, level++; level < path->active; blk++, level++) {
1455  /*
1456  * Release the old block.
1457  * (if it's dirty, trans won't actually let go)
1458  */
1459  if (release)
1460  xfs_trans_brelse(args->trans, blk->bp);
1461 
1462  /*
1463  * Read the next child block.
1464  */
1465  blk->blkno = blkno;
1466  error = xfs_da_read_buf(args->trans, args->dp, blkno, -1,
1467  &blk->bp, args->whichfork);
1468  if (error)
1469  return(error);
1470  ASSERT(blk->bp != NULL);
1471  info = blk->bp->b_addr;
1472  ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
1473  info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1474  info->magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC));
1475  blk->magic = be16_to_cpu(info->magic);
1476  if (blk->magic == XFS_DA_NODE_MAGIC) {
1477  node = (xfs_da_intnode_t *)info;
1478  blk->hashval = be32_to_cpu(node->btree[be16_to_cpu(node->hdr.count)-1].hashval);
1479  if (forward)
1480  blk->index = 0;
1481  else
1482  blk->index = be16_to_cpu(node->hdr.count)-1;
1483  blkno = be32_to_cpu(node->btree[blk->index].before);
1484  } else {
1485  ASSERT(level == path->active-1);
1486  blk->index = 0;
1487  switch(blk->magic) {
1488  case XFS_ATTR_LEAF_MAGIC:
1489  blk->hashval = xfs_attr_leaf_lasthash(blk->bp,
1490  NULL);
1491  break;
1492  case XFS_DIR2_LEAFN_MAGIC:
1493  blk->hashval = xfs_dir2_leafn_lasthash(blk->bp,
1494  NULL);
1495  break;
1496  default:
1497  ASSERT(blk->magic == XFS_ATTR_LEAF_MAGIC ||
1498  blk->magic == XFS_DIR2_LEAFN_MAGIC);
1499  break;
1500  }
1501  }
1502  }
1503  *result = 0;
1504  return(0);
1505 }
1506 
1507 
1508 /*========================================================================
1509  * Utility routines.
1510  *========================================================================*/
1511 
1512 /*
1513  * Implement a simple hash on a character string.
1514  * Rotate the hash value by 7 bits, then XOR each character in.
1515  * This is implemented with some source-level loop unrolling.
1516  */
1517 xfs_dahash_t
1518 xfs_da_hashname(const __uint8_t *name, int namelen)
1519 {
1520  xfs_dahash_t hash;
1521 
1522  /*
1523  * Do four characters at a time as long as we can.
1524  */
1525  for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
1526  hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
1527  (name[3] << 0) ^ rol32(hash, 7 * 4);
1528 
1529  /*
1530  * Now do the rest of the characters.
1531  */
1532  switch (namelen) {
1533  case 3:
1534  return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
1535  rol32(hash, 7 * 3);
1536  case 2:
1537  return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
1538  case 1:
1539  return (name[0] << 0) ^ rol32(hash, 7 * 1);
1540  default: /* case 0: */
1541  return hash;
1542  }
1543 }
1544 
1545 enum xfs_dacmp
1546 xfs_da_compname(
1547  struct xfs_da_args *args,
1548  const unsigned char *name,
1549  int len)
1550 {
1551  return (args->namelen == len && memcmp(args->name, name, len) == 0) ?
1552  XFS_CMP_EXACT : XFS_CMP_DIFFERENT;
1553 }
1554 
1555 static xfs_dahash_t
1556 xfs_default_hashname(
1557  struct xfs_name *name)
1558 {
1559  return xfs_da_hashname(name->name, name->len);
1560 }
1561 
1562 const struct xfs_nameops xfs_default_nameops = {
1563  .hashname = xfs_default_hashname,
1564  .compname = xfs_da_compname
1565 };
1566 
1567 int
1568 xfs_da_grow_inode_int(
1569  struct xfs_da_args *args,
1570  xfs_fileoff_t *bno,
1571  int count)
1572 {
1573  struct xfs_trans *tp = args->trans;
1574  struct xfs_inode *dp = args->dp;
1575  int w = args->whichfork;
1576  xfs_drfsbno_t nblks = dp->i_d.di_nblocks;
1577  struct xfs_bmbt_irec map, *mapp;
1578  int nmap, error, got, i, mapi;
1579 
1580  /*
1581  * Find a spot in the file space to put the new block.
1582  */
1583  error = xfs_bmap_first_unused(tp, dp, count, bno, w);
1584  if (error)
1585  return error;
1586 
1587  /*
1588  * Try mapping it in one filesystem block.
1589  */
1590  nmap = 1;
1591  ASSERT(args->firstblock != NULL);
1592  error = xfs_bmapi_write(tp, dp, *bno, count,
1593  xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,
1594  args->firstblock, args->total, &map, &nmap,
1595  args->flist);
1596  if (error)
1597  return error;
1598 
1599  ASSERT(nmap <= 1);
1600  if (nmap == 1) {
1601  mapp = &map;
1602  mapi = 1;
1603  } else if (nmap == 0 && count > 1) {
1604  xfs_fileoff_t b;
1605  int c;
1606 
1607  /*
1608  * If we didn't get it and the block might work if fragmented,
1609  * try without the CONTIG flag. Loop until we get it all.
1610  */
1611  mapp = kmem_alloc(sizeof(*mapp) * count, KM_SLEEP);
1612  for (b = *bno, mapi = 0; b < *bno + count; ) {
1613  nmap = MIN(XFS_BMAP_MAX_NMAP, count);
1614  c = (int)(*bno + count - b);
1615  error = xfs_bmapi_write(tp, dp, b, c,
1616  xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
1617  args->firstblock, args->total,
1618  &mapp[mapi], &nmap, args->flist);
1619  if (error)
1620  goto out_free_map;
1621  if (nmap < 1)
1622  break;
1623  mapi += nmap;
1624  b = mapp[mapi - 1].br_startoff +
1625  mapp[mapi - 1].br_blockcount;
1626  }
1627  } else {
1628  mapi = 0;
1629  mapp = NULL;
1630  }
1631 
1632  /*
1633  * Count the blocks we got, make sure it matches the total.
1634  */
1635  for (i = 0, got = 0; i < mapi; i++)
1636  got += mapp[i].br_blockcount;
1637  if (got != count || mapp[0].br_startoff != *bno ||
1638  mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
1639  *bno + count) {
1640  error = XFS_ERROR(ENOSPC);
1641  goto out_free_map;
1642  }
1643 
1644  /* account for newly allocated blocks in reserved blocks total */
1645  args->total -= dp->i_d.di_nblocks - nblks;
1646 
1647 out_free_map:
1648  if (mapp != &map)
1649  kmem_free(mapp);
1650  return error;
1651 }
1652 
1653 /*
1654  * Add a block to the btree ahead of the file.
1655  * Return the new block number to the caller.
1656  */
1657 int
1658 xfs_da_grow_inode(
1659  struct xfs_da_args *args,
1660  xfs_dablk_t *new_blkno)
1661 {
1662  xfs_fileoff_t bno;
1663  int count;
1664  int error;
1665 
1666  trace_xfs_da_grow_inode(args);
1667 
1668  if (args->whichfork == XFS_DATA_FORK) {
1669  bno = args->dp->i_mount->m_dirleafblk;
1670  count = args->dp->i_mount->m_dirblkfsbs;
1671  } else {
1672  bno = 0;
1673  count = 1;
1674  }
1675 
1676  error = xfs_da_grow_inode_int(args, &bno, count);
1677  if (!error)
1678  *new_blkno = (xfs_dablk_t)bno;
1679  return error;
1680 }
1681 
1682 /*
1683  * Ick. We need to always be able to remove a btree block, even
1684  * if there's no space reservation because the filesystem is full.
1685  * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
1686  * It swaps the target block with the last block in the file. The
1687  * last block in the file can always be removed since it can't cause
1688  * a bmap btree split to do that.
1689  */
1690 STATIC int
1691 xfs_da_swap_lastblock(
1692  xfs_da_args_t *args,
1693  xfs_dablk_t *dead_blknop,
1694  struct xfs_buf **dead_bufp)
1695 {
1696  xfs_dablk_t dead_blkno, last_blkno, sib_blkno, par_blkno;
1697  struct xfs_buf *dead_buf, *last_buf, *sib_buf, *par_buf;
1698  xfs_fileoff_t lastoff;
1699  xfs_inode_t *ip;
1700  xfs_trans_t *tp;
1701  xfs_mount_t *mp;
1702  int error, w, entno, level, dead_level;
1703  xfs_da_blkinfo_t *dead_info, *sib_info;
1704  xfs_da_intnode_t *par_node, *dead_node;
1705  xfs_dir2_leaf_t *dead_leaf2;
1706  xfs_dahash_t dead_hash;
1707 
1708  trace_xfs_da_swap_lastblock(args);
1709 
1710  dead_buf = *dead_bufp;
1711  dead_blkno = *dead_blknop;
1712  tp = args->trans;
1713  ip = args->dp;
1714  w = args->whichfork;
1715  ASSERT(w == XFS_DATA_FORK);
1716  mp = ip->i_mount;
1717  lastoff = mp->m_dirfreeblk;
1718  error = xfs_bmap_last_before(tp, ip, &lastoff, w);
1719  if (error)
1720  return error;
1721  if (unlikely(lastoff == 0)) {
1722  XFS_ERROR_REPORT("xfs_da_swap_lastblock(1)", XFS_ERRLEVEL_LOW,
1723  mp);
1724  return XFS_ERROR(EFSCORRUPTED);
1725  }
1726  /*
1727  * Read the last block in the btree space.
1728  */
1729  last_blkno = (xfs_dablk_t)lastoff - mp->m_dirblkfsbs;
1730  if ((error = xfs_da_read_buf(tp, ip, last_blkno, -1, &last_buf, w)))
1731  return error;
1732  /*
1733  * Copy the last block into the dead buffer and log it.
1734  */
1735  memcpy(dead_buf->b_addr, last_buf->b_addr, mp->m_dirblksize);
1736  xfs_trans_log_buf(tp, dead_buf, 0, mp->m_dirblksize - 1);
1737  dead_info = dead_buf->b_addr;
1738  /*
1739  * Get values from the moved block.
1740  */
1741  if (dead_info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC)) {
1742  dead_leaf2 = (xfs_dir2_leaf_t *)dead_info;
1743  dead_level = 0;
1744  dead_hash = be32_to_cpu(dead_leaf2->ents[be16_to_cpu(dead_leaf2->hdr.count) - 1].hashval);
1745  } else {
1746  ASSERT(dead_info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC));
1747  dead_node = (xfs_da_intnode_t *)dead_info;
1748  dead_level = be16_to_cpu(dead_node->hdr.level);
1749  dead_hash = be32_to_cpu(dead_node->btree[be16_to_cpu(dead_node->hdr.count) - 1].hashval);
1750  }
1751  sib_buf = par_buf = NULL;
1752  /*
1753  * If the moved block has a left sibling, fix up the pointers.
1754  */
1755  if ((sib_blkno = be32_to_cpu(dead_info->back))) {
1756  if ((error = xfs_da_read_buf(tp, ip, sib_blkno, -1, &sib_buf, w)))
1757  goto done;
1758  sib_info = sib_buf->b_addr;
1759  if (unlikely(
1760  be32_to_cpu(sib_info->forw) != last_blkno ||
1761  sib_info->magic != dead_info->magic)) {
1762  XFS_ERROR_REPORT("xfs_da_swap_lastblock(2)",
1763  XFS_ERRLEVEL_LOW, mp);
1764  error = XFS_ERROR(EFSCORRUPTED);
1765  goto done;
1766  }
1767  sib_info->forw = cpu_to_be32(dead_blkno);
1768  xfs_trans_log_buf(tp, sib_buf,
1769  XFS_DA_LOGRANGE(sib_info, &sib_info->forw,
1770  sizeof(sib_info->forw)));
1771  sib_buf = NULL;
1772  }
1773  /*
1774  * If the moved block has a right sibling, fix up the pointers.
1775  */
1776  if ((sib_blkno = be32_to_cpu(dead_info->forw))) {
1777  if ((error = xfs_da_read_buf(tp, ip, sib_blkno, -1, &sib_buf, w)))
1778  goto done;
1779  sib_info = sib_buf->b_addr;
1780  if (unlikely(
1781  be32_to_cpu(sib_info->back) != last_blkno ||
1782  sib_info->magic != dead_info->magic)) {
1783  XFS_ERROR_REPORT("xfs_da_swap_lastblock(3)",
1784  XFS_ERRLEVEL_LOW, mp);
1785  error = XFS_ERROR(EFSCORRUPTED);
1786  goto done;
1787  }
1788  sib_info->back = cpu_to_be32(dead_blkno);
1789  xfs_trans_log_buf(tp, sib_buf,
1790  XFS_DA_LOGRANGE(sib_info, &sib_info->back,
1791  sizeof(sib_info->back)));
1792  sib_buf = NULL;
1793  }
1794  par_blkno = mp->m_dirleafblk;
1795  level = -1;
1796  /*
1797  * Walk down the tree looking for the parent of the moved block.
1798  */
1799  for (;;) {
1800  if ((error = xfs_da_read_buf(tp, ip, par_blkno, -1, &par_buf, w)))
1801  goto done;
1802  par_node = par_buf->b_addr;
1803  if (unlikely(par_node->hdr.info.magic !=
1804  cpu_to_be16(XFS_DA_NODE_MAGIC) ||
1805  (level >= 0 && level != be16_to_cpu(par_node->hdr.level) + 1))) {
1806  XFS_ERROR_REPORT("xfs_da_swap_lastblock(4)",
1807  XFS_ERRLEVEL_LOW, mp);
1808  error = XFS_ERROR(EFSCORRUPTED);
1809  goto done;
1810  }
1811  level = be16_to_cpu(par_node->hdr.level);
1812  for (entno = 0;
1813  entno < be16_to_cpu(par_node->hdr.count) &&
1814  be32_to_cpu(par_node->btree[entno].hashval) < dead_hash;
1815  entno++)
1816  continue;
1817  if (unlikely(entno == be16_to_cpu(par_node->hdr.count))) {
1818  XFS_ERROR_REPORT("xfs_da_swap_lastblock(5)",
1819  XFS_ERRLEVEL_LOW, mp);
1820  error = XFS_ERROR(EFSCORRUPTED);
1821  goto done;
1822  }
1823  par_blkno = be32_to_cpu(par_node->btree[entno].before);
1824  if (level == dead_level + 1)
1825  break;
1826  xfs_trans_brelse(tp, par_buf);
1827  par_buf = NULL;
1828  }
1829  /*
1830  * We're in the right parent block.
1831  * Look for the right entry.
1832  */
1833  for (;;) {
1834  for (;
1835  entno < be16_to_cpu(par_node->hdr.count) &&
1836  be32_to_cpu(par_node->btree[entno].before) != last_blkno;
1837  entno++)
1838  continue;
1839  if (entno < be16_to_cpu(par_node->hdr.count))
1840  break;
1841  par_blkno = be32_to_cpu(par_node->hdr.info.forw);
1842  xfs_trans_brelse(tp, par_buf);
1843  par_buf = NULL;
1844  if (unlikely(par_blkno == 0)) {
1845  XFS_ERROR_REPORT("xfs_da_swap_lastblock(6)",
1846  XFS_ERRLEVEL_LOW, mp);
1847  error = XFS_ERROR(EFSCORRUPTED);
1848  goto done;
1849  }
1850  if ((error = xfs_da_read_buf(tp, ip, par_blkno, -1, &par_buf, w)))
1851  goto done;
1852  par_node = par_buf->b_addr;
1853  if (unlikely(
1854  be16_to_cpu(par_node->hdr.level) != level ||
1855  par_node->hdr.info.magic != cpu_to_be16(XFS_DA_NODE_MAGIC))) {
1856  XFS_ERROR_REPORT("xfs_da_swap_lastblock(7)",
1857  XFS_ERRLEVEL_LOW, mp);
1858  error = XFS_ERROR(EFSCORRUPTED);
1859  goto done;
1860  }
1861  entno = 0;
1862  }
1863  /*
1864  * Update the parent entry pointing to the moved block.
1865  */
1866  par_node->btree[entno].before = cpu_to_be32(dead_blkno);
1867  xfs_trans_log_buf(tp, par_buf,
1868  XFS_DA_LOGRANGE(par_node, &par_node->btree[entno].before,
1869  sizeof(par_node->btree[entno].before)));
1870  *dead_blknop = last_blkno;
1871  *dead_bufp = last_buf;
1872  return 0;
1873 done:
1874  if (par_buf)
1875  xfs_trans_brelse(tp, par_buf);
1876  if (sib_buf)
1877  xfs_trans_brelse(tp, sib_buf);
1878  xfs_trans_brelse(tp, last_buf);
1879  return error;
1880 }
1881 
1882 /*
1883  * Remove a btree block from a directory or attribute.
1884  */
1885 int
1886 xfs_da_shrink_inode(
1887  xfs_da_args_t *args,
1888  xfs_dablk_t dead_blkno,
1889  struct xfs_buf *dead_buf)
1890 {
1891  xfs_inode_t *dp;
1892  int done, error, w, count;
1893  xfs_trans_t *tp;
1894  xfs_mount_t *mp;
1895 
1896  trace_xfs_da_shrink_inode(args);
1897 
1898  dp = args->dp;
1899  w = args->whichfork;
1900  tp = args->trans;
1901  mp = dp->i_mount;
1902  if (w == XFS_DATA_FORK)
1903  count = mp->m_dirblkfsbs;
1904  else
1905  count = 1;
1906  for (;;) {
1907  /*
1908  * Remove extents. If we get ENOSPC for a dir we have to move
1909  * the last block to the place we want to kill.
1910  */
1911  if ((error = xfs_bunmapi(tp, dp, dead_blkno, count,
1912  xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
1913  0, args->firstblock, args->flist,
1914  &done)) == ENOSPC) {
1915  if (w != XFS_DATA_FORK)
1916  break;
1917  if ((error = xfs_da_swap_lastblock(args, &dead_blkno,
1918  &dead_buf)))
1919  break;
1920  } else {
1921  break;
1922  }
1923  }
1924  xfs_trans_binval(tp, dead_buf);
1925  return error;
1926 }
1927 
1928 /*
1929  * See if the mapping(s) for this btree block are valid, i.e.
1930  * don't contain holes, are logically contiguous, and cover the whole range.
1931  */
1932 STATIC int
1933 xfs_da_map_covers_blocks(
1934  int nmap,
1935  xfs_bmbt_irec_t *mapp,
1936  xfs_dablk_t bno,
1937  int count)
1938 {
1939  int i;
1940  xfs_fileoff_t off;
1941 
1942  for (i = 0, off = bno; i < nmap; i++) {
1943  if (mapp[i].br_startblock == HOLESTARTBLOCK ||
1944  mapp[i].br_startblock == DELAYSTARTBLOCK) {
1945  return 0;
1946  }
1947  if (off != mapp[i].br_startoff) {
1948  return 0;
1949  }
1950  off += mapp[i].br_blockcount;
1951  }
1952  return off == bno + count;
1953 }
1954 
1955 /*
1956  * Convert a struct xfs_bmbt_irec to a struct xfs_buf_map.
1957  *
1958  * For the single map case, it is assumed that the caller has provided a pointer
1959  * to a valid xfs_buf_map. For the multiple map case, this function will
1960  * allocate the xfs_buf_map to hold all the maps and replace the caller's single
1961  * map pointer with the allocated map.
1962  */
1963 static int
1964 xfs_buf_map_from_irec(
1965  struct xfs_mount *mp,
1966  struct xfs_buf_map **mapp,
1967  unsigned int *nmaps,
1968  struct xfs_bmbt_irec *irecs,
1969  unsigned int nirecs)
1970 {
1971  struct xfs_buf_map *map;
1972  int i;
1973 
1974  ASSERT(*nmaps == 1);
1975  ASSERT(nirecs >= 1);
1976 
1977  if (nirecs > 1) {
1978  map = kmem_zalloc(nirecs * sizeof(struct xfs_buf_map), KM_SLEEP);
1979  if (!map)
1980  return ENOMEM;
1981  *mapp = map;
1982  }
1983 
1984  *nmaps = nirecs;
1985  map = *mapp;
1986  for (i = 0; i < *nmaps; i++) {
1987  ASSERT(irecs[i].br_startblock != DELAYSTARTBLOCK &&
1988  irecs[i].br_startblock != HOLESTARTBLOCK);
1989  map[i].bm_bn = XFS_FSB_TO_DADDR(mp, irecs[i].br_startblock);
1990  map[i].bm_len = XFS_FSB_TO_BB(mp, irecs[i].br_blockcount);
1991  }
1992  return 0;
1993 }
1994 
1995 /*
1996  * Map the block we are given ready for reading. There are three possible return
1997  * values:
1998  * -1 - will be returned if we land in a hole and mappedbno == -2 so the
1999  * caller knows not to execute a subsequent read.
2000  * 0 - if we mapped the block successfully
2001  * >0 - positive error number if there was an error.
2002  */
2003 static int
2004 xfs_dabuf_map(
2005  struct xfs_trans *trans,
2006  struct xfs_inode *dp,
2007  xfs_dablk_t bno,
2008  xfs_daddr_t mappedbno,
2009  int whichfork,
2010  struct xfs_buf_map **map,
2011  int *nmaps)
2012 {
2013  struct xfs_mount *mp = dp->i_mount;
2014  int nfsb;
2015  int error = 0;
2016  struct xfs_bmbt_irec irec;
2017  struct xfs_bmbt_irec *irecs = &irec;
2018  int nirecs;
2019 
2020  ASSERT(map && *map);
2021  ASSERT(*nmaps == 1);
2022 
2023  nfsb = (whichfork == XFS_DATA_FORK) ? mp->m_dirblkfsbs : 1;
2024 
2025  /*
2026  * Caller doesn't have a mapping. -2 means don't complain
2027  * if we land in a hole.
2028  */
2029  if (mappedbno == -1 || mappedbno == -2) {
2030  /*
2031  * Optimize the one-block case.
2032  */
2033  if (nfsb != 1)
2034  irecs = kmem_zalloc(sizeof(irec) * nfsb, KM_SLEEP);
2035 
2036  nirecs = nfsb;
2037  error = xfs_bmapi_read(dp, (xfs_fileoff_t)bno, nfsb, irecs,
2038  &nirecs, xfs_bmapi_aflag(whichfork));
2039  if (error)
2040  goto out;
2041  } else {
2042  irecs->br_startblock = XFS_DADDR_TO_FSB(mp, mappedbno);
2043  irecs->br_startoff = (xfs_fileoff_t)bno;
2044  irecs->br_blockcount = nfsb;
2045  irecs->br_state = 0;
2046  nirecs = 1;
2047  }
2048 
2049  if (!xfs_da_map_covers_blocks(nirecs, irecs, bno, nfsb)) {
2050  error = mappedbno == -2 ? -1 : XFS_ERROR(EFSCORRUPTED);
2051  if (unlikely(error == EFSCORRUPTED)) {
2052  if (xfs_error_level >= XFS_ERRLEVEL_LOW) {
2053  int i;
2054  xfs_alert(mp, "%s: bno %lld dir: inode %lld",
2055  __func__, (long long)bno,
2056  (long long)dp->i_ino);
2057  for (i = 0; i < *nmaps; i++) {
2058  xfs_alert(mp,
2059 "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",
2060  i,
2061  (long long)irecs[i].br_startoff,
2062  (long long)irecs[i].br_startblock,
2063  (long long)irecs[i].br_blockcount,
2064  irecs[i].br_state);
2065  }
2066  }
2067  XFS_ERROR_REPORT("xfs_da_do_buf(1)",
2068  XFS_ERRLEVEL_LOW, mp);
2069  }
2070  goto out;
2071  }
2072  error = xfs_buf_map_from_irec(mp, map, nmaps, irecs, nirecs);
2073 out:
2074  if (irecs != &irec)
2075  kmem_free(irecs);
2076  return error;
2077 }
2078 
2079 /*
2080  * Get a buffer for the dir/attr block.
2081  */
2082 int
2083 xfs_da_get_buf(
2084  struct xfs_trans *trans,
2085  struct xfs_inode *dp,
2086  xfs_dablk_t bno,
2087  xfs_daddr_t mappedbno,
2088  struct xfs_buf **bpp,
2089  int whichfork)
2090 {
2091  struct xfs_buf *bp;
2092  struct xfs_buf_map map;
2093  struct xfs_buf_map *mapp;
2094  int nmap;
2095  int error;
2096 
2097  *bpp = NULL;
2098  mapp = &map;
2099  nmap = 1;
2100  error = xfs_dabuf_map(trans, dp, bno, mappedbno, whichfork,
2101  &mapp, &nmap);
2102  if (error) {
2103  /* mapping a hole is not an error, but we don't continue */
2104  if (error == -1)
2105  error = 0;
2106  goto out_free;
2107  }
2108 
2109  bp = xfs_trans_get_buf_map(trans, dp->i_mount->m_ddev_targp,
2110  mapp, nmap, 0);
2111  error = bp ? bp->b_error : XFS_ERROR(EIO);
2112  if (error) {
2113  xfs_trans_brelse(trans, bp);
2114  goto out_free;
2115  }
2116 
2117  *bpp = bp;
2118 
2119 out_free:
2120  if (mapp != &map)
2121  kmem_free(mapp);
2122 
2123  return error;
2124 }
2125 
2126 /*
2127  * Get a buffer for the dir/attr block, fill in the contents.
2128  */
2129 int
2130 xfs_da_read_buf(
2131  struct xfs_trans *trans,
2132  struct xfs_inode *dp,
2133  xfs_dablk_t bno,
2134  xfs_daddr_t mappedbno,
2135  struct xfs_buf **bpp,
2136  int whichfork)
2137 {
2138  struct xfs_buf *bp;
2139  struct xfs_buf_map map;
2140  struct xfs_buf_map *mapp;
2141  int nmap;
2142  int error;
2143 
2144  *bpp = NULL;
2145  mapp = &map;
2146  nmap = 1;
2147  error = xfs_dabuf_map(trans, dp, bno, mappedbno, whichfork,
2148  &mapp, &nmap);
2149  if (error) {
2150  /* mapping a hole is not an error, but we don't continue */
2151  if (error == -1)
2152  error = 0;
2153  goto out_free;
2154  }
2155 
2156  error = xfs_trans_read_buf_map(dp->i_mount, trans,
2157  dp->i_mount->m_ddev_targp,
2158  mapp, nmap, 0, &bp);
2159  if (error)
2160  goto out_free;
2161 
2162  if (whichfork == XFS_ATTR_FORK)
2163  xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);
2164  else
2165  xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);
2166 
2167  /*
2168  * This verification code will be moved to a CRC verification callback
2169  * function so just leave it here unchanged until then.
2170  */
2171  {
2172  xfs_dir2_data_hdr_t *hdr = bp->b_addr;
2173  xfs_dir2_free_t *free = bp->b_addr;
2174  xfs_da_blkinfo_t *info = bp->b_addr;
2175  uint magic, magic1;
2176  struct xfs_mount *mp = dp->i_mount;
2177 
2178  magic = be16_to_cpu(info->magic);
2179  magic1 = be32_to_cpu(hdr->magic);
2180  if (unlikely(
2181  XFS_TEST_ERROR((magic != XFS_DA_NODE_MAGIC) &&
2182  (magic != XFS_ATTR_LEAF_MAGIC) &&
2183  (magic != XFS_DIR2_LEAF1_MAGIC) &&
2184  (magic != XFS_DIR2_LEAFN_MAGIC) &&
2185  (magic1 != XFS_DIR2_BLOCK_MAGIC) &&
2186  (magic1 != XFS_DIR2_DATA_MAGIC) &&
2187  (free->hdr.magic != cpu_to_be32(XFS_DIR2_FREE_MAGIC)),
2188  mp, XFS_ERRTAG_DA_READ_BUF,
2189  XFS_RANDOM_DA_READ_BUF))) {
2190  trace_xfs_da_btree_corrupt(bp, _RET_IP_);
2191  XFS_CORRUPTION_ERROR("xfs_da_do_buf(2)",
2192  XFS_ERRLEVEL_LOW, mp, info);
2193  error = XFS_ERROR(EFSCORRUPTED);
2194  xfs_trans_brelse(trans, bp);
2195  goto out_free;
2196  }
2197  }
2198  *bpp = bp;
2199 out_free:
2200  if (mapp != &map)
2201  kmem_free(mapp);
2202 
2203  return error;
2204 }
2205 
2206 /*
2207  * Readahead the dir/attr block.
2208  */
2209 xfs_daddr_t
2210 xfs_da_reada_buf(
2211  struct xfs_trans *trans,
2212  struct xfs_inode *dp,
2213  xfs_dablk_t bno,
2214  int whichfork)
2215 {
2216  xfs_daddr_t mappedbno = -1;
2217  struct xfs_buf_map map;
2218  struct xfs_buf_map *mapp;
2219  int nmap;
2220  int error;
2221 
2222  mapp = &map;
2223  nmap = 1;
2224  error = xfs_dabuf_map(trans, dp, bno, -1, whichfork,
2225  &mapp, &nmap);
2226  if (error) {
2227  /* mapping a hole is not an error, but we don't continue */
2228  if (error == -1)
2229  error = 0;
2230  goto out_free;
2231  }
2232 
2233  mappedbno = mapp[0].bm_bn;
2234  xfs_buf_readahead_map(dp->i_mount->m_ddev_targp, mapp, nmap);
2235 
2236 out_free:
2237  if (mapp != &map)
2238  kmem_free(mapp);
2239 
2240  if (error)
2241  return -1;
2242  return mappedbno;
2243 }
2244 
2245 kmem_zone_t *xfs_da_state_zone; /* anchor for state struct zone */
2246 
2247 /*
2248  * Allocate a dir-state structure.
2249  * We don't put them on the stack since they're large.
2250  */
2251 xfs_da_state_t *
2252 xfs_da_state_alloc(void)
2253 {
2254  return kmem_zone_zalloc(xfs_da_state_zone, KM_NOFS);
2255 }
2256 
2257 /*
2258  * Kill the altpath contents of a da-state structure.
2259  */
2260 STATIC void
2261 xfs_da_state_kill_altpath(xfs_da_state_t *state)
2262 {
2263  int i;
2264 
2265  for (i = 0; i < state->altpath.active; i++)
2266  state->altpath.blk[i].bp = NULL;
2267  state->altpath.active = 0;
2268 }
2269 
2270 /*
2271  * Free a da-state structure.
2272  */
2273 void
2274 xfs_da_state_free(xfs_da_state_t *state)
2275 {
2276  xfs_da_state_kill_altpath(state);
2277 #ifdef DEBUG
2278  memset((char *)state, 0, sizeof(*state));
2279 #endif /* DEBUG */
2280  kmem_zone_free(xfs_da_state_zone, state);
2281 }
Generated on Thu Jan 10 2013 14:50:22 for Linux Kernel by   doxygen 1.8.2