- 01 Apr, 2024 2 commits
-
-
Alexander Potapenko authored
Add basic tests ensuring that values can be added at arbitrary positions of the bitmap, including those spanning into the adjacent unsigned longs. Two new performance tests, test_bitmap_read_perf() and test_bitmap_write_perf(), can be used to assess future performance improvements of bitmap_read() and bitmap_write(): [ 0.431119][ T1] test_bitmap: Time spent in test_bitmap_read_perf: 615253 [ 0.433197][ T1] test_bitmap: Time spent in test_bitmap_write_perf: 916313 (numbers from a Intel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz machine running QEMU). Signed-off-by:
Alexander Potapenko <glider@google.com> Reviewed-by:
Andy Shevchenko <andriy.shevchenko@linux.intel.com> Acked-by:
Yury Norov <yury.norov@gmail.com> Signed-off-by:
Alexander Lobakin <aleksander.lobakin@intel.com> Signed-off-by:
David S. Miller <davem@davemloft.net>
-
Syed Nayyar Waris authored
The two new functions allow reading/writing values of length up to BITS_PER_LONG bits at arbitrary position in the bitmap. The code was taken from "bitops: Introduce the for_each_set_clump macro" by Syed Nayyar Waris with a number of changes and simplifications: - instead of using roundup(), which adds an unnecessary dependency on <linux/math.h>, we calculate space as BITS_PER_LONG-offset; - indentation is reduced by not using else-clauses (suggested by checkpatch for bitmap_get_value()); - bitmap_get_value()/bitmap_set_value() are renamed to bitmap_read() and bitmap_write(); - some redundant computations are omitted. Cc: Arnd Bergmann <arnd@arndb.de> Signed-off-by:
Syed Nayyar Waris <syednwaris@gmail.com> Signed-off-by:
William Breathitt Gray <william.gray@linaro.org> Link: https://lore.kernel.org/lkml/fe12eedf3666f4af5138de0e70b67a07c7f40338.1592224129.git.syednwaris@gmail.com/Suggested-by:
-
- 29 Mar, 2024 38 commits
-
-
Jakub Kicinski authored
Christophe Roullier says: ==================== Add property in dwmac-stm32 documentation Introduce property in dwmac-stm32 documentation - st,ext-phyclk: is present since 2020 in driver so need to explain it and avoid dtbs check issue : views/kernel/upstream/net-next/arch/arm/boot/dts/st/stm32mp157c-dk2.dtb: ethernet@5800a000: Unevaluated properties are not allowed ('st,ext-phyclk' was unexpected) Furthermore this property will be use in upstream of MP13 dwmac glue. (next step) ==================== Link: https://lore.kernel.org/r/20240328185337.332703-1-christophe.roullier@foss.st.comSigned-off-by:Jakub Kicinski <kuba@kernel.org>
-
Christophe Roullier authored
The Linux kernel dwmac-stm32 driver currently supports three DT properties used to configure whether PHY clock are generated by the MAC or supplied to the MAC from the PHY. Originally there were two properties, st,eth-clk-sel and st,eth-ref-clk-sel, each used to configure MAC clocking in different bus mode and for different MAC clock frequency. Since it is possible to determine the MAC 'eth-ck' clock frequency from the clock subsystem and PHY bus mode from the 'phy-mode' property, two disparate DT properties are no longer required to configure MAC clocking. Linux kernel commit 1bb694e2 ("net: ethernet: stmmac: simplify phy modes management for stm32") introduced a third, unified, property st,ext-phyclk. This property covers both use cases of st,eth-clk-sel and st,eth-ref-clk-sel DT properties, as well as a new use case for 25 MHz clock generated by the MAC. The third property st,ext-phyclk is so far undocumented, document it. Below table summarizes the clock requirement and clock sources for supported PHY interface modes. __________________________________________________________________________ |PHY_MODE | Normal | PHY wo crystal| PHY wo crystal |No 125Mhz from PHY| | | | 25MHz | 50MHz | | --------------------------------------------------------------------------- | MII | - | eth-ck | n/a | n/a | | | | st,ext-phyclk | | | --------------------------------------------------------------------------- | GMII | - | eth-ck | n/a | n/a | | | | st,ext-phyclk | | | --------------------------------------------------------------------------- | RGMII | - | eth-ck | n/a | eth-ck | | | | st,ext-phyclk | | st,eth-clk-sel or| | | | | | st,ext-phyclk | --------------------------------------------------------------------------- | RMII | - | eth-ck | eth-ck | n/a | | | | st,ext-phyclk | st,eth-ref-clk-sel | | | | | | or st,ext-phyclk | | --------------------------------------------------------------------------- Reviewed-by:
Krzysztof Kozlowski <krzysztof.kozlowski@linaro.org> Reviewed-by:
Marek Vasut <marex@denx.de> Signed-off-by:
Christophe Roullier <christophe.roullier@foss.st.com> Link: https://lore.kernel.org/r/20240328185337.332703-2-christophe.roullier@foss.st.comSigned-off-by:
-
Johannes Berg authored
There are, especially with multi-attr arrays, many cases of needing to iterate all attributes of a specific type in a netlink message or a nested attribute. Add specific macros to support that case. Also convert many instances using this spatch: @@ iterator nla_for_each_attr; iterator name nla_for_each_attr_type; identifier nla; expression head, len, rem; expression ATTR; type T; identifier x; @@ -nla_for_each_attr(nla, head, len, rem) +nla_for_each_attr_type(nla, ATTR, head, len, rem) { <... T x; ...> -if (nla_type(nla) == ATTR) { ... -} } @@ identifier nla; iterator nla_for_each_nested; iterator name nla_for_each_nested_type; expression attr, rem; expression ATTR; type T; identifier x; @@ -nla_for_each_nested(nla, attr, rem) +nla_for_each_nested_type(nla, ATTR, attr, rem) { <... T x; ...> -if (nla_type(nla) == ATTR) { ... -} } @@ iterator nla_for_each_attr; iterator name nla_for_each_attr_type; identifier nla; expression head, len, rem; expression ATTR; type T; identifier x; @@ -nla_for_each_attr(nla, head, len, rem) +nla_for_each_attr_type(nla, ATTR, head, len, rem) { <... T x; ...> -if (nla_type(nla) != ATTR) continue; ... } @@ identifier nla; iterator nla_for_each_nested; iterator name nla_for_each_nested_type; expression attr, rem; expression ATTR; type T; identifier x; @@ -nla_for_each_nested(nla, attr, rem) +nla_for_each_nested_type(nla, ATTR, attr, rem) { <... T x; ...> -if (nla_type(nla) != ATTR) continue; ... } Although I had to undo one bad change this made, and I also adjusted some other code for whitespace and to use direct variable initialization now. Signed-off-by:Johannes Berg <johannes.berg@intel.com> Link: https://lore.kernel.org/r/20240328203144.b5a6c895fb80.I1869b44767379f204998ff44dd239803f39c23e0@changeidSigned-off-by:
-
Jakub Kicinski authored
Eric Dumazet says: ==================== udp: small changes on receive path This series is based on an observation I made in UDP receive path. The sock_def_readable() costs are pretty high, especially when epoll is used to generate EPOLLIN events. First patch annotates races on sk->sk_rcvbuf reads. Second patch replaces an atomic_add_return() with a less expensive atomic_add() Third patch avoids calling sock_def_readable() when possible. Fourth patch adds sk_wake_async_rcu() to get better inlining and code generation. ==================== Link: https://lore.kernel.org/r/20240328144032.1864988-1-edumazet@google.comSigned-off-by:
-
Eric Dumazet authored
While looking at UDP receive performance, I saw sk_wake_async() was no longer inlined. This matters at least on AMD Zen1-4 platforms (see SRSO) This might be because rcu_read_lock() and rcu_read_unlock() are no longer nops in recent kernels ? Add sk_wake_async_rcu() variant, which must be called from contexts already holding rcu lock. As SOCK_FASYNC is deprecated in modern days, use unlikely() to give a hint to the compiler. sk_wake_async_rcu() is properly inlined from __udp_enqueue_schedule_skb() and sock_def_readable(). Signed-off-by:
Eric Dumazet <edumazet@google.com> Link: https://lore.kernel.org/r/20240328144032.1864988-5-edumazet@google.comSigned-off-by:
-
Eric Dumazet authored
sock_def_readable() is quite expensive (particularly when ep_poll_callback() is in the picture). We must call sk->sk_data_ready() when : - receive queue was empty, or - SO_PEEK_OFF is enabled on the socket, or - sk->sk_data_ready is not sock_def_readable. We still need to call sk_wake_async(). Signed-off-by:
Willem de Bruijn <willemb@google.com> Acked-by:
Paolo Abeni <pabeni@redhat.com> Link: https://lore.kernel.org/r/20240328144032.1864988-4-edumazet@google.comSigned-off-by:
-
Eric Dumazet authored
atomic_add_return() is more expensive than atomic_add() and seems overkill in UDP rx fast path. Signed-off-by:
-
Eric Dumazet authored
sk->sk_rcvbuf is read locklessly twice, while other threads could change its value. Use a READ_ONCE() to annotate the race. Signed-off-by:
-
Jakub Kicinski authored
Arnd Bergmann says: ==================== address remaining -Wtautological-constant-out-of-range-compare The warning option was introduced a few years ago but left disabled by default. All of the actual bugs that this has found have been fixed in the meantime, and this series should address the remaining false-positives, as tested on arm/arm64/x86 randconfigs as well as allmodconfig builds for all architectures supported by clang. ==================== Link: https://lore.kernel.org/r/20240328143051.1069575-1-arnd@kernel.orgSigned-off-by:
-
Arnd Bergmann authored
When building with 64KB pages, clang points out that xsk->chunk_size can never be PAGE_SIZE: drivers/net/ethernet/mellanox/mlx5/core/en/xsk/setup.c:19:22: error: result of comparison of constant 65536 with expression of type 'u16' (aka 'unsigned short') is always false [-Werror,-Wtautological-constant-out-of-range-compare] if (xsk->chunk_size > PAGE_SIZE || ~~~~~~~~~~~~~~~ ^ ~~~~~~~~~ In older versions of this code, using PAGE_SIZE was the only possibility, so this would have never worked on 64KB page kernels, but the patch apparently did not address this case completely. As Maxim Mikityanskiy suggested, 64KB chunks are really not all that useful, so just shut up the warning by adding a cast. Fixes: 282c0c79 ("net/mlx5e: Allow XSK frames smaller than a page") Link: https://lore.kernel.org/netdev/20211013150232.2942146-1-arnd@kernel.org/ Link: https://lore.kernel.org/lkml/a7b27541-0ebb-4f2d-bd06-270a4d404613@app.fastmail.com/Signed-off-by:Arnd Bergmann <arnd@arndb.de> Acked-by:
Maxim Mikityanskiy <maxtram95@gmail.com> Reviewed-by:
Justin Stitt <justinstitt@google.com> Reviewed-by:
Tariq Toukan <tariqt@nvidia.com> Link: https://lore.kernel.org/r/20240328143051.1069575-9-arnd@kernel.orgSigned-off-by:
-
Suraj Gupta authored
Add description of mdio enable, mdio disable and mdio wait functions. Add description of skb pointer in axidma_bd data structure. Remove 'phy_node' description in axienet local data structure since it is not a valid struct member. Correct description of struct axienet_option. Fix below kernel-doc warnings in drivers/net/ethernet/xilinx/: 1) xilinx_axienet_mdio.c:1: warning: no structured comments found 2) xilinx_axienet.h:379: warning: Function parameter or struct member 'skb' not described in 'axidma_bd' 3) xilinx_axienet.h:538: warning: Excess struct member 'phy_node' description in 'axienet_local' 4) xilinx_axienet.h:1002: warning: expecting prototype for struct axiethernet_option. Prototype was for struct axienet_option instead Signed-off-by:
Suraj Gupta <suraj.gupta2@amd.com> Reviewed-by:
Radhey Shyam Pandey <radhey.shyam.pandey@amd.com> Link: https://lore.kernel.org/r/20240328110713.12885-1-suraj.gupta2@amd.comSigned-off-by:
-
Su Hui authored
Clang static checker(scan-buid): drivers/net/ethernet/marvell/octeontx2/nic/otx2_pf.c:503:2: warning: Value stored to 'rsp_hdr' is never read [deadcode.DeadStores] Remove these unused variables to save some space. Signed-off-by:
Su Hui <suhui@nfschina.com> Reviewed-by:
Simon Horman <horms@kernel.org> Link: https://lore.kernel.org/r/20240328020723.4071539-1-suhui@nfschina.comSigned-off-by:
-
Krzysztof Kozlowski authored
Core in spi_register_driver() already sets the .owner, so driver does not need to. Signed-off-by:
-
Krzysztof Kozlowski authored
Core in spi_register_driver() already sets the .owner, so driver does not need to. Signed-off-by:
-
Krzysztof Kozlowski authored
Core in mhi_driver_register() already sets the .owner, so driver does not need to. Signed-off-by:
Sergey Ryazanov <ryazanov.s.a@gmail.com> Link: https://lore.kernel.org/r/20240327174810.519676-2-krzysztof.kozlowski@linaro.orgSigned-off-by:
-
Krzysztof Kozlowski authored
Core in spi_register_driver() already sets the .owner, so driver does not need to. Signed-off-by:
-
Donald Hunter authored
The NLMSGERR_ATTR_POLICY extack attribute has been ignored by ynl up to now. Extend extack decoding to include _POLICY and the nested NL_POLICY_TYPE_ATTR_* attributes. For example: ./tools/net/ynl/cli.py \ --spec Documentation/netlink/specs/rt_link.yaml \ --create --do newlink --json '{ "ifname": "12345678901234567890", "linkinfo": {"kind": "bridge"} }' Netlink error: Numerical result out of range nl_len = 104 (88) nl_flags = 0x300 nl_type = 2 error: -34 extack: {'msg': 'Attribute failed policy validation', 'policy': {'max-length': 15, 'type': 'string'}, 'bad-attr': '.ifname'} Signed-off-by:Donald Hunter <donald.hunter@gmail.com> Link: https://lore.kernel.org/r/20240328155636.64688-1-donald.hunter@gmail.comSigned-off-by:
-
Jian Wen authored
During live migration of a virtual machine, the SR-IOV VF need to be re-registered. It may fail when the memory is badly fragmented. The related log is as follows. kernel: hv_netvsc 6045bdaa-c0d1-6045-bdaa-c0d16045bdaa eth0: VF slot 1 added ... kernel: kworker/0:0: page allocation failure: order:7, mode:0x40dc0(GFP_KERNEL|__GFP_COMP|__GFP_ZERO), nodemask=(null),cpuset=/,mems_allowed=0 kernel: CPU: 0 PID: 24006 Comm: kworker/0:0 Tainted: G E 5.4...x86_64 #1 kernel: Hardware name: Microsoft Corporation Virtual Machine/Virtual Machine, BIOS 090008 12/07/2018 kernel: Workqueue: events work_for_cpu_fn kernel: Call Trace: kernel: dump_stack+0x8b/0xc8 kernel: warn_alloc+0xff/0x170 kernel: __alloc_pages_slowpath+0x92c/0xb2b kernel: ? get_page_from_freelist+0x1d4/0x1140 kernel: __alloc_pages_nodemask+0x2f9/0x320 kernel: alloc_pages_current+0x6a/0xb0 kernel: kmalloc_order+0x1e/0x70 kernel: kmalloc_order_trace+0x26/0xb0 kernel: ? __switch_to_asm+0x34/0x70 kernel: __kmalloc+0x276/0x280 kernel: ? _raw_spin_unlock_irqrestore+0x1e/0x40 kernel: devlink_alloc+0x29/0x110 kernel: mlx5_devlink_alloc+0x1a/0x20 [mlx5_core] kernel: init_one+0x1d/0x650 [mlx5_core] kernel: local_pci_probe+0x46/0x90 kernel: work_for_cpu_fn+0x1a/0x30 kernel: process_one_work+0x16d/0x390 kernel: worker_thread+0x1d3/0x3f0 kernel: kthread+0x105/0x140 kernel: ? max_active_store+0x80/0x80 kernel: ? kthread_bind+0x20/0x20 kernel: ret_from_fork+0x3a/0x50 Signed-off-by:Jian Wen <wenjian1@xiaomi.com> Link: https://lore.kernel.org/r/20240327082128.942818-1-wenjian1@xiaomi.comSigned-off-by:
-
Jakub Kicinski authored
Arnd Bergmann says: ==================== enabled -Wformat-truncation for clang With randconfig build testing, I found only eight files that produce warnings with clang when -Wformat-truncation is enabled. This means we can just turn it on by default rather than only enabling it for "make W=1". Unfortunately, gcc produces a lot more warnings when the option is enabled, so it's not yet possible to turn it on both compilers. ==================== Link: https://lore.kernel.org/r/20240326223825.4084412-1-arnd@kernel.orgSigned-off-by:
-
Arnd Bergmann authored
clang warns that one error message is too long for its destination buffer: drivers/net/ethernet/mellanox/mlx5/core/esw/bridge.c:1876:4: error: 'snprintf' will always be truncated; specified size is 80, but format string expands to at least 94 [-Werror,-Wformat-truncation-non-kprintf] Reword it to be a bit shorter so it always fits. Fixes: 70f0302b ("net/mlx5: Bridge, implement mdb offload") Signed-off-by:
Subbaraya Sundeep <sbhatta@marvell.com> Link: https://lore.kernel.org/r/20240326223825.4084412-5-arnd@kernel.orgSigned-off-by:
-
Arnd Bergmann authored
clang complains that the temporary string for the name passed into alloc_workqueue() is too short for its contents: drivers/net/ethernet/qlogic/qed/qed_main.c:1218:3: error: 'snprintf' will always be truncated; specified size is 16, but format string expands to at least 18 [-Werror,-Wformat-truncation] There is no need for a temporary buffer, and the actual name of a workqueue is 32 bytes (WQ_NAME_LEN), so just use the interface as intended to avoid the truncation. Fixes: 59ccf86f ("qed: Add driver infrastucture for handling mfw requests.") Signed-off-by:
-
Arnd Bergmann authored
As clang points out, the error message in enetc_setup_xdp_prog() still does not fit in the buffer and will be truncated: drivers/net/ethernet/freescale/enetc/enetc.c:2771:3: error: 'snprintf' will always be truncated; specified size is 80, but format string expands to at least 87 [-Werror,-Wformat-truncation] Replace it with an even shorter message that should fit. Fixes: f968c564 ("net: enetc: shorten enetc_setup_xdp_prog() error message to fit NETLINK_MAX_FMTMSG_LEN") Signed-off-by:
-
Radha Mohan Chintakuntla authored
Any NIX interface type can have maximum 256 channels. So increased the backpressure ID count to 256 so that it can cover cn9k and cn10k SoCs that have different NIX interface types with varied maximum channels. Signed-off-by:
Radha Mohan Chintakuntla <radhac@marvell.com> Link: https://lore.kernel.org/r/20240326184514.1628284-1-radhac@marvell.comSigned-off-by:
-
Jakub Kicinski authored
Balazs Scheidler says: ==================== Add IP/port information to UDP drop tracepoint In our use-case we would like to recover the properties of dropped UDP packets. Unfortunately the current udp_fail_queue_rcv_skb tracepoint only exposes the port number of the receiving socket. This patch-set will add the source/dest ip/port to the tracepoint, while keeping the socket's local port as well for compatibility. Thanks for the review comments by Jason and Kuniyuki, they helped me a lot and I tried to address all of their comments in this new iteration. ==================== Link: https://lore.kernel.org/r/cover.1711475011.git.balazs.scheidler@axoflow.comSigned-off-by:
-
Balazs Scheidler authored
The udp_fail_queue_rcv_skb() tracepoint lacks any details on the source and destination IP/port whereas this information can be critical in case of UDP/syslog. Signed-off-by:
Balazs Scheidler <balazs.scheidler@axoflow.com> Reviewed-by:
Jason Xing <kerneljasonxing@gmail.com> Link: https://lore.kernel.org/r/0c8b3e33dbf679e190be6f4c6736603a76988a20.1711475011.git.balazs.scheidler@axoflow.comSigned-off-by:
-
Balazs Scheidler authored
This patch moves TP_STORE_ADDR_PORTS_SKB() to a common header and removes the TCP specific implementation details. Previously the macro assumed the skb passed as an argument is a TCP packet, the implementation now uses an argument to the L4 header and uses that to extract the source/destination ports, which happen to be named the same in "struct tcphdr" and "struct udphdr" Reviewed-by:
-
Andy Shevchenko authored
This updates the driver to gpiod API, and removes yet another use of of_get_named_gpio(). Signed-off-by:
-
Jakub Kicinski authored
Eric Woudstra says: ==================== Add en8811h phy driver and devicetree binding doc This patch series adds the driver and the devicetree binding documentation for the Airoha en8811h PHY. ==================== Link: https://lore.kernel.org/r/20240326162305.303598-1-ericwouds@gmail.comSigned-off-by:
-
Eric Woudstra authored
Add the driver for the Airoha EN8811H 2.5 Gigabit PHY. The phy supports 100/1000/2500 Mbps with auto negotiation only. The driver uses two firmware files, for which updated versions are added to linux-firmware already. Note: At phy-address + 8 there is another device on the mdio bus, that belongs to the EN881H. While the original driver writes to it, Airoha has confirmed this is not needed. Therefore, communication with this device is not included in this driver. Signed-off-by:
Eric Woudstra <ericwouds@gmail.com> Reviewed-by:
Andrew Lunn <andrew@lunn.ch> Link: https://lore.kernel.org/r/20240326162305.303598-3-ericwouds@gmail.comSigned-off-by:
-
Eric Woudstra authored
Add the Airoha EN8811H 2.5 Gigabit PHY. The en8811h phy can be set with serdes polarity reversed on rx and/or tx. Signed-off-by:
-
Jakub Kicinski authored
Kuniyuki Iwashima says: ==================== af_unix: Rework GC. When we pass a file descriptor to an AF_UNIX socket via SCM_RIGTHS, the underlying struct file of the inflight fd gets its refcount bumped. If the fd is of an AF_UNIX socket, we need to track it in case it forms cyclic references. Let's say we send a fd of AF_UNIX socket A to B and vice versa and close() both sockets. When created, each socket's struct file initially has one reference. After the fd exchange, both refcounts are bumped up to 2. Then, close() decreases both to 1. From this point on, no one can touch the file/socket. However, the struct file has one refcount and thus never calls the release() function of the AF_UNIX socket. That's why we need to track all inflight AF_UNIX sockets and run garbage collection. This series replaces the current GC implementation that locks each inflight socket's receive queue and requires trickiness in other places. The new GC does not lock each socket's queue to minimise its effect and tries to be lightweight if there is no cyclic reference or no update in the shape of the inflight fd graph. The new implementation is based on Tarjan's Strongly Connected Components algorithm, and we will consider each inflight AF_UNIX socket as a vertex and its file descriptor as an edge in a directed graph. For the details, please see each patch. patch 1 - 3 : Add struct to express inflight socket graphs patch 4 : Optimse inflight fd counting patch 5 - 6 : Group SCC possibly forming a cycle patch 7 - 8 : Support embryo socket patch 9 - 11 : Make GC lightweight patch 12 - 13 : Detect dead cycle references patch 14 : Replace GC algorithm patch 15 : selftest After this series is applied, we can remove the two ugly tricks for race, scm_fp_dup() in unix_attach_fds() and spin_lock dance in unix_peek_fds() as done in patch 14/15 of v1. Also, we will add cond_resched_lock() in __unix_gc() and convert it to use a dedicated kthread instead of global system workqueue as suggested by Paolo in a v4 thread. v4: https://lore.kernel.org/netdev/20240301022243.73908-1-kuniyu@amazon.com/ v3: https://lore.kernel.org/netdev/20240223214003.17369-1-kuniyu@amazon.com/ v2: https://lore.kernel.org/netdev/20240216210556.65913-1-kuniyu@amazon.com/ v1: https://lore.kernel.org/netdev/20240203030058.60750-1-kuniyu@amazon.com/ ==================== Link: https://lore.kernel.org/r/20240325202425.60930-1-kuniyu@amazon.comSigned-off-by:
-
Kuniyuki Iwashima authored
This patch adds test cases to verify the new GC. We run each test for the following cases: * SOCK_DGRAM * SOCK_STREAM without embryo socket * SOCK_STREAM without embryo socket + MSG_OOB * SOCK_STREAM with embryo sockets * SOCK_STREAM with embryo sockets + MSG_OOB Before and after running each test case, we ensure that there is no AF_UNIX socket left in the netns by reading /proc/net/protocols. We cannot use /proc/net/unix and UNIX_DIAG because the embryo socket does not show up there. Each test creates multiple sockets in an array. We pass sockets in the even index using the peer sockets in the odd index. So, send_fd(0, 1) actually sends fd[0] to fd[2] via fd[0 + 1]. Test 1 : A <-> A Test 2 : A <-> B Test 3 : A -> B -> C <- D ^.___|___.' ^ `---------' Signed-off-by:Kuniyuki Iwashima <kuniyu@amazon.com> Acked-by:
-
Kuniyuki Iwashima authored
If we find a dead SCC during iteration, we call unix_collect_skb() to splice all skb in the SCC to the global sk_buff_head, hitlist. After iterating all SCC, we unlock unix_gc_lock and purge the queue. Signed-off-by:
-
Kuniyuki Iwashima authored
When iterating SCC, we call unix_vertex_dead() for each vertex to check if the vertex is close()d and has no bridge to another SCC. If both conditions are true for every vertex in SCC, we can execute garbage collection for all skb in the SCC. The actual garbage collection is done in the following patch, replacing the old implementation. Signed-off-by:
-
Kuniyuki Iwashima authored
The definition of the lowlink in Tarjan's algorithm is the smallest index of a vertex that is reachable with at most one back-edge in SCC. This is not useful for a cross-edge. If we start traversing from A in the following graph, the final lowlink of D is 3. The cross-edge here is one between D and C. A -> B -> D D = (4, 3) (index, lowlink) ^ | | C = (3, 1) | V | B = (2, 1) `--- C <--' A = (1, 1) This is because the lowlink of D is updated with the index of C. In the following patch, we detect a dead SCC by checking two conditions for each vertex. 1) vertex has no edge directed to another SCC (no bridge) 2) vertex's out_degree is the same as the refcount of its file If 1) is false, there is a receiver of all fds of the SCC and its ancestor SCC. To evaluate 1), we need to assign a unique index to each SCC and assign it to all vertices in the SCC. This patch changes the lowlink update logic for cross-edge so that in the example above, the lowlink of D is updated with the lowlink of C. A -> B -> D D = (4, 1) (index, lowlink) ^ | | C = (3, 1) | V | B = (2, 1) `--- C <--' A = (1, 1) Then, all vertices in the same SCC have the same lowlink, and we can quickly find the bridge connecting to different SCC if exists. However, it is no longer called lowlink, so we rename it to scc_index. (It's sometimes called lowpoint.) Also, we add a global variable to hold the last index used in DFS so that we do not reset the initial index in each DFS. This patch can be squashed to the SCC detection patch but is split deliberately for anyone wondering why lowlink is not used as used in the original Tarjan's algorithm and many reference implementations. Signed-off-by:
-
Kuniyuki Iwashima authored
Once a cyclic reference is formed, we need to run GC to check if there is dead SCC. However, we do not need to run Tarjan's algorithm if we know that the shape of the inflight graph has not been changed. If an edge is added/updated/deleted and the edge's successor is inflight, we set false to unix_graph_grouped, which means we need to re-classify SCC. Once we finalise SCC, we set true to unix_graph_grouped. While unix_graph_grouped is true, we can iterate the grouped SCC using vertex->scc_entry in unix_walk_scc_fast(). list_add() and list_for_each_entry_reverse() uses seem weird, but they are to keep the vertex order consistent and make writing test easier. Signed-off-by:
-
Kuniyuki Iwashima authored
We do not need to run GC if there is no possible cyclic reference. We use unix_graph_maybe_cyclic to decide if we should run GC. If a fd of an AF_UNIX socket is passed to an already inflight AF_UNIX socket, they could form a cyclic reference. Then, we set true to unix_graph_maybe_cyclic and later run Tarjan's algorithm to group them into SCC. Once we run Tarjan's algorithm, we are 100% sure whether cyclic references exist or not. If there is no cycle, we set false to unix_graph_maybe_cyclic and can skip the entire garbage collection next time. When finalising SCC, we set true to unix_graph_maybe_cyclic if SCC consists of multiple vertices. Even if SCC is a single vertex, a cycle might exist as self-fd passing. Given the corner case is rare, we detect it by checking all edges of the vertex and set true to unix_graph_maybe_cyclic. With this change, __unix_gc() is just a spin_lock() dance in the normal usage. Signed-off-by:
-
Kuniyuki Iwashima authored
Before starting Tarjan's algorithm, we need to mark all vertices as unvisited. We can save this O(n) setup by reserving two special indices (0, 1) and using two variables. The first time we link a vertex to unix_unvisited_vertices, we set unix_vertex_unvisited_index to index. During DFS, we can see that the index of unvisited vertices is the same as unix_vertex_unvisited_index. When we finalise SCC later, we set unix_vertex_grouped_index to each vertex's index. Then, we can know (i) that the vertex is on the stack if the index of a visited vertex is >= 2 and (ii) that it is not on the stack and belongs to a different SCC if the index is unix_vertex_grouped_index. After the whole algorithm, all indices of vertices are set as unix_vertex_grouped_index. Next time we start DFS, we know that all unvisited vertices have unix_vertex_grouped_index, and we can use unix_vertex_unvisited_index as the not-on-stack marker. To use the same variable in __unix_walk_scc(), we can swap unix_vertex_(grouped|unvisited)_index at the end of Tarjan's algorithm. Signed-off-by:
-
