Tuesday 17 December 2013

Infinite Snowflake

So it's close to the Christmas Holiday season, so I thought I would spend some time writing something seasonal.   My son, who is rather mathematically minded, was asking me about finding reoccurring digits in reciprocals of primes, for example 1/7, 1/11, 1/13 etc., and somehow this got me looking at the binary digits of Pi, and after a little more browsing around wikipedia onto the Thue-Morse binary sequence.

The Thue-Morse binary sequence starts with zero and one successively appends to the existing sequence the boolean compliment of the sequence so far.   One interesting feature is that a turtle graphics program can be written to control the turtle by feeding it the successive digits from the sequence so that:
  • A zero moves the cursor forward by a step
  • A one turns the cursor anti-clockwise by 60 degress (or pi/3 radians)
 ..and a Koch snowflake is drawn.  So, I've implemented this in C and obfuscated it a little just for fun:

#include<stdio.h>
#include <math.h>
#define  Q (1<<9)
#define M /**/for
#define E(b,a) {\
J q=1^(X+b)[3+Q*\
a];printf("%c%c%\
c",q,q,q);/*//*/}
int /*/*/ typedef
#define  W double
#define  z (Q<<5)

       J;J X[3+(Q              *Q)]
     ,t[z       ] ;J          main(
    ){ W         o= Q        >>1,V=
   o/5,           a=0;      M (1 [X
   ]=1;           X[1]         <z;X
  [1 ]             *=2)        for(
  X[2]             =0;X        [2]<
  X[1]             ;X[2        ]++,
  t[X[             2]+X        [1]]
  =1^t             [X[2        ]]);
  for(             0[X]        =0;X
  [0]<             3;0[        X]++
   )for           (X[2]        =0;X
   [2]<           z;X[         2]++
    )if(         t[X[          2]])
     a-=(       M_PI           /3.0
       );else{o+=          cos(a ); V+=

sin(a);X[3+( int)o+Q*(int)V]|=1;}printf(
"P6 %d %d 1 ",Q,Q);M(1[X] =0;X[1]<Q;X[1]
++)M(2[X]=0;X[ 2]<Q;X[2]++)E(2[X],X[1]);
return 0;} /* Colin Ian King 2013    */

To build and run:
gcc koch-binary.c -lm -o koch-binary 
./koch-binary | ppmtojpeg > koch-binary.jpg
And the result is a koch-snowflake:


The original source code can be found here. It contains a 512 x 512 turtle graphics plotter, a Thue-Morse binary sequence generator and a PPM output backend. Anyway, have fun figuring out how it works (it is only mildly obfuscated) and have a great Christmas!

Sunday 15 December 2013

Detecting System Management Interrupts

System Management Mode (SMM) is a special operating mode on x86 processors that temporarily jumps from normal execution and executes specialised firmware code in a high privilege before returning back.  SMM is entered via the System Management Interrupt (SMI) and is intented to work transparently to the operating system.

For example, SMM can be used to handle shutdown if CPU temperature is too high, perform transparent fan control, handle special system events (e.g. chipset errors), emulate hardware (non existing or buggy hardware) and a lot more besides.

SMM in theory cannot be disabled by the operating system and have been known to interfere with the operating system even though is it meant to be transparent.  SMIs steal CPU cycles from the system - CPU state has to be stored and restored and there are side effects because of flushing out of the write back cache.  This CPU cycle stealing can impact real time behaviour and in the past it has been hard to determine how frequently SMIs occur and hence how much potential disruption they bring to a system.

When the CPU enters SMM the output pin SMIACT# is asserted (and all further memory cycles are redirected to a protected memory for SMM).  Hence one could use a logic analyser on SMIACT# to count SMIs.   An alternative is to have a non-interruptible thread on a CPU checking time skips by constantly monitoring the Time Stamp Counter (TSC) but this is a CPU expensive operation.

Fortunately, modern Intel CPUs (such as Ivybridge and Haswell) have a special SMI counter in a Model Specific Register. MSR_SMI_COUNT (0x00000034) is incremented when SMIs occur, allowing easy detection of SMIs.

As a quick test, I hacked up smistat that polls MSR_SMI_COUNT every second.  For example, pressing the backlight brightness keys on my Lenovo laptop bumps the counter and this is easy to see with smistat.   So this MSR provides some indication of the frequency of SMIs, however, it of course cannot  inform us how many CPU cycles are stolen in SMM.   Now that would be a very useful MSR to add to the next revision of the Intel silicon...

Wednesday 11 December 2013

fwts 13.12.00 released

Version 13.12.00 of the Firmware Test Suite has been released today.  This latest release includes some of the following new features:
  • ACPI method test, add _IPC, _IFT, _SRV tests
  • Update to version 20131115 of ACPICA
  • Check for thermal overrun messages in klog test
  • Test for CPU frequency maximum limits on cpufreq test
  • Add Ivybridge and Haswell CPU specific MSR checks
  • UEFI variable dump:
    • add more subtype support on acpi device path type  
    • handle the End of Hardware Device Path sub-type 0x01
    • add Fibre Channel Ex subtype-21 support on messaging device path type
    • add SATA subtype-18 support on messaging device path type
    • add USB WWID subtype-16 support on messaging device path type
    • add VLAN subtype-20 support on messaging device path type
    • add Device Logical Unit subtype-17 support on messaging device path typ
    • add SAS Ex subtype-22 support on messaging device path type
    • add the iSCSI subtype-19 support on messaging device path type
    • add the NVM Express namespace subtype-23 support on messaging device path type
..and also the usual bug fixes. 

For more details, please consult the release notes
 
The source tarball is available at:  http://fwts.ubuntu.com/release/fwts-V13.12.00.tar.gz and can be cloned from the repository: git://kernel.ubuntu.com/hwe/fwts.git

The fwts 13.12.00 .debs are available in the firmware testing PPA and will soon appear in Ubuntu Trusty 14.04

And thanks to Alex Hung, Ivan Hu, Keng-Yu Lin their contributions and keen eye for reviewing the numerous patches and also to Robert Moore for the on-going work on ACPICA.

Tuesday 10 December 2013

Digging into TRIM

Enabling the discard mount option to perform auto trimming on a SSD has some downsides.  The non-queued trim command can incur a large performance penalty on deletes; the driver needs to finish pending operations, then peform the trim command before it can resume normal operation again.  Queued TRIM support has been added to the 3.12 kernel which will help improve this issue, however, one requires hardware that supports the Serial ATA revision 3.1 Queued Trim command.

Trimming can trigger internal garbage collection on some firmware and causing some performance impact when one leasts expects it, so enabling TRIM via the discard mount flag may be suboptimal.  It is therefore better to batch up discards and run fstrim periodically when a machine is idle in terms of minimising performance impact (this is also more power efficient too).

For the curious, how much is being discarded when one runs fstrim? Fortunately the kernel has a tracepoint added to ext4_trim_extent and this enables one to observe the block device, allocation group, starting block of the free extent in the allocation group and number of blocks to TRIM.

With debugfs mounted one can easily observe this using:

 echo 1 | sudo tee /sys/kernel/debug/tracing/events/ext4/ext4_trim_extent/enable  
 sudo cat /sys/kernel/debug/tracing/trace_pipe | grep ext4_trim_extent  

then invoke fstrim from another terminal and one will observe:

fstrim-4909  [003] ....  6585.463841: ext4_trim_extent: dev 8,3 group 1378, start 2633, len 829
fstrim-4909  [003] ....  6585.474926: ext4_trim_extent: dev 8,3 group 1378, start 3463, len 187
fstrim-4909  [003] ....  6585.484014: ext4_trim_extent: dev 8,3 group 1378, start 3652, len 474
...

The deeper question is therefore how frequently should run fstrim?  It is hard to say exactly, since it is use-case dependant.  However, anecdotal evidence seems to suggest running fstrim either daily or weekly.