Wonders of paged code sections.

In fact, it does exactly this. Files are not kicked out of cache until there’s memory pressure.

I don’t know how the memory used for file cache is balanced against process memory. I should look that up…

Peter
OSR
@OSRDrivers

> The big question should be how the bug in NDIS.SYS wasn’t discovered by Verifier.

That is a good question. I added the code in question late in the release, in an error path a in a power transition. Apparently my testing did not cover this path while DV was enabled. The static analysis toolset doesn’t seem to catch this either, so I’ll have to investigate that too.

Thanks Jeffrey.

Have I ever told you how great it is to have you contribute here? Your comments are always frank, helpful, cordial, and greatly appreciated.

Peter
OSR
@OSRDrivers

@M M:

As all of the veterans here know, page trimming and replacement as well as cache
balancing algorithm design makes NP hard issues seem trivial.

This is one of those problems that don’t have to have the “best” solution. They need to be good enough, and, the most important, avoid pathological behaviors. Pathological cases usually happen when the programmer tried to make the behavior too smart for its own good. Or overly aggressive.

Avoiding pathological cases is more important than getting the best performance. The “best performance” you can only see in artificial benchmarks, anyway, and when you see an increase in single percents, the users will not notice it, because it’s below noise.

I’ve read about a typical case of misguided optimization. A programmer’s blog on MSDN had an article about converting PDB write component (in LINK) to multi-threaded, because measurements show that it takes significant time. Not once the programmer asked themselves a question: “why would a glorified binary formatting routime be noticeably slow? Could it be because LINK writes a PDB as a compressed file? Could its write pattern cause excessive compression overhead?”

> Have I ever told you how great it is to have you contribute here? Your
comments are always frank, helpful, cordial, and greatly appreciated.

+1 (well, way more than that actually)

Dave Cattley

Why is LRU used for page-replacement? Because at IBM, in the early 1970s,
one researcher asked “What if we knew the furure?” and to that end
instrumented the OS to track page references. Then he took the trace (to
give you an idea of when this was done, the trace was on a magtape) and
built a simulator that could look into the “future” to decide which page
was furthest in the future for a reference, and simulated paging it out.
His overall performance was only about 5% better than LRU. Since the
problem of telling past behavior was easy to solve, and predicting the
future was somwhat more difficult, LRU became the algoritm of choice.

A friend of mine did his PhD dissertation on optimal register allocation
in a compiler. There is a known-best-algoritm for doing this that
involves matrix artithmetic of gigantic binary matrices at each value
creation point. I don’t recall the complexity, but it was certainly
exponential; he used to run overnight batch jobs to compile tiny
subroutines. The compiler we used for production, however, had a
heuristic algorithm whose complexity was linear in the number of value
creations. Like LRU, his algorithm produced code only about 5% better
than the production compiler. So the linear heuristic was “good enough”.

Do we have any similar studies showing aggressive page-out to give
comparable performance to lazy page-out? The experience of many of us
suggests that aggressive page-out produces user-perceptible and serious
degradation of response, particularly when memory is abundant. We already
know that techniques which optimize server performance are different than
techniques that optimize highly-interactive environments; an algorithm
that improves performance under high memory pressure appears to be less
successful when memory pressure is low, and the suggestion seems to be
that the system should be adaptive to its environment rather than trying
to use a single algorithm for 2GB phones running a small number of apps
and 16GB workstations running 50-100 apps.

I am not optimistic; look how many years it took to get GDI to stop
failing when lots of apps needed lots of GDI space, and the same limits
were used for multicore 4GB Win32 machines as had been used for 2GB Win16
machines.
joe

@M M:

>As all of the veterans here know, page trimming and replacement as well
> as cache
balancing algorithm design makes NP hard issues seem trivial.

This is one of those problems that don’t have to have the “best” solution.
They need to be good enough, and, the most important, avoid pathological
behaviors. Pathological cases usually happen when the programmer tried to
make the behavior too smart for its own good. Or overly aggressive.

Avoiding pathological cases is more important than getting the best
performance. The “best performance” you can only see in artificial
benchmarks, anyway, and when you see an increase in single percents, the
users will not notice it, because it’s below noise.

I’ve read about a typical case of misguided optimization. A programmer’s
blog on MSDN had an article about converting PDB write component (in LINK)
to multi-threaded, because measurements show that it takes significant
time. Not once the programmer asked themselves a question: “why would a
glorified binary formatting routime be noticeably slow? Could it be
because LINK writes a PDB as a compressed file? Could its write pattern
cause excessive compression overhead?”


NTDEV is sponsored by OSR

Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev

OSR is HIRING!! See http://www.osr.com/careers

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer

>I am not optimistic; look how many years it took to get GDI to stop failing when lots of apps needed lots of GDI space

I wonder if many years later, when MS finally falls to the same fate as Nokia, Windows will still be resetting the video drivers because “it took too much time”, making your screen go blank at random times.

I WILL tell you that I know the guy who owns the Windows memory Manager, and he’s very, very, clever. In his first few years on the job, he made more improvements to MM than has been made the entire time prior to his arrival. Unlike some other subsystems, over the years the MM has dramatically evolved, improved, and gotten dramatically more sophisticated… All while staying uber-reliable.

So moan about it if you must, and I agree it ain’t perfect, but this guy’s done a far better job than I could have done.

Peter
OSR
@OSRDrivers

It occurred to me that some folks might misinterpret who I was referring to here…

So to be perfectly clear: I’m am referring to Landy Wang, who has artfully evolved the memory manager from its humble origins to the NUMA-aware beast it is today. For the time when it was doing writes paging that were a maximum of 64K to today where you routinely see multi-megabyte writes.

So while you may differ with how a particular policy is implemented, think for a minute: When’s the last time you had a beef with the reliability of MM?

Peter
OSR
@OSRDrivers

Landy’s talks on the memory manager are one of the things I most miss about
the demise of WinHEC. They were one of the talks that disproved the “DDC
lite” label for WinHEC. Of course now we have BUILD, with no content
announcements, and the general description by many folks I know who have
been there as either “PDC lite” or “WinHEC ultra lite”.

Don Burn
Windows Filesystem and Driver Consulting
Website: http://www.windrvr.com
Blog: http://msmvps.com/blogs/WinDrvr

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of xxxxx@osr.com
Sent: Sunday, April 27, 2014 10:07 AM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Wonders of paged code sections.

It occurred to me that some folks might misinterpret who I was referring to
here…

So to be perfectly clear: I’m am referring to Landy Wang, who has artfully
evolved the memory manager from its humble origins to the NUMA-aware beast
it is today. For the time when it was doing writes paging that were a
maximum of 64K to today where you routinely see multi-megabyte writes.

So while you may differ with how a particular policy is implemented, think
for a minute: When’s the last time you had a beef with the reliability of
MM?

Peter
OSR
@OSRDrivers


NTDEV is sponsored by OSR

Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev

OSR is HIRING!! See http://www.osr.com/careers

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at
http://www.osronline.com/page.cfm?name=ListServer

Joe,

Things change very rapidly, and as stated here the owner of the MM is
one of a class, no doubt about that… Here the problem is correctness
( a corner case bug ). We don’t know how much of adaptive approaches
were used, but I suspect already a lot.

In the past analysis of algorithms were mainly based on Offline
approach. MM, scheduler all these are non-deterministic, and tries to
handle hard problem. But in lot of cases, a new approach ( which was
sitting and eating dust for about 20 years) is called - Competitive
Cost Analysis is being used. This is specially for OnIine algorithms.
It is powerful analysis, but when comes down to implementing knowing
the depth of the problems, it is a pure art of an artist, and MM owner
is one such person, really …

-pro

On Sat, Apr 26, 2014 at 8:03 PM, wrote:
> Why is LRU used for page-replacement? Because at IBM, in the early 1970s,
> one researcher asked “What if we knew the furure?” and to that end
> instrumented the OS to track page references. Then he took the trace (to
> give you an idea of when this was done, the trace was on a magtape) and
> built a simulator that could look into the “future” to decide which page
> was furthest in the future for a reference, and simulated paging it out.
> His overall performance was only about 5% better than LRU. Since the
> problem of telling past behavior was easy to solve, and predicting the
> future was somwhat more difficult, LRU became the algoritm of choice.
>
> A friend of mine did his PhD dissertation on optimal register allocation
> in a compiler. There is a known-best-algoritm for doing this that
> involves matrix artithmetic of gigantic binary matrices at each value
> creation point. I don’t recall the complexity, but it was certainly
> exponential; he used to run overnight batch jobs to compile tiny
> subroutines. The compiler we used for production, however, had a
> heuristic algorithm whose complexity was linear in the number of value
> creations. Like LRU, his algorithm produced code only about 5% better
> than the production compiler. So the linear heuristic was “good enough”.
>
> Do we have any similar studies showing aggressive page-out to give
> comparable performance to lazy page-out? The experience of many of us
> suggests that aggressive page-out produces user-perceptible and serious
> degradation of response, particularly when memory is abundant. We already
> know that techniques which optimize server performance are different than
> techniques that optimize highly-interactive environments; an algorithm
> that improves performance under high memory pressure appears to be less
> successful when memory pressure is low, and the suggestion seems to be
> that the system should be adaptive to its environment rather than trying
> to use a single algorithm for 2GB phones running a small number of apps
> and 16GB workstations running 50-100 apps.
>
> I am not optimistic; look how many years it took to get GDI to stop
> failing when lots of apps needed lots of GDI space, and the same limits
> were used for multicore 4GB Win32 machines as had been used for 2GB Win16
> machines.
> joe
>
>> @M M:
>>
>>>As all of the veterans here know, page trimming and replacement as well
>>> as cache
>> balancing algorithm design makes NP hard issues seem trivial.
>>
>> This is one of those problems that don’t have to have the “best” solution.
>> They need to be good enough, and, the most important, avoid pathological
>> behaviors. Pathological cases usually happen when the programmer tried to
>> make the behavior too smart for its own good. Or overly aggressive.
>>
>> Avoiding pathological cases is more important than getting the best
>> performance. The “best performance” you can only see in artificial
>> benchmarks, anyway, and when you see an increase in single percents, the
>> users will not notice it, because it’s below noise.
>>
>> I’ve read about a typical case of misguided optimization. A programmer’s
>> blog on MSDN had an article about converting PDB write component (in LINK)
>> to multi-threaded, because measurements show that it takes significant
>> time. Not once the programmer asked themselves a question: “why would a
>> glorified binary formatting routime be noticeably slow? Could it be
>> because LINK writes a PDB as a compressed file? Could its write pattern
>> cause excessive compression overhead?”
>>
>>
>> —
>> NTDEV is sponsored by OSR
>>
>> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>>
>> OSR is HIRING!! See http://www.osr.com/careers
>>
>> For our schedule of WDF, WDM, debugging and other seminars visit:
>> http://www.osr.com/seminars
>>
>> To unsubscribe, visit the List Server section of OSR Online at
>> http://www.osronline.com/page.cfm?name=ListServer
>>
>
>
>
> —
> NTDEV is sponsored by OSR
>
> Visit the list at: http://www.osronline.com/showlists.cfm?list=ntdev
>
> OSR is HIRING!! See http://www.osr.com/careers
>
> For our schedule of WDF, WDM, debugging and other seminars visit:
> http://www.osr.com/seminars
>
> To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer

>So while you may differ with how a particular policy is implemented, think for a minute: When’s the last time you had a beef with the reliability of MM?

The MM can be perfectly robust and reliable, but at the same time suffer of obscessive-compulsive file data retentiveness. It’s only been recently enough (Vista+) that cache policy for USB drives become to flush dirty pages soon enough. In Win2003 (God forbid I mention it) I was very surprized to be getting “data cannot be flushed” warnings on “unsafe” unplug of a USB stick, EVEN IF NO FILE WERE MODIFIED.

Not to split hairs, but the file cache is managed by the cache manager (CC) not the memory manager (MM). Two intertwined but very different modules, owned by two different people in two entirely separate groups (well, when last I checked they were in different groups anyways – unsurprisingly, CC was owned by the file systems people).

Peter
OSR
@OSRDrivers

Peter Viscarola (OSR) wrote:

So while you may differ with how a particular policy is
implemented, think for a minute: When’s the last time
you had a beef with the reliability of MM?

Well, there was that crash in MmGetSystemRoutineAddress…

> -----Original Message-----

From: xxxxx@lists.osr.com [mailto:bounce-556161-
xxxxx@lists.osr.com] On Behalf Of xxxxx@gmail.com
Sent: Sunday, April 27, 2014 4:54 PM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Wonders of paged code sections.

Peter Viscarola (OSR) wrote:

> So while you may differ with how a particular policy is implemented,
> think for a minute: When’s the last time you had a beef with the
> reliability of MM?

Well, there was that crash in MmGetSystemRoutineAddress…

Thanks for illustrating Peter’s point. That was a lot of years ago.

Phil

Not speaking for LogRhythm
Phil Barila | Senior Software Engineer
720.881.5364 (w)

The Security Intelligence Company
A LEADER 2013 SIEM Magic Quadrant
Perfect 5-Star Rating in SC Magazine for 5 Consecutive Years

>Well, there was that crash in MmGetSystemRoutineAddress…

In all fairness, the only thing that links it to MM is the Mm* prefix.

Cc will unmap the file (putting pages on the standby list) when the app closes its handle. If the app is reading a large file sequentially Cc will also unmap each region after it’s been accessed.

So a typical file indexer kind of app should not be able to inflate the system cache to the point where the OS has to trim processes. What it can do is dump a lot of pages onto the standby list, potentially pushing other more useful pages from memory.

To avoid that, an app that wants to be a good citizen can lower its page priority via SetThreadInformation, or by entering background mode (THREAD_MODE_BACKGROUND etc). In some cases the system can do this automatically, but if you want to reduce the impact on the rest of the system it’s better to be explicit.

Using non-cached IO in scenarios like file indexing can actually make things worse because NTFS will attempt to purge cached files from memory when they are opened for non-cached access.

TL;DR:

If you need to scan a lot of files and you don’t know who else might be using them:

  1. Open files for cached access (or memory map them).
  2. Supply appropriate hints (e.g. FILE_FLAG_SEQUENTIAL_SCAN if reading sequentially).
  3. Lower your page priority via SetThreadInformation or the background mode API.

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of xxxxx@broadcom.com
Sent: Saturday, April 26, 2014 9:02 AM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Wonders of paged code sections.

Windows file cache, also, seems to try to keep files cached indefinitely and without ever trying to limit cache size (in the old good times, Win9x had registry-specified cache limit, though). When some crappy file scanner/indexer is opening lots of files in cached mode (or, equally bad, opens them as file sections), the executable pages seem to fall a victim of that fast.

That sounds very much like the driver bug that was just discussed here (the one that triggers bugcheck 1A/0x61946 in win8+):

http://www.osronline.com/showThread.cfm?link=255401

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of xxxxx@broadcom.com
Sent: Sunday, April 27, 2014 10:43 AM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Wonders of paged code sections.

<…>
In Win2003 (God forbid I mention it) I was very surprized to be getting “data cannot be flushed” warnings on “unsafe” unplug of a USB stick, EVEN IF NO FILE WERE MODIFIED.

>Cc will unmap the file (putting pages on the standby list) when the app closes its handle.

What if a file mapping object doesn’t have open handles to its FILE_OBJECT? Like all loaded EXEs and DLLs do? does it dis-advantage it against currently open files?

Cc doesn’t know anything about loaded EXEs and DLLs.

Cc maps views of files accessed via ReadFile/WriteFile. These views are in the system VA space, and Cc decides when to unmap them.

User programs can also map views, via MapViewFile/NtMapViewOfSection (LoadLibrary internally calls NtMapViewOfSection). These views are in the VA space of the process, and the process decides when to unmap them.

Orthogonally to all that, Mm can decide to trim active pages from a mapped view. When it decides which pages to trim first it looks at various things, but whether the file has any open handles is not one of them.

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of xxxxx@broadcom.com
Sent: Tuesday, April 29, 2014 4:29 PM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Wonders of paged code sections.

Cc will unmap the file (putting pages on the standby list) when the app closes its handle.

What if a file mapping object doesn’t have open handles to its FILE_OBJECT? Like all loaded EXEs and DLLs do? does it dis-advantage it against currently open files?