Whamcloud - gitweb
b=22891 Objects are not getting deleted for files which have been removed
[fs/lustre-release.git] / lustre / fld / fld_cache.c
1 /* -*- mode: c; c-basic-offset: 8; indent-tabs-mode: nil; -*-
2  * vim:expandtab:shiftwidth=8:tabstop=8:
3  *
4  * GPL HEADER START
5  *
6  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7  *
8  * This program is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License version 2 only,
10  * as published by the Free Software Foundation.
11  *
12  * This program is distributed in the hope that it will be useful, but
13  * WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * General Public License version 2 for more details (a copy is included
16  * in the LICENSE file that accompanied this code).
17  *
18  * You should have received a copy of the GNU General Public License
19  * version 2 along with this program; If not, see
20  * http://www.sun.com/software/products/lustre/docs/GPLv2.pdf
21  *
22  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23  * CA 95054 USA or visit www.sun.com if you need additional information or
24  * have any questions.
25  *
26  * GPL HEADER END
27  */
28 /*
29  * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
30  * Use is subject to license terms.
31  */
32 /*
33  * This file is part of Lustre, http://www.lustre.org/
34  * Lustre is a trademark of Sun Microsystems, Inc.
35  *
36  * lustre/fld/fld_cache.c
37  *
38  * FLD (Fids Location Database)
39  *
40  * Author: Pravin Shelar <pravin.shelar@sun.com>
41  * Author: Yury Umanets <umka@clusterfs.com>
42  */
43
44 #ifndef EXPORT_SYMTAB
45 # define EXPORT_SYMTAB
46 #endif
47 #define DEBUG_SUBSYSTEM S_FLD
48
49 #ifdef __KERNEL__
50 # include <libcfs/libcfs.h>
51 # include <linux/module.h>
52 # include <linux/jbd.h>
53 # include <asm/div64.h>
54 #else /* __KERNEL__ */
55 # include <liblustre.h>
56 # include <libcfs/list.h>
57 #endif
58
59 #include <obd.h>
60 #include <obd_class.h>
61 #include <lustre_ver.h>
62 #include <obd_support.h>
63 #include <lprocfs_status.h>
64
65 #include <dt_object.h>
66 #include <md_object.h>
67 #include <lustre_req_layout.h>
68 #include <lustre_fld.h>
69 #include "fld_internal.h"
70
71 /**
72  * create fld cache.
73  */
74 struct fld_cache *fld_cache_init(const char *name,
75                                  int cache_size, int cache_threshold)
76 {
77         struct fld_cache *cache;
78         ENTRY;
79
80         LASSERT(name != NULL);
81         LASSERT(cache_threshold < cache_size);
82
83         OBD_ALLOC_PTR(cache);
84         if (cache == NULL)
85                 RETURN(ERR_PTR(-ENOMEM));
86
87         CFS_INIT_LIST_HEAD(&cache->fci_entries_head);
88         CFS_INIT_LIST_HEAD(&cache->fci_lru);
89
90         cache->fci_cache_count = 0;
91         cfs_spin_lock_init(&cache->fci_lock);
92
93         strncpy(cache->fci_name, name,
94                 sizeof(cache->fci_name));
95
96         cache->fci_cache_size = cache_size;
97         cache->fci_threshold = cache_threshold;
98
99         /* Init fld cache info. */
100         memset(&cache->fci_stat, 0, sizeof(cache->fci_stat));
101
102         CDEBUG(D_INFO, "%s: FLD cache - Size: %d, Threshold: %d\n",
103                cache->fci_name, cache_size, cache_threshold);
104
105         RETURN(cache);
106 }
107
108 /**
109  * destroy fld cache.
110  */
111 void fld_cache_fini(struct fld_cache *cache)
112 {
113         __u64 pct;
114         ENTRY;
115
116         LASSERT(cache != NULL);
117         fld_cache_flush(cache);
118
119         if (cache->fci_stat.fst_count > 0) {
120                 pct = cache->fci_stat.fst_cache * 100;
121                 do_div(pct, cache->fci_stat.fst_count);
122         } else {
123                 pct = 0;
124         }
125
126         CDEBUG(D_INFO, "FLD cache statistics (%s):\n", cache->fci_name);
127         CDEBUG(D_INFO, "  Total reqs: "LPU64"\n", cache->fci_stat.fst_count);
128         CDEBUG(D_INFO, "  Cache reqs: "LPU64"\n", cache->fci_stat.fst_cache);
129         CDEBUG(D_INFO, "  Cache hits: "LPU64"%%\n", pct);
130
131         OBD_FREE_PTR(cache);
132
133         EXIT;
134 }
135
136 /**
137  * delete given node from list.
138  */
139 static inline void fld_cache_entry_delete(struct fld_cache *cache,
140                                           struct fld_cache_entry *node)
141 {
142         cfs_list_del(&node->fce_list);
143         cfs_list_del(&node->fce_lru);
144         cache->fci_cache_count--;
145         OBD_FREE_PTR(node);
146 }
147
148 /**
149  * fix list by checking new entry with NEXT entry in order.
150  */
151 static void fld_fix_new_list(struct fld_cache *cache)
152 {
153         struct fld_cache_entry *f_curr;
154         struct fld_cache_entry *f_next;
155         struct lu_seq_range *c_range;
156         struct lu_seq_range *n_range;
157         cfs_list_t *head = &cache->fci_entries_head;
158         ENTRY;
159
160 restart_fixup:
161
162         cfs_list_for_each_entry_safe(f_curr, f_next, head, fce_list) {
163                 c_range = &f_curr->fce_range;
164                 n_range = &f_next->fce_range;
165
166                 LASSERT(range_is_sane(c_range));
167                 if (&f_next->fce_list == head)
168                         break;
169
170                 LASSERT(c_range->lsr_start <= n_range->lsr_start);
171
172                 /* check merge possibility with next range */
173                 if (c_range->lsr_end == n_range->lsr_start) {
174                         if (c_range->lsr_mdt != n_range->lsr_mdt)
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
184                         if (c_range->lsr_mdt == n_range->lsr_mdt) {
185                                 n_range->lsr_start = c_range->lsr_start;
186                                 n_range->lsr_end = max(c_range->lsr_end,
187                                                        n_range->lsr_end);
188
189                                 fld_cache_entry_delete(cache, f_curr);
190                         } else {
191                                 if (n_range->lsr_end <= c_range->lsr_end) {
192                                         *n_range = *c_range;
193                                         fld_cache_entry_delete(cache, f_curr);
194                                 } else
195                                         n_range->lsr_start = c_range->lsr_end;
196                         }
197
198                         /* we could have overlap over next
199                          * range too. better restart. */
200                         goto restart_fixup;
201                 }
202
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);
207         }
208
209         EXIT;
210 }
211
212 /**
213  * add node to fld cache
214  */
215 static inline void fld_cache_entry_add(struct fld_cache *cache,
216                                        struct fld_cache_entry *f_new,
217                                        cfs_list_t *pos)
218 {
219         cfs_list_add(&f_new->fce_list, pos);
220         cfs_list_add(&f_new->fce_lru, &cache->fci_lru);
221
222         cache->fci_cache_count++;
223         fld_fix_new_list(cache);
224 }
225
226 /**
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.
229  */
230 static int fld_cache_shrink(struct fld_cache *cache)
231 {
232         struct fld_cache_entry *flde;
233         cfs_list_t *curr;
234         int num = 0;
235         ENTRY;
236
237         LASSERT(cache != NULL);
238
239         if (cache->fci_cache_count < cache->fci_cache_size)
240                 RETURN(0);
241
242         curr = cache->fci_lru.prev;
243
244         while (cache->fci_cache_count + cache->fci_threshold >
245                cache->fci_cache_size && curr != &cache->fci_lru) {
246
247                 flde = cfs_list_entry(curr, struct fld_cache_entry, fce_lru);
248                 curr = curr->prev;
249                 fld_cache_entry_delete(cache, flde);
250                 num++;
251         }
252
253         CDEBUG(D_INFO, "%s: FLD cache - Shrunk by "
254                "%d entries\n", cache->fci_name, num);
255
256         RETURN(0);
257 }
258
259 /**
260  * kill all fld cache entries.
261  */
262 void fld_cache_flush(struct fld_cache *cache)
263 {
264         ENTRY;
265
266         cfs_spin_lock(&cache->fci_lock);
267         cache->fci_cache_size = 0;
268         fld_cache_shrink(cache);
269         cfs_spin_unlock(&cache->fci_lock);
270
271         EXIT;
272 }
273
274 /**
275  * punch hole in existing range. divide this range and add new
276  * entry accordingly.
277  */
278
279 void fld_cache_punch_hole(struct fld_cache *cache,
280                           struct fld_cache_entry *f_curr,
281                           struct fld_cache_entry *f_new)
282 {
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;
287
288         ENTRY;
289         OBD_ALLOC_GFP(fldt, sizeof *fldt, CFS_ALLOC_ATOMIC);
290         if (!fldt) {
291                 OBD_FREE_PTR(f_new);
292                 EXIT;
293                 /* overlap is not allowed, so dont mess up list. */
294                 return;
295         }
296         /*  break f_curr RANGE into three RANGES:
297          *        f_curr, f_new , fldt
298          */
299
300         /* f_new = *range */
301
302         /* 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_mdt = f_curr->fce_range.lsr_mdt;
306
307         /* f_curr */
308         f_curr->fce_range.lsr_end = new_start;
309
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);
313
314         /* no need to fixup */
315         EXIT;
316 }
317
318 /**
319  * handle range overlap in fld cache.
320  */
321 void fld_cache_overlap_handle(struct fld_cache *cache,
322                               struct fld_cache_entry *f_curr,
323                               struct fld_cache_entry *f_new)
324 {
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_mdt;
329
330         /* this is overlap case, these case are checking overlapping with
331          * prev range only. fixup will handle overlaping with next range. */
332
333         if (f_curr->fce_range.lsr_mdt == mdt) {
334                 f_curr->fce_range.lsr_start = min(f_curr->fce_range.lsr_start,
335                                                   new_start);
336
337                 f_curr->fce_range.lsr_end = max(f_curr->fce_range.lsr_end,
338                                                 new_end);
339
340                 OBD_FREE_PTR(f_new);
341                 fld_fix_new_list(cache);
342
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 */
347
348                 f_curr->fce_range = *range;
349                 OBD_FREE_PTR(f_new);
350                 fld_fix_new_list(cache);
351
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. */
355
356                 fld_cache_punch_hole(cache, f_curr, f_new);
357
358         } else  if (new_end <= f_curr->fce_range.lsr_end) {
359                 /* case 3: overlap:
360                  *         [new_start [c_start  new_end)  c_end)
361                  */
362
363                 LASSERT(new_start <= f_curr->fce_range.lsr_start);
364
365                 f_curr->fce_range.lsr_start = new_end;
366                 fld_cache_entry_add(cache, f_new, f_curr->fce_list.prev);
367
368         } else if (f_curr->fce_range.lsr_start <= new_start) {
369                 /* case 4: overlap:
370                  *         [c_start [new_start c_end) new_end)
371                  */
372
373                 LASSERT(f_curr->fce_range.lsr_end <= new_end);
374
375                 f_curr->fce_range.lsr_end = new_start;
376                 fld_cache_entry_add(cache, f_new, &f_curr->fce_list);
377         } else
378                 CERROR("NEW range ="DRANGE" curr = "DRANGE"\n",
379                        PRANGE(range),PRANGE(&f_curr->fce_range));
380 }
381
382 /**
383  * Insert FLD entry in FLD cache.
384  *
385  * This function handles all cases of merging and breaking up of
386  * ranges.
387  */
388 void fld_cache_insert(struct fld_cache *cache,
389                       const struct lu_seq_range *range)
390 {
391         struct fld_cache_entry *f_new;
392         struct fld_cache_entry *f_curr;
393         struct fld_cache_entry *n;
394         cfs_list_t *head;
395         cfs_list_t *prev = NULL;
396         const seqno_t new_start  = range->lsr_start;
397         const seqno_t new_end  = range->lsr_end;
398         ENTRY;
399
400         LASSERT(range_is_sane(range));
401
402         /* Allocate new entry. */
403         OBD_ALLOC_PTR(f_new);
404         if (!f_new) {
405                 EXIT;
406                 return;
407         }
408
409         f_new->fce_range = *range;
410
411         /*
412          * Duplicate entries are eliminated in inset op.
413          * So we don't need to search new entry before starting insertion loop.
414          */
415
416         cfs_spin_lock(&cache->fci_lock);
417         fld_cache_shrink(cache);
418
419         head = &cache->fci_entries_head;
420
421         cfs_list_for_each_entry_safe(f_curr, n, head, fce_list) {
422                 /* add list if next is end of list */
423                 if (new_end < f_curr->fce_range.lsr_start)
424                         break;
425
426                 prev = &f_curr->fce_list;
427                 /* check if this range is to left of new range. */
428                 if (new_start < f_curr->fce_range.lsr_end) {
429                         fld_cache_overlap_handle(cache, f_curr, f_new);
430                         goto out;
431                 }
432         }
433
434         if (prev == NULL)
435                 prev = head;
436
437         /* Add new entry to cache and lru list. */
438         fld_cache_entry_add(cache, f_new, prev);
439 out:
440         cfs_spin_unlock(&cache->fci_lock);
441         EXIT;
442 }
443
444 /**
445  * lookup \a seq sequence for range in fld cache.
446  */
447 int fld_cache_lookup(struct fld_cache *cache,
448                      const seqno_t seq, struct lu_seq_range *range)
449 {
450         struct fld_cache_entry *flde;
451         cfs_list_t *head;
452         ENTRY;
453
454
455         cfs_spin_lock(&cache->fci_lock);
456         head = &cache->fci_entries_head;
457
458         cache->fci_stat.fst_count++;
459         cfs_list_for_each_entry(flde, head, fce_list) {
460                 if (flde->fce_range.lsr_start > seq)
461                         break;
462
463                 if (range_within(&flde->fce_range, seq)) {
464                         *range = flde->fce_range;
465
466                         /* update position of this entry in lru list. */
467                         cfs_list_move(&flde->fce_lru, &cache->fci_lru);
468                         cache->fci_stat.fst_cache++;
469                         cfs_spin_unlock(&cache->fci_lock);
470                         RETURN(0);
471                 }
472         }
473         cfs_spin_unlock(&cache->fci_lock);
474         RETURN(-ENOENT);
475 }