[COFF] [TUHS] Tech Sq elevator [ really type-checking ]

[Bakul Shah]

On Sun, 12 Jan 2020 20:23:11 -0500 Dan Cross <crossd at gmail.com> wrote:
>
> -TUHS, +COFF, in line with Warren's wishes.
>
> On Sun, Jan 12, 2020 at 7:36 PM Bakul Shah <bakul at bitblocks.com> wrote:
>
> > 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.
> >
>
> I was actually going to say, "blame Berkeley." As I understand it, this
> code originated in BSD, and the Linux implementation is at least inspired
> by the BSD code. There was code for singly and doubly linked lists, queues,
> FIFOs, etc.
>
> I can actually understand the motivation: lists, etc, are all over the
> place in a number of kernels. The code to remove an element from a list is
> trivial, but also tedious and repetitive: if it can be wrapped up into a
> macro, why not do so? It's one less thing to mess up.

In late '90s when I first came across code in the FreebSD
kernel, as a Scheme-phile I instinctively disliked it.  But upon
reflection and considering doing it the lisp way -- car,cdr,
where car points to a data stucture, I realized this was better,

The list way wouldn't have helped and made things worse. Now
you may have to either cast the car (whose type would've been
void*, which loses type safety) or define data structure
specific types and you are back to needing lots of very
similar functions. In addition you may now have to lock more
data structures to manage these lists. Then consider what
happens when an object is on multiple lists. Now you need O(n)
operations to remove it from all the lists. And so on.

> I agree it's gone off the rails, however.

Well, this is "historic unix code" :-)