lkml.org 
[lkml]   [2005]   [Jul]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    SubjectRe: [linux-pm] [PATCH] swsusp: simpler calculation of number of pages in PBE list
    Date
    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"
    -
    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 15:15    [W:0.024 / U:5.792 seconds]
    ©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site