swsusp: simpler calculation of number of pages in PBE list
Subsystems (2)
PATCH 1/1 swsusp: simpler calculation of number of pages in PBE list
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.
kernel/power/swsusp.c +1 -12
@@ -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 ); }/**
Quoted 3 lines · Michal Schmidt
The function
calc_nruses 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
Signature · 3 lines
- 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"
Quoted 8 lines · Rafael J. Wysocki
Quoted 1 line · Michal Schmidt
The function
calc_nruses 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
#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;
}Quoted 42 lines · Michal Schmidt
Quoted 10 lines · Rafael J. Wysocki
Quoted 3 lines · Michal Schmidt
The function
calc_nruses 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
Quoted 4 lines
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
Signature · 3 lines
- 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"
Quoted 8 lines · Michal Schmidt
Quoted 7 lines · Rafael J. Wysocki
Quoted 3 lines · Michal Schmidt
The function
calc_nruses 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.
Quoted 6 lines
Quoted 3 lines
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
Quoted 38 lines · Alan Stern
Quoted 8 lines · Michal Schmidt
Quoted 7 lines · Rafael J. Wysocki
Quoted 3 lines · Michal Schmidt
The function
calc_nruses 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.Quoted 6 lines
Quoted 3 lines
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_nris givennr_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 whichpx >= n + xor
(p-1)x >= nor
Quoted 8 lines
x >= n / (p-1).The obvious solution is
x = ceiling(n / (p-1)),so
calc_nrshould 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
Signature · 3 lines
- 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"
Hi!
Quoted 14 lines
Quoted 14 lines
px >= n + xor
(p-1)x >= nor
x >= n / (p-1).The obvious solution is
x = ceiling(n / (p-1)),
Quoted 7 lines
Quoted 2 lines
so
calc_nrshould 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
Signature · 1 line
teflon -- maybe it is a trademark, but it should not be.
Hi,
Quoted 19 lines · Pavel Machek
Hi!
Quoted 17 lines
Quoted 16 lines
px >= n + xor
(p-1)x >= nor
x >= n / (p-1).The obvious solution is
x = ceiling(n / (p-1)),so
calc_nrshould return n + ceiling(n / (p-1)), which is exactly what Michal's patch computes.
Quoted 8 lines
Quoted 4 lines
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
Signature · 3 lines
- 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"
Quoted 27 lines · Rafael J. Wysocki
Hi,
Quoted 24 lines · Pavel Machek
Hi!
Quoted 21 lines
Quoted 8 lines
px >= n + xor
(p-1)x >= nor
Quoted 8 lines
x >= n / (p-1).The obvious solution is
x = ceiling(n / (p-1)),so
calc_nrshould 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?
Quoted 7 lines
Quoted 3 lines
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:
Alan Stern
Pavel Machek
AppliedQuoted 5 lines · Michal Schmidt
The function
calc_nruses 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 <[email protected]>
Thanks, applied.
Quoted 23 lines
diff -Nurp -X dontdiff.new
linux-mm/kernel/power/swsusp.clinux-mm.mich/kernel/power/swsusp.ckernel/power/swsusp.c +1
-12@@ -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 ); }/**
Signature · 1 line
teflon -- maybe it is a trademark, but it should not be.