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