?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Linux 2.6.14.1
[linux/fpc-iii.git] / fs / xfs / xfs_dir_leaf.c
blobc2ea6171fb0e3dff5e9afa32c0674a4782df0476
1 /*
2 * Copyright (c) 2000-2003 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 /*
34 * xfs_dir_leaf.c
35 *
36 * GROT: figure out how to recover gracefully when bmap returns ENOSPC.
37 */
38
39 #include "xfs.h"
40
41 #include "xfs_macros.h"
42 #include "xfs_types.h"
43 #include "xfs_inum.h"
44 #include "xfs_log.h"
45 #include "xfs_trans.h"
46 #include "xfs_sb.h"
47 #include "xfs_dir.h"
48 #include "xfs_dir2.h"
49 #include "xfs_dmapi.h"
50 #include "xfs_mount.h"
51 #include "xfs_alloc_btree.h"
52 #include "xfs_bmap_btree.h"
53 #include "xfs_ialloc_btree.h"
54 #include "xfs_alloc.h"
55 #include "xfs_btree.h"
56 #include "xfs_attr_sf.h"
57 #include "xfs_dir_sf.h"
58 #include "xfs_dir2_sf.h"
59 #include "xfs_dinode.h"
60 #include "xfs_inode_item.h"
61 #include "xfs_inode.h"
62 #include "xfs_bmap.h"
63 #include "xfs_da_btree.h"
64 #include "xfs_dir_leaf.h"
65 #include "xfs_error.h"
66
67 /*
68 * xfs_dir_leaf.c
69 *
70 * Routines to implement leaf blocks of directories as Btrees of hashed names.
71 */
72
73 /*========================================================================
74 * Function prototypes for the kernel.
75 *========================================================================*/
76
77 /*
78 * Routines used for growing the Btree.
79 */
80 STATIC void xfs_dir_leaf_add_work(xfs_dabuf_t *leaf_buffer, xfs_da_args_t *args,
81 int insertion_index,
82 int freemap_index);
83 STATIC int xfs_dir_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *leaf_buffer,
84 int musthave, int justcheck);
85 STATIC void xfs_dir_leaf_rebalance(xfs_da_state_t *state,
86 xfs_da_state_blk_t *blk1,
87 xfs_da_state_blk_t *blk2);
88 STATIC int xfs_dir_leaf_figure_balance(xfs_da_state_t *state,
89 xfs_da_state_blk_t *leaf_blk_1,
90 xfs_da_state_blk_t *leaf_blk_2,
91 int *number_entries_in_blk1,
92 int *number_namebytes_in_blk1);
93
94 STATIC int xfs_dir_leaf_create(struct xfs_da_args *args,
95 xfs_dablk_t which_block,
96 struct xfs_dabuf **bpp);
97
98 /*
99 * Utility routines.
100 */
101 STATIC void xfs_dir_leaf_moveents(xfs_dir_leafblock_t *src_leaf,
102 int src_start,
103 xfs_dir_leafblock_t *dst_leaf,
104 int dst_start, int move_count,
105 xfs_mount_t *mp);
106
107
108 /*========================================================================
109 * External routines when dirsize < XFS_IFORK_DSIZE(dp).
110 *========================================================================*/
111
112
113 /*
114 * Validate a given inode number.
115 */
116 int
117 xfs_dir_ino_validate(xfs_mount_t *mp, xfs_ino_t ino)
118 {
119 xfs_agblock_t agblkno;
120 xfs_agino_t agino;
121 xfs_agnumber_t agno;
122 int ino_ok;
123 int ioff;
124
125 agno = XFS_INO_TO_AGNO(mp, ino);
126 agblkno = XFS_INO_TO_AGBNO(mp, ino);
127 ioff = XFS_INO_TO_OFFSET(mp, ino);
128 agino = XFS_OFFBNO_TO_AGINO(mp, agblkno, ioff);
129 ino_ok =
130 agno < mp->m_sb.sb_agcount &&
131 agblkno < mp->m_sb.sb_agblocks &&
132 agblkno != 0 &&
133 ioff < (1 << mp->m_sb.sb_inopblog) &&
134 XFS_AGINO_TO_INO(mp, agno, agino) == ino;
135 if (unlikely(XFS_TEST_ERROR(!ino_ok, mp, XFS_ERRTAG_DIR_INO_VALIDATE,
136 XFS_RANDOM_DIR_INO_VALIDATE))) {
137 xfs_fs_cmn_err(CE_WARN, mp, "Invalid inode number 0x%Lx",
138 (unsigned long long) ino);
139 XFS_ERROR_REPORT("xfs_dir_ino_validate", XFS_ERRLEVEL_LOW, mp);
140 return XFS_ERROR(EFSCORRUPTED);
141 }
142 return 0;
143 }
144
145 /*
146 * Create the initial contents of a shortform directory.
147 */
148 int
149 xfs_dir_shortform_create(xfs_da_args_t *args, xfs_ino_t parent)
150 {
151 xfs_dir_sf_hdr_t *hdr;
152 xfs_inode_t *dp;
153
154 dp = args->dp;
155 ASSERT(dp != NULL);
156 ASSERT(dp->i_d.di_size == 0);
157 if (dp->i_d.di_format == XFS_DINODE_FMT_EXTENTS) {
158 dp->i_df.if_flags &= ~XFS_IFEXTENTS; /* just in case */
159 dp->i_d.di_format = XFS_DINODE_FMT_LOCAL;
160 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE);
161 dp->i_df.if_flags |= XFS_IFINLINE;
162 }
163 ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
164 ASSERT(dp->i_df.if_bytes == 0);
165 xfs_idata_realloc(dp, sizeof(*hdr), XFS_DATA_FORK);
166 hdr = (xfs_dir_sf_hdr_t *)dp->i_df.if_u1.if_data;
167 XFS_DIR_SF_PUT_DIRINO(&parent, &hdr->parent);
168
169 hdr->count = 0;
170 dp->i_d.di_size = sizeof(*hdr);
171 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA);
172 return(0);
173 }
174
175 /*
176 * Add a name to the shortform directory structure.
177 * Overflow from the inode has already been checked for.
178 */
179 int
180 xfs_dir_shortform_addname(xfs_da_args_t *args)
181 {
182 xfs_dir_shortform_t *sf;
183 xfs_dir_sf_entry_t *sfe;
184 int i, offset, size;
185 xfs_inode_t *dp;
186
187 dp = args->dp;
188 ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
189 /*
190 * Catch the case where the conversion from shortform to leaf
191 * failed part way through.
192 */
193 if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
194 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
195 return XFS_ERROR(EIO);
196 }
197 ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
198 ASSERT(dp->i_df.if_u1.if_data != NULL);
199 sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
200 sfe = &sf->list[0];
201 for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
202 if (sfe->namelen == args->namelen &&
203 args->name[0] == sfe->name[0] &&
204 memcmp(args->name, sfe->name, args->namelen) == 0)
205 return(XFS_ERROR(EEXIST));
206 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
207 }
208
209 offset = (int)((char *)sfe - (char *)sf);
210 size = XFS_DIR_SF_ENTSIZE_BYNAME(args->namelen);
211 xfs_idata_realloc(dp, size, XFS_DATA_FORK);
212 sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
213 sfe = (xfs_dir_sf_entry_t *)((char *)sf + offset);
214
215 XFS_DIR_SF_PUT_DIRINO(&args->inumber, &sfe->inumber);
216 sfe->namelen = args->namelen;
217 memcpy(sfe->name, args->name, sfe->namelen);
218 INT_MOD(sf->hdr.count, ARCH_CONVERT, +1);
219
220 dp->i_d.di_size += size;
221 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA);
222
223 return(0);
224 }
225
226 /*
227 * Remove a name from the shortform directory structure.
228 */
229 int
230 xfs_dir_shortform_removename(xfs_da_args_t *args)
231 {
232 xfs_dir_shortform_t *sf;
233 xfs_dir_sf_entry_t *sfe;
234 int base, size = 0, i;
235 xfs_inode_t *dp;
236
237 dp = args->dp;
238 ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
239 /*
240 * Catch the case where the conversion from shortform to leaf
241 * failed part way through.
242 */
243 if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
244 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
245 return XFS_ERROR(EIO);
246 }
247 ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
248 ASSERT(dp->i_df.if_u1.if_data != NULL);
249 base = sizeof(xfs_dir_sf_hdr_t);
250 sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
251 sfe = &sf->list[0];
252 for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
253 size = XFS_DIR_SF_ENTSIZE_BYENTRY(sfe);
254 if (sfe->namelen == args->namelen &&
255 sfe->name[0] == args->name[0] &&
256 memcmp(sfe->name, args->name, args->namelen) == 0)
257 break;
258 base += size;
259 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
260 }
261 if (i < 0) {
262 ASSERT(args->oknoent);
263 return(XFS_ERROR(ENOENT));
264 }
265
266 if ((base + size) != dp->i_d.di_size) {
267 memmove(&((char *)sf)[base], &((char *)sf)[base+size],
268 dp->i_d.di_size - (base+size));
269 }
270 INT_MOD(sf->hdr.count, ARCH_CONVERT, -1);
271
272 xfs_idata_realloc(dp, -size, XFS_DATA_FORK);
273 dp->i_d.di_size -= size;
274 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA);
275
276 return(0);
277 }
278
279 /*
280 * Look up a name in a shortform directory structure.
281 */
282 int
283 xfs_dir_shortform_lookup(xfs_da_args_t *args)
284 {
285 xfs_dir_shortform_t *sf;
286 xfs_dir_sf_entry_t *sfe;
287 int i;
288 xfs_inode_t *dp;
289
290 dp = args->dp;
291 ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
292 /*
293 * Catch the case where the conversion from shortform to leaf
294 * failed part way through.
295 */
296 if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
297 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
298 return XFS_ERROR(EIO);
299 }
300 ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
301 ASSERT(dp->i_df.if_u1.if_data != NULL);
302 sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
303 if (args->namelen == 2 &&
304 args->name[0] == '.' && args->name[1] == '.') {
305 XFS_DIR_SF_GET_DIRINO(&sf->hdr.parent, &args->inumber);
306 return(XFS_ERROR(EEXIST));
307 }
308 if (args->namelen == 1 && args->name[0] == '.') {
309 args->inumber = dp->i_ino;
310 return(XFS_ERROR(EEXIST));
311 }
312 sfe = &sf->list[0];
313 for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
314 if (sfe->namelen == args->namelen &&
315 sfe->name[0] == args->name[0] &&
316 memcmp(args->name, sfe->name, args->namelen) == 0) {
317 XFS_DIR_SF_GET_DIRINO(&sfe->inumber, &args->inumber);
318 return(XFS_ERROR(EEXIST));
319 }
320 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
321 }
322 ASSERT(args->oknoent);
323 return(XFS_ERROR(ENOENT));
324 }
325
326 /*
327 * Convert from using the shortform to the leaf.
328 */
329 int
330 xfs_dir_shortform_to_leaf(xfs_da_args_t *iargs)
331 {
332 xfs_inode_t *dp;
333 xfs_dir_shortform_t *sf;
334 xfs_dir_sf_entry_t *sfe;
335 xfs_da_args_t args;
336 xfs_ino_t inumber;
337 char *tmpbuffer;
338 int retval, i, size;
339 xfs_dablk_t blkno;
340 xfs_dabuf_t *bp;
341
342 dp = iargs->dp;
343 /*
344 * Catch the case where the conversion from shortform to leaf
345 * failed part way through.
346 */
347 if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
348 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
349 return XFS_ERROR(EIO);
350 }
351 ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
352 ASSERT(dp->i_df.if_u1.if_data != NULL);
353 size = dp->i_df.if_bytes;
354 tmpbuffer = kmem_alloc(size, KM_SLEEP);
355 ASSERT(tmpbuffer != NULL);
356
357 memcpy(tmpbuffer, dp->i_df.if_u1.if_data, size);
358
359 sf = (xfs_dir_shortform_t *)tmpbuffer;
360 XFS_DIR_SF_GET_DIRINO(&sf->hdr.parent, &inumber);
361
362 xfs_idata_realloc(dp, -size, XFS_DATA_FORK);
363 dp->i_d.di_size = 0;
364 xfs_trans_log_inode(iargs->trans, dp, XFS_ILOG_CORE);
365 retval = xfs_da_grow_inode(iargs, &blkno);
366 if (retval)
367 goto out;
368
369 ASSERT(blkno == 0);
370 retval = xfs_dir_leaf_create(iargs, blkno, &bp);
371 if (retval)
372 goto out;
373 xfs_da_buf_done(bp);
374
375 args.name = ".";
376 args.namelen = 1;
377 args.hashval = xfs_dir_hash_dot;
378 args.inumber = dp->i_ino;
379 args.dp = dp;
380 args.firstblock = iargs->firstblock;
381 args.flist = iargs->flist;
382 args.total = iargs->total;
383 args.whichfork = XFS_DATA_FORK;
384 args.trans = iargs->trans;
385 args.justcheck = 0;
386 args.addname = args.oknoent = 1;
387 retval = xfs_dir_leaf_addname(&args);
388 if (retval)
389 goto out;
390
391 args.name = "..";
392 args.namelen = 2;
393 args.hashval = xfs_dir_hash_dotdot;
394 args.inumber = inumber;
395 retval = xfs_dir_leaf_addname(&args);
396 if (retval)
397 goto out;
398
399 sfe = &sf->list[0];
400 for (i = 0; i < INT_GET(sf->hdr.count, ARCH_CONVERT); i++) {
401 args.name = (char *)(sfe->name);
402 args.namelen = sfe->namelen;
403 args.hashval = xfs_da_hashname((char *)(sfe->name),
404 sfe->namelen);
405 XFS_DIR_SF_GET_DIRINO(&sfe->inumber, &args.inumber);
406 retval = xfs_dir_leaf_addname(&args);
407 if (retval)
408 goto out;
409 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
410 }
411 retval = 0;
412
413 out:
414 kmem_free(tmpbuffer, size);
415 return(retval);
416 }
417
418 STATIC int
419 xfs_dir_shortform_compare(const void *a, const void *b)
420 {
421 xfs_dir_sf_sort_t *sa, *sb;
422
423 sa = (xfs_dir_sf_sort_t *)a;
424 sb = (xfs_dir_sf_sort_t *)b;
425 if (sa->hash < sb->hash)
426 return -1;
427 else if (sa->hash > sb->hash)
428 return 1;
429 else
430 return sa->entno - sb->entno;
431 }
432
433 /*
434 * Copy out directory entries for getdents(), for shortform directories.
435 */
436 /*ARGSUSED*/
437 int
438 xfs_dir_shortform_getdents(xfs_inode_t *dp, uio_t *uio, int *eofp,
439 xfs_dirent_t *dbp, xfs_dir_put_t put)
440 {
441 xfs_dir_shortform_t *sf;
442 xfs_dir_sf_entry_t *sfe;
443 int retval, i, sbsize, nsbuf, lastresid=0, want_entno;
444 xfs_mount_t *mp;
445 xfs_dahash_t cookhash, hash;
446 xfs_dir_put_args_t p;
447 xfs_dir_sf_sort_t *sbuf, *sbp;
448
449 mp = dp->i_mount;
450 sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
451 cookhash = XFS_DA_COOKIE_HASH(mp, uio->uio_offset);
452 want_entno = XFS_DA_COOKIE_ENTRY(mp, uio->uio_offset);
453 nsbuf = INT_GET(sf->hdr.count, ARCH_CONVERT) + 2;
454 sbsize = (nsbuf + 1) * sizeof(*sbuf);
455 sbp = sbuf = kmem_alloc(sbsize, KM_SLEEP);
456
457 xfs_dir_trace_g_du("sf: start", dp, uio);
458
459 /*
460 * Collect all the entries into the buffer.
461 * Entry 0 is .
462 */
463 sbp->entno = 0;
464 sbp->seqno = 0;
465 sbp->hash = xfs_dir_hash_dot;
466 sbp->ino = dp->i_ino;
467 sbp->name = ".";
468 sbp->namelen = 1;
469 sbp++;
470
471 /*
472 * Entry 1 is ..
473 */
474 sbp->entno = 1;
475 sbp->seqno = 0;
476 sbp->hash = xfs_dir_hash_dotdot;
477 sbp->ino = XFS_GET_DIR_INO8(sf->hdr.parent);
478 sbp->name = "..";
479 sbp->namelen = 2;
480 sbp++;
481
482 /*
483 * Scan the directory data for the rest of the entries.
484 */
485 for (i = 0, sfe = &sf->list[0];
486 i < INT_GET(sf->hdr.count, ARCH_CONVERT); i++) {
487
488 if (unlikely(
489 ((char *)sfe < (char *)sf) ||
490 ((char *)sfe >= ((char *)sf + dp->i_df.if_bytes)))) {
491 xfs_dir_trace_g_du("sf: corrupted", dp, uio);
492 XFS_CORRUPTION_ERROR("xfs_dir_shortform_getdents",
493 XFS_ERRLEVEL_LOW, mp, sfe);
494 kmem_free(sbuf, sbsize);
495 return XFS_ERROR(EFSCORRUPTED);
496 }
497
498 sbp->entno = i + 2;
499 sbp->seqno = 0;
500 sbp->hash = xfs_da_hashname((char *)sfe->name, sfe->namelen);
501 sbp->ino = XFS_GET_DIR_INO8(sfe->inumber);
502 sbp->name = (char *)sfe->name;
503 sbp->namelen = sfe->namelen;
504 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
505 sbp++;
506 }
507
508 /*
509 * Sort the entries on hash then entno.
510 */
511 qsort(sbuf, nsbuf, sizeof(*sbuf), xfs_dir_shortform_compare);
512 /*
513 * Stuff in last entry.
514 */
515 sbp->entno = nsbuf;
516 sbp->hash = XFS_DA_MAXHASH;
517 sbp->seqno = 0;
518 /*
519 * Figure out the sequence numbers in case there's a hash duplicate.
520 */
521 for (hash = sbuf->hash, sbp = sbuf + 1;
522 sbp < &sbuf[nsbuf + 1]; sbp++) {
523 if (sbp->hash == hash)
524 sbp->seqno = sbp[-1].seqno + 1;
525 else
526 hash = sbp->hash;
527 }
528
529 /*
530 * Set up put routine.
531 */
532 p.dbp = dbp;
533 p.put = put;
534 p.uio = uio;
535
536 /*
537 * Find our place.
538 */
539 for (sbp = sbuf; sbp < &sbuf[nsbuf + 1]; sbp++) {
540 if (sbp->hash > cookhash ||
541 (sbp->hash == cookhash && sbp->seqno >= want_entno))
542 break;
543 }
544
545 /*
546 * Did we fail to find anything? We stop at the last entry,
547 * the one we put maxhash into.
548 */
549 if (sbp == &sbuf[nsbuf]) {
550 kmem_free(sbuf, sbsize);
551 xfs_dir_trace_g_du("sf: hash beyond end", dp, uio);
552 uio->uio_offset = XFS_DA_MAKE_COOKIE(mp, 0, 0, XFS_DA_MAXHASH);
553 *eofp = 1;
554 return 0;
555 }
556
557 /*
558 * Loop putting entries into the user buffer.
559 */
560 while (sbp < &sbuf[nsbuf]) {
561 /*
562 * Save the first resid in a run of equal-hashval entries
563 * so that we can back them out if they don't all fit.
564 */
565 if (sbp->seqno == 0 || sbp == sbuf)
566 lastresid = uio->uio_resid;
567 XFS_PUT_COOKIE(p.cook, mp, 0, sbp[1].seqno, sbp[1].hash);
568 p.ino = sbp->ino;
569 #if XFS_BIG_INUMS
570 p.ino += mp->m_inoadd;
571 #endif
572 p.name = sbp->name;
573 p.namelen = sbp->namelen;
574 retval = p.put(&p);
575 if (!p.done) {
576 uio->uio_offset =
577 XFS_DA_MAKE_COOKIE(mp, 0, 0, sbp->hash);
578 kmem_free(sbuf, sbsize);
579 uio->uio_resid = lastresid;
580 xfs_dir_trace_g_du("sf: E-O-B", dp, uio);
581 return retval;
582 }
583 sbp++;
584 }
585 kmem_free(sbuf, sbsize);
586 uio->uio_offset = p.cook.o;
587 *eofp = 1;
588 xfs_dir_trace_g_du("sf: E-O-F", dp, uio);
589 return 0;
590 }
591
592 /*
593 * Look up a name in a shortform directory structure, replace the inode number.
594 */
595 int
596 xfs_dir_shortform_replace(xfs_da_args_t *args)
597 {
598 xfs_dir_shortform_t *sf;
599 xfs_dir_sf_entry_t *sfe;
600 xfs_inode_t *dp;
601 int i;
602
603 dp = args->dp;
604 ASSERT(dp->i_df.if_flags & XFS_IFINLINE);
605 /*
606 * Catch the case where the conversion from shortform to leaf
607 * failed part way through.
608 */
609 if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) {
610 ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount));
611 return XFS_ERROR(EIO);
612 }
613 ASSERT(dp->i_df.if_bytes == dp->i_d.di_size);
614 ASSERT(dp->i_df.if_u1.if_data != NULL);
615 sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data;
616 if (args->namelen == 2 &&
617 args->name[0] == '.' && args->name[1] == '.') {
618 /* XXX - replace assert? */
619 XFS_DIR_SF_PUT_DIRINO(&args->inumber, &sf->hdr.parent);
620 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_DDATA);
621 return(0);
622 }
623 ASSERT(args->namelen != 1 || args->name[0] != '.');
624 sfe = &sf->list[0];
625 for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) {
626 if (sfe->namelen == args->namelen &&
627 sfe->name[0] == args->name[0] &&
628 memcmp(args->name, sfe->name, args->namelen) == 0) {
629 ASSERT(memcmp((char *)&args->inumber,
630 (char *)&sfe->inumber, sizeof(xfs_ino_t)));
631 XFS_DIR_SF_PUT_DIRINO(&args->inumber, &sfe->inumber);
632 xfs_trans_log_inode(args->trans, dp, XFS_ILOG_DDATA);
633 return(0);
634 }
635 sfe = XFS_DIR_SF_NEXTENTRY(sfe);
636 }
637 ASSERT(args->oknoent);
638 return(XFS_ERROR(ENOENT));
639 }
640
641 /*
642 * Convert a leaf directory to shortform structure
643 */
644 int
645 xfs_dir_leaf_to_shortform(xfs_da_args_t *iargs)
646 {
647 xfs_dir_leafblock_t *leaf;
648 xfs_dir_leaf_hdr_t *hdr;
649 xfs_dir_leaf_entry_t *entry;
650 xfs_dir_leaf_name_t *namest;
651 xfs_da_args_t args;
652 xfs_inode_t *dp;
653 xfs_ino_t parent;
654 char *tmpbuffer;
655 int retval, i;
656 xfs_dabuf_t *bp;
657
658 dp = iargs->dp;
659 tmpbuffer = kmem_alloc(XFS_LBSIZE(dp->i_mount), KM_SLEEP);
660 ASSERT(tmpbuffer != NULL);
661
662 retval = xfs_da_read_buf(iargs->trans, iargs->dp, 0, -1, &bp,
663 XFS_DATA_FORK);
664 if (retval)
665 goto out;
666 ASSERT(bp != NULL);
667 memcpy(tmpbuffer, bp->data, XFS_LBSIZE(dp->i_mount));
668 leaf = (xfs_dir_leafblock_t *)tmpbuffer;
669 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
670 memset(bp->data, 0, XFS_LBSIZE(dp->i_mount));
671
672 /*
673 * Find and special case the parent inode number
674 */
675 hdr = &leaf->hdr;
676 entry = &leaf->entries[0];
677 for (i = INT_GET(hdr->count, ARCH_CONVERT)-1; i >= 0; entry++, i--) {
678 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
679 if ((entry->namelen == 2) &&
680 (namest->name[0] == '.') &&
681 (namest->name[1] == '.')) {
682 XFS_DIR_SF_GET_DIRINO(&namest->inumber, &parent);
683 entry->nameidx = 0;
684 } else if ((entry->namelen == 1) && (namest->name[0] == '.')) {
685 entry->nameidx = 0;
686 }
687 }
688 retval = xfs_da_shrink_inode(iargs, 0, bp);
689 if (retval)
690 goto out;
691 retval = xfs_dir_shortform_create(iargs, parent);
692 if (retval)
693 goto out;
694
695 /*
696 * Copy the rest of the filenames
697 */
698 entry = &leaf->entries[0];
699 args.dp = dp;
700 args.firstblock = iargs->firstblock;
701 args.flist = iargs->flist;
702 args.total = iargs->total;
703 args.whichfork = XFS_DATA_FORK;
704 args.trans = iargs->trans;
705 args.justcheck = 0;
706 args.addname = args.oknoent = 1;
707 for (i = 0; i < INT_GET(hdr->count, ARCH_CONVERT); entry++, i++) {
708 if (!entry->nameidx)
709 continue;
710 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
711 args.name = (char *)(namest->name);
712 args.namelen = entry->namelen;
713 args.hashval = INT_GET(entry->hashval, ARCH_CONVERT);
714 XFS_DIR_SF_GET_DIRINO(&namest->inumber, &args.inumber);
715 xfs_dir_shortform_addname(&args);
716 }
717
718 out:
719 kmem_free(tmpbuffer, XFS_LBSIZE(dp->i_mount));
720 return(retval);
721 }
722
723 /*
724 * Convert from using a single leaf to a root node and a leaf.
725 */
726 int
727 xfs_dir_leaf_to_node(xfs_da_args_t *args)
728 {
729 xfs_dir_leafblock_t *leaf;
730 xfs_da_intnode_t *node;
731 xfs_inode_t *dp;
732 xfs_dabuf_t *bp1, *bp2;
733 xfs_dablk_t blkno;
734 int retval;
735
736 dp = args->dp;
737 retval = xfs_da_grow_inode(args, &blkno);
738 ASSERT(blkno == 1);
739 if (retval)
740 return(retval);
741 retval = xfs_da_read_buf(args->trans, args->dp, 0, -1, &bp1,
742 XFS_DATA_FORK);
743 if (retval)
744 return(retval);
745 ASSERT(bp1 != NULL);
746 retval = xfs_da_get_buf(args->trans, args->dp, 1, -1, &bp2,
747 XFS_DATA_FORK);
748 if (retval) {
749 xfs_da_buf_done(bp1);
750 return(retval);
751 }
752 ASSERT(bp2 != NULL);
753 memcpy(bp2->data, bp1->data, XFS_LBSIZE(dp->i_mount));
754 xfs_da_buf_done(bp1);
755 xfs_da_log_buf(args->trans, bp2, 0, XFS_LBSIZE(dp->i_mount) - 1);
756
757 /*
758 * Set up the new root node.
759 */
760 retval = xfs_da_node_create(args, 0, 1, &bp1, XFS_DATA_FORK);
761 if (retval) {
762 xfs_da_buf_done(bp2);
763 return(retval);
764 }
765 node = bp1->data;
766 leaf = bp2->data;
767 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
768 INT_SET(node->btree[0].hashval, ARCH_CONVERT, INT_GET(leaf->entries[ INT_GET(leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT));
769 xfs_da_buf_done(bp2);
770 INT_SET(node->btree[0].before, ARCH_CONVERT, blkno);
771 INT_SET(node->hdr.count, ARCH_CONVERT, 1);
772 xfs_da_log_buf(args->trans, bp1,
773 XFS_DA_LOGRANGE(node, &node->btree[0], sizeof(node->btree[0])));
774 xfs_da_buf_done(bp1);
775
776 return(retval);
777 }
778
779
780 /*========================================================================
781 * Routines used for growing the Btree.
782 *========================================================================*/
783
784 /*
785 * Create the initial contents of a leaf directory
786 * or a leaf in a node directory.
787 */
788 STATIC int
789 xfs_dir_leaf_create(xfs_da_args_t *args, xfs_dablk_t blkno, xfs_dabuf_t **bpp)
790 {
791 xfs_dir_leafblock_t *leaf;
792 xfs_dir_leaf_hdr_t *hdr;
793 xfs_inode_t *dp;
794 xfs_dabuf_t *bp;
795 int retval;
796
797 dp = args->dp;
798 ASSERT(dp != NULL);
799 retval = xfs_da_get_buf(args->trans, dp, blkno, -1, &bp, XFS_DATA_FORK);
800 if (retval)
801 return(retval);
802 ASSERT(bp != NULL);
803 leaf = bp->data;
804 memset((char *)leaf, 0, XFS_LBSIZE(dp->i_mount));
805 hdr = &leaf->hdr;
806 INT_SET(hdr->info.magic, ARCH_CONVERT, XFS_DIR_LEAF_MAGIC);
807 INT_SET(hdr->firstused, ARCH_CONVERT, XFS_LBSIZE(dp->i_mount));
808 if (!hdr->firstused)
809 INT_SET(hdr->firstused, ARCH_CONVERT, XFS_LBSIZE(dp->i_mount) - 1);
810 INT_SET(hdr->freemap[0].base, ARCH_CONVERT, sizeof(xfs_dir_leaf_hdr_t));
811 INT_SET(hdr->freemap[0].size, ARCH_CONVERT, INT_GET(hdr->firstused, ARCH_CONVERT) - INT_GET(hdr->freemap[0].base, ARCH_CONVERT));
812
813 xfs_da_log_buf(args->trans, bp, 0, XFS_LBSIZE(dp->i_mount) - 1);
814
815 *bpp = bp;
816 return(0);
817 }
818
819 /*
820 * Split the leaf node, rebalance, then add the new entry.
821 */
822 int
823 xfs_dir_leaf_split(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk,
824 xfs_da_state_blk_t *newblk)
825 {
826 xfs_dablk_t blkno;
827 xfs_da_args_t *args;
828 int error;
829
830 /*
831 * Allocate space for a new leaf node.
832 */
833 args = state->args;
834 ASSERT(args != NULL);
835 ASSERT(oldblk->magic == XFS_DIR_LEAF_MAGIC);
836 error = xfs_da_grow_inode(args, &blkno);
837 if (error)
838 return(error);
839 error = xfs_dir_leaf_create(args, blkno, &newblk->bp);
840 if (error)
841 return(error);
842 newblk->blkno = blkno;
843 newblk->magic = XFS_DIR_LEAF_MAGIC;
844
845 /*
846 * Rebalance the entries across the two leaves.
847 */
848 xfs_dir_leaf_rebalance(state, oldblk, newblk);
849 error = xfs_da_blk_link(state, oldblk, newblk);
850 if (error)
851 return(error);
852
853 /*
854 * Insert the new entry in the correct block.
855 */
856 if (state->inleaf) {
857 error = xfs_dir_leaf_add(oldblk->bp, args, oldblk->index);
858 } else {
859 error = xfs_dir_leaf_add(newblk->bp, args, newblk->index);
860 }
861
862 /*
863 * Update last hashval in each block since we added the name.
864 */
865 oldblk->hashval = xfs_dir_leaf_lasthash(oldblk->bp, NULL);
866 newblk->hashval = xfs_dir_leaf_lasthash(newblk->bp, NULL);
867 return(error);
868 }
869
870 /*
871 * Add a name to the leaf directory structure.
872 *
873 * Must take into account fragmented leaves and leaves where spacemap has
874 * lost some freespace information (ie: holes).
875 */
876 int
877 xfs_dir_leaf_add(xfs_dabuf_t *bp, xfs_da_args_t *args, int index)
878 {
879 xfs_dir_leafblock_t *leaf;
880 xfs_dir_leaf_hdr_t *hdr;
881 xfs_dir_leaf_map_t *map;
882 int tablesize, entsize, sum, i, tmp, error;
883
884 leaf = bp->data;
885 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
886 ASSERT((index >= 0) && (index <= INT_GET(leaf->hdr.count, ARCH_CONVERT)));
887 hdr = &leaf->hdr;
888 entsize = XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen);
889
890 /*
891 * Search through freemap for first-fit on new name length.
892 * (may need to figure in size of entry struct too)
893 */
894 tablesize = (INT_GET(hdr->count, ARCH_CONVERT) + 1) * (uint)sizeof(xfs_dir_leaf_entry_t)
895 + (uint)sizeof(xfs_dir_leaf_hdr_t);
896 map = &hdr->freemap[XFS_DIR_LEAF_MAPSIZE-1];
897 for (sum = 0, i = XFS_DIR_LEAF_MAPSIZE-1; i >= 0; map--, i--) {
898 if (tablesize > INT_GET(hdr->firstused, ARCH_CONVERT)) {
899 sum += INT_GET(map->size, ARCH_CONVERT);
900 continue;
901 }
902 if (!map->size)
903 continue; /* no space in this map */
904 tmp = entsize;
905 if (INT_GET(map->base, ARCH_CONVERT) < INT_GET(hdr->firstused, ARCH_CONVERT))
906 tmp += (uint)sizeof(xfs_dir_leaf_entry_t);
907 if (INT_GET(map->size, ARCH_CONVERT) >= tmp) {
908 if (!args->justcheck)
909 xfs_dir_leaf_add_work(bp, args, index, i);
910 return(0);
911 }
912 sum += INT_GET(map->size, ARCH_CONVERT);
913 }
914
915 /*
916 * If there are no holes in the address space of the block,
917 * and we don't have enough freespace, then compaction will do us
918 * no good and we should just give up.
919 */
920 if (!hdr->holes && (sum < entsize))
921 return(XFS_ERROR(ENOSPC));
922
923 /*
924 * Compact the entries to coalesce free space.
925 * Pass the justcheck flag so the checking pass can return
926 * an error, without changing anything, if it won't fit.
927 */
928 error = xfs_dir_leaf_compact(args->trans, bp,
929 args->total == 0 ?
930 entsize +
931 (uint)sizeof(xfs_dir_leaf_entry_t) : 0,
932 args->justcheck);
933 if (error)
934 return(error);
935 /*
936 * After compaction, the block is guaranteed to have only one
937 * free region, in freemap[0]. If it is not big enough, give up.
938 */
939 if (INT_GET(hdr->freemap[0].size, ARCH_CONVERT) <
940 (entsize + (uint)sizeof(xfs_dir_leaf_entry_t)))
941 return(XFS_ERROR(ENOSPC));
942
943 if (!args->justcheck)
944 xfs_dir_leaf_add_work(bp, args, index, 0);
945 return(0);
946 }
947
948 /*
949 * Add a name to a leaf directory structure.
950 */
951 STATIC void
952 xfs_dir_leaf_add_work(xfs_dabuf_t *bp, xfs_da_args_t *args, int index,
953 int mapindex)
954 {
955 xfs_dir_leafblock_t *leaf;
956 xfs_dir_leaf_hdr_t *hdr;
957 xfs_dir_leaf_entry_t *entry;
958 xfs_dir_leaf_name_t *namest;
959 xfs_dir_leaf_map_t *map;
960 /* REFERENCED */
961 xfs_mount_t *mp;
962 int tmp, i;
963
964 leaf = bp->data;
965 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
966 hdr = &leaf->hdr;
967 ASSERT((mapindex >= 0) && (mapindex < XFS_DIR_LEAF_MAPSIZE));
968 ASSERT((index >= 0) && (index <= INT_GET(hdr->count, ARCH_CONVERT)));
969
970 /*
971 * Force open some space in the entry array and fill it in.
972 */
973 entry = &leaf->entries[index];
974 if (index < INT_GET(hdr->count, ARCH_CONVERT)) {
975 tmp = INT_GET(hdr->count, ARCH_CONVERT) - index;
976 tmp *= (uint)sizeof(xfs_dir_leaf_entry_t);
977 memmove(entry + 1, entry, tmp);
978 xfs_da_log_buf(args->trans, bp,
979 XFS_DA_LOGRANGE(leaf, entry, tmp + (uint)sizeof(*entry)));
980 }
981 INT_MOD(hdr->count, ARCH_CONVERT, +1);
982
983 /*
984 * Allocate space for the new string (at the end of the run).
985 */
986 map = &hdr->freemap[mapindex];
987 mp = args->trans->t_mountp;
988 ASSERT(INT_GET(map->base, ARCH_CONVERT) < XFS_LBSIZE(mp));
989 ASSERT(INT_GET(map->size, ARCH_CONVERT) >= XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen));
990 ASSERT(INT_GET(map->size, ARCH_CONVERT) < XFS_LBSIZE(mp));
991 INT_MOD(map->size, ARCH_CONVERT, -(XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen)));
992 INT_SET(entry->nameidx, ARCH_CONVERT, INT_GET(map->base, ARCH_CONVERT) + INT_GET(map->size, ARCH_CONVERT));
993 INT_SET(entry->hashval, ARCH_CONVERT, args->hashval);
994 entry->namelen = args->namelen;
995 xfs_da_log_buf(args->trans, bp,
996 XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry)));
997
998 /*
999 * Copy the string and inode number into the new space.
1000 */
1001 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
1002 XFS_DIR_SF_PUT_DIRINO(&args->inumber, &namest->inumber);
1003 memcpy(namest->name, args->name, args->namelen);
1004 xfs_da_log_buf(args->trans, bp,
1005 XFS_DA_LOGRANGE(leaf, namest, XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry)));
1006
1007 /*
1008 * Update the control info for this leaf node
1009 */
1010 if (INT_GET(entry->nameidx, ARCH_CONVERT) < INT_GET(hdr->firstused, ARCH_CONVERT))
1011 INT_COPY(hdr->firstused, entry->nameidx, ARCH_CONVERT);
1012 ASSERT(INT_GET(hdr->firstused, ARCH_CONVERT) >= ((INT_GET(hdr->count, ARCH_CONVERT)*sizeof(*entry))+sizeof(*hdr)));
1013 tmp = (INT_GET(hdr->count, ARCH_CONVERT)-1) * (uint)sizeof(xfs_dir_leaf_entry_t)
1014 + (uint)sizeof(xfs_dir_leaf_hdr_t);
1015 map = &hdr->freemap[0];
1016 for (i = 0; i < XFS_DIR_LEAF_MAPSIZE; map++, i++) {
1017 if (INT_GET(map->base, ARCH_CONVERT) == tmp) {
1018 INT_MOD(map->base, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_entry_t));
1019 INT_MOD(map->size, ARCH_CONVERT, -((uint)sizeof(xfs_dir_leaf_entry_t)));
1020 }
1021 }
1022 INT_MOD(hdr->namebytes, ARCH_CONVERT, args->namelen);
1023 xfs_da_log_buf(args->trans, bp,
1024 XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr)));
1025 }
1026
1027 /*
1028 * Garbage collect a leaf directory block by copying it to a new buffer.
1029 */
1030 STATIC int
1031 xfs_dir_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *bp, int musthave,
1032 int justcheck)
1033 {
1034 xfs_dir_leafblock_t *leaf_s, *leaf_d;
1035 xfs_dir_leaf_hdr_t *hdr_s, *hdr_d;
1036 xfs_mount_t *mp;
1037 char *tmpbuffer;
1038 char *tmpbuffer2=NULL;
1039 int rval;
1040 int lbsize;
1041
1042 mp = trans->t_mountp;
1043 lbsize = XFS_LBSIZE(mp);
1044 tmpbuffer = kmem_alloc(lbsize, KM_SLEEP);
1045 ASSERT(tmpbuffer != NULL);
1046 memcpy(tmpbuffer, bp->data, lbsize);
1047
1048 /*
1049 * Make a second copy in case xfs_dir_leaf_moveents()
1050 * below destroys the original.
1051 */
1052 if (musthave || justcheck) {
1053 tmpbuffer2 = kmem_alloc(lbsize, KM_SLEEP);
1054 memcpy(tmpbuffer2, bp->data, lbsize);
1055 }
1056 memset(bp->data, 0, lbsize);
1057
1058 /*
1059 * Copy basic information
1060 */
1061 leaf_s = (xfs_dir_leafblock_t *)tmpbuffer;
1062 leaf_d = bp->data;
1063 hdr_s = &leaf_s->hdr;
1064 hdr_d = &leaf_d->hdr;
1065 hdr_d->info = hdr_s->info; /* struct copy */
1066 INT_SET(hdr_d->firstused, ARCH_CONVERT, lbsize);
1067 if (!hdr_d->firstused)
1068 INT_SET(hdr_d->firstused, ARCH_CONVERT, lbsize - 1);
1069 hdr_d->namebytes = 0;
1070 hdr_d->count = 0;
1071 hdr_d->holes = 0;
1072 INT_SET(hdr_d->freemap[0].base, ARCH_CONVERT, sizeof(xfs_dir_leaf_hdr_t));
1073 INT_SET(hdr_d->freemap[0].size, ARCH_CONVERT, INT_GET(hdr_d->firstused, ARCH_CONVERT) - INT_GET(hdr_d->freemap[0].base, ARCH_CONVERT));
1074
1075 /*
1076 * Copy all entry's in the same (sorted) order,
1077 * but allocate filenames packed and in sequence.
1078 * This changes the source (leaf_s) as well.
1079 */
1080 xfs_dir_leaf_moveents(leaf_s, 0, leaf_d, 0, (int)INT_GET(hdr_s->count, ARCH_CONVERT), mp);
1081
1082 if (musthave && INT_GET(hdr_d->freemap[0].size, ARCH_CONVERT) < musthave)
1083 rval = XFS_ERROR(ENOSPC);
1084 else
1085 rval = 0;
1086
1087 if (justcheck || rval == ENOSPC) {
1088 ASSERT(tmpbuffer2);
1089 memcpy(bp->data, tmpbuffer2, lbsize);
1090 } else {
1091 xfs_da_log_buf(trans, bp, 0, lbsize - 1);
1092 }
1093
1094 kmem_free(tmpbuffer, lbsize);
1095 if (musthave || justcheck)
1096 kmem_free(tmpbuffer2, lbsize);
1097 return(rval);
1098 }
1099
1100 /*
1101 * Redistribute the directory entries between two leaf nodes,
1102 * taking into account the size of the new entry.
1103 *
1104 * NOTE: if new block is empty, then it will get the upper half of old block.
1105 */
1106 STATIC void
1107 xfs_dir_leaf_rebalance(xfs_da_state_t *state, xfs_da_state_blk_t *blk1,
1108 xfs_da_state_blk_t *blk2)
1109 {
1110 xfs_da_state_blk_t *tmp_blk;
1111 xfs_dir_leafblock_t *leaf1, *leaf2;
1112 xfs_dir_leaf_hdr_t *hdr1, *hdr2;
1113 int count, totallen, max, space, swap;
1114
1115 /*
1116 * Set up environment.
1117 */
1118 ASSERT(blk1->magic == XFS_DIR_LEAF_MAGIC);
1119 ASSERT(blk2->magic == XFS_DIR_LEAF_MAGIC);
1120 leaf1 = blk1->bp->data;
1121 leaf2 = blk2->bp->data;
1122 ASSERT(INT_GET(leaf1->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1123 ASSERT(INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1124
1125 /*
1126 * Check ordering of blocks, reverse if it makes things simpler.
1127 */
1128 swap = 0;
1129 if (xfs_dir_leaf_order(blk1->bp, blk2->bp)) {
1130 tmp_blk = blk1;
1131 blk1 = blk2;
1132 blk2 = tmp_blk;
1133 leaf1 = blk1->bp->data;
1134 leaf2 = blk2->bp->data;
1135 swap = 1;
1136 }
1137 hdr1 = &leaf1->hdr;
1138 hdr2 = &leaf2->hdr;
1139
1140 /*
1141 * Examine entries until we reduce the absolute difference in
1142 * byte usage between the two blocks to a minimum. Then get
1143 * the direction to copy and the number of elements to move.
1144 */
1145 state->inleaf = xfs_dir_leaf_figure_balance(state, blk1, blk2,
1146 &count, &totallen);
1147 if (swap)
1148 state->inleaf = !state->inleaf;
1149
1150 /*
1151 * Move any entries required from leaf to leaf:
1152 */
1153 if (count < INT_GET(hdr1->count, ARCH_CONVERT)) {
1154 /*
1155 * Figure the total bytes to be added to the destination leaf.
1156 */
1157 count = INT_GET(hdr1->count, ARCH_CONVERT) - count; /* number entries being moved */
1158 space = INT_GET(hdr1->namebytes, ARCH_CONVERT) - totallen;
1159 space += count * ((uint)sizeof(xfs_dir_leaf_name_t)-1);
1160 space += count * (uint)sizeof(xfs_dir_leaf_entry_t);
1161
1162 /*
1163 * leaf2 is the destination, compact it if it looks tight.
1164 */
1165 max = INT_GET(hdr2->firstused, ARCH_CONVERT) - (uint)sizeof(xfs_dir_leaf_hdr_t);
1166 max -= INT_GET(hdr2->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t);
1167 if (space > max) {
1168 xfs_dir_leaf_compact(state->args->trans, blk2->bp,
1169 0, 0);
1170 }
1171
1172 /*
1173 * Move high entries from leaf1 to low end of leaf2.
1174 */
1175 xfs_dir_leaf_moveents(leaf1, INT_GET(hdr1->count, ARCH_CONVERT) - count,
1176 leaf2, 0, count, state->mp);
1177
1178 xfs_da_log_buf(state->args->trans, blk1->bp, 0,
1179 state->blocksize-1);
1180 xfs_da_log_buf(state->args->trans, blk2->bp, 0,
1181 state->blocksize-1);
1182
1183 } else if (count > INT_GET(hdr1->count, ARCH_CONVERT)) {
1184 /*
1185 * Figure the total bytes to be added to the destination leaf.
1186 */
1187 count -= INT_GET(hdr1->count, ARCH_CONVERT); /* number entries being moved */
1188 space = totallen - INT_GET(hdr1->namebytes, ARCH_CONVERT);
1189 space += count * ((uint)sizeof(xfs_dir_leaf_name_t)-1);
1190 space += count * (uint)sizeof(xfs_dir_leaf_entry_t);
1191
1192 /*
1193 * leaf1 is the destination, compact it if it looks tight.
1194 */
1195 max = INT_GET(hdr1->firstused, ARCH_CONVERT) - (uint)sizeof(xfs_dir_leaf_hdr_t);
1196 max -= INT_GET(hdr1->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t);
1197 if (space > max) {
1198 xfs_dir_leaf_compact(state->args->trans, blk1->bp,
1199 0, 0);
1200 }
1201
1202 /*
1203 * Move low entries from leaf2 to high end of leaf1.
1204 */
1205 xfs_dir_leaf_moveents(leaf2, 0, leaf1, (int)INT_GET(hdr1->count, ARCH_CONVERT),
1206 count, state->mp);
1207
1208 xfs_da_log_buf(state->args->trans, blk1->bp, 0,
1209 state->blocksize-1);
1210 xfs_da_log_buf(state->args->trans, blk2->bp, 0,
1211 state->blocksize-1);
1212 }
1213
1214 /*
1215 * Copy out last hashval in each block for B-tree code.
1216 */
1217 blk1->hashval = INT_GET(leaf1->entries[ INT_GET(leaf1->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);
1218 blk2->hashval = INT_GET(leaf2->entries[ INT_GET(leaf2->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);
1219
1220 /*
1221 * Adjust the expected index for insertion.
1222 * GROT: this doesn't work unless blk2 was originally empty.
1223 */
1224 if (!state->inleaf) {
1225 blk2->index = blk1->index - INT_GET(leaf1->hdr.count, ARCH_CONVERT);
1226 }
1227 }
1228
1229 /*
1230 * Examine entries until we reduce the absolute difference in
1231 * byte usage between the two blocks to a minimum.
1232 * GROT: Is this really necessary? With other than a 512 byte blocksize,
1233 * GROT: there will always be enough room in either block for a new entry.
1234 * GROT: Do a double-split for this case?
1235 */
1236 STATIC int
1237 xfs_dir_leaf_figure_balance(xfs_da_state_t *state,
1238 xfs_da_state_blk_t *blk1,
1239 xfs_da_state_blk_t *blk2,
1240 int *countarg, int *namebytesarg)
1241 {
1242 xfs_dir_leafblock_t *leaf1, *leaf2;
1243 xfs_dir_leaf_hdr_t *hdr1, *hdr2;
1244 xfs_dir_leaf_entry_t *entry;
1245 int count, max, totallen, half;
1246 int lastdelta, foundit, tmp;
1247
1248 /*
1249 * Set up environment.
1250 */
1251 leaf1 = blk1->bp->data;
1252 leaf2 = blk2->bp->data;
1253 hdr1 = &leaf1->hdr;
1254 hdr2 = &leaf2->hdr;
1255 foundit = 0;
1256 totallen = 0;
1257
1258 /*
1259 * Examine entries until we reduce the absolute difference in
1260 * byte usage between the two blocks to a minimum.
1261 */
1262 max = INT_GET(hdr1->count, ARCH_CONVERT) + INT_GET(hdr2->count, ARCH_CONVERT);
1263 half = (max+1) * (uint)(sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1);
1264 half += INT_GET(hdr1->namebytes, ARCH_CONVERT) + INT_GET(hdr2->namebytes, ARCH_CONVERT) + state->args->namelen;
1265 half /= 2;
1266 lastdelta = state->blocksize;
1267 entry = &leaf1->entries[0];
1268 for (count = 0; count < max; entry++, count++) {
1269
1270 #define XFS_DIR_ABS(A) (((A) < 0) ? -(A) : (A))
1271 /*
1272 * The new entry is in the first block, account for it.
1273 */
1274 if (count == blk1->index) {
1275 tmp = totallen + (uint)sizeof(*entry)
1276 + XFS_DIR_LEAF_ENTSIZE_BYNAME(state->args->namelen);
1277 if (XFS_DIR_ABS(half - tmp) > lastdelta)
1278 break;
1279 lastdelta = XFS_DIR_ABS(half - tmp);
1280 totallen = tmp;
1281 foundit = 1;
1282 }
1283
1284 /*
1285 * Wrap around into the second block if necessary.
1286 */
1287 if (count == INT_GET(hdr1->count, ARCH_CONVERT)) {
1288 leaf1 = leaf2;
1289 entry = &leaf1->entries[0];
1290 }
1291
1292 /*
1293 * Figure out if next leaf entry would be too much.
1294 */
1295 tmp = totallen + (uint)sizeof(*entry)
1296 + XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry);
1297 if (XFS_DIR_ABS(half - tmp) > lastdelta)
1298 break;
1299 lastdelta = XFS_DIR_ABS(half - tmp);
1300 totallen = tmp;
1301 #undef XFS_DIR_ABS
1302 }
1303
1304 /*
1305 * Calculate the number of namebytes that will end up in lower block.
1306 * If new entry not in lower block, fix up the count.
1307 */
1308 totallen -=
1309 count * (uint)(sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1);
1310 if (foundit) {
1311 totallen -= (sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1) +
1312 state->args->namelen;
1313 }
1314
1315 *countarg = count;
1316 *namebytesarg = totallen;
1317 return(foundit);
1318 }
1319
1320 /*========================================================================
1321 * Routines used for shrinking the Btree.
1322 *========================================================================*/
1323
1324 /*
1325 * Check a leaf block and its neighbors to see if the block should be
1326 * collapsed into one or the other neighbor. Always keep the block
1327 * with the smaller block number.
1328 * If the current block is over 50% full, don't try to join it, return 0.
1329 * If the block is empty, fill in the state structure and return 2.
1330 * If it can be collapsed, fill in the state structure and return 1.
1331 * If nothing can be done, return 0.
1332 */
1333 int
1334 xfs_dir_leaf_toosmall(xfs_da_state_t *state, int *action)
1335 {
1336 xfs_dir_leafblock_t *leaf;
1337 xfs_da_state_blk_t *blk;
1338 xfs_da_blkinfo_t *info;
1339 int count, bytes, forward, error, retval, i;
1340 xfs_dablk_t blkno;
1341 xfs_dabuf_t *bp;
1342
1343 /*
1344 * Check for the degenerate case of the block being over 50% full.
1345 * If so, it's not worth even looking to see if we might be able
1346 * to coalesce with a sibling.
1347 */
1348 blk = &state->path.blk[ state->path.active-1 ];
1349 info = blk->bp->data;
1350 ASSERT(INT_GET(info->magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1351 leaf = (xfs_dir_leafblock_t *)info;
1352 count = INT_GET(leaf->hdr.count, ARCH_CONVERT);
1353 bytes = (uint)sizeof(xfs_dir_leaf_hdr_t) +
1354 count * (uint)sizeof(xfs_dir_leaf_entry_t) +
1355 count * ((uint)sizeof(xfs_dir_leaf_name_t)-1) +
1356 INT_GET(leaf->hdr.namebytes, ARCH_CONVERT);
1357 if (bytes > (state->blocksize >> 1)) {
1358 *action = 0; /* blk over 50%, don't try to join */
1359 return(0);
1360 }
1361
1362 /*
1363 * Check for the degenerate case of the block being empty.
1364 * If the block is empty, we'll simply delete it, no need to
1365 * coalesce it with a sibling block. We choose (aribtrarily)
1366 * to merge with the forward block unless it is NULL.
1367 */
1368 if (count == 0) {
1369 /*
1370 * Make altpath point to the block we want to keep and
1371 * path point to the block we want to drop (this one).
1372 */
1373 forward = info->forw;
1374 memcpy(&state->altpath, &state->path, sizeof(state->path));
1375 error = xfs_da_path_shift(state, &state->altpath, forward,
1376 0, &retval);
1377 if (error)
1378 return(error);
1379 if (retval) {
1380 *action = 0;
1381 } else {
1382 *action = 2;
1383 }
1384 return(0);
1385 }
1386
1387 /*
1388 * Examine each sibling block to see if we can coalesce with
1389 * at least 25% free space to spare. We need to figure out
1390 * whether to merge with the forward or the backward block.
1391 * We prefer coalescing with the lower numbered sibling so as
1392 * to shrink a directory over time.
1393 */
1394 forward = (INT_GET(info->forw, ARCH_CONVERT) < INT_GET(info->back, ARCH_CONVERT)); /* start with smaller blk num */
1395 for (i = 0; i < 2; forward = !forward, i++) {
1396 if (forward)
1397 blkno = INT_GET(info->forw, ARCH_CONVERT);
1398 else
1399 blkno = INT_GET(info->back, ARCH_CONVERT);
1400 if (blkno == 0)
1401 continue;
1402 error = xfs_da_read_buf(state->args->trans, state->args->dp,
1403 blkno, -1, &bp,
1404 XFS_DATA_FORK);
1405 if (error)
1406 return(error);
1407 ASSERT(bp != NULL);
1408
1409 leaf = (xfs_dir_leafblock_t *)info;
1410 count = INT_GET(leaf->hdr.count, ARCH_CONVERT);
1411 bytes = state->blocksize - (state->blocksize>>2);
1412 bytes -= INT_GET(leaf->hdr.namebytes, ARCH_CONVERT);
1413 leaf = bp->data;
1414 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1415 count += INT_GET(leaf->hdr.count, ARCH_CONVERT);
1416 bytes -= INT_GET(leaf->hdr.namebytes, ARCH_CONVERT);
1417 bytes -= count * ((uint)sizeof(xfs_dir_leaf_name_t) - 1);
1418 bytes -= count * (uint)sizeof(xfs_dir_leaf_entry_t);
1419 bytes -= (uint)sizeof(xfs_dir_leaf_hdr_t);
1420 if (bytes >= 0)
1421 break; /* fits with at least 25% to spare */
1422
1423 xfs_da_brelse(state->args->trans, bp);
1424 }
1425 if (i >= 2) {
1426 *action = 0;
1427 return(0);
1428 }
1429 xfs_da_buf_done(bp);
1430
1431 /*
1432 * Make altpath point to the block we want to keep (the lower
1433 * numbered block) and path point to the block we want to drop.
1434 */
1435 memcpy(&state->altpath, &state->path, sizeof(state->path));
1436 if (blkno < blk->blkno) {
1437 error = xfs_da_path_shift(state, &state->altpath, forward,
1438 0, &retval);
1439 } else {
1440 error = xfs_da_path_shift(state, &state->path, forward,
1441 0, &retval);
1442 }
1443 if (error)
1444 return(error);
1445 if (retval) {
1446 *action = 0;
1447 } else {
1448 *action = 1;
1449 }
1450 return(0);
1451 }
1452
1453 /*
1454 * Remove a name from the leaf directory structure.
1455 *
1456 * Return 1 if leaf is less than 37% full, 0 if >= 37% full.
1457 * If two leaves are 37% full, when combined they will leave 25% free.
1458 */
1459 int
1460 xfs_dir_leaf_remove(xfs_trans_t *trans, xfs_dabuf_t *bp, int index)
1461 {
1462 xfs_dir_leafblock_t *leaf;
1463 xfs_dir_leaf_hdr_t *hdr;
1464 xfs_dir_leaf_map_t *map;
1465 xfs_dir_leaf_entry_t *entry;
1466 xfs_dir_leaf_name_t *namest;
1467 int before, after, smallest, entsize;
1468 int tablesize, tmp, i;
1469 xfs_mount_t *mp;
1470
1471 leaf = bp->data;
1472 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1473 hdr = &leaf->hdr;
1474 mp = trans->t_mountp;
1475 ASSERT((INT_GET(hdr->count, ARCH_CONVERT) > 0) && (INT_GET(hdr->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8)));
1476 ASSERT((index >= 0) && (index < INT_GET(hdr->count, ARCH_CONVERT)));
1477 ASSERT(INT_GET(hdr->firstused, ARCH_CONVERT) >= ((INT_GET(hdr->count, ARCH_CONVERT)*sizeof(*entry))+sizeof(*hdr)));
1478 entry = &leaf->entries[index];
1479 ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) >= INT_GET(hdr->firstused, ARCH_CONVERT));
1480 ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) < XFS_LBSIZE(mp));
1481
1482 /*
1483 * Scan through free region table:
1484 * check for adjacency of free'd entry with an existing one,
1485 * find smallest free region in case we need to replace it,
1486 * adjust any map that borders the entry table,
1487 */
1488 tablesize = INT_GET(hdr->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t)
1489 + (uint)sizeof(xfs_dir_leaf_hdr_t);
1490 map = &hdr->freemap[0];
1491 tmp = INT_GET(map->size, ARCH_CONVERT);
1492 before = after = -1;
1493 smallest = XFS_DIR_LEAF_MAPSIZE - 1;
1494 entsize = XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry);
1495 for (i = 0; i < XFS_DIR_LEAF_MAPSIZE; map++, i++) {
1496 ASSERT(INT_GET(map->base, ARCH_CONVERT) < XFS_LBSIZE(mp));
1497 ASSERT(INT_GET(map->size, ARCH_CONVERT) < XFS_LBSIZE(mp));
1498 if (INT_GET(map->base, ARCH_CONVERT) == tablesize) {
1499 INT_MOD(map->base, ARCH_CONVERT, -((uint)sizeof(xfs_dir_leaf_entry_t)));
1500 INT_MOD(map->size, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_entry_t));
1501 }
1502
1503 if ((INT_GET(map->base, ARCH_CONVERT) + INT_GET(map->size, ARCH_CONVERT)) == INT_GET(entry->nameidx, ARCH_CONVERT)) {
1504 before = i;
1505 } else if (INT_GET(map->base, ARCH_CONVERT) == (INT_GET(entry->nameidx, ARCH_CONVERT) + entsize)) {
1506 after = i;
1507 } else if (INT_GET(map->size, ARCH_CONVERT) < tmp) {
1508 tmp = INT_GET(map->size, ARCH_CONVERT);
1509 smallest = i;
1510 }
1511 }
1512
1513 /*
1514 * Coalesce adjacent freemap regions,
1515 * or replace the smallest region.
1516 */
1517 if ((before >= 0) || (after >= 0)) {
1518 if ((before >= 0) && (after >= 0)) {
1519 map = &hdr->freemap[before];
1520 INT_MOD(map->size, ARCH_CONVERT, entsize);
1521 INT_MOD(map->size, ARCH_CONVERT, INT_GET(hdr->freemap[after].size, ARCH_CONVERT));
1522 hdr->freemap[after].base = 0;
1523 hdr->freemap[after].size = 0;
1524 } else if (before >= 0) {
1525 map = &hdr->freemap[before];
1526 INT_MOD(map->size, ARCH_CONVERT, entsize);
1527 } else {
1528 map = &hdr->freemap[after];
1529 INT_COPY(map->base, entry->nameidx, ARCH_CONVERT);
1530 INT_MOD(map->size, ARCH_CONVERT, entsize);
1531 }
1532 } else {
1533 /*
1534 * Replace smallest region (if it is smaller than free'd entry)
1535 */
1536 map = &hdr->freemap[smallest];
1537 if (INT_GET(map->size, ARCH_CONVERT) < entsize) {
1538 INT_COPY(map->base, entry->nameidx, ARCH_CONVERT);
1539 INT_SET(map->size, ARCH_CONVERT, entsize);
1540 }
1541 }
1542
1543 /*
1544 * Did we remove the first entry?
1545 */
1546 if (INT_GET(entry->nameidx, ARCH_CONVERT) == INT_GET(hdr->firstused, ARCH_CONVERT))
1547 smallest = 1;
1548 else
1549 smallest = 0;
1550
1551 /*
1552 * Compress the remaining entries and zero out the removed stuff.
1553 */
1554 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
1555 memset((char *)namest, 0, entsize);
1556 xfs_da_log_buf(trans, bp, XFS_DA_LOGRANGE(leaf, namest, entsize));
1557
1558 INT_MOD(hdr->namebytes, ARCH_CONVERT, -(entry->namelen));
1559 tmp = (INT_GET(hdr->count, ARCH_CONVERT) - index) * (uint)sizeof(xfs_dir_leaf_entry_t);
1560 memmove(entry, entry + 1, tmp);
1561 INT_MOD(hdr->count, ARCH_CONVERT, -1);
1562 xfs_da_log_buf(trans, bp,
1563 XFS_DA_LOGRANGE(leaf, entry, tmp + (uint)sizeof(*entry)));
1564 entry = &leaf->entries[INT_GET(hdr->count, ARCH_CONVERT)];
1565 memset((char *)entry, 0, sizeof(xfs_dir_leaf_entry_t));
1566
1567 /*
1568 * If we removed the first entry, re-find the first used byte
1569 * in the name area. Note that if the entry was the "firstused",
1570 * then we don't have a "hole" in our block resulting from
1571 * removing the name.
1572 */
1573 if (smallest) {
1574 tmp = XFS_LBSIZE(mp);
1575 entry = &leaf->entries[0];
1576 for (i = INT_GET(hdr->count, ARCH_CONVERT)-1; i >= 0; entry++, i--) {
1577 ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) >= INT_GET(hdr->firstused, ARCH_CONVERT));
1578 ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) < XFS_LBSIZE(mp));
1579 if (INT_GET(entry->nameidx, ARCH_CONVERT) < tmp)
1580 tmp = INT_GET(entry->nameidx, ARCH_CONVERT);
1581 }
1582 INT_SET(hdr->firstused, ARCH_CONVERT, tmp);
1583 if (!hdr->firstused)
1584 INT_SET(hdr->firstused, ARCH_CONVERT, tmp - 1);
1585 } else {
1586 hdr->holes = 1; /* mark as needing compaction */
1587 }
1588
1589 xfs_da_log_buf(trans, bp, XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr)));
1590
1591 /*
1592 * Check if leaf is less than 50% full, caller may want to
1593 * "join" the leaf with a sibling if so.
1594 */
1595 tmp = (uint)sizeof(xfs_dir_leaf_hdr_t);
1596 tmp += INT_GET(leaf->hdr.count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t);
1597 tmp += INT_GET(leaf->hdr.count, ARCH_CONVERT) * ((uint)sizeof(xfs_dir_leaf_name_t) - 1);
1598 tmp += INT_GET(leaf->hdr.namebytes, ARCH_CONVERT);
1599 if (tmp < mp->m_dir_magicpct)
1600 return(1); /* leaf is < 37% full */
1601 return(0);
1602 }
1603
1604 /*
1605 * Move all the directory entries from drop_leaf into save_leaf.
1606 */
1607 void
1608 xfs_dir_leaf_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
1609 xfs_da_state_blk_t *save_blk)
1610 {
1611 xfs_dir_leafblock_t *drop_leaf, *save_leaf, *tmp_leaf;
1612 xfs_dir_leaf_hdr_t *drop_hdr, *save_hdr, *tmp_hdr;
1613 xfs_mount_t *mp;
1614 char *tmpbuffer;
1615
1616 /*
1617 * Set up environment.
1618 */
1619 mp = state->mp;
1620 ASSERT(drop_blk->magic == XFS_DIR_LEAF_MAGIC);
1621 ASSERT(save_blk->magic == XFS_DIR_LEAF_MAGIC);
1622 drop_leaf = drop_blk->bp->data;
1623 save_leaf = save_blk->bp->data;
1624 ASSERT(INT_GET(drop_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1625 ASSERT(INT_GET(save_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1626 drop_hdr = &drop_leaf->hdr;
1627 save_hdr = &save_leaf->hdr;
1628
1629 /*
1630 * Save last hashval from dying block for later Btree fixup.
1631 */
1632 drop_blk->hashval = INT_GET(drop_leaf->entries[ drop_leaf->hdr.count-1 ].hashval, ARCH_CONVERT);
1633
1634 /*
1635 * Check if we need a temp buffer, or can we do it in place.
1636 * Note that we don't check "leaf" for holes because we will
1637 * always be dropping it, toosmall() decided that for us already.
1638 */
1639 if (save_hdr->holes == 0) {
1640 /*
1641 * dest leaf has no holes, so we add there. May need
1642 * to make some room in the entry array.
1643 */
1644 if (xfs_dir_leaf_order(save_blk->bp, drop_blk->bp)) {
1645 xfs_dir_leaf_moveents(drop_leaf, 0, save_leaf, 0,
1646 (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp);
1647 } else {
1648 xfs_dir_leaf_moveents(drop_leaf, 0,
1649 save_leaf, INT_GET(save_hdr->count, ARCH_CONVERT),
1650 (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp);
1651 }
1652 } else {
1653 /*
1654 * Destination has holes, so we make a temporary copy
1655 * of the leaf and add them both to that.
1656 */
1657 tmpbuffer = kmem_alloc(state->blocksize, KM_SLEEP);
1658 ASSERT(tmpbuffer != NULL);
1659 memset(tmpbuffer, 0, state->blocksize);
1660 tmp_leaf = (xfs_dir_leafblock_t *)tmpbuffer;
1661 tmp_hdr = &tmp_leaf->hdr;
1662 tmp_hdr->info = save_hdr->info; /* struct copy */
1663 tmp_hdr->count = 0;
1664 INT_SET(tmp_hdr->firstused, ARCH_CONVERT, state->blocksize);
1665 if (!tmp_hdr->firstused)
1666 INT_SET(tmp_hdr->firstused, ARCH_CONVERT, state->blocksize - 1);
1667 tmp_hdr->namebytes = 0;
1668 if (xfs_dir_leaf_order(save_blk->bp, drop_blk->bp)) {
1669 xfs_dir_leaf_moveents(drop_leaf, 0, tmp_leaf, 0,
1670 (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp);
1671 xfs_dir_leaf_moveents(save_leaf, 0,
1672 tmp_leaf, INT_GET(tmp_leaf->hdr.count, ARCH_CONVERT),
1673 (int)INT_GET(save_hdr->count, ARCH_CONVERT), mp);
1674 } else {
1675 xfs_dir_leaf_moveents(save_leaf, 0, tmp_leaf, 0,
1676 (int)INT_GET(save_hdr->count, ARCH_CONVERT), mp);
1677 xfs_dir_leaf_moveents(drop_leaf, 0,
1678 tmp_leaf, INT_GET(tmp_leaf->hdr.count, ARCH_CONVERT),
1679 (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp);
1680 }
1681 memcpy(save_leaf, tmp_leaf, state->blocksize);
1682 kmem_free(tmpbuffer, state->blocksize);
1683 }
1684
1685 xfs_da_log_buf(state->args->trans, save_blk->bp, 0,
1686 state->blocksize - 1);
1687
1688 /*
1689 * Copy out last hashval in each block for B-tree code.
1690 */
1691 save_blk->hashval = INT_GET(save_leaf->entries[ INT_GET(save_leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT);
1692 }
1693
1694 /*========================================================================
1695 * Routines used for finding things in the Btree.
1696 *========================================================================*/
1697
1698 /*
1699 * Look up a name in a leaf directory structure.
1700 * This is the internal routine, it uses the caller's buffer.
1701 *
1702 * Note that duplicate keys are allowed, but only check within the
1703 * current leaf node. The Btree code must check in adjacent leaf nodes.
1704 *
1705 * Return in *index the index into the entry[] array of either the found
1706 * entry, or where the entry should have been (insert before that entry).
1707 *
1708 * Don't change the args->inumber unless we find the filename.
1709 */
1710 int
1711 xfs_dir_leaf_lookup_int(xfs_dabuf_t *bp, xfs_da_args_t *args, int *index)
1712 {
1713 xfs_dir_leafblock_t *leaf;
1714 xfs_dir_leaf_entry_t *entry;
1715 xfs_dir_leaf_name_t *namest;
1716 int probe, span;
1717 xfs_dahash_t hashval;
1718
1719 leaf = bp->data;
1720 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1721 ASSERT(INT_GET(leaf->hdr.count, ARCH_CONVERT) < (XFS_LBSIZE(args->dp->i_mount)/8));
1722
1723 /*
1724 * Binary search. (note: small blocks will skip this loop)
1725 */
1726 hashval = args->hashval;
1727 probe = span = INT_GET(leaf->hdr.count, ARCH_CONVERT) / 2;
1728 for (entry = &leaf->entries[probe]; span > 4;
1729 entry = &leaf->entries[probe]) {
1730 span /= 2;
1731 if (INT_GET(entry->hashval, ARCH_CONVERT) < hashval)
1732 probe += span;
1733 else if (INT_GET(entry->hashval, ARCH_CONVERT) > hashval)
1734 probe -= span;
1735 else
1736 break;
1737 }
1738 ASSERT((probe >= 0) && \
1739 ((!leaf->hdr.count) || (probe < INT_GET(leaf->hdr.count, ARCH_CONVERT))));
1740 ASSERT((span <= 4) || (INT_GET(entry->hashval, ARCH_CONVERT) == hashval));
1741
1742 /*
1743 * Since we may have duplicate hashval's, find the first matching
1744 * hashval in the leaf.
1745 */
1746 while ((probe > 0) && (INT_GET(entry->hashval, ARCH_CONVERT) >= hashval)) {
1747 entry--;
1748 probe--;
1749 }
1750 while ((probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)) && (INT_GET(entry->hashval, ARCH_CONVERT) < hashval)) {
1751 entry++;
1752 probe++;
1753 }
1754 if ((probe == INT_GET(leaf->hdr.count, ARCH_CONVERT)) || (INT_GET(entry->hashval, ARCH_CONVERT) != hashval)) {
1755 *index = probe;
1756 ASSERT(args->oknoent);
1757 return(XFS_ERROR(ENOENT));
1758 }
1759
1760 /*
1761 * Duplicate keys may be present, so search all of them for a match.
1762 */
1763 while ((probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)) && (INT_GET(entry->hashval, ARCH_CONVERT) == hashval)) {
1764 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT));
1765 if (entry->namelen == args->namelen &&
1766 namest->name[0] == args->name[0] &&
1767 memcmp(args->name, namest->name, args->namelen) == 0) {
1768 XFS_DIR_SF_GET_DIRINO(&namest->inumber, &args->inumber);
1769 *index = probe;
1770 return(XFS_ERROR(EEXIST));
1771 }
1772 entry++;
1773 probe++;
1774 }
1775 *index = probe;
1776 ASSERT(probe == INT_GET(leaf->hdr.count, ARCH_CONVERT) || args->oknoent);
1777 return(XFS_ERROR(ENOENT));
1778 }
1779
1780 /*========================================================================
1781 * Utility routines.
1782 *========================================================================*/
1783
1784 /*
1785 * Move the indicated entries from one leaf to another.
1786 * NOTE: this routine modifies both source and destination leaves.
1787 */
1788 /* ARGSUSED */
1789 STATIC void
1790 xfs_dir_leaf_moveents(xfs_dir_leafblock_t *leaf_s, int start_s,
1791 xfs_dir_leafblock_t *leaf_d, int start_d,
1792 int count, xfs_mount_t *mp)
1793 {
1794 xfs_dir_leaf_hdr_t *hdr_s, *hdr_d;
1795 xfs_dir_leaf_entry_t *entry_s, *entry_d;
1796 int tmp, i;
1797
1798 /*
1799 * Check for nothing to do.
1800 */
1801 if (count == 0)
1802 return;
1803
1804 /*
1805 * Set up environment.
1806 */
1807 ASSERT(INT_GET(leaf_s->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1808 ASSERT(INT_GET(leaf_d->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1809 hdr_s = &leaf_s->hdr;
1810 hdr_d = &leaf_d->hdr;
1811 ASSERT((INT_GET(hdr_s->count, ARCH_CONVERT) > 0) && (INT_GET(hdr_s->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8)));
1812 ASSERT(INT_GET(hdr_s->firstused, ARCH_CONVERT) >=
1813 ((INT_GET(hdr_s->count, ARCH_CONVERT)*sizeof(*entry_s))+sizeof(*hdr_s)));
1814 ASSERT(INT_GET(hdr_d->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8));
1815 ASSERT(INT_GET(hdr_d->firstused, ARCH_CONVERT) >=
1816 ((INT_GET(hdr_d->count, ARCH_CONVERT)*sizeof(*entry_d))+sizeof(*hdr_d)));
1817
1818 ASSERT(start_s < INT_GET(hdr_s->count, ARCH_CONVERT));
1819 ASSERT(start_d <= INT_GET(hdr_d->count, ARCH_CONVERT));
1820 ASSERT(count <= INT_GET(hdr_s->count, ARCH_CONVERT));
1821
1822 /*
1823 * Move the entries in the destination leaf up to make a hole?
1824 */
1825 if (start_d < INT_GET(hdr_d->count, ARCH_CONVERT)) {
1826 tmp = INT_GET(hdr_d->count, ARCH_CONVERT) - start_d;
1827 tmp *= (uint)sizeof(xfs_dir_leaf_entry_t);
1828 entry_s = &leaf_d->entries[start_d];
1829 entry_d = &leaf_d->entries[start_d + count];
1830 memcpy(entry_d, entry_s, tmp);
1831 }
1832
1833 /*
1834 * Copy all entry's in the same (sorted) order,
1835 * but allocate filenames packed and in sequence.
1836 */
1837 entry_s = &leaf_s->entries[start_s];
1838 entry_d = &leaf_d->entries[start_d];
1839 for (i = 0; i < count; entry_s++, entry_d++, i++) {
1840 ASSERT(INT_GET(entry_s->nameidx, ARCH_CONVERT) >= INT_GET(hdr_s->firstused, ARCH_CONVERT));
1841 tmp = XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry_s);
1842 INT_MOD(hdr_d->firstused, ARCH_CONVERT, -(tmp));
1843 entry_d->hashval = entry_s->hashval; /* INT_: direct copy */
1844 INT_COPY(entry_d->nameidx, hdr_d->firstused, ARCH_CONVERT);
1845 entry_d->namelen = entry_s->namelen;
1846 ASSERT(INT_GET(entry_d->nameidx, ARCH_CONVERT) + tmp <= XFS_LBSIZE(mp));
1847 memcpy(XFS_DIR_LEAF_NAMESTRUCT(leaf_d, INT_GET(entry_d->nameidx, ARCH_CONVERT)),
1848 XFS_DIR_LEAF_NAMESTRUCT(leaf_s, INT_GET(entry_s->nameidx, ARCH_CONVERT)), tmp);
1849 ASSERT(INT_GET(entry_s->nameidx, ARCH_CONVERT) + tmp <= XFS_LBSIZE(mp));
1850 memset((char *)XFS_DIR_LEAF_NAMESTRUCT(leaf_s, INT_GET(entry_s->nameidx, ARCH_CONVERT)),
1851 0, tmp);
1852 INT_MOD(hdr_s->namebytes, ARCH_CONVERT, -(entry_d->namelen));
1853 INT_MOD(hdr_d->namebytes, ARCH_CONVERT, entry_d->namelen);
1854 INT_MOD(hdr_s->count, ARCH_CONVERT, -1);
1855 INT_MOD(hdr_d->count, ARCH_CONVERT, +1);
1856 tmp = INT_GET(hdr_d->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t)
1857 + (uint)sizeof(xfs_dir_leaf_hdr_t);
1858 ASSERT(INT_GET(hdr_d->firstused, ARCH_CONVERT) >= tmp);
1859
1860 }
1861
1862 /*
1863 * Zero out the entries we just copied.
1864 */
1865 if (start_s == INT_GET(hdr_s->count, ARCH_CONVERT)) {
1866 tmp = count * (uint)sizeof(xfs_dir_leaf_entry_t);
1867 entry_s = &leaf_s->entries[start_s];
1868 ASSERT((char *)entry_s + tmp <= (char *)leaf_s + XFS_LBSIZE(mp));
1869 memset((char *)entry_s, 0, tmp);
1870 } else {
1871 /*
1872 * Move the remaining entries down to fill the hole,
1873 * then zero the entries at the top.
1874 */
1875 tmp = INT_GET(hdr_s->count, ARCH_CONVERT) - count;
1876 tmp *= (uint)sizeof(xfs_dir_leaf_entry_t);
1877 entry_s = &leaf_s->entries[start_s + count];
1878 entry_d = &leaf_s->entries[start_s];
1879 memcpy(entry_d, entry_s, tmp);
1880
1881 tmp = count * (uint)sizeof(xfs_dir_leaf_entry_t);
1882 entry_s = &leaf_s->entries[INT_GET(hdr_s->count, ARCH_CONVERT)];
1883 ASSERT((char *)entry_s + tmp <= (char *)leaf_s + XFS_LBSIZE(mp));
1884 memset((char *)entry_s, 0, tmp);
1885 }
1886
1887 /*
1888 * Fill in the freemap information
1889 */
1890 INT_SET(hdr_d->freemap[0].base, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_hdr_t));
1891 INT_MOD(hdr_d->freemap[0].base, ARCH_CONVERT, INT_GET(hdr_d->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t));
1892 INT_SET(hdr_d->freemap[0].size, ARCH_CONVERT, INT_GET(hdr_d->firstused, ARCH_CONVERT) - INT_GET(hdr_d->freemap[0].base, ARCH_CONVERT));
1893 INT_SET(hdr_d->freemap[1].base, ARCH_CONVERT, (hdr_d->freemap[2].base = 0));
1894 INT_SET(hdr_d->freemap[1].size, ARCH_CONVERT, (hdr_d->freemap[2].size = 0));
1895 hdr_s->holes = 1; /* leaf may not be compact */
1896 }
1897
1898 /*
1899 * Compare two leaf blocks "order".
1900 */
1901 int
1902 xfs_dir_leaf_order(xfs_dabuf_t *leaf1_bp, xfs_dabuf_t *leaf2_bp)
1903 {
1904 xfs_dir_leafblock_t *leaf1, *leaf2;
1905
1906 leaf1 = leaf1_bp->data;
1907 leaf2 = leaf2_bp->data;
1908 ASSERT((INT_GET(leaf1->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC) &&
1909 (INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC));
1910 if ((INT_GET(leaf1->hdr.count, ARCH_CONVERT) > 0) && (INT_GET(leaf2->hdr.count, ARCH_CONVERT) > 0) &&
1911 ((INT_GET(leaf2->entries[ 0 ].hashval, ARCH_CONVERT) <
1912 INT_GET(leaf1->entries[ 0 ].hashval, ARCH_CONVERT)) ||
1913 (INT_GET(leaf2->entries[ INT_GET(leaf2->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT) <
1914 INT_GET(leaf1->entries[ INT_GET(leaf1->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT)))) {
1915 return(1);
1916 }
1917 return(0);
1918 }
1919
1920 /*
1921 * Pick up the last hashvalue from a leaf block.
1922 */
1923 xfs_dahash_t
1924 xfs_dir_leaf_lasthash(xfs_dabuf_t *bp, int *count)
1925 {
1926 xfs_dir_leafblock_t *leaf;
1927
1928 leaf = bp->data;
1929 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC);
1930 if (count)
1931 *count = INT_GET(leaf->hdr.count, ARCH_CONVERT);
1932 if (!leaf->hdr.count)
1933 return(0);
1934 return(INT_GET(leaf->entries[ INT_GET(leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT));
1935 }
1936
1937 /*
1938 * Copy out directory entries for getdents(), for leaf directories.
1939 */
1940 int
1941 xfs_dir_leaf_getdents_int(
1942 xfs_dabuf_t *bp,
1943 xfs_inode_t *dp,
1944 xfs_dablk_t bno,
1945 uio_t *uio,
1946 int *eobp,
1947 xfs_dirent_t *dbp,
1948 xfs_dir_put_t put,
1949 xfs_daddr_t nextda)
1950 {
1951 xfs_dir_leafblock_t *leaf;
1952 xfs_dir_leaf_entry_t *entry;
1953 xfs_dir_leaf_name_t *namest;
1954 int entno, want_entno, i, nextentno;
1955 xfs_mount_t *mp;
1956 xfs_dahash_t cookhash;
1957 xfs_dahash_t nexthash = 0;
1958 #if (BITS_PER_LONG == 32)
1959 xfs_dahash_t lasthash = XFS_DA_MAXHASH;
1960 #endif
1961 xfs_dir_put_args_t p;
1962
1963 mp = dp->i_mount;
1964 leaf = bp->data;
1965 if (INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) != XFS_DIR_LEAF_MAGIC) {
1966 *eobp = 1;
1967 return(XFS_ERROR(ENOENT)); /* XXX wrong code */
1968 }
1969
1970 want_entno = XFS_DA_COOKIE_ENTRY(mp, uio->uio_offset);
1971
1972 cookhash = XFS_DA_COOKIE_HASH(mp, uio->uio_offset);
1973
1974 xfs_dir_trace_g_dul("leaf: start", dp, uio, leaf);
1975
1976 /*
1977 * Re-find our place.
1978 */
1979 for (i = entno = 0, entry = &leaf->entries[0];
1980 i < INT_GET(leaf->hdr.count, ARCH_CONVERT);
1981 entry++, i++) {
1982
1983 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf,
1984 INT_GET(entry->nameidx, ARCH_CONVERT));
1985
1986 if (unlikely(
1987 ((char *)namest < (char *)leaf) ||
1988 ((char *)namest >= (char *)leaf + XFS_LBSIZE(mp)))) {
1989 XFS_CORRUPTION_ERROR("xfs_dir_leaf_getdents_int(1)",
1990 XFS_ERRLEVEL_LOW, mp, leaf);
1991 xfs_dir_trace_g_du("leaf: corrupted", dp, uio);
1992 return XFS_ERROR(EFSCORRUPTED);
1993 }
1994 if (INT_GET(entry->hashval, ARCH_CONVERT) >= cookhash) {
1995 if ( entno < want_entno
1996 && INT_GET(entry->hashval, ARCH_CONVERT)
1997 == cookhash) {
1998 /*
1999 * Trying to get to a particular offset in a
2000 * run of equal-hashval entries.
2001 */
2002 entno++;
2003 } else if ( want_entno > 0
2004 && entno == want_entno
2005 && INT_GET(entry->hashval, ARCH_CONVERT)
2006 == cookhash) {
2007 break;
2008 } else {
2009 entno = 0;
2010 break;
2011 }
2012 }
2013 }
2014
2015 if (i == INT_GET(leaf->hdr.count, ARCH_CONVERT)) {
2016 xfs_dir_trace_g_du("leaf: hash not found", dp, uio);
2017 if (!INT_GET(leaf->hdr.info.forw, ARCH_CONVERT))
2018 uio->uio_offset =
2019 XFS_DA_MAKE_COOKIE(mp, 0, 0, XFS_DA_MAXHASH);
2020 /*
2021 * Don't set uio_offset if there's another block:
2022 * the node code will be setting uio_offset anyway.
2023 */
2024 *eobp = 0;
2025 return(0);
2026 }
2027 xfs_dir_trace_g_due("leaf: hash found", dp, uio, entry);
2028
2029 p.dbp = dbp;
2030 p.put = put;
2031 p.uio = uio;
2032
2033 /*
2034 * We're synchronized, start copying entries out to the user.
2035 */
2036 for (; entno >= 0 && i < INT_GET(leaf->hdr.count, ARCH_CONVERT);
2037 entry++, i++, (entno = nextentno)) {
2038 int lastresid=0, retval;
2039 xfs_dircook_t lastoffset;
2040 xfs_dahash_t thishash;
2041
2042 /*
2043 * Check for a damaged directory leaf block and pick up
2044 * the inode number from this entry.
2045 */
2046 namest = XFS_DIR_LEAF_NAMESTRUCT(leaf,
2047 INT_GET(entry->nameidx, ARCH_CONVERT));
2048
2049 if (unlikely(
2050 ((char *)namest < (char *)leaf) ||
2051 ((char *)namest >= (char *)leaf + XFS_LBSIZE(mp)))) {
2052 XFS_CORRUPTION_ERROR("xfs_dir_leaf_getdents_int(2)",
2053 XFS_ERRLEVEL_LOW, mp, leaf);
2054 xfs_dir_trace_g_du("leaf: corrupted", dp, uio);
2055 return XFS_ERROR(EFSCORRUPTED);
2056 }
2057
2058 xfs_dir_trace_g_duc("leaf: middle cookie ",
2059 dp, uio, p.cook.o);
2060
2061 if (i < (INT_GET(leaf->hdr.count, ARCH_CONVERT) - 1)) {
2062 nexthash = INT_GET(entry[1].hashval, ARCH_CONVERT);
2063
2064 if (nexthash == INT_GET(entry->hashval, ARCH_CONVERT))
2065 nextentno = entno + 1;
2066 else
2067 nextentno = 0;
2068 XFS_PUT_COOKIE(p.cook, mp, bno, nextentno, nexthash);
2069 xfs_dir_trace_g_duc("leaf: middle cookie ",
2070 dp, uio, p.cook.o);
2071
2072 } else if ((thishash = INT_GET(leaf->hdr.info.forw,
2073 ARCH_CONVERT))) {
2074 xfs_dabuf_t *bp2;
2075 xfs_dir_leafblock_t *leaf2;
2076
2077 ASSERT(nextda != -1);
2078
2079 retval = xfs_da_read_buf(dp->i_transp, dp, thishash,
2080 nextda, &bp2, XFS_DATA_FORK);
2081 if (retval)
2082 return(retval);
2083
2084 ASSERT(bp2 != NULL);
2085
2086 leaf2 = bp2->data;
2087
2088 if (unlikely(
2089 (INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT)
2090 != XFS_DIR_LEAF_MAGIC)
2091 || (INT_GET(leaf2->hdr.info.back, ARCH_CONVERT)
2092 != bno))) { /* GROT */
2093 XFS_CORRUPTION_ERROR("xfs_dir_leaf_getdents_int(3)",
2094 XFS_ERRLEVEL_LOW, mp,
2095 leaf2);
2096 xfs_da_brelse(dp->i_transp, bp2);
2097
2098 return(XFS_ERROR(EFSCORRUPTED));
2099 }
2100
2101 nexthash = INT_GET(leaf2->entries[0].hashval,
2102 ARCH_CONVERT);
2103 nextentno = -1;
2104 XFS_PUT_COOKIE(p.cook, mp, thishash, 0, nexthash);
2105 xfs_da_brelse(dp->i_transp, bp2);
2106 xfs_dir_trace_g_duc("leaf: next blk cookie",
2107 dp, uio, p.cook.o);
2108 } else {
2109 nextentno = -1;
2110 XFS_PUT_COOKIE(p.cook, mp, 0, 0, XFS_DA_MAXHASH);
2111 }
2112
2113 /*
2114 * Save off the cookie so we can fall back should the
2115 * 'put' into the outgoing buffer fails. To handle a run
2116 * of equal-hashvals, the off_t structure on 64bit
2117 * builds has entno built into the cookie to ID the
2118 * entry. On 32bit builds, we only have space for the
2119 * hashval so we can't ID specific entries within a group
2120 * of same hashval entries. For this, lastoffset is set
2121 * to the first in the run of equal hashvals so we don't
2122 * include any entries unless we can include all entries
2123 * that share the same hashval. Hopefully the buffer
2124 * provided is big enough to handle it (see pv763517).
2125 */
2126 #if (BITS_PER_LONG == 32)
2127 if ((thishash = INT_GET(entry->hashval, ARCH_CONVERT))
2128 != lasthash) {
2129 XFS_PUT_COOKIE(lastoffset, mp, bno, entno, thishash);
2130 lastresid = uio->uio_resid;
2131 lasthash = thishash;
2132 } else {
2133 xfs_dir_trace_g_duc("leaf: DUP COOKIES, skipped",
2134 dp, uio, p.cook.o);
2135 }
2136 #else
2137 thishash = INT_GET(entry->hashval, ARCH_CONVERT);
2138 XFS_PUT_COOKIE(lastoffset, mp, bno, entno, thishash);
2139 lastresid = uio->uio_resid;
2140 #endif /* BITS_PER_LONG == 32 */
2141
2142 /*
2143 * Put the current entry into the outgoing buffer. If we fail
2144 * then restore the UIO to the first entry in the current
2145 * run of equal-hashval entries (probably one 1 entry long).
2146 */
2147 p.ino = XFS_GET_DIR_INO8(namest->inumber);
2148 #if XFS_BIG_INUMS
2149 p.ino += mp->m_inoadd;
2150 #endif
2151 p.name = (char *)namest->name;
2152 p.namelen = entry->namelen;
2153
2154 retval = p.put(&p);
2155
2156 if (!p.done) {
2157 uio->uio_offset = lastoffset.o;
2158 uio->uio_resid = lastresid;
2159
2160 *eobp = 1;
2161
2162 xfs_dir_trace_g_du("leaf: E-O-B", dp, uio);
2163
2164 return(retval);
2165 }
2166 }
2167
2168 uio->uio_offset = p.cook.o;
2169
2170 *eobp = 0;
2171
2172 xfs_dir_trace_g_du("leaf: E-O-F", dp, uio);
2173
2174 return(0);
2175 }
2176
2177 /*
2178 * Format a dirent64 structure and copy it out the the user's buffer.
2179 */
2180 int
2181 xfs_dir_put_dirent64_direct(xfs_dir_put_args_t *pa)
2182 {
2183 iovec_t *iovp;
2184 int reclen, namelen;
2185 xfs_dirent_t *idbp;
2186 uio_t *uio;
2187
2188 namelen = pa->namelen;
2189 reclen = DIRENTSIZE(namelen);
2190 uio = pa->uio;
2191 if (reclen > uio->uio_resid) {
2192 pa->done = 0;
2193 return 0;
2194 }
2195 iovp = uio->uio_iov;
2196 idbp = (xfs_dirent_t *)iovp->iov_base;
2197 iovp->iov_base = (char *)idbp + reclen;
2198 iovp->iov_len -= reclen;
2199 uio->uio_resid -= reclen;
2200 idbp->d_reclen = reclen;
2201 idbp->d_ino = pa->ino;
2202 idbp->d_off = pa->cook.o;
2203 idbp->d_name[namelen] = '\0';
2204 pa->done = 1;
2205 memcpy(idbp->d_name, pa->name, namelen);
2206 return 0;
2207 }
2208
2209 /*
2210 * Format a dirent64 structure and copy it out the the user's buffer.
2211 */
2212 int
2213 xfs_dir_put_dirent64_uio(xfs_dir_put_args_t *pa)
2214 {
2215 int retval, reclen, namelen;
2216 xfs_dirent_t *idbp;
2217 uio_t *uio;
2218
2219 namelen = pa->namelen;
2220 reclen = DIRENTSIZE(namelen);
2221 uio = pa->uio;
2222 if (reclen > uio->uio_resid) {
2223 pa->done = 0;
2224 return 0;
2225 }
2226 idbp = pa->dbp;
2227 idbp->d_reclen = reclen;
2228 idbp->d_ino = pa->ino;
2229 idbp->d_off = pa->cook.o;
2230 idbp->d_name[namelen] = '\0';
2231 memcpy(idbp->d_name, pa->name, namelen);
2232 retval = uio_read((caddr_t)idbp, reclen, uio);
2233 pa->done = (retval == 0);
2234 return retval;
2235 }
Linux with added FPC-III support