ra8_fs_fat_exfat_check.c

Go to the documentation of this file.

 
#include <stddef.h>
#include <stdint.h>
 
#include "ra8_attributes.h"
#include "ra8_fs.h"
#include "ra8_fs_check.h"
#include "ra8_fs_fat_check_internal.h"
#include "ra8_fs_fat_internal.h"

typedef enum : uint32_t {
  k_exchk_bits_per_byte = 8U, 
  k_exchk_bit_mask      = 7U, 
  k_exchk_byte_shift    = 3U, 
} ra8_fs_exfat_check_const_t;

typedef struct {
  exfat_dir_t* items;     
  uint32_t     top;       
  uint8_t      truncated; 
} exfat_dir_stack_t;

RA8_INTERNAL
static uint32_t internal_exchk_popcount8(uint8_t b)
{
  uint32_t n = 0U;
  for (uint32_t i = 0U; i < (uint32_t)k_exchk_bits_per_byte; i++) {
    n += ((uint32_t)b >> i) & 1U;
  }
  return n;
}
 
/* =============================================================================
 * Marking referenced clusters
 * =============================================================================
 */

RA8_INTERNAL
static void internal_exchk_mark_run(ra8_fs_check_ctx_t* ctx, uint32_t first, uint64_t nclus)
{
  if (!priv_check_in_range(ctx, first)) {
    (void)priv_check_visit(ctx, first, k_ra8_fs_check_fault_bad_dir_entry);
    return;
  }
  uint32_t       n         = (uint32_t)nclus;
  const uint32_t available = ctx->rep->clusters_total - (first - (uint32_t)k_cluster_first_data);
  if (nclus > (uint64_t)available) {
    n = available;
    ctx->rep->entries_bad++;
    priv_check_fault(ctx, k_ra8_fs_check_fault_bad_dir_entry, first + n, 0U, 0U);
  }
  for (uint32_t i = 0U; i < n; i++) {
    const uint32_t c = first + i;
    if (priv_check_visit(ctx, c, k_ra8_fs_check_fault_bad_dir_entry)) {
      return;
    }
  }
}
 
RA8_TEST_HELPER
void ra8_fs_check_test_exfat_mark_run(ra8_fs_check_ctx_t* ctx, uint32_t first, uint64_t nclus)
{
  internal_exchk_mark_run(ctx, first, nclus);
}

RA8_INTERNAL
static ra8_err_t internal_exchk_mark_fatchain(ra8_fs_check_ctx_t* ctx, uint32_t first)
{
  uint32_t c = first;
  for (uint32_t hop = 0U; hop < ctx->rep->clusters_total; hop++) {
    if (priv_check_visit(ctx, c, k_ra8_fs_check_fault_bad_chain)) {
      return k_ra8_ok;
    }
    uint32_t        v   = 0U;
    const ra8_err_t err = priv_fat_get(ctx->m, c, &v);
    if (err != k_ra8_ok) {
      return err;
    }
    if (priv_is_eoc(ctx->m, v) != 0U) {
      return k_ra8_ok;
    }
    if (!priv_check_in_range(ctx, v)) {
      priv_check_fault(ctx, k_ra8_fs_check_fault_bad_chain, c, 0U, 0U);
      return k_ra8_ok;
    }
    c = v;
  }
  (void)priv_check_visit(ctx, c, k_ra8_fs_check_fault_bad_chain);
  return k_ra8_ok;
}
 
RA8_TEST_HELPER
ra8_err_t ra8_fs_check_test_exfat_mark_fatchain(ra8_fs_check_ctx_t* ctx, uint32_t first)
{
  return internal_exchk_mark_fatchain(ctx, first);
}

RA8_INTERNAL
static ra8_err_t internal_exchk_mark_dir_alloc(ra8_fs_check_ctx_t* ctx, const exfat_dir_t* dir)
{
  uint32_t c = dir->cluster;
  for (uint32_t hop = 0U; hop < ctx->rep->clusters_total; hop++) {
    if (priv_check_visit(ctx, c, k_ra8_fs_check_fault_bad_dir_entry)) {
      return k_ra8_ok;
    }
    uint32_t        next = 0U;
    const ra8_err_t e    = priv_exfat_step_cluster(ctx->m, c, dir->contig_end, &next);
    if (e == k_ra8_err_not_found) {
      return k_ra8_ok; /* the run ended */
    }
    if (e != k_ra8_ok) {
      return e;
    }
    c = next;
  }
  (void)priv_check_visit(ctx, c, k_ra8_fs_check_fault_bad_dir_entry);
  return k_ra8_ok;
}
 
RA8_TEST_HELPER
ra8_err_t ra8_fs_check_test_exfat_mark_dir_alloc(ra8_fs_check_ctx_t* ctx, uint32_t first)
{
  const exfat_dir_t dir = {.cluster = first};
  return internal_exchk_mark_dir_alloc(ctx, &dir);
}

RA8_INTERNAL
static void internal_exchk_system_run(ra8_fs_check_ctx_t* ctx, const uint8_t* e)
{
  const uint32_t first  = priv_rd32(&e[k_exfat_strm_off_clus]);
  const uint64_t bytes  = priv_rd64(&e[k_exfat_strm_off_dlen]);
  const uint32_t cbytes = priv_cluster_bytes(ctx->m);
  const uint64_t nclus  = (bytes / cbytes) + ((bytes % cbytes) != 0U ? 1U : 0U);
  if (first == 0U) {
    return;
  }
  internal_exchk_mark_run(ctx, first, nclus);
}
 
/* =============================================================================
 * Entry-set verification (SetChecksum + NameHash)
 * =============================================================================
 */

RA8_INTERNAL
static void internal_exchk_extract_name(const uint8_t* set, uint32_t nlen, uint16_t* units)
{
  for (uint32_t i = 0U; i < nlen; i++) {
    const uint32_t ent = 2U + (i / (uint32_t)k_exfat_name_per_entry);
    const uint32_t col = i % (uint32_t)k_exfat_name_per_entry;
    const uint32_t off =
      (ent * (uint32_t)k_exfat_entry_bytes) + (uint32_t)k_exfat_name_off + (col * 2U);
    units[i] = priv_rd16(&set[off]);
  }
}

RA8_INTERNAL
static void internal_exchk_verify_set(ra8_fs_check_ctx_t* ctx,
                                      const uint8_t*      set,
                                      uint32_t            count,
                                      uint64_t            lba,
                                      uint32_t            off)
{
  const uint16_t stored_cs = priv_rd16(&set[k_exfat_off_file_csum]);
  const uint16_t calc_cs   = priv_exfat_set_checksum(set, count * (uint32_t)k_exfat_entry_bytes);
  if (stored_cs != calc_cs) {
    ctx->rep->entries_bad++;
    priv_check_fault(ctx, k_ra8_fs_check_fault_bad_set_checksum, 0U, lba, off);
  }
  const uint8_t* strm = &set[k_exfat_entry_bytes];
  uint32_t       nlen = (uint32_t)strm[k_exfat_strm_off_nlen];
  if (nlen > (uint32_t)k_exfat_name_cap) {
    nlen = (uint32_t)k_exfat_name_cap;
  }
  uint16_t units[k_exfat_name_cap] = {};
  internal_exchk_extract_name(set, nlen, units);
  const uint16_t stored_hash = priv_rd16(&strm[k_exfat_off_strm_hash]);
  const uint16_t calc_hash   = priv_exfat_name_hash(units, nlen);
  if (stored_hash != calc_hash) {
    ctx->rep->entries_bad++;
    priv_check_fault(ctx, k_ra8_fs_check_fault_bad_name_hash, 0U, lba, off);
  }
}
 
/* =============================================================================
 * Directory-tree walk
 * =============================================================================
 */

RA8_INTERNAL
static void
internal_exchk_push(ra8_fs_check_ctx_t* ctx, exfat_dir_stack_t* stack, const exfat_dir_t* dir)
{
  if (stack->top >= (uint32_t)k_ra8_fs_check_max_dirs) {
    if (stack->truncated == 0U) {
      stack->truncated = 1U;
      priv_check_fault(ctx, k_ra8_fs_check_fault_scan_truncated, dir->cluster, 0U, 0U);
    }
    return;
  }
  stack->items[stack->top] = *dir;
  stack->top++;
}
 
/* ra8_fs_check_test_exfat_push_overflow(): see header for the test-only contract. */
RA8_TEST_HELPER
void ra8_fs_check_test_exfat_push_overflow(ra8_fs_check_ctx_t* ctx,
                                           uint32_t            cluster,
                                           bool                already_truncated)
{
  exfat_dir_stack_t stack = {
    .items     = nullptr,
    .top       = (uint32_t)k_ra8_fs_check_max_dirs,
    .truncated = already_truncated ? 1U : 0U,
  };
  const exfat_dir_t dir = {.cluster = cluster};
  internal_exchk_push(ctx, &stack, &dir);
}

RA8_INTERNAL
static ra8_err_t internal_exchk_set_clusters(ra8_fs_check_ctx_t* ctx,
                                             const uint8_t*      set,
                                             const uint8_t*      file,
                                             exfat_dir_stack_t*  stack,
                                             uint64_t            lba,
                                             uint32_t            off)
{
  const uint8_t* strm  = &set[k_exfat_entry_bytes];
  const uint32_t first = priv_rd32(&strm[k_exfat_strm_off_clus]);
  const uint64_t dlen  = priv_rd64(&strm[k_exfat_strm_off_dlen]);
  const uint8_t  is_dir =
    ((file[k_exfat_off_file_attr] & (uint8_t)k_exfat_attr_directory) != 0U) ? 1U : 0U;
  if (first == 0U) {
    if (is_dir == 0U) {
      ctx->rep->files_visited++;
    }
    return k_ra8_ok;
  }
  if (!priv_check_in_range(ctx, first)) {
    ctx->rep->entries_bad++;
    priv_check_fault(ctx, k_ra8_fs_check_fault_bad_dir_entry, first, lba, off);
    return k_ra8_ok;
  }
  if (is_dir != 0U) {
    exfat_dir_t sub = {};
    priv_exfat_dir_from_set(ctx->m, strm, &sub);
    internal_exchk_push(ctx, stack, &sub);
    return k_ra8_ok;
  }
  ctx->rep->files_visited++;
  const uint32_t cbytes = priv_cluster_bytes(ctx->m);
  const uint64_t nclus  = (dlen == 0U) ? 1U : ((dlen / cbytes) + ((dlen % cbytes) != 0U ? 1U : 0U));
  if ((strm[k_exfat_strm_off_flags] & (uint8_t)k_exfat_secflag_no_fat) != 0U) {
    internal_exchk_mark_run(ctx, first, nclus);
    return k_ra8_ok;
  }
  return internal_exchk_mark_fatchain(ctx, first);
}

RA8_INTERNAL
static ra8_err_t internal_exchk_set(ra8_fs_check_ctx_t* ctx,
                                    exfat_cursor_t*     cur,
                                    const uint8_t*      file,
                                    exfat_dir_stack_t*  stack)
{
  const uint32_t count = 1U + (uint32_t)file[k_exfat_off_file_secnt];
  const uint32_t bic   = (cur->entry_in_cluster - 1U) * (uint32_t)k_exfat_entry_bytes;
  const uint64_t lba   = priv_cluster_to_lba(ctx->m, cur->cluster) + (bic / priv_bps(ctx->m));
  const uint32_t off   = bic % priv_bps(ctx->m);
  if ((count < 2U) || (count > (uint32_t)k_exfat_set_max_entries)) {
    ctx->rep->entries_bad++;
    priv_check_fault(ctx, k_ra8_fs_check_fault_bad_dir_entry, 0U, lba, off);
    return k_ra8_ok;
  }
  uint8_t set[(uint32_t)k_exfat_set_max_entries * (uint32_t)k_exfat_entry_bytes] = {};
  priv_byte_copy(set, file, (uint32_t)k_exfat_entry_bytes);
  for (uint32_t k = 1U; k < count; k++) {
    const ra8_err_t e =
      priv_exfat_next_entry(ctx->m, cur, &set[(size_t)k * (size_t)k_exfat_entry_bytes]);
    if (e == k_ra8_err_not_found) {
      ctx->rep->entries_bad++;
      priv_check_fault(ctx, k_ra8_fs_check_fault_bad_dir_entry, 0U, lba, off);
      return k_ra8_ok;
    }
    if (e != k_ra8_ok) {
      return e;
    }
  }
  internal_exchk_verify_set(ctx, set, count, lba, off);
  return internal_exchk_set_clusters(ctx, set, file, stack, lba, off);
}

RA8_INTERNAL
static ra8_err_t internal_exchk_scan_dir_file_entry(ra8_fs_check_ctx_t* ctx,
                                                    exfat_cursor_t*     cur,
                                                    const uint8_t*      e,
                                                    exfat_dir_stack_t*  stack,
                                                    uint32_t            dir_cluster,
                                                    bool*               out_stop)
{
  const uint32_t count     = 1U + (uint32_t)e[k_exfat_off_file_secnt];
  const uint32_t remaining = (uint32_t)k_exfat_scan_limit - cur->scanned;
  if (count <= (uint32_t)k_exfat_set_max_entries) {
    if (count > 1U) {
      if ((count - 1U) > remaining) {
        priv_check_fault(ctx, k_ra8_fs_check_fault_scan_truncated, dir_cluster, 0U, 0U);
        *out_stop = true;
        return k_ra8_ok;
      }
    }
  }
  const ra8_err_t se = internal_exchk_set(ctx, cur, e, stack);
  *out_stop          = (se != k_ra8_ok);
  return se;
}

RA8_INTERNAL
static ra8_err_t internal_exchk_scan_dir_terminal(ra8_fs_check_ctx_t* ctx,
                                                  exfat_cursor_t*     cur,
                                                  const exfat_dir_t*  dir)
{
  uint8_t         terminal[k_exfat_entry_bytes] = {};
  const ra8_err_t probe                         = priv_exfat_next_entry(ctx->m, cur, terminal);
  if (probe == k_ra8_err_not_found) {
    return k_ra8_ok;
  }
  if (probe != k_ra8_ok) {
    return probe;
  }
  if (terminal[0] == (uint8_t)k_exfat_entry_eod) {
    return k_ra8_ok;
  }
  priv_check_fault(ctx, k_ra8_fs_check_fault_scan_truncated, dir->cluster, 0U, 0U);
  return k_ra8_ok;
}

RA8_INTERNAL
static ra8_err_t
internal_exchk_scan_dir(ra8_fs_check_ctx_t* ctx, const exfat_dir_t* dir, exfat_dir_stack_t* stack)
{
  exfat_cursor_t cur = {};
  priv_exfat_cursor_init(dir, &cur);
  while (cur.scanned < (uint32_t)k_exfat_scan_limit) {
    uint8_t         e[k_exfat_entry_bytes] = {};
    const ra8_err_t r                      = priv_exfat_next_entry(ctx->m, &cur, e);
    if (r == k_ra8_err_not_found) {
      return k_ra8_ok; /* run ended without an end-of-directory marker */
    }
    if (r != k_ra8_ok) {
      return r;
    }
    if (e[0] == (uint8_t)k_exfat_entry_eod) {
      return k_ra8_ok;
    }
    if ((e[0] & (uint8_t)k_exfat_inuse_bit) == 0U) {
      continue; /* a deleted remnant */
    }
    if ((e[0] == (uint8_t)k_exfat_entry_bitmap) || (e[0] == (uint8_t)k_exfat_entry_upcase)) {
      internal_exchk_system_run(ctx, e);
      continue;
    }
    if (e[0] == (uint8_t)k_exfat_entry_file) {
      bool            stop = false;
      const ra8_err_t fe =
        internal_exchk_scan_dir_file_entry(ctx, &cur, e, stack, dir->cluster, &stop);
      if (stop) {
        return fe;
      }
    }
  }
  return internal_exchk_scan_dir_terminal(ctx, &cur, dir);
}

RA8_INTERNAL
static ra8_err_t internal_exchk_tree(ra8_fs_check_ctx_t* ctx)
{
  /* The explicit DFS array (~2 KiB) stays in module-static storage so this
   * frame remains within budget. Metadata is automatic, letting the overflow
   * test exercise the real push guard without allocating the whole array. The
   * walk is iterative and single-threaded under the fs lock. */
  static exfat_dir_t s_work_items[k_ra8_fs_check_max_dirs];
  exfat_dir_stack_t  worklist = {.items = s_work_items};
  priv_exfat_dir_root(ctx->m, &worklist.items[0]);
  worklist.top = 1U;
  while (worklist.top > 0U) {
    worklist.top--;
    const exfat_dir_t dir = worklist.items[worklist.top];
    ctx->rep->dirs_visited++;
    ra8_err_t err = internal_exchk_mark_dir_alloc(ctx, &dir);
    if (err != k_ra8_ok) {
      return err;
    }
    err = internal_exchk_scan_dir(ctx, &dir, &worklist);
    if (err != k_ra8_ok) {
      return err;
    }
  }
  return k_ra8_ok;
}
 
/* =============================================================================
 * Allocation-bitmap population count and diff
 * =============================================================================
 */

RA8_INTERNAL
static void internal_exchk_diff_byte(ra8_fs_check_ctx_t* ctx, uint8_t b, uint32_t base)
{
  for (uint32_t j = 0U; j < (uint32_t)k_exchk_bits_per_byte; j++) {
    const uint32_t idx = base + j;
    if (idx >= ctx->rep->clusters_total) {
      return;
    }
    const uint8_t alloc = (uint8_t)(((uint32_t)b >> j) & 1U);
    const uint8_t refd =
      (uint8_t)(((uint32_t)ctx->bitmap[idx >> k_exchk_byte_shift] >> (idx & k_exchk_bit_mask)) &
                1U);
    if ((alloc != 0U) && (refd == 0U)) {
      ctx->rep->clusters_lost++;
      priv_check_fault(ctx,
                       k_ra8_fs_check_fault_lost_cluster,
                       idx + (uint32_t)k_cluster_first_data,
                       0U,
                       0U);
    }
    if ((alloc == 0U) && (refd != 0U)) {
      ctx->rep->bitmap_mismatches++;
      priv_check_fault(ctx,
                       k_ra8_fs_check_fault_bitmap_ref_unset,
                       idx + (uint32_t)k_cluster_first_data,
                       0U,
                       0U);
    }
  }
}

RA8_INTERNAL
static ra8_err_t internal_exchk_bitmap_pass(ra8_fs_check_ctx_t* ctx, uint64_t bmp_lba)
{
  const uint32_t total      = ctx->rep->clusters_total;
  const uint32_t full_bytes = total >> (uint32_t)k_exchk_byte_shift;
  const uint32_t rem_bits   = total & (uint32_t)k_exchk_bit_mask;
  const uint32_t nbytes     = full_bytes + ((rem_bits != 0U) ? 1U : 0U);
  uint32_t       used       = 0U;
  uint64_t       loaded     = UINT64_MAX;
  uint8_t* const sec        = priv_sec_io();
  for (uint32_t bi = 0U; bi < nbytes; bi++) {
    const uint64_t lba = bmp_lba + (bi / priv_bps(ctx->m));
    if (lba != loaded) {
      const ra8_err_t err = priv_read_sector(ctx->m, lba, sec);
      if (err != k_ra8_ok) {
        return err;
      }
      loaded = lba;
    }
    uint8_t b = sec[bi % priv_bps(ctx->m)];
    if (bi == full_bytes) {
      b = (uint8_t)(b & (uint8_t)((1U << rem_bits) - 1U));
    }
    used += internal_exchk_popcount8(b);
    if (ctx->bitmap != nullptr) {
      internal_exchk_diff_byte(ctx, b, bi << (uint32_t)k_exchk_byte_shift);
    }
  }
  ctx->rep->clusters_used = used;
  ctx->rep->clusters_free = total - used;
  return k_ra8_ok;
}
 
/* `priv_check_exfat()`: see header for the documented contract. */
ra8_err_t priv_check_exfat(ra8_fs_check_ctx_t* ctx)
{
  uint32_t        bclus = 0U;
  uint32_t        blen  = 0U;
  const ra8_err_t fe    = priv_exfat_find_bitmap(ctx->m, &bclus, &blen);
  if (fe == k_ra8_err_not_found) {
    ctx->rep->entries_bad++;
    priv_check_fault(ctx, k_ra8_fs_check_fault_bad_dir_entry, 0U, 0U, 0U);
    return k_ra8_ok;
  }
  if (fe != k_ra8_ok) {
    return fe;
  }
  const uint64_t bmp_lba = priv_cluster_to_lba(ctx->m, bclus);
  if (ctx->bitmap != nullptr) {
    priv_check_zero_bitmap(ctx);
    const ra8_err_t te = internal_exchk_tree(ctx);
    if (te != k_ra8_ok) {
      return te;
    }
  }
  return internal_exchk_bitmap_pass(ctx, bmp_lba);
}