of this analysis we looked at how the polymorphic side of object-oriented
programming was implemented in the Linux kernel using regular C constructs. In
examined method dispatch, looked at the different forms that vtables could
take, and the circumstances where separate vtables were eschewed in preference
for storing function pointers directly in objects.
In this conclusion we will explore a second important aspect of object-oriented
programming - inheritance, and in particular data inheritance.
Inheritance is a core concept of object-oriented programming, though it
comes in many forms, whether prototype inheritance, mixin inheritance,
subtype inheritance, interface inheritance etc., some of which overlap.
The form that is of interest when exploring the Linux kernel is most
like subtype inheritance, where a concrete or "final" type inherits
some data fields from a "virtual" parent type. We will call this "data
inheritance" to emphasize the fact that it is the data rather than the
behavior that is being inherited.
Put another way, a number of different implementations of a particular
interface share, and separately extend, a common data structure. They
can be said to inherit from that data structure.
There are three different approaches to this sharing and extending
that can be found in the Linux kernel, and all can be seen by
exploring the struct inode structure and its history, though they
are widely used elsewhere.
Extension through unions
The first approach, which is probably the most obvious but also the
least flexible, is to declare a union as one element of the common
structure and, for each implementation, to declare an entry in that
union with extra fields that the particular implementation needs.
This approach was
to struct inode in Linux-0.97.2 (August 1992) when
struct minix_inode_info minix_i;
struct ext_inode_info ext_i;
struct msdos_inode_info msdos_i;
was added to struct inode. Each of these structures remained empty
until 0.97.5 when i_data was
from struct inode to
Over the years several more "inode_info" fields were added for
different filesystems, peaking at 28 different "inode_info" structures in
ext3 was added.
This approach to data inheritance is simple and straightforward, but
is also somewhat clumsy. There are two obvious problems.
Firstly, every new filesystem implementation needs to add an extra
field to the union "u". With 3 fields this may not seem like a
problem, with 28 it was well past "ugly". Requiring every filesystem to
update this one structure is a barrier to adding filesystems that is
Secondly, every inode allocated will be the same size and will be
large enough to store the data for any filesystem. So a filesystem
that wants lots of space in its "inode_info" structure will impose
that space cost on every other filesystem.
The first of these issues is not an impenetrable barrier as we will see
shortly. The second is a real problem and the general ugliness of the
design encouraged change. Early in the 2.5 development series
this change began; it was completed by 2.5.7 when there were no
"inode_info" structures left in union u (though the union itself
remained until 2.6.19).
The change that happened to inodes in early 2.5 was effectively an
inversion. The change which
ext3_i from struct inode.u also
a struct inode, called vfs_inode, to
So instead of the private structure being embedded in the common data
structure, the common data structure is now embedded in the private
This neatly avoids the two problems with unions; now each filesystem
needs to only allocate memory to store its own structure without any need
to know anything about what other filesystems might need. Of course
nothing ever comes for free and this change brought with it other
issues that needed to be solved, but the solutions were not costly.
The first difficulty is the fact that when the common filesystem code
- the VFS layer - calls into a specific filesystem it passes
a pointer to the common data structure, the struct inode. Using
this pointer, the filesystem needs to find a pointer to its own
private data structure. An obvious approach is to always place the
struct inode at the top of the private inode structure and simply
cast a pointer to one into a pointer to the other. While this can
work, it lacks any semblance of type safety and makes it harder to
arrange fields in the inode to get optimal performance - as some
kernel developers are wont to do.
The solution was to use the
macro to perform the
necessary pointer arithmetic, subtracting from the address of the
struct inode its offset in the private data structure and then casting
The macro for this was called list_entry() simply because the
"list.h lists" implementation was the first to use this pattern of data
structure embedding. The list_entry() macro did exactly
what was needed and so it was used despite the strange name.
This practice lasted until 2.5.28 when a new container_of() macro was
which implemented the same functionality as list_entry(), though
with slightly more type safety and a more meaningful name.
With container_of() it is a simple
matter to map from an embedded data structure to the structure in which it is
The second difficulty was that the filesystem had to be responsible
for allocating the inode - it could no longer be allocated by common
code as the common code did not have enough information to allocate
the correct amount of space. This simply involved
alloc_inode() and destroy_inode() methods to the
super_operations structure and calling them as appropriate.
As noted earlier, the union pattern was not an impenetrable barrier to adding
new filesystems independently. This is because the union u had one
more field that was not an "inode_info" structure.
A generic pointer field
called generic_ip was
in Linux-1.0.5, but it was not used until 1.3.7.
Any file system that does not own a structure in struct inode itself
could define and allocate a separate structure and link it to the inode
through u.generic_ip. This approach addressed both of the problems
with unions as no changes are needed to shared declarations and each
filesystem only uses the space that it needs. However it again
introduced new problems of its own.
Using generic_ip, each filesystem required two allocations
for each inode instead of one and this could lead to more wastage
depending on how the structure size was rounded up for allocation; it also
required writing more error-handling code.
Also there was memory used for the generic_ip pointer and often for a
back pointer from the private structure to the common struct inode.
Both of these are wasted space compared with the union approach or
the embedding approach.
Worse than this though, an extra memory dereference was needed to
access the private structure from the common structure; such
dereferences are best avoided. Filesystem code will often need to
access both the common and the private structures. This either
requires lots of extra memory dereferences, or it requires holding the
address of the private structure in a register which increases
It was largely these concerns that stopped struct inode from ever
migrating to broad use of the generic_ip pointer. It was certainly
used, but not by the major, high-performance filesystems.
Though this pattern has problems it is still in wide use.
struct super_block has an s_fs_info pointer which serves the same
purpose as u.generic_ip (which has since been renamed to
i_private when the u union was finally removed - why it was
not completely removed is left as an exercise for the reader). This is the only
way to store filesystem-private data in a super_block. A simple search in
the Linux include files shows quite a collection of fields which are
void pointers named "private" or something similar. Many
of these are examples of the pattern of extending a data type by using
a pointer to a private extension, and most of these could be converted to using
the embedded-structure pattern.
While inodes serve as an effective vehicle to introduce these three patterns
they do not display the full scope of any of them so it is useful to look
further afield and see what else we can learn.
A survey of the use of unions elsewhere in the kernel shows that they are widely
used though in very different circumstances than in struct inode. The
particular aspect of inodes that is missing elsewhere is that a wide range of
different modules (different filesystems) each wanted to extend an inode in
different ways. In most places where unions are used there are a small fixed
number of subtypes of the base type and there is little expectation of more
being added. A simple example of this is
which stores file attribute information decoded out of an NFS reply. The
details of these attributes are slightly different for NFSv2 and NFSv3 so there
are effectively two subtypes of this structure with the difference encoded in a
union. As NFSv4 uses the same information as NFSv3 this is very unlikely to
ever be extended further.
A very common pattern in other uses of unions in Linux is for encoding messages
that are passed around, typically between the kernel and user-space.
is used to convey extra information with a signal delivery.
Each signal type has a different type
of ancillary information, so struct siginfo has a union to
encode six different subtypes.
appears to be the largest current union with 22 different subtypes. It is used
by the "coda" network file system to pass requests between the kernel module
and a user-space daemon which handles the network communication.
It is not clear whether these examples should be considered as the same pattern
as the original struct inode. Do they really represent different
subtypes of a base type, or is it just one type with internal variants?
object-oriented programming language
does not support variant types at all except through subtype inheritance so
there is clearly a school of thought that would want to treat all usages of
union as a form of subtyping. Many other languages, such as C++, provide both
inheritance and unions allowing the programmer to make a choice. So the answer
is not clear.
For our purposes it doesn't really matter what we call it as long as we know
where to use each pattern. The examples in the kernel fairly clearly show that
when all of the variants are understood by a single module, then a union is a
very appropriate mechanism for variants structures, whether you want to refer
to them as using data inheritance or not. When different subtypes are managed
by different modules, or at least widely separate pieces of code, then one of
the other mechanisms is preferred. The use of unions for this case has almost
completely disappeared with only
remaining as an example of a deprecated pattern.
Problems with void pointers
Void pointers are not quite so easy to classify. It would probably be fair to say
that void pointers are the modern equivalent of "goto" statements. They can be
very useful but they can also lead to very convoluted designs. A particular
problem is that when you look at a void pointer, like looking at a goto, you
don't really know what it is pointing at. A void pointer called
private is even worse - it is like a "goto destination"
command - almost meaningless without reading lots of context.
Examining all the different uses that void pointers can be put to would be well
beyond the scope of this article. Instead we will restrict our attention to
just one new usage which relates to data inheritance and illustrates how the
untamed nature of void pointers makes it hard to recognize their use in data
The example we will use to explain this usage is
used by the seq_file library which makes it easy to synthesize simple
text files like some of those in /proc. The "seq" part of seq_file
simply indicates that the file contains a sequence of lines corresponding to a
sequence of items of information in the kernel, so /proc/mounts is a
seq_file which walks through the mount table reporting each mount
on a single line.
is used to create a new seq_file it allocates a
struct seq_file and assigns it to the private_data field of
the struct file which is being opened. This is a straightforward
example of void pointer based data inheritance where the struct file
is the base type and the struct seq_file is a simple extension to that
type. It is a structure that never exists by itself but is always the
private_data for some file.
struct seq_file itself has a private field which is a void
pointer and it can be used by clients of seq_file to add extra state to the
file. For example
allocates a struct mdstat_info structure and attaches it via
this private field, using it to meet md's internal needs. Again,
this is simple data inheritance following the described pattern.
However the private field of struct seq_file is used by
in a subtly but importantly different way.
In this case the extra data needed is just a single pointer.
So rather than allocating a local data structure to refer to from
the private field, svc_pool_stats_open simply stores that pointer
directly in the private field itself.
This certainly seems like a sensible optimization - performing an allocation to
store a single pointer would be a waste - but it highlights exactly the source
of confusion that was suggested earlier: that when you look at a void
pointer you don't really know what is it pointing at, or why.
To make it a bit clearer what is happening here, it is helpful to imagine
"void *private" as being like a union of every different possible
pointer type. If the value that needs to be stored is a pointer, it can be
stored in this union following the "unions for data inheritance" pattern. If the
value is not a single pointer, then it gets stored in allocated space following
the "void pointers for data inheritance" pattern.
Thus when we see a void pointer being used it may not be obvious whether it is
being used to point to an extension structure for data inheritance, or being
used as an extension for data inheritance (or being used as something else
To highlight this issue from a slightly different perspective it is instructive
which represents a sub-device in a video4linux device, such as a sensor or
camera controller within a webcam.
According to the (rather helpful)
it is expected that this structure will normally be embedded in a larger
structure which contains extra state. However this structure still has not just one
but two void pointers, both with names suggesting that they are for private use
/* pointer to private data */
It is common that a v4l sub-device (a sensor, usually) will be realized by,
for example, an I2C
device (much as a block device which stores your filesystem might be realized
by an ATA or SCSI device). To allow for this common occurrence,
struct v4l2_subdev provides a void pointer (dev_priv), so
that the driver itself
doesn't need to define a more specific pointer in the larger
structure which struct v4l2_subdev would be embedded in.
host_priv is intended to point back to a "parent" device such as a
controller which acquires video data from the sensor. Of the three drivers
which use this field, one
appears to follow that intention while the other
use it to point to an allocated extension structure. So both of these
pointers are intended to be used following the "unions for data
inheritance" pattern, where a void pointer is playing the role of a union
of many other pointer types, but they are not always used that way.
It is not immediately clear that defining this void pointer in case it is
useful is actually a valuable service to provide given that the device
driver could easily enough define its own (type safe) pointer in its extension
What is clear is that an apparently "private" void pointer can be intended for various qualitatively different
uses and, as we have seen in two different circumstances, they may not be used exactly as expected.
In short, recognizing the "data inheritance through void pointers" pattern is
not easy. A fairly deep examination of the code is needed to determine the
exact purpose and usage of void pointers.
A diversion into struct page
Before we leave unions and void pointers behind a look at
may be interesting. This structure uses both of these patterns, though they
are hidden somewhat due to historical baggage. This example is particularly
instructive because it is one case where struct embedding simply is not an option.
In Linux memory is divided into pages, and these pages are put to a
variety of different uses. Some are in the "page cache" used to store the
contents of files. Some are "anonymous pages" holding data used by
applications. Some are used as "slabs" and divided into pieces to answer
kmalloc() requests. Others are
simply part of a multi-page allocation or maybe are on a free list
waiting to be used.
Each of these different use cases could be seen as a subtype of the
general class of "page", and in most cases need some dedicated fields in
such as a struct address_space pointer and index
when used in the page cache, or struct kmem_cache and
freelist pointers when used as a slab.
Each page always has the same struct page describing it, so if the
effective type of the page is to change - as it must as the demands for
different uses of memory change over time - the type of the struct page
must change within the lifetime of that structure. While many type systems are
designed assuming that the type of an object is immutable, we find here that
the kernel has a very real need for type mutability. Both unions and void pointers
allow types to change and as noted, struct page uses both.
At the first level of subtyping there are only a small number of different
subtypes as listed above; these are all known to the core memory management
code, so a union would be ideal here. Unfortunately struct page has three
unions with fields for some subtypes spread over all three, thus hiding the
real structure somewhat.
When the primary subtype in use has the page being used in the page cache, the
particular address_space that it belongs to may want to extend the
data structure further. For this purpose there is a private field
that can be used. However it is not a void pointer but is an unsigned
Many places in the kernel assume an unsigned long and a void *
are the same size and this is one of them. Most users of this field actually
store a pointer here and have to cast it back and forth. The "buffer_head"
library provides macros
to set and get this field.
So while struct page is not the most elegant example, it is an
informative example of a case where unions and void pointers are the only
option for providing data inheritance.
The details of structure embedding
Where structure embedding can be used, and where the list of possible subtypes
is not known in advance, it seems to be increasingly the preferred choice.
To gain a full understanding of it we will again need to explore a little bit
further than inodes and contrast data inheritance with other uses of structure
There are essentially three uses for structure embedding - three reasons for
including a structure within another structure. Sometimes there is nothing
particularly interesting going on. Data items are collected together into
structures and structures within structures simply to highlight the closeness
of the relationships between the different items. In this case the address of
the embedded structure is rarely taken, and it is never mapped back to
the containing structure using container_of().
The second use is the data inheritance embedding that we have already
discussed. The third is like it but importantly different. This third use is
typified by struct list_head and other structs used as an
when creating abstract data types.
The use of an embedded anchor like struct list_head can be seen as a
style of inheritance as the structure containing it "is-a" member of a list
by virtue of inheriting from struct list_head. However it is not a
strict subtype as a single object can have several struct list_heads
embedded - struct inode has six (if we include the
similar hlist_node). So it is probably best to think of this sort of
embedding more like a "mixin" style of inheritance. The struct
list_head provides a service - that of being included in a list - that can
be mixed-in to other objects, an arbitrary number of times.
A key aspect of data inheritance structure embedding that differentiates it from
each of the other two is the existence of a reference counter in the inner-most
structure. This is an observation that is tied directly to the fact that the
Linux kernel uses reference counting as the primary means of lifetime
management and so would not be shared by systems that used, for example,
garbage collection to manage lifetimes.
In Linux, every object with an independent existence will have a
reference counter, sometimes a simple atomic_t or even
an int, though often a more explicit
When an object is created using several levels of inheritance the reference
counter could be buried quite deeply.
For example a
which has a
So usb_device (which might in turn be embedded in a structure for some
specific device) does have a reference counter, but it is contained several
levels down in the nest of structure embedding.
This contrasts quite nicely with a list_head and similar structures.
These have no reference counter, have no independent existence and simply
provide a service to other data structures.
Though it seems obvious when put this way, it is useful to remember that a
single object cannot have two reference counters - at least not two lifetime
reference counters (It is fine to have two counters like s_active
and s_count in struct super_block which count different
This means that multiple inheritance in the "data inheritance" style is not
possible. The only form of multiple inheritance that can work is the mixin
style used by list_head as mentioned above.
It also means that, when designing a data structure, it is important to think
about lifetime issues and whether this data structure should have its own
reference counter or whether it should depend on something else for its
lifetime management. That is, whether it is an object in its own right, or
simply a service provided to other objects. These issues are not really new
and apply equally to void pointer inheritance. However an important difference
with void pointers is that it is relatively easy to change your mind later and
switch an extension structure to be a fully independent object. Structure
embedding requires the discipline of thinking clearly about the problem up
front and making the right decision early - a discipline that is worth
The other key telltale for data inheritance structure embedding is the set of rules
for allocating and initializing new instances of a structure, as has already
been hinted at.
When union or void pointer inheritance is used the main structure is usually
allocated and initialized by common code (the mid-layer) and then a device
specific open() or create() function is called which can
optionally allocate and initialize any extension object.
By contrast when structure embedding is used the structure needs to be
allocated by the lowest level device driver which then initializes its own
fields and calls in to common code to initialize the common fields.
Continuing the struct inode example from above which has an
alloc_inode() method in the super_block to request allocation, we find
that initialization is provided for with
support functions. The first of these is used when the previous use of a piece
of memory is unknown, the second is sufficient by itself when we know that the
memory was previously used for some other inode.
We see this same pattern of an initializer function separate from allocation in
So apart from the obvious embedding of structures, the pattern of "data
inheritance through structure embedding" can be recognized by the presence of a
reference counter in the innermost structure, by the delegation of structure
allocation to the final user of the structure, and by the provision of
initializing functions which initialize a previously allocated structure.
In exploring the use of method dispatch (last week) and data inheritance (this
week) in the
Linux kernel we find that while some patterns seem to dominate they are
by no means universal. While almost all data inheritance could be
implemented using structure embedding, unions provide real value in a
few specific cases. Similarly while simple vtables are common, mixin
vtables are very important and the ability to delegate methods to a
related object can be valuable.
We also find that there are patterns in use with little to recommend
them. Using void pointers for inheritance may have an initial
simplicity, but causes longer term wastage, can cause confusion, and could
nearly always be replaced by embedded inheritance. Using NULL pointers to indicate
default behavior is similarly a poor choice - when the default is
important there are better ways to provide for it.
But maybe the most valuable lesson is that the Linux kernel is not only a
useful program to run, it is also a useful document to study. Such study can
find elegant practical solutions to real problems, and some less elegant
solutions. The willing student can pursue the former to help improve their mind,
and pursue the latter to help improve the kernel itself.
With that in mind, the following exercises might be of interest to some.
As inodes now use structure embedding for inheritance, void
pointers should not be necessary. Examine the consequences and
wisdom of removing "i_private" from "struct inode".
Rearrange the three unions in struct page to just one
union so that the enumeration of different subtypes is more explicit.
As was noted in the text, struct seq_file can be extended both
through "void pointer" and a limited form of "union" data inheritance.
Explain how seq_open_private() allows this structure to also be extended
through "embedded structure" data inheritance and give an example by
converting one usage in the kernel from "void pointer" to "embedded
Consider submitting a patch if this appears to be an improvement.
Contrast this implementation of embedded structure inheritance
with the mechanism used for inodes.
Though subtyping is widely used in the kernel, it is not uncommon
for a object to contain fields that not all users are interested
in. This can indicate that more fine grained subtyping is possible.
As very many completely different things can be represented by a
"file descriptor", it is likely that struct file could be a
candidate for further subtyping.
Identify the smallest set of fields that could serve as a generic
struct file and explore the implications of embedding that in
different structures to implement regular files, socket files, event
files, and other file types. Exploring more general use of the
method for inodes might help here.
Identify an "object-oriented" language which has an object model
that would meet all the needs of the Linux kernel as identified
in these two articles.
to post comments)