Folio Queue

Author:

David Howells <dhowells@redhat.com>

Overview

The folio_queue struct forms a single segment in a segmented list of folios that can be used to form an I/O buffer. As such, the list can be iterated over using 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 and prev, that point to the segments on either side of the segment being accessed. Whilst this is a doubly-linked list, it is intentionally not a circular list; the outward sibling 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 hese should not be accessed directly as the underlying data structure may change, 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 not necessarily initialise all the folio pointers, so care must be taken to check the number of folios added.

Adding and removing folios

Folios can be set in the next unused slot in a segment struct by calling one of:

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 its size. The second function also sets the first mark for the folio added. Both functions return the number of the slot used. [!] Note that no attempt is made to check that the capacity wasn’t overrun and the list will not be extended automatically.

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 check if the slot is occupied.

Querying information about a folio

Information about the folio in a particular slot may be queried by the following 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 undefined pointer. 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 of bytes.

Querying information about a folio_queue

Information may be retrieved about a particular segment with the following functions:

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 be assumed that this won’t vary between segments. The second returns the number of folios added to a segments and the third is a shorthand to indicate if the segment has been filled to capacity.

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

Folio marks

Folios within a queue can also have marks assigned to them. These marks can be used to note information such as if a folio needs folio_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);
void folioq_mark3(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);
void folioq_unmark3(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);
bool folioq_is_marked3(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 using an iov_iter iterator of ITER_FOLIOQ type. The iterator may be initialised 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 a queue. The iov iterator functions will follow the next pointers when advancing and 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 end and shortened by the consumer at the tail end simultaneously without the need to take locks. The ITER_FOLIOQ iterator inserts appropriate barriers to aid with this.

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

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

API Function Reference

void folioq_init(struct folio_queue *folioq)

Initialise a folio queue segment

Parameters

struct folio_queue *folioq

The segment to initialise

Description

Initialise a folio queue segment. Note that the folio pointers are left uninitialised.

unsigned int folioq_nr_slots(const struct folio_queue *folioq)

Query the capacity of a folio queue segment

Parameters

const struct folio_queue *folioq

The segment to query

Description

Query the number of folios that a particular folio queue segment might hold. [!] NOTE: This must not be assumed to be the same for every segment!

unsigned int folioq_count(struct folio_queue *folioq)

Query the occupancy of a folio queue segment

Parameters

struct folio_queue *folioq

The segment to query

Description

Query the number of folios that have been added to a folio queue segment. Note that this is not decreased as folios are removed from a segment.

bool folioq_full(struct folio_queue *folioq)

Query if a folio queue segment is full

Parameters

struct folio_queue *folioq

The segment to query

Description

Query if a folio queue segment is fully occupied. Note that this does not change if folios are removed from a segment.

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

Check first folio mark in a folio queue segment

Parameters

const struct folio_queue *folioq

The segment to query

unsigned int slot

The slot number of the folio to query

Description

Determine if the first mark is set for the folio in the specified slot in a folio queue segment.

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

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

Parameters

struct folio_queue *folioq

The segment to modify

unsigned int slot

The slot number of the folio to modify

Description

Set the first mark for the folio in the specified slot in a folio queue segment.

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

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

Parameters

struct folio_queue *folioq

The segment to modify

unsigned int slot

The slot number of the folio to modify

Description

Clear the first mark for the folio in the specified slot in a folio queue segment.

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

Check second folio mark in a folio queue segment

Parameters

const struct folio_queue *folioq

The segment to query

unsigned int slot

The slot number of the folio to query

Description

Determine if the second mark is set for the folio in the specified slot in a folio queue segment.

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

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

Parameters

struct folio_queue *folioq

The segment to modify

unsigned int slot

The slot number of the folio to modify

Description

Set the second mark for the folio in the specified slot in a folio queue segment.

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

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

Parameters

struct folio_queue *folioq

The segment to modify

unsigned int slot

The slot number of the folio to modify

Description

Clear the second mark for the folio in the specified slot in a folio queue segment.

bool folioq_is_marked3(const struct folio_queue *folioq, unsigned int slot)

Check third folio mark in a folio queue segment

Parameters

const struct folio_queue *folioq

The segment to query

unsigned int slot

The slot number of the folio to query

Description

Determine if the third mark is set for the folio in the specified slot in a folio queue segment.

void folioq_mark3(struct folio_queue *folioq, unsigned int slot)

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

Parameters

struct folio_queue *folioq

The segment to modify

unsigned int slot

The slot number of the folio to modify

Description

Set the third mark for the folio in the specified slot in a folio queue segment.

void folioq_unmark3(struct folio_queue *folioq, unsigned int slot)

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

Parameters

struct folio_queue *folioq

The segment to modify

unsigned int slot

The slot number of the folio to modify

Description

Clear the third mark for the folio in the specified slot in a folio queue segment.

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

Add a folio to a folio queue segment

Parameters

struct folio_queue *folioq

The segment to add to

struct folio *folio

The folio to add

Description

Add a folio to the tail of the sequence in a folio queue segment, increasing the occupancy count and returning the slot number for the folio just added. The folio size is extracted and stored in the queue and the marks are left unmodified.

Note that it’s left up to the caller to check that the segment capacity will not be exceeded and to extend the queue.

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

Add a folio to a folio queue segment

Parameters

struct folio_queue *folioq

The segment to add to

struct folio *folio

The folio to add

Description

Add a folio to the tail of the sequence in a folio queue segment, increasing the occupancy count and returning the slot number for the folio just added. The folio size is extracted and stored in the queue, the first mark is set and and the second and third marks are left unmodified.

Note that it’s left up to the caller to check that the segment capacity will not be exceeded and to extend the queue.

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

Get a folio from a folio queue segment

Parameters

const struct folio_queue *folioq

The segment to access

unsigned int slot

The folio slot to access

Description

Retrieve the folio in the specified slot from a folio queue segment. Note that no bounds check is made and if the slot hasn’t been added into yet, the pointer will be undefined. If the slot has been cleared, NULL will be returned.

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

Get the order of a folio from a folio queue segment

Parameters

const struct folio_queue *folioq

The segment to access

unsigned int slot

The folio slot to access

Description

Retrieve the order of the folio in the specified slot from a folio queue segment. Note that no bounds check is made and if the slot hasn’t been added into yet, the order returned will be 0.

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

Get the size of a folio from a folio queue segment

Parameters

const struct folio_queue *folioq

The segment to access

unsigned int slot

The folio slot to access

Description

Retrieve the size of the folio in the specified slot from a folio queue segment. Note that no bounds check is made and if the slot hasn’t been added into yet, the size returned will be PAGE_SIZE.

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

Clear a folio from a folio queue segment

Parameters

struct folio_queue *folioq

The segment to clear

unsigned int slot

The folio slot to clear

Description

Clear a folio from a sequence in a folio queue segment and clear its marks. The occupancy count is left unchanged.