Squashing the LRU bug

English: Typical actions taken upon a virtual-...
English: Typical actions taken upon a virtual-physical address translation. (Photo credit: Wikipedia)

Just for once I did not rush to an online forum and say I had found a bug in a product – and I was right not too.

Having tried three different cross compiler toolchains I convinced myself that the issue was plainly neither compiler (or, to be more accurate in this case, assembler) output but some process in my code that was causing corruption. And sure enough I found that I was mangling the physical addresses of my page frames.

Thanks to the way OVPsim operates – by default it provides physical mappings on demand for the full 4GB address space of a 32 bit register – this mangling did not generate a page fault, but it did mean that for certain sequences of instructions – particularly those where lots of page faults were likely to occur, memory was being corrupted.

Changing one line of assembly – so that virtual address output was written to virtual address slot and not the physical address slot in my simple list of page table entries fixed that.

So now the code works – at least I think it does!


Curiouser and curiouser – the case of the LRU bug

A 256Kx4 Dynamic RAM chip on an early PC memor...
A 256Kx4 Dynamic RAM chip on an early PC memory card. (Photo by Ian Wilson) (Photo credit: Wikipedia)

My LRU queue bug is continuing to puzzle me – and it’s not as simple as a data misalignment. In fact it does not appear to be a data misalignment issue at all: before I was trapping a lot of hardware exceptions under that header because it was a common fault when I got the code wrong, but a closer examination showed it to be an illegal opcode exception.

How that could be caused by the size of the local memory we were simulating was beyond me – but perhaps some code was being pushed out of alignment and an illegal instruction created, I thought.

But that does not appear to be the issue at all – in fact the really puzzling thing is that the exact same string of opcodes at the same addresses runs without a problem in the version with the functional memory sizes as with the “broken” memory sizes.

The only difference seems to be that when the broken code (ie the setup with the non mod 4 number of 4k memory pages) raises an illegal opcode exception, the good code raises a page fault.

It looks like it might be a bug in the simulator itself – and having written that I am hoping that the bad workman’s curse now befalls me and I quickly find it was all my fault to begin with. But as of now I am drawing a blank.

LRU queue strangeness

Prinzipdarstellung der Arbeitsweise einer MMU
(Photo credit: Wikipedia)

For the last week or so I have been writing and then debugging (and so mainly debugging) a least-recently-used (LRU) page replacement system on my Microblaze simulation.

Perhaps I shouldn’t have bothered – I had a working first-in-first-out (FIFO) system after all. But no one seriously uses FIFO, so I had to write some LRU code.

I thought I had it working tonight – it ran through the target exercise in about 6 million instructions (as the MMU in a Microblaze is crude, memory gets loaded in and out ‘by hand’ and so the instruction count measures time/efficiency) when the system had 32 4k local pages and in about 10.5 million instructions when it had 24 4k pages available locally – all seems fine: less pages means more time is required.

But then things started to get weird – testing the system with 28 pages took about 9 million instructions, but when I tried to use 26 pages I had to break the code after it had executed 14 trillion instructions.

Indeed it seems to only work for a very limited number of page counts. How odd – though a typically debuggers story. A week in, finally thinking I’d cracked it when some really strange behaviour manifests itself.

Update: It appears to be an unaligned data exeception issue. Somewhere along the line a piece of code relies on the LRU queue to be a multiple of 4 in length would be my guess…

There is no such thing as “alternative medicine”

There is no such thing as “alternative medicine” – any more than there is “alternative mathematics”.

Yes, there are different ways to practise medicine, just as there are different ways of calculating the value of pi – but the fundamental remains: something is either medically valid or it is not. If it is not – and that means if it cannot prove its efficacy – then it is not any sort of medicine.

I am move to write this by two things – firstly what appears to be a major outbreak of measles in the United States that has been brought about not by a failure of medicine but by a cold and deliberate attempt to undermine medicine, and secondly by the current vogue in the UK of otherwise rational people saying they would support the Green Party – a party dedicated, amongst other things to the promotion of anti-science in medicine.

The US measles outbreak is not just because of the “irresponsible and dishonest” work of Andrew Wakefield – a man who manipulated research findings in a way that stood to bring substantial financial benefits to lots of people he was associated with. Wakefield has been thoroughly discredited by anyone with the remotest concern for scientific credibility.

What has fuelled the outbreak is the belief by some – too many – that somehow they know better than science that their “alternative” medicine is better. In fact they are putting the lives of their children at risk through their refusal to accept medicine. If you want a contemporary example of “shouting fire in a crowded theatre” then this, surely, is it.

As for the Green Party – which were reported to be as high as 11% in one opinion poll last week and which have also won the right to appear in leaders’ debates on UK television – at least they are no longer explicitly describing homoeopathy (also known as “water”) as “natural medicine”) and they have also seemingly distanced themselves from past demands that scientific research only follow government-approved routes (Lysenko-ism anybody?). But they still state this on their policy website:

Current theory and practice place too much emphasis on interventions at the biochemical and individual levels, too little on the social and ecological.

Of course, perhaps that is just a meaningless left-over from their past days as new age hippies – but it has a distinct anti-science tone to my ears, especially as it is followed up with the statement that their aim is to:

…develop a new public health consciousness, which, through individual and collective action, will challenge vested interests and promote the personal, social and political changes needed to achieve improved states of health.

Wouldn’t actually some new “biochemical interventions” also be a good idea? I certainly think so, but if health is all about lifestyle you might feel otherwise.

Then there is this “aim”:

To develop health services which place as much emphasis on illness prevention, health promotion and the development of individual and community self-reliance as on the treatment and cure of disease. Such services will of necessity be empowering, participatory and democratic and their development will be guided by users’ own perceptions of their health needs.

By now I am beginning to feel distinctly uncomfortable – to me the above statement is seriously anti-scientific in tone and intent: truth, after all, is not democratic.

And, then, under policies we have this:

We will work to reduce the number of interventions in childbirth, and change the culture of the NHS so that birth is treated as a normal and non-medical event, in which mothers are empowered and able to be in control.

(Shades here of the Soviet approach – and the claim that pain was all in the mind of the mother – as described in Red Plenty. Most mothers I know were very glad of medical help at birth, especially in the form of pain relief. Is the Green Party’s policy really to “change the culture” of the NHS to limit access to that?)

And this…

The safety and regulation of medicines will be controled by a single agency. This agency will ensure that medicines meet minimum safety standards, provide clear labelling of both ingredients and side-effects. The agency will cover existing synthetic medicines as well as those considered as natural or alternative medicines.

Considered by whom to be “alternative” medicines? It’s not a purely rhetorical question as the Green’s current sole MP, Caroline Lucas, has a disappointing record as an advocate of “alternative” medicine campaigns funded by commercial interests in this field.

Not fit to hold public office

John Mason, Scottish National Party MSP for Glasgow Shettleston, has (today) tabled the following motion in the Scottish Parliament:

That the Parliament notes that South Lanarkshire Council has issued guidance concerning the appointment and input of chaplains and religious organisations in schools; understands that some people believe that God created the world in six days, some people believe that God created the world over a longer period of time and some people believe that the world came about without anyone creating it; considers that none of these positions can be proved or disproved by science and all are valid beliefs for people to hold, and further considers that children in Scotland’s schools should be aware of all of these different belief systems.

Nobody has proved P=NP

Which are the world’s fastest computers?

The answer is not to be found, I’d guess, in the Top500 list. Instead they are surely to be found somewhere in the US National Security Administration or maybe even in the UK’s Government Communications HQ.

So the fact that David Cameron is calling for the banning of all internet encryption (yes, I know that’s crazy, but he’s said it), tells us that neither of these agencies (which co-operate very closely) has managed to prove P=NP and so reverse the “one way” functions on which internet encryption depends.

It has been suggested that proving P=NP would not, for most of us, make much difference – as although there might be an algorithm available to crack the problems it might be so complex that it’s not much use – but that is where the huge computing power available to the national communications agencies would matter – and so Cameron’s remarks do point even more strongly to no P=NP breakthrough.