Loading...
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 */
91struct 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
106static 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 */
125STATIC 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(lru_list))
147 list_splice_init(lru_list, 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(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 */
189STATIC 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(xfs_mru_reap_wq, &mru->work,
207 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(&elem->list_node, 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 */
227STATIC 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(&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(&elem->list_node, &tmp);
246 }
247 spin_unlock(&mru->lock);
248
249 list_for_each_entry_safe(elem, next, &tmp, list_node) {
250 list_del_init(&elem->list_node);
251 mru->free_func(mru->data, elem);
252 }
253
254 spin_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 */
264STATIC 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(&mru->lock);
277 next = _xfs_mru_cache_migrate(mru, 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(xfs_mru_reap_wq, &mru->work, next);
288 }
289
290 spin_unlock(&mru->lock);
291}
292
293int
294xfs_mru_cache_init(void)
295{
296 xfs_mru_reap_wq = alloc_workqueue("xfs_mru_cache",
297 XFS_WQFLAGS(WQ_MEM_RECLAIM | WQ_FREEZABLE), 1);
298 if (!xfs_mru_reap_wq)
299 return -ENOMEM;
300 return 0;
301}
302
303void
304xfs_mru_cache_uninit(void)
305{
306 destroy_workqueue(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 */
315int
316xfs_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(lifetime_ms) / grp_count))
334 return -EINVAL;
335
336 mru = kzalloc(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(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(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(&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
366exit:
367 if (err && mru && mru->lists)
368 kfree(mru->lists);
369 if (err && mru)
370 kfree(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 */
381static void
382xfs_mru_cache_flush(
383 struct xfs_mru_cache *mru)
384{
385 if (!mru || !mru->lists)
386 return;
387
388 spin_lock(&mru->lock);
389 if (mru->queued) {
390 spin_unlock(&mru->lock);
391 cancel_delayed_work_sync(&mru->work);
392 spin_lock(&mru->lock);
393 }
394
395 _xfs_mru_cache_migrate(mru, jiffies + mru->grp_count * mru->grp_time);
396 _xfs_mru_cache_clear_reap_list(mru);
397
398 spin_unlock(&mru->lock);
399}
400
401void
402xfs_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(mru->lists);
411 kfree(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 */
419int
420xfs_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(&elem->list_node);
435 elem->key = key;
436
437 spin_lock(&mru->lock);
438 error = radix_tree_insert(&mru->store, key, elem);
439 radix_tree_preload_end();
440 if (!error)
441 _xfs_mru_cache_list_insert(mru, elem);
442 spin_unlock(&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 */
453struct xfs_mru_cache_elem *
454xfs_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(&mru->lock);
465 elem = radix_tree_delete(&mru->store, key);
466 if (elem)
467 list_del(&elem->list_node);
468 spin_unlock(&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 */
477void
478xfs_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 */
509struct xfs_mru_cache_elem *
510xfs_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(&mru->lock);
521 elem = radix_tree_lookup(&mru->store, key);
522 if (elem) {
523 list_del(&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(&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 */
537void
538xfs_mru_cache_done(
539 struct xfs_mru_cache *mru)
540 __releases(mru->lock)
541{
542 spin_unlock(&mru->lock);
543}
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 */
91struct 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
106static 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 */
125STATIC 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(lru_list))
147 list_splice_init(lru_list, 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(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 */
189STATIC 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(xfs_mru_reap_wq, &mru->work,
207 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(&elem->list_node, 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 */
227STATIC 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 LIST_HEAD(tmp);
234
235 list_for_each_entry_safe(elem, next, &mru->reap_list, list_node) {
236
237 /* Remove the element from the data store. */
238 radix_tree_delete(&mru->store, elem->key);
239
240 /*
241 * remove to temp list so it can be freed without
242 * needing to hold the lock
243 */
244 list_move(&elem->list_node, &tmp);
245 }
246 spin_unlock(&mru->lock);
247
248 list_for_each_entry_safe(elem, next, &tmp, list_node) {
249 list_del_init(&elem->list_node);
250 mru->free_func(mru->data, elem);
251 }
252
253 spin_lock(&mru->lock);
254}
255
256/*
257 * We fire the reap timer every group expiry interval so
258 * we always have a reaper ready to run. This makes shutdown
259 * and flushing of the reaper easy to do. Hence we need to
260 * keep when the next reap must occur so we can determine
261 * at each interval whether there is anything we need to do.
262 */
263STATIC void
264_xfs_mru_cache_reap(
265 struct work_struct *work)
266{
267 struct xfs_mru_cache *mru =
268 container_of(work, struct xfs_mru_cache, work.work);
269 unsigned long now, next;
270
271 ASSERT(mru && mru->lists);
272 if (!mru || !mru->lists)
273 return;
274
275 spin_lock(&mru->lock);
276 next = _xfs_mru_cache_migrate(mru, jiffies);
277 _xfs_mru_cache_clear_reap_list(mru);
278
279 mru->queued = next;
280 if ((mru->queued > 0)) {
281 now = jiffies;
282 if (next <= now)
283 next = 0;
284 else
285 next -= now;
286 queue_delayed_work(xfs_mru_reap_wq, &mru->work, next);
287 }
288
289 spin_unlock(&mru->lock);
290}
291
292int
293xfs_mru_cache_init(void)
294{
295 xfs_mru_reap_wq = alloc_workqueue("xfs_mru_cache",
296 XFS_WQFLAGS(WQ_MEM_RECLAIM | WQ_FREEZABLE), 1);
297 if (!xfs_mru_reap_wq)
298 return -ENOMEM;
299 return 0;
300}
301
302void
303xfs_mru_cache_uninit(void)
304{
305 destroy_workqueue(xfs_mru_reap_wq);
306}
307
308/*
309 * To initialise a struct xfs_mru_cache pointer, call xfs_mru_cache_create()
310 * with the address of the pointer, a lifetime value in milliseconds, a group
311 * count and a free function to use when deleting elements. This function
312 * returns 0 if the initialisation was successful.
313 */
314int
315xfs_mru_cache_create(
316 struct xfs_mru_cache **mrup,
317 void *data,
318 unsigned int lifetime_ms,
319 unsigned int grp_count,
320 xfs_mru_cache_free_func_t free_func)
321{
322 struct xfs_mru_cache *mru = NULL;
323 int err = 0, grp;
324 unsigned int grp_time;
325
326 if (mrup)
327 *mrup = NULL;
328
329 if (!mrup || !grp_count || !lifetime_ms || !free_func)
330 return -EINVAL;
331
332 if (!(grp_time = msecs_to_jiffies(lifetime_ms) / grp_count))
333 return -EINVAL;
334
335 mru = kzalloc(sizeof(*mru), GFP_KERNEL | __GFP_NOFAIL);
336 if (!mru)
337 return -ENOMEM;
338
339 /* An extra list is needed to avoid reaping up to a grp_time early. */
340 mru->grp_count = grp_count + 1;
341 mru->lists = kzalloc(mru->grp_count * sizeof(*mru->lists),
342 GFP_KERNEL | __GFP_NOFAIL);
343 if (!mru->lists) {
344 err = -ENOMEM;
345 goto exit;
346 }
347
348 for (grp = 0; grp < mru->grp_count; grp++)
349 INIT_LIST_HEAD(mru->lists + grp);
350
351 /*
352 * We use GFP_KERNEL radix tree preload and do inserts under a
353 * spinlock so GFP_ATOMIC is appropriate for the radix tree itself.
354 */
355 INIT_RADIX_TREE(&mru->store, GFP_ATOMIC);
356 INIT_LIST_HEAD(&mru->reap_list);
357 spin_lock_init(&mru->lock);
358 INIT_DELAYED_WORK(&mru->work, _xfs_mru_cache_reap);
359
360 mru->grp_time = grp_time;
361 mru->free_func = free_func;
362 mru->data = data;
363 *mrup = mru;
364
365exit:
366 if (err && mru && mru->lists)
367 kfree(mru->lists);
368 if (err && mru)
369 kfree(mru);
370
371 return err;
372}
373
374/*
375 * Call xfs_mru_cache_flush() to flush out all cached entries, calling their
376 * free functions as they're deleted. When this function returns, the caller is
377 * guaranteed that all the free functions for all the elements have finished
378 * executing and the reaper is not running.
379 */
380static void
381xfs_mru_cache_flush(
382 struct xfs_mru_cache *mru)
383{
384 if (!mru || !mru->lists)
385 return;
386
387 spin_lock(&mru->lock);
388 if (mru->queued) {
389 spin_unlock(&mru->lock);
390 cancel_delayed_work_sync(&mru->work);
391 spin_lock(&mru->lock);
392 }
393
394 _xfs_mru_cache_migrate(mru, jiffies + mru->grp_count * mru->grp_time);
395 _xfs_mru_cache_clear_reap_list(mru);
396
397 spin_unlock(&mru->lock);
398}
399
400void
401xfs_mru_cache_destroy(
402 struct xfs_mru_cache *mru)
403{
404 if (!mru || !mru->lists)
405 return;
406
407 xfs_mru_cache_flush(mru);
408
409 kfree(mru->lists);
410 kfree(mru);
411}
412
413/*
414 * To insert an element, call xfs_mru_cache_insert() with the data store, the
415 * element's key and the client data pointer. This function returns 0 on
416 * success or ENOMEM if memory for the data element couldn't be allocated.
417 */
418int
419xfs_mru_cache_insert(
420 struct xfs_mru_cache *mru,
421 unsigned long key,
422 struct xfs_mru_cache_elem *elem)
423{
424 int error;
425
426 ASSERT(mru && mru->lists);
427 if (!mru || !mru->lists)
428 return -EINVAL;
429
430 if (radix_tree_preload(GFP_KERNEL))
431 return -ENOMEM;
432
433 INIT_LIST_HEAD(&elem->list_node);
434 elem->key = key;
435
436 spin_lock(&mru->lock);
437 error = radix_tree_insert(&mru->store, key, elem);
438 radix_tree_preload_end();
439 if (!error)
440 _xfs_mru_cache_list_insert(mru, elem);
441 spin_unlock(&mru->lock);
442
443 return error;
444}
445
446/*
447 * To remove an element without calling the free function, call
448 * xfs_mru_cache_remove() with the data store and the element's key. On success
449 * the client data pointer for the removed element is returned, otherwise this
450 * function will return a NULL pointer.
451 */
452struct xfs_mru_cache_elem *
453xfs_mru_cache_remove(
454 struct xfs_mru_cache *mru,
455 unsigned long key)
456{
457 struct xfs_mru_cache_elem *elem;
458
459 ASSERT(mru && mru->lists);
460 if (!mru || !mru->lists)
461 return NULL;
462
463 spin_lock(&mru->lock);
464 elem = radix_tree_delete(&mru->store, key);
465 if (elem)
466 list_del(&elem->list_node);
467 spin_unlock(&mru->lock);
468
469 return elem;
470}
471
472/*
473 * To remove and element and call the free function, call xfs_mru_cache_delete()
474 * with the data store and the element's key.
475 */
476void
477xfs_mru_cache_delete(
478 struct xfs_mru_cache *mru,
479 unsigned long key)
480{
481 struct xfs_mru_cache_elem *elem;
482
483 elem = xfs_mru_cache_remove(mru, key);
484 if (elem)
485 mru->free_func(mru->data, elem);
486}
487
488/*
489 * To look up an element using its key, call xfs_mru_cache_lookup() with the
490 * data store and the element's key. If found, the element will be moved to the
491 * head of the MRU list to indicate that it's been touched.
492 *
493 * The internal data structures are protected by a spinlock that is STILL HELD
494 * when this function returns. Call xfs_mru_cache_done() to release it. Note
495 * that it is not safe to call any function that might sleep in the interim.
496 *
497 * The implementation could have used reference counting to avoid this
498 * restriction, but since most clients simply want to get, set or test a member
499 * of the returned data structure, the extra per-element memory isn't warranted.
500 *
501 * If the element isn't found, this function returns NULL and the spinlock is
502 * released. xfs_mru_cache_done() should NOT be called when this occurs.
503 *
504 * Because sparse isn't smart enough to know about conditional lock return
505 * status, we need to help it get it right by annotating the path that does
506 * not release the lock.
507 */
508struct xfs_mru_cache_elem *
509xfs_mru_cache_lookup(
510 struct xfs_mru_cache *mru,
511 unsigned long key)
512{
513 struct xfs_mru_cache_elem *elem;
514
515 ASSERT(mru && mru->lists);
516 if (!mru || !mru->lists)
517 return NULL;
518
519 spin_lock(&mru->lock);
520 elem = radix_tree_lookup(&mru->store, key);
521 if (elem) {
522 list_del(&elem->list_node);
523 _xfs_mru_cache_list_insert(mru, elem);
524 __release(mru_lock); /* help sparse not be stupid */
525 } else
526 spin_unlock(&mru->lock);
527
528 return elem;
529}
530
531/*
532 * To release the internal data structure spinlock after having performed an
533 * xfs_mru_cache_lookup() or an xfs_mru_cache_peek(), call xfs_mru_cache_done()
534 * with the data store pointer.
535 */
536void
537xfs_mru_cache_done(
538 struct xfs_mru_cache *mru)
539 __releases(mru->lock)
540{
541 spin_unlock(&mru->lock);
542}