From: Bakul Shah <bakul@bitblocks.com>
To: Jon Steinhart <jon@fourwinds.com>
Cc: The Eunuchs Hysterical Society <tuhs@tuhs.org>
Subject: Re: [TUHS] Tech Sq elevator [ really type-checking ]
Date: Sun, 12 Jan 2020 16:35:51 -0800 [thread overview]
Message-ID: <AB452025-FCE9-4D41-992A-D3135683A6D6@bitblocks.com> (raw)
In-Reply-To: <202001122340.00CNeef0604557@darkstar.fourwinds.com>
On Jan 12, 2020, at 3:40 PM, Jon Steinhart <jon@fourwinds.com> wrote:
>
> Kevin Bowling writes:
>>
>> I am regularly surprised by how surprising type systems are to
>> computing professionals.
>
> I am currently astonished at this. Unfortunately, I need to make a hopefully
> minor change to the linux kernel to support something that I want to do in my
> current project. But, this is my first time looking at the internals which is
> way different that my recollection of UNIX kernels. It's being enough of an
> adventure that I'm writing up a travelogue of my journey through the code.
> While I swore that I was done writing books this is sure looking like another
> one :-)
>
> So I came across this piece of what I consider to be bad programming that's
> all over the place...
>
> One of my programming style rules is to program in the language in which you're
> programming. The canonical example of not doing this is the Bourne shell which
> was originally written using macros to redefine C to look like Algol68.
>
> Linux contains several sets of list_for_each_entry() macros that are essentially
> obfuscated for loops that generate inefficient code. To make things worse, the
> way that they're implemented is by embedding list_head structures into other
> structures.
>
> In the diagram below, the labels above boxes are structure names. Names inside
> of boxes are structure member names. super_blocks, s_list, s_mounts, and
> mnt_instance are all list_head structures. (Trick question, how many lines are
> in this diagram :-) )
>
> +-----------------------------------------+
> | super_block |
> | +--------------+ +----------+ |
> +->| super_blocks |<->| s_list |<- ... -+
> +--------------+ +----------+
> | | mount mount
> | ... | +--------------+ +--------------+
> | | | ... | | ... |
> +----------+ +--------------+ +--------------+
> +->| s_mounts |<->| mnt_instance |<->| mnt_instance |<- ... -+
> | +----------+ +--------------+ +--------------+ |
> | | ... | | ... | |
> | +--------------+ +--------------+ |
> +------------------------------------------------------------+
>
> The bizarre thing to me is that the list_head structures point to other list_head
> structures that are embedded in other structures. When one needs to access a
> non list-head member of the structure one has to pass both the structure type and
> the list_head member name to a macro that figures out how to subtract the offset
> of the list_head member of the structure from the address of that list_head to
> get the address of the structure, and then casts that as the structure type so
> that members can be accessed.
There is similar code in FreeBSD kernel. Embedding head and next ptrs reduces
memory allocation and improves cache locality somewhat. Since C doesn't have
generics, they try to gain the same functionality with macros. See
https://github.com/freebsd/freebsd/blob/master/sys/sys/queue.h
Not that this is the same as what Linux does (which I haven't dug into) but
I suspect they may have had similar motivation.
next prev parent reply other threads:[~2020-01-13 0:36 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-01-12 22:25 [TUHS] Tech Sq elevator (Was: screen editors) Doug McIlroy
2020-01-12 22:40 ` Kevin Bowling
2020-01-12 23:40 ` [TUHS] Tech Sq elevator [ really type-checking ] Jon Steinhart
2020-01-12 23:50 ` Larry McVoy
2020-01-13 0:01 ` Jon Steinhart
2020-01-13 0:22 ` Larry McVoy
2020-01-13 0:31 ` Jon Steinhart
2020-01-13 0:44 ` Theodore Y. Ts'o
2020-01-13 0:35 ` Bakul Shah [this message]
2020-01-13 0:44 ` Jon Steinhart
2020-01-13 0:49 ` Warren Toomey
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=AB452025-FCE9-4D41-992A-D3135683A6D6@bitblocks.com \
--to=bakul@bitblocks.com \
--cc=jon@fourwinds.com \
--cc=tuhs@tuhs.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).