fs/squashfs: avoid 64-bit divisions on 32-bit
v3 cover fs/squashfs: avoid 64-bit divisions on 32-bit
Corrected to comply with all reviev comments in v2.
Sorry for the delay, but I was fighting a very bad u-boot misbehavior which seems completely unrelated to this patchset, I was unsure, but I made real sure my problems exist with ot without this.
My problem is u-boot seems to become unstable if I have 10 or more partitons on SD. At first I blamed my patches (10th partiton was what I used for testing), but problem persists even without patches and removing 10th (using p6 for SquashFS) errors vanished.
I did not find root cause yet, but it doesn't seem related to this.
Changes in v3:
- converted to use DIV_ROUND_(UP|DOWN)_ULL() macros (Miquel Raynal).
- split commits to handle unrelated Kconfig warning (Thomas Petazzoni).
Changes in v2:
- replace division with right shift (Daniel Schwierzeck).
- remove vocore2-specific change (Daniel Schwierzeck).
- add warning to Kconfig about CONFIG_SYS_MALLOC_LEN (Tom Rini).
Mauro Condarelli (2):
Add warning for dynamic memory usage.
avoid 64-bit divisions on 32-bit
fs/squashfs/Kconfig | 2 ++ fs/squashfs/sqfs.c | 32 ++++++++++++++++---------------- fs/squashfs/sqfs_inode.c | 7 ++++--- 3 files changed, 22 insertions(+), 19 deletions(-)
Signature · 1 line
2.25.1
PATCH v3 1/2 Add warning for dynamic memory usage.
SquashFS may need a large amount of dynamic memory fot its buffers, especially if and when compression is enabled I got failures with CONFIG_SYS_MALLOC_LEN < 0x4000.
I found no way to enforce this in Kconfig itself, so I resorted to ada a warning in help string.
---
(no changes since v1)
fs/squashfs/Kconfig | 2 ++ 1 file changed, 2 insertions(+)
fs/squashfs/Kconfig +2 -0
@@ -9,3 +9,5 @@ config FS_SQUASHFS filesystem use, for archival use (i.e. in cases where a .tar.gz file may be used), and in constrained block device/memory systems (e.g. embedded systems) where low overhead is needed. + WARNING: if compression is enabled SquashFS needs a large amount + of dynamic memory; make sure CONFIG_SYS_MALLOC_LEN >= 0x4000.
Signature · 1 line
2.25.1
PATCH v3 1/2 Add warning for dynamic memory usage.
Hi Mauro,
Mauro Condarelli <[email protected]> wrote on Thu, 8 Oct 2020 00:30:20 +0200:
Quoted 6 lines
SquashFS may need a large amount of dynamic memory fot its buffers, especially if and when compression is enabled I got failures with
CONFIG_SYS_MALLOC_LEN<0x4000.I found no way to enforce this in
Kconfigitself, so I resorted to ada a warning in help string.
Nit: s/ada/add/ s/in help/in the help/?
Besides that,
Quoted 14 lines
Signed-off-by Mauro Condarelli <[email protected]>---
(no changes since v1)
fs/squashfs/Kconfig | 2 ++ 1 file changed, 2 insertions(+)fs/squashfs/Kconfig +0
-0
fs/squashfs/Kconfig config FS_SQUASHFS · line 13
Quoted 5 lines
fs/squashfs/Kconfig +2
-0@@ -9,3 +9,5 @@ config FS_SQUASHFS filesystem use, for archival use (i.e. in cases where a .tar.gz file may be used), and in constrained block device/memory systems (e.g. embedded systems) where low overhead is needed. + WARNING: if compression is enabled SquashFS needs a large amount + of dynamic memory; make sure CONFIG_SYS_MALLOC_LEN >= 0x4000.
Thanks,
Miqu?l
PATCH v3 2/2 avoid 64-bit divisions on 32-bit
In reply to Mauro CondarelliUse macros in linux/kernel.h to avoid 64-bit divisions.
These divisions are needed to convert from file length (potentially over 32-bit range) to block number, so result and remainder are guaranteed to fit in 32-bit integers.
Some 32bit architectures (notably mipsel) lack an implementation of __udivdi3() compiler helper function in reduced libgcc.
Standard strategy is to use macros and do_div() inline.
---
Changes in v3:
- converted to use DIV_ROUND_(UP|DOWN)_ULL() macros (Miquel Raynal).
- split commits to handle unrelated Kconfig warning (Thomas Petazzoni).
Changes in v2:
- replace division with right shift (Daniel Schwierzeck).
- remove vocore2-specific change (Daniel Schwierzeck).
- add warning to Kconfig about CONFIG_SYS_MALLOC_LEN (Tom Rini).
fs/squashfs/sqfs.c | 32 ++++++++++++++++---------------- fs/squashfs/sqfs_inode.c | 7 ++++--- 2 files changed, 20 insertions(+), 19 deletions(-)
fs/squashfs/sqfs.c +16 -16
@@ -10,14 +10,14 @@#include <asm/unaligned.h> #include <errno.h> #include <fs.h> -#include <linux/types.h> +#include <linux/kernel.h> +#include <div64.h> #include <linux/byteorder/little_endian.h> #include <linux/byteorder/generic.h> #include <memalign.h> #include <stdlib.h> #include <string.h> #include <squashfs.h> -#include <part.h> #include "sqfs_decompressor.h" #include "sqfs_filesystem.h"
@@ -85,10 +85,10 @@ static int sqfs_calc_n_blks(__le64 start, __le64 end, u64 *offset)u64 start_, table_size; table_size =le64_to_cpu (end) -le64_to_cpu (start); - start_ =le64_to_cpu (start) / ctxt.cur_dev->blksz; + start_ =DIV_ROUND_DOWN_ULL (le64_to_cpu (start), ctxt.cur_dev->blksz); *offset =le64_to_cpu (start) - (start_ * ctxt.cur_dev->blksz); -return DIV_ROUND_UP (table_size + *offset, ctxt.cur_dev->blksz); +return (table_size + *offset + ctxt.cur_dev->blksz -1 ) >> ctxt.cur_dev->log2blksz; }/*
@@ -109,8 +109,8 @@ static int sqfs_frag_lookup(u32 inode_fragment_index,if (inode_fragment_index >=get_unaligned_le32 (&sblk->fragments))return -EINVAL ; - start =get_unaligned_le64 (&sblk->fragment_table_start) / - ctxt.cur_dev->blksz; + start =DIV_ROUND_DOWN_ULL (get_unaligned_le64 (&sblk->fragment_table_start), + ctxt.cur_dev->blksz); n_blks =sqfs_calc_n_blks (sblk->fragment_table_start, sblk->export_table_start, &table_offset);
@@ -135,7 +135,7 @@ static int sqfs_frag_lookup(u32 inode_fragment_index, start_block =get_unaligned_le64 (table + table_offset + block *sizeof (u64)); - start = start_block / ctxt.cur_dev->blksz; + start =DIV_ROUND_DOWN_ULL (start_block, ctxt.cur_dev->blksz); n_blks =sqfs_calc_n_blks (cpu_to_le64 (start_block), sblk->fragment_table_start, &table_offset);
@@ -641,8 +641,8 @@ static int sqfs_read_inode_table(unsigned char **inode_table) table_size =get_unaligned_le64 (&sblk->directory_table_start) -get_unaligned_le64 (&sblk->inode_table_start); - start =get_unaligned_le64 (&sblk->inode_table_start) / - ctxt.cur_dev->blksz; + start =DIV_ROUND_DOWN_ULL (get_unaligned_le64 (&sblk->inode_table_start), + ctxt.cur_dev->blksz); n_blks =sqfs_calc_n_blks (sblk->inode_table_start, sblk->directory_table_start, &table_offset);
@@ -725,8 +725,8 @@ static int sqfs_read_directory_table(unsigned char **dir_table, u32 **pos_list)/* DIRECTORY TABLE */ table_size =get_unaligned_le64 (&sblk->fragment_table_start) -get_unaligned_le64 (&sblk->directory_table_start); - start =get_unaligned_le64 (&sblk->directory_table_start) / - ctxt.cur_dev->blksz; + start =DIV_ROUND_DOWN_ULL (get_unaligned_le64 (&sblk->directory_table_start), + ctxt.cur_dev->blksz); n_blks =sqfs_calc_n_blks (sblk->directory_table_start, sblk->fragment_table_start, &table_offset);
@@ -1334,11 +1334,11 @@ int sqfs_read(const char *filename, void *buf, loff_t offset, loff_t len, }for (j =0 ; j < datablk_count; j++) { - start = data_offset / ctxt.cur_dev->blksz; + start =DIV_ROUND_DOWN_ULL (data_offset, ctxt.cur_dev->blksz); table_size =SQFS_BLOCK_SIZE (finfo.blk_sizes[j]); table_offset = data_offset - (start * ctxt.cur_dev->blksz); - n_blks =DIV_ROUND_UP (table_size + table_offset, - ctxt.cur_dev->blksz); + n_blks =DIV_ROUND_UP_ULL (table_size + table_offset, + ctxt.cur_dev->blksz); data_buffer =malloc_cache_aligned (n_blks * ctxt.cur_dev->blksz);
@@ -1388,10 +1388,10 @@ int sqfs_read(const char *filename, void *buf, loff_t offset, loff_t len, goto free_buffer; } - start = frag_entry.start / ctxt.cur_dev->blksz; + start =DIV_ROUND_DOWN_ULL (frag_entry.start, ctxt.cur_dev->blksz); table_size =SQFS_BLOCK_SIZE (frag_entry.size); table_offset = frag_entry.start - (start * ctxt.cur_dev->blksz); - n_blks =DIV_ROUND_UP (table_size + table_offset, ctxt.cur_dev->blksz); + n_blks =DIV_ROUND_UP_ULL (table_size + table_offset, ctxt.cur_dev->blksz); fragment =malloc_cache_aligned (n_blks * ctxt.cur_dev->blksz);
fs/squashfs/sqfs_inode.c +4 -3
@@ -10,7 +10,8 @@#include <stdint.h> #include <stdio.h> #include <stdlib.h> -#include <string.h> +#include <div64.h> +#include <linux/kernel.h> #include "sqfs_decompressor.h" #include "sqfs_filesystem.h"
@@ -68,9 +69,9 @@ int sqfs_inode_size(struct squashfs_base_inode *inode, u32 blk_size)unsigned int blk_list_size;if (fragment ==0xFFFFFFFF ) - blk_list_size =DIV_ROUND_UP (file_size, blk_size); + blk_list_size =DIV_ROUND_UP_ULL (file_size, blk_size);else - blk_list_size = file_size / blk_size; + blk_list_size =DIV_ROUND_DOWN_ULL (file_size, blk_size);return sizeof (*lreg) + blk_list_size *sizeof (u32); }
Signature · 1 line
2.25.1
PATCH v3 2/2 avoid 64-bit divisions on 32-bit
Hi Mauro,
Mauro Condarelli <[email protected]> wrote on Thu, 8 Oct 2020 00:30:21 +0200:
Quoted 1 line
Use macros in
linux/kernel.hto avoid 64-bit divisions.
s/in/from/?
Quoted 9 lines
These divisions are needed to convert from file length (potentially over 32-bit range) to block number, so result and remainder are guaranteed to fit in 32-bit integers.
Some 32bit architectures (notably mipsel) lack an implementation of
__udivdi3()compiler helper function in reduced libgcc.Standard strategy is to use macros and
do_div()inline.
You don't use do_div(), here, is it a leftover or do you mean that this is a generic solution?
Quoted 39 lines
Signed-off-by Mauro Condarelli <[email protected]>---
Changes in v3:
- converted to use DIV_ROUND_(UP|DOWN)_ULL() macros (Miquel Raynal).
- split commits to handle unrelatedKconfigwarning (Thomas Petazzoni).Changes in v2:
- replace division with right shift (Daniel Schwierzeck).
- remove vocore2-specific change (Daniel Schwierzeck).
- add warning toKconfigaboutCONFIG_SYS_MALLOC_LEN(Tom Rini).fs/squashfs/sqfs.c | 32 ++++++++++++++++---------------- fs/squashfs/sqfs_inode.c | 7 ++++--- 2 files changed, 20 insertions(+), 19 deletions(-)fs/squashfs/sqfs.c +2
-2@@ -10,14 +10,14 @@#include <asm/unaligned.h> #include <errno.h> #include <fs.h> -#include <linux/types.h> +#include <linux/kernel.h> +#include <div64.h> #include <linux/byteorder/little_endian.h> #include <linux/byteorder/generic.h> #include <memalign.h> #include <stdlib.h> #include <string.h> #include <squashfs.h> -#include <part.h> #include "sqfs_decompressor.h" #include "sqfs_filesystem.h"
fs/squashfs/sqfs.c static int sqfs_calc_n_blks(__le64 start, __le64 end, u64 *offset) · line 91
Quoted 9 lines
fs/squashfs/sqfs.c +2
-2@@ -85,10 +85,10 @@ static int sqfs_calc_n_blks(__le64 start, __le64 end, u64 *offset)u64 start_, table_size; table_size =le64_to_cpu (end) -le64_to_cpu (start); - start_ =le64_to_cpu (start) / ctxt.cur_dev->blksz; + start_ =DIV_ROUND_DOWN_ULL (le64_to_cpu (start), ctxt.cur_dev->blksz); *offset =le64_to_cpu (start) - (start_ * ctxt.cur_dev->blksz); -return DIV_ROUND_UP (table_size + *offset, ctxt.cur_dev->blksz); +return (table_size + *offset + ctxt.cur_dev->blksz -1 ) >> ctxt.cur_dev->log2blksz;
I don't recall Joao using this kind of structure but I might be wrong. Can you just verify that this is not a leftover from a previous change?
Also, as you state in the commit message, all these divisions serve the same purpose: translating a file length to a block number. I think a helper would be very nice here, something like
sqfs_length_to_block_id(ctxt, length);
Thanks,
Miqu?l
PATCH v3 2/2 avoid 64-bit divisions on 32-bit
Quoted 7 lines · Miquel Raynal
Hi Mauro,
Mauro Condarelli <[email protected]> wrote on Thu, 8 Oct 2020 00:30:21 +0200:
Quoted 1 line
Use macros in
linux/kernel.hto avoid 64-bit divisions.s/in/from/?
My command of English language is far from perfect. I meant those macros are used in Linux kernel. Feel free to rewrite as needed.
Quoted 10 lines
Quoted 8 lines
These divisions are needed to convert from file length (potentially over 32-bit range) to block number, so result and remainder are guaranteed to fit in 32-bit integers.
Some 32bit architectures (notably mipsel) lack an implementation of
__udivdi3()compiler helper function in reduced libgcc.Standard strategy is to use macros and
do_div()inline.You don't use
do_div(), here, is it a leftover or do you mean that this is a generic solution?
I meant I use the macros in SquashFS code, but macros use do_div() inline function to do their job.
Should I rephrase to be more explicit?
Quoted 40 lines
Quoted 40 lines
Signed-off-by Mauro Condarelli <[email protected]>---
Changes in v3:
- converted to use DIV_ROUND_(UP|DOWN)_ULL() macros (Miquel Raynal).
- split commits to handle unrelatedKconfigwarning (Thomas Petazzoni).Changes in v2:
- replace division with right shift (Daniel Schwierzeck).
- remove vocore2-specific change (Daniel Schwierzeck).
- add warning toKconfigaboutCONFIG_SYS_MALLOC_LEN(Tom Rini).fs/squashfs/sqfs.c | 32 ++++++++++++++++---------------- fs/squashfs/sqfs_inode.c | 7 ++++--- 2 files changed, 20 insertions(+), 19 deletions(-)fs/squashfs/sqfs.c +2
-2@@ -10,14 +10,14 @@#include <asm/unaligned.h> #include <errno.h> #include <fs.h> -#include <linux/types.h> +#include <linux/kernel.h> +#include <div64.h> #include <linux/byteorder/little_endian.h> #include <linux/byteorder/generic.h> #include <memalign.h> #include <stdlib.h> #include <string.h> #include <squashfs.h> -#include <part.h> #include "sqfs_decompressor.h" #include "sqfs_filesystem.h" @@ -85,10 +85,10 @@ static int sqfs_calc_n_blks(__le64 start, __le64 end, u64 *offset)u64 start_, table_size;
Quoted 7 lines
fs/squashfs/sqfs.c static int sqfs_calc_n_blks(__le64 start, __le64 end, u64 *offset) · line 91
Quoted 7 lines
fs/squashfs/sqfs.c +2
-2table_size =le64_to_cpu (end) -le64_to_cpu (start); - start_ =le64_to_cpu (start) / ctxt.cur_dev->blksz; + start_ =DIV_ROUND_DOWN_ULL (le64_to_cpu (start), ctxt.cur_dev->blksz); *offset =le64_to_cpu (start) - (start_ * ctxt.cur_dev->blksz); -return DIV_ROUND_UP (table_size + *offset, ctxt.cur_dev->blksz); +return (table_size + *offset + ctxt.cur_dev->blksz -1 ) >> ctxt.cur_dev->log2blksz;
This is definitely a leftover.
It should be:
return DIV_ROUND_UP_ULL(table_size + *offset, ctxt.cur_dev->blksz);
Quoted 2 lines
I don't recall Joao using this kind of structure but I might be wrong. Can you just verify that this is not a leftover from a previous change?
I will correct, retest and resend.
Quoted 5 lines
Also, as you state in the commit message, all these divisions serve the same purpose: translating a file length to a block number. I think a helper would be very nice here, something like
sqfs_length_to_block_id(ctxt, length);
I will consider it.
Quoted 4 lines
Thanks,
Miqu?l
PATCH v3 2/2 avoid 64-bit divisions on 32-bit
In reply to Mauro CondarelliHello,
The commit title lacks a proper prefix, it should start with "fs/squashfs". You confused the prefix of the commit title with the "subject prefix" of format-patch.
fs/squashfs/sqfs.c line 14
Quoted 11 lines · On Thu, 8 Oct 2020 00:30:21 +0200 Mauro Condarelli <[email protected]> wrote:
fs/squashfs/sqfs.c +2
-1@@ -10,14 +10,14 @@#include <asm/unaligned.h> #include <errno.h> #include <fs.h> -#include <linux/types.h> +#include <linux/kernel.h> +#include <div64.h>
Do we need both ?
fs/squashfs/sqfs.c line 20
Quoted 7 lines
fs/squashfs/sqfs.c +0
-1#include <linux/byteorder/little_endian.h> #include <linux/byteorder/generic.h> #include <memalign.h> #include <stdlib.h> #include <string.h> #include <squashfs.h> -#include <part.h>
Is this change related ?
fs/squashfs/sqfs.c static int sqfs_calc_n_blks(__le64 start, __le64 end, u64 *offset) · line 91
Quoted 12 lines
fs/squashfs/sqfs.c +2
-2#include "sqfs_decompressor.h" #include "sqfs_filesystem.h" @@ -85,10 +85,10 @@ static int sqfs_calc_n_blks(__le64 start, __le64 end, u64 *offset)u64 start_, table_size; table_size =le64_to_cpu (end) -le64_to_cpu (start); - start_ =le64_to_cpu (start) / ctxt.cur_dev->blksz; + start_ =DIV_ROUND_DOWN_ULL (le64_to_cpu (start), ctxt.cur_dev->blksz); *offset =le64_to_cpu (start) - (start_ * ctxt.cur_dev->blksz); -return DIV_ROUND_UP (table_size + *offset, ctxt.cur_dev->blksz); +return (table_size + *offset + ctxt.cur_dev->blksz -1 ) >> ctxt.cur_dev->log2blksz;
Why are you not using DIV_ROUND_UP_ULL() here ?
Thanks,
Thomas Petazzoni
Signature · 3 lines
Thomas Petazzoni, CTO, Bootlin Embedded Linux and Kernel engineering https://bootlin.com