blob: 40e4a2e2776551d4484e672e5a237f0ba4a6a03f [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
Nathan Scott7b718762005-11-02 14:58:39 +11002 * Copyright (c) 2000-2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
Linus Torvalds1da177e2005-04-16 15:20:36 -07004 *
Nathan Scott7b718762005-11-02 14:58:39 +11005 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
Linus Torvalds1da177e2005-04-16 15:20:36 -07007 * published by the Free Software Foundation.
8 *
Nathan Scott7b718762005-11-02 14:58:39 +11009 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
Linus Torvalds1da177e2005-04-16 15:20:36 -070013 *
Nathan Scott7b718762005-11-02 14:58:39 +110014 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Linus Torvalds1da177e2005-04-16 15:20:36 -070017 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#include "xfs.h"
Nathan Scotta844f452005-11-02 14:38:42 +110019#include "xfs_fs.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070020#include "xfs_types.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070021#include "xfs_log.h"
Nathan Scotta844f452005-11-02 14:38:42 +110022#include "xfs_inum.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070023#include "xfs_trans.h"
24#include "xfs_sb.h"
25#include "xfs_dir.h"
26#include "xfs_dir2.h"
27#include "xfs_dmapi.h"
28#include "xfs_mount.h"
Nathan Scotta844f452005-11-02 14:38:42 +110029#include "xfs_da_btree.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070030#include "xfs_bmap_btree.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070031#include "xfs_dir_sf.h"
32#include "xfs_dir2_sf.h"
Nathan Scotta844f452005-11-02 14:38:42 +110033#include "xfs_attr_sf.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070034#include "xfs_dinode.h"
35#include "xfs_inode.h"
36#include "xfs_bmap.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070037#include "xfs_dir2_data.h"
38#include "xfs_dir2_leaf.h"
39#include "xfs_dir2_block.h"
40#include "xfs_dir2_node.h"
41#include "xfs_dir2_trace.h"
42#include "xfs_error.h"
43
44/*
45 * Function declarations.
46 */
47static void xfs_dir2_free_log_header(xfs_trans_t *tp, xfs_dabuf_t *bp);
48static int xfs_dir2_leafn_add(xfs_dabuf_t *bp, xfs_da_args_t *args, int index);
49#ifdef DEBUG
50static void xfs_dir2_leafn_check(xfs_inode_t *dp, xfs_dabuf_t *bp);
51#else
52#define xfs_dir2_leafn_check(dp, bp)
53#endif
54static void xfs_dir2_leafn_moveents(xfs_da_args_t *args, xfs_dabuf_t *bp_s,
55 int start_s, xfs_dabuf_t *bp_d, int start_d,
56 int count);
57static void xfs_dir2_leafn_rebalance(xfs_da_state_t *state,
58 xfs_da_state_blk_t *blk1,
59 xfs_da_state_blk_t *blk2);
60static int xfs_dir2_leafn_remove(xfs_da_args_t *args, xfs_dabuf_t *bp,
61 int index, xfs_da_state_blk_t *dblk,
62 int *rval);
63static int xfs_dir2_node_addname_int(xfs_da_args_t *args,
64 xfs_da_state_blk_t *fblk);
65
66/*
67 * Log entries from a freespace block.
68 */
69void
70xfs_dir2_free_log_bests(
71 xfs_trans_t *tp, /* transaction pointer */
72 xfs_dabuf_t *bp, /* freespace buffer */
73 int first, /* first entry to log */
74 int last) /* last entry to log */
75{
76 xfs_dir2_free_t *free; /* freespace structure */
77
78 free = bp->data;
Nathan Scott0ba962e2006-03-17 17:27:07 +110079 ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -070080 xfs_da_log_buf(tp, bp,
81 (uint)((char *)&free->bests[first] - (char *)free),
82 (uint)((char *)&free->bests[last] - (char *)free +
83 sizeof(free->bests[0]) - 1));
84}
85
86/*
87 * Log header from a freespace block.
88 */
89static void
90xfs_dir2_free_log_header(
91 xfs_trans_t *tp, /* transaction pointer */
92 xfs_dabuf_t *bp) /* freespace buffer */
93{
94 xfs_dir2_free_t *free; /* freespace structure */
95
96 free = bp->data;
Nathan Scott0ba962e2006-03-17 17:27:07 +110097 ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -070098 xfs_da_log_buf(tp, bp, (uint)((char *)&free->hdr - (char *)free),
99 (uint)(sizeof(xfs_dir2_free_hdr_t) - 1));
100}
101
102/*
103 * Convert a leaf-format directory to a node-format directory.
104 * We need to change the magic number of the leaf block, and copy
105 * the freespace table out of the leaf block into its own block.
106 */
107int /* error */
108xfs_dir2_leaf_to_node(
109 xfs_da_args_t *args, /* operation arguments */
110 xfs_dabuf_t *lbp) /* leaf buffer */
111{
112 xfs_inode_t *dp; /* incore directory inode */
113 int error; /* error return value */
114 xfs_dabuf_t *fbp; /* freespace buffer */
115 xfs_dir2_db_t fdb; /* freespace block number */
116 xfs_dir2_free_t *free; /* freespace structure */
Nathan Scott68b3a102006-03-17 17:27:19 +1100117 __be16 *from; /* pointer to freespace entry */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700118 int i; /* leaf freespace index */
119 xfs_dir2_leaf_t *leaf; /* leaf structure */
120 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
121 xfs_mount_t *mp; /* filesystem mount point */
122 int n; /* count of live freespc ents */
123 xfs_dir2_data_off_t off; /* freespace entry value */
Nathan Scott0ba962e2006-03-17 17:27:07 +1100124 __be16 *to; /* pointer to freespace entry */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125 xfs_trans_t *tp; /* transaction pointer */
126
127 xfs_dir2_trace_args_b("leaf_to_node", args, lbp);
128 dp = args->dp;
129 mp = dp->i_mount;
130 tp = args->trans;
131 /*
132 * Add a freespace block to the directory.
133 */
134 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE, &fdb))) {
135 return error;
136 }
137 ASSERT(fdb == XFS_DIR2_FREE_FIRSTDB(mp));
138 /*
139 * Get the buffer for the new freespace block.
140 */
141 if ((error = xfs_da_get_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, fdb), -1, &fbp,
142 XFS_DATA_FORK))) {
143 return error;
144 }
145 ASSERT(fbp != NULL);
146 free = fbp->data;
147 leaf = lbp->data;
148 ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
149 /*
150 * Initialize the freespace block header.
151 */
Nathan Scott0ba962e2006-03-17 17:27:07 +1100152 free->hdr.magic = cpu_to_be32(XFS_DIR2_FREE_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153 free->hdr.firstdb = 0;
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100154 ASSERT(be32_to_cpu(ltp->bestcount) <= (uint)dp->i_d.di_size / mp->m_dirblksize);
Nathan Scott0ba962e2006-03-17 17:27:07 +1100155 free->hdr.nvalid = ltp->bestcount;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700156 /*
157 * Copy freespace entries from the leaf block to the new block.
158 * Count active entries.
159 */
160 for (i = n = 0, from = XFS_DIR2_LEAF_BESTS_P(ltp), to = free->bests;
Nathan Scottafbcb3f2006-03-17 17:27:28 +1100161 i < be32_to_cpu(ltp->bestcount); i++, from++, to++) {
Nathan Scott68b3a102006-03-17 17:27:19 +1100162 if ((off = be16_to_cpu(*from)) != NULLDATAOFF)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163 n++;
Nathan Scott0ba962e2006-03-17 17:27:07 +1100164 *to = cpu_to_be16(off);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165 }
Nathan Scott0ba962e2006-03-17 17:27:07 +1100166 free->hdr.nused = cpu_to_be32(n);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700167 INT_SET(leaf->hdr.info.magic, ARCH_CONVERT, XFS_DIR2_LEAFN_MAGIC);
168 /*
169 * Log everything.
170 */
171 xfs_dir2_leaf_log_header(tp, lbp);
172 xfs_dir2_free_log_header(tp, fbp);
Nathan Scott0ba962e2006-03-17 17:27:07 +1100173 xfs_dir2_free_log_bests(tp, fbp, 0, be32_to_cpu(free->hdr.nvalid) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174 xfs_da_buf_done(fbp);
175 xfs_dir2_leafn_check(dp, lbp);
176 return 0;
177}
178
179/*
180 * Add a leaf entry to a leaf block in a node-form directory.
181 * The other work necessary is done from the caller.
182 */
183static int /* error */
184xfs_dir2_leafn_add(
185 xfs_dabuf_t *bp, /* leaf buffer */
186 xfs_da_args_t *args, /* operation arguments */
187 int index) /* insertion pt for new entry */
188{
189 int compact; /* compacting stale leaves */
190 xfs_inode_t *dp; /* incore directory inode */
191 int highstale; /* next stale entry */
192 xfs_dir2_leaf_t *leaf; /* leaf structure */
193 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
194 int lfloghigh; /* high leaf entry logging */
195 int lfloglow; /* low leaf entry logging */
196 int lowstale; /* previous stale entry */
197 xfs_mount_t *mp; /* filesystem mount point */
198 xfs_trans_t *tp; /* transaction pointer */
199
200 xfs_dir2_trace_args_sb("leafn_add", args, index, bp);
201 dp = args->dp;
202 mp = dp->i_mount;
203 tp = args->trans;
204 leaf = bp->data;
205
206 /*
207 * Quick check just to make sure we are not going to index
208 * into other peoples memory
209 */
210 if (index < 0)
211 return XFS_ERROR(EFSCORRUPTED);
212
213 /*
214 * If there are already the maximum number of leaf entries in
215 * the block, if there are no stale entries it won't fit.
216 * Caller will do a split. If there are stale entries we'll do
217 * a compact.
218 */
219
Nathan Scotta818e5d2006-03-17 17:28:07 +1100220 if (be16_to_cpu(leaf->hdr.count) == XFS_DIR2_MAX_LEAF_ENTS(mp)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700221 if (!leaf->hdr.stale)
222 return XFS_ERROR(ENOSPC);
Nathan Scotta818e5d2006-03-17 17:28:07 +1100223 compact = be16_to_cpu(leaf->hdr.stale) > 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224 } else
225 compact = 0;
226 ASSERT(index == 0 || INT_GET(leaf->ents[index - 1].hashval, ARCH_CONVERT) <= args->hashval);
Nathan Scotta818e5d2006-03-17 17:28:07 +1100227 ASSERT(index == be16_to_cpu(leaf->hdr.count) ||
Linus Torvalds1da177e2005-04-16 15:20:36 -0700228 INT_GET(leaf->ents[index].hashval, ARCH_CONVERT) >= args->hashval);
229
230 if (args->justcheck)
231 return 0;
232
233 /*
234 * Compact out all but one stale leaf entry. Leaves behind
235 * the entry closest to index.
236 */
237 if (compact) {
238 xfs_dir2_leaf_compact_x1(bp, &index, &lowstale, &highstale,
239 &lfloglow, &lfloghigh);
240 }
241 /*
242 * Set impossible logging indices for this case.
243 */
244 else if (leaf->hdr.stale) {
Nathan Scotta818e5d2006-03-17 17:28:07 +1100245 lfloglow = be16_to_cpu(leaf->hdr.count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700246 lfloghigh = -1;
247 }
248 /*
249 * No stale entries, just insert a space for the new entry.
250 */
251 if (!leaf->hdr.stale) {
252 lep = &leaf->ents[index];
Nathan Scotta818e5d2006-03-17 17:28:07 +1100253 if (index < be16_to_cpu(leaf->hdr.count))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700254 memmove(lep + 1, lep,
Nathan Scotta818e5d2006-03-17 17:28:07 +1100255 (be16_to_cpu(leaf->hdr.count) - index) * sizeof(*lep));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256 lfloglow = index;
Nathan Scotta818e5d2006-03-17 17:28:07 +1100257 lfloghigh = be16_to_cpu(leaf->hdr.count);
258 be16_add(&leaf->hdr.count, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700259 }
260 /*
261 * There are stale entries. We'll use one for the new entry.
262 */
263 else {
264 /*
265 * If we didn't do a compact then we need to figure out
266 * which stale entry will be used.
267 */
268 if (compact == 0) {
269 /*
270 * Find first stale entry before our insertion point.
271 */
272 for (lowstale = index - 1;
273 lowstale >= 0 &&
274 INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) !=
275 XFS_DIR2_NULL_DATAPTR;
276 lowstale--)
277 continue;
278 /*
279 * Find next stale entry after insertion point.
280 * Stop looking if the answer would be worse than
281 * lowstale already found.
282 */
283 for (highstale = index;
Nathan Scotta818e5d2006-03-17 17:28:07 +1100284 highstale < be16_to_cpu(leaf->hdr.count) &&
Linus Torvalds1da177e2005-04-16 15:20:36 -0700285 INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) !=
286 XFS_DIR2_NULL_DATAPTR &&
287 (lowstale < 0 ||
288 index - lowstale - 1 >= highstale - index);
289 highstale++)
290 continue;
291 }
292 /*
293 * Using the low stale entry.
294 * Shift entries up toward the stale slot.
295 */
296 if (lowstale >= 0 &&
Nathan Scotta818e5d2006-03-17 17:28:07 +1100297 (highstale == be16_to_cpu(leaf->hdr.count) ||
Linus Torvalds1da177e2005-04-16 15:20:36 -0700298 index - lowstale - 1 < highstale - index)) {
299 ASSERT(INT_GET(leaf->ents[lowstale].address, ARCH_CONVERT) ==
300 XFS_DIR2_NULL_DATAPTR);
301 ASSERT(index - lowstale - 1 >= 0);
302 if (index - lowstale - 1 > 0)
303 memmove(&leaf->ents[lowstale],
304 &leaf->ents[lowstale + 1],
305 (index - lowstale - 1) * sizeof(*lep));
306 lep = &leaf->ents[index - 1];
307 lfloglow = MIN(lowstale, lfloglow);
308 lfloghigh = MAX(index - 1, lfloghigh);
309 }
310 /*
311 * Using the high stale entry.
312 * Shift entries down toward the stale slot.
313 */
314 else {
315 ASSERT(INT_GET(leaf->ents[highstale].address, ARCH_CONVERT) ==
316 XFS_DIR2_NULL_DATAPTR);
317 ASSERT(highstale - index >= 0);
318 if (highstale - index > 0)
319 memmove(&leaf->ents[index + 1],
320 &leaf->ents[index],
321 (highstale - index) * sizeof(*lep));
322 lep = &leaf->ents[index];
323 lfloglow = MIN(index, lfloglow);
324 lfloghigh = MAX(highstale, lfloghigh);
325 }
Nathan Scotta818e5d2006-03-17 17:28:07 +1100326 be16_add(&leaf->hdr.stale, -1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700327 }
328 /*
329 * Insert the new entry, log everything.
330 */
331 INT_SET(lep->hashval, ARCH_CONVERT, args->hashval);
332 INT_SET(lep->address, ARCH_CONVERT, XFS_DIR2_DB_OFF_TO_DATAPTR(mp, args->blkno, args->index));
333 xfs_dir2_leaf_log_header(tp, bp);
334 xfs_dir2_leaf_log_ents(tp, bp, lfloglow, lfloghigh);
335 xfs_dir2_leafn_check(dp, bp);
336 return 0;
337}
338
339#ifdef DEBUG
340/*
341 * Check internal consistency of a leafn block.
342 */
343void
344xfs_dir2_leafn_check(
345 xfs_inode_t *dp, /* incore directory inode */
346 xfs_dabuf_t *bp) /* leaf buffer */
347{
348 int i; /* leaf index */
349 xfs_dir2_leaf_t *leaf; /* leaf structure */
350 xfs_mount_t *mp; /* filesystem mount point */
351 int stale; /* count of stale leaves */
352
353 leaf = bp->data;
354 mp = dp->i_mount;
355 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
Nathan Scotta818e5d2006-03-17 17:28:07 +1100356 ASSERT(be16_to_cpu(leaf->hdr.count) <= XFS_DIR2_MAX_LEAF_ENTS(mp));
357 for (i = stale = 0; i < be16_to_cpu(leaf->hdr.count); i++) {
358 if (i + 1 < be16_to_cpu(leaf->hdr.count)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700359 ASSERT(INT_GET(leaf->ents[i].hashval, ARCH_CONVERT) <=
360 INT_GET(leaf->ents[i + 1].hashval, ARCH_CONVERT));
361 }
362 if (INT_GET(leaf->ents[i].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
363 stale++;
364 }
Nathan Scotta818e5d2006-03-17 17:28:07 +1100365 ASSERT(be16_to_cpu(leaf->hdr.stale) == stale);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700366}
367#endif /* DEBUG */
368
369/*
370 * Return the last hash value in the leaf.
371 * Stale entries are ok.
372 */
373xfs_dahash_t /* hash value */
374xfs_dir2_leafn_lasthash(
375 xfs_dabuf_t *bp, /* leaf buffer */
376 int *count) /* count of entries in leaf */
377{
378 xfs_dir2_leaf_t *leaf; /* leaf structure */
379
380 leaf = bp->data;
381 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
382 if (count)
Nathan Scotta818e5d2006-03-17 17:28:07 +1100383 *count = be16_to_cpu(leaf->hdr.count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700384 if (!leaf->hdr.count)
385 return 0;
Nathan Scotta818e5d2006-03-17 17:28:07 +1100386 return INT_GET(leaf->ents[be16_to_cpu(leaf->hdr.count) - 1].hashval, ARCH_CONVERT);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700387}
388
389/*
390 * Look up a leaf entry in a node-format leaf block.
391 * If this is an addname then the extrablk in state is a freespace block,
392 * otherwise it's a data block.
393 */
394int
395xfs_dir2_leafn_lookup_int(
396 xfs_dabuf_t *bp, /* leaf buffer */
397 xfs_da_args_t *args, /* operation arguments */
398 int *indexp, /* out: leaf entry index */
399 xfs_da_state_t *state) /* state to fill in */
400{
401 xfs_dabuf_t *curbp; /* current data/free buffer */
402 xfs_dir2_db_t curdb; /* current data block number */
403 xfs_dir2_db_t curfdb; /* current free block number */
404 xfs_dir2_data_entry_t *dep; /* data block entry */
405 xfs_inode_t *dp; /* incore directory inode */
406 int error; /* error return value */
407 int fi; /* free entry index */
408 xfs_dir2_free_t *free=NULL; /* free block structure */
409 int index; /* leaf entry index */
410 xfs_dir2_leaf_t *leaf; /* leaf structure */
411 int length=0; /* length of new data entry */
412 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
413 xfs_mount_t *mp; /* filesystem mount point */
414 xfs_dir2_db_t newdb; /* new data block number */
415 xfs_dir2_db_t newfdb; /* new free block number */
416 xfs_trans_t *tp; /* transaction pointer */
417
418 dp = args->dp;
419 tp = args->trans;
420 mp = dp->i_mount;
421 leaf = bp->data;
422 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
423#ifdef __KERNEL__
Nathan Scotta818e5d2006-03-17 17:28:07 +1100424 ASSERT(be16_to_cpu(leaf->hdr.count) > 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425#endif
426 xfs_dir2_leafn_check(dp, bp);
427 /*
428 * Look up the hash value in the leaf entries.
429 */
430 index = xfs_dir2_leaf_search_hash(args, bp);
431 /*
432 * Do we have a buffer coming in?
433 */
434 if (state->extravalid)
435 curbp = state->extrablk.bp;
436 else
437 curbp = NULL;
438 /*
439 * For addname, it's a free block buffer, get the block number.
440 */
441 if (args->addname) {
442 curfdb = curbp ? state->extrablk.blkno : -1;
443 curdb = -1;
444 length = XFS_DIR2_DATA_ENTSIZE(args->namelen);
445 if ((free = (curbp ? curbp->data : NULL)))
Nathan Scott0ba962e2006-03-17 17:27:07 +1100446 ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700447 }
448 /*
449 * For others, it's a data block buffer, get the block number.
450 */
451 else {
452 curfdb = -1;
453 curdb = curbp ? state->extrablk.blkno : -1;
454 }
455 /*
456 * Loop over leaf entries with the right hash value.
457 */
458 for (lep = &leaf->ents[index];
Nathan Scotta818e5d2006-03-17 17:28:07 +1100459 index < be16_to_cpu(leaf->hdr.count) && INT_GET(lep->hashval, ARCH_CONVERT) == args->hashval;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700460 lep++, index++) {
461 /*
462 * Skip stale leaf entries.
463 */
464 if (INT_GET(lep->address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
465 continue;
466 /*
467 * Pull the data block number from the entry.
468 */
469 newdb = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
470 /*
471 * For addname, we're looking for a place to put the new entry.
472 * We want to use a data block with an entry of equal
473 * hash value to ours if there is one with room.
474 */
475 if (args->addname) {
476 /*
477 * If this block isn't the data block we already have
478 * in hand, take a look at it.
479 */
480 if (newdb != curdb) {
481 curdb = newdb;
482 /*
483 * Convert the data block to the free block
484 * holding its freespace information.
485 */
486 newfdb = XFS_DIR2_DB_TO_FDB(mp, newdb);
487 /*
488 * If it's not the one we have in hand,
489 * read it in.
490 */
491 if (newfdb != curfdb) {
492 /*
493 * If we had one before, drop it.
494 */
495 if (curbp)
496 xfs_da_brelse(tp, curbp);
497 /*
498 * Read the free block.
499 */
500 if ((error = xfs_da_read_buf(tp, dp,
501 XFS_DIR2_DB_TO_DA(mp,
502 newfdb),
503 -1, &curbp,
504 XFS_DATA_FORK))) {
505 return error;
506 }
507 curfdb = newfdb;
508 free = curbp->data;
Nathan Scott0ba962e2006-03-17 17:27:07 +1100509 ASSERT(be32_to_cpu(free->hdr.magic) ==
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510 XFS_DIR2_FREE_MAGIC);
Nathan Scott0ba962e2006-03-17 17:27:07 +1100511 ASSERT((be32_to_cpu(free->hdr.firstdb) %
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512 XFS_DIR2_MAX_FREE_BESTS(mp)) ==
513 0);
Nathan Scott0ba962e2006-03-17 17:27:07 +1100514 ASSERT(be32_to_cpu(free->hdr.firstdb) <= curdb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700515 ASSERT(curdb <
Nathan Scott0ba962e2006-03-17 17:27:07 +1100516 be32_to_cpu(free->hdr.firstdb) +
517 be32_to_cpu(free->hdr.nvalid));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700518 }
519 /*
520 * Get the index for our entry.
521 */
522 fi = XFS_DIR2_DB_TO_FDINDEX(mp, curdb);
523 /*
524 * If it has room, return it.
525 */
Nathan Scott0ba962e2006-03-17 17:27:07 +1100526 if (unlikely(be16_to_cpu(free->bests[fi]) == NULLDATAOFF)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700527 XFS_ERROR_REPORT("xfs_dir2_leafn_lookup_int",
528 XFS_ERRLEVEL_LOW, mp);
529 return XFS_ERROR(EFSCORRUPTED);
530 }
Nathan Scott0ba962e2006-03-17 17:27:07 +1100531 if (be16_to_cpu(free->bests[fi]) >= length) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700532 *indexp = index;
533 state->extravalid = 1;
534 state->extrablk.bp = curbp;
535 state->extrablk.blkno = curfdb;
536 state->extrablk.index = fi;
537 state->extrablk.magic =
538 XFS_DIR2_FREE_MAGIC;
539 ASSERT(args->oknoent);
540 return XFS_ERROR(ENOENT);
541 }
542 }
543 }
544 /*
545 * Not adding a new entry, so we really want to find
546 * the name given to us.
547 */
548 else {
549 /*
550 * If it's a different data block, go get it.
551 */
552 if (newdb != curdb) {
553 /*
554 * If we had a block before, drop it.
555 */
556 if (curbp)
557 xfs_da_brelse(tp, curbp);
558 /*
559 * Read the data block.
560 */
561 if ((error =
562 xfs_da_read_buf(tp, dp,
563 XFS_DIR2_DB_TO_DA(mp, newdb), -1,
564 &curbp, XFS_DATA_FORK))) {
565 return error;
566 }
567 xfs_dir2_data_check(dp, curbp);
568 curdb = newdb;
569 }
570 /*
571 * Point to the data entry.
572 */
573 dep = (xfs_dir2_data_entry_t *)
574 ((char *)curbp->data +
575 XFS_DIR2_DATAPTR_TO_OFF(mp, INT_GET(lep->address, ARCH_CONVERT)));
576 /*
577 * Compare the entry, return it if it matches.
578 */
579 if (dep->namelen == args->namelen &&
580 dep->name[0] == args->name[0] &&
581 memcmp(dep->name, args->name, args->namelen) == 0) {
582 args->inumber = INT_GET(dep->inumber, ARCH_CONVERT);
583 *indexp = index;
584 state->extravalid = 1;
585 state->extrablk.bp = curbp;
586 state->extrablk.blkno = curdb;
587 state->extrablk.index =
588 (int)((char *)dep -
589 (char *)curbp->data);
590 state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
591 return XFS_ERROR(EEXIST);
592 }
593 }
594 }
595 /*
596 * Didn't find a match.
597 * If we are holding a buffer, give it back in case our caller
598 * finds it useful.
599 */
600 if ((state->extravalid = (curbp != NULL))) {
601 state->extrablk.bp = curbp;
602 state->extrablk.index = -1;
603 /*
604 * For addname, giving back a free block.
605 */
606 if (args->addname) {
607 state->extrablk.blkno = curfdb;
608 state->extrablk.magic = XFS_DIR2_FREE_MAGIC;
609 }
610 /*
611 * For other callers, giving back a data block.
612 */
613 else {
614 state->extrablk.blkno = curdb;
615 state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
616 }
617 }
618 /*
619 * Return the final index, that will be the insertion point.
620 */
621 *indexp = index;
Nathan Scotta818e5d2006-03-17 17:28:07 +1100622 ASSERT(index == be16_to_cpu(leaf->hdr.count) || args->oknoent);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700623 return XFS_ERROR(ENOENT);
624}
625
626/*
627 * Move count leaf entries from source to destination leaf.
628 * Log entries and headers. Stale entries are preserved.
629 */
630static void
631xfs_dir2_leafn_moveents(
632 xfs_da_args_t *args, /* operation arguments */
633 xfs_dabuf_t *bp_s, /* source leaf buffer */
634 int start_s, /* source leaf index */
635 xfs_dabuf_t *bp_d, /* destination leaf buffer */
636 int start_d, /* destination leaf index */
637 int count) /* count of leaves to copy */
638{
639 xfs_dir2_leaf_t *leaf_d; /* destination leaf structure */
640 xfs_dir2_leaf_t *leaf_s; /* source leaf structure */
641 int stale; /* count stale leaves copied */
642 xfs_trans_t *tp; /* transaction pointer */
643
644 xfs_dir2_trace_args_bibii("leafn_moveents", args, bp_s, start_s, bp_d,
645 start_d, count);
646 /*
647 * Silently return if nothing to do.
648 */
649 if (count == 0) {
650 return;
651 }
652 tp = args->trans;
653 leaf_s = bp_s->data;
654 leaf_d = bp_d->data;
655 /*
656 * If the destination index is not the end of the current
657 * destination leaf entries, open up a hole in the destination
658 * to hold the new entries.
659 */
Nathan Scotta818e5d2006-03-17 17:28:07 +1100660 if (start_d < be16_to_cpu(leaf_d->hdr.count)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700661 memmove(&leaf_d->ents[start_d + count], &leaf_d->ents[start_d],
Nathan Scotta818e5d2006-03-17 17:28:07 +1100662 (be16_to_cpu(leaf_d->hdr.count) - start_d) *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700663 sizeof(xfs_dir2_leaf_entry_t));
664 xfs_dir2_leaf_log_ents(tp, bp_d, start_d + count,
Nathan Scotta818e5d2006-03-17 17:28:07 +1100665 count + be16_to_cpu(leaf_d->hdr.count) - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700666 }
667 /*
668 * If the source has stale leaves, count the ones in the copy range
669 * so we can update the header correctly.
670 */
671 if (leaf_s->hdr.stale) {
672 int i; /* temp leaf index */
673
674 for (i = start_s, stale = 0; i < start_s + count; i++) {
675 if (INT_GET(leaf_s->ents[i].address, ARCH_CONVERT) == XFS_DIR2_NULL_DATAPTR)
676 stale++;
677 }
678 } else
679 stale = 0;
680 /*
681 * Copy the leaf entries from source to destination.
682 */
683 memcpy(&leaf_d->ents[start_d], &leaf_s->ents[start_s],
684 count * sizeof(xfs_dir2_leaf_entry_t));
685 xfs_dir2_leaf_log_ents(tp, bp_d, start_d, start_d + count - 1);
686 /*
687 * If there are source entries after the ones we copied,
688 * delete the ones we copied by sliding the next ones down.
689 */
Nathan Scotta818e5d2006-03-17 17:28:07 +1100690 if (start_s + count < be16_to_cpu(leaf_s->hdr.count)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700691 memmove(&leaf_s->ents[start_s], &leaf_s->ents[start_s + count],
692 count * sizeof(xfs_dir2_leaf_entry_t));
693 xfs_dir2_leaf_log_ents(tp, bp_s, start_s, start_s + count - 1);
694 }
695 /*
696 * Update the headers and log them.
697 */
Nathan Scotta818e5d2006-03-17 17:28:07 +1100698 be16_add(&leaf_s->hdr.count, -(count));
699 be16_add(&leaf_s->hdr.stale, -(stale));
700 be16_add(&leaf_d->hdr.count, count);
701 be16_add(&leaf_d->hdr.stale, stale);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700702 xfs_dir2_leaf_log_header(tp, bp_s);
703 xfs_dir2_leaf_log_header(tp, bp_d);
704 xfs_dir2_leafn_check(args->dp, bp_s);
705 xfs_dir2_leafn_check(args->dp, bp_d);
706}
707
708/*
709 * Determine the sort order of two leaf blocks.
710 * Returns 1 if both are valid and leaf2 should be before leaf1, else 0.
711 */
712int /* sort order */
713xfs_dir2_leafn_order(
714 xfs_dabuf_t *leaf1_bp, /* leaf1 buffer */
715 xfs_dabuf_t *leaf2_bp) /* leaf2 buffer */
716{
717 xfs_dir2_leaf_t *leaf1; /* leaf1 structure */
718 xfs_dir2_leaf_t *leaf2; /* leaf2 structure */
719
720 leaf1 = leaf1_bp->data;
721 leaf2 = leaf2_bp->data;
722 ASSERT(INT_GET(leaf1->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
723 ASSERT(INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
Nathan Scotta818e5d2006-03-17 17:28:07 +1100724 if (be16_to_cpu(leaf1->hdr.count) > 0 &&
725 be16_to_cpu(leaf2->hdr.count) > 0 &&
Linus Torvalds1da177e2005-04-16 15:20:36 -0700726 (INT_GET(leaf2->ents[0].hashval, ARCH_CONVERT) < INT_GET(leaf1->ents[0].hashval, ARCH_CONVERT) ||
Nathan Scotta818e5d2006-03-17 17:28:07 +1100727 INT_GET(leaf2->ents[be16_to_cpu(leaf2->hdr.count) - 1].hashval, ARCH_CONVERT) <
728 INT_GET(leaf1->ents[be16_to_cpu(leaf1->hdr.count) - 1].hashval, ARCH_CONVERT)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700729 return 1;
730 return 0;
731}
732
733/*
734 * Rebalance leaf entries between two leaf blocks.
735 * This is actually only called when the second block is new,
736 * though the code deals with the general case.
737 * A new entry will be inserted in one of the blocks, and that
738 * entry is taken into account when balancing.
739 */
740static void
741xfs_dir2_leafn_rebalance(
742 xfs_da_state_t *state, /* btree cursor */
743 xfs_da_state_blk_t *blk1, /* first btree block */
744 xfs_da_state_blk_t *blk2) /* second btree block */
745{
746 xfs_da_args_t *args; /* operation arguments */
747 int count; /* count (& direction) leaves */
748 int isleft; /* new goes in left leaf */
749 xfs_dir2_leaf_t *leaf1; /* first leaf structure */
750 xfs_dir2_leaf_t *leaf2; /* second leaf structure */
751 int mid; /* midpoint leaf index */
752#ifdef DEBUG
753 int oldstale; /* old count of stale leaves */
754#endif
755 int oldsum; /* old total leaf count */
756 int swap; /* swapped leaf blocks */
757
758 args = state->args;
759 /*
760 * If the block order is wrong, swap the arguments.
761 */
762 if ((swap = xfs_dir2_leafn_order(blk1->bp, blk2->bp))) {
763 xfs_da_state_blk_t *tmp; /* temp for block swap */
764
765 tmp = blk1;
766 blk1 = blk2;
767 blk2 = tmp;
768 }
769 leaf1 = blk1->bp->data;
770 leaf2 = blk2->bp->data;
Nathan Scotta818e5d2006-03-17 17:28:07 +1100771 oldsum = be16_to_cpu(leaf1->hdr.count) + be16_to_cpu(leaf2->hdr.count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700772#ifdef DEBUG
Nathan Scotta818e5d2006-03-17 17:28:07 +1100773 oldstale = be16_to_cpu(leaf1->hdr.stale) + be16_to_cpu(leaf2->hdr.stale);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700774#endif
775 mid = oldsum >> 1;
776 /*
777 * If the old leaf count was odd then the new one will be even,
778 * so we need to divide the new count evenly.
779 */
780 if (oldsum & 1) {
781 xfs_dahash_t midhash; /* middle entry hash value */
782
Nathan Scotta818e5d2006-03-17 17:28:07 +1100783 if (mid >= be16_to_cpu(leaf1->hdr.count))
784 midhash = INT_GET(leaf2->ents[mid - be16_to_cpu(leaf1->hdr.count)].hashval, ARCH_CONVERT);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700785 else
786 midhash = INT_GET(leaf1->ents[mid].hashval, ARCH_CONVERT);
787 isleft = args->hashval <= midhash;
788 }
789 /*
790 * If the old count is even then the new count is odd, so there's
791 * no preferred side for the new entry.
792 * Pick the left one.
793 */
794 else
795 isleft = 1;
796 /*
797 * Calculate moved entry count. Positive means left-to-right,
798 * negative means right-to-left. Then move the entries.
799 */
Nathan Scotta818e5d2006-03-17 17:28:07 +1100800 count = be16_to_cpu(leaf1->hdr.count) - mid + (isleft == 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700801 if (count > 0)
802 xfs_dir2_leafn_moveents(args, blk1->bp,
Nathan Scotta818e5d2006-03-17 17:28:07 +1100803 be16_to_cpu(leaf1->hdr.count) - count, blk2->bp, 0, count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700804 else if (count < 0)
805 xfs_dir2_leafn_moveents(args, blk2->bp, 0, blk1->bp,
Nathan Scotta818e5d2006-03-17 17:28:07 +1100806 be16_to_cpu(leaf1->hdr.count), count);
807 ASSERT(be16_to_cpu(leaf1->hdr.count) + be16_to_cpu(leaf2->hdr.count) == oldsum);
808 ASSERT(be16_to_cpu(leaf1->hdr.stale) + be16_to_cpu(leaf2->hdr.stale) == oldstale);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700809 /*
810 * Mark whether we're inserting into the old or new leaf.
811 */
Nathan Scotta818e5d2006-03-17 17:28:07 +1100812 if (be16_to_cpu(leaf1->hdr.count) < be16_to_cpu(leaf2->hdr.count))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700813 state->inleaf = swap;
Nathan Scotta818e5d2006-03-17 17:28:07 +1100814 else if (be16_to_cpu(leaf1->hdr.count) > be16_to_cpu(leaf2->hdr.count))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700815 state->inleaf = !swap;
816 else
817 state->inleaf =
Nathan Scotta818e5d2006-03-17 17:28:07 +1100818 swap ^ (blk1->index <= be16_to_cpu(leaf1->hdr.count));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700819 /*
820 * Adjust the expected index for insertion.
821 */
822 if (!state->inleaf)
Nathan Scotta818e5d2006-03-17 17:28:07 +1100823 blk2->index = blk1->index - be16_to_cpu(leaf1->hdr.count);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824
825 /*
826 * Finally sanity check just to make sure we are not returning a negative index
827 */
828 if(blk2->index < 0) {
829 state->inleaf = 1;
830 blk2->index = 0;
831 cmn_err(CE_ALERT,
832 "xfs_dir2_leafn_rebalance: picked the wrong leaf? reverting orignal leaf: "
833 "blk1->index %d\n",
834 blk1->index);
835 }
836}
837
838/*
839 * Remove an entry from a node directory.
840 * This removes the leaf entry and the data entry,
841 * and updates the free block if necessary.
842 */
843static int /* error */
844xfs_dir2_leafn_remove(
845 xfs_da_args_t *args, /* operation arguments */
846 xfs_dabuf_t *bp, /* leaf buffer */
847 int index, /* leaf entry index */
848 xfs_da_state_blk_t *dblk, /* data block */
849 int *rval) /* resulting block needs join */
850{
851 xfs_dir2_data_t *data; /* data block structure */
852 xfs_dir2_db_t db; /* data block number */
853 xfs_dabuf_t *dbp; /* data block buffer */
854 xfs_dir2_data_entry_t *dep; /* data block entry */
855 xfs_inode_t *dp; /* incore directory inode */
856 xfs_dir2_leaf_t *leaf; /* leaf structure */
857 xfs_dir2_leaf_entry_t *lep; /* leaf entry */
858 int longest; /* longest data free entry */
859 int off; /* data block entry offset */
860 xfs_mount_t *mp; /* filesystem mount point */
861 int needlog; /* need to log data header */
862 int needscan; /* need to rescan data frees */
863 xfs_trans_t *tp; /* transaction pointer */
864
865 xfs_dir2_trace_args_sb("leafn_remove", args, index, bp);
866 dp = args->dp;
867 tp = args->trans;
868 mp = dp->i_mount;
869 leaf = bp->data;
870 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
871 /*
872 * Point to the entry we're removing.
873 */
874 lep = &leaf->ents[index];
875 /*
876 * Extract the data block and offset from the entry.
877 */
878 db = XFS_DIR2_DATAPTR_TO_DB(mp, INT_GET(lep->address, ARCH_CONVERT));
879 ASSERT(dblk->blkno == db);
880 off = XFS_DIR2_DATAPTR_TO_OFF(mp, INT_GET(lep->address, ARCH_CONVERT));
881 ASSERT(dblk->index == off);
882 /*
883 * Kill the leaf entry by marking it stale.
884 * Log the leaf block changes.
885 */
Nathan Scotta818e5d2006-03-17 17:28:07 +1100886 be16_add(&leaf->hdr.stale, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700887 xfs_dir2_leaf_log_header(tp, bp);
888 INT_SET(lep->address, ARCH_CONVERT, XFS_DIR2_NULL_DATAPTR);
889 xfs_dir2_leaf_log_ents(tp, bp, index, index);
890 /*
891 * Make the data entry free. Keep track of the longest freespace
892 * in the data block in case it changes.
893 */
894 dbp = dblk->bp;
895 data = dbp->data;
896 dep = (xfs_dir2_data_entry_t *)((char *)data + off);
Nathan Scott70e73f52006-03-17 17:26:52 +1100897 longest = be16_to_cpu(data->hdr.bestfree[0].length);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700898 needlog = needscan = 0;
899 xfs_dir2_data_make_free(tp, dbp, off,
900 XFS_DIR2_DATA_ENTSIZE(dep->namelen), &needlog, &needscan);
901 /*
902 * Rescan the data block freespaces for bestfree.
903 * Log the data block header if needed.
904 */
905 if (needscan)
906 xfs_dir2_data_freescan(mp, data, &needlog, NULL);
907 if (needlog)
908 xfs_dir2_data_log_header(tp, dbp);
909 xfs_dir2_data_check(dp, dbp);
910 /*
911 * If the longest data block freespace changes, need to update
912 * the corresponding freeblock entry.
913 */
Nathan Scott70e73f52006-03-17 17:26:52 +1100914 if (longest < be16_to_cpu(data->hdr.bestfree[0].length)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700915 int error; /* error return value */
916 xfs_dabuf_t *fbp; /* freeblock buffer */
917 xfs_dir2_db_t fdb; /* freeblock block number */
918 int findex; /* index in freeblock entries */
919 xfs_dir2_free_t *free; /* freeblock structure */
920 int logfree; /* need to log free entry */
921
922 /*
923 * Convert the data block number to a free block,
924 * read in the free block.
925 */
926 fdb = XFS_DIR2_DB_TO_FDB(mp, db);
927 if ((error = xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, fdb),
928 -1, &fbp, XFS_DATA_FORK))) {
929 return error;
930 }
931 free = fbp->data;
Nathan Scott0ba962e2006-03-17 17:27:07 +1100932 ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
933 ASSERT(be32_to_cpu(free->hdr.firstdb) ==
Linus Torvalds1da177e2005-04-16 15:20:36 -0700934 XFS_DIR2_MAX_FREE_BESTS(mp) *
935 (fdb - XFS_DIR2_FREE_FIRSTDB(mp)));
936 /*
937 * Calculate which entry we need to fix.
938 */
939 findex = XFS_DIR2_DB_TO_FDINDEX(mp, db);
Nathan Scott70e73f52006-03-17 17:26:52 +1100940 longest = be16_to_cpu(data->hdr.bestfree[0].length);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700941 /*
942 * If the data block is now empty we can get rid of it
943 * (usually).
944 */
945 if (longest == mp->m_dirblksize - (uint)sizeof(data->hdr)) {
946 /*
947 * Try to punch out the data block.
948 */
949 error = xfs_dir2_shrink_inode(args, db, dbp);
950 if (error == 0) {
951 dblk->bp = NULL;
952 data = NULL;
953 }
954 /*
955 * We can get ENOSPC if there's no space reservation.
956 * In this case just drop the buffer and some one else
957 * will eventually get rid of the empty block.
958 */
959 else if (error == ENOSPC && args->total == 0)
960 xfs_da_buf_done(dbp);
961 else
962 return error;
963 }
964 /*
965 * If we got rid of the data block, we can eliminate that entry
966 * in the free block.
967 */
968 if (data == NULL) {
969 /*
970 * One less used entry in the free table.
971 */
Nathan Scott0ba962e2006-03-17 17:27:07 +1100972 free->hdr.nused = cpu_to_be32(-1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973 xfs_dir2_free_log_header(tp, fbp);
974 /*
975 * If this was the last entry in the table, we can
976 * trim the table size back. There might be other
977 * entries at the end referring to non-existent
978 * data blocks, get those too.
979 */
Nathan Scott0ba962e2006-03-17 17:27:07 +1100980 if (findex == be32_to_cpu(free->hdr.nvalid) - 1) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700981 int i; /* free entry index */
982
983 for (i = findex - 1;
Nathan Scott0ba962e2006-03-17 17:27:07 +1100984 i >= 0 && be16_to_cpu(free->bests[i]) == NULLDATAOFF;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700985 i--)
986 continue;
Nathan Scott0ba962e2006-03-17 17:27:07 +1100987 free->hdr.nvalid = cpu_to_be32(i + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700988 logfree = 0;
989 }
990 /*
991 * Not the last entry, just punch it out.
992 */
993 else {
Nathan Scott0ba962e2006-03-17 17:27:07 +1100994 free->bests[findex] = cpu_to_be16(NULLDATAOFF);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700995 logfree = 1;
996 }
997 /*
998 * If there are no useful entries left in the block,
999 * get rid of the block if we can.
1000 */
1001 if (!free->hdr.nused) {
1002 error = xfs_dir2_shrink_inode(args, fdb, fbp);
1003 if (error == 0) {
1004 fbp = NULL;
1005 logfree = 0;
1006 } else if (error != ENOSPC || args->total != 0)
1007 return error;
1008 /*
1009 * It's possible to get ENOSPC if there is no
1010 * space reservation. In this case some one
1011 * else will eventually get rid of this block.
1012 */
1013 }
1014 }
1015 /*
1016 * Data block is not empty, just set the free entry to
1017 * the new value.
1018 */
1019 else {
Nathan Scott0ba962e2006-03-17 17:27:07 +11001020 free->bests[findex] = cpu_to_be16(longest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001021 logfree = 1;
1022 }
1023 /*
1024 * Log the free entry that changed, unless we got rid of it.
1025 */
1026 if (logfree)
1027 xfs_dir2_free_log_bests(tp, fbp, findex, findex);
1028 /*
1029 * Drop the buffer if we still have it.
1030 */
1031 if (fbp)
1032 xfs_da_buf_done(fbp);
1033 }
1034 xfs_dir2_leafn_check(dp, bp);
1035 /*
1036 * Return indication of whether this leaf block is emtpy enough
1037 * to justify trying to join it with a neighbor.
1038 */
1039 *rval =
1040 ((uint)sizeof(leaf->hdr) +
1041 (uint)sizeof(leaf->ents[0]) *
Nathan Scotta818e5d2006-03-17 17:28:07 +11001042 (be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale))) <
Linus Torvalds1da177e2005-04-16 15:20:36 -07001043 mp->m_dir_magicpct;
1044 return 0;
1045}
1046
1047/*
1048 * Split the leaf entries in the old block into old and new blocks.
1049 */
1050int /* error */
1051xfs_dir2_leafn_split(
1052 xfs_da_state_t *state, /* btree cursor */
1053 xfs_da_state_blk_t *oldblk, /* original block */
1054 xfs_da_state_blk_t *newblk) /* newly created block */
1055{
1056 xfs_da_args_t *args; /* operation arguments */
1057 xfs_dablk_t blkno; /* new leaf block number */
1058 int error; /* error return value */
1059 xfs_mount_t *mp; /* filesystem mount point */
1060
1061 /*
1062 * Allocate space for a new leaf node.
1063 */
1064 args = state->args;
1065 mp = args->dp->i_mount;
1066 ASSERT(args != NULL);
1067 ASSERT(oldblk->magic == XFS_DIR2_LEAFN_MAGIC);
1068 error = xfs_da_grow_inode(args, &blkno);
1069 if (error) {
1070 return error;
1071 }
1072 /*
1073 * Initialize the new leaf block.
1074 */
1075 error = xfs_dir2_leaf_init(args, XFS_DIR2_DA_TO_DB(mp, blkno),
1076 &newblk->bp, XFS_DIR2_LEAFN_MAGIC);
1077 if (error) {
1078 return error;
1079 }
1080 newblk->blkno = blkno;
1081 newblk->magic = XFS_DIR2_LEAFN_MAGIC;
1082 /*
1083 * Rebalance the entries across the two leaves, link the new
1084 * block into the leaves.
1085 */
1086 xfs_dir2_leafn_rebalance(state, oldblk, newblk);
1087 error = xfs_da_blk_link(state, oldblk, newblk);
1088 if (error) {
1089 return error;
1090 }
1091 /*
1092 * Insert the new entry in the correct block.
1093 */
1094 if (state->inleaf)
1095 error = xfs_dir2_leafn_add(oldblk->bp, args, oldblk->index);
1096 else
1097 error = xfs_dir2_leafn_add(newblk->bp, args, newblk->index);
1098 /*
1099 * Update last hashval in each block since we added the name.
1100 */
1101 oldblk->hashval = xfs_dir2_leafn_lasthash(oldblk->bp, NULL);
1102 newblk->hashval = xfs_dir2_leafn_lasthash(newblk->bp, NULL);
1103 xfs_dir2_leafn_check(args->dp, oldblk->bp);
1104 xfs_dir2_leafn_check(args->dp, newblk->bp);
1105 return error;
1106}
1107
1108/*
1109 * Check a leaf block and its neighbors to see if the block should be
1110 * collapsed into one or the other neighbor. Always keep the block
1111 * with the smaller block number.
1112 * If the current block is over 50% full, don't try to join it, return 0.
1113 * If the block is empty, fill in the state structure and return 2.
1114 * If it can be collapsed, fill in the state structure and return 1.
1115 * If nothing can be done, return 0.
1116 */
1117int /* error */
1118xfs_dir2_leafn_toosmall(
1119 xfs_da_state_t *state, /* btree cursor */
1120 int *action) /* resulting action to take */
1121{
1122 xfs_da_state_blk_t *blk; /* leaf block */
1123 xfs_dablk_t blkno; /* leaf block number */
1124 xfs_dabuf_t *bp; /* leaf buffer */
1125 int bytes; /* bytes in use */
1126 int count; /* leaf live entry count */
1127 int error; /* error return value */
1128 int forward; /* sibling block direction */
1129 int i; /* sibling counter */
1130 xfs_da_blkinfo_t *info; /* leaf block header */
1131 xfs_dir2_leaf_t *leaf; /* leaf structure */
1132 int rval; /* result from path_shift */
1133
1134 /*
1135 * Check for the degenerate case of the block being over 50% full.
1136 * If so, it's not worth even looking to see if we might be able
1137 * to coalesce with a sibling.
1138 */
1139 blk = &state->path.blk[state->path.active - 1];
1140 info = blk->bp->data;
1141 ASSERT(INT_GET(info->magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1142 leaf = (xfs_dir2_leaf_t *)info;
Nathan Scotta818e5d2006-03-17 17:28:07 +11001143 count = be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001144 bytes = (uint)sizeof(leaf->hdr) + count * (uint)sizeof(leaf->ents[0]);
1145 if (bytes > (state->blocksize >> 1)) {
1146 /*
1147 * Blk over 50%, don't try to join.
1148 */
1149 *action = 0;
1150 return 0;
1151 }
1152 /*
1153 * Check for the degenerate case of the block being empty.
1154 * If the block is empty, we'll simply delete it, no need to
1155 * coalesce it with a sibling block. We choose (arbitrarily)
1156 * to merge with the forward block unless it is NULL.
1157 */
1158 if (count == 0) {
1159 /*
1160 * Make altpath point to the block we want to keep and
1161 * path point to the block we want to drop (this one).
1162 */
1163 forward = info->forw;
1164 memcpy(&state->altpath, &state->path, sizeof(state->path));
1165 error = xfs_da_path_shift(state, &state->altpath, forward, 0,
1166 &rval);
1167 if (error)
1168 return error;
1169 *action = rval ? 2 : 0;
1170 return 0;
1171 }
1172 /*
1173 * Examine each sibling block to see if we can coalesce with
1174 * at least 25% free space to spare. We need to figure out
1175 * whether to merge with the forward or the backward block.
1176 * We prefer coalescing with the lower numbered sibling so as
1177 * to shrink a directory over time.
1178 */
1179 forward = INT_GET(info->forw, ARCH_CONVERT) < INT_GET(info->back, ARCH_CONVERT);
1180 for (i = 0, bp = NULL; i < 2; forward = !forward, i++) {
1181 blkno = forward ?INT_GET( info->forw, ARCH_CONVERT) : INT_GET(info->back, ARCH_CONVERT);
1182 if (blkno == 0)
1183 continue;
1184 /*
1185 * Read the sibling leaf block.
1186 */
1187 if ((error =
1188 xfs_da_read_buf(state->args->trans, state->args->dp, blkno,
1189 -1, &bp, XFS_DATA_FORK))) {
1190 return error;
1191 }
1192 ASSERT(bp != NULL);
1193 /*
1194 * Count bytes in the two blocks combined.
1195 */
1196 leaf = (xfs_dir2_leaf_t *)info;
Nathan Scotta818e5d2006-03-17 17:28:07 +11001197 count = be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001198 bytes = state->blocksize - (state->blocksize >> 2);
1199 leaf = bp->data;
1200 ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
Nathan Scotta818e5d2006-03-17 17:28:07 +11001201 count += be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001202 bytes -= count * (uint)sizeof(leaf->ents[0]);
1203 /*
1204 * Fits with at least 25% to spare.
1205 */
1206 if (bytes >= 0)
1207 break;
1208 xfs_da_brelse(state->args->trans, bp);
1209 }
1210 /*
1211 * Didn't like either block, give up.
1212 */
1213 if (i >= 2) {
1214 *action = 0;
1215 return 0;
1216 }
1217 /*
1218 * Done with the sibling leaf block here, drop the dabuf
1219 * so path_shift can get it.
1220 */
1221 xfs_da_buf_done(bp);
1222 /*
1223 * Make altpath point to the block we want to keep (the lower
1224 * numbered block) and path point to the block we want to drop.
1225 */
1226 memcpy(&state->altpath, &state->path, sizeof(state->path));
1227 if (blkno < blk->blkno)
1228 error = xfs_da_path_shift(state, &state->altpath, forward, 0,
1229 &rval);
1230 else
1231 error = xfs_da_path_shift(state, &state->path, forward, 0,
1232 &rval);
1233 if (error) {
1234 return error;
1235 }
1236 *action = rval ? 0 : 1;
1237 return 0;
1238}
1239
1240/*
1241 * Move all the leaf entries from drop_blk to save_blk.
1242 * This is done as part of a join operation.
1243 */
1244void
1245xfs_dir2_leafn_unbalance(
1246 xfs_da_state_t *state, /* cursor */
1247 xfs_da_state_blk_t *drop_blk, /* dead block */
1248 xfs_da_state_blk_t *save_blk) /* surviving block */
1249{
1250 xfs_da_args_t *args; /* operation arguments */
1251 xfs_dir2_leaf_t *drop_leaf; /* dead leaf structure */
1252 xfs_dir2_leaf_t *save_leaf; /* surviving leaf structure */
1253
1254 args = state->args;
1255 ASSERT(drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1256 ASSERT(save_blk->magic == XFS_DIR2_LEAFN_MAGIC);
1257 drop_leaf = drop_blk->bp->data;
1258 save_leaf = save_blk->bp->data;
1259 ASSERT(INT_GET(drop_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1260 ASSERT(INT_GET(save_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR2_LEAFN_MAGIC);
1261 /*
1262 * If there are any stale leaf entries, take this opportunity
1263 * to purge them.
1264 */
Nathan Scotta818e5d2006-03-17 17:28:07 +11001265 if (drop_leaf->hdr.stale)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001266 xfs_dir2_leaf_compact(args, drop_blk->bp);
Nathan Scotta818e5d2006-03-17 17:28:07 +11001267 if (save_leaf->hdr.stale)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001268 xfs_dir2_leaf_compact(args, save_blk->bp);
1269 /*
1270 * Move the entries from drop to the appropriate end of save.
1271 */
Nathan Scotta818e5d2006-03-17 17:28:07 +11001272 drop_blk->hashval = INT_GET(drop_leaf->ents[be16_to_cpu(drop_leaf->hdr.count) - 1].hashval, ARCH_CONVERT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001273 if (xfs_dir2_leafn_order(save_blk->bp, drop_blk->bp))
1274 xfs_dir2_leafn_moveents(args, drop_blk->bp, 0, save_blk->bp, 0,
Nathan Scotta818e5d2006-03-17 17:28:07 +11001275 be16_to_cpu(drop_leaf->hdr.count));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001276 else
1277 xfs_dir2_leafn_moveents(args, drop_blk->bp, 0, save_blk->bp,
Nathan Scotta818e5d2006-03-17 17:28:07 +11001278 be16_to_cpu(save_leaf->hdr.count), be16_to_cpu(drop_leaf->hdr.count));
1279 save_blk->hashval = INT_GET(save_leaf->ents[be16_to_cpu(save_leaf->hdr.count) - 1].hashval, ARCH_CONVERT);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001280 xfs_dir2_leafn_check(args->dp, save_blk->bp);
1281}
1282
1283/*
1284 * Top-level node form directory addname routine.
1285 */
1286int /* error */
1287xfs_dir2_node_addname(
1288 xfs_da_args_t *args) /* operation arguments */
1289{
1290 xfs_da_state_blk_t *blk; /* leaf block for insert */
1291 int error; /* error return value */
1292 int rval; /* sub-return value */
1293 xfs_da_state_t *state; /* btree cursor */
1294
1295 xfs_dir2_trace_args("node_addname", args);
1296 /*
1297 * Allocate and initialize the state (btree cursor).
1298 */
1299 state = xfs_da_state_alloc();
1300 state->args = args;
1301 state->mp = args->dp->i_mount;
1302 state->blocksize = state->mp->m_dirblksize;
1303 state->node_ents = state->mp->m_dir_node_ents;
1304 /*
1305 * Look up the name. We're not supposed to find it, but
1306 * this gives us the insertion point.
1307 */
1308 error = xfs_da_node_lookup_int(state, &rval);
1309 if (error)
1310 rval = error;
1311 if (rval != ENOENT) {
1312 goto done;
1313 }
1314 /*
1315 * Add the data entry to a data block.
1316 * Extravalid is set to a freeblock found by lookup.
1317 */
1318 rval = xfs_dir2_node_addname_int(args,
1319 state->extravalid ? &state->extrablk : NULL);
1320 if (rval) {
1321 goto done;
1322 }
1323 blk = &state->path.blk[state->path.active - 1];
1324 ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1325 /*
1326 * Add the new leaf entry.
1327 */
1328 rval = xfs_dir2_leafn_add(blk->bp, args, blk->index);
1329 if (rval == 0) {
1330 /*
1331 * It worked, fix the hash values up the btree.
1332 */
1333 if (!args->justcheck)
1334 xfs_da_fixhashpath(state, &state->path);
1335 } else {
1336 /*
1337 * It didn't work, we need to split the leaf block.
1338 */
1339 if (args->total == 0) {
1340 ASSERT(rval == ENOSPC);
1341 goto done;
1342 }
1343 /*
1344 * Split the leaf block and insert the new entry.
1345 */
1346 rval = xfs_da_split(state);
1347 }
1348done:
1349 xfs_da_state_free(state);
1350 return rval;
1351}
1352
1353/*
1354 * Add the data entry for a node-format directory name addition.
1355 * The leaf entry is added in xfs_dir2_leafn_add.
1356 * We may enter with a freespace block that the lookup found.
1357 */
1358static int /* error */
1359xfs_dir2_node_addname_int(
1360 xfs_da_args_t *args, /* operation arguments */
1361 xfs_da_state_blk_t *fblk) /* optional freespace block */
1362{
1363 xfs_dir2_data_t *data; /* data block structure */
1364 xfs_dir2_db_t dbno; /* data block number */
1365 xfs_dabuf_t *dbp; /* data block buffer */
1366 xfs_dir2_data_entry_t *dep; /* data entry pointer */
1367 xfs_inode_t *dp; /* incore directory inode */
1368 xfs_dir2_data_unused_t *dup; /* data unused entry pointer */
1369 int error; /* error return value */
1370 xfs_dir2_db_t fbno; /* freespace block number */
1371 xfs_dabuf_t *fbp; /* freespace buffer */
1372 int findex; /* freespace entry index */
1373 xfs_dir2_free_t *free=NULL; /* freespace block structure */
1374 xfs_dir2_db_t ifbno; /* initial freespace block no */
1375 xfs_dir2_db_t lastfbno=0; /* highest freespace block no */
1376 int length; /* length of the new entry */
1377 int logfree; /* need to log free entry */
1378 xfs_mount_t *mp; /* filesystem mount point */
1379 int needlog; /* need to log data header */
1380 int needscan; /* need to rescan data frees */
1381 xfs_dir2_data_off_t *tagp; /* data entry tag pointer */
1382 xfs_trans_t *tp; /* transaction pointer */
1383
1384 dp = args->dp;
1385 mp = dp->i_mount;
1386 tp = args->trans;
1387 length = XFS_DIR2_DATA_ENTSIZE(args->namelen);
1388 /*
1389 * If we came in with a freespace block that means that lookup
1390 * found an entry with our hash value. This is the freespace
1391 * block for that data entry.
1392 */
1393 if (fblk) {
1394 fbp = fblk->bp;
1395 /*
1396 * Remember initial freespace block number.
1397 */
1398 ifbno = fblk->blkno;
1399 free = fbp->data;
Nathan Scott0ba962e2006-03-17 17:27:07 +11001400 ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 findex = fblk->index;
1402 /*
1403 * This means the free entry showed that the data block had
1404 * space for our entry, so we remembered it.
1405 * Use that data block.
1406 */
1407 if (findex >= 0) {
Nathan Scott0ba962e2006-03-17 17:27:07 +11001408 ASSERT(findex < be32_to_cpu(free->hdr.nvalid));
1409 ASSERT(be16_to_cpu(free->bests[findex]) != NULLDATAOFF);
1410 ASSERT(be16_to_cpu(free->bests[findex]) >= length);
1411 dbno = be32_to_cpu(free->hdr.firstdb) + findex;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001412 }
1413 /*
1414 * The data block looked at didn't have enough room.
1415 * We'll start at the beginning of the freespace entries.
1416 */
1417 else {
1418 dbno = -1;
1419 findex = 0;
1420 }
1421 }
1422 /*
1423 * Didn't come in with a freespace block, so don't have a data block.
1424 */
1425 else {
1426 ifbno = dbno = -1;
1427 fbp = NULL;
1428 findex = 0;
1429 }
1430 /*
1431 * If we don't have a data block yet, we're going to scan the
1432 * freespace blocks looking for one. Figure out what the
1433 * highest freespace block number is.
1434 */
1435 if (dbno == -1) {
1436 xfs_fileoff_t fo; /* freespace block number */
1437
1438 if ((error = xfs_bmap_last_offset(tp, dp, &fo, XFS_DATA_FORK)))
1439 return error;
1440 lastfbno = XFS_DIR2_DA_TO_DB(mp, (xfs_dablk_t)fo);
1441 fbno = ifbno;
1442 }
1443 /*
1444 * While we haven't identified a data block, search the freeblock
1445 * data for a good data block. If we find a null freeblock entry,
1446 * indicating a hole in the data blocks, remember that.
1447 */
1448 while (dbno == -1) {
1449 /*
1450 * If we don't have a freeblock in hand, get the next one.
1451 */
1452 if (fbp == NULL) {
1453 /*
1454 * Happens the first time through unless lookup gave
1455 * us a freespace block to start with.
1456 */
1457 if (++fbno == 0)
1458 fbno = XFS_DIR2_FREE_FIRSTDB(mp);
1459 /*
1460 * If it's ifbno we already looked at it.
1461 */
1462 if (fbno == ifbno)
1463 fbno++;
1464 /*
1465 * If it's off the end we're done.
1466 */
1467 if (fbno >= lastfbno)
1468 break;
1469 /*
1470 * Read the block. There can be holes in the
1471 * freespace blocks, so this might not succeed.
1472 * This should be really rare, so there's no reason
1473 * to avoid it.
1474 */
1475 if ((error = xfs_da_read_buf(tp, dp,
1476 XFS_DIR2_DB_TO_DA(mp, fbno), -2, &fbp,
1477 XFS_DATA_FORK))) {
1478 return error;
1479 }
1480 if (unlikely(fbp == NULL)) {
1481 continue;
1482 }
1483 free = fbp->data;
Nathan Scott0ba962e2006-03-17 17:27:07 +11001484 ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001485 findex = 0;
1486 }
1487 /*
1488 * Look at the current free entry. Is it good enough?
1489 */
Nathan Scott0ba962e2006-03-17 17:27:07 +11001490 if (be16_to_cpu(free->bests[findex]) != NULLDATAOFF &&
1491 be16_to_cpu(free->bests[findex]) >= length)
1492 dbno = be32_to_cpu(free->hdr.firstdb) + findex;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001493 else {
1494 /*
1495 * Are we done with the freeblock?
1496 */
Nathan Scott0ba962e2006-03-17 17:27:07 +11001497 if (++findex == be32_to_cpu(free->hdr.nvalid)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001498 /*
1499 * Drop the block.
1500 */
1501 xfs_da_brelse(tp, fbp);
1502 fbp = NULL;
1503 if (fblk && fblk->bp)
1504 fblk->bp = NULL;
1505 }
1506 }
1507 }
1508 /*
1509 * If we don't have a data block, we need to allocate one and make
1510 * the freespace entries refer to it.
1511 */
1512 if (unlikely(dbno == -1)) {
1513 /*
1514 * Not allowed to allocate, return failure.
1515 */
1516 if (args->justcheck || args->total == 0) {
1517 /*
1518 * Drop the freespace buffer unless it came from our
1519 * caller.
1520 */
1521 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1522 xfs_da_buf_done(fbp);
1523 return XFS_ERROR(ENOSPC);
1524 }
1525 /*
1526 * Allocate and initialize the new data block.
1527 */
1528 if (unlikely((error = xfs_dir2_grow_inode(args,
1529 XFS_DIR2_DATA_SPACE,
1530 &dbno)) ||
1531 (error = xfs_dir2_data_init(args, dbno, &dbp)))) {
1532 /*
1533 * Drop the freespace buffer unless it came from our
1534 * caller.
1535 */
1536 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1537 xfs_da_buf_done(fbp);
1538 return error;
1539 }
1540 /*
1541 * If (somehow) we have a freespace block, get rid of it.
1542 */
1543 if (fbp)
1544 xfs_da_brelse(tp, fbp);
1545 if (fblk && fblk->bp)
1546 fblk->bp = NULL;
1547
1548 /*
1549 * Get the freespace block corresponding to the data block
1550 * that was just allocated.
1551 */
1552 fbno = XFS_DIR2_DB_TO_FDB(mp, dbno);
1553 if (unlikely(error = xfs_da_read_buf(tp, dp,
1554 XFS_DIR2_DB_TO_DA(mp, fbno), -2, &fbp,
1555 XFS_DATA_FORK))) {
1556 xfs_da_buf_done(dbp);
1557 return error;
1558 }
1559 /*
1560 * If there wasn't a freespace block, the read will
1561 * return a NULL fbp. Allocate and initialize a new one.
1562 */
1563 if( fbp == NULL ) {
1564 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE,
1565 &fbno))) {
1566 return error;
1567 }
1568
1569 if (unlikely(XFS_DIR2_DB_TO_FDB(mp, dbno) != fbno)) {
1570 cmn_err(CE_ALERT,
1571 "xfs_dir2_node_addname_int: dir ino "
1572 "%llu needed freesp block %lld for\n"
1573 " data block %lld, got %lld\n"
1574 " ifbno %llu lastfbno %d\n",
1575 (unsigned long long)dp->i_ino,
1576 (long long)XFS_DIR2_DB_TO_FDB(mp, dbno),
1577 (long long)dbno, (long long)fbno,
1578 (unsigned long long)ifbno, lastfbno);
1579 if (fblk) {
1580 cmn_err(CE_ALERT,
1581 " fblk 0x%p blkno %llu "
1582 "index %d magic 0x%x\n",
1583 fblk,
1584 (unsigned long long)fblk->blkno,
1585 fblk->index,
1586 fblk->magic);
1587 } else {
1588 cmn_err(CE_ALERT,
1589 " ... fblk is NULL\n");
1590 }
1591 XFS_ERROR_REPORT("xfs_dir2_node_addname_int",
1592 XFS_ERRLEVEL_LOW, mp);
1593 return XFS_ERROR(EFSCORRUPTED);
1594 }
1595
1596 /*
1597 * Get a buffer for the new block.
1598 */
1599 if ((error = xfs_da_get_buf(tp, dp,
1600 XFS_DIR2_DB_TO_DA(mp, fbno),
1601 -1, &fbp, XFS_DATA_FORK))) {
1602 return error;
1603 }
1604 ASSERT(fbp != NULL);
1605
1606 /*
1607 * Initialize the new block to be empty, and remember
1608 * its first slot as our empty slot.
1609 */
1610 free = fbp->data;
Nathan Scott0ba962e2006-03-17 17:27:07 +11001611 free->hdr.magic = cpu_to_be32(XFS_DIR2_FREE_MAGIC);
1612 free->hdr.firstdb = cpu_to_be32(
Linus Torvalds1da177e2005-04-16 15:20:36 -07001613 (fbno - XFS_DIR2_FREE_FIRSTDB(mp)) *
1614 XFS_DIR2_MAX_FREE_BESTS(mp));
1615 free->hdr.nvalid = 0;
1616 free->hdr.nused = 0;
1617 } else {
1618 free = fbp->data;
Nathan Scott0ba962e2006-03-17 17:27:07 +11001619 ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001620 }
1621
1622 /*
1623 * Set the freespace block index from the data block number.
1624 */
1625 findex = XFS_DIR2_DB_TO_FDINDEX(mp, dbno);
1626 /*
1627 * If it's after the end of the current entries in the
1628 * freespace block, extend that table.
1629 */
Nathan Scott0ba962e2006-03-17 17:27:07 +11001630 if (findex >= be32_to_cpu(free->hdr.nvalid)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001631 ASSERT(findex < XFS_DIR2_MAX_FREE_BESTS(mp));
Nathan Scott0ba962e2006-03-17 17:27:07 +11001632 free->hdr.nvalid = cpu_to_be32(findex + 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001633 /*
1634 * Tag new entry so nused will go up.
1635 */
Nathan Scott0ba962e2006-03-17 17:27:07 +11001636 free->bests[findex] = cpu_to_be16(NULLDATAOFF);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001637 }
1638 /*
1639 * If this entry was for an empty data block
1640 * (this should always be true) then update the header.
1641 */
Nathan Scott0ba962e2006-03-17 17:27:07 +11001642 if (be16_to_cpu(free->bests[findex]) == NULLDATAOFF) {
1643 be32_add(&free->hdr.nused, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001644 xfs_dir2_free_log_header(tp, fbp);
1645 }
1646 /*
1647 * Update the real value in the table.
1648 * We haven't allocated the data entry yet so this will
1649 * change again.
1650 */
1651 data = dbp->data;
Nathan Scott70e73f52006-03-17 17:26:52 +11001652 free->bests[findex] = data->hdr.bestfree[0].length;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001653 logfree = 1;
1654 }
1655 /*
1656 * We had a data block so we don't have to make a new one.
1657 */
1658 else {
1659 /*
1660 * If just checking, we succeeded.
1661 */
1662 if (args->justcheck) {
1663 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1664 xfs_da_buf_done(fbp);
1665 return 0;
1666 }
1667 /*
1668 * Read the data block in.
1669 */
1670 if (unlikely(
1671 error = xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, dbno),
1672 -1, &dbp, XFS_DATA_FORK))) {
1673 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1674 xfs_da_buf_done(fbp);
1675 return error;
1676 }
1677 data = dbp->data;
1678 logfree = 0;
1679 }
Nathan Scott70e73f52006-03-17 17:26:52 +11001680 ASSERT(be16_to_cpu(data->hdr.bestfree[0].length) >= length);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001681 /*
1682 * Point to the existing unused space.
1683 */
1684 dup = (xfs_dir2_data_unused_t *)
Nathan Scott70e73f52006-03-17 17:26:52 +11001685 ((char *)data + be16_to_cpu(data->hdr.bestfree[0].offset));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001686 needscan = needlog = 0;
1687 /*
1688 * Mark the first part of the unused space, inuse for us.
1689 */
1690 xfs_dir2_data_use_free(tp, dbp, dup,
1691 (xfs_dir2_data_aoff_t)((char *)dup - (char *)data), length,
1692 &needlog, &needscan);
1693 /*
1694 * Fill in the new entry and log it.
1695 */
1696 dep = (xfs_dir2_data_entry_t *)dup;
1697 INT_SET(dep->inumber, ARCH_CONVERT, args->inumber);
1698 dep->namelen = args->namelen;
1699 memcpy(dep->name, args->name, dep->namelen);
1700 tagp = XFS_DIR2_DATA_ENTRY_TAG_P(dep);
1701 INT_SET(*tagp, ARCH_CONVERT, (xfs_dir2_data_off_t)((char *)dep - (char *)data));
1702 xfs_dir2_data_log_entry(tp, dbp, dep);
1703 /*
1704 * Rescan the block for bestfree if needed.
1705 */
1706 if (needscan)
1707 xfs_dir2_data_freescan(mp, data, &needlog, NULL);
1708 /*
1709 * Log the data block header if needed.
1710 */
1711 if (needlog)
1712 xfs_dir2_data_log_header(tp, dbp);
1713 /*
1714 * If the freespace entry is now wrong, update it.
1715 */
Nathan Scott0ba962e2006-03-17 17:27:07 +11001716 if (be16_to_cpu(free->bests[findex]) != be16_to_cpu(data->hdr.bestfree[0].length)) {
Nathan Scott70e73f52006-03-17 17:26:52 +11001717 free->bests[findex] = data->hdr.bestfree[0].length;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001718 logfree = 1;
1719 }
1720 /*
1721 * Log the freespace entry if needed.
1722 */
1723 if (logfree)
1724 xfs_dir2_free_log_bests(tp, fbp, findex, findex);
1725 /*
1726 * If the caller didn't hand us the freespace block, drop it.
1727 */
1728 if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
1729 xfs_da_buf_done(fbp);
1730 /*
1731 * Return the data block and offset in args, then drop the data block.
1732 */
1733 args->blkno = (xfs_dablk_t)dbno;
1734 args->index = INT_GET(*tagp, ARCH_CONVERT);
1735 xfs_da_buf_done(dbp);
1736 return 0;
1737}
1738
1739/*
1740 * Lookup an entry in a node-format directory.
1741 * All the real work happens in xfs_da_node_lookup_int.
1742 * The only real output is the inode number of the entry.
1743 */
1744int /* error */
1745xfs_dir2_node_lookup(
1746 xfs_da_args_t *args) /* operation arguments */
1747{
1748 int error; /* error return value */
1749 int i; /* btree level */
1750 int rval; /* operation return value */
1751 xfs_da_state_t *state; /* btree cursor */
1752
1753 xfs_dir2_trace_args("node_lookup", args);
1754 /*
1755 * Allocate and initialize the btree cursor.
1756 */
1757 state = xfs_da_state_alloc();
1758 state->args = args;
1759 state->mp = args->dp->i_mount;
1760 state->blocksize = state->mp->m_dirblksize;
1761 state->node_ents = state->mp->m_dir_node_ents;
1762 /*
1763 * Fill in the path to the entry in the cursor.
1764 */
1765 error = xfs_da_node_lookup_int(state, &rval);
1766 if (error)
1767 rval = error;
1768 /*
1769 * Release the btree blocks and leaf block.
1770 */
1771 for (i = 0; i < state->path.active; i++) {
1772 xfs_da_brelse(args->trans, state->path.blk[i].bp);
1773 state->path.blk[i].bp = NULL;
1774 }
1775 /*
1776 * Release the data block if we have it.
1777 */
1778 if (state->extravalid && state->extrablk.bp) {
1779 xfs_da_brelse(args->trans, state->extrablk.bp);
1780 state->extrablk.bp = NULL;
1781 }
1782 xfs_da_state_free(state);
1783 return rval;
1784}
1785
1786/*
1787 * Remove an entry from a node-format directory.
1788 */
1789int /* error */
1790xfs_dir2_node_removename(
1791 xfs_da_args_t *args) /* operation arguments */
1792{
1793 xfs_da_state_blk_t *blk; /* leaf block */
1794 int error; /* error return value */
1795 int rval; /* operation return value */
1796 xfs_da_state_t *state; /* btree cursor */
1797
1798 xfs_dir2_trace_args("node_removename", args);
1799 /*
1800 * Allocate and initialize the btree cursor.
1801 */
1802 state = xfs_da_state_alloc();
1803 state->args = args;
1804 state->mp = args->dp->i_mount;
1805 state->blocksize = state->mp->m_dirblksize;
1806 state->node_ents = state->mp->m_dir_node_ents;
1807 /*
1808 * Look up the entry we're deleting, set up the cursor.
1809 */
1810 error = xfs_da_node_lookup_int(state, &rval);
1811 if (error) {
1812 rval = error;
1813 }
1814 /*
1815 * Didn't find it, upper layer screwed up.
1816 */
1817 if (rval != EEXIST) {
1818 xfs_da_state_free(state);
1819 return rval;
1820 }
1821 blk = &state->path.blk[state->path.active - 1];
1822 ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1823 ASSERT(state->extravalid);
1824 /*
1825 * Remove the leaf and data entries.
1826 * Extrablk refers to the data block.
1827 */
1828 error = xfs_dir2_leafn_remove(args, blk->bp, blk->index,
1829 &state->extrablk, &rval);
1830 if (error) {
1831 return error;
1832 }
1833 /*
1834 * Fix the hash values up the btree.
1835 */
1836 xfs_da_fixhashpath(state, &state->path);
1837 /*
1838 * If we need to join leaf blocks, do it.
1839 */
1840 if (rval && state->path.active > 1)
1841 error = xfs_da_join(state);
1842 /*
1843 * If no errors so far, try conversion to leaf format.
1844 */
1845 if (!error)
1846 error = xfs_dir2_node_to_leaf(state);
1847 xfs_da_state_free(state);
1848 return error;
1849}
1850
1851/*
1852 * Replace an entry's inode number in a node-format directory.
1853 */
1854int /* error */
1855xfs_dir2_node_replace(
1856 xfs_da_args_t *args) /* operation arguments */
1857{
1858 xfs_da_state_blk_t *blk; /* leaf block */
1859 xfs_dir2_data_t *data; /* data block structure */
1860 xfs_dir2_data_entry_t *dep; /* data entry changed */
1861 int error; /* error return value */
1862 int i; /* btree level */
1863 xfs_ino_t inum; /* new inode number */
1864 xfs_dir2_leaf_t *leaf; /* leaf structure */
1865 xfs_dir2_leaf_entry_t *lep; /* leaf entry being changed */
1866 int rval; /* internal return value */
1867 xfs_da_state_t *state; /* btree cursor */
1868
1869 xfs_dir2_trace_args("node_replace", args);
1870 /*
1871 * Allocate and initialize the btree cursor.
1872 */
1873 state = xfs_da_state_alloc();
1874 state->args = args;
1875 state->mp = args->dp->i_mount;
1876 state->blocksize = state->mp->m_dirblksize;
1877 state->node_ents = state->mp->m_dir_node_ents;
1878 inum = args->inumber;
1879 /*
1880 * Lookup the entry to change in the btree.
1881 */
1882 error = xfs_da_node_lookup_int(state, &rval);
1883 if (error) {
1884 rval = error;
1885 }
1886 /*
1887 * It should be found, since the vnodeops layer has looked it up
1888 * and locked it. But paranoia is good.
1889 */
1890 if (rval == EEXIST) {
1891 /*
1892 * Find the leaf entry.
1893 */
1894 blk = &state->path.blk[state->path.active - 1];
1895 ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
1896 leaf = blk->bp->data;
1897 lep = &leaf->ents[blk->index];
1898 ASSERT(state->extravalid);
1899 /*
1900 * Point to the data entry.
1901 */
1902 data = state->extrablk.bp->data;
Nathan Scott70e73f52006-03-17 17:26:52 +11001903 ASSERT(be32_to_cpu(data->hdr.magic) == XFS_DIR2_DATA_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001904 dep = (xfs_dir2_data_entry_t *)
1905 ((char *)data +
1906 XFS_DIR2_DATAPTR_TO_OFF(state->mp, INT_GET(lep->address, ARCH_CONVERT)));
1907 ASSERT(inum != INT_GET(dep->inumber, ARCH_CONVERT));
1908 /*
1909 * Fill in the new inode number and log the entry.
1910 */
1911 INT_SET(dep->inumber, ARCH_CONVERT, inum);
1912 xfs_dir2_data_log_entry(args->trans, state->extrablk.bp, dep);
1913 rval = 0;
1914 }
1915 /*
1916 * Didn't find it, and we're holding a data block. Drop it.
1917 */
1918 else if (state->extravalid) {
1919 xfs_da_brelse(args->trans, state->extrablk.bp);
1920 state->extrablk.bp = NULL;
1921 }
1922 /*
1923 * Release all the buffers in the cursor.
1924 */
1925 for (i = 0; i < state->path.active; i++) {
1926 xfs_da_brelse(args->trans, state->path.blk[i].bp);
1927 state->path.blk[i].bp = NULL;
1928 }
1929 xfs_da_state_free(state);
1930 return rval;
1931}
1932
1933/*
1934 * Trim off a trailing empty freespace block.
1935 * Return (in rvalp) 1 if we did it, 0 if not.
1936 */
1937int /* error */
1938xfs_dir2_node_trim_free(
1939 xfs_da_args_t *args, /* operation arguments */
1940 xfs_fileoff_t fo, /* free block number */
1941 int *rvalp) /* out: did something */
1942{
1943 xfs_dabuf_t *bp; /* freespace buffer */
1944 xfs_inode_t *dp; /* incore directory inode */
1945 int error; /* error return code */
1946 xfs_dir2_free_t *free; /* freespace structure */
1947 xfs_mount_t *mp; /* filesystem mount point */
1948 xfs_trans_t *tp; /* transaction pointer */
1949
1950 dp = args->dp;
1951 mp = dp->i_mount;
1952 tp = args->trans;
1953 /*
1954 * Read the freespace block.
1955 */
1956 if (unlikely(error = xfs_da_read_buf(tp, dp, (xfs_dablk_t)fo, -2, &bp,
1957 XFS_DATA_FORK))) {
1958 return error;
1959 }
1960
1961 /*
1962 * There can be holes in freespace. If fo is a hole, there's
1963 * nothing to do.
1964 */
1965 if (bp == NULL) {
1966 return 0;
1967 }
1968 free = bp->data;
Nathan Scott0ba962e2006-03-17 17:27:07 +11001969 ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001970 /*
1971 * If there are used entries, there's nothing to do.
1972 */
Nathan Scott0ba962e2006-03-17 17:27:07 +11001973 if (be32_to_cpu(free->hdr.nused) > 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001974 xfs_da_brelse(tp, bp);
1975 *rvalp = 0;
1976 return 0;
1977 }
1978 /*
1979 * Blow the block away.
1980 */
1981 if ((error =
1982 xfs_dir2_shrink_inode(args, XFS_DIR2_DA_TO_DB(mp, (xfs_dablk_t)fo),
1983 bp))) {
1984 /*
1985 * Can't fail with ENOSPC since that only happens with no
1986 * space reservation, when breaking up an extent into two
1987 * pieces. This is the last block of an extent.
1988 */
1989 ASSERT(error != ENOSPC);
1990 xfs_da_brelse(tp, bp);
1991 return error;
1992 }
1993 /*
1994 * Return that we succeeded.
1995 */
1996 *rvalp = 1;
1997 return 0;
1998}