linux/fs/xfs/xfs_mru_cache.c
<<
>>
Prefs
   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 */
 103typedef struct xfs_mru_cache_elem
 104{
 105        struct list_head list_node;
 106        unsigned long   key;
 107        void            *value;
 108} xfs_mru_cache_elem_t;
 109
 110static kmem_zone_t              *xfs_mru_elem_zone;
 111static struct workqueue_struct  *xfs_mru_reap_wq;
 112
 113/*
 114 * When inserting, destroying or reaping, it's first necessary to update the
 115 * lists relative to a particular time.  In the case of destroying, that time
 116 * will be well in the future to ensure that all items are moved to the reap
 117 * list.  In all other cases though, the time will be the current time.
 118 *
 119 * This function enters a loop, moving the contents of the LRU list to the reap
 120 * list again and again until either a) the lists are all empty, or b) time zero
 121 * has been advanced sufficiently to be within the immediate element lifetime.
 122 *
 123 * Case a) above is detected by counting how many groups are migrated and
 124 * stopping when they've all been moved.  Case b) is detected by monitoring the
 125 * time_zero field, which is updated as each group is migrated.
 126 *
 127 * The return value is the earliest time that more migration could be needed, or
 128 * zero if there's no need to schedule more work because the lists are empty.
 129 */
 130STATIC unsigned long
 131_xfs_mru_cache_migrate(
 132        xfs_mru_cache_t *mru,
 133        unsigned long   now)
 134{
 135        unsigned int    grp;
 136        unsigned int    migrated = 0;
 137        struct list_head *lru_list;
 138
 139        /* Nothing to do if the data store is empty. */
 140        if (!mru->time_zero)
 141                return 0;
 142
 143        /* While time zero is older than the time spanned by all the lists. */
 144        while (mru->time_zero <= now - mru->grp_count * mru->grp_time) {
 145
 146                /*
 147                 * If the LRU list isn't empty, migrate its elements to the tail
 148                 * of the reap list.
 149                 */
 150                lru_list = mru->lists + mru->lru_grp;
 151                if (!list_empty(lru_list))
 152                        list_splice_init(lru_list, mru->reap_list.prev);
 153
 154                /*
 155                 * Advance the LRU group number, freeing the old LRU list to
 156                 * become the new MRU list; advance time zero accordingly.
 157                 */
 158                mru->lru_grp = (mru->lru_grp + 1) % mru->grp_count;
 159                mru->time_zero += mru->grp_time;
 160
 161                /*
 162                 * If reaping is so far behind that all the elements on all the
 163                 * lists have been migrated to the reap list, it's now empty.
 164                 */
 165                if (++migrated == mru->grp_count) {
 166                        mru->lru_grp = 0;
 167                        mru->time_zero = 0;
 168                        return 0;
 169                }
 170        }
 171
 172        /* Find the first non-empty list from the LRU end. */
 173        for (grp = 0; grp < mru->grp_count; grp++) {
 174
 175                /* Check the grp'th list from the LRU end. */
 176                lru_list = mru->lists + ((mru->lru_grp + grp) % mru->grp_count);
 177                if (!list_empty(lru_list))
 178                        return mru->time_zero +
 179                               (mru->grp_count + grp) * mru->grp_time;
 180        }
 181
 182        /* All the lists must be empty. */
 183        mru->lru_grp = 0;
 184        mru->time_zero = 0;
 185        return 0;
 186}
 187
 188/*
 189 * When inserting or doing a lookup, an element needs to be inserted into the
 190 * MRU list.  The lists must be migrated first to ensure that they're
 191 * up-to-date, otherwise the new element could be given a shorter lifetime in
 192 * the cache than it should.
 193 */
 194STATIC void
 195_xfs_mru_cache_list_insert(
 196        xfs_mru_cache_t         *mru,
 197        xfs_mru_cache_elem_t    *elem)
 198{
 199        unsigned int    grp = 0;
 200        unsigned long   now = jiffies;
 201
 202        /*
 203         * If the data store is empty, initialise time zero, leave grp set to
 204         * zero and start the work queue timer if necessary.  Otherwise, set grp
 205         * to the number of group times that have elapsed since time zero.
 206         */
 207        if (!_xfs_mru_cache_migrate(mru, now)) {
 208                mru->time_zero = now;
 209                if (!mru->queued) {
 210                        mru->queued = 1;
 211                        queue_delayed_work(xfs_mru_reap_wq, &mru->work,
 212                                           mru->grp_count * mru->grp_time);
 213                }
 214        } else {
 215                grp = (now - mru->time_zero) / mru->grp_time;
 216                grp = (mru->lru_grp + grp) % mru->grp_count;
 217        }
 218
 219        /* Insert the element at the tail of the corresponding list. */
 220        list_add_tail(&elem->list_node, mru->lists + grp);
 221}
 222
 223/*
 224 * When destroying or reaping, all the elements that were migrated to the reap
 225 * list need to be deleted.  For each element this involves removing it from the
 226 * data store, removing it from the reap list, calling the client's free
 227 * function and deleting the element from the element zone.
 228 *
 229 * We get called holding the mru->lock, which we drop and then reacquire.
 230 * Sparse need special help with this to tell it we know what we are doing.
 231 */
 232STATIC void
 233_xfs_mru_cache_clear_reap_list(
 234        xfs_mru_cache_t         *mru) __releases(mru->lock) __acquires(mru->lock)
 235
 236{
 237        xfs_mru_cache_elem_t    *elem, *next;
 238        struct list_head        tmp;
 239
 240        INIT_LIST_HEAD(&tmp);
 241        list_for_each_entry_safe(elem, next, &mru->reap_list, list_node) {
 242
 243                /* Remove the element from the data store. */
 244                radix_tree_delete(&mru->store, elem->key);
 245
 246                /*
 247                 * remove to temp list so it can be freed without
 248                 * needing to hold the lock
 249                 */
 250                list_move(&elem->list_node, &tmp);
 251        }
 252        spin_unlock(&mru->lock);
 253
 254        list_for_each_entry_safe(elem, next, &tmp, list_node) {
 255
 256                /* Remove the element from the reap list. */
 257                list_del_init(&elem->list_node);
 258
 259                /* Call the client's free function with the key and value pointer. */
 260                mru->free_func(elem->key, elem->value);
 261
 262                /* Free the element structure. */
 263                kmem_zone_free(xfs_mru_elem_zone, 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        xfs_mru_cache_t         *mru = container_of(work, xfs_mru_cache_t, 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_elem_zone = kmem_zone_init(sizeof(xfs_mru_cache_elem_t),
 308                                         "xfs_mru_cache_elem");
 309        if (!xfs_mru_elem_zone)
 310                goto out;
 311
 312        xfs_mru_reap_wq = alloc_workqueue("xfs_mru_cache", WQ_MEM_RECLAIM, 1);
 313        if (!xfs_mru_reap_wq)
 314                goto out_destroy_mru_elem_zone;
 315
 316        return 0;
 317
 318 out_destroy_mru_elem_zone:
 319        kmem_zone_destroy(xfs_mru_elem_zone);
 320 out:
 321        return -ENOMEM;
 322}
 323
 324void
 325xfs_mru_cache_uninit(void)
 326{
 327        destroy_workqueue(xfs_mru_reap_wq);
 328        kmem_zone_destroy(xfs_mru_elem_zone);
 329}
 330
 331/*
 332 * To initialise a struct xfs_mru_cache pointer, call xfs_mru_cache_create()
 333 * with the address of the pointer, a lifetime value in milliseconds, a group
 334 * count and a free function to use when deleting elements.  This function
 335 * returns 0 if the initialisation was successful.
 336 */
 337int
 338xfs_mru_cache_create(
 339        xfs_mru_cache_t         **mrup,
 340        unsigned int            lifetime_ms,
 341        unsigned int            grp_count,
 342        xfs_mru_cache_free_func_t free_func)
 343{
 344        xfs_mru_cache_t *mru = NULL;
 345        int             err = 0, grp;
 346        unsigned int    grp_time;
 347
 348        if (mrup)
 349                *mrup = NULL;
 350
 351        if (!mrup || !grp_count || !lifetime_ms || !free_func)
 352                return EINVAL;
 353
 354        if (!(grp_time = msecs_to_jiffies(lifetime_ms) / grp_count))
 355                return EINVAL;
 356
 357        if (!(mru = kmem_zalloc(sizeof(*mru), KM_SLEEP)))
 358                return ENOMEM;
 359
 360        /* An extra list is needed to avoid reaping up to a grp_time early. */
 361        mru->grp_count = grp_count + 1;
 362        mru->lists = kmem_zalloc(mru->grp_count * sizeof(*mru->lists), KM_SLEEP);
 363
 364        if (!mru->lists) {
 365                err = ENOMEM;
 366                goto exit;
 367        }
 368
 369        for (grp = 0; grp < mru->grp_count; grp++)
 370                INIT_LIST_HEAD(mru->lists + grp);
 371
 372        /*
 373         * We use GFP_KERNEL radix tree preload and do inserts under a
 374         * spinlock so GFP_ATOMIC is appropriate for the radix tree itself.
 375         */
 376        INIT_RADIX_TREE(&mru->store, GFP_ATOMIC);
 377        INIT_LIST_HEAD(&mru->reap_list);
 378        spin_lock_init(&mru->lock);
 379        INIT_DELAYED_WORK(&mru->work, _xfs_mru_cache_reap);
 380
 381        mru->grp_time  = grp_time;
 382        mru->free_func = free_func;
 383
 384        *mrup = mru;
 385
 386exit:
 387        if (err && mru && mru->lists)
 388                kmem_free(mru->lists);
 389        if (err && mru)
 390                kmem_free(mru);
 391
 392        return err;
 393}
 394
 395/*
 396 * Call xfs_mru_cache_flush() to flush out all cached entries, calling their
 397 * free functions as they're deleted.  When this function returns, the caller is
 398 * guaranteed that all the free functions for all the elements have finished
 399 * executing and the reaper is not running.
 400 */
 401static void
 402xfs_mru_cache_flush(
 403        xfs_mru_cache_t         *mru)
 404{
 405        if (!mru || !mru->lists)
 406                return;
 407
 408        spin_lock(&mru->lock);
 409        if (mru->queued) {
 410                spin_unlock(&mru->lock);
 411                cancel_delayed_work_sync(&mru->work);
 412                spin_lock(&mru->lock);
 413        }
 414
 415        _xfs_mru_cache_migrate(mru, jiffies + mru->grp_count * mru->grp_time);
 416        _xfs_mru_cache_clear_reap_list(mru);
 417
 418        spin_unlock(&mru->lock);
 419}
 420
 421void
 422xfs_mru_cache_destroy(
 423        xfs_mru_cache_t         *mru)
 424{
 425        if (!mru || !mru->lists)
 426                return;
 427
 428        xfs_mru_cache_flush(mru);
 429
 430        kmem_free(mru->lists);
 431        kmem_free(mru);
 432}
 433
 434/*
 435 * To insert an element, call xfs_mru_cache_insert() with the data store, the
 436 * element's key and the client data pointer.  This function returns 0 on
 437 * success or ENOMEM if memory for the data element couldn't be allocated.
 438 */
 439int
 440xfs_mru_cache_insert(
 441        xfs_mru_cache_t *mru,
 442        unsigned long   key,
 443        void            *value)
 444{
 445        xfs_mru_cache_elem_t *elem;
 446
 447        ASSERT(mru && mru->lists);
 448        if (!mru || !mru->lists)
 449                return EINVAL;
 450
 451        elem = kmem_zone_zalloc(xfs_mru_elem_zone, KM_SLEEP);
 452        if (!elem)
 453                return ENOMEM;
 454
 455        if (radix_tree_preload(GFP_KERNEL)) {
 456                kmem_zone_free(xfs_mru_elem_zone, elem);
 457                return ENOMEM;
 458        }
 459
 460        INIT_LIST_HEAD(&elem->list_node);
 461        elem->key = key;
 462        elem->value = value;
 463
 464        spin_lock(&mru->lock);
 465
 466        radix_tree_insert(&mru->store, key, elem);
 467        radix_tree_preload_end();
 468        _xfs_mru_cache_list_insert(mru, elem);
 469
 470        spin_unlock(&mru->lock);
 471
 472        return 0;
 473}
 474
 475/*
 476 * To remove an element without calling the free function, call
 477 * xfs_mru_cache_remove() with the data store and the element's key.  On success
 478 * the client data pointer for the removed element is returned, otherwise this
 479 * function will return a NULL pointer.
 480 */
 481void *
 482xfs_mru_cache_remove(
 483        xfs_mru_cache_t *mru,
 484        unsigned long   key)
 485{
 486        xfs_mru_cache_elem_t *elem;
 487        void            *value = NULL;
 488
 489        ASSERT(mru && mru->lists);
 490        if (!mru || !mru->lists)
 491                return NULL;
 492
 493        spin_lock(&mru->lock);
 494        elem = radix_tree_delete(&mru->store, key);
 495        if (elem) {
 496                value = elem->value;
 497                list_del(&elem->list_node);
 498        }
 499
 500        spin_unlock(&mru->lock);
 501
 502        if (elem)
 503                kmem_zone_free(xfs_mru_elem_zone, elem);
 504
 505        return value;
 506}
 507
 508/*
 509 * To remove and element and call the free function, call xfs_mru_cache_delete()
 510 * with the data store and the element's key.
 511 */
 512void
 513xfs_mru_cache_delete(
 514        xfs_mru_cache_t *mru,
 515        unsigned long   key)
 516{
 517        void            *value = xfs_mru_cache_remove(mru, key);
 518
 519        if (value)
 520                mru->free_func(key, value);
 521}
 522
 523/*
 524 * To look up an element using its key, call xfs_mru_cache_lookup() with the
 525 * data store and the element's key.  If found, the element will be moved to the
 526 * head of the MRU list to indicate that it's been touched.
 527 *
 528 * The internal data structures are protected by a spinlock that is STILL HELD
 529 * when this function returns.  Call xfs_mru_cache_done() to release it.  Note
 530 * that it is not safe to call any function that might sleep in the interim.
 531 *
 532 * The implementation could have used reference counting to avoid this
 533 * restriction, but since most clients simply want to get, set or test a member
 534 * of the returned data structure, the extra per-element memory isn't warranted.
 535 *
 536 * If the element isn't found, this function returns NULL and the spinlock is
 537 * released.  xfs_mru_cache_done() should NOT be called when this occurs.
 538 *
 539 * Because sparse isn't smart enough to know about conditional lock return
 540 * status, we need to help it get it right by annotating the path that does
 541 * not release the lock.
 542 */
 543void *
 544xfs_mru_cache_lookup(
 545        xfs_mru_cache_t *mru,
 546        unsigned long   key)
 547{
 548        xfs_mru_cache_elem_t *elem;
 549
 550        ASSERT(mru && mru->lists);
 551        if (!mru || !mru->lists)
 552                return NULL;
 553
 554        spin_lock(&mru->lock);
 555        elem = radix_tree_lookup(&mru->store, key);
 556        if (elem) {
 557                list_del(&elem->list_node);
 558                _xfs_mru_cache_list_insert(mru, elem);
 559                __release(mru_lock); /* help sparse not be stupid */
 560        } else
 561                spin_unlock(&mru->lock);
 562
 563        return elem ? elem->value : NULL;
 564}
 565
 566/*
 567 * To release the internal data structure spinlock after having performed an
 568 * xfs_mru_cache_lookup() or an xfs_mru_cache_peek(), call xfs_mru_cache_done()
 569 * with the data store pointer.
 570 */
 571void
 572xfs_mru_cache_done(
 573        xfs_mru_cache_t *mru) __releases(mru->lock)
 574{
 575        spin_unlock(&mru->lock);
 576}
 577