4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License version 2 for more details (a copy is included
14 * in the LICENSE file that accompanied this code).
16 * You should have received a copy of the GNU General Public License
17 * version 2 along with this program; If not, see
18 * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
20 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
21 * CA 95054 USA or visit www.sun.com if you need additional information or
27 * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
28 * Use is subject to license terms.
30 * Copyright (c) 2012, 2013, Intel Corporation.
33 * This file is part of Lustre, http://www.lustre.org/
34 * Lustre is a trademark of Sun Microsystems, Inc.
36 * lustre/fld/fld_cache.c
38 * FLD (Fids Location Database)
40 * Author: Pravin Shelar <pravin.shelar@sun.com>
41 * Author: Yury Umanets <umka@clusterfs.com>
44 #define DEBUG_SUBSYSTEM S_FLD
46 #include <libcfs/libcfs.h>
47 #include <linux/module.h>
48 #include <linux/math64.h>
49 #include <obd_support.h>
50 #include <lustre_fld.h>
51 #include "fld_internal.h"
56 struct fld_cache *fld_cache_init(const char *name,
57 int cache_size, int cache_threshold)
59 struct fld_cache *cache;
62 LASSERT(name != NULL);
63 LASSERT(cache_threshold < cache_size);
67 RETURN(ERR_PTR(-ENOMEM));
69 INIT_LIST_HEAD(&cache->fci_entries_head);
70 INIT_LIST_HEAD(&cache->fci_lru);
72 cache->fci_cache_count = 0;
73 rwlock_init(&cache->fci_lock);
75 strlcpy(cache->fci_name, name,
76 sizeof(cache->fci_name));
78 cache->fci_cache_size = cache_size;
79 cache->fci_threshold = cache_threshold;
81 /* Init fld cache info. */
82 memset(&cache->fci_stat, 0, sizeof(cache->fci_stat));
84 CDEBUG(D_INFO, "%s: FLD cache - Size: %d, Threshold: %d\n",
85 cache->fci_name, cache_size, cache_threshold);
93 void fld_cache_fini(struct fld_cache *cache)
98 LASSERT(cache != NULL);
99 fld_cache_flush(cache);
101 if (cache->fci_stat.fst_count > 0) {
102 pct = cache->fci_stat.fst_cache * 100;
103 do_div(pct, cache->fci_stat.fst_count);
108 CDEBUG(D_INFO, "FLD cache statistics (%s):\n", cache->fci_name);
109 CDEBUG(D_INFO, " Total reqs: "LPU64"\n", cache->fci_stat.fst_count);
110 CDEBUG(D_INFO, " Cache reqs: "LPU64"\n", cache->fci_stat.fst_cache);
111 CDEBUG(D_INFO, " Cache hits: "LPU64"%%\n", pct);
119 * delete given node from list.
121 void fld_cache_entry_delete(struct fld_cache *cache,
122 struct fld_cache_entry *node)
124 list_del(&node->fce_list);
125 list_del(&node->fce_lru);
126 cache->fci_cache_count--;
131 * fix list by checking new entry with NEXT entry in order.
133 static void fld_fix_new_list(struct fld_cache *cache)
135 struct fld_cache_entry *f_curr;
136 struct fld_cache_entry *f_next;
137 struct lu_seq_range *c_range;
138 struct lu_seq_range *n_range;
139 struct list_head *head = &cache->fci_entries_head;
144 list_for_each_entry_safe(f_curr, f_next, head, fce_list) {
145 c_range = &f_curr->fce_range;
146 n_range = &f_next->fce_range;
148 LASSERT(range_is_sane(c_range));
149 if (&f_next->fce_list == head)
152 if (c_range->lsr_flags != n_range->lsr_flags)
155 LASSERTF(c_range->lsr_start <= n_range->lsr_start,
156 "cur lsr_start "DRANGE" next lsr_start "DRANGE"\n",
157 PRANGE(c_range), PRANGE(n_range));
159 /* check merge possibility with next range */
160 if (c_range->lsr_end == n_range->lsr_start) {
161 if (c_range->lsr_index != n_range->lsr_index)
163 n_range->lsr_start = c_range->lsr_start;
164 fld_cache_entry_delete(cache, f_curr);
168 /* check if current range overlaps with next range. */
169 if (n_range->lsr_start < c_range->lsr_end) {
170 if (c_range->lsr_index == n_range->lsr_index) {
171 n_range->lsr_start = c_range->lsr_start;
172 n_range->lsr_end = max(c_range->lsr_end,
174 fld_cache_entry_delete(cache, f_curr);
176 if (n_range->lsr_end <= c_range->lsr_end) {
178 fld_cache_entry_delete(cache, f_curr);
180 n_range->lsr_start = c_range->lsr_end;
183 /* we could have overlap over next
184 * range too. better restart. */
188 /* kill duplicates */
189 if (c_range->lsr_start == n_range->lsr_start &&
190 c_range->lsr_end == n_range->lsr_end)
191 fld_cache_entry_delete(cache, f_curr);
198 * add node to fld cache
200 static inline void fld_cache_entry_add(struct fld_cache *cache,
201 struct fld_cache_entry *f_new,
202 struct list_head *pos)
204 list_add(&f_new->fce_list, pos);
205 list_add(&f_new->fce_lru, &cache->fci_lru);
207 cache->fci_cache_count++;
208 fld_fix_new_list(cache);
212 * Check if cache needs to be shrunk. If so - do it.
213 * Remove one entry in list and so on until cache is shrunk enough.
215 static int fld_cache_shrink(struct fld_cache *cache)
217 struct fld_cache_entry *flde;
218 struct list_head *curr;
222 LASSERT(cache != NULL);
224 if (cache->fci_cache_count < cache->fci_cache_size)
227 curr = cache->fci_lru.prev;
229 while (cache->fci_cache_count + cache->fci_threshold >
230 cache->fci_cache_size && curr != &cache->fci_lru) {
232 flde = list_entry(curr, struct fld_cache_entry, fce_lru);
234 fld_cache_entry_delete(cache, flde);
238 CDEBUG(D_INFO, "%s: FLD cache - Shrunk by "
239 "%d entries\n", cache->fci_name, num);
245 * kill all fld cache entries.
247 void fld_cache_flush(struct fld_cache *cache)
251 write_lock(&cache->fci_lock);
252 cache->fci_cache_size = 0;
253 fld_cache_shrink(cache);
254 write_unlock(&cache->fci_lock);
260 * punch hole in existing range. divide this range and add new
264 static void fld_cache_punch_hole(struct fld_cache *cache,
265 struct fld_cache_entry *f_curr,
266 struct fld_cache_entry *f_new)
268 const struct lu_seq_range *range = &f_new->fce_range;
269 const u64 new_start = range->lsr_start;
270 const u64 new_end = range->lsr_end;
271 struct fld_cache_entry *fldt;
274 OBD_ALLOC_GFP(fldt, sizeof *fldt, GFP_ATOMIC);
278 /* overlap is not allowed, so dont mess up list. */
281 /* break f_curr RANGE into three RANGES:
282 * f_curr, f_new , fldt
288 fldt->fce_range.lsr_start = new_end;
289 fldt->fce_range.lsr_end = f_curr->fce_range.lsr_end;
290 fldt->fce_range.lsr_index = f_curr->fce_range.lsr_index;
293 f_curr->fce_range.lsr_end = new_start;
295 /* add these two entries to list */
296 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
297 fld_cache_entry_add(cache, fldt, &f_new->fce_list);
299 /* no need to fixup */
304 * handle range overlap in fld cache.
306 static void fld_cache_overlap_handle(struct fld_cache *cache,
307 struct fld_cache_entry *f_curr,
308 struct fld_cache_entry *f_new)
310 const struct lu_seq_range *range = &f_new->fce_range;
311 const u64 new_start = range->lsr_start;
312 const u64 new_end = range->lsr_end;
313 const u32 mdt = range->lsr_index;
315 /* this is overlap case, these case are checking overlapping with
316 * prev range only. fixup will handle overlaping with next range. */
318 if (f_curr->fce_range.lsr_index == mdt) {
319 f_curr->fce_range.lsr_start = min(f_curr->fce_range.lsr_start,
322 f_curr->fce_range.lsr_end = max(f_curr->fce_range.lsr_end,
326 fld_fix_new_list(cache);
328 } else if (new_start <= f_curr->fce_range.lsr_start &&
329 f_curr->fce_range.lsr_end <= new_end) {
330 /* case 1: new range completely overshadowed existing range.
331 * e.g. whole range migrated. update fld cache entry */
333 f_curr->fce_range = *range;
335 fld_fix_new_list(cache);
337 } else if (f_curr->fce_range.lsr_start < new_start &&
338 new_end < f_curr->fce_range.lsr_end) {
339 /* case 2: new range fit within existing range. */
341 fld_cache_punch_hole(cache, f_curr, f_new);
343 } else if (new_end <= f_curr->fce_range.lsr_end) {
345 * [new_start [c_start new_end) c_end)
348 LASSERT(new_start <= f_curr->fce_range.lsr_start);
350 f_curr->fce_range.lsr_start = new_end;
351 fld_cache_entry_add(cache, f_new, f_curr->fce_list.prev);
353 } else if (f_curr->fce_range.lsr_start <= new_start) {
355 * [c_start [new_start c_end) new_end)
358 LASSERT(f_curr->fce_range.lsr_end <= new_end);
360 f_curr->fce_range.lsr_end = new_start;
361 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
363 CERROR("NEW range ="DRANGE" curr = "DRANGE"\n",
364 PRANGE(range),PRANGE(&f_curr->fce_range));
367 struct fld_cache_entry
368 *fld_cache_entry_create(const struct lu_seq_range *range)
370 struct fld_cache_entry *f_new;
372 LASSERT(range_is_sane(range));
374 OBD_ALLOC_PTR(f_new);
376 RETURN(ERR_PTR(-ENOMEM));
378 f_new->fce_range = *range;
383 * Insert FLD entry in FLD cache.
385 * This function handles all cases of merging and breaking up of
388 int fld_cache_insert_nolock(struct fld_cache *cache,
389 struct fld_cache_entry *f_new)
391 struct fld_cache_entry *f_curr;
392 struct fld_cache_entry *n;
393 struct list_head *head;
394 struct list_head *prev = NULL;
395 const u64 new_start = f_new->fce_range.lsr_start;
396 const u64 new_end = f_new->fce_range.lsr_end;
397 __u32 new_flags = f_new->fce_range.lsr_flags;
401 * Duplicate entries are eliminated in insert op.
402 * So we don't need to search new entry before starting
406 if (!cache->fci_no_shrink)
407 fld_cache_shrink(cache);
409 head = &cache->fci_entries_head;
411 list_for_each_entry_safe(f_curr, n, head, fce_list) {
412 /* add list if next is end of list */
413 if (new_end < f_curr->fce_range.lsr_start ||
414 (new_end == f_curr->fce_range.lsr_start &&
415 new_flags != f_curr->fce_range.lsr_flags))
418 prev = &f_curr->fce_list;
419 /* check if this range is to left of new range. */
420 if (new_start < f_curr->fce_range.lsr_end &&
421 new_flags == f_curr->fce_range.lsr_flags) {
422 fld_cache_overlap_handle(cache, f_curr, f_new);
430 CDEBUG(D_INFO, "insert range "DRANGE"\n", PRANGE(&f_new->fce_range));
431 /* Add new entry to cache and lru list. */
432 fld_cache_entry_add(cache, f_new, prev);
437 int fld_cache_insert(struct fld_cache *cache,
438 const struct lu_seq_range *range)
440 struct fld_cache_entry *flde;
443 flde = fld_cache_entry_create(range);
445 RETURN(PTR_ERR(flde));
447 write_lock(&cache->fci_lock);
448 rc = fld_cache_insert_nolock(cache, flde);
449 write_unlock(&cache->fci_lock);
456 void fld_cache_delete_nolock(struct fld_cache *cache,
457 const struct lu_seq_range *range)
459 struct fld_cache_entry *flde;
460 struct fld_cache_entry *tmp;
461 struct list_head *head;
463 head = &cache->fci_entries_head;
464 list_for_each_entry_safe(flde, tmp, head, fce_list) {
465 /* add list if next is end of list */
466 if (range->lsr_start == flde->fce_range.lsr_start ||
467 (range->lsr_end == flde->fce_range.lsr_end &&
468 range->lsr_flags == flde->fce_range.lsr_flags)) {
469 fld_cache_entry_delete(cache, flde);
476 * Delete FLD entry in FLD cache.
479 void fld_cache_delete(struct fld_cache *cache,
480 const struct lu_seq_range *range)
482 write_lock(&cache->fci_lock);
483 fld_cache_delete_nolock(cache, range);
484 write_unlock(&cache->fci_lock);
487 struct fld_cache_entry *
488 fld_cache_entry_lookup_nolock(struct fld_cache *cache,
489 const struct lu_seq_range *range)
491 struct fld_cache_entry *flde;
492 struct fld_cache_entry *got = NULL;
493 struct list_head *head;
495 head = &cache->fci_entries_head;
496 list_for_each_entry(flde, head, fce_list) {
497 if (range->lsr_start == flde->fce_range.lsr_start ||
498 (range->lsr_end == flde->fce_range.lsr_end &&
499 range->lsr_flags == flde->fce_range.lsr_flags)) {
509 * lookup \a seq sequence for range in fld cache.
511 struct fld_cache_entry *
512 fld_cache_entry_lookup(struct fld_cache *cache,
513 const struct lu_seq_range *range)
515 struct fld_cache_entry *got = NULL;
518 read_lock(&cache->fci_lock);
519 got = fld_cache_entry_lookup_nolock(cache, range);
520 read_unlock(&cache->fci_lock);
526 * lookup \a seq sequence for range in fld cache.
528 int fld_cache_lookup(struct fld_cache *cache,
529 const u64 seq, struct lu_seq_range *range)
531 struct fld_cache_entry *flde;
532 struct fld_cache_entry *prev = NULL;
533 struct list_head *head;
536 read_lock(&cache->fci_lock);
537 head = &cache->fci_entries_head;
539 cache->fci_stat.fst_count++;
540 list_for_each_entry(flde, head, fce_list) {
541 if (flde->fce_range.lsr_start > seq) {
543 *range = prev->fce_range;
548 if (range_within(&flde->fce_range, seq)) {
549 *range = flde->fce_range;
551 cache->fci_stat.fst_cache++;
552 read_unlock(&cache->fci_lock);
556 read_unlock(&cache->fci_lock);