1#!/usr/bin/env python3 2# SPDX-License-Identifier: GPL-2.0 3 4""" 5Check the quality of the host RSS key (/proc/sys/net/core/netdev_rss_key) 6and that the RSS key a device actually uses spreads flows over all of the 7entries of its indirection table. 8 9The Toeplitz hash is linear over GF(2): the hash is the XOR of the 32 bit key 10windows selected by the set bits of the input, and hardware indexes the 11indirection table with the low order bits of the hash. The windows belonging 12to the q lowest bits of a header field therefore form a Toeplitz matrix, and 13when that matrix is singular the flows of a burst differing only in those 14bits, consecutive ephemeral ports typically, can not reach all of the 2 ** q 15entries of the table. A key drawn uniformly at random is singular for a given 16field and a given q with probability 1/2. 17 18netdev_rss_key_fill() generates keys that are non singular for every field of 19the hash input and every q up to RSS_KEY_QMAX. 20""" 21 22import errno 23import random 24 25from lib.py import ksft_run, ksft_exit, ksft_pr 26from lib.py import ksft_eq, ksft_ge 27from lib.py import KsftSkipEx 28from lib.py import NetDrvEnv, EthtoolFamily, NlError 29 30KEY_PATH = "/proc/sys/net/core/netdev_rss_key" 31 32# Shortest key able to hash an IPv6 4-tuple. 33MIN_KEY_LEN = 40 34 35# Matches NETDEV_RSS_KEY_QMAX, that is up to 256 entries of the table. 36RSS_KEY_QMAX = 8 37 38# "define" for the ID of the Toeplitz hash function 39ETH_RSS_HASH_TOP = 1 40 41FLOW_TYPES = ("tcp4", "udp4", "tcp6", "udp6") 42 43# Map ethtool netlink rxfh-fields flag names to rss_key_layout() codes. 44FIELD_NAMES = { 45 "ip-src": "s", 46 "ip-dst": "d", 47 "l3-proto": "t", 48 "l4-b-0-1": "f", 49 "l4-b-2-3": "n", 50 "ip6-fl": "l", 51} 52 53 54def rss_key_bit(buf, bit): 55 """Bit @bit of @buf, counting from the most significant bit of byte 0.""" 56 return (buf[bit // 8] >> (7 - bit % 8)) & 1 57 58 59def rss_key_assign_bit(buf, bit, value): 60 mask = 0x80 >> (bit % 8) 61 62 if value: 63 buf[bit // 8] |= mask 64 else: 65 buf[bit // 8] &= ~mask 66 67 68def rss_key_window(key, bit): 69 """The 32 key bits starting at @bit, what input bit @bit contributes.""" 70 value = 0 71 72 for i in range(32): 73 value = (value << 1) | rss_key_bit(key, bit + i) 74 75 return value 76 77 78def rss_key_toeplitz(key, inp, nbits): 79 """The Toeplitz hash of the @nbits long input @inp under @key.""" 80 value = 0 81 82 for i in range(nbits): 83 if rss_key_bit(inp, i): 84 value ^= rss_key_window(key, i) 85 86 return value 87 88 89def rss_key_full_rank(key, lsb, q): 90 """Do the q low order bits of the field at @lsb reach all 2 ** q entries? 91 92 Gaussian elimination over GF(2) on the q windows involved, reduced to 93 their q low order bits, which are the ones indexing the table. 94 """ 95 basis = {} 96 97 for j in range(q): 98 vector = rss_key_window(key, lsb - j) & ((1 << q) - 1) 99 100 while vector: 101 low = vector & -vector 102 if low not in basis: 103 basis[low] = vector 104 break 105 vector ^= basis[low] 106 107 if not vector: 108 return False 109 110 return True 111 112 113def rss_key_layout(fields, ipv6): 114 """Describe the hash input built from @fields. 115 116 @fields is the flow hash configuration, "sdfn" for a 4-tuple or "sd" for 117 a 2-tuple. Returns the list of (name, position of the least significant 118 bit) and the length of the input in bits, or None if the layout involves 119 something this does not know how to place. 120 """ 121 addr_bits = 128 if ipv6 else 32 122 known = (("s", "saddr", addr_bits), 123 ("d", "daddr", addr_bits), 124 ("f", "sport", 16), 125 ("n", "dport", 16)) 126 127 if set(fields) - {flag for flag, _, _ in known}: 128 return None, 0 129 130 layout = [] 131 nbits = 0 132 133 for flag, name, width in known: 134 if flag not in fields: 135 continue 136 nbits += width 137 layout.append((name, nbits - 1)) 138 139 return layout, nbits 140 141 142def _read_host_key(): 143 """Return the host RSS key, skipping if it has not been generated.""" 144 try: 145 with open(KEY_PATH, "r", encoding="ascii") as fp: 146 text = fp.read().strip() 147 except FileNotFoundError as exc: 148 raise KsftSkipEx(f"{KEY_PATH} is not available") from exc 149 150 key = bytes(int(byte, 16) for byte in text.split(":")) if text else b"" 151 152 if not any(key): 153 raise KsftSkipEx("the host RSS key has not been generated yet, " 154 "no driver has called netdev_rss_key_fill()") 155 156 return key 157 158 159def _get_rss(cfg): 160 """The key, indirection table, and flow-hash config of @cfg's device.""" 161 try: 162 rss = cfg.ethnl.rss_get({"header": {"dev-index": cfg.ifindex}}) 163 except NlError as exc: 164 if exc.error == errno.EOPNOTSUPP: 165 raise KsftSkipEx(f"{cfg.ifname} does not support RSS") from exc 166 raise 167 168 hkey = rss.get("hkey") 169 if not hkey or not any(hkey): 170 raise KsftSkipEx(f"{cfg.ifname} does not report an RSS key") 171 172 if rss.get("hfunc") != ETH_RSS_HASH_TOP: 173 raise KsftSkipEx(f"{cfg.ifname} does not use the Toeplitz hash") 174 175 if rss.get("input-xfrm"): 176 raise KsftSkipEx(f"{cfg.ifname} transforms the hash input") 177 178 indir = rss.get("indir") 179 if not indir: 180 raise KsftSkipEx(f"{cfg.ifname} does not report an indirection table") 181 182 if len(indir) & (len(indir) - 1): 183 raise KsftSkipEx(f"{cfg.ifname} has {len(indir)} indirection table " 184 "entries, which is not a power of two") 185 186 return bytes(hkey), indir, rss.get("flow-hash", {}) 187 188 189def _get_layouts(flow_hash): 190 """The hash input layouts in use, mapped to the flow types sharing them.""" 191 layouts = {} 192 193 for fl_type in FLOW_TYPES: 194 nl_fields = flow_hash.get(fl_type) 195 if not nl_fields: 196 continue 197 198 fields = "".join(FIELD_NAMES.get(name, "?") for name in nl_fields) 199 layout, nbits = rss_key_layout(fields, fl_type.endswith("6")) 200 if layout is None: 201 ksft_pr(f"{fl_type}: not checked, hashes fields we can not place " 202 f"({nl_fields})") 203 continue 204 205 layouts.setdefault((tuple(layout), nbits), []).append(fl_type) 206 207 if not layouts: 208 raise KsftSkipEx("no flow type with a hash input we can describe") 209 210 return layouts 211 212 213def test_host_rss_key_length(cfg) -> None: 214 key = _read_host_key() 215 216 ksft_pr(f"host RSS key is {len(key)} bytes") 217 ksft_ge(len(key), MIN_KEY_LEN, "key too short to hash an IPv6 4-tuple") 218 219 220def test_host_rss_key_spread(cfg) -> None: 221 key = _read_host_key() 222 degenerate = [] 223 224 for ipv6 in (False, True): 225 layout, _ = rss_key_layout("sdfn", ipv6) 226 family = "IPv6" if ipv6 else "IPv4" 227 228 for name, lsb in layout: 229 if lsb + 32 > len(key) * 8: 230 continue 231 232 for q in range(1, RSS_KEY_QMAX + 1): 233 if not rss_key_full_rank(key, lsb, q): 234 degenerate.append(f"{family} {name} over {1 << q} queues") 235 236 for bad in degenerate: 237 ksft_pr(f"degenerate: {bad}") 238 239 ksft_eq(len(degenerate), 0, 240 "the host RSS key does not spread flows over all the queues") 241 242 243def test_host_rss_key_grid(cfg) -> None: 244 """Sweep the whole key, not only the fields of the usual layouts.""" 245 key = _read_host_key() 246 bits = len(key) * 8 247 positions = 0 248 degenerate = [] 249 250 for lsb in range(15, bits - 31, 16): 251 positions += 1 252 253 for q in range(1, RSS_KEY_QMAX + 1): 254 if not rss_key_full_rank(key, lsb, q): 255 degenerate.append(f"field ending at bit {lsb} " 256 f"over {1 << q} queues") 257 258 ksft_pr(f"checked {positions} positions of the {len(key)} byte key") 259 260 for bad in degenerate[:8]: 261 ksft_pr(f"degenerate: {bad}") 262 263 ksft_eq(len(degenerate), 0, 264 "the host RSS key does not spread flows over all the queues " 265 "at every 16-bit aligned position") 266 267 268def test_dev_rss_key_rank(cfg) -> None: 269 """The key has to be non singular for the size of the table.""" 270 hkey, indir, flow_hash = _get_rss(cfg) 271 q = min((len(indir) - 1).bit_length(), RSS_KEY_QMAX) 272 degenerate = [] 273 274 if not q: 275 raise KsftSkipEx("the indirection table has a single entry") 276 277 for (layout, _), fl_types in _get_layouts(flow_hash).items(): 278 for name, lsb in layout: 279 if lsb + 32 > len(hkey) * 8: 280 ksft_pr(f"{name}: not checked, the key is {len(hkey)} bytes") 281 continue 282 283 if not rss_key_full_rank(hkey, lsb, q): 284 degenerate.append(f"{'/'.join(fl_types)} {name}") 285 286 for bad in degenerate: 287 ksft_pr(f"degenerate: {bad}") 288 289 ksft_eq(len(degenerate), 0, 290 f"the key of {cfg.ifname} does not spread flows over the " 291 f"{1 << q} entries of its indirection table") 292 293 294def test_dev_rss_key_spread(cfg) -> None: 295 """Hash bursts differing in one field only, and place them in the table.""" 296 hkey, indir, flow_hash = _get_rss(cfg) 297 q = (len(indir) - 1).bit_length() 298 collisions = [] 299 300 if q > RSS_KEY_QMAX: 301 raise KsftSkipEx(f"{len(indir)} indirection table entries is more " 302 "than the kernel guarantees") 303 if not q: 304 raise KsftSkipEx("the indirection table has a single entry") 305 306 for (layout, nbits), fl_types in _get_layouts(flow_hash).items(): 307 if nbits + 31 > len(hkey) * 8: 308 ksft_pr(f"{'/'.join(fl_types)}: not checked, the key is " 309 f"{len(hkey)} bytes, input needs {(nbits + 31 + 7) // 8}") 310 continue 311 312 for name, lsb in layout: 313 inp = bytearray(random.randbytes(nbits // 8)) 314 entries = set() 315 for value in range(1 << q): 316 for bit in range(q): 317 rss_key_assign_bit(inp, lsb - bit, value & (1 << bit)) 318 hash_ = rss_key_toeplitz(hkey, inp, nbits) 319 entries.add(hash_ & (len(indir) - 1)) 320 321 if len(entries) != 1 << q: 322 collisions.append(f"{'/'.join(fl_types)} {name} reaches " 323 f"{len(entries)} of the {1 << q} entries") 324 325 for bad in collisions: 326 ksft_pr(bad) 327 328 ksft_eq(len(collisions), 0, 329 f"flows differing in one field only do not fill the " 330 f"indirection table of {cfg.ifname}") 331 332 333def main() -> None: 334 """ Ksft boiler plate main """ 335 336 with NetDrvEnv(__file__, queue_count=4) as cfg: 337 cfg.ethnl = EthtoolFamily() 338 ksft_run(globs=globals(), case_pfx={"test_"}, args=(cfg, )) 339 ksft_exit() 340 341 342if __name__ == "__main__": 343 main() 344