Whamcloud - gitweb
LU-1445 osd: add fld look up in osd.
[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  * Copyright (c) 2012, 2013, Intel Corporation.
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 #define DEBUG_SUBSYSTEM S_FLD
45
46 #ifdef __KERNEL__
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>
54 #endif
55
56 #include <obd.h>
57 #include <obd_class.h>
58 #include <lustre_ver.h>
59 #include <obd_support.h>
60 #include <lprocfs_status.h>
61
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"
67
68 /**
69  * create fld cache.
70  */
71 struct fld_cache *fld_cache_init(const char *name,
72                                  int cache_size, int cache_threshold)
73 {
74         struct fld_cache *cache;
75         ENTRY;
76
77         LASSERT(name != NULL);
78         LASSERT(cache_threshold < cache_size);
79
80         OBD_ALLOC_PTR(cache);
81         if (cache == NULL)
82                 RETURN(ERR_PTR(-ENOMEM));
83
84         CFS_INIT_LIST_HEAD(&cache->fci_entries_head);
85         CFS_INIT_LIST_HEAD(&cache->fci_lru);
86
87         cache->fci_cache_count = 0;
88         rwlock_init(&cache->fci_lock);
89
90         strncpy(cache->fci_name, name,
91                 sizeof(cache->fci_name));
92
93         cache->fci_cache_size = cache_size;
94         cache->fci_threshold = cache_threshold;
95
96         /* Init fld cache info. */
97         memset(&cache->fci_stat, 0, sizeof(cache->fci_stat));
98
99         CDEBUG(D_INFO, "%s: FLD cache - Size: %d, Threshold: %d\n",
100                cache->fci_name, cache_size, cache_threshold);
101
102         RETURN(cache);
103 }
104
105 /**
106  * destroy fld cache.
107  */
108 void fld_cache_fini(struct fld_cache *cache)
109 {
110         __u64 pct;
111         ENTRY;
112
113         LASSERT(cache != NULL);
114         fld_cache_flush(cache);
115
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);
119         } else {
120                 pct = 0;
121         }
122
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);
127
128         OBD_FREE_PTR(cache);
129
130         EXIT;
131 }
132
133 /**
134  * delete given node from list.
135  */
136 void fld_cache_entry_delete(struct fld_cache *cache,
137                             struct fld_cache_entry *node)
138 {
139         cfs_list_del(&node->fce_list);
140         cfs_list_del(&node->fce_lru);
141         cache->fci_cache_count--;
142         OBD_FREE_PTR(node);
143 }
144
145 /**
146  * fix list by checking new entry with NEXT entry in order.
147  */
148 static void fld_fix_new_list(struct fld_cache *cache)
149 {
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;
155         ENTRY;
156
157 restart_fixup:
158
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;
162
163                 LASSERT(range_is_sane(c_range));
164                 if (&f_next->fce_list == head)
165                         break;
166
167                 if (c_range->lsr_flags != n_range->lsr_flags)
168                         continue;
169
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));
173
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)
177                                 continue;
178                         n_range->lsr_start = c_range->lsr_start;
179                         fld_cache_entry_delete(cache, f_curr);
180                         continue;
181                 }
182
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,
188                                                        n_range->lsr_end);
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         write_lock(&cache->fci_lock);
267         cache->fci_cache_size = 0;
268         fld_cache_shrink(cache);
269         write_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_index = f_curr->fce_range.lsr_index;
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 static 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_index;
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_index == 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 struct fld_cache_entry
383 *fld_cache_entry_create(const struct lu_seq_range *range)
384 {
385         struct fld_cache_entry *f_new;
386
387         LASSERT(range_is_sane(range));
388
389         OBD_ALLOC_PTR(f_new);
390         if (!f_new)
391                 RETURN(ERR_PTR(-ENOMEM));
392
393         f_new->fce_range = *range;
394         RETURN(f_new);
395 }
396
397 /**
398  * Insert FLD entry in FLD cache.
399  *
400  * This function handles all cases of merging and breaking up of
401  * ranges.
402  */
403 int fld_cache_insert_nolock(struct fld_cache *cache,
404                             struct fld_cache_entry *f_new)
405 {
406         struct fld_cache_entry *f_curr;
407         struct fld_cache_entry *n;
408         cfs_list_t *head;
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;
413         ENTRY;
414
415         /*
416          * Duplicate entries are eliminated in insert op.
417          * So we don't need to search new entry before starting
418          * insertion loop.
419          */
420
421         if (!cache->fci_no_shrink)
422                 fld_cache_shrink(cache);
423
424         head = &cache->fci_entries_head;
425
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))
431                         break;
432
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);
438                         goto out;
439                 }
440         }
441
442         if (prev == NULL)
443                 prev = head;
444
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);
448 out:
449         RETURN(0);
450 }
451
452 int fld_cache_insert(struct fld_cache *cache,
453                      const struct lu_seq_range *range)
454 {
455         struct fld_cache_entry  *flde;
456         int rc;
457
458         flde = fld_cache_entry_create(range);
459         if (IS_ERR(flde))
460                 RETURN(PTR_ERR(flde));
461
462         write_lock(&cache->fci_lock);
463         rc = fld_cache_insert_nolock(cache, flde);
464         write_unlock(&cache->fci_lock);
465         if (rc)
466                 OBD_FREE_PTR(flde);
467
468         RETURN(rc);
469 }
470
471 void fld_cache_delete_nolock(struct fld_cache *cache,
472                       const struct lu_seq_range *range)
473 {
474         struct fld_cache_entry *flde;
475         struct fld_cache_entry *tmp;
476         cfs_list_t *head;
477
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);
485                         break;
486                 }
487         }
488 }
489
490 /**
491  * Delete FLD entry in FLD cache.
492  *
493  */
494 void fld_cache_delete(struct fld_cache *cache,
495                       const struct lu_seq_range *range)
496 {
497         write_lock(&cache->fci_lock);
498         fld_cache_delete_nolock(cache, range);
499         write_unlock(&cache->fci_lock);
500 }
501
502 struct fld_cache_entry
503 *fld_cache_entry_lookup_nolock(struct fld_cache *cache,
504                               struct lu_seq_range *range)
505 {
506         struct fld_cache_entry *flde;
507         struct fld_cache_entry *got = NULL;
508         cfs_list_t *head;
509
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)) {
515                         got = flde;
516                         break;
517                 }
518         }
519
520         RETURN(got);
521 }
522
523 /**
524  * lookup \a seq sequence for range in fld cache.
525  */
526 struct fld_cache_entry
527 *fld_cache_entry_lookup(struct fld_cache *cache, struct lu_seq_range *range)
528 {
529         struct fld_cache_entry *got = NULL;
530         ENTRY;
531
532         read_lock(&cache->fci_lock);
533         got = fld_cache_entry_lookup_nolock(cache, range);
534         read_unlock(&cache->fci_lock);
535         RETURN(got);
536 }
537
538 /**
539  * lookup \a seq sequence for range in fld cache.
540  */
541 int fld_cache_lookup(struct fld_cache *cache,
542                      const seqno_t seq, struct lu_seq_range *range)
543 {
544         struct fld_cache_entry *flde;
545         struct fld_cache_entry *prev = NULL;
546         cfs_list_t *head;
547         ENTRY;
548
549         read_lock(&cache->fci_lock);
550         head = &cache->fci_entries_head;
551
552         cache->fci_stat.fst_count++;
553         cfs_list_for_each_entry(flde, head, fce_list) {
554                 if (flde->fce_range.lsr_start > seq) {
555                         if (prev != NULL)
556                                 memcpy(range, prev, sizeof(*range));
557                         break;
558                 }
559
560                 prev = flde;
561                 if (range_within(&flde->fce_range, seq)) {
562                         *range = flde->fce_range;
563
564                         cache->fci_stat.fst_cache++;
565                         read_unlock(&cache->fci_lock);
566                         RETURN(0);
567                 }
568         }
569         read_unlock(&cache->fci_lock);
570         RETURN(-ENOENT);
571 }
572