linuxkpi: Implement extensible arrays API using existing radix tree.

[• hselasky]

Summary

MFC after: 1 week
Sponsored by: Mellanox Technologies

[• hselasky]

Fix inverted xa_empty() return value.

[kib]

So what/where is the API specification ?
What are the synchronization guarantees ?
Are there any peculiarities in the implementation worth mention ?

[• hselasky]

Documentation is here:
https://www.kernel.org/doc/html/latest/core-api/xarray.html

Linux use a lot of atomics in there. We don't.

[• hselasky]

What are the synchronization guarantees?

All writing is done under a mutex.
All reading is done under RCU.

That's it.

[kib]

In D25101#552892, @hselasky wrote:

What are the synchronization guarantees?

All writing is done under a mutex.
All reading is done under RCU.

That's it.

I mean, what is the API user contract for locking.

Can you use FreeBSD primitives instead of Linux wrappers ? I mean atomics/mutexes/epochs.

sys/compat/linuxkpi/common/src/linux_radix.c

306 ↗

(On Diff #72564)

In other place you also free root node if it has zero children count.

331 ↗

(On Diff #72564)

Style: space before '('.

sys/compat/linuxkpi/common/src/linux_xarray.c

61

This increment lacks an assert that the operation did not overflow.

71

The check for underflow is needed, even if racy.

77

Style, no initialization in definition.

Why this recursion is possible (explanation should be a comment) ? Is it because user could lock xa and then call the API ?

That said, am I right that API distinguish between unlocked and locked entry points ? mtx_owned() generally should not be used, esp. when the code easily knows the state by contract.

109

What state is kept 'AS-IS' ?

I see, at least, that all readers are forced to use mutex while we sleep, is it needed ?

[• hselasky]

Document each function.

[• hselasky]

sys/compat/linuxkpi/common/src/linux_radix.c

306 ↗

(On Diff #72564)

I will have to look at this.

sys/compat/linuxkpi/common/src/linux_xarray.c

77

The API is not clear about locked and unlocked and I think we need to handle both, looking at the driver code we need to support.

The problem is that tree manipulations are allowed if flags do not allow sleeping. I can assert that.

109

I don't think so. Let me analyze.

[• hselasky]

Address comments from @kib

[• hselasky]

sys/compat/linuxkpi/common/src/linux_radix.c

331 ↗

(On Diff #72564)

Fixed.

[• hselasky]

Add some more comments explaining why memory cleanup is not needed when inserting radix tree nodes and a failure happens.

[• hselasky]

sys/compat/linuxkpi/common/src/linux_radix.c

306 ↗

(On Diff #72564)

I'm adding a comment here to explain the logic and why it is not leaking any memory this way.

[kib]

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

49

Can you please write it in more proper way, 0xffffffff ? If I guess the meaning of the abbreviation 32b correctly.

sys/compat/linuxkpi/common/src/linux_radix.c

229 ↗

(On Diff #75293)

I do not think exclamation mark is warranted in comments.

292 ↗

(On Diff #75293)

We usually provide full sentences even in single-line comments.
I.e. start it with capital letter, end with dot.

sys/compat/linuxkpi/common/src/linux_xarray.c

48

You ignored my notes from previous pass.

[• hselasky]

sys/compat/linuxkpi/common/src/linux_radix.c

292 ↗

(On Diff #75293)

Will update this comment. Trying to follow the style in this file.

sys/compat/linuxkpi/common/src/linux_xarray.c

48

Can you repeat? I've added the assert you requested.

[• hselasky]

Address comments from kib@

[• hselasky]

Remove extra "_" character.

[• hselasky]

Correctly place misplaced underscore.

[kib]

sys/compat/linuxkpi/common/src/linux_xarray.c

48

I do not want to retype all my comments.

One of the biggest one was the request to use FreeBSD primitives directly instead of layering LinuxKPI over LinuxKPI.

[• hselasky]

Use FreeBSD native API's when possible as suggested by @kib

Unfortunately we still have to use the LinuxKPI's RCU, because the EPOCH requires an epoch-tracker, which is not part of the xarray API.

Maybe this can be added to the task_struct structure ...

[• hselasky]

Wrap some long lines.

[• hselasky]

In D25101#576516, @hselasky wrote:

Use FreeBSD native API's when possible as suggested by @kib

Unfortunately we still have to use the LinuxKPI's RCU, because the EPOCH requires an epoch-tracker, which is not part of the xarray API.

Maybe this can be added to the task_struct structure ...

I suggest we use RCU, and then at some point convert RCU in LKPI to use EPOCH. Like said we need an epoch tracker in the LKPI thread structure, and it needs to support recursion.

[• hselasky]

Don't optimise the xarray implementation with RCU yet, because the radix tree needs to support it first!
Just use simple mutexes for now to protect read and write operations.

[• hselasky]

No need to include atomic.h .
Fix minor whitespace issue.

[kib]

sys/compat/linuxkpi/common/src/linux_xarray.c

91

If mask must be 2**n-1, this should be asserted. Otherwise, code accept any value for the mask.

Are there any required relations between *pindex and mask ?

113

I suspect this could be quite slow for large contig runs. Can you add an interface for radix tree to return next free index ?

[• hselasky]

sys/compat/linuxkpi/common/src/linux_xarray.c

91

Let me put an assert there to make it more clear.

[• hselasky]

sys/compat/linuxkpi/common/src/linux_xarray.c

113

I'm not sure how much we can save and if you want to insert multiple items, then use __xa_alloc_cyclic() , because it tracks the last inserted index, to avoid lookup from the start all the time.

[• hselasky]

Add more asserts.

[• hselasky]

sys/compat/linuxkpi/common/src/linux_xarray.c

113

@kib: Can you explain a bit more how the radix tree implementation could find the first free slot faster? I mean, if you want to find the first free slot you need to iterate all the leaf nodes anyway. And the lookup per node is logarithmic, so I don't think we are wasting much time there!

[kib]

sys/compat/linuxkpi/common/src/linux_xarray.c

113

I mean, that for large filled contig runs already existing in the radix tree, calling radix_tree_insert() for each allocated slot adds significant overhead for the implementation. Radix tree code loses its context on return.

You could try to use already known tree pointers to iterate further and return next free slot in case of radix_tree_insert() failure.

[• hselasky]

Fix build issue by including <sys/lock.h>

[• hselasky]

sys/compat/linuxkpi/common/src/linux_xarray.c

113

I see your point. However can we leave that for later?

There are two action items for improving the radix tree:

1. Optimise large contig runs
2. Add support for RCU to the radix tree, so that the xarray load can be lockless under RCU.

Action item #2 is a bigger showstopper than #1.

I'd rather see we can get going with xarrays, than having everything optimised to the teeth :-)

[kib]

Note that things like epochs/RCU provide scalability while giving some hit on single-threaded performance. And the issue of large runs, if the use creates them, also affects single-threaded performance. Anyway, it is not a blocker.

See one small note inline.

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

48

U suffix is not needed. The value is automatically promoted to unsigned if it cannot fit into int.

[• hselasky]

I'll remove the U suffix before committing. Thank you!