cheap malloc-ed stacks

I've accidentally realized that the disjointed stacks (ones composed of the separately allocated chunks) can be pretty inexpensive if they get allocated in fixed pages, and each stack frame is guaranteed to be less than a page (which is fairly common in, say, the OS kernel). And the stack pages can be made larger than the physical pages.

All that the function needs to do at the start of the call is check that there is enough room to the end of the page. Which is easy enough by checking that (SP & PAGE_SIZE) < (PAGE_SIZE-FRAME_SIZE). Well, taking a page from the RISC book, we'd also want to reserve some room at the end of the page for the leaf functions that could then skip the whole check, but it doesn't change the general approach.

If a new page needs to be allocated, it can be taken from a pool of free stack pages (a linked list), and would be linked to the previous page, then the frame created in it (copying the old stack pointer onto the new stack, as in the "classic" Intel x86 sequence of "push BP" that saves the pointer to the previous stack frame). The next page can also be found already linked to the current page from the last time, and then the allocation can be skipped. The function return then doesn't need to do anything special, just "pop SP" and return. And then if the thread blocks, the scheduler can return the unused pages beyond the last active frame back to the pool.

There obviously is some overhead but not a real huge amount of it.

TLB coherence

The discussion described in the last post got me thinking, why don't we have a hardware consistency for the page address translation cache (TLB), done through the same bus transactions as the usual cache snooping? In a multi-threaded environment, invalidating the TLB across all the threads is a pain that requires the cross-CPU interrupts.

In the simplest case the CPU that drives a TLB invalidation could just do a bus transaction that specifies a virtual address, and every CPU would invalidate its TLB entry that matches this address. If the user processes use the address space randomization, there would be few conflicts between processes, and the kernel address space is common for everyone. In a more complicated way, the virtual address can be accompanied by the process or memory protection id, so that only the pages of the CPUs running that process would be invalidated. And finally, each page translation entry has a unique identifier: the physical memory address where the CPU had read it from. If the TLB keeps this address as a tag (keeping enough bits to identify the page of the page directory is enough, since the rest of bits are determined by the virtual address), it can be used as a tag in the TLB invalidation transaction, and only the exact TLB entrues matching this tag would be invalidated.

Which made me wonder if anyone else had thought of this before. And after a bit of searching, it has turned out that they did: https://arxiv.org/pdf/1701.07517.pdf. These guys have approached the problem from the hypervisor standpoint, but the implementation is exactly the same, using the physical memory address of the entry as a tag. There is no date on the article, but judging by the citation list, it could not have been written earlier than 2016.

statistical and password-based memory protection

I've recently had an interesting online conversation with Terry Lambert (whom I know from the FreeBSD times) about the memory protection that resulted in I think a new and interesting idea, that I want to write down here.

Terry was talking about the statistical memory protection. I'm not sure if he invented it, or at least the term, since I can't find it anywhere else. Terry gives the related links but none of them are exactly about that:

• https://en.wikipedia.org/wiki/Capability-based_addressing
• CSDL | IEEE Computer Society - Fast Protection-Domain Crossing in the CHERI Capability-System Architecture
• Address space layout randomization - Wikipedia
• Intro to System Software, Chapter 18 [Iowa State CS]
• ERIM: Secure, Efficient In-process Isolation with Protection ... [PDF]
• Sharing and Protection in a Single Address Space Operating ... [PDF]
• Mondrian Memory Protection - UT CS [PDF]
• Scheduling and Load Balancing in Parallel and Distributed Systems

The statistical memory protection works by having a large common address space where the protection is achieved by allocating memory at random addresses, so the address itself serves as a password. Plus the same physical page can be mapped at different addresses with different permissions, so knowing one address would give the write access while another one the read-only access.

As far as I see it, the major benefit of this system would be in the ability to pass the complex data structures linked by pointers between processes. With the address map being common, the pointers would work in any process. This gives cheap and convenient "mailboxes" for exchanging messages between processes.

This would have multiple potential problems too.

One is the “password leakage” that is also mentioned in one of the papers. Once a password gets out, it can be saved and passed around. With the separate addresses for RO and RW access to the same page this could get pretty bad:  if one of these pointers in an RO page accidentally refers to the RW address, the permission leaks. And actually the whole passing of pointer-connected structures breaks down because the writer and reader would have to use different pointers (with RO and RW addresses). 

Another issue, the memory segments would have to be allocated at the globally unique random addresses, which would have to be a synchronized operation. Considering that the segments have to be spaced far enough form each other, that would consume a sizable number of bits and degrade security of the passwords. 

This would also be susceptible to the brute-force attacks: maybe the attack won’t enumerate the whole address space but it can start with a random point and just see what can be found there. It won’t always be lucky, but sometimes it would. Another way of the attack would be to stick incorrect pointers into the shared pages, hoping that the other process reading the pointer from that page would cause some damage.

The brute-force attacks can be frustrated by keeping a fault counter, and killing the process that has too many faults, but it's harder than it seems at first. The fault counters would have to have a scope greater than a process. Because if you kill a process, nothing stops the user from spawning another one. Also nothing would stop the user from spawning a lot of processes, each doing fewer probes than the fault limit and exiting. But on the other hand, with a greater scope, a malicious application would be able to screw the user completely, so drawing this scope boundary won’t be easy. A possible solution for that problem is to introduce a delay in process's scheduling after a fault, and these delays can even be made to increase if user's global rate is high. This would dramatically slow down the attacks without affecting the correctly running code.

There is one more reason for why the fault counting would have issues: if we allow to transfer the pointers through the global memory, there is no way to know whose fault is the faulty pointer, did the current process get it from someone else?

I've come up with an idea to improve on the statistical memory protection, let's call it password-based memory protection: the same can be achieved in a better and cheaper way by associating a long (say, 128 bit) “password” with a page, effectively making the addresses in the “password-protected” pages 192-bit long (64 bit for the address and 128-bit password). There can be separate passwords for reading-only and reading-writing a page. Possibly execute-only too. But the passwords can be kept separate in some context, so the “short” 64-bit part of the address would be the same for the reader and writer. The context can be inherited from the page: when we load a pointer from a page, we set in the CPU register the password part of it equal to the password of the page. This would also allow to catch the malicious addresses in the shared pages by mismatch of the password. And the whole address space can be split into the private and shared parts, with only the shared part using the passwords. This would allow the private segments to allocate pages without getting a global lock on the address space. And the whole 128-bit space can be used for the password.

It would still be randomly susceptible to the brute-force attacks, as well as to the password leakage.

Some progress can be made on the fault-blaming through. If only the pointers without passwords cold be transferred through the password-protected memory then when we read such a pointer, we can implicitly add the password of the protected page to it and immediately verify that the pointer is valid, that this password also matches the page referred by the pointer. If it doesn't, it means that someone tried to slip in an invalid pointer. If our process has read-only access to the page, we can even say for sure that if was another process's fault and not penalize this one (unless of course it mapped the same page twice, and the other mapping is read-write).

Let's consider in more detail how the pointers would work. For the pointers-with-passwords let's use the "far" keyword from the days of MS-DOS. The common (AKA "near") pointers without password would be just pointers without a special keyword.
 

int *pn; // a common pointer
int far *pf; // a far pointer that includes the password

They generally can't be cast to each other, a far pointer has to be explicitly converted from a near pointer and a password:

pf = make_far(pn, password);

Typically we would use the common pointers in the structures that get passed through the password-protected memory, to store only the address but not password:

 
struct data {
  int *p1;
  int *p2;
};

This would also allow to use the same structure in the normal and password-protected memory.

But when  a common pointer gets accessed through a far pointer, it gets treated in a special way: essentially, it becomes implicitly converted to a far pointer.

 
data far *dpf;
data *dpn; 

pn = dpf->p1; // incorrect, won't compile
dpn->p1 = dpf->p1; // incorrect, won't compile
pf = dpf->p1; // correct, implicitly copies the password 
  // from dpf to pf and verifies that pf is valid, throws an
  // exception if invalid
dpf->p1 = pn; // incorrect, won't compile
dpf->p1 = dpn->p1; // incorrect, won't compile
dpf->p1 = pf; // correct, verifies that dpf and pf have
  // the same password (throws an exception if the
  // passwords differ), and drops the password when
  // writing into p1
dpf->p2 = dpf->p1; // correct

It would actually be more correct to say that the reference to a pointer accessed through a far pointer turns implicitly into a reference to a far pointer, and handles the conversion between the kinds of pointers.

This of course wouldn't stop someone from copying pointers as data to or from the password-protected memory via memcpy (though it would of course have to be a special version of memcpy that accepts the far pointers as arguments), but that would be their own problem of forfeiting the hardware help in the protection.

On the assembly level, this can be done with the addition of the password registers in the CPU along with the instructions for accessing the password-protected pages. Something like this:

 
  ; load the address part of the far pointer
  load (r1), r2
  ; load the password part of the far pointer into a password register
  loadpwd (r1+16), pr1
  ; read a value at a password-protected  far pointer
  loadpp r2, pr1, r3
  ; assuming that the read value was a pointer, verify that it was correct,
  ; it must be pointing to a page that uses the same password from pr1
  verifyp r3, pr1, failure_label
  ; or maybe read and verify in one instruction
  loadpv r2, pr1, r3, failure_label
  ; store a far pointer
  store r3, (r5)
  storepwd pr1, (r5+16)

The next development to prevent the brute-force attacks and password leaks is to have the OS to track on the side, access to which segments is granted to the process. 

Then the problem of the leaked passwords can be solved by changing them periodically. Instead of keeping the pair (password, address) in the far pointer, place the all the passwords for all the granted segments into a canonical location in the process. Then represent the far pointer as  the pair (address of the password, address of the data). Whenever a password needs to be changed, change it in the canonical location (of which the OS would keep track). And when an access exception happens due to a stale password in the CPU register, the kernel can check the access rights of the process against the canonical list. If the rights are present, it can update the password in the register and return to retry the access. 

But a consequence of keeping this special section is that the passwords themselves can be stored in a protected section of memory, otherwise inaccessible in the user mode. The password registers in the CPU would have two parts: the address of the password in the special section that can be loaded and stored by the process and the shadow value of the password itself, invisible to the process and used to check the access. Then the users won’t be able to brute-force the passwords at all because they won't be ever able to set the arbitrary passwords, all the password management would happen in the OS. 

Then if the passwords are not user-visible, they don’t have to be long any more, 64 bits, or maybe even 32 bits would suffice as long as they are all unique. Another consequence would be that changing the password would not be needed most of the time, its only use would be to revoke someone’s access.

But wait, there is more. If we don't have the special hardware available, instead of checking on every access we can check when mapping the page into the address space of the process. It’s just that the shared pages would be mapped at the same virtual address in every process. So we’ve made a full circle back to the existing solution here. It feels like not disturbing the page table would be more efficient, but actually not: the segment would have to be allocated first anyway before making it available to any process, and if the page map is shared between all the processes, that means potentially disturbing all the processes, not only the ones that will use that segment. 

The only other part of the implementation would be the verification that the pointers received in the shared pages are safe, that they point to the pages of he same source. This can be done in user space, allocating a “page id map”, where each page address is direct-mapped to the “source id” of this page (say, 4 bytes each). Look up the ids of the page that contained the pointer and of the pointed page, and verify that the ids are the same. The map itself can be sparse, the unused parts mapped to an all-0 page, so it would be cheap. Some kernel help might be useful for handling the sparseness and making sure that the page id map is consistent with the page table. The compiler support with the "far pointers" would also still be useful for the automated verification, even with the user space solution.

On performace of reading the unaligned data

I've made a template that was supposed to optimize the reading of the unaligned data:

template <typename T>
T getUnaligned(const T *ptr)
{      
    if ((intptr_t)ptr & (sizeof(T)-1)) {
        T value;
        memcpy(&value, ptr, sizeof(T));
        return value;
    } else {
        return *ptr;
    }
}

And I've been wondering if it really makes a difference. So I've made a test.The test compares 5 cases:

Just read the aligned memory directly;
Read the aligned memory through memcpy;
Read the aligned memory through memcpy;
Read the aligned memory through the macro;
Read the unaligned memory through the macro.

All the cases follow this general pattern:

UTESTCASE readAlignedDirect(Utest *utest)
{
    int64_t n = findRunCount();
    int64_t x = 0;

    double tstart = now();
    for (int64_t i = 0; i < n; i++) {
        x += apdata[i % ARRAYSZ];
    }
    double tend = now();
    printf("        [%lld] %lld iterations, %f seconds, %f iter per second\n", (long long) x, (long long)n, (tend-tstart), (double)n / (tend-tstart));
}


The results on an AMD64 machine with -O3 came out like this:

   case 1/6: warmup
        [0] 4294967296 iterations, 4.601818 seconds, 933319757.968194 iter per second
  case 2/6: readAlignedDirect
        [0] 4294967296 iterations, 4.579874 seconds, 937791527.916276 iter per second
  case 3/6: readAlignedMemcpy
        [0] 4294967296 iterations, 4.537628 seconds, 946522579.007429 iter per second
  case 4/6: readUnalignedMemcpy
        [0] 4294967296 iterations, 6.215574 seconds, 691000961.046305 iter per second
  case 5/6: readAlignedTemplate
        [0] 4294967296 iterations, 4.579680 seconds, 937831317.452678 iter per second
  case 6/6: readUnalignedTemplate
        [0] 4294967296 iterations, 5.052706 seconds, 850033049.741168 iter per second

Even more interestingly, the code generated for readAlignedDirect(), readAlignedTemplate() and readUnalignedTemplate() is exactly the same:

.L46:
    movq    %rax, %rdx
    addq    $1, %rax
    andl    $15, %edx
    addq    (%rcx,%rdx,8), %rbx
    cmpq    %rbp, %rax
    jne .L46

The code generated for readAlignedMemcpy() and readUnalignedMemcpy() is slightly different but very similar:

.L34:
    movq    %rax, %rdx
    addq    $1, %rax
    andl    $15, %edx
    salq    $3, %rdx
    addq    (%rcx), %rdx
    movq    (%rdx), %rdx
    addq    %rdx, %rbx
    cmpq    %rax, %rbp
    movq    %rdx, (%rsi)
    jg  .L34

Basically, the compiler is smart enough to know that the machine doesnt' care about alignment, and generates memcpy() as a plain memory read, and then for condition in the template it's also smart enough to know that both branches end up with the same code and eliminate the condition check.

Smart, huh? So now I'm not sure if keeping this template as it is makes sense, or should I just change it to a plain memcpy().

BTW,  I must say it took me a few attempts to make up the code that would not get optimized out by the compiler. I've found out that memcpy() is not suitable for reading the volatile data nowadays. It defines its second argument as (const void *), and so the volatility has to be cast away for passing the pointer to it, and then the compiler just happily takes the whole memory read out of the loop. And it was even smart enough to sometimes replace the whole loop with a multiplication instead of collecting a sum. That's where the modulo operator came handy to confuse this extreme smartness.

A separate interesting note is that each iteration of the loop executes in an about one-billionth of a second. Since this is a 3GHz CPU, this means that every iteration takes only about 3 CPU cycles.  That's 6 or 10 instructions executed in 3 CPU cycles. Such are the modern miracles.

odds and ends

While working on threads support, I've added a few small features here and there. Some of them have been already described, some will be described now. I've also done a few more small clean-ups.

First, the historic methods setName() are now gone everywhere. This means Unit and Label classes, and in C++ also the Gadget. The names can now only be specified during the object construction.

FnReturn has the new method:

$res = fret->isFaceted();

bool isFaceted() const;

It returns true (or 1 in Perl) if this FnReturn object is a part of a Facet.

Unit has gained a couple of methods:

$res = $unit->isFrameEmpty();

bool isFrameEmpty() const;

Check whether the current frame is empty. This is different from the method empty() that checks whether the the whole unit is empty. This method is useful if you run multiple units in the same thread, with some potentially complicated cross-unit scheduling. It's what nextXtray() does with a multi-unit Triead, repeatedly calling drainFrame() for all the units that are found not empty. In this situation the simple empty() can not be used because the current inner frame might not be the outer frame, and draining the inner frame can be repeated forever while the outer frame will still contain rowops. The more precise check of isFrameEmpty() prevents the possibility of such endless loops.

$res = $unit->isInOuterFrame();

bool isInOuterFrame() const;

Check whether the unit's current inner frame is the same as its outer frame, which means that the unit is not in the middle of a call.


In Perl the method Rowop::printP() has gained an optional argument for the printed label name:

$text = $rop->printP();
$text = $rop->printP($lbname);

The reason for that is to make the printing of rowops in the chained labels more convenient. A chained label's execution handler receives the original unchanged rowop that refers to the first label in the chain. So when it gets printed, it will print the name of the first label in the chain, which might be very surprising. The explicit argument allows to override it to the name of the chained label (or to any other value).


 In C++ the Autoref has gained the method swap():

void swap(Autoref &other);

It swaps the values of two references without changing the reference counts in the referred values. This is a minor optimization for such a special situation. One or both references may contain NULL.


In C++ the Table has gained the support for sticky errors. The table internals contain a few places where the errors can't just throw an Exception because it will mess up the logic big time, most specifically the comparator functions for the indexes. The Triceps built-in indexes can't encounter any errors in the comparators but the user-defined ones, such as the Perl Sorted Index, can. Previously there was no way to report these errors other than print the error message and then either continue pretending that nothing happened or abort the program.

The sticky errors provide a way out of this sticky situation. When an index comparator encounters an error, it reports it as a sticky error in the table and then returns false. The table logic then unrolls like nothing happened for a while, but before returning from the user-initiated method it will find this sticky error and throw an Exception at a safe time. Obviously, the incorrect comparison means that the table enters some messed-up state, so all the further operations on the table will keep finding this sticky error and throw an Exception right away, before doing anything. The sticky error can't be unstuck. The only way out of it is to just discard the table and move on.

void setStickyError(Erref err);

Set the sticky error from a location where an exception can not be thrown, such as from the comparators in the indexes. Only the first error sticks, all the others are ignored since (a) the table will be dead and throwing this error in exceptions from this point on anyway and (b) the comparator is likely to report the same error repeatedly and there is no point in seeing multiple copies.

Errors *getStickyError() const;

Get the table's sticky error. Normally there is no point in doing this manually, but just in case.

void checkStickyError() const;

If the sticky error has been set, throw an Exception with it.

another approach to the weak references

I've recently developed another idea about the weak references. So, let's look at the basic problem:

There is an object A that has a reference to object B.

A->B

The object B needs to be able to reach back to the object A. But it can't have a reference because that would create a reference cycle. So instead it has to have some kind of weak reference. In the single-threaded situation it can be as simple as a plain pointer that gets reset to NULL when the object A is destroyed, like for example the Triceps Label has a pointer to its Unit.

There could be lots of objects B per object A. So when the object A gets destroyed, it needs to take care to clear the weak references in all the objects B. Which is kind of annoying. And it easily gets worse if the connection is not direct but multi-level, say A->B->C and then C having a back reference back to A.

However there is a way around it. Create a single object W that will keep a weak reference back to A. Then all the objects B can just keep a reference to W. And of course A would also keep a reference to W. When A is destroyed, it will reset the single weak reference in W.

A------------>W
 \-->B1-->/
 \-->B2-->/
 \-->B3-->/

Then the logic for creating and resetting the object W can be placed into a base class and then reused all over the place. The object W could even hold the pieces of information that can be still useful after the object A goes away, such as the name of the object A for the error messages.

Reference to a RowHandle

The row handles have the requirements very similar to the rows. They get created by the million, so the efficiency is important. They contain data that has to be properly destroyed. For example, when an additive Perl aggregator stores its last state, it 's stored in a row handle.

So they are handled similarly to the rows. they don't have a virtual destructor but rely on the Table that owns them to destroy them right. The special reference type for them is Rhref, defined in mem/Rhref.h (the RowHandle itself is defined in table/Table.h).

It follows in the exact same mold as Rowref, only uses the Table instead of a RowType:

Rhref(Table *t, RowHandle *r = NULL);
void assign(Table *t, RowHandle *r);

The rest of comparisons, assignments etc. work the same.

An important point is that a Rhref contains an Autoref to the table, safely holding the table in place while the Rhref is alive. So does the Rowref with the RowType as well, I just forgot to mention it before.

To find out the table of a Rhref, use:

Table *t = rhr.getTable();

Why is the value returned a simple pointer to the table and not an Autoref or Onceref? Basically, because it's the cheapest way and because the row handle is not likely to go anywhere. Nobody is likely to construct a RowHandle only to get the table from it and have it immediately destroyed. And even if someone does something of the sort

Autoref<table> t = RowHandle(t_orig, rh).getTable();

then the table itself is likely to not go anywhere, there is still likely to be another reference to the table that will still hold it in place. If there isn't then of course all bets are off, and t will end up with a dead reference to corrupted memory. Just exercise a little care, and everything will be fine. The same reasoning was used for the argument of the RowHandle constructor being also a table pointer, not an Autoref or Onceref.

An Rhref may also be conveniently used to construct a RowHandle for a Row:

Rhref(Table *t, Row *row);

In fact, this is the official way to construct a RowHandle. The Rowref has a similar method to construct the rows from raw data but the data is much more complex, so I've left its description until later.

Row reference

The Row objects are reference-counted too but Autoref can't be used with them. The reason is about the destructors.

It isn't used anywhere yet, but the rows in Triceps are designed to be able to contain references to the other rows and in general other objects.  So they can't be destroyed by just freeing the memory. The destructor must know, how to release the references to these nested objects first. And knowing where these references are depends on the type of the row. And rows may be of different types. This calls for a virtual destructor.

But having a virtual destructor requires that every object has a pointer to the table of virtual functions. That adds the overhead of 8 bytes per row, and the rows are likely to be kapt by the million, and that overhead adds up. So I've made the decision to save these 8 bytes and split that knowledge. It might turn out a premature optimization, but since it's something that would be difficult to change later, I've got it in early.

The knowledge of how to destroy a row (and also how to copy the row and to access the elements in it) is kept in the row type object. So the reference to a row needs to know two things: the  row and the row's type. It's still an extra 8 bytes of a pointer, but there are only a few row references active at a time (the tables don't use the common row references to keep the rows, instead they are implemented as a special case and have one single row type for all the rows they store).

The special reference class for the rows is Rowref, defined in type/RowType.h.  It gets constructed as:

Rowref(const RowType *t, Row *r = NULL);
Rowref(const Rowref &ar);

It can be then assigned from rowref or from a row (keeping the row type the same):

Rowref &operator=(const Rowref &ar);
Rowref &operator=(Row *r);

Also both a new row type and a row can be assigned at the same time:

void assign(const RowType *t, Row *r);

There is also the ways to copy a row and assign a copy to this reference:

Rowref &copyRow(const RowType *rtype, const Row *row);
Rowref &copyRow(const Rowref &ar);

The other functionality is similar to Autoref(): isNull(), get(), comparisons, calling the Row methods through ->, and conversion to a Row pointer.

Autoref summary

Autoref can be constructed with or assigned from another Autoref or a pointer:

T *ptr;
Autoref<T> ref1(ptr);
Autoref<T> ref2(ref1);
ref1 = ref2;
ref1 = ptr;

The assignments work for exactly the same type and also for assignment to any parent in the class hierarchy:

Autoref<Label> = new DummyLabel(...);

The automatic conversion to pointers works too:

ptr = ref1;

Or a pointer can get extracted from an Autoref explicitly too:

ptr = ref1.get();

The dereferencing and arrow operations work like on a pointer too:

T val = *ref1;
ref1->method();

The Autorefs can also be compared for equality and inequality:

ref1 == ref2
ref1 != ref2

To compare them to pointers, use get(). Except for one special case: the comparison to NULL happens so often that a special method is provided for it:

ref1.isNull()

And yes, NULL can be assigned to the Autorefs too.

A little about how Autoref works: it can work transparently on both Starget and Mtarget because Autoref doesn't modify the reference counters by itself. Instead the target class is expected to provide the methods 

void incref() const;
int decref() const;

They are defined as const to allow the reference counting of even the const objects, but of course the reference counter must be mutable. decref() returns the resulting counter value. When it goes down to 0, Autoref calls the destructor.

Reference Counting

The code related to the memory management is generally collected under mem/. The reference counting has two parts to it:

• The objects that can be managed by reference counting.
• The references that do the counting.

The managed objects come in two varieties: single-threaded and multi-threaded. The single-threaded objects lead their whole life in a single thread, so their reference counts don't need locking. The multi-threaded objects can be shared by multiple threads, so their reference counts are kept thread-safe by using the atomic integers (if the NSPR library is available) or by using a lock (if NSPR is not used). That whole implementation of atomic data with or without NSPR is encapsulated in the class AtomitInc in mem/Atomic.h.

The way a class selects whether it will be single-threaded or multi-threaded is by inheriting from the appropriate class:

Starget (defined in mem/Starget.h) for single-threaded;
Mtarget (defined in mem/Mtarget.h) for multi-threaded.

If you do the multiple inheritance, the [SM]target has to be inherited only once. Also, you can't change the choice along the inheritance chain. Once chosen, you're stuck with it. The only way around it is by encapsulating that inner class's  object instead of inheriting from it.

The references are created with the template Autoref<>, defined in mem/Autoref.h. For example, if you have an object of class RowType, the reference to it will be Autoref<RowType>. There are are some similar references in the Boost library, but I prefer to avoid the avoidable dependencies (and anyway, I've never used Boost much).

The target objects are created in the constructors with the reference count of 0. The first time the object pointer is assigned to an Autoref, the count goes up to 1. After that it stays above 0 for the whole life of the object. As soon as it goes back to 0 (meaning that the last reference to it has disappeared), the object gets destroyed.No locks are held during the destruction itself. After all the references are gone, nobody should be using it, and destroying it is safe without any extra locks.

An important point is that to do all this, the Autoref must be able to execute the correct destructor when it destroys the object that ran out of references. Starget and Mtarget do not provide the virtual destructors. If you don't use the polymorphism for some class, you don't have to use the virtual destructors. But if you do use it, i.e. create a class B inheriting from A, inheriting from [SM]target, and then assign something like

Autoref<A> ref = new B;

then the class A (and by extension all the classes inheriting from it) must have a virtual destructor to get everything working right.

It's also possible to mess up the destruction with the use of pointers. For example, look at this sequence:

Autoref<RowType> rt = new RowType(...);
RowType *rtp = rt; // copies a reference to a pointer
rt = NULL; // reference cleared, count down to 0, object destroyed
Autoref <RowType> rt2 = rtp; // resurrects the dead pointer, corrupts memory

The lesson here is that even though you can mix the references with pointers to reduce the overhead (the reference assignments change the reference counters, the pointer assignments don't), and I do it in my code, you need to be careful. A pointer may be used only when you know that there is a reference that holds the object in place. Once that reference is gone, the pointer can't be used any more, and especially can't be assigned to another reference. Be careful.

There are more varieties of Autoref<>:

Onceref<>
const_Autoref<>
const_Onceref<>

The Onceref is an attempt at optimization when passing the function arguments and results. It's supposed to work like the standard auto_ptr: you assign a value there once, and then when that value gets assigned to an Autoref or another Onceref, it moves to the new location, leaving the reference count unchanged and the original Onceref as NULL. This way you avoid a spurious extra increase-decrease. However in practice I haven't got around to implementing it yet, so for now it's a placeholder that is defined to be an alias of Autoref.

const_Autoref<> is a reference to a constant object. Essentially, const_Autoref<T> is equivalent to Autoref<const T>, only it handles the automatic type casts much better. The approach is patterned after the const_iterator. The only problem with const_Autoref is that when you try to assign a NULL to it, that blows the compiler's mind. So you have to write an explicit cast of (T*)NULL of (const T*)NULL to help it out.

Finally, const_Onceref is the const version of Onceref.

Memory management strikes back

I've started collecting the docs, and I've found that I wrote up a whole set of rules for how to keep the memory references correct. And I've also found that I've completely ignored them. This means that the rules are way too tricky, and thus don't make a whole lot of sense. Something had to be done about it. And here we go:

First, the problems come not with the data that goes through the models but with the models themselves. The data gets reference-counted without any issues. The reference loops can get formed only between the elements of the models: labels, tables etc. If you don't need them destroyed until the program exits (or more exactly, until the Perl interpreter instance exits), there is no problem. The leaks would happen only if the model elements get created and destroyed as the program runs, such as if you use them to parse and process the short-lived ad-hoc queries.

Second, these leaks are pretty hard to diagnose. There are some packages, like Devel::Cycle, but they won't detect the loops that involve a reference at C++ level. And when the Perl interpreter exits, it clears up all the variables used, even the ones involved in the loops, so if you run it under valgrind, valgrind doesn't show any leaks. If the Perl interpreter allowed to detect all these left-over variables, it would work as a high-level version of valgrind, and it would help.

Third, Perl provides the weak references (using the module Scalar::Util) but the problem is that you need to not forget weakening the references manually. Too much work, too much attention.

Fourth, here are the new, simplified rules.

Have more faith in the label clearing as the driving force. When you create the template objects, don't be afraid to have references to other objects, to units etc., as long as they get cleared by the label clearing logic. But make sure that the label clearing logic gets actually called. When you delete a unit, make sure to call its clearing either directly or through deletion of the unit clearing trigger.

I've been talking about how if a label used by an object receives $self as an argument, it should have a clearing function that would undefine that object hash. And I've never actually done it in any of the join and aggregation examples. Defining it every time is too much work and too easy to forget. The new and better approach: now there is a pre-defined function Triceps::clearArgs(). Just reuse it, there is no need to re-create it from scratch. Better yet, now it gets used automatically if the clearing function for a label is specified as undef (if you really want the clearing to do nothing, use "sub {}" instead).

Some templates don't have their own input labels, instead they just combine and tie together a few internal objects, and use the input labels of some of these internal objects as their inputs. JoinTwo is one of them, it just combines two LookupJoins. Without an input label, there would be no clearing, and the template object's has would never be undefined. To make life easier, now there is a way to create the special clearing-only labels:

$lb = $unit->makeClearingLabel("name", @args);

Since the call is from "should never fail" category, on any errors it will confess. There is no need to check the result. The result can be saved in a variable or can be simply ignored. If you throw away the result, you won't be able to access that label from the Perl code but it won't be lost: it will be still referenced from the unit, until the unit gets cleared.

For a concrete usage example, here is how JoinTwo uses it:

$self->{clearingLabel} = $self->{unit}->makeClearingLabel(
  $self->{name} . ".clear", $self);

Passing $self as an argument makes sure that $self gets cleared.

Note how the clearing label doesn't have a row type. In reality every label does how a row type, just it would be silly to abuse the random row types to create the clearing-only labels. Because of this, the clearing labels are created with a special empty row type that has no fields in it. If you ever want to use this row type for any other purposes, you can get it with the method

$rt = $unit->getEmptyRowType();

Each unit has its own copy of the empty row type, and although they are all matching and equal, they are not the same. However nothing stops you from mixing them up, a row type as such is not connected to a unit, it's just convenient to create an empty row type once in a unit and then reuse it when the unit creates the clearing-only labels.

Labels, part 1

In each CEP engine there are two kinds of logic: One is to get some request, look up some state, maybe update some state, and return the result. The other has to do with the maintenance of the state: make sure that when one part of the state is changed, the change propagates consistently through the rest of it. If we take a common RDBMS for an analog, the first kind would be like the ad-hoc queries, the second kind will be like the triggers. The CEP engines are very much like database engines driven by triggers, so the second kind tends to account for a lot of code.

The first kind of logic is often very nicely accommodated by the procedural logic. The second kind often (but not always) can benefit for a more relational, SQLy definition. Also, when every every SQL statement executes, it gets compiled first into the procedural form, and only then executes as the procedural code.

The Triceps approach is tilted toward procedural execution. That is, the procedural definitions come out of the box, and then the high-level relational logic can be defined with templates and code generators.

These bits of code, especially where the first and second kind connect, need some way to pass the data and operations between them. In Triceps these connection points are called Labels.

The streaming data rows enter the procedural logic through a label. Each row causes one call on the label. From the functional standpoint they are the same as Coral8 Streams, as has been shown earlier in the introduction. Except that in Triceps the labels get not just rows but operations on rows, as in Aleri: a combination of a row and an operation code. The name is "labels" because Triceps has been built around the more procedural ideas, and when looked at from that side, the labels are targets of calls and GOTOs.

If the streaming model is defined as a data flow graph, each arrow in the graph is essentially a GOTO operation, and each node is a label.

A Triceps label is not quite a GOTO label, since the actual procedural control always returns back after executing the label's code. It can be thought of as a label of a function or procedure. But if the caller does nothing but immedially return after getting the control back, it works very much like a GOTO label.

Each label accepts operations on rows of a certain type.

Each label belongs to a certain execution unit, so a label can be used only strictly inside one thread and can not be shared between threads.

Each label may have some code to execute when it receives a row operation. The labels without code can be useful too.

A Triceps model contains the straightforward code and the mode complex stateful elements, such as tables, aggregators, joiners (which may be implemented in C++ or in Perl, or created as user templates). These stateful elements would have some input labels, where the actions may be sent to them (and the actions may also be done as direct method calls), and output labels, where they would produce the indications of the changed state and/or responses to the queries. The output labels are typically the ones without code ("dummy labels"). They do nothing by themselves, but can pass the data to the other labels. This passing of data is achieved by chaining the labels: when a label is called, it will first execute its own code (if it has any), and then call the same operation on whatever labels are chained from it. Which may have more labels chained from them in turn. So, to pass the data, chain the input label of the following element to the output label of the previous element.

The execution unit provides methods to construct labels. A dummy label is constructed as:

$label = $unit->makeDummyLabel($rowType, "name");

It takes as arguments the type of rows that the label will accept and the symbolic name of the label. The name can be any but for the ease of debugging it's better to give the same name as the label variable.

The label with Perl code is constructed as follows:

$label = $unit->makeLabel($rowType, "name", \&clearSub,
  \&execSub, args...);

The row type and name arguments are the same as for the dummy label. The following arguments provide the references to the Perl functions that perform the actions. execSub is the function that executes to handle the incoming rows. It gets the arguments:

execSub($label, $rowop, args...)

Here $label is this label, $rowop is the row operation, and args are the same as extra arguments specified at the label creation.

The row operation actually contains the label reference, so why pass it the second time? The reason lies in the chaining. The current label may be chained, possibly through multiple levels, to some original label, and the rowop will refer to that original label. So the extra argument lets the code find the current label.

The clearSub deals with the destruction. Remember that the Triceps memory management uses the reference counting, which does not like the reference loops. The reference loops cause the objects to be never freed. It's no big deal if the data structures exist until the program exit anyway but becomes a memory leak if they are created and deleted dynamically.

If the labels are arranged in a cyclic graph, they refear to each other and create a reference loop. So the execution unit keeps track of all its labels, and when it gets destoryed, clears them up, breaking up the loops.

The clearing of a label drops all the references to execSub, clearSub and arguments, and clears all the chainings. But before anything else is done, clearSub gets a chance to execute and clear any application-level data. It gets as argument the label reference all the args from the label constructor:

clearSub($label, args...) 

A typical case is  to keep the state of a stateful element in a hash:

package MyElement;

sub new # (class, unit, name...)
{
  my ($class, $unit, $name) = @_; 
  my $self = {};
  ... 
  $self->inLabel = $unit->makeLabel(..., \&clear, \&handle, $self);
  $self->outLabel = $unit->makeDummyLabel(...);
  ...
  bless $self, $class;
  return $self;
}

Then the clearing function can wipe out the whole state of the element by undefining its hash:

sub clear # (label, self)
{
  my ($label, $self) = @_;
  undef %$self;
}

Either of execSub and clearSub can be specified as undef. Though a label with an undefined execSub is essentially a dummy label, only more heavyweight.

Another potential for reference loops is between the  execution unit and the labels. A unit keeps a reference to all its labels. So the labels can not keep a reference to the unit. And they don't. Internally they have a plain pointer.  Note however that in the example shown the labels have a Perl reference to the object where they belong. If that object is to have a Perl reference to the unit, it would create a reference loop, and the object will never be destroyed and never clear the labels. So generally the objects should never keep references to the unit. The unit also provides another way around this situation: it has a way to force the label clearing when a helper object gets destroyed. It will be described later.

P.S. The original published version of this post had a few paragraphs lost, the updated version from 01/06/12 has them re-added.

memory management

The memory is managed in Triceps using the reference counters. Each Triceps object has a reference counter in it. There is an Autoref template that produces reference objects. As the references are copied around between these objects, the reference counts in the target objects are adjusted. When the reference count drops to 0, the target object gets destroyed. While there are live references, the object can't get destroyed from under them. All nice and well and simple, however still possible to get wrong.

The major problem with the reference counters is the reference loops. If object A has a reference to object B, and object B has a reference (possibly, indirect) to object A, then neither of them will ever be destroyed. Many of these cases can be resolved by keeping a reference in one direction and a plain pointer in the other.  This of course introduces the problem of hanging pointers, so extra care has to be taken to not reference them. There also are the unpleasant situations when there is absolutely no way around the reference loops. For example, the Triceps label's method may keep a reference to the next label, where to send its processed results. If the labels are connected into a loop (a perfectly normal occurrence), this would cause a reference loop. Here the way around is to know when all the labels are no longer used (before the thread exit), and explicitly tell them to clear their references to the other labels. This breaks up the loop, and then bits and pieces can be collected by the reference count logic.

The reference counting maybe single-threaded or multi-threaded. If an object may only be used inside one thread, the references to it use the faster single-threaded counting.In C++ it's real important to not access and not reference the single-threaded objects from multiple threads. In Perl, when a new thread is created, only the multithreaded objects from the parent thread become accessible to it, the rest become undefined, so the issue gets handled automatically (as of version 1.0 even the potentially multithreaded objects are still exported to Perl as single-threaded, with no connection between threads yet).

The C++ objects are exported into Perl through wrappers. The wrappers perform the adaptation between Perl reference counting and Triceps reference counting, and sometimes more helper functions. Perl sees them as blessed objects, from which you can inherit and otherwise treat like normal objects.

When the Perl references are copied between the variables, this increases the Perl reference count to the same wrapper object. However if an object goes into the C++ land, and then is extracted back (such as, create a Rowop from a Row, and then extract the Row from that Rowop), a brand new wrapper gets created. It's the same underlying C++ object but with multiple wrappers. You can't tell that it's the same object by comparing the Perl references, because they may be pointing to the different wrappers. However Triceps provides the method same() that compares the data inside the wrappers. It can be used as

$row1->same($row2)

and if it returns true, then both $row1 and $row2 point to the same underlying row. Note also that if you inherit from the Triceps objects and add some extra data to them, none of that data nor even your derived class identity will be preserved when a anew wrapper is created from the underlying C++ object.