[fs/squashfs PATCH v3 0/2] fs/squashfs: avoid 64-bit divisions on 32-bit

[fs/squashfs PATCH v3 0/2] fs/squashfs: avoid 64-bit divisions on 32-bit

[Mauro Condarelli]

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(-)

-- 
2.25.1

[fs/squashfs PATCH v3 1/2] Add warning for dynamic memory usage.

[Mauro Condarelli]

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.

Signed-off-by: Mauro Condarelli <mc5686@mclink.it>
---

(no changes since v1)

 fs/squashfs/Kconfig | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/fs/squashfs/Kconfig b/fs/squashfs/Kconfig
index 54ab1618f1..7c3f83d007 100644
--- a/fs/squashfs/Kconfig
+++ b/fs/squashfs/Kconfig
@@ -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.
-- 
2.25.1

[fs/squashfs PATCH v3 1/2] Add warning for dynamic memory usage.

[Miquel Raynal]

Hi Mauro,

Mauro Condarelli <mc5686@mclink.it> wrote on Thu,  8 Oct 2020 00:30:20
+0200:

> 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.

Nit: s/ada/add/ s/in help/in the help/?

Besides that,

Reviewed-by: Miquel Raynal <miquel.raynal@bootlin.com>

> 
> Signed-off-by: Mauro Condarelli <mc5686@mclink.it>
> ---
> 
> (no changes since v1)
> 
>  fs/squashfs/Kconfig | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/fs/squashfs/Kconfig b/fs/squashfs/Kconfig
> index 54ab1618f1..7c3f83d007 100644
> --- a/fs/squashfs/Kconfig
> +++ b/fs/squashfs/Kconfig
> @@ -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

[fs/squashfs PATCH v3 2/2] avoid 64-bit divisions on 32-bit

[Mauro Condarelli]

Use 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.

Signed-off-by: Mauro Condarelli <mc5686@mclink.it>
---

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(-)

diff --git a/fs/squashfs/sqfs.c b/fs/squashfs/sqfs.c
index 15208b4dab..ef9f5e3449 100644
--- a/fs/squashfs/sqfs.c
+++ b/fs/squashfs/sqfs.c
@@ -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);
 
diff --git a/fs/squashfs/sqfs_inode.c b/fs/squashfs/sqfs_inode.c
index 14d70cf678..43cd516468 100644
--- a/fs/squashfs/sqfs_inode.c
+++ b/fs/squashfs/sqfs_inode.c
@@ -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);
 	}
-- 
2.25.1

[fs/squashfs PATCH v3 2/2] avoid 64-bit divisions on 32-bit

[Miquel Raynal]

Hi Mauro,

Mauro Condarelli <mc5686@mclink.it> wrote on Thu,  8 Oct 2020 00:30:21
+0200:

> Use macros in linux/kernel.h to avoid 64-bit divisions.

s/in/from/?

> 
> 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?

> 
> Signed-off-by: Mauro Condarelli <mc5686@mclink.it>
> ---
> 
> 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(-)
> 
> diff --git a/fs/squashfs/sqfs.c b/fs/squashfs/sqfs.c
> index 15208b4dab..ef9f5e3449 100644
> --- a/fs/squashfs/sqfs.c
> +++ b/fs/squashfs/sqfs.c
> @@ -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;

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

[fs/squashfs PATCH v3 2/2] avoid 64-bit divisions on 32-bit

[Mauro Condarelli]

On 10/8/20 9:34 AM, Miquel Raynal wrote:
> Hi Mauro,
>
> Mauro Condarelli <mc5686@mclink.it> wrote on Thu,  8 Oct 2020 00:30:21
> +0200:
>
>> Use macros in linux/kernel.h to 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.

>> 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?


>> Signed-off-by: Mauro Condarelli <mc5686@mclink.it>
>> ---
>>
>> 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(-)
>>
>> diff --git a/fs/squashfs/sqfs.c b/fs/squashfs/sqfs.c
>> index 15208b4dab..ef9f5e3449 100644
>> --- a/fs/squashfs/sqfs.c
>> +++ b/fs/squashfs/sqfs.c
>> @@ -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;
This is definitely a leftover.
It should be:

          return DIV_ROUND_UP_ULL(table_size + *offset, ctxt.cur_dev->blksz);

> 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.

> 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.

>
> Thanks,
> Miqu?l
>

[fs/squashfs PATCH v3 2/2] avoid 64-bit divisions on 32-bit

[Thomas Petazzoni]

Hello,

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.

On Thu,  8 Oct 2020 00:30:21 +0200
Mauro Condarelli <mc5686@mclink.it> wrote:

> diff --git a/fs/squashfs/sqfs.c b/fs/squashfs/sqfs.c
> index 15208b4dab..ef9f5e3449 100644
> --- a/fs/squashfs/sqfs.c
> +++ b/fs/squashfs/sqfs.c
> @@ -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 ?

>  #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 ?

>  #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
-- 
Thomas Petazzoni, CTO, Bootlin
Embedded Linux and Kernel engineering
https://bootlin.com