Demand Paging

In last week's lesson on paging, we saw the memory map of Neovim running on a 32-bit Raspberry Pi Zero. At the top of the diagram (the bottom of memory) was the code for Neovim, all 2.4 MB of it…

The Case for Demand Paging

Here's actual data from my loading Neovim on a Raspberry Pi Zero. The light green shows code pages that were never used at all. The darker colored pages are colored on a gradient showing when they were found to be needed, with teal being the first pages needed and brown being the last pages loaded (you can also hover over any page to see when it was needed).

Demand Paging Defined

In the previous lesson we mentioned zero-filled memory, where the operating system can lie to the program and claim it has allocated memory when it hasn't done so yet. The page table entry for the page is marked as not present and the CPU generates a page fault when the program tries to access the page. At that point, the operating system can allocate a page of memory and fill it with zeros, then update the page table entry to point to the new page.

We can use exactly the same trick to load code pages on demand. Code is only loaded when the program tries to run code or access data in that page. This is called demand paging.

Architectural Corner Cases

Getting a CPU to do paging correctly is a bit more of a challenge than you might think. We'll look at a CISC feature of the Motorola 68000 CPU that caused a problem with demand paging.

Post-Increment Addressing

One really common pattern in coding is filling an array,

for (int* ip = array; ip < array + 1000; ip++) {
    *ip = 0;
}

    move.l  #0, D0
    lea     array, A0
    moveq   #1000, D1
loop:
    move.l  D0, (A0)        ; store zero in array
    addq.l  #4, A0          ; move to next element
    dbra    D1, loop

    move.l  #0, D0
    lea     array, A0
    moveq   #1000, D1
loop:
    move.l  D0, (A0)+       ; store zero in array and increment A0
    dbra    D1, loop

Pre-Decrement Addressing

It made sense to have the opposite instruction, too; one that would first decrement the address register and then store the value—pre-decrement addressing.

int *ip = array + 1000;
for (int i = 1000; i != 0; --i) {
    *--ip = 0;
}

    move.l  #0, D0
    lea     array + 4000, A0
    moveq   #1000, D1
loop:
    move.l  D0, -(A0)       ; decrement A0 and store zero in array
    dbra    D1, loop

This issue really did occur with the original 68000 series processor. There were workarounds, such as not using pre-decrement addressing, or having the operating system carefully check the machine code to see if it was a pre-decrement instruction and adjust the address register accordingly. But the issue was fixed in the 68010 and later processors by undoing the decrement when the page fault occurred. (For more details, check out this post on the Retrocomputing Stack Exchange.)

strcpy(dest, src)
    char *dest, *src;
{
    register char *d, *s;
    d = dest;
    s = src;
    while (*d++ = *s++) {
        /* do nothing */
    }
}

.globl  _strcpy
.text
_strcpy:
        jsr     r5,csv
        mov     4(r5),r4
        mov     6(r5),r3
L4:     movb    (r3)+,(r4)+
        jne     L4
        jmp     cret

int*
poptonull(stack)
    int *stack;
{
    register int* sp;
    sp = stack;
    while (*--sp) {
        /* do nothing */
    }
    return sp;
}

.globl  _poptonu
.text
_poptonu:
        jsr     r5,csv
        mov     4(r5),r4
L4:     tst     -(r4)
        jne     L4
        mov     r4,r0
        jmp     cret

strcpy(dest, src)
char *dest, *src;
{
    register char *d, *s;
    d = dest-1;
    s = src-1;
    while (*++d = *++s) {
        /* do nothing */
    }
}

.globl  _strcpy
.text
_strcpy:
        jsr     r5,csv
        mov     4(r5),r4
        dec     r4
        mov     6(r5),r3
        dec     r3
L4:     inc     r4
        inc     r3
        movb    (r3),(r4)
        jne     L4
        jmp     cret

Efficiency of Demand Paging

Demand paging may end up being faster because it has less data to load (196 KB vs 2.4 MB), and the time to load a single page from storage is only a few milliseconds. So while it could be slower in some situations, in the common case, it's probably faster. But this is a classic example of a trade-off: avoiding wasting time loading pages we don't need vs. the time to load a page when we do need it.

Pre-Paging

One way to mitigate the time to load all the pages needed by a program when it starts up is to remember what pages were needed the last time the program ran—pre-paging. The operating system can load these pages into memory before the program starts running, so that when the program does start running, the pages are already in memory.

The downside of pre-paging is that it adds more complexity. We need to have somewhere to keep track of what pages were needed, and exactly which pages are actually needed might vary from run to run. So pre-paging is often considered not worth the effort.

Paging Out

One option to get rid of unneeded pages is to have the program explicitly tell the operating sytem it doesn't need them anymore. The posix_madvise system call provides a way to do that:

• posix_madvise(addr, length, POSIX_MADV_DONTNEED) tells the operating system that the program doesn't need the pages in the range [addr, addr+length) anymore.
• posix_madvise(addr, length, POSIX_MADV_WILLNEED) tells the operating system that the program will need the pages in the range [addr, addr+length) soon (making demand paging more efficient).

(When logged in, completion status appears here.)