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