Documentation/core-api/folio_queue.rst

   1 .. SPDX-License-Identifier: GPL-2.0+
   2
   3 ===========
   4 Folio 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
  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 hese 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         void folioq_mark3(struct folio_queue *folioq, unsigned int slot);
 155
 156 Cleared 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
 162 And 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
 168 The marks can be used for any purpose and are not interpreted by this API.
 169
 170
 171 Folio queue iteration
 172 =====================
 173
 174 A list of segments may be iterated over using the I/O iterator facility using
 175 an ``iov_iter`` iterator of ``ITER_FOLIOQ`` type.  The iterator may be
 176 initialised 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
 183 This may be told to start at a particular segment, slot and offset within a
 184 queue.  The iov iterator functions will follow the next pointers when advancing
 185 and prev pointers when reverting when needed.
 186
 187
 188 Lockless simultaneous production/consumption issues
 189 ===================================================
 190
 191 If properly managed, the list can be extended by the producer at the head end
 192 and shortened by the consumer at the tail end simultaneously without the need
 193 to take locks.  The ITER_FOLIOQ iterator inserts appropriate barriers to aid
 194 with this.
 195
 196 Care must be taken when simultaneously producing and consuming a list.  If the
 197 last segment is reached and the folios it refers to are entirely consumed by
 198 the IOV iterators, an iov_iter struct will be left pointing to the last segment
 199 with a slot number equal to the capacity of that segment.  The iterator will
 200 try to continue on from this if there's another segment available when it is
 201 used again, but care must be taken lest the segment got removed and freed by
 202 the consumer before the iterator was advanced.
 203
 204 It is recommended that the queue always contain at least one segment, even if
 205 that segment has never been filled or is entirely spent.  This prevents the
 206 head and tail pointers from collapsing.
 207
 208
 209 API Function Reference
 210 ======================
 211
 212 .. kernel-doc:: include/linux/folio_queue.h