1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * Copyright (c) 2006-2007 Silicon Graphics, Inc. |
4 | * All Rights Reserved. |
5 | */ |
6 | #include "xfs.h" |
7 | #include "xfs_mru_cache.h" |
8 | |
9 | /* |
10 | * The MRU Cache data structure consists of a data store, an array of lists and |
11 | * a lock to protect its internal state. At initialisation time, the client |
12 | * supplies an element lifetime in milliseconds and a group count, as well as a |
13 | * function pointer to call when deleting elements. A data structure for |
14 | * queueing up work in the form of timed callbacks is also included. |
15 | * |
16 | * The group count controls how many lists are created, and thereby how finely |
17 | * the elements are grouped in time. When reaping occurs, all the elements in |
18 | * all the lists whose time has expired are deleted. |
19 | * |
20 | * To give an example of how this works in practice, consider a client that |
21 | * initialises an MRU Cache with a lifetime of ten seconds and a group count of |
22 | * five. Five internal lists will be created, each representing a two second |
23 | * period in time. When the first element is added, time zero for the data |
24 | * structure is initialised to the current time. |
25 | * |
26 | * All the elements added in the first two seconds are appended to the first |
27 | * list. Elements added in the third second go into the second list, and so on. |
28 | * If an element is accessed at any point, it is removed from its list and |
29 | * inserted at the head of the current most-recently-used list. |
30 | * |
31 | * The reaper function will have nothing to do until at least twelve seconds |
32 | * have elapsed since the first element was added. The reason for this is that |
33 | * if it were called at t=11s, there could be elements in the first list that |
34 | * have only been inactive for nine seconds, so it still does nothing. If it is |
35 | * called anywhere between t=12 and t=14 seconds, it will delete all the |
36 | * elements that remain in the first list. It's therefore possible for elements |
37 | * to remain in the data store even after they've been inactive for up to |
38 | * (t + t/g) seconds, where t is the inactive element lifetime and g is the |
39 | * number of groups. |
40 | * |
41 | * The above example assumes that the reaper function gets called at least once |
42 | * every (t/g) seconds. If it is called less frequently, unused elements will |
43 | * accumulate in the reap list until the reaper function is eventually called. |
44 | * The current implementation uses work queue callbacks to carefully time the |
45 | * reaper function calls, so this should happen rarely, if at all. |
46 | * |
47 | * From a design perspective, the primary reason for the choice of a list array |
48 | * representing discrete time intervals is that it's only practical to reap |
49 | * expired elements in groups of some appreciable size. This automatically |
50 | * introduces a granularity to element lifetimes, so there's no point storing an |
51 | * individual timeout with each element that specifies a more precise reap time. |
52 | * The bonus is a saving of sizeof(long) bytes of memory per element stored. |
53 | * |
54 | * The elements could have been stored in just one list, but an array of |
55 | * counters or pointers would need to be maintained to allow them to be divided |
56 | * up into discrete time groups. More critically, the process of touching or |
57 | * removing an element would involve walking large portions of the entire list, |
58 | * which would have a detrimental effect on performance. The additional memory |
59 | * requirement for the array of list heads is minimal. |
60 | * |
61 | * When an element is touched or deleted, it needs to be removed from its |
62 | * current list. Doubly linked lists are used to make the list maintenance |
63 | * portion of these operations O(1). Since reaper timing can be imprecise, |
64 | * inserts and lookups can occur when there are no free lists available. When |
65 | * this happens, all the elements on the LRU list need to be migrated to the end |
66 | * of the reap list. To keep the list maintenance portion of these operations |
67 | * O(1) also, list tails need to be accessible without walking the entire list. |
68 | * This is the reason why doubly linked list heads are used. |
69 | */ |
70 | |
71 | /* |
72 | * An MRU Cache is a dynamic data structure that stores its elements in a way |
73 | * that allows efficient lookups, but also groups them into discrete time |
74 | * intervals based on insertion time. This allows elements to be efficiently |
75 | * and automatically reaped after a fixed period of inactivity. |
76 | * |
77 | * When a client data pointer is stored in the MRU Cache it needs to be added to |
78 | * both the data store and to one of the lists. It must also be possible to |
79 | * access each of these entries via the other, i.e. to: |
80 | * |
81 | * a) Walk a list, removing the corresponding data store entry for each item. |
82 | * b) Look up a data store entry, then access its list entry directly. |
83 | * |
84 | * To achieve both of these goals, each entry must contain both a list entry and |
85 | * a key, in addition to the user's data pointer. Note that it's not a good |
86 | * idea to have the client embed one of these structures at the top of their own |
87 | * data structure, because inserting the same item more than once would most |
88 | * likely result in a loop in one of the lists. That's a sure-fire recipe for |
89 | * an infinite loop in the code. |
90 | */ |
91 | struct xfs_mru_cache { |
92 | struct radix_tree_root store; /* Core storage data structure. */ |
93 | struct list_head *lists; /* Array of lists, one per grp. */ |
94 | struct list_head reap_list; /* Elements overdue for reaping. */ |
95 | spinlock_t lock; /* Lock to protect this struct. */ |
96 | unsigned int grp_count; /* Number of discrete groups. */ |
97 | unsigned int grp_time; /* Time period spanned by grps. */ |
98 | unsigned int lru_grp; /* Group containing time zero. */ |
99 | unsigned long time_zero; /* Time first element was added. */ |
100 | xfs_mru_cache_free_func_t free_func; /* Function pointer for freeing. */ |
101 | struct delayed_work work; /* Workqueue data for reaping. */ |
102 | unsigned int queued; /* work has been queued */ |
103 | void *data; |
104 | }; |
105 | |
106 | static struct workqueue_struct *xfs_mru_reap_wq; |
107 | |
108 | /* |
109 | * When inserting, destroying or reaping, it's first necessary to update the |
110 | * lists relative to a particular time. In the case of destroying, that time |
111 | * will be well in the future to ensure that all items are moved to the reap |
112 | * list. In all other cases though, the time will be the current time. |
113 | * |
114 | * This function enters a loop, moving the contents of the LRU list to the reap |
115 | * list again and again until either a) the lists are all empty, or b) time zero |
116 | * has been advanced sufficiently to be within the immediate element lifetime. |
117 | * |
118 | * Case a) above is detected by counting how many groups are migrated and |
119 | * stopping when they've all been moved. Case b) is detected by monitoring the |
120 | * time_zero field, which is updated as each group is migrated. |
121 | * |
122 | * The return value is the earliest time that more migration could be needed, or |
123 | * zero if there's no need to schedule more work because the lists are empty. |
124 | */ |
125 | STATIC unsigned long |
126 | _xfs_mru_cache_migrate( |
127 | struct xfs_mru_cache *mru, |
128 | unsigned long now) |
129 | { |
130 | unsigned int grp; |
131 | unsigned int migrated = 0; |
132 | struct list_head *lru_list; |
133 | |
134 | /* Nothing to do if the data store is empty. */ |
135 | if (!mru->time_zero) |
136 | return 0; |
137 | |
138 | /* While time zero is older than the time spanned by all the lists. */ |
139 | while (mru->time_zero <= now - mru->grp_count * mru->grp_time) { |
140 | |
141 | /* |
142 | * If the LRU list isn't empty, migrate its elements to the tail |
143 | * of the reap list. |
144 | */ |
145 | lru_list = mru->lists + mru->lru_grp; |
146 | if (!list_empty(head: lru_list)) |
147 | list_splice_init(list: lru_list, head: mru->reap_list.prev); |
148 | |
149 | /* |
150 | * Advance the LRU group number, freeing the old LRU list to |
151 | * become the new MRU list; advance time zero accordingly. |
152 | */ |
153 | mru->lru_grp = (mru->lru_grp + 1) % mru->grp_count; |
154 | mru->time_zero += mru->grp_time; |
155 | |
156 | /* |
157 | * If reaping is so far behind that all the elements on all the |
158 | * lists have been migrated to the reap list, it's now empty. |
159 | */ |
160 | if (++migrated == mru->grp_count) { |
161 | mru->lru_grp = 0; |
162 | mru->time_zero = 0; |
163 | return 0; |
164 | } |
165 | } |
166 | |
167 | /* Find the first non-empty list from the LRU end. */ |
168 | for (grp = 0; grp < mru->grp_count; grp++) { |
169 | |
170 | /* Check the grp'th list from the LRU end. */ |
171 | lru_list = mru->lists + ((mru->lru_grp + grp) % mru->grp_count); |
172 | if (!list_empty(head: lru_list)) |
173 | return mru->time_zero + |
174 | (mru->grp_count + grp) * mru->grp_time; |
175 | } |
176 | |
177 | /* All the lists must be empty. */ |
178 | mru->lru_grp = 0; |
179 | mru->time_zero = 0; |
180 | return 0; |
181 | } |
182 | |
183 | /* |
184 | * When inserting or doing a lookup, an element needs to be inserted into the |
185 | * MRU list. The lists must be migrated first to ensure that they're |
186 | * up-to-date, otherwise the new element could be given a shorter lifetime in |
187 | * the cache than it should. |
188 | */ |
189 | STATIC void |
190 | _xfs_mru_cache_list_insert( |
191 | struct xfs_mru_cache *mru, |
192 | struct xfs_mru_cache_elem *elem) |
193 | { |
194 | unsigned int grp = 0; |
195 | unsigned long now = jiffies; |
196 | |
197 | /* |
198 | * If the data store is empty, initialise time zero, leave grp set to |
199 | * zero and start the work queue timer if necessary. Otherwise, set grp |
200 | * to the number of group times that have elapsed since time zero. |
201 | */ |
202 | if (!_xfs_mru_cache_migrate(mru, now)) { |
203 | mru->time_zero = now; |
204 | if (!mru->queued) { |
205 | mru->queued = 1; |
206 | queue_delayed_work(wq: xfs_mru_reap_wq, dwork: &mru->work, |
207 | delay: mru->grp_count * mru->grp_time); |
208 | } |
209 | } else { |
210 | grp = (now - mru->time_zero) / mru->grp_time; |
211 | grp = (mru->lru_grp + grp) % mru->grp_count; |
212 | } |
213 | |
214 | /* Insert the element at the tail of the corresponding list. */ |
215 | list_add_tail(new: &elem->list_node, head: mru->lists + grp); |
216 | } |
217 | |
218 | /* |
219 | * When destroying or reaping, all the elements that were migrated to the reap |
220 | * list need to be deleted. For each element this involves removing it from the |
221 | * data store, removing it from the reap list, calling the client's free |
222 | * function and deleting the element from the element cache. |
223 | * |
224 | * We get called holding the mru->lock, which we drop and then reacquire. |
225 | * Sparse need special help with this to tell it we know what we are doing. |
226 | */ |
227 | STATIC void |
228 | _xfs_mru_cache_clear_reap_list( |
229 | struct xfs_mru_cache *mru) |
230 | __releases(mru->lock) __acquires(mru->lock) |
231 | { |
232 | struct xfs_mru_cache_elem *elem, *next; |
233 | struct list_head tmp; |
234 | |
235 | INIT_LIST_HEAD(list: &tmp); |
236 | list_for_each_entry_safe(elem, next, &mru->reap_list, list_node) { |
237 | |
238 | /* Remove the element from the data store. */ |
239 | radix_tree_delete(&mru->store, elem->key); |
240 | |
241 | /* |
242 | * remove to temp list so it can be freed without |
243 | * needing to hold the lock |
244 | */ |
245 | list_move(list: &elem->list_node, head: &tmp); |
246 | } |
247 | spin_unlock(lock: &mru->lock); |
248 | |
249 | list_for_each_entry_safe(elem, next, &tmp, list_node) { |
250 | list_del_init(entry: &elem->list_node); |
251 | mru->free_func(mru->data, elem); |
252 | } |
253 | |
254 | spin_lock(lock: &mru->lock); |
255 | } |
256 | |
257 | /* |
258 | * We fire the reap timer every group expiry interval so |
259 | * we always have a reaper ready to run. This makes shutdown |
260 | * and flushing of the reaper easy to do. Hence we need to |
261 | * keep when the next reap must occur so we can determine |
262 | * at each interval whether there is anything we need to do. |
263 | */ |
264 | STATIC void |
265 | _xfs_mru_cache_reap( |
266 | struct work_struct *work) |
267 | { |
268 | struct xfs_mru_cache *mru = |
269 | container_of(work, struct xfs_mru_cache, work.work); |
270 | unsigned long now, next; |
271 | |
272 | ASSERT(mru && mru->lists); |
273 | if (!mru || !mru->lists) |
274 | return; |
275 | |
276 | spin_lock(lock: &mru->lock); |
277 | next = _xfs_mru_cache_migrate(mru, now: jiffies); |
278 | _xfs_mru_cache_clear_reap_list(mru); |
279 | |
280 | mru->queued = next; |
281 | if ((mru->queued > 0)) { |
282 | now = jiffies; |
283 | if (next <= now) |
284 | next = 0; |
285 | else |
286 | next -= now; |
287 | queue_delayed_work(wq: xfs_mru_reap_wq, dwork: &mru->work, delay: next); |
288 | } |
289 | |
290 | spin_unlock(lock: &mru->lock); |
291 | } |
292 | |
293 | int |
294 | xfs_mru_cache_init(void) |
295 | { |
296 | xfs_mru_reap_wq = alloc_workqueue(fmt: "xfs_mru_cache" , |
297 | XFS_WQFLAGS(WQ_MEM_RECLAIM | WQ_FREEZABLE), max_active: 1); |
298 | if (!xfs_mru_reap_wq) |
299 | return -ENOMEM; |
300 | return 0; |
301 | } |
302 | |
303 | void |
304 | xfs_mru_cache_uninit(void) |
305 | { |
306 | destroy_workqueue(wq: xfs_mru_reap_wq); |
307 | } |
308 | |
309 | /* |
310 | * To initialise a struct xfs_mru_cache pointer, call xfs_mru_cache_create() |
311 | * with the address of the pointer, a lifetime value in milliseconds, a group |
312 | * count and a free function to use when deleting elements. This function |
313 | * returns 0 if the initialisation was successful. |
314 | */ |
315 | int |
316 | xfs_mru_cache_create( |
317 | struct xfs_mru_cache **mrup, |
318 | void *data, |
319 | unsigned int lifetime_ms, |
320 | unsigned int grp_count, |
321 | xfs_mru_cache_free_func_t free_func) |
322 | { |
323 | struct xfs_mru_cache *mru = NULL; |
324 | int err = 0, grp; |
325 | unsigned int grp_time; |
326 | |
327 | if (mrup) |
328 | *mrup = NULL; |
329 | |
330 | if (!mrup || !grp_count || !lifetime_ms || !free_func) |
331 | return -EINVAL; |
332 | |
333 | if (!(grp_time = msecs_to_jiffies(m: lifetime_ms) / grp_count)) |
334 | return -EINVAL; |
335 | |
336 | mru = kzalloc(size: sizeof(*mru), GFP_KERNEL | __GFP_NOFAIL); |
337 | if (!mru) |
338 | return -ENOMEM; |
339 | |
340 | /* An extra list is needed to avoid reaping up to a grp_time early. */ |
341 | mru->grp_count = grp_count + 1; |
342 | mru->lists = kzalloc(size: mru->grp_count * sizeof(*mru->lists), |
343 | GFP_KERNEL | __GFP_NOFAIL); |
344 | if (!mru->lists) { |
345 | err = -ENOMEM; |
346 | goto exit; |
347 | } |
348 | |
349 | for (grp = 0; grp < mru->grp_count; grp++) |
350 | INIT_LIST_HEAD(list: mru->lists + grp); |
351 | |
352 | /* |
353 | * We use GFP_KERNEL radix tree preload and do inserts under a |
354 | * spinlock so GFP_ATOMIC is appropriate for the radix tree itself. |
355 | */ |
356 | INIT_RADIX_TREE(&mru->store, GFP_ATOMIC); |
357 | INIT_LIST_HEAD(list: &mru->reap_list); |
358 | spin_lock_init(&mru->lock); |
359 | INIT_DELAYED_WORK(&mru->work, _xfs_mru_cache_reap); |
360 | |
361 | mru->grp_time = grp_time; |
362 | mru->free_func = free_func; |
363 | mru->data = data; |
364 | *mrup = mru; |
365 | |
366 | exit: |
367 | if (err && mru && mru->lists) |
368 | kfree(objp: mru->lists); |
369 | if (err && mru) |
370 | kfree(objp: mru); |
371 | |
372 | return err; |
373 | } |
374 | |
375 | /* |
376 | * Call xfs_mru_cache_flush() to flush out all cached entries, calling their |
377 | * free functions as they're deleted. When this function returns, the caller is |
378 | * guaranteed that all the free functions for all the elements have finished |
379 | * executing and the reaper is not running. |
380 | */ |
381 | static void |
382 | xfs_mru_cache_flush( |
383 | struct xfs_mru_cache *mru) |
384 | { |
385 | if (!mru || !mru->lists) |
386 | return; |
387 | |
388 | spin_lock(lock: &mru->lock); |
389 | if (mru->queued) { |
390 | spin_unlock(lock: &mru->lock); |
391 | cancel_delayed_work_sync(dwork: &mru->work); |
392 | spin_lock(lock: &mru->lock); |
393 | } |
394 | |
395 | _xfs_mru_cache_migrate(mru, now: jiffies + mru->grp_count * mru->grp_time); |
396 | _xfs_mru_cache_clear_reap_list(mru); |
397 | |
398 | spin_unlock(lock: &mru->lock); |
399 | } |
400 | |
401 | void |
402 | xfs_mru_cache_destroy( |
403 | struct xfs_mru_cache *mru) |
404 | { |
405 | if (!mru || !mru->lists) |
406 | return; |
407 | |
408 | xfs_mru_cache_flush(mru); |
409 | |
410 | kfree(objp: mru->lists); |
411 | kfree(objp: mru); |
412 | } |
413 | |
414 | /* |
415 | * To insert an element, call xfs_mru_cache_insert() with the data store, the |
416 | * element's key and the client data pointer. This function returns 0 on |
417 | * success or ENOMEM if memory for the data element couldn't be allocated. |
418 | */ |
419 | int |
420 | xfs_mru_cache_insert( |
421 | struct xfs_mru_cache *mru, |
422 | unsigned long key, |
423 | struct xfs_mru_cache_elem *elem) |
424 | { |
425 | int error; |
426 | |
427 | ASSERT(mru && mru->lists); |
428 | if (!mru || !mru->lists) |
429 | return -EINVAL; |
430 | |
431 | if (radix_tree_preload(GFP_KERNEL)) |
432 | return -ENOMEM; |
433 | |
434 | INIT_LIST_HEAD(list: &elem->list_node); |
435 | elem->key = key; |
436 | |
437 | spin_lock(lock: &mru->lock); |
438 | error = radix_tree_insert(&mru->store, index: key, elem); |
439 | radix_tree_preload_end(); |
440 | if (!error) |
441 | _xfs_mru_cache_list_insert(mru, elem); |
442 | spin_unlock(lock: &mru->lock); |
443 | |
444 | return error; |
445 | } |
446 | |
447 | /* |
448 | * To remove an element without calling the free function, call |
449 | * xfs_mru_cache_remove() with the data store and the element's key. On success |
450 | * the client data pointer for the removed element is returned, otherwise this |
451 | * function will return a NULL pointer. |
452 | */ |
453 | struct xfs_mru_cache_elem * |
454 | xfs_mru_cache_remove( |
455 | struct xfs_mru_cache *mru, |
456 | unsigned long key) |
457 | { |
458 | struct xfs_mru_cache_elem *elem; |
459 | |
460 | ASSERT(mru && mru->lists); |
461 | if (!mru || !mru->lists) |
462 | return NULL; |
463 | |
464 | spin_lock(lock: &mru->lock); |
465 | elem = radix_tree_delete(&mru->store, key); |
466 | if (elem) |
467 | list_del(entry: &elem->list_node); |
468 | spin_unlock(lock: &mru->lock); |
469 | |
470 | return elem; |
471 | } |
472 | |
473 | /* |
474 | * To remove and element and call the free function, call xfs_mru_cache_delete() |
475 | * with the data store and the element's key. |
476 | */ |
477 | void |
478 | xfs_mru_cache_delete( |
479 | struct xfs_mru_cache *mru, |
480 | unsigned long key) |
481 | { |
482 | struct xfs_mru_cache_elem *elem; |
483 | |
484 | elem = xfs_mru_cache_remove(mru, key); |
485 | if (elem) |
486 | mru->free_func(mru->data, elem); |
487 | } |
488 | |
489 | /* |
490 | * To look up an element using its key, call xfs_mru_cache_lookup() with the |
491 | * data store and the element's key. If found, the element will be moved to the |
492 | * head of the MRU list to indicate that it's been touched. |
493 | * |
494 | * The internal data structures are protected by a spinlock that is STILL HELD |
495 | * when this function returns. Call xfs_mru_cache_done() to release it. Note |
496 | * that it is not safe to call any function that might sleep in the interim. |
497 | * |
498 | * The implementation could have used reference counting to avoid this |
499 | * restriction, but since most clients simply want to get, set or test a member |
500 | * of the returned data structure, the extra per-element memory isn't warranted. |
501 | * |
502 | * If the element isn't found, this function returns NULL and the spinlock is |
503 | * released. xfs_mru_cache_done() should NOT be called when this occurs. |
504 | * |
505 | * Because sparse isn't smart enough to know about conditional lock return |
506 | * status, we need to help it get it right by annotating the path that does |
507 | * not release the lock. |
508 | */ |
509 | struct xfs_mru_cache_elem * |
510 | xfs_mru_cache_lookup( |
511 | struct xfs_mru_cache *mru, |
512 | unsigned long key) |
513 | { |
514 | struct xfs_mru_cache_elem *elem; |
515 | |
516 | ASSERT(mru && mru->lists); |
517 | if (!mru || !mru->lists) |
518 | return NULL; |
519 | |
520 | spin_lock(lock: &mru->lock); |
521 | elem = radix_tree_lookup(&mru->store, key); |
522 | if (elem) { |
523 | list_del(entry: &elem->list_node); |
524 | _xfs_mru_cache_list_insert(mru, elem); |
525 | __release(mru_lock); /* help sparse not be stupid */ |
526 | } else |
527 | spin_unlock(lock: &mru->lock); |
528 | |
529 | return elem; |
530 | } |
531 | |
532 | /* |
533 | * To release the internal data structure spinlock after having performed an |
534 | * xfs_mru_cache_lookup() or an xfs_mru_cache_peek(), call xfs_mru_cache_done() |
535 | * with the data store pointer. |
536 | */ |
537 | void |
538 | xfs_mru_cache_done( |
539 | struct xfs_mru_cache *mru) |
540 | __releases(mru->lock) |
541 | { |
542 | spin_unlock(lock: &mru->lock); |
543 | } |
544 | |