Documentation/core-api/genalloc.rst

   1 The genalloc/genpool subsystem
   2 ==============================
   3
   4 There are a number of memory-allocation subsystems in the kernel, each
   5 aimed at a specific need.  Sometimes, however, a kernel developer needs to
   6 implement a new allocator for a specific range of special-purpose memory;
   7 often that memory is located on a device somewhere.  The author of the
   8 driver for that device can certainly write a little allocator to get the
   9 job done, but that is the way to fill the kernel with dozens of poorly
  10 tested allocators.  Back in 2005, Jes Sorensen lifted one of those
  11 allocators from the sym53c8xx_2 driver and posted_ it as a generic module
  12 for the creation of ad hoc memory allocators.  This code was merged
  13 for the 2.6.13 release; it has been modified considerably since then.
  14
  15 .. _posted: https://lwn.net/Articles/125842/
  16
  17 Code using this allocator should include <linux/genalloc.h>.  The action
  18 begins with the creation of a pool using one of:
  19
  20 .. kernel-doc:: lib/genalloc.c
  21    :functions: gen_pool_create
  22
  23 .. kernel-doc:: lib/genalloc.c
  24    :functions: devm_gen_pool_create
  25
  26 A call to :c:func:`gen_pool_create` will create a pool.  The granularity of
  27 allocations is set with min_alloc_order; it is a log-base-2 number like
  28 those used by the page allocator, but it refers to bytes rather than pages.
  29 So, if min_alloc_order is passed as 3, then all allocations will be a
  30 multiple of eight bytes.  Increasing min_alloc_order decreases the memory
  31 required to track the memory in the pool.  The nid parameter specifies
  32 which NUMA node should be used for the allocation of the housekeeping
  33 structures; it can be -1 if the caller doesn't care.
  34
  35 The "managed" interface :c:func:`devm_gen_pool_create` ties the pool to a
  36 specific device.  Among other things, it will automatically clean up the
  37 pool when the given device is destroyed.
  38
  39 A pool is shut down with:
  40
  41 .. kernel-doc:: lib/genalloc.c
  42    :functions: gen_pool_destroy
  43
  44 It's worth noting that, if there are still allocations outstanding from the
  45 given pool, this function will take the rather extreme step of invoking
  46 BUG(), crashing the entire system.  You have been warned.
  47
  48 A freshly created pool has no memory to allocate.  It is fairly useless in
  49 that state, so one of the first orders of business is usually to add memory
  50 to the pool.  That can be done with one of:
  51
  52 .. kernel-doc:: include/linux/genalloc.h
  53    :functions: gen_pool_add
  54
  55 .. kernel-doc:: lib/genalloc.c
  56    :functions: gen_pool_add_virt
  57
  58 A call to :c:func:`gen_pool_add` will place the size bytes of memory
  59 starting at addr (in the kernel's virtual address space) into the given
  60 pool, once again using nid as the node ID for ancillary memory allocations.
  61 The :c:func:`gen_pool_add_virt` variant associates an explicit physical
  62 address with the memory; this is only necessary if the pool will be used
  63 for DMA allocations.
  64
  65 The functions for allocating memory from the pool (and putting it back)
  66 are:
  67
  68 .. kernel-doc:: lib/genalloc.c
  69    :functions: gen_pool_alloc
  70
  71 .. kernel-doc:: lib/genalloc.c
  72    :functions: gen_pool_dma_alloc
  73
  74 .. kernel-doc:: lib/genalloc.c
  75    :functions: gen_pool_free
  76
  77 As one would expect, :c:func:`gen_pool_alloc` will allocate size< bytes
  78 from the given pool.  The :c:func:`gen_pool_dma_alloc` variant allocates
  79 memory for use with DMA operations, returning the associated physical
  80 address in the space pointed to by dma.  This will only work if the memory
  81 was added with :c:func:`gen_pool_add_virt`.  Note that this function
  82 departs from the usual genpool pattern of using unsigned long values to
  83 represent kernel addresses; it returns a void * instead.
  84
  85 That all seems relatively simple; indeed, some developers clearly found it
  86 to be too simple.  After all, the interface above provides no control over
  87 how the allocation functions choose which specific piece of memory to
  88 return.  If that sort of control is needed, the following functions will be
  89 of interest:
  90
  91 .. kernel-doc:: lib/genalloc.c
  92    :functions: gen_pool_alloc_algo
  93
  94 .. kernel-doc:: lib/genalloc.c
  95    :functions: gen_pool_set_algo
  96
  97 Allocations with :c:func:`gen_pool_alloc_algo` specify an algorithm to be
  98 used to choose the memory to be allocated; the default algorithm can be set
  99 with :c:func:`gen_pool_set_algo`.  The data value is passed to the
 100 algorithm; most ignore it, but it is occasionally needed.  One can,
 101 naturally, write a special-purpose algorithm, but there is a fair set
 102 already available:
 103
 104 - gen_pool_first_fit is a simple first-fit allocator; this is the default
 105   algorithm if none other has been specified.
 106
 107 - gen_pool_first_fit_align forces the allocation to have a specific
 108   alignment (passed via data in a genpool_data_align structure).
 109
 110 - gen_pool_first_fit_order_align aligns the allocation to the order of the
 111   size.  A 60-byte allocation will thus be 64-byte aligned, for example.
 112
 113 - gen_pool_best_fit, as one would expect, is a simple best-fit allocator.
 114
 115 - gen_pool_fixed_alloc allocates at a specific offset (passed in a
 116   genpool_data_fixed structure via the data parameter) within the pool.
 117   If the indicated memory is not available the allocation fails.
 118
 119 There is a handful of other functions, mostly for purposes like querying
 120 the space available in the pool or iterating through chunks of memory.
 121 Most users, however, should not need much beyond what has been described
 122 above.  With luck, wider awareness of this module will help to prevent the
 123 writing of special-purpose memory allocators in the future.
 124
 125 .. kernel-doc:: lib/genalloc.c
 126    :functions: gen_pool_virt_to_phys
 127
 128 .. kernel-doc:: lib/genalloc.c
 129    :functions: gen_pool_for_each_chunk
 130
 131 .. kernel-doc:: lib/genalloc.c
 132    :functions: addr_in_gen_pool
 133
 134 .. kernel-doc:: lib/genalloc.c
 135    :functions: gen_pool_avail
 136
 137 .. kernel-doc:: lib/genalloc.c
 138    :functions: gen_pool_size
 139
 140 .. kernel-doc:: lib/genalloc.c
 141    :functions: gen_pool_get
 142
 143 .. kernel-doc:: lib/genalloc.c
 144    :functions: of_gen_pool_get