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