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