[Philip Quaife] ''22 Jan 05''


This is how I understand the [stubs] mechanism works internally. I wrote this while looking into the merits of virtualising the stubs mechanism. Other documents on this [wiki] describe the process from the users point of view. This is more of a tech note.

The information presented here has been gained by looking into the source code of [Tcl]. My understanding of the workings may not be 100% accurate. 

In the following text the words ''[extension]'' and ''shared library'' are used interchangably.


**In Tcl**

In Tcl there is a a table of jump vectors that point to each of the Tcl API functions called ''tclIntStubs''. This table is filled in with pointers to all the `Tcl_*` API funtions at compile time. This table is private to the Tcl library and not visible to outside extensions. When Tcl loads, the OS relocates the pointers in this table to reflect where the functions are actually resident in memory.

Along with this table, there is a Stubs Table pointer:
         * tclStubsPtr

When [Tcl_InitStubs] is called, the public pointer ''tclStubsPtr'' is assigned to a region of newly malloced memory. The static table (''&tclIntStubs'') is copied into this memory.


The reason why this is done is not clear. Obviously the static table (''tclIntStubs'') may be loaded into read-only const memory by the OS, and would not be able to be changed. However, there aren't any public API functions that allow the replacing of the function pointers in the stubs table pointed to by ''tclStubsPtr''.

Internally, Tcl core code calls all API functions directly and not via the stubs table.


**In the extension**

When the global ''-DUSE_TCL_STUBS'' is defined when compiling your source code, all the public Tcl API functions (`Tcl_*`) are redefined as vectors in the jump table ''tclStubsPtr''.

When we make a dynamic library, this reference (tclStubsPtr) is undefined and will require fixup when we load the library.
Since the variable is a pointer, as well as some optimisation in GCC, we only have one reference to the variable ''tclStubsPtr'' in the library.

The only exception is [Tcl_InitStubs] itself, which is made available through the static stub library that you link the extension against.


**When we load the extension**

When the OS loads the extensions dynamic library into memory, it must resolve the unknown symbol ''tclStubsPtr'' which it finds in the already loaded shared library ''libtcl??.so''. 
It then goes through every relocation symbol in the library and fill in the address in the loaded library file. On ix86 processors this just involves relocating one symbol in the global offset table. Other cpu's may require the relocation of every call made through this symbol.

Without this step any call to a Tcl API function would result in a '''segmentation fault'''.


After the shared library is loaded, Tcl asks the OS dynamic loader for the address of the function '''ExtensionName'''''Stubs_Init'', and then calls it to allow the library to perform any initialisation.

This usually involves registering the extension with Tcl as a package.


**How do we now call a Tcl function**

When the source code was compiled , all calls to the Tcl_* API function were changed into an indirect call via a table of pointers.
Conceptually, the statement:
        pos = Tcl_Tell(channel);
Was changed into:
        pos = tclStubsPtr[492](channel);

In reality the stubs table is created as a structure of individual function pointers to preserve type checking. So it actually looks like this:
        pos = tclStubsPtr->tcl_Tell(channel);

When Tcl first started, it assigned the global pointer ''tclStubsPtr'' to a table that has the addresses of all the Tcl_* API functions, the call will now find the API function wherever it was loaded by the OS.

This means that you can dynamically load this extension into any program that has a global symbol called ''tclStubsPtr''.

''Unless you provide a table filled with function pointers however, any attempt to call a function in the shared library that called a Tcl_* API function would result in a segmentation fault.''


**Stubs in extensions**

Each extension can have it's own stubs table. So if you want to link in with another extension you can instead link to it's own stub table to call functions in that extension.

The mechanism is identical to the use of the Tcl stubs table except that it is referenced by a different name, for example:
      imgStubsPtr

When you include the public header for the extension, and have defined the requisite global define, all calls to the extension would be changed into calls through the extensions stub table, such as:
       imgStubsPtr->img_GetAlphaChannel(....)

One prerequisite is that any extensions that you have linked to must be already loaded before your extension gets loaded. Otherwise the OS will return a symbol relocation failure to Tcl.


**Why was stubs added to Tcl**

I don't know. This was a common technique before dynamic link loaders were developed and refined to the point they are at today.

On Linux, dynamic linking is quite successful, even with complicated heirarchy's of dependencies.

Other OS's may not be so flexible. ''([DKF]: Indeed, Windows definitely is not. Also, even Linux is not quite so flexible in more complex linking scenarios with [starkit]s.)''

Since we don't stubify calls to system libraries such as libc and libm, we are still are at risk of changes to these libraries preventing an existing extension from loaded correctly.


'''Whats different about my VStubs proposal'''.

I touched on Vstubs in [Tcl Core - Is All] as a way of allowing extension to tcl at the core level without having to recompile the core.

The principle difference in my proposed extension to the stubs system is that the linking is done the other way around.

Each extension has it's own jump table with initially unknown offsets. When the extension is loaded, in the ''Extname_Init'' function, a call is made to Tcl's Stubs subsystem (by way of passed in pointer) requesting that Tcl fill in the names of the functions that it needs. This will include functions to other extensions such as Tk, or Img, et al. The order of the extensions being loaded is not significant.

In this way there is no direct linkage from the extension to TCL. There are no unresolved symbols in the extension.
(For example, an extension that wants, say, the Img extension can still load even if Img is not present. This is not possible with the present stubs system.

The resolution of the function names is now done by way of name rather than position in the table. The extension does not need to know about functions it never calls. It can also set up dummy functions for library calls to other extensions that are not loaded to offer reduced functionality. An example of this would be the Img extension loaded without Tk. This could be used to provide image processing capibilities for, say, cgi scripts when no GUI is needed.

An extension can also introspect the vstubs table for all currently loaded extensions.

The most important feature of vstubs would be that any extension could intercept an API call for a host of useful purposes not outlined here. This applies to other extensions loaded, as well as Tcl API functions. It could change the parameters before revectoring to the original function pointer, or it could replace the functionality completely.

The possibilities are endless.

----

[NEM]: I'm not entirely clear on what you mean by ''"The resolution of the function names is now done by way of name rather than position in the table..."'' What is a "name" in this context? A string? As a further thought experiment: imagine a system where you could write functions in C, and register them somewhere (in something called, say, an "interpreter") with a string name. Now you could code everything up via the interpreter (say by doing Tcl_Eval(interp, cmd...)). The possibilities are endless... OK, that is a bit facetious. But there is a serious point here: If we go far enough down the flexibility path then we essentially arrive at a general purpose interpreter library which can be used to interface different modules written in C, or some other language. This is exactly what Tcl was built for, and what it is still very good at. Now the existing stubs mechanism solves a single problem well, and efficiently. It works around specific problems with C dynamic linking, AIUI. I'm not sure that your VStubs proposal adds anything, but it seems to duplicate functionality offered by the Tcl language itself.

[NEM] ''Note: there was just an edit conflict while I was posting to this page. Wiki didn't take it well and the result was garbage. I've restored from the version I was editing, so someone (I think [lv]) may have lost an edit - sorry!''

[PWQ] ''NEM'', I am not sure what is so hard to understand in my text, here is an example.

DeveloperA: Wants to change the hash used by associative arrays to use a perfect hashing function. While there are functions to create a custom hash function, there is nothing to direct the array code to use it.

DeveloperA patches the core and write the code, it is good.

DeveloperB: Wants to try out developerA's new hash for their application. They must patch their own interpreter to try out the code.
DeveloperA is using Windows while developerB is using Solaris, and the build process is complicated.

If vstubs were implemented, then the above could be done with an extension. If it was done right, it could even be implemented in tcl script.

So when you talk about extension via commands, you are touching on the next expansion. Why have a command table and a stubs table?, why are there external commands and internal API ones?, I will leave this for another post.

So ignoring the merits or failings in the example, what comments do you (nem) have on vstubs?

[NEM] OK. So all function calls to any public API function (whether in the core or an extension) goes through a (many?) giant stubs table, correct? However, this stubs table is dynamically created at runtime as extensions register their APIs, correct? So, how do you map function name to stubs table entry? AIUI the current mechanism does this at compile-time using macros etc. Now, if your stubs table is dynamically created at runtime, then obviously the mapping also has to be done at runtime. So, how do you do this mapping? How does the extension ''"...[[request]] that Tcl fill in the names of the functions that it needs..."''? What is a "name"? The point I was making before is that this mechanism is going to be a lot like an interpreter. The current stubs mechanism is much more efficient and is essentially a compile-time trick with little (no?) run-time overhead. I would suspect that making all of Tcl's internal calls (at least those to public API functions) go through an interpreter (even a very efficient, specialised one) would cause an unacceptable performance hit, as well as a loss of type-safety at the C level. I don't think the examples given would justify this.

To clear up some basic points, there seem to be two aims of your proposal: firstly, it should be possible to replace an entry in Tcl's stubs table with a different implementation and have Tcl (and extensions) start using the new version; secondly, there should be a central mechanism for negotiating distribution of each extensions stubs table pointers. Is that much correct?

[PWQ] ''29 Jan 05', NEM: The resolution of API addresses can be resolved by a number of ways, I would suggest that in the call to ''Extension''_Init that TCL pass a stub table that has pointers to the functions for the Vstubs system. Another way is to use the symbol resolution process that TCL already uses when loading extensions.

Once the ''name'' has been bound to an address, there is no need to 'resolve'' the name again. That is I am not proposing that we call the resolver on every call. The use of double indirection allows TCL to  change the pointer (if functions are renamed or replaced, or an extension wants to intercept the function call), without having to update the extensions' table of pointers.

As for overhead, we are talking of four instructions per call instead of two (the current stubs mechanism forces all extensions to call through the stubs table). I would offer that the mode (average) of all TCL_* functions is more than 100 instructions, so we are talking about and extra 2% at most extra time. Not enough to rule it out as excessive. 

Function calls (and jumps) are expensive instructions on all modern CPU's, so we have to accept some penalty for having modular code practices.

I am not sure what you mean by ''central ... distribution'', I have made reference to a Central repository of extensions, but this is not directly related to stubs.

Your first point is correct with regard to stubs. While any extension can at this moment change the pointer in the stubs table by virtue of writing to the stubs structure, it would be better to have a formal interface that isolates the extension from changes to the structure, and also at present the changes don't affect the compiled TCL core code as they don't use the stubs table.

As far as the central mechanism is concerned, I am talking about a formal set of TCL_* API functions that are documented that allow the ordered and structed access to the stubs tables (as created by TCL, TK  and other extensions) that can allow replacment of the pointer for purposes as deemed desirable by the extension writers of the future.

An extension publishes (registers) their own API with TCL as if you like the central interface that allows other extensions to 'find' the address of other extensions routines that it may want to call , or ''steal''.

While the average TCL developer will never see any need to intercept say the function ''Tcl_ReadChars'', they will just have to accept that other developers will find real and benificial use of the ability to do so. 

If we provide a mechanism to do this that does not involve changing the core, it can only be good.

Most people would never dream of redfining the 'if' command in TCL, we don't however stop anyone from doing so. Why put limits one things when they don't need to.

A Simple case in point. If the VStubs features as described above have been available in tcl 8.0, the TCL virtual file system (vfs), could have been implemented as an extension without any changes to the core, simply be stacking on top of the channel handlers (via VStubs). Nor would we have had to change the core to allow channel handlers to be stacked (ala [Trf]).

[NEM] Can you produce a patch that demonstrates this mechanism?

<<categories>> Internals