• Eric Paris's avatar
    IMA: use rbtree instead of radix tree for inode information cache · 85491641
    Eric Paris authored
    The IMA code needs to store the number of tasks which have an open fd
    granting permission to write a file even when IMA is not in use.  It
    needs this information in order to be enabled at a later point in time
    without losing it's integrity garantees.
    
    At the moment that means we store a little bit of data about every inode
    in a cache.  We use a radix tree key'd on the inode's memory address.
    Dave Chinner pointed out that a radix tree is a terrible data structure
    for such a sparse key space.  This patch switches to using an rbtree
    which should be more efficient.
    
    Bug report from Dave:
    
     "I just noticed that slabtop was reporting an awfully high usage of
      radix tree nodes:
    
       OBJS ACTIVE  USE OBJ SIZE  SLABS OBJ/SLAB CACHE SIZE NAME
      4200331 2778082  66%    0.55K 144839       29   2317424K radix_tree_node
      2321500 2060290  88%    1.00K  72581       32   2322592K xfs_inode
      2235648 2069791  92%    0.12K  69864       32    279456K iint_cache
    
      That is, 2.7M radix tree nodes are allocated, and the cache itself is
      consuming 2.3GB of RAM.  I know that the XFS inodei caches are indexed
      by radix tree node, but for 2 million cached inodes that would mean a
      density of 1 inode per radix tree node, which for a system with 16M
      inodes in the filsystems is an impossibly low density.  The worst I've
      seen in a production system like kernel.org is about 20-25% density,
      which would mean about 150-200k radix tree nodes for that many inodes.
      So it's not the inode cache.
    
      So I looked up what the iint_cache was.  It appears to used for
      storing per-inode IMA information, and uses a radix tree for indexing.
      It uses the *address* of the struct inode as the indexing key.  That
      means the key space is extremely sparse - for XFS the struct inode
      addresses are approximately 1000 bytes apart, which means the closest
      the radix tree index keys get is ~1000.  Which means that there is a
      single entry per radix tree leaf node, so the radix tree is using
      roughly 550 bytes for every 120byte structure being cached.  For the
      above example, it's probably wasting close to 1GB of RAM...."
    Reported-by: default avatarDave Chinner <david@fromorbit.com>
    Signed-off-by: default avatarEric Paris <eparis@redhat.com>
    Acked-by: default avatarMimi Zohar <zohar@linux.vnet.ibm.com>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    85491641
ima_iint.c 4.15 KB