My new blog about u-Simulator...

For those of you who might have seen some strange posts with the tag "cosimus"...

As the code gets a bit more functionality, there's now a bit more explanation about what those posts mean - and the subsequent posts will go to http://cosimus-news.blogspot.com/

Flying wooden cubes and the tree eclipse

Texture sending code finally works - the stupid mistake was in the wrong assumption about the lower level. So now I can enjoy the strange tree-like sun. Moreover, after the peek at libsl the TextureEntry is somewhat done as well - so now the cubes are made of wood instead of some strange gray matter.

All of this has exposed a few interesting bugs in the lower-level code - timers/slists, which I seem to have found and fixed - although as can be clearly seen, the strings now look a bit like junk - because of the absent null terminator (which was being automagically added by the same code that caused the texture sending to fail). To make them show up quicker, I made a funny patch - which attaches a callback on every object being created and makes it float up to 10m, and then back to 1m, then up again.

Creating the masses of these has exposed another interesting dilemma, which will probably cause the tweak to the use of the simple slist crawlers for the object updates. The funny problem for now looks as follows: suppose I have 100 objects. All of them are with timer callbacks, so they *move* - and move often.

This results in the corresponding slist entries being deleted and reinserted at the tail of the update slist.

Due to the "pull" nature of the updates, if the update iterator moves not too far within one step - then this results in some objects never moving on the client - because by the time the iterator manages to walk to them, they are on the tail of the slist again... I'll need to prove this theory by adding the dynamically tweakable number of the updates sent within a single cycle, but it seems rather plausible.

The interesting question is how to do it in the least quirky way - one possible solution is to measure the frequency of the reinserts of the given object update node, and if the number is consistently high, to periodically leave a node lingering around marked as "secondary", and have a "cleanup" iterator slowly moving alongside the slist and wiping out the secondary nodes. So the slower clients have a chance to get the updates still.

Having the lowest speed of it bounded, would guarantee that the maliciously (or pathologically:) slow client can not stall the resources on the server by forcing it to create an infinitely long slist. Of course, the slow client will now have to pay a price of potentially getting the multiple duplicate updates as it moves along - but that is a fair price for keeping the data structure size O(1) instead of O(Nclients) for the case of the separate per-client queueing. Of course, premature optimization and all that - maybe it is simpler not to try to be smart and have a per-client "intelligent queues" - but assuming there are 200 clients, each object change implies the 200x work at once, and probably to throw away stuff for the majority of these... That's seems a bit too wasteful - and would kill the elegance of simply putting the newly connected client to crawl from the beginning of the object update slist...

Objects, updates, and iterators

Today was the day of object updates. That is, writing the object updates.

The initial implementation is going to be very simple: an array of objects indexed by local id, and a queue of "local updates" with the members pointing towards which objects need to be updated. When the object gets updated, its reference moves to the end of this queue. Each agent periodically advances iterator on this queue as it sees fit, and sucks in the updates.

If there's a new connection - then its iterator is placed in the beginning of the queue, hence getting the updates for all the objects within the scene.

Indeed, polling an iterator for each agent seems like a lot of overhead - but I think it is not - what it would allow is the appropriate pacing of updates - slower clients would get the updates less frequently, and those would be more coarse. The faster clients will get the updates more as they come - hence will get smoother updates.

But there's one small detail - for this to work, the iterator implementation needs to be flawless. Which apparently is totally not the case :-)

Looks like I need to sit and write what happens in each specific scenario - otherwise it is a very good recipe to spaghetti code.

user database, activerecord, and extension to HTTP

Today was mostly about figuring out the intricacies of the certificate generation in openssl, and wrapping them into the appropriate Ruby code - and a bit of standalone ActiveRecord coding.

As a result, I now have the module, that implements PKI in a way that allows to operate it without the major headache:

uca = UCA::UCA.new([ ["CN", "Test CA" ] ],
      "Test CA", Proc.new { |flag| "test" })

u = User.new
u.firstname = "Dalien"
u.lastname = "Talbot"
cn =  [ ["CN", u.firstname + "_" +
        u.lastname + "@" + 'localhost' ] ]
rsa, csr = UCA::Utils::generate_csr(1024, cn)
cert = uca.sign_csr(csr)
u.rsa_cert = cert.to_pem
u.rsa_key = rsa.export(
  OpenSSL::Cipher::DES.new(:EDE3, :CBC), "test" )
u.save!

This small fragment of code creates the user, initializes a tiny CA, and creates a new user record with the certificate signed by this CA.

Now, in the previous post about groups, presence, etc. I was thinking about nice half-persistent connections between the presence servers. HTTP would not necessarily fit there unless I'd be interested to make two unidirectional connections - which is boring.

So, the other part of the fun was figuring out the way to do it in a simplest way, such that I could reuse the webrick as much as I can... And I think I found a pretty fun hack to do it - CONNECT method.
There's an old draft which somewhat describes this method, and from what I know, de-facto it is implemented (even though I could not find the published RFC describing it).

I'm (ab)using this method to provide the "direct connection" between the two stream-oriented applications on client and server. As soon as the server replies with the standard HTTP reply "200 OK" - the two endpoints on the client and the server are connected with asynchronous stream, and can send the data to each other whenever they want. The only difference between the "classic" usage and mine is that I will probably use the URI in lieu of hostname:port - which will describe the point to connect to on the server. (especially since obviously the server would not tunnel the connection anywhere further).

It's a bit of arm-twisting, but seems to integrate quite nicely both with webrick and the C code that I have. And since the stream will be SSL-encrypted anyway - noone should care.

Obviously the process of "short-circuiting" will need to take into the account the certificates presented by both sides, and possibly establish the ACL/QoS based on that.

Also, the Ruby code got an excellent UUID library, so now both the C and Ruby can generate the mac-based UUIDs.

Update:

on a second thought, the "CONNECT" idea is quite a bad one. The end result is that the code on both sides will have to demultiplex the flow of data in two different directions - which adds the complexity and bugs... So it will be put into a box for now.

Thoughts on presence, chat, and groups...

Even though it's pretty much early for this, I've started to muse more in detail about scaling the chat/presence/identity thing. I think it's actually pretty straightforward if we introduce the concept of "home server" - a place where the avatar "belongs". This does not have to be a sim as such - since these activities are not necessarily related to the 3d presence.

A user would have a "home identity server" - something that they trust enough to hold the private key of the avatar, and authorize the signing / encryption operations using this key. This server would house also their "profile" - something that holds the pointers to the their "home inventory server", "home message server", "home presence server", possibly even "home physics server" (even though at current the distributed physics is probably out of the question, one should not assume it will always be like this). The "publicly viewable" profile would also hold the offline contact mail - dedicated to the communications when "off-line".

Then a lot of things become quite easy. Let's take a look at presence. If I add you to my contact list, all I have to do upon my login is to have my home presence server contact the home presence servers of my contact list and notify them that I am online - then they can update the state of the contact lists for the folks who are based there - and correspondingly to let my presence server know in return which of my contacts are online. Assuming the "friendship" link between the presence servers is protected by a shared key specific for this link, it will be rather difficult to spoof - as well as to get an unsolicited presence queries, unless explicitly permitted.

Of course, then revoking the "friendship" is also possible by either of the sides - you just invalidate the shared key for that link, and then the matter of
unsolicited queries reduces to a classic problem of fighting off the DoS against a website - which, although it is a difficult problem, has already received enough attention and has some solutions.

IMs are again trivial - my chat server knows who is online and who is not from the presence server, and can either relay the message to the contacts' chat servers or directly send it to them via their contact email in case they are offline. What's nicest is that then it is only the two servers - those of the sender and of the recipient - participating in the process, so this should scale pretty well as the number of "providers" go up.

Groups then could become just an special abstraction of "contact list" - with the difference that it would act more in a hub-spoke fashion - the members would send their presence / chat data to this server, and it would be the group server authorizing (or not!) chat in the groups, or providing this right to only a few people, etc.

These "contact list records" stored in the friends list / groups could hold some more interesting stuff - e.g. does this user allow the inventory offers from members of the given group, or from its contacts. Of course, the final permission check would be done on the recipient's servers - but putting the signed info as close to the source as possible, it would allow to prevent the waste of resources amongst the "well-behaved" servers.

And again - the protection from the ill-behaved servers reduces to countering a DoS from an untrustworthy source.

I'm pretty sure this is all doable with a little bit of PKI+shared secret+SSL woodoo.

The only (possibly large for some) drawback that I see is the need to expose an email address into the "identity profile" - which needs to be tackled. But the exposing of the email address only makes it resilient in the case of the server-side problems - i.e. in the case of IM, if your chat server could not contact my chat server (which was brought down by a vicious admin), then it would send an email using the exposed mail address.

Nothing prevents from just allocating a "VW-only" email address on the chat server (or its mail-handling counterpart) itself - then the server failures will only cause the delayed delivery of the IMs, but not a total failure. Probably that's the best way.

And given that your home chat server might allocate more than one email - say, one per contact, it would become quite easy to sort/prioritize the email-based IMs. And possibly even request the sent messages be signed by the sender + have the sender's profile attached - this way one can verify their authenticity, and store the state within the message itself.

Consoles, sessions, sockets and other stuff

Safe lists slowly got some code, as per this post, and I needed to test the code... However, I am slowly getting annoyed with the impossibility to dynamically tweak the debug levels.

Hence, I used the excuse of debugging the slist code to implement stupid console service - very simple, using openssl s_client (it does not provide the fancy terminal emulation, and at the moment there is no authentication (yuck!) - but it serves its purpose.)

The presence of the "console" code allowed to start playing with various commands - first one of course was to enable/disable debugging, and then there was some lower-level stuff, like the ability to show the sockets which
are being handled at this moment:

So, here's how it looks so far:

cosimus> show sockets
Running command 'show sockets'
Sockets:
  0:tcp  do_ssl:0,ssl:0,listen:1,lport:2323  remote:         0.0.0.0:0     fd:3     revents:0
  1:udp  do_ssl:0,ssl:0,listen:1,lport:9000  remote:       127.0.0.1:28032 fd:4     revents:0
  2:tcp  do_ssl:0,ssl:1,listen:0,lport:0     remote:         0.0.0.0:0     fd:6     revents:1
  3:udp  do_ssl:0,ssl:0,listen:1,lport:9000  remote:       127.0.0.1:28288 fd:7     revents:0
  4:udp  do_ssl:0,ssl:0,listen:1,lport:9000  remote:         0.0.0.0:0     fd:8     revents:0
cosimus>

Simple and stupid, but serves its purpose.

As we can see, also now there is a rudimentary code to understand the concept of client sessions - such that it was possible to hook up the update routine based on the slist of the local objects (aka lobjects, for short :)

6242 lines of code, if not to count the bazillion of auto-generated stuff.

A missing sunset

I managed to get the sun texture cleaned away off my cache, and I did not fix up the texture sending yet. The notion of the missing sun was quite funny, so I figured I'd make an attempt to do some sort of "arts" about it :-)



(BTW - the blue field on the right is "the water at its default level" :) Feels funny to experiment with the world of no physics and discontiguous water surfaces :-) (oh, and non-moving nudist avatars, for that matter:-)

Safe lists with iterators - useless musings about the data structures

While thinking about making the cubes persistent, and keeping in mind my bug within the list code, I came to a conclusion that to have any sort of iterators, the pointer/malloc based lists will be more a nuissance than help, so I have to come up with something that would encourage a more productive programming pattern.

I liked the feeling I got while coding the allocator for the timer structures, so decided to reuse this "generation+index" model once more - this time for lists.

How ? Each list essentially is managed as a resizable array of element structures. Each element is either allocated or is free. If it is free - then it belongs to the free list, and further discussion about working with it is quite boring - it is a simple unidirectional list, with the new elements grabbed from its head, and the newly freed elements being put onto its tail. But it is much more interesting to think about the allocated entries.

Each entry has a lock count - which greatly simplifies the iterator creation - simply increment the lock counter, and return the index (and element generation, of course). Then the "get_next" iterator will retrieve the "next" index from this list item, decrement the lock count, and it if is zero - then return the element to the free list.

There's only one "but" in all this: the explicit deletion of the element.

Suppose we have the list:

A->B->C->D

we start walking the list, and end up at B - whose index is stored elsewhere - so the picture will look like this: (the number of brackets is the number of locks):

(A)->((B))->(C)->(D)

Now we need to "delete" the item B explicitly and requeue it to the end of the list... So the structure now looks like:

(A)->(C)->(D)->(B')
(B)->(C)


Theoretically all is great - however, now assume the worst-case scenario that we also need to delete and requeue "C"... so we end up with this situation:

(A)->(D)->(B')->(C')
(B)->C

The "C" is now freed - so technically speaking it is undefined - so the get_next iterator will fail...

The way out of this might be to have the locks done only for the iterators use, and check the "previous" item's lock in case of deletion. Then the whole exercise will be done as follows:

1) after the first yield:

A->(B)->C->D

2) after the deletion of B:

A ->C->D->B'
(B)->C

3) now when we attempt to delete and requeue C, on the picture it is all nice... we need to check if there exists an "iterator-locked something" - like B in this case. Except the only small problem - C only has one "prev" index - so the only thing it knows about is A...

Ok, take 2 - we lock "this" and "next" items for the purposes of iterator, so the picture is:

1) after the first yield:

A->(B)->(C)->D

2) after the deletion of B:

A ->(C)->D->B'
(B)->(C)

3) after the deletion of C:

A->D->B'->C'
(B)->(C)->D

All looks great, except now we also would like to delete "D" - which brings us to the problem in the previous example!

However, I think there is still a way out.

Upon the request to delete the "iterator-locked" node, the next node also needs to be "iterator-locked":

1) after the first yield:

A->(B)->C->D

2) delete the B:

A->(C)->D->B'
(B)->(C)->D

3) delete the C:

A->(D)->B'->C'
(B)->(C)->(D)


Intuitively, this approach should prevent the need to find back "the nodes who refer to the node being deleted". Although, of course if has a big drawback - the iterator will need to walk all of the deleted nodes - with allegedly much more recent versions available at the end of the list - so these should be skipped. Which, in case of a large interval between the executions of the iterator and the massive updates to the list, will cause an excessive CPU cycles while skipping the empty elements. Which could probably be ok - I just might need to add a special case - "tried to skip the dead elements, but too much junk in the way - try again later".

Script security in the distributed environment

I won't write yet again that "once you copied something, you lost the control" - so obviourly the source of the scripts has to stay on the original sim (home/inventory sim). Now, how about if we make this even more extremist and keep the whatever binary is there as well (byte code or such) on the home sim ?

This creates a couple of interesting interactions:

1) script creator <-> home sim owner = someone has to pay for the CPU and bandwidth taken by the script execution
2) script creator <-> script owner = now the replication is actually a *constraining* factor for the close-sourced scripts, which means that may be close-sourced scripts might need a "subscription" based model of business to compensate for the (1).
3) script creator <-> script owner's sim owner = possibility to allow to run the script in the non-native environment. What determines whether to allow this or not - an open question.

The coolness of this approach is that it would stimulate the creation of open code, to an extent - since the closed code will accumulate on the home sim and eventually render it almost unusable. But, given the enough backchannel funding from the users (on a service-based model) - this could actually cause a creation of a lot of "closed overlay trees" on top of the grid - and might be a good and interesting thing for the metaverse economy.

Running under electric fence

In one of the previous posts I was promising to give a whirl to ElectricFence. Despite of the flurry of posts (which, as you can correctly infer, means I did not do anything meaningful at a large scale :) - I still did something... Two things. First - inclusion of the reference code for UUID operations from RFC4122, and also the RFC itself into "docs". There's a bunch of the code that I currently do not use - but given that it's still much smaller than the 500-something kilobytes library that I've found otherwise (what, WHAT is there for 500 kilobytes ?:) I am happy with it.

The second thing indeed incorporating the electric fence as part of the build - so the whole thing is now exploding with various memory diag and safety tools :)

ElectricFence allowed indeed to uncover one stupid lapse in the autogenerated serialization/deserialization code.

My assumption about the char[X] members of various structures was that they would hold the strings. Now, there is a "Color" member, which is declared as char[4] :-) So, when this array was set to 0xFF, 0xFF, 0xFF, 0xFF, and I called printf("%s", Color) - obviously the printf walked past the array - which was excellently caught by the efence, so now the _to_s routine just prints the hex values. I should fix it to be smarter and print a more friendly hex dump with characters.

Thinking more about the object updates sent to the clients - they should not be hard-tied to the object updates made by agents (hence exhibiting "received objectAdd - processed - sent objectUpdate to all" pattern) - but rather be "soft" and happen as a modification of the local objects queue (addition of elements to the tail of it) - this will allow to avoid any duplicate code to handle also the "external updates" (not by any of the agents, but rather by the processes), and gives much more headroom in the packet QoS/shaping field.

c-pluff: a smart C plugin framework

Here. With a MIT license, which is great. Looks very much interesting - the plugins can provide their own extension points, so one can build the "layered" functionality. From reading the docs it looks terribly interesting (although I dislike the XML, but well, it's a standard). I'll put this on the backburner and see if I can test it out one of these days with respect to the performance / etc. Or if you had any experience with it - leave a comment here.

Walking over a large list. Slowly and safely.

In my timer code I've deliberately avoided having to deal with the problem of the possibility of the concurrent list traversal - since it is basically an array of lists, and each list I walk exactly in one shot (under the assumption that I would not have the 200000 timers to shooting at the same time) - so the problem does not exist.

However, it is more of a corner case than the rule - I'll need to walk potentially large lists of stuff (not 200K, but 64K quite easily) - and send their contents very slowly and carefully (a blast of 64K of the packets even on the fastest link is a guarantee that you clog the pipe somewhere inbetween and lose the packets - so the list will need to be walked slowly.

There are a couple of interesting articles around the subject - iterators on pine wiki, and continuations.

Continuations are basically a way to reimplement the threads (which I do not want), so I will probably just use the iterator functions, which will take the saved state as one of the parameters - and lock the list items as I hold on to them - to prevent the annoying bugs which come when the two pointers point to the same location, and one piece of code suddenly decides to free it. I've had this kind of bug this weekend - almost a day of a lot of fun to track down, since it is hard to consistently reproduce, and caused more or less random areas of memory to get smashed - depending on what was the sequence of events. Luckily at least I knew the new code that started all of this - but the presence of a second bug of a similar kind did not make the things better :-) That one got smashed with the help of valgrind. Although I also long wanted a chance to play with ElectricFence - so this weekend I'll probably give it a shot - I think I did not yet exhaust my bugs-per-KLOC ratio for the past weekend's code spurt :-)

How does your first cube feel ?

To me - it feels awesome :-) Even though it only exists in the viewer only - because this is just the dummy packet sent to the viewer, and even though it is fully gray... But it's the first one :-)



(Also, note that the nameplate above the avatar includes "| example.com" - that's my take on how it should look. "Firstname Lastname | home_sim_domain" - and this automagically solves the problem of the name duplication... well, sort of - at least on the visual side :-)

What I call a productive weekend...

It's been a long weekend, and I also took the tuesday off.

I think I like the results:

Date:Sun Mar 23 03:10:08 CET 2008
3261 total

Date:Wed Mar 26 00:22:59 CET 2008
4674 total

4674 lines of C code, headers and comments, that is :-)
So, net 500 lines a day. Well, actually more - as I spent a good 1.5 days debugging a couple of memory corruptions - one caused by a bug in the newly done timer library, the other because the image download code was trying to expand the buffer by a negative amount (not a good idea.) :-)

What it can do so far - not much at all - in a half-prototype way:

- connect :)
- tell the client that the moon, sun and cloud textures are not found (although it persists). If I try to send those, then the client crashes - maybe I need to try a newer version as well.
- move the sun and moon around. This was the easiest one and I shamelessly borrowed the code from the respective module in OpenSim (as well as much of the other code).
- get the dead L$1000 of balance.
- chat with yourself - and you can see yourself chatting in the SL viewer.
- upload a picture - via the caps mechanism. Very simple :)

Now a few days of break to have some "RL work", and then back to the fun :-)

The magic of a timer wheel

I was looking for a decent C library, which would implement a simple timer callback functionality - i.e. I want to start a callback in 100 milliseconds from now... Apparently even allmighty glib does not have anything like this... I guess this is mostly because it goes with the threading model.

I might be biased - but my experience with the threads has been that they are much harder to debug than the code with "explicit multitasking" (i.e. the non-blocking IO loop) - I'll see if I am wrong with this assumption, but so far it was the case.

So, I went ahead and written a simple implementation of the timer wheel in its simplest form - just having an array of the next ticks, and list of timers to fire within that tick.

As I'm not doing all this in kernel space, I can take a reasonably wasteful size of the wheel - I took it to be 10000, which at a 100 ticks per second gives reasonable precision and reasonable maximum time - 100 seconds.

Since using the timer structures as pointers in memory is prone to the same errors as double-free (except that the double-stop is something that is definitely more possible), I've taken a decision to avoid using the pointers as much as I can - and using a growable array instead. And to combat a bit the reusal of the stale timers, I've taken an approach of having a "generation number" assigned to the timer - so it takes 256 reuses of the same timer index before the erroneous operation for the error to get unnoticed.

The result - on an Intel Core Duo 1.8 Ghz - I get around 10% CPU being used during the execution of the test with 200000 timers firing in at the same time. I think this can be optimized a bit, but for now I am pretty happy with the result - I will try to not need so many timers :)

The overhead (besides the static 40K of the timer wheel structure), is around 96 bytes per timer.

By far not very economical, but has the features I need - and the code is only 400 lines, including the volumious comments.