/* Pattern extension for memtest86
 *
 * Generates patterns for the Linux kernel's BadRAM extension that avoids
 * allocation of faulty pages.
 *
 * Released under version 2 of the Gnu Public License.
 *
 * By Rick van Rein, vanrein@zonnet.nl
 * ----------------------------------------------------
 * MemTest86+ V1.60 Specific code (GPL V2.0)
 * By Samuel DEMEULEMEESTER, sdemeule@memtest.org
 * http://www.x86-secret.com - http://www.memtest.org 
 */


#include "test.h"


/*
 * DEFAULT_MASK covers a longword, since that is the testing granularity.
 */
#define DEFAULT_MASK ((~0L) << 2)


/* extern struct vars *v; */


/* What it does:
 *  - Keep track of a number of BadRAM patterns in an array;
 *  - Combine new faulty addresses with it whenever possible;
 *  - Keep masks as selective as possible by minimising resulting faults;
 *  - Print a new pattern only when the pattern array is changed.
 */

#define COMBINE_MASK(a,b,c,d) ((a & b & c & d) | (~a & b & ~c & d))

/* Combine two adr/mask pairs to one adr/mask pair.
 */
void combine (ulong adr1, ulong mask1, ulong adr2, ulong mask2,
              ulong *adr, ulong *mask) {

    *mask = COMBINE_MASK (adr1, mask1, adr2, mask2);

    *adr  = adr1 | adr2;
    *adr &= *mask;	// Normalise, no fundamental need for this
}

/* Count the number of addresses covered with a mask.
 */
ulong addresses (ulong mask) {
    ulong ctr=1;
    int i=32;
    while (i-- > 0) {
        if (! (mask & 1)) {
            ctr += ctr;
        }
        mask >>= 1;
    }
    return ctr;
}

/* Count how much more addresses would be covered by adr1/mask1 when combined
 * with adr2/mask2.
 */
ulong combicost (ulong adr1, ulong mask1, ulong adr2, ulong mask2) {
    ulong cost1=addresses (mask1);
    ulong tmp, mask;
    combine (adr1, mask1, adr2, mask2, &tmp, &mask);
    return addresses (mask) - cost1;
}

/* Find the cheapest array index to extend with the given adr/mask pair.
 * Return -1 if nothing below the given minimum cost can be found.
 */
int cheapindex (ulong adr1, ulong mask1, ulong mincost) {
    int i=vv->numpatn;
    int idx=-1;
    while (i-- > 0) {
        ulong tmpcost=combicost(vv->patn[i].adr, vv->patn[i].mask, adr1, mask1);
        if (tmpcost < mincost) {
            mincost=tmpcost;
            idx=i;
        }
    }
    return idx;
}

/* Try to find a relocation index for idx if it costs nothing.
 * Return -1 if no such index exists.
 */
int relocateidx (int idx) {
    ulong adr =vv->patn[idx].adr;
    ulong mask=vv->patn[idx].mask;
    int new;
    vv->patn[idx].adr ^= ~0L;	// Never select idx
    new=cheapindex (adr, mask, 1+addresses (mask));
    vv->patn[idx].adr = adr;
    return new;
}

/* Relocate the given index idx only if free of charge.
 * This is useful to combine to `neighbouring' sections to integrate.
 * Inspired on the Buddy memalloc principle in the Linux kernel.
 */
void relocateiffree (int idx) {
    int newidx=relocateidx (idx);
    if (newidx>=0) {
        ulong cadr, cmask;
        combine (vv->patn [newidx].adr, vv->patn[newidx].mask,
                 vv->patn [   idx].adr, vv->patn[   idx].mask,
                 &cadr, &cmask);
        vv->patn[newidx].adr =cadr;
        vv->patn[newidx].mask=cmask;
        if (idx < --vv->numpatn) {
            vv->patn[idx].adr =vv->patn[vv->numpatn].adr;
            vv->patn[idx].mask=vv->patn[vv->numpatn].mask;
        }
        relocateiffree (newidx);
    }
}

/* Insert a single faulty address in the pattern array.
 * Return 1 only if the array was changed.
 */
int insertaddress (ulong adr) {
    if (cheapindex (adr, DEFAULT_MASK, 1L) != -1)
        return 0;

    if (vv->numpatn < BADRAM_MAXPATNS) {
        vv->patn[vv->numpatn].adr =adr;
        vv->patn[vv->numpatn].mask=DEFAULT_MASK;
        vv->numpatn++;
        relocateiffree (vv->numpatn-1);
    } else {
        int idx=cheapindex (adr, DEFAULT_MASK, ~0L);
        ulong cadr, cmask;
        combine (vv->patn [idx].adr, vv->patn[idx].mask,
                 adr, DEFAULT_MASK, &cadr, &cmask);
        vv->patn[idx].adr =cadr;
        vv->patn[idx].mask=cmask;
        relocateiffree (idx);
    }
    return 1;
}
