blob: 0c5b490f4baef90470b68cccc1e46a97499145c9 [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
12 * http://www.x86-secret.com - http://www.memtest.org
13 */
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
35#define COMBINE_MASK(a,b,c,d) ((a & b & c & d) | (~a & b & ~c & d))
36
37/* Combine two adr/mask pairs to one adr/mask pair.
38 */
39void combine (ulong adr1, ulong mask1, ulong adr2, ulong mask2,
40 ulong *adr, ulong *mask) {
41
42 *mask = COMBINE_MASK (adr1, mask1, adr2, mask2);
43
44 *adr = adr1 | adr2;
45 *adr &= *mask; // Normalise, no fundamental need for this
46}
47
48/* Count the number of addresses covered with a mask.
49 */
50ulong addresses (ulong mask) {
51 ulong ctr=1;
52 int i=32;
53 while (i-- > 0) {
54 if (! (mask & 1)) {
55 ctr += ctr;
56 }
57 mask >>= 1;
58 }
59 return ctr;
60}
61
62/* Count how much more addresses would be covered by adr1/mask1 when combined
63 * with adr2/mask2.
64 */
65ulong combicost (ulong adr1, ulong mask1, ulong adr2, ulong mask2) {
66 ulong cost1=addresses (mask1);
67 ulong tmp, mask;
68 combine (adr1, mask1, adr2, mask2, &tmp, &mask);
69 return addresses (mask) - cost1;
70}
71
72/* Find the cheapest array index to extend with the given adr/mask pair.
73 * Return -1 if nothing below the given minimum cost can be found.
74 */
75int cheapindex (ulong adr1, ulong mask1, ulong mincost) {
76 int i=v->numpatn;
77 int idx=-1;
78 while (i-- > 0) {
79 ulong tmpcost=combicost(v->patn[i].adr, v->patn[i].mask, adr1, mask1);
80 if (tmpcost < mincost) {
81 mincost=tmpcost;
82 idx=i;
83 }
84 }
85 return idx;
86}
87
88/* Try to find a relocation index for idx if it costs nothing.
89 * Return -1 if no such index exists.
90 */
91int relocateidx (int idx) {
92 ulong adr =v->patn[idx].adr;
93 ulong mask=v->patn[idx].mask;
94 int new;
95 v->patn[idx].adr ^= ~0L; // Never select idx
96 new=cheapindex (adr, mask, 1+addresses (mask));
97 v->patn[idx].adr = adr;
98 return new;
99}
100
101/* Relocate the given index idx only if free of charge.
102 * This is useful to combine to `neighbouring' sections to integrate.
103 * Inspired on the Buddy memalloc principle in the Linux kernel.
104 */
105void relocateiffree (int idx) {
106 int newidx=relocateidx (idx);
107 if (newidx>=0) {
108 ulong cadr, cmask;
109 combine (v->patn [newidx].adr, v->patn[newidx].mask,
110 v->patn [ idx].adr, v->patn[ idx].mask,
111 &cadr, &cmask);
112 v->patn[newidx].adr =cadr;
113 v->patn[newidx].mask=cmask;
114 if (idx < --v->numpatn) {
115 v->patn[idx].adr =v->patn[v->numpatn].adr;
116 v->patn[idx].mask=v->patn[v->numpatn].mask;
117 }
118 relocateiffree (newidx);
119 }
120}
121
122/* Insert a single faulty address in the pattern array.
123 * Return 1 only if the array was changed.
124 */
125int insertaddress (ulong adr) {
126 if (cheapindex (adr, DEFAULT_MASK, 1L) != -1)
127 return 0;
128
129 if (v->numpatn < BADRAM_MAXPATNS) {
130 v->patn[v->numpatn].adr =adr;
131 v->patn[v->numpatn].mask=DEFAULT_MASK;
132 v->numpatn++;
133 relocateiffree (v->numpatn-1);
134 } else {
135 int idx=cheapindex (adr, DEFAULT_MASK, ~0L);
136 ulong cadr, cmask;
137 combine (v->patn [idx].adr, v->patn[idx].mask,
138 adr, DEFAULT_MASK, &cadr, &cmask);
139 v->patn[idx].adr =cadr;
140 v->patn[idx].mask=cmask;
141 relocateiffree (idx);
142 }
143 return 1;
144}