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
47 # include <libcfs/libcfs.h>
48 # include <linux/module.h>
49 # include <linux/jbd.h>
50 # include <asm/div64.h>
51 #else /* __KERNEL__ */
52 # include <liblustre.h>
53 # include <libcfs/list.h>
57 #include <obd_class.h>
58 #include <lustre_ver.h>
59 #include <obd_support.h>
60 #include <lprocfs_status.h>
62 #include <dt_object.h>
63 #include <md_object.h>
64 #include <lustre_req_layout.h>
65 #include <lustre_fld.h>
66 #include "fld_internal.h"
71 struct fld_cache *fld_cache_init(const char *name,
72 int cache_size, int cache_threshold)
74 struct fld_cache *cache;
77 LASSERT(name != NULL);
78 LASSERT(cache_threshold < cache_size);
82 RETURN(ERR_PTR(-ENOMEM));
84 CFS_INIT_LIST_HEAD(&cache->fci_entries_head);
85 CFS_INIT_LIST_HEAD(&cache->fci_lru);
87 cache->fci_cache_count = 0;
88 rwlock_init(&cache->fci_lock);
90 strlcpy(cache->fci_name, name,
91 sizeof(cache->fci_name));
93 cache->fci_cache_size = cache_size;
94 cache->fci_threshold = cache_threshold;
96 /* Init fld cache info. */
97 memset(&cache->fci_stat, 0, sizeof(cache->fci_stat));
99 CDEBUG(D_INFO, "%s: FLD cache - Size: %d, Threshold: %d\n",
100 cache->fci_name, cache_size, cache_threshold);
108 void fld_cache_fini(struct fld_cache *cache)
113 LASSERT(cache != NULL);
114 fld_cache_flush(cache);
116 if (cache->fci_stat.fst_count > 0) {
117 pct = cache->fci_stat.fst_cache * 100;
118 do_div(pct, cache->fci_stat.fst_count);
123 CDEBUG(D_INFO, "FLD cache statistics (%s):\n", cache->fci_name);
124 CDEBUG(D_INFO, " Total reqs: "LPU64"\n", cache->fci_stat.fst_count);
125 CDEBUG(D_INFO, " Cache reqs: "LPU64"\n", cache->fci_stat.fst_cache);
126 CDEBUG(D_INFO, " Cache hits: "LPU64"%%\n", pct);
134 * delete given node from list.
136 void fld_cache_entry_delete(struct fld_cache *cache,
137 struct fld_cache_entry *node)
139 cfs_list_del(&node->fce_list);
140 cfs_list_del(&node->fce_lru);
141 cache->fci_cache_count--;
146 * fix list by checking new entry with NEXT entry in order.
148 static void fld_fix_new_list(struct fld_cache *cache)
150 struct fld_cache_entry *f_curr;
151 struct fld_cache_entry *f_next;
152 struct lu_seq_range *c_range;
153 struct lu_seq_range *n_range;
154 cfs_list_t *head = &cache->fci_entries_head;
159 cfs_list_for_each_entry_safe(f_curr, f_next, head, fce_list) {
160 c_range = &f_curr->fce_range;
161 n_range = &f_next->fce_range;
163 LASSERT(range_is_sane(c_range));
164 if (&f_next->fce_list == head)
167 if (c_range->lsr_flags != n_range->lsr_flags)
170 LASSERTF(c_range->lsr_start <= n_range->lsr_start,
171 "cur lsr_start "DRANGE" next lsr_start "DRANGE"\n",
172 PRANGE(c_range), PRANGE(n_range));
174 /* check merge possibility with next range */
175 if (c_range->lsr_end == n_range->lsr_start) {
176 if (c_range->lsr_index != n_range->lsr_index)
178 n_range->lsr_start = c_range->lsr_start;
179 fld_cache_entry_delete(cache, f_curr);
183 /* check if current range overlaps with next range. */
184 if (n_range->lsr_start < c_range->lsr_end) {
185 if (c_range->lsr_index == n_range->lsr_index) {
186 n_range->lsr_start = c_range->lsr_start;
187 n_range->lsr_end = max(c_range->lsr_end,
189 fld_cache_entry_delete(cache, f_curr);
191 if (n_range->lsr_end <= c_range->lsr_end) {
193 fld_cache_entry_delete(cache, f_curr);
195 n_range->lsr_start = c_range->lsr_end;
198 /* we could have overlap over next
199 * range too. better restart. */
203 /* kill duplicates */
204 if (c_range->lsr_start == n_range->lsr_start &&
205 c_range->lsr_end == n_range->lsr_end)
206 fld_cache_entry_delete(cache, f_curr);
213 * add node to fld cache
215 static inline void fld_cache_entry_add(struct fld_cache *cache,
216 struct fld_cache_entry *f_new,
219 cfs_list_add(&f_new->fce_list, pos);
220 cfs_list_add(&f_new->fce_lru, &cache->fci_lru);
222 cache->fci_cache_count++;
223 fld_fix_new_list(cache);
227 * Check if cache needs to be shrunk. If so - do it.
228 * Remove one entry in list and so on until cache is shrunk enough.
230 static int fld_cache_shrink(struct fld_cache *cache)
232 struct fld_cache_entry *flde;
237 LASSERT(cache != NULL);
239 if (cache->fci_cache_count < cache->fci_cache_size)
242 curr = cache->fci_lru.prev;
244 while (cache->fci_cache_count + cache->fci_threshold >
245 cache->fci_cache_size && curr != &cache->fci_lru) {
247 flde = cfs_list_entry(curr, struct fld_cache_entry, fce_lru);
249 fld_cache_entry_delete(cache, flde);
253 CDEBUG(D_INFO, "%s: FLD cache - Shrunk by "
254 "%d entries\n", cache->fci_name, num);
260 * kill all fld cache entries.
262 void fld_cache_flush(struct fld_cache *cache)
266 write_lock(&cache->fci_lock);
267 cache->fci_cache_size = 0;
268 fld_cache_shrink(cache);
269 write_unlock(&cache->fci_lock);
275 * punch hole in existing range. divide this range and add new
279 void fld_cache_punch_hole(struct fld_cache *cache,
280 struct fld_cache_entry *f_curr,
281 struct fld_cache_entry *f_new)
283 const struct lu_seq_range *range = &f_new->fce_range;
284 const seqno_t new_start = range->lsr_start;
285 const seqno_t new_end = range->lsr_end;
286 struct fld_cache_entry *fldt;
289 OBD_ALLOC_GFP(fldt, sizeof *fldt, CFS_ALLOC_ATOMIC);
293 /* overlap is not allowed, so dont mess up list. */
296 /* break f_curr RANGE into three RANGES:
297 * f_curr, f_new , fldt
303 fldt->fce_range.lsr_start = new_end;
304 fldt->fce_range.lsr_end = f_curr->fce_range.lsr_end;
305 fldt->fce_range.lsr_index = f_curr->fce_range.lsr_index;
308 f_curr->fce_range.lsr_end = new_start;
310 /* add these two entries to list */
311 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
312 fld_cache_entry_add(cache, fldt, &f_new->fce_list);
314 /* no need to fixup */
319 * handle range overlap in fld cache.
321 static void fld_cache_overlap_handle(struct fld_cache *cache,
322 struct fld_cache_entry *f_curr,
323 struct fld_cache_entry *f_new)
325 const struct lu_seq_range *range = &f_new->fce_range;
326 const seqno_t new_start = range->lsr_start;
327 const seqno_t new_end = range->lsr_end;
328 const mdsno_t mdt = range->lsr_index;
330 /* this is overlap case, these case are checking overlapping with
331 * prev range only. fixup will handle overlaping with next range. */
333 if (f_curr->fce_range.lsr_index == mdt) {
334 f_curr->fce_range.lsr_start = min(f_curr->fce_range.lsr_start,
337 f_curr->fce_range.lsr_end = max(f_curr->fce_range.lsr_end,
341 fld_fix_new_list(cache);
343 } else if (new_start <= f_curr->fce_range.lsr_start &&
344 f_curr->fce_range.lsr_end <= new_end) {
345 /* case 1: new range completely overshadowed existing range.
346 * e.g. whole range migrated. update fld cache entry */
348 f_curr->fce_range = *range;
350 fld_fix_new_list(cache);
352 } else if (f_curr->fce_range.lsr_start < new_start &&
353 new_end < f_curr->fce_range.lsr_end) {
354 /* case 2: new range fit within existing range. */
356 fld_cache_punch_hole(cache, f_curr, f_new);
358 } else if (new_end <= f_curr->fce_range.lsr_end) {
360 * [new_start [c_start new_end) c_end)
363 LASSERT(new_start <= f_curr->fce_range.lsr_start);
365 f_curr->fce_range.lsr_start = new_end;
366 fld_cache_entry_add(cache, f_new, f_curr->fce_list.prev);
368 } else if (f_curr->fce_range.lsr_start <= new_start) {
370 * [c_start [new_start c_end) new_end)
373 LASSERT(f_curr->fce_range.lsr_end <= new_end);
375 f_curr->fce_range.lsr_end = new_start;
376 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
378 CERROR("NEW range ="DRANGE" curr = "DRANGE"\n",
379 PRANGE(range),PRANGE(&f_curr->fce_range));
382 struct fld_cache_entry
383 *fld_cache_entry_create(const struct lu_seq_range *range)
385 struct fld_cache_entry *f_new;
387 LASSERT(range_is_sane(range));
389 OBD_ALLOC_PTR(f_new);
391 RETURN(ERR_PTR(-ENOMEM));
393 f_new->fce_range = *range;
398 * Insert FLD entry in FLD cache.
400 * This function handles all cases of merging and breaking up of
403 int fld_cache_insert_nolock(struct fld_cache *cache,
404 struct fld_cache_entry *f_new)
406 struct fld_cache_entry *f_curr;
407 struct fld_cache_entry *n;
409 cfs_list_t *prev = NULL;
410 const seqno_t new_start = f_new->fce_range.lsr_start;
411 const seqno_t new_end = f_new->fce_range.lsr_end;
412 __u32 new_flags = f_new->fce_range.lsr_flags;
416 * Duplicate entries are eliminated in insert op.
417 * So we don't need to search new entry before starting
421 if (!cache->fci_no_shrink)
422 fld_cache_shrink(cache);
424 head = &cache->fci_entries_head;
426 cfs_list_for_each_entry_safe(f_curr, n, head, fce_list) {
427 /* add list if next is end of list */
428 if (new_end < f_curr->fce_range.lsr_start ||
429 (new_end == f_curr->fce_range.lsr_start &&
430 new_flags != f_curr->fce_range.lsr_flags))
433 prev = &f_curr->fce_list;
434 /* check if this range is to left of new range. */
435 if (new_start < f_curr->fce_range.lsr_end &&
436 new_flags == f_curr->fce_range.lsr_flags) {
437 fld_cache_overlap_handle(cache, f_curr, f_new);
445 CDEBUG(D_INFO, "insert range "DRANGE"\n", PRANGE(&f_new->fce_range));
446 /* Add new entry to cache and lru list. */
447 fld_cache_entry_add(cache, f_new, prev);
452 int fld_cache_insert(struct fld_cache *cache,
453 const struct lu_seq_range *range)
455 struct fld_cache_entry *flde;
458 flde = fld_cache_entry_create(range);
460 RETURN(PTR_ERR(flde));
462 write_lock(&cache->fci_lock);
463 rc = fld_cache_insert_nolock(cache, flde);
464 write_unlock(&cache->fci_lock);
471 void fld_cache_delete_nolock(struct fld_cache *cache,
472 const struct lu_seq_range *range)
474 struct fld_cache_entry *flde;
475 struct fld_cache_entry *tmp;
478 head = &cache->fci_entries_head;
479 cfs_list_for_each_entry_safe(flde, tmp, head, fce_list) {
480 /* add list if next is end of list */
481 if (range->lsr_start == flde->fce_range.lsr_start ||
482 (range->lsr_end == flde->fce_range.lsr_end &&
483 range->lsr_flags == flde->fce_range.lsr_flags)) {
484 fld_cache_entry_delete(cache, flde);
491 * Delete FLD entry in FLD cache.
494 void fld_cache_delete(struct fld_cache *cache,
495 const struct lu_seq_range *range)
497 write_lock(&cache->fci_lock);
498 fld_cache_delete_nolock(cache, range);
499 write_unlock(&cache->fci_lock);
502 struct fld_cache_entry
503 *fld_cache_entry_lookup_nolock(struct fld_cache *cache,
504 struct lu_seq_range *range)
506 struct fld_cache_entry *flde;
507 struct fld_cache_entry *got = NULL;
510 head = &cache->fci_entries_head;
511 cfs_list_for_each_entry(flde, head, fce_list) {
512 if (range->lsr_start == flde->fce_range.lsr_start ||
513 (range->lsr_end == flde->fce_range.lsr_end &&
514 range->lsr_flags == flde->fce_range.lsr_flags)) {
524 * lookup \a seq sequence for range in fld cache.
526 struct fld_cache_entry
527 *fld_cache_entry_lookup(struct fld_cache *cache, struct lu_seq_range *range)
529 struct fld_cache_entry *got = NULL;
532 read_lock(&cache->fci_lock);
533 got = fld_cache_entry_lookup_nolock(cache, range);
534 read_unlock(&cache->fci_lock);
539 * lookup \a seq sequence for range in fld cache.
541 int fld_cache_lookup(struct fld_cache *cache,
542 const seqno_t seq, struct lu_seq_range *range)
544 struct fld_cache_entry *flde;
545 struct fld_cache_entry *prev = NULL;
549 read_lock(&cache->fci_lock);
550 head = &cache->fci_entries_head;
552 cache->fci_stat.fst_count++;
553 cfs_list_for_each_entry(flde, head, fce_list) {
554 if (flde->fce_range.lsr_start > seq) {
556 *range = prev->fce_range;
561 if (range_within(&flde->fce_range, seq)) {
562 *range = flde->fce_range;
564 cache->fci_stat.fst_cache++;
565 read_unlock(&cache->fci_lock);
569 read_unlock(&cache->fci_lock);