blob: 2e35a38114e88b9b4da94e18e257b1f7fdcc4fca [file] [log] [blame]
Martin Roth9b1b3352016-02-24 12:27:06 -08001/* Pattern extension for memtest86
2 *
3 * Generates patterns for the Linux kernel's BadRAM extension that avoids
4 * allocation of faulty pages.
5 *
6 * Released under version 2 of the Gnu Public License.
7 *
8 * By Rick van Rein, vanrein@zonnet.nl
9 * ----------------------------------------------------
10 * MemTest86+ V1.60 Specific code (GPL V2.0)
11 * By Samuel DEMEULEMEESTER, sdemeule@memtest.org
Martin Roth4dcd13d2016-02-24 13:53:07 -080012 * http://www.x86-secret.com - http://www.memtest.org
Martin Roth9b1b3352016-02-24 12:27:06 -080013 */
14
15
16#include "test.h"
17
18
19/*
20 * DEFAULT_MASK covers a longword, since that is the testing granularity.
21 */
22#define DEFAULT_MASK ((~0L) << 2)
23
24
25/* extern struct vars *v; */
26
27
28/* What it does:
29 * - Keep track of a number of BadRAM patterns in an array;
30 * - Combine new faulty addresses with it whenever possible;
31 * - Keep masks as selective as possible by minimising resulting faults;
32 * - Print a new pattern only when the pattern array is changed.
33 */
34
Ben Gardner90f7d112016-03-15 15:25:22 -050035#define COMBINE_MASK(a, b, c, d) ((a & b & c & d) | (~a & b & ~c & d))
Martin Roth9b1b3352016-02-24 12:27:06 -080036
37/* Combine two adr/mask pairs to one adr/mask pair.
38 */
39void combine (ulong adr1, ulong mask1, ulong adr2, ulong mask2,
Ben Gardner90f7d112016-03-15 15:25:22 -050040 ulong *adr, ulong *mask)
41{
Martin Roth9b1b3352016-02-24 12:27:06 -080042 *mask = COMBINE_MASK (adr1, mask1, adr2, mask2);
43
44 *adr = adr1 | adr2;
Ben Gardner90f7d112016-03-15 15:25:22 -050045 *adr &= *mask; // Normalise, no fundamental need for this
Martin Roth9b1b3352016-02-24 12:27:06 -080046}
47
48/* Count the number of addresses covered with a mask.
49 */
Ben Gardner90f7d112016-03-15 15:25:22 -050050ulong addresses (ulong mask)
51{
Martin Roth9b1b3352016-02-24 12:27:06 -080052 ulong ctr=1;
53 int i=32;
54 while (i-- > 0) {
Ben Gardner90f7d112016-03-15 15:25:22 -050055 if (!(mask & 1)) {
Martin Roth9b1b3352016-02-24 12:27:06 -080056 ctr += ctr;
57 }
58 mask >>= 1;
59 }
60 return ctr;
61}
62
63/* Count how much more addresses would be covered by adr1/mask1 when combined
64 * with adr2/mask2.
65 */
Ben Gardner90f7d112016-03-15 15:25:22 -050066ulong combicost (ulong adr1, ulong mask1, ulong adr2, ulong mask2)
67{
Martin Roth9b1b3352016-02-24 12:27:06 -080068 ulong cost1=addresses (mask1);
69 ulong tmp, mask;
70 combine (adr1, mask1, adr2, mask2, &tmp, &mask);
71 return addresses (mask) - cost1;
72}
73
74/* Find the cheapest array index to extend with the given adr/mask pair.
75 * Return -1 if nothing below the given minimum cost can be found.
76 */
Ben Gardner90f7d112016-03-15 15:25:22 -050077int cheapindex (ulong adr1, ulong mask1, ulong mincost)
78{
Martin Roth9b1b3352016-02-24 12:27:06 -080079 int i=v->numpatn;
80 int idx=-1;
81 while (i-- > 0) {
82 ulong tmpcost=combicost(v->patn[i].adr, v->patn[i].mask, adr1, mask1);
83 if (tmpcost < mincost) {
84 mincost=tmpcost;
85 idx=i;
86 }
87 }
88 return idx;
89}
90
91/* Try to find a relocation index for idx if it costs nothing.
92 * Return -1 if no such index exists.
93 */
Ben Gardner90f7d112016-03-15 15:25:22 -050094int relocateidx (int idx)
95{
Martin Roth9b1b3352016-02-24 12:27:06 -080096 ulong adr =v->patn[idx].adr;
97 ulong mask=v->patn[idx].mask;
98 int new;
Ben Gardner90f7d112016-03-15 15:25:22 -050099 v->patn[idx].adr ^= ~0L; // Never select idx
Martin Roth9b1b3352016-02-24 12:27:06 -0800100 new=cheapindex (adr, mask, 1+addresses (mask));
101 v->patn[idx].adr = adr;
102 return new;
103}
104
105/* Relocate the given index idx only if free of charge.
106 * This is useful to combine to `neighbouring' sections to integrate.
107 * Inspired on the Buddy memalloc principle in the Linux kernel.
108 */
Ben Gardner90f7d112016-03-15 15:25:22 -0500109void relocateiffree (int idx)
110{
Martin Roth9b1b3352016-02-24 12:27:06 -0800111 int newidx=relocateidx (idx);
112 if (newidx>=0) {
113 ulong cadr, cmask;
114 combine (v->patn [newidx].adr, v->patn[newidx].mask,
115 v->patn [ idx].adr, v->patn[ idx].mask,
Ben Gardner90f7d112016-03-15 15:25:22 -0500116 &cadr, &cmask);
Martin Roth9b1b3352016-02-24 12:27:06 -0800117 v->patn[newidx].adr =cadr;
118 v->patn[newidx].mask=cmask;
119 if (idx < --v->numpatn) {
120 v->patn[idx].adr =v->patn[v->numpatn].adr;
121 v->patn[idx].mask=v->patn[v->numpatn].mask;
122 }
123 relocateiffree (newidx);
124 }
125}
126
127/* Insert a single faulty address in the pattern array.
128 * Return 1 only if the array was changed.
129 */
Ben Gardner90f7d112016-03-15 15:25:22 -0500130int insertaddress (ulong adr)
131{
Martin Roth9b1b3352016-02-24 12:27:06 -0800132 if (cheapindex (adr, DEFAULT_MASK, 1L) != -1)
133 return 0;
134
135 if (v->numpatn < BADRAM_MAXPATNS) {
136 v->patn[v->numpatn].adr =adr;
137 v->patn[v->numpatn].mask=DEFAULT_MASK;
138 v->numpatn++;
139 relocateiffree (v->numpatn-1);
140 } else {
141 int idx=cheapindex (adr, DEFAULT_MASK, ~0L);
142 ulong cadr, cmask;
143 combine (v->patn [idx].adr, v->patn[idx].mask,
144 adr, DEFAULT_MASK, &cadr, &cmask);
145 v->patn[idx].adr =cadr;
146 v->patn[idx].mask=cmask;
147 relocateiffree (idx);
148 }
149 return 1;
150}