Re: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list
From: Rafael J. Wysocki
Date: Sat Jul 30 2005 - 08:13:03 EST
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
> (p-1)x >= n
> 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.
Could we perhaps add your proof to the Michal's patch as a comment,
- 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"
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/