lkml.org 
[lkml]   [2005]   [Jul]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list
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

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-07-30 03:41    [W:0.083 / U:0.248 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site