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