8
\$\begingroup\$

I've noticed in the initialization process of the original Quake the following function is called.

volatile int sys_checksum;

//  **lots of code**

void Sys_PageIn(void *ptr, int size)
{
    byte *x;
    int j,m,n;
//touch all memory to make sure its there.  The 16-page skip is to
//keep Win 95 from thinking we're trying to page ourselves in (we are
//doing that, of course, but there's no reason we shouldn't)
    x = (byte *)ptr;

    for (n=0 ; n<4 ; n++)
    {
        for (m=0; m<(size - 16 * 0x1000) ; m += 4)
        {
            sys_checksum += *(int *)&x[m];
            sys_checksum += *(int *)&x[m + 16 * 0x10000];
        }
    }
}

I think I'm just not familiar enough with paging to understand this function. the void* ptr passed to the function is a recently malloc()'d piece of memory that is size bytes big. This is the whole function - j is an unreferenced variable. My best guess is that the volatile int sys_checksum is forcing the system to physically read all of the space that was just malloc()'d, perhaps to ensure that these spaces exist in virtual memory? Is this right? And why would someone do this? Is it for some antiquated Win95 reason?

\$\endgroup\$

3 Answers 3

1
\$\begingroup\$

Raymond Chen answers this directly in a later post on his blog The Old New Thing (Maximus Minimius had the right source it turns out just 3 years too early for a direct explanation): https://blogs.msdn.microsoft.com/oldnewthing/20151111-00/?p=91972

What this code does is access the memory block specified by the ptr and size parameters in an unusual pattern: It reads byte zero, then the byte at an offset of 16 pages, then byte one, then a byte at an offset of 16 pages plus one, and so on, alternating between a byte and its counterpart 16 pages ahead.

This specific access pattern in Windows 95 defeated the "sequential memory scan" detection algorithm.

Recall that computers in the Windows 95 era had 4MB of RAM. Suppose you were working in a document for a long time. Finally, you're done, and you close the window or minimize it. Boom, now your desktop is visible and the wallpaper bitmap needs to be paged in. If your screen is 1024 × 768 at 16 bits per pixel, that comes out to 1.5MB of memory. Paging in 1.5MB of memory means for the bitmap means kicking out 1.5MB of memory being used for other stuff, and that's a lot of memory for a machine that has only 4MB to work with (especially since a lot of that 4MB belongs to stuff that isn't eligible for being paged out). The phenomenon we saw was that repainting your desktop would flush out most of your memory.

And then the next thing you do is probably launch a new application, which will cover the wallpaper, so the wallpaper memory isn't going to be needed any more. So we basically purged all the memory in your system in order to handle a huge block of memory that got accessed only once.

The trick that Windows 95 used was to watch your pattern of page faults, and if it saw that you were doing sequential memory access, it started marking the memory 16 pages behind the current access as not recently accessed. In the case of a straight sequential scan, this means that the entire buffer cycles through a 64KB window of memory, regardless of the buffer size. With this trick, a 4MB buffer ends up consuming only 64KB of memory, as opposed to using all the memory in your system.

The Sys_Page­In function specifically defeates the sequential-scan detector by intentionally going back 16 pages and accessing the page again. This causes it to be marked recently used, counteracting the not recently used that the sequential-scan detector had done. Result: The memory pages are all marked recently used and are no longer prime candidates for being paged out.

\$\endgroup\$
6
\$\begingroup\$

Your guess is basically correct, and it's being done as an optimization (most likely; I can only speculate of course as I did not write the code).

While an application in Windows appears to have full access to the entire range of RAM in the machine (or at least the range reported to it by the OS), in practice the OS is virtualizing an application's access to the actual physical memory and will store regions (pages) of virtual memory to disk when it needs to. The process of transferring these regions from disk to physical RAM is often called "paging in" (when going from disk to RAM) or "paging out" (when going from RAM to disk).

Disk IO is slow, compared to RAM, and so avoiding paging is ideal for achieving maximum performance. The intent of this function appears to be to attempt to minimize paging during the lifetime of the program by forcing the OS to page all the memory in at the start of the program -- the forcing is accomplished by trying to read from all the memory.

Presumably Windows 95 had some kind of code to detect and stop this behavior, which the comment suggests is being circumvented by reading the memory in a particular pattern. It makes sense that the OS would do this, because forcing a complete page-in like this will force other processes memory to be paged out to disk, probably slowing them down.

It can be argued that this is acceptable behavior for a game because a user will generally only run the game and not try to do a lot of multitasking while the game is up, so sacrificing the performance of other processes that may be running isn't that evil.

Some other notes:

  • This sort of thing is not likely to work nearly as well today as it probably did back in Windows 95. The nature of OS schedulers has changed quite a lot since then, so it's not necessarily a technique I would suggest you adopt unless you have compelling profiler data and metrics to support the fact that your attempt is a benefit.

  • volatile is a hint to the implementation to avoid aggressive optimization of an object so declared because that object might change via means the implementation cannot be expected to predict. In other words, it's like a "don't optimize me" flag. This way the compiler, even if it realizes that the variable essentially unused in any significant fashion, will not optimize out the reads from memory into that variable as part of its optimization pass.

  • j being unused is probably just an oversight.

\$\endgroup\$
0
\$\begingroup\$

Resurrecting this, I noticed this entry on Raymond Chen's site recently: Link

Why am I in the Quake credits? I don't remember what it was that I did specifically...the advice I gave was almost certainly related to memory management and swapping.

This indicates that there is at least a decent possibility that this function is the result of Raymond's advice (and when Raymond Chen says "you need to do this" there is at least a decent possibility that he is right).

It's easy to forget nowadays, but back in 1996 the average gamer PC would have had maybe 16mb of RAM, max, and Quake was an absolute monster of a program. In those days hard disks used to grind away relentlessly due to paging, and pulling in all allocated memory in this manner would have (at least) helped prevent the page file from having to be touched at runtime, which could have led to a stall of anything up to a second or more.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .