]>
Commit | Line | Data |
---|---|---|
2bd0ea18 NS |
1 | /* |
2 | * Copyright (c) 2000 Silicon Graphics, Inc. All Rights Reserved. | |
3 | * | |
4 | * This program is free software; you can redistribute it and/or modify it | |
5 | * under the terms of version 2 of the GNU General Public License as | |
6 | * published by the Free Software Foundation. | |
7 | * | |
8 | * This program is distributed in the hope that it would be useful, but | |
9 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. | |
11 | * | |
12 | * Further, this software is distributed without any warranty that it is | |
13 | * free of the rightful claim of any third person regarding infringement | |
14 | * or the like. Any license provided herein, whether implied or | |
15 | * otherwise, applies only to this software file. Patent licenses, if | |
16 | * any, provided herein do not apply to combinations of this program with | |
17 | * other software, or any other product whatsoever. | |
18 | * | |
19 | * You should have received a copy of the GNU General Public License along | |
20 | * with this program; if not, write the Free Software Foundation, Inc., 59 | |
21 | * Temple Place - Suite 330, Boston MA 02111-1307, USA. | |
22 | * | |
23 | * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy, | |
24 | * Mountain View, CA 94043, or: | |
25 | * | |
26 | * http://www.sgi.com | |
27 | * | |
28 | * For further information regarding this notice, see: | |
29 | * | |
30 | * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/ | |
31 | */ | |
32 | ||
33 | #include <xfs.h> | |
34 | ||
35 | /* | |
36 | * xfs_dir_leaf.c | |
37 | * | |
38 | * Routines to implement leaf blocks of directories as Btrees of hashed names. | |
39 | */ | |
40 | ||
41 | /* | |
42 | * Validate a given inode number. | |
43 | */ | |
44 | int | |
45 | xfs_dir_ino_validate(xfs_mount_t *mp, xfs_ino_t ino) | |
46 | { | |
47 | xfs_agblock_t agblkno; | |
48 | xfs_agino_t agino; | |
49 | xfs_agnumber_t agno; | |
50 | int ino_ok; | |
51 | int ioff; | |
52 | ||
53 | agno = XFS_INO_TO_AGNO(mp, ino); | |
54 | agblkno = XFS_INO_TO_AGBNO(mp, ino); | |
55 | ioff = XFS_INO_TO_OFFSET(mp, ino); | |
56 | agino = XFS_OFFBNO_TO_AGINO(mp, agblkno, ioff); | |
57 | ino_ok = | |
58 | agno < mp->m_sb.sb_agcount && | |
59 | agblkno < mp->m_sb.sb_agblocks && | |
60 | agblkno != 0 && | |
61 | ioff < (1 << mp->m_sb.sb_inopblog) && | |
62 | XFS_AGINO_TO_INO(mp, agno, agino) == ino; | |
63 | if (XFS_TEST_ERROR(!ino_ok, mp, XFS_ERRTAG_DIR_INO_VALIDATE, | |
64 | XFS_RANDOM_DIR_INO_VALIDATE)) { | |
65 | xfs_fs_cmn_err(CE_WARN, mp, | |
66 | "Invalid inode number 0x%Lx\n", ino); | |
67 | return XFS_ERROR(EFSCORRUPTED); | |
68 | } | |
69 | return 0; | |
70 | } | |
71 | ||
72 | /* | |
73 | * Create the initial contents of a shortform directory. | |
74 | */ | |
75 | int | |
76 | xfs_dir_shortform_create(xfs_da_args_t *args, xfs_ino_t parent) | |
77 | { | |
78 | xfs_dir_sf_hdr_t *hdr; | |
79 | xfs_inode_t *dp; | |
80 | ||
81 | dp = args->dp; | |
82 | ASSERT(dp != NULL); | |
83 | ASSERT(dp->i_d.di_size == 0); | |
84 | if (dp->i_d.di_format == XFS_DINODE_FMT_EXTENTS) { | |
85 | dp->i_df.if_flags &= ~XFS_IFEXTENTS; /* just in case */ | |
86 | dp->i_d.di_format = XFS_DINODE_FMT_LOCAL; | |
87 | xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE); | |
88 | dp->i_df.if_flags |= XFS_IFINLINE; | |
89 | } | |
90 | ASSERT(dp->i_df.if_flags & XFS_IFINLINE); | |
91 | ASSERT(dp->i_df.if_bytes == 0); | |
92 | xfs_idata_realloc(dp, sizeof(*hdr), XFS_DATA_FORK); | |
93 | hdr = (xfs_dir_sf_hdr_t *)dp->i_df.if_u1.if_data; | |
94 | XFS_DIR_SF_PUT_DIRINO_ARCH(&parent, &hdr->parent, ARCH_CONVERT); | |
95 | ||
96 | INT_ZERO(hdr->count, ARCH_CONVERT); | |
97 | dp->i_d.di_size = sizeof(*hdr); | |
98 | xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA); | |
99 | return(0); | |
100 | } | |
101 | ||
102 | /* | |
103 | * Add a name to the shortform directory structure. | |
104 | * Overflow from the inode has already been checked for. | |
105 | */ | |
106 | int | |
107 | xfs_dir_shortform_addname(xfs_da_args_t *args) | |
108 | { | |
109 | xfs_dir_shortform_t *sf; | |
110 | xfs_dir_sf_entry_t *sfe; | |
111 | int i, offset, size; | |
112 | xfs_inode_t *dp; | |
113 | ||
114 | dp = args->dp; | |
115 | ASSERT(dp->i_df.if_flags & XFS_IFINLINE); | |
116 | /* | |
117 | * Catch the case where the conversion from shortform to leaf | |
118 | * failed part way through. | |
119 | */ | |
120 | if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { | |
121 | #pragma mips_frequency_hint NEVER | |
122 | ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); | |
123 | return XFS_ERROR(EIO); | |
124 | } | |
125 | ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); | |
126 | ASSERT(dp->i_df.if_u1.if_data != NULL); | |
127 | sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; | |
128 | sfe = &sf->list[0]; | |
129 | for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) { | |
130 | if (sfe->namelen == args->namelen && | |
131 | args->name[0] == sfe->name[0] && | |
132 | bcmp(args->name, sfe->name, args->namelen) == 0) | |
133 | return(XFS_ERROR(EEXIST)); | |
134 | sfe = XFS_DIR_SF_NEXTENTRY(sfe); | |
135 | } | |
136 | ||
137 | offset = (int)((char *)sfe - (char *)sf); | |
138 | size = XFS_DIR_SF_ENTSIZE_BYNAME(args->namelen); | |
139 | xfs_idata_realloc(dp, size, XFS_DATA_FORK); | |
140 | sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; | |
141 | sfe = (xfs_dir_sf_entry_t *)((char *)sf + offset); | |
142 | ||
143 | XFS_DIR_SF_PUT_DIRINO_ARCH(&args->inumber, &sfe->inumber, ARCH_CONVERT); | |
144 | sfe->namelen = args->namelen; | |
145 | bcopy(args->name, sfe->name, sfe->namelen); | |
146 | INT_MOD(sf->hdr.count, ARCH_CONVERT, +1); | |
147 | ||
148 | dp->i_d.di_size += size; | |
149 | xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA); | |
150 | ||
151 | return(0); | |
152 | } | |
153 | ||
154 | /* | |
155 | * Remove a name from the shortform directory structure. | |
156 | */ | |
157 | int | |
158 | xfs_dir_shortform_removename(xfs_da_args_t *args) | |
159 | { | |
160 | xfs_dir_shortform_t *sf; | |
161 | xfs_dir_sf_entry_t *sfe; | |
162 | int base, size, i; | |
163 | xfs_inode_t *dp; | |
164 | ||
165 | dp = args->dp; | |
166 | ASSERT(dp->i_df.if_flags & XFS_IFINLINE); | |
167 | /* | |
168 | * Catch the case where the conversion from shortform to leaf | |
169 | * failed part way through. | |
170 | */ | |
171 | if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { | |
172 | #pragma mips_frequency_hint NEVER | |
173 | ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); | |
174 | return XFS_ERROR(EIO); | |
175 | } | |
176 | ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); | |
177 | ASSERT(dp->i_df.if_u1.if_data != NULL); | |
178 | base = sizeof(xfs_dir_sf_hdr_t); | |
179 | sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; | |
180 | sfe = &sf->list[0]; | |
181 | for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) { | |
182 | size = XFS_DIR_SF_ENTSIZE_BYENTRY(sfe); | |
183 | if (sfe->namelen == args->namelen && | |
184 | sfe->name[0] == args->name[0] && | |
185 | bcmp(sfe->name, args->name, args->namelen) == 0) | |
186 | break; | |
187 | base += size; | |
188 | sfe = XFS_DIR_SF_NEXTENTRY(sfe); | |
189 | } | |
190 | if (i < 0) { | |
191 | ASSERT(args->oknoent); | |
192 | return(XFS_ERROR(ENOENT)); | |
193 | } | |
194 | ||
195 | if ((base + size) != dp->i_d.di_size) { | |
196 | ovbcopy(&((char *)sf)[base+size], &((char *)sf)[base], | |
197 | dp->i_d.di_size - (base+size)); | |
198 | } | |
199 | INT_MOD(sf->hdr.count, ARCH_CONVERT, -1); | |
200 | ||
201 | xfs_idata_realloc(dp, -size, XFS_DATA_FORK); | |
202 | dp->i_d.di_size -= size; | |
203 | xfs_trans_log_inode(args->trans, dp, XFS_ILOG_CORE | XFS_ILOG_DDATA); | |
204 | ||
205 | return(0); | |
206 | } | |
207 | ||
208 | /* | |
209 | * Look up a name in a shortform directory structure. | |
210 | */ | |
211 | int | |
212 | xfs_dir_shortform_lookup(xfs_da_args_t *args) | |
213 | { | |
214 | xfs_dir_shortform_t *sf; | |
215 | xfs_dir_sf_entry_t *sfe; | |
216 | int i; | |
217 | xfs_inode_t *dp; | |
218 | ||
219 | dp = args->dp; | |
220 | ASSERT(dp->i_df.if_flags & XFS_IFINLINE); | |
221 | /* | |
222 | * Catch the case where the conversion from shortform to leaf | |
223 | * failed part way through. | |
224 | */ | |
225 | if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { | |
226 | #pragma mips_frequency_hint NEVER | |
227 | ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); | |
228 | return XFS_ERROR(EIO); | |
229 | } | |
230 | ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); | |
231 | ASSERT(dp->i_df.if_u1.if_data != NULL); | |
232 | sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; | |
233 | if (args->namelen == 2 && | |
234 | args->name[0] == '.' && args->name[1] == '.') { | |
235 | XFS_DIR_SF_GET_DIRINO_ARCH(&sf->hdr.parent, &args->inumber, ARCH_CONVERT); | |
236 | return(XFS_ERROR(EEXIST)); | |
237 | } | |
238 | if (args->namelen == 1 && args->name[0] == '.') { | |
239 | args->inumber = dp->i_ino; | |
240 | return(XFS_ERROR(EEXIST)); | |
241 | } | |
242 | sfe = &sf->list[0]; | |
243 | for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) { | |
244 | if (sfe->namelen == args->namelen && | |
245 | sfe->name[0] == args->name[0] && | |
246 | bcmp(args->name, sfe->name, args->namelen) == 0) { | |
247 | XFS_DIR_SF_GET_DIRINO_ARCH(&sfe->inumber, &args->inumber, ARCH_CONVERT); | |
248 | return(XFS_ERROR(EEXIST)); | |
249 | } | |
250 | sfe = XFS_DIR_SF_NEXTENTRY(sfe); | |
251 | } | |
252 | ASSERT(args->oknoent); | |
253 | return(XFS_ERROR(ENOENT)); | |
254 | } | |
255 | ||
256 | /* | |
257 | * Convert from using the shortform to the leaf. | |
258 | */ | |
259 | int | |
260 | xfs_dir_shortform_to_leaf(xfs_da_args_t *iargs) | |
261 | { | |
262 | xfs_inode_t *dp; | |
263 | xfs_dir_shortform_t *sf; | |
264 | xfs_dir_sf_entry_t *sfe; | |
265 | xfs_da_args_t args; | |
266 | xfs_ino_t inumber; | |
267 | char *tmpbuffer; | |
268 | int retval, i, size; | |
269 | xfs_dablk_t blkno; | |
270 | xfs_dabuf_t *bp; | |
271 | ||
272 | dp = iargs->dp; | |
273 | /* | |
274 | * Catch the case where the conversion from shortform to leaf | |
275 | * failed part way through. | |
276 | */ | |
277 | if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { | |
278 | #pragma mips_frequency_hint NEVER | |
279 | ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); | |
280 | return XFS_ERROR(EIO); | |
281 | } | |
282 | ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); | |
283 | ASSERT(dp->i_df.if_u1.if_data != NULL); | |
284 | size = dp->i_df.if_bytes; | |
285 | tmpbuffer = kmem_alloc(size, KM_SLEEP); | |
286 | ASSERT(tmpbuffer != NULL); | |
287 | ||
288 | bcopy(dp->i_df.if_u1.if_data, tmpbuffer, size); | |
289 | ||
290 | sf = (xfs_dir_shortform_t *)tmpbuffer; | |
291 | XFS_DIR_SF_GET_DIRINO_ARCH(&sf->hdr.parent, &inumber, ARCH_CONVERT); | |
292 | ||
293 | xfs_idata_realloc(dp, -size, XFS_DATA_FORK); | |
294 | dp->i_d.di_size = 0; | |
295 | xfs_trans_log_inode(iargs->trans, dp, XFS_ILOG_CORE); | |
296 | retval = xfs_da_grow_inode(iargs, &blkno); | |
297 | if (retval) | |
298 | goto out; | |
299 | ||
300 | ASSERT(blkno == 0); | |
301 | retval = xfs_dir_leaf_create(iargs, blkno, &bp); | |
302 | if (retval) | |
303 | goto out; | |
304 | xfs_da_buf_done(bp); | |
305 | ||
306 | args.name = "."; | |
307 | args.namelen = 1; | |
308 | args.hashval = xfs_dir_hash_dot; | |
309 | args.inumber = dp->i_ino; | |
310 | args.dp = dp; | |
311 | args.firstblock = iargs->firstblock; | |
312 | args.flist = iargs->flist; | |
313 | args.total = iargs->total; | |
314 | args.whichfork = XFS_DATA_FORK; | |
315 | args.trans = iargs->trans; | |
316 | args.justcheck = 0; | |
317 | args.addname = args.oknoent = 1; | |
318 | retval = xfs_dir_leaf_addname(&args); | |
319 | if (retval) | |
320 | goto out; | |
321 | ||
322 | args.name = ".."; | |
323 | args.namelen = 2; | |
324 | args.hashval = xfs_dir_hash_dotdot; | |
325 | args.inumber = inumber; | |
326 | retval = xfs_dir_leaf_addname(&args); | |
327 | if (retval) | |
328 | goto out; | |
329 | ||
330 | sfe = &sf->list[0]; | |
331 | for (i = 0; i < INT_GET(sf->hdr.count, ARCH_CONVERT); i++) { | |
332 | args.name = (char *)(sfe->name); | |
333 | args.namelen = sfe->namelen; | |
334 | args.hashval = xfs_da_hashname((char *)(sfe->name), | |
335 | sfe->namelen); | |
336 | XFS_DIR_SF_GET_DIRINO_ARCH(&sfe->inumber, &args.inumber, ARCH_CONVERT); | |
337 | retval = xfs_dir_leaf_addname(&args); | |
338 | if (retval) | |
339 | goto out; | |
340 | sfe = XFS_DIR_SF_NEXTENTRY(sfe); | |
341 | } | |
342 | retval = 0; | |
343 | ||
344 | out: | |
345 | kmem_free(tmpbuffer, size); | |
346 | return(retval); | |
347 | } | |
348 | ||
349 | /* | |
350 | * Look up a name in a shortform directory structure, replace the inode number. | |
351 | */ | |
352 | int | |
353 | xfs_dir_shortform_replace(xfs_da_args_t *args) | |
354 | { | |
355 | xfs_dir_shortform_t *sf; | |
356 | xfs_dir_sf_entry_t *sfe; | |
357 | xfs_inode_t *dp; | |
358 | int i; | |
359 | ||
360 | dp = args->dp; | |
361 | ASSERT(dp->i_df.if_flags & XFS_IFINLINE); | |
362 | /* | |
363 | * Catch the case where the conversion from shortform to leaf | |
364 | * failed part way through. | |
365 | */ | |
366 | if (dp->i_d.di_size < sizeof(xfs_dir_sf_hdr_t)) { | |
367 | #pragma mips_frequency_hint NEVER | |
368 | ASSERT(XFS_FORCED_SHUTDOWN(dp->i_mount)); | |
369 | return XFS_ERROR(EIO); | |
370 | } | |
371 | ASSERT(dp->i_df.if_bytes == dp->i_d.di_size); | |
372 | ASSERT(dp->i_df.if_u1.if_data != NULL); | |
373 | sf = (xfs_dir_shortform_t *)dp->i_df.if_u1.if_data; | |
374 | if (args->namelen == 2 && | |
375 | args->name[0] == '.' && args->name[1] == '.') { | |
376 | /* XXX - replace assert? */ | |
377 | XFS_DIR_SF_PUT_DIRINO_ARCH(&args->inumber, &sf->hdr.parent, ARCH_CONVERT); | |
378 | xfs_trans_log_inode(args->trans, dp, XFS_ILOG_DDATA); | |
379 | return(0); | |
380 | } | |
381 | ASSERT(args->namelen != 1 || args->name[0] != '.'); | |
382 | sfe = &sf->list[0]; | |
383 | for (i = INT_GET(sf->hdr.count, ARCH_CONVERT)-1; i >= 0; i--) { | |
384 | if (sfe->namelen == args->namelen && | |
385 | sfe->name[0] == args->name[0] && | |
386 | bcmp(args->name, sfe->name, args->namelen) == 0) { | |
387 | ASSERT(bcmp((char *)&args->inumber, | |
388 | (char *)&sfe->inumber, sizeof(xfs_ino_t))); | |
389 | XFS_DIR_SF_PUT_DIRINO_ARCH(&args->inumber, &sfe->inumber, ARCH_CONVERT); | |
390 | xfs_trans_log_inode(args->trans, dp, XFS_ILOG_DDATA); | |
391 | return(0); | |
392 | } | |
393 | sfe = XFS_DIR_SF_NEXTENTRY(sfe); | |
394 | } | |
395 | ASSERT(args->oknoent); | |
396 | return(XFS_ERROR(ENOENT)); | |
397 | } | |
398 | ||
399 | /* | |
400 | * Convert a leaf directory to shortform structure | |
401 | */ | |
402 | int | |
403 | xfs_dir_leaf_to_shortform(xfs_da_args_t *iargs) | |
404 | { | |
405 | xfs_dir_leafblock_t *leaf; | |
406 | xfs_dir_leaf_hdr_t *hdr; | |
407 | xfs_dir_leaf_entry_t *entry; | |
408 | xfs_dir_leaf_name_t *namest; | |
409 | xfs_da_args_t args; | |
410 | xfs_inode_t *dp; | |
411 | xfs_ino_t parent; | |
412 | char *tmpbuffer; | |
413 | int retval, i; | |
414 | xfs_dabuf_t *bp; | |
415 | ||
416 | dp = iargs->dp; | |
417 | tmpbuffer = kmem_alloc(XFS_LBSIZE(dp->i_mount), KM_SLEEP); | |
418 | ASSERT(tmpbuffer != NULL); | |
419 | ||
420 | retval = xfs_da_read_buf(iargs->trans, iargs->dp, 0, -1, &bp, | |
421 | XFS_DATA_FORK); | |
422 | if (retval) | |
423 | return(retval); | |
424 | ASSERT(bp != NULL); | |
425 | bcopy(bp->data, tmpbuffer, XFS_LBSIZE(dp->i_mount)); | |
426 | leaf = (xfs_dir_leafblock_t *)tmpbuffer; | |
427 | ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
428 | bzero(bp->data, XFS_LBSIZE(dp->i_mount)); | |
429 | ||
430 | /* | |
431 | * Find and special case the parent inode number | |
432 | */ | |
433 | hdr = &leaf->hdr; | |
434 | entry = &leaf->entries[0]; | |
435 | for (i = INT_GET(hdr->count, ARCH_CONVERT)-1; i >= 0; entry++, i--) { | |
436 | namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); | |
437 | if ((entry->namelen == 2) && | |
438 | (namest->name[0] == '.') && | |
439 | (namest->name[1] == '.')) { | |
440 | XFS_DIR_SF_GET_DIRINO_ARCH(&namest->inumber, &parent, ARCH_CONVERT); | |
441 | INT_ZERO(entry->nameidx, ARCH_CONVERT); | |
442 | } else if ((entry->namelen == 1) && (namest->name[0] == '.')) { | |
443 | INT_ZERO(entry->nameidx, ARCH_CONVERT); | |
444 | } | |
445 | } | |
446 | retval = xfs_da_shrink_inode(iargs, 0, bp); | |
447 | if (retval) | |
448 | goto out; | |
449 | retval = xfs_dir_shortform_create(iargs, parent); | |
450 | if (retval) | |
451 | goto out; | |
452 | ||
453 | /* | |
454 | * Copy the rest of the filenames | |
455 | */ | |
456 | entry = &leaf->entries[0]; | |
457 | args.dp = dp; | |
458 | args.firstblock = iargs->firstblock; | |
459 | args.flist = iargs->flist; | |
460 | args.total = iargs->total; | |
461 | args.whichfork = XFS_DATA_FORK; | |
462 | args.trans = iargs->trans; | |
463 | args.justcheck = 0; | |
464 | args.addname = args.oknoent = 1; | |
465 | for (i = 0; i < INT_GET(hdr->count, ARCH_CONVERT); entry++, i++) { | |
466 | if (INT_GET(entry->nameidx, ARCH_CONVERT) == 0) | |
467 | continue; | |
468 | namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); | |
469 | args.name = (char *)(namest->name); | |
470 | args.namelen = entry->namelen; | |
471 | args.hashval = INT_GET(entry->hashval, ARCH_CONVERT); | |
472 | XFS_DIR_SF_GET_DIRINO_ARCH(&namest->inumber, &args.inumber, ARCH_CONVERT); | |
473 | xfs_dir_shortform_addname(&args); | |
474 | } | |
475 | ||
476 | out: | |
477 | kmem_free(tmpbuffer, XFS_LBSIZE(dp->i_mount)); | |
478 | return(retval); | |
479 | } | |
480 | ||
481 | /* | |
482 | * Convert from using a single leaf to a root node and a leaf. | |
483 | */ | |
484 | int | |
485 | xfs_dir_leaf_to_node(xfs_da_args_t *args) | |
486 | { | |
487 | xfs_dir_leafblock_t *leaf; | |
488 | xfs_da_intnode_t *node; | |
489 | xfs_inode_t *dp; | |
490 | xfs_dabuf_t *bp1, *bp2; | |
491 | xfs_dablk_t blkno; | |
492 | int retval; | |
493 | ||
494 | dp = args->dp; | |
495 | retval = xfs_da_grow_inode(args, &blkno); | |
496 | ASSERT(blkno == 1); | |
497 | if (retval) | |
498 | return(retval); | |
499 | retval = xfs_da_read_buf(args->trans, args->dp, 0, -1, &bp1, | |
500 | XFS_DATA_FORK); | |
501 | if (retval) | |
502 | return(retval); | |
503 | ASSERT(bp1 != NULL); | |
504 | retval = xfs_da_get_buf(args->trans, args->dp, 1, -1, &bp2, | |
505 | XFS_DATA_FORK); | |
506 | if (retval) { | |
507 | xfs_da_buf_done(bp1); | |
508 | return(retval); | |
509 | } | |
510 | ASSERT(bp2 != NULL); | |
511 | bcopy(bp1->data, bp2->data, XFS_LBSIZE(dp->i_mount)); | |
512 | xfs_da_buf_done(bp1); | |
513 | xfs_da_log_buf(args->trans, bp2, 0, XFS_LBSIZE(dp->i_mount) - 1); | |
514 | ||
515 | /* | |
516 | * Set up the new root node. | |
517 | */ | |
518 | retval = xfs_da_node_create(args, 0, 1, &bp1, XFS_DATA_FORK); | |
519 | if (retval) { | |
520 | xfs_da_buf_done(bp2); | |
521 | return(retval); | |
522 | } | |
523 | node = bp1->data; | |
524 | leaf = bp2->data; | |
525 | ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
526 | INT_SET(node->btree[0].hashval, ARCH_CONVERT, INT_GET(leaf->entries[ INT_GET(leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT)); | |
527 | xfs_da_buf_done(bp2); | |
528 | INT_SET(node->btree[0].before, ARCH_CONVERT, blkno); | |
529 | INT_SET(node->hdr.count, ARCH_CONVERT, 1); | |
530 | xfs_da_log_buf(args->trans, bp1, | |
531 | XFS_DA_LOGRANGE(node, &node->btree[0], sizeof(node->btree[0]))); | |
532 | xfs_da_buf_done(bp1); | |
533 | ||
534 | return(retval); | |
535 | } | |
536 | ||
537 | ||
538 | /*======================================================================== | |
539 | * Routines used for growing the Btree. | |
540 | *========================================================================*/ | |
541 | ||
542 | /* | |
543 | * Create the initial contents of a leaf directory | |
544 | * or a leaf in a node directory. | |
545 | */ | |
546 | int | |
547 | xfs_dir_leaf_create(xfs_da_args_t *args, xfs_dablk_t blkno, xfs_dabuf_t **bpp) | |
548 | { | |
549 | xfs_dir_leafblock_t *leaf; | |
550 | xfs_dir_leaf_hdr_t *hdr; | |
551 | xfs_inode_t *dp; | |
552 | xfs_dabuf_t *bp; | |
553 | int retval; | |
554 | ||
555 | dp = args->dp; | |
556 | ASSERT(dp != NULL); | |
557 | retval = xfs_da_get_buf(args->trans, dp, blkno, -1, &bp, XFS_DATA_FORK); | |
558 | if (retval) | |
559 | return(retval); | |
560 | ASSERT(bp != NULL); | |
561 | leaf = bp->data; | |
562 | bzero((char *)leaf, XFS_LBSIZE(dp->i_mount)); | |
563 | hdr = &leaf->hdr; | |
564 | INT_SET(hdr->info.magic, ARCH_CONVERT, XFS_DIR_LEAF_MAGIC); | |
565 | INT_SET(hdr->firstused, ARCH_CONVERT, XFS_LBSIZE(dp->i_mount)); | |
566 | if (INT_ISZERO(hdr->firstused, ARCH_CONVERT)) | |
567 | INT_SET(hdr->firstused, ARCH_CONVERT, XFS_LBSIZE(dp->i_mount) - 1); | |
568 | INT_SET(hdr->freemap[0].base, ARCH_CONVERT, sizeof(xfs_dir_leaf_hdr_t)); | |
569 | INT_SET(hdr->freemap[0].size, ARCH_CONVERT, INT_GET(hdr->firstused, ARCH_CONVERT) - INT_GET(hdr->freemap[0].base, ARCH_CONVERT)); | |
570 | ||
571 | xfs_da_log_buf(args->trans, bp, 0, XFS_LBSIZE(dp->i_mount) - 1); | |
572 | ||
573 | *bpp = bp; | |
574 | return(0); | |
575 | } | |
576 | ||
577 | /* | |
578 | * Split the leaf node, rebalance, then add the new entry. | |
579 | */ | |
580 | int | |
581 | xfs_dir_leaf_split(xfs_da_state_t *state, xfs_da_state_blk_t *oldblk, | |
582 | xfs_da_state_blk_t *newblk) | |
583 | { | |
584 | xfs_dablk_t blkno; | |
585 | xfs_da_args_t *args; | |
586 | int error; | |
587 | ||
588 | /* | |
589 | * Allocate space for a new leaf node. | |
590 | */ | |
591 | args = state->args; | |
592 | ASSERT(args != NULL); | |
593 | ASSERT(oldblk->magic == XFS_DIR_LEAF_MAGIC); | |
594 | error = xfs_da_grow_inode(args, &blkno); | |
595 | if (error) | |
596 | return(error); | |
597 | error = xfs_dir_leaf_create(args, blkno, &newblk->bp); | |
598 | if (error) | |
599 | return(error); | |
600 | newblk->blkno = blkno; | |
601 | newblk->magic = XFS_DIR_LEAF_MAGIC; | |
602 | ||
603 | /* | |
604 | * Rebalance the entries across the two leaves. | |
605 | */ | |
606 | xfs_dir_leaf_rebalance(state, oldblk, newblk); | |
607 | error = xfs_da_blk_link(state, oldblk, newblk); | |
608 | if (error) | |
609 | return(error); | |
610 | ||
611 | /* | |
612 | * Insert the new entry in the correct block. | |
613 | */ | |
614 | if (state->inleaf) { | |
615 | error = xfs_dir_leaf_add(oldblk->bp, args, oldblk->index); | |
616 | } else { | |
617 | error = xfs_dir_leaf_add(newblk->bp, args, newblk->index); | |
618 | } | |
619 | ||
620 | /* | |
621 | * Update last hashval in each block since we added the name. | |
622 | */ | |
623 | oldblk->hashval = xfs_dir_leaf_lasthash(oldblk->bp, NULL); | |
624 | newblk->hashval = xfs_dir_leaf_lasthash(newblk->bp, NULL); | |
625 | return(error); | |
626 | } | |
627 | ||
628 | /* | |
629 | * Add a name to the leaf directory structure. | |
630 | * | |
631 | * Must take into account fragmented leaves and leaves where spacemap has | |
632 | * lost some freespace information (ie: holes). | |
633 | */ | |
634 | int | |
635 | xfs_dir_leaf_add(xfs_dabuf_t *bp, xfs_da_args_t *args, int index) | |
636 | { | |
637 | xfs_dir_leafblock_t *leaf; | |
638 | xfs_dir_leaf_hdr_t *hdr; | |
639 | xfs_dir_leaf_map_t *map; | |
640 | int tablesize, entsize, sum, i, tmp, error; | |
641 | ||
642 | leaf = bp->data; | |
643 | ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
644 | ASSERT((index >= 0) && (index <= INT_GET(leaf->hdr.count, ARCH_CONVERT))); | |
645 | hdr = &leaf->hdr; | |
646 | entsize = XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen); | |
647 | ||
648 | /* | |
649 | * Search through freemap for first-fit on new name length. | |
650 | * (may need to figure in size of entry struct too) | |
651 | */ | |
652 | tablesize = (INT_GET(hdr->count, ARCH_CONVERT) + 1) * (uint)sizeof(xfs_dir_leaf_entry_t) | |
653 | + (uint)sizeof(xfs_dir_leaf_hdr_t); | |
654 | map = &hdr->freemap[XFS_DIR_LEAF_MAPSIZE-1]; | |
655 | for (sum = 0, i = XFS_DIR_LEAF_MAPSIZE-1; i >= 0; map--, i--) { | |
656 | if (tablesize > INT_GET(hdr->firstused, ARCH_CONVERT)) { | |
657 | sum += INT_GET(map->size, ARCH_CONVERT); | |
658 | continue; | |
659 | } | |
660 | if (INT_GET(map->size, ARCH_CONVERT) == 0) | |
661 | continue; /* no space in this map */ | |
662 | tmp = entsize; | |
663 | if (INT_GET(map->base, ARCH_CONVERT) < INT_GET(hdr->firstused, ARCH_CONVERT)) | |
664 | tmp += (uint)sizeof(xfs_dir_leaf_entry_t); | |
665 | if (INT_GET(map->size, ARCH_CONVERT) >= tmp) { | |
666 | if (!args->justcheck) | |
667 | xfs_dir_leaf_add_work(bp, args, index, i); | |
668 | return(0); | |
669 | } | |
670 | sum += INT_GET(map->size, ARCH_CONVERT); | |
671 | } | |
672 | ||
673 | /* | |
674 | * If there are no holes in the address space of the block, | |
675 | * and we don't have enough freespace, then compaction will do us | |
676 | * no good and we should just give up. | |
677 | */ | |
678 | if (!hdr->holes && (sum < entsize)) | |
679 | return(XFS_ERROR(ENOSPC)); | |
680 | ||
681 | /* | |
682 | * Compact the entries to coalesce free space. | |
683 | * Pass the justcheck flag so the checking pass can return | |
684 | * an error, without changing anything, if it won't fit. | |
685 | */ | |
686 | error = xfs_dir_leaf_compact(args->trans, bp, | |
687 | args->total == 0 ? | |
688 | entsize + | |
689 | (uint)sizeof(xfs_dir_leaf_entry_t) : 0, | |
690 | args->justcheck); | |
691 | if (error) | |
692 | return(error); | |
693 | /* | |
694 | * After compaction, the block is guaranteed to have only one | |
695 | * free region, in freemap[0]. If it is not big enough, give up. | |
696 | */ | |
697 | if (INT_GET(hdr->freemap[0].size, ARCH_CONVERT) < | |
698 | (entsize + (uint)sizeof(xfs_dir_leaf_entry_t))) | |
699 | return(XFS_ERROR(ENOSPC)); | |
700 | ||
701 | if (!args->justcheck) | |
702 | xfs_dir_leaf_add_work(bp, args, index, 0); | |
703 | return(0); | |
704 | } | |
705 | ||
706 | /* | |
707 | * Add a name to a leaf directory structure. | |
708 | */ | |
709 | STATIC void | |
710 | xfs_dir_leaf_add_work(xfs_dabuf_t *bp, xfs_da_args_t *args, int index, | |
711 | int mapindex) | |
712 | { | |
713 | xfs_dir_leafblock_t *leaf; | |
714 | xfs_dir_leaf_hdr_t *hdr; | |
715 | xfs_dir_leaf_entry_t *entry; | |
716 | xfs_dir_leaf_name_t *namest; | |
717 | xfs_dir_leaf_map_t *map; | |
718 | /* REFERENCED */ | |
719 | xfs_mount_t *mp; | |
720 | int tmp, i; | |
721 | ||
722 | leaf = bp->data; | |
723 | ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
724 | hdr = &leaf->hdr; | |
725 | ASSERT((mapindex >= 0) && (mapindex < XFS_DIR_LEAF_MAPSIZE)); | |
726 | ASSERT((index >= 0) && (index <= INT_GET(hdr->count, ARCH_CONVERT))); | |
727 | ||
728 | /* | |
729 | * Force open some space in the entry array and fill it in. | |
730 | */ | |
731 | entry = &leaf->entries[index]; | |
732 | if (index < INT_GET(hdr->count, ARCH_CONVERT)) { | |
733 | tmp = INT_GET(hdr->count, ARCH_CONVERT) - index; | |
734 | tmp *= (uint)sizeof(xfs_dir_leaf_entry_t); | |
735 | ovbcopy(entry, entry + 1, tmp); | |
736 | xfs_da_log_buf(args->trans, bp, | |
737 | XFS_DA_LOGRANGE(leaf, entry, tmp + (uint)sizeof(*entry))); | |
738 | } | |
739 | INT_MOD(hdr->count, ARCH_CONVERT, +1); | |
740 | ||
741 | /* | |
742 | * Allocate space for the new string (at the end of the run). | |
743 | */ | |
744 | map = &hdr->freemap[mapindex]; | |
745 | mp = args->trans->t_mountp; | |
746 | ASSERT(INT_GET(map->base, ARCH_CONVERT) < XFS_LBSIZE(mp)); | |
747 | ASSERT(INT_GET(map->size, ARCH_CONVERT) >= XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen)); | |
748 | ASSERT(INT_GET(map->size, ARCH_CONVERT) < XFS_LBSIZE(mp)); | |
749 | INT_MOD(map->size, ARCH_CONVERT, -(XFS_DIR_LEAF_ENTSIZE_BYNAME(args->namelen))); | |
750 | INT_SET(entry->nameidx, ARCH_CONVERT, INT_GET(map->base, ARCH_CONVERT) + INT_GET(map->size, ARCH_CONVERT)); | |
751 | INT_SET(entry->hashval, ARCH_CONVERT, args->hashval); | |
752 | entry->namelen = args->namelen; | |
753 | xfs_da_log_buf(args->trans, bp, | |
754 | XFS_DA_LOGRANGE(leaf, entry, sizeof(*entry))); | |
755 | ||
756 | /* | |
757 | * Copy the string and inode number into the new space. | |
758 | */ | |
759 | namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); | |
760 | XFS_DIR_SF_PUT_DIRINO_ARCH(&args->inumber, &namest->inumber, ARCH_CONVERT); | |
761 | bcopy(args->name, namest->name, args->namelen); | |
762 | xfs_da_log_buf(args->trans, bp, | |
763 | XFS_DA_LOGRANGE(leaf, namest, XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry))); | |
764 | ||
765 | /* | |
766 | * Update the control info for this leaf node | |
767 | */ | |
768 | if (INT_GET(entry->nameidx, ARCH_CONVERT) < INT_GET(hdr->firstused, ARCH_CONVERT)) | |
769 | INT_COPY(hdr->firstused, entry->nameidx, ARCH_CONVERT); | |
770 | ASSERT(INT_GET(hdr->firstused, ARCH_CONVERT) >= ((INT_GET(hdr->count, ARCH_CONVERT)*sizeof(*entry))+sizeof(*hdr))); | |
771 | tmp = (INT_GET(hdr->count, ARCH_CONVERT)-1) * (uint)sizeof(xfs_dir_leaf_entry_t) | |
772 | + (uint)sizeof(xfs_dir_leaf_hdr_t); | |
773 | map = &hdr->freemap[0]; | |
774 | for (i = 0; i < XFS_DIR_LEAF_MAPSIZE; map++, i++) { | |
775 | if (INT_GET(map->base, ARCH_CONVERT) == tmp) { | |
776 | INT_MOD(map->base, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_entry_t)); | |
777 | INT_MOD(map->size, ARCH_CONVERT, -((uint)sizeof(xfs_dir_leaf_entry_t))); | |
778 | } | |
779 | } | |
780 | INT_MOD(hdr->namebytes, ARCH_CONVERT, args->namelen); | |
781 | xfs_da_log_buf(args->trans, bp, | |
782 | XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr))); | |
783 | } | |
784 | ||
785 | /* | |
786 | * Garbage collect a leaf directory block by copying it to a new buffer. | |
787 | */ | |
788 | STATIC int | |
789 | xfs_dir_leaf_compact(xfs_trans_t *trans, xfs_dabuf_t *bp, int musthave, | |
790 | int justcheck) | |
791 | { | |
792 | xfs_dir_leafblock_t *leaf_s, *leaf_d; | |
793 | xfs_dir_leaf_hdr_t *hdr_s, *hdr_d; | |
794 | xfs_mount_t *mp; | |
795 | char *tmpbuffer; | |
796 | char *tmpbuffer2; | |
797 | int rval; | |
798 | int lbsize; | |
799 | ||
800 | mp = trans->t_mountp; | |
801 | lbsize = XFS_LBSIZE(mp); | |
802 | tmpbuffer = kmem_alloc(lbsize, KM_SLEEP); | |
803 | ASSERT(tmpbuffer != NULL); | |
804 | bcopy(bp->data, tmpbuffer, lbsize); | |
805 | ||
806 | /* | |
807 | * Make a second copy in case xfs_dir_leaf_moveents() | |
808 | * below destroys the original. | |
809 | */ | |
810 | if (musthave || justcheck) { | |
811 | tmpbuffer2 = kmem_alloc(lbsize, KM_SLEEP); | |
812 | bcopy(bp->data, tmpbuffer2, lbsize); | |
813 | } | |
814 | bzero(bp->data, lbsize); | |
815 | ||
816 | /* | |
817 | * Copy basic information | |
818 | */ | |
819 | leaf_s = (xfs_dir_leafblock_t *)tmpbuffer; | |
820 | leaf_d = bp->data; | |
821 | hdr_s = &leaf_s->hdr; | |
822 | hdr_d = &leaf_d->hdr; | |
823 | hdr_d->info = hdr_s->info; /* struct copy */ | |
824 | INT_SET(hdr_d->firstused, ARCH_CONVERT, lbsize); | |
825 | if (INT_GET(hdr_d->firstused, ARCH_CONVERT) == 0) | |
826 | INT_SET(hdr_d->firstused, ARCH_CONVERT, lbsize - 1); | |
827 | INT_ZERO(hdr_d->namebytes, ARCH_CONVERT); | |
828 | INT_ZERO(hdr_d->count, ARCH_CONVERT); | |
829 | hdr_d->holes = 0; | |
830 | INT_SET(hdr_d->freemap[0].base, ARCH_CONVERT, sizeof(xfs_dir_leaf_hdr_t)); | |
831 | INT_SET(hdr_d->freemap[0].size, ARCH_CONVERT, INT_GET(hdr_d->firstused, ARCH_CONVERT) - INT_GET(hdr_d->freemap[0].base, ARCH_CONVERT)); | |
832 | ||
833 | /* | |
834 | * Copy all entry's in the same (sorted) order, | |
835 | * but allocate filenames packed and in sequence. | |
836 | * This changes the source (leaf_s) as well. | |
837 | */ | |
838 | xfs_dir_leaf_moveents(leaf_s, 0, leaf_d, 0, (int)INT_GET(hdr_s->count, ARCH_CONVERT), mp); | |
839 | ||
840 | if (musthave && INT_GET(hdr_d->freemap[0].size, ARCH_CONVERT) < musthave) | |
841 | rval = XFS_ERROR(ENOSPC); | |
842 | else | |
843 | rval = 0; | |
844 | ||
845 | if (justcheck || rval == ENOSPC) { | |
846 | ASSERT(tmpbuffer2); | |
847 | bcopy(tmpbuffer2, bp->data, lbsize); | |
848 | } else { | |
849 | xfs_da_log_buf(trans, bp, 0, lbsize - 1); | |
850 | } | |
851 | ||
852 | kmem_free(tmpbuffer, lbsize); | |
853 | if (musthave || justcheck) | |
854 | kmem_free(tmpbuffer2, lbsize); | |
855 | return(rval); | |
856 | } | |
857 | ||
858 | /* | |
859 | * Redistribute the directory entries between two leaf nodes, | |
860 | * taking into account the size of the new entry. | |
861 | * | |
862 | * NOTE: if new block is empty, then it will get the upper half of old block. | |
863 | */ | |
864 | STATIC void | |
865 | xfs_dir_leaf_rebalance(xfs_da_state_t *state, xfs_da_state_blk_t *blk1, | |
866 | xfs_da_state_blk_t *blk2) | |
867 | { | |
868 | xfs_da_state_blk_t *tmp_blk; | |
869 | xfs_dir_leafblock_t *leaf1, *leaf2; | |
870 | xfs_dir_leaf_hdr_t *hdr1, *hdr2; | |
871 | int count, totallen, max, space, swap; | |
872 | ||
873 | /* | |
874 | * Set up environment. | |
875 | */ | |
876 | ASSERT(blk1->magic == XFS_DIR_LEAF_MAGIC); | |
877 | ASSERT(blk2->magic == XFS_DIR_LEAF_MAGIC); | |
878 | leaf1 = blk1->bp->data; | |
879 | leaf2 = blk2->bp->data; | |
880 | ASSERT(INT_GET(leaf1->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
881 | ASSERT(INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
882 | ||
883 | /* | |
884 | * Check ordering of blocks, reverse if it makes things simpler. | |
885 | */ | |
886 | swap = 0; | |
887 | if (xfs_dir_leaf_order(blk1->bp, blk2->bp)) { | |
888 | tmp_blk = blk1; | |
889 | blk1 = blk2; | |
890 | blk2 = tmp_blk; | |
891 | leaf1 = blk1->bp->data; | |
892 | leaf2 = blk2->bp->data; | |
893 | swap = 1; | |
894 | } | |
895 | hdr1 = &leaf1->hdr; | |
896 | hdr2 = &leaf2->hdr; | |
897 | ||
898 | /* | |
899 | * Examine entries until we reduce the absolute difference in | |
900 | * byte usage between the two blocks to a minimum. Then get | |
901 | * the direction to copy and the number of elements to move. | |
902 | */ | |
903 | state->inleaf = xfs_dir_leaf_figure_balance(state, blk1, blk2, | |
904 | &count, &totallen); | |
905 | if (swap) | |
906 | state->inleaf = !state->inleaf; | |
907 | ||
908 | /* | |
909 | * Move any entries required from leaf to leaf: | |
910 | */ | |
911 | if (count < INT_GET(hdr1->count, ARCH_CONVERT)) { | |
912 | /* | |
913 | * Figure the total bytes to be added to the destination leaf. | |
914 | */ | |
915 | count = INT_GET(hdr1->count, ARCH_CONVERT) - count; /* number entries being moved */ | |
916 | space = INT_GET(hdr1->namebytes, ARCH_CONVERT) - totallen; | |
917 | space += count * ((uint)sizeof(xfs_dir_leaf_name_t)-1); | |
918 | space += count * (uint)sizeof(xfs_dir_leaf_entry_t); | |
919 | ||
920 | /* | |
921 | * leaf2 is the destination, compact it if it looks tight. | |
922 | */ | |
923 | max = INT_GET(hdr2->firstused, ARCH_CONVERT) - (uint)sizeof(xfs_dir_leaf_hdr_t); | |
924 | max -= INT_GET(hdr2->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t); | |
925 | if (space > max) { | |
926 | xfs_dir_leaf_compact(state->args->trans, blk2->bp, | |
927 | 0, 0); | |
928 | } | |
929 | ||
930 | /* | |
931 | * Move high entries from leaf1 to low end of leaf2. | |
932 | */ | |
933 | xfs_dir_leaf_moveents(leaf1, INT_GET(hdr1->count, ARCH_CONVERT) - count, | |
934 | leaf2, 0, count, state->mp); | |
935 | ||
936 | xfs_da_log_buf(state->args->trans, blk1->bp, 0, | |
937 | state->blocksize-1); | |
938 | xfs_da_log_buf(state->args->trans, blk2->bp, 0, | |
939 | state->blocksize-1); | |
940 | ||
941 | } else if (count > INT_GET(hdr1->count, ARCH_CONVERT)) { | |
942 | /* | |
943 | * Figure the total bytes to be added to the destination leaf. | |
944 | */ | |
945 | count -= INT_GET(hdr1->count, ARCH_CONVERT); /* number entries being moved */ | |
946 | space = totallen - INT_GET(hdr1->namebytes, ARCH_CONVERT); | |
947 | space += count * ((uint)sizeof(xfs_dir_leaf_name_t)-1); | |
948 | space += count * (uint)sizeof(xfs_dir_leaf_entry_t); | |
949 | ||
950 | /* | |
951 | * leaf1 is the destination, compact it if it looks tight. | |
952 | */ | |
953 | max = INT_GET(hdr1->firstused, ARCH_CONVERT) - (uint)sizeof(xfs_dir_leaf_hdr_t); | |
954 | max -= INT_GET(hdr1->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t); | |
955 | if (space > max) { | |
956 | xfs_dir_leaf_compact(state->args->trans, blk1->bp, | |
957 | 0, 0); | |
958 | } | |
959 | ||
960 | /* | |
961 | * Move low entries from leaf2 to high end of leaf1. | |
962 | */ | |
963 | xfs_dir_leaf_moveents(leaf2, 0, leaf1, (int)INT_GET(hdr1->count, ARCH_CONVERT), | |
964 | count, state->mp); | |
965 | ||
966 | xfs_da_log_buf(state->args->trans, blk1->bp, 0, | |
967 | state->blocksize-1); | |
968 | xfs_da_log_buf(state->args->trans, blk2->bp, 0, | |
969 | state->blocksize-1); | |
970 | } | |
971 | ||
972 | /* | |
973 | * Copy out last hashval in each block for B-tree code. | |
974 | */ | |
975 | blk1->hashval = INT_GET(leaf1->entries[ INT_GET(leaf1->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT); | |
976 | blk2->hashval = INT_GET(leaf2->entries[ INT_GET(leaf2->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT); | |
977 | ||
978 | /* | |
979 | * Adjust the expected index for insertion. | |
980 | * GROT: this doesn't work unless blk2 was originally empty. | |
981 | */ | |
982 | if (!state->inleaf) { | |
983 | blk2->index = blk1->index - INT_GET(leaf1->hdr.count, ARCH_CONVERT); | |
984 | } | |
985 | } | |
986 | ||
987 | /* | |
988 | * Examine entries until we reduce the absolute difference in | |
989 | * byte usage between the two blocks to a minimum. | |
990 | * GROT: Is this really necessary? With other than a 512 byte blocksize, | |
991 | * GROT: there will always be enough room in either block for a new entry. | |
992 | * GROT: Do a double-split for this case? | |
993 | */ | |
994 | STATIC int | |
995 | xfs_dir_leaf_figure_balance(xfs_da_state_t *state, | |
996 | xfs_da_state_blk_t *blk1, | |
997 | xfs_da_state_blk_t *blk2, | |
998 | int *countarg, int *namebytesarg) | |
999 | { | |
1000 | xfs_dir_leafblock_t *leaf1, *leaf2; | |
1001 | xfs_dir_leaf_hdr_t *hdr1, *hdr2; | |
1002 | xfs_dir_leaf_entry_t *entry; | |
1003 | int count, max, totallen, half; | |
1004 | int lastdelta, foundit, tmp; | |
1005 | ||
1006 | /* | |
1007 | * Set up environment. | |
1008 | */ | |
1009 | leaf1 = blk1->bp->data; | |
1010 | leaf2 = blk2->bp->data; | |
1011 | hdr1 = &leaf1->hdr; | |
1012 | hdr2 = &leaf2->hdr; | |
1013 | foundit = 0; | |
1014 | totallen = 0; | |
1015 | ||
1016 | /* | |
1017 | * Examine entries until we reduce the absolute difference in | |
1018 | * byte usage between the two blocks to a minimum. | |
1019 | */ | |
1020 | max = INT_GET(hdr1->count, ARCH_CONVERT) + INT_GET(hdr2->count, ARCH_CONVERT); | |
1021 | half = (max+1) * (uint)(sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1); | |
1022 | half += INT_GET(hdr1->namebytes, ARCH_CONVERT) + INT_GET(hdr2->namebytes, ARCH_CONVERT) + state->args->namelen; | |
1023 | half /= 2; | |
1024 | lastdelta = state->blocksize; | |
1025 | entry = &leaf1->entries[0]; | |
1026 | for (count = 0; count < max; entry++, count++) { | |
1027 | ||
1028 | #define XFS_DIR_ABS(A) (((A) < 0) ? -(A) : (A)) | |
1029 | /* | |
1030 | * The new entry is in the first block, account for it. | |
1031 | */ | |
1032 | if (count == blk1->index) { | |
1033 | tmp = totallen + (uint)sizeof(*entry) | |
1034 | + XFS_DIR_LEAF_ENTSIZE_BYNAME(state->args->namelen); | |
1035 | if (XFS_DIR_ABS(half - tmp) > lastdelta) | |
1036 | break; | |
1037 | lastdelta = XFS_DIR_ABS(half - tmp); | |
1038 | totallen = tmp; | |
1039 | foundit = 1; | |
1040 | } | |
1041 | ||
1042 | /* | |
1043 | * Wrap around into the second block if necessary. | |
1044 | */ | |
1045 | if (count == INT_GET(hdr1->count, ARCH_CONVERT)) { | |
1046 | leaf1 = leaf2; | |
1047 | entry = &leaf1->entries[0]; | |
1048 | } | |
1049 | ||
1050 | /* | |
1051 | * Figure out if next leaf entry would be too much. | |
1052 | */ | |
1053 | tmp = totallen + (uint)sizeof(*entry) | |
1054 | + XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry); | |
1055 | if (XFS_DIR_ABS(half - tmp) > lastdelta) | |
1056 | break; | |
1057 | lastdelta = XFS_DIR_ABS(half - tmp); | |
1058 | totallen = tmp; | |
1059 | #undef XFS_DIR_ABS | |
1060 | } | |
1061 | ||
1062 | /* | |
1063 | * Calculate the number of namebytes that will end up in lower block. | |
1064 | * If new entry not in lower block, fix up the count. | |
1065 | */ | |
1066 | totallen -= | |
1067 | count * (uint)(sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1); | |
1068 | if (foundit) { | |
1069 | totallen -= (sizeof(*entry)+sizeof(xfs_dir_leaf_entry_t)-1) + | |
1070 | state->args->namelen; | |
1071 | } | |
1072 | ||
1073 | *countarg = count; | |
1074 | *namebytesarg = totallen; | |
1075 | return(foundit); | |
1076 | } | |
1077 | ||
1078 | /*======================================================================== | |
1079 | * Routines used for shrinking the Btree. | |
1080 | *========================================================================*/ | |
1081 | ||
1082 | /* | |
1083 | * Check a leaf block and its neighbors to see if the block should be | |
1084 | * collapsed into one or the other neighbor. Always keep the block | |
1085 | * with the smaller block number. | |
1086 | * If the current block is over 50% full, don't try to join it, return 0. | |
1087 | * If the block is empty, fill in the state structure and return 2. | |
1088 | * If it can be collapsed, fill in the state structure and return 1. | |
1089 | * If nothing can be done, return 0. | |
1090 | */ | |
1091 | int | |
1092 | xfs_dir_leaf_toosmall(xfs_da_state_t *state, int *action) | |
1093 | { | |
1094 | xfs_dir_leafblock_t *leaf; | |
1095 | xfs_da_state_blk_t *blk; | |
1096 | xfs_da_blkinfo_t *info; | |
1097 | int count, bytes, forward, error, retval, i; | |
1098 | xfs_dablk_t blkno; | |
1099 | xfs_dabuf_t *bp; | |
1100 | ||
1101 | /* | |
1102 | * Check for the degenerate case of the block being over 50% full. | |
1103 | * If so, it's not worth even looking to see if we might be able | |
1104 | * to coalesce with a sibling. | |
1105 | */ | |
1106 | blk = &state->path.blk[ state->path.active-1 ]; | |
1107 | info = blk->bp->data; | |
1108 | ASSERT(INT_GET(info->magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
1109 | leaf = (xfs_dir_leafblock_t *)info; | |
1110 | count = INT_GET(leaf->hdr.count, ARCH_CONVERT); | |
1111 | bytes = (uint)sizeof(xfs_dir_leaf_hdr_t) + | |
1112 | count * (uint)sizeof(xfs_dir_leaf_entry_t) + | |
1113 | count * ((uint)sizeof(xfs_dir_leaf_name_t)-1) + | |
1114 | INT_GET(leaf->hdr.namebytes, ARCH_CONVERT); | |
1115 | if (bytes > (state->blocksize >> 1)) { | |
1116 | *action = 0; /* blk over 50%, dont try to join */ | |
1117 | return(0); | |
1118 | } | |
1119 | ||
1120 | /* | |
1121 | * Check for the degenerate case of the block being empty. | |
1122 | * If the block is empty, we'll simply delete it, no need to | |
1123 | * coalesce it with a sibling block. We choose (aribtrarily) | |
1124 | * to merge with the forward block unless it is NULL. | |
1125 | */ | |
1126 | if (count == 0) { | |
1127 | /* | |
1128 | * Make altpath point to the block we want to keep and | |
1129 | * path point to the block we want to drop (this one). | |
1130 | */ | |
1131 | forward = !INT_ISZERO(info->forw, ARCH_CONVERT); | |
1132 | bcopy(&state->path, &state->altpath, sizeof(state->path)); | |
1133 | error = xfs_da_path_shift(state, &state->altpath, forward, | |
1134 | 0, &retval); | |
1135 | if (error) | |
1136 | return(error); | |
1137 | if (retval) { | |
1138 | *action = 0; | |
1139 | } else { | |
1140 | *action = 2; | |
1141 | } | |
1142 | return(0); | |
1143 | } | |
1144 | ||
1145 | /* | |
1146 | * Examine each sibling block to see if we can coalesce with | |
1147 | * at least 25% free space to spare. We need to figure out | |
1148 | * whether to merge with the forward or the backward block. | |
1149 | * We prefer coalescing with the lower numbered sibling so as | |
1150 | * to shrink a directory over time. | |
1151 | */ | |
1152 | forward = (INT_GET(info->forw, ARCH_CONVERT) < INT_GET(info->back, ARCH_CONVERT)); /* start with smaller blk num */ | |
1153 | for (i = 0; i < 2; forward = !forward, i++) { | |
1154 | if (forward) | |
1155 | blkno = INT_GET(info->forw, ARCH_CONVERT); | |
1156 | else | |
1157 | blkno = INT_GET(info->back, ARCH_CONVERT); | |
1158 | if (blkno == 0) | |
1159 | continue; | |
1160 | error = xfs_da_read_buf(state->args->trans, state->args->dp, | |
1161 | blkno, -1, &bp, | |
1162 | XFS_DATA_FORK); | |
1163 | if (error) | |
1164 | return(error); | |
1165 | ASSERT(bp != NULL); | |
1166 | ||
1167 | leaf = (xfs_dir_leafblock_t *)info; | |
1168 | count = INT_GET(leaf->hdr.count, ARCH_CONVERT); | |
1169 | bytes = state->blocksize - (state->blocksize>>2); | |
1170 | bytes -= INT_GET(leaf->hdr.namebytes, ARCH_CONVERT); | |
1171 | leaf = bp->data; | |
1172 | ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
1173 | count += INT_GET(leaf->hdr.count, ARCH_CONVERT); | |
1174 | bytes -= INT_GET(leaf->hdr.namebytes, ARCH_CONVERT); | |
1175 | bytes -= count * ((uint)sizeof(xfs_dir_leaf_name_t) - 1); | |
1176 | bytes -= count * (uint)sizeof(xfs_dir_leaf_entry_t); | |
1177 | bytes -= (uint)sizeof(xfs_dir_leaf_hdr_t); | |
1178 | if (bytes >= 0) | |
1179 | break; /* fits with at least 25% to spare */ | |
1180 | ||
1181 | xfs_da_brelse(state->args->trans, bp); | |
1182 | } | |
1183 | if (i >= 2) { | |
1184 | *action = 0; | |
1185 | return(0); | |
1186 | } | |
1187 | xfs_da_buf_done(bp); | |
1188 | ||
1189 | /* | |
1190 | * Make altpath point to the block we want to keep (the lower | |
1191 | * numbered block) and path point to the block we want to drop. | |
1192 | */ | |
1193 | bcopy(&state->path, &state->altpath, sizeof(state->path)); | |
1194 | if (blkno < blk->blkno) { | |
1195 | error = xfs_da_path_shift(state, &state->altpath, forward, | |
1196 | 0, &retval); | |
1197 | } else { | |
1198 | error = xfs_da_path_shift(state, &state->path, forward, | |
1199 | 0, &retval); | |
1200 | } | |
1201 | if (error) | |
1202 | return(error); | |
1203 | if (retval) { | |
1204 | *action = 0; | |
1205 | } else { | |
1206 | *action = 1; | |
1207 | } | |
1208 | return(0); | |
1209 | } | |
1210 | ||
1211 | /* | |
1212 | * Remove a name from the leaf directory structure. | |
1213 | * | |
1214 | * Return 1 if leaf is less than 37% full, 0 if >= 37% full. | |
1215 | * If two leaves are 37% full, when combined they will leave 25% free. | |
1216 | */ | |
1217 | int | |
1218 | xfs_dir_leaf_remove(xfs_trans_t *trans, xfs_dabuf_t *bp, int index) | |
1219 | { | |
1220 | xfs_dir_leafblock_t *leaf; | |
1221 | xfs_dir_leaf_hdr_t *hdr; | |
1222 | xfs_dir_leaf_map_t *map; | |
1223 | xfs_dir_leaf_entry_t *entry; | |
1224 | xfs_dir_leaf_name_t *namest; | |
1225 | int before, after, smallest, entsize; | |
1226 | int tablesize, tmp, i; | |
1227 | xfs_mount_t *mp; | |
1228 | ||
1229 | leaf = bp->data; | |
1230 | ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
1231 | hdr = &leaf->hdr; | |
1232 | mp = trans->t_mountp; | |
1233 | ASSERT((INT_GET(hdr->count, ARCH_CONVERT) > 0) && (INT_GET(hdr->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8))); | |
1234 | ASSERT((index >= 0) && (index < INT_GET(hdr->count, ARCH_CONVERT))); | |
1235 | ASSERT(INT_GET(hdr->firstused, ARCH_CONVERT) >= ((INT_GET(hdr->count, ARCH_CONVERT)*sizeof(*entry))+sizeof(*hdr))); | |
1236 | entry = &leaf->entries[index]; | |
1237 | ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) >= INT_GET(hdr->firstused, ARCH_CONVERT)); | |
1238 | ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) < XFS_LBSIZE(mp)); | |
1239 | ||
1240 | /* | |
1241 | * Scan through free region table: | |
1242 | * check for adjacency of free'd entry with an existing one, | |
1243 | * find smallest free region in case we need to replace it, | |
1244 | * adjust any map that borders the entry table, | |
1245 | */ | |
1246 | tablesize = INT_GET(hdr->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t) | |
1247 | + (uint)sizeof(xfs_dir_leaf_hdr_t); | |
1248 | map = &hdr->freemap[0]; | |
1249 | tmp = INT_GET(map->size, ARCH_CONVERT); | |
1250 | before = after = -1; | |
1251 | smallest = XFS_DIR_LEAF_MAPSIZE - 1; | |
1252 | entsize = XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry); | |
1253 | for (i = 0; i < XFS_DIR_LEAF_MAPSIZE; map++, i++) { | |
1254 | ASSERT(INT_GET(map->base, ARCH_CONVERT) < XFS_LBSIZE(mp)); | |
1255 | ASSERT(INT_GET(map->size, ARCH_CONVERT) < XFS_LBSIZE(mp)); | |
1256 | if (INT_GET(map->base, ARCH_CONVERT) == tablesize) { | |
1257 | INT_MOD(map->base, ARCH_CONVERT, -((uint)sizeof(xfs_dir_leaf_entry_t))); | |
1258 | INT_MOD(map->size, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_entry_t)); | |
1259 | } | |
1260 | ||
1261 | if ((INT_GET(map->base, ARCH_CONVERT) + INT_GET(map->size, ARCH_CONVERT)) == INT_GET(entry->nameidx, ARCH_CONVERT)) { | |
1262 | before = i; | |
1263 | } else if (INT_GET(map->base, ARCH_CONVERT) == (INT_GET(entry->nameidx, ARCH_CONVERT) + entsize)) { | |
1264 | after = i; | |
1265 | } else if (INT_GET(map->size, ARCH_CONVERT) < tmp) { | |
1266 | tmp = INT_GET(map->size, ARCH_CONVERT); | |
1267 | smallest = i; | |
1268 | } | |
1269 | } | |
1270 | ||
1271 | /* | |
1272 | * Coalesce adjacent freemap regions, | |
1273 | * or replace the smallest region. | |
1274 | */ | |
1275 | if ((before >= 0) || (after >= 0)) { | |
1276 | if ((before >= 0) && (after >= 0)) { | |
1277 | map = &hdr->freemap[before]; | |
1278 | INT_MOD(map->size, ARCH_CONVERT, entsize); | |
1279 | INT_MOD(map->size, ARCH_CONVERT, INT_GET(hdr->freemap[after].size, ARCH_CONVERT)); | |
1280 | INT_ZERO(hdr->freemap[after].base, ARCH_CONVERT); | |
1281 | INT_ZERO(hdr->freemap[after].size, ARCH_CONVERT); | |
1282 | } else if (before >= 0) { | |
1283 | map = &hdr->freemap[before]; | |
1284 | INT_MOD(map->size, ARCH_CONVERT, entsize); | |
1285 | } else { | |
1286 | map = &hdr->freemap[after]; | |
1287 | INT_COPY(map->base, entry->nameidx, ARCH_CONVERT); | |
1288 | INT_MOD(map->size, ARCH_CONVERT, entsize); | |
1289 | } | |
1290 | } else { | |
1291 | /* | |
1292 | * Replace smallest region (if it is smaller than free'd entry) | |
1293 | */ | |
1294 | map = &hdr->freemap[smallest]; | |
1295 | if (INT_GET(map->size, ARCH_CONVERT) < entsize) { | |
1296 | INT_COPY(map->base, entry->nameidx, ARCH_CONVERT); | |
1297 | INT_SET(map->size, ARCH_CONVERT, entsize); | |
1298 | } | |
1299 | } | |
1300 | ||
1301 | /* | |
1302 | * Did we remove the first entry? | |
1303 | */ | |
1304 | if (INT_GET(entry->nameidx, ARCH_CONVERT) == INT_GET(hdr->firstused, ARCH_CONVERT)) | |
1305 | smallest = 1; | |
1306 | else | |
1307 | smallest = 0; | |
1308 | ||
1309 | /* | |
1310 | * Compress the remaining entries and zero out the removed stuff. | |
1311 | */ | |
1312 | namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); | |
1313 | bzero((char *)namest, entsize); | |
1314 | xfs_da_log_buf(trans, bp, XFS_DA_LOGRANGE(leaf, namest, entsize)); | |
1315 | ||
1316 | INT_MOD(hdr->namebytes, ARCH_CONVERT, -(entry->namelen)); | |
1317 | tmp = (INT_GET(hdr->count, ARCH_CONVERT) - index) * (uint)sizeof(xfs_dir_leaf_entry_t); | |
1318 | ovbcopy(entry + 1, entry, tmp); | |
1319 | INT_MOD(hdr->count, ARCH_CONVERT, -1); | |
1320 | xfs_da_log_buf(trans, bp, | |
1321 | XFS_DA_LOGRANGE(leaf, entry, tmp + (uint)sizeof(*entry))); | |
1322 | entry = &leaf->entries[INT_GET(hdr->count, ARCH_CONVERT)]; | |
1323 | bzero((char *)entry, sizeof(xfs_dir_leaf_entry_t)); | |
1324 | ||
1325 | /* | |
1326 | * If we removed the first entry, re-find the first used byte | |
1327 | * in the name area. Note that if the entry was the "firstused", | |
1328 | * then we don't have a "hole" in our block resulting from | |
1329 | * removing the name. | |
1330 | */ | |
1331 | if (smallest) { | |
1332 | tmp = XFS_LBSIZE(mp); | |
1333 | entry = &leaf->entries[0]; | |
1334 | for (i = INT_GET(hdr->count, ARCH_CONVERT)-1; i >= 0; entry++, i--) { | |
1335 | ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) >= INT_GET(hdr->firstused, ARCH_CONVERT)); | |
1336 | ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) < XFS_LBSIZE(mp)); | |
1337 | if (INT_GET(entry->nameidx, ARCH_CONVERT) < tmp) | |
1338 | tmp = INT_GET(entry->nameidx, ARCH_CONVERT); | |
1339 | } | |
1340 | INT_SET(hdr->firstused, ARCH_CONVERT, tmp); | |
1341 | if (INT_GET(hdr->firstused, ARCH_CONVERT) == 0) | |
1342 | INT_SET(hdr->firstused, ARCH_CONVERT, tmp - 1); | |
1343 | } else { | |
1344 | hdr->holes = 1; /* mark as needing compaction */ | |
1345 | } | |
1346 | ||
1347 | xfs_da_log_buf(trans, bp, XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr))); | |
1348 | ||
1349 | /* | |
1350 | * Check if leaf is less than 50% full, caller may want to | |
1351 | * "join" the leaf with a sibling if so. | |
1352 | */ | |
1353 | tmp = (uint)sizeof(xfs_dir_leaf_hdr_t); | |
1354 | tmp += INT_GET(leaf->hdr.count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t); | |
1355 | tmp += INT_GET(leaf->hdr.count, ARCH_CONVERT) * ((uint)sizeof(xfs_dir_leaf_name_t) - 1); | |
1356 | tmp += INT_GET(leaf->hdr.namebytes, ARCH_CONVERT); | |
1357 | if (tmp < mp->m_dir_magicpct) | |
1358 | return(1); /* leaf is < 37% full */ | |
1359 | return(0); | |
1360 | } | |
1361 | ||
1362 | /* | |
1363 | * Move all the directory entries from drop_leaf into save_leaf. | |
1364 | */ | |
1365 | void | |
1366 | xfs_dir_leaf_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk, | |
1367 | xfs_da_state_blk_t *save_blk) | |
1368 | { | |
1369 | xfs_dir_leafblock_t *drop_leaf, *save_leaf, *tmp_leaf; | |
1370 | xfs_dir_leaf_hdr_t *drop_hdr, *save_hdr, *tmp_hdr; | |
1371 | xfs_mount_t *mp; | |
1372 | char *tmpbuffer; | |
1373 | ||
1374 | /* | |
1375 | * Set up environment. | |
1376 | */ | |
1377 | mp = state->mp; | |
1378 | ASSERT(drop_blk->magic == XFS_DIR_LEAF_MAGIC); | |
1379 | ASSERT(save_blk->magic == XFS_DIR_LEAF_MAGIC); | |
1380 | drop_leaf = drop_blk->bp->data; | |
1381 | save_leaf = save_blk->bp->data; | |
1382 | ASSERT(INT_GET(drop_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
1383 | ASSERT(INT_GET(save_leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
1384 | drop_hdr = &drop_leaf->hdr; | |
1385 | save_hdr = &save_leaf->hdr; | |
1386 | ||
1387 | /* | |
1388 | * Save last hashval from dying block for later Btree fixup. | |
1389 | */ | |
1390 | drop_blk->hashval = INT_GET(drop_leaf->entries[ drop_leaf->hdr.count-1 ].hashval, ARCH_CONVERT); | |
1391 | ||
1392 | /* | |
1393 | * Check if we need a temp buffer, or can we do it in place. | |
1394 | * Note that we don't check "leaf" for holes because we will | |
1395 | * always be dropping it, toosmall() decided that for us already. | |
1396 | */ | |
1397 | if (save_hdr->holes == 0) { | |
1398 | /* | |
1399 | * dest leaf has no holes, so we add there. May need | |
1400 | * to make some room in the entry array. | |
1401 | */ | |
1402 | if (xfs_dir_leaf_order(save_blk->bp, drop_blk->bp)) { | |
1403 | xfs_dir_leaf_moveents(drop_leaf, 0, save_leaf, 0, | |
1404 | (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp); | |
1405 | } else { | |
1406 | xfs_dir_leaf_moveents(drop_leaf, 0, | |
1407 | save_leaf, INT_GET(save_hdr->count, ARCH_CONVERT), | |
1408 | (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp); | |
1409 | } | |
1410 | } else { | |
1411 | /* | |
1412 | * Destination has holes, so we make a temporary copy | |
1413 | * of the leaf and add them both to that. | |
1414 | */ | |
1415 | tmpbuffer = kmem_alloc(state->blocksize, KM_SLEEP); | |
1416 | ASSERT(tmpbuffer != NULL); | |
1417 | bzero(tmpbuffer, state->blocksize); | |
1418 | tmp_leaf = (xfs_dir_leafblock_t *)tmpbuffer; | |
1419 | tmp_hdr = &tmp_leaf->hdr; | |
1420 | tmp_hdr->info = save_hdr->info; /* struct copy */ | |
1421 | INT_ZERO(tmp_hdr->count, ARCH_CONVERT); | |
1422 | INT_SET(tmp_hdr->firstused, ARCH_CONVERT, state->blocksize); | |
1423 | if (INT_GET(tmp_hdr->firstused, ARCH_CONVERT) == 0) | |
1424 | INT_SET(tmp_hdr->firstused, ARCH_CONVERT, state->blocksize - 1); | |
1425 | INT_ZERO(tmp_hdr->namebytes, ARCH_CONVERT); | |
1426 | if (xfs_dir_leaf_order(save_blk->bp, drop_blk->bp)) { | |
1427 | xfs_dir_leaf_moveents(drop_leaf, 0, tmp_leaf, 0, | |
1428 | (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp); | |
1429 | xfs_dir_leaf_moveents(save_leaf, 0, | |
1430 | tmp_leaf, INT_GET(tmp_leaf->hdr.count, ARCH_CONVERT), | |
1431 | (int)INT_GET(save_hdr->count, ARCH_CONVERT), mp); | |
1432 | } else { | |
1433 | xfs_dir_leaf_moveents(save_leaf, 0, tmp_leaf, 0, | |
1434 | (int)INT_GET(save_hdr->count, ARCH_CONVERT), mp); | |
1435 | xfs_dir_leaf_moveents(drop_leaf, 0, | |
1436 | tmp_leaf, INT_GET(tmp_leaf->hdr.count, ARCH_CONVERT), | |
1437 | (int)INT_GET(drop_hdr->count, ARCH_CONVERT), mp); | |
1438 | } | |
1439 | bcopy(tmp_leaf, save_leaf, state->blocksize); | |
1440 | kmem_free(tmpbuffer, state->blocksize); | |
1441 | } | |
1442 | ||
1443 | xfs_da_log_buf(state->args->trans, save_blk->bp, 0, | |
1444 | state->blocksize - 1); | |
1445 | ||
1446 | /* | |
1447 | * Copy out last hashval in each block for B-tree code. | |
1448 | */ | |
1449 | save_blk->hashval = INT_GET(save_leaf->entries[ INT_GET(save_leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT); | |
1450 | } | |
1451 | ||
1452 | ||
1453 | /*======================================================================== | |
1454 | * Routines used for finding things in the Btree. | |
1455 | *========================================================================*/ | |
1456 | ||
1457 | /* | |
1458 | * Look up a name in a leaf directory structure. | |
1459 | * This is the internal routine, it uses the caller's buffer. | |
1460 | * | |
1461 | * Note that duplicate keys are allowed, but only check within the | |
1462 | * current leaf node. The Btree code must check in adjacent leaf nodes. | |
1463 | * | |
1464 | * Return in *index the index into the entry[] array of either the found | |
1465 | * entry, or where the entry should have been (insert before that entry). | |
1466 | * | |
1467 | * Don't change the args->inumber unless we find the filename. | |
1468 | */ | |
1469 | int | |
1470 | xfs_dir_leaf_lookup_int(xfs_dabuf_t *bp, xfs_da_args_t *args, int *index) | |
1471 | { | |
1472 | xfs_dir_leafblock_t *leaf; | |
1473 | xfs_dir_leaf_entry_t *entry; | |
1474 | xfs_dir_leaf_name_t *namest; | |
1475 | int probe, span; | |
1476 | xfs_dahash_t hashval; | |
1477 | ||
1478 | leaf = bp->data; | |
1479 | ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
1480 | ASSERT(INT_GET(leaf->hdr.count, ARCH_CONVERT) < (XFS_LBSIZE(args->dp->i_mount)/8)); | |
1481 | ||
1482 | /* | |
1483 | * Binary search. (note: small blocks will skip this loop) | |
1484 | */ | |
1485 | hashval = args->hashval; | |
1486 | probe = span = INT_GET(leaf->hdr.count, ARCH_CONVERT) / 2; | |
1487 | for (entry = &leaf->entries[probe]; span > 4; | |
1488 | entry = &leaf->entries[probe]) { | |
1489 | span /= 2; | |
1490 | if (INT_GET(entry->hashval, ARCH_CONVERT) < hashval) | |
1491 | probe += span; | |
1492 | else if (INT_GET(entry->hashval, ARCH_CONVERT) > hashval) | |
1493 | probe -= span; | |
1494 | else | |
1495 | break; | |
1496 | } | |
1497 | ASSERT((probe >= 0) && \ | |
1498 | ((INT_GET(leaf->hdr.count, ARCH_CONVERT) == 0) || (probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)))); | |
1499 | ASSERT((span <= 4) || (INT_GET(entry->hashval, ARCH_CONVERT) == hashval)); | |
1500 | ||
1501 | /* | |
1502 | * Since we may have duplicate hashval's, find the first matching | |
1503 | * hashval in the leaf. | |
1504 | */ | |
1505 | while ((probe > 0) && (INT_GET(entry->hashval, ARCH_CONVERT) >= hashval)) { | |
1506 | entry--; | |
1507 | probe--; | |
1508 | } | |
1509 | while ((probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)) && (INT_GET(entry->hashval, ARCH_CONVERT) < hashval)) { | |
1510 | entry++; | |
1511 | probe++; | |
1512 | } | |
1513 | if ((probe == INT_GET(leaf->hdr.count, ARCH_CONVERT)) || (INT_GET(entry->hashval, ARCH_CONVERT) != hashval)) { | |
1514 | *index = probe; | |
1515 | ASSERT(args->oknoent); | |
1516 | return(XFS_ERROR(ENOENT)); | |
1517 | } | |
1518 | ||
1519 | /* | |
1520 | * Duplicate keys may be present, so search all of them for a match. | |
1521 | */ | |
1522 | while ((probe < INT_GET(leaf->hdr.count, ARCH_CONVERT)) && (INT_GET(entry->hashval, ARCH_CONVERT) == hashval)) { | |
1523 | namest = XFS_DIR_LEAF_NAMESTRUCT(leaf, INT_GET(entry->nameidx, ARCH_CONVERT)); | |
1524 | if (entry->namelen == args->namelen && | |
1525 | namest->name[0] == args->name[0] && | |
1526 | bcmp(args->name, namest->name, args->namelen) == 0) { | |
1527 | XFS_DIR_SF_GET_DIRINO_ARCH(&namest->inumber, &args->inumber, ARCH_CONVERT); | |
1528 | *index = probe; | |
1529 | return(XFS_ERROR(EEXIST)); | |
1530 | } | |
1531 | entry++; | |
1532 | probe++; | |
1533 | } | |
1534 | *index = probe; | |
1535 | ASSERT(probe == INT_GET(leaf->hdr.count, ARCH_CONVERT) || args->oknoent); | |
1536 | return(XFS_ERROR(ENOENT)); | |
1537 | } | |
1538 | ||
1539 | /*======================================================================== | |
1540 | * Utility routines. | |
1541 | *========================================================================*/ | |
1542 | ||
1543 | /* | |
1544 | * Move the indicated entries from one leaf to another. | |
1545 | * NOTE: this routine modifies both source and destination leaves. | |
1546 | */ | |
1547 | /* ARGSUSED */ | |
1548 | STATIC void | |
1549 | xfs_dir_leaf_moveents(xfs_dir_leafblock_t *leaf_s, int start_s, | |
1550 | xfs_dir_leafblock_t *leaf_d, int start_d, | |
1551 | int count, xfs_mount_t *mp) | |
1552 | { | |
1553 | xfs_dir_leaf_hdr_t *hdr_s, *hdr_d; | |
1554 | xfs_dir_leaf_entry_t *entry_s, *entry_d; | |
1555 | int tmp, i; | |
1556 | ||
1557 | /* | |
1558 | * Check for nothing to do. | |
1559 | */ | |
1560 | if (count == 0) | |
1561 | return; | |
1562 | ||
1563 | /* | |
1564 | * Set up environment. | |
1565 | */ | |
1566 | ASSERT(INT_GET(leaf_s->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
1567 | ASSERT(INT_GET(leaf_d->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
1568 | hdr_s = &leaf_s->hdr; | |
1569 | hdr_d = &leaf_d->hdr; | |
1570 | ASSERT((INT_GET(hdr_s->count, ARCH_CONVERT) > 0) && (INT_GET(hdr_s->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8))); | |
1571 | ASSERT(INT_GET(hdr_s->firstused, ARCH_CONVERT) >= | |
1572 | ((INT_GET(hdr_s->count, ARCH_CONVERT)*sizeof(*entry_s))+sizeof(*hdr_s))); | |
1573 | ASSERT(INT_GET(hdr_d->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8)); | |
1574 | ASSERT(INT_GET(hdr_d->firstused, ARCH_CONVERT) >= | |
1575 | ((INT_GET(hdr_d->count, ARCH_CONVERT)*sizeof(*entry_d))+sizeof(*hdr_d))); | |
1576 | ||
1577 | ASSERT(start_s < INT_GET(hdr_s->count, ARCH_CONVERT)); | |
1578 | ASSERT(start_d <= INT_GET(hdr_d->count, ARCH_CONVERT)); | |
1579 | ASSERT(count <= INT_GET(hdr_s->count, ARCH_CONVERT)); | |
1580 | ||
1581 | /* | |
1582 | * Move the entries in the destination leaf up to make a hole? | |
1583 | */ | |
1584 | if (start_d < INT_GET(hdr_d->count, ARCH_CONVERT)) { | |
1585 | tmp = INT_GET(hdr_d->count, ARCH_CONVERT) - start_d; | |
1586 | tmp *= (uint)sizeof(xfs_dir_leaf_entry_t); | |
1587 | entry_s = &leaf_d->entries[start_d]; | |
1588 | entry_d = &leaf_d->entries[start_d + count]; | |
1589 | bcopy(entry_s, entry_d, tmp); | |
1590 | } | |
1591 | ||
1592 | /* | |
1593 | * Copy all entry's in the same (sorted) order, | |
1594 | * but allocate filenames packed and in sequence. | |
1595 | */ | |
1596 | entry_s = &leaf_s->entries[start_s]; | |
1597 | entry_d = &leaf_d->entries[start_d]; | |
1598 | for (i = 0; i < count; entry_s++, entry_d++, i++) { | |
1599 | ASSERT(INT_GET(entry_s->nameidx, ARCH_CONVERT) >= INT_GET(hdr_s->firstused, ARCH_CONVERT)); | |
1600 | ASSERT(entry_s->namelen < MAXNAMELEN); | |
1601 | tmp = XFS_DIR_LEAF_ENTSIZE_BYENTRY(entry_s); | |
1602 | INT_MOD(hdr_d->firstused, ARCH_CONVERT, -(tmp)); | |
1603 | entry_d->hashval = entry_s->hashval; /* INT_: direct copy */ | |
1604 | INT_COPY(entry_d->nameidx, hdr_d->firstused, ARCH_CONVERT); | |
1605 | entry_d->namelen = entry_s->namelen; | |
1606 | ASSERT(INT_GET(entry_d->nameidx, ARCH_CONVERT) + tmp <= XFS_LBSIZE(mp)); | |
1607 | bcopy(XFS_DIR_LEAF_NAMESTRUCT(leaf_s, INT_GET(entry_s->nameidx, ARCH_CONVERT)), | |
1608 | XFS_DIR_LEAF_NAMESTRUCT(leaf_d, INT_GET(entry_d->nameidx, ARCH_CONVERT)), tmp); | |
1609 | ASSERT(INT_GET(entry_s->nameidx, ARCH_CONVERT) + tmp <= XFS_LBSIZE(mp)); | |
1610 | bzero((char *)XFS_DIR_LEAF_NAMESTRUCT(leaf_s, INT_GET(entry_s->nameidx, ARCH_CONVERT)), | |
1611 | tmp); | |
1612 | INT_MOD(hdr_s->namebytes, ARCH_CONVERT, -(entry_d->namelen)); | |
1613 | INT_MOD(hdr_d->namebytes, ARCH_CONVERT, entry_d->namelen); | |
1614 | INT_MOD(hdr_s->count, ARCH_CONVERT, -1); | |
1615 | INT_MOD(hdr_d->count, ARCH_CONVERT, +1); | |
1616 | tmp = INT_GET(hdr_d->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t) | |
1617 | + (uint)sizeof(xfs_dir_leaf_hdr_t); | |
1618 | ASSERT(INT_GET(hdr_d->firstused, ARCH_CONVERT) >= tmp); | |
1619 | ||
1620 | } | |
1621 | ||
1622 | /* | |
1623 | * Zero out the entries we just copied. | |
1624 | */ | |
1625 | if (start_s == INT_GET(hdr_s->count, ARCH_CONVERT)) { | |
1626 | tmp = count * (uint)sizeof(xfs_dir_leaf_entry_t); | |
1627 | entry_s = &leaf_s->entries[start_s]; | |
1628 | ASSERT((char *)entry_s + tmp <= (char *)leaf_s + XFS_LBSIZE(mp)); | |
1629 | bzero((char *)entry_s, tmp); | |
1630 | } else { | |
1631 | /* | |
1632 | * Move the remaining entries down to fill the hole, | |
1633 | * then zero the entries at the top. | |
1634 | */ | |
1635 | tmp = INT_GET(hdr_s->count, ARCH_CONVERT) - count; | |
1636 | tmp *= (uint)sizeof(xfs_dir_leaf_entry_t); | |
1637 | entry_s = &leaf_s->entries[start_s + count]; | |
1638 | entry_d = &leaf_s->entries[start_s]; | |
1639 | bcopy(entry_s, entry_d, tmp); | |
1640 | ||
1641 | tmp = count * (uint)sizeof(xfs_dir_leaf_entry_t); | |
1642 | entry_s = &leaf_s->entries[INT_GET(hdr_s->count, ARCH_CONVERT)]; | |
1643 | ASSERT((char *)entry_s + tmp <= (char *)leaf_s + XFS_LBSIZE(mp)); | |
1644 | bzero((char *)entry_s, tmp); | |
1645 | } | |
1646 | ||
1647 | /* | |
1648 | * Fill in the freemap information | |
1649 | */ | |
1650 | INT_SET(hdr_d->freemap[0].base, ARCH_CONVERT, (uint)sizeof(xfs_dir_leaf_hdr_t)); | |
1651 | INT_MOD(hdr_d->freemap[0].base, ARCH_CONVERT, INT_GET(hdr_d->count, ARCH_CONVERT) * (uint)sizeof(xfs_dir_leaf_entry_t)); | |
1652 | INT_SET(hdr_d->freemap[0].size, ARCH_CONVERT, INT_GET(hdr_d->firstused, ARCH_CONVERT) - INT_GET(hdr_d->freemap[0].base, ARCH_CONVERT)); | |
1653 | INT_SET(hdr_d->freemap[1].base, ARCH_CONVERT, INT_ZERO(hdr_d->freemap[2].base, ARCH_CONVERT)); | |
1654 | INT_SET(hdr_d->freemap[1].size, ARCH_CONVERT, INT_ZERO(hdr_d->freemap[2].size, ARCH_CONVERT)); | |
1655 | hdr_s->holes = 1; /* leaf may not be compact */ | |
1656 | } | |
1657 | ||
1658 | /* | |
1659 | * Compare two leaf blocks "order". | |
1660 | */ | |
1661 | int | |
1662 | xfs_dir_leaf_order(xfs_dabuf_t *leaf1_bp, xfs_dabuf_t *leaf2_bp) | |
1663 | { | |
1664 | xfs_dir_leafblock_t *leaf1, *leaf2; | |
1665 | ||
1666 | leaf1 = leaf1_bp->data; | |
1667 | leaf2 = leaf2_bp->data; | |
1668 | ASSERT((INT_GET(leaf1->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC) && | |
1669 | (INT_GET(leaf2->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC)); | |
1670 | if ((INT_GET(leaf1->hdr.count, ARCH_CONVERT) > 0) && (INT_GET(leaf2->hdr.count, ARCH_CONVERT) > 0) && | |
1671 | ((INT_GET(leaf2->entries[ 0 ].hashval, ARCH_CONVERT) < | |
1672 | INT_GET(leaf1->entries[ 0 ].hashval, ARCH_CONVERT)) || | |
1673 | (INT_GET(leaf2->entries[ INT_GET(leaf2->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT) < | |
1674 | INT_GET(leaf1->entries[ INT_GET(leaf1->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT)))) { | |
1675 | return(1); | |
1676 | } | |
1677 | return(0); | |
1678 | } | |
1679 | ||
1680 | /* | |
1681 | * Pick up the last hashvalue from a leaf block. | |
1682 | */ | |
1683 | xfs_dahash_t | |
1684 | xfs_dir_leaf_lasthash(xfs_dabuf_t *bp, int *count) | |
1685 | { | |
1686 | xfs_dir_leafblock_t *leaf; | |
1687 | ||
1688 | leaf = bp->data; | |
1689 | ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT) == XFS_DIR_LEAF_MAGIC); | |
1690 | if (count) | |
1691 | *count = INT_GET(leaf->hdr.count, ARCH_CONVERT); | |
1692 | if (INT_GET(leaf->hdr.count, ARCH_CONVERT) == 0) | |
1693 | return(0); | |
1694 | return(INT_GET(leaf->entries[ INT_GET(leaf->hdr.count, ARCH_CONVERT)-1 ].hashval, ARCH_CONVERT)); | |
1695 | } |