1 /* fsys_xfs.c - an implementation for the SGI XFS file system */ 2 /* 3 * GRUB -- GRand Unified Bootloader 4 * Copyright (C) 2001,2002,2004 Free Software Foundation, Inc. 5 * 6 * This program is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 19 */ 20 21 #ifdef FSYS_XFS 22 23 #include "shared.h" 24 #include "filesys.h" 25 #include "xfs.h" 26 27 #define MAX_LINK_COUNT 8 28 29 typedef struct xad { 30 xfs_fileoff_t offset; 31 xfs_fsblock_t start; 32 xfs_filblks_t len; 33 } xad_t; 34 35 struct xfs_info { 36 int bsize; 37 int dirbsize; 38 int isize; 39 unsigned int agblocks; 40 int bdlog; 41 int blklog; 42 int inopblog; 43 int agblklog; 44 int agnolog; 45 unsigned int nextents; 46 xfs_daddr_t next; 47 xfs_daddr_t daddr; 48 xfs_dablk_t forw; 49 xfs_dablk_t dablk; 50 xfs_bmbt_rec_32_t *xt; 51 xfs_bmbt_ptr_t ptr0; 52 int btnode_ptr0_off; 53 int i8param; 54 int dirpos; 55 int dirmax; 56 int blkoff; 57 int fpos; 58 xfs_ino_t rootino; 59 }; 60 61 static struct xfs_info xfs; 62 63 #define dirbuf ((char *)FSYS_BUF) 64 #define filebuf ((char *)FSYS_BUF + 4096) 65 #define inode ((xfs_dinode_t *)((char *)FSYS_BUF + 8192)) 66 #define icore (inode->di_core) 67 68 #define mask32lo(n) (((xfs_uint32_t)1 << (n)) - 1) 69 70 #define XFS_INO_MASK(k) ((xfs_uint32_t)((1ULL << (k)) - 1)) 71 #define XFS_INO_OFFSET_BITS xfs.inopblog 72 #define XFS_INO_AGBNO_BITS xfs.agblklog 73 #define XFS_INO_AGINO_BITS (xfs.agblklog + xfs.inopblog) 74 #define XFS_INO_AGNO_BITS xfs.agnolog 75 76 static inline xfs_agblock_t 77 agino2agbno (xfs_agino_t agino) 78 { 79 return agino >> XFS_INO_OFFSET_BITS; 80 } 81 82 static inline xfs_agnumber_t 83 ino2agno (xfs_ino_t ino) 84 { 85 return ino >> XFS_INO_AGINO_BITS; 86 } 87 88 static inline xfs_agino_t 89 ino2agino (xfs_ino_t ino) 90 { 91 return ino & XFS_INO_MASK(XFS_INO_AGINO_BITS); 92 } 93 94 static inline int 95 ino2offset (xfs_ino_t ino) 96 { 97 return ino & XFS_INO_MASK(XFS_INO_OFFSET_BITS); 98 } 99 100 static inline __const__ xfs_uint16_t 101 le16 (xfs_uint16_t x) 102 { 103 __asm__("xchgb %b0,%h0" \ 104 : "=q" (x) \ 105 : "0" (x)); \ 106 return x; 107 } 108 109 static inline __const__ xfs_uint32_t 110 le32 (xfs_uint32_t x) 111 { 112 #if 0 113 /* 386 doesn't have bswap. */ 114 __asm__("bswap %0" : "=r" (x) : "0" (x)); 115 #else 116 /* This is slower but this works on all x86 architectures. */ 117 __asm__("xchgb %b0, %h0" \ 118 "\n\troll $16, %0" \ 119 "\n\txchgb %b0, %h0" \ 120 : "=q" (x) : "0" (x)); 121 #endif 122 return x; 123 } 124 125 static inline __const__ xfs_uint64_t 126 le64 (xfs_uint64_t x) 127 { 128 xfs_uint32_t h = x >> 32; 129 xfs_uint32_t l = x & ((1ULL<<32)-1); 130 return (((xfs_uint64_t)le32(l)) << 32) | ((xfs_uint64_t)(le32(h))); 131 } 132 133 134 static xfs_fsblock_t 135 xt_start (xfs_bmbt_rec_32_t *r) 136 { 137 return (((xfs_fsblock_t)(le32 (r->l1) & mask32lo(9))) << 43) | 138 (((xfs_fsblock_t)le32 (r->l2)) << 11) | 139 (((xfs_fsblock_t)le32 (r->l3)) >> 21); 140 } 141 142 static xfs_fileoff_t 143 xt_offset (xfs_bmbt_rec_32_t *r) 144 { 145 return (((xfs_fileoff_t)le32 (r->l0) & 146 mask32lo(31)) << 23) | 147 (((xfs_fileoff_t)le32 (r->l1)) >> 9); 148 } 149 150 static xfs_filblks_t 151 xt_len (xfs_bmbt_rec_32_t *r) 152 { 153 return le32(r->l3) & mask32lo(21); 154 } 155 156 static inline int 157 xfs_highbit32(xfs_uint32_t v) 158 { 159 int i; 160 161 if (--v) { 162 for (i = 0; i < 31; i++, v >>= 1) { 163 if (v == 0) 164 return i; 165 } 166 } 167 return 0; 168 } 169 170 static int 171 isinxt (xfs_fileoff_t key, xfs_fileoff_t offset, xfs_filblks_t len) 172 { 173 return (key >= offset) ? (key < offset + len ? 1 : 0) : 0; 174 } 175 176 static xfs_daddr_t 177 agb2daddr (xfs_agnumber_t agno, xfs_agblock_t agbno) 178 { 179 return ((xfs_fsblock_t)agno*xfs.agblocks + agbno) << xfs.bdlog; 180 } 181 182 static xfs_daddr_t 183 fsb2daddr (xfs_fsblock_t fsbno) 184 { 185 return agb2daddr ((xfs_agnumber_t)(fsbno >> xfs.agblklog), 186 (xfs_agblock_t)(fsbno & mask32lo(xfs.agblklog))); 187 } 188 189 #undef offsetof 190 #define offsetof(t,m) ((int)&(((t *)0)->m)) 191 192 static inline int 193 btroot_maxrecs (void) 194 { 195 int tmp = icore.di_forkoff ? (icore.di_forkoff << 3) : xfs.isize; 196 197 return (tmp - sizeof(xfs_bmdr_block_t) - offsetof(xfs_dinode_t, di_u)) / 198 (sizeof (xfs_bmbt_key_t) + sizeof (xfs_bmbt_ptr_t)); 199 } 200 201 static int 202 di_read (xfs_ino_t ino) 203 { 204 xfs_agino_t agino; 205 xfs_agnumber_t agno; 206 xfs_agblock_t agbno; 207 xfs_daddr_t daddr; 208 int offset; 209 210 agno = ino2agno (ino); 211 agino = ino2agino (ino); 212 agbno = agino2agbno (agino); 213 offset = ino2offset (ino); 214 daddr = agb2daddr (agno, agbno); 215 216 devread (daddr, offset*xfs.isize, xfs.isize, (char *)inode); 217 218 xfs.ptr0 = *(xfs_bmbt_ptr_t *) 219 (inode->di_u.di_c + sizeof(xfs_bmdr_block_t) 220 + btroot_maxrecs ()*sizeof(xfs_bmbt_key_t)); 221 222 return 1; 223 } 224 225 static void 226 init_extents (void) 227 { 228 xfs_bmbt_ptr_t ptr0; 229 xfs_btree_lblock_t h; 230 231 switch (icore.di_format) { 232 case XFS_DINODE_FMT_EXTENTS: 233 xfs.xt = inode->di_u.di_bmx; 234 xfs.nextents = le32 (icore.di_nextents); 235 break; 236 case XFS_DINODE_FMT_BTREE: 237 ptr0 = xfs.ptr0; 238 for (;;) { 239 xfs.daddr = fsb2daddr (le64(ptr0)); 240 devread (xfs.daddr, 0, 241 sizeof(xfs_btree_lblock_t), (char *)&h); 242 if (!h.bb_level) { 243 xfs.nextents = le16(h.bb_numrecs); 244 xfs.next = fsb2daddr (le64(h.bb_rightsib)); 245 xfs.fpos = sizeof(xfs_btree_block_t); 246 return; 247 } 248 devread (xfs.daddr, xfs.btnode_ptr0_off, 249 sizeof(xfs_bmbt_ptr_t), (char *)&ptr0); 250 } 251 } 252 } 253 254 static xad_t * 255 next_extent (void) 256 { 257 static xad_t xad; 258 259 switch (icore.di_format) { 260 case XFS_DINODE_FMT_EXTENTS: 261 if (xfs.nextents == 0) 262 return NULL; 263 break; 264 case XFS_DINODE_FMT_BTREE: 265 if (xfs.nextents == 0) { 266 xfs_btree_lblock_t h; 267 if (xfs.next == 0) 268 return NULL; 269 xfs.daddr = xfs.next; 270 devread (xfs.daddr, 0, sizeof(xfs_btree_lblock_t), (char *)&h); 271 xfs.nextents = le16(h.bb_numrecs); 272 xfs.next = fsb2daddr (le64(h.bb_rightsib)); 273 xfs.fpos = sizeof(xfs_btree_block_t); 274 } 275 /* Yeah, I know that's slow, but I really don't care */ 276 devread (xfs.daddr, xfs.fpos, sizeof(xfs_bmbt_rec_t), filebuf); 277 xfs.xt = (xfs_bmbt_rec_32_t *)filebuf; 278 xfs.fpos += sizeof(xfs_bmbt_rec_32_t); 279 } 280 xad.offset = xt_offset (xfs.xt); 281 xad.start = xt_start (xfs.xt); 282 xad.len = xt_len (xfs.xt); 283 ++xfs.xt; 284 --xfs.nextents; 285 286 return &xad; 287 } 288 289 /* 290 * Name lies - the function reads only first 100 bytes 291 */ 292 static void 293 xfs_dabread (void) 294 { 295 xad_t *xad; 296 xfs_fileoff_t offset;; 297 298 init_extents (); 299 while ((xad = next_extent ())) { 300 offset = xad->offset; 301 if (isinxt (xfs.dablk, offset, xad->len)) { 302 devread (fsb2daddr (xad->start + xfs.dablk - offset), 303 0, 100, dirbuf); 304 break; 305 } 306 } 307 } 308 309 static inline xfs_ino_t 310 sf_ino (char *sfe, int namelen) 311 { 312 void *p = sfe + namelen + 3; 313 314 return (xfs.i8param == 0) 315 ? le64(*(xfs_ino_t *)p) : le32(*(xfs_uint32_t *)p); 316 } 317 318 static inline xfs_ino_t 319 sf_parent_ino (void) 320 { 321 return (xfs.i8param == 0) 322 ? le64(*(xfs_ino_t *)(&inode->di_u.di_dir2sf.hdr.parent)) 323 : le32(*(xfs_uint32_t *)(&inode->di_u.di_dir2sf.hdr.parent)); 324 } 325 326 static inline int 327 roundup8 (int n) 328 { 329 return ((n+7)&~7); 330 } 331 332 static char * 333 next_dentry (xfs_ino_t *ino) 334 { 335 int namelen = 1; 336 int toread; 337 static char usual[2][3] = {".", ".."}; 338 static xfs_dir2_sf_entry_t *sfe; 339 char *name = usual[0]; 340 341 if (xfs.dirpos >= xfs.dirmax) { 342 if (xfs.forw == 0) 343 return NULL; 344 xfs.dablk = xfs.forw; 345 xfs_dabread (); 346 #define h ((xfs_dir2_leaf_hdr_t *)dirbuf) 347 xfs.dirmax = le16 (h->count) - le16 (h->stale); 348 xfs.forw = le32 (h->info.forw); 349 #undef h 350 xfs.dirpos = 0; 351 } 352 353 switch (icore.di_format) { 354 case XFS_DINODE_FMT_LOCAL: 355 switch (xfs.dirpos) { 356 case -2: 357 *ino = 0; 358 break; 359 case -1: 360 *ino = sf_parent_ino (); 361 ++name; 362 ++namelen; 363 sfe = (xfs_dir2_sf_entry_t *) 364 (inode->di_u.di_c 365 + sizeof(xfs_dir2_sf_hdr_t) 366 - xfs.i8param); 367 break; 368 default: 369 namelen = sfe->namelen; 370 *ino = sf_ino ((char *)sfe, namelen); 371 name = sfe->name; 372 sfe = (xfs_dir2_sf_entry_t *) 373 ((char *)sfe + namelen + 11 - xfs.i8param); 374 } 375 break; 376 case XFS_DINODE_FMT_BTREE: 377 case XFS_DINODE_FMT_EXTENTS: 378 #define dau ((xfs_dir2_data_union_t *)dirbuf) 379 for (;;) { 380 if (xfs.blkoff >= xfs.dirbsize) { 381 xfs.blkoff = sizeof(xfs_dir2_data_hdr_t); 382 filepos &= ~(xfs.dirbsize - 1); 383 filepos |= xfs.blkoff; 384 } 385 xfs_read (dirbuf, 4); 386 xfs.blkoff += 4; 387 if (dau->unused.freetag == XFS_DIR2_DATA_FREE_TAG) { 388 toread = roundup8 (le16(dau->unused.length)) - 4; 389 xfs.blkoff += toread; 390 filepos += toread; 391 continue; 392 } 393 break; 394 } 395 xfs_read ((char *)dirbuf + 4, 5); 396 *ino = le64 (dau->entry.inumber); 397 namelen = dau->entry.namelen; 398 #undef dau 399 toread = roundup8 (namelen + 11) - 9; 400 xfs_read (dirbuf, toread); 401 name = (char *)dirbuf; 402 xfs.blkoff += toread + 5; 403 } 404 ++xfs.dirpos; 405 name[namelen] = 0; 406 407 return name; 408 } 409 410 static char * 411 first_dentry (xfs_ino_t *ino) 412 { 413 xfs.forw = 0; 414 switch (icore.di_format) { 415 case XFS_DINODE_FMT_LOCAL: 416 xfs.dirmax = inode->di_u.di_dir2sf.hdr.count; 417 xfs.i8param = inode->di_u.di_dir2sf.hdr.i8count ? 0 : 4; 418 xfs.dirpos = -2; 419 break; 420 case XFS_DINODE_FMT_EXTENTS: 421 case XFS_DINODE_FMT_BTREE: 422 filepos = 0; 423 xfs_read (dirbuf, sizeof(xfs_dir2_data_hdr_t)); 424 if (((xfs_dir2_data_hdr_t *)dirbuf)->magic == le32(XFS_DIR2_BLOCK_MAGIC)) { 425 #define tail ((xfs_dir2_block_tail_t *)dirbuf) 426 filepos = xfs.dirbsize - sizeof(*tail); 427 xfs_read (dirbuf, sizeof(*tail)); 428 xfs.dirmax = le32 (tail->count) - le32 (tail->stale); 429 #undef tail 430 } else { 431 xfs.dablk = (1ULL << 35) >> xfs.blklog; 432 #define h ((xfs_dir2_leaf_hdr_t *)dirbuf) 433 #define n ((xfs_da_intnode_t *)dirbuf) 434 for (;;) { 435 xfs_dabread (); 436 if ((n->hdr.info.magic == le16(XFS_DIR2_LEAFN_MAGIC)) 437 || (n->hdr.info.magic == le16(XFS_DIR2_LEAF1_MAGIC))) { 438 xfs.dirmax = le16 (h->count) - le16 (h->stale); 439 xfs.forw = le32 (h->info.forw); 440 break; 441 } 442 xfs.dablk = le32 (n->btree[0].before); 443 } 444 #undef n 445 #undef h 446 } 447 xfs.blkoff = sizeof(xfs_dir2_data_hdr_t); 448 filepos = xfs.blkoff; 449 xfs.dirpos = 0; 450 } 451 return next_dentry (ino); 452 } 453 454 int 455 xfs_mount (void) 456 { 457 xfs_sb_t super; 458 459 if (!devread (0, 0, sizeof(super), (char *)&super) 460 || (le32(super.sb_magicnum) != XFS_SB_MAGIC) 461 || ((le16(super.sb_versionnum) 462 & XFS_SB_VERSION_NUMBITS) != XFS_SB_VERSION_4) ) { 463 return 0; 464 } 465 466 xfs.bsize = le32 (super.sb_blocksize); 467 xfs.blklog = super.sb_blocklog; 468 xfs.bdlog = xfs.blklog - SECTOR_BITS; 469 xfs.rootino = le64 (super.sb_rootino); 470 xfs.isize = le16 (super.sb_inodesize); 471 xfs.agblocks = le32 (super.sb_agblocks); 472 xfs.dirbsize = xfs.bsize << super.sb_dirblklog; 473 474 xfs.inopblog = super.sb_inopblog; 475 xfs.agblklog = super.sb_agblklog; 476 xfs.agnolog = xfs_highbit32 (le32(super.sb_agcount)); 477 478 xfs.btnode_ptr0_off = 479 ((xfs.bsize - sizeof(xfs_btree_block_t)) / 480 (sizeof (xfs_bmbt_key_t) + sizeof (xfs_bmbt_ptr_t))) 481 * sizeof(xfs_bmbt_key_t) + sizeof(xfs_btree_block_t); 482 483 return 1; 484 } 485 486 int 487 xfs_read (char *buf, int len) 488 { 489 xad_t *xad; 490 xfs_fileoff_t endofprev, endofcur, offset; 491 xfs_filblks_t xadlen; 492 int toread, startpos, endpos; 493 494 if (icore.di_format == XFS_DINODE_FMT_LOCAL) { 495 grub_memmove (buf, inode->di_u.di_c + filepos, len); 496 filepos += len; 497 return len; 498 } 499 500 startpos = filepos; 501 endpos = filepos + len; 502 endofprev = (xfs_fileoff_t)-1; 503 init_extents (); 504 while (len > 0 && (xad = next_extent ())) { 505 offset = xad->offset; 506 xadlen = xad->len; 507 if (isinxt (filepos >> xfs.blklog, offset, xadlen)) { 508 endofcur = (offset + xadlen) << xfs.blklog; 509 toread = (endofcur >= endpos) 510 ? len : (endofcur - filepos); 511 512 disk_read_func = disk_read_hook; 513 devread (fsb2daddr (xad->start), 514 filepos - (offset << xfs.blklog), toread, buf); 515 disk_read_func = NULL; 516 517 buf += toread; 518 len -= toread; 519 filepos += toread; 520 } else if (offset > endofprev) { 521 toread = ((offset << xfs.blklog) >= endpos) 522 ? len : ((offset - endofprev) << xfs.blklog); 523 len -= toread; 524 filepos += toread; 525 for (; toread; toread--) { 526 *buf++ = 0; 527 } 528 continue; 529 } 530 endofprev = offset + xadlen; 531 } 532 533 return filepos - startpos; 534 } 535 536 int 537 xfs_dir (char *dirname) 538 { 539 xfs_ino_t ino, parent_ino, new_ino; 540 xfs_fsize_t di_size; 541 int di_mode; 542 int cmp, n, link_count; 543 char linkbuf[xfs.bsize]; 544 char *rest, *name, ch; 545 546 parent_ino = ino = xfs.rootino; 547 link_count = 0; 548 for (;;) { 549 di_read (ino); 550 di_size = le64 (icore.di_size); 551 di_mode = le16 (icore.di_mode); 552 553 if ((di_mode & IFMT) == IFLNK) { 554 if (++link_count > MAX_LINK_COUNT) { 555 errnum = ERR_SYMLINK_LOOP; 556 return 0; 557 } 558 if (di_size < xfs.bsize - 1) { 559 filepos = 0; 560 filemax = di_size; 561 n = xfs_read (linkbuf, filemax); 562 } else { 563 errnum = ERR_FILELENGTH; 564 return 0; 565 } 566 567 ino = (linkbuf[0] == '/') ? xfs.rootino : parent_ino; 568 while (n < (xfs.bsize - 1) && (linkbuf[n++] = *dirname++)); 569 linkbuf[n] = 0; 570 dirname = linkbuf; 571 continue; 572 } 573 574 if (!*dirname || isspace (*dirname)) { 575 if ((di_mode & IFMT) != IFREG) { 576 errnum = ERR_BAD_FILETYPE; 577 return 0; 578 } 579 filepos = 0; 580 filemax = di_size; 581 return 1; 582 } 583 584 if ((di_mode & IFMT) != IFDIR) { 585 errnum = ERR_BAD_FILETYPE; 586 return 0; 587 } 588 589 for (; *dirname == '/'; dirname++); 590 591 for (rest = dirname; (ch = *rest) && !isspace (ch) && ch != '/'; rest++); 592 *rest = 0; 593 594 name = first_dentry (&new_ino); 595 for (;;) { 596 cmp = (!*dirname) ? -1 : substring (dirname, name); 597 #ifndef STAGE1_5 598 if (print_possibilities && ch != '/' && cmp <= 0) { 599 if (print_possibilities > 0) 600 print_possibilities = -print_possibilities; 601 print_a_completion (name); 602 } else 603 #endif 604 if (cmp == 0) { 605 parent_ino = ino; 606 if (new_ino) 607 ino = new_ino; 608 *(dirname = rest) = ch; 609 break; 610 } 611 name = next_dentry (&new_ino); 612 if (name == NULL) { 613 if (print_possibilities < 0) 614 return 1; 615 616 errnum = ERR_FILE_NOT_FOUND; 617 *rest = ch; 618 return 0; 619 } 620 } 621 } 622 } 623 624 #endif /* FSYS_XFS */ 625
