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", WQ_MEM_RECLAIM, 1); 308 if (!xfs_mru_reap_wq) 309 return -ENOMEM; 310 return 0; 311 } 312 313 void 314 xfs_mru_cache_uninit(void) 315 { 316 destroy_workqueue(xfs_mru_reap_wq); 317 } 318 319 /* 320 * To initialise a struct xfs_mru_cache pointer, call xfs_mru_cache_create() 321 * with the address of the pointer, a lifetime value in milliseconds, a group 322 * count and a free function to use when deleting elements. This function 323 * returns 0 if the initialisation was successful. 324 */ 325 int 326 xfs_mru_cache_create( 327 struct xfs_mru_cache **mrup, 328 unsigned int lifetime_ms, 329 unsigned int grp_count, 330 xfs_mru_cache_free_func_t free_func) 331 { 332 struct xfs_mru_cache *mru = NULL; 333 int err = 0, grp; 334 unsigned int grp_time; 335 336 if (mrup) 337 *mrup = NULL; 338 339 if (!mrup || !grp_count || !lifetime_ms || !free_func) 340 return EINVAL; 341 342 if (!(grp_time = msecs_to_jiffies(lifetime_ms) / grp_count)) 343 return EINVAL; 344 345 if (!(mru = kmem_zalloc(sizeof(*mru), KM_SLEEP))) 346 return ENOMEM; 347 348 /* An extra list is needed to avoid reaping up to a grp_time early. */ 349 mru->grp_count = grp_count + 1; 350 mru->lists = kmem_zalloc(mru->grp_count * sizeof(*mru->lists), KM_SLEEP); 351 352 if (!mru->lists) { 353 err = ENOMEM; 354 goto exit; 355 } 356 357 for (grp = 0; grp < mru->grp_count; grp++) 358 INIT_LIST_HEAD(mru->lists + grp); 359 360 /* 361 * We use GFP_KERNEL radix tree preload and do inserts under a 362 * spinlock so GFP_ATOMIC is appropriate for the radix tree itself. 363 */ 364 INIT_RADIX_TREE(&mru->store, GFP_ATOMIC); 365 INIT_LIST_HEAD(&mru->reap_list); 366 spin_lock_init(&mru->lock); 367 INIT_DELAYED_WORK(&mru->work, _xfs_mru_cache_reap); 368 369 mru->grp_time = grp_time; 370 mru->free_func = free_func; 371 372 *mrup = mru; 373 374 exit: 375 if (err && mru && mru->lists) 376 kmem_free(mru->lists); 377 if (err && mru) 378 kmem_free(mru); 379 380 return err; 381 } 382 383 /* 384 * Call xfs_mru_cache_flush() to flush out all cached entries, calling their 385 * free functions as they're deleted. When this function returns, the caller is 386 * guaranteed that all the free functions for all the elements have finished 387 * executing and the reaper is not running. 388 */ 389 static void 390 xfs_mru_cache_flush( 391 struct xfs_mru_cache *mru) 392 { 393 if (!mru || !mru->lists) 394 return; 395 396 spin_lock(&mru->lock); 397 if (mru->queued) { 398 spin_unlock(&mru->lock); 399 cancel_delayed_work_sync(&mru->work); 400 spin_lock(&mru->lock); 401 } 402 403 _xfs_mru_cache_migrate(mru, jiffies + mru->grp_count * mru->grp_time); 404 _xfs_mru_cache_clear_reap_list(mru); 405 406 spin_unlock(&mru->lock); 407 } 408 409 void 410 xfs_mru_cache_destroy( 411 struct xfs_mru_cache *mru) 412 { 413 if (!mru || !mru->lists) 414 return; 415 416 xfs_mru_cache_flush(mru); 417 418 kmem_free(mru->lists); 419 kmem_free(mru); 420 } 421 422 /* 423 * To insert an element, call xfs_mru_cache_insert() with the data store, the 424 * element's key and the client data pointer. This function returns 0 on 425 * success or ENOMEM if memory for the data element couldn't be allocated. 426 */ 427 int 428 xfs_mru_cache_insert( 429 struct xfs_mru_cache *mru, 430 unsigned long key, 431 struct xfs_mru_cache_elem *elem) 432 { 433 int error; 434 435 ASSERT(mru && mru->lists); 436 if (!mru || !mru->lists) 437 return EINVAL; 438 439 if (radix_tree_preload(GFP_KERNEL)) 440 return ENOMEM; 441 442 INIT_LIST_HEAD(&elem->list_node); 443 elem->key = key; 444 445 spin_lock(&mru->lock); 446 error = -radix_tree_insert(&mru->store, key, elem); 447 radix_tree_preload_end(); 448 if (!error) 449 _xfs_mru_cache_list_insert(mru, elem); 450 spin_unlock(&mru->lock); 451 452 return error; 453 } 454 455 /* 456 * To remove an element without calling the free function, call 457 * xfs_mru_cache_remove() with the data store and the element's key. On success 458 * the client data pointer for the removed element is returned, otherwise this 459 * function will return a NULL pointer. 460 */ 461 struct xfs_mru_cache_elem * 462 xfs_mru_cache_remove( 463 struct xfs_mru_cache *mru, 464 unsigned long key) 465 { 466 struct xfs_mru_cache_elem *elem; 467 468 ASSERT(mru && mru->lists); 469 if (!mru || !mru->lists) 470 return NULL; 471 472 spin_lock(&mru->lock); 473 elem = radix_tree_delete(&mru->store, key); 474 if (elem) 475 list_del(&elem->list_node); 476 spin_unlock(&mru->lock); 477 478 return elem; 479 } 480 481 /* 482 * To remove and element and call the free function, call xfs_mru_cache_delete() 483 * with the data store and the element's key. 484 */ 485 void 486 xfs_mru_cache_delete( 487 struct xfs_mru_cache *mru, 488 unsigned long key) 489 { 490 struct xfs_mru_cache_elem *elem; 491 492 elem = xfs_mru_cache_remove(mru, key); 493 if (elem) 494 mru->free_func(elem); 495 } 496 497 /* 498 * To look up an element using its key, call xfs_mru_cache_lookup() with the 499 * data store and the element's key. If found, the element will be moved to the 500 * head of the MRU list to indicate that it's been touched. 501 * 502 * The internal data structures are protected by a spinlock that is STILL HELD 503 * when this function returns. Call xfs_mru_cache_done() to release it. Note 504 * that it is not safe to call any function that might sleep in the interim. 505 * 506 * The implementation could have used reference counting to avoid this 507 * restriction, but since most clients simply want to get, set or test a member 508 * of the returned data structure, the extra per-element memory isn't warranted. 509 * 510 * If the element isn't found, this function returns NULL and the spinlock is 511 * released. xfs_mru_cache_done() should NOT be called when this occurs. 512 * 513 * Because sparse isn't smart enough to know about conditional lock return 514 * status, we need to help it get it right by annotating the path that does 515 * not release the lock. 516 */ 517 struct xfs_mru_cache_elem * 518 xfs_mru_cache_lookup( 519 struct xfs_mru_cache *mru, 520 unsigned long key) 521 { 522 struct xfs_mru_cache_elem *elem; 523 524 ASSERT(mru && mru->lists); 525 if (!mru || !mru->lists) 526 return NULL; 527 528 spin_lock(&mru->lock); 529 elem = radix_tree_lookup(&mru->store, key); 530 if (elem) { 531 list_del(&elem->list_node); 532 _xfs_mru_cache_list_insert(mru, elem); 533 __release(mru_lock); /* help sparse not be stupid */ 534 } else 535 spin_unlock(&mru->lock); 536 537 return elem; 538 } 539 540 /* 541 * To release the internal data structure spinlock after having performed an 542 * xfs_mru_cache_lookup() or an xfs_mru_cache_peek(), call xfs_mru_cache_done() 543 * with the data store pointer. 544 */ 545 void 546 xfs_mru_cache_done( 547 struct xfs_mru_cache *mru) 548 __releases(mru->lock) 549 { 550 spin_unlock(&mru->lock); 551 } 552