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
19 /*
20 * Segment in a queue of running buffers. Each segment can hold a number of
21 * folios and a portion of the queue can be referenced with the ITER_FOLIOQ
22 * iterator. The possibility exists of inserting non-folio elements into the
23 * queue (such as gaps).
24 *
25 * Explicit prev and next pointers are used instead of a list_head to make it
26 * easier to add segments to tail and remove them from the head without the
27 * need for a lock.
28 */
29 struct folio_queue {
30 struct folio_batch vec; /* Folios in the queue segment */
31 u8 orders[PAGEVEC_SIZE]; /* Order of each folio */
32 struct folio_queue *next; /* Next queue segment or NULL */
33 struct folio_queue *prev; /* Previous queue segment of NULL */
34 unsigned long marks; /* 1-bit mark per folio */
35 unsigned long marks2; /* Second 1-bit mark per folio */
36 unsigned long marks3; /* Third 1-bit mark per folio */
37 #if PAGEVEC_SIZE > BITS_PER_LONG
38 #error marks is not big enough
39 #endif
40 };
41
42 /**
43 * folioq_init - Initialise a folio queue segment
44 * @folioq: The segment to initialise
45 *
46 * Initialise a folio queue segment. Note that the folio pointers are
47 * left uninitialised.
48 */
49 static inline void folioq_init(struct folio_queue *folioq)
50 {
51 folio_batch_init(&folioq->vec);
52 folioq->next = NULL;
53 folioq->prev = NULL;
54 folioq->marks = 0;
55 folioq->marks2 = 0;
56 folioq->marks3 = 0;
57 }
58
59 /**
60 * folioq_nr_slots: Query the capacity of a folio queue segment
61 * @folioq: The segment to query
62 *
63 * Query the number of folios that a particular folio queue segment might hold.
64 * [!] NOTE: This must not be assumed to be the same for every segment!
65 */
66 static inline unsigned int folioq_nr_slots(const struct folio_queue *folioq)
67 {
68 return PAGEVEC_SIZE;
69 }
70
71 /**
72 * folioq_count: Query the occupancy of a folio queue segment
73 * @folioq: The segment to query
74 *
75 * Query the number of folios that have been added to a folio queue segment.
76 * Note that this is not decreased as folios are removed from a segment.
77 */
78 static inline unsigned int folioq_count(struct folio_queue *folioq)
79 {
80 return folio_batch_count(&folioq->vec);
81 }
82
83 /**
84 * folioq_full: Query if a folio queue segment is full
85 * @folioq: The segment to query
86 *
87 * Query if a folio queue segment is fully occupied. Note that this does not
88 * change if folios are removed from a segment.
89 */
90 static inline bool folioq_full(struct folio_queue *folioq)
91 {
92 //return !folio_batch_space(&folioq->vec);
93 return folioq_count(folioq) >= folioq_nr_slots(folioq);
94 }
95
96 /**
97 * folioq_is_marked: Check first folio mark in a folio queue segment
98 * @folioq: The segment to query
99 * @slot: The slot number of the folio to query
100 *
101 * Determine if the first mark is set for the folio in the specified slot in a
102 * folio queue segment.
103 */
104 static inline bool folioq_is_marked(const struct folio_queue *folioq, unsigned int slot)
105 {
106 return test_bit(slot, &folioq->marks);
107 }
108
109 /**
110 * folioq_mark: Set the first mark on a folio in a folio queue segment
111 * @folioq: The segment to modify
112 * @slot: The slot number of the folio to modify
113 *
114 * Set the first mark for the folio in the specified slot in a folio queue
115 * segment.
116 */
117 static inline void folioq_mark(struct folio_queue *folioq, unsigned int slot)
118 {
119 set_bit(slot, &folioq->marks);
120 }
121
122 /**
123 * folioq_unmark: Clear the first mark on a folio in a folio queue segment
124 * @folioq: The segment to modify
125 * @slot: The slot number of the folio to modify
126 *
127 * Clear the first mark for the folio in the specified slot in a folio queue
128 * segment.
129 */
130 static inline void folioq_unmark(struct folio_queue *folioq, unsigned int slot)
131 {
132 clear_bit(slot, &folioq->marks);
133 }
134
135 /**
136 * folioq_is_marked2: Check second folio mark in a folio queue segment
137 * @folioq: The segment to query
138 * @slot: The slot number of the folio to query
139 *
140 * Determine if the second mark is set for the folio in the specified slot in a
141 * folio queue segment.
142 */
143 static inline bool folioq_is_marked2(const struct folio_queue *folioq, unsigned int slot)
144 {
145 return test_bit(slot, &folioq->marks2);
146 }
147
148 /**
149 * folioq_mark2: Set the second mark on a folio in a folio queue segment
150 * @folioq: The segment to modify
151 * @slot: The slot number of the folio to modify
152 *
153 * Set the second mark for the folio in the specified slot in a folio queue
154 * segment.
155 */
156 static inline void folioq_mark2(struct folio_queue *folioq, unsigned int slot)
157 {
158 set_bit(slot, &folioq->marks2);
159 }
160
161 /**
162 * folioq_unmark2: Clear the second mark on a folio in a folio queue segment
163 * @folioq: The segment to modify
164 * @slot: The slot number of the folio to modify
165 *
166 * Clear the second mark for the folio in the specified slot in a folio queue
167 * segment.
168 */
169 static inline void folioq_unmark2(struct folio_queue *folioq, unsigned int slot)
170 {
171 clear_bit(slot, &folioq->marks2);
172 }
173
174 /**
175 * folioq_is_marked3: Check third folio mark in a folio queue segment
176 * @folioq: The segment to query
177 * @slot: The slot number of the folio to query
178 *
179 * Determine if the third mark is set for the folio in the specified slot in a
180 * folio queue segment.
181 */
182 static inline bool folioq_is_marked3(const struct folio_queue *folioq, unsigned int slot)
183 {
184 return test_bit(slot, &folioq->marks3);
185 }
186
187 /**
188 * folioq_mark3: Set the third mark on a folio in a folio queue segment
189 * @folioq: The segment to modify
190 * @slot: The slot number of the folio to modify
191 *
192 * Set the third mark for the folio in the specified slot in a folio queue
193 * segment.
194 */
195 static inline void folioq_mark3(struct folio_queue *folioq, unsigned int slot)
196 {
197 set_bit(slot, &folioq->marks3);
198 }
199
200 /**
201 * folioq_unmark3: Clear the third mark on a folio in a folio queue segment
202 * @folioq: The segment to modify
203 * @slot: The slot number of the folio to modify
204 *
205 * Clear the third mark for the folio in the specified slot in a folio queue
206 * segment.
207 */
208 static inline void folioq_unmark3(struct folio_queue *folioq, unsigned int slot)
209 {
210 clear_bit(slot, &folioq->marks3);
211 }
212
213 static inline unsigned int __folio_order(struct folio *folio)
214 {
215 if (!folio_test_large(folio))
216 return 0;
217 return folio->_flags_1 & 0xff;
218 }
219
220 /**
221 * folioq_append: Add a folio to a folio queue segment
222 * @folioq: The segment to add to
223 * @folio: The folio to add
224 *
225 * Add a folio to the tail of the sequence in a folio queue segment, increasing
226 * the occupancy count and returning the slot number for the folio just added.
227 * The folio size is extracted and stored in the queue and the marks are left
228 * unmodified.
229 *
230 * Note that it's left up to the caller to check that the segment capacity will
231 * not be exceeded and to extend the queue.
232 */
233 static inline unsigned int folioq_append(struct folio_queue *folioq, struct folio *folio)
234 {
235 unsigned int slot = folioq->vec.nr++;
236
237 folioq->vec.folios[slot] = folio;
238 folioq->orders[slot] = __folio_order(folio);
239 return slot;
240 }
241
242 /**
243 * folioq_append_mark: Add a folio to a folio queue segment
244 * @folioq: The segment to add to
245 * @folio: The folio to add
246 *
247 * Add a folio to the tail of the sequence in a folio queue segment, increasing
248 * the occupancy count and returning the slot number for the folio just added.
249 * The folio size is extracted and stored in the queue, the first mark is set
250 * and and the second and third marks are left unmodified.
251 *
252 * Note that it's left up to the caller to check that the segment capacity will
253 * not be exceeded and to extend the queue.
254 */
255 static inline unsigned int folioq_append_mark(struct folio_queue *folioq, struct folio *folio)
256 {
257 unsigned int slot = folioq->vec.nr++;
258
259 folioq->vec.folios[slot] = folio;
260 folioq->orders[slot] = __folio_order(folio);
261 folioq_mark(folioq, slot);
262 return slot;
263 }
264
265 /**
266 * folioq_folio: Get a folio from a folio queue segment
267 * @folioq: The segment to access
268 * @slot: The folio slot to access
269 *
270 * Retrieve the folio in the specified slot from a folio queue segment. Note
271 * that no bounds check is made and if the slot hasn't been added into yet, the
272 * pointer will be undefined. If the slot has been cleared, NULL will be
273 * returned.
274 */
275 static inline struct folio *folioq_folio(const struct folio_queue *folioq, unsigned int slot)
276 {
277 return folioq->vec.folios[slot];
278 }
279
280 /**
281 * folioq_folio_order: Get the order of a folio from a folio queue segment
282 * @folioq: The segment to access
283 * @slot: The folio slot to access
284 *
285 * Retrieve the order of the folio in the specified slot from a folio queue
286 * segment. Note that no bounds check is made and if the slot hasn't been
287 * added into yet, the order returned will be 0.
288 */
289 static inline unsigned int folioq_folio_order(const struct folio_queue *folioq, unsigned int slot)
290 {
291 return folioq->orders[slot];
292 }
293
294 /**
295 * folioq_folio_size: Get the size of a folio from a folio queue segment
296 * @folioq: The segment to access
297 * @slot: The folio slot to access
298 *
299 * Retrieve the size of the folio in the specified slot from a folio queue
300 * segment. Note that no bounds check is made and if the slot hasn't been
301 * added into yet, the size returned will be PAGE_SIZE.
302 */
303 static inline size_t folioq_folio_size(const struct folio_queue *folioq, unsigned int slot)
304 {
305 return PAGE_SIZE << folioq_folio_order(folioq, slot);
306 }
307
308 /**
309 * folioq_clear: Clear a folio from a folio queue segment
310 * @folioq: The segment to clear
311 * @slot: The folio slot to clear
312 *
313 * Clear a folio from a sequence in a folio queue segment and clear its marks.
314 * The occupancy count is left unchanged.
315 */
316 static inline void folioq_clear(struct folio_queue *folioq, unsigned int slot)
317 {
318 folioq->vec.folios[slot] = NULL;
319 folioq_unmark(folioq, slot);
320 folioq_unmark2(folioq, slot);
321 folioq_unmark3(folioq, slot);
322 }
323
324 #endif /* _LINUX_FOLIO_QUEUE_H */
325
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.