Hi,
Candy wrote:There's a bit of a problem with properly testing the memory. You would need to test at least each address line and each data line to each of the memory chips separately, specifically those lines that are actually there, as well as some forms of operation. These all differ wildly between types.
For example, DDR2 memory would need at least a burst transaction and a single transaction, you'd need to test each address line for each chip separately etc. You'd have to know, at the very least, how many chips there are on the device and how they're connected. That's nontrivial to say the least.
It is more complicated than it sounds at first...
I've been mostly following
this white paper, with variations, and with assumptions about the relationships between the CPUs address lines and the RAM chips addressing.
First, if the OS crashes due to faulty RAM during boot, then it's unfortunate, but won't cause data loss, corruption, etc because everything at this stage came from somewhere and still exists somewhere (e.g. on a boot disk). This allows me to take some short-cuts.
During boot, a boot image is loaded into memory, decompressed (with corruption detection during decompression phases and a final checksum), and then some boot code taken from the boot image and run. This boot code is responsible for the initial memory testing.
I begin the memory testing by checking the data lines using both a "walking 1's" test and a "walking 0's" test on a 1024 bit (or 128 byte) area (selected as the widest known cache line width). The test is done within each 512 KB "chunk" of RAM. This assumes that each memory bank is 512 KB or larger (which is likely for 80486 and later computers), and means that (for e.g.) testing at 0x00080000 is sufficient for the data line testing for the entire area from 0x00080000 to 0x000FFFFF (including the RAM that is below the video display memory mapping and ROMs). This testing doesn't check anything above 4 GB (more on that later).
Next I do an address line check, but I don't test the lower address lines (bits 0 to 11). I build a list of desired addresses (0x00000000, 0x00001000, 0x00002000, 0x00004000, ..., 0x40000000, 0x80000000) and then filter this list according to where RAM is - any address that doesn't contain RAM is removed from the list. Then I do a test for "address line stuck low", "address lines shorted" and "address line stuck high" as described in the white paper above.
Then I repeat the address line test for each 1 MB "chunk" in the same way (for e.g. from 1 MB to 2 MB I'd create the list of addresses 0x00100000, 0x00101000, 0x00102000, 0x00103000, ..., 0x00140000, 0x00180000). This isn't perfect because I don't know how large each bank of RAM is, and worst case is that I neglect several address lines. I'm still thinking about this - I have a theory that I can do all of the address line checks in parallel to solve this problem.
Also, none of the address line testing checks anything above 4 GB (more on that later).
After the data line and address line tests is meant to be a "memory device tests", which tests to see if each memory location can store a unique value. Instead I have a "page test" which re-tests the data lines at the begining of the page, tests the lowest 12 address lines within the page, and then tests if each memory location in the page can store a unique value.
During boot I only use RAM from 0x0000D000 to 0x0007FFFF and from 0x00100000 to the end of the boot image (likely to be around 0x00400000), so I only test these areas and ignore everything else. For each page in these areas I do my "page test".
After all of this my OS build a "free page stack" of free pages (which is used for initialising the kernel later, but not used after the kernel is initialised). The free page stack does not contain any pages that were tested with the "page test" earlier, as these pages are still considered "in use".
While building this free page stack different things happen. If the boot-time memory check is enabled but the run-time memory check isn't enabled, then the "page test" is done on each page as it's added to the free page stack. If the boot-time memory check and the run-time memory check are both enabled, then the "page test" is skipped. If the boot-time memory check is disabled then none of the above tests would've been done and all pages are put on the free page stack without any testing (regardless of whether or not the run-time tests are enabled).
In any case, if run-time testing is enabled the free page stack is a problem, because the first dword in the free page stack contains the address of the next free page on the stack. If the first dword in a page is faulty then the stack itself is corrupt. To solve this problem, I fill the entire page with the address of the next page on the stack. If the page is faulty but most of the page contains the same address then the OS can continue, otherwise the OS aborts the boot with a big error message.
The next step is to initialise paging (either plain 32-bit paging, "36-bit"/PAE paging or long mode) and leave real mode. As the paging data structures are being created, if run-time testing is enabled each page is tested as it's allocated.
Now we reach the point of initialising the kernel's physical memory manager. For pages below 4 GB this involves shifting physical pages from the free page stack used during boot to whatever structures the kernel decides to use. For PAE and long mode there's still pages above 4 GB that are completely untested, that can be tested now that access to these pages is possible. If boot-time memory testing is enabled more data line and address line tests are done, but only above 4 GB. Then the pages are either immediately put into the kernel's data structures (if run-time testing is enabled) or tested using the "page test" before being put into the kernel's data structures (if run-time testing is disabled).
At this stage, if run-time testing is disabled all memory testing is complete. If run-time testing is enabled pages that are needed are allocated using the kernel and tested during allocation.
The kernel's physical memory manager keeps track of "clean" and "dirty" pages seperately. After the scheduler starts idle thread/s are created that convert dirty pages into clean pages. If run-time testing is enabled this conversion includes the "page test" (otherwise it just means filling the page with zero). When any page is freed it's considered dirty, where it needs to be converted into a clean page before use. If memory is constantly being allocated and freed, then the demand for clean pages may be more than the idle thread/s can supply. In this case the conversion from dirty to clean is done during the allocation.
To assist this (to reduce the chance of running out of clean pages), low priority threads behave differently. When they allocate a page it's taken from the dirty page stack and converted (even when there's already clean pages available). When they free a page the page is put on the clean page stack, which includes converting the page to clean if it was modified. This means that the kernel's idle thread/s only need to allocate and free pages to convert pages from dirty to clean, and this only involves one conversion from dirty to clean. It also means that if an idle thread allocates a page, modifies it and then frees it, then the page ends up getting converted from dirty to clean twice (i.e. double tested if run-time tests are enabled).
As far as I can tell, this leaves a few weaknesses with address line testing for the 32nd address line and because the bank size isn't known (described above). All other problems should have adequate detection (realising that for intermittent problems, no detection algorithm is perfect, except for an extended burn-in test that takes several hours perhaps).
Candy wrote:If you get a proper test up, it'll barely slow down anything and find more problems. Using a dumb test to make it look like you're testing it properly is just silly and for end-users and managers.
I hope it won't cause a noticeable performance loss, but for code that repeatedly allocates and de-allocates pages the run-time testing might be a severe problem. I guess the only way to be sure will be to implement it all and do some benchmarking, and if it is a problem add some sort of work-around (e.g. tracking how long ago pages were tested to prevent re-testing them if they're freed soon after).
One thing I know is that Bochs really doesn't like the WBINVD instruction!
Cheers,
Brendan
