Control-flow integrity in 5.13

Posted May 23, 2021 8:50 UTC (Sun) by jpfrancois (subscriber, #65948)
In reply to: Control-flow integrity in 5.13 by anton
Parent article: Control-flow integrity in 5.13

What about 1000 functions ? How does it scale ? Here is a count of file using struct file_operations.
https://elixir.bootlin.com/linux/v5.12.6/C/ident/file_ope...

net_device_ops goes into the 500.

I suppose other heavily used abstraction will suffer the same penalty.

to post comments

Control-flow integrity in 5.13

Posted May 23, 2021 11:47 UTC (Sun) by anton (subscriber, #25547) [Link]

The number of files that a struct is used in does not tell us anything about the number of targets that clang might see as potential targets for a given call through a function pointer. With several dozen file system types, I expect that VFS operations will have several dozen target functions (and hopefully with unique signatures).

As for scaling, the basic scaling properties of divide-and-conquer searches are well known. The search time (and the number of nodes accessed) increases logarithmically with the size of the search space. If your question is about the constant factors, I can give better answers today than yesterday:

If we try to minimize the number of cache lines accessed (important for cold code), we get a B-tree-like characteristic, where we consider each cache line to be a tree node with 8 subtrees or (for leaf nodes) 8 target functions; in some cases, a little more is possible, giving us 73 targets for a two-level tree. Measuring such a tree access, I see that this dispatch costs, e.g. on Zen3, 8-10 cycles rather than 6-8 for the binary tree with 7 targets, so every level costs roughly 2 cycles. So if we have a four-level tree for 4096 targets, the total cost will be about 12-14 cycles (in the well-predicted and cached case) and the search will access 4 I-cache lines. If there are branch mispredictions, that would cause a lot of slowdown, however.