• Waiman Long's avatar
    locking/lockdep: Reuse freed chain_hlocks entries · 810507fe
    Waiman Long authored
    Once a lock class is zapped, all the lock chains that include the zapped
    class are essentially useless. The lock_chain structure itself can be
    reused, but not the corresponding chain_hlocks[] entries. Over time,
    we will run out of chain_hlocks entries while there are still plenty
    of other lockdep array entries available.
    
    To fix this imbalance, we have to make chain_hlocks entries reusable
    just like the others. As the freed chain_hlocks entries are in blocks of
    various lengths. A simple bitmap like the one used in the other reusable
    lockdep arrays isn't applicable. Instead the chain_hlocks entries are
    put into bucketed lists (MAX_CHAIN_BUCKETS) of chain blocks.  Bucket 0
    is the variable size bucket which houses chain blocks of size larger than
    MAX_CHAIN_BUCKETS sorted in decreasing size order.  Initially, the whole
    array is in one chain block (the primordial chain block) in bucket 0.
    
    The minimum size of a chain block is 2 chain_hlocks entries. That will
    be the minimum allocation size. In other word, allocation requests
    for one chain_hlocks entry will cause 2-entry block to be returned and
    hence 1 entry will be wasted.
    
    Allocation requests for the chain_hlocks are fulfilled first by looking
    for chain block of matching size. If not found, the first chain block
    from bucket[0] (the largest one) is split. That can cause hlock entries
    fragmentation and reduce allocation efficiency if a chain block of size >
    MAX_CHAIN_BUCKETS is ever zapped and put back to after the primordial
    chain block. So the MAX_CHAIN_BUCKETS must be large enough that this
    should seldom happen.
    
    By reusing the chain_hlocks entries, we are able to handle workloads
    that add and zap a lot of lock classes without the risk of running out
    of chain_hlocks entries as long as the total number of outstanding lock
    classes at any time remain within a reasonable limit.
    
    Two new tracking counters, nr_free_chain_hlocks & nr_large_chain_blocks,
    are added to track the total number of chain_hlocks entries in the
    free bucketed lists and the number of large chain blocks in buckets[0]
    respectively. The nr_free_chain_hlocks replaces nr_chain_hlocks.
    
    The nr_large_chain_blocks counter enables to see if we should increase
    the number of buckets (MAX_CHAIN_BUCKETS) available so as to avoid to
    avoid the fragmentation problem in bucket[0].
    
    An internal nfsd test that ran for more than an hour and kept on
    loading and unloading kernel modules could cause the following message
    to be displayed.
    
      [ 4318.443670] BUG: MAX_LOCKDEP_CHAIN_HLOCKS too low!
    
    The patched kernel was able to complete the test with a lot of free
    chain_hlocks entries to spare:
    
      # cat /proc/lockdep_stats
         :
       dependency chains:                   18867 [max: 65536]
       dependency chain hlocks:             74926 [max: 327680]
       dependency chain hlocks lost:            0
         :
       zapped classes:                       1541
       zapped lock chains:                  56765
       large chain blocks:                      1
    
    By changing MAX_CHAIN_BUCKETS to 3 and add a counter for the size of the
    largest chain block. The system still worked and We got the following
    lockdep_stats data:
    
       dependency chains:                   18601 [max: 65536]
       dependency chain hlocks used:        73133 [max: 327680]
       dependency chain hlocks lost:            0
         :
       zapped classes:                       1541
       zapped lock chains:                  56702
       large chain blocks:                  45165
       large chain block size:              20165
    
    By running the test again, I was indeed able to cause chain_hlocks
    entries to get lost:
    
       dependency chain hlocks used:        74806 [max: 327680]
       dependency chain hlocks lost:          575
         :
       large chain blocks:                  48737
       large chain block size:                  7
    
    Due to the fragmentation, it is possible that the
    "MAX_LOCKDEP_CHAIN_HLOCKS too low!" error can happen even if a lot of
    of chain_hlocks entries appear to be free.
    
    Fortunately, a MAX_CHAIN_BUCKETS value of 16 should be big enough that
    few variable sized chain blocks, other than the initial one, should
    ever be present in bucket 0.
    Suggested-by: default avatarPeter Zijlstra <peterz@infradead.org>
    Signed-off-by: default avatarWaiman Long <longman@redhat.com>
    Signed-off-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
    Link: https://lkml.kernel.org/r/20200206152408.24165-7-longman@redhat.com
    810507fe
lockdep_proc.c 17.8 KB