blob: 16fdc0e627a7640659814a527ccfc12b97ef6203 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Nathan Scott7b718762005-11-02 14:58:39 +11002 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc.
Dave Chinner24df33b2013-04-12 07:30:21 +10003 * Copyright (c) 2013 Red Hat, Inc.
Nathan Scott7b718762005-11-02 14:58:39 +11004 * All Rights Reserved.
Linus Torvalds1da177e2005-04-16 15:20:36 -07005 *
Nathan Scott7b718762005-11-02 14:58:39 +11006 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
Linus Torvalds1da177e2005-04-16 15:20:36 -07008 * published by the Free Software Foundation.
9 *
Nathan Scott7b718762005-11-02 14:58:39 +110010 * 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.
Linus Torvalds1da177e2005-04-16 15:20:36 -070014 *
Nathan Scott7b718762005-11-02 14:58:39 +110015 * 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
Linus Torvalds1da177e2005-04-16 15:20:36 -070018 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070019#include "xfs.h"
Nathan Scotta844f452005-11-02 14:38:42 +110020#include "xfs_fs.h"
Dave Chinnera4fbe6a2013-10-23 10:51:50 +110021#include "xfs_format.h"
Dave Chinner239880e2013-10-23 10:50:10 +110022#include "xfs_log_format.h"
23#include "xfs_trans_resv.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070024#include "xfs_sb.h"
25#include "xfs_ag.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070026#include "xfs_mount.h"
Dave Chinner57062782013-10-15 09:17:51 +110027#include "xfs_da_format.h"
Nathan Scotta844f452005-11-02 14:38:42 +110028#include "xfs_da_btree.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070029#include "xfs_inode.h"
30#include "xfs_bmap.h"
Dave Chinner2b9ab5a2013-08-12 20:49:37 +100031#include "xfs_dir2.h"
Christoph Hellwig57926642011-07-13 13:43:48 +020032#include "xfs_dir2_priv.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070033#include "xfs_error.h"
Christoph Hellwig0b1b2132009-12-14 23:14:59 +000034#include "xfs_trace.h"
Dave Chinner239880e2013-10-23 10:50:10 +110035#include "xfs_trans.h"
Dave Chinner24df33b2013-04-12 07:30:21 +100036#include "xfs_buf_item.h"
37#include "xfs_cksum.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070038
39/*
40 * Local function declarations.
41 */
Dave Chinner1d9025e2012-06-22 18:50:14 +100042static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, struct xfs_buf **lbpp,
43 int *indexp, struct xfs_buf **dbpp);
Dave Chinner24df33b2013-04-12 07:30:21 +100044static void xfs_dir3_leaf_log_bests(struct xfs_trans *tp, struct xfs_buf *bp,
Christoph Hellwigba0f32d2005-06-21 15:36:52 +100045 int first, int last);
Dave Chinner24df33b2013-04-12 07:30:21 +100046static void xfs_dir3_leaf_log_tail(struct xfs_trans *tp, struct xfs_buf *bp);
Christoph Hellwigba0f32d2005-06-21 15:36:52 +100047
Dave Chinner24df33b2013-04-12 07:30:21 +100048/*
49 * Check the internal consistency of a leaf1 block.
50 * Pop an assert if something is wrong.
51 */
52#ifdef DEBUG
Dave Chinner41419562013-10-29 22:11:50 +110053#define xfs_dir3_leaf_check(dp, bp) \
Dave Chinner24df33b2013-04-12 07:30:21 +100054do { \
Dave Chinner41419562013-10-29 22:11:50 +110055 if (!xfs_dir3_leaf1_check((dp), (bp))) \
Dave Chinner24df33b2013-04-12 07:30:21 +100056 ASSERT(0); \
57} while (0);
58
59STATIC bool
60xfs_dir3_leaf1_check(
Dave Chinner41419562013-10-29 22:11:50 +110061 struct xfs_inode *dp,
Dave Chinner24df33b2013-04-12 07:30:21 +100062 struct xfs_buf *bp)
63{
64 struct xfs_dir2_leaf *leaf = bp->b_addr;
65 struct xfs_dir3_icleaf_hdr leafhdr;
66
67 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
68
69 if (leafhdr.magic == XFS_DIR3_LEAF1_MAGIC) {
70 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
71 if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
72 return false;
73 } else if (leafhdr.magic != XFS_DIR2_LEAF1_MAGIC)
74 return false;
75
Dave Chinner41419562013-10-29 22:11:50 +110076 return xfs_dir3_leaf_check_int(dp->i_mount, dp, &leafhdr, leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +100077}
78#else
Dave Chinner41419562013-10-29 22:11:50 +110079#define xfs_dir3_leaf_check(dp, bp)
Dave Chinner24df33b2013-04-12 07:30:21 +100080#endif
81
82void
83xfs_dir3_leaf_hdr_from_disk(
84 struct xfs_dir3_icleaf_hdr *to,
85 struct xfs_dir2_leaf *from)
86{
87 if (from->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
88 from->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC)) {
89 to->forw = be32_to_cpu(from->hdr.info.forw);
90 to->back = be32_to_cpu(from->hdr.info.back);
91 to->magic = be16_to_cpu(from->hdr.info.magic);
92 to->count = be16_to_cpu(from->hdr.count);
93 to->stale = be16_to_cpu(from->hdr.stale);
94 } else {
95 struct xfs_dir3_leaf_hdr *hdr3 = (struct xfs_dir3_leaf_hdr *)from;
96
97 to->forw = be32_to_cpu(hdr3->info.hdr.forw);
98 to->back = be32_to_cpu(hdr3->info.hdr.back);
99 to->magic = be16_to_cpu(hdr3->info.hdr.magic);
100 to->count = be16_to_cpu(hdr3->count);
101 to->stale = be16_to_cpu(hdr3->stale);
102 }
103
104 ASSERT(to->magic == XFS_DIR2_LEAF1_MAGIC ||
105 to->magic == XFS_DIR3_LEAF1_MAGIC ||
106 to->magic == XFS_DIR2_LEAFN_MAGIC ||
107 to->magic == XFS_DIR3_LEAFN_MAGIC);
108}
109
110void
111xfs_dir3_leaf_hdr_to_disk(
112 struct xfs_dir2_leaf *to,
113 struct xfs_dir3_icleaf_hdr *from)
114{
115 ASSERT(from->magic == XFS_DIR2_LEAF1_MAGIC ||
116 from->magic == XFS_DIR3_LEAF1_MAGIC ||
117 from->magic == XFS_DIR2_LEAFN_MAGIC ||
118 from->magic == XFS_DIR3_LEAFN_MAGIC);
119
120 if (from->magic == XFS_DIR2_LEAF1_MAGIC ||
121 from->magic == XFS_DIR2_LEAFN_MAGIC) {
122 to->hdr.info.forw = cpu_to_be32(from->forw);
123 to->hdr.info.back = cpu_to_be32(from->back);
124 to->hdr.info.magic = cpu_to_be16(from->magic);
125 to->hdr.count = cpu_to_be16(from->count);
126 to->hdr.stale = cpu_to_be16(from->stale);
127 } else {
128 struct xfs_dir3_leaf_hdr *hdr3 = (struct xfs_dir3_leaf_hdr *)to;
129
130 hdr3->info.hdr.forw = cpu_to_be32(from->forw);
131 hdr3->info.hdr.back = cpu_to_be32(from->back);
132 hdr3->info.hdr.magic = cpu_to_be16(from->magic);
133 hdr3->count = cpu_to_be16(from->count);
134 hdr3->stale = cpu_to_be16(from->stale);
135 }
136}
137
138bool
139xfs_dir3_leaf_check_int(
140 struct xfs_mount *mp,
Dave Chinner41419562013-10-29 22:11:50 +1100141 struct xfs_inode *dp,
Dave Chinner24df33b2013-04-12 07:30:21 +1000142 struct xfs_dir3_icleaf_hdr *hdr,
143 struct xfs_dir2_leaf *leaf)
144{
145 struct xfs_dir2_leaf_entry *ents;
146 xfs_dir2_leaf_tail_t *ltp;
147 int stale;
148 int i;
Dave Chinner41419562013-10-29 22:11:50 +1100149 const struct xfs_dir_ops *ops;
Dave Chinner24df33b2013-04-12 07:30:21 +1000150
Dave Chinner41419562013-10-29 22:11:50 +1100151 /*
152 * we can be passed a null dp here from a verifier, so we need to go the
153 * hard way to get them.
154 */
155 ops = xfs_dir_get_ops(mp, dp);
156
157 ents = ops->leaf_ents_p(leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +1000158 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
159
160 /*
161 * XXX (dgc): This value is not restrictive enough.
162 * Should factor in the size of the bests table as well.
163 * We can deduce a value for that from di_size.
164 */
Dave Chinner41419562013-10-29 22:11:50 +1100165 if (hdr->count > ops->leaf_max_ents(mp))
Dave Chinner24df33b2013-04-12 07:30:21 +1000166 return false;
167
168 /* Leaves and bests don't overlap in leaf format. */
169 if ((hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
170 hdr->magic == XFS_DIR3_LEAF1_MAGIC) &&
171 (char *)&ents[hdr->count] > (char *)xfs_dir2_leaf_bests_p(ltp))
172 return false;
173
174 /* Check hash value order, count stale entries. */
175 for (i = stale = 0; i < hdr->count; i++) {
176 if (i + 1 < hdr->count) {
177 if (be32_to_cpu(ents[i].hashval) >
178 be32_to_cpu(ents[i + 1].hashval))
179 return false;
180 }
181 if (ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
182 stale++;
183 }
184 if (hdr->stale != stale)
185 return false;
186 return true;
187}
188
Dave Chinner0f295a22013-09-03 10:06:58 +1000189/*
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 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000194static bool
195xfs_dir3_leaf_verify(
Dave Chinnere6f76672012-11-12 22:54:15 +1100196 struct xfs_buf *bp,
Dave Chinner24df33b2013-04-12 07:30:21 +1000197 __uint16_t magic)
Dave Chinnere6f76672012-11-12 22:54:15 +1100198{
199 struct xfs_mount *mp = bp->b_target->bt_mount;
Dave Chinner24df33b2013-04-12 07:30:21 +1000200 struct xfs_dir2_leaf *leaf = bp->b_addr;
201 struct xfs_dir3_icleaf_hdr leafhdr;
Dave Chinnere6f76672012-11-12 22:54:15 +1100202
Dave Chinner24df33b2013-04-12 07:30:21 +1000203 ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
204
Dave Chinner24df33b2013-04-12 07:30:21 +1000205 if (xfs_sb_version_hascrc(&mp->m_sb)) {
206 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
Dave Chinner0f295a22013-09-03 10:06:58 +1000207 __uint16_t magic3;
Dave Chinner24df33b2013-04-12 07:30:21 +1000208
Dave Chinner0f295a22013-09-03 10:06:58 +1000209 magic3 = (magic == XFS_DIR2_LEAF1_MAGIC) ? XFS_DIR3_LEAF1_MAGIC
210 : XFS_DIR3_LEAFN_MAGIC;
211
212 if (leaf3->info.hdr.magic != cpu_to_be16(magic3))
Dave Chinner24df33b2013-04-12 07:30:21 +1000213 return false;
Dave Chinner24df33b2013-04-12 07:30:21 +1000214 if (!uuid_equal(&leaf3->info.uuid, &mp->m_sb.sb_uuid))
215 return false;
216 if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
217 return false;
218 } else {
Dave Chinner0f295a22013-09-03 10:06:58 +1000219 if (leaf->hdr.info.magic != cpu_to_be16(magic))
Dave Chinner24df33b2013-04-12 07:30:21 +1000220 return false;
221 }
Dave Chinner0f295a22013-09-03 10:06:58 +1000222
223 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
Dave Chinner41419562013-10-29 22:11:50 +1100224 return xfs_dir3_leaf_check_int(mp, NULL, &leafhdr, leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +1000225}
226
227static void
228__read_verify(
229 struct xfs_buf *bp,
230 __uint16_t magic)
231{
232 struct xfs_mount *mp = bp->b_target->bt_mount;
233
234 if ((xfs_sb_version_hascrc(&mp->m_sb) &&
235 !xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
236 XFS_DIR3_LEAF_CRC_OFF)) ||
237 !xfs_dir3_leaf_verify(bp, magic)) {
238 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
Dave Chinnere6f76672012-11-12 22:54:15 +1100239 xfs_buf_ioerror(bp, EFSCORRUPTED);
240 }
Dave Chinner612cfbf2012-11-14 17:52:32 +1100241}
Dave Chinnere6f76672012-11-12 22:54:15 +1100242
Dave Chinner612cfbf2012-11-14 17:52:32 +1100243static void
Dave Chinner24df33b2013-04-12 07:30:21 +1000244__write_verify(
245 struct xfs_buf *bp,
246 __uint16_t magic)
Dave Chinner612cfbf2012-11-14 17:52:32 +1100247{
Dave Chinner24df33b2013-04-12 07:30:21 +1000248 struct xfs_mount *mp = bp->b_target->bt_mount;
249 struct xfs_buf_log_item *bip = bp->b_fspriv;
250 struct xfs_dir3_leaf_hdr *hdr3 = bp->b_addr;
251
252 if (!xfs_dir3_leaf_verify(bp, magic)) {
253 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
254 xfs_buf_ioerror(bp, EFSCORRUPTED);
255 return;
256 }
257
258 if (!xfs_sb_version_hascrc(&mp->m_sb))
259 return;
260
261 if (bip)
262 hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
263
264 xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length), XFS_DIR3_LEAF_CRC_OFF);
Dave Chinner612cfbf2012-11-14 17:52:32 +1100265}
266
267static void
Dave Chinner24df33b2013-04-12 07:30:21 +1000268xfs_dir3_leaf1_read_verify(
Dave Chinner612cfbf2012-11-14 17:52:32 +1100269 struct xfs_buf *bp)
270{
Dave Chinner24df33b2013-04-12 07:30:21 +1000271 __read_verify(bp, XFS_DIR2_LEAF1_MAGIC);
Dave Chinner1813dd62012-11-14 17:54:40 +1100272}
273
Dave Chinner24df33b2013-04-12 07:30:21 +1000274static void
275xfs_dir3_leaf1_write_verify(
Dave Chinner1813dd62012-11-14 17:54:40 +1100276 struct xfs_buf *bp)
277{
Dave Chinner24df33b2013-04-12 07:30:21 +1000278 __write_verify(bp, XFS_DIR2_LEAF1_MAGIC);
Dave Chinnere6f76672012-11-12 22:54:15 +1100279}
280
Dave Chinner24df33b2013-04-12 07:30:21 +1000281static void
282xfs_dir3_leafn_read_verify(
Dave Chinner612cfbf2012-11-14 17:52:32 +1100283 struct xfs_buf *bp)
Dave Chinnere6f76672012-11-12 22:54:15 +1100284{
Dave Chinner24df33b2013-04-12 07:30:21 +1000285 __read_verify(bp, XFS_DIR2_LEAFN_MAGIC);
Dave Chinnere6f76672012-11-12 22:54:15 +1100286}
287
Dave Chinner24df33b2013-04-12 07:30:21 +1000288static void
289xfs_dir3_leafn_write_verify(
290 struct xfs_buf *bp)
291{
292 __write_verify(bp, XFS_DIR2_LEAFN_MAGIC);
293}
294
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100295const struct xfs_buf_ops xfs_dir3_leaf1_buf_ops = {
Dave Chinner24df33b2013-04-12 07:30:21 +1000296 .verify_read = xfs_dir3_leaf1_read_verify,
297 .verify_write = xfs_dir3_leaf1_write_verify,
Dave Chinner1813dd62012-11-14 17:54:40 +1100298};
299
Dave Chinner24df33b2013-04-12 07:30:21 +1000300const struct xfs_buf_ops xfs_dir3_leafn_buf_ops = {
301 .verify_read = xfs_dir3_leafn_read_verify,
302 .verify_write = xfs_dir3_leafn_write_verify,
Dave Chinner1813dd62012-11-14 17:54:40 +1100303};
Dave Chinnere6f76672012-11-12 22:54:15 +1100304
305static int
Dave Chinner24df33b2013-04-12 07:30:21 +1000306xfs_dir3_leaf_read(
Dave Chinnere6f76672012-11-12 22:54:15 +1100307 struct xfs_trans *tp,
308 struct xfs_inode *dp,
309 xfs_dablk_t fbno,
310 xfs_daddr_t mappedbno,
311 struct xfs_buf **bpp)
312{
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100313 int err;
314
315 err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
Dave Chinner24df33b2013-04-12 07:30:21 +1000316 XFS_DATA_FORK, &xfs_dir3_leaf1_buf_ops);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100317 if (!err && tp)
Dave Chinner61fe1352013-04-03 16:11:30 +1100318 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAF1_BUF);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100319 return err;
Dave Chinnere6f76672012-11-12 22:54:15 +1100320}
321
322int
Dave Chinner24df33b2013-04-12 07:30:21 +1000323xfs_dir3_leafn_read(
Dave Chinnere6f76672012-11-12 22:54:15 +1100324 struct xfs_trans *tp,
325 struct xfs_inode *dp,
326 xfs_dablk_t fbno,
327 xfs_daddr_t mappedbno,
328 struct xfs_buf **bpp)
329{
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100330 int err;
331
332 err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
Dave Chinner24df33b2013-04-12 07:30:21 +1000333 XFS_DATA_FORK, &xfs_dir3_leafn_buf_ops);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100334 if (!err && tp)
Dave Chinner61fe1352013-04-03 16:11:30 +1100335 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAFN_BUF);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100336 return err;
Dave Chinner24df33b2013-04-12 07:30:21 +1000337}
338
339/*
340 * Initialize a new leaf block, leaf1 or leafn magic accepted.
341 */
342static void
343xfs_dir3_leaf_init(
344 struct xfs_mount *mp,
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100345 struct xfs_trans *tp,
Dave Chinner24df33b2013-04-12 07:30:21 +1000346 struct xfs_buf *bp,
347 xfs_ino_t owner,
348 __uint16_t type)
349{
350 struct xfs_dir2_leaf *leaf = bp->b_addr;
351
352 ASSERT(type == XFS_DIR2_LEAF1_MAGIC || type == XFS_DIR2_LEAFN_MAGIC);
353
354 if (xfs_sb_version_hascrc(&mp->m_sb)) {
355 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
356
357 memset(leaf3, 0, sizeof(*leaf3));
358
359 leaf3->info.hdr.magic = (type == XFS_DIR2_LEAF1_MAGIC)
360 ? cpu_to_be16(XFS_DIR3_LEAF1_MAGIC)
361 : cpu_to_be16(XFS_DIR3_LEAFN_MAGIC);
362 leaf3->info.blkno = cpu_to_be64(bp->b_bn);
363 leaf3->info.owner = cpu_to_be64(owner);
364 uuid_copy(&leaf3->info.uuid, &mp->m_sb.sb_uuid);
365 } else {
366 memset(leaf, 0, sizeof(*leaf));
367 leaf->hdr.info.magic = cpu_to_be16(type);
368 }
369
370 /*
371 * If it's a leaf-format directory initialize the tail.
372 * Caller is responsible for initialising the bests table.
373 */
374 if (type == XFS_DIR2_LEAF1_MAGIC) {
375 struct xfs_dir2_leaf_tail *ltp;
376
377 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
378 ltp->bestcount = 0;
379 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
Dave Chinner61fe1352013-04-03 16:11:30 +1100380 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAF1_BUF);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100381 } else {
Dave Chinner24df33b2013-04-12 07:30:21 +1000382 bp->b_ops = &xfs_dir3_leafn_buf_ops;
Dave Chinner61fe1352013-04-03 16:11:30 +1100383 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100384 }
Dave Chinner24df33b2013-04-12 07:30:21 +1000385}
386
387int
388xfs_dir3_leaf_get_buf(
389 xfs_da_args_t *args,
390 xfs_dir2_db_t bno,
391 struct xfs_buf **bpp,
392 __uint16_t magic)
393{
394 struct xfs_inode *dp = args->dp;
395 struct xfs_trans *tp = args->trans;
396 struct xfs_mount *mp = dp->i_mount;
397 struct xfs_buf *bp;
398 int error;
399
400 ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
401 ASSERT(bno >= XFS_DIR2_LEAF_FIRSTDB(mp) &&
402 bno < XFS_DIR2_FREE_FIRSTDB(mp));
403
404 error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(mp, bno), -1, &bp,
405 XFS_DATA_FORK);
406 if (error)
407 return error;
408
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100409 xfs_dir3_leaf_init(mp, tp, bp, dp->i_ino, magic);
Dave Chinner41419562013-10-29 22:11:50 +1100410 xfs_dir3_leaf_log_header(tp, dp, bp);
Dave Chinner24df33b2013-04-12 07:30:21 +1000411 if (magic == XFS_DIR2_LEAF1_MAGIC)
412 xfs_dir3_leaf_log_tail(tp, bp);
413 *bpp = bp;
414 return 0;
Dave Chinnere6f76672012-11-12 22:54:15 +1100415}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700416
417/*
418 * Convert a block form directory to a leaf form directory.
419 */
420int /* error */
421xfs_dir2_block_to_leaf(
422 xfs_da_args_t *args, /* operation arguments */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000423 struct xfs_buf *dbp) /* input block's buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700424{
Nathan Scott68b3a102006-03-17 17:27:19 +1100425 __be16 *bestsp; /* leaf's bestsp entries */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426 xfs_dablk_t blkno; /* leaf block's bno */
Christoph Hellwig4f6ae1a2011-07-08 14:35:27 +0200427 xfs_dir2_data_hdr_t *hdr; /* block header */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700428 xfs_dir2_leaf_entry_t *blp; /* block's leaf entries */
429 xfs_dir2_block_tail_t *btp; /* block's tail */
430 xfs_inode_t *dp; /* incore directory inode */
431 int error; /* error return code */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000432 struct xfs_buf *lbp; /* leaf block's buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700433 xfs_dir2_db_t ldb; /* leaf block's bno */
434 xfs_dir2_leaf_t *leaf; /* leaf structure */
435 xfs_dir2_leaf_tail_t *ltp; /* leaf's tail */
436 xfs_mount_t *mp; /* filesystem mount point */
437 int needlog; /* need to log block header */
438 int needscan; /* need to rescan bestfree */
439 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner33363fe2013-04-03 16:11:22 +1100440 struct xfs_dir2_data_free *bf;
Dave Chinner24df33b2013-04-12 07:30:21 +1000441 struct xfs_dir2_leaf_entry *ents;
442 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000444 trace_xfs_dir2_block_to_leaf(args);
445
Linus Torvalds1da177e2005-04-16 15:20:36 -0700446 dp = args->dp;
447 mp = dp->i_mount;
448 tp = args->trans;
449 /*
450 * Add the leaf block to the inode.
451 * This interface will only put blocks in the leaf/node range.
452 * Since that's empty now, we'll get the root (block 0 in range).
453 */
454 if ((error = xfs_da_grow_inode(args, &blkno))) {
455 return error;
456 }
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000457 ldb = xfs_dir2_da_to_db(mp, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700458 ASSERT(ldb == XFS_DIR2_LEAF_FIRSTDB(mp));
459 /*
460 * Initialize the leaf block, get a buffer for it.
461 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000462 error = xfs_dir3_leaf_get_buf(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC);
463 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464 return error;
Dave Chinner24df33b2013-04-12 07:30:21 +1000465
Dave Chinner1d9025e2012-06-22 18:50:14 +1000466 leaf = lbp->b_addr;
467 hdr = dbp->b_addr;
Dave Chinner33363fe2013-04-03 16:11:22 +1100468 xfs_dir3_data_check(dp, dbp);
Christoph Hellwig4f6ae1a2011-07-08 14:35:27 +0200469 btp = xfs_dir2_block_tail_p(mp, hdr);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000470 blp = xfs_dir2_block_leaf_p(btp);
Dave Chinner2ca98772013-10-29 22:11:49 +1100471 bf = dp->d_ops->data_bestfree_p(hdr);
Dave Chinner41419562013-10-29 22:11:50 +1100472 ents = dp->d_ops->leaf_ents_p(leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +1000473
Linus Torvalds1da177e2005-04-16 15:20:36 -0700474 /*
475 * Set the counts in the leaf header.
476 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000477 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
478 leafhdr.count = be32_to_cpu(btp->count);
479 leafhdr.stale = be32_to_cpu(btp->stale);
480 xfs_dir3_leaf_hdr_to_disk(leaf, &leafhdr);
Dave Chinner41419562013-10-29 22:11:50 +1100481 xfs_dir3_leaf_log_header(tp, dp, lbp);
Dave Chinner24df33b2013-04-12 07:30:21 +1000482
Linus Torvalds1da177e2005-04-16 15:20:36 -0700483 /*
484 * Could compact these but I think we always do the conversion
485 * after squeezing out stale entries.
486 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000487 memcpy(ents, blp, be32_to_cpu(btp->count) * sizeof(xfs_dir2_leaf_entry_t));
Dave Chinner41419562013-10-29 22:11:50 +1100488 xfs_dir3_leaf_log_ents(tp, dp, lbp, 0, leafhdr.count - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700489 needscan = 0;
490 needlog = 1;
491 /*
492 * Make the space formerly occupied by the leaf entries and block
493 * tail be free.
494 */
Dave Chinner2ca98772013-10-29 22:11:49 +1100495 xfs_dir2_data_make_free(tp, dp, dbp,
Christoph Hellwig4f6ae1a2011-07-08 14:35:27 +0200496 (xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),
497 (xfs_dir2_data_aoff_t)((char *)hdr + mp->m_dirblksize -
Linus Torvalds1da177e2005-04-16 15:20:36 -0700498 (char *)blp),
499 &needlog, &needscan);
500 /*
501 * Fix up the block header, make it a data block.
502 */
Dave Chinner33363fe2013-04-03 16:11:22 +1100503 dbp->b_ops = &xfs_dir3_data_buf_ops;
Dave Chinner61fe1352013-04-03 16:11:30 +1100504 xfs_trans_buf_set_type(tp, dbp, XFS_BLFT_DIR_DATA_BUF);
Dave Chinner33363fe2013-04-03 16:11:22 +1100505 if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC))
506 hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
507 else
508 hdr->magic = cpu_to_be32(XFS_DIR3_DATA_MAGIC);
509
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510 if (needscan)
Dave Chinner9d23fc82013-10-29 22:11:48 +1100511 xfs_dir2_data_freescan(dp, hdr, &needlog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512 /*
513 * Set up leaf tail and bests table.
514 */
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000515 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100516 ltp->bestcount = cpu_to_be32(1);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000517 bestsp = xfs_dir2_leaf_bests_p(ltp);
Dave Chinnerf5f3d9b2013-04-03 16:11:20 +1100518 bestsp[0] = bf[0].length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700519 /*
520 * Log the data header and leaf bests table.
521 */
522 if (needlog)
Dave Chinner2ca98772013-10-29 22:11:49 +1100523 xfs_dir2_data_log_header(tp, dp, dbp);
Dave Chinner41419562013-10-29 22:11:50 +1100524 xfs_dir3_leaf_check(dp, lbp);
Dave Chinner33363fe2013-04-03 16:11:22 +1100525 xfs_dir3_data_check(dp, dbp);
Dave Chinner24df33b2013-04-12 07:30:21 +1000526 xfs_dir3_leaf_log_bests(tp, lbp, 0, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700527 return 0;
528}
529
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200530STATIC void
Dave Chinner24df33b2013-04-12 07:30:21 +1000531xfs_dir3_leaf_find_stale(
532 struct xfs_dir3_icleaf_hdr *leafhdr,
533 struct xfs_dir2_leaf_entry *ents,
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200534 int index,
535 int *lowstale,
536 int *highstale)
537{
538 /*
539 * Find the first stale entry before our index, if any.
540 */
541 for (*lowstale = index - 1; *lowstale >= 0; --*lowstale) {
Dave Chinner24df33b2013-04-12 07:30:21 +1000542 if (ents[*lowstale].address ==
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200543 cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
544 break;
545 }
546
547 /*
548 * Find the first stale entry at or after our index, if any.
549 * Stop if the result would require moving more entries than using
550 * lowstale.
551 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000552 for (*highstale = index; *highstale < leafhdr->count; ++*highstale) {
553 if (ents[*highstale].address ==
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200554 cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
555 break;
556 if (*lowstale >= 0 && index - *lowstale <= *highstale - index)
557 break;
558 }
559}
560
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200561struct xfs_dir2_leaf_entry *
Dave Chinner24df33b2013-04-12 07:30:21 +1000562xfs_dir3_leaf_find_entry(
563 struct xfs_dir3_icleaf_hdr *leafhdr,
564 struct xfs_dir2_leaf_entry *ents,
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200565 int index, /* leaf table position */
566 int compact, /* need to compact leaves */
567 int lowstale, /* index of prev stale leaf */
568 int highstale, /* index of next stale leaf */
569 int *lfloglow, /* low leaf logging index */
570 int *lfloghigh) /* high leaf logging index */
571{
Dave Chinner24df33b2013-04-12 07:30:21 +1000572 if (!leafhdr->stale) {
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200573 xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
574
575 /*
576 * Now we need to make room to insert the leaf entry.
577 *
578 * If there are no stale entries, just insert a hole at index.
579 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000580 lep = &ents[index];
581 if (index < leafhdr->count)
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200582 memmove(lep + 1, lep,
Dave Chinner24df33b2013-04-12 07:30:21 +1000583 (leafhdr->count - index) * sizeof(*lep));
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200584
585 /*
586 * Record low and high logging indices for the leaf.
587 */
588 *lfloglow = index;
Dave Chinner24df33b2013-04-12 07:30:21 +1000589 *lfloghigh = leafhdr->count++;
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200590 return lep;
591 }
592
593 /*
594 * There are stale entries.
595 *
596 * We will use one of them for the new entry. It's probably not at
597 * the right location, so we'll have to shift some up or down first.
598 *
599 * If we didn't compact before, we need to find the nearest stale
600 * entries before and after our insertion point.
601 */
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200602 if (compact == 0)
Dave Chinner24df33b2013-04-12 07:30:21 +1000603 xfs_dir3_leaf_find_stale(leafhdr, ents, index,
604 &lowstale, &highstale);
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200605
606 /*
607 * If the low one is better, use it.
608 */
609 if (lowstale >= 0 &&
Dave Chinner24df33b2013-04-12 07:30:21 +1000610 (highstale == leafhdr->count ||
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200611 index - lowstale - 1 < highstale - index)) {
612 ASSERT(index - lowstale - 1 >= 0);
Dave Chinner24df33b2013-04-12 07:30:21 +1000613 ASSERT(ents[lowstale].address ==
Christoph Hellwig69ef9212011-07-08 14:36:05 +0200614 cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200615
616 /*
617 * Copy entries up to cover the stale entry and make room
618 * for the new entry.
619 */
620 if (index - lowstale - 1 > 0) {
Dave Chinner24df33b2013-04-12 07:30:21 +1000621 memmove(&ents[lowstale], &ents[lowstale + 1],
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200622 (index - lowstale - 1) *
Dave Chinner24df33b2013-04-12 07:30:21 +1000623 sizeof(xfs_dir2_leaf_entry_t));
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200624 }
625 *lfloglow = MIN(lowstale, *lfloglow);
626 *lfloghigh = MAX(index - 1, *lfloghigh);
Dave Chinner24df33b2013-04-12 07:30:21 +1000627 leafhdr->stale--;
628 return &ents[index - 1];
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200629 }
630
631 /*
632 * The high one is better, so use that one.
633 */
634 ASSERT(highstale - index >= 0);
Dave Chinner24df33b2013-04-12 07:30:21 +1000635 ASSERT(ents[highstale].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200636
637 /*
638 * Copy entries down to cover the stale entry and make room for the
639 * new entry.
640 */
641 if (highstale - index > 0) {
Dave Chinner24df33b2013-04-12 07:30:21 +1000642 memmove(&ents[index + 1], &ents[index],
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200643 (highstale - index) * sizeof(xfs_dir2_leaf_entry_t));
644 }
645 *lfloglow = MIN(index, *lfloglow);
646 *lfloghigh = MAX(highstale, *lfloghigh);
Dave Chinner24df33b2013-04-12 07:30:21 +1000647 leafhdr->stale--;
648 return &ents[index];
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200649}
650
Linus Torvalds1da177e2005-04-16 15:20:36 -0700651/*
652 * Add an entry to a leaf form directory.
653 */
654int /* error */
655xfs_dir2_leaf_addname(
656 xfs_da_args_t *args) /* operation arguments */
657{
Nathan Scott68b3a102006-03-17 17:27:19 +1100658 __be16 *bestsp; /* freespace table in leaf */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700659 int compact; /* need to compact leaves */
Christoph Hellwigc2066e22011-07-08 14:35:38 +0200660 xfs_dir2_data_hdr_t *hdr; /* data block header */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000661 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662 xfs_dir2_data_entry_t *dep; /* data block entry */
663 xfs_inode_t *dp; /* incore directory inode */
664 xfs_dir2_data_unused_t *dup; /* data unused entry */
665 int error; /* error return value */
666 int grown; /* allocated new data block */
667 int highstale; /* index of next stale leaf */
668 int i; /* temporary, index */
669 int index; /* leaf table position */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000670 struct xfs_buf *lbp; /* leaf's buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700671 xfs_dir2_leaf_t *leaf; /* leaf structure */
672 int length; /* length of new entry */
673 xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
674 int lfloglow; /* low leaf logging index */
675 int lfloghigh; /* high leaf logging index */
676 int lowstale; /* index of prev stale leaf */
677 xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
678 xfs_mount_t *mp; /* filesystem mount point */
679 int needbytes; /* leaf block bytes needed */
680 int needlog; /* need to log data header */
681 int needscan; /* need to rescan data free */
Nathan Scott3d693c62006-03-17 17:28:27 +1100682 __be16 *tagp; /* end of data entry */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700683 xfs_trans_t *tp; /* transaction pointer */
684 xfs_dir2_db_t use_block; /* data block number */
Dave Chinner33363fe2013-04-03 16:11:22 +1100685 struct xfs_dir2_data_free *bf; /* bestfree table */
Dave Chinner24df33b2013-04-12 07:30:21 +1000686 struct xfs_dir2_leaf_entry *ents;
687 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700688
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000689 trace_xfs_dir2_leaf_addname(args);
690
Linus Torvalds1da177e2005-04-16 15:20:36 -0700691 dp = args->dp;
692 tp = args->trans;
693 mp = dp->i_mount;
Dave Chinnere6f76672012-11-12 22:54:15 +1100694
Dave Chinner24df33b2013-04-12 07:30:21 +1000695 error = xfs_dir3_leaf_read(tp, dp, mp->m_dirleafblk, -1, &lbp);
Dave Chinner4bb20a82012-11-12 22:54:10 +1100696 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700697 return error;
Dave Chinnere6f76672012-11-12 22:54:15 +1100698
Linus Torvalds1da177e2005-04-16 15:20:36 -0700699 /*
700 * Look up the entry by hash value and name.
701 * We know it's not there, our caller has already done a lookup.
702 * So the index is of the entry to insert in front of.
703 * But if there are dup hash values the index is of the first of those.
704 */
705 index = xfs_dir2_leaf_search_hash(args, lbp);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000706 leaf = lbp->b_addr;
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000707 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Dave Chinner41419562013-10-29 22:11:50 +1100708 ents = dp->d_ops->leaf_ents_p(leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +1000709 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000710 bestsp = xfs_dir2_leaf_bests_p(ltp);
Dave Chinner9d23fc82013-10-29 22:11:48 +1100711 length = dp->d_ops->data_entsize(args->namelen);
Dave Chinner24df33b2013-04-12 07:30:21 +1000712
Linus Torvalds1da177e2005-04-16 15:20:36 -0700713 /*
714 * See if there are any entries with the same hash value
715 * and space in their block for the new entry.
716 * This is good because it puts multiple same-hash value entries
717 * in a data block, improving the lookup of those entries.
718 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000719 for (use_block = -1, lep = &ents[index];
720 index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700721 index++, lep++) {
Nathan Scott3c1f9c12006-03-17 17:28:18 +1100722 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700723 continue;
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000724 i = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100725 ASSERT(i < be32_to_cpu(ltp->bestcount));
Christoph Hellwig69ef9212011-07-08 14:36:05 +0200726 ASSERT(bestsp[i] != cpu_to_be16(NULLDATAOFF));
Nathan Scott68b3a102006-03-17 17:27:19 +1100727 if (be16_to_cpu(bestsp[i]) >= length) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700728 use_block = i;
729 break;
730 }
731 }
732 /*
733 * Didn't find a block yet, linear search all the data blocks.
734 */
735 if (use_block == -1) {
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100736 for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700737 /*
738 * Remember a block we see that's missing.
739 */
Christoph Hellwig69ef9212011-07-08 14:36:05 +0200740 if (bestsp[i] == cpu_to_be16(NULLDATAOFF) &&
741 use_block == -1)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700742 use_block = i;
Nathan Scott68b3a102006-03-17 17:27:19 +1100743 else if (be16_to_cpu(bestsp[i]) >= length) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700744 use_block = i;
745 break;
746 }
747 }
748 }
749 /*
750 * How many bytes do we need in the leaf block?
751 */
Christoph Hellwig22823962011-07-08 14:35:53 +0200752 needbytes = 0;
Dave Chinner24df33b2013-04-12 07:30:21 +1000753 if (!leafhdr.stale)
Christoph Hellwig22823962011-07-08 14:35:53 +0200754 needbytes += sizeof(xfs_dir2_leaf_entry_t);
755 if (use_block == -1)
756 needbytes += sizeof(xfs_dir2_data_off_t);
757
Linus Torvalds1da177e2005-04-16 15:20:36 -0700758 /*
759 * Now kill use_block if it refers to a missing block, so we
760 * can use it as an indication of allocation needed.
761 */
Christoph Hellwig69ef9212011-07-08 14:36:05 +0200762 if (use_block != -1 && bestsp[use_block] == cpu_to_be16(NULLDATAOFF))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700763 use_block = -1;
764 /*
765 * If we don't have enough free bytes but we can make enough
766 * by compacting out stale entries, we'll do that.
767 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000768 if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes &&
769 leafhdr.stale > 1)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700770 compact = 1;
Dave Chinner24df33b2013-04-12 07:30:21 +1000771
Linus Torvalds1da177e2005-04-16 15:20:36 -0700772 /*
773 * Otherwise if we don't have enough free bytes we need to
774 * convert to node form.
775 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000776 else if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700777 /*
778 * Just checking or no space reservation, give up.
779 */
Barry Naujok6a178102008-05-21 16:42:05 +1000780 if ((args->op_flags & XFS_DA_OP_JUSTCHECK) ||
781 args->total == 0) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000782 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700783 return XFS_ERROR(ENOSPC);
784 }
785 /*
786 * Convert to node form.
787 */
788 error = xfs_dir2_leaf_to_node(args, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700789 if (error)
790 return error;
791 /*
792 * Then add the new entry.
793 */
794 return xfs_dir2_node_addname(args);
795 }
796 /*
797 * Otherwise it will fit without compaction.
798 */
799 else
800 compact = 0;
801 /*
802 * If just checking, then it will fit unless we needed to allocate
803 * a new data block.
804 */
Barry Naujok6a178102008-05-21 16:42:05 +1000805 if (args->op_flags & XFS_DA_OP_JUSTCHECK) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000806 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700807 return use_block == -1 ? XFS_ERROR(ENOSPC) : 0;
808 }
809 /*
810 * If no allocations are allowed, return now before we've
811 * changed anything.
812 */
813 if (args->total == 0 && use_block == -1) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000814 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700815 return XFS_ERROR(ENOSPC);
816 }
817 /*
818 * Need to compact the leaf entries, removing stale ones.
819 * Leave one stale entry behind - the one closest to our
820 * insertion index - and we'll shift that one to our insertion
821 * point later.
822 */
823 if (compact) {
Dave Chinner24df33b2013-04-12 07:30:21 +1000824 xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale,
825 &highstale, &lfloglow, &lfloghigh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700826 }
827 /*
828 * There are stale entries, so we'll need log-low and log-high
829 * impossibly bad values later.
830 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000831 else if (leafhdr.stale) {
832 lfloglow = leafhdr.count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700833 lfloghigh = -1;
834 }
835 /*
836 * If there was no data block space found, we need to allocate
837 * a new one.
838 */
839 if (use_block == -1) {
840 /*
841 * Add the new data block.
842 */
843 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
844 &use_block))) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000845 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846 return error;
847 }
848 /*
849 * Initialize the block.
850 */
Dave Chinnerf5f3d9b2013-04-03 16:11:20 +1100851 if ((error = xfs_dir3_data_init(args, use_block, &dbp))) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000852 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853 return error;
854 }
855 /*
856 * If we're adding a new data block on the end we need to
857 * extend the bests table. Copy it up one entry.
858 */
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100859 if (use_block >= be32_to_cpu(ltp->bestcount)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700860 bestsp--;
861 memmove(&bestsp[0], &bestsp[1],
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100862 be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0]));
Marcin Slusarz413d57c2008-02-13 15:03:29 -0800863 be32_add_cpu(&ltp->bestcount, 1);
Dave Chinner24df33b2013-04-12 07:30:21 +1000864 xfs_dir3_leaf_log_tail(tp, lbp);
865 xfs_dir3_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700866 }
867 /*
868 * If we're filling in a previously empty block just log it.
869 */
870 else
Dave Chinner24df33b2013-04-12 07:30:21 +1000871 xfs_dir3_leaf_log_bests(tp, lbp, use_block, use_block);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000872 hdr = dbp->b_addr;
Dave Chinner2ca98772013-10-29 22:11:49 +1100873 bf = dp->d_ops->data_bestfree_p(hdr);
Dave Chinner33363fe2013-04-03 16:11:22 +1100874 bestsp[use_block] = bf[0].length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875 grown = 1;
Dave Chinnere4813572012-11-12 22:54:14 +1100876 } else {
877 /*
878 * Already had space in some data block.
879 * Just read that one in.
880 */
Dave Chinner33363fe2013-04-03 16:11:22 +1100881 error = xfs_dir3_data_read(tp, dp,
Dave Chinnere4813572012-11-12 22:54:14 +1100882 xfs_dir2_db_to_da(mp, use_block),
883 -1, &dbp);
Dave Chinner4bb20a82012-11-12 22:54:10 +1100884 if (error) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000885 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700886 return error;
887 }
Dave Chinner1d9025e2012-06-22 18:50:14 +1000888 hdr = dbp->b_addr;
Dave Chinner2ca98772013-10-29 22:11:49 +1100889 bf = dp->d_ops->data_bestfree_p(hdr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700890 grown = 0;
891 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892 /*
893 * Point to the biggest freespace in our data block.
894 */
895 dup = (xfs_dir2_data_unused_t *)
Dave Chinner33363fe2013-04-03 16:11:22 +1100896 ((char *)hdr + be16_to_cpu(bf[0].offset));
Nathan Scottad354eb2006-03-17 17:27:37 +1100897 ASSERT(be16_to_cpu(dup->length) >= length);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700898 needscan = needlog = 0;
899 /*
900 * Mark the initial part of our freespace in use for the new entry.
901 */
Dave Chinner2ca98772013-10-29 22:11:49 +1100902 xfs_dir2_data_use_free(tp, dp, dbp, dup,
Christoph Hellwigc2066e22011-07-08 14:35:38 +0200903 (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr), length,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700904 &needlog, &needscan);
905 /*
906 * Initialize our new entry (at last).
907 */
908 dep = (xfs_dir2_data_entry_t *)dup;
Christoph Hellwigff9901c2006-06-09 14:48:37 +1000909 dep->inumber = cpu_to_be64(args->inumber);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700910 dep->namelen = args->namelen;
911 memcpy(dep->name, args->name, dep->namelen);
Dave Chinner9d23fc82013-10-29 22:11:48 +1100912 dp->d_ops->data_put_ftype(dep, args->filetype);
913 tagp = dp->d_ops->data_entry_tag_p(dep);
Christoph Hellwigc2066e22011-07-08 14:35:38 +0200914 *tagp = cpu_to_be16((char *)dep - (char *)hdr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700915 /*
916 * Need to scan fix up the bestfree table.
917 */
918 if (needscan)
Dave Chinner9d23fc82013-10-29 22:11:48 +1100919 xfs_dir2_data_freescan(dp, hdr, &needlog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700920 /*
921 * Need to log the data block's header.
922 */
923 if (needlog)
Dave Chinner2ca98772013-10-29 22:11:49 +1100924 xfs_dir2_data_log_header(tp, dp, dbp);
Dave Chinner9d23fc82013-10-29 22:11:48 +1100925 xfs_dir2_data_log_entry(tp, dp, dbp, dep);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700926 /*
927 * If the bests table needs to be changed, do it.
928 * Log the change unless we've already done that.
929 */
Dave Chinner33363fe2013-04-03 16:11:22 +1100930 if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(bf[0].length)) {
931 bestsp[use_block] = bf[0].length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700932 if (!grown)
Dave Chinner24df33b2013-04-12 07:30:21 +1000933 xfs_dir3_leaf_log_bests(tp, lbp, use_block, use_block);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700934 }
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200935
Dave Chinner24df33b2013-04-12 07:30:21 +1000936 lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale,
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200937 highstale, &lfloglow, &lfloghigh);
938
Linus Torvalds1da177e2005-04-16 15:20:36 -0700939 /*
940 * Fill in the new leaf entry.
941 */
Nathan Scott3c1f9c12006-03-17 17:28:18 +1100942 lep->hashval = cpu_to_be32(args->hashval);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000943 lep->address = cpu_to_be32(xfs_dir2_db_off_to_dataptr(mp, use_block,
Nathan Scott3d693c62006-03-17 17:28:27 +1100944 be16_to_cpu(*tagp)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700945 /*
946 * Log the leaf fields and give up the buffers.
947 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000948 xfs_dir3_leaf_hdr_to_disk(leaf, &leafhdr);
Dave Chinner41419562013-10-29 22:11:50 +1100949 xfs_dir3_leaf_log_header(tp, dp, lbp);
950 xfs_dir3_leaf_log_ents(tp, dp, lbp, lfloglow, lfloghigh);
951 xfs_dir3_leaf_check(dp, lbp);
Dave Chinner33363fe2013-04-03 16:11:22 +1100952 xfs_dir3_data_check(dp, dbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700953 return 0;
954}
955
Linus Torvalds1da177e2005-04-16 15:20:36 -0700956/*
957 * Compact out any stale entries in the leaf.
958 * Log the header and changed leaf entries, if any.
959 */
960void
Dave Chinner24df33b2013-04-12 07:30:21 +1000961xfs_dir3_leaf_compact(
Linus Torvalds1da177e2005-04-16 15:20:36 -0700962 xfs_da_args_t *args, /* operation arguments */
Dave Chinner24df33b2013-04-12 07:30:21 +1000963 struct xfs_dir3_icleaf_hdr *leafhdr,
Dave Chinner1d9025e2012-06-22 18:50:14 +1000964 struct xfs_buf *bp) /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700965{
966 int from; /* source leaf index */
967 xfs_dir2_leaf_t *leaf; /* leaf structure */
968 int loglow; /* first leaf entry to log */
969 int to; /* target leaf index */
Dave Chinner24df33b2013-04-12 07:30:21 +1000970 struct xfs_dir2_leaf_entry *ents;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700971
Dave Chinner1d9025e2012-06-22 18:50:14 +1000972 leaf = bp->b_addr;
Dave Chinner24df33b2013-04-12 07:30:21 +1000973 if (!leafhdr->stale)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700974 return;
Dave Chinner24df33b2013-04-12 07:30:21 +1000975
Linus Torvalds1da177e2005-04-16 15:20:36 -0700976 /*
977 * Compress out the stale entries in place.
978 */
Dave Chinner41419562013-10-29 22:11:50 +1100979 ents = args->dp->d_ops->leaf_ents_p(leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +1000980 for (from = to = 0, loglow = -1; from < leafhdr->count; from++) {
981 if (ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700982 continue;
983 /*
984 * Only actually copy the entries that are different.
985 */
986 if (from > to) {
987 if (loglow == -1)
988 loglow = to;
Dave Chinner24df33b2013-04-12 07:30:21 +1000989 ents[to] = ents[from];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700990 }
991 to++;
992 }
993 /*
994 * Update and log the header, log the leaf entries.
995 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000996 ASSERT(leafhdr->stale == from - to);
997 leafhdr->count -= leafhdr->stale;
998 leafhdr->stale = 0;
999
1000 xfs_dir3_leaf_hdr_to_disk(leaf, leafhdr);
Dave Chinner41419562013-10-29 22:11:50 +11001001 xfs_dir3_leaf_log_header(args->trans, args->dp, bp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001002 if (loglow != -1)
Dave Chinner41419562013-10-29 22:11:50 +11001003 xfs_dir3_leaf_log_ents(args->trans, args->dp, bp,
1004 loglow, to - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001005}
1006
1007/*
1008 * Compact the leaf entries, removing stale ones.
1009 * Leave one stale entry behind - the one closest to our
1010 * insertion index - and the caller will shift that one to our insertion
1011 * point later.
1012 * Return new insertion index, where the remaining stale entry is,
1013 * and leaf logging indices.
1014 */
1015void
Dave Chinner24df33b2013-04-12 07:30:21 +10001016xfs_dir3_leaf_compact_x1(
1017 struct xfs_dir3_icleaf_hdr *leafhdr,
1018 struct xfs_dir2_leaf_entry *ents,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001019 int *indexp, /* insertion index */
1020 int *lowstalep, /* out: stale entry before us */
1021 int *highstalep, /* out: stale entry after us */
1022 int *lowlogp, /* out: low log index */
1023 int *highlogp) /* out: high log index */
1024{
1025 int from; /* source copy index */
1026 int highstale; /* stale entry at/after index */
1027 int index; /* insertion index */
1028 int keepstale; /* source index of kept stale */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001029 int lowstale; /* stale entry before index */
1030 int newindex=0; /* new insertion index */
1031 int to; /* destination copy index */
1032
Dave Chinner24df33b2013-04-12 07:30:21 +10001033 ASSERT(leafhdr->stale > 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001034 index = *indexp;
Christoph Hellwiga230a1d2011-07-13 13:43:48 +02001035
Dave Chinner24df33b2013-04-12 07:30:21 +10001036 xfs_dir3_leaf_find_stale(leafhdr, ents, index, &lowstale, &highstale);
Christoph Hellwiga230a1d2011-07-13 13:43:48 +02001037
Linus Torvalds1da177e2005-04-16 15:20:36 -07001038 /*
1039 * Pick the better of lowstale and highstale.
1040 */
1041 if (lowstale >= 0 &&
Dave Chinner24df33b2013-04-12 07:30:21 +10001042 (highstale == leafhdr->count ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001043 index - lowstale <= highstale - index))
1044 keepstale = lowstale;
1045 else
1046 keepstale = highstale;
1047 /*
1048 * Copy the entries in place, removing all the stale entries
1049 * except keepstale.
1050 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001051 for (from = to = 0; from < leafhdr->count; from++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001052 /*
1053 * Notice the new value of index.
1054 */
1055 if (index == from)
1056 newindex = to;
1057 if (from != keepstale &&
Dave Chinner24df33b2013-04-12 07:30:21 +10001058 ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001059 if (from == to)
1060 *lowlogp = to;
1061 continue;
1062 }
1063 /*
1064 * Record the new keepstale value for the insertion.
1065 */
1066 if (from == keepstale)
1067 lowstale = highstale = to;
1068 /*
1069 * Copy only the entries that have moved.
1070 */
1071 if (from > to)
Dave Chinner24df33b2013-04-12 07:30:21 +10001072 ents[to] = ents[from];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001073 to++;
1074 }
1075 ASSERT(from > to);
1076 /*
1077 * If the insertion point was past the last entry,
1078 * set the new insertion point accordingly.
1079 */
1080 if (index == from)
1081 newindex = to;
1082 *indexp = newindex;
1083 /*
1084 * Adjust the leaf header values.
1085 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001086 leafhdr->count -= from - to;
1087 leafhdr->stale = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001088 /*
1089 * Remember the low/high stale value only in the "right"
1090 * direction.
1091 */
1092 if (lowstale >= newindex)
1093 lowstale = -1;
1094 else
Dave Chinner24df33b2013-04-12 07:30:21 +10001095 highstale = leafhdr->count;
1096 *highlogp = leafhdr->count - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001097 *lowstalep = lowstale;
1098 *highstalep = highstale;
1099}
1100
Linus Torvalds1da177e2005-04-16 15:20:36 -07001101/*
1102 * Log the bests entries indicated from a leaf1 block.
1103 */
Christoph Hellwigba0f32d2005-06-21 15:36:52 +10001104static void
Dave Chinner24df33b2013-04-12 07:30:21 +10001105xfs_dir3_leaf_log_bests(
Linus Torvalds1da177e2005-04-16 15:20:36 -07001106 xfs_trans_t *tp, /* transaction pointer */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001107 struct xfs_buf *bp, /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001108 int first, /* first entry to log */
1109 int last) /* last entry to log */
1110{
Nathan Scott68b3a102006-03-17 17:27:19 +11001111 __be16 *firstb; /* pointer to first entry */
1112 __be16 *lastb; /* pointer to last entry */
Dave Chinner24df33b2013-04-12 07:30:21 +10001113 struct xfs_dir2_leaf *leaf = bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001114 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1115
Dave Chinner24df33b2013-04-12 07:30:21 +10001116 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1117 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC));
1118
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001119 ltp = xfs_dir2_leaf_tail_p(tp->t_mountp, leaf);
1120 firstb = xfs_dir2_leaf_bests_p(ltp) + first;
1121 lastb = xfs_dir2_leaf_bests_p(ltp) + last;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001122 xfs_trans_log_buf(tp, bp, (uint)((char *)firstb - (char *)leaf),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001123 (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
1124}
1125
1126/*
1127 * Log the leaf entries indicated from a leaf1 or leafn block.
1128 */
1129void
Dave Chinner24df33b2013-04-12 07:30:21 +10001130xfs_dir3_leaf_log_ents(
Dave Chinner41419562013-10-29 22:11:50 +11001131 struct xfs_trans *tp,
1132 struct xfs_inode *dp,
1133 struct xfs_buf *bp,
1134 int first,
1135 int last)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001136{
1137 xfs_dir2_leaf_entry_t *firstlep; /* pointer to first entry */
1138 xfs_dir2_leaf_entry_t *lastlep; /* pointer to last entry */
Dave Chinner24df33b2013-04-12 07:30:21 +10001139 struct xfs_dir2_leaf *leaf = bp->b_addr;
1140 struct xfs_dir2_leaf_entry *ents;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001141
Christoph Hellwig69ef9212011-07-08 14:36:05 +02001142 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
Dave Chinner24df33b2013-04-12 07:30:21 +10001143 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1144 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1145 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1146
Dave Chinner41419562013-10-29 22:11:50 +11001147 ents = dp->d_ops->leaf_ents_p(leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +10001148 firstlep = &ents[first];
1149 lastlep = &ents[last];
Dave Chinner1d9025e2012-06-22 18:50:14 +10001150 xfs_trans_log_buf(tp, bp, (uint)((char *)firstlep - (char *)leaf),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001151 (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
1152}
1153
1154/*
1155 * Log the header of the leaf1 or leafn block.
1156 */
1157void
Dave Chinner24df33b2013-04-12 07:30:21 +10001158xfs_dir3_leaf_log_header(
Dave Chinner1d9025e2012-06-22 18:50:14 +10001159 struct xfs_trans *tp,
Dave Chinner41419562013-10-29 22:11:50 +11001160 struct xfs_inode *dp,
Dave Chinner1d9025e2012-06-22 18:50:14 +10001161 struct xfs_buf *bp)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001162{
Dave Chinner24df33b2013-04-12 07:30:21 +10001163 struct xfs_dir2_leaf *leaf = bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001164
Christoph Hellwig69ef9212011-07-08 14:36:05 +02001165 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
Dave Chinner24df33b2013-04-12 07:30:21 +10001166 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1167 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1168 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1169
Dave Chinner1d9025e2012-06-22 18:50:14 +10001170 xfs_trans_log_buf(tp, bp, (uint)((char *)&leaf->hdr - (char *)leaf),
Dave Chinner41419562013-10-29 22:11:50 +11001171 dp->d_ops->leaf_hdr_size() - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001172}
1173
1174/*
1175 * Log the tail of the leaf1 block.
1176 */
Christoph Hellwigba0f32d2005-06-21 15:36:52 +10001177STATIC void
Dave Chinner24df33b2013-04-12 07:30:21 +10001178xfs_dir3_leaf_log_tail(
Dave Chinner1d9025e2012-06-22 18:50:14 +10001179 struct xfs_trans *tp,
1180 struct xfs_buf *bp)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001181{
Dave Chinner24df33b2013-04-12 07:30:21 +10001182 struct xfs_dir2_leaf *leaf = bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001183 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
Dave Chinner24df33b2013-04-12 07:30:21 +10001184 struct xfs_mount *mp = tp->t_mountp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001185
Dave Chinner24df33b2013-04-12 07:30:21 +10001186 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1187 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1188 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1189 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1190
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001191 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001192 xfs_trans_log_buf(tp, bp, (uint)((char *)ltp - (char *)leaf),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001193 (uint)(mp->m_dirblksize - 1));
1194}
1195
1196/*
1197 * Look up the entry referred to by args in the leaf format directory.
1198 * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
1199 * is also used by the node-format code.
1200 */
1201int
1202xfs_dir2_leaf_lookup(
1203 xfs_da_args_t *args) /* operation arguments */
1204{
Dave Chinner1d9025e2012-06-22 18:50:14 +10001205 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001206 xfs_dir2_data_entry_t *dep; /* data block entry */
1207 xfs_inode_t *dp; /* incore directory inode */
1208 int error; /* error return code */
1209 int index; /* found entry index */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001210 struct xfs_buf *lbp; /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001211 xfs_dir2_leaf_t *leaf; /* leaf structure */
1212 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1213 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner24df33b2013-04-12 07:30:21 +10001214 struct xfs_dir2_leaf_entry *ents;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001215
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001216 trace_xfs_dir2_leaf_lookup(args);
1217
Linus Torvalds1da177e2005-04-16 15:20:36 -07001218 /*
1219 * Look up name in the leaf block, returning both buffers and index.
1220 */
1221 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1222 return error;
1223 }
1224 tp = args->trans;
1225 dp = args->dp;
Dave Chinner41419562013-10-29 22:11:50 +11001226 xfs_dir3_leaf_check(dp, lbp);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001227 leaf = lbp->b_addr;
Dave Chinner41419562013-10-29 22:11:50 +11001228 ents = dp->d_ops->leaf_ents_p(leaf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001229 /*
1230 * Get to the leaf entry and contained data entry address.
1231 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001232 lep = &ents[index];
1233
Linus Torvalds1da177e2005-04-16 15:20:36 -07001234 /*
1235 * Point to the data entry.
1236 */
1237 dep = (xfs_dir2_data_entry_t *)
Dave Chinner1d9025e2012-06-22 18:50:14 +10001238 ((char *)dbp->b_addr +
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001239 xfs_dir2_dataptr_to_off(dp->i_mount, be32_to_cpu(lep->address)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001240 /*
Barry Naujok384f3ce2008-05-21 16:58:22 +10001241 * Return the found inode number & CI name if appropriate
Linus Torvalds1da177e2005-04-16 15:20:36 -07001242 */
Christoph Hellwigff9901c2006-06-09 14:48:37 +10001243 args->inumber = be64_to_cpu(dep->inumber);
Dave Chinner9d23fc82013-10-29 22:11:48 +11001244 args->filetype = dp->d_ops->data_get_ftype(dep);
Barry Naujok384f3ce2008-05-21 16:58:22 +10001245 error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001246 xfs_trans_brelse(tp, dbp);
1247 xfs_trans_brelse(tp, lbp);
Barry Naujok384f3ce2008-05-21 16:58:22 +10001248 return XFS_ERROR(error);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001249}
1250
1251/*
1252 * Look up name/hash in the leaf block.
1253 * Fill in indexp with the found index, and dbpp with the data buffer.
1254 * If not found dbpp will be NULL, and ENOENT comes back.
1255 * lbpp will always be filled in with the leaf buffer unless there's an error.
1256 */
1257static int /* error */
1258xfs_dir2_leaf_lookup_int(
1259 xfs_da_args_t *args, /* operation arguments */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001260 struct xfs_buf **lbpp, /* out: leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001261 int *indexp, /* out: index in leaf block */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001262 struct xfs_buf **dbpp) /* out: data buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001263{
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001264 xfs_dir2_db_t curdb = -1; /* current data block number */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001265 struct xfs_buf *dbp = NULL; /* data buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001266 xfs_dir2_data_entry_t *dep; /* data entry */
1267 xfs_inode_t *dp; /* incore directory inode */
1268 int error; /* error return code */
1269 int index; /* index in leaf block */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001270 struct xfs_buf *lbp; /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001271 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1272 xfs_dir2_leaf_t *leaf; /* leaf structure */
1273 xfs_mount_t *mp; /* filesystem mount point */
1274 xfs_dir2_db_t newdb; /* new data block number */
1275 xfs_trans_t *tp; /* transaction pointer */
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001276 xfs_dir2_db_t cidb = -1; /* case match data block no. */
Barry Naujok5163f952008-05-21 16:41:01 +10001277 enum xfs_dacmp cmp; /* name compare result */
Dave Chinner24df33b2013-04-12 07:30:21 +10001278 struct xfs_dir2_leaf_entry *ents;
1279 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001280
1281 dp = args->dp;
1282 tp = args->trans;
1283 mp = dp->i_mount;
Dave Chinnere6f76672012-11-12 22:54:15 +11001284
Dave Chinner24df33b2013-04-12 07:30:21 +10001285 error = xfs_dir3_leaf_read(tp, dp, mp->m_dirleafblk, -1, &lbp);
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001286 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001287 return error;
Dave Chinnere6f76672012-11-12 22:54:15 +11001288
Linus Torvalds1da177e2005-04-16 15:20:36 -07001289 *lbpp = lbp;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001290 leaf = lbp->b_addr;
Dave Chinner41419562013-10-29 22:11:50 +11001291 xfs_dir3_leaf_check(dp, lbp);
1292 ents = dp->d_ops->leaf_ents_p(leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +10001293 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
1294
Linus Torvalds1da177e2005-04-16 15:20:36 -07001295 /*
1296 * Look for the first leaf entry with our hash value.
1297 */
1298 index = xfs_dir2_leaf_search_hash(args, lbp);
1299 /*
1300 * Loop over all the entries with the right hash value
1301 * looking to match the name.
1302 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001303 for (lep = &ents[index];
1304 index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
1305 lep++, index++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001306 /*
1307 * Skip over stale leaf entries.
1308 */
Nathan Scott3c1f9c12006-03-17 17:28:18 +11001309 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001310 continue;
1311 /*
1312 * Get the new data block number.
1313 */
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001314 newdb = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001315 /*
1316 * If it's not the same as the old data block number,
1317 * need to pitch the old one and read the new one.
1318 */
1319 if (newdb != curdb) {
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001320 if (dbp)
Dave Chinner1d9025e2012-06-22 18:50:14 +10001321 xfs_trans_brelse(tp, dbp);
Dave Chinner33363fe2013-04-03 16:11:22 +11001322 error = xfs_dir3_data_read(tp, dp,
Dave Chinnere4813572012-11-12 22:54:14 +11001323 xfs_dir2_db_to_da(mp, newdb),
1324 -1, &dbp);
Barry Naujok5163f952008-05-21 16:41:01 +10001325 if (error) {
Dave Chinner1d9025e2012-06-22 18:50:14 +10001326 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001327 return error;
1328 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001329 curdb = newdb;
1330 }
1331 /*
1332 * Point to the data entry.
1333 */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001334 dep = (xfs_dir2_data_entry_t *)((char *)dbp->b_addr +
Barry Naujok5163f952008-05-21 16:41:01 +10001335 xfs_dir2_dataptr_to_off(mp, be32_to_cpu(lep->address)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001336 /*
Barry Naujok5163f952008-05-21 16:41:01 +10001337 * Compare name and if it's an exact match, return the index
1338 * and buffer. If it's the first case-insensitive match, store
1339 * the index and buffer and continue looking for an exact match.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001340 */
Barry Naujok5163f952008-05-21 16:41:01 +10001341 cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
1342 if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
1343 args->cmpresult = cmp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001344 *indexp = index;
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001345 /* case exact match: return the current buffer. */
Barry Naujok5163f952008-05-21 16:41:01 +10001346 if (cmp == XFS_CMP_EXACT) {
Barry Naujok5163f952008-05-21 16:41:01 +10001347 *dbpp = dbp;
1348 return 0;
1349 }
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001350 cidb = curdb;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001351 }
1352 }
Barry Naujok6a178102008-05-21 16:42:05 +10001353 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
Barry Naujok5163f952008-05-21 16:41:01 +10001354 /*
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001355 * Here, we can only be doing a lookup (not a rename or remove).
1356 * If a case-insensitive match was found earlier, re-read the
1357 * appropriate data block if required and return it.
Barry Naujok5163f952008-05-21 16:41:01 +10001358 */
1359 if (args->cmpresult == XFS_CMP_CASE) {
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001360 ASSERT(cidb != -1);
1361 if (cidb != curdb) {
Dave Chinner1d9025e2012-06-22 18:50:14 +10001362 xfs_trans_brelse(tp, dbp);
Dave Chinner33363fe2013-04-03 16:11:22 +11001363 error = xfs_dir3_data_read(tp, dp,
Dave Chinnere4813572012-11-12 22:54:14 +11001364 xfs_dir2_db_to_da(mp, cidb),
1365 -1, &dbp);
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001366 if (error) {
Dave Chinner1d9025e2012-06-22 18:50:14 +10001367 xfs_trans_brelse(tp, lbp);
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001368 return error;
1369 }
1370 }
1371 *dbpp = dbp;
Barry Naujok5163f952008-05-21 16:41:01 +10001372 return 0;
1373 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001374 /*
1375 * No match found, return ENOENT.
1376 */
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001377 ASSERT(cidb == -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001378 if (dbp)
Dave Chinner1d9025e2012-06-22 18:50:14 +10001379 xfs_trans_brelse(tp, dbp);
1380 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001381 return XFS_ERROR(ENOENT);
1382}
1383
1384/*
1385 * Remove an entry from a leaf format directory.
1386 */
1387int /* error */
1388xfs_dir2_leaf_removename(
1389 xfs_da_args_t *args) /* operation arguments */
1390{
Nathan Scott68b3a102006-03-17 17:27:19 +11001391 __be16 *bestsp; /* leaf block best freespace */
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001392 xfs_dir2_data_hdr_t *hdr; /* data block header */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001393 xfs_dir2_db_t db; /* data block number */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001394 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001395 xfs_dir2_data_entry_t *dep; /* data entry structure */
1396 xfs_inode_t *dp; /* incore directory inode */
1397 int error; /* error return code */
1398 xfs_dir2_db_t i; /* temporary data block # */
1399 int index; /* index into leaf entries */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001400 struct xfs_buf *lbp; /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 xfs_dir2_leaf_t *leaf; /* leaf structure */
1402 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1403 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1404 xfs_mount_t *mp; /* filesystem mount point */
1405 int needlog; /* need to log data header */
1406 int needscan; /* need to rescan data frees */
1407 xfs_dir2_data_off_t oldbest; /* old value of best free */
1408 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner33363fe2013-04-03 16:11:22 +11001409 struct xfs_dir2_data_free *bf; /* bestfree table */
Dave Chinner24df33b2013-04-12 07:30:21 +10001410 struct xfs_dir2_leaf_entry *ents;
1411 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001412
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001413 trace_xfs_dir2_leaf_removename(args);
1414
Linus Torvalds1da177e2005-04-16 15:20:36 -07001415 /*
1416 * Lookup the leaf entry, get the leaf and data blocks read in.
1417 */
1418 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1419 return error;
1420 }
1421 dp = args->dp;
1422 tp = args->trans;
1423 mp = dp->i_mount;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001424 leaf = lbp->b_addr;
1425 hdr = dbp->b_addr;
Dave Chinner33363fe2013-04-03 16:11:22 +11001426 xfs_dir3_data_check(dp, dbp);
Dave Chinner2ca98772013-10-29 22:11:49 +11001427 bf = dp->d_ops->data_bestfree_p(hdr);
Dave Chinner24df33b2013-04-12 07:30:21 +10001428 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
Dave Chinner41419562013-10-29 22:11:50 +11001429 ents = dp->d_ops->leaf_ents_p(leaf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001430 /*
1431 * Point to the leaf entry, use that to point to the data entry.
1432 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001433 lep = &ents[index];
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001434 db = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001435 dep = (xfs_dir2_data_entry_t *)
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001436 ((char *)hdr + xfs_dir2_dataptr_to_off(mp, be32_to_cpu(lep->address)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001437 needscan = needlog = 0;
Dave Chinner33363fe2013-04-03 16:11:22 +11001438 oldbest = be16_to_cpu(bf[0].length);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001439 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
1440 bestsp = xfs_dir2_leaf_bests_p(ltp);
Nathan Scott68b3a102006-03-17 17:27:19 +11001441 ASSERT(be16_to_cpu(bestsp[db]) == oldbest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001442 /*
1443 * Mark the former data entry unused.
1444 */
Dave Chinner2ca98772013-10-29 22:11:49 +11001445 xfs_dir2_data_make_free(tp, dp, dbp,
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001446 (xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),
Dave Chinner9d23fc82013-10-29 22:11:48 +11001447 dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001448 /*
1449 * We just mark the leaf entry stale by putting a null in it.
1450 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001451 leafhdr.stale++;
1452 xfs_dir3_leaf_hdr_to_disk(leaf, &leafhdr);
Dave Chinner41419562013-10-29 22:11:50 +11001453 xfs_dir3_leaf_log_header(tp, dp, lbp);
Dave Chinner24df33b2013-04-12 07:30:21 +10001454
Nathan Scott3c1f9c12006-03-17 17:28:18 +11001455 lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
Dave Chinner41419562013-10-29 22:11:50 +11001456 xfs_dir3_leaf_log_ents(tp, dp, lbp, index, index);
Dave Chinner24df33b2013-04-12 07:30:21 +10001457
Linus Torvalds1da177e2005-04-16 15:20:36 -07001458 /*
1459 * Scan the freespace in the data block again if necessary,
1460 * log the data block header if necessary.
1461 */
1462 if (needscan)
Dave Chinner9d23fc82013-10-29 22:11:48 +11001463 xfs_dir2_data_freescan(dp, hdr, &needlog);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001464 if (needlog)
Dave Chinner2ca98772013-10-29 22:11:49 +11001465 xfs_dir2_data_log_header(tp, dp, dbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001466 /*
1467 * If the longest freespace in the data block has changed,
1468 * put the new value in the bests table and log that.
1469 */
Dave Chinner33363fe2013-04-03 16:11:22 +11001470 if (be16_to_cpu(bf[0].length) != oldbest) {
1471 bestsp[db] = bf[0].length;
Dave Chinner24df33b2013-04-12 07:30:21 +10001472 xfs_dir3_leaf_log_bests(tp, lbp, db, db);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001473 }
Dave Chinner33363fe2013-04-03 16:11:22 +11001474 xfs_dir3_data_check(dp, dbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001475 /*
1476 * If the data block is now empty then get rid of the data block.
1477 */
Dave Chinner33363fe2013-04-03 16:11:22 +11001478 if (be16_to_cpu(bf[0].length) ==
Dave Chinner2ca98772013-10-29 22:11:49 +11001479 mp->m_dirblksize - dp->d_ops->data_entry_offset()) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001480 ASSERT(db != mp->m_dirdatablk);
1481 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1482 /*
1483 * Nope, can't get rid of it because it caused
1484 * allocation of a bmap btree block to do so.
1485 * Just go on, returning success, leaving the
1486 * empty block in place.
1487 */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001488 if (error == ENOSPC && args->total == 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001489 error = 0;
Dave Chinner41419562013-10-29 22:11:50 +11001490 xfs_dir3_leaf_check(dp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001491 return error;
1492 }
1493 dbp = NULL;
1494 /*
1495 * If this is the last data block then compact the
1496 * bests table by getting rid of entries.
1497 */
Nathan Scottafbcb3f2006-03-17 17:27:28 +11001498 if (db == be32_to_cpu(ltp->bestcount) - 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001499 /*
1500 * Look for the last active entry (i).
1501 */
1502 for (i = db - 1; i > 0; i--) {
Christoph Hellwig69ef9212011-07-08 14:36:05 +02001503 if (bestsp[i] != cpu_to_be16(NULLDATAOFF))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001504 break;
1505 }
1506 /*
1507 * Copy the table down so inactive entries at the
1508 * end are removed.
1509 */
1510 memmove(&bestsp[db - i], bestsp,
Nathan Scottafbcb3f2006-03-17 17:27:28 +11001511 (be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp));
Marcin Slusarz413d57c2008-02-13 15:03:29 -08001512 be32_add_cpu(&ltp->bestcount, -(db - i));
Dave Chinner24df33b2013-04-12 07:30:21 +10001513 xfs_dir3_leaf_log_tail(tp, lbp);
1514 xfs_dir3_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001515 } else
Nathan Scott68b3a102006-03-17 17:27:19 +11001516 bestsp[db] = cpu_to_be16(NULLDATAOFF);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001517 }
1518 /*
1519 * If the data block was not the first one, drop it.
1520 */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001521 else if (db != mp->m_dirdatablk)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001522 dbp = NULL;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001523
Dave Chinner41419562013-10-29 22:11:50 +11001524 xfs_dir3_leaf_check(dp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001525 /*
1526 * See if we can convert to block form.
1527 */
1528 return xfs_dir2_leaf_to_block(args, lbp, dbp);
1529}
1530
1531/*
1532 * Replace the inode number in a leaf format directory entry.
1533 */
1534int /* error */
1535xfs_dir2_leaf_replace(
1536 xfs_da_args_t *args) /* operation arguments */
1537{
Dave Chinner1d9025e2012-06-22 18:50:14 +10001538 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001539 xfs_dir2_data_entry_t *dep; /* data block entry */
1540 xfs_inode_t *dp; /* incore directory inode */
1541 int error; /* error return code */
1542 int index; /* index of leaf entry */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001543 struct xfs_buf *lbp; /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001544 xfs_dir2_leaf_t *leaf; /* leaf structure */
1545 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1546 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner24df33b2013-04-12 07:30:21 +10001547 struct xfs_dir2_leaf_entry *ents;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001548
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001549 trace_xfs_dir2_leaf_replace(args);
1550
Linus Torvalds1da177e2005-04-16 15:20:36 -07001551 /*
1552 * Look up the entry.
1553 */
1554 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1555 return error;
1556 }
1557 dp = args->dp;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001558 leaf = lbp->b_addr;
Dave Chinner41419562013-10-29 22:11:50 +11001559 ents = dp->d_ops->leaf_ents_p(leaf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001560 /*
1561 * Point to the leaf entry, get data address from it.
1562 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001563 lep = &ents[index];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001564 /*
1565 * Point to the data entry.
1566 */
1567 dep = (xfs_dir2_data_entry_t *)
Dave Chinner1d9025e2012-06-22 18:50:14 +10001568 ((char *)dbp->b_addr +
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001569 xfs_dir2_dataptr_to_off(dp->i_mount, be32_to_cpu(lep->address)));
Christoph Hellwigff9901c2006-06-09 14:48:37 +10001570 ASSERT(args->inumber != be64_to_cpu(dep->inumber));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001571 /*
1572 * Put the new inode number in, log it.
1573 */
Christoph Hellwigff9901c2006-06-09 14:48:37 +10001574 dep->inumber = cpu_to_be64(args->inumber);
Dave Chinner9d23fc82013-10-29 22:11:48 +11001575 dp->d_ops->data_put_ftype(dep, args->filetype);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001576 tp = args->trans;
Dave Chinner9d23fc82013-10-29 22:11:48 +11001577 xfs_dir2_data_log_entry(tp, dp, dbp, dep);
Dave Chinner41419562013-10-29 22:11:50 +11001578 xfs_dir3_leaf_check(dp, lbp);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001579 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001580 return 0;
1581}
1582
1583/*
1584 * Return index in the leaf block (lbp) which is either the first
1585 * one with this hash value, or if there are none, the insert point
1586 * for that hash value.
1587 */
1588int /* index value */
1589xfs_dir2_leaf_search_hash(
1590 xfs_da_args_t *args, /* operation arguments */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001591 struct xfs_buf *lbp) /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001592{
1593 xfs_dahash_t hash=0; /* hash from this entry */
1594 xfs_dahash_t hashwant; /* hash value looking for */
1595 int high; /* high leaf index */
1596 int low; /* low leaf index */
1597 xfs_dir2_leaf_t *leaf; /* leaf structure */
1598 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1599 int mid=0; /* current leaf index */
Dave Chinner24df33b2013-04-12 07:30:21 +10001600 struct xfs_dir2_leaf_entry *ents;
1601 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001602
Dave Chinner1d9025e2012-06-22 18:50:14 +10001603 leaf = lbp->b_addr;
Dave Chinner41419562013-10-29 22:11:50 +11001604 ents = args->dp->d_ops->leaf_ents_p(leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +10001605 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
1606
Linus Torvalds1da177e2005-04-16 15:20:36 -07001607 /*
1608 * Note, the table cannot be empty, so we have to go through the loop.
1609 * Binary search the leaf entries looking for our hash value.
1610 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001611 for (lep = ents, low = 0, high = leafhdr.count - 1,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001612 hashwant = args->hashval;
1613 low <= high; ) {
1614 mid = (low + high) >> 1;
Nathan Scott3c1f9c12006-03-17 17:28:18 +11001615 if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001616 break;
1617 if (hash < hashwant)
1618 low = mid + 1;
1619 else
1620 high = mid - 1;
1621 }
1622 /*
1623 * Found one, back up through all the equal hash values.
1624 */
1625 if (hash == hashwant) {
Nathan Scott3c1f9c12006-03-17 17:28:18 +11001626 while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001627 mid--;
1628 }
1629 }
1630 /*
1631 * Need to point to an entry higher than ours.
1632 */
1633 else if (hash < hashwant)
1634 mid++;
1635 return mid;
1636}
1637
1638/*
1639 * Trim off a trailing data block. We know it's empty since the leaf
1640 * freespace table says so.
1641 */
1642int /* error */
1643xfs_dir2_leaf_trim_data(
1644 xfs_da_args_t *args, /* operation arguments */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001645 struct xfs_buf *lbp, /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001646 xfs_dir2_db_t db) /* data block number */
1647{
Nathan Scott68b3a102006-03-17 17:27:19 +11001648 __be16 *bestsp; /* leaf bests table */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001649 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001650 xfs_inode_t *dp; /* incore directory inode */
1651 int error; /* error return value */
1652 xfs_dir2_leaf_t *leaf; /* leaf structure */
1653 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1654 xfs_mount_t *mp; /* filesystem mount point */
1655 xfs_trans_t *tp; /* transaction pointer */
1656
1657 dp = args->dp;
1658 mp = dp->i_mount;
1659 tp = args->trans;
1660 /*
1661 * Read the offending data block. We need its buffer.
1662 */
Dave Chinner33363fe2013-04-03 16:11:22 +11001663 error = xfs_dir3_data_read(tp, dp, xfs_dir2_db_to_da(mp, db), -1, &dbp);
Dave Chinner4bb20a82012-11-12 22:54:10 +11001664 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001665 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001666
Dave Chinner1d9025e2012-06-22 18:50:14 +10001667 leaf = lbp->b_addr;
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001668 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001669
1670#ifdef DEBUG
1671{
Dave Chinner1d9025e2012-06-22 18:50:14 +10001672 struct xfs_dir2_data_hdr *hdr = dbp->b_addr;
Dave Chinner2ca98772013-10-29 22:11:49 +11001673 struct xfs_dir2_data_free *bf = dp->d_ops->data_bestfree_p(hdr);
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001674
Dave Chinner33363fe2013-04-03 16:11:22 +11001675 ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
1676 hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
1677 ASSERT(be16_to_cpu(bf[0].length) ==
Dave Chinner2ca98772013-10-29 22:11:49 +11001678 mp->m_dirblksize - dp->d_ops->data_entry_offset());
Nathan Scottafbcb3f2006-03-17 17:27:28 +11001679 ASSERT(db == be32_to_cpu(ltp->bestcount) - 1);
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001680}
1681#endif
1682
Linus Torvalds1da177e2005-04-16 15:20:36 -07001683 /*
1684 * Get rid of the data block.
1685 */
1686 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1687 ASSERT(error != ENOSPC);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001688 xfs_trans_brelse(tp, dbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001689 return error;
1690 }
1691 /*
1692 * Eliminate the last bests entry from the table.
1693 */
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001694 bestsp = xfs_dir2_leaf_bests_p(ltp);
Marcin Slusarz413d57c2008-02-13 15:03:29 -08001695 be32_add_cpu(&ltp->bestcount, -1);
Nathan Scottafbcb3f2006-03-17 17:27:28 +11001696 memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp));
Dave Chinner24df33b2013-04-12 07:30:21 +10001697 xfs_dir3_leaf_log_tail(tp, lbp);
1698 xfs_dir3_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001699 return 0;
1700}
1701
Christoph Hellwig22823962011-07-08 14:35:53 +02001702static inline size_t
Dave Chinner24df33b2013-04-12 07:30:21 +10001703xfs_dir3_leaf_size(
1704 struct xfs_dir3_icleaf_hdr *hdr,
Christoph Hellwig22823962011-07-08 14:35:53 +02001705 int counts)
1706{
Dave Chinner24df33b2013-04-12 07:30:21 +10001707 int entries;
1708 int hdrsize;
Christoph Hellwig22823962011-07-08 14:35:53 +02001709
Dave Chinner24df33b2013-04-12 07:30:21 +10001710 entries = hdr->count - hdr->stale;
1711 if (hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
1712 hdr->magic == XFS_DIR2_LEAFN_MAGIC)
1713 hdrsize = sizeof(struct xfs_dir2_leaf_hdr);
1714 else
1715 hdrsize = sizeof(struct xfs_dir3_leaf_hdr);
1716
1717 return hdrsize + entries * sizeof(xfs_dir2_leaf_entry_t)
1718 + counts * sizeof(xfs_dir2_data_off_t)
1719 + sizeof(xfs_dir2_leaf_tail_t);
Christoph Hellwig22823962011-07-08 14:35:53 +02001720}
1721
Linus Torvalds1da177e2005-04-16 15:20:36 -07001722/*
1723 * Convert node form directory to leaf form directory.
1724 * The root of the node form dir needs to already be a LEAFN block.
1725 * Just return if we can't do anything.
1726 */
1727int /* error */
1728xfs_dir2_node_to_leaf(
1729 xfs_da_state_t *state) /* directory operation state */
1730{
1731 xfs_da_args_t *args; /* operation arguments */
1732 xfs_inode_t *dp; /* incore directory inode */
1733 int error; /* error return code */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001734 struct xfs_buf *fbp; /* buffer for freespace block */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001735 xfs_fileoff_t fo; /* freespace file offset */
1736 xfs_dir2_free_t *free; /* freespace structure */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001737 struct xfs_buf *lbp; /* buffer for leaf block */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001738 xfs_dir2_leaf_tail_t *ltp; /* tail of leaf structure */
1739 xfs_dir2_leaf_t *leaf; /* leaf structure */
1740 xfs_mount_t *mp; /* filesystem mount point */
1741 int rval; /* successful free trim? */
1742 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner24df33b2013-04-12 07:30:21 +10001743 struct xfs_dir3_icleaf_hdr leafhdr;
Dave Chinnercbc8adf2013-04-03 16:11:21 +11001744 struct xfs_dir3_icfree_hdr freehdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001745
1746 /*
1747 * There's more than a leaf level in the btree, so there must
1748 * be multiple leafn blocks. Give up.
1749 */
1750 if (state->path.active > 1)
1751 return 0;
1752 args = state->args;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001753
1754 trace_xfs_dir2_node_to_leaf(args);
1755
Linus Torvalds1da177e2005-04-16 15:20:36 -07001756 mp = state->mp;
1757 dp = args->dp;
1758 tp = args->trans;
1759 /*
1760 * Get the last offset in the file.
1761 */
1762 if ((error = xfs_bmap_last_offset(tp, dp, &fo, XFS_DATA_FORK))) {
1763 return error;
1764 }
1765 fo -= mp->m_dirblkfsbs;
1766 /*
1767 * If there are freespace blocks other than the first one,
1768 * take this opportunity to remove trailing empty freespace blocks
1769 * that may have been left behind during no-space-reservation
1770 * operations.
1771 */
1772 while (fo > mp->m_dirfreeblk) {
1773 if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
1774 return error;
1775 }
1776 if (rval)
1777 fo -= mp->m_dirblkfsbs;
1778 else
1779 return 0;
1780 }
1781 /*
1782 * Now find the block just before the freespace block.
1783 */
1784 if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
1785 return error;
1786 }
1787 /*
1788 * If it's not the single leaf block, give up.
1789 */
1790 if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + mp->m_dirblksize)
1791 return 0;
1792 lbp = state->path.blk[0].bp;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001793 leaf = lbp->b_addr;
Dave Chinner24df33b2013-04-12 07:30:21 +10001794 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
1795
1796 ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
1797 leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
1798
Linus Torvalds1da177e2005-04-16 15:20:36 -07001799 /*
1800 * Read the freespace block.
1801 */
Dave Chinner20252072012-11-12 22:54:13 +11001802 error = xfs_dir2_free_read(tp, dp, mp->m_dirfreeblk, &fbp);
Dave Chinner4bb20a82012-11-12 22:54:10 +11001803 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001804 return error;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001805 free = fbp->b_addr;
Dave Chinnercbc8adf2013-04-03 16:11:21 +11001806 xfs_dir3_free_hdr_from_disk(&freehdr, free);
1807
1808 ASSERT(!freehdr.firstdb);
Christoph Hellwig22823962011-07-08 14:35:53 +02001809
Linus Torvalds1da177e2005-04-16 15:20:36 -07001810 /*
1811 * Now see if the leafn and free data will fit in a leaf1.
1812 * If not, release the buffer and give up.
1813 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001814 if (xfs_dir3_leaf_size(&leafhdr, freehdr.nvalid) > mp->m_dirblksize) {
Dave Chinner1d9025e2012-06-22 18:50:14 +10001815 xfs_trans_brelse(tp, fbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001816 return 0;
1817 }
Christoph Hellwig22823962011-07-08 14:35:53 +02001818
Linus Torvalds1da177e2005-04-16 15:20:36 -07001819 /*
1820 * If the leaf has any stale entries in it, compress them out.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001821 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001822 if (leafhdr.stale)
1823 xfs_dir3_leaf_compact(args, &leafhdr, lbp);
Dave Chinnerb0f539d2012-11-14 17:53:49 +11001824
Dave Chinner24df33b2013-04-12 07:30:21 +10001825 lbp->b_ops = &xfs_dir3_leaf1_buf_ops;
Dave Chinner61fe1352013-04-03 16:11:30 +11001826 xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAF1_BUF);
Dave Chinner24df33b2013-04-12 07:30:21 +10001827 leafhdr.magic = (leafhdr.magic == XFS_DIR2_LEAFN_MAGIC)
1828 ? XFS_DIR2_LEAF1_MAGIC
1829 : XFS_DIR3_LEAF1_MAGIC;
Dave Chinnerb0f539d2012-11-14 17:53:49 +11001830
Linus Torvalds1da177e2005-04-16 15:20:36 -07001831 /*
1832 * Set up the leaf tail from the freespace block.
1833 */
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001834 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Dave Chinnercbc8adf2013-04-03 16:11:21 +11001835 ltp->bestcount = cpu_to_be32(freehdr.nvalid);
Dave Chinner24df33b2013-04-12 07:30:21 +10001836
Linus Torvalds1da177e2005-04-16 15:20:36 -07001837 /*
1838 * Set up the leaf bests table.
1839 */
Dave Chinnercbc8adf2013-04-03 16:11:21 +11001840 memcpy(xfs_dir2_leaf_bests_p(ltp), xfs_dir3_free_bests_p(mp, free),
1841 freehdr.nvalid * sizeof(xfs_dir2_data_off_t));
Dave Chinner24df33b2013-04-12 07:30:21 +10001842
1843 xfs_dir3_leaf_hdr_to_disk(leaf, &leafhdr);
Dave Chinner41419562013-10-29 22:11:50 +11001844 xfs_dir3_leaf_log_header(tp, dp, lbp);
Dave Chinner24df33b2013-04-12 07:30:21 +10001845 xfs_dir3_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
1846 xfs_dir3_leaf_log_tail(tp, lbp);
Dave Chinner41419562013-10-29 22:11:50 +11001847 xfs_dir3_leaf_check(dp, lbp);
Dave Chinner24df33b2013-04-12 07:30:21 +10001848
Linus Torvalds1da177e2005-04-16 15:20:36 -07001849 /*
1850 * Get rid of the freespace block.
1851 */
1852 error = xfs_dir2_shrink_inode(args, XFS_DIR2_FREE_FIRSTDB(mp), fbp);
1853 if (error) {
1854 /*
1855 * This can't fail here because it can only happen when
1856 * punching out the middle of an extent, and this is an
1857 * isolated block.
1858 */
1859 ASSERT(error != ENOSPC);
1860 return error;
1861 }
1862 fbp = NULL;
1863 /*
1864 * Now see if we can convert the single-leaf directory
1865 * down to a block form directory.
1866 * This routine always kills the dabuf for the leaf, so
1867 * eliminate it from the path.
1868 */
1869 error = xfs_dir2_leaf_to_block(args, lbp, NULL);
1870 state->path.blk[0].bp = NULL;
1871 return error;
1872}