The Unix Heritage Society mailing list
 help / color / mirror / Atom feed
* Re: [TUHS] Tech Sq elevator (Was: screen editors)
@ 2020-01-12 22:25 Doug McIlroy
  2020-01-12 22:40 ` Kevin Bowling
  0 siblings, 1 reply; 11+ messages in thread
From: Doug McIlroy @ 2020-01-12 22:25 UTC (permalink / raw)
  To: tuhs

>> After scrolling through the command list, I wondered how
>> long it was and asked to have it counted. Easy, I thought,
>> just pass it to a wc-like program. But "just pass it" and
>> "wc-like" were not givens as they are in Unix culture.
>> It took several minutes for the gurus to do it--without
>> leaving emacs, if I remember right.

> This is kind of illustrative of the '60s acid trip that
> perpetuates in programming "Everything's a string maaaaan".
> The output is seen as truth because the representation is
> for some reason too hard to get at or too hard to cascade
> through the system.

How did strings get into the discussion? Warner showed how
emacs could be expected to do the job--and more efficiently
than the Unix way, at that: (list-length (command-list-fn)).
The surprise was that this wasn't readily available.

Back then, in fact, you couldn't ask sh for its command
list. help|wc couldn't be done because help wasn't there.

Emacs had a different problem. It had a universal internal
interface--lists rather than strings--yet did not have
a way to cause this particular list to "cascade through
the system". (print(command-list-fn)) was provided, while
(command-list-fn) was hidden.

Doug

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator (Was: screen editors)
  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
  0 siblings, 1 reply; 11+ messages in thread
From: Kevin Bowling @ 2020-01-12 22:40 UTC (permalink / raw)
  To: Doug McIlroy; +Cc: The Eunuchs Hysterical Society

On Sun, Jan 12, 2020 at 3:26 PM Doug McIlroy <doug@cs.dartmouth.edu> wrote:
>
> >> After scrolling through the command list, I wondered how
> >> long it was and asked to have it counted. Easy, I thought,
> >> just pass it to a wc-like program. But "just pass it" and
> >> "wc-like" were not givens as they are in Unix culture.
> >> It took several minutes for the gurus to do it--without
> >> leaving emacs, if I remember right.
>
> > This is kind of illustrative of the '60s acid trip that
> > perpetuates in programming "Everything's a string maaaaan".
> > The output is seen as truth because the representation is
> > for some reason too hard to get at or too hard to cascade
> > through the system.
>
> How did strings get into the discussion? Warner showed how
> emacs could be expected to do the job--and more efficiently
> than the Unix way, at that: (list-length (command-list-fn)).
> The surprise was that this wasn't readily available.

Bakul provided an explanation for the pipeline, the funny cue to me
that I interpreted from Warner's message is just that emacs had the
ability to do it in a coherent way but did not and ISTM that the way
you make a mess of that is by losing the intent of the representation.
I am regularly surprised by how surprising type systems are to
computing professionals.  The language and environment may help or
dissuade you from doing that, wasn't really relevant to my original
point.

Larry tells me the message is somehow inflammatory, it wasn't intended
that way I was just trying to make light of the situation and provide
people a launch pad to think for themselves about some fundamentals
because it's worthwhile to do so occasionally.

> Back then, in fact, you couldn't ask sh for its command
> list. help|wc couldn't be done because help wasn't there.
>
> Emacs had a different problem. It had a universal internal
> interface--lists rather than strings--yet did not have
> a way to cause this particular list to "cascade through
> the system". (print(command-list-fn)) was provided, while
> (command-list-fn) was hidden.

The only response I can come up with to these two points eventually
boils down to a philosophical riddle:  does the work matter or does
how the work is done matter?  Both, the situation dictates.  I execute
innumerable shell pipelines per day and perhaps craft a dozen
ephemerals ones.

Regards,
Kevin

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator [ really type-checking ]
  2020-01-12 22:40 ` Kevin Bowling
@ 2020-01-12 23:40   ` Jon Steinhart
  2020-01-12 23:50     ` Larry McVoy
  2020-01-13  0:35     ` Bakul Shah
  0 siblings, 2 replies; 11+ messages in thread
From: Jon Steinhart @ 2020-01-12 23:40 UTC (permalink / raw)
  To: The Eunuchs Hysterical Society

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.

The reason why I think that this is bad is because one can pass anything into that
macro; you just have to know what type of structures make up the list which is not
at all obvious as:

        struct  foo     {
                int                     bar;
                struct  list_head       name;
        };

gives no information about the list, unlike this:

        struct  foo     {
                int                     bar;
                struct  foo             *next;
        };

It completely bypasses the compiler type-checking.  In my opinion, very error prone.
Not to mention completely opaque to someone reading the code.  Without even the
consideration of decent comments, for example:

        struct list_head        s_list;         /* Keep this first */
        struct list_head        s_mounts;       /* list of mounts; _not_ for fs use */
        struct list_head        s_inodes_wb;    /* writeback inodes */

say nothing about what type of structures are in the lists.

In addition to generating less-efficient code than a for loop would and avoiding
type-checking, this approach seems to be used without much thought in the kernel
where memory is at a premium.  Many of these are used to implement circular
double-linked lists where neither the circularity nor the doubly-linking are
needed or used.

As an aside, one has to descend through 8 levels of macros calling macros and
six extra header files just to track down what this stuff does and how it works.

So I just don't get this at all.  I have no idea why someone would code this
way in C unless they just wanted to foist a construct from another language
that they preferred.  Somehow I expected better in the kernel.

Like usual, I could be completely off-base here and if I am, please correct me.

Jon

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator [ really type-checking ]
  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:35     ` Bakul Shah
  1 sibling, 1 reply; 11+ messages in thread
From: Larry McVoy @ 2020-01-12 23:50 UTC (permalink / raw)
  To: Jon Steinhart; +Cc: The Eunuchs Hysterical Society

On Sun, Jan 12, 2020 at 03:40:40PM -0800, Jon Steinhart wrote:
> Linux contains several sets of list_for_each_entry() macros that are essentially
> obfuscated for loops that generate inefficient code.  

Very common idiom in any real system.  BitKeeper has them as well, they are
used everywhere.  They are too useful to not use.  The BitKeeper ones give
you most of Perl's list capabilities.

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator [ really type-checking ]
  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:44         ` Theodore Y. Ts'o
  0 siblings, 2 replies; 11+ messages in thread
From: Jon Steinhart @ 2020-01-13  0:01 UTC (permalink / raw)
  To: The Eunuchs Hysterical Society

Larry McVoy writes:
> On Sun, Jan 12, 2020 at 03:40:40PM -0800, Jon Steinhart wrote:
> > Linux contains several sets of list_for_each_entry() macros that are essentially
> > obfuscated for loops that generate inefficient code.  
>
> Very common idiom in any real system.  BitKeeper has them as well, they are
> used everywhere.  They are too useful to not use.  The BitKeeper ones give
> you most of Perl's list capabilities.

I don't see it.  In the cases that I've seen so far in linux the only uses are
inserting, deleting, and traversing lists.  My opinion that anyone who can't
write
	for (p = list; p != NULL; p = p->next)

shouldn't be programming, much less in the kernel.  To me, type-checking and
code clarity are vastly more important.  If I want to program in Perl, I do
so.  When I program in C that's what I do.

I do want to be clear that I'm coming at this from a code maintenance angle.
Code that I write for my personal use looks way different than what I write
professionally.  I'm willing to put in more work up front to make sure that
other people can easily understand my code because I don't want to be stuck
maintaining stuff.  And I recognize that unless one is coding a web page with
an expected lifespan of 30 seconds the cost of maintenance dwarfs the cost of
development.

Jon

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator [ really type-checking ]
  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
  1 sibling, 1 reply; 11+ messages in thread
From: Larry McVoy @ 2020-01-13  0:22 UTC (permalink / raw)
  To: Jon Steinhart; +Cc: The Eunuchs Hysterical Society

On Sun, Jan 12, 2020 at 04:01:02PM -0800, Jon Steinhart wrote:
> Larry McVoy writes:
> > On Sun, Jan 12, 2020 at 03:40:40PM -0800, Jon Steinhart wrote:
> > > Linux contains several sets of list_for_each_entry() macros that are essentially
> > > obfuscated for loops that generate inefficient code.  
> >
> > Very common idiom in any real system.  BitKeeper has them as well, they are
> > used everywhere.  They are too useful to not use.  The BitKeeper ones give
> > you most of Perl's list capabilities.
> 
> I don't see it.  In the cases that I've seen so far in linux the only uses are
> inserting, deleting, and traversing lists.  My opinion that anyone who can't
> write
> 	for (p = list; p != NULL; p = p->next)
> 
> shouldn't be programming, much less in the kernel.  To me, type-checking and
> code clarity are vastly more important.  If I want to program in Perl, I do
> so.  When I program in C that's what I do.
> 
> I do want to be clear that I'm coming at this from a code maintenance angle.

I'd argue that the code we wrote for BitKeeper would hold up as some
of the most professionally written code ever.  Every commit was peer
reviewed by at least 2 other people, code that add/changed/deleted user
interfaces had to have docs and tests.  The philosophy is very much in
line with code maintenance, I vetoed stuff that was clever, my mantra was
"write once, read many so optimize for read".

Some dude on twitter found our code when we open sourced it and tweeted
something like "Wow, I've just spent the afternoon reading some of the
best written C code I've ever seen.  I didn't know C could be that nice".
So it's not just my opinion, I don't know that dude.

The list code that we have is super pleasant to use and has been
in production use for over 2 decades.  And we maintained it easily,
our 24x7 *average* responsive time on a bug report was 24 minutes.
The only reason it was that high was because we had to sleep (we were
spread out from East to West coast).  During working hours, response time
was almost always under 10 minutes, usually 2-3 minutes.  By "response",
I don't mean some automated nonsense that says "We value your input,
this is to let you know your report has been entered into our system".
I mean an engineer looked at the problem, figured out what was causing the
problem by looking at our source, about 90% of the time we knew what the
fix was, and we sent an update to the bug report with that information.

The list structure was auto resizing, it knew both how much was allocated
and how much was used in the first word of the list (we resized only in
powers of 2 so we could store size in log2 bits, used the rest of the
bits for the length), you could have a list in as short as two words 
and it scaled really well to millions of entries.  

It was, and is, super useful.  Wayne is back at Intel and he's teasing
it out of our libc to use there.

So you may not like it but that's you.  It has worked well in an extremely
professional environment.  Well coding professional, personalities might
have been a bit wonky :)

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator [ really type-checking ]
  2020-01-13  0:22         ` Larry McVoy
@ 2020-01-13  0:31           ` Jon Steinhart
  0 siblings, 0 replies; 11+ messages in thread
From: Jon Steinhart @ 2020-01-13  0:31 UTC (permalink / raw)
  To: The Eunuchs Hysterical Society

Larry McVoy writes:
> On Sun, Jan 12, 2020 at 04:01:02PM -0800, Jon Steinhart wrote:
> > Larry McVoy writes:
> > > On Sun, Jan 12, 2020 at 03:40:40PM -0800, Jon Steinhart wrote:
> > > > Linux contains several sets of list_for_each_entry() macros that are essentially
> > > > obfuscated for loops that generate inefficient code.  
> > >
> > > Very common idiom in any real system.  BitKeeper has them as well, they are
> > > used everywhere.  They are too useful to not use.  The BitKeeper ones give
> > > you most of Perl's list capabilities.
> > 
> > I don't see it.  In the cases that I've seen so far in linux the only uses are
> > inserting, deleting, and traversing lists.  My opinion that anyone who can't
> > write
> > 	for (p = list; p != NULL; p = p->next)
> > 
> > shouldn't be programming, much less in the kernel.  To me, type-checking and
> > code clarity are vastly more important.  If I want to program in Perl, I do
> > so.  When I program in C that's what I do.
> > 
> > I do want to be clear that I'm coming at this from a code maintenance angle.
>
> I'd argue that the code we wrote for BitKeeper would hold up as some
> of the most professionally written code ever.  Every commit was peer
> reviewed by at least 2 other people, code that add/changed/deleted user
> interfaces had to have docs and tests.  The philosophy is very much in
> line with code maintenance, I vetoed stuff that was clever, my mantra was
> "write once, read many so optimize for read".
>
> Some dude on twitter found our code when we open sourced it and tweeted
> something like "Wow, I've just spent the afternoon reading some of the
> best written C code I've ever seen.  I didn't know C could be that nice".
> So it's not just my opinion, I don't know that dude.
>
> The list code that we have is super pleasant to use and has been
> in production use for over 2 decades.  And we maintained it easily,
> our 24x7 *average* responsive time on a bug report was 24 minutes.
> The only reason it was that high was because we had to sleep (we were
> spread out from East to West coast).  During working hours, response time
> was almost always under 10 minutes, usually 2-3 minutes.  By "response",
> I don't mean some automated nonsense that says "We value your input,
> this is to let you know your report has been entered into our system".
> I mean an engineer looked at the problem, figured out what was causing the
> problem by looking at our source, about 90% of the time we knew what the
> fix was, and we sent an update to the bug report with that information.
>
> The list structure was auto resizing, it knew both how much was allocated
> and how much was used in the first word of the list (we resized only in
> powers of 2 so we could store size in log2 bits, used the rest of the
> bits for the length), you could have a list in as short as two words 
> and it scaled really well to millions of entries.  
>
> It was, and is, super useful.  Wayne is back at Intel and he's teasing
> it out of our libc to use there.
>
> So you may not like it but that's you.  It has worked well in an extremely
> professional environment.  Well coding professional, personalities might
> have been a bit wonky :)

I was commenting on what I found in the linux kernel.  Your code and list
interface may be better.

Jon

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator [ really type-checking ]
  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:35     ` Bakul Shah
  2020-01-13  0:44       ` Jon Steinhart
  1 sibling, 1 reply; 11+ messages in thread
From: Bakul Shah @ 2020-01-13  0:35 UTC (permalink / raw)
  To: Jon Steinhart; +Cc: The Eunuchs Hysterical Society

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.


^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator [ really type-checking ]
  2020-01-13  0:01       ` Jon Steinhart
  2020-01-13  0:22         ` Larry McVoy
@ 2020-01-13  0:44         ` Theodore Y. Ts'o
  1 sibling, 0 replies; 11+ messages in thread
From: Theodore Y. Ts'o @ 2020-01-13  0:44 UTC (permalink / raw)
  To: Jon Steinhart; +Cc: The Eunuchs Hysterical Society

(Not sure this is appropriate for TUHS)

On Sun, Jan 12, 2020 at 04:01:02PM -0800, Jon Steinhart wrote:
> Larry McVoy writes:
> > On Sun, Jan 12, 2020 at 03:40:40PM -0800, Jon Steinhart wrote:
> > > Linux contains several sets of list_for_each_entry() macros that are essentially
> > > obfuscated for loops that generate inefficient code.  
> >
> > Very common idiom in any real system.  BitKeeper has them as well, they are
> > used everywhere.  They are too useful to not use.  The BitKeeper ones give
> > you most of Perl's list capabilities.
> 
> I don't see it.  In the cases that I've seen so far in linux the only uses are
> inserting, deleting, and traversing lists.  My opinion that anyone who can't
> write
> 	for (p = list; p != NULL; p = p->next)

There are many places where there is a desire to

(a) add an object to the end of the list
(b) remove an object from a linked list where the object was not found
    via iterating over the linked list

One or the other was true for all of the linked lists that you
complained about earlier up-thread.  For example, a struct super has a
doubly linked list of struct mount where we might want to drop a
struct mount without needing iterate over the whole linked list.

So "just use an open-coded singly linked list" is really not that
simple.  In addition, it should be noted that there are
read-copy-update variants of these functions (e.g.,
list_for_each_entry_rcu, list_del_rcu) that can be used with the same
struct list_head structure.

Sure, it would be simpler to just take a global kernel lock, and
iterating over the entire singly linked list to remove an object from
it, or adding an object to the end of a list.  That would be
*simpler*.  But that would be much more, not less, inefficient.

Cheers,

						- Ted

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator [ really type-checking ]
  2020-01-13  0:35     ` Bakul Shah
@ 2020-01-13  0:44       ` Jon Steinhart
  2020-01-13  0:49         ` Warren Toomey
  0 siblings, 1 reply; 11+ messages in thread
From: Jon Steinhart @ 2020-01-13  0:44 UTC (permalink / raw)
  To: The Eunuchs Hysterical Society

Bakul Shah writes:
> 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.

Not sure that I understand.

A list_head structure takes exactly the same amount of space as a pair of pointers,
so the memory allocation should be identical.

I also don't see the cache locality.  Both the embedded list_head and the start
of the structure are accessed in either case; once the programmer has played
guess-the-type the list macro returns a pointer to the start of the structure.

So again, I'm just commenting on what I'm seeing in linux, and while it is
possible that I may be misunderstanding something so far I don't think so.

Jon

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: [TUHS] Tech Sq elevator [ really type-checking ]
  2020-01-13  0:44       ` Jon Steinhart
@ 2020-01-13  0:49         ` Warren Toomey
  0 siblings, 0 replies; 11+ messages in thread
From: Warren Toomey @ 2020-01-13  0:49 UTC (permalink / raw)
  Cc: The Eunuchs Hysterical Society, coff

All, can we move this not-really-Unix discussion to COFF?
Thanks, Warren

P.S A bit more self-regulation too, please. You shouldn't need me to point
out when the topic has drifted so far :-)

^ permalink raw reply	[flat|nested] 11+ messages in thread

end of thread, other threads:[~2020-01-13  0:51 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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
2020-01-13  0:44       ` Jon Steinhart
2020-01-13  0:49         ` Warren Toomey

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).