Linker's link sets

I don't know about other linkers, but GNU ld provides a very useful feature: link sets. A link set is a list of symbols constructed during link time which can then be inspected in regular code. This is very interesting in situations when you want to initialize several subsystems from a centralized place but don't know which of these will be available; that is, you don't know which ones will be in the final binary.

To illustrate this feature, let's see how NetBSD manages file system initialization. In NetBSD, you can configure which file systems you want in your kernel binary and which not. Each file system has a vfs_init hook that must be called during system initialization but... how to do this in a clean and extensible way? For a moment, imagine we didn't have link sets. In this case, NetBSD would need a function similar to the following:

void
init_file_systems(void)
{
#ifdef UFS
   ufs_init();
#endif 
#ifdef MSDOSFS
   msdosfs_init();
#endif 
...
#ifdef TMPFS
   tmpfs_init();
#endif
}

Isn't this ugly? Very much, although one might support the visual ugliness. However, the real problem is that, in order to add a new file system, you need to edit other parts of the system; this might seem acceptable in an open source project, but what if the initialization code was closed source? You couldn't add your file system. This clearly goes against extensibility.

Using link sets, this problem goes away: each independent module is able to add itself to a global list of symbols. Continuing our file systems example, take a look to the vfsinit function in kern/vfs_init.c. The first thing you see there is the declaration (__link_set_decl) of a new link set, called vfsops, that will hold pointers to struct vfsops objects. Then, the code uses the __link_set_foreach construction to iterate over the list, correctly initializing all the file systems. The following is an extract of this, with many details removed:

void
vfsinit(void)
{
   __link_set_decl(vfsops, struct vfsops);
   struct vfsops * const *vfsp;  /* Iterator */

   __link_set_foreach(vfsp, vfsops) {
       (*vfsp)->vfs_init();
   }
}

At last, how does a module add itself to the link set? Using the __link_set_add_data operation, which takes the name of the link set as its first argument and the object to be added as the second one. E.g.:

struct vfsops barops = {
   ...
   ufs_init,
   ...
};
__link_set_add_data(vfsops, barops);

As you can see, using link sets the kernel does not need to know at all which file systems are compiled into it, yet the initialization code will be executed.