| 1 | |
| 2 |
|
| 3 | ===========
|
| 4 | Folio Queue
|
| 5 | ===========
|
| 6 |
|
| 7 | :Author: David Howells <[email protected]>
|
| 8 |
|
| 9 | |
| 10 |
|
| 11 | * Overview
|
| 12 | * Initialisation
|
| 13 | * Adding and removing folios
|
| 14 | * Querying information about a folio
|
| 15 | * Querying information about a folio_queue
|
| 16 | * Folio queue iteration
|
| 17 | * Folio marks
|
| 18 | * Lockless simultaneous production/consumption issues
|
| 19 |
|
| 20 |
|
| 21 | Overview
|
| 22 | ========
|
| 23 |
|
| 24 | The folio_queue struct forms a single segment in a segmented list of folios
|
| 25 | that can be used to form an I/O buffer. As such, the list can be iterated over
|
| 26 | using the ITER_FOLIOQ iov_iter type.
|
| 27 |
|
| 28 | The publicly accessible members of the structure are::
|
| 29 |
|
| 30 | struct folio_queue {
|
| 31 | struct folio_queue *next;
|
| 32 | struct folio_queue *prev;
|
| 33 | ...
|
| 34 | };
|
| 35 |
|
| 36 | A pair of pointers are provided, ``next`` and ``prev``, that point to the
|
| 37 | segments on either side of the segment being accessed. Whilst this is a
|
| 38 | doubly-linked list, it is intentionally not a circular list; the outward
|
| 39 | sibling pointers in terminal segments should be NULL.
|
| 40 |
|
| 41 | Each segment in the list also stores:
|
| 42 |
|
| 43 | * an ordered sequence of folio pointers,
|
| 44 | * the size of each folio and
|
| 45 | * three 1-bit marks per folio,
|
| 46 |
|
| 47 | but these should not be accessed directly as the underlying data structure may
|
| 48 | change, but rather the access functions outlined below should be used.
|
| 49 |
|
| 50 | The facility can be made accessible by::
|
| 51 |
|
| 52 | #include <linux/folio_queue.h>
|
| 53 |
|
| 54 | and to use the iterator::
|
| 55 |
|
| 56 | #include <linux/uio.h>
|
| 57 |
|
| 58 |
|
| 59 | Initialisation
|
| 60 | ==============
|
| 61 |
|
| 62 | A segment should be initialised by calling::
|
| 63 |
|
| 64 | void folioq_init(struct folio_queue *folioq);
|
| 65 |
|
| 66 | with a pointer to the segment to be initialised. Note that this will not
|
| 67 | necessarily initialise all the folio pointers, so care must be taken to check
|
| 68 | the number of folios added.
|
| 69 |
|
| 70 |
|
| 71 | Adding and removing folios
|
| 72 | ==========================
|
| 73 |
|
| 74 | Folios can be set in the next unused slot in a segment struct by calling one
|
| 75 | of::
|
| 76 |
|
| 77 | unsigned int folioq_append(struct folio_queue *folioq,
|
| 78 | struct folio *folio);
|
| 79 |
|
| 80 | unsigned int folioq_append_mark(struct folio_queue *folioq,
|
| 81 | struct folio *folio);
|
| 82 |
|
| 83 | Both functions update the stored folio count, store the folio and note its
|
| 84 | size. The second function also sets the first mark for the folio added. Both
|
| 85 | functions return the number of the slot used. [!] Note that no attempt is made
|
| 86 | to check that the capacity wasn't overrun and the list will not be extended
|
| 87 | automatically.
|
| 88 |
|
| 89 | A folio can be excised by calling::
|
| 90 |
|
| 91 | void folioq_clear(struct folio_queue *folioq, unsigned int slot);
|
| 92 |
|
| 93 | This clears the slot in the array and also clears all the marks for that folio,
|
| 94 | but doesn't change the folio count - so future accesses of that slot must check
|
| 95 | if the slot is occupied.
|
| 96 |
|
| 97 |
|
| 98 | Querying information about a folio
|
| 99 | ==================================
|
| 100 |
|
| 101 | Information about the folio in a particular slot may be queried by the
|
| 102 | following function::
|
| 103 |
|
| 104 | struct folio *folioq_folio(const struct folio_queue *folioq,
|
| 105 | unsigned int slot);
|
| 106 |
|
| 107 | If a folio has not yet been set in that slot, this may yield an undefined
|
| 108 | pointer. The size of the folio in a slot may be queried with either of::
|
| 109 |
|
| 110 | unsigned int folioq_folio_order(const struct folio_queue *folioq,
|
| 111 | unsigned int slot);
|
| 112 |
|
| 113 | size_t folioq_folio_size(const struct folio_queue *folioq,
|
| 114 | unsigned int slot);
|
| 115 |
|
| 116 | The first function returns the size as an order and the second as a number of
|
| 117 | bytes.
|
| 118 |
|
| 119 |
|
| 120 | Querying information about a folio_queue
|
| 121 | ========================================
|
| 122 |
|
| 123 | Information may be retrieved about a particular segment with the following
|
| 124 | functions::
|
| 125 |
|
| 126 | unsigned int folioq_nr_slots(const struct folio_queue *folioq);
|
| 127 |
|
| 128 | unsigned int folioq_count(struct folio_queue *folioq);
|
| 129 |
|
| 130 | bool folioq_full(struct folio_queue *folioq);
|
| 131 |
|
| 132 | The first function returns the maximum capacity of a segment. It must not be
|
| 133 | assumed that this won't vary between segments. The second returns the number
|
| 134 | of folios added to a segments and the third is a shorthand to indicate if the
|
| 135 | segment has been filled to capacity.
|
| 136 |
|
| 137 | Not that the count and fullness are not affected by clearing folios from the
|
| 138 | segment. These are more about indicating how many slots in the array have been
|
| 139 | initialised, and it assumed that slots won't get reused, but rather the segment
|
| 140 | will get discarded as the queue is consumed.
|
| 141 |
|
| 142 |
|
| 143 | Folio marks
|
| 144 | ===========
|
| 145 |
|
| 146 | Folios within a queue can also have marks assigned to them. These marks can be
|
| 147 | used to note information such as if a folio needs folio_put() calling upon it.
|
| 148 | There are three marks available to be set for each folio.
|
| 149 |
|
| 150 | The marks can be set by::
|
| 151 |
|
| 152 | void folioq_mark(struct folio_queue *folioq, unsigned int slot);
|
| 153 | void folioq_mark2(struct folio_queue *folioq, unsigned int slot);
|
| 154 |
|
| 155 | Cleared by::
|
| 156 |
|
| 157 | void folioq_unmark(struct folio_queue *folioq, unsigned int slot);
|
| 158 | void folioq_unmark2(struct folio_queue *folioq, unsigned int slot);
|
| 159 |
|
| 160 | And the marks can be queried by::
|
| 161 |
|
| 162 | bool folioq_is_marked(const struct folio_queue *folioq, unsigned int slot);
|
| 163 | bool folioq_is_marked2(const struct folio_queue *folioq, unsigned int slot);
|
| 164 |
|
| 165 | The marks can be used for any purpose and are not interpreted by this API.
|
| 166 |
|
| 167 |
|
| 168 | Folio queue iteration
|
| 169 | =====================
|
| 170 |
|
| 171 | A list of segments may be iterated over using the I/O iterator facility using
|
| 172 | an ``iov_iter`` iterator of ``ITER_FOLIOQ`` type. The iterator may be
|
| 173 | initialised with::
|
| 174 |
|
| 175 | void iov_iter_folio_queue(struct iov_iter *i, unsigned int direction,
|
| 176 | const struct folio_queue *folioq,
|
| 177 | unsigned int first_slot, unsigned int offset,
|
| 178 | size_t count);
|
| 179 |
|
| 180 | This may be told to start at a particular segment, slot and offset within a
|
| 181 | queue. The iov iterator functions will follow the next pointers when advancing
|
| 182 | and prev pointers when reverting when needed.
|
| 183 |
|
| 184 |
|
| 185 | Lockless simultaneous production/consumption issues
|
| 186 | ===================================================
|
| 187 |
|
| 188 | If properly managed, the list can be extended by the producer at the head end
|
| 189 | and shortened by the consumer at the tail end simultaneously without the need
|
| 190 | to take locks. The ITER_FOLIOQ iterator inserts appropriate barriers to aid
|
| 191 | with this.
|
| 192 |
|
| 193 | Care must be taken when simultaneously producing and consuming a list. If the
|
| 194 | last segment is reached and the folios it refers to are entirely consumed by
|
| 195 | the IOV iterators, an iov_iter struct will be left pointing to the last segment
|
| 196 | with a slot number equal to the capacity of that segment. The iterator will
|
| 197 | try to continue on from this if there's another segment available when it is
|
| 198 | used again, but care must be taken lest the segment got removed and freed by
|
| 199 | the consumer before the iterator was advanced.
|
| 200 |
|
| 201 | It is recommended that the queue always contain at least one segment, even if
|
| 202 | that segment has never been filled or is entirely spent. This prevents the
|
| 203 | head and tail pointers from collapsing.
|
| 204 |
|
| 205 |
|
| 206 | API Function Reference
|
| 207 | ======================
|
| 208 |
|
| 209 | .. kernel-doc:: include/linux/folio_queue.h
|