fsck_msdosfs: do not call checksize() if the cluster is bad

PR: 276464
MFC after: 1 week

Purge more stray embedded $FreeBSD$ strings

These do not use __FBSDID but instead use bare char arrays.

Reviewed by: imp, emaste
Differential Revision: https://reviews.freebsd.org/D41957

spdx: The BSD-2-Clause-FreeBSD identifier is obsolete, drop -FreeBSD

The SPDX folks have obsoleted the BSD-2-Clause-FreeBSD identifier. Catch
up to that fact and revert to their recommended match of

spdx: The BSD-2-Clause-FreeBSD identifier is obsolete, drop -FreeBSD

The SPDX folks have obsoleted the BSD-2-Clause-FreeBSD identifier. Catch
up to that fact and revert to their recommended match of BSD-2-Clause.

Discussed with: pfg
MFC After: 3 days
Sponsored by: Netflix

show more ...

fsck_msdosfs: truncate directory entry when the head pointer is invalid.

As far as we know, there is no FAT implementation that supported hard
links, and our msdosfs driver assumed one cluster chain

fsck_msdosfs: truncate directory entry when the head pointer is invalid.

As far as we know, there is no FAT implementation that supported hard
links, and our msdosfs driver assumed one cluster chain is only
referenced by one directory entry and clears it out when the file is
deleted. On the other hand, the current code would proceed with
checkchain() when the directory entry's head cluster is a valid numbered
cluster without checking if it was a valid head node of a cluster chain.

So if the cluster do not being a chain (e.g. CLUST_FREE, CLUST_BAD),
or was already referenced by another directory entry, this would
trigger an assertion in check_chain() at a later time.

Fix this by giving the user an option to truncate the directory entry
when the head cluster is an invalid cluster, an visited head node,
or not a head node.

Reported by: NetApp (kevans@)
Reviewed by: kevans, emaste (no objection)
MFC after: 2 weeks
Differential Revision: https://reviews.freebsd.org/D32699

show more ...

Use %ju and cast to (uintmax_t) to avoid using PRI* macros.

Suggested by: kevlo

Fix build.

Pointy hat to: delphij
MFC after: 3 days

sbin/fsck_msdosfs: Fix an integer overflow on 32-bit platforms.

The purpose of checksize() is to verify that the referenced cluster
chain size matches the recorded file size (up to 2^32 - 1) in the

sbin/fsck_msdosfs: Fix an integer overflow on 32-bit platforms.

The purpose of checksize() is to verify that the referenced cluster
chain size matches the recorded file size (up to 2^32 - 1) in the
directory entry. We follow the cluster chain, then multiple the
cluster count by bytes per cluster to get the physical size, then
check it against the recorded size.

When a file is close to 4 GiB (between 4GiB - cluster size and 4GiB,
both non-inclusive), the product of cluster count and bytes per
cluster would be exactly 4 GiB. On 32-bit systems, because size_t
is 32-bit, this would wrap back to 0, which will cause the file be
truncated to 0.

Fix this by using 64-bit physicalSize instead.

This fix is inspired by an Android change request at
https://android-review.googlesource.com/c/platform/external/fsck_msdos/+/1428461

PR: 249533
Reviewed by: kevlo
MFC after: 3 days
Differential Revision: https://reviews.freebsd.org/D26524

show more ...

Reduce memory footprint of fsck_msdosfs.

This is a re-apply r356249 with changes to make GCC happy.

This utility was initially written for FAT12/16, which were inherently
small. When FAT32 support

Reduce memory footprint of fsck_msdosfs.

This is a re-apply r356249 with changes to make GCC happy.

This utility was initially written for FAT12/16, which were inherently
small. When FAT32 support was added, the old data structure and
algorithms remain used with minimal changes.

With growing size of FAT32 media, the current data structure that
requires 4 32-bit variables per each FAT32 table entry would consume up
to 4 GiB of RAM, which can be too big for systems with limited RAM
available.

Address this by taking a different approach of validating the FAT.

The FAT is essentially a set of linked lists of chains that was
referenced by directory entries, and the checker needs to make sure that
the linked chains of clusters do not have cross-linked chains, and every
chain were referenced by one and only one directory entry. Instead of
keeping track of the chain's 'head' cluster number, the size of the
chain, the used status of the chain and the "next" pointer which is
content of the FAT table, we create accessors for the FAT table data
for the "next" pointer, and keep only one bit to indicate if the
current cluster is a 'head' node of a cluster chain, in a bitmap.

We further overhaul the FAT checker to find out the possible head nodes
by excluding ones that are not (in other words, nodes that have some
other nodes claiming them as the next node) instead of marking the head
nodes for each node on the chain. This approach greatly reduced the
complexiety of computation from O(N^2) worst case, to an O(N) scan for
worst case. The file (cluster chain) length is not useful for the FAT
checker, so don't bother to calculate them in the FAT checker and
instead leave the task to the directory structure check, at which point
we would have non-crossed cluster chains, and we are guaranteed that
each cluster will be visited for at most one time.

When checking the directory structures, we use the head node indicator
to as the visited (used) flag: every cluster chain can only be
referenced by one directory entry, so we clear them when calculating
the length of the chain, and we can immediately tell if there are
anomalies in the directory entry.

As a result, the required RAM size is now 1 bit per each entry of
the FAT table, plus memory needed to hold the FAT table in memory,
instead of 16 bytes (=128 bits) per each entry. For FAT12 and FAT16,
we will load the whole FAT table into memory as they are smaller than
128KiB, and for FAT32, we first attempt to mmap() it into memory, and
when that fails, we would fall back to a simple LRU cache of 4 MiB of
RAM.

sbin/fsck_msdosfs/boot.c:

- Added additional sanity checks for valid FAT32/FAT16/FAT12 cluster
number.
- FAT32: check if root directory starts with a valid cluster number,
moved from dir.c. There is no point to proceed if the filesystem
is already damaged beyond repair.

sbin/fsck_msdosfs/check.c:

- Combine phase 1 and phase 2, now that the readfat() is able to
detect cross chains.

sbin/fsck_msdosfs/dir.c:

- Refactor code to use FAT accessor instead of accessing the internal
representation of FAT table.
- Make use of the cluster chain head bitmap.
- Clarify and simplify directory entry check, remove unnecessary
checks that are would be done at a later time (for example, whether
the directory's second cluster is a valid one, which is examined
more throughly in a later checkchain() and does not prevent us
from proceeding further).

sbin/fsck_msdosfs/dosfs.h:

- Remove internal representation of FAT table, which is replaced by
the head bitmap that is opaque to other code.
- Added a special CLUST_DEAD cluster type to indicate errors.

sbin/fsck_msdosfs/ext.h:

- Added a flag that overrides mmap(2) setting. The corresponding
command line option, -M is intentionally undocumented as we do not
expect users to need it.
- Added accessors for FAT table and convert existing interface to use
it.

sbin/fsck_msdosfs/fat.c:

- Added head bitmap to represent whether a cluster is a head cluster.
- Converted FAT internal representation to accessors.
- Implemented a LRU cache for FAT32 when mmap(2) should not or can not
be used.
- _readfat: Attempt a mmap(2) and fall back to regular read for
non-FAT32 file systems; use the LRU cache for FAT32 and prepopulate
the cache with the first 4MiB of the entries.
- readfat: Added support of head bitmap and use the population scan to
detect bogus chains.
- clusterdiff: removed, FATs are copied from the checked copy via
writefat()/copyfat().
- checkchain: calculates the length of a cluster chain and make sure
that it ends with a valid EOF marker.
- clearchain: follow and clear a chain and maintain the free cluster
count.
- checklost: convert to use head bitmap. At the end of all other scans,
the remaining 'head' nodes are leaders of lost cluster chains.

sbin/fsck_msdosfs/fat.c:

- Added a new -M option which is intentionally undocumented, to disable
the use of mmap().

Reviewed by: kevlo
MFC after: 1 month
Relnotes: yes
Differential Revision: https://reviews.freebsd.org/D22965

show more ...

Revert r356249 for now as it broke GCC builds.

Reduce memory footprint of fsck_msdosfs.

This utility was initially written for FAT12/16, which were inherently
small. When FAT32 support was added, the old data structure and
algorithms remain used

Reduce memory footprint of fsck_msdosfs.

This utility was initially written for FAT12/16, which were inherently
small. When FAT32 support was added, the old data structure and
algorithms remain used with minimal changes.

With growing size of FAT32 media, the current data structure that
requires 4 32-bit variables per each FAT32 table entry would consume up
to 4 GiB of RAM, which can be too big for systems with limited RAM
available.

Address this by taking a different approach of validating the FAT.

The FAT is essentially a set of linked lists of chains that was
referenced by directory entries, and the checker needs to make sure that
the linked chains of clusters do not have cross-linked chains, and every
chain were referenced by one and only one directory entry. Instead of
keeping track of the chain's 'head' cluster number, the size of the
chain, the used status of the chain and the "next" pointer which is
content of the FAT table, we create accessors for the FAT table data
for the "next" pointer, and keep only one bit to indicate if the
current cluster is a 'head' node of a cluster chain, in a bitmap.

We further overhaul the FAT checker to find out the possible head nodes
by excluding ones that are not (in other words, nodes that have some
other nodes claiming them as the next node) instead of marking the head
nodes for each node on the chain. This approach greatly reduced the
complexiety of computation from O(N^2) worst case, to an O(N) scan for
worst case. The file (cluster chain) length is not useful for the FAT
checker, so don't bother to calculate them in the FAT checker and
instead leave the task to the directory structure check, at which point
we would have non-crossed cluster chains, and we are guaranteed that
each cluster will be visited for at most one time.

When checking the directory structures, we use the head node indicator
to as the visited (used) flag: every cluster chain can only be
referenced by one directory entry, so we clear them when calculating
the length of the chain, and we can immediately tell if there are
anomalies in the directory entry.

As a result, the required RAM size is now 1 bit per each entry of
the FAT table, plus memory needed to hold the FAT table in memory,
instead of 16 bytes (=128 bits) per each entry. For FAT12 and FAT16,
we will load the whole FAT table into memory as they are smaller than
128KiB, and for FAT32, we first attempt to mmap() it into memory, and
when that fails, we would fall back to a simple LRU cache of 4 MiB of
RAM.

sbin/fsck_msdosfs/boot.c:

- Added additional sanity checks for valid FAT32/FAT16/FAT12 cluster
number.
- FAT32: check if root directory starts with a valid cluster number,
moved from dir.c. There is no point to proceed if the filesystem
is already damaged beyond repair.

sbin/fsck_msdosfs/check.c:

- Combine phase 1 and phase 2, now that the readfat() is able to
detect cross chains.

sbin/fsck_msdosfs/dir.c:

- Refactor code to use FAT accessor instead of accessing the internal
representation of FAT table.
- Make use of the cluster chain head bitmap.
- Clarify and simplify directory entry check, remove unnecessary
checks that are would be done at a later time (for example, whether
the directory's second cluster is a valid one, which is examined
more throughly in a later checkchain() and does not prevent us
from proceeding further).

sbin/fsck_msdosfs/dosfs.h:

- Remove internal representation of FAT table, which is replaced by
the head bitmap that is opaque to other code.
- Added a special CLUST_DEAD cluster type to indicate errors.

sbin/fsck_msdosfs/ext.h:

- Added a flag that overrides mmap(2) setting. The corresponding
command line option, -M is intentionally undocumented as we do not
expect users to need it.
- Added accessors for FAT table and convert existing interface to use
it.

sbin/fsck_msdosfs/fat.c:

- Added head bitmap to represent whether a cluster is a head cluster.
- Converted FAT internal representation to accessors.
- Implemented a LRU cache for FAT32 when mmap(2) should not or can not
be used.
- _readfat: Attempt a mmap(2) and fall back to regular read for
non-FAT32 file systems; use the LRU cache for FAT32 and prepopulate
the cache with the first 4MiB of the entries.
- readfat: Added support of head bitmap and use the population scan to
detect bogus chains.
- clusterdiff: removed, FATs are copied from the checked copy via
writefat()/copyfat().
- checkchain: calculates the length of a cluster chain and make sure
that it ends with a valid EOF marker.
- clearchain: follow and clear a chain and maintain the free cluster
count.
- checklost: convert to use head bitmap. At the end of all other scans,
the remaining 'head' nodes are leaders of lost cluster chains.

sbin/fsck_msdosfs/fat.c:

- Added a new -M option which is intentionally undocumented, to disable
the use of mmap().

Reviewed by: kevlo
MFC after: 1 month
Relnotes: yes
Differential Revision: https://reviews.freebsd.org/D22965

show more ...

Merge ^/head r352319 through r352435.

Avoid mixing cluster numbers and sector numbers. Makes code more readable.

Obtained from: NetBSD
MFC after: 2 weeks

Merge ^/head r351732 through r352104.

Correct overflow logic in fullpath().

Obtained from: OpenBSD
MFC after: 3 days

Remove redundant check and wrong fix: fat.c checks already take care
about cluster chains.

Obtained from: OpenBSD
MFC after: 2 weeks

MFHead @349234

Sponsored by: The FreeBSD Foundation

Avoid out of boundary access when checking invalid long filenames.

Obtained from: OpenBSD (dir.c,v 1.25)
MFC after: 3 days

MFHead @347527

Sponsored by: The FreeBSD Foundation

Don't cast result from malloc().

MFC after: 2 weeks

Write string constant differently to improve readability.

Reported by: rgrimes
Reviewed by: rgrimes, emaste
MFC after: 13 days
Differential Revision: https://reviews.freebsd.org/D19829

Fix build.

MFC after: 2 weeks
X-MFC-With: r345900

Implement checking of `.' and `..' entries of subdirectory.

Reviewed by: pfg
Obtained from: Android https://android.googlesource.com/platform/external/fsck_msdos/+/b6ee08aadb580341a4d80943741b80de

Implement checking of `.' and `..' entries of subdirectory.

Reviewed by: pfg
Obtained from: Android https://android.googlesource.com/platform/external/fsck_msdos/+/b6ee08aadb580341a4d80943741b80de16a88b5d%5E%21/
MFC after: 2 weeks
Differential Revision: https://reviews.freebsd.org/D19824

show more ...

Restore lfcl when LOSTDIR's chain was corrupted and overwritten
with invalid value.

Obtained from: Android https://android.googlesource.com/platform/external/fsck_msdos/+/4d6d6f8a3674ad67f970e2ae908

Restore lfcl when LOSTDIR's chain was corrupted and overwritten
with invalid value.

Obtained from: Android https://android.googlesource.com/platform/external/fsck_msdos/+/4d6d6f8a3674ad67f970e2ae908d34f64e4854cf%5E%21/
MFC after: 2 weeks

show more ...

MFHead@r345880

Assert that q can't be NULL. 'empty' is always non-NULL when DIREMPTY
is set earlier.

MFC after: 1 month