[ifconfig] Prevent extensive cycles spent on sorting IP adresses

[se]

Summary

Bug report #263604 (https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=263604) suggests to remove the sorting of IP addresses currently performed when interface parameters are displayed. This sorting takes a long time (more than 1 second) for interfaces with an excessively high number of addresses (~4000 in this particular bug report).

While the sorted list is useful for quick lookup of addresses in the normal interactive use case, interfaces with a large number of addresses will probably be configured and checked with tools that do not depend on any particular order of addresses in the output.

The patch in this review limits the number of IP addresses that will display in a sorted list to 32 (as #defined), longer lists will be displayed without sorting.

Other operations are unaffected, since the patched function is only called in one place for display purposes, but not for any functionality that changes the interface state.

Test Plan

Apply patch and verify unchanged output for interfaces with at most 32 IP addresses.

Assign more than 32 additional addresses to an interface (e.g., lo0) and verify that all addresses are displayed (but in an arbitrary order, dependent on their position in the internal linked list).

[kp]

Isn't there room for improving sortifaddrs() so it works well on machines with many addresses? It's not ideal to only sort some of the time, and it really shouldn't take all that long to sort 4000 elements.

I've only looked at the function briefly, but it seems as if it's doing a recursive merge sort between [0, Len -1] and [len], so it should be possible to make that a lot faster, even with a naive bubble sort. I'd actually expect a bubble sort to work okay, because we're probably going to get the list sorted per interface already, so most sort work will be local. (Although this is mostly speculation, I've not dug very deep here.)

[se]

I see 3 alternatives to the current approach:

1. Use a better algorithm with lower time complexity
2. Insert addresses at their correct position in ip address order (possibly also in a different data structure, e.g. a balanced tree)
3. Sort for display, keep the sorted list and set a flag (cleared when another address is added) to skip sorting if not necessary

The sorting is relatively slow since there is a complex comparison function defining the desired order and the data to be sorted is in a linked list, not an array.

Since lists of more than 32 addresses are exceptional, the suggested patch affects only a very small part of the user base.
And if there are more than 32 addresses, I do expect that they are not manually configured and checked, but instead by some other process.

It is of course possible to make ifconfig use an array instead of (or in addition to) the linked list, but I'm not going to implement such a change, and I'm also not going to code a quicksort or heapsort that operates on a linked list instead of on an array.

The patch fixes the issue for the reporter, and it does not affect ordinary users. The limit could be higher (e.g. 128 addresses or 512), but due to the n^2 time complexity of the sort, 512 addresses will take 256 times as long as 32.

I might be convinced to provide a patch that inserts added addresses in the correct position in the linked list. This would still impose the cost (n^2) on each user who adds many interfaces, even if the addresses are never queried. But the cycles would be spent distributed over the insert operations and not be as obvious as they are now.

[kp]

In D35144#796757, @se wrote:

I see 3 alternatives to the current approach:

1. Use a better algorithm with lower time complexity
2. Insert addresses at their correct position in ip address order (possibly also in a different data structure, e.g. a balanced tree)
3. Sort for display, keep the sorted list and set a flag (cleared when another address is added) to skip sorting if not necessary

The sorting is relatively slow since there is a complex comparison function defining the desired order and the data to be sorted is in a linked list, not an array.

I strongly suspect the sorting is slow because the sorting algorithm is incorrectly implemented, and it's doing a *lot* more work than it needs to do. I recommend investigating that first, because making the sorting faster is a lot less controversial than not sorting in certain circumstances.

Since lists of more than 32 addresses are exceptional, the suggested patch affects only a very small part of the user base.

I've been bitten by that reasoning too many times to buy into it.

And if there are more than 32 addresses, I do expect that they are not manually configured and checked, but instead by some other process.

Users do user things. They will be creatively silly.

It is of course possible to make ifconfig use an array instead of (or in addition to) the linked list, but I'm not going to implement such a change, and I'm also not going to code a quicksort or heapsort that operates on a linked list instead of on an array.

I don't think it will take converting this to an array to make the sort acceptably quick.

[se]

The sorting has been added as a convenience function in 2015, it provides grouping of entries for IPv6 addresses of different scopes.

Having more than 32 entries in the list that used to be displayed without this extra sorting is extremely uncommon, in the reported case it was for more than 1000 VLANs with some 4000 addresses on a single interface.
Such a configuration is a very special case, and it is possible to document that the convenience function will be skipped for more than 32 (or whatever) elements in the list (in the man-page and in release notes).

As stated before: If you have such a long list, you'll probably use tools to manage it, and those tools should not depend on the order of entries (it is not a simple numerical or lexicographical order that would e.g. allow to do a binary search, anyway).

If a function that has been added for the convenience of users (and not for correctness, the documentation does not specify or guarantee any order) leads to undesirable behavior in cases that have not been assumed and considered when it was implemented, modifying it for such a special case can be a solution.

I'm going to add vsevolod@ as a reviewer, since he has committed this sorting by address family and scope.
It may well be possible to make it more efficient for large lists, but I do not have time to work on this.
Please suggest a better algorithm if you think this is the correct solution.

[mjg]

Quick look suggests there is no need to sort anything. Instead, the code can do multiple passes, each time only printing one specific type. The result will be identical, all while having linear complexity. Of course this still wont be optimal, but it will likely be more than good enough.

[linnemannr_gmail.com]

In D35144#796716, @kp wrote:

I've only looked at the function briefly, but it seems as if it's doing a recursive merge sort between [0, Len -1] and [len], so it should be possible to make that a lot faster, even with a naive bubble sort. I'd actually expect a bubble sort to work okay, because we're probably going to get the list sorted per interface already, so most sort work will be local. (Although this is mostly speculation, I've not dug very deep here.)

I thought this as well, but if you look a little closer the loop is bounded by (temp && temp->ifa_next), and temp seeks two elements each iteration so right is the middle of the list when the loop terminates. There should be a base case for a two element list so the sort doesn't recurse when we can just swap elements if needed and return the input list and skip the additional recursion and merge of an element into a single element list.