[PATCH] swsusp: simpler calculation of number of pages in PBE list

[PATCH] swsusp: simpler calculation of number of pages in PBE list

[Michal Schmidt]

[-- Attachment #1: Type: text/plain, Size: 251 bytes --]

The function calc_nr uses an iterative algorithm to calculate the number 
of pages needed for the image and the pagedir. Exactly the same result 
can be obtained with a one-line expression.

Signed-off-by: Michal Schmidt <xschmi00@stud.feec.vutbr.cz>

[-- Attachment #2: swsusp-simpler-calc_nr.diff --]
[-- Type: text/x-patch, Size: 690 bytes --]

diff -Nurp -X dontdiff.new linux-mm/kernel/power/swsusp.c linux-mm.mich/kernel/power/swsusp.c
--- linux-mm/kernel/power/swsusp.c	2005-07-28 13:57:53.000000000 +0200
+++ linux-mm.mich/kernel/power/swsusp.c	2005-07-29 21:01:46.000000000 +0200
@@ -737,18 +737,7 @@ static void copy_data_pages(void)
 
 static int calc_nr(int nr_copy)
 {
-	int extra = 0;
-	int mod = !!(nr_copy % PBES_PER_PAGE);
-	int diff = (nr_copy / PBES_PER_PAGE) + mod;
-
-	do {
-		extra += diff;
-		nr_copy += diff;
-		mod = !!(nr_copy % PBES_PER_PAGE);
-		diff = (nr_copy / PBES_PER_PAGE) + mod - extra;
-	} while (diff > 0);
-
-	return nr_copy;
+	return nr_copy + (nr_copy+PBES_PER_PAGE-2)/(PBES_PER_PAGE-1);
 }
 
 /**

Re: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list

[Rafael J. Wysocki]

On Friday, 29 of July 2005 21:46, Michal Schmidt wrote:
> The function calc_nr uses an iterative algorithm to calculate the number 
> of pages needed for the image and the pagedir. Exactly the same result 
> can be obtained with a one-line expression.

Could you please post the proof?

Rafael


-- 
- Would you tell me, please, which way I ought to go from here?
- That depends a good deal on where you want to get to.
		-- Lewis Carroll "Alice's Adventures in Wonderland"

Re: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list

[Michal Schmidt]

[-- Attachment #1: Type: text/plain, Size: 1261 bytes --]

Rafael J. Wysocki wrote:
> On Friday, 29 of July 2005 21:46, Michal Schmidt wrote:
> 
>>The function calc_nr uses an iterative algorithm to calculate the number 
>>of pages needed for the image and the pagedir. Exactly the same result 
>>can be obtained with a one-line expression.
> 
> 
> Could you please post the proof?
> 
> Rafael

OK, attached is a proof-by-brute-force program. It compares the results 
of the original function and the simplified one.

This is its output:

$ ./calc_nr2
checked 0 ...
checked 100000000 ...
checked 200000000 ...
checked 300000000 ...
checked 400000000 ...
checked 500000000 ...
checked 600000000 ...
checked 700000000 ...
checked 800000000 ...
checked 900000000 ...
checked 1000000000 ...
checked 1100000000 ...
checked 1200000000 ...
checked 1300000000 ...
checked 1400000000 ...
checked 1500000000 ...
checked 1600000000 ...
checked 1700000000 ...
checked 1800000000 ...
checked 1900000000 ...
checked 2000000000 ...
checked 2100000000 ...
First difference at 2130706433:  -2147483646 x -2147483647

It means that the two functions give the same results for sensible 
values of the input argument.
They results only differ when they overflow into negative values. At 
this point both of the results are useless.

Michal

[-- Attachment #2: calc_nr2.c --]
[-- Type: text/x-csrc, Size: 986 bytes --]

#include <stdio.h>
#include <limits.h>

typedef struct {
	unsigned long val;
} swp_entry_t;

typedef struct pbe {
	unsigned long address;
	unsigned long orig_address;
	swp_entry_t swap_address;
	struct pbe *next;
} suspend_pagedir_t;

#define PAGE_SIZE 4096
#define PBES_PER_PAGE (PAGE_SIZE/sizeof(struct pbe))

static int calc_nr_orig(int nr_copy)
{
        int extra = 0;
	int mod = !!(nr_copy % PBES_PER_PAGE);
	int diff = (nr_copy / PBES_PER_PAGE) + mod;

	do {
		extra += diff;
		nr_copy += diff;
		mod = !!(nr_copy % PBES_PER_PAGE);
		diff = (nr_copy / PBES_PER_PAGE) + mod - extra;
	} while (diff > 0);
	
	return nr_copy;
}

static int calc_nr(int nr_copy)
{
	return nr_copy + (nr_copy+PBES_PER_PAGE-2)/(PBES_PER_PAGE-1);
}

int main()
{
	int i;
	for (i=0; i>=0; i++) {
		if (i%100000000 == 0)
			printf("checked %d ...\n", i);
		if (calc_nr(i) != calc_nr_orig(i)) {
			printf("First difference at %d:  %d x %d\n", i, calc_nr(i), calc_nr_orig(i));
			break;
		}
	}
	return 0;
}

Re: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list

[Rafael J. Wysocki]

On Friday, 29 of July 2005 23:14, Michal Schmidt wrote:
> Rafael J. Wysocki wrote:
> > On Friday, 29 of July 2005 21:46, Michal Schmidt wrote:
> > 
> >>The function calc_nr uses an iterative algorithm to calculate the number 
> >>of pages needed for the image and the pagedir. Exactly the same result 
> >>can be obtained with a one-line expression.
> > 
> > 
> > Could you please post the proof?
> > 
> > Rafael
> 
> OK, attached is a proof-by-brute-force program. It compares the results 
> of the original function and the simplified one.
> 
> This is its output:
> 
> $ ./calc_nr2
> checked 0 ...
> checked 100000000 ...
> checked 200000000 ...
> checked 300000000 ...
> checked 400000000 ...
> checked 500000000 ...
> checked 600000000 ...
> checked 700000000 ...
> checked 800000000 ...
> checked 900000000 ...
> checked 1000000000 ...
> checked 1100000000 ...
> checked 1200000000 ...
> checked 1300000000 ...
> checked 1400000000 ...
> checked 1500000000 ...
> checked 1600000000 ...
> checked 1700000000 ...
> checked 1800000000 ...
> checked 1900000000 ...
> checked 2000000000 ...
> checked 2100000000 ...
> First difference at 2130706433:  -2147483646 x -2147483647
> 
> It means that the two functions give the same results for sensible 
> values of the input argument.
> They results only differ when they overflow into negative values. At 
> this point both of the results are useless.

Thanks, fine. :-)

Greets,
Rafael


-- 
- Would you tell me, please, which way I ought to go from here?
- That depends a good deal on where you want to get to.
		-- Lewis Carroll "Alice's Adventures in Wonderland"

Re: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list

[Alan Stern]

On Fri, 29 Jul 2005, Michal Schmidt wrote:

> Rafael J. Wysocki wrote:
> > On Friday, 29 of July 2005 21:46, Michal Schmidt wrote:
> > 
> >>The function calc_nr uses an iterative algorithm to calculate the number 
> >>of pages needed for the image and the pagedir. Exactly the same result 
> >>can be obtained with a one-line expression.
> > 
> > 
> > Could you please post the proof?
> > 
> > Rafael
> 
> OK, attached is a proof-by-brute-force program. It compares the results 
> of the original function and the simplified one.

Here's a more general proof.

As I understand it, calc_nr is given nr_copy, the number of data pages
that need to be written out, and it has to return the number of pages
needed to hold the image data plus a bunch of PBE pagedir indexes, where
each page gets one index (and pages containing PBEs need their own indexes
as well).

For brevity, let n = nr_copy, let p = PBES_PER_PAGE, and let x be the 
number of pagdir pages needed.  Since each page can hold p PBEs, there 
will be room to store px PBEs.  The total number of pages is n + x, so 
the routine needs to find the smallest value of x for which

	px >= n + x

or

	(p-1)x >= n

or

	x >= n / (p-1).

The obvious solution is

	x = ceiling(n / (p-1)),

so calc_nr should return n + ceiling(n / (p-1)), which is exactly what 
Michal's patch computes.

Alan Stern

Re: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list

[Rafael J. Wysocki]

On Saturday, 30 of July 2005 03:35, Alan Stern wrote:
> On Fri, 29 Jul 2005, Michal Schmidt wrote:
> 
> > Rafael J. Wysocki wrote:
> > > On Friday, 29 of July 2005 21:46, Michal Schmidt wrote:
> > > 
> > >>The function calc_nr uses an iterative algorithm to calculate the number 
> > >>of pages needed for the image and the pagedir. Exactly the same result 
> > >>can be obtained with a one-line expression.
> > > 
> > > 
> > > Could you please post the proof?
> > > 
> > > Rafael
> > 
> > OK, attached is a proof-by-brute-force program. It compares the results 
> > of the original function and the simplified one.
> 
> Here's a more general proof.
> 
> As I understand it, calc_nr is given nr_copy, the number of data pages
> that need to be written out, and it has to return the number of pages
> needed to hold the image data plus a bunch of PBE pagedir indexes, where
> each page gets one index (and pages containing PBEs need their own indexes
> as well).
> 
> For brevity, let n = nr_copy, let p = PBES_PER_PAGE, and let x be the 
> number of pagdir pages needed.  Since each page can hold p PBEs, there 
> will be room to store px PBEs.  The total number of pages is n + x, so 
> the routine needs to find the smallest value of x for which
> 
> 	px >= n + x
> 
> or
> 
> 	(p-1)x >= n
> 
> or
> 
> 	x >= n / (p-1).
> 
> The obvious solution is
> 
> 	x = ceiling(n / (p-1)),
> 
> so calc_nr should return n + ceiling(n / (p-1)), which is exactly what 
> Michal's patch computes.

Nice. :-)

Could we perhaps add your proof to the Michal's patch as a comment,
for reference?

Rafael


-- 
- Would you tell me, please, which way I ought to go from here?
- That depends a good deal on where you want to get to.
		-- Lewis Carroll "Alice's Adventures in Wonderland"

Re: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list

[Pavel Machek]

Hi!

> > 	px >= n + x
> > 
> > or
> > 
> > 	(p-1)x >= n
> > 
> > or
> > 
> > 	x >= n / (p-1).
> > 
> > The obvious solution is
> > 
> > 	x = ceiling(n / (p-1)),
> > 
> > so calc_nr should return n + ceiling(n / (p-1)), which is exactly what 
> > Michal's patch computes.
> 
> Nice. :-)
> 
> Could we perhaps add your proof to the Michal's patch as a comment,
> for reference?

No, thanks. It only proves that it is equivalent to old code, but says
nothing about quality of code, and we really do not want to keep old
code around.
								Pavel
-- 
teflon -- maybe it is a trademark, but it should not be.

Re: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list

[Rafael J. Wysocki]

Hi,

On Saturday, 30 of July 2005 15:13, Pavel Machek wrote:
> Hi!
> 
> > > 	px >= n + x
> > > 
> > > or
> > > 
> > > 	(p-1)x >= n
> > > 
> > > or
> > > 
> > > 	x >= n / (p-1).
> > > 
> > > The obvious solution is
> > > 
> > > 	x = ceiling(n / (p-1)),
> > > 
> > > so calc_nr should return n + ceiling(n / (p-1)), which is exactly what 
> > > Michal's patch computes.
> > 
> > Nice. :-)
> > 
> > Could we perhaps add your proof to the Michal's patch as a comment,
> > for reference?
> 
> No, thanks. It only proves that it is equivalent to old code, but says
> nothing about quality of code, and we really do not want to keep old
> code around.

IMHO it rather says that the formula is OK and would save some time to
people reading the code for the _first_ time and trying to understand it,
but you decide. :-)

Greets,
Rafael


-- 
- Would you tell me, please, which way I ought to go from here?
- That depends a good deal on where you want to get to.
		-- Lewis Carroll "Alice's Adventures in Wonderland"

Re: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list

[Alan Stern]

On Sat, 30 Jul 2005, Rafael J. Wysocki wrote:

> Hi,
> 
> On Saturday, 30 of July 2005 15:13, Pavel Machek wrote:
> > Hi!
> > 
> > > > 	px >= n + x
> > > > 
> > > > or
> > > > 
> > > > 	(p-1)x >= n
> > > > 
> > > > or
> > > > 
> > > > 	x >= n / (p-1).
> > > > 
> > > > The obvious solution is
> > > > 
> > > > 	x = ceiling(n / (p-1)),
> > > > 
> > > > so calc_nr should return n + ceiling(n / (p-1)), which is exactly what 
> > > > Michal's patch computes.
> > > 
> > > Nice. :-)
> > > 
> > > Could we perhaps add your proof to the Michal's patch as a comment,
> > > for reference?
> > 
> > No, thanks. It only proves that it is equivalent to old code, but says
> > nothing about quality of code, and we really do not want to keep old
> > code around.
> 
> IMHO it rather says that the formula is OK and would save some time to
> people reading the code for the _first_ time and trying to understand it,
> but you decide. :-)

It's up to you whether or not to include the proof as a comment -- you 
have my permission and my sign-off:

Signed-off-by: Alan Stern <stern@rowland.harvard.edu>

Alan Stern

Re: [PATCH] swsusp: simpler calculation of number of pages in PBE list

[Pavel Machek]

On Pá 29-07-05 21:46:40, Michal Schmidt wrote:
> The function calc_nr uses an iterative algorithm to calculate the number 
> of pages needed for the image and the pagedir. Exactly the same result 
> can be obtained with a one-line expression.
> 
> Signed-off-by: Michal Schmidt <xschmi00@stud.feec.vutbr.cz>

Thanks, applied.

> diff -Nurp -X dontdiff.new linux-mm/kernel/power/swsusp.c linux-mm.mich/kernel/power/swsusp.c
> --- linux-mm/kernel/power/swsusp.c	2005-07-28 13:57:53.000000000 +0200
> +++ linux-mm.mich/kernel/power/swsusp.c	2005-07-29 21:01:46.000000000 +0200
> @@ -737,18 +737,7 @@ static void copy_data_pages(void)
>  
>  static int calc_nr(int nr_copy)
>  {
> -	int extra = 0;
> -	int mod = !!(nr_copy % PBES_PER_PAGE);
> -	int diff = (nr_copy / PBES_PER_PAGE) + mod;
> -
> -	do {
> -		extra += diff;
> -		nr_copy += diff;
> -		mod = !!(nr_copy % PBES_PER_PAGE);
> -		diff = (nr_copy / PBES_PER_PAGE) + mod - extra;
> -	} while (diff > 0);
> -
> -	return nr_copy;
> +	return nr_copy + (nr_copy+PBES_PER_PAGE-2)/(PBES_PER_PAGE-1);
>  }
>  
>  /**


-- 
teflon -- maybe it is a trademark, but it should not be.