ra8_fs_fat_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_check_bad_fat12 = 0x0FF7U,     
  k_check_bad_fat16 = 0xFFF7U,     
  k_check_bad_fat32 = 0x0FFFFFF7U, 
} ra8_fs_check_marker_t;

typedef enum : uint32_t {
  k_check_bit_mask   = 7U, 
  k_check_byte_shift = 3U, 
} ra8_fs_check_bit_t;

typedef struct {
  dir_loc_t items[k_ra8_fs_check_max_dirs]; 
  uint32_t  top;                            
  uint8_t   truncated;                      
} fat_dir_stack_t;
 
/* =============================================================================
 * Shared scaffolding (used by the exFAT half too)
 * =============================================================================
 */
 
/* `priv_check_fault()`: see header for the documented contract. */
void priv_check_fault(ra8_fs_check_ctx_t*       ctx,
                      ra8_fs_check_fault_kind_t kind,
                      uint32_t                  cluster,
                      uint64_t                  lba,
                      uint32_t                  entry_off)
{
  if (ctx->rep->faults_total == 0U) {
    ctx->rep->first_fault.kind      = kind;
    ctx->rep->first_fault.cluster   = cluster;
    ctx->rep->first_fault.lba       = lba;
    ctx->rep->first_fault.entry_off = entry_off;
  }
  ctx->rep->faults_total++;
}
 
/* `priv_check_in_range()`: see header for the documented contract. */
bool priv_check_in_range(const ra8_fs_check_ctx_t* ctx, uint32_t cluster)
{
  if (cluster < (uint32_t)k_cluster_first_data) {
    return false;
  }
  return (cluster - (uint32_t)k_cluster_first_data) < ctx->rep->clusters_total;
}
 
/* `priv_check_mark()`: see header for the documented contract. */
bool priv_check_mark(ra8_fs_check_ctx_t* ctx, uint32_t cluster)
{
  const uint32_t idx  = cluster - (uint32_t)k_cluster_first_data;
  const uint32_t byte = idx >> (uint32_t)k_check_byte_shift;
  const uint8_t  mask = (uint8_t)(1U << (idx & (uint32_t)k_check_bit_mask));
  if ((ctx->bitmap[byte] & mask) != 0U) {
    return true;
  }
  ctx->bitmap[byte] = (uint8_t)(ctx->bitmap[byte] | mask);
  return false;
}
 
/* `priv_check_visit()`: see header for the documented contract. */
bool priv_check_visit(ra8_fs_check_ctx_t* ctx, uint32_t cluster, ra8_fs_check_fault_kind_t oor_kind)
{
  if (!priv_check_in_range(ctx, cluster)) {
    if (oor_kind == k_ra8_fs_check_fault_bad_dir_entry) {
      ctx->rep->entries_bad++;
    }
    priv_check_fault(ctx, oor_kind, cluster, 0U, 0U);
    return true;
  }
  if (priv_check_mark(ctx, cluster)) {
    ctx->rep->chains_crosslinked++;
    priv_check_fault(ctx, k_ra8_fs_check_fault_crosslink, cluster, 0U, 0U);
    return true;
  }
  return false;
}
 
/* `priv_check_zero_bitmap()`: see header for the documented contract. */
void priv_check_zero_bitmap(ra8_fs_check_ctx_t* ctx)
{
  const uint32_t nbytes =
    (ctx->bitmap_bits + (uint32_t)k_check_bit_mask) >> (uint32_t)k_check_byte_shift;
  for (uint32_t i = 0U; i < nbytes; i++) {
    ctx->bitmap[i] = 0U;
  }
}
 
/* =============================================================================
 * Pass 1: classify every FAT entry
 * =============================================================================
 */

RA8_INTERNAL
static uint32_t internal_fat_bad_marker(const ra8_fs_mount_t* m)
{
  if (m->type == k_ra8_fs_type_fat12) {
    return (uint32_t)k_check_bad_fat12;
  }
  if (m->type == k_ra8_fs_type_fat16) {
    return (uint32_t)k_check_bad_fat16;
  }
  return (uint32_t)k_check_bad_fat32;
}

RA8_INTERNAL
static void internal_fat_classify_one(ra8_fs_check_ctx_t* ctx, uint32_t cluster, uint32_t value)
{
  if (value == (uint32_t)k_cluster_free) {
    ctx->rep->clusters_free++;
    return;
  }
  if (value == internal_fat_bad_marker(ctx->m)) {
    ctx->rep->clusters_bad++;
    return;
  }
  ctx->rep->clusters_used++;
  if (priv_is_eoc(ctx->m, value) != 0U) {
    return;
  }
  if (!priv_check_in_range(ctx, value)) {
    priv_check_fault(ctx, k_ra8_fs_check_fault_bad_fat_value, cluster, 0U, 0U);
  }
}

RA8_INTERNAL
static ra8_err_t internal_fat_classify(ra8_fs_check_ctx_t* ctx)
{
  const uint32_t last = (uint32_t)k_cluster_first_data + ctx->rep->clusters_total;
  for (uint32_t c = (uint32_t)k_cluster_first_data; c < last; c++) {
    uint32_t        v   = 0U;
    const ra8_err_t err = priv_fat_get(ctx->m, c, &v);
    if (err != k_ra8_ok) {
      return err;
    }
    internal_fat_classify_one(ctx, c, v);
  }
  return k_ra8_ok;
}
 
/* =============================================================================
 * Pass 2: walk the directory tree, marking referenced clusters
 * =============================================================================
 */

RA8_INTERNAL
static ra8_err_t internal_fat_mark_chain(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_INTERNAL
static void internal_fat_push(ra8_fs_check_ctx_t* ctx, fat_dir_stack_t* stack, uint32_t clus)
{
  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, clus, 0U, 0U);
    }
    return;
  }
  stack->items[stack->top].is_root = 0U;
  stack->items[stack->top].cluster = clus;
  stack->top++;
}
 
/* ra8_fs_check_test_fat_push_overflow(): see header for the test-only contract. */
RA8_TEST_HELPER
void ra8_fs_check_test_fat_push_overflow(ra8_fs_check_ctx_t* ctx,
                                         uint32_t            cluster,
                                         bool                already_truncated)
{
  fat_dir_stack_t stack = {
    .top       = (uint32_t)k_ra8_fs_check_max_dirs,
    .truncated = already_truncated ? 1U : 0U,
  };
  internal_fat_push(ctx, &stack, cluster);
}

RA8_INTERNAL
static ra8_err_t internal_fat_entry(ra8_fs_check_ctx_t* ctx,
                                    fat_dir_stack_t*    stack,
                                    const uint8_t*      ent,
                                    uint64_t            lba,
                                    uint32_t            entry_off,
                                    uint8_t*            out_eod)
{
  *out_eod            = 0U;
  const uint8_t name0 = ent[k_dir_off_name];
  const uint8_t attr  = ent[k_dir_off_attr];
  if (name0 == (uint8_t)k_dir_marker_free_perm) {
    *out_eod = 1U;
    return k_ra8_ok;
  }
  if (name0 == (uint8_t)k_dir_marker_free_used) {
    return k_ra8_ok;
  }
  if (attr == (uint8_t)k_ra8_fs_attr_lfn) {
    return k_ra8_ok;
  }
  if (name0 == (uint8_t)k_dir_marker_dot) {
    return k_ra8_ok;
  }
  const uint8_t is_dir = ((attr & (uint8_t)k_ra8_fs_attr_directory) != 0U) ? 1U : 0U;
  if ((is_dir == 0U) && ((attr & (uint8_t)k_ra8_fs_attr_volume_id) != 0U)) {
    return k_ra8_ok; /* a volume-label entry owns no chain */
  }
  const uint32_t first = priv_entry_first_cluster(ent);
  if ((first != 0U) && !priv_check_in_range(ctx, first)) {
    ctx->rep->entries_bad++;
    priv_check_fault(ctx, k_ra8_fs_check_fault_bad_dir_entry, first, lba, entry_off);
    return k_ra8_ok;
  }
  if (is_dir != 0U) {
    if (first != 0U) {
      internal_fat_push(ctx, stack, first);
    }
    return k_ra8_ok;
  }
  ctx->rep->files_visited++;
  if (first != 0U) {
    return internal_fat_mark_chain(ctx, first);
  }
  return k_ra8_ok;
}

RA8_INTERNAL
static ra8_err_t internal_fat_visit_sector(ra8_fs_check_ctx_t* ctx,
                                           fat_dir_stack_t*    stack,
                                           const uint8_t*      buf,
                                           uint64_t            lba,
                                           uint8_t*            out_eod)
{
  for (uint32_t e = 0U; e < priv_dir_eps(ctx->m); e++) {
    const uint32_t  off = e * (uint32_t)k_ra8_fs_dir_entry_bytes;
    uint8_t         eod = 0U;
    const ra8_err_t err = internal_fat_entry(ctx, stack, &buf[off], lba, off, &eod);
    if (err != k_ra8_ok) {
      return err;
    }
    if (eod != 0U) {
      *out_eod = 1U;
      return k_ra8_ok;
    }
  }
  *out_eod = 0U;
  return k_ra8_ok;
}

RA8_INTERNAL
static ra8_err_t internal_fat_scan_fixed_root(ra8_fs_check_ctx_t* ctx, fat_dir_stack_t* stack)
{
  const uint32_t secs = (ctx->m->root_entries + (priv_dir_eps(ctx->m) - 1U)) / priv_dir_eps(ctx->m);
  for (uint32_t s = 0U; s < secs; s++) {
    const uint64_t lba = ctx->m->first_root_lba + s;
    uint8_t* const buf = priv_sec_walk();
    ra8_err_t      err = priv_read_sector(ctx->m, lba, buf);
    if (err != k_ra8_ok) {
      return err;
    }
    uint8_t eod = 0U;
    err         = internal_fat_visit_sector(ctx, stack, buf, lba, &eod);
    if (err != k_ra8_ok) {
      return err;
    }
    if (eod != 0U) {
      return k_ra8_ok;
    }
  }
  return k_ra8_ok;
}

RA8_INTERNAL
static ra8_err_t
internal_fat_scan_cluster_dir(ra8_fs_check_ctx_t* ctx, fat_dir_stack_t* stack, 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_dir_entry)) {
      return k_ra8_ok;
    }
    const uint64_t base = priv_cluster_to_lba(ctx->m, c);
    for (uint32_t s = 0U; s < ctx->m->sectors_per_cluster; s++) {
      uint8_t* const buf = priv_sec_walk();
      ra8_err_t      err = priv_read_sector(ctx->m, base + s, buf);
      if (err != k_ra8_ok) {
        return err;
      }
      uint8_t eod = 0U;
      err         = internal_fat_visit_sector(ctx, stack, buf, base + s, &eod);
      if (err != k_ra8_ok) {
        return err;
      }
      if (eod != 0U) {
        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;
    }
    c = v;
  }
  (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_fat_scan_cluster_dir(ra8_fs_check_ctx_t* ctx, uint32_t first)
{
  fat_dir_stack_t stack = {};
  return internal_fat_scan_cluster_dir(ctx, &stack, first);
}

RA8_INTERNAL
static ra8_err_t internal_fat_tree(ra8_fs_check_ctx_t* ctx)
{
  fat_dir_stack_t stack  = {};
  stack.items[0].is_root = 1U;
  stack.items[0].cluster = 0U;
  stack.top              = 1U;
  const bool fat32       = (ctx->m->type == k_ra8_fs_type_fat32);
  while (stack.top > 0U) {
    stack.top--;
    const dir_loc_t loc = stack.items[stack.top];
    ctx->rep->dirs_visited++;
    ra8_err_t err = k_ra8_ok;
    if ((loc.is_root != 0U) && !fat32) {
      err = internal_fat_scan_fixed_root(ctx, &stack);
    } else {
      const uint32_t first = (loc.is_root != 0U) ? ctx->m->root_cluster : loc.cluster;
      err                  = internal_fat_scan_cluster_dir(ctx, &stack, first);
    }
    if (err != k_ra8_ok) {
      return err;
    }
  }
  return k_ra8_ok;
}
 
/* =============================================================================
 * Pass 3: diff for lost clusters, and the FAT32 FSInfo free count
 * =============================================================================
 */

RA8_INTERNAL
static ra8_err_t internal_fat_diff(ra8_fs_check_ctx_t* ctx)
{
  const uint32_t marker = internal_fat_bad_marker(ctx->m);
  const uint32_t last   = (uint32_t)k_cluster_first_data + ctx->rep->clusters_total;
  for (uint32_t c = (uint32_t)k_cluster_first_data; c < last; c++) {
    uint32_t        v   = 0U;
    const ra8_err_t err = priv_fat_get(ctx->m, c, &v);
    if (err != k_ra8_ok) {
      return err;
    }
    if ((v == (uint32_t)k_cluster_free) || (v == marker)) {
      continue;
    }
    const uint32_t idx  = c - (uint32_t)k_cluster_first_data;
    const uint8_t  mask = (uint8_t)(1U << (idx & (uint32_t)k_check_bit_mask));
    if ((ctx->bitmap[idx >> (uint32_t)k_check_byte_shift] & mask) == 0U) {
      ctx->rep->clusters_lost++;
      priv_check_fault(ctx, k_ra8_fs_check_fault_lost_cluster, c, 0U, 0U);
    }
  }
  return k_ra8_ok;
}

RA8_INTERNAL
static ra8_err_t internal_fat_fsinfo(ra8_fs_check_ctx_t* ctx)
{
  if (ctx->m->type != k_ra8_fs_type_fat32) {
    return k_ra8_ok;
  }
  uint8_t* const  boot = priv_sec_walk();
  const ra8_err_t be   = priv_read_sector(ctx->m, 0U, boot);
  if (be != k_ra8_ok) {
    return be;
  }
  const uint32_t lba = (uint32_t)priv_rd16(&boot[k_fmt_off_f32_fsinfo]);
  if ((lba == 0U) || (lba >= ctx->m->reserved_sectors)) {
    return k_ra8_ok;
  }
  uint8_t* const  sec = priv_sec_walk();
  const ra8_err_t se  = priv_read_sector(ctx->m, lba, sec);
  if (se != k_ra8_ok) {
    return se;
  }
  if (priv_rd32(&sec[k_fmt_fsi_off_lead]) != (uint32_t)k_fmt_fsi_lead_sig) {
    return k_ra8_ok;
  }
  if (priv_rd32(&sec[k_fmt_fsi_off_struct]) != (uint32_t)k_fmt_fsi_struct_sig) {
    return k_ra8_ok;
  }
  if (priv_rd32(&sec[k_fmt_fsi_off_trail]) != (uint32_t)k_fmt_fsi_trail_sig) {
    return k_ra8_ok;
  }
  const uint32_t stored = priv_rd32(&sec[k_fmt_fsi_off_free]);
  if ((stored != (uint32_t)k_fs_free_unknown) && (stored != ctx->rep->clusters_free)) {
    priv_check_fault(ctx, k_ra8_fs_check_fault_free_count_bad, 0U, lba, 0U);
  }
  return k_ra8_ok;
}
 
/* `priv_check_fat()`: see header for the documented contract. */
ra8_err_t priv_check_fat(ra8_fs_check_ctx_t* ctx)
{
  ra8_err_t err = internal_fat_classify(ctx);
  if (err != k_ra8_ok) {
    return err;
  }
  if (ctx->bitmap != nullptr) {
    priv_check_zero_bitmap(ctx);
    err = internal_fat_tree(ctx);
    if (err != k_ra8_ok) {
      return err;
    }
    err = internal_fat_diff(ctx);
    if (err != k_ra8_ok) {
      return err;
    }
  }
  return internal_fat_fsinfo(ctx);
}
 
/* =============================================================================
 * Public entry point -- the lock bracket
 * =============================================================================
 */

RA8_INTERNAL
static bool internal_check_bitmap_ok(uint32_t total, const uint8_t* bitmap, uint32_t bitmap_bytes)
{
  if (bitmap == nullptr) {
    return false;
  }
  return bitmap_bytes >= ((total + (uint32_t)k_check_bit_mask) >> (uint32_t)k_check_byte_shift);
}

RA8_INTERNAL
RA8_EXPECTS_LOCK("ra8_fs_lock")
static ra8_err_t internal_check_locked(ra8_fs_mount_t*        handle,
                                       uint8_t*               bitmap,
                                       uint32_t               bitmap_bytes,
                                       ra8_fs_check_report_t* report)
{
  if ((handle == nullptr) || (report == nullptr)) {
    return k_ra8_err_null_ptr;
  }
  if (handle->in_use == 0U) {
    return k_ra8_err_invalid_state;
  }
  ra8_fs_check_report_t candidate = {};
  candidate.type                  = handle->type;
  candidate.clusters_total        = handle->count_of_clusters;
  const bool have_bitmap =
    internal_check_bitmap_ok(handle->count_of_clusters, bitmap, bitmap_bytes);
  candidate.referenced_scan = have_bitmap;
  candidate.clusters_lost   = have_bitmap ? 0U : (uint32_t)k_ra8_fs_check_unknown;
  ra8_fs_check_ctx_t ctx    = {.m           = handle,
                               .rep         = &candidate,
                               .bitmap      = have_bitmap ? bitmap : nullptr,
                               .bitmap_bits = handle->count_of_clusters};
  ra8_err_t          err    = k_ra8_ok;
  if (handle->type == k_ra8_fs_type_exfat) {
    err = priv_check_exfat(&ctx);
  } else {
    err = priv_check_fat(&ctx);
  }
  if (err != k_ra8_ok) {
    return err;
  }
  *report = candidate;
  return k_ra8_ok;
}
 
RA8_OWNS_RESOURCE("ra8_fs_lock")
ra8_err_t ra8_fs_check(ra8_fs_mount_t*        handle,
                       uint8_t*               bitmap,
                       uint32_t               bitmap_bytes,
                       ra8_fs_check_report_t* report)
{
  priv_lock_acquire();
  const ra8_err_t err = internal_check_locked(handle, bitmap, bitmap_bytes, report);
  priv_lock_release();
  return err;
}