~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/xfs/xfs_mru_cache.c

Version: ~ [ linux-5.5-rc7 ] ~ [ linux-5.4.13 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.97 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.166 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.210 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.210 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.81 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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  */
103 struct 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 
117 static 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  */
136 STATIC 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  */
200 STATIC 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  */
238 STATIC 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  */
275 STATIC 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 
304 int
305 xfs_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 
314 void
315 xfs_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  */
326 int
327 xfs_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 
375 exit:
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  */
390 static void
391 xfs_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 
410 void
411 xfs_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  */
428 int
429 xfs_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  */
462 struct xfs_mru_cache_elem *
463 xfs_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  */
486 void
487 xfs_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  */
518 struct xfs_mru_cache_elem *
519 xfs_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  */
546 void
547 xfs_mru_cache_done(
548         struct xfs_mru_cache    *mru)
549                 __releases(mru->lock)
550 {
551         spin_unlock(&mru->lock);
552 }
553 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp