Overview¶

The folio_queuestructforms a single segment in a segmented list of foliosthat can be used to form an I/O buffer. As such, the list can be iterated overusing the ITER_FOLIOQ iov_iter type.

The publicly accessible members of the structure are:

struct folio_queue {        struct folio_queue *next;        struct folio_queue *prev;        ...};

A pair of pointers are provided,next andprev, that point to thesegments on either side of the segment being accessed. Whilst this is adoubly-linked list, it is intentionally not a circular list; the outwardsibling pointers in terminal segments should be NULL.

Each segment in the list also stores:

• an ordered sequence of folio pointers,

• the size of each folio and

• three 1-bit marks per folio,

but these should not be accessed directly as the underlying data structure maychange, but rather the access functions outlined below should be used.

The facility can be made accessible by:

#include <linux/folio_queue.h>

and to use the iterator:

#include <linux/uio.h>

Initialisation¶

A segment should be initialised by calling:

void folioq_init(struct folio_queue *folioq);

with a pointer to the segment to be initialised. Note that this will notnecessarily initialise all the folio pointers, so care must be taken to checkthe number of folios added.

Adding and removing folios¶

Folios can be set in the next unused slot in a segmentstructby calling oneof:

unsigned int folioq_append(struct folio_queue *folioq,                           struct folio *folio);unsigned int folioq_append_mark(struct folio_queue *folioq,                                struct folio *folio);

Both functions update the stored folio count, store the folio and note itssize. The second function also sets the first mark for the folio added. Bothfunctions return the number of the slot used. [!] Note that no attempt is madeto check that the capacity wasn’t overrun and the list will not be extendedautomatically.

A folio can be excised by calling:

void folioq_clear(struct folio_queue *folioq, unsigned int slot);

This clears the slot in the array and also clears all the marks for that folio,but doesn’t change the folio count - so future accesses of that slot must checkif the slot is occupied.

Querying information about a folio¶

Information about the folio in a particular slot may be queried by thefollowing function:

struct folio *folioq_folio(const struct folio_queue *folioq,                           unsigned int slot);

If a folio has not yet been set in that slot, this may yield an undefinedpointer. The size of the folio in a slot may be queried with either of:

unsigned int folioq_folio_order(const struct folio_queue *folioq,                                unsigned int slot);size_t folioq_folio_size(const struct folio_queue *folioq,                         unsigned int slot);

The first function returns the size as an order and the second as a number ofbytes.

Querying information about a folio_queue¶

Information may be retrieved about a particular segment with the followingfunctions:

unsigned int folioq_nr_slots(const struct folio_queue *folioq);unsigned int folioq_count(struct folio_queue *folioq);bool folioq_full(struct folio_queue *folioq);

The first function returns the maximum capacity of a segment. It must not beassumed that this won’t vary between segments. The second returns the numberof folios added to a segments and the third is a shorthand to indicate if thesegment has been filled to capacity.

Not that the count and fullness are not affected by clearing folios from thesegment. These are more about indicating how many slots in the array have beeninitialised, and it assumed that slots won’t get reused, but rather the segmentwill get discarded as the queue is consumed.

Folio marks¶

Folios within a queue can also have marks assigned to them. These marks can beused to note information such as if a folio needsfolio_put() calling upon it.There are three marks available to be set for each folio.

The marks can be set by:

void folioq_mark(struct folio_queue *folioq, unsigned int slot);void folioq_mark2(struct folio_queue *folioq, unsigned int slot);

Cleared by:

void folioq_unmark(struct folio_queue *folioq, unsigned int slot);void folioq_unmark2(struct folio_queue *folioq, unsigned int slot);

And the marks can be queried by:

bool folioq_is_marked(const struct folio_queue *folioq, unsigned int slot);bool folioq_is_marked2(const struct folio_queue *folioq, unsigned int slot);

The marks can be used for any purpose and are not interpreted by this API.

Folio queue iteration¶

A list of segments may be iterated over using the I/O iterator facility usinganiov_iter iterator ofITER_FOLIOQ type. The iterator may beinitialised with:

void iov_iter_folio_queue(struct iov_iter *i, unsigned int direction,                          const struct folio_queue *folioq,                          unsigned int first_slot, unsigned int offset,                          size_t count);

This may be told to start at a particular segment, slot and offset within aqueue. The iov iterator functions will follow the next pointers when advancingand prev pointers when reverting when needed.

Lockless simultaneous production/consumption issues¶

If properly managed, the list can be extended by the producer at the head endand shortened by the consumer at the tail end simultaneously without the needto take locks. The ITER_FOLIOQ iterator inserts appropriate barriers to aidwith this.

Care must be taken when simultaneously producing and consuming a list. If thelast segment is reached and the folios it refers to are entirely consumed bythe IOV iterators, an iov_iterstructwill be left pointing to the last segmentwith a slot number equal to the capacity of that segment. The iterator willtry to continue on from this if there’s another segment available when it isused again, but care must be taken lest the segment got removed and freed bythe consumer before the iterator was advanced.

It is recommended that the queue always contain at least one segment, even ifthat segment has never been filled or is entirely spent. This prevents thehead and tail pointers from collapsing.

API Function Reference¶

voidfolioq_init(structfolio_queue*folioq,unsignedintrreq_id)¶

Initialise a folio queue segment

unsignedintfolioq_nr_slots(conststructfolio_queue*folioq)¶

Query the capacity of a folio queue segment

unsignedintfolioq_count(structfolio_queue*folioq)¶

Query the occupancy of a folio queue segment

boolfolioq_full(structfolio_queue*folioq)¶

Query if a folio queue segment is full

boolfolioq_is_marked(conststructfolio_queue*folioq,unsignedintslot)¶

Check first folio mark in a folio queue segment

voidfolioq_mark(structfolio_queue*folioq,unsignedintslot)¶

Set the first mark on a folio in a folio queue segment

voidfolioq_unmark(structfolio_queue*folioq,unsignedintslot)¶

Clear the first mark on a folio in a folio queue segment

boolfolioq_is_marked2(conststructfolio_queue*folioq,unsignedintslot)¶

Check second folio mark in a folio queue segment

voidfolioq_mark2(structfolio_queue*folioq,unsignedintslot)¶

Set the second mark on a folio in a folio queue segment

voidfolioq_unmark2(structfolio_queue*folioq,unsignedintslot)¶

Clear the second mark on a folio in a folio queue segment

unsignedintfolioq_append(structfolio_queue*folioq,structfolio*folio)¶

Add a folio to a folio queue segment

unsignedintfolioq_append_mark(structfolio_queue*folioq,structfolio*folio)¶

Add a folio to a folio queue segment

structfolio*folioq_folio(conststructfolio_queue*folioq,unsignedintslot)¶

Get a folio from a folio queue segment

unsignedintfolioq_folio_order(conststructfolio_queue*folioq,unsignedintslot)¶

Get the order of a folio from a folio queue segment

size_tfolioq_folio_size(conststructfolio_queue*folioq,unsignedintslot)¶

Get the size of a folio from a folio queue segment

voidfolioq_clear(structfolio_queue*folioq,unsignedintslot)¶

Clear a folio from a folio queue segment