Commit | Line | Data |
---|---|---|
2a82b8be DC |
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 | */ | |
22328d71 CH |
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 | }; | |
2a82b8be | 116 | |
2a82b8be DC |
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( | |
22328d71 CH |
138 | struct xfs_mru_cache *mru, |
139 | unsigned long now) | |
2a82b8be | 140 | { |
22328d71 CH |
141 | unsigned int grp; |
142 | unsigned int migrated = 0; | |
143 | struct list_head *lru_list; | |
2a82b8be DC |
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( | |
22328d71 CH |
202 | struct xfs_mru_cache *mru, |
203 | struct xfs_mru_cache_elem *elem) | |
2a82b8be | 204 | { |
22328d71 CH |
205 | unsigned int grp = 0; |
206 | unsigned long now = jiffies; | |
2a82b8be DC |
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; | |
65de5567 DC |
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 | } | |
2a82b8be DC |
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. | |
a8272ce0 DC |
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. | |
2a82b8be DC |
237 | */ |
238 | STATIC void | |
239 | _xfs_mru_cache_clear_reap_list( | |
22328d71 CH |
240 | struct xfs_mru_cache *mru) |
241 | __releases(mru->lock) __acquires(mru->lock) | |
2a82b8be | 242 | { |
22328d71 | 243 | struct xfs_mru_cache_elem *elem, *next; |
2a82b8be DC |
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 | } | |
ba74d0cb | 258 | spin_unlock(&mru->lock); |
2a82b8be DC |
259 | |
260 | list_for_each_entry_safe(elem, next, &tmp, list_node) { | |
2a82b8be | 261 | list_del_init(&elem->list_node); |
22328d71 | 262 | mru->free_func(elem); |
2a82b8be DC |
263 | } |
264 | ||
ba74d0cb | 265 | spin_lock(&mru->lock); |
2a82b8be DC |
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 | { | |
22328d71 CH |
279 | struct xfs_mru_cache *mru = |
280 | container_of(work, struct xfs_mru_cache, work.work); | |
65de5567 | 281 | unsigned long now, next; |
2a82b8be DC |
282 | |
283 | ASSERT(mru && mru->lists); | |
284 | if (!mru || !mru->lists) | |
285 | return; | |
286 | ||
ba74d0cb | 287 | spin_lock(&mru->lock); |
65de5567 DC |
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); | |
2a82b8be DC |
299 | } |
300 | ||
ba74d0cb | 301 | spin_unlock(&mru->lock); |
2a82b8be DC |
302 | } |
303 | ||
304 | int | |
305 | xfs_mru_cache_init(void) | |
306 | { | |
8018ec08 BF |
307 | xfs_mru_reap_wq = alloc_workqueue("xfs_mru_cache", |
308 | WQ_MEM_RECLAIM|WQ_FREEZABLE, 1); | |
9f8868ff | 309 | if (!xfs_mru_reap_wq) |
22328d71 | 310 | return -ENOMEM; |
2a82b8be DC |
311 | return 0; |
312 | } | |
313 | ||
314 | void | |
315 | xfs_mru_cache_uninit(void) | |
316 | { | |
317 | destroy_workqueue(xfs_mru_reap_wq); | |
2a82b8be DC |
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( | |
22328d71 | 328 | struct xfs_mru_cache **mrup, |
2a82b8be DC |
329 | unsigned int lifetime_ms, |
330 | unsigned int grp_count, | |
331 | xfs_mru_cache_free_func_t free_func) | |
332 | { | |
22328d71 CH |
333 | struct xfs_mru_cache *mru = NULL; |
334 | int err = 0, grp; | |
335 | unsigned int grp_time; | |
2a82b8be DC |
336 | |
337 | if (mrup) | |
338 | *mrup = NULL; | |
339 | ||
340 | if (!mrup || !grp_count || !lifetime_ms || !free_func) | |
2451337d | 341 | return -EINVAL; |
2a82b8be DC |
342 | |
343 | if (!(grp_time = msecs_to_jiffies(lifetime_ms) / grp_count)) | |
2451337d | 344 | return -EINVAL; |
2a82b8be DC |
345 | |
346 | if (!(mru = kmem_zalloc(sizeof(*mru), KM_SLEEP))) | |
2451337d | 347 | return -ENOMEM; |
2a82b8be DC |
348 | |
349 | /* An extra list is needed to avoid reaping up to a grp_time early. */ | |
350 | mru->grp_count = grp_count + 1; | |
65de5567 | 351 | mru->lists = kmem_zalloc(mru->grp_count * sizeof(*mru->lists), KM_SLEEP); |
2a82b8be DC |
352 | |
353 | if (!mru->lists) { | |
2451337d | 354 | err = -ENOMEM; |
2a82b8be DC |
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); | |
007c61c6 | 367 | spin_lock_init(&mru->lock); |
2a82b8be DC |
368 | INIT_DELAYED_WORK(&mru->work, _xfs_mru_cache_reap); |
369 | ||
370 | mru->grp_time = grp_time; | |
371 | mru->free_func = free_func; | |
372 | ||
2a82b8be DC |
373 | *mrup = mru; |
374 | ||
375 | exit: | |
376 | if (err && mru && mru->lists) | |
f0e2d93c | 377 | kmem_free(mru->lists); |
2a82b8be | 378 | if (err && mru) |
f0e2d93c | 379 | kmem_free(mru); |
2a82b8be DC |
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 | |
65de5567 | 388 | * executing and the reaper is not running. |
2a82b8be | 389 | */ |
b657fc82 | 390 | static void |
2a82b8be | 391 | xfs_mru_cache_flush( |
22328d71 | 392 | struct xfs_mru_cache *mru) |
2a82b8be DC |
393 | { |
394 | if (!mru || !mru->lists) | |
395 | return; | |
396 | ||
ba74d0cb | 397 | spin_lock(&mru->lock); |
65de5567 | 398 | if (mru->queued) { |
ba74d0cb | 399 | spin_unlock(&mru->lock); |
afe2c511 | 400 | cancel_delayed_work_sync(&mru->work); |
ba74d0cb | 401 | spin_lock(&mru->lock); |
65de5567 | 402 | } |
2a82b8be | 403 | |
65de5567 DC |
404 | _xfs_mru_cache_migrate(mru, jiffies + mru->grp_count * mru->grp_time); |
405 | _xfs_mru_cache_clear_reap_list(mru); | |
2a82b8be | 406 | |
ba74d0cb | 407 | spin_unlock(&mru->lock); |
2a82b8be DC |
408 | } |
409 | ||
410 | void | |
411 | xfs_mru_cache_destroy( | |
22328d71 | 412 | struct xfs_mru_cache *mru) |
2a82b8be DC |
413 | { |
414 | if (!mru || !mru->lists) | |
415 | return; | |
416 | ||
65de5567 | 417 | xfs_mru_cache_flush(mru); |
2a82b8be | 418 | |
f0e2d93c DV |
419 | kmem_free(mru->lists); |
420 | kmem_free(mru); | |
2a82b8be DC |
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( | |
22328d71 CH |
430 | struct xfs_mru_cache *mru, |
431 | unsigned long key, | |
432 | struct xfs_mru_cache_elem *elem) | |
2a82b8be | 433 | { |
22328d71 | 434 | int error; |
2a82b8be DC |
435 | |
436 | ASSERT(mru && mru->lists); | |
437 | if (!mru || !mru->lists) | |
2451337d | 438 | return -EINVAL; |
2a82b8be | 439 | |
20dafeef | 440 | if (radix_tree_preload(GFP_NOFS)) |
2451337d | 441 | return -ENOMEM; |
2a82b8be | 442 | |
2a82b8be DC |
443 | INIT_LIST_HEAD(&elem->list_node); |
444 | elem->key = key; | |
2a82b8be | 445 | |
ba74d0cb | 446 | spin_lock(&mru->lock); |
2451337d | 447 | error = radix_tree_insert(&mru->store, key, elem); |
2a82b8be | 448 | radix_tree_preload_end(); |
22328d71 CH |
449 | if (!error) |
450 | _xfs_mru_cache_list_insert(mru, elem); | |
ba74d0cb | 451 | spin_unlock(&mru->lock); |
2a82b8be | 452 | |
ce695c65 | 453 | return error; |
2a82b8be DC |
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 | */ | |
22328d71 | 462 | struct xfs_mru_cache_elem * |
2a82b8be | 463 | xfs_mru_cache_remove( |
22328d71 CH |
464 | struct xfs_mru_cache *mru, |
465 | unsigned long key) | |
2a82b8be | 466 | { |
22328d71 | 467 | struct xfs_mru_cache_elem *elem; |
2a82b8be DC |
468 | |
469 | ASSERT(mru && mru->lists); | |
470 | if (!mru || !mru->lists) | |
471 | return NULL; | |
472 | ||
ba74d0cb | 473 | spin_lock(&mru->lock); |
2a82b8be | 474 | elem = radix_tree_delete(&mru->store, key); |
22328d71 | 475 | if (elem) |
2a82b8be | 476 | list_del(&elem->list_node); |
ba74d0cb | 477 | spin_unlock(&mru->lock); |
2a82b8be | 478 | |
22328d71 | 479 | return elem; |
2a82b8be DC |
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( | |
22328d71 CH |
488 | struct xfs_mru_cache *mru, |
489 | unsigned long key) | |
2a82b8be | 490 | { |
22328d71 | 491 | struct xfs_mru_cache_elem *elem; |
2a82b8be | 492 | |
22328d71 CH |
493 | elem = xfs_mru_cache_remove(mru, key); |
494 | if (elem) | |
495 | mru->free_func(elem); | |
2a82b8be DC |
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. | |
a8272ce0 DC |
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. | |
2a82b8be | 517 | */ |
22328d71 | 518 | struct xfs_mru_cache_elem * |
2a82b8be | 519 | xfs_mru_cache_lookup( |
22328d71 CH |
520 | struct xfs_mru_cache *mru, |
521 | unsigned long key) | |
2a82b8be | 522 | { |
22328d71 | 523 | struct xfs_mru_cache_elem *elem; |
2a82b8be DC |
524 | |
525 | ASSERT(mru && mru->lists); | |
526 | if (!mru || !mru->lists) | |
527 | return NULL; | |
528 | ||
ba74d0cb | 529 | spin_lock(&mru->lock); |
2a82b8be DC |
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); | |
a8272ce0 DC |
534 | __release(mru_lock); /* help sparse not be stupid */ |
535 | } else | |
ba74d0cb | 536 | spin_unlock(&mru->lock); |
2a82b8be | 537 | |
22328d71 | 538 | return elem; |
2a82b8be DC |
539 | } |
540 | ||
2a82b8be DC |
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( | |
22328d71 CH |
548 | struct xfs_mru_cache *mru) |
549 | __releases(mru->lock) | |
2a82b8be | 550 | { |
ba74d0cb | 551 | spin_unlock(&mru->lock); |
2a82b8be | 552 | } |