Whamcloud - gitweb
ccfd3811e2205c0aa0faf9f59baaff465749a912
[fs/lustre-release.git] / lustre / fld / fld_cache.c
1 /*
2  * GPL HEADER START
3  *
4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5  *
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.
9  *
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).
15  *
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
19  *
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
22  * have any questions.
23  *
24  * GPL HEADER END
25  */
26 /*
27  * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
28  * Use is subject to license terms.
29  */
30 /*
31  * This file is part of Lustre, http://www.lustre.org/
32  * Lustre is a trademark of Sun Microsystems, Inc.
33  *
34  * lustre/fld/fld_cache.c
35  *
36  * FLD (Fids Location Database)
37  *
38  * Author: Pravin Shelar <pravin.shelar@sun.com>
39  * Author: Yury Umanets <umka@clusterfs.com>
40  */
41
42 #define DEBUG_SUBSYSTEM S_FLD
43
44 #ifdef __KERNEL__
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>
52 #endif
53
54 #include <obd.h>
55 #include <obd_class.h>
56 #include <lustre_ver.h>
57 #include <obd_support.h>
58 #include <lprocfs_status.h>
59
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"
65
66 /**
67  * create fld cache.
68  */
69 struct fld_cache *fld_cache_init(const char *name,
70                                  int cache_size, int cache_threshold)
71 {
72         struct fld_cache *cache;
73         ENTRY;
74
75         LASSERT(name != NULL);
76         LASSERT(cache_threshold < cache_size);
77
78         OBD_ALLOC_PTR(cache);
79         if (cache == NULL)
80                 RETURN(ERR_PTR(-ENOMEM));
81
82         CFS_INIT_LIST_HEAD(&cache->fci_entries_head);
83         CFS_INIT_LIST_HEAD(&cache->fci_lru);
84
85         cache->fci_cache_count = 0;
86         spin_lock_init(&cache->fci_lock);
87
88         strncpy(cache->fci_name, name,
89                 sizeof(cache->fci_name));
90
91         cache->fci_cache_size = cache_size;
92         cache->fci_threshold = cache_threshold;
93
94         /* Init fld cache info. */
95         memset(&cache->fci_stat, 0, sizeof(cache->fci_stat));
96
97         CDEBUG(D_INFO, "%s: FLD cache - Size: %d, Threshold: %d\n",
98                cache->fci_name, cache_size, cache_threshold);
99
100         RETURN(cache);
101 }
102
103 /**
104  * destroy fld cache.
105  */
106 void fld_cache_fini(struct fld_cache *cache)
107 {
108         __u64 pct;
109         ENTRY;
110
111         LASSERT(cache != NULL);
112         fld_cache_flush(cache);
113
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);
117         } else {
118                 pct = 0;
119         }
120
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);
125
126         OBD_FREE_PTR(cache);
127
128         EXIT;
129 }
130
131 /**
132  * delete given node from list.
133  */
134 static inline void fld_cache_entry_delete(struct fld_cache *cache,
135                                           struct fld_cache_entry *node)
136 {
137         cfs_list_del(&node->fce_list);
138         cfs_list_del(&node->fce_lru);
139         cache->fci_cache_count--;
140         OBD_FREE_PTR(node);
141 }
142
143 /**
144  * fix list by checking new entry with NEXT entry in order.
145  */
146 static void fld_fix_new_list(struct fld_cache *cache)
147 {
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;
153         ENTRY;
154
155 restart_fixup:
156
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;
160
161                 LASSERT(range_is_sane(c_range));
162                 if (&f_next->fce_list == head)
163                         break;
164
165                 if (c_range->lsr_flags != n_range->lsr_flags)
166                         continue;
167
168                 LASSERTF(c_range->lsr_start <= n_range->lsr_start,
169                          "cur lsr_start "DRANGE" next lsr_start "DRANGE"\n",
170                          PRANGE(c_range), PRANGE(n_range));
171
172                 /* check merge possibility with next range */
173                 if (c_range->lsr_end == n_range->lsr_start) {
174                         if (c_range->lsr_index != n_range->lsr_index)
175                                 continue;
176                         n_range->lsr_start = c_range->lsr_start;
177                         fld_cache_entry_delete(cache, f_curr);
178                         continue;
179                 }
180
181                 /* check if current range overlaps with next range. */
182                 if (n_range->lsr_start < c_range->lsr_end) {
183                         if (c_range->lsr_index == n_range->lsr_index) {
184                                 n_range->lsr_start = c_range->lsr_start;
185                                 n_range->lsr_end = max(c_range->lsr_end,
186                                                        n_range->lsr_end);
187                                 fld_cache_entry_delete(cache, f_curr);
188                         } else {
189                                 if (n_range->lsr_end <= c_range->lsr_end) {
190                                         *n_range = *c_range;
191                                         fld_cache_entry_delete(cache, f_curr);
192                                 } else
193                                         n_range->lsr_start = c_range->lsr_end;
194                         }
195
196                         /* we could have overlap over next
197                          * range too. better restart. */
198                         goto restart_fixup;
199                 }
200
201                 /* kill duplicates */
202                 if (c_range->lsr_start == n_range->lsr_start &&
203                     c_range->lsr_end == n_range->lsr_end)
204                         fld_cache_entry_delete(cache, f_curr);
205         }
206
207         EXIT;
208 }
209
210 /**
211  * add node to fld cache
212  */
213 static inline void fld_cache_entry_add(struct fld_cache *cache,
214                                        struct fld_cache_entry *f_new,
215                                        cfs_list_t *pos)
216 {
217         cfs_list_add(&f_new->fce_list, pos);
218         cfs_list_add(&f_new->fce_lru, &cache->fci_lru);
219
220         cache->fci_cache_count++;
221         fld_fix_new_list(cache);
222 }
223
224 /**
225  * Check if cache needs to be shrunk. If so - do it.
226  * Remove one entry in list and so on until cache is shrunk enough.
227  */
228 static int fld_cache_shrink(struct fld_cache *cache)
229 {
230         struct fld_cache_entry *flde;
231         cfs_list_t *curr;
232         int num = 0;
233         ENTRY;
234
235         LASSERT(cache != NULL);
236
237         if (cache->fci_cache_count < cache->fci_cache_size)
238                 RETURN(0);
239
240         curr = cache->fci_lru.prev;
241
242         while (cache->fci_cache_count + cache->fci_threshold >
243                cache->fci_cache_size && curr != &cache->fci_lru) {
244
245                 flde = cfs_list_entry(curr, struct fld_cache_entry, fce_lru);
246                 curr = curr->prev;
247                 fld_cache_entry_delete(cache, flde);
248                 num++;
249         }
250
251         CDEBUG(D_INFO, "%s: FLD cache - Shrunk by "
252                "%d entries\n", cache->fci_name, num);
253
254         RETURN(0);
255 }
256
257 /**
258  * kill all fld cache entries.
259  */
260 void fld_cache_flush(struct fld_cache *cache)
261 {
262         ENTRY;
263
264         spin_lock(&cache->fci_lock);
265         cache->fci_cache_size = 0;
266         fld_cache_shrink(cache);
267         spin_unlock(&cache->fci_lock);
268
269         EXIT;
270 }
271
272 /**
273  * punch hole in existing range. divide this range and add new
274  * entry accordingly.
275  */
276
277 void fld_cache_punch_hole(struct fld_cache *cache,
278                           struct fld_cache_entry *f_curr,
279                           struct fld_cache_entry *f_new)
280 {
281         const struct lu_seq_range *range = &f_new->fce_range;
282         const seqno_t new_start  = range->lsr_start;
283         const seqno_t new_end  = range->lsr_end;
284         struct fld_cache_entry *fldt;
285
286         ENTRY;
287         OBD_ALLOC_GFP(fldt, sizeof *fldt, CFS_ALLOC_ATOMIC);
288         if (!fldt) {
289                 OBD_FREE_PTR(f_new);
290                 EXIT;
291                 /* overlap is not allowed, so dont mess up list. */
292                 return;
293         }
294         /*  break f_curr RANGE into three RANGES:
295          *        f_curr, f_new , fldt
296          */
297
298         /* f_new = *range */
299
300         /* fldt */
301         fldt->fce_range.lsr_start = new_end;
302         fldt->fce_range.lsr_end = f_curr->fce_range.lsr_end;
303         fldt->fce_range.lsr_index = f_curr->fce_range.lsr_index;
304
305         /* f_curr */
306         f_curr->fce_range.lsr_end = new_start;
307
308         /* add these two entries to list */
309         fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
310         fld_cache_entry_add(cache, fldt, &f_new->fce_list);
311
312         /* no need to fixup */
313         EXIT;
314 }
315
316 /**
317  * handle range overlap in fld cache.
318  */
319 void fld_cache_overlap_handle(struct fld_cache *cache,
320                               struct fld_cache_entry *f_curr,
321                               struct fld_cache_entry *f_new)
322 {
323         const struct lu_seq_range *range = &f_new->fce_range;
324         const seqno_t new_start  = range->lsr_start;
325         const seqno_t new_end  = range->lsr_end;
326         const mdsno_t mdt = range->lsr_index;
327
328         /* this is overlap case, these case are checking overlapping with
329          * prev range only. fixup will handle overlaping with next range. */
330
331         if (f_curr->fce_range.lsr_index == mdt) {
332                 f_curr->fce_range.lsr_start = min(f_curr->fce_range.lsr_start,
333                                                   new_start);
334
335                 f_curr->fce_range.lsr_end = max(f_curr->fce_range.lsr_end,
336                                                 new_end);
337
338                 OBD_FREE_PTR(f_new);
339                 fld_fix_new_list(cache);
340
341         } else if (new_start <= f_curr->fce_range.lsr_start &&
342                         f_curr->fce_range.lsr_end <= new_end) {
343                 /* case 1: new range completely overshadowed existing range.
344                  *         e.g. whole range migrated. update fld cache entry */
345
346                 f_curr->fce_range = *range;
347                 OBD_FREE_PTR(f_new);
348                 fld_fix_new_list(cache);
349
350         } else if (f_curr->fce_range.lsr_start < new_start &&
351                         new_end < f_curr->fce_range.lsr_end) {
352                 /* case 2: new range fit within existing range. */
353
354                 fld_cache_punch_hole(cache, f_curr, f_new);
355
356         } else  if (new_end <= f_curr->fce_range.lsr_end) {
357                 /* case 3: overlap:
358                  *         [new_start [c_start  new_end)  c_end)
359                  */
360
361                 LASSERT(new_start <= f_curr->fce_range.lsr_start);
362
363                 f_curr->fce_range.lsr_start = new_end;
364                 fld_cache_entry_add(cache, f_new, f_curr->fce_list.prev);
365
366         } else if (f_curr->fce_range.lsr_start <= new_start) {
367                 /* case 4: overlap:
368                  *         [c_start [new_start c_end) new_end)
369                  */
370
371                 LASSERT(f_curr->fce_range.lsr_end <= new_end);
372
373                 f_curr->fce_range.lsr_end = new_start;
374                 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
375         } else
376                 CERROR("NEW range ="DRANGE" curr = "DRANGE"\n",
377                        PRANGE(range),PRANGE(&f_curr->fce_range));
378 }
379
380 /**
381  * Insert FLD entry in FLD cache.
382  *
383  * This function handles all cases of merging and breaking up of
384  * ranges.
385  */
386 void fld_cache_insert(struct fld_cache *cache,
387                       const struct lu_seq_range *range)
388 {
389         struct fld_cache_entry *f_new;
390         struct fld_cache_entry *f_curr;
391         struct fld_cache_entry *n;
392         cfs_list_t *head;
393         cfs_list_t *prev = NULL;
394         const seqno_t new_start  = range->lsr_start;
395         const seqno_t new_end  = range->lsr_end;
396         __u32 new_flags  = range->lsr_flags;
397         ENTRY;
398
399         LASSERT(range_is_sane(range));
400
401         /* Allocate new entry. */
402         OBD_ALLOC_PTR(f_new);
403         if (!f_new) {
404                 EXIT;
405                 return;
406         }
407
408         f_new->fce_range = *range;
409
410         /*
411          * Duplicate entries are eliminated in inset op.
412          * So we don't need to search new entry before starting insertion loop.
413          */
414
415         spin_lock(&cache->fci_lock);
416         fld_cache_shrink(cache);
417
418         head = &cache->fci_entries_head;
419
420         cfs_list_for_each_entry_safe(f_curr, n, head, fce_list) {
421                 /* add list if next is end of list */
422                 if (new_end < f_curr->fce_range.lsr_start ||
423                    (new_end == f_curr->fce_range.lsr_start &&
424                     new_flags != f_curr->fce_range.lsr_flags))
425                         break;
426
427                 prev = &f_curr->fce_list;
428                 /* check if this range is to left of new range. */
429                 if (new_start < f_curr->fce_range.lsr_end &&
430                     new_flags == f_curr->fce_range.lsr_flags) {
431                         fld_cache_overlap_handle(cache, f_curr, f_new);
432                         goto out;
433                 }
434         }
435
436         if (prev == NULL)
437                 prev = head;
438
439         CDEBUG(D_INFO, "insert range "DRANGE"\n", PRANGE(&f_new->fce_range));
440         /* Add new entry to cache and lru list. */
441         fld_cache_entry_add(cache, f_new, prev);
442 out:
443         spin_unlock(&cache->fci_lock);
444         EXIT;
445 }
446
447 /**
448  * lookup \a seq sequence for range in fld cache.
449  */
450 int fld_cache_lookup(struct fld_cache *cache,
451                      const seqno_t seq, struct lu_seq_range *range)
452 {
453         struct fld_cache_entry *flde;
454         cfs_list_t *head;
455         ENTRY;
456
457         spin_lock(&cache->fci_lock);
458         head = &cache->fci_entries_head;
459
460         cache->fci_stat.fst_count++;
461         cfs_list_for_each_entry(flde, head, fce_list) {
462                 if (flde->fce_range.lsr_start > seq)
463                         break;
464
465                 if (range_within(&flde->fce_range, seq)) {
466                         *range = flde->fce_range;
467
468                         /* update position of this entry in lru list. */
469                         cfs_list_move(&flde->fce_lru, &cache->fci_lru);
470                         cache->fci_stat.fst_cache++;
471                         spin_unlock(&cache->fci_lock);
472                         RETURN(0);
473                 }
474         }
475         spin_unlock(&cache->fci_lock);
476         RETURN(-ENOENT);
477 }