Wednesday, December 17, 2014

MCPS' "Image Problem", 11 April 1994

A report prepared for the Society of MCPS Data Distribution
11 April 1994

As with other facets of call processing, image taking presents challenges that can be overcome only through understanding and foresight.  This document hopes to explain the problem as it is currently understood, and to present possible solutions to the reader.

Image Taking Today


An image is a memory dump to offline storage; a snapshot of the current state of the system. It normally takes from 45 to 90 minutes to create an image, and call processing is expected to be up and running all the while. When call processing updates protected memory while an image is being taken, the information is buffered until the dump is completed. If this buffer overflows, the process traps and aborts the image.

MCPS will have several call processing instances, which shared data. This implies that data will be updated more often than in a single call processor system.  If there are X writes to protected store with one call processor, then there may be N*X writes to protected store with N call processors under MCPS.  Consequently, the probability of buffer overflow during image taking (and therefore trapping) increases. But it is important that the probability of trapping does not increase.

Another problem is the possibility of creating an image on several call processors simultaneously. There may be a huge data bottleneck in this case. If the time to take simultaneous images is increased to more than a few hours, then the image taking time may well spill over into prime call processing time. This is truly undesirable.

Facts

  • Typically, images are taken during low-demand hours: from 1:00 AM to around 3:00 to 4:00 AM.
  • Images take 45 to 90 minutes to create.
  • Protected memory can be overwritten to a limited degree during the image taking process (256 writes maximum).
  • Updated data is time critical.  It must be distributed ASAP.
  • In MCPS, any call processing instance may have its image taken.
  • In MCPS, multiple call processing instances may have their images taken simultaneously.
  • Of course, the Customer does not want traps, and does not want any image to abort.

Questions


  • What kind of bottleneck does image taking cause?
  • What kind of bottleneck would simultaneous multiple image taking cause?

Function Calls


There are several functions provided to accommodate protected writes.  The impact of these functions range in politeness levels, from kind to brutal.

UNPROTECTDS and PROTECTDS

These routines may be used to remove data store protection but only in certain circumstances. Anyone can use these during restart code but only CIs may use these after restarts.  This is to protect from applications changing protected data during a dump.  Therefore, what do you do if you are not a CI and want to change protected store in non-restart code?

COND_UNPROTECTDS

This routine will unprotect DS if there is not a dump in progress. A boolean value is returned to indicate whether protection removal was possible [successful]. But what if I need to write to protected store even if a dump is in progress?

WRITE_PROTECTED_STORE

This will keep the dump in a consistent state. However, only a limited number of calls (256) to this routine can be made during a dump so use this sparingly.  Implication: this is not an acceptable call for our MCPS data updates!

UNSAFE_WRITE_PROTECTED_STORE

This is the same as WRITE_PROTECTED_STORE but does not try to keep the dump consistent. This is for people who are currently using WRITE_PROTECTED_STORE for things that do not need to be dumped.  NOTE: This is not for the general user!

INFORM_DSPROT_UPDATE

(We won't actually call this one; it's just FYI).  This procedure is called by WRITE_PROTECTED_STORE. This is used to inform the dump program that a piece of store is about to be changed.  The dumper can remember what was at this location so that consistent dumps can be made.

Solution 1: Local Buffering

When a call processor distributes updated data, it holds it for awhile.  (If it is having its image taken, it could hold this data until the image is completed.)  If other processors explain that they're busy getting their images taken, then the data is held until it is requested from all those processors who asked for it to be held. If nobody responds, the data times out and is deallocated.

When a processor is having its image taken and receives updated information, the processor responds that it can't accept the data yet. This processor then sets a flag to query the sender for the data when the image taking is over.

Advantage: data is locally buffered; memory usage is minimized.

Disadvantage: We might not be allowed to message that much.
Disadvantage: Local memory is limited.

Solution 2: Global Buffering

This is a variant of Local Buffering.  If messaging is more of a bottleneck than local RAM, then each processor buffers up and updates it receives, and performs its own update when image taking is complete.  In face, since 256 writes are "free" before the dumper traps, it may be possible to go ahead and write the first N updates (N<256) and buffer the remainder.

Advantage: This does not rely on ACKing: messaging is minimized.
Disadvantage: This is memory inefficient.  Instead of buffering the memory in one place, it now is buffered in potentially several places.
Disadvantage: Local memory is limited.

Solution 3: Pipe Dream


A hybrid between Local and Global Buffering is where each processor has access to a "status word" containing the state of all processors. In this way a processor would know who to distribute data to, and who to wait on.

Advantage: Data is locally buffered.
Advantage: ACKing is minimized.
Disadvantage: The "status word" may not be feasible to implement, or may not exist.
Disadvantage: Local memory is limited.



Tuesday, November 25, 2014

Fun with opcodes

"If I were to implement a language now, I'd write a very minimal core suitable for bootstrapping. ... Think of a handful of ops. Think very low level. (Think something a little higher than the universal Turing machine and the lambda calculus and maybe a little bit more VMmy than a good Forth implementation, and you have it.) If you've come up with something that can replace XS, stop. You're there. Do not continue. That's what you need." (Chromatic, January 2013) 

In September or October I started thinking about that, and began to play with a tiny interpreter written in Perl that processed a rather loose version of Lua opcodes.

Lua includes a register-based virtual machine (VM) and has a uniquely light-and-performant driven view of interpreters.  Using Perl to implement a sort-of Lua VM opcode interpreter let me play with the concepts without having to really write very much, because Perl is nothing if not excellent at tokenizing strings and tearing apart text.

Here's the core loop.


my %R   = (); # registers
my %K   = (); # constants
my %U   = (); # "upvars"
my $PC  = 0;  # program counter
my $FPF = 0; # ???

my @prg = <DATA>;

while( $PC < @prg )
{
   my $line = $prg[ $PC ];
   my ($opcode, $a, $b, $c, $d) = split ' ', $line;

   $PC++;
  
   next unless $opcode;
  
   given( lc $opcode )
   {
      when (/ffd2/)         { print $R{$a}; print " " if $b eq '\s';  print "\n" if $b eq '\n' }
      when (/nl/)            { print "\n" }
     
      when (/clr/)          { $R{$_} = '' for $a .. $b }
      when (/move/)          { $R{$a} = $R{$b} }
      when (/loadk/)         { $R{$a} = $b     }
      when (/loadbool/)        { $R{$a} = $b? 1 : 0; $PC++ if $c }
      when (/loadnil/)        { $R{$_} = 0 for $a..$b }
      when (/getupval/)     { $R{$a} = $U{$b} }
     
      when (/gettabup/)     { $R{$a} = $U{$b}->{ $c } }
      when (/gettable/)     { $R{$a} = $R{$b}->{ $c } }
     
      when (/settabup/)     { $U{$a}->{ $b } = $R{$c} }
      when (/setupval/)     { $U{$b} = $R{$a} }
      when (/settable/)     { $R{$a}->{$b} = $c }
     
      when (/newtable/)     { $R{$a} = {} } # size = B,C
     
      when (/self/)         { $R{$a+1} = $R{$b};
                              $R{$a} = $R{$b}->{$c} }
                       
      when (/inc/)            { $R{$a}++ }
      when (/dec/)            { $R{$a}-- }
      when (/bz/)           { $PC += $b unless $R{$a} }
      when (/bnz/)          { $PC += $b if     $R{$a} }

      when (/add/)          { $R{$a} = $b + $c }
      when (/sub/)          { $R{$a} = $b - $c }
      when (/mul/)          { $R{$a} = $b * $c }
      when (/div/)             { $R{$a} = $b / $c }
      when (/mod/)          { $R{$a} = $b % $c }
      when (/pow/)            { $R{$a} = $b ** $c }
      when (/unm/)          { $R{$a} = -$R{$b} }
      when (/not/)          { $R{$a} = ~$R{$b} }         # ?
      when (/len/)          { $R{$a} = length $R{$b} }  # ...if scalar
                                     # $#R{$b}          # ...if hash
                                   
      when (/concat|cat|join/)    { my $sp = $R{$d}? ' ' : ''; $R{$a} = join( $sp, @R{$b..$c} ) }
           
      when (/ju?mp/)        { $PC += $a; closeAllUpvalues($R{$a}+1) if $a }
      when (/j?eq/)            { $PC++ if ( $b == $c ) != $a }
      when (/j?lt/)            { $PC++ if ( $b < $c ) != $a }
      when (/j?le/)             { $PC++ if ( $b <= $c ) != $a }
     
      when (/test/)         { $PC++ unless $R{$b} <=> $c }
      when (/testset/)        { ( $R{$b} <=> $c )? $R{$a} = $R{$b} : $PC++ }
 
      when (/call/)         { @R{$a..$a+$c-2} = call( @R{$a..$a+$b-1} ) }
     
      when (/tailcall/)     { call(@R{$a..$a+$b-1}) }
     
      when (/return/)       { @R{$a..$a+$b-2} }
     
      when (/forloop/)        { $R{$a} += $R{$a+2};
                              $PC += $b if $R{$a} <= $R{$a+1} }
     
      when (/forprep/)        { $R{$a} -= $R{$a+2}; $PC += $b }
     
      when (/tforcall/)        { @R{$a+3..$a+2+$c} = call( $R{$a..$a+2} ) }
     
      when (/tforloop/)        { if ( $R{$a+1} ) {
                                $R{$a} = $R{$a+1};
                                $PC += $b
                            }}
     
      when (/setlist/)        { $R{$a}->{ ($c-1) * $FPF + $_ } = $R{$a+1}
                                    for 1..$b;
                            }
     
      when (/closure/)        { $R{$a} = closure(proto($b)) }
      when (/vararg/)        { $R{$_} = 'vararg' for $R{$a} .. $R{$a+$b-2} }                   
     
   }; 
}





Tuesday, January 28, 2014

Subversive Metadata for Existing Commodore Images

SYNOPSIS

Jim Brain has suggested a way to encode optional metadata into Commodore images.  Though there are problems with his suggestion, it has merit.

METHOD

Jim's suggestion is to put optional metadata into the final sector of the directory.  The reason given is that this sector is seldom used, since the directory is seldom filled up or exceeded, although this does happen from time to time.

The reason for making this metadata optional is because this sector can be used for other nonstandard purposes, as well as for directory entries.

METADATA

What sort of metadata could go into this block?  There is a lot of useful, but not critical, information that could go there.

1. Magic Strings.  A "magic string" is a short, constant data string that indicates the overall structure of the image.  This string could be scanned for, regardless of the file size, to verify how the file should be parsed.  For example, a D64 might have a magic string of "1541 Digital Image, 2014 January"-- a string that is highly unlikely to show up in any D64 file.  But if present, the parser can be certain that it's a D64 file.

2. Nonstandard Sizes.  Nonstandard image size data could go here.   For example, a byte that indicates the number of tracks present for this image could allow a D64 with 255 tracks, or as few as 18 tracks (stopping at the Directory track).

3. Nonstandard Formats.  Metadata may indicate that the image's format has been altered in specific ways.  For example, the BAM might be nonexistent, or error data is stored in data blocks as a file starting at a particular T/S link.  For that matter, the entire image may be rearranged, with the header at Block 0, the Directory pointed to with a T/S link, error data at another T/S link, and a disk structure having a variable number of tracks with 256 sectors each.  This sort of radical departure would require easy detection of a Magic String of course.



Absurd Commodore Disk Image Format, version 3

Whereas previously I tried to parameterize every possible physical image format, this time I'm just focusing on a more abstract but Commodore-friendly structure.  My purpose is to define a simpler format that is quite flexible, which carries data that can be transferred onto a true physical image with a minimum of fuss.

OVERVIEW

This meta-disk uses a virtual disk format with 256 sectors per track and a variable number of tracks (64k per track).  The image begins with Track 0, and has a maximum possible track number of 255. 
   
The number of tracks present in an image is always computable as:

    Number of Tracks = [Image Size in Bytes] / 65536;
Similarly, the total number of sectors present in an image is known:

    Sectors Per Track = 256;
    Number of Sectors = [Image Size in Bytes] / 256;

NO BAM

This format has no need for a Block Allocation Map (BAM). Being an image designed for virtual use rather than physical media, such a map would be presumably constructed and maintained in memory as the image is used.  If its contents are written to a physical format (e.g. a D64), the BAM would
be calculated as the target image is built, or the new image would be validated by some other means at hand.

I. Header block, 256 bytes.

   This is addressed as sector 0 of track 0, which is always a "null"
   pointer reference for data blocks.
  
   This block contains information about the disk image,
   plus meta-data found in every header block of a Commodore disk.
  
   IMAGE HEADER
  
   $00-$0c Magic Header ASCII = 'ABSURD FORMAT'
   $0d     $00    
   $0e     Header version
   $0f     $00
   $10-$1f Image Label, $a0 terminated
   $20-$21 First directory block (0/0 = none)
   $22-$23 First error block (0/0 = none)
  
   (remaining bytes thru $3f Reserved)
  
   DISK HEADER
  
   $40-$4f Disk label, $a0 terminated
   $50     $a0
   $51-$52 Disk ID
   $53     $00
   $54-$55 DOS Type and Version
   $56     $00

   (remaining bytes thru $ff Reserved)

II. Directory Block, 256 bytes.
    Standard Commodore format.  Contains up to eight directory entries.
   
III. File Block, 256 bytes.
     Standard Commodore format.
   
IV. Error Block, 256 bytes.
    Similar in structure to a file block, but contains up to 254 error bytes
    per Error Block, corresponding to sector read errors (usually for 1541 error
    protection schemes).  A full 1541 image requires three Error Blocks.