Skip to content

exfat: memory optimisations and stringent integrity checks for up-case table

David Timber linux-fsdevel 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v0 Latest4 patches 2 repliesIn review

Patches in v0 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/4exfat: refactor nls.c (tables)fs/exfat/Makefile fs/exfat/exfat_fs.h fs/exfat/nls.c +1 more+409 -3980 replies
2/4exfat: use upcase_ptable and upcase_range_info to reduce memory footprintfs/exfat/Makefile fs/exfat/exfat_fs.h fs/exfat/nls.c +3 more+1027 -4322 replies
3/4exfat: add default_upcase option (read-only)fs/exfat/super.c+3 -00 replies
4/4exfat: more pedantic upcase table validity checkfs/exfat/nls.c+13 -110 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v0 yet.

Read the v0 thread

Cover letter [PATCH v0 0/4] exfat: memory optimisations and stringent integrity checks for up-case table

This rounds of patches introduce efficient upcase table implementation to exFAT as well as more stringent check against the upcase table when mounting the volume.

**Theoretical trade offs**

The use of "paged upcase table" saw runtime memory footprint reduced from 131KB to 8KB(+some slab overhead). Other trade offs include:

- Reduced .rodata usage from 5KB to 2KB at the cost of added delay in module initialisation for populating the default upcase table
- Slight performance increase from reduced cache misses when traversing directories with entries with a wide range of unicode code points

**Tests**

Upcase table test cases are available in my repo(https://github.com/dxdxdt/gists/tree/master/writeups/exfat):

- exfat-default-upcase:
- -c option: uncompresses and prints the default compressed upcase table
- -p option: tests if exfat_populate_upcase_ptable() produces the same default upcase table included in the kernel prior to the patches
- -pc option: generates .rodata included in fs/exfat/tables.c
- exfat-test-upcase: brute forces combinations(2^32) of unicode upcase conversion to ensure that no regression behaviour is introduced. The test finishes within 24 hours ;)
- exfat-profile-upcase.sh and exfat-print-all-allowed: profile kernel memory use per moun and the worse-case directory traversal, entries filled with a range of unicode code points. Use with make profile

**Profiling**

When tested with 16 volumes(make profile), ~1MB saving in memory usage per volume is observed(available mem 122528 -> 140884).

**NOTES**

Errors found in the "recommended" upcase table are outlined in fs/exfat/tables.c.

The value of EXFAT_UPTBL_PAGESIZE(512 __u16 entries or 1024 bytes) is determined to be the best based on the data:

```
  $ ./exfat-default-upcase > test-control
  ========== page 1 ==========
  ========== page 2 ==========
  ========== page 3 ==========
  ========== page 15 ==========
  ========== page 16 ==========
  ========== page 17 ==========
  ========== page 19 ==========
  ========== page 23 ==========
  entries: 874 (1748 bytes)
  non-empty pages: 8 (nb_page * pagesize * 2 = 512 * 8 * 2 = 8192 bytes)
```

The program reports that the total of 8 "pages" of 1KiB are used by the table.

Regression test:

```

  (with the mainline exfat module)
  $ ./exfat-test-upcase /PATH/TO/EXFAT/MOUNTPOINT > a
  ...

  (with the patched exfat module)
  $ ./exfat-test-upcase /PATH/TO/EXFAT/MOUNTPOINT > b
  ...

  $ diff a b
```

Let me know if the test programs needs to be added to the tree (perhaps in /tools/testing/selftests/filesystems/exfat/ ??)

---

David Timber (4):
exfat: refactor nls.c (tables)
exfat: use upcase_ptable and upcase_range_info to reduce memory
footprint
exfat: add default_upcase option (read-only)
exfat: more pedantic upcase table validity check

 fs/exfat/Makefile   |   2 +-
 fs/exfat/exfat_fs.h |  48 ++-
 fs/exfat/nls.c      | 547 +++++-----------------------
 fs/exfat/super.c    |  10 +
 fs/exfat/tables.c   | 845 ++++++++++++++++++++++++++++++++++++++++++++
 fs/exfat/upcase.c   |  79 +++++
 6 files changed, 1071 insertions(+), 460 deletions(-)
 create mode 100644 fs/exfat/tables.c
 create mode 100644 fs/exfat/upcase.c

--
2.53.0.1.ga224b40d3f.dirty