On 6/28/2024 3:59 AM, Mateusz Guzik wrote:
On Thu, Jun 27, 2024 at 8:27 PM Ma, Yu <yu.ma@xxxxxxxxx> wrote:2. For fast path implementation, the essential and simple point is to directly return an available bit if there is free bit in [0-63]. I'd emphasize that it does not only improve low number of open fds (even it is the majority case on system as Honza agreed), but also improve the cases that lots of fds open/close frequently with short task (as per the algorithm, lower bits will be prioritized to allocate after being recycled). Not only blogbench, a synthetic benchmark, but also the realistic scenario as claimed in f3f86e33dc3d("vfs: Fix pathological performance case for __alloc_fd()"), which literally introduced this 2-levels bitmap searching algorithm to vfs as we see now.I don't understand how using next_fd instead is supposed to be inferior. Maybe I should clarify that by API contract the kernel must return the lowest free fd it can find. To that end it maintains the next_fd field as a hint to hopefully avoid some of the search work. In the stock kernel the first thing done in alloc_fd is setting it as a starting point: fdt = files_fdtable(files); fd = start; if (fd < files->next_fd) fd = files->next_fd; that is all the calls which come here with 0 start their search from next_fd position. Suppose you implemented the patch as suggested by me and next_fd fits the range of 0-63. Then you get the benefit of lower level bitmap check just like in the patch you submitted, but without having to first branch on whether you happen to be in that range. Suppose next_fd is somewhere higher up, say 80. With your general approach the optimization wont be done whatsoever or it will be attempted at the 0-63 range when it is an invariant it finds no free fds. With what I'm suggesting the general idea of taking a peek at the lower level bitmap can be applied across the entire fd space. Some manual mucking will be needed to make sure this never pulls more than one cacheline, easiest way out I see would be to align next_fd to BITS_PER_LONG for the bitmap search purposes.
Some misunderstanding here, Guzik, I thought you felt not so worth for fast path in previous feedback, so the whole message sent just wanna say we still think the original idea is reasonable. Back to the point here, the way to implement it in find_next_fd() by searching the word with next_fd makes sense and OK to me. It's efficient, concise and should bring us the expected benefits. I'll re-measure the data for reference based on the code proposed by you and Honza.
Outside of the scope of this patchset, but definitely worth considering, is an observation that this still pulls an entire cacheline worth of a bitmap (assuming it grew). If one could assume that the size is always a multiply of 64 bytes (which it is after first expansion) the 64 byte scan could be entirely inlined -- there is quite a bit of fd fields in this range we may as well scan in hopes of avoiding looking at the higher level bitmap, after all we already paid for fetching it. This would take the optimization to its logical conclusion. Perhaps it would be ok to special-case the lower bitmap to start with 64 bytes so that there would be no need to branch on it.
