1/* SPDX-License-Identifier: GPL-2.0-or-later */
2/* Queue of folios definitions
3 *
4 * Copyright (C) 2024 Red Hat, Inc. All Rights Reserved.
5 * Written by David Howells (dhowells@redhat.com)
6 *
7 * See:
8 *
9 * Documentation/core-api/folio_queue.rst
10 *
11 * for a description of the API.
12 */
13
14#ifndef _LINUX_FOLIO_QUEUE_H
15#define _LINUX_FOLIO_QUEUE_H
16
17#include <linux/pagevec.h>
18#include <linux/mm.h>
19
20/*
21 * Segment in a queue of running buffers. Each segment can hold a number of
22 * folios and a portion of the queue can be referenced with the ITER_FOLIOQ
23 * iterator. The possibility exists of inserting non-folio elements into the
24 * queue (such as gaps).
25 *
26 * Explicit prev and next pointers are used instead of a list_head to make it
27 * easier to add segments to tail and remove them from the head without the
28 * need for a lock.
29 */
30struct folio_queue {
31 struct folio_batch vec; /* Folios in the queue segment */
32 u8 orders[PAGEVEC_SIZE]; /* Order of each folio */
33 struct folio_queue *next; /* Next queue segment or NULL */
34 struct folio_queue *prev; /* Previous queue segment of NULL */
35 unsigned long marks; /* 1-bit mark per folio */
36 unsigned long marks2; /* Second 1-bit mark per folio */
37#if PAGEVEC_SIZE > BITS_PER_LONG
38#error marks is not big enough
39#endif
40 unsigned int rreq_id;
41 unsigned int debug_id;
42};
43
44/**
45 * folioq_init - Initialise a folio queue segment
46 * @folioq: The segment to initialise
47 * @rreq_id: The request identifier to use in tracelines.
48 *
49 * Initialise a folio queue segment and set an identifier to be used in traces.
50 *
51 * Note that the folio pointers are left uninitialised.
52 */
53static inline void folioq_init(struct folio_queue *folioq, unsigned int rreq_id)
54{
55 folio_batch_init(fbatch: &folioq->vec);
56 folioq->next = NULL;
57 folioq->prev = NULL;
58 folioq->marks = 0;
59 folioq->marks2 = 0;
60 folioq->rreq_id = rreq_id;
61 folioq->debug_id = 0;
62}
63
64/**
65 * folioq_nr_slots: Query the capacity of a folio queue segment
66 * @folioq: The segment to query
67 *
68 * Query the number of folios that a particular folio queue segment might hold.
69 * [!] NOTE: This must not be assumed to be the same for every segment!
70 */
71static inline unsigned int folioq_nr_slots(const struct folio_queue *folioq)
72{
73 return PAGEVEC_SIZE;
74}
75
76/**
77 * folioq_count: Query the occupancy of a folio queue segment
78 * @folioq: The segment to query
79 *
80 * Query the number of folios that have been added to a folio queue segment.
81 * Note that this is not decreased as folios are removed from a segment.
82 */
83static inline unsigned int folioq_count(struct folio_queue *folioq)
84{
85 return folio_batch_count(fbatch: &folioq->vec);
86}
87
88/**
89 * folioq_full: Query if a folio queue segment is full
90 * @folioq: The segment to query
91 *
92 * Query if a folio queue segment is fully occupied. Note that this does not
93 * change if folios are removed from a segment.
94 */
95static inline bool folioq_full(struct folio_queue *folioq)
96{
97 //return !folio_batch_space(&folioq->vec);
98 return folioq_count(folioq) >= folioq_nr_slots(folioq);
99}
100
101/**
102 * folioq_is_marked: Check first folio mark in a folio queue segment
103 * @folioq: The segment to query
104 * @slot: The slot number of the folio to query
105 *
106 * Determine if the first mark is set for the folio in the specified slot in a
107 * folio queue segment.
108 */
109static inline bool folioq_is_marked(const struct folio_queue *folioq, unsigned int slot)
110{
111 return test_bit(slot, &folioq->marks);
112}
113
114/**
115 * folioq_mark: Set the first mark on a folio in a folio queue segment
116 * @folioq: The segment to modify
117 * @slot: The slot number of the folio to modify
118 *
119 * Set the first mark for the folio in the specified slot in a folio queue
120 * segment.
121 */
122static inline void folioq_mark(struct folio_queue *folioq, unsigned int slot)
123{
124 set_bit(nr: slot, addr: &folioq->marks);
125}
126
127/**
128 * folioq_unmark: Clear the first mark on a folio in a folio queue segment
129 * @folioq: The segment to modify
130 * @slot: The slot number of the folio to modify
131 *
132 * Clear the first mark for the folio in the specified slot in a folio queue
133 * segment.
134 */
135static inline void folioq_unmark(struct folio_queue *folioq, unsigned int slot)
136{
137 clear_bit(nr: slot, addr: &folioq->marks);
138}
139
140/**
141 * folioq_is_marked2: Check second folio mark in a folio queue segment
142 * @folioq: The segment to query
143 * @slot: The slot number of the folio to query
144 *
145 * Determine if the second mark is set for the folio in the specified slot in a
146 * folio queue segment.
147 */
148static inline bool folioq_is_marked2(const struct folio_queue *folioq, unsigned int slot)
149{
150 return test_bit(slot, &folioq->marks2);
151}
152
153/**
154 * folioq_mark2: Set the second mark on a folio in a folio queue segment
155 * @folioq: The segment to modify
156 * @slot: The slot number of the folio to modify
157 *
158 * Set the second mark for the folio in the specified slot in a folio queue
159 * segment.
160 */
161static inline void folioq_mark2(struct folio_queue *folioq, unsigned int slot)
162{
163 set_bit(nr: slot, addr: &folioq->marks2);
164}
165
166/**
167 * folioq_unmark2: Clear the second mark on a folio in a folio queue segment
168 * @folioq: The segment to modify
169 * @slot: The slot number of the folio to modify
170 *
171 * Clear the second mark for the folio in the specified slot in a folio queue
172 * segment.
173 */
174static inline void folioq_unmark2(struct folio_queue *folioq, unsigned int slot)
175{
176 clear_bit(nr: slot, addr: &folioq->marks2);
177}
178
179/**
180 * folioq_append: Add a folio to a folio queue segment
181 * @folioq: The segment to add to
182 * @folio: The folio to add
183 *
184 * Add a folio to the tail of the sequence in a folio queue segment, increasing
185 * the occupancy count and returning the slot number for the folio just added.
186 * The folio size is extracted and stored in the queue and the marks are left
187 * unmodified.
188 *
189 * Note that it's left up to the caller to check that the segment capacity will
190 * not be exceeded and to extend the queue.
191 */
192static inline unsigned int folioq_append(struct folio_queue *folioq, struct folio *folio)
193{
194 unsigned int slot = folioq->vec.nr++;
195
196 folioq->vec.folios[slot] = folio;
197 folioq->orders[slot] = folio_order(folio);
198 return slot;
199}
200
201/**
202 * folioq_append_mark: Add a folio to a folio queue segment
203 * @folioq: The segment to add to
204 * @folio: The folio to add
205 *
206 * Add a folio to the tail of the sequence in a folio queue segment, increasing
207 * the occupancy count and returning the slot number for the folio just added.
208 * The folio size is extracted and stored in the queue, the first mark is set
209 * and and the second and third marks are left unmodified.
210 *
211 * Note that it's left up to the caller to check that the segment capacity will
212 * not be exceeded and to extend the queue.
213 */
214static inline unsigned int folioq_append_mark(struct folio_queue *folioq, struct folio *folio)
215{
216 unsigned int slot = folioq->vec.nr++;
217
218 folioq->vec.folios[slot] = folio;
219 folioq->orders[slot] = folio_order(folio);
220 folioq_mark(folioq, slot);
221 return slot;
222}
223
224/**
225 * folioq_folio: Get a folio from a folio queue segment
226 * @folioq: The segment to access
227 * @slot: The folio slot to access
228 *
229 * Retrieve the folio in the specified slot from a folio queue segment. Note
230 * that no bounds check is made and if the slot hasn't been added into yet, the
231 * pointer will be undefined. If the slot has been cleared, NULL will be
232 * returned.
233 */
234static inline struct folio *folioq_folio(const struct folio_queue *folioq, unsigned int slot)
235{
236 return folioq->vec.folios[slot];
237}
238
239/**
240 * folioq_folio_order: Get the order of a folio from a folio queue segment
241 * @folioq: The segment to access
242 * @slot: The folio slot to access
243 *
244 * Retrieve the order of the folio in the specified slot from a folio queue
245 * segment. Note that no bounds check is made and if the slot hasn't been
246 * added into yet, the order returned will be 0.
247 */
248static inline unsigned int folioq_folio_order(const struct folio_queue *folioq, unsigned int slot)
249{
250 return folioq->orders[slot];
251}
252
253/**
254 * folioq_folio_size: Get the size of a folio from a folio queue segment
255 * @folioq: The segment to access
256 * @slot: The folio slot to access
257 *
258 * Retrieve the size of the folio in the specified slot from a folio queue
259 * segment. Note that no bounds check is made and if the slot hasn't been
260 * added into yet, the size returned will be PAGE_SIZE.
261 */
262static inline size_t folioq_folio_size(const struct folio_queue *folioq, unsigned int slot)
263{
264 return PAGE_SIZE << folioq_folio_order(folioq, slot);
265}
266
267/**
268 * folioq_clear: Clear a folio from a folio queue segment
269 * @folioq: The segment to clear
270 * @slot: The folio slot to clear
271 *
272 * Clear a folio from a sequence in a folio queue segment and clear its marks.
273 * The occupancy count is left unchanged.
274 */
275static inline void folioq_clear(struct folio_queue *folioq, unsigned int slot)
276{
277 folioq->vec.folios[slot] = NULL;
278 folioq_unmark(folioq, slot);
279 folioq_unmark2(folioq, slot);
280}
281
282#endif /* _LINUX_FOLIO_QUEUE_H */
283