The Existential Program

In roughtly 1990, I wrote this program called “Who’s Calling?” for the Nascent NeXT computer.  The program itself was one of those early day PIM type programs, you know, contacts, calendar, etc.  The most interesting thing about it at the time was the ‘security’ mechanism I used to prevent random copying.  Basically, it had this little routine it ran when you installed it.  It would find a bit of unique information about your machine, and use that as key information to create a digest.  Once installed, every time the program launched, it would check that digest, and try to decode based on the bit of information from the currently executing machine.  If it got back what it expected, it would continue running.

It was a fairly simple process, that prevented casual copying.  In the end, it was probably more trouble than it was worth, but while coming up with that little trick, I headed down this path of exploring identity.  I asked myself questions such as “how can a program know when it has been tampered with”?  “Does a program have an identity?”.  At the same time, I was writing some collaboration apps, and other questions of authorization and authentication came up there as well.  If I’m collaborating with several people in a session, who has the right to take over the pen?  Does a new user requesting entrance into the collaboration have the right permissions to do so?  How do I know who they are?

This was all pre-internet boom, so it was very interesting.  Then the internet came along, and we went through a round of Berkeley style “free love, free information, free sharing…”, and then it all came crashing down.

But, now we find ourselves at the internet trough again, and those old questions of identity and authorization are coming back, but it a much more serious way.  People are exchanging banking information, and they really don’t want that shared or used by unauthorized entities.

So, I find myself contemplating identity and authorization in a big way, and I find myself going back to the very same old questions.  Does a program have an identity?  What is the smallest unit of existance?  As far as computers are concerned, I can tie this to the idea of the computicle.  Does a computicle have an identity?  The answer to me is yes, and in fact, this is part of what defines a computicle in the first place.

Looking back, I defined a computicle as having a few key traits:

  • Ability to receive input
  • Ability to perform some operations
  • Ability to communicate with other computicles

There is an implied identity in here.  You have to ask the question, “What has the Ability to…?”

You wouldn’t believe how this comes up in some of the most esoteric and mundane places.  For example, once I create multiple cooperating threads in my super computer simulator, I have to answer the question “Who’s responsible for managing chunks of memory?”

The scenario is simple.  Let’s say I have one computicle which does nothing more than generate keyboard/mouse events, and hands them off to other computicles to deal with.  Every time it creates an event, it allocates a chunk of memory, to hand off to the other threads.  Now, once that chunk of memory is created, who owns it?  The keyboard/mouse generator could retain ownership, but for how long?  Does a recipient have a guarantee as to when it might be freed or reused?  Should the recipient copy it?  How long do they have to copy it before it is stale?  Can they share this chunk of memory with others, or what?  It’s such a simple thing, but it seems so hard to deal with the combinatoric explosion.

Well, there are a certainly a few ways to deal with things.  First, I can go back and look at memory allocation.  I created a couple of simple heap structures a while back, and I recently revisited and updated them based on my work with the multiple threads.  One of the questions I was trying to answer is, can the memory chunk deal with its own destiny?  Said in less philosophical terms, can I use the GC system of Lua to manage the life of a chunk of memory in a reasonable and predictable way.

 
So, here’s a couple of data structures to deal with Heap allocated memory (Win32):

ffi.cdef[[
typedef struct {
    void *    Data;
    int32_t   Size;
    HANDLE    HeapHandle;
    DWORD     owningthread;
} HeapBlob;

typedef struct {
    HANDLE  Handle;
    int     Options;
    size_t  InitialSize;
    size_t  MaximumSize;
    DWORD	owningthread;
} HEAP;
]]

There are a couple of ways to allocate stuff in Lua. The regular way, without doing anything fancy, is to just create your thing, and start using it:

local myList = {}
myList.name = "William"
myList.job = "Programmer"

Eventually, once there are no references to your little list, it will magically disappear, being swept away by the garbage collection system.

Then, there’s allocating stuff using LuaJIT FFI:

local myChunk = ffi.new("char[256]")

Something allocated in this way will also be garbage collected, when the ‘myChunk’ variable no longer has any references to it. As long as you’re running with a single threaded environment, and you’re not passing your variables off to any other thread to deal with, this will work just fine. But, what if you need to have your chunk of memory last longer, even if you lose all references to it from the creating side.

The third way of creating a chunk of memory is to use a direct system memory allocation call. In the case of Windows, I could do the following:

local ptr = kernel32.HeapAlloc(self.Handle, flags, nbytes)

Ignoring for the moment where that ‘kernel32’ and self.Handle came from, essentially, you’ll get back a pointer to a chunk of memory that Windows knows about. Lua doesn’t know anything about this as a chunk of memory though. I could use ffi and tell the gc about it, and what function to call once ptr is no longer referenced, but really, if that is what you need, then you can just use the previous method of ffi.new(…).

So, here we have a lonely pointer, all allocated, and ready to use. I’d like to capture a bit of information about the creation event. Back to that existential programming, and back to the HeapBlob data structure.

I could do the following to assign the pointer to one of my HelpBlob data structures:

local blob = ffi.new("HeapBlob", ptr)

In this case, I have a HeapBlob struct, with the Data element initialized to the value the pointer held. So far, nothing has changed over the plain old ordinary ffi.new(), expect for the fact that I’ve just introduced a nice memory leak, wrapped up in an object. I need a bit more meat on the bones of the HeapBlob object. I want it to get in on the act of memory management. Specifically, when there are no more references to the object, I want the HeapBlob to deallocate the chunk of memory, thus, eliminating the memory leak:

So, I create a metatype to associate some functions with this simple data structure:

HeapBlob = nil
HeapBlob_mt = {
    __gc = function(self)
        if self.HeapHandle == nil or self.owningthread == 0 then return nil end

        if self.owningthread == kernel32.GetCurrentThreadId() then
            local success = kernel32.HeapFree(self.HeapHandle, 0, self.Data) ~= 0
        end
    end;

    __tostring = function(self)
        return string.format("Blob: Size: %d  Thread: %d",
            self.Size, self.owningthread);
    end;

    __index = {
        GetSize = function(self, flags)
            flags = flags or 0

            if self.HeapHandle == nil then return 0 end

            local result = kernel32.HeapSize(self.HeapHandle, flags, self.Data)

            return result
        end,

    IsValid = function(self, flags)
        flags = flags or 0
        if self.HeapHandle == nil then return false end
        local isValid = kernel32.HeapValidate(self.HeapHandle, flags, self.Data)
        return isValid
    end,

    ReaAlloc = function(self, nbytes, flags)
        flags = flags or 0
        if self.Heap == nil then return false end
        local ptr = kernel32.HeapReAlloc(self.HeapHandle, flags, self.Data, nbytes)
        if ptr == nil then return false end
        self.Data = ptr;
        self.Size = nbytes;
        return true
    end,
    }
}
HeapBlob = ffi.metatype("HeapBlob", HeapBlob_mt)

There’s a few functions in here, but the __gc function is the one that gets called whenever an instance of the HeapBlob goes out of scope, and has no further references to it. So, in the simplest case, you clould do the following:

HeapBlob(ptr)

And we’re back to having a handle on a piece of memory, and nothing will occur at __gc time, because we have not set an owningthreadid, and our self.HeapHandle is nil. Well, this is actually a good thing. This can be seen in a two thread scenario.

-- Thread 1
local ptr = Heap:Alloc(256)
passMemoryPointerToThread(ptr, 256, takeownership=false, heaphandle=nil)

-- Thread 2
local ptr = ReceiveMemoryPointerFromThread(ptr, size, takeownership, heaphandle)
local threadid = 0
if takeownership then threaid = Sys.GetCurrentThreadId() end
local blob = HeapBlob(ptr,size,heaphandle, 0, threadid)

In this scenario, thread 1 will retain responsibility for the allocated memory. It communicates this information first, by not giving the handle to the heap that was used to allocate the chunk of memory, and second by giving a flag indicating its desire. Really the witholding of the heaphandle is enough of a hint.

Thread 2 is free to go ahead and use the HeapBlob, pass it amongst its friends, etc. Then, when it’s no longer using the blob, the structure will be garbage collected, and nothing will happen to the bit of memory.

This HeapBlob could have additional information, such as a ref count, which can be incremented any time there is a new reference to it, but then it starts to look like a COM program.

If you want to pass along the Heap blob, and allow the second thread to take ownership, thread 1 would simply supply the heap handle. In that scenario, thread2 would have all the information it needs to manage the chunk of memory in ways that it deems appropriate, and it has received an explicit handoff from thread1 imploring it to do so.

This starts to give me better control of memory, which allows me to more strictly control the mechanisms between collaborating threads.

Getting back to Existence, if I can isolate and define one bit of existence, then I’m improving my ability to write fairly independent programs. I haven’t answered the question “who am I”, and “how am I different from another” as yet. But, at least now I have a way to communicate that I can control. I suspect answering the “who am I” thing will involve some GUID or other mechanisms, including ‘claims’ and possibly certificates. That will be an interesting exploration.

Advertisements

One Comment on “The Existential Program”

  1. […] I have written about the “computicle” concept a couple of times in the past: Super Computing Simulation Sure is Simple The Existential Program […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s