From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=HEADER_FROM_DIFFERENT_DOMAINS, MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.2 Received: from minnie.tuhs.org (minnie.tuhs.org [45.79.103.53]) by inbox.vuxu.org (OpenSMTPD) with ESMTP id f9cd9cdb for ; Mon, 13 Jan 2020 00:36:40 +0000 (UTC) Received: by minnie.tuhs.org (Postfix, from userid 112) id 6CCE89BD21; Mon, 13 Jan 2020 10:36:39 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 836BB9BD0F; Mon, 13 Jan 2020 10:36:10 +1000 (AEST) Received: by minnie.tuhs.org (Postfix, from userid 112) id 485F79BD0F; Mon, 13 Jan 2020 10:36:07 +1000 (AEST) Received: from mail.bitblocks.com (ns1.bitblocks.com [173.228.5.8]) by minnie.tuhs.org (Postfix) with ESMTP id C20129BCA8 for ; Mon, 13 Jan 2020 10:36:06 +1000 (AEST) Received: from mob.bitblocks.com (mob.bitblocks.com [192.168.125.11]) by mail.bitblocks.com (Postfix) with ESMTP id B86A9156E42D; Sun, 12 Jan 2020 16:35:51 -0800 (PST) Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\)) From: Bakul Shah In-Reply-To: <202001122340.00CNeef0604557@darkstar.fourwinds.com> Date: Sun, 12 Jan 2020 16:35:51 -0800 Content-Transfer-Encoding: quoted-printable Message-Id: References: <202001122225.00CMPc9S085970@tahoe.cs.Dartmouth.EDU> <202001122340.00CNeef0604557@darkstar.fourwinds.com> To: Jon Steinhart X-Mailer: Apple Mail (2.3445.104.11) Subject: Re: [TUHS] Tech Sq elevator [ really type-checking ] X-BeenThere: tuhs@minnie.tuhs.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: The Unix Heritage Society mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: The Eunuchs Hysterical Society Errors-To: tuhs-bounces@minnie.tuhs.org Sender: "TUHS" On Jan 12, 2020, at 3:40 PM, Jon Steinhart wrote: >=20 > Kevin Bowling writes: >>=20 >> I am regularly surprised by how surprising type systems are to >> computing professionals. >=20 > 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 :-) >=20 > So I came across this piece of what I consider to be bad programming = that's > all over the place... >=20 > 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. >=20 > 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. >=20 > 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 :-) ) >=20 > +-----------------------------------------+ > | super_block | > | +--------------+ +----------+ | > +->| super_blocks |<->| s_list |<- ... -+ > +--------------+ +----------+ > | | mount mount > | ... | +--------------+ = +--------------+ > | | | ... | | ... = | > +----------+ +--------------+ = +--------------+ > +->| s_mounts |<->| mnt_instance |<->| mnt_instance = |<- ... -+ > | +----------+ +--------------+ = +--------------+ | > | | ... | | ... = | | > | +--------------+ = +--------------+ | > = +------------------------------------------------------------+ >=20 > 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=20 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.