1 /*
2 * Copyright (c) 2012-2013 Paulo Alcantara <pcacjr@zytor.com>
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms 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,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write the Free Software Foundation,
15 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
16 */
17
18 #include <cache.h>
19 #include <core.h>
20 #include <fs.h>
21
22 #include "xfs_types.h"
23 #include "xfs_sb.h"
24 #include "xfs_ag.h"
25 #include "misc.h"
26 #include "xfs.h"
27 #include "xfs_dinode.h"
28
29 #include "xfs_dir2.h"
30
31 #define XFS_DIR2_DIRBLKS_CACHE_SIZE 128
32
33 struct xfs_dir2_dirblks_cache {
34 block_t dc_startblock;
35 xfs_filblks_t dc_blkscount;
36 void *dc_area;
37 };
38
39 static struct xfs_dir2_dirblks_cache dirblks_cache[XFS_DIR2_DIRBLKS_CACHE_SIZE];
40 static unsigned char dirblks_cached_count = 0;
41
xfs_dir2_da_hashname(const uint8_t * name,int namelen)42 uint32_t xfs_dir2_da_hashname(const uint8_t *name, int namelen)
43 {
44 uint32_t hash;
45
46 /*
47 * Do four characters at a time as long as we can.
48 */
49 for (hash = 0; namelen >= 4; namelen -=4, name += 4)
50 hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
51 (name[3] << 0) ^ rol32(hash, 7 * 4);
52
53 /*
54 * Now do the rest of the characters.
55 */
56 switch (namelen) {
57 case 3:
58 return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
59 rol32(hash, 7 * 3);
60 case 2:
61 return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
62 case 1:
63 return (name[0] << 0) ^ rol32(hash, 7 * 1);
64 default: /* case 0: */
65 return hash;
66 }
67 }
68
get_dirblks(struct fs_info * fs,block_t startblock,xfs_filblks_t c)69 static void *get_dirblks(struct fs_info *fs, block_t startblock,
70 xfs_filblks_t c)
71 {
72 int count = c << XFS_INFO(fs)->dirblklog;
73 uint8_t *p;
74 uint8_t *buf;
75 off_t offset = 0;
76
77 buf = malloc(c * XFS_INFO(fs)->dirblksize);
78 if (!buf)
79 malloc_error("buffer memory");
80
81 memset(buf, 0, XFS_INFO(fs)->dirblksize);
82
83 while (count--) {
84 p = (uint8_t *)get_cache(fs->fs_dev, startblock++);
85 memcpy(buf + offset, p, BLOCK_SIZE(fs));
86 offset += BLOCK_SIZE(fs);
87 }
88
89 return buf;
90 }
91
xfs_dir2_dirblks_get_cached(struct fs_info * fs,block_t startblock,xfs_filblks_t c)92 const void *xfs_dir2_dirblks_get_cached(struct fs_info *fs, block_t startblock,
93 xfs_filblks_t c)
94 {
95 unsigned char i;
96 void *buf;
97
98 xfs_debug("fs %p startblock %llu (0x%llx) blkscount %lu", fs, startblock,
99 startblock, c);
100
101 if (!dirblks_cached_count) {
102 buf = get_dirblks(fs, startblock, c);
103
104 dirblks_cache[dirblks_cached_count].dc_startblock = startblock;
105 dirblks_cache[dirblks_cached_count].dc_blkscount = c;
106 dirblks_cache[dirblks_cached_count].dc_area = buf;
107
108 return dirblks_cache[dirblks_cached_count++].dc_area;
109 } else if (dirblks_cached_count == XFS_DIR2_DIRBLKS_CACHE_SIZE) {
110 for (i = 0; i < XFS_DIR2_DIRBLKS_CACHE_SIZE / 2; i++) {
111 unsigned char k = XFS_DIR2_DIRBLKS_CACHE_SIZE - (i + 1);
112
113 free(dirblks_cache[i].dc_area);
114 dirblks_cache[i] = dirblks_cache[k];
115 memset(&dirblks_cache[k], 0, sizeof(dirblks_cache[k]));
116 }
117
118 buf = get_dirblks(fs, startblock, c);
119
120 dirblks_cache[XFS_DIR2_DIRBLKS_CACHE_SIZE / 2].dc_startblock =
121 startblock;
122 dirblks_cache[XFS_DIR2_DIRBLKS_CACHE_SIZE / 2].dc_blkscount = c;
123 dirblks_cache[XFS_DIR2_DIRBLKS_CACHE_SIZE / 2].dc_area = buf;
124
125 dirblks_cached_count = XFS_DIR2_DIRBLKS_CACHE_SIZE / 2;
126
127 return dirblks_cache[dirblks_cached_count++].dc_area;
128 } else {
129 block_t block;
130 xfs_filblks_t count;
131
132 block = dirblks_cache[dirblks_cached_count - 1].dc_startblock;
133 count = dirblks_cache[dirblks_cached_count - 1].dc_blkscount;
134
135 if (block == startblock && count == c) {
136 return dirblks_cache[dirblks_cached_count - 1].dc_area;
137 } else {
138 for (i = 0; i < dirblks_cached_count; i++) {
139 block = dirblks_cache[i].dc_startblock;
140 count = dirblks_cache[i].dc_blkscount;
141
142 if (block == startblock && count == c)
143 return dirblks_cache[i].dc_area;
144 }
145
146 buf = get_dirblks(fs, startblock, c);
147
148 dirblks_cache[dirblks_cached_count].dc_startblock = startblock;
149 dirblks_cache[dirblks_cached_count].dc_blkscount = c;
150 dirblks_cache[dirblks_cached_count].dc_area = buf;
151
152 return dirblks_cache[dirblks_cached_count++].dc_area;
153 }
154 }
155
156 return NULL;
157 }
158
xfs_dir2_dirblks_flush_cache(void)159 void xfs_dir2_dirblks_flush_cache(void)
160 {
161 unsigned char i;
162
163 for (i = 0; i < dirblks_cached_count; i++) {
164 free(dirblks_cache[i].dc_area);
165 memset(&dirblks_cache[i], 0, sizeof(dirblks_cache[i]));
166 }
167
168 dirblks_cached_count = 0;
169 }
170
xfs_dir2_local_find_entry(const char * dname,struct inode * parent,xfs_dinode_t * core)171 struct inode *xfs_dir2_local_find_entry(const char *dname, struct inode *parent,
172 xfs_dinode_t *core)
173 {
174 xfs_dir2_sf_t *sf = (xfs_dir2_sf_t *)&core->di_literal_area[0];
175 xfs_dir2_sf_entry_t *sf_entry;
176 uint8_t count = sf->hdr.i8count ? sf->hdr.i8count : sf->hdr.count;
177 struct fs_info *fs = parent->fs;
178 struct inode *inode;
179 xfs_intino_t ino;
180 xfs_dinode_t *ncore = NULL;
181
182 xfs_debug("dname %s parent %p core %p", dname, parent, core);
183 xfs_debug("count %hhu i8count %hhu", sf->hdr.count, sf->hdr.i8count);
184
185 sf_entry = (xfs_dir2_sf_entry_t *)((uint8_t *)&sf->list[0] -
186 (!sf->hdr.i8count ? 4 : 0));
187 while (count--) {
188 uint8_t *start_name = &sf_entry->name[0];
189 uint8_t *end_name = start_name + sf_entry->namelen;
190
191 if (!xfs_dir2_entry_name_cmp(start_name, end_name, dname)) {
192 xfs_debug("Found entry %s", dname);
193 goto found;
194 }
195
196 sf_entry = (xfs_dir2_sf_entry_t *)((uint8_t *)sf_entry +
197 offsetof(struct xfs_dir2_sf_entry,
198 name[0]) +
199 sf_entry->namelen +
200 (sf->hdr.i8count ? 8 : 4));
201 }
202
203 return NULL;
204
205 found:
206 inode = xfs_new_inode(fs);
207
208 ino = xfs_dir2_sf_get_inumber(sf, (xfs_dir2_inou_t *)(
209 (uint8_t *)sf_entry +
210 offsetof(struct xfs_dir2_sf_entry,
211 name[0]) +
212 sf_entry->namelen));
213
214 xfs_debug("entry inode's number %lu", ino);
215
216 ncore = xfs_dinode_get_core(fs, ino);
217 if (!ncore) {
218 xfs_error("Failed to get dinode!");
219 goto out;
220 }
221
222 fill_xfs_inode_pvt(fs, inode, ino);
223
224 inode->ino = ino;
225 inode->size = be64_to_cpu(ncore->di_size);
226
227 if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFDIR) {
228 inode->mode = DT_DIR;
229 xfs_debug("Found a directory inode!");
230 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFREG) {
231 inode->mode = DT_REG;
232 xfs_debug("Found a file inode!");
233 xfs_debug("inode size %llu", inode->size);
234 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFLNK) {
235 inode->mode = DT_LNK;
236 xfs_debug("Found a symbolic link inode!");
237 }
238
239 return inode;
240
241 out:
242 free(inode);
243
244 return NULL;
245 }
246
xfs_dir2_block_find_entry(const char * dname,struct inode * parent,xfs_dinode_t * core)247 struct inode *xfs_dir2_block_find_entry(const char *dname, struct inode *parent,
248 xfs_dinode_t *core)
249 {
250 xfs_bmbt_irec_t r;
251 block_t dir_blk;
252 struct fs_info *fs = parent->fs;
253 const uint8_t *dirblk_buf;
254 uint8_t *p, *endp;
255 xfs_dir2_data_hdr_t *hdr;
256 struct inode *inode = NULL;
257 xfs_dir2_block_tail_t *btp;
258 xfs_dir2_data_unused_t *dup;
259 xfs_dir2_data_entry_t *dep;
260 xfs_intino_t ino;
261 xfs_dinode_t *ncore;
262
263 xfs_debug("dname %s parent %p core %p", dname, parent, core);
264
265 bmbt_irec_get(&r, (xfs_bmbt_rec_t *)&core->di_literal_area[0]);
266 dir_blk = fsblock_to_bytes(fs, r.br_startblock) >> BLOCK_SHIFT(fs);
267
268 dirblk_buf = xfs_dir2_dirblks_get_cached(fs, dir_blk, r.br_blockcount);
269 hdr = (xfs_dir2_data_hdr_t *)dirblk_buf;
270 if (be32_to_cpu(hdr->magic) != XFS_DIR2_BLOCK_MAGIC) {
271 xfs_error("Block directory header's magic number does not match!");
272 xfs_debug("hdr->magic: 0x%lx", be32_to_cpu(hdr->magic));
273 goto out;
274 }
275
276 p = (uint8_t *)(hdr + 1);
277
278 btp = xfs_dir2_block_tail_p(XFS_INFO(fs), hdr);
279 endp = (uint8_t *)((xfs_dir2_leaf_entry_t *)btp - be32_to_cpu(btp->count));
280
281 while (p < endp) {
282 uint8_t *start_name;
283 uint8_t *end_name;
284
285 dup = (xfs_dir2_data_unused_t *)p;
286 if (be16_to_cpu(dup->freetag) == XFS_DIR2_DATA_FREE_TAG) {
287 p += be16_to_cpu(dup->length);
288 continue;
289 }
290
291 dep = (xfs_dir2_data_entry_t *)p;
292
293 start_name = &dep->name[0];
294 end_name = start_name + dep->namelen;
295
296 if (!xfs_dir2_entry_name_cmp(start_name, end_name, dname)) {
297 xfs_debug("Found entry %s", dname);
298 goto found;
299 }
300
301 p += xfs_dir2_data_entsize(dep->namelen);
302 }
303
304 out:
305 return NULL;
306
307 found:
308 inode = xfs_new_inode(fs);
309
310 ino = be64_to_cpu(dep->inumber);
311
312 xfs_debug("entry inode's number %lu", ino);
313
314 ncore = xfs_dinode_get_core(fs, ino);
315 if (!ncore) {
316 xfs_error("Failed to get dinode!");
317 goto failed;
318 }
319
320 fill_xfs_inode_pvt(fs, inode, ino);
321
322 inode->ino = ino;
323 XFS_PVT(inode)->i_ino_blk = ino_to_bytes(fs, ino) >> BLOCK_SHIFT(fs);
324 inode->size = be64_to_cpu(ncore->di_size);
325
326 if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFDIR) {
327 inode->mode = DT_DIR;
328 xfs_debug("Found a directory inode!");
329 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFREG) {
330 inode->mode = DT_REG;
331 xfs_debug("Found a file inode!");
332 xfs_debug("inode size %llu", inode->size);
333 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFLNK) {
334 inode->mode = DT_LNK;
335 xfs_debug("Found a symbolic link inode!");
336 }
337
338 xfs_debug("entry inode's number %lu", ino);
339
340 return inode;
341
342 failed:
343 free(inode);
344
345 return NULL;
346 }
347
xfs_dir2_leaf_find_entry(const char * dname,struct inode * parent,xfs_dinode_t * core)348 struct inode *xfs_dir2_leaf_find_entry(const char *dname, struct inode *parent,
349 xfs_dinode_t *core)
350 {
351 xfs_dir2_leaf_t *leaf;
352 xfs_bmbt_irec_t irec;
353 block_t leaf_blk, dir_blk;
354 xfs_dir2_leaf_entry_t *lep;
355 int low;
356 int high;
357 int mid = 0;
358 uint32_t hash = 0;
359 uint32_t hashwant;
360 uint32_t newdb, curdb = -1;
361 xfs_dir2_data_entry_t *dep;
362 struct inode *ip;
363 xfs_dir2_data_hdr_t *data_hdr;
364 uint8_t *start_name;
365 uint8_t *end_name;
366 xfs_intino_t ino;
367 xfs_dinode_t *ncore;
368 const uint8_t *buf = NULL;
369
370 xfs_debug("dname %s parent %p core %p", dname, parent, core);
371
372 bmbt_irec_get(&irec, ((xfs_bmbt_rec_t *)&core->di_literal_area[0]) +
373 be32_to_cpu(core->di_nextents) - 1);
374 leaf_blk = fsblock_to_bytes(parent->fs, irec.br_startblock) >>
375 BLOCK_SHIFT(parent->fs);
376
377 leaf = (xfs_dir2_leaf_t *)xfs_dir2_dirblks_get_cached(parent->fs, leaf_blk,
378 irec.br_blockcount);
379 if (be16_to_cpu(leaf->hdr.info.magic) != XFS_DIR2_LEAF1_MAGIC) {
380 xfs_error("Single leaf block header's magic number does not match!");
381 goto out;
382 }
383
384 if (!leaf->hdr.count)
385 goto out;
386
387 hashwant = xfs_dir2_da_hashname((uint8_t *)dname, strlen(dname));
388
389 /* Binary search */
390 for (lep = leaf->ents, low = 0, high = be16_to_cpu(leaf->hdr.count) - 1;
391 low <= high; ) {
392 mid = (low + high) >> 1;
393 if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
394 break;
395 if (hash < hashwant)
396 low = mid + 1;
397 else
398 high = mid - 1;
399 }
400
401 /* If hash is not the one we want, then the directory does not contain the
402 * entry we're looking for and there is nothing to do anymore.
403 */
404 if (hash != hashwant)
405 goto out;
406
407 while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant)
408 mid--;
409
410 for (lep = &leaf->ents[mid];
411 mid < be16_to_cpu(leaf->hdr.count) &&
412 be32_to_cpu(lep->hashval) == hashwant;
413 lep++, mid++) {
414 /* Skip over stale leaf entries. */
415 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
416 continue;
417
418 newdb = xfs_dir2_dataptr_to_db(parent->fs, be32_to_cpu(lep->address));
419 if (newdb != curdb) {
420 bmbt_irec_get(&irec,
421 ((xfs_bmbt_rec_t *)&core->di_literal_area[0]) + newdb);
422 dir_blk = fsblock_to_bytes(parent->fs, irec.br_startblock) >>
423
424 BLOCK_SHIFT(parent->fs);
425 buf = xfs_dir2_dirblks_get_cached(parent->fs, dir_blk, irec.br_blockcount);
426 data_hdr = (xfs_dir2_data_hdr_t *)buf;
427 if (be32_to_cpu(data_hdr->magic) != XFS_DIR2_DATA_MAGIC) {
428 xfs_error("Leaf directory's data magic No. does not match!");
429 goto out;
430 }
431
432 curdb = newdb;
433 }
434
435 dep = (xfs_dir2_data_entry_t *)((char *)buf +
436 xfs_dir2_dataptr_to_off(parent->fs, be32_to_cpu(lep->address)));
437
438 start_name = &dep->name[0];
439 end_name = start_name + dep->namelen;
440
441 if (!xfs_dir2_entry_name_cmp(start_name, end_name, dname)) {
442 xfs_debug("Found entry %s", dname);
443 goto found;
444 }
445 }
446
447 out:
448 return NULL;
449
450 found:
451 ip = xfs_new_inode(parent->fs);
452
453 ino = be64_to_cpu(dep->inumber);
454
455 xfs_debug("entry inode's number %lu", ino);
456
457 ncore = xfs_dinode_get_core(parent->fs, ino);
458 if (!ncore) {
459 xfs_error("Failed to get dinode!");
460 goto failed;
461 }
462
463 fill_xfs_inode_pvt(parent->fs, ip, ino);
464
465 ip->ino = ino;
466 XFS_PVT(ip)->i_ino_blk = ino_to_bytes(parent->fs, ino) >>
467 BLOCK_SHIFT(parent->fs);
468 ip->size = be64_to_cpu(ncore->di_size);
469
470 if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFDIR) {
471 ip->mode = DT_DIR;
472 xfs_debug("Found a directory inode!");
473 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFREG) {
474 ip->mode = DT_REG;
475 xfs_debug("Found a file inode!");
476 xfs_debug("inode size %llu", ip->size);
477 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFLNK) {
478 ip->mode = DT_LNK;
479 xfs_debug("Found a symbolic link inode!");
480 }
481
482 xfs_debug("entry inode's number %lu", ino);
483
484 return ip;
485
486 failed:
487 free(ip);
488
489 return ip;
490 }
491
492 static xfs_fsblock_t
select_child(xfs_dfiloff_t off,xfs_bmbt_key_t * kp,xfs_bmbt_ptr_t * pp,int nrecs)493 select_child(xfs_dfiloff_t off,
494 xfs_bmbt_key_t *kp,
495 xfs_bmbt_ptr_t *pp,
496 int nrecs)
497 {
498 int i;
499
500 for (i = 0; i < nrecs; i++) {
501 if (be64_to_cpu(kp[i].br_startoff) == off)
502 return be64_to_cpu(pp[i]);
503 if (be64_to_cpu(kp[i].br_startoff) > off) {
504 if (i == 0)
505 return be64_to_cpu(pp[i]);
506 else
507 return be64_to_cpu(pp[i-1]);
508 }
509 }
510
511 return be64_to_cpu(pp[nrecs - 1]);
512 }
513
xfs_dir2_get_right_blk(struct fs_info * fs,xfs_dinode_t * core,block_t fsblkno,int * error)514 block_t xfs_dir2_get_right_blk(struct fs_info *fs, xfs_dinode_t *core,
515 block_t fsblkno, int *error)
516 {
517 uint32_t idx;
518 xfs_bmbt_irec_t irec;
519 block_t bno;
520 block_t nextbno;
521 xfs_bmdr_block_t *rblock;
522 int fsize;
523 int nextents;
524 xfs_bmbt_ptr_t *pp;
525 xfs_bmbt_key_t *kp;
526 xfs_btree_block_t *blk;
527 xfs_bmbt_rec_t *xp;
528
529 *error = 0;
530 if (core->di_format == XFS_DINODE_FMT_EXTENTS) {
531 xfs_debug("XFS_DINODE_FMT_EXTENTS");
532 for (idx = 0; idx < be32_to_cpu(core->di_nextents); idx++) {
533 bmbt_irec_get(&irec,
534 ((xfs_bmbt_rec_t *)&core->di_literal_area[0]) + idx);
535 if (fsblkno >= irec.br_startoff &&
536 fsblkno < irec.br_startoff + irec.br_blockcount)
537 break;
538 }
539 } else if (core->di_format == XFS_DINODE_FMT_BTREE) {
540 xfs_debug("XFS_DINODE_FMT_BTREE");
541 bno = NULLFSBLOCK;
542 rblock = (xfs_bmdr_block_t *)&core->di_literal_area[0];
543 fsize = XFS_DFORK_SIZE(core, fs, XFS_DATA_FORK);
544 pp = XFS_BMDR_PTR_ADDR(rblock, 1, xfs_bmdr_maxrecs(fsize, 0));
545 kp = XFS_BMDR_KEY_ADDR(rblock, 1);
546 bno = fsblock_to_bytes(fs,
547 select_child(fsblkno, kp, pp,
548 be16_to_cpu(rblock->bb_numrecs))) >> BLOCK_SHIFT(fs);
549
550 /* Find the leaf */
551 for (;;) {
552 blk = (xfs_btree_block_t *)get_cache(fs->fs_dev, bno);
553 if (be16_to_cpu(blk->bb_level) == 0)
554 break;
555 pp = XFS_BMBT_PTR_ADDR(fs, blk, 1,
556 xfs_bmdr_maxrecs(XFS_INFO(fs)->blocksize, 0));
557 kp = XFS_BMBT_KEY_ADDR(fs, blk, 1);
558 bno = fsblock_to_bytes(fs,
559 select_child(fsblkno, kp, pp,
560 be16_to_cpu(blk->bb_numrecs))) >> BLOCK_SHIFT(fs);
561 }
562
563 /* Find the records among leaves */
564 for (;;) {
565 nextbno = be64_to_cpu(blk->bb_u.l.bb_rightsib);
566 nextents = be16_to_cpu(blk->bb_numrecs);
567 xp = (xfs_bmbt_rec_t *)XFS_BMBT_REC_ADDR(fs, blk, 1);
568 for (idx = 0; idx < nextents; idx++) {
569 bmbt_irec_get(&irec, xp + idx);
570 if (fsblkno >= irec.br_startoff &&
571 fsblkno < irec.br_startoff + irec.br_blockcount) {
572 nextbno = NULLFSBLOCK;
573 break;
574 }
575 }
576 if (nextbno == NULLFSBLOCK)
577 break;
578 bno = fsblock_to_bytes(fs, nextbno) >> BLOCK_SHIFT(fs);
579 blk = (xfs_btree_block_t *)get_cache(fs->fs_dev, bno);
580 }
581 }
582
583 if (fsblkno < irec.br_startoff ||
584 fsblkno >= irec.br_startoff + irec.br_blockcount)
585 *error = 1;
586
587 return fsblock_to_bytes(fs,
588 fsblkno - irec.br_startoff + irec.br_startblock) >>
589 BLOCK_SHIFT(fs);
590 }
591
xfs_dir2_node_find_entry(const char * dname,struct inode * parent,xfs_dinode_t * core)592 struct inode *xfs_dir2_node_find_entry(const char *dname, struct inode *parent,
593 xfs_dinode_t *core)
594 {
595 block_t fsblkno;
596 xfs_da_intnode_t *node = NULL;
597 uint32_t hashwant;
598 uint32_t hash = 0;
599 xfs_da_node_entry_t *btree;
600 uint16_t max;
601 uint16_t span;
602 uint16_t probe;
603 int error;
604 xfs_dir2_data_hdr_t *data_hdr;
605 xfs_dir2_leaf_t *leaf;
606 xfs_dir2_leaf_entry_t *lep;
607 xfs_dir2_data_entry_t *dep;
608 struct inode *ip;
609 uint8_t *start_name;
610 uint8_t *end_name;
611 int low;
612 int high;
613 int mid = 0;
614 uint32_t newdb, curdb = -1;
615 xfs_intino_t ino;
616 xfs_dinode_t *ncore;
617 const uint8_t *buf = NULL;
618
619 xfs_debug("dname %s parent %p core %p", dname, parent, core);
620
621 hashwant = xfs_dir2_da_hashname((uint8_t *)dname, strlen(dname));
622
623 fsblkno = xfs_dir2_get_right_blk(parent->fs, core,
624 xfs_dir2_byte_to_db(parent->fs, XFS_DIR2_LEAF_OFFSET),
625 &error);
626 if (error) {
627 xfs_error("Cannot find right rec!");
628 return NULL;
629 }
630
631 node = (xfs_da_intnode_t *)xfs_dir2_dirblks_get_cached(parent->fs, fsblkno,
632 1);
633 if (be16_to_cpu(node->hdr.info.magic) != XFS_DA_NODE_MAGIC) {
634 xfs_error("Node's magic number does not match!");
635 goto out;
636 }
637
638 do {
639 if (!node->hdr.count)
640 goto out;
641
642 /* Given a hash to lookup, you read the node's btree array and first
643 * "hashval" in the array that exceeds the given hash and it can then
644 * be found in the block pointed by the "before" value.
645 */
646 max = be16_to_cpu(node->hdr.count);
647
648 probe = span = max/2;
649 for (btree = &node->btree[probe];
650 span > 4; btree = &node->btree[probe]) {
651 span /= 2;
652 hash = be32_to_cpu(btree->hashval);
653
654 if (hash < hashwant)
655 probe += span;
656 else if (hash > hashwant)
657 probe -= span;
658 else
659 break;
660 }
661
662 while ((probe > 0) && (be32_to_cpu(btree->hashval) >= hashwant)) {
663 btree--;
664 probe--;
665 }
666
667 while ((probe < max) && (be32_to_cpu(btree->hashval) < hashwant)) {
668 btree++;
669 probe++;
670 }
671
672 if (probe == max)
673 fsblkno = be32_to_cpu(node->btree[max-1].before);
674 else
675 fsblkno = be32_to_cpu(node->btree[probe].before);
676
677 fsblkno = xfs_dir2_get_right_blk(parent->fs, core, fsblkno, &error);
678 if (error) {
679 xfs_error("Cannot find right rec!");
680 goto out;
681 }
682
683 node = (xfs_da_intnode_t *)xfs_dir2_dirblks_get_cached(parent->fs,
684 fsblkno, 1);
685 } while(be16_to_cpu(node->hdr.info.magic) == XFS_DA_NODE_MAGIC);
686
687 leaf = (xfs_dir2_leaf_t*)node;
688 if (be16_to_cpu(leaf->hdr.info.magic) != XFS_DIR2_LEAFN_MAGIC) {
689 xfs_error("Leaf's magic number does not match!");
690 goto out;
691 }
692
693 if (!leaf->hdr.count)
694 goto out;
695
696 for (lep = leaf->ents, low = 0, high = be16_to_cpu(leaf->hdr.count) - 1;
697 low <= high; ) {
698 mid = (low + high) >> 1;
699
700 if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
701 break;
702 if (hash < hashwant)
703 low = mid + 1;
704 else
705 high = mid - 1;
706 }
707
708 /* If hash is not the one we want, then the directory does not contain the
709 * entry we're looking for and there is nothing to do anymore.
710 */
711 if (hash != hashwant)
712 goto out;
713
714 while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant)
715 mid--;
716
717 for (lep = &leaf->ents[mid];
718 mid < be16_to_cpu(leaf->hdr.count) &&
719 be32_to_cpu(lep->hashval) == hashwant;
720 lep++, mid++) {
721 /* Skip over stale leaf entries. */
722 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
723 continue;
724
725 newdb = xfs_dir2_dataptr_to_db(parent->fs, be32_to_cpu(lep->address));
726 if (newdb != curdb) {
727 fsblkno = xfs_dir2_get_right_blk(parent->fs, core, newdb, &error);
728 if (error) {
729 xfs_error("Cannot find data block!");
730 goto out;
731 }
732
733 buf = xfs_dir2_dirblks_get_cached(parent->fs, fsblkno, 1);
734 data_hdr = (xfs_dir2_data_hdr_t *)buf;
735 if (be32_to_cpu(data_hdr->magic) != XFS_DIR2_DATA_MAGIC) {
736 xfs_error("Leaf directory's data magic No. does not match!");
737 goto out;
738 }
739
740 curdb = newdb;
741 }
742
743 dep = (xfs_dir2_data_entry_t *)((char *)buf +
744 xfs_dir2_dataptr_to_off(parent->fs, be32_to_cpu(lep->address)));
745
746 start_name = &dep->name[0];
747 end_name = start_name + dep->namelen;
748
749 if (!xfs_dir2_entry_name_cmp(start_name, end_name, dname)) {
750 xfs_debug("Found entry %s", dname);
751 goto found;
752 }
753 }
754
755 out:
756 return NULL;
757
758 found:
759 ip = xfs_new_inode(parent->fs);
760 ino = be64_to_cpu(dep->inumber);
761 ncore = xfs_dinode_get_core(parent->fs, ino);
762 if (!ncore) {
763 xfs_error("Failed to get dinode!");
764 goto failed;
765 }
766
767 fill_xfs_inode_pvt(parent->fs, ip, ino);
768 ip->ino = ino;
769 XFS_PVT(ip)->i_ino_blk = ino_to_bytes(parent->fs, ino) >>
770 BLOCK_SHIFT(parent->fs);
771 ip->size = be64_to_cpu(ncore->di_size);
772
773 if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFDIR) {
774 ip->mode = DT_DIR;
775 xfs_debug("Found a directory inode!");
776 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFREG) {
777 ip->mode = DT_REG;
778 xfs_debug("Found a file inode!");
779 xfs_debug("inode size %llu", ip->size);
780 } else if ((be16_to_cpu(ncore->di_mode) & S_IFMT) == S_IFLNK) {
781 ip->mode = DT_LNK;
782 xfs_debug("Found a symbolic link inode!");
783 }
784
785 xfs_debug("entry inode's number %lu", ino);
786
787 return ip;
788
789 failed:
790 free(ip);
791
792 return NULL;
793 }
794