Re: how not to write a search algorithm

[Andrew Morton <akpm@zip.com.au>]

William Lee Irwin III wrote:
> 
> Rik van Riel wrote:
> >> Good to hear that you found this one ;)
> 
> On Sun, Aug 04, 2002 at 01:00:14PM -0700, Andrew Morton wrote:
> > The same test panics Alan's kernel with pte_chain oom, so I can't
> > check whether/how well it fixes it :(
> > 2.5 is no better off wrt pte_chain oom, and I expect it'll oops
> > with this test when per-zone-LRUs are implemented.
> > Is there a proposed way of recovering from pte_chain oom?
> 
> Yes. I'll outline my strategy here.
> 
> (1) alter pte-highmem semantics to sleep holding pagetable kmaps
>         (A) reserve some virtual address space for mm-local mappings
>         (B) shove pagetable mappings for "self" and "other" into it

Why?

> (2) separate pte_chain allocation from insertion operations
>         (A) provide a hook to preallocate batches outside the locks
>         (B) convert the allocation to sleeping allocations
>         (C) rearrange pagetable modifications for error recovery and
>                 to call preallocation hooks and pass in reserved state

Seems that simply changing the page_add_ramp() interface to require the
caller to pass in one (err, two) pte_chains would suffice.  The tricky
one is copy_page_range(), which is probably where -ac panics.

I suppose we could hang the pool of pte_chains off task_struct
and have a little "precharge the pte_chains" function.  Gack.

> (3) recovery from pte_chain proliferation by unmapping things on demand
>         (A) per-mm and per-vma accounting of pte_chain space consumption
>         (B) pte_chain memory recovery routine run on-demand
>         (C) budget-based allocation and mm-local pte_chain recycling
> 
> (4) recovery from pagetable proliferation by unmapping files on demand
>         (A) per-mm and per-vma accounting of pagetable space consumption
>         (B) per 3rd-level pagetable accounting of occupancy
>         (C) budget-based pagetable allocation and mm-local recycling
>         (D) pagetable memory recovery routine run on-demand
> 
> (5) recovery from pagetable proliferation by swapping anonymous pagetables
>         (A) per-mm and per-vma accounting of anonymous pagetable space
>         (B) per 3rd-level pagetable accounting of occupancy
>         (C) fault handling for non-present pmd's
>         (D) swap I/O for pagetable pages
>         (E) recovery of anonymous pagetable memory run on-demand
> 
> (6) Assign a global hard limit on the amount of space permissible to
>         allocate for pagetables & pte_chains and enforce it with (1)-(5).

Different problem ;)
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/