xref: /openbmc/linux/fs/xfs/libxfs/xfs_dir2_block.c (revision ae40e94f)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
4  * Copyright (c) 2013 Red Hat, Inc.
5  * All Rights Reserved.
6  */
7 #include "xfs.h"
8 #include "xfs_fs.h"
9 #include "xfs_format.h"
10 #include "xfs_log_format.h"
11 #include "xfs_trans_resv.h"
12 #include "xfs_mount.h"
13 #include "xfs_da_format.h"
14 #include "xfs_da_btree.h"
15 #include "xfs_inode.h"
16 #include "xfs_trans.h"
17 #include "xfs_inode_item.h"
18 #include "xfs_bmap.h"
19 #include "xfs_buf_item.h"
20 #include "xfs_dir2.h"
21 #include "xfs_dir2_priv.h"
22 #include "xfs_error.h"
23 #include "xfs_trace.h"
24 #include "xfs_cksum.h"
25 #include "xfs_log.h"
26 
27 /*
28  * Local function prototypes.
29  */
30 static void xfs_dir2_block_log_leaf(xfs_trans_t *tp, struct xfs_buf *bp,
31 				    int first, int last);
32 static void xfs_dir2_block_log_tail(xfs_trans_t *tp, struct xfs_buf *bp);
33 static int xfs_dir2_block_lookup_int(xfs_da_args_t *args, struct xfs_buf **bpp,
34 				     int *entno);
35 static int xfs_dir2_block_sort(const void *a, const void *b);
36 
37 static xfs_dahash_t xfs_dir_hash_dot, xfs_dir_hash_dotdot;
38 
39 /*
40  * One-time startup routine called from xfs_init().
41  */
42 void
43 xfs_dir_startup(void)
44 {
45 	xfs_dir_hash_dot = xfs_da_hashname((unsigned char *)".", 1);
46 	xfs_dir_hash_dotdot = xfs_da_hashname((unsigned char *)"..", 2);
47 }
48 
49 static xfs_failaddr_t
50 xfs_dir3_block_verify(
51 	struct xfs_buf		*bp)
52 {
53 	struct xfs_mount	*mp = bp->b_target->bt_mount;
54 	struct xfs_dir3_blk_hdr	*hdr3 = bp->b_addr;
55 
56 	if (!xfs_verify_magic(bp, hdr3->magic))
57 		return __this_address;
58 
59 	if (xfs_sb_version_hascrc(&mp->m_sb)) {
60 		if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))
61 			return __this_address;
62 		if (be64_to_cpu(hdr3->blkno) != bp->b_bn)
63 			return __this_address;
64 		if (!xfs_log_check_lsn(mp, be64_to_cpu(hdr3->lsn)))
65 			return __this_address;
66 	}
67 	return __xfs_dir3_data_check(NULL, bp);
68 }
69 
70 static void
71 xfs_dir3_block_read_verify(
72 	struct xfs_buf	*bp)
73 {
74 	struct xfs_mount	*mp = bp->b_target->bt_mount;
75 	xfs_failaddr_t		fa;
76 
77 	if (xfs_sb_version_hascrc(&mp->m_sb) &&
78 	     !xfs_buf_verify_cksum(bp, XFS_DIR3_DATA_CRC_OFF))
79 		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
80 	else {
81 		fa = xfs_dir3_block_verify(bp);
82 		if (fa)
83 			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
84 	}
85 }
86 
87 static void
88 xfs_dir3_block_write_verify(
89 	struct xfs_buf	*bp)
90 {
91 	struct xfs_mount	*mp = bp->b_target->bt_mount;
92 	struct xfs_buf_log_item	*bip = bp->b_log_item;
93 	struct xfs_dir3_blk_hdr	*hdr3 = bp->b_addr;
94 	xfs_failaddr_t		fa;
95 
96 	fa = xfs_dir3_block_verify(bp);
97 	if (fa) {
98 		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
99 		return;
100 	}
101 
102 	if (!xfs_sb_version_hascrc(&mp->m_sb))
103 		return;
104 
105 	if (bip)
106 		hdr3->lsn = cpu_to_be64(bip->bli_item.li_lsn);
107 
108 	xfs_buf_update_cksum(bp, XFS_DIR3_DATA_CRC_OFF);
109 }
110 
111 const struct xfs_buf_ops xfs_dir3_block_buf_ops = {
112 	.name = "xfs_dir3_block",
113 	.magic = { cpu_to_be32(XFS_DIR2_BLOCK_MAGIC),
114 		   cpu_to_be32(XFS_DIR3_BLOCK_MAGIC) },
115 	.verify_read = xfs_dir3_block_read_verify,
116 	.verify_write = xfs_dir3_block_write_verify,
117 	.verify_struct = xfs_dir3_block_verify,
118 };
119 
120 int
121 xfs_dir3_block_read(
122 	struct xfs_trans	*tp,
123 	struct xfs_inode	*dp,
124 	struct xfs_buf		**bpp)
125 {
126 	struct xfs_mount	*mp = dp->i_mount;
127 	int			err;
128 
129 	err = xfs_da_read_buf(tp, dp, mp->m_dir_geo->datablk, -1, bpp,
130 				XFS_DATA_FORK, &xfs_dir3_block_buf_ops);
131 	if (!err && tp && *bpp)
132 		xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_BLOCK_BUF);
133 	return err;
134 }
135 
136 static void
137 xfs_dir3_block_init(
138 	struct xfs_mount	*mp,
139 	struct xfs_trans	*tp,
140 	struct xfs_buf		*bp,
141 	struct xfs_inode	*dp)
142 {
143 	struct xfs_dir3_blk_hdr *hdr3 = bp->b_addr;
144 
145 	bp->b_ops = &xfs_dir3_block_buf_ops;
146 	xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_BLOCK_BUF);
147 
148 	if (xfs_sb_version_hascrc(&mp->m_sb)) {
149 		memset(hdr3, 0, sizeof(*hdr3));
150 		hdr3->magic = cpu_to_be32(XFS_DIR3_BLOCK_MAGIC);
151 		hdr3->blkno = cpu_to_be64(bp->b_bn);
152 		hdr3->owner = cpu_to_be64(dp->i_ino);
153 		uuid_copy(&hdr3->uuid, &mp->m_sb.sb_meta_uuid);
154 		return;
155 
156 	}
157 	hdr3->magic = cpu_to_be32(XFS_DIR2_BLOCK_MAGIC);
158 }
159 
160 static void
161 xfs_dir2_block_need_space(
162 	struct xfs_inode		*dp,
163 	struct xfs_dir2_data_hdr	*hdr,
164 	struct xfs_dir2_block_tail	*btp,
165 	struct xfs_dir2_leaf_entry	*blp,
166 	__be16				**tagpp,
167 	struct xfs_dir2_data_unused	**dupp,
168 	struct xfs_dir2_data_unused	**enddupp,
169 	int				*compact,
170 	int				len)
171 {
172 	struct xfs_dir2_data_free	*bf;
173 	__be16				*tagp = NULL;
174 	struct xfs_dir2_data_unused	*dup = NULL;
175 	struct xfs_dir2_data_unused	*enddup = NULL;
176 
177 	*compact = 0;
178 	bf = dp->d_ops->data_bestfree_p(hdr);
179 
180 	/*
181 	 * If there are stale entries we'll use one for the leaf.
182 	 */
183 	if (btp->stale) {
184 		if (be16_to_cpu(bf[0].length) >= len) {
185 			/*
186 			 * The biggest entry enough to avoid compaction.
187 			 */
188 			dup = (xfs_dir2_data_unused_t *)
189 			      ((char *)hdr + be16_to_cpu(bf[0].offset));
190 			goto out;
191 		}
192 
193 		/*
194 		 * Will need to compact to make this work.
195 		 * Tag just before the first leaf entry.
196 		 */
197 		*compact = 1;
198 		tagp = (__be16 *)blp - 1;
199 
200 		/* Data object just before the first leaf entry.  */
201 		dup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));
202 
203 		/*
204 		 * If it's not free then the data will go where the
205 		 * leaf data starts now, if it works at all.
206 		 */
207 		if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
208 			if (be16_to_cpu(dup->length) + (be32_to_cpu(btp->stale) - 1) *
209 			    (uint)sizeof(*blp) < len)
210 				dup = NULL;
211 		} else if ((be32_to_cpu(btp->stale) - 1) * (uint)sizeof(*blp) < len)
212 			dup = NULL;
213 		else
214 			dup = (xfs_dir2_data_unused_t *)blp;
215 		goto out;
216 	}
217 
218 	/*
219 	 * no stale entries, so just use free space.
220 	 * Tag just before the first leaf entry.
221 	 */
222 	tagp = (__be16 *)blp - 1;
223 
224 	/* Data object just before the first leaf entry.  */
225 	enddup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));
226 
227 	/*
228 	 * If it's not free then can't do this add without cleaning up:
229 	 * the space before the first leaf entry needs to be free so it
230 	 * can be expanded to hold the pointer to the new entry.
231 	 */
232 	if (be16_to_cpu(enddup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
233 		/*
234 		 * Check out the biggest freespace and see if it's the same one.
235 		 */
236 		dup = (xfs_dir2_data_unused_t *)
237 		      ((char *)hdr + be16_to_cpu(bf[0].offset));
238 		if (dup != enddup) {
239 			/*
240 			 * Not the same free entry, just check its length.
241 			 */
242 			if (be16_to_cpu(dup->length) < len)
243 				dup = NULL;
244 			goto out;
245 		}
246 
247 		/*
248 		 * It is the biggest freespace, can it hold the leaf too?
249 		 */
250 		if (be16_to_cpu(dup->length) < len + (uint)sizeof(*blp)) {
251 			/*
252 			 * Yes, use the second-largest entry instead if it works.
253 			 */
254 			if (be16_to_cpu(bf[1].length) >= len)
255 				dup = (xfs_dir2_data_unused_t *)
256 				      ((char *)hdr + be16_to_cpu(bf[1].offset));
257 			else
258 				dup = NULL;
259 		}
260 	}
261 out:
262 	*tagpp = tagp;
263 	*dupp = dup;
264 	*enddupp = enddup;
265 }
266 
267 /*
268  * compact the leaf entries.
269  * Leave the highest-numbered stale entry stale.
270  * XXX should be the one closest to mid but mid is not yet computed.
271  */
272 static void
273 xfs_dir2_block_compact(
274 	struct xfs_da_args		*args,
275 	struct xfs_buf			*bp,
276 	struct xfs_dir2_data_hdr	*hdr,
277 	struct xfs_dir2_block_tail	*btp,
278 	struct xfs_dir2_leaf_entry	*blp,
279 	int				*needlog,
280 	int				*lfloghigh,
281 	int				*lfloglow)
282 {
283 	int			fromidx;	/* source leaf index */
284 	int			toidx;		/* target leaf index */
285 	int			needscan = 0;
286 	int			highstale;	/* high stale index */
287 
288 	fromidx = toidx = be32_to_cpu(btp->count) - 1;
289 	highstale = *lfloghigh = -1;
290 	for (; fromidx >= 0; fromidx--) {
291 		if (blp[fromidx].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {
292 			if (highstale == -1)
293 				highstale = toidx;
294 			else {
295 				if (*lfloghigh == -1)
296 					*lfloghigh = toidx;
297 				continue;
298 			}
299 		}
300 		if (fromidx < toidx)
301 			blp[toidx] = blp[fromidx];
302 		toidx--;
303 	}
304 	*lfloglow = toidx + 1 - (be32_to_cpu(btp->stale) - 1);
305 	*lfloghigh -= be32_to_cpu(btp->stale) - 1;
306 	be32_add_cpu(&btp->count, -(be32_to_cpu(btp->stale) - 1));
307 	xfs_dir2_data_make_free(args, bp,
308 		(xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),
309 		(xfs_dir2_data_aoff_t)((be32_to_cpu(btp->stale) - 1) * sizeof(*blp)),
310 		needlog, &needscan);
311 	btp->stale = cpu_to_be32(1);
312 	/*
313 	 * If we now need to rebuild the bestfree map, do so.
314 	 * This needs to happen before the next call to use_free.
315 	 */
316 	if (needscan)
317 		xfs_dir2_data_freescan(args->dp, hdr, needlog);
318 }
319 
320 /*
321  * Add an entry to a block directory.
322  */
323 int						/* error */
324 xfs_dir2_block_addname(
325 	xfs_da_args_t		*args)		/* directory op arguments */
326 {
327 	xfs_dir2_data_hdr_t	*hdr;		/* block header */
328 	xfs_dir2_leaf_entry_t	*blp;		/* block leaf entries */
329 	struct xfs_buf		*bp;		/* buffer for block */
330 	xfs_dir2_block_tail_t	*btp;		/* block tail */
331 	int			compact;	/* need to compact leaf ents */
332 	xfs_dir2_data_entry_t	*dep;		/* block data entry */
333 	xfs_inode_t		*dp;		/* directory inode */
334 	xfs_dir2_data_unused_t	*dup;		/* block unused entry */
335 	int			error;		/* error return value */
336 	xfs_dir2_data_unused_t	*enddup=NULL;	/* unused at end of data */
337 	xfs_dahash_t		hash;		/* hash value of found entry */
338 	int			high;		/* high index for binary srch */
339 	int			highstale;	/* high stale index */
340 	int			lfloghigh=0;	/* last final leaf to log */
341 	int			lfloglow=0;	/* first final leaf to log */
342 	int			len;		/* length of the new entry */
343 	int			low;		/* low index for binary srch */
344 	int			lowstale;	/* low stale index */
345 	int			mid=0;		/* midpoint for binary srch */
346 	int			needlog;	/* need to log header */
347 	int			needscan;	/* need to rescan freespace */
348 	__be16			*tagp;		/* pointer to tag value */
349 	xfs_trans_t		*tp;		/* transaction structure */
350 
351 	trace_xfs_dir2_block_addname(args);
352 
353 	dp = args->dp;
354 	tp = args->trans;
355 
356 	/* Read the (one and only) directory block into bp. */
357 	error = xfs_dir3_block_read(tp, dp, &bp);
358 	if (error)
359 		return error;
360 
361 	len = dp->d_ops->data_entsize(args->namelen);
362 
363 	/*
364 	 * Set up pointers to parts of the block.
365 	 */
366 	hdr = bp->b_addr;
367 	btp = xfs_dir2_block_tail_p(args->geo, hdr);
368 	blp = xfs_dir2_block_leaf_p(btp);
369 
370 	/*
371 	 * Find out if we can reuse stale entries or whether we need extra
372 	 * space for entry and new leaf.
373 	 */
374 	xfs_dir2_block_need_space(dp, hdr, btp, blp, &tagp, &dup,
375 				  &enddup, &compact, len);
376 
377 	/*
378 	 * Done everything we need for a space check now.
379 	 */
380 	if (args->op_flags & XFS_DA_OP_JUSTCHECK) {
381 		xfs_trans_brelse(tp, bp);
382 		if (!dup)
383 			return -ENOSPC;
384 		return 0;
385 	}
386 
387 	/*
388 	 * If we don't have space for the new entry & leaf ...
389 	 */
390 	if (!dup) {
391 		/* Don't have a space reservation: return no-space.  */
392 		if (args->total == 0)
393 			return -ENOSPC;
394 		/*
395 		 * Convert to the next larger format.
396 		 * Then add the new entry in that format.
397 		 */
398 		error = xfs_dir2_block_to_leaf(args, bp);
399 		if (error)
400 			return error;
401 		return xfs_dir2_leaf_addname(args);
402 	}
403 
404 	needlog = needscan = 0;
405 
406 	/*
407 	 * If need to compact the leaf entries, do it now.
408 	 */
409 	if (compact) {
410 		xfs_dir2_block_compact(args, bp, hdr, btp, blp, &needlog,
411 				      &lfloghigh, &lfloglow);
412 		/* recalculate blp post-compaction */
413 		blp = xfs_dir2_block_leaf_p(btp);
414 	} else if (btp->stale) {
415 		/*
416 		 * Set leaf logging boundaries to impossible state.
417 		 * For the no-stale case they're set explicitly.
418 		 */
419 		lfloglow = be32_to_cpu(btp->count);
420 		lfloghigh = -1;
421 	}
422 
423 	/*
424 	 * Find the slot that's first lower than our hash value, -1 if none.
425 	 */
426 	for (low = 0, high = be32_to_cpu(btp->count) - 1; low <= high; ) {
427 		mid = (low + high) >> 1;
428 		if ((hash = be32_to_cpu(blp[mid].hashval)) == args->hashval)
429 			break;
430 		if (hash < args->hashval)
431 			low = mid + 1;
432 		else
433 			high = mid - 1;
434 	}
435 	while (mid >= 0 && be32_to_cpu(blp[mid].hashval) >= args->hashval) {
436 		mid--;
437 	}
438 	/*
439 	 * No stale entries, will use enddup space to hold new leaf.
440 	 */
441 	if (!btp->stale) {
442 		xfs_dir2_data_aoff_t	aoff;
443 
444 		/*
445 		 * Mark the space needed for the new leaf entry, now in use.
446 		 */
447 		aoff = (xfs_dir2_data_aoff_t)((char *)enddup - (char *)hdr +
448 				be16_to_cpu(enddup->length) - sizeof(*blp));
449 		error = xfs_dir2_data_use_free(args, bp, enddup, aoff,
450 				(xfs_dir2_data_aoff_t)sizeof(*blp), &needlog,
451 				&needscan);
452 		if (error)
453 			return error;
454 
455 		/*
456 		 * Update the tail (entry count).
457 		 */
458 		be32_add_cpu(&btp->count, 1);
459 		/*
460 		 * If we now need to rebuild the bestfree map, do so.
461 		 * This needs to happen before the next call to use_free.
462 		 */
463 		if (needscan) {
464 			xfs_dir2_data_freescan(dp, hdr, &needlog);
465 			needscan = 0;
466 		}
467 		/*
468 		 * Adjust pointer to the first leaf entry, we're about to move
469 		 * the table up one to open up space for the new leaf entry.
470 		 * Then adjust our index to match.
471 		 */
472 		blp--;
473 		mid++;
474 		if (mid)
475 			memmove(blp, &blp[1], mid * sizeof(*blp));
476 		lfloglow = 0;
477 		lfloghigh = mid;
478 	}
479 	/*
480 	 * Use a stale leaf for our new entry.
481 	 */
482 	else {
483 		for (lowstale = mid;
484 		     lowstale >= 0 &&
485 			blp[lowstale].address !=
486 			cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
487 		     lowstale--)
488 			continue;
489 		for (highstale = mid + 1;
490 		     highstale < be32_to_cpu(btp->count) &&
491 			blp[highstale].address !=
492 			cpu_to_be32(XFS_DIR2_NULL_DATAPTR) &&
493 			(lowstale < 0 || mid - lowstale > highstale - mid);
494 		     highstale++)
495 			continue;
496 		/*
497 		 * Move entries toward the low-numbered stale entry.
498 		 */
499 		if (lowstale >= 0 &&
500 		    (highstale == be32_to_cpu(btp->count) ||
501 		     mid - lowstale <= highstale - mid)) {
502 			if (mid - lowstale)
503 				memmove(&blp[lowstale], &blp[lowstale + 1],
504 					(mid - lowstale) * sizeof(*blp));
505 			lfloglow = min(lowstale, lfloglow);
506 			lfloghigh = max(mid, lfloghigh);
507 		}
508 		/*
509 		 * Move entries toward the high-numbered stale entry.
510 		 */
511 		else {
512 			ASSERT(highstale < be32_to_cpu(btp->count));
513 			mid++;
514 			if (highstale - mid)
515 				memmove(&blp[mid + 1], &blp[mid],
516 					(highstale - mid) * sizeof(*blp));
517 			lfloglow = min(mid, lfloglow);
518 			lfloghigh = max(highstale, lfloghigh);
519 		}
520 		be32_add_cpu(&btp->stale, -1);
521 	}
522 	/*
523 	 * Point to the new data entry.
524 	 */
525 	dep = (xfs_dir2_data_entry_t *)dup;
526 	/*
527 	 * Fill in the leaf entry.
528 	 */
529 	blp[mid].hashval = cpu_to_be32(args->hashval);
530 	blp[mid].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(
531 				(char *)dep - (char *)hdr));
532 	xfs_dir2_block_log_leaf(tp, bp, lfloglow, lfloghigh);
533 	/*
534 	 * Mark space for the data entry used.
535 	 */
536 	error = xfs_dir2_data_use_free(args, bp, dup,
537 			(xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),
538 			(xfs_dir2_data_aoff_t)len, &needlog, &needscan);
539 	if (error)
540 		return error;
541 	/*
542 	 * Create the new data entry.
543 	 */
544 	dep->inumber = cpu_to_be64(args->inumber);
545 	dep->namelen = args->namelen;
546 	memcpy(dep->name, args->name, args->namelen);
547 	dp->d_ops->data_put_ftype(dep, args->filetype);
548 	tagp = dp->d_ops->data_entry_tag_p(dep);
549 	*tagp = cpu_to_be16((char *)dep - (char *)hdr);
550 	/*
551 	 * Clean up the bestfree array and log the header, tail, and entry.
552 	 */
553 	if (needscan)
554 		xfs_dir2_data_freescan(dp, hdr, &needlog);
555 	if (needlog)
556 		xfs_dir2_data_log_header(args, bp);
557 	xfs_dir2_block_log_tail(tp, bp);
558 	xfs_dir2_data_log_entry(args, bp, dep);
559 	xfs_dir3_data_check(dp, bp);
560 	return 0;
561 }
562 
563 /*
564  * Log leaf entries from the block.
565  */
566 static void
567 xfs_dir2_block_log_leaf(
568 	xfs_trans_t		*tp,		/* transaction structure */
569 	struct xfs_buf		*bp,		/* block buffer */
570 	int			first,		/* index of first logged leaf */
571 	int			last)		/* index of last logged leaf */
572 {
573 	xfs_dir2_data_hdr_t	*hdr = bp->b_addr;
574 	xfs_dir2_leaf_entry_t	*blp;
575 	xfs_dir2_block_tail_t	*btp;
576 
577 	btp = xfs_dir2_block_tail_p(tp->t_mountp->m_dir_geo, hdr);
578 	blp = xfs_dir2_block_leaf_p(btp);
579 	xfs_trans_log_buf(tp, bp, (uint)((char *)&blp[first] - (char *)hdr),
580 		(uint)((char *)&blp[last + 1] - (char *)hdr - 1));
581 }
582 
583 /*
584  * Log the block tail.
585  */
586 static void
587 xfs_dir2_block_log_tail(
588 	xfs_trans_t		*tp,		/* transaction structure */
589 	struct xfs_buf		*bp)		/* block buffer */
590 {
591 	xfs_dir2_data_hdr_t	*hdr = bp->b_addr;
592 	xfs_dir2_block_tail_t	*btp;
593 
594 	btp = xfs_dir2_block_tail_p(tp->t_mountp->m_dir_geo, hdr);
595 	xfs_trans_log_buf(tp, bp, (uint)((char *)btp - (char *)hdr),
596 		(uint)((char *)(btp + 1) - (char *)hdr - 1));
597 }
598 
599 /*
600  * Look up an entry in the block.  This is the external routine,
601  * xfs_dir2_block_lookup_int does the real work.
602  */
603 int						/* error */
604 xfs_dir2_block_lookup(
605 	xfs_da_args_t		*args)		/* dir lookup arguments */
606 {
607 	xfs_dir2_data_hdr_t	*hdr;		/* block header */
608 	xfs_dir2_leaf_entry_t	*blp;		/* block leaf entries */
609 	struct xfs_buf		*bp;		/* block buffer */
610 	xfs_dir2_block_tail_t	*btp;		/* block tail */
611 	xfs_dir2_data_entry_t	*dep;		/* block data entry */
612 	xfs_inode_t		*dp;		/* incore inode */
613 	int			ent;		/* entry index */
614 	int			error;		/* error return value */
615 
616 	trace_xfs_dir2_block_lookup(args);
617 
618 	/*
619 	 * Get the buffer, look up the entry.
620 	 * If not found (ENOENT) then return, have no buffer.
621 	 */
622 	if ((error = xfs_dir2_block_lookup_int(args, &bp, &ent)))
623 		return error;
624 	dp = args->dp;
625 	hdr = bp->b_addr;
626 	xfs_dir3_data_check(dp, bp);
627 	btp = xfs_dir2_block_tail_p(args->geo, hdr);
628 	blp = xfs_dir2_block_leaf_p(btp);
629 	/*
630 	 * Get the offset from the leaf entry, to point to the data.
631 	 */
632 	dep = (xfs_dir2_data_entry_t *)((char *)hdr +
633 			xfs_dir2_dataptr_to_off(args->geo,
634 						be32_to_cpu(blp[ent].address)));
635 	/*
636 	 * Fill in inode number, CI name if appropriate, release the block.
637 	 */
638 	args->inumber = be64_to_cpu(dep->inumber);
639 	args->filetype = dp->d_ops->data_get_ftype(dep);
640 	error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
641 	xfs_trans_brelse(args->trans, bp);
642 	return error;
643 }
644 
645 /*
646  * Internal block lookup routine.
647  */
648 static int					/* error */
649 xfs_dir2_block_lookup_int(
650 	xfs_da_args_t		*args,		/* dir lookup arguments */
651 	struct xfs_buf		**bpp,		/* returned block buffer */
652 	int			*entno)		/* returned entry number */
653 {
654 	xfs_dir2_dataptr_t	addr;		/* data entry address */
655 	xfs_dir2_data_hdr_t	*hdr;		/* block header */
656 	xfs_dir2_leaf_entry_t	*blp;		/* block leaf entries */
657 	struct xfs_buf		*bp;		/* block buffer */
658 	xfs_dir2_block_tail_t	*btp;		/* block tail */
659 	xfs_dir2_data_entry_t	*dep;		/* block data entry */
660 	xfs_inode_t		*dp;		/* incore inode */
661 	int			error;		/* error return value */
662 	xfs_dahash_t		hash;		/* found hash value */
663 	int			high;		/* binary search high index */
664 	int			low;		/* binary search low index */
665 	int			mid;		/* binary search current idx */
666 	xfs_mount_t		*mp;		/* filesystem mount point */
667 	xfs_trans_t		*tp;		/* transaction pointer */
668 	enum xfs_dacmp		cmp;		/* comparison result */
669 
670 	dp = args->dp;
671 	tp = args->trans;
672 	mp = dp->i_mount;
673 
674 	error = xfs_dir3_block_read(tp, dp, &bp);
675 	if (error)
676 		return error;
677 
678 	hdr = bp->b_addr;
679 	xfs_dir3_data_check(dp, bp);
680 	btp = xfs_dir2_block_tail_p(args->geo, hdr);
681 	blp = xfs_dir2_block_leaf_p(btp);
682 	/*
683 	 * Loop doing a binary search for our hash value.
684 	 * Find our entry, ENOENT if it's not there.
685 	 */
686 	for (low = 0, high = be32_to_cpu(btp->count) - 1; ; ) {
687 		ASSERT(low <= high);
688 		mid = (low + high) >> 1;
689 		if ((hash = be32_to_cpu(blp[mid].hashval)) == args->hashval)
690 			break;
691 		if (hash < args->hashval)
692 			low = mid + 1;
693 		else
694 			high = mid - 1;
695 		if (low > high) {
696 			ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
697 			xfs_trans_brelse(tp, bp);
698 			return -ENOENT;
699 		}
700 	}
701 	/*
702 	 * Back up to the first one with the right hash value.
703 	 */
704 	while (mid > 0 && be32_to_cpu(blp[mid - 1].hashval) == args->hashval) {
705 		mid--;
706 	}
707 	/*
708 	 * Now loop forward through all the entries with the
709 	 * right hash value looking for our name.
710 	 */
711 	do {
712 		if ((addr = be32_to_cpu(blp[mid].address)) == XFS_DIR2_NULL_DATAPTR)
713 			continue;
714 		/*
715 		 * Get pointer to the entry from the leaf.
716 		 */
717 		dep = (xfs_dir2_data_entry_t *)
718 			((char *)hdr + xfs_dir2_dataptr_to_off(args->geo, addr));
719 		/*
720 		 * Compare name and if it's an exact match, return the index
721 		 * and buffer. If it's the first case-insensitive match, store
722 		 * the index and buffer and continue looking for an exact match.
723 		 */
724 		cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
725 		if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
726 			args->cmpresult = cmp;
727 			*bpp = bp;
728 			*entno = mid;
729 			if (cmp == XFS_CMP_EXACT)
730 				return 0;
731 		}
732 	} while (++mid < be32_to_cpu(btp->count) &&
733 			be32_to_cpu(blp[mid].hashval) == hash);
734 
735 	ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
736 	/*
737 	 * Here, we can only be doing a lookup (not a rename or replace).
738 	 * If a case-insensitive match was found earlier, return success.
739 	 */
740 	if (args->cmpresult == XFS_CMP_CASE)
741 		return 0;
742 	/*
743 	 * No match, release the buffer and return ENOENT.
744 	 */
745 	xfs_trans_brelse(tp, bp);
746 	return -ENOENT;
747 }
748 
749 /*
750  * Remove an entry from a block format directory.
751  * If that makes the block small enough to fit in shortform, transform it.
752  */
753 int						/* error */
754 xfs_dir2_block_removename(
755 	xfs_da_args_t		*args)		/* directory operation args */
756 {
757 	xfs_dir2_data_hdr_t	*hdr;		/* block header */
758 	xfs_dir2_leaf_entry_t	*blp;		/* block leaf pointer */
759 	struct xfs_buf		*bp;		/* block buffer */
760 	xfs_dir2_block_tail_t	*btp;		/* block tail */
761 	xfs_dir2_data_entry_t	*dep;		/* block data entry */
762 	xfs_inode_t		*dp;		/* incore inode */
763 	int			ent;		/* block leaf entry index */
764 	int			error;		/* error return value */
765 	int			needlog;	/* need to log block header */
766 	int			needscan;	/* need to fixup bestfree */
767 	xfs_dir2_sf_hdr_t	sfh;		/* shortform header */
768 	int			size;		/* shortform size */
769 	xfs_trans_t		*tp;		/* transaction pointer */
770 
771 	trace_xfs_dir2_block_removename(args);
772 
773 	/*
774 	 * Look up the entry in the block.  Gets the buffer and entry index.
775 	 * It will always be there, the vnodeops level does a lookup first.
776 	 */
777 	if ((error = xfs_dir2_block_lookup_int(args, &bp, &ent))) {
778 		return error;
779 	}
780 	dp = args->dp;
781 	tp = args->trans;
782 	hdr = bp->b_addr;
783 	btp = xfs_dir2_block_tail_p(args->geo, hdr);
784 	blp = xfs_dir2_block_leaf_p(btp);
785 	/*
786 	 * Point to the data entry using the leaf entry.
787 	 */
788 	dep = (xfs_dir2_data_entry_t *)((char *)hdr +
789 			xfs_dir2_dataptr_to_off(args->geo,
790 						be32_to_cpu(blp[ent].address)));
791 	/*
792 	 * Mark the data entry's space free.
793 	 */
794 	needlog = needscan = 0;
795 	xfs_dir2_data_make_free(args, bp,
796 		(xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),
797 		dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan);
798 	/*
799 	 * Fix up the block tail.
800 	 */
801 	be32_add_cpu(&btp->stale, 1);
802 	xfs_dir2_block_log_tail(tp, bp);
803 	/*
804 	 * Remove the leaf entry by marking it stale.
805 	 */
806 	blp[ent].address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
807 	xfs_dir2_block_log_leaf(tp, bp, ent, ent);
808 	/*
809 	 * Fix up bestfree, log the header if necessary.
810 	 */
811 	if (needscan)
812 		xfs_dir2_data_freescan(dp, hdr, &needlog);
813 	if (needlog)
814 		xfs_dir2_data_log_header(args, bp);
815 	xfs_dir3_data_check(dp, bp);
816 	/*
817 	 * See if the size as a shortform is good enough.
818 	 */
819 	size = xfs_dir2_block_sfsize(dp, hdr, &sfh);
820 	if (size > XFS_IFORK_DSIZE(dp))
821 		return 0;
822 
823 	/*
824 	 * If it works, do the conversion.
825 	 */
826 	return xfs_dir2_block_to_sf(args, bp, size, &sfh);
827 }
828 
829 /*
830  * Replace an entry in a V2 block directory.
831  * Change the inode number to the new value.
832  */
833 int						/* error */
834 xfs_dir2_block_replace(
835 	xfs_da_args_t		*args)		/* directory operation args */
836 {
837 	xfs_dir2_data_hdr_t	*hdr;		/* block header */
838 	xfs_dir2_leaf_entry_t	*blp;		/* block leaf entries */
839 	struct xfs_buf		*bp;		/* block buffer */
840 	xfs_dir2_block_tail_t	*btp;		/* block tail */
841 	xfs_dir2_data_entry_t	*dep;		/* block data entry */
842 	xfs_inode_t		*dp;		/* incore inode */
843 	int			ent;		/* leaf entry index */
844 	int			error;		/* error return value */
845 
846 	trace_xfs_dir2_block_replace(args);
847 
848 	/*
849 	 * Lookup the entry in the directory.  Get buffer and entry index.
850 	 * This will always succeed since the caller has already done a lookup.
851 	 */
852 	if ((error = xfs_dir2_block_lookup_int(args, &bp, &ent))) {
853 		return error;
854 	}
855 	dp = args->dp;
856 	hdr = bp->b_addr;
857 	btp = xfs_dir2_block_tail_p(args->geo, hdr);
858 	blp = xfs_dir2_block_leaf_p(btp);
859 	/*
860 	 * Point to the data entry we need to change.
861 	 */
862 	dep = (xfs_dir2_data_entry_t *)((char *)hdr +
863 			xfs_dir2_dataptr_to_off(args->geo,
864 						be32_to_cpu(blp[ent].address)));
865 	ASSERT(be64_to_cpu(dep->inumber) != args->inumber);
866 	/*
867 	 * Change the inode number to the new value.
868 	 */
869 	dep->inumber = cpu_to_be64(args->inumber);
870 	dp->d_ops->data_put_ftype(dep, args->filetype);
871 	xfs_dir2_data_log_entry(args, bp, dep);
872 	xfs_dir3_data_check(dp, bp);
873 	return 0;
874 }
875 
876 /*
877  * Qsort comparison routine for the block leaf entries.
878  */
879 static int					/* sort order */
880 xfs_dir2_block_sort(
881 	const void			*a,	/* first leaf entry */
882 	const void			*b)	/* second leaf entry */
883 {
884 	const xfs_dir2_leaf_entry_t	*la;	/* first leaf entry */
885 	const xfs_dir2_leaf_entry_t	*lb;	/* second leaf entry */
886 
887 	la = a;
888 	lb = b;
889 	return be32_to_cpu(la->hashval) < be32_to_cpu(lb->hashval) ? -1 :
890 		(be32_to_cpu(la->hashval) > be32_to_cpu(lb->hashval) ? 1 : 0);
891 }
892 
893 /*
894  * Convert a V2 leaf directory to a V2 block directory if possible.
895  */
896 int						/* error */
897 xfs_dir2_leaf_to_block(
898 	xfs_da_args_t		*args,		/* operation arguments */
899 	struct xfs_buf		*lbp,		/* leaf buffer */
900 	struct xfs_buf		*dbp)		/* data buffer */
901 {
902 	__be16			*bestsp;	/* leaf bests table */
903 	xfs_dir2_data_hdr_t	*hdr;		/* block header */
904 	xfs_dir2_block_tail_t	*btp;		/* block tail */
905 	xfs_inode_t		*dp;		/* incore directory inode */
906 	xfs_dir2_data_unused_t	*dup;		/* unused data entry */
907 	int			error;		/* error return value */
908 	int			from;		/* leaf from index */
909 	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
910 	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
911 	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
912 	xfs_mount_t		*mp;		/* file system mount point */
913 	int			needlog;	/* need to log data header */
914 	int			needscan;	/* need to scan for bestfree */
915 	xfs_dir2_sf_hdr_t	sfh;		/* shortform header */
916 	int			size;		/* bytes used */
917 	__be16			*tagp;		/* end of entry (tag) */
918 	int			to;		/* block/leaf to index */
919 	xfs_trans_t		*tp;		/* transaction pointer */
920 	struct xfs_dir2_leaf_entry *ents;
921 	struct xfs_dir3_icleaf_hdr leafhdr;
922 
923 	trace_xfs_dir2_leaf_to_block(args);
924 
925 	dp = args->dp;
926 	tp = args->trans;
927 	mp = dp->i_mount;
928 	leaf = lbp->b_addr;
929 	dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
930 	ents = dp->d_ops->leaf_ents_p(leaf);
931 	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
932 
933 	ASSERT(leafhdr.magic == XFS_DIR2_LEAF1_MAGIC ||
934 	       leafhdr.magic == XFS_DIR3_LEAF1_MAGIC);
935 	/*
936 	 * If there are data blocks other than the first one, take this
937 	 * opportunity to remove trailing empty data blocks that may have
938 	 * been left behind during no-space-reservation operations.
939 	 * These will show up in the leaf bests table.
940 	 */
941 	while (dp->i_d.di_size > args->geo->blksize) {
942 		int hdrsz;
943 
944 		hdrsz = dp->d_ops->data_entry_offset;
945 		bestsp = xfs_dir2_leaf_bests_p(ltp);
946 		if (be16_to_cpu(bestsp[be32_to_cpu(ltp->bestcount) - 1]) ==
947 					    args->geo->blksize - hdrsz) {
948 			if ((error =
949 			    xfs_dir2_leaf_trim_data(args, lbp,
950 				    (xfs_dir2_db_t)(be32_to_cpu(ltp->bestcount) - 1))))
951 				return error;
952 		} else
953 			return 0;
954 	}
955 	/*
956 	 * Read the data block if we don't already have it, give up if it fails.
957 	 */
958 	if (!dbp) {
959 		error = xfs_dir3_data_read(tp, dp, args->geo->datablk, -1, &dbp);
960 		if (error)
961 			return error;
962 	}
963 	hdr = dbp->b_addr;
964 	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
965 	       hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
966 
967 	/*
968 	 * Size of the "leaf" area in the block.
969 	 */
970 	size = (uint)sizeof(xfs_dir2_block_tail_t) +
971 	       (uint)sizeof(*lep) * (leafhdr.count - leafhdr.stale);
972 	/*
973 	 * Look at the last data entry.
974 	 */
975 	tagp = (__be16 *)((char *)hdr + args->geo->blksize) - 1;
976 	dup = (xfs_dir2_data_unused_t *)((char *)hdr + be16_to_cpu(*tagp));
977 	/*
978 	 * If it's not free or is too short we can't do it.
979 	 */
980 	if (be16_to_cpu(dup->freetag) != XFS_DIR2_DATA_FREE_TAG ||
981 	    be16_to_cpu(dup->length) < size)
982 		return 0;
983 
984 	/*
985 	 * Start converting it to block form.
986 	 */
987 	xfs_dir3_block_init(mp, tp, dbp, dp);
988 
989 	needlog = 1;
990 	needscan = 0;
991 	/*
992 	 * Use up the space at the end of the block (blp/btp).
993 	 */
994 	error = xfs_dir2_data_use_free(args, dbp, dup,
995 			args->geo->blksize - size, size, &needlog, &needscan);
996 	if (error)
997 		return error;
998 	/*
999 	 * Initialize the block tail.
1000 	 */
1001 	btp = xfs_dir2_block_tail_p(args->geo, hdr);
1002 	btp->count = cpu_to_be32(leafhdr.count - leafhdr.stale);
1003 	btp->stale = 0;
1004 	xfs_dir2_block_log_tail(tp, dbp);
1005 	/*
1006 	 * Initialize the block leaf area.  We compact out stale entries.
1007 	 */
1008 	lep = xfs_dir2_block_leaf_p(btp);
1009 	for (from = to = 0; from < leafhdr.count; from++) {
1010 		if (ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
1011 			continue;
1012 		lep[to++] = ents[from];
1013 	}
1014 	ASSERT(to == be32_to_cpu(btp->count));
1015 	xfs_dir2_block_log_leaf(tp, dbp, 0, be32_to_cpu(btp->count) - 1);
1016 	/*
1017 	 * Scan the bestfree if we need it and log the data block header.
1018 	 */
1019 	if (needscan)
1020 		xfs_dir2_data_freescan(dp, hdr, &needlog);
1021 	if (needlog)
1022 		xfs_dir2_data_log_header(args, dbp);
1023 	/*
1024 	 * Pitch the old leaf block.
1025 	 */
1026 	error = xfs_da_shrink_inode(args, args->geo->leafblk, lbp);
1027 	if (error)
1028 		return error;
1029 
1030 	/*
1031 	 * Now see if the resulting block can be shrunken to shortform.
1032 	 */
1033 	size = xfs_dir2_block_sfsize(dp, hdr, &sfh);
1034 	if (size > XFS_IFORK_DSIZE(dp))
1035 		return 0;
1036 
1037 	return xfs_dir2_block_to_sf(args, dbp, size, &sfh);
1038 }
1039 
1040 /*
1041  * Convert the shortform directory to block form.
1042  */
1043 int						/* error */
1044 xfs_dir2_sf_to_block(
1045 	xfs_da_args_t		*args)		/* operation arguments */
1046 {
1047 	xfs_dir2_db_t		blkno;		/* dir-relative block # (0) */
1048 	xfs_dir2_data_hdr_t	*hdr;		/* block header */
1049 	xfs_dir2_leaf_entry_t	*blp;		/* block leaf entries */
1050 	struct xfs_buf		*bp;		/* block buffer */
1051 	xfs_dir2_block_tail_t	*btp;		/* block tail pointer */
1052 	xfs_dir2_data_entry_t	*dep;		/* data entry pointer */
1053 	xfs_inode_t		*dp;		/* incore directory inode */
1054 	int			dummy;		/* trash */
1055 	xfs_dir2_data_unused_t	*dup;		/* unused entry pointer */
1056 	int			endoffset;	/* end of data objects */
1057 	int			error;		/* error return value */
1058 	int			i;		/* index */
1059 	xfs_mount_t		*mp;		/* filesystem mount point */
1060 	int			needlog;	/* need to log block header */
1061 	int			needscan;	/* need to scan block freespc */
1062 	int			newoffset;	/* offset from current entry */
1063 	int			offset;		/* target block offset */
1064 	xfs_dir2_sf_entry_t	*sfep;		/* sf entry pointer */
1065 	xfs_dir2_sf_hdr_t	*oldsfp;	/* old shortform header  */
1066 	xfs_dir2_sf_hdr_t	*sfp;		/* shortform header  */
1067 	__be16			*tagp;		/* end of data entry */
1068 	xfs_trans_t		*tp;		/* transaction pointer */
1069 	struct xfs_name		name;
1070 	struct xfs_ifork	*ifp;
1071 
1072 	trace_xfs_dir2_sf_to_block(args);
1073 
1074 	dp = args->dp;
1075 	tp = args->trans;
1076 	mp = dp->i_mount;
1077 	ifp = XFS_IFORK_PTR(dp, XFS_DATA_FORK);
1078 	ASSERT(ifp->if_flags & XFS_IFINLINE);
1079 	/*
1080 	 * Bomb out if the shortform directory is way too short.
1081 	 */
1082 	if (dp->i_d.di_size < offsetof(xfs_dir2_sf_hdr_t, parent)) {
1083 		ASSERT(XFS_FORCED_SHUTDOWN(mp));
1084 		return -EIO;
1085 	}
1086 
1087 	oldsfp = (xfs_dir2_sf_hdr_t *)ifp->if_u1.if_data;
1088 
1089 	ASSERT(ifp->if_bytes == dp->i_d.di_size);
1090 	ASSERT(ifp->if_u1.if_data != NULL);
1091 	ASSERT(dp->i_d.di_size >= xfs_dir2_sf_hdr_size(oldsfp->i8count));
1092 	ASSERT(dp->i_d.di_nextents == 0);
1093 
1094 	/*
1095 	 * Copy the directory into a temporary buffer.
1096 	 * Then pitch the incore inode data so we can make extents.
1097 	 */
1098 	sfp = kmem_alloc(ifp->if_bytes, KM_SLEEP);
1099 	memcpy(sfp, oldsfp, ifp->if_bytes);
1100 
1101 	xfs_idata_realloc(dp, -ifp->if_bytes, XFS_DATA_FORK);
1102 	xfs_bmap_local_to_extents_empty(dp, XFS_DATA_FORK);
1103 	dp->i_d.di_size = 0;
1104 
1105 	/*
1106 	 * Add block 0 to the inode.
1107 	 */
1108 	error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE, &blkno);
1109 	if (error)
1110 		goto out_free;
1111 	/*
1112 	 * Initialize the data block, then convert it to block format.
1113 	 */
1114 	error = xfs_dir3_data_init(args, blkno, &bp);
1115 	if (error)
1116 		goto out_free;
1117 	xfs_dir3_block_init(mp, tp, bp, dp);
1118 	hdr = bp->b_addr;
1119 
1120 	/*
1121 	 * Compute size of block "tail" area.
1122 	 */
1123 	i = (uint)sizeof(*btp) +
1124 	    (sfp->count + 2) * (uint)sizeof(xfs_dir2_leaf_entry_t);
1125 	/*
1126 	 * The whole thing is initialized to free by the init routine.
1127 	 * Say we're using the leaf and tail area.
1128 	 */
1129 	dup = dp->d_ops->data_unused_p(hdr);
1130 	needlog = needscan = 0;
1131 	error = xfs_dir2_data_use_free(args, bp, dup, args->geo->blksize - i,
1132 			i, &needlog, &needscan);
1133 	if (error)
1134 		goto out_free;
1135 	ASSERT(needscan == 0);
1136 	/*
1137 	 * Fill in the tail.
1138 	 */
1139 	btp = xfs_dir2_block_tail_p(args->geo, hdr);
1140 	btp->count = cpu_to_be32(sfp->count + 2);	/* ., .. */
1141 	btp->stale = 0;
1142 	blp = xfs_dir2_block_leaf_p(btp);
1143 	endoffset = (uint)((char *)blp - (char *)hdr);
1144 	/*
1145 	 * Remove the freespace, we'll manage it.
1146 	 */
1147 	error = xfs_dir2_data_use_free(args, bp, dup,
1148 			(xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),
1149 			be16_to_cpu(dup->length), &needlog, &needscan);
1150 	if (error)
1151 		goto out_free;
1152 	/*
1153 	 * Create entry for .
1154 	 */
1155 	dep = dp->d_ops->data_dot_entry_p(hdr);
1156 	dep->inumber = cpu_to_be64(dp->i_ino);
1157 	dep->namelen = 1;
1158 	dep->name[0] = '.';
1159 	dp->d_ops->data_put_ftype(dep, XFS_DIR3_FT_DIR);
1160 	tagp = dp->d_ops->data_entry_tag_p(dep);
1161 	*tagp = cpu_to_be16((char *)dep - (char *)hdr);
1162 	xfs_dir2_data_log_entry(args, bp, dep);
1163 	blp[0].hashval = cpu_to_be32(xfs_dir_hash_dot);
1164 	blp[0].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(
1165 				(char *)dep - (char *)hdr));
1166 	/*
1167 	 * Create entry for ..
1168 	 */
1169 	dep = dp->d_ops->data_dotdot_entry_p(hdr);
1170 	dep->inumber = cpu_to_be64(dp->d_ops->sf_get_parent_ino(sfp));
1171 	dep->namelen = 2;
1172 	dep->name[0] = dep->name[1] = '.';
1173 	dp->d_ops->data_put_ftype(dep, XFS_DIR3_FT_DIR);
1174 	tagp = dp->d_ops->data_entry_tag_p(dep);
1175 	*tagp = cpu_to_be16((char *)dep - (char *)hdr);
1176 	xfs_dir2_data_log_entry(args, bp, dep);
1177 	blp[1].hashval = cpu_to_be32(xfs_dir_hash_dotdot);
1178 	blp[1].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(
1179 				(char *)dep - (char *)hdr));
1180 	offset = dp->d_ops->data_first_offset;
1181 	/*
1182 	 * Loop over existing entries, stuff them in.
1183 	 */
1184 	i = 0;
1185 	if (!sfp->count)
1186 		sfep = NULL;
1187 	else
1188 		sfep = xfs_dir2_sf_firstentry(sfp);
1189 	/*
1190 	 * Need to preserve the existing offset values in the sf directory.
1191 	 * Insert holes (unused entries) where necessary.
1192 	 */
1193 	while (offset < endoffset) {
1194 		/*
1195 		 * sfep is null when we reach the end of the list.
1196 		 */
1197 		if (sfep == NULL)
1198 			newoffset = endoffset;
1199 		else
1200 			newoffset = xfs_dir2_sf_get_offset(sfep);
1201 		/*
1202 		 * There should be a hole here, make one.
1203 		 */
1204 		if (offset < newoffset) {
1205 			dup = (xfs_dir2_data_unused_t *)((char *)hdr + offset);
1206 			dup->freetag = cpu_to_be16(XFS_DIR2_DATA_FREE_TAG);
1207 			dup->length = cpu_to_be16(newoffset - offset);
1208 			*xfs_dir2_data_unused_tag_p(dup) = cpu_to_be16(
1209 				((char *)dup - (char *)hdr));
1210 			xfs_dir2_data_log_unused(args, bp, dup);
1211 			xfs_dir2_data_freeinsert(hdr,
1212 						 dp->d_ops->data_bestfree_p(hdr),
1213 						 dup, &dummy);
1214 			offset += be16_to_cpu(dup->length);
1215 			continue;
1216 		}
1217 		/*
1218 		 * Copy a real entry.
1219 		 */
1220 		dep = (xfs_dir2_data_entry_t *)((char *)hdr + newoffset);
1221 		dep->inumber = cpu_to_be64(dp->d_ops->sf_get_ino(sfp, sfep));
1222 		dep->namelen = sfep->namelen;
1223 		dp->d_ops->data_put_ftype(dep, dp->d_ops->sf_get_ftype(sfep));
1224 		memcpy(dep->name, sfep->name, dep->namelen);
1225 		tagp = dp->d_ops->data_entry_tag_p(dep);
1226 		*tagp = cpu_to_be16((char *)dep - (char *)hdr);
1227 		xfs_dir2_data_log_entry(args, bp, dep);
1228 		name.name = sfep->name;
1229 		name.len = sfep->namelen;
1230 		blp[2 + i].hashval = cpu_to_be32(mp->m_dirnameops->
1231 							hashname(&name));
1232 		blp[2 + i].address = cpu_to_be32(xfs_dir2_byte_to_dataptr(
1233 						 (char *)dep - (char *)hdr));
1234 		offset = (int)((char *)(tagp + 1) - (char *)hdr);
1235 		if (++i == sfp->count)
1236 			sfep = NULL;
1237 		else
1238 			sfep = dp->d_ops->sf_nextentry(sfp, sfep);
1239 	}
1240 	/* Done with the temporary buffer */
1241 	kmem_free(sfp);
1242 	/*
1243 	 * Sort the leaf entries by hash value.
1244 	 */
1245 	xfs_sort(blp, be32_to_cpu(btp->count), sizeof(*blp), xfs_dir2_block_sort);
1246 	/*
1247 	 * Log the leaf entry area and tail.
1248 	 * Already logged the header in data_init, ignore needlog.
1249 	 */
1250 	ASSERT(needscan == 0);
1251 	xfs_dir2_block_log_leaf(tp, bp, 0, be32_to_cpu(btp->count) - 1);
1252 	xfs_dir2_block_log_tail(tp, bp);
1253 	xfs_dir3_data_check(dp, bp);
1254 	return 0;
1255 out_free:
1256 	kmem_free(sfp);
1257 	return error;
1258 }
1259