grub-core/fs/nilfs2.c

   1 /*
   2  *  nilfs2.c - New Implementation of Log filesystem
   3  *
   4  *  Written by Jiro SEKIBA <jir@unicus.jp>
   5  *
   6  *  Copyright (C) 2003,2004,2005,2007,2008,2010  Free Software Foundation, Inc.
   7  *
   8  *  GRUB is free software: you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation, either version 3 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  GRUB is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
  20  */
  21
  22
  23 /* Filetype information as used in inodes.  */
  24 #define FILETYPE_INO_MASK       0170000
  25 #define FILETYPE_INO_REG        0100000
  26 #define FILETYPE_INO_DIRECTORY  0040000
  27 #define FILETYPE_INO_SYMLINK    0120000
  28
  29 #include <grub/err.h>
  30 #include <grub/file.h>
  31 #include <grub/mm.h>
  32 #include <grub/misc.h>
  33 #include <grub/disk.h>
  34 #include <grub/dl.h>
  35 #include <grub/types.h>
  36 #include <grub/fshelp.h>
  37
  38 GRUB_MOD_LICENSE ("GPLv3+");
  39
  40 #define NILFS_INODE_BMAP_SIZE   7
  41
  42 #define NILFS_SUPORT_REV        2
  43
  44 /* Magic value used to identify an nilfs2 filesystem.  */
  45 #define NILFS2_SUPER_MAGIC      0x3434
  46 /* nilfs btree node flag.  */
  47 #define NILFS_BTREE_NODE_ROOT   0x01
  48
  49 /* nilfs btree node level. */
  50 #define NILFS_BTREE_LEVEL_DATA          0
  51 #define NILFS_BTREE_LEVEL_NODE_MIN      (NILFS_BTREE_LEVEL_DATA + 1)
  52
  53 /* nilfs 1st super block posission from beginning of the partition
  54    in 512 block size */
  55 #define NILFS_1ST_SUPER_BLOCK   2
  56 /* nilfs 2nd super block posission from beginning of the partition
  57    in 512 block size */
  58 #define NILFS_2ND_SUPER_BLOCK(devsize)  (((devsize >> 3) - 1) << 3)
  59
  60 #define LOG_INODE_SIZE 7
  61 struct grub_nilfs2_inode
  62 {
  63   grub_uint64_t i_blocks;
  64   grub_uint64_t i_size;
  65   grub_uint64_t i_ctime;
  66   grub_uint64_t i_mtime;
  67   grub_uint32_t i_ctime_nsec;
  68   grub_uint32_t i_mtime_nsec;
  69   grub_uint32_t i_uid;
  70   grub_uint32_t i_gid;
  71   grub_uint16_t i_mode;
  72   grub_uint16_t i_links_count;
  73   grub_uint32_t i_flags;
  74   grub_uint64_t i_bmap[NILFS_INODE_BMAP_SIZE];
  75 #define i_device_code   i_bmap[0]
  76   grub_uint64_t i_xattr;
  77   grub_uint32_t i_generation;
  78   grub_uint32_t i_pad;
  79 };
  80
  81 struct grub_nilfs2_super_root
  82 {
  83   grub_uint32_t sr_sum;
  84   grub_uint16_t sr_bytes;
  85   grub_uint16_t sr_flags;
  86   grub_uint64_t sr_nongc_ctime;
  87   struct grub_nilfs2_inode sr_dat;
  88   struct grub_nilfs2_inode sr_cpfile;
  89   struct grub_nilfs2_inode sr_sufile;
  90 };
  91
  92 struct grub_nilfs2_super_block
  93 {
  94   grub_uint32_t s_rev_level;
  95   grub_uint16_t s_minor_rev_level;
  96   grub_uint16_t s_magic;
  97   grub_uint16_t s_bytes;
  98   grub_uint16_t s_flags;
  99   grub_uint32_t s_crc_seed;
 100   grub_uint32_t s_sum;
 101   grub_uint32_t s_log_block_size;
 102   grub_uint64_t s_nsegments;
 103   grub_uint64_t s_dev_size;
 104   grub_uint64_t s_first_data_block;
 105   grub_uint32_t s_blocks_per_segment;
 106   grub_uint32_t s_r_segments_percentage;
 107   grub_uint64_t s_last_cno;
 108   grub_uint64_t s_last_pseg;
 109   grub_uint64_t s_last_seq;
 110   grub_uint64_t s_free_blocks_count;
 111   grub_uint64_t s_ctime;
 112   grub_uint64_t s_mtime;
 113   grub_uint64_t s_wtime;
 114   grub_uint16_t s_mnt_count;
 115   grub_uint16_t s_max_mnt_count;
 116   grub_uint16_t s_state;
 117   grub_uint16_t s_errors;
 118   grub_uint64_t s_lastcheck;
 119   grub_uint32_t s_checkinterval;
 120   grub_uint32_t s_creator_os;
 121   grub_uint16_t s_def_resuid;
 122   grub_uint16_t s_def_resgid;
 123   grub_uint32_t s_first_ino;
 124   grub_uint16_t s_inode_size;
 125   grub_uint16_t s_dat_entry_size;
 126   grub_uint16_t s_checkpoint_size;
 127   grub_uint16_t s_segment_usage_size;
 128   grub_uint8_t s_uuid[16];
 129   char s_volume_name[80];
 130   grub_uint32_t s_c_interval;
 131   grub_uint32_t s_c_block_max;
 132   grub_uint32_t s_reserved[192];
 133 };
 134
 135 struct grub_nilfs2_dir_entry
 136 {
 137   grub_uint64_t inode;
 138   grub_uint16_t rec_len;
 139 #define MAX_NAMELEN 255
 140   grub_uint8_t name_len;
 141   grub_uint8_t file_type;
 142 #if 0                           /* followed by file name. */
 143   char name[NILFS_NAME_LEN];
 144   char pad;
 145 #endif
 146 } GRUB_PACKED;
 147
 148 enum
 149 {
 150   NILFS_FT_UNKNOWN,
 151   NILFS_FT_REG_FILE,
 152   NILFS_FT_DIR,
 153   NILFS_FT_CHRDEV,
 154   NILFS_FT_BLKDEV,
 155   NILFS_FT_FIFO,
 156   NILFS_FT_SOCK,
 157   NILFS_FT_SYMLINK,
 158   NILFS_FT_MAX
 159 };
 160
 161 struct grub_nilfs2_finfo
 162 {
 163   grub_uint64_t fi_ino;
 164   grub_uint64_t fi_cno;
 165   grub_uint32_t fi_nblocks;
 166   grub_uint32_t fi_ndatablk;
 167 };
 168
 169 struct grub_nilfs2_binfo_v
 170 {
 171   grub_uint64_t bi_vblocknr;
 172   grub_uint64_t bi_blkoff;
 173 };
 174
 175 struct grub_nilfs2_binfo_dat
 176 {
 177   grub_uint64_t bi_blkoff;
 178   grub_uint8_t bi_level;
 179   grub_uint8_t bi_pad[7];
 180 };
 181
 182 union grub_nilfs2_binfo
 183 {
 184   struct grub_nilfs2_binfo_v bi_v;
 185   struct grub_nilfs2_binfo_dat bi_dat;
 186 };
 187
 188 struct grub_nilfs2_segment_summary
 189 {
 190   grub_uint32_t ss_datasum;
 191   grub_uint32_t ss_sumsum;
 192   grub_uint32_t ss_magic;
 193   grub_uint16_t ss_bytes;
 194   grub_uint16_t ss_flags;
 195   grub_uint64_t ss_seq;
 196   grub_uint64_t ss_create;
 197   grub_uint64_t ss_next;
 198   grub_uint32_t ss_nblocks;
 199   grub_uint32_t ss_nfinfo;
 200   grub_uint32_t ss_sumbytes;
 201   grub_uint32_t ss_pad;
 202 };
 203
 204 struct grub_nilfs2_btree_node
 205 {
 206   grub_uint8_t bn_flags;
 207   grub_uint8_t bn_level;
 208   grub_uint16_t bn_nchildren;
 209   grub_uint32_t bn_pad;
 210   grub_uint64_t keys[0];
 211 };
 212
 213 struct grub_nilfs2_palloc_group_desc
 214 {
 215   grub_uint32_t pg_nfrees;
 216 };
 217
 218 #define LOG_SIZE_GROUP_DESC 2
 219
 220 #define LOG_NILFS_DAT_ENTRY_SIZE 5
 221 struct grub_nilfs2_dat_entry
 222 {
 223   grub_uint64_t de_blocknr;
 224   grub_uint64_t de_start;
 225   grub_uint64_t de_end;
 226   grub_uint64_t de_rsv;
 227 };
 228
 229 struct grub_nilfs2_snapshot_list
 230 {
 231   grub_uint64_t ssl_next;
 232   grub_uint64_t ssl_prev;
 233 };
 234
 235 struct grub_nilfs2_cpfile_header
 236 {
 237   grub_uint64_t ch_ncheckpoints;
 238   grub_uint64_t ch_nsnapshots;
 239   struct grub_nilfs2_snapshot_list ch_snapshot_list;
 240 };
 241
 242 struct grub_nilfs2_checkpoint
 243 {
 244   grub_uint32_t cp_flags;
 245   grub_uint32_t cp_checkpoints_count;
 246   struct grub_nilfs2_snapshot_list cp_snapshot_list;
 247   grub_uint64_t cp_cno;
 248   grub_uint64_t cp_create;
 249   grub_uint64_t cp_nblk_inc;
 250   grub_uint64_t cp_inodes_count;
 251   grub_uint64_t cp_blocks_count;
 252   struct grub_nilfs2_inode cp_ifile_inode;
 253 };
 254
 255
 256 #define NILFS_BMAP_LARGE        0x1
 257 #define NILFS_BMAP_SIZE (NILFS_INODE_BMAP_SIZE * sizeof(grub_uint64_t))
 258
 259 /* nilfs extra padding for nonroot btree node. */
 260 #define NILFS_BTREE_NODE_EXTRA_PAD_SIZE (sizeof(grub_uint64_t))
 261 #define NILFS_BTREE_ROOT_SIZE   NILFS_BMAP_SIZE
 262 #define NILFS_BTREE_ROOT_NCHILDREN_MAX \
 263  ((NILFS_BTREE_ROOT_SIZE - sizeof(struct nilfs_btree_node)) / \
 264   (sizeof(grub_uint64_t) + sizeof(grub_uint64_t)) )
 265
 266
 267 struct grub_fshelp_node
 268 {
 269   struct grub_nilfs2_data *data;
 270   struct grub_nilfs2_inode inode;
 271   grub_uint64_t ino;
 272   int inode_read;
 273 };
 274
 275 struct grub_nilfs2_data
 276 {
 277   struct grub_nilfs2_super_block sblock;
 278   struct grub_nilfs2_super_root sroot;
 279   struct grub_nilfs2_inode ifile;
 280   grub_disk_t disk;
 281   struct grub_nilfs2_inode *inode;
 282   struct grub_fshelp_node diropen;
 283 };
 284
 285 /* Log2 size of nilfs2 block in 512 blocks.  */
 286 #define LOG2_NILFS2_BLOCK_SIZE(data)                    \
 287         (grub_le_to_cpu32 (data->sblock.s_log_block_size) + 1)
 288
 289 /* Log2 size of nilfs2 block in bytes.  */
 290 #define LOG2_BLOCK_SIZE(data)                                   \
 291         (grub_le_to_cpu32 (data->sblock.s_log_block_size) + 10)
 292
 293 /* The size of an nilfs2 block in bytes.  */
 294 #define NILFS2_BLOCK_SIZE(data)         (1 << LOG2_BLOCK_SIZE (data))
 295
 296 static grub_uint64_t
 297 grub_nilfs2_dat_translate (struct grub_nilfs2_data *data, grub_uint64_t key);
 298 static grub_dl_t my_mod;
 299 \f
 300
 301
 302 static inline unsigned long
 303 grub_nilfs2_log_palloc_entries_per_group (struct grub_nilfs2_data *data)
 304 {
 305   return LOG2_BLOCK_SIZE (data) + 3;
 306 }
 307
 308 static inline grub_uint64_t
 309 grub_nilfs2_palloc_group (struct grub_nilfs2_data *data,
 310                           grub_uint64_t nr, grub_uint64_t * offset)
 311 {
 312   *offset = nr & ((1 << grub_nilfs2_log_palloc_entries_per_group (data)) - 1);
 313   return nr >> grub_nilfs2_log_palloc_entries_per_group (data);
 314 }
 315
 316 static inline grub_uint32_t
 317 grub_nilfs2_palloc_log_groups_per_desc_block (struct grub_nilfs2_data *data)
 318 {
 319   return LOG2_BLOCK_SIZE (data) - LOG_SIZE_GROUP_DESC;
 320
 321   COMPILE_TIME_ASSERT (sizeof (struct grub_nilfs2_palloc_group_desc)
 322                        == (1 << LOG_SIZE_GROUP_DESC));
 323 }
 324
 325 static inline grub_uint32_t
 326 grub_nilfs2_log_entries_per_block_log (struct grub_nilfs2_data *data,
 327                                        unsigned long log_entry_size)
 328 {
 329   return LOG2_BLOCK_SIZE (data) - log_entry_size;
 330 }
 331
 332
 333 static inline grub_uint32_t
 334 grub_nilfs2_blocks_per_group_log (struct grub_nilfs2_data *data,
 335                                   unsigned long log_entry_size)
 336 {
 337   return (1 << (grub_nilfs2_log_palloc_entries_per_group (data)
 338                 - grub_nilfs2_log_entries_per_block_log (data,
 339                                                          log_entry_size))) + 1;
 340 }
 341
 342 static inline grub_uint32_t
 343 grub_nilfs2_blocks_per_desc_block_log (struct grub_nilfs2_data *data,
 344                                        unsigned long log_entry_size)
 345 {
 346   return(grub_nilfs2_blocks_per_group_log (data, log_entry_size)
 347          << grub_nilfs2_palloc_log_groups_per_desc_block (data)) + 1;
 348 }
 349
 350 static inline grub_uint32_t
 351 grub_nilfs2_palloc_desc_block_offset_log (struct grub_nilfs2_data *data,
 352                                           unsigned long group,
 353                                           unsigned long log_entry_size)
 354 {
 355   grub_uint32_t desc_block =
 356     group >> grub_nilfs2_palloc_log_groups_per_desc_block (data);
 357   return desc_block * grub_nilfs2_blocks_per_desc_block_log (data,
 358                                                              log_entry_size);
 359 }
 360
 361 static inline grub_uint32_t
 362 grub_nilfs2_palloc_bitmap_block_offset (struct grub_nilfs2_data *data,
 363                                         unsigned long group,
 364                                         unsigned long log_entry_size)
 365 {
 366   unsigned long desc_offset = group
 367     & ((1 << grub_nilfs2_palloc_log_groups_per_desc_block (data)) - 1);
 368
 369   return grub_nilfs2_palloc_desc_block_offset_log (data, group, log_entry_size)
 370     + 1
 371     + desc_offset * grub_nilfs2_blocks_per_group_log (data, log_entry_size);
 372 }
 373
 374 static inline grub_uint32_t
 375 grub_nilfs2_palloc_entry_offset_log (struct grub_nilfs2_data *data,
 376                                      grub_uint64_t nr,
 377                                      unsigned long log_entry_size)
 378 {
 379   unsigned long group;
 380   grub_uint64_t group_offset;
 381
 382   group = grub_nilfs2_palloc_group (data, nr, &group_offset);
 383
 384   return grub_nilfs2_palloc_bitmap_block_offset (data, group,
 385                                                  log_entry_size) + 1 +
 386     (group_offset >> grub_nilfs2_log_entries_per_block_log (data,
 387                                                             log_entry_size));
 388
 389 }
 390
 391 static inline struct grub_nilfs2_btree_node *
 392 grub_nilfs2_btree_get_root (struct grub_nilfs2_inode *inode)
 393 {
 394   return (struct grub_nilfs2_btree_node *) &inode->i_bmap[0];
 395 }
 396
 397 static inline int
 398 grub_nilfs2_btree_get_level (struct grub_nilfs2_btree_node *node)
 399 {
 400   return node->bn_level;
 401 }
 402
 403 static inline grub_uint64_t *
 404 grub_nilfs2_btree_node_dkeys (struct grub_nilfs2_btree_node *node)
 405 {
 406   return (node->keys +
 407           ((node->bn_flags & NILFS_BTREE_NODE_ROOT) ?
 408            0 : (NILFS_BTREE_NODE_EXTRA_PAD_SIZE / sizeof (grub_uint64_t))));
 409 }
 410
 411 static inline grub_uint64_t
 412 grub_nilfs2_btree_node_get_key (struct grub_nilfs2_btree_node *node,
 413                                 int index)
 414 {
 415   return grub_le_to_cpu64 (*(grub_nilfs2_btree_node_dkeys (node) + index));
 416 }
 417
 418 static inline int
 419 grub_nilfs2_btree_node_nchildren_max (struct grub_nilfs2_data *data,
 420                                       struct grub_nilfs2_btree_node *node)
 421 {
 422   int node_children_max = ((NILFS2_BLOCK_SIZE (data) -
 423                             sizeof (struct grub_nilfs2_btree_node) -
 424                             NILFS_BTREE_NODE_EXTRA_PAD_SIZE) /
 425                            (sizeof (grub_uint64_t) + sizeof (grub_uint64_t)));
 426
 427   return (node->bn_flags & NILFS_BTREE_NODE_ROOT) ? 3 : node_children_max;
 428 }
 429
 430 static inline int
 431 grub_nilfs2_btree_node_lookup (struct grub_nilfs2_data *data,
 432                                struct grub_nilfs2_btree_node *node,
 433                                grub_uint64_t key, int *indexp)
 434 {
 435   grub_uint64_t nkey;
 436   int index = 0, low, high, s;
 437
 438   low = 0;
 439
 440   high = grub_le_to_cpu16 (node->bn_nchildren) - 1;
 441   if (high >= grub_nilfs2_btree_node_nchildren_max (data, node))
 442     {
 443       grub_error (GRUB_ERR_BAD_FS, "too many children");
 444       *indexp = index;
 445       return 0;
 446     }
 447
 448   s = 0;
 449   while (low <= high)
 450     {
 451       index = (low + high) / 2;
 452       nkey = grub_nilfs2_btree_node_get_key (node, index);
 453       if (nkey == key)
 454         {
 455           *indexp = index;
 456           return 1;
 457         }
 458       else if (nkey < key)
 459         {
 460           low = index + 1;
 461           s = -1;
 462         }
 463       else
 464         {
 465           high = index - 1;
 466           s = 1;
 467         }
 468     }
 469
 470   if (node->bn_level > NILFS_BTREE_LEVEL_NODE_MIN)
 471     {
 472       if (s > 0 && index > 0)
 473         index--;
 474     }
 475   else if (s < 0)
 476     index++;
 477
 478   *indexp = index;
 479   return s == 0;
 480 }
 481
 482 static inline grub_uint64_t *
 483 grub_nilfs2_btree_node_dptrs (struct grub_nilfs2_data *data,
 484                               struct grub_nilfs2_btree_node *node)
 485 {
 486   return (grub_uint64_t *) (grub_nilfs2_btree_node_dkeys (node) +
 487                             grub_nilfs2_btree_node_nchildren_max (data,
 488                                                                   node));
 489 }
 490
 491 static inline grub_uint64_t
 492 grub_nilfs2_btree_node_get_ptr (struct grub_nilfs2_data *data,
 493                                 struct grub_nilfs2_btree_node *node,
 494                                 int index)
 495 {
 496   return
 497     grub_le_to_cpu64 (*(grub_nilfs2_btree_node_dptrs (data, node) + index));
 498 }
 499
 500 static inline int
 501 grub_nilfs2_btree_get_nonroot_node (struct grub_nilfs2_data *data,
 502                                     grub_uint64_t ptr, void *block)
 503 {
 504   grub_disk_t disk = data->disk;
 505   unsigned int nilfs2_block_count = (1 << LOG2_NILFS2_BLOCK_SIZE (data));
 506
 507   return grub_disk_read (disk, ptr * nilfs2_block_count, 0,
 508                          NILFS2_BLOCK_SIZE (data), block);
 509 }
 510
 511 static grub_uint64_t
 512 grub_nilfs2_btree_lookup (struct grub_nilfs2_data *data,
 513                           struct grub_nilfs2_inode *inode,
 514                           grub_uint64_t key, int need_translate)
 515 {
 516   struct grub_nilfs2_btree_node *node;
 517   void *block;
 518   grub_uint64_t ptr;
 519   int level, found = 0, index;
 520
 521   block = grub_malloc (NILFS2_BLOCK_SIZE (data));
 522   if (!block)
 523     return -1;
 524
 525   node = grub_nilfs2_btree_get_root (inode);
 526   level = grub_nilfs2_btree_get_level (node);
 527
 528   found = grub_nilfs2_btree_node_lookup (data, node, key, &index);
 529
 530   if (grub_errno != GRUB_ERR_NONE)
 531     goto fail;
 532
 533   ptr = grub_nilfs2_btree_node_get_ptr (data, node, index);
 534   if (need_translate)
 535     ptr = grub_nilfs2_dat_translate (data, ptr);
 536
 537   for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--)
 538     {
 539       grub_nilfs2_btree_get_nonroot_node (data, ptr, block);
 540       if (grub_errno)
 541         {
 542           goto fail;
 543         }
 544       node = (struct grub_nilfs2_btree_node *) block;
 545
 546       if (node->bn_level != level)
 547         {
 548           grub_error (GRUB_ERR_BAD_FS, "btree level mismatch\n");
 549           goto fail;
 550         }
 551
 552       if (!found)
 553         found = grub_nilfs2_btree_node_lookup (data, node, key, &index);
 554       else
 555         index = 0;
 556
 557       if (index < grub_nilfs2_btree_node_nchildren_max (data, node) &&
 558           grub_errno == GRUB_ERR_NONE)
 559         {
 560           ptr = grub_nilfs2_btree_node_get_ptr (data, node, index);
 561           if (need_translate)
 562             ptr = grub_nilfs2_dat_translate (data, ptr);
 563         }
 564       else
 565         {
 566           grub_error (GRUB_ERR_BAD_FS, "btree corruption\n");
 567           goto fail;
 568         }
 569     }
 570
 571   grub_free (block);
 572
 573   if (!found)
 574     return -1;
 575
 576   return ptr;
 577  fail:
 578   grub_free (block);
 579   return -1;
 580 }
 581
 582 static inline grub_uint64_t
 583 grub_nilfs2_direct_lookup (struct grub_nilfs2_inode *inode, grub_uint64_t key)
 584 {
 585   if (1 + key > 6)
 586     {
 587       grub_error (GRUB_ERR_BAD_FS, "key is too large");
 588       return 0xffffffffffffffff;
 589     }
 590   return grub_le_to_cpu64 (inode->i_bmap[1 + key]);
 591 }
 592
 593 static inline grub_uint64_t
 594 grub_nilfs2_bmap_lookup (struct grub_nilfs2_data *data,
 595                          struct grub_nilfs2_inode *inode,
 596                          grub_uint64_t key, int need_translate)
 597 {
 598   struct grub_nilfs2_btree_node *root = grub_nilfs2_btree_get_root (inode);
 599   if (root->bn_flags & NILFS_BMAP_LARGE)
 600     return grub_nilfs2_btree_lookup (data, inode, key, need_translate);
 601   else
 602     {
 603       grub_uint64_t ptr;
 604       ptr = grub_nilfs2_direct_lookup (inode, key);
 605       if (ptr != ((grub_uint64_t) 0xffffffffffffffff) && need_translate)
 606         ptr = grub_nilfs2_dat_translate (data, ptr);
 607       return ptr;
 608     }
 609 }
 610
 611 static grub_uint64_t
 612 grub_nilfs2_dat_translate (struct grub_nilfs2_data *data, grub_uint64_t key)
 613 {
 614   struct grub_nilfs2_dat_entry entry;
 615   grub_disk_t disk = data->disk;
 616   grub_uint64_t pptr;
 617   grub_uint64_t blockno, offset;
 618   unsigned int nilfs2_block_count = (1 << LOG2_NILFS2_BLOCK_SIZE (data));
 619
 620   blockno = grub_nilfs2_palloc_entry_offset_log (data, key,
 621                                                  LOG_NILFS_DAT_ENTRY_SIZE);
 622
 623   offset = ((key * sizeof (struct grub_nilfs2_dat_entry))
 624             & ((1 << LOG2_BLOCK_SIZE (data)) - 1));
 625
 626   pptr = grub_nilfs2_bmap_lookup (data, &data->sroot.sr_dat, blockno, 0);
 627   if (pptr == (grub_uint64_t) - 1)
 628     {
 629       grub_error (GRUB_ERR_BAD_FS, "btree lookup failure");
 630       return -1;
 631     }
 632
 633   grub_disk_read (disk, pptr * nilfs2_block_count, offset,
 634                   sizeof (struct grub_nilfs2_dat_entry), &entry);
 635
 636   return grub_le_to_cpu64 (entry.de_blocknr);
 637 }
 638
 639
 640 static grub_disk_addr_t
 641 grub_nilfs2_read_block (grub_fshelp_node_t node, grub_disk_addr_t fileblock)
 642 {
 643   struct grub_nilfs2_data *data = node->data;
 644   struct grub_nilfs2_inode *inode = &node->inode;
 645   grub_uint64_t pptr = -1;
 646
 647   pptr = grub_nilfs2_bmap_lookup (data, inode, fileblock, 1);
 648   if (pptr == (grub_uint64_t) - 1)
 649     {
 650       grub_error (GRUB_ERR_BAD_FS, "btree lookup failure");
 651       return -1;
 652     }
 653
 654   return pptr;
 655 }
 656
 657 /* Read LEN bytes from the file described by DATA starting with byte
 658    POS.  Return the amount of read bytes in READ.  */
 659 static grub_ssize_t
 660 grub_nilfs2_read_file (grub_fshelp_node_t node,
 661                        grub_disk_read_hook_t read_hook, void *read_hook_data,
 662                        grub_off_t pos, grub_size_t len, char *buf)
 663 {
 664   return grub_fshelp_read_file (node->data->disk, node,
 665                                 read_hook, read_hook_data,
 666                                 pos, len, buf, grub_nilfs2_read_block,
 667                                 grub_le_to_cpu64 (node->inode.i_size),
 668                                 LOG2_NILFS2_BLOCK_SIZE (node->data), 0);
 669
 670 }
 671
 672 static grub_err_t
 673 grub_nilfs2_read_checkpoint (struct grub_nilfs2_data *data,
 674                              grub_uint64_t cpno,
 675                              struct grub_nilfs2_checkpoint *cpp)
 676 {
 677   grub_uint64_t blockno;
 678   grub_uint64_t offset;
 679   grub_uint64_t pptr;
 680   grub_disk_t disk = data->disk;
 681   unsigned int nilfs2_block_count = (1 << LOG2_NILFS2_BLOCK_SIZE (data));
 682
 683   /* Assume sizeof(struct grub_nilfs2_cpfile_header) <
 684      sizeof(struct grub_nilfs2_checkpoint).
 685    */
 686   blockno = grub_divmod64 (cpno, NILFS2_BLOCK_SIZE (data) /
 687                           sizeof (struct grub_nilfs2_checkpoint), &offset);
 688
 689   pptr = grub_nilfs2_bmap_lookup (data, &data->sroot.sr_cpfile, blockno, 1);
 690   if (pptr == (grub_uint64_t) - 1)
 691     {
 692       return grub_error (GRUB_ERR_BAD_FS, "btree lookup failure");
 693     }
 694
 695   return grub_disk_read (disk, pptr * nilfs2_block_count,
 696                          offset * sizeof (struct grub_nilfs2_checkpoint),
 697                          sizeof (struct grub_nilfs2_checkpoint), cpp);
 698 }
 699
 700 static inline grub_err_t
 701 grub_nilfs2_read_last_checkpoint (struct grub_nilfs2_data *data,
 702                                   struct grub_nilfs2_checkpoint *cpp)
 703 {
 704   return grub_nilfs2_read_checkpoint (data,
 705                                       grub_le_to_cpu64 (data->
 706                                                         sblock.s_last_cno),
 707                                       cpp);
 708 }
 709
 710 /* Read the inode INO for the file described by DATA into INODE.  */
 711 static grub_err_t
 712 grub_nilfs2_read_inode (struct grub_nilfs2_data *data,
 713                         grub_uint64_t ino, struct grub_nilfs2_inode *inodep)
 714 {
 715   grub_uint64_t blockno;
 716   grub_uint64_t offset;
 717   grub_uint64_t pptr;
 718   grub_disk_t disk = data->disk;
 719   unsigned int nilfs2_block_count = (1 << LOG2_NILFS2_BLOCK_SIZE (data));
 720
 721   blockno = grub_nilfs2_palloc_entry_offset_log (data, ino,
 722                                                  LOG_INODE_SIZE);
 723
 724   offset = ((sizeof (struct grub_nilfs2_inode) * ino)
 725             & ((1 << LOG2_BLOCK_SIZE (data)) - 1));
 726   pptr = grub_nilfs2_bmap_lookup (data, &data->ifile, blockno, 1);
 727   if (pptr == (grub_uint64_t) - 1)
 728     {
 729       return grub_error (GRUB_ERR_BAD_FS, "btree lookup failure");
 730     }
 731
 732   return grub_disk_read (disk, pptr * nilfs2_block_count, offset,
 733                          sizeof (struct grub_nilfs2_inode), inodep);
 734 }
 735
 736 static int
 737 grub_nilfs2_valid_sb (struct grub_nilfs2_super_block *sbp)
 738 {
 739   if (grub_le_to_cpu16 (sbp->s_magic) != NILFS2_SUPER_MAGIC)
 740     return 0;
 741
 742   if (grub_le_to_cpu32 (sbp->s_rev_level) != NILFS_SUPORT_REV)
 743     return 0;
 744
 745   /* 20 already means 1GiB blocks. We don't want to deal with blocks overflowing int32. */
 746   if (grub_le_to_cpu32 (sbp->s_log_block_size) > 20)
 747     return 0;
 748
 749   return 1;
 750 }
 751
 752 static grub_err_t
 753 grub_nilfs2_load_sb (struct grub_nilfs2_data *data)
 754 {
 755   grub_disk_t disk = data->disk;
 756   struct grub_nilfs2_super_block sb2;
 757   grub_uint64_t partition_size;
 758   int valid[2];
 759   int swp = 0;
 760   grub_err_t err;
 761
 762   /* Read first super block. */
 763   err = grub_disk_read (disk, NILFS_1ST_SUPER_BLOCK, 0,
 764                         sizeof (struct grub_nilfs2_super_block), &data->sblock);
 765   if (err)
 766     return err;
 767   /* Make sure if 1st super block is valid.  */
 768   valid[0] = grub_nilfs2_valid_sb (&data->sblock);
 769
 770   if (valid[0])
 771     partition_size = (grub_le_to_cpu64 (data->sblock.s_dev_size)
 772                       >> GRUB_DISK_SECTOR_BITS);
 773   else
 774     partition_size = grub_disk_native_sectors (disk);
 775   if (partition_size != GRUB_DISK_SIZE_UNKNOWN)
 776     {
 777       /* Read second super block. */
 778       err = grub_disk_read (disk, NILFS_2ND_SUPER_BLOCK (partition_size), 0,
 779                             sizeof (struct grub_nilfs2_super_block), &sb2);
 780       if (err)
 781         {
 782           valid[1] = 0;
 783           grub_errno = GRUB_ERR_NONE;
 784         }
 785       else
 786         /* Make sure if 2nd super block is valid.  */
 787         valid[1] = grub_nilfs2_valid_sb (&sb2);
 788     }
 789   else
 790     /* 2nd super block may not exist, so it's invalid. */
 791     valid[1] = 0;
 792
 793   if (!valid[0] && !valid[1])
 794     return grub_error (GRUB_ERR_BAD_FS, "not a nilfs2 filesystem");
 795
 796   swp = valid[1] && (!valid[0] ||
 797                      grub_le_to_cpu64 (data->sblock.s_last_cno) <
 798                      grub_le_to_cpu64 (sb2.s_last_cno));
 799
 800   /* swap if first super block is invalid or older than second one. */
 801   if (swp)
 802     grub_memcpy (&data->sblock, &sb2,
 803                  sizeof (struct grub_nilfs2_super_block));
 804
 805   return GRUB_ERR_NONE;
 806 }
 807
 808 static struct grub_nilfs2_data *
 809 grub_nilfs2_mount (grub_disk_t disk)
 810 {
 811   struct grub_nilfs2_data *data;
 812   struct grub_nilfs2_segment_summary ss;
 813   struct grub_nilfs2_checkpoint last_checkpoint;
 814   grub_uint64_t last_pseg;
 815   grub_uint32_t nblocks;
 816   unsigned int nilfs2_block_count;
 817
 818   data = grub_malloc (sizeof (struct grub_nilfs2_data));
 819   if (!data)
 820     return 0;
 821
 822   data->disk = disk;
 823
 824   /* Read the superblock.  */
 825   grub_nilfs2_load_sb (data);
 826   if (grub_errno)
 827     goto fail;
 828
 829   nilfs2_block_count = (1 << LOG2_NILFS2_BLOCK_SIZE (data));
 830
 831   /* Read the last segment summary. */
 832   last_pseg = grub_le_to_cpu64 (data->sblock.s_last_pseg);
 833   grub_disk_read (disk, last_pseg * nilfs2_block_count, 0,
 834                   sizeof (struct grub_nilfs2_segment_summary), &ss);
 835
 836   if (grub_errno)
 837     goto fail;
 838
 839   /* Read the super root block. */
 840   nblocks = grub_le_to_cpu32 (ss.ss_nblocks);
 841   grub_disk_read (disk, (last_pseg + (nblocks - 1)) * nilfs2_block_count, 0,
 842                   sizeof (struct grub_nilfs2_super_root), &data->sroot);
 843
 844   if (grub_errno)
 845     goto fail;
 846
 847   grub_nilfs2_read_last_checkpoint (data, &last_checkpoint);
 848
 849   if (grub_errno)
 850     goto fail;
 851
 852   grub_memcpy (&data->ifile, &last_checkpoint.cp_ifile_inode,
 853                sizeof (struct grub_nilfs2_inode));
 854
 855   data->diropen.data = data;
 856   data->diropen.ino = 2;
 857   data->diropen.inode_read = 1;
 858   data->inode = &data->diropen.inode;
 859
 860   grub_nilfs2_read_inode (data, 2, data->inode);
 861
 862   return data;
 863
 864 fail:
 865   if (grub_errno == GRUB_ERR_OUT_OF_RANGE)
 866     grub_error (GRUB_ERR_BAD_FS, "not a nilfs2 filesystem");
 867
 868   grub_free (data);
 869   return 0;
 870 }
 871
 872 static char *
 873 grub_nilfs2_read_symlink (grub_fshelp_node_t node)
 874 {
 875   char *symlink;
 876   struct grub_fshelp_node *diro = node;
 877
 878   if (!diro->inode_read)
 879     {
 880       grub_nilfs2_read_inode (diro->data, diro->ino, &diro->inode);
 881       if (grub_errno)
 882         return 0;
 883     }
 884
 885   symlink = grub_malloc (grub_le_to_cpu64 (diro->inode.i_size) + 1);
 886   if (!symlink)
 887     return 0;
 888
 889   grub_nilfs2_read_file (diro, 0, 0, 0,
 890                          grub_le_to_cpu64 (diro->inode.i_size), symlink);
 891   if (grub_errno)
 892     {
 893       grub_free (symlink);
 894       return 0;
 895     }
 896
 897   symlink[grub_le_to_cpu64 (diro->inode.i_size)] = '\0';
 898   return symlink;
 899 }
 900
 901 static int
 902 grub_nilfs2_iterate_dir (grub_fshelp_node_t dir,
 903                          grub_fshelp_iterate_dir_hook_t hook, void *hook_data)
 904 {
 905   grub_off_t fpos = 0;
 906   struct grub_fshelp_node *diro = (struct grub_fshelp_node *) dir;
 907
 908   if (!diro->inode_read)
 909     {
 910       grub_nilfs2_read_inode (diro->data, diro->ino, &diro->inode);
 911       if (grub_errno)
 912         return 0;
 913     }
 914
 915   /* Iterate files.  */
 916   while (fpos < grub_le_to_cpu64 (diro->inode.i_size))
 917     {
 918       struct grub_nilfs2_dir_entry dirent;
 919
 920       grub_nilfs2_read_file (diro, 0, 0, fpos,
 921                              sizeof (struct grub_nilfs2_dir_entry),
 922                              (char *) &dirent);
 923       if (grub_errno)
 924         return 0;
 925
 926       if (dirent.rec_len == 0)
 927         return 0;
 928
 929       if (dirent.name_len != 0)
 930         {
 931           char filename[MAX_NAMELEN + 1];
 932           struct grub_fshelp_node *fdiro;
 933           enum grub_fshelp_filetype type = GRUB_FSHELP_UNKNOWN;
 934
 935           grub_nilfs2_read_file (diro, 0, 0,
 936                                  fpos + sizeof (struct grub_nilfs2_dir_entry),
 937                                  dirent.name_len, filename);
 938           if (grub_errno)
 939             return 0;
 940
 941           fdiro = grub_malloc (sizeof (struct grub_fshelp_node));
 942           if (!fdiro)
 943             return 0;
 944
 945           fdiro->data = diro->data;
 946           fdiro->ino = grub_le_to_cpu64 (dirent.inode);
 947
 948           filename[dirent.name_len] = '\0';
 949
 950           if (dirent.file_type != NILFS_FT_UNKNOWN)
 951             {
 952               fdiro->inode_read = 0;
 953
 954               if (dirent.file_type == NILFS_FT_DIR)
 955                 type = GRUB_FSHELP_DIR;
 956               else if (dirent.file_type == NILFS_FT_SYMLINK)
 957                 type = GRUB_FSHELP_SYMLINK;
 958               else if (dirent.file_type == NILFS_FT_REG_FILE)
 959                 type = GRUB_FSHELP_REG;
 960             }
 961           else
 962             {
 963               /* The filetype can not be read from the dirent, read
 964                  the inode to get more information.  */
 965               grub_nilfs2_read_inode (diro->data,
 966                                       grub_le_to_cpu64 (dirent.inode),
 967                                       &fdiro->inode);
 968               if (grub_errno)
 969                 {
 970                   grub_free (fdiro);
 971                   return 0;
 972                 }
 973
 974               fdiro->inode_read = 1;
 975
 976               if ((grub_le_to_cpu16 (fdiro->inode.i_mode)
 977                    & FILETYPE_INO_MASK) == FILETYPE_INO_DIRECTORY)
 978                 type = GRUB_FSHELP_DIR;
 979               else if ((grub_le_to_cpu16 (fdiro->inode.i_mode)
 980                         & FILETYPE_INO_MASK) == FILETYPE_INO_SYMLINK)
 981                 type = GRUB_FSHELP_SYMLINK;
 982               else if ((grub_le_to_cpu16 (fdiro->inode.i_mode)
 983                         & FILETYPE_INO_MASK) == FILETYPE_INO_REG)
 984                 type = GRUB_FSHELP_REG;
 985             }
 986
 987           if (hook (filename, type, fdiro, hook_data))
 988             return 1;
 989         }
 990
 991       fpos += grub_le_to_cpu16 (dirent.rec_len);
 992     }
 993
 994   return 0;
 995 }
 996
 997 /* Open a file named NAME and initialize FILE.  */
 998 static grub_err_t
 999 grub_nilfs2_open (struct grub_file *file, const char *name)
1000 {
1001   struct grub_nilfs2_data *data = NULL;
1002   struct grub_fshelp_node *fdiro = 0;
1003
1004   grub_dl_ref (my_mod);
1005
1006   data = grub_nilfs2_mount (file->device->disk);
1007   if (!data)
1008     goto fail;
1009
1010   grub_fshelp_find_file (name, &data->diropen, &fdiro,
1011                          grub_nilfs2_iterate_dir, grub_nilfs2_read_symlink,
1012                          GRUB_FSHELP_REG);
1013   if (grub_errno)
1014     goto fail;
1015
1016   if (!fdiro->inode_read)
1017     {
1018       grub_nilfs2_read_inode (data, fdiro->ino, &fdiro->inode);
1019       if (grub_errno)
1020         goto fail;
1021     }
1022
1023   grub_memcpy (data->inode, &fdiro->inode, sizeof (struct grub_nilfs2_inode));
1024   grub_free (fdiro);
1025
1026   file->size = grub_le_to_cpu64 (data->inode->i_size);
1027   file->data = data;
1028   file->offset = 0;
1029
1030   return 0;
1031
1032 fail:
1033   if (fdiro != &data->diropen)
1034     grub_free (fdiro);
1035   grub_free (data);
1036
1037   grub_dl_unref (my_mod);
1038
1039   return grub_errno;
1040 }
1041
1042 static grub_err_t
1043 grub_nilfs2_close (grub_file_t file)
1044 {
1045   grub_free (file->data);
1046
1047   grub_dl_unref (my_mod);
1048
1049   return GRUB_ERR_NONE;
1050 }
1051
1052 /* Read LEN bytes data from FILE into BUF.  */
1053 static grub_ssize_t
1054 grub_nilfs2_read (grub_file_t file, char *buf, grub_size_t len)
1055 {
1056   struct grub_nilfs2_data *data = (struct grub_nilfs2_data *) file->data;
1057
1058   return grub_nilfs2_read_file (&data->diropen,
1059                                 file->read_hook, file->read_hook_data,
1060                                 file->offset, len, buf);
1061 }
1062
1063 /* Context for grub_nilfs2_dir.  */
1064 struct grub_nilfs2_dir_ctx
1065 {
1066   grub_fs_dir_hook_t hook;
1067   void *hook_data;
1068   struct grub_nilfs2_data *data;
1069 };
1070
1071 /* Helper for grub_nilfs2_dir.  */
1072 static int
1073 grub_nilfs2_dir_iter (const char *filename, enum grub_fshelp_filetype filetype,
1074                       grub_fshelp_node_t node, void *data)
1075 {
1076   struct grub_nilfs2_dir_ctx *ctx = data;
1077   struct grub_dirhook_info info;
1078
1079   grub_memset (&info, 0, sizeof (info));
1080   if (!node->inode_read)
1081     {
1082       grub_nilfs2_read_inode (ctx->data, node->ino, &node->inode);
1083       if (!grub_errno)
1084         node->inode_read = 1;
1085       grub_errno = GRUB_ERR_NONE;
1086     }
1087   if (node->inode_read)
1088     {
1089       info.mtimeset = 1;
1090       info.mtime = grub_le_to_cpu64 (node->inode.i_mtime);
1091     }
1092
1093   info.dir = ((filetype & GRUB_FSHELP_TYPE_MASK) == GRUB_FSHELP_DIR);
1094   grub_free (node);
1095   return ctx->hook (filename, &info, ctx->hook_data);
1096 }
1097
1098 static grub_err_t
1099 grub_nilfs2_dir (grub_device_t device, const char *path,
1100                  grub_fs_dir_hook_t hook, void *hook_data)
1101 {
1102   struct grub_nilfs2_dir_ctx ctx = {
1103     .hook = hook,
1104     .hook_data = hook_data
1105   };
1106   struct grub_fshelp_node *fdiro = 0;
1107
1108   grub_dl_ref (my_mod);
1109
1110   ctx.data = grub_nilfs2_mount (device->disk);
1111   if (!ctx.data)
1112     goto fail;
1113
1114   grub_fshelp_find_file (path, &ctx.data->diropen, &fdiro,
1115                          grub_nilfs2_iterate_dir, grub_nilfs2_read_symlink,
1116                          GRUB_FSHELP_DIR);
1117   if (grub_errno)
1118     goto fail;
1119
1120   grub_nilfs2_iterate_dir (fdiro, grub_nilfs2_dir_iter, &ctx);
1121
1122 fail:
1123   if (fdiro != &ctx.data->diropen)
1124     grub_free (fdiro);
1125   grub_free (ctx.data);
1126
1127   grub_dl_unref (my_mod);
1128
1129   return grub_errno;
1130 }
1131
1132 static grub_err_t
1133 grub_nilfs2_label (grub_device_t device, char **label)
1134 {
1135   struct grub_nilfs2_data *data;
1136   grub_disk_t disk = device->disk;
1137
1138   grub_dl_ref (my_mod);
1139
1140   data = grub_nilfs2_mount (disk);
1141   if (data)
1142     *label = grub_strndup (data->sblock.s_volume_name,
1143                            sizeof (data->sblock.s_volume_name));
1144   else
1145     *label = NULL;
1146
1147   grub_dl_unref (my_mod);
1148
1149   grub_free (data);
1150
1151   return grub_errno;
1152 }
1153
1154 static grub_err_t
1155 grub_nilfs2_uuid (grub_device_t device, char **uuid)
1156 {
1157   struct grub_nilfs2_data *data;
1158   grub_disk_t disk = device->disk;
1159
1160   grub_dl_ref (my_mod);
1161
1162   data = grub_nilfs2_mount (disk);
1163   if (data)
1164     {
1165       *uuid =
1166         grub_xasprintf
1167         ("%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-%02x%02x%02x%02x%02x%02x",
1168          data->sblock.s_uuid[0], data->sblock.s_uuid[1],
1169          data->sblock.s_uuid[2], data->sblock.s_uuid[3],
1170          data->sblock.s_uuid[4], data->sblock.s_uuid[5],
1171          data->sblock.s_uuid[6], data->sblock.s_uuid[7],
1172          data->sblock.s_uuid[8], data->sblock.s_uuid[9],
1173          data->sblock.s_uuid[10], data->sblock.s_uuid[11],
1174          data->sblock.s_uuid[12], data->sblock.s_uuid[13],
1175          data->sblock.s_uuid[14], data->sblock.s_uuid[15]);
1176     }
1177   else
1178     *uuid = NULL;
1179
1180   grub_dl_unref (my_mod);
1181
1182   grub_free (data);
1183
1184   return grub_errno;
1185 }
1186
1187 /* Get mtime.  */
1188 static grub_err_t
1189 grub_nilfs2_mtime (grub_device_t device, grub_int64_t * tm)
1190 {
1191   struct grub_nilfs2_data *data;
1192   grub_disk_t disk = device->disk;
1193
1194   grub_dl_ref (my_mod);
1195
1196   data = grub_nilfs2_mount (disk);
1197   if (!data)
1198     *tm = 0;
1199   else
1200     *tm = (grub_int32_t) grub_le_to_cpu64 (data->sblock.s_wtime);
1201
1202   grub_dl_unref (my_mod);
1203
1204   grub_free (data);
1205
1206   return grub_errno;
1207 }
1208 \f
1209
1210
1211 static struct grub_fs grub_nilfs2_fs = {
1212   .name = "nilfs2",
1213   .fs_dir = grub_nilfs2_dir,
1214   .fs_open = grub_nilfs2_open,
1215   .fs_read = grub_nilfs2_read,
1216   .fs_close = grub_nilfs2_close,
1217   .fs_label = grub_nilfs2_label,
1218   .fs_uuid = grub_nilfs2_uuid,
1219   .fs_mtime = grub_nilfs2_mtime,
1220 #ifdef GRUB_UTIL
1221   .reserved_first_sector = 1,
1222   .blocklist_install = 0,
1223 #endif
1224   .next = 0
1225 };
1226
1227 GRUB_MOD_INIT (nilfs2)
1228 {
1229   COMPILE_TIME_ASSERT ((1 << LOG_NILFS_DAT_ENTRY_SIZE)
1230                        == sizeof (struct
1231                                   grub_nilfs2_dat_entry));
1232   COMPILE_TIME_ASSERT (1 << LOG_INODE_SIZE
1233                        == sizeof (struct grub_nilfs2_inode));
1234   grub_fs_register (&grub_nilfs2_fs);
1235   my_mod = mod;
1236 }
1237
1238 GRUB_MOD_FINI (nilfs2)
1239 {
1240   grub_fs_unregister (&grub_nilfs2_fs);
1241 }