exfat: memory optimisations and stringent integrity checks for up-case table
Get series with b4
b4 am [email protected]Versions newest first
- v0 Latest4 patches 2 repliesIn review
Patches in v0 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/4 | exfat: refactor nls.c (tables)fs/ fs/ fs/ +1 more | +409 | 0 replies | |
| 2/4 | exfat: use upcase_ptable and upcase_range_info to reduce memory footprintfs/ fs/ fs/ +3 more | +1027 | 2 replies | |
| 3/4 | exfat: add default_upcase option (read-only)fs/ | +3 | 0 replies | |
| 4/4 | exfat: more pedantic upcase table validity checkfs/ | +13 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v0 yet.
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