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