libkern: add ilog2 helpers

[dougm]

Summary

The fls* bit-finding functions have to include zero-checks. In a case where the caller knows that the argument is not zero, these new functions provide a way to avoid those zero-checks.

This change uses _Generic to define an ilog2 macro that picks the right ilog2 function based on argument type, and to identify constant arguments so that they can be computed at compile time.

This is an alternative to D45170, which does not use _Generic.

[bz]

sys/compat/linuxkpi/common/include/linux/log2.h

54

What is the point of keeping this given libkern.h is included?

sys/sys/libkern.h

190

How does this work with the #define of the same name below?

[dougm]

sys/compat/linuxkpi/common/include/linux/log2.h

54

None. I'll remove it.

sys/sys/libkern.h

190

The preprocessor can replace 'ilog2' with 'ilog2', or 'ilog2l' or whatever.

[dougm]

Drop the ilog2 definition from log2.h.

[dougm]

Rename (function) ilog2 so that it differs from (macro) ilog2. Rename the other functions too, and make the parameter name the same across all ilog2 functions/macros.

[markj]

sys/sys/libkern.h

220

IMO a better formatting here would be

#define ilog2_var(n)          \
        _Generic((n),         \
            default: ...,     \
            long: ...,        \
            ...

225

Indentation here and on following lines should be by four spaces.

Does this microoptimization help in practice? I'd naively expect the compiler's constant folding to be smart enough to make this redundant.

[dougm]

Address whitespace issues.

sys/sys/libkern.h

225

If ilog2 doesn't offer this special path for constants, then lines that use ilog2 to initialize static variables won't compile:

And there is one:
sys/dev/mthca/mthca_main.c:static int log_mtts_per_seg = ilog2(MTHCA_MTT_SEG_SIZE / 8);

[dougm]

sys/sys/libkern.h

225

I could edit sys/dev/mthca* so that it didn't need a compile-time evaluation of ilog2, and hope that no one ever wants that feature again, and drop the 64 or so cases from the ilog2 macro. Tell me how you want me to proceed.

[bz]

sys/sys/libkern.h

225

LinuxKPI (and drivers) rely on this I do believe. If you remove it we need to deal with LinuxKPI differently and likely have a duplicate and extra #ifdefs around the libkern version.
Maybe add a comment as-to why it is there pointing at LinuxKPI and just leave it?

[markj]

Seems fine to me with a comment explaining the compile-time tests.

sys/sys/libkern.h

225

Yes, I think a comment explaining why we do this would be useful.

As an aside, mthca is obsolete at this point and could safely be removed. It was already long in the tooth when I last worked with it ~8 years ago.

[alc]

sys/dev/mana/gdma_util.h

176

Are you convinced that the code that uses this broken version of ilog2 isn't dependent on the brokenness?

[dougm]

sys/dev/mana/gdma_util.h

176

I can find ilog2 used the same way in our gdma_main.c as in gdma_main.c in linux. I can find an ilog2 definition in linux that does the sensible thing. I cannot prove that there's no broken ilog2 implementation hidden in linux that broken in the same way as this one, and used by their gdma_main.c code. I can say that the gdma_main.c in linux is not in the same directory as a header file like (our) gdma_util.h that defines a bad ilog2.

At the same time, I don't know this code. The committer of this code has not responded to my inquiry. I've just reached out to those who reviewed this code before it was committed, in hope that one of them might provide a more confident assessment.

[lwhsu]

sys/dev/mana/gdma_util.h

176

@whu @schakrabarti_microsoft.com can you help check if mana(4) can use global ilog2?

[schakrabarti_microsoft.com]

sys/dev/mana/gdma_util.h

176

I will check and confirm.

[dougm]

sys/dev/mana/gdma_util.h

176

@schakrabarti_microsoft.com can you let me know when confirmation will be available?

[schakrabarti_microsoft.com]

sys/dev/mana/gdma_util.h

176

@dougm I will share it by 3rd June.

[schakrabarti_microsoft.com]

sys/dev/mana/gdma_util.h

176

We have checked, it is working for MANA driver.

[bz]

sys/sys/libkern.h

6

Do any of the previos Copyright holders need to be listed for the move of the expanded list from LinuxKPI to here?

[dougm]

sys/sys/libkern.h

6

I cannot answer legal questions.

I can say that essentially the same idea appears in code at https://docs.zephyrproject.org/apidoc/latest/ilog2_8h_source.html and Intel wasn't afraid to slap their copyright on it, without mentioning anyone else.

I have changed the indentation from what was in the linuxkpi file. I can make more changes if necessary, to make it look less like what was there before. But it's hard for me to believe that something so basic is copyrightable. But, again, not a lawyer.

[dougm]

sys/sys/libkern.h

6

When these lines were first added to the freebsd code repository, it was in 2013, in sys/ofed/include/linux/log2.h, with change c9f432b. That change did not add any copyright lines. Before the change, these three lines were already in the file:

• Copyright (c) 2010 Isilon Systems, Inc.
• Copyright (c) 2010 iX Systems, Inc.
• Copyright (c) 2010 Panasas, Inc.

I can't say what that means in terms of which copyrights, if any, should be made to apply to libkern.h now.

[bz]

sys/sys/libkern.h

6

So it came from Mellanox (according to the commit message from alfred) of c9f432b.

I do not know either -- also not where they had it from at that time.
Generally I'd ask imp@ in these cases.
I'll add him to subscribers in case he has any idea.