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.
31 * This file is part of Lustre, http://www.lustre.org/
32 * Lustre is a trademark of Sun Microsystems, Inc.
34 * lustre/fld/fld_cache.c
36 * FLD (Fids Location Database)
38 * Author: Pravin Shelar <pravin.shelar@sun.com>
39 * Author: Yury Umanets <umka@clusterfs.com>
42 #define DEBUG_SUBSYSTEM S_FLD
45 # include <libcfs/libcfs.h>
46 # include <linux/module.h>
47 # include <linux/jbd.h>
48 # include <asm/div64.h>
49 #else /* __KERNEL__ */
50 # include <liblustre.h>
51 # include <libcfs/list.h>
55 #include <obd_class.h>
56 #include <lustre_ver.h>
57 #include <obd_support.h>
58 #include <lprocfs_status.h>
60 #include <dt_object.h>
61 #include <md_object.h>
62 #include <lustre_req_layout.h>
63 #include <lustre_fld.h>
64 #include "fld_internal.h"
69 struct fld_cache *fld_cache_init(const char *name,
70 int cache_size, int cache_threshold)
72 struct fld_cache *cache;
75 LASSERT(name != NULL);
76 LASSERT(cache_threshold < cache_size);
80 RETURN(ERR_PTR(-ENOMEM));
82 CFS_INIT_LIST_HEAD(&cache->fci_entries_head);
83 CFS_INIT_LIST_HEAD(&cache->fci_lru);
85 cache->fci_cache_count = 0;
86 cfs_spin_lock_init(&cache->fci_lock);
88 strncpy(cache->fci_name, name,
89 sizeof(cache->fci_name));
91 cache->fci_cache_size = cache_size;
92 cache->fci_threshold = cache_threshold;
94 /* Init fld cache info. */
95 memset(&cache->fci_stat, 0, sizeof(cache->fci_stat));
97 CDEBUG(D_INFO, "%s: FLD cache - Size: %d, Threshold: %d\n",
98 cache->fci_name, cache_size, cache_threshold);
106 void fld_cache_fini(struct fld_cache *cache)
111 LASSERT(cache != NULL);
112 fld_cache_flush(cache);
114 if (cache->fci_stat.fst_count > 0) {
115 pct = cache->fci_stat.fst_cache * 100;
116 do_div(pct, cache->fci_stat.fst_count);
121 CDEBUG(D_INFO, "FLD cache statistics (%s):\n", cache->fci_name);
122 CDEBUG(D_INFO, " Total reqs: "LPU64"\n", cache->fci_stat.fst_count);
123 CDEBUG(D_INFO, " Cache reqs: "LPU64"\n", cache->fci_stat.fst_cache);
124 CDEBUG(D_INFO, " Cache hits: "LPU64"%%\n", pct);
132 * delete given node from list.
134 static inline void fld_cache_entry_delete(struct fld_cache *cache,
135 struct fld_cache_entry *node)
137 cfs_list_del(&node->fce_list);
138 cfs_list_del(&node->fce_lru);
139 cache->fci_cache_count--;
144 * fix list by checking new entry with NEXT entry in order.
146 static void fld_fix_new_list(struct fld_cache *cache)
148 struct fld_cache_entry *f_curr;
149 struct fld_cache_entry *f_next;
150 struct lu_seq_range *c_range;
151 struct lu_seq_range *n_range;
152 cfs_list_t *head = &cache->fci_entries_head;
157 cfs_list_for_each_entry_safe(f_curr, f_next, head, fce_list) {
158 c_range = &f_curr->fce_range;
159 n_range = &f_next->fce_range;
161 LASSERT(range_is_sane(c_range));
162 if (&f_next->fce_list == head)
165 LASSERT(c_range->lsr_start <= n_range->lsr_start);
167 /* check merge possibility with next range */
168 if (c_range->lsr_end == n_range->lsr_start) {
169 if (c_range->lsr_index != n_range->lsr_index)
171 n_range->lsr_start = c_range->lsr_start;
172 fld_cache_entry_delete(cache, f_curr);
176 /* check if current range overlaps with next range. */
177 if (n_range->lsr_start < c_range->lsr_end) {
179 if (c_range->lsr_index == n_range->lsr_index) {
180 n_range->lsr_start = c_range->lsr_start;
181 n_range->lsr_end = max(c_range->lsr_end,
184 fld_cache_entry_delete(cache, f_curr);
186 if (n_range->lsr_end <= c_range->lsr_end) {
188 fld_cache_entry_delete(cache, f_curr);
190 n_range->lsr_start = c_range->lsr_end;
193 /* we could have overlap over next
194 * range too. better restart. */
198 /* kill duplicates */
199 if (c_range->lsr_start == n_range->lsr_start &&
200 c_range->lsr_end == n_range->lsr_end)
201 fld_cache_entry_delete(cache, f_curr);
208 * add node to fld cache
210 static inline void fld_cache_entry_add(struct fld_cache *cache,
211 struct fld_cache_entry *f_new,
214 cfs_list_add(&f_new->fce_list, pos);
215 cfs_list_add(&f_new->fce_lru, &cache->fci_lru);
217 cache->fci_cache_count++;
218 fld_fix_new_list(cache);
222 * Check if cache needs to be shrunk. If so - do it.
223 * Remove one entry in list and so on until cache is shrunk enough.
225 static int fld_cache_shrink(struct fld_cache *cache)
227 struct fld_cache_entry *flde;
232 LASSERT(cache != NULL);
234 if (cache->fci_cache_count < cache->fci_cache_size)
237 curr = cache->fci_lru.prev;
239 while (cache->fci_cache_count + cache->fci_threshold >
240 cache->fci_cache_size && curr != &cache->fci_lru) {
242 flde = cfs_list_entry(curr, struct fld_cache_entry, fce_lru);
244 fld_cache_entry_delete(cache, flde);
248 CDEBUG(D_INFO, "%s: FLD cache - Shrunk by "
249 "%d entries\n", cache->fci_name, num);
255 * kill all fld cache entries.
257 void fld_cache_flush(struct fld_cache *cache)
261 cfs_spin_lock(&cache->fci_lock);
262 cache->fci_cache_size = 0;
263 fld_cache_shrink(cache);
264 cfs_spin_unlock(&cache->fci_lock);
270 * punch hole in existing range. divide this range and add new
274 void fld_cache_punch_hole(struct fld_cache *cache,
275 struct fld_cache_entry *f_curr,
276 struct fld_cache_entry *f_new)
278 const struct lu_seq_range *range = &f_new->fce_range;
279 const seqno_t new_start = range->lsr_start;
280 const seqno_t new_end = range->lsr_end;
281 struct fld_cache_entry *fldt;
284 OBD_ALLOC_GFP(fldt, sizeof *fldt, CFS_ALLOC_ATOMIC);
288 /* overlap is not allowed, so dont mess up list. */
291 /* break f_curr RANGE into three RANGES:
292 * f_curr, f_new , fldt
298 fldt->fce_range.lsr_start = new_end;
299 fldt->fce_range.lsr_end = f_curr->fce_range.lsr_end;
300 fldt->fce_range.lsr_index = f_curr->fce_range.lsr_index;
303 f_curr->fce_range.lsr_end = new_start;
305 /* add these two entries to list */
306 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
307 fld_cache_entry_add(cache, fldt, &f_new->fce_list);
309 /* no need to fixup */
314 * handle range overlap in fld cache.
316 void fld_cache_overlap_handle(struct fld_cache *cache,
317 struct fld_cache_entry *f_curr,
318 struct fld_cache_entry *f_new)
320 const struct lu_seq_range *range = &f_new->fce_range;
321 const seqno_t new_start = range->lsr_start;
322 const seqno_t new_end = range->lsr_end;
323 const mdsno_t mdt = range->lsr_index;
325 /* this is overlap case, these case are checking overlapping with
326 * prev range only. fixup will handle overlaping with next range. */
328 if (f_curr->fce_range.lsr_index == mdt) {
329 f_curr->fce_range.lsr_start = min(f_curr->fce_range.lsr_start,
332 f_curr->fce_range.lsr_end = max(f_curr->fce_range.lsr_end,
336 fld_fix_new_list(cache);
338 } else if (new_start <= f_curr->fce_range.lsr_start &&
339 f_curr->fce_range.lsr_end <= new_end) {
340 /* case 1: new range completely overshadowed existing range.
341 * e.g. whole range migrated. update fld cache entry */
343 f_curr->fce_range = *range;
345 fld_fix_new_list(cache);
347 } else if (f_curr->fce_range.lsr_start < new_start &&
348 new_end < f_curr->fce_range.lsr_end) {
349 /* case 2: new range fit within existing range. */
351 fld_cache_punch_hole(cache, f_curr, f_new);
353 } else if (new_end <= f_curr->fce_range.lsr_end) {
355 * [new_start [c_start new_end) c_end)
358 LASSERT(new_start <= f_curr->fce_range.lsr_start);
360 f_curr->fce_range.lsr_start = new_end;
361 fld_cache_entry_add(cache, f_new, f_curr->fce_list.prev);
363 } else if (f_curr->fce_range.lsr_start <= new_start) {
365 * [c_start [new_start c_end) new_end)
368 LASSERT(f_curr->fce_range.lsr_end <= new_end);
370 f_curr->fce_range.lsr_end = new_start;
371 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
373 CERROR("NEW range ="DRANGE" curr = "DRANGE"\n",
374 PRANGE(range),PRANGE(&f_curr->fce_range));
378 * Insert FLD entry in FLD cache.
380 * This function handles all cases of merging and breaking up of
383 void fld_cache_insert(struct fld_cache *cache,
384 const struct lu_seq_range *range)
386 struct fld_cache_entry *f_new;
387 struct fld_cache_entry *f_curr;
388 struct fld_cache_entry *n;
390 cfs_list_t *prev = NULL;
391 const seqno_t new_start = range->lsr_start;
392 const seqno_t new_end = range->lsr_end;
395 LASSERT(range_is_sane(range));
397 /* Allocate new entry. */
398 OBD_ALLOC_PTR(f_new);
404 f_new->fce_range = *range;
407 * Duplicate entries are eliminated in inset op.
408 * So we don't need to search new entry before starting insertion loop.
411 cfs_spin_lock(&cache->fci_lock);
412 fld_cache_shrink(cache);
414 head = &cache->fci_entries_head;
416 cfs_list_for_each_entry_safe(f_curr, n, head, fce_list) {
417 /* add list if next is end of list */
418 if (new_end < f_curr->fce_range.lsr_start)
421 prev = &f_curr->fce_list;
422 /* check if this range is to left of new range. */
423 if (new_start < f_curr->fce_range.lsr_end) {
424 fld_cache_overlap_handle(cache, f_curr, f_new);
432 /* Add new entry to cache and lru list. */
433 fld_cache_entry_add(cache, f_new, prev);
435 cfs_spin_unlock(&cache->fci_lock);
440 * lookup \a seq sequence for range in fld cache.
442 int fld_cache_lookup(struct fld_cache *cache,
443 const seqno_t seq, struct lu_seq_range *range)
445 struct fld_cache_entry *flde;
450 cfs_spin_lock(&cache->fci_lock);
451 head = &cache->fci_entries_head;
453 cache->fci_stat.fst_count++;
454 cfs_list_for_each_entry(flde, head, fce_list) {
455 if (flde->fce_range.lsr_start > seq)
458 if (range_within(&flde->fce_range, seq)) {
459 *range = flde->fce_range;
461 /* update position of this entry in lru list. */
462 cfs_list_move(&flde->fce_lru, &cache->fci_lru);
463 cache->fci_stat.fst_cache++;
464 cfs_spin_unlock(&cache->fci_lock);
468 cfs_spin_unlock(&cache->fci_lock);