Tuesday, February 27, 2007

[off topic] message logging severities

I can recall only five levels of severities:

MAJOR: Alarm. Critical unrecoverable error. Results in certain termination of application.
MINOR: Recoverable error. Application can go on, but something is fishy.
NOTICE: Not an error, but shouldn't have happened.
INFO: Run-time information statistics, "anomalies" a.k.a. unsolicited messages. Must produce passable amount of information since might be used for monitoring of real system.
TRACE: Used to trace what's happening in the system: functions called and their arguments. Produces insane amount of output.
DEBUG: Debugging info. Developer's corner.

Production systems run on MINOR level, so that all errors are displayed. MAJOR level normally has abort() built in so that OS would dump core of application for further investigations.

Systems in testing run with INFO level. Often the output is saved and required to match in repeated tests. E.g. if we have fed application with 1000 bytes of info, we would expect INFO message to reflect that 1000 bytes where handled. Not 999, not 1001, not 500 + 500.

Edit1: Added "TRACE" level.

Thursday, February 01, 2007

Off-Topic :: Wait-Free/Lock-less synchronization crash course

Well, results are not that good as I have hoped. (In depth info at Wikipedia. Read the first reference on the page written by Maurice Herlihy in 1993.)

  1. Rule of thumb: lock-less can only be data structures which synchronize using single datum.
  2. Compare-And-Swap( ptr, old, new ) can be used for implementation of atomic counters. The operation is supported by all high performance platforms (e.g. PowerPC & IA-32).
  3. One cannot make lock-less FIFO for N:M (N readers/M writers) nor for 1:M (1 reader/M writers) configurations. Seems that 1:1 (1 read and 1 writer) only possible configuration and in fact it doesn't require any special support at CPU level. (Reference to rule of thumb: FIFO requires two data items for implementation - head/tail (or next/prev).)
  4. Stack (LIFO) can be implemented wait-free/lock-less using Compare-And-Swap() op, since it needs only single pointer for implementation - head - pointing to first element to remove/last element inserted.
Conclusion:
  1. Unixes were 100% right putting pipes at foundation of I/O: pipe can be implemented as couple of FIFOs and as long as pipe isn't shared between more than 2 applications, it can be completely lock free.
  2. Stack (along with Compare-And-Swap op) allows to implement memory management (for static block size) very efficiently. (Edit1. In preemptive SMP OS, that might lead to situation when Compare-And-Swap would succeed despite fact that state of queue already changed. Proper implementation for multiple CPUs would use several (at minimum 2) stacks. Allocations are made from one stack, freeing is done on next stack. Allocation function rotates stacks when detects that current stack is empty. Allocation is failed when all stacks were queried at least once and all are empty. Alternatively, one can introduce additional counter: generation counter. That way Compare-And-Swap needs to be able to write double word. When element is allocated, generation counter is incremented. When element is freed, we put on stack pair - pointer and generation counter - which would be with high probability unique.)
  3. Message passing systems suck big time because (i) 1:1 FIFOs are inapplicable and (ii) it is impossible to optimize memory allocation with lock-less stack since it is impossible to tell where the message would end up. (The later can only be implemented in worst case scenario of shared memory.)