• Thomas Gleixner's avatar
    genirq: Implement bitmap matrix allocator · 2f75d9e1
    Thomas Gleixner authored
    Implement the infrastructure for a simple bitmap based allocator, which
    will replace the x86 vector allocator. It's in the core code as other
    architectures might be able to reuse/extend it. For now it only implements
    allocations for single CPUs, but it's simple to add multi CPU allocation
    support if required.
    
    The concept is rather simple:
    
     Global information:
     	system_vector bitmap
    	global accounting
    
     PerCPU information:
     	allocation bitmap
    	managed allocation bitmap
    	local accounting
    
    The system vector bitmap is used to exclude vectors system wide from the
    allocation space.
    
    The allocation bitmap is used to keep track of per cpu used vectors.
    
    The managed allocation bitmap is used to reserve vectors for managed
    interrupts.
    
    When a regular (non managed) interrupt allocation happens then the
    following rule applies:
    
          tmpmap = system_map | alloc_map | managed_map
          find_zero_bit(tmpmap)
    
    Oring the bitmaps together gives the real available space. The same rule
    applies for reserving a managed interrupt vector. But contrary to the
    regular interrupts the reservation only marks the bit in the managed map
    and therefor excludes it from the regular allocations. The managed map is
    only cleaned out when the a managed interrupt is completely released and it
    stays alive accross CPU offline/online operations.
    
    For managed interrupt allocations the rule is:
    
          tmpmap = managed_map & ~alloc_map
          find_first_bit(tmpmap)
    
    This returns the first bit which is in the managed map, but not yet
    allocated in the allocation map. The allocation marks it in the allocation
    map and hands it back to the caller for use.
    
    The rest of the code are helper functions to handle the various
    requirements and the accounting which are necessary to replace the x86
    vector allocation code. The result is a single patch as the evolution of
    this infrastructure cannot be represented in bits and pieces.
    Signed-off-by: default avatarThomas Gleixner <tglx@linutronix.de>
    Tested-by: default avatarJuergen Gross <jgross@suse.com>
    Tested-by: default avatarYu Chen <yu.c.chen@intel.com>
    Acked-by: default avatarJuergen Gross <jgross@suse.com>
    Cc: Boris Ostrovsky <boris.ostrovsky@oracle.com>
    Cc: Tony Luck <tony.luck@intel.com>
    Cc: Marc Zyngier <marc.zyngier@arm.com>
    Cc: Alok Kataria <akataria@vmware.com>
    Cc: Joerg Roedel <joro@8bytes.org>
    Cc: "Rafael J. Wysocki" <rjw@rjwysocki.net>
    Cc: Steven Rostedt <rostedt@goodmis.org>
    Cc: Christoph Hellwig <hch@lst.de>
    Cc: Peter Zijlstra <peterz@infradead.org>
    Cc: Borislav Petkov <bp@alien8.de>
    Cc: Paolo Bonzini <pbonzini@redhat.com>
    Cc: Rui Zhang <rui.zhang@intel.com>
    Cc: "K. Y. Srinivasan" <kys@microsoft.com>
    Cc: Arjan van de Ven <arjan@linux.intel.com>
    Cc: Dan Williams <dan.j.williams@intel.com>
    Cc: Chris Metcalf <cmetcalf@mellanox.com>
    Cc: Len Brown <lenb@kernel.org>
    Link: https://lkml.kernel.org/r/20170913213153.185437174@linutronix.de
    2f75d9e1
matrix.c 11.2 KB