What happens if there's already a value stored at node? What should happen?

It seems you can set *out to parent here and drop all the other assignments to *out. Can't the caller invoke _get_parent to get this value?

Is a special case necessary here? This function doesn't modify the tree, except in this case. Isn't this another special case for ALLOC_INSERT?

How do you know that there isn't already something stored here? What should you do in that case?

I think that your array of elements are constrained to have consecutive indices, but I don't see comments about that. And since you're reading index values from the data, it seems that if those indices aren't consecutive, this is going to wreck the tree. So perhaps this function should take an index argument for the first array element and do the assignment of consecutive index values to the array elements so that the tree cannot be wrecked.

The test consumer of this interface performs an explicit lookup prior to insertion so this slipped by me.

My first reaction would be to check before insertions and panic if there's already a value stored.
This would slow things down a bit, but it's consistent with how we've been doing things so far.
We could also perform an explicit lookup before inserting anything and trim the insertion range accordingly

I'm not sure which approach would make more sense though.
The same goes for the other two similar comments out below.

Right, the case is redundant, I've removed it and handled the single-item insertion case in pctrie_batch_insert.

Thanks for pointing this out, this indeed is the case.
I've modified the function according to your suggestion, it'll now take a starting index and populate the elements instead of relying on them being properly prefilled.

If parent == NULL, and you've already assigned *out = parent, you don't need to assign *out = NULL.

Don't need the 'else'. Don't need so many braces.

You don't need to assert node != NULL. The system already checks that assertion for you.

"- n" doesn't contribute much here.

It seems that nitems and to_insert don't overlap. Why not replace to_insert with nitems?

It seems that you are error-handling by assertion. If I try to enter elements 100-199 in the pctrie and element 143 is there already, this assertion will fail. But if I've built the kernel GENERIC-NODEBUG, this assertion is disabled and I will lose element 143. So, is the user required to check that the least element >= 100 is > 199 to make sure they're all missing before entering 100-199 all at once?

I've wondered if this thing you're doing is for mass-insertion at an arbitrary point in the life of the pctrie, or is instead for initialization of the pctrie only. If this were an initializer only, these pesky questions I'm asking would just disappear.

I wonder if this needs to be locked.

I haven't figured out all your code yet, but I'm wondering if you're modifying the original pctrie a few pieces at a time, and using PCTRIE_LOCKED ever 16 writes or so, when you could do something else. Suppose you designed this to build an entire little pctrie of values 100-199, or whatever, and then attach it all at once to the big pctrie. The building of the little pctrie could be completely unsynchronized. Only when you inserted the little pctrie into the big pctrie would the last store have to be synchronized. So I expect that would improve performance.

If this is just an initializer, most of above still applies; you don't need PCTRIE_LOCKED until the pctrie is ready.

Ah, right, that was a bit silly - thanks for catching this!

So, is the user required to check that the least element >= 100 is > 199 to make sure they're all missing before entering 100-199 all at once?

I think its best if we performed the checks when inserting, the popmap is now always checked during batched insertion.

I've wondered if this thing you're doing is for mass-insertion at an arbitrary point in the life of the pctrie, or is instead for initialization of the pctrie only. If this were an initializer only, these pesky questions I'm asking would just disappear.

The former is true, this is meant to be used at any point of the pctrie's lifecycle.

I wonder if this needs to be locked.

I haven't figured out all your code yet, but I'm wondering if you're modifying the original pctrie a few pieces at a time, and using PCTRIE_LOCKED ever 16 writes or so, when you could do something else. Suppose you designed this to build an entire little pctrie of values 100-199, or whatever, and then attach it all at once to the big pctrie. The building of the little pctrie could be completely unsynchronized. Only when you inserted the little pctrie into the big pctrie would the last store have to be synchronized. So I expect that would improve performance.

I had considered this approach initially but ultimately settled for another approach since this idea seemed even more complex and trickier to get right. Would it make sense to do a similar thing with the current patch - i.e. synchronize only at the very last write?

A function so small, used only once, is best avoided.

nitems is not used in this function.

Is an enum type and this function really necessary, since it's only called once? Can't this just be logic in pctrie_batch_insert?

Reorder the tests so that you don't need so many nesting levels.

How about a for loop?

Instead of modifying slot with every iteration, how about slot + n here?

*val always has the same value assigned to it. Might as well do it one place instead of 3.

Some expressions below use 'index' and some use 'start + total'. Pick one.

I don't see the point of this assignment.

It could, but I deliberately split the lookup part out to keep pctrie_batch_insert smaller and easier to read.

I'm going to keep picking at this until this function and this enum goes away, but for now, can you write it to have only 2 if statements and 3 return statements?

	val = pctrie_iter_lookup_ge(it, start);
	if (val != NULL && *val <= start + nitems - 1)
		panic("%s: key '%lu' already present", __func__, *val);

Now you don't need any other panic tests in the code.

I observe that the rest of the code in this file does not wrap single lines after if, like this one, in braces. Don't adopt a unique style for this function.

Correct me if I'm wrong. This happens only when inserting the first item. If, before the loop begins, you check to see if (start + 1) % PCTRIE_COUNT == 0 and, if so, insert the first item with iter_insert and increase total to 1, then this case doesn't have to be checked here in the loop.

	} while (total < nitems - 1);

Now, there are three places where you can stop checking for nitems - total == 1 in the code, and instead, here you can just test for total != nitems and do an iter_insert in that case.

After addressing a couple of your other remarks the lookup function slimmed down to a couple of lines, so I moved everything to pctrie_batch_insert.
The enum is still there since rewriting switch-case code would be cumbersome, but it's now part of the batch insert routine.

That is indeed the case, thanks for catching this!

When I merged vm_radix.c with subr_pctrie.c so that there would be only one implementation of pctries, it was accepted, in part, because I made sure to avoid passing pointers to memory allocators to any functions. Otherwise, we'd still have a separate vm_radix implementation. So casually changing that by turning this function into one that passes a function pointer to a memory allocator is not acceptable.

Right, I'll revert this part but I'll still need to access this from subr_pctrie.c somehow.
Would having a separate static version of pctrie_iter_insert in subr_pctrie.c be okay? Bouncing back and forth between pctrie.h and subr_pctrie.c to allocate nodes is something I want to avoid, if possible.

Bouncing is bad.

The number of pctrie_nodes you have to allocate is bounded by something like nitems/(PCTRIE_COUNT-1) + 1. If you figure the quantity precisely, you can pre-allocate all the nodes at the top level as pass an array of pointers to them to the batch_insert function.

I've converted the batch_insert function to follow this approach, although this might slow down cases where nitems == 1 since node allocation is pretty much guaranteed now.
We can avoid that by doing a regular pctrie_iter_insert, but I'm not sure whether this should be handled in _PCTRIE_INSERT_BATCH or in the pctrie consumers (e.g., vm_radix).

I don't think this is enough nodes. If the pctrie is empty, start is 0 and nitems is 768, then you allocate 50 nodes, but you need 48 at the bottom level and 3 at the level above that, and one at the root, so you have too few. I suggested previously nitems / (PCTRIE_COUNT - 1) + 1 as a starting point. Dividing by PCTRIE_COUNT-1 was not a typo; it's how you account for nodes at all levels in an empty trie. 768/15 == 52 works in this case. I was hoping that you would calculate the exact number needed, which also depends on whether the first and/or last leaf will be added to an already allocated leaf. I didn't expect an approach of allocating too many and then freeing the ones you didn't turn out to need. You should write a function that uses the iterator, start and nitems to calculate exactly how many allocations you need. I could write one if you need me to.

I was hoping that you would calculate the exact number needed, which also depends on whether the first and/or last leaf will be added to an already allocated leaf. I didn't expect an approach of allocating too many and then freeing the ones you didn't turn out to need. You should write a function that uses the iterator, start and nitems to calculate exactly how many allocations you need. I could write one if you need me to.

You're right, this expression underestimates the number of nodes. However, I spent some time analyzing the issue and I believe I found a way to calculate the exact number of nodes needed. I'm currently testing it out, so I'll put it up for review in a day or two if everything goes smoothly. I appreciate the offer though!

@alc has expressed to me his belief that computing the number of nodes to allocate in advance leads to a too-complex solution. At the same time, he doesn't want to see an allocation function pointer passed to a function defined in subr_pctrie.c. What he suggests, instead, is that an inline function in pctrie.h, something like PCTRIE_INSERT_BASE, does the allocation and passes the allocated node along to a function - like pctrie_addnode_batch. But pctrie_batch_insert, or something like it, would reside in pctrie.h.

@alc has expressed to me his belief that computing the number of nodes to allocate in advance leads to a too-complex solution.

I share the sentiment, especially after working on D47744.
I don't think we can thoroughly test such an approach, and debugging any eventual crashes caused by it would be nearly impossible.

What he suggests, instead, is that an inline function in pctrie.h, something like PCTRIE_INSERT_BASE, does the allocation and passes the allocated node along to a function - like pctrie_addnode_batch. But pctrie_batch_insert, or something like it, would reside in pctrie.h.

Thank you for the suggestion, I've used it to hoist most of the logic and the node allocation into pctrie.h.

pctrie_insert_lookup inserts, unless memory allocation is required; then, it just does a lookup. pctrie_batch_insert_lookup never inserts anything. Define pctrie_addnodes(node, index, arr, nitems, offs) and call it from here in the ALLOC_INSERT case, so that pctrie_batch_insert isn't called. When pctrie_batch_insert is called after allocation, it can also use pctrie_addnodes().

There's no need to store parent in a struct field. It's easy to get it from it->path and it->top.

If node has value 1 and index 2, you don't split. But node might be the root of the (1-items) tree, and you have to split.

While this technically is splitting, I treat this as a special case of ALLOC_INSERT since the leaf stored at the target slot will end up in the new clev 0 node.
Treating this as SPLIT will lead to one extra allocation, and I'm not sure that it's possible to detect this specific case (i.e., parent node clev == 0 after pctrie_node_init) when allocating nodes in pctrie.h.

Why even have a switch statement, since there are only two real cases?

How could control reach this line? If the new_parent allocation failed. So with 0 returned, total has 0 added to it, and we loop again, and allocfn fails again, so we have an infinite loop? So maybe the failed alloc of new_parent should be handled differently.

if PCTRIE_BATCH_ALLOC_INSERT, 1 is returned, but no node was added.

How would control reach this point?

Why is this test after the PCTRIE_BATCH_ALLOC_INSERT case and not before it?