blob: dd195363ccf280f0070ebd5d89d8aea7da764717 [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
53#define xfs_dir3_leaf_check(mp, bp) \
54do { \
55 if (!xfs_dir3_leaf1_check((mp), (bp))) \
56 ASSERT(0); \
57} while (0);
58
59STATIC bool
60xfs_dir3_leaf1_check(
61 struct xfs_mount *mp,
62 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
76 return xfs_dir3_leaf_check_int(mp, &leafhdr, leaf);
77}
78#else
79#define xfs_dir3_leaf_check(mp, bp)
80#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,
141 struct xfs_dir3_icleaf_hdr *hdr,
142 struct xfs_dir2_leaf *leaf)
143{
144 struct xfs_dir2_leaf_entry *ents;
145 xfs_dir2_leaf_tail_t *ltp;
146 int stale;
147 int i;
148
149 ents = xfs_dir3_leaf_ents_p(leaf);
150 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
151
152 /*
153 * XXX (dgc): This value is not restrictive enough.
154 * Should factor in the size of the bests table as well.
155 * We can deduce a value for that from di_size.
156 */
157 if (hdr->count > xfs_dir3_max_leaf_ents(mp, leaf))
158 return false;
159
160 /* Leaves and bests don't overlap in leaf format. */
161 if ((hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
162 hdr->magic == XFS_DIR3_LEAF1_MAGIC) &&
163 (char *)&ents[hdr->count] > (char *)xfs_dir2_leaf_bests_p(ltp))
164 return false;
165
166 /* Check hash value order, count stale entries. */
167 for (i = stale = 0; i < hdr->count; i++) {
168 if (i + 1 < hdr->count) {
169 if (be32_to_cpu(ents[i].hashval) >
170 be32_to_cpu(ents[i + 1].hashval))
171 return false;
172 }
173 if (ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
174 stale++;
175 }
176 if (hdr->stale != stale)
177 return false;
178 return true;
179}
180
Dave Chinner0f295a22013-09-03 10:06:58 +1000181/*
182 * We verify the magic numbers before decoding the leaf header so that on debug
183 * kernels we don't get assertion failures in xfs_dir3_leaf_hdr_from_disk() due
184 * to incorrect magic numbers.
185 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000186static bool
187xfs_dir3_leaf_verify(
Dave Chinnere6f76672012-11-12 22:54:15 +1100188 struct xfs_buf *bp,
Dave Chinner24df33b2013-04-12 07:30:21 +1000189 __uint16_t magic)
Dave Chinnere6f76672012-11-12 22:54:15 +1100190{
191 struct xfs_mount *mp = bp->b_target->bt_mount;
Dave Chinner24df33b2013-04-12 07:30:21 +1000192 struct xfs_dir2_leaf *leaf = bp->b_addr;
193 struct xfs_dir3_icleaf_hdr leafhdr;
Dave Chinnere6f76672012-11-12 22:54:15 +1100194
Dave Chinner24df33b2013-04-12 07:30:21 +1000195 ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
196
Dave Chinner24df33b2013-04-12 07:30:21 +1000197 if (xfs_sb_version_hascrc(&mp->m_sb)) {
198 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
Dave Chinner0f295a22013-09-03 10:06:58 +1000199 __uint16_t magic3;
Dave Chinner24df33b2013-04-12 07:30:21 +1000200
Dave Chinner0f295a22013-09-03 10:06:58 +1000201 magic3 = (magic == XFS_DIR2_LEAF1_MAGIC) ? XFS_DIR3_LEAF1_MAGIC
202 : XFS_DIR3_LEAFN_MAGIC;
203
204 if (leaf3->info.hdr.magic != cpu_to_be16(magic3))
Dave Chinner24df33b2013-04-12 07:30:21 +1000205 return false;
Dave Chinner24df33b2013-04-12 07:30:21 +1000206 if (!uuid_equal(&leaf3->info.uuid, &mp->m_sb.sb_uuid))
207 return false;
208 if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
209 return false;
210 } else {
Dave Chinner0f295a22013-09-03 10:06:58 +1000211 if (leaf->hdr.info.magic != cpu_to_be16(magic))
Dave Chinner24df33b2013-04-12 07:30:21 +1000212 return false;
213 }
Dave Chinner0f295a22013-09-03 10:06:58 +1000214
215 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +1000216 return xfs_dir3_leaf_check_int(mp, &leafhdr, leaf);
217}
218
219static void
220__read_verify(
221 struct xfs_buf *bp,
222 __uint16_t magic)
223{
224 struct xfs_mount *mp = bp->b_target->bt_mount;
225
226 if ((xfs_sb_version_hascrc(&mp->m_sb) &&
227 !xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
228 XFS_DIR3_LEAF_CRC_OFF)) ||
229 !xfs_dir3_leaf_verify(bp, magic)) {
230 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
Dave Chinnere6f76672012-11-12 22:54:15 +1100231 xfs_buf_ioerror(bp, EFSCORRUPTED);
232 }
Dave Chinner612cfbf2012-11-14 17:52:32 +1100233}
Dave Chinnere6f76672012-11-12 22:54:15 +1100234
Dave Chinner612cfbf2012-11-14 17:52:32 +1100235static void
Dave Chinner24df33b2013-04-12 07:30:21 +1000236__write_verify(
237 struct xfs_buf *bp,
238 __uint16_t magic)
Dave Chinner612cfbf2012-11-14 17:52:32 +1100239{
Dave Chinner24df33b2013-04-12 07:30:21 +1000240 struct xfs_mount *mp = bp->b_target->bt_mount;
241 struct xfs_buf_log_item *bip = bp->b_fspriv;
242 struct xfs_dir3_leaf_hdr *hdr3 = bp->b_addr;
243
244 if (!xfs_dir3_leaf_verify(bp, magic)) {
245 XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
246 xfs_buf_ioerror(bp, EFSCORRUPTED);
247 return;
248 }
249
250 if (!xfs_sb_version_hascrc(&mp->m_sb))
251 return;
252
253 if (bip)
254 hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
255
256 xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length), XFS_DIR3_LEAF_CRC_OFF);
Dave Chinner612cfbf2012-11-14 17:52:32 +1100257}
258
259static void
Dave Chinner24df33b2013-04-12 07:30:21 +1000260xfs_dir3_leaf1_read_verify(
Dave Chinner612cfbf2012-11-14 17:52:32 +1100261 struct xfs_buf *bp)
262{
Dave Chinner24df33b2013-04-12 07:30:21 +1000263 __read_verify(bp, XFS_DIR2_LEAF1_MAGIC);
Dave Chinner1813dd62012-11-14 17:54:40 +1100264}
265
Dave Chinner24df33b2013-04-12 07:30:21 +1000266static void
267xfs_dir3_leaf1_write_verify(
Dave Chinner1813dd62012-11-14 17:54:40 +1100268 struct xfs_buf *bp)
269{
Dave Chinner24df33b2013-04-12 07:30:21 +1000270 __write_verify(bp, XFS_DIR2_LEAF1_MAGIC);
Dave Chinnere6f76672012-11-12 22:54:15 +1100271}
272
Dave Chinner24df33b2013-04-12 07:30:21 +1000273static void
274xfs_dir3_leafn_read_verify(
Dave Chinner612cfbf2012-11-14 17:52:32 +1100275 struct xfs_buf *bp)
Dave Chinnere6f76672012-11-12 22:54:15 +1100276{
Dave Chinner24df33b2013-04-12 07:30:21 +1000277 __read_verify(bp, XFS_DIR2_LEAFN_MAGIC);
Dave Chinnere6f76672012-11-12 22:54:15 +1100278}
279
Dave Chinner24df33b2013-04-12 07:30:21 +1000280static void
281xfs_dir3_leafn_write_verify(
282 struct xfs_buf *bp)
283{
284 __write_verify(bp, XFS_DIR2_LEAFN_MAGIC);
285}
286
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100287const struct xfs_buf_ops xfs_dir3_leaf1_buf_ops = {
Dave Chinner24df33b2013-04-12 07:30:21 +1000288 .verify_read = xfs_dir3_leaf1_read_verify,
289 .verify_write = xfs_dir3_leaf1_write_verify,
Dave Chinner1813dd62012-11-14 17:54:40 +1100290};
291
Dave Chinner24df33b2013-04-12 07:30:21 +1000292const struct xfs_buf_ops xfs_dir3_leafn_buf_ops = {
293 .verify_read = xfs_dir3_leafn_read_verify,
294 .verify_write = xfs_dir3_leafn_write_verify,
Dave Chinner1813dd62012-11-14 17:54:40 +1100295};
Dave Chinnere6f76672012-11-12 22:54:15 +1100296
297static int
Dave Chinner24df33b2013-04-12 07:30:21 +1000298xfs_dir3_leaf_read(
Dave Chinnere6f76672012-11-12 22:54:15 +1100299 struct xfs_trans *tp,
300 struct xfs_inode *dp,
301 xfs_dablk_t fbno,
302 xfs_daddr_t mappedbno,
303 struct xfs_buf **bpp)
304{
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100305 int err;
306
307 err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
Dave Chinner24df33b2013-04-12 07:30:21 +1000308 XFS_DATA_FORK, &xfs_dir3_leaf1_buf_ops);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100309 if (!err && tp)
Dave Chinner61fe1352013-04-03 16:11:30 +1100310 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAF1_BUF);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100311 return err;
Dave Chinnere6f76672012-11-12 22:54:15 +1100312}
313
314int
Dave Chinner24df33b2013-04-12 07:30:21 +1000315xfs_dir3_leafn_read(
Dave Chinnere6f76672012-11-12 22:54:15 +1100316 struct xfs_trans *tp,
317 struct xfs_inode *dp,
318 xfs_dablk_t fbno,
319 xfs_daddr_t mappedbno,
320 struct xfs_buf **bpp)
321{
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100322 int err;
323
324 err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
Dave Chinner24df33b2013-04-12 07:30:21 +1000325 XFS_DATA_FORK, &xfs_dir3_leafn_buf_ops);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100326 if (!err && tp)
Dave Chinner61fe1352013-04-03 16:11:30 +1100327 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAFN_BUF);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100328 return err;
Dave Chinner24df33b2013-04-12 07:30:21 +1000329}
330
331/*
332 * Initialize a new leaf block, leaf1 or leafn magic accepted.
333 */
334static void
335xfs_dir3_leaf_init(
336 struct xfs_mount *mp,
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100337 struct xfs_trans *tp,
Dave Chinner24df33b2013-04-12 07:30:21 +1000338 struct xfs_buf *bp,
339 xfs_ino_t owner,
340 __uint16_t type)
341{
342 struct xfs_dir2_leaf *leaf = bp->b_addr;
343
344 ASSERT(type == XFS_DIR2_LEAF1_MAGIC || type == XFS_DIR2_LEAFN_MAGIC);
345
346 if (xfs_sb_version_hascrc(&mp->m_sb)) {
347 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
348
349 memset(leaf3, 0, sizeof(*leaf3));
350
351 leaf3->info.hdr.magic = (type == XFS_DIR2_LEAF1_MAGIC)
352 ? cpu_to_be16(XFS_DIR3_LEAF1_MAGIC)
353 : cpu_to_be16(XFS_DIR3_LEAFN_MAGIC);
354 leaf3->info.blkno = cpu_to_be64(bp->b_bn);
355 leaf3->info.owner = cpu_to_be64(owner);
356 uuid_copy(&leaf3->info.uuid, &mp->m_sb.sb_uuid);
357 } else {
358 memset(leaf, 0, sizeof(*leaf));
359 leaf->hdr.info.magic = cpu_to_be16(type);
360 }
361
362 /*
363 * If it's a leaf-format directory initialize the tail.
364 * Caller is responsible for initialising the bests table.
365 */
366 if (type == XFS_DIR2_LEAF1_MAGIC) {
367 struct xfs_dir2_leaf_tail *ltp;
368
369 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
370 ltp->bestcount = 0;
371 bp->b_ops = &xfs_dir3_leaf1_buf_ops;
Dave Chinner61fe1352013-04-03 16:11:30 +1100372 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAF1_BUF);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100373 } else {
Dave Chinner24df33b2013-04-12 07:30:21 +1000374 bp->b_ops = &xfs_dir3_leafn_buf_ops;
Dave Chinner61fe1352013-04-03 16:11:30 +1100375 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100376 }
Dave Chinner24df33b2013-04-12 07:30:21 +1000377}
378
379int
380xfs_dir3_leaf_get_buf(
381 xfs_da_args_t *args,
382 xfs_dir2_db_t bno,
383 struct xfs_buf **bpp,
384 __uint16_t magic)
385{
386 struct xfs_inode *dp = args->dp;
387 struct xfs_trans *tp = args->trans;
388 struct xfs_mount *mp = dp->i_mount;
389 struct xfs_buf *bp;
390 int error;
391
392 ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
393 ASSERT(bno >= XFS_DIR2_LEAF_FIRSTDB(mp) &&
394 bno < XFS_DIR2_FREE_FIRSTDB(mp));
395
396 error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(mp, bno), -1, &bp,
397 XFS_DATA_FORK);
398 if (error)
399 return error;
400
Dave Chinnerd75afeb2013-04-03 16:11:29 +1100401 xfs_dir3_leaf_init(mp, tp, bp, dp->i_ino, magic);
Dave Chinner24df33b2013-04-12 07:30:21 +1000402 xfs_dir3_leaf_log_header(tp, bp);
403 if (magic == XFS_DIR2_LEAF1_MAGIC)
404 xfs_dir3_leaf_log_tail(tp, bp);
405 *bpp = bp;
406 return 0;
Dave Chinnere6f76672012-11-12 22:54:15 +1100407}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700408
409/*
410 * Convert a block form directory to a leaf form directory.
411 */
412int /* error */
413xfs_dir2_block_to_leaf(
414 xfs_da_args_t *args, /* operation arguments */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000415 struct xfs_buf *dbp) /* input block's buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700416{
Nathan Scott68b3a102006-03-17 17:27:19 +1100417 __be16 *bestsp; /* leaf's bestsp entries */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700418 xfs_dablk_t blkno; /* leaf block's bno */
Christoph Hellwig4f6ae1a2011-07-08 14:35:27 +0200419 xfs_dir2_data_hdr_t *hdr; /* block header */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700420 xfs_dir2_leaf_entry_t *blp; /* block's leaf entries */
421 xfs_dir2_block_tail_t *btp; /* block's tail */
422 xfs_inode_t *dp; /* incore directory inode */
423 int error; /* error return code */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000424 struct xfs_buf *lbp; /* leaf block's buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425 xfs_dir2_db_t ldb; /* leaf block's bno */
426 xfs_dir2_leaf_t *leaf; /* leaf structure */
427 xfs_dir2_leaf_tail_t *ltp; /* leaf's tail */
428 xfs_mount_t *mp; /* filesystem mount point */
429 int needlog; /* need to log block header */
430 int needscan; /* need to rescan bestfree */
431 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner33363fe2013-04-03 16:11:22 +1100432 struct xfs_dir2_data_free *bf;
Dave Chinner24df33b2013-04-12 07:30:21 +1000433 struct xfs_dir2_leaf_entry *ents;
434 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700435
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000436 trace_xfs_dir2_block_to_leaf(args);
437
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438 dp = args->dp;
439 mp = dp->i_mount;
440 tp = args->trans;
441 /*
442 * Add the leaf block to the inode.
443 * This interface will only put blocks in the leaf/node range.
444 * Since that's empty now, we'll get the root (block 0 in range).
445 */
446 if ((error = xfs_da_grow_inode(args, &blkno))) {
447 return error;
448 }
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000449 ldb = xfs_dir2_da_to_db(mp, blkno);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700450 ASSERT(ldb == XFS_DIR2_LEAF_FIRSTDB(mp));
451 /*
452 * Initialize the leaf block, get a buffer for it.
453 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000454 error = xfs_dir3_leaf_get_buf(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC);
455 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700456 return error;
Dave Chinner24df33b2013-04-12 07:30:21 +1000457
Dave Chinner1d9025e2012-06-22 18:50:14 +1000458 leaf = lbp->b_addr;
459 hdr = dbp->b_addr;
Dave Chinner33363fe2013-04-03 16:11:22 +1100460 xfs_dir3_data_check(dp, dbp);
Christoph Hellwig4f6ae1a2011-07-08 14:35:27 +0200461 btp = xfs_dir2_block_tail_p(mp, hdr);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000462 blp = xfs_dir2_block_leaf_p(btp);
Dave Chinnerf5f3d9b2013-04-03 16:11:20 +1100463 bf = xfs_dir3_data_bestfree_p(hdr);
Dave Chinner24df33b2013-04-12 07:30:21 +1000464 ents = xfs_dir3_leaf_ents_p(leaf);
465
Linus Torvalds1da177e2005-04-16 15:20:36 -0700466 /*
467 * Set the counts in the leaf header.
468 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000469 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
470 leafhdr.count = be32_to_cpu(btp->count);
471 leafhdr.stale = be32_to_cpu(btp->stale);
472 xfs_dir3_leaf_hdr_to_disk(leaf, &leafhdr);
473 xfs_dir3_leaf_log_header(tp, lbp);
474
Linus Torvalds1da177e2005-04-16 15:20:36 -0700475 /*
476 * Could compact these but I think we always do the conversion
477 * after squeezing out stale entries.
478 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000479 memcpy(ents, blp, be32_to_cpu(btp->count) * sizeof(xfs_dir2_leaf_entry_t));
480 xfs_dir3_leaf_log_ents(tp, lbp, 0, leafhdr.count - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700481 needscan = 0;
482 needlog = 1;
483 /*
484 * Make the space formerly occupied by the leaf entries and block
485 * tail be free.
486 */
487 xfs_dir2_data_make_free(tp, dbp,
Christoph Hellwig4f6ae1a2011-07-08 14:35:27 +0200488 (xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),
489 (xfs_dir2_data_aoff_t)((char *)hdr + mp->m_dirblksize -
Linus Torvalds1da177e2005-04-16 15:20:36 -0700490 (char *)blp),
491 &needlog, &needscan);
492 /*
493 * Fix up the block header, make it a data block.
494 */
Dave Chinner33363fe2013-04-03 16:11:22 +1100495 dbp->b_ops = &xfs_dir3_data_buf_ops;
Dave Chinner61fe1352013-04-03 16:11:30 +1100496 xfs_trans_buf_set_type(tp, dbp, XFS_BLFT_DIR_DATA_BUF);
Dave Chinner33363fe2013-04-03 16:11:22 +1100497 if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC))
498 hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
499 else
500 hdr->magic = cpu_to_be32(XFS_DIR3_DATA_MAGIC);
501
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502 if (needscan)
Dave Chinner9d23fc82013-10-29 22:11:48 +1100503 xfs_dir2_data_freescan(dp, hdr, &needlog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700504 /*
505 * Set up leaf tail and bests table.
506 */
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000507 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100508 ltp->bestcount = cpu_to_be32(1);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000509 bestsp = xfs_dir2_leaf_bests_p(ltp);
Dave Chinnerf5f3d9b2013-04-03 16:11:20 +1100510 bestsp[0] = bf[0].length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700511 /*
512 * Log the data header and leaf bests table.
513 */
514 if (needlog)
515 xfs_dir2_data_log_header(tp, dbp);
Dave Chinner24df33b2013-04-12 07:30:21 +1000516 xfs_dir3_leaf_check(mp, lbp);
Dave Chinner33363fe2013-04-03 16:11:22 +1100517 xfs_dir3_data_check(dp, dbp);
Dave Chinner24df33b2013-04-12 07:30:21 +1000518 xfs_dir3_leaf_log_bests(tp, lbp, 0, 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700519 return 0;
520}
521
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200522STATIC void
Dave Chinner24df33b2013-04-12 07:30:21 +1000523xfs_dir3_leaf_find_stale(
524 struct xfs_dir3_icleaf_hdr *leafhdr,
525 struct xfs_dir2_leaf_entry *ents,
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200526 int index,
527 int *lowstale,
528 int *highstale)
529{
530 /*
531 * Find the first stale entry before our index, if any.
532 */
533 for (*lowstale = index - 1; *lowstale >= 0; --*lowstale) {
Dave Chinner24df33b2013-04-12 07:30:21 +1000534 if (ents[*lowstale].address ==
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200535 cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
536 break;
537 }
538
539 /*
540 * Find the first stale entry at or after our index, if any.
541 * Stop if the result would require moving more entries than using
542 * lowstale.
543 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000544 for (*highstale = index; *highstale < leafhdr->count; ++*highstale) {
545 if (ents[*highstale].address ==
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200546 cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
547 break;
548 if (*lowstale >= 0 && index - *lowstale <= *highstale - index)
549 break;
550 }
551}
552
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200553struct xfs_dir2_leaf_entry *
Dave Chinner24df33b2013-04-12 07:30:21 +1000554xfs_dir3_leaf_find_entry(
555 struct xfs_dir3_icleaf_hdr *leafhdr,
556 struct xfs_dir2_leaf_entry *ents,
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200557 int index, /* leaf table position */
558 int compact, /* need to compact leaves */
559 int lowstale, /* index of prev stale leaf */
560 int highstale, /* index of next stale leaf */
561 int *lfloglow, /* low leaf logging index */
562 int *lfloghigh) /* high leaf logging index */
563{
Dave Chinner24df33b2013-04-12 07:30:21 +1000564 if (!leafhdr->stale) {
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200565 xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
566
567 /*
568 * Now we need to make room to insert the leaf entry.
569 *
570 * If there are no stale entries, just insert a hole at index.
571 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000572 lep = &ents[index];
573 if (index < leafhdr->count)
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200574 memmove(lep + 1, lep,
Dave Chinner24df33b2013-04-12 07:30:21 +1000575 (leafhdr->count - index) * sizeof(*lep));
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200576
577 /*
578 * Record low and high logging indices for the leaf.
579 */
580 *lfloglow = index;
Dave Chinner24df33b2013-04-12 07:30:21 +1000581 *lfloghigh = leafhdr->count++;
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200582 return lep;
583 }
584
585 /*
586 * There are stale entries.
587 *
588 * We will use one of them for the new entry. It's probably not at
589 * the right location, so we'll have to shift some up or down first.
590 *
591 * If we didn't compact before, we need to find the nearest stale
592 * entries before and after our insertion point.
593 */
Christoph Hellwiga230a1d2011-07-13 13:43:48 +0200594 if (compact == 0)
Dave Chinner24df33b2013-04-12 07:30:21 +1000595 xfs_dir3_leaf_find_stale(leafhdr, ents, index,
596 &lowstale, &highstale);
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200597
598 /*
599 * If the low one is better, use it.
600 */
601 if (lowstale >= 0 &&
Dave Chinner24df33b2013-04-12 07:30:21 +1000602 (highstale == leafhdr->count ||
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200603 index - lowstale - 1 < highstale - index)) {
604 ASSERT(index - lowstale - 1 >= 0);
Dave Chinner24df33b2013-04-12 07:30:21 +1000605 ASSERT(ents[lowstale].address ==
Christoph Hellwig69ef9212011-07-08 14:36:05 +0200606 cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200607
608 /*
609 * Copy entries up to cover the stale entry and make room
610 * for the new entry.
611 */
612 if (index - lowstale - 1 > 0) {
Dave Chinner24df33b2013-04-12 07:30:21 +1000613 memmove(&ents[lowstale], &ents[lowstale + 1],
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200614 (index - lowstale - 1) *
Dave Chinner24df33b2013-04-12 07:30:21 +1000615 sizeof(xfs_dir2_leaf_entry_t));
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200616 }
617 *lfloglow = MIN(lowstale, *lfloglow);
618 *lfloghigh = MAX(index - 1, *lfloghigh);
Dave Chinner24df33b2013-04-12 07:30:21 +1000619 leafhdr->stale--;
620 return &ents[index - 1];
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200621 }
622
623 /*
624 * The high one is better, so use that one.
625 */
626 ASSERT(highstale - index >= 0);
Dave Chinner24df33b2013-04-12 07:30:21 +1000627 ASSERT(ents[highstale].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200628
629 /*
630 * Copy entries down to cover the stale entry and make room for the
631 * new entry.
632 */
633 if (highstale - index > 0) {
Dave Chinner24df33b2013-04-12 07:30:21 +1000634 memmove(&ents[index + 1], &ents[index],
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200635 (highstale - index) * sizeof(xfs_dir2_leaf_entry_t));
636 }
637 *lfloglow = MIN(index, *lfloglow);
638 *lfloghigh = MAX(highstale, *lfloghigh);
Dave Chinner24df33b2013-04-12 07:30:21 +1000639 leafhdr->stale--;
640 return &ents[index];
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200641}
642
Linus Torvalds1da177e2005-04-16 15:20:36 -0700643/*
644 * Add an entry to a leaf form directory.
645 */
646int /* error */
647xfs_dir2_leaf_addname(
648 xfs_da_args_t *args) /* operation arguments */
649{
Nathan Scott68b3a102006-03-17 17:27:19 +1100650 __be16 *bestsp; /* freespace table in leaf */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700651 int compact; /* need to compact leaves */
Christoph Hellwigc2066e22011-07-08 14:35:38 +0200652 xfs_dir2_data_hdr_t *hdr; /* data block header */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000653 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700654 xfs_dir2_data_entry_t *dep; /* data block entry */
655 xfs_inode_t *dp; /* incore directory inode */
656 xfs_dir2_data_unused_t *dup; /* data unused entry */
657 int error; /* error return value */
658 int grown; /* allocated new data block */
659 int highstale; /* index of next stale leaf */
660 int i; /* temporary, index */
661 int index; /* leaf table position */
Dave Chinner1d9025e2012-06-22 18:50:14 +1000662 struct xfs_buf *lbp; /* leaf's buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700663 xfs_dir2_leaf_t *leaf; /* leaf structure */
664 int length; /* length of new entry */
665 xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
666 int lfloglow; /* low leaf logging index */
667 int lfloghigh; /* high leaf logging index */
668 int lowstale; /* index of prev stale leaf */
669 xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
670 xfs_mount_t *mp; /* filesystem mount point */
671 int needbytes; /* leaf block bytes needed */
672 int needlog; /* need to log data header */
673 int needscan; /* need to rescan data free */
Nathan Scott3d693c62006-03-17 17:28:27 +1100674 __be16 *tagp; /* end of data entry */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675 xfs_trans_t *tp; /* transaction pointer */
676 xfs_dir2_db_t use_block; /* data block number */
Dave Chinner33363fe2013-04-03 16:11:22 +1100677 struct xfs_dir2_data_free *bf; /* bestfree table */
Dave Chinner24df33b2013-04-12 07:30:21 +1000678 struct xfs_dir2_leaf_entry *ents;
679 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680
Christoph Hellwig0b1b2132009-12-14 23:14:59 +0000681 trace_xfs_dir2_leaf_addname(args);
682
Linus Torvalds1da177e2005-04-16 15:20:36 -0700683 dp = args->dp;
684 tp = args->trans;
685 mp = dp->i_mount;
Dave Chinnere6f76672012-11-12 22:54:15 +1100686
Dave Chinner24df33b2013-04-12 07:30:21 +1000687 error = xfs_dir3_leaf_read(tp, dp, mp->m_dirleafblk, -1, &lbp);
Dave Chinner4bb20a82012-11-12 22:54:10 +1100688 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700689 return error;
Dave Chinnere6f76672012-11-12 22:54:15 +1100690
Linus Torvalds1da177e2005-04-16 15:20:36 -0700691 /*
692 * Look up the entry by hash value and name.
693 * We know it's not there, our caller has already done a lookup.
694 * So the index is of the entry to insert in front of.
695 * But if there are dup hash values the index is of the first of those.
696 */
697 index = xfs_dir2_leaf_search_hash(args, lbp);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000698 leaf = lbp->b_addr;
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000699 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Dave Chinner24df33b2013-04-12 07:30:21 +1000700 ents = xfs_dir3_leaf_ents_p(leaf);
701 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000702 bestsp = xfs_dir2_leaf_bests_p(ltp);
Dave Chinner9d23fc82013-10-29 22:11:48 +1100703 length = dp->d_ops->data_entsize(args->namelen);
Dave Chinner24df33b2013-04-12 07:30:21 +1000704
Linus Torvalds1da177e2005-04-16 15:20:36 -0700705 /*
706 * See if there are any entries with the same hash value
707 * and space in their block for the new entry.
708 * This is good because it puts multiple same-hash value entries
709 * in a data block, improving the lookup of those entries.
710 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000711 for (use_block = -1, lep = &ents[index];
712 index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700713 index++, lep++) {
Nathan Scott3c1f9c12006-03-17 17:28:18 +1100714 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700715 continue;
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000716 i = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100717 ASSERT(i < be32_to_cpu(ltp->bestcount));
Christoph Hellwig69ef9212011-07-08 14:36:05 +0200718 ASSERT(bestsp[i] != cpu_to_be16(NULLDATAOFF));
Nathan Scott68b3a102006-03-17 17:27:19 +1100719 if (be16_to_cpu(bestsp[i]) >= length) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720 use_block = i;
721 break;
722 }
723 }
724 /*
725 * Didn't find a block yet, linear search all the data blocks.
726 */
727 if (use_block == -1) {
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100728 for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700729 /*
730 * Remember a block we see that's missing.
731 */
Christoph Hellwig69ef9212011-07-08 14:36:05 +0200732 if (bestsp[i] == cpu_to_be16(NULLDATAOFF) &&
733 use_block == -1)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700734 use_block = i;
Nathan Scott68b3a102006-03-17 17:27:19 +1100735 else if (be16_to_cpu(bestsp[i]) >= length) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700736 use_block = i;
737 break;
738 }
739 }
740 }
741 /*
742 * How many bytes do we need in the leaf block?
743 */
Christoph Hellwig22823962011-07-08 14:35:53 +0200744 needbytes = 0;
Dave Chinner24df33b2013-04-12 07:30:21 +1000745 if (!leafhdr.stale)
Christoph Hellwig22823962011-07-08 14:35:53 +0200746 needbytes += sizeof(xfs_dir2_leaf_entry_t);
747 if (use_block == -1)
748 needbytes += sizeof(xfs_dir2_data_off_t);
749
Linus Torvalds1da177e2005-04-16 15:20:36 -0700750 /*
751 * Now kill use_block if it refers to a missing block, so we
752 * can use it as an indication of allocation needed.
753 */
Christoph Hellwig69ef9212011-07-08 14:36:05 +0200754 if (use_block != -1 && bestsp[use_block] == cpu_to_be16(NULLDATAOFF))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700755 use_block = -1;
756 /*
757 * If we don't have enough free bytes but we can make enough
758 * by compacting out stale entries, we'll do that.
759 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000760 if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes &&
761 leafhdr.stale > 1)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700762 compact = 1;
Dave Chinner24df33b2013-04-12 07:30:21 +1000763
Linus Torvalds1da177e2005-04-16 15:20:36 -0700764 /*
765 * Otherwise if we don't have enough free bytes we need to
766 * convert to node form.
767 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000768 else if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700769 /*
770 * Just checking or no space reservation, give up.
771 */
Barry Naujok6a178102008-05-21 16:42:05 +1000772 if ((args->op_flags & XFS_DA_OP_JUSTCHECK) ||
773 args->total == 0) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000774 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700775 return XFS_ERROR(ENOSPC);
776 }
777 /*
778 * Convert to node form.
779 */
780 error = xfs_dir2_leaf_to_node(args, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700781 if (error)
782 return error;
783 /*
784 * Then add the new entry.
785 */
786 return xfs_dir2_node_addname(args);
787 }
788 /*
789 * Otherwise it will fit without compaction.
790 */
791 else
792 compact = 0;
793 /*
794 * If just checking, then it will fit unless we needed to allocate
795 * a new data block.
796 */
Barry Naujok6a178102008-05-21 16:42:05 +1000797 if (args->op_flags & XFS_DA_OP_JUSTCHECK) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000798 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700799 return use_block == -1 ? XFS_ERROR(ENOSPC) : 0;
800 }
801 /*
802 * If no allocations are allowed, return now before we've
803 * changed anything.
804 */
805 if (args->total == 0 && use_block == -1) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000806 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700807 return XFS_ERROR(ENOSPC);
808 }
809 /*
810 * Need to compact the leaf entries, removing stale ones.
811 * Leave one stale entry behind - the one closest to our
812 * insertion index - and we'll shift that one to our insertion
813 * point later.
814 */
815 if (compact) {
Dave Chinner24df33b2013-04-12 07:30:21 +1000816 xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale,
817 &highstale, &lfloglow, &lfloghigh);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700818 }
819 /*
820 * There are stale entries, so we'll need log-low and log-high
821 * impossibly bad values later.
822 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000823 else if (leafhdr.stale) {
824 lfloglow = leafhdr.count;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700825 lfloghigh = -1;
826 }
827 /*
828 * If there was no data block space found, we need to allocate
829 * a new one.
830 */
831 if (use_block == -1) {
832 /*
833 * Add the new data block.
834 */
835 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
836 &use_block))) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000837 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838 return error;
839 }
840 /*
841 * Initialize the block.
842 */
Dave Chinnerf5f3d9b2013-04-03 16:11:20 +1100843 if ((error = xfs_dir3_data_init(args, use_block, &dbp))) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000844 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700845 return error;
846 }
847 /*
848 * If we're adding a new data block on the end we need to
849 * extend the bests table. Copy it up one entry.
850 */
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100851 if (use_block >= be32_to_cpu(ltp->bestcount)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700852 bestsp--;
853 memmove(&bestsp[0], &bestsp[1],
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100854 be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0]));
Marcin Slusarz413d57c2008-02-13 15:03:29 -0800855 be32_add_cpu(&ltp->bestcount, 1);
Dave Chinner24df33b2013-04-12 07:30:21 +1000856 xfs_dir3_leaf_log_tail(tp, lbp);
857 xfs_dir3_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700858 }
859 /*
860 * If we're filling in a previously empty block just log it.
861 */
862 else
Dave Chinner24df33b2013-04-12 07:30:21 +1000863 xfs_dir3_leaf_log_bests(tp, lbp, use_block, use_block);
Dave Chinner1d9025e2012-06-22 18:50:14 +1000864 hdr = dbp->b_addr;
Dave Chinner33363fe2013-04-03 16:11:22 +1100865 bf = xfs_dir3_data_bestfree_p(hdr);
866 bestsp[use_block] = bf[0].length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867 grown = 1;
Dave Chinnere4813572012-11-12 22:54:14 +1100868 } else {
869 /*
870 * Already had space in some data block.
871 * Just read that one in.
872 */
Dave Chinner33363fe2013-04-03 16:11:22 +1100873 error = xfs_dir3_data_read(tp, dp,
Dave Chinnere4813572012-11-12 22:54:14 +1100874 xfs_dir2_db_to_da(mp, use_block),
875 -1, &dbp);
Dave Chinner4bb20a82012-11-12 22:54:10 +1100876 if (error) {
Dave Chinner1d9025e2012-06-22 18:50:14 +1000877 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700878 return error;
879 }
Dave Chinner1d9025e2012-06-22 18:50:14 +1000880 hdr = dbp->b_addr;
Dave Chinner33363fe2013-04-03 16:11:22 +1100881 bf = xfs_dir3_data_bestfree_p(hdr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700882 grown = 0;
883 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700884 /*
885 * Point to the biggest freespace in our data block.
886 */
887 dup = (xfs_dir2_data_unused_t *)
Dave Chinner33363fe2013-04-03 16:11:22 +1100888 ((char *)hdr + be16_to_cpu(bf[0].offset));
Nathan Scottad354eb2006-03-17 17:27:37 +1100889 ASSERT(be16_to_cpu(dup->length) >= length);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700890 needscan = needlog = 0;
891 /*
892 * Mark the initial part of our freespace in use for the new entry.
893 */
894 xfs_dir2_data_use_free(tp, dbp, dup,
Christoph Hellwigc2066e22011-07-08 14:35:38 +0200895 (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr), length,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700896 &needlog, &needscan);
897 /*
898 * Initialize our new entry (at last).
899 */
900 dep = (xfs_dir2_data_entry_t *)dup;
Christoph Hellwigff9901c2006-06-09 14:48:37 +1000901 dep->inumber = cpu_to_be64(args->inumber);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700902 dep->namelen = args->namelen;
903 memcpy(dep->name, args->name, dep->namelen);
Dave Chinner9d23fc82013-10-29 22:11:48 +1100904 dp->d_ops->data_put_ftype(dep, args->filetype);
905 tagp = dp->d_ops->data_entry_tag_p(dep);
Christoph Hellwigc2066e22011-07-08 14:35:38 +0200906 *tagp = cpu_to_be16((char *)dep - (char *)hdr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700907 /*
908 * Need to scan fix up the bestfree table.
909 */
910 if (needscan)
Dave Chinner9d23fc82013-10-29 22:11:48 +1100911 xfs_dir2_data_freescan(dp, hdr, &needlog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700912 /*
913 * Need to log the data block's header.
914 */
915 if (needlog)
916 xfs_dir2_data_log_header(tp, dbp);
Dave Chinner9d23fc82013-10-29 22:11:48 +1100917 xfs_dir2_data_log_entry(tp, dp, dbp, dep);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700918 /*
919 * If the bests table needs to be changed, do it.
920 * Log the change unless we've already done that.
921 */
Dave Chinner33363fe2013-04-03 16:11:22 +1100922 if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(bf[0].length)) {
923 bestsp[use_block] = bf[0].length;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700924 if (!grown)
Dave Chinner24df33b2013-04-12 07:30:21 +1000925 xfs_dir3_leaf_log_bests(tp, lbp, use_block, use_block);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700926 }
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200927
Dave Chinner24df33b2013-04-12 07:30:21 +1000928 lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale,
Christoph Hellwig4fb44c82011-07-08 14:34:59 +0200929 highstale, &lfloglow, &lfloghigh);
930
Linus Torvalds1da177e2005-04-16 15:20:36 -0700931 /*
932 * Fill in the new leaf entry.
933 */
Nathan Scott3c1f9c12006-03-17 17:28:18 +1100934 lep->hashval = cpu_to_be32(args->hashval);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +1000935 lep->address = cpu_to_be32(xfs_dir2_db_off_to_dataptr(mp, use_block,
Nathan Scott3d693c62006-03-17 17:28:27 +1100936 be16_to_cpu(*tagp)));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700937 /*
938 * Log the leaf fields and give up the buffers.
939 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000940 xfs_dir3_leaf_hdr_to_disk(leaf, &leafhdr);
941 xfs_dir3_leaf_log_header(tp, lbp);
942 xfs_dir3_leaf_log_ents(tp, lbp, lfloglow, lfloghigh);
943 xfs_dir3_leaf_check(mp, lbp);
Dave Chinner33363fe2013-04-03 16:11:22 +1100944 xfs_dir3_data_check(dp, dbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700945 return 0;
946}
947
Linus Torvalds1da177e2005-04-16 15:20:36 -0700948/*
949 * Compact out any stale entries in the leaf.
950 * Log the header and changed leaf entries, if any.
951 */
952void
Dave Chinner24df33b2013-04-12 07:30:21 +1000953xfs_dir3_leaf_compact(
Linus Torvalds1da177e2005-04-16 15:20:36 -0700954 xfs_da_args_t *args, /* operation arguments */
Dave Chinner24df33b2013-04-12 07:30:21 +1000955 struct xfs_dir3_icleaf_hdr *leafhdr,
Dave Chinner1d9025e2012-06-22 18:50:14 +1000956 struct xfs_buf *bp) /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700957{
958 int from; /* source leaf index */
959 xfs_dir2_leaf_t *leaf; /* leaf structure */
960 int loglow; /* first leaf entry to log */
961 int to; /* target leaf index */
Dave Chinner24df33b2013-04-12 07:30:21 +1000962 struct xfs_dir2_leaf_entry *ents;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700963
Dave Chinner1d9025e2012-06-22 18:50:14 +1000964 leaf = bp->b_addr;
Dave Chinner24df33b2013-04-12 07:30:21 +1000965 if (!leafhdr->stale)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700966 return;
Dave Chinner24df33b2013-04-12 07:30:21 +1000967
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968 /*
969 * Compress out the stale entries in place.
970 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000971 ents = xfs_dir3_leaf_ents_p(leaf);
972 for (from = to = 0, loglow = -1; from < leafhdr->count; from++) {
973 if (ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700974 continue;
975 /*
976 * Only actually copy the entries that are different.
977 */
978 if (from > to) {
979 if (loglow == -1)
980 loglow = to;
Dave Chinner24df33b2013-04-12 07:30:21 +1000981 ents[to] = ents[from];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700982 }
983 to++;
984 }
985 /*
986 * Update and log the header, log the leaf entries.
987 */
Dave Chinner24df33b2013-04-12 07:30:21 +1000988 ASSERT(leafhdr->stale == from - to);
989 leafhdr->count -= leafhdr->stale;
990 leafhdr->stale = 0;
991
992 xfs_dir3_leaf_hdr_to_disk(leaf, leafhdr);
993 xfs_dir3_leaf_log_header(args->trans, bp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700994 if (loglow != -1)
Dave Chinner24df33b2013-04-12 07:30:21 +1000995 xfs_dir3_leaf_log_ents(args->trans, bp, loglow, to - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700996}
997
998/*
999 * Compact the leaf entries, removing stale ones.
1000 * Leave one stale entry behind - the one closest to our
1001 * insertion index - and the caller will shift that one to our insertion
1002 * point later.
1003 * Return new insertion index, where the remaining stale entry is,
1004 * and leaf logging indices.
1005 */
1006void
Dave Chinner24df33b2013-04-12 07:30:21 +10001007xfs_dir3_leaf_compact_x1(
1008 struct xfs_dir3_icleaf_hdr *leafhdr,
1009 struct xfs_dir2_leaf_entry *ents,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001010 int *indexp, /* insertion index */
1011 int *lowstalep, /* out: stale entry before us */
1012 int *highstalep, /* out: stale entry after us */
1013 int *lowlogp, /* out: low log index */
1014 int *highlogp) /* out: high log index */
1015{
1016 int from; /* source copy index */
1017 int highstale; /* stale entry at/after index */
1018 int index; /* insertion index */
1019 int keepstale; /* source index of kept stale */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001020 int lowstale; /* stale entry before index */
1021 int newindex=0; /* new insertion index */
1022 int to; /* destination copy index */
1023
Dave Chinner24df33b2013-04-12 07:30:21 +10001024 ASSERT(leafhdr->stale > 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001025 index = *indexp;
Christoph Hellwiga230a1d2011-07-13 13:43:48 +02001026
Dave Chinner24df33b2013-04-12 07:30:21 +10001027 xfs_dir3_leaf_find_stale(leafhdr, ents, index, &lowstale, &highstale);
Christoph Hellwiga230a1d2011-07-13 13:43:48 +02001028
Linus Torvalds1da177e2005-04-16 15:20:36 -07001029 /*
1030 * Pick the better of lowstale and highstale.
1031 */
1032 if (lowstale >= 0 &&
Dave Chinner24df33b2013-04-12 07:30:21 +10001033 (highstale == leafhdr->count ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001034 index - lowstale <= highstale - index))
1035 keepstale = lowstale;
1036 else
1037 keepstale = highstale;
1038 /*
1039 * Copy the entries in place, removing all the stale entries
1040 * except keepstale.
1041 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001042 for (from = to = 0; from < leafhdr->count; from++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001043 /*
1044 * Notice the new value of index.
1045 */
1046 if (index == from)
1047 newindex = to;
1048 if (from != keepstale &&
Dave Chinner24df33b2013-04-12 07:30:21 +10001049 ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001050 if (from == to)
1051 *lowlogp = to;
1052 continue;
1053 }
1054 /*
1055 * Record the new keepstale value for the insertion.
1056 */
1057 if (from == keepstale)
1058 lowstale = highstale = to;
1059 /*
1060 * Copy only the entries that have moved.
1061 */
1062 if (from > to)
Dave Chinner24df33b2013-04-12 07:30:21 +10001063 ents[to] = ents[from];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001064 to++;
1065 }
1066 ASSERT(from > to);
1067 /*
1068 * If the insertion point was past the last entry,
1069 * set the new insertion point accordingly.
1070 */
1071 if (index == from)
1072 newindex = to;
1073 *indexp = newindex;
1074 /*
1075 * Adjust the leaf header values.
1076 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001077 leafhdr->count -= from - to;
1078 leafhdr->stale = 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001079 /*
1080 * Remember the low/high stale value only in the "right"
1081 * direction.
1082 */
1083 if (lowstale >= newindex)
1084 lowstale = -1;
1085 else
Dave Chinner24df33b2013-04-12 07:30:21 +10001086 highstale = leafhdr->count;
1087 *highlogp = leafhdr->count - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001088 *lowstalep = lowstale;
1089 *highstalep = highstale;
1090}
1091
Linus Torvalds1da177e2005-04-16 15:20:36 -07001092/*
1093 * Log the bests entries indicated from a leaf1 block.
1094 */
Christoph Hellwigba0f32d2005-06-21 15:36:52 +10001095static void
Dave Chinner24df33b2013-04-12 07:30:21 +10001096xfs_dir3_leaf_log_bests(
Linus Torvalds1da177e2005-04-16 15:20:36 -07001097 xfs_trans_t *tp, /* transaction pointer */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001098 struct xfs_buf *bp, /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001099 int first, /* first entry to log */
1100 int last) /* last entry to log */
1101{
Nathan Scott68b3a102006-03-17 17:27:19 +11001102 __be16 *firstb; /* pointer to first entry */
1103 __be16 *lastb; /* pointer to last entry */
Dave Chinner24df33b2013-04-12 07:30:21 +10001104 struct xfs_dir2_leaf *leaf = bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001105 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1106
Dave Chinner24df33b2013-04-12 07:30:21 +10001107 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1108 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC));
1109
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001110 ltp = xfs_dir2_leaf_tail_p(tp->t_mountp, leaf);
1111 firstb = xfs_dir2_leaf_bests_p(ltp) + first;
1112 lastb = xfs_dir2_leaf_bests_p(ltp) + last;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001113 xfs_trans_log_buf(tp, bp, (uint)((char *)firstb - (char *)leaf),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001114 (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
1115}
1116
1117/*
1118 * Log the leaf entries indicated from a leaf1 or leafn block.
1119 */
1120void
Dave Chinner24df33b2013-04-12 07:30:21 +10001121xfs_dir3_leaf_log_ents(
Linus Torvalds1da177e2005-04-16 15:20:36 -07001122 xfs_trans_t *tp, /* transaction pointer */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001123 struct xfs_buf *bp, /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001124 int first, /* first entry to log */
1125 int last) /* last entry to log */
1126{
1127 xfs_dir2_leaf_entry_t *firstlep; /* pointer to first entry */
1128 xfs_dir2_leaf_entry_t *lastlep; /* pointer to last entry */
Dave Chinner24df33b2013-04-12 07:30:21 +10001129 struct xfs_dir2_leaf *leaf = bp->b_addr;
1130 struct xfs_dir2_leaf_entry *ents;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001131
Christoph Hellwig69ef9212011-07-08 14:36:05 +02001132 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
Dave Chinner24df33b2013-04-12 07:30:21 +10001133 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1134 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1135 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1136
1137 ents = xfs_dir3_leaf_ents_p(leaf);
1138 firstlep = &ents[first];
1139 lastlep = &ents[last];
Dave Chinner1d9025e2012-06-22 18:50:14 +10001140 xfs_trans_log_buf(tp, bp, (uint)((char *)firstlep - (char *)leaf),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001141 (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
1142}
1143
1144/*
1145 * Log the header of the leaf1 or leafn block.
1146 */
1147void
Dave Chinner24df33b2013-04-12 07:30:21 +10001148xfs_dir3_leaf_log_header(
Dave Chinner1d9025e2012-06-22 18:50:14 +10001149 struct xfs_trans *tp,
1150 struct xfs_buf *bp)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001151{
Dave Chinner24df33b2013-04-12 07:30:21 +10001152 struct xfs_dir2_leaf *leaf = bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001153
Christoph Hellwig69ef9212011-07-08 14:36:05 +02001154 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
Dave Chinner24df33b2013-04-12 07:30:21 +10001155 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1156 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1157 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1158
Dave Chinner1d9025e2012-06-22 18:50:14 +10001159 xfs_trans_log_buf(tp, bp, (uint)((char *)&leaf->hdr - (char *)leaf),
Dave Chinner24df33b2013-04-12 07:30:21 +10001160 xfs_dir3_leaf_hdr_size(leaf) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001161}
1162
1163/*
1164 * Log the tail of the leaf1 block.
1165 */
Christoph Hellwigba0f32d2005-06-21 15:36:52 +10001166STATIC void
Dave Chinner24df33b2013-04-12 07:30:21 +10001167xfs_dir3_leaf_log_tail(
Dave Chinner1d9025e2012-06-22 18:50:14 +10001168 struct xfs_trans *tp,
1169 struct xfs_buf *bp)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001170{
Dave Chinner24df33b2013-04-12 07:30:21 +10001171 struct xfs_dir2_leaf *leaf = bp->b_addr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001172 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
Dave Chinner24df33b2013-04-12 07:30:21 +10001173 struct xfs_mount *mp = tp->t_mountp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001174
Dave Chinner24df33b2013-04-12 07:30:21 +10001175 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
1176 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
1177 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
1178 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
1179
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001180 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001181 xfs_trans_log_buf(tp, bp, (uint)((char *)ltp - (char *)leaf),
Linus Torvalds1da177e2005-04-16 15:20:36 -07001182 (uint)(mp->m_dirblksize - 1));
1183}
1184
1185/*
1186 * Look up the entry referred to by args in the leaf format directory.
1187 * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
1188 * is also used by the node-format code.
1189 */
1190int
1191xfs_dir2_leaf_lookup(
1192 xfs_da_args_t *args) /* operation arguments */
1193{
Dave Chinner1d9025e2012-06-22 18:50:14 +10001194 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001195 xfs_dir2_data_entry_t *dep; /* data block entry */
1196 xfs_inode_t *dp; /* incore directory inode */
1197 int error; /* error return code */
1198 int index; /* found entry index */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001199 struct xfs_buf *lbp; /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001200 xfs_dir2_leaf_t *leaf; /* leaf structure */
1201 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1202 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner24df33b2013-04-12 07:30:21 +10001203 struct xfs_dir2_leaf_entry *ents;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001204
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001205 trace_xfs_dir2_leaf_lookup(args);
1206
Linus Torvalds1da177e2005-04-16 15:20:36 -07001207 /*
1208 * Look up name in the leaf block, returning both buffers and index.
1209 */
1210 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1211 return error;
1212 }
1213 tp = args->trans;
1214 dp = args->dp;
Dave Chinner24df33b2013-04-12 07:30:21 +10001215 xfs_dir3_leaf_check(dp->i_mount, lbp);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001216 leaf = lbp->b_addr;
Dave Chinner24df33b2013-04-12 07:30:21 +10001217 ents = xfs_dir3_leaf_ents_p(leaf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001218 /*
1219 * Get to the leaf entry and contained data entry address.
1220 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001221 lep = &ents[index];
1222
Linus Torvalds1da177e2005-04-16 15:20:36 -07001223 /*
1224 * Point to the data entry.
1225 */
1226 dep = (xfs_dir2_data_entry_t *)
Dave Chinner1d9025e2012-06-22 18:50:14 +10001227 ((char *)dbp->b_addr +
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001228 xfs_dir2_dataptr_to_off(dp->i_mount, be32_to_cpu(lep->address)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001229 /*
Barry Naujok384f3ce2008-05-21 16:58:22 +10001230 * Return the found inode number & CI name if appropriate
Linus Torvalds1da177e2005-04-16 15:20:36 -07001231 */
Christoph Hellwigff9901c2006-06-09 14:48:37 +10001232 args->inumber = be64_to_cpu(dep->inumber);
Dave Chinner9d23fc82013-10-29 22:11:48 +11001233 args->filetype = dp->d_ops->data_get_ftype(dep);
Barry Naujok384f3ce2008-05-21 16:58:22 +10001234 error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001235 xfs_trans_brelse(tp, dbp);
1236 xfs_trans_brelse(tp, lbp);
Barry Naujok384f3ce2008-05-21 16:58:22 +10001237 return XFS_ERROR(error);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001238}
1239
1240/*
1241 * Look up name/hash in the leaf block.
1242 * Fill in indexp with the found index, and dbpp with the data buffer.
1243 * If not found dbpp will be NULL, and ENOENT comes back.
1244 * lbpp will always be filled in with the leaf buffer unless there's an error.
1245 */
1246static int /* error */
1247xfs_dir2_leaf_lookup_int(
1248 xfs_da_args_t *args, /* operation arguments */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001249 struct xfs_buf **lbpp, /* out: leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001250 int *indexp, /* out: index in leaf block */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001251 struct xfs_buf **dbpp) /* out: data buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252{
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001253 xfs_dir2_db_t curdb = -1; /* current data block number */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001254 struct xfs_buf *dbp = NULL; /* data buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001255 xfs_dir2_data_entry_t *dep; /* data entry */
1256 xfs_inode_t *dp; /* incore directory inode */
1257 int error; /* error return code */
1258 int index; /* index in leaf block */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001259 struct xfs_buf *lbp; /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001260 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1261 xfs_dir2_leaf_t *leaf; /* leaf structure */
1262 xfs_mount_t *mp; /* filesystem mount point */
1263 xfs_dir2_db_t newdb; /* new data block number */
1264 xfs_trans_t *tp; /* transaction pointer */
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001265 xfs_dir2_db_t cidb = -1; /* case match data block no. */
Barry Naujok5163f952008-05-21 16:41:01 +10001266 enum xfs_dacmp cmp; /* name compare result */
Dave Chinner24df33b2013-04-12 07:30:21 +10001267 struct xfs_dir2_leaf_entry *ents;
1268 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001269
1270 dp = args->dp;
1271 tp = args->trans;
1272 mp = dp->i_mount;
Dave Chinnere6f76672012-11-12 22:54:15 +11001273
Dave Chinner24df33b2013-04-12 07:30:21 +10001274 error = xfs_dir3_leaf_read(tp, dp, mp->m_dirleafblk, -1, &lbp);
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001275 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001276 return error;
Dave Chinnere6f76672012-11-12 22:54:15 +11001277
Linus Torvalds1da177e2005-04-16 15:20:36 -07001278 *lbpp = lbp;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001279 leaf = lbp->b_addr;
Dave Chinner24df33b2013-04-12 07:30:21 +10001280 xfs_dir3_leaf_check(mp, lbp);
1281 ents = xfs_dir3_leaf_ents_p(leaf);
1282 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
1283
Linus Torvalds1da177e2005-04-16 15:20:36 -07001284 /*
1285 * Look for the first leaf entry with our hash value.
1286 */
1287 index = xfs_dir2_leaf_search_hash(args, lbp);
1288 /*
1289 * Loop over all the entries with the right hash value
1290 * looking to match the name.
1291 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001292 for (lep = &ents[index];
1293 index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
1294 lep++, index++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001295 /*
1296 * Skip over stale leaf entries.
1297 */
Nathan Scott3c1f9c12006-03-17 17:28:18 +11001298 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299 continue;
1300 /*
1301 * Get the new data block number.
1302 */
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001303 newdb = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001304 /*
1305 * If it's not the same as the old data block number,
1306 * need to pitch the old one and read the new one.
1307 */
1308 if (newdb != curdb) {
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001309 if (dbp)
Dave Chinner1d9025e2012-06-22 18:50:14 +10001310 xfs_trans_brelse(tp, dbp);
Dave Chinner33363fe2013-04-03 16:11:22 +11001311 error = xfs_dir3_data_read(tp, dp,
Dave Chinnere4813572012-11-12 22:54:14 +11001312 xfs_dir2_db_to_da(mp, newdb),
1313 -1, &dbp);
Barry Naujok5163f952008-05-21 16:41:01 +10001314 if (error) {
Dave Chinner1d9025e2012-06-22 18:50:14 +10001315 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001316 return error;
1317 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001318 curdb = newdb;
1319 }
1320 /*
1321 * Point to the data entry.
1322 */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001323 dep = (xfs_dir2_data_entry_t *)((char *)dbp->b_addr +
Barry Naujok5163f952008-05-21 16:41:01 +10001324 xfs_dir2_dataptr_to_off(mp, be32_to_cpu(lep->address)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001325 /*
Barry Naujok5163f952008-05-21 16:41:01 +10001326 * Compare name and if it's an exact match, return the index
1327 * and buffer. If it's the first case-insensitive match, store
1328 * the index and buffer and continue looking for an exact match.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001329 */
Barry Naujok5163f952008-05-21 16:41:01 +10001330 cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
1331 if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
1332 args->cmpresult = cmp;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001333 *indexp = index;
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001334 /* case exact match: return the current buffer. */
Barry Naujok5163f952008-05-21 16:41:01 +10001335 if (cmp == XFS_CMP_EXACT) {
Barry Naujok5163f952008-05-21 16:41:01 +10001336 *dbpp = dbp;
1337 return 0;
1338 }
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001339 cidb = curdb;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001340 }
1341 }
Barry Naujok6a178102008-05-21 16:42:05 +10001342 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
Barry Naujok5163f952008-05-21 16:41:01 +10001343 /*
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001344 * Here, we can only be doing a lookup (not a rename or remove).
1345 * If a case-insensitive match was found earlier, re-read the
1346 * appropriate data block if required and return it.
Barry Naujok5163f952008-05-21 16:41:01 +10001347 */
1348 if (args->cmpresult == XFS_CMP_CASE) {
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001349 ASSERT(cidb != -1);
1350 if (cidb != curdb) {
Dave Chinner1d9025e2012-06-22 18:50:14 +10001351 xfs_trans_brelse(tp, dbp);
Dave Chinner33363fe2013-04-03 16:11:22 +11001352 error = xfs_dir3_data_read(tp, dp,
Dave Chinnere4813572012-11-12 22:54:14 +11001353 xfs_dir2_db_to_da(mp, cidb),
1354 -1, &dbp);
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001355 if (error) {
Dave Chinner1d9025e2012-06-22 18:50:14 +10001356 xfs_trans_brelse(tp, lbp);
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001357 return error;
1358 }
1359 }
1360 *dbpp = dbp;
Barry Naujok5163f952008-05-21 16:41:01 +10001361 return 0;
1362 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001363 /*
1364 * No match found, return ENOENT.
1365 */
Barry Naujok07fe4dd2008-06-27 13:32:11 +10001366 ASSERT(cidb == -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001367 if (dbp)
Dave Chinner1d9025e2012-06-22 18:50:14 +10001368 xfs_trans_brelse(tp, dbp);
1369 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001370 return XFS_ERROR(ENOENT);
1371}
1372
1373/*
1374 * Remove an entry from a leaf format directory.
1375 */
1376int /* error */
1377xfs_dir2_leaf_removename(
1378 xfs_da_args_t *args) /* operation arguments */
1379{
Nathan Scott68b3a102006-03-17 17:27:19 +11001380 __be16 *bestsp; /* leaf block best freespace */
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001381 xfs_dir2_data_hdr_t *hdr; /* data block header */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001382 xfs_dir2_db_t db; /* data block number */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001383 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001384 xfs_dir2_data_entry_t *dep; /* data entry structure */
1385 xfs_inode_t *dp; /* incore directory inode */
1386 int error; /* error return code */
1387 xfs_dir2_db_t i; /* temporary data block # */
1388 int index; /* index into leaf entries */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001389 struct xfs_buf *lbp; /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001390 xfs_dir2_leaf_t *leaf; /* leaf structure */
1391 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1392 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1393 xfs_mount_t *mp; /* filesystem mount point */
1394 int needlog; /* need to log data header */
1395 int needscan; /* need to rescan data frees */
1396 xfs_dir2_data_off_t oldbest; /* old value of best free */
1397 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner33363fe2013-04-03 16:11:22 +11001398 struct xfs_dir2_data_free *bf; /* bestfree table */
Dave Chinner24df33b2013-04-12 07:30:21 +10001399 struct xfs_dir2_leaf_entry *ents;
1400 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001402 trace_xfs_dir2_leaf_removename(args);
1403
Linus Torvalds1da177e2005-04-16 15:20:36 -07001404 /*
1405 * Lookup the leaf entry, get the leaf and data blocks read in.
1406 */
1407 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1408 return error;
1409 }
1410 dp = args->dp;
1411 tp = args->trans;
1412 mp = dp->i_mount;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001413 leaf = lbp->b_addr;
1414 hdr = dbp->b_addr;
Dave Chinner33363fe2013-04-03 16:11:22 +11001415 xfs_dir3_data_check(dp, dbp);
Dave Chinner24df33b2013-04-12 07:30:21 +10001416 bf = xfs_dir3_data_bestfree_p(hdr);
1417 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
1418 ents = xfs_dir3_leaf_ents_p(leaf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001419 /*
1420 * Point to the leaf entry, use that to point to the data entry.
1421 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001422 lep = &ents[index];
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001423 db = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001424 dep = (xfs_dir2_data_entry_t *)
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001425 ((char *)hdr + xfs_dir2_dataptr_to_off(mp, be32_to_cpu(lep->address)));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001426 needscan = needlog = 0;
Dave Chinner33363fe2013-04-03 16:11:22 +11001427 oldbest = be16_to_cpu(bf[0].length);
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001428 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
1429 bestsp = xfs_dir2_leaf_bests_p(ltp);
Nathan Scott68b3a102006-03-17 17:27:19 +11001430 ASSERT(be16_to_cpu(bestsp[db]) == oldbest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001431 /*
1432 * Mark the former data entry unused.
1433 */
1434 xfs_dir2_data_make_free(tp, dbp,
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001435 (xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),
Dave Chinner9d23fc82013-10-29 22:11:48 +11001436 dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001437 /*
1438 * We just mark the leaf entry stale by putting a null in it.
1439 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001440 leafhdr.stale++;
1441 xfs_dir3_leaf_hdr_to_disk(leaf, &leafhdr);
1442 xfs_dir3_leaf_log_header(tp, lbp);
1443
Nathan Scott3c1f9c12006-03-17 17:28:18 +11001444 lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
Dave Chinner24df33b2013-04-12 07:30:21 +10001445 xfs_dir3_leaf_log_ents(tp, lbp, index, index);
1446
Linus Torvalds1da177e2005-04-16 15:20:36 -07001447 /*
1448 * Scan the freespace in the data block again if necessary,
1449 * log the data block header if necessary.
1450 */
1451 if (needscan)
Dave Chinner9d23fc82013-10-29 22:11:48 +11001452 xfs_dir2_data_freescan(dp, hdr, &needlog);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001453 if (needlog)
1454 xfs_dir2_data_log_header(tp, dbp);
1455 /*
1456 * If the longest freespace in the data block has changed,
1457 * put the new value in the bests table and log that.
1458 */
Dave Chinner33363fe2013-04-03 16:11:22 +11001459 if (be16_to_cpu(bf[0].length) != oldbest) {
1460 bestsp[db] = bf[0].length;
Dave Chinner24df33b2013-04-12 07:30:21 +10001461 xfs_dir3_leaf_log_bests(tp, lbp, db, db);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001462 }
Dave Chinner33363fe2013-04-03 16:11:22 +11001463 xfs_dir3_data_check(dp, dbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001464 /*
1465 * If the data block is now empty then get rid of the data block.
1466 */
Dave Chinner33363fe2013-04-03 16:11:22 +11001467 if (be16_to_cpu(bf[0].length) ==
1468 mp->m_dirblksize - xfs_dir3_data_entry_offset(hdr)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001469 ASSERT(db != mp->m_dirdatablk);
1470 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1471 /*
1472 * Nope, can't get rid of it because it caused
1473 * allocation of a bmap btree block to do so.
1474 * Just go on, returning success, leaving the
1475 * empty block in place.
1476 */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001477 if (error == ENOSPC && args->total == 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001478 error = 0;
Dave Chinner24df33b2013-04-12 07:30:21 +10001479 xfs_dir3_leaf_check(mp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001480 return error;
1481 }
1482 dbp = NULL;
1483 /*
1484 * If this is the last data block then compact the
1485 * bests table by getting rid of entries.
1486 */
Nathan Scottafbcb3f2006-03-17 17:27:28 +11001487 if (db == be32_to_cpu(ltp->bestcount) - 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001488 /*
1489 * Look for the last active entry (i).
1490 */
1491 for (i = db - 1; i > 0; i--) {
Christoph Hellwig69ef9212011-07-08 14:36:05 +02001492 if (bestsp[i] != cpu_to_be16(NULLDATAOFF))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001493 break;
1494 }
1495 /*
1496 * Copy the table down so inactive entries at the
1497 * end are removed.
1498 */
1499 memmove(&bestsp[db - i], bestsp,
Nathan Scottafbcb3f2006-03-17 17:27:28 +11001500 (be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp));
Marcin Slusarz413d57c2008-02-13 15:03:29 -08001501 be32_add_cpu(&ltp->bestcount, -(db - i));
Dave Chinner24df33b2013-04-12 07:30:21 +10001502 xfs_dir3_leaf_log_tail(tp, lbp);
1503 xfs_dir3_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001504 } else
Nathan Scott68b3a102006-03-17 17:27:19 +11001505 bestsp[db] = cpu_to_be16(NULLDATAOFF);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001506 }
1507 /*
1508 * If the data block was not the first one, drop it.
1509 */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001510 else if (db != mp->m_dirdatablk)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001511 dbp = NULL;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001512
Dave Chinner24df33b2013-04-12 07:30:21 +10001513 xfs_dir3_leaf_check(mp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001514 /*
1515 * See if we can convert to block form.
1516 */
1517 return xfs_dir2_leaf_to_block(args, lbp, dbp);
1518}
1519
1520/*
1521 * Replace the inode number in a leaf format directory entry.
1522 */
1523int /* error */
1524xfs_dir2_leaf_replace(
1525 xfs_da_args_t *args) /* operation arguments */
1526{
Dave Chinner1d9025e2012-06-22 18:50:14 +10001527 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001528 xfs_dir2_data_entry_t *dep; /* data block entry */
1529 xfs_inode_t *dp; /* incore directory inode */
1530 int error; /* error return code */
1531 int index; /* index of leaf entry */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001532 struct xfs_buf *lbp; /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001533 xfs_dir2_leaf_t *leaf; /* leaf structure */
1534 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1535 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner24df33b2013-04-12 07:30:21 +10001536 struct xfs_dir2_leaf_entry *ents;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001537
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001538 trace_xfs_dir2_leaf_replace(args);
1539
Linus Torvalds1da177e2005-04-16 15:20:36 -07001540 /*
1541 * Look up the entry.
1542 */
1543 if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
1544 return error;
1545 }
1546 dp = args->dp;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001547 leaf = lbp->b_addr;
Dave Chinner24df33b2013-04-12 07:30:21 +10001548 ents = xfs_dir3_leaf_ents_p(leaf);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001549 /*
1550 * Point to the leaf entry, get data address from it.
1551 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001552 lep = &ents[index];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001553 /*
1554 * Point to the data entry.
1555 */
1556 dep = (xfs_dir2_data_entry_t *)
Dave Chinner1d9025e2012-06-22 18:50:14 +10001557 ((char *)dbp->b_addr +
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001558 xfs_dir2_dataptr_to_off(dp->i_mount, be32_to_cpu(lep->address)));
Christoph Hellwigff9901c2006-06-09 14:48:37 +10001559 ASSERT(args->inumber != be64_to_cpu(dep->inumber));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001560 /*
1561 * Put the new inode number in, log it.
1562 */
Christoph Hellwigff9901c2006-06-09 14:48:37 +10001563 dep->inumber = cpu_to_be64(args->inumber);
Dave Chinner9d23fc82013-10-29 22:11:48 +11001564 dp->d_ops->data_put_ftype(dep, args->filetype);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001565 tp = args->trans;
Dave Chinner9d23fc82013-10-29 22:11:48 +11001566 xfs_dir2_data_log_entry(tp, dp, dbp, dep);
Dave Chinner24df33b2013-04-12 07:30:21 +10001567 xfs_dir3_leaf_check(dp->i_mount, lbp);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001568 xfs_trans_brelse(tp, lbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001569 return 0;
1570}
1571
1572/*
1573 * Return index in the leaf block (lbp) which is either the first
1574 * one with this hash value, or if there are none, the insert point
1575 * for that hash value.
1576 */
1577int /* index value */
1578xfs_dir2_leaf_search_hash(
1579 xfs_da_args_t *args, /* operation arguments */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001580 struct xfs_buf *lbp) /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001581{
1582 xfs_dahash_t hash=0; /* hash from this entry */
1583 xfs_dahash_t hashwant; /* hash value looking for */
1584 int high; /* high leaf index */
1585 int low; /* low leaf index */
1586 xfs_dir2_leaf_t *leaf; /* leaf structure */
1587 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
1588 int mid=0; /* current leaf index */
Dave Chinner24df33b2013-04-12 07:30:21 +10001589 struct xfs_dir2_leaf_entry *ents;
1590 struct xfs_dir3_icleaf_hdr leafhdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001591
Dave Chinner1d9025e2012-06-22 18:50:14 +10001592 leaf = lbp->b_addr;
Dave Chinner24df33b2013-04-12 07:30:21 +10001593 ents = xfs_dir3_leaf_ents_p(leaf);
1594 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
1595
Linus Torvalds1da177e2005-04-16 15:20:36 -07001596 /*
1597 * Note, the table cannot be empty, so we have to go through the loop.
1598 * Binary search the leaf entries looking for our hash value.
1599 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001600 for (lep = ents, low = 0, high = leafhdr.count - 1,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001601 hashwant = args->hashval;
1602 low <= high; ) {
1603 mid = (low + high) >> 1;
Nathan Scott3c1f9c12006-03-17 17:28:18 +11001604 if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001605 break;
1606 if (hash < hashwant)
1607 low = mid + 1;
1608 else
1609 high = mid - 1;
1610 }
1611 /*
1612 * Found one, back up through all the equal hash values.
1613 */
1614 if (hash == hashwant) {
Nathan Scott3c1f9c12006-03-17 17:28:18 +11001615 while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001616 mid--;
1617 }
1618 }
1619 /*
1620 * Need to point to an entry higher than ours.
1621 */
1622 else if (hash < hashwant)
1623 mid++;
1624 return mid;
1625}
1626
1627/*
1628 * Trim off a trailing data block. We know it's empty since the leaf
1629 * freespace table says so.
1630 */
1631int /* error */
1632xfs_dir2_leaf_trim_data(
1633 xfs_da_args_t *args, /* operation arguments */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001634 struct xfs_buf *lbp, /* leaf buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001635 xfs_dir2_db_t db) /* data block number */
1636{
Nathan Scott68b3a102006-03-17 17:27:19 +11001637 __be16 *bestsp; /* leaf bests table */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001638 struct xfs_buf *dbp; /* data block buffer */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001639 xfs_inode_t *dp; /* incore directory inode */
1640 int error; /* error return value */
1641 xfs_dir2_leaf_t *leaf; /* leaf structure */
1642 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
1643 xfs_mount_t *mp; /* filesystem mount point */
1644 xfs_trans_t *tp; /* transaction pointer */
1645
1646 dp = args->dp;
1647 mp = dp->i_mount;
1648 tp = args->trans;
1649 /*
1650 * Read the offending data block. We need its buffer.
1651 */
Dave Chinner33363fe2013-04-03 16:11:22 +11001652 error = xfs_dir3_data_read(tp, dp, xfs_dir2_db_to_da(mp, db), -1, &dbp);
Dave Chinner4bb20a82012-11-12 22:54:10 +11001653 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001654 return error;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001655
Dave Chinner1d9025e2012-06-22 18:50:14 +10001656 leaf = lbp->b_addr;
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001657 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001658
1659#ifdef DEBUG
1660{
Dave Chinner1d9025e2012-06-22 18:50:14 +10001661 struct xfs_dir2_data_hdr *hdr = dbp->b_addr;
Dave Chinner33363fe2013-04-03 16:11:22 +11001662 struct xfs_dir2_data_free *bf = xfs_dir3_data_bestfree_p(hdr);
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001663
Dave Chinner33363fe2013-04-03 16:11:22 +11001664 ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
1665 hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
1666 ASSERT(be16_to_cpu(bf[0].length) ==
1667 mp->m_dirblksize - xfs_dir3_data_entry_offset(hdr));
Nathan Scottafbcb3f2006-03-17 17:27:28 +11001668 ASSERT(db == be32_to_cpu(ltp->bestcount) - 1);
Christoph Hellwigc2066e22011-07-08 14:35:38 +02001669}
1670#endif
1671
Linus Torvalds1da177e2005-04-16 15:20:36 -07001672 /*
1673 * Get rid of the data block.
1674 */
1675 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
1676 ASSERT(error != ENOSPC);
Dave Chinner1d9025e2012-06-22 18:50:14 +10001677 xfs_trans_brelse(tp, dbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001678 return error;
1679 }
1680 /*
1681 * Eliminate the last bests entry from the table.
1682 */
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001683 bestsp = xfs_dir2_leaf_bests_p(ltp);
Marcin Slusarz413d57c2008-02-13 15:03:29 -08001684 be32_add_cpu(&ltp->bestcount, -1);
Nathan Scottafbcb3f2006-03-17 17:27:28 +11001685 memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp));
Dave Chinner24df33b2013-04-12 07:30:21 +10001686 xfs_dir3_leaf_log_tail(tp, lbp);
1687 xfs_dir3_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001688 return 0;
1689}
1690
Christoph Hellwig22823962011-07-08 14:35:53 +02001691static inline size_t
Dave Chinner24df33b2013-04-12 07:30:21 +10001692xfs_dir3_leaf_size(
1693 struct xfs_dir3_icleaf_hdr *hdr,
Christoph Hellwig22823962011-07-08 14:35:53 +02001694 int counts)
1695{
Dave Chinner24df33b2013-04-12 07:30:21 +10001696 int entries;
1697 int hdrsize;
Christoph Hellwig22823962011-07-08 14:35:53 +02001698
Dave Chinner24df33b2013-04-12 07:30:21 +10001699 entries = hdr->count - hdr->stale;
1700 if (hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
1701 hdr->magic == XFS_DIR2_LEAFN_MAGIC)
1702 hdrsize = sizeof(struct xfs_dir2_leaf_hdr);
1703 else
1704 hdrsize = sizeof(struct xfs_dir3_leaf_hdr);
1705
1706 return hdrsize + entries * sizeof(xfs_dir2_leaf_entry_t)
1707 + counts * sizeof(xfs_dir2_data_off_t)
1708 + sizeof(xfs_dir2_leaf_tail_t);
Christoph Hellwig22823962011-07-08 14:35:53 +02001709}
1710
Linus Torvalds1da177e2005-04-16 15:20:36 -07001711/*
1712 * Convert node form directory to leaf form directory.
1713 * The root of the node form dir needs to already be a LEAFN block.
1714 * Just return if we can't do anything.
1715 */
1716int /* error */
1717xfs_dir2_node_to_leaf(
1718 xfs_da_state_t *state) /* directory operation state */
1719{
1720 xfs_da_args_t *args; /* operation arguments */
1721 xfs_inode_t *dp; /* incore directory inode */
1722 int error; /* error return code */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001723 struct xfs_buf *fbp; /* buffer for freespace block */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001724 xfs_fileoff_t fo; /* freespace file offset */
1725 xfs_dir2_free_t *free; /* freespace structure */
Dave Chinner1d9025e2012-06-22 18:50:14 +10001726 struct xfs_buf *lbp; /* buffer for leaf block */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001727 xfs_dir2_leaf_tail_t *ltp; /* tail of leaf structure */
1728 xfs_dir2_leaf_t *leaf; /* leaf structure */
1729 xfs_mount_t *mp; /* filesystem mount point */
1730 int rval; /* successful free trim? */
1731 xfs_trans_t *tp; /* transaction pointer */
Dave Chinner24df33b2013-04-12 07:30:21 +10001732 struct xfs_dir3_icleaf_hdr leafhdr;
Dave Chinnercbc8adf2013-04-03 16:11:21 +11001733 struct xfs_dir3_icfree_hdr freehdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001734
1735 /*
1736 * There's more than a leaf level in the btree, so there must
1737 * be multiple leafn blocks. Give up.
1738 */
1739 if (state->path.active > 1)
1740 return 0;
1741 args = state->args;
Christoph Hellwig0b1b2132009-12-14 23:14:59 +00001742
1743 trace_xfs_dir2_node_to_leaf(args);
1744
Linus Torvalds1da177e2005-04-16 15:20:36 -07001745 mp = state->mp;
1746 dp = args->dp;
1747 tp = args->trans;
1748 /*
1749 * Get the last offset in the file.
1750 */
1751 if ((error = xfs_bmap_last_offset(tp, dp, &fo, XFS_DATA_FORK))) {
1752 return error;
1753 }
1754 fo -= mp->m_dirblkfsbs;
1755 /*
1756 * If there are freespace blocks other than the first one,
1757 * take this opportunity to remove trailing empty freespace blocks
1758 * that may have been left behind during no-space-reservation
1759 * operations.
1760 */
1761 while (fo > mp->m_dirfreeblk) {
1762 if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
1763 return error;
1764 }
1765 if (rval)
1766 fo -= mp->m_dirblkfsbs;
1767 else
1768 return 0;
1769 }
1770 /*
1771 * Now find the block just before the freespace block.
1772 */
1773 if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
1774 return error;
1775 }
1776 /*
1777 * If it's not the single leaf block, give up.
1778 */
1779 if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + mp->m_dirblksize)
1780 return 0;
1781 lbp = state->path.blk[0].bp;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001782 leaf = lbp->b_addr;
Dave Chinner24df33b2013-04-12 07:30:21 +10001783 xfs_dir3_leaf_hdr_from_disk(&leafhdr, leaf);
1784
1785 ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
1786 leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
1787
Linus Torvalds1da177e2005-04-16 15:20:36 -07001788 /*
1789 * Read the freespace block.
1790 */
Dave Chinner20252072012-11-12 22:54:13 +11001791 error = xfs_dir2_free_read(tp, dp, mp->m_dirfreeblk, &fbp);
Dave Chinner4bb20a82012-11-12 22:54:10 +11001792 if (error)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001793 return error;
Dave Chinner1d9025e2012-06-22 18:50:14 +10001794 free = fbp->b_addr;
Dave Chinnercbc8adf2013-04-03 16:11:21 +11001795 xfs_dir3_free_hdr_from_disk(&freehdr, free);
1796
1797 ASSERT(!freehdr.firstdb);
Christoph Hellwig22823962011-07-08 14:35:53 +02001798
Linus Torvalds1da177e2005-04-16 15:20:36 -07001799 /*
1800 * Now see if the leafn and free data will fit in a leaf1.
1801 * If not, release the buffer and give up.
1802 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001803 if (xfs_dir3_leaf_size(&leafhdr, freehdr.nvalid) > mp->m_dirblksize) {
Dave Chinner1d9025e2012-06-22 18:50:14 +10001804 xfs_trans_brelse(tp, fbp);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001805 return 0;
1806 }
Christoph Hellwig22823962011-07-08 14:35:53 +02001807
Linus Torvalds1da177e2005-04-16 15:20:36 -07001808 /*
1809 * If the leaf has any stale entries in it, compress them out.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001810 */
Dave Chinner24df33b2013-04-12 07:30:21 +10001811 if (leafhdr.stale)
1812 xfs_dir3_leaf_compact(args, &leafhdr, lbp);
Dave Chinnerb0f539d2012-11-14 17:53:49 +11001813
Dave Chinner24df33b2013-04-12 07:30:21 +10001814 lbp->b_ops = &xfs_dir3_leaf1_buf_ops;
Dave Chinner61fe1352013-04-03 16:11:30 +11001815 xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAF1_BUF);
Dave Chinner24df33b2013-04-12 07:30:21 +10001816 leafhdr.magic = (leafhdr.magic == XFS_DIR2_LEAFN_MAGIC)
1817 ? XFS_DIR2_LEAF1_MAGIC
1818 : XFS_DIR3_LEAF1_MAGIC;
Dave Chinnerb0f539d2012-11-14 17:53:49 +11001819
Linus Torvalds1da177e2005-04-16 15:20:36 -07001820 /*
1821 * Set up the leaf tail from the freespace block.
1822 */
Christoph Hellwigbbaaf532007-06-28 16:43:50 +10001823 ltp = xfs_dir2_leaf_tail_p(mp, leaf);
Dave Chinnercbc8adf2013-04-03 16:11:21 +11001824 ltp->bestcount = cpu_to_be32(freehdr.nvalid);
Dave Chinner24df33b2013-04-12 07:30:21 +10001825
Linus Torvalds1da177e2005-04-16 15:20:36 -07001826 /*
1827 * Set up the leaf bests table.
1828 */
Dave Chinnercbc8adf2013-04-03 16:11:21 +11001829 memcpy(xfs_dir2_leaf_bests_p(ltp), xfs_dir3_free_bests_p(mp, free),
1830 freehdr.nvalid * sizeof(xfs_dir2_data_off_t));
Dave Chinner24df33b2013-04-12 07:30:21 +10001831
1832 xfs_dir3_leaf_hdr_to_disk(leaf, &leafhdr);
1833 xfs_dir3_leaf_log_header(tp, lbp);
1834 xfs_dir3_leaf_log_bests(tp, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
1835 xfs_dir3_leaf_log_tail(tp, lbp);
1836 xfs_dir3_leaf_check(mp, lbp);
1837
Linus Torvalds1da177e2005-04-16 15:20:36 -07001838 /*
1839 * Get rid of the freespace block.
1840 */
1841 error = xfs_dir2_shrink_inode(args, XFS_DIR2_FREE_FIRSTDB(mp), fbp);
1842 if (error) {
1843 /*
1844 * This can't fail here because it can only happen when
1845 * punching out the middle of an extent, and this is an
1846 * isolated block.
1847 */
1848 ASSERT(error != ENOSPC);
1849 return error;
1850 }
1851 fbp = NULL;
1852 /*
1853 * Now see if we can convert the single-leaf directory
1854 * down to a block form directory.
1855 * This routine always kills the dabuf for the leaf, so
1856 * eliminate it from the path.
1857 */
1858 error = xfs_dir2_leaf_to_block(args, lbp, NULL);
1859 state->path.blk[0].bp = NULL;
1860 return error;
1861}