include/linux/folio_queue.h

   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 */