On 3/21/2022 9:58 AM, EricP wrote:
> BGB wrote:
>>
>> At present, the pagefile is a fairly naive format, where each
>> virtual-memory page has an "index" which maps directly to its location
>> in the pagefile. When a page is committed, it is assigned a spot in
>> the pagefile.
>
> It's not naive, its simple and straight forward. That's a good thing.
> The "in use" space tracking is a bit vector and allocation is a find-first.
> Its drawback is that pages that are contiguous in virtual space
> wind up scattered about the page file. Most page fault handlers have
> a "cluster" optimization that tries to bring in multiple pages at once
> if the blocks are also contiguous on disk. However this optimization
> doesn't work with the dynamically allocated scattered page file blocks.
>

Clustering is mostly N/A for an SDcard, as "seek time" doesn't really
exist. What is potentially a problem, is that while the SDcard is
written in terms of 512-byte sectors, the area being rewritten is
actually significantly larger than a given sector.

Then again, it is possible the SDcard could have logic to lessen the
impact of a bunch of scattered small writes, dunno...

Though, from what I can gather, the usual way to extend the lifetime of
an SDcard is to try to do a smaller number of bigger writes aligned on
the SDcard's native block boundary. Historically, they don't hold up
well with small scattered writes.

> A different way is to allocate the page file blocks as a contiguous
> segment at the time the memory section is created. That leaves virtually
> contiguous pages as physically adjacent in the page file.
> The downside is it gets complicated if the memory section starts to
> change size and ends up with multiple file segments as backing store.
>

As noted, this part likely matters a lot more for an HDD than an SDcard.

>> One other thing I was considering is whether or not it would be
>> "effective" to use a quick/dirty LZ compressor on the pages to reduce
>> the amount of data that needs to be written to or read from the SD card.
>
> Its is doable but complicated.
> The problem is that compressing a fixed size block becomes a variable
> sized block. So a fixed "logical block number" winds up at a variable
> offset. To find a particular block again you need something that does
> the equivalent to what the i-node file system structure does,
> but this structure is in memory because it doesn't need to be retained.
>
> And you need some way to recover deleted file space but retain the
> non-deleted blocks.
>
> This is starting to sound like building your own
> log file system but layered onto the page file.
>

Probably.

Haven't really looked much into log file systems, but am aware that some
projects use them (in preference to FAT32 and similar) on SD cards and SSDs.

A log structured approach would seem to be a way to minimize the amount
of writes to an SDcard, and thus hopefully extend its lifespan.

Every page in the pagefile would need to keep track of which chunk it is
in, and its size/offset within the chunk.

If compressed data is stored at a granularity of 64B, we need 16b for
the offset and size within the chunk, plus ~ 8-16b to encode the chunk
within the pagefile.

So, say, 48b to store the location and size of an LZ compressed page
(along with a few flags).

For a 256MB pagefile, this is ~ 128K (with 16K pages).

One would also need a way to daisy-chain all the pages within a chunk,
but this would need ~ 18 or 20 bits, increasing the overhead to 256K.

If I assume a 512B granularity (maps nicely to the sector size), need
13b for size and offset.

So, say:
(63:60): Page Flags
(59:40): Chunk Link Chain
(39:26): Chunk Index
(25:13): Compressed Size
(12: 0): Compressed Offset

The chain is needed, as otherwise one would need to sweep "all" of the
pages to build a list of which pages might be impacted by overwriting a
given chunk.

Though, this operation is likely to be rare enough, and would coincides
with writing ~ 4MB to the SDcard, that it may make sense to skip the
chain and do a brute-force query (leaving these bits for other uses).

It could also be possible to use a log-structured format without LZ
compressing the pages, but this would mean around 3x or 4x as much IO
traffic.

>> This is because IO happens in 512B blocks, and I can reduce the number
>> of IO blocks via LZ compression, however, this assumes a fast LZ
>> compressor.
>>
>> One concern though is that the SD cards internally operate via much
>> larger blocks, meaning that saving a few K here and there would not be
>> effective for lifespan. About the only real option here would be to
>> gather up evicted pages, and then write them out all at once in a big
>> chunk.
>
> There is the larger block size, but also the write amplification because
> the SSD has a map from the disk "physical block number" to its internal
> actual block number, and that map has to also be stored when it changes.
>
> In general, paging to a SSD is discouraged because it wears it out.
>

Yeah, though in this case, can't really connect an HDD up to an FPGA
board. Main option is an SDcard, but I would prefer not to ruin the
lifespan of the SD cards.

>> Say, we have a 4MB "Page Evict Buffer":
>> Evicted pages are LZ compressed, and added to this buffer;
>> When the buffer is full, it is written to the pagefile;
>> The pagefile is written as big circular log buffer.
>> Likely would need a special case to avoid overwriting "still live"
>> pages (if the next chunk includes live pages, they are copied as-is
>> into the evict buffer);
>> ....
>>
>> So, for every page, one will need to keep track of is current position
>> within the pagefile, and for every position, an ability to query for
>> any still-live pages, ...
>
> Yes. That block number can be stored in the Not-Present PTE so if the
> page is touched again you know exactly where to find the backing store.
> If the page gets swapped back in, the old page file block number
> can be stashed in the frame table (aka the struct page table) while
> the PTE contains the page frame number (PFN ) (aka physical page number).
>

The PTE's for non-live pages encode a logical "page index" within the
pagefile.

This gets more complicated with an indirect compressed-page scheme, as
now we need both a logical page number, and another table to encode
where it is currently stored in its LZ compressed form (which may change
dynamically).

It doesn't seem like a great idea to store the compressed location
directly within the PTE, and also my PTE scheme doesn't really leave
enough bits for this.

>> It is a question of what would be the best LZ design to use in this
>> case. Ideally, I would want something that favors encoder speed over
>> ratio (likely a specialized encoder either for RP2, a simplified RP2
>> variant, or some other more specialized format).
>>
>> ....
>>
>> Though, it may not be as big of an immediate issue, as the amount of
>> "thrashing" to the page file seems to be a lot smaller than I was
>> originally expecting (with currently 32MB of RAM being set aside to be
>> used as pagefile backed virtual memory).
>>
>>
>> Any thoughts?...
>
> Every time it writes an SSD block it has to update its internal map.
> The only way to avoid that is don't page swap, or use an HDD.
> Or page swap to a different SSD device, like a cheap-o USB drive
> that cost $5 and you don't care if it wears out.
> And skip that whole compression approach.

I am not dealing with SSD's in this case, but mostly SDcards.

For the physical testing, I mostly have a bunch of 16GB SDcards I got
off Amazon, forget how much they cost now, wasn't all that much. They
were a lot cheaper than 64GB or 128GB SDcards at least.

For my testing on an FPGA, 16GB seemed like plenty.
Nevermind if I hack off several GB to use as a pagefile.

Still generally using FAT32 as the main filesystem, partly as Windows
doesn't really have anything else it can use (otherwise, would have
assumed using EXTn or similar).

There is an option for mounting WAD4 images as part of the filesystem,
but this isn't really used as much yet.

Unlike Linux and friends, most of the basic commands are built into the
shell (which is also the OS kernel for now). Eventually, it may may make
sense to split the shell and kernel into separate binaries, but
consolidating most of the basic command-line tools into the shell makes
more sense from an overhead perspective.

Well, and it is also sort of like Cygwin in that binaries typically
still have an "EXE" file extension (if you launch "whatever", the shell
looks for "whatever.exe" or similar).

....