11) Memtest86 Test Algorithms ============================= Memtest86 uses two algorithms that provide a reasonable approximation of the ideal test strategy above. The first of these strategies is called moving inversions. The moving inversion test works as follows: 1) Fill memory with a pattern 2) Starting at the lowest address 2a check that the pattern has not changed 2b write the patterns complement 2c increment the address repeat 2a - 2c 3) Starting at the highest address 3a check that the pattern has not changed 3b write the patterns complement 3c decrement the address repeat 3a - 3c This this algorithm is a good approximation of an ideal memory test but there are some limitations. Most high density chips today store data 4 to 16 bits wide. With chips that are more than one bit wide it is impossible to selectively read or write just one bit. This means that we cannot guarantee that all adjacent cells have been tested for interaction. In this case the best we can do is to use some patterns to insure that all adjacent cells have at least been written with all possible one and zero combinations. It can also be seen that caching, buffering and out of order execution will interfere with the moving inversions algorithm and make less effective. It is possible to turn off cache but the memory buffering in new high performance chips can not be disabled. To address this limitation a new algorithm I call Modulo-X was created. This algorithm is not affected by cache or buffering. The algorithm works as follows: 1) For starting offsets of 0 - 20 do 1a write every 20th location with a pattern 1b write all other locations with the patterns complement repeat 1b one or more times 1c check every 20th location for the pattern This algorithm accomplishes nearly the same level of adjacency testing as moving inversions but is not affected by caching or buffering. Since separate write passes (1a, 1b) and the read pass (1c) are done for all of memory we can be assured that all of the buffers and cache have been flushed between passes. The selection of 20 as the stride size was somewhat arbitrary. Larger strides may be more effective but would take longer to execute. The choice of 20 seemed to be a reasonable compromise between speed and thoroughness. 12) Individual Test Descriptions ================================ Memtest86 executes a series of numbered test sections to check for errors. These test sections consist of a combination of test algorithm, data pattern and caching. The execution order for these tests were arranged so that errors will be detected as rapidly as possible. Tests 8, 9, 10, 11 and 12 are very long running extended tests and are only executed when extended testing is selected. The extended tests have a low probability of finding errors that were missed by the default tests. A description of each of the test sections follows: Test 0 [Address test, walking ones, no cache] Tests all address bits in all memory banks by using a walking ones address pattern. Errors from this test are not used to calculate BadRAM patterns. Test 1 [Moving Inv, ones&zeros, cached] This test uses the moving inversions algorithm with patterns of only ones and zeros. Cache is enabled even though it interferes to some degree with the test algorithm. With cache enabled this test does not take long and should quickly find all "hard" errors and some more subtle errors. This section is only a quick check. Test 2 [Address test, own address, no cache] Each address is written with its own address and then is checked for consistency. In theory previous tests should have caught any memory addressing problems. This test should catch any addressing errors that somehow were not previously detected. Test 3 [Moving inv, 8 bit pat, cached] This is the same as test 1 but uses a 8 bit wide pattern of "walking" ones and zeros. This test will better detect subtle errors in "wide" memory chips. A total of 20 data patterns are used. Test 4 [Moving inv, 32 bit pat, cached] This is a variation of the moving inversions algorithm that shifts the data pattern left one bit for each successive address. The starting bit position is shifted left for each pass. To use all possible data patterns 32 passes are required. This test is very effective at detecting data sensitive errors in "wide" memory chips. Test 5 [Block move, 64 moves, cached] This test stresses memory by using block move (movsl) instructions and is based on Robert Redelmeier's burnBX test. Memory is initialized with shifting patterns that are inverted every 8 bytes. Then 4MB blocks of memory are moved around using the movsl instruction. After the moves are completed the data patterns are checked. Because the data is checked only after the memory moves are completed it is not possible to know where the error occurred. The addresses reported are only for where the bad pattern was found. Since the moves are constrained to a 8MB segment of memory the failing address will always be lest than 8MB away from the reported address. Errors from this test are not used to calculate BadRAM patterns. Test 6 [Modulo 20, ones&zeros, cached] Using the Modulo-X algorithm should uncover errors that are not detected by moving inversions due to cache and buffering interference with the the algorithm. As with test one only ones and zeros are used for data patterns. Test 7 [Moving inv, ones&zeros, no cache] This is the same as test one but without cache. With cache off there will be much less interference with the test algorithm. However, the execution time is much, much longer. This test may find very subtle errors missed by tests one and two. Test 8 [Block move, 512 moves, cached] This is the same as test #5 except that we do a lot more memory moves before checking memory. Errors from this test are not used to calculate BadRAM patterns. Test 9 [Moving inv, 8 bit pat, no cache] This is the first extended test. By using an 8 bit pattern with cache off this test should be effective in detecting all types of errors. However, it takes a very long time to execute and there is a low probability that it will detect errors not found by the previous tests. Test 10 [Modulo 20, 8 bit, cached] This is the first test to use the modulo 20 algorithm with a data pattern other than ones and zeros. This combination of algorithm and data pattern should be quite effective. However, it's very long execution time relegates it to the extended test section. Test 11 [Moving inv, 32 bit pat, no cache] This test should be the most effective in finding errors that are data pattern sensitive. However, without cache it's execution time is excessively long. Test 12 [Bit fade test, 90 min, 2 patterns] The bit fade test initializes all of memory with a pattern and then sleeps for 90 minutes. Then memory is examined to see if any memory bits have changed. All ones and all zero patterns are used. Since this test takes 6+ hours to complete plan to let this one run overnight.