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_shared.h"
10 #include "xfs_format.h"
11 #include "xfs_log_format.h"
12 #include "xfs_trans_resv.h"
13 #include "xfs_mount.h"
14 #include "xfs_inode.h"
15 #include "xfs_bmap.h"
16 #include "xfs_dir2.h"
17 #include "xfs_dir2_priv.h"
18 #include "xfs_error.h"
19 #include "xfs_trace.h"
20 #include "xfs_trans.h"
21 #include "xfs_buf_item.h"
22 
23 /*
24  * Local function declarations.
25  */
26 static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, struct xfs_buf **lbpp,
27 				    int *indexp, struct xfs_buf **dbpp,
28 				    struct xfs_dir3_icleaf_hdr *leafhdr);
29 static void xfs_dir3_leaf_log_bests(struct xfs_da_args *args,
30 				    struct xfs_buf *bp, int first, int last);
31 static void xfs_dir3_leaf_log_tail(struct xfs_da_args *args,
32 				   struct xfs_buf *bp);
33 
34 void
xfs_dir2_leaf_hdr_from_disk(struct xfs_mount * mp,struct xfs_dir3_icleaf_hdr * to,struct xfs_dir2_leaf * from)35 xfs_dir2_leaf_hdr_from_disk(
36 	struct xfs_mount		*mp,
37 	struct xfs_dir3_icleaf_hdr	*to,
38 	struct xfs_dir2_leaf		*from)
39 {
40 	if (xfs_has_crc(mp)) {
41 		struct xfs_dir3_leaf *from3 = (struct xfs_dir3_leaf *)from;
42 
43 		to->forw = be32_to_cpu(from3->hdr.info.hdr.forw);
44 		to->back = be32_to_cpu(from3->hdr.info.hdr.back);
45 		to->magic = be16_to_cpu(from3->hdr.info.hdr.magic);
46 		to->count = be16_to_cpu(from3->hdr.count);
47 		to->stale = be16_to_cpu(from3->hdr.stale);
48 		to->ents = from3->__ents;
49 
50 		ASSERT(to->magic == XFS_DIR3_LEAF1_MAGIC ||
51 		       to->magic == XFS_DIR3_LEAFN_MAGIC);
52 	} else {
53 		to->forw = be32_to_cpu(from->hdr.info.forw);
54 		to->back = be32_to_cpu(from->hdr.info.back);
55 		to->magic = be16_to_cpu(from->hdr.info.magic);
56 		to->count = be16_to_cpu(from->hdr.count);
57 		to->stale = be16_to_cpu(from->hdr.stale);
58 		to->ents = from->__ents;
59 
60 		ASSERT(to->magic == XFS_DIR2_LEAF1_MAGIC ||
61 		       to->magic == XFS_DIR2_LEAFN_MAGIC);
62 	}
63 }
64 
65 void
xfs_dir2_leaf_hdr_to_disk(struct xfs_mount * mp,struct xfs_dir2_leaf * to,struct xfs_dir3_icleaf_hdr * from)66 xfs_dir2_leaf_hdr_to_disk(
67 	struct xfs_mount		*mp,
68 	struct xfs_dir2_leaf		*to,
69 	struct xfs_dir3_icleaf_hdr	*from)
70 {
71 	if (xfs_has_crc(mp)) {
72 		struct xfs_dir3_leaf *to3 = (struct xfs_dir3_leaf *)to;
73 
74 		ASSERT(from->magic == XFS_DIR3_LEAF1_MAGIC ||
75 		       from->magic == XFS_DIR3_LEAFN_MAGIC);
76 
77 		to3->hdr.info.hdr.forw = cpu_to_be32(from->forw);
78 		to3->hdr.info.hdr.back = cpu_to_be32(from->back);
79 		to3->hdr.info.hdr.magic = cpu_to_be16(from->magic);
80 		to3->hdr.count = cpu_to_be16(from->count);
81 		to3->hdr.stale = cpu_to_be16(from->stale);
82 	} else {
83 		ASSERT(from->magic == XFS_DIR2_LEAF1_MAGIC ||
84 		       from->magic == XFS_DIR2_LEAFN_MAGIC);
85 
86 		to->hdr.info.forw = cpu_to_be32(from->forw);
87 		to->hdr.info.back = cpu_to_be32(from->back);
88 		to->hdr.info.magic = cpu_to_be16(from->magic);
89 		to->hdr.count = cpu_to_be16(from->count);
90 		to->hdr.stale = cpu_to_be16(from->stale);
91 	}
92 }
93 
94 /*
95  * Check the internal consistency of a leaf1 block.
96  * Pop an assert if something is wrong.
97  */
98 #ifdef DEBUG
99 static xfs_failaddr_t
xfs_dir3_leaf1_check(struct xfs_inode * dp,struct xfs_buf * bp)100 xfs_dir3_leaf1_check(
101 	struct xfs_inode	*dp,
102 	struct xfs_buf		*bp)
103 {
104 	struct xfs_dir2_leaf	*leaf = bp->b_addr;
105 	struct xfs_dir3_icleaf_hdr leafhdr;
106 
107 	xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
108 
109 	if (leafhdr.magic == XFS_DIR3_LEAF1_MAGIC) {
110 		struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
111 		if (be64_to_cpu(leaf3->info.blkno) != xfs_buf_daddr(bp))
112 			return __this_address;
113 	} else if (leafhdr.magic != XFS_DIR2_LEAF1_MAGIC)
114 		return __this_address;
115 
116 	return xfs_dir3_leaf_check_int(dp->i_mount, &leafhdr, leaf, false);
117 }
118 
119 static inline void
xfs_dir3_leaf_check(struct xfs_inode * dp,struct xfs_buf * bp)120 xfs_dir3_leaf_check(
121 	struct xfs_inode	*dp,
122 	struct xfs_buf		*bp)
123 {
124 	xfs_failaddr_t		fa;
125 
126 	fa = xfs_dir3_leaf1_check(dp, bp);
127 	if (!fa)
128 		return;
129 	xfs_corruption_error(__func__, XFS_ERRLEVEL_LOW, dp->i_mount,
130 			bp->b_addr, BBTOB(bp->b_length), __FILE__, __LINE__,
131 			fa);
132 	ASSERT(0);
133 }
134 #else
135 #define	xfs_dir3_leaf_check(dp, bp)
136 #endif
137 
138 xfs_failaddr_t
xfs_dir3_leaf_check_int(struct xfs_mount * mp,struct xfs_dir3_icleaf_hdr * hdr,struct xfs_dir2_leaf * leaf,bool expensive_checking)139 xfs_dir3_leaf_check_int(
140 	struct xfs_mount		*mp,
141 	struct xfs_dir3_icleaf_hdr	*hdr,
142 	struct xfs_dir2_leaf		*leaf,
143 	bool				expensive_checking)
144 {
145 	struct xfs_da_geometry		*geo = mp->m_dir_geo;
146 	xfs_dir2_leaf_tail_t		*ltp;
147 	int				stale;
148 	int				i;
149 	bool				isleaf1 = (hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
150 						   hdr->magic == XFS_DIR3_LEAF1_MAGIC);
151 
152 	ltp = xfs_dir2_leaf_tail_p(geo, leaf);
153 
154 	/*
155 	 * XXX (dgc): This value is not restrictive enough.
156 	 * Should factor in the size of the bests table as well.
157 	 * We can deduce a value for that from i_disk_size.
158 	 */
159 	if (hdr->count > geo->leaf_max_ents)
160 		return __this_address;
161 
162 	/* Leaves and bests don't overlap in leaf format. */
163 	if (isleaf1 &&
164 	    (char *)&hdr->ents[hdr->count] > (char *)xfs_dir2_leaf_bests_p(ltp))
165 		return __this_address;
166 
167 	if (!expensive_checking)
168 		return NULL;
169 
170 	/* Check hash value order, count stale entries.  */
171 	for (i = stale = 0; i < hdr->count; i++) {
172 		if (i + 1 < hdr->count) {
173 			if (be32_to_cpu(hdr->ents[i].hashval) >
174 					be32_to_cpu(hdr->ents[i + 1].hashval))
175 				return __this_address;
176 		}
177 		if (hdr->ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
178 			stale++;
179 		if (isleaf1 && xfs_dir2_dataptr_to_db(geo,
180 				be32_to_cpu(hdr->ents[i].address)) >=
181 				be32_to_cpu(ltp->bestcount))
182 			return __this_address;
183 	}
184 	if (hdr->stale != stale)
185 		return __this_address;
186 	return NULL;
187 }
188 
189 /*
190  * We verify the magic numbers before decoding the leaf header so that on debug
191  * kernels we don't get assertion failures in xfs_dir3_leaf_hdr_from_disk() due
192  * to incorrect magic numbers.
193  */
194 static xfs_failaddr_t
xfs_dir3_leaf_verify(struct xfs_buf * bp)195 xfs_dir3_leaf_verify(
196 	struct xfs_buf			*bp)
197 {
198 	struct xfs_mount		*mp = bp->b_mount;
199 	struct xfs_dir3_icleaf_hdr	leafhdr;
200 	xfs_failaddr_t			fa;
201 
202 	fa = xfs_da3_blkinfo_verify(bp, bp->b_addr);
203 	if (fa)
204 		return fa;
205 
206 	xfs_dir2_leaf_hdr_from_disk(mp, &leafhdr, bp->b_addr);
207 	return xfs_dir3_leaf_check_int(mp, &leafhdr, bp->b_addr, true);
208 }
209 
210 static void
xfs_dir3_leaf_read_verify(struct xfs_buf * bp)211 xfs_dir3_leaf_read_verify(
212 	struct xfs_buf  *bp)
213 {
214 	struct xfs_mount	*mp = bp->b_mount;
215 	xfs_failaddr_t		fa;
216 
217 	if (xfs_has_crc(mp) &&
218 	     !xfs_buf_verify_cksum(bp, XFS_DIR3_LEAF_CRC_OFF))
219 		xfs_verifier_error(bp, -EFSBADCRC, __this_address);
220 	else {
221 		fa = xfs_dir3_leaf_verify(bp);
222 		if (fa)
223 			xfs_verifier_error(bp, -EFSCORRUPTED, fa);
224 	}
225 }
226 
227 static void
xfs_dir3_leaf_write_verify(struct xfs_buf * bp)228 xfs_dir3_leaf_write_verify(
229 	struct xfs_buf  *bp)
230 {
231 	struct xfs_mount	*mp = bp->b_mount;
232 	struct xfs_buf_log_item	*bip = bp->b_log_item;
233 	struct xfs_dir3_leaf_hdr *hdr3 = bp->b_addr;
234 	xfs_failaddr_t		fa;
235 
236 	fa = xfs_dir3_leaf_verify(bp);
237 	if (fa) {
238 		xfs_verifier_error(bp, -EFSCORRUPTED, fa);
239 		return;
240 	}
241 
242 	if (!xfs_has_crc(mp))
243 		return;
244 
245 	if (bip)
246 		hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
247 
248 	xfs_buf_update_cksum(bp, XFS_DIR3_LEAF_CRC_OFF);
249 }
250 
251 const struct xfs_buf_ops xfs_dir3_leaf1_buf_ops = {
252 	.name = "xfs_dir3_leaf1",
253 	.magic16 = { cpu_to_be16(XFS_DIR2_LEAF1_MAGIC),
254 		     cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) },
255 	.verify_read = xfs_dir3_leaf_read_verify,
256 	.verify_write = xfs_dir3_leaf_write_verify,
257 	.verify_struct = xfs_dir3_leaf_verify,
258 };
259 
260 const struct xfs_buf_ops xfs_dir3_leafn_buf_ops = {
261 	.name = "xfs_dir3_leafn",
262 	.magic16 = { cpu_to_be16(XFS_DIR2_LEAFN_MAGIC),
263 		     cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) },
264 	.verify_read = xfs_dir3_leaf_read_verify,
265 	.verify_write = xfs_dir3_leaf_write_verify,
266 	.verify_struct = xfs_dir3_leaf_verify,
267 };
268 
269 int
xfs_dir3_leaf_read(struct xfs_trans * tp,struct xfs_inode * dp,xfs_dablk_t fbno,struct xfs_buf ** bpp)270 xfs_dir3_leaf_read(
271 	struct xfs_trans	*tp,
272 	struct xfs_inode	*dp,
273 	xfs_dablk_t		fbno,
274 	struct xfs_buf		**bpp)
275 {
276 	int			err;
277 
278 	err = xfs_da_read_buf(tp, dp, fbno, 0, bpp, XFS_DATA_FORK,
279 			&xfs_dir3_leaf1_buf_ops);
280 	if (!err && tp && *bpp)
281 		xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAF1_BUF);
282 	return err;
283 }
284 
285 int
xfs_dir3_leafn_read(struct xfs_trans * tp,struct xfs_inode * dp,xfs_dablk_t fbno,struct xfs_buf ** bpp)286 xfs_dir3_leafn_read(
287 	struct xfs_trans	*tp,
288 	struct xfs_inode	*dp,
289 	xfs_dablk_t		fbno,
290 	struct xfs_buf		**bpp)
291 {
292 	int			err;
293 
294 	err = xfs_da_read_buf(tp, dp, fbno, 0, bpp, XFS_DATA_FORK,
295 			&xfs_dir3_leafn_buf_ops);
296 	if (!err && tp && *bpp)
297 		xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAFN_BUF);
298 	return err;
299 }
300 
301 /*
302  * Initialize a new leaf block, leaf1 or leafn magic accepted.
303  */
304 static void
xfs_dir3_leaf_init(struct xfs_mount * mp,struct xfs_trans * tp,struct xfs_buf * bp,xfs_ino_t owner,uint16_t type)305 xfs_dir3_leaf_init(
306 	struct xfs_mount	*mp,
307 	struct xfs_trans	*tp,
308 	struct xfs_buf		*bp,
309 	xfs_ino_t		owner,
310 	uint16_t		type)
311 {
312 	struct xfs_dir2_leaf	*leaf = bp->b_addr;
313 
314 	ASSERT(type == XFS_DIR2_LEAF1_MAGIC || type == XFS_DIR2_LEAFN_MAGIC);
315 
316 	if (xfs_has_crc(mp)) {
317 		struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
318 
319 		memset(leaf3, 0, sizeof(*leaf3));
320 
321 		leaf3->info.hdr.magic = (type == XFS_DIR2_LEAF1_MAGIC)
322 					 ? cpu_to_be16(XFS_DIR3_LEAF1_MAGIC)
323 					 : cpu_to_be16(XFS_DIR3_LEAFN_MAGIC);
324 		leaf3->info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
325 		leaf3->info.owner = cpu_to_be64(owner);
326 		uuid_copy(&leaf3->info.uuid, &mp->m_sb.sb_meta_uuid);
327 	} else {
328 		memset(leaf, 0, sizeof(*leaf));
329 		leaf->hdr.info.magic = cpu_to_be16(type);
330 	}
331 
332 	/*
333 	 * If it's a leaf-format directory initialize the tail.
334 	 * Caller is responsible for initialising the bests table.
335 	 */
336 	if (type == XFS_DIR2_LEAF1_MAGIC) {
337 		struct xfs_dir2_leaf_tail *ltp;
338 
339 		ltp = xfs_dir2_leaf_tail_p(mp->m_dir_geo, leaf);
340 		ltp->bestcount = 0;
341 		bp->b_ops = &xfs_dir3_leaf1_buf_ops;
342 		xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAF1_BUF);
343 	} else {
344 		bp->b_ops = &xfs_dir3_leafn_buf_ops;
345 		xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
346 	}
347 }
348 
349 int
xfs_dir3_leaf_get_buf(xfs_da_args_t * args,xfs_dir2_db_t bno,struct xfs_buf ** bpp,uint16_t magic)350 xfs_dir3_leaf_get_buf(
351 	xfs_da_args_t		*args,
352 	xfs_dir2_db_t		bno,
353 	struct xfs_buf		**bpp,
354 	uint16_t		magic)
355 {
356 	struct xfs_inode	*dp = args->dp;
357 	struct xfs_trans	*tp = args->trans;
358 	struct xfs_mount	*mp = dp->i_mount;
359 	struct xfs_buf		*bp;
360 	int			error;
361 
362 	ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
363 	ASSERT(bno >= xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET) &&
364 	       bno < xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET));
365 
366 	error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, bno),
367 			       &bp, XFS_DATA_FORK);
368 	if (error)
369 		return error;
370 
371 	xfs_dir3_leaf_init(mp, tp, bp, dp->i_ino, magic);
372 	xfs_dir3_leaf_log_header(args, bp);
373 	if (magic == XFS_DIR2_LEAF1_MAGIC)
374 		xfs_dir3_leaf_log_tail(args, bp);
375 	*bpp = bp;
376 	return 0;
377 }
378 
379 /*
380  * Convert a block form directory to a leaf form directory.
381  */
382 int						/* error */
xfs_dir2_block_to_leaf(xfs_da_args_t * args,struct xfs_buf * dbp)383 xfs_dir2_block_to_leaf(
384 	xfs_da_args_t		*args,		/* operation arguments */
385 	struct xfs_buf		*dbp)		/* input block's buffer */
386 {
387 	__be16			*bestsp;	/* leaf's bestsp entries */
388 	xfs_dablk_t		blkno;		/* leaf block's bno */
389 	xfs_dir2_data_hdr_t	*hdr;		/* block header */
390 	xfs_dir2_leaf_entry_t	*blp;		/* block's leaf entries */
391 	xfs_dir2_block_tail_t	*btp;		/* block's tail */
392 	xfs_inode_t		*dp;		/* incore directory inode */
393 	int			error;		/* error return code */
394 	struct xfs_buf		*lbp;		/* leaf block's buffer */
395 	xfs_dir2_db_t		ldb;		/* leaf block's bno */
396 	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
397 	xfs_dir2_leaf_tail_t	*ltp;		/* leaf's tail */
398 	int			needlog;	/* need to log block header */
399 	int			needscan;	/* need to rescan bestfree */
400 	xfs_trans_t		*tp;		/* transaction pointer */
401 	struct xfs_dir2_data_free *bf;
402 	struct xfs_dir3_icleaf_hdr leafhdr;
403 
404 	trace_xfs_dir2_block_to_leaf(args);
405 
406 	dp = args->dp;
407 	tp = args->trans;
408 	/*
409 	 * Add the leaf block to the inode.
410 	 * This interface will only put blocks in the leaf/node range.
411 	 * Since that's empty now, we'll get the root (block 0 in range).
412 	 */
413 	if ((error = xfs_da_grow_inode(args, &blkno))) {
414 		return error;
415 	}
416 	ldb = xfs_dir2_da_to_db(args->geo, blkno);
417 	ASSERT(ldb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET));
418 	/*
419 	 * Initialize the leaf block, get a buffer for it.
420 	 */
421 	error = xfs_dir3_leaf_get_buf(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC);
422 	if (error)
423 		return error;
424 
425 	leaf = lbp->b_addr;
426 	hdr = dbp->b_addr;
427 	xfs_dir3_data_check(dp, dbp);
428 	btp = xfs_dir2_block_tail_p(args->geo, hdr);
429 	blp = xfs_dir2_block_leaf_p(btp);
430 	bf = xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
431 
432 	/*
433 	 * Set the counts in the leaf header.
434 	 */
435 	xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
436 	leafhdr.count = be32_to_cpu(btp->count);
437 	leafhdr.stale = be32_to_cpu(btp->stale);
438 	xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, &leafhdr);
439 	xfs_dir3_leaf_log_header(args, lbp);
440 
441 	/*
442 	 * Could compact these but I think we always do the conversion
443 	 * after squeezing out stale entries.
444 	 */
445 	memcpy(leafhdr.ents, blp,
446 		be32_to_cpu(btp->count) * sizeof(struct xfs_dir2_leaf_entry));
447 	xfs_dir3_leaf_log_ents(args, &leafhdr, lbp, 0, leafhdr.count - 1);
448 	needscan = 0;
449 	needlog = 1;
450 	/*
451 	 * Make the space formerly occupied by the leaf entries and block
452 	 * tail be free.
453 	 */
454 	xfs_dir2_data_make_free(args, dbp,
455 		(xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),
456 		(xfs_dir2_data_aoff_t)((char *)hdr + args->geo->blksize -
457 				       (char *)blp),
458 		&needlog, &needscan);
459 	/*
460 	 * Fix up the block header, make it a data block.
461 	 */
462 	dbp->b_ops = &xfs_dir3_data_buf_ops;
463 	xfs_trans_buf_set_type(tp, dbp, XFS_BLFT_DIR_DATA_BUF);
464 	if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC))
465 		hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
466 	else
467 		hdr->magic = cpu_to_be32(XFS_DIR3_DATA_MAGIC);
468 
469 	if (needscan)
470 		xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);
471 	/*
472 	 * Set up leaf tail and bests table.
473 	 */
474 	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
475 	ltp->bestcount = cpu_to_be32(1);
476 	bestsp = xfs_dir2_leaf_bests_p(ltp);
477 	bestsp[0] =  bf[0].length;
478 	/*
479 	 * Log the data header and leaf bests table.
480 	 */
481 	if (needlog)
482 		xfs_dir2_data_log_header(args, dbp);
483 	xfs_dir3_leaf_check(dp, lbp);
484 	xfs_dir3_data_check(dp, dbp);
485 	xfs_dir3_leaf_log_bests(args, lbp, 0, 0);
486 	return 0;
487 }
488 
489 STATIC void
xfs_dir3_leaf_find_stale(struct xfs_dir3_icleaf_hdr * leafhdr,struct xfs_dir2_leaf_entry * ents,int index,int * lowstale,int * highstale)490 xfs_dir3_leaf_find_stale(
491 	struct xfs_dir3_icleaf_hdr *leafhdr,
492 	struct xfs_dir2_leaf_entry *ents,
493 	int			index,
494 	int			*lowstale,
495 	int			*highstale)
496 {
497 	/*
498 	 * Find the first stale entry before our index, if any.
499 	 */
500 	for (*lowstale = index - 1; *lowstale >= 0; --*lowstale) {
501 		if (ents[*lowstale].address ==
502 		    cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
503 			break;
504 	}
505 
506 	/*
507 	 * Find the first stale entry at or after our index, if any.
508 	 * Stop if the result would require moving more entries than using
509 	 * lowstale.
510 	 */
511 	for (*highstale = index; *highstale < leafhdr->count; ++*highstale) {
512 		if (ents[*highstale].address ==
513 		    cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
514 			break;
515 		if (*lowstale >= 0 && index - *lowstale <= *highstale - index)
516 			break;
517 	}
518 }
519 
520 struct xfs_dir2_leaf_entry *
xfs_dir3_leaf_find_entry(struct xfs_dir3_icleaf_hdr * leafhdr,struct xfs_dir2_leaf_entry * ents,int index,int compact,int lowstale,int highstale,int * lfloglow,int * lfloghigh)521 xfs_dir3_leaf_find_entry(
522 	struct xfs_dir3_icleaf_hdr *leafhdr,
523 	struct xfs_dir2_leaf_entry *ents,
524 	int			index,		/* leaf table position */
525 	int			compact,	/* need to compact leaves */
526 	int			lowstale,	/* index of prev stale leaf */
527 	int			highstale,	/* index of next stale leaf */
528 	int			*lfloglow,	/* low leaf logging index */
529 	int			*lfloghigh)	/* high leaf logging index */
530 {
531 	if (!leafhdr->stale) {
532 		xfs_dir2_leaf_entry_t	*lep;	/* leaf entry table pointer */
533 
534 		/*
535 		 * Now we need to make room to insert the leaf entry.
536 		 *
537 		 * If there are no stale entries, just insert a hole at index.
538 		 */
539 		lep = &ents[index];
540 		if (index < leafhdr->count)
541 			memmove(lep + 1, lep,
542 				(leafhdr->count - index) * sizeof(*lep));
543 
544 		/*
545 		 * Record low and high logging indices for the leaf.
546 		 */
547 		*lfloglow = index;
548 		*lfloghigh = leafhdr->count++;
549 		return lep;
550 	}
551 
552 	/*
553 	 * There are stale entries.
554 	 *
555 	 * We will use one of them for the new entry.  It's probably not at
556 	 * the right location, so we'll have to shift some up or down first.
557 	 *
558 	 * If we didn't compact before, we need to find the nearest stale
559 	 * entries before and after our insertion point.
560 	 */
561 	if (compact == 0)
562 		xfs_dir3_leaf_find_stale(leafhdr, ents, index,
563 					 &lowstale, &highstale);
564 
565 	/*
566 	 * If the low one is better, use it.
567 	 */
568 	if (lowstale >= 0 &&
569 	    (highstale == leafhdr->count ||
570 	     index - lowstale - 1 < highstale - index)) {
571 		ASSERT(index - lowstale - 1 >= 0);
572 		ASSERT(ents[lowstale].address ==
573 		       cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
574 
575 		/*
576 		 * Copy entries up to cover the stale entry and make room
577 		 * for the new entry.
578 		 */
579 		if (index - lowstale - 1 > 0) {
580 			memmove(&ents[lowstale], &ents[lowstale + 1],
581 				(index - lowstale - 1) *
582 					sizeof(xfs_dir2_leaf_entry_t));
583 		}
584 		*lfloglow = min(lowstale, *lfloglow);
585 		*lfloghigh = max(index - 1, *lfloghigh);
586 		leafhdr->stale--;
587 		return &ents[index - 1];
588 	}
589 
590 	/*
591 	 * The high one is better, so use that one.
592 	 */
593 	ASSERT(highstale - index >= 0);
594 	ASSERT(ents[highstale].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
595 
596 	/*
597 	 * Copy entries down to cover the stale entry and make room for the
598 	 * new entry.
599 	 */
600 	if (highstale - index > 0) {
601 		memmove(&ents[index + 1], &ents[index],
602 			(highstale - index) * sizeof(xfs_dir2_leaf_entry_t));
603 	}
604 	*lfloglow = min(index, *lfloglow);
605 	*lfloghigh = max(highstale, *lfloghigh);
606 	leafhdr->stale--;
607 	return &ents[index];
608 }
609 
610 /*
611  * Add an entry to a leaf form directory.
612  */
613 int						/* error */
xfs_dir2_leaf_addname(struct xfs_da_args * args)614 xfs_dir2_leaf_addname(
615 	struct xfs_da_args	*args)		/* operation arguments */
616 {
617 	struct xfs_dir3_icleaf_hdr leafhdr;
618 	struct xfs_trans	*tp = args->trans;
619 	__be16			*bestsp;	/* freespace table in leaf */
620 	__be16			*tagp;		/* end of data entry */
621 	struct xfs_buf		*dbp;		/* data block buffer */
622 	struct xfs_buf		*lbp;		/* leaf's buffer */
623 	struct xfs_dir2_leaf	*leaf;		/* leaf structure */
624 	struct xfs_inode	*dp = args->dp;	/* incore directory inode */
625 	struct xfs_dir2_data_hdr *hdr;		/* data block header */
626 	struct xfs_dir2_data_entry *dep;	/* data block entry */
627 	struct xfs_dir2_leaf_entry *lep;	/* leaf entry table pointer */
628 	struct xfs_dir2_leaf_entry *ents;
629 	struct xfs_dir2_data_unused *dup;	/* data unused entry */
630 	struct xfs_dir2_leaf_tail *ltp;		/* leaf tail pointer */
631 	struct xfs_dir2_data_free *bf;		/* bestfree table */
632 	int			compact;	/* need to compact leaves */
633 	int			error;		/* error return value */
634 	int			grown;		/* allocated new data block */
635 	int			highstale = 0;	/* index of next stale leaf */
636 	int			i;		/* temporary, index */
637 	int			index;		/* leaf table position */
638 	int			length;		/* length of new entry */
639 	int			lfloglow;	/* low leaf logging index */
640 	int			lfloghigh;	/* high leaf logging index */
641 	int			lowstale = 0;	/* index of prev stale leaf */
642 	int			needbytes;	/* leaf block bytes needed */
643 	int			needlog;	/* need to log data header */
644 	int			needscan;	/* need to rescan data free */
645 	xfs_dir2_db_t		use_block;	/* data block number */
646 
647 	trace_xfs_dir2_leaf_addname(args);
648 
649 	error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, &lbp);
650 	if (error)
651 		return error;
652 
653 	/*
654 	 * Look up the entry by hash value and name.
655 	 * We know it's not there, our caller has already done a lookup.
656 	 * So the index is of the entry to insert in front of.
657 	 * But if there are dup hash values the index is of the first of those.
658 	 */
659 	index = xfs_dir2_leaf_search_hash(args, lbp);
660 	leaf = lbp->b_addr;
661 	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
662 	xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
663 	ents = leafhdr.ents;
664 	bestsp = xfs_dir2_leaf_bests_p(ltp);
665 	length = xfs_dir2_data_entsize(dp->i_mount, args->namelen);
666 
667 	/*
668 	 * See if there are any entries with the same hash value
669 	 * and space in their block for the new entry.
670 	 * This is good because it puts multiple same-hash value entries
671 	 * in a data block, improving the lookup of those entries.
672 	 */
673 	for (use_block = -1, lep = &ents[index];
674 	     index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
675 	     index++, lep++) {
676 		if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
677 			continue;
678 		i = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
679 		ASSERT(i < be32_to_cpu(ltp->bestcount));
680 		ASSERT(bestsp[i] != cpu_to_be16(NULLDATAOFF));
681 		if (be16_to_cpu(bestsp[i]) >= length) {
682 			use_block = i;
683 			break;
684 		}
685 	}
686 	/*
687 	 * Didn't find a block yet, linear search all the data blocks.
688 	 */
689 	if (use_block == -1) {
690 		for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) {
691 			/*
692 			 * Remember a block we see that's missing.
693 			 */
694 			if (bestsp[i] == cpu_to_be16(NULLDATAOFF) &&
695 			    use_block == -1)
696 				use_block = i;
697 			else if (be16_to_cpu(bestsp[i]) >= length) {
698 				use_block = i;
699 				break;
700 			}
701 		}
702 	}
703 	/*
704 	 * How many bytes do we need in the leaf block?
705 	 */
706 	needbytes = 0;
707 	if (!leafhdr.stale)
708 		needbytes += sizeof(xfs_dir2_leaf_entry_t);
709 	if (use_block == -1)
710 		needbytes += sizeof(xfs_dir2_data_off_t);
711 
712 	/*
713 	 * Now kill use_block if it refers to a missing block, so we
714 	 * can use it as an indication of allocation needed.
715 	 */
716 	if (use_block != -1 && bestsp[use_block] == cpu_to_be16(NULLDATAOFF))
717 		use_block = -1;
718 	/*
719 	 * If we don't have enough free bytes but we can make enough
720 	 * by compacting out stale entries, we'll do that.
721 	 */
722 	if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes &&
723 	    leafhdr.stale > 1)
724 		compact = 1;
725 
726 	/*
727 	 * Otherwise if we don't have enough free bytes we need to
728 	 * convert to node form.
729 	 */
730 	else if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes) {
731 		/*
732 		 * Just checking or no space reservation, give up.
733 		 */
734 		if ((args->op_flags & XFS_DA_OP_JUSTCHECK) ||
735 							args->total == 0) {
736 			xfs_trans_brelse(tp, lbp);
737 			return -ENOSPC;
738 		}
739 		/*
740 		 * Convert to node form.
741 		 */
742 		error = xfs_dir2_leaf_to_node(args, lbp);
743 		if (error)
744 			return error;
745 		/*
746 		 * Then add the new entry.
747 		 */
748 		return xfs_dir2_node_addname(args);
749 	}
750 	/*
751 	 * Otherwise it will fit without compaction.
752 	 */
753 	else
754 		compact = 0;
755 	/*
756 	 * If just checking, then it will fit unless we needed to allocate
757 	 * a new data block.
758 	 */
759 	if (args->op_flags & XFS_DA_OP_JUSTCHECK) {
760 		xfs_trans_brelse(tp, lbp);
761 		return use_block == -1 ? -ENOSPC : 0;
762 	}
763 	/*
764 	 * If no allocations are allowed, return now before we've
765 	 * changed anything.
766 	 */
767 	if (args->total == 0 && use_block == -1) {
768 		xfs_trans_brelse(tp, lbp);
769 		return -ENOSPC;
770 	}
771 	/*
772 	 * Need to compact the leaf entries, removing stale ones.
773 	 * Leave one stale entry behind - the one closest to our
774 	 * insertion index - and we'll shift that one to our insertion
775 	 * point later.
776 	 */
777 	if (compact) {
778 		xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale,
779 			&highstale, &lfloglow, &lfloghigh);
780 	}
781 	/*
782 	 * There are stale entries, so we'll need log-low and log-high
783 	 * impossibly bad values later.
784 	 */
785 	else if (leafhdr.stale) {
786 		lfloglow = leafhdr.count;
787 		lfloghigh = -1;
788 	}
789 	/*
790 	 * If there was no data block space found, we need to allocate
791 	 * a new one.
792 	 */
793 	if (use_block == -1) {
794 		/*
795 		 * Add the new data block.
796 		 */
797 		if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
798 				&use_block))) {
799 			xfs_trans_brelse(tp, lbp);
800 			return error;
801 		}
802 		/*
803 		 * Initialize the block.
804 		 */
805 		if ((error = xfs_dir3_data_init(args, use_block, &dbp))) {
806 			xfs_trans_brelse(tp, lbp);
807 			return error;
808 		}
809 		/*
810 		 * If we're adding a new data block on the end we need to
811 		 * extend the bests table.  Copy it up one entry.
812 		 */
813 		if (use_block >= be32_to_cpu(ltp->bestcount)) {
814 			bestsp--;
815 			memmove(&bestsp[0], &bestsp[1],
816 				be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0]));
817 			be32_add_cpu(&ltp->bestcount, 1);
818 			xfs_dir3_leaf_log_tail(args, lbp);
819 			xfs_dir3_leaf_log_bests(args, lbp, 0,
820 						be32_to_cpu(ltp->bestcount) - 1);
821 		}
822 		/*
823 		 * If we're filling in a previously empty block just log it.
824 		 */
825 		else
826 			xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
827 		hdr = dbp->b_addr;
828 		bf = xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
829 		bestsp[use_block] = bf[0].length;
830 		grown = 1;
831 	} else {
832 		/*
833 		 * Already had space in some data block.
834 		 * Just read that one in.
835 		 */
836 		error = xfs_dir3_data_read(tp, dp,
837 				   xfs_dir2_db_to_da(args->geo, use_block),
838 				   0, &dbp);
839 		if (error) {
840 			xfs_trans_brelse(tp, lbp);
841 			return error;
842 		}
843 		hdr = dbp->b_addr;
844 		bf = xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
845 		grown = 0;
846 	}
847 	/*
848 	 * Point to the biggest freespace in our data block.
849 	 */
850 	dup = (xfs_dir2_data_unused_t *)
851 	      ((char *)hdr + be16_to_cpu(bf[0].offset));
852 	needscan = needlog = 0;
853 	/*
854 	 * Mark the initial part of our freespace in use for the new entry.
855 	 */
856 	error = xfs_dir2_data_use_free(args, dbp, dup,
857 			(xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),
858 			length, &needlog, &needscan);
859 	if (error) {
860 		xfs_trans_brelse(tp, lbp);
861 		return error;
862 	}
863 	/*
864 	 * Initialize our new entry (at last).
865 	 */
866 	dep = (xfs_dir2_data_entry_t *)dup;
867 	dep->inumber = cpu_to_be64(args->inumber);
868 	dep->namelen = args->namelen;
869 	memcpy(dep->name, args->name, dep->namelen);
870 	xfs_dir2_data_put_ftype(dp->i_mount, dep, args->filetype);
871 	tagp = xfs_dir2_data_entry_tag_p(dp->i_mount, dep);
872 	*tagp = cpu_to_be16((char *)dep - (char *)hdr);
873 	/*
874 	 * Need to scan fix up the bestfree table.
875 	 */
876 	if (needscan)
877 		xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);
878 	/*
879 	 * Need to log the data block's header.
880 	 */
881 	if (needlog)
882 		xfs_dir2_data_log_header(args, dbp);
883 	xfs_dir2_data_log_entry(args, dbp, dep);
884 	/*
885 	 * If the bests table needs to be changed, do it.
886 	 * Log the change unless we've already done that.
887 	 */
888 	if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(bf[0].length)) {
889 		bestsp[use_block] = bf[0].length;
890 		if (!grown)
891 			xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
892 	}
893 
894 	lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale,
895 				       highstale, &lfloglow, &lfloghigh);
896 
897 	/*
898 	 * Fill in the new leaf entry.
899 	 */
900 	lep->hashval = cpu_to_be32(args->hashval);
901 	lep->address = cpu_to_be32(
902 				xfs_dir2_db_off_to_dataptr(args->geo, use_block,
903 				be16_to_cpu(*tagp)));
904 	/*
905 	 * Log the leaf fields and give up the buffers.
906 	 */
907 	xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, &leafhdr);
908 	xfs_dir3_leaf_log_header(args, lbp);
909 	xfs_dir3_leaf_log_ents(args, &leafhdr, lbp, lfloglow, lfloghigh);
910 	xfs_dir3_leaf_check(dp, lbp);
911 	xfs_dir3_data_check(dp, dbp);
912 	return 0;
913 }
914 
915 /*
916  * Compact out any stale entries in the leaf.
917  * Log the header and changed leaf entries, if any.
918  */
919 void
xfs_dir3_leaf_compact(xfs_da_args_t * args,struct xfs_dir3_icleaf_hdr * leafhdr,struct xfs_buf * bp)920 xfs_dir3_leaf_compact(
921 	xfs_da_args_t	*args,		/* operation arguments */
922 	struct xfs_dir3_icleaf_hdr *leafhdr,
923 	struct xfs_buf	*bp)		/* leaf buffer */
924 {
925 	int		from;		/* source leaf index */
926 	xfs_dir2_leaf_t	*leaf;		/* leaf structure */
927 	int		loglow;		/* first leaf entry to log */
928 	int		to;		/* target leaf index */
929 	struct xfs_inode *dp = args->dp;
930 
931 	leaf = bp->b_addr;
932 	if (!leafhdr->stale)
933 		return;
934 
935 	/*
936 	 * Compress out the stale entries in place.
937 	 */
938 	for (from = to = 0, loglow = -1; from < leafhdr->count; from++) {
939 		if (leafhdr->ents[from].address ==
940 		    cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
941 			continue;
942 		/*
943 		 * Only actually copy the entries that are different.
944 		 */
945 		if (from > to) {
946 			if (loglow == -1)
947 				loglow = to;
948 			leafhdr->ents[to] = leafhdr->ents[from];
949 		}
950 		to++;
951 	}
952 	/*
953 	 * Update and log the header, log the leaf entries.
954 	 */
955 	ASSERT(leafhdr->stale == from - to);
956 	leafhdr->count -= leafhdr->stale;
957 	leafhdr->stale = 0;
958 
959 	xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, leafhdr);
960 	xfs_dir3_leaf_log_header(args, bp);
961 	if (loglow != -1)
962 		xfs_dir3_leaf_log_ents(args, leafhdr, bp, loglow, to - 1);
963 }
964 
965 /*
966  * Compact the leaf entries, removing stale ones.
967  * Leave one stale entry behind - the one closest to our
968  * insertion index - and the caller will shift that one to our insertion
969  * point later.
970  * Return new insertion index, where the remaining stale entry is,
971  * and leaf logging indices.
972  */
973 void
xfs_dir3_leaf_compact_x1(struct xfs_dir3_icleaf_hdr * leafhdr,struct xfs_dir2_leaf_entry * ents,int * indexp,int * lowstalep,int * highstalep,int * lowlogp,int * highlogp)974 xfs_dir3_leaf_compact_x1(
975 	struct xfs_dir3_icleaf_hdr *leafhdr,
976 	struct xfs_dir2_leaf_entry *ents,
977 	int		*indexp,	/* insertion index */
978 	int		*lowstalep,	/* out: stale entry before us */
979 	int		*highstalep,	/* out: stale entry after us */
980 	int		*lowlogp,	/* out: low log index */
981 	int		*highlogp)	/* out: high log index */
982 {
983 	int		from;		/* source copy index */
984 	int		highstale;	/* stale entry at/after index */
985 	int		index;		/* insertion index */
986 	int		keepstale;	/* source index of kept stale */
987 	int		lowstale;	/* stale entry before index */
988 	int		newindex=0;	/* new insertion index */
989 	int		to;		/* destination copy index */
990 
991 	ASSERT(leafhdr->stale > 1);
992 	index = *indexp;
993 
994 	xfs_dir3_leaf_find_stale(leafhdr, ents, index, &lowstale, &highstale);
995 
996 	/*
997 	 * Pick the better of lowstale and highstale.
998 	 */
999 	if (lowstale >= 0 &&
1000 	    (highstale == leafhdr->count ||
1001 	     index - lowstale <= highstale - index))
1002 		keepstale = lowstale;
1003 	else
1004 		keepstale = highstale;
1005 	/*
1006 	 * Copy the entries in place, removing all the stale entries
1007 	 * except keepstale.
1008 	 */
1009 	for (from = to = 0; from < leafhdr->count; from++) {
1010 		/*
1011 		 * Notice the new value of index.
1012 		 */
1013 		if (index == from)
1014 			newindex = to;
1015 		if (from != keepstale &&
1016 		    ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {
1017 			if (from == to)
1018 				*lowlogp = to;
1019 			continue;
1020 		}
1021 		/*
1022 		 * Record the new keepstale value for the insertion.
1023 		 */
1024 		if (from == keepstale)
1025 			lowstale = highstale = to;
1026 		/*
1027 		 * Copy only the entries that have moved.
1028 		 */
1029 		if (from > to)
1030 			ents[to] = ents[from];
1031 		to++;
1032 	}
1033 	ASSERT(from > to);
1034 	/*
1035 	 * If the insertion point was past the last entry,
1036 	 * set the new insertion point accordingly.
1037 	 */
1038 	if (index == from)
1039 		newindex = to;
1040 	*indexp = newindex;
1041 	/*
1042 	 * Adjust the leaf header values.
1043 	 */
1044 	leafhdr->count -= from - to;
1045 	leafhdr->stale = 1;
1046 	/*
1047 	 * Remember the low/high stale value only in the "right"
1048 	 * direction.
1049 	 */
1050 	if (lowstale >= newindex)
1051 		lowstale = -1;
1052 	else
1053 		highstale = leafhdr->count;
1054 	*highlogp = leafhdr->count - 1;
1055 	*lowstalep = lowstale;
1056 	*highstalep = highstale;
1057 }
1058 
1059 /*
1060  * Log the bests entries indicated from a leaf1 block.
1061  */
1062 static void
xfs_dir3_leaf_log_bests(struct xfs_da_args * args,struct xfs_buf * bp,int first,int last)1063 xfs_dir3_leaf_log_bests(
1064 	struct xfs_da_args	*args,
1065 	struct xfs_buf		*bp,		/* leaf buffer */
1066 	int			first,		/* first entry to log */
1067 	int			last)		/* last entry to log */
1068 {
1069 	__be16			*firstb;	/* pointer to first entry */
1070 	__be16			*lastb;		/* pointer to last entry */
1071 	struct xfs_dir2_leaf	*leaf = bp->b_addr;
1072 	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
1073 
1074 	ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1075 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC));
1076 
1077 	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1078 	firstb = xfs_dir2_leaf_bests_p(ltp) + first;
1079 	lastb = xfs_dir2_leaf_bests_p(ltp) + last;
1080 	xfs_trans_log_buf(args->trans, bp,
1081 		(uint)((char *)firstb - (char *)leaf),
1082 		(uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
1083 }
1084 
1085 /*
1086  * Log the leaf entries indicated from a leaf1 or leafn block.
1087  */
1088 void
xfs_dir3_leaf_log_ents(struct xfs_da_args * args,struct xfs_dir3_icleaf_hdr * hdr,struct xfs_buf * bp,int first,int last)1089 xfs_dir3_leaf_log_ents(
1090 	struct xfs_da_args	*args,
1091 	struct xfs_dir3_icleaf_hdr *hdr,
1092 	struct xfs_buf		*bp,
1093 	int			first,
1094 	int			last)
1095 {
1096 	xfs_dir2_leaf_entry_t	*firstlep;	/* pointer to first entry */
1097 	xfs_dir2_leaf_entry_t	*lastlep;	/* pointer to last entry */
1098 	struct xfs_dir2_leaf	*leaf = bp->b_addr;
1099 
1100 	ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1101 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1102 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1103 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1104 
1105 	firstlep = &hdr->ents[first];
1106 	lastlep = &hdr->ents[last];
1107 	xfs_trans_log_buf(args->trans, bp,
1108 		(uint)((char *)firstlep - (char *)leaf),
1109 		(uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
1110 }
1111 
1112 /*
1113  * Log the header of the leaf1 or leafn block.
1114  */
1115 void
xfs_dir3_leaf_log_header(struct xfs_da_args * args,struct xfs_buf * bp)1116 xfs_dir3_leaf_log_header(
1117 	struct xfs_da_args	*args,
1118 	struct xfs_buf		*bp)
1119 {
1120 	struct xfs_dir2_leaf	*leaf = bp->b_addr;
1121 
1122 	ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1123 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1124 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1125 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1126 
1127 	xfs_trans_log_buf(args->trans, bp,
1128 			  (uint)((char *)&leaf->hdr - (char *)leaf),
1129 			  args->geo->leaf_hdr_size - 1);
1130 }
1131 
1132 /*
1133  * Log the tail of the leaf1 block.
1134  */
1135 STATIC void
xfs_dir3_leaf_log_tail(struct xfs_da_args * args,struct xfs_buf * bp)1136 xfs_dir3_leaf_log_tail(
1137 	struct xfs_da_args	*args,
1138 	struct xfs_buf		*bp)
1139 {
1140 	struct xfs_dir2_leaf	*leaf = bp->b_addr;
1141 	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
1142 
1143 	ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1144 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1145 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1146 	       leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1147 
1148 	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1149 	xfs_trans_log_buf(args->trans, bp, (uint)((char *)ltp - (char *)leaf),
1150 		(uint)(args->geo->blksize - 1));
1151 }
1152 
1153 /*
1154  * Look up the entry referred to by args in the leaf format directory.
1155  * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
1156  * is also used by the node-format code.
1157  */
1158 int
xfs_dir2_leaf_lookup(xfs_da_args_t * args)1159 xfs_dir2_leaf_lookup(
1160 	xfs_da_args_t		*args)		/* operation arguments */
1161 {
1162 	struct xfs_buf		*dbp;		/* data block buffer */
1163 	xfs_dir2_data_entry_t	*dep;		/* data block entry */
1164 	xfs_inode_t		*dp;		/* incore directory inode */
1165 	int			error;		/* error return code */
1166 	int			index;		/* found entry index */
1167 	struct xfs_buf		*lbp;		/* leaf buffer */
1168 	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1169 	xfs_trans_t		*tp;		/* transaction pointer */
1170 	struct xfs_dir3_icleaf_hdr leafhdr;
1171 
1172 	trace_xfs_dir2_leaf_lookup(args);
1173 
1174 	/*
1175 	 * Look up name in the leaf block, returning both buffers and index.
1176 	 */
1177 	error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp, &leafhdr);
1178 	if (error)
1179 		return error;
1180 
1181 	tp = args->trans;
1182 	dp = args->dp;
1183 	xfs_dir3_leaf_check(dp, lbp);
1184 
1185 	/*
1186 	 * Get to the leaf entry and contained data entry address.
1187 	 */
1188 	lep = &leafhdr.ents[index];
1189 
1190 	/*
1191 	 * Point to the data entry.
1192 	 */
1193 	dep = (xfs_dir2_data_entry_t *)
1194 	      ((char *)dbp->b_addr +
1195 	       xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
1196 	/*
1197 	 * Return the found inode number & CI name if appropriate
1198 	 */
1199 	args->inumber = be64_to_cpu(dep->inumber);
1200 	args->filetype = xfs_dir2_data_get_ftype(dp->i_mount, dep);
1201 	error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
1202 	xfs_trans_brelse(tp, dbp);
1203 	xfs_trans_brelse(tp, lbp);
1204 	return error;
1205 }
1206 
1207 /*
1208  * Look up name/hash in the leaf block.
1209  * Fill in indexp with the found index, and dbpp with the data buffer.
1210  * If not found dbpp will be NULL, and ENOENT comes back.
1211  * lbpp will always be filled in with the leaf buffer unless there's an error.
1212  */
1213 static int					/* error */
xfs_dir2_leaf_lookup_int(xfs_da_args_t * args,struct xfs_buf ** lbpp,int * indexp,struct xfs_buf ** dbpp,struct xfs_dir3_icleaf_hdr * leafhdr)1214 xfs_dir2_leaf_lookup_int(
1215 	xfs_da_args_t		*args,		/* operation arguments */
1216 	struct xfs_buf		**lbpp,		/* out: leaf buffer */
1217 	int			*indexp,	/* out: index in leaf block */
1218 	struct xfs_buf		**dbpp,		/* out: data buffer */
1219 	struct xfs_dir3_icleaf_hdr *leafhdr)
1220 {
1221 	xfs_dir2_db_t		curdb = -1;	/* current data block number */
1222 	struct xfs_buf		*dbp = NULL;	/* data buffer */
1223 	xfs_dir2_data_entry_t	*dep;		/* data entry */
1224 	xfs_inode_t		*dp;		/* incore directory inode */
1225 	int			error;		/* error return code */
1226 	int			index;		/* index in leaf block */
1227 	struct xfs_buf		*lbp;		/* leaf buffer */
1228 	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1229 	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1230 	xfs_mount_t		*mp;		/* filesystem mount point */
1231 	xfs_dir2_db_t		newdb;		/* new data block number */
1232 	xfs_trans_t		*tp;		/* transaction pointer */
1233 	xfs_dir2_db_t		cidb = -1;	/* case match data block no. */
1234 	enum xfs_dacmp		cmp;		/* name compare result */
1235 
1236 	dp = args->dp;
1237 	tp = args->trans;
1238 	mp = dp->i_mount;
1239 
1240 	error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, &lbp);
1241 	if (error)
1242 		return error;
1243 
1244 	*lbpp = lbp;
1245 	leaf = lbp->b_addr;
1246 	xfs_dir3_leaf_check(dp, lbp);
1247 	xfs_dir2_leaf_hdr_from_disk(mp, leafhdr, leaf);
1248 
1249 	/*
1250 	 * Look for the first leaf entry with our hash value.
1251 	 */
1252 	index = xfs_dir2_leaf_search_hash(args, lbp);
1253 	/*
1254 	 * Loop over all the entries with the right hash value
1255 	 * looking to match the name.
1256 	 */
1257 	for (lep = &leafhdr->ents[index];
1258 	     index < leafhdr->count &&
1259 			be32_to_cpu(lep->hashval) == args->hashval;
1260 	     lep++, index++) {
1261 		/*
1262 		 * Skip over stale leaf entries.
1263 		 */
1264 		if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
1265 			continue;
1266 		/*
1267 		 * Get the new data block number.
1268 		 */
1269 		newdb = xfs_dir2_dataptr_to_db(args->geo,
1270 					       be32_to_cpu(lep->address));
1271 		/*
1272 		 * If it's not the same as the old data block number,
1273 		 * need to pitch the old one and read the new one.
1274 		 */
1275 		if (newdb != curdb) {
1276 			if (dbp)
1277 				xfs_trans_brelse(tp, dbp);
1278 			error = xfs_dir3_data_read(tp, dp,
1279 					   xfs_dir2_db_to_da(args->geo, newdb),
1280 					   0, &dbp);
1281 			if (error) {
1282 				xfs_trans_brelse(tp, lbp);
1283 				return error;
1284 			}
1285 			curdb = newdb;
1286 		}
1287 		/*
1288 		 * Point to the data entry.
1289 		 */
1290 		dep = (xfs_dir2_data_entry_t *)((char *)dbp->b_addr +
1291 			xfs_dir2_dataptr_to_off(args->geo,
1292 						be32_to_cpu(lep->address)));
1293 		/*
1294 		 * Compare name and if it's an exact match, return the index
1295 		 * and buffer. If it's the first case-insensitive match, store
1296 		 * the index and buffer and continue looking for an exact match.
1297 		 */
1298 		cmp = xfs_dir2_compname(args, dep->name, dep->namelen);
1299 		if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
1300 			args->cmpresult = cmp;
1301 			*indexp = index;
1302 			/* case exact match: return the current buffer. */
1303 			if (cmp == XFS_CMP_EXACT) {
1304 				*dbpp = dbp;
1305 				return 0;
1306 			}
1307 			cidb = curdb;
1308 		}
1309 	}
1310 	ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
1311 	/*
1312 	 * Here, we can only be doing a lookup (not a rename or remove).
1313 	 * If a case-insensitive match was found earlier, re-read the
1314 	 * appropriate data block if required and return it.
1315 	 */
1316 	if (args->cmpresult == XFS_CMP_CASE) {
1317 		ASSERT(cidb != -1);
1318 		if (cidb != curdb) {
1319 			xfs_trans_brelse(tp, dbp);
1320 			error = xfs_dir3_data_read(tp, dp,
1321 					   xfs_dir2_db_to_da(args->geo, cidb),
1322 					   0, &dbp);
1323 			if (error) {
1324 				xfs_trans_brelse(tp, lbp);
1325 				return error;
1326 			}
1327 		}
1328 		*dbpp = dbp;
1329 		return 0;
1330 	}
1331 	/*
1332 	 * No match found, return -ENOENT.
1333 	 */
1334 	ASSERT(cidb == -1);
1335 	if (dbp)
1336 		xfs_trans_brelse(tp, dbp);
1337 	xfs_trans_brelse(tp, lbp);
1338 	return -ENOENT;
1339 }
1340 
1341 /*
1342  * Remove an entry from a leaf format directory.
1343  */
1344 int						/* error */
xfs_dir2_leaf_removename(xfs_da_args_t * args)1345 xfs_dir2_leaf_removename(
1346 	xfs_da_args_t		*args)		/* operation arguments */
1347 {
1348 	struct xfs_da_geometry	*geo = args->geo;
1349 	__be16			*bestsp;	/* leaf block best freespace */
1350 	xfs_dir2_data_hdr_t	*hdr;		/* data block header */
1351 	xfs_dir2_db_t		db;		/* data block number */
1352 	struct xfs_buf		*dbp;		/* data block buffer */
1353 	xfs_dir2_data_entry_t	*dep;		/* data entry structure */
1354 	xfs_inode_t		*dp;		/* incore directory inode */
1355 	int			error;		/* error return code */
1356 	xfs_dir2_db_t		i;		/* temporary data block # */
1357 	int			index;		/* index into leaf entries */
1358 	struct xfs_buf		*lbp;		/* leaf buffer */
1359 	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1360 	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1361 	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
1362 	int			needlog;	/* need to log data header */
1363 	int			needscan;	/* need to rescan data frees */
1364 	xfs_dir2_data_off_t	oldbest;	/* old value of best free */
1365 	struct xfs_dir2_data_free *bf;		/* bestfree table */
1366 	struct xfs_dir3_icleaf_hdr leafhdr;
1367 
1368 	trace_xfs_dir2_leaf_removename(args);
1369 
1370 	/*
1371 	 * Lookup the leaf entry, get the leaf and data blocks read in.
1372 	 */
1373 	error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp, &leafhdr);
1374 	if (error)
1375 		return error;
1376 
1377 	dp = args->dp;
1378 	leaf = lbp->b_addr;
1379 	hdr = dbp->b_addr;
1380 	xfs_dir3_data_check(dp, dbp);
1381 	bf = xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
1382 
1383 	/*
1384 	 * Point to the leaf entry, use that to point to the data entry.
1385 	 */
1386 	lep = &leafhdr.ents[index];
1387 	db = xfs_dir2_dataptr_to_db(geo, be32_to_cpu(lep->address));
1388 	dep = (xfs_dir2_data_entry_t *)((char *)hdr +
1389 		xfs_dir2_dataptr_to_off(geo, be32_to_cpu(lep->address)));
1390 	needscan = needlog = 0;
1391 	oldbest = be16_to_cpu(bf[0].length);
1392 	ltp = xfs_dir2_leaf_tail_p(geo, leaf);
1393 	bestsp = xfs_dir2_leaf_bests_p(ltp);
1394 	if (be16_to_cpu(bestsp[db]) != oldbest) {
1395 		xfs_buf_mark_corrupt(lbp);
1396 		return -EFSCORRUPTED;
1397 	}
1398 	/*
1399 	 * Mark the former data entry unused.
1400 	 */
1401 	xfs_dir2_data_make_free(args, dbp,
1402 		(xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),
1403 		xfs_dir2_data_entsize(dp->i_mount, dep->namelen), &needlog,
1404 		&needscan);
1405 	/*
1406 	 * We just mark the leaf entry stale by putting a null in it.
1407 	 */
1408 	leafhdr.stale++;
1409 	xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, &leafhdr);
1410 	xfs_dir3_leaf_log_header(args, lbp);
1411 
1412 	lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
1413 	xfs_dir3_leaf_log_ents(args, &leafhdr, lbp, index, index);
1414 
1415 	/*
1416 	 * Scan the freespace in the data block again if necessary,
1417 	 * log the data block header if necessary.
1418 	 */
1419 	if (needscan)
1420 		xfs_dir2_data_freescan(dp->i_mount, hdr, &needlog);
1421 	if (needlog)
1422 		xfs_dir2_data_log_header(args, dbp);
1423 	/*
1424 	 * If the longest freespace in the data block has changed,
1425 	 * put the new value in the bests table and log that.
1426 	 */
1427 	if (be16_to_cpu(bf[0].length) != oldbest) {
1428 		bestsp[db] = bf[0].length;
1429 		xfs_dir3_leaf_log_bests(args, lbp, db, db);
1430 	}
1431 	xfs_dir3_data_check(dp, dbp);
1432 	/*
1433 	 * If the data block is now empty then get rid of the data block.
1434 	 */
1435 	if (be16_to_cpu(bf[0].length) ==
1436 	    geo->blksize - geo->data_entry_offset) {
1437 		ASSERT(db != geo->datablk);
1438 		if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1439 			/*
1440 			 * Nope, can't get rid of it because it caused
1441 			 * allocation of a bmap btree block to do so.
1442 			 * Just go on, returning success, leaving the
1443 			 * empty block in place.
1444 			 */
1445 			if (error == -ENOSPC && args->total == 0)
1446 				error = 0;
1447 			xfs_dir3_leaf_check(dp, lbp);
1448 			return error;
1449 		}
1450 		dbp = NULL;
1451 		/*
1452 		 * If this is the last data block then compact the
1453 		 * bests table by getting rid of entries.
1454 		 */
1455 		if (db == be32_to_cpu(ltp->bestcount) - 1) {
1456 			/*
1457 			 * Look for the last active entry (i).
1458 			 */
1459 			for (i = db - 1; i > 0; i--) {
1460 				if (bestsp[i] != cpu_to_be16(NULLDATAOFF))
1461 					break;
1462 			}
1463 			/*
1464 			 * Copy the table down so inactive entries at the
1465 			 * end are removed.
1466 			 */
1467 			memmove(&bestsp[db - i], bestsp,
1468 				(be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp));
1469 			be32_add_cpu(&ltp->bestcount, -(db - i));
1470 			xfs_dir3_leaf_log_tail(args, lbp);
1471 			xfs_dir3_leaf_log_bests(args, lbp, 0,
1472 						be32_to_cpu(ltp->bestcount) - 1);
1473 		} else
1474 			bestsp[db] = cpu_to_be16(NULLDATAOFF);
1475 	}
1476 	/*
1477 	 * If the data block was not the first one, drop it.
1478 	 */
1479 	else if (db != geo->datablk)
1480 		dbp = NULL;
1481 
1482 	xfs_dir3_leaf_check(dp, lbp);
1483 	/*
1484 	 * See if we can convert to block form.
1485 	 */
1486 	return xfs_dir2_leaf_to_block(args, lbp, dbp);
1487 }
1488 
1489 /*
1490  * Replace the inode number in a leaf format directory entry.
1491  */
1492 int						/* error */
xfs_dir2_leaf_replace(xfs_da_args_t * args)1493 xfs_dir2_leaf_replace(
1494 	xfs_da_args_t		*args)		/* operation arguments */
1495 {
1496 	struct xfs_buf		*dbp;		/* data block buffer */
1497 	xfs_dir2_data_entry_t	*dep;		/* data block entry */
1498 	xfs_inode_t		*dp;		/* incore directory inode */
1499 	int			error;		/* error return code */
1500 	int			index;		/* index of leaf entry */
1501 	struct xfs_buf		*lbp;		/* leaf buffer */
1502 	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1503 	xfs_trans_t		*tp;		/* transaction pointer */
1504 	struct xfs_dir3_icleaf_hdr leafhdr;
1505 
1506 	trace_xfs_dir2_leaf_replace(args);
1507 
1508 	/*
1509 	 * Look up the entry.
1510 	 */
1511 	error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp, &leafhdr);
1512 	if (error)
1513 		return error;
1514 
1515 	dp = args->dp;
1516 	/*
1517 	 * Point to the leaf entry, get data address from it.
1518 	 */
1519 	lep = &leafhdr.ents[index];
1520 	/*
1521 	 * Point to the data entry.
1522 	 */
1523 	dep = (xfs_dir2_data_entry_t *)
1524 	      ((char *)dbp->b_addr +
1525 	       xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
1526 	ASSERT(args->inumber != be64_to_cpu(dep->inumber));
1527 	/*
1528 	 * Put the new inode number in, log it.
1529 	 */
1530 	dep->inumber = cpu_to_be64(args->inumber);
1531 	xfs_dir2_data_put_ftype(dp->i_mount, dep, args->filetype);
1532 	tp = args->trans;
1533 	xfs_dir2_data_log_entry(args, dbp, dep);
1534 	xfs_dir3_leaf_check(dp, lbp);
1535 	xfs_trans_brelse(tp, lbp);
1536 	return 0;
1537 }
1538 
1539 /*
1540  * Return index in the leaf block (lbp) which is either the first
1541  * one with this hash value, or if there are none, the insert point
1542  * for that hash value.
1543  */
1544 int						/* index value */
xfs_dir2_leaf_search_hash(xfs_da_args_t * args,struct xfs_buf * lbp)1545 xfs_dir2_leaf_search_hash(
1546 	xfs_da_args_t		*args,		/* operation arguments */
1547 	struct xfs_buf		*lbp)		/* leaf buffer */
1548 {
1549 	xfs_dahash_t		hash=0;		/* hash from this entry */
1550 	xfs_dahash_t		hashwant;	/* hash value looking for */
1551 	int			high;		/* high leaf index */
1552 	int			low;		/* low leaf index */
1553 	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
1554 	int			mid=0;		/* current leaf index */
1555 	struct xfs_dir3_icleaf_hdr leafhdr;
1556 
1557 	xfs_dir2_leaf_hdr_from_disk(args->dp->i_mount, &leafhdr, lbp->b_addr);
1558 
1559 	/*
1560 	 * Note, the table cannot be empty, so we have to go through the loop.
1561 	 * Binary search the leaf entries looking for our hash value.
1562 	 */
1563 	for (lep = leafhdr.ents, low = 0, high = leafhdr.count - 1,
1564 		hashwant = args->hashval;
1565 	     low <= high; ) {
1566 		mid = (low + high) >> 1;
1567 		if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
1568 			break;
1569 		if (hash < hashwant)
1570 			low = mid + 1;
1571 		else
1572 			high = mid - 1;
1573 	}
1574 	/*
1575 	 * Found one, back up through all the equal hash values.
1576 	 */
1577 	if (hash == hashwant) {
1578 		while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) {
1579 			mid--;
1580 		}
1581 	}
1582 	/*
1583 	 * Need to point to an entry higher than ours.
1584 	 */
1585 	else if (hash < hashwant)
1586 		mid++;
1587 	return mid;
1588 }
1589 
1590 /*
1591  * Trim off a trailing data block.  We know it's empty since the leaf
1592  * freespace table says so.
1593  */
1594 int						/* error */
xfs_dir2_leaf_trim_data(xfs_da_args_t * args,struct xfs_buf * lbp,xfs_dir2_db_t db)1595 xfs_dir2_leaf_trim_data(
1596 	xfs_da_args_t		*args,		/* operation arguments */
1597 	struct xfs_buf		*lbp,		/* leaf buffer */
1598 	xfs_dir2_db_t		db)		/* data block number */
1599 {
1600 	struct xfs_da_geometry	*geo = args->geo;
1601 	__be16			*bestsp;	/* leaf bests table */
1602 	struct xfs_buf		*dbp;		/* data block buffer */
1603 	xfs_inode_t		*dp;		/* incore directory inode */
1604 	int			error;		/* error return value */
1605 	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1606 	xfs_dir2_leaf_tail_t	*ltp;		/* leaf tail structure */
1607 	xfs_trans_t		*tp;		/* transaction pointer */
1608 
1609 	dp = args->dp;
1610 	tp = args->trans;
1611 	/*
1612 	 * Read the offending data block.  We need its buffer.
1613 	 */
1614 	error = xfs_dir3_data_read(tp, dp, xfs_dir2_db_to_da(geo, db), 0, &dbp);
1615 	if (error)
1616 		return error;
1617 
1618 	leaf = lbp->b_addr;
1619 	ltp = xfs_dir2_leaf_tail_p(geo, leaf);
1620 
1621 #ifdef DEBUG
1622 {
1623 	struct xfs_dir2_data_hdr *hdr = dbp->b_addr;
1624 	struct xfs_dir2_data_free *bf =
1625 		xfs_dir2_data_bestfree_p(dp->i_mount, hdr);
1626 
1627 	ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
1628 	       hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
1629 	ASSERT(be16_to_cpu(bf[0].length) ==
1630 	       geo->blksize - geo->data_entry_offset);
1631 	ASSERT(db == be32_to_cpu(ltp->bestcount) - 1);
1632 }
1633 #endif
1634 
1635 	/*
1636 	 * Get rid of the data block.
1637 	 */
1638 	if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1639 		ASSERT(error != -ENOSPC);
1640 		xfs_trans_brelse(tp, dbp);
1641 		return error;
1642 	}
1643 	/*
1644 	 * Eliminate the last bests entry from the table.
1645 	 */
1646 	bestsp = xfs_dir2_leaf_bests_p(ltp);
1647 	be32_add_cpu(&ltp->bestcount, -1);
1648 	memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp));
1649 	xfs_dir3_leaf_log_tail(args, lbp);
1650 	xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
1651 	return 0;
1652 }
1653 
1654 static inline size_t
xfs_dir3_leaf_size(struct xfs_dir3_icleaf_hdr * hdr,int counts)1655 xfs_dir3_leaf_size(
1656 	struct xfs_dir3_icleaf_hdr	*hdr,
1657 	int				counts)
1658 {
1659 	int	entries;
1660 	int	hdrsize;
1661 
1662 	entries = hdr->count - hdr->stale;
1663 	if (hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
1664 	    hdr->magic == XFS_DIR2_LEAFN_MAGIC)
1665 		hdrsize = sizeof(struct xfs_dir2_leaf_hdr);
1666 	else
1667 		hdrsize = sizeof(struct xfs_dir3_leaf_hdr);
1668 
1669 	return hdrsize + entries * sizeof(xfs_dir2_leaf_entry_t)
1670 	               + counts * sizeof(xfs_dir2_data_off_t)
1671 		       + sizeof(xfs_dir2_leaf_tail_t);
1672 }
1673 
1674 /*
1675  * Convert node form directory to leaf form directory.
1676  * The root of the node form dir needs to already be a LEAFN block.
1677  * Just return if we can't do anything.
1678  */
1679 int						/* error */
xfs_dir2_node_to_leaf(xfs_da_state_t * state)1680 xfs_dir2_node_to_leaf(
1681 	xfs_da_state_t		*state)		/* directory operation state */
1682 {
1683 	xfs_da_args_t		*args;		/* operation arguments */
1684 	xfs_inode_t		*dp;		/* incore directory inode */
1685 	int			error;		/* error return code */
1686 	struct xfs_buf		*fbp;		/* buffer for freespace block */
1687 	xfs_fileoff_t		fo;		/* freespace file offset */
1688 	struct xfs_buf		*lbp;		/* buffer for leaf block */
1689 	xfs_dir2_leaf_tail_t	*ltp;		/* tail of leaf structure */
1690 	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
1691 	xfs_mount_t		*mp;		/* filesystem mount point */
1692 	int			rval;		/* successful free trim? */
1693 	xfs_trans_t		*tp;		/* transaction pointer */
1694 	struct xfs_dir3_icleaf_hdr leafhdr;
1695 	struct xfs_dir3_icfree_hdr freehdr;
1696 
1697 	/*
1698 	 * There's more than a leaf level in the btree, so there must
1699 	 * be multiple leafn blocks.  Give up.
1700 	 */
1701 	if (state->path.active > 1)
1702 		return 0;
1703 	args = state->args;
1704 
1705 	trace_xfs_dir2_node_to_leaf(args);
1706 
1707 	mp = state->mp;
1708 	dp = args->dp;
1709 	tp = args->trans;
1710 	/*
1711 	 * Get the last offset in the file.
1712 	 */
1713 	if ((error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK))) {
1714 		return error;
1715 	}
1716 	fo -= args->geo->fsbcount;
1717 	/*
1718 	 * If there are freespace blocks other than the first one,
1719 	 * take this opportunity to remove trailing empty freespace blocks
1720 	 * that may have been left behind during no-space-reservation
1721 	 * operations.
1722 	 */
1723 	while (fo > args->geo->freeblk) {
1724 		if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
1725 			return error;
1726 		}
1727 		if (rval)
1728 			fo -= args->geo->fsbcount;
1729 		else
1730 			return 0;
1731 	}
1732 	/*
1733 	 * Now find the block just before the freespace block.
1734 	 */
1735 	if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
1736 		return error;
1737 	}
1738 	/*
1739 	 * If it's not the single leaf block, give up.
1740 	 */
1741 	if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + args->geo->blksize)
1742 		return 0;
1743 	lbp = state->path.blk[0].bp;
1744 	leaf = lbp->b_addr;
1745 	xfs_dir2_leaf_hdr_from_disk(mp, &leafhdr, leaf);
1746 
1747 	ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
1748 	       leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
1749 
1750 	/*
1751 	 * Read the freespace block.
1752 	 */
1753 	error = xfs_dir2_free_read(tp, dp,  args->geo->freeblk, &fbp);
1754 	if (error)
1755 		return error;
1756 	xfs_dir2_free_hdr_from_disk(mp, &freehdr, fbp->b_addr);
1757 
1758 	ASSERT(!freehdr.firstdb);
1759 
1760 	/*
1761 	 * Now see if the leafn and free data will fit in a leaf1.
1762 	 * If not, release the buffer and give up.
1763 	 */
1764 	if (xfs_dir3_leaf_size(&leafhdr, freehdr.nvalid) > args->geo->blksize) {
1765 		xfs_trans_brelse(tp, fbp);
1766 		return 0;
1767 	}
1768 
1769 	/*
1770 	 * If the leaf has any stale entries in it, compress them out.
1771 	 */
1772 	if (leafhdr.stale)
1773 		xfs_dir3_leaf_compact(args, &leafhdr, lbp);
1774 
1775 	lbp->b_ops = &xfs_dir3_leaf1_buf_ops;
1776 	xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAF1_BUF);
1777 	leafhdr.magic = (leafhdr.magic == XFS_DIR2_LEAFN_MAGIC)
1778 					? XFS_DIR2_LEAF1_MAGIC
1779 					: XFS_DIR3_LEAF1_MAGIC;
1780 
1781 	/*
1782 	 * Set up the leaf tail from the freespace block.
1783 	 */
1784 	ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
1785 	ltp->bestcount = cpu_to_be32(freehdr.nvalid);
1786 
1787 	/*
1788 	 * Set up the leaf bests table.
1789 	 */
1790 	memcpy(xfs_dir2_leaf_bests_p(ltp), freehdr.bests,
1791 		freehdr.nvalid * sizeof(xfs_dir2_data_off_t));
1792 
1793 	xfs_dir2_leaf_hdr_to_disk(mp, leaf, &leafhdr);
1794 	xfs_dir3_leaf_log_header(args, lbp);
1795 	xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
1796 	xfs_dir3_leaf_log_tail(args, lbp);
1797 	xfs_dir3_leaf_check(dp, lbp);
1798 
1799 	/*
1800 	 * Get rid of the freespace block.
1801 	 */
1802 	error = xfs_dir2_shrink_inode(args,
1803 			xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET),
1804 			fbp);
1805 	if (error) {
1806 		/*
1807 		 * This can't fail here because it can only happen when
1808 		 * punching out the middle of an extent, and this is an
1809 		 * isolated block.
1810 		 */
1811 		ASSERT(error != -ENOSPC);
1812 		return error;
1813 	}
1814 	fbp = NULL;
1815 	/*
1816 	 * Now see if we can convert the single-leaf directory
1817 	 * down to a block form directory.
1818 	 * This routine always kills the dabuf for the leaf, so
1819 	 * eliminate it from the path.
1820 	 */
1821 	error = xfs_dir2_leaf_to_block(args, lbp, NULL);
1822 	state->path.blk[0].bp = NULL;
1823 	return error;
1824 }
1825