Stubs - Another explanation

Philip Quaife 2005-01-22, revised by PYK 2019-01-26:

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.

Stub Mechanics

tclStubs and tclIntStubs are C structures that contains pointers to each each of the functions in the Tcl public API and private API, respectively. A stubs-enabled extension statically links against libtclstub.a which contains Tcl_InitStubs and also a place to store a pointer to each of the stubs tables. When the extension is loaded, Tcl calls Tcl_InitStubs, which fills in those placeholders with pointers to the stubs tables.

When the extension defines -DUSE_TCL_STUBS and includes tcl.h or tclInt.h, macros redefine all the Tcl function names to instead be the corresponding items in the stubs tables. For example, this:

pos = Tcl_Tell(channel);

is rewritten by the macros into:

pos = tclStubsPtr->tcl_Tell(channel);

Stubs in extensions

Each extension can provide its own stubs table. Other extensions can link to this stub table to access functions in the 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 starkits.)

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 its 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 2005-01-29: 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?

xk2600 Was this ever implemented? or a patch ever created to implement this? The reason I ask.. I have a specific need to be able to provide multiple "environments" ala slave interpreters which utilize different implementations for testing of the same module (via load) as well as perform unit testing against patches that implement specifically what is noted above: different versions of hash tables... to modularize tclcore and tcllib. I would be more than happy to provide an implementation of double indirection for the tclstubs mechanism, but don't wish to perform work that is already done. From what I can tell tclstubs is still a single indirection, however, if someone can point to me either in code or where the patch noted above exists I would be very appreciative.

Page Authors

Philip Quaife
PYK