I have had quite a break in posting to my blog, mostly because I spent last year collecting and playing around with vintage computers. As a kid I only had C64 and Amiga 1200 before I got a PC, so I decided to make up for it and buy a couple of machines popular in my country those days. It turned out to be so much fun that I got completely lost in it. I was absolutley amazed how much retrocomputing is alive and how many people are actually actively involved in it.
Let's start with Atari. 8-bit Atari machines were one of the most powerful home computers of the late seventies and early eighties. They featured an incredibely powerful graphics chip, Antic, which allowed fully programmable graphics modes. You could even use more than one screen resolution at a time, a trick that was later only possible on Amiga thanks to the Copper chip. No wonder if you take into account that both Atari and Amiga graphics chipsets were designed by the same man, Jay Miner.
There is a lot of great software written for the 8-bit Atari computers, and new one is still being developed. My favourite game for 8-bit Atari is Yoomp!, created in 2007 by a demoscene group taQuart, and there are also many great tools, like SpartaDOS X, which gives you the power comparable to CP/M or MS-DOS. Once I put SpartaDOS X on a programmable cartridge I never looked back at any other Atari DOS again. SpartaDOS X also works great with new Atari storage devices, like SIO2SD or Side, which use modern flash memory and not only can seamlessly replace your regular Atari disk drive (Side can also work as a hard drive), but also allow you to exchange data with a regular PC easily. Speaking of hardware - today, apart from buying a flash based disk drive for your Atari, you can also upgrade memory (up to 1MB, bank switched), install a graphic card (VideoBoard XE) or even a CPU accelerator (based on 16-bit MOS 65c816, compatible with 8-bit MOS 6502 originally mounted in Atari 400/800/XL/XE).
16-bit Atari computers can also be upgraded. Two most popular upgrades are Satandisk and Ultrasatan, which are flash based hard drives compatible with Atari ST/STE and Falcon. You can also replace original disk drive with HxC and use floppy images saved on regular pendrive as floppy disks. This is a very comfortable solution, because quality floppies are becoming more and more difficult to buy (those produced today are much less reliable than original ones). If you have enough RAM in your Atari, you can even connect to the Internet thanks to NetUSBee device. Additional RAM is required not by the device itself, but by the software. I have Atari STFM with 4MB RAM and I can comfortably use some simple software for FTP or IRC, I even managed to open a few simple web pages with Crystal Web Browser. Unfortunately in most cases I ended up seeing garbage (I use freeware CAB v1.5, which comes form 1996 and does not support any modern web standard) or running out of memory. Still, connecting to the global network from a 16-bit computer, designed before the beginning of the Internet revolution, is an unforgettable experience.
Atari had many comptetiors at the time. One of them was Commodore, run by Jack Tramiel, who later left the company and bought Atari. Commodore machines were very famous in 1980s and 1990s due to two very popular lines of computers: VIC-20/C64 and Amiga. VIC-20 was the first home computer to sell one million units, and C64 is listed in the Guiness World Records as the best selling single computer model in history, with estimated number of around 12.5 million units sold. Unfortunately, I don't have any VIC-20 in my collection, but I have a C64 and I use two hardware extensions with it: Epyx Fastload Reloaded cartridge and SD2IEC flash based disk drive emulator. Epyx has built-in software to accelerate disk operations (up to five times), but if you don't want to buy a cartridge you can use SJLOAD, which is a software only fastloader. From my experience SJLOAD works as well as Epyx, but I just find the cartridge more comfortable to use (plus it has some additional software, like memory monitor, extended DOS commands, etc). As for SD2IEC - it's quite cheap and works with most software, but unfortunately cannot serve as a full replacement for the original disk drive. A real 1541 has it's own MOS 6502 CPU and RAM, which is extensivelly used by some utilities, like fastloaders, and although SD2IEC can emulate some of them, it does not contain a full MOS 6502 emulation and therefore some programs, like GEOS, will not work with SD2IEC. So if you are not tight on budget, I'd recommend buying a device like Ultimate or UK1541, both of which offer full 1541 hardware emulation.
If you are lucky Amiga owner, you can also enjoy a few interesting hardware extensions. You can replace your floppy disk with HxC, or Gotek, which is much cheaper option than HxC. I have Gotek drive emulator working in my Amiga 600 and so far experienced absolutely no problems with it, so in my opinion it's worth buying. If you have Amiga with IDE controller on board (like A600 or A1200), you can buy a very cheap CF to IDE adapter, which allows you to use Compact Flash cards as hard drives, because they have built-in controllers which work with IDE protocol. Amiga also features probably the most powerful (and most expensive) CPU accelerators in the market. Some of them, like FPGA based Vampire 600, can speed up your machine up to one hundred times! If you have Amiga 1200 you can extend it with PowerPC CPU card, 256 MB RAM, dedicated graphics card, install the latest version of Amiga OS (an operating system designed for Amiga computers, still actively developed) and work on it almost like on any other modern computer. It's because Amiga hardware architecture, combined with dedicated software, makes it much less resource hungry than an Intel based PC.
There is also one more computer brand that holds a special place in my heart: Sinclair. Sir Clive Sinclair is often compared to Steve Jobs, not only because of his temper, but also because he was one of the greatest visioners of his era. He was the first one to introduce pocket calculators in 1972 and pocket TV in 1978, he also introduced the first affordable (priced less than 100 GBP, a few times less than the competition) home computer to the British market: ZX80. It featured a 3.5MHz CPU, only 1kB RAM, no high resoultion graphics (only text mode), no sound chip and no disk drive - you could only use a tape recorder as a storage device. It was very little even those days, but ZX80 was extremely cheap and became a huge success. Sir Clive Sinclair supposedly said that at that price, everyone would want a computer, even if they had absolutely no idea what to do with it. Apart from that, Sinclair devices were always designed to look slick and elegant. Even today, white ZX80 looks beautiful, and so do all later black models. ZX80 featured a built-in Basic interpreter and, despite it's horrible keyboard, allowed users to write their own programs, and many future programmers began their careers from it.
ZX80's successor, ZX81, featured a black case and the same hardware capabilities, but due to more compact chip design it was even cheaper. It also fixed a lot of ZX80 problems (especially screen flickering) and became the first European computer to sell over one million units. ZX81 became successful in United States, where it was sold by Timex as TS1000. In fact, a company called Zebra Systems sells ZX81 kits until today.
An essential hardware extension for every ZX81 is a memory pack, which adds more RAM to the system. It's true that 1kB may be enough even to play chess, but most software for "Zeddy" requires at least 16kB RAM. You can also use your PC as a tape recorder and make tapeutils load software into ZX81 - just remember to use mono audio lead (regular stereo leads will not work) and set the PC audio output volume to maximum (ZX81 requires a strong input signal). If it's not enough for you, there is a ZXpand interface, which adds 32kB RAM, allows instant software loading from a flash card, and features an AY sound interface.
But the most successful Sinclair computers were ZX Spectrum 48k and it's descendants. It was also the most often cloned computer, especially in communist countries, which were cut off from the world computer markets due to Cocom regulations. As a consequence, most of Sinclair fans beyond Britain are located in Eastern Europe. Russian ZX Spectrum scene is especially strong, and they even developed their own, extended models, most famous of them being Pentagon and Scorpion.
The most problematic hardware part of ZX Spectrum was its keyboard, but you can easily buy a new membrane and replace it yourself, following one of many online tutorials - it requires only a screwdriver, and a bit of patience.
If you have a fully functioning Spectrum you can, just as with ZX81, use a PC as a tape recorder. There are two programs that I would recommend using: OTLA and PlayTZX. The first one recognizes a lot of different tape formats (TAP, TZX) and can work in "turbo mode", which due to a smart audio signal modulation allows loading programs a few times faster. Unfotrunately, some games, especially copy protected, don't load with OTLA. In this case, you can try PlayTZX, or its Windows counterpart, winTZX. PlayTZX is a console only tool, which can work only with files encoded in TZX format (it's less popular format than TAP), while winTZX can work with both TAP and TZX files. On the other hand, TAP and TZX formats are very similar, and there are many tools to convert between those two formats to be found online. To avoid load errors remember to use a mono audio lead and very loud audio output (just as with ZX81). It is also important to use verified TAP and TZX files: I found that many of them available online are somehow broken, and although they work with emulators, they fail to load into real hardware. So far the most reliable source of Sinclair software I know is World Of Spectrum - I never found a single file which would refuse to load with a real computer.
And, of course, just as for all aforementioned computers, there is also a flash based storage device for ZX Spectrum: Divide. Just as ZXpand, it connects directly to the system bus through the expansion port, which allows you not only to use TAP and TZX files, but also emulator snapshots (SNA). It means that you can, for example, freeze a game state in a software Spectrum emulator on PC and load it directly into Speccy.
There are of course dozens of computers from the "good old times" that you can have fun with: Apple, Acorn, Amstrad, even an old PC. If you have such computer - don't throw it away! Instead, try to put a new life in it and give it to someone who can still find it enjoyable - like your kid or a geek friend. If not, just sell it online - there are many people out there who will be happy to have it.
Saturday, June 6, 2015
Friday, August 22, 2014
Pushing the limits
Today I'm not going to write about ultra fast Hadoop clusters or insanely scalable, globally-distributed databases. This time I want to take you on the journey in the totally opposite direction, straight into the rabbit hole.
Let's say you want to display a nice looking rainbow on the screen of you TV, like this one:
Because a static picture is a little boring, you also want to animate it, so that the rainbow moves up (or down) the screen. The question is: what hardware do you need for this and what will be the software requirements?
What if I tell you that all you need is a computer with 1.8 MHz CPU, 48 kilobytes of RAM and the program that takes 29 (twenty nine) bytes? Yes, bytes. Less than the number of letters in this sentence. If you don't believe me, you can download a zip archive containing the software from this location. Inside you will find a file rainbow.xex which you can run on any Atari 800/800XL emulator, or even on the real hardware if you still have one (you can use a device like SIO2SD to transfer files to the Atari). I have run it on a real Atari 800XL connected to a plasma TV through a composite video lead, and it works perfectly.
How is that possible? The secret lies in talking directly to hardware. 8-bit computers have very limited resources, so any software layer which is not absolutely necessary is just a waste of memory and CPU cycles. A simple example is a boolean value, which can have one of two states: true or false. Any computer in the world, no matter how simple or complicated, needs only one bit to understand boolean values: 1 for true and 0 for false. Since a byte consists of 8 bits, you can store 8 different boolean values in one byte. Yet, in today's software world, the Java boolean primitive takes entire byte, and the simplest Boolean class:
Going back to the example, the algorithm to make Atari display the rainbow is quite simple:
1. Initialize graphic mode.
2. Read current scanline from Atari display chip - Antic. Antic creates image on a TV screen drawing it line by line, from left to right, 50 times (PAL) or 60 times (NTSC) per second. The horizontal resolution of an Atari screen is 240 pixels (including borders), which means that the scanline number can have values from 0 (first line) to 239 (last line).
3. If the line number is 0, increase the counter, which is used to calculate the colour palette shift. Increasing the counter on every new frame adds the animation effect to the rainbow picture.
3. Wait for Antic to finish drawing the current line on the screen (we don't want to change color in the middle of the line).
4. Change background colour to the value obtained from Antic (Atari has a total palette of 256 colors) summed up with the current shift value.
5. Repeat from point 2.
This algorithm can be easily translated into a C program:
Fortunately, the cc65 compiler provides some optimizations: you can use "‑Oi" and "‑Os" command line switches to inline all subroutines and get rid of jsr instructions, you can also make local variables to be stored under fixed memory address instead of the stack through "‑Cl". Also, using "‑Or" switch enables register variables, which is particularly interesting, because it does not make CPU use physical registers (since MOS 6502 processor used in the 8-bit Atari has only one general purpose register, called accumulator), but it makes variables to be stored in first 256 bytes of physical memory, called zero page. The advantage of using zero page is using less CPU cycles to access it: 8-bit memory addresses (from 0 to 255) are decoded faster by 8-bit processing unit than 16-bit addresses (from 0 to 65535 - the memory limit in Atari 800XL is 64KB).
Let's see what happens if we turn the optimizations on:
But we can still make it smaller, using some knowledge the compiler does not have. First, we don't need to init the counter stored at $cb memory address, because we don't care about it's initial value (it gets increased infinitely anyway), so we can get rid of "sta $cb" instruction. Second, we don't need "lda $cc" right after "sta $cc" and "sta $d40a", because the "sta" instruction doesn't change the accumulator state, so there's no need to reload it. We can also replace the whole procedure of loading counter from memory into accumulator, adding 1 and storing it back in memory, with only one instruction - "inc $cb" - which increases the memory value by 1. Finally, we don't need "clc" to clear the carry flag (the flag indicating that a mathematical operation resulted in value which does not fit in 8 bits) before adding line number and counter, because Atari colour palette can have only 256 values, so it doesn't matter if the addition result fits in 8 bits or not.
After making the changes, the code now looks as follows:
Lessons learned:
1. Compilation with default compiler options sucks.
2. A smart compiler can do a really great job optimizing code.
3. There is always a way for a programmer to optimize it even more.
4. Programming old computers is fun.
Let's say you want to display a nice looking rainbow on the screen of you TV, like this one:
What if I tell you that all you need is a computer with 1.8 MHz CPU, 48 kilobytes of RAM and the program that takes 29 (twenty nine) bytes? Yes, bytes. Less than the number of letters in this sentence. If you don't believe me, you can download a zip archive containing the software from this location. Inside you will find a file rainbow.xex which you can run on any Atari 800/800XL emulator, or even on the real hardware if you still have one (you can use a device like SIO2SD to transfer files to the Atari). I have run it on a real Atari 800XL connected to a plasma TV through a composite video lead, and it works perfectly.
How is that possible? The secret lies in talking directly to hardware. 8-bit computers have very limited resources, so any software layer which is not absolutely necessary is just a waste of memory and CPU cycles. A simple example is a boolean value, which can have one of two states: true or false. Any computer in the world, no matter how simple or complicated, needs only one bit to understand boolean values: 1 for true and 0 for false. Since a byte consists of 8 bits, you can store 8 different boolean values in one byte. Yet, in today's software world, the Java boolean primitive takes entire byte, and the simplest Boolean class:
public final class Boolean
{
public static final Boolean TRUE = new Boolean(true);
public static final Boolean FALSE = new Boolean(false);
private final boolean value;
public Boolean(boolean value) {
this.value = value;
}
public boolean booleanValue() {
return value;
}
}
compiles in Java 7 to 451 bytes of bytecode, not to mention it requires a few hundred megabytes runtime environment to load. This is the cost of having programmer friendly, enterprise grade, programming tools and languages.Going back to the example, the algorithm to make Atari display the rainbow is quite simple:
1. Initialize graphic mode.
2. Read current scanline from Atari display chip - Antic. Antic creates image on a TV screen drawing it line by line, from left to right, 50 times (PAL) or 60 times (NTSC) per second. The horizontal resolution of an Atari screen is 240 pixels (including borders), which means that the scanline number can have values from 0 (first line) to 239 (last line).
3. If the line number is 0, increase the counter, which is used to calculate the colour palette shift. Increasing the counter on every new frame adds the animation effect to the rainbow picture.
3. Wait for Antic to finish drawing the current line on the screen (we don't want to change color in the middle of the line).
4. Change background colour to the value obtained from Antic (Atari has a total palette of 256 colors) summed up with the current shift value.
5. Repeat from point 2.
This algorithm can be easily translated into a C program:
#include <atari.h>
#define SDMCTL (*((unsigned char*)0x22F))
int main() {
unsigned char line, counter = 0;
SDMCTL = 0; // disable display in BASIC screen area
while (1) {
line = ANTIC.vcount; // read current screen line
if (!line) counter++; // increase color shift on new frame
ANTIC.wsync = line; // block CPU until vertical sync
GTIA_WRITE.colbk = line + counter; //change background color
}
return 0;
}
To compile this program on a PC, you can use a cross-platform cc65 compiler:
cl65 -t atari -o rainbow.xex rainbow.cHowever, the resulting executable is 1104 bytes long. Let's make the compiler to output the assembly code to see the CPU instruction list it produced:
cc65 -t atari rainbow.cThe assembly source code in the resulting rainbow.s file looks like this:
jsr decsp1
lda #$00
jsr pusha
ldx #$00
lda #$00
sta $022F
L0008: ldx #$00
lda $D40B
ldy #$01
sta (sp),y
ldy #$01
ldx #$00
lda (sp),y
jsr bnega
jeq L000E
ldy #$00
ldx #$00
lda (sp),y
pha
clc
adc #$01
ldy #$00
sta (sp),y
pla
L000E: ldy #$01
ldx #$00
lda (sp),y
sta $D40A
ldy #$01
ldx #$00
lda (sp),y
jsr pushax
ldy #$02
ldx #$00
lda (sp),y
jsr tosaddax
sta $D01A
jmp L0008
ldx #$00
lda #$00
jmp L0002
L0002: jsr incsp2
rts
Quite long, isn't it? If you understand the assembly language, you will probably notice a few problems here. First, the program jumps a few times to some strange subroutines (like pusha, bnega, tosaddax, etc.), which does not seem necessary. Second, it uses a lot of reads and writes to the stack (although the algorithm uses only two local variables (line and counter). Third, some instructions are completely unnecessary (like LDX, which loads data to never used CPU index register X).Fortunately, the cc65 compiler provides some optimizations: you can use "‑Oi" and "‑Os" command line switches to inline all subroutines and get rid of jsr instructions, you can also make local variables to be stored under fixed memory address instead of the stack through "‑Cl". Also, using "‑Or" switch enables register variables, which is particularly interesting, because it does not make CPU use physical registers (since MOS 6502 processor used in the 8-bit Atari has only one general purpose register, called accumulator), but it makes variables to be stored in first 256 bytes of physical memory, called zero page. The advantage of using zero page is using less CPU cycles to access it: 8-bit memory addresses (from 0 to 255) are decoded faster by 8-bit processing unit than 16-bit addresses (from 0 to 65535 - the memory limit in Atari 800XL is 64KB).
Let's see what happens if we turn the optimizations on:
cc65 -Cl -Osir -t atari rainbow.cThe resulting assembly code is now much smaller:
lda #$00
sta L0004
sta $022F
L000A: lda $D40B
sta L0003
lda L0003
bne L0010
lda L0004
clc
adc #$01
sta L0004
L0010: lda L0003
sta $D40A
lda L0003
clc
adc L0004
sta $D01A
jmp L000A
To produce a working executable, we have to assemble and link it:
ca65 rainbow.s && cl65 -t atari -o rainbow.xex rainbow.oStill, the resulting code is 630 bytes long. This is because the compiler still includes some Atari specific code from the standard library. We can work around this using an assembler (like xasm or MADS). But first, we need to clean up the assembly code a bit:
org $2000 ; start address
lda #$00 ; load accumulator with 0
sta $cb ; store it in memory
sta $022f ; disable display in BASIC screen area
loop
lda $d40b ; read current screen line into accumulator
sta $cc ; store it in zero page
lda $cc ; load current line number from memory
bne skip ; if it's not zero jump to code at 'skip' label
lda $cb ; load counter from memory into accumulator
clc ; clear carry flag
adc #$01 ; add 1 to accumulator
sta $cb ; store counter in memory
skip
lda $cc ; load current line number from memory
sta $d40a ; block CPU until vertical sync
lda $cc ; load current line number from memory
clc ; clear carry flag
adc $cb ; add counter to the line number
sta $d01a ; change background colour
jmp loop ; repeat
I added some comments to make clear what's going on in the code. So, let's assemble it:
xasm rainbow.s /o:rainbow.xexNow rainbow.xex is only 45 bytes long! Two first bytes are the executable file header ($FFFF) and the next two are memory address the program should be loaded into ($2000). The rest is pure CPU instruction list.
But we can still make it smaller, using some knowledge the compiler does not have. First, we don't need to init the counter stored at $cb memory address, because we don't care about it's initial value (it gets increased infinitely anyway), so we can get rid of "sta $cb" instruction. Second, we don't need "lda $cc" right after "sta $cc" and "sta $d40a", because the "sta" instruction doesn't change the accumulator state, so there's no need to reload it. We can also replace the whole procedure of loading counter from memory into accumulator, adding 1 and storing it back in memory, with only one instruction - "inc $cb" - which increases the memory value by 1. Finally, we don't need "clc" to clear the carry flag (the flag indicating that a mathematical operation resulted in value which does not fit in 8 bits) before adding line number and counter, because Atari colour palette can have only 256 values, so it doesn't matter if the addition result fits in 8 bits or not.
After making the changes, the code now looks as follows:
org $2000 ; start address
lda #$00 ; load accumulator with 0
sta $022f ; disable display in BASIC screen area
loop
lda $d40b ; read current screen line into accumulator
sta $cc ; store it in zero page
bne skip ; if it's not zero jump to code at 'skip' label
inc $cb ; increase counter in memory by 1
skip
lda $cc ; load current line number from memory
sta $d40a ; block CPU until vertical sync
adc $cb ; add counter to the line number
sta $d01a ; change background colour
jmp loop ; repeat
After assembling it with xasm, the resulting executable is now only 33 bytes long. However, we can still cut the instruction list down. You may notice that there is no need to load and store accumulator at $cc memory address, because its state doesn't change between "sta $cc" and "lda $cc" - so we can safely remove those instructions:
org $2000 ; start address
lda #$00 ; load accumulator with 0
sta $022f ; disable display in BASIC screen area
loop
lda $d40b ; read current screen line into accumulator
bne skip ; if it's not zero jump to code at 'skip' label
inc $cc ; increase counter in memory by 1
skip
sta $d40a ; block CPU until vertical sync
adc $cc ; add counter to the line number
sta $d01a ; change background colour
jmp loop ; repeat
As we got rid of another couple of bytes, rainbow.xex is now exactly 29 bytes after assembling.Lessons learned:
1. Compilation with default compiler options sucks.
2. A smart compiler can do a really great job optimizing code.
3. There is always a way for a programmer to optimize it even more.
4. Programming old computers is fun.
Saturday, July 26, 2014
How to deal with blocking operations
In distributed environment even simple things become complicated. One of the most trivial examples is a counter. If you have only one instance of an application running, then you can simply store the counter in a database table with the counter's id and value, for example:
I have prepared an example application which simulates such case. You can download a zipped archive from here. It was prepared in Linux, but in case you work in Windows you should also be able to compile it with Cygwin - just make sure to install mysql development libraries (you need mysql_config.exe binary in your PATH).
First, prepare the database and set up the tables. All example assume that you have a MySQL database running on localhost, with test database called "test" and password "root" for the root user. If your environment differs, modifiy respective variables:
When you run the resulting binary you should see the output similar to the following:
There are couple of ways to solve the problem. Some of them involve spending time and money to build a NoSQL cluster based on some fashionable technology, like Hadoop or Cassandra. A cheaper and smarter way involves implementing so called "optimistic locking". The main idea behind this technique is to decrease to the minimum the time you spend in lock. Operation based on optimistic locking takes three phases:
Optimistic locking is a good solution, but it still can lead to failures while updating counter value, and it also requires clients to implement some strategy on how to deal with update failure: "Should I repeat the operation?", "At what intervals?", "How many times before giving up?", etc.
Another way is to get rid of blocking opeartions at all, and replace them with non-blocking ones. It can be done easily by introducing queues. Putting a new value into a queue does not affect any existing values, so it doesn't need any read or write locks. With every new request you just insert a new row into the queue table, and there is a single, separate process which updates the counter and removes the rows it has read form the queue. Because there are no concurrent processes working on the counter, there is no problem of blocking. Also, the worker can read new inserts in batches instead of single records, which can give a huge performance boost with fast growing queue (if there are a hundred new tasks waiting in the queue, you can increase the counter by a hundred in one step). The queue is safe, because each insert has its own unique id, so deleting records from the queue does not interfere with inserting new ones. Also, when updating fails, the inserts are not lost, but they remain in the queue for later processing. The only drawback is that when you read the counter value it is still a little bit behind, but for purposes such as the number of visitors to the website, it can be easily accepted.
Going back to the example. Compile the code with:
| ID | VAL | ------------ | 0 | 1 |and increase its value with a simple query:
UPDATE counters SET val=val+1 WHERE id=0However, when there are many clients trying to increase the counter simultaneously (for example multiple frontends displaying the number of visitors to the website), you may experience some serious slowdowns. It's because updating a row in a database is a blocking operation, which means that during update the row is locked to prevent the situation when multiple process try to modify it at the same time. There are two basic types of locks: write locks and read locks. A write lock is a basic and most often used type of lock, which does not allow modifying a value while another change is in progress. You can still read the row value, but in this case two subsequent reads can return two different values, because the change could have taken place just between them. When this becomes an issue, you can use a read lock, which prevents other processes from reading the row until the change is done. Depending on how your database is configured, locking the counter row will become more or less painful, but it still needs to be done sequentially to ensure its value is correct. This way, simple operation of increasing the visitors counter can become a serious bottleneck to the whole website.
I have prepared an example application which simulates such case. You can download a zipped archive from here. It was prepared in Linux, but in case you work in Windows you should also be able to compile it with Cygwin - just make sure to install mysql development libraries (you need mysql_config.exe binary in your PATH).
First, prepare the database and set up the tables. All example assume that you have a MySQL database running on localhost, with test database called "test" and password "root" for the root user. If your environment differs, modifiy respective variables:
mysql -u root -proot test < counter.sqlNow, compile the example code which works on the counter:
make syncThis example simulates ten simultaneous blocking counter updates. Each transaction starts one second after the previous one, but it takes two seconds to complete, so the transactions overlap and block one another.
When you run the resulting binary you should see the output similar to the following:
Begin #1 Update #1 Begin #2 Update #2 Begin #3 Update #3 Commit #1 Begin #4 Update #4 Begin #5 Update #5 Commit #2 Begin #6 Update #6 Begin #7 Update #7 Commit #3 Begin #8 Update #8 Begin #9 Update #9 Commit #4 Begin #10 Update #10 Commit #5 Commit #6 Commit #7 Commit #8 Commit #9 Commit #10 Counter value: 10, time elapsed: 20.015499sYou can notice that commits do not take place immediately after updates. This is because each transaction must wait for all previous ones to complete. As a result the test takes around 20 seconds, which is the sum of time needed to finish all transactions. In this scenario, the more clients try to modifiy the counter, the longer it takes to complete. Finally, the system becomes overloaded, some of the operations time out, client processes fail to set the correct counter value, and the user experience is a disaster.
There are couple of ways to solve the problem. Some of them involve spending time and money to build a NoSQL cluster based on some fashionable technology, like Hadoop or Cassandra. A cheaper and smarter way involves implementing so called "optimistic locking". The main idea behind this technique is to decrease to the minimum the time you spend in lock. Operation based on optimistic locking takes three phases:
- read the value
- modify the value
- compare and swap
Optimistic locking is a good solution, but it still can lead to failures while updating counter value, and it also requires clients to implement some strategy on how to deal with update failure: "Should I repeat the operation?", "At what intervals?", "How many times before giving up?", etc.
Another way is to get rid of blocking opeartions at all, and replace them with non-blocking ones. It can be done easily by introducing queues. Putting a new value into a queue does not affect any existing values, so it doesn't need any read or write locks. With every new request you just insert a new row into the queue table, and there is a single, separate process which updates the counter and removes the rows it has read form the queue. Because there are no concurrent processes working on the counter, there is no problem of blocking. Also, the worker can read new inserts in batches instead of single records, which can give a huge performance boost with fast growing queue (if there are a hundred new tasks waiting in the queue, you can increase the counter by a hundred in one step). The queue is safe, because each insert has its own unique id, so deleting records from the queue does not interfere with inserting new ones. Also, when updating fails, the inserts are not lost, but they remain in the queue for later processing. The only drawback is that when you read the counter value it is still a little bit behind, but for purposes such as the number of visitors to the website, it can be easily accepted.
Going back to the example. Compile the code with:
make asyncThis will rebuild the code to use queue instead on changin the counter directly. When you now run it, you should see the output similar to the following:
Begin #1 Insert #1 Begin #2 Insert #2 Commit #1 Begin #3 Insert #3 Commit #2 Begin #4 Insert #4 Begin #5 Insert #5 Commit #3 Begin #6 Insert #6 Commit #4 Commit #5 Begin #7 Insert #7 Commit #6 Begin #8 Insert #8 Commit #7 Begin #9 Insert #9 Commit #8 Begin #10 Insert #10 Commit #9 Commit #10 Counter value: 20, time elapsed: 11.023697sAs you can see, the whole operation now took much faster to complete, because the new transactions didn't have to wait for the previous ones to finish.
Saturday, March 15, 2014
Hacking Linux executables with LD_PRELOAD code injection
Executable code can be stored on disk in many different formats. In MS-DOS, programs which didn't use more than one 64kB memory segment, could be simply saved in a COM file, which contained only machine code, with no additional metadata. When instructed to run such file, operating system loaded it into a first free memory segment at address 0x100, initialized code segment register (CS), data segment registers (DS, ES) and stack segment register (SS) to point to that segment and then passed control to the first instruction located at the beginning of the file. More complicated executables contained an EXE header with some additional informaton required by the operating system, like the number of memory blocks the program needs or initial values of the segment registers.
Nowadays, applications compiled for multitasking operating systems often use dynamically shared libraries, so the executable file headers also contain information about required libraries and functions included from those libraries. In Linux, you can get that data with readelf. For example, using command:
You can take advantage of the fact that the program uses a function from an external library to modify its behaviour without touching its code. All you have to do is to substitute strcmp with your own function. You can do it by writing your own dynamic library with custom strcmp and load it before the code of the users executable is initialized.
First, let's create a very simple library mylib.c with this code:
Now all you have to do is to inject the custom library code into the running program. Fortunately, Linux allows you to load your own dynamic libraries before starting any executable with LD_PRELOAD environment variable. We can take advantage of this feature - just compare the results of the two following commands:
Google used the same trick to create TCMalloc, which is a faster modification of the standard Linux malloc.
Nowadays, applications compiled for multitasking operating systems often use dynamically shared libraries, so the executable file headers also contain information about required libraries and functions included from those libraries. In Linux, you can get that data with readelf. For example, using command:
readelf -s /usr/bin/usersgives the following information (I stripped some of the output to increase readability):
Symbol table '.dynsym' contains 58 entries:
Num: Type Bind Vis Name
1: FUNC GLOBAL DEFAULT utmpxname@GLIBC_2.2.5 (2)
2: FUNC GLOBAL DEFAULT free@GLIBC_2.2.5 (2)
3: FUNC GLOBAL DEFAULT abort@GLIBC_2.2.5 (2)
4: FUNC GLOBAL DEFAULT __errno_location@GLIBC_2.2.5 (2)
5: FUNC GLOBAL DEFAULT strncpy@GLIBC_2.2.5 (2)
6: FUNC GLOBAL DEFAULT strncmp@GLIBC_2.2.5 (2)
7: FUNC GLOBAL DEFAULT _exit@GLIBC_2.2.5 (2)
8: FUNC GLOBAL DEFAULT __fpending@GLIBC_2.2.5 (2)
9: FUNC GLOBAL DEFAULT qsort@GLIBC_2.2.5 (2)
10: FUNC GLOBAL DEFAULT textdomain@GLIBC_2.2.5 (2)
11: FUNC GLOBAL DEFAULT endutxent@GLIBC_2.2.5 (2)
12: FUNC GLOBAL DEFAULT fclose@GLIBC_2.2.5 (2)
13: FUNC GLOBAL DEFAULT bindtextdomain@GLIBC_2.2.5 (2)
14: FUNC GLOBAL DEFAULT dcgettext@GLIBC_2.2.5 (2)
15: FUNC GLOBAL DEFAULT __ctype_get_mb_cur_max@GLIBC_2.2.5 (2)
16: FUNC GLOBAL DEFAULT strlen@GLIBC_2.2.5 (2)
17: FUNC GLOBAL DEFAULT __stack_chk_fail@GLIBC_2.4 (3)
18: FUNC GLOBAL DEFAULT getopt_long@GLIBC_2.2.5 (2)
19: FUNC GLOBAL DEFAULT mbrtowc@GLIBC_2.2.5 (2)
20: FUNC GLOBAL DEFAULT __overflow@GLIBC_2.2.5 (2)
21: FUNC GLOBAL DEFAULT strrchr@GLIBC_2.2.5 (2)
22: FUNC GLOBAL DEFAULT lseek@GLIBC_2.2.5 (2)
23: FUNC GLOBAL DEFAULT memset@GLIBC_2.2.5 (2)
24: FUNC GLOBAL DEFAULT __libc_start_main@GLIBC_2.2.5 (2)
25: FUNC GLOBAL DEFAULT memcmp@GLIBC_2.2.5 (2)
26: FUNC GLOBAL DEFAULT fputs_unlocked@GLIBC_2.2.5 (2)
27: FUNC GLOBAL DEFAULT calloc@GLIBC_2.2.5 (2)
28: FUNC GLOBAL DEFAULT strcmp@GLIBC_2.2.5 (2)
As you can see in the last line, users executable calls a strcmp function from the standard Linux GNU C Library library. This function compares two strings given as its arguments and returns 0 if the strings are equal, positive value if the first string is greater than the second one, and negative value otherwise.You can take advantage of the fact that the program uses a function from an external library to modify its behaviour without touching its code. All you have to do is to substitute strcmp with your own function. You can do it by writing your own dynamic library with custom strcmp and load it before the code of the users executable is initialized.
First, let's create a very simple library mylib.c with this code:
int strcmp(const char* s1, const char* s2) {
for (; *s1 == *s2; s1++, s2++) {
if (*s1 == '\0') {
return 0;
}
}
return ((*(unsigned char*)s1 > *(unsigned char*)s2) ? -1 : 1);
}
and compile it with the following command:
gcc mylib.c -shared -Wl,-soname,mylib -o mylib.so -fPICAs you probably noticed, it behaves opposite to the original strcmp function: it returns negative value when the second string is greater than the first one, and positive value otherwise.
Now all you have to do is to inject the custom library code into the running program. Fortunately, Linux allows you to load your own dynamic libraries before starting any executable with LD_PRELOAD environment variable. We can take advantage of this feature - just compare the results of the two following commands:
[adam@ubuntu:~]$ users adam eve [adam@ubuntu:~]$ LD_PRELOAD="./mylib.so" users eve adamBecause we reversed the behaviour of the strcmp function, and users executable relies on it, we managed to change the result of the command (user logins are reversed in the second example) without even touching it.
Google used the same trick to create TCMalloc, which is a faster modification of the standard Linux malloc.
Monday, January 13, 2014
OSV - operating system for the cloud
Cloud development requires design oriented towards environment with reduced performance. With many virtual servers occupying one physical machine a lot of processing power is consumed by context switching, reducing overall performance of all virtual instances.
OSV is a new operating system designed specifically for instances running in the cloud, written in C++ (which, as a side note, proves that Linus Torvalds was wrong when he claimed that C++ is not suitable for writing a system kernel). OSV reduces a lot of overhead found in the traditional operating systems, like kernel memory protection. If you ever worked with operating system which does not use such protection (like AROS or MorphOS), especially on hardware with x86 architecture, you must have observed a huge performance gain on those systems. Of course the biggest drawback of this approach is that a badly written application can crash the whole machine. However, since OSV does not run directly on hardware, but on top of a hypervisor (such as Xen or KVM) such crash affects only a virtual cloud instance, not the whole server. Moreover, OSV runs a standard Java Virtual Machine, which provides automatic memory management and necessary level of protection by itself, so no extra effort from the operating system is needed to ensure software stability.
Will OSV become sucessful? It's hard to say at the moment, but it surely shows a new trend, where not only hardware and applications, but also operating systems evolve to fit the new reality which cloud computing creates. If you are interested in trying out OSV yourself, here are some instructions how to run an Amazon EC2 instance with OSV on-board.
OSV is a new operating system designed specifically for instances running in the cloud, written in C++ (which, as a side note, proves that Linus Torvalds was wrong when he claimed that C++ is not suitable for writing a system kernel). OSV reduces a lot of overhead found in the traditional operating systems, like kernel memory protection. If you ever worked with operating system which does not use such protection (like AROS or MorphOS), especially on hardware with x86 architecture, you must have observed a huge performance gain on those systems. Of course the biggest drawback of this approach is that a badly written application can crash the whole machine. However, since OSV does not run directly on hardware, but on top of a hypervisor (such as Xen or KVM) such crash affects only a virtual cloud instance, not the whole server. Moreover, OSV runs a standard Java Virtual Machine, which provides automatic memory management and necessary level of protection by itself, so no extra effort from the operating system is needed to ensure software stability.
Will OSV become sucessful? It's hard to say at the moment, but it surely shows a new trend, where not only hardware and applications, but also operating systems evolve to fit the new reality which cloud computing creates. If you are interested in trying out OSV yourself, here are some instructions how to run an Amazon EC2 instance with OSV on-board.
Saturday, January 11, 2014
Waiting for the seamless cloud
You may not have heard about memristor, the long sought fundamental circuit element (next to resistor, capacitor and inductor), but this invention can be the greatest revolution in computer industry since introducing the transistor. Memristors have simpler construction than transistors and don't require external power source to retain information. Last year Crossbar Inc. unveiled their RRAM non-volatile memory technology with shockingly impressive characteristics: 1 terabyte of data on a single chip with 20 times faster access than offered by traditional NANDs.
But this is just the beginning. When technology evolves, it may be able to replace not only flash drives, but also DRAMs, which will have a huge impact on the whole computer industry. Imagine a device with only one memory space, used both as data storage and for running applications. Moreover, applications are loaded into memory only once, and they stay there even when you turn the power off. You can take off the battery from the smartphone and replace it with a new one, and after turning the power on you instantly get your device just as you left it.
Sounds familiar? If you ever worked with Smalltalk you already know the whole idea. If you didn't, I strongly encourage you to try out Squeak or Pharo. They are both open source Smalltalk implementations, and they provide complete, object-oriented working environment. What is unique about Smalltalk is that you can start applications, create new workspaces, build classes and objects, and when you quit, the whole environment is saved in an image, and restored on the next session. At first sight it looks like simple hibernation, but it isn't. In Smalltalk you can build applications without writing the source code in a traditional way. You just create an object, dynamically add properties and methods to it, and it becomes a part of the current environment. When you want to distribute the application you just distribute the image, which has all the application code, libraries, and necessary tools.
RRAM is a technology which will eventually allow to implement the old Smalltalk idea on the hardware level and finally separate virtual machines from underlying hardware. Currently, every time a virtual machine crashes, a new instance needs to be started from scratch and configured. Although this process can be automated with tools like Puppet, it still takes time and makes applications run from scratch. With RRAM-based cloud the problem will not exist any more: you will be able to save the state of a virtual machine at any moment and than spawn it or move it to another physical location (server, rack unit, or even datacenter) within seconds. More important, the state of all the applications will be preserved, which means that, for example, you will not loose user sessions even if you move a virtual machine to another location.
In my opinion it will be a next big step in cloud computing evolution. Now the cloud instances are mostly stateless, and require external storage or cache to keep user data. With the new memory chips they will be able to preserve their state even while moving across different hardware, and this process will become absolutely seamless for the end user - just the same way the GSM networks work today, keeping your call running even when you switch between base transceiver stations while talking.
But this is just the beginning. When technology evolves, it may be able to replace not only flash drives, but also DRAMs, which will have a huge impact on the whole computer industry. Imagine a device with only one memory space, used both as data storage and for running applications. Moreover, applications are loaded into memory only once, and they stay there even when you turn the power off. You can take off the battery from the smartphone and replace it with a new one, and after turning the power on you instantly get your device just as you left it.
Sounds familiar? If you ever worked with Smalltalk you already know the whole idea. If you didn't, I strongly encourage you to try out Squeak or Pharo. They are both open source Smalltalk implementations, and they provide complete, object-oriented working environment. What is unique about Smalltalk is that you can start applications, create new workspaces, build classes and objects, and when you quit, the whole environment is saved in an image, and restored on the next session. At first sight it looks like simple hibernation, but it isn't. In Smalltalk you can build applications without writing the source code in a traditional way. You just create an object, dynamically add properties and methods to it, and it becomes a part of the current environment. When you want to distribute the application you just distribute the image, which has all the application code, libraries, and necessary tools.
RRAM is a technology which will eventually allow to implement the old Smalltalk idea on the hardware level and finally separate virtual machines from underlying hardware. Currently, every time a virtual machine crashes, a new instance needs to be started from scratch and configured. Although this process can be automated with tools like Puppet, it still takes time and makes applications run from scratch. With RRAM-based cloud the problem will not exist any more: you will be able to save the state of a virtual machine at any moment and than spawn it or move it to another physical location (server, rack unit, or even datacenter) within seconds. More important, the state of all the applications will be preserved, which means that, for example, you will not loose user sessions even if you move a virtual machine to another location.
In my opinion it will be a next big step in cloud computing evolution. Now the cloud instances are mostly stateless, and require external storage or cache to keep user data. With the new memory chips they will be able to preserve their state even while moving across different hardware, and this process will become absolutely seamless for the end user - just the same way the GSM networks work today, keeping your call running even when you switch between base transceiver stations while talking.
Moving to the cloud
The cloud computing has developed rapidly during last few years. As shown by Gartner study, the cloud market has grown by 18% in 2013 and is now worth 131 billion (or thousand million) US dollars. By the year 2015 it is expected to hit the value of 180 billion. Despite some well known security and privacy concerns regarding public cloud storage, and even despite the PRISM global scandal, the future in which most (if not all) of our data is stored in the cloud seems inevitable. This requires a substantial shift in approach to software architecture and creates new challenge for software developers.
First, you need to abandon huge, complicated, monolytic applications in favour of platforms built from many small, interconnected services. Such services require much less resources, and can be easily replicated througout the cloud, increasing the overall stability and safety of the applications. One of the most famous examples of a successful SOA revolution is Amazon, which radically changed its software platform.
Second, you need to change the underlying technologies. For example, Java with its extremely resource hungry virtual machine, bloated frameworks and heavy threads seems a rather bad choice. On the other hand, Node.js with its small memory footprint and single-threaded, event-driven, non-blocking I/O model fits the cloud perfectly.
If you have ever had doubts about Javascript being the right choice for an enterprise application, than you should read about Paypal moving their backend from Java to Javascript. Except from huge cost savings (Paypal has been extensively using very expensive Java soultions like Terracotta BigMemory to scale its backend vertically) and increased productivity (engineers claim to be able to develop software twice as fast as in Java), Paypal also benefits from new skills of its software developers, who can now work both on frontend and backend using the same programming language.
Third, you may need to redesign the application flow and algorithms used. You may often get better results processing huge amount of data in small chunks on many small cloud instances, than all at once on few huge mainframes. It means not only using MapReduce to speed up your tasks, but also avoiding of using complex sequential algorithms. For example, in typical situations mergesort may perform worse than heapsort, but is much simpler to parallelize and with enough cloud instances will sort your data much faster.
But there is more to it than that. AMD has just announced a new line of 64-bit ARM server CPUs, which is widely regarded as the end of its race against Intel in high performance computing. ARM processors are less complicated and more power efficient than their Intel counterparts, but are also slower - which means that they will be more suited for clouds with many small instances.
Finally, there is a whole new class of problems in cloud computing, which are either not present, or long solved in traditional applications, like data consistence or dealing with transactions. Some of them cannot be solved by software, and they require change in your business model: for example you may have to trade real time consistency for the amount of traffic your application can handle. Also, most cloud installations suffer from poor I/O performance, because there are usually many virtual instances simultaneously trying to access one physical device like hard drive or network interface.
First, you need to abandon huge, complicated, monolytic applications in favour of platforms built from many small, interconnected services. Such services require much less resources, and can be easily replicated througout the cloud, increasing the overall stability and safety of the applications. One of the most famous examples of a successful SOA revolution is Amazon, which radically changed its software platform.
Second, you need to change the underlying technologies. For example, Java with its extremely resource hungry virtual machine, bloated frameworks and heavy threads seems a rather bad choice. On the other hand, Node.js with its small memory footprint and single-threaded, event-driven, non-blocking I/O model fits the cloud perfectly.
If you have ever had doubts about Javascript being the right choice for an enterprise application, than you should read about Paypal moving their backend from Java to Javascript. Except from huge cost savings (Paypal has been extensively using very expensive Java soultions like Terracotta BigMemory to scale its backend vertically) and increased productivity (engineers claim to be able to develop software twice as fast as in Java), Paypal also benefits from new skills of its software developers, who can now work both on frontend and backend using the same programming language.
Third, you may need to redesign the application flow and algorithms used. You may often get better results processing huge amount of data in small chunks on many small cloud instances, than all at once on few huge mainframes. It means not only using MapReduce to speed up your tasks, but also avoiding of using complex sequential algorithms. For example, in typical situations mergesort may perform worse than heapsort, but is much simpler to parallelize and with enough cloud instances will sort your data much faster.
But there is more to it than that. AMD has just announced a new line of 64-bit ARM server CPUs, which is widely regarded as the end of its race against Intel in high performance computing. ARM processors are less complicated and more power efficient than their Intel counterparts, but are also slower - which means that they will be more suited for clouds with many small instances.
Finally, there is a whole new class of problems in cloud computing, which are either not present, or long solved in traditional applications, like data consistence or dealing with transactions. Some of them cannot be solved by software, and they require change in your business model: for example you may have to trade real time consistency for the amount of traffic your application can handle. Also, most cloud installations suffer from poor I/O performance, because there are usually many virtual instances simultaneously trying to access one physical device like hard drive or network interface.
Subscribe to:
Posts (Atom)