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