diff options
author | 2023-02-21 18:24:12 -0800 | |
---|---|---|
committer | 2023-02-21 18:24:12 -0800 | |
commit | 5b7c4cabbb65f5c469464da6c5f614cbd7f730f2 (patch) | |
tree | cc5c2d0a898769fd59549594fedb3ee6f84e59a0 /lib/list-test.c | |
download | linux-5b7c4cabbb65f5c469464da6c5f614cbd7f730f2.tar.gz linux-5b7c4cabbb65f5c469464da6c5f614cbd7f730f2.zip |
Merge tag 'net-next-6.3' of git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net-nextgrafted
Pull networking updates from Jakub Kicinski:
"Core:
- Add dedicated kmem_cache for typical/small skb->head, avoid having
to access struct page at kfree time, and improve memory use.
- Introduce sysctl to set default RPS configuration for new netdevs.
- Define Netlink protocol specification format which can be used to
describe messages used by each family and auto-generate parsers.
Add tools for generating kernel data structures and uAPI headers.
- Expose all net/core sysctls inside netns.
- Remove 4s sleep in netpoll if carrier is instantly detected on
boot.
- Add configurable limit of MDB entries per port, and port-vlan.
- Continue populating drop reasons throughout the stack.
- Retire a handful of legacy Qdiscs and classifiers.
Protocols:
- Support IPv4 big TCP (TSO frames larger than 64kB).
- Add IP_LOCAL_PORT_RANGE socket option, to control local port range
on socket by socket basis.
- Track and report in procfs number of MPTCP sockets used.
- Support mixing IPv4 and IPv6 flows in the in-kernel MPTCP path
manager.
- IPv6: don't check net.ipv6.route.max_size and rely on garbage
collection to free memory (similarly to IPv4).
- Support Penultimate Segment Pop (PSP) flavor in SRv6 (RFC8986).
- ICMP: add per-rate limit counters.
- Add support for user scanning requests in ieee802154.
- Remove static WEP support.
- Support minimal Wi-Fi 7 Extremely High Throughput (EHT) rate
reporting.
- WiFi 7 EHT channel puncturing support (client & AP).
BPF:
- Add a rbtree data structure following the "next-gen data structure"
precedent set by recently added linked list, that is, by using
kfunc + kptr instead of adding a new BPF map type.
- Expose XDP hints via kfuncs with initial support for RX hash and
timestamp metadata.
- Add BPF_F_NO_TUNNEL_KEY extension to bpf_skb_set_tunnel_key to
better support decap on GRE tunnel devices not operating in collect
metadata.
- Improve x86 JIT's codegen for PROBE_MEM runtime error checks.
- Remove the need for trace_printk_lock for bpf_trace_printk and
bpf_trace_vprintk helpers.
- Extend libbpf's bpf_tracing.h support for tracing arguments of
kprobes/uprobes and syscall as a special case.
- Significantly reduce the search time for module symbols by
livepatch and BPF.
- Enable cpumasks to be used as kptrs, which is useful for tracing
programs tracking which tasks end up running on which CPUs in
different time intervals.
- Add support for BPF trampoline on s390x and riscv64.
- Add capability to export the XDP features supported by the NIC.
- Add __bpf_kfunc tag for marking kernel functions as kfuncs.
- Add cgroup.memory=nobpf kernel parameter option to disable BPF
memory accounting for container environments.
Netfilter:
- Remove the CLUSTERIP target. It has been marked as obsolete for
years, and we still have WARN splats wrt races of the out-of-band
/proc interface installed by this target.
- Add 'destroy' commands to nf_tables. They are identical to the
existing 'delete' commands, but do not return an error if the
referenced object (set, chain, rule...) did not exist.
Driver API:
- Improve cpumask_local_spread() locality to help NICs set the right
IRQ affinity on AMD platforms.
- Separate C22 and C45 MDIO bus transactions more clearly.
- Introduce new DCB table to control DSCP rewrite on egress.
- Support configuration of Physical Layer Collision Avoidance (PLCA)
Reconciliation Sublayer (RS) (802.3cg-2019). Modern version of
shared medium Ethernet.
- Support for MAC Merge layer (IEEE 802.3-2018 clause 99). Allowing
preemption of low priority frames by high priority frames.
- Add support for controlling MACSec offload using netlink SET.
- Rework devlink instance refcounts to allow registration and
de-registration under the instance lock. Split the code into
multiple files, drop some of the unnecessarily granular locks and
factor out common parts of netlink operation handling.
- Add TX frame aggregation parameters (for USB drivers).
- Add a new attr TCA_EXT_WARN_MSG to report TC (offload) warning
messages with notifications for debug.
- Allow offloading of UDP NEW connections via act_ct.
- Add support for per action HW stats in TC.
- Support hardware miss to TC action (continue processing in SW from
a specific point in the action chain).
- Warn if old Wireless Extension user space interface is used with
modern cfg80211/mac80211 drivers. Do not support Wireless
Extensions for Wi-Fi 7 devices at all. Everyone should switch to
using nl80211 interface instead.
- Improve the CAN bit timing configuration. Use extack to return
error messages directly to user space, update the SJW handling,
including the definition of a new default value that will benefit
CAN-FD controllers, by increasing their oscillator tolerance.
New hardware / drivers:
- Ethernet:
- nVidia BlueField-3 support (control traffic driver)
- Ethernet support for imx93 SoCs
- Motorcomm yt8531 gigabit Ethernet PHY
- onsemi NCN26000 10BASE-T1S PHY (with support for PLCA)
- Microchip LAN8841 PHY (incl. cable diagnostics and PTP)
- Amlogic gxl MDIO mux
- WiFi:
- RealTek RTL8188EU (rtl8xxxu)
- Qualcomm Wi-Fi 7 devices (ath12k)
- CAN:
- Renesas R-Car V4H
Drivers:
- Bluetooth:
- Set Per Platform Antenna Gain (PPAG) for Intel controllers.
- Ethernet NICs:
- Intel (1G, igc):
- support TSN / Qbv / packet scheduling features of i226 model
- Intel (100G, ice):
- use GNSS subsystem instead of TTY
- multi-buffer XDP support
- extend support for GPIO pins to E823 devices
- nVidia/Mellanox:
- update the shared buffer configuration on PFC commands
- implement PTP adjphase function for HW offset control
- TC support for Geneve and GRE with VF tunnel offload
- more efficient crypto key management method
- multi-port eswitch support
- Netronome/Corigine:
- add DCB IEEE support
- support IPsec offloading for NFP3800
- Freescale/NXP (enetc):
- support XDP_REDIRECT for XDP non-linear buffers
- improve reconfig, avoid link flap and waiting for idle
- support MAC Merge layer
- Other NICs:
- sfc/ef100: add basic devlink support for ef100
- ionic: rx_push mode operation (writing descriptors via MMIO)
- bnxt: use the auxiliary bus abstraction for RDMA
- r8169: disable ASPM and reset bus in case of tx timeout
- cpsw: support QSGMII mode for J721e CPSW9G
- cpts: support pulse-per-second output
- ngbe: add an mdio bus driver
- usbnet: optimize usbnet_bh() by avoiding unnecessary queuing
- r8152: handle devices with FW with NCM support
- amd-xgbe: support 10Mbps, 2.5GbE speeds and rx-adaptation
- virtio-net: support multi buffer XDP
- virtio/vsock: replace virtio_vsock_pkt with sk_buff
- tsnep: XDP support
- Ethernet high-speed switches:
- nVidia/Mellanox (mlxsw):
- add support for latency TLV (in FW control messages)
- Microchip (sparx5):
- separate explicit and implicit traffic forwarding rules, make
the implicit rules always active
- add support for egress DSCP rewrite
- IS0 VCAP support (Ingress Classification)
- IS2 VCAP filters (protos, L3 addrs, L4 ports, flags, ToS
etc.)
- ES2 VCAP support (Egress Access Control)
- support for Per-Stream Filtering and Policing (802.1Q,
8.6.5.1)
- Ethernet embedded switches:
- Marvell (mv88e6xxx):
- add MAB (port auth) offload support
- enable PTP receive for mv88e6390
- NXP (ocelot):
- support MAC Merge layer
- support for the the vsc7512 internal copper phys
- Microchip:
- lan9303: convert to PHYLINK
- lan966x: support TC flower filter statistics
- lan937x: PTP support for KSZ9563/KSZ8563 and LAN937x
- lan937x: support Credit Based Shaper configuration
- ksz9477: support Energy Efficient Ethernet
- other:
- qca8k: convert to regmap read/write API, use bulk operations
- rswitch: Improve TX timestamp accuracy
- Intel WiFi (iwlwifi):
- EHT (Wi-Fi 7) rate reporting
- STEP equalizer support: transfer some STEP (connection to radio
on platforms with integrated wifi) related parameters from the
BIOS to the firmware.
- Qualcomm 802.11ax WiFi (ath11k):
- IPQ5018 support
- Fine Timing Measurement (FTM) responder role support
- channel 177 support
- MediaTek WiFi (mt76):
- per-PHY LED support
- mt7996: EHT (Wi-Fi 7) support
- Wireless Ethernet Dispatch (WED) reset support
- switch to using page pool allocator
- RealTek WiFi (rtw89):
- support new version of Bluetooth co-existance
- Mobile:
- rmnet: support TX aggregation"
* tag 'net-next-6.3' of git://git.kernel.org/pub/scm/linux/kernel/git/netdev/net-next: (1872 commits)
page_pool: add a comment explaining the fragment counter usage
net: ethtool: fix __ethtool_dev_mm_supported() implementation
ethtool: pse-pd: Fix double word in comments
xsk: add linux/vmalloc.h to xsk.c
sefltests: netdevsim: wait for devlink instance after netns removal
selftest: fib_tests: Always cleanup before exit
net/mlx5e: Align IPsec ASO result memory to be as required by hardware
net/mlx5e: TC, Set CT miss to the specific ct action instance
net/mlx5e: Rename CHAIN_TO_REG to MAPPED_OBJ_TO_REG
net/mlx5: Refactor tc miss handling to a single function
net/mlx5: Kconfig: Make tc offload depend on tc skb extension
net/sched: flower: Support hardware miss to tc action
net/sched: flower: Move filter handle initialization earlier
net/sched: cls_api: Support hardware miss to tc action
net/sched: Rename user cookie and act cookie
sfc: fix builds without CONFIG_RTC_LIB
sfc: clean up some inconsistent indentings
net/mlx4_en: Introduce flexible array to silence overflow warning
net: lan966x: Fix possible deadlock inside PTP
net/ulp: Remove redundant ->clone() test in inet_clone_ulp().
...
Diffstat (limited to 'lib/list-test.c')
-rw-r--r-- | lib/list-test.c | 1204 |
1 files changed, 1204 insertions, 0 deletions
diff --git a/lib/list-test.c b/lib/list-test.c new file mode 100644 index 000000000..d374cf5d1 --- /dev/null +++ b/lib/list-test.c @@ -0,0 +1,1204 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * KUnit test for the Kernel Linked-list structures. + * + * Copyright (C) 2019, Google LLC. + * Author: David Gow <davidgow@google.com> + */ +#include <kunit/test.h> + +#include <linux/list.h> + +struct list_test_struct { + int data; + struct list_head list; +}; + +static void list_test_list_init(struct kunit *test) +{ + /* Test the different ways of initialising a list. */ + struct list_head list1 = LIST_HEAD_INIT(list1); + struct list_head list2; + LIST_HEAD(list3); + struct list_head *list4; + struct list_head *list5; + + INIT_LIST_HEAD(&list2); + + list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL); + INIT_LIST_HEAD(list4); + + list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL); + memset(list5, 0xFF, sizeof(*list5)); + INIT_LIST_HEAD(list5); + + /* list_empty_careful() checks both next and prev. */ + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list1)); + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list3)); + KUNIT_EXPECT_TRUE(test, list_empty_careful(list4)); + KUNIT_EXPECT_TRUE(test, list_empty_careful(list5)); + + kfree(list4); + kfree(list5); +} + +static void list_test_list_add(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add(&a, &list); + list_add(&b, &list); + + /* should be [list] -> b -> a */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); + KUNIT_EXPECT_PTR_EQ(test, b.next, &a); +} + +static void list_test_list_add_tail(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* should be [list] -> a -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &a); + KUNIT_EXPECT_PTR_EQ(test, a.prev, &list); + KUNIT_EXPECT_PTR_EQ(test, a.next, &b); +} + +static void list_test_list_del(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a -> b */ + list_del(&a); + + /* now: [list] -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); +} + +static void list_test_list_replace(struct kunit *test) +{ + struct list_head a_old, a_new, b; + LIST_HEAD(list); + + list_add_tail(&a_old, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a_old -> b */ + list_replace(&a_old, &a_new); + + /* now: [list] -> a_new -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); +} + +static void list_test_list_replace_init(struct kunit *test) +{ + struct list_head a_old, a_new, b; + LIST_HEAD(list); + + list_add_tail(&a_old, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a_old -> b */ + list_replace_init(&a_old, &a_new); + + /* now: [list] -> a_new -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); + + /* check a_old is empty (initialized) */ + KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old)); +} + +static void list_test_list_swap(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a -> b */ + list_swap(&a, &b); + + /* after: [list] -> b -> a */ + KUNIT_EXPECT_PTR_EQ(test, &b, list.next); + KUNIT_EXPECT_PTR_EQ(test, &a, list.prev); + + KUNIT_EXPECT_PTR_EQ(test, &a, b.next); + KUNIT_EXPECT_PTR_EQ(test, &list, b.prev); + + KUNIT_EXPECT_PTR_EQ(test, &list, a.next); + KUNIT_EXPECT_PTR_EQ(test, &b, a.prev); +} + +static void list_test_list_del_init(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a -> b */ + list_del_init(&a); + /* after: [list] -> b, a initialised */ + + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); + KUNIT_EXPECT_TRUE(test, list_empty_careful(&a)); +} + +static void list_test_list_del_init_careful(struct kunit *test) +{ + /* NOTE: This test only checks the behaviour of this function in + * isolation. It does not verify memory model guarantees. + */ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a -> b */ + list_del_init_careful(&a); + /* after: [list] -> b, a initialised */ + + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); + KUNIT_EXPECT_TRUE(test, list_empty_careful(&a)); +} + +static void list_test_list_move(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list1); + LIST_HEAD(list2); + + list_add_tail(&a, &list1); + list_add_tail(&b, &list2); + + /* before: [list1] -> a, [list2] -> b */ + list_move(&a, &list2); + /* after: [list1] empty, [list2] -> a -> b */ + + KUNIT_EXPECT_TRUE(test, list_empty(&list1)); + + KUNIT_EXPECT_PTR_EQ(test, &a, list2.next); + KUNIT_EXPECT_PTR_EQ(test, &b, a.next); +} + +static void list_test_list_move_tail(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list1); + LIST_HEAD(list2); + + list_add_tail(&a, &list1); + list_add_tail(&b, &list2); + + /* before: [list1] -> a, [list2] -> b */ + list_move_tail(&a, &list2); + /* after: [list1] empty, [list2] -> b -> a */ + + KUNIT_EXPECT_TRUE(test, list_empty(&list1)); + + KUNIT_EXPECT_PTR_EQ(test, &b, list2.next); + KUNIT_EXPECT_PTR_EQ(test, &a, b.next); +} + +static void list_test_list_bulk_move_tail(struct kunit *test) +{ + struct list_head a, b, c, d, x, y; + struct list_head *list1_values[] = { &x, &b, &c, &y }; + struct list_head *list2_values[] = { &a, &d }; + struct list_head *ptr; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&x, &list1); + list_add_tail(&y, &list1); + + list_add_tail(&a, &list2); + list_add_tail(&b, &list2); + list_add_tail(&c, &list2); + list_add_tail(&d, &list2); + + /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */ + list_bulk_move_tail(&y, &b, &c); + /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */ + + list_for_each(ptr, &list1) { + KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]); + i++; + } + KUNIT_EXPECT_EQ(test, i, 4); + i = 0; + list_for_each(ptr, &list2) { + KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]); + i++; + } + KUNIT_EXPECT_EQ(test, i, 2); +} + +static void list_test_list_is_head(struct kunit *test) +{ + struct list_head a, b, c; + + /* Two lists: [a] -> b, [c] */ + INIT_LIST_HEAD(&a); + INIT_LIST_HEAD(&c); + list_add_tail(&b, &a); + + KUNIT_EXPECT_TRUE_MSG(test, list_is_head(&a, &a), + "Head element of same list"); + KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &b), + "Non-head element of same list"); + KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &c), + "Head element of different list"); +} + + +static void list_test_list_is_first(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list)); + KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list)); +} + +static void list_test_list_is_last(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list)); + KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list)); +} + +static void list_test_list_empty(struct kunit *test) +{ + struct list_head a; + LIST_HEAD(list1); + LIST_HEAD(list2); + + list_add_tail(&a, &list1); + + KUNIT_EXPECT_FALSE(test, list_empty(&list1)); + KUNIT_EXPECT_TRUE(test, list_empty(&list2)); +} + +static void list_test_list_empty_careful(struct kunit *test) +{ + /* This test doesn't check correctness under concurrent access */ + struct list_head a; + LIST_HEAD(list1); + LIST_HEAD(list2); + + list_add_tail(&a, &list1); + + KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1)); + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); +} + +static void list_test_list_rotate_left(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a -> b */ + list_rotate_left(&list); + /* after: [list] -> b -> a */ + + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); + KUNIT_EXPECT_PTR_EQ(test, b.next, &a); +} + +static void list_test_list_rotate_to_front(struct kunit *test) +{ + struct list_head a, b, c, d; + struct list_head *list_values[] = { &c, &d, &a, &b }; + struct list_head *ptr; + LIST_HEAD(list); + int i = 0; + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + list_add_tail(&c, &list); + list_add_tail(&d, &list); + + /* before: [list] -> a -> b -> c -> d */ + list_rotate_to_front(&c, &list); + /* after: [list] -> c -> d -> a -> b */ + + list_for_each(ptr, &list) { + KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]); + i++; + } + KUNIT_EXPECT_EQ(test, i, 4); +} + +static void list_test_list_is_singular(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + /* [list] empty */ + KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); + + list_add_tail(&a, &list); + + /* [list] -> a */ + KUNIT_EXPECT_TRUE(test, list_is_singular(&list)); + + list_add_tail(&b, &list); + + /* [list] -> a -> b */ + KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); +} + +static void list_test_list_cut_position(struct kunit *test) +{ + struct list_head entries[3], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list1); + + /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ + list_cut_position(&list2, &list1, &entries[1]); + /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */ + + list_for_each(cur, &list2) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 2); + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } +} + +static void list_test_list_cut_before(struct kunit *test) +{ + struct list_head entries[3], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list1); + + /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ + list_cut_before(&list2, &list1, &entries[1]); + /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */ + + list_for_each(cur, &list2) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 1); + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } +} + +static void list_test_list_splice(struct kunit *test) +{ + struct list_head entries[5], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list2); + list_add_tail(&entries[3], &list2); + list_add_tail(&entries[4], &list1); + + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ + list_splice(&list2, &entries[1]); + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); +} + +static void list_test_list_splice_tail(struct kunit *test) +{ + struct list_head entries[5], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list2); + list_add_tail(&entries[3], &list2); + list_add_tail(&entries[4], &list1); + + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ + list_splice_tail(&list2, &entries[4]); + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); +} + +static void list_test_list_splice_init(struct kunit *test) +{ + struct list_head entries[5], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list2); + list_add_tail(&entries[3], &list2); + list_add_tail(&entries[4], &list1); + + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ + list_splice_init(&list2, &entries[1]); + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); +} + +static void list_test_list_splice_tail_init(struct kunit *test) +{ + struct list_head entries[5], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list2); + list_add_tail(&entries[3], &list2); + list_add_tail(&entries[4], &list1); + + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ + list_splice_tail_init(&list2, &entries[4]); + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); +} + +static void list_test_list_entry(struct kunit *test) +{ + struct list_test_struct test_struct; + + KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list), + struct list_test_struct, list)); +} + +static void list_test_list_entry_is_head(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2, test_struct3; + + INIT_LIST_HEAD(&test_struct1.list); + INIT_LIST_HEAD(&test_struct3.list); + + list_add_tail(&test_struct2.list, &test_struct1.list); + + KUNIT_EXPECT_TRUE_MSG(test, + list_entry_is_head((&test_struct1), &test_struct1.list, list), + "Head element of same list"); + KUNIT_EXPECT_FALSE_MSG(test, + list_entry_is_head((&test_struct2), &test_struct1.list, list), + "Non-head element of same list"); + KUNIT_EXPECT_FALSE_MSG(test, + list_entry_is_head((&test_struct3), &test_struct1.list, list), + "Head element of different list"); +} + +static void list_test_list_first_entry(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + LIST_HEAD(list); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + + KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list, + struct list_test_struct, list)); +} + +static void list_test_list_last_entry(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + LIST_HEAD(list); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + + KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list, + struct list_test_struct, list)); +} + +static void list_test_list_first_entry_or_null(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + LIST_HEAD(list); + + KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list, + struct list_test_struct, list)); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + KUNIT_EXPECT_PTR_EQ(test, &test_struct1, + list_first_entry_or_null(&list, + struct list_test_struct, list)); +} + +static void list_test_list_next_entry(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + LIST_HEAD(list); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + + KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1, + list)); +} + +static void list_test_list_prev_entry(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + LIST_HEAD(list); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + + KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2, + list)); +} + +static void list_test_list_for_each(struct kunit *test) +{ + struct list_head entries[3], *cur; + LIST_HEAD(list); + int i = 0; + + list_add_tail(&entries[0], &list); + list_add_tail(&entries[1], &list); + list_add_tail(&entries[2], &list); + + list_for_each(cur, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 3); +} + +static void list_test_list_for_each_prev(struct kunit *test) +{ + struct list_head entries[3], *cur; + LIST_HEAD(list); + int i = 2; + + list_add_tail(&entries[0], &list); + list_add_tail(&entries[1], &list); + list_add_tail(&entries[2], &list); + + list_for_each_prev(cur, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i--; + } + + KUNIT_EXPECT_EQ(test, i, -1); +} + +static void list_test_list_for_each_safe(struct kunit *test) +{ + struct list_head entries[3], *cur, *n; + LIST_HEAD(list); + int i = 0; + + + list_add_tail(&entries[0], &list); + list_add_tail(&entries[1], &list); + list_add_tail(&entries[2], &list); + + list_for_each_safe(cur, n, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + list_del(&entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 3); + KUNIT_EXPECT_TRUE(test, list_empty(&list)); +} + +static void list_test_list_for_each_prev_safe(struct kunit *test) +{ + struct list_head entries[3], *cur, *n; + LIST_HEAD(list); + int i = 2; + + list_add_tail(&entries[0], &list); + list_add_tail(&entries[1], &list); + list_add_tail(&entries[2], &list); + + list_for_each_prev_safe(cur, n, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + list_del(&entries[i]); + i--; + } + + KUNIT_EXPECT_EQ(test, i, -1); + KUNIT_EXPECT_TRUE(test, list_empty(&list)); +} + +static void list_test_list_for_each_entry(struct kunit *test) +{ + struct list_test_struct entries[5], *cur; + LIST_HEAD(list); + int i = 0; + + for (i = 0; i < 5; ++i) { + entries[i].data = i; + list_add_tail(&entries[i].list, &list); + } + + i = 0; + + list_for_each_entry(cur, &list, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); +} + +static void list_test_list_for_each_entry_reverse(struct kunit *test) +{ + struct list_test_struct entries[5], *cur; + LIST_HEAD(list); + int i = 0; + + for (i = 0; i < 5; ++i) { + entries[i].data = i; + list_add_tail(&entries[i].list, &list); + } + + i = 4; + + list_for_each_entry_reverse(cur, &list, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + i--; + } + + KUNIT_EXPECT_EQ(test, i, -1); +} + +static struct kunit_case list_test_cases[] = { + KUNIT_CASE(list_test_list_init), + KUNIT_CASE(list_test_list_add), + KUNIT_CASE(list_test_list_add_tail), + KUNIT_CASE(list_test_list_del), + KUNIT_CASE(list_test_list_replace), + KUNIT_CASE(list_test_list_replace_init), + KUNIT_CASE(list_test_list_swap), + KUNIT_CASE(list_test_list_del_init), + KUNIT_CASE(list_test_list_del_init_careful), + KUNIT_CASE(list_test_list_move), + KUNIT_CASE(list_test_list_move_tail), + KUNIT_CASE(list_test_list_bulk_move_tail), + KUNIT_CASE(list_test_list_is_head), + KUNIT_CASE(list_test_list_is_first), + KUNIT_CASE(list_test_list_is_last), + KUNIT_CASE(list_test_list_empty), + KUNIT_CASE(list_test_list_empty_careful), + KUNIT_CASE(list_test_list_rotate_left), + KUNIT_CASE(list_test_list_rotate_to_front), + KUNIT_CASE(list_test_list_is_singular), + KUNIT_CASE(list_test_list_cut_position), + KUNIT_CASE(list_test_list_cut_before), + KUNIT_CASE(list_test_list_splice), + KUNIT_CASE(list_test_list_splice_tail), + KUNIT_CASE(list_test_list_splice_init), + KUNIT_CASE(list_test_list_splice_tail_init), + KUNIT_CASE(list_test_list_entry), + KUNIT_CASE(list_test_list_entry_is_head), + KUNIT_CASE(list_test_list_first_entry), + KUNIT_CASE(list_test_list_last_entry), + KUNIT_CASE(list_test_list_first_entry_or_null), + KUNIT_CASE(list_test_list_next_entry), + KUNIT_CASE(list_test_list_prev_entry), + KUNIT_CASE(list_test_list_for_each), + KUNIT_CASE(list_test_list_for_each_prev), + KUNIT_CASE(list_test_list_for_each_safe), + KUNIT_CASE(list_test_list_for_each_prev_safe), + KUNIT_CASE(list_test_list_for_each_entry), + KUNIT_CASE(list_test_list_for_each_entry_reverse), + {}, +}; + +static struct kunit_suite list_test_module = { + .name = "list-kunit-test", + .test_cases = list_test_cases, +}; + +struct hlist_test_struct { + int data; + struct hlist_node list; +}; + +static void hlist_test_init(struct kunit *test) +{ + /* Test the different ways of initialising a list. */ + struct hlist_head list1 = HLIST_HEAD_INIT; + struct hlist_head list2; + HLIST_HEAD(list3); + struct hlist_head *list4; + struct hlist_head *list5; + + INIT_HLIST_HEAD(&list2); + + list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL); + INIT_HLIST_HEAD(list4); + + list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL); + memset(list5, 0xFF, sizeof(*list5)); + INIT_HLIST_HEAD(list5); + + KUNIT_EXPECT_TRUE(test, hlist_empty(&list1)); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list2)); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list3)); + KUNIT_EXPECT_TRUE(test, hlist_empty(list4)); + KUNIT_EXPECT_TRUE(test, hlist_empty(list5)); + + kfree(list4); + kfree(list5); +} + +static void hlist_test_unhashed(struct kunit *test) +{ + struct hlist_node a; + HLIST_HEAD(list); + + INIT_HLIST_NODE(&a); + + /* is unhashed by default */ + KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a)); + + hlist_add_head(&a, &list); + + /* is hashed once added to list */ + KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a)); + + hlist_del_init(&a); + + /* is again unhashed after del_init */ + KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a)); +} + +/* Doesn't test concurrency guarantees */ +static void hlist_test_unhashed_lockless(struct kunit *test) +{ + struct hlist_node a; + HLIST_HEAD(list); + + INIT_HLIST_NODE(&a); + + /* is unhashed by default */ + KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); + + hlist_add_head(&a, &list); + + /* is hashed once added to list */ + KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a)); + + hlist_del_init(&a); + + /* is again unhashed after del_init */ + KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); +} + +static void hlist_test_del(struct kunit *test) +{ + struct hlist_node a, b; + HLIST_HEAD(list); + + hlist_add_head(&a, &list); + hlist_add_behind(&b, &a); + + /* before: [list] -> a -> b */ + hlist_del(&a); + + /* now: [list] -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.first, &b); + KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first); +} + +static void hlist_test_del_init(struct kunit *test) +{ + struct hlist_node a, b; + HLIST_HEAD(list); + + hlist_add_head(&a, &list); + hlist_add_behind(&b, &a); + + /* before: [list] -> a -> b */ + hlist_del_init(&a); + + /* now: [list] -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.first, &b); + KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first); + + /* a is now initialised */ + KUNIT_EXPECT_PTR_EQ(test, a.next, NULL); + KUNIT_EXPECT_PTR_EQ(test, a.pprev, NULL); +} + +/* Tests all three hlist_add_* functions */ +static void hlist_test_add(struct kunit *test) +{ + struct hlist_node a, b, c, d; + HLIST_HEAD(list); + + hlist_add_head(&a, &list); + hlist_add_head(&b, &list); + hlist_add_before(&c, &a); + hlist_add_behind(&d, &a); + + /* should be [list] -> b -> c -> a -> d */ + KUNIT_EXPECT_PTR_EQ(test, list.first, &b); + + KUNIT_EXPECT_PTR_EQ(test, c.pprev, &(b.next)); + KUNIT_EXPECT_PTR_EQ(test, b.next, &c); + + KUNIT_EXPECT_PTR_EQ(test, a.pprev, &(c.next)); + KUNIT_EXPECT_PTR_EQ(test, c.next, &a); + + KUNIT_EXPECT_PTR_EQ(test, d.pprev, &(a.next)); + KUNIT_EXPECT_PTR_EQ(test, a.next, &d); +} + +/* Tests both hlist_fake() and hlist_add_fake() */ +static void hlist_test_fake(struct kunit *test) +{ + struct hlist_node a; + + INIT_HLIST_NODE(&a); + + /* not fake after init */ + KUNIT_EXPECT_FALSE(test, hlist_fake(&a)); + + hlist_add_fake(&a); + + /* is now fake */ + KUNIT_EXPECT_TRUE(test, hlist_fake(&a)); +} + +static void hlist_test_is_singular_node(struct kunit *test) +{ + struct hlist_node a, b; + HLIST_HEAD(list); + + INIT_HLIST_NODE(&a); + KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list)); + + hlist_add_head(&a, &list); + KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list)); + + hlist_add_head(&b, &list); + KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list)); + KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&b, &list)); +} + +static void hlist_test_empty(struct kunit *test) +{ + struct hlist_node a; + HLIST_HEAD(list); + + /* list starts off empty */ + KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); + + hlist_add_head(&a, &list); + + /* list is no longer empty */ + KUNIT_EXPECT_FALSE(test, hlist_empty(&list)); +} + +static void hlist_test_move_list(struct kunit *test) +{ + struct hlist_node a; + HLIST_HEAD(list1); + HLIST_HEAD(list2); + + hlist_add_head(&a, &list1); + + KUNIT_EXPECT_FALSE(test, hlist_empty(&list1)); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list2)); + hlist_move_list(&list1, &list2); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list1)); + KUNIT_EXPECT_FALSE(test, hlist_empty(&list2)); + +} + +static void hlist_test_entry(struct kunit *test) +{ + struct hlist_test_struct test_struct; + + KUNIT_EXPECT_PTR_EQ(test, &test_struct, + hlist_entry(&(test_struct.list), + struct hlist_test_struct, list)); +} + +static void hlist_test_entry_safe(struct kunit *test) +{ + struct hlist_test_struct test_struct; + + KUNIT_EXPECT_PTR_EQ(test, &test_struct, + hlist_entry_safe(&(test_struct.list), + struct hlist_test_struct, list)); + + KUNIT_EXPECT_PTR_EQ(test, NULL, + hlist_entry_safe((struct hlist_node *)NULL, + struct hlist_test_struct, list)); +} + +static void hlist_test_for_each(struct kunit *test) +{ + struct hlist_node entries[3], *cur; + HLIST_HEAD(list); + int i = 0; + + hlist_add_head(&entries[0], &list); + hlist_add_behind(&entries[1], &entries[0]); + hlist_add_behind(&entries[2], &entries[1]); + + hlist_for_each(cur, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 3); +} + + +static void hlist_test_for_each_safe(struct kunit *test) +{ + struct hlist_node entries[3], *cur, *n; + HLIST_HEAD(list); + int i = 0; + + hlist_add_head(&entries[0], &list); + hlist_add_behind(&entries[1], &entries[0]); + hlist_add_behind(&entries[2], &entries[1]); + + hlist_for_each_safe(cur, n, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + hlist_del(&entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 3); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); +} + +static void hlist_test_for_each_entry(struct kunit *test) +{ + struct hlist_test_struct entries[5], *cur; + HLIST_HEAD(list); + int i = 0; + + entries[0].data = 0; + hlist_add_head(&entries[0].list, &list); + for (i = 1; i < 5; ++i) { + entries[i].data = i; + hlist_add_behind(&entries[i].list, &entries[i-1].list); + } + + i = 0; + + hlist_for_each_entry(cur, &list, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); +} + +static void hlist_test_for_each_entry_continue(struct kunit *test) +{ + struct hlist_test_struct entries[5], *cur; + HLIST_HEAD(list); + int i = 0; + + entries[0].data = 0; + hlist_add_head(&entries[0].list, &list); + for (i = 1; i < 5; ++i) { + entries[i].data = i; + hlist_add_behind(&entries[i].list, &entries[i-1].list); + } + + /* We skip the first (zero-th) entry. */ + i = 1; + + cur = &entries[0]; + hlist_for_each_entry_continue(cur, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + /* Stamp over the entry. */ + cur->data = 42; + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + /* The first entry was not visited. */ + KUNIT_EXPECT_EQ(test, entries[0].data, 0); + /* The second (and presumably others), were. */ + KUNIT_EXPECT_EQ(test, entries[1].data, 42); +} + +static void hlist_test_for_each_entry_from(struct kunit *test) +{ + struct hlist_test_struct entries[5], *cur; + HLIST_HEAD(list); + int i = 0; + + entries[0].data = 0; + hlist_add_head(&entries[0].list, &list); + for (i = 1; i < 5; ++i) { + entries[i].data = i; + hlist_add_behind(&entries[i].list, &entries[i-1].list); + } + + i = 0; + + cur = &entries[0]; + hlist_for_each_entry_from(cur, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + /* Stamp over the entry. */ + cur->data = 42; + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + /* The first entry was visited. */ + KUNIT_EXPECT_EQ(test, entries[0].data, 42); +} + +static void hlist_test_for_each_entry_safe(struct kunit *test) +{ + struct hlist_test_struct entries[5], *cur; + struct hlist_node *tmp_node; + HLIST_HEAD(list); + int i = 0; + + entries[0].data = 0; + hlist_add_head(&entries[0].list, &list); + for (i = 1; i < 5; ++i) { + entries[i].data = i; + hlist_add_behind(&entries[i].list, &entries[i-1].list); + } + + i = 0; + + hlist_for_each_entry_safe(cur, tmp_node, &list, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + hlist_del(&cur->list); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); +} + + +static struct kunit_case hlist_test_cases[] = { + KUNIT_CASE(hlist_test_init), + KUNIT_CASE(hlist_test_unhashed), + KUNIT_CASE(hlist_test_unhashed_lockless), + KUNIT_CASE(hlist_test_del), + KUNIT_CASE(hlist_test_del_init), + KUNIT_CASE(hlist_test_add), + KUNIT_CASE(hlist_test_fake), + KUNIT_CASE(hlist_test_is_singular_node), + KUNIT_CASE(hlist_test_empty), + KUNIT_CASE(hlist_test_move_list), + KUNIT_CASE(hlist_test_entry), + KUNIT_CASE(hlist_test_entry_safe), + KUNIT_CASE(hlist_test_for_each), + KUNIT_CASE(hlist_test_for_each_safe), + KUNIT_CASE(hlist_test_for_each_entry), + KUNIT_CASE(hlist_test_for_each_entry_continue), + KUNIT_CASE(hlist_test_for_each_entry_from), + KUNIT_CASE(hlist_test_for_each_entry_safe), + {}, +}; + +static struct kunit_suite hlist_test_module = { + .name = "hlist", + .test_cases = hlist_test_cases, +}; + +kunit_test_suites(&list_test_module, &hlist_test_module); + +MODULE_LICENSE("GPL v2"); |