1The genalloc/genpool subsystem
2==============================
3
4There are a number of memory-allocation subsystems in the kernel, each
5aimed at a specific need.  Sometimes, however, a kernel developer needs to
6implement a new allocator for a specific range of special-purpose memory;
7often that memory is located on a device somewhere.  The author of the
8driver for that device can certainly write a little allocator to get the
9job done, but that is the way to fill the kernel with dozens of poorly
10tested allocators.  Back in 2005, Jes Sorensen lifted one of those
11allocators from the sym53c8xx_2 driver and posted_ it as a generic module
12for the creation of ad hoc memory allocators.  This code was merged
13for the 2.6.13 release; it has been modified considerably since then.
14
15.. _posted: https://lwn.net/Articles/125842/
16
17Code using this allocator should include <linux/genalloc.h>.  The action
18begins 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
26A call to :c:func:`gen_pool_create` will create a pool.  The granularity of
27allocations is set with min_alloc_order; it is a log-base-2 number like
28those used by the page allocator, but it refers to bytes rather than pages.
29So, if min_alloc_order is passed as 3, then all allocations will be a
30multiple of eight bytes.  Increasing min_alloc_order decreases the memory
31required to track the memory in the pool.  The nid parameter specifies
32which NUMA node should be used for the allocation of the housekeeping
33structures; it can be -1 if the caller doesn't care.
34
35The "managed" interface :c:func:`devm_gen_pool_create` ties the pool to a
36specific device.  Among other things, it will automatically clean up the
37pool when the given device is destroyed.
38
39A pool is shut down with:
40
41.. kernel-doc:: lib/genalloc.c
42   :functions: gen_pool_destroy
43
44It's worth noting that, if there are still allocations outstanding from the
45given pool, this function will take the rather extreme step of invoking
46BUG(), crashing the entire system.  You have been warned.
47
48A freshly created pool has no memory to allocate.  It is fairly useless in
49that state, so one of the first orders of business is usually to add memory
50to 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
58A call to :c:func:`gen_pool_add` will place the size bytes of memory
59starting at addr (in the kernel's virtual address space) into the given
60pool, once again using nid as the node ID for ancillary memory allocations.
61The :c:func:`gen_pool_add_virt` variant associates an explicit physical
62address with the memory; this is only necessary if the pool will be used
63for DMA allocations.
64
65The functions for allocating memory from the pool (and putting it back)
66are:
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
77As one would expect, :c:func:`gen_pool_alloc` will allocate size< bytes
78from the given pool.  The :c:func:`gen_pool_dma_alloc` variant allocates
79memory for use with DMA operations, returning the associated physical
80address in the space pointed to by dma.  This will only work if the memory
81was added with :c:func:`gen_pool_add_virt`.  Note that this function
82departs from the usual genpool pattern of using unsigned long values to
83represent kernel addresses; it returns a void * instead.
84
85That all seems relatively simple; indeed, some developers clearly found it
86to be too simple.  After all, the interface above provides no control over
87how the allocation functions choose which specific piece of memory to
88return.  If that sort of control is needed, the following functions will be
89of 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
97Allocations with :c:func:`gen_pool_alloc_algo` specify an algorithm to be
98used to choose the memory to be allocated; the default algorithm can be set
99with :c:func:`gen_pool_set_algo`.  The data value is passed to the
100algorithm; most ignore it, but it is occasionally needed.  One can,
101naturally, write a special-purpose algorithm, but there is a fair set
102already 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
119There is a handful of other functions, mostly for purposes like querying
120the space available in the pool or iterating through chunks of memory.
121Most users, however, should not need much beyond what has been described
122above.  With luck, wider awareness of this module will help to prevent the
123writing 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
145