# git rev-parse -q --verify d1dc87763f406d4e67caf16dbe438a5647692395^{commit} d1dc87763f406d4e67caf16dbe438a5647692395 already have revision, skipping fetch # git checkout -q -f -B kisskb d1dc87763f406d4e67caf16dbe438a5647692395 # git clean -qxdf # < git log -1 # commit d1dc87763f406d4e67caf16dbe438a5647692395 # Author: Stephen Brennan # Date: Thu May 19 09:50:30 2022 +0100 # # assoc_array: Fix BUG_ON during garbage collect # # A rare BUG_ON triggered in assoc_array_gc: # # [3430308.818153] kernel BUG at lib/assoc_array.c:1609! # # Which corresponded to the statement currently at line 1593 upstream: # # BUG_ON(assoc_array_ptr_is_meta(p)); # # Using the data from the core dump, I was able to generate a userspace # reproducer[1] and determine the cause of the bug. # # [1]: https://github.com/brenns10/kernel_stuff/tree/master/assoc_array_gc # # After running the iterator on the entire branch, an internal tree node # looked like the following: # # NODE (nr_leaves_on_branch: 3) # SLOT [0] NODE (2 leaves) # SLOT [1] NODE (1 leaf) # SLOT [2..f] NODE (empty) # # In the userspace reproducer, the pr_devel output when compressing this # node was: # # -- compress node 0x5607cc089380 -- # free=0, leaves=0 # [0] retain node 2/1 [nx 0] # [1] fold node 1/1 [nx 0] # [2] fold node 0/1 [nx 2] # [3] fold node 0/2 [nx 2] # [4] fold node 0/3 [nx 2] # [5] fold node 0/4 [nx 2] # [6] fold node 0/5 [nx 2] # [7] fold node 0/6 [nx 2] # [8] fold node 0/7 [nx 2] # [9] fold node 0/8 [nx 2] # [10] fold node 0/9 [nx 2] # [11] fold node 0/10 [nx 2] # [12] fold node 0/11 [nx 2] # [13] fold node 0/12 [nx 2] # [14] fold node 0/13 [nx 2] # [15] fold node 0/14 [nx 2] # after: 3 # # At slot 0, an internal node with 2 leaves could not be folded into the # node, because there was only one available slot (slot 0). Thus, the # internal node was retained. At slot 1, the node had one leaf, and was # able to be folded in successfully. The remaining nodes had no leaves, # and so were removed. By the end of the compression stage, there were 14 # free slots, and only 3 leaf nodes. The tree was ascended and then its # parent node was compressed. When this node was seen, it could not be # folded, due to the internal node it contained. # # The invariant for compression in this function is: whenever # nr_leaves_on_branch < ASSOC_ARRAY_FAN_OUT, the node should contain all # leaf nodes. The compression step currently cannot guarantee this, given # the corner case shown above. # # To fix this issue, retry compression whenever we have retained a node, # and yet nr_leaves_on_branch < ASSOC_ARRAY_FAN_OUT. This second # compression will then allow the node in slot 1 to be folded in, # satisfying the invariant. Below is the output of the reproducer once the # fix is applied: # # -- compress node 0x560e9c562380 -- # free=0, leaves=0 # [0] retain node 2/1 [nx 0] # [1] fold node 1/1 [nx 0] # [2] fold node 0/1 [nx 2] # [3] fold node 0/2 [nx 2] # [4] fold node 0/3 [nx 2] # [5] fold node 0/4 [nx 2] # [6] fold node 0/5 [nx 2] # [7] fold node 0/6 [nx 2] # [8] fold node 0/7 [nx 2] # [9] fold node 0/8 [nx 2] # [10] fold node 0/9 [nx 2] # [11] fold node 0/10 [nx 2] # [12] fold node 0/11 [nx 2] # [13] fold node 0/12 [nx 2] # [14] fold node 0/13 [nx 2] # [15] fold node 0/14 [nx 2] # internal nodes remain despite enough space, retrying # -- compress node 0x560e9c562380 -- # free=14, leaves=1 # [0] fold node 2/15 [nx 0] # after: 3 # # Changes # ======= # DH: # - Use false instead of 0. # - Reorder the inserted lines in a couple of places to put retained before # next_slot. # # ver #2) # - Fix typo in pr_devel, correct comparison to "<=" # # Fixes: 3cb989501c26 ("Add a generic associative array implementation.") # Cc: # Signed-off-by: Stephen Brennan # Signed-off-by: David Howells # cc: Andrew Morton # cc: keyrings@vger.kernel.org # Link: https://lore.kernel.org/r/20220511225517.407935-1-stephen.s.brennan@oracle.com/ # v1 # Link: https://lore.kernel.org/r/20220512215045.489140-1-stephen.s.brennan@oracle.com/ # v2 # Reviewed-by: Jarkko Sakkinen # Signed-off-by: Linus Torvalds # < /opt/cross/kisskb/korg/gcc-11.1.0-nolibc/x86_64-linux/bin/x86_64-linux-gcc --version # < /opt/cross/kisskb/korg/gcc-11.1.0-nolibc/x86_64-linux/bin/x86_64-linux-ld --version # < git log --format=%s --max-count=1 d1dc87763f406d4e67caf16dbe438a5647692395 # < make -s -j 24 ARCH=x86_64 O=/kisskb/build/linus-rand_x86_64-randconfig_x86_64-gcc11 CROSS_COMPILE=/opt/cross/kisskb/korg/gcc-11.1.0-nolibc/x86_64-linux/bin/x86_64-linux- randconfig WARNING: unmet direct dependencies detected for DRM_DP_AUX_BUS Depends on [n]: HAS_IOMEM [=y] && DRM [=y] && OF [=n] Selected by [y]: - DRM_MSM [=y] && HAS_IOMEM [=y] && DRM [=y] && (ARCH_QCOM || SOC_IMX5 || COMPILE_TEST [=y]) && COMMON_CLK [=y] && IOMMU_SUPPORT [=y] && (QCOM_OCMEM [=n] || QCOM_OCMEM [=n]=n) && (QCOM_LLCC [=n] || QCOM_LLCC [=n]=n) && (QCOM_COMMAND_DB [=n] || QCOM_COMMAND_DB [=n]=n) # Added to kconfig CONFIG_STANDALONE=y # Added to kconfig CONFIG_PREVENT_FIRMWARE_BUILD=y # Added to kconfig CONFIG_CC_STACKPROTECTOR_STRONG=n # Added to kconfig CONFIG_GCC_PLUGINS=n # Added to kconfig CONFIG_GCC_PLUGIN_CYC_COMPLEXITY=n # Added to kconfig CONFIG_GCC_PLUGIN_SANCOV=n # Added to kconfig CONFIG_GCC_PLUGIN_LATENT_ENTROPY=n # Added to kconfig CONFIG_BPF_PRELOAD=n # Added to kconfig # < make -s -j 24 ARCH=x86_64 O=/kisskb/build/linus-rand_x86_64-randconfig_x86_64-gcc11 CROSS_COMPILE=/opt/cross/kisskb/korg/gcc-11.1.0-nolibc/x86_64-linux/bin/x86_64-linux- help # make -s -j 24 ARCH=x86_64 O=/kisskb/build/linus-rand_x86_64-randconfig_x86_64-gcc11 CROSS_COMPILE=/opt/cross/kisskb/korg/gcc-11.1.0-nolibc/x86_64-linux/bin/x86_64-linux- olddefconfig .config:7404:warning: override: reassigning to symbol PREVENT_FIRMWARE_BUILD .config:7409:warning: override: reassigning to symbol GCC_PLUGIN_LATENT_ENTROPY WARNING: unmet direct dependencies detected for DRM_DP_AUX_BUS Depends on [n]: HAS_IOMEM [=y] && DRM [=y] && OF [=n] Selected by [y]: - DRM_MSM [=y] && HAS_IOMEM [=y] && DRM [=y] && (ARCH_QCOM || SOC_IMX5 || COMPILE_TEST [=y]) && COMMON_CLK [=y] && IOMMU_SUPPORT [=y] && (QCOM_OCMEM [=n] || QCOM_OCMEM [=n]=n) && (QCOM_LLCC [=n] || QCOM_LLCC [=n]=n) && (QCOM_COMMAND_DB [=n] || QCOM_COMMAND_DB [=n]=n) # make -s -j 24 ARCH=x86_64 O=/kisskb/build/linus-rand_x86_64-randconfig_x86_64-gcc11 CROSS_COMPILE=/opt/cross/kisskb/korg/gcc-11.1.0-nolibc/x86_64-linux/bin/x86_64-linux- WARNING: unmet direct dependencies detected for DRM_DP_AUX_BUS Depends on [n]: HAS_IOMEM [=y] && DRM [=y] && OF [=n] Selected by [y]: - DRM_MSM [=y] && HAS_IOMEM [=y] && DRM [=y] && (ARCH_QCOM || SOC_IMX5 || COMPILE_TEST [=y]) && COMMON_CLK [=y] && IOMMU_SUPPORT [=y] && (QCOM_OCMEM [=n] || QCOM_OCMEM [=n]=n) && (QCOM_LLCC [=n] || QCOM_LLCC [=n]=n) && (QCOM_COMMAND_DB [=n] || QCOM_COMMAND_DB [=n]=n) WARNING: unmet direct dependencies detected for DRM_DP_AUX_BUS Depends on [n]: HAS_IOMEM [=y] && DRM [=y] && OF [=n] Selected by [y]: - DRM_MSM [=y] && HAS_IOMEM [=y] && DRM [=y] && (ARCH_QCOM || SOC_IMX5 || COMPILE_TEST [=y]) && COMMON_CLK [=y] && IOMMU_SUPPORT [=y] && (QCOM_OCMEM [=n] || QCOM_OCMEM [=n]=n) && (QCOM_LLCC [=n] || QCOM_LLCC [=n]=n) && (QCOM_COMMAND_DB [=n] || QCOM_COMMAND_DB [=n]=n) WARNING: unmet direct dependencies detected for DRM_DP_AUX_BUS Depends on [n]: HAS_IOMEM [=y] && DRM [=y] && OF [=n] Selected by [y]: - DRM_MSM [=y] && HAS_IOMEM [=y] && DRM [=y] && (ARCH_QCOM || SOC_IMX5 || COMPILE_TEST [=y]) && COMMON_CLK [=y] && IOMMU_SUPPORT [=y] && (QCOM_OCMEM [=n] || QCOM_OCMEM [=n]=n) && (QCOM_LLCC [=n] || QCOM_LLCC [=n]=n) && (QCOM_COMMAND_DB [=n] || QCOM_COMMAND_DB [=n]=n) drivers/dma-buf/st-dma-fence.o: warning: objtool: race_signal_callback+0x33: stack state mismatch: cfa1=4+128 cfa2=5+48 /kisskb/src/drivers/infiniband/core/user_mad.c: In function 'ib_umad_write': /kisskb/src/drivers/infiniband/core/user_mad.c:564:50: error: array subscript 'struct ib_rmpp_mad[0]' is partly outside array bounds of 'unsigned char[140]' [-Werror=array-bounds] 564 | hdr_len = ib_get_mad_data_offset(rmpp_mad->mad_hdr.mgmt_class); | ^~ /kisskb/src/drivers/infiniband/core/user_mad.c:509:18: note: referencing an object of size 140 allocated by 'kzalloc.constprop' 509 | packet = kzalloc(sizeof *packet + IB_MGMT_RMPP_HDR, GFP_KERNEL); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /kisskb/src/drivers/infiniband/core/user_mad.c:566:42: error: array subscript 'struct ib_rmpp_mad[0]' is partly outside array bounds of 'unsigned char[140]' [-Werror=array-bounds] 566 | if (ib_is_mad_class_rmpp(rmpp_mad->mad_hdr.mgmt_class) | ^~ /kisskb/src/drivers/infiniband/core/user_mad.c:509:18: note: referencing an object of size 140 allocated by 'kzalloc.constprop' 509 | packet = kzalloc(sizeof *packet + IB_MGMT_RMPP_HDR, GFP_KERNEL); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /kisskb/src/drivers/infiniband/core/user_mad.c:618:25: error: array subscript 'struct ib_rmpp_mad[0]' is partly outside array bounds of 'unsigned char[140]' [-Werror=array-bounds] 618 | rmpp_mad->mad_hdr.tid = *tid; | ^~ /kisskb/src/drivers/infiniband/core/user_mad.c:509:18: note: referencing an object of size 140 allocated by 'kzalloc.constprop' 509 | packet = kzalloc(sizeof *packet + IB_MGMT_RMPP_HDR, GFP_KERNEL); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /kisskb/src/drivers/infiniband/core/user_mad.c:622:44: error: array subscript 'struct ib_rmpp_mad[0]' is partly outside array bounds of 'unsigned char[140]' [-Werror=array-bounds] 622 | && ib_is_mad_class_rmpp(rmpp_mad->mad_hdr.mgmt_class) | ^~ /kisskb/src/drivers/infiniband/core/user_mad.c:509:18: note: referencing an object of size 140 allocated by 'kzalloc.constprop' 509 | packet = kzalloc(sizeof *packet + IB_MGMT_RMPP_HDR, GFP_KERNEL); | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ cc1: all warnings being treated as errors make[4]: *** [/kisskb/src/scripts/Makefile.build:271: drivers/infiniband/core/user_mad.o] Error 1 make[3]: *** [/kisskb/src/scripts/Makefile.build:500: drivers/infiniband/core] Error 2 make[2]: *** [/kisskb/src/scripts/Makefile.build:500: drivers/infiniband] Error 2 make[2]: *** Waiting for unfinished jobs.... make[1]: *** [/kisskb/src/Makefile:1839: drivers] Error 2 make: *** [Makefile:219: __sub-make] Error 2 Command 'make -s -j 24 ARCH=x86_64 O=/kisskb/build/linus-rand_x86_64-randconfig_x86_64-gcc11 CROSS_COMPILE=/opt/cross/kisskb/korg/gcc-11.1.0-nolibc/x86_64-linux/bin/x86_64-linux- ' returned non-zero exit status 2 # rm -rf /kisskb/build/linus-rand_x86_64-randconfig_x86_64-gcc11 # Build took: 0:10:02.974116