grub-core/fs/bfs.c

2N/A/* bfs.c - The Bee File System.  */
2N/A/*
2N/A *  GRUB  --  GRand Unified Bootloader
2N/A *  Copyright (C) 2010,2011  Free Software Foundation, Inc.
2N/A *
2N/A *  GRUB is free software: you can redistribute it and/or modify
2N/A *  it under the terms of the GNU General Public License as published by
2N/A *  the Free Software Foundation, either version 3 of the License, or
2N/A *  (at your option) any later version.
2N/A *
2N/A *  GRUB is distributed in the hope that it will be useful,
2N/A *  but WITHOUT ANY WARRANTY; without even the implied warranty of
2N/A *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
2N/A *  GNU General Public License for more details.
2N/A *
2N/A *  You should have received a copy of the GNU General Public License
2N/A *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
2N/A */
2N/A/*
2N/A  Based on the book "Practical File System Design by Dominic Giampaolo
2N/A  with corrections and completitions based on Haiku code.
2N/A*/
2N/A
2N/A#include <grub/err.h>
2N/A#include <grub/file.h>
2N/A#include <grub/mm.h>
2N/A#include <grub/misc.h>
2N/A#include <grub/disk.h>
2N/A#include <grub/dl.h>
2N/A#include <grub/types.h>
2N/A
2N/AGRUB_MOD_LICENSE ("GPLv3+");
2N/A
2N/A#ifdef MODE_AFS
2N/A#define BTREE_ALIGN 4
2N/A#define SUPERBLOCK  2
2N/A#else
2N/A#define BTREE_ALIGN 8
2N/A#define SUPERBLOCK  1
2N/A#endif
2N/A
2N/A#define grub_bfs_to_cpu16 grub_le_to_cpu16
2N/A#define grub_bfs_to_cpu32 grub_le_to_cpu32
2N/A#define grub_bfs_to_cpu64 grub_le_to_cpu64
2N/A
2N/A#ifdef MODE_AFS
2N/A#define grub_bfs_to_cpu_treehead grub_bfs_to_cpu32
2N/A#else
2N/A#define grub_bfs_to_cpu_treehead grub_bfs_to_cpu16
2N/A#endif
2N/A
2N/A#ifdef MODE_AFS
2N/A#define SUPER_BLOCK_MAGIC1 0x41465331
2N/A#else
2N/A#define SUPER_BLOCK_MAGIC1 0x42465331
2N/A#endif
2N/A#define SUPER_BLOCK_MAGIC2 0xdd121031
2N/A#define SUPER_BLOCK_MAGIC3 0x15b6830e
2N/A#define POINTER_INVALID 0xffffffffffffffffULL
2N/A
2N/A#define ATTR_TYPE      0160000
2N/A#define ATTR_REG       0100000
2N/A#define ATTR_DIR       0040000
2N/A#define ATTR_LNK       0120000
2N/A
2N/A#define DOUBLE_INDIRECT_SHIFT 2
2N/A
2N/A#define LOG_EXTENT_SIZE 3
2N/Astruct grub_bfs_extent
2N/A{
2N/A  grub_uint32_t ag;
2N/A  grub_uint16_t start;
2N/A  grub_uint16_t len;
2N/A} __attribute__ ((packed));
2N/A
2N/Astruct grub_bfs_superblock
2N/A{
2N/A  char label[32];
2N/A  grub_uint32_t magic1;
2N/A  grub_uint32_t unused1;
2N/A  grub_uint32_t bsize;
2N/A  grub_uint32_t log2_bsize;
2N/A  grub_uint8_t unused[20];
2N/A  grub_uint32_t magic2;
2N/A  grub_uint32_t unused2;
2N/A  grub_uint32_t log2_ag_size;
2N/A  grub_uint8_t unused3[32];
2N/A  grub_uint32_t magic3;
2N/A  struct grub_bfs_extent root_dir;
2N/A} __attribute__ ((packed));
2N/A
2N/Astruct grub_bfs_inode
2N/A{
2N/A  grub_uint8_t unused[20];
2N/A  grub_uint32_t mode;
2N/A  grub_uint32_t flags;
2N/A#ifdef MODE_AFS
2N/A  grub_uint8_t unused2[12];
2N/A#else
2N/A  grub_uint8_t unused2[8];
2N/A#endif
2N/A  grub_uint64_t mtime;
2N/A  grub_uint8_t unused3[8];
2N/A  struct grub_bfs_extent attr;
2N/A  grub_uint8_t unused4[12];
2N/A
2N/A  union
2N/A  {
2N/A    struct
2N/A    {
2N/A      struct grub_bfs_extent direct[12];
2N/A      grub_uint64_t max_direct_range;
2N/A      struct grub_bfs_extent indirect;
2N/A      grub_uint64_t max_indirect_range;
2N/A      struct grub_bfs_extent double_indirect;
2N/A      grub_uint64_t max_double_indirect_range;
2N/A      grub_uint64_t size;
2N/A      grub_uint32_t pad[4];
2N/A    } __attribute__ ((packed));
2N/A    char inplace_link[144];
2N/A  } __attribute__ ((packed));
2N/A  grub_uint8_t small_data[0];
2N/A} __attribute__ ((packed));
2N/A
2N/Aenum
2N/A{
2N/A  LONG_SYMLINK = 0x40
2N/A};
2N/A
2N/Astruct grub_bfs_small_data_element_header
2N/A{
2N/A  grub_uint32_t type;
2N/A  grub_uint16_t name_len;
2N/A  grub_uint16_t value_len;
2N/A} __attribute__ ((packed));
2N/A
2N/Astruct grub_bfs_btree_header
2N/A{
2N/A  grub_uint32_t magic;
2N/A#ifdef MODE_AFS
2N/A  grub_uint64_t root;
2N/A  grub_uint32_t level;
2N/A  grub_uint32_t node_size;
2N/A  grub_uint32_t unused;
2N/A#else
2N/A  grub_uint32_t node_size;
2N/A  grub_uint32_t level;
2N/A  grub_uint32_t unused;
2N/A  grub_uint64_t root;
2N/A#endif
2N/A  grub_uint32_t unused2[2];
2N/A} __attribute__ ((packed));
2N/A
2N/Astruct grub_bfs_btree_node
2N/A{
2N/A  grub_uint64_t unused;
2N/A  grub_uint64_t right;
2N/A  grub_uint64_t overflow;
2N/A#ifdef MODE_AFS
2N/A  grub_uint32_t count_keys;
2N/A  grub_uint32_t total_key_len;
2N/A#else
2N/A  grub_uint16_t count_keys;
2N/A  grub_uint16_t total_key_len;
2N/A#endif
2N/A} __attribute__ ((packed));
2N/A
2N/Astruct grub_bfs_data
2N/A{
2N/A  struct grub_bfs_superblock sb;
2N/A  struct grub_bfs_inode ino[0];
2N/A};
2N/A
2N/Astatic grub_err_t
2N/Aread_extent (grub_disk_t disk,
2N/A         const struct grub_bfs_superblock *sb,
2N/A         const struct grub_bfs_extent *in,
2N/A         grub_off_t off, grub_off_t byteoff, void *buf, grub_size_t len)
2N/A{
2N/A#ifdef MODE_AFS
2N/A  return grub_disk_read (disk, ((grub_bfs_to_cpu32 (in->ag)
2N/A                 << (grub_bfs_to_cpu32 (sb->log2_ag_size)
2N/A                     - GRUB_DISK_SECTOR_BITS))
2N/A                + ((grub_bfs_to_cpu16 (in->start) + off)
2N/A                   << (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A                       - GRUB_DISK_SECTOR_BITS))),
2N/A             byteoff, len, buf);
2N/A#else
2N/A  return grub_disk_read (disk, (((grub_bfs_to_cpu32 (in->ag)
2N/A                  << grub_bfs_to_cpu32 (sb->log2_ag_size))
2N/A                 + grub_bfs_to_cpu16 (in->start) + off)
2N/A                << (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A                    - GRUB_DISK_SECTOR_BITS)),
2N/A             byteoff, len, buf);
2N/A#endif
2N/A}
2N/A
2N/A#ifdef MODE_AFS
2N/A#define RANGE_SHIFT grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A#else
2N/A#define RANGE_SHIFT 0
2N/A#endif
2N/A
2N/Astatic grub_err_t
2N/Aread_bfs_file (grub_disk_t disk,
2N/A           const struct grub_bfs_superblock *sb,
2N/A           const struct grub_bfs_inode *ino,
2N/A           grub_off_t off, void *buf, grub_size_t len,
2N/A           void NESTED_FUNC_ATTR (*read_hook) (grub_disk_addr_t sector,
2N/A                           unsigned offset,
2N/A                           unsigned length))
2N/A{
2N/A  if (len == 0)
2N/A    return GRUB_ERR_NONE;
2N/A
2N/A  if (off + len > grub_bfs_to_cpu64 (ino->size))
2N/A    return grub_error (GRUB_ERR_OUT_OF_RANGE,
2N/A               "attempt to read past the end of file");
2N/A
2N/A  if (off < (grub_bfs_to_cpu64 (ino->max_direct_range) << RANGE_SHIFT))
2N/A    {
2N/A      unsigned i;
2N/A      grub_uint64_t pos = 0;
2N/A      for (i = 0; i < ARRAY_SIZE (ino->direct); i++)
2N/A    {
2N/A      grub_uint64_t newpos;
2N/A      newpos = pos + (grub_bfs_to_cpu16 (ino->direct[i].len)
2N/A              << grub_bfs_to_cpu32 (sb->log2_bsize));
2N/A      if (newpos > off)
2N/A        {
2N/A          grub_size_t read_size;
2N/A          grub_err_t err;
2N/A          read_size = newpos - off;
2N/A          if (read_size > len)
2N/A        read_size = len;
2N/A          disk->read_hook = read_hook;
2N/A          err = read_extent (disk, sb, &ino->direct[i], 0, off - pos,
2N/A                 buf, read_size);
2N/A          disk->read_hook = 0;
2N/A          if (err)
2N/A        return err;
2N/A          off += read_size;
2N/A          len -= read_size;
2N/A          buf = (char *) buf + read_size;
2N/A          if (len == 0)
2N/A        return GRUB_ERR_NONE;
2N/A        }
2N/A      pos = newpos;
2N/A    }
2N/A    }
2N/A
2N/A  if (off < (grub_bfs_to_cpu64 (ino->max_direct_range) << RANGE_SHIFT))
2N/A    return grub_error (GRUB_ERR_BAD_FS, "incorrect direct blocks");
2N/A
2N/A  if (off < (grub_bfs_to_cpu64 (ino->max_indirect_range) << RANGE_SHIFT))
2N/A    {
2N/A      unsigned i;
2N/A      struct grub_bfs_extent *entries;
2N/A      grub_size_t nentries;
2N/A      grub_err_t err;
2N/A      grub_uint64_t pos = (grub_bfs_to_cpu64 (ino->max_direct_range)
2N/A               << RANGE_SHIFT);
2N/A      nentries = (grub_bfs_to_cpu16 (ino->indirect.len)
2N/A          << (grub_bfs_to_cpu32 (sb->log2_bsize) - LOG_EXTENT_SIZE));
2N/A      entries = grub_malloc (nentries << LOG_EXTENT_SIZE);
2N/A      if (!entries)
2N/A    return grub_errno;
2N/A      err = read_extent (disk, sb, &ino->indirect, 0, 0,
2N/A             entries, nentries << LOG_EXTENT_SIZE);
2N/A      for (i = 0; i < nentries; i++)
2N/A    {
2N/A      grub_uint64_t newpos;
2N/A      newpos = pos + (grub_bfs_to_cpu16 (entries[i].len)
2N/A              << grub_bfs_to_cpu32 (sb->log2_bsize));
2N/A      if (newpos > off)
2N/A        {
2N/A          grub_size_t read_size;
2N/A          read_size = newpos - off;
2N/A          if (read_size > len)
2N/A        read_size = len;
2N/A          disk->read_hook = read_hook;
2N/A          err = read_extent (disk, sb, &entries[i], 0, off - pos,
2N/A                 buf, read_size);
2N/A          disk->read_hook = 0;
2N/A          if (err)
2N/A        {
2N/A          grub_free (entries);
2N/A          return err;
2N/A        }
2N/A          off += read_size;
2N/A          len -= read_size;
2N/A          buf = (char *) buf + read_size;
2N/A          if (len == 0)
2N/A        {
2N/A          grub_free (entries);
2N/A          return GRUB_ERR_NONE;
2N/A        }
2N/A        }
2N/A      pos = newpos;
2N/A    }
2N/A      grub_free (entries);
2N/A    }
2N/A
2N/A  if (off < (grub_bfs_to_cpu64 (ino->max_indirect_range) << RANGE_SHIFT))
2N/A    return grub_error (GRUB_ERR_BAD_FS, "incorrect indirect blocks");
2N/A
2N/A  {
2N/A    struct grub_bfs_extent *l1_entries, *l2_entries;
2N/A    grub_size_t nl1_entries, nl2_entries;
2N/A    grub_off_t last_l1n = ~0ULL;
2N/A    grub_err_t err;
2N/A    nl1_entries = (grub_bfs_to_cpu16 (ino->double_indirect.len)
2N/A           << (grub_bfs_to_cpu32 (sb->log2_bsize) - LOG_EXTENT_SIZE));
2N/A    l1_entries = grub_malloc (nl1_entries << LOG_EXTENT_SIZE);
2N/A    if (!l1_entries)
2N/A      return grub_errno;
2N/A    nl2_entries = 0;
2N/A    l2_entries = grub_malloc (1 << (DOUBLE_INDIRECT_SHIFT
2N/A                    + grub_bfs_to_cpu32 (sb->log2_bsize)));
2N/A    if (!l2_entries)
2N/A      {
2N/A    grub_free (l1_entries);
2N/A    return grub_errno;
2N/A      }
2N/A    err = read_extent (disk, sb, &ino->double_indirect, 0, 0,
2N/A               l1_entries, nl1_entries << LOG_EXTENT_SIZE);
2N/A    if (err)
2N/A      {
2N/A    grub_free (l1_entries);
2N/A    grub_free (l2_entries);
2N/A    return err;
2N/A      }
2N/A
2N/A    while (len > 0)
2N/A      {
2N/A    grub_off_t boff, l2n, l1n;
2N/A    grub_size_t read_size;
2N/A    grub_off_t double_indirect_offset;
2N/A    double_indirect_offset = off
2N/A      - grub_bfs_to_cpu64 (ino->max_indirect_range);
2N/A    boff = (double_indirect_offset
2N/A        & ((1 << (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A              + DOUBLE_INDIRECT_SHIFT)) - 1));
2N/A    l2n = ((double_indirect_offset >> (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A                       + DOUBLE_INDIRECT_SHIFT))
2N/A           & ((1 << (grub_bfs_to_cpu32 (sb->log2_bsize) - LOG_EXTENT_SIZE
2N/A             + DOUBLE_INDIRECT_SHIFT)) - 1));
2N/A    l1n =
2N/A      (double_indirect_offset >>
2N/A       (2 * grub_bfs_to_cpu32 (sb->log2_bsize) - LOG_EXTENT_SIZE +
2N/A        2 * DOUBLE_INDIRECT_SHIFT));
2N/A    if (l1n > nl1_entries)
2N/A      {
2N/A        grub_free (l1_entries);
2N/A        grub_free (l2_entries);
2N/A        return grub_error (GRUB_ERR_BAD_FS,
2N/A                   "incorrect double-indirect block");
2N/A      }
2N/A    if (l1n != last_l1n)
2N/A      {
2N/A        nl2_entries = (grub_bfs_to_cpu16 (l1_entries[l1n].len)
2N/A               << (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A                   - LOG_EXTENT_SIZE));
2N/A        if (nl2_entries > (1U << (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A                      - LOG_EXTENT_SIZE
2N/A                      + DOUBLE_INDIRECT_SHIFT)))
2N/A          nl2_entries = (1 << (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A                   - LOG_EXTENT_SIZE
2N/A                   + DOUBLE_INDIRECT_SHIFT));
2N/A        err = read_extent (disk, sb, &l1_entries[l1n], 0, 0,
2N/A                   l2_entries, nl2_entries << LOG_EXTENT_SIZE);
2N/A        if (err)
2N/A          {
2N/A        grub_free (l1_entries);
2N/A        grub_free (l2_entries);
2N/A        return err;
2N/A          }
2N/A        last_l1n = l1n;
2N/A      }
2N/A    if (l2n > nl2_entries)
2N/A      {
2N/A        grub_free (l1_entries);
2N/A        grub_free (l2_entries);
2N/A        return grub_error (GRUB_ERR_BAD_FS,
2N/A                   "incorrect double-indirect block");
2N/A      }
2N/A
2N/A    read_size = (1 << (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A               + DOUBLE_INDIRECT_SHIFT)) - boff;
2N/A    if (read_size > len)
2N/A      read_size = len;
2N/A    disk->read_hook = read_hook;
2N/A    err = read_extent (disk, sb, &l2_entries[l2n], 0, boff,
2N/A               buf, read_size);
2N/A    disk->read_hook = 0;
2N/A    if (err)
2N/A      {
2N/A        grub_free (l1_entries);
2N/A        grub_free (l2_entries);
2N/A        return err;
2N/A      }
2N/A    off += read_size;
2N/A    len -= read_size;
2N/A    buf = (char *) buf + read_size;
2N/A      }
2N/A    return GRUB_ERR_NONE;
2N/A  }
2N/A}
2N/A
2N/Astatic int
2N/Aiterate_in_b_tree (grub_disk_t disk,
2N/A           const struct grub_bfs_superblock *sb,
2N/A           const struct grub_bfs_inode *ino,
2N/A           int (*hook) (const char *name, grub_uint64_t value))
2N/A{
2N/A  struct grub_bfs_btree_header head;
2N/A  grub_err_t err;
2N/A  int level;
2N/A  grub_uint64_t node_off;
2N/A
2N/A  err = read_bfs_file (disk, sb, ino, 0, &head, sizeof (head), 0);
2N/A  if (err)
2N/A    return 0;
2N/A  node_off = grub_bfs_to_cpu64 (head.root);
2N/A
2N/A  level = grub_bfs_to_cpu32 (head.level) - 1;
2N/A  while (level--)
2N/A    {
2N/A      struct grub_bfs_btree_node node;
2N/A      grub_uint64_t key_value;
2N/A      err = read_bfs_file (disk, sb, ino, node_off, &node, sizeof (node), 0);
2N/A      if (err)
2N/A    return 0;
2N/A      err = read_bfs_file (disk, sb, ino, node_off
2N/A               + ALIGN_UP (sizeof (node) +
2N/A                       grub_bfs_to_cpu_treehead (node.
2N/A                                 total_key_len),
2N/A                       BTREE_ALIGN) +
2N/A               grub_bfs_to_cpu_treehead (node.count_keys) *
2N/A               sizeof (grub_uint16_t), &key_value,
2N/A               sizeof (grub_uint64_t), 0);
2N/A      if (err)
2N/A    return 0;
2N/A
2N/A      node_off = grub_bfs_to_cpu64 (key_value);
2N/A    }
2N/A
2N/A  while (1)
2N/A    {
2N/A      struct grub_bfs_btree_node node;
2N/A      err = read_bfs_file (disk, sb, ino, node_off, &node, sizeof (node), 0);
2N/A      if (err)
2N/A    return 0;
2N/A      {
2N/A    char key_data[grub_bfs_to_cpu_treehead (node.total_key_len) + 1];
2N/A    grub_uint16_t keylen_idx[grub_bfs_to_cpu_treehead (node.count_keys)];
2N/A    grub_uint64_t key_values[grub_bfs_to_cpu_treehead (node.count_keys)];
2N/A    unsigned i;
2N/A    grub_uint16_t start = 0, end = 0;
2N/A
2N/A    err =
2N/A      read_bfs_file (disk, sb, ino, node_off + sizeof (node), key_data,
2N/A             grub_bfs_to_cpu_treehead (node.total_key_len), 0);
2N/A    if (err)
2N/A      return 0;
2N/A    key_data[grub_bfs_to_cpu_treehead (node.total_key_len)] = 0;
2N/A    err = read_bfs_file (disk, sb, ino, node_off
2N/A                 + ALIGN_UP (sizeof (node) +
2N/A                     grub_bfs_to_cpu_treehead
2N/A                     (node.total_key_len), BTREE_ALIGN),
2N/A                 keylen_idx,
2N/A                 grub_bfs_to_cpu_treehead (node.count_keys) *
2N/A                 sizeof (grub_uint16_t), 0);
2N/A    if (err)
2N/A      return 0;
2N/A    err = read_bfs_file (disk, sb, ino, node_off
2N/A                 + ALIGN_UP (sizeof (node) +
2N/A                     grub_bfs_to_cpu_treehead
2N/A                     (node.total_key_len),
2N/A                     BTREE_ALIGN) +
2N/A                 grub_bfs_to_cpu_treehead (node.count_keys) *
2N/A                 sizeof (grub_uint16_t), key_values,
2N/A                 grub_bfs_to_cpu_treehead (node.count_keys) *
2N/A                 sizeof (grub_uint64_t), 0);
2N/A    if (err)
2N/A      return 0;
2N/A
2N/A    for (i = 0; i < grub_bfs_to_cpu_treehead (node.count_keys); i++)
2N/A      {
2N/A        char c;
2N/A        start = end;
2N/A        end = grub_bfs_to_cpu16 (keylen_idx[i]);
2N/A        if (grub_bfs_to_cpu_treehead (node.total_key_len) <= end)
2N/A          end = grub_bfs_to_cpu_treehead (node.total_key_len);
2N/A        c = key_data[end];
2N/A        key_data[end] = 0;
2N/A        if (hook (key_data + start, grub_bfs_to_cpu64 (key_values[i])))
2N/A          return 1;
2N/A        key_data[end] = c;
2N/A      }
2N/A    node_off = grub_bfs_to_cpu64 (node.right);
2N/A    if (node_off == POINTER_INVALID)
2N/A      return 0;
2N/A      }
2N/A    }
2N/A}
2N/A
2N/Astatic grub_err_t
2N/Afind_in_b_tree (grub_disk_t disk,
2N/A        const struct grub_bfs_superblock *sb,
2N/A        const struct grub_bfs_inode *ino, const char *name,
2N/A        grub_uint64_t * res)
2N/A{
2N/A  struct grub_bfs_btree_header head;
2N/A  grub_err_t err;
2N/A  int level;
2N/A  grub_uint64_t node_off;
2N/A
2N/A  err = read_bfs_file (disk, sb, ino, 0, &head, sizeof (head), 0);
2N/A  if (err)
2N/A    return err;
2N/A  node_off = grub_bfs_to_cpu64 (head.root);
2N/A
2N/A  level = grub_bfs_to_cpu32 (head.level) - 1;
2N/A  while (1)
2N/A    {
2N/A      struct grub_bfs_btree_node node;
2N/A      err = read_bfs_file (disk, sb, ino, node_off, &node, sizeof (node), 0);
2N/A      if (err)
2N/A    return err;
2N/A      if (node.count_keys == 0)
2N/A    return grub_error (GRUB_ERR_FILE_NOT_FOUND, "file `%s' not found",
2N/A               name);
2N/A      {
2N/A    char key_data[grub_bfs_to_cpu_treehead (node.total_key_len) + 1];
2N/A    grub_uint16_t keylen_idx[grub_bfs_to_cpu_treehead (node.count_keys)];
2N/A    grub_uint64_t key_values[grub_bfs_to_cpu_treehead (node.count_keys)];
2N/A    unsigned i;
2N/A    grub_uint16_t start = 0, end = 0;
2N/A    err =
2N/A      read_bfs_file (disk, sb, ino, node_off + sizeof (node), key_data,
2N/A             grub_bfs_to_cpu_treehead (node.total_key_len), 0);
2N/A    if (err)
2N/A      return err;
2N/A    key_data[grub_bfs_to_cpu_treehead (node.total_key_len)] = 0;
2N/A    err = read_bfs_file (disk, sb, ino, node_off
2N/A                 +
2N/A                 ALIGN_UP (sizeof (node) +
2N/A                       grub_bfs_to_cpu_treehead (node.
2N/A                                 total_key_len),
2N/A                       BTREE_ALIGN), keylen_idx,
2N/A                 grub_bfs_to_cpu_treehead (node.count_keys) *
2N/A                 sizeof (grub_uint16_t), 0);
2N/A    if (err)
2N/A      return err;
2N/A    err = read_bfs_file (disk, sb, ino, node_off
2N/A                 + ALIGN_UP (sizeof (node) +
2N/A                     grub_bfs_to_cpu_treehead
2N/A                     (node.total_key_len),
2N/A                     BTREE_ALIGN) +
2N/A                 grub_bfs_to_cpu_treehead (node.count_keys) *
2N/A                 sizeof (grub_uint16_t), key_values,
2N/A                 grub_bfs_to_cpu_treehead (node.count_keys) *
2N/A                 sizeof (grub_uint64_t), 0);
2N/A    if (err)
2N/A      return err;
2N/A
2N/A    for (i = 0; i < grub_bfs_to_cpu_treehead (node.count_keys); i++)
2N/A      {
2N/A        int cmp;
2N/A        char c;
2N/A        start = end;
2N/A        end = grub_bfs_to_cpu16 (keylen_idx[i]);
2N/A        if (grub_bfs_to_cpu_treehead (node.total_key_len) <= end)
2N/A          end = grub_bfs_to_cpu_treehead (node.total_key_len);
2N/A        c = key_data[end];
2N/A        key_data[end] = 0;
2N/A        cmp = grub_strcmp (key_data + start, name);
2N/A        key_data[end] = c;
2N/A        if (cmp == 0 && level == 0)
2N/A          {
2N/A        *res = grub_bfs_to_cpu64 (key_values[i]);
2N/A        return GRUB_ERR_NONE;
2N/A          }
2N/A        if (cmp >= 0 && level != 0)
2N/A          {
2N/A        node_off = grub_bfs_to_cpu64 (key_values[i]);
2N/A        break;
2N/A          }
2N/A      }
2N/A    if (i < grub_bfs_to_cpu_treehead (node.count_keys))
2N/A      {
2N/A        level--;
2N/A        continue;
2N/A      }
2N/A    if (node.overflow != POINTER_INVALID)
2N/A      {
2N/A        node_off = grub_bfs_to_cpu64 (node.overflow);
2N/A        /* This level-- isn't specified but is needed.  */
2N/A        level--;
2N/A        continue;
2N/A      }
2N/A    return grub_error (GRUB_ERR_FILE_NOT_FOUND, "file `%s' not found",
2N/A               name);
2N/A      }
2N/A    }
2N/A}
2N/A
2N/Astatic grub_err_t
2N/Ahop_level (grub_disk_t disk,
2N/A       const struct grub_bfs_superblock *sb,
2N/A       struct grub_bfs_inode *ino, const char *name)
2N/A{
2N/A  grub_err_t err;
2N/A  grub_uint64_t res;
2N/A
2N/A  if (((grub_bfs_to_cpu32 (ino->mode) & ATTR_TYPE) != ATTR_DIR))
2N/A    return grub_error (GRUB_ERR_BAD_FILE_TYPE, "not a directory");
2N/A
2N/A  err = find_in_b_tree (disk, sb, ino, name, &res);
2N/A  if (err)
2N/A    return err;
2N/A
2N/A  return grub_disk_read (disk, res
2N/A             << (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A                 - GRUB_DISK_SECTOR_BITS), 0,
2N/A             grub_bfs_to_cpu32 (sb->bsize), (char *) ino);
2N/A}
2N/A
2N/Astatic grub_err_t
2N/Afind_file (const char *path, grub_disk_t disk,
2N/A       const struct grub_bfs_superblock *sb, struct grub_bfs_inode *ino)
2N/A{
2N/A  char *ptr, *ptr2;
2N/A  char *alloc = NULL;
2N/A  grub_err_t err;
2N/A  union
2N/A  {
2N/A    struct grub_bfs_inode ino;
2N/A    grub_uint8_t raw[grub_bfs_to_cpu32 (sb->bsize)];
2N/A  } old_ino;
2N/A  unsigned symlinks_max = 32;
2N/A
2N/A  err = read_extent (disk, sb, &sb->root_dir, 0, 0, ino,
2N/A             grub_bfs_to_cpu32 (sb->bsize));
2N/A  if (err)
2N/A    return err;
2N/A
2N/A  ptr = (char *) path;
2N/A  while (1)
2N/A    {
2N/A      while (*ptr == '/')
2N/A    ptr++;
2N/A      if (*ptr == 0)
2N/A    {
2N/A      grub_free (alloc);
2N/A      return GRUB_ERR_NONE;
2N/A    }
2N/A      ptr2 = grub_strchr (ptr, '/');
2N/A      grub_memcpy (&old_ino, ino, grub_bfs_to_cpu32 (sb->bsize));
2N/A      if (ptr2)
2N/A    {
2N/A      char component[ptr2 - ptr + 1];
2N/A      grub_memcpy (component, ptr, ptr2 - ptr);
2N/A      component[ptr2 - ptr] = 0;
2N/A      err = hop_level (disk, sb, ino, component);
2N/A    }
2N/A      else
2N/A    err = hop_level (disk, sb, ino, ptr);
2N/A      if (err)
2N/A    return err;
2N/A
2N/A      if (((grub_bfs_to_cpu32 (ino->mode) & ATTR_TYPE) == ATTR_LNK))
2N/A    {
2N/A      char *old_alloc = alloc;
2N/A      if (--symlinks_max == 0)
2N/A        {
2N/A          grub_free (alloc);
2N/A          return grub_error (GRUB_ERR_SYMLINK_LOOP,
2N/A                 "too deep nesting of symlinks");
2N/A        }
2N/A
2N/A#ifndef MODE_AFS
2N/A      if (grub_bfs_to_cpu32 (ino->flags) & LONG_SYMLINK)
2N/A#endif
2N/A        {
2N/A          grub_size_t symsize = grub_bfs_to_cpu64 (ino->size);
2N/A          alloc = grub_malloc ((ptr2 ? grub_strlen (ptr2) : 0)
2N/A                   + symsize + 1);
2N/A          if (!alloc)
2N/A        {
2N/A          grub_free (alloc);
2N/A          return grub_errno;
2N/A        }
2N/A          grub_free (old_alloc);
2N/A          err = read_bfs_file (disk, sb, ino, 0, alloc, symsize, 0);
2N/A          if (err)
2N/A        {
2N/A          grub_free (alloc);
2N/A          return err;
2N/A        }
2N/A          alloc[symsize] = 0;
2N/A        }
2N/A#ifndef MODE_AFS
2N/A      else
2N/A        {
2N/A          alloc = grub_malloc ((ptr2 ? grub_strlen (ptr2) : 0)
2N/A                   + sizeof (ino->inplace_link) + 1);
2N/A          if (!alloc)
2N/A        {
2N/A          grub_free (alloc);
2N/A          return grub_errno;
2N/A        }
2N/A          grub_free (old_alloc);
2N/A          grub_memcpy (alloc, ino->inplace_link,
2N/A               sizeof (ino->inplace_link));
2N/A          alloc[sizeof (ino->inplace_link)] = 0;
2N/A        }
2N/A#endif
2N/A      if (alloc[0] == '/')
2N/A        {
2N/A          err = read_extent (disk, sb, &sb->root_dir, 0, 0, ino,
2N/A                 grub_bfs_to_cpu32 (sb->bsize));
2N/A          if (err)
2N/A        {
2N/A          grub_free (alloc);
2N/A          return err;
2N/A        }
2N/A        }
2N/A      else
2N/A        grub_memcpy (ino, &old_ino, grub_bfs_to_cpu32 (sb->bsize));
2N/A      ptr = alloc + grub_strlen (alloc);
2N/A      if (ptr2)
2N/A        ptr = grub_stpcpy (ptr, ptr2);
2N/A      *ptr = 0;
2N/A      ptr = ptr2 = alloc;
2N/A      continue;
2N/A    }
2N/A
2N/A      if (!ptr2)
2N/A    {
2N/A      grub_free (alloc);
2N/A      return GRUB_ERR_NONE;
2N/A    }
2N/A      ptr = ptr2 + 1;
2N/A    }
2N/A}
2N/A
2N/Astatic grub_err_t
2N/Amount (grub_disk_t disk, struct grub_bfs_superblock *sb)
2N/A{
2N/A  grub_err_t err;
2N/A  err = grub_disk_read (disk, SUPERBLOCK, 0, sizeof (*sb), sb);
2N/A  if (err == GRUB_ERR_OUT_OF_RANGE)
2N/A    return grub_error (GRUB_ERR_BAD_FS,
2N/A#ifdef MODE_AFS
2N/A               "not an AFS filesystem"
2N/A#else
2N/A               "not a BFS filesystem"
2N/A#endif
2N/A               );
2N/A  if (err)
2N/A    return err;
2N/A  if (grub_bfs_to_cpu32 (sb->magic1) != SUPER_BLOCK_MAGIC1
2N/A      || grub_bfs_to_cpu32 (sb->magic2) != SUPER_BLOCK_MAGIC2
2N/A      || grub_bfs_to_cpu32 (sb->magic3) != SUPER_BLOCK_MAGIC3
2N/A      || (grub_bfs_to_cpu32 (sb->bsize)
2N/A      != (1U << grub_bfs_to_cpu32 (sb->log2_bsize))))
2N/A    return grub_error (GRUB_ERR_BAD_FS,
2N/A#ifdef MODE_AFS
2N/A               "not an AFS filesystem"
2N/A#else
2N/A               "not a BFS filesystem"
2N/A#endif
2N/A               );
2N/A  return GRUB_ERR_NONE;
2N/A}
2N/A
2N/Astatic grub_err_t
2N/Agrub_bfs_dir (grub_device_t device, const char *path,
2N/A          int (*hook_in) (const char *filename,
2N/A                  const struct grub_dirhook_info * info))
2N/A{
2N/A  struct grub_bfs_superblock sb;
2N/A  grub_err_t err;
2N/A  auto int hook (const char *name, grub_uint64_t value);
2N/A
2N/A  int hook (const char *name, grub_uint64_t value)
2N/A  {
2N/A    grub_err_t err2;
2N/A    union
2N/A    {
2N/A      struct grub_bfs_inode ino;
2N/A      grub_uint8_t raw[grub_bfs_to_cpu32 (sb.bsize)];
2N/A    } ino;
2N/A    struct grub_dirhook_info info;
2N/A
2N/A    err2 = grub_disk_read (device->disk, value
2N/A               << (grub_bfs_to_cpu32 (sb.log2_bsize)
2N/A                   - GRUB_DISK_SECTOR_BITS), 0,
2N/A               grub_bfs_to_cpu32 (sb.bsize), (char *) ino.raw);
2N/A    if (err2)
2N/A      {
2N/A    grub_print_error ();
2N/A    return 0;
2N/A      }
2N/A
2N/A    info.mtimeset = 1;
2N/A#ifdef MODE_AFS
2N/A    info.mtime =
2N/A      grub_divmod64 (grub_bfs_to_cpu64 (ino.ino.mtime), 1000000, 0);
2N/A#else
2N/A    info.mtime = grub_bfs_to_cpu64 (ino.ino.mtime) >> 16;
2N/A#endif
2N/A    info.dir = ((grub_bfs_to_cpu32 (ino.ino.mode) & ATTR_TYPE) == ATTR_DIR);
2N/A    return hook_in (name, &info);
2N/A  }
2N/A  err = mount (device->disk, &sb);
2N/A  if (err)
2N/A    return err;
2N/A
2N/A  {
2N/A    union
2N/A    {
2N/A      struct grub_bfs_inode ino;
2N/A      grub_uint8_t raw[grub_bfs_to_cpu32 (sb.bsize)];
2N/A    } ino;
2N/A    err = find_file (path, device->disk, &sb, &ino.ino);
2N/A    if (err)
2N/A      return err;
2N/A    if (((grub_bfs_to_cpu32 (ino.ino.mode) & ATTR_TYPE) != ATTR_DIR))
2N/A      return grub_error (GRUB_ERR_BAD_FILE_TYPE, "not a directory");
2N/A    iterate_in_b_tree (device->disk, &sb, &ino.ino, hook);
2N/A  }
2N/A
2N/A  return grub_errno;
2N/A}
2N/A
2N/Astatic grub_err_t
2N/Agrub_bfs_open (struct grub_file *file, const char *name)
2N/A{
2N/A  struct grub_bfs_superblock sb;
2N/A  grub_err_t err;
2N/A
2N/A  err = mount (file->device->disk, &sb);
2N/A  if (err)
2N/A    return err;
2N/A
2N/A  {
2N/A    union
2N/A    {
2N/A      struct grub_bfs_inode ino;
2N/A      grub_uint8_t raw[grub_bfs_to_cpu32 (sb.bsize)];
2N/A    } ino;
2N/A    struct grub_bfs_data *data;
2N/A    err = find_file (name, file->device->disk, &sb, &ino.ino);
2N/A    if (err)
2N/A      return err;
2N/A    if (((grub_bfs_to_cpu32 (ino.ino.mode) & ATTR_TYPE) != ATTR_REG))
2N/A      return grub_error (GRUB_ERR_BAD_FILE_TYPE, "not a regular file");
2N/A
2N/A    data = grub_zalloc (sizeof (struct grub_bfs_data)
2N/A            + grub_bfs_to_cpu32 (sb.bsize));
2N/A    if (!data)
2N/A      return grub_errno;
2N/A    data->sb = sb;
2N/A    grub_memcpy (&data->ino, &ino, grub_bfs_to_cpu32 (sb.bsize));
2N/A    file->data = data;
2N/A    file->size = grub_bfs_to_cpu64 (ino.ino.size);
2N/A  }
2N/A
2N/A  return GRUB_ERR_NONE;
2N/A}
2N/A
2N/Astatic grub_err_t
2N/Agrub_bfs_close (grub_file_t file)
2N/A{
2N/A  grub_free (file->data);
2N/A
2N/A  return GRUB_ERR_NONE;
2N/A}
2N/A
2N/Astatic grub_ssize_t
2N/Agrub_bfs_read (grub_file_t file, char *buf, grub_size_t len)
2N/A{
2N/A  grub_err_t err;
2N/A  struct grub_bfs_data *data = file->data;
2N/A
2N/A  err = read_bfs_file (file->device->disk, &data->sb,
2N/A               data->ino, file->offset, buf, len, file->read_hook);
2N/A  if (err)
2N/A    return -1;
2N/A  return len;
2N/A}
2N/A
2N/Astatic grub_err_t
2N/Agrub_bfs_label (grub_device_t device, char **label)
2N/A{
2N/A  struct grub_bfs_superblock sb;
2N/A  grub_err_t err;
2N/A
2N/A  *label = 0;
2N/A
2N/A  err = mount (device->disk, &sb);
2N/A  if (err)
2N/A    return err;
2N/A
2N/A  *label = grub_strndup (sb.label, sizeof (sb.label));
2N/A  return GRUB_ERR_NONE;
2N/A}
2N/A
2N/A#ifndef MODE_AFS
2N/Astatic grub_ssize_t
2N/Aread_bfs_attr (grub_disk_t disk,
2N/A           const struct grub_bfs_superblock *sb,
2N/A           const struct grub_bfs_inode *ino,
2N/A           const char *name, void *buf, grub_size_t len)
2N/A{
2N/A  grub_uint8_t *ptr = (grub_uint8_t *) ino->small_data;
2N/A  grub_uint8_t *end = ((grub_uint8_t *) ino + grub_bfs_to_cpu32 (sb->bsize));
2N/A
2N/A  while (ptr + sizeof (struct grub_bfs_small_data_element_header) < end)
2N/A    {
2N/A      struct grub_bfs_small_data_element_header *el;
2N/A      char *el_name;
2N/A      grub_uint8_t *data;
2N/A      el = (struct grub_bfs_small_data_element_header *) ptr;
2N/A      if (el->name_len == 0)
2N/A    break;
2N/A      el_name = (char *) (el + 1);
2N/A      data = (grub_uint8_t *) el_name + grub_bfs_to_cpu16 (el->name_len) + 3;
2N/A      ptr = data + grub_bfs_to_cpu16 (el->value_len) + 1;
2N/A      if (grub_memcmp (name, el_name, grub_bfs_to_cpu16 (el->name_len)) == 0
2N/A      && name[el->name_len] == 0)
2N/A    {
2N/A      grub_size_t copy;
2N/A      copy = len;
2N/A      if (grub_bfs_to_cpu16 (el->value_len) > copy)
2N/A        copy = grub_bfs_to_cpu16 (el->value_len);
2N/A      grub_memcpy (buf, data, copy);
2N/A      return copy;
2N/A    }
2N/A    }
2N/A
2N/A  if (ino->attr.len != 0)
2N/A    {
2N/A      union
2N/A      {
2N/A    struct grub_bfs_inode ino;
2N/A    grub_uint8_t raw[grub_bfs_to_cpu32 (sb->bsize)];
2N/A      } ino2;
2N/A      grub_size_t read;
2N/A      grub_err_t err;
2N/A      grub_uint64_t res;
2N/A
2N/A      err = read_extent (disk, sb, &ino->attr, 0, 0, ino2.raw,
2N/A             grub_bfs_to_cpu32 (sb->bsize));
2N/A      if (err)
2N/A    return -1;
2N/A
2N/A      err = find_in_b_tree (disk, sb, &ino2.ino, name, &res);
2N/A      if (err)
2N/A    return -1;
2N/A      grub_disk_read (disk, res
2N/A              << (grub_bfs_to_cpu32 (sb->log2_bsize)
2N/A              - GRUB_DISK_SECTOR_BITS), 0,
2N/A              grub_bfs_to_cpu32 (sb->bsize), (char *) &ino2);
2N/A      read = grub_bfs_to_cpu64 (ino2.ino.size);
2N/A      if (read > len)
2N/A    read = len;
2N/A
2N/A      err = read_bfs_file (disk, sb, &ino2.ino, 0, buf, read, 0);
2N/A      if (err)
2N/A    return -1;
2N/A      return read;
2N/A    }
2N/A  return -1;
2N/A}
2N/A
2N/Astatic grub_err_t
2N/Agrub_bfs_uuid (grub_device_t device, char **uuid)
2N/A{
2N/A  struct grub_bfs_superblock sb;
2N/A  grub_err_t err;
2N/A
2N/A  *uuid = 0;
2N/A
2N/A  err = mount (device->disk, &sb);
2N/A  if (err)
2N/A    return err;
2N/A
2N/A  {
2N/A    union
2N/A    {
2N/A      struct grub_bfs_inode ino;
2N/A      grub_uint8_t raw[grub_bfs_to_cpu32 (sb.bsize)];
2N/A    } ino;
2N/A    grub_uint64_t vid;
2N/A
2N/A    err = read_extent (device->disk, &sb, &sb.root_dir, 0, 0,
2N/A               &ino, grub_bfs_to_cpu32 (sb.bsize));
2N/A    if (err)
2N/A      return err;
2N/A    if (read_bfs_attr (device->disk, &sb, &ino.ino, "be:volume_id",
2N/A               &vid, sizeof (vid)) == sizeof (vid))
2N/A      *uuid =
2N/A    grub_xasprintf ("%016" PRIxGRUB_UINT64_T, grub_bfs_to_cpu64 (vid));
2N/A  }
2N/A  return GRUB_ERR_NONE;
2N/A}
2N/A#endif
2N/A
2N/Astatic struct grub_fs grub_bfs_fs = {
2N/A#ifdef MODE_AFS
2N/A  .name = "afs",
2N/A#else
2N/A  .name = "bfs",
2N/A#endif
2N/A  .dir = grub_bfs_dir,
2N/A  .open = grub_bfs_open,
2N/A  .read = grub_bfs_read,
2N/A  .close = grub_bfs_close,
2N/A  .label = grub_bfs_label,
2N/A#ifndef MODE_AFS
2N/A  .uuid = grub_bfs_uuid,
2N/A#endif
2N/A#ifdef GRUB_UTIL
2N/A  .reserved_first_sector = 1,
2N/A#endif
2N/A};
2N/A
2N/A#ifdef MODE_AFS
2N/AGRUB_MOD_INIT (afs)
2N/A#else
2N/AGRUB_MOD_INIT (bfs)
2N/A#endif
2N/A{
2N/A  COMPILE_TIME_ASSERT (1 << LOG_EXTENT_SIZE ==
2N/A               sizeof (struct grub_bfs_extent));
2N/A  grub_fs_register (&grub_bfs_fs);
2N/A}
2N/A
2N/A#ifdef MODE_AFS
2N/AGRUB_MOD_FINI (afs)
2N/A#else
2N/AGRUB_MOD_FINI (bfs)
2N/A#endif
2N/A{
2N/A  grub_fs_unregister (&grub_bfs_fs);
2N/A}